Lines Matching +full:half +full:- +full:period
2 A Tour Through TREE_RCU's Grace-Period Memory Ordering
13 grace-period memory ordering guarantee is provided.
15 What Is Tree RCU's Grace Period Memory Ordering Guarantee?
18 RCU grace periods provide extremely strong memory-ordering guarantees
19 for non-idle non-offline code.
20 Any code that happens after the end of a given RCU grace period is guaranteed
22 period that are within RCU read-side critical sections.
24 period is guaranteed to not see the effects of all accesses following the end
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
34 two phases, one of which is executed before the grace period and
35 the other of which is executed after the grace period.
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
46 Tree RCU Grace Period Memory Ordering Building Blocks
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
74 period, including any CPUs that came online or went offline during
75 the grace period in question.
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 ``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 +-----------------------------------------------------------------------+
159 | But what about CPUs that remain offline for the entire grace period? |
160 +-----------------------------------------------------------------------+
162 +-----------------------------------------------------------------------+
163 | Such CPUs will be offline at the beginning of the grace period, so |
164 | the grace period won't expect quiescent states from them. Races |
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 +-----------------------------------------------------------------------+
172 a CPU that is not yet aware that the grace period has ended, and thus
173 might not yet be subject to the grace period's memory ordering.
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
251 Tree RCU Grace Period Memory Ordering Components
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
274 happen before the corresponding grace period. The implementation of this
275 portion of RCU's grace period guarantee is shown in the following
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
285 period until a later call to ``rcu_accelerate_cbs()``, as shown in the
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``.
313 update) happen before the start of the corresponding grace period.
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
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
352 grace period. In the common case where the number of online CPUs for
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
376 ``__note_gp_changes()`` to notice that a new grace period has started,
377 as described in the next section. But because the grace-period kthread
378 started the grace period at the root (with the advancing of the
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
381 the start of the grace period will happen after the actual start of the
382 grace period.
384 +-----------------------------------------------------------------------+
386 +-----------------------------------------------------------------------+
387 | But what about the CPU that started the grace period? Why wouldn't it |
388 | see the start of the grace period right when it started that grace |
389 | period? |
390 +-----------------------------------------------------------------------+
392 +-----------------------------------------------------------------------+
394 | CPU starting the grace period is immediately aware of having done so. |
395 | However, if we instead assume that RCU is not self-aware, then even |
396 | the CPU starting the grace period does not really become aware of the |
397 | start of this grace period until its first call to |
402 +-----------------------------------------------------------------------+
404 Self-Reported Quiescent States
407 When all entities that might block the grace period have reported
409 states reported on their behalf), the grace period can end. Online
410 non-idle CPUs report their own quiescent states, as shown in the
413 .. kernel-figure:: TreeRCU-qs.svg
416 end of the grace period. Earlier quiescent states would push up the
420 that ``rcu_node`` structure's ``->lock``.
424 point that CPU will notice the start of a new grace period while holding
426 diagram happens after the start of the grace period. In addition, this
427 CPU will consider any RCU read-side critical section that started before
429 grace period, and thus a critical section that the grace period must
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 |
437 | earlier), so why should the grace period wait on such a critical |
439 +-----------------------------------------------------------------------+
441 +-----------------------------------------------------------------------+
442 | It is indeed not necessary for the grace period to wait on such a |
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.
457 example, after the next scheduler-clock interrupt), ``rcu_core()`` will
461 apply to the current grace period, it invokes ``rcu_report_rnp()`` which
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
493 precede the idle period (the oval near the top of the diagram above)
494 will happen before the end of the current grace period. Similarly, the
495 beginning of the current grace period will happen before any RCU
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
518 grace period.
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 +-----------------------------------------------------------------------+
549 | subordinate to that structure on which the current grace period is |
551 | root ended the grace period? |
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
573 cleanup is complete, the next grace period can begin.
575 +-----------------------------------------------------------------------+
577 +-----------------------------------------------------------------------+
578 | But when precisely does the grace period end? |
579 +-----------------------------------------------------------------------+
581 +-----------------------------------------------------------------------+
582 | There is no useful single point at which the grace period can be said |
586 | once the ``rcu_state`` structure's ``->gp_seq`` field has been |
590 +-----------------------------------------------------------------------+
595 Once a given CPU's leaf ``rcu_node`` structure's ``->gp_seq`` field has
597 waiting for this grace period to end. These callbacks are identified by
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,
615 period.
622 important, consider the top half of the `grace-period
626 the rightmost leaf ``rcu_node`` structure, and the grace-period kernel
628 grace period's memory ordering might not yet have reached that CPU, so
635 A stitched-together diagram is here:
637 .. kernel-figure:: TreeRCU-gp.svg