Line data Source code
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 29 : 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 29 : assert (prefix_str);
59 :
60 29 : if (str2prefix_ipv4 (prefix_str, &p) <= 0)
61 : {
62 0 : assert (0);
63 : }
64 :
65 29 : rn = route_node_get (table, (struct prefix *) &p);
66 29 : if (rn->info)
67 : {
68 0 : assert (0);
69 : return;
70 : }
71 :
72 29 : node = malloc (sizeof (test_node_t));
73 29 : assert (node);
74 29 : node->prefix_str = strdup (prefix_str);
75 29 : assert (node->prefix_str);
76 29 : rn->info = node;
77 29 : }
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 16 : add_nodes (struct route_table *table, ...)
89 : {
90 : va_list arglist;
91 : char *prefix;
92 :
93 16 : va_start (arglist, table);
94 :
95 16 : prefix = va_arg (arglist, char *);
96 61 : while (prefix)
97 : {
98 29 : add_node (table, prefix);
99 29 : prefix = va_arg (arglist, char *);
100 : }
101 :
102 16 : va_end (arglist);
103 16 : }
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 34 : print_subtree (struct route_node *rn, const char *legend, int indent_level)
114 : {
115 : char buf[INET_ADDRSTRLEN + 4];
116 : int i;
117 :
118 : /*
119 : * Print this node first.
120 : */
121 66 : for (i = 0; i < indent_level; i++)
122 : {
123 32 : printf (" ");
124 : }
125 :
126 34 : prefix2str (&rn->p, buf, sizeof (buf));
127 34 : printf ("%s: %s", legend, buf);
128 34 : if (!rn->info)
129 : {
130 5 : printf (" (internal)");
131 : }
132 34 : printf ("\n");
133 34 : if (rn->l_left)
134 : {
135 12 : print_subtree (rn->l_left, "Left", indent_level + 1);
136 : }
137 34 : if (rn->l_right)
138 : {
139 10 : print_subtree (rn->l_right, "Right", indent_level + 1);
140 : }
141 34 : }
142 :
143 : /*
144 : * print_table
145 : *
146 : * Function that prints out the internal structure of a route table.
147 : */
148 : static void
149 12 : print_table (struct route_table *table)
150 : {
151 : struct route_node *rn;
152 :
153 12 : rn = table->top;
154 :
155 12 : if (!rn)
156 : {
157 0 : printf ("<Empty Table>\n");
158 0 : return;
159 : }
160 :
161 12 : 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 12 : 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 12 : route_table_iter_init (&iter, table);
177 :
178 58 : while ((rn = route_table_iter_next (&iter)))
179 : {
180 34 : node = rn->info;
181 34 : if (!node)
182 : {
183 5 : continue;
184 : }
185 29 : rn->info = NULL;
186 29 : route_unlock_node (rn);
187 29 : free (node->prefix_str);
188 29 : free (node);
189 : }
190 :
191 12 : route_table_iter_cleanup (&iter);
192 :
193 12 : assert (table->top == NULL);
194 12 : }
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 11 : 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 11 : route_table_iter_init (&iter, table);
211 11 : while ((rn = route_table_iter_next (&iter)))
212 : {
213 27 : if (route_table_prefix_iter_cmp (&rn->p, target_pfx) > 0)
214 : {
215 9 : assert (!prefix_cmp (&rn->p, next_pfx));
216 9 : break;
217 : }
218 : }
219 :
220 11 : if (!rn)
221 : {
222 2 : assert (!next_pfx);
223 : }
224 :
225 11 : route_table_iter_cleanup (&iter);
226 11 : }
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 11 : 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;
239 : char result_buf[INET_ADDRSTRLEN + 4];
240 :
241 11 : if (str2prefix_ipv4 (target, &target_pfx) <= 0)
242 : {
243 0 : assert (0);
244 : }
245 :
246 11 : rn = route_table_get_next (table, (struct prefix *) &target_pfx);
247 11 : if (rn)
248 : {
249 9 : prefix2str (&rn->p, result_buf, sizeof (result_buf));
250 : }
251 : else
252 : {
253 2 : snprintf (result_buf, sizeof (result_buf), "(Null)");
254 : }
255 :
256 11 : printf ("\n");
257 11 : print_table (table);
258 11 : printf ("Verifying successor of %s. Expected: %s, Result: %s\n", target,
259 : next ? next : "(Null)", result_buf);
260 :
261 11 : if (!rn)
262 : {
263 2 : assert (!next);
264 2 : verify_next_by_iterating (table, (struct prefix *) &target_pfx, NULL);
265 2 : return;
266 : }
267 :
268 9 : assert (next);
269 :
270 9 : if (str2prefix_ipv4 (next, &next_pfx) <= 0)
271 : {
272 0 : assert (0);
273 : }
274 :
275 9 : if (prefix_cmp (&rn->p, (struct prefix *) &next_pfx))
276 : {
277 0 : assert (0);
278 : }
279 9 : route_unlock_node (rn);
280 :
281 9 : 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 1 : test_get_next (void)
290 : {
291 : struct route_table *table;
292 :
293 1 : printf ("\n\nTesting route_table_get_next()\n");
294 1 : table = route_table_init ();
295 :
296 : /*
297 : * Target exists in tree, but has no successor.
298 : */
299 1 : add_nodes (table, "1.0.1.0/24", NULL);
300 1 : verify_next (table, "1.0.1.0/24", NULL);
301 1 : clear_table (table);
302 :
303 : /*
304 : * Target exists in tree, and there is a node in its left subtree.
305 : */
306 1 : add_nodes (table, "1.0.1.0/24", "1.0.1.0/25", NULL);
307 1 : verify_next (table, "1.0.1.0/24", "1.0.1.0/25");
308 1 : clear_table (table);
309 :
310 : /*
311 : * Target exists in tree, and there is a node in its right subtree.
312 : */
313 1 : add_nodes (table, "1.0.1.0/24", "1.0.1.128/25", NULL);
314 1 : verify_next (table, "1.0.1.0/24", "1.0.1.128/25");
315 1 : clear_table (table);
316 :
317 : /*
318 : * Target exists in the tree, next node is outside subtree.
319 : */
320 1 : add_nodes (table, "1.0.1.0/24", "1.1.0.0/16", NULL);
321 1 : verify_next (table, "1.0.1.0/24", "1.1.0.0/16");
322 1 : 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 1 : add_nodes (table, "1.0.0.0/16", NULL);
333 1 : verify_next (table, "1.0.1.0/24", NULL);
334 1 : clear_table (table);
335 :
336 : /*
337 : * There exists a node that would be in the target's left subtree.
338 : */
339 1 : add_nodes (table, "1.0.0.0/16", "1.0.1.0/25", NULL);
340 1 : verify_next (table, "1.0.1.0/24", "1.0.1.0/25");
341 1 : clear_table (table);
342 :
343 : /*
344 : * There exists a node would be in the target's right subtree.
345 : */
346 1 : add_nodes (table, "1.0.0.0/16", "1.0.1.128/25", NULL);
347 1 : verify_next (table, "1.0.1.0/24", "1.0.1.128/25");
348 1 : 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 1 : add_nodes (table, "1.0.0.0/16", "1.0.128.0/17", NULL);
356 1 : verify_next (table, "1.0.0.0/17", "1.0.128.0/17");
357 1 : 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 1 : 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 1 : verify_next (table, "1.0.1.0/25", "1.0.128.0/17");
366 1 : 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 1 : add_nodes (table, "1.0.0.0/16", "1.0.1.0/24", NULL);
378 1 : verify_next (table, "1.0.0.0/24", "1.0.1.0/24");
379 1 : clear_table (table);
380 :
381 1 : 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 1 : verify_next (table, "1.0.1.128/25", "1.0.128.0/17");
384 1 : clear_table (table);
385 :
386 1 : route_table_finish (table);
387 1 : }
388 :
389 : /*
390 : * verify_prefix_iter_cmp
391 : */
392 : static void
393 3 : 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 3 : if (str2prefix_ipv4 (p1, &p1_pfx) <= 0)
399 : {
400 0 : assert (0);
401 : }
402 :
403 3 : if (str2prefix_ipv4 (p2, &p2_pfx) <= 0)
404 : {
405 0 : assert (0);
406 : }
407 :
408 3 : result = route_table_prefix_iter_cmp ((struct prefix *) &p1_pfx,
409 : (struct prefix *) &p2_pfx);
410 :
411 3 : printf ("Verifying cmp(%s, %s) returns %d\n", p1, p2, exp_result);
412 :
413 3 : assert (exp_result == result);
414 :
415 : /*
416 : * Also check the reverse comparision.
417 : */
418 3 : result = route_table_prefix_iter_cmp ((struct prefix *) &p2_pfx,
419 : (struct prefix *) &p1_pfx);
420 :
421 3 : if (exp_result)
422 : {
423 2 : exp_result = -exp_result;
424 : }
425 :
426 3 : printf ("Verifying cmp(%s, %s) returns %d\n", p1, p2, exp_result);
427 3 : assert (result == exp_result);
428 3 : }
429 :
430 : /*
431 : * test_prefix_iter_cmp
432 : *
433 : * Tests comparision of prefixes according to order of iteration.
434 : */
435 : static void
436 1 : test_prefix_iter_cmp ()
437 : {
438 1 : printf ("\n\nTesting route_table_prefix_iter_cmp()\n");
439 :
440 1 : verify_prefix_iter_cmp ("1.0.0.0/8", "1.0.0.0/8", 0);
441 :
442 1 : verify_prefix_iter_cmp ("1.0.0.0/8", "1.0.0.0/16", -1);
443 :
444 1 : verify_prefix_iter_cmp ("1.0.0.0/16", "1.128.0.0/16", -1);
445 1 : }
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 1 : 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 1 : route_table_iter_t *iter = &iter_space;
461 :
462 1 : route_table_iter_init (iter, table);
463 1 : num_nodes = 0;
464 :
465 8 : for (rn = route_top (table); rn; rn = route_next (rn))
466 : {
467 7 : num_nodes++;
468 7 : route_table_iter_pause (iter);
469 :
470 7 : assert (iter->current == NULL);
471 7 : if (route_table_iter_started (iter))
472 : {
473 6 : assert (iter->state == RT_ITER_STATE_PAUSED);
474 : }
475 : else
476 : {
477 1 : assert (rn == table->top);
478 1 : assert (iter->state == RT_ITER_STATE_INIT);
479 : }
480 :
481 7 : iter_rn = route_table_iter_next (iter);
482 :
483 : /*
484 : * Make sure both iterations return the same node.
485 : */
486 7 : assert (rn == iter_rn);
487 : }
488 :
489 1 : assert (num_nodes == route_table_count (table));
490 :
491 1 : route_table_iter_pause (iter);
492 1 : iter_rn = route_table_iter_next (iter);
493 :
494 1 : assert (iter_rn == NULL);
495 1 : assert (iter->state == RT_ITER_STATE_DONE);
496 :
497 1 : assert (route_table_iter_next (iter) == NULL);
498 1 : assert (iter->state == RT_ITER_STATE_DONE);
499 :
500 1 : route_table_iter_cleanup (iter);
501 :
502 1 : print_table (table);
503 1 : printf ("Verified pausing iteration on tree with %lu nodes\n", num_nodes);
504 1 : }
505 :
506 : /*
507 : * test_iter_pause
508 : */
509 : static void
510 1 : test_iter_pause (void)
511 : {
512 : struct route_table *table;
513 : int i, num_prefixes;
514 1 : 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 1 : num_prefixes = sizeof (prefixes) / sizeof (prefixes[0]);
523 :
524 1 : printf ("\n\nTesting that route_table_iter_pause() works as expected\n");
525 1 : table = route_table_init ();
526 6 : for (i = 0; i < num_prefixes; i++)
527 : {
528 5 : add_nodes (table, prefixes[i], NULL);
529 : }
530 :
531 1 : verify_iter_with_pause (table);
532 :
533 1 : clear_table (table);
534 1 : route_table_finish (table);
535 1 : }
536 :
537 : /*
538 : * run_tests
539 : */
540 : static void
541 1 : run_tests (void)
542 : {
543 1 : test_prefix_iter_cmp ();
544 1 : test_get_next ();
545 1 : test_iter_pause ();
546 1 : }
547 :
548 : /*
549 : * main
550 : */
551 : int
552 1 : main (void)
553 : {
554 1 : run_tests ();
555 : }
|
