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 bitmap_info_t binfo_dyn; 98 bitmap_info_init(&binfo_dyn, nbits); 99 100 assert_zu_eq(bitmap_size(binfo), bitmap_size(&binfo_dyn), 101 "Unexpected difference between static and dynamic initialization, " 102 "nbits=%zu", nbits); 103 assert_zu_eq(binfo->nbits, binfo_dyn.nbits, 104 "Unexpected difference between static and dynamic initialization, " 105 "nbits=%zu", nbits); 106#ifdef BITMAP_USE_TREE 107 assert_u_eq(binfo->nlevels, binfo_dyn.nlevels, 108 "Unexpected difference between static and dynamic initialization, " 109 "nbits=%zu", nbits); 110 { 111 unsigned i; 112 113 for (i = 0; i < binfo->nlevels; i++) { 114 assert_zu_eq(binfo->levels[i].group_offset, 115 binfo_dyn.levels[i].group_offset, 116 "Unexpected difference between static and dynamic " 117 "initialization, nbits=%zu, level=%u", nbits, i); 118 } 119 } 120#else 121 assert_zu_eq(binfo->ngroups, binfo_dyn.ngroups, 122 "Unexpected difference between static and dynamic initialization"); 123#endif 124} 125 126TEST_BEGIN(test_bitmap_initializer) { 127#define NB(nbits) { \ 128 if (nbits <= BITMAP_MAXBITS) { \ 129 bitmap_info_t binfo = \ 130 BITMAP_INFO_INITIALIZER(nbits); \ 131 test_bitmap_initializer_body(&binfo, nbits); \ 132 } \ 133 } 134 NBITS_TAB 135#undef NB 136} 137TEST_END 138 139static size_t 140test_bitmap_size_body(const bitmap_info_t *binfo, size_t nbits, 141 size_t prev_size) { 142 size_t size = bitmap_size(binfo); 143 assert_zu_ge(size, (nbits >> 3), 144 "Bitmap size is smaller than expected"); 145 assert_zu_ge(size, prev_size, "Bitmap size is smaller than expected"); 146 return size; 147} 148 149TEST_BEGIN(test_bitmap_size) { 150 size_t nbits, prev_size; 151 152 prev_size = 0; 153 for (nbits = 1; nbits <= BITMAP_MAXBITS; nbits++) { 154 bitmap_info_t binfo; 155 bitmap_info_init(&binfo, nbits); 156 prev_size = test_bitmap_size_body(&binfo, nbits, prev_size); 157 } 158#define NB(nbits) { \ 159 bitmap_info_t binfo = BITMAP_INFO_INITIALIZER(nbits); \ 160 prev_size = test_bitmap_size_body(&binfo, nbits, \ 161 prev_size); \ 162 } 163 prev_size = 0; 164 NBITS_TAB 165#undef NB 166} 167TEST_END 168 169static void 170test_bitmap_init_body(const bitmap_info_t *binfo, size_t nbits) { 171 size_t i; 172 bitmap_t *bitmap = (bitmap_t *)malloc(bitmap_size(binfo)); 173 assert_ptr_not_null(bitmap, "Unexpected malloc() failure"); 174 175 bitmap_init(bitmap, binfo, false); 176 for (i = 0; i < nbits; i++) { 177 assert_false(bitmap_get(bitmap, binfo, i), 178 "Bit should be unset"); 179 } 180 181 bitmap_init(bitmap, binfo, true); 182 for (i = 0; i < nbits; i++) { 183 assert_true(bitmap_get(bitmap, binfo, i), "Bit should be set"); 184 } 185 186 free(bitmap); 187} 188 189TEST_BEGIN(test_bitmap_init) { 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 size_t i; 209 bitmap_t *bitmap = (bitmap_t *)malloc(bitmap_size(binfo)); 210 assert_ptr_not_null(bitmap, "Unexpected malloc() failure"); 211 bitmap_init(bitmap, binfo, false); 212 213 for (i = 0; i < nbits; i++) { 214 bitmap_set(bitmap, binfo, i); 215 } 216 assert_true(bitmap_full(bitmap, binfo), "All bits should be set"); 217 free(bitmap); 218} 219 220TEST_BEGIN(test_bitmap_set) { 221 size_t nbits; 222 223 for (nbits = 1; nbits <= BITMAP_MAXBITS; nbits++) { 224 bitmap_info_t binfo; 225 bitmap_info_init(&binfo, nbits); 226 test_bitmap_set_body(&binfo, nbits); 227 } 228#define NB(nbits) { \ 229 bitmap_info_t binfo = BITMAP_INFO_INITIALIZER(nbits); \ 230 test_bitmap_set_body(&binfo, nbits); \ 231 } 232 NBITS_TAB 233#undef NB 234} 235TEST_END 236 237static void 238test_bitmap_unset_body(const bitmap_info_t *binfo, size_t nbits) { 239 size_t i; 240 bitmap_t *bitmap = (bitmap_t *)malloc(bitmap_size(binfo)); 241 assert_ptr_not_null(bitmap, "Unexpected malloc() failure"); 242 bitmap_init(bitmap, binfo, false); 243 244 for (i = 0; i < nbits; i++) { 245 bitmap_set(bitmap, binfo, i); 246 } 247 assert_true(bitmap_full(bitmap, binfo), "All bits should be set"); 248 for (i = 0; i < nbits; i++) { 249 bitmap_unset(bitmap, binfo, i); 250 } 251 for (i = 0; i < nbits; i++) { 252 bitmap_set(bitmap, binfo, i); 253 } 254 assert_true(bitmap_full(bitmap, binfo), "All bits should be set"); 255 free(bitmap); 256} 257 258TEST_BEGIN(test_bitmap_unset) { 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_xfu_body(const bitmap_info_t *binfo, size_t nbits) { 277 bitmap_t *bitmap = (bitmap_t *)malloc(bitmap_size(binfo)); 278 assert_ptr_not_null(bitmap, "Unexpected malloc() failure"); 279 bitmap_init(bitmap, binfo, false); 280 281 /* Iteratively set bits starting at the beginning. */ 282 for (size_t i = 0; i < nbits; i++) { 283 assert_zu_eq(bitmap_ffu(bitmap, binfo, 0), i, 284 "First unset bit should be just after previous first unset " 285 "bit"); 286 assert_zu_eq(bitmap_ffu(bitmap, binfo, (i > 0) ? i-1 : i), i, 287 "First unset bit should be just after previous first unset " 288 "bit"); 289 assert_zu_eq(bitmap_ffu(bitmap, binfo, i), i, 290 "First unset bit should be just after previous first unset " 291 "bit"); 292 assert_zu_eq(bitmap_sfu(bitmap, binfo), i, 293 "First unset bit should be just after previous first unset " 294 "bit"); 295 } 296 assert_true(bitmap_full(bitmap, binfo), "All bits should be set"); 297 298 /* 299 * Iteratively unset bits starting at the end, and verify that 300 * bitmap_sfu() reaches the unset bits. 301 */ 302 for (size_t i = nbits - 1; i < nbits; i--) { /* (nbits..0] */ 303 bitmap_unset(bitmap, binfo, i); 304 assert_zu_eq(bitmap_ffu(bitmap, binfo, 0), i, 305 "First unset bit should the bit previously unset"); 306 assert_zu_eq(bitmap_ffu(bitmap, binfo, (i > 0) ? i-1 : i), i, 307 "First unset bit should the bit previously unset"); 308 assert_zu_eq(bitmap_ffu(bitmap, binfo, i), i, 309 "First unset bit should the bit previously unset"); 310 assert_zu_eq(bitmap_sfu(bitmap, binfo), i, 311 "First unset bit should the bit previously unset"); 312 bitmap_unset(bitmap, binfo, i); 313 } 314 assert_false(bitmap_get(bitmap, binfo, 0), "Bit should be unset"); 315 316 /* 317 * Iteratively set bits starting at the beginning, and verify that 318 * bitmap_sfu() looks past them. 319 */ 320 for (size_t i = 1; i < nbits; i++) { 321 bitmap_set(bitmap, binfo, i - 1); 322 assert_zu_eq(bitmap_ffu(bitmap, binfo, 0), i, 323 "First unset bit should be just after the bit previously " 324 "set"); 325 assert_zu_eq(bitmap_ffu(bitmap, binfo, (i > 0) ? i-1 : i), i, 326 "First unset bit should be just after the bit previously " 327 "set"); 328 assert_zu_eq(bitmap_ffu(bitmap, binfo, i), i, 329 "First unset bit should be just after the bit previously " 330 "set"); 331 assert_zu_eq(bitmap_sfu(bitmap, binfo), i, 332 "First unset bit should be just after the bit previously " 333 "set"); 334 bitmap_unset(bitmap, binfo, i); 335 } 336 assert_zu_eq(bitmap_ffu(bitmap, binfo, 0), nbits - 1, 337 "First unset bit should be the last bit"); 338 assert_zu_eq(bitmap_ffu(bitmap, binfo, (nbits > 1) ? nbits-2 : nbits-1), 339 nbits - 1, "First unset bit should be the last bit"); 340 assert_zu_eq(bitmap_ffu(bitmap, binfo, nbits - 1), nbits - 1, 341 "First unset bit should be the last bit"); 342 assert_zu_eq(bitmap_sfu(bitmap, binfo), nbits - 1, 343 "First unset bit should be the last bit"); 344 assert_true(bitmap_full(bitmap, binfo), "All bits should be set"); 345 346 /* 347 * Bubble a "usu" pattern through the bitmap and verify that 348 * bitmap_ffu() finds the correct bit for all five min_bit cases. 349 */ 350 if (nbits >= 3) { 351 for (size_t i = 0; i < nbits-2; i++) { 352 bitmap_unset(bitmap, binfo, i); 353 bitmap_unset(bitmap, binfo, i+2); 354 if (i > 0) { 355 assert_zu_eq(bitmap_ffu(bitmap, binfo, i-1), i, 356 "Unexpected first unset bit"); 357 } 358 assert_zu_eq(bitmap_ffu(bitmap, binfo, i), i, 359 "Unexpected first unset bit"); 360 assert_zu_eq(bitmap_ffu(bitmap, binfo, i+1), i+2, 361 "Unexpected first unset bit"); 362 assert_zu_eq(bitmap_ffu(bitmap, binfo, i+2), i+2, 363 "Unexpected first unset bit"); 364 if (i + 3 < nbits) { 365 assert_zu_eq(bitmap_ffu(bitmap, binfo, i+3), 366 nbits, "Unexpected first unset bit"); 367 } 368 assert_zu_eq(bitmap_sfu(bitmap, binfo), i, 369 "Unexpected first unset bit"); 370 assert_zu_eq(bitmap_sfu(bitmap, binfo), i+2, 371 "Unexpected first unset bit"); 372 } 373 } 374 375 /* 376 * Unset the last bit, bubble another unset bit through the bitmap, and 377 * verify that bitmap_ffu() finds the correct bit for all four min_bit 378 * cases. 379 */ 380 if (nbits >= 3) { 381 bitmap_unset(bitmap, binfo, nbits-1); 382 for (size_t i = 0; i < nbits-1; i++) { 383 bitmap_unset(bitmap, binfo, i); 384 if (i > 0) { 385 assert_zu_eq(bitmap_ffu(bitmap, binfo, i-1), i, 386 "Unexpected first unset bit"); 387 } 388 assert_zu_eq(bitmap_ffu(bitmap, binfo, i), i, 389 "Unexpected first unset bit"); 390 assert_zu_eq(bitmap_ffu(bitmap, binfo, i+1), nbits-1, 391 "Unexpected first unset bit"); 392 assert_zu_eq(bitmap_ffu(bitmap, binfo, nbits-1), 393 nbits-1, "Unexpected first unset bit"); 394 395 assert_zu_eq(bitmap_sfu(bitmap, binfo), i, 396 "Unexpected first unset bit"); 397 } 398 assert_zu_eq(bitmap_sfu(bitmap, binfo), nbits-1, 399 "Unexpected first unset bit"); 400 } 401 402 free(bitmap); 403} 404 405TEST_BEGIN(test_bitmap_xfu) { 406 size_t nbits; 407 408 for (nbits = 1; nbits <= BITMAP_MAXBITS; nbits++) { 409 bitmap_info_t binfo; 410 bitmap_info_init(&binfo, nbits); 411 test_bitmap_xfu_body(&binfo, nbits); 412 } 413#define NB(nbits) { \ 414 bitmap_info_t binfo = BITMAP_INFO_INITIALIZER(nbits); \ 415 test_bitmap_xfu_body(&binfo, nbits); \ 416 } 417 NBITS_TAB 418#undef NB 419} 420TEST_END 421 422int 423main(void) { 424 return test( 425 test_bitmap_initializer, 426 test_bitmap_size, 427 test_bitmap_init, 428 test_bitmap_set, 429 test_bitmap_unset, 430 test_bitmap_xfu); 431} 432