From 9c27ef9b9c26db0af507869c2866c4a8463f4ae7 Mon Sep 17 00:00:00 2001 From: Paul Jakma Date: Thu, 4 May 2006 07:32:57 +0000 Subject: [ospfd] Fix SPF of virtual-links 2006-04-24 Paul Jakma * (general) More Virtual-link fixes, again with much help in testing / debug from Juergen Kammer. Primarily in SPF. * ospf_spf.h: Add guard. ospf_interface.h will include this header. * ospf_interface.h: Modify ospf_vl_lookup definition to take struct ospf as argument, so as to allow for NULL area argument. (struct ospf_vl_data) Remove out_oi, instead add a struct vertex_nexthop, to use as initial nexthop for backbone paths through a vlink. * ospf_interface.c: (ospf_vl_lookup) Modified to allow NULL area to be passed to indicate "any" (first) area. Add extra debug. (ospf_vl_set_params) vl_oi -> nexthop. Add extra debug. (ospf_vl_up_check) Fix debug, inet_ntoa returns a static buffer.. * ospf_route.c: (ospf_intra_add_router) Vlinks dont go through backbone, don't bother checking. * ospf_spf.c: (static struct list vertex_list) Record vertices that will need to be freed. (cmp) Order network before router vertices, as required, wasn't implemented. (vertex_nexthop_free) Mild additional robustness check. (vertex_parent_free) Take void argument, as this function is passed as list deconstructor for vertex parent list. (ospf_vertex_new) More debug. Set deconstructor for parent list. Track allocated vertices on the vertex_list. (ospf_vertex_free) Get rid of the tricky recursive cleanup of vertices. Now frees only the given vertex. (ospf_vertex_add_parent) Fix assert. (ospf_nexthop_calculation) Fix calculation of nexthop for VLink vertices, lookup the vl_data and use its previously recorded nexthop information. (ospf_spf_calculate) Vertices are freed simply by deleting vertex_list nodes and letting ospf_vertex_free as deconstructor work per-node. (ospf_spf_calculate_timer) Trivial optimisation, leave backbone SPF calculation till last to reduce SPF churn on VLink updates. * ospf_vty.c: (ospf_find_vl_data) update call to ospf_vl_lookup (no_ospf_area_vlink_cmd) ditto. (show_ip_ospf_interface_sub) For Vlinks, the peer address is more interesting than the output interface. --- ospfd/ospf_spf.c | 165 ++++++++++++++++++++++++++++++++++++++----------------- 1 file changed, 114 insertions(+), 51 deletions(-) (limited to 'ospfd/ospf_spf.c') diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c index dbd06361..7228d2d4 100644 --- a/ospfd/ospf_spf.c +++ b/ospfd/ospf_spf.c @@ -46,6 +46,13 @@ Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA #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 @@ -54,9 +61,25 @@ cmp (void * node1 , void * node2) struct vertex * v1 = (struct vertex *) node1; struct vertex * v2 = (struct vertex *) node2; if (v1 != NULL && v2 != NULL ) - return (v1->distance - v2->distance); - else - return 0; + { + /* 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 @@ -81,7 +104,8 @@ vertex_nexthop_free (struct vertex_nexthop *nh) } /* Free the canonical nexthop objects for an area, ie the nexthop objects - * attached to the first-hop router vertices. + * attached to the first-hop router vertices, and any intervening network + * vertices. */ static void ospf_canonical_nexthops_free (struct vertex *root) @@ -106,11 +130,14 @@ ospf_canonical_nexthops_free (struct vertex *root) /* Free child nexthops pointing back to this root vertex */ for (ALL_LIST_ELEMENTS (child->parents, n2, nn2, vp)) - if (vp->parent == root) + 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) { @@ -128,7 +155,7 @@ vertex_parent_new (struct vertex *v, int backlink, struct vertex_nexthop *hop) } static void -vertex_parent_free (struct vertex_parent *p) +vertex_parent_free (void *p) { XFREE (MTYPE_OSPF_VERTEX_PARENT, p); } @@ -148,48 +175,39 @@ ospf_vertex_new (struct ospf_lsa *lsa) new->distance = 0; 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; } -/* 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, const struct ospf_area *area) +ospf_vertex_free (void *data) { - struct listnode *node, *nnode; - struct vertex *vc; + struct vertex *v = data; - 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 (IS_DEBUG_OSPF_EVENT) + zlog_debug ("%s: Free %s vertex %s", __func__, + v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network", + inet_ntoa (v->lsa->id)); - /* 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. + /* There should be no parents potentially holding references to this vertex + * Children however may still be there, but presumably referenced by other + * vertices */ - if (listcount (v->parents) > 0) - { - vertex_parent_free (listgetdata (listhead (v->parents))); - list_delete_node (v->parents, listhead (v->parents)); - - if (listcount (v->parents) > 0) - return; /* there are still parent references left */ - } + //assert (listcount (v->parents) == 0); - list_delete (v->parents); + if (v->children) + list_delete (v->children); + v->children = NULL; + + if (v->parents) + list_delete (v->parents); v->parents = NULL; v->lsa = NULL; @@ -248,7 +266,7 @@ ospf_vertex_add_parent (struct vertex *v) struct vertex_parent *vp; struct listnode *node; - assert (v && v->children); + assert (v && v->parents); for (ALL_LIST_ELEMENTS_RO (v->parents, node, vp)) { @@ -264,7 +282,7 @@ static void ospf_spf_init (struct ospf_area *area) { struct vertex *v; - + /* Create root node. */ v = ospf_vertex_new (area->router_lsa_self); @@ -455,7 +473,7 @@ ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v, } 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 @@ -556,11 +574,35 @@ ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v, 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 */ + 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)) { - zlog_info("ospf_nexthop_calculation(): " - "could not determine nexthop for link"); + nh = vertex_nexthop_new (); + nh->oi = vl_data->nexthop.oi; + nh->router = vl_data->nexthop.router; + ospf_spf_add_parent (v, w, nh); } - } /* end point-to-point link from V to W */ + else + zlog_info("ospf_nexthop_calculation(): " + "vl_data for VL link not found"); + } /* end virtual-link from V to W */ + return; } /* end W is a Router vertex */ else { @@ -572,8 +614,11 @@ ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v, nh->oi = oi; nh->router.s_addr = 0; ospf_spf_add_parent (v, w, nh); + return; } } + zlog_info("ospf_nexthop_calculation(): " + "Unknown attached link"); return; } /* end V is the root */ /* Check if W's parent is a network connected to root. */ @@ -616,6 +661,8 @@ ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v, */ for (ALL_LIST_ELEMENTS (v->parents, node, nnode, vp)) ospf_spf_add_parent (v, w, vp->nexthop); + + return; } /* RFC2328 Section 16.1 (2). @@ -757,8 +804,9 @@ ospf_spf_next (struct vertex *v, struct ospf_area *area, /* Calculate nexthop to W. */ w->distance = distance; - ospf_nexthop_calculation (area, v, w, l); - pqueue_enqueue (w, candidate); + + ospf_nexthop_calculation (area, v, w, l); + pqueue_enqueue (w, candidate); } else if (w_lsa->stat >= 0) { @@ -1080,8 +1128,10 @@ ospf_spf_calculate (struct ospf_area *area, struct route_table *new_table, */ ospf_canonical_nexthops_free (area->spf); - /* Free SPF vertices */ - ospf_vertex_free (area->spf, area); + /* 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++; @@ -1089,7 +1139,8 @@ ospf_spf_calculate (struct ospf_area *area, struct route_table *new_table, gettimeofday (&area->ospf->ts_spf, NULL); if (IS_DEBUG_OSPF_EVENT) - zlog_debug ("ospf_spf_calculate: Stop"); + zlog_debug ("ospf_spf_calculate: Stop. %ld vertices", + mtype_stats_alloc(MTYPE_OSPF_VERTEX)); } /* Timer for SPF calculation. */ @@ -1114,8 +1165,20 @@ ospf_spf_calculate_timer (struct thread *thread) /* Calculate SPF for each area. */ for (ALL_LIST_ELEMENTS (ospf->areas, node, nnode, area)) - ospf_spf_calculate (area, new_table, new_rtrs); - + { + /* 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); -- cgit v1.2.3 From 2518efd15b75687d4791a5eb4b0d7febc36cffbc Mon Sep 17 00:00:00 2001 From: Paul Jakma Date: Sun, 27 Aug 2006 06:49:29 +0000 Subject: [ospfd] Bug #134, ospfd should be more robust to backward time change 2006-08-25 Paul Jakma * (general) Bug #134. Be more robust to backward time changes, use the newly added libzebra time functions. In most cases: recent_time -> recent_relative_time() gettimeofday -> quagga_gettime (QUAGGA_CLK_MONOTONIC, ..) time -> quagga_time. (ospf_make_md5_digest) time() call deliberately not changed. (ospf_external_lsa_refresh) remove useless gettimeofday, LSA tv_orig time was already set in ospf_lsa_new, called via ospf_external_lsa_new. --- ospfd/ospf_spf.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'ospfd/ospf_spf.c') diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c index 7228d2d4..a133d5f8 100644 --- a/ospfd/ospf_spf.c +++ b/ospfd/ospf_spf.c @@ -1136,7 +1136,7 @@ ospf_spf_calculate (struct ospf_area *area, struct route_table *new_table, /* Increment SPF Calculation Counter. */ area->spf_calculation++; - gettimeofday (&area->ospf->ts_spf, NULL); + quagga_gettime (QUAGGA_CLK_MONOTONIC, &area->ospf->ts_spf); if (IS_DEBUG_OSPF_EVENT) zlog_debug ("ospf_spf_calculate: Stop. %ld vertices", @@ -1243,7 +1243,7 @@ ospf_spf_calculate_schedule (struct ospf *ospf) } /* XXX Monotic timers: we only care about relative time here. */ - result = tv_sub (recent_time, ospf->ts_spf); + 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; -- cgit v1.2.3 From bc20c1a4638db3b92a2e2f7f4b820e60f30a6146 Mon Sep 17 00:00:00 2001 From: Paul Jakma Date: Wed, 24 Jan 2007 14:51:51 +0000 Subject: [ospfd] Bug #330: SPF must consider that nexthop-calc may fail 2007-01-24 Paul Jakma * ospf_spf.c: Bug #330: Nexthop calculation sometimes may fail, and it needs to indicate this result to SPF. (ospf_spf_add_parent) Flush of parent list needs to be done here, for simplicity. (ospf_nexthop_calculation) Caller needs to know whether nexthop calculation succeeded. Every return statement must correctly indicate such. (ospf_spf_next) Queueing/prioritisation of vertices in SPF must take into account whether nexthop_calculation succeeded, or SPF may fail to find best paths. --- ospfd/ospf_spf.c | 121 ++++++++++++++++++++++++++++++------------------------- 1 file changed, 65 insertions(+), 56 deletions(-) (limited to 'ospfd/ospf_spf.c') diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c index a133d5f8..f4adc114 100644 --- a/ospfd/ospf_spf.c +++ b/ospfd/ospf_spf.c @@ -405,58 +405,63 @@ ospf_get_next_link (struct vertex *v, struct vertex *w, 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. - * - * (Discussed on GNU Zebra list 27 May 2003, [zebra 19184]) - * - * Note that below is a bit of a hack, and limits ECMP to paths that go to - * same nexthop. Where as paths via inequal output_cost interfaces could - * still quite easily be ECMP due to remote cost differences. - * - * TODO: It really should be done by way of recording currently valid - * backlinks and determining the appropriate nexthops from the list of - * backlinks, or even simpler, just flushing nexthop list if we find a lower - * cost path to a candidate vertex in SPF, maybe. */ static void ospf_spf_add_parent (struct vertex *v, struct vertex *w, - struct vertex_nexthop *newhop) + struct vertex_nexthop *newhop, + struct router_lsa_link *l) { struct vertex_parent *vp; + unsigned int new_distance; /* we must have a newhop.. */ - assert (v && w && newhop); + assert (v && w && l && newhop); + + new_distance = v->distance + ntohs (l->m[0].metric); + + /* We shouldn't get here unless callers have determined V(l)->W is + * shortest / equal-shortest path. + */ + assert (new_distance <= w->distance); + + /* Adding parent for a new, better path: flush existing parents from W. */ + if (new_distance < w->distance) + { + ospf_spf_flush_parents (w); + w->distance = new_distance; + } - /* new parent is <= existing parents, add it */ + /* 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; } -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); - } -} - /* 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 +static unsigned int ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v, struct vertex *w, struct router_lsa_link *l) { @@ -464,6 +469,7 @@ ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v, struct vertex_nexthop *nh; struct vertex_parent *vp; struct ospf_interface *oi = NULL; + unsigned int added = 0; if (IS_DEBUG_OSPF_EVENT) { @@ -571,7 +577,8 @@ ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v, nh = vertex_nexthop_new (); nh->oi = oi; nh->router = l2->link_data; - ospf_spf_add_parent (v, w, nh); + ospf_spf_add_parent (v, w, nh, l); + return 1; } else zlog_info("ospf_nexthop_calculation(): " @@ -596,13 +603,14 @@ ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v, nh = vertex_nexthop_new (); nh->oi = vl_data->nexthop.oi; nh->router = vl_data->nexthop.router; - ospf_spf_add_parent (v, w, nh); + ospf_spf_add_parent (v, w, nh, l); + return 1; } else - zlog_info("ospf_nexthop_calculation(): " - "vl_data for VL link not found"); + zlog_info("ospf_nexthop_calculation(): " + "vl_data for VL link not found"); } /* end virtual-link from V to W */ - return; + return 0; } /* end W is a Router vertex */ else { @@ -613,13 +621,13 @@ ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v, nh = vertex_nexthop_new (); nh->oi = oi; nh->router.s_addr = 0; - ospf_spf_add_parent (v, w, nh); - return; + ospf_spf_add_parent (v, w, nh, l); + return 1; } } zlog_info("ospf_nexthop_calculation(): " "Unknown attached link"); - return; + 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) @@ -647,11 +655,12 @@ ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v, nh = vertex_nexthop_new (); nh->oi = vp->nexthop->oi; nh->router = l->link_data; - ospf_spf_add_parent (v, w, nh); + added = 1; + ospf_spf_add_parent (v, w, nh, l); } - return; } } + return added; } /* 16.1.1 para 4. If there is at least one intervening router in the @@ -660,9 +669,12 @@ ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v, * parent. */ for (ALL_LIST_ELEMENTS (v->parents, node, nnode, vp)) - ospf_spf_add_parent (v, w, vp->nexthop); + { + added = 1; + ospf_spf_add_parent (v, w, vp->nexthop, l); + } - return; + return added; } /* RFC2328 Section 16.1 (2). @@ -801,12 +813,11 @@ ospf_spf_next (struct vertex *v, struct ospf_area *area, { /* prepare vertex W. */ w = ospf_vertex_new (w_lsa); + w->distance = distance; /* Calculate nexthop to W. */ - w->distance = distance; - - ospf_nexthop_calculation (area, v, w, l); - pqueue_enqueue (w, candidate); + if (ospf_nexthop_calculation (area, v, w, l)) + pqueue_enqueue (w, candidate); } else if (w_lsa->stat >= 0) { @@ -828,17 +839,15 @@ ospf_spf_next (struct vertex *v, struct ospf_area *area, /* less than. */ else { - /* 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); - - /* Decrease the key of the node in the heap, re-sort the heap. */ - trickle_down (w_lsa->stat, candidate); + /* 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)) + /* Decrease the key of the node in the heap, + * re-sort the heap. */ + trickle_down (w_lsa->stat, candidate); } } /* end W is already on the candidate list */ } /* end loop over the links in V's LSA */ -- cgit v1.2.3 From bd34fb346db5bb1f0bc8eeeef1868e296d889053 Mon Sep 17 00:00:00 2001 From: Paul Jakma Date: Mon, 26 Feb 2007 17:14:48 +0000 Subject: [ospfd] Fix regression in SPF introduced by bug#330 fixes 2007-02-26 Paul Jakma * ospf_spf.c: Fix regression introduced with bug #330 fix: The cost update added to ospf_spf_add_parent only handled PtP case, differing from same functionality in higher-level ospf_spf_next. Regression diagnosed by Anders Pedersen, mailnews+router-quagga-dev@news.cohaesio.com. (ospf_vertex_new) Initialise vertices to max-cost. (ospf_spf_init) Root vertex always creates with 0 cost. (ospf_spf_add_parent) Remove the buggy V->W cost calculating code, instead take the new distance as a parameter. (ospf_nexthop_calculation) Take distance as parameter, so it can be passed down to add_parent. (ospf_spf_next) Dont initialise candiate vertex distance, vertex_new does so already. Pass distance down to nexthop_calculation (see above). --- ospfd/ospf_spf.c | 46 +++++++++++++++++++++++++--------------------- 1 file changed, 25 insertions(+), 21 deletions(-) (limited to 'ospfd/ospf_spf.c') diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c index f4adc114..cd5ebb16 100644 --- a/ospfd/ospf_spf.c +++ b/ospfd/ospf_spf.c @@ -172,7 +172,7 @@ ospf_vertex_new (struct ospf_lsa *lsa) new->type = lsa->data->type; new->id = lsa->data->id; new->lsa = lsa->data; - new->distance = 0; + new->distance = OSPF_OUTPUT_COST_INFINITE; new->children = list_new (); new->parents = list_new (); new->parents->del = vertex_parent_free; @@ -285,7 +285,8 @@ ospf_spf_init (struct ospf_area *area) /* Create root node. */ v = ospf_vertex_new (area->router_lsa_self); - + v->distance = 0; + area->spf = v; /* Reset ABR and ASBR router counts. */ @@ -426,26 +427,23 @@ ospf_spf_flush_parents (struct vertex *w) static void ospf_spf_add_parent (struct vertex *v, struct vertex *w, struct vertex_nexthop *newhop, - struct router_lsa_link *l) + unsigned int distance) { struct vertex_parent *vp; - unsigned int new_distance; /* we must have a newhop.. */ - assert (v && w && l && newhop); - - new_distance = v->distance + ntohs (l->m[0].metric); + assert (v && w && newhop); /* We shouldn't get here unless callers have determined V(l)->W is * shortest / equal-shortest path. */ - assert (new_distance <= w->distance); + assert (distance <= w->distance); /* Adding parent for a new, better path: flush existing parents from W. */ - if (new_distance < w->distance) + if (distance < w->distance) { ospf_spf_flush_parents (w); - w->distance = new_distance; + w->distance = distance; } /* new parent is <= existing parents, add it to parent list */ @@ -456,14 +454,20 @@ ospf_spf_add_parent (struct vertex *v, struct vertex *w, } /* 16.1.1. Calculate nexthop from root through V (parent) to - * vertex W (destination). + * 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) + struct vertex *w, struct router_lsa_link *l, + unsigned int distance) { struct listnode *node, *nnode; struct vertex_nexthop *nh; @@ -476,6 +480,7 @@ ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v, 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) @@ -577,7 +582,7 @@ ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v, nh = vertex_nexthop_new (); nh->oi = oi; nh->router = l2->link_data; - ospf_spf_add_parent (v, w, nh, l); + ospf_spf_add_parent (v, w, nh, distance); return 1; } else @@ -603,7 +608,7 @@ ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v, nh = vertex_nexthop_new (); nh->oi = vl_data->nexthop.oi; nh->router = vl_data->nexthop.router; - ospf_spf_add_parent (v, w, nh, l); + ospf_spf_add_parent (v, w, nh, distance); return 1; } else @@ -621,7 +626,7 @@ ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v, nh = vertex_nexthop_new (); nh->oi = oi; nh->router.s_addr = 0; - ospf_spf_add_parent (v, w, nh, l); + ospf_spf_add_parent (v, w, nh, distance); return 1; } } @@ -656,7 +661,7 @@ ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v, nh->oi = vp->nexthop->oi; nh->router = l->link_data; added = 1; - ospf_spf_add_parent (v, w, nh, l); + ospf_spf_add_parent (v, w, nh, distance); } } } @@ -671,7 +676,7 @@ ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v, for (ALL_LIST_ELEMENTS (v->parents, node, nnode, vp)) { added = 1; - ospf_spf_add_parent (v, w, vp->nexthop, l); + ospf_spf_add_parent (v, w, vp->nexthop, distance); } return added; @@ -813,10 +818,9 @@ ospf_spf_next (struct vertex *v, struct ospf_area *area, { /* prepare vertex W. */ w = ospf_vertex_new (w_lsa); - w->distance = distance; /* Calculate nexthop to W. */ - if (ospf_nexthop_calculation (area, v, w, l)) + if (ospf_nexthop_calculation (area, v, w, l, distance)) pqueue_enqueue (w, candidate); } else if (w_lsa->stat >= 0) @@ -834,7 +838,7 @@ ospf_spf_next (struct vertex *v, struct ospf_area *area, { /* Found an equal-cost path to W. * Calculate nexthop of to W from V. */ - ospf_nexthop_calculation (area, v, w, l); + ospf_nexthop_calculation (area, v, w, l, distance); } /* less than. */ else @@ -844,7 +848,7 @@ ospf_spf_next (struct vertex *v, struct ospf_area *area, * valid nexthop it will call spf_add_parents, which * will flush the old parents */ - if (ospf_nexthop_calculation (area, v, w, l)) + if (ospf_nexthop_calculation (area, v, w, l, distance)) /* Decrease the key of the node in the heap, * re-sort the heap. */ trickle_down (w_lsa->stat, candidate); -- cgit v1.2.3 From b75ae99e1d95685869fb38049e1936129fe17fc9 Mon Sep 17 00:00:00 2001 From: Paul Jakma Date: Fri, 23 Mar 2007 11:17:28 +0000 Subject: [ospfd] Instrument ospf_spf with more debug log messages 2007-03-23 Paul Jakma * ospf_spf.c: (various) Add more debug statements. --- ospfd/ospf_spf.c | 42 +++++++++++++++++++++++++++++++++++++++--- 1 file changed, 39 insertions(+), 3 deletions(-) (limited to 'ospfd/ospf_spf.c') diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c index cd5ebb16..f6e5e663 100644 --- a/ospfd/ospf_spf.c +++ b/ospfd/ospf_spf.c @@ -439,9 +439,21 @@ ospf_spf_add_parent (struct vertex *v, struct vertex *w, */ assert (distance <= w->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; } @@ -673,6 +685,9 @@ ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v, * 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; @@ -705,7 +720,13 @@ ospf_spf_next (struct vertex *v, struct ospf_area *area, 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); @@ -774,16 +795,29 @@ ospf_spf_next (struct vertex *v, struct ospf_area *area, /* 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) - continue; + { + if (IS_DEBUG_OSPF_EVENT) + zlog_debug ("No LSA found"); + continue; + } if (IS_LSA_MAXAGE (w_lsa)) - continue; + { + if (IS_DEBUG_OSPF_EVENT) + zlog_debug ("LSA is MaxAge"); + continue; + } if (ospf_lsa_has_link (w_lsa->data, v->lsa) < 0 ) { @@ -822,6 +856,8 @@ ospf_spf_next (struct vertex *v, struct ospf_area *area, /* 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) { -- cgit v1.2.3 From 85ef784e8a41a6dd11da42e10368f80c8bdb99d8 Mon Sep 17 00:00:00 2001 From: Paul Jakma Date: Fri, 23 Mar 2007 11:19:08 +0000 Subject: [ospfd] Bug #330 regression: failure to calculate routes through networks 2007-03-23 Paul Jakma * ospf_spf.c: (ospf_nexthop_calculation) Fix silly regression causing ospfd to fail to calculate paths past networks not attached to root vertex, introduced with bug #330 fixes. --- ospfd/ospf_spf.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'ospfd/ospf_spf.c') diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c index f6e5e663..c8cbe3f6 100644 --- a/ospfd/ospf_spf.c +++ b/ospfd/ospf_spf.c @@ -677,7 +677,8 @@ ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v, } } } - return added; + if (added) + return added; } /* 16.1.1 para 4. If there is at least one intervening router in the -- cgit v1.2.3 From 08d3d5b398ae81de7659509f159e814d1bbd4375 Mon Sep 17 00:00:00 2001 From: Paul Jakma Date: Mon, 7 May 2007 16:38:35 +0000 Subject: [ospfd] Bug #330 regression: Fix ospf_spf_add_parent assert 2007-05-07 Paul Jakma * ospf_spf.c: (ospf_vertex_new) Dont init vertices to infinity, just let 0 be a special case. (ospf_spf_add_parent) 0 distance candidate vertex is special, cost still to be initialised - asserting that new distance is <= existing only makes sense where w already has a cost. (ospf_spf_next) Infinite cost links should not be followed, bar those of the root. --- ospfd/ospf_spf.c | 22 ++++++++++++++++------ 1 file changed, 16 insertions(+), 6 deletions(-) (limited to 'ospfd/ospf_spf.c') diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c index c8cbe3f6..51e33832 100644 --- a/ospfd/ospf_spf.c +++ b/ospfd/ospf_spf.c @@ -172,7 +172,6 @@ ospf_vertex_new (struct ospf_lsa *lsa) new->type = lsa->data->type; new->id = lsa->data->id; new->lsa = lsa->data; - new->distance = OSPF_OUTPUT_COST_INFINITE; new->children = list_new (); new->parents = list_new (); new->parents->del = vertex_parent_free; @@ -285,7 +284,6 @@ ospf_spf_init (struct ospf_area *area) /* Create root node. */ v = ospf_vertex_new (area->router_lsa_self); - v->distance = 0; area->spf = v; @@ -431,13 +429,18 @@ ospf_spf_add_parent (struct vertex *v, struct vertex *w, { struct vertex_parent *vp; - /* we must have a newhop.. */ + /* we must have a newhop, and a distance */ assert (v && w && newhop); + assert (distance); - /* We shouldn't get here unless callers have determined V(l)->W is - * shortest / equal-shortest path. + /* 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)). */ - assert (distance <= w->distance); + if (w->distance) + assert (distance <= w->distance); + else + w->distance = distance; if (IS_DEBUG_OSPF_EVENT) { @@ -750,6 +753,13 @@ ospf_spf_next (struct vertex *v, struct ospf_area *area, 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 -- cgit v1.2.3 From 7591d8b862439dfae8b4b16d148ce567b6ff8cb7 Mon Sep 17 00:00:00 2001 From: Paul Jakma Date: Mon, 6 Aug 2007 18:52:45 +0000 Subject: [ospfd] Fix bad SPF calculation on some topologies - incorrect sorting 2007-08-07 Atis Elsts * ospf_spf.c: (ospf_spf_next) Sort heap in correct direction after vertex cost is changed, thus fixing incorrect SPF calculation on certain topologies. * lib/pqueue.{c,h}: Export trickle_up --- ospfd/ospf_spf.c | 9 ++++++--- 1 file changed, 6 insertions(+), 3 deletions(-) (limited to 'ospfd/ospf_spf.c') diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c index 51e33832..41288f1e 100644 --- a/ospfd/ospf_spf.c +++ b/ospfd/ospf_spf.c @@ -896,9 +896,12 @@ ospf_spf_next (struct vertex *v, struct ospf_area *area, * will flush the old parents */ if (ospf_nexthop_calculation (area, v, w, l, distance)) - /* Decrease the key of the node in the heap, - * re-sort the heap. */ - trickle_down (w_lsa->stat, candidate); + /* 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. + * (pqueu_{de,en}queue + */ + trickle_up (w_lsa->stat, candidate); } } /* end W is already on the candidate list */ } /* end loop over the links in V's LSA */ -- cgit v1.2.3 From e95537f0495401c0dd86669d096387e5cdddf8e0 Mon Sep 17 00:00:00 2001 From: Paul Jakma Date: Tue, 7 Aug 2007 16:22:05 +0000 Subject: [ospfd] Finish explanatory comment started in previous commit.. 2007-08-07 Paul Jakma * ospf_spf.c: (ospf_spf_next) Finish off the explanatory comment made in previous commit --- ospfd/ospf_spf.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'ospfd/ospf_spf.c') diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c index 41288f1e..23d45dd6 100644 --- a/ospfd/ospf_spf.c +++ b/ospfd/ospf_spf.c @@ -899,7 +899,7 @@ ospf_spf_next (struct vertex *v, struct ospf_area *area, /* 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. - * (pqueu_{de,en}queue + * (next pqueu_{de,en}queue will fully re-heap the queue). */ trickle_up (w_lsa->stat, candidate); } -- cgit v1.2.3 From 910e2704bee6bf78aee858db65f5393be618e683 Mon Sep 17 00:00:00 2001 From: Joakim Tjernlund Date: Wed, 20 Aug 2008 14:24:39 +0200 Subject: Ignore host routes to self. 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 --- ospfd/ospf_spf.c | 16 +++++++++++++++- 1 file changed, 15 insertions(+), 1 deletion(-) (limited to 'ospfd/ospf_spf.c') diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c index 23d45dd6..15d27be7 100644 --- a/ospfd/ospf_spf.c +++ b/ospfd/ospf_spf.c @@ -981,7 +981,21 @@ ospf_spf_process_stubs (struct ospf_area *area, struct vertex *v, (l->m[0].tos_count * ROUTER_LSA_TOS_SIZE)); if (l->m[0].type == LSA_LINK_TYPE_STUB) - ospf_intra_add_stub (rt, l, v, area); + { + /* 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); + } } } -- cgit v1.2.3 From b3bc68e5a4eecd85138463ae5742c2ccaa1db4bb Mon Sep 17 00:00:00 2001 From: Paul Jakma Date: Thu, 4 Sep 2008 13:52:07 +0100 Subject: [ospfd] Minor enhancements to recent self-host-routes suppression patch * ospf_spf.c: (ospf_spf_process_stubs) Track whether parent router vertex is the root, so that the host-route suppression logic need only be activated for such vertices. Move the actual logic to ospf_intra_add_stub. * ospf_route.c: (ospf_intra_add_stub) Main test of link moved here, notionally more appropriate. --- ospfd/ospf_spf.c | 34 +++++++++++++++------------------- 1 file changed, 15 insertions(+), 19 deletions(-) (limited to 'ospfd/ospf_spf.c') diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c index 15d27be7..82f0fedd 100644 --- a/ospfd/ospf_spf.c +++ b/ospfd/ospf_spf.c @@ -946,7 +946,8 @@ ospf_spf_dump (struct vertex *v, int i) /* Second stage of SPF calculation. */ static void ospf_spf_process_stubs (struct ospf_area *area, struct vertex *v, - struct route_table *rt) + struct route_table *rt, + int parent_is_root) { struct listnode *cnode, *cnnode; struct vertex *child; @@ -981,21 +982,7 @@ ospf_spf_process_stubs (struct ospf_area *area, struct vertex *v, (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_intra_add_stub (rt, l, v, area, parent_is_root); } } @@ -1005,8 +992,17 @@ ospf_spf_process_stubs (struct ospf_area *area, struct vertex *v, { if (CHECK_FLAG (child->flags, OSPF_VERTEX_PROCESSED)) continue; - - ospf_spf_process_stubs (area, child, rt); + + /* the first level of routers connected to the root + * should have 'parent_is_root' set, including those + * connected via a network vertex. + */ + if (area->spf == v) + parent_is_root = 1; + else if (v->type == OSPF_VERTEX_ROUTER) + parent_is_root = 0; + + ospf_spf_process_stubs (area, child, rt, parent_is_root); SET_FLAG (child->flags, OSPF_VERTEX_PROCESSED); } @@ -1193,7 +1189,7 @@ 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); + ospf_spf_process_stubs (area, area->spf, new_table, 0); /* Free candidate queue. */ pqueue_delete (candidate); -- cgit v1.2.3