1 #include "test/jemalloc_test.h" 2 3 #include "jemalloc/internal/fb.h" 4 #include "test/nbits.h" 5 6 static void 7 do_test_init(size_t nbits) { 8 size_t sz = FB_NGROUPS(nbits) * sizeof(fb_group_t); 9 fb_group_t *fb = malloc(sz); 10 /* Junk fb's contents. */ 11 memset(fb, 99, sz); 12 fb_init(fb, nbits); 13 for (size_t i = 0; i < nbits; i++) { 14 expect_false(fb_get(fb, nbits, i), 15 "bitmap should start empty"); 16 } 17 free(fb); 18 } 19 20 TEST_BEGIN(test_fb_init) { 21 #define NB(nbits) \ 22 do_test_init(nbits); 23 NBITS_TAB 24 #undef NB 25 } 26 TEST_END 27 28 static void 29 do_test_get_set_unset(size_t nbits) { 30 size_t sz = FB_NGROUPS(nbits) * sizeof(fb_group_t); 31 fb_group_t *fb = malloc(sz); 32 fb_init(fb, nbits); 33 /* Set the bits divisible by 3. */ 34 for (size_t i = 0; i < nbits; i++) { 35 if (i % 3 == 0) { 36 fb_set(fb, nbits, i); 37 } 38 } 39 /* Check them. */ 40 for (size_t i = 0; i < nbits; i++) { 41 expect_b_eq(i % 3 == 0, fb_get(fb, nbits, i), 42 "Unexpected bit at position %zu", i); 43 } 44 /* Unset those divisible by 5. */ 45 for (size_t i = 0; i < nbits; i++) { 46 if (i % 5 == 0) { 47 fb_unset(fb, nbits, i); 48 } 49 } 50 /* Check them. */ 51 for (size_t i = 0; i < nbits; i++) { 52 expect_b_eq(i % 3 == 0 && i % 5 != 0, fb_get(fb, nbits, i), 53 "Unexpected bit at position %zu", i); 54 } 55 free(fb); 56 } 57 58 TEST_BEGIN(test_get_set_unset) { 59 #define NB(nbits) \ 60 do_test_get_set_unset(nbits); 61 NBITS_TAB 62 #undef NB 63 } 64 TEST_END 65 66 static ssize_t 67 find_3_5_compute(ssize_t i, size_t nbits, bool bit, bool forward) { 68 for(; i < (ssize_t)nbits && i >= 0; i += (forward ? 1 : -1)) { 69 bool expected_bit = i % 3 == 0 || i % 5 == 0; 70 if (expected_bit == bit) { 71 return i; 72 } 73 } 74 return forward ? (ssize_t)nbits : (ssize_t)-1; 75 } 76 77 static void 78 do_test_search_simple(size_t nbits) { 79 size_t sz = FB_NGROUPS(nbits) * sizeof(fb_group_t); 80 fb_group_t *fb = malloc(sz); 81 fb_init(fb, nbits); 82 83 /* We pick multiples of 3 or 5. */ 84 for (size_t i = 0; i < nbits; i++) { 85 if (i % 3 == 0) { 86 fb_set(fb, nbits, i); 87 } 88 /* This tests double-setting a little, too. */ 89 if (i % 5 == 0) { 90 fb_set(fb, nbits, i); 91 } 92 } 93 for (size_t i = 0; i < nbits; i++) { 94 size_t ffs_compute = find_3_5_compute(i, nbits, true, true); 95 size_t ffs_search = fb_ffs(fb, nbits, i); 96 expect_zu_eq(ffs_compute, ffs_search, "ffs mismatch at %zu", i); 97 98 ssize_t fls_compute = find_3_5_compute(i, nbits, true, false); 99 size_t fls_search = fb_fls(fb, nbits, i); 100 expect_zu_eq(fls_compute, fls_search, "fls mismatch at %zu", i); 101 102 size_t ffu_compute = find_3_5_compute(i, nbits, false, true); 103 size_t ffu_search = fb_ffu(fb, nbits, i); 104 expect_zu_eq(ffu_compute, ffu_search, "ffu mismatch at %zu", i); 105 106 size_t flu_compute = find_3_5_compute(i, nbits, false, false); 107 size_t flu_search = fb_flu(fb, nbits, i); 108 expect_zu_eq(flu_compute, flu_search, "flu mismatch at %zu", i); 109 } 110 111 free(fb); 112 } 113 114 TEST_BEGIN(test_search_simple) { 115 #define NB(nbits) \ 116 do_test_search_simple(nbits); 117 NBITS_TAB 118 #undef NB 119 } 120 TEST_END 121 122 static void 123 expect_exhaustive_results(fb_group_t *mostly_full, fb_group_t *mostly_empty, 124 size_t nbits, size_t special_bit, size_t position) { 125 if (position < special_bit) { 126 expect_zu_eq(special_bit, fb_ffs(mostly_empty, nbits, position), 127 "mismatch at %zu, %zu", position, special_bit); 128 expect_zd_eq(-1, fb_fls(mostly_empty, nbits, position), 129 "mismatch at %zu, %zu", position, special_bit); 130 expect_zu_eq(position, fb_ffu(mostly_empty, nbits, position), 131 "mismatch at %zu, %zu", position, special_bit); 132 expect_zd_eq(position, fb_flu(mostly_empty, nbits, position), 133 "mismatch at %zu, %zu", position, special_bit); 134 135 expect_zu_eq(position, fb_ffs(mostly_full, nbits, position), 136 "mismatch at %zu, %zu", position, special_bit); 137 expect_zd_eq(position, fb_fls(mostly_full, nbits, position), 138 "mismatch at %zu, %zu", position, special_bit); 139 expect_zu_eq(special_bit, fb_ffu(mostly_full, nbits, position), 140 "mismatch at %zu, %zu", position, special_bit); 141 expect_zd_eq(-1, fb_flu(mostly_full, nbits, position), 142 "mismatch at %zu, %zu", position, special_bit); 143 } else if (position == special_bit) { 144 expect_zu_eq(special_bit, fb_ffs(mostly_empty, nbits, position), 145 "mismatch at %zu, %zu", position, special_bit); 146 expect_zd_eq(special_bit, fb_fls(mostly_empty, nbits, position), 147 "mismatch at %zu, %zu", position, special_bit); 148 expect_zu_eq(position + 1, fb_ffu(mostly_empty, nbits, position), 149 "mismatch at %zu, %zu", position, special_bit); 150 expect_zd_eq(position - 1, fb_flu(mostly_empty, nbits, 151 position), "mismatch at %zu, %zu", position, special_bit); 152 153 expect_zu_eq(position + 1, fb_ffs(mostly_full, nbits, position), 154 "mismatch at %zu, %zu", position, special_bit); 155 expect_zd_eq(position - 1, fb_fls(mostly_full, nbits, 156 position), "mismatch at %zu, %zu", position, special_bit); 157 expect_zu_eq(position, fb_ffu(mostly_full, nbits, position), 158 "mismatch at %zu, %zu", position, special_bit); 159 expect_zd_eq(position, fb_flu(mostly_full, nbits, position), 160 "mismatch at %zu, %zu", position, special_bit); 161 } else { 162 /* position > special_bit. */ 163 expect_zu_eq(nbits, fb_ffs(mostly_empty, nbits, position), 164 "mismatch at %zu, %zu", position, special_bit); 165 expect_zd_eq(special_bit, fb_fls(mostly_empty, nbits, 166 position), "mismatch at %zu, %zu", position, special_bit); 167 expect_zu_eq(position, fb_ffu(mostly_empty, nbits, position), 168 "mismatch at %zu, %zu", position, special_bit); 169 expect_zd_eq(position, fb_flu(mostly_empty, nbits, position), 170 "mismatch at %zu, %zu", position, special_bit); 171 172 expect_zu_eq(position, fb_ffs(mostly_full, nbits, position), 173 "mismatch at %zu, %zu", position, special_bit); 174 expect_zd_eq(position, fb_fls(mostly_full, nbits, position), 175 "mismatch at %zu, %zu", position, special_bit); 176 expect_zu_eq(nbits, fb_ffu(mostly_full, nbits, position), 177 "mismatch at %zu, %zu", position, special_bit); 178 expect_zd_eq(special_bit, fb_flu(mostly_full, nbits, position), 179 "mismatch at %zu, %zu", position, special_bit); 180 } 181 } 182 183 static void 184 do_test_search_exhaustive(size_t nbits) { 185 /* This test is quadratic; let's not get too big. */ 186 if (nbits > 1000) { 187 return; 188 } 189 size_t sz = FB_NGROUPS(nbits) * sizeof(fb_group_t); 190 fb_group_t *empty = malloc(sz); 191 fb_init(empty, nbits); 192 fb_group_t *full = malloc(sz); 193 fb_init(full, nbits); 194 fb_set_range(full, nbits, 0, nbits); 195 196 for (size_t i = 0; i < nbits; i++) { 197 fb_set(empty, nbits, i); 198 fb_unset(full, nbits, i); 199 200 for (size_t j = 0; j < nbits; j++) { 201 expect_exhaustive_results(full, empty, nbits, i, j); 202 } 203 fb_unset(empty, nbits, i); 204 fb_set(full, nbits, i); 205 } 206 207 free(empty); 208 free(full); 209 } 210 211 TEST_BEGIN(test_search_exhaustive) { 212 #define NB(nbits) \ 213 do_test_search_exhaustive(nbits); 214 NBITS_TAB 215 #undef NB 216 } 217 TEST_END 218 219 TEST_BEGIN(test_range_simple) { 220 /* 221 * Just pick a constant big enough to have nontrivial middle sizes, and 222 * big enough that usages of things like weirdnum (below) near the 223 * beginning fit comfortably into the beginning of the bitmap. 224 */ 225 size_t nbits = 64 * 10; 226 size_t ngroups = FB_NGROUPS(nbits); 227 fb_group_t *fb = malloc(sizeof(fb_group_t) * ngroups); 228 fb_init(fb, nbits); 229 for (size_t i = 0; i < nbits; i++) { 230 if (i % 2 == 0) { 231 fb_set_range(fb, nbits, i, 1); 232 } 233 } 234 for (size_t i = 0; i < nbits; i++) { 235 expect_b_eq(i % 2 == 0, fb_get(fb, nbits, i), 236 "mismatch at position %zu", i); 237 } 238 fb_set_range(fb, nbits, 0, nbits / 2); 239 fb_unset_range(fb, nbits, nbits / 2, nbits / 2); 240 for (size_t i = 0; i < nbits; i++) { 241 expect_b_eq(i < nbits / 2, fb_get(fb, nbits, i), 242 "mismatch at position %zu", i); 243 } 244 245 static const size_t weirdnum = 7; 246 fb_set_range(fb, nbits, 0, nbits); 247 fb_unset_range(fb, nbits, weirdnum, FB_GROUP_BITS + weirdnum); 248 for (size_t i = 0; i < nbits; i++) { 249 expect_b_eq(7 <= i && i <= 2 * weirdnum + FB_GROUP_BITS - 1, 250 !fb_get(fb, nbits, i), "mismatch at position %zu", i); 251 } 252 free(fb); 253 } 254 TEST_END 255 256 static void 257 do_test_empty_full_exhaustive(size_t nbits) { 258 size_t sz = FB_NGROUPS(nbits) * sizeof(fb_group_t); 259 fb_group_t *empty = malloc(sz); 260 fb_init(empty, nbits); 261 fb_group_t *full = malloc(sz); 262 fb_init(full, nbits); 263 fb_set_range(full, nbits, 0, nbits); 264 265 expect_true(fb_full(full, nbits), ""); 266 expect_false(fb_empty(full, nbits), ""); 267 expect_false(fb_full(empty, nbits), ""); 268 expect_true(fb_empty(empty, nbits), ""); 269 270 for (size_t i = 0; i < nbits; i++) { 271 fb_set(empty, nbits, i); 272 fb_unset(full, nbits, i); 273 274 expect_false(fb_empty(empty, nbits), "error at bit %zu", i); 275 if (nbits != 1) { 276 expect_false(fb_full(empty, nbits), 277 "error at bit %zu", i); 278 expect_false(fb_empty(full, nbits), 279 "error at bit %zu", i); 280 } else { 281 expect_true(fb_full(empty, nbits), 282 "error at bit %zu", i); 283 expect_true(fb_empty(full, nbits), 284 "error at bit %zu", i); 285 } 286 expect_false(fb_full(full, nbits), "error at bit %zu", i); 287 288 fb_unset(empty, nbits, i); 289 fb_set(full, nbits, i); 290 } 291 292 free(empty); 293 free(full); 294 } 295 296 TEST_BEGIN(test_empty_full) { 297 #define NB(nbits) \ 298 do_test_empty_full_exhaustive(nbits); 299 NBITS_TAB 300 #undef NB 301 } 302 TEST_END 303 304 /* 305 * This tests both iter_range and the longest range functionality, which is 306 * built closely on top of it. 307 */ 308 TEST_BEGIN(test_iter_range_simple) { 309 size_t set_limit = 30; 310 size_t nbits = 100; 311 fb_group_t fb[FB_NGROUPS(100)]; 312 313 fb_init(fb, nbits); 314 315 /* 316 * Failing to initialize these can lead to build failures with -Wall; 317 * the compiler can't prove that they're set. 318 */ 319 size_t begin = (size_t)-1; 320 size_t len = (size_t)-1; 321 bool result; 322 323 /* A set of checks with only the first set_limit bits *set*. */ 324 fb_set_range(fb, nbits, 0, set_limit); 325 expect_zu_eq(set_limit, fb_srange_longest(fb, nbits), 326 "Incorrect longest set range"); 327 expect_zu_eq(nbits - set_limit, fb_urange_longest(fb, nbits), 328 "Incorrect longest unset range"); 329 for (size_t i = 0; i < set_limit; i++) { 330 result = fb_srange_iter(fb, nbits, i, &begin, &len); 331 expect_true(result, "Should have found a range at %zu", i); 332 expect_zu_eq(i, begin, "Incorrect begin at %zu", i); 333 expect_zu_eq(set_limit - i, len, "Incorrect len at %zu", i); 334 335 result = fb_urange_iter(fb, nbits, i, &begin, &len); 336 expect_true(result, "Should have found a range at %zu", i); 337 expect_zu_eq(set_limit, begin, "Incorrect begin at %zu", i); 338 expect_zu_eq(nbits - set_limit, len, "Incorrect len at %zu", i); 339 340 result = fb_srange_riter(fb, nbits, i, &begin, &len); 341 expect_true(result, "Should have found a range at %zu", i); 342 expect_zu_eq(0, begin, "Incorrect begin at %zu", i); 343 expect_zu_eq(i + 1, len, "Incorrect len at %zu", i); 344 345 result = fb_urange_riter(fb, nbits, i, &begin, &len); 346 expect_false(result, "Should not have found a range at %zu", i); 347 } 348 for (size_t i = set_limit; i < nbits; i++) { 349 result = fb_srange_iter(fb, nbits, i, &begin, &len); 350 expect_false(result, "Should not have found a range at %zu", i); 351 352 result = fb_urange_iter(fb, nbits, i, &begin, &len); 353 expect_true(result, "Should have found a range at %zu", i); 354 expect_zu_eq(i, begin, "Incorrect begin at %zu", i); 355 expect_zu_eq(nbits - i, len, "Incorrect len at %zu", i); 356 357 result = fb_srange_riter(fb, nbits, i, &begin, &len); 358 expect_true(result, "Should have found a range at %zu", i); 359 expect_zu_eq(0, begin, "Incorrect begin at %zu", i); 360 expect_zu_eq(set_limit, len, "Incorrect len at %zu", i); 361 362 result = fb_urange_riter(fb, nbits, i, &begin, &len); 363 expect_true(result, "Should have found a range at %zu", i); 364 expect_zu_eq(set_limit, begin, "Incorrect begin at %zu", i); 365 expect_zu_eq(i - set_limit + 1, len, "Incorrect len at %zu", i); 366 } 367 368 /* A set of checks with only the first set_limit bits *unset*. */ 369 fb_unset_range(fb, nbits, 0, set_limit); 370 fb_set_range(fb, nbits, set_limit, nbits - set_limit); 371 expect_zu_eq(nbits - set_limit, fb_srange_longest(fb, nbits), 372 "Incorrect longest set range"); 373 expect_zu_eq(set_limit, fb_urange_longest(fb, nbits), 374 "Incorrect longest unset range"); 375 for (size_t i = 0; i < set_limit; i++) { 376 result = fb_srange_iter(fb, nbits, i, &begin, &len); 377 expect_true(result, "Should have found a range at %zu", i); 378 expect_zu_eq(set_limit, begin, "Incorrect begin at %zu", i); 379 expect_zu_eq(nbits - set_limit, len, "Incorrect len at %zu", i); 380 381 result = fb_urange_iter(fb, nbits, i, &begin, &len); 382 expect_true(result, "Should have found a range at %zu", i); 383 expect_zu_eq(i, begin, "Incorrect begin at %zu", i); 384 expect_zu_eq(set_limit - i, len, "Incorrect len at %zu", i); 385 386 result = fb_srange_riter(fb, nbits, i, &begin, &len); 387 expect_false(result, "Should not have found a range at %zu", i); 388 389 result = fb_urange_riter(fb, nbits, i, &begin, &len); 390 expect_true(result, "Should not have found a range at %zu", i); 391 expect_zu_eq(0, begin, "Incorrect begin at %zu", i); 392 expect_zu_eq(i + 1, len, "Incorrect len at %zu", i); 393 } 394 for (size_t i = set_limit; i < nbits; i++) { 395 result = fb_srange_iter(fb, nbits, i, &begin, &len); 396 expect_true(result, "Should have found a range at %zu", i); 397 expect_zu_eq(i, begin, "Incorrect begin at %zu", i); 398 expect_zu_eq(nbits - i, len, "Incorrect len at %zu", i); 399 400 result = fb_urange_iter(fb, nbits, i, &begin, &len); 401 expect_false(result, "Should not have found a range at %zu", i); 402 403 result = fb_srange_riter(fb, nbits, i, &begin, &len); 404 expect_true(result, "Should have found a range at %zu", i); 405 expect_zu_eq(set_limit, begin, "Incorrect begin at %zu", i); 406 expect_zu_eq(i - set_limit + 1, len, "Incorrect len at %zu", i); 407 408 result = fb_urange_riter(fb, nbits, i, &begin, &len); 409 expect_true(result, "Should have found a range at %zu", i); 410 expect_zu_eq(0, begin, "Incorrect begin at %zu", i); 411 expect_zu_eq(set_limit, len, "Incorrect len at %zu", i); 412 } 413 414 } 415 TEST_END 416 417 /* 418 * Doing this bit-by-bit is too slow for a real implementation, but for testing 419 * code, it's easy to get right. In the exhaustive tests, we'll compare the 420 * (fast but tricky) real implementation against the (slow but simple) testing 421 * one. 422 */ 423 static bool 424 fb_iter_simple(fb_group_t *fb, size_t nbits, size_t start, size_t *r_begin, 425 size_t *r_len, bool val, bool forward) { 426 ssize_t stride = (forward ? (ssize_t)1 : (ssize_t)-1); 427 ssize_t range_begin = (ssize_t)start; 428 for (; range_begin != (ssize_t)nbits && range_begin != -1; 429 range_begin += stride) { 430 if (fb_get(fb, nbits, range_begin) == val) { 431 ssize_t range_end = range_begin; 432 for (; range_end != (ssize_t)nbits && range_end != -1; 433 range_end += stride) { 434 if (fb_get(fb, nbits, range_end) != val) { 435 break; 436 } 437 } 438 if (forward) { 439 *r_begin = range_begin; 440 *r_len = range_end - range_begin; 441 } else { 442 *r_begin = range_end + 1; 443 *r_len = range_begin - range_end; 444 } 445 return true; 446 } 447 } 448 return false; 449 } 450 451 /* Similar, but for finding longest ranges. */ 452 static size_t 453 fb_range_longest_simple(fb_group_t *fb, size_t nbits, bool val) { 454 size_t longest_so_far = 0; 455 for (size_t begin = 0; begin < nbits; begin++) { 456 if (fb_get(fb, nbits, begin) != val) { 457 continue; 458 } 459 size_t end = begin + 1; 460 for (; end < nbits; end++) { 461 if (fb_get(fb, nbits, end) != val) { 462 break; 463 } 464 } 465 if (end - begin > longest_so_far) { 466 longest_so_far = end - begin; 467 } 468 } 469 return longest_so_far; 470 } 471 472 static void 473 expect_iter_results_at(fb_group_t *fb, size_t nbits, size_t pos, 474 bool val, bool forward) { 475 bool iter_res; 476 size_t iter_begin JEMALLOC_CC_SILENCE_INIT(0); 477 size_t iter_len JEMALLOC_CC_SILENCE_INIT(0); 478 if (val) { 479 if (forward) { 480 iter_res = fb_srange_iter(fb, nbits, pos, 481 &iter_begin, &iter_len); 482 } else { 483 iter_res = fb_srange_riter(fb, nbits, pos, 484 &iter_begin, &iter_len); 485 } 486 } else { 487 if (forward) { 488 iter_res = fb_urange_iter(fb, nbits, pos, 489 &iter_begin, &iter_len); 490 } else { 491 iter_res = fb_urange_riter(fb, nbits, pos, 492 &iter_begin, &iter_len); 493 } 494 } 495 496 bool simple_iter_res; 497 /* 498 * These are dead stores, but the compiler can't always figure that out 499 * statically, and warns on the uninitialized variable. 500 */ 501 size_t simple_iter_begin = 0; 502 size_t simple_iter_len = 0; 503 simple_iter_res = fb_iter_simple(fb, nbits, pos, &simple_iter_begin, 504 &simple_iter_len, val, forward); 505 506 expect_b_eq(iter_res, simple_iter_res, "Result mismatch at %zu", pos); 507 if (iter_res && simple_iter_res) { 508 assert_zu_eq(iter_begin, simple_iter_begin, 509 "Begin mismatch at %zu", pos); 510 expect_zu_eq(iter_len, simple_iter_len, 511 "Length mismatch at %zu", pos); 512 } 513 } 514 515 static void 516 expect_iter_results(fb_group_t *fb, size_t nbits) { 517 for (size_t i = 0; i < nbits; i++) { 518 expect_iter_results_at(fb, nbits, i, false, false); 519 expect_iter_results_at(fb, nbits, i, false, true); 520 expect_iter_results_at(fb, nbits, i, true, false); 521 expect_iter_results_at(fb, nbits, i, true, true); 522 } 523 expect_zu_eq(fb_range_longest_simple(fb, nbits, true), 524 fb_srange_longest(fb, nbits), "Longest range mismatch"); 525 expect_zu_eq(fb_range_longest_simple(fb, nbits, false), 526 fb_urange_longest(fb, nbits), "Longest range mismatch"); 527 } 528 529 static void 530 set_pattern_3(fb_group_t *fb, size_t nbits, bool zero_val) { 531 for (size_t i = 0; i < nbits; i++) { 532 if ((i % 6 < 3 && zero_val) || (i % 6 >= 3 && !zero_val)) { 533 fb_set(fb, nbits, i); 534 } else { 535 fb_unset(fb, nbits, i); 536 } 537 } 538 } 539 540 static void 541 do_test_iter_range_exhaustive(size_t nbits) { 542 /* This test is also pretty slow. */ 543 if (nbits > 1000) { 544 return; 545 } 546 size_t sz = FB_NGROUPS(nbits) * sizeof(fb_group_t); 547 fb_group_t *fb = malloc(sz); 548 fb_init(fb, nbits); 549 550 set_pattern_3(fb, nbits, /* zero_val */ true); 551 expect_iter_results(fb, nbits); 552 553 set_pattern_3(fb, nbits, /* zero_val */ false); 554 expect_iter_results(fb, nbits); 555 556 fb_set_range(fb, nbits, 0, nbits); 557 fb_unset_range(fb, nbits, 0, nbits / 2 == 0 ? 1 : nbits / 2); 558 expect_iter_results(fb, nbits); 559 560 fb_unset_range(fb, nbits, 0, nbits); 561 fb_set_range(fb, nbits, 0, nbits / 2 == 0 ? 1: nbits / 2); 562 expect_iter_results(fb, nbits); 563 564 free(fb); 565 } 566 567 /* 568 * Like test_iter_range_simple, this tests both iteration and longest-range 569 * computation. 570 */ 571 TEST_BEGIN(test_iter_range_exhaustive) { 572 #define NB(nbits) \ 573 do_test_iter_range_exhaustive(nbits); 574 NBITS_TAB 575 #undef NB 576 } 577 TEST_END 578 579 /* 580 * If all set bits in the bitmap are contiguous, in [set_start, set_end), 581 * returns the number of set bits in [scount_start, scount_end). 582 */ 583 static size_t 584 scount_contiguous(size_t set_start, size_t set_end, size_t scount_start, 585 size_t scount_end) { 586 /* No overlap. */ 587 if (set_end <= scount_start || scount_end <= set_start) { 588 return 0; 589 } 590 /* set range contains scount range */ 591 if (set_start <= scount_start && set_end >= scount_end) { 592 return scount_end - scount_start; 593 } 594 /* scount range contains set range. */ 595 if (scount_start <= set_start && scount_end >= set_end) { 596 return set_end - set_start; 597 } 598 /* Partial overlap, with set range starting first. */ 599 if (set_start < scount_start && set_end < scount_end) { 600 return set_end - scount_start; 601 } 602 /* Partial overlap, with scount range starting first. */ 603 if (scount_start < set_start && scount_end < set_end) { 604 return scount_end - set_start; 605 } 606 /* 607 * Trigger an assert failure; the above list should have been 608 * exhaustive. 609 */ 610 unreachable(); 611 } 612 613 static size_t 614 ucount_contiguous(size_t set_start, size_t set_end, size_t ucount_start, 615 size_t ucount_end) { 616 /* No overlap. */ 617 if (set_end <= ucount_start || ucount_end <= set_start) { 618 return ucount_end - ucount_start; 619 } 620 /* set range contains ucount range */ 621 if (set_start <= ucount_start && set_end >= ucount_end) { 622 return 0; 623 } 624 /* ucount range contains set range. */ 625 if (ucount_start <= set_start && ucount_end >= set_end) { 626 return (ucount_end - ucount_start) - (set_end - set_start); 627 } 628 /* Partial overlap, with set range starting first. */ 629 if (set_start < ucount_start && set_end < ucount_end) { 630 return ucount_end - set_end; 631 } 632 /* Partial overlap, with ucount range starting first. */ 633 if (ucount_start < set_start && ucount_end < set_end) { 634 return set_start - ucount_start; 635 } 636 /* 637 * Trigger an assert failure; the above list should have been 638 * exhaustive. 639 */ 640 unreachable(); 641 } 642 643 static void 644 expect_count_match_contiguous(fb_group_t *fb, size_t nbits, size_t set_start, 645 size_t set_end) { 646 for (size_t i = 0; i < nbits; i++) { 647 for (size_t j = i + 1; j <= nbits; j++) { 648 size_t cnt = j - i; 649 size_t scount_expected = scount_contiguous(set_start, 650 set_end, i, j); 651 size_t scount_computed = fb_scount(fb, nbits, i, cnt); 652 expect_zu_eq(scount_expected, scount_computed, 653 "fb_scount error with nbits=%zu, start=%zu, " 654 "cnt=%zu, with bits set in [%zu, %zu)", 655 nbits, i, cnt, set_start, set_end); 656 657 size_t ucount_expected = ucount_contiguous(set_start, 658 set_end, i, j); 659 size_t ucount_computed = fb_ucount(fb, nbits, i, cnt); 660 assert_zu_eq(ucount_expected, ucount_computed, 661 "fb_ucount error with nbits=%zu, start=%zu, " 662 "cnt=%zu, with bits set in [%zu, %zu)", 663 nbits, i, cnt, set_start, set_end); 664 665 } 666 } 667 } 668 669 static void 670 do_test_count_contiguous(size_t nbits) { 671 size_t sz = FB_NGROUPS(nbits) * sizeof(fb_group_t); 672 fb_group_t *fb = malloc(sz); 673 674 fb_init(fb, nbits); 675 676 expect_count_match_contiguous(fb, nbits, 0, 0); 677 for (size_t i = 0; i < nbits; i++) { 678 fb_set(fb, nbits, i); 679 expect_count_match_contiguous(fb, nbits, 0, i + 1); 680 } 681 682 for (size_t i = 0; i < nbits; i++) { 683 fb_unset(fb, nbits, i); 684 expect_count_match_contiguous(fb, nbits, i + 1, nbits); 685 } 686 687 free(fb); 688 } 689 690 TEST_BEGIN(test_count_contiguous_simple) { 691 enum {nbits = 300}; 692 fb_group_t fb[FB_NGROUPS(nbits)]; 693 fb_init(fb, nbits); 694 /* Just an arbitrary number. */ 695 size_t start = 23; 696 697 fb_set_range(fb, nbits, start, 30 - start); 698 expect_count_match_contiguous(fb, nbits, start, 30); 699 700 fb_set_range(fb, nbits, start, 40 - start); 701 expect_count_match_contiguous(fb, nbits, start, 40); 702 703 fb_set_range(fb, nbits, start, 70 - start); 704 expect_count_match_contiguous(fb, nbits, start, 70); 705 706 fb_set_range(fb, nbits, start, 120 - start); 707 expect_count_match_contiguous(fb, nbits, start, 120); 708 709 fb_set_range(fb, nbits, start, 150 - start); 710 expect_count_match_contiguous(fb, nbits, start, 150); 711 712 fb_set_range(fb, nbits, start, 200 - start); 713 expect_count_match_contiguous(fb, nbits, start, 200); 714 715 fb_set_range(fb, nbits, start, 290 - start); 716 expect_count_match_contiguous(fb, nbits, start, 290); 717 } 718 TEST_END 719 720 TEST_BEGIN(test_count_contiguous) { 721 #define NB(nbits) \ 722 /* This test is *particularly* slow in debug builds. */ \ 723 if ((!config_debug && nbits < 300) || nbits < 150) { \ 724 do_test_count_contiguous(nbits); \ 725 } 726 NBITS_TAB 727 #undef NB 728 } 729 TEST_END 730 731 static void 732 expect_count_match_alternating(fb_group_t *fb_even, fb_group_t *fb_odd, 733 size_t nbits) { 734 for (size_t i = 0; i < nbits; i++) { 735 for (size_t j = i + 1; j <= nbits; j++) { 736 size_t cnt = j - i; 737 size_t odd_scount = cnt / 2 738 + (size_t)(cnt % 2 == 1 && i % 2 == 1); 739 size_t odd_scount_computed = fb_scount(fb_odd, nbits, 740 i, j - i); 741 assert_zu_eq(odd_scount, odd_scount_computed, 742 "fb_scount error with nbits=%zu, start=%zu, " 743 "cnt=%zu, with alternating bits set.", 744 nbits, i, j - i); 745 746 size_t odd_ucount = cnt / 2 747 + (size_t)(cnt % 2 == 1 && i % 2 == 0); 748 size_t odd_ucount_computed = fb_ucount(fb_odd, nbits, 749 i, j - i); 750 assert_zu_eq(odd_ucount, odd_ucount_computed, 751 "fb_ucount error with nbits=%zu, start=%zu, " 752 "cnt=%zu, with alternating bits set.", 753 nbits, i, j - i); 754 755 size_t even_scount = cnt / 2 756 + (size_t)(cnt % 2 == 1 && i % 2 == 0); 757 size_t even_scount_computed = fb_scount(fb_even, nbits, 758 i, j - i); 759 assert_zu_eq(even_scount, even_scount_computed, 760 "fb_scount error with nbits=%zu, start=%zu, " 761 "cnt=%zu, with alternating bits set.", 762 nbits, i, j - i); 763 764 size_t even_ucount = cnt / 2 765 + (size_t)(cnt % 2 == 1 && i % 2 == 1); 766 size_t even_ucount_computed = fb_ucount(fb_even, nbits, 767 i, j - i); 768 assert_zu_eq(even_ucount, even_ucount_computed, 769 "fb_ucount error with nbits=%zu, start=%zu, " 770 "cnt=%zu, with alternating bits set.", 771 nbits, i, j - i); 772 } 773 } 774 } 775 776 static void 777 do_test_count_alternating(size_t nbits) { 778 if (nbits > 1000) { 779 return; 780 } 781 size_t sz = FB_NGROUPS(nbits) * sizeof(fb_group_t); 782 fb_group_t *fb_even = malloc(sz); 783 fb_group_t *fb_odd = malloc(sz); 784 785 fb_init(fb_even, nbits); 786 fb_init(fb_odd, nbits); 787 788 for (size_t i = 0; i < nbits; i++) { 789 if (i % 2 == 0) { 790 fb_set(fb_even, nbits, i); 791 } else { 792 fb_set(fb_odd, nbits, i); 793 } 794 } 795 796 expect_count_match_alternating(fb_even, fb_odd, nbits); 797 798 free(fb_even); 799 free(fb_odd); 800 } 801 802 TEST_BEGIN(test_count_alternating) { 803 #define NB(nbits) \ 804 do_test_count_alternating(nbits); 805 NBITS_TAB 806 #undef NB 807 } 808 TEST_END 809 810 static void 811 do_test_bit_op(size_t nbits, bool (*op)(bool a, bool b), 812 void (*fb_op)(fb_group_t *dst, fb_group_t *src1, fb_group_t *src2, size_t nbits)) { 813 size_t sz = FB_NGROUPS(nbits) * sizeof(fb_group_t); 814 fb_group_t *fb1 = malloc(sz); 815 fb_group_t *fb2 = malloc(sz); 816 fb_group_t *fb_result = malloc(sz); 817 fb_init(fb1, nbits); 818 fb_init(fb2, nbits); 819 fb_init(fb_result, nbits); 820 821 /* Just two random numbers. */ 822 const uint64_t prng_init1 = (uint64_t)0X4E9A9DE6A35691CDULL; 823 const uint64_t prng_init2 = (uint64_t)0X7856E396B063C36EULL; 824 825 uint64_t prng1 = prng_init1; 826 uint64_t prng2 = prng_init2; 827 828 for (size_t i = 0; i < nbits; i++) { 829 bool bit1 = ((prng1 & (1ULL << (i % 64))) != 0); 830 bool bit2 = ((prng2 & (1ULL << (i % 64))) != 0); 831 832 if (bit1) { 833 fb_set(fb1, nbits, i); 834 } 835 if (bit2) { 836 fb_set(fb2, nbits, i); 837 } 838 839 if (i % 64 == 0) { 840 prng1 = prng_state_next_u64(prng1); 841 prng2 = prng_state_next_u64(prng2); 842 } 843 } 844 845 fb_op(fb_result, fb1, fb2, nbits); 846 847 /* Reset the prngs to replay them. */ 848 prng1 = prng_init1; 849 prng2 = prng_init2; 850 851 for (size_t i = 0; i < nbits; i++) { 852 bool bit1 = ((prng1 & (1ULL << (i % 64))) != 0); 853 bool bit2 = ((prng2 & (1ULL << (i % 64))) != 0); 854 855 /* Original bitmaps shouldn't change. */ 856 expect_b_eq(bit1, fb_get(fb1, nbits, i), "difference at bit %zu", i); 857 expect_b_eq(bit2, fb_get(fb2, nbits, i), "difference at bit %zu", i); 858 859 /* New one should be bitwise and. */ 860 expect_b_eq(op(bit1, bit2), fb_get(fb_result, nbits, i), 861 "difference at bit %zu", i); 862 863 /* Update the same way we did last time. */ 864 if (i % 64 == 0) { 865 prng1 = prng_state_next_u64(prng1); 866 prng2 = prng_state_next_u64(prng2); 867 } 868 } 869 870 free(fb1); 871 free(fb2); 872 free(fb_result); 873 } 874 875 static bool 876 binary_and(bool a, bool b) { 877 return a & b; 878 } 879 880 static void 881 do_test_bit_and(size_t nbits) { 882 do_test_bit_op(nbits, &binary_and, &fb_bit_and); 883 } 884 885 TEST_BEGIN(test_bit_and) { 886 #define NB(nbits) \ 887 do_test_bit_and(nbits); 888 NBITS_TAB 889 #undef NB 890 } 891 TEST_END 892 893 static bool 894 binary_or(bool a, bool b) { 895 return a | b; 896 } 897 898 static void 899 do_test_bit_or(size_t nbits) { 900 do_test_bit_op(nbits, &binary_or, &fb_bit_or); 901 } 902 903 TEST_BEGIN(test_bit_or) { 904 #define NB(nbits) \ 905 do_test_bit_or(nbits); 906 NBITS_TAB 907 #undef NB 908 } 909 TEST_END 910 911 static bool 912 binary_not(bool a, bool b) { 913 (void)b; 914 return !a; 915 } 916 917 static void 918 fb_bit_not_shim(fb_group_t *dst, fb_group_t *src1, fb_group_t *src2, 919 size_t nbits) { 920 (void)src2; 921 fb_bit_not(dst, src1, nbits); 922 } 923 924 static void 925 do_test_bit_not(size_t nbits) { 926 do_test_bit_op(nbits, &binary_not, &fb_bit_not_shim); 927 } 928 929 TEST_BEGIN(test_bit_not) { 930 #define NB(nbits) \ 931 do_test_bit_not(nbits); 932 NBITS_TAB 933 #undef NB 934 } 935 TEST_END 936 937 int 938 main(void) { 939 return test_no_reentrancy( 940 test_fb_init, 941 test_get_set_unset, 942 test_search_simple, 943 test_search_exhaustive, 944 test_range_simple, 945 test_empty_full, 946 test_iter_range_simple, 947 test_iter_range_exhaustive, 948 test_count_contiguous_simple, 949 test_count_contiguous, 950 test_count_alternating, 951 test_bit_and, 952 test_bit_or, 953 test_bit_not); 954 } 955