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 "conf/conf.h"
  14
  15 #define TESTS_NUM               10
  16 #define PREFIXES_NUM            10
  17 #define PREFIX_TESTS_NUM        10000
  18
  19 #define BIG_BUFFER_SIZE         10000
  20
  21 /* Wrapping structure for storing f_prefixes structures in list */
  22 struct f_prefix_node {
  23   node n;
  24   struct f_prefix prefix;
  25 };
  26
  27 static u32
  28 xrandom(u32 max)
  29 {
  30   return (bt_random() % max);
  31 }
  32
  33 static int
  34 is_prefix_included(list *prefixes, struct f_prefix *needle)
  35 {
  36   struct f_prefix_node *n;
  37   WALK_LIST(n, *prefixes)
  38   {
  39     ip6_addr cmask = ip6_mkmask(MIN(n->prefix.net.pxlen, needle->net.pxlen));
  40
  41     ip6_addr ip = net6_prefix(&n->prefix.net);
  42     ip6_addr needle_ip = net6_prefix(&needle->net);
  43
  44     if ((ipa_compare(ipa_and(ip, cmask), ipa_and(needle_ip, cmask)) == 0) &&
  45         (n->prefix.lo <= needle->net.pxlen) && (needle->net.pxlen <= n->prefix.hi))
  46     {
  47       bt_debug("FOUND\t" PRIip6 "/%d %d-%d\n", ARGip6(net6_prefix(&n->prefix.net)), n->prefix.net.pxlen, n->prefix.lo, n->prefix.hi);
  48       return 1; /* OK */
  49     }
  50   }
  51   return 0; /* FAIL */
  52 }
  53
  54 static struct f_prefix
  55 get_random_ip6_prefix(void)
  56 {
  57   struct f_prefix p;
  58   u8 pxlen = xrandom(120)+8;
  59   ip6_addr ip6 = ip6_build(bt_random(),bt_random(),bt_random(),bt_random());
  60   net_addr_ip6 net6 = NET_ADDR_IP6(ip6, pxlen);
  61
  62   p.net = *((net_addr*) &net6);
  63
  64   if (bt_random() % 2)
  65   {
  66     p.lo = 0;
  67     p.hi = p.net.pxlen;
  68   }
  69   else
  70   {
  71     p.lo = p.net.pxlen;
  72     p.hi = net_max_prefix_length[p.net.type];
  73   }
  74
  75   return p;
  76 }
  77
  78 static void
  79 generate_random_ipv6_prefixes(list *prefixes)
  80 {
  81   int i;
  82   for (i = 0; i < PREFIXES_NUM; i++)
  83   {
  84     struct f_prefix f = get_random_ip6_prefix();
  85
  86     struct f_prefix_node *px = calloc(1, sizeof(struct f_prefix_node));
  87     px->prefix = f;
  88
  89     bt_debug("ADD\t" PRIip6 "/%d %d-%d\n", ARGip6(net6_prefix(&px->prefix.net)), px->prefix.net.pxlen, px->prefix.lo, px->prefix.hi);
  90     add_tail(prefixes, &px->n);
  91   }
  92 }
  93
  94 static int
  95 t_match_net(void)
  96 {
  97   bt_bird_init();
  98   bt_config_parse(BT_CONFIG_SIMPLE);
  99
 100   uint round;
 101   for (round = 0; round < TESTS_NUM; round++)
 102   {
 103     list prefixes; /* of structs f_extended_prefix */
 104     init_list(&prefixes);
 105     struct f_trie *trie = f_new_trie(config->mem, sizeof(struct f_trie_node));
 106
 107     generate_random_ipv6_prefixes(&prefixes);
 108     struct f_prefix_node *n;
 109     WALK_LIST(n, prefixes)
 110     {
 111       trie_add_prefix(trie, &n->prefix.net, n->prefix.lo, n->prefix.hi);
 112     }
 113
 114     int i;
 115     for (i = 0; i < PREFIX_TESTS_NUM; i++)
 116     {
 117       struct f_prefix f = get_random_ip6_prefix();
 118       bt_debug("TEST\t" PRIip6 "/%d\n", ARGip6(net6_prefix(&f.net)), f.net.pxlen);
 119
 120       int should_be = is_prefix_included(&prefixes, &f);
 121       int is_there  = trie_match_net(trie, &f.net);
 122       bt_assert_msg(should_be == is_there, "Prefix " PRIip6 "/%d %s", ARGip6(net6_prefix(&f.net)), f.net.pxlen, (should_be ? "should be found in trie" : "should not be found in trie"));
 123     }
 124
 125     struct f_prefix_node *nxt;
 126     WALK_LIST_DELSAFE(n, nxt, prefixes)
 127     {
 128       free(n);
 129     }
 130   }
 131
 132   bt_bird_cleanup();
 133   return 1;
 134 }
 135
 136 static int
 137 t_trie_same(void)
 138 {
 139   bt_bird_init();
 140   bt_config_parse(BT_CONFIG_SIMPLE);
 141
 142   int round;
 143   for (round = 0; round < TESTS_NUM*4; round++)
 144   {
 145     struct f_trie * trie1 = f_new_trie(config->mem, sizeof(struct f_trie_node));
 146     struct f_trie * trie2 = f_new_trie(config->mem, sizeof(struct f_trie_node));
 147
 148     list prefixes; /* a list of f_extended_prefix structures */
 149     init_list(&prefixes);
 150     int i;
 151     for (i = 0; i < 100; i++)
 152       generate_random_ipv6_prefixes(&prefixes);
 153
 154     struct f_prefix_node *n;
 155     WALK_LIST(n, prefixes)
 156     {
 157       trie_add_prefix(trie1, &n->prefix.net, n->prefix.lo, n->prefix.hi);
 158     }
 159     WALK_LIST_BACKWARDS(n, prefixes)
 160     {
 161       trie_add_prefix(trie2, &n->prefix.net, n->prefix.lo, n->prefix.hi);
 162     }
 163
 164     bt_assert(trie_same(trie1, trie2));
 165
 166     struct f_prefix_node *nxt;
 167     WALK_LIST_DELSAFE(n, nxt, prefixes)
 168     {
 169       free(n);
 170     }
 171   }
 172
 173   return 1;
 174 }
 175
 176 int
 177 main(int argc, char *argv[])
 178 {
 179   bt_init(argc, argv);
 180
 181   bt_test_suite(t_match_net, "Testing random prefix matching");
 182   bt_test_suite(t_trie_same, "A trie filled forward should be same with a trie filled backward.");
 183
 184   return bt_exit_value();
 185 }