Feedback-ID: iad51458e:Fastmail
Date:   Mon, 30 Jan 2023 10:38:07 -0800
From:   Boqun Feng <boqun.feng@gmail.com>
To:     Jonas Oberhauser <jonas.oberhauser@huaweicloud.com>
Cc:     Peter Zijlstra <peterz@infradead.org>,
        Jules Maselbas <jmaselbas@kalray.eu>,
        Will Deacon <will@kernel.org>,
        Mark Rutland <mark.rutland@arm.com>,
        Arnd Bergmann <arnd@arndb.de>, linux-arch@vger.kernel.org,
        linux-kernel@vger.kernel.org,
        Alan Stern <stern@rowland.harvard.edu>,
        Andrea Parri <parri.andrea@gmail.com>,
        Nicholas Piggin <npiggin@gmail.com>,
        David Howells <dhowells@redhat.com>,
        Jade Alglave <j.alglave@ucl.ac.uk>,
        Luc Maranget <luc.maranget@inria.fr>,
        "Paul E. McKenney" <paulmck@kernel.org>,
        Akira Yokosawa <akiyks@gmail.com>,
        Daniel Lustig <dlustig@nvidia.com>,
        Joel Fernandes <joel@joelfernandes.org>,
        Hernan Ponce de Leon <hernan.poncedeleon@huaweicloud.com>,
        Paul =?iso-8859-1?Q?Heidekr=FCger?= <paul.heidekrueger@in.tum.de>,
        Marco Elver <elver@google.com>,
        Miguel Ojeda <ojeda@kernel.org>,
        Alex Gaynor <alex.gaynor@gmail.com>,
        Wedson Almeida Filho <wedsonaf@gmail.com>,
        Gary Guo <gary@garyguo.net>,
        =?iso-8859-1?Q?Bj=F6rn?= Roy Baron <bjorn3_gh@protonmail.com>
Subject: Re: [PATCH] locking/atomic: atomic: Use arch_atomic_{read,set} in
 generic atomic ops
Message-ID: <Y9gOjzGaWy2hIAmu@boqun-archlinux>
References: <20230126173354.13250-1-jmaselbas@kalray.eu>
 <Y9Oy9ZAj/DQ7O+6e@hirez.programming.kicks-ass.net>
 <20230127134946.GJ5952@tellis.lin.mbt.kalray.eu>
 <Y9Pg+aNM9f48SY5Z@hirez.programming.kicks-ass.net>
 <Y9RLpYGmzW1KPksE@boqun-archlinux>
 <2f4717b3-268f-8db3-e380-4af0a5479901@huaweicloud.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: <2f4717b3-268f-8db3-e380-4af0a5479901@huaweicloud.com>
Precedence: bulk

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.
> > 
> > It'll be a code version of this document:
> > 
> > 	https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p0124r7.html
> > 
> > (although I realise there may be a few mistakes in that doc since I
> > wasn't familiar with C11 memory model when I wrote part of the doc, but
> > these can be fixed)
> > 
> > Another reason I ask is that since Rust is coming, we need to provide
> > our LKMM atomics in Rust so that C code and Rust code can talk via same
> > atomic variables, since both sides need to use the same memory model.
> > My choices are:
> > 
> > 1.	Using FFI to call Linux atomic APIs: not inline therefore not
> > 	efficient.
> > 
> > 2.	Implementing Rust LKMM atomics in asm: much more work although
> > 	I'm OK if we have to do it.
> > 
> > 3.	Implementing Rust LKMM atomics with standard atomics (i.e. C/C++
> > 	atomics):
> > 
> > 	*	Requires Rust has "volatile" atomics, which is WIP but
> > 		looks promising
> > 	
> > 	*	Less efficient compared to choice #2 but more efficient
> > 		compared to choice #1
> > 
> > Ideally, choice #2 is the best option for all architectures, however, if
> > we have the generic implementation based on choice #3, for some archs it
> > may be good enough.
> > 
> > Thoughts?
> 
> Thanks for adding me to the discussion!
> 
> One reason not to rely on C11 is that old compilers don't support it, and
> there may be application scenarios in which new compilers haven't been
> certified.
> I don't know if this is something that affects linux, but linux is so big
> and versatile I'd be surprised if that's irrelevant.
> 

We are gnu11 since last year:

	e8c07082a810 ("Kbuild: move to -std=gnu11")

, so at least for mainline I don't see a problem to use c11 atomics.

> 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.

> 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.

> 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.

> 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" ;-) ;-) ;-)

> 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? 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?
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.

> 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"

> 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). 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.

> 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 ;-)

Regards,
Boqun

> Best wishes, jonas
>