[prev in list] [next in list] [prev in thread] [next in thread] 

List:       openvswitch-dev
Subject:    [ovs-dev] [PATCH 3/3] bitmap: Optimize bitmap_equal and bitmap_scan
From:       blp () nicira ! com (Ben Pfaff)
Date:       2014-07-31 23:47:29
Message-ID: 20140731234729.GI11107 () nicira ! com
[Download RAW message or body]

On Thu, Jul 31, 2014 at 01:16:06PM +0800, Kmindg wrote:
> ovstest test-bitmap benchmark 100000 (without this commit):
> bitmap equal:     52 ms
> bitmap scan:    758 ms
> 
> ovstest test-bitmap benchmark 100000 (with this commit):
> bitmap equal:     37 ms
> bitmap scan:     34 ms
> 
> Tested on Intel Xeon E5-2620 v2 @ 2.10GHz
> 
> Signed-off-by: Kmindg <kmindg at gmail.com>

I'm pretty sure that this first check in bitmap_scan():
+    if (t && count) {
+        /* 'start' is not aligned to BITMAP_ULONG_BITS. */
+        v = *bitmap_unit__(bitmap, start) >> t;
+
+        idx = bitmap_scan__(v, target);
+        if (idx < BITMAP_ULONG_BITS - t) {
+            return idx + start;
+        }
+        count -= BITMAP_ULONG_BITS - t;
+        start += BITMAP_ULONG_BITS - t;
+    }
could cause bitmap_scan() to return a value greater than 'end'.

bitmap_scan() seems to use 't' for two very different purposes.  Please
use different variables for different purposes.

bitmap_scan() seems to return 'start' if it is unsuccessful, rather than
'end'.

These apparent bugs don't make me feel confident about the tests.

[prev in list] [next in list] [prev in thread] [next in thread]