1 files changed, 541 insertions, 117 deletions

diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c
index 4665f53edb..82acd0829c 100644
--- a/ospfd/ospf_spf.c
+++ b/ospfd/ospf_spf.c
@@ -46,6 +46,7 @@
 #include "ospfd/ospf_abr.h"
 #include "ospfd/ospf_dump.h"
 #include "ospfd/ospf_sr.h"
+#include "ospfd/ospf_ti_lfa.h"
 #include "ospfd/ospf_errors.h"
 
 /* Variables to ensure a SPF scheduled log message is printed only once */
@@ -141,11 +142,16 @@ static void ospf_canonical_nexthops_free(struct vertex *root)
 			ospf_canonical_nexthops_free(child);
 
 		/* Free child nexthops pointing back to this root vertex */
-		for (ALL_LIST_ELEMENTS(child->parents, n2, nn2, vp))
+		for (ALL_LIST_ELEMENTS(child->parents, n2, nn2, vp)) {
 			if (vp->parent == root && vp->nexthop) {
 				vertex_nexthop_free(vp->nexthop);
 				vp->nexthop = NULL;
+				if (vp->local_nexthop) {
+					vertex_nexthop_free(vp->local_nexthop);
+					vp->local_nexthop = NULL;
+				}
 			}
+		}
 	}
 }
 
@@ -154,7 +160,8 @@ static void ospf_canonical_nexthops_free(struct vertex *root)
  * vertex_nexthop, with refcounts.
  */
 static struct vertex_parent *vertex_parent_new(struct vertex *v, int backlink,
-					       struct vertex_nexthop *hop)
+					       struct vertex_nexthop *hop,
+					       struct vertex_nexthop *lhop)
 {
 	struct vertex_parent *new;
 
@@ -163,6 +170,7 @@ static struct vertex_parent *vertex_parent_new(struct vertex *v, int backlink,
 	new->parent = v;
 	new->backlink = backlink;
 	new->nexthop = hop;
+	new->local_nexthop = lhop;
 
 	return new;
 }
@@ -172,7 +180,7 @@ static void vertex_parent_free(void *p)
 	XFREE(MTYPE_OSPF_VERTEX_PARENT, p);
 }
 
-static int vertex_parent_cmp(void *aa, void *bb)
+int vertex_parent_cmp(void *aa, void *bb)
 {
 	struct vertex_parent *a = aa, *b = bb;
 	return IPV4_ADDR_CMP(&a->nexthop->router, &b->nexthop->router);
@@ -284,6 +292,257 @@ static void ospf_vertex_add_parent(struct vertex *v)
 	}
 }
 
+/* Find a vertex according to its router id */
+struct vertex *ospf_spf_vertex_find(struct in_addr id, struct list *vertex_list)
+{
+	struct listnode *node;
+	struct vertex *found;
+
+	for (ALL_LIST_ELEMENTS_RO(vertex_list, node, found)) {
+		if (found->id.s_addr == id.s_addr)
+			return found;
+	}
+
+	return NULL;
+}
+
+/* Find a vertex parent according to its router id */
+struct vertex_parent *ospf_spf_vertex_parent_find(struct in_addr id,
+						  struct vertex *vertex)
+{
+	struct listnode *node;
+	struct vertex_parent *found;
+
+	for (ALL_LIST_ELEMENTS_RO(vertex->parents, node, found)) {
+		if (found->parent->id.s_addr == id.s_addr)
+			return found;
+	}
+
+	return NULL;
+}
+
+struct vertex *ospf_spf_vertex_by_nexthop(struct vertex *root,
+					  struct in_addr *nexthop)
+{
+	struct listnode *node;
+	struct vertex *child;
+	struct vertex_parent *vertex_parent;
+
+	for (ALL_LIST_ELEMENTS_RO(root->children, node, child)) {
+		vertex_parent = ospf_spf_vertex_parent_find(root->id, child);
+		if (vertex_parent->nexthop->router.s_addr == nexthop->s_addr)
+			return child;
+	}
+
+	return NULL;
+}
+
+/* Create a deep copy of a SPF vertex without children and parents */
+static struct vertex *ospf_spf_vertex_copy(struct vertex *vertex)
+{
+	struct vertex *copy;
+
+	copy = XCALLOC(MTYPE_OSPF_VERTEX, sizeof(struct vertex));
+
+	memcpy(copy, vertex, sizeof(struct vertex));
+	copy->parents = list_new();
+	copy->parents->del = vertex_parent_free;
+	copy->parents->cmp = vertex_parent_cmp;
+	copy->children = list_new();
+
+	return copy;
+}
+
+/* Create a deep copy of a SPF vertex_parent */
+static struct vertex_parent *
+ospf_spf_vertex_parent_copy(struct vertex_parent *vertex_parent)
+{
+	struct vertex_parent *vertex_parent_copy;
+	struct vertex_nexthop *nexthop_copy, *local_nexthop_copy;
+
+	vertex_parent_copy =
+		XCALLOC(MTYPE_OSPF_VERTEX, sizeof(struct vertex_parent));
+
+	nexthop_copy = vertex_nexthop_new();
+	local_nexthop_copy = vertex_nexthop_new();
+
+	memcpy(vertex_parent_copy, vertex_parent, sizeof(struct vertex_parent));
+	memcpy(nexthop_copy, vertex_parent->nexthop,
+	       sizeof(struct vertex_nexthop));
+	memcpy(local_nexthop_copy, vertex_parent->local_nexthop,
+	       sizeof(struct vertex_nexthop));
+
+	vertex_parent_copy->nexthop = nexthop_copy;
+	vertex_parent_copy->local_nexthop = local_nexthop_copy;
+
+	return vertex_parent_copy;
+}
+
+/* Create a deep copy of a SPF tree */
+void ospf_spf_copy(struct vertex *vertex, struct list *vertex_list)
+{
+	struct listnode *node;
+	struct vertex *vertex_copy, *child, *child_copy, *parent_copy;
+	struct vertex_parent *vertex_parent, *vertex_parent_copy;
+
+	/* First check if the node is already in the vertex list */
+	vertex_copy = ospf_spf_vertex_find(vertex->id, vertex_list);
+	if (!vertex_copy) {
+		vertex_copy = ospf_spf_vertex_copy(vertex);
+		listnode_add(vertex_list, vertex_copy);
+	}
+
+	/* Copy all parents, create parent nodes if necessary */
+	for (ALL_LIST_ELEMENTS_RO(vertex->parents, node, vertex_parent)) {
+		parent_copy = ospf_spf_vertex_find(vertex_parent->parent->id,
+						   vertex_list);
+		if (!parent_copy) {
+			parent_copy =
+				ospf_spf_vertex_copy(vertex_parent->parent);
+			listnode_add(vertex_list, parent_copy);
+		}
+		vertex_parent_copy = ospf_spf_vertex_parent_copy(vertex_parent);
+		vertex_parent_copy->parent = parent_copy;
+		listnode_add(vertex_copy->parents, vertex_parent_copy);
+	}
+
+	/* Copy all children, create child nodes if necessary */
+	for (ALL_LIST_ELEMENTS_RO(vertex->children, node, child)) {
+		child_copy = ospf_spf_vertex_find(child->id, vertex_list);
+		if (!child_copy) {
+			child_copy = ospf_spf_vertex_copy(child);
+			listnode_add(vertex_list, child_copy);
+		}
+		listnode_add(vertex_copy->children, child_copy);
+	}
+
+	/* Finally continue copying with child nodes */
+	for (ALL_LIST_ELEMENTS_RO(vertex->children, node, child))
+		ospf_spf_copy(child, vertex_list);
+}
+
+static void ospf_spf_remove_branch(struct vertex_parent *vertex_parent,
+				   struct vertex *child,
+				   struct list *vertex_list)
+{
+	struct listnode *node, *nnode, *inner_node, *inner_nnode;
+	struct vertex *grandchild;
+	struct vertex_parent *vertex_parent_found;
+	bool has_more_links = false;
+
+	/*
+	 * First check if there are more nexthops for that parent to that child
+	 */
+	for (ALL_LIST_ELEMENTS_RO(child->parents, node, vertex_parent_found)) {
+		if (vertex_parent_found->parent->id.s_addr
+			    == vertex_parent->parent->id.s_addr
+		    && vertex_parent_found->nexthop->router.s_addr
+			       != vertex_parent->nexthop->router.s_addr)
+			has_more_links = true;
+	}
+
+	/*
+	 * No more links from that parent? Then delete the child from its
+	 * children list.
+	 */
+	if (!has_more_links)
+		listnode_delete(vertex_parent->parent->children, child);
+
+	/*
+	 * Delete the vertex_parent from the child parents list, this needs to
+	 * be done anyway.
+	 */
+	listnode_delete(child->parents, vertex_parent);
+
+	/*
+	 * Are there actually more parents left? If not, then delete the child!
+	 * This is done by recursively removing the links to the grandchildren,
+	 * such that finally the child can be removed without leaving unused
+	 * partial branches.
+	 */
+	if (child->parents->count == 0) {
+		for (ALL_LIST_ELEMENTS(child->children, node, nnode,
+				       grandchild)) {
+			for (ALL_LIST_ELEMENTS(grandchild->parents, inner_node,
+					       inner_nnode,
+					       vertex_parent_found)) {
+				ospf_spf_remove_branch(vertex_parent_found,
+						       grandchild, vertex_list);
+			}
+		}
+		listnode_delete(vertex_list, child);
+		ospf_vertex_free(child);
+	}
+}
+
+static int ospf_spf_remove_link(struct vertex *vertex, struct list *vertex_list,
+				struct router_lsa_link *link)
+{
+	struct listnode *node, *inner_node;
+	struct vertex *child;
+	struct vertex_parent *vertex_parent;
+
+	/*
+	 * Identify the node who shares a subnet (given by the link) with a
+	 * child and remove the branch of this particular child.
+	 */
+	for (ALL_LIST_ELEMENTS_RO(vertex->children, node, child)) {
+		for (ALL_LIST_ELEMENTS_RO(child->parents, inner_node,
+					  vertex_parent)) {
+			if ((vertex_parent->local_nexthop->router.s_addr
+			     & link->link_data.s_addr)
+			    == (link->link_id.s_addr
+				& link->link_data.s_addr)) {
+				ospf_spf_remove_branch(vertex_parent, child,
+						       vertex_list);
+				return 0;
+			}
+		}
+	}
+
+	/* No link found yet, move on recursively */
+	for (ALL_LIST_ELEMENTS_RO(vertex->children, node, child)) {
+		if (ospf_spf_remove_link(child, vertex_list, link) == 0)
+			return 0;
+	}
+
+	/* link was not removed yet */
+	return 1;
+}
+
+void ospf_spf_remove_resource(struct vertex *vertex, struct list *vertex_list,
+			      struct protected_resource *resource)
+{
+	struct listnode *node, *nnode;
+	struct vertex *found;
+	struct vertex_parent *vertex_parent;
+
+	switch (resource->type) {
+	case OSPF_TI_LFA_LINK_PROTECTION:
+		ospf_spf_remove_link(vertex, vertex_list, resource->link);
+		break;
+	case OSPF_TI_LFA_NODE_PROTECTION:
+		found = ospf_spf_vertex_find(resource->router_id, vertex_list);
+		if (!found)
+			break;
+
+		/*
+		 * Remove the node by removing all links from its parents. Note
+		 * that the child is automatically removed here with the last
+		 * link from a parent, hence no explicit removal of the node.
+		 */
+		for (ALL_LIST_ELEMENTS(found->parents, node, nnode,
+				       vertex_parent))
+			ospf_spf_remove_branch(vertex_parent, found,
+					       vertex_list);
+
+		break;
+	default:
+		/* do nothing */
+		break;
+	}
+}
+
 static void ospf_spf_init(struct ospf_area *area, struct ospf_lsa *root_lsa,
 			  bool is_dry_run, bool is_root_node)
 {
@@ -427,6 +686,7 @@ static void ospf_spf_flush_parents(struct vertex *w)
  */
 static void ospf_spf_add_parent(struct vertex *v, struct vertex *w,
 				struct vertex_nexthop *newhop,
+				struct vertex_nexthop *newlhop,
 				unsigned int distance)
 {
 	struct vertex_parent *vp, *wp;
@@ -482,7 +742,8 @@ static void ospf_spf_add_parent(struct vertex *v, struct vertex *w,
 		}
 	}
 
-	vp = vertex_parent_new(v, ospf_lsa_has_link(w->lsa, v->lsa), newhop);
+	vp = vertex_parent_new(v, ospf_lsa_has_link(w->lsa, v->lsa), newhop,
+			       newlhop);
 	listnode_add_sort(w->parents, vp);
 
 	return;
@@ -541,7 +802,7 @@ static unsigned int ospf_nexthop_calculation(struct ospf_area *area,
 					     unsigned int distance, int lsa_pos)
 {
 	struct listnode *node, *nnode;
-	struct vertex_nexthop *nh;
+	struct vertex_nexthop *nh, *lnh;
 	struct vertex_parent *vp;
 	unsigned int added = 0;
 	char buf1[BUFSIZ];
@@ -586,17 +847,22 @@ static unsigned int ospf_nexthop_calculation(struct ospf_area *area,
 				struct ospf_interface *oi = NULL;
 				struct in_addr nexthop = {.s_addr = 0};
 
-				oi = ospf_if_lookup_by_lsa_pos(area, lsa_pos);
-				if (!oi) {
-					zlog_debug(
-						"%s: OI not found in LSA: lsa_pos: %d link_id:%s link_data:%s",
-						__func__, lsa_pos,
-						inet_ntop(AF_INET, &l->link_id,
-							  buf1, BUFSIZ),
-						inet_ntop(AF_INET,
-							  &l->link_data, buf2,
-							  BUFSIZ));
-					return 0;
+				if (area->spf_root_node) {
+					oi = ospf_if_lookup_by_lsa_pos(area,
+								       lsa_pos);
+					if (!oi) {
+						zlog_debug(
+							"%s: OI not found in LSA: lsa_pos: %d link_id:%s link_data:%s",
+							__func__, lsa_pos,
+							inet_ntop(AF_INET,
+								  &l->link_id,
+								  buf1, BUFSIZ),
+							inet_ntop(AF_INET,
+								  &l->link_data,
+								  buf2,
+								  BUFSIZ));
+						return 0;
+					}
 				}
 
 				/*
@@ -644,7 +910,21 @@ static unsigned int ospf_nexthop_calculation(struct ospf_area *area,
 				 * as described above using a reverse lookup to
 				 * figure out the nexthop.
 				 */
-				if (oi->type == OSPF_IFTYPE_POINTOPOINT) {
+
+				/*
+				 * HACK: we don't know (yet) how to distinguish
+				 * between P2P and P2MP interfaces by just
+				 * looking at LSAs, which is important for
+				 * TI-LFA since you want to do SPF calculations
+				 * from the perspective of other nodes. Since
+				 * TI-LFA is currently not implemented for P2MP
+				 * we just check here if it is enabled and then
+				 * blindly assume that P2P is used. Ultimately
+				 * the interface code needs to be removed
+				 * somehow.
+				 */
+				if (area->ospf->ti_lfa_enabled
+				    || (oi && oi->type == OSPF_IFTYPE_POINTOPOINT)) {
 					struct ospf_neighbor *nbr_w = NULL;
 
 					/* Calculating node is root node, link
@@ -673,7 +953,7 @@ static unsigned int ospf_nexthop_calculation(struct ospf_area *area,
 							}
 						}
 					}
-				} else if (oi->type
+				} else if (oi && oi->type
 					   == OSPF_IFTYPE_POINTOMULTIPOINT) {
 					struct prefix_ipv4 la;
 
@@ -703,12 +983,22 @@ static unsigned int ospf_nexthop_calculation(struct ospf_area *area,
 					nh = vertex_nexthop_new();
 					nh->router = nexthop;
 					nh->lsa_pos = lsa_pos;
-					ospf_spf_add_parent(v, w, nh, distance);
+
+					/*
+					 * Since v is the root the nexthop and
+					 * local nexthop are the same.
+					 */
+					lnh = vertex_nexthop_new();
+					memcpy(lnh, nh,
+					       sizeof(struct vertex_nexthop));
+
+					ospf_spf_add_parent(v, w, nh, lnh,
+							    distance);
 					return 1;
 				} else
 					zlog_info(
 						"%s: could not determine nexthop for link %s",
-						__func__, oi->ifp->name);
+						__func__, oi ? oi->ifp->name : "");
 			} /* end point-to-point link from V to W */
 			else if (l->m[0].type == LSA_LINK_TYPE_VIRTUALLINK) {
 				/*
@@ -733,7 +1023,17 @@ static unsigned int ospf_nexthop_calculation(struct ospf_area *area,
 					nh = vertex_nexthop_new();
 					nh->router = vl_data->nexthop.router;
 					nh->lsa_pos = vl_data->nexthop.lsa_pos;
-					ospf_spf_add_parent(v, w, nh, distance);
+
+					/*
+					 * Since v is the root the nexthop and
+					 * local nexthop are the same.
+					 */
+					lnh = vertex_nexthop_new();
+					memcpy(lnh, nh,
+					       sizeof(struct vertex_nexthop));
+
+					ospf_spf_add_parent(v, w, nh, lnh,
+							    distance);
 					return 1;
 				} else
 					zlog_info(
@@ -747,7 +1047,15 @@ static unsigned int ospf_nexthop_calculation(struct ospf_area *area,
 			nh = vertex_nexthop_new();
 			nh->router.s_addr = 0; /* Nexthop not required */
 			nh->lsa_pos = lsa_pos;
-			ospf_spf_add_parent(v, w, nh, distance);
+
+			/*
+			 * Since v is the root the nexthop and
+			 * local nexthop are the same.
+			 */
+			lnh = vertex_nexthop_new();
+			memcpy(lnh, nh, sizeof(struct vertex_nexthop));
+
+			ospf_spf_add_parent(v, w, nh, lnh, distance);
 			return 1;
 		}
 	} /* end V is the root */
@@ -780,8 +1088,18 @@ static unsigned int ospf_nexthop_calculation(struct ospf_area *area,
 					nh = vertex_nexthop_new();
 					nh->router = l->link_data;
 					nh->lsa_pos = vp->nexthop->lsa_pos;
+
+					/*
+					 * Since v is the root the nexthop and
+					 * local nexthop are the same.
+					 */
+					lnh = vertex_nexthop_new();
+					memcpy(lnh, nh,
+					       sizeof(struct vertex_nexthop));
+
 					added = 1;
-					ospf_spf_add_parent(v, w, nh, distance);
+					ospf_spf_add_parent(v, w, nh, lnh,
+							    distance);
 				}
 				/*
 				 * Note lack of return is deliberate. See next
@@ -829,12 +1147,154 @@ static unsigned int ospf_nexthop_calculation(struct ospf_area *area,
 
 	for (ALL_LIST_ELEMENTS(v->parents, node, nnode, vp)) {
 		added = 1;
-		ospf_spf_add_parent(v, w, vp->nexthop, distance);
+
+		/*
+		 * The nexthop is inherited, but the local nexthop still needs
+		 * to be created.
+		 */
+		if (l) {
+			lnh = vertex_nexthop_new();
+			lnh->router = l->link_data;
+			lnh->lsa_pos = lsa_pos;
+		} else {
+			lnh = NULL;
+		}
+
+		ospf_spf_add_parent(v, w, vp->nexthop, lnh, distance);
 	}
 
 	return added;
 }
 
+static int ospf_spf_is_protected_resource(struct ospf_area *area,
+					  struct router_lsa_link *link,
+					  struct lsa_header *lsa)
+{
+	uint8_t *p, *lim;
+	struct router_lsa_link *p_link;
+	struct router_lsa_link *l = NULL;
+	struct in_addr router_id;
+	int link_type;
+
+	if (!area->spf_protected_resource)
+		return 0;
+
+	link_type = link->m[0].type;
+
+	switch (area->spf_protected_resource->type) {
+	case OSPF_TI_LFA_LINK_PROTECTION:
+		p_link = area->spf_protected_resource->link;
+		if (!p_link)
+			return 0;
+
+		/* For P2P: check if the link belongs to the same subnet */
+		if (link_type == LSA_LINK_TYPE_POINTOPOINT
+		    && (p_link->link_id.s_addr & p_link->link_data.s_addr)
+			       == (link->link_data.s_addr
+				   & p_link->link_data.s_addr))
+			return 1;
+
+		/* For stub: check if this the same subnet */
+		if (link_type == LSA_LINK_TYPE_STUB
+		    && (p_link->link_id.s_addr == link->link_id.s_addr)
+		    && (p_link->link_data.s_addr == link->link_data.s_addr))
+			return 1;
+
+		break;
+	case OSPF_TI_LFA_NODE_PROTECTION:
+		router_id = area->spf_protected_resource->router_id;
+		if (router_id.s_addr == INADDR_ANY)
+			return 0;
+
+		/* For P2P: check if the link leads to the protected node */
+		if (link_type == LSA_LINK_TYPE_POINTOPOINT
+		    && link->link_id.s_addr == router_id.s_addr)
+			return 1;
+
+		/* The rest is about stub links! */
+		if (link_type != LSA_LINK_TYPE_STUB)
+			return 0;
+
+		/*
+		 * Check if there's a P2P link in the router LSA with the
+		 * corresponding link data in the same subnet.
+		 */
+
+		p = ((uint8_t *)lsa) + OSPF_LSA_HEADER_SIZE + 4;
+		lim = ((uint8_t *)lsa) + ntohs(lsa->length);
+
+		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));
+
+			/* We only care about P2P with the proper link id */
+			if ((l->m[0].type != LSA_LINK_TYPE_POINTOPOINT)
+			    || (l->link_id.s_addr != router_id.s_addr))
+				continue;
+
+			/* Link data in the subnet given by the link? */
+			if ((link->link_id.s_addr & link->link_data.s_addr)
+			    == (l->link_data.s_addr & link->link_data.s_addr))
+				return 1;
+		}
+
+		break;
+	case OSPF_TI_LFA_UNDEFINED_PROTECTION:
+		break;
+	}
+
+	return 0;
+}
+
+/*
+ * For TI-LFA we need the reverse SPF for Q spaces. The reverse SPF is created
+ * by honoring the weight of the reverse 'edge', e.g. the edge from W to V, and
+ * NOT the weight of the 'edge' from V to W as usual. Hence we need to find the
+ * corresponding link in the LSA of W and extract the particular weight.
+ *
+ * TODO: Only P2P supported by now!
+ */
+static uint16_t get_reverse_distance(struct vertex *v,
+				     struct router_lsa_link *l,
+				     struct ospf_lsa *w_lsa)
+{
+	uint8_t *p, *lim;
+	struct router_lsa_link *w_link;
+	uint16_t distance = 0;
+
+	assert(w_lsa && w_lsa->data);
+
+	p = ((uint8_t *)w_lsa->data) + OSPF_LSA_HEADER_SIZE + 4;
+	lim = ((uint8_t *)w_lsa->data) + ntohs(w_lsa->data->length);
+
+	while (p < lim) {
+		w_link = (struct router_lsa_link *)p;
+		p += (OSPF_ROUTER_LSA_LINK_SIZE
+		      + (w_link->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
+
+		/* Only care about P2P with link ID equal to V's router id */
+		if (w_link->m[0].type == LSA_LINK_TYPE_POINTOPOINT
+		    && w_link->link_id.s_addr == v->id.s_addr) {
+			distance = ntohs(w_link->m[0].metric);
+			break;
+		}
+	}
+
+	/*
+	 * This might happen if the LSA for W is not complete yet. In this
+	 * case we take the weight of the 'forward' link from V. When the LSA
+	 * for W is completed the reverse SPF is run again anyway.
+	 */
+	if (distance == 0)
+		distance = ntohs(l->m[0].metric);
+
+	if (IS_DEBUG_OSPF_EVENT)
+		zlog_debug("%s: reversed distance is %u", __func__, distance);
+
+	return distance;
+}
+
 /*
  * RFC2328 16.1 (2).
  * v is on the SPF tree. Examine the links in v's LSA. Update the list of
@@ -850,6 +1310,7 @@ static void ospf_spf_next(struct vertex *v, struct ospf_area *area,
 	struct router_lsa_link *l = NULL;
 	struct in_addr *r;
 	int type = 0, lsa_pos = -1, lsa_pos_next = 0;
+	uint16_t link_distance;
 
 	/*
 	 * If this is a router-LSA, and bit V of the router-LSA (see Section
@@ -892,6 +1353,16 @@ static void ospf_spf_next(struct vertex *v, struct ospf_area *area,
 				continue;
 
 			/*
+			 * Don't process TI-LFA protected resources.
+			 *
+			 * TODO: Replace this by a proper solution, e.g. remove
+			 * corresponding links from the LSDB and run the SPF
+			 * algo with the stripped-down LSDB.
+			 */
+			if (ospf_spf_is_protected_resource(area, l, v->lsa))
+				continue;
+
+			/*
 			 * (b) Otherwise, W is a transit vertex (router or
 			 * transit network). Look up the vertex W's LSA
 			 * (router-LSA or network-LSA) in Area A's link state
@@ -928,8 +1399,19 @@ static void ospf_spf_next(struct vertex *v, struct ospf_area *area,
 				continue;
 			}
 
+			/*
+			 * For TI-LFA we might need the reverse SPF.
+			 * Currently only works with P2P!
+			 */
+			if (type == LSA_LINK_TYPE_POINTOPOINT
+			    && area->spf_reversed)
+				link_distance =
+					get_reverse_distance(v, l, w_lsa);
+			else
+				link_distance = ntohs(l->m[0].metric);
+
 			/* step (d) below */
-			distance = v->distance + ntohs(l->m[0].metric);
+			distance = v->distance + link_distance;
 		} else {
 			/* In case of V is Network-LSA. */
 			r = (struct in_addr *)p;
@@ -1069,8 +1551,7 @@ void ospf_spf_print(struct vty *vty, struct vertex *v, int i)
 	struct vertex_parent *parent;
 
 	if (v->type == OSPF_VERTEX_ROUTER) {
-		vty_out(vty, "SPF Result: depth %d [R] %pI4\n", i,
-			&v->lsa->id);
+		vty_out(vty, "SPF Result: depth %d [R] %pI4\n", i, &v->lsa->id);
 	} else {
 		struct network_lsa *lsa = (struct network_lsa *)v->lsa;
 		vty_out(vty, "SPF Result: depth %d [N] %pI4/%d\n", i,
@@ -1078,9 +1559,11 @@ void ospf_spf_print(struct vty *vty, struct vertex *v, int i)
 	}
 
 	for (ALL_LIST_ELEMENTS_RO(v->parents, nnode, parent)) {
-		vty_out(vty, " nexthop %pI4 lsa pos %d\n",
-			&parent->nexthop->router,
-			parent->nexthop->lsa_pos);
+		vty_out(vty,
+			" nexthop %pI4 lsa pos %d -- local nexthop %pI4 lsa pos %d\n",
+			&parent->nexthop->router, parent->nexthop->lsa_pos,
+			&parent->local_nexthop->router,
+			parent->local_nexthop->lsa_pos);
 	}
 
 	i++;
@@ -1128,7 +1611,9 @@ static void ospf_spf_process_stubs(struct ospf_area *area, struct vertex *v,
 			p += (OSPF_ROUTER_LSA_LINK_SIZE
 			      + (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
 
-			if (l->m[0].type == LSA_LINK_TYPE_STUB)
+			/* Don't process TI-LFA protected resources */
+			if (l->m[0].type == LSA_LINK_TYPE_STUB
+			    && !ospf_spf_is_protected_resource(area, l, v->lsa))
 				ospf_intra_add_stub(rt, l, v, area,
 						    parent_is_root, lsa_pos);
 			lsa_pos++;
@@ -1190,73 +1675,13 @@ void ospf_spf_cleanup(struct vertex *spf, struct list *vertex_list)
 	 * attached the first level of router vertices attached to the
 	 * root vertex, see ospf_nexthop_calculation.
 	 */
-	ospf_canonical_nexthops_free(spf);
+	if (spf)
+		ospf_canonical_nexthops_free(spf);
 
 	/* Free SPF vertices list with deconstructor ospf_vertex_free. */
-	list_delete(&vertex_list);
-}
-
-#if 0
-static void
-ospf_rtrs_print (struct route_table *rtrs)
-{
-  struct route_node *rn;
-  struct list *or_list;
-  struct listnode *ln;
-  struct listnode *pnode;
-  struct ospf_route *or;
-  struct ospf_path *path;
-  char buf1[BUFSIZ];
-  char buf2[BUFSIZ];
-
-  if (IS_DEBUG_OSPF_EVENT)
-    zlog_debug ("ospf_rtrs_print() start");
-
-  for (rn = route_top (rtrs); rn; rn = route_next (rn))
-    if ((or_list = rn->info) != NULL)
-      for (ALL_LIST_ELEMENTS_RO (or_list, ln, or))
-        {
-          switch (or->path_type)
-            {
-            case OSPF_PATH_INTRA_AREA:
-              if (IS_DEBUG_OSPF_EVENT)
-                zlog_debug ("%s   [%d] area: %s",
-                           inet_ntop (AF_INET, &or->id, buf1, BUFSIZ),
-                           or->cost, inet_ntop (AF_INET, &or->u.std.area_id,
-                                                buf2, BUFSIZ));
-              break;
-            case OSPF_PATH_INTER_AREA:
-              if (IS_DEBUG_OSPF_EVENT)
-                zlog_debug ("%s IA [%d] area: %s",
-                           inet_ntop (AF_INET, &or->id, buf1, BUFSIZ),
-                           or->cost, inet_ntop (AF_INET, &or->u.std.area_id,
-                                                buf2, BUFSIZ));
-              break;
-            default:
-              break;
-            }
-
-          for (ALL_LIST_ELEMENTS_RO (or->paths, pnode, path))
-            {
-              if (path->nexthop.s_addr == INADDR_ANY)
-                {
-                  if (IS_DEBUG_OSPF_EVENT)
-                    zlog_debug ("   directly attached to %s\r",
-				ifindex2ifname (path->ifindex), VRF_DEFAULT);
-                }
-              else
-                {
-                  if (IS_DEBUG_OSPF_EVENT)
-                    zlog_debug ("   via %pI4, %s\r",
-				&path->nexthop,
-				ifindex2ifname (path->ifindex), VRF_DEFAULT);
-                }
-            }
-        }
-
-  zlog_debug ("ospf_rtrs_print() end");
+	if (vertex_list)
+		list_delete(&vertex_list);
 }
-#endif
 
 /* Calculating the shortest-path tree for an area, see RFC2328 16.1. */
 void ospf_spf_calculate(struct ospf_area *area, struct ospf_lsa *root_lsa,
@@ -1359,19 +1784,27 @@ void ospf_spf_calculate(struct ospf_area *area, struct ospf_lsa *root_lsa,
 	if (IS_DEBUG_OSPF_EVENT)
 		zlog_debug("ospf_spf_calculate: Stop. %zd vertices",
 			   mtype_stats_alloc(MTYPE_OSPF_VERTEX));
+}
+
+void ospf_spf_calculate_area(struct ospf *ospf, struct ospf_area *area,
+			     struct route_table *new_table,
+			     struct route_table *new_rtrs)
+{
+	ospf_spf_calculate(area, area->router_lsa_self, new_table, new_rtrs,
+			   false, true);
 
-	/* If this is a dry run then keep the SPF data in place */
-	if (!area->spf_dry_run)
-		ospf_spf_cleanup(area->spf, area->spf_vertex_list);
+	if (ospf->ti_lfa_enabled)
+		ospf_ti_lfa_compute(area, new_table,
+				    ospf->ti_lfa_protection_type);
+
+	ospf_spf_cleanup(area->spf, area->spf_vertex_list);
 }
 
-int ospf_spf_calculate_areas(struct ospf *ospf, struct route_table *new_table,
-			     struct route_table *new_rtrs, bool is_dry_run,
-			     bool is_root_node)
+void ospf_spf_calculate_areas(struct ospf *ospf, struct route_table *new_table,
+			      struct route_table *new_rtrs)
 {
 	struct ospf_area *area;
 	struct listnode *node, *nnode;
-	int areas_processed = 0;
 
 	/* Calculate SPF for each area. */
 	for (ALL_LIST_ELEMENTS(ospf->areas, node, nnode, area)) {
@@ -1380,20 +1813,13 @@ int ospf_spf_calculate_areas(struct ospf *ospf, struct route_table *new_table,
 		if (ospf->backbone && ospf->backbone == area)
 			continue;
 
-		ospf_spf_calculate(area, area->router_lsa_self, new_table,
-				   new_rtrs, is_dry_run, is_root_node);
-		areas_processed++;
+		ospf_spf_calculate_area(ospf, area, new_table, new_rtrs);
 	}
 
 	/* SPF for backbone, if required */
-	if (ospf->backbone) {
-		area = ospf->backbone;
-		ospf_spf_calculate(area, area->router_lsa_self, new_table,
-				   new_rtrs, is_dry_run, is_root_node);
-		areas_processed++;
-	}
-
-	return areas_processed;
+	if (ospf->backbone)
+		ospf_spf_calculate_area(ospf, ospf->backbone, new_table,
+					new_rtrs);
 }
 
 /* Worker for SPF calculation scheduler. */
@@ -1402,7 +1828,6 @@ static int ospf_spf_calculate_schedule_worker(struct thread *thread)
 	struct ospf *ospf = THREAD_ARG(thread);
 	struct route_table *new_table, *new_rtrs;
 	struct timeval start_time, spf_start_time;
-	int areas_processed;
 	unsigned long ia_time, prune_time, rt_time;
 	unsigned long abr_time, total_spf_time, spf_time;
 	char rbuf[32]; /* reason_buf */
@@ -1418,8 +1843,7 @@ static int ospf_spf_calculate_schedule_worker(struct thread *thread)
 	monotime(&spf_start_time);
 	new_table = route_table_init(); /* routing table */
 	new_rtrs = route_table_init();  /* ABR/ASBR routing table */
-	areas_processed = ospf_spf_calculate_areas(ospf, new_table, new_rtrs,
-						   false, true);
+	ospf_spf_calculate_areas(ospf, new_table, new_rtrs);
 	spf_time = monotime_since(&spf_start_time, NULL);
 
 	ospf_vl_shut_unapproved(ospf);
@@ -1512,7 +1936,7 @@ static int ospf_spf_calculate_schedule_worker(struct thread *thread)
 		zlog_info("        RouteInstall: %ld", rt_time);
 		if (IS_OSPF_ABR(ospf))
 			zlog_info("                 ABR: %ld (%d areas)",
-				  abr_time, areas_processed);
+				  abr_time, ospf->areas->count);
 		zlog_info("Reason(s) for SPF: %s", rbuf);
 	}