From e709dc09e61c4604821d10b81604d38616b81a0b Mon Sep 17 00:00:00 2001
From: "Ondrej Zajicek (work)" <santiago@crfreenet.org>
Date: Tue, 21 Apr 2020 13:49:29 +0200
Subject: Filter: Improve prefix trie tests

Add tests explicitly matching insides and outsides of trie and update
tests to do testing of both IPv4 and IPv6 tries.
---
 test/birdtest.c | 6 ++++++
 1 file changed, 6 insertions(+)

(limited to 'test/birdtest.c')

diff --git a/test/birdtest.c b/test/birdtest.c
index a1da078f..d739e78b 100644
--- a/test/birdtest.c
+++ b/test/birdtest.c
@@ -501,6 +501,12 @@ bt_fmt_ipa(char *buf, size_t size, const void *data)
     bsnprintf(buf, size, "(null)");
 }
 
+void
+bt_format_net(char *buf, size_t size, const void *data)
+{
+  bsnprintf(buf, size, "%N", (const net_addr *) data);
+}
+
 int
 bt_is_char(byte c)
 {
-- 
cgit v1.2.3


From 067f69a56de0e0e61d423ec5aa68095aa28e3124 Mon Sep 17 00:00:00 2001
From: "Ondrej Zajicek (work)" <santiago@crfreenet.org>
Date: Sat, 25 Sep 2021 16:00:30 +0200
Subject: Filter: Add prefix trie benchmarks

Add trie tests intended as benchmarks that use external datasets
instead of generated prefixes. As datasets are not included, they
are commented out by default.
---
 filter/trie_test.c | 235 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 test/birdtest.c    |   6 ++
 test/birdtest.h    |   1 +
 3 files changed, 242 insertions(+)

(limited to 'test/birdtest.c')

diff --git a/filter/trie_test.c b/filter/trie_test.c
index 6418427e..3e8ce84d 100644
--- a/filter/trie_test.c
+++ b/filter/trie_test.c
@@ -16,7 +16,10 @@
 #define TESTS_NUM		10
 #define PREFIXES_NUM 		32
 #define PREFIX_TESTS_NUM 	10000
+#define PREFIX_BENCH_NUM 	100000000
 
+#define TRIE_BUFFER_SIZE	1024
+#define TEST_BUFFER_SIZE	(1024*1024)
 #define BIG_BUFFER_SIZE		10000
 
 /* Wrapping structure for storing f_prefixes structures in list */
@@ -266,6 +269,142 @@ make_trie_from_prefix_list(linpool *lp, list *prefixes)
   return trie;
 }
 
+/*
+ * Read sequence of prefixes from file handle and return prefix list.
+ * Each prefix is on one line, sequence terminated by empty line or eof.
+ * Arg @plus means prefix should include all longer ones.
+ */
+static list *
+read_prefix_list(linpool *lp, FILE *f, int v6, int plus)
+{
+  ASSERT(!v6);
+
+  uint a0, a1, a2, a3, pl;
+  char s[32];
+  int n;
+
+  list *pxlist = lp_allocz(lp, sizeof(struct f_prefix_node));
+  init_list(pxlist);
+
+  errno = 0;
+  while (fgets(s, 32, f))
+  {
+    if (s[0] == '\n')
+      return pxlist;
+
+    n = sscanf(s, "%u.%u.%u.%u/%u", &a0, &a1, &a2, &a3, &pl);
+
+    if (n != 5)
+      bt_abort_msg("Invalid content of trie_data");
+
+    struct f_prefix_node *px = lp_allocz(lp, sizeof(struct f_prefix_node));
+    net_fill_ip4(&px->prefix.net, ip4_build(a0, a1, a2, a3), pl);
+    px->prefix.lo = pl;
+    px->prefix.hi = plus ? IP4_MAX_PREFIX_LENGTH : pl;
+    add_tail(pxlist, &px->n);
+
+    char buf[64];
+    bt_format_net(buf, 64, &px->prefix.net);
+    bt_debug("ADD %s{%d,%d}\n", buf, px->prefix.lo, px->prefix.hi);
+  }
+
+  bt_syscall(errno, "fgets()");
+  return EMPTY_LIST(*pxlist) ? NULL : pxlist;
+}
+
+/*
+ * Open file, read multiple sequences of prefixes from it. Fill @data with
+ * prefix lists and @trie with generated tries. Return number of sequences /
+ * tries. Use separate linpool @lp0 for prefix lists and @lp1 for tries.
+ * Arg @plus means prefix should include all longer ones.
+ */
+static int
+read_prefix_file(const char *filename, int plus,
+		 linpool *lp0, linpool *lp1,
+		 list *data[], struct f_trie *trie[])
+{
+  FILE *f = fopen(filename, "r");
+  bt_syscall(!f, "fopen(%s)", filename);
+
+  int n = 0;
+  list *pxlist;
+  while (pxlist = read_prefix_list(lp0, f, 0, plus))
+  {
+    data[n] = pxlist;
+    trie[n] = make_trie_from_prefix_list(lp1, pxlist);
+    bt_debug("NEXT\n");
+    n++;
+  }
+
+  fclose(f);
+  bt_debug("DONE reading %d tries\n", n);
+
+  return n;
+}
+
+/*
+ * Select random subset of @dn prefixes from prefix list @src of length @sn,
+ * and store them to buffer @dst (of size @dn). Prefixes may be chosen multiple
+ * times. Randomize order of prefixes in @dst buffer.
+ */
+static void
+select_random_prefix_subset(list *src[], net_addr dst[], int sn, int dn)
+{
+  int pn = 0;
+
+  if (!dn)
+    return;
+
+  /* Compute total prefix number */
+  for (int i = 0; i < sn; i++)
+    pn += list_length(src[i]);
+
+  /* Change of selecting a prefix */
+  int rnd = (pn / dn) + 10;
+  int n = 0;
+
+  /* Iterate indefinitely over src array */
+  for (int i = 0; 1; i++, i = (i < sn) ? i : 0)
+  {
+    struct f_prefix_node *px;
+    WALK_LIST(px, *src[i])
+    {
+      if (xrandom(rnd) != 0)
+	continue;
+
+      net_copy(&dst[n], &px->prefix.net);
+      n++;
+
+      /* We have enough */
+      if (n == dn)
+	goto done;
+    }
+  }
+
+done:
+  /* Shuffle networks */
+  for (int i = 0; i < dn; i++)
+  {
+    int j = xrandom(dn);
+
+    if (i == j)
+      continue;
+
+    net_addr tmp;
+    net_copy(&tmp, &dst[i]);
+    net_copy(&dst[i], &dst[j]);
+    net_copy(&dst[j], &tmp);
+  }
+}
+
+/* Fill @dst buffer with @dn randomly generated /32 prefixes */
+static void
+make_random_addresses(net_addr dst[], int dn)
+{
+  for (int i = 0; i < dn; i++)
+    net_fill_ip4(&dst[i], ip4_from_u32((u32) bt_random()), IP4_MAX_PREFIX_LENGTH);
+}
+
 static void
 test_match_net(list *prefixes, struct f_trie *trie, const net_addr *net)
 {
@@ -371,6 +510,99 @@ t_match_outer_net(void)
   return 1;
 }
 
+/*
+ * Read prefixes from @filename, build set of tries, prepare test data and do
+ * PREFIX_BENCH_NUM trie lookups. With @plus = 0, use random subset of known
+ * prefixes as test data, with @plus = 1, use randomly generated /32 prefixes
+ * as test data.
+ */
+static int
+benchmark_trie_dataset(const char *filename, int plus)
+{
+  int n = 0;
+  linpool *lp0 = lp_new_default(&root_pool);
+  linpool *lp1 = lp_new_default(&root_pool);
+  list *data[TRIE_BUFFER_SIZE];
+  struct f_trie *trie[TRIE_BUFFER_SIZE];
+  net_addr *nets;
+
+  bt_reset_suite_case_timer();
+  bt_log_suite_case_result(1, "Reading %s", filename, n);
+  n = read_prefix_file(filename, plus, lp0, lp1, data, trie);
+  bt_log_suite_case_result(1, "Read prefix data, %d lists, ", n);
+
+  size_t trie_size = rmemsize(lp1) * 1000 / (1024*1024);
+  bt_log_suite_case_result(1, "Trie size %u.%03u MB",
+			   (uint) (trie_size / 1000), (uint) (trie_size % 1000));
+
+  int t = PREFIX_BENCH_NUM / n;
+  int tb = MIN(t, TEST_BUFFER_SIZE);
+  nets = lp_alloc(lp0, tb * sizeof(net_addr));
+
+  if (!plus)
+    select_random_prefix_subset(data, nets, n, tb);
+  else
+    make_random_addresses(nets, tb);
+
+  bt_log_suite_case_result(1, "Make test data, %d (%d) tests", t, tb);
+  bt_reset_suite_case_timer();
+
+  /*
+  int match = 0;
+  for (int i = 0; i < t; i++)
+    for (int j = 0; j < n; j++)
+      test_match_net(data[j], trie[j], &nets[i]);
+  */
+
+  int match = 0;
+  for (int i = 0; i < t; i++)
+    for (int j = 0; j < n; j++)
+      if (trie_match_net(trie[j], &nets[i % TEST_BUFFER_SIZE]))
+	match++;
+
+  bt_log_suite_case_result(1, "Matching done, %d / %d matches", match, t * n);
+
+  rfree(lp0);
+  rfree(lp1);
+
+  return 1;
+}
+
+static int UNUSED
+t_bench_trie_datasets_subset(void)
+{
+  bt_bird_init();
+  bt_config_parse(BT_CONFIG_SIMPLE);
+
+  /* Specific datasets, not included */
+  benchmark_trie_dataset("trie-data-bgp-1", 0);
+  benchmark_trie_dataset("trie-data-bgp-10", 0);
+  benchmark_trie_dataset("trie-data-bgp-100", 0);
+  benchmark_trie_dataset("trie-data-bgp-1000", 0);
+
+  bt_bird_cleanup();
+
+  return 1;
+}
+
+static int UNUSED
+t_bench_trie_datasets_random(void)
+{
+  bt_bird_init();
+  bt_config_parse(BT_CONFIG_SIMPLE);
+
+  /* Specific datasets, not included */
+  benchmark_trie_dataset("trie-data-bgp-1", 1);
+  benchmark_trie_dataset("trie-data-bgp-10", 1);
+  benchmark_trie_dataset("trie-data-bgp-100", 1);
+  benchmark_trie_dataset("trie-data-bgp-1000", 1);
+
+  bt_bird_cleanup();
+
+  return 1;
+}
+
+
 static int
 t_trie_same(void)
 {
@@ -411,5 +643,8 @@ main(int argc, char *argv[])
   bt_test_suite(t_match_outer_net, "Testing random outer prefix matching");
   bt_test_suite(t_trie_same, "A trie filled forward should be same with a trie filled backward.");
 
+  // bt_test_suite(t_bench_trie_datasets_subset, "Benchmark tries from datasets by random subset of nets");
+  // bt_test_suite(t_bench_trie_datasets_random, "Benchmark tries from datasets by generated addresses");
+
   return bt_exit_value();
 }
diff --git a/test/birdtest.c b/test/birdtest.c
index d739e78b..053954e1 100644
--- a/test/birdtest.c
+++ b/test/birdtest.c
@@ -309,6 +309,12 @@ bt_log_suite_case_result(int result, const char *fmt, ...)
   }
 }
 
+void
+bt_reset_suite_case_timer(void)
+{
+  clock_gettime(CLOCK_MONOTONIC, &bt_suite_case_begin);
+}
+
 int
 bt_test_suite_base(int (*fn)(const void *), const char *id, const void *fn_arg, int forked, int timeout, const char *dsc, ...)
 {
diff --git a/test/birdtest.h b/test/birdtest.h
index 7a0c2fc4..ad5f8f9c 100644
--- a/test/birdtest.h
+++ b/test/birdtest.h
@@ -32,6 +32,7 @@ extern const char *bt_test_id;
 
 void bt_init(int argc, char *argv[]);
 int  bt_exit_value(void);
+void bt_reset_suite_case_timer(void);
 int bt_test_suite_base(int (*test_fn)(const void *), const char *test_id, const void *test_fn_argument, int forked, int timeout, const char *dsc, ...);
 static inline u64 bt_random(void)
 { return ((u64) random() & 0xffffffff) | ((u64) random() << 32); }
-- 
cgit v1.2.3


From 14fc24f3a53ebc5525b854ccdc93274aa74a400f Mon Sep 17 00:00:00 2001
From: "Ondrej Zajicek (work)" <santiago@crfreenet.org>
Date: Fri, 26 Nov 2021 03:26:36 +0100
Subject: Trie: Implement longest-prefix-match queries and walks

The prefix trie now supports longest-prefix-match query by function
trie_match_longest_ipX() and it can be extended to iteration over all
covering prefixes for a given prefix (from longest to shortest) using
TRIE_WALK_TO_ROOT_IPx() macro.
---
 filter/data.h      |  51 ++++++++++++++
 filter/trie.c      | 190 ++++++++++++++++++++++++++++++++++++++++++++++++++++-
 filter/trie_test.c | 115 ++++++++++++++++++++++++++++++++
 test/birdtest.c    |   5 +-
 4 files changed, 359 insertions(+), 2 deletions(-)

(limited to 'test/birdtest.c')

diff --git a/filter/data.h b/filter/data.h
index 4a0ee865..28c7a888 100644
--- a/filter/data.h
+++ b/filter/data.h
@@ -196,11 +196,61 @@ void tree_walk(const struct f_tree *t, void (*hook)(const struct f_tree *, void
 struct f_trie *f_new_trie(linpool *lp, uint data_size);
 void *trie_add_prefix(struct f_trie *t, const net_addr *n, uint l, uint h);
 int trie_match_net(const struct f_trie *t, const net_addr *n);
+int trie_match_longest_ip4(const struct f_trie *t, const net_addr_ip4 *net, net_addr_ip4 *dst, ip4_addr *found0);
+int trie_match_longest_ip6(const struct f_trie *t, const net_addr_ip6 *net, net_addr_ip6 *dst, ip6_addr *found0);
 void trie_walk_init(struct f_trie_walk_state *s, const struct f_trie *t, const net_addr *from);
 int trie_walk_next(struct f_trie_walk_state *s, net_addr *net);
 int trie_same(const struct f_trie *t1, const struct f_trie *t2);
 void trie_format(const struct f_trie *t, buffer *buf);
 
+static inline int
+trie_match_next_longest_ip4(net_addr_ip4 *n, ip4_addr *found)
+{
+  while (n->pxlen)
+  {
+    n->pxlen--;
+    ip4_clrbit(&n->prefix, n->pxlen);
+
+    if (ip4_getbit(*found, n->pxlen))
+      return 1;
+  }
+
+  return 0;
+}
+
+static inline int
+trie_match_next_longest_ip6(net_addr_ip6 *n, ip6_addr *found)
+{
+  while (n->pxlen)
+  {
+    n->pxlen--;
+    ip6_clrbit(&n->prefix, n->pxlen);
+
+    if (ip6_getbit(*found, n->pxlen))
+      return 1;
+  }
+
+  return 0;
+}
+
+
+#define TRIE_WALK_TO_ROOT_IP4(trie, net, dst) ({		\
+  net_addr_ip4 dst;						\
+  ip4_addr _found;						\
+  for (int _n = trie_match_longest_ip4(trie, net, &dst, &_found); \
+       _n;							\
+       _n = trie_match_next_longest_ip4(&dst, &_found))
+
+#define TRIE_WALK_TO_ROOT_IP6(trie, net, dst) ({		\
+  net_addr_ip6 dst;						\
+  ip6_addr _found;						\
+  for (int _n = trie_match_longest_ip6(trie, net, &dst, &_found); \
+       _n;							\
+       _n = trie_match_next_longest_ip6(&dst, &_found))
+
+#define TRIE_WALK_TO_ROOT_END })
+
+
 #define TRIE_WALK(trie, net, from) ({				\
   net_addr net;							\
   struct f_trie_walk_state tws_;				\
@@ -209,6 +259,7 @@ void trie_format(const struct f_trie *t, buffer *buf);
 
 #define TRIE_WALK_END })
 
+
 #define F_CMP_ERROR 999
 
 const char *f_type_name(enum f_type t);
diff --git a/filter/trie.c b/filter/trie.c
index 21b5b5d7..66b56297 100644
--- a/filter/trie.c
+++ b/filter/trie.c
@@ -85,7 +85,7 @@
  *
  * Iteration over prefixes in a trie can be done using TRIE_WALK() macro, or
  * directly using trie_walk_init() and trie_walk_next() functions. The second
- * approeach allows suspending the iteration and continuing in it later.
+ * approach allows suspending the iteration and continuing in it later.
  * Prefixes are enumerated in the usual lexicographic order and may be
  * restricted to a subset of the trie (all subnets of a specified prefix).
  *
@@ -100,6 +100,13 @@
  * path between the current node and its parent node, stored in the bitmap
  * &accept of the current node) and &local_pos for iteration over intra-node
  * prefixes (stored in the bitmap &local).
+ *
+ * The trie also supports longest-prefix-match query by trie_match_longest_ip4()
+ * and it can be extended to iteration over all covering prefixes for a given
+ * prefix (from longest to shortest) using TRIE_WALK_TO_ROOT_IP4() macro. There
+ * are also IPv6 versions (for practical reasons, these functions and macros are
+ * separate for IPv4 and IPv6). There is the same limitation to enumeration of
+ * `implicit' prefixes like with the previous TRIE_WALK() macro.
  */
 
 #include "nest/bird.h"
@@ -541,6 +548,187 @@ trie_match_net(const struct f_trie *t, const net_addr *n)
 }
 
 
+/**
+ * trie_match_longest_ip4
+ * @t: trie
+ * @net: net address
+ * @dst: return value
+ * @found0: optional returned bitmask of found nodes
+ *
+ * Perform longest prefix match for the address @net and return the resulting
+ * prefix in the buffer @dst. The bitmask @found0 is used to report lengths of
+ * prefixes on the path from the root to the resulting prefix. E.g., if there is
+ * also a /20 shorter matching prefix, then 20-th bit is set in @found0. This
+ * can be used to enumerate all matching prefixes for the network @net using
+ * function trie_match_next_longest_ip4() or macro TRIE_WALK_TO_ROOT_IP4().
+ *
+ * This function assumes IPv4 trie, there is also an IPv6 variant.
+ *
+ * Result: 1 if a matching prefix was found, 0 if not.
+ */
+int
+trie_match_longest_ip4(const struct f_trie *t, const net_addr_ip4 *net, net_addr_ip4 *dst, ip4_addr *found0)
+{
+  ASSERT(t->ipv4);
+
+  const struct f_trie_node4 *n = &t->root.v4;
+  int len = 0;
+
+  ip4_addr found = IP4_NONE;
+  int last = -1;
+
+  while (n)
+  {
+    /* We are out of path */
+    if (!ip4_prefix_equal(net->prefix, n->addr, MIN(net->pxlen, n->plen)))
+      goto done;
+
+    /* Check accept mask */
+    for (; len < n->plen; len++)
+    {
+      if (len > net->pxlen)
+	goto done;
+
+      if (ip4_getbit(n->accept, len - 1))
+      {
+	/* len is always < 32 due to len < n->plen */
+	ip4_setbit(&found, len);
+	last = len;
+      }
+    }
+
+    /* Special case for max length, there is only one valid local position */
+    if (len == IP4_MAX_PREFIX_LENGTH)
+    {
+      if (n->local & (1u << 1))
+	last = len;
+
+      goto done;
+    }
+
+    /* Check local mask */
+    for (int pos = 1; pos < (1 << TRIE_STEP); pos = 2 * pos + ip4_getbit(net->prefix, len), len++)
+    {
+      if (len > net->pxlen)
+	goto done;
+
+      if (n->local & (1u << pos))
+      {
+	/* len is always < 32 due to special case above */
+	ip4_setbit(&found, len);
+	last = len;
+      }
+    }
+
+    /* Choose child */
+    n = n->c[ip4_getbits(net->prefix, n->plen, TRIE_STEP)];
+  }
+
+done:
+  if (last < 0)
+    return 0;
+
+  net_copy_ip4(dst, net);
+  dst->prefix = ip4_and(dst->prefix, ip4_mkmask(last));
+  dst->pxlen = last;
+
+  if (found0)
+    *found0 = found;
+
+  return 1;
+}
+
+
+/**
+ * trie_match_longest_ip6
+ * @t: trie
+ * @net: net address
+ * @dst: return value
+ * @found0: optional returned bitmask of found nodes
+ *
+ * Perform longest prefix match for the address @net and return the resulting
+ * prefix in the buffer @dst. The bitmask @found0 is used to report lengths of
+ * prefixes on the path from the root to the resulting prefix. E.g., if there is
+ * also a /20 shorter matching prefix, then 20-th bit is set in @found0. This
+ * can be used to enumerate all matching prefixes for the network @net using
+ * function trie_match_next_longest_ip6() or macro TRIE_WALK_TO_ROOT_IP6().
+ *
+ * This function assumes IPv6 trie, there is also an IPv4 variant.
+ *
+ * Result: 1 if a matching prefix was found, 0 if not.
+ */
+int
+trie_match_longest_ip6(const struct f_trie *t, const net_addr_ip6 *net, net_addr_ip6 *dst, ip6_addr *found0)
+{
+  ASSERT(!t->ipv4);
+
+  const struct f_trie_node6 *n = &t->root.v6;
+  int len = 0;
+
+  ip6_addr found = IP6_NONE;
+  int last = -1;
+
+  while (n)
+  {
+    /* We are out of path */
+    if (!ip6_prefix_equal(net->prefix, n->addr, MIN(net->pxlen, n->plen)))
+      goto done;
+
+    /* Check accept mask */
+    for (; len < n->plen; len++)
+    {
+      if (len > net->pxlen)
+	goto done;
+
+      if (ip6_getbit(n->accept, len - 1))
+      {
+	/* len is always < 128 due to len < n->plen */
+	ip6_setbit(&found, len);
+	last = len;
+      }
+    }
+
+    /* Special case for max length, there is only one valid local position */
+    if (len == IP6_MAX_PREFIX_LENGTH)
+    {
+      if (n->local & (1u << 1))
+	last = len;
+
+      goto done;
+    }
+
+    /* Check local mask */
+    for (int pos = 1; pos < (1 << TRIE_STEP); pos = 2 * pos + ip6_getbit(net->prefix, len), len++)
+    {
+      if (len > net->pxlen)
+	goto done;
+
+      if (n->local & (1u << pos))
+      {
+	/* len is always < 128 due to special case above */
+	ip6_setbit(&found, len);
+	last = len;
+      }
+    }
+
+    /* Choose child */
+    n = n->c[ip6_getbits(net->prefix, n->plen, TRIE_STEP)];
+  }
+
+done:
+  if (last < 0)
+    return 0;
+
+  net_copy_ip6(dst, net);
+  dst->prefix = ip6_and(dst->prefix, ip6_mkmask(last));
+  dst->pxlen = last;
+
+  if (found0)
+    *found0 = found;
+
+  return 1;
+}
+
 #define SAME_PREFIX(A,B,X,L) ((X) ? ip4_prefix_equal((A)->v4.addr, net4_prefix(B), (L)) : ip6_prefix_equal((A)->v6.addr, net6_prefix(B), (L)))
 #define GET_NET_BITS(N,X,A,B) ((X) ? ip4_getbits(net4_prefix(N), (A), (B)) : ip6_getbits(net6_prefix(N), (A), (B)))
 
diff --git a/filter/trie_test.c b/filter/trie_test.c
index bb9a2f26..eee48284 100644
--- a/filter/trie_test.c
+++ b/filter/trie_test.c
@@ -774,6 +774,120 @@ t_trie_walk(void)
   return 1;
 }
 
+static int
+find_covering_nets(struct f_prefix *prefixes, int num, const net_addr *net, net_addr *found)
+{
+  struct f_prefix key;
+  net_addr *n = &key.net;
+  int found_num = 0;
+
+  net_copy(n, net);
+
+  while (1)
+  {
+    struct f_prefix *px =
+      bsearch(&key, prefixes, num, sizeof(struct f_prefix), compare_prefixes);
+
+    if (px)
+    {
+      net_copy(&found[found_num], n);
+      found_num++;
+    }
+
+    if (n->pxlen == 0)
+      return found_num;
+
+    n->pxlen--;
+
+    if (n->type == NET_IP4)
+      ip4_clrbit(&((net_addr_ip4 *) n)->prefix, n->pxlen);
+    else
+      ip6_clrbit(&((net_addr_ip6 *) n)->prefix, n->pxlen);
+  }
+}
+
+static int
+t_trie_walk_to_root(void)
+{
+  bt_bird_init();
+  bt_config_parse(BT_CONFIG_SIMPLE);
+
+  linpool *lp = lp_new_default(&root_pool);
+  for (int round = 0; round < TESTS_NUM * 4; round++)
+  {
+    int level = round / TESTS_NUM;
+    int v6 = level % 2;
+    int num = PREFIXES_NUM  * (int[]){32, 512}[level / 2];
+    int pos = 0;
+    int st = 0, sn = 0, sm = 0;
+
+    list *prefixes = make_random_prefix_list(lp, num, v6, 1);
+    struct f_trie *trie = make_trie_from_prefix_list(lp, prefixes);
+    struct f_prefix *pxset = malloc((num + 1) * sizeof(struct f_prefix));
+
+    struct f_prefix_node *pxn;
+    WALK_LIST(pxn, *prefixes)
+      pxset[pos++] = pxn->prefix;
+    memset(&pxset[pos], 0, sizeof (struct f_prefix));
+
+    qsort(pxset, num, sizeof(struct f_prefix), compare_prefixes);
+
+    int i;
+    for (i = 0; i < (PREFIX_TESTS_NUM / 10); i++)
+    {
+      net_addr from;
+      get_random_net(&from, v6);
+
+      net_addr found[129];
+      int found_num = find_covering_nets(pxset, num, &from, found);
+      int n = 0;
+
+      if (bt_verbose >= BT_VERBOSE_ABSOLUTELY_ALL)
+      {
+	char buf[64];
+	bt_format_net(buf, 64, &from);
+	bt_debug("Lookup for %s (expect %d)\n", buf, found_num);
+      }
+
+      /* Walk to root, separate for IPv4 and IPv6 */
+      if (!v6)
+      {
+	TRIE_WALK_TO_ROOT_IP4(trie, (net_addr_ip4 *) &from, net)
+	{
+	  log_networks((net_addr *) &net, &found[n]);
+	  bt_assert((n < found_num) && net_equal((net_addr *) &net, &found[n]));
+	  n++;
+	}
+	TRIE_WALK_TO_ROOT_END;
+      }
+      else
+      {
+	TRIE_WALK_TO_ROOT_IP6(trie, (net_addr_ip6 *) &from, net)
+	{
+	  log_networks((net_addr *) &net, &found[n]);
+	  bt_assert((n < found_num) && net_equal((net_addr *) &net, &found[n]));
+	  n++;
+	}
+	TRIE_WALK_TO_ROOT_END;
+      }
+
+      bt_assert(n == found_num);
+
+      /* Stats */
+      st += n;
+      sn += !!n;
+      sm = MAX(sm, n);
+    }
+
+    bt_debug("Success in %d / %d, sum %d, max %d\n", sn, i, st, sm);
+
+    lp_flush(lp);
+  }
+
+  bt_bird_cleanup();
+  return 1;
+}
+
 int
 main(int argc, char *argv[])
 {
@@ -784,6 +898,7 @@ main(int argc, char *argv[])
   bt_test_suite(t_match_outer_net, "Testing random outer prefix matching");
   bt_test_suite(t_trie_same, "A trie filled forward should be same with a trie filled backward.");
   bt_test_suite(t_trie_walk, "Testing TRIE_WALK() on random tries");
+  bt_test_suite(t_trie_walk_to_root, "Testing TRIE_WALK_TO_ROOT() on random tries");
 
   // bt_test_suite(t_bench_trie_datasets_subset, "Benchmark tries from datasets by random subset of nets");
   // bt_test_suite(t_bench_trie_datasets_random, "Benchmark tries from datasets by generated addresses");
diff --git a/test/birdtest.c b/test/birdtest.c
index 053954e1..6ad743ce 100644
--- a/test/birdtest.c
+++ b/test/birdtest.c
@@ -510,7 +510,10 @@ bt_fmt_ipa(char *buf, size_t size, const void *data)
 void
 bt_format_net(char *buf, size_t size, const void *data)
 {
-  bsnprintf(buf, size, "%N", (const net_addr *) data);
+  if (data)
+    bsnprintf(buf, size, "%N", (const net_addr *) data);
+  else
+    bsnprintf(buf, size, "(null)");
 }
 
 int
-- 
cgit v1.2.3


From 48bf1322aa141ca6259b26b37551402758cff0cc Mon Sep 17 00:00:00 2001
From: Maria Matejka <mq@ucw.cz>
Date: Wed, 2 Mar 2022 10:35:21 +0100
Subject: Introducing an universal temporary linpool flushed after every task

---
 lib/event.c      |  2 ++
 lib/mempool.c    |  2 ++
 lib/resource.c   |  1 +
 lib/resource.h   |  9 +++++++++
 lib/timer.c      |  1 +
 proto/bfd/io.c   |  2 ++
 sysdep/unix/io.c | 23 ++++++++++++++++++++---
 test/birdtest.c  |  4 ++++
 test/bt-utils.c  |  1 -
 9 files changed, 41 insertions(+), 4 deletions(-)

(limited to 'test/birdtest.c')

diff --git a/lib/event.c b/lib/event.c
index 273447e0..33dc00b0 100644
--- a/lib/event.c
+++ b/lib/event.c
@@ -157,6 +157,7 @@ ev_run_list(event_list *l)
 	io_log_event(e->hook, e->data);
 
       ev_run(e);
+      tmp_flush();
     }
 
   return !EMPTY_LIST(*l);
@@ -184,6 +185,7 @@ ev_run_list_limited(event_list *l, uint limit)
 	io_log_event(e->hook, e->data);
 
       ev_run(e);
+      tmp_flush();
       limit--;
     }
 
diff --git a/lib/mempool.c b/lib/mempool.c
index 90d7c774..169826d4 100644
--- a/lib/mempool.c
+++ b/lib/mempool.c
@@ -42,6 +42,8 @@ struct linpool {
   uint chunk_size, threshold, total, total_large;
 };
 
+_Thread_local linpool *tmp_linpool;
+
 static void lp_free(resource *);
 static void lp_dump(resource *);
 static resource *lp_lookup(resource *, unsigned long);
diff --git a/lib/resource.c b/lib/resource.c
index 5d4c7780..5636872c 100644
--- a/lib/resource.c
+++ b/lib/resource.c
@@ -273,6 +273,7 @@ resource_init(void)
   root_pool.r.class = &pool_class;
   root_pool.name = "Root";
   init_list(&root_pool.inside);
+  tmp_init(&root_pool);
 }
 
 /**
diff --git a/lib/resource.h b/lib/resource.h
index 9ec41ed8..0e4c44d8 100644
--- a/lib/resource.h
+++ b/lib/resource.h
@@ -79,6 +79,15 @@ void lp_flush(linpool *);			/* Free everything, but leave linpool */
 void lp_save(linpool *m, lp_state *p);		/* Save state */
 void lp_restore(linpool *m, lp_state *p);	/* Restore state */
 
+extern _Thread_local linpool *tmp_linpool;	/* Temporary linpool autoflushed regularily */
+
+#define tmp_alloc(sz)	lp_alloc(tmp_linpool, sz)
+#define tmp_allocu(sz)	lp_allocu(tmp_linpool, sz)
+#define tmp_allocz(sz)	lp_allocz(tmp_linpool, sz)
+
+#define tmp_init(p)	tmp_linpool = lp_new_default(p)
+#define tmp_flush()	lp_flush(tmp_linpool)
+
 extern const int lp_chunk_size;
 #define LP_GAS		    1024
 #define LP_GOOD_SIZE(x)	    (((x + LP_GAS - 1) & (~(LP_GAS - 1))) - lp_chunk_size)
diff --git a/lib/timer.c b/lib/timer.c
index 381163d0..c47e0bbc 100644
--- a/lib/timer.c
+++ b/lib/timer.c
@@ -233,6 +233,7 @@ timers_fire(struct timeloop *loop)
       io_log_event(t->hook, t->data);
 
     t->hook(t);
+    tmp_flush();
   }
 }
 
diff --git a/proto/bfd/io.c b/proto/bfd/io.c
index 1cd9365a..e696cc89 100644
--- a/proto/bfd/io.c
+++ b/proto/bfd/io.c
@@ -482,6 +482,8 @@ birdloop_main(void *arg)
 
   birdloop_set_current(loop);
 
+  tmp_init(loop->pool);
+
   pthread_mutex_lock(&loop->mutex);
   while (1)
   {
diff --git a/sysdep/unix/io.c b/sysdep/unix/io.c
index 4fd77453..8a116789 100644
--- a/sysdep/unix/io.c
+++ b/sysdep/unix/io.c
@@ -1854,8 +1854,8 @@ sk_read_ssh(sock *s)
 
  /* sk_read() and sk_write() are called from BFD's event loop */
 
-int
-sk_read(sock *s, int revents)
+static inline int
+sk_read_noflush(sock *s, int revents)
 {
   switch (s->type)
   {
@@ -1918,7 +1918,15 @@ sk_read(sock *s, int revents)
 }
 
 int
-sk_write(sock *s)
+sk_read(sock *s, int revents)
+{
+  int e = sk_read_noflush(s, revents);
+  tmp_flush();
+  return e;
+}
+
+static inline int
+sk_write_noflush(sock *s)
 {
   switch (s->type)
   {
@@ -1966,6 +1974,14 @@ sk_write(sock *s)
   }
 }
 
+int
+sk_write(sock *s)
+{
+  int e = sk_write_noflush(s);
+  tmp_flush();
+  return e;
+}
+
 int sk_is_ipv4(sock *s)
 { return s->af == AF_INET; }
 
@@ -1984,6 +2000,7 @@ sk_err(sock *s, int revents)
     }
 
   s->err_hook(s, se);
+  tmp_flush();
 }
 
 void
diff --git a/test/birdtest.c b/test/birdtest.c
index 86a8882f..10d6d6de 100644
--- a/test/birdtest.c
+++ b/test/birdtest.c
@@ -119,6 +119,8 @@ bt_init(int argc, char *argv[])
   clock_gettime(CLOCK_MONOTONIC, &bt_begin);
   bt_suite_case_begin = bt_suite_begin = bt_begin;
 
+  resource_init();
+
   return;
 
  usage:
@@ -172,6 +174,8 @@ int bt_run_test_fn(int (*fn)(const void *), const void *fn_arg, int timeout)
   if (!bt_suite_result)
     result = 0;
 
+  tmp_flush();
+
   return result;
 }
 
diff --git a/test/bt-utils.c b/test/bt-utils.c
index cbca3a6b..2a7799c3 100644
--- a/test/bt-utils.c
+++ b/test/bt-utils.c
@@ -60,7 +60,6 @@ bt_bird_init(void)
     log_init_debug("");
   log_switch(bt_verbose != 0, NULL, NULL);
 
-  resource_init();
   olock_init();
   timer_init();
   io_init();
-- 
cgit v1.2.3


From 9e60a1fbc3ef9ab93b414dcf451bbe741e2e8827 Mon Sep 17 00:00:00 2001
From: Maria Matejka <mq@ucw.cz>
Date: Wed, 9 Mar 2022 10:30:03 +0100
Subject: Fixed resource initialization in unit tests

---
 lib/bitmap_test.c   | 3 ---
 lib/buffer_test.c   | 1 -
 lib/event_test.c    | 1 -
 lib/flowspec_test.c | 3 ---
 lib/hash_test.c     | 1 -
 nest/a-path_test.c  | 8 --------
 nest/a-set_test.c   | 9 ---------
 sysdep/unix/alloc.c | 2 ++
 test/birdtest.c     | 2 ++
 9 files changed, 4 insertions(+), 26 deletions(-)

(limited to 'test/birdtest.c')

diff --git a/lib/bitmap_test.c b/lib/bitmap_test.c
index 0595a4d0..07860c94 100644
--- a/lib/bitmap_test.c
+++ b/lib/bitmap_test.c
@@ -24,7 +24,6 @@ t_bmap_set_clear_random(void)
 {
   struct bmap b;
 
-  resource_init();
   bmap_init(&b, &root_pool, 1024);
 
   char expected[MAX_NUM] = {};
@@ -60,7 +59,6 @@ t_hmap_set_clear_random(void)
 {
   struct hmap b;
 
-  resource_init();
   hmap_init(&b, &root_pool, 1024);
 
   char expected[MAX_NUM] = {};
@@ -119,7 +117,6 @@ t_hmap_set_clear_fill(void)
 {
   struct hmap b;
 
-  resource_init();
   hmap_init(&b, &root_pool, 1024);
 
   char expected[MAX_NUM] = {};
diff --git a/lib/buffer_test.c b/lib/buffer_test.c
index 5b7de330..0629e901 100644
--- a/lib/buffer_test.c
+++ b/lib/buffer_test.c
@@ -41,7 +41,6 @@ fill_expected_array(void)
 static void
 init_buffer(void)
 {
-  resource_init();
   buffer_pool = &root_pool;
   BUFFER_INIT(buf, buffer_pool, MAX_NUM);
 }
diff --git a/lib/event_test.c b/lib/event_test.c
index e1215bba..e1fbea8f 100644
--- a/lib/event_test.c
+++ b/lib/event_test.c
@@ -53,7 +53,6 @@ t_ev_run_list(void)
 {
   int i;
 
-  resource_init();
   olock_init();
   timer_init();
   io_init();
diff --git a/lib/flowspec_test.c b/lib/flowspec_test.c
index 115084a3..03649b99 100644
--- a/lib/flowspec_test.c
+++ b/lib/flowspec_test.c
@@ -446,8 +446,6 @@ t_validation6(void)
 static int
 t_builder4(void)
 {
-  resource_init();
-
   struct flow_builder *fb = flow_builder_init(&root_pool);
 
   /* Expectation */
@@ -528,7 +526,6 @@ t_builder6(void)
 {
   net_addr_ip6 ip;
 
-  resource_init();
   struct flow_builder *fb = flow_builder_init(&root_pool);
   fb->ipv6 = 1;
 
diff --git a/lib/hash_test.c b/lib/hash_test.c
index 59beb7c0..4bce7017 100644
--- a/lib/hash_test.c
+++ b/lib/hash_test.c
@@ -61,7 +61,6 @@ dump_nodes(void)
 static void
 init_hash_(uint order)
 {
-  resource_init();
   my_pool = rp_new(&root_pool, "Test pool");
 
   HASH_INIT(hash, my_pool, order);
diff --git a/nest/a-path_test.c b/nest/a-path_test.c
index abd2abbf..e007a450 100644
--- a/nest/a-path_test.c
+++ b/nest/a-path_test.c
@@ -23,8 +23,6 @@
 static int
 t_as_path_match(void)
 {
-  resource_init();
-
   int round;
   for (round = 0; round < TESTS_NUM; round++)
   {
@@ -69,8 +67,6 @@ t_as_path_match(void)
 static int
 t_path_format(void)
 {
-  resource_init();
-
   struct adata empty_as_path = {};
   struct adata *as_path = &empty_as_path;
 
@@ -114,8 +110,6 @@ count_asn_in_array(const u32 *array, u32 asn)
 static int
 t_path_include(void)
 {
-  resource_init();
-
   struct adata empty_as_path = {};
   struct adata *as_path = &empty_as_path;
 
@@ -158,8 +152,6 @@ t_path_include(void)
 static int
 t_as_path_converting(void)
 {
-  resource_init();
-
   struct adata empty_as_path = {};
   struct adata *as_path = &empty_as_path;
 #define AS_PATH_LENGTH_FOR_CONVERTING_TEST 10
diff --git a/nest/a-set_test.c b/nest/a-set_test.c
index 669872e3..904e6764 100644
--- a/nest/a-set_test.c
+++ b/nest/a-set_test.c
@@ -68,7 +68,6 @@ t_set_int_contains(void)
 {
   int i;
 
-  resource_init();
   generate_set_sequence(SET_TYPE_INT, SET_SIZE);
 
   bt_assert(int_set_get_size(set_sequence) == SET_SIZE);
@@ -88,7 +87,6 @@ t_set_int_contains(void)
 static int
 t_set_int_union(void)
 {
-  resource_init();
   generate_set_sequence(SET_TYPE_INT, SET_SIZE);
 
   const struct adata *set_union;
@@ -106,7 +104,6 @@ t_set_int_union(void)
 static int
 t_set_int_format(void)
 {
-  resource_init();
   generate_set_sequence(SET_TYPE_INT, SET_SIZE_FOR_FORMAT_OUTPUT);
 
   bt_assert(int_set_format(set_sequence, 0, 0, buf, BUFFER_SIZE) == 0);
@@ -126,7 +123,6 @@ t_set_int_format(void)
 static int
 t_set_int_delete(void)
 {
-  resource_init();
   generate_set_sequence(SET_TYPE_INT, SET_SIZE);
 
   const struct adata *deleting_sequence = set_sequence;
@@ -154,7 +150,6 @@ t_set_ec_contains(void)
 {
   u32 i;
 
-  resource_init();
   generate_set_sequence(SET_TYPE_EC, SET_SIZE);
 
   bt_assert(ec_set_get_size(set_sequence) == SET_SIZE);
@@ -174,7 +169,6 @@ t_set_ec_contains(void)
 static int
 t_set_ec_union(void)
 {
-  resource_init();
   generate_set_sequence(SET_TYPE_EC, SET_SIZE);
 
   const struct adata *set_union;
@@ -192,8 +186,6 @@ t_set_ec_union(void)
 static int
 t_set_ec_format(void)
 {
-  resource_init();
-
   const struct adata empty_as_path = {};
   set_sequence = set_sequence_same = set_sequence_higher = set_random = &empty_as_path;
 
@@ -212,7 +204,6 @@ t_set_ec_format(void)
 static int
 t_set_ec_delete(void)
 {
-  resource_init();
   generate_set_sequence(SET_TYPE_EC, SET_SIZE);
 
   const struct adata *deleting_sequence = set_sequence;
diff --git a/sysdep/unix/alloc.c b/sysdep/unix/alloc.c
index f96c0fcf..755b5fa5 100644
--- a/sysdep/unix/alloc.c
+++ b/sysdep/unix/alloc.c
@@ -164,6 +164,8 @@ void
 resource_sys_init(void)
 {
 #ifdef HAVE_MMAP
+  ASSERT_DIE(global_free_pages.cnt == 0);
+
   if (!(page_size = sysconf(_SC_PAGESIZE)))
     die("System page size must be non-zero");
 
diff --git a/test/birdtest.c b/test/birdtest.c
index 10d6d6de..ae05d1a5 100644
--- a/test/birdtest.c
+++ b/test/birdtest.c
@@ -20,6 +20,7 @@
 
 #include "test/birdtest.h"
 #include "lib/string.h"
+#include "lib/event.h"
 
 #ifdef HAVE_EXECINFO_H
 #include <execinfo.h>
@@ -120,6 +121,7 @@ bt_init(int argc, char *argv[])
   bt_suite_case_begin = bt_suite_begin = bt_begin;
 
   resource_init();
+  ev_init_list(&global_event_list);
 
   return;
 
-- 
cgit v1.2.3


From f1d6c66a78758449f00ed709891e24ab3571cc9c Mon Sep 17 00:00:00 2001
From: Maria Matejka <mq@ucw.cz>
Date: Mon, 1 Aug 2022 15:17:41 +0200
Subject: Fixed main birdloop init in unit tests

Some unit tests weren't initializing the birdloop, trying to write the
birdloop ping into stdin. Fixed this and also forced stdin close on
startup of every test just to be sure that CI and local build behave the
same in this. (CI was failing on this while local build not.)
---
 lib/event_test.c | 3 ---
 test/birdtest.c  | 5 +++++
 test/bt-utils.c  | 2 --
 3 files changed, 5 insertions(+), 5 deletions(-)

(limited to 'test/birdtest.c')

diff --git a/lib/event_test.c b/lib/event_test.c
index 5385011a..612deb25 100644
--- a/lib/event_test.c
+++ b/lib/event_test.c
@@ -54,7 +54,6 @@ t_ev_run_list(void)
   int i;
 
   olock_init();
-  birdloop_init();
   rt_init();
   io_init();
   if_init();
@@ -81,9 +80,7 @@ main(int argc, char *argv[])
 {
   bt_init(argc, argv);
 
-  the_bird_lock();
   bt_test_suite(t_ev_run_list, "Schedule and run 3 events in right order.");
-  the_bird_unlock();
 
   return bt_exit_value();
 }
diff --git a/test/birdtest.c b/test/birdtest.c
index 2ae7b51e..5e3de1c5 100644
--- a/test/birdtest.c
+++ b/test/birdtest.c
@@ -65,6 +65,9 @@ bt_init(int argc, char *argv[])
 {
   int c;
 
+  /* We have no interest in stdin */
+  close(0);
+
   initstate(BT_RANDOM_SEED, (char *) bt_random_state, sizeof(bt_random_state));
 
   bt_verbose = 0;
@@ -121,9 +124,11 @@ bt_init(int argc, char *argv[])
   clock_gettime(CLOCK_MONOTONIC, &bt_begin);
   bt_suite_case_begin = bt_suite_begin = bt_begin;
 
+  the_bird_lock();
   resource_init();
   ev_init_list(&global_event_list, &main_birdloop, "Global event list in unit tests");
   ev_init_list(&global_work_list, &main_birdloop, "Global work list in unit tests");
+  birdloop_init();
   return;
 
  usage:
diff --git a/test/bt-utils.c b/test/bt-utils.c
index 3d56292e..36e44da4 100644
--- a/test/bt-utils.c
+++ b/test/bt-utils.c
@@ -62,9 +62,7 @@ bt_bird_init(void)
     log_init_debug("");
   log_switch(bt_verbose != 0, NULL, NULL);
 
-  the_bird_lock();
   olock_init();
-  birdloop_init();
   rt_init();
   io_init();
   if_init();
-- 
cgit v1.2.3