Commit | Line | Data |
---|---|---|
5e1bc932 PT |
1 | .. _whatisrcu_doc: |
2 | ||
628c0842 | 3 | What is RCU? -- "Read, Copy, Update" |
5e1bc932 | 4 | ====================================== |
628c0842 | 5 | |
32300751 PM |
6 | Please note that the "What is RCU?" LWN series is an excellent place |
7 | to start learning about RCU: | |
8 | ||
5e1bc932 PT |
9 | | 1. What is RCU, Fundamentally? http://lwn.net/Articles/262464/ |
10 | | 2. What is RCU? Part 2: Usage http://lwn.net/Articles/263130/ | |
11 | | 3. RCU part 3: the RCU API http://lwn.net/Articles/264090/ | |
12 | | 4. The RCU API, 2010 Edition http://lwn.net/Articles/418853/ | |
13 | | 2010 Big API Table http://lwn.net/Articles/419086/ | |
14 | | 5. The RCU API, 2014 Edition http://lwn.net/Articles/609904/ | |
15 | | 2014 Big API Table http://lwn.net/Articles/609973/ | |
32300751 PM |
16 | |
17 | ||
dd81eca8 PM |
18 | What is RCU? |
19 | ||
20 | RCU is a synchronization mechanism that was added to the Linux kernel | |
21 | during the 2.5 development effort that is optimized for read-mostly | |
22 | situations. Although RCU is actually quite simple once you understand it, | |
23 | getting there can sometimes be a challenge. Part of the problem is that | |
24 | most of the past descriptions of RCU have been written with the mistaken | |
25 | assumption that there is "one true way" to describe RCU. Instead, | |
26 | the experience has been that different people must take different paths | |
27 | to arrive at an understanding of RCU. This document provides several | |
28 | different paths, as follows: | |
29 | ||
5e1bc932 PT |
30 | :ref:`1. RCU OVERVIEW <1_whatisRCU>` |
31 | ||
32 | :ref:`2. WHAT IS RCU'S CORE API? <2_whatisRCU>` | |
33 | ||
34 | :ref:`3. WHAT ARE SOME EXAMPLE USES OF CORE RCU API? <3_whatisRCU>` | |
35 | ||
36 | :ref:`4. WHAT IF MY UPDATING THREAD CANNOT BLOCK? <4_whatisRCU>` | |
37 | ||
38 | :ref:`5. WHAT ARE SOME SIMPLE IMPLEMENTATIONS OF RCU? <5_whatisRCU>` | |
39 | ||
40 | :ref:`6. ANALOGY WITH READER-WRITER LOCKING <6_whatisRCU>` | |
41 | ||
42 | :ref:`7. FULL LIST OF RCU APIs <7_whatisRCU>` | |
43 | ||
44 | :ref:`8. ANSWERS TO QUICK QUIZZES <8_whatisRCU>` | |
dd81eca8 PM |
45 | |
46 | People who prefer starting with a conceptual overview should focus on | |
47 | Section 1, though most readers will profit by reading this section at | |
48 | some point. People who prefer to start with an API that they can then | |
49 | experiment with should focus on Section 2. People who prefer to start | |
50 | with example uses should focus on Sections 3 and 4. People who need to | |
51 | understand the RCU implementation should focus on Section 5, then dive | |
52 | into the kernel source code. People who reason best by analogy should | |
53 | focus on Section 6. Section 7 serves as an index to the docbook API | |
54 | documentation, and Section 8 is the traditional answer key. | |
55 | ||
56 | So, start with the section that makes the most sense to you and your | |
57 | preferred method of learning. If you need to know everything about | |
58 | everything, feel free to read the whole thing -- but if you are really | |
59 | that type of person, you have perused the source code and will therefore | |
60 | never need this document anyway. ;-) | |
61 | ||
5e1bc932 | 62 | .. _1_whatisRCU: |
dd81eca8 PM |
63 | |
64 | 1. RCU OVERVIEW | |
5e1bc932 | 65 | ---------------- |
dd81eca8 PM |
66 | |
67 | The basic idea behind RCU is to split updates into "removal" and | |
68 | "reclamation" phases. The removal phase removes references to data items | |
69 | within a data structure (possibly by replacing them with references to | |
70 | new versions of these data items), and can run concurrently with readers. | |
71 | The reason that it is safe to run the removal phase concurrently with | |
72 | readers is the semantics of modern CPUs guarantee that readers will see | |
73 | either the old or the new version of the data structure rather than a | |
74 | partially updated reference. The reclamation phase does the work of reclaiming | |
75 | (e.g., freeing) the data items removed from the data structure during the | |
76 | removal phase. Because reclaiming data items can disrupt any readers | |
77 | concurrently referencing those data items, the reclamation phase must | |
78 | not start until readers no longer hold references to those data items. | |
79 | ||
80 | Splitting the update into removal and reclamation phases permits the | |
81 | updater to perform the removal phase immediately, and to defer the | |
82 | reclamation phase until all readers active during the removal phase have | |
83 | completed, either by blocking until they finish or by registering a | |
84 | callback that is invoked after they finish. Only readers that are active | |
85 | during the removal phase need be considered, because any reader starting | |
86 | after the removal phase will be unable to gain a reference to the removed | |
87 | data items, and therefore cannot be disrupted by the reclamation phase. | |
88 | ||
89 | So the typical RCU update sequence goes something like the following: | |
90 | ||
91 | a. Remove pointers to a data structure, so that subsequent | |
92 | readers cannot gain a reference to it. | |
93 | ||
94 | b. Wait for all previous readers to complete their RCU read-side | |
95 | critical sections. | |
96 | ||
97 | c. At this point, there cannot be any readers who hold references | |
98 | to the data structure, so it now may safely be reclaimed | |
99 | (e.g., kfree()d). | |
100 | ||
101 | Step (b) above is the key idea underlying RCU's deferred destruction. | |
102 | The ability to wait until all readers are done allows RCU readers to | |
103 | use much lighter-weight synchronization, in some cases, absolutely no | |
104 | synchronization at all. In contrast, in more conventional lock-based | |
105 | schemes, readers must use heavy-weight synchronization in order to | |
106 | prevent an updater from deleting the data structure out from under them. | |
107 | This is because lock-based updaters typically update data items in place, | |
108 | and must therefore exclude readers. In contrast, RCU-based updaters | |
109 | typically take advantage of the fact that writes to single aligned | |
110 | pointers are atomic on modern CPUs, allowing atomic insertion, removal, | |
111 | and replacement of data items in a linked structure without disrupting | |
112 | readers. Concurrent RCU readers can then continue accessing the old | |
113 | versions, and can dispense with the atomic operations, memory barriers, | |
114 | and communications cache misses that are so expensive on present-day | |
115 | SMP computer systems, even in absence of lock contention. | |
116 | ||
117 | In the three-step procedure shown above, the updater is performing both | |
118 | the removal and the reclamation step, but it is often helpful for an | |
119 | entirely different thread to do the reclamation, as is in fact the case | |
120 | in the Linux kernel's directory-entry cache (dcache). Even if the same | |
121 | thread performs both the update step (step (a) above) and the reclamation | |
122 | step (step (c) above), it is often helpful to think of them separately. | |
123 | For example, RCU readers and updaters need not communicate at all, | |
124 | but RCU provides implicit low-overhead communication between readers | |
125 | and reclaimers, namely, in step (b) above. | |
126 | ||
127 | So how the heck can a reclaimer tell when a reader is done, given | |
128 | that readers are not doing any sort of synchronization operations??? | |
129 | Read on to learn about how RCU's API makes this easy. | |
130 | ||
5e1bc932 | 131 | .. _2_whatisRCU: |
dd81eca8 PM |
132 | |
133 | 2. WHAT IS RCU'S CORE API? | |
5e1bc932 | 134 | --------------------------- |
dd81eca8 PM |
135 | |
136 | The core RCU API is quite small: | |
137 | ||
138 | a. rcu_read_lock() | |
139 | b. rcu_read_unlock() | |
140 | c. synchronize_rcu() / call_rcu() | |
141 | d. rcu_assign_pointer() | |
142 | e. rcu_dereference() | |
143 | ||
144 | There are many other members of the RCU API, but the rest can be | |
145 | expressed in terms of these five, though most implementations instead | |
146 | express synchronize_rcu() in terms of the call_rcu() callback API. | |
147 | ||
148 | The five core RCU APIs are described below, the other 18 will be enumerated | |
149 | later. See the kernel docbook documentation for more info, or look directly | |
150 | at the function header comments. | |
151 | ||
152 | rcu_read_lock() | |
5e1bc932 | 153 | ^^^^^^^^^^^^^^^ |
dd81eca8 PM |
154 | void rcu_read_lock(void); |
155 | ||
156 | Used by a reader to inform the reclaimer that the reader is | |
157 | entering an RCU read-side critical section. It is illegal | |
158 | to block while in an RCU read-side critical section, though | |
28f6569a | 159 | kernels built with CONFIG_PREEMPT_RCU can preempt RCU |
6b3ef48a PM |
160 | read-side critical sections. Any RCU-protected data structure |
161 | accessed during an RCU read-side critical section is guaranteed to | |
162 | remain unreclaimed for the full duration of that critical section. | |
dd81eca8 PM |
163 | Reference counts may be used in conjunction with RCU to maintain |
164 | longer-term references to data structures. | |
165 | ||
166 | rcu_read_unlock() | |
5e1bc932 | 167 | ^^^^^^^^^^^^^^^^^ |
dd81eca8 PM |
168 | void rcu_read_unlock(void); |
169 | ||
170 | Used by a reader to inform the reclaimer that the reader is | |
171 | exiting an RCU read-side critical section. Note that RCU | |
172 | read-side critical sections may be nested and/or overlapping. | |
173 | ||
174 | synchronize_rcu() | |
5e1bc932 | 175 | ^^^^^^^^^^^^^^^^^ |
dd81eca8 PM |
176 | void synchronize_rcu(void); |
177 | ||
178 | Marks the end of updater code and the beginning of reclaimer | |
179 | code. It does this by blocking until all pre-existing RCU | |
180 | read-side critical sections on all CPUs have completed. | |
5e1bc932 | 181 | Note that synchronize_rcu() will **not** necessarily wait for |
dd81eca8 | 182 | any subsequent RCU read-side critical sections to complete. |
5e1bc932 | 183 | For example, consider the following sequence of events:: |
dd81eca8 PM |
184 | |
185 | CPU 0 CPU 1 CPU 2 | |
186 | ----------------- ------------------------- --------------- | |
187 | 1. rcu_read_lock() | |
188 | 2. enters synchronize_rcu() | |
189 | 3. rcu_read_lock() | |
190 | 4. rcu_read_unlock() | |
191 | 5. exits synchronize_rcu() | |
192 | 6. rcu_read_unlock() | |
193 | ||
194 | To reiterate, synchronize_rcu() waits only for ongoing RCU | |
195 | read-side critical sections to complete, not necessarily for | |
196 | any that begin after synchronize_rcu() is invoked. | |
197 | ||
198 | Of course, synchronize_rcu() does not necessarily return | |
5e1bc932 | 199 | **immediately** after the last pre-existing RCU read-side critical |
dd81eca8 PM |
200 | section completes. For one thing, there might well be scheduling |
201 | delays. For another thing, many RCU implementations process | |
202 | requests in batches in order to improve efficiencies, which can | |
203 | further delay synchronize_rcu(). | |
204 | ||
205 | Since synchronize_rcu() is the API that must figure out when | |
206 | readers are done, its implementation is key to RCU. For RCU | |
207 | to be useful in all but the most read-intensive situations, | |
208 | synchronize_rcu()'s overhead must also be quite small. | |
209 | ||
210 | The call_rcu() API is a callback form of synchronize_rcu(), | |
211 | and is described in more detail in a later section. Instead of | |
212 | blocking, it registers a function and argument which are invoked | |
213 | after all ongoing RCU read-side critical sections have completed. | |
214 | This callback variant is particularly useful in situations where | |
165d6c78 PM |
215 | it is illegal to block or where update-side performance is |
216 | critically important. | |
217 | ||
218 | However, the call_rcu() API should not be used lightly, as use | |
219 | of the synchronize_rcu() API generally results in simpler code. | |
220 | In addition, the synchronize_rcu() API has the nice property | |
221 | of automatically limiting update rate should grace periods | |
222 | be delayed. This property results in system resilience in face | |
223 | of denial-of-service attacks. Code using call_rcu() should limit | |
224 | update rate in order to gain this same sort of resilience. See | |
225 | checklist.txt for some approaches to limiting the update rate. | |
dd81eca8 PM |
226 | |
227 | rcu_assign_pointer() | |
5e1bc932 | 228 | ^^^^^^^^^^^^^^^^^^^^ |
9129b017 | 229 | void rcu_assign_pointer(p, typeof(p) v); |
dd81eca8 | 230 | |
5e1bc932 | 231 | Yes, rcu_assign_pointer() **is** implemented as a macro, though it |
dd81eca8 PM |
232 | would be cool to be able to declare a function in this manner. |
233 | (Compiler experts will no doubt disagree.) | |
234 | ||
235 | The updater uses this function to assign a new value to an | |
236 | RCU-protected pointer, in order to safely communicate the change | |
9129b017 AP |
237 | in value from the updater to the reader. This macro does not |
238 | evaluate to an rvalue, but it does execute any memory-barrier | |
239 | instructions required for a given CPU architecture. | |
dd81eca8 | 240 | |
d19720a9 PM |
241 | Perhaps just as important, it serves to document (1) which |
242 | pointers are protected by RCU and (2) the point at which a | |
243 | given structure becomes accessible to other CPUs. That said, | |
244 | rcu_assign_pointer() is most frequently used indirectly, via | |
245 | the _rcu list-manipulation primitives such as list_add_rcu(). | |
dd81eca8 PM |
246 | |
247 | rcu_dereference() | |
5e1bc932 | 248 | ^^^^^^^^^^^^^^^^^ |
dd81eca8 PM |
249 | typeof(p) rcu_dereference(p); |
250 | ||
251 | Like rcu_assign_pointer(), rcu_dereference() must be implemented | |
252 | as a macro. | |
253 | ||
254 | The reader uses rcu_dereference() to fetch an RCU-protected | |
255 | pointer, which returns a value that may then be safely | |
8cf503d3 | 256 | dereferenced. Note that rcu_dereference() does not actually |
dd81eca8 PM |
257 | dereference the pointer, instead, it protects the pointer for |
258 | later dereferencing. It also executes any needed memory-barrier | |
259 | instructions for a given CPU architecture. Currently, only Alpha | |
260 | needs memory barriers within rcu_dereference() -- on other CPUs, | |
261 | it compiles to nothing, not even a compiler directive. | |
262 | ||
263 | Common coding practice uses rcu_dereference() to copy an | |
264 | RCU-protected pointer to a local variable, then dereferences | |
5e1bc932 | 265 | this local variable, for example as follows:: |
dd81eca8 PM |
266 | |
267 | p = rcu_dereference(head.next); | |
268 | return p->data; | |
269 | ||
270 | However, in this case, one could just as easily combine these | |
5e1bc932 | 271 | into one statement:: |
dd81eca8 PM |
272 | |
273 | return rcu_dereference(head.next)->data; | |
274 | ||
275 | If you are going to be fetching multiple fields from the | |
276 | RCU-protected structure, using the local variable is of | |
277 | course preferred. Repeated rcu_dereference() calls look | |
ed384464 MV |
278 | ugly, do not guarantee that the same pointer will be returned |
279 | if an update happened while in the critical section, and incur | |
280 | unnecessary overhead on Alpha CPUs. | |
dd81eca8 PM |
281 | |
282 | Note that the value returned by rcu_dereference() is valid | |
5e1bc932 PT |
283 | only within the enclosing RCU read-side critical section [1]_. |
284 | For example, the following is **not** legal:: | |
dd81eca8 PM |
285 | |
286 | rcu_read_lock(); | |
287 | p = rcu_dereference(head.next); | |
288 | rcu_read_unlock(); | |
4357fb57 | 289 | x = p->address; /* BUG!!! */ |
dd81eca8 | 290 | rcu_read_lock(); |
4357fb57 | 291 | y = p->data; /* BUG!!! */ |
dd81eca8 PM |
292 | rcu_read_unlock(); |
293 | ||
294 | Holding a reference from one RCU read-side critical section | |
295 | to another is just as illegal as holding a reference from | |
296 | one lock-based critical section to another! Similarly, | |
297 | using a reference outside of the critical section in which | |
298 | it was acquired is just as illegal as doing so with normal | |
299 | locking. | |
300 | ||
301 | As with rcu_assign_pointer(), an important function of | |
d19720a9 PM |
302 | rcu_dereference() is to document which pointers are protected by |
303 | RCU, in particular, flagging a pointer that is subject to changing | |
304 | at any time, including immediately after the rcu_dereference(). | |
305 | And, again like rcu_assign_pointer(), rcu_dereference() is | |
306 | typically used indirectly, via the _rcu list-manipulation | |
5e1bc932 | 307 | primitives, such as list_for_each_entry_rcu() [2]_. |
dd81eca8 | 308 | |
5e1bc932 | 309 | .. [1] The variant rcu_dereference_protected() can be used outside |
93eb1420 JFG |
310 | of an RCU read-side critical section as long as the usage is |
311 | protected by locks acquired by the update-side code. This variant | |
312 | avoids the lockdep warning that would happen when using (for | |
313 | example) rcu_dereference() without rcu_read_lock() protection. | |
314 | Using rcu_dereference_protected() also has the advantage | |
315 | of permitting compiler optimizations that rcu_dereference() | |
316 | must prohibit. The rcu_dereference_protected() variant takes | |
317 | a lockdep expression to indicate which locks must be acquired | |
318 | by the caller. If the indicated protection is not provided, | |
ccc9971e | 319 | a lockdep splat is emitted. See Documentation/RCU/Design/Requirements/Requirements.rst |
93eb1420 JFG |
320 | and the API's code comments for more details and example usage. |
321 | ||
5e1bc932 | 322 | .. [2] If the list_for_each_entry_rcu() instance might be used by |
45271064 JFG |
323 | update-side code as well as by RCU readers, then an additional |
324 | lockdep expression can be added to its list of arguments. | |
325 | For example, given an additional "lock_is_held(&mylock)" argument, | |
326 | the RCU lockdep code would complain only if this instance was | |
327 | invoked outside of an RCU read-side critical section and without | |
328 | the protection of mylock. | |
329 | ||
dd81eca8 PM |
330 | The following diagram shows how each API communicates among the |
331 | reader, updater, and reclaimer. | |
5e1bc932 | 332 | :: |
dd81eca8 PM |
333 | |
334 | ||
335 | rcu_assign_pointer() | |
0fa201d1 | 336 | +--------+ |
dd81eca8 PM |
337 | +---------------------->| reader |---------+ |
338 | | +--------+ | | |
339 | | | | | |
340 | | | | Protect: | |
341 | | | | rcu_read_lock() | |
342 | | | | rcu_read_unlock() | |
343 | | rcu_dereference() | | | |
0fa201d1 TA |
344 | +---------+ | | |
345 | | updater |<----------------+ | | |
346 | +---------+ V | |
dd81eca8 PM |
347 | | +-----------+ |
348 | +----------------------------------->| reclaimer | | |
0fa201d1 | 349 | +-----------+ |
dd81eca8 PM |
350 | Defer: |
351 | synchronize_rcu() & call_rcu() | |
352 | ||
353 | ||
354 | The RCU infrastructure observes the time sequence of rcu_read_lock(), | |
355 | rcu_read_unlock(), synchronize_rcu(), and call_rcu() invocations in | |
356 | order to determine when (1) synchronize_rcu() invocations may return | |
357 | to their callers and (2) call_rcu() callbacks may be invoked. Efficient | |
358 | implementations of the RCU infrastructure make heavy use of batching in | |
359 | order to amortize their overhead over many uses of the corresponding APIs. | |
360 | ||
33984964 JFG |
361 | There are at least three flavors of RCU usage in the Linux kernel. The diagram |
362 | above shows the most common one. On the updater side, the rcu_assign_pointer(), | |
77f80860 | 363 | synchronize_rcu() and call_rcu() primitives used are the same for all three |
33984964 JFG |
364 | flavors. However for protection (on the reader side), the primitives used vary |
365 | depending on the flavor: | |
dd81eca8 | 366 | |
33984964 JFG |
367 | a. rcu_read_lock() / rcu_read_unlock() |
368 | rcu_dereference() | |
dd81eca8 | 369 | |
33984964 JFG |
370 | b. rcu_read_lock_bh() / rcu_read_unlock_bh() |
371 | local_bh_disable() / local_bh_enable() | |
372 | rcu_dereference_bh() | |
dd81eca8 | 373 | |
33984964 JFG |
374 | c. rcu_read_lock_sched() / rcu_read_unlock_sched() |
375 | preempt_disable() / preempt_enable() | |
376 | local_irq_save() / local_irq_restore() | |
377 | hardirq enter / hardirq exit | |
378 | NMI enter / NMI exit | |
379 | rcu_dereference_sched() | |
dd81eca8 | 380 | |
33984964 | 381 | These three flavors are used as follows: |
dd81eca8 PM |
382 | |
383 | a. RCU applied to normal data structures. | |
384 | ||
385 | b. RCU applied to networking data structures that may be subjected | |
386 | to remote denial-of-service attacks. | |
387 | ||
388 | c. RCU applied to scheduler and interrupt/NMI-handler tasks. | |
389 | ||
390 | Again, most uses will be of (a). The (b) and (c) cases are important | |
391 | for specialized uses, but are relatively uncommon. | |
392 | ||
5e1bc932 | 393 | .. _3_whatisRCU: |
dd81eca8 PM |
394 | |
395 | 3. WHAT ARE SOME EXAMPLE USES OF CORE RCU API? | |
5e1bc932 | 396 | ----------------------------------------------- |
dd81eca8 PM |
397 | |
398 | This section shows a simple use of the core RCU API to protect a | |
d19720a9 | 399 | global pointer to a dynamically allocated structure. More-typical |
5e1bc932 PT |
400 | uses of RCU may be found in :ref:`listRCU.rst <list_rcu_doc>`, |
401 | :ref:`arrayRCU.rst <array_rcu_doc>`, and :ref:`NMI-RCU.rst <NMI_rcu_doc>`. | |
402 | :: | |
dd81eca8 PM |
403 | |
404 | struct foo { | |
405 | int a; | |
406 | char b; | |
407 | long c; | |
408 | }; | |
409 | DEFINE_SPINLOCK(foo_mutex); | |
410 | ||
2c4ac34b | 411 | struct foo __rcu *gbl_foo; |
dd81eca8 PM |
412 | |
413 | /* | |
414 | * Create a new struct foo that is the same as the one currently | |
415 | * pointed to by gbl_foo, except that field "a" is replaced | |
416 | * with "new_a". Points gbl_foo to the new structure, and | |
417 | * frees up the old structure after a grace period. | |
418 | * | |
419 | * Uses rcu_assign_pointer() to ensure that concurrent readers | |
420 | * see the initialized version of the new structure. | |
421 | * | |
422 | * Uses synchronize_rcu() to ensure that any readers that might | |
423 | * have references to the old structure complete before freeing | |
424 | * the old structure. | |
425 | */ | |
426 | void foo_update_a(int new_a) | |
427 | { | |
428 | struct foo *new_fp; | |
429 | struct foo *old_fp; | |
430 | ||
de0dfcdf | 431 | new_fp = kmalloc(sizeof(*new_fp), GFP_KERNEL); |
dd81eca8 | 432 | spin_lock(&foo_mutex); |
2c4ac34b | 433 | old_fp = rcu_dereference_protected(gbl_foo, lockdep_is_held(&foo_mutex)); |
dd81eca8 PM |
434 | *new_fp = *old_fp; |
435 | new_fp->a = new_a; | |
436 | rcu_assign_pointer(gbl_foo, new_fp); | |
437 | spin_unlock(&foo_mutex); | |
438 | synchronize_rcu(); | |
439 | kfree(old_fp); | |
440 | } | |
441 | ||
442 | /* | |
443 | * Return the value of field "a" of the current gbl_foo | |
444 | * structure. Use rcu_read_lock() and rcu_read_unlock() | |
445 | * to ensure that the structure does not get deleted out | |
446 | * from under us, and use rcu_dereference() to ensure that | |
447 | * we see the initialized version of the structure (important | |
448 | * for DEC Alpha and for people reading the code). | |
449 | */ | |
450 | int foo_get_a(void) | |
451 | { | |
452 | int retval; | |
453 | ||
454 | rcu_read_lock(); | |
455 | retval = rcu_dereference(gbl_foo)->a; | |
456 | rcu_read_unlock(); | |
457 | return retval; | |
458 | } | |
459 | ||
460 | So, to sum up: | |
461 | ||
5e1bc932 | 462 | - Use rcu_read_lock() and rcu_read_unlock() to guard RCU |
dd81eca8 PM |
463 | read-side critical sections. |
464 | ||
5e1bc932 | 465 | - Within an RCU read-side critical section, use rcu_dereference() |
dd81eca8 PM |
466 | to dereference RCU-protected pointers. |
467 | ||
5e1bc932 | 468 | - Use some solid scheme (such as locks or semaphores) to |
dd81eca8 PM |
469 | keep concurrent updates from interfering with each other. |
470 | ||
5e1bc932 | 471 | - Use rcu_assign_pointer() to update an RCU-protected pointer. |
dd81eca8 | 472 | This primitive protects concurrent readers from the updater, |
5e1bc932 | 473 | **not** concurrent updates from each other! You therefore still |
dd81eca8 PM |
474 | need to use locking (or something similar) to keep concurrent |
475 | rcu_assign_pointer() primitives from interfering with each other. | |
476 | ||
5e1bc932 PT |
477 | - Use synchronize_rcu() **after** removing a data element from an |
478 | RCU-protected data structure, but **before** reclaiming/freeing | |
dd81eca8 PM |
479 | the data element, in order to wait for the completion of all |
480 | RCU read-side critical sections that might be referencing that | |
481 | data item. | |
482 | ||
483 | See checklist.txt for additional rules to follow when using RCU. | |
5e1bc932 PT |
484 | And again, more-typical uses of RCU may be found in :ref:`listRCU.rst |
485 | <list_rcu_doc>`, :ref:`arrayRCU.rst <array_rcu_doc>`, and :ref:`NMI-RCU.rst | |
486 | <NMI_rcu_doc>`. | |
dd81eca8 | 487 | |
5e1bc932 | 488 | .. _4_whatisRCU: |
dd81eca8 PM |
489 | |
490 | 4. WHAT IF MY UPDATING THREAD CANNOT BLOCK? | |
5e1bc932 | 491 | -------------------------------------------- |
dd81eca8 PM |
492 | |
493 | In the example above, foo_update_a() blocks until a grace period elapses. | |
494 | This is quite simple, but in some cases one cannot afford to wait so | |
495 | long -- there might be other high-priority work to be done. | |
496 | ||
497 | In such cases, one uses call_rcu() rather than synchronize_rcu(). | |
5e1bc932 | 498 | The call_rcu() API is as follows:: |
dd81eca8 | 499 | |
c386e29d | 500 | void call_rcu(struct rcu_head *head, rcu_callback_t func); |
dd81eca8 PM |
501 | |
502 | This function invokes func(head) after a grace period has elapsed. | |
503 | This invocation might happen from either softirq or process context, | |
504 | so the function is not permitted to block. The foo struct needs to | |
5e1bc932 | 505 | have an rcu_head structure added, perhaps as follows:: |
dd81eca8 PM |
506 | |
507 | struct foo { | |
508 | int a; | |
509 | char b; | |
510 | long c; | |
511 | struct rcu_head rcu; | |
512 | }; | |
513 | ||
5e1bc932 | 514 | The foo_update_a() function might then be written as follows:: |
dd81eca8 PM |
515 | |
516 | /* | |
517 | * Create a new struct foo that is the same as the one currently | |
518 | * pointed to by gbl_foo, except that field "a" is replaced | |
519 | * with "new_a". Points gbl_foo to the new structure, and | |
520 | * frees up the old structure after a grace period. | |
521 | * | |
522 | * Uses rcu_assign_pointer() to ensure that concurrent readers | |
523 | * see the initialized version of the new structure. | |
524 | * | |
525 | * Uses call_rcu() to ensure that any readers that might have | |
526 | * references to the old structure complete before freeing the | |
527 | * old structure. | |
528 | */ | |
529 | void foo_update_a(int new_a) | |
530 | { | |
531 | struct foo *new_fp; | |
532 | struct foo *old_fp; | |
533 | ||
de0dfcdf | 534 | new_fp = kmalloc(sizeof(*new_fp), GFP_KERNEL); |
dd81eca8 | 535 | spin_lock(&foo_mutex); |
2c4ac34b | 536 | old_fp = rcu_dereference_protected(gbl_foo, lockdep_is_held(&foo_mutex)); |
dd81eca8 PM |
537 | *new_fp = *old_fp; |
538 | new_fp->a = new_a; | |
539 | rcu_assign_pointer(gbl_foo, new_fp); | |
540 | spin_unlock(&foo_mutex); | |
541 | call_rcu(&old_fp->rcu, foo_reclaim); | |
542 | } | |
543 | ||
5e1bc932 | 544 | The foo_reclaim() function might appear as follows:: |
dd81eca8 PM |
545 | |
546 | void foo_reclaim(struct rcu_head *rp) | |
547 | { | |
548 | struct foo *fp = container_of(rp, struct foo, rcu); | |
549 | ||
57d34a6c KC |
550 | foo_cleanup(fp->a); |
551 | ||
dd81eca8 PM |
552 | kfree(fp); |
553 | } | |
554 | ||
555 | The container_of() primitive is a macro that, given a pointer into a | |
556 | struct, the type of the struct, and the pointed-to field within the | |
557 | struct, returns a pointer to the beginning of the struct. | |
558 | ||
559 | The use of call_rcu() permits the caller of foo_update_a() to | |
560 | immediately regain control, without needing to worry further about the | |
561 | old version of the newly updated element. It also clearly shows the | |
562 | RCU distinction between updater, namely foo_update_a(), and reclaimer, | |
563 | namely foo_reclaim(). | |
564 | ||
565 | The summary of advice is the same as for the previous section, except | |
566 | that we are now using call_rcu() rather than synchronize_rcu(): | |
567 | ||
5e1bc932 | 568 | - Use call_rcu() **after** removing a data element from an |
dd81eca8 PM |
569 | RCU-protected data structure in order to register a callback |
570 | function that will be invoked after the completion of all RCU | |
571 | read-side critical sections that might be referencing that | |
572 | data item. | |
573 | ||
57d34a6c KC |
574 | If the callback for call_rcu() is not doing anything more than calling |
575 | kfree() on the structure, you can use kfree_rcu() instead of call_rcu() | |
5e1bc932 | 576 | to avoid having to write your own callback:: |
57d34a6c KC |
577 | |
578 | kfree_rcu(old_fp, rcu); | |
579 | ||
dd81eca8 PM |
580 | Again, see checklist.txt for additional rules governing the use of RCU. |
581 | ||
5e1bc932 | 582 | .. _5_whatisRCU: |
dd81eca8 PM |
583 | |
584 | 5. WHAT ARE SOME SIMPLE IMPLEMENTATIONS OF RCU? | |
5e1bc932 | 585 | ------------------------------------------------ |
dd81eca8 PM |
586 | |
587 | One of the nice things about RCU is that it has extremely simple "toy" | |
588 | implementations that are a good first step towards understanding the | |
589 | production-quality implementations in the Linux kernel. This section | |
590 | presents two such "toy" implementations of RCU, one that is implemented | |
591 | in terms of familiar locking primitives, and another that more closely | |
592 | resembles "classic" RCU. Both are way too simple for real-world use, | |
593 | lacking both functionality and performance. However, they are useful | |
87d1779d | 594 | in getting a feel for how RCU works. See kernel/rcu/update.c for a |
dd81eca8 PM |
595 | production-quality implementation, and see: |
596 | ||
597 | http://www.rdrop.com/users/paulmck/RCU | |
598 | ||
599 | for papers describing the Linux kernel RCU implementation. The OLS'01 | |
600 | and OLS'02 papers are a good introduction, and the dissertation provides | |
d19720a9 | 601 | more details on the current implementation as of early 2004. |
dd81eca8 PM |
602 | |
603 | ||
604 | 5A. "TOY" IMPLEMENTATION #1: LOCKING | |
5e1bc932 | 605 | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ |
dd81eca8 PM |
606 | This section presents a "toy" RCU implementation that is based on |
607 | familiar locking primitives. Its overhead makes it a non-starter for | |
608 | real-life use, as does its lack of scalability. It is also unsuitable | |
609 | for realtime use, since it allows scheduling latency to "bleed" from | |
d3d3a3cc PM |
610 | one read-side critical section to another. It also assumes recursive |
611 | reader-writer locks: If you try this with non-recursive locks, and | |
612 | you allow nested rcu_read_lock() calls, you can deadlock. | |
dd81eca8 PM |
613 | |
614 | However, it is probably the easiest implementation to relate to, so is | |
615 | a good starting point. | |
616 | ||
5e1bc932 | 617 | It is extremely simple:: |
dd81eca8 PM |
618 | |
619 | static DEFINE_RWLOCK(rcu_gp_mutex); | |
620 | ||
621 | void rcu_read_lock(void) | |
622 | { | |
623 | read_lock(&rcu_gp_mutex); | |
624 | } | |
625 | ||
626 | void rcu_read_unlock(void) | |
627 | { | |
628 | read_unlock(&rcu_gp_mutex); | |
629 | } | |
630 | ||
631 | void synchronize_rcu(void) | |
632 | { | |
633 | write_lock(&rcu_gp_mutex); | |
264d4f88 | 634 | smp_mb__after_spinlock(); |
dd81eca8 PM |
635 | write_unlock(&rcu_gp_mutex); |
636 | } | |
637 | ||
066bb1c8 PM |
638 | [You can ignore rcu_assign_pointer() and rcu_dereference() without missing |
639 | much. But here are simplified versions anyway. And whatever you do, | |
5e1bc932 | 640 | don't forget about them when submitting patches making use of RCU!]:: |
066bb1c8 PM |
641 | |
642 | #define rcu_assign_pointer(p, v) \ | |
643 | ({ \ | |
644 | smp_store_release(&(p), (v)); \ | |
645 | }) | |
646 | ||
647 | #define rcu_dereference(p) \ | |
648 | ({ \ | |
9ad3c143 | 649 | typeof(p) _________p1 = READ_ONCE(p); \ |
066bb1c8 PM |
650 | (_________p1); \ |
651 | }) | |
dd81eca8 PM |
652 | |
653 | ||
654 | The rcu_read_lock() and rcu_read_unlock() primitive read-acquire | |
655 | and release a global reader-writer lock. The synchronize_rcu() | |
264d4f88 AP |
656 | primitive write-acquires this same lock, then releases it. This means |
657 | that once synchronize_rcu() exits, all RCU read-side critical sections | |
658 | that were in progress before synchronize_rcu() was called are guaranteed | |
659 | to have completed -- there is no way that synchronize_rcu() would have | |
660 | been able to write-acquire the lock otherwise. The smp_mb__after_spinlock() | |
661 | promotes synchronize_rcu() to a full memory barrier in compliance with | |
662 | the "Memory-Barrier Guarantees" listed in: | |
663 | ||
ccc9971e | 664 | Documentation/RCU/Design/Requirements/Requirements.rst |
dd81eca8 PM |
665 | |
666 | It is possible to nest rcu_read_lock(), since reader-writer locks may | |
667 | be recursively acquired. Note also that rcu_read_lock() is immune | |
668 | from deadlock (an important property of RCU). The reason for this is | |
669 | that the only thing that can block rcu_read_lock() is a synchronize_rcu(). | |
670 | But synchronize_rcu() does not acquire any locks while holding rcu_gp_mutex, | |
671 | so there can be no deadlock cycle. | |
672 | ||
5e1bc932 PT |
673 | .. _quiz_1: |
674 | ||
675 | Quick Quiz #1: | |
676 | Why is this argument naive? How could a deadlock | |
dd81eca8 PM |
677 | occur when using this algorithm in a real-world Linux |
678 | kernel? How could this deadlock be avoided? | |
679 | ||
5e1bc932 | 680 | :ref:`Answers to Quick Quiz <8_whatisRCU>` |
dd81eca8 PM |
681 | |
682 | 5B. "TOY" EXAMPLE #2: CLASSIC RCU | |
5e1bc932 | 683 | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ |
dd81eca8 PM |
684 | This section presents a "toy" RCU implementation that is based on |
685 | "classic RCU". It is also short on performance (but only for updates) and | |
81ad58be | 686 | on features such as hotplug CPU and the ability to run in CONFIG_PREEMPTION |
dd81eca8 PM |
687 | kernels. The definitions of rcu_dereference() and rcu_assign_pointer() |
688 | are the same as those shown in the preceding section, so they are omitted. | |
5e1bc932 | 689 | :: |
dd81eca8 PM |
690 | |
691 | void rcu_read_lock(void) { } | |
692 | ||
693 | void rcu_read_unlock(void) { } | |
694 | ||
695 | void synchronize_rcu(void) | |
696 | { | |
697 | int cpu; | |
698 | ||
3c30a752 | 699 | for_each_possible_cpu(cpu) |
dd81eca8 PM |
700 | run_on(cpu); |
701 | } | |
702 | ||
703 | Note that rcu_read_lock() and rcu_read_unlock() do absolutely nothing. | |
704 | This is the great strength of classic RCU in a non-preemptive kernel: | |
705 | read-side overhead is precisely zero, at least on non-Alpha CPUs. | |
706 | And there is absolutely no way that rcu_read_lock() can possibly | |
707 | participate in a deadlock cycle! | |
708 | ||
709 | The implementation of synchronize_rcu() simply schedules itself on each | |
710 | CPU in turn. The run_on() primitive can be implemented straightforwardly | |
711 | in terms of the sched_setaffinity() primitive. Of course, a somewhat less | |
712 | "toy" implementation would restore the affinity upon completion rather | |
713 | than just leaving all tasks running on the last CPU, but when I said | |
5e1bc932 | 714 | "toy", I meant **toy**! |
dd81eca8 PM |
715 | |
716 | So how the heck is this supposed to work??? | |
717 | ||
718 | Remember that it is illegal to block while in an RCU read-side critical | |
719 | section. Therefore, if a given CPU executes a context switch, we know | |
720 | that it must have completed all preceding RCU read-side critical sections. | |
5e1bc932 | 721 | Once **all** CPUs have executed a context switch, then **all** preceding |
dd81eca8 PM |
722 | RCU read-side critical sections will have completed. |
723 | ||
724 | So, suppose that we remove a data item from its structure and then invoke | |
725 | synchronize_rcu(). Once synchronize_rcu() returns, we are guaranteed | |
726 | that there are no RCU read-side critical sections holding a reference | |
727 | to that data item, so we can safely reclaim it. | |
728 | ||
5e1bc932 PT |
729 | .. _quiz_2: |
730 | ||
731 | Quick Quiz #2: | |
732 | Give an example where Classic RCU's read-side | |
733 | overhead is **negative**. | |
734 | ||
735 | :ref:`Answers to Quick Quiz <8_whatisRCU>` | |
dd81eca8 | 736 | |
5e1bc932 PT |
737 | .. _quiz_3: |
738 | ||
739 | Quick Quiz #3: | |
740 | If it is illegal to block in an RCU read-side | |
dd81eca8 | 741 | critical section, what the heck do you do in |
81ad58be | 742 | CONFIG_PREEMPT_RT, where normal spinlocks can block??? |
dd81eca8 | 743 | |
5e1bc932 PT |
744 | :ref:`Answers to Quick Quiz <8_whatisRCU>` |
745 | ||
746 | .. _6_whatisRCU: | |
dd81eca8 PM |
747 | |
748 | 6. ANALOGY WITH READER-WRITER LOCKING | |
5e1bc932 | 749 | -------------------------------------- |
dd81eca8 PM |
750 | |
751 | Although RCU can be used in many different ways, a very common use of | |
752 | RCU is analogous to reader-writer locking. The following unified | |
753 | diff shows how closely related RCU and reader-writer locking can be. | |
5e1bc932 | 754 | :: |
dd81eca8 | 755 | |
70946a44 YD |
756 | @@ -5,5 +5,5 @@ struct el { |
757 | int data; | |
758 | /* Other data fields */ | |
759 | }; | |
760 | -rwlock_t listmutex; | |
761 | +spinlock_t listmutex; | |
762 | struct el head; | |
763 | ||
dd81eca8 PM |
764 | @@ -13,15 +14,15 @@ |
765 | struct list_head *lp; | |
766 | struct el *p; | |
767 | ||
70946a44 | 768 | - read_lock(&listmutex); |
dd81eca8 PM |
769 | - list_for_each_entry(p, head, lp) { |
770 | + rcu_read_lock(); | |
771 | + list_for_each_entry_rcu(p, head, lp) { | |
772 | if (p->key == key) { | |
773 | *result = p->data; | |
70946a44 | 774 | - read_unlock(&listmutex); |
dd81eca8 PM |
775 | + rcu_read_unlock(); |
776 | return 1; | |
777 | } | |
778 | } | |
70946a44 | 779 | - read_unlock(&listmutex); |
dd81eca8 PM |
780 | + rcu_read_unlock(); |
781 | return 0; | |
782 | } | |
783 | ||
784 | @@ -29,15 +30,16 @@ | |
785 | { | |
786 | struct el *p; | |
787 | ||
788 | - write_lock(&listmutex); | |
789 | + spin_lock(&listmutex); | |
790 | list_for_each_entry(p, head, lp) { | |
791 | if (p->key == key) { | |
82a854ec | 792 | - list_del(&p->list); |
dd81eca8 | 793 | - write_unlock(&listmutex); |
82a854ec | 794 | + list_del_rcu(&p->list); |
dd81eca8 PM |
795 | + spin_unlock(&listmutex); |
796 | + synchronize_rcu(); | |
797 | kfree(p); | |
798 | return 1; | |
799 | } | |
800 | } | |
801 | - write_unlock(&listmutex); | |
802 | + spin_unlock(&listmutex); | |
803 | return 0; | |
804 | } | |
805 | ||
5e1bc932 | 806 | Or, for those who prefer a side-by-side listing:: |
dd81eca8 PM |
807 | |
808 | 1 struct el { 1 struct el { | |
809 | 2 struct list_head list; 2 struct list_head list; | |
810 | 3 long key; 3 long key; | |
811 | 4 spinlock_t mutex; 4 spinlock_t mutex; | |
812 | 5 int data; 5 int data; | |
813 | 6 /* Other data fields */ 6 /* Other data fields */ | |
814 | 7 }; 7 }; | |
70946a44 | 815 | 8 rwlock_t listmutex; 8 spinlock_t listmutex; |
dd81eca8 PM |
816 | 9 struct el head; 9 struct el head; |
817 | ||
5e1bc932 PT |
818 | :: |
819 | ||
820 | 1 int search(long key, int *result) 1 int search(long key, int *result) | |
821 | 2 { 2 { | |
822 | 3 struct list_head *lp; 3 struct list_head *lp; | |
823 | 4 struct el *p; 4 struct el *p; | |
824 | 5 5 | |
825 | 6 read_lock(&listmutex); 6 rcu_read_lock(); | |
826 | 7 list_for_each_entry(p, head, lp) { 7 list_for_each_entry_rcu(p, head, lp) { | |
827 | 8 if (p->key == key) { 8 if (p->key == key) { | |
828 | 9 *result = p->data; 9 *result = p->data; | |
829 | 10 read_unlock(&listmutex); 10 rcu_read_unlock(); | |
830 | 11 return 1; 11 return 1; | |
831 | 12 } 12 } | |
832 | 13 } 13 } | |
833 | 14 read_unlock(&listmutex); 14 rcu_read_unlock(); | |
834 | 15 return 0; 15 return 0; | |
835 | 16 } 16 } | |
836 | ||
837 | :: | |
838 | ||
839 | 1 int delete(long key) 1 int delete(long key) | |
840 | 2 { 2 { | |
841 | 3 struct el *p; 3 struct el *p; | |
842 | 4 4 | |
843 | 5 write_lock(&listmutex); 5 spin_lock(&listmutex); | |
844 | 6 list_for_each_entry(p, head, lp) { 6 list_for_each_entry(p, head, lp) { | |
845 | 7 if (p->key == key) { 7 if (p->key == key) { | |
846 | 8 list_del(&p->list); 8 list_del_rcu(&p->list); | |
847 | 9 write_unlock(&listmutex); 9 spin_unlock(&listmutex); | |
848 | 10 synchronize_rcu(); | |
849 | 10 kfree(p); 11 kfree(p); | |
850 | 11 return 1; 12 return 1; | |
851 | 12 } 13 } | |
852 | 13 } 14 } | |
853 | 14 write_unlock(&listmutex); 15 spin_unlock(&listmutex); | |
854 | 15 return 0; 16 return 0; | |
855 | 16 } 17 } | |
dd81eca8 PM |
856 | |
857 | Either way, the differences are quite small. Read-side locking moves | |
858 | to rcu_read_lock() and rcu_read_unlock, update-side locking moves from | |
670e9f34 | 859 | a reader-writer lock to a simple spinlock, and a synchronize_rcu() |
dd81eca8 PM |
860 | precedes the kfree(). |
861 | ||
862 | However, there is one potential catch: the read-side and update-side | |
863 | critical sections can now run concurrently. In many cases, this will | |
864 | not be a problem, but it is necessary to check carefully regardless. | |
865 | For example, if multiple independent list updates must be seen as | |
866 | a single atomic update, converting to RCU will require special care. | |
867 | ||
868 | Also, the presence of synchronize_rcu() means that the RCU version of | |
869 | delete() can now block. If this is a problem, there is a callback-based | |
57d34a6c KC |
870 | mechanism that never blocks, namely call_rcu() or kfree_rcu(), that can |
871 | be used in place of synchronize_rcu(). | |
dd81eca8 | 872 | |
5e1bc932 | 873 | .. _7_whatisRCU: |
dd81eca8 PM |
874 | |
875 | 7. FULL LIST OF RCU APIs | |
5e1bc932 | 876 | ------------------------- |
dd81eca8 PM |
877 | |
878 | The RCU APIs are documented in docbook-format header comments in the | |
879 | Linux-kernel source code, but it helps to have a full list of the | |
880 | APIs, since there does not appear to be a way to categorize them | |
881 | in docbook. Here is the list, by category. | |
882 | ||
5e1bc932 | 883 | RCU list traversal:: |
dd81eca8 | 884 | |
d07e6d08 | 885 | list_entry_rcu |
17f0da13 | 886 | list_entry_lockless |
d07e6d08 PM |
887 | list_first_entry_rcu |
888 | list_next_rcu | |
32300751 | 889 | list_for_each_entry_rcu |
d07e6d08 | 890 | list_for_each_entry_continue_rcu |
b7b6f94c | 891 | list_for_each_entry_from_rcu |
17f0da13 MB |
892 | list_first_or_null_rcu |
893 | list_next_or_null_rcu | |
d07e6d08 PM |
894 | hlist_first_rcu |
895 | hlist_next_rcu | |
896 | hlist_pprev_rcu | |
32300751 | 897 | hlist_for_each_entry_rcu |
d07e6d08 | 898 | hlist_for_each_entry_rcu_bh |
b7b6f94c | 899 | hlist_for_each_entry_from_rcu |
d07e6d08 PM |
900 | hlist_for_each_entry_continue_rcu |
901 | hlist_for_each_entry_continue_rcu_bh | |
902 | hlist_nulls_first_rcu | |
240ebbf8 | 903 | hlist_nulls_for_each_entry_rcu |
d07e6d08 PM |
904 | hlist_bl_first_rcu |
905 | hlist_bl_for_each_entry_rcu | |
dd81eca8 | 906 | |
17f0da13 | 907 | RCU pointer/list update:: |
dd81eca8 PM |
908 | |
909 | rcu_assign_pointer | |
910 | list_add_rcu | |
911 | list_add_tail_rcu | |
912 | list_del_rcu | |
913 | list_replace_rcu | |
1d023284 | 914 | hlist_add_behind_rcu |
32300751 | 915 | hlist_add_before_rcu |
dd81eca8 | 916 | hlist_add_head_rcu |
17f0da13 | 917 | hlist_add_tail_rcu |
d07e6d08 PM |
918 | hlist_del_rcu |
919 | hlist_del_init_rcu | |
32300751 | 920 | hlist_replace_rcu |
17f0da13 MB |
921 | list_splice_init_rcu |
922 | list_splice_tail_init_rcu | |
d07e6d08 PM |
923 | hlist_nulls_del_init_rcu |
924 | hlist_nulls_del_rcu | |
925 | hlist_nulls_add_head_rcu | |
926 | hlist_bl_add_head_rcu | |
927 | hlist_bl_del_init_rcu | |
928 | hlist_bl_del_rcu | |
929 | hlist_bl_set_first_rcu | |
dd81eca8 | 930 | |
5e1bc932 PT |
931 | RCU:: |
932 | ||
933 | Critical sections Grace period Barrier | |
32300751 PM |
934 | |
935 | rcu_read_lock synchronize_net rcu_barrier | |
936 | rcu_read_unlock synchronize_rcu | |
c598a070 | 937 | rcu_dereference synchronize_rcu_expedited |
d07e6d08 PM |
938 | rcu_read_lock_held call_rcu |
939 | rcu_dereference_check kfree_rcu | |
940 | rcu_dereference_protected | |
32300751 | 941 | |
5e1bc932 PT |
942 | bh:: |
943 | ||
944 | Critical sections Grace period Barrier | |
32300751 | 945 | |
33984964 JFG |
946 | rcu_read_lock_bh call_rcu rcu_barrier |
947 | rcu_read_unlock_bh synchronize_rcu | |
948 | [local_bh_disable] synchronize_rcu_expedited | |
949 | [and friends] | |
950 | rcu_dereference_bh | |
d07e6d08 PM |
951 | rcu_dereference_bh_check |
952 | rcu_dereference_bh_protected | |
953 | rcu_read_lock_bh_held | |
32300751 | 954 | |
5e1bc932 PT |
955 | sched:: |
956 | ||
957 | Critical sections Grace period Barrier | |
32300751 | 958 | |
33984964 JFG |
959 | rcu_read_lock_sched call_rcu rcu_barrier |
960 | rcu_read_unlock_sched synchronize_rcu | |
961 | [preempt_disable] synchronize_rcu_expedited | |
240ebbf8 | 962 | [and friends] |
d07e6d08 PM |
963 | rcu_read_lock_sched_notrace |
964 | rcu_read_unlock_sched_notrace | |
c598a070 | 965 | rcu_dereference_sched |
d07e6d08 PM |
966 | rcu_dereference_sched_check |
967 | rcu_dereference_sched_protected | |
968 | rcu_read_lock_sched_held | |
32300751 PM |
969 | |
970 | ||
5e1bc932 PT |
971 | SRCU:: |
972 | ||
973 | Critical sections Grace period Barrier | |
32300751 | 974 | |
33984964 JFG |
975 | srcu_read_lock call_srcu srcu_barrier |
976 | srcu_read_unlock synchronize_srcu | |
99f88919 | 977 | srcu_dereference synchronize_srcu_expedited |
d07e6d08 PM |
978 | srcu_dereference_check |
979 | srcu_read_lock_held | |
dd81eca8 | 980 | |
5e1bc932 PT |
981 | SRCU: Initialization/cleanup:: |
982 | ||
4de5f89e PM |
983 | DEFINE_SRCU |
984 | DEFINE_STATIC_SRCU | |
240ebbf8 PM |
985 | init_srcu_struct |
986 | cleanup_srcu_struct | |
dd81eca8 | 987 | |
5e1bc932 | 988 | All: lockdep-checked RCU-protected pointer access:: |
50aec002 | 989 | |
50aec002 | 990 | rcu_access_pointer |
d07e6d08 | 991 | rcu_dereference_raw |
f78f5b90 | 992 | RCU_LOCKDEP_WARN |
d07e6d08 PM |
993 | rcu_sleep_check |
994 | RCU_NONIDLE | |
50aec002 | 995 | |
dd81eca8 PM |
996 | See the comment headers in the source code (or the docbook generated |
997 | from them) for more information. | |
998 | ||
fea65126 PM |
999 | However, given that there are no fewer than four families of RCU APIs |
1000 | in the Linux kernel, how do you choose which one to use? The following | |
1001 | list can be helpful: | |
1002 | ||
1003 | a. Will readers need to block? If so, you need SRCU. | |
1004 | ||
99f88919 | 1005 | b. What about the -rt patchset? If readers would need to block |
fea65126 PM |
1006 | in an non-rt kernel, you need SRCU. If readers would block |
1007 | in a -rt kernel, but not in a non-rt kernel, SRCU is not | |
4de5f89e PM |
1008 | necessary. (The -rt patchset turns spinlocks into sleeplocks, |
1009 | hence this distinction.) | |
fea65126 | 1010 | |
99f88919 | 1011 | c. Do you need to treat NMI handlers, hardirq handlers, |
fea65126 PM |
1012 | and code segments with preemption disabled (whether |
1013 | via preempt_disable(), local_irq_save(), local_bh_disable(), | |
1014 | or some other mechanism) as if they were explicit RCU readers? | |
2aef619c | 1015 | If so, RCU-sched is the only choice that will work for you. |
fea65126 | 1016 | |
99f88919 | 1017 | d. Do you need RCU grace periods to complete even in the face |
fea65126 PM |
1018 | of softirq monopolization of one or more of the CPUs? For |
1019 | example, is your code subject to network-based denial-of-service | |
77095901 PM |
1020 | attacks? If so, you should disable softirq across your readers, |
1021 | for example, by using rcu_read_lock_bh(). | |
fea65126 | 1022 | |
99f88919 | 1023 | e. Is your workload too update-intensive for normal use of |
fea65126 | 1024 | RCU, but inappropriate for other synchronization mechanisms? |
5f0d5a3a PM |
1025 | If so, consider SLAB_TYPESAFE_BY_RCU (which was originally |
1026 | named SLAB_DESTROY_BY_RCU). But please be careful! | |
fea65126 | 1027 | |
99f88919 | 1028 | f. Do you need read-side critical sections that are respected |
2aef619c PM |
1029 | even though they are in the middle of the idle loop, during |
1030 | user-mode execution, or on an offlined CPU? If so, SRCU is the | |
1031 | only choice that will work for you. | |
1032 | ||
99f88919 | 1033 | g. Otherwise, use RCU. |
fea65126 PM |
1034 | |
1035 | Of course, this all assumes that you have determined that RCU is in fact | |
1036 | the right tool for your job. | |
1037 | ||
5e1bc932 | 1038 | .. _8_whatisRCU: |
dd81eca8 PM |
1039 | |
1040 | 8. ANSWERS TO QUICK QUIZZES | |
5e1bc932 | 1041 | ---------------------------- |
dd81eca8 | 1042 | |
5e1bc932 PT |
1043 | Quick Quiz #1: |
1044 | Why is this argument naive? How could a deadlock | |
dd81eca8 PM |
1045 | occur when using this algorithm in a real-world Linux |
1046 | kernel? [Referring to the lock-based "toy" RCU | |
1047 | algorithm.] | |
1048 | ||
5e1bc932 PT |
1049 | Answer: |
1050 | Consider the following sequence of events: | |
dd81eca8 PM |
1051 | |
1052 | 1. CPU 0 acquires some unrelated lock, call it | |
d19720a9 PM |
1053 | "problematic_lock", disabling irq via |
1054 | spin_lock_irqsave(). | |
dd81eca8 PM |
1055 | |
1056 | 2. CPU 1 enters synchronize_rcu(), write-acquiring | |
1057 | rcu_gp_mutex. | |
1058 | ||
1059 | 3. CPU 0 enters rcu_read_lock(), but must wait | |
1060 | because CPU 1 holds rcu_gp_mutex. | |
1061 | ||
1062 | 4. CPU 1 is interrupted, and the irq handler | |
1063 | attempts to acquire problematic_lock. | |
1064 | ||
1065 | The system is now deadlocked. | |
1066 | ||
1067 | One way to avoid this deadlock is to use an approach like | |
1068 | that of CONFIG_PREEMPT_RT, where all normal spinlocks | |
1069 | become blocking locks, and all irq handlers execute in | |
1070 | the context of special tasks. In this case, in step 4 | |
1071 | above, the irq handler would block, allowing CPU 1 to | |
1072 | release rcu_gp_mutex, avoiding the deadlock. | |
1073 | ||
1074 | Even in the absence of deadlock, this RCU implementation | |
1075 | allows latency to "bleed" from readers to other | |
1076 | readers through synchronize_rcu(). To see this, | |
1077 | consider task A in an RCU read-side critical section | |
1078 | (thus read-holding rcu_gp_mutex), task B blocked | |
1079 | attempting to write-acquire rcu_gp_mutex, and | |
1080 | task C blocked in rcu_read_lock() attempting to | |
1081 | read_acquire rcu_gp_mutex. Task A's RCU read-side | |
1082 | latency is holding up task C, albeit indirectly via | |
1083 | task B. | |
1084 | ||
1085 | Realtime RCU implementations therefore use a counter-based | |
1086 | approach where tasks in RCU read-side critical sections | |
1087 | cannot be blocked by tasks executing synchronize_rcu(). | |
1088 | ||
5e1bc932 PT |
1089 | :ref:`Back to Quick Quiz #1 <quiz_1>` |
1090 | ||
1091 | Quick Quiz #2: | |
1092 | Give an example where Classic RCU's read-side | |
1093 | overhead is **negative**. | |
dd81eca8 | 1094 | |
5e1bc932 | 1095 | Answer: |
81ad58be | 1096 | Imagine a single-CPU system with a non-CONFIG_PREEMPTION |
dd81eca8 PM |
1097 | kernel where a routing table is used by process-context |
1098 | code, but can be updated by irq-context code (for example, | |
1099 | by an "ICMP REDIRECT" packet). The usual way of handling | |
1100 | this would be to have the process-context code disable | |
1101 | interrupts while searching the routing table. Use of | |
1102 | RCU allows such interrupt-disabling to be dispensed with. | |
1103 | Thus, without RCU, you pay the cost of disabling interrupts, | |
1104 | and with RCU you don't. | |
1105 | ||
1106 | One can argue that the overhead of RCU in this | |
1107 | case is negative with respect to the single-CPU | |
1108 | interrupt-disabling approach. Others might argue that | |
1109 | the overhead of RCU is merely zero, and that replacing | |
1110 | the positive overhead of the interrupt-disabling scheme | |
1111 | with the zero-overhead RCU scheme does not constitute | |
1112 | negative overhead. | |
1113 | ||
1114 | In real life, of course, things are more complex. But | |
1115 | even the theoretical possibility of negative overhead for | |
1116 | a synchronization primitive is a bit unexpected. ;-) | |
1117 | ||
5e1bc932 PT |
1118 | :ref:`Back to Quick Quiz #2 <quiz_2>` |
1119 | ||
1120 | Quick Quiz #3: | |
1121 | If it is illegal to block in an RCU read-side | |
dd81eca8 | 1122 | critical section, what the heck do you do in |
81ad58be | 1123 | CONFIG_PREEMPT_RT, where normal spinlocks can block??? |
dd81eca8 | 1124 | |
5e1bc932 | 1125 | Answer: |
81ad58be | 1126 | Just as CONFIG_PREEMPT_RT permits preemption of spinlock |
dd81eca8 PM |
1127 | critical sections, it permits preemption of RCU |
1128 | read-side critical sections. It also permits | |
1129 | spinlocks blocking while in RCU read-side critical | |
1130 | sections. | |
1131 | ||
33984964 | 1132 | Why the apparent inconsistency? Because it is |
dd81eca8 PM |
1133 | possible to use priority boosting to keep the RCU |
1134 | grace periods short if need be (for example, if running | |
1135 | short of memory). In contrast, if blocking waiting | |
1136 | for (say) network reception, there is no way to know | |
1137 | what should be boosted. Especially given that the | |
1138 | process we need to boost might well be a human being | |
1139 | who just went out for a pizza or something. And although | |
1140 | a computer-operated cattle prod might arouse serious | |
1141 | interest, it might also provoke serious objections. | |
1142 | Besides, how does the computer know what pizza parlor | |
1143 | the human being went to??? | |
1144 | ||
5e1bc932 | 1145 | :ref:`Back to Quick Quiz #3 <quiz_3>` |
dd81eca8 PM |
1146 | |
1147 | ACKNOWLEDGEMENTS | |
1148 | ||
1149 | My thanks to the people who helped make this human-readable, including | |
d19720a9 | 1150 | Jon Walpole, Josh Triplett, Serge Hallyn, Suzanne Wood, and Alan Stern. |
dd81eca8 PM |
1151 | |
1152 | ||
1153 | For more information, see http://www.rdrop.com/users/paulmck/RCU. |