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 */ 34typedef 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 44struct thread_master *master; 45 46/* 47 * add_node 48 * 49 * Add the given prefix (passed in as a string) to the given table. 50 */ 51static void 52add_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 */ 87static void 88add_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 */ 112static void 113print_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 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 */ 148static void 149print_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 */ 169static void 170clear_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 */ 203static void 204verify_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 */ 234static void 235verify_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 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 */ 288static void 289test_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 */ 392static void 393verify_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 */ 435static void 436test_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 */ 454static void 455verify_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 */ 509static void 510test_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 */ 540static void 541run_tests (void) 542{ 543 test_prefix_iter_cmp (); 544 test_get_next (); 545 test_iter_pause (); 546} 547 548/* 549 * main 550 */ 551int 552main (void) 553{ 554 run_tests (); 555} 556