Lib: Basic and hierarchical bitmaps

Basic bitmap is obvious. Hierarchical bitmap is structure of several
bitmaps, where higher levels are conjunctions of intervals on level
below, allowing for efficient lookup of first unset bit.

5 files changed, 443 insertions, 2 deletions

diff --git a/lib/Makefile b/lib/Makefile
index 18816bb3..5c78b2a9 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -1,7 +1,7 @@
-src := bitops.c checksum.c event.c flowspec.c idm.c ip.c lists.c mac.c md5.c mempool.c net.c patmatch.c printf.c resource.c sha1.c sha256.c sha512.c slab.c slists.c strtoul.c tbf.c timer.c xmalloc.c
+src := bitmap.c bitops.c checksum.c event.c flowspec.c idm.c ip.c lists.c mac.c md5.c mempool.c net.c patmatch.c printf.c resource.c sha1.c sha256.c sha512.c slab.c slists.c strtoul.c tbf.c timer.c xmalloc.c
 obj := $(src-o-files)
 $(all-daemon)
 
-tests_src := heap_test.c buffer_test.c event_test.c flowspec_test.c bitops_test.c patmatch_test.c fletcher16_test.c slist_test.c checksum_test.c lists_test.c mac_test.c ip_test.c hash_test.c printf_test.c
+tests_src := bitmap_test.c heap_test.c buffer_test.c event_test.c flowspec_test.c bitops_test.c patmatch_test.c fletcher16_test.c slist_test.c checksum_test.c lists_test.c mac_test.c ip_test.c hash_test.c printf_test.c
 tests_targets := $(tests_targets) $(tests-target-files)
 tests_objs := $(tests_objs) $(src-o-files)
diff --git a/lib/bitmap.c b/lib/bitmap.c
new file mode 100644
index 00000000..16bb1464
--- /dev/null
+++ b/lib/bitmap.c
@@ -0,0 +1,190 @@
+/*
+ *	BIRD Library -- Bitmaps
+ *
+ *	(c) 2019 Ondrej Zajicek <santiago@crfreenet.org>
+ *	(c) 2019 CZ.NIC z.s.p.o.
+ *
+ *	Can be freely distributed and used under the terms of the GNU GPL.
+ */
+
+#include <stdlib.h>
+
+#include "nest/bird.h"
+#include "lib/bitmap.h"
+#include "lib/bitops.h"
+#include "lib/resource.h"
+
+
+/*
+ *	Basic bitmap
+ */
+
+void
+bmap_init(struct bmap *b, pool *p, uint size)
+{
+  b->size = BIRD_ALIGN(size, 4);
+  b->data = mb_allocz(p, b->size);
+}
+
+void
+bmap_grow(struct bmap *b, uint need)
+{
+  uint size = b->size * 2;
+  while (size < need)
+    size *= 2;
+
+  uint old_size = b->size;
+  b->size = size;
+  b->data = mb_realloc(b->data, b->size);
+
+  ASSERT(size >= old_size);
+  memset(b->data + (old_size / 4), 0, size - old_size);
+}
+
+void
+bmap_free(struct bmap *b)
+{
+  mb_free(b->data);
+  b->size = 0;
+  b->data = NULL;
+}
+
+
+
+/*
+ *	Hierarchical bitmap
+ */
+
+#define B256_SIZE(b)  BIRD_ALIGN(b, 32)
+#define B256_STEP(b) (BIRD_ALIGN(b, 8192) >> 8)
+
+void
+hmap_init(struct hmap *b, pool *p, uint size)
+{
+  b->size[0] = B256_SIZE(size);
+  b->size[1] = B256_STEP(b->size[0]);
+  b->size[2] = B256_STEP(b->size[1]);
+  b->size[3] = sizeof(b->root);
+
+  b->data[0] = mb_allocz(p, b->size[0]);
+  b->data[1] = mb_allocz(p, b->size[1]);
+  b->data[2] = mb_allocz(p, b->size[2]);
+  b->data[3] = b->root;
+
+  memset(b->root, 0, sizeof(b->root));
+}
+
+static void
+hmap_grow(struct hmap *b, uint need)
+{
+  uint size = b->size[0] * 2;
+  while (size < need)
+    size *= 2;
+
+  for (uint i = 0; i < 3; i++)
+  {
+    uint old_size = b->size[i];
+    b->size[i] = size;
+    b->data[i] = mb_realloc(b->data[i], b->size[i]);
+
+    ASSERT(size >= old_size);
+    memset(b->data[i] + (old_size / 4), 0, size - old_size);
+
+    size = B256_STEP(size);
+  }
+}
+
+void
+hmap_free(struct hmap *b)
+{
+  mb_free(b->data[0]);
+  mb_free(b->data[1]);
+  mb_free(b->data[2]);
+
+  memset(b, 0, sizeof(struct hmap));
+}
+
+static inline int
+b256_and(u32 *p)
+{
+  for (int i = 0; i < 8; i++)
+    if (~p[i])
+      return 0;
+
+  return 1;
+}
+
+void
+hmap_set(struct hmap *b, uint n)
+{
+  if (n >= hmap_max(b))
+    hmap_grow(b, n/8 + 1);
+
+  for (int i = 0; i < 4; i++)
+  {
+    BIT32_SET(b->data[i], n);
+    n = n >> 8;
+
+    /* Continue if all bits in 256-bit block are set */
+    if (! b256_and(b->data[i] + 8*n))
+      break;
+  }
+}
+
+void
+hmap_clear(struct hmap *b, uint n)
+{
+  if (n >= hmap_max(b))
+    return;
+
+  for (int i = 0; i < 4; i++)
+  {
+    BIT32_CLR(b->data[i], n);
+    n = n >> 8;
+  }
+}
+
+static inline int
+b256_first_zero(u32 *p)
+{
+  for (int i = 0; i < 8; i++)
+    if (~p[i])
+      return 32*i + u32_ctz(~p[i]);
+
+  return 256;
+}
+
+u32
+hmap_first_zero(struct hmap *b)
+{
+  u32 n = 0;
+
+  for (int i = 3; i >= 0; i--)
+  {
+    if (32*n >= b->size[i])
+      return hmap_max(b);
+
+    u32 *p = b->data[i] + 8*n;
+
+    n = (n << 8) + b256_first_zero(p);
+  }
+
+  return n;
+}
+
+void
+hmap_check(struct hmap *b)
+{
+  for (int i = 0; i < 2; i++)
+  {
+    int max = b->size[i] / 32;
+
+    for (int j = 0; j < max; j++)
+    {
+      int x = b256_and(b->data[i] + 8*j);
+      int y = !!BIT32_TEST(b->data[i+1], j);
+      if (x != y)
+	bug("Inconsistent data on %d:%d (%d vs %d)", i, j, x, y);
+    }
+  }
+}
diff --git a/lib/bitmap.h b/lib/bitmap.h
new file mode 100644
index 00000000..df2945a1
--- /dev/null
+++ b/lib/bitmap.h
@@ -0,0 +1,62 @@
+/*
+ *	BIRD Library -- Bitmaps
+ *
+ *	(c) 2019 Ondrej Zajicek <santiago@crfreenet.org>
+ *	(c) 2019 CZ.NIC z.s.p.o.
+ *
+ *	Can be freely distributed and used under the terms of the GNU GPL.
+ */
+
+#ifndef _BIRD_BITMAP_H_
+#define _BIRD_BITMAP_H_
+
+struct bmap
+{
+  u32 size;
+  u32 *data;
+};
+
+void bmap_init(struct bmap *b, pool *p, uint size);
+void bmap_grow(struct bmap *b, uint need);
+void bmap_free(struct bmap *b);
+
+static inline uint bmap_max(struct bmap *b)
+{ return 8 * b->size; }
+
+static inline int bmap_test(struct bmap *b, uint n)
+{ return (n < bmap_max(b)) && BIT32_TEST(b->data, n); }
+
+static inline void bmap_set(struct bmap *b, uint n)
+{
+  if (n >= bmap_max(b)) bmap_grow(b, n/8 + 1);
+  BIT32_SET(b->data, n);
+}
+
+static inline void bmap_clear(struct bmap *b, uint n)
+{
+  if (n >= bmap_max(b)) return;
+  BIT32_CLR(b->data, n);
+}
+
+
+struct hmap
+{
+  u32 size[4];
+  u32 *data[4];
+  u32 root[8];
+};
+
+static inline uint hmap_max(struct hmap *b)
+{ return 8 * b->size[0]; }
+
+static inline int hmap_test(struct hmap *b, uint n)
+{ return (n < hmap_max(b)) && BIT32_TEST(b->data[0], n); }
+
+void hmap_init(struct hmap *b, pool *p, uint size);
+void hmap_free(struct hmap *b);
+void hmap_set(struct hmap *b, uint n);
+void hmap_clear(struct hmap *b, uint n);
+u32 hmap_first_zero(struct hmap *b);
+void hmap_check(struct hmap *b);
+
+#endif
diff --git a/lib/bitmap_test.c b/lib/bitmap_test.c
new file mode 100644
index 00000000..0595a4d0
--- /dev/null
+++ b/lib/bitmap_test.c
@@ -0,0 +1,186 @@
+/*
+ *	BIRD Library -- Bitmap Tests
+ *
+ *	(c) 2019 Ondrej Zajicek <santiago@crfreenet.org>
+ *	(c) 2019 CZ.NIC z.s.p.o.
+ *
+ *	Can be freely distributed and used under the terms of the GNU GPL.
+ */
+
+#include "test/birdtest.h"
+#include "sysdep/config.h"
+#include "lib/bitmap.h"
+
+#define MAX_NUM (1 << 20)
+#define MAX_SET (1 << 19)
+#define MAX_CLR (1 << 17)
+
+#define STEP_NUM 1000
+#define STEP_SET 1000
+#define STEP_CLR 500
+
+static int
+t_bmap_set_clear_random(void)
+{
+  struct bmap b;
+
+  resource_init();
+  bmap_init(&b, &root_pool, 1024);
+
+  char expected[MAX_NUM] = {};
+  uint i, n;
+
+  for (i = 0; i < MAX_SET; i++)
+  {
+    do n = bt_random() % MAX_NUM;
+    while (expected[n]);
+
+    bmap_set(&b, n);
+    expected[n] = 1;
+  }
+
+  for (i = 0; i < MAX_CLR; i++)
+  {
+    do n = bt_random() % MAX_NUM;
+    while (!expected[n]);
+
+    bmap_clear(&b, n);
+    expected[n] = 0;
+  }
+
+  for (i = 0; i < MAX_NUM; i++)
+    if (bmap_test(&b, i) != expected[i])
+      bt_abort_msg("Bitmap mismatch on %d (should be %d %d)", i, bmap_test(&b, i), expected[i]);
+
+  return 1;
+}
+
+static int
+t_hmap_set_clear_random(void)
+{
+  struct hmap b;
+
+  resource_init();
+  hmap_init(&b, &root_pool, 1024);
+
+  char expected[MAX_NUM] = {};
+  uint i, n;
+
+  for (i = 0; i < MAX_SET; i++)
+  {
+    do n = bt_random() % MAX_NUM;
+    while (expected[n]);
+
+    hmap_set(&b, n);
+    expected[n] = 1;
+  }
+
+  hmap_check(&b);
+
+  for (i = 0; i < MAX_CLR; i++)
+  {
+    do n = bt_random() % MAX_NUM;
+    while (!expected[n]);
+
+    hmap_clear(&b, n);
+    expected[n] = 0;
+  }
+
+  hmap_check(&b);
+
+  for (i = 0; i < MAX_NUM; i++)
+    if (hmap_test(&b, i) != expected[i])
+      bt_abort_msg("Bitmap mismatch on %d (should be %d %d)", i, hmap_test(&b, i), expected[i]);
+
+  for (i = 0; 1; i++)
+  {
+    n = hmap_first_zero(&b);
+    bt_assert(n >= i);
+    bt_assert(n <= MAX_NUM);
+
+    for (; i < n; i++)
+      bt_assert(expected[i]);
+
+    if (n == MAX_NUM)
+      break;
+
+    bt_assert(!expected[i]);
+
+    hmap_set(&b, n);
+  }
+
+  hmap_check(&b);
+
+  return 1;
+}
+
+static int
+t_hmap_set_clear_fill(void)
+{
+  struct hmap b;
+
+  resource_init();
+  hmap_init(&b, &root_pool, 1024);
+
+  char expected[MAX_NUM] = {};
+  uint i, j, n, max = 0;
+
+  for (i = 0; i < STEP_NUM; i++)
+  {
+    uint last = 0;
+    uint step_set = bt_random() % STEP_SET;
+    uint step_clr = bt_random() % STEP_CLR;
+
+    for (j = 0; j < step_set; j++)
+    {
+      n = hmap_first_zero(&b);
+      bt_assert(n > last || !last);
+      bt_assert(n < MAX_NUM);
+
+      if (!last)
+	last = n;
+
+      for (; last < n; last++)
+	bt_assert(expected[last]);
+
+      bt_assert(!expected[n]);
+
+      hmap_set(&b, n);
+      expected[n] = 1;
+      max = MAX(max, n);
+    }
+
+    for (j = 0; j < step_clr; j++)
+    {
+      uint k = 0;
+      do n = bt_random() % max;
+      while (!expected[n] && (k++ < 8));
+
+      if (!expected[n])
+	continue;
+
+      hmap_clear(&b, n);
+      expected[n] = 0;
+    }
+  }
+
+  for (i = 0; i < MAX_NUM; i++)
+    if (hmap_test(&b, i) != expected[i])
+      bt_abort_msg("Bitmap mismatch on %d (should be %d %d)", i, hmap_test(&b, i), expected[i]);
+
+  hmap_check(&b);
+
+  return 1;
+}
+
+int
+main(int argc, char *argv[])
+{
+  bt_init(argc, argv);
+
+  bt_test_suite(t_bmap_set_clear_random, "BMap - random sequence of sets / clears");
+  bt_test_suite(t_hmap_set_clear_random, "HMap - random sequence of sets / clears");
+  bt_test_suite(t_hmap_set_clear_fill, "HMap - linear sets and random clears");
+
+  return bt_exit_value();
+}
diff --git a/lib/bitops.h b/lib/bitops.h
index 39ade388..a4c48a10 100644
--- a/lib/bitops.h
+++ b/lib/bitops.h
@@ -29,6 +29,9 @@ static inline u32 u32_hash(u32 v) { return v * 2902958171u; }
 
 static inline u8 u32_popcount(u32 v) { return __builtin_popcount(v); }
 
+static inline int u32_clz(u32 v) { return __builtin_clz(v); }
+static inline int u32_ctz(u32 v) { return __builtin_ctz(v); }
+
 static inline int uint_is_pow2(uint n) { return n && !(n & (n-1)); }
 
 #endif