/* 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 GNU Zebra; see the file COPYING. If not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ #include #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 "pqueue.h" #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" static void ospf_vertex_free (void *); /* List of allocated vertices, to simplify cleanup of SPF. * Not thread-safe obviously. If it ever needs to be, it'd have to be * dynamically allocated at begin of ospf_spf_calculate */ static struct list vertex_list = { .del = ospf_vertex_free }; /* Heap related functions, for the managment of the candidates, to * be used with pqueue. */ static int cmp (void * node1 , void * node2) { struct vertex * v1 = (struct vertex *) node1; struct vertex * v2 = (struct vertex *) node2; if (v1 != NULL && v2 != NULL ) { /* network vertices must be chosen before router vertices of same * cost in order to find all shortest paths */ if ( ((v1->distance - v2->distance) == 0) && (v1->type != v2->type)) { switch (v1->type) { case OSPF_VERTEX_NETWORK: return -1; case OSPF_VERTEX_ROUTER: return 1; } } else return (v1->distance - v2->distance); } return 0; } static void update_stat (void *node , int position) { struct vertex *v = node; /* Set the status of the vertex, when its position changes. */ *(v->stat) = position; } 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); } } /* TODO: Parent list should be excised, in favour of maintaining only * vertex_nexthop, with refcounts. */ static struct vertex_parent * vertex_parent_new (struct vertex *v, int backlink, struct vertex_nexthop *hop) { struct vertex_parent *new; new = XMALLOC (MTYPE_OSPF_VERTEX_PARENT, sizeof (struct vertex_parent)); if (new == NULL) return NULL; new->parent = v; new->backlink = backlink; new->nexthop = hop; return new; } static void vertex_parent_free (void *p) { XFREE (MTYPE_OSPF_VERTEX_PARENT, p); } static struct vertex * ospf_vertex_new (struct ospf_lsa *lsa) { struct vertex *new; new = XCALLOC (MTYPE_OSPF_VERTEX, sizeof (struct vertex)); new->flags = 0; new->stat = &(lsa->stat); 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; listnode_add (&vertex_list, new); if (IS_DEBUG_OSPF_EVENT) zlog_debug ("%s: Created %s vertex %s", __func__, new->type == OSPF_VERTEX_ROUTER ? "Router" : "Network", inet_ntoa (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 %s", __func__, v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network", inet_ntoa (v->lsa->id)); /* There should be no parents potentially holding references to this vertex * Children however may still be there, but presumably referenced by other * vertices */ //assert (listcount (v->parents) == 0); if (v->children) list_delete (v->children); v->children = NULL; if (v->parents) list_delete (v->parents); v->parents = NULL; 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 %s distance %u flags %u", msg, v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network", inet_ntoa(v->lsa->id), v->distance, (unsigned int)v->flags); if (print_parents) { struct listnode *node; struct vertex_parent *vp; for (ALL_LIST_ELEMENTS_RO (v->parents, node, vp)) { char buf1[BUFSIZ]; if (vp) { zlog_debug ("parent %s backlink %d nexthop %s interface %s", inet_ntoa(vp->parent->lsa->id), vp->backlink, inet_ntop(AF_INET, &vp->nexthop->router, buf1, BUFSIZ), vp->nexthop->oi ? IF_NAME(vp->nexthop->oi) : "NULL"); } } } if (print_children) { struct listnode *cnode; struct vertex *cv; for (ALL_LIST_ELEMENTS_RO (v->children, cnode, cv)) ospf_vertex_dump(" child:", cv, 0, 0); } } /* Add a vertex to the list of children in each of its parents. */ static void ospf_vertex_add_parent (struct vertex *v) { struct vertex_parent *vp; struct listnode *node; assert (v && v->parents); for (ALL_LIST_ELEMENTS_RO (v->parents, node, vp)) { assert (vp->parent && vp->parent->children); /* No need to add two links from the same parent. */ if (listnode_lookup (vp->parent->children, v) == NULL) listnode_add (vp->parent->children, v); } } static void ospf_spf_init (struct ospf_area *area) { struct vertex *v; /* Create root node. */ v = ospf_vertex_new (area->router_lsa_self); area->spf = v; /* 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; } #define ROUTER_LSA_MIN_SIZE 12 #define ROUTER_LSA_TOS_SIZE 4 /* 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) { u_char *p; u_char *lim; struct router_lsa_link *l; if (prev_link == NULL) p = ((u_char *) v->lsa) + OSPF_LSA_HEADER_SIZE + 4; else { p = (u_char *) prev_link; p += (ROUTER_LSA_MIN_SIZE + (prev_link->m[0].tos_count * ROUTER_LSA_TOS_SIZE)); } lim = ((u_char *) v->lsa) + ntohs (v->lsa->length); while (p < lim) { l = (struct router_lsa_link *) p; p += (ROUTER_LSA_MIN_SIZE + (l->m[0].tos_count * ROUTER_LSA_TOS_SIZE)); if (l->m[0].type == LSA_LINK_TYPE_STUB) continue; /* Defer NH calculation via VLs until summaries from transit areas area confidered */ if (l->m[0].type == LSA_LINK_TYPE_VIRTUALLINK) continue; if (IPV4_ADDR_SAME (&l->link_id, &w->id)) return l; } return NULL; } static void ospf_spf_flush_parents (struct vertex *w) { struct vertex_parent *vp; struct listnode *ln, *nn; /* delete the existing nexthops */ for (ALL_LIST_ELEMENTS (w->parents, ln, nn, vp)) { list_delete_node (w->parents, ln); vertex_parent_free (vp); } } /* * Consider supplied next-hop for inclusion to the supplied list of * equal-cost next-hops, adjust list as neccessary. */ static void ospf_spf_add_parent (struct vertex *v, struct vertex *w, struct vertex_nexthop *newhop, unsigned int distance) { struct vertex_parent *vp; /* we must have a newhop, and a distance */ assert (v && w && newhop); assert (distance); /* IFF w has already been assigned a distance, then we shouldn't get here * unless callers have determined V(l)->W is shortest / equal-shortest * path (0 is a special case distance (no distance yet assigned)). */ if (w->distance) assert (distance <= w->distance); else w->distance = distance; if (IS_DEBUG_OSPF_EVENT) { char buf[2][INET_ADDRSTRLEN]; zlog_debug ("%s: Adding %s as parent of %s", __func__, inet_ntop(AF_INET, &v->lsa->id, buf[0], sizeof(buf[0])), inet_ntop(AF_INET, &w->lsa->id, buf[1], sizeof(buf[1]))); } /* Adding parent for a new, better path: flush existing parents from W. */ if (distance < w->distance) { if (IS_DEBUG_OSPF_EVENT) zlog_debug ("%s: distance %d better than %d, flushing existing parents", __func__, distance, w->distance); ospf_spf_flush_parents (w); w->distance = distance; } /* new parent is <= existing parents, add it to parent list */ vp = vertex_parent_new (v, ospf_lsa_has_link (w->lsa, v->lsa), newhop); listnode_add (w->parents, vp); return; } /* 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) { struct listnode *node, *nnode; struct vertex_nexthop *nh; struct vertex_parent *vp; struct ospf_interface *oi = NULL; 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. */ 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; /* we *must* be supplied with the link data */ assert (l != NULL); if (IS_DEBUG_OSPF_EVENT) { char buf1[BUFSIZ]; char buf2[BUFSIZ]; zlog_debug("ospf_nexthop_calculation(): considering link " "type %d link_id %s link_data %s", l->m[0].type, inet_ntop (AF_INET, &l->link_id, buf1, BUFSIZ), inet_ntop (AF_INET, &l->link_data, buf2, BUFSIZ)); } if (l->m[0].type == LSA_LINK_TYPE_POINTOPOINT) { /* 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"). Find the local interface associated with l (its address is in l->link_data). 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. */ oi = ospf_if_is_configured (area->ospf, &l->link_data); 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) /* link_data is on our PtMP network */ break; } } /* end l is on point-to-multipoint link */ else { /* l is a regular point-to-point link. Look for a link from W to V. */ while ((l2 = ospf_get_next_link (w, v, l2))) { oi = ospf_if_is_configured (area->ospf, &(l2->link_data)); if (oi == NULL) continue; if (!IPV4_ADDR_SAME (&oi->address->u.prefix4, &l->link_data)) continue; break; } } if (oi && l2) { /* found all necessary info to build nexthop */ nh = vertex_nexthop_new (); nh->oi = oi; nh->router = l2->link_data; ospf_spf_add_parent (v, w, nh, distance); return 1; } else zlog_info("ospf_nexthop_calculation(): " "could not determine nexthop for link"); } /* end point-to-point link from V to W */ else if (l->m[0].type == LSA_LINK_TYPE_VIRTUALLINK) { struct ospf_vl_data *vl_data; /* VLink implementation limitations: * a) vl_data can only reference one nexthop, so no ECMP * to backbone through VLinks. Though transit-area * summaries may be considered, and those can be ECMP. * b) We can only use /one/ VLink, even if multiple ones * exist this router through multiple transit-areas. */ 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->oi = vl_data->nexthop.oi; nh->router = vl_data->nexthop.router; ospf_spf_add_parent (v, w, nh, distance); return 1; } else zlog_info("ospf_nexthop_calculation(): " "vl_data for VL link not found"); } /* end virtual-link from V to W */ return 0; } /* end W is a Router vertex */ else { assert(w->type == OSPF_VERTEX_NETWORK); oi = ospf_if_is_configured (area->ospf, &(l->link_data)); if (oi) { nh = vertex_nexthop_new (); nh->oi = oi; nh->router.s_addr = 0; ospf_spf_add_parent (v, w, nh, distance); return 1; } } zlog_info("ospf_nexthop_calculation(): " "Unknown attached link"); return 0; } /* 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) /* connects to root? */ { /* 16.1.1 para 5. ...the parent vertex is a network that * directly connects the calculating router to the destination * router. The list of next hops is then determined by * examining the destination's router-LSA... */ 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->oi = vp->nexthop->oi; nh->router = l->link_data; added = 1; ospf_spf_add_parent (v, w, nh, distance); } } } if (added) return added; } /* 16.1.1 para 4. If there is at least one intervening router in the * current shortest path between the destination and the root, the * destination simply inherits the set of next hops from the * parent. */ if (IS_DEBUG_OSPF_EVENT) zlog_debug ("%s: Intervening routers, adding parent(s)", __func__); for (ALL_LIST_ELEMENTS (v->parents, node, nnode, vp)) { added = 1; ospf_spf_add_parent (v, w, vp->nexthop, distance); } return added; } /* RFC2328 Section 16.1 (2). * v is on the SPF tree. Examine the links in v's LSA. Update the list * of candidates with any vertices not already on the list. If a lower-cost * path is found to a vertex already on the candidate list, store the new cost. */ static void ospf_spf_next (struct vertex *v, struct ospf_area *area, struct pqueue * candidate) { struct ospf_lsa *w_lsa = NULL; u_char *p; u_char *lim; struct router_lsa_link *l = NULL; struct in_addr *r; int type = 0; /* If this is a router-LSA, and bit V of the router-LSA (see Section A.4.2:RFC2328) is set, set Area A's TransitCapability to TRUE. */ if (v->type == OSPF_VERTEX_ROUTER) { if (IS_ROUTER_LSA_VIRTUAL ((struct router_lsa *) v->lsa)) area->transit = OSPF_TRANSIT_TRUE; } if (IS_DEBUG_OSPF_EVENT) zlog_debug ("%s: Next vertex of %s vertex %s", __func__, v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network", inet_ntoa(v->lsa->id)); p = ((u_char *) v->lsa) + OSPF_LSA_HEADER_SIZE + 4; lim = ((u_char *) 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; p += (ROUTER_LSA_MIN_SIZE + (l->m[0].tos_count * 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; /* Infinite distance links shouldn't be followed, except * for local links (a stub-routed router still wants to * calculate tree, so must follow its own links). */ if ((v != area->spf) && l->m[0].metric >= OSPF_OUTPUT_COST_INFINITE) 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) { if (IS_DEBUG_OSPF_EVENT) zlog_debug ("looking up LSA through VL: %s", inet_ntoa (l->link_id)); } w_lsa = ospf_lsa_lookup (area, OSPF_ROUTER_LSA, l->link_id, l->link_id); if (w_lsa) { if (IS_DEBUG_OSPF_EVENT) zlog_debug ("found Router LSA %s", inet_ntoa (l->link_id)); } break; case LSA_LINK_TYPE_TRANSIT: if (IS_DEBUG_OSPF_EVENT) zlog_debug ("Looking up Network LSA, ID: %s", inet_ntoa (l->link_id)); w_lsa = ospf_lsa_lookup_by_id (area, OSPF_NETWORK_LSA, l->link_id); if (w_lsa) if (IS_DEBUG_OSPF_EVENT) zlog_debug ("found the LSA"); break; default: zlog_warn ("Invalid LSA link type %d", type); continue; } } 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) { if (IS_DEBUG_OSPF_EVENT) zlog_debug ("found Router LSA %s", inet_ntoa (w_lsa->data->id)); } } /* (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. */ if (v->lsa->type == OSPF_ROUTER_LSA) distance = v->distance + ntohs (l->m[0].metric); else /* v is not a Router-LSA */ distance = v->distance; /* Is there already vertex W in candidate list? */ if (w_lsa->stat == LSA_SPF_NOT_EXPLORED) { /* prepare vertex W. */ w = ospf_vertex_new (w_lsa); /* Calculate nexthop to W. */ if (ospf_nexthop_calculation (area, v, w, l, distance)) pqueue_enqueue (w, candidate); else if (IS_DEBUG_OSPF_EVENT) zlog_debug ("Nexthop Calc failed"); } else if (w_lsa->stat >= 0) { /* Get the vertex from candidates. */ w = candidate->array[w_lsa->stat]; /* if D is greater than. */ if (w->distance < distance) { continue; } /* equal to. */ else if (w->distance == distance) { /* Found an equal-cost path to W. * Calculate nexthop of to W from V. */ ospf_nexthop_calculation (area, v, w, l, distance); } /* less than. */ 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 */ if (ospf_nexthop_calculation (area, v, w, l, distance)) /* Decrease the key of the node in the heap. * trickle-sort it up towards root, just in case this * node should now be the new root due the cost change. * (next pqueu_{de,en}queue will fully re-heap the queue). */ trickle_up (w_lsa->stat, candidate); } } /* 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] %s", i, inet_ntoa (v->lsa->id)); } else { struct network_lsa *lsa = (struct network_lsa *) v->lsa; if (IS_DEBUG_OSPF_EVENT) zlog_debug ("SPF Result: %d [N] %s/%d", i, inet_ntoa (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 %s %s", parent->nexthop, inet_ntoa (parent->nexthop->router), parent->nexthop->oi ? IF_NAME(parent->nexthop->oi) : "NULL"); } i++; for (ALL_LIST_ELEMENTS_RO (v->children, cnode, v)) ospf_spf_dump (v, i); } /* Second stage of SPF calculation. */ static void ospf_spf_process_stubs (struct ospf_area *area, struct vertex *v, struct route_table *rt) { struct listnode *cnode, *cnnode; struct vertex *child; if (IS_DEBUG_OSPF_EVENT) zlog_debug ("ospf_process_stub():processing stubs for area %s", inet_ntoa (area->area_id)); if (v->type == OSPF_VERTEX_ROUTER) { u_char *p; u_char *lim; struct router_lsa_link *l; struct router_lsa *rlsa; if (IS_DEBUG_OSPF_EVENT) zlog_debug ("ospf_process_stubs():processing router LSA, id: %s", inet_ntoa (v->lsa->id)); rlsa = (struct router_lsa *) v->lsa; if (IS_DEBUG_OSPF_EVENT) zlog_debug ("ospf_process_stubs(): we have %d links to process", ntohs (rlsa->links)); p = ((u_char *) v->lsa) + OSPF_LSA_HEADER_SIZE + 4; lim = ((u_char *) v->lsa) + ntohs (v->lsa->length); while (p < lim) { l = (struct router_lsa_link *) p; p += (ROUTER_LSA_MIN_SIZE + (l->m[0].tos_count * ROUTER_LSA_TOS_SIZE)); if (l->m[0].type == LSA_LINK_TYPE_STUB) { /* PtP links with /32 masks adds host routes to the remote host, see RFC 2328, 12.4.1.1, Option 1. Make sure that such routes are ignored */ /* XXX: Change to breadth-first and avoid the lookup */ if (l->link_data.s_addr == 0xffffffff && ospf_if_lookup_by_local_addr (area->ospf, NULL, l->link_id)) { if (IS_DEBUG_OSPF_EVENT) zlog_debug ("ospf_spf_process_stubs(): ignoring host route " "%s/32 to self.", inet_ntoa (l->link_id)); continue; } ospf_intra_add_stub (rt, l, v, area); } } } 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; ospf_spf_process_stubs (area, child, rt); 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); } static void ospf_rtrs_print (struct route_table *rtrs) { struct route_node *rn; struct list *or_list; struct listnode *ln; struct listnode *pnode; struct ospf_route *or; struct ospf_path *path; char buf1[BUFSIZ]; char buf2[BUFSIZ]; if (IS_DEBUG_OSPF_EVENT) zlog_debug ("ospf_rtrs_print() start"); for (rn = route_top (rtrs); rn; rn = route_next (rn)) if ((or_list = rn->info) != NULL) for (ALL_LIST_ELEMENTS_RO (or_list, ln, or)) { switch (or->path_type) { case OSPF_PATH_INTRA_AREA: if (IS_DEBUG_OSPF_EVENT) zlog_debug ("%s [%d] area: %s", inet_ntop (AF_INET, &or->id, buf1, BUFSIZ), or->cost, inet_ntop (AF_INET, &or->u.std.area_id, buf2, BUFSIZ)); break; case OSPF_PATH_INTER_AREA: if (IS_DEBUG_OSPF_EVENT) zlog_debug ("%s IA [%d] area: %s", inet_ntop (AF_INET, &or->id, buf1, BUFSIZ), or->cost, inet_ntop (AF_INET, &or->u.std.area_id, buf2, BUFSIZ)); break; default: break; } for (ALL_LIST_ELEMENTS_RO (or->paths, pnode, path)) { if (path->nexthop.s_addr == 0) { if (IS_DEBUG_OSPF_EVENT) zlog_debug (" directly attached to %s\r\n", IF_NAME (path->oi)); } else { if (IS_DEBUG_OSPF_EVENT) zlog_debug (" via %s, %s\r\n", inet_ntoa (path->nexthop), IF_NAME (path->oi)); } } } zlog_debug ("ospf_rtrs_print() end"); } /* Calculating the shortest-path tree for an area. */ static void ospf_spf_calculate (struct ospf_area *area, struct route_table *new_table, struct route_table *new_rtrs) { struct pqueue *candidate; struct vertex *v; if (IS_DEBUG_OSPF_EVENT) { zlog_debug ("ospf_spf_calculate: Start"); zlog_debug ("ospf_spf_calculate: running Dijkstra for area %s", inet_ntoa (area->area_id)); } /* Check router-lsa-self. If self-router-lsa is not yet allocated, return this area's calculation. */ if (!area->router_lsa_self) { if (IS_DEBUG_OSPF_EVENT) zlog_debug ("ospf_spf_calculate: " "Skip area %s's calculation due to empty router_lsa_self", inet_ntoa (area->area_id)); return; } /* RFC2328 16.1. (1). */ /* Initialize the algorithm's data structures. */ /* This function scans all the LSA database and set the stat field to * LSA_SPF_NOT_EXPLORED. */ ospf_lsdb_clean_stat (area->lsdb); /* Create a new heap for the candidates. */ candidate = pqueue_create(); candidate->cmp = cmp; candidate->update = update_stat; /* Initialize the shortest-path tree to only the root (which is the router doing the calculation). */ ospf_spf_init (area); v = area->spf; /* Set LSA position to LSA_SPF_IN_SPFTREE. This vertex is the root of the * spanning tree. */ *(v->stat) = LSA_SPF_IN_SPFTREE; /* Set Area A's TransitCapability to FALSE. */ area->transit = OSPF_TRANSIT_FALSE; area->shortcut_capability = 1; for (;;) { /* RFC2328 16.1. (2). */ ospf_spf_next (v, area, candidate); /* RFC2328 16.1. (3). */ /* If at this step the candidate list is empty, the shortest- path tree (of transit vertices) has been completely built and this stage of the procedure terminates. */ if (candidate->size == 0) break; /* Otherwise, choose the vertex belonging to the candidate list that is closest to the root, and add it to the shortest-path tree (removing it from the candidate list in the process). */ /* Extract from the candidates the node with the lower key. */ v = (struct vertex *) pqueue_dequeue (candidate); /* Update stat field in vertex. */ *(v->stat) = LSA_SPF_IN_SPFTREE; ospf_vertex_add_parent (v); /* Note that when there is a choice of vertices closest to the root, network vertices must be chosen before router vertices in order to necessarily find all equal-cost paths. */ /* We don't do this at this moment, we should add the treatment above codes. -- kunihiro. */ /* RFC2328 16.1. (4). */ if (v->type == OSPF_VERTEX_ROUTER) ospf_intra_add_router (new_rtrs, v, area); else ospf_intra_add_transit (new_table, v, area); /* RFC2328 16.1. (5). */ /* Iterate the algorithm by returning to Step 2. */ } /* end loop until no more candidate vertices */ if (IS_DEBUG_OSPF_EVENT) { ospf_spf_dump (area->spf, 0); ospf_route_table_dump (new_table); } /* Second stage of SPF calculation procedure's */ ospf_spf_process_stubs (area, area->spf, new_table); /* Free candidate queue. */ pqueue_delete (candidate); ospf_vertex_dump (__func__, area->spf, 0, 1); /* Free nexthop information, canonical versions of which are attached * the first level of router vertices attached to the root vertex, see * ospf_nexthop_calculation. */ ospf_canonical_nexthops_free (area->spf); /* Free SPF vertices, but not the list. List has ospf_vertex_free * as deconstructor. */ list_delete_all_node (&vertex_list); /* Increment SPF Calculation Counter. */ area->spf_calculation++; quagga_gettime (QUAGGA_CLK_MONOTONIC, &area->ospf->ts_spf); if (IS_DEBUG_OSPF_EVENT) zlog_debug ("ospf_spf_calculate: Stop. %ld vertices", mtype_stats_alloc(MTYPE_OSPF_VERTEX)); } /* Timer for SPF calculation. */ static int ospf_spf_calculate_timer (struct thread *thread) { struct ospf *ospf = THREAD_ARG (thread); struct route_table *new_table, *new_rtrs; struct ospf_area *area; struct listnode *node, *nnode; if (IS_DEBUG_OSPF_EVENT) zlog_debug ("SPF: Timer (SPF calculation expire)"); ospf->t_spf_calc = NULL; /* Allocate new table tree. */ new_table = route_table_init (); new_rtrs = route_table_init (); ospf_vl_unapprove (ospf); /* Calculate SPF for each area. */ for (ALL_LIST_ELEMENTS (ospf->areas, node, nnode, area)) { /* Do backbone last, so as to first discover intra-area paths * for any back-bone virtual-links */ if (ospf->backbone && ospf->backbone == area) continue; ospf_spf_calculate (area, new_table, new_rtrs); } /* SPF for backbone, if required */ if (ospf->backbone) ospf_spf_calculate (ospf->backbone, new_table, new_rtrs); ospf_vl_shut_unapproved (ospf); ospf_ia_routing (ospf, new_table, new_rtrs); ospf_prune_unreachable_networks (new_table); ospf_prune_unreachable_routers (new_rtrs); /* AS-external-LSA calculation should not be performed here. */ /* If new Router Route is installed, then schedule re-calculate External routes. */ if (1) ospf_ase_calculate_schedule (ospf); ospf_ase_calculate_timer_add (ospf); /* Update routing table. */ ospf_route_install (ospf, new_table); /* Update ABR/ASBR routing table */ if (ospf->old_rtrs) { /* old_rtrs's node holds linked list of ospf_route. --kunihiro. */ /* ospf_route_delete (ospf->old_rtrs); */ ospf_rtrs_free (ospf->old_rtrs); } ospf->old_rtrs = ospf->new_rtrs; ospf->new_rtrs = new_rtrs; if (IS_OSPF_ABR (ospf)) ospf_abr_task (ospf); if (IS_DEBUG_OSPF_EVENT) zlog_debug ("SPF: calculation complete"); return 0; } /* Add schedule for SPF calculation. To avoid frequenst SPF calc, we set timer for SPF calc. */ void ospf_spf_calculate_schedule (struct ospf *ospf) { unsigned long delay, elapsed, ht; struct timeval result; if (IS_DEBUG_OSPF_EVENT) zlog_debug ("SPF: calculation timer scheduled"); /* OSPF instance does not exist. */ if (ospf == NULL) return; /* 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", ospf->t_spf_calc); return; } /* XXX Monotic timers: we only care about relative time here. */ result = tv_sub (recent_relative_time (), ospf->ts_spf); elapsed = (result.tv_sec * 1000) + (result.tv_usec / 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", delay); ospf->t_spf_calc = thread_add_timer_msec (master, ospf_spf_calculate_timer, ospf, delay); }