Re: [RFC PATCH] SRCU: More efficient reader counts.

[Paul E. McKenney]

On Fri, Nov 18, 2016 at 02:27:08PM +0000, Mathieu Desnoyers wrote:
> ----- On Nov 18, 2016, at 9:08 AM, Paul E. McKenney paulmck@xxxxxxxxxxxxxxxxxx wrote:
> 
> > On Thu, Nov 17, 2016 at 02:03:35PM -0800, Lance Roy wrote:
> >> SRCU uses two per-cpu counters: a nesting counter to count the number of
> >> active critical sections, and a sequence counter to ensure that the nesting
> >> counters don't change while they are being added together in
> >> srcu_readers_active_idx_check().
> >> 
> >> This patch instead uses per-cpu lock and unlock counters. Because the both
> >> counters only increase and srcu_readers_active_idx_check() reads the unlock
> >> counter before the lock counter, this achieves the same end without having
> >> to increment two different counters in srcu_read_lock(). This also saves a
> >> smp_mb() in srcu_readers_active_idx_check().
> >> 
> >> Possible bug: There is no guarantee that the lock counter won't overflow
> >> during srcu_readers_active_idx_check(), as there are no memory barriers
> >> around srcu_flip() (see comment in srcu_readers_active_idx_check() for
> >> details). However, this problem was already present before this patch.
> > 
> > This patch differs from the previous one in a few (good) code-style
> > changes, comment changes, and of course the commit log.  Good.  Once
> > discussion converges, I will apply the agreed-upon commit, which might
> > well be this one.
> > 
> > However, let's first take a look at the overflow issue.
> > 
> > If a given program could have ULONG_MAX or more readers at any given
> > time, there would of course be overflow.  However, each read must have
> > an srcu_read_lock() outstanding, and the resulting four-byte return
> > value must be stored somewhere.  Because the full address space is at
> > most ULONG_MAX, the maximum number of outstanding readers is at most
> > ULONG_MAX/4, even in the degenerate case where a single CPU/task invokes
> > srcu_read_lock() in a tight loop.  And even this assumes that the entire
> > address space can somehow be devoted to srcu_read_lock() return values.
> > ULONG_MAX/4 is therefore a hard upper bound on the number of outstanding
> > SRCU readers.
> 
> The loop taking srcu_read_lock() seems a bit far fetched.

True, but it is a good worst-case scenario, so it is worth seeing where
it goes.

> More realistically, we could move this bound even lower
> if we can expect each thread to only nest srcu up to a limited
> amount (e.g. 128). The realistic limit of number of SRCU readers
> then becomes bounded by the maximum number of threads multiplied
> by the srcu max nesting count.

A per-thread limit would make sense.  The thought is to enforce this
limit using lockdep or some such?  (Without some sort of enforcement,
setting a limit isn't really helpful.)

> > Now srcu_readers_active_idx_check() checks for strict equality between
> > the number of locks and unlocks, so we can in theory tolerate ULONG_MAX-1
> > readers.  So, the question is whether ULONG_MAX/4 readers can result
> > in the updater seeing ULONG_MAX reads, due to memory misordering and
> > other issues.
> > 
> > Because there are no memory barriers surrounding srcu_flip(), the updater
> > could miss an extremely large number of srcu_read_unlock()s.  However,
> > each missed srcu_read_unlock() must have a corresponding srcu_read_lock(),
> > and there is a full memory barrier between between the srcu_flip() and
> > the read of the lock count.  There is also a full barrier between any
> > srcu_read_lock()'s increment of the lock count and that CPU's/task's next
> > srcu_read_lock()'s fetch of the index.  Therefore, if the updater misses
> > counting a given srcu_read_lock(), that CPU's/task's next srcu_read_lock()
> > must see the new value of the index.  Because srcu_read_lock() disables
> > preemption across the index fetch and the lock increment, there can be at
> > most NR_CPUS-1 srcu_read_lock() calls that missed the recent srcu_flip()'s
> > update to the index.  (I said NR_CPUS earlier, but Mathieu is correct
> > in pointing out that srcu_flip() has to run somewhere.)
> > 
> > The maximum number of locks that the updater can see is therefore:
> > 
> > o	ULONG_MAX/4 for a full set of missed srcu_read_unlock()s.
> > 
> > o	ULONG_MAX/4 for a full set of srcu_read_lock()s.
> > 
> > o	NR_CPUS-1 for a full set of subsequent srcu_read_lock()s that
> >	missed the flip.
> > 
> > This totals to ULONG_MAX/2+NR_CPUS-1.  So as long as there are no more
> > than ULONG_MAX/2 CPUs, we should be good.  And given that the biggest
> > system I have hard evidence of is 4K CPUs, we have ample headrooom
> > compared to the ~2G value of ULONG_MAX/2, even on 32-bit systems.
> > 
> > So, what am I missing here?
> 
> Your analysis makes sense.

OK, so what is it that both of us are missing here?  ;-)

> An alternative approach would be to document some limits on the allowed
> nesting count for a given SRCU domain that should be expected from a thread,
> and use that as an even lower upper bound on the number of concurrent
> SRCU readers, which would allow us to increase the number of supported
> CPUs accordingly on 32-bit systems.

Do you really believe that there will be a 32-bit system with more than
even one million CPUs anytime soon?  Because the code can tolerate a bit
more than two billion.  ;-)

That said, I have no problem with an enforced limit on srcu_read_lock()
nesting as a debugging aid.  But don't we already have a limit inherent
in lockdep's limited number of array entries for tracking acquisitions?
Currently 2000 rather than 128, but seems close enough.  It looks to
me that lockdep dumps out the acquisitions when this limit is exceeded,
so the information would be there.

Thoughts?

							Thanx, Paul

> Thanks,
> 
> Mathieu
> 
> > 
> >							Thanx, Paul
> > 
> >> Suggested-by: Mathieu Desnoyers <mathieu.desnoyers@xxxxxxxxxxxx>
> >> Signed-off-by: Lance Roy <ldr709@xxxxxxxxx>
> >> ---
> >>  include/linux/srcu.h    |   4 +-
> >>  kernel/rcu/rcutorture.c |  20 ++++++++-
> >>  kernel/rcu/srcu.c       | 116 ++++++++++++++++++------------------------------
> >>  3 files changed, 63 insertions(+), 77 deletions(-)
> >> 
> >> diff --git a/include/linux/srcu.h b/include/linux/srcu.h
> >> index dc8eb63..0caea34 100644
> >> --- a/include/linux/srcu.h
> >> +++ b/include/linux/srcu.h
> >> @@ -34,8 +34,8 @@
> >>  #include <linux/workqueue.h>
> >> 
> >>  struct srcu_struct_array {
> >> -	unsigned long c[2];
> >> -	unsigned long seq[2];
> >> +	unsigned long lock_count[2];
> >> +	unsigned long unlock_count[2];
> >>  };
> >> 
> >>  struct rcu_batch {
> >> diff --git a/kernel/rcu/rcutorture.c b/kernel/rcu/rcutorture.c
> >> index bf08fee..2450c61 100644
> >> --- a/kernel/rcu/rcutorture.c
> >> +++ b/kernel/rcu/rcutorture.c
> >> @@ -555,10 +555,26 @@ static void srcu_torture_stats(void)
> >>  	pr_alert("%s%s per-CPU(idx=%d):",
> >>  		 torture_type, TORTURE_FLAG, idx);
> >>  	for_each_possible_cpu(cpu) {
> >> +		unsigned long l0, l1;
> >> +		unsigned long u0, u1;
> >>  		long c0, c1;
> >> +		struct srcu_struct_array *counts =
> >> +			per_cpu_ptr(srcu_ctlp->per_cpu_ref, cpu);
> >> 
> >> -		c0 = (long)per_cpu_ptr(srcu_ctlp->per_cpu_ref, cpu)->c[!idx];
> >> -		c1 = (long)per_cpu_ptr(srcu_ctlp->per_cpu_ref, cpu)->c[idx];
> >> +		u0 = counts->unlock_count[!idx];
> >> +		u1 = counts->unlock_count[idx];
> >> +
> >> +		/*
> >> +		 * Make sure that a lock is always counted if the corresponding
> >> +		 * unlock is counted.
> >> +		 */
> >> +		smp_rmb();
> >> +
> >> +		l0 = counts->lock_count[!idx];
> >> +		l1 = counts->lock_count[idx];
> >> +
> >> +		c0 = (long)(l0 - u0);
> >> +		c1 = (long)(l1 - u1);
> >>  		pr_cont(" %d(%ld,%ld)", cpu, c0, c1);
> >>  	}
> >>  	pr_cont("\n");
> >> diff --git a/kernel/rcu/srcu.c b/kernel/rcu/srcu.c
> >> index 9b9cdd5..38e9aae 100644
> >> --- a/kernel/rcu/srcu.c
> >> +++ b/kernel/rcu/srcu.c
> >> @@ -141,34 +141,38 @@ EXPORT_SYMBOL_GPL(init_srcu_struct);
> >>  #endif /* #else #ifdef CONFIG_DEBUG_LOCK_ALLOC */
> >> 
> >>  /*
> >> - * Returns approximate total of the readers' ->seq[] values for the
> >> + * Returns approximate total of the readers' ->lock_count[] values for the
> >>   * rank of per-CPU counters specified by idx.
> >>   */
> >> -static unsigned long srcu_readers_seq_idx(struct srcu_struct *sp, int idx)
> >> +static unsigned long srcu_readers_lock_idx(struct srcu_struct *sp, int idx)
> >>  {
> >>  	int cpu;
> >>  	unsigned long sum = 0;
> >>  	unsigned long t;
> >> 
> >>  	for_each_possible_cpu(cpu) {
> >> -		t = READ_ONCE(per_cpu_ptr(sp->per_cpu_ref, cpu)->seq[idx]);
> >> +		struct srcu_struct_array *cpu_counts =
> >> +			per_cpu_ptr(sp->per_cpu_ref, cpu);
> >> +		t = READ_ONCE(cpu_counts->lock_count[idx]);
> >>  		sum += t;
> >>  	}
> >>  	return sum;
> >>  }
> >> 
> >>  /*
> >> - * Returns approximate number of readers active on the specified rank
> >> - * of the per-CPU ->c[] counters.
> >> + * Returns approximate total of the readers' ->unlock_count[] values for the
> >> + * rank of per-CPU counters specified by idx.
> >>   */
> >> -static unsigned long srcu_readers_active_idx(struct srcu_struct *sp, int idx)
> >> +static unsigned long srcu_readers_unlock_idx(struct srcu_struct *sp, int idx)
> >>  {
> >>  	int cpu;
> >>  	unsigned long sum = 0;
> >>  	unsigned long t;
> >> 
> >>  	for_each_possible_cpu(cpu) {
> >> -		t = READ_ONCE(per_cpu_ptr(sp->per_cpu_ref, cpu)->c[idx]);
> >> +		struct srcu_struct_array *cpu_counts =
> >> +			per_cpu_ptr(sp->per_cpu_ref, cpu);
> >> +		t = READ_ONCE(cpu_counts->unlock_count[idx]);
> >>  		sum += t;
> >>  	}
> >>  	return sum;
> >> @@ -176,79 +180,42 @@ static unsigned long srcu_readers_active_idx(struct
> >> srcu_struct *sp, int idx)
> >> 
> >>  /*
> >>   * Return true if the number of pre-existing readers is determined to
> >> - * be stably zero.  An example unstable zero can occur if the call
> >> - * to srcu_readers_active_idx() misses an __srcu_read_lock() increment,
> >> - * but due to task migration, sees the corresponding __srcu_read_unlock()
> >> - * decrement.  This can happen because srcu_readers_active_idx() takes
> >> - * time to sum the array, and might in fact be interrupted or preempted
> >> - * partway through the summation.
> >> + * be zero.
> >>   */
> >>  static bool srcu_readers_active_idx_check(struct srcu_struct *sp, int idx)
> >>  {
> >> -	unsigned long seq;
> >> +	unsigned long unlocks;
> >> 
> >> -	seq = srcu_readers_seq_idx(sp, idx);
> >> +	unlocks = srcu_readers_unlock_idx(sp, idx);
> >> 
> >>  	/*
> >> -	 * The following smp_mb() A pairs with the smp_mb() B located in
> >> -	 * __srcu_read_lock().  This pairing ensures that if an
> >> -	 * __srcu_read_lock() increments its counter after the summation
> >> -	 * in srcu_readers_active_idx(), then the corresponding SRCU read-side
> >> -	 * critical section will see any changes made prior to the start
> >> -	 * of the current SRCU grace period.
> >> +	 * Make sure that a lock is always counted if the corresponding unlock
> >> +	 * is counted. Needs to be a smp_mb() as the read side may contain a
> >> +	 * read from a variable that is written to before the synchronize_srcu()
> >> +	 * in the write side. In this case smp_mb()s A and B act like the store
> >> +	 * buffering pattern.
> >>  	 *
> >> -	 * Also, if the above call to srcu_readers_seq_idx() saw the
> >> -	 * increment of ->seq[], then the call to srcu_readers_active_idx()
> >> -	 * must see the increment of ->c[].
> >> +	 * This smp_mb() also pairs with smp_mb() C to prevent writes after the
> >> +	 * synchronize_srcu() from being executed before the grace period ends.
> >>  	 */
> >>  	smp_mb(); /* A */
> >> 
> >>  	/*
> >> -	 * Note that srcu_readers_active_idx() can incorrectly return
> >> -	 * zero even though there is a pre-existing reader throughout.
> >> -	 * To see this, suppose that task A is in a very long SRCU
> >> -	 * read-side critical section that started on CPU 0, and that
> >> -	 * no other reader exists, so that the sum of the counters
> >> -	 * is equal to one.  Then suppose that task B starts executing
> >> -	 * srcu_readers_active_idx(), summing up to CPU 1, and then that
> >> -	 * task C starts reading on CPU 0, so that its increment is not
> >> -	 * summed, but finishes reading on CPU 2, so that its decrement
> >> -	 * -is- summed.  Then when task B completes its sum, it will
> >> -	 * incorrectly get zero, despite the fact that task A has been
> >> -	 * in its SRCU read-side critical section the whole time.
> >> -	 *
> >> -	 * We therefore do a validation step should srcu_readers_active_idx()
> >> -	 * return zero.
> >> -	 */
> >> -	if (srcu_readers_active_idx(sp, idx) != 0)
> >> -		return false;
> >> -
> >> -	/*
> >> -	 * The remainder of this function is the validation step.
> >> -	 * The following smp_mb() D pairs with the smp_mb() C in
> >> -	 * __srcu_read_unlock().  If the __srcu_read_unlock() was seen
> >> -	 * by srcu_readers_active_idx() above, then any destructive
> >> -	 * operation performed after the grace period will happen after
> >> -	 * the corresponding SRCU read-side critical section.
> >> +	 * If the locks are the same as the unlocks, then there must of have
> >> +	 * been no readers on this index at some time in between. This does not
> >> +	 * mean that there are no more readers, as one could have read the
> >> +	 * current index but have incremented the lock counter yet.
> >>  	 *
> >> -	 * Note that there can be at most NR_CPUS worth of readers using
> >> -	 * the old index, which is not enough to overflow even a 32-bit
> >> -	 * integer.  (Yes, this does mean that systems having more than
> >> -	 * a billion or so CPUs need to be 64-bit systems.)  Therefore,
> >> -	 * the sum of the ->seq[] counters cannot possibly overflow.
> >> -	 * Therefore, the only way that the return values of the two
> >> -	 * calls to srcu_readers_seq_idx() can be equal is if there were
> >> -	 * no increments of the corresponding rank of ->seq[] counts
> >> -	 * in the interim.  But the missed-increment scenario laid out
> >> -	 * above includes an increment of the ->seq[] counter by
> >> -	 * the corresponding __srcu_read_lock().  Therefore, if this
> >> -	 * scenario occurs, the return values from the two calls to
> >> -	 * srcu_readers_seq_idx() will differ, and thus the validation
> >> -	 * step below suffices.
> >> +	 * Possible bug: There is no guarantee that there haven't been ULONG_MAX
> >> +	 * increments of ->lock_count[] since the unlocks were counted, meaning
> >> +	 * that this could return true even if there are still active readers.
> >> +	 * Since there are no memory barriers around srcu_flip(), the CPU is not
> >> +	 * required to increment ->completed before running
> >> +	 * srcu_readers_unlock_idx(), which means that there could be an
> >> +	 * arbitrarily large number of critical sections that execute after
> >> +	 * srcu_readers_unlock_idx() but use the old value of ->completed.
> >>  	 */
> >> -	smp_mb(); /* D */
> >> -
> >> -	return srcu_readers_seq_idx(sp, idx) == seq;
> >> +	return srcu_readers_lock_idx(sp, idx) == unlocks;
> >>  }
> >> 
> >>  /**
> >> @@ -266,8 +233,12 @@ static bool srcu_readers_active(struct srcu_struct *sp)
> >>  	unsigned long sum = 0;
> >> 
> >>  	for_each_possible_cpu(cpu) {
> >> -		sum += READ_ONCE(per_cpu_ptr(sp->per_cpu_ref, cpu)->c[0]);
> >> -		sum += READ_ONCE(per_cpu_ptr(sp->per_cpu_ref, cpu)->c[1]);
> >> +		struct srcu_struct_array *cpu_counts =
> >> +			per_cpu_ptr(sp->per_cpu_ref, cpu);
> >> +		sum += READ_ONCE(cpu_counts->lock_count[0]);
> >> +		sum += READ_ONCE(cpu_counts->lock_count[1]);
> >> +		sum -= READ_ONCE(cpu_counts->unlock_count[0]);
> >> +		sum -= READ_ONCE(cpu_counts->unlock_count[1]);
> >>  	}
> >>  	return sum;
> >>  }
> >> @@ -298,9 +269,8 @@ int __srcu_read_lock(struct srcu_struct *sp)
> >>  	int idx;
> >> 
> >>  	idx = READ_ONCE(sp->completed) & 0x1;
> >> -	__this_cpu_inc(sp->per_cpu_ref->c[idx]);
> >> +	__this_cpu_inc(sp->per_cpu_ref->lock_count[idx]);
> >>  	smp_mb(); /* B */  /* Avoid leaking the critical section. */
> >> -	__this_cpu_inc(sp->per_cpu_ref->seq[idx]);
> >>  	return idx;
> >>  }
> >>  EXPORT_SYMBOL_GPL(__srcu_read_lock);
> >> @@ -314,7 +284,7 @@ EXPORT_SYMBOL_GPL(__srcu_read_lock);
> >>  void __srcu_read_unlock(struct srcu_struct *sp, int idx)
> >>  {
> >>  	smp_mb(); /* C */  /* Avoid leaking the critical section. */
> >> -	this_cpu_dec(sp->per_cpu_ref->c[idx]);
> >> +	this_cpu_inc(sp->per_cpu_ref->unlock_count[idx]);
> >>  }
> >>  EXPORT_SYMBOL_GPL(__srcu_read_unlock);
> >> 
> >> @@ -349,7 +319,7 @@ static bool try_check_zero(struct srcu_struct *sp, int idx,
> >> int trycount)
> >> 
> >>  /*
> >>   * Increment the ->completed counter so that future SRCU readers will
> >> - * use the other rank of the ->c[] and ->seq[] arrays.  This allows
> >> + * use the other rank of the ->(un)lock_count[] arrays.  This allows
> >>   * us to wait for pre-existing readers in a starvation-free manner.
> >>   */
> >>  static void srcu_flip(struct srcu_struct *sp)
> >> --
> >> 2.9.0
> 
> -- 
> Mathieu Desnoyers
> EfficiOS Inc.
> http://www.efficios.com
>