]>
Commit | Line | Data |
---|---|---|
acddc0ed | 1 | // SPDX-License-Identifier: GPL-2.0-or-later |
8ef0791c | 2 | /* |
28971c8c AS |
3 | * Routing table test |
4 | * Copyright (C) 2012 OSR. | |
5 | * | |
6 | * This file is part of Quagga | |
28971c8c AS |
7 | */ |
8 | ||
9 | #include <zebra.h> | |
f62fd2ac | 10 | #include "printfrr.h" |
28971c8c AS |
11 | #include "prefix.h" |
12 | #include "table.h" | |
13 | ||
14 | /* | |
15 | * test_node_t | |
16 | * | |
17 | * Information that is kept for each node in the radix tree. | |
18 | */ | |
d62a17ae | 19 | typedef struct test_node_t_ { |
28971c8c | 20 | |
d62a17ae | 21 | /* |
22 | * Human readable representation of the string. Allocated using | |
23 | * malloc()/dup(). | |
24 | */ | |
25 | char *prefix_str; | |
28971c8c AS |
26 | } test_node_t; |
27 | ||
28 | struct thread_master *master; | |
29 | ||
30 | /* | |
31 | * add_node | |
32 | * | |
33 | * Add the given prefix (passed in as a string) to the given table. | |
34 | */ | |
d62a17ae | 35 | static void add_node(struct route_table *table, const char *prefix_str) |
28971c8c | 36 | { |
d62a17ae | 37 | struct prefix_ipv4 p; |
38 | test_node_t *node; | |
39 | struct route_node *rn; | |
40 | ||
41 | assert(prefix_str); | |
42 | ||
43 | if (str2prefix_ipv4(prefix_str, &p) <= 0) { | |
44 | assert(0); | |
45 | } | |
46 | ||
47 | rn = route_node_get(table, (struct prefix *)&p); | |
48 | if (rn->info) { | |
49 | assert(0); | |
50 | return; | |
51 | } | |
52 | ||
53 | node = malloc(sizeof(test_node_t)); | |
54 | assert(node); | |
55 | node->prefix_str = strdup(prefix_str); | |
56 | assert(node->prefix_str); | |
57 | rn->info = node; | |
28971c8c AS |
58 | } |
59 | ||
60 | /* | |
61 | * add_nodes | |
62 | * | |
63 | * Convenience function to add a bunch of nodes together. | |
64 | * | |
65 | * The arguments must be prefixes in string format, with a NULL as the | |
66 | * last argument. | |
67 | */ | |
d62a17ae | 68 | static void add_nodes(struct route_table *table, ...) |
28971c8c | 69 | { |
d62a17ae | 70 | va_list arglist; |
71 | char *prefix; | |
28971c8c | 72 | |
d62a17ae | 73 | va_start(arglist, table); |
28971c8c | 74 | |
d62a17ae | 75 | prefix = va_arg(arglist, char *); |
76 | while (prefix) { | |
77 | add_node(table, prefix); | |
78 | prefix = va_arg(arglist, char *); | |
79 | } | |
28971c8c | 80 | |
d62a17ae | 81 | va_end(arglist); |
28971c8c AS |
82 | } |
83 | ||
84 | /* | |
85 | * print_subtree | |
86 | * | |
87 | * Recursive function to print a route node and its children. | |
88 | * | |
89 | * @see print_table | |
90 | */ | |
d62a17ae | 91 | static void print_subtree(struct route_node *rn, const char *legend, |
92 | int indent_level) | |
28971c8c | 93 | { |
d62a17ae | 94 | int i; |
95 | ||
96 | /* | |
97 | * Print this node first. | |
98 | */ | |
99 | for (i = 0; i < indent_level; i++) { | |
100 | printf(" "); | |
101 | } | |
102 | ||
f62fd2ac | 103 | printfrr("%s: %pFX", legend, &rn->p); |
d62a17ae | 104 | if (!rn->info) { |
105 | printf(" (internal)"); | |
106 | } | |
107 | printf("\n"); | |
108 | if (rn->l_left) { | |
109 | print_subtree(rn->l_left, "Left", indent_level + 1); | |
110 | } | |
111 | if (rn->l_right) { | |
112 | print_subtree(rn->l_right, "Right", indent_level + 1); | |
113 | } | |
28971c8c AS |
114 | } |
115 | ||
116 | /* | |
117 | * print_table | |
118 | * | |
119 | * Function that prints out the internal structure of a route table. | |
120 | */ | |
d62a17ae | 121 | static void print_table(struct route_table *table) |
28971c8c | 122 | { |
d62a17ae | 123 | struct route_node *rn; |
28971c8c | 124 | |
d62a17ae | 125 | rn = table->top; |
28971c8c | 126 | |
d62a17ae | 127 | if (!rn) { |
128 | printf("<Empty Table>\n"); | |
129 | return; | |
130 | } | |
28971c8c | 131 | |
d62a17ae | 132 | print_subtree(rn, "Top", 0); |
28971c8c AS |
133 | } |
134 | ||
135 | /* | |
136 | * clear_table | |
137 | * | |
138 | * Remove all nodes from the given table. | |
139 | */ | |
d62a17ae | 140 | static void clear_table(struct route_table *table) |
28971c8c | 141 | { |
d62a17ae | 142 | route_table_iter_t iter; |
143 | struct route_node *rn; | |
144 | test_node_t *node; | |
145 | ||
146 | route_table_iter_init(&iter, table); | |
147 | ||
148 | while ((rn = route_table_iter_next(&iter))) { | |
149 | node = rn->info; | |
150 | if (!node) { | |
151 | continue; | |
152 | } | |
153 | rn->info = NULL; | |
154 | route_unlock_node(rn); | |
155 | free(node->prefix_str); | |
156 | free(node); | |
28971c8c | 157 | } |
28971c8c | 158 | |
d62a17ae | 159 | route_table_iter_cleanup(&iter); |
28971c8c | 160 | |
d62a17ae | 161 | assert(table->top == NULL); |
28971c8c AS |
162 | } |
163 | ||
164 | /* | |
165 | * verify_next_by_iterating | |
166 | * | |
167 | * Iterate over the tree to make sure that the first prefix after | |
168 | * target_pfx is the expected one. Note that target_pfx may not be | |
169 | * present in the tree. | |
170 | */ | |
d62a17ae | 171 | static void verify_next_by_iterating(struct route_table *table, |
172 | struct prefix *target_pfx, | |
173 | struct prefix *next_pfx) | |
28971c8c | 174 | { |
d62a17ae | 175 | route_table_iter_t iter; |
176 | struct route_node *rn; | |
177 | ||
178 | route_table_iter_init(&iter, table); | |
179 | while ((rn = route_table_iter_next(&iter))) { | |
180 | if (route_table_prefix_iter_cmp(&rn->p, target_pfx) > 0) { | |
181 | assert(!prefix_cmp(&rn->p, next_pfx)); | |
182 | break; | |
183 | } | |
28971c8c | 184 | } |
28971c8c | 185 | |
d62a17ae | 186 | if (!rn) { |
187 | assert(!next_pfx); | |
188 | } | |
28971c8c | 189 | |
d62a17ae | 190 | route_table_iter_cleanup(&iter); |
28971c8c AS |
191 | } |
192 | ||
193 | /* | |
194 | * verify_next | |
195 | * | |
196 | * Verifies that route_table_get_next() returns the expected result | |
197 | * (result) for the prefix string 'target'. | |
198 | */ | |
d62a17ae | 199 | static void verify_next(struct route_table *table, const char *target, |
200 | const char *next) | |
28971c8c | 201 | { |
d62a17ae | 202 | struct prefix_ipv4 target_pfx, next_pfx; |
203 | struct route_node *rn; | |
204 | char result_buf[PREFIX2STR_BUFFER]; | |
205 | ||
206 | if (str2prefix_ipv4(target, &target_pfx) <= 0) { | |
207 | assert(0); | |
208 | } | |
209 | ||
210 | rn = route_table_get_next(table, (struct prefix *)&target_pfx); | |
211 | if (rn) { | |
212 | prefix2str(&rn->p, result_buf, sizeof(result_buf)); | |
213 | } else { | |
214 | snprintf(result_buf, sizeof(result_buf), "(Null)"); | |
215 | } | |
216 | ||
217 | printf("\n"); | |
218 | print_table(table); | |
219 | printf("Verifying successor of %s. Expected: %s, Result: %s\n", target, | |
220 | next ? next : "(Null)", result_buf); | |
221 | ||
222 | if (!rn) { | |
223 | assert(!next); | |
224 | verify_next_by_iterating(table, (struct prefix *)&target_pfx, | |
225 | NULL); | |
226 | return; | |
227 | } | |
228 | ||
229 | assert(next); | |
230 | ||
231 | if (str2prefix_ipv4(next, &next_pfx) <= 0) { | |
232 | assert(0); | |
233 | } | |
234 | ||
235 | if (prefix_cmp(&rn->p, (struct prefix *)&next_pfx)) { | |
236 | assert(0); | |
237 | } | |
238 | route_unlock_node(rn); | |
239 | ||
240 | verify_next_by_iterating(table, (struct prefix *)&target_pfx, | |
241 | (struct prefix *)&next_pfx); | |
28971c8c AS |
242 | } |
243 | ||
244 | /* | |
245 | * test_get_next | |
246 | */ | |
d62a17ae | 247 | static void test_get_next(void) |
28971c8c | 248 | { |
d62a17ae | 249 | struct route_table *table; |
250 | ||
251 | printf("\n\nTesting route_table_get_next()\n"); | |
252 | table = route_table_init(); | |
253 | ||
254 | /* | |
255 | * Target exists in tree, but has no successor. | |
256 | */ | |
257 | add_nodes(table, "1.0.1.0/24", NULL); | |
258 | verify_next(table, "1.0.1.0/24", NULL); | |
259 | clear_table(table); | |
260 | ||
261 | /* | |
262 | * Target exists in tree, and there is a node in its left subtree. | |
263 | */ | |
264 | add_nodes(table, "1.0.1.0/24", "1.0.1.0/25", NULL); | |
265 | verify_next(table, "1.0.1.0/24", "1.0.1.0/25"); | |
266 | clear_table(table); | |
267 | ||
268 | /* | |
269 | * Target exists in tree, and there is a node in its right subtree. | |
270 | */ | |
271 | add_nodes(table, "1.0.1.0/24", "1.0.1.128/25", NULL); | |
272 | verify_next(table, "1.0.1.0/24", "1.0.1.128/25"); | |
273 | clear_table(table); | |
274 | ||
275 | /* | |
276 | * Target exists in the tree, next node is outside subtree. | |
277 | */ | |
278 | add_nodes(table, "1.0.1.0/24", "1.1.0.0/16", NULL); | |
279 | verify_next(table, "1.0.1.0/24", "1.1.0.0/16"); | |
280 | clear_table(table); | |
281 | ||
282 | /* | |
283 | * The target node does not exist in the tree for all the test cases | |
284 | * below this point. | |
285 | */ | |
286 | ||
287 | /* | |
288 | * There is no successor in the tree. | |
289 | */ | |
290 | add_nodes(table, "1.0.0.0/16", NULL); | |
291 | verify_next(table, "1.0.1.0/24", NULL); | |
292 | clear_table(table); | |
293 | ||
294 | /* | |
295 | * There exists a node that would be in the target's left subtree. | |
296 | */ | |
297 | add_nodes(table, "1.0.0.0/16", "1.0.1.0/25", NULL); | |
298 | verify_next(table, "1.0.1.0/24", "1.0.1.0/25"); | |
299 | clear_table(table); | |
300 | ||
301 | /* | |
302 | * There exists a node would be in the target's right subtree. | |
303 | */ | |
304 | add_nodes(table, "1.0.0.0/16", "1.0.1.128/25", NULL); | |
305 | verify_next(table, "1.0.1.0/24", "1.0.1.128/25"); | |
306 | clear_table(table); | |
307 | ||
308 | /* | |
309 | * A search for the target reaches a node where there are no child | |
310 | * nodes in the direction of the target (left), but the node has a | |
311 | * right child. | |
312 | */ | |
313 | add_nodes(table, "1.0.0.0/16", "1.0.128.0/17", NULL); | |
314 | verify_next(table, "1.0.0.0/17", "1.0.128.0/17"); | |
315 | clear_table(table); | |
316 | ||
317 | /* | |
318 | * A search for the target reaches a node with no children. We have | |
319 | * to go upwards in the tree to find a successor. | |
320 | */ | |
321 | add_nodes(table, "1.0.0.0/16", "1.0.0.0/24", "1.0.1.0/24", | |
322 | "1.0.128.0/17", NULL); | |
323 | verify_next(table, "1.0.1.0/25", "1.0.128.0/17"); | |
324 | clear_table(table); | |
325 | ||
326 | /* | |
327 | * A search for the target reaches a node where neither the node nor | |
328 | * the target prefix contain each other. | |
329 | * | |
330 | * In first case below the node succeeds the target. | |
331 | * | |
332 | * In the second case, the node comes before the target, so we have | |
333 | * to go up the tree looking for a successor. | |
334 | */ | |
335 | add_nodes(table, "1.0.0.0/16", "1.0.1.0/24", NULL); | |
336 | verify_next(table, "1.0.0.0/24", "1.0.1.0/24"); | |
337 | clear_table(table); | |
338 | ||
339 | add_nodes(table, "1.0.0.0/16", "1.0.0.0/24", "1.0.1.0/25", | |
340 | "1.0.128.0/17", NULL); | |
341 | verify_next(table, "1.0.1.128/25", "1.0.128.0/17"); | |
342 | clear_table(table); | |
343 | ||
344 | route_table_finish(table); | |
28971c8c AS |
345 | } |
346 | ||
347 | /* | |
348 | * verify_prefix_iter_cmp | |
349 | */ | |
d62a17ae | 350 | static void verify_prefix_iter_cmp(const char *p1, const char *p2, |
351 | int exp_result) | |
28971c8c | 352 | { |
d62a17ae | 353 | struct prefix_ipv4 p1_pfx, p2_pfx; |
354 | int result; | |
28971c8c | 355 | |
d62a17ae | 356 | if (str2prefix_ipv4(p1, &p1_pfx) <= 0) { |
357 | assert(0); | |
358 | } | |
28971c8c | 359 | |
d62a17ae | 360 | if (str2prefix_ipv4(p2, &p2_pfx) <= 0) { |
361 | assert(0); | |
362 | } | |
28971c8c | 363 | |
d62a17ae | 364 | result = route_table_prefix_iter_cmp((struct prefix *)&p1_pfx, |
365 | (struct prefix *)&p2_pfx); | |
28971c8c | 366 | |
d62a17ae | 367 | printf("Verifying cmp(%s, %s) returns %d\n", p1, p2, exp_result); |
28971c8c | 368 | |
d62a17ae | 369 | assert(exp_result == result); |
28971c8c | 370 | |
d62a17ae | 371 | /* |
ce5002c6 | 372 | * Also check the reverse comparison. |
d62a17ae | 373 | */ |
374 | result = route_table_prefix_iter_cmp((struct prefix *)&p2_pfx, | |
375 | (struct prefix *)&p1_pfx); | |
28971c8c | 376 | |
d62a17ae | 377 | if (exp_result) { |
378 | exp_result = -exp_result; | |
379 | } | |
28971c8c | 380 | |
d62a17ae | 381 | printf("Verifying cmp(%s, %s) returns %d\n", p1, p2, exp_result); |
382 | assert(result == exp_result); | |
28971c8c AS |
383 | } |
384 | ||
385 | /* | |
386 | * test_prefix_iter_cmp | |
387 | * | |
ce5002c6 | 388 | * Tests comparison of prefixes according to order of iteration. |
28971c8c | 389 | */ |
4d762f26 | 390 | static void test_prefix_iter_cmp(void) |
28971c8c | 391 | { |
d62a17ae | 392 | printf("\n\nTesting route_table_prefix_iter_cmp()\n"); |
28971c8c | 393 | |
d62a17ae | 394 | verify_prefix_iter_cmp("1.0.0.0/8", "1.0.0.0/8", 0); |
28971c8c | 395 | |
d62a17ae | 396 | verify_prefix_iter_cmp("1.0.0.0/8", "1.0.0.0/16", -1); |
28971c8c | 397 | |
d62a17ae | 398 | verify_prefix_iter_cmp("1.0.0.0/16", "1.128.0.0/16", -1); |
28971c8c AS |
399 | } |
400 | ||
401 | /* | |
402 | * verify_iter_with_pause | |
403 | * | |
404 | * Iterates over a tree using two methods: 'normal' iteration, and an | |
405 | * iterator that pauses at each node. Verifies that the two methods | |
406 | * yield the same results. | |
407 | */ | |
d62a17ae | 408 | static void verify_iter_with_pause(struct route_table *table) |
28971c8c | 409 | { |
d62a17ae | 410 | unsigned long num_nodes; |
411 | struct route_node *rn, *iter_rn; | |
412 | route_table_iter_t iter_space; | |
413 | route_table_iter_t *iter = &iter_space; | |
414 | ||
415 | route_table_iter_init(iter, table); | |
416 | num_nodes = 0; | |
417 | ||
418 | for (rn = route_top(table); rn; rn = route_next(rn)) { | |
419 | num_nodes++; | |
420 | route_table_iter_pause(iter); | |
421 | ||
422 | assert(iter->current == NULL); | |
423 | if (route_table_iter_started(iter)) { | |
424 | assert(iter->state == RT_ITER_STATE_PAUSED); | |
425 | } else { | |
426 | assert(rn == table->top); | |
427 | assert(iter->state == RT_ITER_STATE_INIT); | |
428 | } | |
429 | ||
430 | iter_rn = route_table_iter_next(iter); | |
431 | ||
432 | /* | |
433 | * Make sure both iterations return the same node. | |
434 | */ | |
435 | assert(rn == iter_rn); | |
28971c8c AS |
436 | } |
437 | ||
d62a17ae | 438 | assert(num_nodes == route_table_count(table)); |
28971c8c | 439 | |
d62a17ae | 440 | route_table_iter_pause(iter); |
441 | iter_rn = route_table_iter_next(iter); | |
28971c8c | 442 | |
d62a17ae | 443 | assert(iter_rn == NULL); |
444 | assert(iter->state == RT_ITER_STATE_DONE); | |
28971c8c | 445 | |
d62a17ae | 446 | assert(route_table_iter_next(iter) == NULL); |
447 | assert(iter->state == RT_ITER_STATE_DONE); | |
28971c8c | 448 | |
d62a17ae | 449 | route_table_iter_cleanup(iter); |
28971c8c | 450 | |
d62a17ae | 451 | print_table(table); |
452 | printf("Verified pausing iteration on tree with %lu nodes\n", | |
453 | num_nodes); | |
28971c8c AS |
454 | } |
455 | ||
456 | /* | |
457 | * test_iter_pause | |
458 | */ | |
d62a17ae | 459 | static void test_iter_pause(void) |
28971c8c | 460 | { |
d62a17ae | 461 | struct route_table *table; |
462 | int i, num_prefixes; | |
463 | const char *prefixes[] = {"1.0.1.0/24", "1.0.1.0/25", "1.0.1.128/25", | |
464 | "1.0.2.0/24", "2.0.0.0/8"}; | |
465 | ||
97b5d752 | 466 | num_prefixes = array_size(prefixes); |
d62a17ae | 467 | |
468 | printf("\n\nTesting that route_table_iter_pause() works as expected\n"); | |
469 | table = route_table_init(); | |
470 | for (i = 0; i < num_prefixes; i++) { | |
471 | add_nodes(table, prefixes[i], NULL); | |
472 | } | |
473 | ||
474 | verify_iter_with_pause(table); | |
475 | ||
476 | clear_table(table); | |
477 | route_table_finish(table); | |
28971c8c AS |
478 | } |
479 | ||
480 | /* | |
481 | * run_tests | |
482 | */ | |
d62a17ae | 483 | static void run_tests(void) |
28971c8c | 484 | { |
d62a17ae | 485 | test_prefix_iter_cmp(); |
486 | test_get_next(); | |
487 | test_iter_pause(); | |
28971c8c AS |
488 | } |
489 | ||
490 | /* | |
491 | * main | |
492 | */ | |
d62a17ae | 493 | int main(void) |
28971c8c | 494 | { |
d62a17ae | 495 | run_tests(); |
28971c8c | 496 | } |