[v4,2/5] lib/test_bitmap: add tests for bitmap_{set,get}_value()
Commit Message
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 called
"lib/test_bitmap: add tests for bitmap_{set,get}_value_unaligned"
(https://lore.kernel.org/lkml/20230713125706.2884502-3-glider@google.com/)
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 | 81 +++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 81 insertions(+)
Comments
On Thu, Jul 20, 2023 at 07:39:53PM +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>
[...]
> +/*
> + * 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 (BITS_PER_LONG * 3)
Why not just 1000? Is your code safe against unaligned bitmaps?
> +#define TEST_BYTE_LEN (BITS_TO_LONGS(TEST_BIT_LEN) * sizeof(unsigned long))
BITS_TO_BYTES
> +static void __init test_set_get_value(void)
test_bitmap_read_write. Here, and in subjects for #1 and #2.
> +{
> + DECLARE_BITMAP(bitmap, TEST_BIT_LEN);
> + DECLARE_BITMAP(exp_bitmap, TEST_BIT_LEN);
> + /* Prevent constant folding. */
> + volatile unsigned long zero_bits = 0;
Use READ_ONCE() instead of volatile
> + unsigned long val, bit;
> + int i;
> +
> + /* Setting/getting zero bytes should not crash the kernel. */
> + bitmap_write(NULL, 0, 0, zero_bits);
> + val = bitmap_read(NULL, 0, zero_bits);
> + expect_eq_ulong(0, val);
No, val is undefined.
> +
> + /*
> + * 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++) {
Can you add some empty lines in the block below in sake of
readability? Maybe after expect()?
> + 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);
> + }
> +
> + /*
> + * Check that setting a single bit does not accidentally touch the
> + * adjacent bits.
> + */
> + for (i = 0; i < TEST_BIT_LEN; i++) {
> + /*
> + * A 0b10101010 pattern to catch both 0s replaced to 1s and vice
> + * versa.
> + */
> + memset(bitmap, 0xaa, TEST_BYTE_LEN);
> + memset(exp_bitmap, 0xaa, TEST_BYTE_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);
> + }
I suggested the other test:
val = DEADBEEF;
for (nbits = 1; nbits <= BITS_PER_LONG; nbits++)
for (start = 0; start < 1000; i++) {
if (start + nbits >= 1000)
break;;
v = val & GENMASK(nbits - 1, 0);
memset(bitmap, 0xaa /* also 0xff and 0x00 */, TEST_BYTE_LEN);
memset(exp_bitmap, 0xaa, TEST_BYTE_LEN);
for (n = 0; n < nbits; n++)
__assign_bit(v & BIT(n), exp_bitmap, start + n);
bitmap_write(bitmap, v, start, nbits);
expect_eq_bitmap(exp_bitmap, bitmap, 1000);
r = bitmap_read(bitmap, start, nbits);
expect_eq(r, v);
}
> + }
> +
> + /* Ensure setting 0 bits does not change anything. */
> + memset(bitmap, 0xaa, TEST_BYTE_LEN);
> + memset(exp_bitmap, 0xaa, TEST_BYTE_LEN);
> + for (i = 0; i < TEST_BIT_LEN; i++) {
> + bitmap_write(bitmap, ~0UL, i, 0);
> + expect_eq_bitmap(exp_bitmap, bitmap, TEST_BIT_LEN);
> + }
> +}
> +#undef TEST_BYTE_LEN
> +#undef TEST_BIT_LEN
> +
> static void __init selftest(void)
> {
> test_zero_clear();
> @@ -1249,6 +1328,8 @@ static void __init selftest(void)
> test_for_each_clear_bitrange_from();
> test_for_each_set_clump8();
> test_for_each_set_bit_wrap();
> +
> + test_set_get_value();
This should append the test_bitmap_* section
Thanks,
Yury
> > +/*
> > + * 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 (BITS_PER_LONG * 3)
>
> Why not just 1000? Is your code safe against unaligned bitmaps?
done
> > +#define TEST_BYTE_LEN (BITS_TO_LONGS(TEST_BIT_LEN) * sizeof(unsigned long))
>
> BITS_TO_BYTES
done
>
> > +static void __init test_set_get_value(void)
>
> test_bitmap_read_write. Here, and in subjects for #1 and #2.
done
> > +{
> > + DECLARE_BITMAP(bitmap, TEST_BIT_LEN);
> > + DECLARE_BITMAP(exp_bitmap, TEST_BIT_LEN);
> > + /* Prevent constant folding. */
> > + volatile unsigned long zero_bits = 0;
>
> Use READ_ONCE() instead of volatile
done
> > + unsigned long val, bit;
> > + int i;
> > +
> > + /* Setting/getting zero bytes should not crash the kernel. */
> > + bitmap_write(NULL, 0, 0, zero_bits);
> > + val = bitmap_read(NULL, 0, zero_bits);
> > + expect_eq_ulong(0, val);
>
> No, val is undefined.
Why? bitmap_read(..., ..., 0) always returns 0.
>
> > +
> > + /*
> > + * 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++) {
>
> Can you add some empty lines in the block below in sake of
> readability? Maybe after expect()?
Done
(snip)
> I suggested the other test:
>
> val = DEADBEEF;
> for (nbits = 1; nbits <= BITS_PER_LONG; nbits++)
> for (start = 0; start < 1000; i++) {
> if (start + nbits >= 1000)
> break;;
>
> v = val & GENMASK(nbits - 1, 0);
>
> memset(bitmap, 0xaa /* also 0xff and 0x00 */, TEST_BYTE_LEN);
> memset(exp_bitmap, 0xaa, TEST_BYTE_LEN);
>
> for (n = 0; n < nbits; n++)
> __assign_bit(v & BIT(n), exp_bitmap, start + n);
>
> bitmap_write(bitmap, v, start, nbits);
> expect_eq_bitmap(exp_bitmap, bitmap, 1000);
>
> r = bitmap_read(bitmap, start, nbits);
> expect_eq(r, v);
> }
I factored out test cases that can benefit from different background
patterns into a separate function and added yours there. Thanks!
> > @@ -1249,6 +1328,8 @@ static void __init selftest(void)
> > test_for_each_clear_bitrange_from();
> > test_for_each_set_clump8();
> > test_for_each_set_bit_wrap();
> > +
> > + test_set_get_value();
>
> This should append the test_bitmap_* section
Done
> Thanks,
> Yury
Thanks a lot for your comments!
On Fri, Sep 22, 2023 at 09:57:32AM +0200, Alexander Potapenko wrote:
> > > + unsigned long val, bit;
> > > + int i;
> > > +
> > > + /* Setting/getting zero bytes should not crash the kernel. */
> > > + bitmap_write(NULL, 0, 0, zero_bits);
> > > + val = bitmap_read(NULL, 0, zero_bits);
> > > + expect_eq_ulong(0, val);
> >
> > No, val is undefined.
>
> Why? bitmap_read(..., ..., 0) always returns 0.
Because it's unexpected and most likely wrong to pass 0 bits. We
guarantee that bitmap_read() will return immediately, and will not
touch the memory. But we don't guarantee that we return any specific
value.
It's not a hot path, at least now, and we can spend few extra cycles
to clear output register and return 0, but user should not rely on it
in any way, especially in a test that is intended to show an example
of using the new API.
Consider a less relaxed environment, where we really have to count
cycles. In such environment, we'd return a content of the 1st input
argument, just because it's already in R0, and compiled doesn't have
to:
mov r0, #0
ret
On Fri, Sep 22, 2023 at 3:30 PM Yury Norov <yury.norov@gmail.com> wrote:
>
> On Fri, Sep 22, 2023 at 09:57:32AM +0200, Alexander Potapenko wrote:
> > > > + unsigned long val, bit;
> > > > + int i;
> > > > +
> > > > + /* Setting/getting zero bytes should not crash the kernel. */
> > > > + bitmap_write(NULL, 0, 0, zero_bits);
> > > > + val = bitmap_read(NULL, 0, zero_bits);
> > > > + expect_eq_ulong(0, val);
> > >
> > > No, val is undefined.
> >
> > Why? bitmap_read(..., ..., 0) always returns 0.
>
> Because it's unexpected and most likely wrong to pass 0 bits. We
> guarantee that bitmap_read() will return immediately, and will not
> touch the memory. But we don't guarantee that we return any specific
> value.
Fair enough, I'll remove the expect_eq_ulong() from the test in v6 and
will also add the requirement for nbits to be nonzero to the doc
comments for bitmap_read() and bitmap_write().
> It's not a hot path, at least now, and we can spend few extra cycles
> to clear output register and return 0, but user should not rely on it
> in any way, especially in a test that is intended to show an example
> of using the new API.
Ok, for now I'll keep the "return 0" part.
> Consider a less relaxed environment, where we really have to count
> cycles. In such environment, we'd return a content of the 1st input
> argument, just because it's already in R0, and compiled doesn't have
> to:
>
> mov r0, #0
> ret
@@ -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,73 @@ 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 (BITS_PER_LONG * 3)
+#define TEST_BYTE_LEN (BITS_TO_LONGS(TEST_BIT_LEN) * sizeof(unsigned long))
+static void __init test_set_get_value(void)
+{
+ DECLARE_BITMAP(bitmap, TEST_BIT_LEN);
+ DECLARE_BITMAP(exp_bitmap, TEST_BIT_LEN);
+ /* Prevent constant folding. */
+ volatile unsigned long zero_bits = 0;
+ unsigned long val, bit;
+ int i;
+
+ /* Setting/getting zero bytes should not crash the kernel. */
+ bitmap_write(NULL, 0, 0, zero_bits);
+ val = bitmap_read(NULL, 0, zero_bits);
+ expect_eq_ulong(0, val);
+
+ /*
+ * 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);
+ }
+
+ /*
+ * Check that setting a single bit does not accidentally touch the
+ * adjacent bits.
+ */
+ for (i = 0; i < TEST_BIT_LEN; i++) {
+ /*
+ * A 0b10101010 pattern to catch both 0s replaced to 1s and vice
+ * versa.
+ */
+ memset(bitmap, 0xaa, TEST_BYTE_LEN);
+ memset(exp_bitmap, 0xaa, TEST_BYTE_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 setting 0 bits does not change anything. */
+ memset(bitmap, 0xaa, TEST_BYTE_LEN);
+ memset(exp_bitmap, 0xaa, TEST_BYTE_LEN);
+ for (i = 0; i < TEST_BIT_LEN; i++) {
+ bitmap_write(bitmap, ~0UL, i, 0);
+ expect_eq_bitmap(exp_bitmap, bitmap, TEST_BIT_LEN);
+ }
+}
+#undef TEST_BYTE_LEN
+#undef TEST_BIT_LEN
+
static void __init selftest(void)
{
test_zero_clear();
@@ -1249,6 +1328,8 @@ static void __init selftest(void)
test_for_each_clear_bitrange_from();
test_for_each_set_clump8();
test_for_each_set_bit_wrap();
+
+ test_set_get_value();
}
KSTM_MODULE_LOADERS(test_bitmap);