sched: Remove 'cpu' parameter for idle_balance()
PATCH 1/4 sched: Remove 'cpu' parameter for idle_balance()
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 @@ need_resched: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 @@ out:* 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_sched_class;extern 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);
Signature · 1 line
1.7.9.5
PATCH 2/4 sched: Fix race in idle_balance()
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
Signature · 1 line
1.7.9.5
Peter Zijlstra
maintainerRe: [PATCH 2/4] sched: Fix race in idle_balance()
Quoted 4 lines · Daniel Lezcano
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 inidle_balance()assuming it will go to idle otherwise.
Quoted 8 lines
But the
idle_balance()releases therq->lockin 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 theidle_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.
Did you actually observe this or was it found by reading the code?
Re: [PATCH 2/4] sched: Fix race in idle_balance()
Quoted 10 lines · Peter Zijlstra
Quoted 9 lines · Daniel Lezcano
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 inidle_balance()assuming it will go to idle otherwise.But the
idle_balance()releases therq->lockin 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 theidle_stamp, thinking we will.
Quoted 5 lines
Quoted 3 lines
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.Did you actually observe this or was it found by reading the code?
When I tried to achieve what is doing the patch 4/4, I was falling in the BUG() (comment in patch 4/4). So I did some tests and checked that we enter idle_balance() with nr_running == 0 but we exit with nr_running > 0 and pulled_task == 0.
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
tip-bot for Daniel Lezcano
merge bot[tip:sched/core] sched: Fix race in idle_balance()
In reply to Daniel Lezcanosched: Fix race in idle_balance()
Commit-ID: e5fc66119ec97054eefc83f173a7ee9e133c3c3a Gitweb: http://git.kernel.org/tip/e5fc66119ec97054eefc83f173a7ee9e133c3c3a Author: Daniel Lezcano <[email protected]> AuthorDate: Fri, 17 Jan 2014 10:04:02 +0100 Committer: Ingo Molnar <[email protected]> CommitDate: Mon, 10 Feb 2014 16:17:04 +0100
sched: Fix race in idle_balance()
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 idle_balance() releases the rq->lock in order to look up 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
@@ -6589,6 +6589,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
PATCH 3/4 sched: Move idle_stamp up to the core
In reply to Daniel LezcanoThe 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 @@ need_resched: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 @@ out:* 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_sched_class;extern 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);
Signature · 1 line
1.7.9.5
tip-bot for Daniel Lezcano
merge bot[tip:sched/core] sched: Move rq->idle_stamp up to the core
sched: Move rq->idle_stamp up to the core
Commit-ID: 3c4017c13f91069194fce3160944efec50f15a6e Gitweb: http://git.kernel.org/tip/3c4017c13f91069194fce3160944efec50f15a6e Author: Daniel Lezcano <[email protected]> AuthorDate: Fri, 17 Jan 2014 10:04:03 +0100 Committer: Ingo Molnar <[email protected]> CommitDate: Mon, 10 Feb 2014 16:17:07 +0100
sched: Move rq->idle_stamp up to the core
idle_balance() modifies the rq->idle_stamp field, making this information shared across core.c and fair.c.
As we know if the cpu is going to idle or not with the previous patch, let's encapsulate the rq->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
@@ -2704,8 +2704,15 @@ need_resched: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
@@ -6531,7 +6531,7 @@ out:* 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 ;
@@ -6539,10 +6539,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.
@@ -6580,10 +6578,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 ();
@@ -6594,7 +6590,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)) {/*
@@ -6606,6 +6602,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
@@ -1158,7 +1158,7 @@ extern const struct sched_class idle_sched_class;extern 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);
PATCH 4/4 sched: Idle task shortcut optimization
In reply to Daniel LezcanoWith the previous patch, we have no ambiguity on going to idle. So we can pick directly the idle task instead of looking up all the domains which will in any case return no task except the idle_task.
--- kernel/sched/core.c | 43 ++++++++++++++++++++++++++++++++++++++----- kernel/sched/idle_task.c | 15 +++++---------- 2 files changed, 43 insertions(+), 15 deletions(-)
kernel/sched/core.c +38 -5
@@ -2586,7 +2586,43 @@ pick_next_task(struct rq *rq)return p; } -BUG ();/* the idle class will always have a runnable task */ +/* +* We must have at least one task to run, the idle task is +* returned by the shortcut in pick_next_task_or_idle. If we +* fall here, we don't have any task to run, so something is +* wrong when we thought the cpu was not going to idle. +*/ +BUG (); +} + +static inline struct task_struct *pick_next_task_or_idle (struct rq *rq) +{ +if (likely (rq->nr_running)) +return pick_next_task (rq); + + rq->idle_stamp =0 ; + +/* +* 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)) +return pick_next_task (rq); + + rq->idle_stamp =rq_clock (rq); + +/* +* Optimization: pick_next_task will return rq->idle in any case but +* after walking through the different sched domains. Let's add a +* shortcut to directly return the idle task. +*/ +schedstat_inc (rq, sched_goidle); +#ifdef CONFIG_SMP +/* Trigger the post schedule to do an idle_enter for CFS */ + rq->post_schedule =1 ; +#endif +return rq->idle; }/*
@@ -2679,11 +2715,8 @@ need_resched:pre_schedule (rq, prev); -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); + next =pick_next_task_or_idle (rq);clear_tsk_need_resched (prev);clear_preempt_need_resched (); rq->skip_clock_update =0 ;
kernel/sched/idle_task.c +5 -10
@@ -33,16 +33,6 @@ static void check_preempt_curr_idle(struct rq *rq, struct task_struct *p, int flresched_task (rq->idle); } -static struct task_struct *pick_next_task_idle (struct rq *rq) -{ -schedstat_inc (rq, sched_goidle); -#ifdef CONFIG_SMP -/* Trigger the post schedule to do an idle_enter for CFS */ - rq->post_schedule =1 ; -#endif -return rq->idle; -} -/* * It is not legal to sleep in the idle task - print a warning * message if some code attempts to do it:
@@ -60,6 +50,11 @@ static void put_prev_task_idle(struct rq *rq, struct task_struct *prev) { } +static struct task_struct *pick_next_task_idle (struct rq *rq) +{ +return NULL ; +} +static void task_tick_idle (struct rq *rq,struct task_struct *curr,int queued) { }
Signature · 1 line
1.7.9.5
Peter Zijlstra
maintainerRe: [PATCH 4/4] sched: Idle task shortcut optimization
Review
Quoted 6 lines · Daniel Lezcano
(quoted diff) +6
-0+ schedstat_inc(rq, sched_goidle); +#ifdef CONFIG_SMP + /* Trigger the post schedule to do an idle_enter for CFS */ + rq->post_schedule = 1; +#endif + return rq->idle;
Urgh, that retains the stupid idle crap like it is.
I've not yet tested this, but is there a reason something like the below couldn't work?
---
Subject: sched: Clean up idle task SMP logic
From: Peter Zijlstra <[email protected]>
Date: Fri Jan 17 14:54:02 CET 2014
The 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,
Re: [PATCH 4/4] sched: Idle task shortcut optimization
Quoted 10 lines · Peter Zijlstra
Review
Quoted 6 lines · Daniel Lezcano
(quoted diff) +6
-0+ schedstat_inc(rq, sched_goidle); +#ifdef CONFIG_SMP + /* Trigger the post schedule to do an idle_enter for CFS */ + rq->post_schedule = 1; +#endif + return rq->idle;Urgh, that retains the stupid idle crap like it is.
Quoted 2 lines
I've not yet tested this, but is there a reason something like the below couldn't work?
I tested it by running hackbench and it seems to work as expected.
Quoted 91 lines
---
Subject: sched: Clean up idle task SMP logic
From: Peter Zijlstra <[email protected]>
Date: Fri Jan 17 14:54:02 CET 2014The idle
post_schedulehook is just a vile waste of time, fix it proper.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(-)Index:
linux-2.6/kernel/sched/fair.c
===================================================================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) {Index:
linux-2.6/kernel/sched/idle_task.c
===================================================================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,
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 4/4] sched: Idle task shortcut optimization
Quoted 11 lines · Daniel Lezcano
Quoted 10 lines · Peter Zijlstra
Review
Quoted 6 lines · Daniel Lezcano
(quoted diff) +6
-0+ schedstat_inc(rq, sched_goidle); +#ifdef CONFIG_SMP + /* Trigger the post schedule to do an idle_enter for CFS */ + rq->post_schedule = 1; +#endif + return rq->idle;Urgh, that retains the stupid idle crap like it is.
Quoted 4 lines
Quoted 2 lines
I've not yet tested this, but is there a reason something like the below couldn't work?
I tested it by running hackbench and it seems to work as expected.
Thanks, I was still looking through the throttling. I'll keep it then :-)
Peter Zijlstra
maintainerRe: [PATCH 4/4] sched: Idle task shortcut optimization
In reply to Daniel Lezcanokernel/sched/core.c need_resched: · line 2722
Quoted 13 lines · Daniel Lezcano
kernel/sched/core.c +1
-4@@ -2679,11 +2715,8 @@ need_resched:pre_schedule (rq, prev); -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); + next =pick_next_task_or_idle (rq);clear_tsk_need_resched (prev);clear_preempt_need_resched (); rq->skip_clock_update =0 ;
I have vague memories that we need to have idle_balance() before put_prev_task(), but I can't recollect why this would be so.
That said, if I resurrect these patches:
https://lkml.org/lkml/2012/6/14/271
I suppose we could write something like:
struct task_struct *pick_next_task(struct rq *rq, struct task_struct *prev)
{
const struct sched_class *class;
struct task_struct *p;again:
if (likely(rq->nr_running)) {
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;
}
}
if (idle_balance(rq))
goto again;
rq->idle_stamp = rq_clock(rq);
return idle_sched_class.pick_next_task(rq, prev);
}Which keeps idle_balance() before put_prev_task(), and by using idle_sched_clas.pick_next_task() doesn't rape the idle class interface like you did :-)
Re: [PATCH 4/4] sched: Idle task shortcut optimization
Quoted 50 lines · Peter Zijlstra
kernel/sched/core.c need_resched: · line 2722
Quoted 13 lines · Daniel Lezcano
kernel/sched/core.c +1
-4@@ -2679,11 +2715,8 @@ need_resched:pre_schedule (rq, prev); -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); + next =pick_next_task_or_idle (rq);clear_tsk_need_resched (prev);clear_preempt_need_resched (); rq->skip_clock_update =0 ;I have vague memories that we need to have
idle_balance()beforeput_prev_task(), but I can't recollect why this would be so.That said, if I resurrect these patches:
https://lkml.org/lkml/2012/6/14/271I suppose we could write something like:
struct
task_struct*pick_next_task(struct rq *rq, structtask_struct*prev){ const struct sched_class *class; struct task_struct *p;again:
if (likely(rq->nr_running)) { 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; } } if (idle_balance(rq)) goto again; rq->idle_stamp = rq_clock(rq); return idle_sched_class.pick_next_task(rq, prev); }
Quoted 3 lines
Which keeps
idle_balance()beforeput_prev_task(), and by usingidle_sched_clas.pick_next_task()doesn't rape the idle class interface like you did :-)
But put_prev_task is called before pick_next_task, so idle_balance() is called after now, no ?
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 4/4] sched: Idle task shortcut optimization
Quoted 28 lines · Daniel Lezcano
Quoted 28 lines
I suppose we could write something like:
struct
task_struct*pick_next_task(struct rq *rq, structtask_struct*prev){ const struct sched_class *class; struct task_struct *p;again:
if (likely(rq->nr_running)) { 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; } } if (idle_balance(rq)) goto again; rq->idle_stamp = rq_clock(rq); return idle_sched_class.pick_next_task(rq, prev); }
Quoted 6 lines
Quoted 3 lines
Which keeps
idle_balance()beforeput_prev_task(), and by usingidle_sched_clas.pick_next_task()doesn't rape the idle class interface like you did :-)But
put_prev_taskis called beforepick_next_task, soidle_balance()is called after now, no ?
No, put_prev_task() is called by the pick_next_task() that returns a task. So in the idle case above, the idle_sched_class.pick_next_task() will do the required put_prev_task().
Re: [PATCH 4/4] sched: Idle task shortcut optimization
Quoted 33 lines · Peter Zijlstra
Quoted 32 lines · Daniel Lezcano
Quoted 31 lines
I suppose we could write something like:
struct
task_struct*pick_next_task(struct rq *rq, structtask_struct*prev){ const struct sched_class *class; struct task_struct *p;again:
if (likely(rq->nr_running)) { 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; } } if (idle_balance(rq)) goto again; rq->idle_stamp = rq_clock(rq); return idle_sched_class.pick_next_task(rq, prev); }Which keeps
idle_balance()beforeput_prev_task(), and by usingidle_sched_clas.pick_next_task()doesn't rape the idle class interface like you did :-)
Quoted 6 lines
Quoted 2 lines
But
put_prev_taskis called beforepick_next_task, soidle_balance()is called after now, no ?No,
put_prev_task()is called by thepick_next_task()that returns a task. So in the idle case above, theidle_sched_class.pick_next_task()will do the requiredput_prev_task().
Ah, ok. Let me try it.
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 4/4] sched: Idle task shortcut optimization
Quoted 3 lines · Daniel Lezcano
Ah, ok. Let me try it.
http://programming.kicks-ass.net/sekrit/patches.tar.bz2
has a queue that applies to tip/master.
The patches as on lkml need a little help in applying.
They've not been near a compiler yet though :/
Re: [PATCH 4/4] sched: Idle task shortcut optimization
Quoted 5 lines · Peter Zijlstra
Quoted 3 lines · Daniel Lezcano
Ah, ok. Let me try it.
Quoted 7 lines
http://programming.kicks-ass.net/sekrit/patches.tar.bz2
has a queue that applies to tip/master.
The patches as on lkml need a little help in applying.
They've not been near a compiler yet though :/
Thanks a lot for the series. That makes my life easier :)
I did a small compilation fix with the pick_next_task function for the deadline scheduler and currently hackbench is running. I will give you the results in a moment.
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
Re: [PATCH 4/4] sched: Idle task shortcut optimization
In reply to Peter ZijlstraQuoted 5 lines · Peter Zijlstra
Quoted 3 lines · Daniel Lezcano
Ah, ok. Let me try it.
Quoted 8 lines
http://programming.kicks-ass.net/sekrit/patches.tar.bz2
has a queue that applies to tip/master.
The patches as on lkml need a little help in applying.
They've not been near a compiler yet though :/
Here are the results:
Col1 : tip/sched/core
Col2 : the patchset above
Col3 : the patchset above + idle task shortcut
hackbench -s 4096 -l 1000 -g 10 -f 40 -T
33.306 32.720 31.902
32.344 32.139 32.214
33.342 33.281 33.056
33.319 33.421 31.789
32.325 32.540 31.941
33.701 32.978 32.229
34.981 32.418 30.218
32.379 31.656 31.717
32.135 32.241 32.812
32.531 32.790 31.967
avg:
33.036 32.618 31.984
hackbench -p -s 4096 -l 1000 -g 10 -f 40
27.595 27.601 26.331
25.192 29.336 30.222
26.057 28.579 28.351
28.397 29.419 28.554
27.628 25.045 30.470
28.976 28.027 29.823
28.764 29.361 26.902
27.632 30.101 26.285
29.129 29.248 26.975
26.020 25.047 29.324
avg:
27.539 28.176 28.324
hackbench -P -s 4096 -l 1000 -g 10 -f 40
32.788 32.057 30.691
33.158 33.251 34.315
32.713 33.076 32.880
32.488 32.878 32.792
31.240 33.003 32.958
32.493 33.096 32.244
33.940 33.660 31.550
34.733 33.777 31.829
32.598 34.117 33.714
34.091 33.196 31.336
avg:
33.024 33.211 32.431
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
PATCH 1/2 sched/deadline: Fix compilation error
The pick_next_task function prototype changed with the previous patches.
--- kernel/sched/deadline.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/sched/deadline.c +1 -1
@@ -989,7 +989,7 @@ static struct sched_dl_entity *pick_next_dl_entity(struct rq *rq, 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;
Signature · 1 line
1.7.9.5
PATCH 2/2 sched: Use idle task shortcut
From: Peter Zijlstra <[email protected]>
With 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 task_struct *prev)const 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 @@ need_resched: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);
Signature · 1 line
1.7.9.5
Re: [PATCH 4/4] sched: Idle task shortcut optimization
In reply to Peter ZijlstraQuoted 5 lines · Peter Zijlstra
Quoted 3 lines · Daniel Lezcano
Ah, ok. Let me try it.
Quoted 7 lines
http://programming.kicks-ass.net/sekrit/patches.tar.bz2
has a queue that applies to tip/master.
The patches as on lkml need a little help in applying.
They've not been near a compiler yet though :/
Hi Peter,
do you want me to resend the full serie with your patchset included ?
Thanks
-- Daniel
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 4/4] sched: Idle task shortcut optimization
Quoted 10 lines · Daniel Lezcano
Quoted 9 lines · Peter Zijlstra
Quoted 3 lines · Daniel Lezcano
Ah, ok. Let me try it.
http://programming.kicks-ass.net/sekrit/patches.tar.bz2
has a queue that applies to tip/master.
Quoted 7 lines
Quoted 3 lines
The patches as on lkml need a little help in applying.
They've not been near a compiler yet though :/
Hi Peter,
do you want me to resend the full serie with your patchset included ?
Nah, I'll send it out, I wanted PJT or Ben to look over one more patch I did, meant to do that yesterday but you know how those things go :-)
Re: [PATCH 4/4] sched: Idle task shortcut optimization
Quoted 13 lines · Peter Zijlstra
Quoted 12 lines · Daniel Lezcano
Quoted 11 lines · Peter Zijlstra
Quoted 3 lines · Daniel Lezcano
Ah, ok. Let me try it.
http://programming.kicks-ass.net/sekrit/patches.tar.bz2
has a queue that applies to tip/master.
The patches as on lkml need a little help in applying.
Quoted 8 lines
Quoted 5 lines
Quoted 1 line
They've not been near a compiler yet though :/
Hi Peter,
do you want me to resend the full serie with your patchset included ?
Nah, I'll send it out, I wanted PJT or Ben to look over one more patch I did, meant to do that yesterday but you know how those things go :-)
Yeah :)
Thanks !
-- Daniel
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
tip-bot for Daniel Lezcano
merge bot[tip:sched/core] sched: Remove 'cpu' parameter from idle_balance( )
In reply to Daniel Lezcanosched: Remove 'cpu' parameter from idle_balance()
Commit-ID: b4f2ab43615e5b36c48fffa99f26aca381839ac6 Gitweb: http://git.kernel.org/tip/b4f2ab43615e5b36c48fffa99f26aca381839ac6 Author: Daniel Lezcano <[email protected]> AuthorDate: Fri, 17 Jan 2014 10:04:01 +0100 Committer: Ingo Molnar <[email protected]> CommitDate: Mon, 10 Feb 2014 16:17:01 +0100
sched: Remove 'cpu' parameter from idle_balance()
The cpu parameter passed to idle_balance() is not needed as it could be retrieved from '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
@@ -2705,7 +2705,7 @@ need_resched: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
@@ -6531,12 +6531,13 @@ out:* 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
@@ -1158,7 +1158,7 @@ extern const struct sched_class idle_sched_class;extern 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);