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