tests/table_test.c

   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
  18  * along with Quagga; see the file COPYING.  If not, write to the Free
  19  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  20  * 02111-1307, USA.
  21  */
  22
  23 #include <zebra.h>
  24
  25 #include "prefix.h"
  26 #include "table.h"
  27
  28 /*
  29  * test_node_t
  30  *
  31  * Information that is kept for each node in the radix tree.
  32  */
  33 typedef struct test_node_t_
  34 {
  35
  36   /*
  37    * Human readable representation of the string. Allocated using
  38    * malloc()/dup().
  39    */
  40   char *prefix_str;
  41 } test_node_t;
  42
  43 struct thread_master *master;
  44
  45 /*
  46  * add_node
  47  *
  48  * Add the given prefix (passed in as a string) to the given table.
  49  */
  50 static void
  51 add_node (struct route_table *table, const char *prefix_str)
  52 {
  53   struct prefix_ipv4 p;
  54   test_node_t *node;
  55   struct route_node *rn;
  56
  57   assert (prefix_str);
  58
  59   if (str2prefix_ipv4 (prefix_str, &p) <= 0)
  60     {
  61       assert (0);
  62     }
  63
  64   rn = route_node_get (table, (struct prefix *) &p);
  65   if (rn->info)
  66     {
  67       assert (0);
  68       return;
  69     }
  70
  71   node = malloc (sizeof (test_node_t));
  72   assert (node);
  73   node->prefix_str = strdup (prefix_str);
  74   assert (node->prefix_str);
  75   rn->info = node;
  76 }
  77
  78 /*
  79  * add_nodes
  80  *
  81  * Convenience function to add a bunch of nodes together.
  82  *
  83  * The arguments must be prefixes in string format, with a NULL as the
  84  * last argument.
  85  */
  86 static void
  87 add_nodes (struct route_table *table, ...)
  88 {
  89   va_list arglist;
  90   char *prefix;
  91
  92   va_start (arglist, table);
  93
  94   prefix = va_arg (arglist, char *);
  95   while (prefix)
  96     {
  97       add_node (table, prefix);
  98       prefix = va_arg (arglist, char *);
  99     }
 100
 101   va_end (arglist);
 102 }
 103
 104 /*
 105  * print_subtree
 106  *
 107  * Recursive function to print a route node and its children.
 108  *
 109  * @see print_table
 110  */
 111 static void
 112 print_subtree (struct route_node *rn, const char *legend, int indent_level)
 113 {
 114   char buf[PREFIX2STR_BUFFER];
 115   int i;
 116
 117   /*
 118    * Print this node first.
 119    */
 120   for (i = 0; i < indent_level; i++)
 121     {
 122       printf ("  ");
 123     }
 124
 125   prefix2str (&rn->p, buf, sizeof (buf));
 126   printf ("%s: %s", legend, buf);
 127   if (!rn->info)
 128     {
 129       printf (" (internal)");
 130     }
 131   printf ("\n");
 132   if (rn->l_left)
 133     {
 134       print_subtree (rn->l_left, "Left", indent_level + 1);
 135     }
 136   if (rn->l_right)
 137     {
 138       print_subtree (rn->l_right, "Right", indent_level + 1);
 139     }
 140 }
 141
 142 /*
 143  * print_table
 144  *
 145  * Function that prints out the internal structure of a route table.
 146  */
 147 static void
 148 print_table (struct route_table *table)
 149 {
 150   struct route_node *rn;
 151
 152   rn = table->top;
 153
 154   if (!rn)
 155     {
 156       printf ("<Empty Table>\n");
 157       return;
 158     }
 159
 160   print_subtree (rn, "Top", 0);
 161 }
 162
 163 /*
 164  * clear_table
 165  *
 166  * Remove all nodes from the given table.
 167  */
 168 static void
 169 clear_table (struct route_table *table)
 170 {
 171   route_table_iter_t iter;
 172   struct route_node *rn;
 173   test_node_t *node;
 174
 175   route_table_iter_init (&iter, table);
 176
 177   while ((rn = route_table_iter_next (&iter)))
 178     {
 179       node = rn->info;
 180       if (!node)
 181         {
 182           continue;
 183         }
 184       rn->info = NULL;
 185       route_unlock_node (rn);
 186       free (node->prefix_str);
 187       free (node);
 188     }
 189
 190   route_table_iter_cleanup (&iter);
 191
 192   assert (table->top == NULL);
 193 }
 194
 195 /*
 196  * verify_next_by_iterating
 197  *
 198  * Iterate over the tree to make sure that the first prefix after
 199  * target_pfx is the expected one. Note that target_pfx may not be
 200  * present in the tree.
 201  */
 202 static void
 203 verify_next_by_iterating (struct route_table *table,
 204                           struct prefix *target_pfx, struct prefix *next_pfx)
 205 {
 206   route_table_iter_t iter;
 207   struct route_node *rn;
 208
 209   route_table_iter_init (&iter, table);
 210   while ((rn = route_table_iter_next (&iter)))
 211     {
 212       if (route_table_prefix_iter_cmp (&rn->p, target_pfx) > 0)
 213         {
 214           assert (!prefix_cmp (&rn->p, next_pfx));
 215           break;
 216         }
 217     }
 218
 219   if (!rn)
 220     {
 221       assert (!next_pfx);
 222     }
 223
 224   route_table_iter_cleanup (&iter);
 225 }
 226
 227 /*
 228  * verify_next
 229  *
 230  * Verifies that route_table_get_next() returns the expected result
 231  * (result) for the prefix string 'target'.
 232  */
 233 static void
 234 verify_next (struct route_table *table, const char *target, const char *next)
 235 {
 236   struct prefix_ipv4 target_pfx, next_pfx;
 237   struct route_node *rn;
 238   char result_buf[PREFIX2STR_BUFFER];
 239
 240   if (str2prefix_ipv4 (target, &target_pfx) <= 0)
 241     {
 242       assert (0);
 243     }
 244
 245   rn = route_table_get_next (table, (struct prefix *) &target_pfx);
 246   if (rn)
 247     {
 248       prefix2str (&rn->p, result_buf, sizeof (result_buf));
 249     }
 250   else
 251     {
 252       snprintf (result_buf, sizeof (result_buf), "(Null)");
 253     }
 254
 255   printf ("\n");
 256   print_table (table);
 257   printf ("Verifying successor of %s. Expected: %s, Result: %s\n", target,
 258           next ? next : "(Null)", result_buf);
 259
 260   if (!rn)
 261     {
 262       assert (!next);
 263       verify_next_by_iterating (table, (struct prefix *) &target_pfx, NULL);
 264       return;
 265     }
 266
 267   assert (next);
 268
 269   if (str2prefix_ipv4 (next, &next_pfx) <= 0)
 270     {
 271       assert (0);
 272     }
 273
 274   if (prefix_cmp (&rn->p, (struct prefix *) &next_pfx))
 275     {
 276       assert (0);
 277     }
 278   route_unlock_node (rn);
 279
 280   verify_next_by_iterating (table, (struct prefix *) &target_pfx,
 281                             (struct prefix *) &next_pfx);
 282 }
 283
 284 /*
 285  * test_get_next
 286  */
 287 static void
 288 test_get_next (void)
 289 {
 290   struct route_table *table;
 291
 292   printf ("\n\nTesting route_table_get_next()\n");
 293   table = route_table_init ();
 294
 295   /*
 296    * Target exists in tree, but has no successor.
 297    */
 298   add_nodes (table, "1.0.1.0/24", NULL);
 299   verify_next (table, "1.0.1.0/24", NULL);
 300   clear_table (table);
 301
 302   /*
 303    * Target exists in tree, and there is a node in its left subtree.
 304    */
 305   add_nodes (table, "1.0.1.0/24", "1.0.1.0/25", NULL);
 306   verify_next (table, "1.0.1.0/24", "1.0.1.0/25");
 307   clear_table (table);
 308
 309   /*
 310    * Target exists in tree, and there is a node in its right subtree.
 311    */
 312   add_nodes (table, "1.0.1.0/24", "1.0.1.128/25", NULL);
 313   verify_next (table, "1.0.1.0/24", "1.0.1.128/25");
 314   clear_table (table);
 315
 316   /*
 317    * Target exists in the tree, next node is outside subtree.
 318    */
 319   add_nodes (table, "1.0.1.0/24", "1.1.0.0/16", NULL);
 320   verify_next (table, "1.0.1.0/24", "1.1.0.0/16");
 321   clear_table (table);
 322
 323   /*
 324    * The target node does not exist in the tree for all the test cases
 325    * below this point.
 326    */
 327
 328   /*
 329    * There is no successor in the tree.
 330    */
 331   add_nodes (table, "1.0.0.0/16", NULL);
 332   verify_next (table, "1.0.1.0/24", NULL);
 333   clear_table (table);
 334
 335   /*
 336    * There exists a node that would be in the target's left subtree.
 337    */
 338   add_nodes (table, "1.0.0.0/16", "1.0.1.0/25", NULL);
 339   verify_next (table, "1.0.1.0/24", "1.0.1.0/25");
 340   clear_table (table);
 341
 342   /*
 343    * There exists a node would be in the target's right subtree.
 344    */
 345   add_nodes (table, "1.0.0.0/16", "1.0.1.128/25", NULL);
 346   verify_next (table, "1.0.1.0/24", "1.0.1.128/25");
 347   clear_table (table);
 348
 349   /*
 350    * A search for the target reaches a node where there are no child
 351    * nodes in the direction of the target (left), but the node has a
 352    * right child.
 353    */
 354   add_nodes (table, "1.0.0.0/16", "1.0.128.0/17", NULL);
 355   verify_next (table, "1.0.0.0/17", "1.0.128.0/17");
 356   clear_table (table);
 357
 358   /*
 359    * A search for the target reaches a node with no children. We have
 360    * to go upwards in the tree to find a successor.
 361    */
 362   add_nodes (table, "1.0.0.0/16", "1.0.0.0/24", "1.0.1.0/24",
 363              "1.0.128.0/17", NULL);
 364   verify_next (table, "1.0.1.0/25", "1.0.128.0/17");
 365   clear_table (table);
 366
 367   /*
 368    * A search for the target reaches a node where neither the node nor
 369    * the target prefix contain each other.
 370    *
 371    * In first case below the node succeeds the target.
 372    *
 373    * In the second case, the node comes before the target, so we have
 374    * to go up the tree looking for a successor.
 375    */
 376   add_nodes (table, "1.0.0.0/16", "1.0.1.0/24", NULL);
 377   verify_next (table, "1.0.0.0/24", "1.0.1.0/24");
 378   clear_table (table);
 379
 380   add_nodes (table, "1.0.0.0/16", "1.0.0.0/24", "1.0.1.0/25",
 381              "1.0.128.0/17", NULL);
 382   verify_next (table, "1.0.1.128/25", "1.0.128.0/17");
 383   clear_table (table);
 384
 385   route_table_finish (table);
 386 }
 387
 388 /*
 389  * verify_prefix_iter_cmp
 390  */
 391 static void
 392 verify_prefix_iter_cmp (const char *p1, const char *p2, int exp_result)
 393 {
 394   struct prefix_ipv4 p1_pfx, p2_pfx;
 395   int result;
 396
 397   if (str2prefix_ipv4 (p1, &p1_pfx) <= 0)
 398     {
 399       assert (0);
 400     }
 401
 402   if (str2prefix_ipv4 (p2, &p2_pfx) <= 0)
 403     {
 404       assert (0);
 405     }
 406
 407   result = route_table_prefix_iter_cmp ((struct prefix *) &p1_pfx,
 408                                         (struct prefix *) &p2_pfx);
 409
 410   printf ("Verifying cmp(%s, %s) returns %d\n", p1, p2, exp_result);
 411
 412   assert (exp_result == result);
 413
 414   /*
 415    * Also check the reverse comparision.
 416    */
 417   result = route_table_prefix_iter_cmp ((struct prefix *) &p2_pfx,
 418                                         (struct prefix *) &p1_pfx);
 419
 420   if (exp_result)
 421     {
 422       exp_result = -exp_result;
 423     }
 424
 425   printf ("Verifying cmp(%s, %s) returns %d\n", p1, p2, exp_result);
 426   assert (result == exp_result);
 427 }
 428
 429 /*
 430  * test_prefix_iter_cmp
 431  *
 432  * Tests comparision of prefixes according to order of iteration.
 433  */
 434 static void
 435 test_prefix_iter_cmp ()
 436 {
 437   printf ("\n\nTesting route_table_prefix_iter_cmp()\n");
 438
 439   verify_prefix_iter_cmp ("1.0.0.0/8", "1.0.0.0/8", 0);
 440
 441   verify_prefix_iter_cmp ("1.0.0.0/8", "1.0.0.0/16", -1);
 442
 443   verify_prefix_iter_cmp ("1.0.0.0/16", "1.128.0.0/16", -1);
 444 }
 445
 446 /*
 447  * verify_iter_with_pause
 448  *
 449  * Iterates over a tree using two methods: 'normal' iteration, and an
 450  * iterator that pauses at each node. Verifies that the two methods
 451  * yield the same results.
 452  */
 453 static void
 454 verify_iter_with_pause (struct route_table *table)
 455 {
 456   unsigned long num_nodes;
 457   struct route_node *rn, *iter_rn;
 458   route_table_iter_t iter_space;
 459   route_table_iter_t *iter = &iter_space;
 460
 461   route_table_iter_init (iter, table);
 462   num_nodes = 0;
 463
 464   for (rn = route_top (table); rn; rn = route_next (rn))
 465     {
 466       num_nodes++;
 467       route_table_iter_pause (iter);
 468
 469       assert (iter->current == NULL);
 470       if (route_table_iter_started (iter))
 471         {
 472           assert (iter->state == RT_ITER_STATE_PAUSED);
 473         }
 474       else
 475         {
 476           assert (rn == table->top);
 477           assert (iter->state == RT_ITER_STATE_INIT);
 478         }
 479
 480       iter_rn = route_table_iter_next (iter);
 481
 482       /*
 483        * Make sure both iterations return the same node.
 484        */
 485       assert (rn == iter_rn);
 486     }
 487
 488   assert (num_nodes == route_table_count (table));
 489
 490   route_table_iter_pause (iter);
 491   iter_rn = route_table_iter_next (iter);
 492
 493   assert (iter_rn == NULL);
 494   assert (iter->state == RT_ITER_STATE_DONE);
 495
 496   assert (route_table_iter_next (iter) == NULL);
 497   assert (iter->state == RT_ITER_STATE_DONE);
 498
 499   route_table_iter_cleanup (iter);
 500
 501   print_table (table);
 502   printf ("Verified pausing iteration on tree with %lu nodes\n", num_nodes);
 503 }
 504
 505 /*
 506  * test_iter_pause
 507  */
 508 static void
 509 test_iter_pause (void)
 510 {
 511   struct route_table *table;
 512   int i, num_prefixes;
 513   const char *prefixes[] = {
 514     "1.0.1.0/24",
 515     "1.0.1.0/25",
 516     "1.0.1.128/25",
 517     "1.0.2.0/24",
 518     "2.0.0.0/8"
 519   };
 520
 521   num_prefixes = sizeof (prefixes) / sizeof (prefixes[0]);
 522
 523   printf ("\n\nTesting that route_table_iter_pause() works as expected\n");
 524   table = route_table_init ();
 525   for (i = 0; i < num_prefixes; i++)
 526     {
 527       add_nodes (table, prefixes[i], NULL);
 528     }
 529
 530   verify_iter_with_pause (table);
 531
 532   clear_table (table);
 533   route_table_finish (table);
 534 }
 535
 536 /*
 537  * run_tests
 538  */
 539 static void
 540 run_tests (void)
 541 {
 542   test_prefix_iter_cmp ();
 543   test_get_next ();
 544   test_iter_pause ();
 545 }
 546
 547 /*
 548  * main
 549  */
 550 int
 551 main (void)
 552 {
 553   run_tests ();
 554 }