Skip to contentSkip to conversation

change __wake_up_parent() to use filtered wakeup

RFC PATCH In review Oleg Nesterov 2 participants 13 messages Jun 22, 2009 – Jul 1, 2009 1 message not in the archive

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

RFC PATCH 2/2 change __wake_up_parent() to use filtered wakeup

Ratan Nalumasu reported that in a process with many threads doing unnecessary wakeups. Every waiting thread in the process wakes up to loop through the children and see that the only ones it cares about are still not ready.

Now that we have struct wait_opts we can change do_wait/__wake_up_parent to use filtered wakeups.

We can make child_wait_callback() more clever later, right now it only checks eligible_child().

---

 kernel/signal.c |    3 ++-
 kernel/exit.c   |   22 +++++++++++++++++++---
 2 files changed, 21 insertions(+), 4 deletions(-)
kernel/signal.c renamed from kernel/signal.c~2_WAKE_PARENT +2 -1
@@ -1388,7 +1388,8 @@ ret:
 static inline void __wake_up_parent(struct task_struct *p,
 				    struct task_struct *parent)
 {
-	wake_up_interruptible_sync(&parent->signal->wait_chldexit);
+	__wake_up_sync_key(&parent->signal->wait_chldexit,
+				TASK_INTERRUPTIBLE, 1, p);
 }
 
 /*
kernel/exit.c renamed from kernel/exit.c~2_WAKE_PARENT +19 -3
@@ -1089,6 +1089,7 @@ struct wait_opts {
 	int __user		*wo_stat;
 	struct rusage __user	*wo_rusage;
 
+	wait_queue_t		child_wait;
 	int			notask_error;
 };
 
@@ -1558,15 +1559,29 @@ static int ptrace_do_wait(struct wait_op
 	return 0;
 }
 
+static int child_wait_callback(wait_queue_t *wait, unsigned mode,
+				int sync, void *key)
+{
+	struct wait_opts *wo = container_of(wait, struct wait_opts,
+						child_wait);
+	struct task_struct *p = key;
+
+	if (!eligible_child(wo, p))
+		return 0;
+
+	return default_wake_function(wait, mode, sync, key);
+}
+
 static long do_wait(struct wait_opts *wo)
 {
-	DECLARE_WAITQUEUE(wait, current);
 	struct task_struct *tsk;
 	int retval;
 
 	trace_sched_process_wait(wo->wo_pid);
 
-	add_wait_queue(&current->signal->wait_chldexit,&wait);
+	init_waitqueue_func_entry(&wo->child_wait, child_wait_callback);
+	wo->child_wait.private = current;
+	add_wait_queue(&current->signal->wait_chldexit, &wo->child_wait);
 repeat:
 	/*
 	 * If there is nothing that can match our critiera just get out.
@@ -1607,7 +1622,8 @@ notask:
 	}
 end:
 	__set_current_state(TASK_RUNNING);
-	remove_wait_queue(&current->signal->wait_chldexit,&wait);
+	remove_wait_queue(&current->signal->wait_chldexit, &wo->child_wait);
+
 	if (wo->wo_info) {
 		struct siginfo __user *infop = wo->wo_info;
 
#1 lore raw

Looks good, I'm glad to see this revived.

I note that even simpler than eligible_child() is just:

	if ((wo->wo_flags & __WNOTHREAD) && wo->child_wait.private != p->parent)
		return 0;

IIRC that is the test that Ratan's original patch used to address the particular application usage that first troubled him. But probably this is already what you meant by "more clever later" (and ->parent is perhaps not right in all cases there).

Your two patches as they are look safe and useful to me and I hope they can go in soon.

Thanks,
Roland

#2 lore raw
Quoted 4 lines · Roland McGrath

Looks good, I'm glad to see this revived.

I note that even simpler than eligible_child() is just:

I think the check below is orthogonal to eligible_child(). Not sure eligible_child() can really help, but otoh it is cheap and doesn't hurt. But perhaps we can kill it later.

Quoted 5 lines
	if ((wo->wo_flags & __WNOTHREAD) && wo->child_wait.private != p->parent)
		return 0;

IIRC that is the test that Ratan's original patch used to address the particular application usage that first troubled him.

Aha, now I see what was the problem with Ratan's workload.

Quoted 2 lines

But probably this
is already what you meant by "more clever later"

I didn't mean this particular optimization, but it looks good to me.

Quoted 2 lines

(and ->parent is perhaps
not right in all cases there).

I think this is right... Except I'd like to avoid using ->parent.

Quoted 2 lines

Your two patches as they are look safe and useful to me and I hope they can go in soon.

Thanks.

Yes I think these 2 patches should be applied first, even if eligible_child() itself doesn't buy much. It will be cleaner if we add "real" checks on top.

Oleg.

#3 lore raw
Quoted 1 line

I think the check below is orthogonal to eligible_child().

Yes.

Quoted 3 lines

Not sure
eligible_child() can really help, but otoh it is cheap and doesn't hurt. But perhaps we can kill it later.

No, it's a very good check to have. It is ideal for waitpid(ONE_PID,...) uses, which are also probably quite common.

Quoted 4 lines
Quoted 2 lines

(and ->parent is perhaps
not right in all cases there).

I think this is right... Except I'd like to avoid using ->parent.

Agreed. The not-right case I had in mind was do_notify_parent_cldstop where maybe it could be ->real_parent of the untraced group_leader.

Quoted 7 lines
Quoted 2 lines

Your two patches as they are look safe and useful to me and I hope they can go in soon.

Thanks.

Yes I think these 2 patches should be applied first, even if eligible_child() itself doesn't buy much. It will be cleaner if we add "real" checks on top.

Agreed.

Thanks,
Roland

#4 lore raw
Quoted 8 lines · Roland McGrath
Quoted 5 lines
Quoted 3 lines

(and ->parent is perhaps
not right in all cases there).

I think this is right... Except I'd like to avoid using ->parent.

Agreed. The not-right case I had in mind was do_notify_parent_cldstop where maybe it could be ->real_parent of the untraced group_leader.

Hmm. Could you explain?

I feel I missed something, but can't understand.

Oleg.

#5 lore raw
Quoted 6 lines
Quoted 2 lines

Agreed. The not-right case I had in mind was do_notify_parent_cldstop where maybe it could be ->real_parent of the untraced group_leader.

Hmm. Could you explain?

I feel I missed something, but can't understand.

Sorry, it wasn't very clear. (I guess I should have said "traced group leader", though that would not have been much more obvious.)

do_notify_parent_cldstop:

	if (task_ptrace(tsk))
		parent = tsk->parent;
	else {
		tsk = tsk->group_leader;
		parent = tsk->real_parent;
	}
	...
	__wake_up_parent(tsk, parent);

In the "else" case, parent is not necessarily tsk->parent. That is, if an untraced thread calls do_notify_parent_cldstop() but its group_leader is ptrace_reparented(). Then waitee->group_leader->real_parent is who gets the wakeup, but __wake_up_parent->child_wait_wakeup would check only waiter == waitee->group_leader->parent.

Thanks,
Roland

#6 lore raw
Quoted 12 lines · Roland McGrath

do_notify_parent_cldstop:

	if (task_ptrace(tsk))
		parent = tsk->parent;
	else {
		tsk = tsk->group_leader;
		parent = tsk->real_parent;
	}
	...
	__wake_up_parent(tsk, parent);
Quoted 5 lines

In the "else" case, parent is not necessarily tsk->parent. That is, if an untraced thread calls do_notify_parent_cldstop() but its group_leader is ptrace_reparented(). Then waitee->group_leader->real_parent is who gets the wakeup, but __wake_up_parent->child_wait_wakeup would check only waiter == waitee->group_leader->parent.

... and in this case we do not wake up ->group_leader->real_parent.

But this is fine? It doesn't make sense to wake up, wait_consider_task() will notice task_ptrace() and do nothing?

I really need to think with a fresh head, but it seems to me we could add BUG_ON(p->parent != parent) into wait_consider_task() after "if (ptrace...)" check.

And this "proves" your check in child_wait_callback() is correct, with __WNOTHREAD do_wait_thread(parent) is always called with parent == sleeper, the caller of do_wait().

No?

Btw, this reminds me that wait_consider_task() doesn't need the "parent" argument. I noticed this after adding wait_opts, but forgot to send a patch.

Oleg.

#7 lore raw
Quoted 9 lines
Quoted 4 lines

an untraced thread calls do_notify_parent_cldstop() but its group_leader is ptrace_reparented(). Then waitee->group_leader->real_parent is who gets the wakeup, but __wake_up_parent->child_wait_wakeup would check only waiter == waitee->group_leader->parent.

... and in this case we do not wake up ->group_leader->real_parent.

But this is fine? It doesn't make sense to wake up, wait_consider_task() will notice task_ptrace() and do nothing?

Right. I knew it needed more thought (that's why I said "maybe wrong" to begin with ;-).

Quoted 9 lines

I really need to think with a fresh head, but it seems to me we could add BUG_ON(p->parent != parent) into wait_consider_task() after "if (ptrace...)" check.

And this "proves" your check in child_wait_callback() is correct, with __WNOTHREAD do_wait_thread(parent) is always called with parent == sleeper, the caller of do_wait().

No?

Yes, I think that's right.

Quoted 3 lines

Btw, this reminds me that wait_consider_task() doesn't need the "parent" argument. I noticed this after adding wait_opts, but forgot to send a patch.

With the wq.private now in wait_opts, yes.

Thanks,
Roland

A message that is not in the archive (sent off-list or not yet received): [email protected]

#9 lore raw
Quoted 7 lines · Ratan Nalumasu

I understood it in the _past_, but somehow forgotten the details--I have a vague recollection that there was some special handling for the group leader stuff.
However, to reconfirm, we believe that the
following condition in eligible_child() is good, right:
===

Quoted 6 lines
       if ((wo->wo_flags & __WNOTHREAD) && wo->child_wait.private !=
p->parent)
               return 0;

===

I will run it on my test machines and see if everything looks good.

OK, thanks.

The only problem it uses ->parent, this conflicts with other out-of-tree ptrace changes...

Roland, do you think we should do this change now or later?

If now, then we can also do another nice optimization, and it is for free. See the untested patch below. It conflicts with those patches too, but in both cases fixups are trivial.

Oleg.

------------------------------------------------------------------------
[PATCH] do not place sub-threads on task_struct->children list

Currently we add sub-threads to ->real_parent->children list. This buys nothing but slows down do_wait().

With this patch ->children contains only main threads (group leaders). The only complication is that forget_original_parent() should iterate over sub-threads by hand. (note that we can move reparent_thread() outside of while_each_thread() loop and simplify the code further).

Quoted 1 line

From now do_wait_thread() can never see task_detached() && !EXIT_DEAD

tasks, we can remove this check. (note that now we can unify do_wait_thread() and ptrace_do_wait()).

This change can confuse the optimistic search inmm_update_next_owner(), but this is fixable and minor.

Perhaps badness() and oom_kill_process() should be updated, but they should be fixed in any case.

Do you see any problems?

---

 kernel/fork.c |    2 +-
 kernel/exit.c |   36 +++++++++++++++++-------------------
 2 files changed, 18 insertions(+), 20 deletions(-)
kernel/fork.c renamed from kernel/fork.c~3_CHILDREN_NO_THREADS +1 -1
@@ -1245,7 +1245,6 @@ static struct task_struct *copy_process(
 	}
 
 	if (likely(p->pid)) {
-		list_add_tail(&p->sibling, &p->real_parent->children);
 		tracehook_finish_clone(p, clone_flags, trace);
 
 		if (thread_group_leader(p)) {
@@ -1257,6 +1256,7 @@ static struct task_struct *copy_process(
 			p->signal->tty = tty_kref_get(current->signal->tty);
 			attach_pid(p, PIDTYPE_PGID, task_pgrp(current));
 			attach_pid(p, PIDTYPE_SID, task_session(current));
+			list_add_tail(&p->sibling, &p->real_parent->children);
 			list_add_tail_rcu(&p->tasks, &init_task.tasks);
 			__get_cpu_var(process_counts)++;
 		}
kernel/exit.c renamed from kernel/exit.c~3_CHILDREN_NO_THREADS +17 -19
@@ -67,11 +67,11 @@ static void __unhash_process(struct task
 		detach_pid(p, PIDTYPE_PGID);
 		detach_pid(p, PIDTYPE_SID);
 
+		list_del_init(&p->sibling);
 		list_del_rcu(&p->tasks);
 		__get_cpu_var(process_counts)--;
 	}
 	list_del_rcu(&p->thread_group);
-	list_del_init(&p->sibling);
 }
 
 /*
@@ -742,10 +742,10 @@ static void reparent_thread(struct task_
 	if (p->pdeath_signal)
 		group_send_sig_info(p->pdeath_signal, SEND_SIG_NOINFO, p);
 
-	list_move_tail(&p->sibling, &p->real_parent->children);
-
 	if (task_detached(p))
 		return;
+
+	list_move_tail(&p->sibling, &p->real_parent->children);
 	/*
 	 * If this is a threaded reparent there is no need to
 	 * notify anyone anything has happened.
@@ -771,7 +771,7 @@ static void reparent_thread(struct task_
 
 static void forget_original_parent(struct task_struct *father)
 {
-	struct task_struct *p, *n, *reaper;
+	struct task_struct *g, *p, *n, *reaper;
 	LIST_HEAD(dead_children);
 
 	exit_ptrace(father);
@@ -779,13 +779,16 @@ static void forget_original_parent(struc
 	write_lock_irq(&tasklist_lock);
 	reaper = find_new_reaper(father);
 
-	list_for_each_entry_safe(p, n, &father->children, sibling) {
-		p->real_parent = reaper;
-		if (p->parent == father) {
-			BUG_ON(task_ptrace(p));
-			p->parent = p->real_parent;
-		}
-		reparent_thread(father, p, &dead_children);
+	list_for_each_entry_safe(g, n, &father->children, sibling) {
+		p = g;
+		do {
+			p->real_parent = reaper;
+			if (p->parent == father) {
+				BUG_ON(task_ptrace(p));
+				p->parent = p->real_parent;
+			}
+			reparent_thread(father, p, &dead_children);
+		} while_each_thread(g, p);
 	}
 	write_unlock_irq(&tasklist_lock);
 
@@ -1533,14 +1536,9 @@ static int do_wait_thread(struct wait_op
 	struct task_struct *p;
 
 	list_for_each_entry(p, &tsk->children, sibling) {
-		/*
-		 * Do not consider detached threads.
-		 */
-		if (!task_detached(p)) {
-			int ret = wait_consider_task(wo, tsk, 0, p);
-			if (ret)
-				return ret;
-		}
+		int ret = wait_consider_task(wo, tsk, 0, p);
+		if (ret)
+			return ret;
 	}
 
 	return 0;
#10 lore raw

RFC 1/1 do not place sub-threads on task_struct->children list

(change subject)

Quoted 18 lines · Oleg Nesterov
Quoted 7 lines · Ratan Nalumasu

I understood it in the _past_, but somehow forgotten the details--I have a vague recollection that there was some special handling for the group leader stuff.
However, to reconfirm, we believe that the
following condition in eligible_child() is good, right:
===

Quoted 6 lines
       if ((wo->wo_flags & __WNOTHREAD) && wo->child_wait.private !=
p->parent)
               return 0;

===

I will run it on my test machines and see if everything looks good.

OK, thanks.

Quoted 8 lines

The only problem it uses ->parent, this conflicts with other out-of-tree ptrace changes...

Roland, do you think we should do this change now or later?

If now, then we can also do another nice optimization, and it is for free. See the untested patch below. It conflicts with those patches too, but in both cases fixups are trivial.

See the updated patch below, slightly tested.

Changes: s/reparent_thread/reparent_leader/ and move it out of loop. We still have to check task_detached() in reparent_leader(), we can find EXIT_DEAD leader.

Do you see any problems?

Oleg.

------------------------------------------------------------------------
[PATCH] do not place sub-threads on task_struct->children list

Currently we add sub-threads to ->real_parent->children list. This buys nothing but slows down do_wait().

With this patch ->children contains only main threads (group leaders). The only complication is that forget_original_parent() should iterate over sub-threads by hand.

Quoted 1 line

From now do_wait_thread() can never see task_detached() && !EXIT_DEAD

tasks, we can remove this check (and we can unify do_wait_thread() and ptrace_do_wait()).

This change can confuse the optimistic search inmm_update_next_owner(), but this is fixable and minor.

Perhaps badness() and oom_kill_process() should be updated, but they should be fixed in any case.

---

 kernel/fork.c |    2 +-
 kernel/exit.c |   41 ++++++++++++++++++++---------------------
 2 files changed, 21 insertions(+), 22 deletions(-)
kernel/fork.c renamed from kernel/fork.c~3_CHILDREN_NO_THREADS +1 -1
@@ -1245,7 +1245,6 @@ static struct task_struct *copy_process(
 	}
 
 	if (likely(p->pid)) {
-		list_add_tail(&p->sibling, &p->real_parent->children);
 		tracehook_finish_clone(p, clone_flags, trace);
 
 		if (thread_group_leader(p)) {
@@ -1257,6 +1256,7 @@ static struct task_struct *copy_process(
 			p->signal->tty = tty_kref_get(current->signal->tty);
 			attach_pid(p, PIDTYPE_PGID, task_pgrp(current));
 			attach_pid(p, PIDTYPE_SID, task_session(current));
+			list_add_tail(&p->sibling, &p->real_parent->children);
 			list_add_tail_rcu(&p->tasks, &init_task.tasks);
 			__get_cpu_var(process_counts)++;
 		}
kernel/exit.c renamed from kernel/exit.c~3_CHILDREN_NO_THREADS +20 -21

77 lines not on this page · raw message

#11 lore raw

Re: [rfc] do not place sub-threads on task_struct->children list

Quoted 6 lines

Currently we add sub-threads to ->real_parent->children list. This buys nothing but slows down do_wait().

With this patch ->children contains only main threads (group leaders). The only complication is that forget_original_parent() should iterate over sub-threads by hand.

This seems right to me, though I'll admit I haven't really walked through all the exit/reparent paths afresh with this in mind.

Note that this naturally suggests moving ->sibling to signal_struct. (Of course that can come later.) The abuse of sibling in reparent_leader adds a wrinkle to that, but off hand it looks like it could do the same with it living in signal_struct with a bit of contortion.

Oh, and what about the de_thread() leader-replacement case?

Thanks,
Roland

#12 lore raw

Re: [rfc] do not place sub-threads on task_struct->children list

Quoted 8 lines · Roland McGrath
Quoted 7 lines

Currently we add sub-threads to ->real_parent->children list. This buys nothing but slows down do_wait().

With this patch ->children contains only main threads (group leaders). The only complication is that forget_original_parent() should iterate over sub-threads by hand.

Quoted 7 lines

This seems right to me, though I'll admit I haven't really walked through all the exit/reparent paths afresh with this in mind.

Note that this naturally suggests moving ->sibling to signal_struct. (Of course that can come later.) The abuse of sibling in reparent_leader adds a wrinkle to that, but off hand it looks like it could do the same with it living in signal_struct with a bit of contortion.

Yes, this change was suggested a long ago.

But in that case forget_original_parent() still has to iterate over all childs to send ->pdeath_signal and change ->real_parent when we reparent to sub-thread.

Quoted 1 line

Oh, and what about the de_thread() leader-replacement case?

Ah, good point!

de_thread() should do list_replace_init().

Oleg.

#13 lore raw
In reply to Oleg Nesterov
Quoted 5 lines
Quoted 5 lines
       if ((wo->wo_flags & __WNOTHREAD) && wo->child_wait.private !=
p->parent)
               return 0;

===

Quoted 8 lines
Quoted 1 line

I will run it on my test machines and see if everything looks good.

OK, thanks.

The only problem it uses ->parent, this conflicts with other out-of-tree ptrace changes...

Roland, do you think we should do this change now or later?

I think it makes most sense to put that in right after the initial wait_child_callback patch (if not rolled into it). In fact, the original approach was to do just this "simplest" __WNOTHREAD-checking callback first, and add the eligible_child() hacking second (not that I think that order matters).

Thanks,
Roland