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