| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <ZsOatkpPqzMF6B_c@yury-ThinkPad>
Date: Mon, 19 Aug 2024 12:19:18 -0700
From: Yury Norov <yury.norov@...il.com>
To: Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
Cc: Peter Zijlstra <peterz@...radead.org>, Ingo Molnar <mingo@...hat.com>,
linux-kernel@...r.kernel.org,
Valentin Schneider <vschneid@...hat.com>,
Mel Gorman <mgorman@...e.de>, Steven Rostedt <rostedt@...dmis.org>,
Vincent Guittot <vincent.guittot@...aro.org>,
Dietmar Eggemann <dietmar.eggemann@....com>,
Ben Segall <bsegall@...gle.com>,
Rasmus Villemoes <linux@...musvillemoes.dk>,
Shuah Khan <skhan@...uxfoundation.org>
Subject: Re: [RFC PATCH 1/5] lib: Implement
find_{first,next,nth}_notandnot_bit, find_first_andnot_bit
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@...icios.com>
> Cc: Yury Norov <yury.norov@...il.com>
> Cc: Rasmus Villemoes <linux@...musvillemoes.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
Powered by blists - more mailing lists