tests/table_test.c

   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 {
 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  */
 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;
 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  */
 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 }