From: Peter Zijlstra <peterz@infradead.org>
To: will@kernel.org, peterz@infradead.org, boqun.feng@gmail.com
Cc: 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,
chenhuacai@gmail.com, guoren@kernel.org, geert@linux-m68k.org,
chenhuacai@loongson.cn, mingo@redhat.com, arnd@arndb.de,
wangrui@loongson.cn, lixuefeng@loongson.cn,
jiaxun.yang@flygoat.com
Subject: [PATCH] Documentation/atomic_t: Document forward progress expectations
Date: Thu, 29 Jul 2021 16:40:14 +0200 [thread overview]
Message-ID: <YQK9ziyogxTH0m9H@hirez.programming.kicks-ass.net> (raw)
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:
+
+ old = atomic_read(&v);
+ do {
+ new = func(old);
+ } while (!atomic_try_cmpxchg(&v, &old, new));
+
+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.
next reply other threads:[~2021-07-29 14:40 UTC|newest]
Thread overview: 4+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-07-29 14:40 Peter Zijlstra [this message]
2021-07-29 16:24 ` [PATCH] Documentation/atomic_t: Document forward progress expectations hev
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=YQK9ziyogxTH0m9H@hirez.programming.kicks-ass.net \
--to=peterz@infradead.org \
--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=stern@rowland.harvard.edu \
--cc=wangrui@loongson.cn \
--cc=will@kernel.org \
/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
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
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).