diff options
Diffstat (limited to 'ospf6d/ospf6_spf.c')
| -rw-r--r-- | ospf6d/ospf6_spf.c | 1686 |
1 files changed, 438 insertions, 1248 deletions
diff --git a/ospf6d/ospf6_spf.c b/ospf6d/ospf6_spf.c index fd7fc779..10b73b83 100644 --- a/ospf6d/ospf6_spf.c +++ b/ospf6d/ospf6_spf.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 1999 Yasuhiro Ohara + * Copyright (C) 2003 Yasuhiro Ohara * * This file is part of GNU Zebra. * @@ -18,1437 +18,627 @@ * Free Software Foundation, Inc., 59 Temple Place - Suite 330, * Boston, MA 02111-1307, USA. */ + /* Shortest Path First calculation for OSPFv3 */ -#include "ospf6d.h" +#include <zebra.h> -#include "linklist.h" +#include "log.h" +#include "memory.h" +#include "command.h" +#include "vty.h" #include "prefix.h" -#include "table.h" +#include "pqueue.h" +#include "linklist.h" +#include "thread.h" -#include "ospf6_proto.h" +#include "ospf6d.h" #include "ospf6_lsa.h" #include "ospf6_lsdb.h" #include "ospf6_route.h" +#include "ospf6_area.h" #include "ospf6_spf.h" -#include "ospf6_neighbor.h" +#include "ospf6_intra.h" #include "ospf6_interface.h" -#include "ospf6_area.h" -#include "ospf6_bintree.h" -#include "ospf6_linklist.h" - -struct bintree *_candidate_list; -struct linklist *nexthop_list; - -struct ospf6_spf_candidate_node -{ - u_int32_t cost; - struct linklist *list; -}; - -int -ospf6_spf_candidate_node_cmp (void *a, void *b) -{ - struct ospf6_spf_candidate_node *ca = a; - struct ospf6_spf_candidate_node *cb = b; - return ca->cost - cb->cost; -} +unsigned char conf_debug_ospf6_spf = 0; int -ospf6_spf_vertex_cmp (void *a, void *b) +ospf6_vertex_cmp (void *a, void *b) { - return 1; -} + struct ospf6_vertex *va = (struct ospf6_vertex *) a; + struct ospf6_vertex *vb = (struct ospf6_vertex *) b; -void -ospf6_spf_candidate_node_print (int indent_num, void *node) -{ - struct ospf6_spf_candidate_node *cn = node; - char format[256]; - - snprintf (format, sizeof (format), "%%%ds %%d (num: %%d)", - indent_num * 2 + 1); - zlog_info (format, " ", cn->cost, cn->list->count); + /* ascending order */ + return (va->cost - vb->cost); } -void -ospf6_spf_candidate_init () -{ - _candidate_list = bintree_create (); - _candidate_list->cmp = ospf6_spf_candidate_node_cmp; -} - -u_int32_t -ospf6_spf_candidate_count () -{ - u_int32_t count = 0; - struct bintree_node node; - struct ospf6_spf_candidate_node *cnode; - - for (bintree_head (_candidate_list, &node); ! bintree_end (&node); - bintree_next (&node)) - { - cnode = node.data; - count += cnode->list->count; - } - - return count; -} - -void -ospf6_spf_candidate_print () -{ - zlog_info ("---------------------------"); - bintree_print (ospf6_spf_candidate_node_print, _candidate_list); - zlog_info ("---------------------------"); -} - -void -ospf6_spf_candidate_enqueue (struct ospf6_vertex *v) -{ - struct ospf6_spf_candidate_node req, *node; - - memset (&req, 0, sizeof (req)); - req.cost = v->distance; - node = bintree_lookup (&req, _candidate_list); - - if (node == NULL) - { - node = malloc (sizeof (struct ospf6_spf_candidate_node)); - node->cost = v->distance; - node->list = linklist_create (); - node->list->cmp = ospf6_spf_vertex_cmp; - bintree_add (node, _candidate_list); - } - - linklist_add (v, node->list); - -#if 0 - if (IS_OSPF6_DUMP_SPF) - ospf6_spf_candidate_print (); -#endif -} - -struct ospf6_vertex * -ospf6_spf_candidate_dequeue () +int +ospf6_vertex_id_cmp (void *a, void *b) { - struct ospf6_spf_candidate_node *node; - struct linklist_node lnode; - struct ospf6_vertex *ret; + struct ospf6_vertex *va = (struct ospf6_vertex *) a; + struct ospf6_vertex *vb = (struct ospf6_vertex *) b; + int ret = 0; - node = bintree_lookup_min (_candidate_list); - if (node == NULL) - return NULL; - - linklist_head (node->list, &lnode); - ret = lnode.data; - - linklist_remove (ret, node->list); - if (node->list->count == 0) - { - linklist_delete (node->list); - bintree_remove (node, _candidate_list); - } - -#if 0 - if (IS_OSPF6_DUMP_SPF) - ospf6_spf_candidate_print (); -#endif + ret = ntohl (ospf6_linkstate_prefix_adv_router (&va->vertex_id)) - + ntohl (ospf6_linkstate_prefix_adv_router (&vb->vertex_id)); + if (ret) + return ret; + ret = ntohl (ospf6_linkstate_prefix_id (&va->vertex_id)) - + ntohl (ospf6_linkstate_prefix_id (&vb->vertex_id)); return ret; } -void -ospf6_spf_candidate_remove (struct ospf6_vertex *v) -{ - struct bintree_node node; - struct ospf6_spf_candidate_node *cnode = NULL; - - for (bintree_head (_candidate_list, &node); ! bintree_end (&node); - bintree_next (&node)) - { - cnode = node.data; - if (linklist_lookup (v, cnode->list)) - { - linklist_remove (v, cnode->list); - break; - } - } - - if (cnode->list->count == 0) - { - linklist_delete (cnode->list); - bintree_remove (cnode, _candidate_list); - } -} - - -#define TIMER_SEC_MICRO 1000000 - -/* timeval calculation */ -static void -ospf6_timeval_add (const struct timeval *t1, const struct timeval *t2, - struct timeval *result) -{ - long moveup = 0; - - result->tv_usec = t1->tv_usec + t2->tv_usec; - while (result->tv_usec > TIMER_SEC_MICRO) - { - result->tv_usec -= TIMER_SEC_MICRO; - moveup ++; - } - - result->tv_sec = t1->tv_sec + t2->tv_sec + moveup; -} - -static void -ospf6_timeval_add_equal (const struct timeval *t, struct timeval *result) +struct ospf6_vertex * +ospf6_vertex_create (struct ospf6_lsa *lsa) { - struct timeval tmp; - ospf6_timeval_add (t, result, &tmp); - result->tv_sec = tmp.tv_sec; - result->tv_usec = tmp.tv_usec; -} + struct ospf6_vertex *v; + int i; -/* Compare timeval a and b. It returns an integer less than, equal - to, or great than zero if a is found, respectively, to be less - than, to match, or be greater than b. */ -static int -ospf6_timeval_cmp (const struct timeval t1, const struct timeval t2) -{ - return (t1.tv_sec == t2.tv_sec - ? t1.tv_usec - t2.tv_usec : t1.tv_sec - t2.tv_sec); -} + v = (struct ospf6_vertex *) + XMALLOC (MTYPE_OSPF6_VERTEX, sizeof (struct ospf6_vertex)); - -static int -ospf6_spf_lsd_num (struct ospf6_vertex *V, struct ospf6_area *o6a) -{ - u_int16_t type; - u_int32_t id, adv_router; - struct ospf6_lsa *lsa; - - if (V->vertex_id.id.s_addr) - type = htons (OSPF6_LSA_TYPE_NETWORK); + /* type */ + if (ntohs (lsa->header->type) == OSPF6_LSTYPE_ROUTER) + v->type = OSPF6_VERTEX_TYPE_ROUTER; + else if (ntohs (lsa->header->type) == OSPF6_LSTYPE_NETWORK) + v->type = OSPF6_VERTEX_TYPE_NETWORK; else - type = htons (OSPF6_LSA_TYPE_ROUTER); - id = V->vertex_id.id.s_addr; - adv_router = V->vertex_id.adv_router.s_addr; + assert (0); - lsa = ospf6_lsdb_lookup_lsdb (type, id, adv_router, o6a->lsdb); - if (! lsa) - { - zlog_err ("SPF: Can't find associated LSA for %s", V->string); - return 0; - } + /* vertex_id */ + ospf6_linkstate_prefix (lsa->header->adv_router, lsa->header->id, + &v->vertex_id); - return ospf6_lsa_lsd_num ((struct ospf6_lsa_header *) lsa->header); -} + /* name */ + ospf6_linkstate_prefix2str (&v->vertex_id, v->name, sizeof (v->name)); -/* RFC2328 section 16.1.1: - Check if there is at least one router in the path - from the root to this vertex. */ -static int -ospf6_spf_is_router_to_root (struct ospf6_vertex *c, - struct ospf6_spftree *spf_tree) -{ - listnode node; - struct ospf6_vertex *p; - - if (spf_tree->root == c) - return 0; + /* Associated LSA */ + v->lsa = lsa; - for (node = listhead (c->parent_list); node; nextnode (node)) - { - p = (struct ospf6_vertex *) getdata (node); + /* capability bits + options */ + v->capability = *(u_char *)(OSPF6_LSA_HEADER_END (lsa->header)); + v->options[0] = *(u_char *)(OSPF6_LSA_HEADER_END (lsa->header) + 1); + v->options[1] = *(u_char *)(OSPF6_LSA_HEADER_END (lsa->header) + 2); + v->options[2] = *(u_char *)(OSPF6_LSA_HEADER_END (lsa->header) + 3); - if (p == spf_tree->root) - return 0; + for (i = 0; i < OSPF6_MULTI_PATH_LIMIT; i++) + ospf6_nexthop_clear (&v->nexthop[i]); - if (p->vertex_id.id.s_addr == 0) /* this is router */ - continue; - else if (ospf6_spf_is_router_to_root (p, spf_tree)) - continue; + v->parent = NULL; + v->child_list = list_new (); + v->child_list->cmp = ospf6_vertex_id_cmp; - return 0; - } - - return 1; + return v; } -static struct in6_addr * -ospf6_spf_get_ipaddr (u_int32_t id, u_int32_t adv_router, u_int32_t ifindex) +void +ospf6_vertex_delete (struct ospf6_vertex *v) { - char buf[64], nhbuf[64]; - struct ospf6_interface *o6i; - struct ospf6_neighbor *o6n; - struct ospf6_lsa *lsa; - struct ospf6_lsdb_node node; - - o6i = ospf6_interface_lookup_by_index (ifindex); - if (! o6i) - { - zlog_err ("SPF: Can't find interface: index %d", ifindex); - return (struct in6_addr *) NULL; - } - - /* Find Link-LSA of the vertex in question */ - lsa = NULL; - for (ospf6_lsdb_type_router (&node, htons (OSPF6_LSA_TYPE_LINK), - adv_router, o6i->lsdb); - ! ospf6_lsdb_is_end (&node); - ospf6_lsdb_next (&node)) - lsa = node.lsa; - - /* return Linklocal Address field if the Link-LSA exists */ - if (lsa && lsa->header->adv_router == adv_router) - { - struct ospf6_link_lsa *link_lsa; - link_lsa = (struct ospf6_link_lsa *) (lsa->header + 1); - return &link_lsa->llsa_linklocal; - } - - zlog_warn ("SPF: Can't find Link-LSA for %s", - inet_ntop (AF_INET, &adv_router, buf, sizeof (buf))); - - o6n = ospf6_neighbor_lookup (adv_router, o6i); - if (! o6n) - { - inet_ntop (AF_INET, &adv_router, buf, sizeof (buf)); - zlog_err ("SPF: Can't find neighbor %s in %s, " - "unable to find his linklocal address", - buf, o6i->interface->name); - return (struct in6_addr *) NULL; - } - - zlog_warn ("SPF: use packet's source address for %s's nexthop: %s", - inet_ntop (AF_INET, &adv_router, buf, sizeof (buf)), - inet_ntop (AF_INET6, &o6n->hisaddr, nhbuf, sizeof (nhbuf))); - - return &o6n->hisaddr; + list_delete (v->child_list); + XFREE (MTYPE_OSPF6_VERTEX, v); } -static int -ospf6_spf_nexthop_calculation (struct ospf6_vertex *W, - u_int32_t ifindex, - struct ospf6_vertex *V, - struct ospf6_spftree *spf_tree) +struct ospf6_lsa * +ospf6_lsdesc_lsa (caddr_t lsdesc, struct ospf6_vertex *v) { - struct ospf6_nexthop *nexthop, *n; - u_int32_t adv_router, id; - struct in6_addr nexthop_ipaddr, *ipaddr; - unsigned int nexthop_ifindex; - struct linklist_node node; - - /* until this, nexthop_list should be untouched */ - assert (list_isempty (W->nexthop_list)); - - /* If ther is at least one intervening router from root to W */ - if (ospf6_spf_is_router_to_root (W, spf_tree)) - { - /* Create no new nexthop, Inherit from the intervening router */ - for (linklist_head (V->nexthop_list, &node); ! linklist_end (&node); - linklist_next (&node)) - linklist_add (node.data, W->nexthop_list); - return 0; - } - - /* Create new nexthop */ - - adv_router = W->vertex_id.adv_router.s_addr; - id = W->vertex_id.id.s_addr; + struct ospf6_lsa *lsa; + u_int16_t type = 0; + u_int32_t id = 0, adv_router = 0; - nexthop_ifindex = 0; - memset (&nexthop_ipaddr, 0, sizeof (struct in6_addr)); - if (spf_tree->root && V == spf_tree->root) + if (VERTEX_IS_TYPE (NETWORK, v)) { - nexthop_ifindex = ifindex; - if (! id) /* xxx, if V is router */ - { - ipaddr = ospf6_spf_get_ipaddr (id, adv_router, ifindex); - if (! ipaddr) - { - /* xxx, should trigger error and quit SPF calculation... */ - memset (&nexthop_ipaddr, 0xff, sizeof (struct in6_addr)); - return -1; - } - else - memcpy (&nexthop_ipaddr, ipaddr, sizeof (struct in6_addr)); - } + type = htons (OSPF6_LSTYPE_ROUTER); + id = htonl (0); + adv_router = NETWORK_LSDESC_GET_NBR_ROUTERID (lsdesc); } else { - /* V is broadcast network, W is router */ - assert (V->vertex_id.id.s_addr != 0); - assert (W->vertex_id.id.s_addr == 0); - - linklist_head (V->nexthop_list, &node); - n = (struct ospf6_nexthop *) node.data; - nexthop_ifindex = n->ifindex; - ipaddr = ospf6_spf_get_ipaddr (id, adv_router, n->ifindex); - if (! ipaddr) + if (ROUTER_LSDESC_IS_TYPE (POINTTOPOINT, lsdesc)) { - /* xxx, should trigger error and quit SPF calculation... */ - memset (&nexthop_ipaddr, 0xff, sizeof (struct in6_addr)); - return -1; - } - else - memcpy (&nexthop_ipaddr, ipaddr, sizeof (struct in6_addr)); - } - - nexthop = XCALLOC (MTYPE_OSPF6_VERTEX, sizeof (struct ospf6_nexthop)); - nexthop->ifindex = nexthop_ifindex; - memcpy (&nexthop->address, &nexthop_ipaddr, sizeof (nexthop->address)); - - linklist_add (nexthop, W->nexthop_list); - - /* to hold malloced memory */ - linklist_add (nexthop, nexthop_list); - - return 0; -} - -static struct ospf6_vertex * -ospf6_spf_vertex_create (int index, struct ospf6_vertex *V, - struct ospf6_area *o6a) -{ - struct ospf6_lsa *lsa; - struct ospf6_router_lsa *router_lsa; - struct ospf6_router_lsd *router_lsd; - struct ospf6_network_lsa *network_lsa; - struct ospf6_network_lsd *network_lsd; - u_int32_t id, adv_router; - u_int16_t type; - void *lsd; - struct ospf6_vertex *W; - u_int16_t distance; - u_int32_t ifindex; - int backreference, lsdnum, i; - char buf_router[16], buf_id[16]; - - type = id = adv_router = 0; - - /* Get Linkstate description */ - lsd = ospf6_lsa_lsd_get (index, (struct ospf6_lsa_header *) V->lsa->header); - if (! lsd) - { - zlog_err ("SPF: Can't find %dth Link description from %s", - index, V->lsa->str); - return (struct ospf6_vertex *) NULL; - } - - /* Check Link state description */ - distance = 0; - ifindex = 0; - if (V->lsa->header->type == htons (OSPF6_LSA_TYPE_ROUTER)) - { - router_lsd = lsd; - if (router_lsd->type == OSPF6_ROUTER_LSD_TYPE_POINTTOPOINT) - { - type = htons (OSPF6_LSA_TYPE_ROUTER); + type = htons (OSPF6_LSTYPE_ROUTER); id = htonl (0); + adv_router = ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc); } - else if (router_lsd->type == OSPF6_ROUTER_LSD_TYPE_TRANSIT_NETWORK) + else if (ROUTER_LSDESC_IS_TYPE (TRANSIT_NETWORK, lsdesc)) { - type = htons (OSPF6_LSA_TYPE_NETWORK); - id = router_lsd->neighbor_interface_id; + type = htons (OSPF6_LSTYPE_NETWORK); + id = htonl (ROUTER_LSDESC_GET_NBR_IFID (lsdesc)); + adv_router = ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc); } - adv_router = router_lsd->neighbor_router_id; - distance = ntohs (router_lsd->metric); - ifindex = ntohl (router_lsd->interface_id); - } - else if (V->lsa->header->type == htons (OSPF6_LSA_TYPE_NETWORK)) - { - network_lsd = lsd; - type = htons (OSPF6_LSA_TYPE_ROUTER); - id = htonl (0); - adv_router = network_lsd->adv_router; } - /* Avoid creating candidate of myself */ - if (adv_router == o6a->ospf6->router_id && - type == htons (OSPF6_LSA_TYPE_ROUTER)) - { - return (struct ospf6_vertex *) NULL; - } - - /* Find Associated LSA for W */ - lsa = ospf6_lsdb_lookup_lsdb (type, id, adv_router, o6a->lsdb); - - if (! lsa) - { - inet_ntop (AF_INET, &adv_router, buf_router, sizeof (buf_router)); - inet_ntop (AF_INET, &id, buf_id, sizeof (buf_id)); - - if (IS_OSPF6_DUMP_SPF) - { - if (type == htons (OSPF6_LSA_TYPE_ROUTER)) - zlog_info ("SPF: Can't find LSA for W (%s *): not found", - buf_router); - else - zlog_info ("SPF: Can't find LSA for W (%s %s): not found", - buf_router, buf_id); - } - return (struct ospf6_vertex *) NULL; - } + lsa = ospf6_lsdb_lookup (type, id, adv_router, v->area->lsdb); - if (IS_LSA_MAXAGE (lsa)) + if (IS_OSPF6_DEBUG_SPF (DETAIL)) { - if (IS_OSPF6_DUMP_SPF) - zlog_info ("SPF: Associated LSA for W is MaxAge: %s", lsa->str); - return (struct ospf6_vertex *) NULL; - } - - /* Check back reference from W's lsa to V's lsa */ - backreference = 0; - lsdnum = ospf6_lsa_lsd_num ((struct ospf6_lsa_header *) lsa->header); - for (i = 0; i < lsdnum; i++) - { - if (ospf6_lsa_lsd_is_refer_ok (i, (struct ospf6_lsa_header *) lsa->header, - index, (struct ospf6_lsa_header *) V->lsa->header)) - backreference++; - } - if (! backreference) - { - if (IS_OSPF6_DUMP_SPF) - zlog_info ("SPF: Back reference failed: V: %s, W: %s", - V->lsa->str, lsa->str); - return (struct ospf6_vertex *) NULL; - } - - /* Allocate new ospf6_vertex for W */ - W = (struct ospf6_vertex *) XMALLOC (MTYPE_OSPF6_VERTEX, - sizeof (struct ospf6_vertex)); - if (! W) - { - zlog_err ("SPF: Can't allocate memory for Vertex"); - return (struct ospf6_vertex *) NULL; - } - memset (W, 0, sizeof (struct ospf6_vertex)); - - /* Initialize */ - W->vertex_id.family = AF_UNSPEC; - W->vertex_id.prefixlen = 64; /* xxx */ - W->lsa = lsa; - if (type == htons (OSPF6_LSA_TYPE_ROUTER)) - W->vertex_id.id.s_addr = htonl (0); /* XXX */ - else - W->vertex_id.id.s_addr = W->lsa->header->id; - W->vertex_id.adv_router.s_addr = W->lsa->header->adv_router; - W->nexthop_list = linklist_create (); - W->path_list = list_new (); - W->parent_list = list_new (); - W->distance = V->distance + distance; - W->depth = V->depth + 1; - - inet_ntop (AF_INET, &W->vertex_id.adv_router.s_addr, - buf_router, sizeof (buf_router)); - inet_ntop (AF_INET, &W->vertex_id.id.s_addr, buf_id, sizeof (buf_id)); - snprintf (W->string, sizeof (W->string), "[%s-%s (%d)]", - buf_router, buf_id, W->distance); - - /* capability bits and optional capabilities */ - if (W->vertex_id.id.s_addr == 0) - { - router_lsa = (struct ospf6_router_lsa *) (W->lsa->header + 1); - W->capability_bits = router_lsa->bits; - memcpy (W->opt_capability, router_lsa->options, - sizeof (W->opt_capability)); - } - else - { - network_lsa = (struct ospf6_network_lsa *) (W->lsa->header + 1); - W->capability_bits = network_lsa->reserved; - memcpy (W->opt_capability, network_lsa->options, - sizeof (W->opt_capability)); - } - - /* Link to Parent node */ - listnode_add (W->parent_list, V); - - /* Nexthop Calculation */ - if (ospf6_spf_nexthop_calculation (W, ifindex, V, o6a->spf_tree) < 0) - return NULL; - - return W; -} - -static void -ospf6_spf_vertex_delete (struct ospf6_vertex *v) -{ - linklist_delete (v->nexthop_list); - list_delete (v->path_list); - list_delete (v->parent_list); - XFREE (MTYPE_OSPF6_VERTEX, v); -} - -static void -ospf6_spf_vertex_merge (struct ospf6_vertex *w, struct ospf6_vertex *x) -{ - listnode node; - struct linklist_node lnode; - - /* merge should be done on two nodes which are - almost the same */ - - /* these w and x should be both candidate. - candidate should not have any children */ - assert (list_isempty (w->path_list)); - assert (list_isempty (x->path_list)); - - /* merge parent list */ - for (node = listhead (w->parent_list); node; nextnode (node)) - { - if (listnode_lookup (x->parent_list, getdata (node))) - continue; - listnode_add (x->parent_list, getdata (node)); + char ibuf[16], abuf[16]; + inet_ntop (AF_INET, &id, ibuf, sizeof (ibuf)); + inet_ntop (AF_INET, &adv_router, abuf, sizeof (abuf)); + if (lsa) + zlog_info (" Link to: %s", lsa->name); + else + zlog_info (" Link to: [%s Id:%s Adv:%s] No LSA", + OSPF6_LSTYPE_NAME (type), ibuf, abuf); } - /* merge nexthop list */ - for (linklist_head (w->nexthop_list, &lnode); ! linklist_end (&lnode); - linklist_next (&lnode)) - linklist_add (lnode.data, x->nexthop_list); + return lsa; } -static void -ospf6_spf_initialize (list candidate_list, struct ospf6_area *o6a) +char * +ospf6_lsdesc_backlink (struct ospf6_lsa *lsa, + caddr_t lsdesc, struct ospf6_vertex *v) { - listnode node; - struct ospf6_vertex *v; - struct ospf6_lsa *lsa; - u_int16_t type; - u_int32_t id, adv_router; - struct linklist_node lnode; - - struct ospf6_nexthop *nexthop; - struct interface *ifp; - char buf_router[64], buf_id[64]; + caddr_t backlink, found = NULL; + int size; - /* delete topology routing table for this area */ - ospf6_route_remove_all (o6a->table_topology); - - /* Delete previous spf tree */ - for (node = listhead (o6a->spf_tree->list); node; nextnode (node)) + size = (OSPF6_LSA_IS_TYPE (ROUTER, lsa) ? + sizeof (struct ospf6_router_lsdesc) : + sizeof (struct ospf6_network_lsdesc)); + for (backlink = OSPF6_LSA_HEADER_END (lsa->header) + 4; + backlink + size <= OSPF6_LSA_END (lsa->header); backlink += size) { - v = (struct ospf6_vertex *) getdata (node); - ospf6_spf_vertex_delete (v); - } - list_delete_all_node (o6a->spf_tree->list); - - for (linklist_head (nexthop_list, &lnode); ! linklist_end (&lnode); - linklist_next (&lnode)) - XFREE (MTYPE_OSPF6_VERTEX, lnode.data); - linklist_remove_all (nexthop_list); + assert (! (OSPF6_LSA_IS_TYPE (NETWORK, lsa) && + VERTEX_IS_TYPE (NETWORK, v))); - /* Find self originated Router-LSA */ - type = htons (OSPF6_LSA_TYPE_ROUTER); - id = htonl (0); - adv_router = ospf6->router_id; - - lsa = ospf6_lsdb_lookup_lsdb (type, id, adv_router, o6a->lsdb); - - if (! lsa) - { - if (IS_OSPF6_DUMP_SPF) - zlog_info ("SPF: Can't find self originated Router-LSA"); - return; - } - if (IS_LSA_MAXAGE (lsa)) - { - zlog_err ("SPF: MaxAge self originated Router-LSA"); - return; - } - - /* Create root vertex */ - v = (struct ospf6_vertex *) XMALLOC (MTYPE_OSPF6_VERTEX, - sizeof (struct ospf6_vertex)); - if (! v) - { - zlog_err ("SPF: Can't allocate memory for root vertex"); - return; + if (OSPF6_LSA_IS_TYPE (NETWORK, lsa) && + NETWORK_LSDESC_GET_NBR_ROUTERID (backlink) + == v->lsa->header->adv_router) + found = backlink; + else if (VERTEX_IS_TYPE (NETWORK, v) && + ROUTER_LSDESC_IS_TYPE (TRANSIT_NETWORK, backlink) && + ROUTER_LSDESC_GET_NBR_ROUTERID (backlink) + == v->lsa->header->adv_router && + ROUTER_LSDESC_GET_NBR_IFID (backlink) + == ntohl (v->lsa->header->id)) + found = backlink; + else + { + if (! ROUTER_LSDESC_IS_TYPE (POINTTOPOINT, backlink) || + ! ROUTER_LSDESC_IS_TYPE (POINTTOPOINT, lsdesc)) + continue; + if (ROUTER_LSDESC_GET_NBR_IFID (backlink) != + ROUTER_LSDESC_GET_IFID (lsdesc) || + ROUTER_LSDESC_GET_NBR_IFID (lsdesc) != + ROUTER_LSDESC_GET_IFID (backlink)) + continue; + if (ROUTER_LSDESC_GET_NBR_ROUTERID (backlink) != + v->lsa->header->adv_router || + ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc) != + lsa->header->adv_router) + continue; + found = backlink; + } } - memset (v, 0, sizeof (struct ospf6_vertex)); - - v->vertex_id.family = AF_UNSPEC; /* XXX */ - v->vertex_id.prefixlen = 64; /* XXX */ - v->vertex_id.id.s_addr = htonl (0); - v->vertex_id.adv_router.s_addr = ospf6->router_id; - if (ospf6_is_asbr (ospf6)) - OSPF6_OPT_SET (v->opt_capability, OSPF6_OPT_E); - OSPF6_OPT_SET (v->opt_capability, OSPF6_OPT_V6); - OSPF6_OPT_SET (v->opt_capability, OSPF6_OPT_R); - v->nexthop_list = linklist_create (); - v->path_list = list_new (); - v->parent_list = list_new (); - v->distance = 0; - v->depth = 0; - v->lsa = lsa; - - inet_ntop (AF_INET, &v->vertex_id.adv_router.s_addr, - buf_router, sizeof (buf_router)); - inet_ntop (AF_INET, &v->vertex_id.id.s_addr, buf_id, sizeof (buf_id)); - snprintf (v->string, sizeof (v->string), "[%s-%s (%d)]", - buf_router, buf_id, v->distance); - nexthop = XCALLOC (MTYPE_OSPF6_VERTEX, sizeof (struct ospf6_nexthop)); - ifp = if_lookup_by_name ("lo0"); - if (ifp) - nexthop->ifindex = ifp->ifindex; - inet_pton (AF_INET6, "::1", &nexthop->address); - linklist_add (nexthop, v->nexthop_list); - linklist_add (nexthop, nexthop_list); + if (IS_OSPF6_DEBUG_SPF (DETAIL)) + zlog_info (" Backlink %s", (found ? "OK" : "FAIL")); - o6a->spf_tree->root = v; - listnode_add (candidate_list, v); - - ospf6_spf_candidate_enqueue (v); + return found; } -static struct ospf6_vertex * -ospf6_spf_get_closest_candidate (list candidate_list) +void +ospf6_nexthop_calc (struct ospf6_vertex *w, struct ospf6_vertex *v, + caddr_t lsdesc) { - listnode node; - struct ospf6_vertex *candidate, *closest; + int i, ifindex; + struct ospf6_interface *oi; + u_int16_t type; + u_int32_t adv_router; + struct ospf6_lsa *lsa; + struct ospf6_link_lsa *link_lsa; + char buf[64]; - closest = (struct ospf6_vertex *) NULL; - for (node = listhead (candidate_list); node; nextnode (node)) + assert (VERTEX_IS_TYPE (ROUTER, w)); + ifindex = (VERTEX_IS_TYPE (NETWORK, v) ? v->nexthop[0].ifindex : + ROUTER_LSDESC_GET_IFID (lsdesc)); + oi = ospf6_interface_lookup_by_ifindex (ifindex); + if (oi == NULL) { - candidate = (struct ospf6_vertex *) getdata (node); - - if (closest && candidate->distance > closest->distance) - continue; - - /* always choose network vertices if those're the same cost */ - if (closest && candidate->distance == closest->distance - && closest->vertex_id.id.s_addr != 0) - continue; - - closest = candidate; + if (IS_OSPF6_DEBUG_SPF (SUMMARY)) + zlog_warn ("Can't find interface in SPF: ifindex %d", ifindex); + return; } - return closest; -} + type = htons (OSPF6_LSTYPE_LINK); + adv_router = (VERTEX_IS_TYPE (NETWORK, v) ? + NETWORK_LSDESC_GET_NBR_ROUTERID (lsdesc) : + ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc)); -static struct ospf6_vertex * -ospf6_spf_get_same_candidate (struct ospf6_vertex *w, list candidate_list) -{ - listnode node; - struct ospf6_vertex *c, *same; - - same = (struct ospf6_vertex *) NULL; - for (node = listhead (candidate_list); node; nextnode (node)) + i = 0; + for (lsa = ospf6_lsdb_type_router_head (type, adv_router, oi->lsdb); lsa; + lsa = ospf6_lsdb_type_router_next (type, adv_router, lsa)) { - c = (struct ospf6_vertex *) getdata (node); - if (w->vertex_id.adv_router.s_addr != c->vertex_id.adv_router.s_addr) - continue; - if (w->vertex_id.id.s_addr != c->vertex_id.id.s_addr) + if (VERTEX_IS_TYPE (ROUTER, v) && + htonl (ROUTER_LSDESC_GET_NBR_IFID (lsdesc)) != lsa->header->id) continue; - if (same) - zlog_warn ("SPF: duplicate candidates in candidate_list"); + link_lsa = (struct ospf6_link_lsa *) OSPF6_LSA_HEADER_END (lsa->header); + if (IS_OSPF6_DEBUG_SPF (DETAIL)) + { + inet_ntop (AF_INET6, &link_lsa->linklocal_addr, buf, sizeof (buf)); + zlog_info (" nexthop %s from %s", buf, lsa->name); + } - same = c; + if (i < OSPF6_MULTI_PATH_LIMIT) + { + memcpy (&w->nexthop[i].address, &link_lsa->linklocal_addr, + sizeof (struct in6_addr)); + w->nexthop[i].ifindex = ifindex; + i++; + } } - return same; + if (i == 0 && IS_OSPF6_DEBUG_SPF (SUMMARY)) + zlog_info ("No nexthop for %s found", w->name); } -static void -ospf6_spf_install (struct ospf6_vertex *vertex, struct ospf6_area *o6a) +int +ospf6_spf_install (struct ospf6_vertex *v, + struct ospf6_route_table *result_table) { + struct ospf6_route *route; + int i, j; + struct ospf6_vertex *prev, *w; listnode node; - struct ospf6_vertex *parent; - struct ospf6_nexthop *nexthop; - struct ospf6_route_req request; - struct linklist_node lnode; - - struct ospf6_router_lsa *router_lsa; - struct ospf6_network_lsa *network_lsa; - router_lsa = OSPF6_LSA_HEADER_END (vertex->lsa->header); - network_lsa = OSPF6_LSA_HEADER_END (vertex->lsa->header); + if (IS_OSPF6_DEBUG_SPF (SUMMARY)) + zlog_info ("SPF install %s hops %d cost %d", + v->name, v->hops, v->cost); - if (IS_OSPF6_DUMP_SPF) + route = ospf6_route_lookup (&v->vertex_id, result_table); + if (route && route->path.cost < v->cost) { - zlog_info ("SPF: Install: %s", vertex->string); + if (IS_OSPF6_DEBUG_SPF (SUMMARY)) + zlog_info (" already installed with lower cost (%d), ignore", + route->path.cost); + ospf6_vertex_delete (v); + return -1; } - - listnode_add (o6a->spf_tree->list, vertex); - - for (node = listhead (vertex->parent_list); node; nextnode (node)) + else if (route && route->path.cost == v->cost) { - parent = (struct ospf6_vertex *) getdata (node); - listnode_add (parent->path_list, vertex); - vertex->depth = parent->depth + 1; - } + if (IS_OSPF6_DEBUG_SPF (SUMMARY)) + zlog_info (" another path found, merge"); -#if 0 - if (vertex == o6a->spf_tree->root) - return; -#endif /*0*/ + for (i = 0; ospf6_nexthop_is_set (&v->nexthop[i]) && + i < OSPF6_MULTI_PATH_LIMIT; i++) + { + for (j = 0; j < OSPF6_MULTI_PATH_LIMIT; j++) + { + if (ospf6_nexthop_is_set (&route->nexthop[j])) + { + if (ospf6_nexthop_is_same (&route->nexthop[j], + &v->nexthop[i])) + break; + else + continue; + } + ospf6_nexthop_copy (&route->nexthop[j], &v->nexthop[i]); + break; + } + } - /* install route to topology table */ - memset (&request, 0, sizeof (request)); - if (vertex->vertex_id.id.s_addr) /* xxx */ - request.route.type = OSPF6_DEST_TYPE_NETWORK; - else - request.route.type = OSPF6_DEST_TYPE_ROUTER; - memcpy (&request.route.prefix, &vertex->vertex_id, - sizeof (struct prefix)); - - request.path.area_id = o6a->area_id; - request.path.type = OSPF6_PATH_TYPE_INTRA; - request.path.cost = vertex->distance; - request.path.cost_e2 = 0; - request.path.origin.type = vertex->lsa->header->type; - request.path.origin.id = vertex->lsa->header->id; - request.path.origin.adv_router = vertex->lsa->header->adv_router; - if (vertex->lsa->header->type == htons (OSPF6_LSA_TYPE_ROUTER)) - request.path.router_bits = router_lsa->bits; - memcpy (&request.path.capability, vertex->opt_capability, - sizeof (request.path.capability)); - -#if 0 - if (IS_OSPF6_DUMP_SPF) - zlog_info ("SPF: install %d nexthops for %s", - listcount (vertex->nexthop_list), vertex->string); -#endif - - for (linklist_head (vertex->nexthop_list, &lnode); ! linklist_end (&lnode); - linklist_next (&lnode)) - { - nexthop = lnode.data; + prev = (struct ospf6_vertex *) route->route_option; + if (prev->hops > v->hops) + { + LIST_LOOP (prev->child_list, w, node) + { + assert (w->parent == prev); + w->parent = v; + listnode_add_sort (v->child_list, w); + } + listnode_delete (prev->parent->child_list, prev); + listnode_add_sort (v->parent->child_list, v); - request.nexthop.ifindex = nexthop->ifindex; - memcpy (&request.nexthop.address, &nexthop->address, - sizeof (request.nexthop.address)); + ospf6_vertex_delete (prev); + route->route_option = v; + } + else + ospf6_vertex_delete (v); - ospf6_route_add (&request, o6a->table_topology); + return -1; } + + /* There should be no case where candidate being installed (variable + "v") is closer than the one in the SPF tree (variable "route"). + In the case something's gone wrong with the behavior of + Priority-Queue. */ + assert (route == NULL); + + route = ospf6_route_create (); + memcpy (&route->prefix, &v->vertex_id, sizeof (struct prefix)); + route->type = OSPF6_DEST_TYPE_LINKSTATE; + route->path.type = OSPF6_PATH_TYPE_INTRA; + route->path.origin.type = v->lsa->header->type; + route->path.origin.id = v->lsa->header->id; + route->path.origin.adv_router = v->lsa->header->adv_router; + route->path.metric_type = 1; + route->path.cost = v->cost; + route->path.cost_e2 = v->hops; + route->path.router_bits = v->capability; + route->path.options[0] = v->options[0]; + route->path.options[1] = v->options[1]; + route->path.options[2] = v->options[2]; + + for (i = 0; ospf6_nexthop_is_set (&v->nexthop[i]) && + i < OSPF6_MULTI_PATH_LIMIT; i++) + ospf6_nexthop_copy (&route->nexthop[i], &v->nexthop[i]); + + if (v->parent) + listnode_add_sort (v->parent->child_list, v); + route->route_option = v; + + ospf6_route_add (route, result_table); + return 0; } -struct ospf6_vertex * -ospf6_spf_lookup (struct ospf6_vertex *w, struct ospf6_area *o6a) +void +ospf6_spf_table_finish (struct ospf6_route_table *result_table) { - listnode node; + struct ospf6_route *route; struct ospf6_vertex *v; - - for (node = listhead (o6a->spf_tree->list); node; nextnode (node)) + for (route = ospf6_route_head (result_table); route; + route = ospf6_route_next (route)) { - v = (struct ospf6_vertex *) getdata (node); - - if (w->vertex_id.adv_router.s_addr != v->vertex_id.adv_router.s_addr) - continue; - if (w->vertex_id.id.s_addr != v->vertex_id.id.s_addr) - continue; - - return v; + v = (struct ospf6_vertex *) route->route_option; + ospf6_vertex_delete (v); + ospf6_route_remove (route, result_table); } - - return (struct ospf6_vertex *) NULL; } -u_int32_t stat_node = 0; -u_int32_t stat_candidate = 0; -u_int32_t stat_candidate_max = 0; -u_int32_t stat_spf = 0; - - -/* RFC2328 section 16.1 , RFC2740 section 3.8.1 */ -static int -ospf6_spf_calculation (struct ospf6_area *o6a) -{ - list candidate_list; - struct ospf6_vertex *V, *W, *X; - int ldnum, i; - - if (! o6a || ! o6a->spf_tree) - { - zlog_err ("SPF: Can't calculate SPF tree: malformed area"); - return -1; - } +void +ospf6_spf_calculation (u_int32_t router_id, + struct ospf6_route_table *result_table, + struct ospf6_area *oa) +{ + struct pqueue *candidate_list; + struct ospf6_vertex *root, *v, *w; + int i; + int size; + caddr_t lsdesc; + struct ospf6_lsa *lsa; - stat_spf ++; - stat_node = 0; - stat_candidate = 0; - stat_candidate_max = 0; + /* initialize */ + candidate_list = pqueue_create (); + candidate_list->cmp = ospf6_vertex_cmp; - if (IS_OSPF6_DUMP_SPF) - zlog_info ("SPF: Calculation for area %s", o6a->str); + ospf6_spf_table_finish (result_table); - ospf6_route_table_freeze (o6a->table_topology); - ospf6_route_remove_all (o6a->table_topology); + /* Install the calculating router itself as the root of the SPF tree */ + /* construct root vertex */ + lsa = ospf6_lsdb_lookup (htons (OSPF6_LSTYPE_ROUTER), htonl (0), + router_id, oa->lsdb); + if (lsa == NULL) + return; + root = ospf6_vertex_create (lsa); + root->area = oa; + root->cost = 0; + root->hops = 0; + root->nexthop[0].ifindex = 0; /* should have been loopbak I/F ... */ + inet_pton (AF_INET6, "::1", &root->nexthop[0].address); - /* (1): Initialize the algorithm's data structures */ - candidate_list = list_new (); - ospf6_spf_initialize (candidate_list, o6a); - stat_candidate ++; + /* Actually insert root to the candidate-list as the only candidate */ + pqueue_enqueue (root, candidate_list); - /* (3): Install closest from candidate list; if empty, break */ - while (listcount (candidate_list)) + /* Iterate until candidate-list becomes empty */ + while (candidate_list->size) { - V = ospf6_spf_get_closest_candidate (candidate_list); - listnode_delete (candidate_list, V); - - { - struct ospf6_vertex *V_; - - if (stat_candidate_max < ospf6_spf_candidate_count ()) - stat_candidate_max = ospf6_spf_candidate_count (); - - V_ = ospf6_spf_candidate_dequeue (); + /* get closest candidate from priority queue */ + v = pqueue_dequeue (candidate_list); -#if 0 - if (IS_OSPF6_DUMP_SPF) - { - zlog_info ("Candidate list count: %lu", - (u_long)ospf6_spf_candidate_count ()); - zlog_info ("*** Candidate %s: %p <-> %p", - (V == V_ ? "same" : "*** differ ***"), V, V_); - zlog_info (" %p: %s", V, V->string); - zlog_info (" %p: %s", V_, V_->string); - } -#endif - - } - - stat_node++; - ospf6_spf_install (V, o6a); + /* install may result in merging and rejecting of the vertex */ + if (ospf6_spf_install (v, result_table) < 0) + continue; - /* (2): Examin LSA of just added vertex */ - ldnum = ospf6_spf_lsd_num (V, o6a); - for (i = 0; i < ldnum; i++) + /* For each LS description in the just-added vertex V's LSA */ + size = (VERTEX_IS_TYPE (ROUTER, v) ? + sizeof (struct ospf6_router_lsdesc) : + sizeof (struct ospf6_network_lsdesc)); + for (lsdesc = OSPF6_LSA_HEADER_END (v->lsa->header) + 4; + lsdesc + size <= OSPF6_LSA_END (v->lsa->header); lsdesc += size) { - /* (b): If no LSA, or MaxAge, or LinkBack fail, examin next */ - W = ospf6_spf_vertex_create (i, V, o6a); - if (! W) + lsa = ospf6_lsdesc_lsa (lsdesc, v); + if (lsa == NULL) continue; - stat_candidate ++; - - /* (c) */ - if (ospf6_spf_lookup (W, o6a)) - { - if (IS_OSPF6_DUMP_SPF) - zlog_info ("SPF: %s: Already in SPF tree", W->string); - ospf6_spf_vertex_delete (W); - continue; - } + if (! ospf6_lsdesc_backlink (lsa, lsdesc, v)) + continue; - /* (d) */ - X = ospf6_spf_get_same_candidate (W, candidate_list); - if (X && X->distance < W->distance) + w = ospf6_vertex_create (lsa); + w->area = oa; + w->parent = v; + if (VERTEX_IS_TYPE (ROUTER, v)) { - if (IS_OSPF6_DUMP_SPF) - zlog_info ("SPF: %s: More closer found", W->string); - ospf6_spf_vertex_delete (W); - continue; + w->cost = v->cost + ROUTER_LSDESC_GET_METRIC (lsdesc); + w->hops = v->hops + (VERTEX_IS_TYPE (NETWORK, w) ? 0 : 1); } - if (X && X->distance == W->distance) + else /* NETWORK */ { - if (IS_OSPF6_DUMP_SPF) - zlog_info ("SPF: %s: new ECMP candidate", W->string); - ospf6_spf_vertex_merge (W, X); - ospf6_spf_vertex_delete (W); - continue; + w->cost = v->cost; + w->hops = v->hops + 1; } - if (X) - { - if (IS_OSPF6_DUMP_SPF) - zlog_info ("SPF: %s: Swap with old candidate", W->string); - listnode_delete (candidate_list, X); - ospf6_spf_candidate_remove (X); - ospf6_spf_vertex_delete (X); - } + /* nexthop calculation */ + if (w->hops == 0) + w->nexthop[0].ifindex = ROUTER_LSDESC_GET_IFID (lsdesc); + else if (w->hops == 1 && v->hops == 0) + ospf6_nexthop_calc (w, v, lsdesc); else { - if (IS_OSPF6_DUMP_SPF) - zlog_info ("SPF: %s: New Candidate", W->string); + for (i = 0; ospf6_nexthop_is_set (&v->nexthop[i]) && + i < OSPF6_MULTI_PATH_LIMIT; i++) + ospf6_nexthop_copy (&w->nexthop[i], &v->nexthop[i]); } - if (stat_candidate_max < ospf6_spf_candidate_count ()) - stat_candidate_max = ospf6_spf_candidate_count (); - - listnode_add (candidate_list, W); - ospf6_spf_candidate_enqueue (W); + /* add new candidate to the candidate_list */ + if (IS_OSPF6_DEBUG_SPF (SUMMARY)) + zlog_info (" New candidate: %s hops %d cost %d", + w->name, w->hops, w->cost); + pqueue_enqueue (w, candidate_list); } } - assert (listcount (candidate_list) == 0); - list_free (candidate_list); - assert (ospf6_spf_candidate_count () == 0); - - /* Clear thread timer */ - o6a->spf_tree->t_spf_calculation = (struct thread *) NULL; - - if (IS_OSPF6_DUMP_SPF) - { - zlog_info ("SPF: Calculation for area %s done", o6a->str); - zlog_info ("SPF: Statistics: %luth", (u_long)stat_spf); - zlog_info ("SPF: Node Number: %lu", (u_long)stat_node); - zlog_info ("SPF: Candidate Number: %lu Max: %lu", - (u_long) stat_candidate, (u_long) stat_candidate_max); - } - - ospf6_route_table_thaw (o6a->table_topology); - return 0; + pqueue_delete (candidate_list); } int ospf6_spf_calculation_thread (struct thread *t) { - struct ospf6_area *o6a; - struct timeval start, end, runtime, interval; + struct ospf6_area *oa; + struct timeval start, end, runtime; - o6a = (struct ospf6_area *) THREAD_ARG (t); - if (! o6a) - { - zlog_err ("SPF: Thread error"); - return -1; - } + oa = (struct ospf6_area *) THREAD_ARG (t); + oa->thread_spf_calculation = NULL; - if (! o6a->spf_tree) - { - zlog_err ("SPF: Can't find SPF Tree for area: %s", o6a->str); - return -1; - } + if (IS_OSPF6_DEBUG_SPF (SUMMARY)) + zlog_info ("SPF calculation for area %s", oa->name); /* execute SPF calculation */ gettimeofday (&start, (struct timezone *) NULL); - ospf6_spf_calculation (o6a); + ospf6_spf_calculation (oa->ospf6->router_id, oa->spf_table, oa); gettimeofday (&end, (struct timezone *) NULL); - /* update statistics */ - o6a->spf_tree->timerun ++; - ospf6_timeval_sub (&end, &start, &runtime); - ospf6_timeval_add_equal (&runtime, &o6a->spf_tree->runtime_total); - - if (o6a->spf_tree->timerun == 1) - { - o6a->spf_tree->runtime_min.tv_sec = runtime.tv_sec; - o6a->spf_tree->runtime_min.tv_usec = runtime.tv_usec; - o6a->spf_tree->runtime_max.tv_sec = runtime.tv_sec; - o6a->spf_tree->runtime_max.tv_usec = runtime.tv_usec; - } - if (ospf6_timeval_cmp (o6a->spf_tree->runtime_min, runtime) > 0) + if (IS_OSPF6_DEBUG_SPF (SUMMARY)) { - o6a->spf_tree->runtime_min.tv_sec = runtime.tv_sec; - o6a->spf_tree->runtime_min.tv_usec = runtime.tv_usec; - } - if (ospf6_timeval_cmp (runtime, o6a->spf_tree->runtime_max) > 0) - { - o6a->spf_tree->runtime_max.tv_sec = runtime.tv_sec; - o6a->spf_tree->runtime_max.tv_usec = runtime.tv_usec; + timersub (&end, &start, &runtime); + zlog_info ("SPF calculation for area %s: runtime %ld sec %ld usec", + oa->name, runtime.tv_sec, runtime.tv_usec); } - if (o6a->spf_tree->timerun == 1) - { - ospf6_timeval_sub (&start, &ospf6->starttime, &interval); - ospf6_timeval_add_equal (&interval, &o6a->spf_tree->interval_total); - o6a->spf_tree->interval_min.tv_sec = interval.tv_sec; - o6a->spf_tree->interval_min.tv_usec = interval.tv_usec; - o6a->spf_tree->interval_max.tv_sec = interval.tv_sec; - o6a->spf_tree->interval_max.tv_usec = interval.tv_usec; - } - else - { - ospf6_timeval_sub (&start, &o6a->spf_tree->updated_time, &interval); - ospf6_timeval_add_equal (&interval, &o6a->spf_tree->interval_total); - if (ospf6_timeval_cmp (o6a->spf_tree->interval_min, interval) > 0) - { - o6a->spf_tree->interval_min.tv_sec = interval.tv_sec; - o6a->spf_tree->interval_min.tv_usec = interval.tv_usec; - } - if (ospf6_timeval_cmp (interval, o6a->spf_tree->interval_max) > 0) - { - o6a->spf_tree->interval_max.tv_sec = interval.tv_sec; - o6a->spf_tree->interval_max.tv_usec = interval.tv_usec; - } - } - o6a->spf_tree->updated_time.tv_sec = end.tv_sec; - o6a->spf_tree->updated_time.tv_usec = end.tv_usec; - - /* clear thread */ - o6a->spf_tree->t_spf_calculation = (struct thread *) NULL; + ospf6_intra_route_calculation (oa); + ospf6_intra_asbr_calculation (oa); return 0; } void -ospf6_spf_database_hook (struct ospf6_lsa *old, struct ospf6_lsa *new) -{ - struct ospf6_area *o6a = NULL; - struct ospf6_interface *o6i = NULL; - - if (new->header->type == htons (OSPF6_LSA_TYPE_ROUTER) || - new->header->type == htons (OSPF6_LSA_TYPE_NETWORK)) - o6a = new->scope; - else if (new->header->type == htons (OSPF6_LSA_TYPE_LINK)) - { - o6i = new->scope; - o6a = o6i->area; - } - - if (o6a) - ospf6_spf_calculation_schedule (o6a->area_id); -} - -void -ospf6_spf_calculation_schedule (u_int32_t area_id) +ospf6_spf_schedule (struct ospf6_area *oa) { - struct ospf6_area *o6a; - char buf[64]; - - o6a = ospf6_area_lookup (area_id, ospf6); - if (! o6a) - { - inet_ntop (AF_INET, &area_id, buf, sizeof (buf)); - zlog_err ("SPF: Can't find area: %s", buf); - return; - } - - if (! o6a->spf_tree) - { - zlog_err ("SPF: Can't find SPF Tree for area: %s", o6a->str); - return; - } - - if (o6a->spf_tree->t_spf_calculation) + if (oa->thread_spf_calculation) return; - - o6a->spf_tree->t_spf_calculation = - thread_add_event (master, ospf6_spf_calculation_thread, o6a, 0); -} - -struct ospf6_spftree * -ospf6_spftree_create () -{ - struct ospf6_spftree *spf_tree; - spf_tree = (struct ospf6_spftree *) XMALLOC (MTYPE_OSPF6_SPFTREE, - sizeof (struct ospf6_spftree)); - if (! spf_tree) - { - zlog_err ("SPF: Can't allocate memory for SPF tree"); - return (struct ospf6_spftree *) NULL; - } - memset (spf_tree, 0, sizeof (spf_tree)); - - spf_tree->list = list_new (); - - return spf_tree; + oa->thread_spf_calculation = + thread_add_event (master, ospf6_spf_calculation_thread, oa, 0); } void -ospf6_spftree_delete (struct ospf6_spftree *spf_tree) +ospf6_spf_display_subtree (struct vty *vty, char *prefix, int rest, + struct ospf6_vertex *v) { listnode node; - struct ospf6_vertex *v; - - /* Delete spf tree */ - for (node = listhead (spf_tree->list); node; nextnode (node)) - { - v = (struct ospf6_vertex *) getdata (node); - ospf6_spf_vertex_delete (v); - } - list_delete_all_node (spf_tree->list); - - XFREE (MTYPE_OSPF6_SPFTREE, spf_tree); -} - -void -ospf6_nexthop_show (struct vty *vty, struct ospf6_nexthop *nexthop) -{ - char buf[128], *ifname; - struct ospf6_interface *o6i; + struct ospf6_vertex *c; + char *next_prefix; + int len; + int restnum; - ifname = NULL; + /* "prefix" is the space prefix of the display line */ + vty_out (vty, "%s+-%s [%d]%s", prefix, v->name, v->cost, VTY_NEWLINE); - o6i = ospf6_interface_lookup_by_index (nexthop->ifindex); - if (! o6i) + len = strlen (prefix) + 4; + next_prefix = (char *) malloc (len); + if (next_prefix == NULL) { - zlog_err ("Spf: invalid ifindex %d in nexthop", nexthop->ifindex); - } - else - ifname = o6i->interface->name; - - inet_ntop (AF_INET6, &nexthop->address, buf, sizeof (buf)); - vty_out (vty, " %s%%%s(%d)%s", buf, ifname, - nexthop->ifindex, VTY_NEWLINE); -} - -void -ospf6_vertex_show (struct vty *vty, struct ospf6_vertex *vertex) -{ - listnode node; - struct ospf6_vertex *v; - struct linklist_node lnode; - - vty_out (vty, "SPF node %s%s", vertex->string, VTY_NEWLINE); - vty_out (vty, " cost to this node: %d%s", vertex->distance, VTY_NEWLINE); - vty_out (vty, " hops to this node: %d%s", vertex->depth, VTY_NEWLINE); - - vty_out (vty, " nexthops reachable to this node:%s", VTY_NEWLINE); - for (linklist_head (vertex->nexthop_list, &lnode); - ! linklist_end (&lnode); - linklist_next (&lnode)) - ospf6_nexthop_show (vty, (struct ospf6_nexthop *) lnode.data); - - vty_out (vty, " parent nodes to this node:%s", VTY_NEWLINE); - if (! list_isempty (vertex->parent_list)) - vty_out (vty, " "); - for (node = listhead (vertex->parent_list); node; nextnode (node)) - { - v = (struct ospf6_vertex *) getdata (node); - vty_out (vty, "%s ", v->string); + vty_out (vty, "malloc failed%s", VTY_NEWLINE); + return; } - if (! list_isempty (vertex->parent_list)) - vty_out (vty, "%s", VTY_NEWLINE); + snprintf (next_prefix, len, "%s%s", prefix, (rest ? "| " : " ")); - vty_out (vty, " child nodes to this node:%s", VTY_NEWLINE); - if (! list_isempty (vertex->path_list)) - vty_out (vty, " "); - for (node = listhead (vertex->path_list); node; nextnode (node)) + restnum = listcount (v->child_list); + LIST_LOOP (v->child_list, c, node) { - v = (struct ospf6_vertex *) getdata (node); - vty_out (vty, "%s ", v->string); + restnum--; + ospf6_spf_display_subtree (vty, next_prefix, restnum, c); } - if (! list_isempty (vertex->path_list)) - vty_out (vty, "%s", VTY_NEWLINE); - vty_out (vty, "%s", VTY_NEWLINE); + free (next_prefix); } -void -ospf6_spf_statistics_show (struct vty *vty, struct ospf6_spftree *spf_tree) +DEFUN (debug_ospf6_spf_detail, + debug_ospf6_spf_detail_cmd, + "debug ospf6 spf detail", + DEBUG_STR + OSPF6_STR + "Debug SPF Calculation\n" + "Debug Detailed SPF\n" + ) { - listnode node; - struct ospf6_vertex *vertex; - u_int router_count, network_count, maxdepth; - struct timeval runtime_avg, interval_avg, last_updated, now; - char rmin[64], rmax[64], ravg[64]; - char imin[64], imax[64], iavg[64]; - char last_updated_string[64]; - - maxdepth = router_count = network_count = 0; - for (node = listhead (spf_tree->list); node; nextnode (node)) - { - vertex = (struct ospf6_vertex *) getdata (node); - if (vertex->vertex_id.id.s_addr) - network_count++; - else - router_count++; - if (maxdepth < vertex->depth) - maxdepth = vertex->depth; - } - - ospf6_timeval_div (&spf_tree->runtime_total, spf_tree->timerun, - &runtime_avg); - ospf6_timeval_string (&spf_tree->runtime_min, rmin, sizeof (rmin)); - ospf6_timeval_string (&spf_tree->runtime_max, rmax, sizeof (rmax)); - ospf6_timeval_string (&runtime_avg, ravg, sizeof (ravg)); - - ospf6_timeval_div (&spf_tree->interval_total, spf_tree->timerun, - &interval_avg); - ospf6_timeval_string (&spf_tree->interval_min, imin, sizeof (imin)); - ospf6_timeval_string (&spf_tree->interval_max, imax, sizeof (imax)); - ospf6_timeval_string (&interval_avg, iavg, sizeof (iavg)); - - gettimeofday (&now, (struct timezone *) NULL); - ospf6_timeval_sub (&now, &spf_tree->updated_time, &last_updated); - ospf6_timeval_string (&last_updated, last_updated_string, - sizeof (last_updated_string)); - - vty_out (vty, " SPF algorithm executed %d times%s", - spf_tree->timerun, VTY_NEWLINE); - vty_out (vty, " Average time to run SPF: %s%s", - ravg, VTY_NEWLINE); - vty_out (vty, " Maximum time to run SPF: %s%s", - rmax, VTY_NEWLINE); - vty_out (vty, " Average interval of SPF: %s%s", - iavg, VTY_NEWLINE); - vty_out (vty, " SPF last updated: %s ago%s", - last_updated_string, VTY_NEWLINE); - vty_out (vty, " Current SPF node count: %d%s", - listcount (spf_tree->list), VTY_NEWLINE); - vty_out (vty, " Router: %d Network: %d%s", - router_count, network_count, VTY_NEWLINE); - vty_out (vty, " Maximum of Hop count to nodes: %d%s", - maxdepth, VTY_NEWLINE); + unsigned char level = 0; + level = OSPF6_DEBUG_SPF_SUMMARY | OSPF6_DEBUG_SPF_DETAIL; + OSPF6_DEBUG_SPF_ON (level); + return CMD_SUCCESS; } -DEFUN (show_ipv6_ospf6_area_spf_node, - show_ipv6_ospf6_area_spf_node_cmd, - "show ipv6 ospf6 area A.B.C.D spf node", - SHOW_STR - IP6_STR +DEFUN (debug_ospf6_spf, + debug_ospf6_spf_cmd, + "debug ospf6 spf", + DEBUG_STR OSPF6_STR - OSPF6_AREA_STR - OSPF6_AREA_ID_STR - "Shortest Path First caculation\n" - "vertex infomation\n" - ) + "Debug SPF Calculation\n" + ) { - listnode i; - u_int32_t area_id; - struct ospf6_area *o6a; - struct ospf6_vertex *vertex; - - OSPF6_CMD_CHECK_RUNNING (); - - inet_pton (AF_INET, argv[0], &area_id); - o6a = ospf6_area_lookup (area_id, ospf6); - if (! o6a) - return CMD_SUCCESS; - - for (i = listhead (o6a->spf_tree->list); i; nextnode (i)) - { - vertex = (struct ospf6_vertex *) getdata (i); - ospf6_vertex_show (vty, vertex); - } - + unsigned char level = 0; + level = OSPF6_DEBUG_SPF_SUMMARY; + OSPF6_DEBUG_SPF_ON (level); return CMD_SUCCESS; } -static void -ospf6_spftree_show (struct vty *vty, char *prefix, int current_rest, - struct ospf6_vertex *v) +DEFUN (no_debug_ospf6_spf_detail, + no_debug_ospf6_spf_detail_cmd, + "no debug ospf6 spf detail", + NO_STR + DEBUG_STR + OSPF6_STR + "Quit Debugging SPF Calculation\n" + "Quit Debugging Detailed SPF (change to debug summary)\n" + ) { - char *p; - int psize; - int restnum; - listnode node; - - vty_out (vty, "%s+-%s%s", prefix, v->string, VTY_NEWLINE); - - if (listcount (v->path_list) == 0) - return; - - psize = strlen (prefix) + 3; - p = malloc (psize); - if (!p) - { - vty_out (vty, "depth too long ...%s", VTY_NEWLINE); - return; - } - - restnum = listcount (v->path_list); - for (node = listhead (v->path_list); node; nextnode (node)) - { - --restnum; - snprintf (p, psize, "%s%s", prefix, (current_rest ? "| " : " ")); - ospf6_spftree_show (vty, p, restnum, - (struct ospf6_vertex *) getdata (node)); - } - - free (p); + unsigned char level = 0; + level = OSPF6_DEBUG_SPF_DETAIL; + OSPF6_DEBUG_SPF_OFF (level); + return CMD_SUCCESS; } -DEFUN (show_ipv6_ospf6_area_spf_tree, - show_ipv6_ospf6_area_spf_tree_cmd, - "show ipv6 ospf6 area A.B.C.D spf tree", - SHOW_STR - IP6_STR +DEFUN (no_debug_ospf6_spf, + no_debug_ospf6_spf_cmd, + "no debug ospf6 spf", + NO_STR + DEBUG_STR OSPF6_STR - OSPF6_AREA_STR - OSPF6_AREA_ID_STR - "Shortest Path First caculation\n" - "Displays spf tree\n") + "Quit Debugging SPF Calculation\n" + ) { - u_int32_t area_id; - struct ospf6_area *o6a; - - OSPF6_CMD_CHECK_RUNNING (); - - inet_pton (AF_INET, argv[0], &area_id); - o6a = ospf6_area_lookup (area_id, ospf6); - if (! o6a) - return CMD_SUCCESS; - - vty_out (vty, "%s SPF tree for Area %s%s%s", - VTY_NEWLINE, o6a->str, VTY_NEWLINE, VTY_NEWLINE); - - if (! o6a->spf_tree->root) - return CMD_SUCCESS; - - ospf6_spftree_show (vty, "", 0, o6a->spf_tree->root); + unsigned char level = 0; + level = OSPF6_DEBUG_SPF_SUMMARY | OSPF6_DEBUG_SPF_DETAIL; + OSPF6_DEBUG_SPF_OFF (level); return CMD_SUCCESS; } -DEFUN (show_ipv6_ospf6_area_topology, - show_ipv6_ospf6_area_topology_cmd, - "show ipv6 ospf6 area A.B.C.D topology", - SHOW_STR - IP6_STR - OSPF6_STR - OSPF6_AREA_STR - OSPF6_AREA_ID_STR - OSPF6_SPF_STR - "Displays SPF topology table\n") +int +config_write_ospf6_debug_spf (struct vty *vty) { - struct ospf6_area *o6a; - u_int32_t area_id; - - OSPF6_CMD_CHECK_RUNNING (); - - inet_pton (AF_INET, argv[0], &area_id); - o6a = ospf6_area_lookup (area_id, ospf6); - - if (! o6a) - return CMD_SUCCESS; - - argc -= 1; - argv += 1; - - return ospf6_route_table_show (vty, argc, argv, o6a->table_topology); + if (IS_OSPF6_DEBUG_SPF (DETAIL)) + vty_out (vty, "debug ospf6 spf detail%s", VTY_NEWLINE); + else if (IS_OSPF6_DEBUG_SPF (SUMMARY)) + vty_out (vty, "debug ospf6 spf%s", VTY_NEWLINE); + return 0; } -ALIAS (show_ipv6_ospf6_area_topology, - show_ipv6_ospf6_area_topology_router_cmd, - "show ipv6 ospf6 area A.B.C.D topology (A.B.C.D|<0-4294967295>|detail)", - SHOW_STR - IP6_STR - OSPF6_STR - OSPF6_AREA_STR - OSPF6_AREA_ID_STR - OSPF6_SPF_STR - "Displays SPF topology table\n" - OSPF6_ROUTER_ID_STR - OSPF6_ROUTER_ID_STR - ) - -ALIAS (show_ipv6_ospf6_area_topology, - show_ipv6_ospf6_area_topology_router_lsid_cmd, - "show ipv6 ospf6 area A.B.C.D topology (A.B.C.D|<0-4294967295>) (A.B.C.D|<0-4294967295>)", - SHOW_STR - IP6_STR - OSPF6_STR - OSPF6_AREA_STR - OSPF6_AREA_ID_STR - OSPF6_SPF_STR - "Displays SPF topology table\n" - OSPF6_ROUTER_ID_STR - OSPF6_ROUTER_ID_STR - OSPF6_LS_ID_STR - OSPF6_LS_ID_STR - ) +void +install_element_ospf6_debug_spf () +{ + install_element (ENABLE_NODE, &debug_ospf6_spf_cmd); + install_element (ENABLE_NODE, &debug_ospf6_spf_detail_cmd); + install_element (ENABLE_NODE, &no_debug_ospf6_spf_cmd); + install_element (ENABLE_NODE, &no_debug_ospf6_spf_detail_cmd); + install_element (CONFIG_NODE, &debug_ospf6_spf_cmd); + install_element (CONFIG_NODE, &debug_ospf6_spf_detail_cmd); + install_element (CONFIG_NODE, &no_debug_ospf6_spf_cmd); + install_element (CONFIG_NODE, &no_debug_ospf6_spf_detail_cmd); +} void ospf6_spf_init () { - nexthop_list = linklist_create (); - ospf6_spf_candidate_init (); - install_element (VIEW_NODE, &show_ipv6_ospf6_area_spf_node_cmd); - install_element (VIEW_NODE, &show_ipv6_ospf6_area_spf_tree_cmd); - install_element (VIEW_NODE, &show_ipv6_ospf6_area_topology_cmd); - install_element (VIEW_NODE, &show_ipv6_ospf6_area_topology_router_cmd); - install_element (VIEW_NODE, &show_ipv6_ospf6_area_topology_router_lsid_cmd); - install_element (ENABLE_NODE, &show_ipv6_ospf6_area_spf_node_cmd); - install_element (ENABLE_NODE, &show_ipv6_ospf6_area_spf_tree_cmd); - install_element (ENABLE_NODE, &show_ipv6_ospf6_area_topology_cmd); - install_element (ENABLE_NODE, &show_ipv6_ospf6_area_topology_router_cmd); - install_element (ENABLE_NODE, &show_ipv6_ospf6_area_topology_router_lsid_cmd); } + |