Design/Memory-Ordering/Tree-RCU-Memory-Ordering.rst

2 A Tour Through TREE_RCU's Grace-Period Memory Ordering
13 grace-period memory ordering guarantee is provided.
18 RCU grace periods provide extremely strong memory-ordering guarantees
19 for non-idle non-offline code.
22 period that are within RCU read-side critical sections.
25 of that grace period that are within RCU read-side critical sections.
27 Note well that RCU-sched read-side critical sections include any region
30 an extremely small region of preemption-disabled code, one can think of
37 a linked RCU-protected data structure, and phase two frees that element.
39 phase-one update (in the common case, removal) must not witness state
40 following the phase-two update (in the common case, freeing).
43 of lock-based critical sections, memory barriers, and per-CPU
49 The workhorse for RCU's grace-period memory ordering is the
51 ``->lock``. These critical sections use helper functions for lock
52 acquisition, including ``raw_spin_lock_rcu_node()``,
54 Their lock-release counterparts are ``raw_spin_unlock_rcu_node()``,
58 The key point is that the lock-acquisition functions, including
60 immediately after successful acquisition of the lock.
63 happening before one of the above lock-release functions will be seen
65 one of the above lock-acquisition functions.
67 above lock-release function on any given CPU will be seen by all
69 of the above lock-acquisition functions executing on that same CPU,
70 even if the lock-release and lock-acquisition functions are operating
78 lock-acquisition and lock-release functions::
107 The ``WARN_ON()`` is evaluated at "the end of time",
110 acquisition functions, this ``WARN_ON()`` could trigger, for example
115 +-----------------------------------------------------------------------+
117 +-----------------------------------------------------------------------+
118 | But the chain of rcu_node-structure lock acquisitions guarantees      |
119 | that new readers will see all of the updater's pre-grace-period       |
120 | accesses and also guarantees that the updater's post-grace-period     |
123 +-----------------------------------------------------------------------+
125 +-----------------------------------------------------------------------+
126 | Because we must provide ordering for RCU's polling grace-period       |
131 |  ----                                      ----                       |
142 +-----------------------------------------------------------------------+
145 RCU's grace-period memory ordering guarantee to extend to any
146 RCU read-side critical sections preceding and following the current
149 ``atomic_add_return()`` read-modify-write atomic operation that
150 is invoked within ``ct_kernel_exit_state()`` at idle-entry
151 time and within ``ct_kernel_enter_state()`` at idle-exit time.
152 The grace-period kthread invokes first ``ct_rcu_watching_cpu_acquire()``
156 +-----------------------------------------------------------------------+
158 +-----------------------------------------------------------------------+
160 +-----------------------------------------------------------------------+
162 +-----------------------------------------------------------------------+
165 | between grace-period start and CPU-hotplug operations are mediated    |
166 | by the CPU's leaf ``rcu_node`` structure's ``->lock`` as described    |
168 +-----------------------------------------------------------------------+
177 +-----------------------------------------------------------------------+
179 +-----------------------------------------------------------------------+
182 +-----------------------------------------------------------------------+
184 +-----------------------------------------------------------------------+
191 +-----------------------------------------------------------------------+
193 Tree RCU's grace--period memory-ordering guarantees rely most heavily on
194 the ``rcu_node`` structure's ``->lock`` field, so much so that it is
215    14   if (tne != rdp->tick_nohz_enabled_snap) {
216    15     if (!rcu_segcblist_empty(&rdp->cblist))
218    17     rdp->tick_nohz_enabled_snap = tne;
228    27   if (rdp->last_accelerate == jiffies)
230    29   rdp->last_accelerate = jiffies;
231    30   if (rcu_segcblist_pend_cbs(&rdp->cblist)) {
232    31     rnp = rdp->mynode;
245 .. kernel-figure:: rcu_node-lock.svg
247 The box represents the ``rcu_node`` structure's ``->lock`` critical
254 Tree RCU's grace-period memory-ordering guarantee is provided by a
258 #. `Grace-Period Initialization`_
259 #. `Self-Reported Quiescent States`_
261 #. `CPU-Hotplug Interface`_
263 #. `Grace-Period Cleanup`_
272 If RCU's grace-period guarantee is to mean anything at all, any access
278 .. kernel-figure:: TreeRCU-callback-registry.svg
280 Because ``call_rcu()`` normally acts only on CPU-local state, it
283 RCU-protected data structure). It simply enqueues the ``rcu_head``
284 structure on a per-CPU list, which cannot become associated with a grace
301 There are a few other code paths within grace-period processing that
304 with a future grace-period number under the protection of the CPU's lead
305 ``rcu_node`` structure's ``->lock``. In all cases, there is full
307 structure's ``->lock``, and also full ordering against any of the
309 structure's ``->lock``.
315 +-----------------------------------------------------------------------+
317 +-----------------------------------------------------------------------+
319 +-----------------------------------------------------------------------+
321 +-----------------------------------------------------------------------+
325 +-----------------------------------------------------------------------+
327 Grace-Period Initialization
330 Grace-period initialization is carried out by the grace-period kernel
333 ordering through the grace-period computation will require duplicating
335 ``rcu_node`` changes over time, just like Heraclitus's river. However,
336 to keep the ``rcu_node`` river tractable, the grace-period kernel
338 section with the various phases of grace-period initialization.
340 The first ordering-related grace-period initialization action is to
341 advance the ``rcu_state`` structure's ``->gp_seq`` grace-period-number
344 .. kernel-figure:: TreeRCU-gp-init-1.svg
347 helps reject false-positive RCU CPU stall detection. Note that only the
366 .. kernel-figure:: TreeRCU-gp-init-2.svg
369 breadth-first, setting each ``rcu_node`` structure's ``->gp_seq`` field
373 .. kernel-figure:: TreeRCU-gp-init-3.svg
377 as described in the next section. But because the grace-period kthread
379 ``rcu_state`` structure's ``->gp_seq`` field) before setting each leaf
380 ``rcu_node`` structure's ``->gp_seq`` field, each CPU's observation of
384 +-----------------------------------------------------------------------+
386 +-----------------------------------------------------------------------+
390 +-----------------------------------------------------------------------+
392 +-----------------------------------------------------------------------+
395 | However, if we instead assume that RCU is not self-aware, then even   |
402 +-----------------------------------------------------------------------+
404 Self-Reported Quiescent States
410 non-idle CPUs report their own quiescent states, as shown in the
413 .. kernel-figure:: TreeRCU-qs.svg
420 that ``rcu_node`` structure's ``->lock``.
427 CPU will consider any RCU read-side critical section that started before
432 +-----------------------------------------------------------------------+
434 +-----------------------------------------------------------------------+
435 | But a RCU read-side critical section might have started after the     |
436 | beginning of the grace period (the advancing of ``->gp_seq`` from     |
439 +-----------------------------------------------------------------------+
441 +-----------------------------------------------------------------------+
445 | more scalable than a “big bang” all-at-once grace-period start could  |
447 +-----------------------------------------------------------------------+
451 takes a scheduler-clock interrupt while executing in usermode, a
454 per-CPU variable.
456 The next time an ``RCU_SOFTIRQ`` handler executes on this CPU (for
457 example, after the next scheduler-clock interrupt), ``rcu_core()`` will
463 diagram, clearing bits from each ``rcu_node`` structure's ``->qsmask``
471 proceeds upwards from that point, and the ``rcu_node`` ``->lock``
477 structure's ``->qsmask`` field.
482 Due to energy-efficiency considerations, RCU is forbidden from
485 value-returning atomic operations on a per-CPU variable. The ordering
488 .. kernel-figure:: TreeRCU-dyntick.svg
490 The RCU grace-period kernel thread samples the per-CPU idleness variable
492 ``->lock``. This means that any RCU read-side critical sections that
496 read-side critical sections that follow the idle period (the oval near
499 Plumbing this into the full grace-period execution is described
502 CPU-Hotplug Interface
511 .. kernel-figure:: TreeRCU-hotplug.svg
515 ``rcu_node`` structure's ``->lock`` and update this structure's
516 ``->qsmaskinitnext``. The RCU grace-period kernel thread samples this
520 Plumbing this into the full grace-period execution is described
527 states, and therefore the grace-period kernel thread must do the
532 .. kernel-figure:: TreeRCU-gp-fqs.svg
540 self-reported quiescent states, the upwards driving stops once it
544 +-----------------------------------------------------------------------+
546 +-----------------------------------------------------------------------+
552 +-----------------------------------------------------------------------+
554 +-----------------------------------------------------------------------+
559 | `stitched-together diagram <Putting It All Together_>`__.             |
560 +-----------------------------------------------------------------------+
562 Grace-Period Cleanup
565 Grace-period cleanup first scans the ``rcu_node`` tree breadth-first
566 advancing all the ``->gp_seq`` fields, then it advances the
567 ``rcu_state`` structure's ``->gp_seq`` field. The ordering effects are
570 .. kernel-figure:: TreeRCU-gp-cleanup.svg
572 As indicated by the oval at the bottom of the diagram, once grace-period
575 +-----------------------------------------------------------------------+
577 +-----------------------------------------------------------------------+
579 +-----------------------------------------------------------------------+
581 +-----------------------------------------------------------------------+
586 | once the ``rcu_state`` structure's ``->gp_seq`` field has been        |
588 | completed phase two of their updates by that time. In short, if you   |
590 +-----------------------------------------------------------------------+
595 Once a given CPU's leaf ``rcu_node`` structure's ``->gp_seq`` field has
600 can be triggered by the scheduling-clock interrupt
606 indirectly via wakeup) the needed phase-two processing for each update.
608 .. kernel-figure:: TreeRCU-callback-invocation.svg
611 of corner-case code paths, for example, when a CPU notes that it has
613 its leaf ``rcu_node`` structure's ``->lock`` before invoking callbacks,
622 important, consider the top half of the `grace-period
626 the rightmost leaf ``rcu_node`` structure, and the grace-period kernel
635 A stitched-together diagram is here:
637 .. kernel-figure:: TreeRCU-gp.svg