diff options
Diffstat (limited to 'deps/jemalloc/test/unit/bitmap.c')
| -rw-r--r-- | deps/jemalloc/test/unit/bitmap.c | 194 |
1 files changed, 53 insertions, 141 deletions
diff --git a/deps/jemalloc/test/unit/bitmap.c b/deps/jemalloc/test/unit/bitmap.c index cafb2039e..78e542b67 100644 --- a/deps/jemalloc/test/unit/bitmap.c +++ b/deps/jemalloc/test/unit/bitmap.c @@ -1,124 +1,34 @@ #include "test/jemalloc_test.h" -#define NBITS_TAB \ - NB( 1) \ - NB( 2) \ - NB( 3) \ - NB( 4) \ - NB( 5) \ - NB( 6) \ - NB( 7) \ - NB( 8) \ - NB( 9) \ - NB(10) \ - NB(11) \ - NB(12) \ - NB(13) \ - NB(14) \ - NB(15) \ - NB(16) \ - NB(17) \ - NB(18) \ - NB(19) \ - NB(20) \ - NB(21) \ - NB(22) \ - NB(23) \ - NB(24) \ - NB(25) \ - NB(26) \ - NB(27) \ - NB(28) \ - NB(29) \ - NB(30) \ - NB(31) \ - NB(32) \ - \ - NB(33) \ - NB(34) \ - NB(35) \ - NB(36) \ - NB(37) \ - NB(38) \ - NB(39) \ - NB(40) \ - NB(41) \ - NB(42) \ - NB(43) \ - NB(44) \ - NB(45) \ - NB(46) \ - NB(47) \ - NB(48) \ - NB(49) \ - NB(50) \ - NB(51) \ - NB(52) \ - NB(53) \ - NB(54) \ - NB(55) \ - NB(56) \ - NB(57) \ - NB(58) \ - NB(59) \ - NB(60) \ - NB(61) \ - NB(62) \ - NB(63) \ - NB(64) \ - NB(65) \ - \ - NB(126) \ - NB(127) \ - NB(128) \ - NB(129) \ - NB(130) \ - \ - NB(254) \ - NB(255) \ - NB(256) \ - NB(257) \ - NB(258) \ - \ - NB(510) \ - NB(511) \ - NB(512) \ - NB(513) \ - NB(514) \ - \ - NB(1024) \ - NB(2048) \ - NB(4096) \ - NB(8192) \ - NB(16384) \ +#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); - assert_zu_eq(bitmap_size(binfo), bitmap_size(&binfo_dyn), + expect_zu_eq(bitmap_size(binfo), bitmap_size(&binfo_dyn), "Unexpected difference between static and dynamic initialization, " "nbits=%zu", nbits); - assert_zu_eq(binfo->nbits, binfo_dyn.nbits, + expect_zu_eq(binfo->nbits, binfo_dyn.nbits, "Unexpected difference between static and dynamic initialization, " "nbits=%zu", nbits); #ifdef BITMAP_USE_TREE - assert_u_eq(binfo->nlevels, binfo_dyn.nlevels, + 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++) { - assert_zu_eq(binfo->levels[i].group_offset, + 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 - assert_zu_eq(binfo->ngroups, binfo_dyn.ngroups, + expect_zu_eq(binfo->ngroups, binfo_dyn.ngroups, "Unexpected difference between static and dynamic initialization"); #endif } @@ -140,9 +50,9 @@ 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); - assert_zu_ge(size, (nbits >> 3), + expect_zu_ge(size, (nbits >> 3), "Bitmap size is smaller than expected"); - assert_zu_ge(size, prev_size, "Bitmap size is smaller than expected"); + expect_zu_ge(size, prev_size, "Bitmap size is smaller than expected"); return size; } @@ -170,17 +80,17 @@ 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)); - assert_ptr_not_null(bitmap, "Unexpected malloc() failure"); + expect_ptr_not_null(bitmap, "Unexpected malloc() failure"); bitmap_init(bitmap, binfo, false); for (i = 0; i < nbits; i++) { - assert_false(bitmap_get(bitmap, binfo, i), + expect_false(bitmap_get(bitmap, binfo, i), "Bit should be unset"); } bitmap_init(bitmap, binfo, true); for (i = 0; i < nbits; i++) { - assert_true(bitmap_get(bitmap, binfo, i), "Bit should be set"); + expect_true(bitmap_get(bitmap, binfo, i), "Bit should be set"); } free(bitmap); @@ -207,13 +117,13 @@ 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)); - assert_ptr_not_null(bitmap, "Unexpected malloc() failure"); + expect_ptr_not_null(bitmap, "Unexpected malloc() failure"); bitmap_init(bitmap, binfo, false); for (i = 0; i < nbits; i++) { bitmap_set(bitmap, binfo, i); } - assert_true(bitmap_full(bitmap, binfo), "All bits should be set"); + expect_true(bitmap_full(bitmap, binfo), "All bits should be set"); free(bitmap); } @@ -238,20 +148,20 @@ 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)); - assert_ptr_not_null(bitmap, "Unexpected malloc() failure"); + expect_ptr_not_null(bitmap, "Unexpected malloc() failure"); bitmap_init(bitmap, binfo, false); for (i = 0; i < nbits; i++) { bitmap_set(bitmap, binfo, i); } - assert_true(bitmap_full(bitmap, binfo), "All bits should be set"); + 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); } - assert_true(bitmap_full(bitmap, binfo), "All bits should be set"); + expect_true(bitmap_full(bitmap, binfo), "All bits should be set"); free(bitmap); } @@ -275,25 +185,25 @@ 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)); - assert_ptr_not_null(bitmap, "Unexpected malloc() failure"); + 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++) { - assert_zu_eq(bitmap_ffu(bitmap, binfo, 0), i, + expect_zu_eq(bitmap_ffu(bitmap, binfo, 0), i, "First unset bit should be just after previous first unset " "bit"); - assert_zu_eq(bitmap_ffu(bitmap, binfo, (i > 0) ? i-1 : i), i, + expect_zu_eq(bitmap_ffu(bitmap, binfo, (i > 0) ? i-1 : i), i, "First unset bit should be just after previous first unset " "bit"); - assert_zu_eq(bitmap_ffu(bitmap, binfo, i), i, + expect_zu_eq(bitmap_ffu(bitmap, binfo, i), i, "First unset bit should be just after previous first unset " "bit"); - assert_zu_eq(bitmap_sfu(bitmap, binfo), i, + expect_zu_eq(bitmap_sfu(bitmap, binfo), i, "First unset bit should be just after previous first unset " "bit"); } - assert_true(bitmap_full(bitmap, binfo), "All bits should be set"); + expect_true(bitmap_full(bitmap, binfo), "All bits should be set"); /* * Iteratively unset bits starting at the end, and verify that @@ -301,17 +211,17 @@ test_bitmap_xfu_body(const bitmap_info_t *binfo, size_t nbits) { */ for (size_t i = nbits - 1; i < nbits; i--) { /* (nbits..0] */ bitmap_unset(bitmap, binfo, i); - assert_zu_eq(bitmap_ffu(bitmap, binfo, 0), i, + expect_zu_eq(bitmap_ffu(bitmap, binfo, 0), i, "First unset bit should the bit previously unset"); - assert_zu_eq(bitmap_ffu(bitmap, binfo, (i > 0) ? i-1 : i), i, + expect_zu_eq(bitmap_ffu(bitmap, binfo, (i > 0) ? i-1 : i), i, "First unset bit should the bit previously unset"); - assert_zu_eq(bitmap_ffu(bitmap, binfo, i), i, + expect_zu_eq(bitmap_ffu(bitmap, binfo, i), i, "First unset bit should the bit previously unset"); - assert_zu_eq(bitmap_sfu(bitmap, binfo), i, + expect_zu_eq(bitmap_sfu(bitmap, binfo), i, "First unset bit should the bit previously unset"); bitmap_unset(bitmap, binfo, i); } - assert_false(bitmap_get(bitmap, binfo, 0), "Bit should be unset"); + expect_false(bitmap_get(bitmap, binfo, 0), "Bit should be unset"); /* * Iteratively set bits starting at the beginning, and verify that @@ -319,29 +229,29 @@ test_bitmap_xfu_body(const bitmap_info_t *binfo, size_t nbits) { */ for (size_t i = 1; i < nbits; i++) { bitmap_set(bitmap, binfo, i - 1); - assert_zu_eq(bitmap_ffu(bitmap, binfo, 0), i, + expect_zu_eq(bitmap_ffu(bitmap, binfo, 0), i, "First unset bit should be just after the bit previously " "set"); - assert_zu_eq(bitmap_ffu(bitmap, binfo, (i > 0) ? i-1 : i), i, + expect_zu_eq(bitmap_ffu(bitmap, binfo, (i > 0) ? i-1 : i), i, "First unset bit should be just after the bit previously " "set"); - assert_zu_eq(bitmap_ffu(bitmap, binfo, i), i, + expect_zu_eq(bitmap_ffu(bitmap, binfo, i), i, "First unset bit should be just after the bit previously " "set"); - assert_zu_eq(bitmap_sfu(bitmap, binfo), i, + expect_zu_eq(bitmap_sfu(bitmap, binfo), i, "First unset bit should be just after the bit previously " "set"); bitmap_unset(bitmap, binfo, i); } - assert_zu_eq(bitmap_ffu(bitmap, binfo, 0), nbits - 1, + expect_zu_eq(bitmap_ffu(bitmap, binfo, 0), nbits - 1, "First unset bit should be the last bit"); - assert_zu_eq(bitmap_ffu(bitmap, binfo, (nbits > 1) ? nbits-2 : nbits-1), + expect_zu_eq(bitmap_ffu(bitmap, binfo, (nbits > 1) ? nbits-2 : nbits-1), nbits - 1, "First unset bit should be the last bit"); - assert_zu_eq(bitmap_ffu(bitmap, binfo, nbits - 1), nbits - 1, + expect_zu_eq(bitmap_ffu(bitmap, binfo, nbits - 1), nbits - 1, "First unset bit should be the last bit"); - assert_zu_eq(bitmap_sfu(bitmap, binfo), nbits - 1, + expect_zu_eq(bitmap_sfu(bitmap, binfo), nbits - 1, "First unset bit should be the last bit"); - assert_true(bitmap_full(bitmap, binfo), "All bits should be set"); + expect_true(bitmap_full(bitmap, binfo), "All bits should be set"); /* * Bubble a "usu" pattern through the bitmap and verify that @@ -352,22 +262,22 @@ test_bitmap_xfu_body(const bitmap_info_t *binfo, size_t nbits) { bitmap_unset(bitmap, binfo, i); bitmap_unset(bitmap, binfo, i+2); if (i > 0) { - assert_zu_eq(bitmap_ffu(bitmap, binfo, i-1), i, + expect_zu_eq(bitmap_ffu(bitmap, binfo, i-1), i, "Unexpected first unset bit"); } - assert_zu_eq(bitmap_ffu(bitmap, binfo, i), i, + expect_zu_eq(bitmap_ffu(bitmap, binfo, i), i, "Unexpected first unset bit"); - assert_zu_eq(bitmap_ffu(bitmap, binfo, i+1), i+2, + expect_zu_eq(bitmap_ffu(bitmap, binfo, i+1), i+2, "Unexpected first unset bit"); - assert_zu_eq(bitmap_ffu(bitmap, binfo, i+2), i+2, + expect_zu_eq(bitmap_ffu(bitmap, binfo, i+2), i+2, "Unexpected first unset bit"); if (i + 3 < nbits) { - assert_zu_eq(bitmap_ffu(bitmap, binfo, i+3), + expect_zu_eq(bitmap_ffu(bitmap, binfo, i+3), nbits, "Unexpected first unset bit"); } - assert_zu_eq(bitmap_sfu(bitmap, binfo), i, + expect_zu_eq(bitmap_sfu(bitmap, binfo), i, "Unexpected first unset bit"); - assert_zu_eq(bitmap_sfu(bitmap, binfo), i+2, + expect_zu_eq(bitmap_sfu(bitmap, binfo), i+2, "Unexpected first unset bit"); } } @@ -382,20 +292,20 @@ test_bitmap_xfu_body(const bitmap_info_t *binfo, size_t nbits) { for (size_t i = 0; i < nbits-1; i++) { bitmap_unset(bitmap, binfo, i); if (i > 0) { - assert_zu_eq(bitmap_ffu(bitmap, binfo, i-1), i, + expect_zu_eq(bitmap_ffu(bitmap, binfo, i-1), i, "Unexpected first unset bit"); } - assert_zu_eq(bitmap_ffu(bitmap, binfo, i), i, + expect_zu_eq(bitmap_ffu(bitmap, binfo, i), i, "Unexpected first unset bit"); - assert_zu_eq(bitmap_ffu(bitmap, binfo, i+1), nbits-1, + expect_zu_eq(bitmap_ffu(bitmap, binfo, i+1), nbits-1, "Unexpected first unset bit"); - assert_zu_eq(bitmap_ffu(bitmap, binfo, nbits-1), + expect_zu_eq(bitmap_ffu(bitmap, binfo, nbits-1), nbits-1, "Unexpected first unset bit"); - assert_zu_eq(bitmap_sfu(bitmap, binfo), i, + expect_zu_eq(bitmap_sfu(bitmap, binfo), i, "Unexpected first unset bit"); } - assert_zu_eq(bitmap_sfu(bitmap, binfo), nbits-1, + expect_zu_eq(bitmap_sfu(bitmap, binfo), nbits-1, "Unexpected first unset bit"); } @@ -403,9 +313,11 @@ test_bitmap_xfu_body(const bitmap_info_t *binfo, size_t nbits) { } TEST_BEGIN(test_bitmap_xfu) { - size_t nbits; + size_t nbits, nbits_max; - for (nbits = 1; nbits <= BITMAP_MAXBITS; nbits++) { + /* 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); |