From e709dc09e61c4604821d10b81604d38616b81a0b Mon Sep 17 00:00:00 2001 From: "Ondrej Zajicek (work)" Date: Tue, 21 Apr 2020 13:49:29 +0200 Subject: Filter: Improve prefix trie tests Add tests explicitly matching insides and outsides of trie and update tests to do testing of both IPv4 and IPv6 tries. --- test/birdtest.c | 6 ++++++ 1 file changed, 6 insertions(+) (limited to 'test/birdtest.c') diff --git a/test/birdtest.c b/test/birdtest.c index a1da078f..d739e78b 100644 --- a/test/birdtest.c +++ b/test/birdtest.c @@ -501,6 +501,12 @@ bt_fmt_ipa(char *buf, size_t size, const void *data) bsnprintf(buf, size, "(null)"); } +void +bt_format_net(char *buf, size_t size, const void *data) +{ + bsnprintf(buf, size, "%N", (const net_addr *) data); +} + int bt_is_char(byte c) { -- cgit v1.2.3 From 067f69a56de0e0e61d423ec5aa68095aa28e3124 Mon Sep 17 00:00:00 2001 From: "Ondrej Zajicek (work)" Date: Sat, 25 Sep 2021 16:00:30 +0200 Subject: Filter: Add prefix trie benchmarks Add trie tests intended as benchmarks that use external datasets instead of generated prefixes. As datasets are not included, they are commented out by default. --- filter/trie_test.c | 235 +++++++++++++++++++++++++++++++++++++++++++++++++++++ test/birdtest.c | 6 ++ test/birdtest.h | 1 + 3 files changed, 242 insertions(+) (limited to 'test/birdtest.c') diff --git a/filter/trie_test.c b/filter/trie_test.c index 6418427e..3e8ce84d 100644 --- a/filter/trie_test.c +++ b/filter/trie_test.c @@ -16,7 +16,10 @@ #define TESTS_NUM 10 #define PREFIXES_NUM 32 #define PREFIX_TESTS_NUM 10000 +#define PREFIX_BENCH_NUM 100000000 +#define TRIE_BUFFER_SIZE 1024 +#define TEST_BUFFER_SIZE (1024*1024) #define BIG_BUFFER_SIZE 10000 /* Wrapping structure for storing f_prefixes structures in list */ @@ -266,6 +269,142 @@ make_trie_from_prefix_list(linpool *lp, list *prefixes) return trie; } +/* + * Read sequence of prefixes from file handle and return prefix list. + * Each prefix is on one line, sequence terminated by empty line or eof. + * Arg @plus means prefix should include all longer ones. + */ +static list * +read_prefix_list(linpool *lp, FILE *f, int v6, int plus) +{ + ASSERT(!v6); + + uint a0, a1, a2, a3, pl; + char s[32]; + int n; + + list *pxlist = lp_allocz(lp, sizeof(struct f_prefix_node)); + init_list(pxlist); + + errno = 0; + while (fgets(s, 32, f)) + { + if (s[0] == '\n') + return pxlist; + + n = sscanf(s, "%u.%u.%u.%u/%u", &a0, &a1, &a2, &a3, &pl); + + if (n != 5) + bt_abort_msg("Invalid content of trie_data"); + + struct f_prefix_node *px = lp_allocz(lp, sizeof(struct f_prefix_node)); + net_fill_ip4(&px->prefix.net, ip4_build(a0, a1, a2, a3), pl); + px->prefix.lo = pl; + px->prefix.hi = plus ? IP4_MAX_PREFIX_LENGTH : pl; + add_tail(pxlist, &px->n); + + char buf[64]; + bt_format_net(buf, 64, &px->prefix.net); + bt_debug("ADD %s{%d,%d}\n", buf, px->prefix.lo, px->prefix.hi); + } + + bt_syscall(errno, "fgets()"); + return EMPTY_LIST(*pxlist) ? NULL : pxlist; +} + +/* + * Open file, read multiple sequences of prefixes from it. Fill @data with + * prefix lists and @trie with generated tries. Return number of sequences / + * tries. Use separate linpool @lp0 for prefix lists and @lp1 for tries. + * Arg @plus means prefix should include all longer ones. + */ +static int +read_prefix_file(const char *filename, int plus, + linpool *lp0, linpool *lp1, + list *data[], struct f_trie *trie[]) +{ + FILE *f = fopen(filename, "r"); + bt_syscall(!f, "fopen(%s)", filename); + + int n = 0; + list *pxlist; + while (pxlist = read_prefix_list(lp0, f, 0, plus)) + { + data[n] = pxlist; + trie[n] = make_trie_from_prefix_list(lp1, pxlist); + bt_debug("NEXT\n"); + n++; + } + + fclose(f); + bt_debug("DONE reading %d tries\n", n); + + return n; +} + +/* + * Select random subset of @dn prefixes from prefix list @src of length @sn, + * and store them to buffer @dst (of size @dn). Prefixes may be chosen multiple + * times. Randomize order of prefixes in @dst buffer. + */ +static void +select_random_prefix_subset(list *src[], net_addr dst[], int sn, int dn) +{ + int pn = 0; + + if (!dn) + return; + + /* Compute total prefix number */ + for (int i = 0; i < sn; i++) + pn += list_length(src[i]); + + /* Change of selecting a prefix */ + int rnd = (pn / dn) + 10; + int n = 0; + + /* Iterate indefinitely over src array */ + for (int i = 0; 1; i++, i = (i < sn) ? i : 0) + { + struct f_prefix_node *px; + WALK_LIST(px, *src[i]) + { + if (xrandom(rnd) != 0) + continue; + + net_copy(&dst[n], &px->prefix.net); + n++; + + /* We have enough */ + if (n == dn) + goto done; + } + } + +done: + /* Shuffle networks */ + for (int i = 0; i < dn; i++) + { + int j = xrandom(dn); + + if (i == j) + continue; + + net_addr tmp; + net_copy(&tmp, &dst[i]); + net_copy(&dst[i], &dst[j]); + net_copy(&dst[j], &tmp); + } +} + +/* Fill @dst buffer with @dn randomly generated /32 prefixes */ +static void +make_random_addresses(net_addr dst[], int dn) +{ + for (int i = 0; i < dn; i++) + net_fill_ip4(&dst[i], ip4_from_u32((u32) bt_random()), IP4_MAX_PREFIX_LENGTH); +} + static void test_match_net(list *prefixes, struct f_trie *trie, const net_addr *net) { @@ -371,6 +510,99 @@ t_match_outer_net(void) return 1; } +/* + * Read prefixes from @filename, build set of tries, prepare test data and do + * PREFIX_BENCH_NUM trie lookups. With @plus = 0, use random subset of known + * prefixes as test data, with @plus = 1, use randomly generated /32 prefixes + * as test data. + */ +static int +benchmark_trie_dataset(const char *filename, int plus) +{ + int n = 0; + linpool *lp0 = lp_new_default(&root_pool); + linpool *lp1 = lp_new_default(&root_pool); + list *data[TRIE_BUFFER_SIZE]; + struct f_trie *trie[TRIE_BUFFER_SIZE]; + net_addr *nets; + + bt_reset_suite_case_timer(); + bt_log_suite_case_result(1, "Reading %s", filename, n); + n = read_prefix_file(filename, plus, lp0, lp1, data, trie); + bt_log_suite_case_result(1, "Read prefix data, %d lists, ", n); + + size_t trie_size = rmemsize(lp1) * 1000 / (1024*1024); + bt_log_suite_case_result(1, "Trie size %u.%03u MB", + (uint) (trie_size / 1000), (uint) (trie_size % 1000)); + + int t = PREFIX_BENCH_NUM / n; + int tb = MIN(t, TEST_BUFFER_SIZE); + nets = lp_alloc(lp0, tb * sizeof(net_addr)); + + if (!plus) + select_random_prefix_subset(data, nets, n, tb); + else + make_random_addresses(nets, tb); + + bt_log_suite_case_result(1, "Make test data, %d (%d) tests", t, tb); + bt_reset_suite_case_timer(); + + /* + int match = 0; + for (int i = 0; i < t; i++) + for (int j = 0; j < n; j++) + test_match_net(data[j], trie[j], &nets[i]); + */ + + int match = 0; + for (int i = 0; i < t; i++) + for (int j = 0; j < n; j++) + if (trie_match_net(trie[j], &nets[i % TEST_BUFFER_SIZE])) + match++; + + bt_log_suite_case_result(1, "Matching done, %d / %d matches", match, t * n); + + rfree(lp0); + rfree(lp1); + + return 1; +} + +static int UNUSED +t_bench_trie_datasets_subset(void) +{ + bt_bird_init(); + bt_config_parse(BT_CONFIG_SIMPLE); + + /* Specific datasets, not included */ + benchmark_trie_dataset("trie-data-bgp-1", 0); + benchmark_trie_dataset("trie-data-bgp-10", 0); + benchmark_trie_dataset("trie-data-bgp-100", 0); + benchmark_trie_dataset("trie-data-bgp-1000", 0); + + bt_bird_cleanup(); + + return 1; +} + +static int UNUSED +t_bench_trie_datasets_random(void) +{ + bt_bird_init(); + bt_config_parse(BT_CONFIG_SIMPLE); + + /* Specific datasets, not included */ + benchmark_trie_dataset("trie-data-bgp-1", 1); + benchmark_trie_dataset("trie-data-bgp-10", 1); + benchmark_trie_dataset("trie-data-bgp-100", 1); + benchmark_trie_dataset("trie-data-bgp-1000", 1); + + bt_bird_cleanup(); + + return 1; +} + + static int t_trie_same(void) { @@ -411,5 +643,8 @@ main(int argc, char *argv[]) bt_test_suite(t_match_outer_net, "Testing random outer prefix matching"); bt_test_suite(t_trie_same, "A trie filled forward should be same with a trie filled backward."); + // bt_test_suite(t_bench_trie_datasets_subset, "Benchmark tries from datasets by random subset of nets"); + // bt_test_suite(t_bench_trie_datasets_random, "Benchmark tries from datasets by generated addresses"); + return bt_exit_value(); } diff --git a/test/birdtest.c b/test/birdtest.c index d739e78b..053954e1 100644 --- a/test/birdtest.c +++ b/test/birdtest.c @@ -309,6 +309,12 @@ bt_log_suite_case_result(int result, const char *fmt, ...) } } +void +bt_reset_suite_case_timer(void) +{ + clock_gettime(CLOCK_MONOTONIC, &bt_suite_case_begin); +} + int bt_test_suite_base(int (*fn)(const void *), const char *id, const void *fn_arg, int forked, int timeout, const char *dsc, ...) { diff --git a/test/birdtest.h b/test/birdtest.h index 7a0c2fc4..ad5f8f9c 100644 --- a/test/birdtest.h +++ b/test/birdtest.h @@ -32,6 +32,7 @@ extern const char *bt_test_id; void bt_init(int argc, char *argv[]); int bt_exit_value(void); +void bt_reset_suite_case_timer(void); int bt_test_suite_base(int (*test_fn)(const void *), const char *test_id, const void *test_fn_argument, int forked, int timeout, const char *dsc, ...); static inline u64 bt_random(void) { return ((u64) random() & 0xffffffff) | ((u64) random() << 32); } -- cgit v1.2.3 From 14fc24f3a53ebc5525b854ccdc93274aa74a400f Mon Sep 17 00:00:00 2001 From: "Ondrej Zajicek (work)" Date: Fri, 26 Nov 2021 03:26:36 +0100 Subject: Trie: Implement longest-prefix-match queries and walks The prefix trie now supports longest-prefix-match query by function trie_match_longest_ipX() and it can be extended to iteration over all covering prefixes for a given prefix (from longest to shortest) using TRIE_WALK_TO_ROOT_IPx() macro. --- filter/data.h | 51 ++++++++++++++ filter/trie.c | 190 ++++++++++++++++++++++++++++++++++++++++++++++++++++- filter/trie_test.c | 115 ++++++++++++++++++++++++++++++++ test/birdtest.c | 5 +- 4 files changed, 359 insertions(+), 2 deletions(-) (limited to 'test/birdtest.c') diff --git a/filter/data.h b/filter/data.h index 4a0ee865..28c7a888 100644 --- a/filter/data.h +++ b/filter/data.h @@ -196,11 +196,61 @@ void tree_walk(const struct f_tree *t, void (*hook)(const struct f_tree *, void struct f_trie *f_new_trie(linpool *lp, uint data_size); void *trie_add_prefix(struct f_trie *t, const net_addr *n, uint l, uint h); int trie_match_net(const struct f_trie *t, const net_addr *n); +int trie_match_longest_ip4(const struct f_trie *t, const net_addr_ip4 *net, net_addr_ip4 *dst, ip4_addr *found0); +int trie_match_longest_ip6(const struct f_trie *t, const net_addr_ip6 *net, net_addr_ip6 *dst, ip6_addr *found0); void trie_walk_init(struct f_trie_walk_state *s, const struct f_trie *t, const net_addr *from); int trie_walk_next(struct f_trie_walk_state *s, net_addr *net); int trie_same(const struct f_trie *t1, const struct f_trie *t2); void trie_format(const struct f_trie *t, buffer *buf); +static inline int +trie_match_next_longest_ip4(net_addr_ip4 *n, ip4_addr *found) +{ + while (n->pxlen) + { + n->pxlen--; + ip4_clrbit(&n->prefix, n->pxlen); + + if (ip4_getbit(*found, n->pxlen)) + return 1; + } + + return 0; +} + +static inline int +trie_match_next_longest_ip6(net_addr_ip6 *n, ip6_addr *found) +{ + while (n->pxlen) + { + n->pxlen--; + ip6_clrbit(&n->prefix, n->pxlen); + + if (ip6_getbit(*found, n->pxlen)) + return 1; + } + + return 0; +} + + +#define TRIE_WALK_TO_ROOT_IP4(trie, net, dst) ({ \ + net_addr_ip4 dst; \ + ip4_addr _found; \ + for (int _n = trie_match_longest_ip4(trie, net, &dst, &_found); \ + _n; \ + _n = trie_match_next_longest_ip4(&dst, &_found)) + +#define TRIE_WALK_TO_ROOT_IP6(trie, net, dst) ({ \ + net_addr_ip6 dst; \ + ip6_addr _found; \ + for (int _n = trie_match_longest_ip6(trie, net, &dst, &_found); \ + _n; \ + _n = trie_match_next_longest_ip6(&dst, &_found)) + +#define TRIE_WALK_TO_ROOT_END }) + + #define TRIE_WALK(trie, net, from) ({ \ net_addr net; \ struct f_trie_walk_state tws_; \ @@ -209,6 +259,7 @@ void trie_format(const struct f_trie *t, buffer *buf); #define TRIE_WALK_END }) + #define F_CMP_ERROR 999 const char *f_type_name(enum f_type t); diff --git a/filter/trie.c b/filter/trie.c index 21b5b5d7..66b56297 100644 --- a/filter/trie.c +++ b/filter/trie.c @@ -85,7 +85,7 @@ * * Iteration over prefixes in a trie can be done using TRIE_WALK() macro, or * directly using trie_walk_init() and trie_walk_next() functions. The second - * approeach allows suspending the iteration and continuing in it later. + * approach allows suspending the iteration and continuing in it later. * Prefixes are enumerated in the usual lexicographic order and may be * restricted to a subset of the trie (all subnets of a specified prefix). * @@ -100,6 +100,13 @@ * path between the current node and its parent node, stored in the bitmap * &accept of the current node) and &local_pos for iteration over intra-node * prefixes (stored in the bitmap &local). + * + * The trie also supports longest-prefix-match query by trie_match_longest_ip4() + * and it can be extended to iteration over all covering prefixes for a given + * prefix (from longest to shortest) using TRIE_WALK_TO_ROOT_IP4() macro. There + * are also IPv6 versions (for practical reasons, these functions and macros are + * separate for IPv4 and IPv6). There is the same limitation to enumeration of + * `implicit' prefixes like with the previous TRIE_WALK() macro. */ #include "nest/bird.h" @@ -541,6 +548,187 @@ trie_match_net(const struct f_trie *t, const net_addr *n) } +/** + * trie_match_longest_ip4 + * @t: trie + * @net: net address + * @dst: return value + * @found0: optional returned bitmask of found nodes + * + * Perform longest prefix match for the address @net and return the resulting + * prefix in the buffer @dst. The bitmask @found0 is used to report lengths of + * prefixes on the path from the root to the resulting prefix. E.g., if there is + * also a /20 shorter matching prefix, then 20-th bit is set in @found0. This + * can be used to enumerate all matching prefixes for the network @net using + * function trie_match_next_longest_ip4() or macro TRIE_WALK_TO_ROOT_IP4(). + * + * This function assumes IPv4 trie, there is also an IPv6 variant. + * + * Result: 1 if a matching prefix was found, 0 if not. + */ +int +trie_match_longest_ip4(const struct f_trie *t, const net_addr_ip4 *net, net_addr_ip4 *dst, ip4_addr *found0) +{ + ASSERT(t->ipv4); + + const struct f_trie_node4 *n = &t->root.v4; + int len = 0; + + ip4_addr found = IP4_NONE; + int last = -1; + + while (n) + { + /* We are out of path */ + if (!ip4_prefix_equal(net->prefix, n->addr, MIN(net->pxlen, n->plen))) + goto done; + + /* Check accept mask */ + for (; len < n->plen; len++) + { + if (len > net->pxlen) + goto done; + + if (ip4_getbit(n->accept, len - 1)) + { + /* len is always < 32 due to len < n->plen */ + ip4_setbit(&found, len); + last = len; + } + } + + /* Special case for max length, there is only one valid local position */ + if (len == IP4_MAX_PREFIX_LENGTH) + { + if (n->local & (1u << 1)) + last = len; + + goto done; + } + + /* Check local mask */ + for (int pos = 1; pos < (1 << TRIE_STEP); pos = 2 * pos + ip4_getbit(net->prefix, len), len++) + { + if (len > net->pxlen) + goto done; + + if (n->local & (1u << pos)) + { + /* len is always < 32 due to special case above */ + ip4_setbit(&found, len); + last = len; + } + } + + /* Choose child */ + n = n->c[ip4_getbits(net->prefix, n->plen, TRIE_STEP)]; + } + +done: + if (last < 0) + return 0; + + net_copy_ip4(dst, net); + dst->prefix = ip4_and(dst->prefix, ip4_mkmask(last)); + dst->pxlen = last; + + if (found0) + *found0 = found; + + return 1; +} + + +/** + * trie_match_longest_ip6 + * @t: trie + * @net: net address + * @dst: return value + * @found0: optional returned bitmask of found nodes + * + * Perform longest prefix match for the address @net and return the resulting + * prefix in the buffer @dst. The bitmask @found0 is used to report lengths of + * prefixes on the path from the root to the resulting prefix. E.g., if there is + * also a /20 shorter matching prefix, then 20-th bit is set in @found0. This + * can be used to enumerate all matching prefixes for the network @net using + * function trie_match_next_longest_ip6() or macro TRIE_WALK_TO_ROOT_IP6(). + * + * This function assumes IPv6 trie, there is also an IPv4 variant. + * + * Result: 1 if a matching prefix was found, 0 if not. + */ +int +trie_match_longest_ip6(const struct f_trie *t, const net_addr_ip6 *net, net_addr_ip6 *dst, ip6_addr *found0) +{ + ASSERT(!t->ipv4); + + const struct f_trie_node6 *n = &t->root.v6; + int len = 0; + + ip6_addr found = IP6_NONE; + int last = -1; + + while (n) + { + /* We are out of path */ + if (!ip6_prefix_equal(net->prefix, n->addr, MIN(net->pxlen, n->plen))) + goto done; + + /* Check accept mask */ + for (; len < n->plen; len++) + { + if (len > net->pxlen) + goto done; + + if (ip6_getbit(n->accept, len - 1)) + { + /* len is always < 128 due to len < n->plen */ + ip6_setbit(&found, len); + last = len; + } + } + + /* Special case for max length, there is only one valid local position */ + if (len == IP6_MAX_PREFIX_LENGTH) + { + if (n->local & (1u << 1)) + last = len; + + goto done; + } + + /* Check local mask */ + for (int pos = 1; pos < (1 << TRIE_STEP); pos = 2 * pos + ip6_getbit(net->prefix, len), len++) + { + if (len > net->pxlen) + goto done; + + if (n->local & (1u << pos)) + { + /* len is always < 128 due to special case above */ + ip6_setbit(&found, len); + last = len; + } + } + + /* Choose child */ + n = n->c[ip6_getbits(net->prefix, n->plen, TRIE_STEP)]; + } + +done: + if (last < 0) + return 0; + + net_copy_ip6(dst, net); + dst->prefix = ip6_and(dst->prefix, ip6_mkmask(last)); + dst->pxlen = last; + + if (found0) + *found0 = found; + + return 1; +} + #define SAME_PREFIX(A,B,X,L) ((X) ? ip4_prefix_equal((A)->v4.addr, net4_prefix(B), (L)) : ip6_prefix_equal((A)->v6.addr, net6_prefix(B), (L))) #define GET_NET_BITS(N,X,A,B) ((X) ? ip4_getbits(net4_prefix(N), (A), (B)) : ip6_getbits(net6_prefix(N), (A), (B))) diff --git a/filter/trie_test.c b/filter/trie_test.c index bb9a2f26..eee48284 100644 --- a/filter/trie_test.c +++ b/filter/trie_test.c @@ -774,6 +774,120 @@ t_trie_walk(void) return 1; } +static int +find_covering_nets(struct f_prefix *prefixes, int num, const net_addr *net, net_addr *found) +{ + struct f_prefix key; + net_addr *n = &key.net; + int found_num = 0; + + net_copy(n, net); + + while (1) + { + struct f_prefix *px = + bsearch(&key, prefixes, num, sizeof(struct f_prefix), compare_prefixes); + + if (px) + { + net_copy(&found[found_num], n); + found_num++; + } + + if (n->pxlen == 0) + return found_num; + + n->pxlen--; + + if (n->type == NET_IP4) + ip4_clrbit(&((net_addr_ip4 *) n)->prefix, n->pxlen); + else + ip6_clrbit(&((net_addr_ip6 *) n)->prefix, n->pxlen); + } +} + +static int +t_trie_walk_to_root(void) +{ + bt_bird_init(); + bt_config_parse(BT_CONFIG_SIMPLE); + + linpool *lp = lp_new_default(&root_pool); + for (int round = 0; round < TESTS_NUM * 4; round++) + { + int level = round / TESTS_NUM; + int v6 = level % 2; + int num = PREFIXES_NUM * (int[]){32, 512}[level / 2]; + int pos = 0; + int st = 0, sn = 0, sm = 0; + + list *prefixes = make_random_prefix_list(lp, num, v6, 1); + struct f_trie *trie = make_trie_from_prefix_list(lp, prefixes); + struct f_prefix *pxset = malloc((num + 1) * sizeof(struct f_prefix)); + + struct f_prefix_node *pxn; + WALK_LIST(pxn, *prefixes) + pxset[pos++] = pxn->prefix; + memset(&pxset[pos], 0, sizeof (struct f_prefix)); + + qsort(pxset, num, sizeof(struct f_prefix), compare_prefixes); + + int i; + for (i = 0; i < (PREFIX_TESTS_NUM / 10); i++) + { + net_addr from; + get_random_net(&from, v6); + + net_addr found[129]; + int found_num = find_covering_nets(pxset, num, &from, found); + int n = 0; + + if (bt_verbose >= BT_VERBOSE_ABSOLUTELY_ALL) + { + char buf[64]; + bt_format_net(buf, 64, &from); + bt_debug("Lookup for %s (expect %d)\n", buf, found_num); + } + + /* Walk to root, separate for IPv4 and IPv6 */ + if (!v6) + { + TRIE_WALK_TO_ROOT_IP4(trie, (net_addr_ip4 *) &from, net) + { + log_networks((net_addr *) &net, &found[n]); + bt_assert((n < found_num) && net_equal((net_addr *) &net, &found[n])); + n++; + } + TRIE_WALK_TO_ROOT_END; + } + else + { + TRIE_WALK_TO_ROOT_IP6(trie, (net_addr_ip6 *) &from, net) + { + log_networks((net_addr *) &net, &found[n]); + bt_assert((n < found_num) && net_equal((net_addr *) &net, &found[n])); + n++; + } + TRIE_WALK_TO_ROOT_END; + } + + bt_assert(n == found_num); + + /* Stats */ + st += n; + sn += !!n; + sm = MAX(sm, n); + } + + bt_debug("Success in %d / %d, sum %d, max %d\n", sn, i, st, sm); + + lp_flush(lp); + } + + bt_bird_cleanup(); + return 1; +} + int main(int argc, char *argv[]) { @@ -784,6 +898,7 @@ main(int argc, char *argv[]) bt_test_suite(t_match_outer_net, "Testing random outer prefix matching"); bt_test_suite(t_trie_same, "A trie filled forward should be same with a trie filled backward."); bt_test_suite(t_trie_walk, "Testing TRIE_WALK() on random tries"); + bt_test_suite(t_trie_walk_to_root, "Testing TRIE_WALK_TO_ROOT() on random tries"); // bt_test_suite(t_bench_trie_datasets_subset, "Benchmark tries from datasets by random subset of nets"); // bt_test_suite(t_bench_trie_datasets_random, "Benchmark tries from datasets by generated addresses"); diff --git a/test/birdtest.c b/test/birdtest.c index 053954e1..6ad743ce 100644 --- a/test/birdtest.c +++ b/test/birdtest.c @@ -510,7 +510,10 @@ bt_fmt_ipa(char *buf, size_t size, const void *data) void bt_format_net(char *buf, size_t size, const void *data) { - bsnprintf(buf, size, "%N", (const net_addr *) data); + if (data) + bsnprintf(buf, size, "%N", (const net_addr *) data); + else + bsnprintf(buf, size, "(null)"); } int -- cgit v1.2.3