1 /*- 2 * Copyright (c) 2014 Spectra Logic Corporation 3 * Copyright (c) 2023 Klara, Inc. 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions, and the following disclaimer, 11 * without modification. 12 * 2. Redistributions in binary form must reproduce at minimum a disclaimer 13 * substantially similar to the "NO WARRANTY" disclaimer below 14 * ("Disclaimer") and any redistribution must be conditioned upon 15 * including a substantially similar Disclaimer requirement for further 16 * binary redistribution. 17 * 18 * NO WARRANTY 19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 21 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR 22 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 23 * HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 27 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING 28 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 29 * POSSIBILITY OF SUCH DAMAGES. 30 */ 31 32 #include <sys/param.h> 33 34 #include <bitstring.h> 35 #include <malloc_np.h> 36 37 #include <atf-c.h> 38 39 typedef void (testfunc_t)(bitstr_t *bstr, int nbits, const char *memloc); 40 41 static void 42 bitstring_run_stack_test(testfunc_t *test, int nbits) 43 { 44 bitstr_t bit_decl(bitstr, nbits); 45 46 test(bitstr, nbits, "stack"); 47 } 48 49 static void 50 bitstring_run_heap_test(testfunc_t *test, int nbits) 51 { 52 bitstr_t *bitstr = bit_alloc(nbits); 53 54 test(bitstr, nbits, "heap"); 55 free(bitstr); 56 } 57 58 static void 59 bitstring_test_runner(testfunc_t *test) 60 { 61 const int bitstr_sizes[] = { 62 0, 63 1, 64 _BITSTR_BITS - 1, 65 _BITSTR_BITS, 66 _BITSTR_BITS + 1, 67 2 * _BITSTR_BITS - 1, 68 2 * _BITSTR_BITS, 69 1023, 70 1024 71 }; 72 73 for (unsigned long i = 0; i < nitems(bitstr_sizes); i++) { 74 bitstring_run_stack_test(test, bitstr_sizes[i]); 75 bitstring_run_heap_test(test, bitstr_sizes[i]); 76 } 77 } 78 79 #define BITSTRING_TC_DEFINE(name) \ 80 ATF_TC_WITHOUT_HEAD(name); \ 81 static testfunc_t name ## _test; \ 82 \ 83 ATF_TC_BODY(name, tc) \ 84 { \ 85 bitstring_test_runner(name ## _test); \ 86 } \ 87 \ 88 static void \ 89 name ## _test(bitstr_t *bitstr, int nbits, const char *memloc) 90 91 #define BITSTRING_TC_ADD(tp, name) \ 92 do { \ 93 ATF_TP_ADD_TC(tp, name); \ 94 } while (0) 95 96 ATF_TC_WITHOUT_HEAD(bitstr_in_struct); 97 ATF_TC_BODY(bitstr_in_struct, tc) 98 { 99 struct bitstr_containing_struct { 100 bitstr_t bit_decl(bitstr, 8); 101 } test_struct; 102 103 bit_nclear(test_struct.bitstr, 0, 8); 104 } 105 106 ATF_TC_WITHOUT_HEAD(bitstr_size); 107 ATF_TC_BODY(bitstr_size, tc) 108 { 109 size_t sob = sizeof(bitstr_t); 110 111 ATF_CHECK_EQ(0, bitstr_size(0)); 112 ATF_CHECK_EQ(sob, bitstr_size(1)); 113 ATF_CHECK_EQ(sob, bitstr_size(sob * 8)); 114 ATF_CHECK_EQ(2 * sob, bitstr_size(sob * 8 + 1)); 115 } 116 117 BITSTRING_TC_DEFINE(bit_set) 118 /* bitstr_t *bitstr, int nbits, const char *memloc */ 119 { 120 memset(bitstr, 0, bitstr_size(nbits)); 121 122 for (int i = 0; i < nbits; i++) { 123 bit_set(bitstr, i); 124 125 for (int j = 0; j < nbits; j++) { 126 ATF_REQUIRE_MSG(bit_test(bitstr, j) == (j == i) ? 1 : 0, 127 "bit_set_%d_%s: Failed on bit %d", 128 nbits, memloc, i); 129 } 130 131 bit_clear(bitstr, i); 132 } 133 } 134 135 BITSTRING_TC_DEFINE(bit_clear) 136 /* bitstr_t *bitstr, int nbits, const char *memloc */ 137 { 138 int i, j; 139 140 memset(bitstr, 0xFF, bitstr_size(nbits)); 141 for (i = 0; i < nbits; i++) { 142 bit_clear(bitstr, i); 143 144 for (j = 0; j < nbits; j++) { 145 ATF_REQUIRE_MSG(bit_test(bitstr, j) == (j == i) ? 0 : 1, 146 "bit_clear_%d_%s: Failed on bit %d", 147 nbits, memloc, i); 148 } 149 150 bit_set(bitstr, i); 151 } 152 } 153 154 BITSTRING_TC_DEFINE(bit_ffs) 155 /* bitstr_t *bitstr, int nbits, const char *memloc */ 156 { 157 int i; 158 int found_set_bit; 159 160 memset(bitstr, 0, bitstr_size(nbits)); 161 bit_ffs(bitstr, nbits, &found_set_bit); 162 ATF_REQUIRE_MSG(found_set_bit == -1, 163 "bit_ffs_%d_%s: Failed all clear bits.", nbits, memloc); 164 165 for (i = 0; i < nbits; i++) { 166 memset(bitstr, 0xFF, bitstr_size(nbits)); 167 if (i > 0) 168 bit_nclear(bitstr, 0, i - 1); 169 170 bit_ffs(bitstr, nbits, &found_set_bit); 171 ATF_REQUIRE_MSG(found_set_bit == i, 172 "bit_ffs_%d_%s: Failed on bit %d, Result %d", 173 nbits, memloc, i, found_set_bit); 174 } 175 } 176 177 BITSTRING_TC_DEFINE(bit_ffc) 178 /* bitstr_t *bitstr, int nbits, const char *memloc */ 179 { 180 int i; 181 int found_clear_bit; 182 183 memset(bitstr, 0xFF, bitstr_size(nbits)); 184 bit_ffc(bitstr, nbits, &found_clear_bit); 185 ATF_REQUIRE_MSG(found_clear_bit == -1, 186 "bit_ffc_%d_%s: Failed all set bits.", nbits, memloc); 187 188 for (i = 0; i < nbits; i++) { 189 memset(bitstr, 0, bitstr_size(nbits)); 190 if (i > 0) 191 bit_nset(bitstr, 0, i - 1); 192 193 bit_ffc(bitstr, nbits, &found_clear_bit); 194 ATF_REQUIRE_MSG(found_clear_bit == i, 195 "bit_ffc_%d_%s: Failed on bit %d, Result %d", 196 nbits, memloc, i, found_clear_bit); 197 } 198 } 199 200 BITSTRING_TC_DEFINE(bit_ffs_at) 201 /* bitstr_t *bitstr, int nbits, const char *memloc */ 202 { 203 int i; 204 int found_set_bit; 205 206 memset(bitstr, 0xFF, bitstr_size(nbits)); 207 for (i = 0; i < nbits; i++) { 208 bit_ffs_at(bitstr, i, nbits, &found_set_bit); 209 ATF_REQUIRE_MSG(found_set_bit == i, 210 "bit_ffs_at_%d_%s: Failed on bit %d, Result %d", 211 nbits, memloc, i, found_set_bit); 212 } 213 214 memset(bitstr, 0, bitstr_size(nbits)); 215 for (i = 0; i < nbits; i++) { 216 bit_ffs_at(bitstr, i, nbits, &found_set_bit); 217 ATF_REQUIRE_MSG(found_set_bit == -1, 218 "bit_ffs_at_%d_%s: Failed on bit %d, Result %d", 219 nbits, memloc, i, found_set_bit); 220 } 221 222 memset(bitstr, 0x55, bitstr_size(nbits)); 223 for (i = 0; i < nbits; i++) { 224 bit_ffs_at(bitstr, i, nbits, &found_set_bit); 225 if (i == nbits - 1 && (nbits & 1) == 0) { 226 ATF_REQUIRE_MSG(found_set_bit == -1, 227 "bit_ffs_at_%d_%s: Failed on bit %d, Result %d", 228 nbits, memloc, i, found_set_bit); 229 } else { 230 ATF_REQUIRE_MSG(found_set_bit == i + (i & 1), 231 "bit_ffs_at_%d_%s: Failed on bit %d, Result %d", 232 nbits, memloc, i, found_set_bit); 233 } 234 } 235 236 memset(bitstr, 0xAA, bitstr_size(nbits)); 237 for (i = 0; i < nbits; i++) { 238 bit_ffs_at(bitstr, i, nbits, &found_set_bit); 239 if (i == nbits - 1 && (nbits & 1) != 0) { 240 ATF_REQUIRE_MSG(found_set_bit == -1, 241 "bit_ffs_at_%d_%s: Failed on bit %d, Result %d", 242 nbits, memloc, i, found_set_bit); 243 } else { 244 ATF_REQUIRE_MSG( 245 found_set_bit == i + ((i & 1) ? 0 : 1), 246 "bit_ffs_at_%d_%s: Failed on bit %d, Result %d", 247 nbits, memloc, i, found_set_bit); 248 } 249 } 250 251 /* Pass a start value beyond the size of the bit string */ 252 bit_ffs_at(bitstr, nbits, nbits, &found_set_bit); 253 ATF_REQUIRE_MSG(found_set_bit == -1, 254 "bit_ffs_at_%d_%s: Failed with high start value of %d, Result %d", 255 nbits, memloc, nbits, found_set_bit); 256 257 bit_ffs_at(bitstr, nbits + 3, nbits, &found_set_bit); 258 ATF_REQUIRE_MSG(found_set_bit == -1, 259 "bit_ffs_at_%d_%s: Failed with high start value of %d, Result %d", 260 nbits, memloc, nbits + 3, found_set_bit); 261 } 262 263 BITSTRING_TC_DEFINE(bit_ffc_at) 264 /* bitstr_t *bitstr, int nbits, const char *memloc */ 265 { 266 int i, found_clear_bit; 267 268 memset(bitstr, 0, bitstr_size(nbits)); 269 for (i = 0; i < nbits; i++) { 270 bit_ffc_at(bitstr, i, nbits, &found_clear_bit); 271 ATF_REQUIRE_MSG(found_clear_bit == i, 272 "bit_ffc_at_%d_%s: Failed on bit %d, Result %d", 273 nbits, memloc, i, found_clear_bit); 274 } 275 276 memset(bitstr, 0xFF, bitstr_size(nbits)); 277 for (i = 0; i < nbits; i++) { 278 bit_ffc_at(bitstr, i, nbits, &found_clear_bit); 279 ATF_REQUIRE_MSG(found_clear_bit == -1, 280 "bit_ffc_at_%d_%s: Failed on bit %d, Result %d", 281 nbits, memloc, i, found_clear_bit); 282 } 283 284 memset(bitstr, 0x55, bitstr_size(nbits)); 285 for (i = 0; i < nbits; i++) { 286 bit_ffc_at(bitstr, i, nbits, &found_clear_bit); 287 if (i == nbits - 1 && (nbits & 1) != 0) { 288 ATF_REQUIRE_MSG(found_clear_bit == -1, 289 "bit_ffc_at_%d_%s: Failed on bit %d, Result %d", 290 nbits, memloc, i, found_clear_bit); 291 } else { 292 ATF_REQUIRE_MSG( 293 found_clear_bit == i + ((i & 1) ? 0 : 1), 294 "bit_ffc_at_%d_%s: Failed on bit %d, Result %d", 295 nbits, memloc, i, found_clear_bit); 296 } 297 } 298 299 memset(bitstr, 0xAA, bitstr_size(nbits)); 300 for (i = 0; i < nbits; i++) { 301 bit_ffc_at(bitstr, i, nbits, &found_clear_bit); 302 if (i == nbits - 1 && (nbits & 1) == 0) { 303 ATF_REQUIRE_MSG(found_clear_bit == -1, 304 "bit_ffc_at_%d_%s: Failed on bit %d, Result %d", 305 nbits, memloc, i, found_clear_bit); 306 } else { 307 ATF_REQUIRE_MSG(found_clear_bit == i + (i & 1), 308 "bit_ffc_at_%d_%s: Failed on bit %d, Result %d", 309 nbits, memloc, i, found_clear_bit); 310 } 311 } 312 313 /* Pass a start value beyond the size of the bit string */ 314 bit_ffc_at(bitstr, nbits, nbits, &found_clear_bit); 315 ATF_REQUIRE_MSG(found_clear_bit == -1, 316 "bit_ffc_at_%d_%s: Failed with high start value, Result %d", 317 nbits, memloc, found_clear_bit); 318 319 bit_ffc_at(bitstr, nbits + 3, nbits, &found_clear_bit); 320 ATF_REQUIRE_MSG(found_clear_bit == -1, 321 "bit_ffc_at_%d_%s: Failed with high start value of %d, Result %d", 322 nbits, memloc, nbits + 3, found_clear_bit); 323 } 324 325 BITSTRING_TC_DEFINE(bit_ffc_area_at_all_or_nothing) 326 /* bitstr_t *bitstr, int nbits, const char *memloc */ 327 { 328 int found; 329 330 memset(bitstr, 0, bitstr_size(nbits)); 331 if (nbits % _BITSTR_BITS != 0) 332 bit_nset(bitstr, nbits, roundup2(nbits, _BITSTR_BITS) - 1); 333 334 for (int start = 0; start < nbits; start++) { 335 for (int size = 1; size < nbits - start; size++) { 336 bit_ffc_area_at(bitstr, start, nbits, size, &found); 337 ATF_REQUIRE_EQ_MSG(start, found, 338 "bit_ffc_area_at_%d_%s: " 339 "Did not find %d clear bits at %d", 340 nbits, memloc, size, start); 341 } 342 } 343 344 memset(bitstr, 0xff, bitstr_size(nbits)); 345 if (nbits % _BITSTR_BITS != 0) 346 bit_nclear(bitstr, nbits, roundup2(nbits, _BITSTR_BITS) - 1); 347 348 for (int start = 0; start < nbits; start++) { 349 for (int size = 1; size < nbits - start; size++) { 350 bit_ffc_area_at(bitstr, start, nbits, size, &found); 351 ATF_REQUIRE_EQ_MSG(-1, found, 352 "bit_ffc_area_at_%d_%s: " 353 "Found %d clear bits at %d", 354 nbits, memloc, size, start); 355 } 356 } 357 } 358 359 BITSTRING_TC_DEFINE(bit_ffs_area_at_all_or_nothing) 360 /* bitstr_t *bitstr, int nbits, const char *memloc */ 361 { 362 int found; 363 364 memset(bitstr, 0, bitstr_size(nbits)); 365 if (nbits % _BITSTR_BITS != 0) 366 bit_nset(bitstr, nbits, roundup2(nbits, _BITSTR_BITS) - 1); 367 368 for (int start = 0; start < nbits; start++) { 369 for (int size = 1; size < nbits - start; size++) { 370 bit_ffs_area_at(bitstr, start, nbits, size, &found); 371 ATF_REQUIRE_EQ_MSG(-1, found, 372 "bit_ffs_area_at_%d_%s: " 373 "Found %d set bits at %d", 374 nbits, memloc, size, start); 375 } 376 } 377 378 memset(bitstr, 0xff, bitstr_size(nbits)); 379 if (nbits % _BITSTR_BITS != 0) 380 bit_nclear(bitstr, nbits, roundup2(nbits, _BITSTR_BITS) - 1); 381 382 for (int start = 0; start < nbits; start++) { 383 for (int size = 1; size < nbits - start; size++) { 384 bit_ffs_area_at(bitstr, start, nbits, size, &found); 385 ATF_REQUIRE_EQ_MSG(start, found, 386 "bit_ffs_area_at_%d_%s: " 387 "Did not find %d set bits at %d", 388 nbits, memloc, size, start); 389 } 390 } 391 } 392 393 ATF_TC_WITHOUT_HEAD(bit_ffs_area); 394 ATF_TC_BODY(bit_ffs_area, tc) 395 { 396 const int nbits = 72; 397 bitstr_t bit_decl(bitstr, nbits); 398 int location; 399 400 memset(bitstr, 0, bitstr_size(nbits)); 401 402 bit_nset(bitstr, 5, 6); 403 404 location = 0; 405 bit_ffs_area(bitstr, nbits, 3, &location); 406 ATF_REQUIRE_EQ_MSG(-1, location, 407 "bit_ffs_area: found location of size 3 when only 2 bits are set"); 408 ATF_REQUIRE_EQ_MSG(0, bit_ntest(bitstr, 5, 7, 1), 409 "bit_ntest: found location of size 3 when only 2 bits are set"); 410 411 bit_set(bitstr, 7); 412 413 location = 0; 414 bit_ffs_area(bitstr, nbits, 3, &location); 415 ATF_REQUIRE_EQ_MSG(5, location, 416 "bit_ffs_area: failed to find location of size 3 %d", location); 417 ATF_REQUIRE_EQ_MSG(1, bit_ntest(bitstr, 5, 7, 1), 418 "bit_ntest: failed to find all 3 bits set"); 419 420 bit_set(bitstr, 8); 421 422 location = 0; 423 bit_ffs_area(bitstr, nbits, 3, &location); 424 ATF_REQUIRE_EQ_MSG(5, location, 425 "bit_ffs_area: failed to find location of size 3"); 426 427 location = 0; 428 bit_ffs_area_at(bitstr, 2, nbits, 3, &location); 429 ATF_REQUIRE_EQ_MSG(5, location, 430 "bit_ffs_area_at: failed to find location of size 3"); 431 432 location = 0; 433 bit_ffs_area_at(bitstr, 6, nbits, 3, &location); 434 ATF_REQUIRE_EQ_MSG(6, location, 435 "bit_ffs_area_at: failed to find location of size 3"); 436 437 location = 0; 438 bit_ffs_area_at(bitstr, 8, nbits, 3, &location); 439 ATF_REQUIRE_EQ_MSG(-1, location, 440 "bit_ffs_area_at: found invalid location"); 441 442 bit_nset(bitstr, 69, 71); 443 444 location = 0; 445 bit_ffs_area_at(bitstr, 8, nbits, 3, &location); 446 ATF_REQUIRE_EQ_MSG(69, location, 447 "bit_ffs_area_at: failed to find location of size 3"); 448 449 location = 0; 450 bit_ffs_area_at(bitstr, 69, nbits, 3, &location); 451 ATF_REQUIRE_EQ_MSG(69, location, 452 "bit_ffs_area_at: failed to find location of size 3"); 453 454 location = 0; 455 bit_ffs_area_at(bitstr, 70, nbits, 3, &location); 456 ATF_REQUIRE_EQ_MSG(-1, location, 457 "bit_ffs_area_at: found invalid location"); 458 459 location = 0; 460 bit_ffs_area_at(bitstr, 72, nbits, 3, &location); 461 ATF_REQUIRE_EQ_MSG(-1, location, 462 "bit_ffs_area_at: found invalid location"); 463 464 bit_nset(bitstr, 59, 67); 465 466 location = 0; 467 bit_ffs_area(bitstr, nbits, 9, &location); 468 ATF_REQUIRE_EQ_MSG(59, location, 469 "bit_ffs_area: failed to find location of size 9"); 470 471 location = 0; 472 bit_ffs_area(bitstr, nbits, 10, &location); 473 ATF_REQUIRE_EQ_MSG(-1, location, 474 "bit_ffs_area: found invalid location"); 475 } 476 477 ATF_TC_WITHOUT_HEAD(bit_ffc_area); 478 ATF_TC_BODY(bit_ffc_area, tc) 479 { 480 const int nbits = 80; 481 bitstr_t bit_decl(bitstr, nbits); 482 int location; 483 484 /* set all bits */ 485 memset(bitstr, 0xFF, bitstr_size(nbits)); 486 487 bit_clear(bitstr, 7); 488 bit_clear(bitstr, 8); 489 490 location = 0; 491 bit_ffc_area(bitstr, nbits, 3, &location); 492 ATF_REQUIRE_EQ_MSG(-1, location, 493 "bit_ffc_area: found location of size 3 when only 2 bits are set"); 494 495 bit_clear(bitstr, 9); 496 497 location = 0; 498 bit_ffc_area(bitstr, nbits, 3, &location); 499 ATF_REQUIRE_EQ_MSG(7, location, 500 "bit_ffc_area: failed to find location of size 3"); 501 502 bit_clear(bitstr, 10); 503 504 location = 0; 505 bit_ffc_area(bitstr, nbits, 3, &location); 506 ATF_REQUIRE_EQ_MSG(7, location, 507 "bit_ffc_area: failed to find location of size 3"); 508 509 location = 0; 510 bit_ffc_area_at(bitstr, 2, nbits, 3, &location); 511 ATF_REQUIRE_EQ_MSG(7, location, 512 "bit_ffc_area_at: failed to find location of size 3"); 513 514 location = 0; 515 bit_ffc_area_at(bitstr, 8, nbits, 3, &location); 516 ATF_REQUIRE_EQ_MSG(8, location, 517 "bit_ffc_area_at: failed to find location of size 3"); 518 519 location = 0; 520 bit_ffc_area_at(bitstr, 9, nbits, 3, &location); 521 ATF_REQUIRE_EQ_MSG(-1, location, 522 "bit_ffc_area_at: found invalid bit location"); 523 524 bit_clear(bitstr, 77); 525 bit_clear(bitstr, 78); 526 bit_clear(bitstr, 79); 527 528 location = 0; 529 bit_ffc_area_at(bitstr, 12, nbits, 3, &location); 530 ATF_REQUIRE_EQ_MSG(77, location, 531 "bit_ffc_area_at: failed to find location of size 3"); 532 533 location = 0; 534 bit_ffc_area_at(bitstr, 77, nbits, 3, &location); 535 ATF_REQUIRE_EQ_MSG(77, location, 536 "bit_ffc_area_at: failed to find location of size 3"); 537 538 location = 0; 539 bit_ffc_area_at(bitstr, 78, nbits, 3, &location); 540 ATF_REQUIRE_EQ_MSG(-1, location, 541 "bit_ffc_area_at: found invalid location"); 542 543 location = 0; 544 bit_ffc_area_at(bitstr, 85, nbits, 3, &location); 545 ATF_REQUIRE_EQ_MSG(-1, location, 546 "bit_ffc_area_at: found invalid location"); 547 } 548 549 BITSTRING_TC_DEFINE(bit_nclear) 550 /* bitstr_t *bitstr, int nbits, const char *memloc */ 551 { 552 int i, j; 553 int found_set_bit; 554 int found_clear_bit; 555 556 for (i = 0; i < nbits; i++) { 557 for (j = i; j < nbits; j++) { 558 memset(bitstr, 0xFF, bitstr_size(nbits)); 559 bit_nclear(bitstr, i, j); 560 561 bit_ffc(bitstr, nbits, &found_clear_bit); 562 ATF_REQUIRE_MSG( 563 found_clear_bit == i, 564 "bit_nclear_%d_%d_%d%s: Failed with result %d", 565 nbits, i, j, memloc, found_clear_bit); 566 567 bit_ffs_at(bitstr, i, nbits, &found_set_bit); 568 ATF_REQUIRE_MSG( 569 (j + 1 < nbits) ? found_set_bit == j + 1 : -1, 570 "bit_nset_%d_%d_%d%s: Failed with result %d", 571 nbits, i, j, memloc, found_set_bit); 572 } 573 } 574 } 575 576 BITSTRING_TC_DEFINE(bit_nset) 577 /* bitstr_t *bitstr, int nbits, const char *memloc */ 578 { 579 int i, j; 580 int found_set_bit; 581 int found_clear_bit; 582 583 for (i = 0; i < nbits; i++) { 584 for (j = i; j < nbits; j++) { 585 memset(bitstr, 0, bitstr_size(nbits)); 586 bit_nset(bitstr, i, j); 587 588 bit_ffs(bitstr, nbits, &found_set_bit); 589 ATF_REQUIRE_MSG( 590 found_set_bit == i, 591 "bit_nset_%d_%d_%d%s: Failed with result %d", 592 nbits, i, j, memloc, found_set_bit); 593 594 bit_ffc_at(bitstr, i, nbits, &found_clear_bit); 595 ATF_REQUIRE_MSG( 596 (j + 1 < nbits) ? found_clear_bit == j + 1 : -1, 597 "bit_nset_%d_%d_%d%s: Failed with result %d", 598 nbits, i, j, memloc, found_clear_bit); 599 } 600 } 601 } 602 603 BITSTRING_TC_DEFINE(bit_count) 604 /* bitstr_t *bitstr, int nbits, const char *memloc */ 605 { 606 int result, s, e, expected; 607 608 /* Empty bitstr */ 609 memset(bitstr, 0, bitstr_size(nbits)); 610 bit_count(bitstr, 0, nbits, &result); 611 ATF_CHECK_MSG(0 == result, 612 "bit_count_%d_%s_%s: Failed with result %d", 613 nbits, "clear", memloc, result); 614 615 /* Full bitstr */ 616 memset(bitstr, 0xFF, bitstr_size(nbits)); 617 bit_count(bitstr, 0, nbits, &result); 618 ATF_CHECK_MSG(nbits == result, 619 "bit_count_%d_%s_%s: Failed with result %d", 620 nbits, "set", memloc, result); 621 622 /* Invalid _start value */ 623 memset(bitstr, 0xFF, bitstr_size(nbits)); 624 bit_count(bitstr, nbits, nbits, &result); 625 ATF_CHECK_MSG(0 == result, 626 "bit_count_%d_%s_%s: Failed with result %d", 627 nbits, "invalid_start", memloc, result); 628 629 /* Alternating bitstr, starts with 0 */ 630 memset(bitstr, 0xAA, bitstr_size(nbits)); 631 bit_count(bitstr, 0, nbits, &result); 632 ATF_CHECK_MSG(nbits / 2 == result, 633 "bit_count_%d_%s_%d_%s: Failed with result %d", 634 nbits, "alternating", 0, memloc, result); 635 636 /* Alternating bitstr, starts with 1 */ 637 memset(bitstr, 0x55, bitstr_size(nbits)); 638 bit_count(bitstr, 0, nbits, &result); 639 ATF_CHECK_MSG((nbits + 1) / 2 == result, 640 "bit_count_%d_%s_%d_%s: Failed with result %d", 641 nbits, "alternating", 1, memloc, result); 642 643 /* Varying start location */ 644 memset(bitstr, 0xAA, bitstr_size(nbits)); 645 for (s = 0; s < nbits; s++) { 646 expected = s % 2 == 0 ? (nbits - s) / 2 : (nbits - s + 1) / 2; 647 bit_count(bitstr, s, nbits, &result); 648 ATF_CHECK_MSG(expected == result, 649 "bit_count_%d_%s_%d_%s: Failed with result %d", 650 nbits, "vary_start", s, memloc, result); 651 } 652 653 /* Varying end location */ 654 memset(bitstr, 0xAA, bitstr_size(nbits)); 655 for (e = 0; e < nbits; e++) { 656 bit_count(bitstr, 0, e, &result); 657 ATF_CHECK_MSG(e / 2 == result, 658 "bit_count_%d_%s_%d_%s: Failed with result %d", 659 nbits, "vary_end", e, memloc, result); 660 } 661 662 } 663 664 BITSTRING_TC_DEFINE(bit_foreach) 665 /* bitstr_t *bitstr, int nbits, const char *memloc */ 666 { 667 int i, set_bit; 668 669 /* Empty bitstr */ 670 memset(bitstr, 0x00, bitstr_size(nbits)); 671 bit_foreach (bitstr, nbits, set_bit) { 672 atf_tc_fail("bit_foreach_%d_%s_%s: Failed at location %d", 673 nbits, "clear", memloc, set_bit); 674 } 675 676 /* Full bitstr */ 677 i = 0; 678 memset(bitstr, 0xFF, bitstr_size(nbits)); 679 bit_foreach(bitstr, nbits, set_bit) { 680 ATF_REQUIRE_MSG(set_bit == i, 681 "bit_foreach_%d_%s_%s: Failed on turn %d at location %d", 682 nbits, "set", memloc, i, set_bit); 683 i++; 684 } 685 ATF_REQUIRE_MSG(i == nbits, 686 "bit_foreach_%d_%s_%s: Invalid number of turns %d", 687 nbits, "set", memloc, i); 688 689 /* Alternating bitstr, starts with 0 */ 690 i = 0; 691 memset(bitstr, 0xAA, bitstr_size(nbits)); 692 bit_foreach(bitstr, nbits, set_bit) { 693 ATF_REQUIRE_MSG(set_bit == i * 2 + 1, 694 "bit_foreach_%d_%s_%d_%s: " 695 "Failed on turn %d at location %d", 696 nbits, "alternating", 0, memloc, i, set_bit); 697 i++; 698 } 699 ATF_REQUIRE_MSG(i == nbits / 2, 700 "bit_foreach_%d_%s_%d_%s: Invalid number of turns %d", 701 nbits, "alternating", 0, memloc, i); 702 703 /* Alternating bitstr, starts with 1 */ 704 i = 0; 705 memset(bitstr, 0x55, bitstr_size(nbits)); 706 bit_foreach(bitstr, nbits, set_bit) { 707 ATF_REQUIRE_MSG(set_bit == i * 2, 708 "bit_foreach_%d_%s_%d_%s: " 709 "Failed on turn %d at location %d", 710 nbits, "alternating", 1, memloc, i, set_bit); 711 i++; 712 } 713 ATF_REQUIRE_MSG(i == (nbits + 1) / 2, 714 "bit_foreach_%d_%s_%d_%s: Invalid number of turns %d", 715 nbits, "alternating", 1, memloc, i); 716 } 717 718 BITSTRING_TC_DEFINE(bit_foreach_at) 719 /* bitstr_t *bitstr, int nbits, const char *memloc */ 720 { 721 int i, s, e, set_bit; 722 723 /* Invalid _start value */ 724 memset(bitstr, 0xFF, bitstr_size(nbits)); 725 bit_foreach_at(bitstr, nbits, nbits, set_bit) { 726 atf_tc_fail("bit_foreach_at_%d_%s_%s: Failed at location %d", 727 nbits, "invalid_start", memloc, set_bit); 728 } 729 730 /* Varying start location */ 731 memset(bitstr, 0xAA, bitstr_size(nbits)); 732 for (s = 0; s < nbits; s++) { 733 i = 0; 734 bit_foreach_at(bitstr, s, nbits, set_bit) { 735 ATF_REQUIRE_MSG(set_bit == (i + s / 2) * 2 + 1, 736 "bit_foreach_at_%d_%s_%d_%s: " 737 "Failed on turn %d at location %d", 738 nbits, "vary_start", s, memloc, i, set_bit); 739 i++; 740 } 741 ATF_REQUIRE_MSG(i == nbits / 2 - s / 2, 742 "bit_foreach_at_%d_%s_%d_%s: Invalid number of turns %d", 743 nbits, "vary_start", s, memloc, i); 744 } 745 746 /* Varying end location */ 747 memset(bitstr, 0xAA, bitstr_size(nbits)); 748 for (e = 0; e < nbits; e++) { 749 i = 0; 750 bit_foreach_at(bitstr, 0, e, set_bit) { 751 ATF_REQUIRE_MSG(set_bit == i * 2 + 1, 752 "bit_foreach_at_%d_%s_%d_%s: " 753 "Failed on turn %d at location %d", 754 nbits, "vary_end", e, memloc, i, set_bit); 755 i++; 756 } 757 ATF_REQUIRE_MSG(i == e / 2, 758 "bit_foreach_at_%d_%s_%d_%s: Invalid number of turns %d", 759 nbits, "vary_end", e, memloc, i); 760 } 761 } 762 763 BITSTRING_TC_DEFINE(bit_foreach_unset) 764 /* bitstr_t *bitstr, int nbits, const char *memloc */ 765 { 766 int i, unset_bit; 767 768 /* Empty bitstr */ 769 i = 0; 770 memset(bitstr, 0, bitstr_size(nbits)); 771 bit_foreach_unset(bitstr, nbits, unset_bit) { 772 ATF_REQUIRE_MSG(unset_bit == i, 773 "bit_foreach_unset_%d_%s_%s: " 774 "Failed on turn %d at location %d", 775 nbits, "clear", memloc, i, unset_bit); 776 i++; 777 } 778 ATF_REQUIRE_MSG(i == nbits, 779 "bit_foreach_unset_%d_%s_%s: Invalid number of turns %d", 780 nbits, "set", memloc, i); 781 782 /* Full bitstr */ 783 memset(bitstr, 0xFF, bitstr_size(nbits)); 784 bit_foreach_unset(bitstr, nbits, unset_bit) { 785 atf_tc_fail("bit_foreach_unset_%d_%s_%s: " 786 "Failed at location %d", 787 nbits, "set", memloc, unset_bit); 788 } 789 790 /* Alternating bitstr, starts with 0 */ 791 i = 0; 792 memset(bitstr, 0xAA, bitstr_size(nbits)); 793 bit_foreach_unset(bitstr, nbits, unset_bit) { 794 ATF_REQUIRE_MSG(unset_bit == i * 2, 795 "bit_foreach_unset_%d_%s_%d_%s: " 796 "Failed on turn %d at location %d", 797 nbits, "alternating", 0, memloc, i, unset_bit); 798 i++; 799 } 800 ATF_REQUIRE_MSG(i == (nbits + 1) / 2, 801 "bit_foreach_unset_%d_%s_%d_%s: Invalid number of turns %d", 802 nbits, "alternating", 0, memloc, i); 803 804 /* Alternating bitstr, starts with 1 */ 805 i = 0; 806 memset(bitstr, 0x55, bitstr_size(nbits)); 807 bit_foreach_unset(bitstr, nbits, unset_bit) { 808 ATF_REQUIRE_MSG(unset_bit == i * 2 + 1, 809 "bit_foreach_unset_%d_%s_%d_%s: " 810 "Failed on turn %d at location %d", 811 nbits, "alternating", 1, memloc, i, unset_bit); 812 i++; 813 } 814 ATF_REQUIRE_MSG(i == nbits / 2, 815 "bit_foreach_unset_%d_%s_%d_%s: Invalid number of turns %d", 816 nbits, "alternating", 1, memloc, i); 817 } 818 819 BITSTRING_TC_DEFINE(bit_foreach_unset_at) 820 /* bitstr_t *bitstr, int nbits, const char *memloc */ 821 { 822 int i, s, e, unset_bit; 823 824 /* Invalid _start value */ 825 memset(bitstr, 0, bitstr_size(nbits)); 826 bit_foreach_unset_at(bitstr, nbits, nbits, unset_bit) { 827 atf_tc_fail("bit_foreach_unset_at_%d_%s_%s: " 828 "Failed at location %d", 829 nbits, "invalid_start", memloc, unset_bit); 830 } 831 832 /* Varying start location */ 833 memset(bitstr, 0xAA, bitstr_size(nbits)); 834 for (s = 0; s < nbits; s++) { 835 i = 0; 836 bit_foreach_unset_at(bitstr, s, nbits, unset_bit) { 837 ATF_REQUIRE_MSG(unset_bit == (i + (s + 1) / 2) * 2, 838 "bit_foreach_unset_at_%d_%s_%d_%s: " 839 "Failed on turn %d at location %d", 840 nbits, "vary_start", s, memloc, i, unset_bit); 841 i++; 842 } 843 ATF_REQUIRE_MSG(i == (nbits + 1) / 2 - (s + 1) / 2, 844 "bit_foreach_unset_at_%d_%s_%d_%s: " 845 "Invalid number of turns %d", 846 nbits, "vary_start", s, memloc, i); 847 } 848 849 /* Varying end location */ 850 memset(bitstr, 0xAA, bitstr_size(nbits)); 851 for (e = 0; e < nbits; e++) { 852 i = 0; 853 bit_foreach_unset_at(bitstr, 0, e, unset_bit) { 854 ATF_REQUIRE_MSG(unset_bit == i * 2, 855 "bit_foreach_unset_at_%d_%s_%d_%s: " 856 "Failed on turn %d at location %d", 857 nbits, "vary_end", e, memloc, i, unset_bit); 858 i++; 859 } 860 ATF_REQUIRE_MSG(i == (e + 1) / 2, 861 "bit_foreach_unset_at_%d_%s_%d_%s: " 862 "Invalid number of turns %d", 863 nbits, "vary_end", e, memloc, i); 864 } 865 } 866 867 /* 868 * Perform various tests on large bit strings. We can't simply add larger 869 * sizes to bitstring_runner as most of the existing tests are exhaustive 870 * and would take forever to run for large values of nbits. 871 * 872 * On 32-bit platforms, we use nbits = SSIZE_MAX (2147483647) bits, which 873 * is the largest we can hope to support; on 64-bit platforms, we use 874 * nbits = INT_MAX + 30 (2147483677), which is small enough to be 875 * practicable yet large enough to reveal arithmetic overflow bugs. 876 */ 877 ATF_TC_WITHOUT_HEAD(bitstr_large); 878 ATF_TC_BODY(bitstr_large, tc) 879 { 880 size_t nbits = INT_MAX < SSIZE_MAX ? (size_t)INT_MAX + 30 : SSIZE_MAX; 881 size_t early = 5, late = nbits - 5; 882 ssize_t fc, fs; 883 bitstr_t *b; 884 885 /* Check for overflow in size calculation */ 886 ATF_REQUIRE(nbits >= (size_t)INT_MAX); 887 ATF_REQUIRE(bitstr_size(nbits) >= nbits / 8); 888 889 /* Allocate the bit string */ 890 ATF_REQUIRE(b = bit_alloc(nbits)); 891 892 /* Check that we allocated enough */ 893 ATF_REQUIRE(malloc_usable_size(b) >= bitstr_size(nbits)); 894 895 /* Check ffc, ffs on all-zeroes string */ 896 bit_ffc(b, nbits, &fc); 897 ATF_CHECK_EQ(0L, fc); 898 bit_ffs(b, nbits, &fs); 899 ATF_CHECK_EQ(-1L, fs); 900 901 /* Set, test, and clear an early bit */ 902 bit_set(b, early); 903 bit_ffs(b, nbits, &fs); 904 ATF_CHECK_EQ((ssize_t)early, fs); 905 ATF_CHECK_EQ(0, bit_test(b, early - 1)); 906 ATF_CHECK(bit_test(b, early) != 0); 907 ATF_CHECK_EQ(0, bit_test(b, early + 1)); 908 bit_clear(b, early); 909 ATF_CHECK_EQ(0, bit_test(b, early)); 910 911 /* Set, test, and clear an early bit range */ 912 bit_nset(b, early - 1, early + 1); 913 bit_ffs(b, nbits, &fs); 914 ATF_CHECK_EQ((ssize_t)early - 1, fs); 915 ATF_CHECK_EQ(0, bit_test(b, early - 2)); 916 ATF_CHECK(bit_test(b, early - 1)); 917 ATF_CHECK(bit_test(b, early)); 918 ATF_CHECK(bit_test(b, early + 1)); 919 ATF_CHECK_EQ(0, bit_test(b, early + 2)); 920 bit_nclear(b, early - 1, early + 1); 921 ATF_CHECK_EQ(0, bit_test(b, early - 1)); 922 ATF_CHECK_EQ(0, bit_test(b, early)); 923 ATF_CHECK_EQ(0, bit_test(b, early + 1)); 924 925 /* Set, test, and clear a late bit */ 926 bit_set(b, late); 927 bit_ffs(b, nbits, &fs); 928 ATF_CHECK_EQ((ssize_t)late, fs); 929 ATF_CHECK_EQ(0, bit_test(b, late - 1)); 930 ATF_CHECK(bit_test(b, late) != 0); 931 ATF_CHECK_EQ(0, bit_test(b, late + 1)); 932 bit_clear(b, late); 933 ATF_CHECK_EQ(0, bit_test(b, late)); 934 935 /* Set, test, and clear a late bit range */ 936 bit_nset(b, late - 1, late + 1); 937 bit_ffs(b, nbits, &fs); 938 ATF_CHECK_EQ((ssize_t)late - 1, fs); 939 ATF_CHECK_EQ(0, bit_test(b, late - 2)); 940 ATF_CHECK(bit_test(b, late - 1)); 941 ATF_CHECK(bit_test(b, late)); 942 ATF_CHECK(bit_test(b, late + 1)); 943 ATF_CHECK_EQ(0, bit_test(b, late + 2)); 944 bit_nclear(b, late - 1, late + 1); 945 ATF_CHECK_EQ(0, bit_test(b, late - 1)); 946 ATF_CHECK_EQ(0, bit_test(b, late)); 947 ATF_CHECK_EQ(0, bit_test(b, late + 1)); 948 949 free(b); 950 } 951 952 ATF_TP_ADD_TCS(tp) 953 { 954 955 ATF_TP_ADD_TC(tp, bitstr_in_struct); 956 ATF_TP_ADD_TC(tp, bitstr_size); 957 ATF_TP_ADD_TC(tp, bit_ffc_area); 958 ATF_TP_ADD_TC(tp, bit_ffs_area); 959 BITSTRING_TC_ADD(tp, bit_set); 960 BITSTRING_TC_ADD(tp, bit_clear); 961 BITSTRING_TC_ADD(tp, bit_ffs); 962 BITSTRING_TC_ADD(tp, bit_ffc); 963 BITSTRING_TC_ADD(tp, bit_ffs_at); 964 BITSTRING_TC_ADD(tp, bit_ffc_at); 965 BITSTRING_TC_ADD(tp, bit_nclear); 966 BITSTRING_TC_ADD(tp, bit_nset); 967 BITSTRING_TC_ADD(tp, bit_count); 968 BITSTRING_TC_ADD(tp, bit_ffs_area_at_all_or_nothing); 969 BITSTRING_TC_ADD(tp, bit_ffc_area_at_all_or_nothing); 970 BITSTRING_TC_ADD(tp, bit_foreach); 971 BITSTRING_TC_ADD(tp, bit_foreach_at); 972 BITSTRING_TC_ADD(tp, bit_foreach_unset); 973 BITSTRING_TC_ADD(tp, bit_foreach_unset_at); 974 ATF_TP_ADD_TC(tp, bitstr_large); 975 976 return (atf_no_error()); 977 } 978