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

[Yury Norov]

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 at 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