Something went wrong. Try again.
Linux kernel mirror (for testing) git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567// SPDX-License-Identifier: GPL-2.0-only/* * KUnit tests for ffs()-family functions */#include <kunit/test.h>#include <linux/bitops.h>
/* * Test data structures */struct ffs_test_case { unsigned long input; int expected_ffs; /* ffs() result (1-based) */ int expected_fls; /* fls() result (1-based) */ const char *description;};
struct ffs64_test_case { u64 input; int expected_fls64; /* fls64() result (1-based) */ unsigned int expected_ffs64_0based; /* __ffs64() result (0-based) */ const char *description;};
/* * Basic edge cases - core functionality validation */static const struct ffs_test_case basic_test_cases[] = { /* Zero case - special handling */ {0x00000000, 0, 0, "zero value"},
/* Single bit patterns - powers of 2 */ {0x00000001, 1, 1, "bit 0 set"}, {0x00000002, 2, 2, "bit 1 set"}, {0x00000004, 3, 3, "bit 2 set"}, {0x00000008, 4, 4, "bit 3 set"}, {0x00000010, 5, 5, "bit 4 set"}, {0x00000020, 6, 6, "bit 5 set"}, {0x00000040, 7, 7, "bit 6 set"}, {0x00000080, 8, 8, "bit 7 set"}, {0x00000100, 9, 9, "bit 8 set"}, {0x00008000, 16, 16, "bit 15 set"}, {0x00010000, 17, 17, "bit 16 set"}, {0x40000000, 31, 31, "bit 30 set"}, {0x80000000, 32, 32, "bit 31 set (sign bit)"},
/* Maximum values */ {0xFFFFFFFF, 1, 32, "all bits set"},
/* Multiple bit patterns */ {0x00000003, 1, 2, "bits 0-1 set"}, {0x00000007, 1, 3, "bits 0-2 set"}, {0x0000000F, 1, 4, "bits 0-3 set"}, {0x000000FF, 1, 8, "bits 0-7 set"}, {0x0000FFFF, 1, 16, "bits 0-15 set"}, {0x7FFFFFFF, 1, 31, "bits 0-30 set"},
/* Sparse patterns */ {0x00000101, 1, 9, "bits 0,8 set"}, {0x00001001, 1, 13, "bits 0,12 set"}, {0x80000001, 1, 32, "bits 0,31 set"}, {0x40000002, 2, 31, "bits 1,30 set"},};
/* * 64-bit test cases */static const struct ffs64_test_case ffs64_test_cases[] = { /* Zero case */ {0x0000000000000000ULL, 0, 0, "zero value"},
/* Single bit patterns */ {0x0000000000000001ULL, 1, 0, "bit 0 set"}, {0x0000000000000002ULL, 2, 1, "bit 1 set"}, {0x0000000000000004ULL, 3, 2, "bit 2 set"}, {0x0000000000000008ULL, 4, 3, "bit 3 set"}, {0x0000000000008000ULL, 16, 15, "bit 15 set"}, {0x0000000000010000ULL, 17, 16, "bit 16 set"}, {0x0000000080000000ULL, 32, 31, "bit 31 set"}, {0x0000000100000000ULL, 33, 32, "bit 32 set"}, {0x0000000200000000ULL, 34, 33, "bit 33 set"}, {0x4000000000000000ULL, 63, 62, "bit 62 set"}, {0x8000000000000000ULL, 64, 63, "bit 63 set (sign bit)"},
/* Maximum values */ {0xFFFFFFFFFFFFFFFFULL, 64, 0, "all bits set"},
/* Cross 32-bit boundary patterns */ {0x00000000FFFFFFFFULL, 32, 0, "lower 32 bits set"}, {0xFFFFFFFF00000000ULL, 64, 32, "upper 32 bits set"}, {0x8000000000000001ULL, 64, 0, "bits 0,63 set"}, {0x4000000000000002ULL, 63, 1, "bits 1,62 set"},
/* Mixed patterns */ {0x00000001FFFFFFFFULL, 33, 0, "bit 32 + lower 32 bits"}, {0xFFFFFFFF80000000ULL, 64, 31, "upper 32 bits + bit 31"},};
/* * Helper function to validate ffs results with detailed error messages */static void validate_ffs_result(struct kunit *test, unsigned long input, int actual, int expected, const char *func_name, const char *description){ KUNIT_EXPECT_EQ_MSG(test, actual, expected, "%s(0x%08lx) [%s]: expected %d, got %d", func_name, input, description, expected, actual);}
/* * Helper function to validate 64-bit ffs results */static void validate_ffs64_result(struct kunit *test, u64 input, int actual, int expected, const char *func_name, const char *description){ KUNIT_EXPECT_EQ_MSG(test, actual, expected, "%s(0x%016llx) [%s]: expected %d, got %d", func_name, input, description, expected, actual);}
/* * Helper function to validate mathematical relationships between functions */static void validate_ffs_relationships(struct kunit *test, unsigned long input){ int ffs_result; int fls_result; unsigned int ffs_0based; unsigned int fls_0based;
if (input == 0) { /* Special case: zero input */ KUNIT_EXPECT_EQ(test, ffs(input), 0); KUNIT_EXPECT_EQ(test, fls(input), 0); /* __ffs and __fls are undefined for 0, but often return specific values */ return; }
ffs_result = ffs(input); fls_result = fls(input); ffs_0based = __ffs(input); fls_0based = __fls(input);
/* Relationship: ffs(x) == __ffs(x) + 1 for x != 0 */ KUNIT_EXPECT_EQ_MSG(test, ffs_result, ffs_0based + 1, "ffs(0x%08lx) != __ffs(0x%08lx) + 1: %d != %u + 1", input, input, ffs_result, ffs_0based);
/* Relationship: fls(x) == __fls(x) + 1 for x != 0 */ KUNIT_EXPECT_EQ_MSG(test, fls_result, fls_0based + 1, "fls(0x%08lx) != __fls(0x%08lx) + 1: %d != %u + 1", input, input, fls_result, fls_0based);
/* Range validation */ KUNIT_EXPECT_GE(test, ffs_result, 1); KUNIT_EXPECT_LE(test, ffs_result, BITS_PER_LONG); KUNIT_EXPECT_GE(test, fls_result, 1); KUNIT_EXPECT_LE(test, fls_result, BITS_PER_LONG);}
/* * Helper function to validate 64-bit relationships */static void validate_ffs64_relationships(struct kunit *test, u64 input){ int fls64_result; unsigned int ffs64_0based;
if (input == 0) { KUNIT_EXPECT_EQ(test, fls64(input), 0); return; }
fls64_result = fls64(input); ffs64_0based = __ffs64(input);
/* Range validation */ KUNIT_EXPECT_GE(test, fls64_result, 1); KUNIT_EXPECT_LE(test, fls64_result, 64); KUNIT_EXPECT_LT(test, ffs64_0based, 64);
/* * Relationships with 32-bit functions should hold for small values * on all architectures. */ if (input <= 0xFFFFFFFFULL) { unsigned long input_32 = (unsigned long)input; KUNIT_EXPECT_EQ_MSG(test, fls64(input), fls(input_32), "fls64(0x%llx) != fls(0x%lx): %d != %d", input, input_32, fls64(input), fls(input_32));
if (input != 0) { KUNIT_EXPECT_EQ_MSG(test, __ffs64(input), __ffs(input_32), "__ffs64(0x%llx) != __ffs(0x%lx): %lu != %lu", input, input_32, (unsigned long)__ffs64(input), (unsigned long)__ffs(input_32)); } }}
/* * Test basic correctness of all ffs-family functions */static void ffs_basic_correctness_test(struct kunit *test){ int i;
for (i = 0; i < ARRAY_SIZE(basic_test_cases); i++) { const struct ffs_test_case *tc = &basic_test_cases[i];
/* Test ffs() */ validate_ffs_result(test, tc->input, ffs(tc->input), tc->expected_ffs, "ffs", tc->description);
/* Test fls() */ validate_ffs_result(test, tc->input, fls(tc->input), tc->expected_fls, "fls", tc->description);
/* Test __ffs() - skip zero case as it's undefined */ if (tc->input != 0) { /* Calculate expected __ffs() result: __ffs(x) == ffs(x) - 1 */ unsigned int expected_ffs_0based = tc->expected_ffs - 1; validate_ffs_result(test, tc->input, __ffs(tc->input), expected_ffs_0based, "__ffs", tc->description); }
/* Test __fls() - skip zero case as it's undefined */ if (tc->input != 0) { /* Calculate expected __fls() result: __fls(x) == fls(x) - 1 */ unsigned int expected_fls_0based = tc->expected_fls - 1; validate_ffs_result(test, tc->input, __fls(tc->input), expected_fls_0based, "__fls", tc->description); } }}
/* * Test 64-bit function correctness */static void ffs64_correctness_test(struct kunit *test){ int i;
for (i = 0; i < ARRAY_SIZE(ffs64_test_cases); i++) { const struct ffs64_test_case *tc = &ffs64_test_cases[i];
/* Test fls64() */ validate_ffs64_result(test, tc->input, fls64(tc->input), tc->expected_fls64, "fls64", tc->description);
/* Test __ffs64() - skip zero case as it's undefined */ if (tc->input != 0) { validate_ffs64_result(test, tc->input, __ffs64(tc->input), tc->expected_ffs64_0based, "__ffs64", tc->description); } }}
/* * Test mathematical relationships between functions */static void ffs_mathematical_relationships_test(struct kunit *test){ int i;
/* Test basic cases */ for (i = 0; i < ARRAY_SIZE(basic_test_cases); i++) { validate_ffs_relationships(test, basic_test_cases[i].input); }
/* Test 64-bit cases */ for (i = 0; i < ARRAY_SIZE(ffs64_test_cases); i++) { validate_ffs64_relationships(test, ffs64_test_cases[i].input); }}
/* * Test edge cases and boundary conditions */static void ffs_edge_cases_test(struct kunit *test){ unsigned long test_patterns[] = { /* Powers of 2 */ 1UL, 2UL, 4UL, 8UL, 16UL, 32UL, 64UL, 128UL, 256UL, 512UL, 1024UL, 2048UL, 4096UL, 8192UL,
/* Powers of 2 minus 1 */ 1UL, 3UL, 7UL, 15UL, 31UL, 63UL, 127UL, 255UL, 511UL, 1023UL, 2047UL, 4095UL, 8191UL,
/* Boundary values */ 0x7FFFFFFFUL, /* Maximum positive 32-bit */ 0x80000000UL, /* Minimum negative 32-bit */ 0xFFFFFFFFUL, /* Maximum 32-bit unsigned */ }; int i;
for (i = 0; i < ARRAY_SIZE(test_patterns); i++) { validate_ffs_relationships(test, test_patterns[i]); }}
/* * Test 64-bit edge cases */static void ffs64_edge_cases_test(struct kunit *test){ u64 test_patterns_64[] = { /* 64-bit powers of 2 */ 0x0000000100000000ULL, /* 2^32 */ 0x0000000200000000ULL, /* 2^33 */ 0x0000000400000000ULL, /* 2^34 */ 0x0000001000000000ULL, /* 2^36 */ 0x0000010000000000ULL, /* 2^40 */ 0x0001000000000000ULL, /* 2^48 */ 0x0100000000000000ULL, /* 2^56 */ 0x4000000000000000ULL, /* 2^62 */ 0x8000000000000000ULL, /* 2^63 */
/* Cross-boundary patterns */ 0x00000000FFFFFFFFULL, /* Lower 32 bits */ 0xFFFFFFFF00000000ULL, /* Upper 32 bits */ 0x7FFFFFFFFFFFFFFFULL, /* Maximum positive 64-bit */ 0xFFFFFFFFFFFFFFFFULL, /* Maximum 64-bit unsigned */ }; int i;
for (i = 0; i < ARRAY_SIZE(test_patterns_64); i++) { validate_ffs64_relationships(test, test_patterns_64[i]); }}
/* * ffz() test data - Find First Zero bit test cases */struct ffz_test_case { unsigned long input; unsigned long expected_ffz; const char *description;};
static const struct ffz_test_case ffz_test_cases[] = { /* Zero bits in specific positions */ {0xFFFFFFFE, 0, "bit 0 is zero"}, /* ...11111110 */ {0xFFFFFFFD, 1, "bit 1 is zero"}, /* ...11111101 */ {0xFFFFFFFB, 2, "bit 2 is zero"}, /* ...11111011 */ {0xFFFFFFF7, 3, "bit 3 is zero"}, /* ...11110111 */ {0xFFFFFFEF, 4, "bit 4 is zero"}, /* ...11101111 */ {0xFFFFFFDF, 5, "bit 5 is zero"}, /* ...11011111 */ {0xFFFFFFBF, 6, "bit 6 is zero"}, /* ...10111111 */ {0xFFFFFF7F, 7, "bit 7 is zero"}, /* ...01111111 */ {0xFFFFFEFF, 8, "bit 8 is zero"}, /* Gap in bit 8 */ {0xFFFF7FFF, 15, "bit 15 is zero"}, /* Gap in bit 15 */ {0xFFFEFFFF, 16, "bit 16 is zero"}, /* Gap in bit 16 */ {0xBFFFFFFF, 30, "bit 30 is zero"}, /* Gap in bit 30 */ {0x7FFFFFFF, 31, "bit 31 is zero"}, /* 01111111... */
/* Multiple zero patterns */ {0xFFFFFFFC, 0, "bits 0-1 are zero"}, /* ...11111100 */ {0xFFFFFFF8, 0, "bits 0-2 are zero"}, /* ...11111000 */ {0xFFFFFFF0, 0, "bits 0-3 are zero"}, /* ...11110000 */ {0xFFFFFF00, 0, "bits 0-7 are zero"}, /* ...00000000 */ {0xFFFF0000, 0, "bits 0-15 are zero"}, /* Lower 16 bits zero */
/* All zeros (special case) */ {0x00000000, 0, "all bits zero"},
/* Complex patterns */ {0xFFFDFFFF, 17, "bit 17 is zero"}, /* Gap in bit 17 */ {0xFFF7FFFF, 19, "bit 19 is zero"}, /* Gap in bit 19 */ {0xF7FFFFFF, 27, "bit 27 is zero"}, /* Gap in bit 27 */ {0xDFFFFFFF, 29, "bit 29 is zero"}, /* Gap in bit 29 */};
/* * Test basic correctness of ffz() function */static void ffz_basic_correctness_test(struct kunit *test){ int i;
for (i = 0; i < ARRAY_SIZE(ffz_test_cases); i++) { const struct ffz_test_case *tc = &ffz_test_cases[i]; unsigned long result = ffz(tc->input);
KUNIT_EXPECT_EQ_MSG(test, result, tc->expected_ffz, "ffz(0x%08lx) [%s]: expected %lu, got %lu", tc->input, tc->description, tc->expected_ffz, result); }}
/* * Test mathematical relationships between ffz() and other functions */static void validate_ffz_relationships(struct kunit *test, unsigned long input){ unsigned long ffz_result;
if (input == 0) { /* ffz(0) should return 0 (first zero bit is at position 0) */ KUNIT_EXPECT_EQ(test, ffz(input), 0); return; }
if (input == ~0UL) { /* ffz(~0) is undefined (no zero bits) - just verify it doesn't crash */ ffz_result = ffz(input); /* Implementation-defined behavior, just ensure it completes */ return; }
ffz_result = ffz(input);
/* Range validation - result should be within valid bit range */ KUNIT_EXPECT_LT(test, ffz_result, BITS_PER_LONG);
/* Verify the bit at ffz_result position is actually zero */ KUNIT_EXPECT_EQ_MSG(test, (input >> ffz_result) & 1, 0, "ffz(0x%08lx) = %lu, but bit %lu is not zero", input, ffz_result, ffz_result);
/* Core relationship: if we set the ffz bit, ffz should find a different bit */ if (ffz_result < BITS_PER_LONG - 1) { unsigned long modified = input | (1UL << ffz_result); if (modified != ~0UL) { /* Skip if all bits would be set */ unsigned long new_ffz = ffz(modified); KUNIT_EXPECT_NE_MSG(test, new_ffz, ffz_result, "ffz(0x%08lx) = %lu, but setting that bit doesn't change ffz result", input, ffz_result); } }}
static void ffz_mathematical_relationships_test(struct kunit *test){ unsigned long test_patterns[] = { /* Powers of 2 with one bit clear */ 0xFFFFFFFE, 0xFFFFFFFD, 0xFFFFFFFB, 0xFFFFFFF7, 0xFFFFFFEF, 0xFFFFFFDF, 0xFFFFFFBF, 0xFFFFFF7F,
/* Multiple patterns */ 0xFFFFFF00, 0xFFFFF000, 0xFFFF0000, 0xFFF00000, 0x7FFFFFFF, 0x3FFFFFFF, 0x1FFFFFFF, 0x0FFFFFFF,
/* Complex bit patterns */ 0xAAAAAAAA, 0x55555555, 0xCCCCCCCC, 0x33333333, 0xF0F0F0F0, 0x0F0F0F0F, 0xFF00FF00, 0x00FF00FF, }; int i;
/* Test basic test cases */ for (i = 0; i < ARRAY_SIZE(ffz_test_cases); i++) { validate_ffz_relationships(test, ffz_test_cases[i].input); }
/* Test additional patterns */ for (i = 0; i < ARRAY_SIZE(test_patterns); i++) { validate_ffz_relationships(test, test_patterns[i]); }}
/* * Test edge cases and boundary conditions for ffz() */static void ffz_edge_cases_test(struct kunit *test){ unsigned long edge_patterns[] = { /* Boundary values */ 0x00000000, /* All zeros */ 0x80000000, /* Only MSB set */ 0x00000001, /* Only LSB set */ 0x7FFFFFFF, /* MSB clear */ 0xFFFFFFFE, /* LSB clear */
/* Powers of 2 complement patterns (one zero bit each) */ ~(1UL << 0), ~(1UL << 1), ~(1UL << 2), ~(1UL << 3), ~(1UL << 4), ~(1UL << 8), ~(1UL << 16), ~(1UL << 31),
/* Walking zero patterns */ 0xFFFFFFFE, 0xFFFFFFFD, 0xFFFFFFFB, 0xFFFFFFF7, 0xFFFFFFEF, 0xFFFFFFDF, 0xFFFFFFBF, 0xFFFFFF7F, 0xFFFFFEFF, 0xFFFFFDFF, 0xFFFFFBFF, 0xFFFFF7FF,
/* Multiple zeros */ 0xFFFFFF00, 0xFFFFF000, 0xFFFF0000, 0xFFF00000, 0xFF000000, 0xF0000000, 0x00000000, }; int i;
for (i = 0; i < ARRAY_SIZE(edge_patterns); i++) { validate_ffz_relationships(test, edge_patterns[i]); }}
/* * To have useful build error output, split the tests into separate * functions so it's clear which are missing __attribute_const__. */#define CREATE_WRAPPER(func) \static noinline bool build_test_##func(void) \{ \ int init_##func = 32; \ int result_##func = func(6); \ \ /* Does the static initializer vanish after calling func? */ \ BUILD_BUG_ON(init_##func < 32); \ \ /* "Consume" the results so optimizer doesn't drop them. */ \ barrier_data(&init_##func); \ barrier_data(&result_##func); \ \ return true; \}CREATE_WRAPPER(ffs)CREATE_WRAPPER(fls)CREATE_WRAPPER(__ffs)CREATE_WRAPPER(__fls)CREATE_WRAPPER(ffz)#undef CREATE_WRAPPER
/* * Make sure that __attribute_const__ has be applied to all the * functions. This is a regression test for: * https://github.com/KSPP/linux/issues/364 */static void ffs_attribute_const_test(struct kunit *test){ KUNIT_EXPECT_TRUE(test, build_test_ffs()); KUNIT_EXPECT_TRUE(test, build_test_fls()); KUNIT_EXPECT_TRUE(test, build_test___ffs()); KUNIT_EXPECT_TRUE(test, build_test___fls()); KUNIT_EXPECT_TRUE(test, build_test_ffz());}
/* * KUnit test case definitions */static struct kunit_case ffs_test_cases[] = { KUNIT_CASE(ffs_basic_correctness_test), KUNIT_CASE(ffs64_correctness_test), KUNIT_CASE(ffs_mathematical_relationships_test), KUNIT_CASE(ffs_edge_cases_test), KUNIT_CASE(ffs64_edge_cases_test), KUNIT_CASE(ffz_basic_correctness_test), KUNIT_CASE(ffz_mathematical_relationships_test), KUNIT_CASE(ffz_edge_cases_test), KUNIT_CASE(ffs_attribute_const_test), {}};
/* * KUnit test suite definition */static struct kunit_suite ffs_test_suite = { .name = "ffs", .test_cases = ffs_test_cases,};
kunit_test_suites(&ffs_test_suite);
MODULE_DESCRIPTION("KUnit tests for ffs()-family functions");MODULE_LICENSE("GPL");