rcu_dereference.rst 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463
  1. .. _rcu_dereference_doc:
  2. PROPER CARE AND FEEDING OF RETURN VALUES FROM rcu_dereference()
  3. ===============================================================
  4. Most of the time, you can use values from rcu_dereference() or one of
  5. the similar primitives without worries. Dereferencing (prefix "*"),
  6. field selection ("->"), assignment ("="), address-of ("&"), addition and
  7. subtraction of constants, and casts all work quite naturally and safely.
  8. It is nevertheless possible to get into trouble with other operations.
  9. Follow these rules to keep your RCU code working properly:
  10. - You must use one of the rcu_dereference() family of primitives
  11. to load an RCU-protected pointer, otherwise CONFIG_PROVE_RCU
  12. will complain. Worse yet, your code can see random memory-corruption
  13. bugs due to games that compilers and DEC Alpha can play.
  14. Without one of the rcu_dereference() primitives, compilers
  15. can reload the value, and won't your code have fun with two
  16. different values for a single pointer! Without rcu_dereference(),
  17. DEC Alpha can load a pointer, dereference that pointer, and
  18. return data preceding initialization that preceded the store of
  19. the pointer.
  20. In addition, the volatile cast in rcu_dereference() prevents the
  21. compiler from deducing the resulting pointer value. Please see
  22. the section entitled "EXAMPLE WHERE THE COMPILER KNOWS TOO MUCH"
  23. for an example where the compiler can in fact deduce the exact
  24. value of the pointer, and thus cause misordering.
  25. - You are only permitted to use rcu_dereference on pointer values.
  26. The compiler simply knows too much about integral values to
  27. trust it to carry dependencies through integer operations.
  28. There are a very few exceptions, namely that you can temporarily
  29. cast the pointer to uintptr_t in order to:
  30. - Set bits and clear bits down in the must-be-zero low-order
  31. bits of that pointer. This clearly means that the pointer
  32. must have alignment constraints, for example, this does
  33. -not- work in general for char* pointers.
  34. - XOR bits to translate pointers, as is done in some
  35. classic buddy-allocator algorithms.
  36. It is important to cast the value back to pointer before
  37. doing much of anything else with it.
  38. - Avoid cancellation when using the "+" and "-" infix arithmetic
  39. operators. For example, for a given variable "x", avoid
  40. "(x-(uintptr_t)x)" for char* pointers. The compiler is within its
  41. rights to substitute zero for this sort of expression, so that
  42. subsequent accesses no longer depend on the rcu_dereference(),
  43. again possibly resulting in bugs due to misordering.
  44. Of course, if "p" is a pointer from rcu_dereference(), and "a"
  45. and "b" are integers that happen to be equal, the expression
  46. "p+a-b" is safe because its value still necessarily depends on
  47. the rcu_dereference(), thus maintaining proper ordering.
  48. - If you are using RCU to protect JITed functions, so that the
  49. "()" function-invocation operator is applied to a value obtained
  50. (directly or indirectly) from rcu_dereference(), you may need to
  51. interact directly with the hardware to flush instruction caches.
  52. This issue arises on some systems when a newly JITed function is
  53. using the same memory that was used by an earlier JITed function.
  54. - Do not use the results from relational operators ("==", "!=",
  55. ">", ">=", "<", or "<=") when dereferencing. For example,
  56. the following (quite strange) code is buggy::
  57. int *p;
  58. int *q;
  59. ...
  60. p = rcu_dereference(gp)
  61. q = &global_q;
  62. q += p > &oom_p;
  63. r1 = *q; /* BUGGY!!! */
  64. As before, the reason this is buggy is that relational operators
  65. are often compiled using branches. And as before, although
  66. weak-memory machines such as ARM or PowerPC do order stores
  67. after such branches, but can speculate loads, which can again
  68. result in misordering bugs.
  69. - Be very careful about comparing pointers obtained from
  70. rcu_dereference() against non-NULL values. As Linus Torvalds
  71. explained, if the two pointers are equal, the compiler could
  72. substitute the pointer you are comparing against for the pointer
  73. obtained from rcu_dereference(). For example::
  74. p = rcu_dereference(gp);
  75. if (p == &default_struct)
  76. do_default(p->a);
  77. Because the compiler now knows that the value of "p" is exactly
  78. the address of the variable "default_struct", it is free to
  79. transform this code into the following::
  80. p = rcu_dereference(gp);
  81. if (p == &default_struct)
  82. do_default(default_struct.a);
  83. On ARM and Power hardware, the load from "default_struct.a"
  84. can now be speculated, such that it might happen before the
  85. rcu_dereference(). This could result in bugs due to misordering.
  86. However, comparisons are OK in the following cases:
  87. - The comparison was against the NULL pointer. If the
  88. compiler knows that the pointer is NULL, you had better
  89. not be dereferencing it anyway. If the comparison is
  90. non-equal, the compiler is none the wiser. Therefore,
  91. it is safe to compare pointers from rcu_dereference()
  92. against NULL pointers.
  93. - The pointer is never dereferenced after being compared.
  94. Since there are no subsequent dereferences, the compiler
  95. cannot use anything it learned from the comparison
  96. to reorder the non-existent subsequent dereferences.
  97. This sort of comparison occurs frequently when scanning
  98. RCU-protected circular linked lists.
  99. Note that if checks for being within an RCU read-side
  100. critical section are not required and the pointer is never
  101. dereferenced, rcu_access_pointer() should be used in place
  102. of rcu_dereference().
  103. - The comparison is against a pointer that references memory
  104. that was initialized "a long time ago." The reason
  105. this is safe is that even if misordering occurs, the
  106. misordering will not affect the accesses that follow
  107. the comparison. So exactly how long ago is "a long
  108. time ago"? Here are some possibilities:
  109. - Compile time.
  110. - Boot time.
  111. - Module-init time for module code.
  112. - Prior to kthread creation for kthread code.
  113. - During some prior acquisition of the lock that
  114. we now hold.
  115. - Before mod_timer() time for a timer handler.
  116. There are many other possibilities involving the Linux
  117. kernel's wide array of primitives that cause code to
  118. be invoked at a later time.
  119. - The pointer being compared against also came from
  120. rcu_dereference(). In this case, both pointers depend
  121. on one rcu_dereference() or another, so you get proper
  122. ordering either way.
  123. That said, this situation can make certain RCU usage
  124. bugs more likely to happen. Which can be a good thing,
  125. at least if they happen during testing. An example
  126. of such an RCU usage bug is shown in the section titled
  127. "EXAMPLE OF AMPLIFIED RCU-USAGE BUG".
  128. - All of the accesses following the comparison are stores,
  129. so that a control dependency preserves the needed ordering.
  130. That said, it is easy to get control dependencies wrong.
  131. Please see the "CONTROL DEPENDENCIES" section of
  132. Documentation/memory-barriers.txt for more details.
  133. - The pointers are not equal -and- the compiler does
  134. not have enough information to deduce the value of the
  135. pointer. Note that the volatile cast in rcu_dereference()
  136. will normally prevent the compiler from knowing too much.
  137. However, please note that if the compiler knows that the
  138. pointer takes on only one of two values, a not-equal
  139. comparison will provide exactly the information that the
  140. compiler needs to deduce the value of the pointer.
  141. - Disable any value-speculation optimizations that your compiler
  142. might provide, especially if you are making use of feedback-based
  143. optimizations that take data collected from prior runs. Such
  144. value-speculation optimizations reorder operations by design.
  145. There is one exception to this rule: Value-speculation
  146. optimizations that leverage the branch-prediction hardware are
  147. safe on strongly ordered systems (such as x86), but not on weakly
  148. ordered systems (such as ARM or Power). Choose your compiler
  149. command-line options wisely!
  150. EXAMPLE OF AMPLIFIED RCU-USAGE BUG
  151. ----------------------------------
  152. Because updaters can run concurrently with RCU readers, RCU readers can
  153. see stale and/or inconsistent values. If RCU readers need fresh or
  154. consistent values, which they sometimes do, they need to take proper
  155. precautions. To see this, consider the following code fragment::
  156. struct foo {
  157. int a;
  158. int b;
  159. int c;
  160. };
  161. struct foo *gp1;
  162. struct foo *gp2;
  163. void updater(void)
  164. {
  165. struct foo *p;
  166. p = kmalloc(...);
  167. if (p == NULL)
  168. deal_with_it();
  169. p->a = 42; /* Each field in its own cache line. */
  170. p->b = 43;
  171. p->c = 44;
  172. rcu_assign_pointer(gp1, p);
  173. p->b = 143;
  174. p->c = 144;
  175. rcu_assign_pointer(gp2, p);
  176. }
  177. void reader(void)
  178. {
  179. struct foo *p;
  180. struct foo *q;
  181. int r1, r2;
  182. p = rcu_dereference(gp2);
  183. if (p == NULL)
  184. return;
  185. r1 = p->b; /* Guaranteed to get 143. */
  186. q = rcu_dereference(gp1); /* Guaranteed non-NULL. */
  187. if (p == q) {
  188. /* The compiler decides that q->c is same as p->c. */
  189. r2 = p->c; /* Could get 44 on weakly order system. */
  190. }
  191. do_something_with(r1, r2);
  192. }
  193. You might be surprised that the outcome (r1 == 143 && r2 == 44) is possible,
  194. but you should not be. After all, the updater might have been invoked
  195. a second time between the time reader() loaded into "r1" and the time
  196. that it loaded into "r2". The fact that this same result can occur due
  197. to some reordering from the compiler and CPUs is beside the point.
  198. But suppose that the reader needs a consistent view?
  199. Then one approach is to use locking, for example, as follows::
  200. struct foo {
  201. int a;
  202. int b;
  203. int c;
  204. spinlock_t lock;
  205. };
  206. struct foo *gp1;
  207. struct foo *gp2;
  208. void updater(void)
  209. {
  210. struct foo *p;
  211. p = kmalloc(...);
  212. if (p == NULL)
  213. deal_with_it();
  214. spin_lock(&p->lock);
  215. p->a = 42; /* Each field in its own cache line. */
  216. p->b = 43;
  217. p->c = 44;
  218. spin_unlock(&p->lock);
  219. rcu_assign_pointer(gp1, p);
  220. spin_lock(&p->lock);
  221. p->b = 143;
  222. p->c = 144;
  223. spin_unlock(&p->lock);
  224. rcu_assign_pointer(gp2, p);
  225. }
  226. void reader(void)
  227. {
  228. struct foo *p;
  229. struct foo *q;
  230. int r1, r2;
  231. p = rcu_dereference(gp2);
  232. if (p == NULL)
  233. return;
  234. spin_lock(&p->lock);
  235. r1 = p->b; /* Guaranteed to get 143. */
  236. q = rcu_dereference(gp1); /* Guaranteed non-NULL. */
  237. if (p == q) {
  238. /* The compiler decides that q->c is same as p->c. */
  239. r2 = p->c; /* Locking guarantees r2 == 144. */
  240. }
  241. spin_unlock(&p->lock);
  242. do_something_with(r1, r2);
  243. }
  244. As always, use the right tool for the job!
  245. EXAMPLE WHERE THE COMPILER KNOWS TOO MUCH
  246. -----------------------------------------
  247. If a pointer obtained from rcu_dereference() compares not-equal to some
  248. other pointer, the compiler normally has no clue what the value of the
  249. first pointer might be. This lack of knowledge prevents the compiler
  250. from carrying out optimizations that otherwise might destroy the ordering
  251. guarantees that RCU depends on. And the volatile cast in rcu_dereference()
  252. should prevent the compiler from guessing the value.
  253. But without rcu_dereference(), the compiler knows more than you might
  254. expect. Consider the following code fragment::
  255. struct foo {
  256. int a;
  257. int b;
  258. };
  259. static struct foo variable1;
  260. static struct foo variable2;
  261. static struct foo *gp = &variable1;
  262. void updater(void)
  263. {
  264. initialize_foo(&variable2);
  265. rcu_assign_pointer(gp, &variable2);
  266. /*
  267. * The above is the only store to gp in this translation unit,
  268. * and the address of gp is not exported in any way.
  269. */
  270. }
  271. int reader(void)
  272. {
  273. struct foo *p;
  274. p = gp;
  275. barrier();
  276. if (p == &variable1)
  277. return p->a; /* Must be variable1.a. */
  278. else
  279. return p->b; /* Must be variable2.b. */
  280. }
  281. Because the compiler can see all stores to "gp", it knows that the only
  282. possible values of "gp" are "variable1" on the one hand and "variable2"
  283. on the other. The comparison in reader() therefore tells the compiler
  284. the exact value of "p" even in the not-equals case. This allows the
  285. compiler to make the return values independent of the load from "gp",
  286. in turn destroying the ordering between this load and the loads of the
  287. return values. This can result in "p->b" returning pre-initialization
  288. garbage values.
  289. In short, rcu_dereference() is -not- optional when you are going to
  290. dereference the resulting pointer.
  291. WHICH MEMBER OF THE rcu_dereference() FAMILY SHOULD YOU USE?
  292. ------------------------------------------------------------
  293. First, please avoid using rcu_dereference_raw() and also please avoid
  294. using rcu_dereference_check() and rcu_dereference_protected() with a
  295. second argument with a constant value of 1 (or true, for that matter).
  296. With that caution out of the way, here is some guidance for which
  297. member of the rcu_dereference() to use in various situations:
  298. 1. If the access needs to be within an RCU read-side critical
  299. section, use rcu_dereference(). With the new consolidated
  300. RCU flavors, an RCU read-side critical section is entered
  301. using rcu_read_lock(), anything that disables bottom halves,
  302. anything that disables interrupts, or anything that disables
  303. preemption.
  304. 2. If the access might be within an RCU read-side critical section
  305. on the one hand, or protected by (say) my_lock on the other,
  306. use rcu_dereference_check(), for example::
  307. p1 = rcu_dereference_check(p->rcu_protected_pointer,
  308. lockdep_is_held(&my_lock));
  309. 3. If the access might be within an RCU read-side critical section
  310. on the one hand, or protected by either my_lock or your_lock on
  311. the other, again use rcu_dereference_check(), for example::
  312. p1 = rcu_dereference_check(p->rcu_protected_pointer,
  313. lockdep_is_held(&my_lock) ||
  314. lockdep_is_held(&your_lock));
  315. 4. If the access is on the update side, so that it is always protected
  316. by my_lock, use rcu_dereference_protected()::
  317. p1 = rcu_dereference_protected(p->rcu_protected_pointer,
  318. lockdep_is_held(&my_lock));
  319. This can be extended to handle multiple locks as in #3 above,
  320. and both can be extended to check other conditions as well.
  321. 5. If the protection is supplied by the caller, and is thus unknown
  322. to this code, that is the rare case when rcu_dereference_raw()
  323. is appropriate. In addition, rcu_dereference_raw() might be
  324. appropriate when the lockdep expression would be excessively
  325. complex, except that a better approach in that case might be to
  326. take a long hard look at your synchronization design. Still,
  327. there are data-locking cases where any one of a very large number
  328. of locks or reference counters suffices to protect the pointer,
  329. so rcu_dereference_raw() does have its place.
  330. However, its place is probably quite a bit smaller than one
  331. might expect given the number of uses in the current kernel.
  332. Ditto for its synonym, rcu_dereference_check( ... , 1), and
  333. its close relative, rcu_dereference_protected(... , 1).
  334. SPARSE CHECKING OF RCU-PROTECTED POINTERS
  335. -----------------------------------------
  336. The sparse static-analysis tool checks for direct access to RCU-protected
  337. pointers, which can result in "interesting" bugs due to compiler
  338. optimizations involving invented loads and perhaps also load tearing.
  339. For example, suppose someone mistakenly does something like this::
  340. p = q->rcu_protected_pointer;
  341. do_something_with(p->a);
  342. do_something_else_with(p->b);
  343. If register pressure is high, the compiler might optimize "p" out
  344. of existence, transforming the code to something like this::
  345. do_something_with(q->rcu_protected_pointer->a);
  346. do_something_else_with(q->rcu_protected_pointer->b);
  347. This could fatally disappoint your code if q->rcu_protected_pointer
  348. changed in the meantime. Nor is this a theoretical problem: Exactly
  349. this sort of bug cost Paul E. McKenney (and several of his innocent
  350. colleagues) a three-day weekend back in the early 1990s.
  351. Load tearing could of course result in dereferencing a mashup of a pair
  352. of pointers, which also might fatally disappoint your code.
  353. These problems could have been avoided simply by making the code instead
  354. read as follows::
  355. p = rcu_dereference(q->rcu_protected_pointer);
  356. do_something_with(p->a);
  357. do_something_else_with(p->b);
  358. Unfortunately, these sorts of bugs can be extremely hard to spot during
  359. review. This is where the sparse tool comes into play, along with the
  360. "__rcu" marker. If you mark a pointer declaration, whether in a structure
  361. or as a formal parameter, with "__rcu", which tells sparse to complain if
  362. this pointer is accessed directly. It will also cause sparse to complain
  363. if a pointer not marked with "__rcu" is accessed using rcu_dereference()
  364. and friends. For example, ->rcu_protected_pointer might be declared as
  365. follows::
  366. struct foo __rcu *rcu_protected_pointer;
  367. Use of "__rcu" is opt-in. If you choose not to use it, then you should
  368. ignore the sparse warnings.