Miscellaneous fixes
Subsystems (3)
cover Miscellaneous fixes
Hello!
This RFC series adds some miscellaneous updates to the Linux kernel memory model:
1. Clarify the origin and scope of the tool name to avoid confusion
between "memory model" and "memory management", courtesy of Andrea Parri.
2. Move the maintainer list for LKMM to the main MAINTAINERS file,
courtesy of Andrea Parri.
3. Add memory-barriers.txt to the LKMM MAINTAINERS entry, courtesy
of Andrea Parri.
4. Add comments explaining the purpose of the various litmus tests.
5. Fix punctuation errors in litmus-tests/README.
6. Add Akira Yokosawa as an LKMM reviewer.
7. Cross-reference tools/memory-model from memory-barriers.txt,
courtesy of Andrea Parri and Akira Yokosawa.
8. Fix description of data dependency barriers, courtesy of
Nikolay Borisov.
9. Add required herd7 version to README file.
10. Add a S lock-based external-view litmus test, courtesy of Alan
Stern.
11. Convert underscores to hyphens in .bell and .cat files for
consistency with typical cat-language code.
12. Remove rb-dep, smp_read_barrier_depends, and lockless_dereference,
which reflect recent Linux-kernel changes, courtesy of Alan Stern.
Changes since v1:
o Applied feedback from v1 posting.
o Squashing patches together, as promised in v1.
o Added patches 7-10 and 12.
Thanx, Paul
------------------------------------------------------------------------
/tools/memory-model/MAINTAINERS | 15 - b/Documentation/memory-barriers.txt | 8 b/MAINTAINERS | 18 ++ b/tools/memory-model/Documentation/cheatsheet.txt | 3 b/tools/memory-model/Documentation/explanation.txt | 81 +++++----- b/tools/memory-model/MAINTAINERS | 2 b/tools/memory-model/README | 17 +- b/tools/memory-model/linux-kernel.bell | 9 - b/tools/memory-model/linux-kernel.cat | 15 - b/tools/memory-model/linux-kernel.def | 8 b/tools/memory-model/litmus-tests/CoRR+poonceonce+Once.litmus | 7 b/tools/memory-model/litmus-tests/CoRW+poonceonce+Once.litmus | 7 b/tools/memory-model/litmus-tests/CoWR+poonceonce+Once.litmus | 7 b/tools/memory-model/litmus-tests/CoWW+poonceonce.litmus | 7 b/tools/memory-model/litmus-tests/IRIW+mbonceonces+OnceOnce.litmus | 10 + b/tools/memory-model/litmus-tests/IRIW+poonceonces+OnceOnce.litmus | 10 + b/tools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmus | 41 +++++ b/tools/memory-model/litmus-tests/ISA2+poonceonces.litmus | 9 + b/tools/memory-model/litmus-tests/ISA2+pooncerelease+poacquirerelease+poacquireonce.litmus | 11 + b/tools/memory-model/litmus-tests/LB+ctrlonceonce+mbonceonce.litmus | 11 + b/tools/memory-model/litmus-tests/LB+poacquireonce+pooncerelease.litmus | 8 b/tools/memory-model/litmus-tests/LB+poonceonces.litmus | 7 b/tools/memory-model/litmus-tests/MP+onceassign+derefonce.litmus | 11 + b/tools/memory-model/litmus-tests/MP+polocks.litmus | 11 + b/tools/memory-model/litmus-tests/MP+poonceonces.litmus | 7 b/tools/memory-model/litmus-tests/MP+pooncerelease+poacquireonce.litmus | 8 b/tools/memory-model/litmus-tests/MP+porevlocks.litmus | 11 + b/tools/memory-model/litmus-tests/MP+wmbonceonce+rmbonceonce.litmus | 8 b/tools/memory-model/litmus-tests/R+mbonceonces.litmus | 9 + b/tools/memory-model/litmus-tests/R+poonceonces.litmus | 8 b/tools/memory-model/litmus-tests/README | 4 b/tools/memory-model/litmus-tests/S+poonceonces.litmus | 9 + b/tools/memory-model/litmus-tests/S+wmbonceonce+poacquireonce.litmus | 7 b/tools/memory-model/litmus-tests/SB+mbonceonces.litmus | 9 + b/tools/memory-model/litmus-tests/SB+poonceonces.litmus | 8 b/tools/memory-model/litmus-tests/WRC+poonceonces+Once.litmus | 8 b/tools/memory-model/litmus-tests/WRC+pooncerelease+rmbonceonce+Once.litmus | 8 b/tools/memory-model/litmus-tests/Z6.0+pooncelock+poonceLock+pombonce.litmus | 9 + b/tools/memory-model/litmus-tests/Z6.0+pooncelock+pooncelock+pombonce.litmus | 8 b/tools/memory-model/litmus-tests/Z6.0+pooncerelease+poacquirerelease+mbonceonce.litmus | 14 + 40 files changed, 380 insertions(+), 88 deletions(-)
RFC PATCH 2/12 MAINTAINERS: Add the Memory Consistency Model subsystem
From: Andrea Parri <[email protected]>
Move the contents of tools/memory-model/MAINTAINERS into the main MAINTAINERS file, removing tools/memory-model/MAINTAINERS. This allows get_maintainer.pl to correctly identify the maintainers of tools/memory-model/.
--- MAINTAINERS | 16 ++++++++++++++++ tools/memory-model/MAINTAINERS | 15 --------------- 2 files changed, 16 insertions(+), 15 deletions(-) delete mode 100644 tools/memory-model/MAINTAINERS
MAINTAINERS +16 -0
@@ -8086,6 +8086,22 @@ M: Kees Cook <[email protected]> S: Maintained F: drivers/misc/lkdtm* +LINUX KERNEL MEMORY CONSISTENCY MODEL (LKMM) +M: Alan Stern <[email protected]> +M: Andrea Parri <[email protected]> +M: Will Deacon <[email protected]> +M: Peter Zijlstra <[email protected]> +M: Boqun Feng <[email protected]> +M: Nicholas Piggin <[email protected]> +M: David Howells <[email protected]> +M: Jade Alglave <[email protected]> +M: Luc Maranget <[email protected]> +M: "Paul E. McKenney" <[email protected]> +L: [email protected] +S: Supported +T: git git://git.kernel.org/pub/scm/linux/kernel/git/paulmck/linux-rcu.git +F: tools/memory-model/ + LINUX SECURITY MODULE (LSM) FRAMEWORK M: Chris Wright <[email protected]> L: [email protected]
tools/memory-model/MAINTAINERS deleted +0 -15
@@ -1,15 +0,0 @@ -LINUX KERNEL MEMORY CONSISTENCY MODEL -M: Alan Stern <[email protected]> -M: Andrea Parri <[email protected]> -M: Will Deacon <[email protected]> -M: Peter Zijlstra <[email protected]> -M: Boqun Feng <[email protected]> -M: Nicholas Piggin <[email protected]> -M: David Howells <[email protected]> -M: Jade Alglave <[email protected]> -M: Luc Maranget <[email protected]> -M: "Paul E. McKenney" <[email protected]> -L: [email protected] -S: Supported -T: git git://git.kernel.org/pub/scm/linux/kernel/git/paulmck/linux-rcu.git -F: tools/memory-model/
Signature · 1 line
2.5.2
RFC PATCH 3/12 MAINTAINERS: List file memory-barriers.txt within the LKMM entry
In reply to Paul E. McKenneyFrom: Andrea Parri <[email protected]>
We now have a shiny new Linux-kernel memory model (LKMM) and the old tried-and-true Documentation/memory-barrier.txt. It would be good to keep these automatically synchronized, but in the meantime we need at least let people know that they are related. Will suggested adding the Documentation/memory-barrier.txt file to the LKMM maintainership list, thus making the LKMM maintainers responsible for both the old and the new. This commit follows Will's excellent suggestion.
--- MAINTAINERS | 1 + 1 file changed, 1 insertion(+)
MAINTAINERS +1 -0
@@ -8101,6 +8101,7 @@ L: [email protected] S: Supported T: git git://git.kernel.org/pub/scm/linux/kernel/git/paulmck/linux-rcu.git F: tools/memory-model/ +F: Documentation/memory-barriers.txt LINUX SECURITY MODULE (LSM) FRAMEWORK M: Chris Wright <[email protected]>
Signature · 1 line
2.5.2
RFC PATCH 5/12 README: Fix a couple of punctuation errors
In reply to Paul E. McKenney--- tools/memory-model/litmus-tests/README | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
tools/memory-model/litmus-tests/README +2 -2
@@ -23,14 +23,14 @@ IRIW+mbonceonces+OnceOnce.litmus between each pairs of reads. In other words, is smp_mb() sufficient to cause two different reading processes to agree on the order of a pair of writes, where each write is to a different - variable by a different process. + variable by a different process? IRIW+poonceonces+OnceOnce.litmus Test of independent reads from independent writes with nothing between each pairs of reads. In other words, is anything at all needed to cause two different reading processes to agree on the order of a pair of writes, where each write is to a different - variable by a different process. + variable by a different process? ISA2+poonceonces.litmus As below, but with store-release replaced with WRITE_ONCE()
Signature · 1 line
2.5.2
RFC PATCH 6/12 MAINTAINERS: Add Akira Yokosawa as an LKMM reviewer
In reply to Paul E. McKenney--- MAINTAINERS | 1 + 1 file changed, 1 insertion(+)
MAINTAINERS +1 -0
@@ -8097,6 +8097,7 @@ M: David Howells <[email protected]> M: Jade Alglave <[email protected]> M: Luc Maranget <[email protected]> M: "Paul E. McKenney" <[email protected]> +R: Akira Yokosawa <[email protected]> L: [email protected] S: Supported T: git git://git.kernel.org/pub/scm/linux/kernel/git/paulmck/linux-rcu.git
Signature · 1 line
2.5.2
RFC PATCH 10/12 tools/memory-model: Add a S lock-based external-view litmus test
In reply to Paul E. McKenneyFrom: Alan Stern <[email protected]>
This commit adds a litmus test in which P0() and P1() form a lock-based S litmus test, with the addition of P2(), which observes P0()'s and P1()'s accesses with a full memory barrier but without the lock. This litmus test asks whether writes carried out by two different processes under the same lock will be seen in order by a third process not holding that lock. The answer to this question is "yes" for all architectures supporting the Linux kernel, but is "no" according to the current version of LKMM.
A patch to LKMM is under development.
--- .../ISA2+pooncelock+pooncelock+pombonce.litmus | 41 ++++++++++++++++++++++ 1 file changed, 41 insertions(+) create mode 100644 tools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmus
tools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmus new file +41 -0
@@ -0,0 +1,41 @@ +C ISA2+pooncelock+pooncelock+pombonce.litmus + +(* + * Result: Sometimes + * + * This test shows that the ordering provided by a lock-protected S + * litmus test (P0() and P1()) are not visible to external process P2(). + * This is likely to change soon. + *) + +{} + +P0(int *x, int *y, spinlock_t *mylock) +{ + spin_lock(mylock); + WRITE_ONCE(*x, 1); + WRITE_ONCE(*y, 1); + spin_unlock(mylock); +} + +P1(int *y, int *z, spinlock_t *mylock) +{ + int r0; + + spin_lock(mylock); + r0 = READ_ONCE(*y); + WRITE_ONCE(*z, 1); + spin_unlock(mylock); +} + +P2(int *x, int *z) +{ + int r1; + int r2; + + r2 = READ_ONCE(*z); + smp_mb(); + r1 = READ_ONCE(*x); +} + +exists (1:r0=1 /\ 2:r2=1 /\ 2:r1=0)
Signature · 1 line
2.5.2
RFC PATCH 7/12 Documentation/memory-barriers.txt: Cross-reference "tools/memory-model/"
In reply to Paul E. McKenneyFrom: Andrea Parri <[email protected]>
A memory consistency model is now available for the Linux kernel [1], which "can (roughly speaking) be thought of as an automated version of memory-barriers.txt" and which is (in turn) "accompanied by extensive documentation on its use and its design".
Inform the (occasional) reader of memory-barriers.txt of these developments.
[1] https://marc.info/?l=linux-kernel&m=151687290114799&w=2
--- Documentation/memory-barriers.txt | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-)
Documentation/memory-barriers.txt +5 -1
@@ -14,7 +14,11 @@ DISCLAIMER This document is not a specification; it is intentionally (for the sake of brevity) and unintentionally (due to being human) incomplete. This document is meant as a guide to using the various memory barriers provided by Linux, but -in case of any doubt (and there are many) please ask. +in case of any doubt (and there are many) please ask. Some doubts may be +resolved by referring to the formal memory consistency model and related +documentation at tools/memory-model/. Nevertheless, even this memory +model should be viewed as the collective opinion of its maintainers rather +than as an infallible oracle. To repeat, this document is not a specification of what Linux expects from hardware.
Signature · 1 line
2.5.2
RFC PATCH 11/12 tools/memory-model: Convert underscores to hyphens
In reply to Paul E. McKenneyTypical cat-language code uses hyphens for word separators in identifiers, but several LKMM identifiers use underscores instead. This commit therefore converts underscores to hyphens in the .bell- and .cat-file identifiers corresponding to smp_mb__before_atomic(), smp_mb__after_atomic(), and smp_mb__after_spinlock().
--- tools/memory-model/linux-kernel.bell | 6 +++--- tools/memory-model/linux-kernel.cat | 6 +++--- tools/memory-model/linux-kernel.def | 6 +++--- 3 files changed, 9 insertions(+), 9 deletions(-)
tools/memory-model/linux-kernel.bell +3 -3
@@ -28,9 +28,9 @@ enum Barriers = 'wmb (*smp_wmb*) || 'rcu-lock (*rcu_read_lock*) || 'rcu-unlock (*rcu_read_unlock*) || 'sync-rcu (*synchronize_rcu*) || - 'before_atomic (*smp_mb__before_atomic*) || - 'after_atomic (*smp_mb__after_atomic*) || - 'after_spinlock (*smp_mb__after_spinlock*) + 'before-atomic (*smp_mb__before_atomic*) || + 'after-atomic (*smp_mb__after_atomic*) || + 'after-spinlock (*smp_mb__after_spinlock*) instructions F[Barriers] (* Compute matching pairs of nested Rcu-lock and Rcu-unlock *)
tools/memory-model/linux-kernel.cat +3 -3
@@ -29,9 +29,9 @@ let rb-dep = [R] ; fencerel(Rb_dep) ; [R] let rmb = [R \ Noreturn] ; fencerel(Rmb) ; [R \ Noreturn] let wmb = [W] ; fencerel(Wmb) ; [W] let mb = ([M] ; fencerel(Mb) ; [M]) | - ([M] ; fencerel(Before_atomic) ; [RMW] ; po? ; [M]) | - ([M] ; po? ; [RMW] ; fencerel(After_atomic) ; [M]) | - ([M] ; po? ; [LKW] ; fencerel(After_spinlock) ; [M]) + ([M] ; fencerel(Before-atomic) ; [RMW] ; po? ; [M]) | + ([M] ; po? ; [RMW] ; fencerel(After-atomic) ; [M]) | + ([M] ; po? ; [LKW] ; fencerel(After-spinlock) ; [M]) let gp = po ; [Sync-rcu] ; po? let strong-fence = mb | gp
tools/memory-model/linux-kernel.def +3 -3
@@ -21,9 +21,9 @@ smp_mb() { __fence{mb} ; } smp_rmb() { __fence{rmb} ; } smp_wmb() { __fence{wmb} ; } smp_read_barrier_depends() { __fence{rb_dep}; } -smp_mb__before_atomic() { __fence{before_atomic} ; } -smp_mb__after_atomic() { __fence{after_atomic} ; } -smp_mb__after_spinlock() { __fence{after_spinlock} ; } +smp_mb__before_atomic() { __fence{before-atomic} ; } +smp_mb__after_atomic() { __fence{after-atomic} ; } +smp_mb__after_spinlock() { __fence{after-spinlock} ; } // Exchange xchg(X,V) __xchg{mb}(X,V)
Signature · 1 line
2.5.2
RFC PATCH 1/12 tools/memory-model: Clarify the origin/scope of the tool name
In reply to Paul E. McKenneyFrom: Andrea Parri <[email protected]>
Ingo pointed out that:
"The "memory model" name is overly generic, ambiguous and somewhat
misleading, as we usually mean the virtual memory layout/model when we say "memory model". GCC too uses it in that sense [...]"
Make it clear that tools/memory-model/ uses the term "memory model" as shorthand for "memory consistency model" by calling out this convention in tools/memory-model/README.
Stick to the original "memory model" term in sources' headers and for the subsystem name.
--- tools/memory-model/MAINTAINERS | 2 +- tools/memory-model/README | 14 +++++++------- tools/memory-model/linux-kernel.bell | 2 +- tools/memory-model/linux-kernel.cat | 2 +- 4 files changed, 10 insertions(+), 10 deletions(-)
tools/memory-model/MAINTAINERS +1 -1
@@ -1,4 +1,4 @@ -LINUX KERNEL MEMORY MODEL +LINUX KERNEL MEMORY CONSISTENCY MODEL M: Alan Stern <[email protected]> M: Andrea Parri <[email protected]> M: Will Deacon <[email protected]>
tools/memory-model/README +7 -7
@@ -1,15 +1,15 @@ - ========================= - LINUX KERNEL MEMORY MODEL - ========================= + ===================================== + LINUX KERNEL MEMORY CONSISTENCY MODEL + ===================================== ============ INTRODUCTION ============ -This directory contains the memory model of the Linux kernel, written -in the "cat" language and executable by the (externally provided) -"herd7" simulator, which exhaustively explores the state space of -small litmus tests. +This directory contains the memory consistency model (memory model, for +short) of the Linux kernel, written in the "cat" language and executable +by the externally provided "herd7" simulator, which exhaustively explores +the state space of small litmus tests. In addition, the "klitmus7" tool (also externally provided) may be used to convert a litmus test to a Linux kernel module, which in turn allows
tools/memory-model/linux-kernel.bell +1 -1
@@ -11,7 +11,7 @@ * which is to appear in ASPLOS 2018. *) -"Linux kernel memory model" +"Linux-kernel memory consistency model" enum Accesses = 'once (*READ_ONCE,WRITE_ONCE,ACCESS_ONCE*) || 'release (*smp_store_release*) ||
tools/memory-model/linux-kernel.cat +1 -1
@@ -11,7 +11,7 @@ * which is to appear in ASPLOS 2018. *) -"Linux kernel memory model" +"Linux-kernel memory consistency model" (* * File "lock.cat" handles locks and is experimental.
Signature · 1 line
2.5.2
RFC PATCH 4/12 EXP litmus_tests: Add comments explaining tests' purposes
In reply to Paul E. McKenneyThis commit adds comments to the litmus tests summarizing what these tests are intended to demonstrate.
--- .../memory-model/litmus-tests/CoRR+poonceonce+Once.litmus | 7 +++++++ .../memory-model/litmus-tests/CoRW+poonceonce+Once.litmus | 7 +++++++ .../memory-model/litmus-tests/CoWR+poonceonce+Once.litmus | 7 +++++++ tools/memory-model/litmus-tests/CoWW+poonceonce.litmus | 7 +++++++ .../litmus-tests/IRIW+mbonceonces+OnceOnce.litmus | 10 ++++++++++ .../litmus-tests/IRIW+poonceonces+OnceOnce.litmus | 10 ++++++++++ tools/memory-model/litmus-tests/ISA2+poonceonces.litmus | 9 +++++++++ ...SA2+pooncerelease+poacquirerelease+poacquireonce.litmus | 11 +++++++++++ .../litmus-tests/LB+ctrlonceonce+mbonceonce.litmus | 11 +++++++++++ .../litmus-tests/LB+poacquireonce+pooncerelease.litmus | 8 ++++++++ tools/memory-model/litmus-tests/LB+poonceonces.litmus | 7 +++++++ .../litmus-tests/MP+onceassign+derefonce.litmus | 11 ++++++++++- tools/memory-model/litmus-tests/MP+polocks.litmus | 11 +++++++++++ tools/memory-model/litmus-tests/MP+poonceonces.litmus | 7 +++++++ .../litmus-tests/MP+pooncerelease+poacquireonce.litmus | 8 ++++++++ tools/memory-model/litmus-tests/MP+porevlocks.litmus | 11 +++++++++++ .../litmus-tests/MP+wmbonceonce+rmbonceonce.litmus | 8 ++++++++ tools/memory-model/litmus-tests/R+mbonceonces.litmus | 9 +++++++++ tools/memory-model/litmus-tests/R+poonceonces.litmus | 8 ++++++++ tools/memory-model/litmus-tests/S+poonceonces.litmus | 9 +++++++++ .../litmus-tests/S+wmbonceonce+poacquireonce.litmus | 7 +++++++ tools/memory-model/litmus-tests/SB+mbonceonces.litmus | 9 +++++++++ tools/memory-model/litmus-tests/SB+poonceonces.litmus | 8 ++++++++ .../memory-model/litmus-tests/WRC+poonceonces+Once.litmus | 8 ++++++++ .../litmus-tests/WRC+pooncerelease+rmbonceonce+Once.litmus | 8 ++++++++ .../Z6.0+pooncelock+poonceLock+pombonce.litmus | 9 +++++++++ .../Z6.0+pooncelock+pooncelock+pombonce.litmus | 8 ++++++++ .../Z6.0+pooncerelease+poacquirerelease+mbonceonce.litmus | 14 ++++++++++++++ 28 files changed, 246 insertions(+), 1 deletion(-)
tools/memory-model/litmus-tests/CoRR+poonceonce+Once.litmus +7 -0
@@ -1,5 +1,12 @@ C CoRR+poonceonce+Once +(* + * Result: Never + * + * Test of read-read coherence, that is, whether or not two successive + * reads from the same variable are ordered. + *) + {} P0(int *x)
tools/memory-model/litmus-tests/CoRW+poonceonce+Once.litmus +7 -0
@@ -1,5 +1,12 @@ C CoRW+poonceonce+Once +(* + * Result: Never + * + * Test of read-write coherence, that is, whether or not a read from + * a given variable and a later write to that same variable are ordered. + *) + {} P0(int *x)
tools/memory-model/litmus-tests/CoWR+poonceonce+Once.litmus +7 -0
@@ -1,5 +1,12 @@ C CoWR+poonceonce+Once +(* + * Result: Never + * + * Test of write-read coherence, that is, whether or not a write to a + * given variable and a later read from that same variable are ordered. + *) + {} P0(int *x)
tools/memory-model/litmus-tests/CoWW+poonceonce.litmus +7 -0
@@ -1,5 +1,12 @@ C CoWW+poonceonce +(* + * Result: Never + * + * Test of write-write coherence, that is, whether or not two successive + * writes to the same variable are ordered. + *) + {} P0(int *x)
tools/memory-model/litmus-tests/IRIW+mbonceonces+OnceOnce.litmus +10 -0
@@ -1,5 +1,15 @@ C IRIW+mbonceonces+OnceOnce +(* + * Result: Never + * + * Test of independent reads from independent writes with smp_mb() + * between each pairs of reads. In other words, is smp_mb() sufficient to + * cause two different reading processes to agree on the order of a pair + * of writes, where each write is to a different variable by a different + * process? + *) + {} P0(int *x)
tools/memory-model/litmus-tests/IRIW+poonceonces+OnceOnce.litmus +10 -0
@@ -1,5 +1,15 @@ C IRIW+poonceonces+OnceOnce +(* + * Result: Sometimes + * + * Test of independent reads from independent writes with nothing + * between each pairs of reads. In other words, is anything at all + * needed to cause two different reading processes to agree on the order + * of a pair of writes, where each write is to a different variable by a + * different process? + *) + {} P0(int *x)
tools/memory-model/litmus-tests/ISA2+poonceonces.litmus +9 -0
@@ -1,5 +1,14 @@ C ISA2+poonceonces +(* + * Result: Sometimes + * + * Given a release-acquire chain ordering the first process's store + * against the last process's load, is ordering preserved if all of the + * smp_store_release() invocations are replaced by WRITE_ONCE() and all + * of the smp_load_acquire() invocations are replaced by READ_ONCE()? + *) + {} P0(int *x, int *y)
tools/memory-model/litmus-tests/ISA2+pooncerelease+poacquirerelease+poacquireonce.litmus +11 -0
@@ -1,5 +1,16 @@ C ISA2+pooncerelease+poacquirerelease+poacquireonce +(* + * Result: Never + * + * This litmus test demonstrates that a release-acquire chain suffices + * to order P0()'s initial write against P2()'s final read. The reason + * that the release-acquire chain suffices is because in all but one + * case (P2() to P0()), each process reads from the preceding process's + * write. In memory-model-speak, there is only one non-reads-from + * (AKA non-rf) link, so release-acquire is all that is needed. + *) + {} P0(int *x, int *y)
tools/memory-model/litmus-tests/LB+ctrlonceonce+mbonceonce.litmus +11 -0
@@ -1,5 +1,16 @@ C LB+ctrlonceonce+mbonceonce +(* + * Result: Never + * + * This litmus test demonstrates that lightweight ordering suffices for + * the load-buffering pattern, in other words, preventing all processes + * reading from the preceding process's write. In this example, the + * combination of a control dependency and a full memory barrier are enough + * to do the trick. (But the full memory barrier could be replaced with + * another control dependency and order would still be maintained.) + *) + {} P0(int *x, int *y)
tools/memory-model/litmus-tests/LB+poacquireonce+pooncerelease.litmus +8 -0
@@ -1,5 +1,13 @@ C LB+poacquireonce+pooncerelease +(* + * Result: Never + * + * Does a release-acquire pair suffice for the load-buffering litmus + * test, where each process reads from one of two variables then writes + * to the other? + *) + {} P0(int *x, int *y)
tools/memory-model/litmus-tests/LB+poonceonces.litmus +7 -0
@@ -1,5 +1,12 @@ C LB+poonceonces +(* + * Result: Sometimes + * + * Can the counter-intuitive outcome for the load-buffering pattern + * be prevented even with no explicit ordering? + *) + {} P0(int *x, int *y)
tools/memory-model/litmus-tests/MP+onceassign+derefonce.litmus +10 -1
@@ -1,4 +1,13 @@ -C MP+onceassign+derefonce.litmus +C MP+onceassign+derefonce + +(* + * Result: Never + * + * This litmus test demonstrates that rcu_assign_pointer() and + * rcu_dereference() suffice to ensure that an RCU reader will not see + * pre-initialization garbage when it traverses an RCU-protected data + * structure containing a newly inserted element. + *) { y=z;
tools/memory-model/litmus-tests/MP+polocks.litmus +11 -0
@@ -1,5 +1,16 @@ C MP+polocks +(* + * Result: Never + * + * This litmus test demonstrates how lock acquisitions and releases can + * stand in for smp_load_acquire() and smp_store_release(), respectively. + * In other words, when holding a given lock (or indeed after releasing a + * given lock), a CPU is not only guaranteed to see the accesses that other + * CPUs made while previously holding that lock, it is also guaranteed + * to see all prior accesses by those other CPUs. + *) + {} P0(int *x, int *y, spinlock_t *mylock)
tools/memory-model/litmus-tests/MP+poonceonces.litmus +7 -0
@@ -1,5 +1,12 @@ C MP+poonceonces +(* + * Result: Maybe + * + * Can the counter-intuitive message-passing outcome be prevented with + * no ordering at all? + *) + {} P0(int *x, int *y)
tools/memory-model/litmus-tests/MP+pooncerelease+poacquireonce.litmus +8 -0
@@ -1,5 +1,13 @@ C MP+pooncerelease+poacquireonce +(* + * Result: Never + * + * This litmus test demonstrates that smp_store_release() and + * smp_load_acquire() provide sufficient ordering for the message-passing + * pattern. + *) + {} P0(int *x, int *y)
tools/memory-model/litmus-tests/MP+porevlocks.litmus +11 -0
@@ -1,5 +1,16 @@ C MP+porevlocks +(* + * Result: Never + * + * This litmus test demonstrates how lock acquisitions and releases can + * stand in for smp_load_acquire() and smp_store_release(), respectively. + * In other words, when holding a given lock (or indeed after releasing a + * given lock), a CPU is not only guaranteed to see the accesses that other + * CPUs made while previously holding that lock, it is also guaranteed to + * see all prior accesses by those other CPUs. + *) + {} P0(int *x, int *y, spinlock_t *mylock)
tools/memory-model/litmus-tests/MP+wmbonceonce+rmbonceonce.litmus +8 -0
@@ -1,5 +1,13 @@ C MP+wmbonceonce+rmbonceonce +(* + * Result: Never + * + * This litmus test demonstrates that smp_wmb() and smp_rmb() provide + * sufficient ordering for the message-passing pattern. However, it + * is usually better to use smp_store_release() and smp_load_acquire(). + *) + {} P0(int *x, int *y)
tools/memory-model/litmus-tests/R+mbonceonces.litmus +9 -0
@@ -1,5 +1,14 @@ C R+mbonceonces +(* + * Result: Never + * + * This is the fully ordered (via smp_mb()) version of one of the classic + * counterintuitive litmus tests that illustrates the effects of store + * propagation delays. Note that weakening either of the barriers would + * cause the resulting test to be allowed. + *) + {} P0(int *x, int *y)
tools/memory-model/litmus-tests/R+poonceonces.litmus +8 -0
@@ -1,5 +1,13 @@ C R+poonceonces +(* + * Result: Sometimes + * + * This is the unordered (thus lacking smp_mb()) version of one of the + * classic counterintuitive litmus tests that illustrates the effects of + * store propagation delays. + *) + {} P0(int *x, int *y)
tools/memory-model/litmus-tests/S+poonceonces.litmus +9 -0
@@ -1,5 +1,14 @@ C S+poonceonces +(* + * Result: Sometimes + * + * Starting with a two-process release-acquire chain ordering P0()'s + * first store against P1()'s final load, if the smp_store_release() + * is replaced by WRITE_ONCE() and the smp_load_acquire() replaced by + * READ_ONCE(), is ordering preserved? + *) + {} P0(int *x, int *y)
tools/memory-model/litmus-tests/S+wmbonceonce+poacquireonce.litmus +7 -0
@@ -1,5 +1,12 @@ C S+wmbonceonce+poacquireonce +(* + * Result: Never + * + * Can a smp_wmb(), instead of a release, and an acquire order a prior + * store against a subsequent store? + *) + {} P0(int *x, int *y)
tools/memory-model/litmus-tests/SB+mbonceonces.litmus +9 -0
@@ -1,5 +1,14 @@ C SB+mbonceonces +(* + * Result: Never + * + * This litmus test demonstrates that full memory barriers suffice to + * order the store-buffering pattern, where each process writes to the + * variable that the preceding process reads. (Locking and RCU can also + * suffice, but not much else.) + *) + {} P0(int *x, int *y)
tools/memory-model/litmus-tests/SB+poonceonces.litmus +8 -0
@@ -1,5 +1,13 @@ C SB+poonceonces +(* + * Result: Sometimes + * + * This litmus test demonstrates that at least some ordering is required + * to order the store-buffering pattern, where each process writes to the + * variable that the preceding process reads. + *) + {} P0(int *x, int *y)
tools/memory-model/litmus-tests/WRC+poonceonces+Once.litmus +8 -0
@@ -1,5 +1,13 @@ C WRC+poonceonces+Once +(* + * Result: Sometimes + * + * This litmus test is an extension of the message-passing pattern, + * where the first write is moved to a separate process. Note that this + * test has no ordering at all. + *) + {} P0(int *x)
tools/memory-model/litmus-tests/WRC+pooncerelease+rmbonceonce+Once.litmus +8 -0
@@ -1,5 +1,13 @@ C WRC+pooncerelease+rmbonceonce+Once +(* + * Result: Never + * + * This litmus test is an extension of the message-passing pattern, where + * the first write is moved to a separate process. Because it features + * a release and a read memory barrier, it should be forbidden. + *) + {} P0(int *x)
tools/memory-model/litmus-tests/Z6.0+pooncelock+poonceLock+pombonce.litmus +9 -0
@@ -1,5 +1,14 @@ C Z6.0+pooncelock+poonceLock+pombonce +(* + * Result: Never + * + * This litmus test demonstrates how smp_mb__after_spinlock() may be + * used to ensure that accesses in different critical sections for a + * given lock running on different CPUs are nevertheless seen in order + * by CPUs not holding that lock. + *) + {} P0(int *x, int *y, spinlock_t *mylock)
tools/memory-model/litmus-tests/Z6.0+pooncelock+pooncelock+pombonce.litmus +8 -0
@@ -1,5 +1,13 @@ C Z6.0+pooncelock+pooncelock+pombonce +(* + * Result: Sometimes + * + * This example demonstrates that a pair of accesses made by different + * processes each while holding a given lock will not necessarily be + * seen as ordered by a third process not holding that lock. + *) + {} P0(int *x, int *y, spinlock_t *mylock)
tools/memory-model/litmus-tests/Z6.0+pooncerelease+poacquirerelease+mbonceonce.litmus +14 -0
@@ -1,5 +1,19 @@ C Z6.0+pooncerelease+poacquirerelease+mbonceonce +(* + * Result: Sometimes + * + * This litmus test shows that a release-acquire chain, while sufficient + * when there is but one non-reads-from (AKA non-rf) link, does not suffice + * if there is more than one. Of the three processes, only P1() reads from + * P0's write, which means that there are two non-rf links: P1() to P2() + * is a write-to-write link (AKA a "coherence" or just "co" link) and P2() + * to P0() is a read-to-write link (AKA a "from-reads" or just "fr" link). + * When there are two or more non-rf links, you typically will need one + * full barrier for each non-rf link. (Exceptions include some cases + * involving locking.) + *) + {} P0(int *x, int *y)
Signature · 1 line
2.5.2
RFC PATCH 9/12 tools/memory-model: Add required herd7 version to README file
In reply to Paul E. McKenneyLKMM and the herd7 tool are co-evolving, and out-of-date herd7 tools produce inaccurate results, often with no obvious error messages. This commit therefore adds the required herd7 version to the LKMM README file.
Longer term, it would be good if .cat files could specify the required version in a manner allowing herd7 to produce clear diagnostics.
--- tools/memory-model/README | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)
tools/memory-model/README +2 -1
@@ -20,7 +20,8 @@ that litmus test to be exercised within the Linux kernel. REQUIREMENTS ============ -The "herd7" and "klitmus7" tools must be downloaded separately: +Version 7.48 of the "herd7" and "klitmus7" tools must be downloaded +separately: https://github.com/herd/herdtools7
Signature · 1 line
2.5.2
RFC PATCH 12/12 tools/memory-model: Remove rb-dep, smp_read_barrier_depends, and lockless_dereference
In reply to Paul E. McKenneyFrom: Alan Stern <[email protected]>
Since commit 76ebbe78f739 ("locking/barriers: Add implicit smp_read_barrier_depends() to READ_ONCE()") was merged for the 4.15 kernel, it has not been necessary to use smp_read_barrier_depends(). Similarly, commit 59ecbbe7b31c ("locking/barriers: Kill lockless_dereference()") removed lockless_dereference() from the kernel.
Since these primitives are no longer part of the kernel, they do not belong in the Linux Kernel Memory Consistency Model. This patch removes them, along with the internal rb-dep relation, and updates the revelant documentation.
--- tools/memory-model/Documentation/cheatsheet.txt | 3 +- tools/memory-model/Documentation/explanation.txt | 81 +++++++++++++----------- tools/memory-model/linux-kernel.bell | 1 - tools/memory-model/linux-kernel.cat | 7 +- tools/memory-model/linux-kernel.def | 2 - 5 files changed, 46 insertions(+), 48 deletions(-)
tools/memory-model/Documentation/cheatsheet.txt +1 -2
@@ -6,8 +6,7 @@ Store, e.g., WRITE_ONCE() Y Y Load, e.g., READ_ONCE() Y Y Y Unsuccessful RMW operation Y Y Y -smp_read_barrier_depends() Y Y Y -*_dereference() Y Y Y Y +rcu_dereference() Y Y Y Y Successful *_acquire() R Y Y Y Y Y Y Successful *_release() C Y Y Y W Y smp_rmb() Y R Y Y R
tools/memory-model/Documentation/explanation.txt +43 -38
144 lines not on this page · raw message
tools/memory-model/linux-kernel.bell +0 -1
@@ -24,7 +24,6 @@ instructions RMW[{'once,'acquire,'release}] enum Barriers = 'wmb (*smp_wmb*) || 'rmb (*smp_rmb*) || 'mb (*smp_mb*) || - 'rb_dep (*smp_read_barrier_depends*) || 'rcu-lock (*rcu_read_lock*) || 'rcu-unlock (*rcu_read_unlock*) || 'sync-rcu (*synchronize_rcu*) ||
tools/memory-model/linux-kernel.cat +2 -5
@@ -25,7 +25,6 @@ include "lock.cat" (*******************) (* Fences *) -let rb-dep = [R] ; fencerel(Rb_dep) ; [R] let rmb = [R \ Noreturn] ; fencerel(Rmb) ; [R \ Noreturn] let wmb = [W] ; fencerel(Wmb) ; [W] let mb = ([M] ; fencerel(Mb) ; [M]) |
@@ -61,11 +60,9 @@ let dep = addr | data let rwdep = (dep | ctrl) ; [W] let overwrite = co | fr let to-w = rwdep | (overwrite & int) -let rrdep = addr | (dep ; rfi) -let strong-rrdep = rrdep+ & rb-dep -let to-r = strong-rrdep | rfi-rel-acq +let to-r = addr | (dep ; rfi) | rfi-rel-acq let fence = strong-fence | wmb | po-rel | rmb | acq-po -let ppo = rrdep* ; (to-r | to-w | fence) +let ppo = to-r | to-w | fence (* Propagation: Ordering from release operations and strong fences. *) let A-cumul(r) = rfe? ; r
tools/memory-model/linux-kernel.def +0 -2
@@ -13,14 +13,12 @@ WRITE_ONCE(X,V) { __store{once}(X,V); } smp_store_release(X,V) { __store{release}(*X,V); } smp_load_acquire(X) __load{acquire}(*X) rcu_assign_pointer(X,V) { __store{release}(X,V); } -lockless_dereference(X) __load{lderef}(X) rcu_dereference(X) __load{deref}(X) // Fences smp_mb() { __fence{mb} ; } smp_rmb() { __fence{rmb} ; } smp_wmb() { __fence{wmb} ; } -smp_read_barrier_depends() { __fence{rb_dep}; } smp_mb__before_atomic() { __fence{before-atomic} ; } smp_mb__after_atomic() { __fence{after-atomic} ; } smp_mb__after_spinlock() { __fence{after-spinlock} ; }
Signature · 1 line
2.5.2
RFC PATCH 8/12 memory-barriers: Fix description of data dependency barriers
In reply to Paul E. McKenneyFrom: Nikolay Borisov <[email protected]>
In the description of data dependency barriers the words 'before' is used erroneously. Since such barrier order dependent loads one after the other. So substitute 'before' with 'after'.
--- Documentation/memory-barriers.txt | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
Documentation/memory-barriers.txt +1 -1
@@ -400,7 +400,7 @@ Memory barriers come in four basic varieties: where two loads are performed such that the second depends on the result of the first (eg: the first load retrieves the address to which the second load will be directed), a data dependency barrier would be required to - make sure that the target of the second load is updated before the address + make sure that the target of the second load is updated after the address obtained by the first load is accessed. A data dependency barrier is a partial ordering on interdependent loads
Signature · 1 line
2.5.2
tip-bot for Andrea Parri
merge bot[tip:locking/core] tools/memory-model: Clarify the origin/scope of the tool name
In reply to Paul E. McKenneytools/memory-model: Clarify the origin/scope of the tool name
Commit-ID: 48d44d4e8a583c66d9f376e18c1a1fcc445f4b64 Gitweb: https://git.kernel.org/tip/48d44d4e8a583c66d9f376e18c1a1fcc445f4b64 Author: Andrea Parri <[email protected]> AuthorDate: Tue, 20 Feb 2018 15:25:01 -0800 Committer: Ingo Molnar <[email protected]> CommitDate: Wed, 21 Feb 2018 09:58:12 +0100
tools/memory-model: Clarify the origin/scope of the tool name
Ingo pointed out that:
"The "memory model" name is overly generic, ambiguous and somewhat
misleading, as we usually mean the virtual memory layout/model when we say "memory model". GCC too uses it in that sense [...]"
Make it clear that tools/memory-model/ uses the term "memory model" as shorthand for "memory consistency model" by calling out this convention in tools/memory-model/README.
Stick to the original "memory model" term in sources' headers and for the subsystem name.
--- tools/memory-model/MAINTAINERS | 2 +- tools/memory-model/README | 14 +++++++------- tools/memory-model/linux-kernel.bell | 2 +- tools/memory-model/linux-kernel.cat | 2 +- 4 files changed, 10 insertions(+), 10 deletions(-)
tools/memory-model/MAINTAINERS +1 -1
@@ -1,4 +1,4 @@ -LINUX KERNEL MEMORY MODEL +LINUX KERNEL MEMORY CONSISTENCY MODEL M: Alan Stern <[email protected]> M: Andrea Parri <[email protected]> M: Will Deacon <[email protected]>
tools/memory-model/README +7 -7
@@ -1,15 +1,15 @@ - ========================= - LINUX KERNEL MEMORY MODEL - ========================= + ===================================== + LINUX KERNEL MEMORY CONSISTENCY MODEL + ===================================== ============ INTRODUCTION ============ -This directory contains the memory model of the Linux kernel, written -in the "cat" language and executable by the (externally provided) -"herd7" simulator, which exhaustively explores the state space of -small litmus tests. +This directory contains the memory consistency model (memory model, for +short) of the Linux kernel, written in the "cat" language and executable +by the externally provided "herd7" simulator, which exhaustively explores +the state space of small litmus tests. In addition, the "klitmus7" tool (also externally provided) may be used to convert a litmus test to a Linux kernel module, which in turn allows
tools/memory-model/linux-kernel.bell +1 -1
@@ -11,7 +11,7 @@ * which is to appear in ASPLOS 2018. *) -"Linux kernel memory model" +"Linux-kernel memory consistency model" enum Accesses = 'once (*READ_ONCE,WRITE_ONCE,ACCESS_ONCE*) || 'release (*smp_store_release*) ||
tools/memory-model/linux-kernel.cat +1 -1
@@ -11,7 +11,7 @@ * which is to appear in ASPLOS 2018. *) -"Linux kernel memory model" +"Linux-kernel memory consistency model" (* * File "lock.cat" handles locks and is experimental.
tip-bot for Paul E. McKenney
merge bot[tip:locking/core] EXP litmus_tests: Add comments explaining tests' purposes
In reply to Paul E. McKenneyEXP litmus_tests: Add comments explaining tests' purposes
Commit-ID: 8f32543b61d7daeddb5b64c80b5ad5f05cc97722 Gitweb: https://git.kernel.org/tip/8f32543b61d7daeddb5b64c80b5ad5f05cc97722 Author: Paul E. McKenney <[email protected]> AuthorDate: Tue, 20 Feb 2018 15:25:04 -0800 Committer: Ingo Molnar <[email protected]> CommitDate: Wed, 21 Feb 2018 09:58:13 +0100
EXP litmus_tests: Add comments explaining tests' purposes
This commit adds comments to the litmus tests summarizing what these tests are intended to demonstrate.
--- .../memory-model/litmus-tests/CoRR+poonceonce+Once.litmus | 7 +++++++ .../memory-model/litmus-tests/CoRW+poonceonce+Once.litmus | 7 +++++++ .../memory-model/litmus-tests/CoWR+poonceonce+Once.litmus | 7 +++++++ tools/memory-model/litmus-tests/CoWW+poonceonce.litmus | 7 +++++++ .../litmus-tests/IRIW+mbonceonces+OnceOnce.litmus | 10 ++++++++++ .../litmus-tests/IRIW+poonceonces+OnceOnce.litmus | 10 ++++++++++ tools/memory-model/litmus-tests/ISA2+poonceonces.litmus | 9 +++++++++ ...SA2+pooncerelease+poacquirerelease+poacquireonce.litmus | 11 +++++++++++ .../litmus-tests/LB+ctrlonceonce+mbonceonce.litmus | 11 +++++++++++ .../litmus-tests/LB+poacquireonce+pooncerelease.litmus | 8 ++++++++ tools/memory-model/litmus-tests/LB+poonceonces.litmus | 7 +++++++ .../litmus-tests/MP+onceassign+derefonce.litmus | 11 ++++++++++- tools/memory-model/litmus-tests/MP+polocks.litmus | 11 +++++++++++ tools/memory-model/litmus-tests/MP+poonceonces.litmus | 7 +++++++ .../litmus-tests/MP+pooncerelease+poacquireonce.litmus | 8 ++++++++ tools/memory-model/litmus-tests/MP+porevlocks.litmus | 11 +++++++++++ .../litmus-tests/MP+wmbonceonce+rmbonceonce.litmus | 8 ++++++++ tools/memory-model/litmus-tests/R+mbonceonces.litmus | 9 +++++++++ tools/memory-model/litmus-tests/R+poonceonces.litmus | 8 ++++++++ tools/memory-model/litmus-tests/S+poonceonces.litmus | 9 +++++++++ .../litmus-tests/S+wmbonceonce+poacquireonce.litmus | 7 +++++++ tools/memory-model/litmus-tests/SB+mbonceonces.litmus | 9 +++++++++ tools/memory-model/litmus-tests/SB+poonceonces.litmus | 8 ++++++++ .../memory-model/litmus-tests/WRC+poonceonces+Once.litmus | 8 ++++++++ .../litmus-tests/WRC+pooncerelease+rmbonceonce+Once.litmus | 8 ++++++++ .../Z6.0+pooncelock+poonceLock+pombonce.litmus | 9 +++++++++ .../Z6.0+pooncelock+pooncelock+pombonce.litmus | 8 ++++++++ .../Z6.0+pooncerelease+poacquirerelease+mbonceonce.litmus | 14 ++++++++++++++ 28 files changed, 246 insertions(+), 1 deletion(-)
tools/memory-model/litmus-tests/CoRR+poonceonce+Once.litmus +7 -0
@@ -1,5 +1,12 @@ C CoRR+poonceonce+Once +(* + * Result: Never + * + * Test of read-read coherence, that is, whether or not two successive + * reads from the same variable are ordered. + *) + {} P0(int *x)
tools/memory-model/litmus-tests/CoRW+poonceonce+Once.litmus +7 -0
@@ -1,5 +1,12 @@ C CoRW+poonceonce+Once +(* + * Result: Never + * + * Test of read-write coherence, that is, whether or not a read from + * a given variable and a later write to that same variable are ordered. + *) + {} P0(int *x)
tools/memory-model/litmus-tests/CoWR+poonceonce+Once.litmus +7 -0
@@ -1,5 +1,12 @@ C CoWR+poonceonce+Once +(* + * Result: Never + * + * Test of write-read coherence, that is, whether or not a write to a + * given variable and a later read from that same variable are ordered. + *) + {} P0(int *x)
tools/memory-model/litmus-tests/CoWW+poonceonce.litmus +7 -0
@@ -1,5 +1,12 @@ C CoWW+poonceonce +(* + * Result: Never + * + * Test of write-write coherence, that is, whether or not two successive + * writes to the same variable are ordered. + *) + {} P0(int *x)
tools/memory-model/litmus-tests/IRIW+mbonceonces+OnceOnce.litmus +10 -0
@@ -1,5 +1,15 @@ C IRIW+mbonceonces+OnceOnce +(* + * Result: Never + * + * Test of independent reads from independent writes with smp_mb() + * between each pairs of reads. In other words, is smp_mb() sufficient to + * cause two different reading processes to agree on the order of a pair + * of writes, where each write is to a different variable by a different + * process? + *) + {} P0(int *x)
tools/memory-model/litmus-tests/IRIW+poonceonces+OnceOnce.litmus +10 -0
@@ -1,5 +1,15 @@ C IRIW+poonceonces+OnceOnce +(* + * Result: Sometimes + * + * Test of independent reads from independent writes with nothing + * between each pairs of reads. In other words, is anything at all + * needed to cause two different reading processes to agree on the order + * of a pair of writes, where each write is to a different variable by a + * different process? + *) + {} P0(int *x)
tools/memory-model/litmus-tests/ISA2+poonceonces.litmus +9 -0
@@ -1,5 +1,14 @@ C ISA2+poonceonces +(* + * Result: Sometimes + * + * Given a release-acquire chain ordering the first process's store + * against the last process's load, is ordering preserved if all of the + * smp_store_release() invocations are replaced by WRITE_ONCE() and all + * of the smp_load_acquire() invocations are replaced by READ_ONCE()? + *) + {} P0(int *x, int *y)
tools/memory-model/litmus-tests/ISA2+pooncerelease+poacquirerelease+poacquireonce.litmus +11 -0
@@ -1,5 +1,16 @@ C ISA2+pooncerelease+poacquirerelease+poacquireonce +(* + * Result: Never + * + * This litmus test demonstrates that a release-acquire chain suffices + * to order P0()'s initial write against P2()'s final read. The reason + * that the release-acquire chain suffices is because in all but one + * case (P2() to P0()), each process reads from the preceding process's + * write. In memory-model-speak, there is only one non-reads-from + * (AKA non-rf) link, so release-acquire is all that is needed. + *) + {} P0(int *x, int *y)
tools/memory-model/litmus-tests/LB+ctrlonceonce+mbonceonce.litmus +11 -0
@@ -1,5 +1,16 @@ C LB+ctrlonceonce+mbonceonce +(* + * Result: Never + * + * This litmus test demonstrates that lightweight ordering suffices for + * the load-buffering pattern, in other words, preventing all processes + * reading from the preceding process's write. In this example, the + * combination of a control dependency and a full memory barrier are enough + * to do the trick. (But the full memory barrier could be replaced with + * another control dependency and order would still be maintained.) + *) + {} P0(int *x, int *y)
tools/memory-model/litmus-tests/LB+poacquireonce+pooncerelease.litmus +8 -0
@@ -1,5 +1,13 @@ C LB+poacquireonce+pooncerelease +(* + * Result: Never + * + * Does a release-acquire pair suffice for the load-buffering litmus + * test, where each process reads from one of two variables then writes + * to the other? + *) + {} P0(int *x, int *y)
tools/memory-model/litmus-tests/LB+poonceonces.litmus +7 -0
@@ -1,5 +1,12 @@ C LB+poonceonces +(* + * Result: Sometimes + * + * Can the counter-intuitive outcome for the load-buffering pattern + * be prevented even with no explicit ordering? + *) + {} P0(int *x, int *y)
tools/memory-model/litmus-tests/MP+onceassign+derefonce.litmus +10 -1
@@ -1,4 +1,13 @@ -C MP+onceassign+derefonce.litmus +C MP+onceassign+derefonce + +(* + * Result: Never + * + * This litmus test demonstrates that rcu_assign_pointer() and + * rcu_dereference() suffice to ensure that an RCU reader will not see + * pre-initialization garbage when it traverses an RCU-protected data + * structure containing a newly inserted element. + *) { y=z;
tools/memory-model/litmus-tests/MP+polocks.litmus +11 -0
@@ -1,5 +1,16 @@ C MP+polocks +(* + * Result: Never + * + * This litmus test demonstrates how lock acquisitions and releases can + * stand in for smp_load_acquire() and smp_store_release(), respectively. + * In other words, when holding a given lock (or indeed after releasing a + * given lock), a CPU is not only guaranteed to see the accesses that other + * CPUs made while previously holding that lock, it is also guaranteed + * to see all prior accesses by those other CPUs. + *) + {} P0(int *x, int *y, spinlock_t *mylock)
tools/memory-model/litmus-tests/MP+poonceonces.litmus +7 -0
@@ -1,5 +1,12 @@ C MP+poonceonces +(* + * Result: Maybe + * + * Can the counter-intuitive message-passing outcome be prevented with + * no ordering at all? + *) + {} P0(int *x, int *y)
tools/memory-model/litmus-tests/MP+pooncerelease+poacquireonce.litmus +8 -0
@@ -1,5 +1,13 @@ C MP+pooncerelease+poacquireonce +(* + * Result: Never + * + * This litmus test demonstrates that smp_store_release() and + * smp_load_acquire() provide sufficient ordering for the message-passing + * pattern. + *) + {} P0(int *x, int *y)
tools/memory-model/litmus-tests/MP+porevlocks.litmus +11 -0
@@ -1,5 +1,16 @@ C MP+porevlocks +(* + * Result: Never + * + * This litmus test demonstrates how lock acquisitions and releases can + * stand in for smp_load_acquire() and smp_store_release(), respectively. + * In other words, when holding a given lock (or indeed after releasing a + * given lock), a CPU is not only guaranteed to see the accesses that other + * CPUs made while previously holding that lock, it is also guaranteed to + * see all prior accesses by those other CPUs. + *) + {} P0(int *x, int *y, spinlock_t *mylock)
tools/memory-model/litmus-tests/MP+wmbonceonce+rmbonceonce.litmus +8 -0
@@ -1,5 +1,13 @@ C MP+wmbonceonce+rmbonceonce +(* + * Result: Never + * + * This litmus test demonstrates that smp_wmb() and smp_rmb() provide + * sufficient ordering for the message-passing pattern. However, it + * is usually better to use smp_store_release() and smp_load_acquire(). + *) + {} P0(int *x, int *y)
tools/memory-model/litmus-tests/R+mbonceonces.litmus +9 -0
@@ -1,5 +1,14 @@ C R+mbonceonces +(* + * Result: Never + * + * This is the fully ordered (via smp_mb()) version of one of the classic + * counterintuitive litmus tests that illustrates the effects of store + * propagation delays. Note that weakening either of the barriers would + * cause the resulting test to be allowed. + *) + {} P0(int *x, int *y)
tools/memory-model/litmus-tests/R+poonceonces.litmus +8 -0
@@ -1,5 +1,13 @@ C R+poonceonces +(* + * Result: Sometimes + * + * This is the unordered (thus lacking smp_mb()) version of one of the + * classic counterintuitive litmus tests that illustrates the effects of + * store propagation delays. + *) + {} P0(int *x, int *y)
tools/memory-model/litmus-tests/S+poonceonces.litmus +9 -0
@@ -1,5 +1,14 @@ C S+poonceonces +(* + * Result: Sometimes + * + * Starting with a two-process release-acquire chain ordering P0()'s + * first store against P1()'s final load, if the smp_store_release() + * is replaced by WRITE_ONCE() and the smp_load_acquire() replaced by + * READ_ONCE(), is ordering preserved? + *) + {} P0(int *x, int *y)
tools/memory-model/litmus-tests/S+wmbonceonce+poacquireonce.litmus +7 -0
@@ -1,5 +1,12 @@ C S+wmbonceonce+poacquireonce +(* + * Result: Never + * + * Can a smp_wmb(), instead of a release, and an acquire order a prior + * store against a subsequent store? + *) + {} P0(int *x, int *y)
tools/memory-model/litmus-tests/SB+mbonceonces.litmus +9 -0
@@ -1,5 +1,14 @@ C SB+mbonceonces +(* + * Result: Never + * + * This litmus test demonstrates that full memory barriers suffice to + * order the store-buffering pattern, where each process writes to the + * variable that the preceding process reads. (Locking and RCU can also + * suffice, but not much else.) + *) + {} P0(int *x, int *y)
tools/memory-model/litmus-tests/SB+poonceonces.litmus +8 -0
@@ -1,5 +1,13 @@ C SB+poonceonces +(* + * Result: Sometimes + * + * This litmus test demonstrates that at least some ordering is required + * to order the store-buffering pattern, where each process writes to the + * variable that the preceding process reads. + *) + {} P0(int *x, int *y)
tools/memory-model/litmus-tests/WRC+poonceonces+Once.litmus +8 -0
@@ -1,5 +1,13 @@ C WRC+poonceonces+Once +(* + * Result: Sometimes + * + * This litmus test is an extension of the message-passing pattern, + * where the first write is moved to a separate process. Note that this + * test has no ordering at all. + *) + {} P0(int *x)
tools/memory-model/litmus-tests/WRC+pooncerelease+rmbonceonce+Once.litmus +8 -0
@@ -1,5 +1,13 @@ C WRC+pooncerelease+rmbonceonce+Once +(* + * Result: Never + * + * This litmus test is an extension of the message-passing pattern, where + * the first write is moved to a separate process. Because it features + * a release and a read memory barrier, it should be forbidden. + *) + {} P0(int *x)
tools/memory-model/litmus-tests/Z6.0+pooncelock+poonceLock+pombonce.litmus +9 -0
@@ -1,5 +1,14 @@ C Z6.0+pooncelock+poonceLock+pombonce +(* + * Result: Never + * + * This litmus test demonstrates how smp_mb__after_spinlock() may be + * used to ensure that accesses in different critical sections for a + * given lock running on different CPUs are nevertheless seen in order + * by CPUs not holding that lock. + *) + {} P0(int *x, int *y, spinlock_t *mylock)
tools/memory-model/litmus-tests/Z6.0+pooncelock+pooncelock+pombonce.litmus +8 -0
@@ -1,5 +1,13 @@ C Z6.0+pooncelock+pooncelock+pombonce +(* + * Result: Sometimes + * + * This example demonstrates that a pair of accesses made by different + * processes each while holding a given lock will not necessarily be + * seen as ordered by a third process not holding that lock. + *) + {} P0(int *x, int *y, spinlock_t *mylock)
tools/memory-model/litmus-tests/Z6.0+pooncerelease+poacquirerelease+mbonceonce.litmus +14 -0
@@ -1,5 +1,19 @@ C Z6.0+pooncerelease+poacquirerelease+mbonceonce +(* + * Result: Sometimes + * + * This litmus test shows that a release-acquire chain, while sufficient + * when there is but one non-reads-from (AKA non-rf) link, does not suffice + * if there is more than one. Of the three processes, only P1() reads from + * P0's write, which means that there are two non-rf links: P1() to P2() + * is a write-to-write link (AKA a "coherence" or just "co" link) and P2() + * to P0() is a read-to-write link (AKA a "from-reads" or just "fr" link). + * When there are two or more non-rf links, you typically will need one + * full barrier for each non-rf link. (Exceptions include some cases + * involving locking.) + *) + {} P0(int *x, int *y)
tip-bot for Andrea Parri
merge bot[tip:locking/core] MAINTAINERS: Add the Memory Consistency Model subsystem
In reply to Paul E. McKenneyMAINTAINERS: Add the Memory Consistency Model subsystem
Commit-ID: e7d74c9f900a12ea0bd5cabb3be142441530e24e Gitweb: https://git.kernel.org/tip/e7d74c9f900a12ea0bd5cabb3be142441530e24e Author: Andrea Parri <[email protected]> AuthorDate: Tue, 20 Feb 2018 15:25:02 -0800 Committer: Ingo Molnar <[email protected]> CommitDate: Wed, 21 Feb 2018 09:58:12 +0100
MAINTAINERS: Add the Memory Consistency Model subsystem
Move the contents of tools/memory-model/MAINTAINERS into the main MAINTAINERS file, removing tools/memory-model/MAINTAINERS. This allows get_maintainer.pl to correctly identify the maintainers of tools/memory-model/.
--- MAINTAINERS | 16 ++++++++++++++++ tools/memory-model/MAINTAINERS | 15 --------------- 2 files changed, 16 insertions(+), 15 deletions(-)
MAINTAINERS +16 -0
@@ -8148,6 +8148,22 @@ M: Kees Cook <[email protected]> S: Maintained F: drivers/misc/lkdtm* +LINUX KERNEL MEMORY CONSISTENCY MODEL (LKMM) +M: Alan Stern <[email protected]> +M: Andrea Parri <[email protected]> +M: Will Deacon <[email protected]> +M: Peter Zijlstra <[email protected]> +M: Boqun Feng <[email protected]> +M: Nicholas Piggin <[email protected]> +M: David Howells <[email protected]> +M: Jade Alglave <[email protected]> +M: Luc Maranget <[email protected]> +M: "Paul E. McKenney" <[email protected]> +L: [email protected] +S: Supported +T: git git://git.kernel.org/pub/scm/linux/kernel/git/paulmck/linux-rcu.git +F: tools/memory-model/ + LINUX SECURITY MODULE (LSM) FRAMEWORK M: Chris Wright <[email protected]> L: [email protected]
tools/memory-model/MAINTAINERS deleted +0 -15
@@ -1,15 +0,0 @@ -LINUX KERNEL MEMORY CONSISTENCY MODEL -M: Alan Stern <[email protected]> -M: Andrea Parri <[email protected]> -M: Will Deacon <[email protected]> -M: Peter Zijlstra <[email protected]> -M: Boqun Feng <[email protected]> -M: Nicholas Piggin <[email protected]> -M: David Howells <[email protected]> -M: Jade Alglave <[email protected]> -M: Luc Maranget <[email protected]> -M: "Paul E. McKenney" <[email protected]> -L: [email protected] -S: Supported -T: git git://git.kernel.org/pub/scm/linux/kernel/git/paulmck/linux-rcu.git -F: tools/memory-model/
tip-bot for Andrea Parri
merge bot[tip:locking/core] MAINTAINERS: List file memory-barriers.txt within the LKMM entry
In reply to Paul E. McKenneyMAINTAINERS: List file memory-barriers.txt within the LKMM entry
Commit-ID: ea52d698c1ed0c4555656de0dd1f7ac5866f89e1 Gitweb: https://git.kernel.org/tip/ea52d698c1ed0c4555656de0dd1f7ac5866f89e1 Author: Andrea Parri <[email protected]> AuthorDate: Tue, 20 Feb 2018 15:25:03 -0800 Committer: Ingo Molnar <[email protected]> CommitDate: Wed, 21 Feb 2018 09:58:13 +0100
MAINTAINERS: List file memory-barriers.txt within the LKMM entry
We now have a shiny new Linux-kernel memory model (LKMM) and the old tried-and-true Documentation/memory-barrier.txt. It would be good to keep these automatically synchronized, but in the meantime we need at least let people know that they are related. Will suggested adding the Documentation/memory-barrier.txt file to the LKMM maintainership list, thus making the LKMM maintainers responsible for both the old and the new. This commit follows Will's excellent suggestion.
--- MAINTAINERS | 1 + 1 file changed, 1 insertion(+)
MAINTAINERS +1 -0
@@ -8163,6 +8163,7 @@ L: [email protected] S: Supported T: git git://git.kernel.org/pub/scm/linux/kernel/git/paulmck/linux-rcu.git F: tools/memory-model/ +F: Documentation/memory-barriers.txt LINUX SECURITY MODULE (LSM) FRAMEWORK M: Chris Wright <[email protected]>
tip-bot for Paul E. McKenney
merge bot[tip:locking/core] README: Fix a couple of punctuation errors
In reply to Paul E. McKenneyREADME: Fix a couple of punctuation errors
Commit-ID: 62155147048f6c811b82cbb53bee246aee083774 Gitweb: https://git.kernel.org/tip/62155147048f6c811b82cbb53bee246aee083774 Author: Paul E. McKenney <[email protected]> AuthorDate: Tue, 20 Feb 2018 15:25:05 -0800 Committer: Ingo Molnar <[email protected]> CommitDate: Wed, 21 Feb 2018 09:58:14 +0100
README: Fix a couple of punctuation errors
--- tools/memory-model/litmus-tests/README | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
tools/memory-model/litmus-tests/README +2 -2
@@ -23,14 +23,14 @@ IRIW+mbonceonces+OnceOnce.litmus between each pairs of reads. In other words, is smp_mb() sufficient to cause two different reading processes to agree on the order of a pair of writes, where each write is to a different - variable by a different process. + variable by a different process? IRIW+poonceonces+OnceOnce.litmus Test of independent reads from independent writes with nothing between each pairs of reads. In other words, is anything at all needed to cause two different reading processes to agree on the order of a pair of writes, where each write is to a different - variable by a different process. + variable by a different process? ISA2+poonceonces.litmus As below, but with store-release replaced with WRITE_ONCE()
tip-bot for Paul E. McKenney
merge bot[tip:locking/core] MAINTAINERS: Add Akira Yokosawa as an LKMM reviewer
In reply to Paul E. McKenneyMAINTAINERS: Add Akira Yokosawa as an LKMM reviewer
Commit-ID: 65b65f8e8b941785b0a08cf24ffd7084c8df327c Gitweb: https://git.kernel.org/tip/65b65f8e8b941785b0a08cf24ffd7084c8df327c Author: Paul E. McKenney <[email protected]> AuthorDate: Tue, 20 Feb 2018 15:25:06 -0800 Committer: Ingo Molnar <[email protected]> CommitDate: Wed, 21 Feb 2018 09:58:14 +0100
MAINTAINERS: Add Akira Yokosawa as an LKMM reviewer
--- MAINTAINERS | 1 + 1 file changed, 1 insertion(+)
MAINTAINERS +1 -0
@@ -8159,6 +8159,7 @@ M: David Howells <[email protected]> M: Jade Alglave <[email protected]> M: Luc Maranget <[email protected]> M: "Paul E. McKenney" <[email protected]> +R: Akira Yokosawa <[email protected]> L: [email protected] S: Supported T: git git://git.kernel.org/pub/scm/linux/kernel/git/paulmck/linux-rcu.git
tip-bot for Andrea Parri
merge bot[tip:locking/core] Documentation/memory-barriers.txt: Cross-reference "tools/memory-model/"
In reply to Paul E. McKenneyDocumentation/memory-barriers.txt: Cross-reference "tools/memory-model/"
Commit-ID: 621df431b0ac931e318679f54047c47eb23cfdd2 Gitweb: https://git.kernel.org/tip/621df431b0ac931e318679f54047c47eb23cfdd2 Author: Andrea Parri <[email protected]> AuthorDate: Tue, 20 Feb 2018 15:25:07 -0800 Committer: Ingo Molnar <[email protected]> CommitDate: Wed, 21 Feb 2018 09:58:14 +0100
Documentation/memory-barriers.txt: Cross-reference "tools/memory-model/"
A memory consistency model is now available for the Linux kernel [1], which "can (roughly speaking) be thought of as an automated version of memory-barriers.txt" and which is (in turn) "accompanied by extensive documentation on its use and its design".
Inform the (occasional) reader of memory-barriers.txt of these developments.
[1] https://marc.info/?l=linux-kernel&m=151687290114799&w=2
--- Documentation/memory-barriers.txt | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-)
Documentation/memory-barriers.txt +5 -1
@@ -14,7 +14,11 @@ DISCLAIMER This document is not a specification; it is intentionally (for the sake of brevity) and unintentionally (due to being human) incomplete. This document is meant as a guide to using the various memory barriers provided by Linux, but -in case of any doubt (and there are many) please ask. +in case of any doubt (and there are many) please ask. Some doubts may be +resolved by referring to the formal memory consistency model and related +documentation at tools/memory-model/. Nevertheless, even this memory +model should be viewed as the collective opinion of its maintainers rather +than as an infallible oracle. To repeat, this document is not a specification of what Linux expects from hardware.
tip-bot for Nikolay Borisov
merge bot[tip:locking/core] memory-barriers: Fix description of data dependency barriers
In reply to Paul E. McKenneymemory-barriers: Fix description of data dependency barriers
Commit-ID: 51de78892b1294d1521c41226a5ef215a910c25f Gitweb: https://git.kernel.org/tip/51de78892b1294d1521c41226a5ef215a910c25f Author: Nikolay Borisov <[email protected]> AuthorDate: Tue, 20 Feb 2018 15:25:08 -0800 Committer: Ingo Molnar <[email protected]> CommitDate: Wed, 21 Feb 2018 09:58:14 +0100
memory-barriers: Fix description of data dependency barriers
In the description of data dependency barriers the words 'before' is used erroneously. Since such barrier order dependent loads one after the other. So substitute 'before' with 'after'.
--- Documentation/memory-barriers.txt | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
Documentation/memory-barriers.txt +1 -1
@@ -403,7 +403,7 @@ Memory barriers come in four basic varieties: where two loads are performed such that the second depends on the result of the first (eg: the first load retrieves the address to which the second load will be directed), a data dependency barrier would be required to - make sure that the target of the second load is updated before the address + make sure that the target of the second load is updated after the address obtained by the first load is accessed. A data dependency barrier is a partial ordering on interdependent loads
tip-bot for Paul E. McKenney
merge bot[tip:locking/core] tools/memory-model: Add required herd7 version to README file
In reply to Paul E. McKenneytools/memory-model: Add required herd7 version to README file
Commit-ID: 8f7f2fbd00898deaf01e05a00095411811befd64 Gitweb: https://git.kernel.org/tip/8f7f2fbd00898deaf01e05a00095411811befd64 Author: Paul E. McKenney <[email protected]> AuthorDate: Tue, 20 Feb 2018 15:25:09 -0800 Committer: Ingo Molnar <[email protected]> CommitDate: Wed, 21 Feb 2018 09:58:15 +0100
tools/memory-model: Add required herd7 version to README file
LKMM and the herd7 tool are co-evolving, and out-of-date herd7 tools produce inaccurate results, often with no obvious error messages. This commit therefore adds the required herd7 version to the LKMM README file.
Longer term, it would be good if .cat files could specify the required version in a manner allowing herd7 to produce clear diagnostics.
--- tools/memory-model/README | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)
tools/memory-model/README +2 -1
@@ -20,7 +20,8 @@ that litmus test to be exercised within the Linux kernel. REQUIREMENTS ============ -The "herd7" and "klitmus7" tools must be downloaded separately: +Version 7.48 of the "herd7" and "klitmus7" tools must be downloaded +separately: https://github.com/herd/herdtools7
tip-bot for Alan Stern
merge bot[tip:locking/core] tools/memory-model: Add a S lock-based external-view litmus test
In reply to Paul E. McKenneytools/memory-model: Add a S lock-based external-view litmus test
Commit-ID: 556bb7d252ae42d4653557325670e665087c38ad Gitweb: https://git.kernel.org/tip/556bb7d252ae42d4653557325670e665087c38ad Author: Alan Stern <[email protected]> AuthorDate: Tue, 20 Feb 2018 15:25:10 -0800 Committer: Ingo Molnar <[email protected]> CommitDate: Wed, 21 Feb 2018 09:58:15 +0100
tools/memory-model: Add a S lock-based external-view litmus test
This commit adds a litmus test in which P0() and P1() form a lock-based S litmus test, with the addition of P2(), which observes P0()'s and P1()'s accesses with a full memory barrier but without the lock. This litmus test asks whether writes carried out by two different processes under the same lock will be seen in order by a third process not holding that lock. The answer to this question is "yes" for all architectures supporting the Linux kernel, but is "no" according to the current version of LKMM.
A patch to LKMM is under development.
--- ...ce.litmus => ISA2+pooncelock+pooncelock+pombonce.litmus} | 13 +++++++------ 1 file changed, 7 insertions(+), 6 deletions(-)
tools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmus renamed from tools/memory-model/litmus-tests/Z6.0+pooncelock+pooncelock+pombonce.litmus +7 -6
@@ -1,11 +1,11 @@ -C Z6.0+pooncelock+pooncelock+pombonce +C ISA2+pooncelock+pooncelock+pombonce.litmus (* * Result: Sometimes * - * This example demonstrates that a pair of accesses made by different - * processes each while holding a given lock will not necessarily be - * seen as ordered by a third process not holding that lock. + * This test shows that the ordering provided by a lock-protected S + * litmus test (P0() and P1()) are not visible to external process P2(). + * This is likely to change soon. *) {}
@@ -31,10 +31,11 @@ P1(int *y, int *z, spinlock_t *mylock) P2(int *x, int *z) { int r1; + int r2; - WRITE_ONCE(*z, 2); + r2 = READ_ONCE(*z); smp_mb(); r1 = READ_ONCE(*x); } -exists (1:r0=1 /\ z=2 /\ 2:r1=0) +exists (1:r0=1 /\ 2:r2=1 /\ 2:r1=0)
tip-bot for Paul E. McKenney
merge bot[tip:locking/core] tools/memory-model: Convert underscores to hyphens
In reply to Paul E. McKenneytools/memory-model: Convert underscores to hyphens
Commit-ID: cac79a39f200ef73ae7fc8a429ce2859ebb118d9 Gitweb: https://git.kernel.org/tip/cac79a39f200ef73ae7fc8a429ce2859ebb118d9 Author: Paul E. McKenney <[email protected]> AuthorDate: Tue, 20 Feb 2018 15:25:11 -0800 Committer: Ingo Molnar <[email protected]> CommitDate: Wed, 21 Feb 2018 09:58:15 +0100
tools/memory-model: Convert underscores to hyphens
Typical cat-language code uses hyphens for word separators in identifiers, but several LKMM identifiers use underscores instead. This commit therefore converts underscores to hyphens in the .bell- and .cat-file identifiers corresponding to smp_mb__before_atomic(), smp_mb__after_atomic(), and smp_mb__after_spinlock().
--- tools/memory-model/linux-kernel.bell | 6 +++--- tools/memory-model/linux-kernel.cat | 6 +++--- tools/memory-model/linux-kernel.def | 6 +++--- 3 files changed, 9 insertions(+), 9 deletions(-)
tools/memory-model/linux-kernel.bell +3 -3
@@ -28,9 +28,9 @@ enum Barriers = 'wmb (*smp_wmb*) || 'rcu-lock (*rcu_read_lock*) || 'rcu-unlock (*rcu_read_unlock*) || 'sync-rcu (*synchronize_rcu*) || - 'before_atomic (*smp_mb__before_atomic*) || - 'after_atomic (*smp_mb__after_atomic*) || - 'after_spinlock (*smp_mb__after_spinlock*) + 'before-atomic (*smp_mb__before_atomic*) || + 'after-atomic (*smp_mb__after_atomic*) || + 'after-spinlock (*smp_mb__after_spinlock*) instructions F[Barriers] (* Compute matching pairs of nested Rcu-lock and Rcu-unlock *)
tools/memory-model/linux-kernel.cat +3 -3
@@ -29,9 +29,9 @@ let rb-dep = [R] ; fencerel(Rb_dep) ; [R] let rmb = [R \ Noreturn] ; fencerel(Rmb) ; [R \ Noreturn] let wmb = [W] ; fencerel(Wmb) ; [W] let mb = ([M] ; fencerel(Mb) ; [M]) | - ([M] ; fencerel(Before_atomic) ; [RMW] ; po? ; [M]) | - ([M] ; po? ; [RMW] ; fencerel(After_atomic) ; [M]) | - ([M] ; po? ; [LKW] ; fencerel(After_spinlock) ; [M]) + ([M] ; fencerel(Before-atomic) ; [RMW] ; po? ; [M]) | + ([M] ; po? ; [RMW] ; fencerel(After-atomic) ; [M]) | + ([M] ; po? ; [LKW] ; fencerel(After-spinlock) ; [M]) let gp = po ; [Sync-rcu] ; po? let strong-fence = mb | gp
tools/memory-model/linux-kernel.def +3 -3
@@ -21,9 +21,9 @@ smp_mb() { __fence{mb} ; } smp_rmb() { __fence{rmb} ; } smp_wmb() { __fence{wmb} ; } smp_read_barrier_depends() { __fence{rb_dep}; } -smp_mb__before_atomic() { __fence{before_atomic} ; } -smp_mb__after_atomic() { __fence{after_atomic} ; } -smp_mb__after_spinlock() { __fence{after_spinlock} ; } +smp_mb__before_atomic() { __fence{before-atomic} ; } +smp_mb__after_atomic() { __fence{after-atomic} ; } +smp_mb__after_spinlock() { __fence{after-spinlock} ; } // Exchange xchg(X,V) __xchg{mb}(X,V)
tip-bot for Alan Stern
merge bot[tip:locking/core] tools/memory-model: Remove rb-dep, smp_read_barrier_depends, and lockless_dereference
In reply to Paul E. McKenneytools/memory-model: Remove rb-dep, smp_read_barrier_depends, and lockless_dereference
Commit-ID: bf28ae5627442355dbb8d99238da4fb95c2dd4ec Gitweb: https://git.kernel.org/tip/bf28ae5627442355dbb8d99238da4fb95c2dd4ec Author: Alan Stern <[email protected]> AuthorDate: Tue, 20 Feb 2018 15:25:12 -0800 Committer: Ingo Molnar <[email protected]> CommitDate: Wed, 21 Feb 2018 09:58:16 +0100
tools/memory-model: Remove rb-dep, smp_read_barrier_depends, and lockless_dereference
Since commit 76ebbe78f739 ("locking/barriers: Add implicit smp_read_barrier_depends() to READ_ONCE()") was merged for the 4.15 kernel, it has not been necessary to use smp_read_barrier_depends(). Similarly, commit 59ecbbe7b31c ("locking/barriers: Kill lockless_dereference()") removed lockless_dereference() from the kernel.
Since these primitives are no longer part of the kernel, they do not belong in the Linux Kernel Memory Consistency Model. This patch removes them, along with the internal rb-dep relation, and updates the revelant documentation.
--- tools/memory-model/Documentation/cheatsheet.txt | 3 +- tools/memory-model/Documentation/explanation.txt | 81 +++++++++++++----------- tools/memory-model/linux-kernel.bell | 1 - tools/memory-model/linux-kernel.cat | 7 +- tools/memory-model/linux-kernel.def | 2 - 5 files changed, 46 insertions(+), 48 deletions(-)
tools/memory-model/Documentation/cheatsheet.txt +1 -2
@@ -6,8 +6,7 @@ Store, e.g., WRITE_ONCE() Y Y Load, e.g., READ_ONCE() Y Y Y Unsuccessful RMW operation Y Y Y -smp_read_barrier_depends() Y Y Y -*_dereference() Y Y Y Y +rcu_dereference() Y Y Y Y Successful *_acquire() R Y Y Y Y Y Y Successful *_release() C Y Y Y W Y smp_rmb() Y R Y Y R
tools/memory-model/Documentation/explanation.txt +43 -38
144 lines not on this page · raw message
tools/memory-model/linux-kernel.bell +0 -1
@@ -24,7 +24,6 @@ instructions RMW[{'once,'acquire,'release}] enum Barriers = 'wmb (*smp_wmb*) || 'rmb (*smp_rmb*) || 'mb (*smp_mb*) || - 'rb_dep (*smp_read_barrier_depends*) || 'rcu-lock (*rcu_read_lock*) || 'rcu-unlock (*rcu_read_unlock*) || 'sync-rcu (*synchronize_rcu*) ||
tools/memory-model/linux-kernel.cat +2 -5
@@ -25,7 +25,6 @@ include "lock.cat" (*******************) (* Fences *) -let rb-dep = [R] ; fencerel(Rb_dep) ; [R] let rmb = [R \ Noreturn] ; fencerel(Rmb) ; [R \ Noreturn] let wmb = [W] ; fencerel(Wmb) ; [W] let mb = ([M] ; fencerel(Mb) ; [M]) |
@@ -61,11 +60,9 @@ let dep = addr | data let rwdep = (dep | ctrl) ; [W] let overwrite = co | fr let to-w = rwdep | (overwrite & int) -let rrdep = addr | (dep ; rfi) -let strong-rrdep = rrdep+ & rb-dep -let to-r = strong-rrdep | rfi-rel-acq +let to-r = addr | (dep ; rfi) | rfi-rel-acq let fence = strong-fence | wmb | po-rel | rmb | acq-po -let ppo = rrdep* ; (to-r | to-w | fence) +let ppo = to-r | to-w | fence (* Propagation: Ordering from release operations and strong fences. *) let A-cumul(r) = rfe? ; r
tools/memory-model/linux-kernel.def +0 -2
@@ -13,14 +13,12 @@ WRITE_ONCE(X,V) { __store{once}(X,V); } smp_store_release(X,V) { __store{release}(*X,V); } smp_load_acquire(X) __load{acquire}(*X) rcu_assign_pointer(X,V) { __store{release}(X,V); } -lockless_dereference(X) __load{lderef}(X) rcu_dereference(X) __load{deref}(X) // Fences smp_mb() { __fence{mb} ; } smp_rmb() { __fence{rmb} ; } smp_wmb() { __fence{wmb} ; } -smp_read_barrier_depends() { __fence{rb_dep}; } smp_mb__before_atomic() { __fence{before-atomic} ; } smp_mb__after_atomic() { __fence{after-atomic} ; } smp_mb__after_spinlock() { __fence{after-spinlock} ; }
Alan Stern
maintainerRe: [PATCH RFC tools/lkmm 10/12] tools/memory-model: Add a S lock-based external-view litmus test
In reply to Paul E. McKenneyQuoted 4 lines · Paul E. McKenney
From: Alan Stern <[email protected]>
This commit adds a litmus test in which
P0()andP1()form a lock-based S litmus test, with the addition ofP2(), which observes P0()'s and P1()'s
Why do you call this an "S" litmus test? Isn't ISA2 a better description?
Quoted 6 lines
accesses with a full memory barrier but without the lock. This litmus test asks whether writes carried out by two different processes under the same lock will be seen in order by a third process not holding that lock. The answer to this question is "yes" for all architectures supporting the Linux kernel, but is "no" according to the current version of LKMM.
Quoted 8 lines
A patch to LKMM is under development.
Signed-off-by Alan Stern <[email protected]>Signed-off-by Paul E. McKenney <[email protected]>--- .../ISA2+pooncelock+pooncelock+pombonce.litmus | 41 ++++++++++++++++++++++ 1 file changed, 41 insertions(+) create mode 100644 tools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmus
Aren't these tests supposed to be described in litmus-tests/README?
Quoted 6 lines
tools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmus new file +0
-0
tools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmus line 8
Quoted 8 lines
tools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmus new file +8
-0@@ -0,0 +1,41 @@ +C ISA2+pooncelock+pooncelock+pombonce.litmus + +(* + * Result: Sometimes + * + * This test shows that the ordering provided by a lock-protected S + * litmus test (P0() and P1()) are not visible to external process P2(). + * This is likely to change soon.
That last line may be premature. We haven't reached any consensus on how RISC-V will handle this. If RISC-V allows the test then the memory model can't forbid it.
Alan
Quoted 34 lines
tools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmus new file +33
-0+ *) + +{} + +P0(int *x, int *y, spinlock_t *mylock) +{ + spin_lock(mylock); + WRITE_ONCE(*x, 1); + WRITE_ONCE(*y, 1); + spin_unlock(mylock); +} + +P1(int *y, int *z, spinlock_t *mylock) +{ + int r0; + + spin_lock(mylock); + r0 = READ_ONCE(*y); + WRITE_ONCE(*z, 1); + spin_unlock(mylock); +} + +P2(int *x, int *z) +{ + int r1; + int r2; + + r2 = READ_ONCE(*z); + smp_mb(); + r1 = READ_ONCE(*x); +} + +exists (1:r0=1 /\ 2:r2=1 /\ 2:r1=0)
Alan Stern
maintainerRe: [PATCH RFC tools/lkmm 09/12] tools/memory-model: Add required herd7 version to README file
In reply to Paul E. McKenneyQuoted 18 lines · Paul E. McKenney
LKMM and the herd7 tool are co-evolving, and out-of-date herd7 tools produce inaccurate results, often with no obvious error messages. This commit therefore adds the required herd7 version to the LKMM README file.
Longer term, it would be good if .cat files could specify the required version in a manner allowing herd7 to produce clear diagnostics.
Suggested-by Akira Yokosawa <[email protected]>Signed-off-by Paul E. McKenney <[email protected]>--- tools/memory-model/README | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)tools/memory-model/README +0
-0
tools/memory-model/README that litmus test to be exercised within the Linux kernel. · line 26
Quoted 8 lines
tools/memory-model/README +2
-1@@ -20,7 +20,8 @@ that litmus test to be exercised within the Linux kernel. REQUIREMENTS ============ -The "herd7" and "klitmus7" tools must be downloaded separately: +Version 7.48 of the "herd7" and "klitmus7" tools must be downloaded +separately: https://github.com/herd/herdtools7
The text immediately below this mentions the Docker image and gentoo package. Aren't they both seriously out of date at this point? In which case, shouldn't we remove them from the README?
Alan
Re: [PATCH RFC tools/lkmm 10/12] tools/memory-model: Add a S lock-based external-view litmus test
In reply to Alan SternQuoted 9 lines · Alan Stern
Quoted 4 lines · Paul E. McKenney
From: Alan Stern <[email protected]>
This commit adds a litmus test in which
P0()andP1()form a lock-based S litmus test, with the addition ofP2(), which observes P0()'s and P1()'sWhy do you call this an "S" litmus test? Isn't ISA2 a better description?
Indeed, the name of the test is in fact ISA2.
Quoted 27 lines
Quoted 6 lines
accesses with a full memory barrier but without the lock. This litmus test asks whether writes carried out by two different processes under the same lock will be seen in order by a third process not holding that lock. The answer to this question is "yes" for all architectures supporting the Linux kernel, but is "no" according to the current version of LKMM.
Quoted 8 lines
A patch to LKMM is under development.
Signed-off-by Alan Stern <[email protected]>Signed-off-by Paul E. McKenney <[email protected]>--- .../ISA2+pooncelock+pooncelock+pombonce.litmus | 41 ++++++++++++++++++++++ 1 file changed, 41 insertions(+) create mode 100644 tools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmusAren't these tests supposed to be described in litmus-tests/README?
Quoted 10 lines
tools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmus new file +4
-0@@ -0,0 +1,41 @@ +C ISA2+pooncelock+pooncelock+pombonce.litmus + +(* + * Result: Sometimes
Quoted 8 lines
tools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmus line 8
Quoted 4 lines
tools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmus new file +4
-0+ * + * This test shows that the ordering provided by a lock-protected S + * litmus test (P0() and P1()) are not visible to external process P2(). + * This is likely to change soon.That last line may be premature. We haven't reached any consensus on how RISC-V will handle this. If RISC-V allows the test then the memory model can't forbid it.
Agreed. How about this? If the RISC-V question is answered by the end of next week, I update accordingly. If not, I update the comment to give the details.
Hey, at least having the memory model go in at about the same time as a new architecture is giving us good practice! ;-)
Thanx, Paul
Quoted 38 lines
Alan
Quoted 34 lines
tools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmus new file +33
-0+ *) + +{} + +P0(int *x, int *y, spinlock_t *mylock) +{ + spin_lock(mylock); + WRITE_ONCE(*x, 1); + WRITE_ONCE(*y, 1); + spin_unlock(mylock); +} + +P1(int *y, int *z, spinlock_t *mylock) +{ + int r0; + + spin_lock(mylock); + r0 = READ_ONCE(*y); + WRITE_ONCE(*z, 1); + spin_unlock(mylock); +} + +P2(int *x, int *z) +{ + int r1; + int r2; + + r2 = READ_ONCE(*z); + smp_mb(); + r1 = READ_ONCE(*x); +} + +exists (1:r0=1 /\ 2:r2=1 /\ 2:r1=0)
Re: [PATCH RFC tools/lkmm 09/12] tools/memory-model: Add required herd7 version to README file
In reply to Alan SternQuoted 27 lines · Alan Stern
Quoted 25 lines · Paul E. McKenney
LKMM and the herd7 tool are co-evolving, and out-of-date herd7 tools produce inaccurate results, often with no obvious error messages. This commit therefore adds the required herd7 version to the LKMM README file.
Longer term, it would be good if .cat files could specify the required version in a manner allowing herd7 to produce clear diagnostics.
Suggested-by Akira Yokosawa <[email protected]>Signed-off-by Paul E. McKenney <[email protected]>--- tools/memory-model/README | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)tools/memory-model/README +2
-1@@ -20,7 +20,8 @@ that litmus test to be exercised within the Linux kernel. REQUIREMENTS ============ -The "herd7" and "klitmus7" tools must be downloaded separately: +Version 7.48 of the "herd7" and "klitmus7" tools must be downloaded +separately:
Quoted 5 lines
tools/memory-model/README that litmus test to be exercised within the Linux kernel. · line 26
Quoted 1 line
tools/memory-model/README +0
-0https://github.com/herd/herdtools7The text immediately below this mentions the Docker image and gentoo package. Aren't they both seriously out of date at this point? In which case, shouldn't we remove them from the README?
Agreed, we should. How about the following?
Thanx, Paul
------------------------------------------------------------------------
commit b59fd89b465f0bfbfe06bf47e22c0cf160aef66b
Author: Paul E. McKenney <[email protected]> Date: Wed Feb 21 08:13:48 2018 -0800
tools/memory-model: Remove mention of docker/gentoo image
Because the docker and gentoo images haven't been updated in quite some time, they are likely to provide more confusion than help. This commit therefore removes mention of them from the README file.
tools/memory-model/README +0 -15
@@ -27,21 +27,6 @@ separately: See "herdtools7/INSTALL.md" for installation instructions. -Alternatively, Abhishek Bhardwaj has kindly provided a Docker image -of these tools at "abhishek40/memory-model". Abhishek suggests the -following commands to install and use this image: - - - Users should install Docker for their distribution. - - docker run -itd abhishek40/memory-model - - docker attach <id-emitted-from-the-previous-command> - -Gentoo users might wish to make use of Patrick McLean's package: - - https://gitweb.gentoo.org/repo/gentoo.git/tree/dev-util/herdtools7 - -These packages may not be up-to-date with respect to the GitHub -repository. - ================== BASIC USAGE: HERD7
Alan Stern
maintainerRe: [PATCH RFC tools/lkmm 10/12] tools/memory-model: Add a S lock-based external-view litmus test
In reply to Paul E. McKenneyQuoted 5 lines · Paul E. McKenney
Quoted 4 lines · Alan Stern
Quoted 2 lines · Paul E. McKenney
From: Alan Stern <[email protected]>
Quoted 7 lines
Quoted 5 lines
Quoted 2 lines
This commit adds a litmus test in which
P0()andP1()form a lock-based S litmus test, with the addition ofP2(), which observes P0()'s and P1()'sWhy do you call this an "S" litmus test? Isn't ISA2 a better description?
Indeed, the name of the test is in fact ISA2.
Sure; and the Changelog entry should reflect this.
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
accesses with a full memory barrier but without the lock. This litmus test asks whether writes carried out by two different processes under the same lock will be seen in order by a third process not holding that lock. The answer to this question is "yes" for all architectures supporting the Linux kernel, but is "no" according to the current version of LKMM.
A patch to LKMM is under development.
Quoted 8 lines
Quoted 8 lines
Quoted 6 lines
Signed-off-by Alan Stern <[email protected]>Signed-off-by Paul E. McKenney <[email protected]>--- .../ISA2+pooncelock+pooncelock+pombonce.litmus | 41 ++++++++++++++++++++++ 1 file changed, 41 insertions(+) create mode 100644 tools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmusAren't these tests supposed to be described in litmus-tests/README?
You apparently missed this recommendation.
Quoted 19 lines
Quoted 10 lines
Quoted 10 lines
tools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmus new file +4
-0@@ -0,0 +1,41 @@ +C ISA2+pooncelock+pooncelock+pombonce.litmus + +(* + * Result: SometimesQuoted 8 lines
tools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmus line 8
Quoted 4 lines
tools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmus new file +4
-0+ * + * This test shows that the ordering provided by a lock-protected S + * litmus test (P0() and P1()) are not visible to external process P2(). + * This is likely to change soon.That last line may be premature. We haven't reached any consensus on how RISC-V will handle this. If RISC-V allows the test then the memory model can't forbid it.
Quoted 3 lines
Agreed. How about this? If the RISC-V question is answered by the end of next week, I update accordingly. If not, I update the comment to give the details.
The README also should be updated.
Quoted 2 lines
Hey, at least having the memory model go in at about the same time as a new architecture is giving us good practice! ;-)
Hopefully things will settle down in a week or two.
Alan
Alan Stern
maintainerRe: [PATCH RFC tools/lkmm 09/12] tools/memory-model: Add required herd7 version to README file
In reply to Paul E. McKenneyQuoted 69 lines · Paul E. McKenney
Quoted 27 lines · Alan Stern
Quoted 25 lines · Paul E. McKenney
LKMM and the herd7 tool are co-evolving, and out-of-date herd7 tools produce inaccurate results, often with no obvious error messages. This commit therefore adds the required herd7 version to the LKMM README file.
Longer term, it would be good if .cat files could specify the required version in a manner allowing herd7 to produce clear diagnostics.
Suggested-by Akira Yokosawa <[email protected]>Signed-off-by Paul E. McKenney <[email protected]>--- tools/memory-model/README | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)tools/memory-model/README +2
-1@@ -20,7 +20,8 @@ that litmus test to be exercised within the Linux kernel. REQUIREMENTS ============ -The "herd7" and "klitmus7" tools must be downloaded separately: +Version 7.48 of the "herd7" and "klitmus7" tools must be downloaded +separately:Quoted 5 lines
tools/memory-model/README that litmus test to be exercised within the Linux kernel. · line 26
Quoted 1 line
tools/memory-model/README +0
-0https://github.com/herd/herdtools7The text immediately below this mentions the Docker image and gentoo package. Aren't they both seriously out of date at this point? In which case, shouldn't we remove them from the README?
Agreed, we should. How about the following?
Thanx, Paul
------------------------------------------------------------------------
commit
b59fd89b465f0bfbfe06bf47e22c0cf160aef66bAuthor: Paul E. McKenney <[email protected]> Date: Wed Feb 21 08:13:48 2018 -0800
tools/memory-model: Remove mention of docker/gentoo imageBecause the docker and gentoo images haven't been updated in quite some time, they are likely to provide more confusion than help. This commit therefore removes mention of them from the README file.
Reported-by Alan Stern <[email protected]>Signed-off-by Paul E. McKenney <[email protected]>tools/memory-model/README +0
-8@@ -27,21 +27,6 @@ separately: See "herdtools7/INSTALL.md" for installation instructions. -Alternatively, Abhishek Bhardwaj has kindly provided a Docker image -of these tools at "abhishek40/memory-model". Abhishek suggests the -following commands to install and use this image: - - - Users should install Docker for their distribution. - - docker run -itd abhishek40/memory-model - - docker attach <id-emitted-from-the-previous-command> -
tools/memory-model/README separately: · line 32
Quoted 10 lines
tools/memory-model/README +0
-7-Gentoo users might wish to make use of Patrick McLean's package: - - https://gitweb.gentoo.org/repo/gentoo.git/tree/dev-util/herdtools7 - -These packages may not be up-to-date with respect to the GitHub -repository. - ================== BASIC USAGE: HERD7
Yeah, that's good.
Alan
Re: [PATCH RFC tools/lkmm 10/12] tools/memory-model: Add a S lock-based external-view litmus test
In reply to Alan SternQuoted 10 lines · Alan Stern
Quoted 8 lines · Paul E. McKenney
Quoted 7 lines · Alan Stern
Quoted 4 lines · Paul E. McKenney
From: Alan Stern <[email protected]>
This commit adds a litmus test in which
P0()andP1()form a lock-based S litmus test, with the addition ofP2(), which observes P0()'s and P1()'s
Quoted 6 lines
Quoted 4 lines
Quoted 2 lines
Why do you call this an "S" litmus test? Isn't ISA2 a better description?
Indeed, the name of the test is in fact ISA2.
Sure; and the Changelog entry should reflect this.
No argument.
Quoted 15 lines
Quoted 15 lines
Quoted 15 lines
Quoted 14 lines
accesses with a full memory barrier but without the lock. This litmus test asks whether writes carried out by two different processes under the same lock will be seen in order by a third process not holding that lock. The answer to this question is "yes" for all architectures supporting the Linux kernel, but is "no" according to the current version of LKMM.
A patch to LKMM is under development.
Signed-off-by Alan Stern <[email protected]>Signed-off-by Paul E. McKenney <[email protected]>--- .../ISA2+pooncelock+pooncelock+pombonce.litmus | 41 ++++++++++++++++++++++ 1 file changed, 41 insertions(+) create mode 100644 tools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmus
Quoted 3 lines
Quoted 1 line
Quoted 1 line
Aren't these tests supposed to be described in litmus-tests/README?
You apparently missed this recommendation.
I did, please accept my apologies and please see below.
Quoted 19 lines
Quoted 19 lines
Quoted 18 lines
Quoted 6 lines
tools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmus new file +0
-0tools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmus line 8
Quoted 8 lines
tools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmus new file +8
-0@@ -0,0 +1,41 @@ +C ISA2+pooncelock+pooncelock+pombonce.litmus + +(* + * Result: Sometimes + * + * This test shows that the ordering provided by a lock-protected S + * litmus test (P0() and P1()) are not visible to external process P2(). + * This is likely to change soon.That last line may be premature. We haven't reached any consensus on how RISC-V will handle this. If RISC-V allows the test then the memory model can't forbid it.
Quoted 5 lines
Quoted 3 lines
Agreed. How about this? If the RISC-V question is answered by the end of next week, I update accordingly. If not, I update the comment to give the details.
The README also should be updated.
Agreed.
Quoted 4 lines
Quoted 2 lines
Hey, at least having the memory model go in at about the same time as a new architecture is giving us good practice! ;-)
Hopefully things will settle down in a week or two.
Here is hoping!
Thanx, Paul
------------------------------------------------------------------------
commit e6658d1d7fcc6391f3d00beaadc484243123a893
Author: Paul E. McKenney <[email protected]> Date: Wed Feb 21 09:49:01 2018 -0800
tools/memory-order: Add documentation of new litmus test
The litmus-tests/README file lacked any mention of then litmus test named ISA2+pooncelock+pooncelock+pombonce.litmus. This commit therefore adds this test.
tools/memory-model/litmus-tests/README +5 -0
@@ -32,6 +32,11 @@ IRIW+poonceonces+OnceOnce.litmus order of a pair of writes, where each write is to a different variable by a different process? +ISA2+pooncelock+pooncelock+pombonce.litmus + Tests whether the ordering provided by a lock-protected S litmus + test is visible to an external process whose accesses are + separated by smp_mb(). + ISA2+poonceonces.litmus As below, but with store-release replaced with WRITE_ONCE() and load-acquire replaced with READ_ONCE().
Alan Stern
maintainerRe: [PATCH RFC tools/lkmm 10/12] tools/memory-model: Add a S lock-based external-view litmus test
Quoted 22 lines · Paul E. McKenney
Quoted 10 lines · Alan Stern
Quoted 8 lines · Paul E. McKenney
Quoted 7 lines · Alan Stern
Quoted 4 lines · Paul E. McKenney
From: Alan Stern <[email protected]>
This commit adds a litmus test in which
P0()andP1()form a lock-based S litmus test, with the addition ofP2(), which observes P0()'s and P1()'sQuoted 6 lines
Quoted 4 lines
Quoted 2 lines
Why do you call this an "S" litmus test? Isn't ISA2 a better description?
Indeed, the name of the test is in fact ISA2.
Sure; and the Changelog entry should reflect this.
No argument.
------------------------------------------------------------------------
Quoted 7 lines
commit
e6658d1d7fcc6391f3d00beaadc484243123a893Author: Paul E. McKenney <[email protected]> Date: Wed Feb 21 09:49:01 2018 -0800
tools/memory-order: Add documentation of new litmus testThe litmus-tests/README file lacked any mention of then litmus test
s/lacked/lacks/
s/then/the new/
Quoted 1 line
named ISA2+pooncelock+pooncelock+pombonce.litmus. This commit therefore
s/named //
Quoted 1 line
adds this test.
It adds a description of the test, not the test itself.
Quoted 9 lines
Reported-by Alan Stern <[email protected]>Signed-off-by Paul E. McKenney <[email protected]>tools/memory-model/litmus-tests/README +0
-0
tools/memory-model/litmus-tests/README IRIW+poonceonces+OnceOnce.litmus · line 36
Quoted 5 lines
tools/memory-model/litmus-tests/README +2
-0@@ -32,6 +32,11 @@ IRIW+poonceonces+OnceOnce.litmus order of a pair of writes, where each write is to a different variable by a different process? +ISA2+pooncelock+pooncelock+pombonce.litmus + Tests whether the ordering provided by a lock-protected S litmus
Call it an ISA2 litmus test, not an S litmus test!
tools/memory-model/litmus-tests/README IRIW+poonceonces+OnceOnce.litmus · line 42
Quoted 6 lines
tools/memory-model/litmus-tests/README +3
-0+ test is visible to an external process whose accesses are + separated by smp_mb(). + ISA2+poonceonces.litmus As below, but with store-release replaced with WRITE_ONCE() and load-acquire replaced with READ_ONCE().
Alan
Re: [PATCH RFC tools/lkmm 10/12] tools/memory-model: Add a S lock-based external-view litmus test
Quoted 35 lines · Alan Stern
Quoted 22 lines · Paul E. McKenney
Quoted 10 lines · Alan Stern
Quoted 8 lines · Paul E. McKenney
Quoted 7 lines · Alan Stern
Quoted 4 lines · Paul E. McKenney
From: Alan Stern <[email protected]>
This commit adds a litmus test in which
P0()andP1()form a lock-based S litmus test, with the addition ofP2(), which observes P0()'s and P1()'sQuoted 6 lines
Quoted 4 lines
Quoted 2 lines
Why do you call this an "S" litmus test? Isn't ISA2 a better description?
Indeed, the name of the test is in fact ISA2.
Sure; and the Changelog entry should reflect this.
No argument.
------------------------------------------------------------------------
Quoted 7 lines
commit
e6658d1d7fcc6391f3d00beaadc484243123a893Author: Paul E. McKenney <[email protected]> Date: Wed Feb 21 09:49:01 2018 -0800
tools/memory-order: Add documentation of new litmus testThe litmus-tests/README file lacked any mention of then litmus test
s/lacked/lacks/
s/then/the new/
Quoted 7 lines
Quoted 1 line
named ISA2+pooncelock+pooncelock+pombonce.litmus. This commit therefore
s/named //
Quoted 1 line
adds this test.
It adds a description of the test, not the test itself.
Good catches, fixed.
Quoted 11 lines
Quoted 11 lines
Reported-by Alan Stern <[email protected]>Signed-off-by Paul E. McKenney <[email protected]>tools/memory-model/litmus-tests/README +0
-0@@ -32,6 +32,11 @@ IRIW+poonceonces+OnceOnce.litmus order of a pair of writes, where each write is to a different variable by a different process?
Quoted 4 lines
tools/memory-model/litmus-tests/README IRIW+poonceonces+OnceOnce.litmus · line 36
Quoted 2 lines
tools/memory-model/litmus-tests/README +2
-0+ISA2+pooncelock+pooncelock+pombonce.litmus + Tests whether the ordering provided by a lock-protected S litmusCall it an ISA2 litmus test, not an S litmus test!
Given the structure of the test, the relationship to S is important because it helps motivate why anyone might care. But yes, having ISA2 only in the filename is a bit obtuse. How about the following?
ISA2+pooncelock+pooncelock+pombonce.litmus
Tests whether the ordering provided by a lock-protected S litmus test is visible to an external process whose accesses are
separated by smp_mb(). This addition of an external process to
S is otherwise known as ISA2.
Thanx, Paul
Quoted 9 lines
tools/memory-model/litmus-tests/README IRIW+poonceonces+OnceOnce.litmus · line 42
Quoted 6 lines
tools/memory-model/litmus-tests/README +3
-0+ test is visible to an external process whose accesses are + separated by smp_mb(). + ISA2+poonceonces.litmus As below, but with store-release replaced with WRITE_ONCE() and load-acquire replaced with READ_ONCE().Alan
Alan Stern
maintainerRe: [PATCH RFC tools/lkmm 10/12] tools/memory-model: Add a S lock-based external-view litmus test
Quoted 9 lines · Paul E. McKenney
Quoted 4 lines
tools/memory-model/litmus-tests/README IRIW+poonceonces+OnceOnce.litmus · line 36
Quoted 2 lines
tools/memory-model/litmus-tests/README +2
-0+ISA2+pooncelock+pooncelock+pombonce.litmus + Tests whether the ordering provided by a lock-protected S litmusCall it an ISA2 litmus test, not an S litmus test!
Given the structure of the test, the relationship to S is important because it helps motivate why anyone might care. But yes, having ISA2 only in the filename is a bit obtuse. How about the following?
Quoted 5 lines
ISA2+pooncelock+pooncelock+pombonce.litmus
Tests whether the ordering provided by a lock-protected S litmus test is visible to an external process whose accesses are
separated bysmp_mb(). This addition of an external process to
S is otherwise known as ISA2.
Okay, that's somewhat better.
However, I still don't understand why you think of this as a form of S. In S, the first variable written by P0 is the same as the variable written by P1. In this test, no variable other than the spinlock gets written twice. To me that seems like a pretty fundamental difference.
Alan
Re: [PATCH RFC tools/lkmm 10/12] tools/memory-model: Add a S lock-based external-view litmus test
Quoted 17 lines · Alan Stern
Quoted 9 lines · Paul E. McKenney
Quoted 4 lines
tools/memory-model/litmus-tests/README IRIW+poonceonces+OnceOnce.litmus · line 36
Quoted 2 lines
tools/memory-model/litmus-tests/README +2
-0+ISA2+pooncelock+pooncelock+pombonce.litmus + Tests whether the ordering provided by a lock-protected S litmusCall it an ISA2 litmus test, not an S litmus test!
Given the structure of the test, the relationship to S is important because it helps motivate why anyone might care. But yes, having ISA2 only in the filename is a bit obtuse. How about the following?
Quoted 5 lines
ISA2+pooncelock+pooncelock+pombonce.litmus
Tests whether the ordering provided by a lock-protected S litmus test is visible to an external process whose accesses are
separated bysmp_mb(). This addition of an external process to
S is otherwise known as ISA2.
Quoted 6 lines
Okay, that's somewhat better.
However, I still don't understand why you think of this as a form of S. In S, the first variable written by P0 is the same as the variable written by P1. In this test, no variable other than the spinlock gets written twice. To me that seems like a pretty fundamental difference.
There is a chain of processes connected by variables, similar to a snap-together toy. If you "disconnect" S at the end and snap in a process having a pair of reads separated by a full memory barrier, you get ISA2. And yes, this does rename one of S's variables, but that is OK because in this view, each variable is defined by the connection between a given pair of pair of processes.
Unconventional perhaps, but then again remember who you are emailing with. ;-)
Another (perhaps more conventional) way to think of this is in terms of Andrea's python script that identified equivalent litmus tests. For that script, both the variable names and process numbers are irrelevant.
Thanx, Paul
Re: [PATCH RFC tools/lkmm 10/12] tools/memory-model: Add a S lock-based external-view litmus test
In reply to Paul E. McKenneyQuoted 8 lines · Paul E. McKenney
From: Alan Stern <[email protected]>
This commit adds a litmus test in which
P0()andP1()form a lock-based S litmus test, with the addition ofP2(), which observes P0()'s and P1()'s accesses with a full memory barrier but without the lock. This litmus test asks whether writes carried out by two different processes under the same lock will be seen in order by a third process not holding that lock. The answer to this question is "yes" for all architectures supporting
Hmm.. it this true? Our spin_lock() is RCpc because of PowerPC, so spin_lock()+spin_unlock() pairs don't provide transitivity, and that's why we have smp_mb__after_unlock_lock(). Is there something I'm missing? Or there is an upcomming commit to switch PowerPC's lock implementation?
[Cc ppc maintainers]
Regards,
Boqun
Quoted 61 lines
the Linux kernel, but is "no" according to the current version of LKMM.
A patch to LKMM is under development.
Signed-off-by Alan Stern <[email protected]>Signed-off-by Paul E. McKenney <[email protected]>--- .../ISA2+pooncelock+pooncelock+pombonce.litmus | 41 ++++++++++++++++++++++ 1 file changed, 41 insertions(+) create mode 100644 tools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmustools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmus new file +41
-0@@ -0,0 +1,41 @@ +C ISA2+pooncelock+pooncelock+pombonce.litmus + +(* + * Result: Sometimes + * + * This test shows that the ordering provided by a lock-protected S + * litmus test (P0() and P1()) are not visible to external process P2(). + * This is likely to change soon. + *) + +{} + +P0(int *x, int *y, spinlock_t *mylock) +{ + spin_lock(mylock); + WRITE_ONCE(*x, 1); + WRITE_ONCE(*y, 1); + spin_unlock(mylock); +} + +P1(int *y, int *z, spinlock_t *mylock) +{ + int r0; + + spin_lock(mylock); + r0 = READ_ONCE(*y); + WRITE_ONCE(*z, 1); + spin_unlock(mylock); +} + +P2(int *x, int *z) +{ + int r1; + int r2; + + r2 = READ_ONCE(*z); + smp_mb(); + r1 = READ_ONCE(*x); +} + +exists (1:r0=1 /\ 2:r2=1 /\ 2:r1=0)Signature · 1 line
2.5.2
Re: [PATCH RFC tools/lkmm 10/12] tools/memory-model: Add a S lock-based external-view litmus test
Quoted 10 lines · Boqun Feng
Quoted 8 lines · Paul E. McKenney
From: Alan Stern <[email protected]>
This commit adds a litmus test in which
P0()andP1()form a lock-based S litmus test, with the addition ofP2(), which observes P0()'s and P1()'s accesses with a full memory barrier but without the lock. This litmus test asks whether writes carried out by two different processes under the same lock will be seen in order by a third process not holding that lock. The answer to this question is "yes" for all architectures supporting
Quoted 4 lines
Hmm.. it this true? Our
spin_lock()is RCpc because of PowerPC, so spin_lock()+spin_unlock() pairs don't provide transitivity, and that's why we havesmp_mb__after_unlock_lock(). Is there something I'm missing? Or there is an upcomming commit to switch PowerPC's lock implementation?
The PowerPC lock implementation's unlock-lock pair does not order writes from the previous critical section against reads from the later critical section, but it does order other combinations of reads and writes. Some have apparently said that RISC-V 's unlock-lock pair also does not order writes from the previous critical section against writes from the later critical section. And no, I don't claim to have yet gotten my head around RISC-V memory ordering. ;-)
Thanx, Paul
Quoted 66 lines
[Cc ppc maintainers]
Regards,
BoqunQuoted 61 lines
the Linux kernel, but is "no" according to the current version of LKMM.
A patch to LKMM is under development.
Signed-off-by Alan Stern <[email protected]>Signed-off-by Paul E. McKenney <[email protected]>--- .../ISA2+pooncelock+pooncelock+pombonce.litmus | 41 ++++++++++++++++++++++ 1 file changed, 41 insertions(+) create mode 100644 tools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmustools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmus new file +41
-0@@ -0,0 +1,41 @@ +C ISA2+pooncelock+pooncelock+pombonce.litmus + +(* + * Result: Sometimes + * + * This test shows that the ordering provided by a lock-protected S + * litmus test (P0() and P1()) are not visible to external process P2(). + * This is likely to change soon. + *) + +{} + +P0(int *x, int *y, spinlock_t *mylock) +{ + spin_lock(mylock); + WRITE_ONCE(*x, 1); + WRITE_ONCE(*y, 1); + spin_unlock(mylock); +} + +P1(int *y, int *z, spinlock_t *mylock) +{ + int r0; + + spin_lock(mylock); + r0 = READ_ONCE(*y); + WRITE_ONCE(*z, 1); + spin_unlock(mylock); +} + +P2(int *x, int *z) +{ + int r1; + int r2; + + r2 = READ_ONCE(*z); + smp_mb(); + r1 = READ_ONCE(*x); +} + +exists (1:r0=1 /\ 2:r2=1 /\ 2:r1=0)Signature · 1 line
2.5.2
Re: [PATCH RFC tools/lkmm 10/12] tools/memory-model: Add a S lock-based external-view litmus test
Quoted 11 lines · Paul E. McKenney
Quoted 10 lines · Boqun Feng
Quoted 8 lines · Paul E. McKenney
From: Alan Stern <[email protected]>
This commit adds a litmus test in which
P0()andP1()form a lock-based S litmus test, with the addition ofP2(), which observes P0()'s and P1()'s accesses with a full memory barrier but without the lock. This litmus test asks whether writes carried out by two different processes under the same lock will be seen in order by a third process not holding that lock. The answer to this question is "yes" for all architectures supporting
Quoted 8 lines
Quoted 4 lines
Hmm.. it this true? Our
spin_lock()is RCpc because of PowerPC, so spin_lock()+spin_unlock() pairs don't provide transitivity, and that's why we havesmp_mb__after_unlock_lock(). Is there something I'm missing? Or there is an upcomming commit to switch PowerPC's lock implementation?The PowerPC lock implementation's unlock-lock pair does not order writes from the previous critical section against reads from the later critical section, but it does order other combinations of reads and writes.
Ah.. right! Thanks for the explanation ;-)
Quoted 5 lines
Some have apparently said that RISC-V 's unlock-lock pair also does not order writes from the previous critical section against writes from the later critical section. And no, I don't claim to have yet gotten my head around RISC-V memory ordering. ;-)
Me neither. Now I remember this: we have a off-list(accidentally) discussion about this, and IIRC at that moment riscv people confirmed that riscv's unlock-lock pair doesn't order write->write, but that was before their memory model draft posted for discussions, so things may change now...
Besides, I think the smp_mb() on P2 can be relaxed to smp_rmb(), no?
Regards,
Boqun
Quoted 70 lines
Thanx, Paul
Quoted 66 lines
[Cc ppc maintainers]
Regards,
BoqunQuoted 61 lines
the Linux kernel, but is "no" according to the current version of LKMM.
A patch to LKMM is under development.
Signed-off-by Alan Stern <[email protected]>Signed-off-by Paul E. McKenney <[email protected]>--- .../ISA2+pooncelock+pooncelock+pombonce.litmus | 41 ++++++++++++++++++++++ 1 file changed, 41 insertions(+) create mode 100644 tools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmustools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmus new file +41
-0@@ -0,0 +1,41 @@ +C ISA2+pooncelock+pooncelock+pombonce.litmus + +(* + * Result: Sometimes + * + * This test shows that the ordering provided by a lock-protected S + * litmus test (P0() and P1()) are not visible to external process P2(). + * This is likely to change soon. + *) + +{} + +P0(int *x, int *y, spinlock_t *mylock) +{ + spin_lock(mylock); + WRITE_ONCE(*x, 1); + WRITE_ONCE(*y, 1); + spin_unlock(mylock); +} + +P1(int *y, int *z, spinlock_t *mylock) +{ + int r0; + + spin_lock(mylock); + r0 = READ_ONCE(*y); + WRITE_ONCE(*z, 1); + spin_unlock(mylock); +} + +P2(int *x, int *z) +{ + int r1; + int r2; + + r2 = READ_ONCE(*z); + smp_mb(); + r1 = READ_ONCE(*x); +} + +exists (1:r0=1 /\ 2:r2=1 /\ 2:r1=0)Signature · 1 line
2.5.2
Daniel Lustig
reviewerRe: [PATCH RFC tools/lkmm 10/12] tools/memory-model: Add a S lock-based external-view litmus test
Quoted 35 lines · Boqun Feng
Quoted 11 lines · Paul E. McKenney
Quoted 10 lines · Boqun Feng
Quoted 8 lines · Paul E. McKenney
From: Alan Stern <[email protected]>
This commit adds a litmus test in which
P0()andP1()form a lock-based S litmus test, with the addition ofP2(), which observes P0()'s and P1()'s accesses with a full memory barrier but without the lock. This litmus test asks whether writes carried out by two different processes under the same lock will be seen in order by a third process not holding that lock. The answer to this question is "yes" for all architectures supportingQuoted 8 lines
Quoted 4 lines
Hmm.. it this true? Our
spin_lock()is RCpc because of PowerPC, so spin_lock()+spin_unlock() pairs don't provide transitivity, and that's why we havesmp_mb__after_unlock_lock(). Is there something I'm missing? Or there is an upcomming commit to switch PowerPC's lock implementation?The PowerPC lock implementation's unlock-lock pair does not order writes from the previous critical section against reads from the later critical section, but it does order other combinations of reads and writes.
Ah.. right! Thanks for the explanation ;-)
Quoted 5 lines
Some have apparently said that RISC-V 's unlock-lock pair also does not order writes from the previous critical section against writes from the later critical section. And no, I don't claim to have yet gotten my head around RISC-V memory ordering. ;-)
Me neither. Now I remember this: we have a off-list(accidentally) discussion about this, and IIRC at that moment riscv people confirmed that riscv's unlock-lock pair doesn't order
write->write, but that was before their memory model draft posted for discussions, so things may change now...
Quoted 7 lines
Besides, I think the
smp_mb()on P2 can be relaxed tosmp_rmb(), no?Regards,
BoqunQuoted 2 lines
Thanx, Paul
As a matter of fact, the RISC-V memory model committee is debating this exact question at the moment. Now that I see this thread I'll have to go back and catch up on what I've missed, but at least I can be on cc from this point on to answer any RISC-V questions that come up from here on.
(Is there some place I should add my name as a RISC-V memory model contact, so I don't miss threads like this in the future?)
And yes, if we go with a purely RCpc interpretation of acquire and release, then I don't believe the writes in the previous critical section would be ordered with the writes in the subsequent critical section. That's really all the argument boils down to. We'd like to support RCpc if we can since that's all some software needs, but we also obviously want to make sure we can support RCsc and these kinds of LKMM subtleties efficiently too when needed. So we have a few encoding details that we're still finalizing, because questions like this one are still popping up :)
Let me know if you had other RISC-V-specific questions I can help answer.
Dan
Re: [PATCH RFC tools/lkmm 10/12] tools/memory-model: Add a S lock-based external-view litmus test
Quoted 41 lines · Daniel Lustig
Quoted 40 lines · Boqun Feng
Quoted 11 lines · Paul E. McKenney
Quoted 10 lines · Boqun Feng
Quoted 8 lines · Paul E. McKenney
From: Alan Stern <[email protected]>
This commit adds a litmus test in which
P0()andP1()form a lock-based S litmus test, with the addition ofP2(), which observes P0()'s and P1()'s accesses with a full memory barrier but without the lock. This litmus test asks whether writes carried out by two different processes under the same lock will be seen in order by a third process not holding that lock. The answer to this question is "yes" for all architectures supportingQuoted 8 lines
Quoted 4 lines
Hmm.. it this true? Our
spin_lock()is RCpc because of PowerPC, so spin_lock()+spin_unlock() pairs don't provide transitivity, and that's why we havesmp_mb__after_unlock_lock(). Is there something I'm missing? Or there is an upcomming commit to switch PowerPC's lock implementation?The PowerPC lock implementation's unlock-lock pair does not order writes from the previous critical section against reads from the later critical section, but it does order other combinations of reads and writes.
Ah.. right! Thanks for the explanation ;-)
Quoted 5 lines
Some have apparently said that RISC-V 's unlock-lock pair also does not order writes from the previous critical section against writes from the later critical section. And no, I don't claim to have yet gotten my head around RISC-V memory ordering. ;-)
Me neither. Now I remember this: we have a off-list(accidentally) discussion about this, and IIRC at that moment riscv people confirmed that riscv's unlock-lock pair doesn't order
write->write, but that was before their memory model draft posted for discussions, so things may change now...Besides, I think the
smp_mb()on P2 can be relaxed tosmp_rmb(), no?Regards,
Boqun
Quoted 9 lines
Quoted 2 lines
Quoted 2 lines
Thanx, Paul
As a matter of fact, the RISC-V memory model committee is debating this exact question at the moment. Now that I see this thread I'll have to go back and catch up on what I've missed, but at least I can be on cc from this point on to answer any RISC-V questions that come up from here on.
Hi Daniel ;-)
Quoted 3 lines
(Is there some place I should add my name as a RISC-V memory model contact, so I don't miss threads like this in the future?)
You can submit a patch to add yourself as a Maintainer or Reviewer for LKMM, Patch #6 in this series is a good example:
https://marc.info/?l=linux-kernel&m=151916916630299&w=2
, and "get_maintainer.pl" will help people find you for memory model stuffs.
Quoted 4 lines
And yes, if we go with a purely RCpc interpretation of acquire and release, then I don't believe the writes in the previous critical section would be ordered with the writes in the subsequent critical section. That's really all the argument boils down to. We'd like
I think atomics in Linux kernel(and in LKMM) are purely RCpc, right? Alan and Andrea?
And we are not going to change it, are we?
If atomics in Linux kernel are purely RCpc, then it cerntainly makes sense for riscv to provide purely RCpc atomics.
Quoted 3 lines
to support RCpc if we can since that's all some software needs, but we also obviously want to make sure we can support RCsc and these kinds of LKMM subtleties efficiently too when needed. So we have a
I think the problem here is that locks in Linux kernel are more strict than RCpc but weaker than RCsc, and there is not a well-known concept for the semantics of locks in Linux kernel AFAIK.
Regards,
Boqun
Quoted 7 lines
few encoding details that we're still finalizing, because questions like this one are still popping up :)
Let me know if you had other RISC-V-specific questions I can help answer.
Dan
Peter Zijlstra
maintainerRe: [PATCH RFC tools/lkmm 10/12] tools/memory-model: Add a S lock-based external-view litmus test
In reply to Daniel LustigQuoted 4 lines · Daniel Lustig
And yes, if we go with a purely RCpc interpretation of acquire and release, then I don't believe the writes in the previous critical section would be ordered with the writes in the subsequent critical section.
Excuse my ignorance (also jumping in the middle of things), but how can this be?
spin_unlock() is a store-release, this means the write to the lock word must happen after any stores inside the critical section.
spin_lock() is a load-acquire + test-and-set-ctrl-dep, we'll only proceed with the critical section if we observe the lock 'unlocked', which also means we must observe the stores prior to the unlock.
And both the ctrl-dep and the ACQUIRE ensure future stores cannot happen before.
So while the lock store and subsequent critical section stores are unordered, I don't see how it would be possible to not be ordered against stores from a previous critical section.
Peter Zijlstra
maintainerRe: [PATCH RFC tools/lkmm 10/12] tools/memory-model: Add a S lock-based external-view litmus test
In reply to Boqun FengQuoted 5 lines · Boqun Feng
Quoted 4 lines
And yes, if we go with a purely RCpc interpretation of acquire and release, then I don't believe the writes in the previous critical section would be ordered with the writes in the subsequent critical section. That's really all the argument boils down to. We'd like
Quoted 7 lines
I think atomics in Linux kernel(and in LKMM) are purely RCpc, right? Alan and Andrea?
And we are not going to change it, are we?
If atomics in Linux kernel are purely RCpc, then it cerntainly makes sense for riscv to provide purely RCpc atomics.
So there's 3 things:
smp_load_acquire(), smp_store_release()
atomic*_{acquire,release}()
*_{lock,unlock}();Which are all quite distinct.
smp_load_acquire() and smp_store_release() are RCpc, and there is no discussion of ever wanting to change that.
The atomics also follow this and are RCpc, in fact the RELEASE only applies to the STORE and the ACQUIRE only applies to the LOAD of the atomics.
The locking primitives OTOH we would really rather like to be RCsc, and everybody except PPC has them as such, PPC being the only one having RCpc locks.
I read the part you quoted from Daniel as being purely about spinlocks, the 'critical section' wording being a dead give away, so I'm then somewhat confused why you talk about atomics.
Peter Zijlstra
maintainerRe: [PATCH RFC tools/lkmm 10/12] tools/memory-model: Add a S lock-based external-view litmus test
In reply to Peter ZijlstraQuoted 16 lines · Peter Zijlstra
Quoted 4 lines · Daniel Lustig
And yes, if we go with a purely RCpc interpretation of acquire and release, then I don't believe the writes in the previous critical section would be ordered with the writes in the subsequent critical section.
Excuse my ignorance (also jumping in the middle of things), but how can this be?
spin_unlock()is a store-release, this means the write to the lock word must happen after any stores inside the critical section.
spin_lock()is a load-acquire + test-and-set-ctrl-dep, we'll only proceed with the critical section if we observe the lock 'unlocked', which also means we must observe the stores prior to the unlock.
Quoted 7 lines
And both the ctrl-dep and the ACQUIRE ensure future stores cannot happen before.
So while the lock store and subsequent critical section stores are unordered, I don't see how it would be possible to not be ordered against stores from a previous critical section.
Or are we talking about a third party observing while not partaking in the lock-chain? Then I agree, the stores can be observed out of order by this 3rd actor.
Re: [PATCH RFC tools/lkmm 10/12] tools/memory-model: Add a S lock-based external-view litmus test
In reply to Peter ZijlstraQuoted 31 lines · Peter Zijlstra
Quoted 5 lines · Boqun Feng
Quoted 4 lines
And yes, if we go with a purely RCpc interpretation of acquire and release, then I don't believe the writes in the previous critical section would be ordered with the writes in the subsequent critical section. That's really all the argument boils down to. We'd like
Quoted 7 lines
I think atomics in Linux kernel(and in LKMM) are purely RCpc, right? Alan and Andrea?
And we are not going to change it, are we?
If atomics in Linux kernel are purely RCpc, then it cerntainly makes sense for riscv to provide purely RCpc atomics.
So there's 3 things:
smp_load_acquire(),smp_store_release()atomic*_{acquire,release}()
*_{lock,unlock}();Which are all quite distinct.
smp_load_acquire()andsmp_store_release()are RCpc, and there is no discussion of ever wanting to change that.The atomics also follow this and are RCpc, in fact the RELEASE only applies to the STORE and the ACQUIRE only applies to the LOAD of the atomics.
Quoted 7 lines
The locking primitives OTOH we would really rather like to be RCsc, and everybody except PPC has them as such, PPC being the only one having RCpc locks.
I read the part you quoted from Daniel as being purely about spinlocks, the 'critical section' wording being a dead give away, so I'm then somewhat confused why you talk about atomics.
Maybe it's me who misunderstand Daniel's words. But my understanding is that riscv people are on a debate about whether their "RCpc" atomic instructions need to be more strict: release+acquire pair orders two writes. And I thought that atomics(including RmW atomics) in kernel only have purely RCpc semantics, which I needed to check with you guy. And if I'm right, it's cerntainly fine for riscv "RCpc" instruction to be purely RCpc.
Note that even on PPC, the release+acquire pair of atomics orders writes before and after, and on x86, writes are ordered since it's TSO. So strictly speaking, I think our current implementation of atomics are a little more strict than purely RCpc. If we think this is an requirement for implementation of atomic primitives, than the current version of riscv's "RCpc" atomics don't suffice.
Regards,
Boqun
Peter Zijlstra
maintainerRe: [PATCH RFC tools/lkmm 10/12] tools/memory-model: Add a S lock-based external-view litmus test
Quoted 8 lines · Boqun Feng
Maybe it's me who misunderstand Daniel's words. But my understanding is that riscv people are on a debate about whether their "RCpc" atomic instructions need to be more strict: release+acquire pair orders two writes. And I thought that atomics(including RmW atomics) in kernel only have purely RCpc semantics, which I needed to check with you guy. And if I'm right, it's cerntainly fine for riscv "RCpc" instruction to be purely RCpc.
Quoted 6 lines
Note that even on PPC, the release+acquire pair of atomics orders writes before and after, and on x86, writes are ordered since it's TSO. So strictly speaking, I think our current implementation of atomics are a little more strict than purely RCpc. If we think this is an requirement for implementation of atomic primitives, than the current version of riscv's "RCpc" atomics don't suffice.
So the question is:
P0()
{
WRITE_ONCE(x, 1);
smp_store_release(&y, 1);
r0 = smp_load_acquire(&y);
WRITE_ONCE(z, 1);
}P1()
{
r1 = READ_ONCE(z);
smp_rmb();
r2 = READ_ONCE(x);
}exists: r0 == 1 /\ r1==1 /\ r2==0
Which per the current LKMM would be forbidden? How would strict RCpc allow that? Due to a fwd from the release to the acquire and then defeating the ordering or something like that?
My vote would go to disallowing this. Allowing this would be rather subtle and unexpected IMO.