[libvirt] [PATCH v2 0/4] Update the hash table algorithm
This is a followup to https://www.redhat.com/archives/libvir-list/2012-January/msg00734.html Changes in v2: - Replace virRandom with virRandomBits as per Eric's suggested impl - Move virRandom* functions to virrandom.{c,h} - Move virHash impl to virhash.{c,h} - Remove use of le32toh() function - Convert several virHash functions to use size_t / uint32 instead of int/unsigned long - Split into 4 patches for easier review/bisect
From: "Daniel P. Berrange" <berrange@redhat.com> The old virRandom() API was not generating good random numbers. Replace it with a new API virRandomBits which instead of being told the upper limit, gets told the number of bits of randomness required. * src/util/virrandom.c, src/util/virrandom.h: Add virRandomBits, and move virRandomInitialize * src/util/util.h, src/util/util.c: Delete virRandom and virRandomInitialize * src/libvirt.c, src/security/security_selinux.c, src/test/test_driver.c, src/util/iohelper.c: Update for changes from virRandom to virRandomBits * src/storage/storage_backend_iscsi.c: Remove bogus call to virRandomInitialize & convert to virRandomBits --- src/Makefile.am | 1 + src/libvirt.c | 2 +- src/libvirt_private.syms | 7 ++- src/security/security_selinux.c | 5 +- src/storage/storage_backend_iscsi.c | 12 +---- src/test/test_driver.c | 3 +- src/util/iohelper.c | 1 + src/util/util.c | 37 ++---------------- src/util/util.h | 3 - src/util/uuid.c | 3 +- src/util/virrandom.c | 73 +++++++++++++++++++++++++++++++++++ src/util/virrandom.h | 30 ++++++++++++++ 12 files changed, 125 insertions(+), 52 deletions(-) create mode 100644 src/util/virrandom.c create mode 100644 src/util/virrandom.h diff --git a/src/Makefile.am b/src/Makefile.am index a44446f..4629700 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -99,6 +99,7 @@ UTIL_SOURCES = \ util/virnetdevtap.h util/virnetdevtap.c \ util/virnetdevveth.h util/virnetdevveth.c \ util/virnetdevvportprofile.h util/virnetdevvportprofile.c \ + util/virrandom.h util/virrandom.c \ util/virsocketaddr.h util/virsocketaddr.c \ util/virtime.h util/virtime.c diff --git a/src/libvirt.c b/src/libvirt.c index 722a2e2..68eec2e 100644 --- a/src/libvirt.c +++ b/src/libvirt.c @@ -36,7 +36,6 @@ #include "driver.h" #include "uuid.h" -#include "util.h" #include "memory.h" #include "configmake.h" #include "intprops.h" @@ -44,6 +43,7 @@ #include "rpc/virnettlscontext.h" #include "command.h" #include "virnodesuspend.h" +#include "virrandom.h" #ifndef WITH_DRIVER_MODULES # ifdef WITH_TEST diff --git a/src/libvirt_private.syms b/src/libvirt_private.syms index 924ec16..915a43f 100644 --- a/src/libvirt_private.syms +++ b/src/libvirt_private.syms @@ -1126,8 +1126,6 @@ virParseMacAddr; virParseNumber; virParseVersionString; virPipeReadUntilEOF; -virRandom; -virRandomInitialize; virSetBlocking; virSetCloseExec; virSetInherit; @@ -1369,6 +1367,11 @@ virPidFileDelete; virPidFileDeletePath; +# virrandom.h +virRandomBits; +virRandomInitialize; + + # virsocketaddr.h virSocketAddrBroadcast; virSocketAddrBroadcastByPrefix; diff --git a/src/security/security_selinux.c b/src/security/security_selinux.c index c2dceca..cb41a17 100644 --- a/src/security/security_selinux.c +++ b/src/security/security_selinux.c @@ -32,6 +32,7 @@ #include "hostusb.h" #include "storage_file.h" #include "virfile.h" +#include "virrandom.h" #define VIR_FROM_THIS VIR_FROM_SECURITY @@ -216,8 +217,8 @@ SELinuxGenSecurityLabel(virSecurityManagerPtr mgr ATTRIBUTE_UNUSED, } } else { do { - c1 = virRandom(1024); - c2 = virRandom(1024); + c1 = virRandomBits(10); + c2 = virRandomBits(10); if ( c1 == c2 ) { if (virAsprintf(&mcs, "s0:c%d", c1) < 0) { diff --git a/src/storage/storage_backend_iscsi.c b/src/storage/storage_backend_iscsi.c index 354f99b..6ebc6e1 100644 --- a/src/storage/storage_backend_iscsi.c +++ b/src/storage/storage_backend_iscsi.c @@ -42,6 +42,7 @@ #include "logging.h" #include "virfile.h" #include "command.h" +#include "virrandom.h" #define VIR_FROM_THIS VIR_FROM_STORAGE @@ -283,15 +284,8 @@ virStorageBackendCreateIfaceIQN(const char *initiatoriqn, initiatoriqn, NULL }; - if (virRandomInitialize(time(NULL) ^ getpid()) == -1) { - virStorageReportError(VIR_ERR_INTERNAL_ERROR, "%s", - _("Failed to initialize random generator " - "when creating iscsi interface")); - goto out; - } - - snprintf(temp_ifacename, sizeof(temp_ifacename), "libvirt-iface-%08x", - virRandom(1024 * 1024 * 1024)); + snprintf(temp_ifacename, sizeof(temp_ifacename), "libvirt-iface-%08llx", + (unsigned long long)virRandomBits(30)); VIR_DEBUG("Attempting to create interface '%s' with IQN '%s'", &temp_ifacename[0], initiatoriqn); diff --git a/src/test/test_driver.c b/src/test/test_driver.c index 55b889b..bf6b148 100644 --- a/src/test/test_driver.c +++ b/src/test/test_driver.c @@ -51,6 +51,7 @@ #include "logging.h" #include "virfile.h" #include "virtypedparam.h" +#include "virrandom.h" #define VIR_FROM_THIS VIR_FROM_TEST @@ -5316,7 +5317,7 @@ testNodeDeviceCreateXML(virConnectPtr conn, if (caps->type != VIR_NODE_DEV_CAP_SCSI_HOST) continue; - caps->data.scsi_host.host = virRandom(1024); + caps->data.scsi_host.host = virRandomBits(10); caps = caps->next; } diff --git a/src/util/iohelper.c b/src/util/iohelper.c index 93154f8..0794193 100644 --- a/src/util/iohelper.c +++ b/src/util/iohelper.c @@ -39,6 +39,7 @@ #include "memory.h" #include "virterror_internal.h" #include "configmake.h" +#include "virrandom.h" #define VIR_FROM_THIS VIR_FROM_STORAGE diff --git a/src/util/util.c b/src/util/util.c index c00c2f9..ada423b 100644 --- a/src/util/util.c +++ b/src/util/util.c @@ -77,6 +77,7 @@ #include "command.h" #include "nonblocking.h" #include "passfd.h" +#include "virrandom.h" #ifndef NSIG # define NSIG 32 @@ -1853,9 +1854,9 @@ void virGenerateMacAddr(const unsigned char *prefix, addr[0] = prefix[0]; addr[1] = prefix[1]; addr[2] = prefix[2]; - addr[3] = virRandom(256); - addr[4] = virRandom(256); - addr[5] = virRandom(256); + addr[3] = virRandomBits(8); + addr[4] = virRandomBits(8); + addr[5] = virRandomBits(8); } @@ -2097,36 +2098,6 @@ int virKillProcess(pid_t pid, int sig) } -static char randomState[128]; -static struct random_data randomData; -static virMutex randomLock; - -int virRandomInitialize(unsigned int seed) -{ - if (virMutexInit(&randomLock) < 0) - return -1; - - if (initstate_r(seed, - randomState, - sizeof(randomState), - &randomData) < 0) - return -1; - - return 0; -} - -int virRandom(int max) -{ - int32_t ret; - - virMutexLock(&randomLock); - random_r(&randomData, &ret); - virMutexUnlock(&randomLock); - - return (int) ((double)max * ((double)ret / (double)RAND_MAX)); -} - - #ifdef HAVE_GETPWUID_R enum { VIR_USER_ENT_DIRECTORY, diff --git a/src/util/util.h b/src/util/util.h index 94d9282..91cae47 100644 --- a/src/util/util.h +++ b/src/util/util.h @@ -242,9 +242,6 @@ int virGetUserID(const char *name, int virGetGroupID(const char *name, gid_t *gid) ATTRIBUTE_RETURN_CHECK; -int virRandomInitialize(unsigned int seed) ATTRIBUTE_RETURN_CHECK; -int virRandom(int max); - char *virFileFindMountPoint(const char *type); void virFileWaitForDevices(void); diff --git a/src/util/uuid.c b/src/util/uuid.c index 15ba5af..23822ec 100644 --- a/src/util/uuid.c +++ b/src/util/uuid.c @@ -40,6 +40,7 @@ #include "logging.h" #include "memory.h" #include "virfile.h" +#include "virrandom.h" #ifndef ENODATA # define ENODATA EIO @@ -80,7 +81,7 @@ virUUIDGeneratePseudoRandomBytes(unsigned char *buf, int buflen) { while (buflen > 0) { - *buf++ = virRandom(256); + *buf++ = virRandomBits(8); buflen--; } diff --git a/src/util/virrandom.c b/src/util/virrandom.c new file mode 100644 index 0000000..b35b1f4 --- /dev/null +++ b/src/util/virrandom.c @@ -0,0 +1,73 @@ +/* + * 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 + * + * Authors: + * Daniel P. Berrange <berrange@redhat.com> + */ + +#include <config.h> + +#include <stdlib.h> + +#include "virrandom.h" +#include "threads.h" +#include "count-one-bits.h" + +static char randomState[128]; +static struct random_data randomData; +static virMutex randomLock; + + +int virRandomInitialize(uint32_t seed) +{ + if (virMutexInit(&randomLock) < 0) + return -1; + + if (initstate_r(seed, + randomState, + sizeof(randomState), + &randomData) < 0) + return -1; + + return 0; +} + + +uint64_t virRandomBits(int nbits) +{ + int bits_per_iter = count_one_bits(RAND_MAX); + uint64_t ret = 0; + int32_t bits; + + /* This algorithm requires that RAND_MAX == 2^n-1 for some n; + gnulib's random_r meets this property. */ + verify(((RAND_MAX + 1U) & RAND_MAX) == 0); + + virMutexLock(&randomLock); + + while (nbits > bits_per_iter) { + random_r(&randomData, &bits); + ret = (ret << bits_per_iter) | (bits & RAND_MAX); + nbits -= bits_per_iter; + } + + random_r(&randomData, &bits); + ret = (ret << nbits) | (bits & ((1 << nbits) - 1)); + + virMutexUnlock(&randomLock); + return ret; +} diff --git a/src/util/virrandom.h b/src/util/virrandom.h new file mode 100644 index 0000000..eede373 --- /dev/null +++ b/src/util/virrandom.h @@ -0,0 +1,30 @@ +/* + * 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 + * + * Authors: + * Daniel P. Berrange <berrange@redhat.com> + */ + +#ifndef __VIR_RANDOM_H__ +# define __VIR_RANDOM_H__ + +# include "internal.h" + +int virRandomInitialize(uint32_t seed) ATTRIBUTE_RETURN_CHECK; +uint64_t virRandomBits(int nbits); + +#endif /* __VIR_RANDOM_H__ */ -- 1.7.7.5
On 01/25/2012 09:38 AM, Daniel P. Berrange wrote:
From: "Daniel P. Berrange" <berrange@redhat.com>
The old virRandom() API was not generating good random numbers. Replace it with a new API virRandomBits which instead of being told the upper limit, gets told the number of bits of randomness required.
* src/util/virrandom.c, src/util/virrandom.h: Add virRandomBits, and move virRandomInitialize * src/util/util.h, src/util/util.c: Delete virRandom and virRandomInitialize * src/libvirt.c, src/security/security_selinux.c, src/test/test_driver.c, src/util/iohelper.c: Update for changes from virRandom to virRandomBits * src/storage/storage_backend_iscsi.c: Remove bogus call to virRandomInitialize & convert to virRandomBits ---
+++ b/src/storage/storage_backend_iscsi.c
- - snprintf(temp_ifacename, sizeof(temp_ifacename), "libvirt-iface-%08x", - virRandom(1024 * 1024 * 1024)); + snprintf(temp_ifacename, sizeof(temp_ifacename), "libvirt-iface-%08llx", + (unsigned long long)virRandomBits(30));
Hmm - the cast is indeed necessary if we don't want to rely on PRIx64, thanks to the change in return type as we switch to the new function; knowing we only have 30 bits, we could get away with a smaller cast, as in: "%08x", (unsigned)virRandomBits(30) but this is not enough of an issue to be worth changing.
+ + +uint64_t virRandomBits(int nbits) +{
You lost my documentation comments from my proposal: /* Return an evenly distributed random number between [0,2^nbits), where nbits must be in the range (0,64]. */ Also, the tests failed to compile. Squash this in, and then you have my ACK: diff --git i/tests/testutils.c w/tests/testutils.c index acdfdc1..fccea17 100644 --- i/tests/testutils.c +++ w/tests/testutils.c @@ -1,7 +1,7 @@ /* * testutils.c: basic test utils * - * Copyright (C) 2005-2011 Red Hat, Inc. + * Copyright (C) 2005-2012 Red Hat, Inc. * * See COPYING.LIB for the License of this software * @@ -34,6 +34,7 @@ #include "buf.h" #include "logging.h" #include "command.h" +#include "virrandom.h" #if TEST_OOM_TRACE # include <execinfo.h> -- Eric Blake eblake@redhat.com +1-919-301-3266 Libvirt virtualization library http://libvirt.org
From: "Daniel P. Berrange" <berrange@redhat.com> In preparation for conversion over to use the Murmurhash3 algorithm, convert various virHash APIs to use size_t or uint32 for their return values/parameters, instead of the variable size 'unsigned long' or 'int' types --- src/util/cgroup.c | 4 +- src/util/hash.c | 56 +++++++++++++++++++++++++++------------------------- src/util/hash.h | 14 ++++++------ 3 files changed, 38 insertions(+), 36 deletions(-) diff --git a/src/util/cgroup.c b/src/util/cgroup.c index 25f2691..a270965 100644 --- a/src/util/cgroup.c +++ b/src/util/cgroup.c @@ -1636,9 +1636,9 @@ cleanup: } -static unsigned long virCgroupPidCode(const void *name) +static uint32_t virCgroupPidCode(const void *name) { - return (unsigned long)name; + return (uint32_t)(int64_t)name; } static bool virCgroupPidEqual(const void *namea, const void *nameb) { diff --git a/src/util/hash.c b/src/util/hash.c index ff86f16..20d3a12 100644 --- a/src/util/hash.c +++ b/src/util/hash.c @@ -57,8 +57,8 @@ struct _virHashEntry { */ struct _virHashTable { virHashEntryPtr *table; - int size; - int nbElems; + size_t size; + size_t nbElems; /* True iff we are iterating over hash entries. */ bool iterating; /* Pointer to the current entry during iteration. */ @@ -70,17 +70,17 @@ struct _virHashTable { virHashKeyFree keyFree; }; -static unsigned long virHashStrCode(const void *name) +static uint32_t virHashStrCode(const void *name) { const char *str = name; - unsigned long value = 0L; + uint32_t value = 0L; char ch; if (str != NULL) { value += 30 * (*str); while ((ch = *str++) != 0) { value = - value ^ ((value << 5) + (value >> 3) + (unsigned long) ch); + value ^ ((value << 5) + (value >> 3) + (uint32_t) ch); } } return value; @@ -102,10 +102,10 @@ static void virHashStrFree(void *name) } -static unsigned long +static size_t virHashComputeKey(virHashTablePtr table, const void *name) { - unsigned long value = table->keyCode(name); + uint32_t value = table->keyCode(name); return (value % table->size); } @@ -122,7 +122,7 @@ virHashComputeKey(virHashTablePtr table, const void *name) * * Returns the newly created object, or NULL if an error occurred. */ -virHashTablePtr virHashCreateFull(int size, +virHashTablePtr virHashCreateFull(ssize_t size, virHashDataFree dataFree, virHashKeyCode keyCode, virHashKeyEqual keyEqual, @@ -166,7 +166,7 @@ virHashTablePtr virHashCreateFull(int size, * * Returns the newly created object, or NULL if an error occurred. */ -virHashTablePtr virHashCreate(int size, virHashDataFree dataFree) +virHashTablePtr virHashCreate(ssize_t size, virHashDataFree dataFree) { return virHashCreateFull(size, dataFree, @@ -186,13 +186,13 @@ virHashTablePtr virHashCreate(int size, virHashDataFree dataFree) * Returns 0 in case of success, -1 in case of failure */ static int -virHashGrow(virHashTablePtr table, int size) +virHashGrow(virHashTablePtr table, size_t size) { - int oldsize, i; + size_t oldsize, i; virHashEntryPtr *oldtable; #ifdef DEBUG_GROW - unsigned long nbElem = 0; + size_t nbElem = 0; #endif if (table == NULL) @@ -218,7 +218,7 @@ virHashGrow(virHashTablePtr table, int size) virHashEntryPtr iter = oldtable[i]; while (iter) { virHashEntryPtr next = iter->next; - unsigned long key = virHashComputeKey(table, iter->name); + size_t key = virHashComputeKey(table, iter->name); iter->next = table->table[key]; table->table[key] = iter; @@ -250,7 +250,7 @@ virHashGrow(virHashTablePtr table, int size) void virHashFree(virHashTablePtr table) { - int i; + size_t i; if (table == NULL) return; @@ -278,7 +278,7 @@ virHashAddOrUpdateEntry(virHashTablePtr table, const void *name, void *userdata, bool is_update) { - unsigned long key, len = 0; + size_t key, len = 0; virHashEntryPtr entry; char *new_name; @@ -372,7 +372,7 @@ virHashUpdateEntry(virHashTablePtr table, const void *name, void * virHashLookup(virHashTablePtr table, const void *name) { - unsigned long key; + size_t key; virHashEntryPtr entry; if (!table || !name) @@ -419,7 +419,7 @@ void *virHashSteal(virHashTablePtr table, const void *name) * Returns the number of elements in the hash table or * -1 in case of error */ -int +ssize_t virHashSize(virHashTablePtr table) { if (table == NULL) @@ -436,7 +436,7 @@ virHashSize(virHashTablePtr table) * Returns the number of keys in the hash table or * -1 in case of error */ -int +ssize_t virHashTableSize(virHashTablePtr table) { if (table == NULL) @@ -499,9 +499,10 @@ virHashRemoveEntry(virHashTablePtr table, const void *name) * * Returns number of items iterated over upon completion, -1 on failure */ -int virHashForEach(virHashTablePtr table, virHashIterator iter, void *data) +ssize_t +virHashForEach(virHashTablePtr table, virHashIterator iter, void *data) { - int i, count = 0; + size_t i, count = 0; if (table == NULL || iter == NULL) return (-1); @@ -542,11 +543,12 @@ int virHashForEach(virHashTablePtr table, virHashIterator iter, void *data) * * Returns number of items removed on success, -1 on failure */ -int virHashRemoveSet(virHashTablePtr table, - virHashSearcher iter, - const void *data) +ssize_t +virHashRemoveSet(virHashTablePtr table, + virHashSearcher iter, + const void *data) { - int i, count = 0; + size_t i, count = 0; if (table == NULL || iter == NULL) return (-1); @@ -595,7 +597,7 @@ void *virHashSearch(virHashTablePtr table, virHashSearcher iter, const void *data) { - int i; + size_t i; if (table == NULL || iter == NULL) return (NULL); @@ -622,7 +624,7 @@ void *virHashSearch(virHashTablePtr table, struct getKeysIter { virHashKeyValuePair *sortArray; - unsigned arrayIdx; + size_t arrayIdx; }; static void virHashGetKeysIterator(void *payload, @@ -641,7 +643,7 @@ typedef int (*qsort_comp)(const void *, const void *); virHashKeyValuePairPtr virHashGetItems(virHashTablePtr table, virHashKeyComparator compar) { - int numElems = virHashSize(table); + ssize_t numElems = virHashSize(table); struct getKeysIter iter = { .arrayIdx = 0, .sortArray = NULL, diff --git a/src/util/hash.h b/src/util/hash.h index 9da2da5..2420045 100644 --- a/src/util/hash.h +++ b/src/util/hash.h @@ -60,7 +60,7 @@ typedef int (*virHashSearcher) (const void *payload, const void *name, * * Returns the hash code */ -typedef unsigned long (*virHashKeyCode)(const void *name); +typedef uint32_t (*virHashKeyCode)(const void *name); /** * virHashKeyEqual: * @namea: the first hash key @@ -93,17 +93,17 @@ typedef void (*virHashKeyFree)(void *name); /* * Constructor and destructor. */ -virHashTablePtr virHashCreate(int size, +virHashTablePtr virHashCreate(ssize_t size, virHashDataFree dataFree); -virHashTablePtr virHashCreateFull(int size, +virHashTablePtr virHashCreateFull(ssize_t size, virHashDataFree dataFree, virHashKeyCode keyCode, virHashKeyEqual keyEqual, virHashKeyCopy keyCopy, virHashKeyFree keyFree); void virHashFree(virHashTablePtr table); -int virHashSize(virHashTablePtr table); -int virHashTableSize(virHashTablePtr table); +ssize_t virHashSize(virHashTablePtr table); +ssize_t virHashTableSize(virHashTablePtr table); /* * Add a new entry to the hash table. @@ -168,8 +168,8 @@ bool virHashEqual(const virHashTablePtr table1, /* * Iterators */ -int virHashForEach(virHashTablePtr table, virHashIterator iter, void *data); -int virHashRemoveSet(virHashTablePtr table, virHashSearcher iter, const void *data); +ssize_t virHashForEach(virHashTablePtr table, virHashIterator iter, void *data); +ssize_t virHashRemoveSet(virHashTablePtr table, virHashSearcher iter, const void *data); void *virHashSearch(virHashTablePtr table, virHashSearcher iter, const void *data); #endif /* ! __VIR_HASH_H__ */ -- 1.7.7.5
On 01/25/2012 09:38 AM, Daniel P. Berrange wrote:
From: "Daniel P. Berrange" <berrange@redhat.com>
In preparation for conversion over to use the Murmurhash3 algorithm, convert various virHash APIs to use size_t or uint32 for their return values/parameters, instead of the variable size 'unsigned long' or 'int' types --- src/util/cgroup.c | 4 +- src/util/hash.c | 56 +++++++++++++++++++++++++++------------------------- src/util/hash.h | 14 ++++++------ 3 files changed, 38 insertions(+), 36 deletions(-)
diff --git a/src/util/cgroup.c b/src/util/cgroup.c index 25f2691..a270965 100644 --- a/src/util/cgroup.c +++ b/src/util/cgroup.c @@ -1636,9 +1636,9 @@ cleanup: }
-static unsigned long virCgroupPidCode(const void *name) +static uint32_t virCgroupPidCode(const void *name) { - return (unsigned long)name; + return (uint32_t)(int64_t)name;
I know why you did the double cast - to shut up the compiler warnings about converting a pointer to a different size int. But you still get that warning on 32-bit machines, unless you use: s/int64_t/intptr_t/ Meanwhile, your argument about this hash code only being used on Linux with cgroups, and where pid is not a pid_t but a parsed long int from procfs, convinced me - the naming is a bit unfortunate, but there is no bug that will impact mingw64 pid_t cleanups. Again, you forgot 'make check'. ACK if you fix the above cast, and squash this in: diff --git i/tests/hashtest.c w/tests/hashtest.c index 441672c..e4b2bc1 100644 --- i/tests/hashtest.c +++ w/tests/hashtest.c @@ -40,7 +40,7 @@ testHashInit(int size) } if (virHashTableSize(hash) != oldsize && virTestGetDebug()) { - fprintf(stderr, "\nhash grown from %d to %d", + fprintf(stderr, "\nhash grown from %d to %zd", oldsize, virHashTableSize(hash)); } } @@ -75,7 +75,7 @@ testHashCheckCount(virHashTablePtr hash, int count) int iter_count = 0; if (virHashSize(hash) != count) { - testError("\nhash contains %d instead of %d elements\n", + testError("\nhash contains %zd instead of %d elements\n", virHashSize(hash), count); return -1; } -- Eric Blake eblake@redhat.com +1-919-301-3266 Libvirt virtualization library http://libvirt.org
On Wed, Jan 25, 2012 at 11:34:14AM -0700, Eric Blake wrote:
On 01/25/2012 09:38 AM, Daniel P. Berrange wrote:
From: "Daniel P. Berrange" <berrange@redhat.com>
In preparation for conversion over to use the Murmurhash3 algorithm, convert various virHash APIs to use size_t or uint32 for their return values/parameters, instead of the variable size 'unsigned long' or 'int' types --- src/util/cgroup.c | 4 +- src/util/hash.c | 56 +++++++++++++++++++++++++++------------------------- src/util/hash.h | 14 ++++++------ 3 files changed, 38 insertions(+), 36 deletions(-)
diff --git a/src/util/cgroup.c b/src/util/cgroup.c index 25f2691..a270965 100644 --- a/src/util/cgroup.c +++ b/src/util/cgroup.c @@ -1636,9 +1636,9 @@ cleanup: }
-static unsigned long virCgroupPidCode(const void *name) +static uint32_t virCgroupPidCode(const void *name) { - return (unsigned long)name; + return (uint32_t)(int64_t)name;
I know why you did the double cast - to shut up the compiler warnings about converting a pointer to a different size int. But you still get that warning on 32-bit machines, unless you use:
s/int64_t/intptr_t/
Hmm, yes good point - will change that.
Meanwhile, your argument about this hash code only being used on Linux with cgroups, and where pid is not a pid_t but a parsed long int from procfs, convinced me - the naming is a bit unfortunate, but there is no bug that will impact mingw64 pid_t cleanups.
Again, you forgot 'make check'. ACK if you fix the above cast, and squash this in:
diff --git i/tests/hashtest.c w/tests/hashtest.c index 441672c..e4b2bc1 100644 --- i/tests/hashtest.c +++ w/tests/hashtest.c @@ -40,7 +40,7 @@ testHashInit(int size) }
if (virHashTableSize(hash) != oldsize && virTestGetDebug()) { - fprintf(stderr, "\nhash grown from %d to %d", + fprintf(stderr, "\nhash grown from %d to %zd", oldsize, virHashTableSize(hash)); } } @@ -75,7 +75,7 @@ testHashCheckCount(virHashTablePtr hash, int count) int iter_count = 0;
if (virHashSize(hash) != count) { - testError("\nhash contains %d instead of %d elements\n", + testError("\nhash contains %zd instead of %d elements\n", virHashSize(hash), count); return -1; }
Ok Daniel -- |: http://berrange.com -o- http://www.flickr.com/photos/dberrange/ :| |: http://libvirt.org -o- http://virt-manager.org :| |: http://autobuild.org -o- http://search.cpan.org/~danberr/ :| |: http://entangle-photo.org -o- http://live.gnome.org/gtk-vnc :|
From: "Daniel P. Berrange" <berrange@redhat.com> In preparation for the patch to include Murmurhash3, which introduces a virhashcode.h and virhashcode.c files, rename the existing hash.h and hash.c to virhash.h and virhash.c respectively. --- po/POTFILES.in | 2 +- src/Makefile.am | 2 +- src/conf/domain_conf.h | 2 +- src/conf/nwfilter_conf.h | 2 +- src/conf/nwfilter_params.h | 2 +- src/cpu/cpu_generic.c | 2 +- src/qemu/qemu_monitor.h | 2 +- src/qemu/qemu_monitor_text.h | 1 - src/uml/uml_conf.h | 2 +- src/util/cgroup.c | 2 +- src/util/{hash.c => virhash.c} | 2 +- src/util/{hash.h => virhash.h} | 0 src/xen/xen_driver.h | 2 +- src/xen/xm_internal.c | 2 +- tests/Makefile.am | 10 +++++----- tests/{hashdata.h => virhashdata.h} | 0 tests/{hashtest.c => virhashtest.c} | 4 ++-- 17 files changed, 19 insertions(+), 20 deletions(-) rename src/util/{hash.c => virhash.c} (99%) rename src/util/{hash.h => virhash.h} (100%) rename tests/{hashdata.h => virhashdata.h} (100%) rename tests/{hashtest.c => virhashtest.c} (99%) diff --git a/po/POTFILES.in b/po/POTFILES.in index 0126320..674d6df 100644 --- a/po/POTFILES.in +++ b/po/POTFILES.in @@ -110,7 +110,6 @@ src/util/command.c src/util/conf.c src/util/dnsmasq.c src/util/event_poll.c -src/util/hash.c src/util/hooks.c src/util/hostusb.c src/util/iohelper.c @@ -126,6 +125,7 @@ src/util/sysinfo.c src/util/util.c src/util/viraudit.c src/util/virfile.c +src/util/virhash.c src/util/virnetdev.c src/util/virnetdevbridge.c src/util/virnetdevmacvlan.c diff --git a/src/Makefile.am b/src/Makefile.am index 4629700..eacc741 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -60,7 +60,6 @@ UTIL_SOURCES = \ util/cgroup.c util/cgroup.h \ util/event.c util/event.h \ util/event_poll.c util/event_poll.h \ - util/hash.c util/hash.h \ util/hooks.c util/hooks.h \ util/iptables.c util/iptables.h \ util/ebtables.c util/ebtables.h \ @@ -90,6 +89,7 @@ UTIL_SOURCES = \ util/virtypedparam.c util/virtypedparam.h \ util/xml.c util/xml.h \ util/virterror.c util/virterror_internal.h \ + util/virhash.c util/virhash.h \ util/virkeycode.c util/virkeycode.h \ util/virkeymaps.h \ util/virnetdev.h util/virnetdev.c \ diff --git a/src/conf/domain_conf.h b/src/conf/domain_conf.h index 3b522a9..7a8f12d 100644 --- a/src/conf/domain_conf.h +++ b/src/conf/domain_conf.h @@ -34,7 +34,7 @@ # include "cpu_conf.h" # include "util.h" # include "threads.h" -# include "hash.h" +# include "virhash.h" # include "virsocketaddr.h" # include "nwfilter_params.h" # include "nwfilter_conf.h" diff --git a/src/conf/nwfilter_conf.h b/src/conf/nwfilter_conf.h index 4331ab1..3cb4b82 100644 --- a/src/conf/nwfilter_conf.h +++ b/src/conf/nwfilter_conf.h @@ -32,7 +32,7 @@ # include "internal.h" # include "util.h" -# include "hash.h" +# include "virhash.h" # include "xml.h" # include "buf.h" # include "virsocketaddr.h" diff --git a/src/conf/nwfilter_params.h b/src/conf/nwfilter_params.h index fa8f770..eab46ec 100644 --- a/src/conf/nwfilter_params.h +++ b/src/conf/nwfilter_params.h @@ -23,7 +23,7 @@ #ifndef NWFILTER_PARAMS_H # define NWFILTER_PARAMS_H -# include "hash.h" +# include "virhash.h" # include "buf.h" enum virNWFilterVarValueType { diff --git a/src/cpu/cpu_generic.c b/src/cpu/cpu_generic.c index a98b109..2a31b49 100644 --- a/src/cpu/cpu_generic.c +++ b/src/cpu/cpu_generic.c @@ -25,7 +25,7 @@ #include <config.h> #include "memory.h" -#include "hash.h" +#include "virhash.h" #include "cpu.h" #include "cpu_generic.h" diff --git a/src/qemu/qemu_monitor.h b/src/qemu/qemu_monitor.h index 15acf8b..88ce303 100644 --- a/src/qemu/qemu_monitor.h +++ b/src/qemu/qemu_monitor.h @@ -29,7 +29,7 @@ # include "domain_conf.h" # include "qemu_conf.h" -# include "hash.h" +# include "virhash.h" typedef struct _qemuMonitor qemuMonitor; typedef qemuMonitor *qemuMonitorPtr; diff --git a/src/qemu/qemu_monitor_text.h b/src/qemu/qemu_monitor_text.h index dee2980..47a946d 100644 --- a/src/qemu/qemu_monitor_text.h +++ b/src/qemu/qemu_monitor_text.h @@ -28,7 +28,6 @@ # include "internal.h" # include "qemu_monitor.h" -# include "hash.h" int qemuMonitorTextIOProcess(qemuMonitorPtr mon, const char *data, diff --git a/src/uml/uml_conf.h b/src/uml/uml_conf.h index 383ae66..f942116 100644 --- a/src/uml/uml_conf.h +++ b/src/uml/uml_conf.h @@ -32,7 +32,7 @@ # include "virterror_internal.h" # include "threads.h" # include "command.h" -# include "hash.h" +# include "virhash.h" # define umlDebug(fmt, ...) do {} while(0) diff --git a/src/util/cgroup.c b/src/util/cgroup.c index a270965..7d7570a 100644 --- a/src/util/cgroup.c +++ b/src/util/cgroup.c @@ -32,7 +32,7 @@ #include "cgroup.h" #include "logging.h" #include "virfile.h" -#include "hash.h" +#include "virhash.h" #define CGROUP_MAX_VAL 512 diff --git a/src/util/hash.c b/src/util/virhash.c similarity index 99% rename from src/util/hash.c rename to src/util/virhash.c index 20d3a12..7294c7e 100644 --- a/src/util/hash.c +++ b/src/util/virhash.c @@ -25,7 +25,7 @@ #include <stdlib.h> #include "virterror_internal.h" -#include "hash.h" +#include "virhash.h" #include "memory.h" #include "logging.h" diff --git a/src/util/hash.h b/src/util/virhash.h similarity index 100% rename from src/util/hash.h rename to src/util/virhash.h diff --git a/src/xen/xen_driver.h b/src/xen/xen_driver.h index 4122378..3cefea3 100644 --- a/src/xen/xen_driver.h +++ b/src/xen/xen_driver.h @@ -20,7 +20,7 @@ # include "xen_inotify.h" # endif # include "domain_event.h" -# include "hash.h" +# include "virhash.h" # ifndef HAVE_WINSOCK2_H # include <sys/un.h> diff --git a/src/xen/xm_internal.c b/src/xen/xm_internal.c index 9c376fb..a34e906 100644 --- a/src/xen/xm_internal.c +++ b/src/xen/xm_internal.c @@ -42,7 +42,7 @@ #include "xend_internal.h" #include "xen_sxpr.h" #include "xen_xm.h" -#include "hash.h" +#include "virhash.h" #include "buf.h" #include "uuid.h" #include "util.h" diff --git a/tests/Makefile.am b/tests/Makefile.am index f3b0c09..ed47779 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -95,7 +95,7 @@ EXTRA_DIST = \ check_PROGRAMS = virshtest conftest sockettest \ nodeinfotest qparamtest virbuftest \ commandtest commandhelper seclabeltest \ - hashtest virnetmessagetest virnetsockettest ssh \ + virhashtest virnetmessagetest virnetsockettest ssh \ utiltest virnettlscontexttest shunloadtest \ virtimetest @@ -214,7 +214,7 @@ TESTS = virshtest \ sockettest \ commandtest \ seclabeltest \ - hashtest \ + virhashtest \ virnetmessagetest \ virnetsockettest \ virnettlscontexttest \ @@ -515,9 +515,9 @@ virbuftest_SOURCES = \ virbuftest.c testutils.h testutils.c virbuftest_LDADD = $(LDADDS) -hashtest_SOURCES = \ - hashtest.c hashdata.h testutils.h testutils.c -hashtest_LDADD = $(LDADDS) +virhashtest_SOURCES = \ + virhashtest.c virhashdata.h testutils.h testutils.c +virhashtest_LDADD = $(LDADDS) jsontest_SOURCES = \ jsontest.c testutils.h testutils.c diff --git a/tests/hashdata.h b/tests/virhashdata.h similarity index 100% rename from tests/hashdata.h rename to tests/virhashdata.h diff --git a/tests/hashtest.c b/tests/virhashtest.c similarity index 99% rename from tests/hashtest.c rename to tests/virhashtest.c index 441672c..70d0452 100644 --- a/tests/hashtest.c +++ b/tests/virhashtest.c @@ -6,8 +6,8 @@ #include <time.h> #include "internal.h" -#include "hash.h" -#include "hashdata.h" +#include "virhash.h" +#include "virhashdata.h" #include "testutils.h" #include "memory.h" -- 1.7.7.5
On 01/25/2012 09:38 AM, Daniel P. Berrange wrote:
From: "Daniel P. Berrange" <berrange@redhat.com>
In preparation for the patch to include Murmurhash3, which introduces a virhashcode.h and virhashcode.c files, rename the existing hash.h and hash.c to virhash.h and virhash.c respectively. --- po/POTFILES.in | 2 +- src/Makefile.am | 2 +- src/conf/domain_conf.h | 2 +- src/conf/nwfilter_conf.h | 2 +- src/conf/nwfilter_params.h | 2 +- src/cpu/cpu_generic.c | 2 +- src/qemu/qemu_monitor.h | 2 +- src/qemu/qemu_monitor_text.h | 1 - src/uml/uml_conf.h | 2 +- src/util/cgroup.c | 2 +- src/util/{hash.c => virhash.c} | 2 +- src/util/{hash.h => virhash.h} | 0 src/xen/xen_driver.h | 2 +- src/xen/xm_internal.c | 2 +- tests/Makefile.am | 10 +++++----- tests/{hashdata.h => virhashdata.h} | 0 tests/{hashtest.c => virhashtest.c} | 4 ++--
Gotta love git diffs of a file rename :)
+++ b/src/qemu/qemu_monitor_text.h @@ -28,7 +28,6 @@ # include "internal.h"
# include "qemu_monitor.h" -# include "hash.h"
Huh - wonder why we had a stale header. Recently, there was talk on the gnulib list about generalizing the useless-include syntax checker to be extensible to arbitrary headers, although there is nothing yet concrete from that discussion. If it ever materializes, we could use it for our own headers to catch dead includes like this one.
diff --git a/src/util/hash.c b/src/util/virhash.c similarity index 99% rename from src/util/hash.c rename to src/util/virhash.c
Missing a change in the comment header. ACK - here's my trivial contribution: diff --git i/src/util/virhash.c w/src/util/virhash.c index 7294c7e..8eff50b 100644 --- i/src/util/virhash.c +++ w/src/util/virhash.c @@ -1,9 +1,9 @@ /* - * hash.c: chained hash tables for domain and domain/connection deallocations + * virhash.c: chained hash tables for domain and domain/connection deallocations * * Reference: Your favorite introductory book on algorithms * - * Copyright (C) 2011 Red Hat, Inc. + * Copyright (C) 2011-2012 Red Hat, Inc. * Copyright (C) 2000 Bjorn Reese and Daniel Veillard. * * Permission to use, copy, modify, and distribute this software for any -- Eric Blake eblake@redhat.com +1-919-301-3266 Libvirt virtualization library http://libvirt.org
On 01/25/2012 11:44 AM, Eric Blake wrote:
On 01/25/2012 09:38 AM, Daniel P. Berrange wrote:
From: "Daniel P. Berrange" <berrange@redhat.com>
In preparation for the patch to include Murmurhash3, which introduces a virhashcode.h and virhashcode.c files, rename the existing hash.h and hash.c to virhash.h and virhash.c respectively.
ACK - here's my trivial contribution:
Also, we probably ought to continue to ignore the old (stale) binary, as well as the new binary name: diff --git i/.gitignore w/.gitignore index 61a9a38..2533fce 100644 --- i/.gitignore +++ w/.gitignore @@ -74,14 +74,15 @@ /tests/hashtest /tests/jsontest /tests/networkxml2argvtest /tests/nwfilterxml2xmltest /tests/openvzutilstest /tests/qemuxmlnstest /tests/shunloadtest +/tests/virhashtest /update.log Makefile Makefile.in TAGS coverage cscope.files cscope.out -- Eric Blake eblake@redhat.com +1-919-301-3266 Libvirt virtualization library http://libvirt.org
On Wed, Jan 25, 2012 at 11:44:56AM -0700, Eric Blake wrote:
On 01/25/2012 09:38 AM, Daniel P. Berrange wrote:
From: "Daniel P. Berrange" <berrange@redhat.com>
In preparation for the patch to include Murmurhash3, which introduces a virhashcode.h and virhashcode.c files, rename the existing hash.h and hash.c to virhash.h and virhash.c respectively. --- po/POTFILES.in | 2 +- src/Makefile.am | 2 +- src/conf/domain_conf.h | 2 +- src/conf/nwfilter_conf.h | 2 +- src/conf/nwfilter_params.h | 2 +- src/cpu/cpu_generic.c | 2 +- src/qemu/qemu_monitor.h | 2 +- src/qemu/qemu_monitor_text.h | 1 - src/uml/uml_conf.h | 2 +- src/util/cgroup.c | 2 +- src/util/{hash.c => virhash.c} | 2 +- src/util/{hash.h => virhash.h} | 0 src/xen/xen_driver.h | 2 +- src/xen/xm_internal.c | 2 +- tests/Makefile.am | 10 +++++----- tests/{hashdata.h => virhashdata.h} | 0 tests/{hashtest.c => virhashtest.c} | 4 ++--
Gotta love git diffs of a file rename :)
+++ b/src/qemu/qemu_monitor_text.h @@ -28,7 +28,6 @@ # include "internal.h"
# include "qemu_monitor.h" -# include "hash.h"
Huh - wonder why we had a stale header.
It is & it isn't stale. This File does reference virHashTablePtr in the API, but we inherit the include of virhash.h, from the qemu_monitor.h line just above, which defines all the same API contracts, Daniel -- |: http://berrange.com -o- http://www.flickr.com/photos/dberrange/ :| |: http://libvirt.org -o- http://virt-manager.org :| |: http://autobuild.org -o- http://search.cpan.org/~danberr/ :| |: http://entangle-photo.org -o- http://live.gnome.org/gtk-vnc :|
From: "Daniel P. Berrange" <berrange@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. * 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 diff --git a/bootstrap.conf b/bootstrap.conf index 04c7645..03da267 100644 --- a/bootstrap.conf +++ b/bootstrap.conf @@ -23,6 +23,7 @@ accept areadlink base64 bind +bitrotate byteswap c-ctype c-strcase diff --git a/src/Makefile.am b/src/Makefile.am index eacc741..22fd58e 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -90,6 +90,7 @@ UTIL_SOURCES = \ util/xml.c util/xml.h \ util/virterror.c util/virterror_internal.h \ util/virhash.c util/virhash.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 7d7570a..828ad66 100644 --- a/src/util/cgroup.c +++ b/src/util/cgroup.c @@ -33,6 +33,7 @@ #include "logging.h" #include "virfile.h" #include "virhash.h" +#include "virhashcode.h" #define CGROUP_MAX_VAL 512 @@ -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); } static bool virCgroupPidEqual(const void *namea, const void *nameb) { diff --git a/src/util/virhash.c b/src/util/virhash.c index 7294c7e..4ee1a1c 100644 --- a/src/util/virhash.c +++ b/src/util/virhash.c @@ -28,6 +28,8 @@ #include "virhash.h" #include "memory.h" #include "logging.h" +#include "virhashcode.h" +#include "virrandom.h" #define VIR_FROM_THIS VIR_FROM_NONE @@ -57,6 +59,7 @@ struct _virHashEntry { */ struct _virHashTable { virHashEntryPtr *table; + uint32_t seed; size_t size; size_t nbElems; /* True iff we are iterating over hash entries. */ @@ -70,20 +73,9 @@ struct _virHashTable { virHashKeyFree keyFree; }; -static uint32_t virHashStrCode(const void *name) +static uint32_t virHashStrCode(const void *name, uint32_t seed) { - const char *str = name; - uint32_t value = 0L; - char ch; - - if (str != NULL) { - value += 30 * (*str); - while ((ch = *str++) != 0) { - value = - value ^ ((value << 5) + (value >> 3) + (uint32_t) ch); - } - } - return value; + return virHashCodeGen(name, strlen(name), seed); } static bool virHashStrEqual(const void *namea, const void *nameb) @@ -105,7 +97,7 @@ static void virHashStrFree(void *name) static size_t virHashComputeKey(virHashTablePtr table, const void *name) { - uint32_t value = table->keyCode(name); + uint32_t value = table->keyCode(name, table->seed); return (value % table->size); } @@ -139,6 +131,7 @@ virHashTablePtr virHashCreateFull(ssize_t size, return NULL; } + table->seed = virRandomBits(32); table->size = size; table->nbElems = 0; table->dataFree = dataFree; diff --git a/src/util/virhash.h b/src/util/virhash.h index 2420045..7360676 100644 --- a/src/util/virhash.h +++ b/src/util/virhash.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 uint32_t (*virHashKeyCode)(const void *name); +typedef uint32_t (*virHashKeyCode)(const void *name, + uint32_t seed); /** * virHashKeyEqual: * @namea: the first hash key diff --git a/src/util/virhashcode.c b/src/util/virhashcode.c new file mode 100644 index 0000000..7b2bbf2 --- /dev/null +++ b/src/util/virhashcode.c @@ -0,0 +1,121 @@ +/* + * 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" +#include "bitrotate.h" + +/* 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 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 = rotl32(k1, 15); + k1 *= c2; + + h1 ^= k1; + h1 = rotl32(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 = rotl32(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
On 01/25/2012 09:38 AM, Daniel P. Berrange wrote:
From: "Daniel P. Berrange" <berrange@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@redhat.com +1-919-301-3266 Libvirt virtualization library http://libvirt.org
participants (2)
-
Daniel P. Berrange -
Eric Blake