Adding upstream version 9.1.upstream/9.1

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

1 files changed, 1108 insertions, 0 deletions

diff --git a/ospfd/ospf_ti_lfa.c b/ospfd/ospf_ti_lfa.c
new file mode 100644
index 0000000..d8a2613
--- /dev/null
+++ b/ospfd/ospf_ti_lfa.c
@@ -0,0 +1,1108 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * OSPF TI-LFA
+ * Copyright (C) 2020  NetDEF, Inc.
+ *                     Sascha Kattelmann
+ */
+
+#include <zebra.h>
+
+#include "prefix.h"
+#include "table.h"
+#include "printfrr.h"
+
+#include "ospfd/ospfd.h"
+#include "ospfd/ospf_asbr.h"
+#include "ospfd/ospf_lsa.h"
+#include "ospfd/ospf_spf.h"
+#include "ospfd/ospf_sr.h"
+#include "ospfd/ospf_route.h"
+#include "ospfd/ospf_ti_lfa.h"
+#include "ospfd/ospf_dump.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 void
+ospf_ti_lfa_generate_p_space(struct ospf_area *area, struct vertex *child,
+			     struct protected_resource *protected_resource,
+			     bool recursive, struct list *pc_path);
+
+void ospf_print_protected_resource(
+	struct protected_resource *protected_resource, char *buf)
+{
+	struct router_lsa_link *link;
+
+	switch (protected_resource->type) {
+	case OSPF_TI_LFA_LINK_PROTECTION:
+		link = protected_resource->link;
+		snprintfrr(buf, PROTECTED_RESOURCE_STRLEN,
+			   "protected link: %pI4 %pI4", &link->link_id,
+			   &link->link_data);
+		break;
+	case OSPF_TI_LFA_NODE_PROTECTION:
+		snprintfrr(buf, PROTECTED_RESOURCE_STRLEN,
+			   "protected node: %pI4",
+			   &protected_resource->router_id);
+		break;
+	case OSPF_TI_LFA_UNDEFINED_PROTECTION:
+		snprintfrr(buf, PROTECTED_RESOURCE_STRLEN,
+			   "undefined protected resource");
+		break;
+	}
+}
+
+static enum ospf_ti_lfa_p_q_space_adjacency
+ospf_ti_lfa_find_p_node(struct vertex *pc_node, struct p_space *p_space,
+			struct q_space *q_space)
+{
+	struct listnode *curr_node;
+	struct vertex *p_node = NULL, *pc_node_parent, *p_node_pc_parent;
+	struct vertex_parent *pc_vertex_parent;
+
+	curr_node = listnode_lookup(q_space->pc_path, pc_node);
+	assert(curr_node);
+	pc_node_parent = listgetdata(curr_node->next);
+
+	q_space->p_node_info->type = OSPF_TI_LFA_UNDEFINED_NODE;
+
+	p_node = ospf_spf_vertex_find(pc_node_parent->id, p_space->vertex_list);
+
+	if (p_node) {
+		q_space->p_node_info->node = p_node;
+		q_space->p_node_info->type = OSPF_TI_LFA_P_NODE;
+
+		if (curr_node->next->next) {
+			p_node_pc_parent = listgetdata(curr_node->next->next);
+			pc_vertex_parent = ospf_spf_vertex_parent_find(
+				p_node_pc_parent->id, pc_node_parent);
+			q_space->p_node_info->nexthop =
+				pc_vertex_parent->nexthop->router;
+		} else {
+			/*
+			 * It can happen that the P node is the root node itself
+			 * (hence there can be no parents). In this case we
+			 * don't need to set a nexthop.
+			 */
+			q_space->p_node_info->nexthop.s_addr = INADDR_ANY;
+		}
+
+		return OSPF_TI_LFA_P_Q_SPACE_ADJACENT;
+	}
+
+	ospf_ti_lfa_find_p_node(pc_node_parent, p_space, q_space);
+	return OSPF_TI_LFA_P_Q_SPACE_NON_ADJACENT;
+}
+
+static void ospf_ti_lfa_find_q_node(struct vertex *pc_node,
+				    struct p_space *p_space,
+				    struct q_space *q_space)
+{
+	struct listnode *curr_node, *next_node;
+	struct vertex *p_node, *q_node, *q_space_parent = NULL, *pc_node_parent;
+	struct vertex_parent *pc_vertex_parent;
+
+	curr_node = listnode_lookup(q_space->pc_path, pc_node);
+	assert(curr_node);
+	next_node = curr_node->next;
+	pc_node_parent = listgetdata(next_node);
+	pc_vertex_parent =
+		ospf_spf_vertex_parent_find(pc_node_parent->id, pc_node);
+
+	p_node = ospf_spf_vertex_find(pc_node->id, p_space->vertex_list);
+	q_node = ospf_spf_vertex_find(pc_node->id, q_space->vertex_list);
+
+	/* The Q node is always present. */
+	assert(q_node);
+
+	q_space->q_node_info->type = OSPF_TI_LFA_UNDEFINED_NODE;
+
+	if (p_node && q_node) {
+		q_space->q_node_info->node = pc_node;
+		q_space->q_node_info->type = OSPF_TI_LFA_PQ_NODE;
+		q_space->q_node_info->nexthop =
+			pc_vertex_parent->nexthop->router;
+		return;
+	}
+
+	/*
+	 * Note that the Q space has the 'reverse' direction of the PC
+	 * SPF. Hence compare PC SPF parent to Q space children.
+	 */
+	q_space_parent =
+		ospf_spf_vertex_find(pc_node_parent->id, q_node->children);
+
+	/*
+	 * If the Q space parent doesn't exist we 'hit' the border to the P
+	 * space and hence got our Q node.
+	 */
+	if (!q_space_parent) {
+		q_space->q_node_info->node = pc_node;
+		q_space->q_node_info->type = OSPF_TI_LFA_Q_NODE;
+		q_space->q_node_info->nexthop =
+			pc_vertex_parent->nexthop->router;
+		return;
+	}
+
+	return ospf_ti_lfa_find_q_node(pc_node_parent, p_space, q_space);
+}
+
+static void ospf_ti_lfa_append_label_stack(struct mpls_label_stack *label_stack,
+					   mpls_label_t labels[],
+					   uint32_t num_labels)
+{
+	int i, offset, limit;
+
+	limit = label_stack->num_labels + num_labels;
+	offset = label_stack->num_labels;
+
+	for (i = label_stack->num_labels; i < limit; i++) {
+		label_stack->label[i] = labels[i - offset];
+		label_stack->num_labels++;
+	}
+}
+
+
+static struct mpls_label_stack *
+ospf_ti_lfa_create_label_stack(mpls_label_t labels[], uint32_t num_labels)
+{
+	struct mpls_label_stack *label_stack;
+	uint32_t i;
+
+	/* Sanity check */
+	for (i = 0; i < num_labels; i++) {
+		if (labels[i] == MPLS_INVALID_LABEL)
+			return NULL;
+	}
+
+	label_stack = XCALLOC(MTYPE_OSPF_Q_SPACE,
+			      sizeof(struct mpls_label_stack)
+				      + MPLS_MAX_LABELS * sizeof(mpls_label_t));
+	label_stack->num_labels = num_labels;
+
+	for (i = 0; i < num_labels; i++)
+		label_stack->label[i] = labels[i];
+
+	return label_stack;
+}
+
+static struct list *
+ospf_ti_lfa_map_path_to_pc_vertices(struct list *path,
+				    struct list *pc_vertex_list)
+{
+	struct listnode *node;
+	struct vertex *vertex, *pc_vertex;
+	struct list *pc_path;
+
+	pc_path = list_new();
+
+	for (ALL_LIST_ELEMENTS_RO(path, node, vertex)) {
+		pc_vertex = ospf_spf_vertex_find(vertex->id, pc_vertex_list);
+		listnode_add(pc_path, pc_vertex);
+	}
+
+	return pc_path;
+}
+
+static struct list *ospf_ti_lfa_cut_out_pc_path(struct list *pc_vertex_list,
+						struct list *pc_path,
+						struct vertex *p_node,
+						struct vertex *q_node)
+{
+	struct list *inner_pc_path;
+	struct vertex *current_vertex;
+	struct listnode *current_listnode;
+
+	inner_pc_path = list_new();
+	current_vertex = ospf_spf_vertex_find(q_node->id, pc_vertex_list);
+	current_listnode = listnode_lookup(pc_path, current_vertex);
+
+	/* Note that the post-convergence paths are reversed. */
+	while (current_listnode) {
+		current_vertex = listgetdata(current_listnode);
+		listnode_add(inner_pc_path, current_vertex);
+
+		if (current_vertex->id.s_addr == p_node->id.s_addr)
+			break;
+
+		current_listnode = current_listnode->next;
+	}
+
+	return inner_pc_path;
+}
+
+static void ospf_ti_lfa_generate_inner_label_stack(
+	struct ospf_area *area, struct p_space *p_space,
+	struct q_space *q_space,
+	struct ospf_ti_lfa_inner_backup_path_info *inner_backup_path_info)
+{
+	struct route_table *new_table;
+	struct vertex *q_node;
+	struct vertex *start_vertex, *end_vertex;
+	struct vertex_parent *vertex_parent;
+	struct listnode *pc_p_node, *pc_q_node;
+	struct vertex *spf_orig;
+	struct list *vertex_list_orig;
+	struct p_spaces_head *p_spaces_orig;
+	struct p_space *inner_p_space;
+	struct q_space *inner_q_space;
+	struct ospf_ti_lfa_node_info *p_node_info, *q_node_info;
+	struct protected_resource *protected_resource;
+	struct list *inner_pc_path;
+	mpls_label_t start_label, end_label;
+
+	p_node_info = q_space->p_node_info;
+	q_node_info = q_space->q_node_info;
+	protected_resource = p_space->protected_resource;
+
+	start_vertex = p_node_info->node;
+	end_vertex = q_node_info->node;
+
+	/*
+	 * It can happen that the P node and/or the Q node are the root or
+	 * the destination, therefore we need to force one step forward (resp.
+	 * backward) using an Adjacency-SID.
+	 */
+	start_label = MPLS_INVALID_LABEL;
+	end_label = MPLS_INVALID_LABEL;
+	if (p_node_info->node->id.s_addr == p_space->root->id.s_addr) {
+		pc_p_node = listnode_lookup(q_space->pc_path, p_space->pc_spf);
+		assert(pc_p_node);
+		start_vertex = listgetdata(pc_p_node->prev);
+		start_label = ospf_sr_get_adj_sid_by_id(&p_node_info->node->id,
+							&start_vertex->id);
+	}
+	if (q_node_info->node->id.s_addr == q_space->root->id.s_addr) {
+		pc_q_node = listnode_lookup(q_space->pc_path,
+					    listnode_head(q_space->pc_path));
+		assert(pc_q_node);
+		end_vertex = listgetdata(pc_q_node->next);
+		end_label = ospf_sr_get_adj_sid_by_id(&end_vertex->id,
+						      &q_node_info->node->id);
+	}
+
+	/* Corner case: inner path is just one node */
+	if (start_vertex->id.s_addr == end_vertex->id.s_addr) {
+		inner_backup_path_info->label_stack =
+			ospf_ti_lfa_create_label_stack(&start_label, 1);
+		inner_backup_path_info->q_node_info.node = end_vertex;
+		inner_backup_path_info->q_node_info.type = OSPF_TI_LFA_PQ_NODE;
+		inner_backup_path_info->p_node_info.type =
+			OSPF_TI_LFA_UNDEFINED_NODE;
+		vertex_parent = ospf_spf_vertex_parent_find(p_space->root->id,
+							    end_vertex);
+		inner_backup_path_info->p_node_info.nexthop =
+			vertex_parent->nexthop->router;
+		return;
+	}
+
+	inner_pc_path = ospf_ti_lfa_cut_out_pc_path(p_space->pc_vertex_list,
+						    q_space->pc_path,
+						    start_vertex, end_vertex);
+
+	new_table = route_table_init();
+
+	/* Copy the current state ... */
+	spf_orig = area->spf;
+	vertex_list_orig = area->spf_vertex_list;
+	p_spaces_orig = area->p_spaces;
+
+	area->p_spaces =
+		XCALLOC(MTYPE_OSPF_P_SPACE, sizeof(struct p_spaces_head));
+
+	/* dry run true, root node false */
+	ospf_spf_calculate(area, start_vertex->lsa_p, new_table, NULL, NULL,
+			   true, false);
+
+	q_node = ospf_spf_vertex_find(end_vertex->id, area->spf_vertex_list);
+
+	ospf_ti_lfa_generate_p_space(area, q_node, protected_resource, false,
+				     inner_pc_path);
+
+	/* There's just one P and Q space */
+	inner_p_space = p_spaces_pop(area->p_spaces);
+	inner_q_space = q_spaces_pop(inner_p_space->q_spaces);
+
+	/* Copy over inner backup path information from the inner q_space */
+
+	/* In case the outer P node is also the root of the P space */
+	if (start_label != MPLS_INVALID_LABEL) {
+		inner_backup_path_info->label_stack =
+			ospf_ti_lfa_create_label_stack(&start_label, 1);
+		ospf_ti_lfa_append_label_stack(
+			inner_backup_path_info->label_stack,
+			inner_q_space->label_stack->label,
+			inner_q_space->label_stack->num_labels);
+		inner_backup_path_info->p_node_info.node = start_vertex;
+		inner_backup_path_info->p_node_info.type = OSPF_TI_LFA_P_NODE;
+		vertex_parent = ospf_spf_vertex_parent_find(p_space->root->id,
+							    start_vertex);
+		inner_backup_path_info->p_node_info.nexthop =
+			vertex_parent->nexthop->router;
+	} else {
+		memcpy(inner_backup_path_info->label_stack,
+		       inner_q_space->label_stack,
+		       sizeof(struct mpls_label_stack)
+			       + sizeof(mpls_label_t)
+					 * inner_q_space->label_stack
+						   ->num_labels);
+		memcpy(&inner_backup_path_info->p_node_info,
+		       inner_q_space->p_node_info,
+		       sizeof(struct ospf_ti_lfa_node_info));
+	}
+
+	/* In case the outer Q node is also the root of the Q space */
+	if (end_label != MPLS_INVALID_LABEL) {
+		inner_backup_path_info->q_node_info.node = end_vertex;
+		inner_backup_path_info->q_node_info.type = OSPF_TI_LFA_Q_NODE;
+	} else {
+		memcpy(&inner_backup_path_info->q_node_info,
+		       inner_q_space->q_node_info,
+		       sizeof(struct ospf_ti_lfa_node_info));
+	}
+
+	/* Cleanup */
+	ospf_ti_lfa_free_p_spaces(area);
+	ospf_spf_cleanup(area->spf, area->spf_vertex_list);
+
+	/* ... and copy the current state back. */
+	area->spf = spf_orig;
+	area->spf_vertex_list = vertex_list_orig;
+	area->p_spaces = p_spaces_orig;
+}
+
+static void ospf_ti_lfa_generate_label_stack(struct ospf_area *area,
+					     struct p_space *p_space,
+					     struct q_space *q_space)
+{
+	enum ospf_ti_lfa_p_q_space_adjacency adjacency_result;
+	mpls_label_t labels[MPLS_MAX_LABELS];
+	struct vertex *pc_node;
+	struct ospf_ti_lfa_inner_backup_path_info inner_backup_path_info;
+
+	if (IS_DEBUG_OSPF_TI_LFA)
+		zlog_debug(
+			"%s: Generating Label stack for src %pI4 and dest %pI4.",
+			__func__, &p_space->root->id, &q_space->root->id);
+
+	pc_node = listnode_head(q_space->pc_path);
+
+	if (!pc_node) {
+		if (IS_DEBUG_OSPF_TI_LFA)
+			zlog_debug(
+				"%s: There seems to be no post convergence path (yet).",
+				__func__);
+		return;
+	}
+
+	ospf_ti_lfa_find_q_node(pc_node, p_space, q_space);
+	if (q_space->q_node_info->type == OSPF_TI_LFA_UNDEFINED_NODE) {
+		if (IS_DEBUG_OSPF_TI_LFA)
+			zlog_debug("%s: Q node not found!", __func__);
+		return;
+	}
+
+	/* Found a PQ node? Then we are done here. */
+	if (q_space->q_node_info->type == OSPF_TI_LFA_PQ_NODE) {
+		/*
+		 * If the PQ node is a child of the root, then we can use an
+		 * adjacency SID instead of a prefix SID for the backup path.
+		 */
+		if (ospf_spf_vertex_parent_find(p_space->root->id,
+						q_space->q_node_info->node))
+			labels[0] = ospf_sr_get_adj_sid_by_id(
+				&p_space->root->id,
+				&q_space->q_node_info->node->id);
+		else
+			labels[0] = ospf_sr_get_prefix_sid_by_id(
+				&q_space->q_node_info->node->id);
+
+		q_space->label_stack =
+			ospf_ti_lfa_create_label_stack(labels, 1);
+		q_space->nexthop = q_space->q_node_info->nexthop;
+
+		return;
+	}
+
+	/* Otherwise find a (hopefully adjacent) P node. */
+	pc_node = ospf_spf_vertex_find(q_space->q_node_info->node->id,
+				       p_space->pc_vertex_list);
+	adjacency_result = ospf_ti_lfa_find_p_node(pc_node, p_space, q_space);
+
+	if (q_space->p_node_info->type == OSPF_TI_LFA_UNDEFINED_NODE) {
+		if (IS_DEBUG_OSPF_TI_LFA)
+			zlog_debug("%s: P node not found!", __func__);
+		return;
+	}
+
+	/*
+	 * This should be the regular case: P and Q space are adjacent or even
+	 * overlapping. This is guaranteed for link protection when used with
+	 * symmetric weights.
+	 */
+	if (adjacency_result == OSPF_TI_LFA_P_Q_SPACE_ADJACENT) {
+		/*
+		 * It can happen that the P node is the root itself, therefore
+		 * we don't need a label for it. So just one adjacency SID for
+		 * the Q node.
+		 */
+		if (q_space->p_node_info->node->id.s_addr
+		    == p_space->root->id.s_addr) {
+			labels[0] = ospf_sr_get_adj_sid_by_id(
+				&p_space->root->id,
+				&q_space->q_node_info->node->id);
+			q_space->label_stack =
+				ospf_ti_lfa_create_label_stack(labels, 1);
+			q_space->nexthop = q_space->q_node_info->nexthop;
+			return;
+		}
+
+		/*
+		 * Otherwise we have a P and also a Q node (which are adjacent).
+		 *
+		 * It can happen that the P node is a child of the root,
+		 * therefore we might just need the adjacency SID for the P node
+		 * instead of the prefix SID. For the Q node always take the
+		 * adjacency SID.
+		 */
+		if (ospf_spf_vertex_parent_find(p_space->root->id,
+						q_space->p_node_info->node))
+			labels[0] = ospf_sr_get_adj_sid_by_id(
+				&p_space->root->id,
+				&q_space->p_node_info->node->id);
+		else
+			labels[0] = ospf_sr_get_prefix_sid_by_id(
+				&q_space->p_node_info->node->id);
+
+		labels[1] = ospf_sr_get_adj_sid_by_id(
+			&q_space->p_node_info->node->id,
+			&q_space->q_node_info->node->id);
+
+		q_space->label_stack =
+			ospf_ti_lfa_create_label_stack(labels, 2);
+		q_space->nexthop = q_space->p_node_info->nexthop;
+
+	} else {
+		/*
+		 * It can happen that the P and Q space are not adjacent when
+		 * e.g. node protection or asymmetric weights are used. In this
+		 * case the found P and Q nodes are used as a reference for
+		 * another run of the algorithm!
+		 *
+		 * After having found the inner label stack it is stitched
+		 * together with the outer labels.
+		 */
+		inner_backup_path_info.label_stack = XCALLOC(
+			MTYPE_OSPF_PATH,
+			sizeof(struct mpls_label_stack)
+				+ sizeof(mpls_label_t) * MPLS_MAX_LABELS);
+		ospf_ti_lfa_generate_inner_label_stack(area, p_space, q_space,
+						       &inner_backup_path_info);
+
+		/*
+		 * First stitch together the outer P node label with the inner
+		 * label stack.
+		 */
+		if (q_space->p_node_info->node->id.s_addr
+		    == p_space->root->id.s_addr) {
+			/*
+			 * It can happen that the P node is the root itself,
+			 * therefore we don't need a label for it. Just take
+			 * the inner label stack first.
+			 */
+			q_space->label_stack = ospf_ti_lfa_create_label_stack(
+				inner_backup_path_info.label_stack->label,
+				inner_backup_path_info.label_stack->num_labels);
+
+			/* Use the inner P or Q node for the nexthop */
+			if (inner_backup_path_info.p_node_info.type
+			    != OSPF_TI_LFA_UNDEFINED_NODE)
+				q_space->nexthop = inner_backup_path_info
+							   .p_node_info.nexthop;
+			else
+				q_space->nexthop = inner_backup_path_info
+							   .q_node_info.nexthop;
+
+		} else if (ospf_spf_vertex_parent_find(
+				   p_space->root->id,
+				   q_space->p_node_info->node)) {
+			/*
+			 * It can happen that the outer P node is a child of
+			 * the root, therefore we might just need the
+			 * adjacency SID for the outer P node instead of the
+			 * prefix SID. Then just append the inner label stack.
+			 */
+			labels[0] = ospf_sr_get_adj_sid_by_id(
+				&p_space->root->id,
+				&q_space->p_node_info->node->id);
+			q_space->label_stack =
+				ospf_ti_lfa_create_label_stack(labels, 1);
+			ospf_ti_lfa_append_label_stack(
+				q_space->label_stack,
+				inner_backup_path_info.label_stack->label,
+				inner_backup_path_info.label_stack->num_labels);
+			q_space->nexthop = q_space->p_node_info->nexthop;
+		} else {
+			/* The outer P node needs a Prefix-SID here */
+			labels[0] = ospf_sr_get_prefix_sid_by_id(
+				&q_space->p_node_info->node->id);
+			q_space->label_stack =
+				ospf_ti_lfa_create_label_stack(labels, 1);
+			ospf_ti_lfa_append_label_stack(
+				q_space->label_stack,
+				inner_backup_path_info.label_stack->label,
+				inner_backup_path_info.label_stack->num_labels);
+			q_space->nexthop = q_space->p_node_info->nexthop;
+		}
+
+		/* Now the outer Q node needs to be considered */
+		if (ospf_spf_vertex_parent_find(
+			    inner_backup_path_info.q_node_info.node->id,
+			    q_space->q_node_info->node)) {
+			/*
+			 * The outer Q node can be a child of the inner Q node,
+			 * hence just add an Adjacency-SID.
+			 */
+			labels[0] = ospf_sr_get_adj_sid_by_id(
+				&inner_backup_path_info.q_node_info.node->id,
+				&q_space->q_node_info->node->id);
+			ospf_ti_lfa_append_label_stack(q_space->label_stack,
+						       labels, 1);
+		} else {
+			/* Otherwise a Prefix-SID is needed */
+			labels[0] = ospf_sr_get_prefix_sid_by_id(
+				&q_space->q_node_info->node->id);
+			ospf_ti_lfa_append_label_stack(q_space->label_stack,
+						       labels, 1);
+		}
+		/*
+		 * Note that there's also the case where the inner and outer Q
+		 * node are the same, but then there's nothing to do!
+		 */
+	}
+}
+
+static struct list *
+ospf_ti_lfa_generate_post_convergence_path(struct list *pc_vertex_list,
+					   struct vertex *dest)
+{
+	struct list *pc_path;
+	struct vertex *current_vertex;
+	struct vertex_parent *parent;
+
+	current_vertex = ospf_spf_vertex_find(dest->id, pc_vertex_list);
+	if (!current_vertex) {
+		if (IS_DEBUG_OSPF_TI_LFA)
+			zlog_debug(
+				"%s: There seems to be no post convergence path (yet).",
+				__func__);
+		return NULL;
+	}
+
+	pc_path = list_new();
+	listnode_add(pc_path, current_vertex);
+
+	/* Generate a backup path in reverse order */
+	for (;;) {
+		parent = listnode_head(current_vertex->parents);
+		if (!parent)
+			break;
+
+		listnode_add(pc_path, parent->parent);
+		current_vertex = parent->parent;
+	}
+
+	return pc_path;
+}
+
+static void ospf_ti_lfa_generate_q_spaces(struct ospf_area *area,
+					  struct p_space *p_space,
+					  struct vertex *dest, bool recursive,
+					  struct list *pc_path)
+{
+	struct listnode *node;
+	struct vertex *child;
+	struct route_table *new_table;
+	struct q_space *q_space, q_space_search;
+	char label_buf[MPLS_LABEL_STRLEN];
+	char res_buf[PROTECTED_RESOURCE_STRLEN];
+	bool node_protected;
+
+	ospf_print_protected_resource(p_space->protected_resource, res_buf);
+	node_protected =
+		p_space->protected_resource->type == OSPF_TI_LFA_NODE_PROTECTION
+		&& dest->id.s_addr
+			   == p_space->protected_resource->router_id.s_addr;
+
+	/*
+	 * If node protection is used, don't build a Q space for the protected
+	 * node of that particular P space. Move on with children instead.
+	 */
+	if (node_protected) {
+		if (recursive) {
+			/* Recursively generate Q spaces for all children */
+			for (ALL_LIST_ELEMENTS_RO(dest->children, node, child))
+				ospf_ti_lfa_generate_q_spaces(area, p_space,
+							      child, recursive,
+							      pc_path);
+		}
+		return;
+	}
+
+	/* Check if we already have a Q space for this destination */
+	q_space_search.root = dest;
+	if (q_spaces_find(p_space->q_spaces, &q_space_search))
+		return;
+
+	q_space = XCALLOC(MTYPE_OSPF_Q_SPACE, sizeof(struct q_space));
+	q_space->p_node_info = XCALLOC(MTYPE_OSPF_Q_SPACE,
+				       sizeof(struct ospf_ti_lfa_node_info));
+	q_space->q_node_info = XCALLOC(MTYPE_OSPF_Q_SPACE,
+				       sizeof(struct ospf_ti_lfa_node_info));
+
+	new_table = route_table_init();
+
+	/*
+	 * Generate a new (reversed!) SPF tree for this vertex,
+	 * dry run true, root node false
+	 */
+	area->spf_reversed = true;
+	ospf_spf_calculate(area, dest->lsa_p, new_table, NULL, NULL, true,
+			   false);
+
+	/* Reset the flag for reverse SPF */
+	area->spf_reversed = false;
+
+	q_space->root = area->spf;
+	q_space->vertex_list = area->spf_vertex_list;
+	q_space->label_stack = NULL;
+
+	if (pc_path)
+		q_space->pc_path = ospf_ti_lfa_map_path_to_pc_vertices(
+			pc_path, p_space->pc_vertex_list);
+	else
+		q_space->pc_path = ospf_ti_lfa_generate_post_convergence_path(
+			p_space->pc_vertex_list, q_space->root);
+
+	/* If there's no backup path available then we are done here. */
+	if (!q_space->pc_path) {
+		zlog_info(
+			"%s: NO backup path found for root %pI4 and destination %pI4 for %s, aborting ...",
+			__func__, &p_space->root->id, &q_space->root->id,
+			res_buf);
+
+		list_delete(&q_space->vertex_list);
+		XFREE(MTYPE_OSPF_Q_SPACE, q_space->p_node_info);
+		XFREE(MTYPE_OSPF_Q_SPACE, q_space->q_node_info);
+		XFREE(MTYPE_OSPF_Q_SPACE, q_space);
+
+		return;
+	}
+
+	/* 'Cut' the protected resource out of the new SPF tree */
+	ospf_spf_remove_resource(q_space->root, q_space->vertex_list,
+				 p_space->protected_resource);
+
+	/*
+	 * Generate the smallest possible label stack from the root of the P
+	 * space to the root of the Q space.
+	 */
+	ospf_ti_lfa_generate_label_stack(area, p_space, q_space);
+
+	if (q_space->label_stack) {
+		mpls_label2str(q_space->label_stack->num_labels,
+			       q_space->label_stack->label, label_buf,
+			       MPLS_LABEL_STRLEN, 0, true);
+		zlog_info(
+			"%s: Generated label stack %s for root %pI4 and destination %pI4 for %s",
+			__func__, label_buf, &p_space->root->id,
+			&q_space->root->id, res_buf);
+	} else {
+		zlog_info(
+			"%s: NO label stack generated for root %pI4 and destination %pI4 for %s",
+			__func__, &p_space->root->id, &q_space->root->id,
+			res_buf);
+	}
+
+	/* We are finished, store the new Q space in the P space struct */
+	q_spaces_add(p_space->q_spaces, q_space);
+
+	/* Recursively generate Q spaces for all children */
+	if (recursive) {
+		for (ALL_LIST_ELEMENTS_RO(dest->children, node, child))
+			ospf_ti_lfa_generate_q_spaces(area, p_space, child,
+						      recursive, pc_path);
+	}
+}
+
+static void ospf_ti_lfa_generate_post_convergence_spf(struct ospf_area *area,
+						      struct p_space *p_space)
+{
+	struct route_table *new_table;
+
+	new_table = route_table_init();
+
+	area->spf_protected_resource = p_space->protected_resource;
+
+	/*
+	 * The 'post convergence' SPF tree is generated here
+	 * dry run true, root node false
+	 *
+	 * So how does this work? During the SPF calculation the algorithm
+	 * checks if a link belongs to a protected resource and then just
+	 * ignores it.
+	 * This is actually _NOT_ a good way to calculate the post
+	 * convergence SPF tree. The preferred way would be to delete the
+	 * relevant links (and nodes) from a copy of the LSDB and then just run
+	 * the SPF algorithm on that as usual.
+	 * However, removing links from router LSAs appears to be its own
+	 * endeavour (because LSAs are stored as a 'raw' stream), so we go with
+	 * this rather hacky way for now.
+	 */
+	ospf_spf_calculate(area, area->router_lsa_self, new_table, NULL, NULL,
+			   true, false);
+
+	p_space->pc_spf = area->spf;
+	p_space->pc_vertex_list = area->spf_vertex_list;
+
+	area->spf_protected_resource = NULL;
+}
+
+static void
+ospf_ti_lfa_generate_p_space(struct ospf_area *area, struct vertex *child,
+			     struct protected_resource *protected_resource,
+			     bool recursive, struct list *pc_path)
+{
+	struct vertex *spf_orig;
+	struct list *vertex_list, *vertex_list_orig;
+	struct p_space *p_space;
+
+	p_space = XCALLOC(MTYPE_OSPF_P_SPACE, sizeof(struct p_space));
+	vertex_list = list_new();
+
+	/* The P-space will get its own SPF tree, so copy the old one */
+	ospf_spf_copy(area->spf, vertex_list);
+	p_space->root = listnode_head(vertex_list);
+	p_space->vertex_list = vertex_list;
+	p_space->protected_resource = protected_resource;
+
+	/* Initialize the Q spaces for this P space and protected resource */
+	p_space->q_spaces =
+		XCALLOC(MTYPE_OSPF_Q_SPACE, sizeof(struct q_spaces_head));
+	q_spaces_init(p_space->q_spaces);
+
+	/* 'Cut' the protected resource out of the new SPF tree */
+	ospf_spf_remove_resource(p_space->root, p_space->vertex_list,
+				 p_space->protected_resource);
+
+	/*
+	 * Since we are going to calculate more SPF trees for Q spaces, keep the
+	 * 'original' one here temporarily
+	 */
+	spf_orig = area->spf;
+	vertex_list_orig = area->spf_vertex_list;
+
+	/* Generate the post convergence SPF as a blueprint for backup paths */
+	ospf_ti_lfa_generate_post_convergence_spf(area, p_space);
+
+	/* Generate the relevant Q spaces for this particular P space */
+	ospf_ti_lfa_generate_q_spaces(area, p_space, child, recursive, pc_path);
+
+	/* Put the 'original' SPF tree back in place */
+	area->spf = spf_orig;
+	area->spf_vertex_list = vertex_list_orig;
+
+	/* We are finished, store the new P space */
+	p_spaces_add(area->p_spaces, p_space);
+}
+
+void ospf_ti_lfa_generate_p_spaces(struct ospf_area *area,
+				   enum protection_type protection_type)
+{
+	struct listnode *node, *inner_node;
+	struct vertex *root, *child;
+	struct vertex_parent *vertex_parent;
+	uint8_t *p, *lim;
+	struct router_lsa_link *l = NULL;
+	struct prefix stub_prefix, child_prefix;
+	struct protected_resource *protected_resource;
+
+	area->p_spaces =
+		XCALLOC(MTYPE_OSPF_P_SPACE, sizeof(struct p_spaces_head));
+	p_spaces_init(area->p_spaces);
+
+	root = area->spf;
+
+	/* Root or its router LSA was not created yet? */
+	if (!root || !root->lsa)
+		return;
+
+	stub_prefix.family = AF_INET;
+	child_prefix.family = AF_INET;
+	child_prefix.prefixlen = IPV4_MAX_BITLEN;
+
+	p = ((uint8_t *)root->lsa) + OSPF_LSA_HEADER_SIZE + 4;
+	lim = ((uint8_t *)root->lsa) + ntohs(root->lsa->length);
+
+	zlog_info("%s: Generating P spaces for area %pI4", __func__,
+		  &area->area_id);
+
+	/*
+	 * Iterate over all stub networks which target other OSPF neighbors.
+	 * Check the nexthop of the child vertex if a stub network is relevant.
+	 */
+	while (p < lim) {
+		l = (struct router_lsa_link *)p;
+		p += (OSPF_ROUTER_LSA_LINK_SIZE
+		      + (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
+
+		/* First comes node protection */
+		if (protection_type == OSPF_TI_LFA_NODE_PROTECTION) {
+			if (l->m[0].type == LSA_LINK_TYPE_POINTOPOINT) {
+				protected_resource = XCALLOC(
+					MTYPE_OSPF_P_SPACE,
+					sizeof(struct protected_resource));
+				protected_resource->type = protection_type;
+				protected_resource->router_id = l->link_id;
+				child = ospf_spf_vertex_find(
+					protected_resource->router_id,
+					root->children);
+				if (child)
+					ospf_ti_lfa_generate_p_space(
+						area, child, protected_resource,
+						true, NULL);
+			}
+
+			continue;
+		}
+
+		/* The rest is about link protection */
+		if (protection_type != OSPF_TI_LFA_LINK_PROTECTION)
+			continue;
+
+		if (l->m[0].type != LSA_LINK_TYPE_STUB)
+			continue;
+
+		stub_prefix.prefixlen = ip_masklen(l->link_data);
+		stub_prefix.u.prefix4 = l->link_id;
+
+		for (ALL_LIST_ELEMENTS_RO(root->children, node, child)) {
+
+			if (child->type != OSPF_VERTEX_ROUTER)
+				continue;
+
+			for (ALL_LIST_ELEMENTS_RO(child->parents, inner_node,
+						  vertex_parent)) {
+
+				child_prefix.u.prefix4 =
+					vertex_parent->nexthop->router;
+
+				/*
+				 * If there's a link for that stub network then
+				 * we will protect it. Hence generate a P space
+				 * for that particular link including the
+				 * Q spaces so we can later on generate a
+				 * backup path for the link.
+				 */
+				if (prefix_match(&stub_prefix, &child_prefix)) {
+					zlog_info(
+						"%s: Generating P space for %pI4",
+						__func__, &l->link_id);
+
+					protected_resource = XCALLOC(
+						MTYPE_OSPF_P_SPACE,
+						sizeof(struct
+						       protected_resource));
+					protected_resource->type =
+						protection_type;
+					protected_resource->link = l;
+
+					ospf_ti_lfa_generate_p_space(
+						area, child, protected_resource,
+						true, NULL);
+				}
+			}
+		}
+	}
+}
+
+static struct p_space *ospf_ti_lfa_get_p_space_by_path(struct ospf_area *area,
+						       struct ospf_path *path)
+{
+	struct p_space *p_space;
+	struct router_lsa_link *link;
+	struct vertex *child;
+	int type;
+
+	frr_each(p_spaces, area->p_spaces, p_space) {
+		type = p_space->protected_resource->type;
+
+		if (type == OSPF_TI_LFA_LINK_PROTECTION) {
+			link = p_space->protected_resource->link;
+			if ((path->nexthop.s_addr & link->link_data.s_addr)
+			    == (link->link_id.s_addr & link->link_data.s_addr))
+				return p_space;
+		}
+
+		if (type == OSPF_TI_LFA_NODE_PROTECTION) {
+			child = ospf_spf_vertex_by_nexthop(area->spf,
+							   &path->nexthop);
+			if (child
+			    && p_space->protected_resource->router_id.s_addr
+				       == child->id.s_addr)
+				return p_space;
+		}
+	}
+
+	return NULL;
+}
+
+void ospf_ti_lfa_insert_backup_paths(struct ospf_area *area,
+				     struct route_table *new_table)
+{
+	struct route_node *rn;
+	struct ospf_route *or;
+	struct ospf_path *path;
+	struct listnode *node;
+	struct p_space *p_space;
+	struct q_space *q_space, q_space_search;
+	struct vertex root_search;
+	char label_buf[MPLS_LABEL_STRLEN];
+
+	for (rn = route_top(new_table); rn; rn = route_next(rn)) {
+		or = rn->info;
+		if (or == NULL)
+			continue;
+
+		/* Insert a backup path for all OSPF paths */
+		for (ALL_LIST_ELEMENTS_RO(or->paths, node, path)) {
+
+			if (path->adv_router.s_addr == INADDR_ANY
+			    || path->nexthop.s_addr == INADDR_ANY)
+				continue;
+
+			if (IS_DEBUG_OSPF_TI_LFA)
+				zlog_debug(
+					"%s: attempting to insert backup path for prefix %pFX, router id %pI4 and nexthop %pI4.",
+					__func__, &rn->p, &path->adv_router,
+					&path->nexthop);
+
+			p_space = ospf_ti_lfa_get_p_space_by_path(area, path);
+			if (!p_space) {
+				if (IS_DEBUG_OSPF_TI_LFA)
+					zlog_debug(
+						"%s: P space not found for router id %pI4 and nexthop %pI4.",
+						__func__, &path->adv_router,
+						&path->nexthop);
+				continue;
+			}
+
+			root_search.id = path->adv_router;
+			q_space_search.root = &root_search;
+			q_space = q_spaces_find(p_space->q_spaces,
+						&q_space_search);
+			if (!q_space) {
+				if (IS_DEBUG_OSPF_TI_LFA)
+					zlog_debug(
+						"%s: Q space not found for advertising router %pI4.",
+						__func__, &path->adv_router);
+				continue;
+			}
+
+			/* If there's a backup label stack, insert it*/
+			if (q_space->label_stack) {
+				/* Init the backup path data in path */
+				path->srni.backup_label_stack = XCALLOC(
+					MTYPE_OSPF_PATH,
+					sizeof(struct mpls_label_stack)
+						+ sizeof(mpls_label_t)
+							  * q_space->label_stack
+								    ->num_labels);
+
+				/* Copy over the label stack */
+				path->srni.backup_label_stack->num_labels =
+					q_space->label_stack->num_labels;
+				memcpy(path->srni.backup_label_stack->label,
+				       q_space->label_stack->label,
+				       sizeof(mpls_label_t)
+					       * q_space->label_stack
+							 ->num_labels);
+
+				/* Set the backup nexthop too */
+				path->srni.backup_nexthop = q_space->nexthop;
+			}
+
+			if (path->srni.backup_label_stack) {
+				mpls_label2str(
+					path->srni.backup_label_stack
+						->num_labels,
+					path->srni.backup_label_stack->label,
+					label_buf, MPLS_LABEL_STRLEN, 0, true);
+				if (IS_DEBUG_OSPF_TI_LFA)
+					zlog_debug(
+						"%s: inserted backup path %s for prefix %pFX, router id %pI4 and nexthop %pI4.",
+						__func__, label_buf, &rn->p,
+						&path->adv_router,
+						&path->nexthop);
+			} else {
+				if (IS_DEBUG_OSPF_TI_LFA)
+					zlog_debug(
+						"%s: inserted NO backup path for prefix %pFX, router id %pI4 and nexthop %pI4.",
+						__func__, &rn->p,
+						&path->adv_router,
+						&path->nexthop);
+			}
+		}
+	}
+}
+
+void ospf_ti_lfa_free_p_spaces(struct ospf_area *area)
+{
+	struct p_space *p_space;
+	struct q_space *q_space;
+
+	while ((p_space = p_spaces_pop(area->p_spaces))) {
+		while ((q_space = q_spaces_pop(p_space->q_spaces))) {
+			ospf_spf_cleanup(q_space->root, q_space->vertex_list);
+
+			if (q_space->pc_path)
+				list_delete(&q_space->pc_path);
+
+			XFREE(MTYPE_OSPF_Q_SPACE, q_space->p_node_info);
+			XFREE(MTYPE_OSPF_Q_SPACE, q_space->q_node_info);
+			XFREE(MTYPE_OSPF_Q_SPACE, q_space->label_stack);
+			XFREE(MTYPE_OSPF_Q_SPACE, q_space);
+		}
+
+		ospf_spf_cleanup(p_space->root, p_space->vertex_list);
+		ospf_spf_cleanup(p_space->pc_spf, p_space->pc_vertex_list);
+		XFREE(MTYPE_OSPF_P_SPACE, p_space->protected_resource);
+
+		q_spaces_fini(p_space->q_spaces);
+		XFREE(MTYPE_OSPF_Q_SPACE, p_space->q_spaces);
+		XFREE(MTYPE_OSPF_P_SPACE, p_space);
+	}
+
+	p_spaces_fini(area->p_spaces);
+	XFREE(MTYPE_OSPF_P_SPACE, area->p_spaces);
+}
+
+void ospf_ti_lfa_compute(struct ospf_area *area, struct route_table *new_table,
+			 enum protection_type protection_type)
+{
+	/*
+	 * Generate P spaces per protected link/node and their respective Q
+	 * spaces, generate backup paths (MPLS label stacks) by finding P/Q
+	 * nodes.
+	 */
+	ospf_ti_lfa_generate_p_spaces(area, protection_type);
+
+	/* Insert the generated backup paths into the routing table. */
+	ospf_ti_lfa_insert_backup_paths(area, new_table);
+
+	/* Cleanup P spaces and related datastructures including Q spaces. */
+	ospf_ti_lfa_free_p_spaces(area);
+}