Reduce runqueue lock contention -v2
Subsystems (5)
cover Reduce runqueue lock contention -v2
Hi, here a new posting of my scary patch(es) ;-)
These actually survive a sembench run (and everything else I threw at it). The discussion between Mike and Frank over the task_running() check made me realize what was wrong with the previous one.
As it turns out, what was needed (p->oncpu) was something Thomas wanted me to do for an entirely different reason (see patch #2).
Frank's patch, while encouraging me to poke at it again, has a number of very fundamental problems with it, the most serious one being that it completely wrecks the wake-up load-balancing.
I'll try and come up with a way to unwreck the 32bit select_task_rq_fair() problem, but for now inspiration in that departments seems lacking, yet I still wanted to share these patches so that others can have a go at them.
If all you care about is the numbers, skip to patch #5.
RFC PATCH 1/5 sched: Always provide p->oncpu
Always provide p->oncpu so that we can determine if its on a cpu without having to lock the rq.
--- include/linux/sched.h | 2 -- kernel/sched.c | 36 ++++++++++++++++++++++++------------ 2 files changed, 24 insertions(+), 14 deletions(-)
kernel/sched.c +24 -12
@@ -850,18 +850,39 @@ static inline int task_current(struct rqreturn rq->curr == p; } -#ifndef __ARCH_WANT_UNLOCKED_CTXSWstatic inline int task_running (struct rq *rq,struct task_struct *p) { +#ifdef CONFIG_SMP +return p->oncpu; +#else return task_current (rq, p); +#endif } +#ifndef __ARCH_WANT_UNLOCKED_CTXSWstatic inline void prepare_lock_switch (struct rq *rq,struct task_struct *next) { +#ifdef CONFIG_SMP +/* +* We can optimise this out completely for !SMP, because the +* SMP rebalancing from interrupt is the only thing that cares +* here. +*/ + next->oncpu =1 ; +#endif }static inline void finish_lock_switch (struct rq *rq,struct task_struct *prev) { +#ifdef CONFIG_SMP +/* +* After ->oncpu is cleared, the task can be moved to a different CPU. +* We must ensure this doesn't happen until the switch is completely +* finished. +*/ +smp_wmb (); + prev->oncpu =0 ; +#endif #ifdef CONFIG_DEBUG_SPINLOCK /* this is a valid case when another task releases the spinlock */ rq->lock.owner = current;
@@ -877,15 +898,6 @@ static inline void finish_lock_switch(st }#else /* __ARCH_WANT_UNLOCKED_CTXSW */ -static inline int task_running (struct rq *rq,struct task_struct *p) -{ -#ifdef CONFIG_SMP -return p->oncpu; -#else -return task_current (rq, p); -#endif -} -static inline void prepare_lock_switch (struct rq *rq,struct task_struct *next) {#ifdef CONFIG_SMP
@@ -2589,7 +2601,7 @@ void sched_fork(struct task_struct *p, iif (likely (sched_info_on ()))memset (&p->sched_info,0 ,sizeof (p->sched_info));#endif -#if defined(CONFIG_SMP ) && defined(__ARCH_WANT_UNLOCKED_CTXSW) +#if defined(CONFIG_SMP ) p->oncpu =0 ;#endif #ifdef CONFIG_PREEMPT
@@ -5502,7 +5514,7 @@ void __cpuinit init_idle(struct task_strrcu_read_unlock (); rq->curr = rq->idle = idle; -#if defined(CONFIG_SMP ) && defined(__ARCH_WANT_UNLOCKED_CTXSW) +#if defined(CONFIG_SMP ) idle->oncpu =1 ;#endif raw_spin_unlock_irqrestore (&rq->lock, flags);
include/linux/sched.h +0 -2
@@ -1198,10 +1198,8 @@ struct task_struct {int lock_depth;/* BKL lock depth */ #ifdef CONFIG_SMP -#ifdef __ARCH_WANT_UNLOCKED_CTXSWint oncpu;#endif -#endif int prio, static_prio, normal_prio;unsigned int rt_priority;
Re: [RFC][PATCH 1/5] sched: Always provide p->oncpu
Quoted 4 lines · Peter Zijlstra
Always provide
p->oncpuso that we can determine if its on a cpu without having to lock the rq.Signed-off-by Peter Zijlstra <[email protected]>
Looks good to me.
RFC PATCH 2/5 mutex: Use p->oncpu for the adaptive spin
In reply to Peter ZijlstraSince we now have p->oncpu unconditionally available, use it to spin on.
--- include/linux/mutex.h | 2 - include/linux/sched.h | 2 - kernel/mutex-debug.c | 2 - kernel/mutex-debug.h | 2 - kernel/mutex.c | 2 - kernel/mutex.h | 2 - kernel/sched.c | 52 +++++++++++++------------------------------------- 7 files changed, 20 insertions(+), 44 deletions(-)
include/linux/mutex.h +1 -1
@@ -51,7 +51,7 @@ struct mutex {spinlock_t wait_lock;struct list_head wait_list;#if defined(CONFIG_DEBUG_MUTEXES ) || defined(CONFIG_SMP ) -struct thread_info *owner; +struct task_struct *owner;#endif #ifdef CONFIG_DEBUG_MUTEXES const char *name;
kernel/mutex-debug.c +1 -1
@@ -75,7 +75,7 @@ void debug_mutex_unlock(struct mutex *loreturn ;DEBUG_LOCKS_WARN_ON (lock->magic != lock); -DEBUG_LOCKS_WARN_ON (lock->owner !=current_thread_info ()); +DEBUG_LOCKS_WARN_ON (lock->owner != current);DEBUG_LOCKS_WARN_ON (!lock->wait_list.prev && !lock->wait_list.next);mutex_clear_owner (lock); }
kernel/mutex-debug.h +1 -1
@@ -29,7 +29,7 @@ extern void debug_mutex_init(struct mutestatic inline void mutex_set_owner (struct mutex *lock) { - lock->owner =current_thread_info (); + lock->owner = current; }static inline void mutex_clear_owner (struct mutex *lock)
kernel/mutex.c +1 -1
@@ -160,7 +160,7 @@ __mutex_lock_common(struct mutex *lock,*/ for (;;) { -struct thread_info *owner; +struct task_struct *owner;/* * If we own the BKL, then don't spin. The owner of
kernel/mutex.h +1 -1
@@ -19,7 +19,7 @@#ifdef CONFIG_SMP static inline void mutex_set_owner (struct mutex *lock) { - lock->owner =current_thread_info (); + lock->owner = current; }static inline void mutex_clear_owner (struct mutex *lock)
kernel/sched.c +14 -38
76 lines not on this page · raw message
include/linux/sched.h +1 -1
@@ -360,7 +360,7 @@ extern signed long schedule_timeout_inteextern signed long schedule_timeout_killable (signed long timeout);extern signed long schedule_timeout_uninterruptible (signed long timeout); asmlinkage void schedule(void); -extern int mutex_spin_on_owner (struct mutex *lock,struct thread_info *owner); +extern int mutex_spin_on_owner (struct mutex *lock,struct task_struct *owner);struct nsproxy ;struct user_namespace ;
Re: [RFC][PATCH 2/5] mutex: Use p->oncpu for the adaptive spin
Quoted 40 lines · Peter Zijlstra
kernel/sched.c +3
-26@@ -3867,52 +3866,29 @@ int mutex_spin_on_owner(struct mutex *lo* DEBUG_PAGEALLOC could have unmapped it if * the mutex owner just released it and exited. */ -if (probe_kernel_address (&owner->cpu, cpu)) +if (probe_kernel_address (&owner->oncpu, oncpu))return 0 ;#else - cpu = owner->cpu; + oncpu = owner->oncpu;#endif -/* -* Even if the access succeeded (likely case), -* the cpu field may no longer be valid. -*/ -if (cpu >= nr_cpumask_bits) -return 0 ; - -/* -* We need to validate that we can do a -* get_cpu() and that we have the percpu area. -*/ -if (!cpu_online (cpu)) +if (!oncpu)return 0 ; - rq =cpu_rq (cpu); - -for (;;) { -/* -* Owner changed, break to re-assess state. -*/ -if (lock->owner != owner) { -/* -* If the lock has switched to a different owner, -* we likely have heavy contention. Return 0 to quit -* optimistic spinning and not contend further: -*/
kernel/sched.c int mutex_spin_on_owner(struct mutex *lo · line 3878
Quoted 10 lines
kernel/sched.c +1
-9-if (lock->owner) -return 0 ; -break ; - } - -/* -* Is that owner really running on that cpu? -*/ -if (task_thread_info (rq->curr) != owner ||need_resched ()) +while (lock->owner == owner && owner->oncpu) {
It seems, this owner->oncpu dereference needs probe_kernel_address() too. Of course, only in theory.
OTOH, I do not understand why we need the first "if (!oncpu)" check (and "int oncpu" at all).
Oleg.
Re: [RFC][PATCH 2/5] mutex: Use p->oncpu for the adaptive spin
Quoted 15 lines · Oleg Nesterov
Quoted 14 lines · Peter Zijlstra
(quoted diff) +3
-0@@ -3867,52 +3866,29 @@ int mutex_spin_on_owner(struct mutex *lo * DEBUG_PAGEALLOC could have unmapped it if * the mutex owner just released it and exited. */ + if (probe_kernel_address(&owner->oncpu, oncpu)) return 0; #else + oncpu = owner->oncpu; #endif + if (!oncpu) return 0;
Quoted 7 lines
Review int mutex_spin_on_owner(struct mutex *lo · line 3878
Quoted 1 line
(quoted diff) +1
-0+ while (lock->owner == owner && owner->oncpu) {It seems, this
owner->oncpudereference needsprobe_kernel_address()too. Of course, only in theory.OTOH, I do not understand why we need the first "if (!oncpu)" check (and "int oncpu" at all).
Probably because I got my head in a twist.. I wanted to keep the probe_kernel_address() stuff there so that we wouldn't dereference a dead owner pointer, however..
I then later figured that the: lock->owner == owner, test is already sufficient for that, if owner died and went away, it would have released the mutex already (unless something really bad happened, in which case this wouldn't be the first explosion).
So yea, I think we can simplify all this even further, but we do need a smp_rmb() in between those two checks, hmm, and RCU.
How about this?
---
Subject: mutex: Use p->oncpu for the adaptive spin
From: Peter Zijlstra <[email protected]>
Date: Wed Dec 15 18:37:21 CET 2010
Since we no have p->oncpu unconditionally available, use it to spin on.
LKML-Reference: <new-submission>
--- include/linux/mutex.h | 2 - include/linux/sched.h | 2 - kernel/mutex-debug.c | 2 - kernel/mutex-debug.h | 2 - kernel/mutex.c | 2 - kernel/mutex.h | 2 - kernel/sched.c | 87 +++++++++++++++++++++----------------------------- 7 files changed, 43 insertions(+), 56 deletions(-)
include/linux/mutex.h +1 -1
@@ -51,7 +51,7 @@ struct mutex {spinlock_t wait_lock;struct list_head wait_list;#if defined(CONFIG_DEBUG_MUTEXES ) || defined(CONFIG_SMP ) -struct thread_info *owner; +struct task_struct *owner;#endif #ifdef CONFIG_DEBUG_MUTEXES const char *name;
kernel/mutex-debug.c +1 -1
@@ -75,7 +75,7 @@ void debug_mutex_unlock(struct mutex *loreturn ;DEBUG_LOCKS_WARN_ON (lock->magic != lock); -DEBUG_LOCKS_WARN_ON (lock->owner !=current_thread_info ()); +DEBUG_LOCKS_WARN_ON (lock->owner != current);DEBUG_LOCKS_WARN_ON (!lock->wait_list.prev && !lock->wait_list.next);mutex_clear_owner (lock); }
kernel/mutex-debug.h +1 -1
@@ -29,7 +29,7 @@ extern void debug_mutex_init(struct mutestatic inline void mutex_set_owner (struct mutex *lock) { - lock->owner =current_thread_info (); + lock->owner = current; }static inline void mutex_clear_owner (struct mutex *lock)
kernel/mutex.c +1 -1
@@ -160,7 +160,7 @@ __mutex_lock_common(struct mutex *lock,*/ for (;;) { -struct thread_info *owner; +struct task_struct *owner;/* * If we own the BKL, then don't spin. The owner of
kernel/mutex.h +1 -1
@@ -19,7 +19,7 @@#ifdef CONFIG_SMP static inline void mutex_set_owner (struct mutex *lock) { - lock->owner =current_thread_info (); + lock->owner = current; }static inline void mutex_clear_owner (struct mutex *lock)
kernel/sched.c +37 -50
107 lines not on this page · raw message
include/linux/sched.h +1 -1
@@ -360,7 +360,7 @@ extern signed long schedule_timeout_inteextern signed long schedule_timeout_killable (signed long timeout);extern signed long schedule_timeout_uninterruptible (signed long timeout); asmlinkage void schedule(void); -extern int mutex_spin_on_owner (struct mutex *lock,struct thread_info *owner); +extern int mutex_spin_on_owner (struct mutex *lock,struct task_struct *owner);struct nsproxy ;struct user_namespace ;
Re: [RFC][PATCH 2/5] mutex: Use p->oncpu for the adaptive spin
Quoted 3 lines · Peter Zijlstra
So yea, I think we can simplify all this even further, but we do need a
smp_rmb()in between those two checks, hmm, and RCU.
I am not sure we need rmb() or even read_barrier_depends(), I think the simple barrier() should be enough. Although rcu_dereference() may be more clean.
We don't really care about the "correct" result of *owner. All we need, we should ensure it is safe to dereference this address. If CPU itself does something like "readahead" before we verified "lock->owner == owner" under RCU lock, this shouldn't lead to the fault.
Oleg.
RFC PATCH 3/5 sched: Change the ttwu success details
In reply to Peter Zijlstratry_to_wake_up() would only return a success when it would have to place a task on a rq, change that to every time we change p->state to TASK_RUNNING, because that's the real measure of wakeups.
This results in that success is always true for the tracepoint, so remove its success argument.
--- include/trace/events/sched.h | 18 ++++++++---------- kernel/sched.c | 18 ++++++++---------- kernel/trace/trace_sched_wakeup.c | 3 +-- 3 files changed, 17 insertions(+), 22 deletions(-)
kernel/sched.c +8 -10
@@ -2327,10 +2327,10 @@ static inline void ttwu_activate(structactivate_task (rq, p, en_flags); } -static inline void ttwu_post_activation (struct task_struct *p,struct rq *rq, -int wake_flags,bool success) +static void +ttwu_post_activation (struct task_struct *p,struct rq *rq,int wake_flags) { -trace_sched_wakeup (p, success); +trace_sched_wakeup (p);check_preempt_curr (rq, p, wake_flags); p->state =TASK_RUNNING ;
@@ -2350,7 +2350,7 @@ static inline void ttwu_post_activation( }#endif /* if a worker is waking up, notify workqueue */ -if ((p->flags &PF_WQ_WORKER ) && success) +if (p->flags &PF_WQ_WORKER )wq_worker_waking_up (p,cpu_of (rq)); }
@@ -2449,9 +2449,9 @@ static int try_to_wake_up(struct task_st#endif /* CONFIG_SMP */ ttwu_activate (p, rq, wake_flags &WF_SYNC , orig_cpu != cpu, cpu == this_cpu, en_flags); - success =1 ; out_running: -ttwu_post_activation (p, rq, wake_flags, success); +ttwu_post_activation (p, rq, wake_flags); + success =1 ; out:task_rq_unlock (rq, &flags);put_cpu ();
@@ -2470,7 +2470,6 @@ static int try_to_wake_up(struct task_ststatic void try_to_wake_up_local (struct task_struct *p) {struct rq *rq =task_rq (p); -bool success = false;BUG_ON (rq !=this_rq ());BUG_ON (p == current);
@@ -2485,9 +2484,8 @@ static void try_to_wake_up_local(structschedstat_inc (rq, ttwu_local); }ttwu_activate (p, rq, false, false, true,ENQUEUE_WAKEUP ); - success = true; } -ttwu_post_activation (p, rq,0 , success); +ttwu_post_activation (p, rq,0 ); }/**
@@ -2649,7 +2647,7 @@ void wake_up_new_task(struct task_struct rq =task_rq_lock (p, &flags);activate_task (rq, p,0 ); -trace_sched_wakeup_new (p,1 ); +trace_sched_wakeup_new (p);check_preempt_curr (rq, p,WF_FORK );#ifdef CONFIG_SMP if (p->sched_class->task_woken)
include/trace/events/sched.h +8 -10
@@ -54,15 +54,14 @@ TRACE_EVENT(sched_kthread_stop_ret,*/ DECLARE_EVENT_CLASS(sched_wakeup_template, - TP_PROTO(struct task_struct *p, int success), + TP_PROTO(struct task_struct *p), - TP_ARGS(p, success), + TP_ARGS(p), TP_STRUCT__entry( __array( char, comm, TASK_COMM_LEN ) __field( pid_t, pid ) __field( int, prio ) - __field( int, success ) __field( int, target_cpu ) ),
@@ -70,25 +69,24 @@ DECLARE_EVENT_CLASS(sched_wakeup_templatmemcpy (__entry->comm, p->comm,TASK_COMM_LEN ); __entry->pid = p->pid; __entry->prio = p->prio; - __entry->success = success; __entry->target_cpu =task_cpu (p); ), -TP_printk ("comm=%s pid=%d prio=%d success=%d target_cpu=%03d" , +TP_printk ("comm=%s pid=%d prio=%d target_cpu=%03d" , __entry->comm, __entry->pid, __entry->prio, - __entry->success, __entry->target_cpu) + __entry->target_cpu) );DEFINE_EVENT (sched_wakeup_template, sched_wakeup, - TP_PROTO(struct task_struct *p, int success), -TP_ARGS (p, success)); + TP_PROTO(struct task_struct *p), +TP_ARGS (p));/* * Tracepoint for waking up a new task: */ DEFINE_EVENT (sched_wakeup_template, sched_wakeup_new, - TP_PROTO(struct task_struct *p, int success), -TP_ARGS (p, success)); + TP_PROTO(struct task_struct *p), +TP_ARGS (p));#ifdef CREATE_TRACE_POINTS static inline long __trace_sched_switch_state (struct task_struct *p)
kernel/trace/trace_sched_wakeup.c +1 -2
@@ -399,8 +399,7 @@ static void wakeup_reset(struct trace_arlocal_irq_restore (flags); } -static void -probe_wakeup (void *ignore,struct task_struct *p,int success) +static void probe_wakeup (void *ignore,struct task_struct *p) {struct trace_array_cpu *data;int cpu =smp_processor_id ();
kernel/trace/trace_sched_switch.c +1 -1
@@ -108,7 +108,7 @@ tracing_sched_wakeup_trace(struct trace_array *tr, }static void -probe_sched_wakeup (void *ignore,struct task_struct *wakee,int success) +probe_sched_wakeup (void *ignore,struct task_struct *wakee) {struct trace_array_cpu *data;unsigned long flags;
Re: [RFC][PATCH 3/5] sched: Change the ttwu success details
Quoted 106 lines · Peter Zijlstra
try_to_wake_up()would only return a success when it would have to place a task on a rq, change that to every time we changep->statetoTASK_RUNNING, because that's the real measure of wakeups.This results in that success is always true for the tracepoint, so remove its success argument.
Signed-off-by Peter Zijlstra <[email protected]>--- include/trace/events/sched.h | 18 ++++++++---------- kernel/sched.c | 18 ++++++++---------- kernel/trace/trace_sched_wakeup.c | 3 +-- 3 files changed, 17 insertions(+), 22 deletions(-)Index:
linux-2.6/kernel/sched.c
===================================================================kernel/sched.c +8
-10@@ -2327,10 +2327,10 @@ static inline void ttwu_activate(structactivate_task (rq, p, en_flags); } -static inline void ttwu_post_activation (struct task_struct *p,struct rq *rq, -int wake_flags,bool success) +static void +ttwu_post_activation (struct task_struct *p,struct rq *rq,int wake_flags) { -trace_sched_wakeup (p, success); +trace_sched_wakeup (p);check_preempt_curr (rq, p, wake_flags); p->state =TASK_RUNNING ;@@ -2350,7 +2350,7 @@ static inline void ttwu_post_activation( }#endif /* if a worker is waking up, notify workqueue */ -if ((p->flags &PF_WQ_WORKER ) && success) +if (p->flags &PF_WQ_WORKER )wq_worker_waking_up (p,cpu_of (rq)); }@@ -2449,9 +2449,9 @@ static int try_to_wake_up(struct task_st#endif /* CONFIG_SMP */ ttwu_activate (p, rq, wake_flags &WF_SYNC , orig_cpu != cpu, cpu == this_cpu, en_flags); - success =1 ; out_running: -ttwu_post_activation (p, rq, wake_flags, success); +ttwu_post_activation (p, rq, wake_flags); + success =1 ; out:task_rq_unlock (rq, &flags);put_cpu ();@@ -2470,7 +2470,6 @@ static int try_to_wake_up(struct task_ststatic void try_to_wake_up_local (struct task_struct *p) {struct rq *rq =task_rq (p); -bool success = false;BUG_ON (rq !=this_rq ());BUG_ON (p == current);@@ -2485,9 +2484,8 @@ static void try_to_wake_up_local(structschedstat_inc (rq, ttwu_local); }ttwu_activate (p, rq, false, false, true,ENQUEUE_WAKEUP ); - success = true; } -ttwu_post_activation (p, rq,0 , success); +ttwu_post_activation (p, rq,0 ); }/** @@ -2649,7 +2647,7 @@ void wake_up_new_task(struct task_struct rq =task_rq_lock (p, &flags);activate_task (rq, p,0 ); -trace_sched_wakeup_new (p,1 ); +trace_sched_wakeup_new (p);check_preempt_curr (rq, p,WF_FORK );#ifdef CONFIG_SMP if (p->sched_class->task_woken)Index:
linux-2.6/include/trace/events/sched.h
===================================================================include/trace/events/sched.h +2
-3@@ -54,15 +54,14 @@ TRACE_EVENT(sched_kthread_stop_ret,*/ DECLARE_EVENT_CLASS(sched_wakeup_template, - TP_PROTO(struct task_struct *p, int success), + TP_PROTO(struct task_struct *p), - TP_ARGS(p, success), + TP_ARGS(p), TP_STRUCT__entry( __array( char, comm, TASK_COMM_LEN ) __field( pid_t, pid ) __field( int, prio ) - __field( int, success ) __field( int, target_cpu ) ),@@ -70,25 +69,24 @@ DECLARE_EVENT_CLASS(sched_wakeup_templatmemcpy (__entry->comm, p->comm,TASK_COMM_LEN ); __entry->pid = p->pid;
include/trace/events/sched.h DECLARE_EVENT_CLASS(sched_wakeup_templat · line 77
Quoted 10 lines
include/trace/events/sched.h +2
-3__entry->prio = p->prio; - __entry->success = success; __entry->target_cpu =task_cpu (p); ), -TP_printk ("comm=%s pid=%d prio=%d success=%d target_cpu=%03d" , +TP_printk ("comm=%s pid=%d prio=%d target_cpu=%03d" , __entry->comm, __entry->pid, __entry->prio, - __entry->success, __entry->target_cpu) + __entry->target_cpu)
Note we'll need to fix some perf scripts after that. And also perf sched, probably perf timechart and so on...
Re: [RFC][PATCH 3/5] sched: Change the ttwu success details
Quoted 8 lines · Frederic Weisbecker
include/trace/events/sched.h DECLARE_EVENT_CLASS(sched_wakeup_templat · line 77
Quoted 5 lines
include/trace/events/sched.h +2
-2-TP_printk ("comm=%s pid=%d prio=%d success=%d target_cpu=%03d" , +TP_printk ("comm=%s pid=%d prio=%d target_cpu=%03d" , __entry->comm, __entry->pid, __entry->prio, - __entry->success, __entry->target_cpu) + __entry->target_cpu)Note we'll need to fix some perf scripts after that. And also perf sched, probably perf timechart and so on...
Do any of those actually use the success parameter? If not, then me removing it shouldn't break those tools since they're supposed to parse the format stuff and not notice it missing ;-)
Peter Zijlstra
maintainerRe: [RFC][PATCH 3/5] sched: Change the ttwu success details
Quoted 11 lines · Peter Zijlstra
Quoted 8 lines · Frederic Weisbecker
include/trace/events/sched.h DECLARE_EVENT_CLASS(sched_wakeup_templat · line 77
Quoted 5 lines
include/trace/events/sched.h +2
-2-TP_printk ("comm=%s pid=%d prio=%d success=%d target_cpu=%03d" , +TP_printk ("comm=%s pid=%d prio=%d target_cpu=%03d" , __entry->comm, __entry->pid, __entry->prio, - __entry->success, __entry->target_cpu) + __entry->target_cpu)Note we'll need to fix some perf scripts after that. And also perf sched, probably perf timechart and so on...
Quoted 3 lines
Do any of those actually use the success parameter? If not, then me removing it shouldn't break those tools since they're supposed to parse the format stuff and not notice it missing ;-)
Alternatively we could always call trace_sched_wakeup() and make success reflect actual wakeup success.
Re: [RFC][PATCH 3/5] sched: Change the ttwu success details
Quoted 12 lines · Peter Zijlstra
Quoted 11 lines · Peter Zijlstra
Quoted 8 lines · Frederic Weisbecker
include/trace/events/sched.h DECLARE_EVENT_CLASS(sched_wakeup_templat · line 77
Quoted 5 lines
include/trace/events/sched.h +2
-2-TP_printk ("comm=%s pid=%d prio=%d success=%d target_cpu=%03d" , +TP_printk ("comm=%s pid=%d prio=%d target_cpu=%03d" , __entry->comm, __entry->pid, __entry->prio, - __entry->success, __entry->target_cpu) + __entry->target_cpu)Note we'll need to fix some perf scripts after that. And also perf sched, probably perf timechart and so on...
Quoted 6 lines
Quoted 3 lines
Do any of those actually use the success parameter? If not, then me removing it shouldn't break those tools since they're supposed to parse the format stuff and not notice it missing ;-)
Alternatively we could always call
trace_sched_wakeup()and make success reflect actual wakeup success.
So, that would work very well for sched-migration.py
builtin-sched.c would continue to work fine but would notice that as a bug if a wake up occur on a task already running.
But it will only trigger a warning, besides that it will just continue to work normally.
It's ok I think, if that old tool triggers a spurious warning. I suspect very few people use it anyway.
Re: [RFC][PATCH 3/5] sched: Change the ttwu success details
In reply to Peter ZijlstraQuoted 11 lines · Peter Zijlstra
Quoted 8 lines · Frederic Weisbecker
include/trace/events/sched.h DECLARE_EVENT_CLASS(sched_wakeup_templat · line 77
Quoted 5 lines
include/trace/events/sched.h +2
-2-TP_printk ("comm=%s pid=%d prio=%d success=%d target_cpu=%03d" , +TP_printk ("comm=%s pid=%d prio=%d target_cpu=%03d" , __entry->comm, __entry->pid, __entry->prio, - __entry->success, __entry->target_cpu) + __entry->target_cpu)Note we'll need to fix some perf scripts after that. And also perf sched, probably perf timechart and so on...
Quoted 3 lines
Do any of those actually use the success parameter? If not, then me removing it shouldn't break those tools since they're supposed to parse the format stuff and not notice it missing ;-)
Yep, builtin-sched.c and sched-migration.py do.
Re: [RFC][PATCH 3/5] sched: Change the ttwu success details
In reply to Peter ZijlstraQuoted 8 lines · Peter Zijlstra
try_to_wake_up()would only return a success when it would have to place a task on a rq, change that to every time we changep->statetoTASK_RUNNING, because that's the real measure of wakeups.This results in that success is always true for the tracepoint, so remove its success argument.
Signed-off-by Peter Zijlstra <[email protected]>
Looks good to me, so far. But I still I have a few more places that call try_to_wake_up() to validate.
RFC PATCH 4/5 sched: Clean up ttwu stats
In reply to Peter ZijlstraCollect all ttwu stat code into a single function and ensure its always called for an actual wakeup (changing p->state to TASK_RUNNING).
--- kernel/sched.c | 66 ++++++++++++++++++++++++++------------------------------- 1 file changed, 31 insertions(+), 35 deletions(-)
kernel/sched.c +31 -35
@@ -2310,21 +2310,35 @@ static void update_avg(u64 *avg, u64 sam }#endif -static inline void ttwu_activate (struct task_struct *p,struct rq *rq, -bool is_sync,bool is_migrate,bool is_local, -unsigned long en_flags) +static void +ttwu_stat (struct rq *rq,struct task_struct *p,int cpu,int wake_flags) { +#ifdef CONFIG_SCHEDSTATS + +schedstat_inc (rq, ttwu_count);schedstat_inc (p, se.statistics.nr_wakeups); -if (is_sync) + +if (wake_flags &WF_SYNC )schedstat_inc (p, se.statistics.nr_wakeups_sync); -if (is_migrate) + +if (cpu !=task_cpu (p))schedstat_inc (p, se.statistics.nr_wakeups_migrate); -if (is_local) + +if (cpu ==smp_processor_id ()) { +schedstat_inc (rq, ttwu_local);schedstat_inc (p, se.statistics.nr_wakeups_local); -else -schedstat_inc (p, se.statistics.nr_wakeups_remote); + }else { +struct sched_domain *sd; -activate_task (rq, p, en_flags); +schedstat_inc (p, se.statistics.nr_wakeups_remote); +for_each_domain (smp_processor_id (), sd) { +if (cpumask_test_cpu (cpu,sched_domain_span (sd))) { +schedstat_inc (sd, ttwu_wake_remote); +break ; + } + } + } +#endif /* CONFIG_SCHEDSTATS */ } static void
@@ -2384,12 +2398,12 @@ static int try_to_wake_up(struct task_stif (!(p->state & state)) goto out; + cpu =task_cpu (p); +if (p->se.on_rq) goto out_running; - cpu =task_cpu (p); orig_cpu = cpu; -#ifdef CONFIG_SMP if (unlikely (task_running (rq, p))) goto out_activate;
@@ -2430,27 +2444,12 @@ static int try_to_wake_up(struct task_stWARN_ON (task_cpu (p) != cpu);WARN_ON (p->state !=TASK_WAKING ); -#ifdef CONFIG_SCHEDSTATS -schedstat_inc (rq, ttwu_count); -if (cpu == this_cpu) -schedstat_inc (rq, ttwu_local); -else { -struct sched_domain *sd; -for_each_domain (this_cpu, sd) { -if (cpumask_test_cpu (cpu,sched_domain_span (sd))) { -schedstat_inc (sd, ttwu_wake_remote); -break ; - } - } - } -#endif /* CONFIG_SCHEDSTATS */ - out_activate:#endif /* CONFIG_SMP */ -ttwu_activate (p, rq, wake_flags &WF_SYNC , orig_cpu != cpu, - cpu == this_cpu, en_flags); +activate_task (rq, p, en_flags); out_running:ttwu_post_activation (p, rq, wake_flags); +ttwu_stat (rq, p, cpu, wake_flags); success =1 ; out:task_rq_unlock (rq, &flags);
@@ -2478,14 +2477,11 @@ static void try_to_wake_up_local(structif (!(p->state &TASK_NORMAL ))return ; -if (!p->se.on_rq) { -if (likely (!task_running (rq, p))) { -schedstat_inc (rq, ttwu_count); -schedstat_inc (rq, ttwu_local); - } -ttwu_activate (p, rq, false, false, true,ENQUEUE_WAKEUP ); - } +if (!p->se.on_rq) +activate_task (rq, p,ENQUEUE_WAKEUP ); +ttwu_post_activation (p, rq,0 ); +ttwu_stat (rq, p,smp_processor_id (),0 ); }/**
Re: [RFC][PATCH 4/5] sched: Clean up ttwu stats
Quoted 8 lines · Peter Zijlstra
Collect all ttwu stat code into a single function and ensure its always called for an actual wakeup (changing
p->statetoTASK_RUNNING).Signed-off-by Peter Zijlstra <[email protected]>--- kernel/sched.c | 66 ++++++++++++++++++++++++++------------------------------- 1 file changed, 31 insertions(+), 35 deletions(-)
Looks good to me. Nice cleanup...
A couple of nits inline if you want them.
Quoted 7 lines
Index:
linux-2.6/kernel/sched.c
===================================================================kernel/sched.c +0
-0@@ -2310,21 +2310,35 @@ static void update_avg(u64 *avg, u64 sam }
kernel/sched.c static void update_avg(u64 *avg, u64 sam · line 2317
Quoted 10 lines
kernel/sched.c +4
-3#endif -static inline void ttwu_activate (struct task_struct *p,struct rq *rq, -bool is_sync,bool is_migrate,bool is_local, -unsigned long en_flags) +static void +ttwu_stat (struct rq *rq,struct task_struct *p,int cpu,int wake_flags) { +#ifdef CONFIG_SCHEDSTATS +
int this_cpu = smp_processor_id();
kernel/sched.c static void update_avg(u64 *avg, u64 sam · line 2327
Quoted 13 lines
kernel/sched.c +7
-3+schedstat_inc (rq, ttwu_count);schedstat_inc (p, se.statistics.nr_wakeups); -if (is_sync) + +if (wake_flags &WF_SYNC )schedstat_inc (p, se.statistics.nr_wakeups_sync); -if (is_migrate) + +if (cpu !=task_cpu (p))schedstat_inc (p, se.statistics.nr_wakeups_migrate); -if (is_local) + +if (cpu ==smp_processor_id ()) {
^^^^^^ this_cpu
kernel/sched.c static void update_avg(u64 *avg, u64 sam · line 2334
Quoted 10 lines
kernel/sched.c +5
-3+schedstat_inc (rq, ttwu_local);schedstat_inc (p, se.statistics.nr_wakeups_local); - else - schedstat_inc(p, se.statistics.nr_wakeups_remote); + }else { +struct sched_domain *sd; -activate_task (rq, p, en_flags); +schedstat_inc (p, se.statistics.nr_wakeups_remote); +for_each_domain (smp_processor_id (), sd) {
^^^^^ this_cpu
Quoted 10 lines
kernel/sched.c +7
-0+if (cpumask_test_cpu (cpu,sched_domain_span (sd))) { +schedstat_inc (sd, ttwu_wake_remote); +break ; + } + } + } +#endif /* CONFIG_SCHEDSTATS */ } static void
RFC PATCH 5/5 sched: Reduce ttwu rq->lock contention
In reply to Peter ZijlstraReduce rq->lock contention on try_to_wake_up() by changing the task state using a cmpxchg loop.
Once the task is set to TASK_WAKING we're guaranteed the only one poking at it, then proceed to pick a new cpu without holding the rq->lock (XXX this opens some races).
Then instead of locking the remote rq and activating the task, place the task on a remote queue, again using cmpxchg, and notify the remote cpu per IPI if this queue was empty to start processing its wakeups.
This avoids (in most cases) having to lock the remote runqueue (and therefore the exclusive cacheline transfer thereof) but also touching all the remote runqueue data structures needed for the actual activation.
As measured using: http://oss.oracle.com/~mason/sembench.c
$ echo 4096 32000 64 128 > /proc/sys/kernel/sem $ ./sembench -t 2048 -w 1900 -o 0
unpatched: run time 30 seconds 537953 worker burns per second patched: run time 30 seconds 657336 worker burns per second
Still need to sort out all the races marked XXX (non-trivial), and its x86 only for the moment.
--- arch/x86/kernel/smp.c | 1 include/linux/sched.h | 7 - kernel/sched.c | 241 ++++++++++++++++++++++++++++++++++-------------- kernel/sched_fair.c | 5 kernel/sched_features.h | 3 kernel/sched_idletask.c | 2 kernel/sched_rt.c | 4 kernel/sched_stoptask.c | 3 8 files changed, 190 insertions(+), 76 deletions(-)
arch/x86/kernel/smp.c +1 -0
@@ -205,6 +205,7 @@ void smp_reschedule_interrupt(struct pt_/* * KVM uses this interrupt to force a cpu out of guest mode */ +sched_ttwu_pending (); }void smp_call_function_interrupt (struct pt_regs *regs)
include/linux/sched.h +4 -3
@@ -1020,6 +1020,7 @@ partition_sched_domains(int ndoms_new, c }#endif /* !CONFIG_SMP */ +void sched_ttwu_pending (void );struct io_context ;/* See blkdev.h */
@@ -1063,12 +1064,11 @@ struct sched_class {void (*put_prev_task) (struct rq *rq,struct task_struct *p);#ifdef CONFIG_SMP -int (*select_task_rq)(struct rq *rq,struct task_struct *p, -int sd_flag,int flags); +int (*select_task_rq)(struct task_struct *p,int sd_flag,int flags);void (*pre_schedule) (struct rq *this_rq,struct task_struct *task);void (*post_schedule) (struct rq *this_rq); -void (*task_waking) (struct rq *this_rq,struct task_struct *task); +void (*task_waking) (struct task_struct *task);void (*task_woken) (struct rq *this_rq,struct task_struct *task); void (*set_cpus_allowed)(struct task_struct *p,
@@ -1198,6 +1198,7 @@ struct task_struct {int lock_depth;/* BKL lock depth */ #ifdef CONFIG_SMP +struct task_struct *wake_entry;int oncpu;#endif
kernel/sched.c +174 -67
333 lines not on this page · raw message
kernel/sched_fair.c +3 -2
@@ -1321,11 +1321,12 @@ static void yield_task_fair(struct rq *r#ifdef CONFIG_SMP -static void task_waking_fair (struct rq *rq,struct task_struct *p) +static void task_waking_fair (struct task_struct *p) {struct sched_entity *se = &p->se;struct cfs_rq *cfs_rq =cfs_rq_of (se); +// XXX racy again,.. we need to read cfs_rq->min_vruntime atomically se->vruntime -= cfs_rq->min_vruntime; }
@@ -1606,7 +1607,7 @@ static int select_idle_sibling(struct ta* preempt must be disabled. */ static int -select_task_rq_fair (struct rq *rq,struct task_struct *p,int sd_flag,int wake_flags) +select_task_rq_fair (struct task_struct *p,int sd_flag,int wake_flags) {struct sched_domain *tmp, *affine_sd =NULL , *sd =NULL ;int cpu =smp_processor_id ();
kernel/sched_idletask.c +1 -1
@@ -7,7 +7,7 @@#ifdef CONFIG_SMP static int -select_task_rq_idle (struct rq *rq,struct task_struct *p,int sd_flag,int flags) +select_task_rq_idle (struct task_struct *p,int sd_flag,int flags) {return task_cpu (p);/* IDLE tasks as never migrated */ }
kernel/sched_rt.c +3 -1
@@ -973,8 +973,10 @@ static void yield_task_rt(struct rq *rq)static int find_lowest_rq (struct task_struct *task);static int -select_task_rq_rt (struct rq *rq,struct task_struct *p,int sd_flag,int flags) +select_task_rq_rt (struct task_struct *p,int sd_flag,int flags) { +struct rq *rq =task_rq (p);// XXX racy +if (sd_flag !=SD_BALANCE_WAKE )return smp_processor_id ();
kernel/sched_stoptask.c +1 -2
@@ -9,8 +9,7 @@#ifdef CONFIG_SMP static int -select_task_rq_stop (struct rq *rq,struct task_struct *p, -int sd_flag,int flags) +select_task_rq_stop (struct task_struct *p,int sd_flag,int flags) {return task_cpu (p);/* stop tasks as never migrate */ }
kernel/sched_features.h +3 -0
@@ -64,3 +64,6 @@ SCHED_FEAT(OWNER_SPIN, 1)* Decrement CPU power based on irq activity */ SCHED_FEAT(NONIRQ_POWER, 1) + +SCHED_FEAT(TTWU_FORCE, 0) +SCHED_FEAT (TTWU_SPIN ,1 )
Re: [RFC][PATCH 5/5] sched: Reduce ttwu rq->lock contention
Quoted 44 lines · Peter Zijlstra
Reduce
rq->lockcontention ontry_to_wake_up()by changing the task state using a cmpxchg loop.Once the task is set to
TASK_WAKINGwe're guaranteed the only one poking at it, then proceed to pick a new cpu without holding therq->lock(XXX this opens some races).Then instead of locking the remote rq and activating the task, place the task on a remote queue, again using cmpxchg, and notify the remote cpu per IPI if this queue was empty to start processing its wakeups.
This avoids (in most cases) having to lock the remote runqueue (and therefore the exclusive cacheline transfer thereof) but also touching all the remote runqueue data structures needed for the actual activation.
As measured using: http://oss.oracle.com/~mason/sembench.c
$ echo 4096 32000 64 128 > /proc/sys/kernel/sem $ ./sembench -t 2048 -w 1900 -o 0unpatched: run time 30 seconds 537953 worker burns per second patched: run time 30 seconds 657336 worker burns per secondStill need to sort out all the races marked XXX (non-trivial), and its x86 only for the moment.
Signed-off-by Peter Zijlstra <[email protected]>--- arch/x86/kernel/smp.c | 1 include/linux/sched.h | 7 - kernel/sched.c | 241 ++++++++++++++++++++++++++++++++++-------------- kernel/sched_fair.c | 5 kernel/sched_features.h | 3 kernel/sched_idletask.c | 2 kernel/sched_rt.c | 4 kernel/sched_stoptask.c | 3 8 files changed, 190 insertions(+), 76 deletions(-)Index:
linux-2.6/arch/x86/kernel/smp.c
===================================================================
arch/x86/kernel/smp.c void smp_reschedule_interrupt(struct pt_ · line 209
Quoted 5 lines
arch/x86/kernel/smp.c +1
-0@@ -205,6 +205,7 @@ void smp_reschedule_interrupt(struct pt_/* * KVM uses this interrupt to force a cpu out of guest mode */ +sched_ttwu_pending (); }
Great, that's going to greatly simplify and lower the overhead of the remote tick restart I'm doing on wake up for the nohz task thing.
Re: [RFC][PATCH 5/5] sched: Reduce ttwu rq->lock contention
In reply to Peter ZijlstraQuoted 4 lines · Peter Zijlstra
Then instead of locking the remote rq and activating the task, place the task on a remote queue, again using cmpxchg, and notify the remote cpu per IPI if this queue was empty to start processing its wakeups.
Interesting... I didn't actually read this patch yet, just a very minor nit.
kernel/sched.c ttwu_post_activation(struct task_struct · line 2453
Quoted 11 lines
kernel/sched.c +11
-0+#ifdef CONFIG_SMP +static void ttwu_queue_remote (struct task_struct *p,int cpu) +{ +struct task_struct *next =NULL ; +struct rq *rq =cpu_rq (cpu); + +for (;;) { +struct task_struct *old = next; + + p->wake_entry = next; + next =cmpxchg (&rq->wake_list, old, p);
Somehow I was confused by initial "next = NULL", perhaps
struct rq *rq = cpu_rq(cpu); struct task_struct *next = rq->wake_list;
makes a bit more sense.
Oleg.
Re: [RFC][PATCH 5/5] sched: Reduce ttwu rq->lock contention
In reply to Peter Zijlstrakernel/sched.c ttwu_post_activation(struct task_struct · line 2400
Quoted 9 lines · Peter Zijlstra
kernel/sched.c +8
-0+static int ttwu_force (struct task_struct *p,int wake_flags) +{ +struct rq *rq; +int ret =0 ; + +/* +* Since we've already set TASK_WAKING this task's CPU cannot +* change from under us.
I think it can. Yes, we've set TASK_WAKING. But, at least the task itself can change its state back to TASK_RUNNING without calling schedule. Say, __wait_event()-like code.
Quoted 14 lines
kernel/sched.c +5
-6+static int +try_to_wake_up (struct task_struct *p,unsigned int state,int wake_flags) { -int cpu, orig_cpu, this_cpu, success =0 ; +int cpu =task_cpu (p);unsigned long flags; -unsigned long en_flags =ENQUEUE_WAKEUP ; -struct rq *rq; +int success =0 ; +int load; - this_cpu =get_cpu (); - -smp_wmb ();
kernel/sched.c ttwu_post_activation(struct task_struct · line 2507
Quoted 10 lines
kernel/sched.c +5
-4- rq =task_rq_lock (p, &flags); -if (!(p->state & state)) - goto out; +local_irq_save (flags); +for (;;) { +unsigned int task_state = p->state; - cpu =task_cpu (p); +if (!(task_state & state)) + goto out;
Well, this surely breaks the code like
CONDITION = true; wake_up_process(p);
At least we need mb() before we check task_state the first time.
Oleg.
Re: [RFC][PATCH 5/5] sched: Reduce ttwu rq->lock contention
Quoted 14 lines · Oleg Nesterov
kernel/sched.c ttwu_post_activation(struct task_struct · line 2400
Quoted 9 lines · Peter Zijlstra
kernel/sched.c +8
-0+static int ttwu_force (struct task_struct *p,int wake_flags) +{ +struct rq *rq; +int ret =0 ; + +/* +* Since we've already set TASK_WAKING this task's CPU cannot +* change from under us. I think it can. Yes, we've set
TASK_WAKING. But, at least the task itself can change its state back toTASK_RUNNINGwithout calling schedule. Say, __wait_event()-like code.
Oh crud, you're right, that's going to make all this cmpxchg stuff lots more interesting :/
Quoted 27 lines
Quoted 14 lines
kernel/sched.c +5
-6+static int +try_to_wake_up (struct task_struct *p,unsigned int state,int wake_flags) { -int cpu, orig_cpu, this_cpu, success =0 ; +int cpu =task_cpu (p);unsigned long flags; -unsigned long en_flags =ENQUEUE_WAKEUP ; -struct rq *rq; +int success =0 ; +int load; - this_cpu =get_cpu (); - -smp_wmb ();kernel/sched.c ttwu_post_activation(struct task_struct · line 2507
Quoted 10 lines
kernel/sched.c +5
-4- rq =task_rq_lock (p, &flags); -if (!(p->state & state)) - goto out; +local_irq_save (flags); +for (;;) { +unsigned int task_state = p->state; - cpu =task_cpu (p); +if (!(task_state & state)) + goto out;Well, this surely breaks the code like
Quoted 4 lines
CONDITION = true; wake_up_process(p);At least we need
mb()before we checktask_statethe first time.
You're right (wmb, at least), I left that out because I had the cmpxchg in there that provides a mb, but didn't notice I read the state before that.. /me goes put the smp_wmb() back.
Peter Zijlstra
maintainerRe: [RFC][PATCH 5/5] sched: Reduce ttwu rq->lock contention
Quoted 9 lines · Peter Zijlstra
Quoted 6 lines
kernel/sched.c ttwu_post_activation(struct task_struct · line 2400
Quoted 2 lines
kernel/sched.c +2
-0+* Since we've already set TASK_WAKING this task's CPU cannot +* change from under us. I think it can. Yes, we've set
TASK_WAKING. But, at least the task itself can change its state back toTASK_RUNNINGwithout calling schedule. Say, __wait_event()-like code.Oh crud, you're right, that's going to make all this cmpxchg stuff lots more interesting :/
Hrmph, we can add a task_is_waking() test to the rq->lock in schedule(), like we have for __task_rq_lock():
local_irq_save(flags);
again:
while (task_is_waking(current))
cpu_relax();
raw_spin_lock(rq->lock);
if (task_is_waking(current)) {
raw_spin_unlock(rq->lock);
goto again;}
But that's not particularly pretty...
Peter Zijlstra
maintainerRe: [RFC][PATCH 5/5] sched: Reduce ttwu rq->lock contention
Quoted 22 lines · Peter Zijlstra
Quoted 9 lines · Peter Zijlstra
Quoted 6 lines
kernel/sched.c ttwu_post_activation(struct task_struct · line 2400
Quoted 2 lines
kernel/sched.c +2
-0+* Since we've already set TASK_WAKING this task's CPU cannot +* change from under us. I think it can. Yes, we've set
TASK_WAKING. But, at least the task itself can change its state back toTASK_RUNNINGwithout calling schedule. Say, __wait_event()-like code.Oh crud, you're right, that's going to make all this cmpxchg stuff lots more interesting :/
Hrmph, we can add a
task_is_waking()test to therq->lockinschedule(), like we have for__task_rq_lock():
local_irq_save(flags);
again:
while (task_is_waking(current))cpu_relax(); raw_spin_lock(rq->lock); if (task_is_waking(current)) { raw_spin_unlock(rq->lock); goto again;
Quoted 4 lines
}
But that's not particularly pretty...
OK, I'm just not thinking straight here, if we're not passing through schedule() the above clearly won't help any...
Damn, that's a nasty case to solve...
current->state = TASK_UNINTERRUPTIBLE;
while (!true)
schedule();
current->state = TASK_RUNNING;... /me goes make a strong pot of tea
Peter Zijlstra
maintainerRe: [RFC][PATCH 5/5] sched: Reduce ttwu rq->lock contention
Quoted 1 line · Peter Zijlstra
... /me goes make a strong pot of tea
Just when the tea was setting my brain sparked (could be insanity, dunno), anyway, how about the below?
It does the state and on_rq checks first, if we find on_rq, we do a forced remote wakeup (rq->lock, recheck state, recheck on_rq, set p->state to TASK_RUNNING), otherwise, we do the cmpxchg thing to TASK_WAKING, (since !on_rq @p passed through schedule()) and proceed like before.
---
Subject: sched: Reduce ttwu rq->lock contention
From: Peter Zijlstra <[email protected]>
Date: Tue, 22 Jun 2010 15:33:06 +0200
Reduce rq->lock contention on try_to_wake_up() by changing the task state using a cmpxchg loop.
Once the task is set to TASK_WAKING we're guaranteed the only one poking at it, then proceed to pick a new cpu without holding the rq->lock (XXX this opens some races).
Then instead of locking the remote rq and activating the task, place the task on a remote queue, again using cmpxchg, and notify the remote cpu per IPI if this queue was empty to start processing its wakeups.
This avoids (in most cases) having to lock the remote runqueue (and therefore the exclusive cacheline transfer thereof) but also touching all the remote runqueue data structures needed for the actual activation.
As measured using: http://oss.oracle.com/~mason/sembench.c
$ echo 4096 32000 64 128 > /proc/sys/kernel/sem $ ./sembench -t 2048 -w 1900 -o 0
unpatched: run time 30 seconds 537953 worker burns per second patched: run time 30 seconds 657336 worker burns per second
Still need to sort out all the races marked XXX (non-trivial), and its x86 only for the moment.
LKML-Reference: <1277213586.1875.704.camel@laptop>
--- arch/x86/kernel/smp.c | 1 include/linux/sched.h | 7 - kernel/sched.c | 226 +++++++++++++++++++++++++++++++++--------------- kernel/sched_fair.c | 5 - kernel/sched_features.h | 2 kernel/sched_idletask.c | 2 kernel/sched_rt.c | 4 kernel/sched_stoptask.c | 3 8 files changed, 175 insertions(+), 75 deletions(-)
arch/x86/kernel/smp.c +1 -0
@@ -205,6 +205,7 @@ void smp_reschedule_interrupt(struct pt_/* * KVM uses this interrupt to force a cpu out of guest mode */ +sched_ttwu_pending (); }void smp_call_function_interrupt (struct pt_regs *regs)
include/linux/sched.h +4 -3
@@ -1020,6 +1020,7 @@ partition_sched_domains(int ndoms_new, c }#endif /* !CONFIG_SMP */ +void sched_ttwu_pending (void );struct io_context ;/* See blkdev.h */
@@ -1063,12 +1064,11 @@ struct sched_class {void (*put_prev_task) (struct rq *rq,struct task_struct *p);#ifdef CONFIG_SMP -int (*select_task_rq)(struct rq *rq,struct task_struct *p, -int sd_flag,int flags); +int (*select_task_rq)(struct task_struct *p,int sd_flag,int flags);void (*pre_schedule) (struct rq *this_rq,struct task_struct *task);void (*post_schedule) (struct rq *this_rq); -void (*task_waking) (struct rq *this_rq,struct task_struct *task); +void (*task_waking) (struct task_struct *task);void (*task_woken) (struct rq *this_rq,struct task_struct *task); void (*set_cpus_allowed)(struct task_struct *p,
@@ -1198,6 +1198,7 @@ struct task_struct {int lock_depth;/* BKL lock depth */ #ifdef CONFIG_SMP +struct task_struct *wake_entry;int oncpu;#endif
kernel/sched.c +160 -66
322 lines not on this page · raw message
kernel/sched_fair.c +3 -2
@@ -1321,11 +1321,12 @@ static void yield_task_fair(struct rq *r#ifdef CONFIG_SMP -static void task_waking_fair (struct rq *rq,struct task_struct *p) +static void task_waking_fair (struct task_struct *p) {struct sched_entity *se = &p->se;struct cfs_rq *cfs_rq =cfs_rq_of (se); +// XXX racy again,.. we need to read cfs_rq->min_vruntime atomically se->vruntime -= cfs_rq->min_vruntime; }
@@ -1606,7 +1607,7 @@ static int select_idle_sibling(struct ta* preempt must be disabled. */ static int -select_task_rq_fair (struct rq *rq,struct task_struct *p,int sd_flag,int wake_flags) +select_task_rq_fair (struct task_struct *p,int sd_flag,int wake_flags) {struct sched_domain *tmp, *affine_sd =NULL , *sd =NULL ;int cpu =smp_processor_id ();
kernel/sched_idletask.c +1 -1
@@ -7,7 +7,7 @@#ifdef CONFIG_SMP static int -select_task_rq_idle (struct rq *rq,struct task_struct *p,int sd_flag,int flags) +select_task_rq_idle (struct task_struct *p,int sd_flag,int flags) {return task_cpu (p);/* IDLE tasks as never migrated */ }
kernel/sched_rt.c +3 -1
@@ -973,8 +973,10 @@ static void yield_task_rt(struct rq *rq)static int find_lowest_rq (struct task_struct *task);static int -select_task_rq_rt (struct rq *rq,struct task_struct *p,int sd_flag,int flags) +select_task_rq_rt (struct task_struct *p,int sd_flag,int flags) { +struct rq *rq =task_rq (p); +if (sd_flag !=SD_BALANCE_WAKE )return smp_processor_id ();
kernel/sched_stoptask.c +1 -2
@@ -9,8 +9,7 @@#ifdef CONFIG_SMP static int -select_task_rq_stop (struct rq *rq,struct task_struct *p, -int sd_flag,int flags) +select_task_rq_stop (struct task_struct *p,int sd_flag,int flags) {return task_cpu (p);/* stop tasks as never migrate */ }
kernel/sched_features.h +2 -0
@@ -64,3 +64,5 @@ SCHED_FEAT(OWNER_SPIN, 1)* Decrement CPU power based on irq activity */ SCHED_FEAT(NONIRQ_POWER, 1) + +SCHED_FEAT (TTWU_FORCE ,0 )
Re: [RFC][PATCH 5/5] sched: Reduce ttwu rq->lock contention
Quoted 10 lines · Peter Zijlstra
kernel/sched.c +1
-1@@ -953,7 +955,7 @@ static inline struct rq *__task_rq_lock( for (;;) { rq = task_rq(p); raw_spin_lock(&rq->lock); - if (likely(rq == task_rq(p))) + if (likely(rq == task_rq(p)) && !task_is_waking(p)) return rq; raw_spin_unlock(&rq->lock); }
kernel/sched.c static struct rq *task_rq_lock(struct ta · line 981
Quoted 8 lines
kernel/sched.c +1
-1@@ -973,7 +975,7 @@ static struct rq *task_rq_lock(struct ta local_irq_save(*flags); rq = task_rq(p); raw_spin_lock(&rq->lock); - if (likely(rq == task_rq(p))) + if (likely(rq == task_rq(p)) && !task_is_waking(p)) return rq; raw_spin_unlock_irqrestore(&rq->lock, *flags); }
Looks like nothing prevents ttwu() from changing task's CPU while some one else is holding task_rq_lock(). Is this OK?
Thanks
Yan, Zheng
Peter Zijlstra
maintainerRe: [RFC][PATCH 5/5] sched: Reduce ttwu rq->lock contention
Quoted 14 lines · Zheng
Quoted 13 lines · Peter Zijlstra
(quoted diff) +1
-1@@ -953,7 +955,7 @@ static inline struct rq *__task_rq_lock( for (;;) { rq = task_rq(p); raw_spin_lock(&rq->lock); - if (likely(rq == task_rq(p))) + if (likely(rq == task_rq(p)) && !task_is_waking(p)) return rq; raw_spin_unlock(&rq->lock); }@@ -973,7 +975,7 @@ static struct rq *task_rq_lock(struct ta local_irq_save(*flags); rq = task_rq(p); raw_spin_lock(&rq->lock);
Quoted 8 lines
Review static struct rq *task_rq_lock(struct ta · line 981
Quoted 5 lines
(quoted diff) +1
-1- if (likely(rq == task_rq(p))) + if (likely(rq == task_rq(p)) && !task_is_waking(p)) return rq; raw_spin_unlock_irqrestore(&rq->lock, *flags); }Looks like nothing prevents
ttwu()from changing task's CPU while some one else is holdingtask_rq_lock(). Is this OK?
Ah, crud, good catch. No that is not quite OK ;-)
I'm starting to think adding a per-task scheduler lock isn't such a bad idea after all :-)
How does something like the below look, it waits for the current task_rq(p)->lock owner to go away after we flip p->state to TASK_WAKING.
It also optimizes the x86 spinlock code a bit, no need to wait for all pending owners to go away, just the current one.
This also solves the p->cpus_allowed race..
---
kernel/sched.c +3 -4
@@ -2518,6 +2518,8 @@ try_to_wake_up(struct task_struct *p, unbreak ; } +raw_spin_unlock_wait (&task_rq (p)->lock); + ret =1 ;/* we qualify as a proper wakeup now */ if (load)// XXX racy
@@ -2536,10 +2538,7 @@ try_to_wake_up(struct task_struct *p, unif (p->sched_class->task_waking) p->sched_class->task_waking (p); -/* -* XXX: by having set TASK_WAKING outside of rq->lock, there -* could be an in-flight change to p->cpus_allowed.. -*/ + cpu =select_task_rq (p,SD_BALANCE_WAKE , wake_flags);#endif ttwu_queue (p, cpu);
arch/x86/include/asm/spinlock.h +25 -3
@@ -158,18 +158,34 @@ static __always_inline void __ticket_spi }#endif +#define TICKET_MASK ((1 << TICKET_SHIFT) - 1) +static inline int __ticket_spin_is_locked (arch_spinlock_t *lock) {int tmp =ACCESS_ONCE (lock->slock); -return !!(((tmp >>TICKET_SHIFT ) ^ tmp) & ((1 <<TICKET_SHIFT ) -1 )); +return !!(((tmp >>TICKET_SHIFT ) ^ tmp) &TICKET_MASK ); }static inline int __ticket_spin_is_contended (arch_spinlock_t *lock) {int tmp =ACCESS_ONCE (lock->slock); -return (((tmp >>TICKET_SHIFT ) - tmp) & ((1 <<TICKET_SHIFT ) -1 )) >1 ; +return (((tmp >>TICKET_SHIFT ) - tmp) &TICKET_MASK ) >1 ; +} + +static inline void __ticket_spin_unlock_wait (arch_spinlock_t *lock) +{ +int tmp =ACCESS_ONCE (lock->slock); + +if (!(((tmp >>TICKET_SHIFT ) ^ tmp) &TICKET_MASK )) +return ;/* not locked */ + + tmp &=TICKET_MASK ; + +/* wait until the current lock holder goes away */ +while ((ACCESS_ONCE (lock->slock) &TICKET_MASK ) == tmp) +cpu_relax (); }#ifndef CONFIG_PARAVIRT_SPINLOCKS
@@ -206,7 +222,11 @@ static __always_inline void arch_spin_lo arch_spin_lock(lock); } -#endif /* CONFIG_PARAVIRT_SPINLOCKS */ +static inline void arch_spin_unlock_wait (arch_spinlock_t *lock) +{ +__ticket_spin_unlock_wait (lock); +} +#else static inline void arch_spin_unlock_wait (arch_spinlock_t *lock) {
@@ -214,6 +234,8 @@ static inline void arch_spin_unlock_wait cpu_relax(); } +#endif /* CONFIG_PARAVIRT_SPINLOCKS */ +/* * Read-write spinlocks, allowing multiple readers * but only one writer.
Re: [RFC][PATCH 5/5] sched: Reduce ttwu rq->lock contention
In reply to Peter ZijlstraQuoted 2 lines · Peter Zijlstra
It does the state and
on_rqchecks first, if we findon_rq,
The problem is, somehow we should check both on_rq and state at the same time,
kernel/sched.c ttwu_post_activation(struct task_struct · line 2494
Quoted 10 lines
kernel/sched.c +3
-4+try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags) { -int cpu, orig_cpu, this_cpu, success =0 ; + int cpu, load, ret = 0;unsigned long flags; -unsigned long en_flags =ENQUEUE_WAKEUP ; -struct rq *rq; - this_cpu =get_cpu (); +smp_mb ();
Yes, we need the full mb(). without subsequent spin_lock(), wmb() can't act as a smp_store_load_barrier() (which we don't have).
kernel/sched.c ttwu_post_activation(struct task_struct · line 2500
Quoted 2 lines
kernel/sched.c +2
-0+if (p->se.on_rq &&ttwu_force (p, state, wake_flags)) +return 1 ;
----- WINDOW -----
kernel/sched.c ttwu_post_activation(struct task_struct · line 2518
Quoted 10 lines
kernel/sched.c +10
-0+for (;;) { +unsigned int task_state = p->state; + +if (!(task_state & state)) + goto out; + + load =task_contributes_to_load (p); + +if (cmpxchg (&p->state, task_state,TASK_WAKING ) == task_state) +break ;
Suppose that we have a task T sleeping in TASK_INTERRUPTIBLE state, and this cpu does try_to_wake_up(TASK_INTERRUPTIBLE). on_rq == false. try_to_wake_up() starts the "for (;;)" loop.
However, in the WINDOW above, it is possible that somebody else wakes it up, and then this task changes its state to TASK_INTERRUPTIBLE again.
Then we set ->state = TASK_WAKING, but this (still running) T restores TASK_RUNNING after us.
Oleg.
Peter Zijlstra
maintainerRe: [RFC][PATCH 5/5] sched: Reduce ttwu rq->lock contention
Quoted 41 lines · Oleg Nesterov
Quoted 2 lines · Peter Zijlstra
It does the state and
on_rqchecks first, if we findon_rq,The problem is, somehow we should check both
on_rqand state at the same time,kernel/sched.c ttwu_post_activation(struct task_struct · line 2494
Quoted 10 lines
kernel/sched.c +3
-4+try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags) { -int cpu, orig_cpu, this_cpu, success =0 ; + int cpu, load, ret = 0;unsigned long flags; -unsigned long en_flags =ENQUEUE_WAKEUP ; -struct rq *rq; - this_cpu =get_cpu (); +smp_mb ();Yes, we need the full
mb(). without subsequentspin_lock(),wmb()can't act as asmp_store_load_barrier()(which we don't have).kernel/sched.c ttwu_post_activation(struct task_struct · line 2500
Quoted 2 lines
kernel/sched.c +2
-0+if (p->se.on_rq &&ttwu_force (p, state, wake_flags)) +return 1 ;----- WINDOW -----kernel/sched.c ttwu_post_activation(struct task_struct · line 2518
Quoted 10 lines
kernel/sched.c +10
-0+for (;;) { +unsigned int task_state = p->state; + +if (!(task_state & state)) + goto out; + + load =task_contributes_to_load (p); + +if (cmpxchg (&p->state, task_state,TASK_WAKING ) == task_state) +break ;Suppose that we have a task T sleeping in
TASK_INTERRUPTIBLEstate, and this cpu doestry_to_wake_up(TASK_INTERRUPTIBLE).on_rq== false.try_to_wake_up()starts the "for (;;)" loop.
Quoted 5 lines
However, in the WINDOW above, it is possible that somebody else wakes it up, and then this task changes its state to
TASK_INTERRUPTIBLEagain.Then we set ->state =
TASK_WAKING, but this (still running) T restoresTASK_RUNNINGafter us.
See, there's a reason I CC'ed you ;-)
Hrmph, so is it only about serializing concurrent wakeups? If so, we could possibly hold p->pi_lock over the wakeup.
Peter Zijlstra
maintainerRe: [RFC][PATCH 5/5] sched: Reduce ttwu rq->lock contention
Quoted 3 lines · Peter Zijlstra
Hrmph, so is it only about serializing concurrent wakeups? If so, we could possibly hold
p->pi_lockover the wakeup.
Something like the below.. except it still suffers from the __migrate_task() hole you identified in your other email.
By fully serializing all wakeups using ->pi_lock it becomes a lot simpler (although I just realized we might have a problem with try_to_wake_up_local).
static inttry_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)
{
unsigned long flags;
int cpu, ret = 0;
smp_wmb();
raw_spin_lock_irqsave(&p->pi_lock, flags);
if (!(p->state & state))
goto unlock;
ret = 1; /* we qualify as a proper wakeup now */
if (p->se.on_rq && ttwu_force(p, state, wake_flags))
goto unlock;
p->sched_contributes_to_load = !!task_contributes_to_load(p);
/*
* In order to serialize against other tasks wanting to task_rq_lock()
* we need to wait until the current task_rq(p)->lock holder goes away,
* so that the next might observe TASK_WAKING.
*/
p->state = TASK_WAKING;
smp_wmb();
raw_spin_unlock_wait(&task_rq(p)->lock);
/*
* Stable, now that TASK_WAKING is visible.
*/
cpu = task_cpu(p);#ifdef CONFIG_SMP
/*
* Catch the case where schedule() has done the dequeue but hasn't yet
* scheduled to a new task, in that case p is still being referenced
* by that cpu so we cannot wake it to any other cpu.
*
* Here we must either do a full remote enqueue, or simply wait for
* the remote cpu to finish the schedule(), the latter was found to
* be cheapest.
*/
while (p->oncpu)
cpu_relax();
if (p->sched_class->task_waking)
p->sched_class->task_waking(p);
cpu = select_task_rq(p, SD_BALANCE_WAKE, wake_flags);
#endif
ttwu_queue(p, cpu);
ttwu_stat(p, cpu, wake_flags);
unlock:
raw_spin_unlock_irqrestore(&p->pi_lock, flags);
return ret;
}Re: [RFC][PATCH 5/5] sched: Reduce ttwu rq->lock contention
Quoted 3 lines · Peter Zijlstra
By fully serializing all wakeups using ->pi_lock it becomes a lot simpler
Hmm, yes. Contrary to my expectations ;)
Quoted 16 lines
static int
try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags){ unsigned long flags; int cpu, ret = 0; smp_wmb(); raw_spin_lock_irqsave(&p->pi_lock, flags); if (!(p->state & state)) goto unlock; ret = 1; /* we qualify as a proper wakeup now */ if (p->se.on_rq && ttwu_force(p, state, wake_flags)) goto unlock;
Well. All I can say, I'll try to re-read this code with the fresh head ;) We should ensure that on_rq == 0 can not be racy.
Quoted 3 lines
p->state = TASK_WAKING;
smp_wmb();
raw_spin_unlock_wait(&task_rq(p)->lock);This needs smp_mb(), unlock_wait() reads the memory.
Oleg.
Peter Zijlstra
maintainerRe: [RFC][PATCH 5/5] sched: Reduce ttwu rq->lock contention
Quoted 1 line · Oleg Nesterov
Well. All I can say, I'll try to re-read this code with the fresh head ;)
Right, good plan ;-)
I'll try and clean up my current mess and try to post a new series this weekend (although it looks to be a busy weekend, with the holidays coming up and all).
Re: [RFC][PATCH 5/5] sched: Reduce ttwu rq->lock contention
In reply to Peter ZijlstraQuoted 18 lines · Peter Zijlstra
Quoted 3 lines · Peter Zijlstra
Hrmph, so is it only about serializing concurrent wakeups? If so, we could possibly hold
p->pi_lockover the wakeup.Something like the below.. except it still suffers from the
__migrate_task()hole you identified in your other email.By fully serializing all wakeups using ->pi_lock it becomes a lot simpler (although I just realized we might have a problem with
try_to_wake_up_local).static int
try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags){
unsigned long flags;
int cpu, ret = 0;
Quoted 7 lines
smp_wmb();
raw_spin_lock_irqsave(&p->pi_lock, flags);if (!(p->state & state))
goto unlock;ret = 1; /* we qualify as a proper wakeup now */
Could below happen in this __window__?
p is going through wake_event and it first set TASK_UNINTERRUPTIBLE, then waker see that and above if (!(p->state & state)) passed. But at this time condition == true for p, and p return to run and intend to sleep:
p->state == XXX;
sleep;then we could wake up a process which has wrong state, no?
Quoted 52 lines
if (
p->se.on_rq&&ttwu_force(p, state, wake_flags)) goto unlock;p->sched_contributes_to_load = !!task_contributes_to_load(p);
/*
* In order to serialize against other tasks wanting totask_rq_lock()
* we need to wait until the current task_rq(p)->lock holder goes away,
* so that the next might observeTASK_WAKING.
*/
p->state =TASK_WAKING;
smp_wmb();
raw_spin_unlock_wait(&task_rq(p)->lock);/*
* Stable, now thatTASK_WAKINGis visible. */
cpu =task_cpu(p);#ifdef
CONFIG_SMP
/*
* Catch the case whereschedule()has done the dequeue but hasn't yet
* scheduled to a new task, in that case p is still being referenced
* by that cpu so we cannot wake it to any other cpu.
*
* Here we must either do a full remote enqueue, or simply wait for
* the remote cpu to finish theschedule(), the latter was found to
* be cheapest.
*/
while (p->oncpu)
cpu_relax();if (
p->sched_class->task_waking)
p->sched_class->task_waking(p);cpu =
select_task_rq(p, SD_BALANCE_WAKE, wake_flags); #endif
ttwu_queue(p, cpu);
ttwu_stat(p, cpu,wake_flags);
unlock:
raw_spin_unlock_irqrestore(&p->pi_lock, flags);return ret;
}--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Signature · 1 line
Only stand for myself.
Re: [RFC][PATCH 5/5] sched: Reduce ttwu rq->lock contention
Quoted 12 lines · Yong Zhang
Quoted 10 lines · Peter Zijlstra
static int
try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags){
unsigned long flags;
int cpu, ret = 0;smp_wmb();
raw_spin_lock_irqsave(&p->pi_lock, flags);
Quoted 8 lines
Quoted 4 lines
if (!(p->state & state))
goto unlock;ret = 1; /* we qualify as a proper wakeup now */
Could below happen in this
__window__?p is going through
wake_event
I don't think this can happen with wait_event/wake_up/etc, wait_queue_head_t->lock adds the necessary synchronization.
But, in general,
Quoted 8 lines
and it first set
TASK_UNINTERRUPTIBLE,
then waker see that and above if (!(p->state & state)) passed. But at this time condition == true for p, and p return to run and intend to sleep:p->state == XXX; sleep;then we could wake up a process which has wrong state, no?
I think this is possible, and this is possible whatever we do. Afaics, this patch changes nothing in this sense. Consider:
set_current_state(TASK_INTERRUPTIBLE); set_current_state(TASK_UNINTERRUPTIBLE); schedule();
wake_up_state(TASK_INTERRUPTIBLE) in between can in fact wakeup this task in TASK_UNINTERRUPTIBLE state.
I do not think this is the problem. The user of wake_up_process() should take care and write the correct code ;) And in any case, any wait-event-like code should handle the spurious wakeups correctly.
Or I missed your point?
Oleg.
Re: [RFC][PATCH 5/5] sched: Reduce ttwu rq->lock contention
Quoted 16 lines · Oleg Nesterov
Quoted 15 lines · Yong Zhang
Quoted 13 lines · Peter Zijlstra
static int
try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags){
? ? ? ?unsigned long flags;
? ? ? ?int cpu, ret = 0;? ? ? ?smp_wmb();
? ? ? ?raw_spin_lock_irqsave(&p->pi_lock, flags);? ? ? ?if (!(p->state & state))
? ? ? ? ? ? ? ?goto unlock;
Quoted 8 lines
Quoted 5 lines
Quoted 1 line
? ? ? ?ret = 1; /* we qualify as a proper wakeup now */
Could below happen in this
__window__?p is going through
wake_eventI don't think this can happen with wait_event/wake_up/etc,
wait_queue_head_t->lockadds the necessary synchronization.
Actually I don't take different sight into wait_event/wake_up and sleep/wake_up_process, beause nothing prevent the user from using wake_up_process on an added-to-wait_queue sleeper though we know that it's not recommended.
And you're right wait_queue_head_t->lock privide necessary synchronization with wait_event/wake_up.
Quoted 15 lines
But, in general,
Quoted 8 lines
and it first set
TASK_UNINTERRUPTIBLE,
then waker see that and above if (!(p->state & state)) passed. But at this time condition == true for p, and p return to run and intend to sleep:p->state == XXX; sleep;then we could wake up a process which has wrong state, no?
I think this is possible, and this is possible whatever we do. Afaics, this patch changes nothing in this sense. Consider:
Quoted 7 lines
set_current_state(TASK_INTERRUPTIBLE); set_current_state(TASK_UNINTERRUPTIBLE); schedule();
wake_up_state(TASK_INTERRUPTIBLE)in between can in fact wakeup this task inTASK_UNINTERRUPTIBLEstate.
Hmmm, yeah. I missed that.
Quoted 3 lines
I do not think this is the problem. The user of
wake_up_process()should take care and write the correct code ;)
Fair enough ;)
Quoted 3 lines
And in any case,
any wait-event-like code should handle the spurious wakeups correctly.
Yup.
Thanks,
Yong
Re: [RFC][PATCH 5/5] sched: Reduce ttwu rq->lock contention
In reply to Peter ZijlstraQuoted 2 lines · Peter Zijlstra
Hrmph, so is it only about serializing concurrent wakeups?
I __think__ that it is possible to solve other problems, but of course I am not sure ;)
Quoted 2 lines
If so, we
could possibly holdp->pi_lockover the wakeup.
Hmm, yes, this looks right.
Oleg.
Re: [RFC][PATCH 5/5] sched: Reduce ttwu rq->lock contention
In reply to Oleg NesterovQuoted 23 lines · Oleg Nesterov
kernel/sched.c ttwu_post_activation(struct task_struct · line 2500
Quoted 3 lines · Peter Zijlstra
kernel/sched.c +2
-0+if (p->se.on_rq &&ttwu_force (p, state, wake_flags)) +return 1 ;----- WINDOW -----kernel/sched.c ttwu_post_activation(struct task_struct · line 2518
Quoted 10 lines
kernel/sched.c +10
-0+for (;;) { +unsigned int task_state = p->state; + +if (!(task_state & state)) + goto out; + + load =task_contributes_to_load (p); + +if (cmpxchg (&p->state, task_state,TASK_WAKING ) == task_state) +break ;Suppose that we have a task T sleeping in
TASK_INTERRUPTIBLEstate, and this cpu doestry_to_wake_up(TASK_INTERRUPTIBLE).on_rq== false.try_to_wake_up()starts the "for (;;)" loop.
Quoted 5 lines
However, in the WINDOW above, it is possible that somebody else wakes it up, and then this task changes its state to
TASK_INTERRUPTIBLEagain.Then we set ->state =
TASK_WAKING, but this (still running) T restoresTASK_RUNNINGafter us.
Even simpler. This can race with, say, __migrate_task() which does deactivate_task + activate_task and temporary clears on_rq. Although this is simple to fix, I think.
Also. Afaics, without rq->lock, we can't trust "while (p->oncpu)", at least we need rmb() after that.
Interestingly, I can't really understand the current meaning of smp_wmb() in finish_lock_switch(). Do you know what exactly is buys? In any case, task_running() (or its callers) do not have the corresponding rmb(). Say, currently try_to_wake_up()->task_waking() can miss all changes starting from prepare_lock_switch(). Hopefully this is OK, but I am confused ;)
Oleg.
Peter Zijlstra
maintainerRe: [RFC][PATCH 5/5] sched: Reduce ttwu rq->lock contention
Quoted 27 lines · Oleg Nesterov
Quoted 26 lines · Oleg Nesterov
kernel/sched.c ttwu_post_activation(struct task_struct · line 2500
Quoted 3 lines · Peter Zijlstra
kernel/sched.c +2
-0+if (p->se.on_rq &&ttwu_force (p, state, wake_flags)) +return 1 ;----- WINDOW -----kernel/sched.c ttwu_post_activation(struct task_struct · line 2518
Quoted 10 lines
kernel/sched.c +10
-0+for (;;) { +unsigned int task_state = p->state; + +if (!(task_state & state)) + goto out; + + load =task_contributes_to_load (p); + +if (cmpxchg (&p->state, task_state,TASK_WAKING ) == task_state) +break ;Suppose that we have a task T sleeping in
TASK_INTERRUPTIBLEstate, and this cpu doestry_to_wake_up(TASK_INTERRUPTIBLE).on_rq== false.try_to_wake_up()starts the "for (;;)" loop.However, in the WINDOW above, it is possible that somebody else wakes it up, and then this task changes its state to
TASK_INTERRUPTIBLEagain.
Quoted 6 lines
Quoted 2 lines
Then we set ->state =
TASK_WAKING, but this (still running) T restoresTASK_RUNNINGafter us.Even simpler. This can race with, say,
__migrate_task()which doesdeactivate_task+activate_taskand temporary clearson_rq. Although this is simple to fix, I think.
Yes, another hole..
Quoted 2 lines
Also. Afaics, without
rq->lock, we can't trust "while (p->oncpu)", at least we needrmb()after that.
I think Linus once argued that loops like that should be fine without a rmb(), at worst they'll have to spin a few more times to observe the 1->0 switch (we don't care about the 0->1 switch in this case because that's ruled out by the ->state test).
Quoted 2 lines
Interestingly, I can't really understand the current meaning of
smp_wmb()infinish_lock_switch(). Do you know what exactly is buys?
I _think_ its meant to ensure the full contest switch happened and we've stored all changes to the rq structure (destroying all references to prev), in particular, we've finished writing the new value of current.
Quoted 5 lines
In any case,
task_running()(or its callers) do not have the correspondingrmb(). Say, currently try_to_wake_up()->task_waking() can miss all changes starting fromprepare_lock_switch(). Hopefully this is OK, but I am confused ;)
So I thought I saw how we are OK there, but then I got myself confused too :-)
My argument was something along the lines of there must be some serialization between the task going to sleep and another task waking it (the task setting TASK_UNINTERRUPTIBLE and enqueuing it on a waitqueue, and the waker finding it on the waitqueue), this should be sufficient to make ->state visible to the waker.
If the waker observes a !TASK_RUNNING ->state, then by definition it must see all the changes previous to it (including the ->oncpu 0->1 transition).
But like said, got my brain in a twist too.
Peter Zijlstra
maintainerRe: [RFC][PATCH 5/5] sched: Reduce ttwu rq->lock contention
Quoted 5 lines · Peter Zijlstra
Quoted 3 lines
Even simpler. This can race with, say,
__migrate_task()which doesdeactivate_task+activate_taskand temporary clearson_rq. Although this is simple to fix, I think.Yes, another hole..
__migrate_task() is a tad special in that it should only migrate runnable tasks, but of course we can have it preempted with ->state != TASK_RUNNING, which makes life interesting, but we can fix that by including a PREEMPT_ACTIVE test in ttwu.
Other such callers are more straight fwd though:
rt_mutex_setprio()
set_user_nice()
sched_move_task()
__sched_setscheduler()
normalize_task()
none of those are fast-path operations, so it is quite doable to also take the ->pi_lock there and fully serialize them.
Quoted 6 lines · Peter Zijlstra
Hi, here a new posting of my scary patch(es) ;-)
These actually survive a sembench run (and everything else I threw at it). The discussion between Mike and Frank over the
task_running()check made me realize what was wrong with the previous one.
Quoted 6 lines
As it turns out, what was needed (
p->oncpu) was something Thomas wanted me to do for an entirely different reason (see patch #2).Frank's patch, while encouraging me to poke at it again, has a number of very fundamental problems with it, the most serious one being that it completely wrecks the wake-up load-balancing.
And also as Peter pointed out when I posted the patch (thank you Peter), I did not properly handle the return value for try_to_wake_up() - a rather fatal flaw.
By coincidence, I was about to post a new version of my scary patch when this email arrived. I'll post my patches as a reply to this email, then read through Peter's.
Frank's patch, Version 2
Changes from Version 1:
- Ensure return value of try_to_wake_up() is correct, even when queueing wake up on a different cpu.
- rq->lock contention reduction not as good as first version
patch 1
The core changes. All the scary lock related stuff.
select_task_rq() uses the smp_processor_id() of the old task_cpu(p) instead of the waking smp_processor_id().
patch 2
select_task_rq() uses the smp_processor_id() of the waking smp_processor_id()
Limitations
x86 only
Tests
- tested on 2 cpu x86_64
- very simplistic workload
- results:
rq->lock contention count reduced by ~ 75%
rq->lock contention wait time reduced by ~ 70%
test duration reduction is in the noise
rq->lock contention improvement is slightly better with just patch 1
applied, but the difference is in the noiseTodo
- handle cpu being offlined
-Frank
patch 1 of 2
---
arch/x86/kernel/smp.c | 1 1 + 0 - 0 ! include/linux/sched.h | 5 5 + 0 - 0 ! kernel/sched.c | 105 99 + 6 - 0 ! 3 files changed, 105 insertions(+), 6 deletions(-)
arch/x86/kernel/smp.c +1 -0
@@ -205,6 +205,7 @@ void smp_reschedule_interrupt(struct pt_/* * KVM uses this interrupt to force a cpu out of guest mode */ +sched_ttwu_pending (); }void smp_call_function_interrupt (struct pt_regs *regs)
include/linux/sched.h +4 -0
@@ -1038,6 +1038,7 @@ struct sched_domain;*/ #define WF_SYNC 0x01/* waker goes to sleep after wakup */ #define WF_FORK 0x02/* child wakeup after fork */ +#define WF_LOAD 0x04/* for queued try_to_wake_up() */ #define ENQUEUE_WAKEUP 1#define ENQUEUE_WAKING 2
@@ -1193,6 +1194,8 @@ struct task_struct {int lock_depth;/* BKL lock depth */ #ifdef CONFIG_SMP +struct task_struct *ttwu_queue_wake_entry; +int ttwu_queue_wake_flags;#ifdef __ARCH_WANT_UNLOCKED_CTXSWint oncpu;#endif
@@ -2017,6 +2020,7 @@ extern void release_uids(struct user_namextern void do_timer (unsigned long ticks); +extern void sched_ttwu_pending (void );extern int wake_up_state (struct task_struct *tsk,unsigned int state);extern int wake_up_process (struct task_struct *tsk); extern void wake_up_new_task(struct task_struct *tsk,
kernel/sched.c +122 -10
186 lines not on this page · raw message
Quoted 3 lines · Frank Rowand
patch 1 of 2
The email that explains the context for this does not seem to have gotten through to the list. Here is the email that this patch should have been a reply to:
Quoted 6 lines · Peter Zijlstra
Hi, here a new posting of my scary patch(es) ;-)
These actually survive a sembench run (and everything else I threw at it). The discussion between Mike and Frank over the
task_running()check made me realize what was wrong with the previous one.
Quoted 6 lines
As it turns out, what was needed (
p->oncpu) was something Thomas wanted me to do for an entirely different reason (see patch #2).Frank's patch, while encouraging me to poke at it again, has a number of very fundamental problems with it, the most serious one being that it completely wrecks the wake-up load-balancing.
And also as Peter pointed out when I posted the patch (thank you Peter), I did not properly handle the return value for try_to_wake_up() - a rather fatal flaw.
By coincidence, I was about to post a new version of my scary patch when this email arrived. I'll post my patches as a reply to this email, then read through Peter's.
Frank's patch, Version 2
Changes from Version 1:
- Ensure return value of try_to_wake_up() is correct, even when queueing wake up on a different cpu.
- rq->lock contention reduction not as good as first version
patch 1
The core changes. All the scary lock related stuff.
select_task_rq() uses the smp_processor_id() of the old task_cpu(p) instead of the waking smp_processor_id().
patch 2
select_task_rq() uses the smp_processor_id() of the waking smp_processor_id()
Limitations
x86 only
Tests
- tested on 2 cpu x86_64
- very simplistic workload
- results:
rq->lock contention count reduced by ~ 75%
rq->lock contention wait time reduced by ~ 70%
test duration reduction is in the noise
rq->lock contention improvement is slightly better with just patch 1
applied, but the difference is in the noiseTodo
- handle cpu being offlined
-Frank
Quoted 2 lines · Frank Rowand
select_task_rq()uses thesmp_processor_id()of the oldtask_cpu(p)instead of the wakingsmp_processor_id().
So first you bounce the wakeup to the previous task cpu, when you do select_task_rq() and then you bounce it to the new target?
Quoted 6 lines · Peter Zijlstra
Quoted 2 lines · Frank Rowand
select_task_rq()uses thesmp_processor_id()of the oldtask_cpu(p)instead of the wakingsmp_processor_id().So first you bounce the wakeup to the previous task cpu, when you do
select_task_rq()and then you bounce it to the new target?
Yes. (This is the answer when only the first patch is applied.)
The wakeup is bounced to the previous task cpu. The bounce adds extra overhead (including an IRQ on the previous task cpu) in return for a reduction in the number of rq->lock contentions.
Then the try_to_wake_up() on the previous task cpu may wake the task on a different cpu, but the bias should be the cpu that try_to_wake_up() is now running on.
The second patch in my series instead feeds the waking cpu number to select_task_rq(), so the bias will be to wake the task on the waking cpu.
-Frank
patch 2 of 2
---
include/linux/sched.h +2 -1
@@ -1060,7 +1060,7 @@ struct sched_class {#ifdef CONFIG_SMP int (*select_task_rq)(struct rq *rq,struct task_struct *p, -int sd_flag,int flags); +int sd_flag,int flags,int waking_cpu);void (*pre_schedule) (struct rq *this_rq,struct task_struct *task);void (*post_schedule) (struct rq *this_rq);
@@ -1196,6 +1196,7 @@ struct task_struct {#ifdef CONFIG_SMP struct task_struct *ttwu_queue_wake_entry;int ttwu_queue_wake_flags; +int ttwu_waking_cpu;#ifdef __ARCH_WANT_UNLOCKED_CTXSWint oncpu;#endif
kernel/sched.c +20 -13
@@ -2262,9 +2262,11 @@ static int select_fallback_rq(int cpu, s* The caller (fork, wakeup) owns TASK_WAKING, ->cpus_allowed is stable. */ static inline -int select_task_rq (struct rq *rq,struct task_struct *p,int sd_flags,int wake_flags) +int select_task_rq (struct rq *rq,struct task_struct *p,int sd_flags, +int wake_flags,int waking_cpu) { -int cpu = p->sched_class->select_task_rq (rq, p, sd_flags, wake_flags); +int cpu = p->sched_class->select_task_rq (rq, p, sd_flags, wake_flags, + waking_cpu);/* * In order not to call set_task_cpu() on a blocking task we need
@@ -2335,12 +2337,14 @@ static inline void ttwu_post_activation( }#ifdef CONFIG_SMP -static void ttwu_queue_wake_up (struct task_struct *p,int cpu,int wake_flags) +static void ttwu_queue_wake_up (struct task_struct *p,int this_cpu,int p_cpu, +int wake_flags) {struct task_struct *next =NULL ; -struct rq *rq =cpu_rq (cpu); +struct rq *rq =cpu_rq (p_cpu); p->ttwu_queue_wake_flags = wake_flags; + p->ttwu_waking_cpu = this_cpu;for (;;) {struct task_struct *old = next;
@@ -2352,7 +2356,7 @@ static void ttwu_queue_wake_up(struct ta }if (!next) -smp_send_reschedule (cpu); +smp_send_reschedule (p_cpu); }#endif
@@ -2377,8 +2381,6 @@ static int try_to_wake_up(struct task_st/* * xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx * todo -* - pass waking cpu with queued wake up, to be used in call to -* select_task_rq(). * - handle cpu being offlined * xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx */
@@ -2387,7 +2389,7 @@ static int try_to_wake_up(struct task_stunsigned long en_flags =ENQUEUE_WAKEUP ;struct rq *rq;#ifdef CONFIG_SMP -int load; +int load, waking_cpu;#endif this_cpu =get_cpu ();
@@ -2405,8 +2407,12 @@ static int try_to_wake_up(struct task_st load =task_contributes_to_load (p);if (cmpxchg (&p->state, task_state,TASK_WAKING ) == task_state) { -if (state ==TASK_WAKING ) +if (state ==TASK_WAKING ) { load = wake_flags &WF_LOAD ; + waking_cpu = p->ttwu_waking_cpu; + }else { + waking_cpu = this_cpu; + }break ; } }
@@ -2443,7 +2449,7 @@ static int try_to_wake_up(struct task_stif (cpu != this_cpu) {if (load) wake_flags |=WF_LOAD ; -ttwu_queue_wake_up (p, cpu, wake_flags); +ttwu_queue_wake_up (p, this_cpu, cpu, wake_flags); success =1 ; goto out_nolock; }
@@ -2482,7 +2488,7 @@ static int try_to_wake_up(struct task_st en_flags |=ENQUEUE_WAKING ; } - cpu =select_task_rq (rq, p,SD_BALANCE_WAKE , wake_flags); + cpu =select_task_rq (rq, p,SD_BALANCE_WAKE , wake_flags, waking_cpu);if (cpu != orig_cpu)set_task_cpu (p, cpu);/*
@@ -2728,7 +2734,7 @@ void wake_up_new_task(struct task_struct* We set TASK_WAKING so that select_task_rq() can drop rq->lock * without people poking at ->cpus_allowed. */ - cpu =select_task_rq (rq, p,SD_BALANCE_FORK ,0 ); + cpu =select_task_rq (rq, p,SD_BALANCE_FORK ,0 , cpu);set_task_cpu (p, cpu); p->state =TASK_RUNNING ;
@@ -3327,7 +3333,8 @@ void sched_exec(void)int dest_cpu; rq =task_rq_lock (p, &flags); - dest_cpu = p->sched_class->select_task_rq (rq, p,SD_BALANCE_EXEC ,0 ); + dest_cpu = p->sched_class->select_task_rq (rq, p,SD_BALANCE_EXEC ,0 , +smp_processor_id ());if (dest_cpu ==smp_processor_id ()) goto unlock;
kernel/sched_fair.c +2 -2
@@ -1606,10 +1606,10 @@ static int select_idle_sibling(struct ta* preempt must be disabled. */ static int -select_task_rq_fair (struct rq *rq,struct task_struct *p,int sd_flag,int wake_flags) +select_task_rq_fair (struct rq *rq,struct task_struct *p,int sd_flag, +int wake_flags,int cpu) {struct sched_domain *tmp, *affine_sd =NULL , *sd =NULL ; -int cpu =smp_processor_id ();int prev_cpu =task_cpu (p);int new_cpu = cpu;int want_affine =0 ;
kernel/sched_idletask.c +2 -1
@@ -7,7 +7,8 @@#ifdef CONFIG_SMP static int -select_task_rq_idle (struct rq *rq,struct task_struct *p,int sd_flag,int flags) +select_task_rq_idle (struct rq *rq,struct task_struct *p,int sd_flag, +int flags,int waking_cpu) {return task_cpu (p);/* IDLE tasks as never migrated */ }
kernel/sched_rt.c +2 -1
@@ -973,7 +973,8 @@ static void yield_task_rt(struct rq *rq)static int find_lowest_rq (struct task_struct *task);static int -select_task_rq_rt (struct rq *rq,struct task_struct *p,int sd_flag,int flags) +select_task_rq_rt (struct rq *rq,struct task_struct *p,int sd_flag,int flags, +int waking_cpu) {if (sd_flag !=SD_BALANCE_WAKE )return smp_processor_id ();
kernel/sched_stoptask.c +1 -1
@@ -10,7 +10,7 @@#ifdef CONFIG_SMP static int select_task_rq_stop (struct rq *rq,struct task_struct *p, -int sd_flag,int flags) +int sd_flag,int flags,int waking_cpu) {return task_cpu (p);/* stop tasks as never migrate */ }