Documentation/RCU/Design/Expedited-Grace-Periods/Expedited-Grace-Periods.html

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