Merge pull request #11242 from patrasar/pimv6_issue_11233

[mirror_frr.git] / 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_ti_lfa.h"
#include "ospfd/ospf_errors.h"
#include "ospfd/ospf_apiserver.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;
                                if (vp->local_nexthop) {
                                        vertex_nexthop_free(vp->local_nexthop);
                                        vp->local_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_nexthop *lhop)
{
        struct vertex_parent *new;

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

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

        return new;
}

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

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)) {
                        if (vp) {
                                zlog_debug(
                                        "parent %pI4 backlink %d nexthop %pI4 lsa pos %d",
                                        &vp->parent->lsa->id, vp->backlink,
                                        &vp->nexthop->router,
                                        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);
        }
}

/* Find a vertex according to its router id */
struct vertex *ospf_spf_vertex_find(struct in_addr id, struct list *vertex_list)
{
        struct listnode *node;
        struct vertex *found;

        for (ALL_LIST_ELEMENTS_RO(vertex_list, node, found)) {
                if (found->id.s_addr == id.s_addr)
                        return found;
        }

        return NULL;
}

/* Find a vertex parent according to its router id */
struct vertex_parent *ospf_spf_vertex_parent_find(struct in_addr id,
                                                  struct vertex *vertex)
{
        struct listnode *node;
        struct vertex_parent *found;

        for (ALL_LIST_ELEMENTS_RO(vertex->parents, node, found)) {
                if (found->parent->id.s_addr == id.s_addr)
                        return found;
        }

        return NULL;
}

struct vertex *ospf_spf_vertex_by_nexthop(struct vertex *root,
                                          struct in_addr *nexthop)
{
        struct listnode *node;
        struct vertex *child;
        struct vertex_parent *vertex_parent;

        for (ALL_LIST_ELEMENTS_RO(root->children, node, child)) {
                vertex_parent = ospf_spf_vertex_parent_find(root->id, child);
                if (vertex_parent->nexthop->router.s_addr == nexthop->s_addr)
                        return child;
        }

        return NULL;
}

/* Create a deep copy of a SPF vertex without children and parents */
static struct vertex *ospf_spf_vertex_copy(struct vertex *vertex)
{
        struct vertex *copy;

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

        memcpy(copy, vertex, sizeof(struct vertex));
        copy->parents = list_new();
        copy->parents->del = vertex_parent_free;
        copy->parents->cmp = vertex_parent_cmp;
        copy->children = list_new();

        return copy;
}

/* Create a deep copy of a SPF vertex_parent */
static struct vertex_parent *
ospf_spf_vertex_parent_copy(struct vertex_parent *vertex_parent)
{
        struct vertex_parent *vertex_parent_copy;
        struct vertex_nexthop *nexthop_copy, *local_nexthop_copy;

        vertex_parent_copy =
                XCALLOC(MTYPE_OSPF_VERTEX, sizeof(struct vertex_parent));

        nexthop_copy = vertex_nexthop_new();
        local_nexthop_copy = vertex_nexthop_new();

        memcpy(vertex_parent_copy, vertex_parent, sizeof(struct vertex_parent));
        memcpy(nexthop_copy, vertex_parent->nexthop,
               sizeof(struct vertex_nexthop));
        memcpy(local_nexthop_copy, vertex_parent->local_nexthop,
               sizeof(struct vertex_nexthop));

        vertex_parent_copy->nexthop = nexthop_copy;
        vertex_parent_copy->local_nexthop = local_nexthop_copy;

        return vertex_parent_copy;
}

/* Create a deep copy of a SPF tree */
void ospf_spf_copy(struct vertex *vertex, struct list *vertex_list)
{
        struct listnode *node;
        struct vertex *vertex_copy, *child, *child_copy, *parent_copy;
        struct vertex_parent *vertex_parent, *vertex_parent_copy;

        /* First check if the node is already in the vertex list */
        vertex_copy = ospf_spf_vertex_find(vertex->id, vertex_list);
        if (!vertex_copy) {
                vertex_copy = ospf_spf_vertex_copy(vertex);
                listnode_add(vertex_list, vertex_copy);
        }

        /* Copy all parents, create parent nodes if necessary */
        for (ALL_LIST_ELEMENTS_RO(vertex->parents, node, vertex_parent)) {
                parent_copy = ospf_spf_vertex_find(vertex_parent->parent->id,
                                                   vertex_list);
                if (!parent_copy) {
                        parent_copy =
                                ospf_spf_vertex_copy(vertex_parent->parent);
                        listnode_add(vertex_list, parent_copy);
                }
                vertex_parent_copy = ospf_spf_vertex_parent_copy(vertex_parent);
                vertex_parent_copy->parent = parent_copy;
                listnode_add(vertex_copy->parents, vertex_parent_copy);
        }

        /* Copy all children, create child nodes if necessary */
        for (ALL_LIST_ELEMENTS_RO(vertex->children, node, child)) {
                child_copy = ospf_spf_vertex_find(child->id, vertex_list);
                if (!child_copy) {
                        child_copy = ospf_spf_vertex_copy(child);
                        listnode_add(vertex_list, child_copy);
                }
                listnode_add(vertex_copy->children, child_copy);
        }

        /* Finally continue copying with child nodes */
        for (ALL_LIST_ELEMENTS_RO(vertex->children, node, child))
                ospf_spf_copy(child, vertex_list);
}

static void ospf_spf_remove_branch(struct vertex_parent *vertex_parent,
                                   struct vertex *child,
                                   struct list *vertex_list)
{
        struct listnode *node, *nnode, *inner_node, *inner_nnode;
        struct vertex *grandchild;
        struct vertex_parent *vertex_parent_found;
        bool has_more_links = false;

        /*
         * First check if there are more nexthops for that parent to that child
         */
        for (ALL_LIST_ELEMENTS_RO(child->parents, node, vertex_parent_found)) {
                if (vertex_parent_found->parent->id.s_addr
                            == vertex_parent->parent->id.s_addr
                    && vertex_parent_found->nexthop->router.s_addr
                               != vertex_parent->nexthop->router.s_addr)
                        has_more_links = true;
        }

        /*
         * No more links from that parent? Then delete the child from its
         * children list.
         */
        if (!has_more_links)
                listnode_delete(vertex_parent->parent->children, child);

        /*
         * Delete the vertex_parent from the child parents list, this needs to
         * be done anyway.
         */
        listnode_delete(child->parents, vertex_parent);

        /*
         * Are there actually more parents left? If not, then delete the child!
         * This is done by recursively removing the links to the grandchildren,
         * such that finally the child can be removed without leaving unused
         * partial branches.
         */
        if (child->parents->count == 0) {
                for (ALL_LIST_ELEMENTS(child->children, node, nnode,
                                       grandchild)) {
                        for (ALL_LIST_ELEMENTS(grandchild->parents, inner_node,
                                               inner_nnode,
                                               vertex_parent_found)) {
                                ospf_spf_remove_branch(vertex_parent_found,
                                                       grandchild, vertex_list);
                        }
                }
                listnode_delete(vertex_list, child);
                ospf_vertex_free(child);
        }
}

static int ospf_spf_remove_link(struct vertex *vertex, struct list *vertex_list,
                                struct router_lsa_link *link)
{
        struct listnode *node, *inner_node;
        struct vertex *child;
        struct vertex_parent *vertex_parent;

        /*
         * Identify the node who shares a subnet (given by the link) with a
         * child and remove the branch of this particular child.
         */
        for (ALL_LIST_ELEMENTS_RO(vertex->children, node, child)) {
                for (ALL_LIST_ELEMENTS_RO(child->parents, inner_node,
                                          vertex_parent)) {
                        if ((vertex_parent->local_nexthop->router.s_addr
                             & link->link_data.s_addr)
                            == (link->link_id.s_addr
                                & link->link_data.s_addr)) {
                                ospf_spf_remove_branch(vertex_parent, child,
                                                       vertex_list);
                                return 0;
                        }
                }
        }

        /* No link found yet, move on recursively */
        for (ALL_LIST_ELEMENTS_RO(vertex->children, node, child)) {
                if (ospf_spf_remove_link(child, vertex_list, link) == 0)
                        return 0;
        }

        /* link was not removed yet */
        return 1;
}

void ospf_spf_remove_resource(struct vertex *vertex, struct list *vertex_list,
                              struct protected_resource *resource)
{
        struct listnode *node, *nnode;
        struct vertex *found;
        struct vertex_parent *vertex_parent;

        switch (resource->type) {
        case OSPF_TI_LFA_LINK_PROTECTION:
                ospf_spf_remove_link(vertex, vertex_list, resource->link);
                break;
        case OSPF_TI_LFA_NODE_PROTECTION:
                found = ospf_spf_vertex_find(resource->router_id, vertex_list);
                if (!found)
                        break;

                /*
                 * Remove the node by removing all links from its parents. Note
                 * that the child is automatically removed here with the last
                 * link from a parent, hence no explicit removal of the node.
                 */
                for (ALL_LIST_ELEMENTS(found->parents, node, nnode,
                                       vertex_parent))
                        ospf_spf_remove_branch(vertex_parent, found,
                                               vertex_list);

                break;
        default:
                /* do nothing */
                break;
        }
}

static void ospf_spf_init(struct ospf_area *area, struct ospf_lsa *root_lsa,
                          bool is_dry_run, bool is_root_node)
{
        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 necessary.
 */
static void ospf_spf_add_parent(struct vertex *v, struct vertex *w,
                                struct vertex_nexthop *newhop,
                                struct vertex_nexthop *newlhop,
                                unsigned int distance)
{
        struct vertex_parent *vp, *wp;
        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)
                zlog_debug("%s: Adding %pI4 as parent of %pI4", __func__,
                           &v->lsa->id, &w->lsa->id);

        /*
         * 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,
                               newlhop);
        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, *lnh;
        struct vertex_parent *vp;
        unsigned int added = 0;

        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:%pI4 link_data:%pI4",
                                __func__, l->m[0].type, &l->link_id,
                                &l->link_data);

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

                                if (area->spf_root_node) {
                                        oi = ospf_if_lookup_by_lsa_pos(area,
                                                                       lsa_pos);
                                        if (!oi) {
                                                zlog_debug(
                                                        "%s: OI not found in LSA: lsa_pos: %d link_id:%pI4 link_data:%pI4",
                                                        __func__, lsa_pos,
                                                        &l->link_id,
                                                        &l->link_data);
                                                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.
                                 */

                                /*
                                 * HACK: we don't know (yet) how to distinguish
                                 * between P2P and P2MP interfaces by just
                                 * looking at LSAs, which is important for
                                 * TI-LFA since you want to do SPF calculations
                                 * from the perspective of other nodes. Since
                                 * TI-LFA is currently not implemented for P2MP
                                 * we just check here if it is enabled and then
                                 * blindly assume that P2P is used. Ultimately
                                 * the interface code needs to be removed
                                 * somehow.
                                 */
                                if (area->ospf->ti_lfa_enabled
                                    || (oi && oi->type == OSPF_IFTYPE_POINTOPOINT)
                                    || (oi && oi->type == OSPF_IFTYPE_POINTOMULTIPOINT
                                           && oi->address->prefixlen == IPV4_MAX_BITLEN)) {
                                        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 && 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;

                                        /*
                                         * Since v is the root the nexthop and
                                         * local nexthop are the same.
                                         */
                                        lnh = vertex_nexthop_new();
                                        memcpy(lnh, nh,
                                               sizeof(struct vertex_nexthop));

                                        ospf_spf_add_parent(v, w, nh, lnh,
                                                            distance);
                                        return 1;
                                } else
                                        zlog_info(
                                                "%s: could not determine nexthop for link %s",
                                                __func__, oi ? 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;

                                        /*
                                         * Since v is the root the nexthop and
                                         * local nexthop are the same.
                                         */
                                        lnh = vertex_nexthop_new();
                                        memcpy(lnh, nh,
                                               sizeof(struct vertex_nexthop));

                                        ospf_spf_add_parent(v, w, nh, lnh,
                                                            distance);
                                        return 1;
                                } else
                                        zlog_info(
                                                "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;

                        /*
                         * Since v is the root the nexthop and
                         * local nexthop are the same.
                         */
                        lnh = vertex_nexthop_new();
                        memcpy(lnh, nh, sizeof(struct vertex_nexthop));

                        ospf_spf_add_parent(v, w, nh, lnh, distance);
                        return 1;
                }
        } /* end V is the root */
        /* 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;

                                        /*
                                         * Since v is the root the nexthop and
                                         * local nexthop are the same.
                                         */
                                        lnh = vertex_nexthop_new();
                                        memcpy(lnh, nh,
                                               sizeof(struct vertex_nexthop));

                                        added = 1;
                                        ospf_spf_add_parent(v, w, nh, lnh,
                                                            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;

                /*
                 * The nexthop is inherited, but the local nexthop still needs
                 * to be created.
                 */
                if (l) {
                        lnh = vertex_nexthop_new();
                        lnh->router = l->link_data;
                        lnh->lsa_pos = lsa_pos;
                } else {
                        lnh = NULL;
                }

                ospf_spf_add_parent(v, w, vp->nexthop, lnh, distance);
        }

        return added;
}

static int ospf_spf_is_protected_resource(struct ospf_area *area,
                                          struct router_lsa_link *link,
                                          struct lsa_header *lsa)
{
        uint8_t *p, *lim;
        struct router_lsa_link *p_link;
        struct router_lsa_link *l = NULL;
        struct in_addr router_id;
        int link_type;

        if (!area->spf_protected_resource)
                return 0;

        link_type = link->m[0].type;

        switch (area->spf_protected_resource->type) {
        case OSPF_TI_LFA_LINK_PROTECTION:
                p_link = area->spf_protected_resource->link;
                if (!p_link)
                        return 0;

                /* For P2P: check if the link belongs to the same subnet */
                if (link_type == LSA_LINK_TYPE_POINTOPOINT
                    && (p_link->link_id.s_addr & p_link->link_data.s_addr)
                               == (link->link_data.s_addr
                                   & p_link->link_data.s_addr))
                        return 1;

                /* For stub: check if this the same subnet */
                if (link_type == LSA_LINK_TYPE_STUB
                    && (p_link->link_id.s_addr == link->link_id.s_addr)
                    && (p_link->link_data.s_addr == link->link_data.s_addr))
                        return 1;

                break;
        case OSPF_TI_LFA_NODE_PROTECTION:
                router_id = area->spf_protected_resource->router_id;
                if (router_id.s_addr == INADDR_ANY)
                        return 0;

                /* For P2P: check if the link leads to the protected node */
                if (link_type == LSA_LINK_TYPE_POINTOPOINT
                    && link->link_id.s_addr == router_id.s_addr)
                        return 1;

                /* The rest is about stub links! */
                if (link_type != LSA_LINK_TYPE_STUB)
                        return 0;

                /*
                 * Check if there's a P2P link in the router LSA with the
                 * corresponding link data in the same subnet.
                 */

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

                while (p < lim) {
                        l = (struct router_lsa_link *)p;
                        p += (OSPF_ROUTER_LSA_LINK_SIZE
                              + (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));

                        /* We only care about P2P with the proper link id */
                        if ((l->m[0].type != LSA_LINK_TYPE_POINTOPOINT)
                            || (l->link_id.s_addr != router_id.s_addr))
                                continue;

                        /* Link data in the subnet given by the link? */
                        if ((link->link_id.s_addr & link->link_data.s_addr)
                            == (l->link_data.s_addr & link->link_data.s_addr))
                                return 1;
                }

                break;
        case OSPF_TI_LFA_UNDEFINED_PROTECTION:
                break;
        }

        return 0;
}

/*
 * For TI-LFA we need the reverse SPF for Q spaces. The reverse SPF is created
 * by honoring the weight of the reverse 'edge', e.g. the edge from W to V, and
 * NOT the weight of the 'edge' from V to W as usual. Hence we need to find the
 * corresponding link in the LSA of W and extract the particular weight.
 *
 * TODO: Only P2P supported by now!
 */
static uint16_t get_reverse_distance(struct vertex *v,
                                     struct router_lsa_link *l,
                                     struct ospf_lsa *w_lsa)
{
        uint8_t *p, *lim;
        struct router_lsa_link *w_link;
        uint16_t distance = 0;

        assert(w_lsa && w_lsa->data);

        p = ((uint8_t *)w_lsa->data) + OSPF_LSA_HEADER_SIZE + 4;
        lim = ((uint8_t *)w_lsa->data) + ntohs(w_lsa->data->length);

        while (p < lim) {
                w_link = (struct router_lsa_link *)p;
                p += (OSPF_ROUTER_LSA_LINK_SIZE
                      + (w_link->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));

                /* Only care about P2P with link ID equal to V's router id */
                if (w_link->m[0].type == LSA_LINK_TYPE_POINTOPOINT
                    && w_link->link_id.s_addr == v->id.s_addr) {
                        distance = ntohs(w_link->m[0].metric);
                        break;
                }
        }

        /*
         * This might happen if the LSA for W is not complete yet. In this
         * case we take the weight of the 'forward' link from V. When the LSA
         * for W is completed the reverse SPF is run again anyway.
         */
        if (distance == 0)
                distance = ntohs(l->m[0].metric);

        if (IS_DEBUG_OSPF_EVENT)
                zlog_debug("%s: reversed distance is %u", __func__, distance);

        return distance;
}

/*
 * RFC2328 16.1 (2).
 * v is on the SPF tree. Examine the links in v's LSA. Update the list of
 * 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;
        uint16_t link_distance;

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

                        /*
                         * Don't process TI-LFA protected resources.
                         *
                         * TODO: Replace this by a proper solution, e.g. remove
                         * corresponding links from the LSDB and run the SPF
                         * algo with the stripped-down LSDB.
                         */
                        if (ospf_spf_is_protected_resource(area, l, v->lsa))
                                continue;

                        /*
                         * (b) Otherwise, W is a transit vertex (router or
                         * transit network). Look up the vertex W's LSA
                         * (router-LSA or network-LSA) in Area A's link state
                         * 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;
                        }

                        /*
                         * For TI-LFA we might need the reverse SPF.
                         * Currently only works with P2P!
                         */
                        if (type == LSA_LINK_TYPE_POINTOPOINT
                            && area->spf_reversed)
                                link_distance =
                                        get_reverse_distance(v, l, w_lsa);
                        else
                                link_distance = ntohs(l->m[0].metric);

                        /* step (d) below */
                        distance = v->distance + link_distance;
                } 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 -- local nexthop %pI4 lsa pos %d\n",
                        &parent->nexthop->router, parent->nexthop->lsa_pos,
                        &parent->local_nexthop->router,
                        parent->local_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));

                        /* Don't process TI-LFA protected resources */
                        if (l->m[0].type == LSA_LINK_TYPE_STUB
                            && !ospf_spf_is_protected_resource(area, l, v->lsa))
                                ospf_intra_add_stub(rt, l, v, area,
                                                    parent_is_root, lsa_pos);
                        lsa_pos++;
                }
        }

        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.
         */
        if (spf)
                ospf_canonical_nexthops_free(spf);

        /* Free SPF vertices list with deconstructor ospf_vertex_free. */
        if (vertex_list)
                list_delete(&vertex_list);
}

/* 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 *all_rtrs,
                        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_transit(new_table, v, area);
                else {
                        ospf_intra_add_router(new_rtrs, v, area, false);
                        if (all_rtrs)
                                ospf_intra_add_router(all_rtrs, v, area, true);
                }

                /* 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);
                if (all_rtrs)
                        ospf_router_route_table_dump(all_rtrs);
        }

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

void ospf_spf_calculate_area(struct ospf *ospf, struct ospf_area *area,
                             struct route_table *new_table,
                             struct route_table *all_rtrs,
                             struct route_table *new_rtrs)
{
        ospf_spf_calculate(area, area->router_lsa_self, new_table, all_rtrs,
                           new_rtrs, false, true);

        if (ospf->ti_lfa_enabled)
                ospf_ti_lfa_compute(area, new_table,
                                    ospf->ti_lfa_protection_type);

        ospf_spf_cleanup(area->spf, area->spf_vertex_list);

        area->spf = NULL;
        area->spf_vertex_list = NULL;
}

void ospf_spf_calculate_areas(struct ospf *ospf, struct route_table *new_table,
                              struct route_table *all_rtrs,
                              struct route_table *new_rtrs)
{
        struct ospf_area *area;
        struct listnode *node, *nnode;

        /* 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(ospf, area, new_table, all_rtrs,
                                        new_rtrs);
        }

        /* SPF for backbone, if required */
        if (ospf->backbone)
                ospf_spf_calculate_area(ospf, ospf->backbone, new_table,
                                        all_rtrs, new_rtrs);
}

/* Worker for SPF calculation scheduler. */
static void ospf_spf_calculate_schedule_worker(struct thread *thread)
{
        struct ospf *ospf = THREAD_ARG(thread);
        struct route_table *new_table, *new_rtrs;
        struct route_table *all_rtrs = NULL;
        struct timeval start_time, spf_start_time;
        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 */

        /* If we have opaque enabled then track all router reachability */
        if (CHECK_FLAG(ospf->opaque, OPAQUE_OPERATION_READY_BIT))
                all_rtrs = route_table_init();

        ospf_spf_calculate_areas(ospf, new_table, all_rtrs, 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);
        if (all_rtrs)
                ospf_prune_unreachable_routers(all_rtrs);
        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 all routers routing table */
        if (ospf->oall_rtrs)
                /* ospf_route_delete (ospf->old_rtrs); */
                ospf_rtrs_free(ospf->oall_rtrs);

        /* Update all routers routing table */
        ospf->oall_rtrs = ospf->all_rtrs;
        ospf->all_rtrs = all_rtrs;
        ospf_apiserver_notify_reachable(ospf->oall_rtrs, ospf->all_rtrs);

        /* 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 & (1 << SPF_FLAG_ROUTER_LSA_INSTALL))
                        strlcat(rbuf, "R, ", sizeof(rbuf));
                if (spf_reason_flags & (1 << SPF_FLAG_NETWORK_LSA_INSTALL))
                        strlcat(rbuf, "N, ", sizeof(rbuf));
                if (spf_reason_flags & (1 << SPF_FLAG_SUMMARY_LSA_INSTALL))
                        strlcat(rbuf, "S, ", sizeof(rbuf));
                if (spf_reason_flags & (1 << SPF_FLAG_ASBR_SUMMARY_LSA_INSTALL))
                        strlcat(rbuf, "AS, ", sizeof(rbuf));
                if (spf_reason_flags & (1 << SPF_FLAG_ABR_STATUS_CHANGE))
                        strlcat(rbuf, "ABR, ", sizeof(rbuf));
                if (spf_reason_flags & (1 << SPF_FLAG_ASBR_STATUS_CHANGE))
                        strlcat(rbuf, "ASBR, ", sizeof(rbuf));
                if (spf_reason_flags & (1 << SPF_FLAG_MAXAGE))
                        strlcat(rbuf, "M, ", sizeof(rbuf));
                if (spf_reason_flags & (1 << SPF_FLAG_GR_FINISH))
                        strlcat(rbuf, "GR, ", 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, ospf->areas->count);
                zlog_info("Reason(s) for SPF: %s", rbuf);
        }

        ospf_clear_spf_reason_flags();
}

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

/* Restart OSPF SPF algorithm*/
void ospf_restart_spf(struct ospf *ospf)
{
        if (IS_DEBUG_OSPF_EVENT)
                zlog_debug("%s: Restart SPF.", __func__);

        /* Handling inter area and intra area routes*/
        if (ospf->new_table) {
                ospf_route_delete(ospf, ospf->new_table);
                ospf_route_table_free(ospf->new_table);
                ospf->new_table = route_table_init();
        }

        /* Handling of TYPE-5 lsa(external routes) */
        if (ospf->old_external_route) {
                ospf_route_delete(ospf, ospf->old_external_route);
                ospf_route_table_free(ospf->old_external_route);
                ospf->old_external_route = route_table_init();
        }

        /* Trigger SPF */
        ospf_spf_calculate_schedule(ospf, SPF_FLAG_CONFIG_CHANGE);
}