[linux/fpc-iii.git] / Documentation / RCU / Design / Memory-Ordering / Tree-RCU-Memory-Ordering.html
| blob | 8651b0b4fd79f37caef5572037656d1eb2a43cda |
3 <html>
12 <p>This document gives a rough visual overview of how Tree RCU's
13 grace-period memory ordering guarantee is provided.
15 <ol>
17 What Is Tree RCU's Grace Period Memory Ordering Guarantee?</a>
19 Tree RCU Grace Period Memory Ordering Building Blocks</a>
21 Tree RCU Grace Period Memory Ordering Components</a>
23 </ol>
26 What Is Tree RCU's Grace Period Memory Ordering Guarantee?</a></h3>
28 <p>RCU grace periods provide extremely strong memory-ordering guarantees
29 for non-idle non-offline code.
30 Any code that happens after the end of a given RCU grace period is guaranteed
31 to see the effects of all accesses prior to the beginning of that grace
32 period that are within RCU read-side critical sections.
33 Similarly, any code that happens before the beginning of a given RCU grace
34 period is guaranteed to see the effects of all accesses following the end
35 of that grace period that are within RCU read-side critical sections.
38 for which RCU-sched read-side critical sections include any region
39 of code for which preemption is disabled.
40 Given that each individual machine instruction can be thought of as
41 an extremely small region of preemption-disabled code, one can think of
44 <p>RCU updaters use this guarantee by splitting their updates into
45 two phases, one of which is executed before the grace period and
46 the other of which is executed after the grace period.
47 In the most common use case, phase one removes an element from
48 a linked RCU-protected data structure, and phase two frees that element.
49 For this to work, any readers that have witnessed state prior to the
50 phase-one update (in the common case, removal) must not witness state
51 following the phase-two update (in the common case, freeing).
53 <p>The RCU implementation provides this guarantee using a network
54 of lock-based critical sections, memory barriers, and per-CPU
55 processing, as is described in the following sections.
58 Tree RCU Grace Period Memory Ordering Building Blocks</a></h3>
60 <p>The workhorse for RCU's grace-period memory ordering is the
63 These critical sections use helper functions for lock acquisition, including
67 Their lock-release counterparts are
71 respectively.
72 For completeness, a
74 is also provided.
75 The key point is that the lock-acquisition functions, including
78 acquisition of the lock.
81 happening before one of the above lock-release functions will be seen
82 by all CPUs as happening before any access happening after a later
83 one of the above lock-acquisition functions.
84 Furthermore, any access happening before one of the
85 above lock-release function on any given CPU will be seen by all
86 CPUs as happening before any access happening after a later one
87 of the above lock-acquisition functions executing on that same CPU,
88 even if the lock-release and lock-acquisition functions are operating
90 Tree RCU uses these two ordering guarantees to form an ordering
91 network among all CPUs that were in any way involved in the grace
92 period, including any CPUs that came online or went offline during
93 the grace period in question.
95 <p>The following litmus test exhibits the ordering effects of these
96 lock-acquisition and lock-release functions:
98 <pre>
99 1 int x, y, z;
100 2
101 3 void task0(void)
102 4 {
103 5 raw_spin_lock_rcu_node(rnp);
105 7 r1 = READ_ONCE(y);
106 8 raw_spin_unlock_rcu_node(rnp);
107 9 }
108 10
109 11 void task1(void)
110 12 {
111 13 raw_spin_lock_rcu_node(rnp);
113 15 r2 = READ_ONCE(z);
114 16 raw_spin_unlock_rcu_node(rnp);
115 17 }
116 18
117 19 void task2(void)
118 20 {
120 22 smp_mb();
121 23 r3 = READ_ONCE(x);
122 24 }
123 25
125 </pre>
128 after all changes have propagated throughout the system.
131 on PowerPC.
135 <p>This approach must be extended to include idle CPUs, which need
136 RCU's grace-period memory ordering guarantee to extend to any
137 RCU read-side critical sections preceding and following the current
138 idle sojourn.
139 This case is handled by calls to the strongly ordered
147 <table>
150 <tr><td>
151 But what about CPUs that remain offline for the entire
152 grace period?
153 </td></tr>
156 Such CPUs will be offline at the beginning of the grace period,
157 so the grace period won't expect quiescent states from them.
158 Races between grace-period start and CPU-hotplug operations
161 </font></td></tr>
163 </table>
165 <p>The approach must be extended to handle one final case, that
167 This task might be affinitied to a CPU that is not yet aware that
168 the grace period has ended, and thus might not yet be subject to
169 the grace period's memory ordering.
172 code path.
174 <table>
177 <tr><td>
178 What? Where???
181 </td></tr>
184 That would be because I spotted the need for that
186 and it is therefore unlikely to hit mainline before v4.14.
187 Kudos to Lance Roy, Will Deacon, Peter Zijlstra, and
188 Jonathan Cameron for asking questions that sensitized me
189 to the rather elaborate sequence of events that demonstrate
190 the need for this memory barrier.
191 </font></td></tr>
193 </table>
195 <p>Tree RCU's grace--period memory-ordering guarantees rely most
197 field, so much so that it is necessary to abbreviate this pattern
198 in the diagrams in the next section.
200 shown below, which is one of several functions that enforce ordering
201 of newly arrived RCU callbacks against future grace periods:
203 <pre>
204 1 static void rcu_prepare_for_idle(void)
205 2 {
206 3 bool needwake;
207 4 struct rcu_data *rdp;
209 6 struct rcu_node *rnp;
210 7 struct rcu_state *rsp;
211 8 int tne;
212 9
213 10 if (IS_ENABLED(CONFIG_RCU_NOCB_CPU_ALL) ||
214 11 rcu_is_nocb_cpu(smp_processor_id()))
215 12 return;
216 13 tne = READ_ONCE(tick_nohz_active);
218 15 if (rcu_cpu_has_callbacks(NULL))
219 16 invoke_rcu_core();
221 18 return;
222 19 }
223 20 if (!tne)
224 21 return;
229 26 invoke_rcu_core();
230 27 return;
231 28 }
233 30 return;
235 32 for_each_rcu_flavor(rsp) {
238 35 continue;
240 37 raw_spin_lock_rcu_node(rnp);
241 38 needwake = rcu_accelerate_cbs(rsp, rnp, rdp);
242 39 raw_spin_unlock_rcu_node(rnp);
243 40 if (needwake)
244 41 rcu_gp_kthread_wake(rsp);
245 42 }
246 43 }
247 </pre>
251 We will therefore abbreviate this function as follows:
256 critical section, with the double line on top representing the additional
260 Tree RCU Grace Period Memory Ordering Components</a></h3>
262 <p>Tree RCU's grace-period memory-ordering guarantee is provided by
263 a number of RCU components:
265 <ol>
269 Self-Reported Quiescent States</a>
275 </ol>
277 <p>Each of the following section looks at the corresponding component
278 in detail.
282 <p>If RCU's grace-period guarantee is to mean anything at all, any
284 must also happen before the corresponding grace period.
285 The implementation of this portion of RCU's grace period guarantee
286 is shown in the following figure:
291 it provides no ordering guarantees, either for itself or for
292 phase one of the update (which again will usually be removal of
293 an element from an RCU-protected data structure).
295 which cannot become associated with a grace period until a later
298 <p>One set of code paths shown on the left invokes
303 Another code path in the middle is taken only in kernels built with
306 The final code path on the right is taken only in kernels built with
311 which in turn is invoked on a surviving CPU after the outgoing
312 CPU has been completely offlined.
314 <p>There are a few other code paths within grace-period processing
317 structures are associated with a future grace-period number under
320 In all cases, there is full ordering against any prior critical section
322 also full ordering against any of the current task's or CPU's prior critical
325 <p>The next section will show how this ordering ensures that any
327 one of the update)
328 happen before the start of the corresponding grace period.
330 <table>
333 <tr><td>
335 </td></tr>
341 </font></td></tr>
343 </table>
347 <p>Grace-period initialization is carried out by
348 the grace-period kernel thread, which makes several passes over the
350 This means that showing the full flow of ordering through the
351 grace-period computation will require duplicating this tree.
352 If you find this confusing, please note that the state of the
355 grace-period kernel thread's traversals are presented in multiple
356 parts, starting in this section with the various phases of
357 grace-period initialization.
359 <p>The first ordering-related grace-period initialization action is to
361 grace-period-number counter, as shown below:
366 which helps reject false-positive RCU CPU stall detection.
370 based on CPUs having come online or gone offline since the start of
371 the previous grace period.
373 structure has not transitioned to or from zero,
376 structure has transitioned from zero,
379 structure has transitioned to zero,
381 The diagram below shows the path of ordering if the leftmost
396 <p>This change will also cause each CPU's next call to
398 to notice that a new grace period has started, as described in the next
399 section.
400 But because the grace-period kthread started the grace period at the
404 the start of the grace period will happen after the actual start
405 of the grace period.
407 <table>
410 <tr><td>
411 But what about the CPU that started the grace period?
412 Why wouldn't it see the start of the grace period right when
413 it started that grace period?
414 </td></tr>
417 In some deep philosophical and overly anthromorphized
418 sense, yes, the CPU starting the grace period is immediately
419 aware of having done so.
420 However, if we instead assume that RCU is not self-aware,
421 then even the CPU starting the grace period does not really
422 become aware of the start of this grace period until its
424 On the other hand, this CPU potentially gets early notification
428 </font></td></tr>
430 </table>
433 Self-Reported Quiescent States</a></h4>
435 <p>When all entities that might block the grace period have reported
436 quiescent states (or as described in a later section, had quiescent
437 states reported on their behalf), the grace period can end.
438 Online non-idle CPUs report their own quiescent states, as shown
439 in the following diagram:
443 <p>This is for the last CPU to report a quiescent state, which signals
444 the end of the grace period.
447 is waiting for additional quiescent states.
448 However, ordering is nevertheless preserved because some later quiescent
451 <p>Any number of events can lead up to a CPU invoking
454 the start of a new grace period while holding its leaf
456 Therefore, all execution shown in this diagram happens after the
457 start of the grace period.
458 In addition, this CPU will consider any RCU read-side critical
460 to have started before the grace period, and thus a critical
461 section that the grace period must wait on.
463 <table>
466 <tr><td>
467 But a RCU read-side critical section might have started
468 after the beginning of the grace period
470 the grace period wait on such a critical section?
471 </td></tr>
474 It is indeed not necessary for the grace period to wait on such
475 a critical section.
476 However, it is permissible to wait on it.
477 And it is furthermore important to wait on it, as this
479 all-at-once grace-period start could possibly be.
480 </font></td></tr>
482 </table>
484 <p>If the CPU does a context switch, a quiescent state will be
486 On the other hand, if the CPU takes a scheduler-clock interrupt
487 while executing in usermode, a quiescent state will be noted by
489 Either way, the passage through a quiescent state will be noted
490 in a per-CPU variable.
493 this CPU (for example, after the next scheduler-clock
496 recorded quiescent state, and invoke
499 really does apply to the current grace period, it invokes
501 tree as shown at the bottom of the diagram, clearing bits from
503 and propagating up the tree when the result is zero.
506 structure only if the current CPU is reporting the last quiescent
509 structure, then there will be a later traversal by another CPU
510 (or perhaps the same one) that proceeds upwards
512 guarantees that the first CPU's quiescent state happens before the
513 remainder of the second CPU's traversal.
514 Applying this line of thought repeatedly shows that all CPUs'
515 quiescent states happen before the last CPU traverses through
522 <p>Due to energy-efficiency considerations, RCU is forbidden from
523 disturbing idle CPUs.
524 CPUs are therefore required to notify RCU when entering or leaving idle
525 state, which they do via fully ordered value-returning atomic operations
526 on a per-CPU variable.
527 The ordering effects are as shown below:
531 <p>The RCU grace-period kernel thread samples the per-CPU idleness
534 This means that any RCU read-side critical sections that precede the
535 idle period (the oval near the top of the diagram above) will happen
536 before the end of the current grace period.
537 Similarly, the beginning of the current grace period will happen before
538 any RCU read-side critical sections that follow the
539 idle period (the oval near the bottom of the diagram above).
541 <p>Plumbing this into the full grace-period execution is described
546 <p>RCU is also forbidden from disturbing offline CPUs, which might well
547 be powered off and removed from the system completely.
548 CPUs are therefore required to notify RCU of their comings and goings
549 as part of the corresponding CPU hotplug operations.
550 The ordering effects are shown below:
554 <p>Because CPU hotplug operations are much less frequent than idle transitions,
558 The RCU grace-period kernel thread samples this mask to detect CPUs
559 having gone offline since the beginning of this grace period.
561 <p>Plumbing this into the full grace-period execution is described
566 <p>As noted above, idle and offline CPUs cannot report their own
567 quiescent states, and therefore the grace-period kernel thread
568 must do the reporting on their behalf.
570 repeated every few jiffies, and its ordering effects are shown below:
574 <p>Each pass of quiescent state forcing is guaranteed to traverse the
576 states due to recently idled and/or offlined CPUs, then only the
577 leaves are traversed.
578 However, if there is a newly offlined CPU as illustrated on the left
579 or a newly idled CPU as illustrated on the right, the corresponding
580 quiescent state will be driven up towards the root.
581 As with self-reported quiescent states, the upwards driving stops
583 states outstanding from other CPUs.
585 <table>
588 <tr><td>
589 The leftmost drive to root stopped before it reached
591 there are still CPUs subordinate to that structure on
592 which the current grace period is waiting.
593 Given that, how is it possible that the rightmost drive
594 to root ended the grace period?
595 </td></tr>
598 Good analysis!
599 It is in fact impossible in the absence of bugs in RCU.
600 But this diagram is complex enough as it is, so simplicity
601 overrode accuracy.
602 You can think of it as poetic license, or you can think of
603 it as misdirection that is resolved in the
605 </font></td></tr>
607 </table>
613 to the number of the newly completed grace period, then it sets
615 again to the number of the newly completed grace period.
616 The ordering effects are shown below:
620 <p>As indicated by the oval at the bottom of the diagram, once
621 grace-period cleanup is complete, the next grace period can begin.
623 <table>
626 <tr><td>
627 But when precisely does the grace period end?
628 </td></tr>
631 There is no useful single point at which the grace period
632 can be said to end.
633 The earliest reasonable candidate is as soon as the last
634 CPU has reported its quiescent state, but it may be some
635 milliseconds before RCU becomes aware of this.
638 but it is quite possible that some CPUs have already completed
639 phase two of their updates by that time.
640 In short, if you are going to work with RCU, you need to
641 learn to embrace uncertainty.
642 </font></td></tr>
644 </table>
651 invoking its RCU callbacks that were waiting for this grace period
652 to end.
655 As shown in the diagram below, this invocation can be triggered by
658 the right, but only for kernels build with
662 allows those callbacks to carry out (either directly or indirectly
663 via wakeup) the needed phase-two processing for each update.
665 </p><p><img src="TreeRCU-callback-invocation.svg" alt="TreeRCU-callback-invocation.svg" width="60%">
667 <p>Please note that callback invocation can also be prompted by any
668 number of corner-case code paths, for example, when a CPU notes that
669 it has excessive numbers of callbacks queued.
672 required ordering against the newly completed grace period.
674 <p>However, if the callback function communicates to other CPUs,
675 for example, doing a wakeup, then it is that function's responsibility
676 to maintain ordering.
677 For example, if the callback function wakes up a task that runs on
678 some other CPU, proper ordering must in place in both the callback
679 function and the task being awakened.
680 To see why this is important, consider the top half of the
682 The callback might be running on a CPU corresponding to the leftmost
685 and the grace-period kernel thread might not yet have reached the
686 rightmost leaf.
687 In this case, the grace period's memory ordering might not yet have
688 reached that CPU, so again the callback function and the awakened
689 task must supply proper ordering.
693 <p>A stitched-together diagram is
697 Legal Statement</a></h3>
699 <p>This work represents the view of the author and does not necessarily
700 represent the view of IBM.
702 </p><p>Linux is a registered trademark of Linus Torvalds.
704 </p><p>Other company, product, and service names may be trademarks or
705 service marks of others.
707 </body></html>