Re: [libvirt] [PATCH 4/4] Replace hashing algorithm with murmurhash
On 01/25/2012 09:38 AM, Daniel P. Berrange wrote:
From: "Daniel P. Berrange" <berrange(a)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(a)redhat.com +1-919-301-3266
Libvirt virtualization library http://libvirt.org
Attachments:
- signature.asc (application/pgp-signature — 620 bytes)