]>
Commit | Line | Data |
---|---|---|
785025ee CF |
1 | /* |
2 | * Test srcdest table for correctness. | |
3 | * | |
4 | * Copyright (C) 2017 by David Lamparter & Christian Franke, | |
5 | * Open Source Routing / NetDEF Inc. | |
6 | * | |
7 | * This file is part of FreeRangeRouting (FRR) | |
8 | * | |
9 | * FRR is free software; you can redistribute it and/or modify it | |
10 | * under the terms of the GNU General Public License as published by the | |
11 | * Free Software Foundation; either version 2, or (at your option) any | |
12 | * later version. | |
13 | * | |
14 | * FRR is distributed in the hope that it will be useful, but | |
15 | * WITHOUT ANY WARRANTY; without even the implied warranty of | |
16 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
17 | * General Public License for more details. | |
18 | * | |
896014f4 DL |
19 | * You should have received a copy of the GNU General Public License along |
20 | * with this program; see the file COPYING; if not, write to the Free Software | |
21 | * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA | |
785025ee CF |
22 | */ |
23 | ||
24 | #include <zebra.h> | |
25 | ||
26 | #include "hash.h" | |
27 | #include "memory.h" | |
28 | #include "prefix.h" | |
29 | #include "prng.h" | |
30 | #include "srcdest_table.h" | |
31 | #include "table.h" | |
32 | ||
33 | /* Copied from ripngd/ripng_nexthop.h - maybe the whole s6_addr32 thing | |
34 | * should be added by autoconf if not present? | |
35 | */ | |
36 | #ifndef s6_addr32 | |
37 | #if defined(SUNOS_5) | |
38 | /* Some SunOS define s6_addr32 only to kernel */ | |
39 | #define s6_addr32 _S6_un._S6_u32 | |
40 | #else | |
41 | #define s6_addr32 __u6_addr.__u6_addr32 | |
42 | #endif /* SUNOS_5 */ | |
43 | #endif /*s6_addr32*/ | |
44 | ||
45 | struct thread_master *master; | |
46 | ||
47 | /* This structure is copied from lib/srcdest_table.c to which it is | |
48 | * private as far as other parts of Quagga are concerned. | |
49 | */ | |
d62a17ae | 50 | struct srcdest_rnode { |
51 | /* must be first in structure for casting to/from route_node */ | |
52 | ROUTE_NODE_FIELDS; | |
785025ee | 53 | |
d62a17ae | 54 | struct route_table *src_table; |
785025ee CF |
55 | }; |
56 | ||
d62a17ae | 57 | struct test_state { |
58 | struct route_table *table; | |
59 | struct hash *log; | |
785025ee CF |
60 | }; |
61 | ||
d62a17ae | 62 | static char *format_srcdest(const struct prefix_ipv6 *dst_p, |
63 | const struct prefix_ipv6 *src_p) | |
785025ee | 64 | { |
d62a17ae | 65 | char dst_str[BUFSIZ]; |
66 | char src_str[BUFSIZ]; | |
67 | char *rv; | |
68 | int ec; | |
69 | ||
70 | prefix2str((const struct prefix *)dst_p, dst_str, sizeof(dst_str)); | |
71 | if (src_p && src_p->prefixlen) | |
72 | prefix2str((const struct prefix *)src_p, src_str, | |
73 | sizeof(src_str)); | |
74 | else | |
75 | src_str[0] = '\0'; | |
76 | ||
77 | ec = asprintf(&rv, "%s%s%s", dst_str, | |
78 | (src_str[0] != '\0') ? " from " : "", src_str); | |
79 | ||
80 | assert(ec > 0); | |
81 | return rv; | |
785025ee CF |
82 | } |
83 | ||
84 | static unsigned int log_key(void *data) | |
85 | { | |
d62a17ae | 86 | struct prefix *hash_entry = data; |
87 | struct prefix_ipv6 *dst_p = (struct prefix_ipv6 *)&hash_entry[0]; | |
88 | struct prefix_ipv6 *src_p = (struct prefix_ipv6 *)&hash_entry[1]; | |
89 | unsigned int hash = 0; | |
90 | unsigned int i; | |
91 | ||
92 | hash = (hash * 33) ^ (unsigned int)dst_p->prefixlen; | |
93 | for (i = 0; i < 4; i++) | |
94 | hash = (hash * 33) ^ (unsigned int)dst_p->prefix.s6_addr32[i]; | |
95 | ||
96 | hash = (hash * 33) ^ (unsigned int)src_p->prefixlen; | |
97 | if (src_p->prefixlen) | |
98 | for (i = 0; i < 4; i++) | |
99 | hash = (hash * 33) | |
100 | ^ (unsigned int)src_p->prefix.s6_addr32[i]; | |
101 | ||
102 | return hash; | |
785025ee CF |
103 | } |
104 | ||
d62a17ae | 105 | static int log_cmp(const void *a, const void *b) |
785025ee | 106 | { |
6d10727a | 107 | if (a == NULL || b == NULL) |
d62a17ae | 108 | return 0; |
785025ee | 109 | |
d62a17ae | 110 | return !memcmp(a, b, 2 * sizeof(struct prefix)); |
785025ee CF |
111 | } |
112 | ||
d62a17ae | 113 | static void log_free(void *data) |
785025ee | 114 | { |
d62a17ae | 115 | XFREE(MTYPE_TMP, data); |
785025ee CF |
116 | } |
117 | ||
d62a17ae | 118 | static void *log_alloc(void *data) |
785025ee | 119 | { |
d62a17ae | 120 | void *rv = XMALLOC(MTYPE_TMP, 2 * sizeof(struct prefix)); |
121 | memcpy(rv, data, 2 * sizeof(struct prefix)); | |
122 | return rv; | |
785025ee CF |
123 | } |
124 | ||
d62a17ae | 125 | static struct test_state *test_state_new(void) |
785025ee | 126 | { |
d62a17ae | 127 | struct test_state *rv; |
785025ee | 128 | |
d62a17ae | 129 | rv = XCALLOC(MTYPE_TMP, sizeof(*rv)); |
130 | assert(rv); | |
785025ee | 131 | |
d62a17ae | 132 | rv->table = srcdest_table_init(); |
133 | assert(rv->table); | |
785025ee | 134 | |
d62a17ae | 135 | rv->log = hash_create(log_key, log_cmp, NULL); |
136 | return rv; | |
785025ee CF |
137 | } |
138 | ||
d62a17ae | 139 | static void test_state_free(struct test_state *test) |
785025ee | 140 | { |
d62a17ae | 141 | route_table_finish(test->table); |
142 | hash_clean(test->log, log_free); | |
143 | hash_free(test->log); | |
144 | XFREE(MTYPE_TMP, test); | |
785025ee CF |
145 | } |
146 | ||
d62a17ae | 147 | static void test_state_add_route(struct test_state *test, |
148 | struct prefix_ipv6 *dst_p, | |
149 | struct prefix_ipv6 *src_p) | |
785025ee | 150 | { |
d62a17ae | 151 | struct route_node *rn = |
152 | srcdest_rnode_get(test->table, (struct prefix *)dst_p, src_p); | |
153 | struct prefix hash_entry[2]; | |
154 | ||
155 | memset(hash_entry, 0, sizeof(hash_entry)); | |
156 | memcpy(&hash_entry[0], dst_p, sizeof(*dst_p)); | |
157 | memcpy(&hash_entry[1], src_p, sizeof(*src_p)); | |
158 | ||
159 | if (rn->info) { | |
160 | route_unlock_node(rn); | |
161 | assert(hash_lookup(test->log, hash_entry) != NULL); | |
162 | return; | |
163 | } else { | |
164 | assert(hash_lookup(test->log, hash_entry) == NULL); | |
165 | } | |
166 | ||
167 | rn->info = (void *)0xdeadbeef; | |
168 | hash_get(test->log, hash_entry, log_alloc); | |
785025ee CF |
169 | }; |
170 | ||
d62a17ae | 171 | static void test_state_del_route(struct test_state *test, |
172 | struct prefix_ipv6 *dst_p, | |
173 | struct prefix_ipv6 *src_p) | |
785025ee | 174 | { |
d62a17ae | 175 | struct route_node *rn = srcdest_rnode_lookup( |
176 | test->table, (struct prefix *)dst_p, src_p); | |
177 | struct prefix hash_entry[2]; | |
178 | ||
179 | memset(hash_entry, 0, sizeof(hash_entry)); | |
180 | memcpy(&hash_entry[0], dst_p, sizeof(*dst_p)); | |
181 | memcpy(&hash_entry[1], src_p, sizeof(*src_p)); | |
182 | ||
183 | if (!rn) { | |
184 | assert(!hash_lookup(test->log, hash_entry)); | |
185 | return; | |
186 | } | |
187 | ||
188 | assert(rn->info == (void *)0xdeadbeef); | |
189 | rn->info = NULL; | |
190 | route_unlock_node(rn); | |
191 | route_unlock_node(rn); | |
192 | ||
193 | struct prefix *hash_entry_intern = hash_release(test->log, hash_entry); | |
194 | assert(hash_entry_intern != NULL); | |
195 | XFREE(MTYPE_TMP, hash_entry_intern); | |
785025ee CF |
196 | } |
197 | ||
d62a17ae | 198 | static void verify_log(struct hash_backet *backet, void *arg) |
785025ee | 199 | { |
d62a17ae | 200 | struct test_state *test = arg; |
201 | struct prefix *hash_entry = backet->data; | |
202 | struct prefix *dst_p = &hash_entry[0]; | |
203 | struct prefix_ipv6 *src_p = (struct prefix_ipv6 *)&hash_entry[1]; | |
204 | struct route_node *rn = srcdest_rnode_lookup(test->table, dst_p, src_p); | |
785025ee | 205 | |
d62a17ae | 206 | assert(rn); |
207 | assert(rn->info == (void *)0xdeadbeef); | |
785025ee | 208 | |
d62a17ae | 209 | route_unlock_node(rn); |
785025ee CF |
210 | } |
211 | ||
d62a17ae | 212 | static void dump_log(struct hash_backet *backet, void *arg) |
785025ee | 213 | { |
d62a17ae | 214 | struct prefix *hash_entry = backet->data; |
215 | struct prefix_ipv6 *dst_p = (struct prefix_ipv6 *)&hash_entry[0]; | |
216 | struct prefix_ipv6 *src_p = (struct prefix_ipv6 *)&hash_entry[1]; | |
217 | char *route_id = format_srcdest(dst_p, src_p); | |
785025ee | 218 | |
d62a17ae | 219 | fprintf(stderr, " %s\n", route_id); |
220 | free(route_id); | |
785025ee CF |
221 | } |
222 | ||
d62a17ae | 223 | static void test_dump(struct test_state *test) |
785025ee | 224 | { |
d62a17ae | 225 | fprintf(stderr, "Contents of hash table:\n"); |
226 | hash_iterate(test->log, dump_log, test); | |
227 | fprintf(stderr, "\n"); | |
785025ee CF |
228 | } |
229 | ||
d62a17ae | 230 | static void test_failed(struct test_state *test, const char *message, |
2861a0de MS |
231 | const struct prefix_ipv6 *dst_p, |
232 | const struct prefix_ipv6 *src_p) | |
785025ee | 233 | { |
d62a17ae | 234 | char *route_id = format_srcdest(dst_p, src_p); |
785025ee | 235 | |
d62a17ae | 236 | fprintf(stderr, "Test failed. Error: %s\n", message); |
237 | fprintf(stderr, "Route in question: %s\n", route_id); | |
238 | free(route_id); | |
785025ee | 239 | |
d62a17ae | 240 | test_dump(test); |
241 | assert(3 == 4); | |
785025ee CF |
242 | } |
243 | ||
d62a17ae | 244 | static void test_state_verify(struct test_state *test) |
785025ee | 245 | { |
d62a17ae | 246 | struct route_node *rn; |
247 | struct prefix hash_entry[2]; | |
248 | ||
249 | memset(hash_entry, 0, sizeof(hash_entry)); | |
250 | ||
251 | /* Verify that there are no elements in the table which have never | |
252 | * been added */ | |
253 | for (rn = route_top(test->table); rn; rn = srcdest_route_next(rn)) { | |
2861a0de | 254 | const struct prefix_ipv6 *dst_p, *src_p; |
d62a17ae | 255 | |
256 | /* While we are iterating, we hold a lock on the current | |
257 | * route_node, | |
258 | * so all the lock counts we check for take that into account; | |
259 | * in idle | |
260 | * state all the numbers will be exactly one less. | |
261 | * | |
262 | * Also this makes quite some assumptions based on the current | |
263 | * implementation details of route_table and srcdest_table - | |
264 | * another | |
265 | * valid implementation might trigger assertions here. | |
266 | */ | |
267 | ||
268 | if (rnode_is_dstnode(rn)) { | |
269 | struct srcdest_rnode *srn = (struct srcdest_rnode *)rn; | |
270 | unsigned int expected_lock = 1; /* We are in the loop */ | |
271 | ||
272 | if (rn->info | |
273 | != NULL) /* The route node is not internal */ | |
274 | expected_lock++; | |
275 | if (srn->src_table != NULL) /* There's a source table | |
276 | associated with rn */ | |
277 | expected_lock++; | |
278 | ||
279 | if (rn->lock != expected_lock) | |
280 | test_failed( | |
281 | test, | |
282 | "Dest rnode lock count doesn't match expected count!", | |
283 | (struct prefix_ipv6 *)&rn->p, NULL); | |
284 | } else { | |
285 | unsigned int expected_lock = 1; /* We are in the loop */ | |
286 | ||
287 | if (rn->info | |
288 | != NULL) /* The route node is not internal */ | |
289 | expected_lock++; | |
290 | ||
291 | if (rn->lock != expected_lock) { | |
2861a0de | 292 | const struct prefix_ipv6 *dst_p, *src_p; |
d62a17ae | 293 | srcdest_rnode_prefixes( |
2861a0de MS |
294 | rn, (const struct prefix **)&dst_p, |
295 | (const struct prefix **)&src_p); | |
d62a17ae | 296 | |
297 | test_failed( | |
298 | test, | |
299 | "Src rnode lock count doesn't match expected count!", | |
300 | dst_p, src_p); | |
301 | } | |
302 | } | |
303 | ||
304 | if (!rn->info) | |
305 | continue; | |
306 | ||
307 | assert(rn->info == (void *)0xdeadbeef); | |
308 | ||
2861a0de MS |
309 | srcdest_rnode_prefixes(rn, (const struct prefix **)&dst_p, |
310 | (const struct prefix **)&src_p); | |
d62a17ae | 311 | memcpy(&hash_entry[0], dst_p, sizeof(*dst_p)); |
312 | if (src_p) | |
313 | memcpy(&hash_entry[1], src_p, sizeof(*src_p)); | |
314 | else | |
315 | memset(&hash_entry[1], 0, sizeof(hash_entry[1])); | |
316 | ||
317 | if (hash_lookup(test->log, hash_entry) == NULL) | |
318 | test_failed(test, "Route is missing in hash", dst_p, | |
319 | src_p); | |
320 | } | |
321 | ||
322 | /* Verify that all added elements are still in the table */ | |
323 | hash_iterate(test->log, verify_log, test); | |
785025ee CF |
324 | } |
325 | ||
d62a17ae | 326 | static void get_rand_prefix(struct prng *prng, struct prefix_ipv6 *p) |
785025ee | 327 | { |
d62a17ae | 328 | int i; |
785025ee | 329 | |
d62a17ae | 330 | memset(p, 0, sizeof(*p)); |
785025ee | 331 | |
d62a17ae | 332 | for (i = 0; i < 4; i++) |
333 | p->prefix.s6_addr32[i] = prng_rand(prng); | |
334 | p->prefixlen = prng_rand(prng) % 129; | |
335 | p->family = AF_INET6; | |
785025ee | 336 | |
d62a17ae | 337 | apply_mask((struct prefix *)p); |
785025ee CF |
338 | } |
339 | ||
d62a17ae | 340 | static void get_rand_prefix_pair(struct prng *prng, struct prefix_ipv6 *dst_p, |
341 | struct prefix_ipv6 *src_p) | |
785025ee | 342 | { |
d62a17ae | 343 | get_rand_prefix(prng, dst_p); |
344 | if ((prng_rand(prng) % 4) == 0) { | |
345 | get_rand_prefix(prng, src_p); | |
346 | if (src_p->prefixlen) | |
347 | return; | |
348 | } | |
349 | ||
350 | memset(src_p, 0, sizeof(*src_p)); | |
785025ee CF |
351 | } |
352 | ||
d62a17ae | 353 | static void test_state_add_rand_route(struct test_state *test, |
354 | struct prng *prng) | |
785025ee | 355 | { |
d62a17ae | 356 | struct prefix_ipv6 dst_p, src_p; |
785025ee | 357 | |
d62a17ae | 358 | get_rand_prefix_pair(prng, &dst_p, &src_p); |
359 | test_state_add_route(test, &dst_p, &src_p); | |
785025ee CF |
360 | } |
361 | ||
d62a17ae | 362 | static void test_state_del_rand_route(struct test_state *test, |
363 | struct prng *prng) | |
785025ee | 364 | { |
d62a17ae | 365 | struct prefix_ipv6 dst_p, src_p; |
785025ee | 366 | |
d62a17ae | 367 | get_rand_prefix_pair(prng, &dst_p, &src_p); |
368 | test_state_del_route(test, &dst_p, &src_p); | |
785025ee CF |
369 | } |
370 | ||
d62a17ae | 371 | static void test_state_del_one_route(struct test_state *test, struct prng *prng) |
785025ee | 372 | { |
d62a17ae | 373 | unsigned int which_route; |
374 | ||
375 | if (test->log->count == 0) | |
376 | return; | |
377 | ||
378 | which_route = prng_rand(prng) % test->log->count; | |
379 | ||
380 | struct route_node *rn; | |
2861a0de | 381 | const struct prefix *dst_p, *src_p; |
d62a17ae | 382 | struct prefix_ipv6 dst6_p, src6_p; |
383 | ||
384 | for (rn = route_top(test->table); rn; rn = srcdest_route_next(rn)) { | |
385 | if (!rn->info) | |
386 | continue; | |
387 | if (!which_route) { | |
388 | route_unlock_node(rn); | |
389 | break; | |
390 | } | |
391 | which_route--; | |
392 | } | |
393 | ||
394 | assert(rn); | |
395 | srcdest_rnode_prefixes(rn, &dst_p, &src_p); | |
396 | memcpy(&dst6_p, dst_p, sizeof(dst6_p)); | |
397 | if (src_p) | |
398 | memcpy(&src6_p, src_p, sizeof(src6_p)); | |
399 | else | |
400 | memset(&src6_p, 0, sizeof(src6_p)); | |
401 | ||
402 | test_state_del_route(test, &dst6_p, &src6_p); | |
785025ee CF |
403 | } |
404 | ||
d62a17ae | 405 | static void run_prng_test(void) |
785025ee | 406 | { |
d62a17ae | 407 | struct test_state *test = test_state_new(); |
408 | struct prng *prng = prng_new(0); | |
409 | size_t i; | |
410 | ||
411 | for (i = 0; i < 1000; i++) { | |
412 | switch (prng_rand(prng) % 10) { | |
413 | case 0: | |
414 | case 1: | |
415 | case 2: | |
416 | case 3: | |
417 | case 4: | |
418 | test_state_add_rand_route(test, prng); | |
419 | break; | |
420 | case 5: | |
421 | case 6: | |
422 | case 7: | |
423 | test_state_del_one_route(test, prng); | |
424 | break; | |
425 | case 8: | |
426 | case 9: | |
427 | test_state_del_rand_route(test, prng); | |
428 | break; | |
429 | } | |
430 | test_state_verify(test); | |
431 | } | |
432 | ||
433 | prng_free(prng); | |
434 | test_state_free(test); | |
785025ee CF |
435 | } |
436 | ||
437 | int main(int argc, char *argv[]) | |
438 | { | |
d62a17ae | 439 | run_prng_test(); |
440 | printf("PRNG Test successful.\n"); | |
441 | return 0; | |
785025ee | 442 | } |