Re: hash resizing bug

[Jim Meyering]

Eric Blake wrote:

> According to Eric Blake on 6/17/2009 12:21 PM:
>> Before the rehash, about 20% of the buckets were empty.  But after changing 
>> the
>> prime factor, the hasher function scatters better, and _every single bucket_ 
>> is
>> occupied.  Which means ALL subsequent calls to hash_insert will trigger an
>> overflow, rather than inserting into a bucket head.  And since the resize
>> checking logic in hash_rehash is only triggered after insertion into a bucket
>> head, the hash table has effectively been locked into a fixed size that will
>> never grow again, no matter how many hash_insert calls are made, even though
>> the table is certainly exceeding the requested threshold of 20% empty 
>> buckets.
>> Ouch.
>
> I'm now playing with this simple code motion patch, also available at:
> http://repo.or.cz/w/gnulib/ericb.git
> $ git pull git://repo.or.cz/gnulib/ericb.git master

...
>>From d3edc0d1e302af613e8b56396f1f9d0bec15a264 Mon Sep 17 00:00:00 2001
> From: Eric Blake <address@hidden>
> Date: Wed, 17 Jun 2009 13:01:41 -0600
> Subject: [PATCH] hash: check for resize before insertion
>
> * lib/hash.c (hash_insert): Check whether bucket usage exceeds
> threshold before insertion, so that a pathological hash_rehash
> that fills every bucket can still trigger another rehash.

The patch attached to that message did not apply to gnulib, since
it had bits like this:

  -+      if (table->overflow_size <= new_entry - table->overflow)
  -+      abort ();
  ...
  --      bucket->next = new_entry - table->overflow;
  +-      bucket->next = new_entry;

Did you verify that stock gnulib/hash.c
can get stuck like you described?