Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1565278 > unrolled thread

[PATCH v2 tip/core/rcu 1/3] srcu: Implement more-efficient reader counts

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  [PATCH v2 tip/core/rcu 1/3] srcu: Implement more-efficient reader counts Lance Roy <ldr709@gmail.com> - 2017-01-23 21:20 +0100
    [PATCH] SRCU: More efficient reader counts. Lance Roy <ldr709@gmail.com> - 2017-01-23 21:20 +0100
      Re: [PATCH] SRCU: More efficient reader counts. "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2017-01-23 21:40 +0100
        Re: [PATCH] SRCU: More efficient reader counts. Lance Roy <ldr709@gmail.com> - 2017-01-23 22:40 +0100
          [PATCH] srcu: Implement more-efficient reader counts Lance Roy <ldr709@gmail.com> - 2017-01-23 22:40 +0100
            Re: [PATCH] srcu: Implement more-efficient reader counts "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2017-01-24 01:50 +0100
              Re: [PATCH] srcu: Implement more-efficient reader counts Lance Roy <ldr709@gmail.com> - 2017-01-24 02:00 +0100
                Re: [PATCH] srcu: Implement more-efficient reader counts "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2017-01-24 03:00 +0100
                  Re: [PATCH] srcu: Implement more-efficient reader counts Lance Roy <ldr709@gmail.com> - 2017-01-24 04:30 +0100
                    Re: [PATCH] srcu: Implement more-efficient reader counts "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2017-01-24 18:10 +0100

#1565278 — [PATCH v2 tip/core/rcu 1/3] srcu: Implement more-efficient reader counts

Here is a more recent version of the patch. It has more accurate comments.

[toc] | [next] | [standalone]

#1565279 — [PATCH] SRCU: More efficient reader counts.

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.

Suggested-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Signed-off-by: Lance Roy <ldr709@gmail.com>
---
 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 87c5122..c3f25d1 100644
--- a/kernel/rcu/rcutorture.c
+++ b/kernel/rcu/rcutorture.c
@@ -564,10 +564,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

[toc] | [prev] | [next] | [standalone]

#1565289 — Re: [PATCH] SRCU: More efficient reader counts.

On Mon, Jan 23, 2017 at 12:17:25PM -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.
> 
> Suggested-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> Signed-off-by: Lance Roy <ldr709@gmail.com>

In general, the comment update looks good, but this patch undoes my
application of review feedback to your original patch.  Could you please
submit the comment update as a separate patch on top of branch rcu/next
of my -rcu tree?

git://git.kernel.org/pub/scm/linux/kernel/git/paulmck/linux-rcu.git

Of course, if any of the changes from the review feedback are in any
way problematic, please do let me know.

							Thanx, Paul

> ---
>  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 87c5122..c3f25d1 100644
> --- a/kernel/rcu/rcutorture.c
> +++ b/kernel/rcu/rcutorture.c
> @@ -564,10 +564,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
> 

[toc] | [prev] | [next] | [standalone]

#1565318 — Re: [PATCH] SRCU: More efficient reader counts.

On Mon, 23 Jan 2017 12:35:08 -0800
"Paul E. McKenney" <paulmck@linux.vnet.ibm.com> wrote:

> On Mon, Jan 23, 2017 at 12:17:25PM -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.
> > 
> > Suggested-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> > Signed-off-by: Lance Roy <ldr709@gmail.com>  
> 
> In general, the comment update looks good, but this patch undoes my
> application of review feedback to your original patch.  Could you please
> submit the comment update as a separate patch on top of branch rcu/next
> of my -rcu tree?
> 
> git://git.kernel.org/pub/scm/linux/kernel/git/paulmck/linux-rcu.git
I have added the review feedback to the new patch. I will send the new version.
If you prefer that the comment changes are in a separate patch I can change it,
but I thought it would be better not to have an incorrect statement in the
commit message.

> Of course, if any of the changes from the review feedback are in any
> way problematic, please do let me know.
I don't see any problems.

Thanks,
Lance

[toc] | [prev] | [next] | [standalone]

#1565319 — [PATCH] srcu: Implement more-efficient reader counts

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 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.

Suggested-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Signed-off-by: Lance Roy <ldr709@gmail.com>
Cc: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Cc: Lai Jiangshan <jiangshanlai@gmail.com>
Cc: Peter Zijlstra <peterz@infradead.org>
---
 include/linux/srcu.h    |  10 ++--
 kernel/rcu/rcutorture.c |  19 +++++++-
 kernel/rcu/srcu.c       | 122 +++++++++++++++++-------------------------------
 3 files changed, 66 insertions(+), 85 deletions(-)

diff --git a/include/linux/srcu.h b/include/linux/srcu.h
index dc8eb63..a598cf3 100644
--- a/include/linux/srcu.h
+++ b/include/linux/srcu.h
@@ -33,9 +33,9 @@
 #include <linux/rcupdate.h>
 #include <linux/workqueue.h>
 
-struct srcu_struct_array {
-	unsigned long c[2];
-	unsigned long seq[2];
+struct srcu_array {
+	unsigned long lock_count[2];
+	unsigned long unlock_count[2];
 };
 
 struct rcu_batch {
@@ -46,7 +46,7 @@ struct rcu_batch {
 
 struct srcu_struct {
 	unsigned long completed;
-	struct srcu_struct_array __percpu *per_cpu_ref;
+	struct srcu_array __percpu *per_cpu_ref;
 	spinlock_t queue_lock; /* protect ->batch_queue, ->running */
 	bool running;
 	/* callbacks just queued */
@@ -118,7 +118,7 @@ void process_srcu(struct work_struct *work);
  * See include/linux/percpu-defs.h for the rules on per-CPU variables.
  */
 #define __DEFINE_SRCU(name, is_static)					\
-	static DEFINE_PER_CPU(struct srcu_struct_array, name##_srcu_array);\
+	static DEFINE_PER_CPU(struct srcu_array, name##_srcu_array);\
 	is_static struct srcu_struct name = __SRCU_STRUCT_INIT(name)
 #define DEFINE_SRCU(name)		__DEFINE_SRCU(name, /* not static */)
 #define DEFINE_STATIC_SRCU(name)	__DEFINE_SRCU(name, static)
diff --git a/kernel/rcu/rcutorture.c b/kernel/rcu/rcutorture.c
index 87c5122..d81345b 100644
--- a/kernel/rcu/rcutorture.c
+++ b/kernel/rcu/rcutorture.c
@@ -564,10 +564,25 @@ 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_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 = l0 - u0;
+		c1 = 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..c9a0015 100644
--- a/kernel/rcu/srcu.c
+++ b/kernel/rcu/srcu.c
@@ -106,7 +106,7 @@ static int init_srcu_struct_fields(struct srcu_struct *sp)
 	rcu_batch_init(&sp->batch_check1);
 	rcu_batch_init(&sp->batch_done);
 	INIT_DELAYED_WORK(&sp->work, process_srcu);
-	sp->per_cpu_ref = alloc_percpu(struct srcu_struct_array);
+	sp->per_cpu_ref = alloc_percpu(struct srcu_array);
 	return sp->per_cpu_ref ? 0 : -ENOMEM;
 }
 
@@ -141,114 +141,77 @@ 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]);
-		sum += t;
+		struct srcu_array *cpuc = per_cpu_ptr(sp->per_cpu_ref, cpu);
+
+		sum += READ_ONCE(cpuc->lock_count[idx]);
 	}
 	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]);
-		sum += t;
+		struct srcu_array *cpuc = per_cpu_ptr(sp->per_cpu_ref, cpu);
+
+		sum += READ_ONCE(cpuc->unlock_count[idx]);
 	}
 	return sum;
 }
 
 /*
  * 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 accesses 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.
+	 * If the locks are the same as the unlocks, then there must 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 not have incremented the lock counter yet.
 	 *
-	 * We therefore do a validation step should srcu_readers_active_idx()
-	 * return zero.
+	 * 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.
 	 */
-	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.
-	 *
-	 * 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.
-	 */
-	smp_mb(); /* D */
-
-	return srcu_readers_seq_idx(sp, idx) == seq;
+	return srcu_readers_lock_idx(sp, idx) == unlocks;
 }
 
 /**
@@ -266,8 +229,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_array *cpuc = per_cpu_ptr(sp->per_cpu_ref, cpu);
+
+		sum += READ_ONCE(cpuc->lock_count[0]);
+		sum += READ_ONCE(cpuc->lock_count[1]);
+		sum -= READ_ONCE(cpuc->unlock_count[0]);
+		sum -= READ_ONCE(cpuc->unlock_count[1]);
 	}
 	return sum;
 }
@@ -298,9 +265,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 +280,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 +315,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

[toc] | [prev] | [next] | [standalone]

#1565391 — Re: [PATCH] srcu: Implement more-efficient reader counts

On Mon, Jan 23, 2017 at 01:35:18PM -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 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.
> 
> Suggested-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> Signed-off-by: Lance Roy <ldr709@gmail.com>
> Cc: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> Cc: Lai Jiangshan <jiangshanlai@gmail.com>
> Cc: Peter Zijlstra <peterz@infradead.org>

OK, this only has differences only in the comments, so I can reasonably
substitute it, even this near the next merge window.

But let's talk about the potential overflow.  If I understand correctly,
for this to happen, there needs to be ULONG_MAX/2 or thereabouts
srcu_read_lock() calls without matching srcu_read_unlock() calls.
Let's focus on 32-bit systems for the moment.

Lockdep allows at most 48 locks held at a given time by any single task,
and RCU does not pass in a non-NULL nest_lock -- if you acquire more than
that, a lockdep kernel will splat.  Each task has at least one 4K page of
kernel stack, so there can be at most 1,048,576 tasks (actually quite a
bit fewer due to the size of the task_struct and so on).  This allows
at most 50,331,648 unmatched srcu_read_lock() calls in the system,
which is not sufficient to cause overflow.

Or am I missing something here?

								Thanx, Paul

> ---
>  include/linux/srcu.h    |  10 ++--
>  kernel/rcu/rcutorture.c |  19 +++++++-
>  kernel/rcu/srcu.c       | 122 +++++++++++++++++-------------------------------
>  3 files changed, 66 insertions(+), 85 deletions(-)
> 
> diff --git a/include/linux/srcu.h b/include/linux/srcu.h
> index dc8eb63..a598cf3 100644
> --- a/include/linux/srcu.h
> +++ b/include/linux/srcu.h
> @@ -33,9 +33,9 @@
>  #include <linux/rcupdate.h>
>  #include <linux/workqueue.h>
> 
> -struct srcu_struct_array {
> -	unsigned long c[2];
> -	unsigned long seq[2];
> +struct srcu_array {
> +	unsigned long lock_count[2];
> +	unsigned long unlock_count[2];
>  };
> 
>  struct rcu_batch {
> @@ -46,7 +46,7 @@ struct rcu_batch {
> 
>  struct srcu_struct {
>  	unsigned long completed;
> -	struct srcu_struct_array __percpu *per_cpu_ref;
> +	struct srcu_array __percpu *per_cpu_ref;
>  	spinlock_t queue_lock; /* protect ->batch_queue, ->running */
>  	bool running;
>  	/* callbacks just queued */
> @@ -118,7 +118,7 @@ void process_srcu(struct work_struct *work);
>   * See include/linux/percpu-defs.h for the rules on per-CPU variables.
>   */
>  #define __DEFINE_SRCU(name, is_static)					\
> -	static DEFINE_PER_CPU(struct srcu_struct_array, name##_srcu_array);\
> +	static DEFINE_PER_CPU(struct srcu_array, name##_srcu_array);\
>  	is_static struct srcu_struct name = __SRCU_STRUCT_INIT(name)
>  #define DEFINE_SRCU(name)		__DEFINE_SRCU(name, /* not static */)
>  #define DEFINE_STATIC_SRCU(name)	__DEFINE_SRCU(name, static)
> diff --git a/kernel/rcu/rcutorture.c b/kernel/rcu/rcutorture.c
> index 87c5122..d81345b 100644
> --- a/kernel/rcu/rcutorture.c
> +++ b/kernel/rcu/rcutorture.c
> @@ -564,10 +564,25 @@ 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_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 = l0 - u0;
> +		c1 = 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..c9a0015 100644
> --- a/kernel/rcu/srcu.c
> +++ b/kernel/rcu/srcu.c
> @@ -106,7 +106,7 @@ static int init_srcu_struct_fields(struct srcu_struct *sp)
>  	rcu_batch_init(&sp->batch_check1);
>  	rcu_batch_init(&sp->batch_done);
>  	INIT_DELAYED_WORK(&sp->work, process_srcu);
> -	sp->per_cpu_ref = alloc_percpu(struct srcu_struct_array);
> +	sp->per_cpu_ref = alloc_percpu(struct srcu_array);
>  	return sp->per_cpu_ref ? 0 : -ENOMEM;
>  }
> 
> @@ -141,114 +141,77 @@ 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]);
> -		sum += t;
> +		struct srcu_array *cpuc = per_cpu_ptr(sp->per_cpu_ref, cpu);
> +
> +		sum += READ_ONCE(cpuc->lock_count[idx]);
>  	}
>  	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]);
> -		sum += t;
> +		struct srcu_array *cpuc = per_cpu_ptr(sp->per_cpu_ref, cpu);
> +
> +		sum += READ_ONCE(cpuc->unlock_count[idx]);
>  	}
>  	return sum;
>  }
> 
>  /*
>   * 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 accesses 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.
> +	 * If the locks are the same as the unlocks, then there must 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 not have incremented the lock counter yet.
>  	 *
> -	 * We therefore do a validation step should srcu_readers_active_idx()
> -	 * return zero.
> +	 * 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.
>  	 */
> -	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.
> -	 *
> -	 * 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.
> -	 */
> -	smp_mb(); /* D */
> -
> -	return srcu_readers_seq_idx(sp, idx) == seq;
> +	return srcu_readers_lock_idx(sp, idx) == unlocks;
>  }
> 
>  /**
> @@ -266,8 +229,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_array *cpuc = per_cpu_ptr(sp->per_cpu_ref, cpu);
> +
> +		sum += READ_ONCE(cpuc->lock_count[0]);
> +		sum += READ_ONCE(cpuc->lock_count[1]);
> +		sum -= READ_ONCE(cpuc->unlock_count[0]);
> +		sum -= READ_ONCE(cpuc->unlock_count[1]);
>  	}
>  	return sum;
>  }
> @@ -298,9 +265,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 +280,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 +315,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
> 

[toc] | [prev] | [next] | [standalone]

#1565393 — Re: [PATCH] srcu: Implement more-efficient reader counts

On Mon, 23 Jan 2017 16:42:52 -0800
"Paul E. McKenney" <paulmck@linux.vnet.ibm.com> wrote:

> On Mon, Jan 23, 2017 at 01:35:18PM -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 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.
> > 
> > Suggested-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> > Signed-off-by: Lance Roy <ldr709@gmail.com>
> > Cc: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> > Cc: Lai Jiangshan <jiangshanlai@gmail.com>
> > Cc: Peter Zijlstra <peterz@infradead.org>  
> 
> OK, this only has differences only in the comments, so I can reasonably
> substitute it, even this near the next merge window.
> 
> But let's talk about the potential overflow.  If I understand correctly,
> for this to happen, there needs to be ULONG_MAX/2 or thereabouts
> srcu_read_lock() calls without matching srcu_read_unlock() calls.
> Let's focus on 32-bit systems for the moment.
> 
> Lockdep allows at most 48 locks held at a given time by any single task,
> and RCU does not pass in a non-NULL nest_lock -- if you acquire more than
> that, a lockdep kernel will splat.  Each task has at least one 4K page of
> kernel stack, so there can be at most 1,048,576 tasks (actually quite a
> bit fewer due to the size of the task_struct and so on).  This allows
> at most 50,331,648 unmatched srcu_read_lock() calls in the system,
> which is not sufficient to cause overflow.
> 
> Or am I missing something here?
> 
> 								Thanx, Paul

It isn't the nest that is the problem. Here is a previous email I wrote
describing the problem:


The trouble is that disabling preemption is not enough to ensure that there
is at most one srcu_read_lock() call per CPU that missed the srcu_flip().

Define a reader to be an SRCU lock+unlock pair. A reader is called active if it
has incremented ->lock_count[] but hasn't incremented ->unlock_count[] yet, and
completed if it has incremented ->unlock_count[]. I think that we only want to
limit the number of active readers and the number of CPUs. In particular, I
don't think there should be a limit on the rate of completion of read side
critical section.

The goal of srcu_readers_active_idx_check() is to verify that there were zero
active readers on the inactive index at some time during its execution. To do
this, it totals the unlock counts, executes a memory barrier, totals the lock
counts, and takes the difference. This difference counts the readers that are
active when srcu_readers_lock_idx() gets to their CPU, plus the readers that
completed after srcu_readers_unlock_idx() and before srcu_readers_lock_idx().
If the true (infinite precision) value of the difference is zero, then there
were no active readers at some point while srcu_readers_lock_idx() is running.
However, the difference is only stored in a long, so there is a potential for
overflow if too many readers complete during srcu_readers_active_idx_check().

For example, let's say there are three threads, each running on their own CPU:

int data, flag;
struct srcu_struct *sp = /* ... */;

Thread 0:
	data = 1;
	synchronize_srcu(sp);
	flag = 1;

Thread 1:
	int data_r, flag_r;
	int idx = srcu_read_lock(sp);
	data_r = data;
	flag_r = flag;
	srcu_read_unlock(sp, idx);
	BUG_ON(flag_r == 1 && data_r == 0);

Thread 2:
	while (true) {
		int idx = srcu_read_lock(sp);
		srcu_read_unlock(sp, idx);
	}

Let's take the following execution order. Thread 1 increments
the CPU 1 version of sp->lock_count[0], sets idx to zero, and loads data (0)
into data_r. Thread 0 then sets data to be 1, verifies that there are no
readers on index 1, and increments sp->completed, but the CPU actually doesn't
preform the last operation, putting it off until the next memory barrier. Thread
0 then calls srcu_readers_active_idx_check() on index 0, which runs
srcu_readers_unlock_idx() (returning 0). Right after srcu_readers_unlock_idx()
completes, thread 2 starts running. Since Thread 0 hasn't actually incremented
sp->completed in any way that is visible to thread 2, srcu_read_lock() will
still return 0. Thread 2 can then run for ULONG_MAX iterations, setting
the CPU 2 version of sp->unlock_count[0] to ULONG_MAX. CPU 0 then finally gets
around to incrementing sp->completed, runs its memory barrier, and then reads
the lock counts: 1, 0, ULONG_MAX. The total of ULONG_MAX+1 will overflow to 0
and compare equal with earlier unlock count. Thread 0 will then think that the
grace period is over and set flag to one. Thread 1 can then read flag (1) into
flag_r and run srcu_read_unlock(). The BUG_ON statement will then fail.

Although ULONG_MAX readers completed during srcu_readers_active_idx_check(),
there were at most 2 active readers at any time, so this program doesn't run
into any limit.

I hope that was clear enough.

Thanks,
Lance

[toc] | [prev] | [next] | [standalone]

#1565413 — Re: [PATCH] srcu: Implement more-efficient reader counts

On Mon, Jan 23, 2017 at 04:53:34PM -0800, Lance Roy wrote:
> On Mon, 23 Jan 2017 16:42:52 -0800
> "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> wrote:
> 
> > On Mon, Jan 23, 2017 at 01:35:18PM -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 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.
> > > 
> > > Suggested-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> > > Signed-off-by: Lance Roy <ldr709@gmail.com>
> > > Cc: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> > > Cc: Lai Jiangshan <jiangshanlai@gmail.com>
> > > Cc: Peter Zijlstra <peterz@infradead.org>  
> > 
> > OK, this only has differences only in the comments, so I can reasonably
> > substitute it, even this near the next merge window.
> > 
> > But let's talk about the potential overflow.  If I understand correctly,
> > for this to happen, there needs to be ULONG_MAX/2 or thereabouts
> > srcu_read_lock() calls without matching srcu_read_unlock() calls.
> > Let's focus on 32-bit systems for the moment.
> > 
> > Lockdep allows at most 48 locks held at a given time by any single task,
> > and RCU does not pass in a non-NULL nest_lock -- if you acquire more than
> > that, a lockdep kernel will splat.  Each task has at least one 4K page of
> > kernel stack, so there can be at most 1,048,576 tasks (actually quite a
> > bit fewer due to the size of the task_struct and so on).  This allows
> > at most 50,331,648 unmatched srcu_read_lock() calls in the system,
> > which is not sufficient to cause overflow.
> > 
> > Or am I missing something here?
> > 
> > 								Thanx, Paul
> 
> It isn't the nest that is the problem. Here is a previous email I wrote
> describing the problem:
> 
> 
> The trouble is that disabling preemption is not enough to ensure that there
> is at most one srcu_read_lock() call per CPU that missed the srcu_flip().
> 
> Define a reader to be an SRCU lock+unlock pair. A reader is called active if it
> has incremented ->lock_count[] but hasn't incremented ->unlock_count[] yet, and
> completed if it has incremented ->unlock_count[]. I think that we only want to
> limit the number of active readers and the number of CPUs. In particular, I
> don't think there should be a limit on the rate of completion of read side
> critical section.
> 
> The goal of srcu_readers_active_idx_check() is to verify that there were zero
> active readers on the inactive index at some time during its execution. To do
> this, it totals the unlock counts, executes a memory barrier, totals the lock
> counts, and takes the difference. This difference counts the readers that are
> active when srcu_readers_lock_idx() gets to their CPU, plus the readers that
> completed after srcu_readers_unlock_idx() and before srcu_readers_lock_idx().
> If the true (infinite precision) value of the difference is zero, then there
> were no active readers at some point while srcu_readers_lock_idx() is running.
> However, the difference is only stored in a long, so there is a potential for
> overflow if too many readers complete during srcu_readers_active_idx_check().
> 
> For example, let's say there are three threads, each running on their own CPU:
> 
> int data, flag;
> struct srcu_struct *sp = /* ... */;
> 
> Thread 0:
> 	data = 1;
> 	synchronize_srcu(sp);
> 	flag = 1;
> 
> Thread 1:
> 	int data_r, flag_r;
> 	int idx = srcu_read_lock(sp);
> 	data_r = data;
> 	flag_r = flag;
> 	srcu_read_unlock(sp, idx);
> 	BUG_ON(flag_r == 1 && data_r == 0);
> 
> Thread 2:
> 	while (true) {
> 		int idx = srcu_read_lock(sp);
> 		srcu_read_unlock(sp, idx);
> 	}
> 
> Let's take the following execution order. Thread 1 increments
> the CPU 1 version of sp->lock_count[0], sets idx to zero, and loads data (0)
> into data_r. Thread 0 then sets data to be 1, verifies that there are no
> readers on index 1, and increments sp->completed, but the CPU actually doesn't
> preform the last operation, putting it off until the next memory barrier. Thread
> 0 then calls srcu_readers_active_idx_check() on index 0, which runs
> srcu_readers_unlock_idx() (returning 0). Right after srcu_readers_unlock_idx()
> completes, thread 2 starts running. Since Thread 0 hasn't actually incremented
> sp->completed in any way that is visible to thread 2, srcu_read_lock() will
> still return 0. Thread 2 can then run for ULONG_MAX iterations, setting
> the CPU 2 version of sp->unlock_count[0] to ULONG_MAX. CPU 0 then finally gets
> around to incrementing sp->completed, runs its memory barrier, and then reads
> the lock counts: 1, 0, ULONG_MAX. The total of ULONG_MAX+1 will overflow to 0
> and compare equal with earlier unlock count. Thread 0 will then think that the
> grace period is over and set flag to one. Thread 1 can then read flag (1) into
> flag_r and run srcu_read_unlock(). The BUG_ON statement will then fail.
> 
> Although ULONG_MAX readers completed during srcu_readers_active_idx_check(),
> there were at most 2 active readers at any time, so this program doesn't run
> into any limit.
> 
> I hope that was clear enough.

Yeah, we did have this same conversation awhile back, didn't we?

Back then, did I think to ask if this could be minimized or even prevented
by adding memory barriers appropriately?  ;-)

							Thanx, Paul

[toc] | [prev] | [next] | [standalone]

#1565458 — Re: [PATCH] srcu: Implement more-efficient reader counts

> Yeah, we did have this same conversation awhile back, didn't we?
> 
> Back then, did I think to ask if this could be minimized or even prevented
> by adding memory barriers appropriately?  ;-)
> 
> 							Thanx, Paul

Yes, it can be fixed by adding a memory barrier after incrementing ->completed
inside srcu_flip(). The upper limit on NR_CPUS turns out to be more complicated
than this, as it needs to deal with highly nested read side critical sections
mixed with the critical section loops, but only the one memory barrier should
be necessary.

Thanks,
Lance

Begin forwarded message:

Date: Fri, 18 Nov 2016 16:54:42 -0800
From: Lance Roy <ldr709@gmail.com>
To: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
Cc: linux-kernel@vger.kernel.org, mingo@kernel.org, jiangshanlai@gmail.com,
dipankar@in.ibm.com, akpm@linux-foundation.org, mathieu.desnoyers@efficios.com,
josh@joshtriplett.org, tglx@linutronix.de, peterz@infradead.org,
rostedt@goodmis.org, dhowells@redhat.com, edumazet@google.com,
dvhart@linux.intel.com, fweisbec@gmail.com, oleg@redhat.com,
bobby.prani@gmail.com Subject: Re: [RFC PATCH] SRCU: More efficient reader
counts.


On Fri, 18 Nov 2016 15:13:45 -0800
"Paul E. McKenney" <paulmck@linux.vnet.ibm.com> wrote:
> On Fri, Nov 18, 2016 at 12:33:00PM -0800, Lance Roy wrote:    
> > The trouble is that disabling preemption is not enough to ensure that there
> > is at most one srcu_read_lock() call per CPU that missed the srcu_flip().
> > 
> > Define a reader to be an SRCU lock+unlock pair. A reader is called active
> > if it has incremented ->lock_count[] but hasn't incremented    
> > ->unlock_count[] yet, and completed if it has incremented
> > ->unlock_count[]. I think that we only want to limit the number of active  
> > readers and the number of CPUs. In particular, I don't think there should
> > be a limit on the rate of completion of read side critical section.
> > 
> > The goal of srcu_readers_active_idx_check() is to verify that there were
> > zero active readers on the inactive index at some time during its
> > execution. To do this, it totals the unlock counts, executes a memory
> > barrier, totals the lock counts, and takes the difference. This difference
> > counts the readers that are active when srcu_readers_lock_idx() gets to
> > their CPU, plus the readers that completed after srcu_readers_unlock_idx()
> > and before srcu_readers_lock_idx(). If the true (infinite precision) value
> > of the difference is zero, then there were no active readers at some point
> > while srcu_readers_lock_idx() is running. However, the difference is only
> > stored in a long, so there is a potential for overflow if too many readers
> > complete during srcu_readers_active_idx_check().
> > 
> > For example, let's say there are three threads, each running on their own
> > CPU:
> > 
> > int data, flag;
> > struct srcu_struct *sp = /* ... */;
> > 
> > Thread 0:
> > 	data = 1;
> > 	synchronize_srcu(sp);
> > 	flag = 1;
> > 
> > Thread 1:
> > 	int data_r, flag_r;
> > 	int idx = srcu_read_lock(sp);
> > 	data_r = data;
> > 	flag_r = flag;
> > 	srcu_read_unlock(sp, idx);
> > 	BUG_ON(flag_r == 1 && data_r == 0);
> > 
> > Thread 2:
> > 	while (true) {
> > 		int idx = srcu_read_lock(sp);
> > 		srcu_read_unlock(sp, idx);
> > 	}
> > 
> > Let's take the following execution order. Thread 1 increments
> > the CPU 1 version of sp->lock_count[0], sets idx to zero, and loads data (0)
> > into data_r. Thread 0 then sets data to be 1, verifies that there are no
> > readers on index 1, and increments sp->completed, but the CPU actually
> > doesn't preform the last operation, putting it off until the next memory
> > barrier. Thread 0 then calls srcu_readers_active_idx_check() on index 0,
> > which runs srcu_readers_unlock_idx() (returning 0). Right after
> > srcu_readers_unlock_idx() completes, thread 2 starts running. Since Thread
> > 0 hasn't actually incremented sp->completed in any way that is visible to
> > thread 2, srcu_read_lock() will still return 0. Thread 2 can then run for
> > ULONG_MAX iterations, setting the CPU 2 version of sp->unlock_count[0] to
> > ULONG_MAX. CPU 0 then finally gets around to incrementing sp->completed,
> > runs its memory barrier, and then reads the lock counts: 1, 0, ULONG_MAX.
> > The total of ULONG_MAX+1 will overflow to 0 and compare equal with earlier
> > unlock count. Thread 0 will then think that the grace period is over and
> > set flag to one. Thread 1 can then read flag (1) into flag_r and run
> > srcu_read_unlock(). The BUG_ON statement will then fail.
> > 
> > Although ULONG_MAX readers completed during srcu_readers_active_idx_check(),
> > there were at most 2 active readers at any time, so this program doesn't run
> > into any limit.
> > 
> > I hope that was clear enough.      
> 
> Indeed it is!
> 
> So adding a full memory barrier immediately after the srcu_flip() should
> prevent this, because if the updater failed to see an unlock increment,
> the second following lock for that CPU/task would be guaranteed to see
> the flip.  Or am I still missing something?    
Yes, adding a full memory barrier after srcu_flip() prevents this problem.

> Is there a sequence of events that requires a full memory barrier
> before the srcu_flip()?    
I am now unsure if a memory barrier before srcu_flip() is necessary. I thought
that it would be needed to prevent the CPU from preforming the increment early,
but I have just noticed that srcu_advance_batches() will return early if the
first try_check_zero() fails, creating a control dependency. I think that this
control dependency should be enough to prevent the problem from occurring.

One interesting thing about this version is that there is only an address
dependency between the load of ->completed and the increment of ->load_count[].
This means that without an smp_read_barrier_depends() between the two, a reader
could use the new value of ->completed to increment ->load_count[], before
actually reading ->completed. (I was surprised that this ordering doesn't come
for free, as it seems like violating it would require speculative writes.) It
doesn't matter much if the dependency barrier is actually there, because
leaving it out just means at most 1 more spurious increment per CPU.

I think that with the added synchronization in srcu_flip() there would be at
most 3 * NR_CPUS readers that start and complete inside one
srcu_readers_active_idx_check(). With the read side dependency barrier this
would drop to 2 * NR_CPUS.

Thanks,
Lance

[toc] | [prev] | [next] | [standalone]

#1566008 — Re: [PATCH] srcu: Implement more-efficient reader counts

On Mon, Jan 23, 2017 at 07:26:45PM -0800, Lance Roy wrote:
> > Yeah, we did have this same conversation awhile back, didn't we?
> > 
> > Back then, did I think to ask if this could be minimized or even prevented
> > by adding memory barriers appropriately?  ;-)
> > 
> > 							Thanx, Paul
> 
> Yes, it can be fixed by adding a memory barrier after incrementing ->completed
> inside srcu_flip(). The upper limit on NR_CPUS turns out to be more complicated
> than this, as it needs to deal with highly nested read side critical sections
> mixed with the critical section loops, but only the one memory barrier should
> be necessary.

Something like this, then?

							Thanx, Paul

------------------------------------------------------------------------

commit 35be9e413dde662fc9661352e595105ac4b0b167
Author: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Date:   Tue Jan 24 08:51:34 2017 -0800

    srcu: Reduce probability of SRCU ->unlock_count[] counter overflow
    
    Because there are no memory barriers between the srcu_flip() ->completed
    increment and the summation of the read-side ->unlock_count[] counters,
    both the compiler and the CPU can reorder the summation with the
    ->completed increment.  If the updater is preempted long enough during
    this process, the read-side counters could overflow, resulting in a
    too-short grace period.
    
    This commit therefore adds a memory barrier just after the ->completed
    increment, ensuring that if the summation misses an increment of
    ->unlock_count[] from __srcu_read_unlock(), the next __srcu_read_lock()
    will see the new value of ->completed, thus bounding the number of
    ->unlock_count[] increments that can be missed to NR_CPUS.  The actual
    overflow computation is more complex due to the possibility of nesting
    of __srcu_read_lock().
    
    Reported-by: Lance Roy <ldr709@gmail.com>
    Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>

diff --git a/kernel/rcu/srcu.c b/kernel/rcu/srcu.c
index d3378ceb9762..aefe3ab20a6a 100644
--- a/kernel/rcu/srcu.c
+++ b/kernel/rcu/srcu.c
@@ -337,7 +337,16 @@ static bool try_check_zero(struct srcu_struct *sp, int idx, int trycount)
  */
 static void srcu_flip(struct srcu_struct *sp)
 {
-	sp->completed++;
+	WRITE_ONCE(sp->completed, sp->completed + 1);
+
+	/*
+	 * Ensure that if the updater misses an __srcu_read_unlock()
+	 * increment, that task's next __srcu_read_lock() will see the
+	 * above counter update.  Note that both this memory barrier
+	 * and the one in srcu_readers_active_idx_check() provide the
+	 * guarantee for __srcu_read_lock().
+	 */
+	smp_mb(); /* D */  /* Pairs with C. */
 }
 
 /*

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web