Various sched patches
Peter Zijlstra
maintainercover Various sched patches
Hi,
A set of recent patches by Daniel reminded me of a series I did a while back. So here's a combined set.
Paul, Ben, could you guys have a careful look at the one optimizing pick_next_task_fair() (patch 8)? That patch is somewhat big and scary, although it does appear to do what it says.
I've not yet tested the bandwidth aspect at all.
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 | 2 +- kernel/sched/fair.c | 14 ++++++-------- kernel/sched/sched.h | 2 +- 3 files changed, 8 insertions(+), 10 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 (rq); + rq->idle_stamp =idle_balance (rq) ?0 :rq_clock (rq);put_prev_task (rq, prev); next =pick_next_task (rq);
kernel/sched/fair.c +6 -8
@@ -6359,7 +6359,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 ;
@@ -6367,10 +6367,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.
@@ -6408,10 +6406,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 ();
@@ -6422,7 +6418,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)) {/*
@@ -6434,6 +6430,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
maintainerRe: [PATCH 3/9] sched: Move idle_stamp up to the core
Quoted 24 lines · Peter Zijlstra
From: Daniel Lezcano <[email protected]>
The
idle_balancemodifies theidle_stampfield of the rq, making this information to be shared acrosscore.candfair.c. As we can know if the cpu is going to idle or not with the previous patch, let's encapsulate theidle_stampinformation incore.cby moving it up to the caller. Theidle_balancefunction 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.Signed-off-by Daniel Lezcano <[email protected]>Signed-off-by Peter Zijlstra <[email protected]>--- kernel/sched/core.c | 2 +- kernel/sched/fair.c | 14 ++++++-------- kernel/sched/sched.h | 2 +- 3 files changed, 8 insertions(+), 10 deletions(-)
kernel/sched/core.c static void __sched __schedule(void) · line 2683
Quoted 5 lines
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 (rq); + rq->idle_stamp =idle_balance (rq) ?0 :rq_clock (rq);
OK, spotted a problem here..
So previously idle_stamp was set _before_ actually doing idle_balance(), and that was RIGHT, because that way we include the cost of actually doing idle_balance() into the idle time.
By not including the cost of idle_balance() you underestimate the 'idle' time in that if idle_balance() filled the entire idle time we account 0 idle, even though we had 'plenty' of time to run the entire thing.
This leads to not running idle_balance() even though we have the time for it.
So we very much want something like:
if (!rq->nr_running) rq->idle_stamp = rq_clock(rq); p = pick_next_task(rq, prev); if (!is_idle_task(p)) rq->idle_stamp = 0;
Re: [PATCH 3/9] sched: Move idle_stamp up to the core
Quoted 37 lines · Peter Zijlstra
Quoted 24 lines · Peter Zijlstra
From: Daniel Lezcano <[email protected]>
The
idle_balancemodifies theidle_stampfield of the rq, making this information to be shared acrosscore.candfair.c. As we can know if the cpu is going to idle or not with the previous patch, let's encapsulate theidle_stampinformation incore.cby moving it up to the caller. Theidle_balancefunction 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.Signed-off-by Daniel Lezcano <[email protected]>Signed-off-by Peter Zijlstra <[email protected]>--- kernel/sched/core.c | 2 +- kernel/sched/fair.c | 14 ++++++-------- kernel/sched/sched.h | 2 +- 3 files changed, 8 insertions(+), 10 deletions(-)kernel/sched/core.c static void __sched __schedule(void) · line 2683
Quoted 5 lines
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 (rq); + rq->idle_stamp =idle_balance (rq) ?0 :rq_clock (rq);OK, spotted a problem here..
So previously
idle_stampwas set _before_ actually doingidle_balance(), and that was RIGHT, because that way we include the cost of actually doingidle_balance()into the idle time.
Quoted 6 lines
By not including the cost of
idle_balance()you underestimate the 'idle' time in that ifidle_balance()filled the entire idle time we account 0 idle, even though we had 'plenty' of time to run the entire thing.This leads to not running
idle_balance()even though we have the time for it.
Good catch. How did you notice that ?
Quoted 10 lines
So we very much want something like:
if (!rq->nr_running) rq->idle_stamp = rq_clock(rq); p = pick_next_task(rq, prev); if (!is_idle_task(p)) rq->idle_stamp = 0;
Is this code assuming idle_balance() is in pick_next_task ?
For this specific patch 3/9, will be ok the following ?
+ if (unlikely(!rq->nr_running)) {
+ rq->idle_stamp = rq_clock(rq);
+ if (idle_balance(rq))
+ rq->idle_stamp = 0;
+ }
So the patch 9/9 is wrong also because it does not fill idle_stamp before idle_balance, the fix would be.
kernel/sched/core.c | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-)
kernel/sched/core.c +5 -3
@@ -2579,15 +2579,17 @@ again: } } + rq->idle_stamp =rq_clock (rq); +/* * If there is a task balanced on this cpu, pick the next task, * otherwise fall in the optimization by picking the idle task * directly. */ -if (idle_balance (rq)) +if (idle_balance (rq)) { + rq->idle_stamp =0 ; goto again; - - rq->idle_stamp =rq_clock (rq); + }return idle_sched_class.pick_next_task (rq, prev); }
Quoted 6 lines
--
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 · 5 lines
<http://www.linaro.org/> Linaro.org │ Open source software for ARM SoCs Follow Linaro: <http://www.facebook.com/pages/Linaro> Facebook | <http://twitter.com/#!/linaroorg> Twitter | <http://www.linaro.org/linaro-blog/> Blog
Peter Zijlstra
maintainerRe: [PATCH 3/9] sched: Move idle_stamp up to the core
Quoted 38 lines · Daniel Lezcano
Quoted 37 lines · Peter Zijlstra
Quoted 24 lines · Peter Zijlstra
From: Daniel Lezcano <[email protected]>
The
idle_balancemodifies theidle_stampfield of the rq, making this information to be shared acrosscore.candfair.c. As we can know if the cpu is going to idle or not with the previous patch, let's encapsulate theidle_stampinformation incore.cby moving it up to the caller. Theidle_balancefunction 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.Signed-off-by Daniel Lezcano <[email protected]>Signed-off-by Peter Zijlstra <[email protected]>--- kernel/sched/core.c | 2 +- kernel/sched/fair.c | 14 ++++++-------- kernel/sched/sched.h | 2 +- 3 files changed, 8 insertions(+), 10 deletions(-)kernel/sched/core.c static void __sched __schedule(void) · line 2683
Quoted 5 lines
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 (rq); + rq->idle_stamp =idle_balance (rq) ?0 :rq_clock (rq);OK, spotted a problem here..
So previously
idle_stampwas set _before_ actually doingidle_balance(), and that was RIGHT, because that way we include the cost of actually doingidle_balance()into the idle time.
Quoted 8 lines
Quoted 6 lines
By not including the cost of
idle_balance()you underestimate the 'idle' time in that ifidle_balance()filled the entire idle time we account 0 idle, even though we had 'plenty' of time to run the entire thing.This leads to not running
idle_balance()even though we have the time for it.Good catch. How did you notice that ?
Staring at that code for too long :-)
Quoted 6 lines
Quoted 6 lines
So we very much want something like:
if (!rq->nr_running) rq->idle_stamp = rq_clock(rq);
Quoted 6 lines
Quoted 4 lines
p = pick_next_task(rq, prev); if (!is_idle_task(p)) rq->idle_stamp = 0;Is this code assuming
idle_balance()is inpick_next_task?
Yeah, I'm trying to make that work.
Peter Zijlstra
maintainerPATCH 4/9 sched: Clean up idle task SMP logic
In reply to Peter ZijlstraThe idle post_schedule hook is just a vile waste of time, fix it proper.
--- kernel/sched/fair.c | 5 +++-- kernel/sched/idle_task.c | 21 ++++++--------------- 2 files changed, 9 insertions(+), 17 deletions(-)
kernel/sched/fair.c +3 -2
@@ -2416,7 +2416,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) {}
@@ -2428,7 +2429,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) {
kernel/sched/idle_task.c +6 -15
@@ -13,18 +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); -} - -static void post_schedule_idle (struct rq *rq) -{ -idle_enter_fair (rq); -}#endif /* CONFIG_SMP */ +/* * Idle tasks are unconditionally rescheduled: */
@@ -37,8 +27,7 @@ static struct task_struct *pick_next_tas {schedstat_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; }
@@ -58,6 +47,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)
@@ -101,8 +94,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,
Vincent Guittot
maintainerRe: [PATCH 4/9] sched: Clean up idle task SMP logic
Quoted 57 lines · Peter Zijlstra
The idle
post_schedulehook is just a vile waste of time, fix it proper.Cc Vincent Guittot <[email protected]>Tested-by Daniel Lezcano <[email protected]>Signed-off-by Peter Zijlstra <[email protected]>--- kernel/sched/fair.c | 5 +++-- kernel/sched/idle_task.c | 21 ++++++--------------- 2 files changed, 9 insertions(+), 17 deletions(-)kernel/sched/fair.c +3
-2@@ -2416,7 +2416,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) {}@@ -2428,7 +2429,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) {kernel/sched/idle_task.c +1
-11@@ -13,18 +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); -} - -static void post_schedule_idle (struct rq *rq) -{ -idle_enter_fair (rq); -}#endif /* CONFIG_SMP */ +/* * Idle tasks are unconditionally rescheduled: */
kernel/sched/idle_task.c static struct task_struct *pick_next_tas · line 30
Quoted 6 lines
kernel/sched/idle_task.c +1
-2@@ -37,8 +27,7 @@ static struct task_struct *pick_next_tas {schedstat_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);
If i have correctly followed the new function path that is introduced by the patchset, idle_enter_fair is called after idle_balance whereas it must be called before in order to update the runnable_avg_sum/period of the rq before evaluating the interest of pulling cfs task
Regards,
vincent
Quoted 25 lines
kernel/sched/idle_task.c +4
-2#endif return rq->idle; }@@ -58,6 +47,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)@@ -101,8 +94,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
maintainerRe: [PATCH 4/9] sched: Clean up idle task SMP logic
Quoted 7 lines · Vincent Guittot
On 21 January 2014 12:17, Peter Zijlstra <[email protected]> wrote:
If i have correctly followed the new function path that is introduced by the patchset,
idle_enter_fairis called afteridle_balancewhereas it must be called before in order to update the runnable_avg_sum/period of the rq before evaluating the interest of pulling cfs task
Its idle_exit_fair, that's moved from pre_schedule to put_prev_task and thus indeed has crossed idle_balance.
Yeah, I can leave that pre_schedule thing in place, however all that has be thinking.
Ideally we'd do something like the below; but I must admit to still being slightly confused about the idle_{enter,exit}_fair() calls, their comment doesn't seem to clarify things.
Steve, I don't think I wrecked rt/deadline by pulling in the pre_schedule call into pick_next_task(), but then, who knows :-)
The only thing I really don't like is having that double conditional for the direct fair_sched_class call, but I didn't see a way around that, other than dropping that entirely. Then again, we cut out a conditional and indirect call by getting rid of pre_schedule() -- so it might just balance out.
---
kernel/sched/core.c +2 -22
@@ -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) { }
@@ -2571,7 +2560,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))return fair_sched_class.pick_next_task (rq, prev);for_each_class (class) {
@@ -2581,14 +2571,6 @@ pick_next_task(struct rq *rq, struct tas } } -/* -* If there is a task balanced on this cpu, pick the next task, -* otherwise fall in the optimization by picking the idle task -* directly. -*/ -if (idle_balance (rq)) - goto again; - rq->idle_stamp =rq_clock (rq);return idle_sched_class.pick_next_task (rq, prev);
@@ -2682,8 +2664,6 @@ static void __sched __schedule(void) switch_count = &prev->nvcsw; } -pre_schedule (rq, prev); -if (prev->on_rq || rq->skip_clock_update <0 )update_rq_clock (rq);
kernel/sched/deadline.c +3 -3
@@ -997,6 +997,9 @@ struct task_struct *pick_next_task_dl(st dl_rq = &rq->dl; +if (dl_task (prev)) +pull_dl_task (rq); +if (unlikely (!dl_rq->dl_nr_running))return NULL ;
@@ -1430,8 +1433,6 @@ static int pull_dl_task(struct rq *this_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)
@@ -1626,7 +1627,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 +15 -7
@@ -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) {
@@ -4700,10 +4701,11 @@ 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; -#ifdef CONFIG_FAIR_GROUP_SCHED if (prev->sched_class != &fair_sched_class) goto simple;
@@ -4769,11 +4771,10 @@ pick_next_task_fair(struct rq *rq, strucreturn p; simple: -#endif cfs_rq = &rq->cfs; - +#endif if (!cfs_rq->nr_running) -return NULL ; + goto idle; prev->sched_class->put_prev_task (rq, prev);
@@ -4789,6 +4790,13 @@ pick_next_task_fair(struct rq *rq, struchrtick_start_fair (rq, p);return p; + +idle: +idle_exit_fair (); +if (idle_balance ())/* drops rq->lock */ + goto again; + +return NULL ; }/*
kernel/sched/idle_task.c +6 -15
@@ -13,18 +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); -} - -static void post_schedule_idle (struct rq *rq) -{ -idle_enter_fair (rq); -}#endif /* CONFIG_SMP */ +/* * Idle tasks are unconditionally rescheduled: */
@@ -40,8 +30,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; }
@@ -61,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)
@@ -104,8 +97,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,
kernel/sched/rt.c +4 -8
@@ -1330,6 +1330,10 @@ pick_next_task_rt(struct rq *rq, structstruct task_struct *p;struct rt_rq *rt_rq = &rq->rt; +/* 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); +if (!rt_rq->rt_nr_running)return NULL ;
@@ -1720,13 +1724,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 +2000,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 4/9] sched: Clean up idle task SMP logic
Quoted 11 lines · Peter Zijlstra
Quoted 7 lines · Vincent Guittot
On 21 January 2014 12:17, Peter Zijlstra <[email protected]> wrote:
If i have correctly followed the new function path that is introduced by the patchset,
idle_enter_fairis called afteridle_balancewhereas it must be called before in order to update the runnable_avg_sum/period of the rq before evaluating the interest of pulling cfs taskIts
idle_exit_fair, that's moved frompre_scheduletoput_prev_taskand thus indeed has crossedidle_balance.
ok, so i probably mix the changes introduced by your patches and a potential issue that was already present before
idle_enter/exit_fair are used to be sure to account correctly the run time of a rq in its sched_avg field, so they must be called before entering/leaving idle. Your patch ensures that they will be called correctly. Now, the idle_balance is used to check the interest of pulling task on this newly idle CPU and it could use the sched_avg field in a near future regarding the discussion around a energy aware scheduler. as a result, we must update the sched_avg field before running the idle_balance (that's not the case even before your patches)
So one solution is probably to move idle_enter_fair into the idle_balance
Regards,
Vincent
Quoted 17 lines
Yeah, I can leave that
pre_schedulething in place, however all that has be thinking.Ideally we'd do something like the below; but I must admit to still being slightly confused about the idle_{enter,exit}_fair() calls, their comment doesn't seem to clarify things.
Steve, I don't think I wrecked rt/deadline by pulling in the
pre_schedulecall intopick_next_task(), but then, who knows :-)The only thing I really don't like is having that double conditional for the direct
fair_sched_classcall, but I didn't see a way around that, other than dropping that entirely. Then again, we cut out a conditional and indirect call by getting rid ofpre_schedule()-- so it might just balance out.
[snip]
Peter Zijlstra
maintainerPATCH 5/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 6/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 | 2 +- kernel/sched/fair.c | 6 +++++- kernel/sched/idle_task.c | 6 +++++- kernel/sched/rt.c | 27 ++++++++++++++++----------- kernel/sched/sched.h | 8 +++++++- kernel/sched/stop_task.c | 5 ++++- 7 files changed, 46 insertions(+), 29 deletions(-)
kernel/sched/core.c +8 -13
@@ -2554,18 +2554,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;
@@ -2575,13 +2568,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; }
@@ -2682,8 +2675,10 @@ static void __sched __schedule(void)if (unlikely (!rq->nr_running)) rq->idle_stamp =idle_balance (rq) ?0 :rq_clock (rq); -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 ;
@@ -4725,7 +4720,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 +1 -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;
kernel/sched/fair.c +5 -1
@@ -4484,7 +4484,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;
@@ -4493,6 +4494,9 @@ static struct task_struct *pick_next_tasif (!cfs_rq->nr_running)return NULL ; +if (prev) + 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 +5 -1
@@ -23,8 +23,12 @@ 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) { +if (prev) + prev->sched_class->put_prev_task (rq, prev); +schedstat_inc (rq, sched_goidle);#ifdef CONFIG_SMP idle_enter_fair (rq);
kernel/sched/rt.c +16 -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,22 @@ 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 ; + +if (prev) + 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 +4 -1
@@ -23,11 +23,14 @@ 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) { +if (prev) + prev->sched_class->put_prev_task (rq, prev); stop->se.exec_start =rq_clock_task (rq);return stop; }
[email protected]
reviewerRe: [PATCH 6/9] sched: Push put_prev_task() into pick_next_task()
Quoted 57 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/idle_task.c +5
-1@@ -23,8 +23,12 @@ 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) { +if (prev) + prev->sched_class->put_prev_task (rq, prev); +schedstat_inc (rq, sched_goidle);#ifdef CONFIG_SMP idle_enter_fair (rq);kernel/sched/rt.c +9
-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,22 @@ 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 ; +
kernel/sched/rt.c static struct task_struct *_pick_next_ta · line 1345
Quoted 10 lines
kernel/sched/rt.c +7
-0+if (rt_rq_throttled (rt_rq)) +return NULL ; + +if (prev) + prev->sched_class->put_prev_task (rq, prev); + + p =_pick_next_task_rt (rq);/* The running task is never eligible for pushing */ if (p)
p is now always non-NULL, so this branch can now go (and it is important that we can't fail after doing put).
Peter Zijlstra
maintainerPATCH 7/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 8/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.
XXX please review carefully; its quite horrid.
That said, simple hackbench runs in a 3 deep cgroup show a consistent performance increase (small, but consistent).
--- kernel/sched/fair.c | 140 +++++++++++++++++++++++++++++++++++++++++----------- 1 file changed, 111 insertions(+), 29 deletions(-)
kernel/sched/fair.c +111 -29
@@ -2738,15 +2738,46 @@ wakeup_preempt_entity(struct sched_entit*/ static struct sched_entity *pick_next_entity (struct cfs_rq *cfs_rq) { -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, *curr = cfs_rq->curr; + +/* +* Since its possible we got here without doing put_prev_entity() we +* also have to consider cfs_rq->curr. If it was set, and is still a +* runnable entity, update_curr() will update its vruntime, otherwise +* forget we've ever seen it. +*/ +if (curr) { +if (curr->on_rq) +update_curr (cfs_rq); +else + curr =NULL ; + } + +/* +* 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; }
@@ -2768,7 +2799,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) {
@@ -3423,22 +3454,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)
@@ -3548,7 +3580,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) {}
@@ -4484,44 +4516,94 @@ static void check_preempt_wakeup(structset_last_buddy (se); } +/* +* Account for a descheduled task: +*/ +static void put_prev_task_fair (struct rq *rq,struct task_struct *prev) +{ +struct sched_entity *se = &prev->se; +struct cfs_rq *cfs_rq; + +for_each_sched_entity (se) { + cfs_rq =cfs_rq_of (se); +put_prev_entity (cfs_rq, se); + } +} +static struct task_struct *pick_next_task_fair (struct rq *rq,struct task_struct *prev) { +struct sched_entity *se,__maybe_unused *pse;struct task_struct *p; -struct cfs_rq *cfs_rq = &rq->cfs; -struct sched_entity *se; +struct cfs_rq *cfs_rq; + +again:__maybe_unused + cfs_rq = &rq->cfs; + +if (prev) { +if (!IS_ENABLED (CONFIG_FAIR_GROUP_SCHED ) || + (prev->sched_class != &fair_sched_class)) { + prev->sched_class->put_prev_task (rq, prev); + prev =NULL ; + } + }if (!cfs_rq->nr_running)return NULL ; -if (prev) - prev->sched_class->put_prev_task (rq, prev); -do { se =pick_next_entity (cfs_rq); -set_next_entity (cfs_rq, se); +if (!prev) +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); -return p; -} +#ifdef CONFIG_FAIR_GROUP_SCHED +/* +* If we haven't yet done put_prev_entity and the selected task is +* a different task than we started out with, try and touch the least +* amount of cfs_rq trees. +*/ +if (prev) { +if (prev != p) { + 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); + } + } -/* -* Account for a descheduled task: -*/ -static void put_prev_task_fair (struct rq *rq,struct task_struct *prev) -{ -struct sched_entity *se = &prev->se; -struct cfs_rq *cfs_rq; +put_prev_entity (cfs_rq, pse); +set_next_entity (cfs_rq, se); + } -for_each_sched_entity (se) { - cfs_rq =cfs_rq_of (se); -put_prev_entity (cfs_rq, se); +/* +* In case the common cfs_rq got throttled, just give up and +* put the stack and retry. +*/ +if (unlikely (check_cfs_rq_runtime (cfs_rq))) { +put_prev_task_fair (rq, p); + prev =NULL ; + goto again; + } } +#endif + +if (hrtick_enabled (rq)) +hrtick_start_fair (rq, p); + +return p; }/*
[email protected]
reviewerRe: [PATCH 8/9] sched/fair: Optimize cgroup pick_next_task_fair
Quoted 77 lines · Peter Zijlstra
static struct
task_struct*pick_next_task_fair(struct rq *rq, struct task_struct *prev){kernel/sched/fair.c +41
-19+struct sched_entity *se,__maybe_unused *pse;struct task_struct *p; -struct cfs_rq *cfs_rq = &rq->cfs; -struct sched_entity *se; +struct cfs_rq *cfs_rq; + +again:__maybe_unused + cfs_rq = &rq->cfs; + +if (prev) { +if (!IS_ENABLED (CONFIG_FAIR_GROUP_SCHED ) || + (prev->sched_class != &fair_sched_class)) { + prev->sched_class->put_prev_task (rq, prev); + prev =NULL ; + } + }if (!cfs_rq->nr_running)return NULL ; -if (prev) - prev->sched_class->put_prev_task (rq, prev); -do { se =pick_next_entity (cfs_rq); -set_next_entity (cfs_rq, se); +if (!prev) +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); -return p; -} +#ifdef CONFIG_FAIR_GROUP_SCHED +/* +* If we haven't yet done put_prev_entity and the selected task is +* a different task than we started out with, try and touch the least +* amount of cfs_rq trees. +*/ +if (prev) { +if (prev != p) { + 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); + } + } -/* -* Account for a descheduled task: -*/ -static void put_prev_task_fair (struct rq *rq,struct task_struct *prev) -{ -struct sched_entity *se = &prev->se; -struct cfs_rq *cfs_rq; +put_prev_entity (cfs_rq, pse); +set_next_entity (cfs_rq, se); + } -for_each_sched_entity (se) { - cfs_rq =cfs_rq_of (se);
kernel/sched/fair.c static void check_preempt_wakeup(struct · line 4599
Quoted 10 lines
kernel/sched/fair.c +9
-1-put_prev_entity (cfs_rq, se); +/* +* In case the common cfs_rq got throttled, just give up and +* put the stack and retry. +*/ +if (unlikely (check_cfs_rq_runtime (cfs_rq))) { +put_prev_task_fair (rq, p); + prev =NULL ; + goto again; + }
This double-calls put_prev_entity on any non-common cfs_rqs and ses, which means double __enqueue_entity, among other things. Just doing the put_prev loop from se->parent should fix that.
However, any sort of abort means that we may have already done set_next_entity on some children, which even with the changes to pick_next_entity will cause problems, up to and including double __dequeue_entity I think.
Also, this way we never do check_cfs_rq_runtime on any parents of the common cfs_rq, which could even have been the reason for the resched to begin with. I'm not sure if there would be any problem doing it on the way down or not, I don't see any problems at a glance.
Quoted 10 lines
kernel/sched/fair.c +6
-0} +#endif + +if (hrtick_enabled (rq)) +hrtick_start_fair (rq, p); + +return p; }/*
Peter Zijlstra
maintainerRe: [PATCH 8/9] sched/fair: Optimize cgroup pick_next_task_fair
Quoted 26 lines · On Tue, Jan 21, 2014 at 11:24:39AM -0800, [email protected] wrote:
Quoted 24 lines · Peter Zijlstra
kernel/sched/fair.c +23
-0+#ifdef CONFIG_FAIR_GROUP_SCHED +/* +* If we haven't yet done put_prev_entity and the selected task is +* a different task than we started out with, try and touch the least +* amount of cfs_rq trees. +*/ +if (prev) { +if (prev != p) { + 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); + } + }
Quoted 3 lines
kernel/sched/fair.c static void check_preempt_wakeup(struct · line 4589
Quoted 3 lines
kernel/sched/fair.c +3
-0+put_prev_entity (cfs_rq, pse); +set_next_entity (cfs_rq, se); + }
(A)
Quoted 5 lines
Quoted 5 lines
kernel/sched/fair.c +5
-0+/* +* In case the common cfs_rq got throttled, just give up and +* put the stack and retry. +*/ +if (unlikely (check_cfs_rq_runtime (cfs_rq))) {
Quoted 8 lines
kernel/sched/fair.c static void check_preempt_wakeup(struct · line 4599
Quoted 4 lines
kernel/sched/fair.c +4
-0+put_prev_task_fair (rq, p); + prev =NULL ; + goto again; + }This double-calls
put_prev_entityon any non-commoncfs_rqsand ses, which means double__enqueue_entity, among other things. Just doing theput_prevloop fromse->parentshould fix that.
I'm not seeing that, so at point (A) we've completely switched over from @prev to @p, we've put all pse until the common parent and set all se back to @p.
So if we then do: put_prev_task_fair(rq, p), we simply undo all the set_next_entity(se) we just did, and continue from the common parent upwards.
Quoted 4 lines
However, any sort of abort means that we may have already done
set_next_entityon some children, which even with the changes topick_next_entitywill cause problems, up to and including double__dequeue_entityI think.
But the abort is only done after we've completely set up @p as the current task.
Yes, completely tearing it down again is probably a waste, but given that bandwidth enforcement should be rare and I didn't want to complicate things even further for rare cases.
Quoted 4 lines
Also, this way we never do
check_cfs_rq_runtimeon any parents of the commoncfs_rq, which could even have been the reason for the resched to begin with. I'm not sure if there would be any problem doing it on the way down or not, I don't see any problems at a glance.
Oh, so we allow a parent to have less runtime than the sum of all its children?
Indeed, in that case we can miss something... we could try to call check_cfs_rq_runtime() from the initial top-down selection loop? When true, just put the entire stack and don't pretend to be smart?
[email protected]
reviewerRe: [PATCH 8/9] sched/fair: Optimize cgroup pick_next_task_fair
Quoted 60 lines · Peter Zijlstra
Quoted 26 lines · On Tue, Jan 21, 2014 at 11:24:39AM -0800, [email protected] wrote:
Quoted 24 lines · Peter Zijlstra
kernel/sched/fair.c +23
-0+#ifdef CONFIG_FAIR_GROUP_SCHED +/* +* If we haven't yet done put_prev_entity and the selected task is +* a different task than we started out with, try and touch the least +* amount of cfs_rq trees. +*/ +if (prev) { +if (prev != p) { + 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); + } + }Quoted 3 lines
kernel/sched/fair.c static void check_preempt_wakeup(struct · line 4589
Quoted 3 lines
kernel/sched/fair.c +3
-0+put_prev_entity (cfs_rq, pse); +set_next_entity (cfs_rq, se); + }(A)
Quoted 5 lines
Quoted 5 lines
kernel/sched/fair.c +5
-0+/* +* In case the common cfs_rq got throttled, just give up and +* put the stack and retry. +*/ +if (unlikely (check_cfs_rq_runtime (cfs_rq))) {Quoted 8 lines
kernel/sched/fair.c static void check_preempt_wakeup(struct · line 4599
Quoted 4 lines
kernel/sched/fair.c +4
-0+put_prev_task_fair (rq, p); + prev =NULL ; + goto again; + }This double-calls
put_prev_entityon any non-commoncfs_rqsand ses, which means double__enqueue_entity, among other things. Just doing theput_prevloop fromse->parentshould fix that.I'm not seeing that, so at point (A) we've completely switched over from @prev to @p, we've put all pse until the common parent and set all se back to @p.
So if we then do:
put_prev_task_fair(rq, p), we simply undo all theset_next_entity(se)we just did, and continue from the common parent upwards.Quoted 4 lines
However, any sort of abort means that we may have already done
set_next_entityon some children, which even with the changes topick_next_entitywill cause problems, up to and including double__dequeue_entityI think.
Quoted 6 lines
But the abort is only done after we've completely set up @p as the current task.
Yes, completely tearing it down again is probably a waste, but given that bandwidth enforcement should be rare and I didn't want to complicate things even further for rare cases.
Ah, I missed that this was p, not prev. That makes a lot more sense, and I agree that this should be fine.
Quoted 8 lines
Quoted 5 lines
Also, this way we never do
check_cfs_rq_runtimeon any parents of the commoncfs_rq, which could even have been the reason for the resched to begin with. I'm not sure if there would be any problem doing it on the way down or not, I don't see any problems at a glance.Oh, so we allow a parent to have less runtime than the sum of all its children?
Yeah, the check is currently max(children) <= parent, and unthrottled children are also allowed.
Quoted 4 lines
Indeed, in that case we can miss something... we could try to call
check_cfs_rq_runtime()from the initial top-down selection loop? When true, just put the entire stack and don't pretend to be smart?
Yeah, I think that should work. I wasn't sure if there could be a problem of doing throttle_cfs_rq(parent); throttle_cfs_rq(child);, but thinking about, that has to be ok, because schedule can do that if deactivate throttled the parent, schedule calls update_rq_clock, and then put_prev throttled the child.
Peter Zijlstra
maintainerRe: [PATCH 8/9] sched/fair: Optimize cgroup pick_next_task_fair
Quoted 9 lines · On Tue, Jan 21, 2014 at 12:03:38PM -0800, [email protected] wrote:
Quoted 3 lines
Indeed, in that case we can miss something... we could try to call
check_cfs_rq_runtime()from the initial top-down selection loop? When true, just put the entire stack and don't pretend to be smart?Yeah, I think that should work. I wasn't sure if there could be a problem of doing
throttle_cfs_rq(parent);throttle_cfs_rq(child);, but thinking about, that has to be ok, because schedule can do that if deactivate throttled the parent, schedule callsupdate_rq_clock, and thenput_prevthrottled the child.
Maybe something like the below? Completely untested and everything.
There's the obviuos XXX fail that was also in the previous version; not sure how to deal with that yet, either we need to change the interface to take struct task_struct **prev, or get smarter :-)
Any other obvious fails in here?
---
kernel/sched/fair.c +116 -27
@@ -2736,17 +2736,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; }
@@ -2768,7 +2787,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) {
@@ -3423,22 +3442,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)
@@ -3548,7 +3568,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) {}
@@ -4484,26 +4504,109 @@ static void check_preempt_wakeup(structset_last_buddy (se); } +/* +* Account for a descheduled task: +*/ +static void put_prev_task_fair (struct rq *rq,struct task_struct *prev) +{ +struct sched_entity *se = &prev->se; +struct cfs_rq *cfs_rq; + +for_each_sched_entity (se) { + cfs_rq =cfs_rq_of (se); +put_prev_entity (cfs_rq, se); + } +} +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;struct sched_entity *se; +struct task_struct *p;if (!cfs_rq->nr_running)return NULL ; -if (prev) +if (!IS_ENABLED (CONFIG_FAIR_GROUP_SCHED ) || + (prev->sched_class != &fair_sched_class)) { prev->sched_class->put_prev_task (rq, prev); + prev =NULL ; + } + +#ifdef CONFIG_FAIR_GROUP_SCHED +if (!prev) + goto simple;do { - se =pick_next_entity (cfs_rq); +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->on_rq) +update_curr (cfs_rq); +else + curr =NULL ; + +if (unlikely (check_cfs_rq_runtime (cfs_rq))) { +put_prev_task_fair (rq, prev); + 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); + } + +return p; +simple: +#endif + cfs_rq = &rq->cfs; + +if (!cfs_rq->nr_running) { +// XXX FAIL we should never return NULL after putting @prev +return NULL ; + } + +do { + 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);
@@ -4511,20 +4614,6 @@ pick_next_task_fair(struct rq *rq, struc }/* -* Account for a descheduled task: -*/ -static void put_prev_task_fair (struct rq *rq,struct task_struct *prev) -{ -struct sched_entity *se = &prev->se; -struct cfs_rq *cfs_rq; - -for_each_sched_entity (se) { - cfs_rq =cfs_rq_of (se); -put_prev_entity (cfs_rq, se); - } -} - -/* * sched_yield() is very simple * * The magic of dealing with the ->skip buddy is in pick_next_entity.
[email protected]
reviewerRe: [PATCH 8/9] sched/fair: Optimize cgroup pick_next_task_fair
Quoted 12 lines · Peter Zijlstra
Quoted 9 lines · On Tue, Jan 21, 2014 at 12:03:38PM -0800, [email protected] wrote:
Quoted 3 lines
Indeed, in that case we can miss something... we could try to call
check_cfs_rq_runtime()from the initial top-down selection loop? When true, just put the entire stack and don't pretend to be smart?Yeah, I think that should work. I wasn't sure if there could be a problem of doing
throttle_cfs_rq(parent);throttle_cfs_rq(child);, but thinking about, that has to be ok, because schedule can do that if deactivate throttled the parent, schedule callsupdate_rq_clock, and thenput_prevthrottled the child.
Quoted 7 lines
Maybe something like the below? Completely untested and everything.
There's the obviuos XXX fail that was also in the previous version; not sure how to deal with that yet, either we need to change the interface to take struct
task_struct**prev, or get smarter :-)Any other obvious fails in here?
prev can be NULL to start with, hrtick should be handled in both paths. How about this on top of your patch (equally untested) to fix those and the XXX? The double-check on nr_running is annoying, but necessary when prev slept.
---
kernel/sched/fair.c +9 -13
@@ -4528,14 +4528,8 @@ pick_next_task_fair(struct rq *rq, struct task_struct *prev)if (!cfs_rq->nr_running)return NULL ; -if (!IS_ENABLED (CONFIG_FAIR_GROUP_SCHED ) || - (prev->sched_class != &fair_sched_class)) { - prev->sched_class->put_prev_task (rq, prev); - prev =NULL ; - } - #ifdef CONFIG_FAIR_GROUP_SCHED - if (!prev) + if (!prev || prev->sched_class != &fair_sched_class) goto simple; do {
@@ -4552,10 +4546,8 @@ pick_next_task_fair(struct rq *rq, struct task_struct *prev)else curr =NULL ; -if (unlikely (check_cfs_rq_runtime (cfs_rq))) { -put_prev_task_fair (rq, prev); +if (unlikely (check_cfs_rq_runtime (cfs_rq))) goto simple; - } se =pick_next_entity (cfs_rq, curr); cfs_rq =group_cfs_rq (se);
@@ -4589,15 +4581,19 @@ pick_next_task_fair(struct rq *rq, struct task_struct *prev) set_next_entity(cfs_rq, se); } + if (hrtick_enabled(rq)) + hrtick_start_fair(rq, p); + return p; simple: #endif cfs_rq = &rq->cfs; - if (!cfs_rq->nr_running) { - // XXX FAIL we should never return NULL after putting @prev + if (!cfs_rq->nr_running) return NULL; - } + + if (prev) + prev->sched_class->put_prev_task(rq, prev); do { se = pick_next_entity(cfs_rq, NULL);
Peter Zijlstra
maintainerRe: [PATCH 8/9] sched/fair: Optimize cgroup pick_next_task_fair
Quoted 4 lines · On Tue, Jan 21, 2014 at 01:43:32PM -0800, [email protected] wrote:
prev can be NULL to start with, hrtick should be handled in both paths. How about this on top of your patch (equally untested) to fix those and the XXX? The double-check on
nr_runningis annoying, but necessary when prev slept.
Ah yes indeed. Let me build the lot and see if I can wreck it ;-)
Peter Zijlstra
maintainerPATCH 9/9 sched: Use idle task shortcut
In reply to Peter ZijlstraWith the previous patches, we have no ambiguity on going to idle. So we can return directly the idle task instead of looking up all the domains which will in any case return the idle_task.
--- kernel/sched/core.c | 39 +++++++++++++++++++++++---------------- 1 file changed, 23 insertions(+), 16 deletions(-)
kernel/sched/core.c +23 -16
@@ -2563,23 +2563,33 @@ pick_next_task(struct rq *rq, struct tasconst struct sched_class *class;struct task_struct *p; +again: +if (likely (rq->nr_running)) { +/* +* 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)) +return fair_sched_class.pick_next_task (rq, prev); + +for_each_class (class) { + p = class->pick_next_task (rq, prev); +if (p) +return p; + } + } +/* -* Optimization: we know that if all tasks are in -* the fair class we can call that function directly: +* If there is a task balanced on this cpu, pick the next task, +* otherwise fall in the optimization by picking the idle task +* directly. */ -if (likely (rq->nr_running == rq->cfs.h_nr_running)) { - p = fair_sched_class.pick_next_task (rq, prev); -if (likely (p)) -return p; - } +if (idle_balance (rq)) + goto again; -for_each_class (class) { - p = class->pick_next_task (rq, prev); -if (p) -return p; - } + rq->idle_stamp =rq_clock (rq); -BUG ();/* the idle class will always have a runnable task */ +return idle_sched_class.pick_next_task (rq, prev); }/*
@@ -2672,9 +2682,6 @@ static void __sched __schedule(void)pre_schedule (rq, prev); -if (unlikely (!rq->nr_running)) - rq->idle_stamp =idle_balance (rq) ?0 :rq_clock (rq); -if (prev->on_rq || rq->skip_clock_update <0 )update_rq_clock (rq);