futex_requeue-optimize
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
@@ -835,17 +835,20 @@ static int futex_requeue(u32 __user *uadif (++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; } }
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 thefutex_qto 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 *uadif (++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
-3get_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?
Quoted 1 line · Andrew Morton
Should the futex code be using
hlist_headsfor that hashtable?
yeah. That would save 1K of .data on 32-bit platforms, 2K on 64-bit platforms.
Ingo
Quoted 6 lines · Ingo Molnar
Quoted 1 line · Andrew Morton
Should the futex code be using
hlist_headsfor 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.
Quoted 10 lines · Sébastien Dugué
Quoted 6 lines · Ingo Molnar
Quoted 1 line · Andrew Morton
Should the futex code be using
hlist_headsfor 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.
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_headsfor 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
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_headsfor 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.
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
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 thefutex_qto 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.