path: root/ospfd/ospf_spf.c

/* OSPF SPF calculation.
 * Copyright (C) 1999, 2000 Kunihiro Ishiguro, Toshiaki Takada
 *
 * This file is part of GNU Zebra.
 *
 * GNU Zebra is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the
 * Free Software Foundation; either version 2, or (at your option) any
 * later version.
 *
 * GNU Zebra is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program; see the file COPYING; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
 */

#include <zebra.h>

#include "monotime.h"
#include "thread.h"
#include "memory.h"
#include "hash.h"
#include "linklist.h"
#include "prefix.h"
#include "if.h"
#include "table.h"
#include "log.h"
#include "sockunion.h" /* for inet_ntop () */

#include "ospfd/ospfd.h"
#include "ospfd/ospf_interface.h"
#include "ospfd/ospf_ism.h"
#include "ospfd/ospf_asbr.h"
#include "ospfd/ospf_lsa.h"
#include "ospfd/ospf_lsdb.h"
#include "ospfd/ospf_neighbor.h"
#include "ospfd/ospf_nsm.h"
#include "ospfd/ospf_spf.h"
#include "ospfd/ospf_route.h"
#include "ospfd/ospf_ia.h"
#include "ospfd/ospf_ase.h"
#include "ospfd/ospf_abr.h"
#include "ospfd/ospf_dump.h"
#include "ospfd/ospf_sr.h"
#include "ospfd/ospf_errors.h"

/* Variables to ensure a SPF scheduled log message is printed only once */

static unsigned int spf_reason_flags = 0;

/* dummy vertex to flag "in spftree" */
static const struct vertex vertex_in_spftree = {};
#define LSA_SPF_IN_SPFTREE	(struct vertex *)&vertex_in_spftree
#define LSA_SPF_NOT_EXPLORED	NULL

static void ospf_clear_spf_reason_flags(void)
{
	spf_reason_flags = 0;
}

static void ospf_spf_set_reason(ospf_spf_reason_t reason)
{
	spf_reason_flags |= 1 << reason;
}

static void ospf_vertex_free(void *);

/*
 * 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)
		return v1->distance - v2->distance;

	if (v1->type != v2->type) {
		switch (v1->type) {
		case OSPF_VERTEX_NETWORK:
			return -1;
		case OSPF_VERTEX_ROUTER:
			return 1;
		}
	}
	return 0;
}
DECLARE_SKIPLIST_NONUNIQ(vertex_pqueue, struct vertex, pqi, vertex_cmp)

static void lsdb_clean_stat(struct ospf_lsdb *lsdb)
{
	struct route_table *table;
	struct route_node *rn;
	struct ospf_lsa *lsa;
	int i;

	for (i = OSPF_MIN_LSA; i < OSPF_MAX_LSA; i++) {
		table = lsdb->type[i].db;
		for (rn = route_top(table); rn; rn = route_next(rn))
			if ((lsa = (rn->info)) != NULL)
				lsa->stat = LSA_SPF_NOT_EXPLORED;
	}
}

static struct vertex_nexthop *vertex_nexthop_new(void)
{
	return XCALLOC(MTYPE_OSPF_NEXTHOP, sizeof(struct vertex_nexthop));
}

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
 * attached to the first-hop router vertices, and any intervening network
 * vertices.
 */
static void ospf_canonical_nexthops_free(struct vertex *root)
{
	struct listnode *node, *nnode;
	struct vertex *child;

	for (ALL_LIST_ELEMENTS(root->children, node, nnode, child)) {
		struct listnode *n2, *nn2;
		struct vertex_parent *vp;

		/*
		 * router vertices through an attached network each
		 * have a distinct (canonical / not inherited) nexthop
		 * which must be freed.
		 *
		 * A network vertex can only have router vertices as its
		 * children, so only one level of recursion is possible.
		 */
		if (child->type == OSPF_VERTEX_NETWORK)
			ospf_canonical_nexthops_free(child);

		/* Free child nexthops pointing back to this root vertex */
		for (ALL_LIST_ELEMENTS(child->parents, n2, nn2, vp))
			if (vp->parent == root && vp->nexthop) {
				vertex_nexthop_free(vp->nexthop);
				vp->nexthop = NULL;
			}
	}
}

/*
 * 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,
					       struct vertex_nexthop *hop)
{
	struct vertex_parent *new;

	new = XMALLOC(MTYPE_OSPF_VERTEX_PARENT, sizeof(struct vertex_parent));

	new->parent = v;
	new->backlink = backlink;
	new->nexthop = hop;

	return new;
}

static void vertex_parent_free(void *p)
{
	XFREE(MTYPE_OSPF_VERTEX_PARENT, p);
}

static 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);
}

static struct vertex *ospf_vertex_new(struct ospf_area *area,
				      struct ospf_lsa *lsa)
{
	struct vertex *new;

	new = XCALLOC(MTYPE_OSPF_VERTEX, sizeof(struct vertex));

	new->flags = 0;
	new->type = lsa->data->type;
	new->id = lsa->data->id;
	new->lsa = lsa->data;
	new->children = list_new();
	new->parents = list_new();
	new->parents->del = vertex_parent_free;
	new->parents->cmp = vertex_parent_cmp;
	new->lsa_p = lsa;

	lsa->stat = new;

	listnode_add(area->spf_vertex_list, new);

	if (IS_DEBUG_OSPF_EVENT)
		zlog_debug("%s: Created %s vertex %pI4", __func__,
			   new->type == OSPF_VERTEX_ROUTER ? "Router"
							   : "Network",
			   &new->lsa->id);

	return new;
}

static void ospf_vertex_free(void *data)
{
	struct vertex *v = data;

	if (IS_DEBUG_OSPF_EVENT)
		zlog_debug("%s: Free %s vertex %pI4", __func__,
			   v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network",
			   &v->lsa->id);

	if (v->children)
		list_delete(&v->children);

	if (v->parents)
		list_delete(&v->parents);

	v->lsa = NULL;

	XFREE(MTYPE_OSPF_VERTEX, v);
}

static void ospf_vertex_dump(const char *msg, struct vertex *v,
			     int print_parents, int print_children)
{
	if (!IS_DEBUG_OSPF_EVENT)
		return;

	zlog_debug("%s %s vertex %pI4  distance %u flags %u", msg,
		   v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network",
		   &v->lsa->id, v->distance, (unsigned int)v->flags);

	if (print_parents) {
		struct listnode *node;
		struct vertex_parent *vp;

		for (ALL_LIST_ELEMENTS_RO(v->parents, node, vp)) {
			char buf1[BUFSIZ];

			if (vp) {
				zlog_debug(
					"parent %pI4 backlink %d nexthop %s  lsa pos %d",
					&vp->parent->lsa->id,
					vp->backlink,
					inet_ntop(AF_INET, &vp->nexthop->router,
						  buf1, BUFSIZ),
					vp->nexthop->lsa_pos);
			}
		}
	}

	if (print_children) {
		struct listnode *cnode;
		struct vertex *cv;

		for (ALL_LIST_ELEMENTS_RO(v->children, cnode, cv))
			ospf_vertex_dump(" child:", cv, 0, 0);
	}
}


/* Add a vertex to the list of children in each of its parents. */
static void ospf_vertex_add_parent(struct vertex *v)
{
	struct vertex_parent *vp;
	struct listnode *node;

	assert(v && v->parents);

	for (ALL_LIST_ELEMENTS_RO(v->parents, node, vp)) {
		assert(vp->parent && vp->parent->children);

		/* No need to add two links from the same parent. */
		if (listnode_lookup(vp->parent->children, v) == NULL)
			listnode_add(vp->parent->children, v);
	}
}

static void ospf_spf_init(struct ospf_area *area, struct ospf_lsa *root_lsa,
			  bool is_dry_run, bool is_root_node)
{
	struct list *vertex_list;
	struct vertex *v;

	/* Create vertex list */
	vertex_list = list_new();
	vertex_list->del = ospf_vertex_free;
	area->spf_vertex_list = vertex_list;

	/* Create root node. */
	v = ospf_vertex_new(area, 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;
	area->asbr_count = 0;
}

/* return index of link back to V from W, or -1 if no link found */
static int ospf_lsa_has_link(struct lsa_header *w, struct lsa_header *v)
{
	unsigned int i, length;
	struct router_lsa *rl;
	struct network_lsa *nl;

	/* In case of W is Network LSA. */
	if (w->type == OSPF_NETWORK_LSA) {
		if (v->type == OSPF_NETWORK_LSA)
			return -1;

		nl = (struct network_lsa *)w;
		length = (ntohs(w->length) - OSPF_LSA_HEADER_SIZE - 4) / 4;

		for (i = 0; i < length; i++)
			if (IPV4_ADDR_SAME(&nl->routers[i], &v->id))
				return i;
		return -1;
	}

	/* In case of W is Router LSA. */
	if (w->type == OSPF_ROUTER_LSA) {
		rl = (struct router_lsa *)w;

		length = ntohs(w->length);

		for (i = 0; i < ntohs(rl->links)
			    && length >= sizeof(struct router_lsa);
		     i++, length -= 12) {
			switch (rl->link[i].type) {
			case LSA_LINK_TYPE_POINTOPOINT:
			case LSA_LINK_TYPE_VIRTUALLINK:
				/* Router LSA ID. */
				if (v->type == OSPF_ROUTER_LSA
				    && IPV4_ADDR_SAME(&rl->link[i].link_id,
						      &v->id)) {
					return i;
				}
				break;
			case LSA_LINK_TYPE_TRANSIT:
				/* Network LSA ID. */
				if (v->type == OSPF_NETWORK_LSA
				    && IPV4_ADDR_SAME(&rl->link[i].link_id,
						      &v->id)) {
					return i;
				}
				break;
			case LSA_LINK_TYPE_STUB:
				/* Stub can't lead anywhere, carry on */
				continue;
			default:
				break;
			}
		}
	}
	return -1;
}

/*
 * 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.
 */
static struct router_lsa_link *
ospf_get_next_link(struct vertex *v, struct vertex *w,
		   struct router_lsa_link *prev_link)
{
	uint8_t *p;
	uint8_t *lim;
	uint8_t lsa_type = LSA_LINK_TYPE_TRANSIT;
	struct router_lsa_link *l;

	if (w->type == OSPF_VERTEX_ROUTER)
		lsa_type = LSA_LINK_TYPE_POINTOPOINT;

	if (prev_link == NULL)
		p = ((uint8_t *)v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
	else {
		p = (uint8_t *)prev_link;
		p += (OSPF_ROUTER_LSA_LINK_SIZE
		      + (prev_link->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
	}

	lim = ((uint8_t *)v->lsa) + ntohs(v->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_type)
			continue;

		if (IPV4_ADDR_SAME(&l->link_id, &w->id))
			return l;
	}

	return NULL;
}

static void ospf_spf_flush_parents(struct vertex *w)
{
	struct vertex_parent *vp;
	struct listnode *ln, *nn;

	/* delete the existing nexthops */
	for (ALL_LIST_ELEMENTS(w->parents, ln, nn, vp)) {
		list_delete_node(w->parents, ln);
		vertex_parent_free(vp);
	}
}

/*
 * Consider supplied next-hop for inclusion to the supplied list of
 * equal-cost next-hops, adjust list as neccessary.
 */
static void ospf_spf_add_parent(struct vertex *v, struct vertex *w,
				struct vertex_nexthop *newhop,
				unsigned int distance)
{
	struct vertex_parent *vp, *wp;
	struct listnode *node;

	/* we must have a newhop, and a distance */
	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)).
	 */
	if (w->distance)
		assert(distance <= w->distance);
	else
		w->distance = distance;

	if (IS_DEBUG_OSPF_EVENT) {
		char buf[2][INET_ADDRSTRLEN];
		zlog_debug(
			"%s: Adding %s as parent of %s", __func__,
			inet_ntop(AF_INET, &v->lsa->id, buf[0], sizeof(buf[0])),
			inet_ntop(AF_INET, &w->lsa->id, buf[1],
				  sizeof(buf[1])));
	}

	/*
	 * Adding parent for a new, better path: flush existing parents from W.
	 */
	if (distance < w->distance) {
		if (IS_DEBUG_OSPF_EVENT)
			zlog_debug(
				"%s: distance %d better than %d, flushing existing parents",
				__func__, distance, w->distance);
		ospf_spf_flush_parents(w);
		w->distance = distance;
	}

	/*
	 * 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)) {
		if (memcmp(newhop, wp->nexthop, sizeof(*newhop)) == 0) {
			if (IS_DEBUG_OSPF_EVENT)
				zlog_debug(
					"%s: ... nexthop already on parent list, skipping add",
					__func__);
			return;
		}
	}

	vp = vertex_parent_new(v, ospf_lsa_has_link(w->lsa, v->lsa), newhop);
	listnode_add_sort(w->parents, vp);

	return;
}

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
 * it may be NULL.
 *
 * Note that this function may fail, hence the state of the destination
 * vertex, W, should /not/ be modified in a dependent manner until
 * this function returns. This function will update the W vertex with the
 * provided distance as appropriate.
 */
static unsigned int ospf_nexthop_calculation(struct ospf_area *area,
					     struct vertex *v, struct vertex *w,
					     struct router_lsa_link *l,
					     unsigned int distance, int lsa_pos)
{
	struct listnode *node, *nnode;
	struct vertex_nexthop *nh;
	struct vertex_parent *vp;
	unsigned int added = 0;
	char buf1[BUFSIZ];
	char buf2[BUFSIZ];

	if (IS_DEBUG_OSPF_EVENT) {
		zlog_debug("ospf_nexthop_calculation(): Start");
		ospf_vertex_dump("V (parent):", v, 1, 1);
		ospf_vertex_dump("W (dest)  :", w, 1, 1);
		zlog_debug("V->W distance: %d", distance);
	}

	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.
		 */

		/* we *must* be supplied with the link data */
		assert(l != NULL);

		if (IS_DEBUG_OSPF_EVENT) {
			zlog_debug(
				"%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
			 */
			struct router_lsa_link *l2 = NULL;

			if (l->m[0].type == LSA_LINK_TYPE_POINTOPOINT) {
				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 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.
				 */
				if (oi->type == OSPF_IFTYPE_POINTOPOINT) {
					struct ospf_neighbor *nbr_w = NULL;

					/* Calculating node is root node, link
					 * is P2P */
					if (area->spf_root_node) {
						nbr_w = ospf_nbr_lookup_by_routerid(
							oi->nbrs, &l->link_id);
						if (nbr_w) {
							added = 1;
							nexthop = nbr_w->src;
						}
					}

					/* Reverse lookup */
					if (!added) {
						while ((l2 = ospf_get_next_link(
								w, v, l2))) {
							if (match_stub_prefix(
								    v->lsa,
								    l->link_data,
								    l2->link_data)) {
								added = 1;
								nexthop =
									l2->link_data;
								break;
							}
						}
					}
				} else if (oi->type
					   == OSPF_IFTYPE_POINTOMULTIPOINT) {
					struct prefix_ipv4 la;

					la.family = AF_INET;
					la.prefixlen = oi->address->prefixlen;

					/*
					 * 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;

						if (prefix_cmp((struct prefix
									*)&la,
							       oi->address)
						    != 0)
							continue;
						added = 1;
						nexthop = l2->link_data;
						break;
					}
				}

				if (added) {
					nh = vertex_nexthop_new();
					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);
			} /* end point-to-point link from V to W */
			else if (l->m[0].type == LSA_LINK_TYPE_VIRTUALLINK) {
				/*
				 * 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.
				 */

				struct ospf_vl_data *vl_data;

				vl_data = ospf_vl_lookup(area->ospf, NULL,
							 l->link_id);

				if (vl_data
				    && CHECK_FLAG(vl_data->flags,
						  OSPF_VL_FLAG_APPROVED)) {
					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);
					return 1;
				} else
					zlog_info(
						"ospf_nexthop_calculation(): vl_data for VL link not found");
			} /* end virtual-link from V to W */
			return 0;
		} /* end W is a Router vertex */
		else {
			assert(w->type == OSPF_VERTEX_NETWORK);

			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);
			return 1;
		}
	} /* end V is the root */
	/* Check if W's parent is a network connected to root. */
	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) {
				/*
				 * 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).
					 */
					nh = vertex_nexthop_new();
					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.
				 */
			}
		}
		/*
		 * 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.
		 *
		 * 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 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.
		 */
		if (added)
			return added;
	}

	/*
	 * 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.
	 */
	if (IS_DEBUG_OSPF_EVENT)
		zlog_debug("%s: Intervening routers, adding parent(s)",
			   __func__);

	for (ALL_LIST_ELEMENTS(v->parents, node, nnode, vp)) {
		added = 1;
		ospf_spf_add_parent(v, w, vp->nexthop, distance);
	}

	return added;
}

/*
 * 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_area *area,
			  struct vertex_pqueue_head *candidate)
{
	struct ospf_lsa *w_lsa = NULL;
	uint8_t *p;
	uint8_t *lim;
	struct router_lsa_link *l = NULL;
	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 (v->type == OSPF_VERTEX_ROUTER) {
		if (IS_ROUTER_LSA_VIRTUAL((struct router_lsa *)v->lsa))
			area->transit = OSPF_TRANSIT_TRUE;
	}

	if (IS_DEBUG_OSPF_EVENT)
		zlog_debug("%s: Next vertex of %s vertex %pI4", __func__,
			   v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network",
			   &v->lsa->id);

	p = ((uint8_t *)v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
	lim = ((uint8_t *)v->lsa) + ntohs(v->lsa->length);

	while (p < lim) {
		struct vertex *w;
		unsigned int distance;

		/* In case of V is Router-LSA. */
		if (v->lsa->type == OSPF_ROUTER_LSA) {
			l = (struct router_lsa_link *)p;

			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.
			 */
			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.
			 */
			switch (type) {
			case LSA_LINK_TYPE_POINTOPOINT:
			case LSA_LINK_TYPE_VIRTUALLINK:
				if (type == LSA_LINK_TYPE_VIRTUALLINK
				    && IS_DEBUG_OSPF_EVENT)
					zlog_debug(
						"looking up LSA through VL: %pI4",
						&l->link_id);
				w_lsa = ospf_lsa_lookup(area->ospf, area,
							OSPF_ROUTER_LSA,
							l->link_id, l->link_id);
				if (w_lsa && IS_DEBUG_OSPF_EVENT)
					zlog_debug("found Router LSA %pI4",
						   &l->link_id);
				break;
			case LSA_LINK_TYPE_TRANSIT:
				if (IS_DEBUG_OSPF_EVENT)
					zlog_debug(
						"Looking up Network LSA, ID: %pI4",
						&l->link_id);
				w_lsa = ospf_lsa_lookup_by_id(
					area, OSPF_NETWORK_LSA, l->link_id);
				if (w_lsa && IS_DEBUG_OSPF_EVENT)
					zlog_debug("found the LSA");
				break;
			default:
				flog_warn(EC_OSPF_LSA,
					  "Invalid LSA link type %d", type);
				continue;
			}

			/* step (d) below */
			distance = v->distance + ntohs(l->m[0].metric);
		} else {
			/* In case of V is Network-LSA. */
			r = (struct in_addr *)p;
			p += sizeof(struct in_addr);

			/* Lookup the vertex W's LSA. */
			w_lsa = ospf_lsa_lookup_by_id(area, OSPF_ROUTER_LSA,
						      *r);
			if (w_lsa && IS_DEBUG_OSPF_EVENT)
				zlog_debug("found Router LSA %pI4",
					   &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]
		 */
		if (w_lsa == NULL) {
			if (IS_DEBUG_OSPF_EVENT)
				zlog_debug("No LSA found");
			continue;
		}

		if (IS_LSA_MAXAGE(w_lsa)) {
			if (IS_DEBUG_OSPF_EVENT)
				zlog_debug("LSA is MaxAge");
			continue;
		}

		if (ospf_lsa_has_link(w_lsa->data, v->lsa) < 0) {
			if (IS_DEBUG_OSPF_EVENT)
				zlog_debug("The LSA doesn't have a link back");
			continue;
		}

		/*
		 * (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:
		 */

		/* calculate link cost D -- moved above */

		/* Is there already vertex W in candidate list? */
		if (w_lsa->stat == LSA_SPF_NOT_EXPLORED) {
			/* prepare vertex W. */
			w = ospf_vertex_new(area, w_lsa);

			/* Calculate nexthop to W. */
			if (ospf_nexthop_calculation(area, v, w, l, distance,
						     lsa_pos))
				vertex_pqueue_add(candidate, w);
			else if (IS_DEBUG_OSPF_EVENT)
				zlog_debug("Nexthop Calc failed");
		} else if (w_lsa->stat != LSA_SPF_IN_SPFTREE) {
			w = w_lsa->stat;
			if (w->distance < distance) {
				continue;
			}
			else if (w->distance == distance) {
				/*
				 * Found an equal-cost path to W.
				 * Calculate nexthop of to W from V.
				 */
				ospf_nexthop_calculation(area, v, w, l,
							 distance, lsa_pos);
			}
			else {
				/*
				 * 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.
				 */
				vertex_pqueue_del(candidate, w);
				ospf_nexthop_calculation(area, v, w, l,
							 distance, lsa_pos);
				vertex_pqueue_add(candidate, w);
			}
		} /* end W is already on the candidate list */
	}	 /* end loop over the links in V's LSA */
}

static void ospf_spf_dump(struct vertex *v, int i)
{
	struct listnode *cnode;
	struct listnode *nnode;
	struct vertex_parent *parent;

	if (v->type == OSPF_VERTEX_ROUTER) {
		if (IS_DEBUG_OSPF_EVENT)
			zlog_debug("SPF Result: %d [R] %pI4", i,
				   &v->lsa->id);
	} else {
		struct network_lsa *lsa = (struct network_lsa *)v->lsa;
		if (IS_DEBUG_OSPF_EVENT)
			zlog_debug("SPF Result: %d [N] %pI4/%d", i,
				   &v->lsa->id,
				   ip_masklen(lsa->mask));
	}

	if (IS_DEBUG_OSPF_EVENT)
		for (ALL_LIST_ELEMENTS_RO(v->parents, nnode, parent)) {
			zlog_debug(" nexthop %p %pI4 %d",
				   (void *)parent->nexthop,
				   &parent->nexthop->router,
				   parent->nexthop->lsa_pos);
		}

	i++;

	for (ALL_LIST_ELEMENTS_RO(v->children, cnode, v))
		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] %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,
			&v->lsa->id, ip_masklen(lsa->mask));
	}

	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);
	}

	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)
{
	struct listnode *cnode, *cnnode;
	struct vertex *child;

	if (IS_DEBUG_OSPF_EVENT)
		zlog_debug("ospf_process_stub():processing stubs for area %pI4",
			   &area->area_id);

	if (v->type == OSPF_VERTEX_ROUTER) {
		uint8_t *p;
		uint8_t *lim;
		struct router_lsa_link *l;
		struct router_lsa *router_lsa;
		int lsa_pos = 0;

		if (IS_DEBUG_OSPF_EVENT)
			zlog_debug(
				"ospf_process_stubs():processing router LSA, id: %pI4",
				&v->lsa->id);

		router_lsa = (struct router_lsa *)v->lsa;

		if (IS_DEBUG_OSPF_EVENT)
			zlog_debug(
				"ospf_process_stubs(): we have %d links to process",
				ntohs(router_lsa->links));

		p = ((uint8_t *)v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
		lim = ((uint8_t *)v->lsa) + ntohs(v->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)
				ospf_intra_add_stub(rt, l, v, area,
						    parent_is_root, lsa_pos);
			lsa_pos++;
		}
	}

	ospf_vertex_dump("ospf_process_stubs(): after examining links: ", v, 1,
			 1);

	for (ALL_LIST_ELEMENTS(v->children, cnode, cnnode, child)) {
		if (CHECK_FLAG(child->flags, OSPF_VERTEX_PROCESSED))
			continue;

		/*
		 * The first level of routers connected to the root
		 * should have 'parent_is_root' set, including those
		 * connected via a network vertex.
		 */
		if (area->spf == v)
			parent_is_root = 1;
		else if (v->type == OSPF_VERTEX_ROUTER)
			parent_is_root = 0;

		ospf_spf_process_stubs(area, child, rt, parent_is_root);

		SET_FLAG(child->flags, OSPF_VERTEX_PROCESSED);
	}
}

void ospf_rtrs_free(struct route_table *rtrs)
{
	struct route_node *rn;
	struct list *or_list;
	struct ospf_route * or ;
	struct listnode *node, *nnode;

	if (IS_DEBUG_OSPF_EVENT)
		zlog_debug("Route: Router Routing Table free");

	for (rn = route_top(rtrs); rn; rn = route_next(rn))
		if ((or_list = rn->info) != NULL) {
			for (ALL_LIST_ELEMENTS(or_list, node, nnode, or))
				ospf_route_free(or);

			list_delete(&or_list);

			/* Unlock the node. */
			rn->info = NULL;
			route_unlock_node(rn);
		}

	route_table_finish(rtrs);
}

void ospf_spf_cleanup(struct vertex *spf, struct list *vertex_list)
{
	/*
	 * 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(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 == 0)
                {
                  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");
}
#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,
			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;

	if (IS_DEBUG_OSPF_EVENT) {
		zlog_debug("ospf_spf_calculate: Start");
		zlog_debug("ospf_spf_calculate: running Dijkstra for area %pI4",
			   &area->area_id);
	}

	/*
	 * 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 %pI4's calculation due to empty root LSA",
				&area->area_id);
		return;
	}

	/* 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.
	 */
	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 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, area, &candidate);

		/* RFC2328 16.1. (3). */
		v = vertex_pqueue_pop(&candidate);
		if (!v)
			/* No more vertices left. */
			break;

		v->lsa_p->stat = LSA_SPF_IN_SPFTREE;

		ospf_vertex_add_parent(v);

		/* RFC2328 16.1. (4). */
		if (v->type == OSPF_VERTEX_ROUTER)
			ospf_intra_add_router(new_rtrs, v, area);
		else
			ospf_intra_add_transit(new_table, v, area);

		/* 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, add leaves to the tree
	 * for stub networks.
	 */
	ospf_spf_process_stubs(area, area->spf, new_table, 0);

	ospf_vertex_dump(__func__, area->spf, 0, 1);

	/* Increment SPF Calculation Counter. */
	area->spf_calculation++;

	monotime(&area->ospf->ts_spf);
	area->ts_spf = area->ospf->ts_spf;

	if (IS_DEBUG_OSPF_EVENT)
		zlog_debug("ospf_spf_calculate: Stop. %zd vertices",
			   mtype_stats_alloc(MTYPE_OSPF_VERTEX));

	/* 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);
}

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_area *area;
	struct listnode *node, *nnode;
	int areas_processed = 0;

	/* 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 */
		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++;
	}

	/* 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;
}

/* 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);

	/* 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)
		zlog_debug(
			"%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);

	/* 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)) {
		if (ospf->anyNSSA)
			ospf_abr_nssa_check_status(ospf);
		ospf_abr_task(ospf);
	}
	abr_time = monotime_since(&start_time, NULL);

	/* Schedule Segment Routing update */
	ospf_sr_update_task(ospf);

	total_spf_time =
		monotime_since(&spf_start_time, &ospf->ts_spf_duration);

	rbuf[0] = '\0';
	if (spf_reason_flags) {
		if (spf_reason_flags & SPF_FLAG_ROUTER_LSA_INSTALL)
			strlcat(rbuf, "R, ", sizeof(rbuf));
		if (spf_reason_flags & SPF_FLAG_NETWORK_LSA_INSTALL)
			strlcat(rbuf, "N, ", sizeof(rbuf));
		if (spf_reason_flags & SPF_FLAG_SUMMARY_LSA_INSTALL)
			strlcat(rbuf, "S, ", sizeof(rbuf));
		if (spf_reason_flags & SPF_FLAG_ASBR_SUMMARY_LSA_INSTALL)
			strlcat(rbuf, "AS, ", sizeof(rbuf));
		if (spf_reason_flags & SPF_FLAG_ABR_STATUS_CHANGE)
			strlcat(rbuf, "ABR, ", sizeof(rbuf));
		if (spf_reason_flags & SPF_FLAG_ASBR_STATUS_CHANGE)
			strlcat(rbuf, "ASBR, ",	sizeof(rbuf));
		if (spf_reason_flags & SPF_FLAG_MAXAGE)
			strlcat(rbuf, "M, ", sizeof(rbuf));

		size_t rbuflen = strlen(rbuf);
		if (rbuflen >= 2)
			rbuf[rbuflen - 2] = '\0'; /* skip the last ", " */
		else
			rbuf[0] = '\0';
	}

	if (IS_DEBUG_OSPF_EVENT) {
		zlog_info("SPF Processing Time(usecs): %ld", total_spf_time);
		zlog_info("            SPF Time: %ld", spf_time);
		zlog_info("           InterArea: %ld", ia_time);
		zlog_info("               Prune: %ld", prune_time);
		zlog_info("        RouteInstall: %ld", rt_time);
		if (IS_OSPF_ABR(ospf))
			zlog_info("                 ABR: %ld (%d areas)",
				  abr_time, areas_processed);
		zlog_info("Reason(s) for SPF: %s", rbuf);
	}

	ospf_clear_spf_reason_flags();

	return 0;
}

/*
 * 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;

	if (IS_DEBUG_OSPF_EVENT)
		zlog_debug("SPF: calculation timer scheduled");

	/* OSPF instance does not exist. */
	if (ospf == NULL)
		return;

	ospf_spf_set_reason(reason);

	/* SPF calculation timer is already scheduled. */
	if (ospf->t_spf_calc) {
		if (IS_DEBUG_OSPF_EVENT)
			zlog_debug(
				"SPF: calculation timer is already scheduled: %p",
				(void *)ospf->t_spf_calc);
		return;
	}

	elapsed = monotime_since(&ospf->ts_spf, NULL) / 1000;

	ht = ospf->spf_holdtime * ospf->spf_hold_multiplier;

	if (ht > ospf->spf_max_holdtime)
		ht = ospf->spf_max_holdtime;

	/* Get SPF calculation delay time. */
	if (elapsed < ht) {
		/*
		 * 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.
		 */
		if (ht < ospf->spf_max_holdtime)
			ospf->spf_hold_multiplier++;

		/* always honour the SPF initial delay */
		if ((ht - elapsed) < ospf->spf_delay)
			delay = ospf->spf_delay;
		else
			delay = ht - elapsed;
	} else {
		/* Event is past required hold-time of last SPF */
		delay = ospf->spf_delay;
		ospf->spf_hold_multiplier = 1;
	}

	if (IS_DEBUG_OSPF_EVENT)
		zlog_debug("SPF: calculation timer delay = %ld msec", delay);

	ospf->t_spf_calc = NULL;
	thread_add_timer_msec(master, ospf_spf_calculate_schedule_worker, ospf,
			      delay, &ospf->t_spf_calc);
}