Re: [PATCH 1/2] lib/find: Make functions safe on changing bitmaps

[Mirsad Goran Todorovac]

On 10/14/2023 2:15 AM, Yury Norov wrote:
> Restore LKML
>
> On Thu, Oct 12, 2023 at 02:21:10PM +0200, Jan Kara wrote:
> > On Wed 11-10-23 11:26:29, Yury Norov wrote:
> > > 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.
> >
> > I'm sorry but this is not what the patch does. I'm not sure how to get the
> > message across so maybe let me start from a different angle:
> >
> > Bitmaps are perfectly fine to be used without any external locking if
> > only atomic bit ops (set_bit, clear_bit, test_and_{set/clear}_bit) are
> > used. This is a significant performance gain compared to using a spinlock
> > or other locking and people do this for a long time. I hope we agree on
> > that.
> >
> > Now it is also common that you need to find a set / clear bit in a bitmap.
> > To maintain lockless protocol and deal with races people employ schemes
> > like (the dumbest form):
> >
> > 	do {
> > 		bit = find_first_bit(bitmap, n);
> > 		if (bit >= n)
> > 			abort...
> > 	} while (!test_and_clear_bit(bit, bitmap));
> >
> > So the code loops until it finds a set bit that is successfully cleared by
> > it. This is perfectly fine and safe lockless code and such use should be
> > supported. Agreed?
>
> Great example. When you're running non-atomic functions concurrently,
> the result may easily become incorrect, and this is what you're
> demonstrating here.
>
> Regarding find_first_bit() it means that:
>   - it may erroneously return unset bit;
>   - it may erroneously return non-first set bit;
>   - it may erroneously return no bits for non-empty bitmap.
>
> Effectively it means that find_first bit may just return a random number.
>
> Let's take another example:
>
> 	do {
> 		bit = get_random_number();
> 		if (bit >= n)
> 			abort...
> 	} while (!test_and_clear_bit(bit, bitmap));
>
> When running concurrently, the difference between this and your code
> is only in probability of getting set bit somewhere from around the
> beginning of bitmap.
>
> The key point is that find_bit() may return undef even if READ_ONCE() is
> used. If bitmap gets changed anytime in the process, the result becomes
> invalid. It may happen even after returning from find_first_bit().
>
> And if my understanding correct, your code is designed in the
> assumption that find_first_bit() may return garbage, so handles it
> correctly.
>
> > *Except* that the above actually is not safe due to find_first_bit()
> > implementation and KCSAN warns about that. The problem is that:
> >
> > Assume *addr == 1
> > CPU1			CPU2
> > find_first_bit(addr, 64)
> >    val = *addr;
> >    if (val) -> true
> > 			clear_bit(0, addr)
> >      val = *addr -> compiler decided to refetch addr contents for whatever
> > 		   reason in the generated assembly
> >      __ffs(val) -> now executed for value 0 which has undefined results.
>
> Yes, __ffs(0) is undef. But the whole function is undef when accessing
> bitmap concurrently.
>
> > And the READ_ONCE() this patch adds prevents the compiler from adding the
> > refetching of addr into the assembly.
>
> That's true. But it doesn't improve on the situation. It was an undef
> before, and it's undef after, but a 2% slower undef.
>
> Now on that KCSAN warning. If I understand things correctly, for the
> example above, KCSAN warning is false-positive, because you're
> intentionally running lockless.
>
> But for some other people it may be a true error, and now they'll have
> no chance to catch it if KCSAN is forced to ignore find_bit() entirely.
>
> We've got the whole class of lockless algorithms that allow safe concurrent
> access to the memory. And now that there's a tool that searches for them
> (concurrent accesses), we need to have an option to somehow teach it
> to suppress irrelevant warnings. Maybe something like this?
>
>          lockless_algorithm_begin(bitmap, bitmap_size(nbits));
> 	do {
> 		bit = find_first_bit(bitmap, nbits);
> 		if (bit >= nbits)
> 			break;
> 	} while (!test_and_clear_bit(bit, bitmap));
>          lockless_algorithm_end(bitmap, bitmap_size(nbits));
>
> And, of course, as I suggested a couple iterations ago, you can invent
> a thread-safe version of find_bit(), that would be perfectly correct
> for lockless use:
>
>   unsigned long _find_and_clear_bit(volatile unsigned long *addr, unsigned long size)
>   {
>          unsigned long bit = 0;
>   
>          while (!test_and_clear_bit(bit, bitmap) {
>                  bit = FIND_FIRST_BIT(addr[idx], /* nop */, size);
>                  if (bit >= size)
>                          return size;
>          }
>
>          return bit;
>   }

Hi, Yuri,

But the code above effectively does the same as the READ_ONCE() macro
as defined in rwonce.h:

#ifndef __READ_ONCE
#define __READ_ONCE(x)	(*(const volatile __unqual_scalar_typeof(x) *)&(x))
#endif

#define READ_ONCE(x)							\
({									\
	compiletime_assert_rwonce_type(x);				\
	__READ_ONCE(x);							\
})

Both uses only prevent the funny stuff the compiler might have done to the
read of the addr[idx], there's no black magic in READ_ONCE().

Both examples would probably result in the same assembly and produce the
same 2% slowdown ...

Only you declare volatile in one place, and READ_ONCE() in each read, but
this will only compile a bit slower and generate the same machine code.

Best regards,
Mirsad Todorovac


> Didn't test that, but I hope 'volatile' specifier should be enough
> for compiler to realize that it shouldn't optimize memory access, and
> for KCSAN that everything's OK here.
>
> By the way, thank you for respectful and professional communication.
>
> Thanks,
> Yury

--
Mirsad Todorovac
Sistem inženjer
Grafički fakultet | Akademija likovnih umjetnosti
Sveučilište u Zagrebu

System engineer
Faculty of Graphic Arts | Academy of Fine Arts
University of Zagreb, Republic of Croatia
tel. +385 (0)1 3711 451
mob. +385 91 57 88 355