Various sched patches -v2
Peter Zijlstra
maintainercover Various sched patches -v2
Here's a set that seems to work properly and hopefully adresses all previously raised issues.
Daniel, I'm sorry, the idle_stamp thing wandered back over to fair.c :-)
I did test the fair bits, including bandwidth (although not very extensively).
I did not test the dl/rt bits, Steve do you have a testcase for that?
Peter Zijlstra
maintainerPATCH 1/9 sched: Remove cpu parameter for idle_balance()
From: Daniel Lezcano <[email protected]>
The cpu parameter passed to idle_balance is not needed as it could be retrieved from the struct rq.
--- kernel/sched/core.c | 2 +- kernel/sched/fair.c | 3 ++- kernel/sched/sched.h | 2 +- 3 files changed, 4 insertions(+), 3 deletions(-)
kernel/sched/core.c +1 -1
@@ -2680,7 +2680,7 @@ static void __sched __schedule(void)pre_schedule (rq, prev);if (unlikely (!rq->nr_running)) -idle_balance (cpu, rq); +idle_balance (rq);put_prev_task (rq, prev); next =pick_next_task (rq);
kernel/sched/fair.c +2 -1
@@ -6359,12 +6359,13 @@ static int load_balance(int this_cpu, st* idle_balance is called by schedule() if this_cpu is about to become * idle. Attempts to pull tasks from other CPUs. */ -void idle_balance (int this_cpu,struct rq *this_rq) +void idle_balance (struct rq *this_rq) {struct sched_domain *sd;int pulled_task =0 ;unsigned long next_balance = jiffies +HZ ;u64 curr_cost =0 ; +int this_cpu = this_rq->cpu; this_rq->idle_stamp =rq_clock (this_rq);
kernel/sched/sched.h +1 -1
@@ -1176,7 +1176,7 @@ extern const struct sched_class idle_schextern void update_group_power (struct sched_domain *sd,int cpu);extern void trigger_load_balance (struct rq *rq); -extern void idle_balance (int this_cpu,struct rq *this_rq); +extern void idle_balance (struct rq *this_rq);extern void idle_enter_fair (struct rq *this_rq);extern void idle_exit_fair (struct rq *this_rq);
Peter Zijlstra
maintainerPATCH 2/9 sched: Fix race in idle_balance()
In reply to Peter ZijlstraFrom: Daniel Lezcano <[email protected]>
The scheduler main function 'schedule()' checks if there are no more tasks on the runqueue. Then it checks if a task should be pulled in the current runqueue in idle_balance() assuming it will go to idle otherwise.
But the idle_balance() releases the rq->lock in order to lookup in the sched domains and takes the lock again right after. That opens a window where another cpu may put a task in our runqueue, so we won't go to idle but we have filled the idle_stamp, thinking we will.
This patch closes the window by checking if the runqueue has been modified but without pulling a task after taking the lock again, so we won't go to idle right after in the __schedule() function.
--- kernel/sched/fair.c | 7 +++++++ 1 file changed, 7 insertions(+)
kernel/sched/fair.c +7 -0
@@ -6417,6 +6417,13 @@ void idle_balance(struct rq *this_rq)raw_spin_lock (&this_rq->lock); +/* +* While browsing the domains, we released the rq lock. +* A task could have be enqueued in the meantime +*/ +if (this_rq->nr_running && !pulled_task) +return ; +if (pulled_task ||time_after (jiffies, this_rq->next_balance)) {/* * We are going idle. next_balance may be set based on
Peter Zijlstra
maintainerPATCH 3/9 sched: Move idle_stamp up to the core
In reply to Peter ZijlstraFrom: Daniel Lezcano <[email protected]>
The idle_balance modifies the idle_stamp field of the rq, making this information to be shared across core.c and fair.c. As we can know if the cpu is going to idle or not with the previous patch, let's encapsulate the idle_stamp information in core.c by moving it up to the caller. The idle_balance function returns true in case a balancing occured and the cpu won't be idle, false if no balance happened and the cpu is going idle.
--- kernel/sched/core.c | 11 +++++++++-- kernel/sched/fair.c | 14 ++++++-------- kernel/sched/sched.h | 2 +- 3 files changed, 16 insertions(+), 11 deletions(-)
kernel/sched/core.c +9 -2
@@ -2681,8 +2681,15 @@ static void __sched __schedule(void)pre_schedule (rq, prev); -if (unlikely (!rq->nr_running)) -idle_balance (rq); +if (unlikely (!rq->nr_running)) { +/* +* We must set idle_stamp _before_ calling idle_balance(), such +* that we measure the duration of idle_balance() as idle time. +*/ + rq->idle_stamp =rq_clock (rq); +if (idle_balance (rq)) + rq->idle_stamp =0 ; + }put_prev_task (rq, prev); next =pick_next_task (rq);
kernel/sched/fair.c +6 -8
@@ -6535,7 +6535,7 @@ static int load_balance(int this_cpu, st* idle_balance is called by schedule() if this_cpu is about to become * idle. Attempts to pull tasks from other CPUs. */ -void idle_balance (struct rq *this_rq) +int idle_balance (struct rq *this_rq) {struct sched_domain *sd;int pulled_task =0 ;
@@ -6543,10 +6543,8 @@ void idle_balance(struct rq *this_rq)u64 curr_cost =0 ;int this_cpu = this_rq->cpu; - this_rq->idle_stamp =rq_clock (this_rq); -if (this_rq->avg_idle < sysctl_sched_migration_cost) -return ; +return 0 ;/* * Drop the rq->lock, but keep IRQ/preempt disabled.
@@ -6584,10 +6582,8 @@ void idle_balance(struct rq *this_rq) interval =msecs_to_jiffies (sd->balance_interval);if (time_after (next_balance, sd->last_balance + interval)) next_balance = sd->last_balance + interval; -if (pulled_task) { - this_rq->idle_stamp =0 ; +if (pulled_task)break ; - } }rcu_read_unlock ();
@@ -6598,7 +6594,7 @@ void idle_balance(struct rq *this_rq)* A task could have be enqueued in the meantime */ if (this_rq->nr_running && !pulled_task) -return ; +return 1 ;if (pulled_task ||time_after (jiffies, this_rq->next_balance)) {/*
@@ -6610,6 +6606,8 @@ void idle_balance(struct rq *this_rq)if (curr_cost > this_rq->max_idle_balance_cost) this_rq->max_idle_balance_cost = curr_cost; + +return pulled_task; }/*
kernel/sched/sched.h +1 -1
@@ -1176,7 +1176,7 @@ extern const struct sched_class idle_schextern void update_group_power (struct sched_domain *sd,int cpu);extern void trigger_load_balance (struct rq *rq); -extern void idle_balance (struct rq *this_rq); +extern int idle_balance (struct rq *this_rq);extern void idle_enter_fair (struct rq *this_rq);extern void idle_exit_fair (struct rq *this_rq);
Peter Zijlstra
maintainerPATCH 4/9 sched/fair: Track cgroup depth
In reply to Peter ZijlstraTrack depth in cgroup tree, this is useful for things like find_matching_se() where you need to get to a common parent of two sched entities.
Keeping the depth avoids having to calculate it on the spot, which saves a number of possible cache-misses.
--- include/linux/sched.h | 1 + kernel/sched/fair.c | 47 +++++++++++++++++++++-------------------------- 2 files changed, 22 insertions(+), 26 deletions(-)
include/linux/sched.h +1 -0
@@ -1064,6 +1064,7 @@ struct sched_entity {#endif #ifdef CONFIG_FAIR_GROUP_SCHED +int depth;struct sched_entity *parent;/* rq on which this entity is (to be) queued: */ struct cfs_rq *cfs_rq;
kernel/sched/fair.c +21 -26
109 lines not on this page · raw message
Peter Zijlstra
maintainerPATCH 5/9 sched: Push put_prev_task() into pick_next_task()
In reply to Peter ZijlstraIn order to avoid having to do put/set on a whole cgroup hierarchy when we context switch, push the put into pick_next_task() so that both operations are in the same function. Further changes then allow us to possibly optimize away redundant work.
--- kernel/sched/core.c | 21 ++++++++------------- kernel/sched/deadline.c | 4 +++- kernel/sched/fair.c | 5 ++++- kernel/sched/idle_task.c | 5 ++++- kernel/sched/rt.c | 26 +++++++++++++++----------- kernel/sched/sched.h | 8 +++++++- kernel/sched/stop_task.c | 14 ++++++++------ 7 files changed, 49 insertions(+), 34 deletions(-)
kernel/sched/core.c +8 -13
@@ -2556,18 +2556,11 @@ static inline void schedule_debug(structschedstat_inc (this_rq (), sched_count); } -static void put_prev_task (struct rq *rq,struct task_struct *prev) -{ -if (prev->on_rq || rq->skip_clock_update <0 ) -update_rq_clock (rq); - prev->sched_class->put_prev_task (rq, prev); -} -/* * Pick up the highest-prio task: */ static inline struct task_struct * -pick_next_task (struct rq *rq) +pick_next_task (struct rq *rq,struct task_struct *prev) {const struct sched_class *class;struct task_struct *p;
@@ -2577,13 +2570,13 @@ pick_next_task(struct rq *rq)* the fair class we can call that function directly: */ if (likely (rq->nr_running == rq->cfs.h_nr_running)) { - p = fair_sched_class.pick_next_task (rq); + p = fair_sched_class.pick_next_task (rq, prev);if (likely (p))return p; }for_each_class (class) { - p = class->pick_next_task (rq); + p = class->pick_next_task (rq, prev);if (p)return p; }
@@ -2691,8 +2684,10 @@ static void __sched __schedule(void) rq->idle_stamp =0 ; } -put_prev_task (rq, prev); - next =pick_next_task (rq); +if (prev->on_rq || rq->skip_clock_update <0 ) +update_rq_clock (rq); + + next =pick_next_task (rq, prev);clear_tsk_need_resched (prev);clear_preempt_need_resched (); rq->skip_clock_update =0 ;
@@ -4734,7 +4729,7 @@ static void migrate_tasks(unsigned int dif (rq->nr_running ==1 )break ; - next =pick_next_task (rq); + next =pick_next_task (rq,NULL );BUG_ON (!next); next->sched_class->put_prev_task (rq, next);
kernel/sched/deadline.c +3 -1
@@ -989,7 +989,7 @@ static struct sched_dl_entity *pick_next return rb_entry(left, struct sched_dl_entity, rb_node); } -struct task_struct *pick_next_task_dl (struct rq *rq) +struct task_struct *pick_next_task_dl (struct rq *rq,struct task_struct *prev) {struct sched_dl_entity *dl_se;struct task_struct *p;
@@ -1000,6 +1000,8 @@ struct task_struct *pick_next_task_dl(stif (unlikely (!dl_rq->dl_nr_running))return NULL ; + prev->sched_class->put_prev_task (rq, prev); + dl_se =pick_next_dl_entity (rq, dl_rq);BUG_ON (!dl_se);
kernel/sched/fair.c +4 -1
@@ -4659,7 +4659,8 @@ static void check_preempt_wakeup(structset_last_buddy (se); } -static struct task_struct *pick_next_task_fair (struct rq *rq) +static struct task_struct * +pick_next_task_fair (struct rq *rq,struct task_struct *prev) {struct task_struct *p;struct cfs_rq *cfs_rq = &rq->cfs;
@@ -4668,6 +4669,8 @@ static struct task_struct *pick_next_tasif (!cfs_rq->nr_running)return NULL ; + prev->sched_class->put_prev_task (rq, prev); + do { se = pick_next_entity(cfs_rq); set_next_entity(cfs_rq, se);
kernel/sched/idle_task.c +4 -1
@@ -33,8 +33,11 @@ static void check_preempt_curr_idle(struresched_task (rq->idle); } -static struct task_struct *pick_next_task_idle (struct rq *rq) +static struct task_struct * +pick_next_task_idle (struct rq *rq,struct task_struct *prev) { + prev->sched_class->put_prev_task (rq, prev); +schedstat_inc (rq, sched_goidle);#ifdef CONFIG_SMP /* Trigger the post schedule to do an idle_enter for CFS */
kernel/sched/rt.c +15 -11
@@ -1310,15 +1310,7 @@ static struct task_struct *_pick_next_ta {struct sched_rt_entity *rt_se;struct task_struct *p; -struct rt_rq *rt_rq; - - rt_rq = &rq->rt; - -if (!rt_rq->rt_nr_running) -return NULL ; - -if (rt_rq_throttled (rt_rq)) -return NULL ; +struct rt_rq *rt_rq = &rq->rt; do { rt_se = pick_next_rt_entity(rq, rt_rq);
@@ -1332,9 +1324,21 @@ static struct task_struct *_pick_next_tareturn p; } -static struct task_struct *pick_next_task_rt (struct rq *rq) +static struct task_struct * +pick_next_task_rt (struct rq *rq,struct task_struct *prev) { -struct task_struct *p =_pick_next_task_rt (rq); +struct task_struct *p; +struct rt_rq *rt_rq = &rq->rt; + +if (!rt_rq->rt_nr_running) +return NULL ; + +if (rt_rq_throttled (rt_rq)) +return NULL ; + + prev->sched_class->put_prev_task (rq, prev); + + p =_pick_next_task_rt (rq);/* The running task is never eligible for pushing */ if (p)
kernel/sched/sched.h +7 -1
@@ -1123,7 +1123,13 @@ struct sched_class {void (*check_preempt_curr) (struct rq *rq,struct task_struct *p,int flags); -struct task_struct * (*pick_next_task) (struct rq *rq); +/* +* It is the responsibility of the pick_next_task() method that will +* return the next task to call put_prev_task() on the @prev task or +* something equivalent. +*/ +struct task_struct * (*pick_next_task) (struct rq *rq, +struct task_struct *prev);void (*put_prev_task) (struct rq *rq,struct task_struct *p);#ifdef CONFIG_SMP
kernel/sched/stop_task.c +8 -6
@@ -23,16 +23,18 @@ check_preempt_curr_stop(struct rq *rq, s/* we're never preempted */ } -static struct task_struct *pick_next_task_stop (struct rq *rq) +static struct task_struct * +pick_next_task_stop (struct rq *rq,struct task_struct *prev) {struct task_struct *stop = rq->stop; -if (stop && stop->on_rq) { - stop->se.exec_start =rq_clock_task (rq); -return stop; - } +if (!stop || !stop->on_rq) +return NULL ; -return NULL ; + prev->sched_class->put_prev_task (rq, prev); + stop->se.exec_start =rq_clock_task (rq); + +return stop; } static void
[email protected]
reviewerRe: [PATCH 5/9] sched: Push put_prev_task() into pick_next_task()
Quoted 68 lines · Peter Zijlstra
In order to avoid having to do put/set on a whole cgroup hierarchy when we context switch, push the put into
pick_next_task()so that both operations are in the same function. Further changes then allow us to possibly optimize away redundant work.Signed-off-by Peter Zijlstra <[email protected]>--- kernel/sched/core.c | 21 ++++++++------------- kernel/sched/deadline.c | 4 +++- kernel/sched/fair.c | 5 ++++- kernel/sched/idle_task.c | 5 ++++- kernel/sched/rt.c | 26 +++++++++++++++----------- kernel/sched/sched.h | 8 +++++++- kernel/sched/stop_task.c | 14 ++++++++------ 7 files changed, 49 insertions(+), 34 deletions(-)kernel/sched/core.c +7
-12@@ -2556,18 +2556,11 @@ static inline void schedule_debug(structschedstat_inc (this_rq (), sched_count); } -static void put_prev_task (struct rq *rq,struct task_struct *prev) -{ -if (prev->on_rq || rq->skip_clock_update <0 ) -update_rq_clock (rq); - prev->sched_class->put_prev_task (rq, prev); -} -/* * Pick up the highest-prio task: */ static inline struct task_struct * -pick_next_task (struct rq *rq) +pick_next_task (struct rq *rq,struct task_struct *prev) {const struct sched_class *class;struct task_struct *p;@@ -2577,13 +2570,13 @@ pick_next_task(struct rq *rq)* the fair class we can call that function directly: */ if (likely (rq->nr_running == rq->cfs.h_nr_running)) { - p = fair_sched_class.pick_next_task (rq); + p = fair_sched_class.pick_next_task (rq, prev);if (likely (p))return p; }for_each_class (class) { - p = class->pick_next_task (rq); + p = class->pick_next_task (rq, prev);if (p)return p; }@@ -2691,8 +2684,10 @@ static void __sched __schedule(void) rq->idle_stamp =0 ; } -put_prev_task (rq, prev); - next =pick_next_task (rq); +if (prev->on_rq || rq->skip_clock_update <0 ) +update_rq_clock (rq); + + next =pick_next_task (rq, prev);clear_tsk_need_resched (prev);clear_preempt_need_resched (); rq->skip_clock_update =0 ;
kernel/sched/core.c static void migrate_tasks(unsigned int d · line 4732
Quoted 5 lines
kernel/sched/core.c +1
-1@@ -4734,7 +4729,7 @@ static void migrate_tasks(unsigned int dif (rq->nr_running ==1 )break ; - next =pick_next_task (rq); + next =pick_next_task (rq,NULL );
This seems to be incorrect without the if (prev) lines in pick_next_task_foo, since foo_nr_running isn't enough to save us.
Quoted 146 lines
kernel/sched/core.c +0
-0BUG_ON (!next); next->sched_class->put_prev_task (rq, next);kernel/sched/deadline.c +3
-1@@ -989,7 +989,7 @@ static struct sched_dl_entity *pick_next return rb_entry(left, struct sched_dl_entity, rb_node); } -struct task_struct *pick_next_task_dl (struct rq *rq) +struct task_struct *pick_next_task_dl (struct rq *rq,struct task_struct *prev) {struct sched_dl_entity *dl_se;struct task_struct *p;@@ -1000,6 +1000,8 @@ struct task_struct *pick_next_task_dl(stif (unlikely (!dl_rq->dl_nr_running))return NULL ; + prev->sched_class->put_prev_task (rq, prev); + dl_se =pick_next_dl_entity (rq, dl_rq);BUG_ON (!dl_se);kernel/sched/fair.c +4
-1@@ -4659,7 +4659,8 @@ static void check_preempt_wakeup(structset_last_buddy (se); } -static struct task_struct *pick_next_task_fair (struct rq *rq) +static struct task_struct * +pick_next_task_fair (struct rq *rq,struct task_struct *prev) {struct task_struct *p;struct cfs_rq *cfs_rq = &rq->cfs;@@ -4668,6 +4669,8 @@ static struct task_struct *pick_next_tasif (!cfs_rq->nr_running)return NULL ; + prev->sched_class->put_prev_task (rq, prev); + do { se = pick_next_entity(cfs_rq); set_next_entity(cfs_rq, se);kernel/sched/idle_task.c +4
-1@@ -33,8 +33,11 @@ static void check_preempt_curr_idle(struresched_task (rq->idle); } -static struct task_struct *pick_next_task_idle (struct rq *rq) +static struct task_struct * +pick_next_task_idle (struct rq *rq,struct task_struct *prev) { + prev->sched_class->put_prev_task (rq, prev); +schedstat_inc (rq, sched_goidle);#ifdef CONFIG_SMP /* Trigger the post schedule to do an idle_enter for CFS */ kernel/sched/rt.c +15
-11@@ -1310,15 +1310,7 @@ static struct task_struct *_pick_next_ta {struct sched_rt_entity *rt_se;struct task_struct *p; -struct rt_rq *rt_rq; - - rt_rq = &rq->rt; - -if (!rt_rq->rt_nr_running) -return NULL ; - -if (rt_rq_throttled (rt_rq)) -return NULL ; +struct rt_rq *rt_rq = &rq->rt; do { rt_se = pick_next_rt_entity(rq, rt_rq);@@ -1332,9 +1324,21 @@ static struct task_struct *_pick_next_tareturn p; } -static struct task_struct *pick_next_task_rt (struct rq *rq) +static struct task_struct * +pick_next_task_rt (struct rq *rq,struct task_struct *prev) { -struct task_struct *p =_pick_next_task_rt (rq); +struct task_struct *p; +struct rt_rq *rt_rq = &rq->rt; + +if (!rt_rq->rt_nr_running) +return NULL ; + +if (rt_rq_throttled (rt_rq)) +return NULL ; + + prev->sched_class->put_prev_task (rq, prev); + + p =_pick_next_task_rt (rq);/* The running task is never eligible for pushing */ if (p)kernel/sched/sched.h +7
-1@@ -1123,7 +1123,13 @@ struct sched_class {void (*check_preempt_curr) (struct rq *rq,struct task_struct *p,int flags); -struct task_struct * (*pick_next_task) (struct rq *rq); +/* +* It is the responsibility of the pick_next_task() method that will +* return the next task to call put_prev_task() on the @prev task or +* something equivalent. +*/ +struct task_struct * (*pick_next_task) (struct rq *rq, +struct task_struct *prev);void (*put_prev_task) (struct rq *rq,struct task_struct *p);#ifdef CONFIG_SMP kernel/sched/stop_task.c +8
-6@@ -23,16 +23,18 @@ check_preempt_curr_stop(struct rq *rq, s/* we're never preempted */ } -static struct task_struct *pick_next_task_stop (struct rq *rq) +static struct task_struct * +pick_next_task_stop (struct rq *rq,struct task_struct *prev) {struct task_struct *stop = rq->stop; -if (stop && stop->on_rq) { - stop->se.exec_start =rq_clock_task (rq); -return stop; - } +if (!stop || !stop->on_rq) +return NULL ; -return NULL ; + prev->sched_class->put_prev_task (rq, prev); + stop->se.exec_start =rq_clock_task (rq); + +return stop; } static void
Peter Zijlstra
maintainerRe: [PATCH 5/9] sched: Push put_prev_task() into pick_next_task()
Quoted 9 lines · On Tue, Jan 28, 2014 at 10:46:18AM -0800, [email protected] wrote:
kernel/sched/core.c static void migrate_tasks(unsigned int d · line 4732
Quoted 6 lines
kernel/sched/core.c +1
-1@@ -4734,7 +4729,7 @@ static void migrate_tasks(unsigned int dif (rq->nr_running ==1 )break ; - next =pick_next_task (rq); + next =pick_next_task (rq,NULL );This seems to be incorrect without the if (prev) lines in
pick_next_task_foo, sincefoo_nr_runningisn't enough to save us.
ARgh, I knew there must've been a reason I had those :/
Peter Zijlstra
maintainerPATCH 6/9 sched/fair: Clean up __clear_buddies_*
In reply to Peter ZijlstraSlightly easier code flow, no functional changes.
--- kernel/sched/fair.c | 18 +++++++++--------- 1 file changed, 9 insertions(+), 9 deletions(-)
kernel/sched/fair.c +9 -9
@@ -2567,10 +2567,10 @@ static void __clear_buddies_last(struct {for_each_sched_entity (se) {struct cfs_rq *cfs_rq =cfs_rq_of (se); -if (cfs_rq->last == se) - cfs_rq->last =NULL ; -else +if (cfs_rq->last != se)break ; + + cfs_rq->last =NULL ; } }
@@ -2578,10 +2578,10 @@ static void __clear_buddies_next(struct {for_each_sched_entity (se) {struct cfs_rq *cfs_rq =cfs_rq_of (se); -if (cfs_rq->next == se) - cfs_rq->next =NULL ; -else +if (cfs_rq->next != se)break ; + + cfs_rq->next =NULL ; } }
@@ -2589,10 +2589,10 @@ static void __clear_buddies_skip(struct {for_each_sched_entity (se) {struct cfs_rq *cfs_rq =cfs_rq_of (se); -if (cfs_rq->skip == se) - cfs_rq->skip =NULL ; -else +if (cfs_rq->skip != se)break ; + + cfs_rq->skip =NULL ; } }
Peter Zijlstra
maintainerPATCH 7/9 sched/fair: Optimize cgroup pick_next_task_fair
In reply to Peter ZijlstraSince commit 2f36825b1 ("sched: Next buddy hint on sleep and preempt path") it is likely we pick a new task from the same cgroup, doing a put and then set on all intermediate entities is a waste of time, so try to avoid this.
Measured using:
mount nodev /cgroup -t cgroup -o cpu
cd /cgroup
mkdir a; cd a
mkdir b; cd b
mkdir c; cd c
echo $$ > tasks
perf stat --repeat 10 -- taskset 1 perf bench sched pipe
PRE : 4.542422684 seconds time elapsed ( +- 0.33% ) POST: 4.389409991 seconds time elapsed ( +- 0.32% )
Which shows a significant improvement of ~3.5%
--- kernel/sched/fair.c | 122 ++++++++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 110 insertions(+), 12 deletions(-)
kernel/sched/fair.c +110 -12
@@ -2911,17 +2911,36 @@ wakeup_preempt_entity(struct sched_entit* 3) pick the "last" process, for cache locality * 4) do not run the "skip" process, if something else is available */ -static struct sched_entity *pick_next_entity (struct cfs_rq *cfs_rq) +static struct sched_entity * +pick_next_entity (struct cfs_rq *cfs_rq,struct sched_entity *curr) { -struct sched_entity *se =__pick_first_entity (cfs_rq); -struct sched_entity *left = se; +struct sched_entity *left =__pick_first_entity (cfs_rq); +struct sched_entity *se; + +/* +* If curr is set we have to see if its left of the leftmost entity +* still in the tree, provided there was anything in the tree at all. +*/ +if (!left || (curr &&entity_before (curr, left))) + left = curr; + + se = left;/* ideally we run the leftmost entity */ /* * Avoid running the skip buddy, if running something else can * be done without getting too unfair. */ if (cfs_rq->skip == se) { -struct sched_entity *second =__pick_next_entity (se); +struct sched_entity *second; + +if (se == curr) { + second =__pick_first_entity (cfs_rq); + }else { + second =__pick_next_entity (se); +if (!second || (curr &&entity_before (curr, second))) + second = curr; + } +if (second &&wakeup_preempt_entity (second, left) <1 ) se = second; }
@@ -2943,7 +2962,7 @@ static struct sched_entity *pick_next_enreturn se; } -static void check_cfs_rq_runtime (struct cfs_rq *cfs_rq); +static bool check_cfs_rq_runtime (struct cfs_rq *cfs_rq);static void put_prev_entity (struct cfs_rq *cfs_rq,struct sched_entity *prev) {
@@ -3598,22 +3617,23 @@ static void check_enqueue_throttle(struc }/* conditionally throttle active cfs_rq's from put_prev_entity() */ -static void check_cfs_rq_runtime (struct cfs_rq *cfs_rq) +static bool check_cfs_rq_runtime (struct cfs_rq *cfs_rq) {if (!cfs_bandwidth_used ()) -return ; +return false;if (likely (!cfs_rq->runtime_enabled || cfs_rq->runtime_remaining >0 )) -return ; +return false;/* * it's possible for a throttled entity to be forced into a running * state (e.g. set_curr_task), in this case we're finished. */ if (cfs_rq_throttled (cfs_rq)) -return ; +return true;throttle_cfs_rq (cfs_rq); +return true; }static enum hrtimer_restart sched_cfs_slack_timer (struct hrtimer *timer)
@@ -3723,7 +3743,7 @@ static inline u64 cfs_rq_clock_task(stru }static void account_cfs_rq_runtime (struct cfs_rq *cfs_rq,u64 delta_exec) {} -static void check_cfs_rq_runtime (struct cfs_rq *cfs_rq) {} +static bool check_cfs_rq_runtime (struct cfs_rq *cfs_rq) {return false; }static void check_enqueue_throttle (struct cfs_rq *cfs_rq) {} static __always_inline void return_cfs_rq_runtime(struct cfs_rq *cfs_rq) {}
@@ -4662,9 +4682,86 @@ static void check_preempt_wakeup(structstatic struct task_struct *pick_next_task_fair (struct rq *rq,struct task_struct *prev) { -struct task_struct *p;struct cfs_rq *cfs_rq = &rq->cfs;struct sched_entity *se; +struct task_struct *p; + +#ifdef CONFIG_FAIR_GROUP_SCHED +if (!cfs_rq->nr_running) +return NULL ; + +if (prev->sched_class != &fair_sched_class) + goto simple; + +/* +* Because of the set_next_buddy() in dequeue_task_fair() it is rather +* likely that a next task is from the same cgroup as the current. +* +* Therefore attempt to avoid putting and setting the entire cgroup +* hierarchy, only change the part that actually changes. +*/ + +do { +struct sched_entity *curr = cfs_rq->curr; + +/* +* Since we got here without doing put_prev_entity() we also +* have to consider cfs_rq->curr. If it is still a runnable +* entity, update_curr() will update its vruntime, otherwise +* forget we've ever seen it. +*/ +if (curr && curr->on_rq) +update_curr (cfs_rq); +else + curr =NULL ; + +/* +* This call to check_cfs_rq_runtime() will do the throttle and +* dequeue its entity in the parent(s). Therefore the 'simple' +* nr_running test will indeed be correct. +*/ +if (unlikely (check_cfs_rq_runtime (cfs_rq))) + goto simple; + + se =pick_next_entity (cfs_rq, curr); + cfs_rq =group_cfs_rq (se); + }while (cfs_rq); + + p =task_of (se); + +/* +* Since we haven't yet done put_prev_entity and if the selected task +* is a different task than we started out with, try and touch the +* least amount of cfs_rqs. +*/ +if (prev != p) { +struct sched_entity *pse = &prev->se; + +while (!(cfs_rq =is_same_group (se, pse))) { +int se_depth = se->depth; +int pse_depth = pse->depth; + +if (se_depth <= pse_depth) { +put_prev_entity (cfs_rq_of (pse), pse); + pse =parent_entity (pse); + } +if (se_depth >= pse_depth) { +set_next_entity (cfs_rq_of (se), se); + se =parent_entity (se); + } + } + +put_prev_entity (cfs_rq, pse); +set_next_entity (cfs_rq, se); + } + +if (hrtick_enabled (rq)) +hrtick_start_fair (rq, p); + +return p; +simple: + cfs_rq = &rq->cfs; +#endif if (!cfs_rq->nr_running)return NULL ;
@@ -4672,12 +4769,13 @@ pick_next_task_fair(struct rq *rq, struc prev->sched_class->put_prev_task (rq, prev);do { - se =pick_next_entity (cfs_rq); + se =pick_next_entity (cfs_rq,NULL );set_next_entity (cfs_rq, se); cfs_rq =group_cfs_rq (se); }while (cfs_rq); p =task_of (se); +if (hrtick_enabled (rq))hrtick_start_fair (rq, p);
Vincent Guittot
maintainerRe: [PATCH 7/9] sched/fair: Optimize cgroup pick_next_task_fair
On 28 January 2014 18:16, Peter Zijlstra <[email protected]> wrote:
[snip]
kernel/sched/fair.c static void check_preempt_wakeup(struct · line 4691
Quoted 13 lines
kernel/sched/fair.c +5
-1@@ -4662,9 +4682,86 @@ static void check_preempt_wakeup(structstatic struct task_struct *pick_next_task_fair (struct rq *rq,struct task_struct *prev) { -struct task_struct *p;struct cfs_rq *cfs_rq = &rq->cfs;struct sched_entity *se; +struct task_struct *p; + +#ifdef CONFIG_FAIR_GROUP_SCHED +if (!cfs_rq->nr_running) +return NULL ;
Couldn't you move the test above out of the CONFIG_FAIR_GROUP_SCHED and remove the same test that is done after the simple label
Vincent
Quoted 93 lines
kernel/sched/fair.c +75
-1+ +if (prev->sched_class != &fair_sched_class) + goto simple; + +/* +* Because of the set_next_buddy() in dequeue_task_fair() it is rather +* likely that a next task is from the same cgroup as the current. +* +* Therefore attempt to avoid putting and setting the entire cgroup +* hierarchy, only change the part that actually changes. +*/ + +do { +struct sched_entity *curr = cfs_rq->curr; + +/* +* Since we got here without doing put_prev_entity() we also +* have to consider cfs_rq->curr. If it is still a runnable +* entity, update_curr() will update its vruntime, otherwise +* forget we've ever seen it. +*/ +if (curr && curr->on_rq) +update_curr (cfs_rq); +else + curr =NULL ; + +/* +* This call to check_cfs_rq_runtime() will do the throttle and +* dequeue its entity in the parent(s). Therefore the 'simple' +* nr_running test will indeed be correct. +*/ +if (unlikely (check_cfs_rq_runtime (cfs_rq))) + goto simple; + + se =pick_next_entity (cfs_rq, curr); + cfs_rq =group_cfs_rq (se); + }while (cfs_rq); + + p =task_of (se); + +/* +* Since we haven't yet done put_prev_entity and if the selected task +* is a different task than we started out with, try and touch the +* least amount of cfs_rqs. +*/ +if (prev != p) { +struct sched_entity *pse = &prev->se; + +while (!(cfs_rq =is_same_group (se, pse))) { +int se_depth = se->depth; +int pse_depth = pse->depth; + +if (se_depth <= pse_depth) { +put_prev_entity (cfs_rq_of (pse), pse); + pse =parent_entity (pse); + } +if (se_depth >= pse_depth) { +set_next_entity (cfs_rq_of (se), se); + se =parent_entity (se); + } + } + +put_prev_entity (cfs_rq, pse); +set_next_entity (cfs_rq, se); + } + +if (hrtick_enabled (rq)) +hrtick_start_fair (rq, p); + +return p; +simple: + cfs_rq = &rq->cfs; +#endif if (!cfs_rq->nr_running)return NULL ;@@ -4672,12 +4769,13 @@ pick_next_task_fair(struct rq *rq, struc prev->sched_class->put_prev_task (rq, prev);do { - se =pick_next_entity (cfs_rq); + se =pick_next_entity (cfs_rq,NULL );set_next_entity (cfs_rq, se); cfs_rq =group_cfs_rq (se); }while (cfs_rq); p =task_of (se); +if (hrtick_enabled (rq))hrtick_start_fair (rq, p);
Peter Zijlstra
maintainerRe: [PATCH 7/9] sched/fair: Optimize cgroup pick_next_task_fair
Quoted 5 lines · Vincent Guittot
On 28 January 2014 18:16, Peter Zijlstra <[email protected]> wrote:
[snip]
Quoted 1 line
Quoted 15 lines
kernel/sched/fair.c static void check_preempt_wakeup(struct · line 4691
Quoted 12 lines
kernel/sched/fair.c +5
-1@@ -4662,9 +4682,86 @@ static void check_preempt_wakeup(structstatic struct task_struct *pick_next_task_fair (struct rq *rq,struct task_struct *prev) { -struct task_struct *p;struct cfs_rq *cfs_rq = &rq->cfs;struct sched_entity *se; +struct task_struct *p; + +#ifdef CONFIG_FAIR_GROUP_SCHED +if (!cfs_rq->nr_running) +return NULL ;Couldn't you move the test above out of the
CONFIG_FAIR_GROUP_SCHEDand remove the same test that is done after the simple label
No, we have to check it twice because..
Quoted 26 lines
Quoted 26 lines
kernel/sched/fair.c +25
-0+ +if (prev->sched_class != &fair_sched_class) + goto simple; + +/* +* Because of the set_next_buddy() in dequeue_task_fair() it is rather +* likely that a next task is from the same cgroup as the current. +* +* Therefore attempt to avoid putting and setting the entire cgroup +* hierarchy, only change the part that actually changes. +*/ + + do { + struct sched_entity *curr = cfs_rq->curr; + + /* + * Since we got here without doing put_prev_entity() we also + * have to consider cfs_rq->curr. If it is still a runnable + * entity, update_curr() will update its vruntime, otherwise + * forget we've ever seen it. + */ + if (curr && curr->on_rq) + update_curr(cfs_rq); + else + curr = NULL;
Quoted 8 lines
kernel/sched/fair.c static void check_preempt_wakeup(struct · line 4724
Quoted 8 lines
kernel/sched/fair.c +8
-0+ +/* +* This call to check_cfs_rq_runtime() will do the throttle and +* dequeue its entity in the parent(s). Therefore the 'simple' +* nr_running test will indeed be correct. +*/ +if (unlikely (check_cfs_rq_runtime (cfs_rq))) + goto simple;
... here if you read the comment above, we could have modified the nr_running.
Quoted 40 lines
Quoted 40 lines
kernel/sched/fair.c +39
-0+ se =pick_next_entity (cfs_rq, curr); + cfs_rq =group_cfs_rq (se); + } while (cfs_rq); + + p =task_of (se); + +/* +* Since we haven't yet done put_prev_entity and if the selected task +* is a different task than we started out with, try and touch the +* least amount of cfs_rqs. +*/ +if (prev != p) { +struct sched_entity *pse = &prev->se; + +while (!(cfs_rq =is_same_group (se, pse))) { +int se_depth = se->depth; +int pse_depth = pse->depth; + +if (se_depth <= pse_depth) { +put_prev_entity (cfs_rq_of (pse), pse); + pse =parent_entity (pse); + } +if (se_depth >= pse_depth) { +set_next_entity (cfs_rq_of (se), se); + se =parent_entity (se); + } + } + +put_prev_entity (cfs_rq, pse); +set_next_entity (cfs_rq, se); + } + +if (hrtick_enabled (rq)) +hrtick_start_fair (rq, p); + +return p; +simple: + cfs_rq = &rq->cfs; +#endif
Quoted 2 lines
kernel/sched/fair.c static void check_preempt_wakeup(struct · line 4767
Quoted 2 lines
kernel/sched/fair.c +0
-0if (!cfs_rq->nr_running)return NULL ;
And therefore this test needs to stay.
Vincent Guittot
maintainerRe: [PATCH 7/9] sched/fair: Optimize cgroup pick_next_task_fair
Quoted 52 lines · Peter Zijlstra
Quoted 5 lines · Vincent Guittot
On 28 January 2014 18:16, Peter Zijlstra <[email protected]> wrote:
[snip]
Quoted 1 line
Quoted 15 lines
kernel/sched/fair.c static void check_preempt_wakeup(struct · line 4691
Quoted 12 lines
kernel/sched/fair.c +5
-1@@ -4662,9 +4682,86 @@ static void check_preempt_wakeup(structstatic struct task_struct *pick_next_task_fair (struct rq *rq,struct task_struct *prev) { -struct task_struct *p;struct cfs_rq *cfs_rq = &rq->cfs;struct sched_entity *se; +struct task_struct *p; + +#ifdef CONFIG_FAIR_GROUP_SCHED +if (!cfs_rq->nr_running) +return NULL ;Couldn't you move the test above out of the
CONFIG_FAIR_GROUP_SCHEDand remove the same test that is done after the simple labelNo, we have to check it twice because..
Quoted 29 lines
Quoted 29 lines
kernel/sched/fair.c +28
-0+ +if (prev->sched_class != &fair_sched_class) + goto simple; + +/* +* Because of the set_next_buddy() in dequeue_task_fair() it is rather +* likely that a next task is from the same cgroup as the current. +* +* Therefore attempt to avoid putting and setting the entire cgroup +* hierarchy, only change the part that actually changes. +*/ + + do { + struct sched_entity *curr = cfs_rq->curr; + + /* + * Since we got here without doing put_prev_entity() we also + * have to consider cfs_rq->curr. If it is still a runnable + * entity, update_curr() will update its vruntime, otherwise + * forget we've ever seen it. + */ + if (curr && curr->on_rq) + update_curr(cfs_rq); + else + curr = NULL; + + /* + * This call to check_cfs_rq_runtime() will do the throttle and
Quoted 8 lines
Quoted 5 lines
kernel/sched/fair.c static void check_preempt_wakeup(struct · line 4724
Quoted 5 lines
kernel/sched/fair.c +5
-0+* dequeue its entity in the parent(s). Therefore the 'simple' +* nr_running test will indeed be correct. +*/ +if (unlikely (check_cfs_rq_runtime (cfs_rq))) + goto simple;... here if you read the comment above, we could have modified the
nr_running.
ok, i missed this point
Quoted 45 lines
Quoted 41 lines
Quoted 41 lines
kernel/sched/fair.c +39
-0+ se =pick_next_entity (cfs_rq, curr); + cfs_rq =group_cfs_rq (se); + } while (cfs_rq); + + p =task_of (se); + +/* +* Since we haven't yet done put_prev_entity and if the selected task +* is a different task than we started out with, try and touch the +* least amount of cfs_rqs. +*/ +if (prev != p) { +struct sched_entity *pse = &prev->se; + +while (!(cfs_rq =is_same_group (se, pse))) { +int se_depth = se->depth; +int pse_depth = pse->depth; + +if (se_depth <= pse_depth) { +put_prev_entity (cfs_rq_of (pse), pse); + pse =parent_entity (pse); + } +if (se_depth >= pse_depth) { +set_next_entity (cfs_rq_of (se), se); + se =parent_entity (se); + } + } + +put_prev_entity (cfs_rq, pse); +set_next_entity (cfs_rq, se); + } + +if (hrtick_enabled (rq)) +hrtick_start_fair (rq, p); + +return p; +simple: + cfs_rq = &rq->cfs; +#endif Quoted 2 lines
kernel/sched/fair.c static void check_preempt_wakeup(struct · line 4767
Quoted 2 lines
kernel/sched/fair.c +0
-0if (!cfs_rq->nr_running)return NULL ;And therefore this test needs to stay.
Peter Zijlstra
maintainerPATCH 8/9 sched: Clean up idle task SMP logic
In reply to Peter ZijlstraThe idle post_schedule hook is just a vile waste of time, furthermore it appears unneeded, move the idle_enter_fair() call into pick_next_task_idle().
--- kernel/sched/idle_task.c | 9 +-------- 1 file changed, 1 insertion(+), 8 deletions(-)
kernel/sched/idle_task.c +1 -8
@@ -19,11 +19,6 @@ static void pre_schedule_idle(struct rqidle_exit_fair (rq); rq_last_tick_reset(rq); } - -static void post_schedule_idle (struct rq *rq) -{ -idle_enter_fair (rq); -}#endif /* CONFIG_SMP */ /* * Idle tasks are unconditionally rescheduled:
@@ -40,8 +35,7 @@ pick_next_task_idle(struct rq *rq, strucschedstat_inc (rq, sched_goidle);#ifdef CONFIG_SMP -/* Trigger the post schedule to do an idle_enter for CFS */ - rq->post_schedule =1 ; +idle_enter_fair (rq);#endif return rq->idle; }
@@ -105,7 +99,6 @@ const struct sched_class idle_sched_clas#ifdef CONFIG_SMP .select_task_rq = select_task_rq_idle, .pre_schedule = pre_schedule_idle, - .post_schedule = post_schedule_idle, #endif .set_curr_task = set_curr_task_idle,
Re: [PATCH 8/9] sched: Clean up idle task SMP logic
Hi Peter,
Vincent
Quoted 48 lines · Peter Zijlstra
The idle
post_schedulehook is just a vile waste of time, furthermore it appears unneeded, move theidle_enter_fair()call intopick_next_task_idle().Cc Daniel Lezcano <[email protected]>Cc Vincent Guittot <[email protected]>Cc Steven Rostedt <[email protected]>Signed-off-by Peter Zijlstra <[email protected]>--- kernel/sched/idle_task.c | 9 +-------- 1 file changed, 1 insertion(+), 8 deletions(-)kernel/sched/idle_task.c +1
-8@@ -19,11 +19,6 @@ static void pre_schedule_idle(struct rqidle_exit_fair (rq); rq_last_tick_reset(rq); } - -static void post_schedule_idle (struct rq *rq) -{ -idle_enter_fair (rq); -}#endif /* CONFIG_SMP */ /* * Idle tasks are unconditionally rescheduled: @@ -40,8 +35,7 @@ pick_next_task_idle(struct rq *rq, strucschedstat_inc (rq, sched_goidle);#ifdef CONFIG_SMP -/* Trigger the post schedule to do an idle_enter for CFS */ - rq->post_schedule =1 ; +idle_enter_fair (rq);#endif return rq->idle; }@@ -105,7 +99,6 @@ const struct sched_class idle_sched_clas#ifdef CONFIG_SMP .select_task_rq = select_task_rq_idle, .pre_schedule = pre_schedule_idle, - .post_schedule = post_schedule_idle, #endif .set_curr_task = set_curr_task_idle,
Peter Zijlstra
maintainerPATCH 9/9 sched: Push down pre_schedule() and idle_balance()
In reply to Peter ZijlstraThis patch both merged idle_balance() and pre_schedule() and pushes both of them into pick_next_task().
Conceptually pre_schedule() and idle_balance() are rather similar, both are used to pull more work onto the current CPU.
We cannot however first move idle_balance() into pre_schedule_fair() since there is no guarantee the last runnable task is a fair task, and thus we would miss newidle balances.
Similarly, the dl and rt pre_schedule calls must be ran before idle_balance() since their respective tasks have higher priority and it would not do to delay their execution searching for less important tasks first.
However, by noticing that pick_next_tasks() already traverses the sched_class hierarchy in the right order, we can get the right behaviour and do away with both calls.
We must however change the special case optimization to also require that prev is of sched_class_fair, otherwise we can miss doing a dl or rt pull where we needed one.
--- kernel/sched/core.c | 26 ++------------------------ kernel/sched/deadline.c | 15 +++++++-------- kernel/sched/fair.c | 24 ++++++++++++++++++++---- kernel/sched/idle_task.c | 12 +++++------- kernel/sched/rt.c | 16 ++++++++-------- kernel/sched/sched.h | 1 - 6 files changed, 42 insertions(+), 52 deletions(-)
kernel/sched/core.c +2 -24
@@ -2146,13 +2146,6 @@ static void finish_task_switch(struct rq#ifdef CONFIG_SMP -/* assumes rq->lock is held */ -static inline void pre_schedule (struct rq *rq,struct task_struct *prev) -{ -if (prev->sched_class->pre_schedule) - prev->sched_class->pre_schedule (rq, prev); -} -/* rq->lock is NOT held, but preemption is disabled */ static inline void post_schedule (struct rq *rq) {
@@ -2170,10 +2163,6 @@ static inline void post_schedule(struct#else -static inline void pre_schedule (struct rq *rq,struct task_struct *p) -{ -} -static inline void post_schedule (struct rq *rq) { }
@@ -2569,7 +2558,8 @@ pick_next_task(struct rq *rq, struct tas* Optimization: we know that if all tasks are in * the fair class we can call that function directly: */ -if (likely (rq->nr_running == rq->cfs.h_nr_running)) { +if (likely (prev->sched_class == &fair_sched_class && + rq->nr_running == rq->cfs.h_nr_running)) { p = fair_sched_class.pick_next_task (rq, prev);if (likely (p))return p;
@@ -2672,18 +2662,6 @@ static void __sched __schedule(void) switch_count = &prev->nvcsw; } -pre_schedule (rq, prev); - -if (unlikely (!rq->nr_running)) { -/* -* We must set idle_stamp _before_ calling idle_balance(), such -* that we measure the duration of idle_balance() as idle time. -*/ - rq->idle_stamp =rq_clock (rq); -if (idle_balance (rq)) - rq->idle_stamp =0 ; - } -if (prev->on_rq || rq->skip_clock_update <0 )update_rq_clock (rq);
kernel/sched/deadline.c +7 -8
@@ -989,6 +989,8 @@ static struct sched_dl_entity *pick_next return rb_entry(left, struct sched_dl_entity, rb_node); } +static int pull_dl_task (struct rq *this_rq); +struct task_struct *pick_next_task_dl (struct rq *rq,struct task_struct *prev) {struct sched_dl_entity *dl_se;
@@ -997,6 +999,11 @@ struct task_struct *pick_next_task_dl(st dl_rq = &rq->dl; +#ifdef CONFIG_SMP +if (dl_task (prev)) +pull_dl_task (rq); +#endif +if (unlikely (!dl_rq->dl_nr_running))return NULL ;
@@ -1427,13 +1434,6 @@ static int pull_dl_task(struct rq *this_return ret; } -static void pre_schedule_dl (struct rq *rq,struct task_struct *prev) -{ -/* Try to pull other tasks here */ -if (dl_task (prev)) -pull_dl_task (rq); -} -static void post_schedule_dl (struct rq *rq) {push_dl_tasks (rq);
@@ -1626,7 +1626,6 @@ const struct sched_class dl_sched_class .set_cpus_allowed = set_cpus_allowed_dl, .rq_online = rq_online_dl, .rq_offline = rq_offline_dl, - .pre_schedule = pre_schedule_dl, .post_schedule = post_schedule_dl, .task_woken = task_woken_dl,#endif
kernel/sched/fair.c +20 -4
@@ -2581,7 +2581,8 @@ void idle_exit_fair(struct rq *this_rq) update_rq_runnable_avg(this_rq, 0); } -#else +#else /* CONFIG_SMP */ +static inline void update_entity_load_avg (struct sched_entity *se,int update_cfs_rq) {}static inline void update_rq_runnable_avg (struct rq *rq,int runnable) {}
@@ -2593,7 +2594,7 @@ static inline void dequeue_entity_load_a int sleep) {}static inline void update_cfs_rq_blocked_load (struct cfs_rq *cfs_rq,int force_update) {} -#endif +#endif /* CONFIG_SMP */ static void enqueue_sleeper (struct cfs_rq *cfs_rq,struct sched_entity *se) {
@@ -4686,9 +4687,10 @@ pick_next_task_fair(struct rq *rq, strucstruct sched_entity *se;struct task_struct *p; +again:#ifdef CONFIG_FAIR_GROUP_SCHED if (!cfs_rq->nr_running) -return NULL ; + goto idle;if (prev->sched_class != &fair_sched_class) goto simple;
@@ -4764,7 +4766,7 @@ pick_next_task_fair(struct rq *rq, struc#endif if (!cfs_rq->nr_running) -return NULL ; + goto idle; prev->sched_class->put_prev_task (rq, prev);
@@ -4780,6 +4782,20 @@ pick_next_task_fair(struct rq *rq, struchrtick_start_fair (rq, p);return p; + +idle: +idle_exit_fair (rq); +/* +* We must set idle_stamp _before_ calling idle_balance(), such that we +* measure the duration of idle_balance() as idle time. +*/ + rq->idle_stamp =rq_clock (rq); +if (idle_balance (rq)) {/* drops rq->lock */ + rq->idle_stamp =0 ; + goto again; + } + +return NULL ; }/*
kernel/sched/idle_task.c +5 -7
@@ -13,13 +13,8 @@ select_task_rq_idle(struct task_struct * {return task_cpu (p);/* IDLE tasks as never migrated */ } - -static void pre_schedule_idle (struct rq *rq,struct task_struct *prev) -{ -idle_exit_fair (rq); -rq_last_tick_reset (rq); -}#endif /* CONFIG_SMP */ +/* * Idle tasks are unconditionally rescheduled: */
@@ -55,6 +50,10 @@ dequeue_task_idle(struct rq *rq, structstatic void put_prev_task_idle (struct rq *rq,struct task_struct *prev) { +#ifdef CONFIG_SMP +idle_exit_fair (rq); +rq_last_tick_reset (rq); +#endif }static void task_tick_idle (struct rq *rq,struct task_struct *curr,int queued)
@@ -98,7 +97,6 @@ const struct sched_class idle_sched_clas#ifdef CONFIG_SMP .select_task_rq = select_task_rq_idle, - .pre_schedule = pre_schedule_idle, #endif .set_curr_task = set_curr_task_idle,
kernel/sched/rt.c +8 -8
@@ -1324,12 +1324,20 @@ static struct task_struct *_pick_next_tareturn p; } +static int pull_rt_task (struct rq *this_rq); +static struct task_struct *pick_next_task_rt (struct rq *rq,struct task_struct *prev) {struct task_struct *p;struct rt_rq *rt_rq = &rq->rt; +#ifdef CONFIG_SMP +/* Try to pull RT tasks here if we lower this rq's prio */ +if (rq->rt.highest_prio.curr > prev->prio) +pull_rt_task (rq); +#endif +if (!rt_rq->rt_nr_running)return NULL ;
@@ -1720,13 +1728,6 @@ static int pull_rt_task(struct rq *this_return ret; } -static void pre_schedule_rt (struct rq *rq,struct task_struct *prev) -{ -/* Try to pull RT tasks here if we lower this rq's prio */ -if (rq->rt.highest_prio.curr > prev->prio) -pull_rt_task (rq); -} -static void post_schedule_rt (struct rq *rq) {push_rt_tasks (rq);
@@ -2003,7 +2004,6 @@ const struct sched_class rt_sched_class .set_cpus_allowed = set_cpus_allowed_rt, .rq_online = rq_online_rt, .rq_offline = rq_offline_rt, - .pre_schedule = pre_schedule_rt, .post_schedule = post_schedule_rt, .task_woken = task_woken_rt, .switched_from = switched_from_rt,
kernel/sched/sched.h +0 -1
@@ -1136,7 +1136,6 @@ struct sched_class {int (*select_task_rq)(struct task_struct *p,int task_cpu,int sd_flag,int flags);void (*migrate_task_rq)(struct task_struct *p,int next_cpu); -void (*pre_schedule) (struct rq *this_rq,struct task_struct *task);void (*post_schedule) (struct rq *this_rq);void (*task_waking) (struct task_struct *task);void (*task_woken) (struct rq *this_rq,struct task_struct *task);
Vincent Guittot
maintainerRe: [PATCH 9/9] sched: Push down pre_schedule() and idle_balance()
Quoted 177 lines · Peter Zijlstra
This patch both merged
idle_balance()andpre_schedule()and pushes both of them intopick_next_task().Conceptually
pre_schedule()andidle_balance()are rather similar, both are used to pull more work onto the current CPU.We cannot however first move
idle_balance()intopre_schedule_fair()since there is no guarantee the last runnable task is a fair task, and thus we would miss newidle balances.Similarly, the dl and rt
pre_schedulecalls must be ran beforeidle_balance()since their respective tasks have higher priority and it would not do to delay their execution searching for less important tasks first.However, by noticing that
pick_next_tasks()already traverses thesched_classhierarchy in the right order, we can get the right behaviour and do away with both calls.We must however change the special case optimization to also require that prev is of
sched_class_fair, otherwise we can miss doing a dl or rt pull where we needed one.Signed-off-by Peter Zijlstra <[email protected]>--- kernel/sched/core.c | 26 ++------------------------ kernel/sched/deadline.c | 15 +++++++-------- kernel/sched/fair.c | 24 ++++++++++++++++++++---- kernel/sched/idle_task.c | 12 +++++------- kernel/sched/rt.c | 16 ++++++++-------- kernel/sched/sched.h | 1 - 6 files changed, 42 insertions(+), 52 deletions(-)kernel/sched/core.c +2
-24@@ -2146,13 +2146,6 @@ static void finish_task_switch(struct rq#ifdef CONFIG_SMP -/* assumes rq->lock is held */ -static inline void pre_schedule (struct rq *rq,struct task_struct *prev) -{ -if (prev->sched_class->pre_schedule) - prev->sched_class->pre_schedule (rq, prev); -} -/* rq->lock is NOT held, but preemption is disabled */ static inline void post_schedule (struct rq *rq) {@@ -2170,10 +2163,6 @@ static inline void post_schedule(struct#else -static inline void pre_schedule (struct rq *rq,struct task_struct *p) -{ -} -static inline void post_schedule (struct rq *rq) { }@@ -2569,7 +2558,8 @@ pick_next_task(struct rq *rq, struct tas* Optimization: we know that if all tasks are in * the fair class we can call that function directly: */ -if (likely (rq->nr_running == rq->cfs.h_nr_running)) { +if (likely (prev->sched_class == &fair_sched_class && + rq->nr_running == rq->cfs.h_nr_running)) { p = fair_sched_class.pick_next_task (rq, prev);if (likely (p))return p;@@ -2672,18 +2662,6 @@ static void __sched __schedule(void) switch_count = &prev->nvcsw; } -pre_schedule (rq, prev); - -if (unlikely (!rq->nr_running)) { -/* -* We must set idle_stamp _before_ calling idle_balance(), such -* that we measure the duration of idle_balance() as idle time. -*/ - rq->idle_stamp =rq_clock (rq); -if (idle_balance (rq)) - rq->idle_stamp =0 ; - } -if (prev->on_rq || rq->skip_clock_update <0 )update_rq_clock (rq);kernel/sched/deadline.c +7
-8@@ -989,6 +989,8 @@ static struct sched_dl_entity *pick_next return rb_entry(left, struct sched_dl_entity, rb_node); } +static int pull_dl_task (struct rq *this_rq); +struct task_struct *pick_next_task_dl (struct rq *rq,struct task_struct *prev) {struct sched_dl_entity *dl_se;@@ -997,6 +999,11 @@ struct task_struct *pick_next_task_dl(st dl_rq = &rq->dl; +#ifdef CONFIG_SMP +if (dl_task (prev)) +pull_dl_task (rq); +#endif +if (unlikely (!dl_rq->dl_nr_running))return NULL ;@@ -1427,13 +1434,6 @@ static int pull_dl_task(struct rq *this_return ret; } -static void pre_schedule_dl (struct rq *rq,struct task_struct *prev) -{ -/* Try to pull other tasks here */ -if (dl_task (prev)) -pull_dl_task (rq); -} -static void post_schedule_dl (struct rq *rq) {push_dl_tasks (rq);@@ -1626,7 +1626,6 @@ const struct sched_class dl_sched_class .set_cpus_allowed = set_cpus_allowed_dl, .rq_online = rq_online_dl, .rq_offline = rq_offline_dl, - .pre_schedule = pre_schedule_dl, .post_schedule = post_schedule_dl, .task_woken = task_woken_dl,#endif kernel/sched/fair.c +6
-4@@ -2581,7 +2581,8 @@ void idle_exit_fair(struct rq *this_rq) update_rq_runnable_avg(this_rq, 0); } -#else +#else /* CONFIG_SMP */ +static inline void update_entity_load_avg (struct sched_entity *se,int update_cfs_rq) {}static inline void update_rq_runnable_avg (struct rq *rq,int runnable) {}@@ -2593,7 +2594,7 @@ static inline void dequeue_entity_load_a int sleep) {}static inline void update_cfs_rq_blocked_load (struct cfs_rq *cfs_rq,int force_update) {} -#endif +#endif /* CONFIG_SMP */ static void enqueue_sleeper (struct cfs_rq *cfs_rq,struct sched_entity *se) {@@ -4686,9 +4687,10 @@ pick_next_task_fair(struct rq *rq, strucstruct sched_entity *se;struct task_struct *p; +again:#ifdef CONFIG_FAIR_GROUP_SCHED if (!cfs_rq->nr_running) -return NULL ; + goto idle;if (prev->sched_class != &fair_sched_class) goto simple;@@ -4764,7 +4766,7 @@ pick_next_task_fair(struct rq *rq, struc#endif if (!cfs_rq->nr_running) -return NULL ; + goto idle; prev->sched_class->put_prev_task (rq, prev);
kernel/sched/fair.c pick_next_task_fair(struct rq *rq, struc · line 4787
Quoted 6 lines
kernel/sched/fair.c +3
-0@@ -4780,6 +4782,20 @@ pick_next_task_fair(struct rq *rq, struchrtick_start_fair (rq, p);return p; + +idle: +idle_exit_fair (rq);
It should be idle_enter_fair.
we want to update the statistic with the running time of other classes than CFS.
The use case is:
exit idleput_prev_task_idle
--> idle_exit_fair (account elapsed idle time) pick_next_task other than fair tasks
switch between "other than fair" tasks
...
no more "other than fair" tasks to schedule pick_next_task_fair
--> no fair task on the rq
--> jump to simple
--> idle_enter_fair (account elapsed running time of other class before trying to pull fair task from other CPUs)
--> idle_balance()
...
Vincent
Quoted 107 lines
kernel/sched/fair.c +11
-0+/* +* We must set idle_stamp _before_ calling idle_balance(), such that we +* measure the duration of idle_balance() as idle time. +*/ + rq->idle_stamp =rq_clock (rq); +if (idle_balance (rq)) {/* drops rq->lock */ + rq->idle_stamp =0 ; + goto again; + } + +return NULL ; }/* kernel/sched/idle_task.c +5
-7@@ -13,13 +13,8 @@ select_task_rq_idle(struct task_struct * {return task_cpu (p);/* IDLE tasks as never migrated */ } - -static void pre_schedule_idle (struct rq *rq,struct task_struct *prev) -{ -idle_exit_fair (rq); -rq_last_tick_reset (rq); -}#endif /* CONFIG_SMP */ +/* * Idle tasks are unconditionally rescheduled: */ @@ -55,6 +50,10 @@ dequeue_task_idle(struct rq *rq, structstatic void put_prev_task_idle (struct rq *rq,struct task_struct *prev) { +#ifdef CONFIG_SMP +idle_exit_fair (rq); +rq_last_tick_reset (rq); +#endif }static void task_tick_idle (struct rq *rq,struct task_struct *curr,int queued)@@ -98,7 +97,6 @@ const struct sched_class idle_sched_clas#ifdef CONFIG_SMP .select_task_rq = select_task_rq_idle, - .pre_schedule = pre_schedule_idle, #endif .set_curr_task = set_curr_task_idle,kernel/sched/rt.c +8
-8@@ -1324,12 +1324,20 @@ static struct task_struct *_pick_next_tareturn p; } +static int pull_rt_task (struct rq *this_rq); +static struct task_struct *pick_next_task_rt (struct rq *rq,struct task_struct *prev) {struct task_struct *p;struct rt_rq *rt_rq = &rq->rt; +#ifdef CONFIG_SMP +/* Try to pull RT tasks here if we lower this rq's prio */ +if (rq->rt.highest_prio.curr > prev->prio) +pull_rt_task (rq); +#endif +if (!rt_rq->rt_nr_running)return NULL ;@@ -1720,13 +1728,6 @@ static int pull_rt_task(struct rq *this_return ret; } -static void pre_schedule_rt (struct rq *rq,struct task_struct *prev) -{ -/* Try to pull RT tasks here if we lower this rq's prio */ -if (rq->rt.highest_prio.curr > prev->prio) -pull_rt_task (rq); -} -static void post_schedule_rt (struct rq *rq) {push_rt_tasks (rq);@@ -2003,7 +2004,6 @@ const struct sched_class rt_sched_class .set_cpus_allowed = set_cpus_allowed_rt, .rq_online = rq_online_rt, .rq_offline = rq_offline_rt, - .pre_schedule = pre_schedule_rt, .post_schedule = post_schedule_rt, .task_woken = task_woken_rt, .switched_from = switched_from_rt,kernel/sched/sched.h +0
-1@@ -1136,7 +1136,6 @@ struct sched_class {int (*select_task_rq)(struct task_struct *p,int task_cpu,int sd_flag,int flags);void (*migrate_task_rq)(struct task_struct *p,int next_cpu); -void (*pre_schedule) (struct rq *this_rq,struct task_struct *task);void (*post_schedule) (struct rq *this_rq);void (*task_waking) (struct task_struct *task);void (*task_woken) (struct rq *this_rq,struct task_struct *task);
Peter Zijlstra
maintainerRe: [PATCH 9/9] sched: Push down pre_schedule() and idle_balance()
Quoted 11 lines · Vincent Guittot
kernel/sched/fair.c pick_next_task_fair(struct rq *rq, struc · line 4787
Quoted 2 lines · Peter Zijlstra
kernel/sched/fair.c +2
-0+idle: +idle_exit_fair (rq);It should be
idle_enter_fair.we want to update the statistic with the running time of other classes than CFS.
The use case is:
Quoted 14 lines
exit idle
put_prev_task_idle
-->idle_exit_fair(account elapsed idle time)pick_next_taskother than fair tasks
switch between "other than fair" tasks
...
no more "other than fair" tasks to schedulepick_next_task_fair
--> no fair task on the rq
--> jump to simple
-->idle_enter_fair(account elapsed running time of other class before trying to pull fair task from other CPUs)
-->idle_balance()
...
Right.. terminal confusion on this topic it seems. Fixed it up.
Steven Rostedt
reviewerQuoted 9 lines · On Tue, 28 Jan 2014 18:16:34 +0100 Peter Zijlstra <[email protected]> wrote:
Here's a set that seems to work properly and hopefully adresses all previously raised issues.
Daniel, I'm sorry, the
idle_stampthing wandered back over tofair.c:-)I did test the fair bits, including bandwidth (although not very extensively).
I did not test the dl/rt bits, Steve do you have a testcase for that?
My sched tests are usually done by running some scheduling tests while recording sched switches and then analyzing it under kernelshark. I don't have many other tests that do pass fail. Hmm, I did have a couple of rt migration tests, but that's it.
I'll take a look at theses tomorrow.
-- Steve