[PATCH] Don't apply for write lock on tasklist_lock if parent doesn't ptrace other processes

[PATCH] Don't apply for write lock on tasklist_lock if parent doesn't ptrace other processes

[Zhang, Yanmin]

We run some sub-cases (fork, exec, pipe, tcp, udp) of aim7 on 8-socket machine.
Perf shows write_lock_irq(&tasklist_lock) consumes more than 50% cpu time.

One hot caller is exit_ptrace. If the exiting process doesn't ptrace other
processes, kernel needn't apply for the write lock on tasklist_lock.

With below patch against kernel 2.6.35-rc5, we get more than 10% result improvement.

Signed-off-by: Zhang Yanmin <yanmin_zhang@linux.intel.com>

---

diff -Nraup linux-2.6.35-rc5/kernel/ptrace.c linux-2.6.35-rc5_ptrace/kernel/ptrace.c
--- linux-2.6.35-rc5/kernel/ptrace.c	2010-07-16 14:01:15.000000000 +0800
+++ linux-2.6.35-rc5_ptrace/kernel/ptrace.c	2010-07-16 14:03:20.000000000 +0800
@@ -331,6 +331,9 @@ void exit_ptrace(struct task_struct *tra
 	struct task_struct *p, *n;
 	LIST_HEAD(ptrace_dead);
 
+	if (list_empty(&tracer->ptraced))
+		return;
+
 	write_lock_irq(&tasklist_lock);
 	list_for_each_entry_safe(p, n, &tracer->ptraced, ptrace_entry) {
 		if (__ptrace_detach(tracer, p))

Re: [PATCH] Don't apply for write lock on tasklist_lock if parent doesn't ptrace other processes

[David Rientjes]

On Thu, 15 Jul 2010, Zhang, Yanmin wrote:

> We run some sub-cases (fork, exec, pipe, tcp, udp) of aim7 on 8-socket machine.
> Perf shows write_lock_irq(&tasklist_lock) consumes more than 50% cpu time.
> 
> One hot caller is exit_ptrace. If the exiting process doesn't ptrace other
> processes, kernel needn't apply for the write lock on tasklist_lock.
> 
> With below patch against kernel 2.6.35-rc5, we get more than 10% result improvement.
> 
> Signed-off-by: Zhang Yanmin <yanmin_zhang@linux.intel.com>

Acked-by: David Rientjes <rientjes@google.com>

We're guarded against ptrace_attach() because tracer->exit_state is 
non-zero at this point in the exit path.

Re: [PATCH] Don't apply for write lock on tasklist_lock if parent doesn't ptrace other processes

[Andrew Morton]

On Thu, 15 Jul 2010 14:51:03 +0800
"Zhang, Yanmin" <yanmin_zhang@linux.intel.com> wrote:

> We run some sub-cases (fork, exec, pipe, tcp, udp) of aim7 on 8-socket machine.
> Perf shows write_lock_irq(&tasklist_lock) consumes more than 50% cpu time.
> 
> One hot caller is exit_ptrace. If the exiting process doesn't ptrace other
> processes, kernel needn't apply for the write lock on tasklist_lock.
> 
> With below patch against kernel 2.6.35-rc5, we get more than 10% result improvement.
> 
> Signed-off-by: Zhang Yanmin <yanmin_zhang@linux.intel.com>
> 
> ---
> 
> diff -Nraup linux-2.6.35-rc5/kernel/ptrace.c linux-2.6.35-rc5_ptrace/kernel/ptrace.c
> --- linux-2.6.35-rc5/kernel/ptrace.c	2010-07-16 14:01:15.000000000 +0800
> +++ linux-2.6.35-rc5_ptrace/kernel/ptrace.c	2010-07-16 14:03:20.000000000 +0800
> @@ -331,6 +331,9 @@ void exit_ptrace(struct task_struct *tra
>  	struct task_struct *p, *n;
>  	LIST_HEAD(ptrace_dead);
>  
> +	if (list_empty(&tracer->ptraced))
> +		return;
> +
>  	write_lock_irq(&tasklist_lock);
>  	list_for_each_entry_safe(p, n, &tracer->ptraced, ptrace_entry) {
>  		if (__ptrace_detach(tracer, p))

hah, nice patch - an easy 10%.  I snuck a cc:stable into the changelog
in the hope that those guys mistake it for a bugfix ;)

Re: [PATCH] Don't apply for write lock on tasklist_lock if parent doesn't ptrace other processes

[Roland McGrath]

> > @@ -331,6 +331,9 @@ void exit_ptrace(struct task_struct *tra
> >  	struct task_struct *p, *n;
> >  	LIST_HEAD(ptrace_dead);
> >  
> > +	if (list_empty(&tracer->ptraced))
> > +		return;
> > +
> >  	write_lock_irq(&tasklist_lock);
> >  	list_for_each_entry_safe(p, n, &tracer->ptraced, ptrace_entry) {
> >  		if (__ptrace_detach(tracer, p))

I think we may have tried that before.  Oleg can tell us if it's really
safe vs a race with PTRACE_TRACEME or something like that.


Thanks,
Roland

Re: [PATCH] Don't apply for write lock on tasklist_lock if parent doesn't ptrace other processes

[Oleg Nesterov]

I am not surpized perf blaims tasklist, but I am really surpized this patch
adds 10% improvement...

On 07/21, Roland McGrath wrote:
>
> > > @@ -331,6 +331,9 @@ void exit_ptrace(struct task_struct *tra
> > >  	struct task_struct *p, *n;
> > >  	LIST_HEAD(ptrace_dead);
> > >
> > > +	if (list_empty(&tracer->ptraced))
> > > +		return;
> > > +
> > >  	write_lock_irq(&tasklist_lock);
> > >  	list_for_each_entry_safe(p, n, &tracer->ptraced, ptrace_entry) {
> > >  		if (__ptrace_detach(tracer, p))
>
> I think we may have tried that before.  Oleg can tell us if it's really
> safe vs a race with PTRACE_TRACEME or something like that.

Yes, this can race with ptrace_traceme(). Without tasklist_lock in
exit_ptrace(), it is possible that ptrace_traceme() starts __ptrace_link()
before it sees PF_EXITING, and completes before the result of list_add()
is visible to the exiting parent. tasklist acts as a barrier.

So, this list_empty() check needs taskslit at least for reading. But, we
are going to take it for writing right after exit_ptrace() returns, afaics
we can add this fastpatch check for free.

Uncompiled/untested.

Oleg.

 kernel/ptrace.c |   10 +++++++---
 kernel/exit.c   |    3 ++-
 2 files changed, 9 insertions(+), 4 deletions(-)

--- x/kernel/ptrace.c
+++ x/kernel/ptrace.c
@@ -324,26 +324,30 @@ int ptrace_detach(struct task_struct *ch
 }
 
 /*
- * Detach all tasks we were using ptrace on.
+ * Detach all tasks we were using ptrace on. Called with tasklist held.
  */
 void exit_ptrace(struct task_struct *tracer)
 {
 	struct task_struct *p, *n;
 	LIST_HEAD(ptrace_dead);
 
-	write_lock_irq(&tasklist_lock);
+	if (likely(list_empty(&tracer->ptraced)))
+		return;
+
 	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);
 
+	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);
 	}
+
+	write_lock_irq(&tasklist_lock);
 }
 
 int ptrace_readdata(struct task_struct *tsk, unsigned long src, char __user *dst, int len)
--- x/kernel/exit.c
+++ x/kernel/exit.c
@@ -771,9 +771,10 @@ static void forget_original_parent(struc
 	struct task_struct *p, *n, *reaper;
 	LIST_HEAD(dead_children);
 
+	write_lock_irq(&tasklist_lock);
+
 	exit_ptrace(father);
 
-	write_lock_irq(&tasklist_lock);
 	reaper = find_new_reaper(father);
 
 	list_for_each_entry_safe(p, n, &father->children, sibling) {

Re: [PATCH] Don't apply for write lock on tasklist_lock if parent doesn't ptrace other processes

[Roland McGrath]

> So, this list_empty() check needs taskslit at least for reading. But, we
> are going to take it for writing right after exit_ptrace() returns, afaics
> we can add this fastpatch check for free.

That looks good to me, but it could use some more scare comments.

>  /*
> - * Detach all tasks we were using ptrace on.
> + * Detach all tasks we were using ptrace on. Called with tasklist held.

 * Called with tasklist held for writing, and returns with it held too.
 * But note it can release and reacquire the lock.

> +	write_lock_irq(&tasklist_lock);
> +
	/*
	 * Note that exit_ptrace() might drop tasklist_lock and reacquire it.
	 */
>  	exit_ptrace(father);
>  
> -	write_lock_irq(&tasklist_lock);
>  	reaper = find_new_reaper(father);


Thanks,
Roland

Re: [PATCH] Don't apply for write lock on tasklist_lock if parent doesn't ptrace other processes

[Oleg Nesterov]

On 07/22, Roland McGrath wrote:
>
> > So, this list_empty() check needs taskslit at least for reading. But, we
> > are going to take it for writing right after exit_ptrace() returns, afaics
> > we can add this fastpatch check for free.
>
> That looks good to me, but it could use some more scare comments.

Good. Hopfully Zhang can test it to confirm it has the same effect.
It should, but I am still wondering about 10% improvement.

> >  /*
> > - * Detach all tasks we were using ptrace on.
> > + * Detach all tasks we were using ptrace on. Called with tasklist held.
>
>  * Called with tasklist held for writing, and returns with it held too.
>  * But note it can release and reacquire the lock.

OK.

> > +	write_lock_irq(&tasklist_lock);
> > +
> 	/*
> 	 * Note that exit_ptrace() might drop tasklist_lock and reacquire it.
> 	 */
> >  	exit_ptrace(father);

Well, this comment a bit "unfair", please see below.

> > -	write_lock_irq(&tasklist_lock);
> >  	reaper = find_new_reaper(father);

Note that find_new_reaper() can drop/reacquire tasklist too.

Perhaps,

	/* These two might drop and reacquire tasklist_lock */
	exit_ptrace(father);
	reaper = find_new_reaper(father);

	...

?

Oleg.

Re: [PATCH] Don't apply for write lock on tasklist_lock if parent doesn't ptrace other processes

[Zhang, Yanmin]

On Thu, 2010-07-22 at 11:05 +0200, Oleg Nesterov wrote:
> I am not surpized perf blaims tasklist, but I am really surpized this patch
> adds 10% improvement...
I changed aim7 workfile to focus on fork/exec and other a couple of sub-cases.
And this behavior is clear on 8-socket machines. 

> 
> On 07/21, Roland McGrath wrote:
> >
> > > > @@ -331,6 +331,9 @@ void exit_ptrace(struct task_struct *tra
> > > >  	struct task_struct *p, *n;
> > > >  	LIST_HEAD(ptrace_dead);
> > > >
> > > > +	if (list_empty(&tracer->ptraced))
> > > > +		return;
> > > > +
> > > >  	write_lock_irq(&tasklist_lock);
> > > >  	list_for_each_entry_safe(p, n, &tracer->ptraced, ptrace_entry) {
> > > >  		if (__ptrace_detach(tracer, p))
> >
> > I think we may have tried that before.  Oleg can tell us if it's really
> > safe vs a race with PTRACE_TRACEME or something like that.
> 
> Yes, this can race with ptrace_traceme(). Without tasklist_lock in
> exit_ptrace(), it is possible that ptrace_traceme() starts __ptrace_link()
> before it sees PF_EXITING, and completes before the result of list_add()
> is visible to the exiting parent. tasklist acts as a barrier.
Thanks for your kind explanation.

> 
> So, this list_empty() check needs taskslit at least for reading. But, we
> are going to take it for writing right after exit_ptrace() returns, afaics
> we can add this fastpatch check for free.
> 
> Uncompiled/untested.
> 
> Oleg.
> 
>  kernel/ptrace.c |   10 +++++++---
>  kernel/exit.c   |    3 ++-
>  2 files changed, 9 insertions(+), 4 deletions(-)
> 
> --- x/kernel/ptrace.c
> +++ x/kernel/ptrace.c
> @@ -324,26 +324,30 @@ int ptrace_detach(struct task_struct *ch
>  }
>  
>  /*
> - * Detach all tasks we were using ptrace on.
> + * Detach all tasks we were using ptrace on. Called with tasklist held.
>   */
>  void exit_ptrace(struct task_struct *tracer)
>  {
>  	struct task_struct *p, *n;
>  	LIST_HEAD(ptrace_dead);
>  
> -	write_lock_irq(&tasklist_lock);
> +	if (likely(list_empty(&tracer->ptraced)))
> +		return;
> +
>  	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);
>  
> +	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);
>  	}
> +
> +	write_lock_irq(&tasklist_lock);
>  }
>  
>  int ptrace_readdata(struct task_struct *tsk, unsigned long src, char __user *dst, int len)
> --- x/kernel/exit.c
> +++ x/kernel/exit.c
> @@ -771,9 +771,10 @@ static void forget_original_parent(struc
After applying my patch (although it's incorrect as there is a race with TRACEME),
perf shows write_lock_irq in forget_original_parent consumes less than 40% cpu time on
8-socket machine.

Is it possible to optimize it to use finer locks instead of the global tasklist_lock?


>  	struct task_struct *p, *n, *reaper;
>  	LIST_HEAD(dead_children);
>  
> +	write_lock_irq(&tasklist_lock);
> +
>  	exit_ptrace(father);
>  
> -	write_lock_irq(&tasklist_lock);
>  	reaper = find_new_reaper(father);
>  
>  	list_for_each_entry_safe(p, n, &father->children, sibling) {
> 

Re: [PATCH] Don't apply for write lock on tasklist_lock if parent doesn't ptrace other processes

[Oleg Nesterov]

On 07/23, Zhang, Yanmin wrote:
>
> On Thu, 2010-07-22 at 11:05 +0200, Oleg Nesterov wrote:
> > I am not surpized perf blaims tasklist, but I am really surpized this patch
> > adds 10% improvement...
> I changed aim7 workfile to focus on fork/exec and other a couple of sub-cases.
> And this behavior is clear on 8-socket machines. 

Thanks...

> After applying my patch (although it's incorrect as there is a race with TRACEME),
> perf shows write_lock_irq in forget_original_parent consumes less than 40% cpu time on
> 8-socket machine.

Any chance you can test the patch I sent? It should have the same effect,
otherwise there is something interesting.

> Is it possible to optimize it to use finer locks instead of the global tasklist_lock?

Heh. We must optimize it. But it is not clear when ;)

Oleg.

Re: [PATCH] Don't apply for write lock on tasklist_lock if parent doesn't ptrace other processes

[Zhang, Yanmin]

On Fri, 2010-07-23 at 19:34 +0200, Oleg Nesterov wrote:
> On 07/23, Zhang, Yanmin wrote:
> >
> > On Thu, 2010-07-22 at 11:05 +0200, Oleg Nesterov wrote:
> > > I am not surpized perf blaims tasklist, but I am really surpized this patch
> > > adds 10% improvement...
> > I changed aim7 workfile to focus on fork/exec and other a couple of sub-cases.
> > And this behavior is clear on 8-socket machines. 
> 
> Thanks...
> 
> > After applying my patch (although it's incorrect as there is a race with TRACEME),
> > perf shows write_lock_irq in forget_original_parent consumes less than 40% cpu time on
> > 8-socket machine.
> 
> Any chance you can test the patch I sent? It should have the same effect,
> otherwise there is something interesting.
1) with my patch, we got about 13% improvement;
2) With your patch, we got about 11% improvement;

Performance is very sensitive to spinlock contention on large machines.
 
> 
> > Is it possible to optimize it to use finer locks instead of the global tasklist_lock?
> 
> Heh. We must optimize it. But it is not clear when ;)
Thanks. It's better to remove the big lock.

Re: [PATCH] Don't apply for write lock on tasklist_lock if parent doesn't ptrace other processes

[Oleg Nesterov]

On 07/26, Zhang, Yanmin wrote:
>
> On Fri, 2010-07-23 at 19:34 +0200, Oleg Nesterov wrote:
> > On 07/23, Zhang, Yanmin wrote:
> > >
> > > After applying my patch (although it's incorrect as there is a race with TRACEME),
> > > perf shows write_lock_irq in forget_original_parent consumes less than 40% cpu time on
> > > 8-socket machine.
> >
> > Any chance you can test the patch I sent? It should have the same effect,
> > otherwise there is something interesting.
> 1) with my patch, we got about 13% improvement;
> 2) With your patch, we got about 11% improvement;
>
> Performance is very sensitive to spinlock contention on large machines.

Zhang, thank you very much.

But. In this case I do not trust these results or I missed something.
I mean, they do not look 100% accurate.

With your patch:

	forget_original_parent:

		exit_ptrace:
			if (list_empty(ptraced))
				return;


		write_lock_irq(tasklist);

		... do a lot more work ...

With my patch:

	forget_original_parent:

		write_lock_irq(tasklist);
	
		exit_ptrace:
			if (list_empty(ptraced))
				return;

		... do a lot more work ...

The only difference is that we are doing the function call + list_empty()
under tasklist, just a few instructions compared to "do a lot more work"
in forget_original_parent().

How this can make the 2% difference ? This looks like a noise to me,
or do you think I missed something?

> > Heh. We must optimize it. But it is not clear when ;)
> Thanks. It's better to remove the big lock.

Yes. The only problem this is very much nontrival with the current code.

Oleg.

RE: [PATCH] Don't apply for write lock on tasklist_lock if parent doesn't ptrace other processes

[Kleen, Andi]

> The only difference is that we are doing the function call +
> list_empty()
> under tasklist, just a few instructions compared to "do a lot more
> work"
> in forget_original_parent().
> 
> How this can make the 2% difference ? This looks like a noise to me,
> or do you think I missed something?

It could be a cache miss or something like that. Instructions are not
all the same cost. Only detailed profiling with different performance counters
could give you more information.

-Andi

Re: [PATCH] Don't apply for write lock on tasklist_lock if parent doesn't ptrace other processes

[Zhang, Yanmin]

On Mon, 2010-07-26 at 10:53 +0200, Oleg Nesterov wrote:
> On 07/26, Zhang, Yanmin wrote:
> >
> > On Fri, 2010-07-23 at 19:34 +0200, Oleg Nesterov wrote:
> > > On 07/23, Zhang, Yanmin wrote:
> > > >
> > > > After applying my patch (although it's incorrect as there is a race with TRACEME),
> > > > perf shows write_lock_irq in forget_original_parent consumes less than 40% cpu time on
> > > > 8-socket machine.
> > >
> > > Any chance you can test the patch I sent? It should have the same effect,
> > > otherwise there is something interesting.
> > 1) with my patch, we got about 13% improvement;
> > 2) With your patch, we got about 11% improvement;
> >
> > Performance is very sensitive to spinlock contention on large machines.
> 
> Zhang, thank you very much.
> 
> But. In this case I do not trust these results or I missed something.
> I mean, they do not look 100% accurate.
> 
> With your patch:
> 
> 	forget_original_parent:
> 
> 		exit_ptrace:
> 			if (list_empty(ptraced))
> 				return;
> 
> 
> 		write_lock_irq(tasklist);
> 
> 		... do a lot more work ...
> 
> With my patch:
> 
> 	forget_original_parent:
> 
> 		write_lock_irq(tasklist);
> 	
> 		exit_ptrace:
> 			if (list_empty(ptraced))
> 				return;
> 
> 		... do a lot more work ...
> 
> The only difference is that we are doing the function call + list_empty()
> under tasklist, just a few instructions compared to "do a lot more work"
> in forget_original_parent().
If considering lock acquire/release on a big machine, plus cache-misses like
what Andi said, the result is reasonable. We did lots of testing on 8-socket
machine. Performance result is very sensitive to lock contentions and cache-misses.


> 
> How this can make the 2% difference ?
I reran the testing for a couple of times to make sure the result is stable.

>  This looks like a noise to me,
> or do you think I missed something?
No, you didn't miss anything. Any patch shouldn't introduce bugs, so your patch is
right and good.

> 
> > > Heh. We must optimize it. But it is not clear when ;)
> > Thanks. It's better to remove the big lock.
> 
> Yes. The only problem this is very much nontrival with the current code.
I agree that would be a big project.

[PATCH] ptrace: optimize exit_ptrace() for the likely case

[Oleg Nesterov]

(replaces ptrace-dont-run-write_locktasklist_lock-if-the-parent-doesnt-ptrace-other-processes.patch)

exit_ptrace() takes tasklist_lock unconditionally. We need this lock
to avoid the race with ptrace_traceme(), it acts as a barrier.

Change its caller, forget_original_parent(), to call exit_ptrace()
under tasklist_lock. Change exit_ptrace() to drop and reacquire this
lock if needed.

This allows us to add the fastpath list_empty(ptraced) check. In the
likely no-tracees case exit_ptrace() just returns and we avoid the
lock() + unlock() sequence.

"Zhang, Yanmin" <yanmin_zhang@linux.intel.com> suggested to add this
check, and he reports that this change adds about 11% improvement in
some tests.

Suggested-and-tested-by: "Zhang, Yanmin" <yanmin_zhang@linux.intel.com>
Signed-off-by: Oleg Nesterov <oleg@redhat.com>
---

 kernel/ptrace.c |   12 +++++++++---
 kernel/exit.c   |    7 +++++--
 2 files changed, 14 insertions(+), 5 deletions(-)

--- 35-rc3/kernel/ptrace.c~exit_ptrace_fastpath_check	2010-05-28 13:41:41.000000000 +0200
+++ 35-rc3/kernel/ptrace.c	2010-07-29 16:37:13.000000000 +0200
@@ -324,26 +324,32 @@ int ptrace_detach(struct task_struct *ch
 }
 
 /*
- * Detach all tasks we were using ptrace on.
+ * Detach all tasks we were using ptrace on. Called with tasklist held
+ * for writing, and returns with it held too. But note it can release
+ * and reacquire the lock.
  */
 void exit_ptrace(struct task_struct *tracer)
 {
 	struct task_struct *p, *n;
 	LIST_HEAD(ptrace_dead);
 
-	write_lock_irq(&tasklist_lock);
+	if (likely(list_empty(&tracer->ptraced)))
+		return;
+
 	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);
 
+	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);
 	}
+
+	write_lock_irq(&tasklist_lock);
 }
 
 int ptrace_readdata(struct task_struct *tsk, unsigned long src, char __user *dst, int len)
--- 35-rc3/kernel/exit.c~exit_ptrace_fastpath_check	2010-05-28 13:41:41.000000000 +0200
+++ 35-rc3/kernel/exit.c	2010-07-29 16:38:37.000000000 +0200
@@ -771,9 +771,12 @@ static void forget_original_parent(struc
 	struct task_struct *p, *n, *reaper;
 	LIST_HEAD(dead_children);
 
-	exit_ptrace(father);
-
 	write_lock_irq(&tasklist_lock);
+	/*
+	 * Note that exit_ptrace() and find_new_reaper() might
+	 * drop tasklist_lock and reacquire it.
+	 */
+	exit_ptrace(father);
 	reaper = find_new_reaper(father);
 
 	list_for_each_entry_safe(p, n, &father->children, sibling) {

Re: [PATCH] ptrace: optimize exit_ptrace() for the likely case

[Roland McGrath]

Acked-by: Roland McGrath <roland@redhat.com>