[PATCH -tip] Create rcutree plugins to handle hotplug CPU for multi-level trees

[PATCH -tip] Create rcutree plugins to handle hotplug CPU for multi-level trees

[Paul E. McKenney]

When offlining CPUs from a multi-level tree, there is the possibility
of offlining the last CPU from a given node when there are preempted
RCU read-side critical sections that started life on one of the CPUs on
that node.  In this case, the corresponding tasks will be enqueued via
the task_struct's rcu_node_entry list_head onto one of the rcu_node's
blocked_tasks[] lists.  These tasks need to be moved somewhere else
so that they will prevent the current grace period from ending.
That somewhere is the root rcu_node.

With this patch, TREE_PREEMPT_RCU passes moderate rcutorture testing
with aggressive CPU-hotplugging (no delay between inserting/removing
randomly selected CPU).

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
---

 include/linux/init_task.h |    2 -
 include/linux/sched.h     |    4 +-
 kernel/rcutree.c          |    2 +
 kernel/rcutree_plugin.h   |   69 ++++++++++++++++++++++++++++++++++++++++++----
 4 files changed, 69 insertions(+), 8 deletions(-)

diff --git a/include/linux/init_task.h b/include/linux/init_task.h
index 79d4bae..9e7f2e8 100644
--- a/include/linux/init_task.h
+++ b/include/linux/init_task.h
@@ -98,7 +98,7 @@ extern struct group_info init_groups;
 #define INIT_TASK_RCU_PREEMPT(tsk)					\
 	.rcu_read_lock_nesting = 0,					\
 	.rcu_read_unlock_special = 0,					\
-	.rcu_blocked_cpu = -1,						\
+	.rcu_blocked_node = NULL,					\
 	.rcu_node_entry = LIST_HEAD_INIT(tsk.rcu_node_entry),
 #else
 #define INIT_TASK_RCU_PREEMPT(tsk)
diff --git a/include/linux/sched.h b/include/linux/sched.h
index bfca26d..3fe0315 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -1208,7 +1208,7 @@ struct task_struct {
 #ifdef CONFIG_TREE_PREEMPT_RCU
 	int rcu_read_lock_nesting;
 	char rcu_read_unlock_special;
-	int rcu_blocked_cpu;
+	void *rcu_blocked_node;
 	struct list_head rcu_node_entry;
 #endif /* #ifdef CONFIG_TREE_PREEMPT_RCU */
 
@@ -1735,7 +1735,7 @@ static inline void rcu_copy_process(struct task_struct *p)
 {
 	p->rcu_read_lock_nesting = 0;
 	p->rcu_read_unlock_special = 0;
-	p->rcu_blocked_cpu = -1;
+	p->rcu_blocked_node = NULL;
 	INIT_LIST_HEAD(&p->rcu_node_entry);
 }
 
diff --git a/kernel/rcutree.c b/kernel/rcutree.c
index fee6316..d903e2f 100644
--- a/kernel/rcutree.c
+++ b/kernel/rcutree.c
@@ -81,6 +81,7 @@ struct rcu_state rcu_bh_state = RCU_STATE_INITIALIZER(rcu_bh_state);
 DEFINE_PER_CPU(struct rcu_data, rcu_bh_data);
 
 extern long rcu_batches_completed_sched(void);
+static struct rcu_node *rcu_get_root(struct rcu_state *rsp);
 static void cpu_quiet_msk(unsigned long mask, struct rcu_state *rsp,
 			  struct rcu_node *rnp, unsigned long flags);
 static void cpu_quiet_msk_finish(struct rcu_state *rsp, unsigned long flags);
@@ -876,6 +877,7 @@ static void __rcu_offline_cpu(int cpu, struct rcu_state *rsp)
 			spin_unlock(&rnp->lock); /* irqs remain disabled. */
 			break;
 		}
+		rcu_preempt_offline_tasks(rsp, rnp);
 		mask = rnp->grpmask;
 		spin_unlock(&rnp->lock);	/* irqs remain disabled. */
 		rnp = rnp->parent;
diff --git a/kernel/rcutree_plugin.h b/kernel/rcutree_plugin.h
index 201334c..04343be 100644
--- a/kernel/rcutree_plugin.h
+++ b/kernel/rcutree_plugin.h
@@ -92,7 +92,7 @@ static void rcu_preempt_qs(int cpu)
 		rnp = rdp->mynode;
 		spin_lock(&rnp->lock);
 		t->rcu_read_unlock_special |= RCU_READ_UNLOCK_BLOCKED;
-		t->rcu_blocked_cpu = cpu;
+		t->rcu_blocked_node = (void *)rnp;
 
 		/*
 		 * If this CPU has already checked in, then this task
@@ -170,12 +170,21 @@ static void rcu_read_unlock_special(struct task_struct *t)
 	if (special & RCU_READ_UNLOCK_BLOCKED) {
 		t->rcu_read_unlock_special &= ~RCU_READ_UNLOCK_BLOCKED;
 
-		/* Remove this task from the list it blocked on. */
-		rnp = rcu_preempt_state.rda[t->rcu_blocked_cpu]->mynode;
-		spin_lock(&rnp->lock);
+		/*
+		 * Remove this task from the list it blocked on.  The
+		 * task can migrate while we acquire the lock, but at
+		 * most one time.  So at most two passes through loop.
+		 */
+		for (;;) {
+			rnp = (struct rcu_node *)t->rcu_blocked_node;
+			spin_lock(&rnp->lock);
+			if (rnp == (struct rcu_node *)t->rcu_blocked_node)
+				break;
+			spin_unlock(&rnp->lock);
+		}
 		empty = list_empty(&rnp->blocked_tasks[rnp->gpnum & 0x1]);
 		list_del_init(&t->rcu_node_entry);
-		t->rcu_blocked_cpu = -1;
+		t->rcu_blocked_node = NULL;
 
 		/*
 		 * If this was the last task on the current list, and if
@@ -262,6 +271,47 @@ static int rcu_preempted_readers(struct rcu_node *rnp)
 #ifdef CONFIG_HOTPLUG_CPU
 
 /*
+ * Handle tasklist migration for case in which all CPUs covered by the
+ * specified rcu_node have gone offline.  Move them up to the root
+ * rcu_node.  The reason for not just moving them to the immediate
+ * parent is to remove the need for rcu_read_unlock_special() to
+ * make more than two attempts to acquire the target rcu_node's lock.
+ *
+ * The caller must hold rnp->lock with irqs disabled.
+ */
+static void rcu_preempt_offline_tasks(struct rcu_state *rsp,
+				      struct rcu_node *rnp)
+{
+	int i;
+	struct list_head *lp;
+	struct list_head *lp_root;
+	struct rcu_node *rnp_root = rcu_get_root(rsp);
+	struct task_struct *tp;
+
+	if (rnp == rnp_root)
+		return;  /* Shouldn't happen: at least one CPU online. */
+
+	/*
+	 * Move tasks up to root rcu_node.  Rely on the fact that the
+	 * root rcu_node can be at most one ahead of the rest of the
+	 * rcu_nodes in terms of gp_num value.  This fact allows us to
+	 * move the blocked_tasks[] array directly, element by element.
+	 */
+	for (i = 0; i < 2; i++) {
+		lp = &rnp->blocked_tasks[i];
+		lp_root = &rnp_root->blocked_tasks[i];
+		while (!list_empty(lp)) {
+			tp = list_entry(lp->next, typeof(*tp), rcu_node_entry);
+			spin_lock(&rnp_root->lock); /* irqs already disabled */
+			list_del(&tp->rcu_node_entry);
+			tp->rcu_blocked_node = rnp_root;
+			list_add(&tp->rcu_node_entry, lp_root);
+			spin_unlock(&rnp_root->lock); /* irqs remain disabled */
+		}
+	}
+}
+
+/*
  * Do CPU-offline processing for preemptable RCU.
  */
 static void rcu_preempt_offline_cpu(int cpu)
@@ -410,6 +460,15 @@ static int rcu_preempted_readers(struct rcu_node *rnp)
 #ifdef CONFIG_HOTPLUG_CPU
 
 /*
+ * Because preemptable RCU does not exist, it never needs to migrate
+ * tasks that were blocked within RCU read-side critical sections.
+ */
+static void rcu_preempt_offline_tasks(struct rcu_state *rsp,
+				      struct rcu_node *rnp)
+{
+}
+
+/*
  * Because preemptable RCU does not exist, it never needs CPU-offline
  * processing.
  */

Re: [PATCH -tip] Create rcutree plugins to handle hotplug CPU for multi-level trees

[Josh Triplett]

On Tue, 2009-08-25 at 11:22 -0700, Paul E. McKenney wrote:
> When offlining CPUs from a multi-level tree, there is the possibility
> of offlining the last CPU from a given node when there are preempted
> RCU read-side critical sections that started life on one of the CPUs on
> that node.  In this case, the corresponding tasks will be enqueued via
> the task_struct's rcu_node_entry list_head onto one of the rcu_node's
> blocked_tasks[] lists.  These tasks need to be moved somewhere else
> so that they will prevent the current grace period from ending.
> That somewhere is the root rcu_node.
> 
> With this patch, TREE_PREEMPT_RCU passes moderate rcutorture testing
> with aggressive CPU-hotplugging (no delay between inserting/removing
> randomly selected CPU).
> 
> Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>

Looks good.  One comment below.

> --- a/include/linux/sched.h
> +++ b/include/linux/sched.h
> @@ -1208,7 +1208,7 @@ struct task_struct {
>  #ifdef CONFIG_TREE_PREEMPT_RCU
>  	int rcu_read_lock_nesting;
>  	char rcu_read_unlock_special;
> -	int rcu_blocked_cpu;
> +	void *rcu_blocked_node;

This should use struct rcu_node *, not void *.  That would eliminate
several casts in the changes below.  You can forward-declare struct
rcu_node if you want to avoid including RCU headers in sched.h.

> --- a/kernel/rcutree_plugin.h
> +++ b/kernel/rcutree_plugin.h
> @@ -92,7 +92,7 @@ static void rcu_preempt_qs(int cpu)
>  		rnp = rdp->mynode;
>  		spin_lock(&rnp->lock);
>  		t->rcu_read_unlock_special |= RCU_READ_UNLOCK_BLOCKED;
> -		t->rcu_blocked_cpu = cpu;
> +		t->rcu_blocked_node = (void *)rnp;

Regardless of whether you change the type in the structure, you never
need to cast a pointer to type void *; any non-function pointer will
become void * without complaint.

> @@ -170,12 +170,21 @@ static void rcu_read_unlock_special(struct task_struct *t)
>  	if (special & RCU_READ_UNLOCK_BLOCKED) {
>  		t->rcu_read_unlock_special &= ~RCU_READ_UNLOCK_BLOCKED;
> 
> -		/* Remove this task from the list it blocked on. */
> -		rnp = rcu_preempt_state.rda[t->rcu_blocked_cpu]->mynode;
> -		spin_lock(&rnp->lock);
> +		/*
> +		 * Remove this task from the list it blocked on.  The
> +		 * task can migrate while we acquire the lock, but at
> +		 * most one time.  So at most two passes through loop.
> +		 */
> +		for (;;) {
> +			rnp = (struct rcu_node *)t->rcu_blocked_node;
> +			spin_lock(&rnp->lock);
> +			if (rnp == (struct rcu_node *)t->rcu_blocked_node)
> +				break;
> +			spin_unlock(&rnp->lock);
> +		}

Both of the casts of t->rcu_blocked_node can go away here, given the
type change in the structure.

- Josh Triplett

Re: [PATCH -tip] Create rcutree plugins to handle hotplug CPU for multi-level trees

[Mathieu Desnoyers]

* Paul E. McKenney (paulmck@linux.vnet.ibm.com) wrote:
> When offlining CPUs from a multi-level tree, there is the possibility
> of offlining the last CPU from a given node when there are preempted
> RCU read-side critical sections that started life on one of the CPUs on
> that node.  In this case, the corresponding tasks will be enqueued via
> the task_struct's rcu_node_entry list_head onto one of the rcu_node's
> blocked_tasks[] lists.  These tasks need to be moved somewhere else
> so that they will prevent the current grace period from ending.
> That somewhere is the root rcu_node.
> 
> With this patch, TREE_PREEMPT_RCU passes moderate rcutorture testing
> with aggressive CPU-hotplugging (no delay between inserting/removing
> randomly selected CPU).
> 
> Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> ---
[...]
>  /*
> + * Handle tasklist migration for case in which all CPUs covered by the
> + * specified rcu_node have gone offline.  Move them up to the root
> + * rcu_node.  The reason for not just moving them to the immediate
> + * parent is to remove the need for rcu_read_unlock_special() to
> + * make more than two attempts to acquire the target rcu_node's lock.
> + *
> + * The caller must hold rnp->lock with irqs disabled.
> + */
> +static void rcu_preempt_offline_tasks(struct rcu_state *rsp,
> +				      struct rcu_node *rnp)
> +{
> +	int i;
> +	struct list_head *lp;
> +	struct list_head *lp_root;
> +	struct rcu_node *rnp_root = rcu_get_root(rsp);
> +	struct task_struct *tp;
> +
> +	if (rnp == rnp_root)
> +		return;  /* Shouldn't happen: at least one CPU online. */
> +

Hrm, is it "shouldn't happen" or "could be called, but we should not
move anything" ?

If it is really the former, we could put a WARN_ON_ONCE (or, more
aggressively, a BUG_ON) there and see when the caller is going crazy
rather than ignoring the error.

> +	/*
> +	 * Move tasks up to root rcu_node.  Rely on the fact that the
> +	 * root rcu_node can be at most one ahead of the rest of the
> +	 * rcu_nodes in terms of gp_num value.

Do you gather the description of such constraints in a central place
somewhere around the code or design documentation in the kernel tree ?
I just want to point out that every clever assumption like this, which
is based on the constraints imposed by the current design, should be
easy to list in a year from now if we ever decide to move from tree to
hashed RCU (or whichever next step will be necessary then).

I am just worried that migration helpers seems to be added to the design
as an afterthought, and therefore might make future evolution more
difficult.

Thanks,

Mathieu

>  This fact allows us to
> +	 * move the blocked_tasks[] array directly, element by element.
> +	 */
> +	for (i = 0; i < 2; i++) {
> +		lp = &rnp->blocked_tasks[i];
> +		lp_root = &rnp_root->blocked_tasks[i];
> +		while (!list_empty(lp)) {
> +			tp = list_entry(lp->next, typeof(*tp), rcu_node_entry);
> +			spin_lock(&rnp_root->lock); /* irqs already disabled */
> +			list_del(&tp->rcu_node_entry);
> +			tp->rcu_blocked_node = rnp_root;
> +			list_add(&tp->rcu_node_entry, lp_root);
> +			spin_unlock(&rnp_root->lock); /* irqs remain disabled */
> +		}
> +	}
> +}
> +
> +/*
>   * Do CPU-offline processing for preemptable RCU.
>   */
>  static void rcu_preempt_offline_cpu(int cpu)
> @@ -410,6 +460,15 @@ static int rcu_preempted_readers(struct rcu_node *rnp)
>  #ifdef CONFIG_HOTPLUG_CPU
>  
>  /*
> + * Because preemptable RCU does not exist, it never needs to migrate
> + * tasks that were blocked within RCU read-side critical sections.
> + */
> +static void rcu_preempt_offline_tasks(struct rcu_state *rsp,
> +				      struct rcu_node *rnp)
> +{
> +}
> +
> +/*
>   * Because preemptable RCU does not exist, it never needs CPU-offline
>   * processing.
>   */

-- 
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

Re: [PATCH -tip] Create rcutree plugins to handle hotplug CPU for multi-level trees

[Paul E. McKenney]

On Tue, Aug 25, 2009 at 11:38:03AM -0700, Josh Triplett wrote:
> On Tue, 2009-08-25 at 11:22 -0700, Paul E. McKenney wrote:
> > When offlining CPUs from a multi-level tree, there is the possibility
> > of offlining the last CPU from a given node when there are preempted
> > RCU read-side critical sections that started life on one of the CPUs on
> > that node.  In this case, the corresponding tasks will be enqueued via
> > the task_struct's rcu_node_entry list_head onto one of the rcu_node's
> > blocked_tasks[] lists.  These tasks need to be moved somewhere else
> > so that they will prevent the current grace period from ending.
> > That somewhere is the root rcu_node.
> > 
> > With this patch, TREE_PREEMPT_RCU passes moderate rcutorture testing
> > with aggressive CPU-hotplugging (no delay between inserting/removing
> > randomly selected CPU).
> > 
> > Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> 
> Looks good.  One comment below.
> 
> > --- a/include/linux/sched.h
> > +++ b/include/linux/sched.h
> > @@ -1208,7 +1208,7 @@ struct task_struct {
> >  #ifdef CONFIG_TREE_PREEMPT_RCU
> >  	int rcu_read_lock_nesting;
> >  	char rcu_read_unlock_special;
> > -	int rcu_blocked_cpu;
> > +	void *rcu_blocked_node;
> 
> This should use struct rcu_node *, not void *.  That would eliminate
> several casts in the changes below.  You can forward-declare struct
> rcu_node if you want to avoid including RCU headers in sched.h.

Good point -- it would be nice to avoid the casts.

> > --- a/kernel/rcutree_plugin.h
> > +++ b/kernel/rcutree_plugin.h
> > @@ -92,7 +92,7 @@ static void rcu_preempt_qs(int cpu)
> >  		rnp = rdp->mynode;
> >  		spin_lock(&rnp->lock);
> >  		t->rcu_read_unlock_special |= RCU_READ_UNLOCK_BLOCKED;
> > -		t->rcu_blocked_cpu = cpu;
> > +		t->rcu_blocked_node = (void *)rnp;
> 
> Regardless of whether you change the type in the structure, you never
> need to cast a pointer to type void *; any non-function pointer will
> become void * without complaint.
> 
> > @@ -170,12 +170,21 @@ static void rcu_read_unlock_special(struct task_struct *t)
> >  	if (special & RCU_READ_UNLOCK_BLOCKED) {
> >  		t->rcu_read_unlock_special &= ~RCU_READ_UNLOCK_BLOCKED;
> > 
> > -		/* Remove this task from the list it blocked on. */
> > -		rnp = rcu_preempt_state.rda[t->rcu_blocked_cpu]->mynode;
> > -		spin_lock(&rnp->lock);
> > +		/*
> > +		 * Remove this task from the list it blocked on.  The
> > +		 * task can migrate while we acquire the lock, but at
> > +		 * most one time.  So at most two passes through loop.
> > +		 */
> > +		for (;;) {
> > +			rnp = (struct rcu_node *)t->rcu_blocked_node;
> > +			spin_lock(&rnp->lock);
> > +			if (rnp == (struct rcu_node *)t->rcu_blocked_node)
> > +				break;
> > +			spin_unlock(&rnp->lock);
> > +		}
> 
> Both of the casts of t->rcu_blocked_node can go away here, given the
> type change in the structure.

Indeed.  Fixed, will submit early tomorrow.

							Thanx, Paul

Re: [PATCH -tip] Create rcutree plugins to handle hotplug CPU for multi-level trees

[Paul E. McKenney]

On Tue, Aug 25, 2009 at 02:48:00PM -0400, Mathieu Desnoyers wrote:
> * Paul E. McKenney (paulmck@linux.vnet.ibm.com) wrote:
> > When offlining CPUs from a multi-level tree, there is the possibility
> > of offlining the last CPU from a given node when there are preempted
> > RCU read-side critical sections that started life on one of the CPUs on
> > that node.  In this case, the corresponding tasks will be enqueued via
> > the task_struct's rcu_node_entry list_head onto one of the rcu_node's
> > blocked_tasks[] lists.  These tasks need to be moved somewhere else
> > so that they will prevent the current grace period from ending.
> > That somewhere is the root rcu_node.
> > 
> > With this patch, TREE_PREEMPT_RCU passes moderate rcutorture testing
> > with aggressive CPU-hotplugging (no delay between inserting/removing
> > randomly selected CPU).
> > 
> > Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> > ---
> [...]
> >  /*
> > + * Handle tasklist migration for case in which all CPUs covered by the
> > + * specified rcu_node have gone offline.  Move them up to the root
> > + * rcu_node.  The reason for not just moving them to the immediate
> > + * parent is to remove the need for rcu_read_unlock_special() to
> > + * make more than two attempts to acquire the target rcu_node's lock.
> > + *
> > + * The caller must hold rnp->lock with irqs disabled.
> > + */
> > +static void rcu_preempt_offline_tasks(struct rcu_state *rsp,
> > +				      struct rcu_node *rnp)
> > +{
> > +	int i;
> > +	struct list_head *lp;
> > +	struct list_head *lp_root;
> > +	struct rcu_node *rnp_root = rcu_get_root(rsp);
> > +	struct task_struct *tp;
> > +
> > +	if (rnp == rnp_root)
> > +		return;  /* Shouldn't happen: at least one CPU online. */
> > +
> 
> Hrm, is it "shouldn't happen" or "could be called, but we should not
> move anything" ?
> 
> If it is really the former, we could put a WARN_ON_ONCE (or, more
> aggressively, a BUG_ON) there and see when the caller is going crazy
> rather than ignoring the error.

The only way this could happen is if we managed to offline the last CPU.
Which does raise the question as to exactly what would be executing
this code, doesn't it?  ;-)

So, yes, WARN_ON_ONCE() seems reasonable here.  Or perhaps WARN_ONCE().

I added a WARN_ONCE().  Will send patch later.

> > +	/*
> > +	 * Move tasks up to root rcu_node.  Rely on the fact that the
> > +	 * root rcu_node can be at most one ahead of the rest of the
> > +	 * rcu_nodes in terms of gp_num value.
> 
> Do you gather the description of such constraints in a central place
> somewhere around the code or design documentation in the kernel tree ?
> I just want to point out that every clever assumption like this, which
> is based on the constraints imposed by the current design, should be
> easy to list in a year from now if we ever decide to move from tree to
> hashed RCU (or whichever next step will be necessary then).

Interesting point...  The LWN article doesn't get to this level of
detail (http://lwn.net/Articles/305782/), and in any case struct
rcu_node didn't have a gpnum when that article was written.

For the moment, I added a comment to the ->gpnum field's comment.

> I am just worried that migration helpers seems to be added to the design
> as an afterthought, and therefore might make future evolution more
> difficult.

Ah!

No, this limitation is inherent, at least for any rcu_node covering at
least one online CPU.  The root rcu_node's ->gpnum field cannot advance
until all subordinate nodes' ->gpnum fields have caught up, as this
defines a grace period.

As to the case of the rcu_node that has no online CPUs, such nodes had
better not be able to have additional CPUs go offline, as the code is in
no shape to tolerate negative numbers of online CPUs per node.  Nor do
I plan to add support for this situation.  ;-)

							Thanx, Paul