Re: [RFC PATCH 1/5] lib: Implement find_{first,next,nth}_notandnot_bit, find_first_andnot_bit

[Yury Norov <yury.norov@gmail.com>]

On Mon, Aug 19, 2024 at 04:24:02PM +0200, Mathieu Desnoyers wrote:
> Allow finding the first, next, or nth bit within two input bitmasks
> which is zero in both masks.
> 
> Allow fiding the first bit within two input bitmasks which is set in
> first mask and cleared in the second mask. find_next_andnot_bit and
> find_nth_andnot_bit already exist, so find the first bit appears to be
> missing.
> 
> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> Cc: Yury Norov <yury.norov@gmail.com>
> Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk>
> ---
>  include/linux/find.h | 122 +++++++++++++++++++++++++++++++++++++++++--
>  lib/find_bit.c       |  42 +++++++++++++++
>  2 files changed, 160 insertions(+), 4 deletions(-)
> 
> diff --git a/include/linux/find.h b/include/linux/find.h
> index 5dfca4225fef..6b2377006b22 100644
> --- a/include/linux/find.h
> +++ b/include/linux/find.h
> @@ -14,6 +14,8 @@ unsigned long _find_next_and_bit(const unsigned long *addr1, const unsigned long
>  					unsigned long nbits, unsigned long start);
>  unsigned long _find_next_andnot_bit(const unsigned long *addr1, const unsigned long *addr2,
>  					unsigned long nbits, unsigned long start);
> +unsigned long _find_next_notandnot_bit(const unsigned long *addr1, const unsigned long *addr2,
> +					unsigned long nbits, unsigned long start);
>  unsigned long _find_next_or_bit(const unsigned long *addr1, const unsigned long *addr2,
>  					unsigned long nbits, unsigned long start);
>  unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long nbits,
> @@ -24,11 +26,17 @@ unsigned long __find_nth_and_bit(const unsigned long *addr1, const unsigned long
>  				unsigned long size, unsigned long n);
>  unsigned long __find_nth_andnot_bit(const unsigned long *addr1, const unsigned long *addr2,
>  					unsigned long size, unsigned long n);
> +unsigned long __find_nth_notandnot_bit(const unsigned long *addr1, const unsigned long *addr2,
> +					unsigned long size, unsigned long n);
>  unsigned long __find_nth_and_andnot_bit(const unsigned long *addr1, const unsigned long *addr2,
>  					const unsigned long *addr3, unsigned long size,
>  					unsigned long n);
>  extern unsigned long _find_first_and_bit(const unsigned long *addr1,
>  					 const unsigned long *addr2, unsigned long size);
> +extern unsigned long _find_first_andnot_bit(const unsigned long *addr1,
> +					 const unsigned long *addr2, unsigned long size);
> +extern unsigned long _find_first_notandnot_bit(const unsigned long *addr1,
> +					 const unsigned long *addr2, unsigned long size);
>  unsigned long _find_first_and_and_bit(const unsigned long *addr1, const unsigned long *addr2,
>  				      const unsigned long *addr3, unsigned long size);
>  extern unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size);
> @@ -102,15 +110,14 @@ unsigned long find_next_and_bit(const unsigned long *addr1,
>  
>  #ifndef find_next_andnot_bit
>  /**
> - * find_next_andnot_bit - find the next set bit in *addr1 excluding all the bits
> - *                        in *addr2
> + * find_next_andnot_bit - find the next set bit in *addr1, cleared in *addr2
>   * @addr1: The first address to base the search on
>   * @addr2: The second address to base the search on
>   * @size: The bitmap size in bits
>   * @offset: The bitnumber to start searching at
>   *
> - * Returns the bit number for the next set bit
> - * If no bits are set, returns @size.
> + * Returns the bit number for the next bit set in *addr1, cleared in *addr2.
> + * If no such bits are found, returns @size.

Can you split rewording of existing comments out to a separate patch
please?

>   */
>  static inline
>  unsigned long find_next_andnot_bit(const unsigned long *addr1,
> @@ -131,6 +138,36 @@ unsigned long find_next_andnot_bit(const unsigned long *addr1,
>  }
>  #endif
>  
> +#ifndef find_next_notandnot_bit

Don't protect new functions. This is only for those having arch
implementation, and it's only armv7 now.

> +/**
> + * find_next_notandnot_bit - find the next bit cleared in both *addr1 and *addr2
> + * @addr1: The first address to base the search on
> + * @addr2: The second address to base the search on
> + * @size: The bitmap size in bits
> + * @offset: The bitnumber to start searching at
> + *
> + * Returns the bit number for the next bit cleared in both *addr1 and *addr2.
> + * If no such bits are found, returns @size.
> + */
> +static inline
> +unsigned long find_next_notandnot_bit(const unsigned long *addr1,
> +		const unsigned long *addr2, unsigned long size,
> +		unsigned long offset)
> +{
> +	if (small_const_nbits(size)) {
> +		unsigned long val;
> +
> +		if (unlikely(offset >= size))
> +			return size;
> +
> +		val = (~*addr1) & (~*addr2) & GENMASK(size - 1, offset);
> +		return val ? __ffs(val) : size;
> +	}
> +
> +	return _find_next_notandnot_bit(addr1, addr2, size, offset);
> +}
> +#endif
> +

It's not said explicitly, but some naming conventions exist around bitmap
searching.

If you're looking for a clear (unset) bit in a mask, you'd use a 'zero'
modifier. We have only 2 such functions now: find_{first,next}_zero_bit,
both taking one bitmap. I think it's time to extend this rule for
many bitmaps and write down the naming rules.

With the following, the find_next_notandnot_bit() should be named
like; find_next_zero_and_bit(). It's not perfect, but still sounds
better to me than 'notandnot' thing.

If we search for a set bit in bitmap, we use find_first or find_next
prefixes:
 - find_first_bit;
 - find_next_bit.

If we'd like to pass an additional bitmap to AND, OR or XOR with the
1st bitmap, we provide as corresponding logical operation as
suffix(es):
 - find_first_and_bit(b1, b2) : b1 & b2;
 - find _next_and_or_bit(b1, b2, b3) : b1 & b2 | b3.

If additional bitmap must be inverted, we provide a 'not' after the
corresponding logical operation:
 - find_first_andnot_bit(b1, b2) : b1 & ~b2;
 - find _next_and_ornot_bit(b1, b2, b3) : b1 & b2 | ~b3.

If all bitmaps have to be inverted, or in other words, we are looking
for an unset bit in a bitmap or a combination of bitmaps, we provide
a 'zero' prefix in the function name:
 - find_next_zero_bit;
 - find_next_zero_and_bit;
 - find_next_zero_and_or_bit;

Functions having 'zero' prefix should not negate bitmaps (should not
have 'not' in names) because of commutative property. For example,
find_next_zero_andnot_bit(), which is ~b1 & ~(~b2) is redundant
because it's the same as find_next_andnot_bit() : b2 & ~b1.

Iterators over unset bits in bitmap(s) (those based on 'zero' search
functions) should have a 'clear' prefix in the name:
 - for_each_clear_bit;
 - for_each_clear_bit_from;

I should probably put the above on top of the file...

Thanks,
Yury