Implements deterministic MED handling.

Thanks to Alexander V. Chernikov for many suggestions.

4 files changed, 56 insertions, 16 deletions

diff --git a/nest/proto-hooks.c b/nest/proto-hooks.c
index f0261922..2582c48b 100644
--- a/nest/proto-hooks.c
+++ b/nest/proto-hooks.c
@@ -268,6 +268,26 @@ int import_control(struct proto *p, rte **e, ea_list **attrs, struct linpool *po
 { DUMMY; }
 
 /**
+ * rte_recalculate - prepare routes for comparison
+ * @table: a routing table 
+ * @net: a network entry
+ * @new: new route for the network
+ * @old: old route for the network
+ * @old_best: old best route for the network (may be NULL)
+ *
+ * This hook is called when a route change (from @old to @new for a
+ * @net entry) is propagated to a @table. It may be used to prepare
+ * routes for comparison by rte_better() in the best route
+ * selection. @new may or may not be in @net->routes list,
+ * @old is not there.
+ *
+ * Result: 1 if the ordering implied by rte_better() changes enough
+ * that full best route calculation have to be done, 0 otherwise.
+ */
+int rte_recalculate(struct rtable *table, struct network *net, struct rte *new, struct rte *old, struct rte *old_best)
+{ DUMMY; }
+
+/**
  * rte_better - compare metrics of two routes
  * @new: the new route
  * @old: the original route
diff --git a/nest/protocol.h b/nest/protocol.h
index a7518c2a..3766e15e 100644
--- a/nest/protocol.h
+++ b/nest/protocol.h
@@ -178,12 +178,14 @@ struct proto {
   /*
    *	Routing entry hooks (called only for rte's belonging to this protocol):
    *
+   *	   rte_recalculate Called at the beginning of the best route selection  
    *	   rte_better	Compare two rte's and decide which one is better (1=first, 0=second).
    *       rte_same	Compare two rte's and decide whether they are identical (1=yes, 0=no).
    *	   rte_insert	Called whenever a rte is inserted to a routing table.
    *	   rte_remove	Called whenever a rte is removed from the routing table.
    */
 
+  int (*rte_recalculate)(struct rtable *, struct network *, struct rte *, struct rte *, struct rte *);
   int (*rte_better)(struct rte *, struct rte *);
   int (*rte_same)(struct rte *, struct rte *);
   void (*rte_insert)(struct network *, struct rte *);
diff --git a/nest/route.h b/nest/route.h
index a4c01548..e6712c64 100644
--- a/nest/route.h
+++ b/nest/route.h
@@ -201,6 +201,11 @@ typedef struct rte {
       u32 router_id;			/* Router that originated this route */
     } ospf;
 #endif
+#ifdef CONFIG_BGP
+    struct {
+      u8 suppressed;			/* Used for deterministic MED comparison */
+    } bgp;
+#endif
     struct {				/* Routes generated by krt sync (both temporary and inherited ones) */
       s8 src;				/* Alleged route source (see krt.h) */
       u8 proto;				/* Kernel source protocol ID */
diff --git a/nest/rt-table.c b/nest/rt-table.c
index e20d2f6d..377687de 100644
--- a/nest/rt-table.c
+++ b/nest/rt-table.c
@@ -498,6 +498,9 @@ rte_recalculate(rtable *table, net *net, struct proto *p, struct proto *src, rte
 
   rte_announce(table, RA_ANY, net, new, old, tmpa);
 
+  if (src->rte_recalculate && src->rte_recalculate(table, net, new, old, old_best))
+    goto do_recalculate;
+
   if (new && rte_better(new, old_best))
     {
       /* The first case - the new route is cleary optimal, we link it
@@ -516,6 +519,7 @@ rte_recalculate(rtable *table, net *net, struct proto *p, struct proto *src, rte
 	 that route at the first position and announce it. New optimal
 	 route might be NULL if there is no more routes */
 
+    do_recalculate:
       /* Add the new route to the list */
       if (new)
 	{
@@ -1015,27 +1019,36 @@ rt_next_hop_update_net(rtable *tab, net *n)
   if (!old_best)
     return 0;
 
-  new_best = NULL;
-
   for (k = &n->routes; e = *k; k = &e->next)
-    {
-      if (rta_next_hop_outdated(e->attrs))
-	{
-	  new = rt_next_hop_update_rte(tab, e);
-	  *k = new;
+    if (rta_next_hop_outdated(e->attrs))
+      {
+	new = rt_next_hop_update_rte(tab, e);
+	*k = new;
 
-	  rte_announce_i(tab, RA_ANY, n, new, e);
-	  rte_trace_in(D_ROUTES, new->sender, new, "updated");
+	rte_announce_i(tab, RA_ANY, n, new, e);
+	rte_trace_in(D_ROUTES, new->sender, new, "updated");
 
-	  if (e != old_best)
-	    rte_free_quick(e);
-	  else /* Freeing of the old best rte is postponed */
-	    free_old_best = 1;
+	/* Call a pre-comparison hook */
+	/* Not really an efficient way to compute this */
+	if (e->attrs->proto->rte_recalculate)
+	  e->attrs->proto->rte_recalculate(tab, n, new, e, NULL);
 
-	  e = new;
-	  count++;
-	}
+	if (e != old_best)
+	  rte_free_quick(e);
+	else /* Freeing of the old best rte is postponed */
+	  free_old_best = 1;
 
+	e = new;
+	count++;
+      }
+
+  if (!count)
+    return 0;
+
+  /* Find the new best route */
+  new_best = NULL;
+  for (k = &n->routes; e = *k; k = &e->next)
+    {
       if (!new_best || rte_better(e, *new_best))
 	new_best = k;
     }