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