lkml.org 
[lkml]   [2020]   [Sep]   [24]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
SubjectRe: [PATCH V2] rcu/tree: Correctly handle single cpu check in rcu_blocking_is_gp
From
Date
Hi Paul,

On 9/24/2020 2:33 AM, Paul E. McKenney wrote:
> On Wed, Sep 23, 2020 at 12:59:33PM +0530, Neeraj Upadhyay wrote:
>> 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.
>
> 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

> Thanx, Paul
>
> ------------------------------------------------------------------------
>
> commit 7af8c1c8d13c6c9c7013fbfef77f843dbc430c4b
> Author: Neeraj Upadhyay <neeraju@codeaurora.org>
> 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.
>
> Signed-off-by: Neeraj Upadhyay <neeraju@codeaurora.org>
> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
>
> diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
> index 6d9ec8e..9c56b63 100644
> --- a/kernel/rcu/tree.c
> +++ b/kernel/rcu/tree.c
> @@ -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;
> }
> diff --git a/kernel/rcu/tree.h b/kernel/rcu/tree.h
> index e4f66b8..805c9eb 100644
> --- a/kernel/rcu/tree.h
> +++ b/kernel/rcu/tree.h
> @@ -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. */
>
>

--
QUALCOMM INDIA, on behalf of Qualcomm Innovation Center, Inc. is a
member of the Code Aurora Forum, hosted by The Linux Foundation

\
 
 \ /
  Last update: 2020-09-24 07:01    [W:0.045 / U:10.356 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site