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.

3 files changed, 242 insertions, 0 deletions

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); }