Filter: Faster prefix sets

Use 16-way (4bit) branching in prefix trie instead of basic binary
branching. The change makes IPv4 prefix sets almost 3x faster, but
with more memory consumption and much more complicated algorithm.

Together with a previous filter change, it makes IPv4 prefix sets
about ~4.3x faster and slightly smaller (on my test data).

3 files changed, 218 insertions, 71 deletions

diff --git a/filter/data.h b/filter/data.h
index d296776d..21967deb 100644
--- a/filter/data.h
+++ b/filter/data.h
@@ -140,18 +140,22 @@ struct f_tree {
   void *data;
 };
 
+#define TRIE_STEP	4
+
 struct f_trie_node4
 {
   ip4_addr addr, mask, accept;
-  uint plen;
-  struct f_trie_node4 *c[2];
+  u16 plen;
+  u16 local;
+  struct f_trie_node4 *c[1 << TRIE_STEP];
 };
 
 struct f_trie_node6
 {
   ip6_addr addr, mask, accept;
-  uint plen;
-  struct f_trie_node6 *c[2];
+  u16 plen;
+  u16 local;
+  struct f_trie_node6 *c[1 << TRIE_STEP];
 };
 
 struct f_trie_node
diff --git a/filter/test.conf b/filter/test.conf
index 3a8804a1..1edcd64e 100644
--- a/filter/test.conf
+++ b/filter/test.conf
@@ -558,6 +558,12 @@ prefix set pxs;
 	bt_assert(2000::/29 !~ pxs);
 	bt_assert(1100::/10 !~ pxs);
 	bt_assert(2010::/26 !~ pxs);
+
+	pxs = [ 52E0::/13{13,128} ];
+	bt_assert(52E7:BE81:379B:E6FD:541F:B0D0::/93 ~ pxs);
+
+	pxs = [ 41D8:8718::/30{0,30}, 413A:99A8:6C00::/38{38,128} ];
+	bt_assert(4180::/9 ~ pxs);
 }
 
 bt_test_suite(t_prefix6_set, "Testing prefix IPv6 sets");
diff --git a/filter/trie.c b/filter/trie.c
index 1a4e1ac3..cf805afc 100644
--- a/filter/trie.c
+++ b/filter/trie.c
@@ -86,7 +86,10 @@
 #define ipa_mkmask(x) ip6_mkmask(x)
 #define ipa_masklen(x) ip6_masklen(&x)
 #define ipa_pxlen(x,y) ip6_pxlen(x,y)
-#define ipa_getbit(x,n) ip6_getbit(x,n)
+#define ipa_getbit(a,p) ip6_getbit(a,p)
+#define ipa_getbits(a,p,n) ip6_getbits(a,p,n)
+#define ipa_setbits(a,p,n) ip6_setbits(a,p,n)
+#define trie_local_mask(a,b,c) trie_local_mask6(a,b,c)
 
 #define ipt_from_ip4(x) _MI6(_I(x), 0, 0, 0)
 #define ipt_to_ip4(x) _MI4(_I0(x))
@@ -109,10 +112,11 @@ f_new_trie(linpool *lp, uint data_size)
 }
 
 static inline struct f_trie_node4 *
-new_node4(struct f_trie *t, int plen, ip4_addr paddr, ip4_addr pmask, ip4_addr amask)
+new_node4(struct f_trie *t, uint plen, uint local, ip4_addr paddr, ip4_addr pmask, ip4_addr amask)
 {
   struct f_trie_node4 *n = lp_allocz(t->lp, sizeof(struct f_trie_node4) + t->data_size);
   n->plen = plen;
+  n->local = local;
   n->addr = paddr;
   n->mask = pmask;
   n->accept = amask;
@@ -120,10 +124,11 @@ new_node4(struct f_trie *t, int plen, ip4_addr paddr, ip4_addr pmask, ip4_addr a
 }
 
 static inline struct f_trie_node6 *
-new_node6(struct f_trie *t, int plen, ip6_addr paddr, ip6_addr pmask, ip6_addr amask)
+new_node6(struct f_trie *t, uint plen, uint local, ip6_addr paddr, ip6_addr pmask, ip6_addr amask)
 {
   struct f_trie_node6 *n = lp_allocz(t->lp, sizeof(struct f_trie_node6) + t->data_size);
   n->plen = plen;
+  n->local = local;
   n->addr = paddr;
   n->mask = pmask;
   n->accept = amask;
@@ -131,24 +136,24 @@ new_node6(struct f_trie *t, int plen, ip6_addr paddr, ip6_addr pmask, ip6_addr a
 }
 
 static inline struct f_trie_node *
-new_node(struct f_trie *t, int plen, ip_addr paddr, ip_addr pmask, ip_addr amask)
+new_node(struct f_trie *t, uint plen, uint local, ip_addr paddr, ip_addr pmask, ip_addr amask)
 {
   if (t->ipv4)
-    return (struct f_trie_node *) new_node4(t, plen, ipt_to_ip4(paddr), ipt_to_ip4(pmask), ipt_to_ip4(amask));
+    return (struct f_trie_node *) new_node4(t, plen, local, ipt_to_ip4(paddr), ipt_to_ip4(pmask), ipt_to_ip4(amask));
   else
-    return (struct f_trie_node *) new_node6(t, plen, ipa_to_ip6(paddr), ipa_to_ip6(pmask), ipa_to_ip6(amask));
+    return (struct f_trie_node *) new_node6(t, plen, local, ipa_to_ip6(paddr), ipa_to_ip6(pmask), ipa_to_ip6(amask));
 }
 
 static inline void
 attach_node4(struct f_trie_node4 *parent, struct f_trie_node4 *child)
 {
-  parent->c[ip4_getbit(child->addr, parent->plen) ? 1 : 0] = child;
+  parent->c[ip4_getbits(child->addr, parent->plen, TRIE_STEP)] = child;
 }
 
 static inline void
 attach_node6(struct f_trie_node6 *parent, struct f_trie_node6 *child)
 {
-  parent->c[ip6_getbit(child->addr, parent->plen) ? 1 : 0] = child;
+  parent->c[ip6_getbits(child->addr, parent->plen, TRIE_STEP)] = child;
 }
 
 static inline void
@@ -160,63 +165,60 @@ attach_node(struct f_trie_node *parent, struct f_trie_node *child, int v4)
     attach_node6(&parent->v6, &child->v6);
 }
 
-#define GET_ADDR(N,F,X) ((X) ? ipt_from_ip4((N)->v4.F) : ipa_from_ip6((N)->v6.F))
-#define SET_ADDR(N,F,X,V) ({ if (X) (N)->v4.F =ipt_to_ip4(V); else (N)->v6.F =ipa_to_ip6(V); })
 
-#define GET_CHILD(N,F,X,I) ((X) ? (struct f_trie_node *) (N)->v4.c[I] : (struct f_trie_node *) (N)->v6.c[I])
-/**
- * trie_add_prefix
- * @t: trie to add to
- * @net: IP network prefix
- * @l: prefix lower bound
- * @h: prefix upper bound
- *
- * Adds prefix (prefix pattern) @n to trie @t.  @l and @h are lower
- * and upper bounds on accepted prefix lengths, both inclusive.
- * 0 <= l, h <= 32 (128 for IPv6).
- *
- * Returns a pointer to the allocated node. The function can return a pointer to
- * an existing node if @px and @plen are the same. If px/plen == 0/0 (or ::/0),
- * a pointer to the root node is returned. Returns NULL when called with
- * mismatched IPv4/IPv6 net type.
- */
+static inline uint
+trie_local_mask4(ip4_addr px, uint plen, uint nlen)
+{
+  uint step = plen - nlen;
+  uint pos = (1u << step) + ip4_getbits(px, nlen, step);
+  return 1u << pos;
+}
 
-void *
-trie_add_prefix(struct f_trie *t, const net_addr *net, uint l, uint h)
+static inline uint
+trie_local_mask6(ip6_addr px, uint plen, uint nlen)
 {
-  uint plen = net_pxlen(net);
-  ip_addr px;
-  int v4;
+  uint step = plen - nlen;
+  uint pos = (1u << step) + ip6_getbits(px, nlen, step);
+  return 1u << pos;
+}
 
-  switch (net->type)
-  {
-  case NET_IP4: px = ipt_from_ip4(net4_prefix(net)); v4 = 1; break;
-  case NET_IP6: px = ipa_from_ip6(net6_prefix(net)); v4 = 0; break;
-  default: bug("invalid type");
-  }
+static inline uint
+trie_amask_to_local(ip_addr px, ip_addr amask, uint nlen)
+{
+  uint local = 0;
 
-  if (t->ipv4 != v4)
-  {
-    if (t->ipv4 < 0)
-      t->ipv4 = v4;
-    else
-      return NULL;
-  }
+  for (uint plen = MAX(nlen, 1); plen < (nlen + TRIE_STEP); plen++)
+    if (ipa_getbit(amask, plen - 1))
+      local |= trie_local_mask(px, plen, nlen);
 
-  if (l == 0)
-    t->zero = 1;
-  else
-    l--;
+  return local;
+}
 
-  if (h < plen)
-    plen = h;
+#define GET_ADDR(N,F,X) ((X) ? ipt_from_ip4((N)->v4.F) : ipa_from_ip6((N)->v6.F))
+#define SET_ADDR(N,F,X,V) ({ if (X) (N)->v4.F =ipt_to_ip4(V); else (N)->v6.F =ipa_to_ip6(V); })
 
-  ip_addr amask = ipa_xor(ipa_mkmask(l), ipa_mkmask(h));
+#define ADD_LOCAL(N,X,V) ({ uint v_ = (V); if (X) (N)->v4.local |= v_; else (N)->v6.local |= v_; })
+
+#define GET_CHILD(N,F,X,I) ((X) ? (struct f_trie_node *) (N)->v4.c[I] : (struct f_trie_node *) (N)->v6.c[I])
+
+
+static void *
+trie_add_node(struct f_trie *t, uint plen, ip_addr px, uint local, uint l, uint h)
+{
+  uint l_ = l ? (l - 1) : 0;
+  ip_addr amask = (l_ < h) ? ipa_xor(ipa_mkmask(l_), ipa_mkmask(h)) : IPA_NONE;
   ip_addr pmask = ipa_mkmask(plen);
   ip_addr paddr = ipa_and(px, pmask);
   struct f_trie_node *o = NULL;
   struct f_trie_node *n = &t->root;
+  int v4 = t->ipv4;
+
+  /* Add all bits for each active level (0x0002 0x000c 0x00f0 0xff00) */
+  for (uint i = 0; i < TRIE_STEP; i++)
+    if ((l <= (plen + i)) && ((plen + i) <= h))
+      local |= ((1u << (1u << i)) - 1) << (1u << i);
 
+  DBG("Insert node %I/%u (%I %x)\n", paddr, plen, amask, local);
   while (n)
     {
       ip_addr naddr = GET_ADDR(n, addr, v4);
@@ -225,23 +227,30 @@ trie_add_prefix(struct f_trie *t, const net_addr *net, uint l, uint h)
       ip_addr cmask = ipa_and(nmask, pmask);
       uint nlen = v4 ? n->v4.plen : n->v6.plen;
 
+      DBG("Found node %I/%u (%I %x)\n",
+	  naddr, nlen, accept, v4 ? n->v4.local : n->v6.local);
+
       if (ipa_compare(ipa_and(paddr, cmask), ipa_and(naddr, cmask)))
         {
 	  /* We are out of path - we have to add branching node 'b'
 	     between node 'o' and node 'n', and attach new node 'a'
 	     as the other child of 'b'. */
-	  int blen = ipa_pxlen(paddr, naddr);
+	  int blen = ROUND_DOWN_POW2(ipa_pxlen(paddr, naddr), TRIE_STEP);
 	  ip_addr bmask = ipa_mkmask(blen);
 	  ip_addr baddr = ipa_and(px, bmask);
 
 	  /* Merge accept masks from children to get accept mask for node 'b' */
 	  ip_addr baccm = ipa_and(ipa_or(amask, accept), bmask);
+	  uint bloc = trie_amask_to_local(naddr, accept, blen) |
+	              trie_amask_to_local(paddr, amask, blen);
 
-	  struct f_trie_node *a = new_node(t, plen, paddr, pmask, amask);
-	  struct f_trie_node *b = new_node(t, blen, baddr, bmask, baccm);
+	  struct f_trie_node *a = new_node(t, plen, local, paddr, pmask, amask);
+	  struct f_trie_node *b = new_node(t, blen, bloc, baddr, bmask, baccm);
 	  attach_node(o, b, v4);
 	  attach_node(b, n, v4);
 	  attach_node(b, a, v4);
+
+	  DBG("Case 1\n");
 	  return a;
 	}
 
@@ -249,36 +258,144 @@ trie_add_prefix(struct f_trie *t, const net_addr *net, uint l, uint h)
 	{
 	  /* We add new node 'a' between node 'o' and node 'n' */
 	  amask = ipa_or(amask, ipa_and(accept, pmask));
-	  struct f_trie_node *a = new_node(t, plen, paddr, pmask, amask);
+	  local |= trie_amask_to_local(naddr, accept, plen);
+	  struct f_trie_node *a = new_node(t, plen, local, paddr, pmask, amask);
 	  attach_node(o, a, v4);
 	  attach_node(a, n, v4);
+
+	  DBG("Case 2\n");
 	  return a;
 	}
 
       if (plen == nlen)
 	{
-	  /* We already found added node in trie. Just update accept mask */
+	  /* We already found added node in trie. Just update accept and local mask */
 	  accept = ipa_or(accept, amask);
 	  SET_ADDR(n, accept, v4, accept);
+	  ADD_LOCAL(n, v4, local);
+
+	  DBG("Case 3\n");
 	  return n;
 	}
 
       /* Update accept mask part M2 and go deeper */
       accept = ipa_or(accept, ipa_and(amask, nmask));
       SET_ADDR(n, accept, v4, accept);
+      ADD_LOCAL(n, v4, trie_amask_to_local(paddr, amask, nlen));
+
+      DBG("Step %u\n", ipa_getbits(paddr, nlen));
 
       /* n->plen < plen and plen <= 32 (128) */
       o = n;
-      n = GET_CHILD(n, c, v4, ipa_getbit(paddr, nlen) ? 1 : 0);
+      n = GET_CHILD(n, c, v4, ipa_getbits(paddr, nlen, TRIE_STEP));
     }
 
   /* We add new tail node 'a' after node 'o' */
-  struct f_trie_node *a = new_node(t, plen, paddr, pmask, amask);
+  struct f_trie_node *a = new_node(t, plen, local, paddr, pmask, amask);
   attach_node(o, a, v4);
 
+  DBG("Case 4\n");
   return a;
 }
 
+/**
+ * trie_add_prefix
+ * @t: trie to add to
+ * @net: IP network prefix
+ * @l: prefix lower bound
+ * @h: prefix upper bound
+ *
+ * Adds prefix (prefix pattern) @n to trie @t.  @l and @h are lower
+ * and upper bounds on accepted prefix lengths, both inclusive.
+ * 0 <= l, h <= 32 (128 for IPv6).
+ *
+ * Returns a pointer to the allocated node. The function can return a pointer to
+ * an existing node if @px and @plen are the same. If px/plen == 0/0 (or ::/0),
+ * a pointer to the root node is returned. Returns NULL when called with
+ * mismatched IPv4/IPv6 net type.
+ */
+void *
+trie_add_prefix(struct f_trie *t, const net_addr *net, uint l, uint h)
+{
+  uint plen = net_pxlen(net);
+  ip_addr px;
+  int v4;
+
+  switch (net->type)
+  {
+  case NET_IP4: px = ipt_from_ip4(net4_prefix(net)); v4 = 1; break;
+  case NET_IP6: px = ipa_from_ip6(net6_prefix(net)); v4 = 0; break;
+  default: bug("invalid type");
+  }
+
+  if (t->ipv4 != v4)
+  {
+    if (t->ipv4 < 0)
+      t->ipv4 = v4;
+    else
+      return NULL;
+  }
+
+  DBG("\nInsert net %N (%u-%u)\n", net, l, h);
+
+  if (l == 0)
+    t->zero = 1;
+
+  if (h < plen)
+    plen = h;
+
+  /* Primary node length, plen rounded down */
+  uint nlen = ROUND_DOWN_POW2(plen, TRIE_STEP);
+
+  if (plen == nlen)
+    return trie_add_node(t, nlen, px, 0, l,  h);
+
+  /* Secondary node length, plen rouned up */
+  uint slen = nlen + TRIE_STEP;
+  void *node = NULL;
+
+  /*
+   * For unaligned prefix lengths it is more complicated. We need to encode
+   * matching prefixes of lengths from l to h. There are three cases of lengths:
+   *
+   * 1) 0..nlen are encoded by the accept mask of the primary node
+   * 2) nlen..(slen-1) are encoded by the local mask of the primary node
+   * 3) slen..max are encoded in secondary nodes
+   */
+
+  if (l < slen)
+  {
+    uint local = 0;
+
+    /* Compute local bits for accepted nlen..(slen-1) prefixes */
+    for (uint i = 0; i < TRIE_STEP; i++)
+      if ((l <= (nlen + i)) && ((nlen + i) <= h))
+      {
+	uint pos = (1u << i) + ipa_getbits(px, nlen, i);
+	uint len = ((nlen + i) <= plen) ? 1 : (1u << (nlen + i - plen));
+
+	/* We need to fill 'len' bits starting at 'pos' position */
+	local |= ((1u << len) - 1) << pos;
+      }
+
+    /* Add the primary node */
+    node = trie_add_node(t, nlen, px, local, l,  nlen);
+  }
+
+  if (slen <= h)
+  {
+    uint l2 = MAX(l, slen);
+    uint max = (1u << (slen - plen));
+
+    /* Add secondary nodes */
+    for (uint i = 0; i < max; i++)
+      node = trie_add_node(t, slen, ipa_setbits(px,  slen - 1, i), 0, l2,  h);
+  }
+
+  return node;
+}
+
+
 static int
 trie_match_net4(const struct f_trie *t, ip4_addr px, uint plen)
 {
@@ -289,6 +406,8 @@ trie_match_net4(const struct f_trie *t, ip4_addr px, uint plen)
     return t->zero;
 
   int plentest = plen - 1;
+  uint nlen = ROUND_DOWN_POW2(plen, TRIE_STEP);
+  uint local = trie_local_mask4(px, plen, nlen);
   const struct f_trie_node4 *n = &t->root.v4;
 
   while (n)
@@ -299,6 +418,10 @@ trie_match_net4(const struct f_trie *t, ip4_addr px, uint plen)
     if (ip4_compare(ip4_and(paddr, cmask), ip4_and(n->addr, cmask)))
       return 0;
 
+    /* Check local mask */
+    if ((n->plen == nlen) && (n->local & local))
+      return 1;
+
     /* Check accept mask */
     if (ip4_getbit(n->accept, plentest))
       return 1;
@@ -308,7 +431,7 @@ trie_match_net4(const struct f_trie *t, ip4_addr px, uint plen)
       return 0;
 
     /* Choose children */
-    n =  n->c[(ip4_getbit(paddr, n->plen)) ? 1 : 0];
+    n =  n->c[ip4_getbits(paddr, n->plen, TRIE_STEP)];
   }
 
   return 0;
@@ -324,6 +447,8 @@ trie_match_net6(const struct f_trie *t, ip6_addr px, uint plen)
     return t->zero;
 
   int plentest = plen - 1;
+  uint nlen = ROUND_DOWN_POW2(plen, TRIE_STEP);
+  uint local = trie_local_mask6(px, plen, nlen);
   const struct f_trie_node6 *n = &t->root.v6;
 
   while (n)
@@ -334,6 +459,10 @@ trie_match_net6(const struct f_trie *t, ip6_addr px, uint plen)
     if (ip6_compare(ip6_and(paddr, cmask), ip6_and(n->addr, cmask)))
       return 0;
 
+    /* Check local mask */
+    if ((n->plen == nlen) && (n->local & local))
+      return 1;
+
     /* Check accept mask */
     if (ip6_getbit(n->accept, plentest))
       return 1;
@@ -343,7 +472,7 @@ trie_match_net6(const struct f_trie *t, ip6_addr px, uint plen)
       return 0;
 
     /* Choose children */
-    n =  n->c[(ip6_getbit(paddr, n->plen)) ? 1 : 0];
+    n =  n->c[ip6_getbits(paddr, n->plen, TRIE_STEP)];
   }
 
   return 0;
@@ -392,7 +521,11 @@ trie_node_same4(const struct f_trie_node4 *t1, const struct f_trie_node4 *t2)
       (! ip4_equal(t1->accept, t2->accept)))
     return 0;
 
-  return trie_node_same4(t1->c[0], t2->c[0]) && trie_node_same4(t1->c[1], t2->c[1]);
+  for (uint i = 0; i < (1 << TRIE_STEP); i++)
+    if (! trie_node_same4(t1->c[i], t2->c[i]))
+      return 0;
+
+  return 1;
 }
 
 static int
@@ -409,7 +542,11 @@ trie_node_same6(const struct f_trie_node6 *t1, const struct f_trie_node6 *t2)
       (! ip6_equal(t1->accept, t2->accept)))
     return 0;
 
-  return trie_node_same6(t1->c[0], t2->c[0]) && trie_node_same6(t1->c[1], t2->c[1]);
+  for (uint i = 0; i < (1 << TRIE_STEP); i++)
+    if (! trie_node_same6(t1->c[i], t2->c[i]))
+      return 0;
+
+  return 1;
 }
 
 /**
@@ -440,8 +577,8 @@ trie_node_format4(const struct f_trie_node4 *t, buffer *buf)
   if (ip4_nonzero(t->accept))
     buffer_print(buf, "%I4/%d{%I4}, ", t->addr, t->plen, t->accept);
 
-  trie_node_format4(t->c[0], buf);
-  trie_node_format4(t->c[1], buf);
+  for (uint i = 0; i < (1 << TRIE_STEP); i++)
+    trie_node_format4(t->c[i], buf);
 }
 
 static void
@@ -453,8 +590,8 @@ trie_node_format6(const struct f_trie_node6 *t, buffer *buf)
   if (ip6_nonzero(t->accept))
     buffer_print(buf, "%I6/%d{%I6}, ", t->addr, t->plen, t->accept);
 
-  trie_node_format6(t->c[0], buf);
-  trie_node_format6(t->c[1], buf);
+  for (uint i = 0; i < (1 << TRIE_STEP); i++)
+    trie_node_format6(t->c[i], buf);
 }
 
 /**