Skip to contentSkip to conversation

Parallelize expedited grace periods for v4.18

PATCH New Paul E. McKenney 1 participant 4 messages Apr 23, 2018 RCU

lore
Share & tools
lore

Paul E. McKenney

author
#0 lore raw

cover Parallelize expedited grace periods for v4.18

Hello!

This series parallelizes grace-period initialization for expedited grace periods and adds a couple of fixes:

1. Parallelize expedited grace-period initialization in order to
reduce the growth of latency with increasing numbers of CPUs.

2. Updates comments on which locks are to be held to match the
code, courtesy of Boqun Feng.

3. Protect all calls to sync_rcu_preempt_exp_done() with the

	corresponding rcu_node structure's ->lock held, courtesy of
	Boqun Feng.

							Thanx, Paul

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

 rcu.h      |    1 
 tree.c     |    3 
 tree.h     |   10 ++
 tree_exp.h |  222 ++++++++++++++++++++++++++++++++++++-------------------------
 4 files changed, 148 insertions(+), 88 deletions(-)
author
#1 lore raw

PATCH 1/3 rcu: Parallelize expedited grace-period initialization

The latency of RCU expedited grace periods grows with increasing numbers of CPUs, eventually failing to be all that expedited. Much of the growth in latency is in the initialization phase, so this commit uses workqueues to carry out this initialization concurrently on a rcu_node-by-rcu_node basis.

This change makes use of a new rcu_par_gp_wq because flushing a work item from another work item running from the same workqueue can result in deadlock.

Signed-off-by Paul E. McKenney <[email protected]>
---
 kernel/rcu/rcu.h      |   1 +
 kernel/rcu/tree.c     |   3 +
 kernel/rcu/tree.h     |  10 +++
 kernel/rcu/tree_exp.h | 184 +++++++++++++++++++++++++++++---------------------
 4 files changed, 120 insertions(+), 78 deletions(-)
kernel/rcu/rcu.h +1 -0
index 7a693e31184a..976019d6fa06 100644
@@ -486,6 +486,7 @@ void rcu_force_quiescent_state(void);
 void rcu_bh_force_quiescent_state(void);
 void rcu_sched_force_quiescent_state(void);
 extern struct workqueue_struct *rcu_gp_wq;
+extern struct workqueue_struct *rcu_par_gp_wq;
 #endif /* #else #ifdef CONFIG_TINY_RCU */
 
 #ifdef CONFIG_RCU_NOCB_CPU
kernel/rcu/tree.c +3 -0
index 2a734692a581..23781fc90830 100644
@@ -4168,6 +4168,7 @@ static void __init rcu_dump_rcu_node_tree(struct rcu_state *rsp)
 }
 
 struct workqueue_struct *rcu_gp_wq;
+struct workqueue_struct *rcu_par_gp_wq;
 
 void __init rcu_init(void)
 {

@@ -4199,6 +4200,8 @@ void __init rcu_init(void)
 	/* Create workqueue for expedited GPs and for Tree SRCU. */
 	rcu_gp_wq = alloc_workqueue("rcu_gp", WQ_MEM_RECLAIM, 0);
 	WARN_ON(!rcu_gp_wq);
+	rcu_par_gp_wq = alloc_workqueue("rcu_par_gp", WQ_MEM_RECLAIM, 0);
+	WARN_ON(!rcu_par_gp_wq);
 }
 
 #include "tree_exp.h"
kernel/rcu/tree.h +10 -0
index f491ab4f2e8e..98d33902b65c 100644
@@ -58,6 +58,14 @@ struct rcu_dynticks {
 #endif /* #ifdef CONFIG_RCU_FAST_NO_HZ */
 };
 
+/* Communicate arguments to a workqueue handler. */
+struct rcu_exp_work {
+	smp_call_func_t rew_func;
+	struct rcu_state *rew_rsp;
+	unsigned long rew_s;
+	struct work_struct rew_work;
+};
+
 /* RCU's kthread states for tracing. */
 #define RCU_KTHREAD_STOPPED  0
 #define RCU_KTHREAD_RUNNING  1

@@ -157,6 +165,8 @@ struct rcu_node {
 	spinlock_t exp_lock ____cacheline_internodealigned_in_smp;
 	unsigned long exp_seq_rq;
 	wait_queue_head_t exp_wq[4];
+	struct rcu_exp_work rew;
+	bool exp_need_flush;	/* Need to flush workitem? */
 } ____cacheline_internodealigned_in_smp;
 
 /*
kernel/rcu/tree_exp.h +106 -78

213 lines not on this page · raw message

Signature · 1 line
2.5.2
author
#2 lore raw

PATCH 2/3 rcu: exp: Fix "must hold exp_mutex" comments for QS reporting functions

In reply to Paul E. McKenney

From: Boqun Feng <[email protected]>

Since commit d9a3da0699b2 ("rcu: Add expedited grace-period support for preemptible RCU"), there are comments for some funtions in rcu_report_exp_rnp()'s call-chain saying that exp_mutex or its predecessors needs to be held.

However, exp_mutex and its predecessors were used only to synchronize between GPs, and it is clear that all variables visited by those functions are under the protection of rcu_node's ->lock. Moreover, those functions are currently called without held exp_mutex, and seems that doesn't introduce any trouble.

So this patch fixes this problem by updating the comments to match the current code.

Signed-off-by Boqun Feng <[email protected]>
Fixes d9a3da0699b2 ("rcu: Add expedited grace-period support for preemptible RCU")
Signed-off-by Paul E. McKenney <[email protected]>
---
 kernel/rcu/tree_exp.h | 10 +++-------
 1 file changed, 3 insertions(+), 7 deletions(-)
kernel/rcu/tree_exp.h +3 -7
index 73e1d3dca5b1..d7622cb85aa7 100644
@@ -154,7 +154,7 @@ static void __maybe_unused sync_exp_reset_tree(struct rcu_state *rsp)
  * for the current expedited grace period.  Works only for preemptible
  * RCU -- other RCU implementation use other means.
  *
- * Caller must hold the rcu_state's exp_mutex.
+ * Caller must hold the specificed rcu_node structure's ->lock
  */
 static bool sync_rcu_preempt_exp_done(struct rcu_node *rnp)
 {

@@ -170,8 +170,7 @@ static bool sync_rcu_preempt_exp_done(struct rcu_node *rnp)
  * recursively up the tree.  (Calm down, calm down, we do the recursion
  * iteratively!)
  *
- * Caller must hold the rcu_state's exp_mutex and the specified rcu_node
- * structure's ->lock.
+ * Caller must hold the specified rcu_node structure's ->lock.
  */
 static void __rcu_report_exp_rnp(struct rcu_state *rsp, struct rcu_node *rnp,
 				 bool wake, unsigned long flags)

@@ -207,8 +206,6 @@ static void __rcu_report_exp_rnp(struct rcu_state *rsp, struct rcu_node *rnp,
 /*
  * Report expedited quiescent state for specified node.  This is a
  * lock-acquisition wrapper function for __rcu_report_exp_rnp().
- *
- * Caller must hold the rcu_state's exp_mutex.
  */
 static void __maybe_unused rcu_report_exp_rnp(struct rcu_state *rsp,
 					      struct rcu_node *rnp, bool wake)

@@ -221,8 +218,7 @@ static void __maybe_unused rcu_report_exp_rnp(struct rcu_state *rsp,
 
 /*
  * Report expedited quiescent state for multiple CPUs, all covered by the
- * specified leaf rcu_node structure.  Caller must hold the rcu_state's
- * exp_mutex.
+ * specified leaf rcu_node structure.
  */
 static void rcu_report_exp_cpu_mult(struct rcu_state *rsp, struct rcu_node *rnp,
 				    unsigned long mask, bool wake)
Signature · 1 line
2.5.2
author
#3 lore raw

PATCH 3/3 rcu: exp: Protect all sync_rcu_preempt_exp_done() with rcu_node lock

In reply to Paul E. McKenney

From: Boqun Feng <[email protected]>

Currently some callsites of sync_rcu_preempt_exp_done() are not called with the corresponding rcu_node's ->lock held, which could introduces bugs as per Paul:

o CPU 0 in sync_rcu_preempt_exp_done() reads ->exp_tasks and
sees that it is NULL.

o CPU 1 blocks within an RCU read-side critical section, so

	it enqueues the task and points ->exp_tasks at it and
	clears CPU 1's bit in ->expmask.

o All other CPUs clear their bits in ->expmask.

o CPU 0 reads ->expmask, sees that it is zero, so incorrectly

	concludes that all quiescent states have completed, despite
	the fact that ->exp_tasks is non-NULL.

To fix this, sync_rcu_preempt_exp_unlocked() is introduced to replace lockless callsites of sync_rcu_preempt_exp_done().

Further, a lockdep annotation is added into sync_rcu_preempt_exp_done() to prevent mis-use in the future.

Signed-off-by Boqun Feng <[email protected]>
Signed-off-by Paul E. McKenney <[email protected]>
---
 kernel/rcu/tree_exp.h | 28 +++++++++++++++++++++++++---
 1 file changed, 25 insertions(+), 3 deletions(-)
kernel/rcu/tree_exp.h +25 -3
index d7622cb85aa7..755d0f461f26 100644
@@ -20,6 +20,8 @@
  * Authors: Paul E. McKenney <[email protected]>
  */
 
+#include <linux/lockdep.h>
+
 /*
  * Record the start of an expedited grace period.
  */

@@ -158,11 +160,31 @@ static void __maybe_unused sync_exp_reset_tree(struct rcu_state *rsp)
  */
 static bool sync_rcu_preempt_exp_done(struct rcu_node *rnp)
 {
+	raw_lockdep_assert_held_rcu_node(rnp);
+
 	return rnp->exp_tasks == NULL &&
 	       READ_ONCE(rnp->expmask) == 0;
 }
 
 /*
+ * Like sync_rcu_preempt_exp_done(), but this function assumes the caller
+ * doesn't hold the rcu_node's ->lock, and will acquire and release the lock
+ * itself
+ */
+static bool sync_rcu_preempt_exp_done_unlocked(struct rcu_node *rnp)
+{
+	unsigned long flags;
+	bool ret;
+
+	raw_spin_lock_irqsave_rcu_node(rnp, flags);
+	ret = sync_rcu_preempt_exp_done(rnp);
+	raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
+
+	return ret;
+}
+
+
+/*
  * Report the exit from RCU read-side critical section for the last task
  * that queued itself during or before the current expedited preemptible-RCU
  * grace period.  This event is reported either to the rcu_node structure on

@@ -501,9 +523,9 @@ static void synchronize_sched_expedited_wait(struct rcu_state *rsp)
 	for (;;) {
 		ret = swait_event_timeout(
 				rsp->expedited_wq,
-				sync_rcu_preempt_exp_done(rnp_root),
+				sync_rcu_preempt_exp_done_unlocked(rnp_root),
 				jiffies_stall);
-		if (ret > 0 || sync_rcu_preempt_exp_done(rnp_root))
+		if (ret > 0 || sync_rcu_preempt_exp_done_unlocked(rnp_root))
 			return;
 		WARN_ON(ret < 0);  /* workqueues should not be signaled. */
 		if (rcu_cpu_stall_suppress)

@@ -536,7 +558,7 @@ static void synchronize_sched_expedited_wait(struct rcu_state *rsp)
 			rcu_for_each_node_breadth_first(rsp, rnp) {
 				if (rnp == rnp_root)
 					continue; /* printed unconditionally */
-				if (sync_rcu_preempt_exp_done(rnp))
+				if (sync_rcu_preempt_exp_done_unlocked(rnp))
 					continue;
 				pr_cont(" l=%u:%d-%d:%#lx/%c",
 					rnp->level, rnp->grplo, rnp->grphi,
Signature · 1 line
2.5.2