1CONTROL DEPENDENCIES
2====================
3
4A major difficulty with control dependencies is that current compilers
5do not support them.  One purpose of this document is therefore to
6help you prevent your compiler from breaking your code.  However,
7control dependencies also pose other challenges, which leads to the
8second purpose of this document, namely to help you to avoid breaking
9your own code, even in the absence of help from your compiler.
10
11One such challenge is that control dependencies order only later stores.
12Therefore, a load-load control dependency will not preserve ordering
13unless a read memory barrier is provided.  Consider the following code:
14
15	q = READ_ONCE(a);
16	if (q)
17		p = READ_ONCE(b);
18
19This is not guaranteed to provide any ordering because some types of CPUs
20are permitted to predict the result of the load from "b".  This prediction
21can cause other CPUs to see this load as having happened before the load
22from "a".  This means that an explicit read barrier is required, for example
23as follows:
24
25	q = READ_ONCE(a);
26	if (q) {
27		smp_rmb();
28		p = READ_ONCE(b);
29	}
30
31However, stores are not speculated.  This means that ordering is
32(usually) guaranteed for load-store control dependencies, as in the
33following example:
34
35	q = READ_ONCE(a);
36	if (q)
37		WRITE_ONCE(b, 1);
38
39Control dependencies can pair with each other and with other types
40of ordering.  But please note that neither the READ_ONCE() nor the
41WRITE_ONCE() are optional.  Without the READ_ONCE(), the compiler might
42fuse the load from "a" with other loads.  Without the WRITE_ONCE(),
43the compiler might fuse the store to "b" with other stores.  Worse yet,
44the compiler might convert the store into a load and a check followed
45by a store, and this compiler-generated load would not be ordered by
46the control dependency.
47
48Furthermore, if the compiler is able to prove that the value of variable
49"a" is always non-zero, it would be well within its rights to optimize
50the original example by eliminating the "if" statement as follows:
51
52	q = a;
53	b = 1;  /* BUG: Compiler and CPU can both reorder!!! */
54
55So don't leave out either the READ_ONCE() or the WRITE_ONCE().
56In particular, although READ_ONCE() does force the compiler to emit a
57load, it does *not* force the compiler to actually use the loaded value.
58
59It is tempting to try use control dependencies to enforce ordering on
60identical stores on both branches of the "if" statement as follows:
61
62	q = READ_ONCE(a);
63	if (q) {
64		barrier();
65		WRITE_ONCE(b, 1);
66		do_something();
67	} else {
68		barrier();
69		WRITE_ONCE(b, 1);
70		do_something_else();
71	}
72
73Unfortunately, current compilers will transform this as follows at high
74optimization levels:
75
76	q = READ_ONCE(a);
77	barrier();
78	WRITE_ONCE(b, 1);  /* BUG: No ordering vs. load from a!!! */
79	if (q) {
80		/* WRITE_ONCE(b, 1); -- moved up, BUG!!! */
81		do_something();
82	} else {
83		/* WRITE_ONCE(b, 1); -- moved up, BUG!!! */
84		do_something_else();
85	}
86
87Now there is no conditional between the load from "a" and the store to
88"b", which means that the CPU is within its rights to reorder them:  The
89conditional is absolutely required, and must be present in the final
90assembly code, after all of the compiler and link-time optimizations
91have been applied.  Therefore, if you need ordering in this example,
92you must use explicit memory ordering, for example, smp_store_release():
93
94	q = READ_ONCE(a);
95	if (q) {
96		smp_store_release(&b, 1);
97		do_something();
98	} else {
99		smp_store_release(&b, 1);
100		do_something_else();
101	}
102
103Without explicit memory ordering, control-dependency-based ordering is
104guaranteed only when the stores differ, for example:
105
106	q = READ_ONCE(a);
107	if (q) {
108		WRITE_ONCE(b, 1);
109		do_something();
110	} else {
111		WRITE_ONCE(b, 2);
112		do_something_else();
113	}
114
115The initial READ_ONCE() is still required to prevent the compiler from
116knowing too much about the value of "a".
117
118But please note that you need to be careful what you do with the local
119variable "q", otherwise the compiler might be able to guess the value
120and again remove the conditional branch that is absolutely required to
121preserve ordering.  For example:
122
123	q = READ_ONCE(a);
124	if (q % MAX) {
125		WRITE_ONCE(b, 1);
126		do_something();
127	} else {
128		WRITE_ONCE(b, 2);
129		do_something_else();
130	}
131
132If MAX is compile-time defined to be 1, then the compiler knows that
133(q % MAX) must be equal to zero, regardless of the value of "q".
134The compiler is therefore within its rights to transform the above code
135into the following:
136
137	q = READ_ONCE(a);
138	WRITE_ONCE(b, 2);
139	do_something_else();
140
141Given this transformation, the CPU is not required to respect the ordering
142between the load from variable "a" and the store to variable "b".  It is
143tempting to add a barrier(), but this does not help.  The conditional
144is gone, and the barrier won't bring it back.  Therefore, if you need
145to relying on control dependencies to produce this ordering, you should
146make sure that MAX is greater than one, perhaps as follows:
147
148	q = READ_ONCE(a);
149	BUILD_BUG_ON(MAX <= 1); /* Order load from a with store to b. */
150	if (q % MAX) {
151		WRITE_ONCE(b, 1);
152		do_something();
153	} else {
154		WRITE_ONCE(b, 2);
155		do_something_else();
156	}
157
158Please note once again that each leg of the "if" statement absolutely
159must store different values to "b".  As in previous examples, if the two
160values were identical, the compiler could pull this store outside of the
161"if" statement, destroying the control dependency's ordering properties.
162
163You must also be careful avoid relying too much on boolean short-circuit
164evaluation.  Consider this example:
165
166	q = READ_ONCE(a);
167	if (q || 1 > 0)
168		WRITE_ONCE(b, 1);
169
170Because the first condition cannot fault and the second condition is
171always true, the compiler can transform this example as follows, again
172destroying the control dependency's ordering:
173
174	q = READ_ONCE(a);
175	WRITE_ONCE(b, 1);
176
177This is yet another example showing the importance of preventing the
178compiler from out-guessing your code.  Again, although READ_ONCE() really
179does force the compiler to emit code for a given load, the compiler is
180within its rights to discard the loaded value.
181
182In addition, control dependencies apply only to the then-clause and
183else-clause of the "if" statement in question.  In particular, they do
184not necessarily order the code following the entire "if" statement:
185
186	q = READ_ONCE(a);
187	if (q) {
188		WRITE_ONCE(b, 1);
189	} else {
190		WRITE_ONCE(b, 2);
191	}
192	WRITE_ONCE(c, 1);  /* BUG: No ordering against the read from "a". */
193
194It is tempting to argue that there in fact is ordering because the
195compiler cannot reorder volatile accesses and also cannot reorder
196the writes to "b" with the condition.  Unfortunately for this line
197of reasoning, the compiler might compile the two writes to "b" as
198conditional-move instructions, as in this fanciful pseudo-assembly
199language:
200
201	ld r1,a
202	cmp r1,$0
203	cmov,ne r4,$1
204	cmov,eq r4,$2
205	st r4,b
206	st $1,c
207
208The control dependencies would then extend only to the pair of cmov
209instructions and the store depending on them.  This means that a weakly
210ordered CPU would have no dependency of any sort between the load from
211"a" and the store to "c".  In short, control dependencies provide ordering
212only to the stores in the then-clause and else-clause of the "if" statement
213in question (including functions invoked by those two clauses), and not
214to code following that "if" statement.
215
216
217In summary:
218
219  (*) Control dependencies can order prior loads against later stores.
220      However, they do *not* guarantee any other sort of ordering:
221      Not prior loads against later loads, nor prior stores against
222      later anything.  If you need these other forms of ordering, use
223      smp_load_acquire(), smp_store_release(), or, in the case of prior
224      stores and later loads, smp_mb().
225
226  (*) If both legs of the "if" statement contain identical stores to
227      the same variable, then you must explicitly order those stores,
228      either by preceding both of them with smp_mb() or by using
229      smp_store_release().  Please note that it is *not* sufficient to use
230      barrier() at beginning and end of each leg of the "if" statement
231      because, as shown by the example above, optimizing compilers can
232      destroy the control dependency while respecting the letter of the
233      barrier() law.
234
235  (*) Control dependencies require at least one run-time conditional
236      between the prior load and the subsequent store, and this
237      conditional must involve the prior load.  If the compiler is able
238      to optimize the conditional away, it will have also optimized
239      away the ordering.  Careful use of READ_ONCE() and WRITE_ONCE()
240      can help to preserve the needed conditional.
241
242  (*) Control dependencies require that the compiler avoid reordering the
243      dependency into nonexistence.  Careful use of READ_ONCE() or
244      atomic{,64}_read() can help to preserve your control dependency.
245
246  (*) Control dependencies apply only to the then-clause and else-clause
247      of the "if" statement containing the control dependency, including
248      any functions that these two clauses call.  Control dependencies
249      do *not* apply to code beyond the end of that "if" statement.
250
251  (*) Control dependencies pair normally with other types of barriers.
252
253  (*) Control dependencies do *not* provide multicopy atomicity.  If you
254      need all the CPUs to agree on the ordering of a given store against
255      all other accesses, use smp_mb().
256
257  (*) Compilers do not understand control dependencies.  It is therefore
258      your job to ensure that they do not break your code.
259