[libvirt] [PATCH] util: Simplify hash implementation
So far first entries for each hash key are stored directly in the hash table while other entries mapped to the same key are linked through pointers. As a result of that, the code is cluttered with special handling for the first items. Commit 9677cd33eea4c65d78ba463b46b8b45ed2da1709 made it possible to remove current entry when iterating through all hash entries. However, it didn't add the special first item handling which could cause libvirtd crash or hang. Instead of adding more clutter, this patch fixes the crash by linking all entries (even the first ones) through pointers which significantly simplifies the code and makes it more maintainable. --- src/util/hash.c | 290 ++++++++++++++++++------------------------------------- 1 files changed, 94 insertions(+), 196 deletions(-) diff --git a/src/util/hash.c b/src/util/hash.c index 48a94ad..dbb34ec 100644 --- a/src/util/hash.c +++ b/src/util/hash.c @@ -50,14 +50,13 @@ struct _virHashEntry { struct _virHashEntry *next; void *name; void *payload; - int valid; }; /* * The entire hash table */ struct _virHashTable { - struct _virHashEntry *table; + virHashEntryPtr *table; int size; int nbElems; /* True iff we are iterating over hash entries. */ @@ -165,7 +164,7 @@ virHashTablePtr virHashCreateFull(int size, * * Create a new virHashTablePtr. * - * Returns the newly created object, or NULL if an error occured. + * Returns the newly created object, or NULL if an error occurred. */ virHashTablePtr virHashCreate(int size, virHashDataFree dataFree) { @@ -189,10 +188,8 @@ virHashTablePtr virHashCreate(int size, virHashDataFree dataFree) static int virHashGrow(virHashTablePtr table, int size) { - unsigned long key; int oldsize, i; - virHashEntryPtr iter, next; - struct _virHashEntry *oldtable; + virHashEntryPtr *oldtable; #ifdef DEBUG_GROW unsigned long nbElem = 0; @@ -217,43 +214,18 @@ virHashGrow(virHashTablePtr table, int size) } table->size = size; - /* If the two loops are merged, there would be situations where - * a new entry needs to allocated and data copied into it from - * the main table. So instead, we run through the array twice, first - * copying all the elements in the main array (where we can't get - * conflicts) and then the rest, so we only free (and don't allocate) - */ - for (i = 0; i < oldsize; i++) { - if (oldtable[i].valid == 0) - continue; - key = virHashComputeKey(table, oldtable[i].name); - memcpy(&(table->table[key]), &(oldtable[i]), sizeof(virHashEntry)); - table->table[key].next = NULL; - } - for (i = 0; i < oldsize; i++) { - iter = oldtable[i].next; + virHashEntryPtr iter = oldtable[i]; while (iter) { - next = iter->next; + virHashEntryPtr next = iter->next; + unsigned long key = virHashComputeKey(table, iter->name); - /* - * put back the entry in the new table - */ - - key = virHashComputeKey(table, iter->name); - if (table->table[key].valid == 0) { - memcpy(&(table->table[key]), iter, sizeof(virHashEntry)); - table->table[key].next = NULL; - VIR_FREE(iter); - } else { - iter->next = table->table[key].next; - table->table[key].next = iter; - } + iter->next = table->table[key]; + table->table[key] = iter; #ifdef DEBUG_GROW nbElem++; #endif - iter = next; } } @@ -279,36 +251,24 @@ void virHashFree(virHashTablePtr table) { int i; - virHashEntryPtr iter; - virHashEntryPtr next; - int inside_table = 0; - int nbElems; if (table == NULL) return; - if (table->table) { - nbElems = table->nbElems; - for (i = 0; (i < table->size) && (nbElems > 0); i++) { - iter = &(table->table[i]); - if (iter->valid == 0) - continue; - inside_table = 1; - while (iter) { - next = iter->next; - if ((table->dataFree != NULL) && (iter->payload != NULL)) - table->dataFree(iter->payload, iter->name); - if (table->keyFree) - table->keyFree(iter->name); - iter->payload = NULL; - if (!inside_table) - VIR_FREE(iter); - nbElems--; - inside_table = 0; - iter = next; - } + + for (i = 0; i < table->size; i++) { + virHashEntryPtr iter = table->table[i]; + while (iter) { + virHashEntryPtr next = iter->next; + + if (table->dataFree) + table->dataFree(iter->payload, iter->name); + if (table->keyFree) + table->keyFree(iter->name); + VIR_FREE(iter); + iter = next; } - VIR_FREE(table->table); } + VIR_FREE(table); } @@ -319,9 +279,7 @@ virHashAddOrUpdateEntry(virHashTablePtr table, const void *name, { unsigned long key, len = 0; virHashEntryPtr entry; - virHashEntryPtr insert; char *new_name; - bool found; if ((table == NULL) || (name == NULL)) return (-1); @@ -329,67 +287,40 @@ virHashAddOrUpdateEntry(virHashTablePtr table, const void *name, if (table->iterating) virHashIterationError(-1); - /* - * Check for duplicate and insertion location. - */ - found = false; key = virHashComputeKey(table, name); - if (table->table[key].valid == 0) { - insert = NULL; - } else { - for (insert = &(table->table[key]); insert->next != NULL; - insert = insert->next) { - if (table->keyEqual(insert->name, name)) { - found = true; - break; - } - len++; - } - if (table->keyEqual(insert->name, name)) - found = true; - } - - if (found) { - if (is_update) { - if (table->dataFree) - table->dataFree(insert->payload, insert->name); - insert->payload = userdata; - return (0); - } else { - return (-1); - } - } - if (insert == NULL) { - entry = &(table->table[key]); - } else { - if (VIR_ALLOC(entry) < 0) { - virReportOOMError(); - return (-1); + /* Check for duplicate entry */ + for (entry = table->table[key]; entry; entry = entry->next) { + if (table->keyEqual(entry->name, name)) { + if (is_update) { + if (table->dataFree) + table->dataFree(entry->payload, entry->name); + entry->payload = userdata; + return 0; + } else { + return -1; + } } + len++; } - new_name = table->keyCopy(name); - if (new_name == NULL) { + if (VIR_ALLOC(entry) < 0 || !(new_name = table->keyCopy(name))) { virReportOOMError(); - if (insert != NULL) - VIR_FREE(entry); - return (-1); + VIR_FREE(entry); + return -1; } + entry->name = new_name; entry->payload = userdata; - entry->next = NULL; - entry->valid = 1; - - if (insert != NULL) - insert->next = entry; + entry->next = table->table[key]; + table->table[key] = entry; table->nbElems++; if (len > MAX_HASH_LEN) virHashGrow(table, MAX_HASH_LEN * table->size); - return (0); + return 0; } /** @@ -443,18 +374,15 @@ virHashLookup(virHashTablePtr table, const void *name) unsigned long key; virHashEntryPtr entry; - if (table == NULL) - return (NULL); - if (name == NULL) - return (NULL); + if (!table || !name) + return NULL; + key = virHashComputeKey(table, name); - if (table->table[key].valid == 0) - return (NULL); - for (entry = &(table->table[key]); entry != NULL; entry = entry->next) { + for (entry = table->table[key]; entry; entry = entry->next) { if (table->keyEqual(entry->name, name)) - return (entry->payload); + return entry->payload; } - return (NULL); + return NULL; } @@ -512,47 +440,31 @@ virHashSize(virHashTablePtr table) int virHashRemoveEntry(virHashTablePtr table, const void *name) { - unsigned long key; virHashEntryPtr entry; - virHashEntryPtr prev = NULL; + virHashEntryPtr *nextptr; if (table == NULL || name == NULL) return (-1); - key = virHashComputeKey(table, name); - if (table->table[key].valid == 0) { - return (-1); - } else { - for (entry = &(table->table[key]); entry != NULL; - entry = entry->next) { - if (table->keyEqual(entry->name, name)) { - if (table->iterating && table->current != entry) - virHashIterationError(-1); - if (table->dataFree && (entry->payload != NULL)) - table->dataFree(entry->payload, entry->name); - entry->payload = NULL; - if (table->keyFree) - table->keyFree(entry->name); - if (prev) { - prev->next = entry->next; - VIR_FREE(entry); - } else { - if (entry->next == NULL) { - entry->valid = 0; - } else { - entry = entry->next; - memcpy(&(table->table[key]), entry, - sizeof(virHashEntry)); - VIR_FREE(entry); - } - } - table->nbElems--; - return (0); - } - prev = entry; + nextptr = table->table + virHashComputeKey(table, name); + for (entry = *nextptr; entry; entry = entry->next) { + if (table->keyEqual(entry->name, name)) { + if (table->iterating && table->current != entry) + virHashIterationError(-1); + + if (table->dataFree) + table->dataFree(entry->payload, entry->name); + if (table->keyFree) + table->keyFree(entry->name); + *nextptr = entry->next; + VIR_FREE(entry); + table->nbElems--; + return 0; } - return (-1); + nextptr = &entry->next; } + + return -1; } @@ -581,15 +493,15 @@ int virHashForEach(virHashTablePtr table, virHashIterator iter, void *data) table->iterating = true; table->current = NULL; for (i = 0 ; i < table->size ; i++) { - virHashEntryPtr entry = table->table + i; + virHashEntryPtr entry = table->table[i]; while (entry) { virHashEntryPtr next = entry->next; - if (entry->valid) { - table->current = entry; - iter(entry->payload, entry->name, data); - table->current = NULL; - count++; - } + + table->current = entry; + iter(entry->payload, entry->name, data); + table->current = NULL; + + count++; entry = next; } } @@ -612,7 +524,10 @@ 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) { +int virHashRemoveSet(virHashTablePtr table, + virHashSearcher iter, + const void *data) +{ int i, count = 0; if (table == NULL || iter == NULL) @@ -624,44 +539,27 @@ int virHashRemoveSet(virHashTablePtr table, virHashSearcher iter, const void *da table->iterating = true; table->current = NULL; for (i = 0 ; i < table->size ; i++) { - virHashEntryPtr prev = NULL; - virHashEntryPtr entry = &(table->table[i]); + virHashEntryPtr *nextptr = table->table + i; - while (entry && entry->valid) { - if (iter(entry->payload, entry->name, data)) { + while (*nextptr) { + virHashEntryPtr entry = *nextptr; + if (!iter(entry->payload, entry->name, data)) { + *nextptr = entry->next; + } else { count++; if (table->dataFree) table->dataFree(entry->payload, entry->name); if (table->keyFree) table->keyFree(entry->name); + *nextptr = entry->next; + VIR_FREE(entry); table->nbElems--; - if (prev) { - prev->next = entry->next; - VIR_FREE(entry); - entry = prev; - } else { - if (entry->next == NULL) { - entry->valid = 0; - entry->name = NULL; - } else { - entry = entry->next; - memcpy(&(table->table[i]), entry, - sizeof(virHashEntry)); - VIR_FREE(entry); - entry = &(table->table[i]); - continue; - } - } - } - prev = entry; - if (entry) { - entry = entry->next; } } } table->iterating = false; - return (count); + return count; } /** @@ -675,7 +573,10 @@ int virHashRemoveSet(virHashTablePtr table, virHashSearcher iter, const void *da * returns non-zero will be returned by this function. * The elements are processed in a undefined order */ -void *virHashSearch(virHashTablePtr table, virHashSearcher iter, const void *data) { +void *virHashSearch(virHashTablePtr table, + virHashSearcher iter, + const void *data) +{ int i; if (table == NULL || iter == NULL) @@ -687,18 +588,15 @@ void *virHashSearch(virHashTablePtr table, virHashSearcher iter, const void *dat table->iterating = true; table->current = NULL; for (i = 0 ; i < table->size ; i++) { - virHashEntryPtr entry = table->table + i; - while (entry) { - if (entry->valid) { - if (iter(entry->payload, entry->name, data)) { - table->iterating = false; - return entry->payload; - } + virHashEntryPtr entry; + for (entry = table->table[i]; entry; entry = entry->next) { + if (iter(entry->payload, entry->name, data)) { + table->iterating = false; + return entry->payload; } - entry = entry->next; } } table->iterating = false; - return (NULL); + return NULL; } -- 1.7.5.rc1
Commit 9677cd33eea4c65d78ba463b46b8b45ed2da1709 made it possible to remove current entry when iterating through all hash entries. However, it didn't properly handle a special case of removing first entry assigned to a given key which contains several entries in its collision list. --- This is an alternate less invasive fix to "util: Simplify hash implementation". I prefer the more invasive fix for upstream but I'm sending this alternative here for completeness. src/util/hash.c | 8 ++++++++ 1 files changed, 8 insertions(+), 0 deletions(-) diff --git a/src/util/hash.c b/src/util/hash.c index 48a94ad..fc7652d 100644 --- a/src/util/hash.c +++ b/src/util/hash.c @@ -585,10 +585,18 @@ int virHashForEach(virHashTablePtr table, virHashIterator iter, void *data) while (entry) { virHashEntryPtr next = entry->next; if (entry->valid) { + void *name = (entry == table->table + i) ? entry->name : NULL; + table->current = entry; iter(entry->payload, entry->name, data); table->current = NULL; count++; + + /* revisit current entry if it was the first one in collision + * list and its content changed, i.e. it was deleted by iter() + */ + if (name && name != entry->name) + continue; } entry = next; } -- 1.7.5.rc1
On 04/12/2011 10:54 AM, Jiri Denemark wrote:
Commit 9677cd33eea4c65d78ba463b46b8b45ed2da1709 made it possible to remove current entry when iterating through all hash entries. However, it didn't properly handle a special case of removing first entry assigned to a given key which contains several entries in its collision list. --- This is an alternate less invasive fix to "util: Simplify hash implementation". I prefer the more invasive fix for upstream but I'm sending this alternative here for completeness.
For backporting purposes, would it make sense to apply this patch first, then apply the other one which undoes this patch as part of its simplifications? Then, anyone trying to pick and choose patches to backport can feel justified going with the smaller patch in isolation. As for this patch itself, ACK, but whether to apply it depends on the answer to the bigger question above. -- Eric Blake eblake@redhat.com +1-801-349-2682 Libvirt virtualization library http://libvirt.org
On Tue, Apr 12, 2011 at 11:06:17 -0600, Eric Blake wrote:
On 04/12/2011 10:54 AM, Jiri Denemark wrote:
Commit 9677cd33eea4c65d78ba463b46b8b45ed2da1709 made it possible to remove current entry when iterating through all hash entries. However, it didn't properly handle a special case of removing first entry assigned to a given key which contains several entries in its collision list. --- This is an alternate less invasive fix to "util: Simplify hash implementation". I prefer the more invasive fix for upstream but I'm sending this alternative here for completeness.
For backporting purposes, would it make sense to apply this patch first, then apply the other one which undoes this patch as part of its simplifications? Then, anyone trying to pick and choose patches to backport can feel justified going with the smaller patch in isolation.
That sounds like a good idea. I'll send a v2 for the simplification patch soon.
As for this patch itself, ACK, but whether to apply it depends on the answer to the bigger question above.
Thanks and I pushed it. Jirka
On Tue, Apr 12, 2011 at 06:54:33PM +0200, Jiri Denemark wrote:
So far first entries for each hash key are stored directly in the hash table while other entries mapped to the same key are linked through pointers. As a result of that, the code is cluttered with special handling for the first items.
Commit 9677cd33eea4c65d78ba463b46b8b45ed2da1709 made it possible to remove current entry when iterating through all hash entries. However, it didn't add the special first item handling which could cause libvirtd crash or hang.
This highlights what should be an obvious problem.... we have near zero test coverage of the hash table class. The code is totally standalone and it should be easy to write a test case to exercise all its methods, and many of the edge cases. IMHO we should fix the lack of a test suite before refactoring it again, so that we know we're actually get it right this time :-) Both the existing code & your new patch are complex enough, that I'm not confident in code review alone identifying all the bugs. Regards, 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 :|
This is a basic set of tests for testing removals of hash entries during iteration. --- More tests for all other hash APIs will come on Monday. tests/Makefile.am | 8 +++- tests/hashdata.h | 33 +++++++++++ tests/hashtest.c | 157 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 197 insertions(+), 1 deletions(-) create mode 100644 tests/hashdata.h create mode 100644 tests/hashtest.c diff --git a/tests/Makefile.am b/tests/Makefile.am index 5896442..063ab60 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -77,7 +77,8 @@ EXTRA_DIST = \ check_PROGRAMS = virshtest conftest sockettest \ nodeinfotest qparamtest virbuftest \ - commandtest commandhelper seclabeltest + commandtest commandhelper seclabeltest \ + hashtest if WITH_XEN check_PROGRAMS += xml2sexprtest sexpr2xmltest \ @@ -159,6 +160,7 @@ TESTS = virshtest \ sockettest \ commandtest \ seclabeltest \ + hashtest \ $(test_scripts) if WITH_XEN @@ -373,6 +375,10 @@ virbuftest_SOURCES = \ virbuftest.c testutils.h testutils.c virbuftest_LDADD = $(LDADDS) +hashtest_SOURCES = \ + hashtest.c hashdata.h testutils.h testutils.c +hashtest_LDADD = $(LDADDS) + if WITH_LIBVIRTD eventtest_SOURCES = \ eventtest.c testutils.h testutils.c diff --git a/tests/hashdata.h b/tests/hashdata.h new file mode 100644 index 0000000..2782255 --- /dev/null +++ b/tests/hashdata.h @@ -0,0 +1,33 @@ +const char *uuids[] = { +/* [ 46] */ "f17494ba-2353-4af0-b1ba-13680858edcc", + "64ab4e78-1b6e-4b88-b47f-2def46c79a86", + "f99b0d59-ecff-4cc6-a9d3-20159536edc8", +/* [ 75] */ "e1bfa30f-bc0b-4a24-99ae-bed7f3f21a7b", + "acda5fa0-58de-4e1e-aa65-2124d1e29c54", +/* [ 76] */ "5f476c28-8f26-48e0-98de-85745fe2f304", +/* [123] */ "8be1d21c-cd35-4c7c-8fee-4b5046c7a62b", + "830f0d57-9f21-40e8-bb86-cbf41de23fd6", + "57044958-1b8a-4c02-ab75-2298c6e44263", + "d526cd6c-4a99-4d5f-abfb-fc9419edd9d0", +/* [237] */ "3ab39f7f-4613-4da6-a216-c2d6acc441bb", + "ae20cf3c-38b8-483c-baea-6fb0994dc30c", + "cd204d90-2414-4b9e-9d4f-fed09c9a816f", +/* [240] */ "ed2cc723-db4b-43aa-ab02-0e3161087499", +/* [246] */ "8ada85bc-9bdf-4507-8334-849635ea0a01", + "8a7d5deb-615f-4cd3-8977-b5fab8ec4d05", +/* [247] */ "dc2173b0-48fe-4555-b190-8052be1120eb", + "040e434d-68d8-41a9-b3a1-1bee239914c1", + "d1a564b2-c7f3-4b76-8712-3b8f5aae6ded", + "0e614f33-c1da-4cfe-b6d5-65ecd2d066f2" +}; + +const char *uuids_subset[] = { + "64ab4e78-1b6e-4b88-b47f-2def46c79a86", + "acda5fa0-58de-4e1e-aa65-2124d1e29c54", + "830f0d57-9f21-40e8-bb86-cbf41de23fd6", + "57044958-1b8a-4c02-ab75-2298c6e44263", + "ae20cf3c-38b8-483c-baea-6fb0994dc30c", + "040e434d-68d8-41a9-b3a1-1bee239914c1", + "d1a564b2-c7f3-4b76-8712-3b8f5aae6ded", + "8ada85bc-9bdf-4507-8334-849635ea0a01" +}; diff --git a/tests/hashtest.c b/tests/hashtest.c new file mode 100644 index 0000000..dff0181 --- /dev/null +++ b/tests/hashtest.c @@ -0,0 +1,157 @@ +#include <config.h> + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "internal.h" +#include "hash.h" +#include "hashdata.h" +#include "testutils.h" + + +#define testError(...) \ + do { \ + fprintf(stderr, __VA_ARGS__); \ + /* Pad to line up with test name ... in virTestRun */ \ + fprintf(stderr, "%74s", "... "); \ + } while (0) + + +static virHashTablePtr +testHashInit(int size) +{ + virHashTablePtr hash; + int i; + + if (!(hash = virHashCreate(size, NULL))) + return NULL; + + /* entires are added in reverse order so that they will be linked in + * collision list in the same order as in the uuids array + */ + for (i = ARRAY_CARDINALITY(uuids) - 1; i >= 0; i--) { + if (virHashAddEntry(hash, uuids[i], (void *) uuids[i]) < 0) { + virHashFree(hash); + return NULL; + } + } + + return hash; +} + + +static int +testHashCheckCount(virHashTablePtr hash, int count) +{ + if (virHashSize(hash) != count) { + testError("\nhash contains %d instead of %d elements\n", + virHashSize(hash), count); + return -1; + } + + return 0; +} + + +struct testInfo { + void *data; + int count; +}; + + +const int testHashCountRemoveForEachSome = + ARRAY_CARDINALITY(uuids) - ARRAY_CARDINALITY(uuids_subset); + +static void +testHashRemoveForEachSome(void *payload ATTRIBUTE_UNUSED, + const void *name, + void *data) +{ + virHashTablePtr hash = data; + int i; + + for (i = 0; i < ARRAY_CARDINALITY(uuids_subset); i++) { + if (STREQ(uuids_subset[i], name)) { + if (virHashRemoveEntry(hash, name) < 0 && virTestGetVerbose()) { + fprintf(stderr, "\nentry \"%s\" could not be removed", + uuids_subset[i]); + } + break; + } + } +} + + +const int testHashCountRemoveForEachAll = 0; + +static void +testHashRemoveForEachAll(void *payload ATTRIBUTE_UNUSED, + const void *name, + void *data) +{ + virHashTablePtr hash = data; + + virHashRemoveEntry(hash, name); +} + + +static int +testHashRemoveForEach(const void *data) +{ + const struct testInfo *info = data; + virHashTablePtr hash; + int count; + int ret = -1; + + if (!(hash = testHashInit(0))) + return -1; + + count = virHashForEach(hash, (virHashIterator) info->data, hash); + + if (count != ARRAY_CARDINALITY(uuids)) { + if (virTestGetVerbose()) { + testError("\nvirHashForEach didn't go through all entries," + " %d != %lu\n", + count, ARRAY_CARDINALITY(uuids)); + } + goto cleanup; + } + + if (testHashCheckCount(hash, info->count) < 0) + goto cleanup; + + ret = 0; + +cleanup: + virHashFree(hash); + return ret; +} + + +static int +mymain(int argc ATTRIBUTE_UNUSED, + char **argv ATTRIBUTE_UNUSED) +{ + int ret = 0; + +#define DO_TEST_FULL(name, cmd, data, count) \ + do { \ + struct testInfo info = { data, count }; \ + if (virtTestRun(name, 1, testHash ## cmd, &info) < 0) \ + ret = -1; \ + } while (0) + +#define DO_TEST_DATA(name, cmd, data) \ + DO_TEST_FULL(name "(" #data ")", \ + cmd, \ + testHash ## cmd ## data, \ + testHashCount ## cmd ## data) + + DO_TEST_DATA("Remove in ForEach", RemoveForEach, Some); + DO_TEST_DATA("Remove in ForEach", RemoveForEach, All); + + return (ret == 0) ? EXIT_SUCCESS : EXIT_FAILURE; +} + +VIRT_TEST_MAIN(mymain) -- 1.7.5.rc1
On 04/15/2011 02:04 PM, Jiri Denemark wrote:
This is a basic set of tests for testing removals of hash entries during iteration. --- More tests for all other hash APIs will come on Monday.
Such as a test that gets 8 collisions into a single bucket to force hash table growth, or a test of custom hasher/comparator functions?
tests/Makefile.am | 8 +++- tests/hashdata.h | 33 +++++++++++ tests/hashtest.c | 157 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 197 insertions(+), 1 deletions(-) create mode 100644 tests/hashdata.h create mode 100644 tests/hashtest.c
+++ b/tests/hashdata.h @@ -0,0 +1,33 @@ +const char *uuids[] = { +/* [ 46] */ "f17494ba-2353-4af0-b1ba-13680858edcc", + "64ab4e78-1b6e-4b88-b47f-2def46c79a86", + "f99b0d59-ecff-4cc6-a9d3-20159536edc8", +/* [ 75] */ "e1bfa30f-bc0b-4a24-99ae-bed7f3f21a7b", + "acda5fa0-58de-4e1e-aa65-2124d1e29c54", +/* [ 76] */ "5f476c28-8f26-48e0-98de-85745fe2f304",
Looks suspiciously like you used gdb to dump an existing hash structure on a machine with lots of VMs :) Works for me.
+static virHashTablePtr +testHashInit(int size) +{ + virHashTablePtr hash; + int i; + + if (!(hash = virHashCreate(size, NULL))) + return NULL; + + /* entires are added in reverse order so that they will be linked in + * collision list in the same order as in the uuids array
We're abusing an an internal detail. So good to have the comment - if the test breaks because of another rewrite, but the only breakage is due to a different link order in each bucket, then I'm okay modifying the test at that point, and meanwhile it justifies our abuse (that is, no change needed).
+#define DO_TEST_DATA(name, cmd, data) \ + DO_TEST_FULL(name "(" #data ")", \ + cmd, \ + testHash ## cmd ## data, \ + testHashCount ## cmd ## data) + + DO_TEST_DATA("Remove in ForEach", RemoveForEach, Some); + DO_TEST_DATA("Remove in ForEach", RemoveForEach, All); + + return (ret == 0) ? EXIT_SUCCESS : EXIT_FAILURE;
Looks like a good test; it certainly would have caught the previous bugs before the most recent hash.c fixes. ACK. -- Eric Blake eblake@redhat.com +1-801-349-2682 Libvirt virtualization library http://libvirt.org
On Fri, Apr 15, 2011 at 16:31:15 -0600, Eric Blake wrote:
On 04/15/2011 02:04 PM, Jiri Denemark wrote:
This is a basic set of tests for testing removals of hash entries during iteration. --- More tests for all other hash APIs will come on Monday.
Such as a test that gets 8 collisions into a single bucket to force hash table growth
Yes.
, or a test of custom hasher/comparator functions?
Not yet, but I'll add it, thanks for mentioning that :-)
+++ b/tests/hashdata.h @@ -0,0 +1,33 @@ +const char *uuids[] = { +/* [ 46] */ "f17494ba-2353-4af0-b1ba-13680858edcc", + "64ab4e78-1b6e-4b88-b47f-2def46c79a86", + "f99b0d59-ecff-4cc6-a9d3-20159536edc8", +/* [ 75] */ "e1bfa30f-bc0b-4a24-99ae-bed7f3f21a7b", + "acda5fa0-58de-4e1e-aa65-2124d1e29c54", +/* [ 76] */ "5f476c28-8f26-48e0-98de-85745fe2f304",
Looks suspiciously like you used gdb to dump an existing hash structure on a machine with lots of VMs :) Works for me.
Not really, I just generated a bunch of UUIDs with uuidgen, used them within this test to create a hash, dumped that in gdb and replaced the original list with this dump :-) The full set of UUIDs will come with the additional tests since these two test didn't really require so many entries in a hash table.
+static virHashTablePtr +testHashInit(int size) +{ + virHashTablePtr hash; + int i; + + if (!(hash = virHashCreate(size, NULL))) + return NULL; + + /* entires are added in reverse order so that they will be linked in + * collision list in the same order as in the uuids array
We're abusing an an internal detail. So good to have the comment - if the test breaks because of another rewrite, but the only breakage is due to a different link order in each bucket, then I'm okay modifying the test at that point, and meanwhile it justifies our abuse (that is, no change needed).
The order doesn't matter much. Actually the comment isn't even right for current hash code. It's correct only after applying the hash rewrite. Making sure link order matches the uuids array just helps with designing the tests. E.g., when removing entries, one can easily say which entry is the first, last or in the middle of the list and can select appropriate uuids to test removing from different places in the list.
+#define DO_TEST_DATA(name, cmd, data) \ + DO_TEST_FULL(name "(" #data ")", \ + cmd, \ + testHash ## cmd ## data, \ + testHashCount ## cmd ## data) + + DO_TEST_DATA("Remove in ForEach", RemoveForEach, Some); + DO_TEST_DATA("Remove in ForEach", RemoveForEach, All); + + return (ret == 0) ? EXIT_SUCCESS : EXIT_FAILURE;
Looks like a good test; it certainly would have caught the previous bugs before the most recent hash.c fixes.
Yes, of course I tested this test with older libvirt code without the hash fixes and the test just segfaults.
ACK.
Thanks, pushed. Jirka
* .gitignore: Add exemption for hashtest. --- Pushing this under the trivial rule. .gitignore | 1 + 1 files changed, 1 insertions(+), 0 deletions(-) diff --git a/.gitignore b/.gitignore index 35dbdde..803f2a3 100644 --- a/.gitignore +++ b/.gitignore @@ -51,6 +51,7 @@ /src/libvirt_iohelper /tests/*.log /tests/cputest +/tests/hashtest /tests/nwfilterxml2xmltest /update.log Makefile -- 1.7.4.2
participants (3)
-
Daniel P. Berrange -
Eric Blake -
Jiri Denemark