Statistics
| Branch: | Revision:

iof-bird / bird-2.0.1 / filter / trie_test.c @ 6b3f1a54

History | View | Annotate | Download (4.29 KB)

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
}