sphinx.addnodesdocument)}( rawsourcechildren]( translations LanguagesNode)}(hhh](h pending_xref)}(hhh]docutils.nodesTextChinese (Simplified)}parenthsba attributes}(ids]classes]names]dupnames]backrefs] refdomainstdreftypedoc reftargetN/translations/zh_CN/RCU/Design/Expedited-Grace-Periods/Expedited-Grace-PeriodsmodnameN classnameN refexplicitutagnamehhh ubh)}(hhh]hChinese (Traditional)}hh2sbah}(h]h ]h"]h$]h&] refdomainh)reftypeh+ reftargetN/translations/zh_TW/RCU/Design/Expedited-Grace-Periods/Expedited-Grace-PeriodsmodnameN classnameN refexplicituh1hhh ubh)}(hhh]hItalian}hhFsbah}(h]h ]h"]h$]h&] refdomainh)reftypeh+ reftargetN/translations/it_IT/RCU/Design/Expedited-Grace-Periods/Expedited-Grace-PeriodsmodnameN classnameN refexplicituh1hhh ubh)}(hhh]hJapanese}hhZsbah}(h]h ]h"]h$]h&] refdomainh)reftypeh+ reftargetN/translations/ja_JP/RCU/Design/Expedited-Grace-Periods/Expedited-Grace-PeriodsmodnameN classnameN refexplicituh1hhh ubh)}(hhh]hKorean}hhnsbah}(h]h ]h"]h$]h&] refdomainh)reftypeh+ reftargetN/translations/ko_KR/RCU/Design/Expedited-Grace-Periods/Expedited-Grace-PeriodsmodnameN classnameN refexplicituh1hhh ubh)}(hhh]hSpanish}hhsbah}(h]h ]h"]h$]h&] refdomainh)reftypeh+ reftargetN/translations/sp_SP/RCU/Design/Expedited-Grace-Periods/Expedited-Grace-PeriodsmodnameN classnameN refexplicituh1hhh ubeh}(h]h ]h"]h$]h&]current_languageEnglishuh1h hh _documenthsourceNlineNubhsection)}(hhh](htitle)}(h1A Tour Through TREE_RCU's Expedited Grace Periodsh]h3A Tour Through TREE_RCU’s Expedited Grace Periods}(hhhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhhhh/var/lib/git/docbuild/linux/Documentation/RCU/Design/Expedited-Grace-Periods/Expedited-Grace-Periods.rsthKubh)}(hhh](h)}(h Introductionh]h Introduction}(hhhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhhhhhKubh paragraph)}(hXThis document describes RCU's expedited grace periods. Unlike RCU's normal grace periods, which accept long latencies to attain high efficiency and minimal disturbance, expedited grace periods accept lower efficiency and significant disturbance to attain shorter latencies.h]hXThis document describes RCU’s expedited grace periods. Unlike RCU’s normal grace periods, which accept long latencies to attain high efficiency and minimal disturbance, expedited grace periods accept lower efficiency and significant disturbance to attain shorter latencies.}(hhhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhhhhubh)}(hThere are two flavors of RCU (RCU-preempt and RCU-sched), with an earlier third RCU-bh flavor having been implemented in terms of the other two. Each of the two implementations is covered in its own section.h]hThere are two flavors of RCU (RCU-preempt and RCU-sched), with an earlier third RCU-bh flavor having been implemented in terms of the other two. Each of the two implementations is covered in its own section.}(hhhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK hhhhubeh}(h] introductionah ]h"] introductionah$]h&]uh1hhhhhhhhKubh)}(hhh](h)}(hExpedited Grace Period Designh]hExpedited Grace Period Design}(hhhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhhhhhKubh)}(hXThe expedited RCU grace periods cannot be accused of being subtle, given that they for all intents and purposes hammer every CPU that has not yet provided a quiescent state for the current expedited grace period. The one saving grace is that the hammer has grown a bit smaller over time: The old call to ``try_stop_cpus()`` has been replaced with a set of calls to ``smp_call_function_single()``, each of which results in an IPI to the target CPU. The corresponding handler function checks the CPU's state, motivating a faster quiescent state where possible, and triggering a report of that quiescent state. As always for RCU, once everything has spent some time in a quiescent state, the expedited grace period has completed.h](hX1The expedited RCU grace periods cannot be accused of being subtle, given that they for all intents and purposes hammer every CPU that has not yet provided a quiescent state for the current expedited grace period. The one saving grace is that the hammer has grown a bit smaller over time: The old call to }(hhhhhNhNubhliteral)}(h``try_stop_cpus()``h]htry_stop_cpus()}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jhhubh* has been replaced with a set of calls to }(hhhhhNhNubj)}(h``smp_call_function_single()``h]hsmp_call_function_single()}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhhubhXM, each of which results in an IPI to the target CPU. The corresponding handler function checks the CPU’s state, motivating a faster quiescent state where possible, and triggering a report of that quiescent state. As always for RCU, once everything has spent some time in a quiescent state, the expedited grace period has completed.}(hhhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKhhhhubh)}(hThe details of the ``smp_call_function_single()`` handler's operation depend on the RCU flavor, as described in the following sections.h](hThe details of the }(hj3hhhNhNubj)}(h``smp_call_function_single()``h]hsmp_call_function_single()}(hj;hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj3ubhX handler’s operation depend on the RCU flavor, as described in the following sections.}(hj3hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhK"hhhhubeh}(h]expedited-grace-period-designah ]h"]expedited grace period designah$]h&]uh1hhhhhhhhKubh)}(hhh](h)}(h#RCU-preempt Expedited Grace Periodsh]h#RCU-preempt Expedited Grace Periods}(hj^hhhNhNubah}(h]h ]h"]h$]h&]uh1hhj[hhhhhK'ubh)}(h``CONFIG_PREEMPTION=y`` kernels implement RCU-preempt. The overall flow of the handling of a given CPU by an RCU-preempt expedited grace period is shown in the following diagram:h](j)}(h``CONFIG_PREEMPTION=y``h]hCONFIG_PREEMPTION=y}(hjphhhNhNubah}(h]h ]h"]h$]h&]uh1jhjlubh kernels implement RCU-preempt. The overall flow of the handling of a given CPU by an RCU-preempt expedited grace period is shown in the following diagram:}(hjlhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhK)hj[hhubkfigure kernel_figure)}(hhh]hfigure)}(hhh]himage)}(h".. kernel-figure:: ExpRCUFlow.svg h]h}(h]h ]h"]h$]h&]uri1RCU/Design/Expedited-Grace-Periods/ExpRCUFlow.svg candidates}*jsuh1jhjhhhKubah}(h]h ]h"]h$]h&]uh1jhjubah}(h]h ]h"]h$]h&]uh1jhj[hhhhhK.ubh)}(hThe solid arrows denote direct action, for example, a function call. The dotted arrows denote indirect action, for example, an IPI or a state that is reached after some time.h]hThe solid arrows denote direct action, for example, a function call. The dotted arrows denote indirect action, for example, an IPI or a state that is reached after some time.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK/hj[hhubh)}(hX*If a given CPU is offline or idle, ``synchronize_rcu_expedited()`` will ignore it because idle and offline CPUs are already residing in quiescent states. Otherwise, the expedited grace period will use ``smp_call_function_single()`` to send the CPU an IPI, which is handled by ``rcu_exp_handler()``.h](h#If a given CPU is offline or idle, }(hjhhhNhNubj)}(h``synchronize_rcu_expedited()``h]hsynchronize_rcu_expedited()}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh will ignore it because idle and offline CPUs are already residing in quiescent states. Otherwise, the expedited grace period will use }(hjhhhNhNubj)}(h``smp_call_function_single()``h]hsmp_call_function_single()}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh- to send the CPU an IPI, which is handled by }(hjhhhNhNubj)}(h``rcu_exp_handler()``h]hrcu_exp_handler()}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh.}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhK3hj[hhubh)}(hXJHowever, because this is preemptible RCU, ``rcu_exp_handler()`` can check to see if the CPU is currently running in an RCU read-side critical section. If not, the handler can immediately report a quiescent state. Otherwise, it sets flags so that the outermost ``rcu_read_unlock()`` invocation will provide the needed quiescent-state report. This flag-setting avoids the previous forced preemption of all CPUs that might have RCU read-side critical sections. In addition, this flag-setting is done so as to avoid increasing the overhead of the common-case fastpath through the scheduler.h](h*However, because this is preemptible RCU, }(hjhhhNhNubj)}(h``rcu_exp_handler()``h]hrcu_exp_handler()}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh can check to see if the CPU is currently running in an RCU read-side critical section. If not, the handler can immediately report a quiescent state. Otherwise, it sets flags so that the outermost }(hjhhhNhNubj)}(h``rcu_read_unlock()``h]hrcu_read_unlock()}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubhX1 invocation will provide the needed quiescent-state report. This flag-setting avoids the previous forced preemption of all CPUs that might have RCU read-side critical sections. In addition, this flag-setting is done so as to avoid increasing the overhead of the common-case fastpath through the scheduler.}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhK:hj[hhubh)}(hXAgain because this is preemptible RCU, an RCU read-side critical section can be preempted. When that happens, RCU will enqueue the task, which will the continue to block the current expedited grace period until it resumes and finds its outermost ``rcu_read_unlock()``. The CPU will report a quiescent state just after enqueuing the task because the CPU is no longer blocking the grace period. It is instead the preempted task doing the blocking. The list of blocked tasks is managed by ``rcu_preempt_ctxt_queue()``, which is called from ``rcu_preempt_note_context_switch()``, which in turn is called from ``rcu_note_context_switch()``, which in turn is called from the scheduler.h](hAgain because this is preemptible RCU, an RCU read-side critical section can be preempted. When that happens, RCU will enqueue the task, which will the continue to block the current expedited grace period until it resumes and finds its outermost }(hj4hhhNhNubj)}(h``rcu_read_unlock()``h]hrcu_read_unlock()}(hj<hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj4ubh. The CPU will report a quiescent state just after enqueuing the task because the CPU is no longer blocking the grace period. It is instead the preempted task doing the blocking. The list of blocked tasks is managed by }(hj4hhhNhNubj)}(h``rcu_preempt_ctxt_queue()``h]hrcu_preempt_ctxt_queue()}(hjNhhhNhNubah}(h]h ]h"]h$]h&]uh1jhj4ubh, which is called from }(hj4hhhNhNubj)}(h%``rcu_preempt_note_context_switch()``h]h!rcu_preempt_note_context_switch()}(hj`hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj4ubh, which in turn is called from }(hj4hhhNhNubj)}(h``rcu_note_context_switch()``h]hrcu_note_context_switch()}(hjrhhhNhNubah}(h]h ]h"]h$]h&]uh1jhj4ubh-, which in turn is called from the scheduler.}(hj4hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKEhj[hhubhtable)}(hhh]htgroup)}(hhh](hcolspec)}(hhh]h}(h]h ]h"]h$]h&]colwidthKGuh1jhjubhtbody)}(hhh](hrow)}(hhh]hentry)}(hhh]h)}(h**Quick Quiz**:h](hstrong)}(h**Quick Quiz**h]h Quick Quiz}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh:}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKThjubah}(h]h ]h"]h$]h&]uh1jhjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]j)}(hhh]h)}(hWhy not just have the expedited grace period check the state of all the CPUs? After all, that would avoid all those real-time-unfriendly IPIs.h]hWhy not just have the expedited grace period check the state of all the CPUs? After all, that would avoid all those real-time-unfriendly IPIs.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKVhjubah}(h]h ]h"]h$]h&]uh1jhjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]j)}(hhh]h)}(h **Answer**:h](j)}(h **Answer**h]hAnswer}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh:}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKZhjubah}(h]h ]h"]h$]h&]uh1jhjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]j)}(hhh](h)}(hXBecause we want the RCU read-side critical sections to run fast, which means no memory barriers. Therefore, it is not possible to safely check the state from some other CPU. And even if it was possible to safely check the state, it would still be necessary to IPI the CPU to safely interact with the upcoming ``rcu_read_unlock()`` invocation, which means that the remote state testing would not help the worst-case latency that real-time applications care about.h](hX5Because we want the RCU read-side critical sections to run fast, which means no memory barriers. Therefore, it is not possible to safely check the state from some other CPU. And even if it was possible to safely check the state, it would still be necessary to IPI the CPU to safely interact with the upcoming }(hj-hhhNhNubj)}(h``rcu_read_unlock()``h]hrcu_read_unlock()}(hj5hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj-ubh invocation, which means that the remote state testing would not help the worst-case latency that real-time applications care about.}(hj-hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhK\hj*ubh)}(hXOne way to prevent your real-time application from getting hit with these IPIs is to build your kernel with ``CONFIG_NO_HZ_FULL=y``. RCU would then perceive the CPU running your application as being idle, and it would be able to safely detect that state without needing to IPI the CPU.h](hlOne way to prevent your real-time application from getting hit with these IPIs is to build your kernel with }(hjMhhhNhNubj)}(h``CONFIG_NO_HZ_FULL=y``h]hCONFIG_NO_HZ_FULL=y}(hjUhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjMubh. RCU would then perceive the CPU running your application as being idle, and it would be able to safely detect that state without needing to IPI the CPU.}(hjMhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKehj*ubeh}(h]h ]h"]h$]h&]uh1jhj'ubah}(h]h ]h"]h$]h&]uh1jhjubeh}(h]h ]h"]h$]h&]uh1jhjubeh}(h]h ]h"]h$]h&]colsKuh1jhjubah}(h]h ]h"]h$]h&]uh1jhj[hhhhhNubh)}(hPlease note that this is just the overall flow: Additional complications can arise due to races with CPUs going idle or offline, among other things.h]hPlease note that this is just the overall flow: Additional complications can arise due to races with CPUs going idle or offline, among other things.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKlhj[hhubh)}(hhh](h)}(h!RCU-sched Expedited Grace Periodsh]h!RCU-sched Expedited Grace Periods}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjhhhhhKqubh)}(h``CONFIG_PREEMPTION=n`` kernels implement RCU-sched. The overall flow of the handling of a given CPU by an RCU-sched expedited grace period is shown in the following diagram:h](j)}(h``CONFIG_PREEMPTION=n``h]hCONFIG_PREEMPTION=n}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh kernels implement RCU-sched. The overall flow of the handling of a given CPU by an RCU-sched expedited grace period is shown in the following diagram:}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKshjhhubj)}(hhh]j)}(hhh]j)}(h$.. kernel-figure:: ExpSchedFlow.svg h]h}(h]h ]h"]h$]h&]uri3RCU/Design/Expedited-Grace-Periods/ExpSchedFlow.svgj}jjsuh1jhjhhhKubah}(h]h ]h"]h$]h&]uh1jhjubah}(h]h ]h"]h$]h&]uh1jhjhhhhhKxubh)}(hX_As with RCU-preempt, RCU-sched's ``synchronize_rcu_expedited()`` ignores offline and idle CPUs, again because they are in remotely detectable quiescent states. However, because the ``rcu_read_lock_sched()`` and ``rcu_read_unlock_sched()`` leave no trace of their invocation, in general it is not possible to tell whether or not the current CPU is in an RCU read-side critical section. The best that RCU-sched's ``rcu_exp_handler()`` can do is to check for idle, on the off-chance that the CPU went idle while the IPI was in flight. If the CPU is idle, then ``rcu_exp_handler()`` reports the quiescent state.h](h#As with RCU-preempt, RCU-sched’s }(hjhhhNhNubj)}(h``synchronize_rcu_expedited()``h]hsynchronize_rcu_expedited()}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubhu ignores offline and idle CPUs, again because they are in remotely detectable quiescent states. However, because the }(hjhhhNhNubj)}(h``rcu_read_lock_sched()``h]hrcu_read_lock_sched()}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh and }(hjhhhNhNubj)}(h``rcu_read_unlock_sched()``h]hrcu_read_unlock_sched()}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh leave no trace of their invocation, in general it is not possible to tell whether or not the current CPU is in an RCU read-side critical section. The best that RCU-sched’s }(hjhhhNhNubj)}(h``rcu_exp_handler()``h]hrcu_exp_handler()}(hj$hhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh} can do is to check for idle, on the off-chance that the CPU went idle while the IPI was in flight. If the CPU is idle, then }(hjhhhNhNubj)}(h``rcu_exp_handler()``h]hrcu_exp_handler()}(hj6hhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh reports the quiescent state.}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKyhjhhubh)}(hX/Otherwise, the handler forces a future context switch by setting the NEED_RESCHED flag of the current task's thread flag and the CPU preempt counter. At the time of the context switch, the CPU reports the quiescent state. Should the CPU go offline first, it will report the quiescent state at that time.h]hX1Otherwise, the handler forces a future context switch by setting the NEED_RESCHED flag of the current task’s thread flag and the CPU preempt counter. At the time of the context switch, the CPU reports the quiescent state. Should the CPU go offline first, it will report the quiescent state at that time.}(hjNhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubeh}(h]!rcu-sched-expedited-grace-periodsah ]h"]!rcu-sched expedited grace periodsah$]h&]uh1hhj[hhhhhKqubh)}(hhh](h)}(h&Expedited Grace Period and CPU Hotplugh]h&Expedited Grace Period and CPU Hotplug}(hjghhhNhNubah}(h]h ]h"]h$]h&]uh1hhjdhhhhhKubh)}(hXVThe expedited nature of expedited grace periods require a much tighter interaction with CPU hotplug operations than is required for normal grace periods. In addition, attempting to IPI offline CPUs will result in splats, but failing to IPI online CPUs can result in too-short grace periods. Neither option is acceptable in production kernels.h]hXVThe expedited nature of expedited grace periods require a much tighter interaction with CPU hotplug operations than is required for normal grace periods. In addition, attempting to IPI offline CPUs will result in splats, but failing to IPI online CPUs can result in too-short grace periods. Neither option is acceptable in production kernels.}(hjuhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjdhhubh)}(hlThe interaction between expedited grace periods and CPU hotplug operations is carried out at several levels:h]hlThe interaction between expedited grace periods and CPU hotplug operations is carried out at several levels:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjdhhubhenumerated_list)}(hhh](h list_item)}(hX[The number of CPUs that have ever been online is tracked by the ``rcu_state`` structure's ``->ncpus`` field. The ``rcu_state`` structure's ``->ncpus_snap`` field tracks the number of CPUs that have ever been online at the beginning of an RCU expedited grace period. Note that this number never decreases, at least in the absence of a time machine.h]h)}(hX[The number of CPUs that have ever been online is tracked by the ``rcu_state`` structure's ``->ncpus`` field. The ``rcu_state`` structure's ``->ncpus_snap`` field tracks the number of CPUs that have ever been online at the beginning of an RCU expedited grace period. Note that this number never decreases, at least in the absence of a time machine.h](h@The number of CPUs that have ever been online is tracked by the }(hjhhhNhNubj)}(h ``rcu_state``h]h rcu_state}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh structure’s }(hjhhhNhNubj)}(h ``->ncpus``h]h->ncpus}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh field. The }(hjhhhNhNubj)}(h ``rcu_state``h]h rcu_state}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh structure’s }(hjhhhNhNubj)}(h``->ncpus_snap``h]h ->ncpus_snap}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh field tracks the number of CPUs that have ever been online at the beginning of an RCU expedited grace period. Note that this number never decreases, at least in the absence of a time machine.}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKhjubah}(h]h ]h"]h$]h&]uh1jhjhhhhhNubj)}(hXThe identities of the CPUs that have ever been online is tracked by the ``rcu_node`` structure's ``->expmaskinitnext`` field. The ``rcu_node`` structure's ``->expmaskinit`` field tracks the identities of the CPUs that were online at least once at the beginning of the most recent RCU expedited grace period. The ``rcu_state`` structure's ``->ncpus`` and ``->ncpus_snap`` fields are used to detect when new CPUs have come online for the first time, that is, when the ``rcu_node`` structure's ``->expmaskinitnext`` field has changed since the beginning of the last RCU expedited grace period, which triggers an update of each ``rcu_node`` structure's ``->expmaskinit`` field from its ``->expmaskinitnext`` field.h]h)}(hXThe identities of the CPUs that have ever been online is tracked by the ``rcu_node`` structure's ``->expmaskinitnext`` field. The ``rcu_node`` structure's ``->expmaskinit`` field tracks the identities of the CPUs that were online at least once at the beginning of the most recent RCU expedited grace period. The ``rcu_state`` structure's ``->ncpus`` and ``->ncpus_snap`` fields are used to detect when new CPUs have come online for the first time, that is, when the ``rcu_node`` structure's ``->expmaskinitnext`` field has changed since the beginning of the last RCU expedited grace period, which triggers an update of each ``rcu_node`` structure's ``->expmaskinit`` field from its ``->expmaskinitnext`` field.h](hHThe identities of the CPUs that have ever been online is tracked by the }(hjhhhNhNubj)}(h ``rcu_node``h]hrcu_node}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh structure’s }(hjhhhNhNubj)}(h``->expmaskinitnext``h]h->expmaskinitnext}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh field. The }(hjhhhNhNubj)}(h ``rcu_node``h]hrcu_node}(hj(hhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh structure’s }(hjhhhNhNubj)}(h``->expmaskinit``h]h ->expmaskinit}(hj:hhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh field tracks the identities of the CPUs that were online at least once at the beginning of the most recent RCU expedited grace period. The }(hjhhhNhNubj)}(h ``rcu_state``h]h rcu_state}(hjLhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh structure’s }(hjhhhNhNubj)}(h ``->ncpus``h]h->ncpus}(hj^hhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh and }(hjhhhNhNubj)}(h``->ncpus_snap``h]h ->ncpus_snap}(hjphhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh` fields are used to detect when new CPUs have come online for the first time, that is, when the }(hjhhhNhNubj)}(h ``rcu_node``h]hrcu_node}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh structure’s }(hjhhhNhNubj)}(h``->expmaskinitnext``h]h->expmaskinitnext}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubhp field has changed since the beginning of the last RCU expedited grace period, which triggers an update of each }(hjhhhNhNubj)}(h ``rcu_node``h]hrcu_node}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh structure’s }(hjhhhNhNubj)}(h``->expmaskinit``h]h ->expmaskinit}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh field from its }(hjhhhNhNubj)}(h``->expmaskinitnext``h]h->expmaskinitnext}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh field.}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKhjubah}(h]h ]h"]h$]h&]uh1jhjhhhhhNubj)}(hXEach ``rcu_node`` structure's ``->expmaskinit`` field is used to initialize that structure's ``->expmask`` at the beginning of each RCU expedited grace period. This means that only those CPUs that have been online at least once will be considered for a given grace period.h]h)}(hXEach ``rcu_node`` structure's ``->expmaskinit`` field is used to initialize that structure's ``->expmask`` at the beginning of each RCU expedited grace period. This means that only those CPUs that have been online at least once will be considered for a given grace period.h](hEach }(hjhhhNhNubj)}(h ``rcu_node``h]hrcu_node}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh structure’s }(hjhhhNhNubj)}(h``->expmaskinit``h]h ->expmaskinit}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh0 field is used to initialize that structure’s }(hjhhhNhNubj)}(h ``->expmask``h]h ->expmask}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh at the beginning of each RCU expedited grace period. This means that only those CPUs that have been online at least once will be considered for a given grace period.}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKhjubah}(h]h ]h"]h$]h&]uh1jhjhhhhhNubj)}(hX/Any CPU that goes offline will clear its bit in its leaf ``rcu_node`` structure's ``->qsmaskinitnext`` field, so any CPU with that bit clear can safely be ignored. However, it is possible for a CPU coming online or going offline to have this bit set for some time while ``cpu_online`` returns ``false``.h]h)}(hX/Any CPU that goes offline will clear its bit in its leaf ``rcu_node`` structure's ``->qsmaskinitnext`` field, so any CPU with that bit clear can safely be ignored. However, it is possible for a CPU coming online or going offline to have this bit set for some time while ``cpu_online`` returns ``false``.h](h9Any CPU that goes offline will clear its bit in its leaf }(hj:hhhNhNubj)}(h ``rcu_node``h]hrcu_node}(hjBhhhNhNubah}(h]h ]h"]h$]h&]uh1jhj:ubh structure’s }(hj:hhhNhNubj)}(h``->qsmaskinitnext``h]h->qsmaskinitnext}(hjThhhNhNubah}(h]h ]h"]h$]h&]uh1jhj:ubh field, so any CPU with that bit clear can safely be ignored. However, it is possible for a CPU coming online or going offline to have this bit set for some time while }(hj:hhhNhNubj)}(h``cpu_online``h]h cpu_online}(hjfhhhNhNubah}(h]h ]h"]h$]h&]uh1jhj:ubh returns }(hj:hhhNhNubj)}(h ``false``h]hfalse}(hjxhhhNhNubah}(h]h ]h"]h$]h&]uh1jhj:ubh.}(hj:hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKhj6ubah}(h]h ]h"]h$]h&]uh1jhjhhhhhNubj)}(hXFor each non-idle CPU that RCU believes is currently online, the grace period invokes ``smp_call_function_single()``. If this succeeds, the CPU was fully online. Failure indicates that the CPU is in the process of coming online or going offline, in which case it is necessary to wait for a short time period and try again. The purpose of this wait (or series of waits, as the case may be) is to permit a concurrent CPU-hotplug operation to complete.h]h)}(hXFor each non-idle CPU that RCU believes is currently online, the grace period invokes ``smp_call_function_single()``. If this succeeds, the CPU was fully online. Failure indicates that the CPU is in the process of coming online or going offline, in which case it is necessary to wait for a short time period and try again. The purpose of this wait (or series of waits, as the case may be) is to permit a concurrent CPU-hotplug operation to complete.h](hVFor each non-idle CPU that RCU believes is currently online, the grace period invokes }(hjhhhNhNubj)}(h``smp_call_function_single()``h]hsmp_call_function_single()}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubhXM. If this succeeds, the CPU was fully online. Failure indicates that the CPU is in the process of coming online or going offline, in which case it is necessary to wait for a short time period and try again. The purpose of this wait (or series of waits, as the case may be) is to permit a concurrent CPU-hotplug operation to complete.}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKhjubah}(h]h ]h"]h$]h&]uh1jhjhhhhhNubj)}(hIn the case of RCU-sched, one of the last acts of an outgoing CPU is to invoke ``rcutree_report_cpu_dead()``, which reports a quiescent state for that CPU. However, this is likely paranoia-induced redundancy. h]h)}(hIn the case of RCU-sched, one of the last acts of an outgoing CPU is to invoke ``rcutree_report_cpu_dead()``, which reports a quiescent state for that CPU. However, this is likely paranoia-induced redundancy.h](hOIn the case of RCU-sched, one of the last acts of an outgoing CPU is to invoke }(hjhhhNhNubj)}(h``rcutree_report_cpu_dead()``h]hrcutree_report_cpu_dead()}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubhd, which reports a quiescent state for that CPU. However, this is likely paranoia-induced redundancy.}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKhjubah}(h]h ]h"]h$]h&]uh1jhjhhhhhNubeh}(h]h ]h"]h$]h&]enumtypearabicprefixhsuffix.uh1jhjdhhhhhKubj)}(hhh]j)}(hhh](j)}(hhh]h}(h]h ]h"]h$]h&]colwidthKGuh1jhjubj)}(hhh](j)}(hhh]j)}(hhh]h)}(h**Quick Quiz**:h](j)}(h**Quick Quiz**h]h Quick Quiz}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh:}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKhj ubah}(h]h ]h"]h$]h&]uh1jhjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]j)}(hhh]h)}(hWhy all the dancing around with multiple counters and masks tracking CPUs that were once online? Why not just have a single set of masks tracking the currently online CPUs and be done with it?h]hWhy all the dancing around with multiple counters and masks tracking CPUs that were once online? Why not just have a single set of masks tracking the currently online CPUs and be done with it?}(hj<hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhj9ubah}(h]h ]h"]h$]h&]uh1jhj6ubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]j)}(hhh]h)}(h **Answer**:h](j)}(h **Answer**h]hAnswer}(hj`hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj\ubh:}(hj\hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKhjYubah}(h]h ]h"]h$]h&]uh1jhjVubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]j)}(hhh](h)}(hX7Maintaining single set of masks tracking the online CPUs *sounds* easier, at least until you try working out all the race conditions between grace-period initialization and CPU-hotplug operations. For example, suppose initialization is progressing down the tree while a CPU-offline operation is progressing up the tree. This situation can result in bits set at the top of the tree that have no counterparts at the bottom of the tree. Those bits will never be cleared, which will result in grace-period hangs. In short, that way lies madness, to say nothing of a great many bugs, hangs, and deadlocks. In contrast, the current multi-mask multi-counter scheme ensures that grace-period initialization will always see consistent masks up and down the tree, which brings significant simplifications over the single-mask method.h](h9Maintaining single set of masks tracking the online CPUs }(hjhhhNhNubhemphasis)}(h*sounds*h]hsounds}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubhX easier, at least until you try working out all the race conditions between grace-period initialization and CPU-hotplug operations. For example, suppose initialization is progressing down the tree while a CPU-offline operation is progressing up the tree. This situation can result in bits set at the top of the tree that have no counterparts at the bottom of the tree. Those bits will never be cleared, which will result in grace-period hangs. In short, that way lies madness, to say nothing of a great many bugs, hangs, and deadlocks. In contrast, the current multi-mask multi-counter scheme ensures that grace-period initialization will always see consistent masks up and down the tree, which brings significant simplifications over the single-mask method.}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKhjubh)}(hXLThis is an instance of `deferring work in order to avoid synchronization `__. Lazily recording CPU-hotplug events at the beginning of the next grace period greatly simplifies maintenance of the CPU-tracking bitmasks in the ``rcu_node`` tree.h](hThis is an instance of }(hjhhhNhNubh reference)}(h`deferring work in order to avoid synchronization `__h]h0deferring work in order to avoid synchronization}(hjhhhNhNubah}(h]h ]h"]h$]h&]name0deferring work in order to avoid synchronizationrefuriXhttp://www.cs.columbia.edu/~library/TR-repository/reports/reports-1992/cucs-039-92.ps.gzuh1jhjubh. Lazily recording CPU-hotplug events at the beginning of the next grace period greatly simplifies maintenance of the CPU-tracking bitmasks in the }(hjhhhNhNubj)}(h ``rcu_node``h]hrcu_node}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh tree.}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKhjubeh}(h]h ]h"]h$]h&]uh1jhjubah}(h]h ]h"]h$]h&]uh1jhjubeh}(h]h ]h"]h$]h&]uh1jhjubeh}(h]h ]h"]h$]h&]colsKuh1jhjubah}(h]h ]h"]h$]h&]uh1jhjdhhhhhNubeh}(h]&expedited-grace-period-and-cpu-hotplugah ]h"]&expedited grace period and cpu hotplugah$]h&]uh1hhj[hhhhhKubh)}(hhh](h)}(h"Expedited Grace Period Refinementsh]h"Expedited Grace Period Refinements}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhj hhhhhKubh)}(hhh](h)}(hIdle-CPU Checksh]hIdle-CPU Checks}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjhhhhhKubh)}(hXEach expedited grace period checks for idle CPUs when initially forming the mask of CPUs to be IPIed and again just before IPIing a CPU (both checks are carried out by ``sync_rcu_exp_select_cpus()``). If the CPU is idle at any time between those two times, the CPU will not be IPIed. Instead, the task pushing the grace period forward will include the idle CPUs in the mask passed to ``rcu_report_exp_cpu_mult()``.h](hEach expedited grace period checks for idle CPUs when initially forming the mask of CPUs to be IPIed and again just before IPIing a CPU (both checks are carried out by }(hj-hhhNhNubj)}(h``sync_rcu_exp_select_cpus()``h]hsync_rcu_exp_select_cpus()}(hj5hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj-ubh). If the CPU is idle at any time between those two times, the CPU will not be IPIed. Instead, the task pushing the grace period forward will include the idle CPUs in the mask passed to }(hj-hhhNhNubj)}(h``rcu_report_exp_cpu_mult()``h]hrcu_report_exp_cpu_mult()}(hjGhhhNhNubah}(h]h ]h"]h$]h&]uh1jhj-ubh.}(hj-hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKhjhhubh)}(hFor RCU-sched, there is an additional check: If the IPI has interrupted the idle loop, then ``rcu_exp_handler()`` invokes ``rcu_report_exp_rdp()`` to report the corresponding quiescent state.h](h\For RCU-sched, there is an additional check: If the IPI has interrupted the idle loop, then }(hj_hhhNhNubj)}(h``rcu_exp_handler()``h]hrcu_exp_handler()}(hjghhhNhNubah}(h]h ]h"]h$]h&]uh1jhj_ubh invokes }(hj_hhhNhNubj)}(h``rcu_report_exp_rdp()``h]hrcu_report_exp_rdp()}(hjyhhhNhNubah}(h]h ]h"]h$]h&]uh1jhj_ubh- to report the corresponding quiescent state.}(hj_hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKhjhhubh)}(hXFor RCU-preempt, there is no specific check for idle in the IPI handler (``rcu_exp_handler()``), but because RCU read-side critical sections are not permitted within the idle loop, if ``rcu_exp_handler()`` sees that the CPU is within RCU read-side critical section, the CPU cannot possibly be idle. Otherwise, ``rcu_exp_handler()`` invokes ``rcu_report_exp_rdp()`` to report the corresponding quiescent state, regardless of whether or not that quiescent state was due to the CPU being idle.h](hIFor RCU-preempt, there is no specific check for idle in the IPI handler (}(hjhhhNhNubj)}(h``rcu_exp_handler()``h]hrcu_exp_handler()}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubhZ), but because RCU read-side critical sections are not permitted within the idle loop, if }(hjhhhNhNubj)}(h``rcu_exp_handler()``h]hrcu_exp_handler()}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubhi sees that the CPU is within RCU read-side critical section, the CPU cannot possibly be idle. Otherwise, }(hjhhhNhNubj)}(h``rcu_exp_handler()``h]hrcu_exp_handler()}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh invokes }(hjhhhNhNubj)}(h``rcu_report_exp_rdp()``h]hrcu_report_exp_rdp()}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh~ to report the corresponding quiescent state, regardless of whether or not that quiescent state was due to the CPU being idle.}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKhjhhubh)}(hIn summary, RCU expedited grace periods check for idle when building the bitmask of CPUs that must be IPIed, just before sending each IPI, and (either explicitly or implicitly) within the IPI handler.h]hIn summary, RCU expedited grace periods check for idle when building the bitmask of CPUs that must be IPIed, just before sending each IPI, and (either explicitly or implicitly) within the IPI handler.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubeh}(h]idle-cpu-checksah ]h"]idle-cpu checksah$]h&]uh1hhj hhhhhKubh)}(hhh](h)}(hBatching via Sequence Counterh]hBatching via Sequence Counter}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhjhhhhhKubh)}(hXsIf each grace-period request was carried out separately, expedited grace periods would have abysmal scalability and problematic high-load characteristics. Because each grace-period operation can serve an unlimited number of updates, it is important to *batch* requests, so that a single expedited grace-period operation will cover all requests in the corresponding batch.h](hIf each grace-period request was carried out separately, expedited grace periods would have abysmal scalability and problematic high-load characteristics. Because each grace-period operation can serve an unlimited number of updates, it is important to }(hj hhhNhNubj)}(h*batch*h]hbatch}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj ubhp requests, so that a single expedited grace-period operation will cover all requests in the corresponding batch.}(hj hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKhjhhubh)}(hXThis batching is controlled by a sequence counter named ``->expedited_sequence`` in the ``rcu_state`` structure. This counter has an odd value when there is an expedited grace period in progress and an even value otherwise, so that dividing the counter value by two gives the number of completed grace periods. During any given update request, the counter must transition from even to odd and then back to even, thus indicating that a grace period has elapsed. Therefore, if the initial value of the counter is ``s``, the updater must wait until the counter reaches at least the value ``(s+3)&~0x1``. This counter is managed by the following access functions:h](h8This batching is controlled by a sequence counter named }(hj. hhhNhNubj)}(h``->expedited_sequence``h]h->expedited_sequence}(hj6 hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj. ubh in the }(hj. hhhNhNubj)}(h ``rcu_state``h]h rcu_state}(hjH hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj. ubhX structure. This counter has an odd value when there is an expedited grace period in progress and an even value otherwise, so that dividing the counter value by two gives the number of completed grace periods. During any given update request, the counter must transition from even to odd and then back to even, thus indicating that a grace period has elapsed. Therefore, if the initial value of the counter is }(hj. hhhNhNubj)}(h``s``h]hs}(hjZ hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj. ubhE, the updater must wait until the counter reaches at least the value }(hj. hhhNhNubj)}(h``(s+3)&~0x1``h]h (s+3)&~0x1}(hjl hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj. ubh<. This counter is managed by the following access functions:}(hj. hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMhjhhubj)}(hhh](j)}(hO``rcu_exp_gp_seq_start()``, which marks the start of an expedited grace period.h]h)}(hO``rcu_exp_gp_seq_start()``, which marks the start of an expedited grace period.h](j)}(h``rcu_exp_gp_seq_start()``h]hrcu_exp_gp_seq_start()}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj ubh5, which marks the start of an expedited grace period.}(hj hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhM hj ubah}(h]h ]h"]h$]h&]uh1jhj hhhhhNubj)}(hK``rcu_exp_gp_seq_end()``, which marks the end of an expedited grace period.h]h)}(hK``rcu_exp_gp_seq_end()``, which marks the end of an expedited grace period.h](j)}(h``rcu_exp_gp_seq_end()``h]hrcu_exp_gp_seq_end()}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj ubh3, which marks the end of an expedited grace period.}(hj hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMhj ubah}(h]h ]h"]h$]h&]uh1jhj hhhhhNubj)}(hC``rcu_exp_gp_seq_snap()``, which obtains a snapshot of the counter.h]h)}(hj h](j)}(h``rcu_exp_gp_seq_snap()``h]hrcu_exp_gp_seq_snap()}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj ubh*, which obtains a snapshot of the counter.}(hj hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMhj ubah}(h]h ]h"]h$]h&]uh1jhj hhhhhNubj)}(h``rcu_exp_gp_seq_done()``, which returns ``true`` if a full expedited grace period has elapsed since the corresponding call to ``rcu_exp_gp_seq_snap()``. h]h)}(h``rcu_exp_gp_seq_done()``, which returns ``true`` if a full expedited grace period has elapsed since the corresponding call to ``rcu_exp_gp_seq_snap()``.h](j)}(h``rcu_exp_gp_seq_done()``h]hrcu_exp_gp_seq_done()}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj ubh, which returns }(hj hhhNhNubj)}(h``true``h]htrue}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj ubhN if a full expedited grace period has elapsed since the corresponding call to }(hj hhhNhNubj)}(h``rcu_exp_gp_seq_snap()``h]hrcu_exp_gp_seq_snap()}(hj$ hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj ubh.}(hj hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMhj ubah}(h]h ]h"]h$]h&]uh1jhj hhhhhNubeh}(h]h ]h"]h$]h&]jjjhjjuh1jhjhhhhhM ubh)}(hXlAgain, only one request in a given batch need actually carry out a grace-period operation, which means there must be an efficient way to identify which of many concurrent requests will initiate the grace period, and that there be an efficient way for the remaining requests to wait for that grace period to complete. However, that is the topic of the next section.h]hXlAgain, only one request in a given batch need actually carry out a grace-period operation, which means there must be an efficient way to identify which of many concurrent requests will initiate the grace period, and that there be an efficient way for the remaining requests to wait for that grace period to complete. However, that is the topic of the next section.}(hjH hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubeh}(h]batching-via-sequence-counterah ]h"]batching via sequence counterah$]h&]uh1hhj hhhhhKubh)}(hhh](h)}(hFunnel Locking and Wait/Wakeuph]hFunnel Locking and Wait/Wakeup}(hja hhhNhNubah}(h]h ]h"]h$]h&]uh1hhj^ hhhhhMubh)}(hX The natural way to sort out which of a batch of updaters will initiate the expedited grace period is to use the ``rcu_node`` combining tree, as implemented by the ``exp_funnel_lock()`` function. The first updater corresponding to a given grace period arriving at a given ``rcu_node`` structure records its desired grace-period sequence number in the ``->exp_seq_rq`` field and moves up to the next level in the tree. Otherwise, if the ``->exp_seq_rq`` field already contains the sequence number for the desired grace period or some later one, the updater blocks on one of four wait queues in the ``->exp_wq[]`` array, using the second-from-bottom and third-from bottom bits as an index. An ``->exp_lock`` field in the ``rcu_node`` structure synchronizes access to these fields.h](hpThe natural way to sort out which of a batch of updaters will initiate the expedited grace period is to use the }(hjo hhhNhNubj)}(h ``rcu_node``h]hrcu_node}(hjw hhhNhNubah}(h]h ]h"]h$]h&]uh1jhjo ubh' combining tree, as implemented by the }(hjo hhhNhNubj)}(h``exp_funnel_lock()``h]hexp_funnel_lock()}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jhjo ubhW function. The first updater corresponding to a given grace period arriving at a given }(hjo hhhNhNubj)}(h ``rcu_node``h]hrcu_node}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jhjo ubhC structure records its desired grace-period sequence number in the }(hjo hhhNhNubj)}(h``->exp_seq_rq``h]h ->exp_seq_rq}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jhjo ubhE field and moves up to the next level in the tree. Otherwise, if the }(hjo hhhNhNubj)}(h``->exp_seq_rq``h]h ->exp_seq_rq}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jhjo ubh field already contains the sequence number for the desired grace period or some later one, the updater blocks on one of four wait queues in the }(hjo hhhNhNubj)}(h``->exp_wq[]``h]h ->exp_wq[]}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jhjo ubhP array, using the second-from-bottom and third-from bottom bits as an index. An }(hjo hhhNhNubj)}(h``->exp_lock``h]h ->exp_lock}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jhjo ubh field in the }(hjo hhhNhNubj)}(h ``rcu_node``h]hrcu_node}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jhjo ubh/ structure synchronizes access to these fields.}(hjo hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhM hj^ hhubh)}(hAn empty ``rcu_node`` tree is shown in the following diagram, with the white cells representing the ``->exp_seq_rq`` field and the red cells representing the elements of the ``->exp_wq[]`` array.h](h An empty }(hj hhhNhNubj)}(h ``rcu_node``h]hrcu_node}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj ubhO tree is shown in the following diagram, with the white cells representing the }(hj hhhNhNubj)}(h``->exp_seq_rq``h]h ->exp_seq_rq}(hj' hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj ubh: field and the red cells representing the elements of the }(hj hhhNhNubj)}(h``->exp_wq[]``h]h ->exp_wq[]}(hj9 hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj ubh array.}(hj hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhM-hj^ hhubj)}(hhh]j)}(hhh]j)}(h.. kernel-figure:: Funnel0.svg h]h}(h]h ]h"]h$]h&]uri.RCU/Design/Expedited-Grace-Periods/Funnel0.svgj}jjb suh1jhjT hhhKubah}(h]h ]h"]h$]h&]uh1jhjQ ubah}(h]h ]h"]h$]h&]uh1jhj^ hhhhhM2ubh)}(hXThe next diagram shows the situation after the arrival of Task A and Task B at the leftmost and rightmost leaf ``rcu_node`` structures, respectively. The current value of the ``rcu_state`` structure's ``->expedited_sequence`` field is zero, so adding three and clearing the bottom bit results in the value two, which both tasks record in the ``->exp_seq_rq`` field of their respective ``rcu_node`` structures:h](hqThe next diagram shows the situation after the arrival of Task A and Task B at the leftmost and rightmost leaf }(hjp hhhNhNubj)}(h ``rcu_node``h]hrcu_node}(hjx hhhNhNubah}(h]h ]h"]h$]h&]uh1jhjp ubh4 structures, respectively. The current value of the }(hjp hhhNhNubj)}(h ``rcu_state``h]h rcu_state}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jhjp ubh structure’s }(hjp hhhNhNubj)}(h``->expedited_sequence``h]h->expedited_sequence}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jhjp ubhu field is zero, so adding three and clearing the bottom bit results in the value two, which both tasks record in the }(hjp hhhNhNubj)}(h``->exp_seq_rq``h]h ->exp_seq_rq}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jhjp ubh field of their respective }(hjp hhhNhNubj)}(h ``rcu_node``h]hrcu_node}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jhjp ubh structures:}(hjp hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhM3hj^ hhubj)}(hhh]j)}(hhh]j)}(h.. kernel-figure:: Funnel1.svg h]h}(h]h ]h"]h$]h&]uri.RCU/Design/Expedited-Grace-Periods/Funnel1.svgj}jj suh1jhj hhhKubah}(h]h ]h"]h$]h&]uh1jhj ubah}(h]h ]h"]h$]h&]uh1jhj^ hhhhhM;ubh)}(hEach of Tasks A and B will move up to the root ``rcu_node`` structure. Suppose that Task A wins, recording its desired grace-period sequence number and resulting in the state shown below:h](h1Each of Tasks A and B will move up to the root }(hj hhhNhNubj)}(h ``rcu_node``h]hrcu_node}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj ubh structure. Suppose that Task A wins, recording its desired grace-period sequence number and resulting in the state shown below:}(hj hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhM<hj^ hhubj)}(hhh]j)}(hhh]j)}(h.. kernel-figure:: Funnel2.svg h]h}(h]h ]h"]h$]h&]uri.RCU/Design/Expedited-Grace-Periods/Funnel2.svgj}jj( suh1jhj hhhKubah}(h]h ]h"]h$]h&]uh1jhj ubah}(h]h ]h"]h$]h&]uh1jhj^ hhhhhMAubh)}(hTask A now advances to initiate a new grace period, while Task B moves up to the root ``rcu_node`` structure, and, seeing that its desired sequence number is already recorded, blocks on ``->exp_wq[1]``.h](hXTask A now advances to initiate a new grace period, while Task B moves up to the root }(hj6 hhhNhNubj)}(h ``rcu_node``h]hrcu_node}(hj> hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj6 ubhX structure, and, seeing that its desired sequence number is already recorded, blocks on }(hj6 hhhNhNubj)}(h``->exp_wq[1]``h]h ->exp_wq[1]}(hjP hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj6 ubh.}(hj6 hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMBhj^ hhubj)}(hhh]j)}(hhh](j)}(hhh]h}(h]h ]h"]h$]h&]colwidthKGuh1jhjk ubj)}(hhh](j)}(hhh]j)}(hhh]h)}(h**Quick Quiz**:h](j)}(h**Quick Quiz**h]h Quick Quiz}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj ubh:}(hj hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMGhj~ ubah}(h]h ]h"]h$]h&]uh1jhj{ ubah}(h]h ]h"]h$]h&]uh1jhjx ubj)}(hhh]j)}(hhh]h)}(hWhy ``->exp_wq[1]``? Given that the value of these tasks' desired sequence number is two, so shouldn't they instead block on ``->exp_wq[2]``?h](hWhy }(hj hhhNhNubj)}(h``->exp_wq[1]``h]h ->exp_wq[1]}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj ubhn? Given that the value of these tasks’ desired sequence number is two, so shouldn’t they instead block on }(hj hhhNhNubj)}(h``->exp_wq[2]``h]h ->exp_wq[2]}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj ubh?}(hj hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMIhj ubah}(h]h ]h"]h$]h&]uh1jhj ubah}(h]h ]h"]h$]h&]uh1jhjx ubj)}(hhh]j)}(hhh]h)}(h **Answer**:h](j)}(h **Answer**h]hAnswer}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj ubh:}(hj hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMMhj ubah}(h]h ]h"]h$]h&]uh1jhj ubah}(h]h ]h"]h$]h&]uh1jhjx ubj)}(hhh]j)}(hhh]h)}(hXNo. Recall that the bottom bit of the desired sequence number indicates whether or not a grace period is currently in progress. It is therefore necessary to shift the sequence number right one bit position to obtain the number of the grace period. This results in ``->exp_wq[1]``.h](hXNo. Recall that the bottom bit of the desired sequence number indicates whether or not a grace period is currently in progress. It is therefore necessary to shift the sequence number right one bit position to obtain the number of the grace period. This results in }(hj! hhhNhNubj)}(h``->exp_wq[1]``h]h ->exp_wq[1]}(hj) hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj! ubh.}(hj! hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMOhj ubah}(h]h ]h"]h$]h&]uh1jhj ubah}(h]h ]h"]h$]h&]uh1jhjx ubeh}(h]h ]h"]h$]h&]uh1jhjk ubeh}(h]h ]h"]h$]h&]colsKuh1jhjh ubah}(h]h ]h"]h$]h&]uh1jhj^ hhhhhNubh)}(hX.If Tasks C and D also arrive at this point, they will compute the same desired grace-period sequence number, and see that both leaf ``rcu_node`` structures already have that value recorded. They will therefore block on their respective ``rcu_node`` structures' ``->exp_wq[1]`` fields, as shown below:h](hIf Tasks C and D also arrive at this point, they will compute the same desired grace-period sequence number, and see that both leaf }(hj` hhhNhNubj)}(h ``rcu_node``h]hrcu_node}(hjh hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj` ubh\ structures already have that value recorded. They will therefore block on their respective }(hj` hhhNhNubj)}(h ``rcu_node``h]hrcu_node}(hjz hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj` ubh structures’ }(hj` hhhNhNubj)}(h``->exp_wq[1]``h]h ->exp_wq[1]}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj` ubh fields, as shown below:}(hj` hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMWhj^ hhubj)}(hhh]j)}(hhh]j)}(h.. kernel-figure:: Funnel3.svg h]h}(h]h ]h"]h$]h&]uri.RCU/Design/Expedited-Grace-Periods/Funnel3.svgj}jj suh1jhj hhhKubah}(h]h ]h"]h$]h&]uh1jhj ubah}(h]h ]h"]h$]h&]uh1jhj^ hhhhhM^ubh)}(hXTask A now acquires the ``rcu_state`` structure's ``->exp_mutex`` and initiates the grace period, which increments ``->expedited_sequence``. Therefore, if Tasks E and F arrive, they will compute a desired sequence number of 4 and will record this value as shown below:h](hTask A now acquires the }(hj hhhNhNubj)}(h ``rcu_state``h]h rcu_state}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj ubh structure’s }(hj hhhNhNubj)}(h``->exp_mutex``h]h ->exp_mutex}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj ubh2 and initiates the grace period, which increments }(hj hhhNhNubj)}(h``->expedited_sequence``h]h->expedited_sequence}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj ubh. Therefore, if Tasks E and F arrive, they will compute a desired sequence number of 4 and will record this value as shown below:}(hj hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhM_hj^ hhubj)}(hhh]j)}(hhh]j)}(h.. kernel-figure:: Funnel4.svg h]h}(h]h ]h"]h$]h&]uri.RCU/Design/Expedited-Grace-Periods/Funnel4.svgj}jjsuh1jhj hhhKubah}(h]h ]h"]h$]h&]uh1jhjubah}(h]h ]h"]h$]h&]uh1jhj^ hhhhhMeubh)}(hTasks E and F will propagate up the ``rcu_node`` combining tree, with Task F blocking on the root ``rcu_node`` structure and Task E wait for Task A to finish so that it can start the next grace period. The resulting state is as shown below:h](h&Tasks E and F will propagate up the }(hj&hhhNhNubj)}(h ``rcu_node``h]hrcu_node}(hj.hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj&ubh3 combining tree, with Task F blocking on the root }(hj&hhhNhNubj)}(h ``rcu_node``h]hrcu_node}(hj@hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj&ubh structure and Task E wait for Task A to finish so that it can start the next grace period. The resulting state is as shown below:}(hj&hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMfhj^ hhubj)}(hhh]j)}(hhh]j)}(h.. kernel-figure:: Funnel5.svg h]h}(h]h ]h"]h$]h&]uri.RCU/Design/Expedited-Grace-Periods/Funnel5.svgj}jjisuh1jhj[hhhKubah}(h]h ]h"]h$]h&]uh1jhjXubah}(h]h ]h"]h$]h&]uh1jhj^ hhhhhMlubh)}(hXOnce the grace period completes, Task A starts waking up the tasks waiting for this grace period to complete, increments the ``->expedited_sequence``, acquires the ``->exp_wake_mutex`` and then releases the ``->exp_mutex``. This results in the following state:h](h~Once the grace period completes, Task A starts waking up the tasks waiting for this grace period to complete, increments the }(hjwhhhNhNubj)}(h``->expedited_sequence``h]h->expedited_sequence}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjwubh, acquires the }(hjwhhhNhNubj)}(h``->exp_wake_mutex``h]h->exp_wake_mutex}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjwubh and then releases the }(hjwhhhNhNubj)}(h``->exp_mutex``h]h ->exp_mutex}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjwubh&. This results in the following state:}(hjwhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMmhj^ hhubj)}(hhh]j)}(hhh]j)}(h.. kernel-figure:: Funnel6.svg h]h}(h]h ]h"]h$]h&]uri.RCU/Design/Expedited-Grace-Periods/Funnel6.svgj}jjsuh1jhjhhhKubah}(h]h ]h"]h$]h&]uh1jhjubah}(h]h ]h"]h$]h&]uh1jhj^ hhhhhMsubh)}(hTask E can then acquire ``->exp_mutex`` and increment ``->expedited_sequence`` to the value three. If new tasks G and H arrive and moves up the combining tree at the same time, the state will be as follows:h](hTask E can then acquire }(hjhh]hNhNubj)}(h``->exp_mutex``h]h ->exp_mutex}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh and increment }(hjhhhNhNubj)}(h``->expedited_sequence``h]h->expedited_sequence}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh to the value three. If new tasks G and H arrive and moves up the combining tree at the same time, the state will be as follows:}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMthj^ hhubj)}(hhh]j)}(hhh]j)}(h.. kernel-figure:: Funnel7.svg h]h}(h]h ]h"]h$]h&]uri.RCU/Design/Expedited-Grace-Periods/Funnel7.svgj}jjsuh1jhjhhhKubah}(h]h ]h"]h$]h&]uh1jhj ubah}(h]h ]h"]h$]h&]uh1jhj^ hhhhhMzubh)}(hNote that three of the root ``rcu_node`` structure's waitqueues are now occupied. However, at some point, Task A will wake up the tasks blocked on the ``->exp_wq`` waitqueues, resulting in the following state:h](hNote that three of the root }(hj+hhhNhNubj)}(h ``rcu_node``h]hrcu_node}(hj3hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj+ubhr structure’s waitqueues are now occupied. However, at some point, Task A will wake up the tasks blocked on the }(hj+hhhNhNubj)}(h ``->exp_wq``h]h->exp_wq}(hjEhhhNhNubah}(h]h ]h"]h$]h&]uh1jhj+ubh. waitqueues, resulting in the following state:}(hj+hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhM{hj^ hhubj)}(hhh]j)}(hhh]j)}(h.. kernel-figure:: Funnel8.svg h]h}(h]h ]h"]h$]h&]uri.RCU/Design/Expedited-Grace-Periods/Funnel8.svgj}jjnsuh1jhj`hhhKubah}(h]h ]h"]h$]h&]uh1jhj]ubah}(h]h ]h"]h$]h&]uh1jhj^ hhhhhMubh)}(hkExecution will continue with Tasks E and H completing their grace periods and carrying out their wakeups.h]hkExecution will continue with Tasks E and H completing their grace periods and carrying out their wakeups.}(hj|hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj^ hhubj)}(hhh]j)}(hhh](j)}(hhh]h}(h]h ]h"]h$]h&]colwidthKGuh1jhjubj)}(hhh](j)}(hhh]j)}(hhh]h)}(h**Quick Quiz**:h](j)}(h**Quick Quiz**h]h Quick Quiz}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh:}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMhjubah}(h]h ]h"]h$]h&]uh1jhjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]j)}(hhh]h)}(h^What happens if Task A takes so long to do its wakeups that Task E's grace period completes?h]h`What happens if Task A takes so long to do its wakeups that Task E’s grace period completes?}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjubah}(h]h ]h"]h$]h&]uh1jhjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]j)}(hhh]h)}(h **Answer**:h](j)}(h **Answer**h]hAnswer}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh:}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMhjubah}(h]h ]h"]h$]h&]uh1jhjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]j)}(hhh]h)}(hThen Task E will block on the ``->exp_wake_mutex``, which will also prevent it from releasing ``->exp_mutex``, which in turn will prevent the next grace period from starting. This last is important in preventing overflow of the ``->exp_wq[]`` array.h](hThen Task E will block on the }(hjhhhNhNubj)}(h``->exp_wake_mutex``h]h->exp_wake_mutex}(hj'hhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh,, which will also prevent it from releasing }(hjhhhNhNubj)}(h``->exp_mutex``h]h ->exp_mutex}(hj9hhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubhw, which in turn will prevent the next grace period from starting. This last is important in preventing overflow of the }(hjhhhNhNubj)}(h``->exp_wq[]``h]h ->exp_wq[]}(hjKhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh array.}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMhjubah}(h]h ]h"]h$]h&]uh1jhjubah}(h]h ]h"]h$]h&]uh1jhjubeh}(h]h ]h"]h$]h&]uh1jhjubeh}(h]h ]h"]h$]h&]colsKuh1jhjubah}(h]h ]h"]h$]h&]uh1jhj^ hhhhhNubeh}(h]funnel-locking-and-wait-wakeupah ]h"]funnel locking and wait/wakeupah$]h&]uh1hhj hhhhhMubh)}(hhh](h)}(hUse of Workqueuesh]hUse of Workqueues}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjhhhhhMubh)}(hXCIn earlier implementations, the task requesting the expedited grace period also drove it to completion. This straightforward approach had the disadvantage of needing to account for POSIX signals sent to user tasks, so more recent implementations use the Linux kernel's workqueues (see Documentation/core-api/workqueue.rst).h]hXEIn earlier implementations, the task requesting the expedited grace period also drove it to completion. This straightforward approach had the disadvantage of needing to account for POSIX signals sent to user tasks, so more recent implementations use the Linux kernel’s workqueues (see Documentation/core-api/workqueue.rst).}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubh)}(hX.The requesting task still does counter snapshotting and funnel-lock processing, but the task reaching the top of the funnel lock does a ``schedule_work()`` (from ``_synchronize_rcu_expedited()`` so that a workqueue kthread does the actual grace-period processing. Because workqueue kthreads do not accept POSIX signals, grace-period-wait processing need not allow for POSIX signals. In addition, this approach allows wakeups for the previous expedited grace period to be overlapped with processing for the next expedited grace period. Because there are only four sets of waitqueues, it is necessary to ensure that the previous grace period's wakeups complete before the next grace period's wakeups start. This is handled by having the ``->exp_mutex`` guard expedited grace-period processing and the ``->exp_wake_mutex`` guard wakeups. The key point is that the ``->exp_mutex`` is not released until the first wakeup is complete, which means that the ``->exp_wake_mutex`` has already been acquired at that point. This approach ensures that the previous grace period's wakeups can be carried out while the current grace period is in process, but that these wakeups will complete before the next grace period starts. This means that only three waitqueues are required, guaranteeing that the four that are provided are sufficient.h](hThe requesting task still does counter snapshotting and funnel-lock processing, but the task reaching the top of the funnel lock does a }(hjhhhNhNubj)}(h``schedule_work()``h]hschedule_work()}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh (from }(hjhhhNhNubj)}(h ``_synchronize_rcu_expedited()``h]h_synchronize_rcu_expedited()}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubhX! so that a workqueue kthread does the actual grace-period processing. Because workqueue kthreads do not accept POSIX signals, grace-period-wait processing need not allow for POSIX signals. In addition, this approach allows wakeups for the previous expedited grace period to be overlapped with processing for the next expedited grace period. Because there are only four sets of waitqueues, it is necessary to ensure that the previous grace period’s wakeups complete before the next grace period’s wakeups start. This is handled by having the }(hjhhhNhNubj)}(h``->exp_mutex``h]h ->exp_mutex}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh1 guard expedited grace-period processing and the }(hjhhhNhNubj)}(h``->exp_wake_mutex``h]h->exp_wake_mutex}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh* guard wakeups. The key point is that the }(hjhhhNhNubj)}(h``->exp_mutex``h]h ->exp_mutex}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubhJ is not released until the first wakeup is complete, which means that the }(hjhhhNhNubj)}(h``->exp_wake_mutex``h]h->exp_wake_mutex}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubhXf has already been acquired at that point. This approach ensures that the previous grace period’s wakeups can be carried out while the current grace period is in process, but that these wakeups will complete before the next grace period starts. This means that only three waitqueues are required, guaranteeing that the four that are provided are sufficient.}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMhjhhubeh}(h]use-of-workqueuesah ]h"]use of workqueuesah$]h&]uh1hhj hhhhhMubh)}(hhh](h)}(hStall Warningsh]hStall Warnings}(hj.hhhNhNubah}(h]h ]h"]h$]h&]uh1hhj+hhhhhMubh)}(hExpediting grace periods does nothing to speed things up when RCU readers take too long, and therefore expedited grace periods check for stalls just as normal grace periods do.h]hExpediting grace periods does nothing to speed things up when RCU readers take too long, and therefore expedited grace periods check for stalls just as normal grace periods do.}(hj<hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj+hhubj)}(hhh]j)}(hhh](j)}(hhh]h}(h]h ]h"]h$]h&]colwidthKGuh1jhjMubj)}(hhh](j)}(hhh]j)}(hhh]h)}(h**Quick Quiz**:h](j)}(h**Quick Quiz**h]h Quick Quiz}(hjghhhNhNubah}(h]h ]h"]h$]h&]uh1jhjcubh:}(hjchhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMhj`ubah}(h]h ]h"]h$]h&]uh1jhj]ubah}(h]h ]h"]h$]h&]uh1jhjZubj)}(hhh]j)}(hhh]h)}(hBut why not just let the normal grace-period machinery detect the stalls, given that a given reader must block both normal and expedited grace periods?h]hBut why not just let the normal grace-period machinery detect the stalls, given that a given reader must block both normal and expedited grace periods?}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjubah}(h]h ]h"]h$]h&]uh1jhjubah}(h]h ]h"]h$]h&]uh1jhjZubj)}(hhh]j)}(hhh]h)}(h **Answer**:h](j)}(h **Answer**h]hAnswer}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh:}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMhjubah}(h]h ]h"]h$]h&]uh1jhjubah}(h]h ]h"]h$]h&]uh1jhjZubj)}(hhh]j)}(hhh]h)}(hBecause it is quite possible that at a given time there is no normal grace period in progress, in which case the normal grace period cannot emit a stall warning.h]hBecause it is quite possible that at a given time there is no normal grace period in progress, in which case the normal grace period cannot emit a stall warning.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjubah}(h]h ]h"]h$]h&]uh1jhjubah}(h]h ]h"]h$]h&]uh1jhjZubeh}(h]h ]h"]h$]h&]uh1jhjMubeh}(h]h ]h"]h$]h&]colsKuh1jhjJubah}(h]h ]h"]h$]h&]uh1jhj+hhhhhNubh)}(hXThe ``synchronize_sched_expedited_wait()`` function loops waiting for the expedited grace period to end, but with a timeout set to the current RCU CPU stall-warning time. If this time is exceeded, any CPUs or ``rcu_node`` structures blocking the current grace period are printed. Each stall warning results in another pass through the loop, but the second and subsequent passes use longer stall times.h](hThe }(hj hhhNhNubj)}(h&``synchronize_sched_expedited_wait()``h]h"synchronize_sched_expedited_wait()}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhj ubh function loops waiting for the expedited grace period to end, but with a timeout set to the current RCU CPU stall-warning time. If this time is exceeded, any CPUs or }(hj hhhNhNubj)}(h ``rcu_node``h]hrcu_node}(hj&hhhNhNubah}(h]h ]h"]h$]h&]uh1jhj ubh structures blocking the current grace period are printed. Each stall warning results in another pass through the loop, but the second and subsequent passes use longer stall times.}(hj hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMhj+hhubeh}(h]stall-warningsah ]h"]stall warningsah$]h&]uh1hhj hhhhhMubh)}(hhh](h)}(hMid-boot operationh]hMid-boot operation}(hjIhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjFhhhhhMubh)}(hXThe use of workqueues has the advantage that the expedited grace-period code need not worry about POSIX signals. Unfortunately, it has the corresponding disadvantage that workqueues cannot be used until they are initialized, which does not happen until some time after the scheduler spawns the first task. Given that there are parts of the kernel that really do want to execute grace periods during this mid-boot “dead zone”, expedited grace periods must do something else during this time.h]hXThe use of workqueues has the advantage that the expedited grace-period code need not worry about POSIX signals. Unfortunately, it has the corresponding disadvantage that workqueues cannot be used until they are initialized, which does not happen until some time after the scheduler spawns the first task. Given that there are parts of the kernel that really do want to execute grace periods during this mid-boot “dead zone”, expedited grace periods must do something else during this time.}(hjWhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjFhhubh)}(hXtWhat they do is to fall back to the old practice of requiring that the requesting task drive the expedited grace period, as was the case before the use of workqueues. However, the requesting task is only required to drive the grace period during the mid-boot dead zone. Before mid-boot, a synchronous grace period is a no-op. Some time after mid-boot, workqueues are used.h]hXtWhat they do is to fall back to the old practice of requiring that the requesting task drive the expedited grace period, as was the case before the use of workqueues. However, the requesting task is only required to drive the grace period during the mid-boot dead zone. Before mid-boot, a synchronous grace period is a no-op. Some time after mid-boot, workqueues are used.}(hjehhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjFhhubh)}(hNon-expedited non-SRCU synchronous grace periods must also operate normally during mid-boot. This is handled by causing non-expedited grace periods to take the expedited code path during mid-boot.h]hNon-expedited non-SRCU synchronous grace periods must also operate normally during mid-boot. This is handled by causing non-expedited grace periods to take the expedited code path during mid-boot.}(hjshhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjFhhubh)}(hXWThe current code assumes that there are no POSIX signals during the mid-boot dead zone. However, if an overwhelming need for POSIX signals somehow arises, appropriate adjustments can be made to the expedited stall-warning code. One such adjustment would reinstate the pre-workqueue stall-warning checks, but only during the mid-boot dead zone.h]hXWThe current code assumes that there are no POSIX signals during the mid-boot dead zone. However, if an overwhelming need for POSIX signals somehow arises, appropriate adjustments can be made to the expedited stall-warning code. One such adjustment would reinstate the pre-workqueue stall-warning checks, but only during the mid-boot dead zone.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjFhhubh)}(hWith this refinement, synchronous grace periods can now be used from task context pretty much any time during the life of the kernel. That is, aside from some points in the suspend, hibernate, or shutdown code path.h]hWith this refinement, synchronous grace periods can now be used from task context pretty much any time during the life of the kernel. That is, aside from some points in the suspend, hibernate, or shutdown code path.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjFhhubeh}(h]mid-boot-operationah ]h"]mid-boot operationah$]h&]uh1hhj hhhhhMubh)}(hhh](h)}(hSummaryh]hSummary}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjhhhhhMubh)}(hXExpedited grace periods use a sequence-number approach to promote batching, so that a single grace-period operation can serve numerous requests. A funnel lock is used to efficiently identify the one task out of a concurrent group that will request the grace period. All members of the group will block on waitqueues provided in the ``rcu_node`` structure. The actual grace-period processing is carried out by a workqueue.h](hXLExpedited grace periods use a sequence-number approach to promote batching, so that a single grace-period operation can serve numerous requests. A funnel lock is used to efficiently identify the one task out of a concurrent group that will request the grace period. All members of the group will block on waitqueues provided in the }(hjhhhNhNubj)}(h ``rcu_node``h]hrcu_node}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubhM structure. The actual grace-period processing is carried out by a workqueue.}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMhjhhubh)}(hXCPU-hotplug operations are noted lazily in order to prevent the need for tight synchronization between expedited grace periods and CPU-hotplug operations. The dyntick-idle counters are used to avoid sending IPIs to idle CPUs, at least in the common case. RCU-preempt and RCU-sched use different IPI handlers and different code to respond to the state changes carried out by those handlers, but otherwise use common code.h]hXCPU-hotplug operations are noted lazily in order to prevent the need for tight synchronization between expedited grace periods and CPU-hotplug operations. The dyntick-idle counters are used to avoid sending IPIs to idle CPUs, at least in the common case. RCU-preempt and RCU-sched use different IPI handlers and different code to respond to the state changes carried out by those handlers, but otherwise use common code.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubh)}(hX4Quiescent states are tracked using the ``rcu_node`` tree, and once all necessary quiescent states have been reported, all tasks waiting on this expedited grace period are awakened. A pair of mutexes are used to allow one grace period's wakeups to proceed concurrently with the next grace period's processing.h](h'Quiescent states are tracked using the }(hjhhhNhNubj)}(h ``rcu_node``h]hrcu_node}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubhX tree, and once all necessary quiescent states have been reported, all tasks waiting on this expedited grace period are awakened. A pair of mutexes are used to allow one grace period’s wakeups to proceed concurrently with the next grace period’s processing.}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMhjhhubh)}(hX This combination of mechanisms allows expedited grace periods to run reasonably efficiently. However, for non-time-critical tasks, normal grace periods should be used instead because their longer duration permits much higher degrees of batching, and thus much lower per-request overheads.h]hX This combination of mechanisms allows expedited grace periods to run reasonably efficiently. However, for non-time-critical tasks, normal grace periods should be used instead because their longer duration permits much higher degrees of batching, and thus much lower per-request overheads.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubeh}(h]summaryah ]h"]summaryah$]h&]uh1hhj hhhhhMubeh}(h]"expedited-grace-period-refinementsah ]h"]"expedited grace period refinementsah$]h&]uh1hhj[hhhhhKubeh}(h]#rcu-preempt-expedited-grace-periodsah ]h"]#rcu-preempt expedited grace periodsah$]h&]uh1hhhhhhhhK'ubeh}(h]1a-tour-through-tree-rcu-s-expedited-grace-periodsah ]h"]1a tour through tree_rcu's expedited grace periodsah$]h&]uh1hhhhhhhhKubeh}(h]h ]h"]h$]h&]sourcehuh1hcurrent_sourceN current_lineNsettingsdocutils.frontendValues)}(hN generatorN datestampN source_linkN source_urlN toc_backlinksjfootnote_backlinksK sectnum_xformKstrip_commentsNstrip_elements_with_classesN strip_classesN report_levelK halt_levelKexit_status_levelKdebugNwarning_streamN tracebackinput_encoding utf-8-siginput_encoding_error_handlerstrictoutput_encodingutf-8output_encoding_error_handlerjTerror_encodingutf-8error_encoding_error_handlerbackslashreplace language_codeenrecord_dependenciesNconfigN id_prefixhauto_id_prefixid dump_settingsNdump_internalsNdump_transformsNdump_pseudo_xmlNexpose_internalsNstrict_visitorN_disable_configN_sourceh _destinationN _config_files]7/var/lib/git/docbuild/linux/Documentation/docutils.confafile_insertion_enabled raw_enabledKline_length_limitM'pep_referencesN pep_base_urlhttps://peps.python.org/pep_file_url_templatepep-%04drfc_referencesN rfc_base_url&https://datatracker.ietf.org/doc/html/ tab_widthKtrim_footnote_reference_spacesyntax_highlightlong smart_quotessmartquotes_locales]character_level_inline_markupdoctitle_xform docinfo_xformKsectsubtitle_xform image_loadinglinkembed_stylesheetcloak_email_addressessection_self_linkenvNubreporterNindirect_targets]substitution_defs}substitution_names}refnames}refids}nameids}(j/j,hhjXjUj'j$jaj^jjjjjjj[ jX jjj(j%jCj@jjjju nametypes}(j/hjXj'jajjjj[ jj(jCjjuh}(j,hhhjUhj$j[j^jjjdjj jjjX jjj^ j%jj@j+jjFjju footnote_refs} citation_refs} autofootnotes]autofootnote_refs]symbol_footnotes]symbol_footnote_refs] footnotes] citations]autofootnote_startKsymbol_footnote_startK id_counter collectionsCounter}Rparse_messages]transform_messages] transformerN include_log] decorationNhhub.