sched,rt: enqueue spinlock waiters to the head of their queue
RFC PATCH 1/1 sched,rt: enqueue spinlock waiters to the head of their queue
If a task blocks on a spinlock, give the CPU back as soon as possible so we can turn over the lock as quickly as possible. The task was at HEAD when it blocked, put it back, and tell everyone else to get the hell out of the way.
--- include/linux/sched.h | 1 + kernel/rtmutex.c | 13 +++++++++++-- kernel/sched/core.c | 9 +++++++-- kernel/sched/fair.c | 4 ++++ kernel/sched/rt.c | 29 +++++++++++++++++++++++++++-- 5 files changed, 50 insertions(+), 6 deletions(-)
include/linux/sched.h +1 -0
@@ -1064,6 +1064,7 @@ struct sched_domain;#define WF_FORK 0x02/* child wakeup after fork */ #define WF_MIGRATED 0x04/* internal use, task got migrated */ #define WF_LOCK_SLEEPER 0x08/* wakeup spinlock "sleeper" */ +#define WF_REQUEUE 0x10/* requeue spinlock "sleeper" */ #define ENQUEUE_WAKEUP 1#define ENQUEUE_HEAD 2
kernel/rtmutex.c +11 -2
@@ -722,7 +722,7 @@ static void noinline __sched rt_spin_lo {struct task_struct *lock_owner, *self = current;struct rt_mutex_waiter waiter, *top_waiter; -int ret; +int ret, wait, cpu =raw_smp_processor_id ();rt_mutex_init_waiter (&waiter, true);
@@ -757,12 +757,21 @@ static void noinline __sched rt_spin_lo top_waiter =rt_mutex_top_waiter (lock); lock_owner =rt_mutex_owner (lock); + wait = top_waiter != &waiter; + +/* +* If we preempt the lock owner, just preempt ourselves. +* the now boosted lock owner is queued to queue head. +* When we release the wait lock, lock owner runs. +*/ +if (!wait &&task_cpu (lock_owner) == cpu) +set_tsk_need_resched (self);raw_spin_unlock (&lock->wait_lock);debug_rt_mutex_print_deadlock (&waiter); -if (top_waiter != &waiter ||adaptive_wait (lock, lock_owner)) +if (wait ||adaptive_wait (lock, lock_owner))schedule_rt_mutex (lock);raw_spin_lock (&lock->wait_lock);
kernel/sched/core.c +7 -2
@@ -1611,7 +1611,12 @@ EXPORT_SYMBOL(wake_up_process);*/ int wake_up_lock_sleeper (struct task_struct *p) { -return try_to_wake_up (p,TASK_ALL ,WF_LOCK_SLEEPER ); +int flags =WF_LOCK_SLEEPER ; + +if (rt_task (p)) + flags |=WF_REQUEUE ; + +return try_to_wake_up (p,TASK_ALL , flags); }int wake_up_state (struct task_struct *p,unsigned int state)
@@ -3815,7 +3820,7 @@ void rt_mutex_setprio(struct task_structif (running) p->sched_class->set_curr_task (rq);if (on_rq) -enqueue_task (rq, p, oldprio < prio ?ENQUEUE_HEAD :0 ); +enqueue_task (rq, p,ENQUEUE_HEAD );check_class_changed (rq, p, prev_class, oldprio); out_unlock:
kernel/sched/fair.c +4 -0
@@ -3522,6 +3522,10 @@ static void check_preempt_wakeup(structif (unlikely (se == pse))return ; +/* Preempting SCHED_OTHER lock holders harms throughput for no good reason */ +if (__migrate_disabled (curr)) +return ; +/* * This is possible from callers such as move_task(), in which we * unconditionally check_prempt_curr() after an enqueue (which may have
kernel/sched/rt.c +27 -2
@@ -1180,6 +1180,10 @@ enqueue_task_rt(struct rq *rq, struct taif (flags &ENQUEUE_WAKEUP ) rt_se->timeout =0 ; +/* The wakee is a FIFO lock sleeper */ +if (flags &WF_REQUEUE ) + flags |=ENQUEUE_HEAD ; +enqueue_rt_entity (rt_se, flags &ENQUEUE_HEAD );if (!task_current (rq, p) && p->nr_cpus_allowed >1 )
@@ -1295,8 +1299,29 @@ select_task_rq_rt(struct task_struct *p,return cpu; } -static void check_preempt_equal_prio (struct rq *rq,struct task_struct *p) +static void check_preempt_equal_prio (struct rq *rq,struct task_struct *p,int wake_flags) { +#ifdef CONFIG_PREEMPT_RT_BASE +if (wake_flags &WF_REQUEUE ) { +if (!p->on_cpu) +requeue_task_rt (rq, p,1 ); + +/* +* The lock owner was here first, top waiter +* must follow. If the owner was PI boosted, +* it's gone RSN. All others need to get off +* this CPU ASAP, this waiter had it first. +*/ +if (rq ==this_rq ()) +requeue_task_rt (rq, rq->curr,1 ); +else if (__migrate_disabled (rq->curr)) +set_tsk_need_resched (rq->curr); +else +resched_task (rq->curr); + +return ; + } +#endif if (rq->curr->nr_cpus_allowed ==1 )return ;
@@ -1342,7 +1367,7 @@ static void check_preempt_curr_rt(struct* task. */ if (p->prio == rq->curr->prio && !test_tsk_need_resched (rq->curr)) -check_preempt_equal_prio (rq, p); +check_preempt_equal_prio (rq, p, flags);#endif }
BTW, if I were a reader, I'd be asking "where are the cold hard numbers showing that this is a good thing to do?" They're missing because I don't have any.
This is the fallout from turning spinlocks back into 100% spinning locks for rt explorations, which _can_ improve semop throughput up to 7 fold when combined with a "Ok boss, how long may I spin before I have to check for other runnable tasks at my prio" knob, but which also adds a little overhead to the general case for one (making it a FAIL), and will chew huge amounts of CPU in the heavily contended case just to close off most priority inversions should a high priority task block briefly while there's a low priority task runnable. Preemptible spinning locks are pure evil.
Doing this wake to head _should_ speed up lock turnaround, but I have zero hard evidence that it really makes any difference in practice, so yawn/NAK is perfectly understandable :) These are only the leftover bits that I think might be worth a ponder or two after declaring preemptible spinning locks to be too evil to live.
Quoted 151 lines · Mike Galbraith
If a task blocks on a spinlock, give the CPU back as soon as possible so we can turn over the lock as quickly as possible. The task was at HEAD when it blocked, put it back, and tell everyone else to get the hell out of the way.
Signed-off-by Mike Galbraith <[email protected]>--- include/linux/sched.h | 1 + kernel/rtmutex.c | 13 +++++++++++-- kernel/sched/core.c | 9 +++++++-- kernel/sched/fair.c | 4 ++++ kernel/sched/rt.c | 29 +++++++++++++++++++++++++++-- 5 files changed, 50 insertions(+), 6 deletions(-)include/linux/sched.h +1
-0@@ -1064,6 +1064,7 @@ struct sched_domain;#define WF_FORK 0x02/* child wakeup after fork */ #define WF_MIGRATED 0x04/* internal use, task got migrated */ #define WF_LOCK_SLEEPER 0x08/* wakeup spinlock "sleeper" */ +#define WF_REQUEUE 0x10/* requeue spinlock "sleeper" */ #define ENQUEUE_WAKEUP 1#define ENQUEUE_HEAD 2kernel/rtmutex.c +11
-2@@ -722,7 +722,7 @@ static void noinline __sched rt_spin_lo {struct task_struct *lock_owner, *self = current;struct rt_mutex_waiter waiter, *top_waiter; -int ret; +int ret, wait, cpu =raw_smp_processor_id ();rt_mutex_init_waiter (&waiter, true);@@ -757,12 +757,21 @@ static void noinline __sched rt_spin_lo top_waiter =rt_mutex_top_waiter (lock); lock_owner =rt_mutex_owner (lock); + wait = top_waiter != &waiter; + +/* +* If we preempt the lock owner, just preempt ourselves. +* the now boosted lock owner is queued to queue head. +* When we release the wait lock, lock owner runs. +*/ +if (!wait &&task_cpu (lock_owner) == cpu) +set_tsk_need_resched (self);raw_spin_unlock (&lock->wait_lock);debug_rt_mutex_print_deadlock (&waiter); -if (top_waiter != &waiter ||adaptive_wait (lock, lock_owner)) +if (wait ||adaptive_wait (lock, lock_owner))schedule_rt_mutex (lock);raw_spin_lock (&lock->wait_lock);kernel/sched/core.c +7
-2@@ -1611,7 +1611,12 @@ EXPORT_SYMBOL(wake_up_process);*/ int wake_up_lock_sleeper (struct task_struct *p) { -return try_to_wake_up (p,TASK_ALL ,WF_LOCK_SLEEPER ); +int flags =WF_LOCK_SLEEPER ; + +if (rt_task (p)) + flags |=WF_REQUEUE ; + +return try_to_wake_up (p,TASK_ALL , flags); }int wake_up_state (struct task_struct *p,unsigned int state)@@ -3815,7 +3820,7 @@ void rt_mutex_setprio(struct task_structif (running) p->sched_class->set_curr_task (rq);if (on_rq) -enqueue_task (rq, p, oldprio < prio ?ENQUEUE_HEAD :0 ); +enqueue_task (rq, p,ENQUEUE_HEAD );check_class_changed (rq, p, prev_class, oldprio); out_unlock:kernel/sched/fair.c +4
-0@@ -3522,6 +3522,10 @@ static void check_preempt_wakeup(structif (unlikely (se == pse))return ; +/* Preempting SCHED_OTHER lock holders harms throughput for no good reason */ +if (__migrate_disabled (curr)) +return ; +/* * This is possible from callers such as move_task(), in which we * unconditionally check_prempt_curr() after an enqueue (which may have kernel/sched/rt.c +27
-2@@ -1180,6 +1180,10 @@ enqueue_task_rt(struct rq *rq, struct taif (flags &ENQUEUE_WAKEUP ) rt_se->timeout =0 ; +/* The wakee is a FIFO lock sleeper */ +if (flags &WF_REQUEUE ) + flags |=ENQUEUE_HEAD ; +enqueue_rt_entity (rt_se, flags &ENQUEUE_HEAD );if (!task_current (rq, p) && p->nr_cpus_allowed >1 )@@ -1295,8 +1299,29 @@ select_task_rq_rt(struct task_struct *p,return cpu; } -static void check_preempt_equal_prio (struct rq *rq,struct task_struct *p) +static void check_preempt_equal_prio (struct rq *rq,struct task_struct *p,int wake_flags) { +#ifdef CONFIG_PREEMPT_RT_BASE +if (wake_flags &WF_REQUEUE ) { +if (!p->on_cpu) +requeue_task_rt (rq, p,1 ); + +/* +* The lock owner was here first, top waiter +* must follow. If the owner was PI boosted, +* it's gone RSN. All others need to get off +* this CPU ASAP, this waiter had it first. +*/ +if (rq ==this_rq ()) +requeue_task_rt (rq, rq->curr,1 ); +else if (__migrate_disabled (rq->curr)) +set_tsk_need_resched (rq->curr); +else +resched_task (rq->curr); + +return ; + } +#endif if (rq->curr->nr_cpus_allowed ==1 )return ;@@ -1342,7 +1367,7 @@ static void check_preempt_curr_rt(struct* task. */ if (p->prio == rq->curr->prio && !test_tsk_need_resched (rq->curr)) -check_preempt_equal_prio (rq, p); +check_preempt_equal_prio (rq, p, flags);#endif }
Quoted 4 lines · Mike Galbraith
If a task blocks on a spinlock, give the CPU back as soon as possible so we can turn over the lock as quickly as possible. The task was at HEAD when it blocked, put it back, and tell everyone else to get the hell out of the way.
Hm, seems I may have munged it a little while separating 'good' from 'evil'.
With that patch.
vogelweide:/abuild/mike/:[0]# schedctl -F ./semop-multi 64 64 cpus 64, threads: 64, semaphores: 64, test duration: 30 secs total operations: 15322680, ops/sec 510756 vogelweide:/abuild/mike/:[0]# schedctl -F ./semop-multi 64 64 cpus 64, threads: 64, semaphores: 64, test duration: 30 secs total operations: 15448786, ops/sec 514959 vogelweide:/abuild/mike/:[0]# schedctl -F ./semop-multi 64 64 cpus 64, threads: 64, semaphores: 64, test duration: 30 secs total operations: 15697128, ops/sec 523237
Without the patch.
vogelweide:/abuild/mike/:[0]# schedctl -F ./semop-multi 64 64 cpus 64, threads: 64, semaphores: 64, test duration: 30 secs total operations: 19056218, ops/sec 635207 vogelweide:/abuild/mike/:[0]# schedctl -F ./semop-multi 64 64 cpus 64, threads: 64, semaphores: 64, test duration: 30 secs total operations: 18702572, ops/sec 623419 vogelweide:/abuild/mike/:[0]# schedctl -F ./semop-multi 64 64 cpus 64, threads: 64, semaphores: 64, test duration: 30 secs total operations: 19164792, ops/sec 638826
With spinning spinlocks locks parent patch.
vogelweide:/abuild/mike/:[0]# schedctl -F ./semop-multi 64 64 cpus 64, threads: 64, semaphores: 64, test duration: 30 secs total operations: 37788816, ops/sec 1259627 vogelweide:/abuild/mike/:[0]# schedctl -F ./semop-multi 64 64 cpus 64, threads: 64, semaphores: 64, test duration: 30 secs total operations: 37981322, ops/sec 1266044 vogelweide:/abuild/mike/:[0]# schedctl -F ./semop-multi 64 64 cpus 64, threads: 64, semaphores: 64, test duration: 30 secs total operations: 37840314, ops/sec 1261343
Crap. Bloody mumble mutter rt....
Quoted 146 lines
Signed-off-by Mike Galbraith <[email protected]>--- include/linux/sched.h | 1 + kernel/rtmutex.c | 13 +++++++++++-- kernel/sched/core.c | 9 +++++++-- kernel/sched/fair.c | 4 ++++ kernel/sched/rt.c | 29 +++++++++++++++++++++++++++-- 5 files changed, 50 insertions(+), 6 deletions(-)include/linux/sched.h +1
-0@@ -1064,6 +1064,7 @@ struct sched_domain;#define WF_FORK 0x02/* child wakeup after fork */ #define WF_MIGRATED 0x04/* internal use, task got migrated */ #define WF_LOCK_SLEEPER 0x08/* wakeup spinlock "sleeper" */ +#define WF_REQUEUE 0x10/* requeue spinlock "sleeper" */ #define ENQUEUE_WAKEUP 1#define ENQUEUE_HEAD 2kernel/rtmutex.c +11
-2@@ -722,7 +722,7 @@ static void noinline __sched rt_spin_lo {struct task_struct *lock_owner, *self = current;struct rt_mutex_waiter waiter, *top_waiter; -int ret; +int ret, wait, cpu =raw_smp_processor_id ();rt_mutex_init_waiter (&waiter, true);@@ -757,12 +757,21 @@ static void noinline __sched rt_spin_lo top_waiter =rt_mutex_top_waiter (lock); lock_owner =rt_mutex_owner (lock); + wait = top_waiter != &waiter; + +/* +* If we preempt the lock owner, just preempt ourselves. +* the now boosted lock owner is queued to queue head. +* When we release the wait lock, lock owner runs. +*/ +if (!wait &&task_cpu (lock_owner) == cpu) +set_tsk_need_resched (self);raw_spin_unlock (&lock->wait_lock);debug_rt_mutex_print_deadlock (&waiter); -if (top_waiter != &waiter ||adaptive_wait (lock, lock_owner)) +if (wait ||adaptive_wait (lock, lock_owner))schedule_rt_mutex (lock);raw_spin_lock (&lock->wait_lock);kernel/sched/core.c +7
-2@@ -1611,7 +1611,12 @@ EXPORT_SYMBOL(wake_up_process);*/ int wake_up_lock_sleeper (struct task_struct *p) { -return try_to_wake_up (p,TASK_ALL ,WF_LOCK_SLEEPER ); +int flags =WF_LOCK_SLEEPER ; + +if (rt_task (p)) + flags |=WF_REQUEUE ; + +return try_to_wake_up (p,TASK_ALL , flags); }int wake_up_state (struct task_struct *p,unsigned int state)@@ -3815,7 +3820,7 @@ void rt_mutex_setprio(struct task_structif (running) p->sched_class->set_curr_task (rq);if (on_rq) -enqueue_task (rq, p, oldprio < prio ?ENQUEUE_HEAD :0 ); +enqueue_task (rq, p,ENQUEUE_HEAD );check_class_changed (rq, p, prev_class, oldprio); out_unlock:kernel/sched/fair.c +4
-0@@ -3522,6 +3522,10 @@ static void check_preempt_wakeup(structif (unlikely (se == pse))return ; +/* Preempting SCHED_OTHER lock holders harms throughput for no good reason */ +if (__migrate_disabled (curr)) +return ; +/* * This is possible from callers such as move_task(), in which we * unconditionally check_prempt_curr() after an enqueue (which may have kernel/sched/rt.c +27
-2@@ -1180,6 +1180,10 @@ enqueue_task_rt(struct rq *rq, struct taif (flags &ENQUEUE_WAKEUP ) rt_se->timeout =0 ; +/* The wakee is a FIFO lock sleeper */ +if (flags &WF_REQUEUE ) + flags |=ENQUEUE_HEAD ; +enqueue_rt_entity (rt_se, flags &ENQUEUE_HEAD );if (!task_current (rq, p) && p->nr_cpus_allowed >1 )@@ -1295,8 +1299,29 @@ select_task_rq_rt(struct task_struct *p,return cpu; } -static void check_preempt_equal_prio (struct rq *rq,struct task_struct *p) +static void check_preempt_equal_prio (struct rq *rq,struct task_struct *p,int wake_flags) { +#ifdef CONFIG_PREEMPT_RT_BASE +if (wake_flags &WF_REQUEUE ) { +if (!p->on_cpu) +requeue_task_rt (rq, p,1 ); + +/* +* The lock owner was here first, top waiter +* must follow. If the owner was PI boosted, +* it's gone RSN. All others need to get off +* this CPU ASAP, this waiter had it first. +*/ +if (rq ==this_rq ()) +requeue_task_rt (rq, rq->curr,1 ); +else if (__migrate_disabled (rq->curr)) +set_tsk_need_resched (rq->curr); +else +resched_task (rq->curr); + +return ; + } +#endif if (rq->curr->nr_cpus_allowed ==1 )return ;@@ -1342,7 +1367,7 @@ static void check_preempt_curr_rt(struct* task. */ if (p->prio == rq->curr->prio && !test_tsk_need_resched (rq->curr)) -check_preempt_equal_prio (rq, p); +check_preempt_equal_prio (rq, p, flags);#endif }