2004-08-04 Paul Jakma <paul@dishone.st>

        * 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.

2 files changed, 48 insertions, 19 deletions

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 <paul@dishone.st>
+
+	* 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 <paul@dishone.st>
 
         * 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;
             }