Lines Matching +full:double +full:- +full:phase
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
36 In the most common use case, phase one removes an element from
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
54 Their lock-release counterparts are ``raw_spin_unlock_rcu_node()``,
58 The key point is that the lock-acquisition functions, including
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::
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 ``rcu_dynticks_eqs_enter()`` at idle-entry
151 time and within ``rcu_dynticks_eqs_exit()`` at idle-exit time.
152 The grace-period kthread invokes ``rcu_dynticks_snap()`` and
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 != rdtp->tick_nohz_enabled_snap) {
218 17 rdtp->tick_nohz_enabled_snap = tne;
223 22 if (rdtp->all_lazy &&
224 23 rdtp->nonlazy_posted != rdtp->nonlazy_posted_snap) {
225 24 rdtp->all_lazy = false;
226 25 rdtp->nonlazy_posted_snap = rdtp->nonlazy_posted;
230 29 if (rdtp->last_accelerate == jiffies)
232 31 rdtp->last_accelerate = jiffies;
234 33 rdp = this_cpu_ptr(rsp->rda);
235 34 if (rcu_segcblist_pend_cbs(&rdp->cblist))
237 36 rnp = rdp->mynode;
250 .. kernel-figure:: rcu_node-lock.svg
252 The box represents the ``rcu_node`` structure's ``->lock`` critical
253 section, with the double line on top representing the additional
259 Tree RCU's grace-period memory-ordering guarantee is provided by a
263 #. `Grace-Period Initialization`_
264 #. `Self-Reported Quiescent States`_
266 #. `CPU-Hotplug Interface`_
268 #. `Grace-Period Cleanup`_
277 If RCU's grace-period guarantee is to mean anything at all, any access
283 .. kernel-figure:: TreeRCU-callback-registry.svg
285 Because ``call_rcu()`` normally acts only on CPU-local state, it
286 provides no ordering guarantees, either for itself or for phase one of
288 RCU-protected data structure). It simply enqueues the ``rcu_head``
289 structure on a per-CPU list, which cannot become associated with a grace
306 There are a few other code paths within grace-period processing that
309 with a future grace-period number under the protection of the CPU's lead
310 ``rcu_node`` structure's ``->lock``. In all cases, there is full
312 structure's ``->lock``, and also full ordering against any of the
314 structure's ``->lock``.
317 prior to the ``call_rcu()`` (particularly including phase one of the
320 +-----------------------------------------------------------------------+
322 +-----------------------------------------------------------------------+
324 +-----------------------------------------------------------------------+
326 +-----------------------------------------------------------------------+
330 +-----------------------------------------------------------------------+
332 Grace-Period Initialization
335 Grace-period initialization is carried out by the grace-period kernel
338 ordering through the grace-period computation will require duplicating
341 to keep the ``rcu_node`` river tractable, the grace-period kernel
343 section with the various phases of grace-period initialization.
345 The first ordering-related grace-period initialization action is to
346 advance the ``rcu_state`` structure's ``->gp_seq`` grace-period-number
349 .. kernel-figure:: TreeRCU-gp-init-1.svg
352 helps reject false-positive RCU CPU stall detection. Note that only the
371 .. kernel-figure:: TreeRCU-gp-init-2.svg
374 breadth-first, setting each ``rcu_node`` structure's ``->gp_seq`` field
378 .. kernel-figure:: TreeRCU-gp-init-3.svg
382 as described in the next section. But because the grace-period kthread
384 ``rcu_state`` structure's ``->gp_seq`` field) before setting each leaf
385 ``rcu_node`` structure's ``->gp_seq`` field, each CPU's observation of
389 +-----------------------------------------------------------------------+
391 +-----------------------------------------------------------------------+
395 +-----------------------------------------------------------------------+
397 +-----------------------------------------------------------------------+
400 | However, if we instead assume that RCU is not self-aware, then even |
407 +-----------------------------------------------------------------------+
409 Self-Reported Quiescent States
415 non-idle CPUs report their own quiescent states, as shown in the
418 .. kernel-figure:: TreeRCU-qs.svg
425 that ``rcu_node`` structure's ``->lock``.
432 CPU will consider any RCU read-side critical section that started before
437 +-----------------------------------------------------------------------+
439 +-----------------------------------------------------------------------+
440 | But a RCU read-side critical section might have started after the |
441 | beginning of the grace period (the advancing of ``->gp_seq`` from |
444 +-----------------------------------------------------------------------+
446 +-----------------------------------------------------------------------+
450 | more scalable than a “big bang” all-at-once grace-period start could |
452 +-----------------------------------------------------------------------+
456 takes a scheduler-clock interrupt while executing in usermode, a
459 per-CPU variable.
462 example, after the next scheduler-clock interrupt), ``rcu_core()`` will
468 diagram, clearing bits from each ``rcu_node`` structure's ``->qsmask``
476 proceeds upwards from that point, and the ``rcu_node`` ``->lock``
482 structure's ``->qsmask`` field.
487 Due to energy-efficiency considerations, RCU is forbidden from
490 value-returning atomic operations on a per-CPU variable. The ordering
493 .. kernel-figure:: TreeRCU-dyntick.svg
495 The RCU grace-period kernel thread samples the per-CPU idleness variable
497 ``->lock``. This means that any RCU read-side critical sections that
501 read-side critical sections that follow the idle period (the oval near
504 Plumbing this into the full grace-period execution is described
507 CPU-Hotplug Interface
516 .. kernel-figure:: TreeRCU-hotplug.svg
520 ``rcu_node`` structure's ``->lock`` and update this structure's
521 ``->qsmaskinitnext``. The RCU grace-period kernel thread samples this
525 Plumbing this into the full grace-period execution is described
532 states, and therefore the grace-period kernel thread must do the
537 .. kernel-figure:: TreeRCU-gp-fqs.svg
545 self-reported quiescent states, the upwards driving stops once it
549 +-----------------------------------------------------------------------+
551 +-----------------------------------------------------------------------+
557 +-----------------------------------------------------------------------+
559 +-----------------------------------------------------------------------+
564 | `stitched-together diagram <Putting It All Together_>`__. |
565 +-----------------------------------------------------------------------+
567 Grace-Period Cleanup
570 Grace-period cleanup first scans the ``rcu_node`` tree breadth-first
571 advancing all the ``->gp_seq`` fields, then it advances the
572 ``rcu_state`` structure's ``->gp_seq`` field. The ordering effects are
575 .. kernel-figure:: TreeRCU-gp-cleanup.svg
577 As indicated by the oval at the bottom of the diagram, once grace-period
580 +-----------------------------------------------------------------------+
582 +-----------------------------------------------------------------------+
584 +-----------------------------------------------------------------------+
586 +-----------------------------------------------------------------------+
591 | once the ``rcu_state`` structure's ``->gp_seq`` field has been |
593 | completed phase two of their updates by that time. In short, if you |
595 +-----------------------------------------------------------------------+
600 Once a given CPU's leaf ``rcu_node`` structure's ``->gp_seq`` field has
605 can be triggered by the scheduling-clock interrupt
611 indirectly via wakeup) the needed phase-two processing for each update.
613 .. kernel-figure:: TreeRCU-callback-invocation.svg
616 of corner-case code paths, for example, when a CPU notes that it has
618 its leaf ``rcu_node`` structure's ``->lock`` before invoking callbacks,
627 important, consider the top half of the `grace-period
631 the rightmost leaf ``rcu_node`` structure, and the grace-period kernel
640 A stitched-together diagram is here:
642 .. kernel-figure:: TreeRCU-gp.svg