bug-gnulib
[Top][All Lists]
Advanced

[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



reply via email to

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