* [PATCH tip/core/rcu 2/3] memory-barriers: Retain barrier() in fold-to-zero example
2014-08-28 18:12 ` [PATCH tip/core/rcu 1/3] memory-barriers: Fix control-ordering no-transitivity example Paul E. McKenney
@ 2014-08-28 18:12 ` Paul E. McKenney
2014-08-28 18:12 ` [PATCH tip/core/rcu 3/3] memory-barriers: Fix description of 2-legged-if-based control dependencies Paul E. McKenney
2014-09-07 17:10 ` [PATCH tip/core/rcu 1/3] memory-barriers: Fix control-ordering no-transitivity example Pranith Kumar
2 siblings, 0 replies; 5+ messages in thread
From: Paul E. McKenney @ 2014-08-28 18:12 UTC (permalink / raw)
To: linux-kernel
Cc: mingo, laijs, dipankar, akpm, mathieu.desnoyers, josh, tglx,
peterz, rostedt, dhowells, edumazet, dvhart, fweisbec, oleg,
bobby.prani, Paul E. McKenney
From: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
The transformation in the fold-to-zero example incorrectly omits the
barrier() directive. This commit therefore adds it back in.
Reported-by: Pranith Kumar <pranith@gatech.edu>
Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
---
Documentation/memory-barriers.txt | 9 ++++++---
1 file changed, 6 insertions(+), 3 deletions(-)
diff --git a/Documentation/memory-barriers.txt b/Documentation/memory-barriers.txt
index d67c508eb660..600b45c6e2ad 100644
--- a/Documentation/memory-barriers.txt
+++ b/Documentation/memory-barriers.txt
@@ -679,12 +679,15 @@ equal to zero, in which case the compiler is within its rights to
transform the above code into the following:
q = ACCESS_ONCE(a);
+ barrier();
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:
+This transformation fails to require that the CPU respect the ordering
+between the load from variable 'a' and the store to variable 'b'.
+Yes, the barrier() is still there, but it affects only the compiler,
+not the CPU. Therefore, 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. */
--
1.8.1.5
^ permalink raw reply related [flat|nested] 5+ messages in thread
* [PATCH tip/core/rcu 3/3] memory-barriers: Fix description of 2-legged-if-based control dependencies
2014-08-28 18:12 ` [PATCH tip/core/rcu 1/3] memory-barriers: Fix control-ordering no-transitivity example Paul E. McKenney
2014-08-28 18:12 ` [PATCH tip/core/rcu 2/3] memory-barriers: Retain barrier() in fold-to-zero example Paul E. McKenney
@ 2014-08-28 18:12 ` Paul E. McKenney
2014-09-07 17:10 ` [PATCH tip/core/rcu 1/3] memory-barriers: Fix control-ordering no-transitivity example Pranith Kumar
2 siblings, 0 replies; 5+ messages in thread
From: Paul E. McKenney @ 2014-08-28 18:12 UTC (permalink / raw)
To: linux-kernel
Cc: mingo, laijs, dipankar, akpm, mathieu.desnoyers, josh, tglx,
peterz, rostedt, dhowells, edumazet, dvhart, fweisbec, oleg,
bobby.prani, Paul E. McKenney
From: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
Sad to say, current compilers really will hoist identical stores from both
branches of an "if" statement to precede the conditional. This commit
therefore updates the description of control dependencies to reflect this
ugly reality.
Reported-by: Pranith Kumar <bobby.prani@gmail.com>
Reported-by: Peter Zijlstra <peterz@infradead.org>
Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
---
Documentation/memory-barriers.txt | 103 ++++++++++++++++++--------------------
1 file changed, 49 insertions(+), 54 deletions(-)
diff --git a/Documentation/memory-barriers.txt b/Documentation/memory-barriers.txt
index 600b45c6e2ad..22a969cdd476 100644
--- a/Documentation/memory-barriers.txt
+++ b/Documentation/memory-barriers.txt
@@ -574,30 +574,14 @@ 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();
+ ACCESS_ONCE(b) = p;
}
-into this, which of course defeats the ordering:
-
- b = p;
- q = a;
- if (q)
- do_something();
- else
- do_something_else();
+Please note that ACCESS_ONCE() is not optional! Without the
+ACCESS_ONCE(), might combine the load from 'a' with other loads from
+'a', and the store to 'b' with other stores to 'b', with possible highly
+counterintuitive effects on ordering.
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
@@ -605,11 +589,12 @@ to optimize the original example by eliminating the "if" statement
as follows:
q = a;
- b = p; /* BUG: Compiler can reorder!!! */
- do_something();
+ b = p; /* BUG: Compiler and CPU can both reorder!!! */
-The solution is again ACCESS_ONCE() and barrier(), which preserves the
-ordering between the load from variable 'a' and the store to variable 'b':
+So don't leave out the ACCESS_ONCE().
+
+It is tempting to try to enforce ordering on identical stores on both
+branches of the "if" statement as follows:
q = ACCESS_ONCE(a);
if (q) {
@@ -622,18 +607,11 @@ ordering between the load from variable 'a' and the store to variable 'b':
do_something_else();
}
-The initial ACCESS_ONCE() is required to prevent the compiler from
-proving the value of 'a', and the pair of barrier() invocations are
-required to prevent the compiler from pulling the two identical stores
-to 'b' out from the legs of the "if" statement.
-
-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, which is why the barrier() invocations
-are absolutely required if you have identical stores in both legs of
-the "if" statement:
+Unfortunately, current compilers will transform this as follows at high
+optimization levels:
q = ACCESS_ONCE(a);
+ barrier();
ACCESS_ONCE(b) = p; /* BUG: No ordering vs. load from a!!! */
if (q) {
/* ACCESS_ONCE(b) = p; -- moved up, BUG!!! */
@@ -643,21 +621,36 @@ the "if" statement:
do_something_else();
}
-It is of course legal for the prior load to be part of the conditional,
-for example, as follows:
+Now there is no conditional between the load from 'a' and the store to
+'b', which means that the CPU is within its rights to reorder them:
+The conditional is absolutely required, and must be present in the
+assembly code even after all compiler optimizations have been applied.
+Therefore, if you need ordering in this example, you need explicit
+memory barriers, for example, smp_store_release():
- if (ACCESS_ONCE(a) > 0) {
- barrier();
- ACCESS_ONCE(b) = q / 2;
+ q = ACCESS_ONCE(a);
+ if (q) {
+ smp_store_release(&b, p);
do_something();
} else {
- barrier();
- ACCESS_ONCE(b) = q / 3;
+ smp_store_release(&b, p);
+ do_something_else();
+ }
+
+In contrast, without explicit memory barriers, two-legged-if control
+ordering is guaranteed only when the stores differ, for example:
+
+ q = ACCESS_ONCE(a);
+ if (q) {
+ ACCESS_ONCE(b) = p;
+ do_something();
+ } else {
+ ACCESS_ONCE(b) = r;
do_something_else();
}
-This will again ensure that the load from variable 'a' is ordered before the
-stores to variable 'b'.
+The initial ACCESS_ONCE() is still required to prevent the compiler from
+proving the value of 'a'.
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
@@ -665,12 +658,10 @@ the needed conditional. For example:
q = ACCESS_ONCE(a);
if (q % MAX) {
- barrier();
ACCESS_ONCE(b) = p;
do_something();
} else {
- barrier();
- ACCESS_ONCE(b) = p;
+ ACCESS_ONCE(b) = r;
do_something_else();
}
@@ -679,15 +670,15 @@ equal to zero, in which case the compiler is within its rights to
transform the above code into the following:
q = ACCESS_ONCE(a);
- barrier();
ACCESS_ONCE(b) = p;
do_something_else();
-This transformation fails to require that the CPU respect the ordering
-between the load from variable 'a' and the store to variable 'b'.
-Yes, the barrier() is still there, but it affects only the compiler,
-not the CPU. Therefore, if you are relying on this ordering, you should
-do something like the following:
+Given this transformation, the CPU is not required to respect the ordering
+between the load from variable 'a' and the store to variable 'b'. It is
+tempting to add a barrier(), but this does not help. The conditional
+is gone, and the barrier won't bring it back. Therefore, if you are
+relying on this ordering, you should make sure that MAX is greater than
+one, perhaps as follows:
q = ACCESS_ONCE(a);
BUILD_BUG_ON(MAX <= 1); /* Order load from a with store to b. */
@@ -695,10 +686,14 @@ do something like the following:
ACCESS_ONCE(b) = p;
do_something();
} else {
- ACCESS_ONCE(b) = p;
+ ACCESS_ONCE(b) = r;
do_something_else();
}
+Please note once again that the stores to 'b' differ. If they were
+identical, as noted earlier, the compiler could pull this store outside
+of the 'if' statement.
+
Finally, control dependencies do -not- provide transitivity. This is
demonstrated by two related examples, with the initial values of
x and y both being zero:
--
1.8.1.5
^ permalink raw reply related [flat|nested] 5+ messages in thread* Re: [PATCH tip/core/rcu 1/3] memory-barriers: Fix control-ordering no-transitivity example
2014-08-28 18:12 ` [PATCH tip/core/rcu 1/3] memory-barriers: Fix control-ordering no-transitivity example Paul E. McKenney
2014-08-28 18:12 ` [PATCH tip/core/rcu 2/3] memory-barriers: Retain barrier() in fold-to-zero example Paul E. McKenney
2014-08-28 18:12 ` [PATCH tip/core/rcu 3/3] memory-barriers: Fix description of 2-legged-if-based control dependencies Paul E. McKenney
@ 2014-09-07 17:10 ` Pranith Kumar
2 siblings, 0 replies; 5+ messages in thread
From: Pranith Kumar @ 2014-09-07 17:10 UTC (permalink / raw)
To: Paul E. McKenney
Cc: LKML, Ingo Molnar, Lai Jiangshan, Dipankar Sarma, Andrew Morton,
Mathieu Desnoyers, Josh Triplett, Thomas Gleixner, Peter Zijlstra,
Steven Rostedt, David Howells, Eric Dumazet, dvhart,
Frédéric Weisbecker, Oleg Nesterov
On Thu, Aug 28, 2014 at 2:12 PM, Paul E. McKenney
<paulmck@linux.vnet.ibm.com> wrote:
> From: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
>
> The control-ordering example demonstrating lack of transitivity had
> multiple problems. This commit fixes them.
>
> Reported-by: Nikolay Samofatov <nikolay.samofatov@gmail.com>
> Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Reviewed-by: Pranith Kumar <bobby.prani@gmail.com>
> ---
> Documentation/memory-barriers.txt | 28 +++++++++++++++++-----------
> 1 file changed, 17 insertions(+), 11 deletions(-)
>
> diff --git a/Documentation/memory-barriers.txt b/Documentation/memory-barriers.txt
> index a4de88fb55f0..d67c508eb660 100644
> --- a/Documentation/memory-barriers.txt
> +++ b/Documentation/memory-barriers.txt
> @@ -697,30 +697,36 @@ should do something like the following:
> }
>
> Finally, control dependencies do -not- provide transitivity. This is
> -demonstrated by two related examples:
> +demonstrated by two related examples, with the initial values of
> +x and y both being zero:
>
> CPU 0 CPU 1
> ===================== =====================
> r1 = ACCESS_ONCE(x); r2 = ACCESS_ONCE(y);
> - if (r1 >= 0) if (r2 >= 0)
> + 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:
> +then adding the following CPU would guarantee a related assertion:
>
> - CPU 2 CPU 3
> - ===================== =====================
> - ACCESS_ONCE(x) = 2; ACCESS_ONCE(y) = 2;
> + CPU 2
> + =====================
> + ACCESS_ONCE(x) = 2;
> +
> + assert(!(r1 == 2 && r2 == 1 && x == 2)); /* FAILS!!! */
>
> - 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 three-CPU example completes. If you
> +need the three-CPU example to provide ordering, you will need smp_mb()
> +between the loads and stores in the CPU 0 and CPU 1 code fragments,
> +that is, just before or just after the "if" statements.
>
> -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.
> +These two examples are the LB and WWC litmus tests from this paper:
> +http://www.cl.cam.ac.uk/users/pes20/ppc-supplemental/test6.pdf and this
> +site: https://www.cl.cam.ac.uk/~pes20/ppcmem/index.html.
>
> In summary:
>
> --
> 1.8.1.5
>
--
Pranith
^ permalink raw reply [flat|nested] 5+ messages in thread