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.

1 files changed, 32 insertions, 11 deletions

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);
 }