11:54 a.m.
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
11:54 a.m.
New subject: [libvirt] [PATCH] util: Fix crash when removing entries during hash iteration
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
12:06 p.m.
New subject: [libvirt] [PATCH] util: Fix crash when removing entries during hash iteration
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(a)redhat.com +1-801-349-2682
Libvirt virtualization library http://libvirt.org
12:24 p.m.
New subject: [libvirt] [PATCH] util: Fix crash when removing entries during hash iteration
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
6:15 a.m.
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 :|
3:04 p.m.
New subject: [libvirt] [PATCH] tests: Unit tests for internal hash APIs
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
5:31 p.m.
New subject: [libvirt] [PATCH] tests: Unit tests for internal hash APIs
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(a)redhat.com +1-801-349-2682
Libvirt virtualization library http://libvirt.org
4:47 a.m.
New subject: [libvirt] [PATCH] tests: Unit tests for internal hash APIs
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
10:31 a.m.
New subject: [libvirt] [PATCH] maint: ignore built file
* .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
4967
days inactive
4973
days old
8 comments
3 participants
participants (3)
-
Daniel P. Berrange -
Eric Blake -
Jiri Denemark