| Message ID | 20220817175812.671843-2-vschneid@redhat.com (mailing list archive) |
|---|---|
| State | Superseded |
| Headers | show |
| Series | sched, net: NUMA-aware CPU spreading interface | expand |
On Wed, 17 Aug 2022 18:58:08 +0100 Valentin Schneider <vschneid@redhat.com> wrote: > +#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. Can we make the above documentation more descriptive. Because I read this three times, and I still have no idea what it does. The tag line sounds like the nursery song "One of these things is not like the others". -- Steve > + */ > +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, ~0UL, 0); > } > #endif
On 18/08/22 10:08, Steven Rostedt wrote: > On Wed, 17 Aug 2022 18:58:08 +0100 > Valentin Schneider <vschneid@redhat.com> wrote: > >> +#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. > > Can we make the above documentation more descriptive. Because I read this > three times, and I still have no idea what it does. > > The tag line sounds like the nursery song "One of these things is not like > the others". > How about: find the next set bit in ((first region) AND NOT(second region)) Or find the next set bit in (*addr1 & ~*addr2) ? > -- Steve
On Thu, 18 Aug 2022 17:26:43 +0100 Valentin Schneider <vschneid@redhat.com> wrote: > How about: > > find the next set bit in (*addr1 & ~*addr2) I understand the above better. But to convert that into English, we could say: Find the next bit in *addr1 excluding all the bits in *addr2. or Find the next bit in *addr1 that is not set in *addr2. -- Steve
On Thu, Aug 18, 2022 at 8:18 PM Steven Rostedt <rostedt@goodmis.org> wrote: > On Thu, 18 Aug 2022 17:26:43 +0100 > Valentin Schneider <vschneid@redhat.com> wrote: > > > How about: > > > > > find the next set bit in (*addr1 & ~*addr2) > > I understand the above better. But to convert that into English, we could > say: > > > Find the next bit in *addr1 excluding all the bits in *addr2. > > or > > Find the next bit in *addr1 that is not set in *addr2. With this explanation I'm wondering how different this is to bitmap_bitremap(), with adjusting to using an inverted mask. If they have something in common, perhaps make them in the same namespace with similar naming convention?
On 18/08/22 22:04, Andy Shevchenko wrote: > On Thu, Aug 18, 2022 at 8:18 PM Steven Rostedt <rostedt@goodmis.org> wrote: >> On Thu, 18 Aug 2022 17:26:43 +0100 >> Valentin Schneider <vschneid@redhat.com> wrote: >> >> > How about: >> >> > >> > find the next set bit in (*addr1 & ~*addr2) >> >> I understand the above better. But to convert that into English, we could >> say: >> >> >> Find the next bit in *addr1 excluding all the bits in *addr2. >> >> or >> >> Find the next bit in *addr1 that is not set in *addr2. > > With this explanation I'm wondering how different this is to > bitmap_bitremap(), with adjusting to using an inverted mask. If they > have something in common, perhaps make them in the same namespace with > similar naming convention? > I'm trying to wrap my head around the whole remap thing, IIUC we could have something like remap *addr1 to ~*addr2 and stop rather than continue with a wraparound, but that really feels like shoehorning. > -- > With Best Regards, > Andy Shevchenko
On Fri, Aug 19, 2022 at 11:34:01AM +0100, Valentin Schneider wrote: > On 18/08/22 22:04, Andy Shevchenko wrote: > > On Thu, Aug 18, 2022 at 8:18 PM Steven Rostedt <rostedt@goodmis.org> wrote: > >> On Thu, 18 Aug 2022 17:26:43 +0100 > >> Valentin Schneider <vschneid@redhat.com> wrote: > >> > >> > How about: > >> > >> > > >> > find the next set bit in (*addr1 & ~*addr2) > >> > >> I understand the above better. But to convert that into English, we could > >> say: > >> > >> > >> Find the next bit in *addr1 excluding all the bits in *addr2. > >> > >> or > >> > >> Find the next bit in *addr1 that is not set in *addr2. > > > > With this explanation I'm wondering how different this is to > > bitmap_bitremap(), with adjusting to using an inverted mask. If they > > have something in common, perhaps make them in the same namespace with > > similar naming convention? > > > > I'm trying to wrap my head around the whole remap thing, IIUC we could have > something like remap *addr1 to ~*addr2 and stop rather than continue with a > wraparound, but that really feels like shoehorning. Old and new maps create a simple forward-looking mapping, like this: #0 #4 old: 0111 0 ... | \\\| New: 00 111 ... So if you pass #0, it's wired to 0; but #1 will skip 1 bit and would be wired to 2; and so on. There is some puzzling when wraparound comes in play, but the general idea is like that. I think there's nothing common with bitmap_and{,_not}. Thanks, Yury
diff --git a/include/linux/find.h b/include/linux/find.h index 424ef67d4a42..920597de4e62 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 invert1, unsigned long invert2, + unsigned long le); 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, 0UL, 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, 0UL, 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, ~0UL, 0); } #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, 0UL, 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, 0UL, 1); } #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, 0UL, 1); } #endif diff --git a/lib/find_bit.c b/lib/find_bit.c index 1b8e4b2a9cba..c46b66d7d2b4 100644 --- a/lib/find_bit.c +++ b/lib/find_bit.c @@ -21,27 +21,29 @@ #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 "invert" arguments, which are XORed with each fetched word (invert1 + * for words in addr1, invert2 for those in addr2) before searching it for + * one bits. */ 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) + const unsigned long *addr2, + unsigned long nbits, unsigned long start, + unsigned long invert1, unsigned long invert2, + unsigned long le) { unsigned long tmp, mask; if (unlikely(start >= nbits)) return nbits; - tmp = addr1[start / BITS_PER_LONG]; + tmp = addr1[start / BITS_PER_LONG] ^ invert1; if (addr2) - tmp &= addr2[start / BITS_PER_LONG]; - tmp ^= invert; + tmp &= addr2[start / BITS_PER_LONG] ^ invert2; /* Handle 1st word. */ mask = BITMAP_FIRST_WORD_MASK(start); @@ -57,10 +59,9 @@ unsigned long _find_next_bit(const unsigned long *addr1, if (start >= nbits) return nbits; - tmp = addr1[start / BITS_PER_LONG]; + tmp = addr1[start / BITS_PER_LONG] ^ invert1; if (addr2) - tmp &= addr2[start / BITS_PER_LONG]; - tmp ^= invert; + tmp &= addr2[start / BITS_PER_LONG] ^ invert2; } if (le)
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. Note that the _find_next_bit() @invert argument now gets split into two: @invert1 for words in @addr1, @invert2 for words in @addr2. The only current users of _find_next_bit() with @invert set are: o find_next_zero_bit() o find_next_zero_bit_le() and neither of these pass an @addr2, so the conversion is straightforward. Signed-off-by: Valentin Schneider <vschneid@redhat.com> --- include/linux/find.h | 44 ++++++++++++++++++++++++++++++++++++++------ lib/find_bit.c | 23 ++++++++++++----------- 2 files changed, 50 insertions(+), 17 deletions(-)