bug-gnulib
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [PATCH] hash: declare some functions with the warn_unused_result att


From: Eric Blake
Subject: Re: [PATCH] hash: declare some functions with the warn_unused_result attribute
Date: Tue, 16 Jun 2009 07:06:26 -0600
User-agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.8.1.21) Gecko/20090302 Thunderbird/2.0.0.21 Mnenhy/0.7.6.666

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

According to Eric Blake on 6/15/2009 5:17 PM:
>>> Additionally, it looks like hash_rehash has a memory leak - if new_table
>>> is allocated, but we later fail to allocate new_entry, the function
>>> returns immediately without reclaiming new_table.  Which means that even
>>> if an application is prepared to deal with a false return by trying other
>>> means to reduce memory usage rather than just giving up with xalloc_die,
>>> the leaked memory from the previous attempt will interfere.
>> Good catch.
>> That is definitely a bug.
> 
> How does this look as a patch?  Is my logic sound for: a) my claim that 
> the 'goto fail' path in hash_rehash will not encounter subsequent memory 
> allocation failure, and b) my claim that a failed rehash when shrinking the 
> table on hash_delete can be ignored?

I thought of another approach (at any rate, it uses fewer lines of code,
so it should be easier to understand).  Rather than dealing with memory
allocation failures after we have already started moving objects out of
the old table into the new, we can instead guarantee up front that there
are enough free entries to be recycled so that the motion will not need to
allocate memory.  The worst case is that the old hash table had
n_buckets_used, but the hasher consolidates everything into the same
bucket when paired with the new size.  So if we merely guarantee that
there are n_buckets_used-1 free entries prior to entering the for loop to
move entries from old to new, then we know that allocation will not occur
once we start, and we need not worry about a failed allocation and have
thus avoided the memory leak of new_table.

And while writing this, I also noticed that hash_insert was inconsistent;
when it returned NULL, the caller did not know whether the entry had been
inserted or not.  So I fixed it to guarantee that a NULL return due to a
rehash running out of memory means no insertion occurred, even if there
was room without the rehash.

OK to apply?

- --
Don't work too hard, make some time for fun as well!

Eric Blake             address@hidden
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Public key at home.comcast.net/~ericblake/eblake.gpg
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAko3mNIACgkQ84KuGfSFAYDtyACgsVkTwD0ouS0VxV91P4G1UeqA
Uz8AoK+wiE+Lpu2FSRJGSChPt/+lEHLQ
=FKrg
-----END PGP SIGNATURE-----
>From 9f87604424fc0bd0a1c0006bb0beb2c8d458b9f7 Mon Sep 17 00:00:00 2001
From: Eric Blake <address@hidden>
Date: Tue, 16 Jun 2009 06:56:10 -0600
Subject: [PATCH] hash: improve memory management

* lib/hash.c (hash_delete): Free entries if resize failed.
(hash_insert): Don't leave entry on table when returning failure.
(hash_rehash): Avoid memory leak, by guaranteeing that we won't
allocate once we start moving entries.

Signed-off-by: Eric Blake <address@hidden>
---
 ChangeLog  |    6 +++++
 lib/hash.c |   73 +++++++++++++++++++++++++++++++++++++++++++++++++++--------
 2 files changed, 69 insertions(+), 10 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index fdd1120..c3e7cdc 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,11 @@
 2009-06-16  Eric Blake  <address@hidden>

+       hash: improve memory management
+       * lib/hash.c (hash_delete): Free entries if resize failed.
+       (hash_insert): Don't leave entry on table when returning failure.
+       (hash_rehash): Avoid memory leak, by guaranteeing that we won't
+       allocate once we start moving entries.
+
        strstr: replace on platforms with broken memchr
        * m4/strstr.m4 (gl_FUNC_STRSTR): Also replace strstr if the
        platform version is linear but memchr is broken, per Debian bug
diff --git a/lib/hash.c b/lib/hash.c
index 7d76d45..d217040 100644
--- a/lib/hash.c
+++ b/lib/hash.c
@@ -1,7 +1,7 @@
 /* hash - hashing table processing.

-   Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2006, 2007 Free
-   Software Foundation, Inc.
+   Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2006, 2007,
+   2009 Free Software Foundation, Inc.

    Written by Jim Meyering, 1992.

@@ -827,6 +827,39 @@ hash_rehash (Hash_table *table, size_t candidate)
   if (new_table == NULL)
     return false;

+  /* Guarantee that once we start moving entries into the new table,
+     we will not need any further memory allocations.  We only need
+     new allocations if the hasher consolidates multiple buckets from
+     the old size into one bucket with the new size (a sign of a bad
+     hasher, but we must deal with it).  Therefore, we need merely
+     check that there are at least table->n_buckets_used-1 entries on
+     the free entry list for the worst case collision (everything gets
+     combined into one bucket during the rehash).  */
+  {
+    size_t needed = table->n_buckets_used - 1;
+    cursor = table->free_entry_list;
+    while (cursor)
+      {
+       cursor = cursor->next;
+       needed--;
+      }
+    while (needed--)
+      {
+#if USE_OBSTACK
+       cursor = obstack_alloc (&table->entry_stack, sizeof *cursor);
+#else
+       cursor = malloc (sizeof *cursor);
+#endif
+       if (!cursor)
+         {
+           free (new_table);
+           return false;
+         }
+       cursor->next = table->free_entry_list;
+       table->free_entry_list = cursor;
+      }
+  }
+
   /* Merely reuse the extra old space into the new table.  */
 #if USE_OBSTACK
   obstack_free (&new_table->entry_stack, NULL);
@@ -857,7 +890,7 @@ hash_rehash (Hash_table *table, size_t candidate)
                  struct hash_entry *new_entry = allocate_entry (new_table);

                  if (new_entry == NULL)
-                   return false;
+                   abort ();

                  new_entry->data = data;
                  new_entry->next = new_bucket->next;
@@ -962,12 +995,14 @@ hash_insert (Hash_table *table, const void *entry)
             : (table->n_buckets * tuning->growth_factor
                * tuning->growth_threshold));

-         if (SIZE_MAX <= candidate)
-           return NULL;
-
-         /* If the rehash fails, arrange to return NULL.  */
-         if (!hash_rehash (table, candidate))
-           entry = NULL;
+         /* If the rehash fails, remove the entry that we just
+            inserted, and arrange to return NULL.  */
+         if (SIZE_MAX <= candidate || !hash_rehash (table, candidate))
+           {
+             if (hash_delete (table, entry) != entry)
+               abort ();
+             entry = NULL;
+           }
        }
     }

@@ -1012,7 +1047,25 @@ hash_delete (Hash_table *table, const void *entry)
                 : (table->n_buckets * tuning->shrink_factor
                    * tuning->growth_threshold));

-             hash_rehash (table, candidate);
+             if (hash_rehash (table, candidate))
+               {
+                 /* Failure to allocate memory in an attempt to
+                    shrink the table is not fatal.  But since memory
+                    is low, we can at least be kind and free any
+                    spare entries, rather than keeping them tied up
+                    in the free entry list.  */
+#if ! USE_OBSTACK
+                 struct hash_entry *cursor = table->free_entry_list;
+                 struct hash_entry *next;
+                 while (cursor)
+                   {
+                     next = cursor->next;
+                     free (cursor);
+                     cursor = next;
+                   }
+                 table->free_entry_list = NULL;
+#endif
+               }
            }
        }
     }
-- 
1.6.3.rc3.2.g4b51


reply via email to

[Prev in Thread] Current Thread [Next in Thread]