1 // SPDX-License-Identifier: GPL-2.0-only 2 /* 3 * KUnit tests for ffs()-family functions 4 */ 5 #include <kunit/test.h> 6 #include <linux/bitops.h> 7 8 /* 9 * Test data structures 10 */ 11 struct ffs_test_case { 12 unsigned long input; 13 int expected_ffs; /* ffs() result (1-based) */ 14 int expected_fls; /* fls() result (1-based) */ 15 const char *description; 16 }; 17 18 struct ffs64_test_case { 19 u64 input; 20 int expected_fls64; /* fls64() result (1-based) */ 21 unsigned int expected_ffs64_0based; /* __ffs64() result (0-based) */ 22 const char *description; 23 }; 24 25 /* 26 * Basic edge cases - core functionality validation 27 */ 28 static const struct ffs_test_case basic_test_cases[] = { 29 /* Zero case - special handling */ 30 {0x00000000, 0, 0, "zero value"}, 31 32 /* Single bit patterns - powers of 2 */ 33 {0x00000001, 1, 1, "bit 0 set"}, 34 {0x00000002, 2, 2, "bit 1 set"}, 35 {0x00000004, 3, 3, "bit 2 set"}, 36 {0x00000008, 4, 4, "bit 3 set"}, 37 {0x00000010, 5, 5, "bit 4 set"}, 38 {0x00000020, 6, 6, "bit 5 set"}, 39 {0x00000040, 7, 7, "bit 6 set"}, 40 {0x00000080, 8, 8, "bit 7 set"}, 41 {0x00000100, 9, 9, "bit 8 set"}, 42 {0x00008000, 16, 16, "bit 15 set"}, 43 {0x00010000, 17, 17, "bit 16 set"}, 44 {0x40000000, 31, 31, "bit 30 set"}, 45 {0x80000000, 32, 32, "bit 31 set (sign bit)"}, 46 47 /* Maximum values */ 48 {0xFFFFFFFF, 1, 32, "all bits set"}, 49 50 /* Multiple bit patterns */ 51 {0x00000003, 1, 2, "bits 0-1 set"}, 52 {0x00000007, 1, 3, "bits 0-2 set"}, 53 {0x0000000F, 1, 4, "bits 0-3 set"}, 54 {0x000000FF, 1, 8, "bits 0-7 set"}, 55 {0x0000FFFF, 1, 16, "bits 0-15 set"}, 56 {0x7FFFFFFF, 1, 31, "bits 0-30 set"}, 57 58 /* Sparse patterns */ 59 {0x00000101, 1, 9, "bits 0,8 set"}, 60 {0x00001001, 1, 13, "bits 0,12 set"}, 61 {0x80000001, 1, 32, "bits 0,31 set"}, 62 {0x40000002, 2, 31, "bits 1,30 set"}, 63 }; 64 65 /* 66 * 64-bit test cases 67 */ 68 static const struct ffs64_test_case ffs64_test_cases[] = { 69 /* Zero case */ 70 {0x0000000000000000ULL, 0, 0, "zero value"}, 71 72 /* Single bit patterns */ 73 {0x0000000000000001ULL, 1, 0, "bit 0 set"}, 74 {0x0000000000000002ULL, 2, 1, "bit 1 set"}, 75 {0x0000000000000004ULL, 3, 2, "bit 2 set"}, 76 {0x0000000000000008ULL, 4, 3, "bit 3 set"}, 77 {0x0000000000008000ULL, 16, 15, "bit 15 set"}, 78 {0x0000000000010000ULL, 17, 16, "bit 16 set"}, 79 {0x0000000080000000ULL, 32, 31, "bit 31 set"}, 80 {0x0000000100000000ULL, 33, 32, "bit 32 set"}, 81 {0x0000000200000000ULL, 34, 33, "bit 33 set"}, 82 {0x4000000000000000ULL, 63, 62, "bit 62 set"}, 83 {0x8000000000000000ULL, 64, 63, "bit 63 set (sign bit)"}, 84 85 /* Maximum values */ 86 {0xFFFFFFFFFFFFFFFFULL, 64, 0, "all bits set"}, 87 88 /* Cross 32-bit boundary patterns */ 89 {0x00000000FFFFFFFFULL, 32, 0, "lower 32 bits set"}, 90 {0xFFFFFFFF00000000ULL, 64, 32, "upper 32 bits set"}, 91 {0x8000000000000001ULL, 64, 0, "bits 0,63 set"}, 92 {0x4000000000000002ULL, 63, 1, "bits 1,62 set"}, 93 94 /* Mixed patterns */ 95 {0x00000001FFFFFFFFULL, 33, 0, "bit 32 + lower 32 bits"}, 96 {0xFFFFFFFF80000000ULL, 64, 31, "upper 32 bits + bit 31"}, 97 }; 98 99 /* 100 * Helper function to validate ffs results with detailed error messages 101 */ 102 static void validate_ffs_result(struct kunit *test, unsigned long input, 103 int actual, int expected, const char *func_name, 104 const char *description) 105 { 106 KUNIT_EXPECT_EQ_MSG(test, actual, expected, 107 "%s(0x%08lx) [%s]: expected %d, got %d", 108 func_name, input, description, expected, actual); 109 } 110 111 /* 112 * Helper function to validate 64-bit ffs results 113 */ 114 static void validate_ffs64_result(struct kunit *test, u64 input, 115 int actual, int expected, const char *func_name, 116 const char *description) 117 { 118 KUNIT_EXPECT_EQ_MSG(test, actual, expected, 119 "%s(0x%016llx) [%s]: expected %d, got %d", 120 func_name, input, description, expected, actual); 121 } 122 123 /* 124 * Helper function to validate mathematical relationships between functions 125 */ 126 static void validate_ffs_relationships(struct kunit *test, unsigned long input) 127 { 128 int ffs_result; 129 int fls_result; 130 unsigned int ffs_0based; 131 unsigned int fls_0based; 132 133 if (input == 0) { 134 /* Special case: zero input */ 135 KUNIT_EXPECT_EQ(test, ffs(input), 0); 136 KUNIT_EXPECT_EQ(test, fls(input), 0); 137 /* __ffs and __fls are undefined for 0, but often return specific values */ 138 return; 139 } 140 141 ffs_result = ffs(input); 142 fls_result = fls(input); 143 ffs_0based = __ffs(input); 144 fls_0based = __fls(input); 145 146 /* Relationship: ffs(x) == __ffs(x) + 1 for x != 0 */ 147 KUNIT_EXPECT_EQ_MSG(test, ffs_result, ffs_0based + 1, 148 "ffs(0x%08lx) != __ffs(0x%08lx) + 1: %d != %u + 1", 149 input, input, ffs_result, ffs_0based); 150 151 /* Relationship: fls(x) == __fls(x) + 1 for x != 0 */ 152 KUNIT_EXPECT_EQ_MSG(test, fls_result, fls_0based + 1, 153 "fls(0x%08lx) != __fls(0x%08lx) + 1: %d != %u + 1", 154 input, input, fls_result, fls_0based); 155 156 /* Range validation */ 157 KUNIT_EXPECT_GE(test, ffs_result, 1); 158 KUNIT_EXPECT_LE(test, ffs_result, BITS_PER_LONG); 159 KUNIT_EXPECT_GE(test, fls_result, 1); 160 KUNIT_EXPECT_LE(test, fls_result, BITS_PER_LONG); 161 } 162 163 /* 164 * Helper function to validate 64-bit relationships 165 */ 166 static void validate_ffs64_relationships(struct kunit *test, u64 input) 167 { 168 int fls64_result; 169 unsigned int ffs64_0based; 170 171 if (input == 0) { 172 KUNIT_EXPECT_EQ(test, fls64(input), 0); 173 return; 174 } 175 176 fls64_result = fls64(input); 177 ffs64_0based = __ffs64(input); 178 179 /* Range validation */ 180 KUNIT_EXPECT_GE(test, fls64_result, 1); 181 KUNIT_EXPECT_LE(test, fls64_result, 64); 182 KUNIT_EXPECT_LT(test, ffs64_0based, 64); 183 184 /* 185 * Relationships with 32-bit functions should hold for small values 186 * on all architectures. 187 */ 188 if (input <= 0xFFFFFFFFULL) { 189 unsigned long input_32 = (unsigned long)input; 190 KUNIT_EXPECT_EQ_MSG(test, fls64(input), fls(input_32), 191 "fls64(0x%llx) != fls(0x%lx): %d != %d", 192 input, input_32, fls64(input), fls(input_32)); 193 194 if (input != 0) { 195 KUNIT_EXPECT_EQ_MSG(test, __ffs64(input), __ffs(input_32), 196 "__ffs64(0x%llx) != __ffs(0x%lx): %lu != %lu", 197 input, input_32, 198 (unsigned long)__ffs64(input), 199 (unsigned long)__ffs(input_32)); 200 } 201 } 202 } 203 204 /* 205 * Test basic correctness of all ffs-family functions 206 */ 207 static void ffs_basic_correctness_test(struct kunit *test) 208 { 209 int i; 210 211 for (i = 0; i < ARRAY_SIZE(basic_test_cases); i++) { 212 const struct ffs_test_case *tc = &basic_test_cases[i]; 213 214 /* Test ffs() */ 215 validate_ffs_result(test, tc->input, ffs(tc->input), 216 tc->expected_ffs, "ffs", tc->description); 217 218 /* Test fls() */ 219 validate_ffs_result(test, tc->input, fls(tc->input), 220 tc->expected_fls, "fls", tc->description); 221 222 /* Test __ffs() - skip zero case as it's undefined */ 223 if (tc->input != 0) { 224 /* Calculate expected __ffs() result: __ffs(x) == ffs(x) - 1 */ 225 unsigned int expected_ffs_0based = tc->expected_ffs - 1; 226 validate_ffs_result(test, tc->input, __ffs(tc->input), 227 expected_ffs_0based, "__ffs", tc->description); 228 } 229 230 /* Test __fls() - skip zero case as it's undefined */ 231 if (tc->input != 0) { 232 /* Calculate expected __fls() result: __fls(x) == fls(x) - 1 */ 233 unsigned int expected_fls_0based = tc->expected_fls - 1; 234 validate_ffs_result(test, tc->input, __fls(tc->input), 235 expected_fls_0based, "__fls", tc->description); 236 } 237 } 238 } 239 240 /* 241 * Test 64-bit function correctness 242 */ 243 static void ffs64_correctness_test(struct kunit *test) 244 { 245 int i; 246 247 for (i = 0; i < ARRAY_SIZE(ffs64_test_cases); i++) { 248 const struct ffs64_test_case *tc = &ffs64_test_cases[i]; 249 250 /* Test fls64() */ 251 validate_ffs64_result(test, tc->input, fls64(tc->input), 252 tc->expected_fls64, "fls64", tc->description); 253 254 /* Test __ffs64() - skip zero case as it's undefined */ 255 if (tc->input != 0) { 256 validate_ffs64_result(test, tc->input, __ffs64(tc->input), 257 tc->expected_ffs64_0based, "__ffs64", 258 tc->description); 259 } 260 } 261 } 262 263 /* 264 * Test mathematical relationships between functions 265 */ 266 static void ffs_mathematical_relationships_test(struct kunit *test) 267 { 268 int i; 269 270 /* Test basic cases */ 271 for (i = 0; i < ARRAY_SIZE(basic_test_cases); i++) { 272 validate_ffs_relationships(test, basic_test_cases[i].input); 273 } 274 275 /* Test 64-bit cases */ 276 for (i = 0; i < ARRAY_SIZE(ffs64_test_cases); i++) { 277 validate_ffs64_relationships(test, ffs64_test_cases[i].input); 278 } 279 } 280 281 /* 282 * Test edge cases and boundary conditions 283 */ 284 static void ffs_edge_cases_test(struct kunit *test) 285 { 286 unsigned long test_patterns[] = { 287 /* Powers of 2 */ 288 1UL, 2UL, 4UL, 8UL, 16UL, 32UL, 64UL, 128UL, 289 256UL, 512UL, 1024UL, 2048UL, 4096UL, 8192UL, 290 291 /* Powers of 2 minus 1 */ 292 1UL, 3UL, 7UL, 15UL, 31UL, 63UL, 127UL, 255UL, 293 511UL, 1023UL, 2047UL, 4095UL, 8191UL, 294 295 /* Boundary values */ 296 0x7FFFFFFFUL, /* Maximum positive 32-bit */ 297 0x80000000UL, /* Minimum negative 32-bit */ 298 0xFFFFFFFFUL, /* Maximum 32-bit unsigned */ 299 }; 300 int i; 301 302 for (i = 0; i < ARRAY_SIZE(test_patterns); i++) { 303 validate_ffs_relationships(test, test_patterns[i]); 304 } 305 } 306 307 /* 308 * Test 64-bit edge cases 309 */ 310 static void ffs64_edge_cases_test(struct kunit *test) 311 { 312 u64 test_patterns_64[] = { 313 /* 64-bit powers of 2 */ 314 0x0000000100000000ULL, /* 2^32 */ 315 0x0000000200000000ULL, /* 2^33 */ 316 0x0000000400000000ULL, /* 2^34 */ 317 0x0000001000000000ULL, /* 2^36 */ 318 0x0000010000000000ULL, /* 2^40 */ 319 0x0001000000000000ULL, /* 2^48 */ 320 0x0100000000000000ULL, /* 2^56 */ 321 0x4000000000000000ULL, /* 2^62 */ 322 0x8000000000000000ULL, /* 2^63 */ 323 324 /* Cross-boundary patterns */ 325 0x00000000FFFFFFFFULL, /* Lower 32 bits */ 326 0xFFFFFFFF00000000ULL, /* Upper 32 bits */ 327 0x7FFFFFFFFFFFFFFFULL, /* Maximum positive 64-bit */ 328 0xFFFFFFFFFFFFFFFFULL, /* Maximum 64-bit unsigned */ 329 }; 330 int i; 331 332 for (i = 0; i < ARRAY_SIZE(test_patterns_64); i++) { 333 validate_ffs64_relationships(test, test_patterns_64[i]); 334 } 335 } 336 337 /* 338 * ffz() test data - Find First Zero bit test cases 339 */ 340 struct ffz_test_case { 341 unsigned long input; 342 unsigned long expected_ffz; 343 const char *description; 344 }; 345 346 static const struct ffz_test_case ffz_test_cases[] = { 347 /* Zero bits in specific positions */ 348 {0xFFFFFFFE, 0, "bit 0 is zero"}, /* ...11111110 */ 349 {0xFFFFFFFD, 1, "bit 1 is zero"}, /* ...11111101 */ 350 {0xFFFFFFFB, 2, "bit 2 is zero"}, /* ...11111011 */ 351 {0xFFFFFFF7, 3, "bit 3 is zero"}, /* ...11110111 */ 352 {0xFFFFFFEF, 4, "bit 4 is zero"}, /* ...11101111 */ 353 {0xFFFFFFDF, 5, "bit 5 is zero"}, /* ...11011111 */ 354 {0xFFFFFFBF, 6, "bit 6 is zero"}, /* ...10111111 */ 355 {0xFFFFFF7F, 7, "bit 7 is zero"}, /* ...01111111 */ 356 {0xFFFFFEFF, 8, "bit 8 is zero"}, /* Gap in bit 8 */ 357 {0xFFFF7FFF, 15, "bit 15 is zero"}, /* Gap in bit 15 */ 358 {0xFFFEFFFF, 16, "bit 16 is zero"}, /* Gap in bit 16 */ 359 {0xBFFFFFFF, 30, "bit 30 is zero"}, /* Gap in bit 30 */ 360 {0x7FFFFFFF, 31, "bit 31 is zero"}, /* 01111111... */ 361 362 /* Multiple zero patterns */ 363 {0xFFFFFFFC, 0, "bits 0-1 are zero"}, /* ...11111100 */ 364 {0xFFFFFFF8, 0, "bits 0-2 are zero"}, /* ...11111000 */ 365 {0xFFFFFFF0, 0, "bits 0-3 are zero"}, /* ...11110000 */ 366 {0xFFFFFF00, 0, "bits 0-7 are zero"}, /* ...00000000 */ 367 {0xFFFF0000, 0, "bits 0-15 are zero"}, /* Lower 16 bits zero */ 368 369 /* All zeros (special case) */ 370 {0x00000000, 0, "all bits zero"}, 371 372 /* Complex patterns */ 373 {0xFFFDFFFF, 17, "bit 17 is zero"}, /* Gap in bit 17 */ 374 {0xFFF7FFFF, 19, "bit 19 is zero"}, /* Gap in bit 19 */ 375 {0xF7FFFFFF, 27, "bit 27 is zero"}, /* Gap in bit 27 */ 376 {0xDFFFFFFF, 29, "bit 29 is zero"}, /* Gap in bit 29 */ 377 }; 378 379 /* 380 * Test basic correctness of ffz() function 381 */ 382 static void ffz_basic_correctness_test(struct kunit *test) 383 { 384 int i; 385 386 for (i = 0; i < ARRAY_SIZE(ffz_test_cases); i++) { 387 const struct ffz_test_case *tc = &ffz_test_cases[i]; 388 unsigned long result = ffz(tc->input); 389 390 KUNIT_EXPECT_EQ_MSG(test, result, tc->expected_ffz, 391 "ffz(0x%08lx) [%s]: expected %lu, got %lu", 392 tc->input, tc->description, tc->expected_ffz, result); 393 } 394 } 395 396 /* 397 * Test mathematical relationships between ffz() and other functions 398 */ 399 static void validate_ffz_relationships(struct kunit *test, unsigned long input) 400 { 401 unsigned long ffz_result; 402 403 if (input == 0) { 404 /* ffz(0) should return 0 (first zero bit is at position 0) */ 405 KUNIT_EXPECT_EQ(test, ffz(input), 0); 406 return; 407 } 408 409 if (input == ~0UL) { 410 /* ffz(~0) is undefined (no zero bits) - just verify it doesn't crash */ 411 ffz_result = ffz(input); 412 /* Implementation-defined behavior, just ensure it completes */ 413 return; 414 } 415 416 ffz_result = ffz(input); 417 418 /* Range validation - result should be within valid bit range */ 419 KUNIT_EXPECT_LT(test, ffz_result, BITS_PER_LONG); 420 421 /* Verify the bit at ffz_result position is actually zero */ 422 KUNIT_EXPECT_EQ_MSG(test, (input >> ffz_result) & 1, 0, 423 "ffz(0x%08lx) = %lu, but bit %lu is not zero", 424 input, ffz_result, ffz_result); 425 426 /* Core relationship: if we set the ffz bit, ffz should find a different bit */ 427 if (ffz_result < BITS_PER_LONG - 1) { 428 unsigned long modified = input | (1UL << ffz_result); 429 if (modified != ~0UL) { /* Skip if all bits would be set */ 430 unsigned long new_ffz = ffz(modified); 431 KUNIT_EXPECT_NE_MSG(test, new_ffz, ffz_result, 432 "ffz(0x%08lx) = %lu, but setting that bit doesn't change ffz result", 433 input, ffz_result); 434 } 435 } 436 } 437 438 static void ffz_mathematical_relationships_test(struct kunit *test) 439 { 440 unsigned long test_patterns[] = { 441 /* Powers of 2 with one bit clear */ 442 0xFFFFFFFE, 0xFFFFFFFD, 0xFFFFFFFB, 0xFFFFFFF7, 443 0xFFFFFFEF, 0xFFFFFFDF, 0xFFFFFFBF, 0xFFFFFF7F, 444 445 /* Multiple patterns */ 446 0xFFFFFF00, 0xFFFFF000, 0xFFFF0000, 0xFFF00000, 447 0x7FFFFFFF, 0x3FFFFFFF, 0x1FFFFFFF, 0x0FFFFFFF, 448 449 /* Complex bit patterns */ 450 0xAAAAAAAA, 0x55555555, 0xCCCCCCCC, 0x33333333, 451 0xF0F0F0F0, 0x0F0F0F0F, 0xFF00FF00, 0x00FF00FF, 452 }; 453 int i; 454 455 /* Test basic test cases */ 456 for (i = 0; i < ARRAY_SIZE(ffz_test_cases); i++) { 457 validate_ffz_relationships(test, ffz_test_cases[i].input); 458 } 459 460 /* Test additional patterns */ 461 for (i = 0; i < ARRAY_SIZE(test_patterns); i++) { 462 validate_ffz_relationships(test, test_patterns[i]); 463 } 464 } 465 466 /* 467 * Test edge cases and boundary conditions for ffz() 468 */ 469 static void ffz_edge_cases_test(struct kunit *test) 470 { 471 unsigned long edge_patterns[] = { 472 /* Boundary values */ 473 0x00000000, /* All zeros */ 474 0x80000000, /* Only MSB set */ 475 0x00000001, /* Only LSB set */ 476 0x7FFFFFFF, /* MSB clear */ 477 0xFFFFFFFE, /* LSB clear */ 478 479 /* Powers of 2 complement patterns (one zero bit each) */ 480 ~(1UL << 0), ~(1UL << 1), ~(1UL << 2), ~(1UL << 3), 481 ~(1UL << 4), ~(1UL << 8), ~(1UL << 16), ~(1UL << 31), 482 483 /* Walking zero patterns */ 484 0xFFFFFFFE, 0xFFFFFFFD, 0xFFFFFFFB, 0xFFFFFFF7, 485 0xFFFFFFEF, 0xFFFFFFDF, 0xFFFFFFBF, 0xFFFFFF7F, 486 0xFFFFFEFF, 0xFFFFFDFF, 0xFFFFFBFF, 0xFFFFF7FF, 487 488 /* Multiple zeros */ 489 0xFFFFFF00, 0xFFFFF000, 0xFFFF0000, 0xFFF00000, 490 0xFF000000, 0xF0000000, 0x00000000, 491 }; 492 int i; 493 494 for (i = 0; i < ARRAY_SIZE(edge_patterns); i++) { 495 validate_ffz_relationships(test, edge_patterns[i]); 496 } 497 } 498 499 /* 500 * To have useful build error output, split the tests into separate 501 * functions so it's clear which are missing __attribute_const__. 502 */ 503 #define CREATE_WRAPPER(func) \ 504 static noinline bool build_test_##func(void) \ 505 { \ 506 int init_##func = 32; \ 507 int result_##func = func(6); \ 508 \ 509 /* Does the static initializer vanish after calling func? */ \ 510 BUILD_BUG_ON(init_##func < 32); \ 511 \ 512 /* "Consume" the results so optimizer doesn't drop them. */ \ 513 barrier_data(&init_##func); \ 514 barrier_data(&result_##func); \ 515 \ 516 return true; \ 517 } 518 CREATE_WRAPPER(ffs) 519 CREATE_WRAPPER(fls) 520 CREATE_WRAPPER(__ffs) 521 CREATE_WRAPPER(__fls) 522 CREATE_WRAPPER(ffz) 523 #undef CREATE_WRAPPER 524 525 /* 526 * Make sure that __attribute_const__ has be applied to all the 527 * functions. This is a regression test for: 528 * https://github.com/KSPP/linux/issues/364 529 */ 530 static void ffs_attribute_const_test(struct kunit *test) 531 { 532 KUNIT_EXPECT_TRUE(test, build_test_ffs()); 533 KUNIT_EXPECT_TRUE(test, build_test_fls()); 534 KUNIT_EXPECT_TRUE(test, build_test___ffs()); 535 KUNIT_EXPECT_TRUE(test, build_test___fls()); 536 KUNIT_EXPECT_TRUE(test, build_test_ffz()); 537 } 538 539 /* 540 * KUnit test case definitions 541 */ 542 static struct kunit_case ffs_test_cases[] = { 543 KUNIT_CASE(ffs_basic_correctness_test), 544 KUNIT_CASE(ffs64_correctness_test), 545 KUNIT_CASE(ffs_mathematical_relationships_test), 546 KUNIT_CASE(ffs_edge_cases_test), 547 KUNIT_CASE(ffs64_edge_cases_test), 548 KUNIT_CASE(ffz_basic_correctness_test), 549 KUNIT_CASE(ffz_mathematical_relationships_test), 550 KUNIT_CASE(ffz_edge_cases_test), 551 KUNIT_CASE(ffs_attribute_const_test), 552 {} 553 }; 554 555 /* 556 * KUnit test suite definition 557 */ 558 static struct kunit_suite ffs_test_suite = { 559 .name = "ffs", 560 .test_cases = ffs_test_cases, 561 }; 562 563 kunit_test_suites(&ffs_test_suite); 564 565 MODULE_DESCRIPTION("KUnit tests for ffs()-family functions"); 566 MODULE_LICENSE("GPL"); 567