[RFA] Fix leak detected in GDB test gdb.base/macscp.exp

[RFA] Fix leak detected in GDB test gdb.base/macscp.exp

[Philippe Waroquiers]

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.

Fix the leak by calling the delete key function when removing a node.

Also, clarify the documentation about when the release functions are
called.

include/ChangeLog
2019-01-19  Philippe Waroquiers  <philippe.waroquiers@skynet.be>

	* splay-tree.h (splay_tree_delete_key_fn): Update comment.

libiberty/ChangeLog
2019-01-19  Philippe Waroquiers  <philippe.waroquiers@skynet.be>

	* splay-tree.c (splay_tree_remove): Call sp->delete_key.
	(splay_tree_new_typed_alloc): Update comment.
---
 include/splay-tree.h   |  5 ++++-
 libiberty/splay-tree.c | 18 +++++++++++++++++-
 2 files changed, 21 insertions(+), 2 deletions(-)

diff --git a/include/splay-tree.h b/include/splay-tree.h
index 0d26272943..44a9369d75 100644
--- a/include/splay-tree.h
+++ b/include/splay-tree.h
@@ -58,7 +58,10 @@ 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.  This is called to release the keys present in the
+   tree when calling splay_tree_delete or splay_tree_remove.  The
+   caller of splay_tree_insert might have to call it if the same key
+   value is re-inserted in the tree.  */
 typedef void (*splay_tree_delete_key_fn) (splay_tree_key);
 
 /* The type of a function used to deallocate any resources associated
diff --git a/libiberty/splay-tree.c b/libiberty/splay-tree.c
index 920e68db2c..93069c5daa 100644
--- a/libiberty/splay-tree.c
+++ b/libiberty/splay-tree.c
@@ -318,7 +318,21 @@ 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 previous
+value using @var{delete_value_fn} if the inserted key is already found
+in the tree.  In such a case, if the caller has allocated a new key
+to call splay_tree_insert, it is the responsibility of the caller to
+release the newly allocated key, as the tree does not take ownership
+of the key given in argument in case of re-insertion of the same key
+value.  So, typically, the caller might do:
+   splay_tree_key k = ...allocate a key ...;
+   splay_tree_node s = splay_tree_insert (tree, k, value);
+   if ((struct macro_key *) s->key != k)
+     macro_tree_delete_key (k);
+to ensure the newly allocated splay_tree_key k is released when the same
+k value was already present in the tree.
 
 @end deftypefn
 
@@ -427,6 +441,8 @@ splay_tree_remove (splay_tree sp, splay_tree_key key)
       /* Delete the root node itself.  */
       if (sp->delete_value)
 	(*sp->delete_value) (sp->root->value);
+      if (sp->delete_key)
+         sp->delete_key (sp->root->key);
       (*sp->deallocate) (sp->root, sp->allocate_data);
 
       /* One of the children is now the root.  Doesn't matter much
-- 
2.20.1

Re: [RFA] Fix leak detected in GDB test gdb.base/macscp.exp

[Tom Tromey]

>>>>> "Philippe" == Philippe Waroquiers <philippe.waroquiers@skynet.be> writes:

Philippe> libiberty/ChangeLog
Philippe> 2019-01-19  Philippe Waroquiers  <philippe.waroquiers@skynet.be>
Philippe> 	* splay-tree.c (splay_tree_remove): Call sp->delete_key.
Philippe> 	(splay_tree_new_typed_alloc): Update comment.

Like I mentioned before, I didn't see this before sending my own patch
to gcc.

I'm checking in the appended to binutils-gdb now.

I looked at all splay_tree_new* calls in binutils-gdb and the only one
impacted is the one in gdb that causes the leak.

Tom

commit 33ee267e434ae4b7acb44537f8be5a6663f3b70f
Author: Tom Tromey <tom@tromey.com>
Date:   Fri Jan 18 14:19:55 2019 -0700

    Fix leak in splay-tree
    
    Philippe Waroquiers noticed a memory leak in gdb, which he tracked
    down to a bug in splay-tree.  splay_tree_remove does not call the
    `delete_key' function when it removes the old node; but it should.
    
    I looked at every splay tree in GCC and there is only one that passes
    a non-NULL delete function -- the one in lto.c.  That file does not
    call splay_tree_remove.  So, I think this is safe to check in.
    
    I re-ran the LTO tests to double check.
    
    libiberty/
            * splay-tree.c (splay_tree_remove): Delete the key if necessary.

diff --git a/libiberty/ChangeLog b/libiberty/ChangeLog
index bcc0227bdd8..1eb25f928f2 100644
--- a/libiberty/ChangeLog
+++ b/libiberty/ChangeLog
@@ -1,3 +1,7 @@
+2019-01-18  Tom Tromey  <tom@tromey.com>
+
+	* splay-tree.c (splay_tree_remove): Delete the key if necessary.
+
 2019-01-14  Tom Honermann  <tom@honermann.net>
 
 	* cp-demangle.c (cplus_demangle_builtin_types)
diff --git a/libiberty/splay-tree.c b/libiberty/splay-tree.c
index 920e68db2cb..21d23c38dfc 100644
--- a/libiberty/splay-tree.c
+++ b/libiberty/splay-tree.c
@@ -425,6 +425,8 @@ splay_tree_remove (splay_tree sp, splay_tree_key key)
       right = sp->root->right;
 
       /* Delete the root node itself.  */
+      if (sp->delete_key)
+	(*sp->delete_key) (sp->root->key);
       if (sp->delete_value)
 	(*sp->delete_value) (sp->root->value);
       (*sp->deallocate) (sp->root, sp->allocate_data);