diff options
author | Thomas Haller <thaller@redhat.com> | 2021-02-11 11:36:44 +0100 |
---|---|---|
committer | Thomas Haller <thaller@redhat.com> | 2021-02-11 13:00:18 +0100 |
commit | 24abf13239446d01e414e476bff2c78f64121d35 (patch) | |
tree | b98015bf19c41f750eacf24ea765f6348eb29290 | |
parent | 1cbe926c2048fa375aae9629217cf21ee2ebbc42 (diff) | |
download | NetworkManager-24abf13239446d01e414e476bff2c78f64121d35.tar.gz |
dhcp: binary search in nm_dhcp_option_find()
Let's use binary search.
Test patch:
diff --git a/src/core/dhcp/tests/test-dhcp-utils.c b/src/core/dhcp/tests/test-dhcp-utils.c
index 9b54e2cd0228..007993341672 100644
--- a/src/core/dhcp/tests/test-dhcp-utils.c
+++ b/src/core/dhcp/tests/test-dhcp-utils.c
@@ -788,6 +788,24 @@ NMTST_DEFINE();
int
main(int argc, char **argv)
{
+ int i;
+ guint idx;
+ guint c;
+
+ idx = 0;
+ c = 0;
+ for (i = 0; i < 1000000; i++) {
+ const guint option = _nm_dhcp_option_dhcp4_options[idx % G_N_ELEMENTS(_nm_dhcp_option_dhcp4_options)].option_num;
+
+ idx += 2010055757;
+
+ if (nm_dhcp_option_find(AF_INET, option)->name)
+ c++;
+ }
+ g_print(">%u\n", c);
+
+ return 0;
+
nmtst_init_assert_logging(&argc, &argv, "WARN", "DEFAULT");
g_test_add_func("/dhcp/generic-options", test_generic_options);
Build:
CFLAGS='-O2' ./autogen.sh --with-more-asserts=0
make -j 10 src/core/dhcp/tests/test-dhcp-utils && \
src/core/dhcp/tests/test-dhcp-utils && \
perf stat -r 200 -B src/core/dhcp/tests/test-dhcp-utils
Before:
Performance counter stats for 'src/core/dhcp/tests/test-dhcp-utils' (200 runs):
82.83 msec task-clock:u # 0.994 CPUs utilized ( +- 0.21% )
0 context-switches:u # 0.000 K/sec
0 cpu-migrations:u # 0.000 K/sec
579 page-faults:u # 0.007 M/sec ( +- 0.03% )
264,676,245 cycles:u # 3.195 GHz ( +- 0.06% )
544,792,266 instructions:u # 2.06 insn per cycle ( +- 0.00% )
151,624,848 branches:u # 1830.472 M/sec ( +- 0.00% )
1,083,780 branch-misses:u # 0.71% of all branches ( +- 0.01% )
0.083328 +- 0.000178 seconds time elapsed ( +- 0.21% )
After:
Performance counter stats for 'src/core/dhcp/tests/test-dhcp-utils' (200 runs):
39.21 msec task-clock:u # 0.987 CPUs utilized ( +- 0.57% )
0 context-switches:u # 0.000 K/sec
0 cpu-migrations:u # 0.000 K/sec
579 page-faults:u # 0.015 M/sec ( +- 0.03% )
115,396,123 cycles:u # 2.943 GHz ( +- 0.23% )
137,664,630 instructions:u # 1.19 insn per cycle ( +- 0.00% )
25,866,025 branches:u # 659.597 M/sec ( +- 0.00% )
1,919,616 branch-misses:u # 7.42% of all branches ( +- 0.12% )
0.039717 +- 0.000227 seconds time elapsed ( +- 0.57% )
-rw-r--r-- | src/core/dhcp/nm-dhcp-options.c | 172 |
1 files changed, 162 insertions, 10 deletions
diff --git a/src/core/dhcp/nm-dhcp-options.c b/src/core/dhcp/nm-dhcp-options.c index a8b27ddb8d..3537cd147e 100644 --- a/src/core/dhcp/nm-dhcp-options.c +++ b/src/core/dhcp/nm-dhcp-options.c @@ -7,6 +7,8 @@ #include "nm-dhcp-options.h" +#include "nm-glib-aux/nm-str-buf.h" + /*****************************************************************************/ #define REQ(_num, _name, _include) \ @@ -169,6 +171,23 @@ const NMDhcpOption _nm_dhcp_option_dhcp4_options[] = { REQ(NM_DHCP_OPTION_DHCP4_NM_NEXT_SERVER, "next_server", FALSE), }; +static const NMDhcpOption *const _sorted_options_4[G_N_ELEMENTS(_nm_dhcp_option_dhcp4_options)] = { +#define A(idx) (&_nm_dhcp_option_dhcp4_options[(idx)]) + A(0), A(1), A(8), A(18), A(19), A(2), A(20), A(21), A(22), A(23), A(24), A(3), + A(25), A(26), A(4), A(27), A(17), A(28), A(29), A(30), A(31), A(32), A(33), A(34), + A(35), A(5), A(36), A(6), A(37), A(38), A(39), A(40), A(9), A(41), A(42), A(43), + A(44), A(45), A(46), A(10), A(11), A(12), A(47), A(48), A(49), A(50), A(51), A(52), + A(13), A(53), A(54), A(55), A(57), A(58), A(59), A(60), A(61), A(62), A(63), A(64), + A(65), A(66), A(67), A(68), A(69), A(70), A(71), A(72), A(73), A(74), A(75), A(76), + A(77), A(78), A(79), A(80), A(81), A(82), A(83), A(84), A(85), A(86), A(87), A(56), + A(88), A(89), A(90), A(91), A(92), A(93), A(14), A(7), A(94), A(95), A(96), A(97), + A(98), A(99), A(100), A(101), A(102), A(103), A(104), A(105), A(106), A(107), A(108), A(109), + A(110), A(111), A(112), A(113), A(114), A(115), A(116), A(117), A(118), A(119), A(120), A(121), + A(122), A(123), A(124), A(125), A(126), A(127), A(128), A(129), A(130), A(131), A(132), A(133), + A(134), A(15), A(135), A(136), A(16), A(137), A(138), A(139), A(140), A(141), +#undef A +}; + const NMDhcpOption _nm_dhcp_option_dhcp6_options[] = { REQ(NM_DHCP_OPTION_DHCP6_CLIENTID, "dhcp6_client_id", FALSE), @@ -197,27 +216,160 @@ const NMDhcpOption _nm_dhcp_option_dhcp6_options[] = { #undef REQ -const NMDhcpOption * -nm_dhcp_option_find(int addr_family, guint option) +static const NMDhcpOption *const _sorted_options_6[G_N_ELEMENTS(_nm_dhcp_option_dhcp6_options)] = { +#define A(idx) (&_nm_dhcp_option_dhcp6_options[(idx)]) + A(0), + A(1), + A(2), + A(3), + A(4), + A(5), + A(6), + A(7), + A(8), + A(9), + A(10), + A(11), + A(12), + A(13), + A(14), + A(15), +#undef A +}; + +/*****************************************************************************/ + +static int +_sorted_options_generate_sort(gconstpointer pa, gconstpointer pb, gpointer user_data) +{ + const NMDhcpOption *const *a = pa; + const NMDhcpOption *const *b = pb; + + NM_CMP_DIRECT((*a)->option_num, (*b)->option_num); + return nm_assert_unreachable_val(0); +} + +static char * +_sorted_options_generate(const NMDhcpOption *base, const NMDhcpOption *const *sorted, guint n) +{ + gs_free const NMDhcpOption **sort2 = NULL; + NMStrBuf sbuf = NM_STR_BUF_INIT(0, FALSE); + guint i; + + sort2 = nm_memdup(sorted, n * sizeof(sorted[0])); + + g_qsort_with_data(sort2, n, sizeof(sort2[0]), _sorted_options_generate_sort, NULL); + + for (i = 0; i < n; i++) { + if (i > 0) + nm_str_buf_append(&sbuf, ", "); + nm_str_buf_append_printf(&sbuf, "A(%d)", (int) (sort2[i] - base)); + } + + return nm_str_buf_finalize(&sbuf, NULL); +} + +_nm_unused static void +_ASSERT_sorted(int IS_IPv4, const NMDhcpOption *const *const sorted, int n) + { - const int IS_IPv4 = NM_IS_IPv4(addr_family); const NMDhcpOption *const options = IS_IPv4 ? _nm_dhcp_option_dhcp4_options : _nm_dhcp_option_dhcp6_options; - int n_options = IS_IPv4 ? G_N_ELEMENTS(_nm_dhcp_option_dhcp4_options) - : G_N_ELEMENTS(_nm_dhcp_option_dhcp6_options); - int i; + int i; + int j; + gs_free char *sorted_msg = NULL; - for (i = 0; i < n_options; i++) { - const NMDhcpOption *opt = &options[i]; + for (i = 0; i < n; i++) { + const NMDhcpOption *opt = sorted[i]; + + g_assert(opt); + g_assert(opt >= options); + g_assert(opt < &options[n]); + + for (j = 0; j < i; j++) { + const NMDhcpOption *opt2 = sorted[j]; + + if (opt == opt2) { + g_error("%s:%d: the _sorted_options_%c at [%d] (opt=%u, %s) is duplicated at " + "[%d] (SORT: %s)", + __FILE__, + __LINE__, + IS_IPv4 ? '4' : '6', + i, + opt->option_num, + opt->name, + j, + (sorted_msg = _sorted_options_generate(options, sorted, n))); + } + } - if (opt->option_num == option) - return opt; + if (i > 0) { + const NMDhcpOption *opt2 = sorted[i - 1]; + + if (opt2->option_num >= opt->option_num) { + g_error("%s:%d: the _sorted_options_%c at [%d] (opt=%u, %s) should come before " + "[%d] (opt=%u, %s) (SORT: %s)", + __FILE__, + __LINE__, + IS_IPv4 ? '4' : '6', + i, + opt->option_num, + opt->name, + i - 1, + opt2->option_num, + opt2->name, + (sorted_msg = _sorted_options_generate(options, sorted, n))); + } + } + } +} + +/*****************************************************************************/ + +const NMDhcpOption * +nm_dhcp_option_find(int addr_family, guint option) +{ + const int IS_IPv4 = NM_IS_IPv4(addr_family); + const NMDhcpOption *const *const sorted = IS_IPv4 ? _sorted_options_4 : _sorted_options_6; + const int n = IS_IPv4 ? G_N_ELEMENTS(_nm_dhcp_option_dhcp4_options) + : G_N_ELEMENTS(_nm_dhcp_option_dhcp6_options); + int imin = 0; + int imax = n - 1; + int imid = (n - 1) / 2; + +#if NM_MORE_ASSERTS > 10 + nm_assert(n < G_MAXINT / 2); + if (IS_IPv4 && !NM_MORE_ASSERT_ONCE(10)) { + /* already checked */ + } else if (!IS_IPv4 && !NM_MORE_ASSERT_ONCE(10)) { + /* already checked */ + } else + _ASSERT_sorted(IS_IPv4, sorted, n); +#endif + + for (;;) { + const guint o = sorted[imid]->option_num; + + if (G_UNLIKELY(o == option)) + return sorted[imid]; + + if (o < option) + imin = imid + 1; + else + imax = imid - 1; + + if (G_UNLIKELY(imin > imax)) + break; + + imid = (imin + imax) / 2; } /* Option should always be found */ return nm_assert_unreachable_val(NULL); } +/*****************************************************************************/ + void nm_dhcp_option_take_option(GHashTable *options, int addr_family, guint option, char *value) { |