From 76adea871d0d76674a5e030c83c7edc8d6b37e7d Mon Sep 17 00:00:00 2001 From: Han Zhou Date: Sun, 20 Mar 2016 00:08:48 -0700 Subject: 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 [blp@ovn.org enhanced the test] Signed-off-by: Ben Pfaff --- tests/test-util.c | 103 +++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 102 insertions(+), 1 deletion(-) (limited to 'tests/test-util.c') 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}, -- cgit v1.2.1