Re: [PATCH RFC 1/2] arch: Introduce ARCH_HAS_HW_XCHG_SMALL

From: Peter Zijlstra <peterz@infradead.org>
To: Guo Ren <guoren@kernel.org>
Cc: Boqun Feng <boqun.feng@gmail.com>,
	Huacai Chen <chenhuacai@gmail.com>,
	Geert Uytterhoeven <geert@linux-m68k.org>,
	Huacai Chen <chenhuacai@loongson.cn>,
	Ingo Molnar <mingo@redhat.com>, Will Deacon <will@kernel.org>,
	Arnd Bergmann <arnd@arndb.de>, Waiman Long <longman@redhat.com>,
	Linux-Arch <linux-arch@vger.kernel.org>,
	Rui Wang <wangrui@loongson.cn>,
	Xuefeng Li <lixuefeng@loongson.cn>,
	Jiaxun Yang <jiaxun.yang@flygoat.com>
Subject: Re: [PATCH RFC 1/2] arch: Introduce ARCH_HAS_HW_XCHG_SMALL
Date: Tue, 27 Jul 2021 12:50:23 +0200	[thread overview]
Message-ID: <YP/k7xB8DwbBI9Lx@hirez.programming.kicks-ass.net> (raw)
In-Reply-To: <CAJF2gTSZdi_U6we4K7Y0M9XsL++Dppdc4jh-UZFxHR+dqBq6fQ@mail.gmail.com>

On Tue, Jul 27, 2021 at 09:07:44AM +0800, Guo Ren wrote:
> On Tue, Jul 27, 2021 at 1:03 AM Boqun Feng <boqun.feng@gmail.com> wrote:

> > I'm missing you point here, a) ll/sc can provide forward progress and b)
> > ll/sc instructions are used to implement xchg/cmpxchg (see ARM64 and
> > PPC).
> I don't think arm64 could provide fwd guarantee with ll/sc, otherwise,
> they wouldn't add ARM64_HAS_LSE_ATOMICS for large systems.

You can do LL/SC with fwd progress, it's just that AMOs can be done
faster.

> That's the problem of "_Q_PENDING_BITS == 1", no hardware could
> provide "load + ALU + cas" fwd guarantee!
> 
> A simple example, atomic a++:
> c = READ_ONCE(g_value);
> new = c + 1;
> while ((old = cmpxchg(&g_value, c, new)) != c) {
>     c = old;
>     new = c + 1;
> }
> 
> Q: When it runs on CPU0(500Mhz) & CPU1(2Ghz) in one SMP, how do we
> prevent CPU1 from starving CPU0?

By not handing the cacheline to CPU1 for a while, similar to LL/SC.

The traditional way of making this work is for LL to hold onto the
exclusive state for a while and the same for a failed CAS. Simply refuse
to yield the line for a while.

OoO CPUs can get all fancy and detect the loop, but simply holding onto
the line for some N instructions mostly works.

The obvious problem is that the LL/SC fwd progress doesn't extend to
cmpxchg() implemented using LL/SC. Typically the body of the cmpxchg()
loop does things that break the exclusive hold.

For things like lock implementations, the best way is to make sure the
primitives are in native form, in this case using xchg16 implemented
with LL/SC (note that implementing xchg16() using cmpxchg() in terms of
LL/SC is terrible and throws everything out the window again).

And if the native form doesn't provide fwd progress, your best option is
to switch to a better architecture :-)