summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorPaul Jakma <paul.jakma@sun.com>2007-02-26 17:14:48 +0000
committerPaul Jakma <paul.jakma@sun.com>2007-02-26 17:14:48 +0000
commitbd34fb346db5bb1f0bc8eeeef1868e296d889053 (patch)
treed29904361a06e21d77fc5cbb163c39dd327962fe
parentff1dd550b01fd6bb4aa137cfee282e6175f89c50 (diff)
[ospfd] Fix regression in SPF introduced by bug#330 fixes
2007-02-26 Paul Jakma <paul.jakma@sun.com> * 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).
-rw-r--r--ospfd/ChangeLog17
-rw-r--r--ospfd/ospf_spf.c46
2 files changed, 42 insertions, 21 deletions
diff --git a/ospfd/ChangeLog b/ospfd/ChangeLog
index d026bf88..35ffd69d 100644
--- a/ospfd/ChangeLog
+++ b/ospfd/ChangeLog
@@ -1,3 +1,20 @@
+2007-02-26 Paul Jakma <paul.jakma@sun.com>
+
+ * 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).
+
2007-01-24 Paul Jakma <paul.jakma@sun.com>
* ospf_spf.c: Bug #330: Nexthop calculation sometimes may fail,
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);