tests/isisd/test_isis_spf.c

   1 /*
   2  * Copyright (C) 2020  NetDEF, Inc.
   3  *                     Renato Westphal
   4  *
   5  * This program is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License as published by the Free
   7  * Software Foundation; either version 2 of the License, or (at your option)
   8  * any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful, but WITHOUT
  11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  12  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
  13  * more details.
  14  *
  15  * You should have received a copy of the GNU General Public License along
  16  * with this program; see the file COPYING; if not, write to the Free Software
  17  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  18  */
  19
  20 #include <zebra.h>
  21
  22 #include <lib/version.h>
  23 #include "getopt.h"
  24 #include "thread.h"
  25 #include "vty.h"
  26 #include "command.h"
  27 #include "log.h"
  28 #include "vrf.h"
  29 #include "yang.h"
  30
  31 #include "isisd/isisd.h"
  32 #include "isisd/isis_dynhn.h"
  33 #include "isisd/isis_misc.h"
  34 #include "isisd/isis_route.h"
  35 #include "isisd/isis_spf.h"
  36 #include "isisd/isis_spf_private.h"
  37
  38 #include "test_common.h"
  39
  40 enum test_type {
  41         TEST_SPF = 1,
  42         TEST_REVERSE_SPF,
  43         TEST_LFA,
  44         TEST_RLFA,
  45         TEST_TI_LFA,
  46 };
  47
  48 #define F_DISPLAY_LSPDB 0x01
  49 #define F_IPV4_ONLY 0x02
  50 #define F_IPV6_ONLY 0x04
  51 #define F_LEVEL1_ONLY 0x08
  52 #define F_LEVEL2_ONLY 0x10
  53
  54 static struct isis *isis;
  55
  56 static void test_run_spf(struct vty *vty, const struct isis_topology *topology,
  57                          const struct isis_test_node *root,
  58                          struct isis_area *area, struct lspdb_head *lspdb,
  59                          int level, int tree, bool reverse)
  60 {
  61         struct isis_spftree *spftree;
  62         enum spf_type spf_type;
  63
  64         /* Run SPF. */
  65         spf_type = reverse ? SPF_TYPE_REVERSE : SPF_TYPE_FORWARD;
  66         spftree = isis_spftree_new(area, lspdb, root->sysid, level, tree,
  67                                    spf_type, F_SPFTREE_NO_ADJACENCIES);
  68         isis_run_spf(spftree);
  69
  70         /* Print the SPT and the corresponding routing table. */
  71         isis_print_spftree(vty, spftree);
  72         isis_print_routes(vty, spftree, false, false);
  73
  74         /* Cleanup SPF tree. */
  75         isis_spftree_del(spftree);
  76 }
  77
  78 static void test_run_lfa(struct vty *vty, const struct isis_topology *topology,
  79                          const struct isis_test_node *root,
  80                          struct isis_area *area, struct lspdb_head *lspdb,
  81                          int level, int tree,
  82                          struct lfa_protected_resource *protected_resource)
  83 {
  84         struct isis_spftree *spftree_self;
  85         uint8_t flags;
  86
  87         /* Run forward SPF in the root node. */
  88         flags = F_SPFTREE_NO_ADJACENCIES;
  89         spftree_self = isis_spftree_new(area, lspdb, root->sysid, level, tree,
  90                                         SPF_TYPE_FORWARD, flags);
  91         isis_run_spf(spftree_self);
  92
  93         /* Run forward SPF on all adjacent routers. */
  94         isis_spf_run_neighbors(spftree_self);
  95
  96         /* Compute the LFA repair paths. */
  97         isis_lfa_compute(area, NULL, spftree_self, protected_resource);
  98
  99         /* Print the SPT and the corresponding main/backup routing tables. */
 100         isis_print_spftree(vty, spftree_self);
 101         vty_out(vty, "Main:\n");
 102         isis_print_routes(vty, spftree_self, false, false);
 103         vty_out(vty, "Backup:\n");
 104         isis_print_routes(vty, spftree_self, false, true);
 105
 106         /* Cleanup everything. */
 107         isis_spftree_del(spftree_self);
 108 }
 109
 110 static void test_run_rlfa(struct vty *vty, const struct isis_topology *topology,
 111                           const struct isis_test_node *root,
 112                           struct isis_area *area, struct lspdb_head *lspdb,
 113                           int level, int tree,
 114                           struct lfa_protected_resource *protected_resource)
 115 {
 116         struct isis_spftree *spftree_self;
 117         struct isis_spftree *spftree_reverse;
 118         struct isis_spftree *spftree_pc;
 119         struct isis_spf_node *spf_node, *node;
 120         struct rlfa *rlfa;
 121         uint8_t flags;
 122
 123         /* Run forward SPF in the root node. */
 124         flags = F_SPFTREE_NO_ADJACENCIES;
 125         spftree_self = isis_spftree_new(area, lspdb, root->sysid, level, tree,
 126                                         SPF_TYPE_FORWARD, flags);
 127         isis_run_spf(spftree_self);
 128
 129         /* Run reverse SPF in the root node. */
 130         spftree_reverse = isis_spf_reverse_run(spftree_self);
 131
 132         /* Run forward SPF on all adjacent routers. */
 133         isis_spf_run_neighbors(spftree_self);
 134
 135         /* Compute the local LFA repair paths. */
 136         isis_lfa_compute(area, NULL, spftree_self, protected_resource);
 137
 138         /* Compute the remote LFA repair paths. */
 139         spftree_pc = isis_rlfa_compute(area, spftree_self, spftree_reverse, 0,
 140                                        protected_resource);
 141
 142         /* Print the extended P-space and Q-space. */
 143         vty_out(vty, "P-space (self):\n");
 144         RB_FOREACH (node, isis_spf_nodes, &spftree_pc->lfa.p_space)
 145                 vty_out(vty, " %s\n", print_sys_hostname(node->sysid));
 146         vty_out(vty, "\n");
 147         RB_FOREACH (spf_node, isis_spf_nodes, &spftree_self->adj_nodes) {
 148                 if (RB_EMPTY(isis_spf_nodes, &spf_node->lfa.p_space))
 149                         continue;
 150                 vty_out(vty, "P-space (%s):\n",
 151                         print_sys_hostname(spf_node->sysid));
 152                 RB_FOREACH (node, isis_spf_nodes, &spf_node->lfa.p_space)
 153                         vty_out(vty, " %s\n", print_sys_hostname(node->sysid));
 154                 vty_out(vty, "\n");
 155         }
 156         vty_out(vty, "Q-space:\n");
 157         RB_FOREACH (node, isis_spf_nodes, &spftree_pc->lfa.q_space)
 158                 vty_out(vty, " %s\n", print_sys_hostname(node->sysid));
 159         vty_out(vty, "\n");
 160
 161         /* Print the post-convergence SPT. */
 162         isis_print_spftree(vty, spftree_pc);
 163
 164         /*
 165          * Activate the computed RLFAs (if any) using artificial LDP labels for
 166          * the PQ nodes.
 167          */
 168         frr_each_safe (rlfa_tree, &spftree_self->lfa.remote.rlfas, rlfa) {
 169                 struct zapi_rlfa_response response = {};
 170
 171                 response.pq_label = test_topology_node_ldp_label(
 172                         topology, rlfa->pq_address);
 173                 assert(response.pq_label != MPLS_INVALID_LABEL);
 174                 isis_rlfa_activate(spftree_self, rlfa, &response);
 175         }
 176
 177         /* Print the SPT and the corresponding main/backup routing tables. */
 178         isis_print_spftree(vty, spftree_self);
 179         vty_out(vty, "Main:\n");
 180         isis_print_routes(vty, spftree_self, false, false);
 181         vty_out(vty, "Backup:\n");
 182         isis_print_routes(vty, spftree_self, false, true);
 183
 184         /* Cleanup everything. */
 185         isis_spftree_del(spftree_self);
 186         isis_spftree_del(spftree_reverse);
 187         isis_spftree_del(spftree_pc);
 188 }
 189
 190 static void test_run_ti_lfa(struct vty *vty,
 191                             const struct isis_topology *topology,
 192                             const struct isis_test_node *root,
 193                             struct isis_area *area, struct lspdb_head *lspdb,
 194                             int level, int tree,
 195                             struct lfa_protected_resource *protected_resource)
 196 {
 197         struct isis_spftree *spftree_self;
 198         struct isis_spftree *spftree_reverse;
 199         struct isis_spftree *spftree_pc;
 200         struct isis_spf_node *spf_node, *node;
 201         uint8_t flags;
 202
 203         /* Run forward SPF in the root node. */
 204         flags = F_SPFTREE_NO_ADJACENCIES;
 205         spftree_self = isis_spftree_new(area, lspdb, root->sysid, level, tree,
 206                                         SPF_TYPE_FORWARD, flags);
 207         isis_run_spf(spftree_self);
 208
 209         /* Run reverse SPF in the root node. */
 210         spftree_reverse = isis_spf_reverse_run(spftree_self);
 211
 212         /* Run forward SPF on all adjacent routers. */
 213         isis_spf_run_neighbors(spftree_self);
 214
 215         /* Compute the TI-LFA repair paths. */
 216         spftree_pc = isis_tilfa_compute(area, spftree_self, spftree_reverse,
 217                                         protected_resource);
 218
 219         /* Print the extended P-space and Q-space. */
 220         vty_out(vty, "P-space (self):\n");
 221         RB_FOREACH (node, isis_spf_nodes, &spftree_pc->lfa.p_space)
 222                 vty_out(vty, " %s\n", print_sys_hostname(node->sysid));
 223         vty_out(vty, "\n");
 224         RB_FOREACH (spf_node, isis_spf_nodes, &spftree_self->adj_nodes) {
 225                 if (RB_EMPTY(isis_spf_nodes, &spf_node->lfa.p_space))
 226                         continue;
 227                 vty_out(vty, "P-space (%s):\n",
 228                         print_sys_hostname(spf_node->sysid));
 229                 RB_FOREACH (node, isis_spf_nodes, &spf_node->lfa.p_space)
 230                         vty_out(vty, " %s\n", print_sys_hostname(node->sysid));
 231                 vty_out(vty, "\n");
 232         }
 233         vty_out(vty, "Q-space:\n");
 234         RB_FOREACH (node, isis_spf_nodes, &spftree_pc->lfa.q_space)
 235                 vty_out(vty, " %s\n", print_sys_hostname(node->sysid));
 236         vty_out(vty, "\n");
 237
 238         /*
 239          * Print the post-convergence SPT and the corresponding routing table.
 240          */
 241         isis_print_spftree(vty, spftree_pc);
 242         isis_print_routes(vty, spftree_self, false, true);
 243
 244         /* Cleanup everything. */
 245         isis_spftree_del(spftree_self);
 246         isis_spftree_del(spftree_reverse);
 247         isis_spftree_del(spftree_pc);
 248 }
 249
 250 static int test_run(struct vty *vty, const struct isis_topology *topology,
 251                     const struct isis_test_node *root, enum test_type test_type,
 252                     uint8_t flags, enum lfa_protection_type protection_type,
 253                     const char *fail_sysid_str, uint8_t fail_pseudonode_id)
 254 {
 255         struct isis_area *area;
 256         struct lfa_protected_resource protected_resource = {};
 257         uint8_t fail_id[ISIS_SYS_ID_LEN] = {};
 258
 259         /* Init topology. */
 260         memcpy(isis->sysid, root->sysid, sizeof(isis->sysid));
 261         area = isis_area_create("1", NULL);
 262         area->is_type = IS_LEVEL_1_AND_2;
 263         area->srdb.enabled = true;
 264         if (test_topology_load(topology, area, area->lspdb) != 0) {
 265                 vty_out(vty, "%% Failed to load topology\n");
 266                 return CMD_WARNING;
 267         }
 268
 269         /* Parse failed link/node. */
 270         if (fail_sysid_str) {
 271                 if (sysid2buff(fail_id, fail_sysid_str) == 0) {
 272                         struct isis_dynhn *dynhn;
 273
 274                         dynhn = dynhn_find_by_name(fail_sysid_str);
 275                         if (dynhn == NULL) {
 276                                 vty_out(vty, "Invalid system id %s\n",
 277                                         fail_sysid_str);
 278                                 return CMD_WARNING;
 279                         }
 280                         memcpy(fail_id, dynhn->id, ISIS_SYS_ID_LEN);
 281                 }
 282
 283                 protected_resource.type = protection_type;
 284                 memcpy(protected_resource.adjacency, fail_id, ISIS_SYS_ID_LEN);
 285                 LSP_PSEUDO_ID(protected_resource.adjacency) =
 286                         fail_pseudonode_id;
 287         }
 288
 289         for (int level = IS_LEVEL_1; level <= IS_LEVEL_2; level++) {
 290                 if (level == IS_LEVEL_1 && CHECK_FLAG(flags, F_LEVEL2_ONLY))
 291                         continue;
 292                 if (level == IS_LEVEL_2 && CHECK_FLAG(flags, F_LEVEL1_ONLY))
 293                         continue;
 294                 if ((root->level & level) == 0)
 295                         continue;
 296
 297                 /* Print the LDPDB. */
 298                 if (CHECK_FLAG(flags, F_DISPLAY_LSPDB))
 299                         show_isis_database_lspdb(vty, area, level - 1,
 300                                                  &area->lspdb[level - 1], NULL,
 301                                                  ISIS_UI_LEVEL_DETAIL);
 302
 303                 for (int tree = SPFTREE_IPV4; tree <= SPFTREE_IPV6; tree++) {
 304                         if (tree == SPFTREE_IPV4
 305                             && CHECK_FLAG(flags, F_IPV6_ONLY))
 306                                 continue;
 307                         if (tree == SPFTREE_IPV6
 308                             && CHECK_FLAG(flags, F_IPV4_ONLY))
 309                                 continue;
 310
 311                         switch (test_type) {
 312                         case TEST_SPF:
 313                                 test_run_spf(vty, topology, root, area,
 314                                              &area->lspdb[level - 1], level,
 315                                              tree, false);
 316                                 break;
 317                         case TEST_REVERSE_SPF:
 318                                 test_run_spf(vty, topology, root, area,
 319                                              &area->lspdb[level - 1], level,
 320                                              tree, true);
 321                                 break;
 322                         case TEST_LFA:
 323                                 test_run_lfa(vty, topology, root, area,
 324                                              &area->lspdb[level - 1], level,
 325                                              tree, &protected_resource);
 326                                 break;
 327                         case TEST_RLFA:
 328                                 test_run_rlfa(vty, topology, root, area,
 329                                               &area->lspdb[level - 1], level,
 330                                               tree, &protected_resource);
 331                                 break;
 332                         case TEST_TI_LFA:
 333                                 test_run_ti_lfa(vty, topology, root, area,
 334                                                 &area->lspdb[level - 1], level,
 335                                                 tree, &protected_resource);
 336                                 break;
 337                         }
 338                 }
 339         }
 340
 341         /* Cleanup IS-IS area. */
 342         isis_area_destroy(area);
 343
 344         /* Cleanup hostnames. */
 345         dyn_cache_cleanup_all();
 346
 347         return CMD_SUCCESS;
 348 }
 349
 350 DEFUN(test_isis, test_isis_cmd,
 351       "test isis topology (1-14) root HOSTNAME\
 352          <\
 353            spf\
 354            |reverse-spf\
 355            |lfa system-id WORD [pseudonode-id <1-255>]\
 356            |remote-lfa system-id WORD [pseudonode-id <1-255>]\
 357            |ti-lfa system-id WORD [pseudonode-id <1-255>] [node-protection]\
 358          >\
 359          [display-lspdb] [<ipv4-only|ipv6-only>] [<level-1-only|level-2-only>]",
 360       "Test command\n"
 361       "IS-IS routing protocol\n"
 362       "Test topology\n"
 363       "Test topology number\n"
 364       "SPF root\n"
 365       "SPF root hostname\n"
 366       "Normal Shortest Path First\n"
 367       "Reverse Shortest Path First\n"
 368       "Classic LFA\n"
 369       "System ID\n"
 370       "System ID\n"
 371       "Pseudonode-ID\n"
 372       "Pseudonode-ID\n"
 373       "Remote LFA\n"
 374       "System ID\n"
 375       "System ID\n"
 376       "Pseudonode-ID\n"
 377       "Pseudonode-ID\n"
 378       "Topology Independent LFA\n"
 379       "System ID\n"
 380       "System ID\n"
 381       "Pseudonode-ID\n"
 382       "Pseudonode-ID\n"
 383       "Node protection\n"
 384       "Display the LSPDB\n"
 385       "Do IPv4 processing only\n"
 386       "Do IPv6 processing only\n"
 387       "Skip L2 LSPs\n"
 388       "Skip L1 LSPs\n")
 389 {
 390         uint16_t topology_number;
 391         const struct isis_topology *topology;
 392         const struct isis_test_node *root;
 393         enum test_type test_type;
 394         enum lfa_protection_type protection_type = 0;
 395         const char *fail_sysid_str = NULL;
 396         uint8_t fail_pseudonode_id = 0;
 397         uint8_t flags = 0;
 398         int idx = 0;
 399
 400         /* Load topology. */
 401         argv_find(argv, argc, "topology", &idx);
 402         topology_number = atoi(argv[idx + 1]->arg);
 403         topology = test_topology_find(test_topologies, topology_number);
 404         if (!topology) {
 405                 vty_out(vty, "%% Topology \"%s\" not found\n",
 406                         argv[idx + 1]->arg);
 407                 return CMD_WARNING;
 408         }
 409
 410         /* Find root node. */
 411         argv_find(argv, argc, "root", &idx);
 412         root = test_topology_find_node(topology, argv[idx + 1]->arg, 0);
 413         if (!root) {
 414                 vty_out(vty, "%% Node \"%s\" not found\n", argv[idx + 1]->arg);
 415                 return CMD_WARNING;
 416         }
 417
 418         /* Parse test information. */
 419         if (argv_find(argv, argc, "spf", &idx))
 420                 test_type = TEST_SPF;
 421         else if (argv_find(argv, argc, "reverse-spf", &idx))
 422                 test_type = TEST_REVERSE_SPF;
 423         else if (argv_find(argv, argc, "lfa", &idx)) {
 424                 test_type = TEST_LFA;
 425
 426                 fail_sysid_str = argv[idx + 2]->arg;
 427                 if (argv_find(argv, argc, "pseudonode-id", &idx))
 428                         fail_pseudonode_id =
 429                                 strtoul(argv[idx + 1]->arg, NULL, 10);
 430                 protection_type = LFA_LINK_PROTECTION;
 431         } else if (argv_find(argv, argc, "remote-lfa", &idx)) {
 432                 test_type = TEST_RLFA;
 433
 434                 fail_sysid_str = argv[idx + 2]->arg;
 435                 if (argv_find(argv, argc, "pseudonode-id", &idx))
 436                         fail_pseudonode_id =
 437                                 strtoul(argv[idx + 1]->arg, NULL, 10);
 438                 protection_type = LFA_LINK_PROTECTION;
 439         } else if (argv_find(argv, argc, "ti-lfa", &idx)) {
 440                 test_type = TEST_TI_LFA;
 441
 442                 fail_sysid_str = argv[idx + 2]->arg;
 443                 if (argv_find(argv, argc, "pseudonode-id", &idx))
 444                         fail_pseudonode_id =
 445                                 strtoul(argv[idx + 1]->arg, NULL, 10);
 446                 if (argv_find(argv, argc, "node-protection", &idx))
 447                         protection_type = LFA_NODE_PROTECTION;
 448                 else
 449                         protection_type = LFA_LINK_PROTECTION;
 450         } else
 451                 return CMD_WARNING;
 452
 453         /* Parse control flags. */
 454         if (argv_find(argv, argc, "display-lspdb", &idx))
 455                 SET_FLAG(flags, F_DISPLAY_LSPDB);
 456         if (argv_find(argv, argc, "ipv4-only", &idx))
 457                 SET_FLAG(flags, F_IPV4_ONLY);
 458         else if (argv_find(argv, argc, "ipv6-only", &idx))
 459                 SET_FLAG(flags, F_IPV6_ONLY);
 460         if (argv_find(argv, argc, "level-1-only", &idx))
 461                 SET_FLAG(flags, F_LEVEL1_ONLY);
 462         else if (argv_find(argv, argc, "level-2-only", &idx))
 463                 SET_FLAG(flags, F_LEVEL2_ONLY);
 464
 465         return test_run(vty, topology, root, test_type, flags, protection_type,
 466                         fail_sysid_str, fail_pseudonode_id);
 467 }
 468
 469 static void vty_do_exit(int isexit)
 470 {
 471         printf("\nend.\n");
 472
 473         isis_finish(isis);
 474         cmd_terminate();
 475         vty_terminate();
 476         yang_terminate();
 477         thread_master_free(master);
 478
 479         log_memstats(stderr, "test-isis-spf");
 480         if (!isexit)
 481                 exit(0);
 482 }
 483
 484 struct option longopts[] = {{"help", no_argument, NULL, 'h'},
 485                             {"debug", no_argument, NULL, 'd'},
 486                             {0}};
 487
 488 /* Help information display. */
 489 static void usage(char *progname, int status)
 490 {
 491         if (status != 0)
 492                 fprintf(stderr, "Try `%s --help' for more information.\n",
 493                         progname);
 494         else {
 495                 printf("Usage : %s [OPTION...]\n\
 496 isisd SPF test program.\n\n\
 497 -u, --debug        Enable debugging\n\
 498 -h, --help         Display this help and exit\n\
 499 \n\
 500 Report bugs to %s\n",
 501                        progname, FRR_BUG_ADDRESS);
 502         }
 503         exit(status);
 504 }
 505
 506 int main(int argc, char **argv)
 507 {
 508         char *p;
 509         char *progname;
 510         struct thread thread;
 511         bool debug = false;
 512
 513         /* Set umask before anything for security */
 514         umask(0027);
 515
 516         /* get program name */
 517         progname = ((p = strrchr(argv[0], '/')) ? ++p : argv[0]);
 518
 519         while (1) {
 520                 int opt;
 521
 522                 opt = getopt_long(argc, argv, "hd", longopts, 0);
 523
 524                 if (opt == EOF)
 525                         break;
 526
 527                 switch (opt) {
 528                 case 0:
 529                         break;
 530                 case 'd':
 531                         debug = true;
 532                         break;
 533                 case 'h':
 534                         usage(progname, 0);
 535                         break;
 536                 default:
 537                         usage(progname, 1);
 538                         break;
 539                 }
 540         }
 541
 542         /* master init. */
 543         master = thread_master_create(NULL);
 544         isis_master_init(master);
 545
 546         /* Library inits. */
 547         cmd_init(1);
 548         cmd_hostname_set("test");
 549         vty_init(master, false);
 550         yang_init(true);
 551         if (debug)
 552                 zlog_aux_init("NONE: ", LOG_DEBUG);
 553         else
 554                 zlog_aux_init("NONE: ", ZLOG_DISABLED);
 555
 556         /* IS-IS inits. */
 557         yang_module_load("frr-isisd");
 558         isis = isis_new(VRF_DEFAULT_NAME);
 559         listnode_add(im->isis, isis);
 560         SET_FLAG(im->options, F_ISIS_UNIT_TEST);
 561         debug_spf_events |= DEBUG_SPF_EVENTS;
 562         debug_lfa |= DEBUG_LFA;
 563         debug_events |= DEBUG_EVENTS;
 564         debug_rte_events |= DEBUG_RTE_EVENTS;
 565
 566         /* Install test command. */
 567         install_element(VIEW_NODE, &test_isis_cmd);
 568
 569         /* Read input from .in file. */
 570         vty_stdio(vty_do_exit);
 571
 572         /* Fetch next active thread. */
 573         while (thread_fetch(master, &thread))
 574                 thread_call(&thread);
 575
 576         /* Not reached. */
 577         exit(0);
 578 }