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