[libvirt] [PATCH 4/4] Replace hashing algorithm with murmurhash

[Eric Blake]

On 01/25/2012 09:38 AM, Daniel P. Berrange wrote:
> From: "Daniel P. Berrange" <berrange at redhat.com>
> 
> Recent discussions have illustrated the potential for DOS attacks
> with the hash table implementations used by most languages and
> libraries.
> 
>    https://lwn.net/Articles/474912/
> 
> libvirt has an internal hash table impl, and uses hash tables for
> a variety of purposes. The hash key generation code is pretty
> simple and thus not strongly collision resistant.
> 
> This patch replaces the current libvirt hash key generator with
> the (public domain) Murmurhash3 code. In addition every hash
> table now gets a random seed value which is used to perturb the
> hashing code. This should make it impossible to mount any
> practical attack against libvirt hashing code.
> 
> * bootstrap.conf: Import bitrotate module
> * src/Makefile.am: Add virhashcode.[ch]
> * src/util/util.c: Make virRandom() return a fixed 32 bit
>   integer value.

This part of the commit message is stale.

> * src/util/hash.c, src/util/hash.h, src/util/cgroup.c: Replace
>   hash code generation with a call to virHashCodeGen()
> * src/util/virhashcode.h, src/util/virhashcode.c: Add a new
>   virHashCodeGen() API using the Murmurhash3 algorithm.
> ---
>  bootstrap.conf         |    1 +
>  src/Makefile.am        |    1 +
>  src/util/cgroup.c      |    6 ++-
>  src/util/virhash.c     |   21 +++------
>  src/util/virhash.h     |    7 ++-
>  src/util/virhashcode.c |  121 ++++++++++++++++++++++++++++++++++++++++++++++++
>  src/util/virhashcode.h |   35 ++++++++++++++
>  7 files changed, 174 insertions(+), 18 deletions(-)
>  create mode 100644 src/util/virhashcode.c
>  create mode 100644 src/util/virhashcode.h
> 

> @@ -1636,9 +1637,10 @@ cleanup:
>  }
>  
>  
> -static uint32_t virCgroupPidCode(const void *name)
> +static uint32_t virCgroupPidCode(const void *name, uint32_t seed)
>  {
> -    return (uint32_t)(int64_t)name;
> +    unsigned long pid = (unsigned long)name;
> +    return virHashCodeGen(&pid, sizeof(pid), seed);

Hmm - now we're losing the double-cast, so you might be reintroducing
compiler warnings about casting a pointer to an incorrectly-sized
integer.  I think you still need to use:

unsigned long pid = (unsigned long)(intptr_t)name;

> + *
> + * The hash code generation is based on the public domain MurmurHash3 from Austin Appleby:
> + * http://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp
> + *
> + * We use only the 32 bit variant because the 2 produce different result while

s/result/results/

> +/* slower than original but is endian neutral and handles platforms that
> + * do only aligned reads */

s/is endian neutral and/

Your version is endian-dependent, but that's okay (you convinced me that
what matters is that a single libvirtd instance will always generate the
same hash for the same string, regardless of alignment; and that we
aren't transferring the hash over the wire to any other libvirtd
instance running on a different-endian machine).

> +__attribute__((always_inline))
> +static uint32_t getblock(const uint8_t *p, int i)
> +{
> +    uint32_t r;
> +    size_t size = sizeof(uint32_t);

I would have used sizeof(r) here (it's always nicer to use sizeof(var)
rather than sizeof(type), when a var is present, in case var changes
type later in a later patch).

> +
> +    memcpy(&r, &p[i * size], size);

Hopefully the compiler optimizes this decently.

> +
> +    switch (len & 3) {
> +    case 3:
> +        k1 ^= tail[2] << 16;
> +    case 2:
> +        k1 ^= tail[1] << 8;
> +    case 1:

I'd add some /* fallthrough */ comments to shut up Coverity.

Beyond that, it looked like a faithful conversion of the upstream code.

ACK with nits addressed.

-- 
Eric Blake   eblake at redhat.com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 620 bytes
Desc: OpenPGP digital signature
URL: <http://listman.redhat.com/archives/libvir-list/attachments/20120125/f7cc7ae9/attachment-0001.sig>