Clarify limited control-dependency scope
Subsystems (3)
PATCH 1/1 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.
Documentation/memory-barriers.txt +41 -0
@@ -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
Quoted 32 lines · Paul E. McKenney
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()andWRITE_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 <[email protected]>Signed-off-by Paul E. McKenney <[email protected]>Documentation/memory-barriers.txt +8
-0@@ -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 {
Documentation/memory-barriers.txt out-guess your code. More generally, although READ_ONCE() does force · line 826
Quoted 10 lines
Documentation/memory-barriers.txt +10
-0+ 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:
Documentation/memory-barriers.txt out-guess your code. More generally, although READ_ONCE() does force · line 817
Quoted 4 lines
Documentation/memory-barriers.txt +4
-0+ 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
Quoted 57 lines · Ingo Molnar
Quoted 32 lines · Paul E. McKenney
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()andWRITE_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 <[email protected]>Signed-off-by Paul E. McKenney <[email protected]>Documentation/memory-barriers.txt +8
-0@@ -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 {Documentation/memory-barriers.txt out-guess your code. More generally, although READ_ONCE() does force · line 826
Quoted 10 lines
Documentation/memory-barriers.txt +10
-0+ 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:
Documentation/memory-barriers.txt out-guess your code. More generally, although READ_ONCE() does force · line 817
Quoted 4 lines
Documentation/memory-barriers.txt +4
-0+ 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'.
Quoted 2 lines
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
tip-bot for Paul E. McKenney
merge bot[tip:locking/core] locking/Documentation: Clarify limited control-dependency scope
In reply to Paul E. McKenneylocking/Documentation: Clarify limited control-dependency scope
Commit-ID: ebff09a6ff164aec2b33bf1f9a488c45ac108413 Gitweb: http://git.kernel.org/tip/ebff09a6ff164aec2b33bf1f9a488c45ac108413 Author: Paul E. McKenney <[email protected]> AuthorDate: Wed, 15 Jun 2016 16:08:17 -0700 Committer: Ingo Molnar <[email protected]> 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.
--- Documentation/memory-barriers.txt | 41 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 41 insertions(+)
Documentation/memory-barriers.txt +41 -0
@@ -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