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