Date:   Tue, 31 Jan 2023 16:08:29 +0100
From:   Jonas Oberhauser <jonas.oberhauser@...weicloud.com>
To:     Boqun Feng <boqun.feng@...il.com>
Cc:     Peter Zijlstra <peterz@...radead.org>,
        Jules Maselbas <jmaselbas@...ray.eu>,
        Will Deacon <will@...nel.org>,
        Mark Rutland <mark.rutland@....com>,
        Arnd Bergmann <arnd@...db.de>, linux-arch@...r.kernel.org,
        linux-kernel@...r.kernel.org,
        Alan Stern <stern@...land.harvard.edu>,
        Andrea Parri <parri.andrea@...il.com>,
        Nicholas Piggin <npiggin@...il.com>,
        David Howells <dhowells@...hat.com>,
        Jade Alglave <j.alglave@....ac.uk>,
        Luc Maranget <luc.maranget@...ia.fr>,
        "Paul E. McKenney" <paulmck@...nel.org>,
        Akira Yokosawa <akiyks@...il.com>,
        Daniel Lustig <dlustig@...dia.com>,
        Joel Fernandes <joel@...lfernandes.org>,
        Hernan Ponce de Leon <hernan.poncedeleon@...weicloud.com>,
        Paul Heidekrüger <paul.heidekrueger@...tum.de>,
        Marco Elver <elver@...gle.com>,
        Miguel Ojeda <ojeda@...nel.org>,
        Alex Gaynor <alex.gaynor@...il.com>,
        Wedson Almeida Filho <wedsonaf@...il.com>,
        Gary Guo <gary@...yguo.net>,
        Björn Roy Baron <bjorn3_gh@...tonmail.com>
Subject: Re: [PATCH] locking/atomic: atomic: Use arch_atomic_{read,set} in
 generic atomic ops



On 1/30/2023 7:38 PM, Boqun Feng wrote:
> On Mon, Jan 30, 2023 at 01:23:28PM +0100, Jonas Oberhauser wrote:
>>
>> On 1/27/2023 11:09 PM, Boqun Feng wrote:
>>> On Fri, Jan 27, 2023 at 03:34:33PM +0100, Peter Zijlstra wrote:
>>>>> I also noticed that GCC has some builtin/extension to do such things,
>>>>> __atomic_OP_fetch and __atomic_fetch_OP, but I do not know if this
>>>>> can be used in the kernel.
>>>> On a per-architecture basis only, the C/C++ memory model does not match
>>>> the Linux Kernel memory model so using the compiler to generate the
>>>> atomic ops is somewhat tricky and needs architecture audits.
>>> Hijack this thread a little bit, but while we are at it, do you think it
>>> makes sense that we have a config option that allows archs to
>>> implement LKMM atomics via C11 (volatile) atomics? I know there are gaps
>>> between two memory models, but the option is only for fallback/generic
>>> implementation so we can put extra barriers/orderings to make things
>>> guaranteed to work.
>> Another is that the C11 model is more about atomic locations than atomic
>> accesses, and there are several places in the kernel where a location is
>> accessed both atomically and non-atomically. This API mismatch is more
>> severe than the semantic differences in my opinion, since you don't have
>> guarantees of what the layout of atomics is going to be.
>>
> True, but the same problem for our asm implemented atomics, right? My
> plan is to do (volatile atomic_int *) casts on these locations.

Do you? I think LKMM atomic types are always exactly as big as the 
underlying types.
With C you might get into a case where the atomic_int is actually [lock 
; non-atomic int] and when you access the location in a mixed way, you 
will non-atomically read the lock part but the atomic accesses modify 
the int part (protected by the lock).

>
>> Perhaps you could instead rely on the compiler builtins? Note that this may
> These are less formal/defined to me, and not much research on them I
> assume, I'd rather not use them.

I think that it's easy enough to define a formal model of these that is 
a bit conservative, and then just add mb()s to make them safe.

>
>> invalidate some progress properties, e.g., ticket locks become unfair if the
>> increment (for taking a ticket) is implemented with a CAS loop (because a
>> thread can fail forever to get a ticket if the ticket counter is contended,
>> and thus starve). There may be some linux atomics that don't map to any
>> compiler builtins and need to implemented with such CAS loops, potentially
>> leading to such problems.
>>
>> I'm also curious whether link time optimization can resolve the inlining
>> issue?
>>
> For Rust case, cross-language LTO is needed I think, and last time I
> tried, it didn't work.

In German we say "Was noch nicht ist kann ja noch werden", translated as 
"what isn't can yet become", I don't feel like putting too much effort 
into something that hardly affects performance and will hopefully become 
obsolete at some point in the near future.

>
>> I think another big question for me is to which extent it makes sense
>> anyways to have shared memory concurrency between the Rust code and the C
>> code. It seems all the bad concurrency stuff from the C world would flow
>> into the Rust world, right?
> What do you mean by "bad" ;-) ;-) ;-)

Uh oh. Let's pretend I didn't say anything :D

>> If you can live without shared Rust & C concurrency, then perhaps you can
>> get away without using LKMM in Rust at all, and just rely on its (C11-like)
>> memory model internally and talk to the C code through synchronous, safer
>> ways.
>>
> First I don't think I can avoid using LKMM in Rust, besides the
> communication from two sides, what if kernel developers just want to
> use the memory model they learn and understand (i.e. LKMM) in a new Rust
> driver?

I'd rather people think 10 times before relying on atomics to write Rust 
code.
There may be cases where it can't be avoided because of performance 
reasons, but Rust has a much more convenient concurrency model to offer 
than atomics.
I think a lot more people understand Rust mutexes or channels compared 
to atomics.
Unfortunately I haven't written much driver code so I don't have 
experience to what extent it's generally necessary to rely on atomics :(


> They probably already have a working parallel algorithm based on
> LKMM.
>
> Further, let's say we make C and Rust talk without shared memory
> concurrency, what would that be? Will it more defined/formal the LKMM?

Normal FFI with sequential shared memory (passing a buffer sequentially 
through FFI)?

> How's the cost if we use synchronous ways? I personally think there are
> places in core kernel where Rust can be tried, whatever the mechanism is
> used, it cannot sarcrifed.

Note that if you turn a C atomics-based implementation into a Rust 
atomics-based implementation, you'll probably need some unsafe when you 
"consume" the data synchronized through atomics (Sebastian Humenda and 
Jonathan Schwender explained this to me recently), and any memory safety 
bugs coming from that unsafe part can be due to incorrect use of the 
atomics in the rest of the algorithm. So you don't really gain much 
memory safety compared to the C implementation.

Hopefully you can write a small safe Rust API around your mechanism, and 
then constrain its possibly unsafe atomics use inside the library.
But the motivation for porting that mechanism to Rust atomics rather 
than relying on FFI is low for me.

>> I'm not against having a fallback builtin-based implementation of LKMM, and
>> I don't think that it really needs architecture audits. What it needs is
> Fun fact, there exist some "optimizations" that don't generate the asm
> code as you want:
>
> 	https://github.com/llvm/llvm-project/issues/56450
>
> Needless to say, they are bugs, and will be fixed, besides making atomic
> volatile seems to avoid these "optimizations"


Haha. Reminds me of a similar issue with failed CAS, which are usually 
only reads but are considered to write back the same value in some 
papers, leading to some incorrect results.


>> some additional compiler barriers and memory barriers, to ensure that the
>> arguments about dependencies and non-atomics still hold. E.g., a release
>> store may not just be "builtin release store" but may need to have a
>> compiler barrier to prevent the release store being moved in program order.
>> And a "full barrier" exchange may need an mb() infront of the operation to
>> avoid "roach motel ordering" (i.e.,  x=1 ; "full barrier exchange"; y = 1
>> allows y=1 to execute before x=1 in the compiler builtins as far as I
>> remember). And there may be some other cases like this.
>>
> Agreed. And this is another reason I want to do it: I'm curious about
> how far C11 memory model and LKMM are different, and whether there is a
> way to implement one by another, what are the gaps (theorical and
> pratical), whether the ordering we have in LKMM can be implemented by
> compilers (mostly dependencies).


I could imagine you'll find lots of differences, starting from SC 
ordering, dependencies, local ordering of barriers, propagation...
I generally categorize memory models in 4 tiers:
- po | rfe | coe | fre is acyclic  (SC)
- ppo | rfe | coe | fre is acyclic (Arm, x86)
- ppo | rfe | pb is acyclic (LKMM, Power)
- synchronize-with | po is acyclic (C11)

Just structurally, C11 and LKMM are extremely different. Because C11 has 
no notion of ppo, barriers have no local ordering effect. Only globally 
when matched with another barrier on another thread.
Bridging this gap will be hard!


> More importantly, we could improve both
> to get something better? With the ability to exactly express the
> programmers' intention yet still allow optimization by the compilers.


In my humble opinion, programmers shouldn't have the intention of 
relying on dependency ordering :D
I've had a few times people ask me if some barrier could be relaxed due 
to dependency ordering, and I've said "I honestly don't care if it can 
be relaxed until there's some evidence it improves performance".
And I haven't yet seen any convincing evidence that relying on a 
dependency rather than an acquire improves end-to-end performance, which 
isn't surprising considering the hardware optimizations for acquire. 
(But we also haven't measured on PowerPC, where perhaps the lwsync might 
be a tad more expensive).

Nevertheless, ruling out OOTA has some nice practical properties for 
verification methodology.
I think most of the potential improvement is in identifying the cases in 
which compilers won't eliminate dependencies, and showing that this 
covers all the ones that are necessary to rule out OOTA. Namely the ones 
in which the store might be observed by other threads, and the values of 
the read that lead to this store being produced can only come from 
specific stores of other threads.
And then C can follow Viktor's suggestion to just explicitly rule out 
OOTA, without any concrete explanation of how (and without making 
dependencies provide order beyond that).

That said, for a huge code base like Linux where some code just *does* 
rely on dependency ordering, you can't go and kick out that ordering 
from the model. That's why I think it's important to keep it in LKMM, 
but not necessarily add it to C.


>> But I currently don't see that this implementation would be noticeably
>> faster than paying the overhead of lack of inline.
>>
> You are not wrong, surely we will need to real benchmark to know. But my
> rationale is 1) in theory this is faster, 2) we also get a chance to try
> out code based on LKMM with C11 atomics to see where it hurts. Therefore
> I asked ;-)

I think one beautiful thing about open source is that nobody can stop 
you from trying it out yourself :D
It's currently not something I would personally put resources into though.
You could pick a DPDK or CK algorithm and port it to a version using FFI 
instead of using atomics directly, and measure the impact on some 
microbenchmarks.
Then consider that the end-to-end impact on Linux will probably be at 
least one or two orders of magnitude less.

Have fun, jonas

Powered by blists - more mailing lists