summaryrefslogtreecommitdiffstats
path: root/tests/ospfd
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-09 13:16:35 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-09 13:16:35 +0000
commite2bbf175a2184bd76f6c54ccf8456babeb1a46fc (patch)
treef0b76550d6e6f500ada964a3a4ee933a45e5a6f1 /tests/ospfd
parentInitial commit. (diff)
downloadfrr-e2bbf175a2184bd76f6c54ccf8456babeb1a46fc.tar.xz
frr-e2bbf175a2184bd76f6c54ccf8456babeb1a46fc.zip
Adding upstream version 9.1.upstream/9.1
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'tests/ospfd')
-rw-r--r--tests/ospfd/.gitignore3
-rw-r--r--tests/ospfd/common.c249
-rw-r--r--tests/ospfd/common.h47
-rw-r--r--tests/ospfd/subdir.am21
-rw-r--r--tests/ospfd/test_ospf_spf.c305
-rw-r--r--tests/ospfd/test_ospf_spf.in10
-rw-r--r--tests/ospfd/test_ospf_spf.py4
-rw-r--r--tests/ospfd/test_ospf_spf.refout130
-rw-r--r--tests/ospfd/topologies.c575
9 files changed, 1344 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..e394186
--- /dev/null
+++ b/tests/ospfd/common.c
@@ -0,0 +1,249 @@
+#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 event_loop *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,
+ ZEBRA_LSP_NONE, 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..18e412b
--- /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 event_loop *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..fc6b8e8
--- /dev/null
+++ b/tests/ospfd/test_ospf_spf.c
@@ -0,0 +1,305 @@
+#include <zebra.h>
+
+#include "getopt.h"
+#include "frrevent.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,
+ ZEBRA_LSP_NONE, 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();
+ event_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 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);
+
+ /* 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 (event_fetch(master, &thread))
+ event_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,
+ },
+ },
+ },
+ },
+};