mutex debug: add generic blocked_on usage
Subsystems (3)
PATCH 1/3 mutex debug: add generic blocked_on usage
There are a couple of blocked on type structures. One for mutexes, and one for rtmutexes, and we also need one for futexes.
Instead of just adding another one to the task struct I combined them all into a union. Since a waiter can only be blocked on one of the types at any given time this should be safe.
I also usurped the pi_lock as the lock which protects all the blocked_on types.
--- include/linux/sched.h | 27 ++++++++++++++++++++++----- kernel/fork.c | 2 -- kernel/mutex-debug.c | 23 +++++++++++++++++------ kernel/mutex-debug.h | 4 +++- kernel/mutex.c | 7 ++++++- 5 files changed, 48 insertions(+), 15 deletions(-)
include/linux/sched.h +22 -5
@@ -1024,6 +1024,21 @@ struct sched_rt_entity {#endif }; +enum lock_waiter_type { +RT_MUTEX_WAITER =1 , +MUTEX_WAITER , +FUTEX_WAITER , +}; + +struct lock_waiter_state { +enum lock_waiter_type lock_type; +union { +struct rt_mutex_waiter *rt_blocked_on; +struct mutex_waiter *mutex_blocked_on; +struct futex_q *futex_blocked_on; + }; +}; +struct task_struct {volatile long state;/* -1 unrunnable, 0 runnable, >0 stopped */ void *stack;
@@ -1201,7 +1216,7 @@ struct task_struct {/* Protection of (de-)allocation: mm, files, fs, tty, keyrings */ spinlock_t alloc_lock; -/* Protection of the PI data structures: */ +/* Protects blocked_on field and PI waiters list. */ spinlock_t pi_lock;#ifdef CONFIG_RT_MUTEXES
@@ -1211,10 +1226,12 @@ struct task_struct {struct rt_mutex_waiter *pi_blocked_on;#endif -#ifdef CONFIG_DEBUG_MUTEXES -/* mutex deadlock detection */ -struct mutex_waiter *blocked_on; -#endif +/* +* Deadlock detection and priority inheritance handling, +* and any other out of line mutex operations +*/ +struct lock_waiter_state *blocked_on; +#ifdef CONFIG_TRACE_IRQFLAGS unsigned int irq_events;int hardirqs_enabled;
kernel/fork.c +0 -2
@@ -1158,9 +1158,7 @@ static struct task_struct *copy_process( p->lockdep_recursion =0 ;#endif -#ifdef CONFIG_DEBUG_MUTEXES p->blocked_on =NULL ;/* not blocked yet */ -#endif /* Perform scheduler related setup. Assign this task to a CPU. */ sched_fork (p, clone_flags);
kernel/mutex-debug.c +17 -6
@@ -52,23 +52,34 @@ void debug_mutex_free_waiter(struct mutememset (waiter,MUTEX_DEBUG_FREE ,sizeof (*waiter)); } -void debug_mutex_add_waiter (struct mutex *lock,struct mutex_waiter *waiter, +void debug_mutex_add_waiter (struct mutex *lock,struct lock_waiter_state *lock_waiter,struct thread_info *ti) { +struct task_struct *task = ti->task; +SMP_DEBUG_LOCKS_WARN_ON (!spin_is_locked (&lock->wait_lock));/* Mark the current thread as blocked on the lock: */ - ti->task->blocked_on = waiter; - waiter->lock = lock; + lock_waiter->mutex_blocked_on->lock = lock; +spin_lock (&task->pi_lock); + task->blocked_on = lock_waiter; +spin_unlock (&task->pi_lock); }void mutex_remove_waiter (struct mutex *lock,struct mutex_waiter *waiter,struct thread_info *ti) { +struct task_struct *task = ti->task; + +spin_lock (&task->pi_lock); +DEBUG_LOCKS_WARN_ON (list_empty (&waiter->list)); -DEBUG_LOCKS_WARN_ON (waiter->task != ti->task); -DEBUG_LOCKS_WARN_ON (ti->task->blocked_on != waiter); - ti->task->blocked_on =NULL ; +DEBUG_LOCKS_WARN_ON (waiter->task != task); +DEBUG_LOCKS_WARN_ON (task->blocked_on !=NULL ); +DEBUG_LOCKS_WARN_ON (task->blocked_on->mutex_blocked_on != waiter); + + task->blocked_on =NULL ; +spin_unlock (&task->pi_lock);list_del_init (&waiter->list); waiter->task =NULL ;
kernel/mutex-debug.h +3 -1
@@ -25,10 +25,12 @@ extern void debug_mutex_lock_common(stru struct mutex_waiter *waiter);extern void debug_mutex_wake_waiter (struct mutex *lock,struct mutex_waiter *waiter); +extern void debug_mutex_free_waiter (struct mutex_waiter *waiter);extern void debug_mutex_add_waiter (struct mutex *lock, -struct mutex_waiter *waiter, +struct lock_waiter_state *lock_waiter,struct thread_info *ti); +extern void mutex_remove_waiter (struct mutex *lock,struct mutex_waiter *waiter,struct thread_info *ti);extern void debug_mutex_unlock (struct mutex *lock);
kernel/mutex.c +6 -1
@@ -131,11 +131,16 @@ __mutex_lock_common(struct mutex *lock,unsigned int old_val;unsigned long flags; +#ifdef CONFIG_DEBUG_MUTEXES +struct lock_waiter_state lock_waiter = + { .lock_type =MUTEX_WAITER , { .mutex_blocked_on = &waiter} }; +#endif +spin_lock_mutex (&lock->wait_lock, flags);debug_mutex_lock_common (lock, &waiter);mutex_acquire (&lock->dep_map, subclass,0 , ip); -debug_mutex_add_waiter (lock, &waiter,task_thread_info (task)); +debug_mutex_add_waiter (lock, &lock_waiter,task_thread_info (task));/* add waiting tasks to the end of the waitqueue (FIFO): */ list_add_tail (&waiter.list, &lock->wait_list);
PATCH 2/3 rtmutex: add generic blocked_on usage
Modify the rtmutex to use the generic blocked_on field.
--- include/linux/sched.h | 2 -- kernel/fork.c | 1 - kernel/rtmutex.c | 35 ++++++++++++++++++++++++----------- 3 files changed, 24 insertions(+), 14 deletions(-)
include/linux/sched.h +0 -2
@@ -1222,8 +1222,6 @@ struct task_struct {#ifdef CONFIG_RT_MUTEXES /* PI waiters blocked on a rt_mutex held by this task */ struct plist_head pi_waiters; -/* Deadlock detection and priority inheritance handling */ -struct rt_mutex_waiter *pi_blocked_on;#endif /*
kernel/fork.c +0 -1
@@ -980,7 +980,6 @@ static void rt_mutex_init_task(struct taspin_lock_init (&p->pi_lock);#ifdef CONFIG_RT_MUTEXES plist_head_init (&p->pi_waiters, &p->pi_lock); - p->pi_blocked_on =NULL ;#endif }
kernel/rtmutex.c +24 -11
@@ -74,6 +74,14 @@ static void fixup_rt_mutex_waiters(strucclear_rt_mutex_waiters (lock); } +static +struct rt_mutex_waiter *rt_mutex_get_waiter (struct task_struct *task) +{ +if (task->blocked_on && task->blocked_on->lock_type ==RT_MUTEX_WAITER ) +return task->blocked_on->rt_blocked_on; +return NULL ; +} +/* * We can speed up the acquire/release, if the architecture * supports cmpxchg and if there's no debugging state to be set up
@@ -197,7 +205,7 @@ static int rt_mutex_adjust_prio_chain(st*/ spin_lock_irqsave (&task->pi_lock, flags); - waiter = task->pi_blocked_on; + waiter =rt_mutex_get_waiter (task);/* * Check whether the end of the boosting chain has been * reached or the state of the chain has changed while we
@@ -411,6 +419,7 @@ static int try_to_take_rt_mutex(struct r*/ static int task_blocks_on_rt_mutex (struct rt_mutex *lock,struct rt_mutex_waiter *waiter, +struct lock_waiter_state *lock_waiter,int detect_deadlock) {struct task_struct *owner =rt_mutex_owner (lock);
@@ -430,7 +439,7 @@ static int task_blocks_on_rt_mutex(struc top_waiter =rt_mutex_top_waiter (lock);plist_add (&waiter->list_entry, &lock->wait_list); - current->pi_blocked_on = waiter; + current->blocked_on = lock_waiter;spin_unlock_irqrestore (¤t->pi_lock, flags);
@@ -440,7 +449,7 @@ static int task_blocks_on_rt_mutex(strucplist_add (&waiter->pi_list_entry, &owner->pi_waiters);__rt_mutex_adjust_prio (owner); -if (owner->pi_blocked_on) +if (rt_mutex_get_waiter (owner)) chain_walk =1 ;spin_unlock_irqrestore (&owner->pi_lock, flags); }
@@ -501,7 +510,7 @@ static void wakeup_next_waiter(struct rtspin_unlock_irqrestore (¤t->pi_lock, flags);/* -* Clear the pi_blocked_on variable and enqueue a possible +* Clear the blocked_on variable and enqueue a possible * waiter into the pi_waiters list of the pending owner. This * prevents that in case the pending owner gets unboosted a * waiter with higher priority than pending-owner->normal_prio
@@ -509,11 +518,12 @@ static void wakeup_next_waiter(struct rt*/ spin_lock_irqsave (&pendowner->pi_lock, flags); -WARN_ON (!pendowner->pi_blocked_on); -WARN_ON (pendowner->pi_blocked_on != waiter); -WARN_ON (pendowner->pi_blocked_on->lock != lock); +WARN_ON (!pendowner->blocked_on); +WARN_ON (pendowner->blocked_on->lock_type !=RT_MUTEX_WAITER ); +WARN_ON (pendowner->blocked_on->rt_blocked_on != waiter); +WARN_ON (pendowner->blocked_on->rt_blocked_on->lock != lock); - pendowner->pi_blocked_on =NULL ; + pendowner->blocked_on =NULL ;if (rt_mutex_has_waiters (lock)) {struct rt_mutex_waiter *next;
@@ -542,7 +552,7 @@ static void remove_waiter(struct rt_mutespin_lock_irqsave (¤t->pi_lock, flags);plist_del (&waiter->list_entry, &lock->wait_list); waiter->task =NULL ; - current->pi_blocked_on =NULL ; + current->blocked_on =NULL ;spin_unlock_irqrestore (¤t->pi_lock, flags);if (first && owner != current) {
@@ -559,7 +569,7 @@ static void remove_waiter(struct rt_mute }__rt_mutex_adjust_prio (owner); -if (owner->pi_blocked_on) +if (rt_mutex_get_waiter (owner)) chain_walk =1 ;spin_unlock_irqrestore (&owner->pi_lock, flags);
@@ -592,7 +602,7 @@ void rt_mutex_adjust_pi(struct task_struspin_lock_irqsave (&task->pi_lock, flags); - waiter = task->pi_blocked_on; + waiter =rt_mutex_get_waiter (task);if (!waiter || waiter->list_entry.prio == task->prio) {spin_unlock_irqrestore (&task->pi_lock, flags);return ;
@@ -614,6 +624,8 @@ rt_mutex_slowlock(struct rt_mutex *lock, int detect_deadlock) {struct rt_mutex_waiter waiter; +struct lock_waiter_state lock_waiter = + { .lock_type =RT_MUTEX_WAITER , { .rt_blocked_on = &waiter} };int ret =0 ;debug_rt_mutex_init_waiter (&waiter);
@@ -663,6 +675,7 @@ rt_mutex_slowlock(struct rt_mutex *lock,*/ if (!waiter.task) { ret =task_blocks_on_rt_mutex (lock, &waiter, + &lock_waiter, detect_deadlock);/* * If we got woken up by the owner then start loop
PATCH 3/3 futex: fix miss ordered wakeups
In reply to Daniel WalkerWhen the plist was added to futexes it added overhead to sort based on priority for the futex waiters. If there is a miss order the value of this, from my perspective, is lost. Since we don't re-order tasks when their priority is changed after they sleep then we get a miss ordered scenerio, and tasks aren't woken in priority order.
This patch corrects this issue, so the tasks are always woken in priority order.
--- include/linux/sched.h | 2 ++ kernel/futex.c | 45 +++++++++++++++++++++++++++++++++++++++++++++ kernel/sched.c | 1 + 3 files changed, 48 insertions(+)
include/linux/sched.h +2 -0
@@ -1664,6 +1664,8 @@ static inline int rt_mutex_getprio(struc# define rt_mutex_adjust_pi (p) do { } while (0)#endif +extern void futex_adjust_waiters (struct task_struct *p); +extern void set_user_nice (struct task_struct *p,long nice);extern int task_prio (const struct task_struct *p);extern int task_nice (const struct task_struct *p);
kernel/futex.c +45 -0
69 lines not on this page · raw message
kernel/sched.c +1 -0
@@ -5209,6 +5209,7 @@ recheck:spin_unlock_irqrestore (&p->pi_lock, flags);rt_mutex_adjust_pi (p); +futex_adjust_waiters (p);return 0 ; }
Re: [PATCH 3/3] futex: fix miss ordered wakeups
Quoted 2 lines · Daniel Walker
This patch corrects this issue, so the tasks are always woken in priority order.
This is completely unnecessary overhead for 99.999% of all cases. It was deliberately not done. You slowing things down for everybody. If you want priorities, then use PI futexes.
Re: [PATCH 3/3] futex: fix miss ordered wakeups
Quoted 7 lines · Ulrich Drepper
Quoted 2 lines · Daniel Walker
This patch corrects this issue, so the tasks are always woken in priority order.
This is completely unnecessary overhead for 99.999% of all cases. It was deliberately not done. You slowing things down for everybody. If you want priorities, then use PI futexes.
That's the problem we aren't just covering 99.99% we're trying to cover 100% of cases.. If we don't do it in that one case we may as well not do it at all.
Daniel
Re: [PATCH 3/3] futex: fix miss ordered wakeups
Quoted 3 lines · Daniel Walker
That's the problem we aren't just covering 99.99% we're trying to cover 100% of cases.. If we don't do it in that one case we may as well not do it at all.
I have no problem with removing the other ordering. It was added because it limited overhead. It is completely wrong to have everybody pay for the needs for a very small minority.
Re: [PATCH 3/3] futex: fix miss ordered wakeups
Quoted 8 lines · Ulrich Drepper
Quoted 3 lines · Daniel Walker
That's the problem we aren't just covering 99.99% we're trying to cover 100% of cases.. If we don't do it in that one case we may as well not do it at all.
I have no problem with removing the other ordering. It was added because it limited overhead. It is completely wrong to have everybody pay for the needs for a very small minority.
I think that ordering is something companies have been wanting for a long time.. I had a lot of people asking about it, I was glad when it was added.. However, it all falls down in the one case which we don't handle.
I don't think the overhead for this is all that bad.. Consider that the worst performance case is the contended case, and this patch adds a very small amount of code. The vast majority of cases are un-contended , and it's already know to be slow in the cases which are contended.
Daniel
Re: [PATCH 3/3] futex: fix miss ordered wakeups
Quoted 2 lines · Daniel Walker
I think that ordering is something companies have been wanting for a long time..
That's your claim. Again, almost nobody outside the realm of embedded fortunately uses priorities. It's a complete waste of time almost all programs, certainly all but one or two on any of my systems.
There is already a solution for priority wakeup. Use it and don't punish everybody else for your needs.
Re: [PATCH 3/3] futex: fix miss ordered wakeups
In reply to Daniel WalkerQuoted 5 lines · Daniel Walker
When the plist was added to futexes it added overhead to sort based on priority for the futex waiters. If there is a miss order the value of this, from my perspective, is lost. Since we don't re-order tasks when their priority is changed after they sleep then we get a miss ordered scenerio, and tasks aren't woken in priority order.
This is a solution looking for a problem.
Normal futexes have no ordering guarantees at all. There is no mechanism to prevent lock stealing from lower priority tasks. So why should we care about the once a year case, where a sleepers priority is modified ?
If you need ordering guarantees then use PI futexes.
Quoted 2 lines
This patch corrects this issue, so the tasks are always woken in priority order.
The patch corrects a non issue and introduces lock order issues:
kernel/futex.c static int get_futex_value_locked(u32 *d · line 362
Quoted 9 lines
kernel/futex.c +8
-0+void futex_adjust_waiters (struct task_struct *p) +{ +spin_lock (&p->pi_lock); +spin_lock (&hb->lock); +spin_unlock (&hb->lock); + } +spin_unlock (&p->pi_lock); +}
vs.
Review static int futex_wait(u32 __user *uaddr,
Quoted 1 line
(quoted diff) +0
-0@@ -1155,6 +1191,8 @@ static int futex_wait(u32 __user *uaddr,
{
....
hb = queue_lock(&q);
kernel/futex.c static int futex_wait(u32 __user *uaddr, · line 1258
Quoted 3 lines
kernel/futex.c +3
-0+spin_lock (¤t->pi_lock); + current->blocked_on = &blocked_on; +spin_unlock (¤t->pi_lock);
There are more issues vs. pi futexes as well. The simple case of futex_wait() vs. futex_adjust_waiters will just upset lockdep, but there are real dealocks vs. unqueue_me_pi waiting.
Thanks,
tglx
Re: [PATCH 3/3] futex: fix miss ordered wakeups
Quoted 4 lines · Thomas Gleixner
Normal futexes have no ordering guarantees at all. There is no mechanism to prevent lock stealing from lower priority tasks. So why should we care about the once a year case, where a sleepers priority is modified ?
Lock stealing? The usage of sched_setscheduler is fairly pervasive in userspace, if a task becomes SCHED_FIFO it did so via sched_setscheduler. So I don't think this is at all "once a year". Tasks shouldn't be forced to determine if a task is sleeping or not before it calls sched_setscheduler.
Quoted 1 line
If you need ordering guarantees then use PI futexes.
There are degree's of overhead with each step.. Someone may not need or want priority inheritance.
Quoted 17 lines
kernel/futex.c static int get_futex_value_locked(u32 *d · line 362
Quoted 9 lines
kernel/futex.c +8
-0+void futex_adjust_waiters (struct task_struct *p) +{ +spin_lock (&p->pi_lock); +spin_lock (&hb->lock); +spin_unlock (&hb->lock); + } +spin_unlock (&p->pi_lock); +}vs.
Review static int futex_wait(u32 __user *uaddr,
Quoted 1 line
(quoted diff) +0
-0@@ -1155,6 +1191,8 @@ static int futex_wait(u32 __user *uaddr,{
....hb = queue_lock(&q);
Quoted 7 lines
kernel/futex.c static int futex_wait(u32 __user *uaddr, · line 1258
Quoted 3 lines
kernel/futex.c +3
-0+spin_lock (¤t->pi_lock); + current->blocked_on = &blocked_on; +spin_unlock (¤t->pi_lock);There are more issues vs. pi futexes as well. The simple case of
futex_wait()vs.futex_adjust_waiterswill just upset lockdep, but there are real dealocks vs.unqueue_me_piwaiting.
You mean the lock ordering would cause the deadlock vs. unqueue_me_pi , or are you talking about something else?
Daniel
Re: [PATCH 3/3] futex: fix miss ordered wakeups
Quoted 8 lines · Daniel Walker
Quoted 4 lines · Thomas Gleixner
Normal futexes have no ordering guarantees at all. There is no mechanism to prevent lock stealing from lower priority tasks. So why should we care about the once a year case, where a sleepers priority is modified ?
Lock stealing?
Do you have the faintest idea how the futex code works at all ? There is no guarantee that the task which is woken up first gets the futex.
A) A task on another CPU can get it independent of its priority
B) In case of multiple waiters wakeup there is no guarantee either
Quoted 3 lines
The usage of
sched_setscheduleris fairly pervasive in userspace, if a task becomesSCHED_FIFOit did so viasched_setscheduler.
Sigh.
sched_setscheduler is usually done during the startup and not in the middle of some operation.
Quoted 3 lines
So I don't think this is at all "once a year". Tasks shouldn't be forced to determine if a task is sleeping or not before it calls
sched_setscheduler.
A sane written program which uses RT priorities does none of this and I don't care about abstruse use cases at all.
Quoted 4 lines
Quoted 1 line
If you need ordering guarantees then use PI futexes.
There are degree's of overhead with each step.. Someone may not need or want priority inheritance.
Then there is no need to add this artifical "correctness" at all.
Quoted 6 lines
Quoted 3 lines
There are more issues vs. pi futexes as well. The simple case of
futex_wait()vs.futex_adjust_waiterswill just upset lockdep, but there are real dealocks vs.unqueue_me_piwaiting.You mean the lock ordering would cause the deadlock vs.
unqueue_me_pi, or are you talking about something else?
Do I write Chinese or what ?
Thanks,
tglx
Re: [PATCH 3/3] futex: fix miss ordered wakeups
Quoted 8 lines · Thomas Gleixner
Quoted 7 lines · Daniel Walker
Quoted 4 lines · Thomas Gleixner
Normal futexes have no ordering guarantees at all. There is no mechanism to prevent lock stealing from lower priority tasks. So why should we care about the once a year case, where a sleepers priority is modified ?
Quoted 4 lines
Quoted 1 line
Lock stealing?
Do you have the faintest idea how the futex code works at all ? There is no guarantee that the task which is woken up first gets the futex.
Thomas if you want to be abusive, talk to someone else.
Quoted 2 lines
A) A task on another CPU can get it independent of its priority
B) In case of multiple waiters wakeup there is no guarantee either
This is how I would imagine the pre-plist code would work.
Quoted 6 lines
Quoted 4 lines
Quoted 1 line
If you need ordering guarantees then use PI futexes.
There are degree's of overhead with each step.. Someone may not need or want priority inheritance.
Then there is no need to add this artifical "correctness" at all.
huh?
Quoted 8 lines
Quoted 6 lines
Quoted 3 lines
There are more issues vs. pi futexes as well. The simple case of
futex_wait()vs.futex_adjust_waiterswill just upset lockdep, but there are real dealocks vs.unqueue_me_piwaiting.You mean the lock ordering would cause the deadlock vs.
unqueue_me_pi, or are you talking about something else?Do I write Chinese or what ?
I guess so ..
Daniel
Re: [PATCH 3/3] futex: fix miss ordered wakeups
Quoted 9 lines · Daniel Walker
Quoted 8 lines · Thomas Gleixner
Quoted 7 lines · Daniel Walker
Quoted 4 lines · Thomas Gleixner
Normal futexes have no ordering guarantees at all. There is no mechanism to prevent lock stealing from lower priority tasks. So why should we care about the once a year case, where a sleepers priority is modified ?
Quoted 6 lines
Quoted 4 lines
Quoted 1 line
Lock stealing?
Do you have the faintest idea how the futex code works at all ? There is no guarantee that the task which is woken up first gets the futex.
Thomas if you want to be abusive, talk to someone else.
See below.
Quoted 4 lines
Quoted 2 lines
A) A task on another CPU can get it independent of its priority
B) In case of multiple waiters wakeup there is no guarantee eitherThis is how I would imagine the pre-plist code would work.
And it works this way even after the plist code.
May I politely suggest, that you carefully read futex_wake() and the corresponding libc implementation and figure out why there is no guarantee and why there can't be one?
Sorry, I'm not abusive. You make claims about correctness and you seem to believe that the plist code gives guarantees except for the setscheduler corner case, but your hypothesis is simply wrong:
There is no kernel side controlled handover of a normal futex. The woken up waiters race for it and a low prio thread on another CPU can steal it even if there is a high prio waiter woken up.
So you try to tell me about the correctness of code where you just imagine how it works.
The plist add on works correct in most of the cases, nothing else. To achieve full correctness there is much more necessary than this setscheduler issue. The plist changes were accepted because the overhead is really minimal, but achieving full correctness would hurt performance badly.
Quoted 10 lines
Quoted 8 lines
Quoted 6 lines
Quoted 3 lines
There are more issues vs. pi futexes as well. The simple case of
futex_wait()vs.futex_adjust_waiterswill just upset lockdep, but there are real dealocks vs.unqueue_me_piwaiting.You mean the lock ordering would cause the deadlock vs.
unqueue_me_pi, or are you talking about something else?Do I write Chinese or what ?
I guess so ..
So maybe you should take some private lessons in Chinese. Then we could easier communicate.
Thanks,
tglx
Re: [PATCH 3/3] futex: fix miss ordered wakeups
Quoted 10 lines · Thomas Gleixner
Quoted 4 lines
Quoted 2 lines
A) A task on another CPU can get it independent of its priority
B) In case of multiple waiters wakeup there is no guarantee eitherThis is how I would imagine the pre-plist code would work.
And it works this way even after the plist code.
May I politely suggest, that you carefully read
futex_wake()and the corresponding libc implementation and figure out why there is no guarantee and why there can't be one?
Sure ..
Quoted 7 lines
Sorry, I'm not abusive. You make claims about correctness and you seem to believe that the plist code gives guarantees except for the setscheduler corner case, but your hypothesis is simply wrong:
There is no kernel side controlled handover of a normal futex. The woken up waiters race for it and a low prio thread on another CPU can steal it even if there is a high prio waiter woken up.
After reading futex_wake, Doesn't it depend how many waiters are woken? Given that comes from userspace, glibc could wake a single waiter and obtain a priority ordering, couldn't it?
Quoted 5 lines
The plist add on works correct in most of the cases, nothing else. To achieve full correctness there is much more necessary than this setscheduler issue. The plist changes were accepted because the overhead is really minimal, but achieving full correctness would hurt performance badly.
If that's the requirement then code that cleans up the corner case that I've identified, which is also minimal should be acceptable .. Since it's meeting the same requirement you layed out above for the original plist changes.
Daniel
Re: [PATCH 3/3] futex: fix miss ordered wakeups
Quoted 7 lines · On Sat, 24 May 2008 12:19:34 -0700 Daniel Walker <[email protected]> wrote:
Quoted 3 lines
There is no kernel side controlled handover of a normal futex. The woken up waiters race for it and a low prio thread on another CPU can steal it even if there is a high prio waiter woken up.
After reading
futex_wake, Doesn't it depend how many waiters are woken? Given that comes from userspace, glibc could wake a single waiter and obtain a priority ordering, couldn't it?
nope. Don't look at the release path... look at the acquire path. If a thread sees the futex is free, it'll take it, without even going to the kernel at all. So you have the situation where the kernel spends a lot of time finding the "perfect" candidate to wake up, but kaboom some other thread just happens to try to get the mutex between the wakeup and the acquire of the wakee.. and just "steal" the lock.