On Mon, Jul 15, 2013 at 08:21:04AM +0800, ZhengLingyun wrote:
> hindex_next() shouldn't jump over different hashs in the same bucket.
> tests/test-hindex did not detect it, add a multipart_hash() method to detect
> it.
>
>
> Signed-off-by: ZhengLingyun <konghuaru...@163.com>
Thank you very much for finding the problem and fixing it.
hindex_head_node() seems suboptimal to me, because it follows as many
->d pointers as there are nodes with a single hash, which is
potentially a very large number. It seems better to just look through
the bucket's head node to find the head node, because there should be
at most 2 head nodes in the bucket in the average case.
Therefore, here is a counterproposal. What do you think?
Thanks again,
Ben.
--8<--------------------------cut here-------------------------->8--
From: ZhengLingyun <konghuaru...@163.com>
Date: Mon, 15 Jul 2013 08:21:04 +0800
Subject: [PATCH] hindex: Fix incomplete iteration bug.
hindex_next() make the completely wrong assumption that head nodes within
a bucket were sorted in ascending order by hash. This commit removes
that assumption.
Also add a test that would have found the problem.
Signed-off-by: ZhengLingyun <konghuaru...@163.com>
[b...@nicira.com changed how hindex_head_node() is implemented and
other code details]
Signed-off-by: Ben Pfaff <b...@nicira.com>
---
lib/hindex.c | 35 +++++++++++++++++++++++++++++------
tests/test-hindex.c | 7 +++++++
2 files changed, 36 insertions(+), 6 deletions(-)
diff --git a/lib/hindex.c b/lib/hindex.c
index dc0f1b7..fd4199a 100644
--- a/lib/hindex.c
+++ b/lib/hindex.c
@@ -287,6 +287,19 @@ hindex_node_with_hash(const struct hindex *hindex, size_t
hash)
return node;
}
+/* Returns the head node in 'hindex' with the given 'hash'. 'hindex' must
+ * contain a head node with the given hash. */
+static struct hindex_node *
+hindex_head_node(const struct hindex *hindex, size_t hash)
+{
+ struct hindex_node *node = hindex->buckets[hash & hindex->mask];
+
+ while (node->hash != hash) {
+ node = node->d;
+ }
+ return node;
+}
+
static struct hindex_node *
hindex_next__(const struct hindex *hindex, size_t start)
{
@@ -312,13 +325,23 @@ hindex_first(const struct hindex *hindex)
* null pointer if 'node' is the last node in 'hindex'.
*
* If the hash index has been reallocated since 'node' was visited, some nodes
- * may be skipped or visited twice. (Removing 'node' from the hash index does
- * not prevent calling this function, since node->next is preserved, although
- * freeing 'node' of course does.) */
+ * may be skipped or visited twice. */
struct hindex_node *
hindex_next(const struct hindex *hindex, const struct hindex_node *node)
{
- return (node->s ? node->s
- : node->d && node->d->hash != node->hash ? node->d
- : hindex_next__(hindex, (node->hash & hindex->mask) + 1));
+ struct hindex_node *head;
+
+ /* If there's a node with the same hash, return it. */
+ if (node->s) {
+ return node->s;
+ }
+
+ /* If there's another node in the same bucket, return it. */
+ head = hindex_head_node(hindex, node->hash);
+ if (head->d) {
+ return head->d;
+ }
+
+ /* Return the first node in the next (or later) bucket. */
+ return hindex_next__(hindex, (node->hash & hindex->mask) + 1);
}
diff --git a/tests/test-hindex.c b/tests/test-hindex.c
index 7a3ef72..f0a8b93 100644
--- a/tests/test-hindex.c
+++ b/tests/test-hindex.c
@@ -178,6 +178,12 @@ mod2_hash(int value)
return value % 2;
}
+static size_t
+multipart_hash(int value)
+{
+ return (mod4_hash(value) << 16) | (constant_hash(value) & 0xFFFF);
+}
+
/* Tests basic hindex insertion and deletion. */
static void
test_hindex_insert_delete(hash_func *hash)
@@ -298,6 +304,7 @@ run_test(void (*function)(hash_func *))
mod4_hash,
mod3_hash,
mod2_hash,
+ multipart_hash,
};
size_t i;
--
1.7.2.5
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
