Nest: Add tests and benchmark for FIB

Basic fib_get() / fib_find() test for random prefixes, FIB_WALK() test,
and benchmark for fib_find(). Also generalize and reuse some code from
trie tests.

3 files changed, 142 insertions, 0 deletions

diff --git a/test/birdtest.h b/test/birdtest.h
index cfeebb98..540092d6 100644
--- a/test/birdtest.h
+++ b/test/birdtest.h
@@ -37,6 +37,10 @@ int bt_test_suite_base(int (*test_fn)(const void *), const char *test_id, const
 static inline u64 bt_random(void)
 { return ((u64) random() & 0xffffffff) | ((u64) random() << 32); }
 
+static inline u32 bt_random_n(u32 max)
+{ return random() % max; }
+
+
 void bt_log_suite_result(int result, const char *fmt, ...);
 void bt_log_suite_case_result(int result, const char *fmt, ...);
 
diff --git a/test/bt-utils.c b/test/bt-utils.c
index 8496e185..fb42cd35 100644
--- a/test/bt-utils.c
+++ b/test/bt-utils.c
@@ -219,3 +219,135 @@ bt_bytes_to_hex(char *buf, const byte *in_data, size_t size)
     sprintf(buf + i*2, "%02x", in_data[i]);
 }
 
+void
+bt_random_net(net_addr *net, int type)
+{
+  ip4_addr ip4;
+  ip6_addr ip6;
+  uint pxlen;
+
+  switch (type)
+  {
+  case NET_IP4:
+    pxlen = bt_random_n(24)+8;
+    ip4 = ip4_from_u32((u32) bt_random());
+    net_fill_ip4(net, ip4_and(ip4, ip4_mkmask(pxlen)), pxlen);
+    break;
+
+  case NET_IP6:
+    pxlen = bt_random_n(120)+8;
+    ip6 = ip6_build(bt_random(), bt_random(), bt_random(), bt_random());
+    net_fill_ip6(net, ip6_and(ip6, ip6_mkmask(pxlen)), pxlen);
+    break;
+
+  default:
+    die("Net type %d not implemented", type);
+  }
+}
+
+net_addr *
+bt_random_nets(int type, uint n)
+{
+  net_addr *nets = tmp_alloc(n * sizeof(net_addr));
+
+  for (uint i = 0; i < n; i++)
+    bt_random_net(&nets[i], type);
+
+  return nets;
+}
+
+net_addr *
+bt_random_net_subset(net_addr *src, uint sn, uint dn)
+{
+  net_addr *nets = tmp_alloc(dn * sizeof(net_addr));
+
+  for (uint i = 0; i < dn; i++)
+    net_copy(&nets[i], &src[bt_random_n(sn)]);
+
+  return nets;
+}
+
+void
+bt_read_net(const char *str, net_addr *net, int type)
+{
+  ip4_addr ip4;
+  ip6_addr ip6;
+  uint pxlen;
+  char addr[64];
+
+  switch (type)
+  {
+  case NET_IP4:
+    if (sscanf(str, "%[0-9.]/%u", addr, &pxlen) != 2)
+      goto err;
+
+    if (!ip4_pton(addr, &ip4))
+      goto err;
+
+    if (!net_validate_px4(ip4, pxlen))
+      goto err;
+
+    net_fill_ip4(net, ip4, pxlen);
+    break;
+
+  case NET_IP6:
+    if (sscanf(str, "%[0-9a-fA-F:.]/%u", addr, &pxlen) != 2)
+      goto err;
+
+    if (!ip6_pton(addr, &ip6))
+      goto err;
+
+    if (!net_validate_px6(ip6, pxlen))
+      goto err;
+
+    net_fill_ip6(net, ip6, pxlen);
+    break;
+
+  default:
+    die("Net type %d not implemented", type);
+  }
+  return;
+
+err:
+  bt_abort_msg("Invalid network '%s'", str);
+}
+
+net_addr *
+bt_read_nets(FILE *f, int type, uint *n)
+{
+  char str[80];
+
+  net_addr *nets = tmp_alloc(*n * sizeof(net_addr));
+  uint i = 0;
+
+  errno = 0;
+  while (fgets(str, sizeof(str), f))
+  {
+    if (str[0] == '\n')
+      break;
+
+    if (i >= *n)
+      bt_abort_msg("Too many networks");
+
+    bt_read_net(str, &nets[i], type);
+    bt_debug("ADD %s\n", str);
+    i++;
+  }
+  bt_syscall(errno, "fgets()");
+
+  bt_debug("DONE reading %u nets\n", i);
+
+  *n = i;
+  return nets;
+}
+
+net_addr *
+bt_read_net_file(const char *filename, int type, uint *n)
+{
+  FILE *f = fopen(filename, "r");
+  bt_syscall(!f, "fopen(%s)", filename);
+  net_addr *nets = bt_read_nets(f, type, n);
+  fclose(f);
+
+  return nets;
+}
diff --git a/test/bt-utils.h b/test/bt-utils.h
index 13d267cc..d29a0b7c 100644
--- a/test/bt-utils.h
+++ b/test/bt-utils.h
@@ -26,6 +26,12 @@
 
 uint bt_naive_pow(uint base, uint power);
 void bt_bytes_to_hex(char *buf, const byte *in_data, size_t size);
+void bt_random_net(net_addr *net, int type);
+net_addr *bt_random_nets(int type, uint n);
+net_addr *bt_random_net_subset(net_addr *src, uint sn, uint dn);
+void bt_read_net(const char *str, net_addr *net, int type);
+net_addr *bt_read_nets(FILE *f, int type, uint *n);
+net_addr *bt_read_net_file(const char *filename, int type, uint *n);
 
 void bt_bird_init(void);
 void bt_bird_cleanup(void);