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

On 9/23/2020 1:59 AM, Paul E. McKenney wrote:
> On Tue, Sep 22, 2020 at 01:15:57AM +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:
>
> Great catch!!!
>
> I do have some questions about your suggested fix, though.
>
>> 1. 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().
>>
>> To handle these issues, add a new rcu_state member n_online_cpus, to
>> keep account of the current number of online cpus. The atomic updates
>> to this counter from rcu_report_dead() and rcu_cpu_starting() and
>> the added read/write memory ordering semantics ensure that
>> synchronize_rcu() fast path waits for all read side sections, where
>> incoming/outgoing cpus are considered online, for RCU i.e. after
>> rcu_cpu_starting() and before rcu_report_dead().
>>
>> Signed-off-by: Neeraj Upadhyay <neeraju@codeaurora.org>
>> ---
>>
>> Below is the reproducer for issue described in point 3; this snippet
>> is based on klitmus generated test, which is modified to sample reads
>> from idle thread:
>>
>> static void code0(int* x) {
>> WRITE_ONCE(*x, 1);
>> idle_ctr = 0;
>> smp_mb();
>> mdelay(10);
>> WRITE_ONCE(*x, 1);
>> idle_ctr = 1;
>> synchronize_rcu();
>> WRITE_ONCE(*x, 2);
>> idle_ctr = 2;
>>
>> }
>>
>> static int thread0(void *_p) {
>> int _j, _i;
>> ctx_t *_a = (ctx_t *)_p;
>>
>> smp_mb();
>> for (_j = 0 ; _j < stride ; _j++) {
>> for (_i = _j ; _i < size ; _i += stride) {
>> while (idle_wait1) {
>> cpu_relax();
>> cond_resched();
>> }
>> code0(&_a->x[_i]);
>> smp_mb();
>> get_online_cpus();
>> idle_wait1 = true;
>> put_online_cpus();
>> }
>> }
>> atomic_inc(&done);
>> smp_mb();
>> wake_up(wq);
>> smp_mb();
>> do_exit(0);
>> }
>>
>>
>> static void code1(int* x,int* out_1_r1,int* out_1_r0) {
>>
>> int r0; int r1;
>>
>> r0 = READ_ONCE(idle_ctr_snap1);
>> r1 = READ_ONCE(idle_ctr_snap2);
>>
>> *out_1_r1 = (int)r1;
>> *out_1_r0 = (int)r0;
>> }
>>
>> static int thread1(void *_p) {
>> ctx_t *_a = (ctx_t *)_p;
>> int _j, _i;
>>
>> smp_mb();
>> for (_j = 0 ; _j < stride ; _j++) {
>> for (_i = _j ; _i < size ; _i += stride) {
>> while (idle_wait2) {
>> cpu_relax();
>> cond_resched();
>> }
>> get_online_cpus();
>> code1(&_a->x[_i],&_a->out_1_r1[_i],&_a->out_1_r0[_i]);
>> smp_mb();
>> idle_wait2 = true;
>> put_online_cpus();
>> }
>> }
>> atomic_inc(&done);
>> smp_mb();
>> wake_up(wq);
>> smp_mb();
>> do_exit(0);
>> }
>>
>> Idle thread snippet:
>>
>> if (cpu_is_offline(cpu)) {
>> smp_mb();
>> idle_wait1 = false;
>> mdelay(8);
>> smp_mb();
>> rcu_read_lock();
>> idle_ctr_snap1 = idle_ctr;
>> mdelay(40);
>> smp_rmb();
>> idle_ctr_snap2 = idle_ctr;
>> rcu_read_unlock();
>> smp_mb();
>> idle_wait2 = false;
>> tick_nohz_idle_stop_tick();
>> cpuhp_report_idle_dead();
>> arch_cpu_idle_dead();
>>
>> kernel/rcu/tree.c | 65 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
>> kernel/rcu/tree.h | 1 +
>> 2 files changed, 66 insertions(+)
>>
>> diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
>> index 2424e2a..33493f0 100644
>> --- a/kernel/rcu/tree.c
>> +++ b/kernel/rcu/tree.c
>> @@ -3609,9 +3609,59 @@ static int rcu_blocking_is_gp(void)
>> if (IS_ENABLED(CONFIG_PREEMPTION))
>> return rcu_scheduler_active == RCU_SCHEDULER_INACTIVE;
>> might_sleep(); /* Check for RCU read-side critical section. */
>> + /*
>> + * a = p
>> + * a = NULL
>> + * synchronize_rcu()
>> + * rcu_blocking_is_gp()
>> + * num_online_cpus()
>> + * atomic_read(&__num_online_cpus)
>> + * kfree(p);
>> + *
>> + * - VS -
>> + *
>> + * __cpu_up()
>> + * set_cpu_online(cpu)
>> + * atomic_inc(&__num_online_cpus)
>> + * rcu_read_lock()
>> + * rcu_dereference(a) (a == p)
>> + * rcu_read_unlock()
>> + *
>> + * rcu_blocking_is_gp() must observe atomic_inc(&__num_online_cpus),
>> + * in order to ensure that, RCU read side critical section on new
>> + * online cpu, either start after synchronize_rcu()'s GP starts or
>> + * it completes before synchronize_rcu() returns.
>> + *
>> + * However, atomic_read(&__num_online_cpus) does not ensure that.
>> + *
>> + * Essentially, below condition exist:
>> + *
>> + * {
>> + * int x = 0;
>> + * atomic_t numonline = ATOMIC_INIT(1);
>> + * }
>> + *
>> + * P0(int *x, atomic_t *numonline) P1(int *x, atomic_t *numonline)
>> + * { {
>> + * int r0; int r0; int r1;
>> + * WRITE_ONCE(*x, 1); atomic_inc(numonline);
>> + * r0 = atomic_read(numonline); rcu_read_lock();
>> + * if (r0 == 2) { r0 = READ_ONCE(*x);
>> + * synchronize_rcu(); smp_rmb();
>> + * } r1 = READ_ONCE(*x);
>> + * WRITE_ONCE(*x, 2); rcu_read_unlock();
>> + * } }
>> + *
>> + * exists (1:r0=0 /\ 1:r1=2)
>> + *
>> + * atomic_add_return(0, &rcu_state.n_online_cpus) and corresponding
>> + * atomic_inc(&rcu_state.n_online_cpus) in rcu_cpu_starting() corrects
>> + * this ordering issue.
>> + */
>> preempt_disable();
>> ret = num_online_cpus() <= 1;
>
> Here I assume that rcu_state.n_online_cpus is incremented early in
> the CPU-hotplug CPU-online process, that is, on one of the CPUs that
> was running prior to the new CPU coming online. (The problem with the
> existing code is not the lack of ordering, but rather that the changes
> to the number of online CPUs happen in places that are not helpful to
> synchronize_rcu().)
>
> If rcu_state.n_online_cpus is equal to one at any point in this region of
> code, 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, and without
> added memory barriers. Those memory barriers have to be present in the
> CPU-hotplug code or lots of things would break.
>
> On the other hand, if n_online_cpus is greater than one, then we
> will be using the heavyweight call to synchronize_rcu(), which will
> guarantee all the ordering we need. (Please refer to the rather
> lengthy header comment for synchronize_rcu().)
>
> So if you access rcu_state.n_online_cpus with preemption disabled,
> READ_ONCE() suffices and no memory barriers are required.
>
>> preempt_enable();
>
> And we only get to this point in the code when CONFIG_PREEMPT_NONE=y,
> so the preempt_disable() and preempt_enable() are optional. Though they
> can be argued to be useful documentation. Or maybe not...
>

I also noticed it. For CONFIG_PREEMPTION=n, preempt_disable() and
preempt_enable() adds barrier(); I thought that was required for the
case where num online cpus <= 1?

>> + ret = ret && (atomic_add_return(0, &rcu_state.n_online_cpus) <= 1);
>> return ret;
>> }
>>
>> @@ -3655,6 +3705,11 @@ 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())
>> + /*
>> + * atomic_add_return() in rcu_blocking_is_gp () provides
>> + * full memory barrier ordering with any rcu section after
>> + * synchronize_rcu() call.
>> + */
>
> Given your fix of having RCU keep its own count of the number of online
> CPUs, no additional ordering is required. Either synchronize_rcu()
> provides what is required or we are in single-CPU state, meaning we
> don't need any ordering.
>
>> return;
>> if (rcu_gp_is_expedited())
>> synchronize_rcu_expedited();
>> @@ -4086,6 +4141,10 @@ void rcu_cpu_starting(unsigned int cpu)
>> mask = rdp->grpmask;
>> raw_spin_lock_irqsave_rcu_node(rnp, flags);
>> WRITE_ONCE(rnp->qsmaskinitnext, rnp->qsmaskinitnext | mask);
>> + /* Order with access of n_online_cpus in rcu_blocking_is_gp */
>> + atomic_inc(&rcu_state.n_online_cpus);
>> + /* Order with rcu-side usages after this */
>> + smp_mb__after_atomic();
>
> Ah, here is the problem. Please instead put the increment in
> rcutree_prepare_cpu(), which in the one-to-two transition will be running
> on the single CPU in the system, thus avoiding the need for ordering.
> Yes, this will result in unnecessary calls to synchronize_rcu() during
> the CPU-online process, but who cares? ;-)
>
>> newcpu = !(rnp->expmaskinitnext & mask);
>> rnp->expmaskinitnext |= mask;
>> /* Allow lockless access for expedited grace periods. */
>> @@ -4138,6 +4197,12 @@ void rcu_report_dead(unsigned int cpu)
>> raw_spin_lock_irqsave_rcu_node(rnp, flags);
>> }
>> WRITE_ONCE(rnp->qsmaskinitnext, rnp->qsmaskinitnext & ~mask);
>> + /*
>> + * Order with access of n_online_cpus in rcu_blocking_is_gp().
>> + * Release semantics ensures that RCU read sections before it
>> + * are observed by rcu_blocking_is_gp().
>> + */
>> + atomic_dec_return_release(&rcu_state.n_online_cpus);
>
> Similarly, please put this decrement into rcutree_dead_cpu(), which
> runs on one of the remaining CPUs after the outgoing CPU is long gone.
> In the two-to-one transition, this will run on the single remaining
> CPU in the system, thus avoiding the need for ordering. Again, yes,
> this will result in unnecessary calls to synchronize_rcu() during the
> CPU-online process, but again who cares?
>
>> raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
>> raw_spin_unlock(&rcu_state.ofl_lock);
>>
>> diff --git a/kernel/rcu/tree.h b/kernel/rcu/tree.h
>> index e4f66b8..4d9a9c0 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. */
>> + atomic_t n_online_cpus; /* # CPUs online for RCU. */
>
> With those changes in place, this can be just an int. The increments
> and decrements can use normal C-language loads and WRITE_ONCE() for the
> stores. The trick is that this value will only change from one to two
> (and vice versa) when there is only one online CPU.
>
> And the num_online_cpus() can be replaced with a READ_ONCE().
>
> Does this make sense, or am I missing something?
>
> Thanx, Paul
>

Yes, this makes sense; thanks for the details! Will post v2.


Thanks
Neeraj

>> /* The following fields are guarded by the root rcu_node's lock. */
>>
>> --
>> The Qualcomm Innovation Center, Inc. is a member of the Code Aurora Forum,
>> a Linux Foundation Collaborative Project
>>

--
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-23 09:23    [W:0.091 / U:1.044 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site