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