1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
2 "http://www.w3.org/TR/html4/loose.dtd">
4 <head><title>A Tour Through TREE_RCU's Expedited Grace Periods</title>
5 <meta HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
9 This document describes RCU's expedited grace periods.
10 Unlike RCU's normal grace periods, which accept long latencies to attain
11 high efficiency and minimal disturbance, expedited grace periods accept
12 lower efficiency and significant disturbance to attain shorter latencies.
15 There are two flavors of RCU (RCU-preempt and RCU-sched), with an earlier
16 third RCU-bh flavor having been implemented in terms of the other two.
17 Each of the two implementations is covered in its own section.
20 <li> <a href="#Expedited Grace Period Design">
21 Expedited Grace Period Design</a>
22 <li> <a href="#RCU-preempt Expedited Grace Periods">
23 RCU-preempt Expedited Grace Periods</a>
24 <li> <a href="#RCU-sched Expedited Grace Periods">
25 RCU-sched Expedited Grace Periods</a>
26 <li> <a href="#Expedited Grace Period and CPU Hotplug">
27 Expedited Grace Period and CPU Hotplug</a>
28 <li> <a href="#Expedited Grace Period Refinements">
29 Expedited Grace Period Refinements</a>
32 <h2><a name="Expedited Grace Period Design">
33 Expedited Grace Period Design</a></h2>
36 The expedited RCU grace periods cannot be accused of being subtle,
37 given that they for all intents and purposes hammer every CPU that
38 has not yet provided a quiescent state for the current expedited
40 The one saving grace is that the hammer has grown a bit smaller
41 over time: The old call to <tt>try_stop_cpus()</tt> has been
42 replaced with a set of calls to <tt>smp_call_function_single()</tt>,
43 each of which results in an IPI to the target CPU.
44 The corresponding handler function checks the CPU's state, motivating
45 a faster quiescent state where possible, and triggering a report
46 of that quiescent state.
47 As always for RCU, once everything has spent some time in a quiescent
48 state, the expedited grace period has completed.
51 The details of the <tt>smp_call_function_single()</tt> handler's
52 operation depend on the RCU flavor, as described in the following
55 <h2><a name="RCU-preempt Expedited Grace Periods">
56 RCU-preempt Expedited Grace Periods</a></h2>
59 <tt>CONFIG_PREEMPT=y</tt> kernels implement RCU-preempt.
60 The overall flow of the handling of a given CPU by an RCU-preempt
61 expedited grace period is shown in the following diagram:
63 <p><img src="ExpRCUFlow.svg" alt="ExpRCUFlow.svg" width="55%">
66 The solid arrows denote direct action, for example, a function call.
67 The dotted arrows denote indirect action, for example, an IPI
68 or a state that is reached after some time.
71 If a given CPU is offline or idle, <tt>synchronize_rcu_expedited()</tt>
72 will ignore it because idle and offline CPUs are already residing
74 Otherwise, the expedited grace period will use
75 <tt>smp_call_function_single()</tt> to send the CPU an IPI, which
76 is handled by <tt>rcu_exp_handler()</tt>.
79 However, because this is preemptible RCU, <tt>rcu_exp_handler()</tt>
80 can check to see if the CPU is currently running in an RCU read-side
82 If not, the handler can immediately report a quiescent state.
83 Otherwise, it sets flags so that the outermost <tt>rcu_read_unlock()</tt>
84 invocation will provide the needed quiescent-state report.
85 This flag-setting avoids the previous forced preemption of all
86 CPUs that might have RCU read-side critical sections.
87 In addition, this flag-setting is done so as to avoid increasing
88 the overhead of the common-case fastpath through the scheduler.
91 Again because this is preemptible RCU, an RCU read-side critical section
93 When that happens, RCU will enqueue the task, which will the continue to
94 block the current expedited grace period until it resumes and finds its
95 outermost <tt>rcu_read_unlock()</tt>.
96 The CPU will report a quiescent state just after enqueuing the task because
97 the CPU is no longer blocking the grace period.
98 It is instead the preempted task doing the blocking.
99 The list of blocked tasks is managed by <tt>rcu_preempt_ctxt_queue()</tt>,
100 which is called from <tt>rcu_preempt_note_context_switch()</tt>, which
101 in turn is called from <tt>rcu_note_context_switch()</tt>, which in
102 turn is called from the scheduler.
105 <tr><th> </th></tr>
106 <tr><th align="left">Quick Quiz:</th></tr>
108 Why not just have the expedited grace period check the
109 state of all the CPUs?
110 After all, that would avoid all those real-time-unfriendly IPIs.
112 <tr><th align="left">Answer:</th></tr>
113 <tr><td bgcolor="#ffffff"><font color="ffffff">
114 Because we want the RCU read-side critical sections to run fast,
115 which means no memory barriers.
116 Therefore, it is not possible to safely check the state from some
118 And even if it was possible to safely check the state, it would
119 still be necessary to IPI the CPU to safely interact with the
120 upcoming <tt>rcu_read_unlock()</tt> invocation, which means that
121 the remote state testing would not help the worst-case
122 latency that real-time applications care about.
124 <p><font color="ffffff">One way to prevent your real-time
125 application from getting hit with these IPIs is to
126 build your kernel with <tt>CONFIG_NO_HZ_FULL=y</tt>.
127 RCU would then perceive the CPU running your application
128 as being idle, and it would be able to safely detect that
129 state without needing to IPI the CPU.
131 <tr><td> </td></tr>
135 Please note that this is just the overall flow:
136 Additional complications can arise due to races with CPUs going idle
137 or offline, among other things.
139 <h2><a name="RCU-sched Expedited Grace Periods">
140 RCU-sched Expedited Grace Periods</a></h2>
143 <tt>CONFIG_PREEMPT=n</tt> kernels implement RCU-sched.
144 The overall flow of the handling of a given CPU by an RCU-sched
145 expedited grace period is shown in the following diagram:
147 <p><img src="ExpSchedFlow.svg" alt="ExpSchedFlow.svg" width="55%">
150 As with RCU-preempt, RCU-sched's
151 <tt>synchronize_rcu_expedited()</tt> ignores offline and
152 idle CPUs, again because they are in remotely detectable
155 <tt>rcu_read_lock_sched()</tt> and <tt>rcu_read_unlock_sched()</tt>
156 leave no trace of their invocation, in general it is not possible to tell
157 whether or not the current CPU is in an RCU read-side critical section.
158 The best that RCU-sched's <tt>rcu_exp_handler()</tt> can do is to check
159 for idle, on the off-chance that the CPU went idle while the IPI
161 If the CPU is idle, then <tt>rcu_exp_handler()</tt> reports
164 <p> Otherwise, the handler forces a future context switch by setting the
165 NEED_RESCHED flag of the current task's thread flag and the CPU preempt
167 At the time of the context switch, the CPU reports the quiescent state.
168 Should the CPU go offline first, it will report the quiescent state
171 <h2><a name="Expedited Grace Period and CPU Hotplug">
172 Expedited Grace Period and CPU Hotplug</a></h2>
175 The expedited nature of expedited grace periods require a much tighter
176 interaction with CPU hotplug operations than is required for normal
178 In addition, attempting to IPI offline CPUs will result in splats, but
179 failing to IPI online CPUs can result in too-short grace periods.
180 Neither option is acceptable in production kernels.
183 The interaction between expedited grace periods and CPU hotplug operations
184 is carried out at several levels:
187 <li> The number of CPUs that have ever been online is tracked
188 by the <tt>rcu_state</tt> structure's <tt>->ncpus</tt>
190 The <tt>rcu_state</tt> structure's <tt>->ncpus_snap</tt>
191 field tracks the number of CPUs that have ever been online
192 at the beginning of an RCU expedited grace period.
193 Note that this number never decreases, at least in the absence
195 <li> The identities of the CPUs that have ever been online is
196 tracked by the <tt>rcu_node</tt> structure's
197 <tt>->expmaskinitnext</tt> field.
198 The <tt>rcu_node</tt> structure's <tt>->expmaskinit</tt>
199 field tracks the identities of the CPUs that were online
200 at least once at the beginning of the most recent RCU
201 expedited grace period.
202 The <tt>rcu_state</tt> structure's <tt>->ncpus</tt> and
203 <tt>->ncpus_snap</tt> fields are used to detect when
204 new CPUs have come online for the first time, that is,
205 when the <tt>rcu_node</tt> structure's <tt>->expmaskinitnext</tt>
206 field has changed since the beginning of the last RCU
207 expedited grace period, which triggers an update of each
208 <tt>rcu_node</tt> structure's <tt>->expmaskinit</tt>
209 field from its <tt>->expmaskinitnext</tt> field.
210 <li> Each <tt>rcu_node</tt> structure's <tt>->expmaskinit</tt>
211 field is used to initialize that structure's
212 <tt>->expmask</tt> at the beginning of each RCU
213 expedited grace period.
214 This means that only those CPUs that have been online at least
215 once will be considered for a given grace period.
216 <li> Any CPU that goes offline will clear its bit in its leaf
217 <tt>rcu_node</tt> structure's <tt>->qsmaskinitnext</tt>
218 field, so any CPU with that bit clear can safely be ignored.
219 However, it is possible for a CPU coming online or going offline
220 to have this bit set for some time while <tt>cpu_online</tt>
221 returns <tt>false</tt>.
222 <li> For each non-idle CPU that RCU believes is currently online, the grace
223 period invokes <tt>smp_call_function_single()</tt>.
224 If this succeeds, the CPU was fully online.
225 Failure indicates that the CPU is in the process of coming online
226 or going offline, in which case it is necessary to wait for a
227 short time period and try again.
228 The purpose of this wait (or series of waits, as the case may be)
229 is to permit a concurrent CPU-hotplug operation to complete.
230 <li> In the case of RCU-sched, one of the last acts of an outgoing CPU
231 is to invoke <tt>rcu_report_dead()</tt>, which
232 reports a quiescent state for that CPU.
233 However, this is likely paranoia-induced redundancy. <!-- @@@ -->
237 <tr><th> </th></tr>
238 <tr><th align="left">Quick Quiz:</th></tr>
240 Why all the dancing around with multiple counters and masks
241 tracking CPUs that were once online?
242 Why not just have a single set of masks tracking the currently
243 online CPUs and be done with it?
245 <tr><th align="left">Answer:</th></tr>
246 <tr><td bgcolor="#ffffff"><font color="ffffff">
247 Maintaining single set of masks tracking the online CPUs <i>sounds</i>
248 easier, at least until you try working out all the race conditions
249 between grace-period initialization and CPU-hotplug operations.
250 For example, suppose initialization is progressing down the
251 tree while a CPU-offline operation is progressing up the tree.
252 This situation can result in bits set at the top of the tree
253 that have no counterparts at the bottom of the tree.
254 Those bits will never be cleared, which will result in
256 In short, that way lies madness, to say nothing of a great many
257 bugs, hangs, and deadlocks.
259 <p><font color="ffffff">
260 In contrast, the current multi-mask multi-counter scheme ensures
261 that grace-period initialization will always see consistent masks
262 up and down the tree, which brings significant simplifications
263 over the single-mask method.
265 <p><font color="ffffff">
266 This is an instance of
267 <a href="http://www.cs.columbia.edu/~library/TR-repository/reports/reports-1992/cucs-039-92.ps.gz"><font color="ffffff">
268 deferring work in order to avoid synchronization</a>.
269 Lazily recording CPU-hotplug events at the beginning of the next
270 grace period greatly simplifies maintenance of the CPU-tracking
271 bitmasks in the <tt>rcu_node</tt> tree.
273 <tr><td> </td></tr>
276 <h2><a name="Expedited Grace Period Refinements">
277 Expedited Grace Period Refinements</a></h2>
280 <li> <a href="#Idle-CPU Checks">Idle-CPU checks</a>.
281 <li> <a href="#Batching via Sequence Counter">
282 Batching via sequence counter</a>.
283 <li> <a href="#Funnel Locking and Wait/Wakeup">
284 Funnel locking and wait/wakeup</a>.
285 <li> <a href="#Use of Workqueues">Use of Workqueues</a>.
286 <li> <a href="#Stall Warnings">Stall warnings</a>.
287 <li> <a href="#Mid-Boot Operation">Mid-boot operation</a>.
290 <h3><a name="Idle-CPU Checks">Idle-CPU Checks</a></h3>
293 Each expedited grace period checks for idle CPUs when initially forming
294 the mask of CPUs to be IPIed and again just before IPIing a CPU
295 (both checks are carried out by <tt>sync_rcu_exp_select_cpus()</tt>).
296 If the CPU is idle at any time between those two times, the CPU will
298 Instead, the task pushing the grace period forward will include the
299 idle CPUs in the mask passed to <tt>rcu_report_exp_cpu_mult()</tt>.
302 For RCU-sched, there is an additional check:
303 If the IPI has interrupted the idle loop, then
304 <tt>rcu_exp_handler()</tt> invokes <tt>rcu_report_exp_rdp()</tt>
305 to report the corresponding quiescent state.
308 For RCU-preempt, there is no specific check for idle in the
309 IPI handler (<tt>rcu_exp_handler()</tt>), but because
310 RCU read-side critical sections are not permitted within the
311 idle loop, if <tt>rcu_exp_handler()</tt> sees that the CPU is within
312 RCU read-side critical section, the CPU cannot possibly be idle.
313 Otherwise, <tt>rcu_exp_handler()</tt> invokes
314 <tt>rcu_report_exp_rdp()</tt> to report the corresponding quiescent
315 state, regardless of whether or not that quiescent state was due to
319 In summary, RCU expedited grace periods check for idle when building
320 the bitmask of CPUs that must be IPIed, just before sending each IPI,
321 and (either explicitly or implicitly) within the IPI handler.
323 <h3><a name="Batching via Sequence Counter">
324 Batching via Sequence Counter</a></h3>
327 If each grace-period request was carried out separately, expedited
328 grace periods would have abysmal scalability and
329 problematic high-load characteristics.
330 Because each grace-period operation can serve an unlimited number of
331 updates, it is important to <i>batch</i> requests, so that a single
332 expedited grace-period operation will cover all requests in the
336 This batching is controlled by a sequence counter named
337 <tt>->expedited_sequence</tt> in the <tt>rcu_state</tt> structure.
338 This counter has an odd value when there is an expedited grace period
339 in progress and an even value otherwise, so that dividing the counter
340 value by two gives the number of completed grace periods.
341 During any given update request, the counter must transition from
342 even to odd and then back to even, thus indicating that a grace
344 Therefore, if the initial value of the counter is <tt>s</tt>,
345 the updater must wait until the counter reaches at least the
346 value <tt>(s+3)&~0x1</tt>.
347 This counter is managed by the following access functions:
350 <li> <tt>rcu_exp_gp_seq_start()</tt>, which marks the start of
351 an expedited grace period.
352 <li> <tt>rcu_exp_gp_seq_end()</tt>, which marks the end of an
353 expedited grace period.
354 <li> <tt>rcu_exp_gp_seq_snap()</tt>, which obtains a snapshot of
356 <li> <tt>rcu_exp_gp_seq_done()</tt>, which returns <tt>true</tt>
357 if a full expedited grace period has elapsed since the
358 corresponding call to <tt>rcu_exp_gp_seq_snap()</tt>.
362 Again, only one request in a given batch need actually carry out
363 a grace-period operation, which means there must be an efficient
364 way to identify which of many concurrent reqeusts will initiate
365 the grace period, and that there be an efficient way for the
366 remaining requests to wait for that grace period to complete.
367 However, that is the topic of the next section.
369 <h3><a name="Funnel Locking and Wait/Wakeup">
370 Funnel Locking and Wait/Wakeup</a></h3>
373 The natural way to sort out which of a batch of updaters will initiate
374 the expedited grace period is to use the <tt>rcu_node</tt> combining
375 tree, as implemented by the <tt>exp_funnel_lock()</tt> function.
376 The first updater corresponding to a given grace period arriving
377 at a given <tt>rcu_node</tt> structure records its desired grace-period
378 sequence number in the <tt>->exp_seq_rq</tt> field and moves up
379 to the next level in the tree.
380 Otherwise, if the <tt>->exp_seq_rq</tt> field already contains
381 the sequence number for the desired grace period or some later one,
382 the updater blocks on one of four wait queues in the
383 <tt>->exp_wq[]</tt> array, using the second-from-bottom
384 and third-from bottom bits as an index.
385 An <tt>->exp_lock</tt> field in the <tt>rcu_node</tt> structure
386 synchronizes access to these fields.
389 An empty <tt>rcu_node</tt> tree is shown in the following diagram,
390 with the white cells representing the <tt>->exp_seq_rq</tt> field
391 and the red cells representing the elements of the
392 <tt>->exp_wq[]</tt> array.
394 <p><img src="Funnel0.svg" alt="Funnel0.svg" width="75%">
397 The next diagram shows the situation after the arrival of Task A
398 and Task B at the leftmost and rightmost leaf <tt>rcu_node</tt>
399 structures, respectively.
400 The current value of the <tt>rcu_state</tt> structure's
401 <tt>->expedited_sequence</tt> field is zero, so adding three and
402 clearing the bottom bit results in the value two, which both tasks
403 record in the <tt>->exp_seq_rq</tt> field of their respective
404 <tt>rcu_node</tt> structures:
406 <p><img src="Funnel1.svg" alt="Funnel1.svg" width="75%">
409 Each of Tasks A and B will move up to the root
410 <tt>rcu_node</tt> structure.
411 Suppose that Task A wins, recording its desired grace-period sequence
412 number and resulting in the state shown below:
414 <p><img src="Funnel2.svg" alt="Funnel2.svg" width="75%">
417 Task A now advances to initiate a new grace period, while Task B
418 moves up to the root <tt>rcu_node</tt> structure, and, seeing that
419 its desired sequence number is already recorded, blocks on
420 <tt>->exp_wq[1]</tt>.
423 <tr><th> </th></tr>
424 <tr><th align="left">Quick Quiz:</th></tr>
426 Why <tt>->exp_wq[1]</tt>?
427 Given that the value of these tasks' desired sequence number is
428 two, so shouldn't they instead block on <tt>->exp_wq[2]</tt>?
430 <tr><th align="left">Answer:</th></tr>
431 <tr><td bgcolor="#ffffff"><font color="ffffff">
434 <p><font color="ffffff">
435 Recall that the bottom bit of the desired sequence number indicates
436 whether or not a grace period is currently in progress.
437 It is therefore necessary to shift the sequence number right one
438 bit position to obtain the number of the grace period.
439 This results in <tt>->exp_wq[1]</tt>.
441 <tr><td> </td></tr>
445 If Tasks C and D also arrive at this point, they will compute the
446 same desired grace-period sequence number, and see that both leaf
447 <tt>rcu_node</tt> structures already have that value recorded.
448 They will therefore block on their respective <tt>rcu_node</tt>
449 structures' <tt>->exp_wq[1]</tt> fields, as shown below:
451 <p><img src="Funnel3.svg" alt="Funnel3.svg" width="75%">
454 Task A now acquires the <tt>rcu_state</tt> structure's
455 <tt>->exp_mutex</tt> and initiates the grace period, which
456 increments <tt>->expedited_sequence</tt>.
457 Therefore, if Tasks E and F arrive, they will compute
458 a desired sequence number of 4 and will record this value as
461 <p><img src="Funnel4.svg" alt="Funnel4.svg" width="75%">
464 Tasks E and F will propagate up the <tt>rcu_node</tt>
465 combining tree, with Task F blocking on the root <tt>rcu_node</tt>
466 structure and Task E wait for Task A to finish so that
467 it can start the next grace period.
468 The resulting state is as shown below:
470 <p><img src="Funnel5.svg" alt="Funnel5.svg" width="75%">
473 Once the grace period completes, Task A
474 starts waking up the tasks waiting for this grace period to complete,
475 increments the <tt>->expedited_sequence</tt>,
476 acquires the <tt>->exp_wake_mutex</tt> and then releases the
477 <tt>->exp_mutex</tt>.
478 This results in the following state:
480 <p><img src="Funnel6.svg" alt="Funnel6.svg" width="75%">
483 Task E can then acquire <tt>->exp_mutex</tt> and increment
484 <tt>->expedited_sequence</tt> to the value three.
485 If new tasks G and H arrive and moves up the combining tree at the
486 same time, the state will be as follows:
488 <p><img src="Funnel7.svg" alt="Funnel7.svg" width="75%">
491 Note that three of the root <tt>rcu_node</tt> structure's
492 waitqueues are now occupied.
493 However, at some point, Task A will wake up the
494 tasks blocked on the <tt>->exp_wq</tt> waitqueues, resulting
495 in the following state:
497 <p><img src="Funnel8.svg" alt="Funnel8.svg" width="75%">
500 Execution will continue with Tasks E and H completing
501 their grace periods and carrying out their wakeups.
504 <tr><th> </th></tr>
505 <tr><th align="left">Quick Quiz:</th></tr>
507 What happens if Task A takes so long to do its wakeups
508 that Task E's grace period completes?
510 <tr><th align="left">Answer:</th></tr>
511 <tr><td bgcolor="#ffffff"><font color="ffffff">
512 Then Task E will block on the <tt>->exp_wake_mutex</tt>,
513 which will also prevent it from releasing <tt>->exp_mutex</tt>,
514 which in turn will prevent the next grace period from starting.
515 This last is important in preventing overflow of the
516 <tt>->exp_wq[]</tt> array.
518 <tr><td> </td></tr>
521 <h3><a name="Use of Workqueues">Use of Workqueues</a></h3>
524 In earlier implementations, the task requesting the expedited
525 grace period also drove it to completion.
526 This straightforward approach had the disadvantage of needing to
527 account for POSIX signals sent to user tasks,
528 so more recent implemementations use the Linux kernel's
529 <a href="https://www.kernel.org/doc/Documentation/core-api/workqueue.rst">workqueues</a>.
532 The requesting task still does counter snapshotting and funnel-lock
533 processing, but the task reaching the top of the funnel lock
534 does a <tt>schedule_work()</tt> (from <tt>_synchronize_rcu_expedited()</tt>
535 so that a workqueue kthread does the actual grace-period processing.
536 Because workqueue kthreads do not accept POSIX signals, grace-period-wait
537 processing need not allow for POSIX signals.
539 In addition, this approach allows wakeups for the previous expedited
540 grace period to be overlapped with processing for the next expedited
542 Because there are only four sets of waitqueues, it is necessary to
543 ensure that the previous grace period's wakeups complete before the
544 next grace period's wakeups start.
545 This is handled by having the <tt>->exp_mutex</tt>
546 guard expedited grace-period processing and the
547 <tt>->exp_wake_mutex</tt> guard wakeups.
548 The key point is that the <tt>->exp_mutex</tt> is not released
549 until the first wakeup is complete, which means that the
550 <tt>->exp_wake_mutex</tt> has already been acquired at that point.
551 This approach ensures that the previous grace period's wakeups can
552 be carried out while the current grace period is in process, but
553 that these wakeups will complete before the next grace period starts.
554 This means that only three waitqueues are required, guaranteeing that
555 the four that are provided are sufficient.
557 <h3><a name="Stall Warnings">Stall Warnings</a></h3>
560 Expediting grace periods does nothing to speed things up when RCU
561 readers take too long, and therefore expedited grace periods check
562 for stalls just as normal grace periods do.
565 <tr><th> </th></tr>
566 <tr><th align="left">Quick Quiz:</th></tr>
568 But why not just let the normal grace-period machinery
569 detect the stalls, given that a given reader must block
570 both normal and expedited grace periods?
572 <tr><th align="left">Answer:</th></tr>
573 <tr><td bgcolor="#ffffff"><font color="ffffff">
574 Because it is quite possible that at a given time there
575 is no normal grace period in progress, in which case the
576 normal grace period cannot emit a stall warning.
578 <tr><td> </td></tr>
581 The <tt>synchronize_sched_expedited_wait()</tt> function loops waiting
582 for the expedited grace period to end, but with a timeout set to the
583 current RCU CPU stall-warning time.
584 If this time is exceeded, any CPUs or <tt>rcu_node</tt> structures
585 blocking the current grace period are printed.
586 Each stall warning results in another pass through the loop, but the
587 second and subsequent passes use longer stall times.
589 <h3><a name="Mid-Boot Operation">Mid-boot operation</a></h3>
592 The use of workqueues has the advantage that the expedited
593 grace-period code need not worry about POSIX signals.
594 Unfortunately, it has the
595 corresponding disadvantage that workqueues cannot be used until
596 they are initialized, which does not happen until some time after
597 the scheduler spawns the first task.
598 Given that there are parts of the kernel that really do want to
599 execute grace periods during this mid-boot “dead zone”,
600 expedited grace periods must do something else during thie time.
603 What they do is to fall back to the old practice of requiring that the
604 requesting task drive the expedited grace period, as was the case
605 before the use of workqueues.
606 However, the requesting task is only required to drive the grace period
607 during the mid-boot dead zone.
608 Before mid-boot, a synchronous grace period is a no-op.
609 Some time after mid-boot, workqueues are used.
612 Non-expedited non-SRCU synchronous grace periods must also operate
613 normally during mid-boot.
614 This is handled by causing non-expedited grace periods to take the
615 expedited code path during mid-boot.
618 The current code assumes that there are no POSIX signals during
619 the mid-boot dead zone.
620 However, if an overwhelming need for POSIX signals somehow arises,
621 appropriate adjustments can be made to the expedited stall-warning code.
622 One such adjustment would reinstate the pre-workqueue stall-warning
623 checks, but only during the mid-boot dead zone.
626 With this refinement, synchronous grace periods can now be used from
627 task context pretty much any time during the life of the kernel.
628 That is, aside from some points in the suspend, hibernate, or shutdown
631 <h3><a name="Summary">
635 Expedited grace periods use a sequence-number approach to promote
636 batching, so that a single grace-period operation can serve numerous
638 A funnel lock is used to efficiently identify the one task out of
639 a concurrent group that will request the grace period.
640 All members of the group will block on waitqueues provided in
641 the <tt>rcu_node</tt> structure.
642 The actual grace-period processing is carried out by a workqueue.
645 CPU-hotplug operations are noted lazily in order to prevent the need
646 for tight synchronization between expedited grace periods and
647 CPU-hotplug operations.
648 The dyntick-idle counters are used to avoid sending IPIs to idle CPUs,
649 at least in the common case.
650 RCU-preempt and RCU-sched use different IPI handlers and different
651 code to respond to the state changes carried out by those handlers,
652 but otherwise use common code.
655 Quiescent states are tracked using the <tt>rcu_node</tt> tree,
656 and once all necessary quiescent states have been reported,
657 all tasks waiting on this expedited grace period are awakened.
658 A pair of mutexes are used to allow one grace period's wakeups
659 to proceed concurrently with the next grace period's processing.
662 This combination of mechanisms allows expedited grace periods to
663 run reasonably efficiently.
664 However, for non-time-critical tasks, normal grace periods should be
665 used instead because their longer duration permits much higher
666 degrees of batching, and thus much lower per-request overheads.