Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1423568 > unrolled thread

[PATCH Documentation/memory-barriers.txt] Clarify limited control-dependency scope

Back to article view | Back to linux.kernel

Contents

  [PATCH Documentation/memory-barriers.txt] Clarify limited  control-dependency scope "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-06-16 01:10 +0200
    Re: [PATCH Documentation/memory-barriers.txt] Clarify limited  control-dependency scope Ingo Molnar <mingo@kernel.org> - 2016-06-17 10:00 +0200
      Re: [PATCH Documentation/memory-barriers.txt] Clarify limited  control-dependency scope "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-06-18 02:30 +0200
    [tip:locking/core] locking/Documentation: Clarify limited  control-dependency scope "tip-bot for Paul E. McKenney" <tipbot@zytor.com> - 2016-06-17 14:30 +0200

#1423568 — [PATCH Documentation/memory-barriers.txt] Clarify limited control-dependency scope

Nothing in the control-dependencies section of memory-barriers.txt
says that control dependencies don't extend beyond the end of the
if-statement containing the control dependency.  Worse yet, in many
situations, they do extend beyond that if-statement.  In particular,
the compiler cannot destroy the control dependency given proper use of
READ_ONCE() and WRITE_ONCE().  However, a weakly ordered system having
a conditional-move instruction provides the control-dependency guarantee
only to code within the scope of the if-statement itself.

This commit therefore adds words and an example demonstrating this
limitation of control dependencies.

Reported-by: Will Deacon <will.deacon@arm.com>
Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>

diff --git a/Documentation/memory-barriers.txt b/Documentation/memory-barriers.txt
index 147ae8ec836f..a4d0a99de04d 100644
--- a/Documentation/memory-barriers.txt
+++ b/Documentation/memory-barriers.txt
@@ -806,6 +806,41 @@ out-guess your code.  More generally, although READ_ONCE() does force
 the compiler to actually emit code for a given load, it does not force
 the compiler to use the results.
 
+In addition, control dependencies apply only to the then-clause and
+else-clause of the if-statement in question.  In particular, it does
+not necessarily apply to code following the if-statement:
+
+	q = READ_ONCE(a);
+	if (q) {
+		WRITE_ONCE(b, p);
+	} else {
+		WRITE_ONCE(b, r);
+	}
+	WRITE_ONCE(c, 1);  /* BUG: No ordering against the read from "a". */
+
+It is tempting to argue that there in fact is ordering because the
+compiler cannot reorder volatile accesses and also cannot reorder
+the writes to "b" with the condition.  Unfortunately for this line
+of reasoning, the compiler might compile the two writes to "b" as
+conditional-move instructions, as in this fanciful pseudo-assembly
+language:
+
+	ld r1,a
+	ld r2,p
+	ld r3,r
+	cmp r1,$0
+	cmov,ne r4,r2
+	cmov,eq r4,r3
+	st r4,b
+	st $1,c
+
+A weakly ordered CPU would have no dependency of any sort between the load
+from "a" and the store to "c".  The control dependencies would extend
+only to the pair of cmov instructions and the store depending on them.
+In short, control dependencies apply only to the stores in the then-clause
+and else-clause of the if-statement in question (including functions
+invoked by those two clauses), not to code following that 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:
@@ -869,6 +904,12 @@ In summary:
       atomic{,64}_read() can help to preserve your control dependency.
       Please see the COMPILER BARRIER section for more information.
 
+  (*) Control dependencies apply only to the then-clause and else-clause
+      of the if-statement containing the control dependency, including
+      any functions that these two clauses call.  Control dependencies
+      do -not- apply to code following the if-statement containing the
+      control dependency.
+
   (*) Control dependencies pair normally with other types of barriers.
 
   (*) Control dependencies do -not- provide transitivity.  If you

[toc] | [next] | [standalone]

#1424775

* Paul E. McKenney <paulmck@linux.vnet.ibm.com> wrote:

> Nothing in the control-dependencies section of memory-barriers.txt
> says that control dependencies don't extend beyond the end of the
> if-statement containing the control dependency.  Worse yet, in many
> situations, they do extend beyond that if-statement.  In particular,
> the compiler cannot destroy the control dependency given proper use of
> READ_ONCE() and WRITE_ONCE().  However, a weakly ordered system having
> a conditional-move instruction provides the control-dependency guarantee
> only to code within the scope of the if-statement itself.
> 
> This commit therefore adds words and an example demonstrating this
> limitation of control dependencies.
> 
> Reported-by: Will Deacon <will.deacon@arm.com>
> Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>
> 
> diff --git a/Documentation/memory-barriers.txt b/Documentation/memory-barriers.txt
> index 147ae8ec836f..a4d0a99de04d 100644
> --- a/Documentation/memory-barriers.txt
> +++ b/Documentation/memory-barriers.txt
> @@ -806,6 +806,41 @@ out-guess your code.  More generally, although READ_ONCE() does force
>  the compiler to actually emit code for a given load, it does not force
>  the compiler to use the results.
>  
> +In addition, control dependencies apply only to the then-clause and
> +else-clause of the if-statement in question.  In particular, it does
> +not necessarily apply to code following the if-statement:
> +
> +	q = READ_ONCE(a);
> +	if (q) {
> +		WRITE_ONCE(b, p);
> +	} else {
> +		WRITE_ONCE(b, r);
> +	}
> +	WRITE_ONCE(c, 1);  /* BUG: No ordering against the read from "a". */
> +
> +It is tempting to argue that there in fact is ordering because the
> +compiler cannot reorder volatile accesses and also cannot reorder
> +the writes to "b" with the condition.  Unfortunately for this line
> +of reasoning, the compiler might compile the two writes to "b" as
> +conditional-move instructions, as in this fanciful pseudo-assembly
> +language:

While CMOV would be the typical situation, even without CMOV the compiler could 
also internally transform it to:

> +	if (q)
> +		WRITE_ONCE(b, p);
> +	if (!q)
> +		WRITE_ONCE(b, r);

... and CPU speculation flow could get past the two branches without seeing any 
ordering constraint with the writes to 'b'.

I.e. conditions are not 'atomic', they can be 'torn' by the compiler just as much 
as reads or writes can be torn.

Thanks,

	Ingo

[toc] | [prev] | [next] | [standalone]

#1425583

On Fri, Jun 17, 2016 at 09:53:50AM +0200, Ingo Molnar wrote:
> 
> * Paul E. McKenney <paulmck@linux.vnet.ibm.com> wrote:
> 
> > Nothing in the control-dependencies section of memory-barriers.txt
> > says that control dependencies don't extend beyond the end of the
> > if-statement containing the control dependency.  Worse yet, in many
> > situations, they do extend beyond that if-statement.  In particular,
> > the compiler cannot destroy the control dependency given proper use of
> > READ_ONCE() and WRITE_ONCE().  However, a weakly ordered system having
> > a conditional-move instruction provides the control-dependency guarantee
> > only to code within the scope of the if-statement itself.
> > 
> > This commit therefore adds words and an example demonstrating this
> > limitation of control dependencies.
> > 
> > Reported-by: Will Deacon <will.deacon@arm.com>
> > Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> > Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>
> > 
> > diff --git a/Documentation/memory-barriers.txt b/Documentation/memory-barriers.txt
> > index 147ae8ec836f..a4d0a99de04d 100644
> > --- a/Documentation/memory-barriers.txt
> > +++ b/Documentation/memory-barriers.txt
> > @@ -806,6 +806,41 @@ out-guess your code.  More generally, although READ_ONCE() does force
> >  the compiler to actually emit code for a given load, it does not force
> >  the compiler to use the results.
> >  
> > +In addition, control dependencies apply only to the then-clause and
> > +else-clause of the if-statement in question.  In particular, it does
> > +not necessarily apply to code following the if-statement:
> > +
> > +	q = READ_ONCE(a);
> > +	if (q) {
> > +		WRITE_ONCE(b, p);
> > +	} else {
> > +		WRITE_ONCE(b, r);
> > +	}
> > +	WRITE_ONCE(c, 1);  /* BUG: No ordering against the read from "a". */
> > +
> > +It is tempting to argue that there in fact is ordering because the
> > +compiler cannot reorder volatile accesses and also cannot reorder
> > +the writes to "b" with the condition.  Unfortunately for this line
> > +of reasoning, the compiler might compile the two writes to "b" as
> > +conditional-move instructions, as in this fanciful pseudo-assembly
> > +language:
> 
> While CMOV would be the typical situation, even without CMOV the compiler could 
> also internally transform it to:
> 
> > +	if (q)
> > +		WRITE_ONCE(b, p);
> > +	if (!q)
> > +		WRITE_ONCE(b, r);
> 
> ... and CPU speculation flow could get past the two branches without seeing any 
> ordering constraint with the writes to 'b'.
> 
> I.e. conditions are not 'atomic', they can be 'torn' by the compiler just as much 
> as reads or writes can be torn.

That is an interesting test case!

PowerPC prohibits speculating the writes in your transformed case, that is,
prohibits the writes to "b" from being reordered with the read from "a".
I believe that ARM also prohibits it in that case, but must defer to
Will Deacon.  Not sure about MIPS.

Or am I misunderstanding your intent with that example?

							Thanx, Paul

[toc] | [prev] | [next] | [standalone]

#1425014 — [tip:locking/core] locking/Documentation: Clarify limited control-dependency scope

Commit-ID:  ebff09a6ff164aec2b33bf1f9a488c45ac108413
Gitweb:     http://git.kernel.org/tip/ebff09a6ff164aec2b33bf1f9a488c45ac108413
Author:     Paul E. McKenney <paulmck@linux.vnet.ibm.com>
AuthorDate: Wed, 15 Jun 2016 16:08:17 -0700
Committer:  Ingo Molnar <mingo@kernel.org>
CommitDate: Fri, 17 Jun 2016 09:54:45 +0200

locking/Documentation: Clarify limited control-dependency scope

Nothing in the control-dependencies section of memory-barriers.txt
says that control dependencies don't extend beyond the end of the
if-statement containing the control dependency.  Worse yet, in many
situations, they do extend beyond that if-statement.  In particular,
the compiler cannot destroy the control dependency given proper use of
READ_ONCE() and WRITE_ONCE().  However, a weakly ordered system having
a conditional-move instruction provides the control-dependency guarantee
only to code within the scope of the if-statement itself.

This commit therefore adds words and an example demonstrating this
limitation of control dependencies.

Reported-by: Will Deacon <will.deacon@arm.com>
Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: corbet@lwn.net
Cc: linux-arch@vger.kernel.org
Cc: linux-doc@vger.kernel.org
Link: http://lkml.kernel.org/r/20160615230817.GA18039@linux.vnet.ibm.com
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 Documentation/memory-barriers.txt | 41 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 41 insertions(+)

diff --git a/Documentation/memory-barriers.txt b/Documentation/memory-barriers.txt
index 147ae8e..a4d0a99 100644
--- a/Documentation/memory-barriers.txt
+++ b/Documentation/memory-barriers.txt
@@ -806,6 +806,41 @@ out-guess your code.  More generally, although READ_ONCE() does force
 the compiler to actually emit code for a given load, it does not force
 the compiler to use the results.
 
+In addition, control dependencies apply only to the then-clause and
+else-clause of the if-statement in question.  In particular, it does
+not necessarily apply to code following the if-statement:
+
+	q = READ_ONCE(a);
+	if (q) {
+		WRITE_ONCE(b, p);
+	} else {
+		WRITE_ONCE(b, r);
+	}
+	WRITE_ONCE(c, 1);  /* BUG: No ordering against the read from "a". */
+
+It is tempting to argue that there in fact is ordering because the
+compiler cannot reorder volatile accesses and also cannot reorder
+the writes to "b" with the condition.  Unfortunately for this line
+of reasoning, the compiler might compile the two writes to "b" as
+conditional-move instructions, as in this fanciful pseudo-assembly
+language:
+
+	ld r1,a
+	ld r2,p
+	ld r3,r
+	cmp r1,$0
+	cmov,ne r4,r2
+	cmov,eq r4,r3
+	st r4,b
+	st $1,c
+
+A weakly ordered CPU would have no dependency of any sort between the load
+from "a" and the store to "c".  The control dependencies would extend
+only to the pair of cmov instructions and the store depending on them.
+In short, control dependencies apply only to the stores in the then-clause
+and else-clause of the if-statement in question (including functions
+invoked by those two clauses), not to code following that 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:
@@ -869,6 +904,12 @@ In summary:
       atomic{,64}_read() can help to preserve your control dependency.
       Please see the COMPILER BARRIER section for more information.
 
+  (*) Control dependencies apply only to the then-clause and else-clause
+      of the if-statement containing the control dependency, including
+      any functions that these two clauses call.  Control dependencies
+      do -not- apply to code following the if-statement containing the
+      control dependency.
+
   (*) Control dependencies pair normally with other types of barriers.
 
   (*) Control dependencies do -not- provide transitivity.  If you

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web