From 9c9059fd172dcc2f8805529de4b3174f280c109c Mon Sep 17 00:00:00 2001
From: Maria Matejka <mq@ucw.cz>
Date: Wed, 22 Jun 2022 12:45:42 +0200
Subject: [PATCH] Allowed optimized exporting of a subprefix tree

Added an option for export filter to allow for prefiltering based on the
prefix. Routes outside the given prefix are completely ignored. Config
is simple:

	export in <net> <filter>;
---
 doc/bird.sgml       |  8 ++--
 nest/config.Y       |  6 +++
 nest/proto.c        |  8 +++-
 nest/protocol.h     |  2 +
 nest/rt-table.c     | 89 +++++++++++++++++++++++++++++++++++++--------
 nest/rt.h           |  3 ++
 proto/pipe/config.Y |  6 +++
 proto/pipe/pipe.c   |  8 ++++
 proto/pipe/pipe.h   |  1 +
 9 files changed, 111 insertions(+), 20 deletions(-)

diff --git a/doc/bird.sgml b/doc/bird.sgml
index d17de23fe..c9ce670b7 100644
--- a/doc/bird.sgml
+++ b/doc/bird.sgml
@@ -914,10 +914,12 @@ inherited from templates can be updated by new definitions.
 	<cf/none/ is for dropping all routes. Default: <cf/all/ (except for
 	EBGP).
 
-	<tag><label id="proto-export">export <m/filter/</tag>
+	<tag><label id="proto-export">export [ in <m/prefix/ ] <m/filter/</tag>
 	This is similar to the <cf>import</cf> keyword, except that it works in
-	the direction from the routing table to the protocol. Default: <cf/none/
-	(except for EBGP).
+	the direction from the routing table to the protocol. If <cf/in/ keyword is used,
+	only routes inside the given prefix are exported. Other routes are completely
+	ignored (e.g. no logging and no statistics).
+	Default: <cf/none/ (except for EBGP).
 
 	<tag><label id="proto-import-keep-filtered">import keep filtered <m/switch/</tag>
 	Usually, if an import filter rejects a route, the route is forgotten.
diff --git a/nest/config.Y b/nest/config.Y
index ea7e12666..c3f2532fc 100644
--- a/nest/config.Y
+++ b/nest/config.Y
@@ -306,6 +306,12 @@ channel_item_:
      this_channel->table = $2;
    }
  | IMPORT imexport { this_channel->in_filter = $2; }
+ | EXPORT IN net_any imexport {
+     if (this_channel->net_type && ($3->type != this_channel->net_type))
+       cf_error("Incompatible export prefilter type");
+     this_channel->out_subprefix = $3;
+     this_channel->out_filter = $4;
+   }
  | EXPORT imexport { this_channel->out_filter = $2; }
  | RECEIVE LIMIT limit_spec { this_channel->rx_limit = $3; }
  | IMPORT LIMIT limit_spec { this_channel->in_limit = $3; }
diff --git a/nest/proto.c b/nest/proto.c
index 8513b9cba..3792fde4e 100644
--- a/nest/proto.c
+++ b/nest/proto.c
@@ -214,6 +214,7 @@ proto_add_channel(struct proto *p, struct channel_config *cf)
 
   c->in_filter = cf->in_filter;
   c->out_filter = cf->out_filter;
+  c->out_subprefix = cf->out_subprefix;
 
   channel_init_limit(c, &c->rx_limit, PLD_RX, &cf->rx_limit);
   channel_init_limit(c, &c->in_limit, PLD_IN, &cf->in_limit);
@@ -467,6 +468,7 @@ channel_start_export(struct channel *c)
 
   c->out_req = (struct rt_export_request) {
     .name = rn,
+    .addr_in = c->out_subprefix,
     .trace_routes = c->debug | c->proto->debug,
     .dump_req = channel_dump_export_req,
     .log_state_change = channel_export_log_state_change,
@@ -922,7 +924,10 @@ channel_reconfigure(struct channel *c, struct channel_config *cf)
   /* FIXME: better handle these changes, also handle in_keep_filtered */
   if ((c->table != cf->table->table) ||
       (cf->ra_mode && (c->ra_mode != cf->ra_mode)) ||
-      (cf->in_keep != c->in_keep))
+      (cf->in_keep != c->in_keep) ||
+      cf->out_subprefix && c->out_subprefix &&
+	  !net_equal(cf->out_subprefix, c->out_subprefix) ||
+      (!cf->out_subprefix != !c->out_subprefix))
     return 0;
 
   /* Note that filter_same() requires arguments in (new, old) order */
@@ -947,6 +952,7 @@ channel_reconfigure(struct channel *c, struct channel_config *cf)
   // c->ra_mode = cf->ra_mode;
   c->merge_limit = cf->merge_limit;
   c->preference = cf->preference;
+  c->out_req.addr_in = c->out_subprefix = cf->out_subprefix;
   c->debug = cf->debug;
   c->in_req.trace_routes = c->out_req.trace_routes = c->debug | c->proto->debug;
   c->rpki_reload = cf->rpki_reload;
diff --git a/nest/protocol.h b/nest/protocol.h
index b482ed997..a1701a7eb 100644
--- a/nest/protocol.h
+++ b/nest/protocol.h
@@ -452,6 +452,7 @@ struct channel_config {
   struct proto_config *parent;		/* Where channel is defined (proto or template) */
   struct rtable_config *table;		/* Table we're attached to */
   const struct filter *in_filter, *out_filter; /* Attached filters */
+  const net_addr *out_subprefix;	/* Export only subprefixes of this net */
 
   struct channel_limit rx_limit;	/* Limit for receiving routes from protocol
 					   (relevant when in_keep & RIK_REJECTED) */
@@ -477,6 +478,7 @@ struct channel {
   struct rtable *table;
   const struct filter *in_filter;	/* Input filter */
   const struct filter *out_filter;	/* Output filter */
+  const net_addr *out_subprefix;	/* Export only subprefixes of this net */
   struct bmap export_map;		/* Keeps track which routes were really exported */
   struct bmap export_reject_map;	/* Keeps track which routes were rejected by export filter */
 
diff --git a/nest/rt-table.c b/nest/rt-table.c
index 14c801387..afafef623 100644
--- a/nest/rt-table.c
+++ b/nest/rt-table.c
@@ -126,7 +126,9 @@ static inline void rt_flowspec_resolve_rte(rte *r, struct channel *c);
 static inline void rt_prune_table(rtable *tab);
 static inline void rt_schedule_notify(rtable *tab);
 static void rt_flowspec_notify(rtable *tab, net *net);
-static void rt_feed_channel(void *);
+static void rt_feed_by_fib(void *);
+static void rt_feed_by_trie(void *);
+static uint rt_feed_net(struct rt_export_hook *c, net *n);
 
 const char *rt_import_state_name_array[TIS_MAX] = {
   [TIS_DOWN] = "DOWN",
@@ -1187,6 +1189,9 @@ rte_announce(rtable *tab, net *net, struct rte_storage *new, struct rte_storage
     if (eh->export_state == TES_STOP)
       continue;
 
+    if (eh->req->addr_in && !net_in_netX(net->n.addr, eh->req->addr_in))
+      continue;
+
     if (new)
       eh->stats.updates_received++;
     else
@@ -1768,13 +1773,21 @@ rt_table_export_start(struct rt_exporter *re, struct rt_export_request *req)
   hook->lp = lp_new_default(p);
 
   /* stats zeroed by mb_allocz */
-
-  FIB_ITERATE_INIT(&hook->feed_fit, &tab->fib);
+  if (tab->trie && req->addr_in && net_val_match(tab->addr_type, NB_IP))
+  {
+    hook->walk_state = mb_allocz(p, sizeof (struct f_trie_walk_state));
+    hook->walk_lock = rt_lock_trie(tab);
+    trie_walk_init(hook->walk_state, tab->trie, req->addr_in);
+    hook->event = ev_new_init(p, rt_feed_by_trie, hook);
+  }
+  else
+  {
+    FIB_ITERATE_INIT(&hook->feed_fit, &tab->fib);
+    hook->event = ev_new_init(p, rt_feed_by_fib, hook);
+  }
 
   DBG("New export hook %p req %p in table %s uc=%u\n", hook, req, tab->name, tab->use_count);
 
-  hook->event = ev_new_init(p, rt_feed_channel, hook);
-
   return hook;
 }
 
@@ -3154,7 +3167,7 @@ rt_commit(struct config *new, struct config *old)
 }
 
 /**
- * rt_feed_channel - advertise all routes to a channel
+ * rt_feed_by_fib - advertise all routes to a channel by walking a fib
  * @c: channel to be fed
  *
  * This function performs one pass of advertisement of routes to a channel that
@@ -3163,7 +3176,7 @@ rt_commit(struct config *new, struct config *old)
  * order not to monopolize CPU time.)
  */
 static void
-rt_feed_channel(void *data)
+rt_feed_by_fib(void *data)
 {
   struct rt_export_hook *c = data;
 
@@ -3183,9 +3196,55 @@ rt_feed_channel(void *data)
 	  return;
 	}
 
-      if (c->export_state != TES_FEEDING)
-	goto done;
+      ASSERT(c->export_state == TES_FEEDING);
+
+      if (!c->req->addr_in || net_in_netX(n->n.addr, c->req->addr_in))
+	max_feed -= rt_feed_net(c, n);
+    }
+  FIB_ITERATE_END;
+
+  rt_set_export_state(c, TES_READY);
+}
+
+static void
+rt_feed_by_trie(void *data)
+{
+  struct rt_export_hook *c = data;
+  rtable *tab = SKIP_BACK(rtable, exporter, c->table);
+
+  ASSERT_DIE(c->walk_state);
+  struct f_trie_walk_state *ws = c->walk_state;
+
+  int max_feed = 256;
+
+  ASSERT_DIE(c->export_state == TES_FEEDING);
+
+  net_addr addr;
+  while (trie_walk_next(ws, &addr))
+  {
+    net *n = net_find(tab, &addr);
+    if (!n)
+      continue;
+
+    if ((max_feed -= rt_feed_net(c, n)) <= 0)
+      return;
+
+    ASSERT_DIE(c->export_state == TES_FEEDING);
+  }
 
+  rt_unlock_trie(tab, c->walk_lock);
+  c->walk_lock = NULL;
+
+  mb_free(c->walk_state);
+  c->walk_state = NULL;
+
+  rt_set_export_state(c, TES_READY);
+}
+
+
+static uint
+rt_feed_net(struct rt_export_hook *c, net *n)
+{
       if (c->req->export_bulk)
       {
 	uint count = rte_feed_count(n);
@@ -3196,23 +3255,21 @@ rt_feed_channel(void *data)
 	  rte_feed_obtain(n, feed, count);
 	  struct rt_pending_export rpe = { .new_best = n->routes };
 	  c->req->export_bulk(c->req, n->n.addr, &rpe, feed, count);
-	  max_feed -= count;
 	  rte_update_unlock();
 	}
+	return count;
       }
-      else if (n->routes && rte_is_valid(&n->routes->rte))
+
+      if (n->routes && rte_is_valid(&n->routes->rte))
       {
 	rte_update_lock();
 	struct rt_pending_export rpe = { .new = n->routes, .new_best = n->routes };
 	c->req->export_one(c->req, n->n.addr, &rpe);
-	max_feed--;
 	rte_update_unlock();
+	return 1;
       }
-    }
-  FIB_ITERATE_END;
 
-done:
-  rt_set_export_state(c, TES_READY);
+      return 0;
 }
 
 
diff --git a/nest/rt.h b/nest/rt.h
index 0f5a5ba78..57e117da7 100644
--- a/nest/rt.h
+++ b/nest/rt.h
@@ -212,6 +212,7 @@ struct rt_pending_export {
 
 struct rt_export_request {
   struct rt_export_hook *hook;		/* Table part of the export */
+  const net_addr *addr_in;		/* Subnet export request */
   char *name;
   u8 trace_routes;
 
@@ -245,6 +246,8 @@ struct rt_export_hook {
   } 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 */
 
   btime last_state_change;		/* Time of last state transition */
 
diff --git a/proto/pipe/config.Y b/proto/pipe/config.Y
index c869de9f7..0990168e4 100644
--- a/proto/pipe/config.Y
+++ b/proto/pipe/config.Y
@@ -41,6 +41,12 @@ pipe_proto:
    pipe_proto_start '{'
  | pipe_proto proto_item ';'
  | pipe_proto channel_item_ ';'
+ | pipe_proto IMPORT IN net_any imexport ';' {
+    if (this_channel->net_type && ($4->type != this_channel->net_type))
+      cf_error("Incompatible export prefilter type");
+    PIPE_CFG->in_subprefix = $4;
+    this_channel->in_filter = $5;
+  }
  | pipe_proto PEER TABLE rtable ';' { PIPE_CFG->peer = $4; }
  | pipe_proto MAX GENERATION expr ';' {
     if (($4 < 1) || ($4 > 254)) cf_error("Max generation must be in range 1..254, got %u", $4);
diff --git a/proto/pipe/pipe.c b/proto/pipe/pipe.c
index d12e6731b..351db36ba 100644
--- a/proto/pipe/pipe.c
+++ b/proto/pipe/pipe.c
@@ -123,6 +123,12 @@ pipe_postconfig(struct proto_config *CF)
   if (cc->table->addr_type != cf->peer->addr_type)
     cf_error("Primary table and peer table must have the same type");
 
+  if (cc->out_subprefix && (cc->table->addr_type != cc->out_subprefix->type))
+    cf_error("Export subprefix must match table type");
+
+  if (cf->in_subprefix && (cc->table->addr_type != cf->in_subprefix->type))
+    cf_error("Import subprefix must match table type");
+
   if (cc->rx_limit.action)
     cf_error("Pipe protocol does not support receive limits");
 
@@ -142,6 +148,7 @@ pipe_configure_channels(struct pipe_proto *p, struct pipe_config *cf)
     .channel = cc->channel,
     .table = cc->table,
     .out_filter = cc->out_filter,
+    .out_subprefix = cc->out_subprefix,
     .in_limit = cc->in_limit,
     .ra_mode = RA_ANY,
     .debug = cc->debug,
@@ -153,6 +160,7 @@ pipe_configure_channels(struct pipe_proto *p, struct pipe_config *cf)
     .channel = cc->channel,
     .table = cf->peer,
     .out_filter = cc->in_filter,
+    .out_subprefix = cf->in_subprefix,
     .in_limit = cc->out_limit,
     .ra_mode = RA_ANY,
     .debug = cc->debug,
diff --git a/proto/pipe/pipe.h b/proto/pipe/pipe.h
index 60c857eb6..a6534e1cb 100644
--- a/proto/pipe/pipe.h
+++ b/proto/pipe/pipe.h
@@ -12,6 +12,7 @@
 struct pipe_config {
   struct proto_config c;
   struct rtable_config *peer;		/* Table we're connected to */
+  const net_addr *in_subprefix;
   u8 max_generation;
 };
 
-- 
2.47.2