[libvirt] [PATCH] Replace hashing algorithm with murmurhash
Daniel P. Berrange
berrange at redhat.com
Wed Jan 18 16:23:29 UTC 2012
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.
* src/Makefile.am: Add virhashcode.[ch]
* src/util/util.c: Make virRandom() return a fixed 32 bit
integer value.
* 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.
---
src/Makefile.am | 1 +
src/util/cgroup.c | 6 ++-
src/util/hash.c | 24 ++++------
src/util/hash.h | 7 ++-
src/util/util.c | 4 +-
src/util/virhashcode.c | 125 ++++++++++++++++++++++++++++++++++++++++++++++++
src/util/virhashcode.h | 35 +++++++++++++
7 files changed, 181 insertions(+), 21 deletions(-)
create mode 100644 src/util/virhashcode.c
create mode 100644 src/util/virhashcode.h
diff --git a/src/Makefile.am b/src/Makefile.am
index 0a1221a..dd5acc4 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -89,6 +89,7 @@ UTIL_SOURCES = \
util/virpidfile.c util/virpidfile.h \
util/xml.c util/xml.h \
util/virterror.c util/virterror_internal.h \
+ util/virhashcode.c util/virhashcode.h \
util/virkeycode.c util/virkeycode.h \
util/virkeymaps.h \
util/virnetdev.h util/virnetdev.c \
diff --git a/src/util/cgroup.c b/src/util/cgroup.c
index 25f2691..7623264 100644
--- a/src/util/cgroup.c
+++ b/src/util/cgroup.c
@@ -33,6 +33,7 @@
#include "logging.h"
#include "virfile.h"
#include "hash.h"
+#include "virhashcode.h"
#define CGROUP_MAX_VAL 512
@@ -1636,9 +1637,10 @@ cleanup:
}
-static unsigned long virCgroupPidCode(const void *name)
+static int32_t virCgroupPidCode(const void *name, int32_t seed)
{
- return (unsigned long)name;
+ unsigned long pid = (unsigned long)name;
+ return virHashCodeGen(&pid, sizeof(pid), seed);
}
static bool virCgroupPidEqual(const void *namea, const void *nameb)
{
diff --git a/src/util/hash.c b/src/util/hash.c
index 665bcce..e765a6c 100644
--- a/src/util/hash.c
+++ b/src/util/hash.c
@@ -28,6 +28,8 @@
#include "hash.h"
#include "memory.h"
#include "logging.h"
+#include "virhashcode.h"
+#include "util.h"
#define VIR_FROM_THIS VIR_FROM_NONE
@@ -57,6 +59,7 @@ struct _virHashEntry {
*/
struct _virHashTable {
virHashEntryPtr *table;
+ uint32_t seed;
int size;
int nbElems;
/* True iff we are iterating over hash entries. */
@@ -70,20 +73,11 @@ struct _virHashTable {
virHashKeyFree keyFree;
};
-static unsigned long virHashStrCode(const void *name)
+
+
+static int32_t virHashStrCode(const void *name, int32_t seed)
{
- const char *str = name;
- unsigned long value = 0L;
- char ch;
-
- if (str != NULL) {
- value += 30 * (*str);
- while ((ch = *str++) != 0) {
- value =
- value ^ ((value << 5) + (value >> 3) + (unsigned long) ch);
- }
- }
- return value;
+ return virHashCodeGen(name, strlen(name), seed);
}
static bool virHashStrEqual(const void *namea, const void *nameb)
@@ -101,11 +95,10 @@ static void virHashStrFree(void *name)
VIR_FREE(name);
}
-
static unsigned long
virHashComputeKey(virHashTablePtr table, const void *name)
{
- unsigned long value = table->keyCode(name);
+ uint32_t value = table->keyCode(name, table->seed);
return (value % table->size);
}
@@ -139,6 +132,7 @@ virHashTablePtr virHashCreateFull(int size,
return NULL;
}
+ table->seed = virRandom(INT32_MAX);
table->size = size;
table->nbElems = 0;
table->dataFree = dataFree;
diff --git a/src/util/hash.h b/src/util/hash.h
index 1ba12b9..c415844 100644
--- a/src/util/hash.h
+++ b/src/util/hash.h
@@ -55,12 +55,15 @@ typedef int (*virHashSearcher) (const void *payload, const void *name,
/**
* virHashKeyCode:
* @name: the hash key
+ * @seed: random seed
*
- * Compute the hash code corresponding to the key @name
+ * Compute the hash code corresponding to the key @name, using
+ * @seed to perturb the hashing algorithm
*
* Returns the hash code
*/
-typedef unsigned long (*virHashKeyCode)(const void *name);
+typedef int32_t (*virHashKeyCode)(const void *name,
+ int32_t seed);
/**
* virHashKeyEqual:
* @namea: the first hash key
diff --git a/src/util/util.c b/src/util/util.c
index 8663c4d..c8588b5 100644
--- a/src/util/util.c
+++ b/src/util/util.c
@@ -2115,7 +2115,7 @@ int virRandomInitialize(unsigned int seed)
return 0;
}
-int virRandom(int max)
+int32_t virRandom(int32_t max)
{
int32_t ret;
@@ -2123,7 +2123,7 @@ int virRandom(int max)
random_r(&randomData, &ret);
virMutexUnlock(&randomLock);
- return (int) ((double)max * ((double)ret / (double)RAND_MAX));
+ return (int32_t) ((double)max * ((double)ret / (double)RAND_MAX));
}
diff --git a/src/util/virhashcode.c b/src/util/virhashcode.c
new file mode 100644
index 0000000..50b46f4
--- /dev/null
+++ b/src/util/virhashcode.c
@@ -0,0 +1,125 @@
+/*
+ * virhashcode.c: hash code generation
+ *
+ * Copyright (C) 2012 Red Hat, Inc.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * 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
+ * we need to produce the same result regardless of the architecture as
+ * clients can be both 64 or 32 bit at the same time.
+ */
+
+#include <config.h>
+
+#include "virhashcode.h"
+
+static uint32_t rotl(uint32_t x, int8_t r)
+{
+ return (x << r) | (x >> (32 - r));
+}
+
+/* slower than original but is endian neutral and handles platforms that
+ * do only aligned reads */
+__attribute__((always_inline))
+static uint32_t getblock(const uint8_t *p, int i)
+{
+ uint32_t r;
+ size_t size = sizeof(uint32_t);
+
+ memcpy(&r, &p[i * size], size);
+
+ return le32toh(r);
+}
+
+/*
+ * Finalization mix - force all bits of a hash block to avalanche
+ */
+__attribute__((always_inline))
+static uint32_t fmix(uint32_t h)
+{
+ h ^= h >> 16;
+ h *= 0x85ebca6b;
+ h ^= h >> 13;
+ h *= 0xc2b2ae35;
+ h ^= h >> 16;
+
+ return h;
+}
+
+
+uint32_t virHashCodeGen(const void *key, size_t len, uint32_t seed)
+{
+ const uint8_t *blocks;
+ const uint8_t *tail;
+ size_t nblocks;
+ uint32_t h1;
+ uint32_t k1;
+ uint32_t c1;
+ uint32_t c2;
+ size_t i;
+
+ blocks = (const uint8_t *)key;
+ nblocks = len / 4;
+ h1 = seed;
+ c1 = 0xcc9e2d51;
+ c2 = 0x1b873593;
+
+ /* body */
+
+ for (i = 0; i < nblocks; i++) {
+
+ k1 = getblock(blocks, i);
+
+ k1 *= c1;
+ k1 = rotl(k1, 15);
+ k1 *= c2;
+
+ h1 ^= k1;
+ h1 = rotl(h1, 13);
+ h1 = h1 * 5 + 0xe6546b64;
+ }
+
+ /* tail */
+
+ tail = (const uint8_t *)key + nblocks * 4;
+
+ k1 = 0;
+
+ switch (len & 3) {
+ case 3:
+ k1 ^= tail[2] << 16;
+ case 2:
+ k1 ^= tail[1] << 8;
+ case 1:
+ k1 ^= tail[0];
+ k1 *= c1;
+ k1 = rotl(k1, 15);
+ k1 *= c2;
+ h1 ^= k1;
+ default:
+ break;
+ }
+
+ /* finalization */
+
+ h1 ^= len;
+ h1 = fmix(h1);
+
+ return h1;
+}
diff --git a/src/util/virhashcode.h b/src/util/virhashcode.h
new file mode 100644
index 0000000..867e04e
--- /dev/null
+++ b/src/util/virhashcode.h
@@ -0,0 +1,35 @@
+/*
+ * virhashcode.h: hash code generation
+ *
+ * Copyright (C) 2012 Red Hat, Inc.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * 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
+ * we need to produce the same result regardless of the architecture as
+ * clients can be both 64 or 32 bit at the same time.
+ */
+
+#ifndef __VIR_HASH_CODE_H__
+# define __VIR_HASH_CODE_H__
+
+# include "internal.h"
+
+extern uint32_t virHashCodeGen(const void *key, size_t len, uint32_t seed);
+
+#endif /* __VIR_HASH_CODE_H__ */
--
1.7.7.5
More information about the libvir-list
mailing list