[PATCH 2.6.21-rc3-mm2 1/4] futex priority based wakeup
Today, all threads waiting for a given futex are woken in FIFO order (first
waiter woken first) instead of priority order.
This patch makes use of plist (pirotity ordered lists) instead of simple list in
futex_hash_bucket.
All non-RT threads are stored with priority MAX_RT_PRIO, causing them to be
woken last, in FIFO order (RT-threads are woken first, in priority order).
Signed-off-by: Sébastien Dugué <[EMAIL PROTECTED]>
Signed-off-by: Pierre Peiffer <[EMAIL PROTECTED]>
---
kernel/futex.c | 78 +++--
1 file changed, 49 insertions(+), 29 deletions(-)
Index: b/kernel/futex.c
===
--- a/kernel/futex.c
+++ b/kernel/futex.c
@@ -81,12 +81,12 @@ struct futex_pi_state {
* we can wake only the relevant ones (hashed queues may be shared).
*
* A futex_q has a woken state, just like tasks have TASK_RUNNING.
- * It is considered woken when list_empty(>list) || q->lock_ptr == 0.
+ * It is considered woken when plist_node_empty(>list) || q->lock_ptr == 0.
* The order of wakup is always to make the first condition true, then
* wake up q->waiters, then make the second condition true.
*/
struct futex_q {
- struct list_head list;
+ struct plist_node list;
wait_queue_head_t waiters;
/* Which hash list lock to use: */
@@ -108,8 +108,8 @@ struct futex_q {
* Split the global futex_lock into every hash list lock.
*/
struct futex_hash_bucket {
- spinlock_t lock;
- struct list_head chain;
+ spinlock_t lock;
+ struct plist_head chain;
};
static struct futex_hash_bucket futex_queues[1key, >key)) {
/*
* Another waiter already exists - bump up
@@ -513,12 +513,12 @@ lookup_pi_state(u32 uval, struct futex_h
*/
static void wake_futex(struct futex_q *q)
{
- list_del_init(>list);
+ plist_del(>list, >list.plist);
if (q->filp)
send_sigio(>filp->f_owner, q->fd, POLL_IN);
/*
* The lock in wake_up_all() is a crucial memory barrier after the
-* list_del_init() and also before assigning to q->lock_ptr.
+* plist_del() and also before assigning to q->lock_ptr.
*/
wake_up_all(>waiters);
/*
@@ -631,7 +631,7 @@ static int futex_wake(u32 __user *uaddr,
{
struct futex_hash_bucket *hb;
struct futex_q *this, *next;
- struct list_head *head;
+ struct plist_head *head;
union futex_key key;
int ret;
@@ -645,7 +645,7 @@ static int futex_wake(u32 __user *uaddr,
spin_lock(>lock);
head = >chain;
- list_for_each_entry_safe(this, next, head, list) {
+ plist_for_each_entry_safe(this, next, head, list) {
if (match_futex (>key, )) {
if (this->pi_state) {
ret = -EINVAL;
@@ -673,7 +673,7 @@ futex_wake_op(u32 __user *uaddr1, u32 __
{
union futex_key key1, key2;
struct futex_hash_bucket *hb1, *hb2;
- struct list_head *head;
+ struct plist_head *head;
struct futex_q *this, *next;
int ret, op_ret, attempt = 0;
@@ -746,7 +746,7 @@ retry:
head = >chain;
- list_for_each_entry_safe(this, next, head, list) {
+ plist_for_each_entry_safe(this, next, head, list) {
if (match_futex (>key, )) {
wake_futex(this);
if (++ret >= nr_wake)
@@ -758,7 +758,7 @@ retry:
head = >chain;
op_ret = 0;
- list_for_each_entry_safe(this, next, head, list) {
+ plist_for_each_entry_safe(this, next, head, list) {
if (match_futex (>key, )) {
wake_futex(this);
if (++op_ret >= nr_wake2)
@@ -785,7 +785,7 @@ static int futex_requeue(u32 __user *uad
{
union futex_key key1, key2;
struct futex_hash_bucket *hb1, *hb2;
- struct list_head *head1;
+ struct plist_head *head1;
struct futex_q *this, *next;
int ret, drop_count = 0;
@@ -834,7 +834,7 @@ static int futex_requeue(u32 __user *uad
}
head1 = >chain;
- list_for_each_entry_safe(this, next, head1, list) {
+ plist_for_each_entry_safe(this, next, head1, list) {
if (!match_futex (>key, ))
continue;
if (++ret <= nr_wake) {
@@ -845,9 +845,13 @@ static int futex_requeue(u32 __user *uad
* requeue.
*/
if (likely(head1 != >chain)) {
- list_move_tail(>list, >chain);
+
[PATCH 2.6.21-rc3-mm2 1/4] futex priority based wakeup
Today, all threads waiting for a given futex are woken in FIFO order (first
waiter woken first) instead of priority order.
This patch makes use of plist (pirotity ordered lists) instead of simple list in
futex_hash_bucket.
All non-RT threads are stored with priority MAX_RT_PRIO, causing them to be
woken last, in FIFO order (RT-threads are woken first, in priority order).
Signed-off-by: Sébastien Dugué [EMAIL PROTECTED]
Signed-off-by: Pierre Peiffer [EMAIL PROTECTED]
---
kernel/futex.c | 78 +++--
1 file changed, 49 insertions(+), 29 deletions(-)
Index: b/kernel/futex.c
===
--- a/kernel/futex.c
+++ b/kernel/futex.c
@@ -81,12 +81,12 @@ struct futex_pi_state {
* we can wake only the relevant ones (hashed queues may be shared).
*
* A futex_q has a woken state, just like tasks have TASK_RUNNING.
- * It is considered woken when list_empty(q-list) || q-lock_ptr == 0.
+ * It is considered woken when plist_node_empty(q-list) || q-lock_ptr == 0.
* The order of wakup is always to make the first condition true, then
* wake up q-waiters, then make the second condition true.
*/
struct futex_q {
- struct list_head list;
+ struct plist_node list;
wait_queue_head_t waiters;
/* Which hash list lock to use: */
@@ -108,8 +108,8 @@ struct futex_q {
* Split the global futex_lock into every hash list lock.
*/
struct futex_hash_bucket {
- spinlock_t lock;
- struct list_head chain;
+ spinlock_t lock;
+ struct plist_head chain;
};
static struct futex_hash_bucket futex_queues[1FUTEX_HASHBITS];
@@ -443,13 +443,13 @@ lookup_pi_state(u32 uval, struct futex_h
{
struct futex_pi_state *pi_state = NULL;
struct futex_q *this, *next;
- struct list_head *head;
+ struct plist_head *head;
struct task_struct *p;
pid_t pid;
head = hb-chain;
- list_for_each_entry_safe(this, next, head, list) {
+ plist_for_each_entry_safe(this, next, head, list) {
if (match_futex(this-key, me-key)) {
/*
* Another waiter already exists - bump up
@@ -513,12 +513,12 @@ lookup_pi_state(u32 uval, struct futex_h
*/
static void wake_futex(struct futex_q *q)
{
- list_del_init(q-list);
+ plist_del(q-list, q-list.plist);
if (q-filp)
send_sigio(q-filp-f_owner, q-fd, POLL_IN);
/*
* The lock in wake_up_all() is a crucial memory barrier after the
-* list_del_init() and also before assigning to q-lock_ptr.
+* plist_del() and also before assigning to q-lock_ptr.
*/
wake_up_all(q-waiters);
/*
@@ -631,7 +631,7 @@ static int futex_wake(u32 __user *uaddr,
{
struct futex_hash_bucket *hb;
struct futex_q *this, *next;
- struct list_head *head;
+ struct plist_head *head;
union futex_key key;
int ret;
@@ -645,7 +645,7 @@ static int futex_wake(u32 __user *uaddr,
spin_lock(hb-lock);
head = hb-chain;
- list_for_each_entry_safe(this, next, head, list) {
+ plist_for_each_entry_safe(this, next, head, list) {
if (match_futex (this-key, key)) {
if (this-pi_state) {
ret = -EINVAL;
@@ -673,7 +673,7 @@ futex_wake_op(u32 __user *uaddr1, u32 __
{
union futex_key key1, key2;
struct futex_hash_bucket *hb1, *hb2;
- struct list_head *head;
+ struct plist_head *head;
struct futex_q *this, *next;
int ret, op_ret, attempt = 0;
@@ -746,7 +746,7 @@ retry:
head = hb1-chain;
- list_for_each_entry_safe(this, next, head, list) {
+ plist_for_each_entry_safe(this, next, head, list) {
if (match_futex (this-key, key1)) {
wake_futex(this);
if (++ret = nr_wake)
@@ -758,7 +758,7 @@ retry:
head = hb2-chain;
op_ret = 0;
- list_for_each_entry_safe(this, next, head, list) {
+ plist_for_each_entry_safe(this, next, head, list) {
if (match_futex (this-key, key2)) {
wake_futex(this);
if (++op_ret = nr_wake2)
@@ -785,7 +785,7 @@ static int futex_requeue(u32 __user *uad
{
union futex_key key1, key2;
struct futex_hash_bucket *hb1, *hb2;
- struct list_head *head1;
+ struct plist_head *head1;
struct futex_q *this, *next;
int ret, drop_count = 0;
@@ -834,7 +834,7 @@ static int futex_requeue(u32 __user *uad
}
head1 = hb1-chain;
- list_for_each_entry_safe(this, next, head1, list) {
+ plist_for_each_entry_safe(this, next, head1, list) {
if (!match_futex (this-key, key1))
