diff options
| -rw-r--r-- | lib/ChangeLog | 4 | ||||
| -rw-r--r-- | lib/memtypes.c | 3 | ||||
| -rw-r--r-- | ospfd/ChangeLog | 54 | ||||
| -rw-r--r-- | ospfd/ospf_interface.c | 12 | ||||
| -rw-r--r-- | ospfd/ospf_route.c | 11 | ||||
| -rw-r--r-- | ospfd/ospf_spf.c | 596 | ||||
| -rw-r--r-- | ospfd/ospf_spf.h | 17 |
7 files changed, 374 insertions, 323 deletions
diff --git a/lib/ChangeLog b/lib/ChangeLog index 956b10eb..aea7e87d 100644 --- a/lib/ChangeLog +++ b/lib/ChangeLog @@ -1,3 +1,7 @@ +2005-10-18 Paul Jakma <paul.jakma@sun.com> + + * memtypes.c: (memory_list_ospf) Add MTYPE_OSPF_VERTEX_PARENT. + 2005-10-01 Andrew J. Schorr <ajschorr@alumni.princeton.edu> * zebra.h: Declare new functions zebra_route_string() and diff --git a/lib/memtypes.c b/lib/memtypes.c index 45c07dad..f7c07fbb 100644 --- a/lib/memtypes.c +++ b/lib/memtypes.c @@ -6,7 +6,7 @@ * The script is sensitive to the format (though not whitespace), see * the top of memtypes.awk for more details. * - * $Id: memtypes.c,v 1.7 2005/09/21 14:06:35 paul Exp $ + * $Id: memtypes.c,v 1.8 2005/10/18 04:20:33 paul Exp $ */ #include "zebra.h" @@ -182,6 +182,7 @@ struct memory_list memory_list_ospf[] = { MTYPE_OSPF_PACKET, "OSPF packet" }, { MTYPE_OSPF_FIFO, "OSPF FIFO queue" }, { MTYPE_OSPF_VERTEX, "OSPF vertex" }, + { MTYPE_OSPF_VERTEX_PARENT, "OSPF vertex parent", }, { MTYPE_OSPF_NEXTHOP, "OSPF nexthop" }, { MTYPE_OSPF_PATH, "OSPF path" }, { MTYPE_OSPF_VL_DATA, "OSPF VL data" }, diff --git a/ospfd/ChangeLog b/ospfd/ChangeLog index c56f01bb..299de23c 100644 --- a/ospfd/ChangeLog +++ b/ospfd/ChangeLog @@ -1,3 +1,57 @@ +2005-10-18 Paul Jakma <paul.jakma@sun.com> + + * (general) SPF memory management cleanup and fix for rare + double-free bug. + * ospf_spf.h: (struct vertex_parent) New struct to hold parent + specific data, eg the backlink and the parent vertex pointer, + and point to the appropriate general struct vertex_nexthop. + (struct vertex_nexthop) remove parent vertex pointer, so + this struct can be shared across vertices. + (struct vertex) rename list child to list children. Remove + list of nexthops, replace with list of vertex_parents. + * ospf_spf.c: (update_stat) trivial, remove cast from void *. + (vertex_nexthop_new) remove init of parent - field is gone + from struct vertex_nexthop. + (ospf_canonical_nexthops_free) Remove the canonical + vertex_nexthop memory objects. These are the vertex_nexthops + attached to the first level of router vertices from the root. + (vertex_parent_new) new function, create a vertex_parent. + (vertex_parent_free) ditto, but free it. + (ospf_vertex_new) Update to match changes to struct vertex. + (ospf_vertex_free) Recursively free a struct vertex and its + children. The parent list is used as a reference count. + vertex_nexthops must be free seperately, if required. + (ospf_vertex_dump) update to match struct vertex changes. + Print out backlink of parents too. + (ospf_vertex_add_parent) ditto. + (ospf_lsa_has_link) update comment. + (ospf_nexthop_add_unique) removed, not needed anymore. + (ospf_nexthop_merge) ditto. + (ospf_spf_consider_nexthop) renamed to ospf_spf_add_parent. + Simplified to just create vertex_parent and add it. + (ospf_spf_flush_parents) new function, flush out the parent + list. + (ospf_nexthop_calculation) Take the relevant route_lsa_link + as an argument, which simplifies things and removes the need + for the hack in ospf_nexthop_add_unique - ospf_spf_next + already knew exactly which link the cost calculated was for. + Update to match struct vertex changes too. + (ospf_spf_next) Don't create a vertex for W unnecessarily, if + it's there's a vertex already created for W, use it, and + hence there's no need to free it either. + Update some manipulation/comparisons of distance to match. + Flush the parent list if a lower cost path is found. + (ospf_spf_route_free) unused, removed. + (ospf_spf_dump) match the struct vertex changes, and dump the + ifname if possible. + (ospf_spf_calculate) At end of SPF, free the canonical nexthops + and call ospf_vertex_free on the root vertex to free the + entire tree. + * ospf_interface.c: (ospf_vl_set_params) match struct vertex + changes. + * ospf_route.c: (ospf_intra_route_add) ditto + (ospf_route_copy_nexthops_from_vertex) ditto + 2005-10-11 Paul Jakma <paul.jakma@sun.com> * ospf_api.c: sign warnings. diff --git a/ospfd/ospf_interface.c b/ospfd/ospf_interface.c index 9d31b7a3..fe32268f 100644 --- a/ospfd/ospf_interface.c +++ b/ospfd/ospf_interface.c @@ -999,7 +999,7 @@ ospf_vl_set_params (struct ospf_vl_data *vl_data, struct vertex *v) int changed = 0; struct ospf_interface *voi; struct listnode *node; - struct vertex_nexthop *nh; + struct vertex_parent *vp = NULL; int i; struct router_lsa *rl; @@ -1012,9 +1012,9 @@ ospf_vl_set_params (struct ospf_vl_data *vl_data, struct vertex *v) changed = 1; } - for (ALL_LIST_ELEMENTS_RO (v->nexthop, node, nh)) + for (ALL_LIST_ELEMENTS_RO (v->parents, node, vp)) { - vl_data->out_oi = (struct ospf_interface *) nh->oi; + vl_data->out_oi = vp->nexthop->oi; if (!IPV4_ADDR_SAME(&voi->address->u.prefix4, &vl_data->out_oi->address->u.prefix4)) @@ -1031,12 +1031,12 @@ ospf_vl_set_params (struct ospf_vl_data *vl_data, struct vertex *v) /* use SPF determined backlink index in struct vertex * for virtual link destination address */ - if (v->backlink >= 0) + if (vp && vp->backlink >= 0) { if (!IPV4_ADDR_SAME (&vl_data->peer_addr, - &rl->link[v->backlink].link_data)) + &rl->link[vp->backlink].link_data)) changed = 1; - vl_data->peer_addr = rl->link[v->backlink].link_data; + vl_data->peer_addr = rl->link[vp->backlink].link_data; } else { diff --git a/ospfd/ospf_route.c b/ospfd/ospf_route.c index 00733d84..bdbdd03e 100644 --- a/ospfd/ospf_route.c +++ b/ospfd/ospf_route.c @@ -278,7 +278,7 @@ ospf_intra_route_add (struct route_table *rt, struct vertex *v, struct ospf_route *or; struct prefix_ipv4 p; struct ospf_path *path; - struct vertex_nexthop *nexthop; + struct vertex_parent *parent; struct listnode *node, *nnode; p.family = AF_INET; @@ -306,10 +306,10 @@ ospf_intra_route_add (struct route_table *rt, struct vertex *v, { or->type = OSPF_DESTINATION_NETWORK; - for (ALL_LIST_ELEMENTS (v->nexthop, node, nnode, nexthop)) + for (ALL_LIST_ELEMENTS (v->parents, node, nnode, parent)) { path = ospf_path_new (); - path->nexthop = nexthop->router; + path->nexthop = parent->nexthop->router; listnode_add (or->paths, path); } } @@ -799,11 +799,14 @@ ospf_route_copy_nexthops_from_vertex (struct ospf_route *to, struct listnode *node; struct ospf_path *path; struct vertex_nexthop *nexthop; + struct vertex_parent *vp; assert (to->paths); - for (ALL_LIST_ELEMENTS_RO (v->nexthop, node, nexthop)) + for (ALL_LIST_ELEMENTS_RO (v->parents, node, vp)) { + nexthop = vp->nexthop; + if (nexthop->oi != NULL) { if (! ospf_path_exist (to->paths, nexthop->router, nexthop->oi)) diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c index 1aba5d97..b05117da 100644 --- a/ospfd/ospf_spf.c +++ b/ospfd/ospf_spf.c @@ -60,23 +60,18 @@ cmp (void * node1 , void * node2) } static void -update_stat (void * node , int position) +update_stat (void *node , int position) { - struct vertex * v = (struct vertex *) node; + struct vertex *v = node; + /* Set the status of the vertex, when its position changes. */ *(v->stat) = position; } -/* End of the heap related functions. */ - + static struct vertex_nexthop * -vertex_nexthop_new (struct vertex *parent) +vertex_nexthop_new (void) { - struct vertex_nexthop *new; - - new = XCALLOC (MTYPE_OSPF_NEXTHOP, sizeof (struct vertex_nexthop)); - new->parent = parent; - - return new; + return XCALLOC (MTYPE_OSPF_NEXTHOP, sizeof (struct vertex_nexthop)); } static void @@ -85,27 +80,56 @@ vertex_nexthop_free (struct vertex_nexthop *nh) XFREE (MTYPE_OSPF_NEXTHOP, nh); } -static struct vertex_nexthop * -vertex_nexthop_dup (struct vertex_nexthop *nh) +/* Free the canonical nexthop objects for an area, ie the nexthop objects + * attached to the first-hop router vertices. + */ +static void +ospf_canonical_nexthops_free (struct vertex *root) { - struct vertex_nexthop *new; - - new = vertex_nexthop_new (nh->parent); - - new->oi = nh->oi; - new->router = nh->router; - + struct listnode *node, *nnode; + struct vertex *child; + + for (ALL_LIST_ELEMENTS (root->children, node, nnode, child)) + { + struct listnode *n2, *nn2; + struct vertex_parent *vp; + + if (child->type == OSPF_VERTEX_NETWORK) + ospf_canonical_nexthops_free (child); + + for (ALL_LIST_ELEMENTS (child->parents, n2, nn2, vp)) + vertex_nexthop_free (vp->nexthop); + } +} + +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 (struct vertex_parent *p) +{ + XFREE (MTYPE_OSPF_VERTEX_PARENT, p); +} + static struct vertex * ospf_vertex_new (struct ospf_lsa *lsa) { struct vertex *new; - new = XMALLOC (MTYPE_OSPF_VERTEX, sizeof (struct vertex)); - memset (new, 0, sizeof (struct vertex)); + new = XCALLOC (MTYPE_OSPF_VERTEX, sizeof (struct vertex)); new->flags = 0; new->stat = &(lsa->stat); @@ -113,66 +137,86 @@ ospf_vertex_new (struct ospf_lsa *lsa) new->id = lsa->data->id; new->lsa = lsa->data; new->distance = 0; - new->child = list_new (); - new->nexthop = list_new (); - new->backlink = -1; - + new->children = list_new (); + new->parents = list_new (); + return new; } +/* Recursively free the given vertex and all its children + * and associated parent and nexthop information + * Parent should indicate which parent is trying to free this child, + * NULL parent is only valid for the root vertex. + */ static void -ospf_vertex_free (struct vertex *v) +ospf_vertex_free (struct vertex *v, const struct ospf_area *area) { struct listnode *node, *nnode; - struct vertex_nexthop *nh; - - list_delete (v->child); - v->child = NULL; + struct vertex *vc; + + assert (*(v->stat) == LSA_SPF_IN_SPFTREE); + + /* recurse down the tree, freeing furthest children first */ + if (v->children) + { + for (ALL_LIST_ELEMENTS (v->children, node, nnode, vc)) + ospf_vertex_free (vc, area); + + list_delete (v->children); + v->children = NULL; + } - if (listcount (v->nexthop) > 0) - for (ALL_LIST_ELEMENTS (v->nexthop, node, nnode, nh)) - vertex_nexthop_free (nh); + /* The vertex itself can only be freed when the last remaining parent + * with a reference to this vertex frees this vertex. Until then, we + * just cleanup /one/ parent association (doesnt matter which) - + * essentially using the parents list as a refcount. + */ + if (listcount (v->parents) > 0) + { + vertex_parent_free (listgetdata (listhead (v->parents))); + list_delete_node (v->parents, listhead (v->parents)); - list_delete (v->nexthop); - v->nexthop = NULL; + if (listcount (v->parents) > 0) + return; /* there are still parent references left */ + } + + 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_nexthops, int print_children) + int print_parents, int print_children) { if ( ! IS_DEBUG_OSPF_EVENT) return; - zlog_debug("%s %s vertex %s distance %u backlink %d flags %u", + 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, - v->backlink, (unsigned int)v->flags); - if (print_nexthops) + if (print_parents) { struct listnode *node; - struct vertex_nexthop *nexthop; + struct vertex_parent *vp; - for (ALL_LIST_ELEMENTS_RO (v->nexthop, node, nexthop)) + for (ALL_LIST_ELEMENTS_RO (v->parents, node, vp)) { char buf1[BUFSIZ]; - char buf2[BUFSIZ]; - - if (nexthop) + + if (vp) { - zlog_debug (" nexthop %s interface %s parent %s", - inet_ntop(AF_INET, &nexthop->router, buf1, BUFSIZ), - nexthop->oi ? IF_NAME(nexthop->oi) : "NULL", - nexthop->parent ? inet_ntop(AF_INET, - &nexthop->parent->id, - buf2, BUFSIZ) - : "NULL"); + 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"); } } } @@ -182,7 +226,7 @@ ospf_vertex_dump(const char *msg, struct vertex *v, struct listnode *cnode; struct vertex *cv; - for (ALL_LIST_ELEMENTS_RO (v->child, cnode, cv)) + for (ALL_LIST_ELEMENTS_RO (v->children, cnode, cv)) ospf_vertex_dump(" child:", cv, 0, 0); } } @@ -192,18 +236,18 @@ ospf_vertex_dump(const char *msg, struct vertex *v, static void ospf_vertex_add_parent (struct vertex *v) { - struct vertex_nexthop *nh; + struct vertex_parent *vp; struct listnode *node; - assert (v->nexthop && v->child); + assert (v && v->children); - for (ALL_LIST_ELEMENTS_RO (v->nexthop, node, nh)) + for (ALL_LIST_ELEMENTS_RO (v->parents, node, vp)) { - assert (nh->parent && nh->parent->child); + assert (vp->parent && vp->parent->children); /* No need to add two links from the same parent. */ - if (listnode_lookup (nh->parent->child, v) == NULL) - listnode_add (nh->parent->child, v); + if (listnode_lookup (vp->parent->children, v) == NULL) + listnode_add (vp->parent->children, v); } } @@ -276,7 +320,7 @@ ospf_lsa_has_link (struct lsa_header *w, struct lsa_header *v) } break; case LSA_LINK_TYPE_STUB: - /* Not take into count? */ + /* Stub can't lead anywhere, carry on */ continue; default: break; @@ -286,51 +330,6 @@ ospf_lsa_has_link (struct lsa_header *w, struct lsa_header *v) return -1; } -/* Add the nexthop to the list, only if it is unique. - * If it's not unique, free the nexthop entry. - */ -static void -ospf_nexthop_add_unique (struct vertex_nexthop *new, struct list *nexthop) -{ - struct vertex_nexthop *nh; - struct listnode *node; - int match; - - match = 0; - - for (ALL_LIST_ELEMENTS_RO (nexthop, node, nh)) - { - /* Compare the two entries. */ - /* XXX - * Comparing the parent preserves the shortest path tree - * structure even when the nexthops are identical. - */ - if (nh->oi == new->oi && - IPV4_ADDR_SAME (&nh->router, &new->router) && - nh->parent == new->parent) - { - match = 1; - break; - } - } - - if (!match) - listnode_add (nexthop, new); - else - vertex_nexthop_free (new); -} - -/* Merge entries in list b into list a. */ -static void -ospf_nexthop_merge (struct list *a, struct list *b) -{ - struct listnode *node, *nnode; - struct vertex_nexthop *nh; - - for (ALL_LIST_ELEMENTS (b, node, nnode, nh)) - ospf_nexthop_add_unique (nh, a); -} - #define ROUTER_LSA_MIN_SIZE 12 #define ROUTER_LSA_TOS_SIZE 4 @@ -395,51 +394,49 @@ ospf_get_next_link (struct vertex *v, struct vertex *w, * cost path to a candidate vertex in SPF, maybe. */ static void -ospf_spf_consider_nexthop (struct list *nexthops, - struct vertex_nexthop *newhop) +ospf_spf_add_parent (struct vertex *v, struct vertex *w, + struct vertex_nexthop *newhop) { - struct vertex_nexthop *hop; - struct listnode *ln, *nn; + struct vertex_parent *vp; + + /* we must have a newhop.. */ + assert (v && w && newhop); + + /* new parent is <= existing parents, add it */ + vp = vertex_parent_new (v, ospf_lsa_has_link (w->lsa, v->lsa), newhop); + listnode_add (w->parents, vp); - /* nexthop list should contain only the set of nexthops that have the lowest - * equal cost - */ - if (nexthops->head != NULL) + return; +} + +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)) { - hop = listgetdata (nexthops->head); - - /* weed out hops with higher cost than the newhop */ - if (hop->oi->output_cost > newhop->oi->output_cost) - { - /* delete the existing nexthops */ - for (ALL_LIST_ELEMENTS (nexthops, ln, nn, hop)) - { - listnode_delete (nexthops, hop); - vertex_nexthop_free (hop); - } - } - else if (hop->oi->output_cost < newhop->oi->output_cost) - return; + list_delete_node (w->parents, ln); + vertex_parent_free (vp); } - - /* new hop is <= existing hops, add it */ - listnode_add (nexthops, newhop); - - return; } /* 16.1.1. Calculate nexthop from root through V (parent) to * vertex W (destination). + * + * The link must be supplied if V is the root vertex. In all other cases + * it may be NULL. */ static void -ospf_nexthop_calculation (struct ospf_area *area, - struct vertex *v, struct vertex *w) +ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v, + struct vertex *w, struct router_lsa_link *l) { struct listnode *node, *nnode; - struct vertex_nexthop *nh, *x; + struct vertex_nexthop *nh; + struct vertex_parent *vp; struct ospf_interface *oi = NULL; - struct router_lsa_link *l = NULL; - if (IS_DEBUG_OSPF_EVENT) { @@ -459,128 +456,124 @@ ospf_nexthop_calculation (struct ospf_area *area, if (w->type == OSPF_VERTEX_ROUTER) { - while ((l = ospf_get_next_link (v, w, l))) + /* 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) { - /* l is a link from v to w - * l2 will be link from w to v - */ - struct router_lsa_link *l2 = 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) + 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) { - /* 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 + 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))) { - /* 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; - } - } + la.prefix = l2->link_data; - if (oi && l2) + 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))) { - /* found all necessary info to build nexthop */ - nh = vertex_nexthop_new (v); - nh->oi = oi; - nh->router = l2->link_data; - ospf_spf_consider_nexthop (w->nexthop, nh); + 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; } - else - { - zlog_info("ospf_nexthop_calculation(): " - "could not determine nexthop for link"); - } - } /* end point-to-point link from V to W */ - } /* end iterate over links in W */ + } + + 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); + } + else + { + zlog_info("ospf_nexthop_calculation(): " + "could not determine nexthop for link"); + } + } /* end point-to-point link from V to W */ } /* end W is a Router vertex */ else { - assert(w->type == OSPF_VERTEX_NETWORK); - while ((l = ospf_get_next_link (v, w, l))) + assert(w->type == OSPF_VERTEX_NETWORK); + oi = ospf_if_is_configured (area->ospf, &(l->link_data)); + if (oi) { - oi = ospf_if_is_configured (area->ospf, &(l->link_data)); - if (oi) - { - nh = vertex_nexthop_new (v); - nh->oi = oi; - nh->router.s_addr = 0; - ospf_spf_consider_nexthop (w->nexthop, nh); - } + nh = vertex_nexthop_new (); + nh->oi = oi; + nh->router.s_addr = 0; + ospf_spf_add_parent (v, w, nh); } } return; } /* 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->nexthop, node, nnode, x)) + for (ALL_LIST_ELEMENTS (v->parents, node, nnode, vp)) { - if (x->parent == area->spf) /* connects to root? */ + 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 @@ -597,10 +590,10 @@ ospf_nexthop_calculation (struct ospf_area *area, * use can then be derived from the next hop IP address (or * it can be inherited from the parent network). */ - nh = vertex_nexthop_new (v); - nh->oi = x->oi; - nh->router = l->link_data; - ospf_spf_consider_nexthop (w->nexthop, nh); + nh = vertex_nexthop_new (); + nh->oi = vp->nexthop->oi; + nh->router = l->link_data; + ospf_spf_add_parent (v, w, nh); } return; } @@ -612,11 +605,8 @@ ospf_nexthop_calculation (struct ospf_area *area, * destination simply inherits the set of next hops from the * parent. */ - for (ALL_LIST_ELEMENTS (v->nexthop, node, nnode, nh)) - { - nh->parent = v; - ospf_nexthop_add_unique (nh, w->nexthop); - } + for (ALL_LIST_ELEMENTS (v->parents, node, nnode, vp)) + ospf_spf_add_parent (v, w, vp->nexthop); } /* RFC2328 Section 16.1 (2). @@ -648,9 +638,8 @@ ospf_spf_next (struct vertex *v, struct ospf_area *area, while (p < lim) { - struct vertex *w, *cw; - - int link = -1; /* link index for w's back link */ + struct vertex *w; + unsigned int distance; /* In case of V is Router-LSA. */ if (v->lsa->type == OSPF_ROUTER_LSA) @@ -723,7 +712,7 @@ ospf_spf_next (struct vertex *v, struct ospf_area *area, if (IS_LSA_MAXAGE (w_lsa)) continue; - if ( (link = ospf_lsa_has_link (w_lsa->data, v->lsa)) < 0 ) + 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"); @@ -745,54 +734,52 @@ ospf_spf_next (struct vertex *v, struct ospf_area *area, vertex V and the advertised cost of the link between vertices V and W. If D is: */ - /* prepare vertex W. */ - w = ospf_vertex_new (w_lsa); - - /* Save W's back link index number, for use by virtual links */ - w->backlink = link; - /* calculate link cost D. */ if (v->lsa->type == OSPF_ROUTER_LSA) - w->distance = v->distance + ntohs (l->m[0].metric); + distance = v->distance + ntohs (l->m[0].metric); else /* v is not a Router-LSA */ - w->distance = v->distance; + 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. */ - ospf_nexthop_calculation (area, v, w); + w->distance = distance; + ospf_nexthop_calculation (area, v, w, l); pqueue_enqueue (w, candidate); } else if (w_lsa->stat >= 0) { /* Get the vertex from candidates. */ - cw = (struct vertex *) candidate->array[w_lsa->stat]; + w = candidate->array[w_lsa->stat]; /* if D is greater than. */ - if (cw->distance < w->distance) + if (w->distance < distance) { - ospf_vertex_free (w); continue; } /* equal to. */ - else if (cw->distance == w->distance) + else if (w->distance == distance) { - /* Found an equal-cost path to W. Calculate nexthop to W. */ - ospf_nexthop_calculation (area, v, w); - ospf_nexthop_merge (cw->nexthop, w->nexthop); - list_delete_all_node (w->nexthop); - ospf_vertex_free (w); + /* Found an equal-cost path to W. + * Calculate nexthop of to W from V. */ + ospf_nexthop_calculation (area, v, w, l); } /* less than. */ else { - /* Found a lower-cost path to W. Calculate nexthop to W. */ - ospf_nexthop_calculation (area, v, w); + /* Found a lower-cost path to W. */ + w->distance = distance; + + /* Flush existing parent list from W */ + ospf_spf_flush_parents (w); + + /* Calculate new nexthop(s) to W. */ + ospf_nexthop_calculation (area, v, w, l); - /* Remove old vertex from candidate list. */ - ospf_vertex_free (cw); - candidate->array[w_lsa->stat] = w; /* Decrease the key of the node in the heap, re-sort the heap. */ trickle_down (w_lsa->stat, candidate); } @@ -801,31 +788,11 @@ ospf_spf_next (struct vertex *v, struct ospf_area *area, } static void -ospf_spf_route_free (struct route_table *table) -{ - struct route_node *rn; - struct vertex *v; - - for (rn = route_top (table); rn; rn = route_next (rn)) - { - if ((v = rn->info)) - { - ospf_vertex_free (v); - rn->info = NULL; - } - - route_unlock_node (rn); - } - - route_table_finish (table); -} - -static void ospf_spf_dump (struct vertex *v, int i) { struct listnode *cnode; struct listnode *nnode; - struct vertex_nexthop *nexthop; + struct vertex_parent *parent; if (v->type == OSPF_VERTEX_ROUTER) { @@ -841,12 +808,18 @@ ospf_spf_dump (struct vertex *v, int i) } if (IS_DEBUG_OSPF_EVENT) - for (ALL_LIST_ELEMENTS_RO (v->nexthop, nnode, nexthop)) - zlog_debug (" nexthop %s", inet_ntoa (nexthop->router)); + 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->child, cnode, v)) + for (ALL_LIST_ELEMENTS_RO (v->children, cnode, v)) ospf_spf_dump (v, i); } @@ -894,7 +867,7 @@ ospf_spf_process_stubs (struct ospf_area *area, struct vertex *v, ospf_vertex_dump("ospf_process_stubs(): after examining links: ", v, 1, 1); - for (ALL_LIST_ELEMENTS (v->child, cnode, cnnode, child)) + for (ALL_LIST_ELEMENTS (v->children, cnode, cnnode, child)) { if (CHECK_FLAG (child->flags, OSPF_VERTEX_PROCESSED)) continue; @@ -997,7 +970,7 @@ ospf_spf_calculate (struct ospf_area *area, struct route_table *new_table, { struct pqueue *candidate; struct vertex *v; - + if (IS_DEBUG_OSPF_EVENT) { zlog_debug ("ospf_spf_calculate: Start"); @@ -1038,7 +1011,7 @@ ospf_spf_calculate (struct ospf_area *area, struct route_table *new_table, /* Set Area A's TransitCapability to FALSE. */ area->transit = OSPF_TRANSIT_FALSE; area->shortcut_capability = 1; - + for (;;) { /* RFC2328 16.1. (2). */ @@ -1059,6 +1032,7 @@ ospf_spf_calculate (struct ospf_area *area, struct route_table *new_table, 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 @@ -1087,9 +1061,19 @@ ospf_spf_calculate (struct ospf_area *area, struct route_table *new_table, /* Second stage of SPF calculation procedure's */ ospf_spf_process_stubs (area, area->spf, new_table); - /* Free candidates. */ + /* 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 */ + ospf_vertex_free (area->spf, area); + /* Increment SPF Calculation Counter. */ area->spf_calculation++; diff --git a/ospfd/ospf_spf.h b/ospfd/ospf_spf.h index 1aa871ae..50e590d6 100644 --- a/ospfd/ospf_spf.h +++ b/ospfd/ospf_spf.h @@ -36,11 +36,10 @@ struct vertex u_char type; /* copied from LSA header */ struct in_addr id; /* copied from LSA header */ struct lsa_header *lsa; /* Router or Network LSA */ - int * stat; /* Link to LSA status. */ - u_int32_t distance; /* from root to this vertex */ - int backlink; /* link index of back-link */ - struct list *child; /* list of vertex: children in SPF tree*/ - struct list *nexthop; /* list of vertex_nexthop from root to this vertex */ + int *stat; /* Link to LSA status. */ + u_int32_t distance; /* from root to this vertex */ + struct list *parents; /* list of parents in SPF tree */ + struct list *children; /* list of children in SPF tree*/ }; /* A nexthop taken on the root node to get to this (parent) vertex */ @@ -48,7 +47,13 @@ struct vertex_nexthop { struct ospf_interface *oi; /* output intf on root node */ struct in_addr router; /* router address to send to */ - struct vertex *parent; /* parent in SPF tree */ +}; + +struct vertex_parent +{ + struct vertex_nexthop *nexthop; /* link to nexthop info for this parent */ + struct vertex *parent; /* parent vertex */ + int backlink; /* index back to parent for router-lsa's */ }; extern void ospf_spf_calculate_schedule (struct ospf *); |