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