Commit | Line | Data |
---|---|---|
b4c5bf35 PM |
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 | ||
8a597d63 PM |
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 | ||
b4c5bf35 PM |
45 | o Avoid cancellation when using the "+" and "-" infix arithmetic |
46 | operators. For example, for a given variable "x", avoid | |
8a597d63 PM |
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. | |
b4c5bf35 PM |
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 | ||
b4c5bf35 PM |
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. | |
b4c5bf35 PM |
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 | ||
cf9fbf80 PM |
68 | int *p; |
69 | int *q; | |
b4c5bf35 PM |
70 | |
71 | ... | |
72 | ||
cf9fbf80 PM |
73 | p = rcu_dereference(gp) |
74 | q = &global_q; | |
75 | q += p > &oom_p; | |
76 | r1 = *q; /* BUGGY!!! */ | |
b4c5bf35 PM |
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 | ||
93728af0 MK |
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 | |
9ad3c143 | 125 | of rcu_dereference(). |
93728af0 | 126 | |
b4c5bf35 PM |
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 | ||
ee7c29be PM |
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 | ||
b4c5bf35 PM |
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. |