[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [PATCH] hash: silence spurious clang warning
From: |
Jim Meyering |
Subject: |
Re: [PATCH] hash: silence spurious clang warning |
Date: |
Tue, 31 Aug 2010 10:10:32 +0200 |
Eric Blake wrote:
> On 08/30/2010 05:09 PM, Bruno Haible wrote:
>> Hi Eric,
>>
>>> - if (! (bucket< table->bucket_limit))
>>> + if (! (bucket&& bucket< table->bucket_limit))
>>> abort ();
>>
>> I would not apply this, because it causes a slowdown at runtime
>> for no good reason.
>
> Hmm - I see the point of the original abort(), but think it isn't
> checking quite enough. A malicious table->hasher could return a value
> so large as to cause arithmetic wraparound, such that bucket really is
> NULL in that case. Since we're already willing to abort() if
> table->hasher returns an out-of-bounds hash index, maybe the real fix
> is to add:
>
> static struct hash_entry const *
> safe_hasher (const Hash_table *table, const void *key)
> {
> size_t n = table->hasher (key, table->n_buckets);
> if (table->n_buckets <= n)
> abort ();
> return table->bucket + n;
> }
>
> then change all callers like:
>
> struct hash_entry const *bucket
> = table->bucket + table->hasher (entry, table->n_buckets);
> if (! bucket < table->bucket_limit))
> abort ();
>
> to instead be the simpler:
>
> struct hash_entry const *bucket = safe_hasher (table, entry);
>
> (that is, factor the out-of-bounds abort() detection into a central
> location, rather than in every client, at the same time as making it
> robust to modulo arithmetic wraparounds).
Good idea.
The only thing I've changed is the test in safe_hasher.
In that context, I find this more readable:
size_t n = ...
if (! (n < table->n_buckets))
abort ();
than this:
if (table->n_buckets <= n)
abort ();
Eric, I've listed you as an author, so will wait for your ACK.
>From 5bcff7b85b7b88fa4809ad874a1203e27abed085 Mon Sep 17 00:00:00 2001
From: Eric Blake <address@hidden>
Date: Tue, 31 Aug 2010 10:06:16 +0200
Subject: [PATCH] hash: factor, and guard against misbehaving hasher function
* lib/hash.c (safe_hasher): New function, to encapsulate the checking
of table->hasher's return value. Also protect against a hash value
so large that adding it to table->bucket would result in a NULL pointer.
(hash_lookup, hash_get_next, hash_find_entry): Use it in place of
open-coded check-and-abort.
---
ChangeLog | 10 ++++++++++
lib/hash.c | 29 ++++++++++++++---------------
2 files changed, 24 insertions(+), 15 deletions(-)
diff --git a/ChangeLog b/ChangeLog
index a61bf9f..ef3adf1 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,13 @@
+2010-08-31 Eric Blake <address@hidden>
+ Jim Meyering <address@hidden>
+
+ hash: factor, and guard against misbehaving hasher function
+ * lib/hash.c (safe_hasher): New function, to encapsulate the checking
+ of table->hasher's return value. Also protect against a hash value
+ so large that adding it to table->bucket would result in a NULL pointer.
+ (hash_lookup, hash_get_next, hash_find_entry): Use it in place of
+ open-coded check-and-abort.
+
2010-08-30 Bruno Haible <address@hidden>
hash: silence spurious clang warning
diff --git a/lib/hash.c b/lib/hash.c
index 2258652..30a10b1 100644
--- a/lib/hash.c
+++ b/lib/hash.c
@@ -243,19 +243,26 @@ hash_print_statistics (const Hash_table *table, FILE
*stream)
(unsigned long int) max_bucket_length);
}
+/* Hash KEY and return a pointer to the selected bucket.
+ If TABLE->hasher misbehaves, abort. */
+static struct hash_entry const *
+safe_hasher (const Hash_table *table, const void *key)
+{
+ size_t n = table->hasher (key, table->n_buckets);
+ if (! (n < table->n_buckets))
+ abort ();
+ return table->bucket + n;
+}
+
/* If ENTRY matches an entry already in the hash table, return the
entry from the table. Otherwise, return NULL. */
void *
hash_lookup (const Hash_table *table, const void *entry)
{
- struct hash_entry const *bucket
- = table->bucket + table->hasher (entry, table->n_buckets);
+ struct hash_entry const *bucket = safe_hasher (table, entry);
struct hash_entry const *cursor;
- if (! (bucket < table->bucket_limit))
- abort ();
-
if (bucket->data == NULL)
return NULL;
@@ -299,13 +306,9 @@ hash_get_first (const Hash_table *table)
void *
hash_get_next (const Hash_table *table, const void *entry)
{
- struct hash_entry const *bucket
- = table->bucket + table->hasher (entry, table->n_buckets);
+ struct hash_entry const *bucket = safe_hasher (table, entry);
struct hash_entry const *cursor;
- if (! (bucket < table->bucket_limit))
- abort ();
-
/* Find next entry in the same bucket. */
cursor = bucket;
do
@@ -787,13 +790,9 @@ static void *
hash_find_entry (Hash_table *table, const void *entry,
struct hash_entry **bucket_head, bool delete)
{
- struct hash_entry *bucket
- = table->bucket + table->hasher (entry, table->n_buckets);
+ struct hash_entry *bucket = safe_hasher (table, entry);
struct hash_entry *cursor;
- if (! (bucket < table->bucket_limit))
- abort ();
-
*bucket_head = bucket;
/* Test for empty bucket. */
--
1.7.2.2.510.g7180a
Re: [PATCH] hash: silence spurious clang warning, Jim Meyering, 2010/08/31