Long story short: KCSAN found some potential issues related to how
people use bitmap API. And instead of working through that issues,
the following code shuts down KCSAN by applying READ_ONCE() here
and there.
On Wed, Oct 11, 2023 at 05:02:31PM +0200, Jan Kara wrote:
> From: Mirsad Todorovac <mirsad.todorovac@xxxxxxxxxxxx>
>
> Some users of lib/find functions can operate on bitmaps that change
> while we are looking at the bitmap. For example xarray code looks at tag
> bitmaps only with RCU protection. The xarray users are prepared to
> handle a situation were tag modification races with reading of a tag
> bitmap (and thus we get back a stale information) but the find_*bit()
> functions should return based on bitmap contents at *some* point in time.
> As UBSAN properly warns, the code like:
>
> val = *addr;
> if (val)
> __ffs(val)
>
> prone to refetching 'val' contents from addr by the compiler and thus
> passing 0 to __ffs() which has undefined results.
>
> Fix the problem by using READ_ONCE() in all the appropriate places so
> that the compiler cannot accidentally refetch the contents of addr
> between the test and __ffs(). This makes the undefined behavior
> impossible. The generated code is somewhat larger due to gcc tracking
> both the index and target fetch address in separate registers (according
> to GCC folks the volatile cast confuses their optimizer a bit, they are
> looking into a fix). The difference in performance is minimal though.
> Targetted microbenchmark (in userspace) of the bit searching loop shows
> about 2% regression on some x86 microarchitectures so for normal kernel
> workloads this should be in the noise and not worth introducing special
> set of bitmap searching functions.
>
> [JK: Wrote commit message]
READ_ONCE() fixes nothing because nothing is broken in find_bit() API.
As I suspected, and as Matthew confirmed in his email, the true reason
for READ_ONCE() here is to disable KCSAN check:
READ_ONCE() serves two functions here;
one is that it tells the compiler not to try anything fancy, and
the other is that it tells KCSAN to not bother instrumenting this
load; no load-delay-reload.
https://lkml.kernel.org/linux-mm/ZQkhgVb8nWGxpSPk@xxxxxxxxxxxxxxxxxxxx/
And as side-effect, it of course hurts the performance. In the same
email Matthew said he doesn't believe me that READ_ONCE would do that,
so thank you for testing and confirming that it does.
Matthew, in my experience compilers do really well in that low-level
things, and gambling with compilers usually makes thing worse. x86_64
is one of the most strong-ordered architectures that I've been working
with, and even here READ_ONCE has visible effect on performance. I
expect that it will get even worse on more weakly ordered platforms.
I'm OK that you don't believe me; probably you can believe Paul
McKenney and his paper on kernel memory model, which says in the very
first paragraph:
Applying ACCESS_ONCE() to a large array or structure is unlikely
to do anything useful, and use of READ_ONCE() and WRITE_ONCE()
in this situation can result in load-tearing and store-tearing.
https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4444.html
Jan, I think that in your last email you confirmed that the xarray
problem that you're trying to solve is about a lack of proper locking:
Well, for xarray the write side is synchronized with a spinlock but the read
side is not (only RCU protected).
https://lkml.kernel.org/linux-mm/20230918155403.ylhfdbscgw6yek6p@quack3/
If there's no enough synchronization, why not just adding it?
Regardless performance consideration, my main concern is that this patch
considers bitmap as an atomic structure, which is intentionally not.
There are just a few single-bit atomic operations like set_bit() and
clear_bit(). All other functions are non-atomic, including those
find_bit() operations.
There is quite a lot of examples of wrong use of bitmaps wrt
atomicity, the most typical is like:
for(idx = 0; idx < num; idx++) {
...
set_bit(idx, bitmap);
}
This is wrong because a series of atomic ops is not atomic itself, and
if you see something like this in you code, it should be converted to
using non-atomic __set_bit(), and protected externally if needed.
Similarly, READ_ONCE() in a for-loop doesn't guarantee any ordering or
atomicity, and only hurts the performance. And this is exactly what
this patch does.
Thanks,
Yury
> CC: Yury Norov <yury.norov@xxxxxxxxx>
> Link: https://lore.kernel.org/all/20230918044739.29782-1-mirsad.todorovac@xxxxxxxxxxxx/
> Signed-off-by: Mirsad Todorovac <mirsad.todorovac@xxxxxxxxxxxx>
> Signed-off-by: Jan Kara <jack@xxxxxxx>
> ---
> include/linux/find.h | 40 ++++++++++++++++++++++++----------------
> lib/find_bit.c | 39 +++++++++++++++++++++++----------------
> 2 files changed, 47 insertions(+), 32 deletions(-)
>
> diff --git a/include/linux/find.h b/include/linux/find.h
> index 5e4f39ef2e72..5ef6466dc7cc 100644
> --- a/include/linux/find.h
> +++ b/include/linux/find.h
> @@ -60,7 +60,7 @@ unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
> if (unlikely(offset >= size))
> return size;
>
> - val = *addr & GENMASK(size - 1, offset);
> + val = READ_ONCE(*addr) & GENMASK(size - 1, offset);
> return val ? __ffs(val) : size;
> }
>
> @@ -90,7 +90,8 @@ unsigned long find_next_and_bit(const unsigned long *addr1,
> if (unlikely(offset >= size))
> return size;
>
> - val = *addr1 & *addr2 & GENMASK(size - 1, offset);
> + val = READ_ONCE(*addr1) & READ_ONCE(*addr2) &
> + GENMASK(size - 1, offset);
> return val ? __ffs(val) : size;
> }
>
> @@ -121,7 +122,8 @@ unsigned long find_next_andnot_bit(const unsigned long *addr1,
> if (unlikely(offset >= size))
> return size;
>
> - val = *addr1 & ~*addr2 & GENMASK(size - 1, offset);
> + val = READ_ONCE(*addr1) & ~READ_ONCE(*addr2) &
> + GENMASK(size - 1, offset);
> return val ? __ffs(val) : size;
> }
>
> @@ -151,7 +153,8 @@ unsigned long find_next_or_bit(const unsigned long *addr1,
> if (unlikely(offset >= size))
> return size;
>
> - val = (*addr1 | *addr2) & GENMASK(size - 1, offset);
> + val = (READ_ONCE(*addr1) | READ_ONCE(*addr2)) &
> + GENMASK(size - 1, offset);
> return val ? __ffs(val) : size;
> }
>
> @@ -179,7 +182,7 @@ unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
> if (unlikely(offset >= size))
> return size;
>
> - val = *addr | ~GENMASK(size - 1, offset);
> + val = READ_ONCE(*addr) | ~GENMASK(size - 1, offset);
> return val == ~0UL ? size : ffz(val);
> }
>
> @@ -200,7 +203,7 @@ static inline
> unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
> {
> if (small_const_nbits(size)) {
> - unsigned long val = *addr & GENMASK(size - 1, 0);
> + unsigned long val = READ_ONCE(*addr) & GENMASK(size - 1, 0);
>
> return val ? __ffs(val) : size;
> }
> @@ -229,7 +232,7 @@ unsigned long find_nth_bit(const unsigned long *addr, unsigned long size, unsign
> return size;
>
> if (small_const_nbits(size)) {
> - unsigned long val = *addr & GENMASK(size - 1, 0);
> + unsigned long val = READ_ONCE(*addr) & GENMASK(size - 1, 0);
>
> return val ? fns(val, n) : size;
> }
> @@ -255,7 +258,8 @@ unsigned long find_nth_and_bit(const unsigned long *addr1, const unsigned long *
> return size;
>
> if (small_const_nbits(size)) {
> - unsigned long val = *addr1 & *addr2 & GENMASK(size - 1, 0);
> + unsigned long val = READ_ONCE(*addr1) & READ_ONCE(*addr2)
> + & GENMASK(size - 1, 0);
>
> return val ? fns(val, n) : size;
> }
> @@ -282,7 +286,8 @@ unsigned long find_nth_andnot_bit(const unsigned long *addr1, const unsigned lon
> return size;
>
> if (small_const_nbits(size)) {
> - unsigned long val = *addr1 & (~*addr2) & GENMASK(size - 1, 0);
> + unsigned long val = READ_ONCE(*addr1) & ~READ_ONCE(*addr2) &
> + GENMASK(size - 1, 0);
>
> return val ? fns(val, n) : size;
> }
> @@ -312,7 +317,8 @@ unsigned long find_nth_and_andnot_bit(const unsigned long *addr1,
> return size;
>
> if (small_const_nbits(size)) {
> - unsigned long val = *addr1 & *addr2 & (~*addr3) & GENMASK(size - 1, 0);
> + unsigned long val = READ_ONCE(*addr1) & READ_ONCE(*addr2) &
> + ~READ_ONCE(*addr3) & GENMASK(size - 1, 0);
>
> return val ? fns(val, n) : size;
> }
> @@ -336,7 +342,8 @@ unsigned long find_first_and_bit(const unsigned long *addr1,
> unsigned long size)
> {
> if (small_const_nbits(size)) {
> - unsigned long val = *addr1 & *addr2 & GENMASK(size - 1, 0);
> + unsigned long val = READ_ONCE(*addr1) & READ_ONCE(*addr2) &
> + GENMASK(size - 1, 0);
>
> return val ? __ffs(val) : size;
> }
> @@ -358,7 +365,7 @@ static inline
> unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
> {
> if (small_const_nbits(size)) {
> - unsigned long val = *addr | ~GENMASK(size - 1, 0);
> + unsigned long val = READ_ONCE(*addr) | ~GENMASK(size - 1, 0);
>
> return val == ~0UL ? size : ffz(val);
> }
> @@ -379,7 +386,7 @@ static inline
> unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
> {
> if (small_const_nbits(size)) {
> - unsigned long val = *addr & GENMASK(size - 1, 0);
> + unsigned long val = READ_ONCE(*addr) & GENMASK(size - 1, 0);
>
> return val ? __fls(val) : size;
> }
> @@ -505,7 +512,7 @@ unsigned long find_next_zero_bit_le(const void *addr, unsigned
> long size, unsigned long offset)
> {
> if (small_const_nbits(size)) {
> - unsigned long val = *(const unsigned long *)addr;
> + unsigned long val = READ_ONCE(*(const unsigned long *)addr);
>
> if (unlikely(offset >= size))
> return size;
> @@ -523,7 +530,8 @@ static inline
> unsigned long find_first_zero_bit_le(const void *addr, unsigned long size)
> {
> if (small_const_nbits(size)) {
> - unsigned long val = swab(*(const unsigned long *)addr) | ~GENMASK(size - 1, 0);
> + unsigned long val = swab(READ_ONCE(*(const unsigned long *)addr))
> + | ~GENMASK(size - 1, 0);
>
> return val == ~0UL ? size : ffz(val);
> }
> @@ -538,7 +546,7 @@ unsigned long find_next_bit_le(const void *addr, unsigned
> long size, unsigned long offset)
> {
> if (small_const_nbits(size)) {
> - unsigned long val = *(const unsigned long *)addr;
> + unsigned long val = READ_ONCE(*(const unsigned long *)addr);
>
> if (unlikely(offset >= size))
> return size;
> diff --git a/lib/find_bit.c b/lib/find_bit.c
> index 32f99e9a670e..6867ef8a85e0 100644
> --- a/lib/find_bit.c
> +++ b/lib/find_bit.c
> @@ -98,7 +98,7 @@ out: \
> */
> unsigned long _find_first_bit(const unsigned long *addr, unsigned long size)
> {
> - return FIND_FIRST_BIT(addr[idx], /* nop */, size);
> + return FIND_FIRST_BIT(READ_ONCE(addr[idx]), /* nop */, size);
> }
> EXPORT_SYMBOL(_find_first_bit);
> #endif
> @@ -111,7 +111,8 @@ unsigned long _find_first_and_bit(const unsigned long *addr1,
> const unsigned long *addr2,
> unsigned long size)
> {
> - return FIND_FIRST_BIT(addr1[idx] & addr2[idx], /* nop */, size);
> + return FIND_FIRST_BIT(READ_ONCE(addr1[idx]) & READ_ONCE(addr2[idx]),
> + /* nop */, size);
> }
> EXPORT_SYMBOL(_find_first_and_bit);
> #endif
> @@ -122,7 +123,7 @@ EXPORT_SYMBOL(_find_first_and_bit);
> */
> unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size)
> {
> - return FIND_FIRST_BIT(~addr[idx], /* nop */, size);
> + return FIND_FIRST_BIT(~READ_ONCE(addr[idx]), /* nop */, size);
> }
> EXPORT_SYMBOL(_find_first_zero_bit);
> #endif
> @@ -130,28 +131,30 @@ EXPORT_SYMBOL(_find_first_zero_bit);
> #ifndef find_next_bit
> unsigned long _find_next_bit(const unsigned long *addr, unsigned long nbits, unsigned long start)
> {
> - return FIND_NEXT_BIT(addr[idx], /* nop */, nbits, start);
> + return FIND_NEXT_BIT(READ_ONCE(addr[idx]), /* nop */, nbits, start);
> }
> EXPORT_SYMBOL(_find_next_bit);
> #endif
>
> unsigned long __find_nth_bit(const unsigned long *addr, unsigned long size, unsigned long n)
> {
> - return FIND_NTH_BIT(addr[idx], size, n);
> + return FIND_NTH_BIT(READ_ONCE(addr[idx]), size, n);
> }
> EXPORT_SYMBOL(__find_nth_bit);
>
> unsigned long __find_nth_and_bit(const unsigned long *addr1, const unsigned long *addr2,
> unsigned long size, unsigned long n)
> {
> - return FIND_NTH_BIT(addr1[idx] & addr2[idx], size, n);
> + return FIND_NTH_BIT(READ_ONCE(addr1[idx]) & READ_ONCE(addr2[idx]),
> + size, n);
> }
> EXPORT_SYMBOL(__find_nth_and_bit);
>
> unsigned long __find_nth_andnot_bit(const unsigned long *addr1, const unsigned long *addr2,
> unsigned long size, unsigned long n)
> {
> - return FIND_NTH_BIT(addr1[idx] & ~addr2[idx], size, n);
> + return FIND_NTH_BIT(READ_ONCE(addr1[idx]) & ~READ_ONCE(addr2[idx]),
> + size, n);
> }
> EXPORT_SYMBOL(__find_nth_andnot_bit);
>
> @@ -160,7 +163,8 @@ unsigned long __find_nth_and_andnot_bit(const unsigned long *addr1,
> const unsigned long *addr3,
> unsigned long size, unsigned long n)
> {
> - return FIND_NTH_BIT(addr1[idx] & addr2[idx] & ~addr3[idx], size, n);
> + return FIND_NTH_BIT(READ_ONCE(addr1[idx]) & READ_ONCE(addr2[idx]) &
> + ~READ_ONCE(addr3[idx]), size, n);
> }
> EXPORT_SYMBOL(__find_nth_and_andnot_bit);
>
> @@ -168,7 +172,8 @@ EXPORT_SYMBOL(__find_nth_and_andnot_bit);
> unsigned long _find_next_and_bit(const unsigned long *addr1, const unsigned long *addr2,
> unsigned long nbits, unsigned long start)
> {
> - return FIND_NEXT_BIT(addr1[idx] & addr2[idx], /* nop */, nbits, start);
> + return FIND_NEXT_BIT(READ_ONCE(addr1[idx]) & READ_ONCE(addr2[idx]),
> + /* nop */, nbits, start);
> }
> EXPORT_SYMBOL(_find_next_and_bit);
> #endif
> @@ -177,7 +182,8 @@ EXPORT_SYMBOL(_find_next_and_bit);
> unsigned long _find_next_andnot_bit(const unsigned long *addr1, const unsigned long *addr2,
> unsigned long nbits, unsigned long start)
> {
> - return FIND_NEXT_BIT(addr1[idx] & ~addr2[idx], /* nop */, nbits, start);
> + return FIND_NEXT_BIT(READ_ONCE(addr1[idx]) & ~READ_ONCE(addr2[idx]),
> + /* nop */, nbits, start);
> }
> EXPORT_SYMBOL(_find_next_andnot_bit);
> #endif
> @@ -186,7 +192,8 @@ EXPORT_SYMBOL(_find_next_andnot_bit);
> unsigned long _find_next_or_bit(const unsigned long *addr1, const unsigned long *addr2,
> unsigned long nbits, unsigned long start)
> {
> - return FIND_NEXT_BIT(addr1[idx] | addr2[idx], /* nop */, nbits, start);
> + return FIND_NEXT_BIT(READ_ONCE(addr1[idx]) | READ_ONCE(addr2[idx]),
> + /* nop */, nbits, start);
> }
> EXPORT_SYMBOL(_find_next_or_bit);
> #endif
> @@ -195,7 +202,7 @@ EXPORT_SYMBOL(_find_next_or_bit);
> unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long nbits,
> unsigned long start)
> {
> - return FIND_NEXT_BIT(~addr[idx], /* nop */, nbits, start);
> + return FIND_NEXT_BIT(~READ_ONCE(addr[idx]), /* nop */, nbits, start);
> }
> EXPORT_SYMBOL(_find_next_zero_bit);
> #endif
> @@ -208,7 +215,7 @@ unsigned long _find_last_bit(const unsigned long *addr, unsigned long size)
> unsigned long idx = (size-1) / BITS_PER_LONG;
>
> do {
> - val &= addr[idx];
> + val &= READ_ONCE(addr[idx]);
> if (val)
> return idx * BITS_PER_LONG + __fls(val);
>
> @@ -242,7 +249,7 @@ EXPORT_SYMBOL(find_next_clump8);
> */
> unsigned long _find_first_zero_bit_le(const unsigned long *addr, unsigned long size)
> {
> - return FIND_FIRST_BIT(~addr[idx], swab, size);
> + return FIND_FIRST_BIT(~READ_ONCE(addr[idx]), swab, size);
> }
> EXPORT_SYMBOL(_find_first_zero_bit_le);
>
> @@ -252,7 +259,7 @@ EXPORT_SYMBOL(_find_first_zero_bit_le);
> unsigned long _find_next_zero_bit_le(const unsigned long *addr,
> unsigned long size, unsigned long offset)
> {
> - return FIND_NEXT_BIT(~addr[idx], swab, size, offset);
> + return FIND_NEXT_BIT(~READ_ONCE(addr[idx]), swab, size, offset);
> }
> EXPORT_SYMBOL(_find_next_zero_bit_le);
> #endif
> @@ -261,7 +268,7 @@ EXPORT_SYMBOL(_find_next_zero_bit_le);
> unsigned long _find_next_bit_le(const unsigned long *addr,
> unsigned long size, unsigned long offset)
> {
> - return FIND_NEXT_BIT(addr[idx], swab, size, offset);
> + return FIND_NEXT_BIT(READ_ONCE(addr[idx]), swab, size, offset);
> }
> EXPORT_SYMBOL(_find_next_bit_le);
>
> --
> 2.35.3
