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

From: Mathieu Desnoyers
Date: Tue Aug 20 2024 - 13:20:43 EST


On 2024-08-19 21:19, Yury Norov wrote:
[...[> Can you split rewording of existing comments out to a separate patch
please?

Will do.


*/
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.

OK


+/**
+ * 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...

I'll do this for the next round. Yes, it would be good to add
those explanations on top of the file.

Thanks for the review !

Mathieu


Thanks,
Yury

--
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com