As you have said in hindex.h, hindex need a high-quality hash function to
work appropriately. So maybe these two kinds of hindex_head_node() are
similar in performance.
If unfortunately hindex meets a low-quality hash function, i think it will
depands on the hash function, which will more likely to produce the same
hash result, like constant_hash(), or will more likely to produce different hash
but AND a MASK will produce a same result, like
hash = (good_hash(value) << 16 | constant_hash() & 0xFFFF).
Maybe we can just use hindex_node_with_hash() instead of hindex_head_node(),
these two functions seems confusing.
Thank you.
ZhengLingyun
At 2013-07-16 08:16:09,"Ben Pfaff" <b...@nicira.com> wrote:
>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
