[RFC][PATCH RT 1/2] futex_requeue-optimize

[RFC][PATCH RT 1/2] futex_requeue-optimize

[Sébastien Dugué]

  In futex_requeue(), when the 2 futexes keys hash to the same bucket, there
is no need to move the futex_q to the end of the bucket list.

 futex.c |   13 ++++++++-----
 1 files changed, 8 insertions(+), 5 deletions(-)

Signed-off-by: Sébastien Dugué <sebastien.dugue@bull.net>

Index: linux-2.6.16-rt20/kernel/futex.c
===================================================================
--- linux-2.6.16-rt20.orig/kernel/futex.c	2006-05-04 10:58:38.000000000 +0200
+++ linux-2.6.16-rt20/kernel/futex.c	2006-05-04 10:58:55.000000000 +0200
@@ -835,17 +835,20 @@ static int futex_requeue(u32 __user *uad
 		if (++ret <= nr_wake) {
 			wake_futex(this);
 		} else {
-			list_move_tail(&this->list, &hb2->chain);
-			this->lock_ptr = &hb2->lock;
+			/*
+			 * If key1 and key2 hash to the same bucket, no
+			 * need to requeue.
+			 */
+			if (likely(head1 != &hb2->chain)) {
+				list_move_tail(&this->list, &hb2->chain);
+				this->lock_ptr = &hb2->lock;
+			}
 			this->key = key2;
 			get_key_refs(&key2);
 			drop_count++;
 
 			if (ret - nr_wake >= nr_requeue)
 				break;
-			/* Make sure to stop if key1 == key2: */
-			if (head1 == &hb2->chain && head1 != &next->list)
-				head1 = &this->list;
 		}
 	}
 

Re: [RFC][PATCH RT 1/2] futex_requeue-optimize

[Andrew Morton]

Sébastien Dugué <sebastien.dugue@bull.net> wrote:
>
> 
> 
>   In futex_requeue(), when the 2 futexes keys hash to the same bucket, there
> is no need to move the futex_q to the end of the bucket list.
> 
> ...
> 
> Index: linux-2.6.16-rt20/kernel/futex.c
> ===================================================================
> --- linux-2.6.16-rt20.orig/kernel/futex.c	2006-05-04 10:58:38.000000000 +0200
> +++ linux-2.6.16-rt20/kernel/futex.c	2006-05-04 10:58:55.000000000 +0200
> @@ -835,17 +835,20 @@ static int futex_requeue(u32 __user *uad
>  		if (++ret <= nr_wake) {
>  			wake_futex(this);
>  		} else {
> -			list_move_tail(&this->list, &hb2->chain);
> -			this->lock_ptr = &hb2->lock;
> +			/*
> +			 * If key1 and key2 hash to the same bucket, no
> +			 * need to requeue.
> +			 */
> +			if (likely(head1 != &hb2->chain)) {
> +				list_move_tail(&this->list, &hb2->chain);
> +				this->lock_ptr = &hb2->lock;
> +			}
>  			this->key = key2;
>  			get_key_refs(&key2);
>  			drop_count++;
>  
>  			if (ret - nr_wake >= nr_requeue)
>  				break;
> -			/* Make sure to stop if key1 == key2: */
> -			if (head1 == &hb2->chain && head1 != &next->list)
> -				head1 = &this->list;
>  		}
>  	}

For some reason I get a reject when applying this.  Which is odd, because I
see no differences in there.  Oh well - please try to work out what went
wrong and double-check that the patch which I applied still makes sense.

Should the futex code be using hlist_heads for that hashtable?

Re: [RFC][PATCH RT 1/2] futex_requeue-optimize

[Ingo Molnar]

* Andrew Morton <akpm@osdl.org> wrote:

> Should the futex code be using hlist_heads for that hashtable?

yeah. That would save 1K of .data on 32-bit platforms, 2K on 64-bit 
platforms.

	Ingo

Re: [RFC][PATCH RT 1/2] futex_requeue-optimize

[Sébastien Dugué]

On Thu, 2006-05-11 at 09:15 -0700, Andrew Morton wrote:
> Sébastien Dugué <sebastien.dugue@bull.net> wrote:
> >
> > 
> > 
> >   In futex_requeue(), when the 2 futexes keys hash to the same bucket, there
> > is no need to move the futex_q to the end of the bucket list.
> > 
> > ...
> > 
> For some reason I get a reject when applying this.  Which is odd, because I
> see no differences in there.  Oh well - please try to work out what went
> wrong and double-check that the patch which I applied still makes sense.

  Yep, it's due to the futex_hash_bucket renaming from ->bh to ->hb that
went into pi-futex-futex-code-cleanups.patch from the PI-futex
patchset - no harm.

  Sébastien.

Re: [RFC][PATCH RT 1/2] futex_requeue-optimize

[Sébastien Dugué]

On Fri, 2006-05-12 at 08:32 +0200, Ingo Molnar wrote:
> * Andrew Morton <akpm@osdl.org> wrote:
> 
> > Should the futex code be using hlist_heads for that hashtable?
> 
> yeah. That would save 1K of .data on 32-bit platforms, 2K on 64-bit 
> platforms.

  I'll try to look into this.

  Sébastien.

Re: [RFC][PATCH RT 1/2] futex_requeue-optimize

[Ingo Molnar]

* Sébastien Dugué <sebastien.dugue@bull.net> wrote:

> On Fri, 2006-05-12 at 10:10 +0200, Sébastien Dugué wrote:
> > On Fri, 2006-05-12 at 08:32 +0200, Ingo Molnar wrote:
> > > * Andrew Morton <akpm@osdl.org> wrote:
> > > 
> > > > Should the futex code be using hlist_heads for that hashtable?
> > > 
> > > yeah. That would save 1K of .data on 32-bit platforms, 2K on 64-bit 
> > > platforms.
> > 
> >   I'll try to look into this.
> > 
> 
>   Well, moving the hash bucket list to an hlist may save a few bytes 
> on .data, but all the insertions are done at the tail on this list 
> which would not be easily done using hlists.
> 
>   Any thoughts?

just queue to the head. This is a hash-list, ordering has only 
performance effects.

	Ingo

Re: [RFC][PATCH RT 1/2] futex_requeue-optimize

[Sébastien Dugué]

On Fri, 2006-05-12 at 10:10 +0200, Sébastien Dugué wrote:
> On Fri, 2006-05-12 at 08:32 +0200, Ingo Molnar wrote:
> > * Andrew Morton <akpm@osdl.org> wrote:
> > 
> > > Should the futex code be using hlist_heads for that hashtable?
> > 
> > yeah. That would save 1K of .data on 32-bit platforms, 2K on 64-bit 
> > platforms.
> 
>   I'll try to look into this.
> 

  Well, moving the hash bucket list to an hlist may save a few bytes on
.data, but all the insertions are done at the tail on this list which
would not be easily done using hlists.

  Any thoughts?

  Sébastien.

Re: [RFC][PATCH RT 1/2] futex_requeue-optimize

[Sébastien Dugué]

On Fri, 2006-05-12 at 13:12 +0200, Ingo Molnar wrote:
> * Sébastien Dugué <sebastien.dugue@bull.net> wrote:
> 
> > On Fri, 2006-05-12 at 10:10 +0200, Sébastien Dugué wrote:
> > > On Fri, 2006-05-12 at 08:32 +0200, Ingo Molnar wrote:
> > > > * Andrew Morton <akpm@osdl.org> wrote:
> > > > 
> > > > > Should the futex code be using hlist_heads for that hashtable?
> > > > 
> > > > yeah. That would save 1K of .data on 32-bit platforms, 2K on 64-bit 
> > > > platforms.
> > > 
> > >   I'll try to look into this.
> > > 
> > 
> >   Well, moving the hash bucket list to an hlist may save a few bytes 
> > on .data, but all the insertions are done at the tail on this list 
> > which would not be easily done using hlists.
> > 
> >   Any thoughts?
> 
> just queue to the head. This is a hash-list, ordering has only 
> performance effects.
> 

  Queuing to the head would mean that tasks are woken up in LIFO order
(i.e. the last task put to sleep will be the first to be woken up).
  I'm not sure that's what people would expect, or am I missing
something here?

  Sébastien.

Re: [RFC][PATCH RT 1/2] futex_requeue-optimize

[Ingo Molnar]

* Sébastien Dugué <sebastien.dugue@bull.net> wrote:

>   Queuing to the head would mean that tasks are woken up in LIFO order 
> (i.e. the last task put to sleep will be the first to be woken up).
>   I'm not sure that's what people would expect, or am I missing 
> something here?

hm, indeed, you are right. So a double-linked list head it has to be.

	Ingo