259 lines · plain
1CONTROL DEPENDENCIES2====================3 4A major difficulty with control dependencies is that current compilers5do not support them. One purpose of this document is therefore to6help you prevent your compiler from breaking your code. However,7control dependencies also pose other challenges, which leads to the8second purpose of this document, namely to help you to avoid breaking9your 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 ordering13unless 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 CPUs20are permitted to predict the result of the load from "b". This prediction21can cause other CPUs to see this load as having happened before the load22from "a". This means that an explicit read barrier is required, for example23as 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 is32(usually) guaranteed for load-store control dependencies, as in the33following 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 types40of ordering. But please note that neither the READ_ONCE() nor the41WRITE_ONCE() are optional. Without the READ_ONCE(), the compiler might42fuse 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 followed45by a store, and this compiler-generated load would not be ordered by46the control dependency.47 48Furthermore, if the compiler is able to prove that the value of variable49"a" is always non-zero, it would be well within its rights to optimize50the 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 a57load, it does *not* force the compiler to actually use the loaded value.58 59It is tempting to try use control dependencies to enforce ordering on60identical 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 high74optimization 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 to88"b", which means that the CPU is within its rights to reorder them: The89conditional is absolutely required, and must be present in the final90assembly code, after all of the compiler and link-time optimizations91have 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 is104guaranteed 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 from116knowing too much about the value of "a".117 118But please note that you need to be careful what you do with the local119variable "q", otherwise the compiler might be able to guess the value120and again remove the conditional branch that is absolutely required to121preserve 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 that133(q % MAX) must be equal to zero, regardless of the value of "q".134The compiler is therefore within its rights to transform the above code135into 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 ordering142between the load from variable "a" and the store to variable "b". It is143tempting to add a barrier(), but this does not help. The conditional144is gone, and the barrier won't bring it back. Therefore, if you need145to relying on control dependencies to produce this ordering, you should146make 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 absolutely159must store different values to "b". As in previous examples, if the two160values were identical, the compiler could pull this store outside of the161"if" statement, destroying the control dependency's ordering properties.162 163You must also be careful avoid relying too much on boolean short-circuit164evaluation. 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 is171always true, the compiler can transform this example as follows, again172destroying 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 the178compiler from out-guessing your code. Again, although READ_ONCE() really179does force the compiler to emit code for a given load, the compiler is180within its rights to discard the loaded value.181 182In addition, control dependencies apply only to the then-clause and183else-clause of the "if" statement in question. In particular, they do184not 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 the195compiler cannot reorder volatile accesses and also cannot reorder196the writes to "b" with the condition. Unfortunately for this line197of reasoning, the compiler might compile the two writes to "b" as198conditional-move instructions, as in this fanciful pseudo-assembly199language:200 201 ld r1,a202 cmp r1,$0203 cmov,ne r4,$1204 cmov,eq r4,$2205 st r4,b206 st $1,c207 208The control dependencies would then extend only to the pair of cmov209instructions and the store depending on them. This means that a weakly210ordered CPU would have no dependency of any sort between the load from211"a" and the store to "c". In short, control dependencies provide ordering212only to the stores in the then-clause and else-clause of the "if" statement213in question (including functions invoked by those two clauses), and not214to 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 against222 later anything. If you need these other forms of ordering, use223 smp_load_acquire(), smp_store_release(), or, in the case of prior224 stores and later loads, smp_mb().225 226 (*) If both legs of the "if" statement contain identical stores to227 the same variable, then you must explicitly order those stores,228 either by preceding both of them with smp_mb() or by using229 smp_store_release(). Please note that it is *not* sufficient to use230 barrier() at beginning and end of each leg of the "if" statement231 because, as shown by the example above, optimizing compilers can232 destroy the control dependency while respecting the letter of the233 barrier() law.234 235 (*) Control dependencies require at least one run-time conditional236 between the prior load and the subsequent store, and this237 conditional must involve the prior load. If the compiler is able238 to optimize the conditional away, it will have also optimized239 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 the243 dependency into nonexistence. Careful use of READ_ONCE() or244 atomic{,64}_read() can help to preserve your control dependency.245 246 (*) Control dependencies apply only to the then-clause and else-clause247 of the "if" statement containing the control dependency, including248 any functions that these two clauses call. Control dependencies249 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 you254 need all the CPUs to agree on the ordering of a given store against255 all other accesses, use smp_mb().256 257 (*) Compilers do not understand control dependencies. It is therefore258 your job to ensure that they do not break your code.259