lib/util.c: Optimise bitwise_rscan.

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@gmail.com>
[blp@ovn.org enhanced the test]
Signed-off-by: Ben Pfaff <blp@ovn.org>

1 files changed, 102 insertions, 1 deletions

diff --git a/tests/test-util.c b/tests/test-util.c
index 8eedaf09e..ef459034e 100644
--- a/tests/test-util.c
+++ b/tests/test-util.c
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2011, 2012, 2013, 2014, 2015 Nicira, Inc.
+ * Copyright (c) 2011, 2012, 2013, 2014, 2015, 2016 Nicira, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -462,6 +462,106 @@ test_bitwise_is_all_zeros(struct ovs_cmdl_context *ctx OVS_UNUSED)
     }
 }
 
+static int
+trivial_bitwise_rscan(const void *p, unsigned int len, bool target,
+                      int start, int end)
+{
+    int ofs;
+
+    for (ofs = start; ofs > end; ofs--) {
+        if (bitwise_get_bit(p, len, ofs) == target) {
+            break;
+        }
+    }
+    return ofs;
+}
+
+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));
+
+    int n_loops;
+    for (n_loops = 0; n_loops < 100; n_loops++) {
+        ovs_be64 x = htonll(0);
+        int i;
+
+        for (i = 0; i < 64; i++) {
+            ovs_be64 bit;
+
+            /* Change a random 0-bit into a 1-bit. */
+            do {
+                bit = htonll(UINT64_C(1) << (random_range(64)));
+            } while (x & bit);
+            x |= bit;
+
+            for (int end = -1; end <= 63; end++) {
+                for (int start = end; start <= 63; start++) {
+                    for (int target = 0; target < 2; target++) {
+                        bool expect = trivial_bitwise_rscan(
+                            &x, sizeof x, target, start, end);
+                        bool answer = bitwise_rscan(
+                            &x, sizeof x, target, start, end);
+                        if (expect != answer) {
+                            fprintf(stderr,
+                                    "bitwise_rscan(0x%016"PRIx64",8,%s,%d,%d) "
+                                    "returned %s instead of %s\n",
+                                    ntohll(x),
+                                    target ? "true" : "false",
+                                    start, end,
+                                    answer ? "true" : "false",
+                                    expect ? "true" : "false");
+                            abort();
+                        }
+                    }
+                }
+            }
+        }
+    }
+}
+
 static void
 test_follow_symlinks(struct ovs_cmdl_context *ctx)
 {
@@ -1059,6 +1159,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},