[mirror_frr.git] / tests / isisd / test_isis_spf.c

// SPDX-License-Identifier: GPL-2.0-or-later
/*
 * Copyright (C) 2020  NetDEF, Inc.
 *                     Renato Westphal
 */

#include <zebra.h>

#include <lib/version.h>
#include "getopt.h"
#include "frrevent.h"
#include "vty.h"
#include "command.h"
#include "log.h"
#include "vrf.h"
#include "yang.h"

#include "isisd/isisd.h"
#include "isisd/isis_dynhn.h"
#include "isisd/isis_misc.h"
#include "isisd/isis_route.h"
#include "isisd/isis_spf.h"
#include "isisd/isis_spf_private.h"

#include "test_common.h"

enum test_type {
	TEST_SPF = 1,
	TEST_REVERSE_SPF,
	TEST_LFA,
	TEST_RLFA,
	TEST_TI_LFA,
};

#define F_DISPLAY_LSPDB 0x01
#define F_IPV4_ONLY 0x02
#define F_IPV6_ONLY 0x04
#define F_LEVEL1_ONLY 0x08
#define F_LEVEL2_ONLY 0x10

static void test_run_spf(struct vty *vty, const struct isis_topology *topology,
			 const struct isis_test_node *root,
			 struct isis_area *area, struct lspdb_head *lspdb,
			 int level, int tree, bool reverse)
{
	struct isis_spftree *spftree;
	enum spf_type spf_type;

	/* Run SPF. */
	spf_type = reverse ? SPF_TYPE_REVERSE : SPF_TYPE_FORWARD;
	spftree = isis_spftree_new(area, lspdb, root->sysid, level, tree,
				   spf_type, F_SPFTREE_NO_ADJACENCIES,
				   SR_ALGORITHM_SPF);
	isis_run_spf(spftree);

	/* Print the SPT and the corresponding routing table. */
	isis_print_spftree(vty, spftree);
	isis_print_routes(vty, spftree, NULL, false, false);

	/* Cleanup SPF tree. */
	isis_spftree_del(spftree);
}

static void test_run_lfa(struct vty *vty, const struct isis_topology *topology,
			 const struct isis_test_node *root,
			 struct isis_area *area, struct lspdb_head *lspdb,
			 int level, int tree,
			 struct lfa_protected_resource *protected_resource)
{
	struct isis_spftree *spftree_self;
	uint8_t flags;

	/* Run forward SPF in the root node. */
	flags = F_SPFTREE_NO_ADJACENCIES;
	spftree_self =
		isis_spftree_new(area, lspdb, root->sysid, level, tree,
				 SPF_TYPE_FORWARD, flags, SR_ALGORITHM_SPF);
	isis_run_spf(spftree_self);

	/* Run forward SPF on all adjacent routers. */
	isis_spf_run_neighbors(spftree_self);

	/* Compute the LFA repair paths. */
	isis_lfa_compute(area, NULL, spftree_self, protected_resource);

	/* Print the SPT and the corresponding main/backup routing tables. */
	isis_print_spftree(vty, spftree_self);
	vty_out(vty, "Main:\n");
	isis_print_routes(vty, spftree_self, NULL, false, false);
	vty_out(vty, "Backup:\n");
	isis_print_routes(vty, spftree_self, NULL, false, true);

	/* Cleanup everything. */
	isis_spftree_del(spftree_self);
}

static void test_run_rlfa(struct vty *vty, const struct isis_topology *topology,
			  const struct isis_test_node *root,
			  struct isis_area *area, struct lspdb_head *lspdb,
			  int level, int tree,
			  struct lfa_protected_resource *protected_resource)
{
	struct isis_spftree *spftree_self;
	struct isis_spftree *spftree_reverse;
	struct isis_spftree *spftree_pc;
	struct isis_spf_node *spf_node, *node;
	struct rlfa *rlfa;
	uint8_t flags;

	/* Run forward SPF in the root node. */
	flags = F_SPFTREE_NO_ADJACENCIES;
	spftree_self =
		isis_spftree_new(area, lspdb, root->sysid, level, tree,
				 SPF_TYPE_FORWARD, flags, SR_ALGORITHM_SPF);
	isis_run_spf(spftree_self);

	/* Run reverse SPF in the root node. */
	spftree_reverse = isis_spf_reverse_run(spftree_self);

	/* Run forward SPF on all adjacent routers. */
	isis_spf_run_neighbors(spftree_self);

	/* Compute the local LFA repair paths. */
	isis_lfa_compute(area, NULL, spftree_self, protected_resource);

	/* Compute the remote LFA repair paths. */
	spftree_pc = isis_rlfa_compute(area, spftree_self, spftree_reverse, 0,
				       protected_resource);

	/* Print the extended P-space and Q-space. */
	vty_out(vty, "P-space (self):\n");
	RB_FOREACH (node, isis_spf_nodes, &spftree_pc->lfa.p_space)
		vty_out(vty, " %s\n", print_sys_hostname(node->sysid));
	vty_out(vty, "\n");
	RB_FOREACH (spf_node, isis_spf_nodes, &spftree_self->adj_nodes) {
		if (RB_EMPTY(isis_spf_nodes, &spf_node->lfa.p_space))
			continue;
		vty_out(vty, "P-space (%s):\n",
			print_sys_hostname(spf_node->sysid));
		RB_FOREACH (node, isis_spf_nodes, &spf_node->lfa.p_space)
			vty_out(vty, " %s\n", print_sys_hostname(node->sysid));
		vty_out(vty, "\n");
	}
	vty_out(vty, "Q-space:\n");
	RB_FOREACH (node, isis_spf_nodes, &spftree_pc->lfa.q_space)
		vty_out(vty, " %s\n", print_sys_hostname(node->sysid));
	vty_out(vty, "\n");

	/* Print the post-convergence SPT. */
	isis_print_spftree(vty, spftree_pc);

	/*
	 * Activate the computed RLFAs (if any) using artificial LDP labels for
	 * the PQ nodes.
	 */
	frr_each_safe (rlfa_tree, &spftree_self->lfa.remote.rlfas, rlfa) {
		struct zapi_rlfa_response response = {};

		response.pq_label = test_topology_node_ldp_label(
			topology, rlfa->pq_address);
		assert(response.pq_label != MPLS_INVALID_LABEL);
		isis_rlfa_activate(spftree_self, rlfa, &response);
	}

	/* Print the SPT and the corresponding main/backup routing tables. */
	isis_print_spftree(vty, spftree_self);
	vty_out(vty, "Main:\n");
	isis_print_routes(vty, spftree_self, NULL, false, false);
	vty_out(vty, "Backup:\n");
	isis_print_routes(vty, spftree_self, NULL, false, true);

	/* Cleanup everything. */
	isis_spftree_del(spftree_self);
	isis_spftree_del(spftree_reverse);
	isis_spftree_del(spftree_pc);
}

static void test_run_ti_lfa(struct vty *vty,
			    const struct isis_topology *topology,
			    const struct isis_test_node *root,
			    struct isis_area *area, struct lspdb_head *lspdb,
			    int level, int tree,
			    struct lfa_protected_resource *protected_resource)
{
	struct isis_spftree *spftree_self;
	struct isis_spftree *spftree_reverse;
	struct isis_spftree *spftree_pc;
	struct isis_spf_node *spf_node, *node;
	uint8_t flags;

	/* Run forward SPF in the root node. */
	flags = F_SPFTREE_NO_ADJACENCIES;
	spftree_self =
		isis_spftree_new(area, lspdb, root->sysid, level, tree,
				 SPF_TYPE_FORWARD, flags, SR_ALGORITHM_SPF);
	isis_run_spf(spftree_self);

	/* Run reverse SPF in the root node. */
	spftree_reverse = isis_spf_reverse_run(spftree_self);

	/* Run forward SPF on all adjacent routers. */
	isis_spf_run_neighbors(spftree_self);

	/* Compute the TI-LFA repair paths. */
	spftree_pc = isis_tilfa_compute(area, spftree_self, spftree_reverse,
					protected_resource);

	/* Print the extended P-space and Q-space. */
	vty_out(vty, "P-space (self):\n");
	RB_FOREACH (node, isis_spf_nodes, &spftree_pc->lfa.p_space)
		vty_out(vty, " %s\n", print_sys_hostname(node->sysid));
	vty_out(vty, "\n");
	RB_FOREACH (spf_node, isis_spf_nodes, &spftree_self->adj_nodes) {
		if (RB_EMPTY(isis_spf_nodes, &spf_node->lfa.p_space))
			continue;
		vty_out(vty, "P-space (%s):\n",
			print_sys_hostname(spf_node->sysid));
		RB_FOREACH (node, isis_spf_nodes, &spf_node->lfa.p_space)
			vty_out(vty, " %s\n", print_sys_hostname(node->sysid));
		vty_out(vty, "\n");
	}
	vty_out(vty, "Q-space:\n");
	RB_FOREACH (node, isis_spf_nodes, &spftree_pc->lfa.q_space)
		vty_out(vty, " %s\n", print_sys_hostname(node->sysid));
	vty_out(vty, "\n");

	/*
	 * Print the post-convergence SPT and the corresponding routing table.
	 */
	isis_print_spftree(vty, spftree_pc);
	isis_print_routes(vty, spftree_self, NULL, false, true);

	/* Cleanup everything. */
	isis_spftree_del(spftree_self);
	isis_spftree_del(spftree_reverse);
	isis_spftree_del(spftree_pc);
}

static int test_run(struct vty *vty, const struct isis_topology *topology,
		    const struct isis_test_node *root, enum test_type test_type,
		    uint8_t flags, enum lfa_protection_type protection_type,
		    const char *fail_sysid_str, uint8_t fail_pseudonode_id)
{
	struct isis_area *area;
	struct lfa_protected_resource protected_resource = {};
	uint8_t fail_id[ISIS_SYS_ID_LEN] = {};

	/* Init topology. */
	area = isis_area_create("1", NULL);
	memcpy(area->isis->sysid, root->sysid, sizeof(area->isis->sysid));
	area->is_type = IS_LEVEL_1_AND_2;
	area->srdb.enabled = true;
	if (test_topology_load(topology, area, area->lspdb) != 0) {
		vty_out(vty, "%% Failed to load topology\n");
		return CMD_WARNING;
	}

	/* Parse failed link/node. */
	if (fail_sysid_str) {
		if (sysid2buff(fail_id, fail_sysid_str) == 0) {
			struct isis_dynhn *dynhn;

			dynhn = dynhn_find_by_name(area->isis, fail_sysid_str);
			if (dynhn == NULL) {
				vty_out(vty, "Invalid system id %s\n",
					fail_sysid_str);
				return CMD_WARNING;
			}
			memcpy(fail_id, dynhn->id, ISIS_SYS_ID_LEN);
		}

		protected_resource.type = protection_type;
		memcpy(protected_resource.adjacency, fail_id, ISIS_SYS_ID_LEN);
		LSP_PSEUDO_ID(protected_resource.adjacency) =
			fail_pseudonode_id;
	}

	for (int level = IS_LEVEL_1; level <= IS_LEVEL_2; level++) {
		if (level == IS_LEVEL_1 && CHECK_FLAG(flags, F_LEVEL2_ONLY))
			continue;
		if (level == IS_LEVEL_2 && CHECK_FLAG(flags, F_LEVEL1_ONLY))
			continue;
		if ((root->level & level) == 0)
			continue;

		/* Print the LDPDB. */
		if (CHECK_FLAG(flags, F_DISPLAY_LSPDB))
			show_isis_database_lspdb_vty(vty, area, level - 1,
						 &area->lspdb[level - 1], NULL,
						 ISIS_UI_LEVEL_DETAIL);

		for (int tree = SPFTREE_IPV4; tree <= SPFTREE_IPV6; tree++) {
			if (tree == SPFTREE_IPV4
			    && CHECK_FLAG(flags, F_IPV6_ONLY))
				continue;
			if (tree == SPFTREE_IPV6
			    && CHECK_FLAG(flags, F_IPV4_ONLY))
				continue;

			switch (test_type) {
			case TEST_SPF:
				test_run_spf(vty, topology, root, area,
					     &area->lspdb[level - 1], level,
					     tree, false);
				break;
			case TEST_REVERSE_SPF:
				test_run_spf(vty, topology, root, area,
					     &area->lspdb[level - 1], level,
					     tree, true);
				break;
			case TEST_LFA:
				test_run_lfa(vty, topology, root, area,
					     &area->lspdb[level - 1], level,
					     tree, &protected_resource);
				break;
			case TEST_RLFA:
				test_run_rlfa(vty, topology, root, area,
					      &area->lspdb[level - 1], level,
					      tree, &protected_resource);
				break;
			case TEST_TI_LFA:
				test_run_ti_lfa(vty, topology, root, area,
						&area->lspdb[level - 1], level,
						tree, &protected_resource);
				break;
			}
		}
	}

	/* Cleanup IS-IS area. */
	isis_area_destroy(area);

	return CMD_SUCCESS;
}

DEFUN(test_isis, test_isis_cmd,
      "test isis topology (1-14) root HOSTNAME\
         <\
	   spf\
	   |reverse-spf\
	   |lfa system-id WORD [pseudonode-id <1-255>]\
	   |remote-lfa system-id WORD [pseudonode-id <1-255>]\
	   |ti-lfa system-id WORD [pseudonode-id <1-255>] [node-protection]\
	 >\
	 [display-lspdb] [<ipv4-only|ipv6-only>] [<level-1-only|level-2-only>]",
      "Test command\n"
      "IS-IS routing protocol\n"
      "Test topology\n"
      "Test topology number\n"
      "SPF root\n"
      "SPF root hostname\n"
      "Normal Shortest Path First\n"
      "Reverse Shortest Path First\n"
      "Classic LFA\n"
      "System ID\n"
      "System ID\n"
      "Pseudonode-ID\n"
      "Pseudonode-ID\n"
      "Remote LFA\n"
      "System ID\n"
      "System ID\n"
      "Pseudonode-ID\n"
      "Pseudonode-ID\n"
      "Topology Independent LFA\n"
      "System ID\n"
      "System ID\n"
      "Pseudonode-ID\n"
      "Pseudonode-ID\n"
      "Node protection\n"
      "Display the LSPDB\n"
      "Do IPv4 processing only\n"
      "Do IPv6 processing only\n"
      "Skip L2 LSPs\n"
      "Skip L1 LSPs\n")
{
	uint16_t topology_number;
	const struct isis_topology *topology;
	const struct isis_test_node *root;
	enum test_type test_type;
	enum lfa_protection_type protection_type = 0;
	const char *fail_sysid_str = NULL;
	uint8_t fail_pseudonode_id = 0;
	uint8_t flags = 0;
	int idx = 0;

	/* Load topology. */
	argv_find(argv, argc, "topology", &idx);
	topology_number = atoi(argv[idx + 1]->arg);
	topology = test_topology_find(test_topologies, topology_number);
	if (!topology) {
		vty_out(vty, "%% Topology \"%s\" not found\n",
			argv[idx + 1]->arg);
		return CMD_WARNING;
	}

	/* Find root node. */
	argv_find(argv, argc, "root", &idx);
	root = test_topology_find_node(topology, argv[idx + 1]->arg, 0);
	if (!root) {
		vty_out(vty, "%% Node \"%s\" not found\n", argv[idx + 1]->arg);
		return CMD_WARNING;
	}

	/* Parse test information. */
	if (argv_find(argv, argc, "spf", &idx))
		test_type = TEST_SPF;
	else if (argv_find(argv, argc, "reverse-spf", &idx))
		test_type = TEST_REVERSE_SPF;
	else if (argv_find(argv, argc, "lfa", &idx)) {
		test_type = TEST_LFA;

		fail_sysid_str = argv[idx + 2]->arg;
		if (argv_find(argv, argc, "pseudonode-id", &idx))
			fail_pseudonode_id =
				strtoul(argv[idx + 1]->arg, NULL, 10);
		protection_type = LFA_LINK_PROTECTION;
	} else if (argv_find(argv, argc, "remote-lfa", &idx)) {
		test_type = TEST_RLFA;

		fail_sysid_str = argv[idx + 2]->arg;
		if (argv_find(argv, argc, "pseudonode-id", &idx))
			fail_pseudonode_id =
				strtoul(argv[idx + 1]->arg, NULL, 10);
		protection_type = LFA_LINK_PROTECTION;
	} else if (argv_find(argv, argc, "ti-lfa", &idx)) {
		test_type = TEST_TI_LFA;

		fail_sysid_str = argv[idx + 2]->arg;
		if (argv_find(argv, argc, "pseudonode-id", &idx))
			fail_pseudonode_id =
				strtoul(argv[idx + 1]->arg, NULL, 10);
		if (argv_find(argv, argc, "node-protection", &idx))
			protection_type = LFA_NODE_PROTECTION;
		else
			protection_type = LFA_LINK_PROTECTION;
	} else
		return CMD_WARNING;

	/* Parse control flags. */
	if (argv_find(argv, argc, "display-lspdb", &idx))
		SET_FLAG(flags, F_DISPLAY_LSPDB);
	if (argv_find(argv, argc, "ipv4-only", &idx))
		SET_FLAG(flags, F_IPV4_ONLY);
	else if (argv_find(argv, argc, "ipv6-only", &idx))
		SET_FLAG(flags, F_IPV6_ONLY);
	if (argv_find(argv, argc, "level-1-only", &idx))
		SET_FLAG(flags, F_LEVEL1_ONLY);
	else if (argv_find(argv, argc, "level-2-only", &idx))
		SET_FLAG(flags, F_LEVEL2_ONLY);

	return test_run(vty, topology, root, test_type, flags, protection_type,
			fail_sysid_str, fail_pseudonode_id);
}

static void vty_do_exit(int isexit)
{
	printf("\nend.\n");

	cmd_terminate();
	vty_terminate();
	yang_terminate();
	event_master_free(master);

	log_memstats(stderr, "test-isis-spf");
	if (!isexit)
		exit(0);
}

struct option longopts[] = {{"help", no_argument, NULL, 'h'},
			    {"debug", no_argument, NULL, 'd'},
			    {0}};

/* Help information display. */
static void usage(char *progname, int status)
{
	if (status != 0)
		fprintf(stderr, "Try `%s --help' for more information.\n",
			progname);
	else {
		printf("Usage : %s [OPTION...]\n\
isisd SPF test program.\n\n\
-u, --debug        Enable debugging\n\
-h, --help         Display this help and exit\n\
\n\
Report bugs to %s\n",
		       progname, FRR_BUG_ADDRESS);
	}
	exit(status);
}

int main(int argc, char **argv)
{
	char *p;
	char *progname;
	struct event thread;
	bool debug = false;

	/* Set umask before anything for security */
	umask(0027);

	/* get program name */
	progname = ((p = strrchr(argv[0], '/')) ? ++p : argv[0]);

	while (1) {
		int opt;

		opt = getopt_long(argc, argv, "hd", longopts, 0);

		if (opt == EOF)
			break;

		switch (opt) {
		case 0:
			break;
		case 'd':
			debug = true;
			break;
		case 'h':
			usage(progname, 0);
			break;
		default:
			usage(progname, 1);
			break;
		}
	}

	/* master init. */
	master = event_master_create(NULL);
	isis_master_init(master);

	/* Library inits. */
	cmd_init(1);
	cmd_hostname_set("test");
	vty_init(master, false);
	yang_init(true, false);
	if (debug)
		zlog_aux_init("NONE: ", LOG_DEBUG);
	else
		zlog_aux_init("NONE: ", ZLOG_DISABLED);

	/* IS-IS inits. */
	yang_module_load("frr-isisd");
	SET_FLAG(im->options, F_ISIS_UNIT_TEST);
	debug_spf_events |= DEBUG_SPF_EVENTS;
	debug_lfa |= DEBUG_LFA;
	debug_events |= DEBUG_EVENTS;
	debug_rte_events |= DEBUG_RTE_EVENTS;

	/* Install test command. */
	install_element(VIEW_NODE, &test_isis_cmd);

	/* Read input from .in file. */
	vty_stdio(vty_do_exit);

	/* Fetch next active thread. */
	while (event_fetch(master, &thread))
		event_call(&thread);

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