lkml.org 
[lkml]   [2023]   [Jan]   [31]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
SubjectRe: [PATCH] locking/atomic: atomic: Use arch_atomic_{read,set} in generic atomic ops
From


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

\
 
 \ /
  Last update: 2023-03-27 00:03    [W:0.076 / U:0.556 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site