Create rcutree plugins to handle hotplug CPU for multi-level trees

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 <[email protected]>

kernel/rcutree_plugin.h +2 -3

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

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 <[email protected]>

---

/*
+ * 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.
+ */

kernel/rcutree_plugin.h +2 -0

+static void rcu_preempt_offline_tasks(struct rcu_state *rsp,
+				      struct rcu_node *rnp)

This fact allows us to

kernel/rcutree_plugin.h +26 -0

+	 * 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.
  */

Quoted 9 lines · 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.

Quoted 5 lines

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 <[email protected]>

Looks good. One comment below.

include/linux/sched.h struct task_struct { · line 1211

Quoted 8 lines

include/linux/sched.h +1 -1

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

kernel/rcutree_plugin.h static void rcu_preempt_qs(int cpu) · line 95

Quoted 8 lines

kernel/rcutree_plugin.h +1 -1

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

Quoted 14 lines

kernel/rcutree_plugin.h +7 -3

@@ -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;

kernel/rcutree_plugin.h static void rcu_read_unlock_special(struct task_struct *t) · line 184

Quoted 5 lines

kernel/rcutree_plugin.h +5 -0

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

Quoted 15 lines · * Paul E. McKenney ([email protected]) 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 <[email protected]>

---

[...]

Quoted 11 lines

/*
+ * 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.
+ */

kernel/rcutree_plugin.h +2 -0

+static void rcu_preempt_offline_tasks(struct rcu_state *rsp,
+				      struct rcu_node *rnp)

kernel/rcutree_plugin.h static int rcu_preempted_readers(struct rcu_node *rnp) · line 293

Quoted 10 lines

kernel/rcutree_plugin.h +10 -0

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

kernel/rcutree_plugin.h static int rcu_preempted_readers(struct rcu_node *rnp)

Quoted 4 lines

kernel/rcutree_plugin.h +4 -0

+	/*
+	 * 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.