1 <!-- DO NOT HAND EDIT. -->
2 <!-- Instead, edit Requirements.htmlx and run 'sh htmlqqz.sh Requirements' -->
3 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
4 "http://www.w3.org/TR/html4/loose.dtd">
6 <head><title>A Tour Through RCU's Requirements [LWN.net]</title>
7 <meta HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=utf-8">
9 <h1>A Tour Through RCU's Requirements</h1>
11 <p>Copyright IBM Corporation, 2015</p>
12 <p>Author: Paul E. McKenney</p>
13 <p><i>The initial version of this document appeared in the
14 <a href="https://lwn.net/">LWN</a> articles
15 <a href="https://lwn.net/Articles/652156/">here</a>,
16 <a href="https://lwn.net/Articles/652677/">here</a>, and
17 <a href="https://lwn.net/Articles/653326/">here</a>.</i></p>
22 Read-copy update (RCU) is a synchronization mechanism that is often
23 used as a replacement for reader-writer locking.
24 RCU is unusual in that updaters do not block readers,
25 which means that RCU's read-side primitives can be exceedingly fast
27 In addition, updaters can make useful forward progress concurrently
29 However, all this concurrency between RCU readers and updaters does raise
30 the question of exactly what RCU readers are doing, which in turn
31 raises the question of exactly what RCU's requirements are.
34 This document therefore summarizes RCU's requirements, and can be thought
35 of as an informal, high-level specification for RCU.
36 It is important to understand that RCU's specification is primarily
38 in fact, I learned about many of these requirements the hard way.
39 This situation might cause some consternation, however, not only
40 has this learning process been a lot of fun, but it has also been
41 a great privilege to work with so many people willing to apply
42 technologies in interesting new ways.
45 All that aside, here are the categories of currently known RCU requirements:
49 <li> <a href="#Fundamental Requirements">
50 Fundamental Requirements</a>
51 <li> <a href="#Fundamental Non-Requirements">Fundamental Non-Requirements</a>
52 <li> <a href="#Parallelism Facts of Life">
53 Parallelism Facts of Life</a>
54 <li> <a href="#Quality-of-Implementation Requirements">
55 Quality-of-Implementation Requirements</a>
56 <li> <a href="#Linux Kernel Complications">
57 Linux Kernel Complications</a>
58 <li> <a href="#Software-Engineering Requirements">
59 Software-Engineering Requirements</a>
60 <li> <a href="#Other RCU Flavors">
62 <li> <a href="#Possible Future Changes">
63 Possible Future Changes</a>
67 This is followed by a <a href="#Summary">summary</a>,
68 which is in turn followed by the inevitable
69 <a href="#Answers to Quick Quizzes">answers to the quick quizzes</a>.
71 <h2><a name="Fundamental Requirements">Fundamental Requirements</a></h2>
74 RCU's fundamental requirements are the closest thing RCU has to hard
75 mathematical requirements.
79 <li> <a href="#Grace-Period Guarantee">
80 Grace-Period Guarantee</a>
81 <li> <a href="#Publish-Subscribe Guarantee">
82 Publish-Subscribe Guarantee</a>
83 <li> <a href="#Memory-Barrier Guarantees">
84 Memory-Barrier Guarantees</a>
85 <li> <a href="#RCU Primitives Guaranteed to Execute Unconditionally">
86 RCU Primitives Guaranteed to Execute Unconditionally</a>
87 <li> <a href="#Guaranteed Read-to-Write Upgrade">
88 Guaranteed Read-to-Write Upgrade</a>
91 <h3><a name="Grace-Period Guarantee">Grace-Period Guarantee</a></h3>
94 RCU's grace-period guarantee is unusual in being premeditated:
95 Jack Slingwine and I had this guarantee firmly in mind when we started
96 work on RCU (then called “rclock”) in the early 1990s.
97 That said, the past two decades of experience with RCU have produced
98 a much more detailed understanding of this guarantee.
101 RCU's grace-period guarantee allows updaters to wait for the completion
102 of all pre-existing RCU read-side critical sections.
103 An RCU read-side critical section
104 begins with the marker <tt>rcu_read_lock()</tt> and ends with
105 the marker <tt>rcu_read_unlock()</tt>.
106 These markers may be nested, and RCU treats a nested set as one
107 big RCU read-side critical section.
108 Production-quality implementations of <tt>rcu_read_lock()</tt> and
109 <tt>rcu_read_unlock()</tt> are extremely lightweight, and in
110 fact have exactly zero overhead in Linux kernels built for production
111 use with <tt>CONFIG_PREEMPT=n</tt>.
114 This guarantee allows ordering to be enforced with extremely low
115 overhead to readers, for example:
129 11 void thread1(void)
132 14 synchronize_rcu();
139 Because the <tt>synchronize_rcu()</tt> on line 14 waits for
140 all pre-existing readers, any instance of <tt>thread0()</tt> that
141 loads a value of zero from <tt>x</tt> must complete before
142 <tt>thread1()</tt> stores to <tt>y</tt>, so that instance must
143 also load a value of zero from <tt>y</tt>.
144 Similarly, any instance of <tt>thread0()</tt> that loads a value of
145 one from <tt>y</tt> must have started after the
146 <tt>synchronize_rcu()</tt> started, and must therefore also load
147 a value of one from <tt>x</tt>.
148 Therefore, the outcome:
151 (r1 == 0 && r2 == 1)
156 <p><a name="Quick Quiz 1"><b>Quick Quiz 1</b>:</a>
158 You said that updaters can make useful forward progress concurrently
159 with readers, but pre-existing readers will block
160 <tt>synchronize_rcu()</tt>!!!
161 Just who are you trying to fool???
162 <br><a href="#qq1answer">Answer</a>
165 This scenario resembles one of the first uses of RCU in
166 <a href="https://en.wikipedia.org/wiki/DYNIX">DYNIX/ptx</a>,
167 which managed a distributed lock manager's transition into
168 a state suitable for handling recovery from node failure,
169 more or less as follows:
173 1 #define STATE_NORMAL 0
174 2 #define STATE_WANT_RECOVERY 1
175 3 #define STATE_RECOVERING 2
176 4 #define STATE_WANT_NORMAL 3
178 6 int state = STATE_NORMAL;
180 8 void do_something_dlm(void)
185 13 state_snap = READ_ONCE(state);
186 14 if (state_snap == STATE_NORMAL)
189 17 do_something_carefully();
190 18 rcu_read_unlock();
193 21 void start_recovery(void)
195 23 WRITE_ONCE(state, STATE_WANT_RECOVERY);
196 24 synchronize_rcu();
197 25 WRITE_ONCE(state, STATE_RECOVERING);
199 27 WRITE_ONCE(state, STATE_WANT_NORMAL);
200 28 synchronize_rcu();
201 29 WRITE_ONCE(state, STATE_NORMAL);
207 The RCU read-side critical section in <tt>do_something_dlm()</tt>
208 works with the <tt>synchronize_rcu()</tt> in <tt>start_recovery()</tt>
209 to guarantee that <tt>do_something()</tt> never runs concurrently
210 with <tt>recovery()</tt>, but with little or no synchronization
211 overhead in <tt>do_something_dlm()</tt>.
213 <p><a name="Quick Quiz 2"><b>Quick Quiz 2</b>:</a>
214 Why is the <tt>synchronize_rcu()</tt> on line 28 needed?
215 <br><a href="#qq2answer">Answer</a>
218 In order to avoid fatal problems such as deadlocks,
219 an RCU read-side critical section must not contain calls to
220 <tt>synchronize_rcu()</tt>.
221 Similarly, an RCU read-side critical section must not
222 contain anything that waits, directly or indirectly, on completion of
223 an invocation of <tt>synchronize_rcu()</tt>.
226 Although RCU's grace-period guarantee is useful in and of itself, with
227 <a href="https://lwn.net/Articles/573497/">quite a few use cases</a>,
228 it would be good to be able to use RCU to coordinate read-side
229 access to linked data structures.
230 For this, the grace-period guarantee is not sufficient, as can
231 be seen in function <tt>add_gp_buggy()</tt> below.
232 We will look at the reader's code later, but in the meantime, just think of
233 the reader as locklessly picking up the <tt>gp</tt> pointer,
234 and, if the value loaded is non-<tt>NULL</tt>, locklessly accessing the
235 <tt>->a</tt> and <tt>->b</tt> fields.
239 1 bool add_gp_buggy(int a, int b)
241 3 p = kmalloc(sizeof(*p), GFP_KERNEL);
244 6 spin_lock(&gp_lock);
245 7 if (rcu_access_pointer(gp)) {
246 8 spin_unlock(&gp_lock);
251 13 gp = p; /* ORDERING BUG */
252 14 spin_unlock(&gp_lock);
259 The problem is that both the compiler and weakly ordered CPUs are within
260 their rights to reorder this code as follows:
264 1 bool add_gp_buggy_optimized(int a, int b)
266 3 p = kmalloc(sizeof(*p), GFP_KERNEL);
269 6 spin_lock(&gp_lock);
270 7 if (rcu_access_pointer(gp)) {
271 8 spin_unlock(&gp_lock);
274 <b>11 gp = p; /* ORDERING BUG */
277 14 spin_unlock(&gp_lock);
284 If an RCU reader fetches <tt>gp</tt> just after
285 <tt>add_gp_buggy_optimized</tt> executes line 11,
286 it will see garbage in the <tt>->a</tt> and <tt>->b</tt>
288 And this is but one of many ways in which compiler and hardware optimizations
290 Therefore, we clearly need some way to prevent the compiler and the CPU from
291 reordering in this manner, which brings us to the publish-subscribe
292 guarantee discussed in the next section.
294 <h3><a name="Publish-Subscribe Guarantee">Publish/Subscribe Guarantee</a></h3>
297 RCU's publish-subscribe guarantee allows data to be inserted
298 into a linked data structure without disrupting RCU readers.
299 The updater uses <tt>rcu_assign_pointer()</tt> to insert the
300 new data, and readers use <tt>rcu_dereference()</tt> to
301 access data, whether new or old.
302 The following shows an example of insertion:
306 1 bool add_gp(int a, int b)
308 3 p = kmalloc(sizeof(*p), GFP_KERNEL);
311 6 spin_lock(&gp_lock);
312 7 if (rcu_access_pointer(gp)) {
313 8 spin_unlock(&gp_lock);
318 13 rcu_assign_pointer(gp, p);
319 14 spin_unlock(&gp_lock);
326 The <tt>rcu_assign_pointer()</tt> on line 13 is conceptually
327 equivalent to a simple assignment statement, but also guarantees
328 that its assignment will
329 happen after the two assignments in lines 11 and 12,
330 similar to the C11 <tt>memory_order_release</tt> store operation.
331 It also prevents any number of “interesting” compiler
332 optimizations, for example, the use of <tt>gp</tt> as a scratch
333 location immediately preceding the assignment.
335 <p><a name="Quick Quiz 3"><b>Quick Quiz 3</b>:</a>
336 But <tt>rcu_assign_pointer()</tt> does nothing to prevent the
337 two assignments to <tt>p->a</tt> and <tt>p->b</tt>
338 from being reordered.
339 Can't that also cause problems?
340 <br><a href="#qq3answer">Answer</a>
343 It is tempting to assume that the reader need not do anything special
344 to control its accesses to the RCU-protected data,
345 as shown in <tt>do_something_gp_buggy()</tt> below:
349 1 bool do_something_gp_buggy(void)
352 4 p = gp; /* OPTIMIZATIONS GALORE!!! */
354 6 do_something(p->a, p->b);
358 10 rcu_read_unlock();
365 However, this temptation must be resisted because there are a
366 surprisingly large number of ways that the compiler
368 <a href="https://h71000.www7.hp.com/wizard/wiz_2637.html">DEC Alpha CPUs</a>)
369 can trip this code up.
370 For but one example, if the compiler were short of registers, it
371 might choose to refetch from <tt>gp</tt> rather than keeping
372 a separate copy in <tt>p</tt> as follows:
376 1 bool do_something_gp_buggy_optimized(void)
379 4 if (gp) { /* OPTIMIZATIONS GALORE!!! */
380 <b> 5 do_something(gp->a, gp->b);</b>
391 If this function ran concurrently with a series of updates that
392 replaced the current structure with a new one,
393 the fetches of <tt>gp->a</tt>
394 and <tt>gp->b</tt> might well come from two different structures,
395 which could cause serious confusion.
396 To prevent this (and much else besides), <tt>do_something_gp()</tt> uses
397 <tt>rcu_dereference()</tt> to fetch from <tt>gp</tt>:
401 1 bool do_something_gp(void)
404 4 p = rcu_dereference(gp);
406 6 do_something(p->a, p->b);
410 10 rcu_read_unlock();
417 The <tt>rcu_dereference()</tt> uses volatile casts and (for DEC Alpha)
418 memory barriers in the Linux kernel.
420 <a href="http://www.rdrop.com/users/paulmck/RCU/consume.2015.07.13a.pdf">high-quality implementation of C11 <tt>memory_order_consume</tt> [PDF]</a>
421 ever appear, then <tt>rcu_dereference()</tt> could be implemented
422 as a <tt>memory_order_consume</tt> load.
423 Regardless of the exact implementation, a pointer fetched by
424 <tt>rcu_dereference()</tt> may not be used outside of the
425 outermost RCU read-side critical section containing that
426 <tt>rcu_dereference()</tt>, unless protection of
427 the corresponding data element has been passed from RCU to some
428 other synchronization mechanism, most commonly locking or
429 <a href="https://www.kernel.org/doc/Documentation/RCU/rcuref.txt">reference counting</a>.
432 In short, updaters use <tt>rcu_assign_pointer()</tt> and readers
433 use <tt>rcu_dereference()</tt>, and these two RCU API elements
434 work together to ensure that readers have a consistent view of
435 newly added data elements.
438 Of course, it is also necessary to remove elements from RCU-protected
439 data structures, for example, using the following process:
442 <li> Remove the data element from the enclosing structure.
443 <li> Wait for all pre-existing RCU read-side critical sections
444 to complete (because only pre-existing readers can possibly have
445 a reference to the newly removed data element).
446 <li> At this point, only the updater has a reference to the
447 newly removed data element, so it can safely reclaim
448 the data element, for example, by passing it to <tt>kfree()</tt>.
451 This process is implemented by <tt>remove_gp_synchronous()</tt>:
455 1 bool remove_gp_synchronous(void)
459 5 spin_lock(&gp_lock);
460 6 p = rcu_access_pointer(gp);
462 8 spin_unlock(&gp_lock);
465 11 rcu_assign_pointer(gp, NULL);
466 12 spin_unlock(&gp_lock);
467 13 synchronize_rcu();
475 This function is straightforward, with line 13 waiting for a grace
476 period before line 14 frees the old data element.
477 This waiting ensures that readers will reach line 7 of
478 <tt>do_something_gp()</tt> before the data element referenced by
480 The <tt>rcu_access_pointer()</tt> on line 6 is similar to
481 <tt>rcu_dereference()</tt>, except that:
484 <li> The value returned by <tt>rcu_access_pointer()</tt>
485 cannot be dereferenced.
486 If you want to access the value pointed to as well as
487 the pointer itself, use <tt>rcu_dereference()</tt>
488 instead of <tt>rcu_access_pointer()</tt>.
489 <li> The call to <tt>rcu_access_pointer()</tt> need not be
491 In contrast, <tt>rcu_dereference()</tt> must either be
492 within an RCU read-side critical section or in a code
493 segment where the pointer cannot change, for example, in
494 code protected by the corresponding update-side lock.
497 <p><a name="Quick Quiz 4"><b>Quick Quiz 4</b>:</a>
498 Without the <tt>rcu_dereference()</tt> or the
499 <tt>rcu_access_pointer()</tt>, what destructive optimizations
500 might the compiler make use of?
501 <br><a href="#qq4answer">Answer</a>
504 In short, RCU's publish-subscribe guarantee is provided by the combination
505 of <tt>rcu_assign_pointer()</tt> and <tt>rcu_dereference()</tt>.
506 This guarantee allows data elements to be safely added to RCU-protected
507 linked data structures without disrupting RCU readers.
508 This guarantee can be used in combination with the grace-period
509 guarantee to also allow data elements to be removed from RCU-protected
510 linked data structures, again without disrupting RCU readers.
513 This guarantee was only partially premeditated.
514 DYNIX/ptx used an explicit memory barrier for publication, but had nothing
515 resembling <tt>rcu_dereference()</tt> for subscription, nor did it
516 have anything resembling the <tt>smp_read_barrier_depends()</tt>
517 that was later subsumed into <tt>rcu_dereference()</tt>.
518 The need for these operations made itself known quite suddenly at a
519 late-1990s meeting with the DEC Alpha architects, back in the days when
520 DEC was still a free-standing company.
521 It took the Alpha architects a good hour to convince me that any sort
522 of barrier would ever be needed, and it then took me a good <i>two</i> hours
523 to convince them that their documentation did not make this point clear.
524 More recent work with the C and C++ standards committees have provided
525 much education on tricks and traps from the compiler.
526 In short, compilers were much less tricky in the early 1990s, but in
527 2015, don't even think about omitting <tt>rcu_dereference()</tt>!
529 <h3><a name="Memory-Barrier Guarantees">Memory-Barrier Guarantees</a></h3>
532 The previous section's simple linked-data-structure scenario clearly
533 demonstrates the need for RCU's stringent memory-ordering guarantees on
534 systems with more than one CPU:
537 <li> Each CPU that has an RCU read-side critical section that
538 begins before <tt>synchronize_rcu()</tt> starts is
539 guaranteed to execute a full memory barrier between the time
540 that the RCU read-side critical section ends and the time that
541 <tt>synchronize_rcu()</tt> returns.
542 Without this guarantee, a pre-existing RCU read-side critical section
543 might hold a reference to the newly removed <tt>struct foo</tt>
544 after the <tt>kfree()</tt> on line 14 of
545 <tt>remove_gp_synchronous()</tt>.
546 <li> Each CPU that has an RCU read-side critical section that ends
547 after <tt>synchronize_rcu()</tt> returns is guaranteed
548 to execute a full memory barrier between the time that
549 <tt>synchronize_rcu()</tt> begins and the time that the RCU
550 read-side critical section begins.
551 Without this guarantee, a later RCU read-side critical section
552 running after the <tt>kfree()</tt> on line 14 of
553 <tt>remove_gp_synchronous()</tt> might
554 later run <tt>do_something_gp()</tt> and find the
555 newly deleted <tt>struct foo</tt>.
556 <li> If the task invoking <tt>synchronize_rcu()</tt> remains
557 on a given CPU, then that CPU is guaranteed to execute a full
558 memory barrier sometime during the execution of
559 <tt>synchronize_rcu()</tt>.
560 This guarantee ensures that the <tt>kfree()</tt> on
561 line 14 of <tt>remove_gp_synchronous()</tt> really does
562 execute after the removal on line 11.
563 <li> If the task invoking <tt>synchronize_rcu()</tt> migrates
564 among a group of CPUs during that invocation, then each of the
565 CPUs in that group is guaranteed to execute a full memory barrier
566 sometime during the execution of <tt>synchronize_rcu()</tt>.
567 This guarantee also ensures that the <tt>kfree()</tt> on
568 line 14 of <tt>remove_gp_synchronous()</tt> really does
569 execute after the removal on
570 line 11, but also in the case where the thread executing the
571 <tt>synchronize_rcu()</tt> migrates in the meantime.
574 <p><a name="Quick Quiz 5"><b>Quick Quiz 5</b>:</a>
575 Given that multiple CPUs can start RCU read-side critical sections
576 at any time without any ordering whatsoever, how can RCU possibly tell whether
577 or not a given RCU read-side critical section starts before a
578 given instance of <tt>synchronize_rcu()</tt>?
579 <br><a href="#qq5answer">Answer</a>
581 <p><a name="Quick Quiz 6"><b>Quick Quiz 6</b>:</a>
582 The first and second guarantees require unbelievably strict ordering!
583 Are all these memory barriers <i> really</i> required?
584 <br><a href="#qq6answer">Answer</a>
587 Note that these memory-barrier requirements do not replace the fundamental
588 RCU requirement that a grace period wait for all pre-existing readers.
589 On the contrary, the memory barriers called out in this section must operate in
590 such a way as to <i>enforce</i> this fundamental requirement.
591 Of course, different implementations enforce this requirement in different
592 ways, but enforce it they must.
594 <h3><a name="RCU Primitives Guaranteed to Execute Unconditionally">RCU Primitives Guaranteed to Execute Unconditionally</a></h3>
597 The common-case RCU primitives are unconditional.
598 They are invoked, they do their job, and they return, with no possibility
599 of error, and no need to retry.
600 This is a key RCU design philosophy.
603 However, this philosophy is pragmatic rather than pigheaded.
604 If someone comes up with a good justification for a particular conditional
605 RCU primitive, it might well be implemented and added.
606 After all, this guarantee was reverse-engineered, not premeditated.
607 The unconditional nature of the RCU primitives was initially an
608 accident of implementation, and later experience with synchronization
609 primitives with conditional primitives caused me to elevate this
610 accident to a guarantee.
611 Therefore, the justification for adding a conditional primitive to
612 RCU would need to be based on detailed and compelling use cases.
614 <h3><a name="Guaranteed Read-to-Write Upgrade">Guaranteed Read-to-Write Upgrade</a></h3>
617 As far as RCU is concerned, it is always possible to carry out an
618 update within an RCU read-side critical section.
619 For example, that RCU read-side critical section might search for
620 a given data element, and then might acquire the update-side
621 spinlock in order to update that element, all while remaining
622 in that RCU read-side critical section.
623 Of course, it is necessary to exit the RCU read-side critical section
624 before invoking <tt>synchronize_rcu()</tt>, however, this
625 inconvenience can be avoided through use of the
626 <tt>call_rcu()</tt> and <tt>kfree_rcu()</tt> API members
627 described later in this document.
629 <p><a name="Quick Quiz 7"><b>Quick Quiz 7</b>:</a>
630 But how does the upgrade-to-write operation exclude other readers?
631 <br><a href="#qq7answer">Answer</a>
634 This guarantee allows lookup code to be shared between read-side
635 and update-side code, and was premeditated, appearing in the earliest
636 DYNIX/ptx RCU documentation.
638 <h2><a name="Fundamental Non-Requirements">Fundamental Non-Requirements</a></h2>
641 RCU provides extremely lightweight readers, and its read-side guarantees,
642 though quite useful, are correspondingly lightweight.
643 It is therefore all too easy to assume that RCU is guaranteeing more
645 Of course, the list of things that RCU does not guarantee is infinitely
646 long, however, the following sections list a few non-guarantees that
647 have caused confusion.
648 Except where otherwise noted, these non-guarantees were premeditated.
651 <li> <a href="#Readers Impose Minimal Ordering">
652 Readers Impose Minimal Ordering</a>
653 <li> <a href="#Readers Do Not Exclude Updaters">
654 Readers Do Not Exclude Updaters</a>
655 <li> <a href="#Updaters Only Wait For Old Readers">
656 Updaters Only Wait For Old Readers</a>
657 <li> <a href="#Grace Periods Don't Partition Read-Side Critical Sections">
658 Grace Periods Don't Partition Read-Side Critical Sections</a>
659 <li> <a href="#Read-Side Critical Sections Don't Partition Grace Periods">
660 Read-Side Critical Sections Don't Partition Grace Periods</a>
661 <li> <a href="#Disabling Preemption Does Not Block Grace Periods">
662 Disabling Preemption Does Not Block Grace Periods</a>
665 <h3><a name="Readers Impose Minimal Ordering">Readers Impose Minimal Ordering</a></h3>
668 Reader-side markers such as <tt>rcu_read_lock()</tt> and
669 <tt>rcu_read_unlock()</tt> provide absolutely no ordering guarantees
670 except through their interaction with the grace-period APIs such as
671 <tt>synchronize_rcu()</tt>.
672 To see this, consider the following pair of threads:
686 11 void thread1(void)
689 14 r1 = READ_ONCE(y);
690 15 rcu_read_unlock();
692 17 r2 = READ_ONCE(x);
693 18 rcu_read_unlock();
699 After <tt>thread0()</tt> and <tt>thread1()</tt> execute
700 concurrently, it is quite possible to have
704 (r1 == 1 && r2 == 0)
708 (that is, <tt>y</tt> appears to have been assigned before <tt>x</tt>),
709 which would not be possible if <tt>rcu_read_lock()</tt> and
710 <tt>rcu_read_unlock()</tt> had much in the way of ordering
712 But they do not, so the CPU is within its rights
713 to do significant reordering.
714 This is by design: Any significant ordering constraints would slow down
715 these fast-path APIs.
717 <p><a name="Quick Quiz 8"><b>Quick Quiz 8</b>:</a>
718 Can't the compiler also reorder this code?
719 <br><a href="#qq8answer">Answer</a>
721 <h3><a name="Readers Do Not Exclude Updaters">Readers Do Not Exclude Updaters</a></h3>
724 Neither <tt>rcu_read_lock()</tt> nor <tt>rcu_read_unlock()</tt>
726 All they do is to prevent grace periods from ending.
727 The following example illustrates this:
736 6 do_something_with_nonzero_x();
738 8 WARN_ON(!r2); /* BUG!!! */
740 10 rcu_read_unlock();
743 13 void thread1(void)
745 15 spin_lock(&my_lock);
748 18 spin_unlock(&my_lock);
754 If the <tt>thread0()</tt> function's <tt>rcu_read_lock()</tt>
755 excluded the <tt>thread1()</tt> function's update,
756 the <tt>WARN_ON()</tt> could never fire.
757 But the fact is that <tt>rcu_read_lock()</tt> does not exclude
758 much of anything aside from subsequent grace periods, of which
759 <tt>thread1()</tt> has none, so the
760 <tt>WARN_ON()</tt> can and does fire.
762 <h3><a name="Updaters Only Wait For Old Readers">Updaters Only Wait For Old Readers</a></h3>
765 It might be tempting to assume that after <tt>synchronize_rcu()</tt>
766 completes, there are no readers executing.
767 This temptation must be avoided because
768 new readers can start immediately after <tt>synchronize_rcu()</tt>
769 starts, and <tt>synchronize_rcu()</tt> is under no
770 obligation to wait for these new readers.
772 <p><a name="Quick Quiz 9"><b>Quick Quiz 9</b>:</a>
773 Suppose that synchronize_rcu() did wait until all readers had completed.
774 Would the updater be able to rely on this?
775 <br><a href="#qq9answer">Answer</a>
777 <h3><a name="Grace Periods Don't Partition Read-Side Critical Sections">
778 Grace Periods Don't Partition Read-Side Critical Sections</a></h3>
781 It is tempting to assume that if any part of one RCU read-side critical
782 section precedes a given grace period, and if any part of another RCU
783 read-side critical section follows that same grace period, then all of
784 the first RCU read-side critical section must precede all of the second.
785 However, this just isn't the case: A single grace period does not
786 partition the set of RCU read-side critical sections.
787 An example of this situation can be illustrated as follows, where
788 <tt>x</tt>, <tt>y</tt>, and <tt>z</tt> are initially all zero:
802 11 r1 = READ_ONCE(a);
803 12 synchronize_rcu();
807 16 void thread2(void)
810 19 r2 = READ_ONCE(b);
811 20 r3 = READ_ONCE(c);
812 21 rcu_read_unlock();
818 It turns out that the outcome:
822 (r1 == 1 && r2 == 0 && r3 == 1)
826 is entirely possible.
827 The following figure show how this can happen, with each circled
828 <tt>QS</tt> indicating the point at which RCU recorded a
829 <i>quiescent state</i> for each thread, that is, a state in which
830 RCU knows that the thread cannot be in the midst of an RCU read-side
831 critical section that started before the current grace period:
833 <p><img src="GPpartitionReaders1.svg" alt="GPpartitionReaders1.svg" width="60%"></p>
836 If it is necessary to partition RCU read-side critical sections in this
837 manner, it is necessary to use two grace periods, where the first
838 grace period is known to end before the second grace period starts:
852 11 r1 = READ_ONCE(a);
853 12 synchronize_rcu();
857 16 void thread2(void)
859 18 r2 = READ_ONCE(c);
860 19 synchronize_rcu();
864 23 void thread3(void)
867 26 r3 = READ_ONCE(b);
868 27 r4 = READ_ONCE(d);
869 28 rcu_read_unlock();
875 Here, if <tt>(r1 == 1)</tt>, then
876 <tt>thread0()</tt>'s write to <tt>b</tt> must happen
877 before the end of <tt>thread1()</tt>'s grace period.
878 If in addition <tt>(r4 == 1)</tt>, then
879 <tt>thread3()</tt>'s read from <tt>b</tt> must happen
880 after the beginning of <tt>thread2()</tt>'s grace period.
881 If it is also the case that <tt>(r2 == 1)</tt>, then the
882 end of <tt>thread1()</tt>'s grace period must precede the
883 beginning of <tt>thread2()</tt>'s grace period.
884 This mean that the two RCU read-side critical sections cannot overlap,
885 guaranteeing that <tt>(r3 == 1)</tt>.
886 As a result, the outcome:
890 (r1 == 1 && r2 == 1 && r3 == 0 && r4 == 1)
897 This non-requirement was also non-premeditated, but became apparent
898 when studying RCU's interaction with memory ordering.
900 <h3><a name="Read-Side Critical Sections Don't Partition Grace Periods">
901 Read-Side Critical Sections Don't Partition Grace Periods</a></h3>
904 It is also tempting to assume that if an RCU read-side critical section
905 happens between a pair of grace periods, then those grace periods cannot
907 However, this temptation leads nowhere good, as can be illustrated by
908 the following, with all variables initially zero:
922 11 r1 = READ_ONCE(a);
923 12 synchronize_rcu();
927 16 void thread2(void)
931 20 r2 = READ_ONCE(c);
932 21 rcu_read_unlock();
935 24 void thread3(void)
937 26 r3 = READ_ONCE(d);
938 27 synchronize_rcu();
942 31 void thread4(void)
945 34 r4 = READ_ONCE(b);
946 35 r5 = READ_ONCE(e);
947 36 rcu_read_unlock();
953 In this case, the outcome:
957 (r1 == 1 && r2 == 1 && r3 == 1 && r4 == 0 && r5 == 1)
961 is entirely possible, as illustrated below:
963 <p><img src="ReadersPartitionGP1.svg" alt="ReadersPartitionGP1.svg" width="100%"></p>
966 Again, an RCU read-side critical section can overlap almost all of a
967 given grace period, just so long as it does not overlap the entire
969 As a result, an RCU read-side critical section cannot partition a pair
970 of RCU grace periods.
972 <p><a name="Quick Quiz 10"><b>Quick Quiz 10</b>:</a>
973 How long a sequence of grace periods, each separated by an RCU read-side
974 critical section, would be required to partition the RCU read-side
975 critical sections at the beginning and end of the chain?
976 <br><a href="#qq10answer">Answer</a>
978 <h3><a name="Disabling Preemption Does Not Block Grace Periods">
979 Disabling Preemption Does Not Block Grace Periods</a></h3>
982 There was a time when disabling preemption on any given CPU would block
983 subsequent grace periods.
984 However, this was an accident of implementation and is not a requirement.
985 And in the current Linux-kernel implementation, disabling preemption
986 on a given CPU in fact does not block grace periods, as Oleg Nesterov
987 <a href="https://lkml.kernel.org/g/20150614193825.GA19582@redhat.com">demonstrated</a>.
990 If you need a preempt-disable region to block grace periods, you need to add
991 <tt>rcu_read_lock()</tt> and <tt>rcu_read_unlock()</tt>, for example
1002 7 /* Spinlocks implicitly disable preemption. */
1003 8 spin_lock(&mylock);
1006 11 rcu_read_unlock();
1007 12 spin_unlock(&mylock);
1012 In theory, you could enter the RCU read-side critical section first,
1013 but it is more efficient to keep the entire RCU read-side critical
1014 section contained in the preempt-disable region as shown above.
1015 Of course, RCU read-side critical sections that extend outside of
1016 preempt-disable regions will work correctly, but such critical sections
1017 can be preempted, which forces <tt>rcu_read_unlock()</tt> to do
1019 And no, this is <i>not</i> an invitation to enclose all of your RCU
1020 read-side critical sections within preempt-disable regions, because
1021 doing so would degrade real-time response.
1024 This non-requirement appeared with preemptible RCU.
1025 If you need a grace period that waits on non-preemptible code regions, use
1026 <a href="#Sched Flavor">RCU-sched</a>.
1028 <h2><a name="Parallelism Facts of Life">Parallelism Facts of Life</a></h2>
1031 These parallelism facts of life are by no means specific to RCU, but
1032 the RCU implementation must abide by them.
1033 They therefore bear repeating:
1036 <li> Any CPU or task may be delayed at any time,
1037 and any attempts to avoid these delays by disabling
1038 preemption, interrupts, or whatever are completely futile.
1039 This is most obvious in preemptible user-level
1040 environments and in virtualized environments (where
1041 a given guest OS's VCPUs can be preempted at any time by
1042 the underlying hypervisor), but can also happen in bare-metal
1043 environments due to ECC errors, NMIs, and other hardware
1045 Although a delay of more than about 20 seconds can result
1046 in splats, the RCU implementation is obligated to use
1047 algorithms that can tolerate extremely long delays, but where
1048 “extremely long” is not long enough to allow
1049 wrap-around when incrementing a 64-bit counter.
1050 <li> Both the compiler and the CPU can reorder memory accesses.
1051 Where it matters, RCU must use compiler directives and
1052 memory-barrier instructions to preserve ordering.
1053 <li> Conflicting writes to memory locations in any given cache line
1054 will result in expensive cache misses.
1055 Greater numbers of concurrent writes and more-frequent
1056 concurrent writes will result in more dramatic slowdowns.
1057 RCU is therefore obligated to use algorithms that have
1058 sufficient locality to avoid significant performance and
1059 scalability problems.
1060 <li> As a rough rule of thumb, only one CPU's worth of processing
1061 may be carried out under the protection of any given exclusive
1063 RCU must therefore use scalable locking designs.
1064 <li> Counters are finite, especially on 32-bit systems.
1065 RCU's use of counters must therefore tolerate counter wrap,
1066 or be designed such that counter wrap would take way more
1067 time than a single system is likely to run.
1068 An uptime of ten years is quite possible, a runtime
1069 of a century much less so.
1070 As an example of the latter, RCU's dyntick-idle nesting counter
1071 allows 54 bits for interrupt nesting level (this counter
1072 is 64 bits even on a 32-bit system).
1073 Overflowing this counter requires 2<sup>54</sup>
1074 half-interrupts on a given CPU without that CPU ever going idle.
1075 If a half-interrupt happened every microsecond, it would take
1076 570 years of runtime to overflow this counter, which is currently
1077 believed to be an acceptably long time.
1078 <li> Linux systems can have thousands of CPUs running a single
1079 Linux kernel in a single shared-memory environment.
1080 RCU must therefore pay close attention to high-end scalability.
1084 This last parallelism fact of life means that RCU must pay special
1085 attention to the preceding facts of life.
1086 The idea that Linux might scale to systems with thousands of CPUs would
1087 have been met with some skepticism in the 1990s, but these requirements
1088 would have otherwise have been unsurprising, even in the early 1990s.
1090 <h2><a name="Quality-of-Implementation Requirements">Quality-of-Implementation Requirements</a></h2>
1093 These sections list quality-of-implementation requirements.
1094 Although an RCU implementation that ignores these requirements could
1095 still be used, it would likely be subject to limitations that would
1096 make it inappropriate for industrial-strength production use.
1097 Classes of quality-of-implementation requirements are as follows:
1100 <li> <a href="#Specialization">Specialization</a>
1101 <li> <a href="#Performance and Scalability">Performance and Scalability</a>
1102 <li> <a href="#Composability">Composability</a>
1103 <li> <a href="#Corner Cases">Corner Cases</a>
1107 These classes is covered in the following sections.
1109 <h3><a name="Specialization">Specialization</a></h3>
1112 RCU is and always has been intended primarily for read-mostly situations, as
1113 illustrated by the following figure.
1114 This means that RCU's read-side primitives are optimized, often at the
1115 expense of its update-side primitives.
1117 <p><img src="RCUApplicability.svg" alt="RCUApplicability.svg" width="70%"></p>
1120 This focus on read-mostly situations means that RCU must interoperate
1121 with other synchronization primitives.
1122 For example, the <tt>add_gp()</tt> and <tt>remove_gp_synchronous()</tt>
1123 examples discussed earlier use RCU to protect readers and locking to
1124 coordinate updaters.
1125 However, the need extends much farther, requiring that a variety of
1126 synchronization primitives be legal within RCU read-side critical sections,
1127 including spinlocks, sequence locks, atomic operations, reference
1128 counters, and memory barriers.
1130 <p><a name="Quick Quiz 11"><b>Quick Quiz 11</b>:</a>
1131 What about sleeping locks?
1132 <br><a href="#qq11answer">Answer</a>
1135 It often comes as a surprise that many algorithms do not require a
1136 consistent view of data, but many can function in that mode,
1137 with network routing being the poster child.
1138 Internet routing algorithms take significant time to propagate
1139 updates, so that by the time an update arrives at a given system,
1140 that system has been sending network traffic the wrong way for
1141 a considerable length of time.
1142 Having a few threads continue to send traffic the wrong way for a
1143 few more milliseconds is clearly not a problem: In the worst case,
1144 TCP retransmissions will eventually get the data where it needs to go.
1145 In general, when tracking the state of the universe outside of the
1146 computer, some level of inconsistency must be tolerated due to
1147 speed-of-light delays if nothing else.
1150 Furthermore, uncertainty about external state is inherent in many cases.
1151 For example, a pair of veternarians might use heartbeat to determine
1152 whether or not a given cat was alive.
1153 But how long should they wait after the last heartbeat to decide that
1154 the cat is in fact dead?
1155 Waiting less than 400 milliseconds makes no sense because this would
1156 mean that a relaxed cat would be considered to cycle between death
1157 and life more than 100 times per minute.
1158 Moreover, just as with human beings, a cat's heart might stop for
1159 some period of time, so the exact wait period is a judgment call.
1160 One of our pair of veternarians might wait 30 seconds before pronouncing
1161 the cat dead, while the other might insist on waiting a full minute.
1162 The two veternarians would then disagree on the state of the cat during
1163 the final 30 seconds of the minute following the last heartbeat, as
1164 fancifully illustrated below:
1166 <p><img src="2013-08-is-it-dead.png" alt="2013-08-is-it-dead.png" width="431"></p>
1169 Interestingly enough, this same situation applies to hardware.
1170 When push comes to shove, how do we tell whether or not some
1171 external server has failed?
1172 We send messages to it periodically, and declare it failed if we
1173 don't receive a response within a given period of time.
1174 Policy decisions can usually tolerate short
1175 periods of inconsistency.
1176 The policy was decided some time ago, and is only now being put into
1177 effect, so a few milliseconds of delay is normally inconsequential.
1180 However, there are algorithms that absolutely must see consistent data.
1181 For example, the translation between a user-level SystemV semaphore
1182 ID to the corresponding in-kernel data structure is protected by RCU,
1183 but it is absolutely forbidden to update a semaphore that has just been
1185 In the Linux kernel, this need for consistency is accommodated by acquiring
1186 spinlocks located in the in-kernel data structure from within
1187 the RCU read-side critical section, and this is indicated by the
1188 green box in the figure above.
1189 Many other techniques may be used, and are in fact used within the
1193 In short, RCU is not required to maintain consistency, and other
1194 mechanisms may be used in concert with RCU when consistency is required.
1195 RCU's specialization allows it to do its job extremely well, and its
1196 ability to interoperate with other synchronization mechanisms allows
1197 the right mix of synchronization tools to be used for a given job.
1199 <h3><a name="Performance and Scalability">Performance and Scalability</a></h3>
1202 Energy efficiency is a critical component of performance today,
1203 and Linux-kernel RCU implementations must therefore avoid unnecessarily
1204 awakening idle CPUs.
1205 I cannot claim that this requirement was premeditated.
1206 In fact, I learned of it during a telephone conversation in which I
1207 was given “frank and open” feedback on the importance
1208 of energy efficiency in battery-powered systems and on specific
1209 energy-efficiency shortcomings of the Linux-kernel RCU implementation.
1210 In my experience, the battery-powered embedded community will consider
1211 any unnecessary wakeups to be extremely unfriendly acts.
1212 So much so that mere Linux-kernel-mailing-list posts are
1213 insufficient to vent their ire.
1216 Memory consumption is not particularly important for in most
1217 situations, and has become decreasingly
1218 so as memory sizes have expanded and memory
1219 costs have plummeted.
1220 However, as I learned from Matt Mackall's
1221 <a href="http://elinux.org/Linux_Tiny-FAQ">bloatwatch</a>
1222 efforts, memory footprint is critically important on single-CPU systems with
1223 non-preemptible (<tt>CONFIG_PREEMPT=n</tt>) kernels, and thus
1224 <a href="https://lkml.kernel.org/g/20090113221724.GA15307@linux.vnet.ibm.com">tiny RCU</a>
1226 Josh Triplett has since taken over the small-memory banner with his
1227 <a href="https://tiny.wiki.kernel.org/">Linux kernel tinification</a>
1228 project, which resulted in
1229 <a href="#Sleepable RCU">SRCU</a>
1230 becoming optional for those kernels not needing it.
1233 The remaining performance requirements are, for the most part,
1235 For example, in keeping with RCU's read-side specialization,
1236 <tt>rcu_dereference()</tt> should have negligible overhead (for
1237 example, suppression of a few minor compiler optimizations).
1238 Similarly, in non-preemptible environments, <tt>rcu_read_lock()</tt> and
1239 <tt>rcu_read_unlock()</tt> should have exactly zero overhead.
1242 In preemptible environments, in the case where the RCU read-side
1243 critical section was not preempted (as will be the case for the
1244 highest-priority real-time process), <tt>rcu_read_lock()</tt> and
1245 <tt>rcu_read_unlock()</tt> should have minimal overhead.
1246 In particular, they should not contain atomic read-modify-write
1247 operations, memory-barrier instructions, preemption disabling,
1248 interrupt disabling, or backwards branches.
1249 However, in the case where the RCU read-side critical section was preempted,
1250 <tt>rcu_read_unlock()</tt> may acquire spinlocks and disable interrupts.
1251 This is why it is better to nest an RCU read-side critical section
1252 within a preempt-disable region than vice versa, at least in cases
1253 where that critical section is short enough to avoid unduly degrading
1254 real-time latencies.
1257 The <tt>synchronize_rcu()</tt> grace-period-wait primitive is
1258 optimized for throughput.
1259 It may therefore incur several milliseconds of latency in addition to
1260 the duration of the longest RCU read-side critical section.
1261 On the other hand, multiple concurrent invocations of
1262 <tt>synchronize_rcu()</tt> are required to use batching optimizations
1263 so that they can be satisfied by a single underlying grace-period-wait
1265 For example, in the Linux kernel, it is not unusual for a single
1266 grace-period-wait operation to serve more than
1267 <a href="https://www.usenix.org/conference/2004-usenix-annual-technical-conference/making-rcu-safe-deep-sub-millisecond-response">1,000 separate invocations</a>
1268 of <tt>synchronize_rcu()</tt>, thus amortizing the per-invocation
1269 overhead down to nearly zero.
1270 However, the grace-period optimization is also required to avoid
1271 measurable degradation of real-time scheduling and interrupt latencies.
1274 In some cases, the multi-millisecond <tt>synchronize_rcu()</tt>
1275 latencies are unacceptable.
1276 In these cases, <tt>synchronize_rcu_expedited()</tt> may be used
1277 instead, reducing the grace-period latency down to a few tens of
1278 microseconds on small systems, at least in cases where the RCU read-side
1279 critical sections are short.
1280 There are currently no special latency requirements for
1281 <tt>synchronize_rcu_expedited()</tt> on large systems, but,
1282 consistent with the empirical nature of the RCU specification,
1283 that is subject to change.
1284 However, there most definitely are scalability requirements:
1285 A storm of <tt>synchronize_rcu_expedited()</tt> invocations on 4096
1286 CPUs should at least make reasonable forward progress.
1287 In return for its shorter latencies, <tt>synchronize_rcu_expedited()</tt>
1288 is permitted to impose modest degradation of real-time latency
1289 on non-idle online CPUs.
1290 That said, it will likely be necessary to take further steps to reduce this
1291 degradation, hopefully to roughly that of a scheduling-clock interrupt.
1294 There are a number of situations where even
1295 <tt>synchronize_rcu_expedited()</tt>'s reduced grace-period
1296 latency is unacceptable.
1297 In these situations, the asynchronous <tt>call_rcu()</tt> can be
1298 used in place of <tt>synchronize_rcu()</tt> as follows:
1305 4 struct rcu_head rh;
1308 7 static void remove_gp_cb(struct rcu_head *rhp)
1310 9 struct foo *p = container_of(rhp, struct foo, rh);
1315 14 bool remove_gp_asynchronous(void)
1319 18 spin_lock(&gp_lock);
1320 19 p = rcu_dereference(gp);
1322 21 spin_unlock(&gp_lock);
1325 24 rcu_assign_pointer(gp, NULL);
1326 25 call_rcu(&p->rh, remove_gp_cb);
1327 26 spin_unlock(&gp_lock);
1334 A definition of <tt>struct foo</tt> is finally needed, and appears
1336 The function <tt>remove_gp_cb()</tt> is passed to <tt>call_rcu()</tt>
1337 on line 25, and will be invoked after the end of a subsequent
1339 This gets the same effect as <tt>remove_gp_synchronous()</tt>,
1340 but without forcing the updater to wait for a grace period to elapse.
1341 The <tt>call_rcu()</tt> function may be used in a number of
1342 situations where neither <tt>synchronize_rcu()</tt> nor
1343 <tt>synchronize_rcu_expedited()</tt> would be legal,
1344 including within preempt-disable code, <tt>local_bh_disable()</tt> code,
1345 interrupt-disable code, and interrupt handlers.
1346 However, even <tt>call_rcu()</tt> is illegal within NMI handlers.
1347 The callback function (<tt>remove_gp_cb()</tt> in this case) will be
1348 executed within softirq (software interrupt) environment within the
1350 either within a real softirq handler or under the protection
1351 of <tt>local_bh_disable()</tt>.
1352 In both the Linux kernel and in userspace, it is bad practice to
1353 write an RCU callback function that takes too long.
1354 Long-running operations should be relegated to separate threads or
1355 (in the Linux kernel) workqueues.
1357 <p><a name="Quick Quiz 12"><b>Quick Quiz 12</b>:</a>
1358 Why does line 19 use <tt>rcu_access_pointer()</tt>?
1359 After all, <tt>call_rcu()</tt> on line 25 stores into the
1360 structure, which would interact badly with concurrent insertions.
1361 Doesn't this mean that <tt>rcu_dereference()</tt> is required?
1362 <br><a href="#qq12answer">Answer</a>
1365 However, all that <tt>remove_gp_cb()</tt> is doing is
1366 invoking <tt>kfree()</tt> on the data element.
1367 This is a common idiom, and is supported by <tt>kfree_rcu()</tt>,
1368 which allows “fire and forget” operation as shown below:
1375 4 struct rcu_head rh;
1378 7 bool remove_gp_faf(void)
1382 11 spin_lock(&gp_lock);
1383 12 p = rcu_dereference(gp);
1385 14 spin_unlock(&gp_lock);
1388 17 rcu_assign_pointer(gp, NULL);
1389 18 kfree_rcu(p, rh);
1390 19 spin_unlock(&gp_lock);
1397 Note that <tt>remove_gp_faf()</tt> simply invokes
1398 <tt>kfree_rcu()</tt> and proceeds, without any need to pay any
1399 further attention to the subsequent grace period and <tt>kfree()</tt>.
1400 It is permissible to invoke <tt>kfree_rcu()</tt> from the same
1401 environments as for <tt>call_rcu()</tt>.
1402 Interestingly enough, DYNIX/ptx had the equivalents of
1403 <tt>call_rcu()</tt> and <tt>kfree_rcu()</tt>, but not
1404 <tt>synchronize_rcu()</tt>.
1405 This was due to the fact that RCU was not heavily used within DYNIX/ptx,
1406 so the very few places that needed something like
1407 <tt>synchronize_rcu()</tt> simply open-coded it.
1409 <p><a name="Quick Quiz 13"><b>Quick Quiz 13</b>:</a>
1410 Earlier it was claimed that <tt>call_rcu()</tt> and
1411 <tt>kfree_rcu()</tt> allowed updaters to avoid being blocked
1413 But how can that be correct, given that the invocation of the callback
1414 and the freeing of the memory (respectively) must still wait for
1415 a grace period to elapse?
1416 <br><a href="#qq13answer">Answer</a>
1419 But what if the updater must wait for the completion of code to be
1420 executed after the end of the grace period, but has other tasks
1421 that can be carried out in the meantime?
1422 The polling-style <tt>get_state_synchronize_rcu()</tt> and
1423 <tt>cond_synchronize_rcu()</tt> functions may be used for this
1424 purpose, as shown below:
1428 1 bool remove_gp_poll(void)
1433 6 spin_lock(&gp_lock);
1434 7 p = rcu_access_pointer(gp);
1436 9 spin_unlock(&gp_lock);
1439 12 rcu_assign_pointer(gp, NULL);
1440 13 spin_unlock(&gp_lock);
1441 14 s = get_state_synchronize_rcu();
1442 15 do_something_while_waiting();
1443 16 cond_synchronize_rcu(s);
1451 On line 14, <tt>get_state_synchronize_rcu()</tt> obtains a
1452 “cookie” from RCU,
1453 then line 15 carries out other tasks,
1454 and finally, line 16 returns immediately if a grace period has
1455 elapsed in the meantime, but otherwise waits as required.
1456 The need for <tt>get_state_synchronize_rcu</tt> and
1457 <tt>cond_synchronize_rcu()</tt> has appeared quite recently,
1458 so it is too early to tell whether they will stand the test of time.
1461 RCU thus provides a range of tools to allow updaters to strike the
1462 required tradeoff between latency, flexibility and CPU overhead.
1464 <h3><a name="Composability">Composability</a></h3>
1467 Composability has received much attention in recent years, perhaps in part
1468 due to the collision of multicore hardware with object-oriented techniques
1469 designed in single-threaded environments for single-threaded use.
1470 And in theory, RCU read-side critical sections may be composed, and in
1471 fact may be nested arbitrarily deeply.
1472 In practice, as with all real-world implementations of composable
1473 constructs, there are limitations.
1476 Implementations of RCU for which <tt>rcu_read_lock()</tt>
1477 and <tt>rcu_read_unlock()</tt> generate no code, such as
1478 Linux-kernel RCU when <tt>CONFIG_PREEMPT=n</tt>, can be
1479 nested arbitrarily deeply.
1480 After all, there is no overhead.
1481 Except that if all these instances of <tt>rcu_read_lock()</tt>
1482 and <tt>rcu_read_unlock()</tt> are visible to the compiler,
1483 compilation will eventually fail due to exhausting memory,
1484 mass storage, or user patience, whichever comes first.
1485 If the nesting is not visible to the compiler, as is the case with
1486 mutually recursive functions each in its own translation unit,
1487 stack overflow will result.
1488 If the nesting takes the form of loops, either the control variable
1489 will overflow or (in the Linux kernel) you will get an RCU CPU stall warning.
1490 Nevertheless, this class of RCU implementations is one
1491 of the most composable constructs in existence.
1494 RCU implementations that explicitly track nesting depth
1495 are limited by the nesting-depth counter.
1496 For example, the Linux kernel's preemptible RCU limits nesting to
1498 This should suffice for almost all practical purposes.
1499 That said, a consecutive pair of RCU read-side critical sections
1500 between which there is an operation that waits for a grace period
1501 cannot be enclosed in another RCU read-side critical section.
1502 This is because it is not legal to wait for a grace period within
1503 an RCU read-side critical section: To do so would result either
1505 in RCU implicitly splitting the enclosing RCU read-side critical
1506 section, neither of which is conducive to a long-lived and prosperous
1510 It is worth noting that RCU is not alone in limiting composability.
1511 For example, many transactional-memory implementations prohibit
1512 composing a pair of transactions separated by an irrevocable
1513 operation (for example, a network receive operation).
1514 For another example, lock-based critical sections can be composed
1515 surprisingly freely, but only if deadlock is avoided.
1518 In short, although RCU read-side critical sections are highly composable,
1519 care is required in some situations, just as is the case for any other
1520 composable synchronization mechanism.
1522 <h3><a name="Corner Cases">Corner Cases</a></h3>
1525 A given RCU workload might have an endless and intense stream of
1526 RCU read-side critical sections, perhaps even so intense that there
1527 was never a point in time during which there was not at least one
1528 RCU read-side critical section in flight.
1529 RCU cannot allow this situation to block grace periods: As long as
1530 all the RCU read-side critical sections are finite, grace periods
1531 must also be finite.
1534 That said, preemptible RCU implementations could potentially result
1535 in RCU read-side critical sections being preempted for long durations,
1536 which has the effect of creating a long-duration RCU read-side
1538 This situation can arise only in heavily loaded systems, but systems using
1539 real-time priorities are of course more vulnerable.
1540 Therefore, RCU priority boosting is provided to help deal with this
1542 That said, the exact requirements on RCU priority boosting will likely
1543 evolve as more experience accumulates.
1546 Other workloads might have very high update rates.
1547 Although one can argue that such workloads should instead use
1548 something other than RCU, the fact remains that RCU must
1549 handle such workloads gracefully.
1550 This requirement is another factor driving batching of grace periods,
1551 but it is also the driving force behind the checks for large numbers
1552 of queued RCU callbacks in the <tt>call_rcu()</tt> code path.
1553 Finally, high update rates should not delay RCU read-side critical
1554 sections, although some read-side delays can occur when using
1555 <tt>synchronize_rcu_expedited()</tt>, courtesy of this function's use
1556 of <tt>try_stop_cpus()</tt>.
1557 (In the future, <tt>synchronize_rcu_expedited()</tt> will be
1558 converted to use lighter-weight inter-processor interrupts (IPIs),
1559 but this will still disturb readers, though to a much smaller degree.)
1562 Although all three of these corner cases were understood in the early
1563 1990s, a simple user-level test consisting of <tt>close(open(path))</tt>
1565 in the early 2000s suddenly provided a much deeper appreciation of the
1566 high-update-rate corner case.
1567 This test also motivated addition of some RCU code to react to high update
1568 rates, for example, if a given CPU finds itself with more than 10,000
1569 RCU callbacks queued, it will cause RCU to take evasive action by
1570 more aggressively starting grace periods and more aggressively forcing
1571 completion of grace-period processing.
1572 This evasive action causes the grace period to complete more quickly,
1573 but at the cost of restricting RCU's batching optimizations, thus
1574 increasing the CPU overhead incurred by that grace period.
1576 <h2><a name="Software-Engineering Requirements">
1577 Software-Engineering Requirements</a></h2>
1580 Between Murphy's Law and “To err is human”, it is necessary to
1581 guard against mishaps and misuse:
1584 <li> It is all too easy to forget to use <tt>rcu_read_lock()</tt>
1585 everywhere that it is needed, so kernels built with
1586 <tt>CONFIG_PROVE_RCU=y</tt> will spat if
1587 <tt>rcu_dereference()</tt> is used outside of an
1588 RCU read-side critical section.
1589 Update-side code can use <tt>rcu_dereference_protected()</tt>,
1591 <a href="https://lwn.net/Articles/371986/">lockdep expression</a>
1592 to indicate what is providing the protection.
1593 If the indicated protection is not provided, a lockdep splat
1597 Code shared between readers and updaters can use
1598 <tt>rcu_dereference_check()</tt>, which also takes a
1599 lockdep expression, and emits a lockdep splat if neither
1600 <tt>rcu_read_lock()</tt> nor the indicated protection
1602 In addition, <tt>rcu_dereference_raw()</tt> is used in those
1603 (hopefully rare) cases where the required protection cannot
1604 be easily described.
1605 Finally, <tt>rcu_read_lock_held()</tt> is provided to
1606 allow a function to verify that it has been invoked within
1607 an RCU read-side critical section.
1608 I was made aware of this set of requirements shortly after Thomas
1609 Gleixner audited a number of RCU uses.
1610 <li> A given function might wish to check for RCU-related preconditions
1611 upon entry, before using any other RCU API.
1612 The <tt>rcu_lockdep_assert()</tt> does this job,
1613 asserting the expression in kernels having lockdep enabled
1614 and doing nothing otherwise.
1615 <li> It is also easy to forget to use <tt>rcu_assign_pointer()</tt>
1616 and <tt>rcu_dereference()</tt>, perhaps (incorrectly)
1617 substituting a simple assignment.
1618 To catch this sort of error, a given RCU-protected pointer may be
1619 tagged with <tt>__rcu</tt>, after which running sparse
1620 with <tt>CONFIG_SPARSE_RCU_POINTER=y</tt> will complain
1621 about simple-assignment accesses to that pointer.
1622 Arnd Bergmann made me aware of this requirement, and also
1624 <a href="https://lwn.net/Articles/376011/">patch series</a>.
1625 <li> Kernels built with <tt>CONFIG_DEBUG_OBJECTS_RCU_HEAD=y</tt>
1626 will splat if a data element is passed to <tt>call_rcu()</tt>
1627 twice in a row, without a grace period in between.
1628 (This error is similar to a double free.)
1629 The corresponding <tt>rcu_head</tt> structures that are
1630 dynamically allocated are automatically tracked, but
1631 <tt>rcu_head</tt> structures allocated on the stack
1632 must be initialized with <tt>init_rcu_head_on_stack()</tt>
1633 and cleaned up with <tt>destroy_rcu_head_on_stack()</tt>.
1634 Similarly, statically allocated non-stack <tt>rcu_head</tt>
1635 structures must be initialized with <tt>init_rcu_head()</tt>
1636 and cleaned up with <tt>destroy_rcu_head()</tt>.
1637 Mathieu Desnoyers made me aware of this requirement, and also
1639 <a href="https://lkml.kernel.org/g/20100319013024.GA28456@Krystal">patch</a>.
1640 <li> An infinite loop in an RCU read-side critical section will
1641 eventually trigger an RCU CPU stall warning splat, with
1642 the duration of “eventually” being controlled by the
1643 <tt>RCU_CPU_STALL_TIMEOUT</tt> <tt>Kconfig</tt> option, or,
1644 alternatively, by the
1645 <tt>rcupdate.rcu_cpu_stall_timeout</tt> boot/sysfs
1647 However, RCU is not obligated to produce this splat
1648 unless there is a grace period waiting on that particular
1649 RCU read-side critical section.
1651 Some extreme workloads might intentionally delay
1652 RCU grace periods, and systems running those workloads can
1653 be booted with <tt>rcupdate.rcu_cpu_stall_suppress</tt>
1654 to suppress the splats.
1655 This kernel parameter may also be set via <tt>sysfs</tt>.
1656 Furthermore, RCU CPU stall warnings are counter-productive
1657 during sysrq dumps and during panics.
1658 RCU therefore supplies the <tt>rcu_sysrq_start()</tt> and
1659 <tt>rcu_sysrq_end()</tt> API members to be called before
1660 and after long sysrq dumps.
1661 RCU also supplies the <tt>rcu_panic()</tt> notifier that is
1662 automatically invoked at the beginning of a panic to suppress
1663 further RCU CPU stall warnings.
1666 This requirement made itself known in the early 1990s, pretty
1667 much the first time that it was necessary to debug a CPU stall.
1668 That said, the initial implementation in DYNIX/ptx was quite
1669 generic in comparison with that of Linux.
1670 <li> Although it would be very good to detect pointers leaking out
1671 of RCU read-side critical sections, there is currently no
1672 good way of doing this.
1673 One complication is the need to distinguish between pointers
1674 leaking and pointers that have been handed off from RCU to
1675 some other synchronization mechanism, for example, reference
1677 <li> In kernels built with <tt>CONFIG_RCU_TRACE=y</tt>, RCU-related
1678 information is provided via both debugfs and event tracing.
1679 <li> Open-coded use of <tt>rcu_assign_pointer()</tt> and
1680 <tt>rcu_dereference()</tt> to create typical linked
1681 data structures can be surprisingly error-prone.
1682 Therefore, RCU-protected
1683 <a href="https://lwn.net/Articles/609973/#RCU List APIs">linked lists</a>
1684 and, more recently, RCU-protected
1685 <a href="https://lwn.net/Articles/612100/">hash tables</a>
1687 Many other special-purpose RCU-protected data structures are
1688 available in the Linux kernel and the userspace RCU library.
1689 <li> Some linked structures are created at compile time, but still
1690 require <tt>__rcu</tt> checking.
1691 The <tt>RCU_POINTER_INITIALIZER()</tt> macro serves this
1693 <li> It is not necessary to use <tt>rcu_assign_pointer()</tt>
1694 when creating linked structures that are to be published via
1695 a single external pointer.
1696 The <tt>RCU_INIT_POINTER()</tt> macro is provided for
1697 this task and also for assigning <tt>NULL</tt> pointers
1702 This not a hard-and-fast list: RCU's diagnostic capabilities will
1703 continue to be guided by the number and type of usage bugs found
1704 in real-world RCU usage.
1706 <h2><a name="Linux Kernel Complications">Linux Kernel Complications</a></h2>
1709 The Linux kernel provides an interesting environment for all kinds of
1710 software, including RCU.
1711 Some of the relevant points of interest are as follows:
1714 <li> <a href="#Configuration">Configuration</a>.
1715 <li> <a href="#Firmware Interface">Firmware Interface</a>.
1716 <li> <a href="#Early Boot">Early Boot</a>.
1717 <li> <a href="#Interrupts and NMIs">
1718 Interrupts and non-maskable interrupts (NMIs)</a>.
1719 <li> <a href="#Loadable Modules">Loadable Modules</a>.
1720 <li> <a href="#Hotplug CPU">Hotplug CPU</a>.
1721 <li> <a href="#Scheduler and RCU">Scheduler and RCU</a>.
1722 <li> <a href="#Tracing and RCU">Tracing and RCU</a>.
1723 <li> <a href="#Energy Efficiency">Energy Efficiency</a>.
1724 <li> <a href="#Memory Efficiency">Memory Efficiency</a>.
1725 <li> <a href="#Performance, Scalability, Response Time, and Reliability">
1726 Performance, Scalability, Response Time, and Reliability</a>.
1730 This list is probably incomplete, but it does give a feel for the
1731 most notable Linux-kernel complications.
1732 Each of the following sections covers one of the above topics.
1734 <h3><a name="Configuration">Configuration</a></h3>
1737 RCU's goal is automatic configuration, so that almost nobody
1738 needs to worry about RCU's <tt>Kconfig</tt> options.
1739 And for almost all users, RCU does in fact work well
1740 “out of the box.”
1743 However, there are specialized use cases that are handled by
1744 kernel boot parameters and <tt>Kconfig</tt> options.
1745 Unfortunately, the <tt>Kconfig</tt> system will explicitly ask users
1746 about new <tt>Kconfig</tt> options, which requires almost all of them
1747 be hidden behind a <tt>CONFIG_RCU_EXPERT</tt> <tt>Kconfig</tt> option.
1750 This all should be quite obvious, but the fact remains that
1751 Linus Torvalds recently had to
1752 <a href="https://lkml.kernel.org/g/CA+55aFy4wcCwaL4okTs8wXhGZ5h-ibecy_Meg9C4MNQrUnwMcg@mail.gmail.com">remind</a>
1753 me of this requirement.
1755 <h3><a name="Firmware Interface">Firmware Interface</a></h3>
1758 In many cases, kernel obtains information about the system from the
1759 firmware, and sometimes things are lost in translation.
1760 Or the translation is accurate, but the original message is bogus.
1763 For example, some systems' firmware overreports the number of CPUs,
1764 sometimes by a large factor.
1765 If RCU naively believed the firmware, as it used to do,
1766 it would create too many per-CPU kthreads.
1767 Although the resulting system will still run correctly, the extra
1768 kthreads needlessly consume memory and can cause confusion
1769 when they show up in <tt>ps</tt> listings.
1772 RCU must therefore wait for a given CPU to actually come online before
1773 it can allow itself to believe that the CPU actually exists.
1774 The resulting “ghost CPUs” (which are never going to
1775 come online) cause a number of
1776 <a href="https://paulmck.livejournal.com/37494.html">interesting complications</a>.
1778 <h3><a name="Early Boot">Early Boot</a></h3>
1781 The Linux kernel's boot sequence is an interesting process,
1782 and RCU is used early, even before <tt>rcu_init()</tt>
1784 In fact, a number of RCU's primitives can be used as soon as the
1785 initial task's <tt>task_struct</tt> is available and the
1786 boot CPU's per-CPU variables are set up.
1787 The read-side primitives (<tt>rcu_read_lock()</tt>,
1788 <tt>rcu_read_unlock()</tt>, <tt>rcu_dereference()</tt>,
1789 and <tt>rcu_access_pointer()</tt>) will operate normally very early on,
1790 as will <tt>rcu_assign_pointer()</tt>.
1793 Although <tt>call_rcu()</tt> may be invoked at any
1794 time during boot, callbacks are not guaranteed to be invoked until after
1795 the scheduler is fully up and running.
1796 This delay in callback invocation is due to the fact that RCU does not
1797 invoke callbacks until it is fully initialized, and this full initialization
1798 cannot occur until after the scheduler has initialized itself to the
1799 point where RCU can spawn and run its kthreads.
1800 In theory, it would be possible to invoke callbacks earlier,
1801 however, this is not a panacea because there would be severe restrictions
1802 on what operations those callbacks could invoke.
1805 Perhaps surprisingly, <tt>synchronize_rcu()</tt>,
1806 <a href="#Bottom-Half Flavor"><tt>synchronize_rcu_bh()</tt></a>
1807 (<a href="#Bottom-Half Flavor">discussed below</a>),
1809 <a href="#Sched Flavor"><tt>synchronize_sched()</tt></a>
1810 will all operate normally
1811 during very early boot, the reason being that there is only one CPU
1812 and preemption is disabled.
1813 This means that the call <tt>synchronize_rcu()</tt> (or friends)
1814 itself is a quiescent
1815 state and thus a grace period, so the early-boot implementation can
1819 Both <tt>synchronize_rcu_bh()</tt> and <tt>synchronize_sched()</tt>
1820 continue to operate normally through the remainder of boot, courtesy
1821 of the fact that preemption is disabled across their RCU read-side
1822 critical sections and also courtesy of the fact that there is still
1824 However, once the scheduler starts initializing, preemption is enabled.
1825 There is still only a single CPU, but the fact that preemption is enabled
1826 means that the no-op implementation of <tt>synchronize_rcu()</tt> no
1827 longer works in <tt>CONFIG_PREEMPT=y</tt> kernels.
1828 Therefore, as soon as the scheduler starts initializing, the early-boot
1829 fastpath is disabled.
1830 This means that <tt>synchronize_rcu()</tt> switches to its runtime
1831 mode of operation where it posts callbacks, which in turn means that
1832 any call to <tt>synchronize_rcu()</tt> will block until the corresponding
1833 callback is invoked.
1834 Unfortunately, the callback cannot be invoked until RCU's runtime
1835 grace-period machinery is up and running, which cannot happen until
1836 the scheduler has initialized itself sufficiently to allow RCU's
1837 kthreads to be spawned.
1838 Therefore, invoking <tt>synchronize_rcu()</tt> during scheduler
1839 initialization can result in deadlock.
1841 <p><a name="Quick Quiz 14"><b>Quick Quiz 14</b>:</a>
1842 So what happens with <tt>synchronize_rcu()</tt> during
1843 scheduler initialization for <tt>CONFIG_PREEMPT=n</tt>
1845 <br><a href="#qq14answer">Answer</a>
1848 I learned of these boot-time requirements as a result of a series of
1851 <h3><a name="Interrupts and NMIs">Interrupts and NMIs</a></h3>
1854 The Linux kernel has interrupts, and RCU read-side critical sections are
1855 legal within interrupt handlers and within interrupt-disabled regions
1856 of code, as are invocations of <tt>call_rcu()</tt>.
1859 Some Linux-kernel architectures can enter an interrupt handler from
1860 non-idle process context, and then just never leave it, instead stealthily
1861 transitioning back to process context.
1862 This trick is sometimes used to invoke system calls from inside the kernel.
1863 These “half-interrupts” mean that RCU has to be very careful
1864 about how it counts interrupt nesting levels.
1865 I learned of this requirement the hard way during a rewrite
1866 of RCU's dyntick-idle code.
1869 The Linux kernel has non-maskable interrupts (NMIs), and
1870 RCU read-side critical sections are legal within NMI handlers.
1871 Thankfully, RCU update-side primitives, including
1872 <tt>call_rcu()</tt>, are prohibited within NMI handlers.
1875 The name notwithstanding, some Linux-kernel architectures
1876 can have nested NMIs, which RCU must handle correctly.
1878 <a href="https://lkml.kernel.org/g/CALCETrXLq1y7e_dKFPgou-FKHB6Pu-r8+t-6Ds+8=va7anBWDA@mail.gmail.com">surprised me</a>
1879 with this requirement;
1880 he also kindly surprised me with
1881 <a href="https://lkml.kernel.org/g/CALCETrXSY9JpW3uE6H8WYk81sg56qasA2aqmjMPsq5dOtzso=g@mail.gmail.com">an algorithm</a>
1882 that meets this requirement.
1884 <h3><a name="Loadable Modules">Loadable Modules</a></h3>
1887 The Linux kernel has loadable modules, and these modules can
1889 After a given module has been unloaded, any attempt to call
1890 one of its functions results in a segmentation fault.
1891 The module-unload functions must therefore cancel any
1892 delayed calls to loadable-module functions, for example,
1893 any outstanding <tt>mod_timer()</tt> must be dealt with
1894 via <tt>del_timer_sync()</tt> or similar.
1897 Unfortunately, there is no way to cancel an RCU callback;
1898 once you invoke <tt>call_rcu()</tt>, the callback function is
1899 going to eventually be invoked, unless the system goes down first.
1900 Because it is normally considered socially irresponsible to crash the system
1901 in response to a module unload request, we need some other way
1902 to deal with in-flight RCU callbacks.
1905 RCU therefore provides
1906 <tt><a href="https://lwn.net/Articles/217484/">rcu_barrier()</a></tt>,
1907 which waits until all in-flight RCU callbacks have been invoked.
1908 If a module uses <tt>call_rcu()</tt>, its exit function should therefore
1909 prevent any future invocation of <tt>call_rcu()</tt>, then invoke
1910 <tt>rcu_barrier()</tt>.
1911 In theory, the underlying module-unload code could invoke
1912 <tt>rcu_barrier()</tt> unconditionally, but in practice this would
1913 incur unacceptable latencies.
1916 Nikita Danilov noted this requirement for an analogous filesystem-unmount
1917 situation, and Dipankar Sarma incorporated <tt>rcu_barrier()</tt> into RCU.
1918 The need for <tt>rcu_barrier()</tt> for module unloading became
1921 <h3><a name="Hotplug CPU">Hotplug CPU</a></h3>
1924 The Linux kernel supports CPU hotplug, which means that CPUs
1926 It is of course illegal to use any RCU API member from an offline CPU.
1927 This requirement was present from day one in DYNIX/ptx, but
1928 on the other hand, the Linux kernel's CPU-hotplug implementation
1929 is “interesting.”
1932 The Linux-kernel CPU-hotplug implementation has notifiers that
1933 are used to allow the various kernel subsystems (including RCU)
1934 to respond appropriately to a given CPU-hotplug operation.
1935 Most RCU operations may be invoked from CPU-hotplug notifiers,
1936 including even normal synchronous grace-period operations
1937 such as <tt>synchronize_rcu()</tt>.
1938 However, expedited grace-period operations such as
1939 <tt>synchronize_rcu_expedited()</tt> are not supported,
1940 due to the fact that current implementations block CPU-hotplug
1941 operations, which could result in deadlock.
1944 In addition, all-callback-wait operations such as
1945 <tt>rcu_barrier()</tt> are also not supported, due to the
1946 fact that there are phases of CPU-hotplug operations where
1947 the outgoing CPU's callbacks will not be invoked until after
1948 the CPU-hotplug operation ends, which could also result in deadlock.
1950 <h3><a name="Scheduler and RCU">Scheduler and RCU</a></h3>
1953 RCU depends on the scheduler, and the scheduler uses RCU to
1954 protect some of its data structures.
1955 This means the scheduler is forbidden from acquiring
1956 the runqueue locks and the priority-inheritance locks
1957 in the middle of an outermost RCU read-side critical section unless either
1958 (1) it releases them before exiting that same
1959 RCU read-side critical section, or
1960 (2) interrupts are disabled across
1961 that entire RCU read-side critical section.
1962 This same prohibition also applies (recursively!) to any lock that is acquired
1963 while holding any lock to which this prohibition applies.
1964 Adhering to this rule prevents preemptible RCU from invoking
1965 <tt>rcu_read_unlock_special()</tt> while either runqueue or
1966 priority-inheritance locks are held, thus avoiding deadlock.
1969 Prior to v4.4, it was only necessary to disable preemption across
1970 RCU read-side critical sections that acquired scheduler locks.
1971 In v4.4, expedited grace periods started using IPIs, and these
1972 IPIs could force a <tt>rcu_read_unlock()</tt> to take the slowpath.
1973 Therefore, this expedited-grace-period change required disabling of
1974 interrupts, not just preemption.
1977 For RCU's part, the preemptible-RCU <tt>rcu_read_unlock()</tt>
1978 implementation must be written carefully to avoid similar deadlocks.
1979 In particular, <tt>rcu_read_unlock()</tt> must tolerate an
1980 interrupt where the interrupt handler invokes both
1981 <tt>rcu_read_lock()</tt> and <tt>rcu_read_unlock()</tt>.
1982 This possibility requires <tt>rcu_read_unlock()</tt> to use
1983 negative nesting levels to avoid destructive recursion via
1984 interrupt handler's use of RCU.
1987 This pair of mutual scheduler-RCU requirements came as a
1988 <a href="https://lwn.net/Articles/453002/">complete surprise</a>.
1991 As noted above, RCU makes use of kthreads, and it is necessary to
1992 avoid excessive CPU-time accumulation by these kthreads.
1993 This requirement was no surprise, but RCU's violation of it
1994 when running context-switch-heavy workloads when built with
1995 <tt>CONFIG_NO_HZ_FULL=y</tt>
1996 <a href="http://www.rdrop.com/users/paulmck/scalability/paper/BareMetal.2015.01.15b.pdf">did come as a surprise [PDF]</a>.
1997 RCU has made good progress towards meeting this requirement, even
1998 for context-switch-have <tt>CONFIG_NO_HZ_FULL=y</tt> workloads,
1999 but there is room for further improvement.
2001 <h3><a name="Tracing and RCU">Tracing and RCU</a></h3>
2004 It is possible to use tracing on RCU code, but tracing itself
2006 For this reason, <tt>rcu_dereference_raw_notrace()</tt>
2007 is provided for use by tracing, which avoids the destructive
2008 recursion that could otherwise ensue.
2009 This API is also used by virtualization in some architectures,
2010 where RCU readers execute in environments in which tracing
2012 The tracing folks both located the requirement and provided the
2013 needed fix, so this surprise requirement was relatively painless.
2015 <h3><a name="Energy Efficiency">Energy Efficiency</a></h3>
2018 Interrupting idle CPUs is considered socially unacceptable,
2019 especially by people with battery-powered embedded systems.
2020 RCU therefore conserves energy by detecting which CPUs are
2021 idle, including tracking CPUs that have been interrupted from idle.
2022 This is a large part of the energy-efficiency requirement,
2023 so I learned of this via an irate phone call.
2026 Because RCU avoids interrupting idle CPUs, it is illegal to
2027 execute an RCU read-side critical section on an idle CPU.
2028 (Kernels built with <tt>CONFIG_PROVE_RCU=y</tt> will splat
2030 The <tt>RCU_NONIDLE()</tt> macro and <tt>_rcuidle</tt>
2031 event tracing is provided to work around this restriction.
2032 In addition, <tt>rcu_is_watching()</tt> may be used to
2033 test whether or not it is currently legal to run RCU read-side
2034 critical sections on this CPU.
2035 I learned of the need for diagnostics on the one hand
2036 and <tt>RCU_NONIDLE()</tt> on the other while inspecting
2038 Steven Rostedt supplied <tt>_rcuidle</tt> event tracing,
2039 which is used quite heavily in the idle loop.
2042 It is similarly socially unacceptable to interrupt an
2043 <tt>nohz_full</tt> CPU running in userspace.
2044 RCU must therefore track <tt>nohz_full</tt> userspace
2047 <a href="https://lwn.net/Articles/558284/"><tt>CONFIG_NO_HZ_FULL_SYSIDLE=y</tt></a>
2048 kernels, RCU must separately track idle CPUs on the one hand and
2049 CPUs that are either idle or executing in userspace on the other.
2050 In both cases, RCU must be able to sample state at two points in
2051 time, and be able to determine whether or not some other CPU spent
2052 any time idle and/or executing in userspace.
2055 These energy-efficiency requirements have proven quite difficult to
2056 understand and to meet, for example, there have been more than five
2057 clean-sheet rewrites of RCU's energy-efficiency code, the last of
2058 which was finally able to demonstrate
2059 <a href="http://www.rdrop.com/users/paulmck/realtime/paper/AMPenergy.2013.04.19a.pdf">real energy savings running on real hardware [PDF]</a>.
2061 I learned of many of these requirements via angry phone calls:
2062 Flaming me on the Linux-kernel mailing list was apparently not
2063 sufficient to fully vent their ire at RCU's energy-efficiency bugs!
2065 <h3><a name="Memory Efficiency">Memory Efficiency</a></h3>
2068 Although small-memory non-realtime systems can simply use Tiny RCU,
2069 code size is only one aspect of memory efficiency.
2070 Another aspect is the size of the <tt>rcu_head</tt> structure
2071 used by <tt>call_rcu()</tt> and <tt>kfree_rcu()</tt>.
2072 Although this structure contains nothing more than a pair of pointers,
2073 it does appear in many RCU-protected data structures, including
2074 some that are size critical.
2075 The <tt>page</tt> structure is a case in point, as evidenced by
2076 the many occurrences of the <tt>union</tt> keyword within that structure.
2079 This need for memory efficiency is one reason that RCU uses hand-crafted
2080 singly linked lists to track the <tt>rcu_head</tt> structures that
2081 are waiting for a grace period to elapse.
2082 It is also the reason why <tt>rcu_head</tt> structures do not contain
2083 debug information, such as fields tracking the file and line of the
2084 <tt>call_rcu()</tt> or <tt>kfree_rcu()</tt> that posted them.
2085 Although this information might appear in debug-only kernel builds at some
2086 point, in the meantime, the <tt>->func</tt> field will often provide
2087 the needed debug information.
2090 However, in some cases, the need for memory efficiency leads to even
2091 more extreme measures.
2092 Returning to the <tt>page</tt> structure, the <tt>rcu_head</tt> field
2093 shares storage with a great many other structures that are used at
2094 various points in the corresponding page's lifetime.
2095 In order to correctly resolve certain
2096 <a href="https://lkml.kernel.org/g/1439976106-137226-1-git-send-email-kirill.shutemov@linux.intel.com">race conditions</a>,
2097 the Linux kernel's memory-management subsystem needs a particular bit
2098 to remain zero during all phases of grace-period processing,
2099 and that bit happens to map to the bottom bit of the
2100 <tt>rcu_head</tt> structure's <tt>->next</tt> field.
2101 RCU makes this guarantee as long as <tt>call_rcu()</tt>
2102 is used to post the callback, as opposed to <tt>kfree_rcu()</tt>
2103 or some future “lazy”
2104 variant of <tt>call_rcu()</tt> that might one day be created for
2105 energy-efficiency purposes.
2107 <h3><a name="Performance, Scalability, Response Time, and Reliability">
2108 Performance, Scalability, Response Time, and Reliability</a></h3>
2112 <a href="#Performance and Scalability">earlier discussion</a>,
2113 RCU is used heavily by hot code paths in performance-critical
2114 portions of the Linux kernel's networking, security, virtualization,
2115 and scheduling code paths.
2116 RCU must therefore use efficient implementations, especially in its
2117 read-side primitives.
2118 To that end, it would be good if preemptible RCU's implementation
2119 of <tt>rcu_read_lock()</tt> could be inlined, however, doing
2120 this requires resolving <tt>#include</tt> issues with the
2121 <tt>task_struct</tt> structure.
2124 The Linux kernel supports hardware configurations with up to
2125 4096 CPUs, which means that RCU must be extremely scalable.
2126 Algorithms that involve frequent acquisitions of global locks or
2127 frequent atomic operations on global variables simply cannot be
2128 tolerated within the RCU implementation.
2129 RCU therefore makes heavy use of a combining tree based on the
2130 <tt>rcu_node</tt> structure.
2131 RCU is required to tolerate all CPUs continuously invoking any
2132 combination of RCU's runtime primitives with minimal per-operation
2134 In fact, in many cases, increasing load must <i>decrease</i> the
2135 per-operation overhead, witness the batching optimizations for
2136 <tt>synchronize_rcu()</tt>, <tt>call_rcu()</tt>,
2137 <tt>synchronize_rcu_expedited()</tt>, and <tt>rcu_barrier()</tt>.
2138 As a general rule, RCU must cheerfully accept whatever the
2139 rest of the Linux kernel decides to throw at it.
2142 The Linux kernel is used for real-time workloads, especially
2143 in conjunction with the
2144 <a href="https://rt.wiki.kernel.org/index.php/Main_Page">-rt patchset</a>.
2145 The real-time-latency response requirements are such that the
2146 traditional approach of disabling preemption across RCU
2147 read-side critical sections is inappropriate.
2148 Kernels built with <tt>CONFIG_PREEMPT=y</tt> therefore
2149 use an RCU implementation that allows RCU read-side critical
2150 sections to be preempted.
2151 This requirement made its presence known after users made it
2152 clear that an earlier
2153 <a href="https://lwn.net/Articles/107930/">real-time patch</a>
2154 did not meet their needs, in conjunction with some
2155 <a href="https://lkml.kernel.org/g/20050318002026.GA2693@us.ibm.com">RCU issues</a>
2156 encountered by a very early version of the -rt patchset.
2159 In addition, RCU must make do with a sub-100-microsecond real-time latency
2161 In fact, on smaller systems with the -rt patchset, the Linux kernel
2162 provides sub-20-microsecond real-time latencies for the whole kernel,
2164 RCU's scalability and latency must therefore be sufficient for
2165 these sorts of configurations.
2166 To my surprise, the sub-100-microsecond real-time latency budget
2167 <a href="http://www.rdrop.com/users/paulmck/realtime/paper/bigrt.2013.01.31a.LCA.pdf">
2168 applies to even the largest systems [PDF]</a>,
2169 up to and including systems with 4096 CPUs.
2170 This real-time requirement motivated the grace-period kthread, which
2171 also simplified handling of a number of race conditions.
2174 RCU must avoid degrading real-time response for CPU-bound threads, whether
2175 executing in usermode (which is one use case for
2176 <tt>CONFIG_NO_HZ_FULL=y</tt>) or in the kernel.
2177 That said, CPU-bound loops in the kernel must execute
2178 <tt>cond_resched_rcu_qs()</tt> at least once per few tens of milliseconds
2179 in order to avoid receiving an IPI from RCU.
2182 Finally, RCU's status as a synchronization primitive means that
2183 any RCU failure can result in arbitrary memory corruption that can be
2184 extremely difficult to debug.
2185 This means that RCU must be extremely reliable, which in
2186 practice also means that RCU must have an aggressive stress-test
2188 This stress-test suite is called <tt>rcutorture</tt>.
2191 Although the need for <tt>rcutorture</tt> was no surprise,
2192 the current immense popularity of the Linux kernel is posing
2193 interesting—and perhaps unprecedented—validation
2195 To see this, keep in mind that there are well over one billion
2196 instances of the Linux kernel running today, given Android
2197 smartphones, Linux-powered televisions, and servers.
2198 This number can be expected to increase sharply with the advent of
2199 the celebrated Internet of Things.
2202 Suppose that RCU contains a race condition that manifests on average
2203 once per million years of runtime.
2204 This bug will be occurring about three times per <i>day</i> across
2206 RCU could simply hide behind hardware error rates, given that no one
2207 should really expect their smartphone to last for a million years.
2208 However, anyone taking too much comfort from this thought should
2209 consider the fact that in most jurisdictions, a successful multi-year
2210 test of a given mechanism, which might include a Linux kernel,
2211 suffices for a number of types of safety-critical certifications.
2212 In fact, rumor has it that the Linux kernel is already being used
2213 in production for safety-critical applications.
2214 I don't know about you, but I would feel quite bad if a bug in RCU
2216 Which might explain my recent focus on validation and verification.
2218 <h2><a name="Other RCU Flavors">Other RCU Flavors</a></h2>
2221 One of the more surprising things about RCU is that there are now
2222 no fewer than five <i>flavors</i>, or API families.
2223 In addition, the primary flavor that has been the sole focus up to
2224 this point has two different implementations, non-preemptible and
2226 The other four flavors are listed below, with requirements for each
2227 described in a separate section.
2230 <li> <a href="#Bottom-Half Flavor">Bottom-Half Flavor</a>
2231 <li> <a href="#Sched Flavor">Sched Flavor</a>
2232 <li> <a href="#Sleepable RCU">Sleepable RCU</a>
2233 <li> <a href="#Tasks RCU">Tasks RCU</a>
2234 <li> <a href="#Waiting for Multiple Grace Periods">
2235 Waiting for Multiple Grace Periods</a>
2238 <h3><a name="Bottom-Half Flavor">Bottom-Half Flavor</a></h3>
2241 The softirq-disable (AKA “bottom-half”,
2242 hence the “_bh” abbreviations)
2243 flavor of RCU, or <i>RCU-bh</i>, was developed by
2244 Dipankar Sarma to provide a flavor of RCU that could withstand the
2245 network-based denial-of-service attacks researched by Robert
2247 These attacks placed so much networking load on the system
2248 that some of the CPUs never exited softirq execution,
2249 which in turn prevented those CPUs from ever executing a context switch,
2250 which, in the RCU implementation of that time, prevented grace periods
2252 The result was an out-of-memory condition and a system hang.
2255 The solution was the creation of RCU-bh, which does
2256 <tt>local_bh_disable()</tt>
2257 across its read-side critical sections, and which uses the transition
2258 from one type of softirq processing to another as a quiescent state
2259 in addition to context switch, idle, user mode, and offline.
2260 This means that RCU-bh grace periods can complete even when some of
2261 the CPUs execute in softirq indefinitely, thus allowing algorithms
2262 based on RCU-bh to withstand network-based denial-of-service attacks.
2266 <tt>rcu_read_lock_bh()</tt> and <tt>rcu_read_unlock_bh()</tt>
2267 disable and re-enable softirq handlers, any attempt to start a softirq
2269 RCU-bh read-side critical section will be deferred.
2270 In this case, <tt>rcu_read_unlock_bh()</tt>
2271 will invoke softirq processing, which can take considerable time.
2272 One can of course argue that this softirq overhead should be associated
2273 with the code following the RCU-bh read-side critical section rather
2274 than <tt>rcu_read_unlock_bh()</tt>, but the fact
2275 is that most profiling tools cannot be expected to make this sort
2276 of fine distinction.
2277 For example, suppose that a three-millisecond-long RCU-bh read-side
2278 critical section executes during a time of heavy networking load.
2279 There will very likely be an attempt to invoke at least one softirq
2280 handler during that three milliseconds, but any such invocation will
2281 be delayed until the time of the <tt>rcu_read_unlock_bh()</tt>.
2282 This can of course make it appear at first glance as if
2283 <tt>rcu_read_unlock_bh()</tt> was executing very slowly.
2287 <a href="https://lwn.net/Articles/609973/#RCU Per-Flavor API Table">RCU-bh API</a>
2289 <tt>rcu_read_lock_bh()</tt>,
2290 <tt>rcu_read_unlock_bh()</tt>,
2291 <tt>rcu_dereference_bh()</tt>,
2292 <tt>rcu_dereference_bh_check()</tt>,
2293 <tt>synchronize_rcu_bh()</tt>,
2294 <tt>synchronize_rcu_bh_expedited()</tt>,
2295 <tt>call_rcu_bh()</tt>,
2296 <tt>rcu_barrier_bh()</tt>, and
2297 <tt>rcu_read_lock_bh_held()</tt>.
2299 <h3><a name="Sched Flavor">Sched Flavor</a></h3>
2302 Before preemptible RCU, waiting for an RCU grace period had the
2303 side effect of also waiting for all pre-existing interrupt
2305 However, there are legitimate preemptible-RCU implementations that
2306 do not have this property, given that any point in the code outside
2307 of an RCU read-side critical section can be a quiescent state.
2308 Therefore, <i>RCU-sched</i> was created, which follows “classic”
2309 RCU in that an RCU-sched grace period waits for for pre-existing
2310 interrupt and NMI handlers.
2311 In kernels built with <tt>CONFIG_PREEMPT=n</tt>, the RCU and RCU-sched
2312 APIs have identical implementations, while kernels built with
2313 <tt>CONFIG_PREEMPT=y</tt> provide a separate implementation for each.
2316 Note well that in <tt>CONFIG_PREEMPT=y</tt> kernels,
2317 <tt>rcu_read_lock_sched()</tt> and <tt>rcu_read_unlock_sched()</tt>
2318 disable and re-enable preemption, respectively.
2319 This means that if there was a preemption attempt during the
2320 RCU-sched read-side critical section, <tt>rcu_read_unlock_sched()</tt>
2321 will enter the scheduler, with all the latency and overhead entailed.
2322 Just as with <tt>rcu_read_unlock_bh()</tt>, this can make it look
2323 as if <tt>rcu_read_unlock_sched()</tt> was executing very slowly.
2324 However, the highest-priority task won't be preempted, so that task
2325 will enjoy low-overhead <tt>rcu_read_unlock_sched()</tt> invocations.
2329 <a href="https://lwn.net/Articles/609973/#RCU Per-Flavor API Table">RCU-sched API</a>
2331 <tt>rcu_read_lock_sched()</tt>,
2332 <tt>rcu_read_unlock_sched()</tt>,
2333 <tt>rcu_read_lock_sched_notrace()</tt>,
2334 <tt>rcu_read_unlock_sched_notrace()</tt>,
2335 <tt>rcu_dereference_sched()</tt>,
2336 <tt>rcu_dereference_sched_check()</tt>,
2337 <tt>synchronize_sched()</tt>,
2338 <tt>synchronize_rcu_sched_expedited()</tt>,
2339 <tt>call_rcu_sched()</tt>,
2340 <tt>rcu_barrier_sched()</tt>, and
2341 <tt>rcu_read_lock_sched_held()</tt>.
2342 However, anything that disables preemption also marks an RCU-sched
2343 read-side critical section, including
2344 <tt>preempt_disable()</tt> and <tt>preempt_enable()</tt>,
2345 <tt>local_irq_save()</tt> and <tt>local_irq_restore()</tt>,
2348 <h3><a name="Sleepable RCU">Sleepable RCU</a></h3>
2351 For well over a decade, someone saying “I need to block within
2352 an RCU read-side critical section” was a reliable indication
2353 that this someone did not understand RCU.
2354 After all, if you are always blocking in an RCU read-side critical
2355 section, you can probably afford to use a higher-overhead synchronization
2357 However, that changed with the advent of the Linux kernel's notifiers,
2358 whose RCU read-side critical
2359 sections almost never sleep, but sometimes need to.
2360 This resulted in the introduction of
2361 <a href="https://lwn.net/Articles/202847/">sleepable RCU</a>,
2365 SRCU allows different domains to be defined, with each such domain
2366 defined by an instance of an <tt>srcu_struct</tt> structure.
2367 A pointer to this structure must be passed in to each SRCU function,
2368 for example, <tt>synchronize_srcu(&ss)</tt>, where
2369 <tt>ss</tt> is the <tt>srcu_struct</tt> structure.
2370 The key benefit of these domains is that a slow SRCU reader in one
2371 domain does not delay an SRCU grace period in some other domain.
2372 That said, one consequence of these domains is that read-side code
2373 must pass a “cookie” from <tt>srcu_read_lock()</tt>
2374 to <tt>srcu_read_unlock()</tt>, for example, as follows:
2380 3 idx = srcu_read_lock(&ss);
2382 5 srcu_read_unlock(&ss, idx);
2387 As noted above, it is legal to block within SRCU read-side critical sections,
2388 however, with great power comes great responsibility.
2389 If you block forever in one of a given domain's SRCU read-side critical
2390 sections, then that domain's grace periods will also be blocked forever.
2391 Of course, one good way to block forever is to deadlock, which can
2392 happen if any operation in a given domain's SRCU read-side critical
2393 section can block waiting, either directly or indirectly, for that domain's
2394 grace period to elapse.
2395 For example, this results in a self-deadlock:
2401 3 idx = srcu_read_lock(&ss);
2403 5 synchronize_srcu(&ss);
2404 6 srcu_read_unlock(&ss, idx);
2409 However, if line 5 acquired a mutex that was held across
2410 a <tt>synchronize_srcu()</tt> for domain <tt>ss</tt>,
2411 deadlock would still be possible.
2412 Furthermore, if line 5 acquired a mutex that was held across
2413 a <tt>synchronize_srcu()</tt> for some other domain <tt>ss1</tt>,
2414 and if an <tt>ss1</tt>-domain SRCU read-side critical section
2415 acquired another mutex that was held across as <tt>ss</tt>-domain
2416 <tt>synchronize_srcu()</tt>,
2417 deadlock would again be possible.
2418 Such a deadlock cycle could extend across an arbitrarily large number
2419 of different SRCU domains.
2420 Again, with great power comes great responsibility.
2423 Unlike the other RCU flavors, SRCU read-side critical sections can
2424 run on idle and even offline CPUs.
2425 This ability requires that <tt>srcu_read_lock()</tt> and
2426 <tt>srcu_read_unlock()</tt> contain memory barriers, which means
2427 that SRCU readers will run a bit slower than would RCU readers.
2428 It also motivates the <tt>smp_mb__after_srcu_read_unlock()</tt>
2429 API, which, in combination with <tt>srcu_read_unlock()</tt>,
2430 guarantees a full memory barrier.
2434 <a href="https://lwn.net/Articles/609973/#RCU Per-Flavor API Table">SRCU API</a>
2436 <tt>srcu_read_lock()</tt>,
2437 <tt>srcu_read_unlock()</tt>,
2438 <tt>srcu_dereference()</tt>,
2439 <tt>srcu_dereference_check()</tt>,
2440 <tt>synchronize_srcu()</tt>,
2441 <tt>synchronize_srcu_expedited()</tt>,
2442 <tt>call_srcu()</tt>,
2443 <tt>srcu_barrier()</tt>, and
2444 <tt>srcu_read_lock_held()</tt>.
2446 <tt>DEFINE_SRCU()</tt>,
2447 <tt>DEFINE_STATIC_SRCU()</tt>, and
2448 <tt>init_srcu_struct()</tt>
2449 APIs for defining and initializing <tt>srcu_struct</tt> structures.
2451 <h3><a name="Tasks RCU">Tasks RCU</a></h3>
2454 Some forms of tracing use “tramopolines” to handle the
2455 binary rewriting required to install different types of probes.
2456 It would be good to be able to free old trampolines, which sounds
2457 like a job for some form of RCU.
2458 However, because it is necessary to be able to install a trace
2459 anywhere in the code, it is not possible to use read-side markers
2460 such as <tt>rcu_read_lock()</tt> and <tt>rcu_read_unlock()</tt>.
2461 In addition, it does not work to have these markers in the trampoline
2462 itself, because there would need to be instructions following
2463 <tt>rcu_read_unlock()</tt>.
2464 Although <tt>synchronize_rcu()</tt> would guarantee that execution
2465 reached the <tt>rcu_read_unlock()</tt>, it would not be able to
2466 guarantee that execution had completely left the trampoline.
2469 The solution, in the form of
2470 <a href="https://lwn.net/Articles/607117/"><i>Tasks RCU</i></a>,
2472 read-side critical sections that are delimited by voluntary context
2473 switches, that is, calls to <tt>schedule()</tt>,
2474 <tt>cond_resched_rcu_qs()</tt>, and
2475 <tt>synchronize_rcu_tasks()</tt>.
2476 In addition, transitions to and from userspace execution also delimit
2477 tasks-RCU read-side critical sections.
2480 The tasks-RCU API is quite compact, consisting only of
2481 <tt>call_rcu_tasks()</tt>,
2482 <tt>synchronize_rcu_tasks()</tt>, and
2483 <tt>rcu_barrier_tasks()</tt>.
2485 <h3><a name="Waiting for Multiple Grace Periods">
2486 Waiting for Multiple Grace Periods</a></h3>
2489 Perhaps you have an RCU protected data structure that is accessed from
2490 RCU read-side critical sections, from softirq handlers, and from
2491 hardware interrupt handlers.
2492 That is three flavors of RCU, the normal flavor, the bottom-half flavor,
2493 and the sched flavor.
2494 How to wait for a compound grace period?
2497 The best approach is usually to “just say no!” and
2498 insert <tt>rcu_read_lock()</tt> and <tt>rcu_read_unlock()</tt>
2499 around each RCU read-side critical section, regardless of what
2500 environment it happens to be in.
2501 But suppose that some of the RCU read-side critical sections are
2502 on extremely hot code paths, and that use of <tt>CONFIG_PREEMPT=n</tt>
2503 is not a viable option, so that <tt>rcu_read_lock()</tt> and
2504 <tt>rcu_read_unlock()</tt> are not free.
2508 You <i>could</i> wait on all three grace periods in succession, as follows:
2512 1 synchronize_rcu();
2513 2 synchronize_rcu_bh();
2514 3 synchronize_sched();
2519 This works, but triples the update-side latency penalty.
2520 In cases where this is not acceptable, <tt>synchronize_rcu_mult()</tt>
2521 may be used to wait on all three flavors of grace period concurrently:
2525 1 synchronize_rcu_mult(call_rcu, call_rcu_bh, call_rcu_sched);
2530 But what if it is necessary to also wait on SRCU?
2531 This can be done as follows:
2535 1 static void call_my_srcu(struct rcu_head *head,
2536 2 void (*func)(struct rcu_head *head))
2538 4 call_srcu(&my_srcu, head, func);
2541 7 synchronize_rcu_mult(call_rcu, call_rcu_bh, call_rcu_sched, call_my_srcu);
2546 If you needed to wait on multiple different flavors of SRCU
2547 (but why???), you would need to create a wrapper function resembling
2548 <tt>call_my_srcu()</tt> for each SRCU flavor.
2550 <p><a name="Quick Quiz 15"><b>Quick Quiz 15</b>:</a>
2551 But what if I need to wait for multiple RCU flavors, but I also need
2552 the grace periods to be expedited?
2553 <br><a href="#qq15answer">Answer</a>
2556 Again, it is usually better to adjust the RCU read-side critical sections
2557 to use a single flavor of RCU, but when this is not feasible, you can use
2558 <tt>synchronize_rcu_mult()</tt>.
2560 <h2><a name="Possible Future Changes">Possible Future Changes</a></h2>
2563 One of the tricks that RCU uses to attain update-side scalability is
2564 to increase grace-period latency with increasing numbers of CPUs.
2565 If this becomes a serious problem, it will be necessary to rework the
2566 grace-period state machine so as to avoid the need for the additional
2570 Expedited grace periods scan the CPUs, so their latency and overhead
2571 increases with increasing numbers of CPUs.
2572 If this becomes a serious problem on large systems, it will be necessary
2573 to do some redesign to avoid this scalability problem.
2576 RCU disables CPU hotplug in a few places, perhaps most notably in the
2577 expedited grace-period and <tt>rcu_barrier()</tt> operations.
2578 If there is a strong reason to use expedited grace periods in CPU-hotplug
2579 notifiers, it will be necessary to avoid disabling CPU hotplug.
2580 This would introduce some complexity, so there had better be a <i>very</i>
2584 The tradeoff between grace-period latency on the one hand and interruptions
2585 of other CPUs on the other hand may need to be re-examined.
2586 The desire is of course for zero grace-period latency as well as zero
2587 interprocessor interrupts undertaken during an expedited grace period
2589 While this ideal is unlikely to be achievable, it is quite possible that
2590 further improvements can be made.
2593 The multiprocessor implementations of RCU use a combining tree that
2594 groups CPUs so as to reduce lock contention and increase cache locality.
2595 However, this combining tree does not spread its memory across NUMA
2596 nodes nor does it align the CPU groups with hardware features such
2597 as sockets or cores.
2598 Such spreading and alignment is currently believed to be unnecessary
2599 because the hotpath read-side primitives do not access the combining
2600 tree, nor does <tt>call_rcu()</tt> in the common case.
2601 If you believe that your architecture needs such spreading and alignment,
2602 then your architecture should also benefit from the
2603 <tt>rcutree.rcu_fanout_leaf</tt> boot parameter, which can be set
2604 to the number of CPUs in a socket, NUMA node, or whatever.
2605 If the number of CPUs is too large, use a fraction of the number of
2607 If the number of CPUs is a large prime number, well, that certainly
2608 is an “interesting” architectural choice!
2609 More flexible arrangements might be considered, but only if
2610 <tt>rcutree.rcu_fanout_leaf</tt> has proven inadequate, and only
2611 if the inadequacy has been demonstrated by a carefully run and
2612 realistic system-level workload.
2615 Please note that arrangements that require RCU to remap CPU numbers will
2616 require extremely good demonstration of need and full exploration of
2620 There is an embarrassingly large number of flavors of RCU, and this
2621 number has been increasing over time.
2622 Perhaps it will be possible to combine some at some future date.
2625 RCU's various kthreads are reasonably recent additions.
2626 It is quite likely that adjustments will be required to more gracefully
2627 handle extreme loads.
2628 It might also be necessary to be able to relate CPU utilization by
2629 RCU's kthreads and softirq handlers to the code that instigated this
2631 For example, RCU callback overhead might be charged back to the
2632 originating <tt>call_rcu()</tt> instance, though probably not
2633 in production kernels.
2635 <h2><a name="Summary">Summary</a></h2>
2638 This document has presented more than two decade's worth of RCU
2640 Given that the requirements keep changing, this will not be the last
2641 word on this subject, but at least it serves to get an important
2642 subset of the requirements set forth.
2644 <h2><a name="Acknowledgments">Acknowledgments</a></h2>
2646 I am grateful to Steven Rostedt, Lai Jiangshan, Ingo Molnar,
2647 Oleg Nesterov, Borislav Petkov, Peter Zijlstra, Boqun Feng, and
2648 Andy Lutomirski for their help in rendering
2649 this article human readable, and to Michelle Rankin for her support
2651 Other contributions are acknowledged in the Linux kernel's git archive.
2652 The cartoon is copyright (c) 2013 by Melissa Broussard,
2654 under the terms of the Creative Commons Attribution-Share Alike 3.0
2655 United States license.
2657 <h3><a name="Answers to Quick Quizzes">
2658 Answers to Quick Quizzes</a></h3>
2660 <a name="qq1answer"></a>
2661 <p><b>Quick Quiz 1</b>:
2663 You said that updaters can make useful forward progress concurrently
2664 with readers, but pre-existing readers will block
2665 <tt>synchronize_rcu()</tt>!!!
2666 Just who are you trying to fool???
2669 </p><p><b>Answer</b>:
2670 First, if updaters do not wish to be blocked by readers, they can use
2671 <tt>call_rcu()</tt> or <tt>kfree_rcu()</tt>, which will
2673 Second, even when using <tt>synchronize_rcu()</tt>, the other
2674 update-side code does run concurrently with readers, whether pre-existing
2678 </p><p><a href="#Quick%20Quiz%201"><b>Back to Quick Quiz 1</b>.</a>
2680 <a name="qq2answer"></a>
2681 <p><b>Quick Quiz 2</b>:
2682 Why is the <tt>synchronize_rcu()</tt> on line 28 needed?
2685 </p><p><b>Answer</b>:
2686 Without that extra grace period, memory reordering could result in
2687 <tt>do_something_dlm()</tt> executing <tt>do_something()</tt>
2688 concurrently with the last bits of <tt>recovery()</tt>.
2691 </p><p><a href="#Quick%20Quiz%202"><b>Back to Quick Quiz 2</b>.</a>
2693 <a name="qq3answer"></a>
2694 <p><b>Quick Quiz 3</b>:
2695 But <tt>rcu_assign_pointer()</tt> does nothing to prevent the
2696 two assignments to <tt>p->a</tt> and <tt>p->b</tt>
2697 from being reordered.
2698 Can't that also cause problems?
2701 </p><p><b>Answer</b>:
2703 The readers cannot see either of these two fields until
2704 the assignment to <tt>gp</tt>, by which time both fields are
2706 So reordering the assignments
2707 to <tt>p->a</tt> and <tt>p->b</tt> cannot possibly
2711 </p><p><a href="#Quick%20Quiz%203"><b>Back to Quick Quiz 3</b>.</a>
2713 <a name="qq4answer"></a>
2714 <p><b>Quick Quiz 4</b>:
2715 Without the <tt>rcu_dereference()</tt> or the
2716 <tt>rcu_access_pointer()</tt>, what destructive optimizations
2717 might the compiler make use of?
2720 </p><p><b>Answer</b>:
2721 Let's start with what happens to <tt>do_something_gp()</tt>
2722 if it fails to use <tt>rcu_dereference()</tt>.
2723 It could reuse a value formerly fetched from this same pointer.
2724 It could also fetch the pointer from <tt>gp</tt> in a byte-at-a-time
2725 manner, resulting in <i>load tearing</i>, in turn resulting a bytewise
2726 mash-up of two distince pointer values.
2727 It might even use value-speculation optimizations, where it makes a wrong
2728 guess, but by the time it gets around to checking the value, an update
2729 has changed the pointer to match the wrong guess.
2730 Too bad about any dereferences that returned pre-initialization garbage
2734 For <tt>remove_gp_synchronous()</tt>, as long as all modifications
2735 to <tt>gp</tt> are carried out while holding <tt>gp_lock</tt>,
2736 the above optimizations are harmless.
2738 with <tt>CONFIG_SPARSE_RCU_POINTER=y</tt>,
2739 <tt>sparse</tt> will complain if you
2740 define <tt>gp</tt> with <tt>__rcu</tt> and then
2741 access it without using
2742 either <tt>rcu_access_pointer()</tt> or <tt>rcu_dereference()</tt>.
2745 </p><p><a href="#Quick%20Quiz%204"><b>Back to Quick Quiz 4</b>.</a>
2747 <a name="qq5answer"></a>
2748 <p><b>Quick Quiz 5</b>:
2749 Given that multiple CPUs can start RCU read-side critical sections
2750 at any time without any ordering whatsoever, how can RCU possibly tell whether
2751 or not a given RCU read-side critical section starts before a
2752 given instance of <tt>synchronize_rcu()</tt>?
2755 </p><p><b>Answer</b>:
2756 If RCU cannot tell whether or not a given
2757 RCU read-side critical section starts before a
2758 given instance of <tt>synchronize_rcu()</tt>,
2759 then it must assume that the RCU read-side critical section
2761 In other words, a given instance of <tt>synchronize_rcu()</tt>
2762 can avoid waiting on a given RCU read-side critical section only
2763 if it can prove that <tt>synchronize_rcu()</tt> started first.
2766 </p><p><a href="#Quick%20Quiz%205"><b>Back to Quick Quiz 5</b>.</a>
2768 <a name="qq6answer"></a>
2769 <p><b>Quick Quiz 6</b>:
2770 The first and second guarantees require unbelievably strict ordering!
2771 Are all these memory barriers <i> really</i> required?
2774 </p><p><b>Answer</b>:
2775 Yes, they really are required.
2776 To see why the first guarantee is required, consider the following
2780 <li> CPU 1: <tt>rcu_read_lock()</tt>
2781 <li> CPU 1: <tt>q = rcu_dereference(gp);
2782 /* Very likely to return p. */</tt>
2783 <li> CPU 0: <tt>list_del_rcu(p);</tt>
2784 <li> CPU 0: <tt>synchronize_rcu()</tt> starts.
2785 <li> CPU 1: <tt>do_something_with(q->a);
2786 /* No smp_mb(), so might happen after kfree(). */</tt>
2787 <li> CPU 1: <tt>rcu_read_unlock()</tt>
2788 <li> CPU 0: <tt>synchronize_rcu()</tt> returns.
2789 <li> CPU 0: <tt>kfree(p);</tt>
2793 Therefore, there absolutely must be a full memory barrier between the
2794 end of the RCU read-side critical section and the end of the
2798 The sequence of events demonstrating the necessity of the second rule
2802 <li> CPU 0: <tt>list_del_rcu(p);</tt>
2803 <li> CPU 0: <tt>synchronize_rcu()</tt> starts.
2804 <li> CPU 1: <tt>rcu_read_lock()</tt>
2805 <li> CPU 1: <tt>q = rcu_dereference(gp);
2806 /* Might return p if no memory barrier. */</tt>
2807 <li> CPU 0: <tt>synchronize_rcu()</tt> returns.
2808 <li> CPU 0: <tt>kfree(p);</tt>
2809 <li> CPU 1: <tt>do_something_with(q->a); /* Boom!!! */</tt>
2810 <li> CPU 1: <tt>rcu_read_unlock()</tt>
2814 And similarly, without a memory barrier between the beginning of the
2815 grace period and the beginning of the RCU read-side critical section,
2816 CPU 1 might end up accessing the freelist.
2819 The “as if” rule of course applies, so that any implementation
2820 that acts as if the appropriate memory barriers were in place is a
2821 correct implementation.
2822 That said, it is much easier to fool yourself into believing that you have
2823 adhered to the as-if rule than it is to actually adhere to it!
2826 </p><p><a href="#Quick%20Quiz%206"><b>Back to Quick Quiz 6</b>.</a>
2828 <a name="qq7answer"></a>
2829 <p><b>Quick Quiz 7</b>:
2830 But how does the upgrade-to-write operation exclude other readers?
2833 </p><p><b>Answer</b>:
2834 It doesn't, just like normal RCU updates, which also do not exclude
2838 </p><p><a href="#Quick%20Quiz%207"><b>Back to Quick Quiz 7</b>.</a>
2840 <a name="qq8answer"></a>
2841 <p><b>Quick Quiz 8</b>:
2842 Can't the compiler also reorder this code?
2845 </p><p><b>Answer</b>:
2846 No, the volatile casts in <tt>READ_ONCE()</tt> and
2847 <tt>WRITE_ONCE()</tt> prevent the compiler from reordering in
2848 this particular case.
2851 </p><p><a href="#Quick%20Quiz%208"><b>Back to Quick Quiz 8</b>.</a>
2853 <a name="qq9answer"></a>
2854 <p><b>Quick Quiz 9</b>:
2855 Suppose that synchronize_rcu() did wait until all readers had completed.
2856 Would the updater be able to rely on this?
2859 </p><p><b>Answer</b>:
2861 Even if <tt>synchronize_rcu()</tt> were to wait until
2862 all readers had completed, a new reader might start immediately after
2863 <tt>synchronize_rcu()</tt> completed.
2864 Therefore, the code following
2865 <tt>synchronize_rcu()</tt> cannot rely on there being no readers
2869 </p><p><a href="#Quick%20Quiz%209"><b>Back to Quick Quiz 9</b>.</a>
2871 <a name="qq10answer"></a>
2872 <p><b>Quick Quiz 10</b>:
2873 How long a sequence of grace periods, each separated by an RCU read-side
2874 critical section, would be required to partition the RCU read-side
2875 critical sections at the beginning and end of the chain?
2878 </p><p><b>Answer</b>:
2879 In theory, an infinite number.
2880 In practice, an unknown number that is sensitive to both implementation
2881 details and timing considerations.
2882 Therefore, even in practice, RCU users must abide by the theoretical rather
2883 than the practical answer.
2886 </p><p><a href="#Quick%20Quiz%2010"><b>Back to Quick Quiz 10</b>.</a>
2888 <a name="qq11answer"></a>
2889 <p><b>Quick Quiz 11</b>:
2890 What about sleeping locks?
2893 </p><p><b>Answer</b>:
2894 These are forbidden within Linux-kernel RCU read-side critical sections
2895 because it is not legal to place a quiescent state (in this case,
2896 voluntary context switch) within an RCU read-side critical section.
2897 However, sleeping locks may be used within userspace RCU read-side critical
2898 sections, and also within Linux-kernel sleepable RCU
2899 <a href="#Sleepable RCU">(SRCU)</a>
2900 read-side critical sections.
2901 In addition, the -rt patchset turns spinlocks into a sleeping locks so
2902 that the corresponding critical sections can be preempted, which
2903 also means that these sleeplockified spinlocks (but not other sleeping locks!)
2904 may be acquire within -rt-Linux-kernel RCU read-side critical sections.
2907 Note that it <i>is</i> legal for a normal RCU read-side critical section
2908 to conditionally acquire a sleeping locks (as in <tt>mutex_trylock()</tt>),
2909 but only as long as it does not loop indefinitely attempting to
2910 conditionally acquire that sleeping locks.
2911 The key point is that things like <tt>mutex_trylock()</tt>
2912 either return with the mutex held, or return an error indication if
2913 the mutex was not immediately available.
2914 Either way, <tt>mutex_trylock()</tt> returns immediately without sleeping.
2917 </p><p><a href="#Quick%20Quiz%2011"><b>Back to Quick Quiz 11</b>.</a>
2919 <a name="qq12answer"></a>
2920 <p><b>Quick Quiz 12</b>:
2921 Why does line 19 use <tt>rcu_access_pointer()</tt>?
2922 After all, <tt>call_rcu()</tt> on line 25 stores into the
2923 structure, which would interact badly with concurrent insertions.
2924 Doesn't this mean that <tt>rcu_dereference()</tt> is required?
2927 </p><p><b>Answer</b>:
2928 Presumably the <tt>->gp_lock</tt> acquired on line 18 excludes
2929 any changes, including any insertions that <tt>rcu_dereference()</tt>
2930 would protect against.
2931 Therefore, any insertions will be delayed until after <tt>->gp_lock</tt>
2932 is released on line 25, which in turn means that
2933 <tt>rcu_access_pointer()</tt> suffices.
2936 </p><p><a href="#Quick%20Quiz%2012"><b>Back to Quick Quiz 12</b>.</a>
2938 <a name="qq13answer"></a>
2939 <p><b>Quick Quiz 13</b>:
2940 Earlier it was claimed that <tt>call_rcu()</tt> and
2941 <tt>kfree_rcu()</tt> allowed updaters to avoid being blocked
2943 But how can that be correct, given that the invocation of the callback
2944 and the freeing of the memory (respectively) must still wait for
2945 a grace period to elapse?
2948 </p><p><b>Answer</b>:
2949 We could define things this way, but keep in mind that this sort of
2950 definition would say that updates in garbage-collected languages
2951 cannot complete until the next time the garbage collector runs,
2952 which does not seem at all reasonable.
2953 The key point is that in most cases, an updater using either
2954 <tt>call_rcu()</tt> or <tt>kfree_rcu()</tt> can proceed to the
2955 next update as soon as it has invoked <tt>call_rcu()</tt> or
2956 <tt>kfree_rcu()</tt>, without having to wait for a subsequent
2960 </p><p><a href="#Quick%20Quiz%2013"><b>Back to Quick Quiz 13</b>.</a>
2962 <a name="qq14answer"></a>
2963 <p><b>Quick Quiz 14</b>:
2964 So what happens with <tt>synchronize_rcu()</tt> during
2965 scheduler initialization for <tt>CONFIG_PREEMPT=n</tt>
2969 </p><p><b>Answer</b>:
2970 In <tt>CONFIG_PREEMPT=n</tt> kernel, <tt>synchronize_rcu()</tt>
2971 maps directly to <tt>synchronize_sched()</tt>.
2972 Therefore, <tt>synchronize_rcu()</tt> works normally throughout
2973 boot in <tt>CONFIG_PREEMPT=n</tt> kernels.
2974 However, your code must also work in <tt>CONFIG_PREEMPT=y</tt> kernels,
2975 so it is still necessary to avoid invoking <tt>synchronize_rcu()</tt>
2976 during scheduler initialization.
2979 </p><p><a href="#Quick%20Quiz%2014"><b>Back to Quick Quiz 14</b>.</a>
2981 <a name="qq15answer"></a>
2982 <p><b>Quick Quiz 15</b>:
2983 But what if I need to wait for multiple RCU flavors, but I also need
2984 the grace periods to be expedited?
2987 </p><p><b>Answer</b>:
2988 If you are using expedited grace periods, there should be less penalty
2989 for waiting on them in succession.
2990 But if that is nevertheless a problem, you can use workqueues or multiple
2991 kthreads to wait on the various expedited grace periods concurrently.
2994 </p><p><a href="#Quick%20Quiz%2015"><b>Back to Quick Quiz 15</b>.</a>
projects / karo-tx-linux.git / blob