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