Adding upstream version 8.4.4.upstream/8.4.4upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

9 files changed, 1343 insertions, 0 deletions

diff --git a/tests/ospfd/.gitignore b/tests/ospfd/.gitignore
new file mode 100644
index 0000000..c659b64
--- /dev/null
+++ b/tests/ospfd/.gitignore
@@ -0,0 +1,3 @@
+/*_afl/*
+test_ospf_spf
+core
diff --git a/tests/ospfd/common.c b/tests/ospfd/common.c
new file mode 100644
index 0000000..eb30c40
--- /dev/null
+++ b/tests/ospfd/common.c
@@ -0,0 +1,248 @@
+#include <zebra.h>
+
+#include "lib/stream.h"
+#include "lib/vty.h"
+#include "lib/mpls.h"
+#include "lib/if.h"
+#include "lib/table.h"
+
+#include "ospfd/ospfd.h"
+#include "ospfd/ospf_route.h"
+#include "ospfd/ospf_spf.h"
+#include "ospfd/ospf_flood.h"
+#include "ospfd/ospf_lsa.h"
+#include "ospfd/ospf_lsdb.h"
+#include "ospfd/ospf_interface.h"
+#include "ospfd/ospf_sr.h"
+
+#include "common.h"
+
+struct thread_master *master;
+struct zebra_privs_t ospfd_privs;
+
+
+struct ospf_topology *test_find_topology(const char *name)
+{
+	if (strmatch(name, "topo1"))
+		return &topo1;
+	else if (strmatch(name, "topo2"))
+		return &topo2;
+	else if (strmatch(name, "topo3"))
+		return &topo3;
+	else if (strmatch(name, "topo4"))
+		return &topo4;
+	else if (strmatch(name, "topo5"))
+		return &topo5;
+
+	return NULL;
+}
+
+int sort_paths(const void **path1, const void **path2)
+{
+	const struct ospf_path *p1 = *path1;
+	const struct ospf_path *p2 = *path2;
+
+	return (p1->nexthop.s_addr - p2->nexthop.s_addr);
+}
+
+void print_route_table(struct vty *vty, struct route_table *rt)
+{
+	struct route_node *rn;
+	struct ospf_route * or ;
+	struct listnode *pnode;
+	struct ospf_path *path;
+	struct mpls_label_stack *label_stack;
+	char buf[MPLS_LABEL_STRLEN];
+
+	for (rn = route_top(rt); rn; rn = route_next(rn)) {
+		if ((or = rn->info) == NULL)
+			continue;
+
+		vty_out(vty, "N %-18pFX %-15pI4 %d\n", &rn->p,
+			& or->u.std.area_id, or->cost);
+
+		list_sort(or->paths, sort_paths);
+
+		for (ALL_LIST_ELEMENTS_RO(or->paths, pnode, path)) {
+			if (path->nexthop.s_addr == 0)
+				continue;
+
+			vty_out(vty, "  -> %pI4 with adv router %pI4",
+				&path->nexthop, &path->adv_router);
+
+			if (path->srni.backup_label_stack) {
+				label_stack = path->srni.backup_label_stack;
+				mpls_label2str(label_stack->num_labels,
+					       label_stack->label, buf,
+					       MPLS_LABEL_STRLEN, true);
+				vty_out(vty, " and backup path %s", buf);
+			}
+			vty_out(vty, "\n");
+		}
+	}
+}
+
+struct ospf_test_node *test_find_node(struct ospf_topology *topology,
+				      const char *hostname)
+{
+	for (int i = 0; topology->nodes[i].hostname[0]; i++)
+		if (strmatch(hostname, topology->nodes[i].hostname))
+			return &topology->nodes[i];
+
+	return NULL;
+}
+
+static void inject_router_lsa(struct vty *vty, struct ospf *ospf,
+			      struct ospf_topology *topology,
+			      struct ospf_test_node *root,
+			      struct ospf_test_node *tnode)
+{
+	struct ospf_area *area;
+	struct in_addr router_id;
+	struct in_addr adj_router_id;
+	struct prefix_ipv4 prefix;
+	struct in_addr data;
+	struct stream *s;
+	struct lsa_header *lsah;
+	struct ospf_lsa *new;
+	int length;
+	unsigned long putp;
+	uint16_t link_count;
+	struct ospf_test_node *tfound_adj_node;
+	struct ospf_test_adj *tadj;
+	bool is_self_lsa = false;
+
+	area = ospf->backbone;
+	inet_aton(tnode->router_id, &router_id);
+
+	if (strncmp(root->router_id, tnode->router_id, 256) == 0)
+		is_self_lsa = true;
+
+	s = stream_new(OSPF_MAX_LSA_SIZE);
+	lsa_header_set(s, LSA_OPTIONS_GET(area) | LSA_OPTIONS_NSSA_GET(area),
+		       OSPF_ROUTER_LSA, router_id, router_id);
+
+	stream_putc(s, router_lsa_flags(area));
+	stream_putc(s, 0);
+
+	putp = stream_get_endp(s);
+	stream_putw(s, 0);
+
+	for (link_count = 0; tnode->adjacencies[link_count].hostname[0];
+	     link_count++) {
+		tadj = &tnode->adjacencies[link_count];
+		tfound_adj_node = test_find_node(topology, tadj->hostname);
+		str2prefix_ipv4(tnode->adjacencies[link_count].network,
+				&prefix);
+
+		inet_aton(tfound_adj_node->router_id, &adj_router_id);
+		data.s_addr = prefix.prefix.s_addr;
+		link_info_set(&s, adj_router_id, data,
+			      LSA_LINK_TYPE_POINTOPOINT, 0, tadj->metric);
+
+		masklen2ip(prefix.prefixlen, &data);
+		link_info_set(&s, prefix.prefix, data, LSA_LINK_TYPE_STUB, 0,
+			      tadj->metric);
+	}
+
+	/* Don't forget the node itself (just a stub) */
+	str2prefix_ipv4(tnode->router_id, &prefix);
+	data.s_addr = 0xffffffff;
+	link_info_set(&s, prefix.prefix, data, LSA_LINK_TYPE_STUB, 0, 0);
+
+	/* Take twice the link count (for P2P and stub) plus the local stub */
+	stream_putw_at(s, putp, (2 * link_count) + 1);
+
+	length = stream_get_endp(s);
+	lsah = (struct lsa_header *)STREAM_DATA(s);
+	lsah->length = htons(length);
+
+	new = ospf_lsa_new_and_data(length);
+	new->area = area;
+	new->vrf_id = area->ospf->vrf_id;
+
+	if (is_self_lsa)
+		SET_FLAG(new->flags, OSPF_LSA_SELF | OSPF_LSA_SELF_CHECKED);
+
+	memcpy(new->data, lsah, length);
+	stream_free(s);
+
+	ospf_lsdb_add(area->lsdb, new);
+
+	if (is_self_lsa) {
+		ospf_lsa_unlock(&area->router_lsa_self);
+		area->router_lsa_self = ospf_lsa_lock(new);
+	}
+}
+
+static void inject_sr_db_entry(struct vty *vty, struct ospf_test_node *tnode,
+			       struct ospf_topology *topology)
+{
+	struct ospf_test_node *tfound_adj_node;
+	struct ospf_test_adj *tadj;
+	struct in_addr router_id;
+	struct in_addr remote_id;
+	struct sr_node *srn;
+	struct sr_prefix *srp;
+	struct sr_link *srl;
+	int link_count;
+
+	inet_aton(tnode->router_id, &router_id);
+
+	srn = ospf_sr_node_create(&router_id);
+
+	srn->srgb.range_size = 8000;
+	srn->srgb.lower_bound = 16000;
+	srn->msd = 16;
+
+	srn->srlb.range_size = 1000;
+	srn->srlb.lower_bound = 15000;
+
+	/* Prefix SID */
+	srp = XCALLOC(MTYPE_OSPF_SR_PARAMS, sizeof(struct sr_prefix));
+	srp->adv_router = router_id;
+	srp->sid = tnode->label;
+	srp->srn = srn;
+
+	listnode_add(srn->ext_prefix, srp);
+
+	/* Adjacency SIDs for all adjacencies */
+	for (link_count = 0; tnode->adjacencies[link_count].hostname[0];
+	     link_count++) {
+		tadj = &tnode->adjacencies[link_count];
+		tfound_adj_node = test_find_node(topology, tadj->hostname);
+
+		srl = XCALLOC(MTYPE_OSPF_SR_PARAMS, sizeof(struct sr_link));
+		srl->adv_router = router_id;
+
+		inet_aton(tfound_adj_node->router_id, &remote_id);
+		srl->remote_id = remote_id;
+
+		srl->type = ADJ_SID;
+		srl->sid[0] = srn->srlb.lower_bound + tadj->label;
+		srl->srn = srn;
+
+		listnode_add(srn->ext_link, srl);
+	}
+}
+
+int topology_load(struct vty *vty, struct ospf_topology *topology,
+		  struct ospf_test_node *root, struct ospf *ospf)
+{
+	struct ospf_test_node *tnode;
+
+	for (int i = 0; topology->nodes[i].hostname[0]; i++) {
+		tnode = &topology->nodes[i];
+
+		/* Inject a router LSA for each node, used for SPF */
+		inject_router_lsa(vty, ospf, topology, root, tnode);
+
+		/*
+		 * SR information could also be inected via LSAs, but directly
+		 * filling the SR DB with labels is just easier.
+		 */
+		inject_sr_db_entry(vty, tnode, topology);
+	}
+
+	return 0;
+}
diff --git a/tests/ospfd/common.h b/tests/ospfd/common.h
new file mode 100644
index 0000000..6d3e63e
--- /dev/null
+++ b/tests/ospfd/common.h
@@ -0,0 +1,47 @@
+#ifndef _COMMON_OSPF_H
+#define _COMMON_OSPF_H
+
+#define MAX_ADJACENCIES 8
+#define MAX_NODES 12
+
+struct ospf_test_adj {
+	char hostname[256];
+	char network[256];
+	uint32_t metric;
+	mpls_label_t label;
+};
+
+struct ospf_test_node {
+	char hostname[256];
+	const char *router_id;
+	mpls_label_t label;
+	struct ospf_test_adj adjacencies[MAX_ADJACENCIES + 1];
+};
+
+struct ospf_topology {
+	struct ospf_test_node nodes[MAX_NODES + 1];
+};
+
+/* Prototypes. */
+extern struct ospf_topology *test_find_topology(const char *name);
+extern struct ospf_test_node *test_find_node(struct ospf_topology *topology,
+					     const char *hostname);
+extern int topology_load(struct vty *vty, struct ospf_topology *topology,
+			 struct ospf_test_node *root, struct ospf *ospf);
+
+/* Global variables. */
+extern struct thread_master *master;
+extern struct ospf_topology topo1;
+extern struct ospf_topology topo2;
+extern struct ospf_topology topo3;
+extern struct ospf_topology topo4;
+extern struct ospf_topology topo5;
+extern struct zebra_privs_t ospfd_privs;
+
+/* For stable order in unit tests */
+extern int sort_paths(const void **path1, const void **path2);
+
+/* Print the routing table */
+extern void print_route_table(struct vty *vty, struct route_table *rt);
+
+#endif /* _COMMON_OSPF_H */
diff --git a/tests/ospfd/subdir.am b/tests/ospfd/subdir.am
new file mode 100644
index 0000000..5ed5b9d
--- /dev/null
+++ b/tests/ospfd/subdir.am
@@ -0,0 +1,21 @@
+if !OSPFD
+PYTEST_IGNORE += --ignore=ospfd/
+endif
+OSPFD_TEST_LDADD = ospfd/libfrrospf.a $(ALL_TESTS_LDADD)
+noinst_HEADERS += \
+	tests/ospfd/common.h \
+	# end
+
+
+if OSPFD
+check_PROGRAMS += tests/ospfd/test_ospf_spf
+endif
+tests_ospfd_test_ospf_spf_CFLAGS = $(TESTS_CFLAGS)
+tests_ospfd_test_ospf_spf_CPPFLAGS = $(TESTS_CPPFLAGS)
+tests_ospfd_test_ospf_spf_LDADD = $(OSPFD_TEST_LDADD)
+tests_ospfd_test_ospf_spf_SOURCES = tests/ospfd/test_ospf_spf.c tests/ospfd/common.c tests/ospfd/topologies.c
+EXTRA_DIST += \
+	tests/ospfd/test_ospf_spf.py \
+	tests/ospfd/test_ospf_spf.in \
+	tests/ospfd/test_ospf_spf.refout \
+	# end
diff --git a/tests/ospfd/test_ospf_spf.c b/tests/ospfd/test_ospf_spf.c
new file mode 100644
index 0000000..73f2e29
--- /dev/null
+++ b/tests/ospfd/test_ospf_spf.c
@@ -0,0 +1,305 @@
+#include <zebra.h>
+
+#include "getopt.h"
+#include "thread.h"
+#include <lib/version.h>
+#include "vty.h"
+#include "command.h"
+#include "log.h"
+#include "vrf.h"
+#include "table.h"
+#include "mpls.h"
+
+#include "ospfd/ospfd.h"
+#include "ospfd/ospf_asbr.h"
+#include "ospfd/ospf_lsa.h"
+#include "ospfd/ospf_route.h"
+#include "ospfd/ospf_spf.h"
+#include "ospfd/ospf_ti_lfa.h"
+#include "ospfd/ospf_vty.h"
+#include "ospfd/ospf_dump.h"
+#include "ospfd/ospf_sr.h"
+
+#include "common.h"
+
+DECLARE_RBTREE_UNIQ(p_spaces, struct p_space, p_spaces_item,
+		    p_spaces_compare_func);
+DECLARE_RBTREE_UNIQ(q_spaces, struct q_space, q_spaces_item,
+		    q_spaces_compare_func);
+
+static struct ospf *test_init(struct ospf_test_node *root)
+{
+	struct ospf *ospf;
+	struct ospf_area *area;
+	struct in_addr area_id;
+	struct in_addr router_id;
+
+	ospf = ospf_new_alloc(0, VRF_DEFAULT_NAME);
+
+	area_id.s_addr = OSPF_AREA_BACKBONE;
+	area = ospf_area_new(ospf, area_id);
+	listnode_add_sort(ospf->areas, area);
+
+	inet_aton(root->router_id, &router_id);
+	ospf->router_id = router_id;
+	ospf->router_id_static = router_id;
+	ospf->ti_lfa_enabled = true;
+
+	return ospf;
+}
+
+static void test_run_spf(struct vty *vty, struct ospf *ospf,
+			 enum protection_type protection_type, bool verbose)
+{
+	struct route_table *new_table, *new_rtrs;
+	struct route_table *all_rtrs = NULL;
+	struct ospf_area *area;
+	struct p_space *p_space;
+	struct q_space *q_space;
+	char label_buf[MPLS_LABEL_STRLEN];
+	char res_buf[PROTECTED_RESOURCE_STRLEN];
+
+	/* Just use the backbone for testing */
+	area = ospf->backbone;
+
+	new_table = route_table_init();
+	new_rtrs = route_table_init();
+	all_rtrs = route_table_init();
+
+	/* dryrun true, root_node false */
+	ospf_spf_calculate(area, area->router_lsa_self, new_table, all_rtrs,
+			   new_rtrs, true, false);
+
+	if (verbose) {
+		vty_out(vty, "SPF Tree without TI-LFA backup paths:\n\n");
+		ospf_spf_print(vty, area->spf, 0);
+
+		vty_out(vty,
+			"\nRouting Table without TI-LFA backup paths:\n\n");
+		print_route_table(vty, new_table);
+	}
+
+	if (verbose)
+		vty_out(vty, "\n... generating TI-LFA backup paths ...\n");
+
+	/* TI-LFA testrun */
+	ospf_ti_lfa_generate_p_spaces(area, protection_type);
+	ospf_ti_lfa_insert_backup_paths(area, new_table);
+
+	/* Print P/Q space information */
+	if (verbose) {
+		vty_out(vty, "\nP and Q space info:\n");
+		frr_each (p_spaces, area->p_spaces, p_space) {
+			ospf_print_protected_resource(
+				p_space->protected_resource, res_buf);
+			vty_out(vty, "\nP Space for root %pI4 and %s\n",
+				&p_space->root->id, res_buf);
+			ospf_spf_print(vty, p_space->root, 0);
+
+			frr_each (q_spaces, p_space->q_spaces, q_space) {
+				vty_out(vty,
+					"\nQ Space for destination %pI4:\n",
+					&q_space->root->id);
+				ospf_spf_print(vty, q_space->root, 0);
+				if (q_space->label_stack) {
+					mpls_label2str(
+						q_space->label_stack
+							->num_labels,
+						q_space->label_stack->label,
+						label_buf, MPLS_LABEL_STRLEN,
+						true);
+					vty_out(vty, "\nLabel stack: %s\n",
+						label_buf);
+				} else {
+					vty_out(vty,
+						"\nLabel stack not generated!\n");
+				}
+			}
+
+			vty_out(vty, "\nPost-convergence SPF Tree:\n");
+			ospf_spf_print(vty, p_space->pc_spf, 0);
+		}
+	}
+
+	/* Cleanup */
+	ospf_ti_lfa_free_p_spaces(area);
+	ospf_spf_cleanup(area->spf, area->spf_vertex_list);
+
+	/*
+	 * Print the new routing table which is augmented with TI-LFA backup
+	 * paths (label stacks).
+	 */
+	if (verbose)
+		vty_out(vty,
+			"\n\nFinal Routing Table including backup paths:\n\n");
+
+	print_route_table(vty, new_table);
+}
+
+static int test_run(struct vty *vty, struct ospf_topology *topology,
+		    struct ospf_test_node *root,
+		    enum protection_type protection_type, bool verbose)
+{
+	struct ospf *ospf;
+
+	ospf = test_init(root);
+
+	/* Inject LSAs into the OSPF backbone according to the topology */
+	if (topology_load(vty, topology, root, ospf)) {
+		vty_out(vty, "%% Failed to load topology\n");
+		return CMD_WARNING;
+	}
+
+	if (verbose) {
+		vty_out(vty, "\n");
+		show_ip_ospf_database_summary(vty, ospf, 0, NULL);
+	}
+
+	test_run_spf(vty, ospf, protection_type, verbose);
+
+	return 0;
+}
+
+DEFUN(test_ospf, test_ospf_cmd,
+      "test ospf topology WORD root HOSTNAME ti-lfa [node-protection] [verbose]",
+      "Test mode\n"
+      "Choose OSPF for SPF testing\n"
+      "Network topology to choose\n"
+      "Name of the network topology to choose\n"
+      "Root node to choose\n"
+      "Hostname of the root node to choose\n"
+      "Use Topology-Independent LFA\n"
+      "Use node protection (default is link protection)\n"
+      "Verbose output\n")
+{
+	struct ospf_topology *topology;
+	struct ospf_test_node *root;
+	enum protection_type protection_type = OSPF_TI_LFA_LINK_PROTECTION;
+	int idx = 0;
+	bool verbose = false;
+
+	/* Parse topology. */
+	argv_find(argv, argc, "topology", &idx);
+	topology = test_find_topology(argv[idx + 1]->arg);
+	if (!topology) {
+		vty_out(vty, "%% Topology not found\n");
+		return CMD_WARNING;
+	}
+
+	argv_find(argv, argc, "root", &idx);
+	root = test_find_node(topology, argv[idx + 1]->arg);
+	if (!root) {
+		vty_out(vty, "%% Root not found\n");
+		return CMD_WARNING;
+	}
+
+	if (argv_find(argv, argc, "node-protection", &idx))
+		protection_type = OSPF_TI_LFA_NODE_PROTECTION;
+
+	if (argv_find(argv, argc, "verbose", &idx))
+		verbose = true;
+
+	return test_run(vty, topology, root, protection_type, verbose);
+}
+
+static void vty_do_exit(int isexit)
+{
+	printf("\nend.\n");
+
+	cmd_terminate();
+	vty_terminate();
+	thread_master_free(master);
+
+	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\
+ospfd 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 thread 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 = thread_master_create(NULL);
+
+	/* Library inits. */
+	cmd_init(1);
+	cmd_hostname_set("test");
+	vty_init(master, false);
+	if (debug)
+		zlog_aux_init("NONE: ", LOG_DEBUG);
+	else
+		zlog_aux_init("NONE: ", ZLOG_DISABLED);
+
+	/* Install test command. */
+	install_element(VIEW_NODE, &test_ospf_cmd);
+
+	/* needed for SR DB init */
+	ospf_vty_init();
+	ospf_sr_init();
+
+	term_debug_ospf_ti_lfa = 1;
+
+	/* Read input from .in file. */
+	vty_stdio(vty_do_exit);
+
+	/* Fetch next active thread. */
+	while (thread_fetch(master, &thread))
+		thread_call(&thread);
+
+	/* Not reached. */
+	exit(0);
+}
diff --git a/tests/ospfd/test_ospf_spf.in b/tests/ospfd/test_ospf_spf.in
new file mode 100644
index 0000000..f1e7467
--- /dev/null
+++ b/tests/ospfd/test_ospf_spf.in
@@ -0,0 +1,10 @@
+test ospf topology topo1 root rt1 ti-lfa
+test ospf topology topo1 root rt1 ti-lfa node-protection
+test ospf topology topo2 root rt1 ti-lfa
+test ospf topology topo2 root rt1 ti-lfa node-protection
+test ospf topology topo3 root rt1 ti-lfa
+test ospf topology topo3 root rt1 ti-lfa node-protection
+test ospf topology topo4 root rt1 ti-lfa
+test ospf topology topo4 root rt1 ti-lfa node-protection
+test ospf topology topo5 root rt1 ti-lfa
+test ospf topology topo5 root rt1 ti-lfa node-protection
diff --git a/tests/ospfd/test_ospf_spf.py b/tests/ospfd/test_ospf_spf.py
new file mode 100644
index 0000000..92a1c6a
--- /dev/null
+++ b/tests/ospfd/test_ospf_spf.py
@@ -0,0 +1,4 @@
+import frrtest
+
+class TestOspfSPF(frrtest.TestRefOut):
+    program = './test_ospf_spf'
diff --git a/tests/ospfd/test_ospf_spf.refout b/tests/ospfd/test_ospf_spf.refout
new file mode 100644
index 0000000..d1e3c7b
--- /dev/null
+++ b/tests/ospfd/test_ospf_spf.refout
@@ -0,0 +1,130 @@
+test# test ospf topology topo1 root rt1 ti-lfa
+N 1.1.1.1/32         0.0.0.0         0
+N 2.2.2.2/32         0.0.0.0         10
+  -> 10.0.1.2 with adv router 2.2.2.2 and backup path 15002
+N 3.3.3.3/32         0.0.0.0         10
+  -> 10.0.3.2 with adv router 3.3.3.3 and backup path 15001
+N 10.0.1.0/24        0.0.0.0         10
+N 10.0.2.0/24        0.0.0.0         20
+  -> 10.0.1.2 with adv router 2.2.2.2 and backup path 15002
+  -> 10.0.3.2 with adv router 3.3.3.3 and backup path 15001
+N 10.0.3.0/24        0.0.0.0         10
+test# test ospf topology topo1 root rt1 ti-lfa node-protection
+N 1.1.1.1/32         0.0.0.0         0
+N 2.2.2.2/32         0.0.0.0         10
+  -> 10.0.1.2 with adv router 2.2.2.2
+N 3.3.3.3/32         0.0.0.0         10
+  -> 10.0.3.2 with adv router 3.3.3.3
+N 10.0.1.0/24        0.0.0.0         10
+N 10.0.2.0/24        0.0.0.0         20
+  -> 10.0.1.2 with adv router 2.2.2.2
+  -> 10.0.3.2 with adv router 3.3.3.3
+N 10.0.3.0/24        0.0.0.0         10
+test# test ospf topology topo2 root rt1 ti-lfa
+N 1.1.1.1/32         0.0.0.0         0
+N 2.2.2.2/32         0.0.0.0         10
+  -> 10.0.1.2 with adv router 2.2.2.2 and backup path 15002
+N 3.3.3.3/32         0.0.0.0         20
+  -> 10.0.1.2 with adv router 3.3.3.3 and backup path 15002
+N 10.0.1.0/24        0.0.0.0         10
+N 10.0.2.0/24        0.0.0.0         20
+  -> 10.0.1.2 with adv router 2.2.2.2 and backup path 15002
+N 10.0.3.0/24        0.0.0.0         30
+test# test ospf topology topo2 root rt1 ti-lfa node-protection
+N 1.1.1.1/32         0.0.0.0         0
+N 2.2.2.2/32         0.0.0.0         10
+  -> 10.0.1.2 with adv router 2.2.2.2
+N 3.3.3.3/32         0.0.0.0         20
+  -> 10.0.1.2 with adv router 3.3.3.3 and backup path 15002
+N 10.0.1.0/24        0.0.0.0         10
+N 10.0.2.0/24        0.0.0.0         20
+  -> 10.0.1.2 with adv router 2.2.2.2
+N 10.0.3.0/24        0.0.0.0         30
+test# test ospf topology topo3 root rt1 ti-lfa
+N 1.1.1.1/32         0.0.0.0         0
+N 2.2.2.2/32         0.0.0.0         10
+  -> 10.0.1.2 with adv router 2.2.2.2 and backup path 16030
+N 3.3.3.3/32         0.0.0.0         20
+  -> 10.0.4.2 with adv router 3.3.3.3 and backup path 15001
+N 4.4.4.4/32         0.0.0.0         10
+  -> 10.0.4.2 with adv router 4.4.4.4 and backup path 15001/15004
+N 10.0.1.0/24        0.0.0.0         10
+N 10.0.2.0/24        0.0.0.0         30
+  -> 10.0.1.2 with adv router 2.2.2.2 and backup path 16030
+N 10.0.3.0/24        0.0.0.0         20
+  -> 10.0.4.2 with adv router 4.4.4.4 and backup path 15001/15004
+N 10.0.4.0/24        0.0.0.0         10
+test# test ospf topology topo3 root rt1 ti-lfa node-protection
+N 1.1.1.1/32         0.0.0.0         0
+N 2.2.2.2/32         0.0.0.0         10
+  -> 10.0.1.2 with adv router 2.2.2.2
+N 3.3.3.3/32         0.0.0.0         20
+  -> 10.0.4.2 with adv router 3.3.3.3 and backup path 15001
+N 4.4.4.4/32         0.0.0.0         10
+  -> 10.0.4.2 with adv router 4.4.4.4
+N 10.0.1.0/24        0.0.0.0         10
+N 10.0.2.0/24        0.0.0.0         30
+  -> 10.0.1.2 with adv router 2.2.2.2
+N 10.0.3.0/24        0.0.0.0         20
+  -> 10.0.4.2 with adv router 4.4.4.4
+N 10.0.4.0/24        0.0.0.0         10
+test# test ospf topology topo4 root rt1 ti-lfa
+N 1.1.1.1/32         0.0.0.0         0
+N 2.2.2.2/32         0.0.0.0         10
+  -> 10.0.1.2 with adv router 2.2.2.2 and backup path 16030/15006
+N 3.3.3.3/32         0.0.0.0         20
+  -> 10.0.4.2 with adv router 3.3.3.3 and backup path 15001/15004
+N 4.4.4.4/32         0.0.0.0         10
+  -> 10.0.4.2 with adv router 4.4.4.4 and backup path 15001/15004
+N 10.0.1.0/24        0.0.0.0         10
+N 10.0.2.0/24        0.0.0.0         60
+  -> 10.0.1.2 with adv router 2.2.2.2 and backup path 16030/15006
+N 10.0.3.0/24        0.0.0.0         20
+  -> 10.0.4.2 with adv router 4.4.4.4 and backup path 15001/15004
+N 10.0.4.0/24        0.0.0.0         10
+test# test ospf topology topo4 root rt1 ti-lfa node-protection
+N 1.1.1.1/32         0.0.0.0         0
+N 2.2.2.2/32         0.0.0.0         10
+  -> 10.0.1.2 with adv router 2.2.2.2
+N 3.3.3.3/32         0.0.0.0         20
+  -> 10.0.4.2 with adv router 3.3.3.3 and backup path 15001/15004
+N 4.4.4.4/32         0.0.0.0         10
+  -> 10.0.4.2 with adv router 4.4.4.4
+N 10.0.1.0/24        0.0.0.0         10
+N 10.0.2.0/24        0.0.0.0         60
+  -> 10.0.1.2 with adv router 2.2.2.2
+N 10.0.3.0/24        0.0.0.0         20
+  -> 10.0.4.2 with adv router 4.4.4.4
+N 10.0.4.0/24        0.0.0.0         10
+test# test ospf topology topo5 root rt1 ti-lfa
+N 1.1.1.1/32         0.0.0.0         0
+N 2.2.2.2/32         0.0.0.0         30
+  -> 10.0.4.2 with adv router 2.2.2.2 and backup path 15001
+N 3.3.3.3/32         0.0.0.0         20
+  -> 10.0.4.2 with adv router 3.3.3.3 and backup path 15001/15004
+N 4.4.4.4/32         0.0.0.0         10
+  -> 10.0.4.2 with adv router 4.4.4.4 and backup path 15001/15004/15006
+N 10.0.1.0/24        0.0.0.0         40
+  -> 10.0.4.2 with adv router 2.2.2.2 and backup path 15001
+N 10.0.2.0/24        0.0.0.0         30
+  -> 10.0.4.2 with adv router 3.3.3.3 and backup path 15001/15004
+N 10.0.3.0/24        0.0.0.0         20
+  -> 10.0.4.2 with adv router 4.4.4.4 and backup path 15001/15004/15006
+N 10.0.4.0/24        0.0.0.0         10
+test# test ospf topology topo5 root rt1 ti-lfa node-protection
+N 1.1.1.1/32         0.0.0.0         0
+N 2.2.2.2/32         0.0.0.0         30
+  -> 10.0.4.2 with adv router 2.2.2.2 and backup path 15001
+N 3.3.3.3/32         0.0.0.0         20
+  -> 10.0.4.2 with adv router 3.3.3.3 and backup path 15001/15004
+N 4.4.4.4/32         0.0.0.0         10
+  -> 10.0.4.2 with adv router 4.4.4.4
+N 10.0.1.0/24        0.0.0.0         40
+  -> 10.0.4.2 with adv router 2.2.2.2 and backup path 15001
+N 10.0.2.0/24        0.0.0.0         30
+  -> 10.0.4.2 with adv router 3.3.3.3 and backup path 15001/15004
+N 10.0.3.0/24        0.0.0.0         20
+  -> 10.0.4.2 with adv router 4.4.4.4
+N 10.0.4.0/24        0.0.0.0         10
+test# 
+end.
diff --git a/tests/ospfd/topologies.c b/tests/ospfd/topologies.c
new file mode 100644
index 0000000..2dc611c
--- /dev/null
+++ b/tests/ospfd/topologies.c
@@ -0,0 +1,575 @@
+#include <zebra.h>
+
+#include "mpls.h"
+#include "if.h"
+
+#include "ospfd/ospfd.h"
+
+#include "common.h"
+
+/*
+ * +---------+                     +---------+
+ * |         |                     |         |
+ * |   RT1   |eth-rt2       eth-rt1|   RT2   |
+ * | 1.1.1.1 +---------------------+ 2.2.2.2 |
+ * |         |     10.0.1.0/24     |         |
+ * +---------+                     +---------+
+ *      |eth-rt3                 eth-rt3|
+ *      |                               |
+ *      |10.0.3.0/24                    |
+ *      |                               |
+ *      |eth-rt1                        |
+ * +---------+                          |
+ * |         |eth-rt2        10.0.2.0/24|
+ * |   RT3   +--------------------------+
+ * | 3.3.3.3 |
+ * |         |
+ * +---------+
+ *
+ * Link Protection:
+ * P and Q spaces overlap here, hence just one P/Q node regardless of which
+ * link is protected. Hence the backup label stack just has one label.
+ *
+ * Node Protection:
+ * Obviously no backup paths involved.
+ */
+struct ospf_topology topo1 = {
+	.nodes =
+		{
+			{
+				.hostname = "rt1",
+				.router_id = "1.1.1.1",
+				.label = 10,
+				.adjacencies =
+					{
+						{
+							.hostname = "rt2",
+							.network =
+								"10.0.1.1/24",
+							.metric = 10,
+							.label = 1,
+						},
+						{
+							.hostname = "rt3",
+							.network =
+								"10.0.3.1/24",
+							.metric = 10,
+							.label = 2,
+						},
+					},
+			},
+			{
+				.hostname = "rt2",
+				.router_id = "2.2.2.2",
+				.label = 20,
+				.adjacencies =
+					{
+						{
+							.hostname = "rt1",
+							.network =
+								"10.0.1.2/24",
+							.metric = 10,
+							.label = 3,
+						},
+						{
+							.hostname = "rt3",
+							.network =
+								"10.0.2.1/24",
+							.metric = 10,
+							.label = 4,
+						},
+					},
+			},
+			{
+				.hostname = "rt3",
+				.router_id = "3.3.3.3",
+				.label = 30,
+				.adjacencies =
+					{
+						{
+							.hostname = "rt1",
+							.network =
+								"10.0.3.2/24",
+							.metric = 10,
+							.label = 5,
+						},
+						{
+							.hostname = "rt2",
+							.network =
+								"10.0.2.2/24",
+							.metric = 10,
+							.label = 6,
+						},
+					},
+			},
+		},
+};
+
+
+/*
+ * +---------+                     +---------+
+ * |         |                     |         |
+ * |   RT1   |eth-rt2       eth-rt1|   RT2   |
+ * | 1.1.1.1 +---------------------+ 2.2.2.2 |
+ * |         |  10.0.1.0/24 (10)   |         |
+ * +---------+                     +---------+
+ *      |eth-rt3                 eth-rt3|
+ *      |                               |
+ *      |10.0.3.0/24 (30)               |
+ *      |                               |
+ *      |eth-rt1                        |
+ * +---------+                          |
+ * |         |eth-rt2        10.0.2.0/24|(10)
+ * |   RT3   +--------------------------+
+ * | 3.3.3.3 |
+ * |         |
+ * +---------+
+ *
+ * Link Protection:
+ * Regarding the subnet 10.0.1.0/24, the P space of RT1 is just RT1 itself
+ * while the Q space of RT3 consists of RT3 and RT2. Hence the P and Q
+ * nodes are disjunct (tricky: the root node is the P node here). For the
+ * backup label stack just one label is necessary.
+ *
+ * Node Protection:
+ * For protected node RT2 and route from RT1 to RT3 there is just the backup
+ * path consisting of the label 15002.
+ */
+struct ospf_topology topo2 = {
+	.nodes =
+		{
+			{
+				.hostname = "rt1",
+				.router_id = "1.1.1.1",
+				.label = 10,
+				.adjacencies =
+					{
+						{
+							.hostname = "rt2",
+							.network =
+								"10.0.1.1/24",
+							.metric = 10,
+							.label = 1,
+						},
+						{
+							.hostname = "rt3",
+							.network =
+								"10.0.3.1/24",
+							.metric = 30,
+							.label = 2,
+						},
+					},
+			},
+			{
+				.hostname = "rt2",
+				.router_id = "2.2.2.2",
+				.label = 20,
+				.adjacencies =
+					{
+						{
+							.hostname = "rt1",
+							.network =
+								"10.0.1.2/24",
+							.metric = 10,
+							.label = 3,
+						},
+						{
+							.hostname = "rt3",
+							.network =
+								"10.0.2.1/24",
+							.metric = 10,
+							.label = 4,
+						},
+					},
+			},
+			{
+				.hostname = "rt3",
+				.router_id = "3.3.3.3",
+				.label = 30,
+				.adjacencies =
+					{
+						{
+							.hostname = "rt1",
+							.network =
+								"10.0.3.2/24",
+							.metric = 30,
+							.label = 5,
+						},
+						{
+							.hostname = "rt2",
+							.network =
+								"10.0.2.2/24",
+							.metric = 10,
+							.label = 6,
+						},
+					},
+			},
+		},
+};
+
+/*
+ * +---------+                     +---------+
+ * |         |                     |         |
+ * |   RT1   |eth-rt4       eth-rt1|   RT4   |
+ * | 1.1.1.1 +---------------------+ 4.4.4.4 |
+ * |         |  10.0.4.0/24 (10)   |         |
+ * +---------+                     +---------+
+ *      |eth-rt2                 eth-rt3|
+ *      |                               |
+ *      |10.0.1.0/24 (10)               |
+ *      |              10.0.3.0/24 (10) |
+ *      |eth-rt1                 eth-rt4|
+ * +---------+                     +---------+
+ * |         |eth-rt3       eth-rt2|         |
+ * |   RT2   +---------------------+   RT3   |
+ * | 2.2.2.2 |  10.0.2.0/24 (20)   | 3.3.3.3 |
+ * |         |                     |         |
+ * +---------+                     +---------+
+ *
+ * Link Protection:
+ * Regarding the protected subnet 10.0.4.0/24, the P and Q spaces for root RT1
+ * and destination RT4 are disjunct and the P node is RT2 while RT3 is the Q
+ * node. Hence the backup label stack here is 16020/15004. Note that here the
+ * P and Q nodes are neither the root nor the destination nodes, so this is a
+ * case where you really need a label stack consisting of two labels.
+ *
+ * Node Protection:
+ * For the protected node RT4 and the route from RT1 to RT3 there is a backup
+ * path with the single label 15001.
+ */
+struct ospf_topology topo3 = {
+	.nodes =
+		{
+			{
+				.hostname = "rt1",
+				.router_id = "1.1.1.1",
+				.label = 10,
+				.adjacencies =
+					{
+						{
+							.hostname = "rt2",
+							.network =
+								"10.0.1.1/24",
+							.metric = 10,
+							.label = 1,
+						},
+						{
+							.hostname = "rt4",
+							.network =
+								"10.0.4.1/24",
+							.metric = 10,
+							.label = 2,
+						},
+					},
+			},
+			{
+				.hostname = "rt2",
+				.router_id = "2.2.2.2",
+				.label = 20,
+				.adjacencies =
+					{
+						{
+							.hostname = "rt1",
+							.network =
+								"10.0.1.2/24",
+							.metric = 10,
+							.label = 3,
+						},
+						{
+							.hostname = "rt3",
+							.network =
+								"10.0.2.1/24",
+							.metric = 20,
+							.label = 4,
+						},
+					},
+			},
+			{
+				.hostname = "rt3",
+				.router_id = "3.3.3.3",
+				.label = 30,
+				.adjacencies =
+					{
+						{
+							.hostname = "rt2",
+							.network =
+								"10.0.2.2/24",
+							.metric = 20,
+							.label = 5,
+						},
+						{
+							.hostname = "rt4",
+							.network =
+								"10.0.3.1/24",
+							.metric = 10,
+							.label = 6,
+						},
+					},
+			},
+			{
+				.hostname = "rt4",
+				.router_id = "4.4.4.4",
+				.label = 40,
+				.adjacencies =
+					{
+						{
+							.hostname = "rt1",
+							.network =
+								"10.0.4.2/24",
+							.metric = 10,
+							.label = 7,
+						},
+						{
+							.hostname = "rt3",
+							.network =
+								"10.0.3.2/24",
+							.metric = 10,
+							.label = 8,
+						},
+					},
+			},
+		},
+};
+
+/*
+ * +---------+                     +---------+
+ * |         |                     |         |
+ * |   RT1   |eth-rt4       eth-rt1|   RT4   |
+ * | 1.1.1.1 +---------------------+ 4.4.4.4 |
+ * |         |  10.0.4.0/24 (10)   |         |
+ * +---------+                     +---------+
+ *      |eth+rt2                 eth-rt3|
+ *      |                               |
+ *      |10.0.1.0/24 (10)               |
+ *      |              10.0.3.0/24 (10) |
+ *      |eth-rt1                 eth-rt4|
+ * +---------+                     +---------+
+ * |         |eth-rt3       eth-rt2|         |
+ * |   RT2   +---------------------+   RT3   |
+ * | 2.2.2.2 |  10.0.2.0/24 (40)   | 3.3.3.3 |
+ * |         |                     |         |
+ * +---------+                     +---------+
+ *
+ * This case was specifically created for Node Protection with RT4 as
+ * protected node from the perspective of RT1. Note the weight of 40
+ * on the link between RT2 and RT3.
+ * The P space of RT1 is just RT2 while the Q space of RT3 is empty.
+ * This means that the P and Q spaces are disjunct and there are two
+ * labels needed to get from RT1 to RT3.
+ */
+struct ospf_topology topo4 = {
+	.nodes =
+		{
+			{
+				.hostname = "rt1",
+				.router_id = "1.1.1.1",
+				.label = 10,
+				.adjacencies =
+					{
+						{
+							.hostname = "rt2",
+							.network =
+								"10.0.1.1/24",
+							.metric = 10,
+							.label = 1,
+						},
+						{
+							.hostname = "rt4",
+							.network =
+								"10.0.4.1/24",
+							.metric = 10,
+							.label = 2,
+						},
+					},
+			},
+			{
+				.hostname = "rt2",
+				.router_id = "2.2.2.2",
+				.label = 20,
+				.adjacencies =
+					{
+						{
+							.hostname = "rt1",
+							.network =
+								"10.0.1.2/24",
+							.metric = 10,
+							.label = 3,
+						},
+						{
+							.hostname = "rt3",
+							.network =
+								"10.0.2.1/24",
+							.metric = 50,
+							.label = 4,
+						},
+					},
+			},
+			{
+				.hostname = "rt3",
+				.router_id = "3.3.3.3",
+				.label = 30,
+				.adjacencies =
+					{
+						{
+							.hostname = "rt2",
+							.network =
+								"10.0.2.2/24",
+							.metric = 50,
+							.label = 5,
+						},
+						{
+							.hostname = "rt4",
+							.network =
+								"10.0.3.1/24",
+							.metric = 10,
+							.label = 6,
+						},
+					},
+			},
+			{
+				.hostname = "rt4",
+				.router_id = "4.4.4.4",
+				.label = 40,
+				.adjacencies =
+					{
+						{
+							.hostname = "rt3",
+							.network =
+								"10.0.3.2/24",
+							.metric = 10,
+							.label = 7,
+						},
+						{
+							.hostname = "rt1",
+							.network =
+								"10.0.4.2/24",
+							.metric = 10,
+							.label = 8,
+						},
+					},
+			},
+		},
+};
+
+/*
+ * +---------+                     +---------+
+ * |         |                     |         |
+ * |   RT1   |eth-rt4       eth-rt1|   RT4   |
+ * | 1.1.1.1 +---------------------+ 4.4.4.4 |
+ * |         |  10.0.4.0/24        |         |
+ * +---------+                     +---------+
+ *      |eth+rt2                 eth-rt3|
+ *      |                               |
+ *      |10.0.1.0/24                    |
+ *      |                    10.0.3.0/24|
+ *      |eth-rt1                 eth-rt4|
+ * +---------+                     +---------+
+ * |         |eth-rt3       eth-rt2|         |
+ * |   RT2   +---------------------+   RT3   |
+ * | 2.2.2.2 |     10.0.2.0/24     | 3.3.3.3 |
+ * |         |                     |         |
+ * +---------+                     +---------+
+ *
+ * Weights:
+ * - clockwise: 10
+ * - counterclockwise: 40
+ *
+ * This is an example where 3 (!) labels are needed for the protected
+ * link RT1<->RT2, e.g. the subnet 10.0.1.0/24, to reach RT4.
+ *
+ * Because the initial P and Q spaces will not be overlapping or
+ * adjacent for this case the TI-LFA will be applied recursively.
+ */
+struct ospf_topology topo5 = {
+	.nodes =
+		{
+			{
+				.hostname = "rt1",
+				.router_id = "1.1.1.1",
+				.label = 10,
+				.adjacencies =
+					{
+						{
+							.hostname = "rt2",
+							.network =
+								"10.0.1.1/24",
+							.metric = 40,
+							.label = 1,
+						},
+						{
+							.hostname = "rt4",
+							.network =
+								"10.0.4.1/24",
+							.metric = 10,
+							.label = 2,
+						},
+					},
+			},
+			{
+				.hostname = "rt2",
+				.router_id = "2.2.2.2",
+				.label = 20,
+				.adjacencies =
+					{
+						{
+							.hostname = "rt1",
+							.network =
+								"10.0.1.2/24",
+							.metric = 10,
+							.label = 3,
+						},
+						{
+							.hostname = "rt3",
+							.network =
+								"10.0.2.1/24",
+							.metric = 40,
+							.label = 4,
+						},
+					},
+			},
+			{
+				.hostname = "rt3",
+				.router_id = "3.3.3.3",
+				.label = 30,
+				.adjacencies =
+					{
+						{
+							.hostname = "rt2",
+							.network =
+								"10.0.2.2/24",
+							.metric = 10,
+							.label = 5,
+						},
+						{
+							.hostname = "rt4",
+							.network =
+								"10.0.3.1/24",
+							.metric = 40,
+							.label = 6,
+						},
+					},
+			},
+			{
+				.hostname = "rt4",
+				.router_id = "4.4.4.4",
+				.label = 40,
+				.adjacencies =
+					{
+						{
+							.hostname = "rt3",
+							.network =
+								"10.0.3.2/24",
+							.metric = 10,
+							.label = 7,
+						},
+						{
+							.hostname = "rt1",
+							.network =
+								"10.0.4.2/24",
+							.metric = 40,
+							.label = 8,
+						},
+					},
+			},
+		},
+};