RCUify single-thread case of clock_gettime()

RFC PATCH In review Paul E. McKenney 4 participants 7 messages Oct 31, 2005

Subsystems (4)

VFS MM core Scheduler exec and binfmt

lore

Share & tools

lore

Paul E. McKenney

author

2005-10-31 17:44 UTC #0 lore raw

RFC PATCH 1/1 RCUify single-thread case of clock_gettime()

Hello!

The attached patch uses RCU to avoid the need to acquire tasklist_lock in the single-thread case of clock_gettime(). Still acquires tasklist_lock when asking for the time of a (potentially multithreaded) process.

Experimental, has been touch-tested on x86 and POWER. Requires RCU on task_struct. Further more focused testing in progress.

Thoughts? (Why? Some off-list users want to be able to monitor CPU consumption of specific threads. They need to do so quite frequently, so acquiring tasklist_lock is inappropriate.)

Thanx, Paul

kernel/posix-cpu-timers.c +4 -2

diff -urpNa -X dontdiff linux-2.6.14-rc5-rt2/kernel/posix-cpu-timers.c linux-2.6.14-rc5-rt2-RCUgettime/kernel/posix-cpu-timers.c
@@ -302,7 +302,7 @@ int posix_cpu_clock_get(clockid_t which_
 		 * should be able to see it.
 		 */
 		struct task_struct *p;
-		read_lock(&tasklist_lock);
+		rcu_read_lock();
 		p = find_task_by_pid(pid);
 		if (p) {
 			if (CPUCLOCK_PERTHREAD(which_clock)) {

@@ -311,11 +311,13 @@ int posix_cpu_clock_get(clockid_t which_
 								 p, &rtn);
 				}
 			} else if (p->tgid == pid && p->signal) {
+				read_lock(&tasklist_lock);
 				error = cpu_clock_sample_group(which_clock,
 							       p, &rtn);
+				read_unlock(&tasklist_lock);
 			}
 		}
-		read_unlock(&tasklist_lock);
+		rcu_read_unlock();
 	}
 
 	if (error)

Hugh Dickins

2005-10-31 18:09 UTC #1 lore raw

Quoted 11 lines · Paul E. McKenney

The attached patch uses RCU to avoid the need to acquire tasklist_lock in the single-thread case of clock_gettime(). Still acquires tasklist_lock when asking for the time of a (potentially multithreaded) process.
Experimental, has been touch-tested on x86 and POWER. Requires RCU on task_struct. Further more focused testing in progress.
Thoughts? (Why? Some off-list users want to be able to monitor CPU consumption of specific threads. They need to do so quite frequently, so acquiring tasklist_lock is inappropriate.)

Not my area at all, but this looks really dodgy to me, Paul:
could you explain it further?

First off, I don't see what's "RCU" about it at all. Essentially, you're replacing read_lock(&tasklist_lock) by preempt_disable(), but calling it by the fancier rcu_read_lock() alias. I thought there would need to be some more infrastructure to make this RCU and safe?

Hugh

Ingo Molnar

2005-10-31 19:54 UTC #2 lore raw

Quoted 13 lines · Hugh Dickins

Quoted 11 lines · Paul E. McKenney
The attached patch uses RCU to avoid the need to acquire tasklist_lock in the single-thread case of clock_gettime(). Still acquires tasklist_lock when asking for the time of a (potentially multithreaded) process.
Experimental, has been touch-tested on x86 and POWER. Requires RCU on task_struct. Further more focused testing in progress.
Thoughts? (Why? Some off-list users want to be able to monitor CPU consumption of specific threads. They need to do so quite frequently, so acquiring tasklist_lock is inappropriate.)

Quoted 7 lines

Not my area at all, but this looks really dodgy to me, Paul:
could you explain it further?
First off, I don't see what's "RCU" about it at all. Essentially, you're replacing read_lock(&tasklist_lock) by preempt_disable(), but calling it by the fancier rcu_read_lock() alias. I thought there would need to be some more infrastructure to make this RCU and safe?

the patch below (included in the -rt tree) is the prerequisite. That's what Paul's "requires RCU on task_struct" comment refers to.

the point of RCU here is SMP scalability from one side:
preempt_disable() only has effect on the current CPU, while the tasklist_lock is a globally bouncing lock.

secondly, with the PREEMPT_RCU feature enabled (also included in the -rt tree), all rcu_read_lock() sections become fully preemptible.

Ingo

----

RCU tasklist_lock and RCU signal handling: send signals RCU-read-locked instead of tasklist_lock read-locked. This is a scalability improvement on SMP and a preemption-latency improvement under PREEMPT_RCU.

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

Signed-off-by Ingo Molnar <[email protected]>

include/linux/sched.h +33 -2

Index: linux/include/linux/sched.h
===================================================================
@@ -34,6 +34,7 @@
 #include <linux/percpu.h>
 #include <linux/topology.h>
 #include <linux/seccomp.h>
+#include <linux/rcupdate.h>
 
 #include <linux/auxvec.h>	/* For AT_VECTOR_SIZE */

@@ -408,8 +409,16 @@ struct sighand_struct {
 	atomic_t		count;
 	struct k_sigaction	action[_NSIG];
 	spinlock_t		siglock;
+	struct rcu_head		rcu;
 };
 
+static inline void sighand_free(struct sighand_struct *sp)
+{
+	extern void sighand_free_cb(struct rcu_head *rhp);
+
+	call_rcu(&sp->rcu, sighand_free_cb);
+}
+
 /*
  * NOTE! "signal_struct" does not have it's own
  * locking, because a shared signal_struct always

@@ -913,6 +922,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)

@@ -936,8 +946,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 +7 -0

Index: linux/kernel/sched.c
===================================================================
@@ -176,6 +176,13 @@ 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));
+}
+
+EXPORT_SYMBOL_GPL(__put_task_struct_cb);
+
 /*
  * These are the runqueue data structures:
  */

kernel/signal.c +77 ~~-15~~

184 lines not on this page · raw message

fs/exec.c +1 -1

Index: linux/fs/exec.c
===================================================================
@@ -779,7 +779,7 @@ no_thread_group:
 		write_unlock_irq(&tasklist_lock);
 
 		if (atomic_dec_and_test(&oldsighand->count))
-			kmem_cache_free(sighand_cachep, oldsighand);
+			sighand_free(oldsighand);
 	}
 
 	BUG_ON(!thread_group_leader(current));

kernel/exit.c +0 -1

Index: linux/kernel/exit.c
===================================================================
@@ -71,7 +71,6 @@ repeat: 
 		__ptrace_unlink(p);
 	BUG_ON(!list_empty(&p->ptrace_list) || !list_empty(&p->ptrace_children));
 	__exit_signal(p);
-	__exit_sighand(p);
 	/*
 	 * Note that the fastpath in sys_times depends on __exit_signal having
 	 * updated the counters before a task is removed from the tasklist of

kernel/fork.c +8 -0

Index: linux/kernel/fork.c
===================================================================
@@ -754,6 +754,14 @@ int unshare_files(void)
 
 EXPORT_SYMBOL(unshare_files);
 
+void sighand_free_cb(struct rcu_head *rhp)
+{
+	struct sighand_struct *sp =
+		container_of(rhp, struct sighand_struct, rcu);
+
+	kmem_cache_free(sighand_cachep, sp);
+}
+
 static inline int copy_sighand(unsigned long clone_flags, struct task_struct * tsk)
 {
 	struct sighand_struct *sig;

kernel/rcupdate.c +1 -0

Index: linux/kernel/rcupdate.c
===================================================================
@@ -35,6 +35,7 @@
 #include <linux/init.h>
 #include <linux/spinlock.h>
 #include <linux/smp.h>
+#include <linux/rcupdate.h>
 #include <linux/interrupt.h>
 #include <linux/sched.h>
 #include <asm/atomic.h>

include/linux/list.h +20 -0

Index: linux/include/linux/list.h
===================================================================
@@ -208,6 +208,7 @@ static inline void list_replace_rcu(stru
 	smp_wmb();
 	new->next->prev = new;
 	new->prev->next = new;
+	old->prev = LIST_POISON2;
 }
 
 /**

@@ -578,6 +579,25 @@ static inline void hlist_del_init(struct
 	}
 }
 
+/*
+ * hlist_replace_rcu - replace old entry by new one
+ * @old : the element to be replaced
+ * @new : the new element to insert
+ *
+ * The old entry will be replaced with the new entry atomically.
+ */
+static inline void hlist_replace_rcu(struct hlist_node *old, struct hlist_node *new){
+	struct hlist_node *next = old->next;
+
+	new->next = next;
+	new->pprev = old->pprev;
+	smp_wmb();
+	if (next)
+		new->next->pprev = &new->next;
+	*new->pprev = new;
+	old->pprev = LIST_POISON2;
+}
+
 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
 {
 	struct hlist_node *first = h->first;

kernel/pid.c +10 ~~-10~~

Index: linux/kernel/pid.c
===================================================================
@@ -136,7 +136,7 @@ struct pid * fastcall find_pid(enum pid_
 	struct hlist_node *elem;
 	struct pid *pid;
 
-	hlist_for_each_entry(pid, elem,
+	hlist_for_each_entry_rcu(pid, elem,
 			&pid_hash[type][pid_hashfn(nr)], pid_chain) {
 		if (pid->nr == nr)
 			return pid;

@@ -151,12 +151,12 @@ int fastcall attach_pid(task_t *task, en
 	task_pid = &task->pids[type];
 	pid = find_pid(type, nr);
 	if (pid == NULL) {
-		hlist_add_head(&task_pid->pid_chain,
-				&pid_hash[type][pid_hashfn(nr)]);
 		INIT_LIST_HEAD(&task_pid->pid_list);
+		hlist_add_head_rcu(&task_pid->pid_chain,
+				   &pid_hash[type][pid_hashfn(nr)]);
 	} else {
 		INIT_HLIST_NODE(&task_pid->pid_chain);
-		list_add_tail(&task_pid->pid_list, &pid->pid_list);
+		list_add_tail_rcu(&task_pid->pid_list, &pid->pid_list);
 	}
 	task_pid->nr = nr;

@@ -170,20 +170,20 @@ static fastcall int __detach_pid(task_t 
 
 	pid = &task->pids[type];
 	if (!hlist_unhashed(&pid->pid_chain)) {
-		hlist_del(&pid->pid_chain);
 
-		if (list_empty(&pid->pid_list))
+		if (list_empty(&pid->pid_list)) {
 			nr = pid->nr;
-		else {
+			hlist_del_rcu(&pid->pid_chain);
+		} else {
 			pid_next = list_entry(pid->pid_list.next,
 						struct pid, pid_list);
 			/* insert next pid from pid_list to hash */
-			hlist_add_head(&pid_next->pid_chain,
-				&pid_hash[type][pid_hashfn(pid_next->nr)]);
+			hlist_replace_rcu(&pid->pid_chain,
+					  &pid_next->pid_chain);
 		}
 	}
 
-	list_del(&pid->pid_list);
+	list_del_rcu(&pid->pid_list);
 	pid->nr = 0;
 
 	return nr;

Hugh Dickins

2005-10-31 20:08 UTC #3 lore raw

Quoted 7 lines · Ingo Molnar

Quoted 3 lines · Hugh Dickins
Not my area at all, but this looks really dodgy to me, Paul:
could you explain it further?
the patch below (included in the -rt tree) is the prerequisite. That's what Paul's "requires RCU on task_struct" comment refers to.

Thanks, Ingo: Sorry, Paul: I missed that it was an -rt patch: Ignore me.

Hugh

Ingo Molnar

2005-10-31 21:50 UTC #4 lore raw

Quoted 11 lines · Hugh Dickins

Quoted 7 lines · Ingo Molnar
Quoted 3 lines · Hugh Dickins
Not my area at all, but this looks really dodgy to me, Paul:
could you explain it further?
the patch below (included in the -rt tree) is the prerequisite. That's what Paul's "requires RCU on task_struct" comment refers to.
Thanks, Ingo: Sorry, Paul: I missed that it was an -rt patch: Ignore me.

btw., since the RCU-task-struct thing is beneficial to upstream SMP kernels (even without any preempt option enabled), it should be considered for upstream too. The tasklist_lock is one of our last remaining monolithic and globally-bouncing locks. The patch i attached to the previous mail is against the upstream kernel and implements the RCU-task-struct logic, without any PREEMPT_RT dependency. (the -rt tree is a collection of various preemption related patches, not just PREEMPT_RT)

Ingo

Joe Seigh

2005-10-31 19:40 UTC #5 lore raw

In reply to Paul E. McKenney

Quoted 6 lines · Paul E. McKenney

Hello!
The attached patch uses RCU to avoid the need to acquire tasklist_lock in the single-thread case of clock_gettime(). Still acquires tasklist_lock when asking for the time of a (potentially multithreaded) process.

Quoted 6 lines

Experimental, has been touch-tested on x86 and POWER. Requires RCU on task_struct. Further more focused testing in progress.
Thoughts? (Why? Some off-list users want to be able to monitor CPU consumption of specific threads. They need to do so quite frequently, so acquiring tasklist_lock is inappropriate.)

I'd like to see the time the thread is dispatched put into a read only memory segment along with a virtual timer and real timer offsets. The thread gets the read or virtual time by reading the virtual offset, reading the real clock (whatever that is), rereading the virtual offset, and if that hasn't changed, getting the desired timer value by adding the appropiate offset. No kernel entanglements required. This is an old trick VM used to support virtual timers for MVS.

And while we're at it, throw in the rest of the thread usage stats.

The use of mapped memory segments to avoid syscalls is a good idea. relayfs has already established that precedent. relayfs only handles circular producer/consumer queues but you could use RCU for preeemptive user threads or RCU+SMR for other data structures in mapped memory managed by the kernel or another process even.

--
Joe Seigh

Ingo Molnar

2005-10-31 21:44 UTC #6 lore raw

In reply to Paul E. McKenney

Quoted 7 lines · Paul E. McKenney

Hello!
The attached patch uses RCU to avoid the need to acquire tasklist_lock in the single-thread case of clock_gettime(). Still acquires tasklist_lock when asking for the time of a (potentially multithreaded) process.

Quoted 6 lines

Experimental, has been touch-tested on x86 and POWER. Requires RCU on task_struct. Further more focused testing in progress.
Thoughts? (Why? Some off-list users want to be able to monitor CPU consumption of specific threads. They need to do so quite frequently, so acquiring tasklist_lock is inappropriate.)

looks good to me - i have added this to the -rt tree, it should show up in 2.6.14-rt3.

Ingo