cachepc-linux

Fork of AMDESE/linux with modifications for CachePC side-channel attack
git clone https://git.sinitax.com/sinitax/cachepc-linux
Log | Files | Refs | README | LICENSE | sfeed.txt

Expedited-Grace-Periods.rst (27475B)


      1=================================================
      2A Tour Through TREE_RCU's Expedited Grace Periods
      3=================================================
      4
      5Introduction
      6============
      7
      8This document describes RCU's expedited grace periods.
      9Unlike RCU's normal grace periods, which accept long latencies to attain
     10high efficiency and minimal disturbance, expedited grace periods accept
     11lower efficiency and significant disturbance to attain shorter latencies.
     12
     13There are two flavors of RCU (RCU-preempt and RCU-sched), with an earlier
     14third RCU-bh flavor having been implemented in terms of the other two.
     15Each of the two implementations is covered in its own section.
     16
     17Expedited Grace Period Design
     18=============================
     19
     20The expedited RCU grace periods cannot be accused of being subtle,
     21given that they for all intents and purposes hammer every CPU that
     22has not yet provided a quiescent state for the current expedited
     23grace period.
     24The one saving grace is that the hammer has grown a bit smaller
     25over time:  The old call to ``try_stop_cpus()`` has been
     26replaced with a set of calls to ``smp_call_function_single()``,
     27each of which results in an IPI to the target CPU.
     28The corresponding handler function checks the CPU's state, motivating
     29a faster quiescent state where possible, and triggering a report
     30of that quiescent state.
     31As always for RCU, once everything has spent some time in a quiescent
     32state, the expedited grace period has completed.
     33
     34The details of the ``smp_call_function_single()`` handler's
     35operation depend on the RCU flavor, as described in the following
     36sections.
     37
     38RCU-preempt Expedited Grace Periods
     39===================================
     40
     41``CONFIG_PREEMPTION=y`` kernels implement RCU-preempt.
     42The overall flow of the handling of a given CPU by an RCU-preempt
     43expedited grace period is shown in the following diagram:
     44
     45.. kernel-figure:: ExpRCUFlow.svg
     46
     47The solid arrows denote direct action, for example, a function call.
     48The dotted arrows denote indirect action, for example, an IPI
     49or a state that is reached after some time.
     50
     51If a given CPU is offline or idle, ``synchronize_rcu_expedited()``
     52will ignore it because idle and offline CPUs are already residing
     53in quiescent states.
     54Otherwise, the expedited grace period will use
     55``smp_call_function_single()`` to send the CPU an IPI, which
     56is handled by ``rcu_exp_handler()``.
     57
     58However, because this is preemptible RCU, ``rcu_exp_handler()``
     59can check to see if the CPU is currently running in an RCU read-side
     60critical section.
     61If not, the handler can immediately report a quiescent state.
     62Otherwise, it sets flags so that the outermost ``rcu_read_unlock()``
     63invocation will provide the needed quiescent-state report.
     64This flag-setting avoids the previous forced preemption of all
     65CPUs that might have RCU read-side critical sections.
     66In addition, this flag-setting is done so as to avoid increasing
     67the overhead of the common-case fastpath through the scheduler.
     68
     69Again because this is preemptible RCU, an RCU read-side critical section
     70can be preempted.
     71When that happens, RCU will enqueue the task, which will the continue to
     72block the current expedited grace period until it resumes and finds its
     73outermost ``rcu_read_unlock()``.
     74The CPU will report a quiescent state just after enqueuing the task because
     75the CPU is no longer blocking the grace period.
     76It is instead the preempted task doing the blocking.
     77The list of blocked tasks is managed by ``rcu_preempt_ctxt_queue()``,
     78which is called from ``rcu_preempt_note_context_switch()``, which
     79in turn is called from ``rcu_note_context_switch()``, which in
     80turn is called from the scheduler.
     81
     82
     83+-----------------------------------------------------------------------+
     84| **Quick Quiz**:                                                       |
     85+-----------------------------------------------------------------------+
     86| Why not just have the expedited grace period check the state of all   |
     87| the CPUs? After all, that would avoid all those real-time-unfriendly  |
     88| IPIs.                                                                 |
     89+-----------------------------------------------------------------------+
     90| **Answer**:                                                           |
     91+-----------------------------------------------------------------------+
     92| Because we want the RCU read-side critical sections to run fast,      |
     93| which means no memory barriers. Therefore, it is not possible to      |
     94| safely check the state from some other CPU. And even if it was        |
     95| possible to safely check the state, it would still be necessary to    |
     96| IPI the CPU to safely interact with the upcoming                      |
     97| ``rcu_read_unlock()`` invocation, which means that the remote state   |
     98| testing would not help the worst-case latency that real-time          |
     99| applications care about.                                              |
    100|                                                                       |
    101| One way to prevent your real-time application from getting hit with   |
    102| these IPIs is to build your kernel with ``CONFIG_NO_HZ_FULL=y``. RCU  |
    103| would then perceive the CPU running your application as being idle,   |
    104| and it would be able to safely detect that state without needing to   |
    105| IPI the CPU.                                                          |
    106+-----------------------------------------------------------------------+
    107
    108Please note that this is just the overall flow: Additional complications
    109can arise due to races with CPUs going idle or offline, among other
    110things.
    111
    112RCU-sched Expedited Grace Periods
    113---------------------------------
    114
    115``CONFIG_PREEMPTION=n`` kernels implement RCU-sched. The overall flow of
    116the handling of a given CPU by an RCU-sched expedited grace period is
    117shown in the following diagram:
    118
    119.. kernel-figure:: ExpSchedFlow.svg
    120
    121As with RCU-preempt, RCU-sched's ``synchronize_rcu_expedited()`` ignores
    122offline and idle CPUs, again because they are in remotely detectable
    123quiescent states. However, because the ``rcu_read_lock_sched()`` and
    124``rcu_read_unlock_sched()`` leave no trace of their invocation, in
    125general it is not possible to tell whether or not the current CPU is in
    126an RCU read-side critical section. The best that RCU-sched's
    127``rcu_exp_handler()`` can do is to check for idle, on the off-chance
    128that the CPU went idle while the IPI was in flight. If the CPU is idle,
    129then ``rcu_exp_handler()`` reports the quiescent state.
    130
    131Otherwise, the handler forces a future context switch by setting the
    132NEED_RESCHED flag of the current task's thread flag and the CPU preempt
    133counter. At the time of the context switch, the CPU reports the
    134quiescent state. Should the CPU go offline first, it will report the
    135quiescent state at that time.
    136
    137Expedited Grace Period and CPU Hotplug
    138--------------------------------------
    139
    140The expedited nature of expedited grace periods require a much tighter
    141interaction with CPU hotplug operations than is required for normal
    142grace periods. In addition, attempting to IPI offline CPUs will result
    143in splats, but failing to IPI online CPUs can result in too-short grace
    144periods. Neither option is acceptable in production kernels.
    145
    146The interaction between expedited grace periods and CPU hotplug
    147operations is carried out at several levels:
    148
    149#. The number of CPUs that have ever been online is tracked by the
    150   ``rcu_state`` structure's ``->ncpus`` field. The ``rcu_state``
    151   structure's ``->ncpus_snap`` field tracks the number of CPUs that
    152   have ever been online at the beginning of an RCU expedited grace
    153   period. Note that this number never decreases, at least in the
    154   absence of a time machine.
    155#. The identities of the CPUs that have ever been online is tracked by
    156   the ``rcu_node`` structure's ``->expmaskinitnext`` field. The
    157   ``rcu_node`` structure's ``->expmaskinit`` field tracks the
    158   identities of the CPUs that were online at least once at the
    159   beginning of the most recent RCU expedited grace period. The
    160   ``rcu_state`` structure's ``->ncpus`` and ``->ncpus_snap`` fields are
    161   used to detect when new CPUs have come online for the first time,
    162   that is, when the ``rcu_node`` structure's ``->expmaskinitnext``
    163   field has changed since the beginning of the last RCU expedited grace
    164   period, which triggers an update of each ``rcu_node`` structure's
    165   ``->expmaskinit`` field from its ``->expmaskinitnext`` field.
    166#. Each ``rcu_node`` structure's ``->expmaskinit`` field is used to
    167   initialize that structure's ``->expmask`` at the beginning of each
    168   RCU expedited grace period. This means that only those CPUs that have
    169   been online at least once will be considered for a given grace
    170   period.
    171#. Any CPU that goes offline will clear its bit in its leaf ``rcu_node``
    172   structure's ``->qsmaskinitnext`` field, so any CPU with that bit
    173   clear can safely be ignored. However, it is possible for a CPU coming
    174   online or going offline to have this bit set for some time while
    175   ``cpu_online`` returns ``false``.
    176#. For each non-idle CPU that RCU believes is currently online, the
    177   grace period invokes ``smp_call_function_single()``. If this
    178   succeeds, the CPU was fully online. Failure indicates that the CPU is
    179   in the process of coming online or going offline, in which case it is
    180   necessary to wait for a short time period and try again. The purpose
    181   of this wait (or series of waits, as the case may be) is to permit a
    182   concurrent CPU-hotplug operation to complete.
    183#. In the case of RCU-sched, one of the last acts of an outgoing CPU is
    184   to invoke ``rcu_report_dead()``, which reports a quiescent state for
    185   that CPU. However, this is likely paranoia-induced redundancy.
    186
    187+-----------------------------------------------------------------------+
    188| **Quick Quiz**:                                                       |
    189+-----------------------------------------------------------------------+
    190| Why all the dancing around with multiple counters and masks tracking  |
    191| CPUs that were once online? Why not just have a single set of masks   |
    192| tracking the currently online CPUs and be done with it?               |
    193+-----------------------------------------------------------------------+
    194| **Answer**:                                                           |
    195+-----------------------------------------------------------------------+
    196| Maintaining single set of masks tracking the online CPUs *sounds*     |
    197| easier, at least until you try working out all the race conditions    |
    198| between grace-period initialization and CPU-hotplug operations. For   |
    199| example, suppose initialization is progressing down the tree while a  |
    200| CPU-offline operation is progressing up the tree. This situation can  |
    201| result in bits set at the top of the tree that have no counterparts   |
    202| at the bottom of the tree. Those bits will never be cleared, which    |
    203| will result in grace-period hangs. In short, that way lies madness,   |
    204| to say nothing of a great many bugs, hangs, and deadlocks.            |
    205| In contrast, the current multi-mask multi-counter scheme ensures that |
    206| grace-period initialization will always see consistent masks up and   |
    207| down the tree, which brings significant simplifications over the      |
    208| single-mask method.                                                   |
    209|                                                                       |
    210| This is an instance of `deferring work in order to avoid              |
    211| synchronization <http://www.cs.columbia.edu/~library/TR-repository/re |
    212| ports/reports-1992/cucs-039-92.ps.gz>`__.                             |
    213| Lazily recording CPU-hotplug events at the beginning of the next      |
    214| grace period greatly simplifies maintenance of the CPU-tracking       |
    215| bitmasks in the ``rcu_node`` tree.                                    |
    216+-----------------------------------------------------------------------+
    217
    218Expedited Grace Period Refinements
    219----------------------------------
    220
    221Idle-CPU Checks
    222~~~~~~~~~~~~~~~
    223
    224Each expedited grace period checks for idle CPUs when initially forming
    225the mask of CPUs to be IPIed and again just before IPIing a CPU (both
    226checks are carried out by ``sync_rcu_exp_select_cpus()``). If the CPU is
    227idle at any time between those two times, the CPU will not be IPIed.
    228Instead, the task pushing the grace period forward will include the idle
    229CPUs in the mask passed to ``rcu_report_exp_cpu_mult()``.
    230
    231For RCU-sched, there is an additional check: If the IPI has interrupted
    232the idle loop, then ``rcu_exp_handler()`` invokes
    233``rcu_report_exp_rdp()`` to report the corresponding quiescent state.
    234
    235For RCU-preempt, there is no specific check for idle in the IPI handler
    236(``rcu_exp_handler()``), but because RCU read-side critical sections are
    237not permitted within the idle loop, if ``rcu_exp_handler()`` sees that
    238the CPU is within RCU read-side critical section, the CPU cannot
    239possibly be idle. Otherwise, ``rcu_exp_handler()`` invokes
    240``rcu_report_exp_rdp()`` to report the corresponding quiescent state,
    241regardless of whether or not that quiescent state was due to the CPU
    242being idle.
    243
    244In summary, RCU expedited grace periods check for idle when building the
    245bitmask of CPUs that must be IPIed, just before sending each IPI, and
    246(either explicitly or implicitly) within the IPI handler.
    247
    248Batching via Sequence Counter
    249~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    250
    251If each grace-period request was carried out separately, expedited grace
    252periods would have abysmal scalability and problematic high-load
    253characteristics. Because each grace-period operation can serve an
    254unlimited number of updates, it is important to *batch* requests, so
    255that a single expedited grace-period operation will cover all requests
    256in the corresponding batch.
    257
    258This batching is controlled by a sequence counter named
    259``->expedited_sequence`` in the ``rcu_state`` structure. This counter
    260has an odd value when there is an expedited grace period in progress and
    261an even value otherwise, so that dividing the counter value by two gives
    262the number of completed grace periods. During any given update request,
    263the counter must transition from even to odd and then back to even, thus
    264indicating that a grace period has elapsed. Therefore, if the initial
    265value of the counter is ``s``, the updater must wait until the counter
    266reaches at least the value ``(s+3)&~0x1``. This counter is managed by
    267the following access functions:
    268
    269#. ``rcu_exp_gp_seq_start()``, which marks the start of an expedited
    270   grace period.
    271#. ``rcu_exp_gp_seq_end()``, which marks the end of an expedited grace
    272   period.
    273#. ``rcu_exp_gp_seq_snap()``, which obtains a snapshot of the counter.
    274#. ``rcu_exp_gp_seq_done()``, which returns ``true`` if a full expedited
    275   grace period has elapsed since the corresponding call to
    276   ``rcu_exp_gp_seq_snap()``.
    277
    278Again, only one request in a given batch need actually carry out a
    279grace-period operation, which means there must be an efficient way to
    280identify which of many concurrent reqeusts will initiate the grace
    281period, and that there be an efficient way for the remaining requests to
    282wait for that grace period to complete. However, that is the topic of
    283the next section.
    284
    285Funnel Locking and Wait/Wakeup
    286~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    287
    288The natural way to sort out which of a batch of updaters will initiate
    289the expedited grace period is to use the ``rcu_node`` combining tree, as
    290implemented by the ``exp_funnel_lock()`` function. The first updater
    291corresponding to a given grace period arriving at a given ``rcu_node``
    292structure records its desired grace-period sequence number in the
    293``->exp_seq_rq`` field and moves up to the next level in the tree.
    294Otherwise, if the ``->exp_seq_rq`` field already contains the sequence
    295number for the desired grace period or some later one, the updater
    296blocks on one of four wait queues in the ``->exp_wq[]`` array, using the
    297second-from-bottom and third-from bottom bits as an index. An
    298``->exp_lock`` field in the ``rcu_node`` structure synchronizes access
    299to these fields.
    300
    301An empty ``rcu_node`` tree is shown in the following diagram, with the
    302white cells representing the ``->exp_seq_rq`` field and the red cells
    303representing the elements of the ``->exp_wq[]`` array.
    304
    305.. kernel-figure:: Funnel0.svg
    306
    307The next diagram shows the situation after the arrival of Task A and
    308Task B at the leftmost and rightmost leaf ``rcu_node`` structures,
    309respectively. The current value of the ``rcu_state`` structure's
    310``->expedited_sequence`` field is zero, so adding three and clearing the
    311bottom bit results in the value two, which both tasks record in the
    312``->exp_seq_rq`` field of their respective ``rcu_node`` structures:
    313
    314.. kernel-figure:: Funnel1.svg
    315
    316Each of Tasks A and B will move up to the root ``rcu_node`` structure.
    317Suppose that Task A wins, recording its desired grace-period sequence
    318number and resulting in the state shown below:
    319
    320.. kernel-figure:: Funnel2.svg
    321
    322Task A now advances to initiate a new grace period, while Task B moves
    323up to the root ``rcu_node`` structure, and, seeing that its desired
    324sequence number is already recorded, blocks on ``->exp_wq[1]``.
    325
    326+-----------------------------------------------------------------------+
    327| **Quick Quiz**:                                                       |
    328+-----------------------------------------------------------------------+
    329| Why ``->exp_wq[1]``? Given that the value of these tasks' desired     |
    330| sequence number is two, so shouldn't they instead block on            |
    331| ``->exp_wq[2]``?                                                      |
    332+-----------------------------------------------------------------------+
    333| **Answer**:                                                           |
    334+-----------------------------------------------------------------------+
    335| No.                                                                   |
    336| Recall that the bottom bit of the desired sequence number indicates   |
    337| whether or not a grace period is currently in progress. It is         |
    338| therefore necessary to shift the sequence number right one bit        |
    339| position to obtain the number of the grace period. This results in    |
    340| ``->exp_wq[1]``.                                                      |
    341+-----------------------------------------------------------------------+
    342
    343If Tasks C and D also arrive at this point, they will compute the same
    344desired grace-period sequence number, and see that both leaf
    345``rcu_node`` structures already have that value recorded. They will
    346therefore block on their respective ``rcu_node`` structures'
    347``->exp_wq[1]`` fields, as shown below:
    348
    349.. kernel-figure:: Funnel3.svg
    350
    351Task A now acquires the ``rcu_state`` structure's ``->exp_mutex`` and
    352initiates the grace period, which increments ``->expedited_sequence``.
    353Therefore, if Tasks E and F arrive, they will compute a desired sequence
    354number of 4 and will record this value as shown below:
    355
    356.. kernel-figure:: Funnel4.svg
    357
    358Tasks E and F will propagate up the ``rcu_node`` combining tree, with
    359Task F blocking on the root ``rcu_node`` structure and Task E wait for
    360Task A to finish so that it can start the next grace period. The
    361resulting state is as shown below:
    362
    363.. kernel-figure:: Funnel5.svg
    364
    365Once the grace period completes, Task A starts waking up the tasks
    366waiting for this grace period to complete, increments the
    367``->expedited_sequence``, acquires the ``->exp_wake_mutex`` and then
    368releases the ``->exp_mutex``. This results in the following state:
    369
    370.. kernel-figure:: Funnel6.svg
    371
    372Task E can then acquire ``->exp_mutex`` and increment
    373``->expedited_sequence`` to the value three. If new tasks G and H arrive
    374and moves up the combining tree at the same time, the state will be as
    375follows:
    376
    377.. kernel-figure:: Funnel7.svg
    378
    379Note that three of the root ``rcu_node`` structure's waitqueues are now
    380occupied. However, at some point, Task A will wake up the tasks blocked
    381on the ``->exp_wq`` waitqueues, resulting in the following state:
    382
    383.. kernel-figure:: Funnel8.svg
    384
    385Execution will continue with Tasks E and H completing their grace
    386periods and carrying out their wakeups.
    387
    388+-----------------------------------------------------------------------+
    389| **Quick Quiz**:                                                       |
    390+-----------------------------------------------------------------------+
    391| What happens if Task A takes so long to do its wakeups that Task E's  |
    392| grace period completes?                                               |
    393+-----------------------------------------------------------------------+
    394| **Answer**:                                                           |
    395+-----------------------------------------------------------------------+
    396| Then Task E will block on the ``->exp_wake_mutex``, which will also   |
    397| prevent it from releasing ``->exp_mutex``, which in turn will prevent |
    398| the next grace period from starting. This last is important in        |
    399| preventing overflow of the ``->exp_wq[]`` array.                      |
    400+-----------------------------------------------------------------------+
    401
    402Use of Workqueues
    403~~~~~~~~~~~~~~~~~
    404
    405In earlier implementations, the task requesting the expedited grace
    406period also drove it to completion. This straightforward approach had
    407the disadvantage of needing to account for POSIX signals sent to user
    408tasks, so more recent implemementations use the Linux kernel's
    409workqueues (see Documentation/core-api/workqueue.rst).
    410
    411The requesting task still does counter snapshotting and funnel-lock
    412processing, but the task reaching the top of the funnel lock does a
    413``schedule_work()`` (from ``_synchronize_rcu_expedited()`` so that a
    414workqueue kthread does the actual grace-period processing. Because
    415workqueue kthreads do not accept POSIX signals, grace-period-wait
    416processing need not allow for POSIX signals. In addition, this approach
    417allows wakeups for the previous expedited grace period to be overlapped
    418with processing for the next expedited grace period. Because there are
    419only four sets of waitqueues, it is necessary to ensure that the
    420previous grace period's wakeups complete before the next grace period's
    421wakeups start. This is handled by having the ``->exp_mutex`` guard
    422expedited grace-period processing and the ``->exp_wake_mutex`` guard
    423wakeups. The key point is that the ``->exp_mutex`` is not released until
    424the first wakeup is complete, which means that the ``->exp_wake_mutex``
    425has already been acquired at that point. This approach ensures that the
    426previous grace period's wakeups can be carried out while the current
    427grace period is in process, but that these wakeups will complete before
    428the next grace period starts. This means that only three waitqueues are
    429required, guaranteeing that the four that are provided are sufficient.
    430
    431Stall Warnings
    432~~~~~~~~~~~~~~
    433
    434Expediting grace periods does nothing to speed things up when RCU
    435readers take too long, and therefore expedited grace periods check for
    436stalls just as normal grace periods do.
    437
    438+-----------------------------------------------------------------------+
    439| **Quick Quiz**:                                                       |
    440+-----------------------------------------------------------------------+
    441| But why not just let the normal grace-period machinery detect the     |
    442| stalls, given that a given reader must block both normal and          |
    443| expedited grace periods?                                              |
    444+-----------------------------------------------------------------------+
    445| **Answer**:                                                           |
    446+-----------------------------------------------------------------------+
    447| Because it is quite possible that at a given time there is no normal  |
    448| grace period in progress, in which case the normal grace period       |
    449| cannot emit a stall warning.                                          |
    450+-----------------------------------------------------------------------+
    451
    452The ``synchronize_sched_expedited_wait()`` function loops waiting for
    453the expedited grace period to end, but with a timeout set to the current
    454RCU CPU stall-warning time. If this time is exceeded, any CPUs or
    455``rcu_node`` structures blocking the current grace period are printed.
    456Each stall warning results in another pass through the loop, but the
    457second and subsequent passes use longer stall times.
    458
    459Mid-boot operation
    460~~~~~~~~~~~~~~~~~~
    461
    462The use of workqueues has the advantage that the expedited grace-period
    463code need not worry about POSIX signals. Unfortunately, it has the
    464corresponding disadvantage that workqueues cannot be used until they are
    465initialized, which does not happen until some time after the scheduler
    466spawns the first task. Given that there are parts of the kernel that
    467really do want to execute grace periods during this mid-boot “dead
    468zone”, expedited grace periods must do something else during thie time.
    469
    470What they do is to fall back to the old practice of requiring that the
    471requesting task drive the expedited grace period, as was the case before
    472the use of workqueues. However, the requesting task is only required to
    473drive the grace period during the mid-boot dead zone. Before mid-boot, a
    474synchronous grace period is a no-op. Some time after mid-boot,
    475workqueues are used.
    476
    477Non-expedited non-SRCU synchronous grace periods must also operate
    478normally during mid-boot. This is handled by causing non-expedited grace
    479periods to take the expedited code path during mid-boot.
    480
    481The current code assumes that there are no POSIX signals during the
    482mid-boot dead zone. However, if an overwhelming need for POSIX signals
    483somehow arises, appropriate adjustments can be made to the expedited
    484stall-warning code. One such adjustment would reinstate the
    485pre-workqueue stall-warning checks, but only during the mid-boot dead
    486zone.
    487
    488With this refinement, synchronous grace periods can now be used from
    489task context pretty much any time during the life of the kernel. That
    490is, aside from some points in the suspend, hibernate, or shutdown code
    491path.
    492
    493Summary
    494~~~~~~~
    495
    496Expedited grace periods use a sequence-number approach to promote
    497batching, so that a single grace-period operation can serve numerous
    498requests. A funnel lock is used to efficiently identify the one task out
    499of a concurrent group that will request the grace period. All members of
    500the group will block on waitqueues provided in the ``rcu_node``
    501structure. The actual grace-period processing is carried out by a
    502workqueue.
    503
    504CPU-hotplug operations are noted lazily in order to prevent the need for
    505tight synchronization between expedited grace periods and CPU-hotplug
    506operations. The dyntick-idle counters are used to avoid sending IPIs to
    507idle CPUs, at least in the common case. RCU-preempt and RCU-sched use
    508different IPI handlers and different code to respond to the state
    509changes carried out by those handlers, but otherwise use common code.
    510
    511Quiescent states are tracked using the ``rcu_node`` tree, and once all
    512necessary quiescent states have been reported, all tasks waiting on this
    513expedited grace period are awakened. A pair of mutexes are used to allow
    514one grace period's wakeups to proceed concurrently with the next grace
    515period's processing.
    516
    517This combination of mechanisms allows expedited grace periods to run
    518reasonably efficiently. However, for non-time-critical tasks, normal
    519grace periods should be used instead because their longer duration
    520permits much higher degrees of batching, and thus much lower per-request
    521overheads.