linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: hev <r@hev.cc>
To: Peter Zijlstra <peterz@infradead.org>
Cc: Will Deacon <will@kernel.org>, Boqun Feng <boqun.feng@gmail.com>,
	linux-kernel@vger.kernel.org, stern@rowland.harvard.edu,
	parri.andrea@gmail.com, npiggin@gmail.com, dhowells@redhat.com,
	j.alglave@ucl.ac.uk, luc.maranget@inria.fr, paulmck@kernel.org,
	akiyks@gmail.com, dlustig@nvidia.com, joel@joelfernandes.org,
	huacai chen <chenhuacai@gmail.com>, Guo Ren <guoren@kernel.org>,
	geert@linux-m68k.org, Huacai Chen <chenhuacai@loongson.cn>,
	Ingo Molnar <mingo@redhat.com>, Arnd Bergmann <arnd@arndb.de>,
	wangrui <wangrui@loongson.cn>, lixuefeng <lixuefeng@loongson.cn>,
	Jiaxun Yang <jiaxun.yang@flygoat.com>
Subject: Re: [PATCH] Documentation/atomic_t: Document forward progress expectations
Date: Fri, 30 Jul 2021 00:24:14 +0800	[thread overview]
Message-ID: <CAHirt9hsN9cy16TKSn7Bb+HG5M52FR1Ct8=7xDiM14+5K_S8eg@mail.gmail.com> (raw)
In-Reply-To: <YQK9ziyogxTH0m9H@hirez.programming.kicks-ass.net>

Hi, Peter,

On Thu, Jul 29, 2021 at 10:40 PM Peter Zijlstra <peterz@infradead.org> wrote:
>
>
> Add a few words on forward progress; there's been quite a bit of
> confusion on the subject.
>
> Specifically, more complex locking primitives (ticket/qspinlock) require
> forward progress from their consituent operations in order to provide
> better/more guarantees than TaS locks.
>
> Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
> Acked-by: Will Deacon <will@kernel.org>
> Acked-by: Boqun Feng <boqun.feng@gmail.com>
> ---
> --- a/Documentation/atomic_t.txt
> +++ b/Documentation/atomic_t.txt
> @@ -312,3 +312,56 @@ Both provide the same functionality, but
>
>  NB. try_cmpxchg() also generates better code on some platforms (notably x86)
>  where the function more closely matches the hardware instruction.
> +
> +
> +FORWARD PROGRESS
> +----------------
> +
> +In general strong forward progress is expected of all unconditional atomic
> +operations -- those in the Arithmetic and Bitwise classes and xchg(). However
> +a fair amount of code also requires forward progress from the conditional
> +atomic operations.
> +
> +Specifically 'simple' cmpxchg() loops are expected to not starve one another
> +indefinitely. However, this is not evident on LL/SC architectures, because
> +while an LL/SC architecure 'can/should/must' provide forward progress
> +guarantees between competing LL/SC sections, such a guarantee does not
> +transfer to cmpxchg() implemented using LL/SC. Consider:

Thanks for your explanation.

> +
> +  old = atomic_read(&v);
> +  do {
> +    new = func(old);
> +  } while (!atomic_try_cmpxchg(&v, &old, new));

We may need new APIs to help LL/SC to implement atomic operations, but
this is obviously incompatible with native CAS. and many and many
common functions are CAS friendly. Let's more functions that implement
atomic semantics can be overridden by architecture may be a way. ;-)

In the above example, the correct implementation on LL/SC may be like:

do {
    old = LL(&v);
    new = func(old, &skip);
    if (skip) {
        break;
    }
} while (!SC(&v, new);

However, the success of SC may be affected by the inconstant
complexity of func. :-(

Regards,
Rui

> +
> +which on LL/SC becomes something like:
> +
> +  old = atomic_read(&v);
> +  do {
> +    new = func(old);
> +  } while (!({
> +    volatile asm ("1: LL  %[oldval], %[v]\n"
> +                  "   CMP %[oldval], %[old]\n"
> +                  "   BNE 2f\n"
> +                  "   SC  %[new], %[v]\n"
> +                  "   BNE 1b\n"
> +                  "2:\n"
> +                  : [oldval] "=&r" (oldval), [v] "m" (v)
> +                 : [old] "r" (old), [new] "r" (new)
> +                  : "memory");
> +    success = (oldval == old);
> +    if (!success)
> +      old = oldval;
> +    success; }));
> +
> +However, even the forward branch from the failed compare can cause the LL/SC
> +to fail on some architectures, let alone whatever the compiler makes of the C
> +loop body. As a result there is no guarantee what so ever the cacheline
> +containing @v will stay on the local CPU and progress is made.
> +
> +Even native CAS architectures can fail to provide forward progress for their
> +primitive (See Sparc64 for an example).
> +
> +Such implementations are strongly encouraged to add exponential backoff loops
> +to a failed CAS in order to ensure some progress. Affected architectures are
> +also strongly encouraged to inspect/audit the atomic fallbacks, refcount_t and
> +their locking primitives.

  reply	other threads:[~2021-07-29 16:24 UTC|newest]

Thread overview: 4+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-07-29 14:40 Peter Zijlstra
2021-07-29 16:24 ` hev [this message]
2021-07-29 20:03   ` Peter Zijlstra
2021-08-05  9:40 ` [tip: locking/core] " tip-bot2 for Peter Zijlstra

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to='CAHirt9hsN9cy16TKSn7Bb+HG5M52FR1Ct8=7xDiM14+5K_S8eg@mail.gmail.com' \
    --to=r@hev.cc \
    --cc=akiyks@gmail.com \
    --cc=arnd@arndb.de \
    --cc=boqun.feng@gmail.com \
    --cc=chenhuacai@gmail.com \
    --cc=chenhuacai@loongson.cn \
    --cc=dhowells@redhat.com \
    --cc=dlustig@nvidia.com \
    --cc=geert@linux-m68k.org \
    --cc=guoren@kernel.org \
    --cc=j.alglave@ucl.ac.uk \
    --cc=jiaxun.yang@flygoat.com \
    --cc=joel@joelfernandes.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=lixuefeng@loongson.cn \
    --cc=luc.maranget@inria.fr \
    --cc=mingo@redhat.com \
    --cc=npiggin@gmail.com \
    --cc=parri.andrea@gmail.com \
    --cc=paulmck@kernel.org \
    --cc=peterz@infradead.org \
    --cc=stern@rowland.harvard.edu \
    --cc=wangrui@loongson.cn \
    --cc=will@kernel.org \
    --subject='Re: [PATCH] Documentation/atomic_t: Document forward progress expectations' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).