Messages in this thread | | | Date | Mon, 23 Oct 2023 13:49:32 -0700 | From | Yury Norov <> | Subject | Re: [PATCH v8 2/2] lib/test_bitmap: add tests for bitmap_{read,write}() |
| |
On Mon, Oct 23, 2023 at 12:23:27PM +0200, Alexander Potapenko wrote: > Add basic tests ensuring that values can be added at arbitrary positions > of the bitmap, including those spanning into the adjacent unsigned > longs. > > Signed-off-by: Alexander Potapenko <glider@google.com> > Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> > > --- > This patch was previously part of the "Implement MTE tag compression for > swapped pages" series > (https://lore.kernel.org/linux-arm-kernel/20231011172836.2579017-4-glider@google.com/T/) > > This patch was previously called > "lib/test_bitmap: add tests for bitmap_{set,get}_value()" > (https://lore.kernel.org/lkml/20230720173956.3674987-3-glider@google.com/) > and > "lib/test_bitmap: add tests for bitmap_{set,get}_value_unaligned" > (https://lore.kernel.org/lkml/20230713125706.2884502-3-glider@google.com/) > > v8: > - as requested by Andy Shevchenko, add tests for reading/writing > sizes > BITS_PER_LONG > > v7: > - as requested by Yury Norov, add performance tests for bitmap_read() > and bitmap_write() > > v6: > - use bitmap API to initialize test bitmaps > - as requested by Yury Norov, do not check the return value of > bitmap_read(..., 0) > - fix a compiler warning on 32-bit systems > > v5: > - update patch title > - address Yury Norov's comments: > - rename the test cases > - factor out test_bitmap_write_helper() to test writing over > different background patterns; > - add a test case copying a nontrivial value bit-by-bit; > - drop volatile > > v4: > - Address comments by Andy Shevchenko: added Reviewed-by: and a link to > the previous discussion > - Address comments by Yury Norov: > - expand the bitmap to catch more corner cases > - add code testing that bitmap_set_value() does not touch adjacent > bits > - add code testing the nbits==0 case > - rename bitmap_{get,set}_value() to bitmap_{read,write}() > > v3: > - switch to using bitmap_{set,get}_value() > - change the expected bit pattern in test_set_get_value(), > as the test was incorrectly assuming 0 is the LSB. > --- > lib/test_bitmap.c | 174 ++++++++++++++++++++++++++++++++++++++++++++++ > 1 file changed, 174 insertions(+) > > diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c > index f2ea9f30c7c5d..ba567f53feff1 100644 > --- a/lib/test_bitmap.c > +++ b/lib/test_bitmap.c > @@ -71,6 +71,17 @@ __check_eq_uint(const char *srcfile, unsigned int line, > return true; > } > > +static bool __init > +__check_eq_ulong(const char *srcfile, unsigned int line, > + const unsigned long exp_ulong, unsigned long x) > +{ > + if (exp_ulong != x) { > + pr_err("[%s:%u] expected %lu, got %lu\n", > + srcfile, line, exp_ulong, x); > + return false; > + } > + return true; > +} > > static bool __init > __check_eq_bitmap(const char *srcfile, unsigned int line, > @@ -186,6 +197,7 @@ __check_eq_str(const char *srcfile, unsigned int line, > }) > > #define expect_eq_uint(...) __expect_eq(uint, ##__VA_ARGS__) > +#define expect_eq_ulong(...) __expect_eq(ulong, ##__VA_ARGS__) > #define expect_eq_bitmap(...) __expect_eq(bitmap, ##__VA_ARGS__) > #define expect_eq_pbl(...) __expect_eq(pbl, ##__VA_ARGS__) > #define expect_eq_u32_array(...) __expect_eq(u32_array, ##__VA_ARGS__) > @@ -1222,6 +1234,165 @@ static void __init test_bitmap_const_eval(void) > BUILD_BUG_ON(~var != ~BIT(25)); > } > > +/* > + * Test bitmap should be big enough to include the cases when start is not in > + * the first word, and start+nbits lands in the following word. > + */ > +#define TEST_BIT_LEN (1000) > + > +/* > + * Helper function to test bitmap_write() overwriting the chosen byte pattern. > + */ > +static void __init test_bitmap_write_helper(const char *pattern) > +{ > + DECLARE_BITMAP(bitmap, TEST_BIT_LEN); > + DECLARE_BITMAP(exp_bitmap, TEST_BIT_LEN); > + DECLARE_BITMAP(pat_bitmap, TEST_BIT_LEN); > + unsigned long w, r, bit; > + int i, n, nbits; > + > + /* > + * Only parse the pattern once and store the result in the intermediate > + * bitmap. > + */ > + bitmap_parselist(pattern, pat_bitmap, TEST_BIT_LEN); > + > + /* > + * Check that writing a single bit does not accidentally touch the > + * adjacent bits. > + */ > + for (i = 0; i < TEST_BIT_LEN; i++) { > + bitmap_copy(bitmap, pat_bitmap, TEST_BIT_LEN); > + bitmap_copy(exp_bitmap, pat_bitmap, TEST_BIT_LEN); > + for (bit = 0; bit <= 1; bit++) { > + bitmap_write(bitmap, bit, i, 1); > + __assign_bit(i, exp_bitmap, bit); > + expect_eq_bitmap(exp_bitmap, bitmap, > + TEST_BIT_LEN); > + } > + } > + > + /* Ensure writing 0 bits does not change anything. */ > + bitmap_copy(bitmap, pat_bitmap, TEST_BIT_LEN); > + bitmap_copy(exp_bitmap, pat_bitmap, TEST_BIT_LEN); > + for (i = 0; i < TEST_BIT_LEN; i++) { > + bitmap_write(bitmap, ~0UL, i, 0); > + expect_eq_bitmap(exp_bitmap, bitmap, TEST_BIT_LEN); > + } > + > + for (nbits = BITS_PER_LONG; nbits >= 1; nbits--) { > + w = IS_ENABLED(CONFIG_64BIT) ? 0xdeadbeefdeadbeefUL > + : 0xdeadbeefUL; > + w >>= (BITS_PER_LONG - nbits); > + for (i = 0; i <= TEST_BIT_LEN - nbits; i++) { > + bitmap_copy(bitmap, pat_bitmap, TEST_BIT_LEN); > + bitmap_copy(exp_bitmap, pat_bitmap, TEST_BIT_LEN); > + for (n = 0; n < nbits; n++) > + __assign_bit(i + n, exp_bitmap, w & BIT(n)); > + bitmap_write(bitmap, w, i, nbits); > + expect_eq_bitmap(exp_bitmap, bitmap, TEST_BIT_LEN); > + r = bitmap_read(bitmap, i, nbits); > + expect_eq_ulong(r, w); > + } > + } > +} > + > +static void __init test_bitmap_read_write(void) > +{ > + unsigned char *pattern[3] = {"", "all:1/2", "all"}; > + DECLARE_BITMAP(bitmap, TEST_BIT_LEN); > + unsigned long zero_bits = 0, bits_per_long = BITS_PER_LONG; > + unsigned long val; > + int i, pi; > + > + /* > + * Reading/writing zero bits should not crash the kernel. > + * READ_ONCE() prevents constant folding. > + */ > + bitmap_write(NULL, 0, 0, READ_ONCE(zero_bits)); > + /* Return value of bitmap_read() is undefined here. */ > + bitmap_read(NULL, 0, READ_ONCE(zero_bits)); > + > + /* > + * Reading/writing more than BITS_PER_LONG bits should not crash the > + * kernel. READ_ONCE() prevents constant folding. > + */ > + bitmap_write(NULL, 0, 0, READ_ONCE(bits_per_long) + 1); > + /* Return value of bitmap_read() is undefined here. */ > + bitmap_read(NULL, 0, READ_ONCE(bits_per_long) + 1); > + > + /* > + * Ensure that bitmap_read() reads the same value that was previously > + * written, and two consequent values are correctly merged. > + * The resulting bit pattern is asymmetric to rule out possible issues > + * with bit numeration order. > + */ > + for (i = 0; i < TEST_BIT_LEN - 7; i++) { > + bitmap_zero(bitmap, TEST_BIT_LEN); > + > + bitmap_write(bitmap, 0b10101UL, i, 5); > + val = bitmap_read(bitmap, i, 5); > + expect_eq_ulong(0b10101UL, val); > + > + bitmap_write(bitmap, 0b101UL, i + 5, 3); > + val = bitmap_read(bitmap, i + 5, 3); > + expect_eq_ulong(0b101UL, val); > + > + val = bitmap_read(bitmap, i, 8); > + expect_eq_ulong(0b10110101UL, val); > + } > + > + for (pi = 0; pi < ARRAY_SIZE(pattern); pi++) > + test_bitmap_write_helper(pattern[pi]); > +} > + > +static void __init test_bitmap_read_perf(void) > +{ > + DECLARE_BITMAP(bitmap, TEST_BIT_LEN); > + unsigned int cnt, nbits, i; > + unsigned long val; > + ktime_t time; > + > + bitmap_fill(bitmap, TEST_BIT_LEN); > + time = ktime_get(); > + for (cnt = 0; cnt < 5; cnt++) { > + for (nbits = 1; nbits <= BITS_PER_LONG; nbits++) { > + for (i = 0; i < TEST_BIT_LEN; i++) { > + if (i + nbits > TEST_BIT_LEN) > + break; > + val = bitmap_read(bitmap, i, nbits); > + (void)val; > + } > + } > + } > + time = ktime_get() - time; > + pr_err("Time spent in %s:\t%llu\n", __func__, time); > +} > + > +static void __init test_bitmap_write_perf(void) > +{ > + DECLARE_BITMAP(bitmap, TEST_BIT_LEN); > + unsigned int cnt, nbits, i; > + unsigned long val = 0xfeedface; > + ktime_t time; > + > + bitmap_zero(bitmap, TEST_BIT_LEN); > + time = ktime_get(); > + for (cnt = 0; cnt < 5; cnt++) { > + for (nbits = 1; nbits <= BITS_PER_LONG; nbits++) { > + for (i = 0; i < TEST_BIT_LEN; i++) { > + if (i + nbits > TEST_BIT_LEN) > + break; > + bitmap_write(bitmap, val, i, nbits); > + } > + } > + } > + time = ktime_get() - time; > + pr_err("Time spent in %s:\t%llu\n", __func__, time);
For the perf part, can you add the output example to the commit message, and compare numbers with non-optimized for-loop()?
> +} > + > +#undef TEST_BIT_LEN > + > static void __init selftest(void) > { > test_zero_clear(); > @@ -1237,6 +1408,9 @@ static void __init selftest(void) > test_bitmap_cut(); > test_bitmap_print_buf(); > test_bitmap_const_eval(); > + test_bitmap_read_write(); > + test_bitmap_read_perf(); > + test_bitmap_write_perf(); > > test_find_nth_bit(); > test_for_each_set_bit(); > -- > 2.42.0.655.g421f12c284-goog
| |