From patchwork Wed Feb 6 13:59:21 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom Tromey X-Patchwork-Id: 1037547 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-495380-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=tromey.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="Y8LzpbTX"; dkim=fail reason="signature verification failed" (768-bit key; unprotected) header.d=tromey.com header.i=@tromey.com header.b="ZlNjLGhn"; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 43vjrR2D2lz9sLw for ; Thu, 7 Feb 2019 01:05:04 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:subject:date:message-id:mime-version:content-type; q=dns; s= default; b=klvxcgfYsvF9zRMDclJw0xkp0jAJo0jk3tXntXnxIiz1TbKJ4+MBm LnnDNOhGrY1QQuO753+iGtg5fHniInreA4GDaMEoJSrzIFWgYtqn+tdn7pkhaRH5 1c/A46u4/R6/JKnF67hNErwbC9/r++6IsAfrYUA48lOrbirB+NnLzs= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:subject:date:message-id:mime-version:content-type; s= default; bh=TcVvK0SfYW+fBecc+/U5RJ8vv1Q=; b=Y8LzpbTXo5EcrV8z3UFW dcAssfnO8IokTJ8ig8irWqL6Jmj4eP1Ohd+NPxc68ZYcvk4lgSUTPpOoSSVQihRm pVbTMwuoaAczDYqktr/0fUn/qlgYXLdXO9yiNb1FcRt8pcJfKG+zNJbdkm9vkZby dkdekpgddlNsdfFRyIFU4es= Received: (qmail 50720 invoked by alias); 6 Feb 2019 14:04:58 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 50650 invoked by uid 89); 6 Feb 2019 14:04:56 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-26.9 required=5.0 tests=BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_NONE, SPF_HELO_PASS autolearn=ham version=3.3.2 spammy=ownership X-HELO: gateway36.websitewelcome.com Received: from gateway36.websitewelcome.com (HELO gateway36.websitewelcome.com) (192.185.193.119) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 06 Feb 2019 14:04:54 +0000 Received: from cm16.websitewelcome.com (cm16.websitewelcome.com [100.42.49.19]) by gateway36.websitewelcome.com (Postfix) with ESMTP id 7B204400EC185 for ; Wed, 6 Feb 2019 07:13:11 -0600 (CST) Received: from box5379.bluehost.com ([162.241.216.53]) by cmsmtp with SMTP id rNjZgEdXq4FKprNjZgaYLV; Wed, 06 Feb 2019 07:59:25 -0600 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=tromey.com; s=default; h=Content-Type:MIME-Version:Message-ID:Date:Subject:To:From: Sender:Reply-To:Cc:Content-Transfer-Encoding:Content-ID:Content-Description: Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID: In-Reply-To:References:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=w6Bp/4cuIg4+VpxNTDIkZKxVQnaO5WowrfrMG0TJ2zE=; b=ZlNjLGhneH3aCoTtL2iNIDMkUv OgeUnIpGQVmvPDbGX4/7XVIAaQl95wcXzlbO/1xjLAbvpRqRkPDD1NnyvCjOQHWidS620X3ldNjpz H7YVrhaXWFNOt12wNn6Zlq810; Received: from dhcp-guest.act-europe.fr ([194.98.77.127]:51867 helo=bapiya) by box5379.bluehost.com with esmtpsa (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (Exim 4.91) (envelope-from ) id 1grNjY-002mQZ-OI; Wed, 06 Feb 2019 07:59:25 -0600 From: Tom Tromey To: gcc-patches@gcc.gnu.org Subject: [gmane.comp.gdb.patches] [RFA] Fix splay tree KEY leak detected in GDB test gdb.base/macscp.exp Date: Wed, 06 Feb 2019 06:59:21 -0700 Message-ID: <87h8dh81c6.fsf@tromey.com> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.1.90 (gnu/linux) MIME-Version: 1.0 Philippe Waroquiers found another splay-tree memory leak and sent this patch to the gdb patch list. I'm forwarding it here, as splay-tree is canonically maintained in gcc; if approved I will check it in for him. Note that the analysis from the previous splay-tree patch applies here as well: there is a single user of the key-deletion functionality in gcc, and I believe it remains safe with this patch. (In fact, if duplicate keys were ever used, this would fix a leak in gcc. I am not sure whether or not that can happen though.) thanks, Tom When a node is removed from a splay tree, the splay tree was not using the function splay_tree_delete_key_fn to release the key. This was causing a leak, fixed by Tom Tromey. This patch fixes another key leak, that happens when a key equal to a key already present is inserted. In such a case, we have to release the old KEY. Note that this is based on the assumption that the caller always allocates a new KEY when doing an insert. Also, clarify the documentation about when the release functions are called. include/ChangeLog 2019-01-26 Philippe Waroquiers * splay-tree.h (splay_tree_delete_key_fn): Update comment. (splay_tree_delete_value_fn): Likewise. libiberty/ChangeLog 2019-01-26 Philippe Waroquiers * splay-tree.c (splay_tree_insert): Also release old KEY in case of insertion of a key equal to an already present key. (splay_tree_new_typed_alloc): Update comment. --- include/splay-tree.h | 11 +++++++++-- libiberty/splay-tree.c | 13 ++++++++++--- 2 files changed, 19 insertions(+), 5 deletions(-) diff --git a/include/splay-tree.h b/include/splay-tree.h index 0d26272943..da533dec18 100644 --- a/include/splay-tree.h +++ b/include/splay-tree.h @@ -58,11 +58,18 @@ typedef struct splay_tree_node_s *splay_tree_node; typedef int (*splay_tree_compare_fn) (splay_tree_key, splay_tree_key); /* The type of a function used to deallocate any resources associated - with the key. */ + with the key. If you provide this function, the splay tree + will take the ownership of the memory of the splay_tree_key arg + of splay_tree_insert. This function is called to release the keys + present in the tree when calling splay_tree_delete or splay_tree_remove. + If splay_tree_insert is called with a key equal to a key already + present in the tree, the old key and old value will be released. */ typedef void (*splay_tree_delete_key_fn) (splay_tree_key); /* The type of a function used to deallocate any resources associated - with the value. */ + with the value. If you provide this function, the memory of the + splay_tree_value arg of splay_tree_insert is managed similarly to + the splay_tree_key memory: see splay_tree_delete_key_fn. */ typedef void (*splay_tree_delete_value_fn) (splay_tree_value); /* The type of a function used to iterate over the tree. */ diff --git a/libiberty/splay-tree.c b/libiberty/splay-tree.c index 21d23c38df..4bbb39a62c 100644 --- a/libiberty/splay-tree.c +++ b/libiberty/splay-tree.c @@ -318,7 +318,11 @@ different types need to be allocated with different allocators. The splay tree will use @var{compare_fn} to compare nodes, @var{delete_key_fn} to deallocate keys, and @var{delete_value_fn} to -deallocate values. +deallocate values. Keys and values will be deallocated when the +tree is deleted using splay_tree_delete or when a node is removed +using splay_tree_remove. splay_tree_insert will release the previously +inserted key and value using @var{delete_key_fn} and @var{delete_value_fn} +if the inserted key is already found in the tree. @end deftypefn @@ -372,10 +376,13 @@ splay_tree_insert (splay_tree sp, splay_tree_key key, splay_tree_value value) if (sp->root && comparison == 0) { - /* If the root of the tree already has the indicated KEY, just - replace the value with VALUE. */ + /* If the root of the tree already has the indicated KEY, delete + the old key and old value, and replace them with KEY and VALUE. */ + if (sp->delete_key) + (*sp->delete_key) (sp->root->key); if (sp->delete_value) (*sp->delete_value)(sp->root->value); + sp->root->key = key; sp->root->value = value; } else