[ovs-dev] [PATCH] Fix hindex iteration incomplete bug

ZhengLingyun konghuarukhr at 163.com
Tue Jul 16 10:46:22 UTC 2013


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" <blp at 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 <konghuarukhr at 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 <konghuarukhr at 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 <konghuarukhr at 163.com>
>[blp at nicira.com changed how hindex_head_node() is implemented and
> other code details]
>Signed-off-by: Ben Pfaff <blp at 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openvswitch.org/pipermail/ovs-dev/attachments/20130716/76348202/attachment-0003.html>


More information about the dev mailing list