Skip to contentSkip to conversation

futex_requeue-optimize

RFC PATCH In review Sébastien Dugué 3 participants 9 messages May 10, 2006 – May 12, 2006

lore
Share & tools
lore
#0 lore raw

RFC PATCH 1/2 futex_requeue-optimize

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(-)
kernel/futex.c +8 -5
Index: linux-2.6.16-rt20/kernel/futex.c
===================================================================
@@ -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;
 		}
 	}
 
#1 lore raw
Quoted 27 lines · 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.

...

Index: linux-2.6.16-rt20/kernel/futex.c
===================================================================

kernel/futex.c +8 -2
@@ -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;

kernel/futex.c static int futex_requeue(u32 __user *uad · line 853

Quoted 10 lines
kernel/futex.c +0 -3
 			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?

#2 lore raw
Quoted 1 line · Andrew Morton

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

#3 lore raw
Quoted 6 lines · Ingo Molnar
Quoted 1 line · Andrew Morton

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.

#4 lore raw
Quoted 10 lines · Sébastien Dugué
Quoted 6 lines · Ingo Molnar
Quoted 1 line · Andrew Morton

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.

#5 lore raw
Quoted 9 lines · Sébastien Dugué
Quoted 8 lines · Sébastien Dugué
Quoted 6 lines · Ingo Molnar
Quoted 1 line · Andrew Morton

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.

Quoted 8 lines
Quoted 2 lines

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

#6 lore raw
Quoted 14 lines · Ingo Molnar
Quoted 12 lines · Sébastien Dugué
Quoted 10 lines · Sébastien Dugué
Quoted 6 lines · Ingo Molnar
Quoted 1 line · Andrew Morton

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.

Quoted 9 lines
Quoted 5 lines

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.

#7 lore raw
Quoted 4 lines · Sébastien Dugué

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

#8 lore raw
In reply to Andrew Morton
Quoted 4 lines · Andrew Morton
Quoted 3 lines · Sébastien Dugué
Quoted 8 lines
Quoted 5 lines

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.