projects/linux·blob master · refs

566 lines · 16.3 KiB

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 */
11struct 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
18struct 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 */
28static 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 */
68static 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 */
102static 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 */
114static 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 */
126static 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 */
166static 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 */
207static 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 */
243static 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 */
266static 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 */
284static 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 */
310static 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 */
340struct ffz_test_case {
341 unsigned long input;
342 unsigned long expected_ffz;
343 const char *description;
344};
345
346static 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 */
382static 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 */
399static 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
438static 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 */
469static 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) \
504static 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}
518CREATE_WRAPPER(ffs)
519CREATE_WRAPPER(fls)
520CREATE_WRAPPER(__ffs)
521CREATE_WRAPPER(__fls)
522CREATE_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 */
530static 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 */
542static 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 */
558static struct kunit_suite ffs_test_suite = {
559 .name = "ffs",
560 .test_cases = ffs_test_cases,
561};
562
563kunit_test_suites(&ffs_test_suite);
564
565MODULE_DESCRIPTION("KUnit tests for ffs()-family functions");
566MODULE_LICENSE("GPL");