]>
Commit | Line | Data |
---|---|---|
1 | /* | |
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 | * | |
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 | |
20 | */ | |
21 | ||
22 | #include <zebra.h> | |
23 | #include "printfrr.h" | |
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 | * Human readable representation of the string. Allocated using | |
36 | * malloc()/dup(). | |
37 | */ | |
38 | char *prefix_str; | |
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 | */ | |
48 | static void add_node(struct route_table *table, const char *prefix_str) | |
49 | { | |
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; | |
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 | */ | |
81 | static void add_nodes(struct route_table *table, ...) | |
82 | { | |
83 | va_list arglist; | |
84 | char *prefix; | |
85 | ||
86 | va_start(arglist, table); | |
87 | ||
88 | prefix = va_arg(arglist, char *); | |
89 | while (prefix) { | |
90 | add_node(table, prefix); | |
91 | prefix = va_arg(arglist, char *); | |
92 | } | |
93 | ||
94 | va_end(arglist); | |
95 | } | |
96 | ||
97 | /* | |
98 | * print_subtree | |
99 | * | |
100 | * Recursive function to print a route node and its children. | |
101 | * | |
102 | * @see print_table | |
103 | */ | |
104 | static void print_subtree(struct route_node *rn, const char *legend, | |
105 | int indent_level) | |
106 | { | |
107 | int i; | |
108 | ||
109 | /* | |
110 | * Print this node first. | |
111 | */ | |
112 | for (i = 0; i < indent_level; i++) { | |
113 | printf(" "); | |
114 | } | |
115 | ||
116 | printfrr("%s: %pFX", legend, &rn->p); | |
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 | } | |
127 | } | |
128 | ||
129 | /* | |
130 | * print_table | |
131 | * | |
132 | * Function that prints out the internal structure of a route table. | |
133 | */ | |
134 | static void print_table(struct route_table *table) | |
135 | { | |
136 | struct route_node *rn; | |
137 | ||
138 | rn = table->top; | |
139 | ||
140 | if (!rn) { | |
141 | printf("<Empty Table>\n"); | |
142 | return; | |
143 | } | |
144 | ||
145 | print_subtree(rn, "Top", 0); | |
146 | } | |
147 | ||
148 | /* | |
149 | * clear_table | |
150 | * | |
151 | * Remove all nodes from the given table. | |
152 | */ | |
153 | static void clear_table(struct route_table *table) | |
154 | { | |
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); | |
170 | } | |
171 | ||
172 | route_table_iter_cleanup(&iter); | |
173 | ||
174 | assert(table->top == NULL); | |
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 | */ | |
184 | static void verify_next_by_iterating(struct route_table *table, | |
185 | struct prefix *target_pfx, | |
186 | struct prefix *next_pfx) | |
187 | { | |
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 | } | |
197 | } | |
198 | ||
199 | if (!rn) { | |
200 | assert(!next_pfx); | |
201 | } | |
202 | ||
203 | route_table_iter_cleanup(&iter); | |
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 | */ | |
212 | static void verify_next(struct route_table *table, const char *target, | |
213 | const char *next) | |
214 | { | |
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); | |
255 | } | |
256 | ||
257 | /* | |
258 | * test_get_next | |
259 | */ | |
260 | static void test_get_next(void) | |
261 | { | |
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); | |
358 | } | |
359 | ||
360 | /* | |
361 | * verify_prefix_iter_cmp | |
362 | */ | |
363 | static void verify_prefix_iter_cmp(const char *p1, const char *p2, | |
364 | int exp_result) | |
365 | { | |
366 | struct prefix_ipv4 p1_pfx, p2_pfx; | |
367 | int result; | |
368 | ||
369 | if (str2prefix_ipv4(p1, &p1_pfx) <= 0) { | |
370 | assert(0); | |
371 | } | |
372 | ||
373 | if (str2prefix_ipv4(p2, &p2_pfx) <= 0) { | |
374 | assert(0); | |
375 | } | |
376 | ||
377 | result = route_table_prefix_iter_cmp((struct prefix *)&p1_pfx, | |
378 | (struct prefix *)&p2_pfx); | |
379 | ||
380 | printf("Verifying cmp(%s, %s) returns %d\n", p1, p2, exp_result); | |
381 | ||
382 | assert(exp_result == result); | |
383 | ||
384 | /* | |
385 | * Also check the reverse comparison. | |
386 | */ | |
387 | result = route_table_prefix_iter_cmp((struct prefix *)&p2_pfx, | |
388 | (struct prefix *)&p1_pfx); | |
389 | ||
390 | if (exp_result) { | |
391 | exp_result = -exp_result; | |
392 | } | |
393 | ||
394 | printf("Verifying cmp(%s, %s) returns %d\n", p1, p2, exp_result); | |
395 | assert(result == exp_result); | |
396 | } | |
397 | ||
398 | /* | |
399 | * test_prefix_iter_cmp | |
400 | * | |
401 | * Tests comparison of prefixes according to order of iteration. | |
402 | */ | |
403 | static void test_prefix_iter_cmp(void) | |
404 | { | |
405 | printf("\n\nTesting route_table_prefix_iter_cmp()\n"); | |
406 | ||
407 | verify_prefix_iter_cmp("1.0.0.0/8", "1.0.0.0/8", 0); | |
408 | ||
409 | verify_prefix_iter_cmp("1.0.0.0/8", "1.0.0.0/16", -1); | |
410 | ||
411 | verify_prefix_iter_cmp("1.0.0.0/16", "1.128.0.0/16", -1); | |
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 | */ | |
421 | static void verify_iter_with_pause(struct route_table *table) | |
422 | { | |
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); | |
449 | } | |
450 | ||
451 | assert(num_nodes == route_table_count(table)); | |
452 | ||
453 | route_table_iter_pause(iter); | |
454 | iter_rn = route_table_iter_next(iter); | |
455 | ||
456 | assert(iter_rn == NULL); | |
457 | assert(iter->state == RT_ITER_STATE_DONE); | |
458 | ||
459 | assert(route_table_iter_next(iter) == NULL); | |
460 | assert(iter->state == RT_ITER_STATE_DONE); | |
461 | ||
462 | route_table_iter_cleanup(iter); | |
463 | ||
464 | print_table(table); | |
465 | printf("Verified pausing iteration on tree with %lu nodes\n", | |
466 | num_nodes); | |
467 | } | |
468 | ||
469 | /* | |
470 | * test_iter_pause | |
471 | */ | |
472 | static void test_iter_pause(void) | |
473 | { | |
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 | ||
479 | num_prefixes = array_size(prefixes); | |
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); | |
491 | } | |
492 | ||
493 | /* | |
494 | * run_tests | |
495 | */ | |
496 | static void run_tests(void) | |
497 | { | |
498 | test_prefix_iter_cmp(); | |
499 | test_get_next(); | |
500 | test_iter_pause(); | |
501 | } | |
502 | ||
503 | /* | |
504 | * main | |
505 | */ | |
506 | int main(void) | |
507 | { | |
508 | run_tests(); | |
509 | } |