filter/trie_test.c

   1 /*
   2  *      Filters: Utility Functions Tests
   3  *
   4  *      (c) 2015 CZ.NIC z.s.p.o.
   5  *
   6  *      Can be freely distributed and used under the terms of the GNU GPL.
   7  */
   8
   9 #include "test/birdtest.h"
  10 #include "test/bt-utils.h"
  11
  12 #include "filter/filter.h"
  13 #include "filter/data.h"
  14 #include "conf/conf.h"
  15
  16 #define TESTS_NUM               10
  17 #define PREFIXES_NUM            32
  18 #define PREFIX_TESTS_NUM        10000
  19 #define PREFIX_BENCH_NUM        100000000
  20
  21 #define TRIE_BUFFER_SIZE        1024
  22 #define TEST_BUFFER_SIZE        (1024*1024)
  23 #define BIG_BUFFER_SIZE         10000
  24
  25 /* Wrapping structure for storing f_prefixes structures in list */
  26 struct f_prefix_node {
  27   node n;
  28   struct f_prefix prefix;
  29 };
  30
  31 static u32
  32 xrandom(u32 max)
  33 {
  34   return (bt_random() % max);
  35 }
  36
  37 static inline uint
  38 get_exp_random(void)
  39 {
  40   uint r, n = 0;
  41
  42   for (r = bt_random(); r & 1; r = r >> 1)
  43     n++;
  44
  45   return n;
  46 }
  47
  48 static int
  49 compare_prefixes(const void *a, const void *b)
  50 {
  51   return net_compare(&((const struct f_prefix *) a)->net,
  52                      &((const struct f_prefix *) b)->net);
  53 }
  54
  55 static inline int
  56 matching_ip4_nets(const net_addr_ip4 *a, const net_addr_ip4 *b)
  57 {
  58   ip4_addr cmask = ip4_mkmask(MIN(a->pxlen, b->pxlen));
  59   return ip4_compare(ip4_and(a->prefix, cmask), ip4_and(b->prefix, cmask)) == 0;
  60 }
  61
  62 static inline int
  63 matching_ip6_nets(const net_addr_ip6 *a, const net_addr_ip6 *b)
  64 {
  65   ip6_addr cmask = ip6_mkmask(MIN(a->pxlen, b->pxlen));
  66   return ip6_compare(ip6_and(a->prefix, cmask), ip6_and(b->prefix, cmask)) == 0;
  67 }
  68
  69 static inline int
  70 matching_nets(const net_addr *a, const net_addr *b)
  71 {
  72   if (a->type != b->type)
  73     return 0;
  74
  75   return (a->type == NET_IP4) ?
  76     matching_ip4_nets((const net_addr_ip4 *) a, (const net_addr_ip4 *) b) :
  77     matching_ip6_nets((const net_addr_ip6 *) a, (const net_addr_ip6 *) b);
  78 }
  79
  80 static int
  81 is_prefix_included(list *prefixes, const net_addr *needle)
  82 {
  83   struct f_prefix_node *n;
  84   WALK_LIST(n, *prefixes)
  85     if (matching_nets(&n->prefix.net, needle) &&
  86         (n->prefix.lo <= needle->pxlen) && (needle->pxlen <= n->prefix.hi))
  87     {
  88       char buf[64];
  89       bt_format_net(buf, 64, &n->prefix.net);
  90       bt_debug("FOUND %s %d-%d\n", buf, n->prefix.lo, n->prefix.hi);
  91
  92       return 1; /* OK */
  93     }
  94
  95   return 0; /* FAIL */
  96 }
  97
  98 static void
  99 get_random_net(net_addr *net, int v6)
 100 {
 101   if (!v6)
 102   {
 103     uint pxlen = xrandom(24)+8;
 104     ip4_addr ip4 = ip4_from_u32((u32) bt_random());
 105     net_fill_ip4(net, ip4_and(ip4, ip4_mkmask(pxlen)), pxlen);
 106   }
 107   else
 108   {
 109     uint pxlen = xrandom(120)+8;
 110     ip6_addr ip6 = ip6_build(bt_random(), bt_random(), bt_random(), bt_random());
 111     net_fill_ip6(net, ip6_and(ip6, ip6_mkmask(pxlen)), pxlen);
 112   }
 113 }
 114
 115 static void
 116 get_random_prefix(struct f_prefix *px, int v6, int tight)
 117 {
 118   get_random_net(&px->net, v6);
 119
 120   if (tight)
 121   {
 122     px->lo = px->hi = px->net.pxlen;
 123   }
 124   else if (bt_random() % 2)
 125   {
 126     px->lo = 0;
 127     px->hi = px->net.pxlen;
 128   }
 129   else
 130   {
 131     px->lo = px->net.pxlen;
 132     px->hi = net_max_prefix_length[px->net.type];
 133   }
 134 }
 135
 136 static void
 137 get_random_ip4_subnet(net_addr_ip4 *net, const net_addr_ip4 *src, int pxlen)
 138 {
 139   *net = NET_ADDR_IP4(ip4_and(src->prefix, ip4_mkmask(pxlen)), pxlen);
 140
 141   if (pxlen > src->pxlen)
 142   {
 143     ip4_addr rnd = ip4_from_u32((u32) bt_random());
 144     ip4_addr mask = ip4_xor(ip4_mkmask(src->pxlen), ip4_mkmask(pxlen));
 145     net->prefix = ip4_or(net->prefix, ip4_and(rnd, mask));
 146   }
 147 }
 148
 149 static void
 150 get_random_ip6_subnet(net_addr_ip6 *net, const net_addr_ip6 *src, int pxlen)
 151 {
 152   *net = NET_ADDR_IP6(ip6_and(src->prefix, ip6_mkmask(pxlen)), pxlen);
 153
 154   if (pxlen > src->pxlen)
 155   {
 156     ip6_addr rnd = ip6_build(bt_random(), bt_random(), bt_random(), bt_random());
 157     ip6_addr mask = ip6_xor(ip6_mkmask(src->pxlen), ip6_mkmask(pxlen));
 158     net->prefix = ip6_or(net->prefix, ip6_and(rnd, mask));
 159   }
 160 }
 161
 162 static void
 163 get_random_subnet(net_addr *net, const net_addr *src, int pxlen)
 164 {
 165   if (src->type == NET_IP4)
 166     get_random_ip4_subnet((net_addr_ip4 *) net, (const net_addr_ip4 *) src, pxlen);
 167   else
 168     get_random_ip6_subnet((net_addr_ip6 *) net, (const net_addr_ip6 *) src, pxlen);
 169 }
 170
 171 static void
 172 get_inner_net(net_addr *net, const struct f_prefix *src)
 173 {
 174   int pxlen, step;
 175
 176   if (bt_random() % 2)
 177   {
 178     step = get_exp_random();
 179     step = MIN(step, src->hi - src->lo);
 180     pxlen = (bt_random() % 2) ? (src->lo + step) : (src->hi - step);
 181   }
 182   else
 183     pxlen = src->lo + bt_random() % (src->hi - src->lo + 1);
 184
 185   get_random_subnet(net, &src->net, pxlen);
 186 }
 187
 188 static void
 189 swap_random_bits_ip4(net_addr_ip4 *net, int num)
 190 {
 191   for (int i = 0; i < num; i++)
 192   {
 193     ip4_addr swap = IP4_NONE;
 194     ip4_setbit(&swap, bt_random() % net->pxlen);
 195     net->prefix = ip4_xor(net->prefix, swap);
 196   }
 197 }
 198
 199 static void
 200 swap_random_bits_ip6(net_addr_ip6 *net, int num)
 201 {
 202   for (int i = 0; i < num; i++)
 203   {
 204     ip6_addr swap = IP6_NONE;
 205     ip6_setbit(&swap, bt_random() % net->pxlen);
 206     net->prefix = ip6_xor(net->prefix, swap);
 207   }
 208 }
 209
 210 static void
 211 swap_random_bits(net_addr *net, int num)
 212 {
 213   if (net->type == NET_IP4)
 214     swap_random_bits_ip4((net_addr_ip4 *) net, num);
 215   else
 216     swap_random_bits_ip6((net_addr_ip6 *) net, num);
 217 }
 218
 219 static void
 220 get_outer_net(net_addr *net, const struct f_prefix *src)
 221 {
 222   int pxlen, step;
 223   int inside = 0;
 224   int max = net_max_prefix_length[src->net.type];
 225
 226   if ((src->lo > 0) && (bt_random() % 3))
 227   {
 228     step = 1 + get_exp_random();
 229     step = MIN(step, src->lo);
 230     pxlen = src->lo - step;
 231   }
 232   else if ((src->hi < max) && (bt_random() % 2))
 233   {
 234     step = 1 + get_exp_random();
 235     step = MIN(step, max - src->hi);
 236     pxlen = src->hi + step;
 237   }
 238   else
 239   {
 240     pxlen = src->lo + bt_random() % (src->hi - src->lo + 1);
 241     inside = 1;
 242   }
 243
 244   get_random_subnet(net, &src->net, pxlen);
 245
 246   /* Perhaps swap some bits in prefix */
 247   if ((net->pxlen > 0) && (inside || (bt_random() % 4)))
 248     swap_random_bits(net, 1 + get_exp_random());
 249 }
 250
 251 static list *
 252 make_random_prefix_list(linpool *lp, int num, int v6, int tight)
 253 {
 254   list *prefixes = lp_allocz(lp, sizeof(struct f_prefix_node));
 255   init_list(prefixes);
 256
 257   for (int i = 0; i < num; i++)
 258   {
 259     struct f_prefix_node *px = lp_allocz(lp, sizeof(struct f_prefix_node));
 260     get_random_prefix(&px->prefix, v6, tight);
 261     add_tail(prefixes, &px->n);
 262
 263     char buf[64];
 264     bt_format_net(buf, 64, &px->prefix.net);
 265     bt_debug("ADD %s{%d,%d}\n", buf, px->prefix.lo, px->prefix.hi);
 266   }
 267
 268   return prefixes;
 269 }
 270
 271 static struct f_trie *
 272 make_trie_from_prefix_list(linpool *lp, list *prefixes)
 273 {
 274   struct f_trie *trie = f_new_trie(lp, 0);
 275
 276   struct f_prefix_node *n;
 277   WALK_LIST(n, *prefixes)
 278     trie_add_prefix(trie, &n->prefix.net, n->prefix.lo, n->prefix.hi);
 279
 280   return trie;
 281 }
 282
 283 /*
 284  * Read sequence of prefixes from file handle and return prefix list.
 285  * Each prefix is on one line, sequence terminated by empty line or eof.
 286  * Arg @plus means prefix should include all longer ones.
 287  */
 288 static list *
 289 read_prefix_list(linpool *lp, FILE *f, int v6, int plus)
 290 {
 291   ASSERT(!v6);
 292
 293   uint a0, a1, a2, a3, pl;
 294   char s[32];
 295   int n;
 296
 297   list *pxlist = lp_allocz(lp, sizeof(struct f_prefix_node));
 298   init_list(pxlist);
 299
 300   errno = 0;
 301   while (fgets(s, 32, f))
 302   {
 303     if (s[0] == '\n')
 304       return pxlist;
 305
 306     n = sscanf(s, "%u.%u.%u.%u/%u", &a0, &a1, &a2, &a3, &pl);
 307
 308     if (n != 5)
 309       bt_abort_msg("Invalid content of trie_data");
 310
 311     struct f_prefix_node *px = lp_allocz(lp, sizeof(struct f_prefix_node));
 312     net_fill_ip4(&px->prefix.net, ip4_build(a0, a1, a2, a3), pl);
 313     px->prefix.lo = pl;
 314     px->prefix.hi = plus ? IP4_MAX_PREFIX_LENGTH : pl;
 315     add_tail(pxlist, &px->n);
 316
 317     char buf[64];
 318     bt_format_net(buf, 64, &px->prefix.net);
 319     bt_debug("ADD %s{%d,%d}\n", buf, px->prefix.lo, px->prefix.hi);
 320   }
 321
 322   bt_syscall(errno, "fgets()");
 323   return EMPTY_LIST(*pxlist) ? NULL : pxlist;
 324 }
 325
 326 /*
 327  * Open file, read multiple sequences of prefixes from it. Fill @data with
 328  * prefix lists and @trie with generated tries. Return number of sequences /
 329  * tries. Use separate linpool @lp0 for prefix lists and @lp1 for tries.
 330  * Arg @plus means prefix should include all longer ones.
 331  */
 332 static int
 333 read_prefix_file(const char *filename, int plus,
 334                  linpool *lp0, linpool *lp1,
 335                  list *data[], struct f_trie *trie[])
 336 {
 337   FILE *f = fopen(filename, "r");
 338   bt_syscall(!f, "fopen(%s)", filename);
 339
 340   int n = 0;
 341   list *pxlist;
 342   while (pxlist = read_prefix_list(lp0, f, 0, plus))
 343   {
 344     data[n] = pxlist;
 345     trie[n] = make_trie_from_prefix_list(lp1, pxlist);
 346     bt_debug("NEXT\n");
 347     n++;
 348   }
 349
 350   fclose(f);
 351   bt_debug("DONE reading %d tries\n", n);
 352
 353   return n;
 354 }
 355
 356 /*
 357  * Select random subset of @dn prefixes from prefix list @src of length @sn,
 358  * and store them to buffer @dst (of size @dn). Prefixes may be chosen multiple
 359  * times. Randomize order of prefixes in @dst buffer.
 360  */
 361 static void
 362 select_random_prefix_subset(list *src[], net_addr dst[], int sn, int dn)
 363 {
 364   int pn = 0;
 365
 366   if (!dn)
 367     return;
 368
 369   /* Compute total prefix number */
 370   for (int i = 0; i < sn; i++)
 371     pn += list_length(src[i]);
 372
 373   /* Change of selecting a prefix */
 374   int rnd = (pn / dn) + 10;
 375   int n = 0;
 376
 377   /* Iterate indefinitely over src array */
 378   for (int i = 0; 1; i++, i = (i < sn) ? i : 0)
 379   {
 380     struct f_prefix_node *px;
 381     WALK_LIST(px, *src[i])
 382     {
 383       if (xrandom(rnd) != 0)
 384         continue;
 385
 386       net_copy(&dst[n], &px->prefix.net);
 387       n++;
 388
 389       /* We have enough */
 390       if (n == dn)
 391         goto done;
 392     }
 393   }
 394
 395 done:
 396   /* Shuffle networks */
 397   for (int i = 0; i < dn; i++)
 398   {
 399     int j = xrandom(dn);
 400
 401     if (i == j)
 402       continue;
 403
 404     net_addr tmp;
 405     net_copy(&tmp, &dst[i]);
 406     net_copy(&dst[i], &dst[j]);
 407     net_copy(&dst[j], &tmp);
 408   }
 409 }
 410
 411 /* Fill @dst buffer with @dn randomly generated /32 prefixes */
 412 static void
 413 make_random_addresses(net_addr dst[], int dn)
 414 {
 415   for (int i = 0; i < dn; i++)
 416     net_fill_ip4(&dst[i], ip4_from_u32((u32) bt_random()), IP4_MAX_PREFIX_LENGTH);
 417 }
 418
 419 static void
 420 test_match_net(list *prefixes, struct f_trie *trie, const net_addr *net)
 421 {
 422   char buf[64];
 423   bt_format_net(buf, 64, net);
 424   bt_debug("TEST %s\n", buf);
 425
 426   int should_be = is_prefix_included(prefixes, net);
 427   int is_there  = trie_match_net(trie, net);
 428
 429   bt_assert_msg(should_be == is_there, "Prefix %s %s match", buf,
 430                 (should_be ? "should" : "should not"));
 431 }
 432
 433 static int
 434 t_match_random_net(void)
 435 {
 436   bt_bird_init();
 437   bt_config_parse(BT_CONFIG_SIMPLE);
 438
 439   int v6 = 0;
 440   linpool *lp = lp_new_default(&root_pool);
 441   for (int round = 0; round < TESTS_NUM; round++)
 442   {
 443     list *prefixes = make_random_prefix_list(lp, PREFIXES_NUM, v6, 0);
 444     struct f_trie *trie = make_trie_from_prefix_list(lp, prefixes);
 445
 446     for (int i = 0; i < PREFIX_TESTS_NUM; i++)
 447     {
 448       net_addr net;
 449       get_random_net(&net, v6);
 450       test_match_net(prefixes, trie, &net);
 451     }
 452
 453     v6 = !v6;
 454     lp_flush(lp);
 455   }
 456
 457   bt_bird_cleanup();
 458   return 1;
 459 }
 460
 461 static int
 462 t_match_inner_net(void)
 463 {
 464   bt_bird_init();
 465   bt_config_parse(BT_CONFIG_SIMPLE);
 466
 467   int v6 = 0;
 468   linpool *lp = lp_new_default(&root_pool);
 469   for (int round = 0; round < TESTS_NUM; round++)
 470   {
 471     list *prefixes = make_random_prefix_list(lp, PREFIXES_NUM, v6, 0);
 472     struct f_trie *trie = make_trie_from_prefix_list(lp, prefixes);
 473
 474     struct f_prefix_node *n = HEAD(*prefixes);
 475     for (int i = 0; i < PREFIX_TESTS_NUM; i++)
 476     {
 477       net_addr net;
 478       get_inner_net(&net, &n->prefix);
 479       test_match_net(prefixes, trie, &net);
 480
 481       n = NODE_VALID(NODE_NEXT(n)) ? NODE_NEXT(n) : HEAD(*prefixes);
 482     }
 483
 484     v6 = !v6;
 485     lp_flush(lp);
 486   }
 487
 488   bt_bird_cleanup();
 489   return 1;
 490 }
 491
 492 static int
 493 t_match_outer_net(void)
 494 {
 495   bt_bird_init();
 496   bt_config_parse(BT_CONFIG_SIMPLE);
 497
 498   int v6 = 0;
 499   linpool *lp = lp_new_default(&root_pool);
 500   for (int round = 0; round < TESTS_NUM; round++)
 501   {
 502     list *prefixes = make_random_prefix_list(lp, PREFIXES_NUM, v6, 0);
 503     struct f_trie *trie = make_trie_from_prefix_list(lp, prefixes);
 504
 505     struct f_prefix_node *n = HEAD(*prefixes);
 506     for (int i = 0; i < PREFIX_TESTS_NUM; i++)
 507     {
 508       net_addr net;
 509       get_outer_net(&net, &n->prefix);
 510       test_match_net(prefixes, trie, &net);
 511
 512       n = NODE_VALID(NODE_NEXT(n)) ? NODE_NEXT(n) : HEAD(*prefixes);
 513     }
 514
 515     v6 = !v6;
 516     lp_flush(lp);
 517   }
 518
 519   v6 = !v6;
 520   bt_bird_cleanup();
 521   return 1;
 522 }
 523
 524 /*
 525  * Read prefixes from @filename, build set of tries, prepare test data and do
 526  * PREFIX_BENCH_NUM trie lookups. With @plus = 0, use random subset of known
 527  * prefixes as test data, with @plus = 1, use randomly generated /32 prefixes
 528  * as test data.
 529  */
 530 static int
 531 benchmark_trie_dataset(const char *filename, int plus)
 532 {
 533   int n = 0;
 534   linpool *lp0 = lp_new_default(&root_pool);
 535   linpool *lp1 = lp_new_default(&root_pool);
 536   list *data[TRIE_BUFFER_SIZE];
 537   struct f_trie *trie[TRIE_BUFFER_SIZE];
 538   net_addr *nets;
 539
 540   bt_reset_suite_case_timer();
 541   bt_log_suite_case_result(1, "Reading %s", filename, n);
 542   n = read_prefix_file(filename, plus, lp0, lp1, data, trie);
 543   bt_log_suite_case_result(1, "Read prefix data, %d lists, ", n);
 544
 545   size_t trie_size = rmemsize(lp1).effective * 1000 / (1024*1024);
 546   bt_log_suite_case_result(1, "Trie size %u.%03u MB",
 547                            (uint) (trie_size / 1000), (uint) (trie_size % 1000));
 548
 549   int t = PREFIX_BENCH_NUM / n;
 550   int tb = MIN(t, TEST_BUFFER_SIZE);
 551   nets = lp_alloc(lp0, tb * sizeof(net_addr));
 552
 553   if (!plus)
 554     select_random_prefix_subset(data, nets, n, tb);
 555   else
 556     make_random_addresses(nets, tb);
 557
 558   bt_log_suite_case_result(1, "Make test data, %d (%d) tests", t, tb);
 559   bt_reset_suite_case_timer();
 560
 561   /*
 562   int match = 0;
 563   for (int i = 0; i < t; i++)
 564     for (int j = 0; j < n; j++)
 565       test_match_net(data[j], trie[j], &nets[i]);
 566   */
 567
 568   int match = 0;
 569   for (int i = 0; i < t; i++)
 570     for (int j = 0; j < n; j++)
 571       if (trie_match_net(trie[j], &nets[i % TEST_BUFFER_SIZE]))
 572         match++;
 573
 574   bt_log_suite_case_result(1, "Matching done, %d / %d matches", match, t * n);
 575
 576   rfree(lp0);
 577   rfree(lp1);
 578
 579   return 1;
 580 }
 581
 582 static int UNUSED
 583 t_bench_trie_datasets_subset(void)
 584 {
 585   bt_bird_init();
 586   bt_config_parse(BT_CONFIG_SIMPLE);
 587
 588   /* Specific datasets, not included */
 589   benchmark_trie_dataset("trie-data-bgp-1", 0);
 590   benchmark_trie_dataset("trie-data-bgp-10", 0);
 591   benchmark_trie_dataset("trie-data-bgp-100", 0);
 592   benchmark_trie_dataset("trie-data-bgp-1000", 0);
 593
 594   bt_bird_cleanup();
 595
 596   return 1;
 597 }
 598
 599 static int UNUSED
 600 t_bench_trie_datasets_random(void)
 601 {
 602   bt_bird_init();
 603   bt_config_parse(BT_CONFIG_SIMPLE);
 604
 605   /* Specific datasets, not included */
 606   benchmark_trie_dataset("trie-data-bgp-1", 1);
 607   benchmark_trie_dataset("trie-data-bgp-10", 1);
 608   benchmark_trie_dataset("trie-data-bgp-100", 1);
 609   benchmark_trie_dataset("trie-data-bgp-1000", 1);
 610
 611   bt_bird_cleanup();
 612
 613   return 1;
 614 }
 615
 616
 617 static int
 618 t_trie_same(void)
 619 {
 620   bt_bird_init();
 621   bt_config_parse(BT_CONFIG_SIMPLE);
 622
 623   int v6 = 0;
 624   linpool *lp = lp_new_default(&root_pool);
 625   for (int round = 0; round < TESTS_NUM*4; round++)
 626   {
 627     list *prefixes = make_random_prefix_list(lp, 100 * PREFIXES_NUM, v6, 0);
 628     struct f_trie *trie1 = f_new_trie(lp, 0);
 629     struct f_trie *trie2 = f_new_trie(lp, 0);
 630
 631     struct f_prefix_node *n;
 632     WALK_LIST(n, *prefixes)
 633       trie_add_prefix(trie1, &n->prefix.net, n->prefix.lo, n->prefix.hi);
 634
 635     WALK_LIST_BACKWARDS(n, *prefixes)
 636       trie_add_prefix(trie2, &n->prefix.net, n->prefix.lo, n->prefix.hi);
 637
 638     bt_assert(trie_same(trie1, trie2));
 639
 640     v6 = !v6;
 641     lp_flush(lp);
 642   }
 643
 644   bt_bird_cleanup();
 645   return 1;
 646 }
 647
 648 static inline void
 649 log_networks(const net_addr *a, const net_addr *b)
 650 {
 651   if (bt_verbose >= BT_VERBOSE_ABSOLUTELY_ALL)
 652   {
 653     char buf0[64];
 654     char buf1[64];
 655     bt_format_net(buf0, 64, a);
 656     bt_format_net(buf1, 64, b);
 657     bt_debug("Found %s expected %s\n", buf0, buf1);
 658   }
 659 }
 660
 661 static int
 662 t_trie_walk(void)
 663 {
 664   bt_bird_init();
 665   bt_config_parse(BT_CONFIG_SIMPLE);
 666
 667   linpool *lp = lp_new_default(&root_pool);
 668   for (int round = 0; round < TESTS_NUM*8; round++)
 669   {
 670     int level = round / TESTS_NUM;
 671     int v6 = level % 2;
 672     int num = PREFIXES_NUM * (int[]){1, 10, 100, 1000}[level / 2];
 673     int pos = 0, end = 0;
 674     list *prefixes = make_random_prefix_list(lp, num, v6, 1);
 675     struct f_trie *trie = make_trie_from_prefix_list(lp, prefixes);
 676     struct f_prefix *pxset = malloc((num + 1) * sizeof(struct f_prefix));
 677
 678     struct f_prefix_node *n;
 679     WALK_LIST(n, *prefixes)
 680       pxset[pos++] = n->prefix;
 681     memset(&pxset[pos], 0, sizeof (struct f_prefix));
 682
 683     qsort(pxset, num, sizeof(struct f_prefix), compare_prefixes);
 684
 685
 686     /* Full walk */
 687     bt_debug("Full walk (round %d, %d nets)\n", round, num);
 688
 689     pos = 0;
 690     uint pxc = 0;
 691     TRIE_WALK(trie, net, NULL)
 692     {
 693       log_networks(&net, &pxset[pos].net);
 694       bt_assert(net_equal(&net, &pxset[pos].net));
 695
 696       /* Skip possible duplicates */
 697       while (net_equal(&pxset[pos].net, &pxset[pos + 1].net))
 698         pos++;
 699
 700       pos++;
 701       pxc++;
 702     }
 703     TRIE_WALK_END;
 704
 705     bt_assert(pos == num);
 706     bt_assert(pxc == trie->prefix_count);
 707     bt_debug("Full walk done\n");
 708
 709
 710     /* Prepare net for subnet walk - start with random prefix */
 711     pos = bt_random() % num;
 712     end = pos + (int[]){2, 2, 3, 4}[level / 2];
 713     end = MIN(end, num);
 714
 715     struct f_prefix from = pxset[pos];
 716
 717     /* Find a common superprefix to several subsequent prefixes */
 718     for (; pos < end; pos++)
 719     {
 720       if (net_equal(&from.net, &pxset[pos].net))
 721         continue;
 722
 723       int common = !v6 ?
 724         ip4_pxlen(net4_prefix(&from.net), net4_prefix(&pxset[pos].net)) :
 725         ip6_pxlen(net6_prefix(&from.net), net6_prefix(&pxset[pos].net));
 726       from.net.pxlen = MIN(from.net.pxlen, common);
 727
 728       if (!v6)
 729         ((net_addr_ip4 *) &from.net)->prefix =
 730           ip4_and(net4_prefix(&from.net), net4_prefix(&pxset[pos].net));
 731       else
 732         ((net_addr_ip6 *) &from.net)->prefix =
 733           ip6_and(net6_prefix(&from.net), net6_prefix(&pxset[pos].net));
 734     }
 735
 736     /* Fix irrelevant bits */
 737     if (!v6)
 738       ((net_addr_ip4 *) &from.net)->prefix =
 739         ip4_and(net4_prefix(&from.net), ip4_mkmask(net4_pxlen(&from.net)));
 740     else
 741       ((net_addr_ip6 *) &from.net)->prefix =
 742         ip6_and(net6_prefix(&from.net), ip6_mkmask(net6_pxlen(&from.net)));
 743
 744
 745     /* Find initial position for final prefix */
 746     for (pos = 0; pos < num; pos++)
 747       if (compare_prefixes(&pxset[pos], &from) >= 0)
 748         break;
 749
 750     int p0 = pos;
 751     char buf0[64];
 752     bt_format_net(buf0, 64, &from.net);
 753     bt_debug("Subnet walk for %s (round %d, %d nets)\n", buf0, round, num);
 754
 755     /* Subnet walk */
 756     TRIE_WALK(trie, net, &from.net)
 757     {
 758       log_networks(&net, &pxset[pos].net);
 759       bt_assert(net_equal(&net, &pxset[pos].net));
 760       bt_assert(net_in_netX(&net, &from.net));
 761
 762       /* Skip possible duplicates */
 763       while (net_equal(&pxset[pos].net, &pxset[pos + 1].net))
 764         pos++;
 765
 766       pos++;
 767     }
 768     TRIE_WALK_END;
 769
 770     bt_assert((pos == num) || !net_in_netX(&pxset[pos].net, &from.net));
 771     bt_debug("Subnet walk done for %s (found %d nets)\n", buf0, pos - p0);
 772
 773     lp_flush(lp);
 774   }
 775
 776   bt_bird_cleanup();
 777   return 1;
 778 }
 779
 780 static int
 781 find_covering_nets(struct f_prefix *prefixes, int num, const net_addr *net, net_addr *found)
 782 {
 783   struct f_prefix key;
 784   net_addr *n = &key.net;
 785   int found_num = 0;
 786
 787   net_copy(n, net);
 788
 789   while (1)
 790   {
 791     struct f_prefix *px =
 792       bsearch(&key, prefixes, num, sizeof(struct f_prefix), compare_prefixes);
 793
 794     if (px)
 795     {
 796       net_copy(&found[found_num], n);
 797       found_num++;
 798     }
 799
 800     if (n->pxlen == 0)
 801       return found_num;
 802
 803     n->pxlen--;
 804
 805     if (n->type == NET_IP4)
 806       ip4_clrbit(&((net_addr_ip4 *) n)->prefix, n->pxlen);
 807     else
 808       ip6_clrbit(&((net_addr_ip6 *) n)->prefix, n->pxlen);
 809   }
 810 }
 811
 812 static int
 813 t_trie_walk_to_root(void)
 814 {
 815   bt_bird_init();
 816   bt_config_parse(BT_CONFIG_SIMPLE);
 817
 818   linpool *lp = lp_new_default(&root_pool);
 819   for (int round = 0; round < TESTS_NUM * 4; round++)
 820   {
 821     int level = round / TESTS_NUM;
 822     int v6 = level % 2;
 823     int num = PREFIXES_NUM  * (int[]){32, 512}[level / 2];
 824     int pos = 0;
 825     int st = 0, sn = 0, sm = 0;
 826
 827     list *prefixes = make_random_prefix_list(lp, num, v6, 1);
 828     struct f_trie *trie = make_trie_from_prefix_list(lp, prefixes);
 829     struct f_prefix *pxset = malloc((num + 1) * sizeof(struct f_prefix));
 830
 831     struct f_prefix_node *pxn;
 832     WALK_LIST(pxn, *prefixes)
 833       pxset[pos++] = pxn->prefix;
 834     memset(&pxset[pos], 0, sizeof (struct f_prefix));
 835
 836     qsort(pxset, num, sizeof(struct f_prefix), compare_prefixes);
 837
 838     int i;
 839     for (i = 0; i < (PREFIX_TESTS_NUM / 10); i++)
 840     {
 841       net_addr from;
 842       get_random_net(&from, v6);
 843
 844       net_addr found[129];
 845       int found_num = find_covering_nets(pxset, num, &from, found);
 846       int n = 0;
 847
 848       if (bt_verbose >= BT_VERBOSE_ABSOLUTELY_ALL)
 849       {
 850         char buf[64];
 851         bt_format_net(buf, 64, &from);
 852         bt_debug("Lookup for %s (expect %d)\n", buf, found_num);
 853       }
 854
 855       /* Walk to root, separate for IPv4 and IPv6 */
 856       if (!v6)
 857       {
 858         TRIE_WALK_TO_ROOT_IP4(trie, (net_addr_ip4 *) &from, net)
 859         {
 860           log_networks((net_addr *) &net, &found[n]);
 861           bt_assert((n < found_num) && net_equal((net_addr *) &net, &found[n]));
 862           n++;
 863         }
 864         TRIE_WALK_TO_ROOT_END;
 865       }
 866       else
 867       {
 868         TRIE_WALK_TO_ROOT_IP6(trie, (net_addr_ip6 *) &from, net)
 869         {
 870           log_networks((net_addr *) &net, &found[n]);
 871           bt_assert((n < found_num) && net_equal((net_addr *) &net, &found[n]));
 872           n++;
 873         }
 874         TRIE_WALK_TO_ROOT_END;
 875       }
 876
 877       bt_assert(n == found_num);
 878
 879       /* Stats */
 880       st += n;
 881       sn += !!n;
 882       sm = MAX(sm, n);
 883     }
 884
 885     bt_debug("Success in %d / %d, sum %d, max %d\n", sn, i, st, sm);
 886
 887     lp_flush(lp);
 888   }
 889
 890   bt_bird_cleanup();
 891   return 1;
 892 }
 893
 894 int
 895 main(int argc, char *argv[])
 896 {
 897   bt_init(argc, argv);
 898
 899   bt_test_suite(t_match_random_net, "Testing random prefix matching");
 900   bt_test_suite(t_match_inner_net, "Testing random inner prefix matching");
 901   bt_test_suite(t_match_outer_net, "Testing random outer prefix matching");
 902   bt_test_suite(t_trie_same, "A trie filled forward should be same with a trie filled backward.");
 903   bt_test_suite(t_trie_walk, "Testing TRIE_WALK() on random tries");
 904   bt_test_suite(t_trie_walk_to_root, "Testing TRIE_WALK_TO_ROOT() on random tries");
 905
 906   // bt_test_suite(t_bench_trie_datasets_subset, "Benchmark tries from datasets by random subset of nets");
 907   // bt_test_suite(t_bench_trie_datasets_random, "Benchmark tries from datasets by generated addresses");
 908
 909   return bt_exit_value();
 910 }