1======================================================
2A Tour Through TREE_RCU's Grace-Period Memory Ordering
3======================================================
4
5August 8, 2017
6
7This article was contributed by Paul E. McKenney
8
9Introduction
10============
11
12This document gives a rough visual overview of how Tree RCU's
13grace-period memory ordering guarantee is provided.
14
15What Is Tree RCU's Grace Period Memory Ordering Guarantee?
16==========================================================
17
18RCU grace periods provide extremely strong memory-ordering guarantees
19for non-idle non-offline code.
20Any code that happens after the end of a given RCU grace period is guaranteed
21to see the effects of all accesses prior to the beginning of that grace
22period that are within RCU read-side critical sections.
23Similarly, any code that happens before the beginning of a given RCU grace
24period is guaranteed to not see the effects of all accesses following the end
25of that grace period that are within RCU read-side critical sections.
26
27Note well that RCU-sched read-side critical sections include any region
28of code for which preemption is disabled.
29Given that each individual machine instruction can be thought of as
30an extremely small region of preemption-disabled code, one can think of
31``synchronize_rcu()`` as ``smp_mb()`` on steroids.
32
33RCU updaters use this guarantee by splitting their updates into
34two phases, one of which is executed before the grace period and
35the other of which is executed after the grace period.
36In the most common use case, phase one removes an element from
37a linked RCU-protected data structure, and phase two frees that element.
38For this to work, any readers that have witnessed state prior to the
39phase-one update (in the common case, removal) must not witness state
40following the phase-two update (in the common case, freeing).
41
42The RCU implementation provides this guarantee using a network
43of lock-based critical sections, memory barriers, and per-CPU
44processing, as is described in the following sections.
45
46Tree RCU Grace Period Memory Ordering Building Blocks
47=====================================================
48
49The workhorse for RCU's grace-period memory ordering is the
50critical section for the ``rcu_node`` structure's
51``->lock``. These critical sections use helper functions for lock
52acquisition, including ``raw_spin_lock_rcu_node()``,
53``raw_spin_lock_irq_rcu_node()``, and ``raw_spin_lock_irqsave_rcu_node()``.
54Their lock-release counterparts are ``raw_spin_unlock_rcu_node()``,
55``raw_spin_unlock_irq_rcu_node()``, and
56``raw_spin_unlock_irqrestore_rcu_node()``, respectively.
57For completeness, a ``raw_spin_trylock_rcu_node()`` is also provided.
58The key point is that the lock-acquisition functions, including
59``raw_spin_trylock_rcu_node()``, all invoke ``smp_mb__after_unlock_lock()``
60immediately after successful acquisition of the lock.
61
62Therefore, for any given ``rcu_node`` structure, any access
63happening before one of the above lock-release functions will be seen
64by all CPUs as happening before any access happening after a later
65one of the above lock-acquisition functions.
66Furthermore, any access happening before one of the
67above lock-release function on any given CPU will be seen by all
68CPUs as happening before any access happening after a later one
69of the above lock-acquisition functions executing on that same CPU,
70even if the lock-release and lock-acquisition functions are operating
71on different ``rcu_node`` structures.
72Tree RCU uses these two ordering guarantees to form an ordering
73network among all CPUs that were in any way involved in the grace
74period, including any CPUs that came online or went offline during
75the grace period in question.
76
77The following litmus test exhibits the ordering effects of these
78lock-acquisition and lock-release functions::
79
80    1 int x, y, z;
81    2
82    3 void task0(void)
83    4 {
84    5   raw_spin_lock_rcu_node(rnp);
85    6   WRITE_ONCE(x, 1);
86    7   r1 = READ_ONCE(y);
87    8   raw_spin_unlock_rcu_node(rnp);
88    9 }
89   10
90   11 void task1(void)
91   12 {
92   13   raw_spin_lock_rcu_node(rnp);
93   14   WRITE_ONCE(y, 1);
94   15   r2 = READ_ONCE(z);
95   16   raw_spin_unlock_rcu_node(rnp);
96   17 }
97   18
98   19 void task2(void)
99   20 {
100   21   WRITE_ONCE(z, 1);
101   22   smp_mb();
102   23   r3 = READ_ONCE(x);
103   24 }
104   25
105   26 WARN_ON(r1 == 0 && r2 == 0 && r3 == 0);
106
107The ``WARN_ON()`` is evaluated at "the end of time",
108after all changes have propagated throughout the system.
109Without the ``smp_mb__after_unlock_lock()`` provided by the
110acquisition functions, this ``WARN_ON()`` could trigger, for example
111on PowerPC.
112The ``smp_mb__after_unlock_lock()`` invocations prevent this
113``WARN_ON()`` from triggering.
114
115This approach must be extended to include idle CPUs, which need
116RCU's grace-period memory ordering guarantee to extend to any
117RCU read-side critical sections preceding and following the current
118idle sojourn.
119This case is handled by calls to the strongly ordered
120``atomic_add_return()`` read-modify-write atomic operation that
121is invoked within ``rcu_dynticks_eqs_enter()`` at idle-entry
122time and within ``rcu_dynticks_eqs_exit()`` at idle-exit time.
123The grace-period kthread invokes ``rcu_dynticks_snap()`` and
124``rcu_dynticks_in_eqs_since()`` (both of which invoke
125an ``atomic_add_return()`` of zero) to detect idle CPUs.
126
127+-----------------------------------------------------------------------+
128| **Quick Quiz**:                                                       |
129+-----------------------------------------------------------------------+
130| But what about CPUs that remain offline for the entire grace period?  |
131+-----------------------------------------------------------------------+
132| **Answer**:                                                           |
133+-----------------------------------------------------------------------+
134| Such CPUs will be offline at the beginning of the grace period, so    |
135| the grace period won't expect quiescent states from them. Races       |
136| between grace-period start and CPU-hotplug operations are mediated    |
137| by the CPU's leaf ``rcu_node`` structure's ``->lock`` as described    |
138| above.                                                                |
139+-----------------------------------------------------------------------+
140
141The approach must be extended to handle one final case, that of waking a
142task blocked in ``synchronize_rcu()``. This task might be affinitied to
143a CPU that is not yet aware that the grace period has ended, and thus
144might not yet be subject to the grace period's memory ordering.
145Therefore, there is an ``smp_mb()`` after the return from
146``wait_for_completion()`` in the ``synchronize_rcu()`` code path.
147
148+-----------------------------------------------------------------------+
149| **Quick Quiz**:                                                       |
150+-----------------------------------------------------------------------+
151| What? Where??? I don't see any ``smp_mb()`` after the return from     |
152| ``wait_for_completion()``!!!                                          |
153+-----------------------------------------------------------------------+
154| **Answer**:                                                           |
155+-----------------------------------------------------------------------+
156| That would be because I spotted the need for that ``smp_mb()`` during |
157| the creation of this documentation, and it is therefore unlikely to   |
158| hit mainline before v4.14. Kudos to Lance Roy, Will Deacon, Peter     |
159| Zijlstra, and Jonathan Cameron for asking questions that sensitized   |
160| me to the rather elaborate sequence of events that demonstrate the    |
161| need for this memory barrier.                                         |
162+-----------------------------------------------------------------------+
163
164Tree RCU's grace--period memory-ordering guarantees rely most heavily on
165the ``rcu_node`` structure's ``->lock`` field, so much so that it is
166necessary to abbreviate this pattern in the diagrams in the next
167section. For example, consider the ``rcu_prepare_for_idle()`` function
168shown below, which is one of several functions that enforce ordering of
169newly arrived RCU callbacks against future grace periods:
170
171::
172
173    1 static void rcu_prepare_for_idle(void)
174    2 {
175    3   bool needwake;
176    4   struct rcu_data *rdp;
177    5   struct rcu_dynticks *rdtp = this_cpu_ptr(&rcu_dynticks);
178    6   struct rcu_node *rnp;
179    7   struct rcu_state *rsp;
180    8   int tne;
181    9
182   10   if (IS_ENABLED(CONFIG_RCU_NOCB_CPU_ALL) ||
183   11       rcu_is_nocb_cpu(smp_processor_id()))
184   12     return;
185   13   tne = READ_ONCE(tick_nohz_active);
186   14   if (tne != rdtp->tick_nohz_enabled_snap) {
187   15     if (rcu_cpu_has_callbacks(NULL))
188   16       invoke_rcu_core();
189   17     rdtp->tick_nohz_enabled_snap = tne;
190   18     return;
191   19   }
192   20   if (!tne)
193   21     return;
194   22   if (rdtp->all_lazy &&
195   23       rdtp->nonlazy_posted != rdtp->nonlazy_posted_snap) {
196   24     rdtp->all_lazy = false;
197   25     rdtp->nonlazy_posted_snap = rdtp->nonlazy_posted;
198   26     invoke_rcu_core();
199   27     return;
200   28   }
201   29   if (rdtp->last_accelerate == jiffies)
202   30     return;
203   31   rdtp->last_accelerate = jiffies;
204   32   for_each_rcu_flavor(rsp) {
205   33     rdp = this_cpu_ptr(rsp->rda);
206   34     if (rcu_segcblist_pend_cbs(&rdp->cblist))
207   35       continue;
208   36     rnp = rdp->mynode;
209   37     raw_spin_lock_rcu_node(rnp);
210   38     needwake = rcu_accelerate_cbs(rsp, rnp, rdp);
211   39     raw_spin_unlock_rcu_node(rnp);
212   40     if (needwake)
213   41       rcu_gp_kthread_wake(rsp);
214   42   }
215   43 }
216
217But the only part of ``rcu_prepare_for_idle()`` that really matters for
218this discussion are lines 37–39. We will therefore abbreviate this
219function as follows:
220
221.. kernel-figure:: rcu_node-lock.svg
222
223The box represents the ``rcu_node`` structure's ``->lock`` critical
224section, with the double line on top representing the additional
225``smp_mb__after_unlock_lock()``.
226
227Tree RCU Grace Period Memory Ordering Components
228~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
229
230Tree RCU's grace-period memory-ordering guarantee is provided by a
231number of RCU components:
232
233#. `Callback Registry`_
234#. `Grace-Period Initialization`_
235#. `Self-Reported Quiescent States`_
236#. `Dynamic Tick Interface`_
237#. `CPU-Hotplug Interface`_
238#. `Forcing Quiescent States`_
239#. `Grace-Period Cleanup`_
240#. `Callback Invocation`_
241
242Each of the following section looks at the corresponding component in
243detail.
244
245Callback Registry
246^^^^^^^^^^^^^^^^^
247
248If RCU's grace-period guarantee is to mean anything at all, any access
249that happens before a given invocation of ``call_rcu()`` must also
250happen before the corresponding grace period. The implementation of this
251portion of RCU's grace period guarantee is shown in the following
252figure:
253
254.. kernel-figure:: TreeRCU-callback-registry.svg
255
256Because ``call_rcu()`` normally acts only on CPU-local state, it
257provides no ordering guarantees, either for itself or for phase one of
258the update (which again will usually be removal of an element from an
259RCU-protected data structure). It simply enqueues the ``rcu_head``
260structure on a per-CPU list, which cannot become associated with a grace
261period until a later call to ``rcu_accelerate_cbs()``, as shown in the
262diagram above.
263
264One set of code paths shown on the left invokes ``rcu_accelerate_cbs()``
265via ``note_gp_changes()``, either directly from ``call_rcu()`` (if the
266current CPU is inundated with queued ``rcu_head`` structures) or more
267likely from an ``RCU_SOFTIRQ`` handler. Another code path in the middle
268is taken only in kernels built with ``CONFIG_RCU_FAST_NO_HZ=y``, which
269invokes ``rcu_accelerate_cbs()`` via ``rcu_prepare_for_idle()``. The
270final code path on the right is taken only in kernels built with
271``CONFIG_HOTPLUG_CPU=y``, which invokes ``rcu_accelerate_cbs()`` via
272``rcu_advance_cbs()``, ``rcu_migrate_callbacks``,
273``rcutree_migrate_callbacks()``, and ``takedown_cpu()``, which in turn
274is invoked on a surviving CPU after the outgoing CPU has been completely
275offlined.
276
277There are a few other code paths within grace-period processing that
278opportunistically invoke ``rcu_accelerate_cbs()``. However, either way,
279all of the CPU's recently queued ``rcu_head`` structures are associated
280with a future grace-period number under the protection of the CPU's lead
281``rcu_node`` structure's ``->lock``. In all cases, there is full
282ordering against any prior critical section for that same ``rcu_node``
283structure's ``->lock``, and also full ordering against any of the
284current task's or CPU's prior critical sections for any ``rcu_node``
285structure's ``->lock``.
286
287The next section will show how this ordering ensures that any accesses
288prior to the ``call_rcu()`` (particularly including phase one of the
289update) happen before the start of the corresponding grace period.
290
291+-----------------------------------------------------------------------+
292| **Quick Quiz**:                                                       |
293+-----------------------------------------------------------------------+
294| But what about ``synchronize_rcu()``?                                 |
295+-----------------------------------------------------------------------+
296| **Answer**:                                                           |
297+-----------------------------------------------------------------------+
298| The ``synchronize_rcu()`` passes ``call_rcu()`` to ``wait_rcu_gp()``, |
299| which invokes it. So either way, it eventually comes down to          |
300| ``call_rcu()``.                                                       |
301+-----------------------------------------------------------------------+
302
303Grace-Period Initialization
304^^^^^^^^^^^^^^^^^^^^^^^^^^^
305
306Grace-period initialization is carried out by the grace-period kernel
307thread, which makes several passes over the ``rcu_node`` tree within the
308``rcu_gp_init()`` function. This means that showing the full flow of
309ordering through the grace-period computation will require duplicating
310this tree. If you find this confusing, please note that the state of the
311``rcu_node`` changes over time, just like Heraclitus's river. However,
312to keep the ``rcu_node`` river tractable, the grace-period kernel
313thread's traversals are presented in multiple parts, starting in this
314section with the various phases of grace-period initialization.
315
316The first ordering-related grace-period initialization action is to
317advance the ``rcu_state`` structure's ``->gp_seq`` grace-period-number
318counter, as shown below:
319
320.. kernel-figure:: TreeRCU-gp-init-1.svg
321
322The actual increment is carried out using ``smp_store_release()``, which
323helps reject false-positive RCU CPU stall detection. Note that only the
324root ``rcu_node`` structure is touched.
325
326The first pass through the ``rcu_node`` tree updates bitmasks based on
327CPUs having come online or gone offline since the start of the previous
328grace period. In the common case where the number of online CPUs for
329this ``rcu_node`` structure has not transitioned to or from zero, this
330pass will scan only the leaf ``rcu_node`` structures. However, if the
331number of online CPUs for a given leaf ``rcu_node`` structure has
332transitioned from zero, ``rcu_init_new_rnp()`` will be invoked for the
333first incoming CPU. Similarly, if the number of online CPUs for a given
334leaf ``rcu_node`` structure has transitioned to zero,
335``rcu_cleanup_dead_rnp()`` will be invoked for the last outgoing CPU.
336The diagram below shows the path of ordering if the leftmost
337``rcu_node`` structure onlines its first CPU and if the next
338``rcu_node`` structure has no online CPUs (or, alternatively if the
339leftmost ``rcu_node`` structure offlines its last CPU and if the next
340``rcu_node`` structure has no online CPUs).
341
342.. kernel-figure:: TreeRCU-gp-init-2.svg
343
344The final ``rcu_gp_init()`` pass through the ``rcu_node`` tree traverses
345breadth-first, setting each ``rcu_node`` structure's ``->gp_seq`` field
346to the newly advanced value from the ``rcu_state`` structure, as shown
347in the following diagram.
348
349.. kernel-figure:: TreeRCU-gp-init-3.svg
350
351This change will also cause each CPU's next call to
352``__note_gp_changes()`` to notice that a new grace period has started,
353as described in the next section. But because the grace-period kthread
354started the grace period at the root (with the advancing of the
355``rcu_state`` structure's ``->gp_seq`` field) before setting each leaf
356``rcu_node`` structure's ``->gp_seq`` field, each CPU's observation of
357the start of the grace period will happen after the actual start of the
358grace period.
359
360+-----------------------------------------------------------------------+
361| **Quick Quiz**:                                                       |
362+-----------------------------------------------------------------------+
363| But what about the CPU that started the grace period? Why wouldn't it |
364| see the start of the grace period right when it started that grace    |
365| period?                                                               |
366+-----------------------------------------------------------------------+
367| **Answer**:                                                           |
368+-----------------------------------------------------------------------+
369| In some deep philosophical and overly anthromorphized sense, yes, the |
370| CPU starting the grace period is immediately aware of having done so. |
371| However, if we instead assume that RCU is not self-aware, then even   |
372| the CPU starting the grace period does not really become aware of the |
373| start of this grace period until its first call to                    |
374| ``__note_gp_changes()``. On the other hand, this CPU potentially gets |
375| early notification because it invokes ``__note_gp_changes()`` during  |
376| its last ``rcu_gp_init()`` pass through its leaf ``rcu_node``         |
377| structure.                                                            |
378+-----------------------------------------------------------------------+
379
380Self-Reported Quiescent States
381^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
382
383When all entities that might block the grace period have reported
384quiescent states (or as described in a later section, had quiescent
385states reported on their behalf), the grace period can end. Online
386non-idle CPUs report their own quiescent states, as shown in the
387following diagram:
388
389.. kernel-figure:: TreeRCU-qs.svg
390
391This is for the last CPU to report a quiescent state, which signals the
392end of the grace period. Earlier quiescent states would push up the
393``rcu_node`` tree only until they encountered an ``rcu_node`` structure
394that is waiting for additional quiescent states. However, ordering is
395nevertheless preserved because some later quiescent state will acquire
396that ``rcu_node`` structure's ``->lock``.
397
398Any number of events can lead up to a CPU invoking ``note_gp_changes``
399(or alternatively, directly invoking ``__note_gp_changes()``), at which
400point that CPU will notice the start of a new grace period while holding
401its leaf ``rcu_node`` lock. Therefore, all execution shown in this
402diagram happens after the start of the grace period. In addition, this
403CPU will consider any RCU read-side critical section that started before
404the invocation of ``__note_gp_changes()`` to have started before the
405grace period, and thus a critical section that the grace period must
406wait on.
407
408+-----------------------------------------------------------------------+
409| **Quick Quiz**:                                                       |
410+-----------------------------------------------------------------------+
411| But a RCU read-side critical section might have started after the     |
412| beginning of the grace period (the advancing of ``->gp_seq`` from     |
413| earlier), so why should the grace period wait on such a critical      |
414| section?                                                              |
415+-----------------------------------------------------------------------+
416| **Answer**:                                                           |
417+-----------------------------------------------------------------------+
418| It is indeed not necessary for the grace period to wait on such a     |
419| critical section. However, it is permissible to wait on it. And it is |
420| furthermore important to wait on it, as this lazy approach is far     |
421| more scalable than a “big bang” all-at-once grace-period start could  |
422| possibly be.                                                          |
423+-----------------------------------------------------------------------+
424
425If the CPU does a context switch, a quiescent state will be noted by
426``rcu_note_context_switch()`` on the left. On the other hand, if the CPU
427takes a scheduler-clock interrupt while executing in usermode, a
428quiescent state will be noted by ``rcu_sched_clock_irq()`` on the right.
429Either way, the passage through a quiescent state will be noted in a
430per-CPU variable.
431
432The next time an ``RCU_SOFTIRQ`` handler executes on this CPU (for
433example, after the next scheduler-clock interrupt), ``rcu_core()`` will
434invoke ``rcu_check_quiescent_state()``, which will notice the recorded
435quiescent state, and invoke ``rcu_report_qs_rdp()``. If
436``rcu_report_qs_rdp()`` verifies that the quiescent state really does
437apply to the current grace period, it invokes ``rcu_report_rnp()`` which
438traverses up the ``rcu_node`` tree as shown at the bottom of the
439diagram, clearing bits from each ``rcu_node`` structure's ``->qsmask``
440field, and propagating up the tree when the result is zero.
441
442Note that traversal passes upwards out of a given ``rcu_node`` structure
443only if the current CPU is reporting the last quiescent state for the
444subtree headed by that ``rcu_node`` structure. A key point is that if a
445CPU's traversal stops at a given ``rcu_node`` structure, then there will
446be a later traversal by another CPU (or perhaps the same one) that
447proceeds upwards from that point, and the ``rcu_node`` ``->lock``
448guarantees that the first CPU's quiescent state happens before the
449remainder of the second CPU's traversal. Applying this line of thought
450repeatedly shows that all CPUs' quiescent states happen before the last
451CPU traverses through the root ``rcu_node`` structure, the “last CPU”
452being the one that clears the last bit in the root ``rcu_node``
453structure's ``->qsmask`` field.
454
455Dynamic Tick Interface
456^^^^^^^^^^^^^^^^^^^^^^
457
458Due to energy-efficiency considerations, RCU is forbidden from
459disturbing idle CPUs. CPUs are therefore required to notify RCU when
460entering or leaving idle state, which they do via fully ordered
461value-returning atomic operations on a per-CPU variable. The ordering
462effects are as shown below:
463
464.. kernel-figure:: TreeRCU-dyntick.svg
465
466The RCU grace-period kernel thread samples the per-CPU idleness variable
467while holding the corresponding CPU's leaf ``rcu_node`` structure's
468``->lock``. This means that any RCU read-side critical sections that
469precede the idle period (the oval near the top of the diagram above)
470will happen before the end of the current grace period. Similarly, the
471beginning of the current grace period will happen before any RCU
472read-side critical sections that follow the idle period (the oval near
473the bottom of the diagram above).
474
475Plumbing this into the full grace-period execution is described
476`below <Forcing Quiescent States_>`__.
477
478CPU-Hotplug Interface
479^^^^^^^^^^^^^^^^^^^^^
480
481RCU is also forbidden from disturbing offline CPUs, which might well be
482powered off and removed from the system completely. CPUs are therefore
483required to notify RCU of their comings and goings as part of the
484corresponding CPU hotplug operations. The ordering effects are shown
485below:
486
487.. kernel-figure:: TreeRCU-hotplug.svg
488
489Because CPU hotplug operations are much less frequent than idle
490transitions, they are heavier weight, and thus acquire the CPU's leaf
491``rcu_node`` structure's ``->lock`` and update this structure's
492``->qsmaskinitnext``. The RCU grace-period kernel thread samples this
493mask to detect CPUs having gone offline since the beginning of this
494grace period.
495
496Plumbing this into the full grace-period execution is described
497`below <Forcing Quiescent States_>`__.
498
499Forcing Quiescent States
500^^^^^^^^^^^^^^^^^^^^^^^^
501
502As noted above, idle and offline CPUs cannot report their own quiescent
503states, and therefore the grace-period kernel thread must do the
504reporting on their behalf. This process is called “forcing quiescent
505states”, it is repeated every few jiffies, and its ordering effects are
506shown below:
507
508.. kernel-figure:: TreeRCU-gp-fqs.svg
509
510Each pass of quiescent state forcing is guaranteed to traverse the leaf
511``rcu_node`` structures, and if there are no new quiescent states due to
512recently idled and/or offlined CPUs, then only the leaves are traversed.
513However, if there is a newly offlined CPU as illustrated on the left or
514a newly idled CPU as illustrated on the right, the corresponding
515quiescent state will be driven up towards the root. As with
516self-reported quiescent states, the upwards driving stops once it
517reaches an ``rcu_node`` structure that has quiescent states outstanding
518from other CPUs.
519
520+-----------------------------------------------------------------------+
521| **Quick Quiz**:                                                       |
522+-----------------------------------------------------------------------+
523| The leftmost drive to root stopped before it reached the root         |
524| ``rcu_node`` structure, which means that there are still CPUs         |
525| subordinate to that structure on which the current grace period is    |
526| waiting. Given that, how is it possible that the rightmost drive to   |
527| root ended the grace period?                                          |
528+-----------------------------------------------------------------------+
529| **Answer**:                                                           |
530+-----------------------------------------------------------------------+
531| Good analysis! It is in fact impossible in the absence of bugs in     |
532| RCU. But this diagram is complex enough as it is, so simplicity       |
533| overrode accuracy. You can think of it as poetic license, or you can  |
534| think of it as misdirection that is resolved in the                   |
535| `stitched-together diagram <Putting It All Together_>`__.             |
536+-----------------------------------------------------------------------+
537
538Grace-Period Cleanup
539^^^^^^^^^^^^^^^^^^^^
540
541Grace-period cleanup first scans the ``rcu_node`` tree breadth-first
542advancing all the ``->gp_seq`` fields, then it advances the
543``rcu_state`` structure's ``->gp_seq`` field. The ordering effects are
544shown below:
545
546.. kernel-figure:: TreeRCU-gp-cleanup.svg
547
548As indicated by the oval at the bottom of the diagram, once grace-period
549cleanup is complete, the next grace period can begin.
550
551+-----------------------------------------------------------------------+
552| **Quick Quiz**:                                                       |
553+-----------------------------------------------------------------------+
554| But when precisely does the grace period end?                         |
555+-----------------------------------------------------------------------+
556| **Answer**:                                                           |
557+-----------------------------------------------------------------------+
558| There is no useful single point at which the grace period can be said |
559| to end. The earliest reasonable candidate is as soon as the last CPU  |
560| has reported its quiescent state, but it may be some milliseconds     |
561| before RCU becomes aware of this. The latest reasonable candidate is  |
562| once the ``rcu_state`` structure's ``->gp_seq`` field has been        |
563| updated, but it is quite possible that some CPUs have already         |
564| completed phase two of their updates by that time. In short, if you   |
565| are going to work with RCU, you need to learn to embrace uncertainty. |
566+-----------------------------------------------------------------------+
567
568Callback Invocation
569^^^^^^^^^^^^^^^^^^^
570
571Once a given CPU's leaf ``rcu_node`` structure's ``->gp_seq`` field has
572been updated, that CPU can begin invoking its RCU callbacks that were
573waiting for this grace period to end. These callbacks are identified by
574``rcu_advance_cbs()``, which is usually invoked by
575``__note_gp_changes()``. As shown in the diagram below, this invocation
576can be triggered by the scheduling-clock interrupt
577(``rcu_sched_clock_irq()`` on the left) or by idle entry
578(``rcu_cleanup_after_idle()`` on the right, but only for kernels build
579with ``CONFIG_RCU_FAST_NO_HZ=y``). Either way, ``RCU_SOFTIRQ`` is
580raised, which results in ``rcu_do_batch()`` invoking the callbacks,
581which in turn allows those callbacks to carry out (either directly or
582indirectly via wakeup) the needed phase-two processing for each update.
583
584.. kernel-figure:: TreeRCU-callback-invocation.svg
585
586Please note that callback invocation can also be prompted by any number
587of corner-case code paths, for example, when a CPU notes that it has
588excessive numbers of callbacks queued. In all cases, the CPU acquires
589its leaf ``rcu_node`` structure's ``->lock`` before invoking callbacks,
590which preserves the required ordering against the newly completed grace
591period.
592
593However, if the callback function communicates to other CPUs, for
594example, doing a wakeup, then it is that function's responsibility to
595maintain ordering. For example, if the callback function wakes up a task
596that runs on some other CPU, proper ordering must in place in both the
597callback function and the task being awakened. To see why this is
598important, consider the top half of the `grace-period
599cleanup`_ diagram. The callback might be
600running on a CPU corresponding to the leftmost leaf ``rcu_node``
601structure, and awaken a task that is to run on a CPU corresponding to
602the rightmost leaf ``rcu_node`` structure, and the grace-period kernel
603thread might not yet have reached the rightmost leaf. In this case, the
604grace period's memory ordering might not yet have reached that CPU, so
605again the callback function and the awakened task must supply proper
606ordering.
607
608Putting It All Together
609~~~~~~~~~~~~~~~~~~~~~~~
610
611A stitched-together diagram is here:
612
613.. kernel-figure:: TreeRCU-gp.svg
614
615Legal Statement
616~~~~~~~~~~~~~~~
617
618This work represents the view of the author and does not necessarily
619represent the view of IBM.
620
621Linux is a registered trademark of Linus Torvalds.
622
623Other company, product, and service names may be trademarks or service
624marks of others.
625