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