1 CONTROL DEPENDENCIES
2 ====================
3
4 A major difficulty with control dependencies is that current compilers
5 do not support them. One purpose of this document is therefore to
6 help you prevent your compiler from breaking your code. However,
7 control dependencies also pose other challenges, which leads to the
8 second purpose of this document, namely to help you to avoid breaking
9 your own code, even in the absence of help from your compiler.
10
11 One such challenge is that control dependencies order only later stores.
12 Therefore, a load-load control dependency will not preserve ordering
13 unless 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
19 This is not guaranteed to provide any ordering because some types of CPUs
20 are permitted to predict the result of the load from "b". This prediction
21 can cause other CPUs to see this load as having happened before the load
22 from "a". This means that an explicit read barrier is required, for example
23 as follows:
24
25 q = READ_ONCE(a);
26 if (q) {
27 smp_rmb();
28 p = READ_ONCE(b);
29 }
30
31 However, stores are not speculated. This means that ordering is
32 (usually) guaranteed for load-store control dependencies, as in the
33 following example:
34
35 q = READ_ONCE(a);
36 if (q)
37 WRITE_ONCE(b, 1);
38
39 Control dependencies can pair with each other and with other types
40 of ordering. But please note that neither the READ_ONCE() nor the
41 WRITE_ONCE() are optional. Without the READ_ONCE(), the compiler might
42 fuse the load from "a" with other loads. Without the WRITE_ONCE(),
43 the compiler might fuse the store to "b" with other stores. Worse yet,
44 the compiler might convert the store into a load and a check followed
45 by a store, and this compiler-generated load would not be ordered by
46 the control dependency.
47
48 Furthermore, 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
50 the original example by eliminating the "if" statement as follows:
51
52 q = a;
53 b = 1; /* BUG: Compiler and CPU can both reorder!!! */
54
55 So don't leave out either the READ_ONCE() or the WRITE_ONCE().
56 In particular, although READ_ONCE() does force the compiler to emit a
57 load, it does *not* force the compiler to actually use the loaded value.
58
59 It is tempting to try use control dependencies to enforce ordering on
60 identical 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
73 Unfortunately, current compilers will transform this as follows at high
74 optimization 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
87 Now 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
89 conditional is absolutely required, and must be present in the final
90 assembly code, after all of the compiler and link-time optimizations
91 have been applied. Therefore, if you need ordering in this example,
92 you 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
103 Without explicit memory ordering, control-dependency-based ordering is
104 guaranteed 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
115 The initial READ_ONCE() is still required to prevent the compiler from
116 knowing too much about the value of "a".
117
118 But please note that you need to be careful what you do with the local
119 variable "q", otherwise the compiler might be able to guess the value
120 and again remove the conditional branch that is absolutely required to
121 preserve 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
132 If 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".
134 The compiler is therefore within its rights to transform the above code
135 into the following:
136
137 q = READ_ONCE(a);
138 WRITE_ONCE(b, 2);
139 do_something_else();
140
141 Given this transformation, the CPU is not required to respect the ordering
142 between the load from variable "a" and the store to variable "b". It is
143 tempting to add a barrier(), but this does not help. The conditional
144 is gone, and the barrier won't bring it back. Therefore, if you need
145 to relying on control dependencies to produce this ordering, you should
146 make 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
158 Please note once again that each leg of the "if" statement absolutely
159 must store different values to "b". As in previous examples, if the two
160 values were identical, the compiler could pull this store outside of the
161 "if" statement, destroying the control dependency's ordering properties.
162
163 You must also be careful avoid relying too much on boolean short-circuit
164 evaluation. Consider this example:
165
166 q = READ_ONCE(a);
167 if (q || 1 > 0)
168 WRITE_ONCE(b, 1);
169
170 Because the first condition cannot fault and the second condition is
171 always true, the compiler can transform this example as follows, again
172 destroying the control dependency's ordering:
173
174 q = READ_ONCE(a);
175 WRITE_ONCE(b, 1);
176
177 This is yet another example showing the importance of preventing the
178 compiler from out-guessing your code. Again, although READ_ONCE() really
179 does force the compiler to emit code for a given load, the compiler is
180 within its rights to discard the loaded value.
181
182 In addition, control dependencies apply only to the then-clause and
183 else-clause of the "if" statement in question. In particular, they do
184 not 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
194 It is tempting to argue that there in fact is ordering because the
195 compiler cannot reorder volatile accesses and also cannot reorder
196 the writes to "b" with the condition. Unfortunately for this line
197 of reasoning, the compiler might compile the two writes to "b" as
198 conditional-move instructions, as in this fanciful pseudo-assembly
199 language:
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
208 The control dependencies would then extend only to the pair of cmov
209 instructions and the store depending on them. This means that a weakly
210 ordered 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
212 only to the stores in the then-clause and else-clause of the "if" statement
213 in question (including functions invoked by those two clauses), and not
214 to code following that "if" statement.
215
216
217 In 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.
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.