<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> <html> <head><title>A Tour Through TREE_RCU's Grace-Period Memory Ordering</title> <meta HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1"> <p>August 8, 2017</p> <p>This article was contributed by Paul E. McKenney</p> <h3>Introduction</h3> <p>This document gives a rough visual overview of how Tree RCU'sgrace-period memory ordering guarantee is provided. <ol><li> <a href="#What Is Tree RCU's Grace Period Memory Ordering Guarantee?"> What Is Tree RCU's Grace Period Memory Ordering Guarantee?</a><li> <a href="#Tree RCU Grace Period Memory Ordering Building Blocks"> Tree RCU Grace Period Memory Ordering Building Blocks</a><li> <a href="#Tree RCU Grace Period Memory Ordering Components"> Tree RCU Grace Period Memory Ordering Components</a><li> <a href="#Putting It All Together">Putting It All Together</a></ol> <h3><a name="What Is Tree RCU's Grace Period Memory Ordering Guarantee?">What Is Tree RCU's Grace Period Memory Ordering Guarantee?</a></h3> <p>RCU grace periods provide extremely strong memory-ordering guaranteesfor non-idle non-offline code.Any code that happens after the end of a given RCU grace period is guaranteedto see the effects of all accesses prior to the beginning of that graceperiod that are within RCU read-side critical sections.Similarly, any code that happens before the beginning of a given RCU graceperiod is guaranteed to see the effects of all accesses following the endof that grace period that are within RCU read-side critical sections. <p>This guarantee is particularly pervasive for <tt>synchronize_sched()</tt>,for which RCU-sched read-side critical sections include any regionof code for which preemption is disabled.Given that each individual machine instruction can be thought of asan extremely small region of preemption-disabled code, one can think of<tt>synchronize_sched()</tt> as <tt>smp_mb()</tt> on steroids. <p>RCU updaters use this guarantee by splitting their updates intotwo phases, one of which is executed before the grace period andthe other of which is executed after the grace period.In the most common use case, phase one removes an element froma linked RCU-protected data structure, and phase two frees that element.For this to work, any readers that have witnessed state prior to thephase-one update (in the common case, removal) must not witness statefollowing the phase-two update (in the common case, freeing). <p>The RCU implementation provides this guarantee using a networkof lock-based critical sections, memory barriers, and per-CPUprocessing, as is described in the following sections. <h3><a name="Tree RCU Grace Period Memory Ordering Building Blocks">Tree RCU Grace Period Memory Ordering Building Blocks</a></h3> <p>The workhorse for RCU's grace-period memory ordering is thecritical section for the <tt>rcu_node</tt> structure's<tt>->lock</tt>.These critical sections use helper functions for lock acquisition, including<tt>raw_spin_lock_rcu_node()</tt>,<tt>raw_spin_lock_irq_rcu_node()</tt>, and<tt>raw_spin_lock_irqsave_rcu_node()</tt>.Their lock-release counterparts are<tt>raw_spin_unlock_rcu_node()</tt>,<tt>raw_spin_unlock_irq_rcu_node()</tt>, and<tt>raw_spin_unlock_irqrestore_rcu_node()</tt>,respectively.For completeness, a<tt>raw_spin_trylock_rcu_node()</tt>is also provided.The key point is that the lock-acquisition functions, including<tt>raw_spin_trylock_rcu_node()</tt>, all invoke<tt>smp_mb__after_unlock_lock()</tt> immediately after successfulacquisition of the lock. <p>Therefore, for any given <tt>rcu_node</tt> struction, any accesshappening before one of the above lock-release functions will be seenby all CPUs as happening before any access happening after a laterone of the above lock-acquisition functions.Furthermore, any access happening before one of theabove lock-release function on any given CPU will be seen by allCPUs as happening before any access happening after a later oneof the above lock-acquisition functions executing on that same CPU,even if the lock-release and lock-acquisition functions are operatingon different <tt>rcu_node</tt> structures.Tree RCU uses these two ordering guarantees to form an orderingnetwork among all CPUs that were in any way involved in the graceperiod, including any CPUs that came online or went offline duringthe grace period in question. <p>The following litmus test exhibits the ordering effects of theselock-acquisition and lock-release functions: <pre> 1 int x, y, z; 2 3 void task0(void) 4 { 5 raw_spin_lock_rcu_node(rnp); 6 WRITE_ONCE(x, 1); 7 r1 = READ_ONCE(y); 8 raw_spin_unlock_rcu_node(rnp); 9 }1011 void task1(void)12 {13 raw_spin_lock_rcu_node(rnp);14 WRITE_ONCE(y, 1);15 r2 = READ_ONCE(z);16 raw_spin_unlock_rcu_node(rnp);17 }1819 void task2(void)20 {21 WRITE_ONCE(z, 1);22 smp_mb();23 r3 = READ_ONCE(x);24 }2526 WARN_ON(r1 == 0 && r2 == 0 && r3 == 0);</pre> <p>The <tt>WARN_ON()</tt> is evaluated at “the end of time”,after all changes have propagated throughout the system.Without the <tt>smp_mb__after_unlock_lock()</tt> provided by theacquisition functions, this <tt>WARN_ON()</tt> could trigger, for exampleon PowerPC.The <tt>smp_mb__after_unlock_lock()</tt> invocations prevent this<tt>WARN_ON()</tt> from triggering. <p>This approach must be extended to include idle CPUs, which needRCU's grace-period memory ordering guarantee to extend to anyRCU read-side critical sections preceding and following the currentidle sojourn.This case is handled by calls to the strongly ordered<tt>atomic_add_return()</tt> read-modify-write atomic operation thatis invoked within <tt>rcu_dynticks_eqs_enter()</tt> at idle-entrytime and within <tt>rcu_dynticks_eqs_exit()</tt> at idle-exit time.The grace-period kthread invokes <tt>rcu_dynticks_snap()</tt> and<tt>rcu_dynticks_in_eqs_since()</tt> (both of which invokean <tt>atomic_add_return()</tt> of zero) to detect idle CPUs. <table><tr><th> </th></tr><tr><th align="left">Quick Quiz:</th></tr><tr><td> But what about CPUs that remain offline for the entire grace period?</td></tr><tr><th align="left">Answer:</th></tr><tr><td bgcolor="#ffffff"><font color="ffffff"> Such CPUs will be offline at the beginning of the grace period, so the grace period won't expect quiescent states from them. Races between grace-period start and CPU-hotplug operations are mediated by the CPU's leaf <tt>rcu_node</tt> structure's <tt>->lock</tt> as described above.</font></td></tr><tr><td> </td></tr></table> <p>The approach must be extended to handle one final case, thatof waking a task blocked in <tt>synchronize_rcu()</tt>.This task might be affinitied to a CPU that is not yet aware thatthe grace period has ended, and thus might not yet be subject tothe grace period's memory ordering.Therefore, there is an <tt>smp_mb()</tt> after the return from<tt>wait_for_completion()</tt> in the <tt>synchronize_rcu()</tt>code path. <table><tr><th> </th></tr><tr><th align="left">Quick Quiz:</th></tr><tr><td> What? Where??? I don't see any <tt>smp_mb()</tt> after the return from <tt>wait_for_completion()</tt>!!!</td></tr><tr><th align="left">Answer:</th></tr><tr><td bgcolor="#ffffff"><font color="ffffff"> That would be because I spotted the need for that <tt>smp_mb()</tt> during the creation of this documentation, and it is therefore unlikely to hit mainline before v4.14. Kudos to Lance Roy, Will Deacon, Peter Zijlstra, and Jonathan Cameron for asking questions that sensitized me to the rather elaborate sequence of events that demonstrate the need for this memory barrier.</font></td></tr><tr><td> </td></tr></table> <p>Tree RCU's grace--period memory-ordering guarantees rely mostheavily on the <tt>rcu_node</tt> structure's <tt>->lock</tt>field, so much so that it is necessary to abbreviate this patternin the diagrams in the next section.For example, consider the <tt>rcu_prepare_for_idle()</tt> functionshown below, which is one of several functions that enforce orderingof newly arrived RCU callbacks against future grace periods: <pre> 1 static void rcu_prepare_for_idle(void) 2 { 3 bool needwake; 4 struct rcu_data *rdp; 5 struct rcu_dynticks *rdtp = this_cpu_ptr(&rcu_dynticks); 6 struct rcu_node *rnp; 7 struct rcu_state *rsp; 8 int tne; 910 if (IS_ENABLED(CONFIG_RCU_NOCB_CPU_ALL) ||11 rcu_is_nocb_cpu(smp_processor_id()))12 return;13 tne = READ_ONCE(tick_nohz_active);14 if (tne != rdtp->tick_nohz_enabled_snap) {15 if (rcu_cpu_has_callbacks(NULL))16 invoke_rcu_core();17 rdtp->tick_nohz_enabled_snap = tne;18 return;19 }20 if (!tne)21 return;22 if (rdtp->all_lazy &&23 rdtp->nonlazy_posted != rdtp->nonlazy_posted_snap) {24 rdtp->all_lazy = false;25 rdtp->nonlazy_posted_snap = rdtp->nonlazy_posted;26 invoke_rcu_core();27 return;28 }29 if (rdtp->last_accelerate == jiffies)30 return;31 rdtp->last_accelerate = jiffies;32 for_each_rcu_flavor(rsp) {33 rdp = this_cpu_ptr(rsp->rda);34 if (rcu_segcblist_pend_cbs(&rdp->cblist))35 continue;36 rnp = rdp->mynode;37 raw_spin_lock_rcu_node(rnp);38 needwake = rcu_accelerate_cbs(rsp, rnp, rdp);39 raw_spin_unlock_rcu_node(rnp);40 if (needwake)41 rcu_gp_kthread_wake(rsp);42 }43 }</pre> <p>But the only part of <tt>rcu_prepare_for_idle()</tt> that reallymatters for this discussion are lines 37–39.We will therefore abbreviate this function as follows: </p><p><img src="rcu_node-lock.svg" alt="rcu_node-lock.svg"> <p>The box represents the <tt>rcu_node</tt> structure's <tt>->lock</tt>critical section, with the double line on top representing the additional<tt>smp_mb__after_unlock_lock()</tt>. <h3><a name="Tree RCU Grace Period Memory Ordering Components">Tree RCU Grace Period Memory Ordering Components</a></h3> <p>Tree RCU's grace-period memory-ordering guarantee is provided bya number of RCU components: <ol><li> <a href="#Callback Registry">Callback Registry</a><li> <a href="#Grace-Period Initialization">Grace-Period Initialization</a><li> <a href="#Self-Reported Quiescent States"> Self-Reported Quiescent States</a><li> <a href="#Dynamic Tick Interface">Dynamic Tick Interface</a><li> <a href="#CPU-Hotplug Interface">CPU-Hotplug Interface</a><li> <a href="Forcing Quiescent States">Forcing Quiescent States</a><li> <a href="Grace-Period Cleanup">Grace-Period Cleanup</a><li> <a href="Callback Invocation">Callback Invocation</a></ol> <p>Each of the following section looks at the corresponding componentin detail. <h4><a name="Callback Registry">Callback Registry</a></h4> <p>If RCU's grace-period guarantee is to mean anything at all, anyaccess that happens before a given invocation of <tt>call_rcu()</tt>must also happen before the corresponding grace period.The implementation of this portion of RCU's grace period guaranteeis shown in the following figure: </p><p><img src="TreeRCU-callback-registry.svg" alt="TreeRCU-callback-registry.svg"> <p>Because <tt>call_rcu()</tt> normally acts only on CPU-local state,it provides no ordering guarantees, either for itself or forphase one of the update (which again will usually be removal ofan element from an RCU-protected data structure).It simply enqueues the <tt>rcu_head</tt> structure on a per-CPU list,which cannot become associated with a grace period until a latercall to <tt>rcu_accelerate_cbs()</tt>, as shown in the diagram above. <p>One set of code paths shown on the left invokes<tt>rcu_accelerate_cbs()</tt> via<tt>note_gp_changes()</tt>, either directly from <tt>call_rcu()</tt> (ifthe current CPU is inundated with queued <tt>rcu_head</tt> structures)or more likely from an <tt>RCU_SOFTIRQ</tt> handler.Another code path in the middle is taken only in kernels built with<tt>CONFIG_RCU_FAST_NO_HZ=y</tt>, which invokes<tt>rcu_accelerate_cbs()</tt> via <tt>rcu_prepare_for_idle()</tt>.The final code path on the right is taken only in kernels built with<tt>CONFIG_HOTPLUG_CPU=y</tt>, which invokes<tt>rcu_accelerate_cbs()</tt> via<tt>rcu_advance_cbs()</tt>, <tt>rcu_migrate_callbacks</tt>,<tt>rcutree_migrate_callbacks()</tt>, and <tt>takedown_cpu()</tt>,which in turn is invoked on a surviving CPU after the outgoingCPU has been completely offlined. <p>There are a few other code paths within grace-period processingthat opportunistically invoke <tt>rcu_accelerate_cbs()</tt>.However, either way, all of the CPU's recently queued <tt>rcu_head</tt>structures are associated with a future grace-period number underthe protection of the CPU's lead <tt>rcu_node</tt> structure's<tt>->lock</tt>.In all cases, there is full ordering against any prior critical sectionfor that same <tt>rcu_node</tt> structure's <tt>->lock</tt>, andalso full ordering against any of the current task's or CPU's prior criticalsections for any <tt>rcu_node</tt> structure's <tt>->lock</tt>. <p>The next section will show how this ordering ensures that anyaccesses prior to the <tt>call_rcu()</tt> (particularly including phaseone of the update)happen before the start of the corresponding grace period. <table><tr><th> </th></tr><tr><th align="left">Quick Quiz:</th></tr><tr><td> But what about <tt>synchronize_rcu()</tt>?</td></tr><tr><th align="left">Answer:</th></tr><tr><td bgcolor="#ffffff"><font color="ffffff"> The <tt>synchronize_rcu()</tt> passes <tt>call_rcu()</tt> to <tt>wait_rcu_gp()</tt>, which invokes it. So either way, it eventually comes down to <tt>call_rcu()</tt>.</font></td></tr><tr><td> </td></tr></table> <h4><a name="Grace-Period Initialization">Grace-Period Initialization</a></h4> <p>Grace-period initialization is carried out bythe grace-period kernel thread, which makes several passes over the<tt>rcu_node</tt> tree within the <tt>rcu_gp_init()</tt> function.This means that showing the full flow of ordering through thegrace-period computation will require duplicating this tree.If you find this confusing, please note that the state of the<tt>rcu_node</tt> changes over time, just like Heraclitus's river.However, to keep the <tt>rcu_node</tt> river tractable, thegrace-period kernel thread's traversals are presented in multipleparts, starting in this section with the various phases ofgrace-period initialization. <p>The first ordering-related grace-period initialization action is toadvance the <tt>rcu_state</tt> structure's <tt>->gp_seq</tt>grace-period-number counter, as shown below: </p><p><img src="TreeRCU-gp-init-1.svg" alt="TreeRCU-gp-init-1.svg" width="75%"> <p>The actual increment is carried out using <tt>smp_store_release()</tt>,which helps reject false-positive RCU CPU stall detection.Note that only the root <tt>rcu_node</tt> structure is touched. <p>The first pass through the <tt>rcu_node</tt> tree updates bitmasksbased on CPUs having come online or gone offline since the start ofthe previous grace period.In the common case where the number of online CPUs for this <tt>rcu_node</tt>structure has not transitioned to or from zero,this pass will scan only the leaf <tt>rcu_node</tt> structures.However, if the number of online CPUs for a given leaf <tt>rcu_node</tt>structure has transitioned from zero,<tt>rcu_init_new_rnp()</tt> will be invoked for the first incoming CPU.Similarly, if the number of online CPUs for a given leaf <tt>rcu_node</tt>structure has transitioned to zero,<tt>rcu_cleanup_dead_rnp()</tt> will be invoked for the last outgoing CPU.The diagram below shows the path of ordering if the leftmost<tt>rcu_node</tt> structure onlines its first CPU and if the next<tt>rcu_node</tt> structure has no online CPUs(or, alternatively if the leftmost <tt>rcu_node</tt> structure offlinesits last CPU and if the next <tt>rcu_node</tt> structure has no online CPUs). </p><p><img src="TreeRCU-gp-init-2.svg" alt="TreeRCU-gp-init-1.svg" width="75%"> <p>The final <tt>rcu_gp_init()</tt> pass through the <tt>rcu_node</tt>tree traverses breadth-first, setting each <tt>rcu_node</tt> structure's<tt>->gp_seq</tt> field to the newly advanced value from the<tt>rcu_state</tt> structure, as shown in the following diagram. </p><p><img src="TreeRCU-gp-init-3.svg" alt="TreeRCU-gp-init-1.svg" width="75%"> <p>This change will also cause each CPU's next call to<tt>__note_gp_changes()</tt>to notice that a new grace period has started, as described in the nextsection.But because the grace-period kthread started the grace period at theroot (with the advancing of the <tt>rcu_state</tt> structure's<tt>->gp_seq</tt> field) before setting each leaf <tt>rcu_node</tt>structure's <tt>->gp_seq</tt> field, each CPU's observation ofthe start of the grace period will happen after the actual startof the grace period. <table><tr><th> </th></tr><tr><th align="left">Quick Quiz:</th></tr><tr><td> But what about the CPU that started the grace period? Why wouldn't it see the start of the grace period right when it started that grace period?</td></tr><tr><th align="left">Answer:</th></tr><tr><td bgcolor="#ffffff"><font color="ffffff"> In some deep philosophical and overly anthromorphized sense, yes, the CPU starting the grace period is immediately aware of having done so. However, if we instead assume that RCU is not self-aware, then even the CPU starting the grace period does not really become aware of the start of this grace period until its first call to <tt>__note_gp_changes()</tt>. On the other hand, this CPU potentially gets early notification because it invokes <tt>__note_gp_changes()</tt> during its last <tt>rcu_gp_init()</tt> pass through its leaf <tt>rcu_node</tt> structure.</font></td></tr><tr><td> </td></tr></table> <h4><a name="Self-Reported Quiescent States">Self-Reported Quiescent States</a></h4> <p>When all entities that might block the grace period have reportedquiescent states (or as described in a later section, had quiescentstates reported on their behalf), the grace period can end.Online non-idle CPUs report their own quiescent states, as shownin the following diagram: </p><p><img src="TreeRCU-qs.svg" alt="TreeRCU-qs.svg" width="75%"> <p>This is for the last CPU to report a quiescent state, which signalsthe end of the grace period.Earlier quiescent states would push up the <tt>rcu_node</tt> treeonly until they encountered an <tt>rcu_node</tt> structure thatis waiting for additional quiescent states.However, ordering is nevertheless preserved because some later quiescentstate will acquire that <tt>rcu_node</tt> structure's <tt>->lock</tt>. <p>Any number of events can lead up to a CPU invoking<tt>note_gp_changes</tt> (or alternatively, directly invoking<tt>__note_gp_changes()</tt>), at which point that CPU will noticethe start of a new grace period while holding its leaf<tt>rcu_node</tt> lock.Therefore, all execution shown in this diagram happens after thestart of the grace period.In addition, this CPU will consider any RCU read-side criticalsection that started before the invocation of <tt>__note_gp_changes()</tt>to have started before the grace period, and thus a criticalsection that the grace period must wait on. <table><tr><th> </th></tr><tr><th align="left">Quick Quiz:</th></tr><tr><td> But a RCU read-side critical section might have started after the beginning of the grace period (the advancing of <tt>->gp_seq</tt> from earlier), so why should the grace period wait on such a critical section?</td></tr><tr><th align="left">Answer:</th></tr><tr><td bgcolor="#ffffff"><font color="ffffff"> It is indeed not necessary for the grace period to wait on such a critical section. However, it is permissible to wait on it. And it is furthermore important to wait on it, as this lazy approach is far more scalable than a “big bang” all-at-once grace-period start could possibly be.</font></td></tr><tr><td> </td></tr></table> <p>If the CPU does a context switch, a quiescent state will benoted by <tt>rcu_node_context_switch()</tt> on the left.On the other hand, if the CPU takes a scheduler-clock interruptwhile executing in usermode, a quiescent state will be noted by<tt>rcu_check_callbacks()</tt> on the right.Either way, the passage through a quiescent state will be notedin a per-CPU variable. <p>The next time an <tt>RCU_SOFTIRQ</tt> handler executes onthis CPU (for example, after the next scheduler-clockinterrupt), <tt>__rcu_process_callbacks()</tt> will invoke<tt>rcu_check_quiescent_state()</tt>, which will notice therecorded quiescent state, and invoke<tt>rcu_report_qs_rdp()</tt>.If <tt>rcu_report_qs_rdp()</tt> verifies that the quiescent statereally does apply to the current grace period, it invokes<tt>rcu_report_rnp()</tt> which traverses up the <tt>rcu_node</tt>Lines 1–500 of 705. Load more
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> <html> <head><title>A Tour Through TREE_RCU's Grace-Period Memory Ordering</title> <meta HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1"> <p>August 8, 2017</p> <p>This article was contributed by Paul E. McKenney</p> <h3>Introduction</h3> <p>This document gives a rough visual overview of how Tree RCU's grace-period memory ordering guarantee is provided. <ol> <li> <a href="#What Is Tree RCU's Grace Period Memory Ordering Guarantee?"> What Is Tree RCU's Grace Period Memory Ordering Guarantee?</a> <li> <a href="#Tree RCU Grace Period Memory Ordering Building Blocks"> Tree RCU Grace Period Memory Ordering Building Blocks</a> <li> <a href="#Tree RCU Grace Period Memory Ordering Components"> Tree RCU Grace Period Memory Ordering Components</a> <li> <a href="#Putting It All Together">Putting It All Together</a> </ol> <h3><a name="What Is Tree RCU's Grace Period Memory Ordering Guarantee?"> What Is Tree RCU's Grace Period Memory Ordering Guarantee?</a></h3> <p>RCU grace periods provide extremely strong memory-ordering guarantees for non-idle non-offline code. Any code that happens after the end of a given RCU grace period is guaranteed to see the effects of all accesses prior to the beginning of that grace period that are within RCU read-side critical sections. Similarly, any code that happens before the beginning of a given RCU grace period is guaranteed to see the effects of all accesses following the end of that grace period that are within RCU read-side critical sections. <p>This guarantee is particularly pervasive for <tt>synchronize_sched()</tt>, for which RCU-sched read-side critical sections include any region of code for which preemption is disabled. Given that each individual machine instruction can be thought of as an extremely small region of preemption-disabled code, one can think of <tt>synchronize_sched()</tt> as <tt>smp_mb()</tt> on steroids. <p>RCU updaters use this guarantee by splitting their updates into two phases, one of which is executed before the grace period and the other of which is executed after the grace period. In the most common use case, phase one removes an element from a linked RCU-protected data structure, and phase two frees that element. For this to work, any readers that have witnessed state prior to the phase-one update (in the common case, removal) must not witness state following the phase-two update (in the common case, freeing). <p>The RCU implementation provides this guarantee using a network of lock-based critical sections, memory barriers, and per-CPU processing, as is described in the following sections. <h3><a name="Tree RCU Grace Period Memory Ordering Building Blocks"> Tree RCU Grace Period Memory Ordering Building Blocks</a></h3> <p>The workhorse for RCU's grace-period memory ordering is the critical section for the <tt>rcu_node</tt> structure's <tt>->lock</tt>. These critical sections use helper functions for lock acquisition, including <tt>raw_spin_lock_rcu_node()</tt>, <tt>raw_spin_lock_irq_rcu_node()</tt>, and <tt>raw_spin_lock_irqsave_rcu_node()</tt>. Their lock-release counterparts are <tt>raw_spin_unlock_rcu_node()</tt>, <tt>raw_spin_unlock_irq_rcu_node()</tt>, and <tt>raw_spin_unlock_irqrestore_rcu_node()</tt>, respectively. For completeness, a <tt>raw_spin_trylock_rcu_node()</tt> is also provided. The key point is that the lock-acquisition functions, including <tt>raw_spin_trylock_rcu_node()</tt>, all invoke <tt>smp_mb__after_unlock_lock()</tt> immediately after successful acquisition of the lock. <p>Therefore, for any given <tt>rcu_node</tt> struction, any access happening before one of the above lock-release functions will be seen by all CPUs as happening before any access happening after a later one of the above lock-acquisition functions. Furthermore, any access happening before one of the above lock-release function on any given CPU will be seen by all CPUs as happening before any access happening after a later one of the above lock-acquisition functions executing on that same CPU, even if the lock-release and lock-acquisition functions are operating on different <tt>rcu_node</tt> structures. Tree RCU uses these two ordering guarantees to form an ordering network among all CPUs that were in any way involved in the grace period, including any CPUs that came online or went offline during the grace period in question. <p>The following litmus test exhibits the ordering effects of these lock-acquisition and lock-release functions: <pre> 1 int x, y, z; 2 3 void task0(void) 4 { 5 raw_spin_lock_rcu_node(rnp); 6 WRITE_ONCE(x, 1); 7 r1 = READ_ONCE(y); 8 raw_spin_unlock_rcu_node(rnp); 9 } 10 11 void task1(void) 12 { 13 raw_spin_lock_rcu_node(rnp); 14 WRITE_ONCE(y, 1); 15 r2 = READ_ONCE(z); 16 raw_spin_unlock_rcu_node(rnp); 17 } 18 19 void task2(void) 20 { 21 WRITE_ONCE(z, 1); 22 smp_mb(); 23 r3 = READ_ONCE(x); 24 } 25 26 WARN_ON(r1 == 0 && r2 == 0 && r3 == 0); </pre> <p>The <tt>WARN_ON()</tt> is evaluated at “the end of time”, after all changes have propagated throughout the system. Without the <tt>smp_mb__after_unlock_lock()</tt> provided by the acquisition functions, this <tt>WARN_ON()</tt> could trigger, for example on PowerPC. The <tt>smp_mb__after_unlock_lock()</tt> invocations prevent this <tt>WARN_ON()</tt> from triggering. <p>This approach must be extended to include idle CPUs, which need RCU's grace-period memory ordering guarantee to extend to any RCU read-side critical sections preceding and following the current idle sojourn. This case is handled by calls to the strongly ordered <tt>atomic_add_return()</tt> read-modify-write atomic operation that is invoked within <tt>rcu_dynticks_eqs_enter()</tt> at idle-entry time and within <tt>rcu_dynticks_eqs_exit()</tt> at idle-exit time. The grace-period kthread invokes <tt>rcu_dynticks_snap()</tt> and <tt>rcu_dynticks_in_eqs_since()</tt> (both of which invoke an <tt>atomic_add_return()</tt> of zero) to detect idle CPUs. <table> <tr><th> </th></tr> <tr><th align="left">Quick Quiz:</th></tr> <tr><td> But what about CPUs that remain offline for the entire grace period? </td></tr> <tr><th align="left">Answer:</th></tr> <tr><td bgcolor="#ffffff"><font color="ffffff"> Such CPUs will be offline at the beginning of the grace period, so the grace period won't expect quiescent states from them. Races between grace-period start and CPU-hotplug operations are mediated by the CPU's leaf <tt>rcu_node</tt> structure's <tt>->lock</tt> as described above. </font></td></tr> <tr><td> </td></tr> </table> <p>The approach must be extended to handle one final case, that of waking a task blocked in <tt>synchronize_rcu()</tt>. This task might be affinitied to a CPU that is not yet aware that the grace period has ended, and thus might not yet be subject to the grace period's memory ordering. Therefore, there is an <tt>smp_mb()</tt> after the return from <tt>wait_for_completion()</tt> in the <tt>synchronize_rcu()</tt> code path. <table> <tr><th> </th></tr> <tr><th align="left">Quick Quiz:</th></tr> <tr><td> What? Where??? I don't see any <tt>smp_mb()</tt> after the return from <tt>wait_for_completion()</tt>!!! </td></tr> <tr><th align="left">Answer:</th></tr> <tr><td bgcolor="#ffffff"><font color="ffffff"> That would be because I spotted the need for that <tt>smp_mb()</tt> during the creation of this documentation, and it is therefore unlikely to hit mainline before v4.14. Kudos to Lance Roy, Will Deacon, Peter Zijlstra, and Jonathan Cameron for asking questions that sensitized me to the rather elaborate sequence of events that demonstrate the need for this memory barrier. </font></td></tr> <tr><td> </td></tr> </table> <p>Tree RCU's grace--period memory-ordering guarantees rely most heavily on the <tt>rcu_node</tt> structure's <tt>->lock</tt> field, so much so that it is necessary to abbreviate this pattern in the diagrams in the next section. For example, consider the <tt>rcu_prepare_for_idle()</tt> function shown below, which is one of several functions that enforce ordering of newly arrived RCU callbacks against future grace periods: <pre> 1 static void rcu_prepare_for_idle(void) 2 { 3 bool needwake; 4 struct rcu_data *rdp; 5 struct rcu_dynticks *rdtp = this_cpu_ptr(&rcu_dynticks); 6 struct rcu_node *rnp; 7 struct rcu_state *rsp; 8 int tne; 9 10 if (IS_ENABLED(CONFIG_RCU_NOCB_CPU_ALL) || 11 rcu_is_nocb_cpu(smp_processor_id())) 12 return; 13 tne = READ_ONCE(tick_nohz_active); 14 if (tne != rdtp->tick_nohz_enabled_snap) { 15 if (rcu_cpu_has_callbacks(NULL)) 16 invoke_rcu_core(); 17 rdtp->tick_nohz_enabled_snap = tne; 18 return; 19 } 20 if (!tne) 21 return; 22 if (rdtp->all_lazy && 23 rdtp->nonlazy_posted != rdtp->nonlazy_posted_snap) { 24 rdtp->all_lazy = false; 25 rdtp->nonlazy_posted_snap = rdtp->nonlazy_posted; 26 invoke_rcu_core(); 27 return; 28 } 29 if (rdtp->last_accelerate == jiffies) 30 return; 31 rdtp->last_accelerate = jiffies; 32 for_each_rcu_flavor(rsp) { 33 rdp = this_cpu_ptr(rsp->rda); 34 if (rcu_segcblist_pend_cbs(&rdp->cblist)) 35 continue; 36 rnp = rdp->mynode; 37 raw_spin_lock_rcu_node(rnp); 38 needwake = rcu_accelerate_cbs(rsp, rnp, rdp); 39 raw_spin_unlock_rcu_node(rnp); 40 if (needwake) 41 rcu_gp_kthread_wake(rsp); 42 } 43 } </pre> <p>But the only part of <tt>rcu_prepare_for_idle()</tt> that really matters for this discussion are lines 37–39. We will therefore abbreviate this function as follows: </p><p><img src="rcu_node-lock.svg" alt="rcu_node-lock.svg"> <p>The box represents the <tt>rcu_node</tt> structure's <tt>->lock</tt> critical section, with the double line on top representing the additional <tt>smp_mb__after_unlock_lock()</tt>. <h3><a name="Tree RCU Grace Period Memory Ordering Components"> Tree RCU Grace Period Memory Ordering Components</a></h3> <p>Tree RCU's grace-period memory-ordering guarantee is provided by a number of RCU components: <ol> <li> <a href="#Callback Registry">Callback Registry</a> <li> <a href="#Grace-Period Initialization">Grace-Period Initialization</a> <li> <a href="#Self-Reported Quiescent States"> Self-Reported Quiescent States</a> <li> <a href="#Dynamic Tick Interface">Dynamic Tick Interface</a> <li> <a href="#CPU-Hotplug Interface">CPU-Hotplug Interface</a> <li> <a href="Forcing Quiescent States">Forcing Quiescent States</a> <li> <a href="Grace-Period Cleanup">Grace-Period Cleanup</a> <li> <a href="Callback Invocation">Callback Invocation</a> </ol> <p>Each of the following section looks at the corresponding component in detail. <h4><a name="Callback Registry">Callback Registry</a></h4> <p>If RCU's grace-period guarantee is to mean anything at all, any access that happens before a given invocation of <tt>call_rcu()</tt> must also happen before the corresponding grace period. The implementation of this portion of RCU's grace period guarantee is shown in the following figure: </p><p><img src="TreeRCU-callback-registry.svg" alt="TreeRCU-callback-registry.svg"> <p>Because <tt>call_rcu()</tt> normally acts only on CPU-local state, it provides no ordering guarantees, either for itself or for phase one of the update (which again will usually be removal of an element from an RCU-protected data structure). It simply enqueues the <tt>rcu_head</tt> structure on a per-CPU list, which cannot become associated with a grace period until a later call to <tt>rcu_accelerate_cbs()</tt>, as shown in the diagram above. <p>One set of code paths shown on the left invokes <tt>rcu_accelerate_cbs()</tt> via <tt>note_gp_changes()</tt>, either directly from <tt>call_rcu()</tt> (if the current CPU is inundated with queued <tt>rcu_head</tt> structures) or more likely from an <tt>RCU_SOFTIRQ</tt> handler. Another code path in the middle is taken only in kernels built with <tt>CONFIG_RCU_FAST_NO_HZ=y</tt>, which invokes <tt>rcu_accelerate_cbs()</tt> via <tt>rcu_prepare_for_idle()</tt>. The final code path on the right is taken only in kernels built with <tt>CONFIG_HOTPLUG_CPU=y</tt>, which invokes <tt>rcu_accelerate_cbs()</tt> via <tt>rcu_advance_cbs()</tt>, <tt>rcu_migrate_callbacks</tt>, <tt>rcutree_migrate_callbacks()</tt>, and <tt>takedown_cpu()</tt>, which in turn is invoked on a surviving CPU after the outgoing CPU has been completely offlined. <p>There are a few other code paths within grace-period processing that opportunistically invoke <tt>rcu_accelerate_cbs()</tt>. However, either way, all of the CPU's recently queued <tt>rcu_head</tt> structures are associated with a future grace-period number under the protection of the CPU's lead <tt>rcu_node</tt> structure's <tt>->lock</tt>. In all cases, there is full ordering against any prior critical section for that same <tt>rcu_node</tt> structure's <tt>->lock</tt>, and also full ordering against any of the current task's or CPU's prior critical sections for any <tt>rcu_node</tt> structure's <tt>->lock</tt>. <p>The next section will show how this ordering ensures that any accesses prior to the <tt>call_rcu()</tt> (particularly including phase one of the update) happen before the start of the corresponding grace period. <table> <tr><th> </th></tr> <tr><th align="left">Quick Quiz:</th></tr> <tr><td> But what about <tt>synchronize_rcu()</tt>? </td></tr> <tr><th align="left">Answer:</th></tr> <tr><td bgcolor="#ffffff"><font color="ffffff"> The <tt>synchronize_rcu()</tt> passes <tt>call_rcu()</tt> to <tt>wait_rcu_gp()</tt>, which invokes it. So either way, it eventually comes down to <tt>call_rcu()</tt>. </font></td></tr> <tr><td> </td></tr> </table> <h4><a name="Grace-Period Initialization">Grace-Period Initialization</a></h4> <p>Grace-period initialization is carried out by the grace-period kernel thread, which makes several passes over the <tt>rcu_node</tt> tree within the <tt>rcu_gp_init()</tt> function. This means that showing the full flow of ordering through the grace-period computation will require duplicating this tree. If you find this confusing, please note that the state of the <tt>rcu_node</tt> changes over time, just like Heraclitus's river. However, to keep the <tt>rcu_node</tt> river tractable, the grace-period kernel thread's traversals are presented in multiple parts, starting in this section with the various phases of grace-period initialization. <p>The first ordering-related grace-period initialization action is to advance the <tt>rcu_state</tt> structure's <tt>->gp_seq</tt> grace-period-number counter, as shown below: </p><p><img src="TreeRCU-gp-init-1.svg" alt="TreeRCU-gp-init-1.svg" width="75%"> <p>The actual increment is carried out using <tt>smp_store_release()</tt>, which helps reject false-positive RCU CPU stall detection. Note that only the root <tt>rcu_node</tt> structure is touched. <p>The first pass through the <tt>rcu_node</tt> tree updates bitmasks based on CPUs having come online or gone offline since the start of the previous grace period. In the common case where the number of online CPUs for this <tt>rcu_node</tt> structure has not transitioned to or from zero, this pass will scan only the leaf <tt>rcu_node</tt> structures. However, if the number of online CPUs for a given leaf <tt>rcu_node</tt> structure has transitioned from zero, <tt>rcu_init_new_rnp()</tt> will be invoked for the first incoming CPU. Similarly, if the number of online CPUs for a given leaf <tt>rcu_node</tt> structure has transitioned to zero, <tt>rcu_cleanup_dead_rnp()</tt> will be invoked for the last outgoing CPU. The diagram below shows the path of ordering if the leftmost <tt>rcu_node</tt> structure onlines its first CPU and if the next <tt>rcu_node</tt> structure has no online CPUs (or, alternatively if the leftmost <tt>rcu_node</tt> structure offlines its last CPU and if the next <tt>rcu_node</tt> structure has no online CPUs). </p><p><img src="TreeRCU-gp-init-2.svg" alt="TreeRCU-gp-init-1.svg" width="75%"> <p>The final <tt>rcu_gp_init()</tt> pass through the <tt>rcu_node</tt> tree traverses breadth-first, setting each <tt>rcu_node</tt> structure's <tt>->gp_seq</tt> field to the newly advanced value from the <tt>rcu_state</tt> structure, as shown in the following diagram. </p><p><img src="TreeRCU-gp-init-3.svg" alt="TreeRCU-gp-init-1.svg" width="75%"> <p>This change will also cause each CPU's next call to <tt>__note_gp_changes()</tt> to notice that a new grace period has started, as described in the next section. But because the grace-period kthread started the grace period at the root (with the advancing of the <tt>rcu_state</tt> structure's <tt>->gp_seq</tt> field) before setting each leaf <tt>rcu_node</tt> structure's <tt>->gp_seq</tt> field, each CPU's observation of the start of the grace period will happen after the actual start of the grace period. <table> <tr><th> </th></tr> <tr><th align="left">Quick Quiz:</th></tr> <tr><td> But what about the CPU that started the grace period? Why wouldn't it see the start of the grace period right when it started that grace period? </td></tr> <tr><th align="left">Answer:</th></tr> <tr><td bgcolor="#ffffff"><font color="ffffff"> In some deep philosophical and overly anthromorphized sense, yes, the CPU starting the grace period is immediately aware of having done so. However, if we instead assume that RCU is not self-aware, then even the CPU starting the grace period does not really become aware of the start of this grace period until its first call to <tt>__note_gp_changes()</tt>. On the other hand, this CPU potentially gets early notification because it invokes <tt>__note_gp_changes()</tt> during its last <tt>rcu_gp_init()</tt> pass through its leaf <tt>rcu_node</tt> structure. </font></td></tr> <tr><td> </td></tr> </table> <h4><a name="Self-Reported Quiescent States"> Self-Reported Quiescent States</a></h4> <p>When all entities that might block the grace period have reported quiescent states (or as described in a later section, had quiescent states reported on their behalf), the grace period can end. Online non-idle CPUs report their own quiescent states, as shown in the following diagram: </p><p><img src="TreeRCU-qs.svg" alt="TreeRCU-qs.svg" width="75%"> <p>This is for the last CPU to report a quiescent state, which signals the end of the grace period. Earlier quiescent states would push up the <tt>rcu_node</tt> tree only until they encountered an <tt>rcu_node</tt> structure that is waiting for additional quiescent states. However, ordering is nevertheless preserved because some later quiescent state will acquire that <tt>rcu_node</tt> structure's <tt>->lock</tt>. <p>Any number of events can lead up to a CPU invoking <tt>note_gp_changes</tt> (or alternatively, directly invoking <tt>__note_gp_changes()</tt>), at which point that CPU will notice the start of a new grace period while holding its leaf <tt>rcu_node</tt> lock. Therefore, all execution shown in this diagram happens after the start of the grace period. In addition, this CPU will consider any RCU read-side critical section that started before the invocation of <tt>__note_gp_changes()</tt> to have started before the grace period, and thus a critical section that the grace period must wait on. <table> <tr><th> </th></tr> <tr><th align="left">Quick Quiz:</th></tr> <tr><td> But a RCU read-side critical section might have started after the beginning of the grace period (the advancing of <tt>->gp_seq</tt> from earlier), so why should the grace period wait on such a critical section? </td></tr> <tr><th align="left">Answer:</th></tr> <tr><td bgcolor="#ffffff"><font color="ffffff"> It is indeed not necessary for the grace period to wait on such a critical section. However, it is permissible to wait on it. And it is furthermore important to wait on it, as this lazy approach is far more scalable than a “big bang” all-at-once grace-period start could possibly be. </font></td></tr> <tr><td> </td></tr> </table> <p>If the CPU does a context switch, a quiescent state will be noted by <tt>rcu_node_context_switch()</tt> on the left. On the other hand, if the CPU takes a scheduler-clock interrupt while executing in usermode, a quiescent state will be noted by <tt>rcu_check_callbacks()</tt> on the right. Either way, the passage through a quiescent state will be noted in a per-CPU variable. <p>The next time an <tt>RCU_SOFTIRQ</tt> handler executes on this CPU (for example, after the next scheduler-clock interrupt), <tt>__rcu_process_callbacks()</tt> will invoke <tt>rcu_check_quiescent_state()</tt>, which will notice the recorded quiescent state, and invoke <tt>rcu_report_qs_rdp()</tt>. If <tt>rcu_report_qs_rdp()</tt> verifies that the quiescent state really does apply to the current grace period, it invokes <tt>rcu_report_rnp()</tt> which traverses up the <tt>rcu_node</tt>