-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)
--- /dev/null
+/*
+ * 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);
+ }
+ }
+}
--- /dev/null
+/*
+ * 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
--- /dev/null
+/*
+ * 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();
+}
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
projects / thirdparty / bird.git / commitdiff
