]>
Commit | Line | Data |
---|---|---|
9b0a0ba9 OZ |
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" | |
4f082dfa | 13 | #include "filter/data.h" |
9b0a0ba9 OZ |
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, sizeof(struct f_trie_node)); | |
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 | ||
fd328869 | 133 | bt_bird_cleanup(); |
5e3cd0e5 | 134 | return 1; |
9b0a0ba9 OZ |
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, sizeof(struct f_trie_node)); | |
147 | struct f_trie * trie2 = f_new_trie(config->mem, sizeof(struct f_trie_node)); | |
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 | ||
5e3cd0e5 | 174 | return 1; |
9b0a0ba9 OZ |
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 | } |