1PROPER CARE AND FEEDING OF RETURN VALUES FROM rcu_dereference() 2 3Most of the time, you can use values from rcu_dereference() or one of 4the similar primitives without worries. Dereferencing (prefix "*"), 5field selection ("->"), assignment ("="), address-of ("&"), addition and 6subtraction of constants, and casts all work quite naturally and safely. 7 8It is nevertheless possible to get into trouble with other operations. 9Follow these rules to keep your RCU code working properly: 10 11o You must use one of the rcu_dereference() family of primitives 12 to load an RCU-protected pointer, otherwise CONFIG_PROVE_RCU 13 will complain. Worse yet, your code can see random memory-corruption 14 bugs due to games that compilers and DEC Alpha can play. 15 Without one of the rcu_dereference() primitives, compilers 16 can reload the value, and won't your code have fun with two 17 different values for a single pointer! Without rcu_dereference(), 18 DEC Alpha can load a pointer, dereference that pointer, and 19 return data preceding initialization that preceded the store of 20 the pointer. 21 22 In addition, the volatile cast in rcu_dereference() prevents the 23 compiler from deducing the resulting pointer value. Please see 24 the section entitled "EXAMPLE WHERE THE COMPILER KNOWS TOO MUCH" 25 for an example where the compiler can in fact deduce the exact 26 value of the pointer, and thus cause misordering. 27 28o Do not use single-element RCU-protected arrays. The compiler 29 is within its right to assume that the value of an index into 30 such an array must necessarily evaluate to zero. The compiler 31 could then substitute the constant zero for the computation, so 32 that the array index no longer depended on the value returned 33 by rcu_dereference(). If the array index no longer depends 34 on rcu_dereference(), then both the compiler and the CPU 35 are within their rights to order the array access before the 36 rcu_dereference(), which can cause the array access to return 37 garbage. 38 39o Avoid cancellation when using the "+" and "-" infix arithmetic 40 operators. For example, for a given variable "x", avoid 41 "(x-x)". There are similar arithmetic pitfalls from other 42 arithmetic operatiors, such as "(x*0)", "(x/(x+1))" or "(x%1)". 43 The compiler is within its rights to substitute zero for all of 44 these expressions, so that subsequent accesses no longer depend 45 on the rcu_dereference(), again possibly resulting in bugs due 46 to misordering. 47 48 Of course, if "p" is a pointer from rcu_dereference(), and "a" 49 and "b" are integers that happen to be equal, the expression 50 "p+a-b" is safe because its value still necessarily depends on 51 the rcu_dereference(), thus maintaining proper ordering. 52 53o Avoid all-zero operands to the bitwise "&" operator, and 54 similarly avoid all-ones operands to the bitwise "|" operator. 55 If the compiler is able to deduce the value of such operands, 56 it is within its rights to substitute the corresponding constant 57 for the bitwise operation. Once again, this causes subsequent 58 accesses to no longer depend on the rcu_dereference(), causing 59 bugs due to misordering. 60 61 Please note that single-bit operands to bitwise "&" can also 62 be dangerous. At this point, the compiler knows that the 63 resulting value can only take on one of two possible values. 64 Therefore, a very small amount of additional information will 65 allow the compiler to deduce the exact value, which again can 66 result in misordering. 67 68o If you are using RCU to protect JITed functions, so that the 69 "()" function-invocation operator is applied to a value obtained 70 (directly or indirectly) from rcu_dereference(), you may need to 71 interact directly with the hardware to flush instruction caches. 72 This issue arises on some systems when a newly JITed function is 73 using the same memory that was used by an earlier JITed function. 74 75o Do not use the results from the boolean "&&" and "||" when 76 dereferencing. For example, the following (rather improbable) 77 code is buggy: 78 79 int a[2]; 80 int index; 81 int force_zero_index = 1; 82 83 ... 84 85 r1 = rcu_dereference(i1) 86 r2 = a[r1 && force_zero_index]; /* BUGGY!!! */ 87 88 The reason this is buggy is that "&&" and "||" are often compiled 89 using branches. While weak-memory machines such as ARM or PowerPC 90 do order stores after such branches, they can speculate loads, 91 which can result in misordering bugs. 92 93o Do not use the results from relational operators ("==", "!=", 94 ">", ">=", "<", or "<=") when dereferencing. For example, 95 the following (quite strange) code is buggy: 96 97 int a[2]; 98 int index; 99 int flip_index = 0; 100 101 ... 102 103 r1 = rcu_dereference(i1) 104 r2 = a[r1 != flip_index]; /* BUGGY!!! */ 105 106 As before, the reason this is buggy is that relational operators 107 are often compiled using branches. And as before, although 108 weak-memory machines such as ARM or PowerPC do order stores 109 after such branches, but can speculate loads, which can again 110 result in misordering bugs. 111 112o Be very careful about comparing pointers obtained from 113 rcu_dereference() against non-NULL values. As Linus Torvalds 114 explained, if the two pointers are equal, the compiler could 115 substitute the pointer you are comparing against for the pointer 116 obtained from rcu_dereference(). For example: 117 118 p = rcu_dereference(gp); 119 if (p == &default_struct) 120 do_default(p->a); 121 122 Because the compiler now knows that the value of "p" is exactly 123 the address of the variable "default_struct", it is free to 124 transform this code into the following: 125 126 p = rcu_dereference(gp); 127 if (p == &default_struct) 128 do_default(default_struct.a); 129 130 On ARM and Power hardware, the load from "default_struct.a" 131 can now be speculated, such that it might happen before the 132 rcu_dereference(). This could result in bugs due to misordering. 133 134 However, comparisons are OK in the following cases: 135 136 o The comparison was against the NULL pointer. If the 137 compiler knows that the pointer is NULL, you had better 138 not be dereferencing it anyway. If the comparison is 139 non-equal, the compiler is none the wiser. Therefore, 140 it is safe to compare pointers from rcu_dereference() 141 against NULL pointers. 142 143 o The pointer is never dereferenced after being compared. 144 Since there are no subsequent dereferences, the compiler 145 cannot use anything it learned from the comparison 146 to reorder the non-existent subsequent dereferences. 147 This sort of comparison occurs frequently when scanning 148 RCU-protected circular linked lists. 149 150 o The comparison is against a pointer that references memory 151 that was initialized "a long time ago." The reason 152 this is safe is that even if misordering occurs, the 153 misordering will not affect the accesses that follow 154 the comparison. So exactly how long ago is "a long 155 time ago"? Here are some possibilities: 156 157 o Compile time. 158 159 o Boot time. 160 161 o Module-init time for module code. 162 163 o Prior to kthread creation for kthread code. 164 165 o During some prior acquisition of the lock that 166 we now hold. 167 168 o Before mod_timer() time for a timer handler. 169 170 There are many other possibilities involving the Linux 171 kernel's wide array of primitives that cause code to 172 be invoked at a later time. 173 174 o The pointer being compared against also came from 175 rcu_dereference(). In this case, both pointers depend 176 on one rcu_dereference() or another, so you get proper 177 ordering either way. 178 179 That said, this situation can make certain RCU usage 180 bugs more likely to happen. Which can be a good thing, 181 at least if they happen during testing. An example 182 of such an RCU usage bug is shown in the section titled 183 "EXAMPLE OF AMPLIFIED RCU-USAGE BUG". 184 185 o All of the accesses following the comparison are stores, 186 so that a control dependency preserves the needed ordering. 187 That said, it is easy to get control dependencies wrong. 188 Please see the "CONTROL DEPENDENCIES" section of 189 Documentation/memory-barriers.txt for more details. 190 191 o The pointers are not equal -and- the compiler does 192 not have enough information to deduce the value of the 193 pointer. Note that the volatile cast in rcu_dereference() 194 will normally prevent the compiler from knowing too much. 195 196o Disable any value-speculation optimizations that your compiler 197 might provide, especially if you are making use of feedback-based 198 optimizations that take data collected from prior runs. Such 199 value-speculation optimizations reorder operations by design. 200 201 There is one exception to this rule: Value-speculation 202 optimizations that leverage the branch-prediction hardware are 203 safe on strongly ordered systems (such as x86), but not on weakly 204 ordered systems (such as ARM or Power). Choose your compiler 205 command-line options wisely! 206 207 208EXAMPLE OF AMPLIFIED RCU-USAGE BUG 209 210Because updaters can run concurrently with RCU readers, RCU readers can 211see stale and/or inconsistent values. If RCU readers need fresh or 212consistent values, which they sometimes do, they need to take proper 213precautions. To see this, consider the following code fragment: 214 215 struct foo { 216 int a; 217 int b; 218 int c; 219 }; 220 struct foo *gp1; 221 struct foo *gp2; 222 223 void updater(void) 224 { 225 struct foo *p; 226 227 p = kmalloc(...); 228 if (p == NULL) 229 deal_with_it(); 230 p->a = 42; /* Each field in its own cache line. */ 231 p->b = 43; 232 p->c = 44; 233 rcu_assign_pointer(gp1, p); 234 p->b = 143; 235 p->c = 144; 236 rcu_assign_pointer(gp2, p); 237 } 238 239 void reader(void) 240 { 241 struct foo *p; 242 struct foo *q; 243 int r1, r2; 244 245 p = rcu_dereference(gp2); 246 if (p == NULL) 247 return; 248 r1 = p->b; /* Guaranteed to get 143. */ 249 q = rcu_dereference(gp1); /* Guaranteed non-NULL. */ 250 if (p == q) { 251 /* The compiler decides that q->c is same as p->c. */ 252 r2 = p->c; /* Could get 44 on weakly order system. */ 253 } 254 do_something_with(r1, r2); 255 } 256 257You might be surprised that the outcome (r1 == 143 && r2 == 44) is possible, 258but you should not be. After all, the updater might have been invoked 259a second time between the time reader() loaded into "r1" and the time 260that it loaded into "r2". The fact that this same result can occur due 261to some reordering from the compiler and CPUs is beside the point. 262 263But suppose that the reader needs a consistent view? 264 265Then one approach is to use locking, for example, as follows: 266 267 struct foo { 268 int a; 269 int b; 270 int c; 271 spinlock_t lock; 272 }; 273 struct foo *gp1; 274 struct foo *gp2; 275 276 void updater(void) 277 { 278 struct foo *p; 279 280 p = kmalloc(...); 281 if (p == NULL) 282 deal_with_it(); 283 spin_lock(&p->lock); 284 p->a = 42; /* Each field in its own cache line. */ 285 p->b = 43; 286 p->c = 44; 287 spin_unlock(&p->lock); 288 rcu_assign_pointer(gp1, p); 289 spin_lock(&p->lock); 290 p->b = 143; 291 p->c = 144; 292 spin_unlock(&p->lock); 293 rcu_assign_pointer(gp2, p); 294 } 295 296 void reader(void) 297 { 298 struct foo *p; 299 struct foo *q; 300 int r1, r2; 301 302 p = rcu_dereference(gp2); 303 if (p == NULL) 304 return; 305 spin_lock(&p->lock); 306 r1 = p->b; /* Guaranteed to get 143. */ 307 q = rcu_dereference(gp1); /* Guaranteed non-NULL. */ 308 if (p == q) { 309 /* The compiler decides that q->c is same as p->c. */ 310 r2 = p->c; /* Locking guarantees r2 == 144. */ 311 } 312 spin_unlock(&p->lock); 313 do_something_with(r1, r2); 314 } 315 316As always, use the right tool for the job! 317 318 319EXAMPLE WHERE THE COMPILER KNOWS TOO MUCH 320 321If a pointer obtained from rcu_dereference() compares not-equal to some 322other pointer, the compiler normally has no clue what the value of the 323first pointer might be. This lack of knowledge prevents the compiler 324from carrying out optimizations that otherwise might destroy the ordering 325guarantees that RCU depends on. And the volatile cast in rcu_dereference() 326should prevent the compiler from guessing the value. 327 328But without rcu_dereference(), the compiler knows more than you might 329expect. Consider the following code fragment: 330 331 struct foo { 332 int a; 333 int b; 334 }; 335 static struct foo variable1; 336 static struct foo variable2; 337 static struct foo *gp = &variable1; 338 339 void updater(void) 340 { 341 initialize_foo(&variable2); 342 rcu_assign_pointer(gp, &variable2); 343 /* 344 * The above is the only store to gp in this translation unit, 345 * and the address of gp is not exported in any way. 346 */ 347 } 348 349 int reader(void) 350 { 351 struct foo *p; 352 353 p = gp; 354 barrier(); 355 if (p == &variable1) 356 return p->a; /* Must be variable1.a. */ 357 else 358 return p->b; /* Must be variable2.b. */ 359 } 360 361Because the compiler can see all stores to "gp", it knows that the only 362possible values of "gp" are "variable1" on the one hand and "variable2" 363on the other. The comparison in reader() therefore tells the compiler 364the exact value of "p" even in the not-equals case. This allows the 365compiler to make the return values independent of the load from "gp", 366in turn destroying the ordering between this load and the loads of the 367return values. This can result in "p->b" returning pre-initialization 368garbage values. 369 370In short, rcu_dereference() is -not- optional when you are going to 371dereference the resulting pointer. 372