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