tests/lib/test_table.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 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 comparision.
 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 comparision 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 }