Use RCU to protect tasklist for unicast signals

RFC PATCH In review Paul E. McKenney 5 participants 10 messages Aug 10, 2005 – Aug 12, 2005

Subsystems (4)

VFS Scheduler exec and binfmt Proc filesystem

lore

Share & tools

lore

Paul E. McKenney

author

2005-08-10 17:11 UTC #0 lore raw

RFC PATCH 1/1 Use RCU to protect tasklist for unicast signals

Hello!

This patch is an experiment in use of RCU for individual code paths that read-acquire the tasklist lock, in this case, unicast signal delivery. It passes five kernbenches on 4-CPU x86, but obviously needs much more testing before it is considered for serious use, let alone inclusion.

My main question is whether I have the POSIX semantics covered. I believe that I do, but thought I should check with people who are more familiar with POSIX than am I.

For the record, some shortcomings of this patch:

o Needs lots more testing on more architectures.

o Needs performance and stress testing.

o Needs testing in Ingo's PREEMPT_RT environment.

o Uses cmpxchg(), which is currently architecture dependent.
This can be fixed, for example, by using the hashed locks proposed in an earlier patch from Dipankar:

http://marc.theaimsgroup.com/?l=linux-kernel&m=111875978502912&w=2

Thoughts?

Thanx, Paul

---

Not-signed-off-by [email protected]

 include/linux/sched.h |   27 +++++++++++++++++++++++++--
 kernel/sched.c        |    5 +++++
 kernel/signal.c       |    8 ++++++--
 3 files changed, 36 insertions(+), 4 deletions(-)

include/linux/sched.h +25 -2

diff -urpN -X dontdiff linux-2.6.13-rc6/include/linux/sched.h linux-2.6.13-rc6-tasklistRCU/include/linux/sched.h
@@ -34,6 +34,7 @@
 #include <linux/percpu.h>
 #include <linux/topology.h>
 #include <linux/seccomp.h>
+#include <linux/rcupdate.h>
 
 struct exec_domain;

@@ -770,6 +771,7 @@ struct task_struct {
 	int cpuset_mems_generation;
 #endif
 	atomic_t fs_excl;	/* holding fs exclusive resources */
+	struct rcu_head rcu;
 };
 
 static inline pid_t process_group(struct task_struct *tsk)

@@ -793,8 +795,29 @@ static inline int pid_alive(struct task_
 extern void free_task(struct task_struct *tsk);
 extern void __put_task_struct(struct task_struct *tsk);
 #define get_task_struct(tsk) do { atomic_inc(&(tsk)->usage); } while(0)
-#define put_task_struct(tsk) \
-do { if (atomic_dec_and_test(&(tsk)->usage)) __put_task_struct(tsk); } while(0)
+
+static inline int get_task_struct_rcu(struct task_struct *t)
+{
+	int oldusage;
+
+	do {
+		oldusage = atomic_read(&t->usage);
+		if (oldusage == 0) {
+			return 0;
+		}
+	} while (cmpxchg(&t->usage.counter,
+		 oldusage, oldusage + 1) != oldusage);
+	return 1;
+}
+
+extern void __put_task_struct_cb(struct rcu_head *rhp);
+
+static inline void put_task_struct(struct task_struct *t)
+{
+	if (atomic_dec_and_test(&t->usage)) {
+		call_rcu(&t->rcu, __put_task_struct_cb);
+	}
+}
 
 /*
  * Per process flags

kernel/sched.c +5 -0

diff -urpN -X dontdiff linux-2.6.13-rc6/kernel/sched.c linux-2.6.13-rc6-tasklistRCU/kernel/sched.c
@@ -176,6 +176,11 @@ static unsigned int task_timeslice(task_
 #define task_hot(p, now, sd) ((long long) ((now) - (p)->last_ran)	\
 				< (long long) (sd)->cache_hot_time)
 
+void __put_task_struct_cb(struct rcu_head *rhp)
+{
+	__put_task_struct(container_of(rhp, struct task_struct, rcu));
+}
+
 /*
  * These are the runqueue data structures:
  */

kernel/signal.c +6 -2

diff -urpN -X dontdiff linux-2.6.13-rc6/kernel/signal.c linux-2.6.13-rc6-tasklistRCU/kernel/signal.c
@@ -1151,9 +1151,13 @@ int group_send_sig_info(int sig, struct 
 
 	ret = check_kill_permission(sig, info, p);
 	if (!ret && sig && p->sighand) {
+		if (!get_task_struct_rcu(p)) {
+			return -ESRCH;
+		}
 		spin_lock_irqsave(&p->sighand->siglock, flags);
 		ret = __group_send_sig_info(sig, info, p);
 		spin_unlock_irqrestore(&p->sighand->siglock, flags);
+		put_task_struct(p);
 	}
 
 	return ret;

@@ -1200,12 +1204,12 @@ kill_proc_info(int sig, struct siginfo *
 	int error;
 	struct task_struct *p;
 
-	read_lock(&tasklist_lock);
+	rcu_read_lock();
 	p = find_task_by_pid(pid);
 	error = -ESRCH;
 	if (p)
 		error = group_send_sig_info(sig, info, p);
-	read_unlock(&tasklist_lock);
+	rcu_read_unlock();
 	return error;
 }

Ingo Molnar

2005-08-11 09:56 UTC #1 lore raw

Quoted 12 lines · Paul E. McKenney

Hello!
This patch is an experiment in use of RCU for individual code paths that read-acquire the tasklist lock, in this case, unicast signal delivery. It passes five kernbenches on 4-CPU x86, but obviously needs much more testing before it is considered for serious use, let alone inclusion.
My main question is whether I have the POSIX semantics covered. I believe that I do, but thought I should check with people who are more familiar with POSIX than am I.

Quoted 7 lines

For the record, some shortcomings of this patch:
o Needs lots more testing on more architectures.
o Needs performance and stress testing.
o Needs testing in Ingo's PREEMPT_RT environment.

cool patch! I have integrated it into my PREEMPT_RT tree, and all it needed to boot was the patch below (doesnt affect the upstream kernel). Using the raw IRQ flag isnt an issue in the RCU code, all the affected codepaths are small and deterministic.

(without this patch it locked up after detecting IRQ7 - not sure why.)

kernel still works fine after some (mostly light) testing.

Ingo

kernel/rcupdate.c +9 -9

Index: linux/kernel/rcupdate.c
===================================================================
@@ -134,11 +134,11 @@ void fastcall call_rcu(struct rcu_head *
 
 	head->func = func;
 	head->next = NULL;
-	local_irq_save(flags);
+	raw_local_irq_save(flags);
 	rdp = &__get_cpu_var(rcu_data);
 	*rdp->nxttail = head;
 	rdp->nxttail = &head->next;
-	local_irq_restore(flags);
+	raw_local_irq_restore(flags);
 }
 
 /**

@@ -165,11 +165,11 @@ void fastcall call_rcu_bh(struct rcu_hea
 
 	head->func = func;
 	head->next = NULL;
-	local_irq_save(flags);
+	raw_local_irq_save(flags);
 	rdp = &__get_cpu_var(rcu_bh_data);
 	*rdp->nxttail = head;
 	rdp->nxttail = &head->next;
-	local_irq_restore(flags);
+	raw_local_irq_restore(flags);
 }
 
 /*

@@ -305,11 +305,11 @@ static void rcu_check_quiescent_state(st
 static void rcu_move_batch(struct rcu_data *this_rdp, struct rcu_head *list,
 				struct rcu_head **tail)
 {
-	local_irq_disable();
+	raw_local_irq_disable();
 	*this_rdp->nxttail = list;
 	if (list)
 		this_rdp->nxttail = tail;
-	local_irq_enable();
+	raw_local_irq_enable();
 }
 
 static void __rcu_offline_cpu(struct rcu_data *this_rdp,

@@ -362,13 +362,13 @@ static void __rcu_process_callbacks(stru
 		rdp->curtail = &rdp->curlist;
 	}
 
-	local_irq_disable();
+	raw_local_irq_disable();
 	if (rdp->nxtlist && !rdp->curlist) {
 		rdp->curlist = rdp->nxtlist;
 		rdp->curtail = rdp->nxttail;
 		rdp->nxtlist = NULL;
 		rdp->nxttail = &rdp->nxtlist;
-		local_irq_enable();
+		raw_local_irq_enable();
 
 		/*
 		 * start the next batch of callbacks

@@ -388,7 +388,7 @@ static void __rcu_process_callbacks(stru
 			spin_unlock(&rsp->lock);
 		}
 	} else {
-		local_irq_enable();
+		raw_local_irq_enable();
 	}
 	rcu_check_quiescent_state(rcp, rsp, rdp);
 	if (rdp->donelist)

Paul E. McKenney

author

2005-08-11 14:14 UTC #2 lore raw

Quoted 21 lines · Ingo Molnar

Quoted 18 lines · Paul E. McKenney
Hello!
This patch is an experiment in use of RCU for individual code paths that read-acquire the tasklist lock, in this case, unicast signal delivery. It passes five kernbenches on 4-CPU x86, but obviously needs much more testing before it is considered for serious use, let alone inclusion.
My main question is whether I have the POSIX semantics covered. I believe that I do, but thought I should check with people who are more familiar with POSIX than am I.
For the record, some shortcomings of this patch:
o Needs lots more testing on more architectures.
o Needs performance and stress testing.

Quoted 8 lines

Quoted 1 line
o Needs testing in Ingo's PREEMPT_RT environment.
cool patch! I have integrated it into my PREEMPT_RT tree, and all it needed to boot was the patch below (doesnt affect the upstream kernel). Using the raw IRQ flag isnt an issue in the RCU code, all the affected codepaths are small and deterministic.
(without this patch it locked up after detecting IRQ7 - not sure why.)

Without this patch on an older version of PREEMPT_RT (V0.7.52-12), it would boot, pass kernbench, but fail LTP. Passed both on a stock kernel.

Will re-run with your patch. ;-)

Quoted 1 line

kernel still works fine after some (mostly light) testing.

Cool! Next step for me is to run some focussed stress tests.

Thanx, Paul

Quoted 74 lines

Ingo

Index: linux/kernel/rcupdate.c
===================================================================

kernel/rcupdate.c +9 -9

@@ -134,11 +134,11 @@ void fastcall call_rcu(struct rcu_head *
 
 	head->func = func;
 	head->next = NULL;
-	local_irq_save(flags);
+	raw_local_irq_save(flags);
 	rdp = &__get_cpu_var(rcu_data);
 	*rdp->nxttail = head;
 	rdp->nxttail = &head->next;
-	local_irq_restore(flags);
+	raw_local_irq_restore(flags);
 }
 
 /**

@@ -165,11 +165,11 @@ void fastcall call_rcu_bh(struct rcu_hea
 
 	head->func = func;
 	head->next = NULL;
-	local_irq_save(flags);
+	raw_local_irq_save(flags);
 	rdp = &__get_cpu_var(rcu_bh_data);
 	*rdp->nxttail = head;
 	rdp->nxttail = &head->next;
-	local_irq_restore(flags);
+	raw_local_irq_restore(flags);
 }
 
 /*

@@ -305,11 +305,11 @@ static void rcu_check_quiescent_state(st
 static void rcu_move_batch(struct rcu_data *this_rdp, struct rcu_head *list,
 				struct rcu_head **tail)
 {
-	local_irq_disable();
+	raw_local_irq_disable();
 	*this_rdp->nxttail = list;
 	if (list)
 		this_rdp->nxttail = tail;
-	local_irq_enable();
+	raw_local_irq_enable();
 }
 
 static void __rcu_offline_cpu(struct rcu_data *this_rdp,

@@ -362,13 +362,13 @@ static void __rcu_process_callbacks(stru
 		rdp->curtail = &rdp->curlist;
 	}
 
-	local_irq_disable();
+	raw_local_irq_disable();
 	if (rdp->nxtlist && !rdp->curlist) {
 		rdp->curlist = rdp->nxtlist;
 		rdp->curtail = rdp->nxttail;
 		rdp->nxtlist = NULL;
 		rdp->nxttail = &rdp->nxtlist;
-		local_irq_enable();
+		raw_local_irq_enable();
 
 		/*
 		 * start the next batch of callbacks

@@ -388,7 +388,7 @@ static void __rcu_process_callbacks(stru
 			spin_unlock(&rsp->lock);
 		}
 	} else {
-		local_irq_enable();
+		raw_local_irq_enable();
 	}
 	rcu_check_quiescent_state(rcp, rsp, rdp);
 	if (rdp->donelist)

Lee Revell

2005-08-12 02:01 UTC #3 lore raw

In reply to Ingo Molnar

Quoted 4 lines · Ingo Molnar

Quoted 4 lines
For the record, some shortcomings of this patch:
o Needs lots more testing on more architectures.

Quoted 9 lines

Quoted 3 lines
o Needs performance and stress testing.
o Needs testing in Ingo's PREEMPT_RT environment.
cool patch! I have integrated it into my PREEMPT_RT tree, and all it needed to boot was the patch below (doesnt affect the upstream kernel). Using the raw IRQ flag isnt an issue in the RCU code, all the affected codepaths are small and deterministic.

Ingo,

Doesn't this fix the longest latency we were seeing with PREEMPT_DESKTOP, I don't have a trace handy but the upshot was "signal delivery must remain atomic on !PREEMPT_RT"?

Lee

Ingo Molnar

2005-08-12 06:35 UTC #4 lore raw

Quoted 3 lines · Lee Revell

Doesn't this fix the longest latency we were seeing with PREEMPT_DESKTOP, I don't have a trace handy but the upshot was "signal delivery must remain atomic on !PREEMPT_RT"?

yes - although Paul's patch converts only a portion of the signal code to RCU-read-lock, so i'd expect there to be other latencies too. Might be worth a test (once we've sorted out the HRT build bugs).

Ingo

Paul E. McKenney

author

2005-08-12 20:57 UTC #5 lore raw

Quoted 10 lines · Ingo Molnar

Quoted 3 lines · Lee Revell
Doesn't this fix the longest latency we were seeing with PREEMPT_DESKTOP, I don't have a trace handy but the upshot was "signal delivery must remain atomic on !PREEMPT_RT"?
yes - although Paul's patch converts only a portion of the signal code to RCU-read-lock, so i'd expect there to be other latencies too. Might be worth a test (once we've sorted out the HRT build bugs).

And there remains the question of how much of the benefit remains after I handle the corner cases... :-/

Thanx, Paul

Christoph Hellwig

2005-08-11 17:14 UTC #6 lore raw

In reply to Paul E. McKenney

Quoted 6 lines · Paul E. McKenney

Hello!
This patch is an experiment in use of RCU for individual code paths that read-acquire the tasklist lock, in this case, unicast signal delivery. It passes five kernbenches on 4-CPU x86, but obviously needs much more testing before it is considered for serious use, let alone inclusion.

I think we should switch over tasklist_lock to RCU completely instead of adding suck hacks. I've started lots of preparation work to get rid of tasklist_lock users outside of kernel/, especialy getting rid of any use in modules.

Paul E. McKenney

author

2005-08-11 17:56 UTC #7 lore raw

Quoted 8 lines · Christoph Hellwig

Quoted 6 lines · Paul E. McKenney
Hello!
This patch is an experiment in use of RCU for individual code paths that read-acquire the tasklist lock, in this case, unicast signal delivery. It passes five kernbenches on 4-CPU x86, but obviously needs much more testing before it is considered for serious use, let alone inclusion.

Quoted 4 lines

I think we should switch over tasklist_lock to RCU completely instead of adding suck hacks. I've started lots of preparation work to get rid of tasklist_lock users outside of kernel/, especialy getting rid of any use in modules.

I agree fully with your end goal -- I would certainly look funny disagreeing, right? ;-) And Oleg pointed out an area I missed in my patch, am fixing, but in the meantime it most certainly does qualify as a suck hack. :-/ Working on it...

But one of the cool things about RCU is that we can make this change incrementally, with a series of small patches. We can have some of the read paths protected by RCU and others continuing to be protected by read_lock(), so that we can avoid the need for a "flag day" that hits all 300+ uses of tasklist_lock.

FWIW, the approach that I am taking to fix the bug Oleg and Christoph spotted is roughly as follows:

o Add "struct rcu_head rcu", "struct sighand_struct *successor",
and "int deleted" to struct sighand_struct. This allows reliable signal delivery in face of sighand_struct replacements. If an RCU reader finds (deleted && !successor), that reader is trying to signal a dying process, so gives up. If an RCU reader instead finds (deleted && successor), the reader traverses the successor pointer to find the current version.

o Apply call_rcu() to deletion of struct sighand_struct, with
the exception of a couple of failure paths in exec.c, where the sighand_struct was never exposed to RCU readers.

Thoughts?

Thanx, Paul

Dipankar Sarma

2005-08-11 18:05 UTC #8 lore raw

In reply to Christoph Hellwig

Quoted 8 lines · Christoph Hellwig

Quoted 6 lines · Paul E. McKenney
Hello!
This patch is an experiment in use of RCU for individual code paths that read-acquire the tasklist lock, in this case, unicast signal delivery. It passes five kernbenches on 4-CPU x86, but obviously needs much more testing before it is considered for serious use, let alone inclusion.

Quoted 4 lines

I think we should switch over tasklist_lock to RCU completely instead of adding suck hacks. I've started lots of preparation work to get rid of tasklist_lock users outside of kernel/, especialy getting rid of any use in modules.

That would be really helpful, specially the ones in drivers/char/tty*.c :)

When I worked on this last (a year or so ago), it seemed that I would need to put a number of additional structures under RCU control. It would be better to gradually move it towards RCU rather than trying make all the readers lock-free.

Thanks
Dipankar

Dipankar Sarma

2005-08-11 18:16 UTC #9 lore raw

Quoted 4 lines · Dipankar Sarma

When I worked on this last (a year or so ago), it seemed that I would need to put a number of additional structures under RCU control. It would be better to gradually move it towards RCU rather than trying make all the readers lock-free.

Just for reference, this was my tasks-rcu patch. 2.6.0-test2, no less :) I was interested in get_pid_list() at that time. IIRC, I tested it with lots of top running along with other tests.

Thanks
Dipankar

Incremental patch to do lockfree traversal of the task list using RCU. For now it just does one of the costlies ones in /proc.

Signed-off-by Dipankar Sarma <[email protected]>

 fs/exec.c             |    1 +
 fs/proc/base.c        |    5 +++--
 include/linux/sched.h |   21 ++++++++++++++++-----
 3 files changed, 20 insertions(+), 7 deletions(-)

fs/exec.c renamed from fs/exec.c~tasks-rcu +1 -0

diff -puN fs/exec.c~tasks-rcu fs/exec.c
@@ -676,6 +676,7 @@ static inline int de_thread(struct task_
 
 		list_del(&current->tasks);
 		list_add_tail(&current->tasks, &init_task.tasks);
+		list_add_tail_rcu(&current->tasks, &init_task.tasks);
 		current->exit_signal = SIGCHLD;
 		state = leader->state;

fs/proc/base.c renamed from fs/proc/base.c~tasks-rcu +3 -2

diff -puN fs/proc/base.c~tasks-rcu fs/proc/base.c
@@ -32,6 +32,7 @@
 #include <linux/mount.h>
 #include <linux/security.h>
 #include <linux/ptrace.h>
+#include <linux/rcupdate.h>
 
 /*
  * For hysterical raisins we keep the same inumbers as in the old procfs.

@@ -1403,7 +1404,7 @@ static int get_pid_list(int index, unsig
 	int nr_pids = 0;
 
 	index--;
-	read_lock(&tasklist_lock);
+	rcu_read_lock();
 	for_each_process(p) {
 		int pid = p->pid;
 		if (!pid_alive(p))

@@ -1415,7 +1416,7 @@ static int get_pid_list(int index, unsig
 		if (nr_pids >= PROC_MAXPIDS)
 			break;
 	}
-	read_unlock(&tasklist_lock);
+	rcu_read_unlock();
 	return nr_pids;
 }

include/linux/sched.h renamed from include/linux/sched.h~tasks-rcu +16 -5

diff -puN include/linux/sched.h~tasks-rcu include/linux/sched.h
@@ -28,6 +28,7 @@
 #include <linux/completion.h>
 #include <linux/pid.h>
 #include <linux/percpu.h>
+#include <linux/rcupdate.h>
 
 struct exec_domain;

@@ -456,13 +457,23 @@ struct task_struct {
 	struct io_context *io_context;
 
 	unsigned long ptrace_message;
+	struct rcu_head rcu;
 	siginfo_t *last_siginfo; /* For ptrace use.  */
 };
 
 extern void __put_task_struct(struct task_struct *tsk);
 #define get_task_struct(tsk) do { atomic_inc(&(tsk)->usage); } while(0)
-#define put_task_struct(tsk) \
-do { if (atomic_dec_and_test(&(tsk)->usage)) __put_task_struct(tsk); } while(0)
+static void put_task_struct_rcu(struct rcu_head *rcu)
+{
+	struct task_struct *tsk = container_of(rcu, struct task_struct, rcu);
+	__put_task_struct(tsk);
+}
+static inline void put_task_struct(struct task_struct *tsk)
+{
+	if (atomic_dec_and_test(&tsk->usage))
+		call_rcu(&tsk->rcu, put_task_struct_rcu);
+}
+
 
 /*
  * Per process flags

@@ -675,13 +686,13 @@ extern void wait_task_inactive(task_t * 
 
 #define REMOVE_LINKS(p) do {					\
 	if (thread_group_leader(p))				\
-		list_del_init(&(p)->tasks);			\
+		list_del_rcu(&(p)->tasks);			\
 	remove_parent(p);					\
 	} while (0)
 
 #define SET_LINKS(p) do {					\
 	if (thread_group_leader(p))				\
-		list_add_tail(&(p)->tasks,&init_task.tasks);	\
+		list_add_tail_rcu(&(p)->tasks,&init_task.tasks);	\
 	add_parent(p, (p)->parent);				\
 	} while (0)

@@ -689,7 +700,7 @@ extern void wait_task_inactive(task_t * 
 #define prev_task(p)	list_entry((p)->tasks.prev, struct task_struct, tasks)
 
 #define for_each_process(p) \
-	for (p = &init_task ; (p = next_task(p)) != &init_task ; )
+	for (p = &init_task ; (p = next_task(p)),({ read_barrier_depends(); 0;}),p != &init_task ; )
 
 /*
  * Careful: do_each_thread/while_each_thread is a double loop so