[PATCH 1/4] forget_original_parent: split out the un-ptrace part

[PATCH 1/4] forget_original_parent: split out the un-ptrace part

[Oleg Nesterov]

By discussion with Roland.

- Rename ptrace_exit() to exit_ptrace(), and change it to do all the
  necessary work with ->ptraced list by its own.

- Move this code from exit.c to ptrace.c

- Update the comment in ptrace_detach() to explain the rechecking of
  the child->ptrace.

Signed-off-by: Oleg Nesterov <oleg@redhat.com>

 include/linux/ptrace.h |    2 -
 include/linux/sched.h  |    5 ++
 kernel/exit.c          |   95 +++----------------------------------------------
 kernel/ptrace.c        |   78 +++++++++++++++++++++++++++++++++++++++-
 4 files changed, 88 insertions(+), 92 deletions(-)

--- 6.29-rc3/include/linux/ptrace.h~1_UNTRACE	2009-01-29 17:11:30.000000000 +0100
+++ 6.29-rc3/include/linux/ptrace.h	2009-02-11 02:41:08.000000000 +0100
@@ -94,7 +94,7 @@ extern void ptrace_notify(int exit_code)
 extern void __ptrace_link(struct task_struct *child,
 			  struct task_struct *new_parent);
 extern void __ptrace_unlink(struct task_struct *child);
-extern int __ptrace_detach(struct task_struct *tracer, struct task_struct *p);
+extern void exit_ptrace(struct task_struct *tracer);
 extern void ptrace_fork(struct task_struct *task, unsigned long clone_flags);
 #define PTRACE_MODE_READ   1
 #define PTRACE_MODE_ATTACH 2
--- 6.29-rc3/include/linux/sched.h~1_UNTRACE	2009-01-29 01:13:55.000000000 +0100
+++ 6.29-rc3/include/linux/sched.h	2009-02-11 03:05:20.000000000 +0100
@@ -2014,6 +2014,11 @@ static inline int thread_group_empty(str
 #define delay_group_leader(p) \
 		(thread_group_leader(p) && !thread_group_empty(p))
 
+static inline int task_detached(struct task_struct *p)
+{
+	return p->exit_signal == -1;
+}
+
 /*
  * Protects ->fs, ->files, ->mm, ->group_info, ->comm, keyring
  * subscriptions and synchronises with wait4().  Also used in procfs.  Also
--- 6.29-rc3/kernel/exit.c~1_UNTRACE	2009-02-11 01:48:57.000000000 +0100
+++ 6.29-rc3/kernel/exit.c	2009-02-11 03:01:46.000000000 +0100
@@ -61,11 +61,6 @@ DEFINE_TRACE(sched_process_wait);
 
 static void exit_mm(struct task_struct * tsk);
 
-static inline int task_detached(struct task_struct *p)
-{
-	return p->exit_signal == -1;
-}
-
 static void __unhash_process(struct task_struct *p)
 {
 	nr_threads--;
@@ -728,85 +723,6 @@ static void exit_mm(struct task_struct *
 	mmput(mm);
 }
 
-/*
- * Called with irqs disabled, returns true if childs should reap themselves.
- */
-static int ignoring_children(struct sighand_struct *sigh)
-{
-	int ret;
-	spin_lock(&sigh->siglock);
-	ret = (sigh->action[SIGCHLD-1].sa.sa_handler == SIG_IGN) ||
-	      (sigh->action[SIGCHLD-1].sa.sa_flags & SA_NOCLDWAIT);
-	spin_unlock(&sigh->siglock);
-	return ret;
-}
-
-/* Returns nonzero if the tracee should be released. */
-int __ptrace_detach(struct task_struct *tracer, struct task_struct *p)
-{
-	__ptrace_unlink(p);
-
-	if (p->exit_state != EXIT_ZOMBIE)
-		return 0;
-	/*
-	 * If it's a zombie, our attachedness prevented normal
-	 * parent notification or self-reaping.  Do notification
-	 * now if it would have happened earlier.  If it should
-	 * reap itself we return true.
-	 *
-	 * If it's our own child, there is no notification to do.
-	 * But if our normal children self-reap, then this child
-	 * was prevented by ptrace and we must reap it now.
-	 */
-	if (!task_detached(p) && thread_group_empty(p)) {
-		if (!same_thread_group(p->real_parent, tracer))
-			do_notify_parent(p, p->exit_signal);
-		else if (ignoring_children(tracer->sighand))
-			p->exit_signal = -1;
-	}
-
-	if (!task_detached(p))
-		return 0;
-
-	/* Mark it as in the process of being reaped. */
-	p->exit_state = EXIT_DEAD;
-	return 1;
-}
-
-/*
- * Detach all tasks we were using ptrace on.
- * Any that need to be release_task'd are put on the @dead list.
- *
- * Called with write_lock(&tasklist_lock) held.
- */
-static void ptrace_exit(struct task_struct *parent, struct list_head *dead)
-{
-	struct task_struct *p, *n;
-
-	list_for_each_entry_safe(p, n, &parent->ptraced, ptrace_entry) {
-		if (__ptrace_detach(parent, p))
-			list_add(&p->ptrace_entry, dead);
-	}
-}
-
-/*
- * Finish up exit-time ptrace cleanup.
- *
- * Called without locks.
- */
-static void ptrace_exit_finish(struct task_struct *parent,
-			       struct list_head *dead)
-{
-	struct task_struct *p, *n;
-
-	BUG_ON(!list_empty(&parent->ptraced));
-
-	list_for_each_entry_safe(p, n, dead, ptrace_entry) {
-		list_del_init(&p->ptrace_entry);
-		release_task(p);
-	}
-}
-
 /* Returns nonzero if the child should be released. */
 static int reparent_thread(struct task_struct *p, struct task_struct *father)
 {
@@ -891,12 +807,10 @@ static void forget_original_parent(struc
 	struct task_struct *p, *n, *reaper;
 	LIST_HEAD(ptrace_dead);
 
+	exit_ptrace(father);
+
 	write_lock_irq(&tasklist_lock);
 	reaper = find_new_reaper(father);
-	/*
-	 * First clean up ptrace if we were using it.
-	 */
-	ptrace_exit(father, &ptrace_dead);
 
 	list_for_each_entry_safe(p, n, &father->children, sibling) {
 		p->real_parent = reaper;
@@ -911,7 +825,10 @@ static void forget_original_parent(struc
 	write_unlock_irq(&tasklist_lock);
 	BUG_ON(!list_empty(&father->children));
 
-	ptrace_exit_finish(father, &ptrace_dead);
+	list_for_each_entry_safe(p, n, &ptrace_dead, ptrace_entry) {
+		list_del_init(&p->ptrace_entry);
+		release_task(p);
+	}
 }
 
 /*
--- 6.29-rc3/kernel/ptrace.c~1_UNTRACE	2009-02-11 01:44:52.000000000 +0100
+++ 6.29-rc3/kernel/ptrace.c	2009-02-11 04:04:17.000000000 +0100
@@ -235,9 +235,57 @@ out:
 	return retval;
 }
 
+/*
+ * Called with irqs disabled, returns true if childs should reap themselves.
+ */
+static int ignoring_children(struct sighand_struct *sigh)
+{
+	int ret;
+	spin_lock(&sigh->siglock);
+	ret = (sigh->action[SIGCHLD-1].sa.sa_handler == SIG_IGN) ||
+	      (sigh->action[SIGCHLD-1].sa.sa_flags & SA_NOCLDWAIT);
+	spin_unlock(&sigh->siglock);
+	return ret;
+}
+
+/*
+ * Called with tasklist_lock held for writing.
+ * Unlink a traced task, and clean it up if it was a traced zombie.
+ * Return true if it needs to be reaped with release_task().
+ * (We can't call release_task() here because we already hold tasklist_lock.)
+ *
+ * If it's a zombie, our attachedness prevented normal parent notification
+ * or self-reaping.  Do notification now if it would have happened earlier.
+ * If it should reap itself, return true.
+ *
+ * If it's our own child, there is no notification to do.
+ * But if our normal children self-reap, then this child
+ * was prevented by ptrace and we must reap it now.
+ */
+static bool __ptrace_detach(struct task_struct *tracer, struct task_struct *p)
+{
+	__ptrace_unlink(p);
+
+	if (p->exit_state == EXIT_ZOMBIE) {
+		if (!task_detached(p) && thread_group_empty(p)) {
+			if (!same_thread_group(p->real_parent, tracer))
+				do_notify_parent(p, p->exit_signal);
+			else if (ignoring_children(tracer->sighand))
+				p->exit_signal = -1;
+		}
+		if (task_detached(p)) {
+			/* Mark it as in the process of being reaped. */
+			p->exit_state = EXIT_DEAD;
+			return true;
+		}
+	}
+
+	return false;
+}
+
 int ptrace_detach(struct task_struct *child, unsigned int data)
 {
-	int dead = 0;
+	bool dead = false;
 
 	if (!valid_signal(data))
 		return -EIO;
@@ -247,7 +295,10 @@ int ptrace_detach(struct task_struct *ch
 	clear_tsk_thread_flag(child, TIF_SYSCALL_TRACE);
 
 	write_lock_irq(&tasklist_lock);
-	/* protect against de_thread()->release_task() */
+	/*
+	 * This child can be already killed. Make sure de_thread() or
+	 * our sub-thread doing do_wait() didn't do release_task() yet.
+	 */
 	if (child->ptrace) {
 		child->exit_code = data;
 
@@ -264,6 +315,29 @@ int ptrace_detach(struct task_struct *ch
 	return 0;
 }
 
+/*
+ * Detach all tasks we were using ptrace on.
+ */
+void exit_ptrace(struct task_struct *tracer)
+{
+	struct task_struct *p, *n;
+	LIST_HEAD(ptrace_dead);
+
+	write_lock_irq(&tasklist_lock);
+	list_for_each_entry_safe(p, n, &tracer->ptraced, ptrace_entry) {
+		if (__ptrace_detach(tracer, p))
+			list_add(&p->ptrace_entry, &ptrace_dead);
+	}
+	write_unlock_irq(&tasklist_lock);
+
+	BUG_ON(!list_empty(&tracer->ptraced));
+
+	list_for_each_entry_safe(p, n, &ptrace_dead, ptrace_entry) {
+		list_del_init(&p->ptrace_entry);
+		release_task(p);
+	}
+}
+
 int ptrace_readdata(struct task_struct *tsk, unsigned long src, char __user *dst, int len)
 {
 	int copied = 0;

Re: [PATCH 1/4] forget_original_parent: split out the un-ptrace part

[Roland McGrath]

> +static inline int task_detached(struct task_struct *p)

Maybe take the opportunity to make it bool?
Clearly trivial, but a bit of implicit documentation that doesn't hurt.

> @@ -911,7 +825,10 @@ static void forget_original_parent(struc
>  	write_unlock_irq(&tasklist_lock);
>  	BUG_ON(!list_empty(&father->children));
>  
> -	ptrace_exit_finish(father, &ptrace_dead);
> +	list_for_each_entry_safe(p, n, &ptrace_dead, ptrace_entry) {
> +		list_del_init(&p->ptrace_entry);
> +		release_task(p);
> +	}
>  }

I know it's removed by the next patch anyway.  But I wouldn't mind a comment
in this patch saying "kludge overload of ptrace_entry should go away soon".

> +/*
> + * Called with irqs disabled, returns true if childs should reap themselves.

s/childs/children/

Make this bool too.

> +/*
> + * Detach all tasks we were using ptrace on.
> + */
> +void exit_ptrace(struct task_struct *tracer)
> +{
> +	struct task_struct *p, *n;
> +	LIST_HEAD(ptrace_dead);

I think this can do a short-circuit for the common case and avoid the lock:

	if (list_empty(&tracer->ptraced))
		return;

It might even be worthwhile making it an inline that does the short-circuit
check before calling out to ptrace.c at all.

I see your patch 4/4 on this.  In fact, I think the short-circuit
optimization of these two cases should be two separate patches.  They are
for the same motivation and the same kind of optimization, but the details
of what the race issues might be are quite distinct between the two.

Moreover, the exit_ptrace optimization is removing the new lock overhead we
introduce in this patch.  The real-child optimization is just a new
optimization beyond the status quo.  It can really be considered wholly
after this whole series (and probably just punted because it gets so hairy).

For the ptrace case, I started out thinking it was trivially clear that no
false positives are possible here.  The tracer can't do ptrace_attach() or
do_fork(), it's exiting.  But ptrace_traceme() can sneak in here.  (I don't
see how release_task() could be a problem at all.  Going from nonempty to
empty could only cause false negatives--which are always harmless--not false
positives.)  

You didn't mention ptrace_traceme() in your 4/4 message.  Off hand I don't
see what keeps it safe when we go to dropping the tasklist_lock between
exit_ptrace and changing children's real_parent links.  In fact, that seems
like a new hole, period--without the short-circuit optimization.  
Am I overlooking something here?

That seems addressed by e.g.:

--- a/kernel/ptrace.c
+++ b/kernel/ptrace.c
@@ -534,7 +534,7 @@ repeat:
 		 * Set the ptrace bit in the process ptrace flags.
 		 * Then link us on our parent's ptraced list.
 		 */
-		if (!ret) {
+		if (!ret && !(current->real_parent->flags & PF_EXITING)) {
 			current->ptrace |= PT_PTRACED;
 			__ptrace_link(current, current->real_parent);
 		}



Thanks,
Roland

Re: [PATCH 1/4] forget_original_parent: split out the un-ptrace part

[Oleg Nesterov]

On 02/19, Roland McGrath wrote:
>
> > +static inline int task_detached(struct task_struct *p)
>
> Maybe take the opportunity to make it bool?
> Clearly trivial, but a bit of implicit documentation that doesn't hurt.

Agreed. Actually I was going to do this, but forgot.

I'll send the cleanup patch.

> > +void exit_ptrace(struct task_struct *tracer)
> > +{
> > +	struct task_struct *p, *n;
> > +	LIST_HEAD(ptrace_dead);
>
> I think this can do a short-circuit for the common case and avoid the lock:
>
> 	if (list_empty(&tracer->ptraced))
> 		return;

4/4 does this, but

> I see your patch 4/4 on this.  In fact, I think the short-circuit
> optimization of these two cases should be two separate patches.

agreed,

> The real-child optimization is just a new
> optimization beyond the status quo.  It can really be considered wholly
> after this whole series (and probably just punted because it gets so hairy).

Yes. You can see from the changelog that I don't actually like this
optimizatio very much. Because it complicates the code, adds the barrier,
but needs thread_group_empty().

If we are going to optimize out tasklist in forget_original_parent(), then
I'd prefer http://marc.info/?l=linux-kernel&m=123438710725342

But this needs a fat comment. And I didn't think carefully about this code.

> (I don't
> see how release_task() could be a problem at all.

This was mostly about forget_original_parent...

But from the _pure theoretical_ pov, it is not correct to assume that
list_empty(&tracer->ptraced) == T means that current can not be used
somehow as tracee->parent. Another subthread can release a dead tracee.

For example, list_empty(&tracer->ptraced) == T doesn't mean that the
STOREs to this task_struct are finished, list_del_init(->ptrace_entry)
can still be in progress.

But since we take tasklist before release_task(current) we are safe,
even in theory.

> You didn't mention ptrace_traceme() in your 4/4 message.

And I guess you want to know why I didn't...

Because I forgot completely about traceme! Thanks Roland.

> In fact, that seems
> like a new hole, period--without the short-circuit optimization.

I think you are right, the current code looks racy too.

> That seems addressed by e.g.:
>
> --- a/kernel/ptrace.c
> +++ b/kernel/ptrace.c
> @@ -534,7 +534,7 @@ repeat:
>  		 * Set the ptrace bit in the process ptrace flags.
>  		 * Then link us on our parent's ptraced list.
>  		 */
> -		if (!ret) {
> +		if (!ret && !(current->real_parent->flags & PF_EXITING)) {
>  			current->ptrace |= PT_PTRACED;

Yes sure.

But this means exit_ptrace() must always take tasklist, otherwise we
don't have the necessary barriers.

I am still feeling bad, will try to think more later.

Oleg.

Re: [PATCH 1/4] forget_original_parent: split out the un-ptrace part

[Oleg Nesterov]

On 02/23, Oleg Nesterov wrote:
>
> If we are going to optimize out tasklist in forget_original_parent(), then
> I'd prefer http://marc.info/?l=linux-kernel&m=123438710725342
>
> But this needs a fat comment. And I didn't think carefully about this code.

No, this won't work.

When ->child_reaper exits, it must take tasklist and call find_new_reaper()
even if it has no children.

Oleg.

Re: [PATCH 1/4] forget_original_parent: split out the un-ptrace part

[Oleg Nesterov]

Argh. Sorry to all for the noise, I should not have replied today...

On 02/23, Oleg Nesterov wrote:
>
> On 02/19, Roland McGrath wrote:
> >
> > In fact, that seems
> > like a new hole, period--without the short-circuit optimization.
>
> I think you are right, the current code looks racy too.

No, the current code is fine. And I just misunderstood you.

Oleg.

Re: [PATCH 1/4] forget_original_parent: split out the un-ptrace part

[Roland McGrath]

> But from the _pure theoretical_ pov, it is not correct to assume that
> list_empty(&tracer->ptraced) == T means that current can not be used
> somehow as tracee->parent. Another subthread can release a dead tracee.

I don't follow how that's relevant.  If list_empty(), then it was empty or
is becoming empty.  It can't then become nonempty again (because the thread
doing the check is the only one that adds to that list).  That's all we're
assuming.

> For example, list_empty(&tracer->ptraced) == T doesn't mean that the
> STOREs to this task_struct are finished, list_del_init(->ptrace_entry)
> can still be in progress.

Sure, but so what?  The check is to verify that some new list_del* (and
related cleanup work, of course) doesn't need to be *started*.

> > --- a/kernel/ptrace.c
> > +++ b/kernel/ptrace.c
> > @@ -534,7 +534,7 @@ repeat:
> >  		 * Set the ptrace bit in the process ptrace flags.
> >  		 * Then link us on our parent's ptraced list.
> >  		 */
> > -		if (!ret) {
> > +		if (!ret && !(current->real_parent->flags & PF_EXITING)) {
> >  			current->ptrace |= PT_PTRACED;
> 
> Yes sure.
> 
> But this means exit_ptrace() must always take tasklist, otherwise we
> don't have the necessary barriers.

Really?

	exit_signals(tsk);  /* sets PF_EXITING */
	/*
	 * tsk->flags are checked in the futex code to protect against
	 * an exiting task cleaning up the robust pi futexes.
	 */
	smp_mb();

This is an exactly analogous use, isn't it?  So exit_ptrace() just has to
follow this same existing barrier.  Right?


Thanks,
Roland

Re: [PATCH 1/4] forget_original_parent: split out the un-ptrace part

[Oleg Nesterov]

On 02/24, Roland McGrath wrote:
>
> > > --- a/kernel/ptrace.c
> > > +++ b/kernel/ptrace.c
> > > @@ -534,7 +534,7 @@ repeat:
> > >  		 * Set the ptrace bit in the process ptrace flags.
> > >  		 * Then link us on our parent's ptraced list.
> > >  		 */
> > > -		if (!ret) {
> > > +		if (!ret && !(current->real_parent->flags & PF_EXITING)) {
> > >  			current->ptrace |= PT_PTRACED;
> >
> > Yes sure.
> >
> > But this means exit_ptrace() must always take tasklist, otherwise we
> > don't have the necessary barriers.
>
> Really?
>
> 	exit_signals(tsk);  /* sets PF_EXITING */
> 	/*
> 	 * tsk->flags are checked in the futex code to protect against
> 	 * an exiting task cleaning up the robust pi futexes.
> 	 */
> 	smp_mb();
>
> This is an exactly analogous use, isn't it?  So exit_ptrace() just has to
> follow this same existing barrier.  Right?

Yes, we do have the barrier between "flags |= PF_EXITING" and
"if (list_empty(ptraced))" in exit_ptrace(), but it is not enough.

Because the exiting ->real_parent can both set PF_EXITING and return
from exit_ptrace() (without taking tasklist because it sees ->ptraced
is empty) right after the child checks ->real_parent->flags & PF_EXITING.

I am still thinking what can we do here (and btw my apologies for delay,
some stupid reasons distract me).

> > But from the _pure theoretical_ pov, it is not correct to assume that
> > list_empty(&tracer->ptraced) == T means that current can not be used
> > somehow as tracee->parent. Another subthread can release a dead tracee.
>
> I don't follow how that's relevant.  If list_empty(), then it was empty or
> is becoming empty.  It can't then become nonempty again (because the thread
> doing the check is the only one that adds to that list).  That's all we're
> assuming.
>
> > For example, list_empty(&tracer->ptraced) == T doesn't mean that the
> > STOREs to this task_struct are finished, list_del_init(->ptrace_entry)
> > can still be in progress.
>
> Sure, but so what?  The check is to verify that some new list_del* (and
> related cleanup work, of course) doesn't need to be *started*.

Well. I am starting to regret I mentioned this "problem" ;) Because even
if I am right (it is very possible I am not), this all is _absolutely_
theoretical. Let me try again to explain what I meant.

First of all, in theory write_lock_irq() does not imply rcu_read_lock().

Now let's suppose that the exiting task T does exit_ptrace(), sees the
empty ->ptraced list, and then can do release_task()->call_rcu(put_task_struct)
without taking the tasklist_lock on this path.

Let's also suppose that we race with another sub-thread which reaps
a zombie tracee and does __ptrace_unlink()->list_del_init(ptrace_entry).
__list_del does 1) next->prev = prev and 2) prev->next = next.

Let's suppose 2 is completed, but 1 is not.

T checks list_empty(->ptraced) and sees head->next == head. It proceeds
and calls call_rcu(put_task_struct).

Since (in theory!) we do not have rcu_read_lock(), it is possible that
task_struct is already freed when 1 write to the memory.


But actually I meant that this is not really safe "in general". Let's
suppose we change __ptrace_unlink() so that it does, say,
BUG_ON(child->parent->exit_state != 0) before untracing. Yes, sure,
this is ugly, but correct. Or BUG_ON(!child->parent->signal), or
whatever else.

But this is only correct because T takes tasklist before it actually
starts to "destroy" itself.


In short, my point is: even if exit_ptrace() sees list_empty(->ptraced),
it is possible that the just-untraced tracee "looks" at us and expects
that the former tracer is "alive" enough.

Oleg.