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
  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         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         }
 129 }
 130
 131 /*
 132  * print_table
 133  *
 134  * Function that prints out the internal structure of a route table.
 135  */
 136 static void print_table(struct route_table *table)
 137 {
 138         struct route_node *rn;
 139
 140         rn = table->top;
 141
 142         if (!rn) {
 143                 printf("<Empty Table>\n");
 144                 return;
 145         }
 146
 147         print_subtree(rn, "Top", 0);
 148 }
 149
 150 /*
 151  * clear_table
 152  *
 153  * Remove all nodes from the given table.
 154  */
 155 static void clear_table(struct route_table *table)
 156 {
 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);
 172         }
 173
 174         route_table_iter_cleanup(&iter);
 175
 176         assert(table->top == NULL);
 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  */
 186 static void verify_next_by_iterating(struct route_table *table,
 187                                      struct prefix *target_pfx,
 188                                      struct prefix *next_pfx)
 189 {
 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                 }
 199         }
 200
 201         if (!rn) {
 202                 assert(!next_pfx);
 203         }
 204
 205         route_table_iter_cleanup(&iter);
 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  */
 214 static void verify_next(struct route_table *table, const char *target,
 215                         const char *next)
 216 {
 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);
 257 }
 258
 259 /*
 260  * test_get_next
 261  */
 262 static void test_get_next(void)
 263 {
 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);
 360 }
 361
 362 /*
 363  * verify_prefix_iter_cmp
 364  */
 365 static void verify_prefix_iter_cmp(const char *p1, const char *p2,
 366                                    int exp_result)
 367 {
 368         struct prefix_ipv4 p1_pfx, p2_pfx;
 369         int result;
 370
 371         if (str2prefix_ipv4(p1, &p1_pfx) <= 0) {
 372                 assert(0);
 373         }
 374
 375         if (str2prefix_ipv4(p2, &p2_pfx) <= 0) {
 376                 assert(0);
 377         }
 378
 379         result = route_table_prefix_iter_cmp((struct prefix *)&p1_pfx,
 380                                              (struct prefix *)&p2_pfx);
 381
 382         printf("Verifying cmp(%s, %s) returns %d\n", p1, p2, exp_result);
 383
 384         assert(exp_result == result);
 385
 386         /*
 387          * Also check the reverse comparision.
 388          */
 389         result = route_table_prefix_iter_cmp((struct prefix *)&p2_pfx,
 390                                              (struct prefix *)&p1_pfx);
 391
 392         if (exp_result) {
 393                 exp_result = -exp_result;
 394         }
 395
 396         printf("Verifying cmp(%s, %s) returns %d\n", p1, p2, exp_result);
 397         assert(result == exp_result);
 398 }
 399
 400 /*
 401  * test_prefix_iter_cmp
 402  *
 403  * Tests comparision of prefixes according to order of iteration.
 404  */
 405 static void test_prefix_iter_cmp(void)
 406 {
 407         printf("\n\nTesting route_table_prefix_iter_cmp()\n");
 408
 409         verify_prefix_iter_cmp("1.0.0.0/8", "1.0.0.0/8", 0);
 410
 411         verify_prefix_iter_cmp("1.0.0.0/8", "1.0.0.0/16", -1);
 412
 413         verify_prefix_iter_cmp("1.0.0.0/16", "1.128.0.0/16", -1);
 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  */
 423 static void verify_iter_with_pause(struct route_table *table)
 424 {
 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);
 451         }
 452
 453         assert(num_nodes == route_table_count(table));
 454
 455         route_table_iter_pause(iter);
 456         iter_rn = route_table_iter_next(iter);
 457
 458         assert(iter_rn == NULL);
 459         assert(iter->state == RT_ITER_STATE_DONE);
 460
 461         assert(route_table_iter_next(iter) == NULL);
 462         assert(iter->state == RT_ITER_STATE_DONE);
 463
 464         route_table_iter_cleanup(iter);
 465
 466         print_table(table);
 467         printf("Verified pausing iteration on tree with %lu nodes\n",
 468                num_nodes);
 469 }
 470
 471 /*
 472  * test_iter_pause
 473  */
 474 static void test_iter_pause(void)
 475 {
 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
 481         num_prefixes = sizeof(prefixes) / sizeof(prefixes[0]);
 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);
 493 }
 494
 495 /*
 496  * run_tests
 497  */
 498 static void run_tests(void)
 499 {
 500         test_prefix_iter_cmp();
 501         test_get_next();
 502         test_iter_pause();
 503 }
 504
 505 /*
 506  * main
 507  */
 508 int main(void)
 509 {
 510         run_tests();
 511 }