bug-gnulib
[Top][All Lists]
Advanced

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

Re: another hash cleanup


From: Eric Blake
Subject: Re: another hash cleanup
Date: Fri, 19 Jun 2009 06:37:29 -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 Jim Meyering on 6/19/2009 6:02 AM:
>> But, come to think of it, why are we even malloc'ing the new_table at all
>> in this code path?  Maybe the better technical approach would be factoring
>> out the table size computation from hash_initialize, and have both
>> hash_initialize and hash_rehash first compute the needed size and later do
>> the malloc, so that hash_rehash doesn't even malloc in the first place if
>> the size computation shows it isn't necessary.
> 
> Yes, I think that would be better still.

Like so, along with an overflow bug fix.  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

iEYEARECAAYFAko7hokACgkQ84KuGfSFAYCirgCgjr5GN1iT6/BkdINnKLzNeuiP
4C0An2ySuWdxkgpeYmLYNtpO2ShUFd5P
=o/XC
-----END PGP SIGNATURE-----
>From 5db730acab3f7d73137abc4419d11ff7b4a97949 Mon Sep 17 00:00:00 2001
From: Eric Blake <address@hidden>
Date: Fri, 19 Jun 2009 06:35:11 -0600
Subject: [PATCH] hash: reduce memory pressure in hash_rehash no-op case

* lib/hash.c (next_prime): Avoid overflow.
(hash_initialize): Factor bucket size computation...
(compute_bucket_size): ...into new helper function.
(hash_rehash): Use new function and open coding to reduce memory
pressure, and avoids a memory leak in USE_OBSTACK code.
Reported by Jim Meyering.

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

diff --git a/ChangeLog b/ChangeLog
index 70de83e..2574b78 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,13 @@
+2009-06-19  Eric Blake  <address@hidden>
+
+       hash: reduce memory pressure in hash_rehash no-op case
+       * lib/hash.c (next_prime): Avoid overflow.
+       (hash_initialize): Factor bucket size computation...
+       (compute_bucket_size): ...into new helper function.
+       (hash_rehash): Use new function and open coding to reduce memory
+       pressure, and avoids a memory leak in USE_OBSTACK code.
+       Reported by Jim Meyering.
+
 2009-06-18  Eric Blake  <address@hidden>

        hash: make rotation more obvious
diff --git a/lib/hash.c b/lib/hash.c
index a81eec7..e2af5f3 100644
--- a/lib/hash.c
+++ b/lib/hash.c
@@ -462,7 +462,7 @@ next_prime (size_t candidate)
   /* Make it definitely odd.  */
   candidate |= 1;

-  while (!is_prime (candidate))
+  while (SIZE_MAX != candidate && !is_prime (candidate))
     candidate += 2;

   return candidate;
@@ -528,6 +528,26 @@ check_tuning (Hash_table *table)
   return false;
 }

+/* Compute the size of the bucket array for the given CANDIDATE and
+   TUNING, or return 0 if there is no possible way to allocate that
+   many entries.  */
+
+static size_t
+compute_bucket_size (size_t candidate, const Hash_tuning *tuning)
+{
+  if (!tuning->is_n_buckets)
+    {
+      float new_candidate = candidate / tuning->growth_threshold;
+      if (SIZE_MAX <= new_candidate)
+       return 0;
+      candidate = new_candidate;
+    }
+  candidate = next_prime (candidate);
+  if (xalloc_oversized (candidate, sizeof (struct hash_entry *)))
+    return 0;
+  return candidate;
+}
+
 /* Allocate and return a new hash table, or NULL upon failure.  The initial
    number of buckets is automatically selected so as to _guarantee_ that you
    may insert at least CANDIDATE different user entries before any growth of
@@ -591,18 +611,8 @@ hash_initialize (size_t candidate, const Hash_tuning 
*tuning,
       goto fail;
     }

-  if (!tuning->is_n_buckets)
-    {
-      float new_candidate = candidate / tuning->growth_threshold;
-      if (SIZE_MAX <= new_candidate)
-       goto fail;
-      candidate = new_candidate;
-    }
-
-  if (xalloc_oversized (candidate, sizeof *table->bucket))
-    goto fail;
-  table->n_buckets = next_prime (candidate);
-  if (xalloc_oversized (table->n_buckets, sizeof *table->bucket))
+  table->n_buckets = compute_bucket_size (candidate, tuning);
+  if (!table->n_buckets)
     goto fail;

   table->bucket = calloc (table->n_buckets, sizeof *table->bucket);
@@ -847,25 +857,33 @@ hash_find_entry (Hash_table *table, const void *entry,
 bool
 hash_rehash (Hash_table *table, size_t candidate)
 {
+  Hash_table storage;
   Hash_table *new_table;
   struct hash_entry *bucket;
   struct hash_entry *cursor;
   struct hash_entry *next;
+  size_t new_size;

-  new_table = hash_initialize (candidate, table->tuning, table->hasher,
-                              table->comparator, table->data_freer);
-  if (new_table == NULL)
+  new_size = compute_bucket_size (candidate, table->tuning);
+  if (!new_size)
     return false;
-  if (new_table->n_buckets == table->n_buckets)
-    {
-      free (new_table->bucket);
-      free (new_table);
-      return true;
-    }
+  if (new_size == table->n_buckets)
+    return true;
+  new_table = &storage;
+  new_table->bucket = calloc (new_size, sizeof *new_table->bucket);
+  if (new_table->bucket == NULL)
+    return false;
+  new_table->n_buckets = new_size;
+  new_table->bucket_limit = new_table->bucket + new_size;
+  new_table->n_buckets_used = 0;
+  new_table->n_entries = 0;
+  new_table->tuning = table->tuning;
+  new_table->hasher = table->hasher;
+  new_table->comparator = table->comparator;
+  new_table->data_freer = table->data_freer;

   /* Merely reuse the extra old space into the new table.  */
 #if USE_OBSTACK
-  obstack_free (&new_table->entry_stack, NULL);
   new_table->entry_stack = table->entry_stack;
 #endif
   new_table->free_entry_list = table->free_entry_list;
@@ -926,12 +944,7 @@ hash_rehash (Hash_table *table, size_t candidate)
   table->n_buckets = new_table->n_buckets;
   table->n_buckets_used = new_table->n_buckets_used;
   table->free_entry_list = new_table->free_entry_list;
-  /* table->n_entries already holds its value.  */
-#if USE_OBSTACK
-  table->entry_stack = new_table->entry_stack;
-#endif
-  free (new_table);
-
+  /* table->n_entries and table->entry_stack already hold their value.  */
   return true;
 }

-- 
1.6.3.rc3.2.g4b51


reply via email to

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