zebra: rib update in background and recursive routes

Right now Zebra doesn't support recursive routes correctly when
the next hop is a dynamic protocol. Imagine the case where a static
route was entered to destination X.X.X.X via Y.Y.Y.Y and a protocol
created a route to Y.Y.Y.Y.  Any change from that protocol to
Y.Y.Y.Y would might require zebra to update it's recursive route.

The RIB as is doesn't have the necessary state to do this quickly,
and the rib_update() and the resulting meta-queue is slow (2N) with
lots of routes. That combined with the incremental updates from
protocols makes the whole process potentially N^2. When we enabled
it for BGP, the feed to 30min to complete.

The comprimise I took was to start a delayed thread when zebra receives
an update from protocol. So only a limited number of scans are done.

I know this conflicts with your cleanup; but this might provide additional
help. The existing meta-queue stuff makes the rib update worse not
better.

4 files changed, 44 insertions, 11 deletions

diff --git a/zebra/rib.h b/zebra/rib.h
index 887ed3c2..499d48b2 100644
--- a/zebra/rib.h
+++ b/zebra/rib.h
@@ -262,6 +262,7 @@ extern struct rib *rib_match_ipv4 (struct in_addr);
 extern struct rib *rib_lookup_ipv4 (struct prefix_ipv4 *);
 
 extern void rib_update (void);
+extern void rib_update_background (void);
 extern void rib_weed_tables (void);
 extern void rib_sweep_route (void);
 extern void rib_close (void);
diff --git a/zebra/zebra_rib.c b/zebra/zebra_rib.c
index 12f3fa5a..40b012fc 100644
--- a/zebra/zebra_rib.c
+++ b/zebra/zebra_rib.c
@@ -1332,7 +1332,6 @@ rib_queue_init (struct zebra_t *zebra)
   zebra->ribq->spec.errorfunc = NULL;
   /* XXX: TODO: These should be runtime configurable via vty */
   zebra->ribq->spec.max_retries = 3;
-  zebra->ribq->spec.hold = rib_process_hold_time;
   
   if (!(zebra->mq = meta_queue_new ()))
     zlog_err ("%s: could not initialise meta queue!", __func__);
@@ -2791,23 +2790,45 @@ static_delete_ipv6 (struct prefix *p, u_char type, struct in6_addr *gate,
 #endif /* HAVE_IPV6 */
 
 /* RIB update function. */
-void
-rib_update (void)
+static void
+rib_update_table (struct table *table)
 {
   struct route_node *rn;
-  struct route_table *table;
-  
-  table = vrf_table (AFI_IP, SAFI_UNICAST, 0);
   if (table)
     for (rn = route_top (table); rn; rn = route_next (rn))
       if (rn->info)
         rib_queue_add (&zebrad, rn);
+}
 
-  table = vrf_table (AFI_IP6, SAFI_UNICAST, 0);
-  if (table)
-    for (rn = route_top (table); rn; rn = route_next (rn))
-      if (rn->info)
-        rib_queue_add (&zebrad, rn);
+void
+rib_update (void)
+{
+  if (zebrad.update)
+    {
+      thread_cancel (zebrad.update);
+      zebrad.update = NULL;
+    }
+
+  rib_update_table (vrf_table (AFI_IP, SAFI_UNICAST, 0));
+
+#ifdef HAVE_IPV6
+  rib_update_table (vrf_table (AFI_IP6, SAFI_UNICAST, 0));
+#endif
+}
+
+static int
+rib_update_thread (struct thread *self)
+{
+  rib_update ();
+  return 0;
+}
+
+void
+rib_update_background (void)
+{
+  if (!zebrad.update)
+    zebrad.update = thread_add_background (zebrad.master, rib_update_thread,
+					   NULL, rib_process_hold_time);
 }
 
 
diff --git a/zebra/zserv.c b/zebra/zserv.c
index cb5e411c..de84d95d 100644
--- a/zebra/zserv.c
+++ b/zebra/zserv.c
@@ -804,6 +804,8 @@ zread_ipv4_add (struct zserv *client, u_short length)
   /* Table */
   rib->table=zebrad.rtm_table_default;
   rib_add_ipv4_multipath (&p, rib);
+
+  rib_update_background ();
   return 0;
 }
 
@@ -878,6 +880,8 @@ zread_ipv4_delete (struct zserv *client, u_short length)
     
   rib_delete_ipv4 (api.type, api.flags, &p, &nexthop, ifindex,
 		   client->rtm_table);
+
+  rib_update_background ();
   return 0;
 }
 
@@ -969,6 +973,8 @@ zread_ipv6_add (struct zserv *client, u_short length)
   else
     rib_add_ipv6 (api.type, api.flags, &p, &nexthop, ifindex, zebrad.rtm_table_default, api.metric,
 		  api.distance);
+
+  rib_update_background ();
   return 0;
 }
 
@@ -1033,6 +1039,8 @@ zread_ipv6_delete (struct zserv *client, u_short length)
     rib_delete_ipv6 (api.type, api.flags, &p, NULL, ifindex, client->rtm_table);
   else
     rib_delete_ipv6 (api.type, api.flags, &p, &nexthop, ifindex, client->rtm_table);
+
+  rib_update_background ();
   return 0;
 }
 
diff --git a/zebra/zserv.h b/zebra/zserv.h
index a7371830..13c4a651 100644
--- a/zebra/zserv.h
+++ b/zebra/zserv.h
@@ -81,6 +81,9 @@ struct zebra_t
   /* rib work queue */
   struct work_queue *ribq;
   struct meta_queue *mq;
+
+  /* rib update thread */
+  struct thread *update;
 };
 
 /* Count prefix size from mask length */