archive mirror
 help / color / mirror / Atom feed
* [PATCH] Documentation/atomic_t: Document forward progress expectations
@ 2021-07-29 14:40 Peter Zijlstra
  2021-07-29 16:24 ` hev
  2021-08-05  9:40 ` [tip: locking/core] " tip-bot2 for Peter Zijlstra
  0 siblings, 2 replies; 4+ messages in thread
From: Peter Zijlstra @ 2021-07-29 14:40 UTC (permalink / raw)
  To: will, peterz, boqun.feng
  Cc: linux-kernel, stern, parri.andrea, npiggin, dhowells, j.alglave,
	luc.maranget, paulmck, akiyks, dlustig, joel, chenhuacai, guoren,
	geert, chenhuacai, mingo, arnd, wangrui, lixuefeng, jiaxun.yang

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) <>
Acked-by: Will Deacon <>
Acked-by: Boqun Feng <>
--- 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.
+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.

^ permalink raw reply	[flat|nested] 4+ messages in thread

end of thread, other threads:[~2021-08-05  9:40 UTC | newest]

Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-07-29 14:40 [PATCH] Documentation/atomic_t: Document forward progress expectations Peter Zijlstra
2021-07-29 16:24 ` hev
2021-07-29 20:03   ` Peter Zijlstra
2021-08-05  9:40 ` [tip: locking/core] " tip-bot2 for Peter Zijlstra

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