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 <[email protected]> --- 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 _______________________________________________ dev mailing list [email protected] http://openvswitch.org/mailman/listinfo/dev
