Nest: Attach prefix trie to rtable for faster LPM and interval queries

Attach a prefix trie to IP/VPN/ROA tables. Use it for net_route() and
net_roa_check(). This leads to 3-5x speedups for IPv4 and 5-10x
speedup for IPv6 of these calls.

TODO:
 - Rebuild the trie during rt_prune_table()
 - Better way to avoid trie_add_prefix() in net_get() for existing tables
 - Make it configurable (?)

1 files changed, 7 insertions, 2 deletions

diff --git a/nest/route.h b/nest/route.h
index f5fc9e31..fa87e22c 100644
--- a/nest/route.h
+++ b/nest/route.h
@@ -20,7 +20,9 @@ struct proto;
 struct rte_src;
 struct symbol;
 struct timer;
+struct fib;
 struct filter;
+struct f_trie;
 struct cli;
 
 /*
@@ -49,7 +51,7 @@ struct fib_iterator {			/* See lib/slists.h for an explanation */
   uint hash;
 };
 
-typedef void (*fib_init_fn)(void *);
+typedef void (*fib_init_fn)(struct fib *, void *);
 
 struct fib {
   pool *fib_pool;			/* Pool holding all our data */
@@ -149,6 +151,7 @@ struct rtable_config {
   int gc_min_time;			/* Minimum time between two consecutive GC runs */
   byte sorted;				/* Routes of network are sorted according to rte_better() */
   byte internal;			/* Internal table of a protocol */
+  byte trie_used;			/* Rtable has attached trie */
   btime min_settle_time;		/* Minimum settle time for notifications */
   btime max_settle_time;		/* Maximum settle time for notifications */
 };
@@ -158,6 +161,7 @@ typedef struct rtable {
   node n;				/* Node in list of all tables */
   pool *rp;				/* Resource pool to allocate everything from, including itself */
   struct fib fib;
+  struct f_trie *trie;			/* Trie of prefixes defined in fib */
   char *name;				/* Name of this table */
   list channels;			/* List of attached channels (struct channel) */
   uint addr_type;			/* Type of address data stored in table (NET_*) */
@@ -324,7 +328,8 @@ static inline net *net_find(rtable *tab, const net_addr *addr) { return (net *)
 static inline net *net_find_valid(rtable *tab, const net_addr *addr)
 { net *n = net_find(tab, addr); return (n && rte_is_valid(n->routes)) ? n : NULL; }
 static inline net *net_get(rtable *tab, const net_addr *addr) { return (net *) fib_get(&tab->fib, addr); }
-void *net_route(rtable *tab, const net_addr *n);
+net *net_get(rtable *tab, const net_addr *addr);
+net *net_route(rtable *tab, const net_addr *n);
 int net_roa_check(rtable *tab, const net_addr *n, u32 asn);
 rte *rte_find(net *net, struct rte_src *src);
 rte *rte_get_temp(struct rta *);