From 2c523550b9924f98299414253d8a1fef7c60ef2d Mon Sep 17 00:00:00 2001 From: Yury Norov Date: Thu, 28 Apr 2022 13:51:14 -0700 Subject: lib/bitmap: add test for bitmap_{from,to}_arr64 Test newly added bitmap_{from,to}_arr64() functions similarly to already existing bitmap_{from,to}_arr32() tests. CC: Alexander Gordeev CC: Andy Shevchenko CC: Christian Borntraeger CC: Claudio Imbrenda CC: David Hildenbrand CC: Heiko Carstens CC: Janosch Frank CC: Rasmus Villemoes CC: Sven Schnelle CC: Vasily Gorbik Signed-off-by: Yury Norov --- lib/test_bitmap.c | 25 +++++++++++++++++++++++++ 1 file changed, 25 insertions(+) (limited to 'lib/test_bitmap.c') diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c index 0c82f07f74fc..d5923a640457 100644 --- a/lib/test_bitmap.c +++ b/lib/test_bitmap.c @@ -585,6 +585,30 @@ static void __init test_bitmap_arr32(void) } } +static void __init test_bitmap_arr64(void) +{ + unsigned int nbits, next_bit; + u64 arr[EXP1_IN_BITS / 64]; + DECLARE_BITMAP(bmap2, EXP1_IN_BITS); + + memset(arr, 0xa5, sizeof(arr)); + + for (nbits = 0; nbits < EXP1_IN_BITS; ++nbits) { + memset(bmap2, 0xff, sizeof(arr)); + bitmap_to_arr64(arr, exp1, nbits); + bitmap_from_arr64(bmap2, arr, nbits); + expect_eq_bitmap(bmap2, exp1, nbits); + + next_bit = find_next_bit(bmap2, round_up(nbits, BITS_PER_LONG), nbits); + if (next_bit < round_up(nbits, BITS_PER_LONG)) + pr_err("bitmap_copy_arr64(nbits == %d:" + " tail is not safely cleared: %d\n", nbits, next_bit); + + if (nbits < EXP1_IN_BITS - 64) + expect_eq_uint(arr[DIV_ROUND_UP(nbits, 64)], 0xa5a5a5a5); + } +} + static void noinline __init test_mem_optimisations(void) { DECLARE_BITMAP(bmap1, 1024); @@ -852,6 +876,7 @@ static void __init selftest(void) test_copy(); test_replace(); test_bitmap_arr32(); + test_bitmap_arr64(); test_bitmap_parse(); test_bitmap_parselist(); test_bitmap_printlist(); -- cgit v1.2.3 From dc34d5036692c614eef23c1130ee42a201c316bf Mon Sep 17 00:00:00 2001 From: Alexander Lobakin Date: Fri, 24 Jun 2022 14:13:13 +0200 Subject: lib: test_bitmap: add compile-time optimization/evaluations assertions Add a function to the bitmap test suite, which will ensure that compilers are able to evaluate operations performed by the bitops/bitmap helpers to compile-time constants when all of the arguments are compile-time constants as well, or trigger a build bug otherwise. This should work on all architectures and all the optimization levels supported by Kbuild. The function doesn't perform any runtime tests and gets optimized out to nothing after passing the build assertions. Unfortunately, Clang for s390 is currently broken (up to the latest Git snapshots) -- see the comment in the code -- so for now there's a small workaround for it which doesn't alter the logics. Hope we'll be able to remove it one day (bugreport is on its way). Suggested-by: Yury Norov Signed-off-by: Alexander Lobakin Reviewed-by: Andy Shevchenko Signed-off-by: Yury Norov --- lib/test_bitmap.c | 62 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 62 insertions(+) (limited to 'lib/test_bitmap.c') diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c index d5923a640457..25967cfa4ab2 100644 --- a/lib/test_bitmap.c +++ b/lib/test_bitmap.c @@ -869,6 +869,67 @@ static void __init test_bitmap_print_buf(void) } } +static void __init test_bitmap_const_eval(void) +{ + DECLARE_BITMAP(bitmap, BITS_PER_LONG); + unsigned long initvar = BIT(2); + unsigned long bitopvar = 0; + unsigned long var = 0; + int res; + + /* + * Compilers must be able to optimize all of those to compile-time + * constants on any supported optimization level (-O2, -Os) and any + * architecture. Otherwise, trigger a build bug. + * The whole function gets optimized out then, there's nothing to do + * in runtime. + */ + + /* + * Equals to `unsigned long bitmap[1] = { GENMASK(6, 5), }`. + * Clang on s390 optimizes bitops at compile-time as intended, but at + * the same time stops treating @bitmap and @bitopvar as compile-time + * constants after regular test_bit() is executed, thus triggering the + * build bugs below. So, call const_test_bit() there directly until + * the compiler is fixed. + */ + bitmap_clear(bitmap, 0, BITS_PER_LONG); +#if defined(__s390__) && defined(__clang__) + if (!const_test_bit(7, bitmap)) +#else + if (!test_bit(7, bitmap)) +#endif + bitmap_set(bitmap, 5, 2); + + /* Equals to `unsigned long bitopvar = BIT(20)` */ + __change_bit(31, &bitopvar); + bitmap_shift_right(&bitopvar, &bitopvar, 11, BITS_PER_LONG); + + /* Equals to `unsigned long var = BIT(25)` */ + var |= BIT(25); + if (var & BIT(0)) + var ^= GENMASK(9, 6); + + /* __const_hweight<32|64>(GENMASK(6, 5)) == 2 */ + res = bitmap_weight(bitmap, 20); + BUILD_BUG_ON(!__builtin_constant_p(res)); + BUILD_BUG_ON(res != 2); + + /* !(BIT(31) & BIT(18)) == 1 */ + res = !test_bit(18, &bitopvar); + BUILD_BUG_ON(!__builtin_constant_p(res)); + BUILD_BUG_ON(!res); + + /* BIT(2) & GENMASK(14, 8) == 0 */ + res = initvar & GENMASK(14, 8); + BUILD_BUG_ON(!__builtin_constant_p(res)); + BUILD_BUG_ON(res); + + /* ~BIT(25) */ + BUILD_BUG_ON(!__builtin_constant_p(~var)); + BUILD_BUG_ON(~var != ~BIT(25)); +} + static void __init selftest(void) { test_zero_clear(); @@ -884,6 +945,7 @@ static void __init selftest(void) test_for_each_set_clump8(); test_bitmap_cut(); test_bitmap_print_buf(); + test_bitmap_const_eval(); } KSTM_MODULE_LOADERS(test_bitmap); -- cgit v1.2.3 From 30fd8cdf53a02b54b199043fcf1857db76e8badc Mon Sep 17 00:00:00 2001 From: Alexander Lobakin Date: Mon, 11 Jul 2022 20:09:30 +0200 Subject: lib/test_bitmap: test the tail after bitmap_to_arr64() Currently, test_bitmap_arr64() only tests bitmap_to_arr64()'s sanity by comparing the result of double-conversion (bm -> arr64 -> bm2) with the input bitmap. However, this may be not enough when one side hides bugs of the second one (e.g. tail clearing, which is being performed by both). Expand the tests and check the tail of the actual arr64 used as a temporary buffer for double-converting. Signed-off-by: Alexander Lobakin Reviewed-by: Andy Shevchenko Signed-off-by: Yury Norov --- lib/test_bitmap.c | 6 ++++++ 1 file changed, 6 insertions(+) (limited to 'lib/test_bitmap.c') diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c index 25967cfa4ab2..98754ff9fe68 100644 --- a/lib/test_bitmap.c +++ b/lib/test_bitmap.c @@ -604,6 +604,12 @@ static void __init test_bitmap_arr64(void) pr_err("bitmap_copy_arr64(nbits == %d:" " tail is not safely cleared: %d\n", nbits, next_bit); + if ((nbits % 64) && + (arr[(nbits - 1) / 64] & ~GENMASK_ULL((nbits - 1) % 64, 0))) + pr_err("bitmap_to_arr64(nbits == %d): tail is not safely cleared: 0x%016llx (must be 0x%016llx)\n", + nbits, arr[(nbits - 1) / 64], + GENMASK_ULL((nbits - 1) % 64, 0)); + if (nbits < EXP1_IN_BITS - 64) expect_eq_uint(arr[DIV_ROUND_UP(nbits, 64)], 0xa5a5a5a5); } -- cgit v1.2.3 From e3783c805db29c8cb3e8dcc8160f6449da1100e3 Mon Sep 17 00:00:00 2001 From: Yury Norov Date: Sat, 17 Sep 2022 20:07:14 -0700 Subject: lib/bitmap: add tests for find_nth_bit() Add functional and performance tests for find_nth_bit(). Signed-off-by: Yury Norov --- lib/find_bit_benchmark.c | 18 ++++++++++++++++++ lib/test_bitmap.c | 47 +++++++++++++++++++++++++++++++++++++++++++++-- 2 files changed, 63 insertions(+), 2 deletions(-) (limited to 'lib/test_bitmap.c') diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c index db904b57d4b8..10754586403b 100644 --- a/lib/find_bit_benchmark.c +++ b/lib/find_bit_benchmark.c @@ -115,6 +115,22 @@ static int __init test_find_last_bit(const void *bitmap, unsigned long len) return 0; } +static int __init test_find_nth_bit(const unsigned long *bitmap, unsigned long len) +{ + unsigned long l, n, w = bitmap_weight(bitmap, len); + ktime_t time; + + time = ktime_get(); + for (n = 0; n < w; n++) { + l = find_nth_bit(bitmap, len, n); + WARN_ON(l >= len); + } + time = ktime_get() - time; + pr_err("find_nth_bit: %18llu ns, %6ld iterations\n", time, w); + + return 0; +} + static int __init test_find_next_and_bit(const void *bitmap, const void *bitmap2, unsigned long len) { @@ -142,6 +158,7 @@ static int __init find_bit_test(void) test_find_next_bit(bitmap, BITMAP_LEN); test_find_next_zero_bit(bitmap, BITMAP_LEN); test_find_last_bit(bitmap, BITMAP_LEN); + test_find_nth_bit(bitmap, BITMAP_LEN / 10); /* * test_find_first_bit() may take some time, so @@ -164,6 +181,7 @@ static int __init find_bit_test(void) test_find_next_bit(bitmap, BITMAP_LEN); test_find_next_zero_bit(bitmap, BITMAP_LEN); test_find_last_bit(bitmap, BITMAP_LEN); + test_find_nth_bit(bitmap, BITMAP_LEN); test_find_first_bit(bitmap, BITMAP_LEN); test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN); test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN); diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c index 98754ff9fe68..da52dc759c95 100644 --- a/lib/test_bitmap.c +++ b/lib/test_bitmap.c @@ -16,6 +16,8 @@ #include "../tools/testing/selftests/kselftest_module.h" +#define EXP1_IN_BITS (sizeof(exp1) * 8) + KSTM_MODULE_GLOBALS(); static char pbl_buffer[PAGE_SIZE] __initdata; @@ -219,6 +221,47 @@ static void __init test_zero_clear(void) expect_eq_pbl("", bmap, 1024); } +static void __init test_find_nth_bit(void) +{ + unsigned long b, bit, cnt = 0; + DECLARE_BITMAP(bmap, 64 * 3); + + bitmap_zero(bmap, 64 * 3); + __set_bit(10, bmap); + __set_bit(20, bmap); + __set_bit(30, bmap); + __set_bit(40, bmap); + __set_bit(50, bmap); + __set_bit(60, bmap); + __set_bit(80, bmap); + __set_bit(123, bmap); + + expect_eq_uint(10, find_nth_bit(bmap, 64 * 3, 0)); + expect_eq_uint(20, find_nth_bit(bmap, 64 * 3, 1)); + expect_eq_uint(30, find_nth_bit(bmap, 64 * 3, 2)); + expect_eq_uint(40, find_nth_bit(bmap, 64 * 3, 3)); + expect_eq_uint(50, find_nth_bit(bmap, 64 * 3, 4)); + expect_eq_uint(60, find_nth_bit(bmap, 64 * 3, 5)); + expect_eq_uint(80, find_nth_bit(bmap, 64 * 3, 6)); + expect_eq_uint(123, find_nth_bit(bmap, 64 * 3, 7)); + expect_eq_uint(64 * 3, find_nth_bit(bmap, 64 * 3, 8)); + + expect_eq_uint(10, find_nth_bit(bmap, 64 * 3 - 1, 0)); + expect_eq_uint(20, find_nth_bit(bmap, 64 * 3 - 1, 1)); + expect_eq_uint(30, find_nth_bit(bmap, 64 * 3 - 1, 2)); + expect_eq_uint(40, find_nth_bit(bmap, 64 * 3 - 1, 3)); + expect_eq_uint(50, find_nth_bit(bmap, 64 * 3 - 1, 4)); + expect_eq_uint(60, find_nth_bit(bmap, 64 * 3 - 1, 5)); + expect_eq_uint(80, find_nth_bit(bmap, 64 * 3 - 1, 6)); + expect_eq_uint(123, find_nth_bit(bmap, 64 * 3 - 1, 7)); + expect_eq_uint(64 * 3 - 1, find_nth_bit(bmap, 64 * 3 - 1, 8)); + + for_each_set_bit(bit, exp1, EXP1_IN_BITS) { + b = find_nth_bit(exp1, EXP1_IN_BITS, cnt++); + expect_eq_uint(b, bit); + } +} + static void __init test_fill_set(void) { DECLARE_BITMAP(bmap, 1024); @@ -557,8 +600,6 @@ static void __init test_bitmap_parse(void) } } -#define EXP1_IN_BITS (sizeof(exp1) * 8) - static void __init test_bitmap_arr32(void) { unsigned int nbits, next_bit; @@ -952,6 +993,8 @@ static void __init selftest(void) test_bitmap_cut(); test_bitmap_print_buf(); test_bitmap_const_eval(); + + test_find_nth_bit(); } KSTM_MODULE_LOADERS(test_bitmap); -- cgit v1.2.3 From 8173aa26260e6d0153db0c7135d41a4da612da5b Mon Sep 17 00:00:00 2001 From: Yury Norov Date: Mon, 19 Sep 2022 14:05:59 -0700 Subject: lib/bitmap: add tests for for_each() loops We have a test for test_for_each_set_clump8 only. Add basic tests for the others. Signed-off-by: Yury Norov --- lib/test_bitmap.c | 244 +++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 243 insertions(+), 1 deletion(-) (limited to 'lib/test_bitmap.c') diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c index da52dc759c95..a8005ad3bd58 100644 --- a/lib/test_bitmap.c +++ b/lib/test_bitmap.c @@ -726,6 +726,239 @@ static void __init test_for_each_set_clump8(void) expect_eq_clump8(start, CLUMP_EXP_NUMBITS, clump_exp, &clump); } +static void __init test_for_each_set_bit_wrap(void) +{ + DECLARE_BITMAP(orig, 500); + DECLARE_BITMAP(copy, 500); + unsigned int wr, bit; + + bitmap_zero(orig, 500); + + /* Set individual bits */ + for (bit = 0; bit < 500; bit += 10) + bitmap_set(orig, bit, 1); + + /* Set range of bits */ + bitmap_set(orig, 100, 50); + + for (wr = 0; wr < 500; wr++) { + bitmap_zero(copy, 500); + + for_each_set_bit_wrap(bit, orig, 500, wr) + bitmap_set(copy, bit, 1); + + expect_eq_bitmap(orig, copy, 500); + } +} + +static void __init test_for_each_set_bit(void) +{ + DECLARE_BITMAP(orig, 500); + DECLARE_BITMAP(copy, 500); + unsigned int bit; + + bitmap_zero(orig, 500); + bitmap_zero(copy, 500); + + /* Set individual bits */ + for (bit = 0; bit < 500; bit += 10) + bitmap_set(orig, bit, 1); + + /* Set range of bits */ + bitmap_set(orig, 100, 50); + + for_each_set_bit(bit, orig, 500) + bitmap_set(copy, bit, 1); + + expect_eq_bitmap(orig, copy, 500); +} + +static void __init test_for_each_set_bit_from(void) +{ + DECLARE_BITMAP(orig, 500); + DECLARE_BITMAP(copy, 500); + unsigned int wr, bit; + + bitmap_zero(orig, 500); + + /* Set individual bits */ + for (bit = 0; bit < 500; bit += 10) + bitmap_set(orig, bit, 1); + + /* Set range of bits */ + bitmap_set(orig, 100, 50); + + for (wr = 0; wr < 500; wr++) { + DECLARE_BITMAP(tmp, 500); + + bitmap_zero(copy, 500); + bit = wr; + + for_each_set_bit_from(bit, orig, 500) + bitmap_set(copy, bit, 1); + + bitmap_copy(tmp, orig, 500); + bitmap_clear(tmp, 0, wr); + expect_eq_bitmap(tmp, copy, 500); + } +} + +static void __init test_for_each_clear_bit(void) +{ + DECLARE_BITMAP(orig, 500); + DECLARE_BITMAP(copy, 500); + unsigned int bit; + + bitmap_fill(orig, 500); + bitmap_fill(copy, 500); + + /* Set individual bits */ + for (bit = 0; bit < 500; bit += 10) + bitmap_clear(orig, bit, 1); + + /* Set range of bits */ + bitmap_clear(orig, 100, 50); + + for_each_clear_bit(bit, orig, 500) + bitmap_clear(copy, bit, 1); + + expect_eq_bitmap(orig, copy, 500); +} + +static void __init test_for_each_clear_bit_from(void) +{ + DECLARE_BITMAP(orig, 500); + DECLARE_BITMAP(copy, 500); + unsigned int wr, bit; + + bitmap_fill(orig, 500); + + /* Set individual bits */ + for (bit = 0; bit < 500; bit += 10) + bitmap_clear(orig, bit, 1); + + /* Set range of bits */ + bitmap_clear(orig, 100, 50); + + for (wr = 0; wr < 500; wr++) { + DECLARE_BITMAP(tmp, 500); + + bitmap_fill(copy, 500); + bit = wr; + + for_each_clear_bit_from(bit, orig, 500) + bitmap_clear(copy, bit, 1); + + bitmap_copy(tmp, orig, 500); + bitmap_set(tmp, 0, wr); + expect_eq_bitmap(tmp, copy, 500); + } +} + +static void __init test_for_each_set_bitrange(void) +{ + DECLARE_BITMAP(orig, 500); + DECLARE_BITMAP(copy, 500); + unsigned int s, e; + + bitmap_zero(orig, 500); + bitmap_zero(copy, 500); + + /* Set individual bits */ + for (s = 0; s < 500; s += 10) + bitmap_set(orig, s, 1); + + /* Set range of bits */ + bitmap_set(orig, 100, 50); + + for_each_set_bitrange(s, e, orig, 500) + bitmap_set(copy, s, e-s); + + expect_eq_bitmap(orig, copy, 500); +} + +static void __init test_for_each_clear_bitrange(void) +{ + DECLARE_BITMAP(orig, 500); + DECLARE_BITMAP(copy, 500); + unsigned int s, e; + + bitmap_fill(orig, 500); + bitmap_fill(copy, 500); + + /* Set individual bits */ + for (s = 0; s < 500; s += 10) + bitmap_clear(orig, s, 1); + + /* Set range of bits */ + bitmap_clear(orig, 100, 50); + + for_each_clear_bitrange(s, e, orig, 500) + bitmap_clear(copy, s, e-s); + + expect_eq_bitmap(orig, copy, 500); +} + +static void __init test_for_each_set_bitrange_from(void) +{ + DECLARE_BITMAP(orig, 500); + DECLARE_BITMAP(copy, 500); + unsigned int wr, s, e; + + bitmap_zero(orig, 500); + + /* Set individual bits */ + for (s = 0; s < 500; s += 10) + bitmap_set(orig, s, 1); + + /* Set range of bits */ + bitmap_set(orig, 100, 50); + + for (wr = 0; wr < 500; wr++) { + DECLARE_BITMAP(tmp, 500); + + bitmap_zero(copy, 500); + s = wr; + + for_each_set_bitrange_from(s, e, orig, 500) + bitmap_set(copy, s, e - s); + + bitmap_copy(tmp, orig, 500); + bitmap_clear(tmp, 0, wr); + expect_eq_bitmap(tmp, copy, 500); + } +} + +static void __init test_for_each_clear_bitrange_from(void) +{ + DECLARE_BITMAP(orig, 500); + DECLARE_BITMAP(copy, 500); + unsigned int wr, s, e; + + bitmap_fill(orig, 500); + + /* Set individual bits */ + for (s = 0; s < 500; s += 10) + bitmap_clear(orig, s, 1); + + /* Set range of bits */ + bitmap_set(orig, 100, 50); + + for (wr = 0; wr < 500; wr++) { + DECLARE_BITMAP(tmp, 500); + + bitmap_fill(copy, 500); + s = wr; + + for_each_clear_bitrange_from(s, e, orig, 500) + bitmap_clear(copy, s, e - s); + + bitmap_copy(tmp, orig, 500); + bitmap_set(tmp, 0, wr); + expect_eq_bitmap(tmp, copy, 500); + } +} + struct test_bitmap_cut { unsigned int first; unsigned int cut; @@ -989,12 +1222,21 @@ static void __init selftest(void) test_bitmap_parselist(); test_bitmap_printlist(); test_mem_optimisations(); - test_for_each_set_clump8(); test_bitmap_cut(); test_bitmap_print_buf(); test_bitmap_const_eval(); test_find_nth_bit(); + test_for_each_set_bit(); + test_for_each_set_bit_from(); + test_for_each_clear_bit(); + test_for_each_clear_bit_from(); + test_for_each_set_bitrange(); + test_for_each_clear_bitrange(); + test_for_each_set_bitrange_from(); + test_for_each_clear_bitrange_from(); + test_for_each_set_clump8(); + test_for_each_set_bit_wrap(); } KSTM_MODULE_LOADERS(test_bitmap); -- cgit v1.2.3