Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > linux.kernel > #1566194 > unrolled thread
| Started by | "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> |
|---|---|
| First post | 2017-01-24 23:10 +0100 |
| Last post | 2017-01-24 23:10 +0100 |
| Articles | 5 — 2 participants |
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.
[PATCH v3 tip/core/rcu 0/4] SRCU updates for 4.11 "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2017-01-24 23:10 +0100
[PATCH v3 tip/core/rcu 1/4] srcu: Implement more-efficient reader counts "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2017-01-24 23:10 +0100
Re: [PATCH v3 tip/core/rcu 1/4] srcu: Implement more-efficient reader counts Lance Roy <ldr709@gmail.com> - 2017-01-25 19:20 +0100
Re: [PATCH v3 tip/core/rcu 1/4] srcu: Implement more-efficient reader counts "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2017-01-25 22:10 +0100
[PATCH v3 tip/core/rcu 2/4] srcu: Force full grace-period ordering "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2017-01-24 23:10 +0100
| From | "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> |
|---|---|
| Date | 2017-01-24 23:10 +0100 |
| Subject | [PATCH v3 tip/core/rcu 0/4] SRCU updates for 4.11 |
| Message-ID | <t3hrQ-1E3-5@gated-at.bofh.it> |
Hello! This series provides v3 updates to SRCU: 1. This is a rewrite of the algorithm simplifying reader-count tracking. Algorithm courtesy of Mathieu Desnoyers, implementation courtesy of Lance Roy. 2. Force full grace-period ordering in SRCU. 3. Add CBMC-based formal verification for SRCU, courtesy of Lance Roy. Updates since v2: o Fix memory-barrier problems noted by Lance Roy. o Add memory barrier to lower probability of counter overflow, also noted by Lance Roy. Updates since v1: o Applied Ingo Molnar feedback. o Fix some checkpatch issues. Thanx, Paul ------------------------------------------------------------------------ include/linux/rcupdate.h | 12 include/linux/srcu.h | 10 kernel/rcu/rcutorture.c | 19 kernel/rcu/srcu.c | 144 +-- kernel/rcu/tree.h | 12 tools/testing/selftests/rcutorture/formal/srcu-cbmc/.gitignore | 1 tools/testing/selftests/rcutorture/formal/srcu-cbmc/Makefile | 16 tools/testing/selftests/rcutorture/formal/srcu-cbmc/include/linux/.gitignore | 1 tools/testing/selftests/rcutorture/formal/srcu-cbmc/include/linux/kconfig.h | 1 tools/testing/selftests/rcutorture/formal/srcu-cbmc/include/linux/types.h | 155 ++++ tools/testing/selftests/rcutorture/formal/srcu-cbmc/modify_srcu.awk | 375 ++++++++++ tools/testing/selftests/rcutorture/formal/srcu-cbmc/src/assume.h | 16 tools/testing/selftests/rcutorture/formal/srcu-cbmc/src/barriers.h | 41 + tools/testing/selftests/rcutorture/formal/srcu-cbmc/src/bug_on.h | 13 tools/testing/selftests/rcutorture/formal/srcu-cbmc/src/combined_source.c | 13 tools/testing/selftests/rcutorture/formal/srcu-cbmc/src/config.h | 27 tools/testing/selftests/rcutorture/formal/srcu-cbmc/src/include_srcu.c | 31 tools/testing/selftests/rcutorture/formal/srcu-cbmc/src/int_typedefs.h | 33 tools/testing/selftests/rcutorture/formal/srcu-cbmc/src/locks.h | 220 +++++ tools/testing/selftests/rcutorture/formal/srcu-cbmc/src/misc.c | 11 tools/testing/selftests/rcutorture/formal/srcu-cbmc/src/misc.h | 58 + tools/testing/selftests/rcutorture/formal/srcu-cbmc/src/percpu.h | 92 ++ tools/testing/selftests/rcutorture/formal/srcu-cbmc/src/preempt.c | 78 ++ tools/testing/selftests/rcutorture/formal/srcu-cbmc/src/preempt.h | 58 + tools/testing/selftests/rcutorture/formal/srcu-cbmc/src/simple_sync_srcu.c | 50 + tools/testing/selftests/rcutorture/formal/srcu-cbmc/src/workqueues.h | 102 ++ tools/testing/selftests/rcutorture/formal/srcu-cbmc/tests/store_buffering/.gitignore | 1 tools/testing/selftests/rcutorture/formal/srcu-cbmc/tests/store_buffering/Makefile | 11 tools/testing/selftests/rcutorture/formal/srcu-cbmc/tests/store_buffering/assert_end.fail | 1 tools/testing/selftests/rcutorture/formal/srcu-cbmc/tests/store_buffering/force.fail | 1 tools/testing/selftests/rcutorture/formal/srcu-cbmc/tests/store_buffering/force2.fail | 1 tools/testing/selftests/rcutorture/formal/srcu-cbmc/tests/store_buffering/force3.fail | 1 tools/testing/selftests/rcutorture/formal/srcu-cbmc/tests/store_buffering/test.c | 72 + tools/testing/selftests/rcutorture/formal/srcu-cbmc/tests/test_script.sh | 102 ++ 34 files changed, 1679 insertions(+), 100 deletions(-)
[toc] | [next] | [standalone]
| From | "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> |
|---|---|
| Date | 2017-01-24 23:10 +0100 |
| Subject | [PATCH v3 tip/core/rcu 1/4] srcu: Implement more-efficient reader counts |
| Message-ID | <t3hrQ-1E3-19@gated-at.bofh.it> |
| In reply to | #1566194 |
From: Lance Roy <ldr709@gmail.com>
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().
A possible problem with this patch is that it can only handle
ULONG_MAX - NR_CPUS simultaneous readers, whereas the old version could
handle up to ULONG_MAX.
Suggested-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Signed-off-by: Lance Roy <ldr709@gmail.com>
Signed-off-by: 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 | 123 ++++++++++++++++++------------------------------
3 files changed, 67 insertions(+), 85 deletions(-)
diff --git a/include/linux/srcu.h b/include/linux/srcu.h
index dc8eb63c6568..a598cf3ac70c 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 87c51225ceec..d81345be730e 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 9b9cdd549caa..ddabf5fbf562 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,78 @@ 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 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.
+ * 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.
+ * Note that there can be at most NR_CPUS worth of readers using the old
+ * index that haven't incremented ->lock_count[] yet. Therefore, the
+ * sum of the ->lock_count[]s cannot increment enough times to overflow
+ * and end up equal the sum of the ->unlock_count[]s, as long as there
+ * are at most ULONG_MAX - NR_CPUS readers at a time. (Yes, this does
+ * mean that systems having more than a billion or so CPUs need to be
+ * 64-bit systems.) Therefore, the only way that the return values of
+ * the two calls to srcu_readers_(un)lock_idx() can be equal is if there
+ * are no active readers using this index.
*/
- 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 +230,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 +266,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 +281,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 +316,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.5.2
[toc] | [prev] | [next] | [standalone]
| From | Lance Roy <ldr709@gmail.com> |
|---|---|
| Date | 2017-01-25 19:20 +0100 |
| Subject | Re: [PATCH v3 tip/core/rcu 1/4] srcu: Implement more-efficient reader counts |
| Message-ID | <t3AkN-5aQ-15@gated-at.bofh.it> |
| In reply to | #1566196 |
Could you please use the new patch? The remark about ULONG_MAX - NR_CPUS is
incorrect in this one.
Thanks,
Lance
On Tue, 24 Jan 2017 14:00:26 -0800
"Paul E. McKenney" <paulmck@linux.vnet.ibm.com> wrote:
> From: Lance Roy <ldr709@gmail.com>
>
> 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().
>
> A possible problem with this patch is that it can only handle
> ULONG_MAX - NR_CPUS simultaneous readers, whereas the old version could
> handle up to ULONG_MAX.
>
> Suggested-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> Signed-off-by: Lance Roy <ldr709@gmail.com>
> Signed-off-by: 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 | 123
> ++++++++++++++++++------------------------------ 3 files changed, 67
> insertions(+), 85 deletions(-)
>
> diff --git a/include/linux/srcu.h b/include/linux/srcu.h
> index dc8eb63c6568..a598cf3ac70c 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 87c51225ceec..d81345be730e 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 9b9cdd549caa..ddabf5fbf562 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,78 @@ 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 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.
> + * 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.
> + * Note that there can be at most NR_CPUS worth of readers using the
> old
> + * index that haven't incremented ->lock_count[] yet. Therefore, the
> + * sum of the ->lock_count[]s cannot increment enough times to
> overflow
> + * and end up equal the sum of the ->unlock_count[]s, as long as
> there
> + * are at most ULONG_MAX - NR_CPUS readers at a time. (Yes, this
> does
> + * mean that systems having more than a billion or so CPUs need to be
> + * 64-bit systems.) Therefore, the only way that the return values
> of
> + * the two calls to srcu_readers_(un)lock_idx() can be equal is if
> there
> + * are no active readers using this index.
> */
> - 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 +230,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 +266,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 +281,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 +316,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)
[toc] | [prev] | [next] | [standalone]
| From | "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> |
|---|---|
| Date | 2017-01-25 22:10 +0100 |
| Subject | Re: [PATCH v3 tip/core/rcu 1/4] srcu: Implement more-efficient reader counts |
| Message-ID | <t3CZk-6Zx-15@gated-at.bofh.it> |
| In reply to | #1566806 |
On Wed, Jan 25, 2017 at 10:17:52AM -0800, Lance Roy wrote:
> Could you please use the new patch? The remark about ULONG_MAX - NR_CPUS is
> incorrect in this one.
Apologies -- I very carefully applied your patch, verified that it changed
only comments, and then very carefully forgot to rebase the rest of the
commits on top of it.
Fixed on -rcu branch dev.2017.01.25a.
Thanx, Paul
> Thanks,
> Lance
>
> On Tue, 24 Jan 2017 14:00:26 -0800
> "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> wrote:
>
> > From: Lance Roy <ldr709@gmail.com>
> >
> > 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().
> >
> > A possible problem with this patch is that it can only handle
> > ULONG_MAX - NR_CPUS simultaneous readers, whereas the old version could
> > handle up to ULONG_MAX.
> >
> > Suggested-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> > Signed-off-by: Lance Roy <ldr709@gmail.com>
> > Signed-off-by: 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 | 123
> > ++++++++++++++++++------------------------------ 3 files changed, 67
> > insertions(+), 85 deletions(-)
> >
> > diff --git a/include/linux/srcu.h b/include/linux/srcu.h
> > index dc8eb63c6568..a598cf3ac70c 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 87c51225ceec..d81345be730e 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 9b9cdd549caa..ddabf5fbf562 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,78 @@ 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 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.
> > + * 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.
> > + * Note that there can be at most NR_CPUS worth of readers using the
> > old
> > + * index that haven't incremented ->lock_count[] yet. Therefore, the
> > + * sum of the ->lock_count[]s cannot increment enough times to
> > overflow
> > + * and end up equal the sum of the ->unlock_count[]s, as long as
> > there
> > + * are at most ULONG_MAX - NR_CPUS readers at a time. (Yes, this
> > does
> > + * mean that systems having more than a billion or so CPUs need to be
> > + * 64-bit systems.) Therefore, the only way that the return values
> > of
> > + * the two calls to srcu_readers_(un)lock_idx() can be equal is if
> > there
> > + * are no active readers using this index.
> > */
> > - 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 +230,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 +266,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 +281,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 +316,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)
>
[toc] | [prev] | [next] | [standalone]
| From | "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> |
|---|---|
| Date | 2017-01-24 23:10 +0100 |
| Subject | [PATCH v3 tip/core/rcu 2/4] srcu: Force full grace-period ordering |
| Message-ID | <t3hrR-1E3-25@gated-at.bofh.it> |
| In reply to | #1566194 |
If a process invokes synchronize_srcu(), is delayed just the right amount
of time, and thus does not sleep when waiting for the grace period to
complete, there is no ordering between the end of the grace period and
the code following the synchronize_srcu(). Similarly, there can be a
lack of ordering between the end of the SRCU grace period and callback
invocation.
This commit adds the necessary ordering.
Reported-by: Lance Roy <ldr709@gmail.com>
Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
[ paulmck: Further smp_mb() adjustment per email with Lance Roy. ]
---
include/linux/rcupdate.h | 12 ++++++++++++
kernel/rcu/srcu.c | 10 ++++++++--
kernel/rcu/tree.h | 12 ------------
3 files changed, 20 insertions(+), 14 deletions(-)
diff --git a/include/linux/rcupdate.h b/include/linux/rcupdate.h
index 01f71e1d2e94..6ade6a52d9d4 100644
--- a/include/linux/rcupdate.h
+++ b/include/linux/rcupdate.h
@@ -1161,5 +1161,17 @@ do { \
ftrace_dump(oops_dump_mode); \
} while (0)
+/*
+ * Place this after a lock-acquisition primitive to guarantee that
+ * an UNLOCK+LOCK pair acts as a full barrier. This guarantee applies
+ * if the UNLOCK and LOCK are executed by the same CPU or if the
+ * UNLOCK and LOCK operate on the same lock variable.
+ */
+#ifdef CONFIG_PPC
+#define smp_mb__after_unlock_lock() smp_mb() /* Full ordering for lock. */
+#else /* #ifdef CONFIG_PPC */
+#define smp_mb__after_unlock_lock() do { } while (0)
+#endif /* #else #ifdef CONFIG_PPC */
+
#endif /* __LINUX_RCUPDATE_H */
diff --git a/kernel/rcu/srcu.c b/kernel/rcu/srcu.c
index ddabf5fbf562..fcd07eda95a3 100644
--- a/kernel/rcu/srcu.c
+++ b/kernel/rcu/srcu.c
@@ -359,6 +359,7 @@ void call_srcu(struct srcu_struct *sp, struct rcu_head *head,
head->next = NULL;
head->func = func;
spin_lock_irqsave(&sp->queue_lock, flags);
+ smp_mb__after_unlock_lock(); /* Caller's prior accesses before GP. */
rcu_batch_queue(&sp->batch_queue, head);
if (!sp->running) {
sp->running = true;
@@ -392,6 +393,7 @@ static void __synchronize_srcu(struct srcu_struct *sp, int trycount)
head->next = NULL;
head->func = wakeme_after_rcu;
spin_lock_irq(&sp->queue_lock);
+ smp_mb__after_unlock_lock(); /* Caller's prior accesses before GP. */
if (!sp->running) {
/* steal the processing owner */
sp->running = true;
@@ -411,8 +413,11 @@ static void __synchronize_srcu(struct srcu_struct *sp, int trycount)
spin_unlock_irq(&sp->queue_lock);
}
- if (!done)
+ if (!done) {
wait_for_completion(&rcu.completion);
+ smp_mb(); /* Caller's later accesses after GP. */
+ }
+
}
/**
@@ -580,7 +585,8 @@ static void srcu_advance_batches(struct srcu_struct *sp, int trycount)
/*
* Invoke a limited number of SRCU callbacks that have passed through
* their grace period. If there are more to do, SRCU will reschedule
- * the workqueue.
+ * the workqueue. Note that needed memory barriers have been executed
+ * in this task's context by srcu_readers_active_idx_check().
*/
static void srcu_invoke_callbacks(struct srcu_struct *sp)
{
diff --git a/kernel/rcu/tree.h b/kernel/rcu/tree.h
index fe98dd24adf8..abcc25bdcb29 100644
--- a/kernel/rcu/tree.h
+++ b/kernel/rcu/tree.h
@@ -688,18 +688,6 @@ static inline void rcu_nocb_q_lengths(struct rcu_data *rdp, long *ql, long *qll)
#endif /* #ifdef CONFIG_RCU_TRACE */
/*
- * Place this after a lock-acquisition primitive to guarantee that
- * an UNLOCK+LOCK pair act as a full barrier. This guarantee applies
- * if the UNLOCK and LOCK are executed by the same CPU or if the
- * UNLOCK and LOCK operate on the same lock variable.
- */
-#ifdef CONFIG_PPC
-#define smp_mb__after_unlock_lock() smp_mb() /* Full ordering for lock. */
-#else /* #ifdef CONFIG_PPC */
-#define smp_mb__after_unlock_lock() do { } while (0)
-#endif /* #else #ifdef CONFIG_PPC */
-
-/*
* Wrappers for the rcu_node::lock acquire and release.
*
* Because the rcu_nodes form a tree, the tree traversal locking will observe
--
2.5.2
[toc] | [prev] | [standalone]
Back to top | Article view | linux.kernel
csiph-web