Message ID | 20231030153210.139512-2-glider@google.com (mailing list archive) |
---|---|
State | New, archived |
Headers | show |
Series | [v11,1/2] lib/bitmap: add bitmap_{read,write}() | expand |
From: Alexander Potapenko <glider@google.com> Date: Mon, 30 Oct 2023 16:32:10 +0100 > Add basic tests ensuring that values can be added at arbitrary positions > of the bitmap, including those spanning into the adjacent unsigned > longs. > > Two new performance tests, test_bitmap_read_perf() and > test_bitmap_write_perf(), can be used to assess future performance > improvements of bitmap_read() and bitmap_write(): > > [ 0.431119][ T1] test_bitmap: Time spent in test_bitmap_read_perf: 615253 > [ 0.433197][ T1] test_bitmap: Time spent in test_bitmap_write_perf: 916313 > > (numbers from a Intel(R) Xeon(R) Gold 6154 CPU @ 3.00GHz machine running > QEMU). > > Signed-off-by: Alexander Potapenko <glider@google.com> > Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> [...] > +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; > +} Could we maybe rather extend __check_eq_uint to take ulongs? Doesn't seem like they differ a lot. > > static bool __init > __check_eq_bitmap(const char *srcfile, unsigned int line, [...] > +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; > + /* > + * Prevent the compiler from optimizing away the > + * bitmap_read() by using its value. > + */ > + WRITE_ONCE(val, bitmap_read(bitmap, i, nbits)); > + } > + } > + } > + time = ktime_get() - time; > + pr_err("Time spent in %s:\t%llu\n", __func__, time); pr_err() is for printing errors and is shown in red by some log readers. Maybe use pr_info() or pr_notice()? Definitely not an error or even warning. > +} > + > +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); (same) > +} > + > +#undef TEST_BIT_LEN > + > static void __init selftest(void) > { > test_zero_clear(); > @@ -1237,6 +1411,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(); Thanks, Olek
> > Could we maybe rather extend __check_eq_uint to take ulongs? Doesn't > seem like they differ a lot. We could redefine expect_eq_uint as: #define expect_eq_uint(x, y) expect_eq_ulong((unsigned int)(x), (unsigned int)(y)) and throw __expect_eq_uint away. > > + } > > + time = ktime_get() - time; > > + pr_err("Time spent in %s:\t%llu\n", __func__, time); > > pr_err() is for printing errors and is shown in red by some log readers. > Maybe use pr_info() or pr_notice()? Definitely not an error or even warning. Note that test_bitmap.c has 17 calls of pr_err() and 7 calls of pr_warn(), which aren't really consistent (e.g. they are used in certain __check helpers instead of pr_err()), and the existing performance tests are calling pr_err(). I can change that in a separate patch, if you think it's worth the effort: the error messages should probably remain pr_err(), but the informational ones could be made pr_info(). > > > +} > > + > > +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); > > (same) > > > +} > > + > > +#undef TEST_BIT_LEN > > + > > static void __init selftest(void) > > { > > test_zero_clear(); > > @@ -1237,6 +1411,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(); > > Thanks, > Olek -- Alexander Potapenko Software Engineer Google Germany GmbH Erika-Mann-Straße, 33 80636 München Geschäftsführer: Paul Manicle, Liana Sebastian Registergericht und -nummer: Hamburg, HRB 86891 Sitz der Gesellschaft: Hamburg
From: Alexander Potapenko <glider@google.com> Date: Thu, 9 Nov 2023 15:28:56 +0100 >> >> Could we maybe rather extend __check_eq_uint to take ulongs? Doesn't >> seem like they differ a lot. > > We could redefine expect_eq_uint as: > > #define expect_eq_uint(x, y) expect_eq_ulong((unsigned > int)(x), (unsigned int)(y)) Do we need explicit casts here tho? > > and throw __expect_eq_uint away. > > >>> + } >>> + time = ktime_get() - time; >>> + pr_err("Time spent in %s:\t%llu\n", __func__, time); >> >> pr_err() is for printing errors and is shown in red by some log readers. >> Maybe use pr_info() or pr_notice()? Definitely not an error or even warning. > > Note that test_bitmap.c has 17 calls of pr_err() and 7 calls of > pr_warn(), which aren't really consistent (e.g. they are used in > certain __check helpers instead of pr_err()), and the existing > performance tests are calling pr_err(). Correct, and that's what caught my attention: visual grepping for bitmap messages makes no sense because some of them are red even thought all tests pass correctly. > I can change that in a separate patch, if you think it's worth the > effort: the error messages should probably remain pr_err(), but the > informational ones could be made pr_info(). Sounds good to be, would be nice to see! [...] >>> @@ -1237,6 +1411,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(); >> >> Thanks, >> Olek > > > > -- > Alexander Potapenko > Software Engineer > > Google Germany GmbH > Erika-Mann-Straße, 33 > 80636 München > > Geschäftsführer: Paul Manicle, Liana Sebastian > Registergericht und -nummer: Hamburg, HRB 86891 > Sitz der Gesellschaft: Hamburg Thanks, Olek
On Thu, Nov 9, 2023 at 3:32 PM Alexander Lobakin <aleksander.lobakin@intel.com> wrote: > > From: Alexander Potapenko <glider@google.com> > Date: Thu, 9 Nov 2023 15:28:56 +0100 > > >> > >> Could we maybe rather extend __check_eq_uint to take ulongs? Doesn't > >> seem like they differ a lot. > > > > We could redefine expect_eq_uint as: > > > > #define expect_eq_uint(x, y) expect_eq_ulong((unsigned > > int)(x), (unsigned int)(y)) > > Do we need explicit casts here tho? > > > > > and throw __expect_eq_uint away. > > > > > >>> + } > >>> + time = ktime_get() - time; > >>> + pr_err("Time spent in %s:\t%llu\n", __func__, time); > >> > >> pr_err() is for printing errors and is shown in red by some log readers. > >> Maybe use pr_info() or pr_notice()? Definitely not an error or even warning. > > > > Note that test_bitmap.c has 17 calls of pr_err() and 7 calls of > > pr_warn(), which aren't really consistent (e.g. they are used in > > certain __check helpers instead of pr_err()), and the existing > > performance tests are calling pr_err(). > > Correct, and that's what caught my attention: visual grepping for bitmap > messages makes no sense because some of them are red even thought all > tests pass correctly. > > > I can change that in a separate patch, if you think it's worth the > > effort: the error messages should probably remain pr_err(), but the > > informational ones could be made pr_info(). > > Sounds good to be, would be nice to see! > > [...] > > >>> @@ -1237,6 +1411,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(); > >> > >> Thanks, > >> Olek > > > > > > > > -- > > Alexander Potapenko > > Software Engineer > > > > Google Germany GmbH > > Erika-Mann-Straße, 33 > > 80636 München > > > > Geschäftsführer: Paul Manicle, Liana Sebastian > > Registergericht und -nummer: Hamburg, HRB 86891 > > Sitz der Gesellschaft: Hamburg > > Thanks, > Olek
On Thu, Nov 9, 2023 at 3:32 PM Alexander Lobakin <aleksander.lobakin@intel.com> wrote: > > From: Alexander Potapenko <glider@google.com> > Date: Thu, 9 Nov 2023 15:28:56 +0100 > > >> > >> Could we maybe rather extend __check_eq_uint to take ulongs? Doesn't > >> seem like they differ a lot. > > > > We could redefine expect_eq_uint as: > > > > #define expect_eq_uint(x, y) expect_eq_ulong((unsigned > > int)(x), (unsigned int)(y)) > > Do we need explicit casts here tho? We do. test_bitmap_arr64() passes u64 values to expect_eq_uint(), which results in test failures. We could add an explicit cast there instead, but I think it's more natural to let the users rely on expect_eq_uint() taking uints.
diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c index f2ea9f30c7c5d..a4195c7376840 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,168 @@ 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; + /* + * Prevent the compiler from optimizing away the + * bitmap_read() by using its value. + */ + WRITE_ONCE(val, bitmap_read(bitmap, i, nbits)); + } + } + } + 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); +} + +#undef TEST_BIT_LEN + static void __init selftest(void) { test_zero_clear(); @@ -1237,6 +1411,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();