1#include "test/jemalloc_test.h" 2 3#define NBITS_TAB \ 4 NB( 1) \ 5 NB( 2) \ 6 NB( 3) \ 7 NB( 4) \ 8 NB( 5) \ 9 NB( 6) \ 10 NB( 7) \ 11 NB( 8) \ 12 NB( 9) \ 13 NB(10) \ 14 NB(11) \ 15 NB(12) \ 16 NB(13) \ 17 NB(14) \ 18 NB(15) \ 19 NB(16) \ 20 NB(17) \ 21 NB(18) \ 22 NB(19) \ 23 NB(20) \ 24 NB(21) \ 25 NB(22) \ 26 NB(23) \ 27 NB(24) \ 28 NB(25) \ 29 NB(26) \ 30 NB(27) \ 31 NB(28) \ 32 NB(29) \ 33 NB(30) \ 34 NB(31) \ 35 NB(32) \ 36 \ 37 NB(33) \ 38 NB(34) \ 39 NB(35) \ 40 NB(36) \ 41 NB(37) \ 42 NB(38) \ 43 NB(39) \ 44 NB(40) \ 45 NB(41) \ 46 NB(42) \ 47 NB(43) \ 48 NB(44) \ 49 NB(45) \ 50 NB(46) \ 51 NB(47) \ 52 NB(48) \ 53 NB(49) \ 54 NB(50) \ 55 NB(51) \ 56 NB(52) \ 57 NB(53) \ 58 NB(54) \ 59 NB(55) \ 60 NB(56) \ 61 NB(57) \ 62 NB(58) \ 63 NB(59) \ 64 NB(60) \ 65 NB(61) \ 66 NB(62) \ 67 NB(63) \ 68 NB(64) \ 69 NB(65) \ 70 \ 71 NB(126) \ 72 NB(127) \ 73 NB(128) \ 74 NB(129) \ 75 NB(130) \ 76 \ 77 NB(254) \ 78 NB(255) \ 79 NB(256) \ 80 NB(257) \ 81 NB(258) \ 82 \ 83 NB(510) \ 84 NB(511) \ 85 NB(512) \ 86 NB(513) \ 87 NB(514) \ 88 \ 89 NB(1024) \ 90 NB(2048) \ 91 NB(4096) \ 92 NB(8192) \ 93 NB(16384) \ 94 95static void 96test_bitmap_initializer_body(const bitmap_info_t *binfo, size_t nbits) 97{ 98 bitmap_info_t binfo_dyn; 99 bitmap_info_init(&binfo_dyn, nbits); 100 101 assert_zu_eq(bitmap_size(binfo), bitmap_size(&binfo_dyn), 102 "Unexpected difference between static and dynamic initialization, " 103 "nbits=%zu", nbits); 104 assert_zu_eq(binfo->nbits, binfo_dyn.nbits, 105 "Unexpected difference between static and dynamic initialization, " 106 "nbits=%zu", nbits); 107#ifdef BITMAP_USE_TREE 108 assert_u_eq(binfo->nlevels, binfo_dyn.nlevels, 109 "Unexpected difference between static and dynamic initialization, " 110 "nbits=%zu", nbits); 111 { 112 unsigned i; 113 114 for (i = 0; i < binfo->nlevels; i++) { 115 assert_zu_eq(binfo->levels[i].group_offset, 116 binfo_dyn.levels[i].group_offset, 117 "Unexpected difference between static and dynamic " 118 "initialization, nbits=%zu, level=%u", nbits, i); 119 } 120 } 121#else 122 assert_zu_eq(binfo->ngroups, binfo_dyn.ngroups, 123 "Unexpected difference between static and dynamic initialization"); 124#endif 125} 126 127TEST_BEGIN(test_bitmap_initializer) 128{ 129#define NB(nbits) { \ 130 if (nbits <= BITMAP_MAXBITS) { \ 131 bitmap_info_t binfo = \ 132 BITMAP_INFO_INITIALIZER(nbits); \ 133 test_bitmap_initializer_body(&binfo, nbits); \ 134 } \ 135 } 136 NBITS_TAB 137#undef NB 138} 139TEST_END 140 141static size_t 142test_bitmap_size_body(const bitmap_info_t *binfo, size_t nbits, 143 size_t prev_size) 144{ 145 size_t size = bitmap_size(binfo); 146 assert_zu_ge(size, (nbits >> 3), 147 "Bitmap size is smaller than expected"); 148 assert_zu_ge(size, prev_size, "Bitmap size is smaller than expected"); 149 return (size); 150} 151 152TEST_BEGIN(test_bitmap_size) 153{ 154 size_t nbits, prev_size; 155 156 prev_size = 0; 157 for (nbits = 1; nbits <= BITMAP_MAXBITS; nbits++) { 158 bitmap_info_t binfo; 159 bitmap_info_init(&binfo, nbits); 160 prev_size = test_bitmap_size_body(&binfo, nbits, prev_size); 161 } 162#define NB(nbits) { \ 163 bitmap_info_t binfo = BITMAP_INFO_INITIALIZER(nbits); \ 164 prev_size = test_bitmap_size_body(&binfo, nbits, \ 165 prev_size); \ 166 } 167 prev_size = 0; 168 NBITS_TAB 169#undef NB 170} 171TEST_END 172 173static void 174test_bitmap_init_body(const bitmap_info_t *binfo, size_t nbits) 175{ 176 size_t i; 177 bitmap_t *bitmap = (bitmap_t *)malloc(bitmap_size(binfo)); 178 assert_ptr_not_null(bitmap, "Unexpected malloc() failure"); 179 bitmap_init(bitmap, binfo); 180 181 for (i = 0; i < nbits; i++) { 182 assert_false(bitmap_get(bitmap, binfo, i), 183 "Bit should be unset"); 184 } 185 free(bitmap); 186} 187 188TEST_BEGIN(test_bitmap_init) 189{ 190 size_t nbits; 191 192 for (nbits = 1; nbits <= BITMAP_MAXBITS; nbits++) { 193 bitmap_info_t binfo; 194 bitmap_info_init(&binfo, nbits); 195 test_bitmap_init_body(&binfo, nbits); 196 } 197#define NB(nbits) { \ 198 bitmap_info_t binfo = BITMAP_INFO_INITIALIZER(nbits); \ 199 test_bitmap_init_body(&binfo, nbits); \ 200 } 201 NBITS_TAB 202#undef NB 203} 204TEST_END 205 206static void 207test_bitmap_set_body(const bitmap_info_t *binfo, size_t nbits) 208{ 209 size_t i; 210 bitmap_t *bitmap = (bitmap_t *)malloc(bitmap_size(binfo)); 211 assert_ptr_not_null(bitmap, "Unexpected malloc() failure"); 212 bitmap_init(bitmap, binfo); 213 214 for (i = 0; i < nbits; i++) 215 bitmap_set(bitmap, binfo, i); 216 assert_true(bitmap_full(bitmap, binfo), "All bits should be set"); 217 free(bitmap); 218} 219 220TEST_BEGIN(test_bitmap_set) 221{ 222 size_t nbits; 223 224 for (nbits = 1; nbits <= BITMAP_MAXBITS; nbits++) { 225 bitmap_info_t binfo; 226 bitmap_info_init(&binfo, nbits); 227 test_bitmap_set_body(&binfo, nbits); 228 } 229#define NB(nbits) { \ 230 bitmap_info_t binfo = BITMAP_INFO_INITIALIZER(nbits); \ 231 test_bitmap_set_body(&binfo, nbits); \ 232 } 233 NBITS_TAB 234#undef NB 235} 236TEST_END 237 238static void 239test_bitmap_unset_body(const bitmap_info_t *binfo, size_t nbits) 240{ 241 size_t i; 242 bitmap_t *bitmap = (bitmap_t *)malloc(bitmap_size(binfo)); 243 assert_ptr_not_null(bitmap, "Unexpected malloc() failure"); 244 bitmap_init(bitmap, binfo); 245 246 for (i = 0; i < nbits; i++) 247 bitmap_set(bitmap, binfo, i); 248 assert_true(bitmap_full(bitmap, binfo), "All bits should be set"); 249 for (i = 0; i < nbits; i++) 250 bitmap_unset(bitmap, binfo, i); 251 for (i = 0; i < nbits; i++) 252 bitmap_set(bitmap, binfo, i); 253 assert_true(bitmap_full(bitmap, binfo), "All bits should be set"); 254 free(bitmap); 255} 256 257TEST_BEGIN(test_bitmap_unset) 258{ 259 size_t nbits; 260 261 for (nbits = 1; nbits <= BITMAP_MAXBITS; nbits++) { 262 bitmap_info_t binfo; 263 bitmap_info_init(&binfo, nbits); 264 test_bitmap_unset_body(&binfo, nbits); 265 } 266#define NB(nbits) { \ 267 bitmap_info_t binfo = BITMAP_INFO_INITIALIZER(nbits); \ 268 test_bitmap_unset_body(&binfo, nbits); \ 269 } 270 NBITS_TAB 271#undef NB 272} 273TEST_END 274 275static void 276test_bitmap_sfu_body(const bitmap_info_t *binfo, size_t nbits) 277{ 278 size_t i; 279 bitmap_t *bitmap = (bitmap_t *)malloc(bitmap_size(binfo)); 280 assert_ptr_not_null(bitmap, "Unexpected malloc() failure"); 281 bitmap_init(bitmap, binfo); 282 283 /* Iteratively set bits starting at the beginning. */ 284 for (i = 0; i < nbits; i++) { 285 assert_zd_eq(bitmap_sfu(bitmap, binfo), i, 286 "First unset bit should be just after previous first unset " 287 "bit"); 288 } 289 assert_true(bitmap_full(bitmap, binfo), "All bits should be set"); 290 291 /* 292 * Iteratively unset bits starting at the end, and verify that 293 * bitmap_sfu() reaches the unset bits. 294 */ 295 for (i = nbits - 1; i < nbits; i--) { /* (nbits..0] */ 296 bitmap_unset(bitmap, binfo, i); 297 assert_zd_eq(bitmap_sfu(bitmap, binfo), i, 298 "First unset bit should the bit previously unset"); 299 bitmap_unset(bitmap, binfo, i); 300 } 301 assert_false(bitmap_get(bitmap, binfo, 0), "Bit should be unset"); 302 303 /* 304 * Iteratively set bits starting at the beginning, and verify that 305 * bitmap_sfu() looks past them. 306 */ 307 for (i = 1; i < nbits; i++) { 308 bitmap_set(bitmap, binfo, i - 1); 309 assert_zd_eq(bitmap_sfu(bitmap, binfo), i, 310 "First unset bit should be just after the bit previously " 311 "set"); 312 bitmap_unset(bitmap, binfo, i); 313 } 314 assert_zd_eq(bitmap_sfu(bitmap, binfo), nbits - 1, 315 "First unset bit should be the last bit"); 316 assert_true(bitmap_full(bitmap, binfo), "All bits should be set"); 317 free(bitmap); 318} 319 320TEST_BEGIN(test_bitmap_sfu) 321{ 322 size_t nbits; 323 324 for (nbits = 1; nbits <= BITMAP_MAXBITS; nbits++) { 325 bitmap_info_t binfo; 326 bitmap_info_init(&binfo, nbits); 327 test_bitmap_sfu_body(&binfo, nbits); 328 } 329#define NB(nbits) { \ 330 bitmap_info_t binfo = BITMAP_INFO_INITIALIZER(nbits); \ 331 test_bitmap_sfu_body(&binfo, nbits); \ 332 } 333 NBITS_TAB 334#undef NB 335} 336TEST_END 337 338int 339main(void) 340{ 341 return (test( 342 test_bitmap_initializer, 343 test_bitmap_size, 344 test_bitmap_init, 345 test_bitmap_set, 346 test_bitmap_unset, 347 test_bitmap_sfu)); 348} 349