diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-14 13:40:54 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-14 13:40:54 +0000 |
commit | 317c0644ccf108aa23ef3fd8358bd66c2840bfc0 (patch) | |
tree | c417b3d25c86b775989cb5ac042f37611b626c8a /deps/jemalloc/test/unit/bitmap.c | |
parent | Initial commit. (diff) | |
download | redis-317c0644ccf108aa23ef3fd8358bd66c2840bfc0.tar.xz redis-317c0644ccf108aa23ef3fd8358bd66c2840bfc0.zip |
Adding upstream version 5:7.2.4.upstream/5%7.2.4
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'deps/jemalloc/test/unit/bitmap.c')
-rw-r--r-- | deps/jemalloc/test/unit/bitmap.c | 343 |
1 files changed, 343 insertions, 0 deletions
diff --git a/deps/jemalloc/test/unit/bitmap.c b/deps/jemalloc/test/unit/bitmap.c new file mode 100644 index 0000000..78e542b --- /dev/null +++ b/deps/jemalloc/test/unit/bitmap.c @@ -0,0 +1,343 @@ +#include "test/jemalloc_test.h" + +#include "test/nbits.h" + +static void +test_bitmap_initializer_body(const bitmap_info_t *binfo, size_t nbits) { + bitmap_info_t binfo_dyn; + bitmap_info_init(&binfo_dyn, nbits); + + expect_zu_eq(bitmap_size(binfo), bitmap_size(&binfo_dyn), + "Unexpected difference between static and dynamic initialization, " + "nbits=%zu", nbits); + expect_zu_eq(binfo->nbits, binfo_dyn.nbits, + "Unexpected difference between static and dynamic initialization, " + "nbits=%zu", nbits); +#ifdef BITMAP_USE_TREE + expect_u_eq(binfo->nlevels, binfo_dyn.nlevels, + "Unexpected difference between static and dynamic initialization, " + "nbits=%zu", nbits); + { + unsigned i; + + for (i = 0; i < binfo->nlevels; i++) { + expect_zu_eq(binfo->levels[i].group_offset, + binfo_dyn.levels[i].group_offset, + "Unexpected difference between static and dynamic " + "initialization, nbits=%zu, level=%u", nbits, i); + } + } +#else + expect_zu_eq(binfo->ngroups, binfo_dyn.ngroups, + "Unexpected difference between static and dynamic initialization"); +#endif +} + +TEST_BEGIN(test_bitmap_initializer) { +#define NB(nbits) { \ + if (nbits <= BITMAP_MAXBITS) { \ + bitmap_info_t binfo = \ + BITMAP_INFO_INITIALIZER(nbits); \ + test_bitmap_initializer_body(&binfo, nbits); \ + } \ + } + NBITS_TAB +#undef NB +} +TEST_END + +static size_t +test_bitmap_size_body(const bitmap_info_t *binfo, size_t nbits, + size_t prev_size) { + size_t size = bitmap_size(binfo); + expect_zu_ge(size, (nbits >> 3), + "Bitmap size is smaller than expected"); + expect_zu_ge(size, prev_size, "Bitmap size is smaller than expected"); + return size; +} + +TEST_BEGIN(test_bitmap_size) { + size_t nbits, prev_size; + + prev_size = 0; + for (nbits = 1; nbits <= BITMAP_MAXBITS; nbits++) { + bitmap_info_t binfo; + bitmap_info_init(&binfo, nbits); + prev_size = test_bitmap_size_body(&binfo, nbits, prev_size); + } +#define NB(nbits) { \ + bitmap_info_t binfo = BITMAP_INFO_INITIALIZER(nbits); \ + prev_size = test_bitmap_size_body(&binfo, nbits, \ + prev_size); \ + } + prev_size = 0; + NBITS_TAB +#undef NB +} +TEST_END + +static void +test_bitmap_init_body(const bitmap_info_t *binfo, size_t nbits) { + size_t i; + bitmap_t *bitmap = (bitmap_t *)malloc(bitmap_size(binfo)); + expect_ptr_not_null(bitmap, "Unexpected malloc() failure"); + + bitmap_init(bitmap, binfo, false); + for (i = 0; i < nbits; i++) { + expect_false(bitmap_get(bitmap, binfo, i), + "Bit should be unset"); + } + + bitmap_init(bitmap, binfo, true); + for (i = 0; i < nbits; i++) { + expect_true(bitmap_get(bitmap, binfo, i), "Bit should be set"); + } + + free(bitmap); +} + +TEST_BEGIN(test_bitmap_init) { + size_t nbits; + + for (nbits = 1; nbits <= BITMAP_MAXBITS; nbits++) { + bitmap_info_t binfo; + bitmap_info_init(&binfo, nbits); + test_bitmap_init_body(&binfo, nbits); + } +#define NB(nbits) { \ + bitmap_info_t binfo = BITMAP_INFO_INITIALIZER(nbits); \ + test_bitmap_init_body(&binfo, nbits); \ + } + NBITS_TAB +#undef NB +} +TEST_END + +static void +test_bitmap_set_body(const bitmap_info_t *binfo, size_t nbits) { + size_t i; + bitmap_t *bitmap = (bitmap_t *)malloc(bitmap_size(binfo)); + expect_ptr_not_null(bitmap, "Unexpected malloc() failure"); + bitmap_init(bitmap, binfo, false); + + for (i = 0; i < nbits; i++) { + bitmap_set(bitmap, binfo, i); + } + expect_true(bitmap_full(bitmap, binfo), "All bits should be set"); + free(bitmap); +} + +TEST_BEGIN(test_bitmap_set) { + size_t nbits; + + for (nbits = 1; nbits <= BITMAP_MAXBITS; nbits++) { + bitmap_info_t binfo; + bitmap_info_init(&binfo, nbits); + test_bitmap_set_body(&binfo, nbits); + } +#define NB(nbits) { \ + bitmap_info_t binfo = BITMAP_INFO_INITIALIZER(nbits); \ + test_bitmap_set_body(&binfo, nbits); \ + } + NBITS_TAB +#undef NB +} +TEST_END + +static void +test_bitmap_unset_body(const bitmap_info_t *binfo, size_t nbits) { + size_t i; + bitmap_t *bitmap = (bitmap_t *)malloc(bitmap_size(binfo)); + expect_ptr_not_null(bitmap, "Unexpected malloc() failure"); + bitmap_init(bitmap, binfo, false); + + for (i = 0; i < nbits; i++) { + bitmap_set(bitmap, binfo, i); + } + expect_true(bitmap_full(bitmap, binfo), "All bits should be set"); + for (i = 0; i < nbits; i++) { + bitmap_unset(bitmap, binfo, i); + } + for (i = 0; i < nbits; i++) { + bitmap_set(bitmap, binfo, i); + } + expect_true(bitmap_full(bitmap, binfo), "All bits should be set"); + free(bitmap); +} + +TEST_BEGIN(test_bitmap_unset) { + size_t nbits; + + for (nbits = 1; nbits <= BITMAP_MAXBITS; nbits++) { + bitmap_info_t binfo; + bitmap_info_init(&binfo, nbits); + test_bitmap_unset_body(&binfo, nbits); + } +#define NB(nbits) { \ + bitmap_info_t binfo = BITMAP_INFO_INITIALIZER(nbits); \ + test_bitmap_unset_body(&binfo, nbits); \ + } + NBITS_TAB +#undef NB +} +TEST_END + +static void +test_bitmap_xfu_body(const bitmap_info_t *binfo, size_t nbits) { + bitmap_t *bitmap = (bitmap_t *)malloc(bitmap_size(binfo)); + expect_ptr_not_null(bitmap, "Unexpected malloc() failure"); + bitmap_init(bitmap, binfo, false); + + /* Iteratively set bits starting at the beginning. */ + for (size_t i = 0; i < nbits; i++) { + expect_zu_eq(bitmap_ffu(bitmap, binfo, 0), i, + "First unset bit should be just after previous first unset " + "bit"); + expect_zu_eq(bitmap_ffu(bitmap, binfo, (i > 0) ? i-1 : i), i, + "First unset bit should be just after previous first unset " + "bit"); + expect_zu_eq(bitmap_ffu(bitmap, binfo, i), i, + "First unset bit should be just after previous first unset " + "bit"); + expect_zu_eq(bitmap_sfu(bitmap, binfo), i, + "First unset bit should be just after previous first unset " + "bit"); + } + expect_true(bitmap_full(bitmap, binfo), "All bits should be set"); + + /* + * Iteratively unset bits starting at the end, and verify that + * bitmap_sfu() reaches the unset bits. + */ + for (size_t i = nbits - 1; i < nbits; i--) { /* (nbits..0] */ + bitmap_unset(bitmap, binfo, i); + expect_zu_eq(bitmap_ffu(bitmap, binfo, 0), i, + "First unset bit should the bit previously unset"); + expect_zu_eq(bitmap_ffu(bitmap, binfo, (i > 0) ? i-1 : i), i, + "First unset bit should the bit previously unset"); + expect_zu_eq(bitmap_ffu(bitmap, binfo, i), i, + "First unset bit should the bit previously unset"); + expect_zu_eq(bitmap_sfu(bitmap, binfo), i, + "First unset bit should the bit previously unset"); + bitmap_unset(bitmap, binfo, i); + } + expect_false(bitmap_get(bitmap, binfo, 0), "Bit should be unset"); + + /* + * Iteratively set bits starting at the beginning, and verify that + * bitmap_sfu() looks past them. + */ + for (size_t i = 1; i < nbits; i++) { + bitmap_set(bitmap, binfo, i - 1); + expect_zu_eq(bitmap_ffu(bitmap, binfo, 0), i, + "First unset bit should be just after the bit previously " + "set"); + expect_zu_eq(bitmap_ffu(bitmap, binfo, (i > 0) ? i-1 : i), i, + "First unset bit should be just after the bit previously " + "set"); + expect_zu_eq(bitmap_ffu(bitmap, binfo, i), i, + "First unset bit should be just after the bit previously " + "set"); + expect_zu_eq(bitmap_sfu(bitmap, binfo), i, + "First unset bit should be just after the bit previously " + "set"); + bitmap_unset(bitmap, binfo, i); + } + expect_zu_eq(bitmap_ffu(bitmap, binfo, 0), nbits - 1, + "First unset bit should be the last bit"); + expect_zu_eq(bitmap_ffu(bitmap, binfo, (nbits > 1) ? nbits-2 : nbits-1), + nbits - 1, "First unset bit should be the last bit"); + expect_zu_eq(bitmap_ffu(bitmap, binfo, nbits - 1), nbits - 1, + "First unset bit should be the last bit"); + expect_zu_eq(bitmap_sfu(bitmap, binfo), nbits - 1, + "First unset bit should be the last bit"); + expect_true(bitmap_full(bitmap, binfo), "All bits should be set"); + + /* + * Bubble a "usu" pattern through the bitmap and verify that + * bitmap_ffu() finds the correct bit for all five min_bit cases. + */ + if (nbits >= 3) { + for (size_t i = 0; i < nbits-2; i++) { + bitmap_unset(bitmap, binfo, i); + bitmap_unset(bitmap, binfo, i+2); + if (i > 0) { + expect_zu_eq(bitmap_ffu(bitmap, binfo, i-1), i, + "Unexpected first unset bit"); + } + expect_zu_eq(bitmap_ffu(bitmap, binfo, i), i, + "Unexpected first unset bit"); + expect_zu_eq(bitmap_ffu(bitmap, binfo, i+1), i+2, + "Unexpected first unset bit"); + expect_zu_eq(bitmap_ffu(bitmap, binfo, i+2), i+2, + "Unexpected first unset bit"); + if (i + 3 < nbits) { + expect_zu_eq(bitmap_ffu(bitmap, binfo, i+3), + nbits, "Unexpected first unset bit"); + } + expect_zu_eq(bitmap_sfu(bitmap, binfo), i, + "Unexpected first unset bit"); + expect_zu_eq(bitmap_sfu(bitmap, binfo), i+2, + "Unexpected first unset bit"); + } + } + + /* + * Unset the last bit, bubble another unset bit through the bitmap, and + * verify that bitmap_ffu() finds the correct bit for all four min_bit + * cases. + */ + if (nbits >= 3) { + bitmap_unset(bitmap, binfo, nbits-1); + for (size_t i = 0; i < nbits-1; i++) { + bitmap_unset(bitmap, binfo, i); + if (i > 0) { + expect_zu_eq(bitmap_ffu(bitmap, binfo, i-1), i, + "Unexpected first unset bit"); + } + expect_zu_eq(bitmap_ffu(bitmap, binfo, i), i, + "Unexpected first unset bit"); + expect_zu_eq(bitmap_ffu(bitmap, binfo, i+1), nbits-1, + "Unexpected first unset bit"); + expect_zu_eq(bitmap_ffu(bitmap, binfo, nbits-1), + nbits-1, "Unexpected first unset bit"); + + expect_zu_eq(bitmap_sfu(bitmap, binfo), i, + "Unexpected first unset bit"); + } + expect_zu_eq(bitmap_sfu(bitmap, binfo), nbits-1, + "Unexpected first unset bit"); + } + + free(bitmap); +} + +TEST_BEGIN(test_bitmap_xfu) { + size_t nbits, nbits_max; + + /* The test is O(n^2); large page sizes may slow down too much. */ + nbits_max = BITMAP_MAXBITS > 512 ? 512 : BITMAP_MAXBITS; + for (nbits = 1; nbits <= nbits_max; nbits++) { + bitmap_info_t binfo; + bitmap_info_init(&binfo, nbits); + test_bitmap_xfu_body(&binfo, nbits); + } +#define NB(nbits) { \ + bitmap_info_t binfo = BITMAP_INFO_INITIALIZER(nbits); \ + test_bitmap_xfu_body(&binfo, nbits); \ + } + NBITS_TAB +#undef NB +} +TEST_END + +int +main(void) { + return test( + test_bitmap_initializer, + test_bitmap_size, + test_bitmap_init, + test_bitmap_set, + test_bitmap_unset, + test_bitmap_xfu); +} |