KRT: Improve syncer code to avoid using temporary data in rtable

The old code stored route verdicts and temporary routes directly in
rtable. The new code do not store received routes (it immediately
compares them with exported routes and resolves conflicts) and uses
internal bitmap to keep track of which routes were received and which
needs to be reinstalled.

By not putting 'invalid' temporary routes to rtable, we keep rtable
in consistent state, therefore scan no longer needs to be atomic
operation and could be splitted to multiple events.

1 files changed, 75 insertions, 100 deletions

diff --git a/sysdep/unix/krt.c b/sysdep/unix/krt.c
index 84207251..42dd12f6 100644
--- a/sysdep/unix/krt.c
+++ b/sysdep/unix/krt.c
@@ -625,19 +625,17 @@ krt_same_dest(rte *k, rte *e)
 void
 krt_got_route(struct krt_proto *p, rte *e)
 {
-  net *net = e->net;
-  int verdict;
+  rte *new = NULL, *rt_free = NULL;
+  net *n = e->net;
 
 #ifdef KRT_ALLOW_LEARN
   switch (e->u.krt.src)
     {
     case KRT_SRC_KERNEL:
-      verdict = KRF_IGNORE;
-      goto sentenced;
+      goto ignore;
 
     case KRT_SRC_REDIRECT:
-      verdict = KRF_DELETE;
-      goto sentenced;
+      goto delete;
 
     case  KRT_SRC_ALIEN:
       if (KRT_CF->learn)
@@ -652,58 +650,68 @@ krt_got_route(struct krt_proto *p, rte *e)
 #endif
   /* The rest is for KRT_SRC_BIRD (or KRT_SRC_UNKNOWN) */
 
-  if (net->n.flags & KRF_VERDICT_MASK)
-    {
-      /* Route to this destination was already seen. Strange, but it happens... */
-      krt_trace_in(p, e, "already seen");
-      rte_free(e);
-      return;
-    }
 
+  /* We wait for the initial feed to have correct installed state */
   if (!p->ready)
-    {
-      /* We wait for the initial feed to have correct installed state */
-      verdict = KRF_IGNORE;
-      goto sentenced;
-    }
+    goto ignore;
 
-  if (krt_is_installed(p, net))
-    {
-      rte *new, *rt_free;
+  if (!krt_is_installed(p, n))
+    goto delete;
 
-      new = krt_export_net(p, net, &rt_free);
+  new = krt_export_net(p, n, &rt_free);
 
-      /* TODO: There also may be changes in route eattrs, we ignore that for now. */
+  /* Rejected by filters */
+  if (!new)
+    goto delete;
 
-      if (!new)
-	verdict = KRF_DELETE;
-      else if (!bmap_test(&p->sync_map, new->id) || !krt_same_dest(e, new))
-	verdict = KRF_UPDATE;
-      else
-	verdict = KRF_SEEN;
+  /* Route to this destination was already seen. Strange, but it happens... */
+  if (bmap_test(&p->seen_map, new->id))
+    goto aseen;
 
-      if (rt_free)
-	rte_free(rt_free);
+  /* Mark route as seen */
+  bmap_set(&p->seen_map, new->id);
 
-      lp_flush(krt_filter_lp);
-    }
-  else
-    verdict = KRF_DELETE;
+  /* TODO: There also may be changes in route eattrs, we ignore that for now. */
+  if (!bmap_test(&p->sync_map, new->id) || !krt_same_dest(e, new))
+    goto update;
 
- sentenced:
-  krt_trace_in(p, e, ((char *[]) { "?", "seen", "will be updated", "will be removed", "ignored" }) [verdict]);
-  net->n.flags = (net->n.flags & ~KRF_VERDICT_MASK) | verdict;
-  if (verdict == KRF_UPDATE || verdict == KRF_DELETE)
-    {
-      /* Get a cached copy of attributes and temporarily link the route */
-      rta *a = e->attrs;
-      a->source = RTS_DUMMY;
-      e->attrs = rta_lookup(a);
-      e->next = net->routes;
-      net->routes = e;
-    }
-  else
-    rte_free(e);
+  goto seen;
+
+seen:
+  krt_trace_in(p, e, "seen");
+  goto done;
+
+aseen:
+  krt_trace_in(p, e, "already seen");
+  goto done;
+
+ignore:
+  krt_trace_in(p, e, "ignored");
+  goto done;
+
+update:
+  krt_trace_in(p, new, "updating");
+  krt_replace_rte(p, n, new, e);
+  goto done;
+
+delete:
+  krt_trace_in(p, e, "deleting");
+  krt_replace_rte(p, n, NULL, e);
+  goto done;
+
+done:
+  rte_free(e);
+
+  if (rt_free)
+    rte_free(rt_free);
+
+  lp_flush(krt_filter_lp);
+}
+
+static void
+krt_init_scan(struct krt_proto *p)
+{
+  bmap_reset(&p->seen_map, 1024);
 }
 
 static void
@@ -713,59 +721,24 @@ krt_prune(struct krt_proto *p)
 
   KRT_TRACE(p, D_EVENTS, "Pruning table %s", t->name);
   FIB_WALK(&t->fib, net, n)
+  {
+    if (p->ready && krt_is_installed(p, n) && !bmap_test(&p->seen_map, n->routes->id))
     {
-      int verdict = n->n.flags & KRF_VERDICT_MASK;
-      rte *new, *old, *rt_free = NULL;
+      rte *rt_free = NULL;
+      rte *new = krt_export_net(p, n, &rt_free);
 
-      if (verdict == KRF_UPDATE || verdict == KRF_DELETE)
-	{
-	  /* Get a dummy route from krt_got_route() */
-	  old = n->routes;
-	  n->routes = old->next;
-	}
-      else
-	old = NULL;
-
-      if (verdict == KRF_CREATE || verdict == KRF_UPDATE)
-	{
-	  /* We have to run export filter to get proper 'new' route */
-	  new = krt_export_net(p, n, &rt_free);
-
-	  if (!new)
-	    verdict = (verdict == KRF_CREATE) ? KRF_IGNORE : KRF_DELETE;
-	}
-      else
-	new = NULL;
-
-      switch (verdict)
-	{
-	case KRF_CREATE:
-	  krt_trace_in(p, new, "reinstalling");
-	  krt_replace_rte(p, n, new, NULL);
-	  break;
-	case KRF_SEEN:
-	case KRF_IGNORE:
-	  /* Nothing happens */
-	  break;
-	case KRF_UPDATE:
-	  krt_trace_in(p, new, "updating");
-	  krt_replace_rte(p, n, new, old);
-	  break;
-	case KRF_DELETE:
-	  krt_trace_in(p, old, "deleting");
-	  krt_replace_rte(p, n, NULL, old);
-	  break;
-	default:
-	  bug("krt_prune: invalid route status");
-	}
+      if (new)
+      {
+	krt_trace_in(p, new, "installing");
+	krt_replace_rte(p, n, new, NULL);
+      }
 
-      if (old)
-	rte_free(old);
       if (rt_free)
 	rte_free(rt_free);
+
       lp_flush(krt_filter_lp);
-      n->n.flags &= ~KRF_VERDICT_MASK;
     }
+  }
   FIB_WALK_END;
 
 #ifdef KRT_ALLOW_LEARN
@@ -823,6 +796,7 @@ static void
 krt_scan(timer *t UNUSED)
 {
   struct krt_proto *p;
+  node *n;
 
   kif_force_scan();
 
@@ -830,14 +804,13 @@ krt_scan(timer *t UNUSED)
   p = SKIP_BACK(struct krt_proto, krt_node, HEAD(krt_proto_list));
   KRT_TRACE(p, D_EVENTS, "Scanning routing table");
 
+  WALK_LIST2(p, n, krt_proto_list, krt_node)
+    krt_init_scan(p);
+
   krt_do_scan(NULL);
 
-  void *q;
-  WALK_LIST(q, krt_proto_list)
-  {
-    p = SKIP_BACK(struct krt_proto, krt_node, q);
+  WALK_LIST2(p, n, krt_proto_list, krt_node)
     krt_prune(p);
-  }
 }
 
 static void
@@ -879,6 +852,7 @@ krt_scan(timer *t)
   kif_force_scan();
 
   KRT_TRACE(p, D_EVENTS, "Scanning routing table");
+  krt_init_scan(p);
   krt_do_scan(p);
   krt_prune(p);
 }
@@ -1095,6 +1069,7 @@ krt_start(struct proto *P)
   }
 
   bmap_init(&p->sync_map, p->p.pool, 1024);
+  bmap_init(&p->seen_map, p->p.pool, 1024);
   add_tail(&krt_proto_list, &p->krt_node);
 
 #ifdef KRT_ALLOW_LEARN