Skip to contentSkip to conversation

increase rcutorture intensity and fix a couple resulting bugs

PATCH In review Paul E. McKenney 5 participants 16 messages Sep 8, 2009 – Sep 17, 2009

lore
Share & tools
lore
#0 lore raw

cover increase rcutorture intensity and fix a couple resulting bugs

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(-)
#6 lore raw

PATCH 2/3 Need to update rnp->gpnum if preemptable RCU is to be reliable.

From: Paul E. McKenney <[email protected]>

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.

---
 kernel/rcutree.c |    6 +++++-
 1 files changed, 5 insertions(+), 1 deletions(-)
kernel/rcutree.c +5 -1
index 71bc797..03866bd 100644
@@ -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. */
 	}
 
Signature · 1 line
1.5.2.5
#1 lore raw

PATCH 1/3 rcutorture: Occasionally delay readers enough to make RCU force_quiescent_state

In reply to Paul E. McKenney

From: Josh Triplett <[email protected]>

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

---
 kernel/rcutorture.c |   15 +++++++++------
 1 files changed, 9 insertions(+), 6 deletions(-)
kernel/rcutorture.c +9 -6
index b33db53..328a825 100644
@@ -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)
Signature · 1 line
1.5.2.5
#9 lore raw

PATCH 3/3 Initialize multi-level RCU grace periods holding locks

In reply to Paul E. McKenney

From: Paul E. McKenney <[email protected]>

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.

---
 kernel/rcutree.c |   41 ++++++++++++-----------------------------
 1 files changed, 12 insertions(+), 29 deletions(-)
kernel/rcutree.c +12 -29
index 03866bd..bca0aba 100644
@@ -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;
Signature · 1 line
1.5.2.5
Acked-by on the v1 series
#12 lore raw
In reply to Paul E. McKenney
Quoted 13 lines · 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.

Quoted 8 lines

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:

-- Steve

#13 lore raw
In reply to Paul E. McKenney
Quoted 2 lines · Paul E. McKenney

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

#14 lore raw
Quoted 7 lines · On Wed, Sep 09, 2009 at 01:43:59PM -0400, [email protected] wrote:
Quoted 2 lines · Paul E. McKenney

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

#2 lore raw

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

In reply to Paul E. McKenney
Quoted 6 lines · Paul E. McKenney

From: Josh Triplett <[email protected]>

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

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

Ingo

#15 lore raw
In reply to [email protected]
Quoted 8 lines · * [email protected] <[email protected]> wrote:
Quoted 2 lines · Paul E. McKenney

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

#7 lore raw

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

In reply to Paul E. McKenney
Commit-ID:  08ce258a8c263a8b87c652a5661e37b0e7238454
Gitweb:     http://git.kernel.org/tip/08ce258a8c263a8b87c652a5661e37b0e7238454
Author:     Paul E. McKenney <[email protected]>
AuthorDate: Tue, 8 Sep 2009 15:54:36 -0700
Committer:  Ingo Molnar <[email protected]>
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.

LKML-Reference: <12524504771622-git-send-email->

---
 kernel/rcutree.c |    6 +++++-
 1 files changed, 5 insertions(+), 1 deletions(-)
kernel/rcutree.c +5 -1
index 6b11b07..c634a92 100644
@@ -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. */
 	}
 
#10 lore raw

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

In reply to Paul E. McKenney
Commit-ID:  ef6d39655ce7472cc30f221586fb81144be8bf8e
Gitweb:     http://git.kernel.org/tip/ef6d39655ce7472cc30f221586fb81144be8bf8e
Author:     Paul E. McKenney <[email protected]>
AuthorDate: Tue, 8 Sep 2009 15:54:37 -0700
Committer:  Ingo Molnar <[email protected]>
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.

LKML-Reference: <12524504773190-git-send-email->

---
 kernel/rcutree.c |   41 ++++++++++++-----------------------------
 1 files changed, 12 insertions(+), 29 deletions(-)
kernel/rcutree.c +12 -29
index c634a92..da301e2 100644
@@ -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;
#4 lore raw

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

In reply to Paul E. McKenney
Commit-ID:  f4a82a059aea43947d4f37dba9da1782d11caece
Gitweb:     http://git.kernel.org/tip/f4a82a059aea43947d4f37dba9da1782d11caece
Author:     Josh Triplett <[email protected]>
AuthorDate: Tue, 8 Sep 2009 15:54:35 -0700
Committer:  Ingo Molnar <[email protected]>
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.

LKML-Reference: <12524504772607-git-send-email->

---
 kernel/rcutorture.c |   15 +++++++++------
 1 files changed, 9 insertions(+), 6 deletions(-)
kernel/rcutorture.c +9 -6
index b33db53..328a825 100644
@@ -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)
#3 lore raw

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

In reply to Ingo Molnar
Quoted 5 lines · Ingo Molnar
Quoted 2 lines · Paul E. McKenney

From: Josh Triplett <[email protected]>

Quoted 7 lines
Quoted 4 lines

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

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

#8 lore raw

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

In reply to Paul E. McKenney
Commit-ID:  de078d875cc7fc709f7818f26d38389c04369826
Gitweb:     http://git.kernel.org/tip/de078d875cc7fc709f7818f26d38389c04369826
Author:     Paul E. McKenney <[email protected]>
AuthorDate: Tue, 8 Sep 2009 15:54:36 -0700
Committer:  Ingo Molnar <[email protected]>
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.

LKML-Reference: <12524504771622-git-send-email->

---
 kernel/rcutree.c |    6 +++++-
 1 files changed, 5 insertions(+), 1 deletions(-)
kernel/rcutree.c +5 -1
index 6b11b07..c634a92 100644
@@ -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. */
 	}
 
#11 lore raw

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

In reply to Paul E. McKenney
Commit-ID:  b835db1f9cadaf008750a32664e35a207782c95e
Gitweb:     http://git.kernel.org/tip/b835db1f9cadaf008750a32664e35a207782c95e
Author:     Paul E. McKenney <[email protected]>
AuthorDate: Tue, 8 Sep 2009 15:54:37 -0700
Committer:  Ingo Molnar <[email protected]>
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.

LKML-Reference: <12524504773190-git-send-email->

---
 kernel/rcutree.c |   41 ++++++++++++-----------------------------
 1 files changed, 12 insertions(+), 29 deletions(-)
kernel/rcutree.c +12 -29
index c634a92..da301e2 100644
@@ -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;
#5 lore raw

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

In reply to Paul E. McKenney
Commit-ID:  b8d57a76d9f92aa63b4f12990da5697b17000b0c
Gitweb:     http://git.kernel.org/tip/b8d57a76d9f92aa63b4f12990da5697b17000b0c
Author:     Josh Triplett <[email protected]>
AuthorDate: Tue, 8 Sep 2009 15:54:35 -0700
Committer:  Ingo Molnar <[email protected]>
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.

LKML-Reference: <12524504772607-git-send-email->

---
 kernel/rcutorture.c |   15 +++++++++------
 1 files changed, 9 insertions(+), 6 deletions(-)
kernel/rcutorture.c +9 -6
index b33db53..328a825 100644
@@ -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)