Based on kernel version 4.16.1. Page generated on 2018-04-09 11:53 EST.
1 PROPER CARE AND FEEDING OF RETURN VALUES FROM rcu_dereference() 2 3 Most of the time, you can use values from rcu_dereference() or one of 4 the similar primitives without worries. Dereferencing (prefix "*"), 5 field selection ("->"), assignment ("="), address-of ("&"), addition and 6 subtraction of constants, and casts all work quite naturally and safely. 7 8 It is nevertheless possible to get into trouble with other operations. 9 Follow these rules to keep your RCU code working properly: 10 11 o 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 28 o 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 45 o 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 57 o 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 64 o 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 84 o 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(). 126 127 o The comparison is against a pointer that references memory 128 that was initialized "a long time ago." The reason 129 this is safe is that even if misordering occurs, the 130 misordering will not affect the accesses that follow 131 the comparison. So exactly how long ago is "a long 132 time ago"? Here are some possibilities: 133 134 o Compile time. 135 136 o Boot time. 137 138 o Module-init time for module code. 139 140 o Prior to kthread creation for kthread code. 141 142 o During some prior acquisition of the lock that 143 we now hold. 144 145 o Before mod_timer() time for a timer handler. 146 147 There are many other possibilities involving the Linux 148 kernel's wide array of primitives that cause code to 149 be invoked at a later time. 150 151 o The pointer being compared against also came from 152 rcu_dereference(). In this case, both pointers depend 153 on one rcu_dereference() or another, so you get proper 154 ordering either way. 155 156 That said, this situation can make certain RCU usage 157 bugs more likely to happen. Which can be a good thing, 158 at least if they happen during testing. An example 159 of such an RCU usage bug is shown in the section titled 160 "EXAMPLE OF AMPLIFIED RCU-USAGE BUG". 161 162 o All of the accesses following the comparison are stores, 163 so that a control dependency preserves the needed ordering. 164 That said, it is easy to get control dependencies wrong. 165 Please see the "CONTROL DEPENDENCIES" section of 166 Documentation/memory-barriers.txt for more details. 167 168 o The pointers are not equal -and- the compiler does 169 not have enough information to deduce the value of the 170 pointer. Note that the volatile cast in rcu_dereference() 171 will normally prevent the compiler from knowing too much. 172 173 However, please note that if the compiler knows that the 174 pointer takes on only one of two values, a not-equal 175 comparison will provide exactly the information that the 176 compiler needs to deduce the value of the pointer. 177 178 o Disable any value-speculation optimizations that your compiler 179 might provide, especially if you are making use of feedback-based 180 optimizations that take data collected from prior runs. Such 181 value-speculation optimizations reorder operations by design. 182 183 There is one exception to this rule: Value-speculation 184 optimizations that leverage the branch-prediction hardware are 185 safe on strongly ordered systems (such as x86), but not on weakly 186 ordered systems (such as ARM or Power). Choose your compiler 187 command-line options wisely! 188 189 190 EXAMPLE OF AMPLIFIED RCU-USAGE BUG 191 192 Because updaters can run concurrently with RCU readers, RCU readers can 193 see stale and/or inconsistent values. If RCU readers need fresh or 194 consistent values, which they sometimes do, they need to take proper 195 precautions. To see this, consider the following code fragment: 196 197 struct foo { 198 int a; 199 int b; 200 int c; 201 }; 202 struct foo *gp1; 203 struct foo *gp2; 204 205 void updater(void) 206 { 207 struct foo *p; 208 209 p = kmalloc(...); 210 if (p == NULL) 211 deal_with_it(); 212 p->a = 42; /* Each field in its own cache line. */ 213 p->b = 43; 214 p->c = 44; 215 rcu_assign_pointer(gp1, p); 216 p->b = 143; 217 p->c = 144; 218 rcu_assign_pointer(gp2, p); 219 } 220 221 void reader(void) 222 { 223 struct foo *p; 224 struct foo *q; 225 int r1, r2; 226 227 p = rcu_dereference(gp2); 228 if (p == NULL) 229 return; 230 r1 = p->b; /* Guaranteed to get 143. */ 231 q = rcu_dereference(gp1); /* Guaranteed non-NULL. */ 232 if (p == q) { 233 /* The compiler decides that q->c is same as p->c. */ 234 r2 = p->c; /* Could get 44 on weakly order system. */ 235 } 236 do_something_with(r1, r2); 237 } 238 239 You might be surprised that the outcome (r1 == 143 && r2 == 44) is possible, 240 but you should not be. After all, the updater might have been invoked 241 a second time between the time reader() loaded into "r1" and the time 242 that it loaded into "r2". The fact that this same result can occur due 243 to some reordering from the compiler and CPUs is beside the point. 244 245 But suppose that the reader needs a consistent view? 246 247 Then one approach is to use locking, for example, as follows: 248 249 struct foo { 250 int a; 251 int b; 252 int c; 253 spinlock_t lock; 254 }; 255 struct foo *gp1; 256 struct foo *gp2; 257 258 void updater(void) 259 { 260 struct foo *p; 261 262 p = kmalloc(...); 263 if (p == NULL) 264 deal_with_it(); 265 spin_lock(&p->lock); 266 p->a = 42; /* Each field in its own cache line. */ 267 p->b = 43; 268 p->c = 44; 269 spin_unlock(&p->lock); 270 rcu_assign_pointer(gp1, p); 271 spin_lock(&p->lock); 272 p->b = 143; 273 p->c = 144; 274 spin_unlock(&p->lock); 275 rcu_assign_pointer(gp2, p); 276 } 277 278 void reader(void) 279 { 280 struct foo *p; 281 struct foo *q; 282 int r1, r2; 283 284 p = rcu_dereference(gp2); 285 if (p == NULL) 286 return; 287 spin_lock(&p->lock); 288 r1 = p->b; /* Guaranteed to get 143. */ 289 q = rcu_dereference(gp1); /* Guaranteed non-NULL. */ 290 if (p == q) { 291 /* The compiler decides that q->c is same as p->c. */ 292 r2 = p->c; /* Locking guarantees r2 == 144. */ 293 } 294 spin_unlock(&p->lock); 295 do_something_with(r1, r2); 296 } 297 298 As always, use the right tool for the job! 299 300 301 EXAMPLE WHERE THE COMPILER KNOWS TOO MUCH 302 303 If a pointer obtained from rcu_dereference() compares not-equal to some 304 other pointer, the compiler normally has no clue what the value of the 305 first pointer might be. This lack of knowledge prevents the compiler 306 from carrying out optimizations that otherwise might destroy the ordering 307 guarantees that RCU depends on. And the volatile cast in rcu_dereference() 308 should prevent the compiler from guessing the value. 309 310 But without rcu_dereference(), the compiler knows more than you might 311 expect. Consider the following code fragment: 312 313 struct foo { 314 int a; 315 int b; 316 }; 317 static struct foo variable1; 318 static struct foo variable2; 319 static struct foo *gp = &variable1; 320 321 void updater(void) 322 { 323 initialize_foo(&variable2); 324 rcu_assign_pointer(gp, &variable2); 325 /* 326 * The above is the only store to gp in this translation unit, 327 * and the address of gp is not exported in any way. 328 */ 329 } 330 331 int reader(void) 332 { 333 struct foo *p; 334 335 p = gp; 336 barrier(); 337 if (p == &variable1) 338 return p->a; /* Must be variable1.a. */ 339 else 340 return p->b; /* Must be variable2.b. */ 341 } 342 343 Because the compiler can see all stores to "gp", it knows that the only 344 possible values of "gp" are "variable1" on the one hand and "variable2" 345 on the other. The comparison in reader() therefore tells the compiler 346 the exact value of "p" even in the not-equals case. This allows the 347 compiler to make the return values independent of the load from "gp", 348 in turn destroying the ordering between this load and the loads of the 349 return values. This can result in "p->b" returning pre-initialization 350 garbage values. 351 352 In short, rcu_dereference() is -not- optional when you are going to 353 dereference the resulting pointer.