[ovs-dev] [PATCH v2] lib/util.c: Optimise bitwise_rscan.

[Han Zhou]

bitwise_rscan() is found to be hot spot in ovn-controller during OVN
scalability tests. It is triggered by lflow_run() when processing
lflow updates from SB ovsdb. The perf result shows:

+  35.90%  ovn-controller  ovn-controller      [.] bitwise_rscan
+  13.39%  ovn-controller  [kernel.kallsyms]   [k] 0xffffffff8104f45a
+   5.02%  ovn-controller  libc-2.19.so        [.] _int_malloc
+   3.47%  ovn-controller  libc-2.19.so        [.] _int_free

After optimization, bitwise_rscan percentage dropped from 36% to less
than 6%:

+  11.34%  ovn-controller  [kernel.kallsyms]   [k] 0xffffffff8104f45a
+   8.15%  ovn-controller  libc-2.19.so        [.] _int_malloc
+   5.77%  ovn-controller  ovn-controller      [.] bitwise_rscan
+   5.49%  ovn-controller  libc-2.19.so        [.] _int_free

Signed-off-by: Han Zhou <zhouhan at gmail.com>
---

Notes:
    v1->v2:
        - Refactor code and fixed a bug in v1
        - Unit test

 lib/util.c        | 37 ++++++++++++++++++++++++++++++++++---
 tests/library.at  |  1 +
 tests/test-util.c | 49 +++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 84 insertions(+), 3 deletions(-)

diff --git a/lib/util.c b/lib/util.c
index f06dee5..d8d4cc9 100644
--- a/lib/util.c
+++ b/lib/util.c
@@ -1400,14 +1400,45 @@ bitwise_scan(const void *p, unsigned int len, bool target, unsigned int start,
 int
 bitwise_rscan(const void *p, unsigned int len, bool target, int start, int end)
 {
+    const uint8_t *s = p;
+    int start_byte = len - (start / 8 + 1);
+    int end_byte = len - (end / 8 + 1);
+    int ofs_byte;
     int ofs;
+    uint8_t the_byte;
 
-    for (ofs = start; ofs > end; ofs--) {
-        if (bitwise_get_bit(p, len, ofs) == target) {
+    /* Find the target in the start_byte from starting offset */
+    ofs_byte = start_byte;
+    the_byte = s[ofs_byte];
+    for (ofs = start % 8; ofs >= 0; ofs--) {
+        if (((the_byte & (1u << ofs)) != 0) == target) {
             break;
         }
     }
-    return ofs;
+    if (ofs < 0) {
+        /* Target not found in start byte, continue searching byte by byte */
+        for (ofs_byte = start_byte + 1; ofs_byte <= end_byte; ofs_byte++) {
+            if ((target && s[ofs_byte])
+                    || (!target && (s[ofs_byte] != 0xff))) {
+               break;
+            }
+        }
+        if (ofs_byte > end_byte) {
+            return end;
+        }
+        the_byte = s[ofs_byte];
+        /* Target is in the_byte, find it bit by bit */
+        for (ofs = 7; ofs >= 0; ofs--) {
+            if (((the_byte & (1u << ofs)) != 0) == target) {
+                break;
+            }
+        }
+    }
+    int ret = (len - ofs_byte) * 8 - (8 - ofs);
+    if (ret < end) {
+        return end;
+    }
+    return ret;
 }
 
 /* Copies the 'n_bits' low-order bits of 'value' into the 'n_bits' bits
diff --git a/tests/library.at b/tests/library.at
index d82113f..4094348 100644
--- a/tests/library.at
+++ b/tests/library.at
@@ -129,6 +129,7 @@ m4_foreach(
    [bitwise_zero],
    [bitwise_one],
    [bitwise_is_all_zeros],
+   [bitwise_rscan],
    [ovs_scan]],
   [AT_SETUP([testname[()] function])
    AT_KEYWORDS([testname])
diff --git a/tests/test-util.c b/tests/test-util.c
index 8eedaf0..88d7cba 100644
--- a/tests/test-util.c
+++ b/tests/test-util.c
@@ -463,6 +463,54 @@ test_bitwise_is_all_zeros(struct ovs_cmdl_context *ctx OVS_UNUSED)
 }
 
 static void
+test_bitwise_rscan(struct ovs_cmdl_context *ctx OVS_UNUSED)
+{
+    /* All 1s */
+    uint8_t s1[3] = {0xff, 0xff, 0xff};
+    /* Target is the first bit */
+    ovs_assert(23 == bitwise_rscan(s1, 3, 1, 23, -1));
+    /* Target is not found, return -1 */
+    ovs_assert(-1 == bitwise_rscan(s1, 3, 0, 23, -1));
+    /* Target is not found and end != -1, return end */
+    ovs_assert(20 == bitwise_rscan(s1, 3, 0, 23, 20));
+
+    /* bit 20 - 23 are 0s */
+    uint8_t s2[3] = {0x0f, 0xff, 0xff};
+    /* Target is in the first byte but not the first bit */
+    ovs_assert(19 == bitwise_rscan(s2, 3, 1, 23, -1));
+    /* Target exists before the start postion */
+    ovs_assert(18 == bitwise_rscan(s2, 3, 1, 18, -1));
+    /* Target exists after the end postion, return end */
+    ovs_assert(20 == bitwise_rscan(s2, 3, 1, 23, 20));
+    /* Target is at the end postion, return end */
+    ovs_assert(19 == bitwise_rscan(s2, 3, 1, 23, 19));
+    /* start == end, target at start */
+    ovs_assert(19 == bitwise_rscan(s2, 3, 1, 19, 19));
+    /* start == end, target not at start */
+    ovs_assert(20 == bitwise_rscan(s2, 3, 1, 20, 20));
+    /* Target is 0 ... */
+    ovs_assert(22 == bitwise_rscan(s2, 3, 0, 22, -1));
+
+    /* bit 4 - 23 are 0s */
+    uint8_t s3[3] = {0x00, 0x00, 0x0f};
+    /* Target is in the end byte */
+    ovs_assert(3 == bitwise_rscan(s3, 3, 1, 16, -1));
+    /* Target exists after the end byte, return end */
+    ovs_assert(15 == bitwise_rscan(s3, 3, 1, 23, 15));
+    /* Target exists in end byte but after the end bit, return end */
+    ovs_assert(4 == bitwise_rscan(s3, 3, 1, 23, 4));
+    /* Target is 0 ... */
+    ovs_assert(12 == bitwise_rscan(s3, 3, 0, 12, -1));
+
+    /* All 0s */
+    uint8_t s4[3] = {0x00, 0x00, 0x00};
+    /* Target not found */
+    ovs_assert(-1 == bitwise_rscan(s4, 3, 1, 23, -1));
+    /* Target is 0 ..., start is 0 */
+    ovs_assert(0 == bitwise_rscan(s4, 3, 0, 0, -1));
+}
+
+static void
 test_follow_symlinks(struct ovs_cmdl_context *ctx)
 {
     int i;
@@ -1059,6 +1107,7 @@ static const struct ovs_cmdl_command commands[] = {
     {"bitwise_zero", NULL, 0, 0, test_bitwise_zero},
     {"bitwise_one", NULL, 0, 0, test_bitwise_one},
     {"bitwise_is_all_zeros", NULL, 0, 0, test_bitwise_is_all_zeros},
+    {"bitwise_rscan", NULL, 0, 0, test_bitwise_rscan},
     {"follow-symlinks", NULL, 1, INT_MAX, test_follow_symlinks},
     {"assert", NULL, 0, 0, test_assert},
     {"ovs_scan", NULL, 0, 0, test_ovs_scan},
-- 
2.1.0