| 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
| ||
|
Date: Tue, 16 Aug 2022 15:13:48 -0700
From: Yury Norov <yury.norov@...il.com>
To: Valentin Schneider <vschneid@...hat.com>
Cc: netdev@...r.kernel.org, linux-rdma@...r.kernel.org,
linux-kernel@...r.kernel.org, Saeed Mahameed <saeedm@...dia.com>,
Leon Romanovsky <leon@...nel.org>,
"David S. Miller" <davem@...emloft.net>,
Eric Dumazet <edumazet@...gle.com>,
Jakub Kicinski <kuba@...nel.org>,
Paolo Abeni <pabeni@...hat.com>,
Andy Shevchenko <andriy.shevchenko@...ux.intel.com>,
Rasmus Villemoes <linux@...musvillemoes.dk>,
Ingo Molnar <mingo@...nel.org>,
Peter Zijlstra <peterz@...radead.org>,
Vincent Guittot <vincent.guittot@...aro.org>,
Dietmar Eggemann <dietmar.eggemann@....com>,
Steven Rostedt <rostedt@...dmis.org>,
Mel Gorman <mgorman@...e.de>,
Greg Kroah-Hartman <gregkh@...uxfoundation.org>,
Barry Song <song.bao.hua@...ilicon.com>,
Heiko Carstens <hca@...ux.ibm.com>,
Tony Luck <tony.luck@...el.com>,
Jonathan Cameron <Jonathan.Cameron@...wei.com>,
Gal Pressman <gal@...dia.com>, Tariq Toukan <tariqt@...dia.com>
Subject: Re: [PATCH 1/5] bitops: Introduce find_next_andnot_bit()
On Tue, Aug 16, 2022 at 07:07:23PM +0100, Valentin Schneider wrote:
> In preparation of introducing for_each_cpu_andnot(), add a variant of
> find_next_bit() that negate the bits in @addr2 when ANDing them with the
> bits in @addr1.
>
> Signed-off-by: Valentin Schneider <vschneid@...hat.com>
> ---
> include/linux/find.h | 44 ++++++++++++++++++++++++++++++++++++++------
> lib/find_bit.c | 16 +++++++++++-----
> 2 files changed, 49 insertions(+), 11 deletions(-)
>
> diff --git a/include/linux/find.h b/include/linux/find.h
> index 424ef67d4a42..454cde69b30b 100644
> --- a/include/linux/find.h
> +++ b/include/linux/find.h
> @@ -10,7 +10,8 @@
>
> extern unsigned long _find_next_bit(const unsigned long *addr1,
> const unsigned long *addr2, unsigned long nbits,
> - unsigned long start, unsigned long invert, unsigned long le);
> + unsigned long start, unsigned long invert, unsigned long le,
> + bool negate);
> extern unsigned long _find_first_bit(const unsigned long *addr, unsigned long size);
> extern unsigned long _find_first_and_bit(const unsigned long *addr1,
> const unsigned long *addr2, unsigned long size);
> @@ -41,7 +42,7 @@ unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
> return val ? __ffs(val) : size;
> }
>
> - return _find_next_bit(addr, NULL, size, offset, 0UL, 0);
> + return _find_next_bit(addr, NULL, size, offset, 0UL, 0, 0);
> }
> #endif
>
> @@ -71,7 +72,38 @@ unsigned long find_next_and_bit(const unsigned long *addr1,
> return val ? __ffs(val) : size;
> }
>
> - return _find_next_bit(addr1, addr2, size, offset, 0UL, 0);
> + return _find_next_bit(addr1, addr2, size, offset, 0UL, 0, 0);
> +}
> +#endif
> +
> +#ifndef find_next_andnot_bit
> +/**
> + * find_next_andnot_bit - find the next set bit in one memory region
> + * but not in the other
> + * @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.
> + */
> +static inline
> +unsigned long find_next_andnot_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_bit(addr1, addr2, size, offset, 0UL, 0, 1);
> }
> #endif
>
> @@ -99,7 +131,7 @@ unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
> return val == ~0UL ? size : ffz(val);
> }
>
> - return _find_next_bit(addr, NULL, size, offset, ~0UL, 0);
> + return _find_next_bit(addr, NULL, size, offset, ~0UL, 0, 0);
> }
> #endif
>
> @@ -247,7 +279,7 @@ unsigned long find_next_zero_bit_le(const void *addr, unsigned
> return val == ~0UL ? size : ffz(val);
> }
>
> - return _find_next_bit(addr, NULL, size, offset, ~0UL, 1);
> + return _find_next_bit(addr, NULL, size, offset, ~0UL, 1, 0);
> }
> #endif
>
> @@ -266,7 +298,7 @@ unsigned long find_next_bit_le(const void *addr, unsigned
> return val ? __ffs(val) : size;
> }
>
> - return _find_next_bit(addr, NULL, size, offset, 0UL, 1);
> + return _find_next_bit(addr, NULL, size, offset, 0UL, 1, 0);
> }
> #endif
>
> diff --git a/lib/find_bit.c b/lib/find_bit.c
> index 1b8e4b2a9cba..6e5f42c621a9 100644
> --- a/lib/find_bit.c
> +++ b/lib/find_bit.c
> @@ -21,17 +21,19 @@
>
> #if !defined(find_next_bit) || !defined(find_next_zero_bit) || \
> !defined(find_next_bit_le) || !defined(find_next_zero_bit_le) || \
> - !defined(find_next_and_bit)
> + !defined(find_next_and_bit) || !defined(find_next_andnot_bit)
> /*
> * This is a common helper function for find_next_bit, find_next_zero_bit, and
> * find_next_and_bit. The differences are:
> * - The "invert" argument, which is XORed with each fetched word before
> * searching it for one bits.
> - * - The optional "addr2", which is anded with "addr1" if present.
> + * - The optional "addr2", negated if "negate" and ANDed with "addr1" if
> + * present.
> */
> unsigned long _find_next_bit(const unsigned long *addr1,
> const unsigned long *addr2, unsigned long nbits,
> - unsigned long start, unsigned long invert, unsigned long le)
> + unsigned long start, unsigned long invert, unsigned long le,
> + bool negate)
> {
> unsigned long tmp, mask;
>
> @@ -40,7 +42,9 @@ unsigned long _find_next_bit(const unsigned long *addr1,
>
> tmp = addr1[start / BITS_PER_LONG];
> if (addr2)
> - tmp &= addr2[start / BITS_PER_LONG];
> + tmp &= negate ?
> + ~addr2[start / BITS_PER_LONG] :
> + addr2[start / BITS_PER_LONG];
> tmp ^= invert;
>
> /* Handle 1st word. */
> @@ -59,7 +63,9 @@ unsigned long _find_next_bit(const unsigned long *addr1,
>
> tmp = addr1[start / BITS_PER_LONG];
> if (addr2)
> - tmp &= addr2[start / BITS_PER_LONG];
> + tmp &= negate ?
> + ~addr2[start / BITS_PER_LONG] :
> + addr2[start / BITS_PER_LONG];
> tmp ^= invert;
> }
So it flips addr2 bits twice - first with new 'negate', and second
with the existing 'invert'. There is no such combination in the
existing code, but the pattern looks ugly, particularly because we use
different inverting approaches. Because of that, and because XOR trick
generates better code, I'd suggest something like this:
tmp = addr1[start / BITS_PER_LONG] ^ invert1;
if (addr2)
tmp &= addr2[start / BITS_PER_LONG] ^ invert2;
Powered by blists - more mailing lists