wait4() WIFSTOPPED starvation fix #1/2

PATCH New David Howells 1 participant 1 message Mar 15, 2002

Subsystems (6)

VFS MM core Scheduler exec and binfmt +2 more subsystems

lore

Share & tools

lore

David Howells

author

2002-03-15 21:10 UTC #0 lore raw

PATCH 1/1 wait4() WIFSTOPPED starvation fix #1/2

Hi Linus,

There appears to be a starvation bug in sys_wait4().

The case runs like this:

(1) If a process has a lot of threads, and a debugger like strace is running over all the threads, then the threads will be sat in the stopped more often than they're running.

(2) the children being traced are "reparented" and added to strace's children list.

(4) strace uses wait4() to find an _unspecified_ stopped (T) or zombie (Z) state process for it to deal with.

(5) sys_wait4() always walks the list of children in the same order (effectively fork/clone order).

(6) children at the end of the list starve for attention because sys_wait4() always takes the first process on the list that needs attention, and the list isn't ever rearranged.

This patch (#1) just converts the task_struct to use struct list_head rather than direct pointers for maintaining the children list.

David

arch/i386/kernel/signal.c +3 -3

diff -uNr linux-2.5.6-pre1/arch/i386/kernel/signal.c linux-wait-256p1/arch/i386/kernel/signal.c
@@ -630,8 +630,8 @@
 				info.si_signo = signr;
 				info.si_errno = 0;
 				info.si_code = SI_USER;
-				info.si_pid = current->p_pptr->pid;
-				info.si_uid = current->p_pptr->uid;
+				info.si_pid = current->parent->pid;
+				info.si_uid = current->parent->uid;
 			}
 
 			/* If the (new) signal is now blocked, requeue it.  */

@@ -670,7 +670,7 @@
 			case SIGSTOP: {
 				struct signal_struct *sig;
 				current->exit_code = signr;
-				sig = current->p_pptr->sig;
+				sig = current->parent->sig;
 				preempt_disable();
 				current->state = TASK_STOPPED;
 				if (sig && !(sig->action[SIGCHLD-1].sa.sa_flags & SA_NOCLDSTOP))

fs/binfmt_elf.c +1 -1

diff -uNr linux-2.5.6-pre1/fs/binfmt_elf.c linux-wait-256p1/fs/binfmt_elf.c
@@ -1094,7 +1094,7 @@
 	prstatus.pr_sigpend = current->pending.signal.sig[0];
 	prstatus.pr_sighold = current->blocked.sig[0];
 	psinfo.pr_pid = prstatus.pr_pid = current->pid;
-	psinfo.pr_ppid = prstatus.pr_ppid = current->p_pptr->pid;
+	psinfo.pr_ppid = prstatus.pr_ppid = current->parent->pid;
 	psinfo.pr_pgrp = prstatus.pr_pgrp = current->pgrp;
 	psinfo.pr_sid = prstatus.pr_sid = current->session;
 	prstatus.pr_utime.tv_sec = CT_TO_SECS(current->times.tms_utime);

fs/proc/array.c +2 -2

diff -uNr linux-2.5.6-pre1/fs/proc/array.c linux-wait-256p1/fs/proc/array.c
@@ -159,7 +159,7 @@
 		"Uid:\t%d\t%d\t%d\t%d\n"
 		"Gid:\t%d\t%d\t%d\t%d\n",
 		get_task_state(p), p->tgid,
-		p->pid, p->pid ? p->p_opptr->pid : 0, 0,
+		p->pid, p->pid ? p->real_parent->pid : 0, 0,
 		p->uid, p->euid, p->suid, p->fsuid,
 		p->gid, p->egid, p->sgid, p->fsgid);
 	read_unlock(&tasklist_lock);

@@ -340,7 +340,7 @@
 	nice = task_nice(task);
 
 	read_lock(&tasklist_lock);
-	ppid = task->pid ? task->p_opptr->pid : 0;
+	ppid = task->pid ? task->real_parent->pid : 0;
 	read_unlock(&tasklist_lock);
 	res = sprintf(buffer,"%d (%s) %c %d %d %d %d %d %lu %lu \
 %lu %lu %lu %lu %lu %ld %ld %ld %ld %ld %ld %lu %lu %ld %lu %lu %lu %lu %lu \

fs/proc/base.c +1 -1

diff -uNr linux-2.5.6-pre1/fs/proc/base.c linux-wait-256p1/fs/proc/base.c
@@ -336,7 +336,7 @@
 };
 
 #define MAY_PTRACE(p) \
-(p==current||(p->p_pptr==current&&(p->ptrace & PT_PTRACED)&&p->state==TASK_STOPPED))
+(p==current||(p->parent==current&&(p->ptrace & PT_PTRACED)&&p->state==TASK_STOPPED))
 
 
 static int mem_open(struct inode* inode, struct file* file)

include/linux/init_task.h +4 -2

diff -uNr linux-2.5.6-pre1/include/linux/init_task.h linux-wait-256p1/include/linux/init_task.h
@@ -55,8 +55,10 @@
     time_slice:		HZ,						\
     next_task:		&tsk,						\
     prev_task:		&tsk,						\
-    p_opptr:		&tsk,						\
-    p_pptr:		&tsk,						\
+    real_parent:	&tsk,						\
+    parent:		&tsk,						\
+    children:		LIST_HEAD_INIT(tsk.children),			\
+    sibling:		LIST_HEAD_INIT(tsk.sibling),			\
     thread_group:	LIST_HEAD_INIT(tsk.thread_group),		\
     wait_chldexit:	__WAIT_QUEUE_HEAD_INITIALIZER(tsk.wait_chldexit),\
     real_timer:		{						\

include/linux/sched.h +39 ~~-20~~

76 lines not on this page · raw message

kernel/exit.c +18 ~~-21~~

diff -uNr linux-2.5.6-pre1/kernel/exit.c linux-wait-256p1/kernel/exit.c
@@ -91,10 +91,10 @@
 	for_each_task(p) {
 		if ((p == ignored_task) || (p->pgrp != pgrp) ||
 		    (p->state == TASK_ZOMBIE) ||
-		    (p->p_pptr->pid == 1))
+		    (p->parent->pid == 1))
 			continue;
-		if ((p->p_pptr->pgrp != pgrp) &&
-		    (p->p_pptr->session == p->session)) {
+		if ((p->parent->pgrp != pgrp) &&
+		    (p->parent->session == p->session)) {
 			read_unlock(&tasklist_lock);
  			return 0;
 		}

@@ -144,8 +144,8 @@
 
 	/* Reparent to init */
 	REMOVE_LINKS(current);
-	current->p_pptr = child_reaper;
-	current->p_opptr = child_reaper;
+	current->parent = child_reaper;
+	current->real_parent = child_reaper;
 	SET_LINKS(current);
 
 	/* Set the exit signal to SIGCHLD so we signal init on exit */

@@ -217,16 +217,16 @@
 		reaper = child_reaper;
 
 	for_each_task(p) {
-		if (p->p_opptr == father) {
+		if (p->real_parent == father) {
 			/* We dont want people slaying init */
 			p->exit_signal = SIGCHLD;
 			p->self_exec_id++;
 
 			/* Make sure we're not reparenting to ourselves */
 			if (p == reaper)
-				p->p_opptr = child_reaper;
+				p->real_parent = child_reaper;
 			else
-				p->p_opptr = reaper;
+				p->real_parent = reaper;
 
 			if (p->pdeath_signal) send_sig(p->pdeath_signal, p, 0);
 		}

@@ -400,7 +400,7 @@
 	 * is about to become orphaned.
 	 */
 	 
-	t = current->p_pptr;
+	t = current->parent;
 	
 	if ((t->pgrp != current->pgrp) &&
 	    (t->session == current->session) &&

@@ -445,17 +445,12 @@
 	write_lock_irq(&tasklist_lock);
 	current->state = TASK_ZOMBIE;
 	do_notify_parent(current, current->exit_signal);
-	while (current->p_cptr != NULL) {
-		p = current->p_cptr;
-		current->p_cptr = p->p_osptr;
-		p->p_ysptr = NULL;
+	while ((p = eldest_child(current))) {
+		list_del_init(&p->sibling);
 		p->ptrace = 0;
 
-		p->p_pptr = p->p_opptr;
-		p->p_osptr = p->p_pptr->p_cptr;
-		if (p->p_osptr)
-			p->p_osptr->p_ysptr = p;
-		p->p_pptr->p_cptr = p;
+		p->parent = p->real_parent;
+		list_add_tail(&p->sibling,&p->parent->children);
 		if (p->state == TASK_ZOMBIE)
 			do_notify_parent(p, p->exit_signal);
 		/*

@@ -568,7 +563,9 @@
 	tsk = current;
 	do {
 		struct task_struct *p;
-	 	for (p = tsk->p_cptr ; p ; p = p->p_osptr) {
+		struct list_head *_p;
+		list_for_each(_p,&tsk->children) {
+			p = list_entry(_p,struct task_struct,sibling);
 			if (pid>0) {
 				if (p->pid != pid)
 					continue;

@@ -613,10 +610,10 @@
 				if (retval)
 					goto end_wait4; 
 				retval = p->pid;
-				if (p->p_opptr != p->p_pptr) {
+				if (p->real_parent != p->parent) {
 					write_lock_irq(&tasklist_lock);
 					REMOVE_LINKS(p);
-					p->p_pptr = p->p_opptr;
+					p->parent = p->real_parent;
 					SET_LINKS(p);
 					do_notify_parent(p, SIGCHLD);
 					write_unlock_irq(&tasklist_lock);

kernel/fork.c +6 -5

diff -uNr linux-2.5.6-pre1/kernel/fork.c linux-wait-256p1/kernel/fork.c
@@ -666,7 +666,8 @@
 
 	INIT_LIST_HEAD(&p->run_list);
 
-	p->p_cptr = NULL;
+	INIT_LIST_HEAD(&p->children);
+	INIT_LIST_HEAD(&p->sibling);
 	init_waitqueue_head(&p->wait_chldexit);
 	p->vfork_done = NULL;
 	if (clone_flags & CLONE_VFORK) {

@@ -766,12 +767,12 @@
 	write_lock_irq(&tasklist_lock);
 
 	/* CLONE_PARENT re-uses the old parent */
-	p->p_opptr = current->p_opptr;
-	p->p_pptr = current->p_pptr;
+	p->real_parent = current->real_parent;
+	p->parent = current->parent;
 	if (!(clone_flags & CLONE_PARENT)) {
-		p->p_opptr = current;
+		p->real_parent = current;
 		if (!(p->ptrace & PT_PTRACED))
-			p->p_pptr = current;
+			p->parent = current;
 	}
 
 	if (clone_flags & CLONE_THREAD) {

kernel/ptrace.c +4 -4

diff -uNr linux-2.5.6-pre1/kernel/ptrace.c linux-wait-256p1/kernel/ptrace.c
@@ -24,7 +24,7 @@
 	if (!(child->ptrace & PT_PTRACED))
 		return -ESRCH;
 
-	if (child->p_pptr != current)
+	if (child->parent != current)
 		return -ESRCH;
 
 	if (!kill) {

@@ -70,9 +70,9 @@
 	task_unlock(task);
 
 	write_lock_irq(&tasklist_lock);
-	if (task->p_pptr != current) {
+	if (task->parent != current) {
 		REMOVE_LINKS(task);
-		task->p_pptr = current;
+		task->parent = current;
 		SET_LINKS(task);
 	}
 	write_unlock_irq(&tasklist_lock);

@@ -98,7 +98,7 @@
 	child->exit_code = data;
 	write_lock_irq(&tasklist_lock);
 	REMOVE_LINKS(child);
-	child->p_pptr = child->p_opptr;
+	child->parent = child->real_parent;
 	SET_LINKS(child);
 	write_unlock_irq(&tasklist_lock);

kernel/sched.c +8 -7

diff -uNr linux-2.5.6-pre1/kernel/sched.c linux-wait-256p1/kernel/sched.c
@@ -1311,6 +1311,7 @@
 static void show_task(task_t * p)
 {
 	unsigned long free = 0;
+	task_t *relative;
 	int state;
 	static const char * stat_nam[] = { "R", "S", "D", "Z", "T", "W" };

@@ -1337,17 +1338,17 @@
 			n++;
 		free = (unsigned long) n - (unsigned long)(p+1);
 	}
-	printk("%5lu %5d %6d ", free, p->pid, p->p_pptr->pid);
-	if (p->p_cptr)
-		printk("%5d ", p->p_cptr->pid);
+	printk("%5lu %5d %6d ", free, p->pid, p->parent->pid);
+	if ((relative = eldest_child(p)))
+		printk("%5d ", relative->pid);
 	else
 		printk("      ");
-	if (p->p_ysptr)
-		printk("%7d", p->p_ysptr->pid);
+	if ((relative = younger_sibling(p)))
+		printk("%7d", relative->pid);
 	else
 		printk("       ");
-	if (p->p_osptr)
-		printk(" %5d", p->p_osptr->pid);
+	if ((relative = older_sibling(p)))
+		printk(" %5d", relative->pid);
 	else
 		printk("      ");
 	if (!p->mm)

kernel/signal.c +2 -2

diff -uNr linux-2.5.6-pre1/kernel/signal.c linux-wait-256p1/kernel/signal.c
@@ -804,8 +804,8 @@
 	info.si_code = why;
 	info.si_status = status;
 
-	send_sig_info(sig, &info, tsk->p_pptr);
-	wake_up_parent(tsk->p_pptr);
+	send_sig_info(sig, &info, tsk->parent);
+	wake_up_parent(tsk->parent);
 }

kernel/sys.c +1 -1

diff -uNr linux-2.5.6-pre1/kernel/sys.c linux-wait-256p1/kernel/sys.c
@@ -839,7 +839,7 @@
 	if (!p)
 		goto out;
 
-	if (p->p_pptr == current || p->p_opptr == current) {
+	if (p->parent == current || p->real_parent == current) {
 		err = -EPERM;
 		if (p->session != current->session)
 			goto out;

kernel/timer.c +2 -2

diff -uNr linux-2.5.6-pre1/kernel/timer.c linux-wait-256p1/kernel/timer.c
@@ -742,14 +742,14 @@
 	struct task_struct * me = current;
 	struct task_struct * parent;
 
-	parent = me->p_opptr;
+	parent = me->real_parent;
 	for (;;) {
 		pid = parent->pid;
 #if CONFIG_SMP
 {
 		struct task_struct *old = parent;
 		mb();
-		parent = me->p_opptr;
+		parent = me->real_parent;
 		if (old != parent)
 			continue;
 }