diff options
| -rw-r--r-- | lib/Makefile | 4 | ||||
| -rw-r--r-- | lib/bitmap.c | 190 | ||||
| -rw-r--r-- | lib/bitmap.h | 62 | ||||
| -rw-r--r-- | lib/bitmap_test.c | 186 | ||||
| -rw-r--r-- | lib/bitops.h | 3 |
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 |