From 75ee0b8eed29619b98c67dcb5f6b10e1c8f201ae Mon Sep 17 00:00:00 2001 From: paul Date: Thu, 5 Aug 2004 09:10:31 +0000 Subject: 2004-08-04 Paul Jakma * ospf_spf.c: (ospf_spf_consider_nexthop) Add comment about issue. Compare only against list head - all nexthops must be same cost anyway, fixes a reference-listnode-after-delete bug noted by Kir Kostuchenko. (ospf_nexthop_calculation) Use ospf_spf_consider_nexthop for all candidates attached to root. --- ospfd/ChangeLog | 9 +++++++++ ospfd/ospf_spf.c | 58 +++++++++++++++++++++++++++++++++++++------------------- 2 files changed, 48 insertions(+), 19 deletions(-) (limited to 'ospfd') diff --git a/ospfd/ChangeLog b/ospfd/ChangeLog index 369822d9..4bbc2caf 100644 --- a/ospfd/ChangeLog +++ b/ospfd/ChangeLog @@ -1,3 +1,12 @@ +2004-08-04 Paul Jakma + + * ospf_spf.c: (ospf_spf_consider_nexthop) Add comment about issue. + Compare only against list head - all nexthops must be same cost + anyway, fixes a reference-listnode-after-delete bug noted by + Kir Kostuchenko. + (ospf_nexthop_calculation) Use ospf_spf_consider_nexthop for all + candidates attached to root. + 2004-07-27 Paul Jakma * ospf_packet.c: (ospf_ls_upd_send_queue_event) fix thinko from diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c index 916e9800..5afdf161 100644 --- a/ospfd/ospf_spf.c +++ b/ospfd/ospf_spf.c @@ -341,31 +341,51 @@ ospf_get_next_link (struct vertex *v, struct vertex *w, return NULL; } -/* Consider supplied next-hop for inclusion to the supplied list - * of next-hops, adjust list as neccessary +/* + * 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. */ void ospf_spf_consider_nexthop (struct list *nexthops, struct vertex_nexthop *newhop) { - struct listnode *nnode; struct vertex_nexthop *hop; + struct listnode *ln, *nn; - LIST_LOOP (nexthops, hop, nnode) - { - assert (hop->oi); - /* weed out hops with higher cost than the newhop */ - if (hop->oi->output_cost > newhop->oi->output_cost) - { - /* delete the existing nexthop */ - listnode_delete (nexthops, hop); - vertex_nexthop_free (hop); - } - else if (hop->oi->output_cost < newhop->oi->output_cost) - { + /* nexthop list should contain only the set of nexthops that have the lowest + * equal cost + */ + if (nexthops->head != NULL) + { + hop = getdata (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 (ln = nexthops->head; ln; ln = nn) + { + nn = ln->next; + hop = getdata (ln); + + listnode_delete (nexthops, hop); + vertex_nexthop_free (hop); + } + } + else if (hop->oi->output_cost < newhop->oi->output_cost) return; - } - } + } /* new hop is <= existing hops, add it */ listnode_add (nexthops, newhop); @@ -455,7 +475,7 @@ ospf_nexthop_calculation (struct ospf_area *area, nh = vertex_nexthop_new (v); nh->oi = oi; nh->router.s_addr = 0; - listnode_add (w->nexthop, nh); + ospf_spf_consider_nexthop (w->nexthop, nh); } } } @@ -474,7 +494,7 @@ ospf_nexthop_calculation (struct ospf_area *area, nh = vertex_nexthop_new (v); nh->oi = x->oi; nh->router = l->link_data; - listnode_add (w->nexthop, nh); + ospf_spf_consider_nexthop (w->nexthop, nh); } return; } -- cgit v1.2.1