[PATCH tip/core/rcu 0/3] increase rcutorture intensity and fix a couple resulting bugs

[PATCH tip/core/rcu 0/3] increase rcutorture intensity and fix a couple resulting bugs

[Paul E. McKenney]

This patch series increases the intensity of rcutorture testing for
TREE_PREEMPT_RCU and provides fixes for a couple resulting bugs.

o	Make rcutorture's RCU read-side critical sections occasionally
	spin for a few tens of milliseconds, which greatly increases
	the probability that they will be preempted and that quiescent
	states will be forced.  Yes, this does uncover some bugs in
	TREE_PREEMPT_RCU (though TREE_RCU passes with flying colors).

o	Fix a bug where rnp->gpnum was not being updated.  This
	increases TREE_PREEMPT_RCU's reliability considerably, though
	bugs still remain.

o	Make the initialization of multi-node trees of rcu_node
	structures unconditionally acquire rnp->lock.  This simplifies
	the code a bit and will make it easier to allow grace-period
	initialization become preemptable, should this be needed.

Next steps include applying review comments, adding expedited grace
periods, and chasing down remaining bugs.  Longer term, RCU priority
boosting.

 b/kernel/rcutorture.c |   16 +++++++++-------
 b/kernel/rcutree.c    |    7 +++++--
 kernel/rcutree.c      |   42 ++++++++++++------------------------------
 3 files changed, 26 insertions(+), 39 deletions(-)

[PATCH tip/core/rcu 1/3] rcutorture: Occasionally delay readers enough to make RCU force_quiescent_state

[Paul E. McKenney]

From: Josh Triplett <josh@joshtriplett.org>

rcutorture already delays readers, but never for long enough to make RCU
force a quiescent state.  Add an occasional delay of 50ms.

Signed-off-by: Josh Triplett <josh@joshtriplett.org>
---
 kernel/rcutorture.c |   15 +++++++++------
 1 files changed, 9 insertions(+), 6 deletions(-)

diff --git a/kernel/rcutorture.c b/kernel/rcutorture.c
index b33db53..328a825 100644
--- a/kernel/rcutorture.c
+++ b/kernel/rcutorture.c
@@ -281,14 +281,17 @@ static int rcu_torture_read_lock(void) __acquires(RCU)
 
 static void rcu_read_delay(struct rcu_random_state *rrsp)
 {
-	long delay;
-	const long longdelay = 200;
+	const unsigned long shortdelay_us = 200;
+	const unsigned long longdelay_ms = 50;
 
-	/* We want there to be long-running readers, but not all the time. */
+	/* We want a short delay sometimes to make a reader delay the grace
+	 * period, and we want a long delay occasionally to trigger
+	 * force_quiescent_state. */
 
-	delay = rcu_random(rrsp) % (nrealreaders * 2 * longdelay);
-	if (!delay)
-		udelay(longdelay);
+	if (!(rcu_random(rrsp) % (nrealreaders * 2000 * longdelay_ms)))
+		mdelay(longdelay_ms);
+	if (!(rcu_random(rrsp) % (nrealreaders * 2 * shortdelay_us)))
+		udelay(shortdelay_us);
 }
 
 static void rcu_torture_read_unlock(int idx) __releases(RCU)
-- 
1.5.2.5

[PATCH tip/core/rcu 2/3] Need to update rnp->gpnum if preemptable RCU is to be reliable.

[Paul E. McKenney]

From: Paul E. McKenney <paulmck@linux.vnet.ibm.com>

Without this patch, tasks preempted in RCU read-side critical sections
can fail to block the grace period, given that rnp->gpnum is used to
determine which rnp->blocked_tasks[] element the preempted task is
enqueued on.  Before the patch, rnp->gpnum is always zero, so preempted
tasks are always enqueued on rnp->blocked_tasks[0], which is correct
only when the current CPU has not checked into the current grace period
and the grace-period number is even, or, similarly, if the current CPU
-has- checked into the current grace period and the grace-period number
is odd.

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
---
 kernel/rcutree.c |    6 +++++-
 1 files changed, 5 insertions(+), 1 deletions(-)

diff --git a/kernel/rcutree.c b/kernel/rcutree.c
index 71bc797..03866bd 100644
--- a/kernel/rcutree.c
+++ b/kernel/rcutree.c
@@ -627,6 +627,7 @@ rcu_start_gp(struct rcu_state *rsp, unsigned long flags)
 	/* Special-case the common single-level case. */
 	if (NUM_RCU_NODES == 1) {
 		rnp->qsmask = rnp->qsmaskinit;
+		rnp->gpnum = rsp->gpnum;
 		rsp->signaled = RCU_SIGNAL_INIT; /* force_quiescent_state OK. */
 		spin_unlock_irqrestore(&rnp->lock, flags);
 		return;
@@ -652,8 +653,10 @@ rcu_start_gp(struct rcu_state *rsp, unsigned long flags)
 	 */
 
 	rnp_end = rsp->level[NUM_RCU_LVLS - 1];
-	for (rnp_cur = &rsp->node[0]; rnp_cur < rnp_end; rnp_cur++)
+	for (rnp_cur = &rsp->node[0]; rnp_cur < rnp_end; rnp_cur++) {
 		rnp_cur->qsmask = rnp_cur->qsmaskinit;
+		rnp->gpnum = rsp->gpnum;
+	}
 
 	/*
 	 * Now set up the leaf nodes.  Here we must be careful.  First,
@@ -674,6 +677,7 @@ rcu_start_gp(struct rcu_state *rsp, unsigned long flags)
 	for (; rnp_cur < rnp_end; rnp_cur++) {
 		spin_lock(&rnp_cur->lock);	/* irqs already disabled. */
 		rnp_cur->qsmask = rnp_cur->qsmaskinit;
+		rnp->gpnum = rsp->gpnum;
 		spin_unlock(&rnp_cur->lock);	/* irqs already disabled. */
 	}
 
-- 
1.5.2.5

[PATCH tip/core/rcu 3/3] Initialize multi-level RCU grace periods holding locks

[Paul E. McKenney]

From: Paul E. McKenney <paulmck@linux.vnet.ibm.com>

Prior implementations initialized the root and any internal nodes without
holding locks, then initialized the leaves holding locks.  This is a
false economy, as the leaf nodes will usually greatly outnumber the root
and internal nodes.  Acquiring locks on all nodes is conceptually much
simpler as well.

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
---
 kernel/rcutree.c |   41 ++++++++++++-----------------------------
 1 files changed, 12 insertions(+), 29 deletions(-)

diff --git a/kernel/rcutree.c b/kernel/rcutree.c
index 03866bd..bca0aba 100644
--- a/kernel/rcutree.c
+++ b/kernel/rcutree.c
@@ -640,41 +640,24 @@ rcu_start_gp(struct rcu_state *rsp, unsigned long flags)
 	spin_lock(&rsp->onofflock);  /* irqs already disabled. */
 
 	/*
-	 * Set the quiescent-state-needed bits in all the non-leaf RCU
-	 * nodes for all currently online CPUs.  This operation relies
-	 * on the layout of the hierarchy within the rsp->node[] array.
-	 * Note that other CPUs will access only the leaves of the
-	 * hierarchy, which still indicate that no grace period is in
-	 * progress.  In addition, we have excluded CPU-hotplug operations.
-	 *
-	 * We therefore do not need to hold any locks.  Any required
-	 * memory barriers will be supplied by the locks guarding the
-	 * leaf rcu_nodes in the hierarchy.
-	 */
-
-	rnp_end = rsp->level[NUM_RCU_LVLS - 1];
-	for (rnp_cur = &rsp->node[0]; rnp_cur < rnp_end; rnp_cur++) {
-		rnp_cur->qsmask = rnp_cur->qsmaskinit;
-		rnp->gpnum = rsp->gpnum;
-	}
-
-	/*
-	 * Now set up the leaf nodes.  Here we must be careful.  First,
-	 * we need to hold the lock in order to exclude other CPUs, which
-	 * might be contending for the leaf nodes' locks.  Second, as
-	 * soon as we initialize a given leaf node, its CPUs might run
-	 * up the rest of the hierarchy.  We must therefore acquire locks
-	 * for each node that we touch during this stage.  (But we still
-	 * are excluding CPU-hotplug operations.)
+	 * Set the quiescent-state-needed bits in all the rcu_node
+	 * structures for all currently online CPUs in breadth-first
+	 * order, starting from the root rcu_node structure.  This
+	 * operation relies on the layout of the hierarchy within the
+	 * rsp->node[] array.  Note that other CPUs will access only
+	 * the leaves of the hierarchy, which still indicate that no
+	 * grace period is in progress, at least until the corresponding
+	 * leaf node has been initialized.  In addition, we have excluded
+	 * CPU-hotplug operations.
 	 *
 	 * Note that the grace period cannot complete until we finish
 	 * the initialization process, as there will be at least one
 	 * qsmask bit set in the root node until that time, namely the
-	 * one corresponding to this CPU.
+	 * one corresponding to this CPU, due to the fact that we have
+	 * irqs disabled.
 	 */
 	rnp_end = &rsp->node[NUM_RCU_NODES];
-	rnp_cur = rsp->level[NUM_RCU_LVLS - 1];
-	for (; rnp_cur < rnp_end; rnp_cur++) {
+	for (rnp_cur = &rsp->node[0]; rnp_cur < rnp_end; rnp_cur++) {
 		spin_lock(&rnp_cur->lock);	/* irqs already disabled. */
 		rnp_cur->qsmask = rnp_cur->qsmaskinit;
 		rnp->gpnum = rsp->gpnum;
-- 
1.5.2.5

Re: [PATCH tip/core/rcu 0/3] increase rcutorture intensity and fix a couple resulting bugs

[Steven Rostedt]

On Tue, 2009-09-08 at 15:53 -0700, Paul E. McKenney wrote:
> This patch series increases the intensity of rcutorture testing for
> TREE_PREEMPT_RCU and provides fixes for a couple resulting bugs.
> 
> o	Make rcutorture's RCU read-side critical sections occasionally
> 	spin for a few tens of milliseconds, which greatly increases
> 	the probability that they will be preempted and that quiescent
> 	states will be forced.  Yes, this does uncover some bugs in
> 	TREE_PREEMPT_RCU (though TREE_RCU passes with flying colors).
> 
> o	Fix a bug where rnp->gpnum was not being updated.  This
> 	increases TREE_PREEMPT_RCU's reliability considerably, though
> 	bugs still remain.
> 
> o	Make the initialization of multi-node trees of rcu_node
> 	structures unconditionally acquire rnp->lock.  This simplifies
> 	the code a bit and will make it easier to allow grace-period
> 	initialization become preemptable, should this be needed.
> 
> Next steps include applying review comments, adding expedited grace
> periods, and chasing down remaining bugs.  Longer term, RCU priority
> boosting.

Hi Paul,

These patches look decent to me.

If it makes you feel comfy:

Acked-by: Steven Rostedt <rostedt@goodmis.org>

-- Steve

Re: [PATCH tip/core/rcu 0/3] increase rcutorture intensity and fix a couple resulting bugs

[Valdis.Kletnieks]

[-- Attachment #1: Type: text/plain, Size: 423 bytes --]

On Tue, 08 Sep 2009 15:53:49 PDT, "Paul E. McKenney" said:
> This patch series increases the intensity of rcutorture testing for
> TREE_PREEMPT_RCU and provides fixes for a couple resulting bugs.

Minor bisection nit - should patch 1/3 be renumbered to 3/3, so the two bugfix
patches go in before the patch that makes the unpatched bugs visible? Otherwise
if a bisect waypoint happens to land on 1/3, oddness can happen...

[-- Attachment #2: Type: application/pgp-signature, Size: 227 bytes --]

Re: [PATCH tip/core/rcu 0/3] increase rcutorture intensity and fix a couple resulting bugs

[Paul E. McKenney]

On Wed, Sep 09, 2009 at 01:43:59PM -0400, Valdis.Kletnieks@vt.edu wrote:
> On Tue, 08 Sep 2009 15:53:49 PDT, "Paul E. McKenney" said:
> > This patch series increases the intensity of rcutorture testing for
> > TREE_PREEMPT_RCU and provides fixes for a couple resulting bugs.
> 
> Minor bisection nit - should patch 1/3 be renumbered to 3/3, so the two bugfix
> patches go in before the patch that makes the unpatched bugs visible? Otherwise
> if a bisect waypoint happens to land on 1/3, oddness can happen...

Agreed.  That said, the larger series of patches that this patchset
is part of has several other similar bisection issues.  My guess is that
the larger series will be refactored at some point.

Besides which, I expect to be sending in more bug fixes...

							Thanx, Paul

Re: [PATCH tip/core/rcu 1/3] rcutorture: Occasionally delay readers enough to make RCU force_quiescent_state

[Ingo Molnar]

* Paul E. McKenney <paulmck@linux.vnet.ibm.com> wrote:

> From: Josh Triplett <josh@joshtriplett.org>
> 
> rcutorture already delays readers, but never for long enough to make RCU
> force a quiescent state.  Add an occasional delay of 50ms.
> 
> Signed-off-by: Josh Triplett <josh@joshtriplett.org>

Small patch flow nit - your Signed-off-by after Josh's signoff is 
missing.

	Ingo

Re: [PATCH tip/core/rcu 0/3] increase rcutorture intensity and fix a couple resulting bugs

[Ingo Molnar]

* Valdis.Kletnieks@vt.edu <Valdis.Kletnieks@vt.edu> wrote:

> On Tue, 08 Sep 2009 15:53:49 PDT, "Paul E. McKenney" said:
> > This patch series increases the intensity of rcutorture testing for
> > TREE_PREEMPT_RCU and provides fixes for a couple resulting bugs.
> 
> Minor bisection nit - should patch 1/3 be renumbered to 3/3, so 
> the two bugfix patches go in before the patch that makes the 
> unpatched bugs visible? Otherwise if a bisect waypoint happens to 
> land on 1/3, oddness can happen...

Makes perfect sense - i've queued them up like that.

Thanks,

	Ingo

[tip:core/urgent] rcu: Need to update rnp->gpnum if preemptable RCU is to be reliable

[tip-bot for Paul E. McKenney]

Commit-ID:  08ce258a8c263a8b87c652a5661e37b0e7238454
Gitweb:     http://git.kernel.org/tip/08ce258a8c263a8b87c652a5661e37b0e7238454
Author:     Paul E. McKenney <paulmck@linux.vnet.ibm.com>
AuthorDate: Tue, 8 Sep 2009 15:54:36 -0700
Committer:  Ingo Molnar <mingo@elte.hu>
CommitDate: Sat, 12 Sep 2009 09:47:06 +0200

rcu: Need to update rnp->gpnum if preemptable RCU is to be reliable

Without this patch, tasks preempted in RCU read-side critical
sections can fail to block the grace period, given that
rnp->gpnum is used to determine which rnp->blocked_tasks[]
element the preempted task is enqueued on.

Before the patch, rnp->gpnum is always zero, so preempted tasks
are always enqueued on rnp->blocked_tasks[0], which is correct
only when the current CPU has not checked into the current
grace period and the grace-period number is even, or,
similarly, if the current CPU -has- checked into the current
grace period and the grace-period number is odd.

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Acked-by: Steven Rostedt <rostedt@goodmis.org>
Cc: laijs@cn.fujitsu.com
Cc: dipankar@in.ibm.com
Cc: akpm@linux-foundation.org
Cc: mathieu.desnoyers@polymtl.ca
Cc: josht@linux.vnet.ibm.com
Cc: dvhltc@us.ibm.com
Cc: niv@us.ibm.com
Cc: peterz@infradead.org
LKML-Reference: <12524504771622-git-send-email->
Signed-off-by: Ingo Molnar <mingo@elte.hu>


---
 kernel/rcutree.c |    6 +++++-
 1 files changed, 5 insertions(+), 1 deletions(-)

diff --git a/kernel/rcutree.c b/kernel/rcutree.c
index 6b11b07..c634a92 100644
--- a/kernel/rcutree.c
+++ b/kernel/rcutree.c
@@ -632,6 +632,7 @@ rcu_start_gp(struct rcu_state *rsp, unsigned long flags)
 	/* Special-case the common single-level case. */
 	if (NUM_RCU_NODES == 1) {
 		rnp->qsmask = rnp->qsmaskinit;
+		rnp->gpnum = rsp->gpnum;
 		rsp->signaled = RCU_SIGNAL_INIT; /* force_quiescent_state OK. */
 		spin_unlock_irqrestore(&rnp->lock, flags);
 		return;
@@ -657,8 +658,10 @@ rcu_start_gp(struct rcu_state *rsp, unsigned long flags)
 	 */
 
 	rnp_end = rsp->level[NUM_RCU_LVLS - 1];
-	for (rnp_cur = &rsp->node[0]; rnp_cur < rnp_end; rnp_cur++)
+	for (rnp_cur = &rsp->node[0]; rnp_cur < rnp_end; rnp_cur++) {
 		rnp_cur->qsmask = rnp_cur->qsmaskinit;
+		rnp->gpnum = rsp->gpnum;
+	}
 
 	/*
 	 * Now set up the leaf nodes.  Here we must be careful.  First,
@@ -679,6 +682,7 @@ rcu_start_gp(struct rcu_state *rsp, unsigned long flags)
 	for (; rnp_cur < rnp_end; rnp_cur++) {
 		spin_lock(&rnp_cur->lock);	/* irqs already disabled. */
 		rnp_cur->qsmask = rnp_cur->qsmaskinit;
+		rnp->gpnum = rsp->gpnum;
 		spin_unlock(&rnp_cur->lock);	/* irqs already disabled. */
 	}
 

[tip:core/urgent] rcu: Initialize multi-level RCU grace periods holding locks

[tip-bot for Paul E. McKenney]

Commit-ID:  ef6d39655ce7472cc30f221586fb81144be8bf8e
Gitweb:     http://git.kernel.org/tip/ef6d39655ce7472cc30f221586fb81144be8bf8e
Author:     Paul E. McKenney <paulmck@linux.vnet.ibm.com>
AuthorDate: Tue, 8 Sep 2009 15:54:37 -0700
Committer:  Ingo Molnar <mingo@elte.hu>
CommitDate: Sat, 12 Sep 2009 09:47:07 +0200

rcu: Initialize multi-level RCU grace periods holding locks

Prior implementations initialized the root and any internal
nodes without holding locks, then initialized the leaves
holding locks.

This is a false economy, as the leaf nodes will usually greatly
outnumber the root and internal nodes.  Acquiring locks on all
nodes is conceptually much simpler as well.

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Acked-by: Steven Rostedt <rostedt@goodmis.org>
Cc: laijs@cn.fujitsu.com
Cc: dipankar@in.ibm.com
Cc: akpm@linux-foundation.org
Cc: mathieu.desnoyers@polymtl.ca
Cc: josht@linux.vnet.ibm.com
Cc: dvhltc@us.ibm.com
Cc: niv@us.ibm.com
Cc: peterz@infradead.org
LKML-Reference: <12524504773190-git-send-email->
Signed-off-by: Ingo Molnar <mingo@elte.hu>


---
 kernel/rcutree.c |   41 ++++++++++++-----------------------------
 1 files changed, 12 insertions(+), 29 deletions(-)

diff --git a/kernel/rcutree.c b/kernel/rcutree.c
index c634a92..da301e2 100644
--- a/kernel/rcutree.c
+++ b/kernel/rcutree.c
@@ -645,41 +645,24 @@ rcu_start_gp(struct rcu_state *rsp, unsigned long flags)
 	spin_lock(&rsp->onofflock);  /* irqs already disabled. */
 
 	/*
-	 * Set the quiescent-state-needed bits in all the non-leaf RCU
-	 * nodes for all currently online CPUs.  This operation relies
-	 * on the layout of the hierarchy within the rsp->node[] array.
-	 * Note that other CPUs will access only the leaves of the
-	 * hierarchy, which still indicate that no grace period is in
-	 * progress.  In addition, we have excluded CPU-hotplug operations.
-	 *
-	 * We therefore do not need to hold any locks.  Any required
-	 * memory barriers will be supplied by the locks guarding the
-	 * leaf rcu_nodes in the hierarchy.
-	 */
-
-	rnp_end = rsp->level[NUM_RCU_LVLS - 1];
-	for (rnp_cur = &rsp->node[0]; rnp_cur < rnp_end; rnp_cur++) {
-		rnp_cur->qsmask = rnp_cur->qsmaskinit;
-		rnp->gpnum = rsp->gpnum;
-	}
-
-	/*
-	 * Now set up the leaf nodes.  Here we must be careful.  First,
-	 * we need to hold the lock in order to exclude other CPUs, which
-	 * might be contending for the leaf nodes' locks.  Second, as
-	 * soon as we initialize a given leaf node, its CPUs might run
-	 * up the rest of the hierarchy.  We must therefore acquire locks
-	 * for each node that we touch during this stage.  (But we still
-	 * are excluding CPU-hotplug operations.)
+	 * Set the quiescent-state-needed bits in all the rcu_node
+	 * structures for all currently online CPUs in breadth-first
+	 * order, starting from the root rcu_node structure.  This
+	 * operation relies on the layout of the hierarchy within the
+	 * rsp->node[] array.  Note that other CPUs will access only
+	 * the leaves of the hierarchy, which still indicate that no
+	 * grace period is in progress, at least until the corresponding
+	 * leaf node has been initialized.  In addition, we have excluded
+	 * CPU-hotplug operations.
 	 *
 	 * Note that the grace period cannot complete until we finish
 	 * the initialization process, as there will be at least one
 	 * qsmask bit set in the root node until that time, namely the
-	 * one corresponding to this CPU.
+	 * one corresponding to this CPU, due to the fact that we have
+	 * irqs disabled.
 	 */
 	rnp_end = &rsp->node[NUM_RCU_NODES];
-	rnp_cur = rsp->level[NUM_RCU_LVLS - 1];
-	for (; rnp_cur < rnp_end; rnp_cur++) {
+	for (rnp_cur = &rsp->node[0]; rnp_cur < rnp_end; rnp_cur++) {
 		spin_lock(&rnp_cur->lock);	/* irqs already disabled. */
 		rnp_cur->qsmask = rnp_cur->qsmaskinit;
 		rnp->gpnum = rsp->gpnum;

[tip:core/urgent] rcutorture: Occasionally delay readers enough to make RCU force_quiescent_state

[tip-bot for Josh Triplett]

Commit-ID:  f4a82a059aea43947d4f37dba9da1782d11caece
Gitweb:     http://git.kernel.org/tip/f4a82a059aea43947d4f37dba9da1782d11caece
Author:     Josh Triplett <josh@joshtriplett.org>
AuthorDate: Tue, 8 Sep 2009 15:54:35 -0700
Committer:  Ingo Molnar <mingo@elte.hu>
CommitDate: Sat, 12 Sep 2009 09:47:07 +0200

rcutorture: Occasionally delay readers enough to make RCU force_quiescent_state

rcutorture already delays readers, but never for long enough to
make RCU force a quiescent state.  Add an occasional delay of
50ms.

Signed-off-by: Josh Triplett <josh@joshtriplett.org>
Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Acked-by: Steven Rostedt <rostedt@goodmis.org>
Cc: laijs@cn.fujitsu.com
Cc: dipankar@in.ibm.com
Cc: akpm@linux-foundation.org
Cc: mathieu.desnoyers@polymtl.ca
Cc: josht@linux.vnet.ibm.com
Cc: dvhltc@us.ibm.com
Cc: niv@us.ibm.com
Cc: peterz@infradead.org
LKML-Reference: <12524504772607-git-send-email->
Signed-off-by: Ingo Molnar <mingo@elte.hu>


---
 kernel/rcutorture.c |   15 +++++++++------
 1 files changed, 9 insertions(+), 6 deletions(-)

diff --git a/kernel/rcutorture.c b/kernel/rcutorture.c
index b33db53..328a825 100644
--- a/kernel/rcutorture.c
+++ b/kernel/rcutorture.c
@@ -281,14 +281,17 @@ static int rcu_torture_read_lock(void) __acquires(RCU)
 
 static void rcu_read_delay(struct rcu_random_state *rrsp)
 {
-	long delay;
-	const long longdelay = 200;
+	const unsigned long shortdelay_us = 200;
+	const unsigned long longdelay_ms = 50;
 
-	/* We want there to be long-running readers, but not all the time. */
+	/* We want a short delay sometimes to make a reader delay the grace
+	 * period, and we want a long delay occasionally to trigger
+	 * force_quiescent_state. */
 
-	delay = rcu_random(rrsp) % (nrealreaders * 2 * longdelay);
-	if (!delay)
-		udelay(longdelay);
+	if (!(rcu_random(rrsp) % (nrealreaders * 2000 * longdelay_ms)))
+		mdelay(longdelay_ms);
+	if (!(rcu_random(rrsp) % (nrealreaders * 2 * shortdelay_us)))
+		udelay(shortdelay_us);
 }
 
 static void rcu_torture_read_unlock(int idx) __releases(RCU)

Re: [PATCH tip/core/rcu 1/3] rcutorture: Occasionally delay readers enough to make RCU force_quiescent_state

[Paul E. McKenney]

On Sat, Sep 12, 2009 at 09:45:40AM +0200, Ingo Molnar wrote:
> 
> * Paul E. McKenney <paulmck@linux.vnet.ibm.com> wrote:
> 
> > From: Josh Triplett <josh@joshtriplett.org>
> > 
> > rcutorture already delays readers, but never for long enough to make RCU
> > force a quiescent state.  Add an occasional delay of 50ms.
> > 
> > Signed-off-by: Josh Triplett <josh@joshtriplett.org>
> 
> Small patch flow nit - your Signed-off-by after Josh's signoff is 
> missing.

/me rechecks the "git am" manpage, sees "-s".

Apologies for my confusion, thank you for fixing it!

							Thanx, Paul

[tip:core/urgent] rcu: Need to update rnp->gpnum if preemptable RCU is to be reliable

[tip-bot for Paul E. McKenney]

Commit-ID:  de078d875cc7fc709f7818f26d38389c04369826
Gitweb:     http://git.kernel.org/tip/de078d875cc7fc709f7818f26d38389c04369826
Author:     Paul E. McKenney <paulmck@linux.vnet.ibm.com>
AuthorDate: Tue, 8 Sep 2009 15:54:36 -0700
Committer:  Ingo Molnar <mingo@elte.hu>
CommitDate: Fri, 18 Sep 2009 00:04:54 +0200

rcu: Need to update rnp->gpnum if preemptable RCU is to be reliable

Without this patch, tasks preempted in RCU read-side critical
sections can fail to block the grace period, given that
rnp->gpnum is used to determine which rnp->blocked_tasks[]
element the preempted task is enqueued on.

Before the patch, rnp->gpnum is always zero, so preempted tasks
are always enqueued on rnp->blocked_tasks[0], which is correct
only when the current CPU has not checked into the current
grace period and the grace-period number is even, or,
similarly, if the current CPU -has- checked into the current
grace period and the grace-period number is odd.

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Acked-by: Steven Rostedt <rostedt@goodmis.org>
Cc: laijs@cn.fujitsu.com
Cc: dipankar@in.ibm.com
Cc: akpm@linux-foundation.org
Cc: mathieu.desnoyers@polymtl.ca
Cc: josht@linux.vnet.ibm.com
Cc: dvhltc@us.ibm.com
Cc: niv@us.ibm.com
Cc: peterz@infradead.org
LKML-Reference: <12524504771622-git-send-email->
Signed-off-by: Ingo Molnar <mingo@elte.hu>


---
 kernel/rcutree.c |    6 +++++-
 1 files changed, 5 insertions(+), 1 deletions(-)

diff --git a/kernel/rcutree.c b/kernel/rcutree.c
index 6b11b07..c634a92 100644
--- a/kernel/rcutree.c
+++ b/kernel/rcutree.c
@@ -632,6 +632,7 @@ rcu_start_gp(struct rcu_state *rsp, unsigned long flags)
 	/* Special-case the common single-level case. */
 	if (NUM_RCU_NODES == 1) {
 		rnp->qsmask = rnp->qsmaskinit;
+		rnp->gpnum = rsp->gpnum;
 		rsp->signaled = RCU_SIGNAL_INIT; /* force_quiescent_state OK. */
 		spin_unlock_irqrestore(&rnp->lock, flags);
 		return;
@@ -657,8 +658,10 @@ rcu_start_gp(struct rcu_state *rsp, unsigned long flags)
 	 */
 
 	rnp_end = rsp->level[NUM_RCU_LVLS - 1];
-	for (rnp_cur = &rsp->node[0]; rnp_cur < rnp_end; rnp_cur++)
+	for (rnp_cur = &rsp->node[0]; rnp_cur < rnp_end; rnp_cur++) {
 		rnp_cur->qsmask = rnp_cur->qsmaskinit;
+		rnp->gpnum = rsp->gpnum;
+	}
 
 	/*
 	 * Now set up the leaf nodes.  Here we must be careful.  First,
@@ -679,6 +682,7 @@ rcu_start_gp(struct rcu_state *rsp, unsigned long flags)
 	for (; rnp_cur < rnp_end; rnp_cur++) {
 		spin_lock(&rnp_cur->lock);	/* irqs already disabled. */
 		rnp_cur->qsmask = rnp_cur->qsmaskinit;
+		rnp->gpnum = rsp->gpnum;
 		spin_unlock(&rnp_cur->lock);	/* irqs already disabled. */
 	}
 

[tip:core/urgent] rcu: Initialize multi-level RCU grace periods holding locks

[tip-bot for Paul E. McKenney]

Commit-ID:  b835db1f9cadaf008750a32664e35a207782c95e
Gitweb:     http://git.kernel.org/tip/b835db1f9cadaf008750a32664e35a207782c95e
Author:     Paul E. McKenney <paulmck@linux.vnet.ibm.com>
AuthorDate: Tue, 8 Sep 2009 15:54:37 -0700
Committer:  Ingo Molnar <mingo@elte.hu>
CommitDate: Fri, 18 Sep 2009 00:05:14 +0200

rcu: Initialize multi-level RCU grace periods holding locks

Prior implementations initialized the root and any internal
nodes without holding locks, then initialized the leaves
holding locks.

This is a false economy, as the leaf nodes will usually greatly
outnumber the root and internal nodes.  Acquiring locks on all
nodes is conceptually much simpler as well.

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Acked-by: Steven Rostedt <rostedt@goodmis.org>
Cc: laijs@cn.fujitsu.com
Cc: dipankar@in.ibm.com
Cc: akpm@linux-foundation.org
Cc: mathieu.desnoyers@polymtl.ca
Cc: josht@linux.vnet.ibm.com
Cc: dvhltc@us.ibm.com
Cc: niv@us.ibm.com
Cc: peterz@infradead.org
LKML-Reference: <12524504773190-git-send-email->
Signed-off-by: Ingo Molnar <mingo@elte.hu>


---
 kernel/rcutree.c |   41 ++++++++++++-----------------------------
 1 files changed, 12 insertions(+), 29 deletions(-)

diff --git a/kernel/rcutree.c b/kernel/rcutree.c
index c634a92..da301e2 100644
--- a/kernel/rcutree.c
+++ b/kernel/rcutree.c
@@ -645,41 +645,24 @@ rcu_start_gp(struct rcu_state *rsp, unsigned long flags)
 	spin_lock(&rsp->onofflock);  /* irqs already disabled. */
 
 	/*
-	 * Set the quiescent-state-needed bits in all the non-leaf RCU
-	 * nodes for all currently online CPUs.  This operation relies
-	 * on the layout of the hierarchy within the rsp->node[] array.
-	 * Note that other CPUs will access only the leaves of the
-	 * hierarchy, which still indicate that no grace period is in
-	 * progress.  In addition, we have excluded CPU-hotplug operations.
-	 *
-	 * We therefore do not need to hold any locks.  Any required
-	 * memory barriers will be supplied by the locks guarding the
-	 * leaf rcu_nodes in the hierarchy.
-	 */
-
-	rnp_end = rsp->level[NUM_RCU_LVLS - 1];
-	for (rnp_cur = &rsp->node[0]; rnp_cur < rnp_end; rnp_cur++) {
-		rnp_cur->qsmask = rnp_cur->qsmaskinit;
-		rnp->gpnum = rsp->gpnum;
-	}
-
-	/*
-	 * Now set up the leaf nodes.  Here we must be careful.  First,
-	 * we need to hold the lock in order to exclude other CPUs, which
-	 * might be contending for the leaf nodes' locks.  Second, as
-	 * soon as we initialize a given leaf node, its CPUs might run
-	 * up the rest of the hierarchy.  We must therefore acquire locks
-	 * for each node that we touch during this stage.  (But we still
-	 * are excluding CPU-hotplug operations.)
+	 * Set the quiescent-state-needed bits in all the rcu_node
+	 * structures for all currently online CPUs in breadth-first
+	 * order, starting from the root rcu_node structure.  This
+	 * operation relies on the layout of the hierarchy within the
+	 * rsp->node[] array.  Note that other CPUs will access only
+	 * the leaves of the hierarchy, which still indicate that no
+	 * grace period is in progress, at least until the corresponding
+	 * leaf node has been initialized.  In addition, we have excluded
+	 * CPU-hotplug operations.
 	 *
 	 * Note that the grace period cannot complete until we finish
 	 * the initialization process, as there will be at least one
 	 * qsmask bit set in the root node until that time, namely the
-	 * one corresponding to this CPU.
+	 * one corresponding to this CPU, due to the fact that we have
+	 * irqs disabled.
 	 */
 	rnp_end = &rsp->node[NUM_RCU_NODES];
-	rnp_cur = rsp->level[NUM_RCU_LVLS - 1];
-	for (; rnp_cur < rnp_end; rnp_cur++) {
+	for (rnp_cur = &rsp->node[0]; rnp_cur < rnp_end; rnp_cur++) {
 		spin_lock(&rnp_cur->lock);	/* irqs already disabled. */
 		rnp_cur->qsmask = rnp_cur->qsmaskinit;
 		rnp->gpnum = rsp->gpnum;

[tip:core/urgent] rcutorture: Occasionally delay readers enough to make RCU force_quiescent_state

[tip-bot for Josh Triplett]

Commit-ID:  b8d57a76d9f92aa63b4f12990da5697b17000b0c
Gitweb:     http://git.kernel.org/tip/b8d57a76d9f92aa63b4f12990da5697b17000b0c
Author:     Josh Triplett <josh@joshtriplett.org>
AuthorDate: Tue, 8 Sep 2009 15:54:35 -0700
Committer:  Ingo Molnar <mingo@elte.hu>
CommitDate: Fri, 18 Sep 2009 00:05:34 +0200

rcutorture: Occasionally delay readers enough to make RCU force_quiescent_state

rcutorture already delays readers, but never for long enough to
make RCU force a quiescent state.  Add an occasional delay of
50ms.

Signed-off-by: Josh Triplett <josh@joshtriplett.org>
Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Acked-by: Steven Rostedt <rostedt@goodmis.org>
Cc: laijs@cn.fujitsu.com
Cc: dipankar@in.ibm.com
Cc: akpm@linux-foundation.org
Cc: mathieu.desnoyers@polymtl.ca
Cc: josht@linux.vnet.ibm.com
Cc: dvhltc@us.ibm.com
Cc: niv@us.ibm.com
Cc: peterz@infradead.org
LKML-Reference: <12524504772607-git-send-email->
Signed-off-by: Ingo Molnar <mingo@elte.hu>


---
 kernel/rcutorture.c |   15 +++++++++------
 1 files changed, 9 insertions(+), 6 deletions(-)

diff --git a/kernel/rcutorture.c b/kernel/rcutorture.c
index b33db53..328a825 100644
--- a/kernel/rcutorture.c
+++ b/kernel/rcutorture.c
@@ -281,14 +281,17 @@ static int rcu_torture_read_lock(void) __acquires(RCU)
 
 static void rcu_read_delay(struct rcu_random_state *rrsp)
 {
-	long delay;
-	const long longdelay = 200;
+	const unsigned long shortdelay_us = 200;
+	const unsigned long longdelay_ms = 50;
 
-	/* We want there to be long-running readers, but not all the time. */
+	/* We want a short delay sometimes to make a reader delay the grace
+	 * period, and we want a long delay occasionally to trigger
+	 * force_quiescent_state. */
 
-	delay = rcu_random(rrsp) % (nrealreaders * 2 * longdelay);
-	if (!delay)
-		udelay(longdelay);
+	if (!(rcu_random(rrsp) % (nrealreaders * 2000 * longdelay_ms)))
+		mdelay(longdelay_ms);
+	if (!(rcu_random(rrsp) % (nrealreaders * 2 * shortdelay_us)))
+		udelay(shortdelay_us);
 }
 
 static void rcu_torture_read_unlock(int idx) __releases(RCU)