Re: Kernel Benchmarking

[Linus Torvalds <torvalds@linux-foundation.org>]

On Wed, Sep 16, 2020 at 3:34 AM Jan Kara <jack@suse.cz> wrote:
>
> wait_on_page_bit_common() has:
>
>         spin_lock_irq(&q->lock);
>         SetPageWaiters(page);
>         if (!trylock_page_bit_common(page, bit_nr, wait))
>           - which expands to:
>           (
>                 if (wait->flags & WQ_FLAG_EXCLUSIVE) {
>                         if (test_and_set_bit(bit_nr, &page->flags))
>                                 return false;
>                 } else if (test_bit(bit_nr, &page->flags))
>                         return false;
>           )
>
>                 __add_wait_queue_entry_tail(q, wait);
>         spin_unlock_irq(&q->lock);
>
> Now the suspicious thing is the ordering here. What prevents the compiler
> (or the CPU for that matter) from reordering SetPageWaiters() call behind
> the __add_wait_queue_entry_tail() call? I know SetPageWaiters() and
> test_and_set_bit() operate on the same long but is it really guaranteed
> something doesn't reorder these?

I agree that we might want to make this much more specific, but no,
those things can't be re-ordered.

Part of it is very much that memory ordering is only about two
different locations - accessing the *same* location is always ordered,
even on weakly ordered CPU's.

And the compiler can't re-order them either, we very much make
test_and_set_bit() have the proper barriers. We'd be very screwed if a
"set_bit()" could pass a "test_and_set_bit".

That said, the PageWaiters bit is obviously very much by design in the
same word as the bit we're testing and setting - because the whole
point is that we can then at clear time check the PageWaiters bit
atomically with the bit we're clearing.

So this code optimally shouldn't use separate operations for those
bits at all. It would be better to just have one atomic sequence with
a cmpxchg that does both at the same time.

So I agree that sequence isn't wonderful. But no, I don't think this is the bug.

And as you mention, Matthieu sees it on UP, so memory ordering
wouldn't have been an issue anyway (and compiler re-ordering would
cause all kinds of other problems and break our bit operations
entirely).

Plus if it was some subtle bug like that, it wouldn't trigger as
consistently as it apparently does for Matthieu.

Of course, the reason that I don't see how it can trigger at all (I
still like my ABBA deadlock scenario, but I don't see anybody holding
any crossing locks in Matthieu's list of processes) means that I'm
clearly missing something

                  Linus