lkml.org 
[lkml]   [2023]   [Oct]   [13]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
SubjectRe: [PATCH 1/2] lib/find: Make functions safe on changing bitmaps
From
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

\
 
 \ /
  Last update: 2023-10-14 04:22    [W:0.206 / U:0.100 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site