[PATCH v2 1/3] gpiolib: Introduce the for_each_set_clump macro

[William Breathitt Gray]

On Fri, Feb 12, 2021 at 06:50:20PM +0530, Syed Nayyar Waris wrote:
> This macro iterates for each group of bits (clump) with set bits,
> within a bitmap memory region. For each iteration, "start" is set to
> the bit offset of the found clump, while the respective clump value is
> stored to the location pointed by "clump". Additionally, the
> bitmap_get_value() and bitmap_set_value() functions are introduced to
> respectively get and set a value of n-bits in a bitmap memory region.
> The n-bits can have any size from 1 to BITS_PER_LONG. size less
> than 1 or more than BITS_PER_LONG causes undefined behaviour.
> Moreover, during setting value of n-bit in bitmap, if a situation arise
> that the width of next n-bit is exceeding the word boundary, then it
> will divide itself such that some portion of it is stored in that word,
> while the remaining portion is stored in the next higher word. Similar
> situation occurs while retrieving the value from bitmap.
> 
> Cc: Linus Walleij <linus.walleij at linaro.org>
> Cc: Bartosz Gołaszewski <bgolaszewski at baylibre.com>
> Cc: Arnd Bergmann <arnd at arndb.de>
> Cc: William Breathitt Gray <vilhelm.gray at gmail.com>
> Cc: Andy Shevchenko <andriy.shevchenko at linux.intel.com>
> Signed-off-by: Syed Nayyar Waris <syednwaris at gmail.com>

I think it would be good to retire the "clump" nomenclature and instead
call this macro for_each_set_nbits in order to match the existing
convention used by the bitmap functions. But I don't feel strongly
enough to nitpick on that, so this version looks good to me as is.

Acked-by: William Breathitt Gray <vilhelm.gray at gmail.com>

> ---
>  drivers/gpio/gpiolib.c | 90 ++++++++++++++++++++++++++++++++++++++++++
>  drivers/gpio/gpiolib.h | 28 +++++++++++++
>  2 files changed, 118 insertions(+)
> 
> diff --git a/drivers/gpio/gpiolib.c b/drivers/gpio/gpiolib.c
> index b02cc2abd3b6..282ae599c143 100644
> --- a/drivers/gpio/gpiolib.c
> +++ b/drivers/gpio/gpiolib.c
> @@ -4342,6 +4342,96 @@ static int gpiolib_seq_show(struct seq_file *s, void *v)
>  	return 0;
>  }
>  
> +/**
> + * bitmap_get_value - get a value of n-bits from the memory region
> + * @map: address to the bitmap memory region
> + * @start: bit offset of the n-bit value
> + * @nbits: size of value in bits (must be between 1 and BITS_PER_LONG inclusive).
> + *
> + * Returns value of nbits located at the @start bit offset within the @map
> + * memory region.
> + */
> +unsigned long bitmap_get_value(const unsigned long *map,
> +				unsigned long start,
> +				unsigned long nbits)
> +{
> +	const size_t index = BIT_WORD(start);
> +	const unsigned long offset = start % BITS_PER_LONG;
> +	const unsigned long ceiling = round_up(start + 1, BITS_PER_LONG);
> +	const unsigned long space = ceiling - start;
> +	unsigned long value_low, value_high;
> +
> +	if (space >= nbits)
> +		return (map[index] >> offset) & GENMASK(nbits - 1, 0);
> +	else {
> +		value_low = map[index] & BITMAP_FIRST_WORD_MASK(start);
> +		value_high = map[index + 1] & BITMAP_LAST_WORD_MASK(start + nbits);
> +		return (value_low >> offset) | (value_high << space);
> +	}
> +}
> +EXPORT_SYMBOL_GPL(bitmap_get_value);
> +
> +/**
> + * bitmap_set_value - set value within a memory region
> + * @map: address to the bitmap memory region
> + * @nbits: size of map in bits
> + * @value: value of clump
> + * @value_width: size of value in bits (must be between 1 and BITS_PER_LONG inclusive)
> + * @start: bit offset of the value
> + */
> +void bitmap_set_value(unsigned long *map, unsigned long nbits,
> +			unsigned long value, unsigned long value_width,
> +			unsigned long start)
> +{
> +	const unsigned long index = BIT_WORD(start);
> +	const unsigned long length = BIT_WORD(nbits);
> +	const unsigned long offset = start % BITS_PER_LONG;
> +	const unsigned long ceiling = round_up(start + 1, BITS_PER_LONG);
> +	const unsigned long space = ceiling - start;
> +
> +	value &= GENMASK(value_width - 1, 0);
> +
> +	if (space >= value_width) {
> +		map[index] &= ~(GENMASK(value_width - 1, 0) << offset);
> +		map[index] |= value << offset;
> +	} else {
> +		map[index + 0] &= ~BITMAP_FIRST_WORD_MASK(start);
> +		map[index + 0] |= value << offset;
> +
> +		if (index + 1 >= length)
> +			return;
> +
> +		map[index + 1] &= ~BITMAP_LAST_WORD_MASK(start + value_width);
> +		map[index + 1] |= value >> space;
> +	}
> +}
> +EXPORT_SYMBOL_GPL(bitmap_set_value);
> +
> +/**
> + * find_next_clump - find next clump with set bits in a memory region
> + * @clump: location to store copy of found clump
> + * @addr: address to base the search on
> + * @size: bitmap size in number of bits
> + * @offset: bit offset at which to start searching
> + * @clump_size: clump size in bits
> + *
> + * Returns the bit offset for the next set clump; the found clump value is
> + * copied to the location pointed by @clump. If no bits are set, returns @size.
> + */
> +unsigned long find_next_clump(unsigned long *clump, const unsigned long *addr,
> +				unsigned long size, unsigned long offset,
> +				unsigned long clump_size)
> +{
> +	offset = find_next_bit(addr, size, offset);
> +	if (offset == size)
> +		return size;
> +
> +	offset = rounddown(offset, clump_size);
> +	*clump = bitmap_get_value(addr, offset, clump_size);
> +	return offset;
> +}
> +EXPORT_SYMBOL_GPL(find_next_clump);
> +
>  static const struct seq_operations gpiolib_sops = {
>  	.start = gpiolib_seq_start,
>  	.next = gpiolib_seq_next,
> diff --git a/drivers/gpio/gpiolib.h b/drivers/gpio/gpiolib.h
> index 30bc3f80f83e..41c6b24d9842 100644
> --- a/drivers/gpio/gpiolib.h
> +++ b/drivers/gpio/gpiolib.h
> @@ -141,6 +141,34 @@ int gpio_set_debounce_timeout(struct gpio_desc *desc, unsigned int debounce);
>  int gpiod_hog(struct gpio_desc *desc, const char *name,
>  		unsigned long lflags, enum gpiod_flags dflags);
>  
> +unsigned long bitmap_get_value(const unsigned long *map,
> +				unsigned long start,
> +				unsigned long nbits);
> +
> +void bitmap_set_value(unsigned long *map, unsigned long nbits,
> +			unsigned long value, unsigned long value_width,
> +			unsigned long start);
> +
> +unsigned long find_next_clump(unsigned long *clump, const unsigned long *addr,
> +				unsigned long size, unsigned long offset,
> +				unsigned long clump_size);
> +
> +#define find_first_clump(clump, bits, size, clump_size) \
> +	find_next_clump((clump), (bits), (size), 0, (clump_size))
> +
> +/**
> + * for_each_set_clump - iterate over bitmap for each clump with set bits
> + * @start: bit offset to start search and to store the current iteration offset
> + * @clump: location to store copy of current 8-bit clump
> + * @bits: bitmap address to base the search on
> + * @size: bitmap size in number of bits
> + * @clump_size: clump size in bits
> + */
> +#define for_each_set_clump(start, clump, bits, size, clump_size) \
> +	for ((start) = find_first_clump(&(clump), (bits), (size), (clump_size)); \
> +	     (start) < (size); \
> +	     (start) = find_next_clump(&(clump), (bits), (size), (start) + (clump_size), (clump_size)))
> +
>  /*
>   * Return the GPIO number of the passed descriptor relative to its chip
>   */
> -- 
> 2.29.0
> 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: not available
URL: <http://lists.infradead.org/pipermail/linux-arm-kernel/attachments/20210214/a634289b/attachment.sig>