1.. _whatisrcu_doc: 2 3What is RCU? -- "Read, Copy, Update" 4====================================== 5 6Please note that the "What is RCU?" LWN series is an excellent place 7to start learning about RCU: 8 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/ 16 17 18What is RCU? 19 20RCU is a synchronization mechanism that was added to the Linux kernel 21during the 2.5 development effort that is optimized for read-mostly 22situations. Although RCU is actually quite simple once you understand it, 23getting there can sometimes be a challenge. Part of the problem is that 24most of the past descriptions of RCU have been written with the mistaken 25assumption that there is "one true way" to describe RCU. Instead, 26the experience has been that different people must take different paths 27to arrive at an understanding of RCU. This document provides several 28different paths, as follows: 29 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>` 45 46People who prefer starting with a conceptual overview should focus on 47Section 1, though most readers will profit by reading this section at 48some point. People who prefer to start with an API that they can then 49experiment with should focus on Section 2. People who prefer to start 50with example uses should focus on Sections 3 and 4. People who need to 51understand the RCU implementation should focus on Section 5, then dive 52into the kernel source code. People who reason best by analogy should 53focus on Section 6. Section 7 serves as an index to the docbook API 54documentation, and Section 8 is the traditional answer key. 55 56So, start with the section that makes the most sense to you and your 57preferred method of learning. If you need to know everything about 58everything, feel free to read the whole thing -- but if you are really 59that type of person, you have perused the source code and will therefore 60never need this document anyway. ;-) 61 62.. _1_whatisRCU: 63 641. RCU OVERVIEW 65---------------- 66 67The basic idea behind RCU is to split updates into "removal" and 68"reclamation" phases. The removal phase removes references to data items 69within a data structure (possibly by replacing them with references to 70new versions of these data items), and can run concurrently with readers. 71The reason that it is safe to run the removal phase concurrently with 72readers is the semantics of modern CPUs guarantee that readers will see 73either the old or the new version of the data structure rather than a 74partially updated reference. The reclamation phase does the work of reclaiming 75(e.g., freeing) the data items removed from the data structure during the 76removal phase. Because reclaiming data items can disrupt any readers 77concurrently referencing those data items, the reclamation phase must 78not start until readers no longer hold references to those data items. 79 80Splitting the update into removal and reclamation phases permits the 81updater to perform the removal phase immediately, and to defer the 82reclamation phase until all readers active during the removal phase have 83completed, either by blocking until they finish or by registering a 84callback that is invoked after they finish. Only readers that are active 85during the removal phase need be considered, because any reader starting 86after the removal phase will be unable to gain a reference to the removed 87data items, and therefore cannot be disrupted by the reclamation phase. 88 89So the typical RCU update sequence goes something like the following: 90 91a. Remove pointers to a data structure, so that subsequent 92 readers cannot gain a reference to it. 93 94b. Wait for all previous readers to complete their RCU read-side 95 critical sections. 96 97c. 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 101Step (b) above is the key idea underlying RCU's deferred destruction. 102The ability to wait until all readers are done allows RCU readers to 103use much lighter-weight synchronization, in some cases, absolutely no 104synchronization at all. In contrast, in more conventional lock-based 105schemes, readers must use heavy-weight synchronization in order to 106prevent an updater from deleting the data structure out from under them. 107This is because lock-based updaters typically update data items in place, 108and must therefore exclude readers. In contrast, RCU-based updaters 109typically take advantage of the fact that writes to single aligned 110pointers are atomic on modern CPUs, allowing atomic insertion, removal, 111and replacement of data items in a linked structure without disrupting 112readers. Concurrent RCU readers can then continue accessing the old 113versions, and can dispense with the atomic operations, memory barriers, 114and communications cache misses that are so expensive on present-day 115SMP computer systems, even in absence of lock contention. 116 117In the three-step procedure shown above, the updater is performing both 118the removal and the reclamation step, but it is often helpful for an 119entirely different thread to do the reclamation, as is in fact the case 120in the Linux kernel's directory-entry cache (dcache). Even if the same 121thread performs both the update step (step (a) above) and the reclamation 122step (step (c) above), it is often helpful to think of them separately. 123For example, RCU readers and updaters need not communicate at all, 124but RCU provides implicit low-overhead communication between readers 125and reclaimers, namely, in step (b) above. 126 127So how the heck can a reclaimer tell when a reader is done, given 128that readers are not doing any sort of synchronization operations??? 129Read on to learn about how RCU's API makes this easy. 130 131.. _2_whatisRCU: 132 1332. WHAT IS RCU'S CORE API? 134--------------------------- 135 136The core RCU API is quite small: 137 138a. rcu_read_lock() 139b. rcu_read_unlock() 140c. synchronize_rcu() / call_rcu() 141d. rcu_assign_pointer() 142e. rcu_dereference() 143 144There are many other members of the RCU API, but the rest can be 145expressed in terms of these five, though most implementations instead 146express synchronize_rcu() in terms of the call_rcu() callback API. 147 148The five core RCU APIs are described below, the other 18 will be enumerated 149later. See the kernel docbook documentation for more info, or look directly 150at the function header comments. 151 152rcu_read_lock() 153^^^^^^^^^^^^^^^ 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 159 kernels built with CONFIG_PREEMPT_RCU can preempt RCU 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. 163 Reference counts may be used in conjunction with RCU to maintain 164 longer-term references to data structures. 165 166rcu_read_unlock() 167^^^^^^^^^^^^^^^^^ 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 174synchronize_rcu() 175^^^^^^^^^^^^^^^^^ 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. 181 Note that synchronize_rcu() will **not** necessarily wait for 182 any subsequent RCU read-side critical sections to complete. 183 For example, consider the following sequence of events:: 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 199 **immediately** after the last pre-existing RCU read-side critical 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 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. 226 227rcu_assign_pointer() 228^^^^^^^^^^^^^^^^^^^^ 229 void rcu_assign_pointer(p, typeof(p) v); 230 231 Yes, rcu_assign_pointer() **is** implemented as a macro, though it 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 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. 240 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(). 246 247rcu_dereference() 248^^^^^^^^^^^^^^^^^ 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 256 dereferenced. Note that rcu_dereference() does not actually 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 265 this local variable, for example as follows:: 266 267 p = rcu_dereference(head.next); 268 return p->data; 269 270 However, in this case, one could just as easily combine these 271 into one statement:: 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 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. 281 282 Note that the value returned by rcu_dereference() is valid 283 only within the enclosing RCU read-side critical section [1]_. 284 For example, the following is **not** legal:: 285 286 rcu_read_lock(); 287 p = rcu_dereference(head.next); 288 rcu_read_unlock(); 289 x = p->address; /* BUG!!! */ 290 rcu_read_lock(); 291 y = p->data; /* BUG!!! */ 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 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 307 primitives, such as list_for_each_entry_rcu() [2]_. 308 309.. [1] The variant rcu_dereference_protected() can be used outside 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, 319 a lockdep splat is emitted. See Documentation/RCU/Design/Requirements/Requirements.rst 320 and the API's code comments for more details and example usage. 321 322.. [2] If the list_for_each_entry_rcu() instance might be used by 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 330The following diagram shows how each API communicates among the 331reader, updater, and reclaimer. 332:: 333 334 335 rcu_assign_pointer() 336 +--------+ 337 +---------------------->| reader |---------+ 338 | +--------+ | 339 | | | 340 | | | Protect: 341 | | | rcu_read_lock() 342 | | | rcu_read_unlock() 343 | rcu_dereference() | | 344 +---------+ | | 345 | updater |<----------------+ | 346 +---------+ V 347 | +-----------+ 348 +----------------------------------->| reclaimer | 349 +-----------+ 350 Defer: 351 synchronize_rcu() & call_rcu() 352 353 354The RCU infrastructure observes the time sequence of rcu_read_lock(), 355rcu_read_unlock(), synchronize_rcu(), and call_rcu() invocations in 356order to determine when (1) synchronize_rcu() invocations may return 357to their callers and (2) call_rcu() callbacks may be invoked. Efficient 358implementations of the RCU infrastructure make heavy use of batching in 359order to amortize their overhead over many uses of the corresponding APIs. 360 361There are at least three flavors of RCU usage in the Linux kernel. The diagram 362above shows the most common one. On the updater side, the rcu_assign_pointer(), 363synchronize_rcu() and call_rcu() primitives used are the same for all three 364flavors. However for protection (on the reader side), the primitives used vary 365depending on the flavor: 366 367a. rcu_read_lock() / rcu_read_unlock() 368 rcu_dereference() 369 370b. rcu_read_lock_bh() / rcu_read_unlock_bh() 371 local_bh_disable() / local_bh_enable() 372 rcu_dereference_bh() 373 374c. 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() 380 381These three flavors are used as follows: 382 383a. RCU applied to normal data structures. 384 385b. RCU applied to networking data structures that may be subjected 386 to remote denial-of-service attacks. 387 388c. RCU applied to scheduler and interrupt/NMI-handler tasks. 389 390Again, most uses will be of (a). The (b) and (c) cases are important 391for specialized uses, but are relatively uncommon. 392 393.. _3_whatisRCU: 394 3953. WHAT ARE SOME EXAMPLE USES OF CORE RCU API? 396----------------------------------------------- 397 398This section shows a simple use of the core RCU API to protect a 399global pointer to a dynamically allocated structure. More-typical 400uses 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:: 403 404 struct foo { 405 int a; 406 char b; 407 long c; 408 }; 409 DEFINE_SPINLOCK(foo_mutex); 410 411 struct foo __rcu *gbl_foo; 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 431 new_fp = kmalloc(sizeof(*new_fp), GFP_KERNEL); 432 spin_lock(&foo_mutex); 433 old_fp = rcu_dereference_protected(gbl_foo, lockdep_is_held(&foo_mutex)); 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 460So, to sum up: 461 462- Use rcu_read_lock() and rcu_read_unlock() to guard RCU 463 read-side critical sections. 464 465- Within an RCU read-side critical section, use rcu_dereference() 466 to dereference RCU-protected pointers. 467 468- Use some solid scheme (such as locks or semaphores) to 469 keep concurrent updates from interfering with each other. 470 471- Use rcu_assign_pointer() to update an RCU-protected pointer. 472 This primitive protects concurrent readers from the updater, 473 **not** concurrent updates from each other! You therefore still 474 need to use locking (or something similar) to keep concurrent 475 rcu_assign_pointer() primitives from interfering with each other. 476 477- Use synchronize_rcu() **after** removing a data element from an 478 RCU-protected data structure, but **before** reclaiming/freeing 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 483See checklist.txt for additional rules to follow when using RCU. 484And 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>`. 487 488.. _4_whatisRCU: 489 4904. WHAT IF MY UPDATING THREAD CANNOT BLOCK? 491-------------------------------------------- 492 493In the example above, foo_update_a() blocks until a grace period elapses. 494This is quite simple, but in some cases one cannot afford to wait so 495long -- there might be other high-priority work to be done. 496 497In such cases, one uses call_rcu() rather than synchronize_rcu(). 498The call_rcu() API is as follows:: 499 500 void call_rcu(struct rcu_head *head, rcu_callback_t func); 501 502This function invokes func(head) after a grace period has elapsed. 503This invocation might happen from either softirq or process context, 504so the function is not permitted to block. The foo struct needs to 505have an rcu_head structure added, perhaps as follows:: 506 507 struct foo { 508 int a; 509 char b; 510 long c; 511 struct rcu_head rcu; 512 }; 513 514The foo_update_a() function might then be written as follows:: 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 534 new_fp = kmalloc(sizeof(*new_fp), GFP_KERNEL); 535 spin_lock(&foo_mutex); 536 old_fp = rcu_dereference_protected(gbl_foo, lockdep_is_held(&foo_mutex)); 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 544The foo_reclaim() function might appear as follows:: 545 546 void foo_reclaim(struct rcu_head *rp) 547 { 548 struct foo *fp = container_of(rp, struct foo, rcu); 549 550 foo_cleanup(fp->a); 551 552 kfree(fp); 553 } 554 555The container_of() primitive is a macro that, given a pointer into a 556struct, the type of the struct, and the pointed-to field within the 557struct, returns a pointer to the beginning of the struct. 558 559The use of call_rcu() permits the caller of foo_update_a() to 560immediately regain control, without needing to worry further about the 561old version of the newly updated element. It also clearly shows the 562RCU distinction between updater, namely foo_update_a(), and reclaimer, 563namely foo_reclaim(). 564 565The summary of advice is the same as for the previous section, except 566that we are now using call_rcu() rather than synchronize_rcu(): 567 568- Use call_rcu() **after** removing a data element from an 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 574If the callback for call_rcu() is not doing anything more than calling 575kfree() on the structure, you can use kfree_rcu() instead of call_rcu() 576to avoid having to write your own callback:: 577 578 kfree_rcu(old_fp, rcu); 579 580Again, see checklist.txt for additional rules governing the use of RCU. 581 582.. _5_whatisRCU: 583 5845. WHAT ARE SOME SIMPLE IMPLEMENTATIONS OF RCU? 585------------------------------------------------ 586 587One of the nice things about RCU is that it has extremely simple "toy" 588implementations that are a good first step towards understanding the 589production-quality implementations in the Linux kernel. This section 590presents two such "toy" implementations of RCU, one that is implemented 591in terms of familiar locking primitives, and another that more closely 592resembles "classic" RCU. Both are way too simple for real-world use, 593lacking both functionality and performance. However, they are useful 594in getting a feel for how RCU works. See kernel/rcu/update.c for a 595production-quality implementation, and see: 596 597 http://www.rdrop.com/users/paulmck/RCU 598 599for papers describing the Linux kernel RCU implementation. The OLS'01 600and OLS'02 papers are a good introduction, and the dissertation provides 601more details on the current implementation as of early 2004. 602 603 6045A. "TOY" IMPLEMENTATION #1: LOCKING 605^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 606This section presents a "toy" RCU implementation that is based on 607familiar locking primitives. Its overhead makes it a non-starter for 608real-life use, as does its lack of scalability. It is also unsuitable 609for realtime use, since it allows scheduling latency to "bleed" from 610one read-side critical section to another. It also assumes recursive 611reader-writer locks: If you try this with non-recursive locks, and 612you allow nested rcu_read_lock() calls, you can deadlock. 613 614However, it is probably the easiest implementation to relate to, so is 615a good starting point. 616 617It is extremely simple:: 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); 634 smp_mb__after_spinlock(); 635 write_unlock(&rcu_gp_mutex); 636 } 637 638[You can ignore rcu_assign_pointer() and rcu_dereference() without missing 639much. But here are simplified versions anyway. And whatever you do, 640don't forget about them when submitting patches making use of RCU!]:: 641 642 #define rcu_assign_pointer(p, v) \ 643 ({ \ 644 smp_store_release(&(p), (v)); \ 645 }) 646 647 #define rcu_dereference(p) \ 648 ({ \ 649 typeof(p) _________p1 = READ_ONCE(p); \ 650 (_________p1); \ 651 }) 652 653 654The rcu_read_lock() and rcu_read_unlock() primitive read-acquire 655and release a global reader-writer lock. The synchronize_rcu() 656primitive write-acquires this same lock, then releases it. This means 657that once synchronize_rcu() exits, all RCU read-side critical sections 658that were in progress before synchronize_rcu() was called are guaranteed 659to have completed -- there is no way that synchronize_rcu() would have 660been able to write-acquire the lock otherwise. The smp_mb__after_spinlock() 661promotes synchronize_rcu() to a full memory barrier in compliance with 662the "Memory-Barrier Guarantees" listed in: 663 664 Documentation/RCU/Design/Requirements/Requirements.rst 665 666It is possible to nest rcu_read_lock(), since reader-writer locks may 667be recursively acquired. Note also that rcu_read_lock() is immune 668from deadlock (an important property of RCU). The reason for this is 669that the only thing that can block rcu_read_lock() is a synchronize_rcu(). 670But synchronize_rcu() does not acquire any locks while holding rcu_gp_mutex, 671so there can be no deadlock cycle. 672 673.. _quiz_1: 674 675Quick Quiz #1: 676 Why is this argument naive? How could a deadlock 677 occur when using this algorithm in a real-world Linux 678 kernel? How could this deadlock be avoided? 679 680:ref:`Answers to Quick Quiz <8_whatisRCU>` 681 6825B. "TOY" EXAMPLE #2: CLASSIC RCU 683^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 684This section presents a "toy" RCU implementation that is based on 685"classic RCU". It is also short on performance (but only for updates) and 686on features such as hotplug CPU and the ability to run in CONFIG_PREEMPTION 687kernels. The definitions of rcu_dereference() and rcu_assign_pointer() 688are the same as those shown in the preceding section, so they are omitted. 689:: 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 699 for_each_possible_cpu(cpu) 700 run_on(cpu); 701 } 702 703Note that rcu_read_lock() and rcu_read_unlock() do absolutely nothing. 704This is the great strength of classic RCU in a non-preemptive kernel: 705read-side overhead is precisely zero, at least on non-Alpha CPUs. 706And there is absolutely no way that rcu_read_lock() can possibly 707participate in a deadlock cycle! 708 709The implementation of synchronize_rcu() simply schedules itself on each 710CPU in turn. The run_on() primitive can be implemented straightforwardly 711in terms of the sched_setaffinity() primitive. Of course, a somewhat less 712"toy" implementation would restore the affinity upon completion rather 713than just leaving all tasks running on the last CPU, but when I said 714"toy", I meant **toy**! 715 716So how the heck is this supposed to work??? 717 718Remember that it is illegal to block while in an RCU read-side critical 719section. Therefore, if a given CPU executes a context switch, we know 720that it must have completed all preceding RCU read-side critical sections. 721Once **all** CPUs have executed a context switch, then **all** preceding 722RCU read-side critical sections will have completed. 723 724So, suppose that we remove a data item from its structure and then invoke 725synchronize_rcu(). Once synchronize_rcu() returns, we are guaranteed 726that there are no RCU read-side critical sections holding a reference 727to that data item, so we can safely reclaim it. 728 729.. _quiz_2: 730 731Quick 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>` 736 737.. _quiz_3: 738 739Quick Quiz #3: 740 If it is illegal to block in an RCU read-side 741 critical section, what the heck do you do in 742 CONFIG_PREEMPT_RT, where normal spinlocks can block??? 743 744:ref:`Answers to Quick Quiz <8_whatisRCU>` 745 746.. _6_whatisRCU: 747 7486. ANALOGY WITH READER-WRITER LOCKING 749-------------------------------------- 750 751Although RCU can be used in many different ways, a very common use of 752RCU is analogous to reader-writer locking. The following unified 753diff shows how closely related RCU and reader-writer locking can be. 754:: 755 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 764 @@ -13,15 +14,15 @@ 765 struct list_head *lp; 766 struct el *p; 767 768 - read_lock(&listmutex); 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; 774 - read_unlock(&listmutex); 775 + rcu_read_unlock(); 776 return 1; 777 } 778 } 779 - read_unlock(&listmutex); 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) { 792 - list_del(&p->list); 793 - write_unlock(&listmutex); 794 + list_del_rcu(&p->list); 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 806Or, for those who prefer a side-by-side listing:: 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 }; 815 8 rwlock_t listmutex; 8 spinlock_t listmutex; 816 9 struct el head; 9 struct el head; 817 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 } 856 857Either way, the differences are quite small. Read-side locking moves 858to rcu_read_lock() and rcu_read_unlock, update-side locking moves from 859a reader-writer lock to a simple spinlock, and a synchronize_rcu() 860precedes the kfree(). 861 862However, there is one potential catch: the read-side and update-side 863critical sections can now run concurrently. In many cases, this will 864not be a problem, but it is necessary to check carefully regardless. 865For example, if multiple independent list updates must be seen as 866a single atomic update, converting to RCU will require special care. 867 868Also, the presence of synchronize_rcu() means that the RCU version of 869delete() can now block. If this is a problem, there is a callback-based 870mechanism that never blocks, namely call_rcu() or kfree_rcu(), that can 871be used in place of synchronize_rcu(). 872 873.. _7_whatisRCU: 874 8757. FULL LIST OF RCU APIs 876------------------------- 877 878The RCU APIs are documented in docbook-format header comments in the 879Linux-kernel source code, but it helps to have a full list of the 880APIs, since there does not appear to be a way to categorize them 881in docbook. Here is the list, by category. 882 883RCU list traversal:: 884 885 list_entry_rcu 886 list_entry_lockless 887 list_first_entry_rcu 888 list_next_rcu 889 list_for_each_entry_rcu 890 list_for_each_entry_continue_rcu 891 list_for_each_entry_from_rcu 892 list_first_or_null_rcu 893 list_next_or_null_rcu 894 hlist_first_rcu 895 hlist_next_rcu 896 hlist_pprev_rcu 897 hlist_for_each_entry_rcu 898 hlist_for_each_entry_rcu_bh 899 hlist_for_each_entry_from_rcu 900 hlist_for_each_entry_continue_rcu 901 hlist_for_each_entry_continue_rcu_bh 902 hlist_nulls_first_rcu 903 hlist_nulls_for_each_entry_rcu 904 hlist_bl_first_rcu 905 hlist_bl_for_each_entry_rcu 906 907RCU pointer/list update:: 908 909 rcu_assign_pointer 910 list_add_rcu 911 list_add_tail_rcu 912 list_del_rcu 913 list_replace_rcu 914 hlist_add_behind_rcu 915 hlist_add_before_rcu 916 hlist_add_head_rcu 917 hlist_add_tail_rcu 918 hlist_del_rcu 919 hlist_del_init_rcu 920 hlist_replace_rcu 921 list_splice_init_rcu 922 list_splice_tail_init_rcu 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 930 931RCU:: 932 933 Critical sections Grace period Barrier 934 935 rcu_read_lock synchronize_net rcu_barrier 936 rcu_read_unlock synchronize_rcu 937 rcu_dereference synchronize_rcu_expedited 938 rcu_read_lock_held call_rcu 939 rcu_dereference_check kfree_rcu 940 rcu_dereference_protected 941 942bh:: 943 944 Critical sections Grace period Barrier 945 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 951 rcu_dereference_bh_check 952 rcu_dereference_bh_protected 953 rcu_read_lock_bh_held 954 955sched:: 956 957 Critical sections Grace period Barrier 958 959 rcu_read_lock_sched call_rcu rcu_barrier 960 rcu_read_unlock_sched synchronize_rcu 961 [preempt_disable] synchronize_rcu_expedited 962 [and friends] 963 rcu_read_lock_sched_notrace 964 rcu_read_unlock_sched_notrace 965 rcu_dereference_sched 966 rcu_dereference_sched_check 967 rcu_dereference_sched_protected 968 rcu_read_lock_sched_held 969 970 971SRCU:: 972 973 Critical sections Grace period Barrier 974 975 srcu_read_lock call_srcu srcu_barrier 976 srcu_read_unlock synchronize_srcu 977 srcu_dereference synchronize_srcu_expedited 978 srcu_dereference_check 979 srcu_read_lock_held 980 981SRCU: Initialization/cleanup:: 982 983 DEFINE_SRCU 984 DEFINE_STATIC_SRCU 985 init_srcu_struct 986 cleanup_srcu_struct 987 988All: lockdep-checked RCU-protected pointer access:: 989 990 rcu_access_pointer 991 rcu_dereference_raw 992 RCU_LOCKDEP_WARN 993 rcu_sleep_check 994 RCU_NONIDLE 995 996See the comment headers in the source code (or the docbook generated 997from them) for more information. 998 999However, given that there are no fewer than four families of RCU APIs 1000in the Linux kernel, how do you choose which one to use? The following
1001list can be helpful: 1002 1003a. Will readers need to block? If so, you need SRCU. 1004 1005b. What about the -rt patchset? If readers would need to block 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 1008 necessary. (The -rt patchset turns spinlocks into sleeplocks, 1009 hence this distinction.) 1010 1011c. Do you need to treat NMI handlers, hardirq handlers, 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? 1015 If so, RCU-sched is the only choice that will work for you. 1016 1017d. Do you need RCU grace periods to complete even in the face 1018 of softirq monopolization of one or more of the CPUs? For 1019 example, is your code subject to network-based denial-of-service 1020 attacks? If so, you should disable softirq across your readers, 1021 for example, by using rcu_read_lock_bh(). 1022 1023e. Is your workload too update-intensive for normal use of 1024 RCU, but inappropriate for other synchronization mechanisms? 1025 If so, consider SLAB_TYPESAFE_BY_RCU (which was originally 1026 named SLAB_DESTROY_BY_RCU). But please be careful! 1027 1028f. Do you need read-side critical sections that are respected 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 1033g. Otherwise, use RCU. 1034 1035Of course, this all assumes that you have determined that RCU is in fact 1036the right tool for your job. 1037 1038.. _8_whatisRCU: 1039 10408. ANSWERS TO QUICK QUIZZES 1041---------------------------- 1042 1043Quick Quiz #1: 1044 Why is this argument naive? How could a deadlock 1045 occur when using this algorithm in a real-world Linux 1046 kernel? [Referring to the lock-based "toy" RCU 1047 algorithm.] 1048 1049Answer: 1050 Consider the following sequence of events: 1051 1052 1. CPU 0 acquires some unrelated lock, call it 1053 "problematic_lock", disabling irq via 1054 spin_lock_irqsave(). 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 1089:ref:`Back to Quick Quiz #1 <quiz_1>` 1090 1091Quick Quiz #2: 1092 Give an example where Classic RCU's read-side 1093 overhead is **negative**. 1094 1095Answer: 1096 Imagine a single-CPU system with a non-CONFIG_PREEMPTION 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 1118:ref:`Back to Quick Quiz #2 <quiz_2>` 1119 1120Quick Quiz #3: 1121 If it is illegal to block in an RCU read-side 1122 critical section, what the heck do you do in 1123 CONFIG_PREEMPT_RT, where normal spinlocks can block??? 1124 1125Answer: 1126 Just as CONFIG_PREEMPT_RT permits preemption of spinlock 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 1132 Why the apparent inconsistency? Because it is 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 1145:ref:`Back to Quick Quiz #3 <quiz_3>` 1146 1147ACKNOWLEDGEMENTS 1148 1149My thanks to the people who helped make this human-readable, including 1150Jon Walpole, Josh Triplett, Serge Hallyn, Suzanne Wood, and Alan Stern. 1151 1152 1153For more information, see http://www.rdrop.com/users/paulmck/RCU. 1154