RCU-tasks implementation

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

It turns out to be easier to add the synchronous grace-period waiting functions to RCU-tasks than to work around their absense in rcutorture, so this commit adds them. The key point is that the existence of call_rcu_tasks() means that rcutorture needs an rcu_barrier_tasks().

Signed-off-by Paul E. McKenney <[email protected]>

 include/linux/rcupdate.h |  2 ++
 kernel/rcu/update.c      | 55 ++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 57 insertions(+)

include/linux/rcupdate.h +2 -0

index 3299ff98ad03..17c7e25c38be 100644
@@ -216,6 +216,8 @@ void synchronize_sched(void);
  * memory ordering guarantees.
  */
 void call_rcu_tasks(struct rcu_head *head, void (*func)(struct rcu_head *head));
+void synchronize_rcu_tasks(void);
+void rcu_barrier_tasks(void);
 
 #ifdef CONFIG_PREEMPT_RCU
 

kernel/rcu/update.c +55 -0

index b92268647a01..c8d304dc6d8a 100644
@@ -387,6 +387,61 @@ void call_rcu_tasks(struct rcu_head *rhp, void (*func)(struct rcu_head *rhp))
 }
 EXPORT_SYMBOL_GPL(call_rcu_tasks);
 
+/**
+ * synchronize_rcu_tasks - wait until an rcu-tasks grace period has elapsed.
+ *
+ * Control will return to the caller some time after a full rcu-tasks
+ * grace period has elapsed, in other words after all currently
+ * executing rcu-tasks read-side critical sections have elapsed.  These
+ * read-side critical sections are delimited by calls to schedule(),
+ * cond_resched_rcu_qs(), idle execution, userspace execution, calls
+ * to synchronize_rcu_tasks(), and (in theory, anyway) cond_resched().
+ *
+ * This is a very specialized primitive, intended only for a few uses in
+ * tracing and other situations requiring manipulation of function
+ * preambles and profiling hooks.  The synchronize_rcu_tasks() function
+ * is not (yet) intended for heavy use from multiple CPUs.
+ *
+ * Note that this guarantee implies further memory-ordering guarantees.
+ * On systems with more than one CPU, when synchronize_rcu_tasks() returns,
+ * each CPU is guaranteed to have executed a full memory barrier since the
+ * end of its last RCU-tasks read-side critical section whose beginning
+ * preceded the call to synchronize_rcu_tasks().  In addition, each CPU
+ * having an RCU-tasks read-side critical section that extends beyond
+ * the return from synchronize_rcu_tasks() is guaranteed to have executed
+ * a full memory barrier after the beginning of synchronize_rcu_tasks()
+ * and before the beginning of that RCU-tasks read-side critical section.
+ * Note that these guarantees include CPUs that are offline, idle, or
+ * executing in user mode, as well as CPUs that are executing in the kernel.
+ *
+ * Furthermore, if CPU A invoked synchronize_rcu_tasks(), which returned
+ * to its caller on CPU B, then both CPU A and CPU B are guaranteed
+ * to have executed a full memory barrier during the execution of
+ * synchronize_rcu_tasks() -- even if CPU A and CPU B are the same CPU
+ * (but again only if the system has more than one CPU).
+ */
+void synchronize_rcu_tasks(void)
+{
+	/* Complain if the scheduler has not started.  */
+	rcu_lockdep_assert(!rcu_scheduler_active,
+			   "synchronize_rcu_tasks called too soon");
+
+	/* Wait for the grace period. */
+	wait_rcu_gp(call_rcu_tasks);
+}
+
+/**
+ * rcu_barrier_tasks - Wait for in-flight call_rcu_tasks() callbacks.
+ *
+ * Although the current implementation is guaranteed to wait, it is not
+ * obligated to, for example, if there are no pending callbacks.
+ */
+void rcu_barrier_tasks(void)
+{
+	/* There is only one callback queue, so this is easy.  ;-) */
+	synchronize_rcu_tasks();
+}
+
 /* RCU-tasks kthread that detects grace periods and invokes callbacks. */
 static int __noreturn rcu_tasks_kthread(void *arg)
 {

Signature · 1 line

1.8.1.5

Quoted 7 lines · Paul E. McKenney

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

It turns out to be easier to add the synchronous grace-period waiting functions to RCU-tasks than to work around their absense in rcutorture, so this commit adds them. The key point is that the existence of call_rcu_tasks() means that rcutorture needs an rcu_barrier_tasks().

Quoted 1 line

Signed-off-by Paul E. McKenney <[email protected]>

With rcu_barrier_tasks being a trivial wrapper, why not just let rcutorture call synchronize_rcu_tasks directly?

Quoted 86 lines

 include/linux/rcupdate.h |  2 ++
 kernel/rcu/update.c      | 55 ++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 57 insertions(+)

include/linux/rcupdate.h +2 -0

index 3299ff98ad03..17c7e25c38be 100644
@@ -216,6 +216,8 @@ void synchronize_sched(void);
  * memory ordering guarantees.
  */
 void call_rcu_tasks(struct rcu_head *head, void (*func)(struct rcu_head *head));
+void synchronize_rcu_tasks(void);
+void rcu_barrier_tasks(void);
 
 #ifdef CONFIG_PREEMPT_RCU
 

kernel/rcu/update.c +55 -0

index b92268647a01..c8d304dc6d8a 100644
@@ -387,6 +387,61 @@ void call_rcu_tasks(struct rcu_head *rhp, void (*func)(struct rcu_head *rhp))
 }
 EXPORT_SYMBOL_GPL(call_rcu_tasks);
 
+/**
+ * synchronize_rcu_tasks - wait until an rcu-tasks grace period has elapsed.
+ *
+ * Control will return to the caller some time after a full rcu-tasks
+ * grace period has elapsed, in other words after all currently
+ * executing rcu-tasks read-side critical sections have elapsed.  These
+ * read-side critical sections are delimited by calls to schedule(),
+ * cond_resched_rcu_qs(), idle execution, userspace execution, calls
+ * to synchronize_rcu_tasks(), and (in theory, anyway) cond_resched().
+ *
+ * This is a very specialized primitive, intended only for a few uses in
+ * tracing and other situations requiring manipulation of function
+ * preambles and profiling hooks.  The synchronize_rcu_tasks() function
+ * is not (yet) intended for heavy use from multiple CPUs.
+ *
+ * Note that this guarantee implies further memory-ordering guarantees.
+ * On systems with more than one CPU, when synchronize_rcu_tasks() returns,
+ * each CPU is guaranteed to have executed a full memory barrier since the
+ * end of its last RCU-tasks read-side critical section whose beginning
+ * preceded the call to synchronize_rcu_tasks().  In addition, each CPU
+ * having an RCU-tasks read-side critical section that extends beyond
+ * the return from synchronize_rcu_tasks() is guaranteed to have executed
+ * a full memory barrier after the beginning of synchronize_rcu_tasks()
+ * and before the beginning of that RCU-tasks read-side critical section.
+ * Note that these guarantees include CPUs that are offline, idle, or
+ * executing in user mode, as well as CPUs that are executing in the kernel.
+ *
+ * Furthermore, if CPU A invoked synchronize_rcu_tasks(), which returned
+ * to its caller on CPU B, then both CPU A and CPU B are guaranteed
+ * to have executed a full memory barrier during the execution of
+ * synchronize_rcu_tasks() -- even if CPU A and CPU B are the same CPU
+ * (but again only if the system has more than one CPU).
+ */
+void synchronize_rcu_tasks(void)
+{
+	/* Complain if the scheduler has not started.  */
+	rcu_lockdep_assert(!rcu_scheduler_active,
+			   "synchronize_rcu_tasks called too soon");
+
+	/* Wait for the grace period. */
+	wait_rcu_gp(call_rcu_tasks);
+}
+
+/**
+ * rcu_barrier_tasks - Wait for in-flight call_rcu_tasks() callbacks.
+ *
+ * Although the current implementation is guaranteed to wait, it is not
+ * obligated to, for example, if there are no pending callbacks.
+ */
+void rcu_barrier_tasks(void)
+{
+	/* There is only one callback queue, so this is easy.  ;-) */
+	synchronize_rcu_tasks();
+}
+
 /* RCU-tasks kthread that detects grace periods and invokes callbacks. */
 static int __noreturn rcu_tasks_kthread(void *arg)
 {

Signature · 1 line

1.8.1.5

From: Steven Rostedt <[email protected]>

This commit exports the RCU-tasks APIs, call_rcu_tasks(), synchronize_rcu_tasks(), and rcu_barrier_tasks(), to GPL-licensed kernel modules.

Signed-off-by Steven Rostedt <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

 kernel/rcu/update.c | 2 ++
 1 file changed, 2 insertions(+)

kernel/rcu/update.c +2 -0

index c8d304dc6d8a..1bfc07ed854e 100644
@@ -429,6 +429,7 @@ void synchronize_rcu_tasks(void)
 	/* Wait for the grace period. */
 	wait_rcu_gp(call_rcu_tasks);
 }
+EXPORT_SYMBOL_GPL(synchronize_rcu_tasks);
 
 /**
  * rcu_barrier_tasks - Wait for in-flight call_rcu_tasks() callbacks.

@@ -441,6 +442,7 @@ void rcu_barrier_tasks(void)
 	/* There is only one callback queue, so this is easy.  ;-) */
 	synchronize_rcu_tasks();
 }
+EXPORT_SYMBOL_GPL(rcu_barrier_tasks);
 
 /* RCU-tasks kthread that detects grace periods and invokes callbacks. */
 static int __noreturn rcu_tasks_kthread(void *arg)

Signature · 1 line

1.8.1.5

Quoted 6 lines · Paul E. McKenney

From: Steven Rostedt <[email protected]>

This commit exports the RCU-tasks APIs, call_rcu_tasks(), synchronize_rcu_tasks(), and rcu_barrier_tasks(), to GPL-licensed kernel modules.

Quoted 2 lines

Signed-off-by Steven Rostedt <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

Reviewed-by Josh Triplett <[email protected]>

Should this remain a separate patch, or go into the patch that creates these APIs?

Quoted 26 lines

 kernel/rcu/update.c | 2 ++
 1 file changed, 2 insertions(+)

kernel/rcu/update.c +2 -0

index c8d304dc6d8a..1bfc07ed854e 100644
@@ -429,6 +429,7 @@ void synchronize_rcu_tasks(void)
 	/* Wait for the grace period. */
 	wait_rcu_gp(call_rcu_tasks);
 }
+EXPORT_SYMBOL_GPL(synchronize_rcu_tasks);
 
 /**
  * rcu_barrier_tasks - Wait for in-flight call_rcu_tasks() callbacks.

@@ -441,6 +442,7 @@ void rcu_barrier_tasks(void)
 	/* There is only one callback queue, so this is easy.  ;-) */
 	synchronize_rcu_tasks();
 }
+EXPORT_SYMBOL_GPL(rcu_barrier_tasks);
 
 /* RCU-tasks kthread that detects grace periods and invokes callbacks. */
 static int __noreturn rcu_tasks_kthread(void *arg)

Signature · 1 line

1.8.1.5

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

This commit adds torture tests for RCU-tasks. It also fixes a bug that would segfault for an RCU flavor lacking a callback-barrier function.

Signed-off-by Paul E. McKenney <[email protected]>

 include/linux/rcupdate.h |  1 +
 kernel/rcu/rcutorture.c  | 40 +++++++++++++++++++++++++++++++++++++++-
 2 files changed, 40 insertions(+), 1 deletion(-)

include/linux/rcupdate.h +1 -0

index 17c7e25c38be..ecb2198849e0 100644
@@ -55,6 +55,7 @@ enum rcutorture_type {
 	RCU_FLAVOR,
 	RCU_BH_FLAVOR,
 	RCU_SCHED_FLAVOR,
+	RCU_TASKS_FLAVOR,
 	SRCU_FLAVOR,
 	INVALID_RCU_FLAVOR
 };

kernel/rcu/rcutorture.c +39 -1

index febe07062ac5..6d12ab6675bc 100644
@@ -602,6 +602,42 @@ static struct rcu_torture_ops sched_ops = {
 };
 
 /*
+ * Definitions for RCU-tasks torture testing.
+ */
+
+static int tasks_torture_read_lock(void)
+{
+	return 0;
+}
+
+static void tasks_torture_read_unlock(int idx)
+{
+}
+
+static void rcu_tasks_torture_deferred_free(struct rcu_torture *p)
+{
+	call_rcu_tasks(&p->rtort_rcu, rcu_torture_cb);
+}
+
+static struct rcu_torture_ops tasks_ops = {
+	.ttype		= RCU_TASKS_FLAVOR,
+	.init		= rcu_sync_torture_init,
+	.readlock	= tasks_torture_read_lock,
+	.read_delay	= rcu_read_delay,  /* just reuse rcu's version. */
+	.readunlock	= tasks_torture_read_unlock,
+	.completed	= rcu_no_completed,
+	.deferred_free	= rcu_tasks_torture_deferred_free,
+	.sync		= synchronize_rcu_tasks,
+	.exp_sync	= synchronize_rcu_tasks,
+	.call		= call_rcu_tasks,
+	.cb_barrier	= rcu_barrier_tasks,
+	.fqs		= NULL,
+	.stats		= NULL,
+	.irq_capable	= 1,
+	.name		= "tasks"
+};
+
+/*
  * RCU torture priority-boost testing.  Runs one real-time thread per
  * CPU for moderate bursts, repeatedly registering RCU callbacks and
  * spinning waiting for them to be invoked.  If a given callback takes

@@ -1295,7 +1331,8 @@ static int rcu_torture_barrier_cbs(void *arg)
 		if (atomic_dec_and_test(&barrier_cbs_count))
 			wake_up(&barrier_wq);
 	} while (!torture_must_stop());
-	cur_ops->cb_barrier();
+	if (cur_ops->cb_barrier != NULL)
+		cur_ops->cb_barrier();
 	destroy_rcu_head_on_stack(&rcu);
 	torture_kthread_stopping("rcu_torture_barrier_cbs");
 	return 0;

@@ -1534,6 +1571,7 @@ rcu_torture_init(void)
 	int firsterr = 0;
 	static struct rcu_torture_ops *torture_ops[] = {
 		&rcu_ops, &rcu_bh_ops, &rcu_busted_ops, &srcu_ops, &sched_ops,
+		&tasks_ops,
 	};
 
 	if (!torture_init_begin(torture_type, verbose, &rcutorture_runnable))

Signature · 1 line

1.8.1.5

Quoted 6 lines · Paul E. McKenney

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

This commit adds torture tests for RCU-tasks. It also fixes a bug that would segfault for an RCU flavor lacking a callback-barrier function.

Signed-off-by Paul E. McKenney <[email protected]>

Seems reasonable; however, you could also set .cb_barrier = synchronize_rcu_tasks and drop rcu_barrier_tasks.

Either way:

Reviewed-by Josh Triplett <[email protected]>

Quoted 84 lines

 include/linux/rcupdate.h |  1 +
 kernel/rcu/rcutorture.c  | 40 +++++++++++++++++++++++++++++++++++++++-
 2 files changed, 40 insertions(+), 1 deletion(-)

include/linux/rcupdate.h +1 -0

index 17c7e25c38be..ecb2198849e0 100644
@@ -55,6 +55,7 @@ enum rcutorture_type {
 	RCU_FLAVOR,
 	RCU_BH_FLAVOR,
 	RCU_SCHED_FLAVOR,
+	RCU_TASKS_FLAVOR,
 	SRCU_FLAVOR,
 	INVALID_RCU_FLAVOR
 };

kernel/rcu/rcutorture.c +39 -1

index febe07062ac5..6d12ab6675bc 100644
@@ -602,6 +602,42 @@ static struct rcu_torture_ops sched_ops = {
 };
 
 /*
+ * Definitions for RCU-tasks torture testing.
+ */
+
+static int tasks_torture_read_lock(void)
+{
+	return 0;
+}
+
+static void tasks_torture_read_unlock(int idx)
+{
+}
+
+static void rcu_tasks_torture_deferred_free(struct rcu_torture *p)
+{
+	call_rcu_tasks(&p->rtort_rcu, rcu_torture_cb);
+}
+
+static struct rcu_torture_ops tasks_ops = {
+	.ttype		= RCU_TASKS_FLAVOR,
+	.init		= rcu_sync_torture_init,
+	.readlock	= tasks_torture_read_lock,
+	.read_delay	= rcu_read_delay,  /* just reuse rcu's version. */
+	.readunlock	= tasks_torture_read_unlock,
+	.completed	= rcu_no_completed,
+	.deferred_free	= rcu_tasks_torture_deferred_free,
+	.sync		= synchronize_rcu_tasks,
+	.exp_sync	= synchronize_rcu_tasks,
+	.call		= call_rcu_tasks,
+	.cb_barrier	= rcu_barrier_tasks,
+	.fqs		= NULL,
+	.stats		= NULL,
+	.irq_capable	= 1,
+	.name		= "tasks"
+};
+
+/*
  * RCU torture priority-boost testing.  Runs one real-time thread per
  * CPU for moderate bursts, repeatedly registering RCU callbacks and
  * spinning waiting for them to be invoked.  If a given callback takes

@@ -1295,7 +1331,8 @@ static int rcu_torture_barrier_cbs(void *arg)
 		if (atomic_dec_and_test(&barrier_cbs_count))
 			wake_up(&barrier_wq);
 	} while (!torture_must_stop());
-	cur_ops->cb_barrier();
+	if (cur_ops->cb_barrier != NULL)
+		cur_ops->cb_barrier();
 	destroy_rcu_head_on_stack(&rcu);
 	torture_kthread_stopping("rcu_torture_barrier_cbs");
 	return 0;

@@ -1534,6 +1571,7 @@ rcu_torture_init(void)
 	int firsterr = 0;
 	static struct rcu_torture_ops *torture_ops[] = {
 		&rcu_ops, &rcu_bh_ops, &rcu_busted_ops, &srcu_ops, &sched_ops,
+		&tasks_ops,
 	};
 
 	if (!torture_init_begin(torture_type, verbose, &rcutorture_runnable))

Signature · 1 line

1.8.1.5

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

This commit adds a new RCU-tasks flavor of RCU, which provides call_rcu_tasks(). This RCU flavor's quiescent states are voluntary context switch (not preemption!), userspace execution, and the idle loop. Note that unlike other RCU flavors, these quiescent states occur in tasks, not necessarily CPUs. Includes fixes from Steven Rostedt.

This RCU flavor is assumed to have very infrequent latency-tolerate updaters. This assumption permits significant simplifications, including a single global callback list protected by a single global lock, along with a single linked list containing all tasks that have not yet passed through a quiescent state. If experience shows this assumption to be incorrect, the required additional complexity will be added.

Suggested-by Steven Rostedt <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

---
 include/linux/init_task.h |   9 +++
 include/linux/rcupdate.h  |  36 ++++++++++
 include/linux/sched.h     |  23 +++----
 init/Kconfig              |  10 +++
 kernel/rcu/tiny.c         |   2 +
 kernel/rcu/tree.c         |   2 +
 kernel/rcu/update.c       | 164 ++++++++++++++++++++++++++++++++++++++++++++++
 7 files changed, 235 insertions(+), 11 deletions(-)

include/linux/init_task.h +9 -0

index 6df7f9fe0d01..78715ea7c30c 100644
@@ -124,6 +124,14 @@ extern struct group_info init_groups;
 #else
 #define INIT_TASK_RCU_PREEMPT(tsk)
 #endif
+#ifdef CONFIG_TASKS_RCU
+#define INIT_TASK_RCU_TASKS(tsk)					\
+	.rcu_tasks_holdout = false,					\
+	.rcu_tasks_holdout_list =					\
+		LIST_HEAD_INIT(tsk.rcu_tasks_holdout_list),
+#else
+#define INIT_TASK_RCU_TASKS(tsk)
+#endif
 
 extern struct cred init_cred;
 

@@ -231,6 +239,7 @@ extern struct task_group root_task_group;
 	INIT_FTRACE_GRAPH						\
 	INIT_TRACE_RECURSION						\
 	INIT_TASK_RCU_PREEMPT(tsk)					\
+	INIT_TASK_RCU_TASKS(tsk)					\
 	INIT_CPUSET_SEQ(tsk)						\
 	INIT_RT_MUTEXES(tsk)						\
 	INIT_VTIME(tsk)							\

include/linux/rcupdate.h +36 -0

index 6a94cc8b1ca0..05656b504295 100644
@@ -197,6 +197,26 @@ void call_rcu_sched(struct rcu_head *head,
 
 void synchronize_sched(void);
 
+/**
+ * call_rcu_tasks() - Queue an RCU for invocation task-based grace period
+ * @head: structure to be used for queueing the RCU updates.
+ * @func: actual callback function to be invoked after the grace period
+ *
+ * The callback function will be invoked some time after a full grace
+ * period elapses, in other words after all currently executing RCU
+ * read-side critical sections have completed. call_rcu_tasks() assumes
+ * that the read-side critical sections end at a voluntary context
+ * switch (not a preemption!), entry into idle, or transition to usermode
+ * execution.  As such, there are no read-side primitives analogous to
+ * rcu_read_lock() and rcu_read_unlock() because this primitive is intended
+ * to determine that all tasks have passed through a safe state, not so
+ * much for data-strcuture synchronization.
+ *
+ * See the description of call_rcu() for more detailed information on
+ * memory ordering guarantees.
+ */
+void call_rcu_tasks(struct rcu_head *head, void (*func)(struct rcu_head *head));
+
 #ifdef CONFIG_PREEMPT_RCU
 
 void __rcu_read_lock(void);

@@ -294,6 +314,22 @@ static inline void rcu_user_hooks_switch(struct task_struct *prev,
 		rcu_irq_exit(); \
 	} while (0)
 
+/*
+ * Note a voluntary context switch for RCU-tasks benefit.  This is a
+ * macro rather than an inline function to avoid #include hell.
+ */
+#ifdef CONFIG_TASKS_RCU
+#define rcu_note_voluntary_context_switch(t) \
+	do { \
+		preempt_disable(); /* Exclude synchronize_sched(); */ \
+		if ((t)->rcu_tasks_holdout) \
+			smp_store_release(&(t)->rcu_tasks_holdout, 0); \
+		preempt_enable(); \
+	} while (0)
+#else /* #ifdef CONFIG_TASKS_RCU */
+#define rcu_note_voluntary_context_switch(t)	do { } while (0)
+#endif /* #else #ifdef CONFIG_TASKS_RCU */
+
 #if defined(CONFIG_DEBUG_LOCK_ALLOC) || defined(CONFIG_RCU_TRACE) || defined(CONFIG_SMP)
 bool __rcu_is_watching(void);
 #endif /* #if defined(CONFIG_DEBUG_LOCK_ALLOC) || defined(CONFIG_RCU_TRACE) || defined(CONFIG_SMP) */

include/linux/sched.h +12 -11

index 306f4f0c987a..3cf124389ec7 100644
@@ -1273,6 +1273,11 @@ struct task_struct {
 #ifdef CONFIG_RCU_BOOST
 	struct rt_mutex *rcu_boost_mutex;
 #endif /* #ifdef CONFIG_RCU_BOOST */
+#ifdef CONFIG_TASKS_RCU
+	unsigned long rcu_tasks_nvcsw;
+	int rcu_tasks_holdout;
+	struct list_head rcu_tasks_holdout_list;
+#endif /* #ifdef CONFIG_TASKS_RCU */
 
 #if defined(CONFIG_SCHEDSTATS) || defined(CONFIG_TASK_DELAY_ACCT)
 	struct sched_info sched_info;

@@ -1998,31 +2003,27 @@ extern void task_clear_jobctl_pending(struct task_struct *task,
 				      unsigned int mask);
 
 #ifdef CONFIG_PREEMPT_RCU
-
 #define RCU_READ_UNLOCK_BLOCKED (1 << 0) /* blocked while in RCU read-side. */
 #define RCU_READ_UNLOCK_NEED_QS (1 << 1) /* RCU core needs CPU response. */
+#endif /* #ifdef CONFIG_PREEMPT_RCU */
 
 static inline void rcu_copy_process(struct task_struct *p)
 {
+#ifdef CONFIG_PREEMPT_RCU
 	p->rcu_read_lock_nesting = 0;
 	p->rcu_read_unlock_special = 0;
-#ifdef CONFIG_TREE_PREEMPT_RCU
 	p->rcu_blocked_node = NULL;
-#endif /* #ifdef CONFIG_TREE_PREEMPT_RCU */
 #ifdef CONFIG_RCU_BOOST
 	p->rcu_boost_mutex = NULL;
 #endif /* #ifdef CONFIG_RCU_BOOST */
 	INIT_LIST_HEAD(&p->rcu_node_entry);
+#endif /* #ifdef CONFIG_PREEMPT_RCU */
+#ifdef CONFIG_TASKS_RCU
+	p->rcu_tasks_holdout = false;
+	INIT_LIST_HEAD(&p->rcu_tasks_holdout_list);
+#endif /* #ifdef CONFIG_TASKS_RCU */
 }
 
-#else
-
-static inline void rcu_copy_process(struct task_struct *p)
-{
-}
-
-#endif
-
 static inline void tsk_restore_flags(struct task_struct *task,
 				unsigned long orig_flags, unsigned long flags)
 {

init/Kconfig +10 -0

index 9d76b99af1b9..c56cb62a2df1 100644
@@ -507,6 +507,16 @@ config PREEMPT_RCU
 	  This option enables preemptible-RCU code that is common between
 	  the TREE_PREEMPT_RCU and TINY_PREEMPT_RCU implementations.
 
+config TASKS_RCU
+	bool "Task_based RCU implementation using voluntary context switch"
+	default n
+	help
+	  This option enables a task-based RCU implementation that uses
+	  only voluntary context switch (not preemption!), idle, and
+	  user-mode execution as quiescent states.
+
+	  If unsure, say N.
+
 config RCU_STALL_COMMON
 	def_bool ( TREE_RCU || TREE_PREEMPT_RCU || RCU_TRACE )
 	help

kernel/rcu/tiny.c +2 -0

index d9efcc13008c..717f00854fc0 100644
@@ -254,6 +254,8 @@ void rcu_check_callbacks(int cpu, int user)
 		rcu_sched_qs(cpu);
 	else if (!in_softirq())
 		rcu_bh_qs(cpu);
+	if (user)
+		rcu_note_voluntary_context_switch(current);
 }
 
 /*

kernel/rcu/tree.c +2 -0

index 625d0b0cd75a..f958c52f644d 100644
@@ -2413,6 +2413,8 @@ void rcu_check_callbacks(int cpu, int user)
 	rcu_preempt_check_callbacks(cpu);
 	if (rcu_pending(cpu))
 		invoke_rcu_core();
+	if (user)
+		rcu_note_voluntary_context_switch(current);
 	trace_rcu_utilization(TPS("End scheduler-tick"));
 }
 

kernel/rcu/update.c +60 -0

index bc7883570530..b92268647a01 100644
@@ -47,6 +47,7 @@
 #include <linux/hardirq.h>
 #include <linux/delay.h>
 #include <linux/module.h>
+#include <linux/kthread.h>
 
 #define CREATE_TRACE_POINTS
 

@@ -350,3 +351,166 @@ static int __init check_cpu_stall_init(void)
 early_initcall(check_cpu_stall_init);
 
 #endif /* #ifdef CONFIG_RCU_STALL_COMMON */
+
+#ifdef CONFIG_TASKS_RCU
+
+/*
+ * Simple variant of RCU whose quiescent states are voluntary context switch,
+ * user-space execution, and idle.  As such, grace periods can take one good
+ * long time.  There are no read-side primitives similar to rcu_read_lock()
+ * and rcu_read_unlock() because this implementation is intended to get
+ * the system into a safe state for some of the manipulations involved in
+ * tracing and the like.  Finally, this implementation does not support
+ * high call_rcu_tasks() rates from multiple CPUs.  If this is required,
+ * per-CPU callback lists will be needed.
+ */
+
+/* Lists of tasks that we are still waiting for during this grace period. */
+static LIST_HEAD(rcu_tasks_holdouts);
+
+/* Global list of callbacks and associated lock. */
+static struct rcu_head *rcu_tasks_cbs_head;
+static struct rcu_head **rcu_tasks_cbs_tail = &rcu_tasks_cbs_head;
+static DEFINE_RAW_SPINLOCK(rcu_tasks_cbs_lock);
+
+/* Post an RCU-tasks callback. */
+void call_rcu_tasks(struct rcu_head *rhp, void (*func)(struct rcu_head *rhp))
+{
+	unsigned long flags;
+
+	rhp->next = NULL;
+	rhp->func = func;
+	raw_spin_lock_irqsave(&rcu_tasks_cbs_lock, flags);
+	*rcu_tasks_cbs_tail = rhp;
+	rcu_tasks_cbs_tail = &rhp->next;
+	raw_spin_unlock_irqrestore(&rcu_tasks_cbs_lock, flags);
+}
+EXPORT_SYMBOL_GPL(call_rcu_tasks);
+
+/* RCU-tasks kthread that detects grace periods and invokes callbacks. */
+static int __noreturn rcu_tasks_kthread(void *arg)
+{
+	unsigned long flags;
+	struct task_struct *g, *t;
+	struct rcu_head *list;
+	struct rcu_head *next;
+
+	/* FIXME: Add housekeeping affinity. */
+
+	/*
+	 * Each pass through the following loop makes one check for
+	 * newly arrived callbacks, and, if there are some, waits for
+	 * one RCU-tasks grace period and then invokes the callbacks.
+	 * This loop is terminated by the system going down.  ;-)
+	 */
+	for (;;) {
+
+		/* Pick up any new callbacks. */
+		raw_spin_lock_irqsave(&rcu_tasks_cbs_lock, flags);
+		smp_mb__after_unlock_lock(); /* Enforce GP memory ordering. */
+		list = rcu_tasks_cbs_head;
+		rcu_tasks_cbs_head = NULL;

kernel/rcu/update.c +27 -0

+			}
+		}
+		rcu_read_unlock();
+
+		/*
+		 * The "t != current" and "!is_idle_task()" comparisons
+		 * above are stable, but the "t->on_rq" value could
+		 * change at any time, and is generally unordered.
+		 * Therefore, we need some ordering.  The trick is
+		 * that t->on_rq is updated with a runqueue lock held,
+		 * and thus with interrupts disabled.  So the following
+		 * synchronize_sched() provides the needed ordering by:
+		 * (1) Waiting for all interrupts-disabled code sections
+		 * to complete and (2) The synchronize_sched() ordering
+		 * guarantees, which provide for a memory barrier on each
+		 * CPU since the completion of its last read-side critical
+		 * section, including interrupt-disabled code sections.
+		 */
+		synchronize_sched();
+
+		/*
+		 * Each pass through the following loop scans the list
+		 * of holdout tasks, removing any that are no longer
+		 * holdouts.  When the list is empty, we are done.
+		 */
+		while (!list_empty(&rcu_tasks_holdouts)) {
+			schedule_timeout_interruptible(HZ / 10);

kernel/rcu/update.c +42 -0

+				list_del_init(&t->rcu_tasks_holdout_list);
+				/* @@@ need to check for usermode on CPU. */
+			}
+			rcu_read_unlock();
+		}
+
+		/*
+		 * Because ->nvcsw is not guaranteed to have a full
+		 * memory barrier prior to it in the schedule() path,
+		 * memory reordering on other CPUs could cause their
+		 * RCU-tasks read-side critical sections to extend past
+		 * the end of the grace period.  However, because these
+		 * ->nvcsw updates are carried out with interrupts
+		 * disabled, we can use synchronize_sched() to force
+		 * the needed ordering on all such CPUs.
+		 */
+		synchronize_sched();
+
+		/* Invoke the callbacks. */
+		while (list) {
+			next = list->next;
+			local_bh_disable();
+			list->func(list);
+			local_bh_enable();
+			list = next;
+			cond_resched();
+		}
+	}
+}
+
+/* Spawn rcu_tasks_kthread() at boot time. */
+static int __init rcu_spawn_tasks_kthread(void)
+{
+	struct task_struct __maybe_unused *t;
+
+	t = kthread_run(rcu_tasks_kthread, NULL, "rcu_tasks_kthread");
+	BUG_ON(IS_ERR(t));
+	return 0;
+}
+early_initcall(rcu_spawn_tasks_kthread);
+
+#endif /* #ifdef CONFIG_TASKS_RCU */

Quoted 290 lines · Paul E. McKenney

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

This commit adds a new RCU-tasks flavor of RCU, which provides call_rcu_tasks(). This RCU flavor's quiescent states are voluntary context switch (not preemption!), userspace execution, and the idle loop. Note that unlike other RCU flavors, these quiescent states occur in tasks, not necessarily CPUs. Includes fixes from Steven Rostedt.

This RCU flavor is assumed to have very infrequent latency-tolerate updaters. This assumption permits significant simplifications, including a single global callback list protected by a single global lock, along with a single linked list containing all tasks that have not yet passed through a quiescent state. If experience shows this assumption to be incorrect, the required additional complexity will be added.

Suggested-by Steven Rostedt <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

---
 include/linux/init_task.h |   9 +++
 include/linux/rcupdate.h  |  36 ++++++++++
 include/linux/sched.h     |  23 +++----
 init/Kconfig              |  10 +++
 kernel/rcu/tiny.c         |   2 +
 kernel/rcu/tree.c         |   2 +
 kernel/rcu/update.c       | 164 ++++++++++++++++++++++++++++++++++++++++++++++
 7 files changed, 235 insertions(+), 11 deletions(-)

include/linux/init_task.h +9 -0

index 6df7f9fe0d01..78715ea7c30c 100644
@@ -124,6 +124,14 @@ extern struct group_info init_groups;
 #else
 #define INIT_TASK_RCU_PREEMPT(tsk)
 #endif
+#ifdef CONFIG_TASKS_RCU
+#define INIT_TASK_RCU_TASKS(tsk)					\
+	.rcu_tasks_holdout = false,					\
+	.rcu_tasks_holdout_list =					\
+		LIST_HEAD_INIT(tsk.rcu_tasks_holdout_list),
+#else
+#define INIT_TASK_RCU_TASKS(tsk)
+#endif
 
 extern struct cred init_cred;
 

@@ -231,6 +239,7 @@ extern struct task_group root_task_group;
 	INIT_FTRACE_GRAPH						\
 	INIT_TRACE_RECURSION						\
 	INIT_TASK_RCU_PREEMPT(tsk)					\
+	INIT_TASK_RCU_TASKS(tsk)					\
 	INIT_CPUSET_SEQ(tsk)						\
 	INIT_RT_MUTEXES(tsk)						\
 	INIT_VTIME(tsk)							\

include/linux/rcupdate.h +36 -0

index 6a94cc8b1ca0..05656b504295 100644
@@ -197,6 +197,26 @@ void call_rcu_sched(struct rcu_head *head,
 
 void synchronize_sched(void);
 
+/**
+ * call_rcu_tasks() - Queue an RCU for invocation task-based grace period
+ * @head: structure to be used for queueing the RCU updates.
+ * @func: actual callback function to be invoked after the grace period
+ *
+ * The callback function will be invoked some time after a full grace
+ * period elapses, in other words after all currently executing RCU
+ * read-side critical sections have completed. call_rcu_tasks() assumes
+ * that the read-side critical sections end at a voluntary context
+ * switch (not a preemption!), entry into idle, or transition to usermode
+ * execution.  As such, there are no read-side primitives analogous to
+ * rcu_read_lock() and rcu_read_unlock() because this primitive is intended
+ * to determine that all tasks have passed through a safe state, not so
+ * much for data-strcuture synchronization.
+ *
+ * See the description of call_rcu() for more detailed information on
+ * memory ordering guarantees.
+ */
+void call_rcu_tasks(struct rcu_head *head, void (*func)(struct rcu_head *head));
+
 #ifdef CONFIG_PREEMPT_RCU
 
 void __rcu_read_lock(void);

@@ -294,6 +314,22 @@ static inline void rcu_user_hooks_switch(struct task_struct *prev,
 		rcu_irq_exit(); \
 	} while (0)
 
+/*
+ * Note a voluntary context switch for RCU-tasks benefit.  This is a
+ * macro rather than an inline function to avoid #include hell.
+ */
+#ifdef CONFIG_TASKS_RCU
+#define rcu_note_voluntary_context_switch(t) \
+	do { \
+		preempt_disable(); /* Exclude synchronize_sched(); */ \
+		if ((t)->rcu_tasks_holdout) \
+			smp_store_release(&(t)->rcu_tasks_holdout, 0); \
+		preempt_enable(); \
+	} while (0)
+#else /* #ifdef CONFIG_TASKS_RCU */
+#define rcu_note_voluntary_context_switch(t)	do { } while (0)
+#endif /* #else #ifdef CONFIG_TASKS_RCU */
+
 #if defined(CONFIG_DEBUG_LOCK_ALLOC) || defined(CONFIG_RCU_TRACE) || defined(CONFIG_SMP)
 bool __rcu_is_watching(void);
 #endif /* #if defined(CONFIG_DEBUG_LOCK_ALLOC) || defined(CONFIG_RCU_TRACE) || defined(CONFIG_SMP) */

include/linux/sched.h +12 -11

index 306f4f0c987a..3cf124389ec7 100644
@@ -1273,6 +1273,11 @@ struct task_struct {
 #ifdef CONFIG_RCU_BOOST
 	struct rt_mutex *rcu_boost_mutex;
 #endif /* #ifdef CONFIG_RCU_BOOST */
+#ifdef CONFIG_TASKS_RCU
+	unsigned long rcu_tasks_nvcsw;
+	int rcu_tasks_holdout;
+	struct list_head rcu_tasks_holdout_list;
+#endif /* #ifdef CONFIG_TASKS_RCU */
 
 #if defined(CONFIG_SCHEDSTATS) || defined(CONFIG_TASK_DELAY_ACCT)
 	struct sched_info sched_info;

@@ -1998,31 +2003,27 @@ extern void task_clear_jobctl_pending(struct task_struct *task,
 				      unsigned int mask);
 
 #ifdef CONFIG_PREEMPT_RCU
-
 #define RCU_READ_UNLOCK_BLOCKED (1 << 0) /* blocked while in RCU read-side. */
 #define RCU_READ_UNLOCK_NEED_QS (1 << 1) /* RCU core needs CPU response. */
+#endif /* #ifdef CONFIG_PREEMPT_RCU */
 
 static inline void rcu_copy_process(struct task_struct *p)
 {
+#ifdef CONFIG_PREEMPT_RCU
 	p->rcu_read_lock_nesting = 0;
 	p->rcu_read_unlock_special = 0;
-#ifdef CONFIG_TREE_PREEMPT_RCU
 	p->rcu_blocked_node = NULL;
-#endif /* #ifdef CONFIG_TREE_PREEMPT_RCU */
 #ifdef CONFIG_RCU_BOOST
 	p->rcu_boost_mutex = NULL;
 #endif /* #ifdef CONFIG_RCU_BOOST */
 	INIT_LIST_HEAD(&p->rcu_node_entry);
+#endif /* #ifdef CONFIG_PREEMPT_RCU */
+#ifdef CONFIG_TASKS_RCU
+	p->rcu_tasks_holdout = false;
+	INIT_LIST_HEAD(&p->rcu_tasks_holdout_list);
+#endif /* #ifdef CONFIG_TASKS_RCU */
 }
 
-#else
-
-static inline void rcu_copy_process(struct task_struct *p)
-{
-}
-
-#endif
-
 static inline void tsk_restore_flags(struct task_struct *task,
 				unsigned long orig_flags, unsigned long flags)
 {

init/Kconfig +10 -0

index 9d76b99af1b9..c56cb62a2df1 100644
@@ -507,6 +507,16 @@ config PREEMPT_RCU
 	  This option enables preemptible-RCU code that is common between
 	  the TREE_PREEMPT_RCU and TINY_PREEMPT_RCU implementations.
 
+config TASKS_RCU
+	bool "Task_based RCU implementation using voluntary context switch"
+	default n
+	help
+	  This option enables a task-based RCU implementation that uses
+	  only voluntary context switch (not preemption!), idle, and
+	  user-mode execution as quiescent states.
+
+	  If unsure, say N.
+
 config RCU_STALL_COMMON
 	def_bool ( TREE_RCU || TREE_PREEMPT_RCU || RCU_TRACE )
 	help

kernel/rcu/tiny.c +2 -0

index d9efcc13008c..717f00854fc0 100644
@@ -254,6 +254,8 @@ void rcu_check_callbacks(int cpu, int user)
 		rcu_sched_qs(cpu);
 	else if (!in_softirq())
 		rcu_bh_qs(cpu);
+	if (user)
+		rcu_note_voluntary_context_switch(current);
 }
 
 /*

kernel/rcu/tree.c +2 -0

index 625d0b0cd75a..f958c52f644d 100644
@@ -2413,6 +2413,8 @@ void rcu_check_callbacks(int cpu, int user)
 	rcu_preempt_check_callbacks(cpu);
 	if (rcu_pending(cpu))
 		invoke_rcu_core();
+	if (user)
+		rcu_note_voluntary_context_switch(current);
 	trace_rcu_utilization(TPS("End scheduler-tick"));
 }
 

kernel/rcu/update.c +65 -0

index bc7883570530..b92268647a01 100644
@@ -47,6 +47,7 @@
 #include <linux/hardirq.h>
 #include <linux/delay.h>
 #include <linux/module.h>
+#include <linux/kthread.h>
 
 #define CREATE_TRACE_POINTS
 

@@ -350,3 +351,166 @@ static int __init check_cpu_stall_init(void)
 early_initcall(check_cpu_stall_init);
 
 #endif /* #ifdef CONFIG_RCU_STALL_COMMON */
+
+#ifdef CONFIG_TASKS_RCU
+
+/*
+ * Simple variant of RCU whose quiescent states are voluntary context switch,
+ * user-space execution, and idle.  As such, grace periods can take one good
+ * long time.  There are no read-side primitives similar to rcu_read_lock()
+ * and rcu_read_unlock() because this implementation is intended to get
+ * the system into a safe state for some of the manipulations involved in
+ * tracing and the like.  Finally, this implementation does not support
+ * high call_rcu_tasks() rates from multiple CPUs.  If this is required,
+ * per-CPU callback lists will be needed.
+ */
+
+/* Lists of tasks that we are still waiting for during this grace period. */
+static LIST_HEAD(rcu_tasks_holdouts);
+
+/* Global list of callbacks and associated lock. */
+static struct rcu_head *rcu_tasks_cbs_head;
+static struct rcu_head **rcu_tasks_cbs_tail = &rcu_tasks_cbs_head;
+static DEFINE_RAW_SPINLOCK(rcu_tasks_cbs_lock);
+
+/* Post an RCU-tasks callback. */
+void call_rcu_tasks(struct rcu_head *rhp, void (*func)(struct rcu_head *rhp))
+{
+	unsigned long flags;
+
+	rhp->next = NULL;
+	rhp->func = func;
+	raw_spin_lock_irqsave(&rcu_tasks_cbs_lock, flags);
+	*rcu_tasks_cbs_tail = rhp;
+	rcu_tasks_cbs_tail = &rhp->next;
+	raw_spin_unlock_irqrestore(&rcu_tasks_cbs_lock, flags);
+}
+EXPORT_SYMBOL_GPL(call_rcu_tasks);
+
+/* RCU-tasks kthread that detects grace periods and invokes callbacks. */
+static int __noreturn rcu_tasks_kthread(void *arg)
+{
+	unsigned long flags;
+	struct task_struct *g, *t;
+	struct rcu_head *list;
+	struct rcu_head *next;
+
+	/* FIXME: Add housekeeping affinity. */
+
+	/*
+	 * Each pass through the following loop makes one check for
+	 * newly arrived callbacks, and, if there are some, waits for
+	 * one RCU-tasks grace period and then invokes the callbacks.
+	 * This loop is terminated by the system going down.  ;-)
+	 */
+	for (;;) {
+
+		/* Pick up any new callbacks. */
+		raw_spin_lock_irqsave(&rcu_tasks_cbs_lock, flags);
+		smp_mb__after_unlock_lock(); /* Enforce GP memory ordering. */
+		list = rcu_tasks_cbs_head;
+		rcu_tasks_cbs_head = NULL;
+		rcu_tasks_cbs_tail = &rcu_tasks_cbs_head;
+		raw_spin_unlock_irqrestore(&rcu_tasks_cbs_lock, flags);
+
+		/* If there were none, wait a bit and start over. */
+		if (!list) {

kernel/rcu/update.c static int __init check_cpu_stall_init(void) · line 422

Quoted 5 lines

kernel/rcu/update.c +5 -0

+			schedule_timeout_interruptible(HZ);
+			flush_signals(current);
+			continue;
+		}
+

A "synchronize_sched();" may be needed here, or else the following code may read t->on_rq == 0 but actually the task is just running and traced with trampoline.

kernel/rcu/update.c static int __init check_cpu_stall_init(void) · line 433

Quoted 11 lines

kernel/rcu/update.c +11 -0

+		/*
+		 * There were callbacks, so we need to wait for an
+		 * RCU-tasks grace period.  Start off by scanning
+		 * the task list for tasks that are not already
+		 * voluntarily blocked.  Mark these tasks and make
+		 * a list of them in rcu_tasks_holdouts.
+		 */
+		rcu_read_lock();
+		for_each_process_thread(g, t) {
+			if (t != current && ACCESS_ONCE(t->on_rq) &&
+			    !is_idle_task(t)) {

What happen when the trampoline is on the idle task?

I think we need to use schedule_on_each_cpu() to replace one of the synchronize_sched() in this function. (or other stuff which can cause real schedule for *ALL* online CPUs).

kernel/rcu/update.c static int __init check_cpu_stall_init(void) · line 437

Quoted 4 lines

kernel/rcu/update.c +4 -0

+				t->rcu_tasks_nvcsw = ACCESS_ONCE(t->nvcsw);
+				t->rcu_tasks_holdout = 1;
+				list_add(&t->rcu_tasks_holdout_list,
+					 &rcu_tasks_holdouts);

I think get_task_struct() is needed here to avoid the task disappears.

Quoted 31 lines

kernel/rcu/update.c +31 -0

+			}
+		}
+		rcu_read_unlock();
+
+		/*
+		 * The "t != current" and "!is_idle_task()" comparisons
+		 * above are stable, but the "t->on_rq" value could
+		 * change at any time, and is generally unordered.
+		 * Therefore, we need some ordering.  The trick is
+		 * that t->on_rq is updated with a runqueue lock held,
+		 * and thus with interrupts disabled.  So the following
+		 * synchronize_sched() provides the needed ordering by:
+		 * (1) Waiting for all interrupts-disabled code sections
+		 * to complete and (2) The synchronize_sched() ordering
+		 * guarantees, which provide for a memory barrier on each
+		 * CPU since the completion of its last read-side critical
+		 * section, including interrupt-disabled code sections.
+		 */
+		synchronize_sched();
+
+		/*
+		 * Each pass through the following loop scans the list
+		 * of holdout tasks, removing any that are no longer
+		 * holdouts.  When the list is empty, we are done.
+		 */
+		while (!list_empty(&rcu_tasks_holdouts)) {
+			schedule_timeout_interruptible(HZ / 10);
+			flush_signals(current);
+			rcu_read_lock();
+			list_for_each_entry_rcu(t, &rcu_tasks_holdouts,
+						rcu_tasks_holdout_list) {

kernel/rcu/update.c static int __init check_cpu_stall_init(void) · line 474

Quoted 6 lines

kernel/rcu/update.c +6 -0

+				if (smp_load_acquire(&t->rcu_tasks_holdout)) {
+					if (t->rcu_tasks_nvcsw ==
+					    ACCESS_ONCE(t->nvcsw))
+						continue;
+					ACCESS_ONCE(t->rcu_tasks_holdout) = 0;
+				}

t->on_rq can be rechecked here.

I think the recheck for t->on_rq and get_task_struct()/put_task_struct() can handle the exiting of the tasks, thus we don't need the complex of the patch 10/10.

Quick and superficial thought,

Thanks,
Lai

Quoted 42 lines

kernel/rcu/update.c +42 -0

+				list_del_init(&t->rcu_tasks_holdout_list);
+				/* @@@ need to check for usermode on CPU. */
+			}
+			rcu_read_unlock();
+		}
+
+		/*
+		 * Because ->nvcsw is not guaranteed to have a full
+		 * memory barrier prior to it in the schedule() path,
+		 * memory reordering on other CPUs could cause their
+		 * RCU-tasks read-side critical sections to extend past
+		 * the end of the grace period.  However, because these
+		 * ->nvcsw updates are carried out with interrupts
+		 * disabled, we can use synchronize_sched() to force
+		 * the needed ordering on all such CPUs.
+		 */
+		synchronize_sched();
+
+		/* Invoke the callbacks. */
+		while (list) {
+			next = list->next;
+			local_bh_disable();
+			list->func(list);
+			local_bh_enable();
+			list = next;
+			cond_resched();
+		}
+	}
+}
+
+/* Spawn rcu_tasks_kthread() at boot time. */
+static int __init rcu_spawn_tasks_kthread(void)
+{
+	struct task_struct __maybe_unused *t;
+
+	t = kthread_run(rcu_tasks_kthread, NULL, "rcu_tasks_kthread");
+	BUG_ON(IS_ERR(t));
+	return 0;
+}
+early_initcall(rcu_spawn_tasks_kthread);
+
+#endif /* #ifdef CONFIG_TASKS_RCU */

Well, that is one of the questions in the 0/10 cover letter. If it turns out to be necessary to worry about idle-task trampolines, it should be possible to avoid hammering all idle CPUs in the common case. Though maybe battery-powered devices won't need RCU-tasks.

Quoted 4 lines · Paul E. McKenney

Well, that is one of the questions in the 0/10 cover letter. If it turns out to be necessary to worry about idle-task trampolines, it should be possible to avoid hammering all idle CPUs in the common case. Though maybe battery-powered devices won't need RCU-tasks.

So do we really need this to be a full blown RCU implementation? Could we not live with something like a task_barrier() function that guarantees the same as this rcu_task_synchronize() or somesuch?

So for rostedt's case he could patch out all trampolines, call task_barrier() and then free them.

We can make task_barrier() force each cpu to resched once -- which, if we do that after the task's have all scheduled once, could be the empty set.

It also pushes the cost of this machinery into the caller of task_barrier() and not in some random kthread (yet another one).

Now, if only task_work would work for kernel threads, then we could do something far nicer...

The idea here is to avoid having the kthread and to avoid providing callbacks, but to instead do the work currently done by the kthread in a synchronous function called by the updater?

My concern with this approach is that I bet that Steven will want to have multiple concurrent calls to remove trampolines, and if I need to support that efficiently, I end up with more-painful counter tricks instead of the current callbacks.

Or am I confused about what you are suggesting?

Quoted 2 lines

Now, if only task_work would work for kernel threads, then we could do something far nicer...

OK, I'll bite... What is task_work? I am guessing that you are not talking about struct ql4_task_data in drivers/scsi/qla4xxx/ql4_def.h. ;-)

Quoted 6 lines · Lai Jiangshan

kernel/rcu/update.c static int __init check_cpu_stall_init(void) · line 437

Quoted 4 lines

kernel/rcu/update.c +4 -0

+				t->rcu_tasks_nvcsw = ACCESS_ONCE(t->nvcsw);
+				t->rcu_tasks_holdout = 1;
+				list_add(&t->rcu_tasks_holdout_list,
+					 &rcu_tasks_holdouts);

I think get_task_struct() is needed here to avoid the task disappears.

Hmmm... Let's see...

Looks like get_task_struct() does a blind atomic increment of ->usage. And put_task_struct() does an atomic_dec_and_test(). So one question is "what prevents us from doing get_task_struct() after the final put_task_struct() has pushed ->usage down to zero?"

Hopefully there is a grace period in there somewhere, otherwise it will be necessary to take the task-list lock, which I would like to avoid.

Looks like the call_rcu() of delayed_put_task_struct() in release_task() might be doing this.

Again, sorry, I didn't read the patches yet, just noticed your discussion...

Quoted 20 lines · Paul E. McKenney

Quoted 6 lines · Lai Jiangshan

kernel/rcu/update.c static int __init check_cpu_stall_init(void) · line 437

Quoted 4 lines

kernel/rcu/update.c +4 -0

+				t->rcu_tasks_nvcsw = ACCESS_ONCE(t->nvcsw);
+				t->rcu_tasks_holdout = 1;
+				list_add(&t->rcu_tasks_holdout_list,
+					 &rcu_tasks_holdouts);

I think get_task_struct() is needed here to avoid the task disappears.

Hmmm... Let's see...

Looks like get_task_struct() does a blind atomic increment of ->usage. And put_task_struct() does an atomic_dec_and_test(). So one question is "what prevents us from doing get_task_struct() after the final put_task_struct() has pushed ->usage down to zero?"

Hopefully there is a grace period in there somewhere, otherwise it will be necessary to take the task-list lock, which I would like to avoid.

Quoted 2 lines

Looks like the call_rcu() of delayed_put_task_struct() in release_task() might be doing this.

Yes, exactly, so get_task_struct() is always fine as long as task_struct itself is protected by RCU.

But can't we avoid get_task_struct()? This can pin a lot of task_struct's. Can't we just add list_del_rcu(holdout_list) into __unhash_process() ?

We only need to ensure that list_add() above can't race with that list_del(), perhaps we can tolerate lock_task_sighand() ?

Quoted 2 lines · Oleg Nesterov

But can't we avoid get_task_struct()? This can pin a lot of task_struct's. Can't we just add list_del_rcu(holdout_list) into __unhash_process() ?

If I add the list_del_rcu() there, then I am back to a concurrent list, which I would like to avoid. Don't get me wrong, it was fun playing with the list-locked stuff, but best to avoid it if we can.

The nice thing about using get_task_struct to lock
them down is that -only- the task_struct itself is locked down -- the task can be reaped and so on.

Quoted 2 lines

We only need to ensure that list_add() above can't race with that list_del(), perhaps we can tolerate lock_task_sighand() ?

I am worried about a task that does a voluntary context switch, then exits. This could results in rcu_tasks_kthread() and __unhash_process() both wanting to dequeue at the same time, right?

Quoted 9 lines · Paul E. McKenney

Quoted 2 lines · Oleg Nesterov

But can't we avoid get_task_struct()? This can pin a lot of task_struct's. Can't we just add list_del_rcu(holdout_list) into __unhash_process() ?

If I add the list_del_rcu() there, then I am back to a concurrent list, which I would like to avoid. Don't get me wrong, it was fun playing with the list-locked stuff, but best to avoid it if we can.

OK,

Quoted 3 lines

The nice thing about using get_task_struct to lock
them down is that -only- the task_struct itself is locked down -- the task can be reaped and so on.

I understand. but otoh it would be nice to not pin this memory if the task was already (auto)reaped.

And afaics the number of pinned task_struct's is not bounded. In theory it is not even limited by, say, PID_MAX_LIMIT. A thread can exit and reap itself right after get_task_struct() but create another running thread which can be noticed by rcu_tasks_kthread() too.

Quoted 6 lines

Quoted 2 lines

We only need to ensure that list_add() above can't race with that list_del(), perhaps we can tolerate lock_task_sighand() ?

I am worried about a task that does a voluntary context switch, then exits. This could results in rcu_tasks_kthread() and __unhash_process() both wanting to dequeue at the same time, right?

Oh yes, I was very wrong. And we do not want to abuse tasklist_lock...

OK, let me try to read the patch first.

Quoted 15 lines

kernel/rcu/update.c static int __init check_cpu_stall_init(void) · line 433

Quoted 12 lines

kernel/rcu/update.c +11 -0

+		/*
+		 * There were callbacks, so we need to wait for an
+		 * RCU-tasks grace period.  Start off by scanning
+		 * the task list for tasks that are not already
+		 * voluntarily blocked.  Mark these tasks and make
+		 * a list of them in rcu_tasks_holdouts.
+		 */
+		rcu_read_lock();
+		for_each_process_thread(g, t) {
+			if (t != current && ACCESS_ONCE(t->on_rq) &&
+			    !is_idle_task(t)) {

What happen when the trampoline is on the idle task?

Quoted 3 lines

I think we need to use schedule_on_each_cpu() to replace one of the synchronize_sched() in this function. (or other stuff which can cause real schedule for *ALL* online CPUs).

Well, that is one of the questions in the 0/10 cover letter. If it turns out to be necessary to worry about idle-task trampolines, it should be possible to avoid hammering all idle CPUs in the common case. Though maybe battery-powered devices won't need RCU-tasks.

Quoted 19 lines · Paul E. McKenney

Quoted 18 lines

kernel/rcu/update.c static int __init check_cpu_stall_init(void) · line 433

Quoted 12 lines

kernel/rcu/update.c +11 -0

+		/*
+		 * There were callbacks, so we need to wait for an
+		 * RCU-tasks grace period.  Start off by scanning
+		 * the task list for tasks that are not already
+		 * voluntarily blocked.  Mark these tasks and make
+		 * a list of them in rcu_tasks_holdouts.
+		 */
+		rcu_read_lock();
+		for_each_process_thread(g, t) {
+			if (t != current && ACCESS_ONCE(t->on_rq) &&
+			    !is_idle_task(t)) {

What happen when the trampoline is on the idle task?

I think we need to use schedule_on_each_cpu() to replace one of the synchronize_sched() in this function. (or other stuff which can cause real schedule for *ALL* online CPUs).

Quoted 4 lines

Well, that is one of the questions in the 0/10 cover letter. If it turns out to be necessary to worry about idle-task trampolines, it should be possible to avoid hammering all idle CPUs in the common case. Though maybe battery-powered devices won't need RCU-tasks.

trampolines on NO_HZ idle CPU can be arbitrary long, (example, SMI happens inside the trampoline). So only the real schedule on idle CPU is reliable to me.

kernel/rcu/update.c static int __init check_cpu_stall_init(void) · line 440

Quoted 12 lines · Paul E. McKenney

kernel/rcu/update.c +11 -0

+		rcu_read_lock();
+		for_each_process_thread(g, t) {
+			if (t != current && ACCESS_ONCE(t->on_rq) &&
+			    !is_idle_task(t)) {
+				t->rcu_tasks_nvcsw = ACCESS_ONCE(t->nvcsw);
+				t->rcu_tasks_holdout = 1;
+				list_add(&t->rcu_tasks_holdout_list,
+					 &rcu_tasks_holdouts);
+			}
+		}
+		rcu_read_unlock();

Wait, unless I missed something this can't work...

The problem is, once the exiting task passes exit_notify() it can be removed from rcu lists.

Now suppose that (say) proc_exit_connector() has a probe, and this task has jumped into trampoline and it was preempted there.

No?

Quoted 19 lines · Oleg Nesterov

kernel/rcu/update.c static int __init check_cpu_stall_init(void) · line 440

Quoted 12 lines · Paul E. McKenney

kernel/rcu/update.c +11 -0

+		rcu_read_lock();
+		for_each_process_thread(g, t) {
+			if (t != current && ACCESS_ONCE(t->on_rq) &&
+			    !is_idle_task(t)) {
+				t->rcu_tasks_nvcsw = ACCESS_ONCE(t->nvcsw);
+				t->rcu_tasks_holdout = 1;
+				list_add(&t->rcu_tasks_holdout_list,
+					 &rcu_tasks_holdouts);
+			}
+		}
+		rcu_read_unlock();

Wait, unless I missed something this can't work...

The problem is, once the exiting task passes exit_notify() it can be removed from rcu lists.

Quoted 4 lines

Now suppose that (say) proc_exit_connector() has a probe, and this task has jumped into trampoline and it was preempted there.

No?

OK, this sounds to me like another vote for get_task_struct() as used in the v3 series. Or am I missing something?

This series provides a prototype of an RCU-tasks implementation, which has been requested to assist with tramopoline removal. This flavor of RCU is task-based rather than CPU-based, and has voluntary context switch, usermode execution, and the idle loops as its only quiescent states. This selection of quiescent states ensures that at the end of a grace period, there will no longer be any tasks depending on a trampoline that was removed before the beginning of that grace period. This works because such trampolines do not contain function calls, do not contain voluntary context switches, do not switch to usermode, and do not switch to idle.

Also, ideally this should remain entirely optional; nothing in the core kernel should depend on it.

Quoted 2 lines · On Thu, Jul 31, 2014 at 09:19:02AM -0700, [email protected] wrote:

Also, ideally this should remain entirely optional; nothing in the core kernel should depend on it.

I suspect Steve wants it for ftrace :-)

Quoted 2 lines · On Thu, Jul 31, 2014 at 09:19:02AM -0700, [email protected] wrote:

Also, ideally this should remain entirely optional; nothing in the core kernel should depend on it.

I suspect Steve wants it for ftrace :-)

Quoted 9 lines · Paul E. McKenney

This series provides a prototype of an RCU-tasks implementation, which has been requested to assist with tramopoline removal. This flavor of RCU is task-based rather than CPU-based, and has voluntary context switch, usermode execution, and the idle loops as its only quiescent states. This selection of quiescent states ensures that at the end of a grace period, there will no longer be any tasks depending on a trampoline that was removed before the beginning of that grace period. This works because such trampolines do not contain function calls, do not contain voluntary context switches, do not switch to usermode, and do not switch to idle.

I'm concerned about the amount of system overhead this introduces. Polling for holdout tasks seems quite excessive. If I understand the intended use case correctly, the users of this will want to free relatively small amounts of memory; thus, waiting a while to do so seems fine, especially if the system isn't under any particular memory pressure.

Thus, rather than polling, could you simply flag the holdout tasks, telling the scheduler "hey, next time you don't have anything better to do..."? Then don't bother with them again unless the system runs low on memory and asks you to free some. (And mandate that you can only use this to free memory rather than for any other purpose.)

Also, ideally this should remain entirely optional; nothing in the core kernel should depend on it.

Quoted 18 lines · On Thu, Jul 31, 2014 at 09:19:02AM -0700, [email protected] wrote:

Quoted 9 lines · Paul E. McKenney

This series provides a prototype of an RCU-tasks implementation, which has been requested to assist with tramopoline removal. This flavor of RCU is task-based rather than CPU-based, and has voluntary context switch, usermode execution, and the idle loops as its only quiescent states. This selection of quiescent states ensures that at the end of a grace period, there will no longer be any tasks depending on a trampoline that was removed before the beginning of that grace period. This works because such trampolines do not contain function calls, do not contain voluntary context switches, do not switch to usermode, and do not switch to idle.

I'm concerned about the amount of system overhead this introduces. Polling for holdout tasks seems quite excessive. If I understand the intended use case correctly, the users of this will want to free relatively small amounts of memory; thus, waiting a while to do so seems fine, especially if the system isn't under any particular memory pressure.

Quoted 5 lines

Thus, rather than polling, could you simply flag the holdout tasks, telling the scheduler "hey, next time you don't have anything better to do..."? Then don't bother with them again unless the system runs low on memory and asks you to free some. (And mandate that you can only use this to free memory rather than for any other purpose.)

One of the many of my alternative suggestions that Steven rejected was to simply leak the memory. ;-)

But from what I can see, if we simply flag the holdout tasks, we either are also holding onto the task_struct structures, re-introducing concurrency to the list of holdout tasks, or requiring that the eventual scan for holdout tasks scan the entire task list. Neither of these seems particularly appetizing to me.

The nice thing about Lai Jiangshan's suggestion is that it allows the scan of the holdout list to be done completely unsynchronized, which allows pauses during the scan, thus allowing the loop to check for competing work on that CPU. This should get almost all the effect of indefinite delay without the indefinite delay (at least in the common case).

Or am I missing something here?

Quoted 2 lines

Also, ideally this should remain entirely optional; nothing in the core kernel should depend on it.

Agreed, the CONFIG_TASKS_RCU is not likely to disappear anytime soon. I therefore do not see RCU-tasks as an obstacle to kernel tinification. I also would also guess that you might complain if someone does try to use if from the tinified core of the Linux kernel. ;-)

Quoted 34 lines · Paul E. McKenney

Quoted 18 lines · On Thu, Jul 31, 2014 at 09:19:02AM -0700, [email protected] wrote:

Quoted 9 lines · Paul E. McKenney

This series provides a prototype of an RCU-tasks implementation, which has been requested to assist with tramopoline removal. This flavor of RCU is task-based rather than CPU-based, and has voluntary context switch, usermode execution, and the idle loops as its only quiescent states. This selection of quiescent states ensures that at the end of a grace period, there will no longer be any tasks depending on a trampoline that was removed before the beginning of that grace period. This works because such trampolines do not contain function calls, do not contain voluntary context switches, do not switch to usermode, and do not switch to idle.

I'm concerned about the amount of system overhead this introduces. Polling for holdout tasks seems quite excessive. If I understand the intended use case correctly, the users of this will want to free relatively small amounts of memory; thus, waiting a while to do so seems fine, especially if the system isn't under any particular memory pressure.

Quoted 5 lines

Thus, rather than polling, could you simply flag the holdout tasks, telling the scheduler "hey, next time you don't have anything better to do..."? Then don't bother with them again unless the system runs low on memory and asks you to free some. (And mandate that you can only use this to free memory rather than for any other purpose.)

One of the many of my alternative suggestions that Steven rejected was to simply leak the memory. ;-)

But from what I can see, if we simply flag the holdout tasks, we either are also holding onto the task_struct structures, re-introducing concurrency to the list of holdout tasks, or requiring that the eventual scan for holdout tasks scan the entire task list. Neither of these seems particularly appetizing to me.

Quoted 8 lines

The nice thing about Lai Jiangshan's suggestion is that it allows the scan of the holdout list to be done completely unsynchronized, which allows pauses during the scan, thus allowing the loop to check for competing work on that CPU. This should get almost all the effect of indefinite delay without the indefinite delay (at least in the common case).

Or am I missing something here?

If you only allow a single outstanding set of callbacks at a time, you could have a single flag stored in the task, combined with a count stored with the set of callbacks. Each time one of the holdout tasks comes up, clear the flag and decrement the count. If and only if you get asked to free up memory, start poking the scheduler to bring up those tasks. When the count hits 0, free the memory.

The set of trampolines won't change often, and presumably only changes in response to user-driven requests to trace or stop tracing things. So, if you have to wait for the existing set of callbacks to go away before adding more, that seems fine. And you could then ditch polling entirely.

Quoted 7 lines

Quoted 2 lines

Also, ideally this should remain entirely optional; nothing in the core kernel should depend on it.

Agreed, the CONFIG_TASKS_RCU is not likely to disappear anytime soon. I therefore do not see RCU-tasks as an obstacle to kernel tinification. I also would also guess that you might complain if someone does try to use if from the tinified core of the Linux kernel. ;-)

Yes. :)

Quoted 51 lines · On Thu, Jul 31, 2014 at 10:20:24AM -0700, [email protected] wrote:

Quoted 34 lines · Paul E. McKenney

Quoted 18 lines · On Thu, Jul 31, 2014 at 09:19:02AM -0700, [email protected] wrote:

Quoted 9 lines · Paul E. McKenney

This series provides a prototype of an RCU-tasks implementation, which has been requested to assist with tramopoline removal. This flavor of RCU is task-based rather than CPU-based, and has voluntary context switch, usermode execution, and the idle loops as its only quiescent states. This selection of quiescent states ensures that at the end of a grace period, there will no longer be any tasks depending on a trampoline that was removed before the beginning of that grace period. This works because such trampolines do not contain function calls, do not contain voluntary context switches, do not switch to usermode, and do not switch to idle.

I'm concerned about the amount of system overhead this introduces. Polling for holdout tasks seems quite excessive. If I understand the intended use case correctly, the users of this will want to free relatively small amounts of memory; thus, waiting a while to do so seems fine, especially if the system isn't under any particular memory pressure.

Quoted 5 lines

Thus, rather than polling, could you simply flag the holdout tasks, telling the scheduler "hey, next time you don't have anything better to do..."? Then don't bother with them again unless the system runs low on memory and asks you to free some. (And mandate that you can only use this to free memory rather than for any other purpose.)

One of the many of my alternative suggestions that Steven rejected was to simply leak the memory. ;-)

But from what I can see, if we simply flag the holdout tasks, we either are also holding onto the task_struct structures, re-introducing concurrency to the list of holdout tasks, or requiring that the eventual scan for holdout tasks scan the entire task list. Neither of these seems particularly appetizing to me.

Quoted 8 lines

The nice thing about Lai Jiangshan's suggestion is that it allows the scan of the holdout list to be done completely unsynchronized, which allows pauses during the scan, thus allowing the loop to check for competing work on that CPU. This should get almost all the effect of indefinite delay without the indefinite delay (at least in the common case).

Or am I missing something here?

If you only allow a single outstanding set of callbacks at a time, you could have a single flag stored in the task, combined with a count stored with the set of callbacks. Each time one of the holdout tasks comes up, clear the flag and decrement the count. If and only if you get asked to free up memory, start poking the scheduler to bring up those tasks. When the count hits 0, free the memory.

Quoted 5 lines

The set of trampolines won't change often, and presumably only changes in response to user-driven requests to trace or stop tracing things. So, if you have to wait for the existing set of callbacks to go away before adding more, that seems fine. And you could then ditch polling entirely.

If I understand what you are suggesting, this requires hooks in the scheduler. I used to have hooks in the scheduler, but I dropped them in favor of polling the voluntary context-switch count in response to Peter Zijlstra's concerns about adding overhead to the scheduler's fastpaths.

Therefore, although the flags are sometimes cleared externally from the scheduling-clock interrupt (for usermode execution), it is quite possible that a given task might never have its flag cleared asynchronously.

Another approach might be to poll more slowly or to make the polling evict itself if it detects that this CPU has something else to do. Would either or both of these help?

Quoted 63 lines · Paul E. McKenney

Quoted 51 lines · On Thu, Jul 31, 2014 at 10:20:24AM -0700, [email protected] wrote:

Quoted 34 lines · Paul E. McKenney

Quoted 18 lines · On Thu, Jul 31, 2014 at 09:19:02AM -0700, [email protected] wrote:

Quoted 9 lines · Paul E. McKenney

This series provides a prototype of an RCU-tasks implementation, which has been requested to assist with tramopoline removal. This flavor of RCU is task-based rather than CPU-based, and has voluntary context switch, usermode execution, and the idle loops as its only quiescent states. This selection of quiescent states ensures that at the end of a grace period, there will no longer be any tasks depending on a trampoline that was removed before the beginning of that grace period. This works because such trampolines do not contain function calls, do not contain voluntary context switches, do not switch to usermode, and do not switch to idle.

I'm concerned about the amount of system overhead this introduces. Polling for holdout tasks seems quite excessive. If I understand the intended use case correctly, the users of this will want to free relatively small amounts of memory; thus, waiting a while to do so seems fine, especially if the system isn't under any particular memory pressure.

Quoted 5 lines

Thus, rather than polling, could you simply flag the holdout tasks, telling the scheduler "hey, next time you don't have anything better to do..."? Then don't bother with them again unless the system runs low on memory and asks you to free some. (And mandate that you can only use this to free memory rather than for any other purpose.)

One of the many of my alternative suggestions that Steven rejected was to simply leak the memory. ;-)

But from what I can see, if we simply flag the holdout tasks, we either are also holding onto the task_struct structures, re-introducing concurrency to the list of holdout tasks, or requiring that the eventual scan for holdout tasks scan the entire task list. Neither of these seems particularly appetizing to me.

Quoted 8 lines

The nice thing about Lai Jiangshan's suggestion is that it allows the scan of the holdout list to be done completely unsynchronized, which allows pauses during the scan, thus allowing the loop to check for competing work on that CPU. This should get almost all the effect of indefinite delay without the indefinite delay (at least in the common case).

Or am I missing something here?

If you only allow a single outstanding set of callbacks at a time, you could have a single flag stored in the task, combined with a count stored with the set of callbacks. Each time one of the holdout tasks comes up, clear the flag and decrement the count. If and only if you get asked to free up memory, start poking the scheduler to bring up those tasks. When the count hits 0, free the memory.

Quoted 5 lines

The set of trampolines won't change often, and presumably only changes in response to user-driven requests to trace or stop tracing things. So, if you have to wait for the existing set of callbacks to go away before adding more, that seems fine. And you could then ditch polling entirely.

If I understand what you are suggesting, this requires hooks in the scheduler. I used to have hooks in the scheduler, but I dropped them in favor of polling the voluntary context-switch count in response to Peter Zijlstra's concerns about adding overhead to the scheduler's fastpaths.

Quoted 7 lines

Therefore, although the flags are sometimes cleared externally from the scheduling-clock interrupt (for usermode execution), it is quite possible that a given task might never have its flag cleared asynchronously.

Another approach might be to poll more slowly or to make the polling evict itself if it detects that this CPU has something else to do. Would either or both of these help?

As discussed at lunch today, another option would be to drop the thread and handle cleanup synchronously from the caller in the tracing code, or fire off a kthread *on request* to handle it asynchronously. That would avoid paying the startup and overhead on a system that has tracing in the kernel but never uses it, as will likely occur with distro kernels.

Hello!

This series provides a prototype of an RCU-tasks implementation, which has been requested to assist with tramopoline removal.

Quoted 4 lines · Paul E. McKenney

Hello!

This series provides a prototype of an RCU-tasks implementation, which has been requested to assist with tramopoline removal.

Is that trampoline removal (whatever it is) important enough to justify adding that much new (and complicated) code? Are there other potential users of this? Is the long term maintenance cost justified? Will RCU keep growing forever?