rcu/tree: Correctly handle single cpu check in rcu_blocking_is_gp
PATCH v2 1/1 rcu/tree: Correctly handle single cpu check in rcu_blocking_is_gp
Currently, for non-preempt kernels (with CONFIG_PREEMPTION=n), rcu_blocking_is_gp() checks (with preemption disabled), whether there is only one cpu online. It uses num_online_cpus() to decide whether only one cpu is online. If there is only single cpu online, synchronize_rcu() is optimized to return without doing all the work to wait for grace period. However, there are few issues with the num_online_cpus() check used, for transition of __num_online_cpus from 2 -> 1 for cpu down path and 1 -> 2 for cpu up path.
1. For CPU path, num_online_cpus() does a atomic_read(&__num_online_cpus). As hotplug locks are not held, this does not ensure that new incoming cpus update of the count is visible. This can result in read side section on new incoming cpu, observe updates which should not be visible beyond the grace period corresponding to synchronize_rcu().
For e.g. below litmus test, where P0 process corresponds to synchronize_rcu() and P1 corresponds to new online cpu, has positive witnesses; confirming the possibility of read side section to extend before and after the grace period, thereby breaking guarantees provided by synchronize_rcu().
{
int x = 0;
atomic_t numonline = ATOMIC_INIT(1);
}
P0(int *x, atomic_t *numonline)
{
int r0;
WRITE_ONCE(*x, 1);
r0 = atomic_read(numonline);
if (r0 == 1) {
smp_mb();
} else {
synchronize_rcu();
}
WRITE_ONCE(*x, 2);
}
P1(int *x, atomic_t *numonline)
{
int r0; int r1; atomic_inc(numonline);
smp_mb();
rcu_read_lock();
r0 = READ_ONCE(*x);
smp_rmb();
r1 = READ_ONCE(*x);
rcu_read_unlock();}
locations [x;numonline;]
exists (1:r0=0 /\ 1:r1=2)
2. Second problem is, the same early exit, from synchronize_rcu() does not provide full ordering, memory barrier, w.r.t. memory accesses after synchronize_rcu() call.
3. Third, more important issue is related to outgoing cpu. Checking only for __num_online_cpus with preemotion disabled isn't sufficient for RCU, as, on completion of CPUHP_TEARDOWN_CPU stop machine (which clears outgoing cpu from __num_online_cpus, the CPU switches to idle task. So, checking only for __num_online_cpus does not consider RCU read side sections in scheduler code (before switching to idle task) and any potential read side sections in idle task, before final RCU-quiesce entry into cpuhp_report_idle_dead() -> rcu_report_dead().
The problem here is, changes to number of online cpus happen from places that are not helpful for lockless access from synchronize_rcu() :
for offlining cpu, it happens from stop machine on that cpu, before cpu is marked offline in rcu bookkeeping, resulting in unwatched RCU critical sections; and for onlining cpu, it happens on the new cpu, after it is online, resulting in visibility issues.
To handle these issues, add a new rcu_state member n_online_cpus, to keep count of the current number of online cpus. This counter is incremented early in the CPU-hotplug CPU-online process, that is, on the control CPU, prior to the new CPU coming online. For outgoing cpu, counter is decremented on the control cpu, after the offlining cpu is long gone.
Update of this counter from control cpu means that, if rcu_state. n_online_cpus is equal to one in rcu_blocking_is_gp(), below is guaranteed:
a. There is only one CPU, and that CPU sees all prior accesses made by
any CPU that was online at the time of its access. Furthermore, rcu_state.n_online_cpus value cannot change, as CONFIG_PREEMPTION=n.
b. All later CPUs (both this one and any that come online later on) are
guaranteed to see all accesses by any CPU prior to this point in the code. The CPU-hotplug code provides the required memory barriers to ensure this.
This eliminates the need for any additional memory barriers for the single cpu online case; it also eliminates the early counter update and visibility problems with __num_online_cpus value. For multiple cpu online case, synchronize_rcu() does all the work of grace period initiation and wait and that provides the required ordering gurantees. rcu_state.n_online_cpus update from control cpu would result in unnecessary calls to synchronize_rcu() slow path during the CPU-online process, but that should have negligible impact.
---
Changes in V2:
- Make rcu_state.n_online_cpus int, instead of atomic_t.
- Move counter updates to rcutree_prepare_cpu() and rcutree_dead_cpu().
- Update commit log and code comments to highlight single-cpu behavior.
kernel/rcu/tree.c | 21 ++++++++++++++++++++- kernel/rcu/tree.h | 1 + 2 files changed, 21 insertions(+), 1 deletion(-)
kernel/rcu/tree.c +20 -1
@@ -2405,6 +2405,7 @@ int rcutree_dead_cpu(unsigned int cpu)if (!IS_ENABLED (CONFIG_HOTPLUG_CPU ))return 0 ; +WRITE_ONCE (rcu_state.n_online_cpus, rcu_state.n_online_cpus -1 );/* Adjust any no-longer-needed kthreads. */ rcu_boost_kthread_setaffinity (rnp,-1 );/* Do any needed no-CB deferred wakeups from this CPU. */
@@ -3610,7 +3611,20 @@ static int rcu_blocking_is_gp(void)return rcu_scheduler_active ==RCU_SCHEDULER_INACTIVE ;might_sleep ();/* Check for RCU read-side critical section. */ preempt_disable (); - ret =num_online_cpus () <=1 ; +/* +* If rcu_state.n_online_cpus is equal to one, there is only one CPU, +* and that CPU sees all prior accesses made by any CPU that was +* online at the time of its access. Furthermore, if rcu_state. +* n_online_cpus is equal to one, its value cannot change until +* after the preempt_enable() below. +* +* Furthermore, if n_online_cpus is equal to one here, all later CPUs +* (both this one and any that come online later on) are guaranteed to +* see all accesses by any CPU prior to this point in the code, +* without the need for additional memory barriers. Those memory +* barriers are provided by CPU-hotplug code. +*/ + ret =READ_ONCE (rcu_state.n_online_cpus) <=1 ;preempt_enable ();return ret; }
@@ -3655,6 +3669,10 @@ void synchronize_rcu(void)lock_is_held (&rcu_sched_lock_map), "Illegal synchronize_rcu() in RCU read-side critical section");if (rcu_blocking_is_gp ()) +/* +* Single cpu-state (see comment in rcu_blocking_is_gp()) +* guarantees memory ordering. +*/ return ;if (rcu_gp_is_expedited ())synchronize_rcu_expedited ();
@@ -3996,6 +4014,7 @@ int rcutree_prepare_cpu(unsigned int cpu)raw_spin_unlock_irqrestore_rcu_node (rnp, flags);rcu_prepare_kthreads (cpu);rcu_spawn_cpu_nocb_kthread (cpu); +WRITE_ONCE (rcu_state.n_online_cpus, rcu_state.n_online_cpus +1 );return 0 ; }
kernel/rcu/tree.h +1 -0
@@ -298,6 +298,7 @@ struct rcu_state {/* Hierarchy levels (+1 to */ /* shut bogus gcc warning) */ int ncpus;/* # CPUs seen so far. */ +int n_online_cpus;/* # CPUs online for RCU. */ /* The following fields are guarded by the root rcu_node's lock. */
Signature · 2 lines
The Qualcomm Innovation Center, Inc. is a member of the Code Aurora Forum, a Linux Foundation Collaborative Project
Paul E. McKenney
maintainerQuoted 9 lines · Neeraj Upadhyay
Currently, for non-preempt kernels (with
CONFIG_PREEMPTION=n),rcu_blocking_is_gp()checks (with preemption disabled), whether there is only one cpu online. It usesnum_online_cpus()to decide whether only one cpu is online. If there is only single cpu online,synchronize_rcu()is optimized to return without doing all the work to wait for grace period. However, there are few issues with thenum_online_cpus()check used, for transition of__num_online_cpusfrom 2 -> 1 for cpu down path and 1 -> 2 for cpu up path.
Again, good catch!
As usual, I could not resist editing the commit log and comments, so could you please look the following over to make sure that I did not mess anything up?
Thanx, Paul
------------------------------------------------------------------------
commit 7af8c1c8d13c6c9c7013fbfef77f843dbc430c4b
Author: Neeraj Upadhyay <[email protected]> Date: Wed Sep 23 12:59:33 2020 +0530
rcu: Fix single-CPU check in rcu_blocking_is_gp()
Currently, for CONFIG_PREEMPTION=n kernels, rcu_blocking_is_gp() uses num_online_cpus() to determine whether there is only one CPU online. When there is only single CPU online, the simple fact that synchronize_rcu() could be legally called implies that a full grace period has elapsed. Therefore, in the single-CPU case, synchronize_rcu() simply returns immediately. Unfortunately, num_online_cpus() is unreliable while a CPU-hotplug operation is transitioning to or from single-CPU operation because:
1. num_online_cpus() uses atomic_read(&__num_online_cpus) to
locklessly sample the number of online CPUs. The hotplug locks are not held, which means that an incoming CPU can concurrently update this count. This in turn means that an RCU read-side critical section on the incoming CPU might observe updates prior to the grace period, but also that this critical section might extend beyond the end of the optimized synchronize_rcu(). This breaks RCU's fundamental guarantee.
2. In addition, num_online_cpus() does no ordering, thus providing
another way that RCU's fundamental guarantee can be broken by the current code.
3. The most probable failure mode happens on outgoing CPUs.
The outgoing CPU updates the count of online CPUs in the CPUHP_TEARDOWN_CPU stop-machine handler, which is fine in and of itself due to preemption being disabled at the call to num_online_cpus(). Unfortunately, after that stop-machine handler returns, the CPU takes one last trip through the scheduler (which has RCU readers) and, after the resulting context switch, one final dive into the idle loop. During this time, RCU needs to keep track of two CPUs, but num_online_cpus() will say that there is only one, which in turn means that the surviving CPU will incorrectly ignore the outgoing CPU's RCU read-side critical sections.
This problem is illustrated by the following litmus test in which P0() corresponds to synchronize_rcu() and P1() corresponds to the incoming CPU. The herd7 tool confirms that the "exists" clause can be satisfied, thus demonstrating that this breakage can happen according to the Linux kernel memory model.
{
int x = 0;
atomic_t numonline = ATOMIC_INIT(1);
}
P0(int *x, atomic_t *numonline)
{
int r0;
WRITE_ONCE(*x, 1);
r0 = atomic_read(numonline);
if (r0 == 1) {
smp_mb();
} else {
synchronize_rcu();
}
WRITE_ONCE(*x, 2);
}
P1(int *x, atomic_t *numonline)
{
int r0; int r1;
atomic_inc(numonline);
smp_mb();
rcu_read_lock();
r0 = READ_ONCE(*x);
smp_rmb();
r1 = READ_ONCE(*x);
rcu_read_unlock();
}
locations [x;numonline;]
exists (1:r0=0 /\ 1:r1=2)
It is important to note that these problems arise only when the system is transitioning to or from single-CPU operation.
One solution would be to hold the CPU-hotplug locks while sampling num_online_cpus(), which was in fact the intent of the (redundant) preempt_disable() and preempt_enable() surrounding this call to num_online_cpus(). Actually blocking CPU hotplug would not only result in excessive overhead, but would also unnecessarily impede CPU-hotplug operations.
This commit therefore follows long-standing RCU tradition by maintaining a separate RCU-specific set of CPU-hotplug books.
This separate set of books is implemented by a new ->n_online_cpus field in the rcu_state structure that maintains RCU's count of the online CPUs. This count is incremented early in the CPU-online process, so that the critical transition away from single-CPU operation will occur when there is only a single CPU. Similarly for the critical transition to single-CPU operation, the counter is decremented late in the CPU-offline process, again while there is only a single CPU. Because there is only ever a single CPU when the ->n_online_cpus field undergoes the critical 1->2 and 2->1 transitions, full memory ordering and mutual exclusion is provided implicitly and, better yet, for free.
In the case where the CPU is coming online, nothing will happen until the current CPU helps it come online. Therefore, the new CPU will see all accesses prior to the optimized grace period, which means that RCU does not need to further delay this new CPU. In the case where the CPU is going offline, the outgoing CPU is totally out of the picture before the optimized grace period starts, which means that this outgoing CPU cannot see any of the accesses following that grace period. Again, RCU needs no further interaction with the outgoing CPU.
This does mean that synchronize_rcu() will unnecessarily do a few grace periods the hard way just before the second CPU comes online and just after the second-to-last CPU goes offline, but it is not worth optimizing this uncommon case.
kernel/rcu/tree.c +17 -2
@@ -2402,6 +2402,7 @@ int rcutree_dead_cpu(unsigned int cpu)if (!IS_ENABLED (CONFIG_HOTPLUG_CPU ))return 0 ; +WRITE_ONCE (rcu_state.n_online_cpus, rcu_state.n_online_cpus -1 );/* Adjust any no-longer-needed kthreads. */ rcu_boost_kthread_setaffinity (rnp,-1 );/* Do any needed no-CB deferred wakeups from this CPU. */
@@ -3604,7 +3605,20 @@ static int rcu_blocking_is_gp(void)return rcu_scheduler_active ==RCU_SCHEDULER_INACTIVE ;might_sleep ();/* Check for RCU read-side critical section. */ preempt_disable (); - ret =num_online_cpus () <=1 ; +/* +* If the rcu_state.n_online_cpus counter is equal to one, +* there is only one CPU, and that CPU sees all prior accesses +* made by any CPU that was online at the time of its access. +* Furthermore, if this counter is equal to one, its value cannot +* change until after the preempt_enable() below. +* +* Furthermore, if rcu_state.n_online_cpus is equal to one here, +* all later CPUs (both this one and any that come online later +* on) are guaranteed to see all accesses prior to this point +* in the code, without the need for additional memory barriers. +* Those memory barriers are provided by CPU-hotplug code. +*/ + ret =READ_ONCE (rcu_state.n_online_cpus) <=1 ;preempt_enable ();return ret; }
@@ -3649,7 +3663,7 @@ void synchronize_rcu(void)lock_is_held (&rcu_sched_lock_map), "Illegal synchronize_rcu() in RCU read-side critical section");if (rcu_blocking_is_gp ()) -return ; +return ;// Context allows vacuous grace periods. if (rcu_gp_is_expedited ())synchronize_rcu_expedited ();else
@@ -3989,6 +4003,7 @@ int rcutree_prepare_cpu(unsigned int cpu)raw_spin_unlock_irqrestore_rcu_node (rnp, flags);rcu_prepare_kthreads (cpu);rcu_spawn_cpu_nocb_kthread (cpu); +WRITE_ONCE (rcu_state.n_online_cpus, rcu_state.n_online_cpus +1 );return 0 ; }
kernel/rcu/tree.h +1 -0
@@ -298,6 +298,7 @@ struct rcu_state {/* Hierarchy levels (+1 to */ /* shut bogus gcc warning) */ int ncpus;/* # CPUs seen so far. */ +int n_online_cpus;/* # CPUs online for RCU. */ /* The following fields are guarded by the root rcu_node's lock. */
Hi Paul,
Quoted 11 lines · Paul E. McKenney
Quoted 9 lines · Neeraj Upadhyay
Currently, for non-preempt kernels (with
CONFIG_PREEMPTION=n),rcu_blocking_is_gp()checks (with preemption disabled), whether there is only one cpu online. It usesnum_online_cpus()to decide whether only one cpu is online. If there is only single cpu online,synchronize_rcu()is optimized to return without doing all the work to wait for grace period. However, there are few issues with thenum_online_cpus()check used, for transition of__num_online_cpusfrom 2 -> 1 for cpu down path and 1 -> 2 for cpu up path.
Quoted 6 lines
Again, good catch!
As usual, I could not resist editing the commit log and comments, so could you please look the following over to make sure that I did not mess anything up?
The commit log and comments look very good! Thanks!
Thanks
Neeraj
Quoted 191 lines
Thanx, Paul
------------------------------------------------------------------------
commit
7af8c1c8d13c6c9c7013fbfef77f843dbc430c4bAuthor: Neeraj Upadhyay <[email protected]> Date: Wed Sep 23 12:59:33 2020 +0530rcu: Fix single-CPU check in
rcu_blocking_is_gp()Currently, for
CONFIG_PREEMPTION=nkernels,rcu_blocking_is_gp()usesnum_online_cpus()to determine whether there is only one CPU online. When there is only single CPU online, the simple fact thatsynchronize_rcu()could be legally called implies that a full grace period has elapsed. Therefore, in the single-CPU case,synchronize_rcu()simply returns immediately. Unfortunately,num_online_cpus()is unreliable while a CPU-hotplug operation is transitioning to or from single-CPU operation because:1.
num_online_cpus()usesatomic_read(&__num_online_cpus)to
locklessly sample the number of online CPUs. The hotplug locks are not held, which means that an incoming CPU can concurrently update this count. This in turn means that an RCU read-side critical section on the incoming CPU might observe updates prior to the grace period, but also that this critical section might extend beyond the end of the optimizedsynchronize_rcu(). This breaks RCU's fundamental guarantee.2. In addition,
num_online_cpus()does no ordering, thus providing
another way that RCU's fundamental guarantee can be broken by the current code.3. The most probable failure mode happens on outgoing CPUs.
The outgoing CPU updates the count of online CPUs in theCPUHP_TEARDOWN_CPUstop-machine handler, which is fine in and of itself due to preemption being disabled at the call tonum_online_cpus(). Unfortunately, after that stop-machine handler returns, the CPU takes one last trip through the scheduler (which has RCU readers) and, after the resulting context switch, one final dive into the idle loop. During this time, RCU needs to keep track of two CPUs, butnum_online_cpus()will say that there is only one, which in turn means that the surviving CPU will incorrectly ignore the outgoing CPU's RCU read-side critical sections.This problem is illustrated by the following litmus test in which
P0()corresponds tosynchronize_rcu()andP1()corresponds to the incoming CPU. The herd7 tool confirms that the "exists" clause can be satisfied, thus demonstrating that this breakage can happen according to the Linux kernel memory model.{
int x = 0;
atomic_tnumonline =ATOMIC_INIT(1);
}
P0(int *x, atomic_t *numonline)
{
int r0;
WRITE_ONCE(*x, 1);
r0 =atomic_read(numonline);
if (r0 == 1) {
smp_mb();
} else {
synchronize_rcu();
}
WRITE_ONCE(*x, 2);
}
P1(int *x, atomic_t *numonline)
{
int r0; int r1;
atomic_inc(numonline);
smp_mb();
rcu_read_lock();
r0 =READ_ONCE(*x);
smp_rmb();
r1 =READ_ONCE(*x);
rcu_read_unlock();
}locations [x;numonline;]
exists (1:r0=0 /\ 1:r1=2)
It is important to note that these problems arise only when the system is transitioning to or from single-CPU operation.
One solution would be to hold the CPU-hotplug locks while sampling
num_online_cpus(), which was in fact the intent of the (redundant)preempt_disable()andpreempt_enable()surrounding this call tonum_online_cpus(). Actually blocking CPU hotplug would not only result in excessive overhead, but would also unnecessarily impede CPU-hotplug operations.This commit therefore follows long-standing RCU tradition by maintaining a separate RCU-specific set of CPU-hotplug books.
This separate set of books is implemented by a new ->n_online_cpus field in the
rcu_statestructure that maintains RCU's count of the online CPUs. This count is incremented early in the CPU-online process, so that the critical transition away from single-CPU operation will occur when there is only a single CPU. Similarly for the critical transition to single-CPU operation, the counter is decremented late in the CPU-offline process, again while there is only a single CPU. Because there is only ever a single CPU when the ->n_online_cpus field undergoes the critical 1->2 and 2->1 transitions, full memory ordering and mutual exclusion is provided implicitly and, better yet, for free.In the case where the CPU is coming online, nothing will happen until the current CPU helps it come online. Therefore, the new CPU will see all accesses prior to the optimized grace period, which means that RCU does not need to further delay this new CPU. In the case where the CPU is going offline, the outgoing CPU is totally out of the picture before the optimized grace period starts, which means that this outgoing CPU cannot see any of the accesses following that grace period. Again, RCU needs no further interaction with the outgoing CPU.
This does mean that
synchronize_rcu()will unnecessarily do a few grace periods the hard way just before the second CPU comes online and just after the second-to-last CPU goes offline, but it is not worth optimizing this uncommon case.Signed-off-by Neeraj Upadhyay <[email protected]>Signed-off-by Paul E. McKenney <[email protected]>kernel/rcu/tree.c +17
-2@@ -2402,6 +2402,7 @@ int rcutree_dead_cpu(unsigned int cpu)if (!IS_ENABLED (CONFIG_HOTPLUG_CPU ))return 0 ; +WRITE_ONCE (rcu_state.n_online_cpus, rcu_state.n_online_cpus -1 );/* Adjust any no-longer-needed kthreads. */ rcu_boost_kthread_setaffinity (rnp,-1 );/* Do any needed no-CB deferred wakeups from this CPU. */ @@ -3604,7 +3605,20 @@ static int rcu_blocking_is_gp(void)return rcu_scheduler_active ==RCU_SCHEDULER_INACTIVE ;might_sleep ();/* Check for RCU read-side critical section. */ preempt_disable (); - ret =num_online_cpus () <=1 ; +/* +* If the rcu_state.n_online_cpus counter is equal to one, +* there is only one CPU, and that CPU sees all prior accesses +* made by any CPU that was online at the time of its access. +* Furthermore, if this counter is equal to one, its value cannot +* change until after the preempt_enable() below. +* +* Furthermore, if rcu_state.n_online_cpus is equal to one here, +* all later CPUs (both this one and any that come online later +* on) are guaranteed to see all accesses prior to this point +* in the code, without the need for additional memory barriers. +* Those memory barriers are provided by CPU-hotplug code. +*/ + ret =READ_ONCE (rcu_state.n_online_cpus) <=1 ;preempt_enable ();return ret; }@@ -3649,7 +3663,7 @@ void synchronize_rcu(void)lock_is_held (&rcu_sched_lock_map), "Illegal synchronize_rcu() in RCU read-side critical section");if (rcu_blocking_is_gp ()) -return ; +return ;// Context allows vacuous grace periods. if (rcu_gp_is_expedited ())synchronize_rcu_expedited ();else @@ -3989,6 +4003,7 @@ int rcutree_prepare_cpu(unsigned int cpu)raw_spin_unlock_irqrestore_rcu_node (rnp, flags);rcu_prepare_kthreads (cpu);rcu_spawn_cpu_nocb_kthread (cpu); +WRITE_ONCE (rcu_state.n_online_cpus, rcu_state.n_online_cpus +1 );return 0 ; }kernel/rcu/tree.h +1
-0@@ -298,6 +298,7 @@ struct rcu_state {/* Hierarchy levels (+1 to */ /* shut bogus gcc warning) */ int ncpus;/* # CPUs seen so far. */ +int n_online_cpus;/* # CPUs online for RCU. */ /* The following fields are guarded by the root rcu_node's lock. */
Signature · 1 line
QUALCOMM INDIA, on behalf of Qualcomm Innovation Center, Inc. is a member of the Code Aurora Forum, hosted by The Linux Foundation