Skip to contentSkip to conversation

Miscellaneous fixes

RFC PATCH In review Paul E. McKenney 6 participants 46 messages Feb 20, 2018 – Feb 22, 2018

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

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(-)
#3 lore raw

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
index e3581413420c..50bcedbdca86 100644
@@ -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
deleted file mode 100644
index db3bd3fc0435..000000000000
@@ -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
#5 lore raw

RFC PATCH 3/12 MAINTAINERS: List file memory-barriers.txt within the LKMM entry

In reply to Paul E. McKenney

From: 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
index 50bcedbdca86..674b35c3f28e 100644
@@ -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
#9 lore raw

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
index 9a3bb5949191..dca7d823ad57 100644
@@ -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
#11 lore raw

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
index 674b35c3f28e..cc4c1ac94593 100644
@@ -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
#22 lore raw

RFC PATCH 10/12 tools/memory-model: Add a S lock-based external-view litmus test

In reply to Paul E. McKenney

From: 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
new file mode 100644
index 000000000000..7a39a0aaa976
@@ -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
#13 lore raw

RFC PATCH 7/12 Documentation/memory-barriers.txt: Cross-reference "tools/memory-model/"

In reply to Paul E. McKenney

From: 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
index 479ecec80593..74ad222d11ed 100644
@@ -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
#42 lore raw

RFC PATCH 11/12 tools/memory-model: Convert underscores to hyphens

In reply to Paul E. McKenney

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
index b984bbda01a5..18885ad15de9 100644
@@ -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
index babe2b3b0bb3..f0d27f813ec2 100644
@@ -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
index a397387f77cc..f5a1eb04cb64 100644
@@ -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
#1 lore raw

RFC PATCH 1/12 tools/memory-model: Clarify the origin/scope of the tool name

In reply to Paul E. McKenney

From: 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
index 711cbe72d606..db3bd3fc0435 100644
@@ -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
index 43ba49492111..91414a49fac5 100644
@@ -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
index 57112505f5e0..b984bbda01a5 100644
@@ -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
index 15b7a5dd8a9a..babe2b3b0bb3 100644
@@ -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
#7 lore raw

RFC PATCH 4/12 EXP litmus_tests: Add comments explaining tests' purposes

In reply to Paul E. McKenney

This commit adds comments to the litmus tests summarizing what these tests are intended to demonstrate.

[ paulmck: Apply Andrea's and Alan's feedback. ]
---
 .../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
index 5b83d57f6ac5..967f9f2a6226 100644
@@ -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
index fab91c13d52c..4635739f3974 100644
@@ -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
index 6a35ec2042ea..bb068c92d8da 100644
@@ -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
index 32a96b832021..0d9f0a958799 100644
@@ -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
index 7eba2c68992b..50d5db9ea983 100644
@@ -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
index b0556c6c75d4..4b54dd6a6cd9 100644
@@ -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
index 9a1a233d70c3..b321aa6f4ea5 100644
@@ -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
index 235195e87d4e..025b0462ec9b 100644
@@ -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
index dd5ac3a8974a..de6708229dd1 100644
@@ -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
index 47bd61319d93..07b9904b0e49 100644
@@ -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
index a5cdf027e34b..74c49cb3c37b 100644
@@ -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
index 1a2fe5830381..97731b4bbdd8 100644
@@ -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
index 5fe6f1e3c452..712a4fcdf6ce 100644
@@ -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
index 46e1ac7ba126..b2b60b84fb9d 100644
@@ -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
index 0b00cc7293ba..d52c68429722 100644
@@ -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
index 90d011c34f33..72c9276b363e 100644
@@ -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
index 604ad41ea0c2..c078f38ff27a 100644
@@ -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
index e69b9e3e9436..a0e884ad2132 100644
@@ -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
index f7a12e00f82d..5386f128a131 100644
@@ -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
index d0d541c8ec7d..8c9c2f81a580 100644
@@ -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
index 1d292d0d6603..c53350205d28 100644
@@ -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
index b76caa5af1af..74b874ffa8da 100644
@@ -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
index c1797e03807e..10d550730b25 100644
@@ -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
index f5e7c92f61cc..6a2bc12a1af1 100644
@@ -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
index e3d0018025dd..97fcbffde9a0 100644
@@ -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
index 9c2cb53e6ef0..415248fb6699 100644
@@ -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
index c9a1f1a49ae1..10a2aa04cd07 100644
@@ -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
index 25409a033514..a20fc3fafb53 100644
@@ -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
#17 lore raw

RFC PATCH 9/12 tools/memory-model: Add required herd7 version to README file

In reply to 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.

---
 tools/memory-model/README | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
tools/memory-model/README +2 -1
index 91414a49fac5..ea950c566ffd 100644
@@ -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
#44 lore raw

RFC PATCH 12/12 tools/memory-model: Remove rb-dep, smp_read_barrier_depends, and lockless_dereference

In reply to Paul E. McKenney

From: 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
index 1917712bce99..04e458acd6d4 100644
@@ -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
index 18885ad15de9..432c7cf71b23 100644
@@ -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
index f0d27f813ec2..df97db03b6c2 100644
@@ -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
index f5a1eb04cb64..5dfb9c7f3462 100644
@@ -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
#15 lore raw

RFC PATCH 8/12 memory-barriers: Fix description of data dependency barriers

In reply to Paul E. McKenney

From: 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
index 74ad222d11ed..0d83333b84a9 100644
@@ -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
#2 lore raw

[tip:locking/core] tools/memory-model: Clarify the origin/scope of the tool name

In reply to Paul E. McKenney
tools/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
index 711cbe7..db3bd3f 100644
@@ -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
index 43ba494..91414a4 100644
@@ -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
index 5711250..b984bbd 100644
@@ -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
index 15b7a5d..babe2b3 100644
@@ -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.
#8 lore raw

[tip:locking/core] EXP litmus_tests: Add comments explaining tests' purposes

In reply to Paul E. McKenney
EXP 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
index 5b83d57..967f9f2 100644
@@ -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
index fab91c1..4635739 100644
@@ -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
index 6a35ec2..bb068c9 100644
@@ -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
index 32a96b8..0d9f0a9 100644
@@ -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
index 7eba2c6..50d5db9 100644
@@ -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
index b0556c6..4b54dd6 100644
@@ -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
index 9a1a233..b321aa6 100644
@@ -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
index 235195e..025b046 100644
@@ -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
index dd5ac3a..de67082 100644
@@ -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
index 47bd613..07b9904 100644
@@ -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
index a5cdf02..74c49cb 100644
@@ -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
index 1a2fe58..97731b4 100644
@@ -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
index 5fe6f1e..712a4fcd 100644
@@ -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
index 46e1ac7b..b2b60b8 100644
@@ -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
index 0b00cc7..d52c684 100644
@@ -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
index 90d011c..72c9276 100644
@@ -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
index 604ad41..c078f38 100644
@@ -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
index e69b9e3..a0e884a 100644
@@ -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
index f7a12e0..5386f12 100644
@@ -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
index d0d541c..8c9c2f8 100644
@@ -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
index 1d292d0..c533502 100644
@@ -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
index b76caa5..74b874f 100644
@@ -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
index c1797e03..10d5507 100644
@@ -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
index f5e7c92..6a2bc12 100644
@@ -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
index e3d0018..97fcbff 100644
@@ -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
index 9c2cb53..415248f 100644
@@ -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
index c9a1f1a..10a2aa0 100644
@@ -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
index 25409a0..a20fc3f 100644
@@ -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)
#4 lore raw

[tip:locking/core] MAINTAINERS: Add the Memory Consistency Model subsystem

In reply to Paul E. McKenney
MAINTAINERS: 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
index 9a7f76e..654c6c6 100644
@@ -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
deleted file mode 100644
index db3bd3f..0000000
@@ -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/
#6 lore raw

[tip:locking/core] MAINTAINERS: List file memory-barriers.txt within the LKMM entry

In reply to Paul E. McKenney
MAINTAINERS: 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
index 654c6c6..42da350 100644
@@ -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]>
#10 lore raw

[tip:locking/core] README: Fix a couple of punctuation errors

In reply to Paul E. McKenney
README: 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
index 9a3bb59..dca7d823 100644
@@ -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()
#12 lore raw

[tip:locking/core] MAINTAINERS: Add Akira Yokosawa as an LKMM reviewer

In reply to Paul E. McKenney
MAINTAINERS: 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
index 42da350..1dd9cc2 100644
@@ -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
#14 lore raw

[tip:locking/core] Documentation/memory-barriers.txt: Cross-reference "tools/memory-model/"

In reply to Paul E. McKenney
Documentation/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
index a863009..a37d3af 100644
@@ -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.
#16 lore raw

[tip:locking/core] memory-barriers: Fix description of data dependency barriers

In reply to Paul E. McKenney
memory-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
index a37d3af..da6525b 100644
@@ -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
#18 lore raw

[tip:locking/core] tools/memory-model: Add required herd7 version to README file

In reply to Paul E. McKenney
tools/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
index 91414a4..ea950c5 100644
@@ -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
 
#23 lore raw

[tip:locking/core] tools/memory-model: Add a S lock-based external-view litmus test

In reply to Paul E. McKenney
tools/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
similarity index 55%
copy from tools/memory-model/litmus-tests/Z6.0+pooncelock+pooncelock+pombonce.litmus
copy to tools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmus
index 10a2aa0..7a39a0a 100644
@@ -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)
#43 lore raw

[tip:locking/core] tools/memory-model: Convert underscores to hyphens

In reply to Paul E. McKenney
tools/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
index b984bbd..18885ad 100644
@@ -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
index babe2b3..f0d27f8 100644
@@ -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
index a397387..f5a1eb0 100644
@@ -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)
#45 lore raw

[tip:locking/core] tools/memory-model: Remove rb-dep, smp_read_barrier_depends, and lockless_dereference

In reply to Paul E. McKenney
tools/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
index 1917712..04e458a 100644
@@ -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
index 18885ad..432c7cf 100644
@@ -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
index f0d27f8..df97db0 100644
@@ -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
index f5a1eb0..5dfb9c7 100644
@@ -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} ; }
maintainer
#24 lore raw

Re: [PATCH RFC tools/lkmm 10/12] tools/memory-model: Add a S lock-based external-view litmus test

In reply to Paul E. McKenney
Quoted 4 lines · Paul E. McKenney

From: 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

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.

---
 .../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
new file mode 100644
index 000000000000..7a39a0aaa976

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)
maintainer
#19 lore raw

Re: [PATCH RFC tools/lkmm 09/12] tools/memory-model: Add required herd7 version to README file

In reply to Paul E. McKenney
Quoted 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.

---
 tools/memory-model/README | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
tools/memory-model/README +0 -0
index 91414a49fac5..ea950c566ffd 100644

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

#25 lore raw

Re: [PATCH RFC tools/lkmm 10/12] tools/memory-model: Add a S lock-based external-view litmus test

In reply to Alan Stern
Quoted 9 lines · Alan Stern
Quoted 4 lines · Paul E. McKenney

From: 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

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.

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.

---
 .../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 10 lines
tools/memory-model/litmus-tests/ISA2+pooncelock+pooncelock+pombonce.litmus new file +4 -0
new file mode 100644
index 000000000000..7a39a0aaa976
@@ -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)
#20 lore raw

Re: [PATCH RFC tools/lkmm 09/12] tools/memory-model: Add required herd7 version to README file

In reply to Alan Stern
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.

---
 tools/memory-model/README | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
tools/memory-model/README +2 -1
index 91414a49fac5..ea950c566ffd 100644
@@ -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 -0
   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?

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
index ea950c566ffd..0b3a5f3c9ccd 100644
@@ -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
maintainer
#26 lore raw

Re: [PATCH RFC tools/lkmm 10/12] tools/memory-model: Add a S lock-based external-view litmus test

In reply to Paul E. McKenney
Quoted 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() and P1() form a lock-based S litmus test, with the addition of P2(), which observes P0()'s and P1()'s

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.

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
---
 .../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?

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
new file mode 100644
index 000000000000..7a39a0aaa976
@@ -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.

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

maintainer
#21 lore raw

Re: [PATCH RFC tools/lkmm 09/12] tools/memory-model: Add required herd7 version to README file

In reply to Paul E. McKenney
Quoted 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.

---
 tools/memory-model/README | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
tools/memory-model/README +2 -1
index 91414a49fac5..ea950c566ffd 100644
@@ -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 -0
   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?

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 -8
index ea950c566ffd..0b3a5f3c9ccd 100644
@@ -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

#27 lore raw

Re: [PATCH RFC tools/lkmm 10/12] tools/memory-model: Add a S lock-based external-view litmus test

In reply to Alan Stern
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() and P1() form a lock-based S litmus test, with the addition of P2(), 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.

---
 .../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 -0
new file mode 100644
index 000000000000..7a39a0aaa976

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.

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
index dca7d823ad57..aff3eb90e067 100644
@@ -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().
maintainer
#28 lore raw

Re: [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() and P1() form a lock-based S litmus test, with the addition of P2(), 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 7 lines

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

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
tools/memory-model/litmus-tests/README +0 -0
index dca7d823ad57..aff3eb90e067 100644

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

#29 lore raw

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() and P1() form a lock-based S litmus test, with the addition of P2(), 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 7 lines

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

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
tools/memory-model/litmus-tests/README +0 -0
index dca7d823ad57..aff3eb90e067 100644
@@ -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 litmus

Call 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

maintainer
#30 lore raw

Re: [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 litmus

Call 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 by smp_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

#31 lore raw

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 litmus

Call 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 by smp_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

#32 lore raw

Re: [PATCH RFC tools/lkmm 10/12] tools/memory-model: Add a S lock-based external-view litmus test

In reply to Paul E. McKenney
Quoted 8 lines · Paul E. McKenney

From: 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

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.

---
 .../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
new file mode 100644
index 000000000000..7a39a0aaa976
@@ -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
#33 lore raw

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

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 have smp_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,
Boqun

Quoted 61 lines

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
new file mode 100644
index 000000000000..7a39a0aaa976
@@ -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
#34 lore raw

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

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 have smp_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,
Boqun

Quoted 61 lines

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
new file mode 100644
index 000000000000..7a39a0aaa976
@@ -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
reviewer
#35 lore raw

Re: [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() 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

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 have smp_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 to smp_rmb(), no?

Regards,
Boqun

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.

(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

#36 lore raw

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

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 have smp_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 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

maintainer
#40 lore raw

Re: [PATCH RFC tools/lkmm 10/12] tools/memory-model: Add a S lock-based external-view litmus test

In reply to Daniel Lustig
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.

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.

maintainer
#37 lore raw

Re: [PATCH RFC tools/lkmm 10/12] tools/memory-model: Add a S lock-based external-view litmus test

In reply to Boqun Feng
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() 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.

maintainer
#41 lore raw

Re: [PATCH RFC tools/lkmm 10/12] tools/memory-model: Add a S lock-based external-view litmus test

In reply to Peter Zijlstra
Quoted 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.

#38 lore raw

Re: [PATCH RFC tools/lkmm 10/12] tools/memory-model: Add a S lock-based external-view litmus test

In reply to Peter Zijlstra
Quoted 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() 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.

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

maintainer
#39 lore raw

Re: [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.