[patch] kwaitd, 2.5.31-A1

[patch] kwaitd, 2.5.31-A1

[Ingo Molnar]

the attached patch is the other half of making pthread_exit() a
single-syscall, low-overhead matter.

it implements a new clone flag, CLONE_DETACHED, over which the parent can
tell the kernel that it's not interested in parent notification signals.  
(new pthreads now does any such potential notification via the much lower
overhead futexes.)

(my first choice, 'exit notification signal 0' is an already existing
semantic detail that is being use by kmod and perhaps by userspace code as
well, so it had to be a clone flag. Besides, signal 0 notification still
creates some signal handling related overhead, which is absolutely
unncessery in the thread-exit case.)

the reaping of the thread is thus not done by the parent (or init), but by
per-CPU [kwaitd] kernel threads. The exiting thread queues itself always
to the CPU-local kwaitd queue, to maintain locality of reference and cheap
switching to kwaitd.

[ this new reaping method could also be used when reparenting to init -
but i'm unsure whether this would really work as expected - do some init
variants rely perhaps on getting all orphan tasks in the system? ]

i've tested this against the 2.5.31-BK + clone_startup()-patch +
exit_free()-patch kernel tree, it works as expected.

	Ingo

--- linux/include/linux/sched.h.orig	Tue Aug 13 17:32:35 2002
+++ linux/include/linux/sched.h	Tue Aug 13 17:36:24 2002
@@ -46,6 +46,7 @@
 #define CLONE_NEWNS	0x00020000	/* New namespace group? */
 #define CLONE_SYSVSEM	0x00040000	/* share system V SEM_UNDO semantics */
 #define CLONE_STARTUP	0x00080000	/* create child state */
+#define CLONE_DETACHED	0x00100000	/* auto-reaped by kwaitd */
 
 #define CLONE_SIGNAL	(CLONE_SIGHAND | CLONE_THREAD)
 
@@ -297,6 +298,7 @@
 	struct list_head children;	/* list of my children */
 	struct list_head sibling;	/* linkage in my parent's children list */
 	struct list_head thread_group;
+	struct list_head zombie_list;
 
 	/* PID hash table linkage. */
 	struct task_struct *pidhash_next;
@@ -647,6 +649,8 @@
 extern void reparent_to_init(void);
 extern void daemonize(void);
 extern task_t *child_reaper;
+extern void reap_thread(task_t *p);
+extern void release_task(struct task_struct * p);
 
 extern int do_execve(char *, char **, char **, struct pt_regs *);
 extern struct task_struct *do_fork(unsigned long, unsigned long, struct pt_regs *, unsigned long);
--- linux/include/linux/init_task.h.orig	Tue Aug 13 17:36:32 2002
+++ linux/include/linux/init_task.h	Tue Aug 13 17:36:47 2002
@@ -59,6 +59,7 @@
     children:		LIST_HEAD_INIT(tsk.children),			\
     sibling:		LIST_HEAD_INIT(tsk.sibling),			\
     thread_group:	LIST_HEAD_INIT(tsk.thread_group),		\
+    zombie_list:	LIST_HEAD_INIT(tsk.zombie_list),		\
     wait_chldexit:	__WAIT_QUEUE_HEAD_INITIALIZER(tsk.wait_chldexit),\
     real_timer:		{						\
 	function:		it_real_fn				\
--- linux/kernel/exit.c.orig	Tue Aug 13 17:29:05 2002
+++ linux/kernel/exit.c	Tue Aug 13 17:36:03 2002
@@ -54,9 +54,13 @@
 	}
 }
 
-static void release_task(struct task_struct * p)
+void release_task(struct task_struct * p)
 {
 	if (p == current)
+		BUG();
+	if (p->state != TASK_ZOMBIE)
+		BUG();
+	if (!list_empty(&p->zombie_list))
 		BUG();
 #ifdef CONFIG_SMP
 	wait_task_inactive(p);
--- linux/kernel/signal.c.orig	Tue Aug 13 17:29:36 2002
+++ linux/kernel/signal.c	Tue Aug 13 17:50:42 2002
@@ -16,6 +16,8 @@
 #include <linux/fs.h>
 #include <linux/tty.h>
 #include <linux/binfmts.h>
+#include <linux/percpu.h>
+#include <linux/notifier.h>
 
 #include <asm/uaccess.h>
 #include <asm/siginfo.h>
@@ -774,6 +776,12 @@
 	struct siginfo info;
 	int why, status;
 
+	/* is the thread detached? */
+	if (sig == -1) {
+		reap_thread(tsk);
+		return;
+	}
+
 	info.si_signo = sig;
 	info.si_errno = 0;
 	info.si_pid = tsk->pid;
@@ -1501,3 +1509,104 @@
 }
 
 #endif /* HAVE_ARCH_SYS_PAUSE */
+
+/*
+ * kwaitd per-CPU threads help freeing exit()ed threads:
+ */
+typedef struct {
+	spinlock_t lock;
+	list_t queue;
+	task_t *task;
+} kwait_t;
+
+static kwait_t kwait_threads[NR_CPUS] __cacheline_aligned;
+
+void reap_thread(task_t *p)
+{
+	kwait_t *kwait = kwait_threads + smp_processor_id();
+
+
+	if (p->parent == kwait->task) {
+		printk("hm, %s(%d) reaped already.\n", p->comm, p->pid);
+		return;
+	}
+	REMOVE_LINKS(p);
+	p->parent = kwait->task;
+	p->real_parent = kwait->task;
+	SET_LINKS(p);
+
+	spin_lock(&kwait->lock);
+	if (!list_empty(&p->zombie_list))
+		BUG();
+	list_add_tail(&p->zombie_list, &kwait->queue);
+	spin_unlock(&kwait->lock);
+	wake_up_process(kwait->task);
+}
+
+static int kwaitd(void * __cpu)
+{
+	int cpu = (long) __cpu;
+	kwait_t *kwait = kwait_threads + cpu;
+	list_t *tmp;
+	task_t *p;
+
+	daemonize();
+	set_cpus_allowed(current, 1UL << cpu);
+	printk("[kwaitd_CPU%d] started up.\n", cpu);
+
+	spin_lock_init(&kwait->lock);
+	INIT_LIST_HEAD(&kwait->queue);
+	kwait->task = current;
+	
+	set_user_nice(current, -20);
+	sigfillset(&current->blocked);
+	sprintf(current->comm, "kwaitd_CPU%d", cpu);
+
+	for (;;) {
+		spin_lock(&kwait->lock);
+		tmp = kwait->queue.next;
+		if (list_empty(tmp)) {
+			current->state = TASK_INTERRUPTIBLE;
+			spin_unlock(&kwait->lock);
+
+			schedule();
+			current->state = TASK_RUNNING;
+			continue;
+		}
+		list_del_init(tmp);
+		spin_unlock(&kwait->lock);
+
+		p = list_entry(tmp, task_t, zombie_list);
+
+
+		release_task(p);
+	}
+}
+
+static int __devinit cpu_callback(struct notifier_block *nfb,
+				unsigned long action, void *hcpu)
+{
+	int cpu = (long)hcpu;
+
+        if (action == CPU_ONLINE) {
+		if (kernel_thread(kwaitd, hcpu,
+				CLONE_FS | CLONE_FILES | CLONE_SIGNAL) < 0) {
+			printk("start_kwaitd() failed for cpu %d\n", cpu);
+			return NOTIFY_BAD;
+		}
+		while (!kwait_threads[cpu].task)
+			yield();
+		return NOTIFY_OK;
+        }
+	return NOTIFY_BAD;
+}
+
+static struct notifier_block cpu_nfb = { &cpu_callback, NULL, 0 };
+
+__init int start_kwaitd(void)
+{
+	cpu_callback(&cpu_nfb, CPU_ONLINE, (void *)(long)smp_processor_id());
+	register_cpu_notifier(&cpu_nfb);
+	return 0;
+}
+
--- linux/kernel/fork.c.orig	Tue Aug 13 17:34:54 2002
+++ linux/kernel/fork.c	Tue Aug 13 17:35:29 2002
@@ -737,7 +737,11 @@
 
 	/* ok, now we should be set up.. */
 	p->swappable = 1;
-	p->exit_signal = clone_flags & CSIGNAL;
+	if (clone_flags & CLONE_DETACHED)
+		p->exit_signal = -1;
+	else
+		p->exit_signal = clone_flags & CSIGNAL;
+        INIT_LIST_HEAD(&p->zombie_list);
 	p->pdeath_signal = 0;
 
 	/*
--- linux/init/main.c.orig	Tue Aug 13 17:50:55 2002
+++ linux/init/main.c	Tue Aug 13 17:51:23 2002
@@ -527,12 +527,14 @@
 static void do_pre_smp_initcalls(void)
 {
 	extern int spawn_ksoftirqd(void);
+	extern int start_kwaitd(void);
 #ifdef CONFIG_SMP
 	extern int migration_init(void);
 
 	migration_init();
 #endif
 	spawn_ksoftirqd();
+	start_kwaitd();
 }
 
 extern void prepare_namespace(void);

Re: [patch] kwaitd, 2.5.31-A1

[Christoph Hellwig]

On Tue, Aug 13, 2002 at 06:01:48PM +0200, Ingo Molnar wrote:
> the reaping of the thread is thus not done by the parent (or init), but by
> per-CPU [kwaitd] kernel threads. The exiting thread queues itself always
> to the CPU-local kwaitd queue, to maintain locality of reference and cheap
> switching to kwaitd.

Is there a reason you don't use kevent for this?  Especially when going to
the per-CPU kevent as part of aio?

Re: [patch] kwaitd, 2.5.31-A1

[Andrew Morton]

Ingo Molnar wrote:
> 
> ...
> the reaping of the thread is thus not done by the parent (or init), but by
> per-CPU [kwaitd] kernel threads. The exiting thread queues itself always
> to the CPU-local kwaitd queue, to maintain locality of reference and cheap
> switching to kwaitd.

I'd be inclined to agree with hch on that.  We have an awful lot of
kernel threads nowadays, and keventd would fill the bill.

Andrea's kernels have keventd running SCHED_RR, and that's appropriate
to this application also.   Not sure about AIO though.

> [ this new reaping method could also be used when reparenting to init -
> but i'm unsure whether this would really work as expected - do some init
> variants rely perhaps on getting all orphan tasks in the system? ]

That should be OK.  init never knew about the reparented ones anyway.

> ...
> +
> +static kwait_t kwait_threads[NR_CPUS] __cacheline_aligned;
> +

We need to start using Rusty's percpu stuff sometime.

> +void reap_thread(task_t *p)
> +{
> +       kwait_t *kwait = kwait_threads + smp_processor_id();
> +

get_cpu() here?

> +
> +       if (p->parent == kwait->task) {
> +               printk("hm, %s(%d) reaped already.\n", p->comm, p->pid);
> +               return;
> +       }
> +       REMOVE_LINKS(p);

This is called under read_lock(&tasklist_lock), but modifies the
task list.

> ...
> +
> +                       schedule();
> +                       current->state = TASK_RUNNING;

schedule() always returns in state TASK_RUNNING?  (Or at least, it
used to.  Tell me if that changed, quick ;))

And a question: is it not possible to make the exitting task just go
and reap itself?  If it's a matter of freeing the stack pages we could
just add the page to a per-cpu deferred freeing list and reap it in
page reclaim.

Re: [patch] kwaitd, 2.5.31-A1

[Ingo Molnar]

On Tue, 13 Aug 2002, Andrew Morton wrote:

> > the reaping of the thread is thus not done by the parent (or init), but by
> > per-CPU [kwaitd] kernel threads. The exiting thread queues itself always
> > to the CPU-local kwaitd queue, to maintain locality of reference and cheap
> > switching to kwaitd.
> 
> I'd be inclined to agree with hch on that.  We have an awful lot of
> kernel threads nowadays, and keventd would fill the bill.

i agree. What i did was i looked at the kernel-source as-is, and there was
no mechanism to do this properly so i took a different approach. Could
anyone send me per-CPU keventd patches? The thread-exit path is pretty
timing-critical, the current global keventd spinlock does not work.

> > +void reap_thread(task_t *p)
> > +{
> > +       kwait_t *kwait = kwait_threads + smp_processor_id();
> > +
> 
> get_cpu() here?

this function is called under a spinlock currently, so there's no point in
doing that.

> > +       if (p->parent == kwait->task) {
> > +               printk("hm, %s(%d) reaped already.\n", p->comm, p->pid);
> > +               return;
> > +       }
> > +       REMOVE_LINKS(p);
> 
> This is called under read_lock(&tasklist_lock), but modifies the
> task list.

hm, i thought it was only under the write lock. Oh, i see, a rare strace
codepath does it. Fixed - thanks.

> > ...
> > +
> > +                       schedule();
> > +                       current->state = TASK_RUNNING;
> 
> schedule() always returns in state TASK_RUNNING? [...]

right - fixed :)

> And a question: is it not possible to make the exitting task just go and
> reap itself?  If it's a matter of freeing the stack pages we could just
> add the page to a per-cpu deferred freeing list and reap it in page
> reclaim.

well, yes - but i dislike deferred freeing lists, it's always a problem
where to free the RAM for real. It didnt really work for bhs, it didnt
really work for other items either. And we have this nice lazy-TLB
mechanism for kernel threads so it's really a non-issue to use them.

	Ingo

Re: [patch] kwaitd, 2.5.31-A1

[Andrew Morton]

Ingo Molnar wrote:
> 
> On Tue, 13 Aug 2002, Andrew Morton wrote:
> 
> > > the reaping of the thread is thus not done by the parent (or init), but by
> > > per-CPU [kwaitd] kernel threads. The exiting thread queues itself always
> > > to the CPU-local kwaitd queue, to maintain locality of reference and cheap
> > > switching to kwaitd.
> >
> > I'd be inclined to agree with hch on that.  We have an awful lot of
> > kernel threads nowadays, and keventd would fill the bill.
> 
> i agree. What i did was i looked at the kernel-source as-is, and there was
> no mechanism to do this properly so i took a different approach. Could
> anyone send me per-CPU keventd patches? The thread-exit path is pretty
> timing-critical, the current global keventd spinlock does not work.

I think Arjan has them, or the AIO patch.

> ...
> > And a question: is it not possible to make the exitting task just go and
> > reap itself?  If it's a matter of freeing the stack pages we could just
> > add the page to a per-cpu deferred freeing list and reap it in page
> > reclaim.
> 
> well, yes - but i dislike deferred freeing lists, it's always a problem
> where to free the RAM for real. It didnt really work for bhs, it didnt
> really work for other items either. And we have this nice lazy-TLB
> mechanism for kernel threads so it's really a non-issue to use them.

Well what we can do in there is to just have a one-deep percpu list.
So the exitting task frees the previous thread's stack (if any)
and inserts its own stack.  And that stack can be used in fork, of
course.  Which gives some per-cpu LIFO stack allocation.

It would mean that the thread would have to exit with preempt disabled,
but AFAIK that's just a matter of fixing or deleting that debug warning.

Re: [patch] kwaitd, 2.5.31-A1

[Ingo Molnar]

On Tue, 13 Aug 2002, Andrew Morton wrote:

> Well what we can do in there is to just have a one-deep percpu list. So
> the exitting task frees the previous thread's stack (if any) and inserts
> its own stack.  And that stack can be used in fork, of course.  Which
> gives some per-cpu LIFO stack allocation.

yeah, this will work - and it's not a big chunk of RAM we are holding
onto, so we can keep it around indefinitely. I'll try it this way.

(the LIFO argument is not true once the proper per-CPU page caching
patches are integrated.)

(btw., the kernel has the same catch-22 problem as user-space's problem
with stack deallocation, with the difference that it's much easier and
cheaper to provide atomicity in kernel-space.)

	Ingo

[patch] clone-detached-2.5.31-A1

[Ingo Molnar]

the attached patch implements the per-CPU thread-structure cache to do
detached exit, if the parent does not want to be notified of child exit
via a signal. It works wondefully. (tested patch against BK-current.)

i'm worried about one codepath though, in sys_wait4() we have this:

                                        p->parent = p->real_parent;
                                        add_parent(p, p->parent);
                                        do_notify_parent(p, SIGCHLD);

can this actually trigger for a detached process as well? In any case i've
put an assert in to make sure.

	Ingo

--- linux/include/linux/sched.h.orig	Tue Aug 13 20:27:23 2002
+++ linux/include/linux/sched.h	Tue Aug 13 20:50:18 2002
@@ -47,6 +47,7 @@
 #define CLONE_SYSVSEM	0x00040000	/* share system V SEM_UNDO semantics */
 #define CLONE_SETTLS	0x00080000	/* create a new TLS for the child */
 #define CLONE_SETTID	0x00100000	/* write the TID back to userspace */
+#define CLONE_DETACHED	0x00200000	/* parent wants no child-exit signal */
 
 #define CLONE_SIGNAL	(CLONE_SIGHAND | CLONE_THREAD)
 
--- linux/kernel/exit.c.orig	Tue Aug 13 19:55:04 2002
+++ linux/kernel/exit.c	Tue Aug 13 20:52:46 2002
@@ -56,10 +56,11 @@
 
 static void release_task(struct task_struct * p)
 {
-	if (p == current)
+	if (p->state != TASK_ZOMBIE)
 		BUG();
 #ifdef CONFIG_SMP
-	wait_task_inactive(p);
+	if (p != current)
+		wait_task_inactive(p);
 #endif
 	atomic_dec(&p->user->processes);
 	security_ops->task_free_security(p);
@@ -67,10 +68,12 @@
 	unhash_process(p);
 
 	release_thread(p);
-	current->cmin_flt += p->min_flt + p->cmin_flt;
-	current->cmaj_flt += p->maj_flt + p->cmaj_flt;
-	current->cnswap += p->nswap + p->cnswap;
-	sched_exit(p);
+	if (p != current) {
+		current->cmin_flt += p->min_flt + p->cmin_flt;
+		current->cmaj_flt += p->maj_flt + p->cmaj_flt;
+		current->cnswap += p->nswap + p->cnswap;
+		sched_exit(p);
+	}
 	put_task_struct(p);
 }
 
@@ -479,14 +482,15 @@
 
 	write_lock_irq(&tasklist_lock);
 	current->state = TASK_ZOMBIE;
-	do_notify_parent(current, current->exit_signal);
+	if (current->exit_signal != -1)
+		do_notify_parent(current, current->exit_signal);
 	while ((p = eldest_child(current))) {
 		list_del_init(&p->sibling);
 		p->ptrace = 0;
 
 		p->parent = p->real_parent;
 		list_add_tail(&p->sibling,&p->parent->children);
-		if (p->state == TASK_ZOMBIE)
+		if (p->state == TASK_ZOMBIE && p->exit_signal != -1)
 			do_notify_parent(p, p->exit_signal);
 		/*
 		 * process group orphan check
@@ -555,6 +559,9 @@
 
 	tsk->exit_code = code;
 	exit_notify();
+	preempt_disable();
+	if (current->exit_signal == -1)
+		release_task(current);
 	schedule();
 	BUG();
 /*
--- linux/kernel/signal.c.orig	Tue Aug 13 19:55:07 2002
+++ linux/kernel/signal.c	Tue Aug 13 20:53:43 2002
@@ -768,12 +768,15 @@
 /*
  * Let a parent know about a status change of a child.
  */
-
 void do_notify_parent(struct task_struct *tsk, int sig)
 {
 	struct siginfo info;
 	int why, status;
 
+	/* is the thread detached? */
+	if (sig == -1 || tsk->exit_signal == -1)
+		BUG();
+
 	info.si_signo = sig;
 	info.si_errno = 0;
 	info.si_pid = tsk->pid;
@@ -823,9 +826,11 @@
 void
 notify_parent(struct task_struct *tsk, int sig)
 {
-	read_lock(&tasklist_lock);
-	do_notify_parent(tsk, sig);
-	read_unlock(&tasklist_lock);
+	if (sig != -1) {
+		read_lock(&tasklist_lock);
+		do_notify_parent(tsk, sig);
+		read_unlock(&tasklist_lock);
+	}
 }
 
 #ifndef HAVE_ARCH_GET_SIGNAL_TO_DELIVER
--- linux/kernel/fork.c.orig	Tue Aug 13 19:55:07 2002
+++ linux/kernel/fork.c	Tue Aug 13 20:47:03 2002
@@ -50,6 +50,31 @@
 
 rwlock_t tasklist_lock __cacheline_aligned = RW_LOCK_UNLOCKED;  /* outer */
 
+/*
+ * A per-CPU task cache - this relies on the fact that
+ * the very last portion of sys_exit() is executed with
+ * preemption turned off.
+ */
+static task_t *task_cache[NR_CPUS] __cacheline_aligned;
+
+void __put_task_struct(struct task_struct *tsk)
+{
+	if (tsk != current) {
+		free_thread_info(tsk->thread_info);
+		kmem_cache_free(task_struct_cachep,tsk);
+	} else {
+		int cpu = smp_processor_id();
+
+		tsk = task_cache[cpu];
+		if (tsk) {
+			free_thread_info(tsk->thread_info);
+			kmem_cache_free(task_struct_cachep,tsk);
+		}
+		task_cache[cpu] = current;
+	}
+}
+
+/* Protects next_safe and last_pid. */
 void add_wait_queue(wait_queue_head_t *q, wait_queue_t * wait)
 {
 	unsigned long flags;
@@ -123,13 +148,6 @@
 	return tsk;
 }
 
-void __put_task_struct(struct task_struct *tsk)
-{
-	free_thread_info(tsk->thread_info);
-	kmem_cache_free(task_struct_cachep,tsk);
-}
-
-/* Protects next_safe and last_pid. */
 spinlock_t lastpid_lock = SPIN_LOCK_UNLOCKED;
 
 static int get_pid(unsigned long flags)
@@ -737,7 +755,10 @@
 
 	/* ok, now we should be set up.. */
 	p->swappable = 1;
-	p->exit_signal = clone_flags & CSIGNAL;
+	if (clone_flags & CLONE_DETACHED)
+		p->exit_signal = -1;
+	else
+		p->exit_signal = clone_flags & CSIGNAL;
 	p->pdeath_signal = 0;
 
 	/*

Re: [patch] clone-detached-2.5.31-A1

[Ingo Molnar]

> i'm worried about one codepath though, in sys_wait4() we have this:
> 
>                                         p->parent = p->real_parent;
>                                         add_parent(p, p->parent);
>                                         do_notify_parent(p, SIGCHLD);
> 
> can this actually trigger for a detached process as well? In any case
> i've put an assert in to make sure.

as far as i can see this cannot trigger because reparent_to_init() sets
exit_signal to SIGCHLD so the above code is correct.

	Ingo

Re: [patch] kwaitd, 2.5.31-A1

[Ingo Molnar]

On Tue, 13 Aug 2002, Andrew Morton wrote:

> Andrea's kernels have keventd running SCHED_RR, and that's appropriate
> to this application also.  Not sure about AIO though.

actually, the default (non-RT) priority of kwaitd is a feature. If there's
lots of exit() activity with lots or running threads (which is the typical
case on an exit-all for threads) then the kwaitd work will nicely cluster
up due it *not* always having the highest priority. This makes the cost of
kwaitd equivalent to the cost of per-CPU lists, asymptotically.

	Ingo