Re: [PATCH] hash: silence spurious clang warning

[Eric Blake]

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).

> Given this analysis, I would rewrite the code as below. This should
> not only placate clang's warning, but also make the code faster
> rather than slower.

Awesome - any time we can rewrite something that shuts up a warning 
without adding extra lint, it wins my support.  By the way, we'd still 
need this rewrite, even if Jim likes my idea of adding safe_hasher.

--
Eric Blake   address@hidden    +1-801-349-2682
Libvirt virtualization library http://libvirt.org