Re: [PATCH 3/6] bitops: bitmap helper to set variable length values

Yury Norov
2022-07-13T18:49:48Z

On Wed, Jul 13, 2022 at 06:31:59PM +0200, Sebastian Fricke wrote:
> Add a new helper to set variable length values within a bitmap, that can
> overflow the borders of a single BITS_PER_LONG container.
> This function makes it easier to write values to hardware memory blobs that
> do not require alignment.
>
> Add tests to the lib/test_bitmap.c kselftest module to verify proper function.
>
> Signed-off-by: Sebastian Fricke <sebastian.fricke@collabora.com>
> ---
> include/linux/bitmap.h | 40 +++++++++++++++++++++++++++++++++++
> lib/test_bitmap.c | 48 ++++++++++++++++++++++++++++++++++++++++++
> 2 files changed, 88 insertions(+)
>
> diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
> index 2e6cd5681040..9f8d635b70a9 100644
> --- a/include/linux/bitmap.h
> +++ b/include/linux/bitmap.h
> @@ -76,6 +76,7 @@ struct device;
> * bitmap_to_arr64(buf, src, nbits) Copy nbits from buf to u64[] dst
> * bitmap_get_value8(map, start) Get 8bit value from map at start
> * bitmap_set_value8(map, value, start) Set 8bit value to map at start
> + * bitmap_set_value(map, value, start, nbits) Set a variable length value to map at start
> *
> * Note, bitmap_zero() and bitmap_fill() operate over the region of
> * unsigned longs, that is, bits behind bitmap till the unsigned long
> @@ -573,6 +574,45 @@ static inline void bitmap_set_value8(unsigned long *map, unsigned long value,
> map[index] |= value << offset;
> }
>
> +/**
> + * bitmap_set_value - set a variable length value within a memory region
> + * @map: address to the bitmap memory region
> + * @value: the variable length value
> + * @start: bit offset of the value
> + * @length: Length of the value

There's no such thing like a length of value. Data structures and
types have size, and arrays have length.

> + */
> +static inline void bitmap_set_value(unsigned long *map, unsigned long value,
> + unsigned long start, unsigned char length)
> +{
> + size_t index = BIT_WORD(start);
> + unsigned long offset = start % BITS_PER_LONG;
> + int diff_to_max = 0;
> +
> + if (!length)
> + return;
> +
> +

2nd empty line is not needed. Actually, all this chunk is not needed
because 'while (length > 0)' will do the work.

> + if (length < BITS_PER_LONG)
> + value &= (BIT(length) - 1);
> +
> + while (length > 0) {
> + diff_to_max = BITS_PER_LONG - offset;
> + map[index] &= ~((BIT(length) - 1) << offset);
> + if (length > diff_to_max) {
> + unsigned long tmp = value & (BIT(diff_to_max) - 1);

We have GENMASK() for this.

> +
> + map[index] |= tmp << offset;
> + value >>= diff_to_max;
> + length -= diff_to_max;
> + index += 1;
> + offset = 0;
> + } else {
> + map[index] |= value << offset;
> + length = 0;
> + }
> + }

I have a strong feeling that this can be written much simpler...

But anyways, this is not suitable for generic bitmaps because this
bitmap_set_value() is limited with a single words. All bitmap functions
that copy data to/from bitmap are able to work with bigger chunks. (With
the exception of bitmap_{set,get}_value8, which doesn't allow unaligned
accesses.)

What you want is to copy bits to the dst bitmap starting from the offset,
right? It's very similar to what bitmap_set() does, except that it always
'copies' ~0UL.

I'd suggest you to try implementing
bitmap_copy_from(dst, src, dst_off, len)
or even
bitmap_copy_from(dst, dst_off, src, src_off, len)
if you expect that you'll need more flexibility in the future.

This bitmap_copy_from() may be based, for example, on extended version
of __bitmap_set():
void __bitmap_set(unsigned long *dst, unsigned long *src, unsigned int start, int len)

Thanks,
Yury

> +}
> +
> #endif /* __ASSEMBLY__ */
>
> #endif /* __LINUX_BITMAP_H */
> diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c
> index d5923a640457..509317ad2f72 100644
> --- a/lib/test_bitmap.c
> +++ b/lib/test_bitmap.c
> @@ -869,6 +869,53 @@ static void __init test_bitmap_print_buf(void)
> }
> }
>
> +struct test_bitmap_set_value_sample {
> + unsigned long value[2];
> + unsigned char length[2];
> + unsigned int offset[2];
> + unsigned long expected[2][2];
> + int amount;
> +};
> +
> +static const struct test_bitmap_set_value_sample test_set[] __initconst = {
> + /* Check that multiple values can be chained up */
> + { {10, 20}, {4, 5}, {0, 4}, {{10, 330}}, 2 },
> + /* Check that a value can be set across two BITS_PER_LONG chunks */
> + { {10, 6}, {4, 3}, {0, 63}, {{10, 10}, {0, 3}}, 2 },
> + /* Set a value with length shorter than the given length */
> + { {3, 6}, {4, 10}, {0, 4}, {{3, 99}}, 1 },
> + /* Set a value with length longer than the given length */
> + { {15}, {2}, {0}, {{3}}, 1 },
> + /* Check that values are properly overwritten */
> + { {15, 12}, {4, 4}, {0, 2}, {{15, 51}}, 2 },
> + /* Check that a set without a length doesn't change anything */
> + { {10}, {0}, {0}, {{0}}, 1 },
> +};
> +
> +static void __init test_bitmap_set_value(void)
> +{
> + int i, j, k;
> + int correct_tests = 0;
> +
> + for (i = 0; i < ARRAY_SIZE(test_set); i++) {
> + const struct test_bitmap_set_value_sample *t = &test_set[i];
> + int test_correct = 1;
> + DECLARE_BITMAP(map, BITS_PER_LONG * 2);
> +
> + bitmap_zero(map, BITS_PER_LONG * 2);
> + for (j = 0; j < t->amount; j++) {
> + bitmap_set_value(map, t->value[j], t->offset[j], t->length[j]);
> + for (k = 0; k < 2; k++) {
> + if (expect_eq_uint(map[k], t->expected[k][j]))
> + test_correct = 0;
> + }
> + }
> + if (test_correct)
> + correct_tests += 1;
> + }
> + pr_err("set_value: %d/%ld tests correct\n", correct_tests, ARRAY_SIZE(test_set));
> +}
> +
> static void __init selftest(void)
> {
> test_zero_clear();
> @@ -884,6 +931,7 @@ static void __init selftest(void)
> test_for_each_set_clump8();
> test_bitmap_cut();
> test_bitmap_print_buf();
> + test_bitmap_set_value();
> }
>
> KSTM_MODULE_LOADERS(test_bitmap);
> --
> 2.25.1