tests/lib/test_table.c

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