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