ospfd: clean some bitrot in SPF code

Just non-functional changes, cosmetics, removal of eye
cancer. The intention here is to make the SPF code more
approachable.

Signed-off-by: GalaxyGorilla <sascha@netdef.org>

1 files changed, 304 insertions, 289 deletions

diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c
index 91fc20475..7e293d7ed 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);
 
@@ -291,12 +291,12 @@ 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)
 {
 	struct vertex *v;
 
 	/* Create root node. */
-	v = ospf_vertex_new(area->router_lsa_self);
+	v = ospf_vertex_new(root_lsa);
 
 	area->spf = v;
 
@@ -364,7 +364,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 +434,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 +454,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 +466,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 +486,8 @@ static void ospf_spf_add_parent(struct vertex *v, struct vertex *w,
 	return;
 }
 
-/* 16.1.1.  Calculate nexthop from root through V (parent) to
+/*
+ * 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
@@ -514,16 +519,14 @@ 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);
@@ -548,58 +551,51 @@ static unsigned int ospf_nexthop_calculation(struct ospf_area *area,
 		}
 
 		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 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.
-					*/
+					/*
+					 * 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.
+					 */
 					struct ospf_neighbor *nbr_w;
 
 					nbr_w = ospf_nbr_lookup_by_routerid(
@@ -615,8 +611,10 @@ static unsigned int ospf_nexthop_calculation(struct ospf_area *area,
 					la.family = AF_INET;
 					la.prefixlen = oi->address->prefixlen;
 
-					/* V links to W on PtMP interface
-					   - find the interface address on W */
+					/*
+					 * V links to W on PtMP interface;
+					 * find the interface address on W
+					 */
 					while ((l2 = ospf_get_next_link(w, v,
 									l2))) {
 						la.prefix = l2->link_data;
@@ -626,8 +624,11 @@ static unsigned int ospf_nexthop_calculation(struct ospf_area *area,
 							       oi->address)
 						    != 0)
 							continue;
-						/* link_data is on our PtMP
-						 * network */
+
+						/*
+						 * link_data is on our PtMP
+						 * network
+						 */
 						added = 1;
 						nexthop = l2->link_data;
 						break;
@@ -635,8 +636,10 @@ static unsigned int ospf_nexthop_calculation(struct ospf_area *area,
 				}
 
 				if (added) {
-					/* found all necessary info to build
-					 * nexthop */
+					/*
+					 * found all necessary info to build
+					 * nexthop
+					 */
 					nh = vertex_nexthop_new();
 					nh->oi = oi;
 					nh->router = nexthop;
@@ -650,17 +653,15 @@ static unsigned int ospf_nexthop_calculation(struct ospf_area *area,
 			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.
 				 */
 				vl_data = ospf_vl_lookup(area->ospf, NULL,
 							 l->link_id);
@@ -693,29 +694,27 @@ 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;
@@ -723,52 +722,42 @@ static unsigned int ospf_nexthop_calculation(struct ospf_area *area,
 					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 +774,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 +790,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;
@@ -829,37 +820,35 @@ static void ospf_spf_next(struct vertex *v, struct ospf *ospf,
 			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 +857,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 +876,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 +907,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,25 +940,24 @@ 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,
@@ -1020,24 +1011,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 +1054,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 +1091,7 @@ void ospf_rtrs_free(struct route_table *rtrs)
 			rn->info = NULL;
 			route_unlock_node(rn);
 		}
+
 	route_table_finish(rtrs);
 }
 
@@ -1162,8 +1157,9 @@ 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,
+/* Calculating the shortest-path tree for an area, see RFC2328 16.1. */
+static void ospf_spf_calculate(struct ospf_area *area,
+			       struct ospf_lsa *root_lsa,
 			       struct route_table *new_table,
 			       struct route_table *new_rtrs)
 {
@@ -1176,55 +1172,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);
 
 	/* 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,24 +1233,23 @@ 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
+	/*
+	 * Free nexthop information, canonical versions of which are attached
 	 * the first level of router vertices attached to the root vertex, see
 	 * ospf_nexthop_calculation.
 	 */
@@ -1268,75 +1265,90 @@ 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
+	/*
+	 * 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)
+static int ospf_spf_calculate_areas(struct ospf *ospf,
+				    struct route_table *new_table,
+				    struct route_table *new_rtrs)
 {
-	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);
 		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);
 		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);
 	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 +1356,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 +1425,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 +1460,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 +1483,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);
 }