Merge pull request #6912 from GalaxyGorilla/ospf_ti_lfa_prep

ospfd: preparation for TI-LFA

6 files changed, 540 insertions, 391 deletions

diff --git a/ospfd/ospf_interface.c b/ospfd/ospf_interface.c
index 7977a2a9f..af801da8d 100644
--- a/ospfd/ospf_interface.c
+++ b/ospfd/ospf_interface.c
@@ -995,7 +995,8 @@ void ospf_vl_delete(struct ospf *ospf, struct ospf_vl_data *vl_data)
 	ospf_vl_data_free(vl_data);
 }
 
-static int ospf_vl_set_params(struct ospf_vl_data *vl_data, struct vertex *v)
+static int ospf_vl_set_params(struct ospf_area *area,
+			      struct ospf_vl_data *vl_data, struct vertex *v)
 {
 	int changed = 0;
 	struct ospf_interface *voi;
@@ -1003,6 +1004,7 @@ static int ospf_vl_set_params(struct ospf_vl_data *vl_data, struct vertex *v)
 	struct vertex_parent *vp = NULL;
 	unsigned int i;
 	struct router_lsa *rl;
+	struct ospf_interface *oi;
 
 	voi = vl_data->vl_oi;
 
@@ -1013,17 +1015,24 @@ static int ospf_vl_set_params(struct ospf_vl_data *vl_data, struct vertex *v)
 	}
 
 	for (ALL_LIST_ELEMENTS_RO(v->parents, node, vp)) {
-		vl_data->nexthop.oi = vp->nexthop->oi;
+		vl_data->nexthop.lsa_pos = vp->nexthop->lsa_pos;
 		vl_data->nexthop.router = vp->nexthop->router;
 
-		if (!IPV4_ADDR_SAME(&voi->address->u.prefix4,
-				    &vl_data->nexthop.oi->address->u.prefix4))
-			changed = 1;
+		/*
+		 * Only deal with interface data when the local
+		 * (calculating) node is the SPF root node
+		 */
+		if (!area->spf_dry_run) {
+			oi = ospf_if_lookup_by_lsa_pos(
+				area, vl_data->nexthop.lsa_pos);
 
-		voi->address->u.prefix4 =
-			vl_data->nexthop.oi->address->u.prefix4;
-		voi->address->prefixlen =
-			vl_data->nexthop.oi->address->prefixlen;
+			if (!IPV4_ADDR_SAME(&voi->address->u.prefix4,
+					    &oi->address->u.prefix4))
+				changed = 1;
+
+			voi->address->u.prefix4 = oi->address->u.prefix4;
+			voi->address->prefixlen = oi->address->prefixlen;
+		}
 
 		break; /* We take the first interface. */
 	}
@@ -1114,7 +1123,7 @@ void ospf_vl_up_check(struct ospf_area *area, struct in_addr rid,
 				OSPF_ISM_EVENT_EXECUTE(oi, ISM_InterfaceUp);
 			}
 
-			if (ospf_vl_set_params(vl_data, v)) {
+			if (ospf_vl_set_params(area, vl_data, v)) {
 				if (IS_DEBUG_OSPF(ism, ISM_EVENTS))
 					zlog_debug(
 						"ospf_vl_up_check: VL cost change, scheduling router lsa refresh");
diff --git a/ospfd/ospf_route.c b/ospfd/ospf_route.c
index 776f50b33..3b049555b 100644
--- a/ospfd/ospf_route.c
+++ b/ospfd/ospf_route.c
@@ -375,7 +375,7 @@ void ospf_intra_add_router(struct route_table *rt, struct vertex *v,
 	else
 		route_unlock_node(rn);
 
-	ospf_route_copy_nexthops_from_vertex(or, v);
+	ospf_route_copy_nexthops_from_vertex(area, or, v);
 
 	listnode_add(rn->info, or);
 
@@ -438,7 +438,7 @@ void ospf_intra_add_transit(struct route_table *rt, struct vertex *v,
 	or->type = OSPF_DESTINATION_NETWORK;
 	or->u.std.origin = (struct lsa_header *)lsa;
 
-	ospf_route_copy_nexthops_from_vertex(or, v);
+	ospf_route_copy_nexthops_from_vertex(area, or, v);
 
 	rn->info = or ;
 }
@@ -453,7 +453,7 @@ void ospf_intra_add_stub(struct route_table *rt, struct router_lsa_link *link,
 	struct ospf_route * or ;
 	struct prefix_ipv4 p;
 	struct router_lsa *lsa;
-	struct ospf_interface *oi;
+	struct ospf_interface *oi = NULL;
 	struct ospf_path *path;
 
 	if (IS_DEBUG_OSPF_EVENT)
@@ -538,7 +538,7 @@ void ospf_intra_add_stub(struct route_table *rt, struct router_lsa_link *link,
 				zlog_debug(
 					"ospf_intra_add_stub(): routes are equal, merge");
 
-			ospf_route_copy_nexthops_from_vertex(cur_or, v);
+			ospf_route_copy_nexthops_from_vertex(area, cur_or, v);
 
 			if (IPV4_ADDR_CMP(&cur_or->u.std.origin->id,
 					  &lsa->header.id)
@@ -563,7 +563,7 @@ void ospf_intra_add_stub(struct route_table *rt, struct router_lsa_link *link,
 
 			list_delete_all_node(cur_or->paths);
 
-			ospf_route_copy_nexthops_from_vertex(cur_or, v);
+			ospf_route_copy_nexthops_from_vertex(area, cur_or, v);
 
 			cur_or->u.std.origin = (struct lsa_header *)lsa;
 			return;
@@ -588,24 +588,35 @@ void ospf_intra_add_stub(struct route_table *rt, struct router_lsa_link *link,
 		if (IS_DEBUG_OSPF_EVENT)
 			zlog_debug(
 				"ospf_intra_add_stub(): this network is on remote router");
-		ospf_route_copy_nexthops_from_vertex(or, v);
+		ospf_route_copy_nexthops_from_vertex(area, or, v);
 	} else {
 		if (IS_DEBUG_OSPF_EVENT)
 			zlog_debug(
 				"ospf_intra_add_stub(): this network is on this router");
 
-		if ((oi = ospf_if_lookup_by_lsa_pos(area, lsa_pos))) {
+		/*
+		 * Only deal with interface data when we
+		 * don't do a dry run
+		 */
+		if (!area->spf_dry_run)
+			oi = ospf_if_lookup_by_lsa_pos(area, lsa_pos);
+
+		if (oi || area->spf_dry_run) {
 			if (IS_DEBUG_OSPF_EVENT)
 				zlog_debug(
-					"ospf_intra_add_stub(): the interface is %s",
-					IF_NAME(oi));
+					"ospf_intra_add_stub(): the lsa pos is %d",
+					lsa_pos);
 
 			path = ospf_path_new();
 			path->nexthop.s_addr = INADDR_ANY;
-			path->ifindex = oi->ifp->ifindex;
-			if (CHECK_FLAG(oi->connected->flags,
-				       ZEBRA_IFA_UNNUMBERED))
-				path->unnumbered = 1;
+
+			if (oi) {
+				path->ifindex = oi->ifp->ifindex;
+				if (CHECK_FLAG(oi->connected->flags,
+					       ZEBRA_IFA_UNNUMBERED))
+					path->unnumbered = 1;
+			}
+
 			listnode_add(or->paths, path);
 		} else {
 			if (IS_DEBUG_OSPF_EVENT)
@@ -654,6 +665,37 @@ void ospf_route_table_dump(struct route_table *rt)
 	zlog_debug("========================================");
 }
 
+void ospf_route_table_print(struct vty *vty, struct route_table *rt)
+{
+	struct route_node *rn;
+	struct ospf_route * or ;
+	struct listnode *pnode;
+	struct ospf_path *path;
+
+	vty_out(vty, "========== OSPF routing table ==========\n");
+	for (rn = route_top(rt); rn; rn = route_next(rn))
+		if ((or = rn->info) != NULL) {
+			if (or->type == OSPF_DESTINATION_NETWORK) {
+				vty_out(vty, "N %-18pFX %-15pI4 %s %d\n",
+					&rn->p, & or->u.std.area_id,
+					ospf_path_type_str[or->path_type],
+					or->cost);
+				for (ALL_LIST_ELEMENTS_RO(or->paths, pnode,
+							  path))
+					vty_out(vty, "  -> %s\n",
+						path->nexthop.s_addr != 0
+							? inet_ntoa(
+								path->nexthop)
+							: "directly connected");
+			} else
+				vty_out(vty, "R %-18pI4 %-15pI4 %s %d\n",
+					&rn->p.u.prefix4, & or->u.std.area_id,
+					ospf_path_type_str[or->path_type],
+					or->cost);
+		}
+	vty_out(vty, "========================================\n");
+}
+
 /* This is 16.4.1 implementation.
    o Intra-area paths using non-backbone areas are always the most preferred.
    o The other paths, intra-area backbone paths and inter-area paths,
@@ -734,30 +776,41 @@ static int ospf_path_exist(struct list *plist, struct in_addr nexthop,
 	return 0;
 }
 
-void ospf_route_copy_nexthops_from_vertex(struct ospf_route *to,
+void ospf_route_copy_nexthops_from_vertex(struct ospf_area *area,
+					  struct ospf_route *to,
 					  struct vertex *v)
 {
 	struct listnode *node;
 	struct ospf_path *path;
 	struct vertex_nexthop *nexthop;
 	struct vertex_parent *vp;
+	struct ospf_interface *oi = NULL;
 
 	assert(to->paths);
 
 	for (ALL_LIST_ELEMENTS_RO(v->parents, node, vp)) {
 		nexthop = vp->nexthop;
 
-		if (nexthop->oi != NULL) {
-			if (!ospf_path_exist(to->paths, nexthop->router,
-					     nexthop->oi)) {
-				path = ospf_path_new();
-				path->nexthop = nexthop->router;
-				path->ifindex = nexthop->oi->ifp->ifindex;
-				if (CHECK_FLAG(nexthop->oi->connected->flags,
+		/*
+		 * Only deal with interface data when we
+		 * don't do a dry run
+		 */
+		if (!area->spf_dry_run)
+			oi = ospf_if_lookup_by_lsa_pos(area, nexthop->lsa_pos);
+
+		if ((oi && !ospf_path_exist(to->paths, nexthop->router, oi))
+		    || area->spf_dry_run) {
+			path = ospf_path_new();
+			path->nexthop = nexthop->router;
+
+			if (oi) {
+				path->ifindex = oi->ifp->ifindex;
+				if (CHECK_FLAG(oi->connected->flags,
 					       ZEBRA_IFA_UNNUMBERED))
 					path->unnumbered = 1;
-				listnode_add(to->paths, path);
 			}
+
+			listnode_add(to->paths, path);
 		}
 	}
 }
diff --git a/ospfd/ospf_route.h b/ospfd/ospf_route.h
index 20cdc75fe..c3fa5954d 100644
--- a/ospfd/ospf_route.h
+++ b/ospfd/ospf_route.h
@@ -132,6 +132,7 @@ extern void ospf_route_table_free(struct route_table *);
 
 extern void ospf_route_install(struct ospf *, struct route_table *);
 extern void ospf_route_table_dump(struct route_table *);
+extern void ospf_route_table_print(struct vty *vty, struct route_table *rt);
 
 extern void ospf_intra_add_router(struct route_table *, struct vertex *,
 				  struct ospf_area *);
@@ -146,7 +147,8 @@ extern void ospf_intra_add_stub(struct route_table *, struct router_lsa_link *,
 extern int ospf_route_cmp(struct ospf *, struct ospf_route *,
 			  struct ospf_route *);
 extern void ospf_route_copy_nexthops(struct ospf_route *, struct list *);
-extern void ospf_route_copy_nexthops_from_vertex(struct ospf_route *,
+extern void ospf_route_copy_nexthops_from_vertex(struct ospf_area *area,
+						 struct ospf_route *,
 						 struct vertex *);
 
 extern void ospf_route_subst(struct route_node *, struct ospf_route *,
diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c
index 91fc20475..6d09d91c5 100644
--- a/ospfd/ospf_spf.c
+++ b/ospfd/ospf_spf.c
@@ -68,14 +68,17 @@ static void ospf_spf_set_reason(ospf_spf_reason_t reason)
 }
 
 static void ospf_vertex_free(void *);
-/* List of allocated vertices, to simplify cleanup of SPF.
+/*
+ * List of allocated vertices, to simplify cleanup of SPF.
  * Not thread-safe obviously. If it ever needs to be, it'd have to be
  * dynamically allocated at begin of ospf_spf_calculate
  */
 static struct list vertex_list = {.del = ospf_vertex_free};
 
-/* Heap related functions, for the managment of the candidates, to
- * be used with pqueue. */
+/*
+ * Heap related functions, for the managment of the candidates, to
+ * be used with pqueue.
+ */
 static int vertex_cmp(const struct vertex *v1, const struct vertex *v2)
 {
 	if (v1->distance != v2->distance)
@@ -118,7 +121,8 @@ static void vertex_nexthop_free(struct vertex_nexthop *nh)
 	XFREE(MTYPE_OSPF_NEXTHOP, nh);
 }
 
-/* Free the canonical nexthop objects for an area, ie the nexthop objects
+/*
+ * Free the canonical nexthop objects for an area, ie the nexthop objects
  * attached to the first-hop router vertices, and any intervening network
  * vertices.
  */
@@ -131,7 +135,8 @@ static void ospf_canonical_nexthops_free(struct vertex *root)
 		struct listnode *n2, *nn2;
 		struct vertex_parent *vp;
 
-		/* router vertices through an attached network each
+		/*
+		 * router vertices through an attached network each
 		 * have a distinct (canonical / not inherited) nexthop
 		 * which must be freed.
 		 *
@@ -150,7 +155,8 @@ static void ospf_canonical_nexthops_free(struct vertex *root)
 	}
 }
 
-/* TODO: Parent list should be excised, in favour of maintaining only
+/*
+ * TODO: Parent list should be excised, in favour of maintaining only
  * vertex_nexthop, with refcounts.
  */
 static struct vertex_parent *vertex_parent_new(struct vertex *v, int backlink,
@@ -163,6 +169,7 @@ static struct vertex_parent *vertex_parent_new(struct vertex *v, int backlink,
 	new->parent = v;
 	new->backlink = backlink;
 	new->nexthop = hop;
+
 	return new;
 }
 
@@ -202,6 +209,7 @@ static struct vertex *ospf_vertex_new(struct ospf_lsa *lsa)
 			   new->type == OSPF_VERTEX_ROUTER ? "Router"
 							   : "Network",
 			   inet_ntoa(new->lsa->id));
+
 	return new;
 }
 
@@ -214,14 +222,6 @@ static void ospf_vertex_free(void *data)
 			   v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network",
 			   inet_ntoa(v->lsa->id));
 
-	/* There should be no parents potentially holding references to this
-	 * vertex
-	 * Children however may still be there, but presumably referenced by
-	 * other
-	 * vertices
-	 */
-	// assert (listcount (v->parents) == 0);
-
 	if (v->children)
 		list_delete(&v->children);
 
@@ -252,14 +252,12 @@ static void ospf_vertex_dump(const char *msg, struct vertex *v,
 
 			if (vp) {
 				zlog_debug(
-					"parent %s backlink %d nexthop %s  interface %s",
+					"parent %s backlink %d nexthop %s  lsa pos %d",
 					inet_ntoa(vp->parent->lsa->id),
 					vp->backlink,
 					inet_ntop(AF_INET, &vp->nexthop->router,
 						  buf1, BUFSIZ),
-					vp->nexthop->oi
-						? IF_NAME(vp->nexthop->oi)
-						: "NULL");
+					vp->nexthop->lsa_pos);
 			}
 		}
 	}
@@ -291,14 +289,17 @@ static void ospf_vertex_add_parent(struct vertex *v)
 	}
 }
 
-static void ospf_spf_init(struct ospf_area *area)
+static void ospf_spf_init(struct ospf_area *area, struct ospf_lsa *root_lsa,
+			  bool is_dry_run, bool is_root_node)
 {
 	struct vertex *v;
 
 	/* Create root node. */
-	v = ospf_vertex_new(area->router_lsa_self);
+	v = ospf_vertex_new(root_lsa);
 
 	area->spf = v;
+	area->spf_dry_run = is_dry_run;
+	area->spf_root_node = is_root_node;
 
 	/* Reset ABR and ASBR router counts. */
 	area->abr_count = 0;
@@ -364,7 +365,8 @@ static int ospf_lsa_has_link(struct lsa_header *w, struct lsa_header *v)
 	return -1;
 }
 
-/* Find the next link after prev_link from v to w.  If prev_link is
+/*
+ * Find the next link after prev_link from v to w.  If prev_link is
  * NULL, return the first link from v to w.  Ignore stub and virtual links;
  * these link types will never be returned.
  */
@@ -433,10 +435,11 @@ static void ospf_spf_add_parent(struct vertex *v, struct vertex *w,
 	assert(v && w && newhop);
 	assert(distance);
 
-	/* IFF w has already been assigned a distance, then we shouldn't get
-	 * here
-	 * unless callers have determined V(l)->W is shortest / equal-shortest
-	 * path (0 is a special case distance (no distance yet assigned)).
+	/*
+	 * IFF w has already been assigned a distance, then we shouldn't get
+	 * here unless callers have determined V(l)->W is shortest /
+	 * equal-shortest path (0 is a special case distance (no distance yet
+	 * assigned)).
 	 */
 	if (w->distance)
 		assert(distance <= w->distance);
@@ -452,7 +455,8 @@ static void ospf_spf_add_parent(struct vertex *v, struct vertex *w,
 				  sizeof(buf[1])));
 	}
 
-	/* Adding parent for a new, better path: flush existing parents from W.
+	/*
+	 * Adding parent for a new, better path: flush existing parents from W.
 	 */
 	if (distance < w->distance) {
 		if (IS_DEBUG_OSPF_EVENT)
@@ -463,7 +467,8 @@ static void ospf_spf_add_parent(struct vertex *v, struct vertex *w,
 		w->distance = distance;
 	}
 
-	/* new parent is <= existing parents, add it to parent list (if nexthop
+	/*
+	 * new parent is <= existing parents, add it to parent list (if nexthop
 	 * not on parent list)
 	 */
 	for (ALL_LIST_ELEMENTS_RO(w->parents, node, wp)) {
@@ -482,7 +487,43 @@ static void ospf_spf_add_parent(struct vertex *v, struct vertex *w,
 	return;
 }
 
-/* 16.1.1.  Calculate nexthop from root through V (parent) to
+static int match_stub_prefix(struct lsa_header *lsa, struct in_addr v_link_addr,
+			     struct in_addr w_link_addr)
+{
+	uint8_t *p, *lim;
+	struct router_lsa_link *l = NULL;
+	struct in_addr masked_lsa_addr;
+
+	if (lsa->type != OSPF_ROUTER_LSA)
+		return 0;
+
+	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));
+
+		if (l->m[0].type != LSA_LINK_TYPE_STUB)
+			continue;
+
+		masked_lsa_addr.s_addr =
+			(l->link_id.s_addr & l->link_data.s_addr);
+
+		/* check that both links belong to the same stub subnet */
+		if ((masked_lsa_addr.s_addr
+		     == (v_link_addr.s_addr & l->link_data.s_addr))
+		    && (masked_lsa_addr.s_addr
+			== (w_link_addr.s_addr & l->link_data.s_addr)))
+			return 1;
+	}
+
+	return 0;
+}
+
+/*
+ * 16.1.1.  Calculate nexthop from root through V (parent) to
  * vertex W (destination), with given distance from root->W.
  *
  * The link must be supplied if V is the root vertex. In all other cases
@@ -501,7 +542,6 @@ static unsigned int ospf_nexthop_calculation(struct ospf_area *area,
 	struct listnode *node, *nnode;
 	struct vertex_nexthop *nh;
 	struct vertex_parent *vp;
-	struct ospf_interface *oi = NULL;
 	unsigned int added = 0;
 	char buf1[BUFSIZ];
 	char buf2[BUFSIZ];
@@ -514,154 +554,140 @@ static unsigned int ospf_nexthop_calculation(struct ospf_area *area,
 	}
 
 	if (v == area->spf) {
-		/* 16.1.1 para 4.  In the first case, the parent vertex (V) is
-		   the
-		   root (the calculating router itself).  This means that the
-		   destination is either a directly connected network or
-		   directly
-		   connected router.  The outgoing interface in this case is
-		   simply
-		   the OSPF interface connecting to the destination
-		   network/router.
-		*/
+		/*
+		 * 16.1.1 para 4.  In the first case, the parent vertex (V) is
+		 * the root (the calculating router itself).  This means that
+		 * the destination is either a directly connected network or
+		 * directly connected router.  The outgoing interface in this
+		 * case is simply the OSPF interface connecting to the
+		 * destination network/router.
+		 */
 
 		/* we *must* be supplied with the link data */
 		assert(l != NULL);
-		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 (IS_DEBUG_OSPF_EVENT) {
 			zlog_debug(
-				"%s: considering link:%s type:%d link_id:%s link_data:%s",
-				__func__, oi->ifp->name, l->m[0].type,
+				"%s: considering link type:%d link_id:%s link_data:%s",
+				__func__, l->m[0].type,
 				inet_ntop(AF_INET, &l->link_id, buf1, BUFSIZ),
 				inet_ntop(AF_INET, &l->link_data, buf2,
 					  BUFSIZ));
 		}
 
 		if (w->type == OSPF_VERTEX_ROUTER) {
-			/* l  is a link from v to w
-			 * l2 will be link from w to v
+			/*
+			 * l is a link from v to w l2 will be link from w to v
 			 */
 			struct router_lsa_link *l2 = NULL;
 
 			if (l->m[0].type == LSA_LINK_TYPE_POINTOPOINT) {
-				struct in_addr nexthop = {.s_addr = 0};
 
-				/* If the destination is a router which connects
-				   to
-				   the calculating router via a
-				   Point-to-MultiPoint
-				   network, the destination's next hop IP
-				   address(es)
-				   can be determined by examining the
-				   destination's
-				   router-LSA: each link pointing back to the
-				   calculating router and having a Link Data
-				   field
-				   belonging to the Point-to-MultiPoint network
-				   provides an IP address of the next hop
-				   router.
-
-				   At this point l is a link from V to W, and V
-				   is the
-				   root ("us"). If it is a point-to-multipoint
-				   interface,
-				   then look through the links in the opposite
-				   direction (W to V).
-				   If any of them have an address that lands
-				   within the
-				   subnet declared by the PtMP link, then that
-				   link
-				   is a constituent of the PtMP link, and its
-				   address is
-				   a nexthop address for V.
-				*/
-				if (oi->type == OSPF_IFTYPE_POINTOPOINT) {
-					/* Having nexthop = 0 is tempting, but
-					   NOT acceptable.
-					   It breaks AS-External routes with a
-					   forwarding address,
-					   since
-					   ospf_ase_complete_direct_routes()
-					   will mistakenly
-					   assume we've reached the last hop and
-					   should place the
-					   forwarding address as nexthop.
-					   Also, users may configure
-					   multi-access links in p2p mode,
-					   so we need the IP to ARP the nexthop.
-					*/
-					struct ospf_neighbor *nbr_w;
-
-					nbr_w = ospf_nbr_lookup_by_routerid(
-						oi->nbrs, &l->link_id);
-					if (nbr_w != NULL) {
-						added = 1;
-						nexthop = nbr_w->src;
-					}
-				} else if (oi->type
-					   == OSPF_IFTYPE_POINTOMULTIPOINT) {
-					struct prefix_ipv4 la;
+				/*
+				 * If the destination is a router which connects
+				 * to the calculating router via a
+				 * Point-to-MultiPoint network, the
+				 * destination's next hop IP address(es) can be
+				 * determined by examining the destination's
+				 * router-LSA: each link pointing back to the
+				 * calculating router and having a Link Data
+				 * field belonging to the Point-to-MultiPoint
+				 * network provides an IP address of the next
+				 * hop router.
+				 *
+				 * At this point l is a link from V to W, and V
+				 * is the root ("us"). If it is a point-to-
+				 * multipoint interface, then look through the
+				 * links in the opposite direction (W to V).
+				 * If any of them have an address that lands
+				 * within the subnet declared by the PtMP link,
+				 * then that link is a constituent of the PtMP
+				 * link, and its address is a nexthop address
+				 * for V.
+				 *
+				 * Note for point-to-point interfaces:
+				 *
+				 * Having nexthop = 0 (as proposed in the RFC)
+				 * is tempting, but NOT acceptable. It breaks
+				 * AS-External routes with a forwarding address,
+				 * since ospf_ase_complete_direct_routes() will
+				 * mistakenly assume we've reached the last hop
+				 * and should place the forwarding address as
+				 * nexthop. Also, users may configure multi-
+				 * access links in p2p mode, so we need the IP
+				 * to ARP the nexthop.
+				 *
+				 * If the calculating router is the SPF root
+				 * node and the link is P2P then access the
+				 * interface information directly. This can be
+				 * crucial when e.g. IP unnumbered is used
+				 * where 'correct' nexthop information are not
+				 * available via Router LSAs.
+				 *
+				 * Otherwise handle P2P and P2MP the same way
+				 * as described above using a reverse lookup to
+				 * figure out the nexthop.
+				 */
 
-					la.family = AF_INET;
-					la.prefixlen = oi->address->prefixlen;
+				struct in_addr nexthop = {.s_addr = 0};
+				struct ospf_interface *oi = NULL;
+				struct ospf_neighbor *nbr_w = NULL;
+
+				/* Calculating node is root node, link is P2P */
+				if (area->spf_root_node) {
+					oi = ospf_if_lookup_by_lsa_pos(area,
+								       lsa_pos);
+					if (oi->type
+					    == OSPF_IFTYPE_POINTOPOINT) {
+						nbr_w = ospf_nbr_lookup_by_routerid(
+							oi->nbrs, &l->link_id);
+						if (nbr_w) {
+							added = 1;
+							nexthop = nbr_w->src;
+						}
+					}
+				}
 
-					/* V links to W on PtMP interface
-					   - find the interface address on W */
+				/* Reverse lookup */
+				if (!added) {
 					while ((l2 = ospf_get_next_link(w, v,
 									l2))) {
-						la.prefix = l2->link_data;
-
-						if (prefix_cmp((struct prefix
-									*)&la,
-							       oi->address)
-						    != 0)
-							continue;
-						/* link_data is on our PtMP
-						 * network */
-						added = 1;
-						nexthop = l2->link_data;
-						break;
+						if (match_stub_prefix(
+							    v->lsa,
+							    l->link_data,
+							    l2->link_data)) {
+							added = 1;
+							nexthop = l2->link_data;
+							break;
+						}
 					}
 				}
 
 				if (added) {
-					/* found all necessary info to build
-					 * nexthop */
 					nh = vertex_nexthop_new();
-					nh->oi = oi;
 					nh->router = nexthop;
+					nh->lsa_pos = lsa_pos;
 					ospf_spf_add_parent(v, w, nh, distance);
 					return 1;
 				} else
 					zlog_info(
-						"%s: could not determine nexthop for link %s",
-						__func__, oi->ifp->name);
+						"%s: could not determine nexthop for link",
+						__func__);
 			} /* end point-to-point link from V to W */
 			else if (l->m[0].type == LSA_LINK_TYPE_VIRTUALLINK) {
-				struct ospf_vl_data *vl_data;
-
-				/* VLink implementation limitations:
-				 * a) vl_data can only reference one nexthop, so
-				 * no ECMP
-				 *    to backbone through VLinks. Though
-				 * transit-area
-				 *    summaries may be considered, and those can
-				 * be ECMP.
+				/*
+				 * VLink implementation limitations:
+				 * a) vl_data can only reference one nexthop,
+				 *    so no ECMP to backbone through VLinks.
+				 *    Though transit-area summaries may be
+				 *    considered, and those can be ECMP.
 				 * b) We can only use /one/ VLink, even if
-				 * multiple ones
-				 *    exist this router through multiple
-				 * transit-areas.
+				 *    multiple ones exist this router through
+				 *    multiple transit-areas.
 				 */
+
+				struct ospf_vl_data *vl_data;
+
 				vl_data = ospf_vl_lookup(area->ospf, NULL,
 							 l->link_id);
 
@@ -669,8 +695,8 @@ static unsigned int ospf_nexthop_calculation(struct ospf_area *area,
 				    && CHECK_FLAG(vl_data->flags,
 						  OSPF_VL_FLAG_APPROVED)) {
 					nh = vertex_nexthop_new();
-					nh->oi = vl_data->nexthop.oi;
 					nh->router = vl_data->nexthop.router;
+					nh->lsa_pos = vl_data->nexthop.lsa_pos;
 					ospf_spf_add_parent(v, w, nh, distance);
 					return 1;
 				} else
@@ -683,8 +709,8 @@ static unsigned int ospf_nexthop_calculation(struct ospf_area *area,
 			assert(w->type == OSPF_VERTEX_NETWORK);
 
 			nh = vertex_nexthop_new();
-			nh->oi = oi;
 			nh->router.s_addr = 0; /* Nexthop not required */
+			nh->lsa_pos = lsa_pos;
 			ospf_spf_add_parent(v, w, nh, distance);
 			return 1;
 		}
@@ -693,82 +719,70 @@ static unsigned int ospf_nexthop_calculation(struct ospf_area *area,
 	else if (v->type == OSPF_VERTEX_NETWORK) {
 		/* See if any of V's parents are the root. */
 		for (ALL_LIST_ELEMENTS(v->parents, node, nnode, vp)) {
-			if (vp->parent == area->spf) /* connects to root? */
-			{
-				/* 16.1.1 para 5. ...the parent vertex is a
-				 * network that
-				 * directly connects the calculating router to
-				 * the destination
-				 * router.  The list of next hops is then
-				 * determined by
-				 * examining the destination's router-LSA...
+			if (vp->parent == area->spf) {
+				/*
+				 * 16.1.1 para 5. ...the parent vertex is a
+				 * network that directly connects the
+				 * calculating router to the destination
+				 * router. The list of next hops is then
+				 * determined by examining the destination's
+				 * router-LSA ...
 				 */
 
 				assert(w->type == OSPF_VERTEX_ROUTER);
 				while ((l = ospf_get_next_link(w, v, l))) {
-					/* ...For each link in the router-LSA
-					 * that points back to the
-					 * parent network, the link's Link Data
-					 * field provides the IP
-					 * address of a next hop router.  The
-					 * outgoing interface to
-					 * use can then be derived from the next
-					 * hop IP address (or
-					 * it can be inherited from the parent
-					 * network).
+					/*
+					 * ... For each link in the router-LSA
+					 * that points back to the parent
+					 * network, the link's Link Data field
+					 * provides the IP address of a next hop
+					 * router. The outgoing interface to use
+					 * can then be derived from the next
+					 * hop IP address (or it can be
+					 * inherited from the parent network).
 					 */
 					nh = vertex_nexthop_new();
-					nh->oi = vp->nexthop->oi;
 					nh->router = l->link_data;
+					nh->lsa_pos = vp->nexthop->lsa_pos;
 					added = 1;
 					ospf_spf_add_parent(v, w, nh, distance);
 				}
-				/* Note lack of return is deliberate. See next
-				 * comment. */
+				/*
+				 * Note lack of return is deliberate. See next
+				 * comment.
+				 */
 			}
 		}
-		/* NB: This code is non-trivial.
+		/*
+		 * NB: This code is non-trivial.
 		 *
 		 * E.g. it is not enough to know that V connects to the root. It
-		 * is
-		 * also important that the while above, looping through all
-		 * links from
-		 * W->V found at least one link, so that we know there is
-		 * bi-directional connectivity between V and W (which need not
-		 * be the
-		 * case, e.g.  when OSPF has not yet converged fully).
-		 * Otherwise, if
-		 * we /always/ return here, without having checked that
-		 * root->V->-W
-		 * actually resulted in a valid nexthop being created, then we
-		 * we will
-		 * prevent SPF from finding/using higher cost paths.
+		 * is also important that the while above, looping through all
+		 * links from W->V found at least one link, so that we know
+		 * there is bi-directional connectivity between V and W (which
+		 * need not be the case, e.g.  when OSPF has not yet converged
+		 * fully). Otherwise, if we /always/ return here, without having
+		 * checked that root->V->-W actually resulted in a valid nexthop
+		 * being created, then we we will prevent SPF from finding/using
+		 * higher cost paths.
 		 *
 		 * It is important, if root->V->W has not been added, that we
-		 * continue
-		 * through to the intervening-router nexthop code below.  So as
-		 * to
-		 * ensure other paths to V may be used.  This avoids unnecessary
-		 * blackholes while OSPF is convergening.
+		 * continue through to the intervening-router nexthop code
+		 * below. So as to ensure other paths to V may be used. This
+		 * avoids unnecessary blackholes while OSPF is converging.
 		 *
 		 * I.e. we may have arrived at this function, examining V -> W,
-		 * via
-		 * workable paths other than root -> V, and it's important to
-		 * avoid
-		 * getting "confused" by non-working root->V->W path - it's
-		 * important
-		 * to *not* lose the working non-root paths, just because of a
-		 * non-viable root->V->W.
-		 *
-		 * See also bug #330 (required reading!), and:
-		 *
-		 * http://blogs.oracle.com/paulj/entry/the_difference_a_line_makes
+		 * via workable paths other than root -> V, and it's important
+		 * to avoid getting "confused" by non-working root->V->W path
+		 * - it's important to *not* lose the working non-root paths,
+		 * just because of a non-viable root->V->W.
 		 */
 		if (added)
 			return added;
 	}
 
-	/* 16.1.1 para 4.  If there is at least one intervening router in the
+	/*
+	 * 16.1.1 para 4.  If there is at least one intervening router in the
 	 * current shortest path between the destination and the root, the
 	 * destination simply inherits the set of next hops from the
 	 * parent.
@@ -785,13 +799,13 @@ static unsigned int ospf_nexthop_calculation(struct ospf_area *area,
 	return added;
 }
 
-/* RFC2328 Section 16.1 (2).
- * v is on the SPF tree.  Examine the links in v's LSA.  Update the list
- * of candidates with any vertices not already on the list.  If a lower-cost
- * path is found to a vertex already on the candidate list, store the new cost.
+/*
+ * RFC2328 16.1 (2).
+ * v is on the SPF tree. Examine the links in v's LSA. Update the list of
+ * candidates with any vertices not already on the list. If a lower-cost path
+ * is found to a vertex already on the candidate list, store the new cost.
  */
-static void ospf_spf_next(struct vertex *v, struct ospf *ospf,
-			  struct ospf_area *area,
+static void ospf_spf_next(struct vertex *v, struct ospf_area *area,
 			  struct vertex_pqueue_head *candidate)
 {
 	struct ospf_lsa *w_lsa = NULL;
@@ -801,8 +815,10 @@ static void ospf_spf_next(struct vertex *v, struct ospf *ospf,
 	struct in_addr *r;
 	int type = 0, lsa_pos = -1, lsa_pos_next = 0;
 
-	/* If this is a router-LSA, and bit V of the router-LSA (see Section
-	   A.4.2:RFC2328) is set, set Area A's TransitCapability to true.  */
+	/*
+	 * If this is a router-LSA, and bit V of the router-LSA (see Section
+	 * A.4.2:RFC2328) is set, set Area A's TransitCapability to true.
+	 */
 	if (v->type == OSPF_VERTEX_ROUTER) {
 		if (IS_ROUTER_LSA_VIRTUAL((struct router_lsa *)v->lsa))
 			area->transit = OSPF_TRANSIT_TRUE;
@@ -826,40 +842,39 @@ static void ospf_spf_next(struct vertex *v, struct ospf *ospf,
 
 			lsa_pos = lsa_pos_next; /* LSA link position */
 			lsa_pos_next++;
+
 			p += (OSPF_ROUTER_LSA_LINK_SIZE
 			      + (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
 
-			/* (a) If this is a link to a stub network, examine the
-			   next
-			   link in V's LSA.  Links to stub networks will be
-			   considered in the second stage of the shortest path
-			   calculation. */
+			/*
+			 * (a) If this is a link to a stub network, examine the
+			 * next link in V's LSA. Links to stub networks will
+			 * be considered in the second stage of the shortest
+			 * path calculation.
+			 */
 			if ((type = l->m[0].type) == LSA_LINK_TYPE_STUB)
 				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 database. */
+			/*
+			 * (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
+			 * database.
+			 */
 			switch (type) {
 			case LSA_LINK_TYPE_POINTOPOINT:
 			case LSA_LINK_TYPE_VIRTUALLINK:
-				if (type == LSA_LINK_TYPE_VIRTUALLINK) {
-					if (IS_DEBUG_OSPF_EVENT)
-						zlog_debug(
-							"looking up LSA through VL: %s",
-							inet_ntoa(l->link_id));
-				}
-
-				w_lsa = ospf_lsa_lookup(ospf, area,
+				if (type == LSA_LINK_TYPE_VIRTUALLINK
+				    && IS_DEBUG_OSPF_EVENT)
+					zlog_debug(
+						"looking up LSA through VL: %s",
+						inet_ntoa(l->link_id));
+				w_lsa = ospf_lsa_lookup(area->ospf, area,
 							OSPF_ROUTER_LSA,
 							l->link_id, l->link_id);
-				if (w_lsa) {
-					if (IS_DEBUG_OSPF_EVENT)
-						zlog_debug(
-							"found Router LSA %s",
-							inet_ntoa(l->link_id));
-				}
+				if (w_lsa && IS_DEBUG_OSPF_EVENT)
+					zlog_debug("found Router LSA %s",
+						   inet_ntoa(l->link_id));
 				break;
 			case LSA_LINK_TYPE_TRANSIT:
 				if (IS_DEBUG_OSPF_EVENT)
@@ -868,9 +883,8 @@ static void ospf_spf_next(struct vertex *v, struct ospf *ospf,
 						inet_ntoa(l->link_id));
 				w_lsa = ospf_lsa_lookup_by_id(
 					area, OSPF_NETWORK_LSA, l->link_id);
-				if (w_lsa)
-					if (IS_DEBUG_OSPF_EVENT)
-						zlog_debug("found the LSA");
+				if (w_lsa && IS_DEBUG_OSPF_EVENT)
+					zlog_debug("found the LSA");
 				break;
 			default:
 				flog_warn(EC_OSPF_LSA,
@@ -888,19 +902,19 @@ static void ospf_spf_next(struct vertex *v, struct ospf *ospf,
 			/* Lookup the vertex W's LSA. */
 			w_lsa = ospf_lsa_lookup_by_id(area, OSPF_ROUTER_LSA,
 						      *r);
-			if (w_lsa) {
-				if (IS_DEBUG_OSPF_EVENT)
-					zlog_debug("found Router LSA %s",
-						   inet_ntoa(w_lsa->data->id));
-			}
+			if (w_lsa && IS_DEBUG_OSPF_EVENT)
+				zlog_debug("found Router LSA %s",
+					   inet_ntoa(w_lsa->data->id));
 
 			/* step (d) below */
 			distance = v->distance;
 		}
 
-		/* (b cont.) If the LSA does not exist, or its LS age is equal
-		   to MaxAge, or it does not have a link back to vertex V,
-		   examine the next link in V's LSA.[23] */
+		/*
+		 * (b cont.) If the LSA does not exist, or its LS age is equal
+		 * to MaxAge, or it does not have a link back to vertex V,
+		 * examine the next link in V's LSA.[23]
+		 */
 		if (w_lsa == NULL) {
 			if (IS_DEBUG_OSPF_EVENT)
 				zlog_debug("No LSA found");
@@ -919,19 +933,23 @@ static void ospf_spf_next(struct vertex *v, struct ospf *ospf,
 			continue;
 		}
 
-		/* (c) If vertex W is already on the shortest-path tree, examine
-		   the next link in the LSA. */
+		/*
+		 * (c) If vertex W is already on the shortest-path tree, examine
+		 * the next link in the LSA.
+		 */
 		if (w_lsa->stat == LSA_SPF_IN_SPFTREE) {
 			if (IS_DEBUG_OSPF_EVENT)
 				zlog_debug("The LSA is already in SPF");
 			continue;
 		}
 
-		/* (d) Calculate the link state cost D of the resulting path
-		   from the root to vertex W.  D is equal to the sum of the link
-		   state cost of the (already calculated) shortest path to
-		   vertex V and the advertised cost of the link between vertices
-		   V and W.  If D is: */
+		/*
+		 * (d) Calculate the link state cost D of the resulting path
+		 * from the root to vertex W.  D is equal to the sum of the link
+		 * state cost of the (already calculated) shortest path to
+		 * vertex V and the advertised cost of the link between vertices
+		 * V and W.  If D is:
+		 */
 
 		/* calculate link cost D -- moved above */
 
@@ -948,29 +966,28 @@ static void ospf_spf_next(struct vertex *v, struct ospf *ospf,
 				zlog_debug("Nexthop Calc failed");
 		} else if (w_lsa->stat != LSA_SPF_IN_SPFTREE) {
 			w = w_lsa->stat;
-			/* if D is greater than. */
 			if (w->distance < distance) {
 				continue;
 			}
-			/* equal to. */
 			else if (w->distance == distance) {
-				/* Found an equal-cost path to W.
-				 * Calculate nexthop of to W from V. */
+				/*
+				 * Found an equal-cost path to W.
+				 * Calculate nexthop of to W from V.
+				 */
 				ospf_nexthop_calculation(area, v, w, l,
 							 distance, lsa_pos);
 			}
-			/* less than. */
 			else {
-				/* Found a lower-cost path to W.
+				/*
+				 * Found a lower-cost path to W.
 				 * nexthop_calculation is conditional, if it
-				 * finds
-				 * valid nexthop it will call spf_add_parents,
-				 * which
-				 * will flush the old parents
+				 * finds valid nexthop it will call
+				 * spf_add_parents, which will flush the old
+				 * parents.
 				 */
 				vertex_pqueue_del(candidate, w);
 				ospf_nexthop_calculation(area, v, w, l,
-							     distance, lsa_pos);
+							 distance, lsa_pos);
 				vertex_pqueue_add(candidate, w);
 			}
 		} /* end W is already on the candidate list */
@@ -997,11 +1014,9 @@ static void ospf_spf_dump(struct vertex *v, int i)
 
 	if (IS_DEBUG_OSPF_EVENT)
 		for (ALL_LIST_ELEMENTS_RO(v->parents, nnode, parent)) {
-			zlog_debug(" nexthop %p %s %s", (void *)parent->nexthop,
+			zlog_debug(" nexthop %p %s %d", (void *)parent->nexthop,
 				   inet_ntoa(parent->nexthop->router),
-				   parent->nexthop->oi
-					   ? IF_NAME(parent->nexthop->oi)
-					   : "NULL");
+				   parent->nexthop->lsa_pos);
 		}
 
 	i++;
@@ -1010,6 +1025,33 @@ static void ospf_spf_dump(struct vertex *v, int i)
 		ospf_spf_dump(v, i);
 }
 
+void ospf_spf_print(struct vty *vty, struct vertex *v, int i)
+{
+	struct listnode *cnode;
+	struct listnode *nnode;
+	struct vertex_parent *parent;
+
+	if (v->type == OSPF_VERTEX_ROUTER) {
+		vty_out(vty, "SPF Result: depth %d [R] %s\n", i,
+			inet_ntoa(v->lsa->id));
+	} else {
+		struct network_lsa *lsa = (struct network_lsa *)v->lsa;
+		vty_out(vty, "SPF Result: depth %d [N] %s/%d\n", i,
+			inet_ntoa(v->lsa->id), ip_masklen(lsa->mask));
+	}
+
+	for (ALL_LIST_ELEMENTS_RO(v->parents, nnode, parent)) {
+		vty_out(vty, " nexthop %s lsa pos %d\n",
+			inet_ntoa(parent->nexthop->router),
+			parent->nexthop->lsa_pos);
+	}
+
+	i++;
+
+	for (ALL_LIST_ELEMENTS_RO(v->children, cnode, v))
+		ospf_spf_print(vty, v, i);
+}
+
 /* Second stage of SPF calculation. */
 static void ospf_spf_process_stubs(struct ospf_area *area, struct vertex *v,
 				   struct route_table *rt, int parent_is_root)
@@ -1020,24 +1062,26 @@ static void ospf_spf_process_stubs(struct ospf_area *area, struct vertex *v,
 	if (IS_DEBUG_OSPF_EVENT)
 		zlog_debug("ospf_process_stub():processing stubs for area %s",
 			   inet_ntoa(area->area_id));
+
 	if (v->type == OSPF_VERTEX_ROUTER) {
 		uint8_t *p;
 		uint8_t *lim;
 		struct router_lsa_link *l;
-		struct router_lsa *rlsa;
+		struct router_lsa *router_lsa;
 		int lsa_pos = 0;
 
 		if (IS_DEBUG_OSPF_EVENT)
 			zlog_debug(
 				"ospf_process_stubs():processing router LSA, id: %s",
 				inet_ntoa(v->lsa->id));
-		rlsa = (struct router_lsa *)v->lsa;
 
+		router_lsa = (struct router_lsa *)v->lsa;
 
 		if (IS_DEBUG_OSPF_EVENT)
 			zlog_debug(
 				"ospf_process_stubs(): we have %d links to process",
-				ntohs(rlsa->links));
+				ntohs(router_lsa->links));
+
 		p = ((uint8_t *)v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
 		lim = ((uint8_t *)v->lsa) + ntohs(v->lsa->length);
 
@@ -1061,7 +1105,8 @@ static void ospf_spf_process_stubs(struct ospf_area *area, struct vertex *v,
 		if (CHECK_FLAG(child->flags, OSPF_VERTEX_PROCESSED))
 			continue;
 
-		/* the first level of routers connected to the root
+		/*
+		 * The first level of routers connected to the root
 		 * should have 'parent_is_root' set, including those
 		 * connected via a network vertex.
 		 */
@@ -1097,6 +1142,7 @@ void ospf_rtrs_free(struct route_table *rtrs)
 			rn->info = NULL;
 			route_unlock_node(rn);
 		}
+
 	route_table_finish(rtrs);
 }
 
@@ -1162,10 +1208,11 @@ ospf_rtrs_print (struct route_table *rtrs)
 }
 #endif
 
-/* Calculating the shortest-path tree for an area. */
-static void ospf_spf_calculate(struct ospf *ospf, struct ospf_area *area,
-			       struct route_table *new_table,
-			       struct route_table *new_rtrs)
+/* 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,
+			struct route_table *new_table,
+			struct route_table *new_rtrs, bool is_dry_run,
+			bool is_root_node)
 {
 	struct vertex_pqueue_head candidate;
 	struct vertex *v;
@@ -1176,55 +1223,57 @@ static void ospf_spf_calculate(struct ospf *ospf, struct ospf_area *area,
 			   inet_ntoa(area->area_id));
 	}
 
-	/* Check router-lsa-self.  If self-router-lsa is not yet allocated,
-	   return this area's calculation. */
-	if (!area->router_lsa_self) {
+	/*
+	 * If the router LSA of the root is not yet allocated, return this
+	 * area's calculation. In the 'usual' case the root_lsa is the
+	 * self-originated router LSA of the node itself.
+	 */
+	if (!root_lsa) {
 		if (IS_DEBUG_OSPF_EVENT)
 			zlog_debug(
-				"ospf_spf_calculate: Skip area %s's calculation due to empty router_lsa_self",
+				"ospf_spf_calculate: Skip area %s's calculation due to empty root LSA",
 				inet_ntoa(area->area_id));
 		return;
 	}
 
-	/* RFC2328 16.1. (1). */
-	/* Initialize the algorithm's data structures. */
+	/* Initialize the algorithm's data structures, see RFC2328 16.1. (1). */
 
-	/* This function scans all the LSA database and set the stat field to
-	 * LSA_SPF_NOT_EXPLORED. */
+	/*
+	 * This function scans all the LSA database and set the stat field to
+	 * LSA_SPF_NOT_EXPLORED.
+	 */
 	lsdb_clean_stat(area->lsdb);
+
 	/* Create a new heap for the candidates. */
 	vertex_pqueue_init(&candidate);
 
-	/* Initialize the shortest-path tree to only the root (which is the
-	   router doing the calculation). */
-	ospf_spf_init(area);
-	v = area->spf;
-	/* Set LSA position to LSA_SPF_IN_SPFTREE. This vertex is the root of
-	 * the
-	 * spanning tree. */
-	v->lsa_p->stat = LSA_SPF_IN_SPFTREE;
+	/*
+	 * Initialize the shortest-path tree to only the root (which is usually
+	 * the router doing the calculation).
+	 */
+	ospf_spf_init(area, root_lsa, is_dry_run, is_root_node);
 
 	/* Set Area A's TransitCapability to false. */
 	area->transit = OSPF_TRANSIT_FALSE;
 	area->shortcut_capability = 1;
 
+	/*
+	 * Use the root vertex for the start of the SPF algorithm and make it
+	 * part of the tree.
+	 */
+	v = area->spf;
+	v->lsa_p->stat = LSA_SPF_IN_SPFTREE;
+
 	for (;;) {
 		/* RFC2328 16.1. (2). */
-		ospf_spf_next(v, ospf, area, &candidate);
+		ospf_spf_next(v, area, &candidate);
 
 		/* RFC2328 16.1. (3). */
-		/* If at this step the candidate list is empty, the shortest-
-		   path tree (of transit vertices) has been completely built and
-		   this stage of the procedure terminates. */
-		/* Otherwise, choose the vertex belonging to the candidate list
-		   that is closest to the root, and add it to the shortest-path
-		   tree (removing it from the candidate list in the
-		   process). */
-		/* Extract from the candidates the node with the lower key. */
 		v = vertex_pqueue_pop(&candidate);
 		if (!v)
+			/* No more vertices left. */
 			break;
-		/* Update stat field in vertex. */
+
 		v->lsa_p->stat = LSA_SPF_IN_SPFTREE;
 
 		ospf_vertex_add_parent(v);
@@ -1235,28 +1284,21 @@ static void ospf_spf_calculate(struct ospf *ospf, struct ospf_area *area,
 		else
 			ospf_intra_add_transit(new_table, v, area);
 
-		/* RFC2328 16.1. (5). */
-		/* Iterate the algorithm by returning to Step 2. */
-
-	} /* end loop until no more candidate vertices */
+		/* Iterate back to (2), see RFC2328 16.1. (5). */
+	}
 
 	if (IS_DEBUG_OSPF_EVENT) {
 		ospf_spf_dump(area->spf, 0);
 		ospf_route_table_dump(new_table);
 	}
 
-	/* Second stage of SPF calculation procedure's  */
+	/*
+	 * Second stage of SPF calculation procedure's, add leaves to the tree
+	 * for stub networks.
+	 */
 	ospf_spf_process_stubs(area, area->spf, new_table, 0);
 
-	/* Free candidate queue. */
-	//vertex_pqueue_fini(&candidate);
-
 	ospf_vertex_dump(__func__, area->spf, 0, 1);
-	/* Free nexthop information, canonical versions of which are attached
-	 * the first level of router vertices attached to the root vertex, see
-	 * ospf_nexthop_calculation.
-	 */
-	ospf_canonical_nexthops_free(area->spf);
 
 	/* Increment SPF Calculation Counter. */
 	area->spf_calculation++;
@@ -1268,75 +1310,101 @@ static void ospf_spf_calculate(struct ospf *ospf, struct ospf_area *area,
 		zlog_debug("ospf_spf_calculate: Stop. %zd vertices",
 			   mtype_stats_alloc(MTYPE_OSPF_VERTEX));
 
-	/* Free SPF vertices, but not the list. List has ospf_vertex_free
-	 * as deconstructor.
-	 */
-	list_delete_all_node(&vertex_list);
+	/* If this is a dry run then keep the SPF data in place */
+	if (!area->spf_dry_run) {
+		/*
+		 * Free nexthop information, canonical versions of which are
+		 * attached the first level of router vertices attached to the
+		 * root vertex, see ospf_nexthop_calculation.
+		 */
+		ospf_canonical_nexthops_free(area->spf);
+
+		/*
+		 * Free SPF vertices, but not the list. List has
+		 * ospf_vertex_free as deconstructor.
+		 */
+		list_delete_all_node(&vertex_list);
+	}
 }
 
-/* Timer for SPF calculation. */
-static int ospf_spf_calculate_timer(struct thread *thread)
+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)
 {
-	struct ospf *ospf = THREAD_ARG(thread);
-	struct route_table *new_table, *new_rtrs;
 	struct ospf_area *area;
 	struct listnode *node, *nnode;
-	struct timeval start_time, spf_start_time;
 	int areas_processed = 0;
-	unsigned long ia_time, prune_time, rt_time;
-	unsigned long abr_time, total_spf_time, spf_time;
-	char rbuf[32]; /* reason_buf */
-
-	if (IS_DEBUG_OSPF_EVENT)
-		zlog_debug("SPF: Timer (SPF calculation expire)");
-
-	ospf->t_spf_calc = NULL;
-
-	monotime(&spf_start_time);
-	/* Allocate new table tree. */
-	new_table = route_table_init();
-	new_rtrs = route_table_init();
-
-	ospf_vl_unapprove(ospf);
 
 	/* Calculate SPF for each area. */
 	for (ALL_LIST_ELEMENTS(ospf->areas, node, nnode, area)) {
 		/* Do backbone last, so as to first discover intra-area paths
-		 * for any back-bone virtual-links
-		 */
+		 * for any back-bone virtual-links */
 		if (ospf->backbone && ospf->backbone == area)
 			continue;
 
-		ospf_spf_calculate(ospf, area, new_table, new_rtrs);
+		ospf_spf_calculate(area, area->router_lsa_self, new_table,
+				   new_rtrs, is_dry_run, is_root_node);
 		areas_processed++;
 	}
 
 	/* SPF for backbone, if required */
 	if (ospf->backbone) {
-		ospf_spf_calculate(ospf, ospf->backbone, new_table, new_rtrs);
+		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;
+}
+
+/* Worker for SPF calculation scheduler. */
+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 */
+
+	if (IS_DEBUG_OSPF_EVENT)
+		zlog_debug("SPF: Timer (SPF calculation expire)");
+
+	ospf->t_spf_calc = NULL;
+
+	ospf_vl_unapprove(ospf);
+
+	/* Execute SPF for each area including backbone, see RFC 2328 16.1. */
+	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);
 	spf_time = monotime_since(&spf_start_time, NULL);
 
 	ospf_vl_shut_unapproved(ospf);
 
+	/* Calculate inter-area routes, see RFC 2328 16.2. */
 	monotime(&start_time);
 	ospf_ia_routing(ospf, new_table, new_rtrs);
 	ia_time = monotime_since(&start_time, NULL);
 
+	/* Get rid of transit networks and routers we cannot reach anyway. */
 	monotime(&start_time);
 	ospf_prune_unreachable_networks(new_table);
 	ospf_prune_unreachable_routers(new_rtrs);
 	prune_time = monotime_since(&start_time, NULL);
 
-	/* AS-external-LSA calculation should not be performed here. */
-
-	/* If new Router Route is installed,
-	   then schedule re-calculate External routes. */
-	if (1)
-		ospf_ase_calculate_schedule(ospf);
+	/* Note: RFC 2328 16.3. is apparently missing. */
 
+	/*
+	 * Calculate AS external routes, see RFC 2328 16.4.
+	 * There is a dedicated routing table for external routes which is not
+	 * handled here directly
+	 */
+	ospf_ase_calculate_schedule(ospf);
 	ospf_ase_calculate_timer_add(ospf);
 
 	if (IS_DEBUG_OSPF_EVENT)
@@ -1344,22 +1412,22 @@ static int ospf_spf_calculate_timer(struct thread *thread)
 			"%s: ospf install new route, vrf %s id %u new_table count %lu",
 			__func__, ospf_vrf_id_to_name(ospf->vrf_id),
 			ospf->vrf_id, new_table->count);
+
 	/* Update routing table. */
 	monotime(&start_time);
 	ospf_route_install(ospf, new_table);
 	rt_time = monotime_since(&start_time, NULL);
 
-	/* Update ABR/ASBR routing table */
-	if (ospf->old_rtrs) {
-		/* old_rtrs's node holds linked list of ospf_route. --kunihiro.
-		 */
+	/* Free old ABR/ASBR routing table */
+	if (ospf->old_rtrs)
 		/* ospf_route_delete (ospf->old_rtrs); */
 		ospf_rtrs_free(ospf->old_rtrs);
-	}
 
+	/* Update ABR/ASBR routing table */
 	ospf->old_rtrs = ospf->new_rtrs;
 	ospf->new_rtrs = new_rtrs;
 
+	/* ABRs may require additional changes, see RFC 2328 16.7. */
 	monotime(&start_time);
 	if (IS_OSPF_ABR(ospf))
 		ospf_abr_task(ospf);
@@ -1413,8 +1481,10 @@ static int ospf_spf_calculate_timer(struct thread *thread)
 	return 0;
 }
 
-/* Add schedule for SPF calculation.  To avoid frequenst SPF calc, we
-   set timer for SPF calc. */
+/*
+ * Add schedule for SPF calculation. To avoid frequenst SPF calc, we set timer
+ * for SPF calc.
+ */
 void ospf_spf_calculate_schedule(struct ospf *ospf, ospf_spf_reason_t reason)
 {
 	unsigned long delay, elapsed, ht;
@@ -1446,9 +1516,10 @@ void ospf_spf_calculate_schedule(struct ospf *ospf, ospf_spf_reason_t reason)
 
 	/* Get SPF calculation delay time. */
 	if (elapsed < ht) {
-		/* Got an event within the hold time of last SPF. We need to
+		/*
+		 * Got an event within the hold time of last SPF. We need to
 		 * increase the hold_multiplier, if it's not already at/past
-		 * maximum value, and wasn't already increased..
+		 * maximum value, and wasn't already increased.
 		 */
 		if (ht < ospf->spf_max_holdtime)
 			ospf->spf_hold_multiplier++;
@@ -1468,6 +1539,6 @@ void ospf_spf_calculate_schedule(struct ospf *ospf, ospf_spf_reason_t reason)
 		zlog_debug("SPF: calculation timer delay = %ld msec", delay);
 
 	ospf->t_spf_calc = NULL;
-	thread_add_timer_msec(master, ospf_spf_calculate_timer, ospf, delay,
-			      &ospf->t_spf_calc);
+	thread_add_timer_msec(master, ospf_spf_calculate_schedule_worker, ospf,
+			      delay, &ospf->t_spf_calc);
 }
diff --git a/ospfd/ospf_spf.h b/ospfd/ospf_spf.h
index 09a0b6f1b..037114642 100644
--- a/ospfd/ospf_spf.h
+++ b/ospfd/ospf_spf.h
@@ -49,15 +49,14 @@ struct vertex {
 
 /* A nexthop taken on the root node to get to this (parent) vertex */
 struct vertex_nexthop {
-	struct ospf_interface *oi; /* output intf on root node */
 	struct in_addr router;     /* router address to send to */
+	int lsa_pos; /* LSA position for resolving the interface */
 };
 
 struct vertex_parent {
-	struct vertex_nexthop
-		*nexthop;      /* link to nexthop info for this parent */
-	struct vertex *parent; /* parent vertex */
-	int backlink;	  /* index back to parent for router-lsa's */
+	struct vertex_nexthop *nexthop; /* nexthop address for this parent */
+	struct vertex *parent;		/* parent vertex */
+	int backlink; /* index back to parent for router-lsa's */
 };
 
 /* What triggered the SPF ? */
@@ -73,7 +72,18 @@ typedef enum {
 } ospf_spf_reason_t;
 
 extern void ospf_spf_calculate_schedule(struct ospf *, ospf_spf_reason_t);
+extern void ospf_spf_calculate(struct ospf_area *area,
+			       struct ospf_lsa *root_lsa,
+			       struct route_table *new_table,
+			       struct route_table *new_rtrs, bool is_dry_run,
+			       bool is_root_node);
+extern 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);
 extern void ospf_rtrs_free(struct route_table *);
 
+extern void ospf_spf_print(struct vty *vty, struct vertex *v, int i);
+
 /* void ospf_spf_calculate_timer_add (); */
 #endif /* _QUAGGA_OSPF_SPF_H */
diff --git a/ospfd/ospfd.h b/ospfd/ospfd.h
index 230c10e44..8a1469469 100644
--- a/ospfd/ospfd.h
+++ b/ospfd/ospfd.h
@@ -414,6 +414,10 @@ struct ospf_area {
 
 	/* Shortest Path Tree. */
 	struct vertex *spf;
+	bool spf_dry_run;   /* flag for checking if the SPF calculation is
+			       intended for the local RIB */
+	bool spf_root_node; /* flag for checking if the calculating node is the
+			       root node of the SPF tree */
 
 	/* Threads. */
 	struct thread *t_stub_router;     /* Stub-router timer */