[PATCH v4 tip/core/locking 3/4] Documentation/memory-barriers.txt:Prohibit speculative writes

[Ingo Molnar]

(here's #3.)

----- Forwarded message from "Paul E. McKenney" <paulmck@xxxxxxxxxxxxxxxxxx> -----

Date: Wed,  4 Dec 2013 14:46:58 -0800
From: "Paul E. McKenney" <paulmck@xxxxxxxxxxxxxxxxxx>
To: linux-kernel@xxxxxxxxxxxxxxx
Cc: mingo@xxxxxxxxxx, laijs@xxxxxxxxxxxxxx, dipankar@xxxxxxxxxx, akpm@xxxxxxxxxxxxxxxxxxxx, mathieu.desnoyers@xxxxxxxxxxxx, josh@xxxxxxxxxxxxxxxx, niv@xxxxxxxxxx,
	tglx@xxxxxxxxxxxxx, peterz@xxxxxxxxxxxxx, rostedt@xxxxxxxxxxx, dhowells@xxxxxxxxxx, edumazet@xxxxxxxxxx, darren@xxxxxxxxxx, fweisbec@xxxxxxxxx, sbw@xxxxxxx,
	"Paul E. McKenney" <paulmck@xxxxxxxxxxxxxxxxxx>, Richard Henderson <rth@xxxxxxxxxxx>, Ivan Kokshaysky <ink@xxxxxxxxxxxxxxxxxxxx>, Matt Turner
	<mattst88@xxxxxxxxx>, Russell King <linux@xxxxxxxxxxxxxxxx>, Arnd Bergmann <arnd@xxxxxxxx>, Olof Johansson <olof@xxxxxxxxx>, Catalin Marinas
	<catalin.marinas@xxxxxxx>, Will Deacon <will.deacon@xxxxxxx>, Haavard Skinnemoen <hskinnemoen@xxxxxxxxx>, Hans-Christian Egtvedt <egtvedt@xxxxxxxxxxxx>, Mike
	Frysinger <vapier@xxxxxxxxxx>, Mark Salter <msalter@xxxxxxxxxx>, Aurelien Jacquiot <a-jacquiot@xxxxxx>, Mikael Starvik <starvik@xxxxxxxx>, Jesper Nilsson
	<jesper.nilsson@xxxxxxxx>, Yoshinori Sato <ysato@xxxxxxxxxxxxxxxxxxxx>, Richard Kuo <rkuo@xxxxxxxxxxxxxx>, Tony Luck <tony.luck@xxxxxxxxx>, Fenghua Yu
	<fenghua.yu@xxxxxxxxx>, Hirokazu Takata <takata@xxxxxxxxxxxxxx>, Geert Uytterhoeven <geert@xxxxxxxxxxxxxx>, James Hogan <james.hogan@xxxxxxxxxx>, Michal Simek
	<monstr@xxxxxxxxx>, Ralf Baechle <ralf@xxxxxxxxxxxxxx>, Koichi Yasutake <yasutake.koichi@xxxxxxxxxxxxxxxx>, Jonas Bonn <jonas@xxxxxxxxxxxx>, "James E.J.
	Bottomley" <jejb@xxxxxxxxxxxxxxxx>, Helge Deller <deller@xxxxxx>, Benjamin Herrenschmidt <benh@xxxxxxxxxxxxxxxxxxx>, Paul Mackerras <paulus@xxxxxxxxx>, Anatolij
	Gustschin <agust@xxxxxxx>, Josh Boyer <jwboyer@xxxxxxxxx>, Matt Porter <mporter@xxxxxxxxxxxxxxxxxxx>, Vitaly Bordug <vitb@xxxxxxxxxxxxxxxxxxx>, Kumar Gala
	<galak@xxxxxxxxxxxxxxxxxxx>, Martin Schwidefsky <schwidefsky@xxxxxxxxxx>, Heiko Carstens <heiko.carstens@xxxxxxxxxx>, Chen Liqin <liqin.linux@xxxxxxxxx>, Lennox
	Wu <lennox.wu@xxxxxxxxx>, Paul Mundt <lethal@xxxxxxxxxxxx>, "David S. Miller" <davem@xxxxxxxxxxxxx>, Chris Metcalf <cmetcalf@xxxxxxxxxx>, Jeff Dike
	<jdike@xxxxxxxxxxx>, Richard Weinberger <richard@xxxxxx>, Guan Xuetao <gxt@xxxxxxxxxxxxxxx>, Ingo Molnar <mingo@xxxxxxxxxx>, "H. Peter Anvin" <hpa@xxxxxxxxx>,
	Chris Zankel <chris@xxxxxxxxxx>, Max Filippov <jcmvbkbc@xxxxxxxxx>
Subject: [PATCH tip/core/locking 3/4] Documentation/memory-barriers.txt: Prohibit speculative writes

From: "Paul E. McKenney" <paulmck@xxxxxxxxxxxxxxxxxx>

No SMP architecture currently supporting Linux allows speculative writes,
so this commit updates Documentation/memory-barriers.txt to prohibit
them in Linux core code.  It also records restrictions on their use.

Signed-off-by: Peter Zijlstra <peterz@xxxxxxxxxxxxx>
Signed-off-by: Paul E. McKenney <paulmck@xxxxxxxxxxxxxxxxxx>
Cc: Richard Henderson <rth@xxxxxxxxxxx>
Cc: Ivan Kokshaysky <ink@xxxxxxxxxxxxxxxxxxxx>
Cc: Matt Turner <mattst88@xxxxxxxxx>
Cc: Russell King <linux@xxxxxxxxxxxxxxxx>
Cc: Arnd Bergmann <arnd@xxxxxxxx>
Cc: Olof Johansson <olof@xxxxxxxxx>
Cc: Catalin Marinas <catalin.marinas@xxxxxxx>
Cc: Will Deacon <will.deacon@xxxxxxx>
Cc: Haavard Skinnemoen <hskinnemoen@xxxxxxxxx>
Cc: Hans-Christian Egtvedt <egtvedt@xxxxxxxxxxxx>
Cc: Mike Frysinger <vapier@xxxxxxxxxx>
Cc: Mark Salter <msalter@xxxxxxxxxx>
Cc: Aurelien Jacquiot <a-jacquiot@xxxxxx>
Cc: Mikael Starvik <starvik@xxxxxxxx>
Cc: Jesper Nilsson <jesper.nilsson@xxxxxxxx>
Cc: David Howells <dhowells@xxxxxxxxxx>
Cc: Yoshinori Sato <ysato@xxxxxxxxxxxxxxxxxxxx>
Cc: Richard Kuo <rkuo@xxxxxxxxxxxxxx>
Cc: Tony Luck <tony.luck@xxxxxxxxx>
Cc: Fenghua Yu <fenghua.yu@xxxxxxxxx>
Cc: Hirokazu Takata <takata@xxxxxxxxxxxxxx>
Cc: Geert Uytterhoeven <geert@xxxxxxxxxxxxxx>
Cc: James Hogan <james.hogan@xxxxxxxxxx>
Cc: Michal Simek <monstr@xxxxxxxxx>
Cc: Ralf Baechle <ralf@xxxxxxxxxxxxxx>
Cc: Koichi Yasutake <yasutake.koichi@xxxxxxxxxxxxxxxx>
Cc: Jonas Bonn <jonas@xxxxxxxxxxxx>
Cc: "James E.J. Bottomley" <jejb@xxxxxxxxxxxxxxxx>
Cc: Helge Deller <deller@xxxxxx>
Cc: Benjamin Herrenschmidt <benh@xxxxxxxxxxxxxxxxxxx>
Cc: Paul Mackerras <paulus@xxxxxxxxx>
Cc: Anatolij Gustschin <agust@xxxxxxx>
Cc: Josh Boyer <jwboyer@xxxxxxxxx>
Cc: Matt Porter <mporter@xxxxxxxxxxxxxxxxxxx>
Cc: Vitaly Bordug <vitb@xxxxxxxxxxxxxxxxxxx>
Cc: Kumar Gala <galak@xxxxxxxxxxxxxxxxxxx>
Cc: Martin Schwidefsky <schwidefsky@xxxxxxxxxx>
Cc: Heiko Carstens <heiko.carstens@xxxxxxxxxx>
Cc: Chen Liqin <liqin.linux@xxxxxxxxx>
Cc: Lennox Wu <lennox.wu@xxxxxxxxx>
Cc: Paul Mundt <lethal@xxxxxxxxxxxx>
Cc: "David S. Miller" <davem@xxxxxxxxxxxxx>
Cc: Chris Metcalf <cmetcalf@xxxxxxxxxx>
Cc: Jeff Dike <jdike@xxxxxxxxxxx>
Cc: Richard Weinberger <richard@xxxxxx>
Cc: Guan Xuetao <gxt@xxxxxxxxxxxxxxx>
Cc: Thomas Gleixner <tglx@xxxxxxxxxxxxx>
Cc: Ingo Molnar <mingo@xxxxxxxxxx>
Cc: "H. Peter Anvin" <hpa@xxxxxxxxx>
Cc: Chris Zankel <chris@xxxxxxxxxx>
Cc: Max Filippov <jcmvbkbc@xxxxxxxxx>
---
 Documentation/memory-barriers.txt | 183 ++++++++++++++++++++++++++++++++++++--
 1 file changed, 175 insertions(+), 8 deletions(-)

diff --git a/Documentation/memory-barriers.txt b/Documentation/memory-barriers.txt
index 2d22da095a60..3e4429ef1458 100644
--- a/Documentation/memory-barriers.txt
+++ b/Documentation/memory-barriers.txt
@@ -571,11 +571,10 @@ dependency barrier to make it work correctly.  Consider the following bit of
 code:
 
 	q = ACCESS_ONCE(a);
-	if (p) {
-		<data dependency barrier>
-		q = ACCESS_ONCE(b);
+	if (q) {
+		<data dependency barrier>  /* BUG: No data dependency!!! */
+		p = ACCESS_ONCE(b);
 	}
-	x = *q;
 
 This will not have the desired effect because there is no actual data
 dependency, but rather a control dependency that the CPU may short-circuit
@@ -584,11 +583,176 @@ the load from b as having happened before the load from a.  In such a
 case what's actually required is:
 
 	q = ACCESS_ONCE(a);
-	if (p) {
+	if (q) {
 		<read barrier>
-		q = ACCESS_ONCE(b);
+		p = ACCESS_ONCE(b);
 	}
-	x = *q;
+
+However, stores are not speculated.  This means that ordering -is- provided
+in the following example:
+
+	q = ACCESS_ONCE(a);
+	if (ACCESS_ONCE(q)) {
+		ACCESS_ONCE(b) = p;
+	}
+
+Please note that ACCESS_ONCE() is not optional!  Without the ACCESS_ONCE(),
+the compiler is within its rights to transform this example:
+
+	q = a;
+	if (q) {
+		b = p;  /* BUG: Compiler can reorder!!! */
+		do_something();
+	} else {
+		b = p;  /* BUG: Compiler can reorder!!! */
+		do_something_else();
+	}
+
+into this, which of course defeats the ordering:
+
+	b = p;
+	q = a;
+	if (q)
+		do_something();
+	else
+		do_something_else();
+
+Worse yet, if the compiler is able to prove (say) that the value of
+variable a is always non-zero, it would be well within its rights
+to optimize the original example by eliminating the "if" statement
+as follows:
+
+	q = a;
+	b = p;  /* BUG: Compiler can reorder!!! */
+	do_something();
+
+The solution is again ACCESS_ONCE(), which preserves the ordering between
+the load from variable a and the store to variable b:
+
+	q = ACCESS_ONCE(a);
+	if (q) {
+		ACCESS_ONCE(b) = p;
+		do_something();
+	} else {
+		ACCESS_ONCE(b) = p;
+		do_something_else();
+	}
+
+You could also use barrier() to prevent the compiler from moving
+the stores to variable b, but barrier() would not prevent the
+compiler from proving to itself that a==1 always, so ACCESS_ONCE()
+is also needed.
+
+It is important to note that control dependencies absolutely require a
+a conditional.  For example, the following "optimized" version of
+the above example breaks ordering:
+
+	q = ACCESS_ONCE(a);
+	ACCESS_ONCE(b) = p;  /* BUG: No ordering vs. load from a!!! */
+	if (q) {
+		/* ACCESS_ONCE(b) = p; -- moved up, BUG!!! */
+		do_something();
+	} else {
+		/* ACCESS_ONCE(b) = p; -- moved up, BUG!!! */
+		do_something_else();
+	}
+
+It is of course legal for the prior load to be part of the conditional,
+for example, as follows:
+
+	if (ACCESS_ONCE(a) > 0) {
+		ACCESS_ONCE(b) = q / 2;
+		do_something();
+	} else {
+		ACCESS_ONCE(b) = q / 3;
+		do_something_else();
+	}
+
+This will again ensure that the load from variable a is ordered before the
+stores to variable b.
+
+In addition, you need to be careful what you do with the local variable q,
+otherwise the compiler might be able to guess the value and again remove
+the needed conditional.  For example:
+
+	q = ACCESS_ONCE(a);
+	if (q % MAX) {
+		ACCESS_ONCE(b) = p;
+		do_something();
+	} else {
+		ACCESS_ONCE(b) = p;
+		do_something_else();
+	}
+
+If MAX is defined to be 1, then the compiler knows that (q % MAX) is
+equal to zero, in which case the compiler is within its rights to
+transform the above code into the following:
+
+	q = ACCESS_ONCE(a);
+	ACCESS_ONCE(b) = p;
+	do_something_else();
+
+This transformation loses the ordering between the load from variable a
+and the store to variable b.  If you are relying on this ordering, you
+should do something like the following:
+
+	q = ACCESS_ONCE(a);
+	BUILD_BUG_ON(MAX <= 1); /* Order load from a with store to b. */
+	if (q % MAX) {
+		ACCESS_ONCE(b) = p;
+		do_something();
+	} else {
+		ACCESS_ONCE(b) = p;
+		do_something_else();
+	}
+
+Finally, control dependencies do -not- provide transitivity.  This is
+demonstrated by two related examples:
+
+	CPU 0                     CPU 1
+	=====================     =====================
+	r1 = ACCESS_ONCE(x);      r2 = ACCESS_ONCE(y);
+	if (r1 >= 0)              if (r2 >= 0)
+	  ACCESS_ONCE(y) = 1;       ACCESS_ONCE(x) = 1;
+
+	assert(!(r1 == 1 && r2 == 1));
+
+The above two-CPU example will never trigger the assert().  However,
+if control dependencies guaranteed transitivity (which they do not),
+then adding the following two CPUs would guarantee a related assertion:
+
+	CPU 2                     CPU 3
+	=====================     =====================
+	ACCESS_ONCE(x) = 2;       ACCESS_ONCE(y) = 2;
+
+	assert(!(r1 == 2 && r2 == 2 && x == 1 && y == 1)); /* FAILS!!! */
+
+But because control dependencies do -not- provide transitivity, the
+above assertion can fail after the combined four-CPU example completes.
+If you need the four-CPU example to provide ordering, you will need
+smp_mb() between the loads and stores in the CPU 0 and CPU 1 code fragments.
+
+In summary:
+
+  (*) Control dependencies can order prior loads against later stores.
+      However, they do -not- guarantee any other sort of ordering:
+      Not prior loads against later loads, nor prior stores against
+      later anything.  If you need these other forms of ordering,
+      use smb_rmb(), smp_wmb(), or, in the case of prior stores and
+      later loads, smp_mb().
+
+  (*) Control dependencies require at least one run-time conditional
+      between the prior load and the subsequent store.  If the compiler
+      is able to optimize the conditional away, it will have also
+      optimized away the ordering.  Careful use of ACCESS_ONCE() can
+      help to preserve the needed conditional.
+
+  (*) Control dependencies require that the compiler avoid reordering the
+      dependency into nonexistence.  Careful use of ACCESS_ONCE() or
+      barrier() can help to preserve your control dependency.
+
+  (*) Control dependencies do -not- provide transitivity.  If you
+      need transitivity, use smp_mb().
 
 
 SMP BARRIER PAIRING
@@ -1083,7 +1247,10 @@ compiler from moving the memory accesses either side of it to the other side:
 
 	barrier();
 
-This is a general barrier - lesser varieties of compiler barrier do not exist.
+This is a general barrier -- there are no read-read or write-write variants
+of barrier().  Howevever, ACCESS_ONCE() can be thought of as a weak form
+for barrier() that affects only the specific accesses flagged by the
+ACCESS_ONCE().
 
 The compiler barrier has no direct effect on the CPU, which may then reorder
 things however it wishes.
-- 
1.8.1.5


----- End forwarded message -----
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/