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 three flavors of RCU (RCU-bh, RCU-preempt, and RCU-sched),
  16 but only two flavors of expedited grace periods because the RCU-bh
  17 expedited grace period maps onto the RCU-sched expedited grace period.
  18 Each of the remaining two implementations is covered in its own section.
  19
  20 <ol>
  21 <li>    <a href="#Expedited Grace Period Design">
  22         Expedited Grace Period Design</a>
  23 <li>    <a href="#RCU-preempt Expedited Grace Periods">
  24         RCU-preempt Expedited Grace Periods</a>
  25 <li>    <a href="#RCU-sched Expedited Grace Periods">
  26         RCU-sched Expedited Grace Periods</a>
  27 <li>    <a href="#Expedited Grace Period and CPU Hotplug">
  28         Expedited Grace Period and CPU Hotplug</a>
  29 <li>    <a href="#Expedited Grace Period Refinements">
  30         Expedited Grace Period Refinements</a>
  31 </ol>
  32
  33 <h2><a name="Expedited Grace Period Design">
  34 Expedited Grace Period Design</a></h2>
  35
  36 <p>
  37 The expedited RCU grace periods cannot be accused of being subtle,
  38 given that they for all intents and purposes hammer every CPU that
  39 has not yet provided a quiescent state for the current expedited
  40 grace period.
  41 The one saving grace is that the hammer has grown a bit smaller
  42 over time:  The old call to <tt>try_stop_cpus()</tt> has been
  43 replaced with a set of calls to <tt>smp_call_function_single()</tt>,
  44 each of which results in an IPI to the target CPU.
  45 The corresponding handler function checks the CPU's state, motivating
  46 a faster quiescent state where possible, and triggering a report
  47 of that quiescent state.
  48 As always for RCU, once everything has spent some time in a quiescent
  49 state, the expedited grace period has completed.
  50
  51 <p>
  52 The details of the <tt>smp_call_function_single()</tt> handler's
  53 operation depend on the RCU flavor, as described in the following
  54 sections.
  55
  56 <h2><a name="RCU-preempt Expedited Grace Periods">
  57 RCU-preempt Expedited Grace Periods</a></h2>
  58
  59 <p>
  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:
  62
  63 <p><img src="ExpRCUFlow.svg" alt="ExpRCUFlow.svg" width="55%">
  64
  65 <p>
  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.
  69
  70 <p>
  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
  73 in quiescent states.
  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>sync_rcu_exp_handler()</tt>.
  77
  78 <p>
  79 However, because this is preemptible RCU, <tt>sync_rcu_exp_handler()</tt>
  80 can check to see if the CPU is currently running in an RCU read-side
  81 critical section.
  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.
  89
  90 <p>
  91 Again because this is preemptible RCU, an RCU read-side critical section
  92 can be preempted.
  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.
 103
 104 <table>
 105 <tr><th>&nbsp;</th></tr>
 106 <tr><th align="left">Quick Quiz:</th></tr>
 107 <tr><td>
 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.
 111 </td></tr>
 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
 117         other CPU.
 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.
 123
 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.
 130 </font></td></tr>
 131 <tr><td>&nbsp;</td></tr>
 132 </table>
 133
 134 <p>
 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.
 138
 139 <h2><a name="RCU-sched Expedited Grace Periods">
 140 RCU-sched Expedited Grace Periods</a></h2>
 141
 142 <p>
 143 The overall flow of the handling of a given CPU by an RCU-sched
 144 expedited grace period is shown in the following diagram:
 145
 146 <p><img src="ExpSchedFlow.svg" alt="ExpSchedFlow.svg" width="55%">
 147
 148 <p>
 149 As with RCU-preempt's <tt>synchronize_rcu_expedited()</tt>,
 150 <tt>synchronize_sched_expedited()</tt> ignores offline and
 151 idle CPUs, again because they are in remotely detectable
 152 quiescent states.
 153 However, the <tt>synchronize_rcu_expedited()</tt> handler
 154 is <tt>sync_sched_exp_handler()</tt>, and because the
 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 <tt>sync_sched_exp_handler()</tt> can do is to check
 159 for idle, on the off-chance that the CPU went idle while the IPI
 160 was in flight.
 161 If the CPU is idle, then tt>sync_sched_exp_handler()</tt> reports
 162 the quiescent state.
 163
 164 <p>
 165 Otherwise, the handler invokes <tt>resched_cpu()</tt>, which forces
 166 a future context switch.
 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
 169 at that time.
 170
 171 <h2><a name="Expedited Grace Period and CPU Hotplug">
 172 Expedited Grace Period and CPU Hotplug</a></h2>
 173
 174 <p>
 175 The expedited nature of expedited grace periods require a much tighter
 176 interaction with CPU hotplug operations than is required for normal
 177 grace periods.
 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.
 181
 182 <p>
 183 The interaction between expedited grace periods and CPU hotplug operations
 184 is carried out at several levels:
 185
 186 <ol>
 187 <li>    The number of CPUs that have ever been online is tracked
 188         by the <tt>rcu_state</tt> structure's <tt>-&gt;ncpus</tt>
 189         field.
 190         The <tt>rcu_state</tt> structure's <tt>-&gt;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
 194         of a time machine.
 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>-&gt;expmaskinitnext</tt> field.
 198         The <tt>rcu_node</tt> structure's <tt>-&gt;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>-&gt;ncpus</tt> and
 203         <tt>-&gt;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>-&gt;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>-&gt;expmaskinit</tt>
 209         field from its <tt>-&gt;expmaskinitnext</tt> field.
 210 <li>    Each <tt>rcu_node</tt> structure's <tt>-&gt;expmaskinit</tt>
 211         field is used to initialize that structure's
 212         <tt>-&gt;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>-&gt;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. <!-- @@@ -->
 234 </ol>
 235
 236 <table>
 237 <tr><th>&nbsp;</th></tr>
 238 <tr><th align="left">Quick Quiz:</th></tr>
 239 <tr><td>
 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?
 244 </td></tr>
 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
 255         grace-period hangs.
 256         In short, that way lies madness, to say nothing of a great many
 257         bugs, hangs, and deadlocks.
 258
 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.
 264
 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.
 272 </font></td></tr>
 273 <tr><td>&nbsp;</td></tr>
 274 </table>
 275
 276 <h2><a name="Expedited Grace Period Refinements">
 277 Expedited Grace Period Refinements</a></h2>
 278
 279 <ol>
 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>.
 288 </ol>
 289
 290 <h3><a name="Idle-CPU Checks">Idle-CPU Checks</a></h3>
 291
 292 <p>
 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
 297 not be IPIed.
 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>.
 300
 301 <p>
 302 For RCU-sched, there is an additional check for idle in the IPI
 303 handler, <tt>sync_sched_exp_handler()</tt>.
 304 If the IPI has interrupted the idle loop, then
 305 <tt>sync_sched_exp_handler()</tt> invokes <tt>rcu_report_exp_rdp()</tt>
 306 to report the corresponding quiescent state.
 307
 308 <p>
 309 For RCU-preempt, there is no specific check for idle in the
 310 IPI handler (<tt>sync_rcu_exp_handler()</tt>), but because
 311 RCU read-side critical sections are not permitted within the
 312 idle loop, if <tt>sync_rcu_exp_handler()</tt> sees that the CPU is within
 313 RCU read-side critical section, the CPU cannot possibly be idle.
 314 Otherwise, <tt>sync_rcu_exp_handler()</tt> invokes
 315 <tt>rcu_report_exp_rdp()</tt> to report the corresponding quiescent
 316 state, regardless of whether or not that quiescent state was due to
 317 the CPU being idle.
 318
 319 <p>
 320 In summary, RCU expedited grace periods check for idle when building
 321 the bitmask of CPUs that must be IPIed, just before sending each IPI,
 322 and (either explicitly or implicitly) within the IPI handler.
 323
 324 <h3><a name="Batching via Sequence Counter">
 325 Batching via Sequence Counter</a></h3>
 326
 327 <p>
 328 If each grace-period request was carried out separately, expedited
 329 grace periods would have abysmal scalability and
 330 problematic high-load characteristics.
 331 Because each grace-period operation can serve an unlimited number of
 332 updates, it is important to <i>batch</i> requests, so that a single
 333 expedited grace-period operation will cover all requests in the
 334 corresponding batch.
 335
 336 <p>
 337 This batching is controlled by a sequence counter named
 338 <tt>-&gt;expedited_sequence</tt> in the <tt>rcu_state</tt> structure.
 339 This counter has an odd value when there is an expedited grace period
 340 in progress and an even value otherwise, so that dividing the counter
 341 value by two gives the number of completed grace periods.
 342 During any given update request, the counter must transition from
 343 even to odd and then back to even, thus indicating that a grace
 344 period has elapsed.
 345 Therefore, if the initial value of the counter is <tt>s</tt>,
 346 the updater must wait until the counter reaches at least the
 347 value <tt>(s+3)&amp;~0x1</tt>.
 348 This counter is managed by the following access functions:
 349
 350 <ol>
 351 <li>    <tt>rcu_exp_gp_seq_start()</tt>, which marks the start of
 352         an expedited grace period.
 353 <li>    <tt>rcu_exp_gp_seq_end()</tt>, which marks the end of an
 354         expedited grace period.
 355 <li>    <tt>rcu_exp_gp_seq_snap()</tt>, which obtains a snapshot of
 356         the counter.
 357 <li>    <tt>rcu_exp_gp_seq_done()</tt>, which returns <tt>true</tt>
 358         if a full expedited grace period has elapsed since the
 359         corresponding call to <tt>rcu_exp_gp_seq_snap()</tt>.
 360 </ol>
 361
 362 <p>
 363 Again, only one request in a given batch need actually carry out
 364 a grace-period operation, which means there must be an efficient
 365 way to identify which of many concurrent reqeusts will initiate
 366 the grace period, and that there be an efficient way for the
 367 remaining requests to wait for that grace period to complete.
 368 However, that is the topic of the next section.
 369
 370 <h3><a name="Funnel Locking and Wait/Wakeup">
 371 Funnel Locking and Wait/Wakeup</a></h3>
 372
 373 <p>
 374 The natural way to sort out which of a batch of updaters will initiate
 375 the expedited grace period is to use the <tt>rcu_node</tt> combining
 376 tree, as implemented by the <tt>exp_funnel_lock()</tt> function.
 377 The first updater corresponding to a given grace period arriving
 378 at a given <tt>rcu_node</tt> structure records its desired grace-period
 379 sequence number in the <tt>-&gt;exp_seq_rq</tt> field and moves up
 380 to the next level in the tree.
 381 Otherwise, if the <tt>-&gt;exp_seq_rq</tt> field already contains
 382 the sequence number for the desired grace period or some later one,
 383 the updater blocks on one of four wait queues in the
 384 <tt>-&gt;exp_wq[]</tt> array, using the second-from-bottom
 385 and third-from bottom bits as an index.
 386 An <tt>-&gt;exp_lock</tt> field in the <tt>rcu_node</tt> structure
 387 synchronizes access to these fields.
 388
 389 <p>
 390 An empty <tt>rcu_node</tt> tree is shown in the following diagram,
 391 with the white cells representing the <tt>-&gt;exp_seq_rq</tt> field
 392 and the red cells representing the elements of the
 393 <tt>-&gt;exp_wq[]</tt> array.
 394
 395 <p><img src="Funnel0.svg" alt="Funnel0.svg" width="75%">
 396
 397 <p>
 398 The next diagram shows the situation after the arrival of Task&nbsp;A
 399 and Task&nbsp;B at the leftmost and rightmost leaf <tt>rcu_node</tt>
 400 structures, respectively.
 401 The current value of the <tt>rcu_state</tt> structure's
 402 <tt>-&gt;expedited_sequence</tt> field is zero, so adding three and
 403 clearing the bottom bit results in the value two, which both tasks
 404 record in the <tt>-&gt;exp_seq_rq</tt> field of their respective
 405 <tt>rcu_node</tt> structures:
 406
 407 <p><img src="Funnel1.svg" alt="Funnel1.svg" width="75%">
 408
 409 <p>
 410 Each of Tasks&nbsp;A and&nbsp;B will move up to the root
 411 <tt>rcu_node</tt> structure.
 412 Suppose that Task&nbsp;A wins, recording its desired grace-period sequence
 413 number and resulting in the state shown below:
 414
 415 <p><img src="Funnel2.svg" alt="Funnel2.svg" width="75%">
 416
 417 <p>
 418 Task&nbsp;A now advances to initiate a new grace period, while Task&nbsp;B
 419 moves up to the root <tt>rcu_node</tt> structure, and, seeing that
 420 its desired sequence number is already recorded, blocks on
 421 <tt>-&gt;exp_wq[1]</tt>.
 422
 423 <table>
 424 <tr><th>&nbsp;</th></tr>
 425 <tr><th align="left">Quick Quiz:</th></tr>
 426 <tr><td>
 427         Why <tt>-&gt;exp_wq[1]</tt>?
 428         Given that the value of these tasks' desired sequence number is
 429         two, so shouldn't they instead block on <tt>-&gt;exp_wq[2]</tt>?
 430 </td></tr>
 431 <tr><th align="left">Answer:</th></tr>
 432 <tr><td bgcolor="#ffffff"><font color="ffffff">
 433         No.
 434
 435         <p><font color="ffffff">
 436         Recall that the bottom bit of the desired sequence number indicates
 437         whether or not a grace period is currently in progress.
 438         It is therefore necessary to shift the sequence number right one
 439         bit position to obtain the number of the grace period.
 440         This results in <tt>-&gt;exp_wq[1]</tt>.
 441 </font></td></tr>
 442 <tr><td>&nbsp;</td></tr>
 443 </table>
 444
 445 <p>
 446 If Tasks&nbsp;C and&nbsp;D also arrive at this point, they will compute the
 447 same desired grace-period sequence number, and see that both leaf
 448 <tt>rcu_node</tt> structures already have that value recorded.
 449 They will therefore block on their respective <tt>rcu_node</tt>
 450 structures' <tt>-&gt;exp_wq[1]</tt> fields, as shown below:
 451
 452 <p><img src="Funnel3.svg" alt="Funnel3.svg" width="75%">
 453
 454 <p>
 455 Task&nbsp;A now acquires the <tt>rcu_state</tt> structure's
 456 <tt>-&gt;exp_mutex</tt> and initiates the grace period, which
 457 increments <tt>-&gt;expedited_sequence</tt>.
 458 Therefore, if Tasks&nbsp;E and&nbsp;F arrive, they will compute
 459 a desired sequence number of 4 and will record this value as
 460 shown below:
 461
 462 <p><img src="Funnel4.svg" alt="Funnel4.svg" width="75%">
 463
 464 <p>
 465 Tasks&nbsp;E and&nbsp;F will propagate up the <tt>rcu_node</tt>
 466 combining tree, with Task&nbsp;F blocking on the root <tt>rcu_node</tt>
 467 structure and Task&nbsp;E wait for Task&nbsp;A to finish so that
 468 it can start the next grace period.
 469 The resulting state is as shown below:
 470
 471 <p><img src="Funnel5.svg" alt="Funnel5.svg" width="75%">
 472
 473 <p>
 474 Once the grace period completes, Task&nbsp;A
 475 starts waking up the tasks waiting for this grace period to complete,
 476 increments the <tt>-&gt;expedited_sequence</tt>,
 477 acquires the <tt>-&gt;exp_wake_mutex</tt> and then releases the
 478 <tt>-&gt;exp_mutex</tt>.
 479 This results in the following state:
 480
 481 <p><img src="Funnel6.svg" alt="Funnel6.svg" width="75%">
 482
 483 <p>
 484 Task&nbsp;E can then acquire <tt>-&gt;exp_mutex</tt> and increment
 485 <tt>-&gt;expedited_sequence</tt> to the value three.
 486 If new tasks&nbsp;G and&nbsp;H arrive and moves up the combining tree at the
 487 same time, the state will be as follows:
 488
 489 <p><img src="Funnel7.svg" alt="Funnel7.svg" width="75%">
 490
 491 <p>
 492 Note that three of the root <tt>rcu_node</tt> structure's
 493 waitqueues are now occupied.
 494 However, at some point, Task&nbsp;A will wake up the
 495 tasks blocked on the <tt>-&gt;exp_wq</tt> waitqueues, resulting
 496 in the following state:
 497
 498 <p><img src="Funnel8.svg" alt="Funnel8.svg" width="75%">
 499
 500 <p>
 501 Execution will continue with Tasks&nbsp;E and&nbsp;H completing
 502 their grace periods and carrying out their wakeups.
 503
 504 <table>
 505 <tr><th>&nbsp;</th></tr>
 506 <tr><th align="left">Quick Quiz:</th></tr>
 507 <tr><td>
 508         What happens if Task&nbsp;A takes so long to do its wakeups
 509         that Task&nbsp;E's grace period completes?
 510 </td></tr>
 511 <tr><th align="left">Answer:</th></tr>
 512 <tr><td bgcolor="#ffffff"><font color="ffffff">
 513         Then Task&nbsp;E will block on the <tt>-&gt;exp_wake_mutex</tt>,
 514         which will also prevent it from releasing <tt>-&gt;exp_mutex</tt>,
 515         which in turn will prevent the next grace period from starting.
 516         This last is important in preventing overflow of the
 517         <tt>-&gt;exp_wq[]</tt> array.
 518 </font></td></tr>
 519 <tr><td>&nbsp;</td></tr>
 520 </table>
 521
 522 <h3><a name="Use of Workqueues">Use of Workqueues</a></h3>
 523
 524 <p>
 525 In earlier implementations, the task requesting the expedited
 526 grace period also drove it to completion.
 527 This straightforward approach had the disadvantage of needing to
 528 account for POSIX signals sent to user tasks,
 529 so more recent implemementations use the Linux kernel's
 530 <a href="https://www.kernel.org/doc/Documentation/core-api/workqueue.rst">workqueues</a>.
 531
 532 <p>
 533 The requesting task still does counter snapshotting and funnel-lock
 534 processing, but the task reaching the top of the funnel lock
 535 does a <tt>schedule_work()</tt> (from <tt>_synchronize_rcu_expedited()</tt>
 536 so that a workqueue kthread does the actual grace-period processing.
 537 Because workqueue kthreads do not accept POSIX signals, grace-period-wait
 538 processing need not allow for POSIX signals.
 539
 540 In addition, this approach allows wakeups for the previous expedited
 541 grace period to be overlapped with processing for the next expedited
 542 grace period.
 543 Because there are only four sets of waitqueues, it is necessary to
 544 ensure that the previous grace period's wakeups complete before the
 545 next grace period's wakeups start.
 546 This is handled by having the <tt>-&gt;exp_mutex</tt>
 547 guard expedited grace-period processing and the
 548 <tt>-&gt;exp_wake_mutex</tt> guard wakeups.
 549 The key point is that the <tt>-&gt;exp_mutex</tt> is not released
 550 until the first wakeup is complete, which means that the
 551 <tt>-&gt;exp_wake_mutex</tt> has already been acquired at that point.
 552 This approach ensures that the previous grace period's wakeups can
 553 be carried out while the current grace period is in process, but
 554 that these wakeups will complete before the next grace period starts.
 555 This means that only three waitqueues are required, guaranteeing that
 556 the four that are provided are sufficient.
 557
 558 <h3><a name="Stall Warnings">Stall Warnings</a></h3>
 559
 560 <p>
 561 Expediting grace periods does nothing to speed things up when RCU
 562 readers take too long, and therefore expedited grace periods check
 563 for stalls just as normal grace periods do.
 564
 565 <table>
 566 <tr><th>&nbsp;</th></tr>
 567 <tr><th align="left">Quick Quiz:</th></tr>
 568 <tr><td>
 569         But why not just let the normal grace-period machinery
 570         detect the stalls, given that a given reader must block
 571         both normal and expedited grace periods?
 572 </td></tr>
 573 <tr><th align="left">Answer:</th></tr>
 574 <tr><td bgcolor="#ffffff"><font color="ffffff">
 575         Because it is quite possible that at a given time there
 576         is no normal grace period in progress, in which case the
 577         normal grace period cannot emit a stall warning.
 578 </font></td></tr>
 579 <tr><td>&nbsp;</td></tr>
 580 </table>
 581
 582 The <tt>synchronize_sched_expedited_wait()</tt> function loops waiting
 583 for the expedited grace period to end, but with a timeout set to the
 584 current RCU CPU stall-warning time.
 585 If this time is exceeded, any CPUs or <tt>rcu_node</tt> structures
 586 blocking the current grace period are printed.
 587 Each stall warning results in another pass through the loop, but the
 588 second and subsequent passes use longer stall times.
 589
 590 <h3><a name="Mid-Boot Operation">Mid-boot operation</a></h3>
 591
 592 <p>
 593 The use of workqueues has the advantage that the expedited
 594 grace-period code need not worry about POSIX signals.
 595 Unfortunately, it has the
 596 corresponding disadvantage that workqueues cannot be used until
 597 they are initialized, which does not happen until some time after
 598 the scheduler spawns the first task.
 599 Given that there are parts of the kernel that really do want to
 600 execute grace periods during this mid-boot &ldquo;dead zone&rdquo;,
 601 expedited grace periods must do something else during thie time.
 602
 603 <p>
 604 What they do is to fall back to the old practice of requiring that the
 605 requesting task drive the expedited grace period, as was the case
 606 before the use of workqueues.
 607 However, the requesting task is only required to drive the grace period
 608 during the mid-boot dead zone.
 609 Before mid-boot, a synchronous grace period is a no-op.
 610 Some time after mid-boot, workqueues are used.
 611
 612 <p>
 613 Non-expedited non-SRCU synchronous grace periods must also operate
 614 normally during mid-boot.
 615 This is handled by causing non-expedited grace periods to take the
 616 expedited code path during mid-boot.
 617
 618 <p>
 619 The current code assumes that there are no POSIX signals during
 620 the mid-boot dead zone.
 621 However, if an overwhelming need for POSIX signals somehow arises,
 622 appropriate adjustments can be made to the expedited stall-warning code.
 623 One such adjustment would reinstate the pre-workqueue stall-warning
 624 checks, but only during the mid-boot dead zone.
 625
 626 <p>
 627 With this refinement, synchronous grace periods can now be used from
 628 task context pretty much any time during the life of the kernel.
 629
 630 <h3><a name="Summary">
 631 Summary</a></h3>
 632
 633 <p>
 634 Expedited grace periods use a sequence-number approach to promote
 635 batching, so that a single grace-period operation can serve numerous
 636 requests.
 637 A funnel lock is used to efficiently identify the one task out of
 638 a concurrent group that will request the grace period.
 639 All members of the group will block on waitqueues provided in
 640 the <tt>rcu_node</tt> structure.
 641 The actual grace-period processing is carried out by a workqueue.
 642
 643 <p>
 644 CPU-hotplug operations are noted lazily in order to prevent the need
 645 for tight synchronization between expedited grace periods and
 646 CPU-hotplug operations.
 647 The dyntick-idle counters are used to avoid sending IPIs to idle CPUs,
 648 at least in the common case.
 649 RCU-preempt and RCU-sched use different IPI handlers and different
 650 code to respond to the state changes carried out by those handlers,
 651 but otherwise use common code.
 652
 653 <p>
 654 Quiescent states are tracked using the <tt>rcu_node</tt> tree,
 655 and once all necessary quiescent states have been reported,
 656 all tasks waiting on this expedited grace period are awakened.
 657 A pair of mutexes are used to allow one grace period's wakeups
 658 to proceed concurrently with the next grace period's processing.
 659
 660 <p>
 661 This combination of mechanisms allows expedited grace periods to
 662 run reasonably efficiently.
 663 However, for non-time-critical tasks, normal grace periods should be
 664 used instead because their longer duration permits much higher
 665 degrees of batching, and thus much lower per-request overheads.
 666
 667 </body></html>