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 | ||
28 | o 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 | ||
39 | o 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 | ||
53 | o 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 | ||
68 | o 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 | ||
75 | o 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 | ||
93 | o 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 | ||
112 | o 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 | ||
196 | o 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 | ||
208 | EXAMPLE OF AMPLIFIED RCU-USAGE BUG | |
209 | ||
210 | Because updaters can run concurrently with RCU readers, RCU readers can | |
211 | see stale and/or inconsistent values. If RCU readers need fresh or | |
212 | consistent values, which they sometimes do, they need to take proper | |
213 | precautions. 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 | ||
257 | You might be surprised that the outcome (r1 == 143 && r2 == 44) is possible, | |
258 | but you should not be. After all, the updater might have been invoked | |
259 | a second time between the time reader() loaded into "r1" and the time | |
260 | that it loaded into "r2". The fact that this same result can occur due | |
261 | to some reordering from the compiler and CPUs is beside the point. | |
262 | ||
263 | But suppose that the reader needs a consistent view? | |
264 | ||
265 | Then 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 | ||
316 | As always, use the right tool for the job! | |
317 | ||
318 | ||
319 | EXAMPLE WHERE THE COMPILER KNOWS TOO MUCH | |
320 | ||
321 | If a pointer obtained from rcu_dereference() compares not-equal to some | |
322 | other pointer, the compiler normally has no clue what the value of the | |
323 | first pointer might be. This lack of knowledge prevents the compiler | |
324 | from carrying out optimizations that otherwise might destroy the ordering | |
325 | guarantees that RCU depends on. And the volatile cast in rcu_dereference() | |
326 | should prevent the compiler from guessing the value. | |
327 | ||
328 | But without rcu_dereference(), the compiler knows more than you might | |
329 | expect. 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 | ||
361 | Because the compiler can see all stores to "gp", it knows that the only | |
362 | possible values of "gp" are "variable1" on the one hand and "variable2" | |
363 | on the other. The comparison in reader() therefore tells the compiler | |
364 | the exact value of "p" even in the not-equals case. This allows the | |
365 | compiler to make the return values independent of the load from "gp", | |
366 | in turn destroying the ordering between this load and the loads of the | |
367 | return values. This can result in "p->b" returning pre-initialization | |
368 | garbage values. | |
369 | ||
370 | In short, rcu_dereference() is -not- optional when you are going to | |
371 | dereference the resulting pointer. |