Export tables merged with BGP prefix hash

Until now, if export table was enabled, Nest was storing exactly the
route before rt_notify() was called on it. This was quite sloppy and
spooky and it also wasn't reflecting the changes BGP does before
sending. And as BGP is storing the routes to be sent anyway, we are
simply keeping the already-sent routes in there to better rule out
unneeded reexports.

Some of the route attributes (IGP metric, preference) make no sense in
BGP, therefore these will be probably replaced by something sensible.
Also the nexthop shown in the short output is the BGP nexthop.

6 files changed, 60 insertions, 176 deletions

diff --git a/nest/config.Y b/nest/config.Y
index 7c163f74..edddfc2b 100644
--- a/nest/config.Y
+++ b/nest/config.Y
@@ -694,7 +694,7 @@ r_args:
    }
  | r_args EXPORT TABLE channel_arg {
      if (!$4->out_table) cf_error("No export table in channel %s.%s", $4->proto->name, $4->name);
-     rt_show_add_exporter($$, &$4->out_table->exporter, "export");
+     rt_show_add_exporter($$, $4->out_table, "export");
      $$->tables_defined_by = RSD_TDB_DIRECT;
    }
  | r_args FILTER filter {
diff --git a/nest/proto.c b/nest/proto.c
index e7be8001..061205c1 100644
--- a/nest/proto.c
+++ b/nest/proto.c
@@ -559,10 +559,6 @@ channel_export_stopped(struct rt_export_request *req)
     return;
   }
 
-  /* Free the routes from out_table */
-  if (c->out_table)
-    rt_prune_sync(c->out_table, 1);
-
   mb_free(c->out_req.name);
   c->out_req.name = NULL;
 
@@ -647,18 +643,6 @@ channel_setup_in_table(struct channel *c)
   c->in_keep |= RIK_PREFILTER;
 }
 
-/* Called by protocol to activate out_table */
-void
-channel_setup_out_table(struct channel *c)
-{
-  struct rtable_config *cf = mb_allocz(c->proto->pool, sizeof(struct rtable_config));
-  cf->name = "export";
-  cf->addr_type = c->net_type;
-  cf->internal = 1;
-
-  c->out_table = rt_setup(c->proto->pool, cf);
-}
-
 
 static void
 channel_do_start(struct channel *c)
diff --git a/nest/protocol.h b/nest/protocol.h
index a1701a7e..3ccd364a 100644
--- a/nest/protocol.h
+++ b/nest/protocol.h
@@ -537,7 +537,7 @@ struct channel {
   u8 refeed_pending;			/* Refeeding and another refeed is scheduled */
   u8 rpki_reload;			/* RPKI changes trigger channel reload */
 
-  struct rtable *out_table;		/* Internal table for exported routes */
+  struct rt_exporter *out_table;	/* Internal table for exported routes */
 
   list roa_subscriptions;		/* List of active ROA table subscriptions based on filters roa_check() */
 };
@@ -610,7 +610,6 @@ int proto_configure_channel(struct proto *p, struct channel **c, struct channel_
 
 void channel_set_state(struct channel *c, uint state);
 void channel_setup_in_table(struct channel *c);
-void channel_setup_out_table(struct channel *c);
 void channel_schedule_reload(struct channel *c);
 
 static inline void channel_init(struct channel *c) { channel_set_state(c, CS_START); }
diff --git a/nest/rt-attr.c b/nest/rt-attr.c
index a66d4c6e..b31bc5cc 100644
--- a/nest/rt-attr.c
+++ b/nest/rt-attr.c
@@ -197,11 +197,14 @@ static struct idm src_ids;
 #define RSH_INIT_ORDER		6
 
 static HASH(struct rte_src) src_hash;
+static struct rte_src **rte_src_global;
+static uint rte_src_global_max = SRC_ID_INIT_SIZE;
 
 static void
 rte_src_init(void)
 {
   rte_src_slab = sl_new(rta_pool, sizeof(struct rte_src));
+  rte_src_global = mb_allocz(rta_pool, sizeof(struct rte_src *) * rte_src_global_max);
 
   idm_init(&src_ids, rta_pool, SRC_ID_INIT_SIZE);
 
@@ -232,10 +235,27 @@ rt_get_source(struct proto *p, u32 id)
   src->uc = 0;
 
   HASH_INSERT2(src_hash, RSH, rta_pool, src);
+  if (src->global_id >= rte_src_global_max)
+  {
+    rte_src_global = mb_realloc(rte_src_global, sizeof(struct rte_src *) * (rte_src_global_max *= 2));
+    memset(&rte_src_global[rte_src_global_max / 2], 0,
+	sizeof(struct rte_src *) * (rte_src_global_max / 2));
+  }
+
+  rte_src_global[src->global_id] = src;
 
   return src;
 }
 
+struct rte_src *
+rt_find_source_global(u32 id)
+{
+  if (id >= rte_src_global_max)
+    return NULL;
+  else
+    return rte_src_global[id];
+}
+
 void
 rt_prune_sources(void)
 {
@@ -1081,8 +1101,11 @@ ea_show_nexthop_list(struct cli *c, struct nexthop_adata *nhad)
       bsprintf(weight, " weight %d", nh->weight + 1);
 
     if (ipa_nonzero(nh->gw))
-      cli_printf(c, -1007, "\tvia %I on %s%s%s%s",
-	  nh->gw, nh->iface->name, mpls, onlink, weight);
+      if (nh->iface)
+	cli_printf(c, -1007, "\tvia %I on %s%s%s%s",
+	    nh->gw, nh->iface->name, mpls, onlink, weight);
+      else
+	cli_printf(c, -1007, "\tvia %I", nh->gw);
     else
       cli_printf(c, -1007, "\tdev %s%s%s",
 	  nh->iface->name, mpls,  onlink, weight);
diff --git a/nest/rt-table.c b/nest/rt-table.c
index 5adf6346..29690414 100644
--- a/nest/rt-table.c
+++ b/nest/rt-table.c
@@ -820,17 +820,6 @@ do_rt_notify(struct channel *c, const net_addr *net, rte *new, const rte *old)
   if (!new && old)
     CHANNEL_LIMIT_POP(c, OUT);
 
-  /* Apply export table */
-  struct rte_storage *old_exported = NULL;
-  if (c->out_table)
-  {
-    if (!rte_update_out(c, net, new, old, &old_exported))
-    {
-      channel_rte_trace_out(D_ROUTES, c, new, "idempotent");
-      return;
-    }
-  }
-
   if (new)
     stats->updates_accepted++;
   else
@@ -852,10 +841,7 @@ do_rt_notify(struct channel *c, const net_addr *net, rte *new, const rte *old)
       channel_rte_trace_out(D_ROUTES, c, old, "removed");
   }
 
-  p->rt_notify(p, c, net, new, old_exported ? &old_exported->rte : old);
-
-  if (c->out_table && old_exported)
-    rte_free(old_exported);
+  p->rt_notify(p, c, net, new, old);
 }
 
 static void
@@ -1747,7 +1733,7 @@ rt_export_stopped(void *data)
   hook->stopped(hook->req);
 
   /* Reporting the hook as finished. */
-  tab->done(hook);
+  CALL(tab->done, hook);
 
   /* Freeing the hook together with its coroutine. */
   rfree(hook->pool);
@@ -1763,7 +1749,7 @@ rt_set_import_state(struct rt_import_hook *hook, u8 state)
     hook->req->log_state_change(hook->req, state);
 }
 
-static inline void
+void
 rt_set_export_state(struct rt_export_hook *hook, u8 state)
 {
   hook->last_state_change = current_time();
@@ -1874,16 +1860,22 @@ rt_table_export_stop(struct rt_export_hook *hook)
   if (hook->export_state != TES_FEEDING)
     return;
 
-  if (hook->walk_lock)
+  switch (hook->req->addr_mode)
   {
-    rt_unlock_trie(tab, hook->walk_lock);
-    hook->walk_lock = NULL;
-
-    mb_free(hook->walk_state);
-    hook->walk_state = NULL;
+    case TE_ADDR_IN:
+      if (hook->walk_lock)
+      {
+	rt_unlock_trie(tab, hook->walk_lock);
+	hook->walk_lock = NULL;
+	mb_free(hook->walk_state);
+	hook->walk_state = NULL;
+	break;
+      }
+      /* fall through */
+    case TE_ADDR_NONE:
+      fit_get(&tab->fib, &hook->feed_fit);
+      break;
   }
-  else
-    fit_get(&tab->fib, &hook->feed_fit);
 }
 
 void
@@ -1896,7 +1888,7 @@ rt_stop_export(struct rt_export_request *req, void (*stopped)(struct rt_export_r
   ev_postpone(hook->event);
 
   /* Stop feeding from the exporter */
-  hook->table->stop(hook);
+  CALL(hook->table->stop, hook);
 
   /* Reset the event as the stopped event */
   hook->event->hook = rt_export_stopped;
@@ -3397,130 +3389,6 @@ void channel_reload_export_bulk(struct rt_export_request *req, const net_addr *n
     }
 }
 
-void
-rt_prune_sync(rtable *t, int all)
-{
-  struct fib_iterator fit;
-
-  FIB_ITERATE_INIT(&fit, &t->fib);
-
-again:
-  FIB_ITERATE_START(&t->fib, &fit, net, n)
-  {
-    struct rte_storage *e, **ee = &n->routes;
-
-    while (e = *ee)
-    {
-      if (all || (e->rte.flags & (REF_STALE | REF_DISCARD)))
-      {
-	*ee = e->next;
-	rte_free(e);
-	t->rt_count--;
-      }
-      else
-	ee = &e->next;
-    }
-
-    if (all || !n->routes)
-    {
-      FIB_ITERATE_PUT(&fit);
-      fib_delete(&t->fib, n);
-      goto again;
-    }
-  }
-  FIB_ITERATE_END;
-}
-
-
-/*
- *	Export table
- */
-
-int
-rte_update_out(struct channel *c, const net_addr *n, rte *new, const rte *old0, struct rte_storage **old_exported)
-{
-  struct rtable *tab = c->out_table;
-  struct rte_src *src;
-  net *net;
-
-  if (new)
-  {
-    net = net_get(tab, n);
-    src = new->src;
-  }
-  else
-  {
-    net = net_find(tab, n);
-    src = old0->src;
-
-    if (!net)
-      goto drop;
-  }
-
-  /* Find the old rte */
-  struct rte_storage **pos = (c->ra_mode == RA_ANY) ? rte_find(net, src) : &net->routes;
-  struct rte_storage *old = NULL;
-
-  if (old = *pos)
-  {
-    if (new && rte_same(&(*pos)->rte, new))
-      goto drop;
-
-    /* Remove the old rte */
-    *pos = old->next;
-    *old_exported = old;
-    tab->rt_count--;
-  }
-
-  if (!new)
-  {
-    if (!old)
-      goto drop;
-
-    if (!net->routes)
-      fib_delete(&tab->fib, net);
-
-    return 1;
-  }
-
-  /* Insert the new rte */
-  struct rte_storage *e = rte_store(new, net, tab);
-  e->rte.lastmod = current_time();
-  e->next = *pos;
-  *pos = e;
-  tab->rt_count++;
-  return 1;
-
-drop:
-  return 0;
-}
-
-void
-rt_refeed_channel(struct channel *c)
-{
-  if (!c->out_table)
-  {
-    channel_request_feeding(c);
-    return;
-  }
-
-  ASSERT_DIE(c->ra_mode != RA_ANY);
-
-  c->proto->feed_begin(c, 0);
-
-  FIB_WALK(&c->out_table->fib, net, n)
-  {
-    if (!n->routes)
-      continue;
-
-    rte e = n->routes->rte;
-    c->proto->rt_notify(c->proto, c, n->n.addr, &e, NULL);
-  }
-  FIB_WALK_END;
-
-  c->proto->feed_end(c);
-}
-
 
 /*
  *	Hostcache
diff --git a/nest/rt.h b/nest/rt.h
index 3ed56fcc..5a8c5a19 100644
--- a/nest/rt.h
+++ b/nest/rt.h
@@ -247,14 +247,20 @@ struct rt_export_hook {
     u32 withdraws_received;		/* Number of route withdraws received */
   } stats;
 
-  struct fib_iterator feed_fit;		/* Routing table iterator used during feeding */
-  struct f_trie_walk_state *walk_state;	/* Iterator over networks in trie */
-  struct f_trie *walk_lock;		/* Locked trie for walking */
+  union {
+    struct fib_iterator feed_fit;		/* Routing table iterator used during feeding */
+    struct {
+      struct f_trie_walk_state *walk_state;	/* Iterator over networks in trie */
+      struct f_trie *walk_lock;			/* Locked trie for walking */
+    };
+    u32 hash_iter;				/* Iterator over hash */
+  };
 
   btime last_state_change;		/* Time of last state transition */
 
   u8 refeed_pending;			/* Refeeding and another refeed is scheduled */
   u8 export_state;			/* Route export state (TES_*, see below) */
+  u8 feed_type;				/* Which feeding method is used (TFT_*, see below) */
 
   struct event *event;			/* Event running all the export operations */
 
@@ -282,6 +288,10 @@ struct rt_export_hook {
 #define TE_ADDR_IN	3		/* Interval query - show route in <addr> */
 
 
+#define TFT_FIB		1
+#define TFT_TRIE	2
+#define TFT_HASH	3
+
 void rt_request_import(rtable *tab, struct rt_import_request *req);
 void rt_request_export(struct rt_exporter *tab, struct rt_export_request *req);
 
@@ -296,6 +306,8 @@ const char *rt_export_state_name(u8 state);
 static inline u8 rt_import_get_state(struct rt_import_hook *ih) { return ih ? ih->import_state : TIS_DOWN; }
 static inline u8 rt_export_get_state(struct rt_export_hook *eh) { return eh ? eh->export_state : TES_DOWN; }
 
+void rt_set_export_state(struct rt_export_hook *hook, u8 state);
+
 void rte_import(struct rt_import_request *req, const net_addr *net, rte *new, struct rte_src *src);
 
 /* Types of route announcement, also used as flags */
@@ -386,8 +398,6 @@ int rt_reload_channel(struct channel *c);
 void rt_reload_channel_abort(struct channel *c);
 void rt_refeed_channel(struct channel *c);
 void rt_prune_sync(rtable *t, int all);
-int rte_update_in(struct channel *c, const net_addr *n, rte *new, struct rte_src *src);
-int rte_update_out(struct channel *c, const net_addr *n, rte *new, const rte *old, struct rte_storage **old_exported);
 struct rtable_config *rt_new_table(struct symbol *s, uint addr_type);
 
 static inline int rt_is_ip(rtable *tab)