-----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 e...@byu.net
-----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 <e...@byu.net>
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 <e...@byu.net>
---
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 <e...@byu.net>
+
+ 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 <e...@byu.net>
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
