sched/fair: Tweaks for select_task_rq_fair slowpath
v2 cover sched/fair: Tweaks for select_task_rq_fair slowpath
This patchset optimises away an unused comparison, and fixes some corner cases in the find_idlest_group path of select_task_rq_fair.
Changes v1 -> v2:
- Reworked task affinity checks to avoid repeating them, as per Vincent's suggestion. To avoid excessive indentation this required moving code into its own function, as per PeterZ's suggestion.
- Split up the patches.
- Altered the caller of find_idlest_group so that it now unconditionally uses find_idlest_group_cpu (formerly find_idlest_cpu). This means that we more often use the maligned "perspective-switching" logic at the bottom of the while(sd) loop, but it also means the task placement algorithm is more consistent between whether the idlest group is local or remote.
As mentioned in 5/5 an alternative would be to just initialise @new_cpu to @cpu instead of @prev_cpu (which is what PeterZ suggested in v1 review). In that case, some extra code could be removed in & around find_idlest_group_cpu.
Brendan Jackman (5):
sched/fair: Move select_task_rq_fair slow-path into its own function sched/fair: Remove unnecessary comparison with -1 sched/fair: Fix find_idlest_group when local group is not allowed sched/fair: Fix use of find_idlest_group when no groups are allowed sched/fair: Fix use of find_idlest_group when local group is idlest.
kernel/sched/fair.c | 112 ++++++++++++++++++++++++++++------------------------ 1 file changed, 61 insertions(+), 51 deletions(-)
--
2.14.1
PATCH v2 1/5 sched/fair: Move select_task_rq_fair slow-path into its own function
In preparation for changes that would otherwise require adding a new level of indentation to the while(sd) loop, create a new function find_idlest_cpu which contains this loop, and rename the existing find_idlest_cpu to find_idlest_group_cpu.
Code inside the while(sd) loop is unchanged. @new_cpu is added as a variable in the new function, with the same initial value as the @new_cpu in select_task_rq_fair.
squash! sched/fair: Move select_task_rq_fair slow-path into its own function
--- kernel/sched/fair.c | 83 +++++++++++++++++++++++++++++++---------------------- 1 file changed, 48 insertions(+), 35 deletions(-)
kernel/sched/fair.c +48 -35
@@ -5509,10 +5509,10 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p, }/* -* find_idlest_cpu - find the idlest cpu among the cpus in group. +* find_idlest_group_cpu - find the idlest cpu among the cpus in group. */ static int -find_idlest_cpu (struct sched_group *group,struct task_struct *p,int this_cpu) +find_idlest_group_cpu (struct sched_group *group,struct task_struct *p,int this_cpu) {unsigned long load, min_load =ULONG_MAX ;unsigned int min_exit_latency =UINT_MAX ;
@@ -5561,6 +5561,50 @@ find_idlest_cpu(struct sched_group *group, struct task_struct *p, int this_cpu)return shallowest_idle_cpu !=-1 ? shallowest_idle_cpu : least_loaded_cpu; } +static inline int find_idlest_cpu (struct sched_domain *sd,struct task_struct *p, +int cpu,int prev_cpu,int sd_flag) +{ +int new_cpu = prev_cpu; + +while (sd) { +struct sched_group *group; +struct sched_domain *tmp; +int weight; + +if (!(sd->flags & sd_flag)) { + sd = sd->child; +continue ; + } + + group =find_idlest_group (sd, p, cpu, sd_flag); +if (!group) { + sd = sd->child; +continue ; + } + + new_cpu =find_idlest_group_cpu (group, p, cpu); +if (new_cpu ==-1 || new_cpu == cpu) { +/* Now try balancing at a lower domain level of cpu */ + sd = sd->child; +continue ; + } + +/* Now try balancing at a lower domain level of new_cpu */ + cpu = new_cpu; + weight = sd->span_weight; + sd =NULL ; +for_each_domain (cpu, tmp) { +if (weight <= tmp->span_weight) +break ; +if (tmp->flags & sd_flag) + sd = tmp; + } +/* while loop will break here if sd == NULL */ + } + +return new_cpu; +} +#ifdef CONFIG_SCHED_SMT static inline void set_idle_cores (int cpu,int val)
@@ -5918,39 +5962,8 @@ select_task_rq_fair(struct task_struct *p, int prev_cpu, int sd_flag, int wake_fif (sd_flag &SD_BALANCE_WAKE )/* XXX always ? */ new_cpu =select_idle_sibling (p, prev_cpu, new_cpu); - }else while (sd) { -struct sched_group *group; -int weight; - -if (!(sd->flags & sd_flag)) { - sd = sd->child; -continue ; - } - - group =find_idlest_group (sd, p, cpu, sd_flag); -if (!group) { - sd = sd->child; -continue ; - } - - new_cpu =find_idlest_cpu (group, p, cpu); -if (new_cpu ==-1 || new_cpu == cpu) { -/* Now try balancing at a lower domain level of cpu */ - sd = sd->child; -continue ; - } - -/* Now try balancing at a lower domain level of new_cpu */ - cpu = new_cpu; - weight = sd->span_weight; - sd =NULL ; -for_each_domain (cpu, tmp) { -if (weight <= tmp->span_weight) -break ; -if (tmp->flags & sd_flag) - sd = tmp; - } -/* while loop will break here if sd == NULL */ + }else { + new_cpu =find_idlest_cpu (sd, p, cpu, prev_cpu, sd_flag); }rcu_read_unlock ();
Signature · 1 line
2.14.1
Re: [PATCH v2 1/5] sched/fair: Move select_task_rq_fair slow-path into its own function
Quoted 28 lines · Brendan Jackman
In preparation for changes that would otherwise require adding a new level of indentation to the while(sd) loop, create a new function
find_idlest_cpuwhich contains this loop, and rename the existingfind_idlest_cputofind_idlest_group_cpu.Code inside the while(sd) loop is unchanged. @new_cpu is added as a variable in the new function, with the same initial value as the @new_cpu in
select_task_rq_fair.Suggested-by Peter Zijlstra <[email protected]>Signed-off-by Brendan Jackman <[email protected]>Cc Dietmar Eggemann <[email protected]>Cc Vincent Guittot <[email protected]>Cc Josef Bacik <[email protected]>Cc Ingo Molnar <[email protected]>Cc Morten Rasmussen <[email protected]>Cc Peter Zijlstra <[email protected]>squash! sched/fair: Move
select_task_rq_fairslow-path into its own function--- kernel/sched/fair.c | 83 +++++++++++++++++++++++++++++++---------------------- 1 file changed, 48 insertions(+), 35 deletions(-)kernel/sched/fair.c +0
-0
kernel/sched/fair.c find_idlest_group(struct sched_domain *sd, struct task_struct *p, · line 5515
Quoted 9 lines
kernel/sched/fair.c +2
-2@@ -5509,10 +5509,10 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p, }/* -* find_idlest_cpu - find the idlest cpu among the cpus in group. +* find_idlest_group_cpu - find the idlest cpu among the cpus in group. */ static int -find_idlest_cpu (struct sched_group *group,struct task_struct *p,int this_cpu) +find_idlest_group_cpu (struct sched_group *group,struct task_struct *p,int this_cpu)
I hate this name but can't think of something that isn't unreasonably long either.
Thanks,
Josef
Re: [PATCH v2 1/5] sched/fair: Move select_task_rq_fair slow-path into its own function
In reply to Brendan JackmanQuoted 9 lines · Brendan Jackman
In preparation for changes that would otherwise require adding a new level of indentation to the while(sd) loop, create a new function
find_idlest_cpuwhich contains this loop, and rename the existingfind_idlest_cputofind_idlest_group_cpu.Code inside the while(sd) loop is unchanged. @new_cpu is added as a variable in the new function, with the same initial value as the @new_cpu in
select_task_rq_fair.
Quoted 8 lines
Suggested-by Peter Zijlstra <[email protected]>Signed-off-by Brendan Jackman <[email protected]>Cc Dietmar Eggemann <[email protected]>Cc Vincent Guittot <[email protected]>Cc Josef Bacik <[email protected]>Cc Ingo Molnar <[email protected]>Cc Morten Rasmussen <[email protected]>Cc Peter Zijlstra <[email protected]>
Quoted 119 lines
squash! sched/fair: Move
select_task_rq_fairslow-path into its own function--- kernel/sched/fair.c | 83 +++++++++++++++++++++++++++++++---------------------- 1 file changed, 48 insertions(+), 35 deletions(-)kernel/sched/fair.c +48
-36@@ -5509,10 +5509,10 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p, }/* -* find_idlest_cpu - find the idlest cpu among the cpus in group. +* find_idlest_group_cpu - find the idlest cpu among the cpus in group. */ static int -find_idlest_cpu (struct sched_group *group,struct task_struct *p,int this_cpu) +find_idlest_group_cpu (struct sched_group *group,struct task_struct *p,int this_cpu) {unsigned long load, min_load =ULONG_MAX ;unsigned int min_exit_latency =UINT_MAX ;@@ -5561,6 +5561,50 @@ find_idlest_cpu(struct sched_group *group, struct task_struct *p, int this_cpu)return shallowest_idle_cpu !=-1 ? shallowest_idle_cpu : least_loaded_cpu; } +static inline int find_idlest_cpu (struct sched_domain *sd,struct task_struct *p, +int cpu,int prev_cpu,int sd_flag) +{ +int new_cpu = prev_cpu; + +while (sd) { +struct sched_group *group; +struct sched_domain *tmp; +int weight; + +if (!(sd->flags & sd_flag)) { + sd = sd->child; +continue ; + } + + group =find_idlest_group (sd, p, cpu, sd_flag); +if (!group) { + sd = sd->child; +continue ; + } + + new_cpu =find_idlest_group_cpu (group, p, cpu); +if (new_cpu ==-1 || new_cpu == cpu) { +/* Now try balancing at a lower domain level of cpu */ + sd = sd->child; +continue ; + } + +/* Now try balancing at a lower domain level of new_cpu */ + cpu = new_cpu; + weight = sd->span_weight; + sd =NULL ; +for_each_domain (cpu, tmp) { +if (weight <= tmp->span_weight) +break ; +if (tmp->flags & sd_flag) + sd = tmp; + } +/* while loop will break here if sd == NULL */ + } + +return new_cpu; +} +#ifdef CONFIG_SCHED_SMT static inline void set_idle_cores (int cpu,int val)@@ -5918,39 +5962,8 @@ select_task_rq_fair(struct task_struct *p, int prev_cpu, int sd_flag, int wake_fif (sd_flag &SD_BALANCE_WAKE )/* XXX always ? */ new_cpu =select_idle_sibling (p, prev_cpu, new_cpu); - }else while (sd) { -struct sched_group *group; -int weight; - -if (!(sd->flags & sd_flag)) { - sd = sd->child; -continue ; - } - - group =find_idlest_group (sd, p, cpu, sd_flag); -if (!group) { - sd = sd->child; -continue ; - } - - new_cpu =find_idlest_cpu (group, p, cpu); -if (new_cpu ==-1 || new_cpu == cpu) { -/* Now try balancing at a lower domain level of cpu */ - sd = sd->child; -continue ; - } - -/* Now try balancing at a lower domain level of new_cpu */ - cpu = new_cpu; - weight = sd->span_weight; - sd =NULL ; -for_each_domain (cpu, tmp) { -if (weight <= tmp->span_weight) -break ; -if (tmp->flags & sd_flag) - sd = tmp; - } -/* while loop will break here if sd == NULL */ + }else { + new_cpu =find_idlest_cpu (sd, p, cpu, prev_cpu, sd_flag); }rcu_read_unlock (); --2.14.1
PATCH v2 2/5 sched/fair: Remove unnecessary comparison with -1
In reply to Brendan JackmanSince commit 83a0a96a5f26 ("sched/fair: Leverage the idle state info when choosing the "idlest" cpu") find_idlest_grou_cpu (formerly find_idlest_cpu) no longer returns -1.
--- kernel/sched/fair.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/sched/fair.c +1 -1
@@ -5583,7 +5583,7 @@ static inline int find_idlest_cpu(struct sched_domain *sd, struct task_struct *p } new_cpu =find_idlest_group_cpu (group, p, cpu); -if (new_cpu ==-1 || new_cpu == cpu) { +if (new_cpu == cpu) {/* Now try balancing at a lower domain level of cpu */ sd = sd->child;continue ;
Signature · 1 line
2.14.1
Re: [PATCH v2 2/5] sched/fair: Remove unnecessary comparison with -1
Quoted 4 lines · Brendan Jackman
Since commit
83a0a96a5f26("sched/fair: Leverage the idle state info when choosing the "idlest" cpu")find_idlest_grou_cpu(formerlyfind_idlest_cpu) no longer returns -1.
Thanks,
Josef
Re: [PATCH v2 2/5] sched/fair: Remove unnecessary comparison with -1
In reply to Brendan JackmanQuoted 11 lines · Brendan Jackman
Since commit
83a0a96a5f26("sched/fair: Leverage the idle state info when choosing the "idlest" cpu")find_idlest_grou_cpu(formerlyfind_idlest_cpu) no longer returns -1.Signed-off-by Brendan Jackman <[email protected]>Cc Dietmar Eggemann <[email protected]>Cc Vincent Guittot <[email protected]>Cc Josef Bacik <[email protected]>Cc Ingo Molnar <[email protected]>Cc Morten Rasmussen <[email protected]>Cc Peter Zijlstra <[email protected]>
Quoted 20 lines
--- kernel/sched/fair.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)kernel/sched/fair.c +1
-2@@ -5583,7 +5583,7 @@ static inline int find_idlest_cpu(struct sched_domain *sd, struct task_struct *p } new_cpu =find_idlest_group_cpu (group, p, cpu); -if (new_cpu ==-1 || new_cpu == cpu) { +if (new_cpu == cpu) {/* Now try balancing at a lower domain level of cpu */ sd = sd->child;continue ; --2.14.1
PATCH v2 3/5 sched/fair: Fix find_idlest_group when local group is not allowed
In reply to Brendan JackmanWhen the local group is not allowed we do not modify this_*_load from their initial value of 0. That means that the load checks at the end of find_idlest_group cause us to incorrectly return NULL. Fixing the initial values to ULONG_MAX means we will instead return the idlest remote group in that case.
--- kernel/sched/fair.c | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-)
kernel/sched/fair.c +3 -2
@@ -5387,8 +5387,9 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p, {struct sched_group *idlest =NULL , *group = sd->groups;struct sched_group *most_spare_sg =NULL ; -unsigned long min_runnable_load =ULONG_MAX , this_runnable_load =0 ; -unsigned long min_avg_load =ULONG_MAX , this_avg_load =0 ; +unsigned long min_runnable_load =ULONG_MAX ; +unsigned long this_runnable_load =ULONG_MAX ; +unsigned long min_avg_load =ULONG_MAX , this_avg_load =ULONG_MAX ;unsigned long most_spare =0 , this_spare =0 ;int load_idx = sd->forkexec_idx;int imbalance_scale =100 + (sd->imbalance_pct-100 )/2 ;
Signature · 1 line
2.14.1
Re: [PATCH v2 3/5] sched/fair: Fix find_idlest_group when local group is not allowed
Quoted 6 lines · Brendan Jackman
When the local group is not allowed we do not modify this_*_load from their initial value of 0. That means that the load checks at the end of
find_idlest_groupcause us to incorrectly return NULL. Fixing the initial values toULONG_MAXmeans we will instead return the idlest remote group in that case.
Quoted 7 lines
Signed-off-by Brendan Jackman <[email protected]>Cc Dietmar Eggemann <[email protected]>Cc Vincent Guittot <[email protected]>Cc Josef Bacik <[email protected]>Cc Ingo Molnar <[email protected]>Cc Morten Rasmussen <[email protected]>Cc Peter Zijlstra <[email protected]>
Quoted 23 lines
--- kernel/sched/fair.c | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-)kernel/sched/fair.c +3
-3@@ -5387,8 +5387,9 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p, {struct sched_group *idlest =NULL , *group = sd->groups;struct sched_group *most_spare_sg =NULL ; -unsigned long min_runnable_load =ULONG_MAX , this_runnable_load =0 ; -unsigned long min_avg_load =ULONG_MAX , this_avg_load =0 ; +unsigned long min_runnable_load =ULONG_MAX ; +unsigned long this_runnable_load =ULONG_MAX ; +unsigned long min_avg_load =ULONG_MAX , this_avg_load =ULONG_MAX ;unsigned long most_spare =0 , this_spare =0 ;int load_idx = sd->forkexec_idx;int imbalance_scale =100 + (sd->imbalance_pct-100 )/2 ; --2.14.1
PATCH v2 4/5 sched/fair: Fix use of find_idlest_group when no groups are allowed
In reply to Brendan JackmanWhen p is allowed on none of the CPUs in the sched_domain, we currently return NULL from find_idlest_group, and pointlessly continue the search on lower sched_domain levels (where p is also not allowed) before returning prev_cpu regardless (as we have not updated new_cpu).
Add an explicit check for this case, and a comment to find_idlest_group. Now when find_idlest_group returns NULL, it always means that the local group is allowed and idlest.
--- kernel/sched/fair.c | 5 +++++ 1 file changed, 5 insertions(+)
kernel/sched/fair.c +5 -0
@@ -5380,6 +5380,8 @@ static unsigned long capacity_spare_wake(int cpu, struct task_struct *p)/* * find_idlest_group finds and returns the least busy CPU group within the * domain. +* +* Assumes p is allowed on at least one CPU in sd. */ static struct sched_group * find_idlest_group(struct sched_domain *sd, struct task_struct *p,
@@ -5567,6 +5569,9 @@ static inline int find_idlest_cpu(struct sched_domain *sd, struct task_struct *p {int new_cpu = prev_cpu; +if (!cpumask_intersects (sched_domain_span (sd), &p->cpus_allowed)) +return prev_cpu; +while (sd) {struct sched_group *group;struct sched_domain *tmp;
Signature · 1 line
2.14.1
Re: [PATCH v2 4/5] sched/fair: Fix use of find_idlest_group when no groups are allowed
Quoted 10 lines · Brendan Jackman
When p is allowed on none of the CPUs in the
sched_domain, we currently return NULL fromfind_idlest_group, and pointlessly continue the search on lowersched_domainlevels (where p is also not allowed) before returningprev_cpuregardless (as we have not updatednew_cpu).Add an explicit check for this case, and a comment to
find_idlest_group. Now whenfind_idlest_groupreturns NULL, it always means that the local group is allowed and idlest.
Quoted 7 lines
Signed-off-by Brendan Jackman <[email protected]>Cc Dietmar Eggemann <[email protected]>Cc Vincent Guittot <[email protected]>Cc Josef Bacik <[email protected]>Cc Ingo Molnar <[email protected]>Cc Morten Rasmussen <[email protected]>Cc Peter Zijlstra <[email protected]>
Quoted 30 lines
--- kernel/sched/fair.c | 5 +++++ 1 file changed, 5 insertions(+)kernel/sched/fair.c +5
-1@@ -5380,6 +5380,8 @@ static unsigned long capacity_spare_wake(int cpu, struct task_struct *p)/* * find_idlest_group finds and returns the least busy CPU group within the * domain. +* +* Assumes p is allowed on at least one CPU in sd. */ static struct sched_group * find_idlest_group(struct sched_domain *sd, struct task_struct *p,@@ -5567,6 +5569,9 @@ static inline int find_idlest_cpu(struct sched_domain *sd, struct task_struct *p {int new_cpu = prev_cpu; +if (!cpumask_intersects (sched_domain_span (sd), &p->cpus_allowed)) +return prev_cpu; +while (sd) {struct sched_group *group;struct sched_domain *tmp; --2.14.1
PATCH v2 5/5 sched/fair: Fix use of find_idlest_group when local group is idlest.
In reply to Brendan Jackmanfind_idlest_group currently returns NULL when the local group is idlest. The caller then continues the find_idlest_group search at a lower level of the current CPU's sched_domain hierarchy. However find_idlest_group_cpu is not consulted and, crucially, @new_cpu is not updated. This means the search is pointless and we return @prev_cpu from select_task_rq_fair.
This patch makes find_idlest_group return the idlest group, and never NULL, and then has the caller unconditionally continue to consult find_idlest_group_cpu and update @new_cpu.
* * *
An alternative, simpler, fix for this would be to initialize @new_cpu to @cpu instead of @prev_cpu, at the beginning of the new find_idlest_cpu. However this would not fix the fact that find_idlest_group_cpu goes unused, and we miss out on the bias toward a shallower-idle CPU, unless find_idlest_group picks a non-local group.
If that alternative solution was preferred, then some code could be removed in recognition of the fact that when find_idlest_group_cpu was called, @cpu would never be a member of @group (because @group would be a non-local group, and since @sd is derived from @cpu, @cpu would always be in @sd's local group).
--- kernel/sched/fair.c | 29 ++++++++++------------------- 1 file changed, 10 insertions(+), 19 deletions(-)
kernel/sched/fair.c +10 -19
@@ -5384,11 +5384,10 @@ static unsigned long capacity_spare_wake(int cpu, struct task_struct *p)* Assumes p is allowed on at least one CPU in sd. */ static struct sched_group * -find_idlest_group (struct sched_domain *sd,struct task_struct *p, -int this_cpu,int sd_flag) +find_idlest_group (struct sched_domain *sd,struct task_struct *p,int sd_flag) { -struct sched_group *idlest =NULL , *group = sd->groups; -struct sched_group *most_spare_sg =NULL ; +struct sched_group *group = sd->groups, *local_group = sd->groups; +struct sched_group *idlest =NULL , *most_spare_sg =NULL ;unsigned long min_runnable_load =ULONG_MAX ;unsigned long this_runnable_load =ULONG_MAX ;unsigned long min_avg_load =ULONG_MAX , this_avg_load =ULONG_MAX ;
@@ -5404,7 +5403,6 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p, do { unsigned long load, avg_load, runnable_load; unsigned long spare_cap, max_spare_cap; - int local_group; int i; /* Skip over this group if it has no CPUs allowed */
@@ -5412,9 +5410,6 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p, &p->cpus_allowed))continue ; - local_group =cpumask_test_cpu (this_cpu, -sched_group_span (group)); -/* * Tally up the load of all CPUs in the group and find * the group containing the CPU with most spare capacity.
@@ -5425,7 +5420,7 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p,for_each_cpu (i,sched_group_span (group)) {/* Bias balancing toward cpus of our domain */ -if (local_group) +if (group == local_group) load =source_load (i, load_idx);else load =target_load (i, load_idx);
@@ -5446,7 +5441,7 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p, runnable_load = (runnable_load *SCHED_CAPACITY_SCALE ) / group->sgc->capacity; -if (local_group) { +if (group == local_group) { this_runnable_load = runnable_load; this_avg_load = avg_load; this_spare = max_spare_cap;
@@ -5492,21 +5487,21 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p,if (this_spare >task_util (p) /2 && imbalance_scale*this_spare >100 *most_spare) -return NULL ; +return local_group;if (most_spare >task_util (p) /2 )return most_spare_sg; skip_spare:if (!idlest) -return NULL ; +return local_group;if (min_runnable_load > (this_runnable_load + imbalance)) -return NULL ; +return local_group;if ((this_runnable_load < (min_runnable_load + imbalance)) && (100 *this_avg_load < imbalance_scale*min_avg_load)) -return NULL ; +return local_group;return idlest; }
@@ -5582,11 +5577,7 @@ static inline int find_idlest_cpu(struct sched_domain *sd, struct task_struct *pcontinue ; } - group =find_idlest_group (sd, p, cpu, sd_flag); -if (!group) { - sd = sd->child; -continue ; - } + group =find_idlest_group (sd, p, sd_flag); new_cpu =find_idlest_group_cpu (group, p, cpu);if (new_cpu == cpu) {
--
2.14.1
Vincent Guittot
maintainerRe: [PATCH v2 5/5] sched/fair: Fix use of find_idlest_group when local group is idlest.
Quoted 11 lines · Brendan Jackman
find_idlest_groupcurrently returns NULL when the local group is idlest. The caller then continues thefind_idlest_groupsearch at a lower level of the current CPU'ssched_domainhierarchy. Howeverfind_idlest_group_cpuis not consulted and, crucially, @new_cpu is not updated. This means the search is pointless and we return @prev_cpu fromselect_task_rq_fair.This patch makes
find_idlest_groupreturn the idlest group, and never NULL, and then has the caller unconditionally continue to consultfind_idlest_group_cpuand update @new_cpu.
Quoted 5 lines
* * *
An alternative, simpler, fix for this would be to initialize @new_cpu to @cpu instead of @prev_cpu, at the beginning of the new
find_idlest_cpu. However this would not fix the fact that
Yes this is simpler
Quoted 3 lines
find_idlest_group_cpugoes unused, and we miss out on the bias toward a shallower-idle CPU, unlessfind_idlest_grouppicks a non-local group.
I'm not sure to catch why it's not enough.
If no cpu of sched_domain span is allowed, we continue to return prev_cpu But if at least 1 cpu is allowed, the default new_cpu is cpu in case it is really the idlest and no other group will be returned by find_idlest_group
Otherwise, find_idlest_group will finally return another group than the local one when running with sd->child
Is there sched_domain topology where the sched_group of lowest level is not with only 1 cpu ?
Quoted 115 lines
If that alternative solution was preferred, then some code could be removed in recognition of the fact that when
find_idlest_group_cpuwas called, @cpu would never be a member of @group (because @group would be a non-local group, and since @sd is derived from @cpu, @cpu would always be in @sd's local group).Signed-off-by Brendan Jackman <[email protected]>Cc Dietmar Eggemann <[email protected]>Cc Vincent Guittot <[email protected]>Cc Josef Bacik <[email protected]>Cc Ingo Molnar <[email protected]>Cc Morten Rasmussen <[email protected]>Cc Peter Zijlstra <[email protected]>--- kernel/sched/fair.c | 29 ++++++++++------------------- 1 file changed, 10 insertions(+), 19 deletions(-)kernel/sched/fair.c +10
-20@@ -5384,11 +5384,10 @@ static unsigned long capacity_spare_wake(int cpu, struct task_struct *p)* Assumes p is allowed on at least one CPU in sd. */ static struct sched_group * -find_idlest_group (struct sched_domain *sd,struct task_struct *p, -int this_cpu,int sd_flag) +find_idlest_group (struct sched_domain *sd,struct task_struct *p,int sd_flag) { -struct sched_group *idlest =NULL , *group = sd->groups; -struct sched_group *most_spare_sg =NULL ; +struct sched_group *group = sd->groups, *local_group = sd->groups; +struct sched_group *idlest =NULL , *most_spare_sg =NULL ;unsigned long min_runnable_load =ULONG_MAX ;unsigned long this_runnable_load =ULONG_MAX ;unsigned long min_avg_load =ULONG_MAX , this_avg_load =ULONG_MAX ;@@ -5404,7 +5403,6 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p, do { unsigned long load, avg_load, runnable_load; unsigned long spare_cap, max_spare_cap; - int local_group; int i; /* Skip over this group if it has no CPUs allowed */@@ -5412,9 +5410,6 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p, &p->cpus_allowed))continue ; - local_group =cpumask_test_cpu (this_cpu, -sched_group_span (group)); -/* * Tally up the load of all CPUs in the group and find * the group containing the CPU with most spare capacity. @@ -5425,7 +5420,7 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p,for_each_cpu (i,sched_group_span (group)) {/* Bias balancing toward cpus of our domain */ -if (local_group) +if (group == local_group) load =source_load (i, load_idx);else load =target_load (i, load_idx);@@ -5446,7 +5441,7 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p, runnable_load = (runnable_load *SCHED_CAPACITY_SCALE ) / group->sgc->capacity; -if (local_group) { +if (group == local_group) { this_runnable_load = runnable_load; this_avg_load = avg_load; this_spare = max_spare_cap;@@ -5492,21 +5487,21 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p,if (this_spare >task_util (p) /2 && imbalance_scale*this_spare >100 *most_spare) -return NULL ; +return local_group;if (most_spare >task_util (p) /2 )return most_spare_sg; skip_spare:if (!idlest) -return NULL ; +return local_group;if (min_runnable_load > (this_runnable_load + imbalance)) -return NULL ; +return local_group;if ((this_runnable_load < (min_runnable_load + imbalance)) && (100 *this_avg_load < imbalance_scale*min_avg_load)) -return NULL ; +return local_group;return idlest; }@@ -5582,11 +5577,7 @@ static inline int find_idlest_cpu(struct sched_domain *sd, struct task_struct *pcontinue ; } - group =find_idlest_group (sd, p, cpu, sd_flag); -if (!group) { - sd = sd->child; -continue ; - } + group =find_idlest_group (sd, p, sd_flag); new_cpu =find_idlest_group_cpu (group, p, cpu);if (new_cpu == cpu) { --2.14.1
Re: [PATCH v2 5/5] sched/fair: Fix use of find_idlest_group when local group is idlest.
Quoted 24 lines · Vincent Guittot
Quoted 11 lines · Brendan Jackman
find_idlest_groupcurrently returns NULL when the local group is idlest. The caller then continues thefind_idlest_groupsearch at a lower level of the current CPU'ssched_domainhierarchy. Howeverfind_idlest_group_cpuis not consulted and, crucially, @new_cpu is not updated. This means the search is pointless and we return @prev_cpu fromselect_task_rq_fair.This patch makes
find_idlest_groupreturn the idlest group, and never NULL, and then has the caller unconditionally continue to consultfind_idlest_group_cpuand update @new_cpu.Quoted 5 lines
* * *
An alternative, simpler, fix for this would be to initialize @new_cpu to @cpu instead of @prev_cpu, at the beginning of the new
find_idlest_cpu. However this would not fix the fact thatYes this is simpler
Quoted 3 lines
find_idlest_group_cpugoes unused, and we miss out on the bias toward a shallower-idle CPU, unlessfind_idlest_grouppicks a non-local group.
Quoted 7 lines
I'm not sure to catch why it's not enough.
If no cpu ofsched_domainspan is allowed, we continue to returnprev_cpuBut if at least 1 cpu is allowed, the defaultnew_cpuis cpu in case it is really the idlest and no other group will be returned byfind_idlest_group
Otherwise,find_idlest_groupwill finally return another group than the local one when running withsd->child
This patch isn't about affinity but just about which group is idlest.
Consider a 4 CPU system with 2 shared caches where CPU0's sched_domains look like:
DIE: [0 1][2 3]
MC: [0][1]
Suppose CPUs 0 and 1 are equally idle wrt load and util, but CPU1 is in a shallower idle state. Suppose all CPUs are allowed.
Assuming @cpu is 0, on the first iteration, find_idlest_group (fig) will currently return NULL meaning [0 1], then on the second iteration it will return NULL meaning [0].
With this patch, on the first iteration fig will return [0 1], then find_idlest_group_cpu (figc) will return 1. Then on the second iteration, fig should return [1] (because it is biased towards the local group i.e. [@cpu] i.e. [1]). This is better because CPU1 is in a shallower idle state.
So basically we're currently missing out on the biasing in figc, unless we at some point return a non-local group.
Does that make sense?
Quoted 119 lines
Is there
sched_domaintopology where thesched_groupof lowest level is not with only 1 cpu ?Quoted 115 lines
If that alternative solution was preferred, then some code could be removed in recognition of the fact that when
find_idlest_group_cpuwas called, @cpu would never be a member of @group (because @group would be a non-local group, and since @sd is derived from @cpu, @cpu would always be in @sd's local group).Signed-off-by Brendan Jackman <[email protected]>Cc Dietmar Eggemann <[email protected]>Cc Vincent Guittot <[email protected]>Cc Josef Bacik <[email protected]>Cc Ingo Molnar <[email protected]>Cc Morten Rasmussen <[email protected]>Cc Peter Zijlstra <[email protected]>--- kernel/sched/fair.c | 29 ++++++++++------------------- 1 file changed, 10 insertions(+), 19 deletions(-)kernel/sched/fair.c +10
-20@@ -5384,11 +5384,10 @@ static unsigned long capacity_spare_wake(int cpu, struct task_struct *p)* Assumes p is allowed on at least one CPU in sd. */ static struct sched_group * -find_idlest_group (struct sched_domain *sd,struct task_struct *p, -int this_cpu,int sd_flag) +find_idlest_group (struct sched_domain *sd,struct task_struct *p,int sd_flag) { -struct sched_group *idlest =NULL , *group = sd->groups; -struct sched_group *most_spare_sg =NULL ; +struct sched_group *group = sd->groups, *local_group = sd->groups; +struct sched_group *idlest =NULL , *most_spare_sg =NULL ;unsigned long min_runnable_load =ULONG_MAX ;unsigned long this_runnable_load =ULONG_MAX ;unsigned long min_avg_load =ULONG_MAX , this_avg_load =ULONG_MAX ;@@ -5404,7 +5403,6 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p, do { unsigned long load, avg_load, runnable_load; unsigned long spare_cap, max_spare_cap; - int local_group; int i; /* Skip over this group if it has no CPUs allowed */@@ -5412,9 +5410,6 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p, &p->cpus_allowed))continue ; - local_group =cpumask_test_cpu (this_cpu, -sched_group_span (group)); -/* * Tally up the load of all CPUs in the group and find * the group containing the CPU with most spare capacity. @@ -5425,7 +5420,7 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p,for_each_cpu (i,sched_group_span (group)) {/* Bias balancing toward cpus of our domain */ -if (local_group) +if (group == local_group) load =source_load (i, load_idx);else load =target_load (i, load_idx);@@ -5446,7 +5441,7 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p, runnable_load = (runnable_load *SCHED_CAPACITY_SCALE ) / group->sgc->capacity; -if (local_group) { +if (group == local_group) { this_runnable_load = runnable_load; this_avg_load = avg_load; this_spare = max_spare_cap;@@ -5492,21 +5487,21 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p,if (this_spare >task_util (p) /2 && imbalance_scale*this_spare >100 *most_spare) -return NULL ; +return local_group;if (most_spare >task_util (p) /2 )return most_spare_sg; skip_spare:if (!idlest) -return NULL ; +return local_group;if (min_runnable_load > (this_runnable_load + imbalance)) -return NULL ; +return local_group;if ((this_runnable_load < (min_runnable_load + imbalance)) && (100 *this_avg_load < imbalance_scale*min_avg_load)) -return NULL ; +return local_group;return idlest; }@@ -5582,11 +5577,7 @@ static inline int find_idlest_cpu(struct sched_domain *sd, struct task_struct *pcontinue ; } - group =find_idlest_group (sd, p, cpu, sd_flag); -if (!group) { - sd = sd->child; -continue ; - } + group =find_idlest_group (sd, p, sd_flag); new_cpu =find_idlest_group_cpu (group, p, cpu);if (new_cpu == cpu) { --2.14.1
Vincent Guittot
maintainerRe: [PATCH v2 5/5] sched/fair: Fix use of find_idlest_group when local group is idlest.
Quoted 34 lines · Brendan Jackman
Quoted 24 lines · Vincent Guittot
Quoted 11 lines · Brendan Jackman
find_idlest_groupcurrently returns NULL when the local group is idlest. The caller then continues thefind_idlest_groupsearch at a lower level of the current CPU'ssched_domainhierarchy. Howeverfind_idlest_group_cpuis not consulted and, crucially, @new_cpu is not updated. This means the search is pointless and we return @prev_cpu fromselect_task_rq_fair.This patch makes
find_idlest_groupreturn the idlest group, and never NULL, and then has the caller unconditionally continue to consultfind_idlest_group_cpuand update @new_cpu.Quoted 5 lines
* * *
An alternative, simpler, fix for this would be to initialize @new_cpu to @cpu instead of @prev_cpu, at the beginning of the new
find_idlest_cpu. However this would not fix the fact thatYes this is simpler
Quoted 3 lines
find_idlest_group_cpugoes unused, and we miss out on the bias toward a shallower-idle CPU, unlessfind_idlest_grouppicks a non-local group.Quoted 7 lines
I'm not sure to catch why it's not enough.
If no cpu ofsched_domainspan is allowed, we continue to returnprev_cpuBut if at least 1 cpu is allowed, the defaultnew_cpuis cpu in case it is really the idlest and no other group will be returned byfind_idlest_group
Otherwise,find_idlest_groupwill finally return another group than the local one when running withsd->child
Quoted 1 line
This patch isn't about affinity but just about which group is idlest.
So this patch changes 2 things:
- don't return @prev if @cpu is the idlest one
- always call find_idlest_group_cpu even for local group
The 1st point is a bug but the 2nd one is more a matter of policy. Current implementation favors locality and load/capacity over current idle state of CPU which is only used at a last resort to select a cpu. What you are proposing, it's to increase the weight of the current idle state of cpus in the selection of the cpu in order to become sometime higher than the locality of even the load/capacity
Quoted 20 lines
Consider a 4 CPU system with 2 shared caches where CPU0's
sched_domainslook like:DIE: [0 1][2 3]
MC: [0][1]Suppose CPUs 0 and 1 are equally idle wrt load and util, but CPU1 is in a shallower idle state. Suppose all CPUs are allowed.
Assuming @cpu is 0, on the first iteration,
find_idlest_group(fig) will currently return NULL meaning [0 1], then on the second iteration it will return NULL meaning [0].With this patch, on the first iteration fig will return [0 1], then
find_idlest_group_cpu(figc) will return 1. Then on the second iteration, fig should return [1] (because it is biased towards the local group i.e. [@cpu] i.e. [1]). This is better because CPU1 is in a shallower idle state.
Quoted 4 lines
So basically we're currently missing out on the biasing in figc, unless we at some point return a non-local group.
Does that make sense?
With your previous example if the load/capacity of CPU0 is significantly lower than CPU1, we will also select CPU1 instead of CPU0:
@cpu is 0.
fig returns local group [0 1]
figc returns 1
@new_cpu != @cpu so we don't go to child
cpu = new cpu
sd = NULL
weight = 4
sd stays null because weight == tmp->span_weight (DIE) we don't loop at lower level
fic returns CPU1
Quoted 121 lines
Quoted 120 lines
Is there
sched_domaintopology where thesched_groupof lowest level is not with only 1 cpu ?Quoted 115 lines
If that alternative solution was preferred, then some code could be removed in recognition of the fact that when
find_idlest_group_cpuwas called, @cpu would never be a member of @group (because @group would be a non-local group, and since @sd is derived from @cpu, @cpu would always be in @sd's local group).Signed-off-by Brendan Jackman <[email protected]>Cc Dietmar Eggemann <[email protected]>Cc Vincent Guittot <[email protected]>Cc Josef Bacik <[email protected]>Cc Ingo Molnar <[email protected]>Cc Morten Rasmussen <[email protected]>Cc Peter Zijlstra <[email protected]>--- kernel/sched/fair.c | 29 ++++++++++------------------- 1 file changed, 10 insertions(+), 19 deletions(-)kernel/sched/fair.c +10
-20@@ -5384,11 +5384,10 @@ static unsigned long capacity_spare_wake(int cpu, struct task_struct *p)* Assumes p is allowed on at least one CPU in sd. */ static struct sched_group * -find_idlest_group (struct sched_domain *sd,struct task_struct *p, -int this_cpu,int sd_flag) +find_idlest_group (struct sched_domain *sd,struct task_struct *p,int sd_flag) { -struct sched_group *idlest =NULL , *group = sd->groups; -struct sched_group *most_spare_sg =NULL ; +struct sched_group *group = sd->groups, *local_group = sd->groups; +struct sched_group *idlest =NULL , *most_spare_sg =NULL ;unsigned long min_runnable_load =ULONG_MAX ;unsigned long this_runnable_load =ULONG_MAX ;unsigned long min_avg_load =ULONG_MAX , this_avg_load =ULONG_MAX ;@@ -5404,7 +5403,6 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p, do { unsigned long load, avg_load, runnable_load; unsigned long spare_cap, max_spare_cap; - int local_group; int i; /* Skip over this group if it has no CPUs allowed */@@ -5412,9 +5410,6 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p, &p->cpus_allowed))continue ; - local_group =cpumask_test_cpu (this_cpu, -sched_group_span (group)); -/* * Tally up the load of all CPUs in the group and find * the group containing the CPU with most spare capacity. @@ -5425,7 +5420,7 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p,for_each_cpu (i,sched_group_span (group)) {/* Bias balancing toward cpus of our domain */ -if (local_group) +if (group == local_group) load =source_load (i, load_idx);else load =target_load (i, load_idx);@@ -5446,7 +5441,7 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p, runnable_load = (runnable_load *SCHED_CAPACITY_SCALE ) / group->sgc->capacity; -if (local_group) { +if (group == local_group) { this_runnable_load = runnable_load; this_avg_load = avg_load; this_spare = max_spare_cap;@@ -5492,21 +5487,21 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p,if (this_spare >task_util (p) /2 && imbalance_scale*this_spare >100 *most_spare) -return NULL ; +return local_group;if (most_spare >task_util (p) /2 )return most_spare_sg; skip_spare:if (!idlest) -return NULL ; +return local_group;if (min_runnable_load > (this_runnable_load + imbalance)) -return NULL ; +return local_group;if ((this_runnable_load < (min_runnable_load + imbalance)) && (100 *this_avg_load < imbalance_scale*min_avg_load)) -return NULL ; +return local_group;return idlest; }@@ -5582,11 +5577,7 @@ static inline int find_idlest_cpu(struct sched_domain *sd, struct task_struct *pcontinue ; } - group =find_idlest_group (sd, p, cpu, sd_flag); -if (!group) { - sd = sd->child; -continue ; - } + group =find_idlest_group (sd, p, sd_flag); new_cpu =find_idlest_group_cpu (group, p, cpu);if (new_cpu == cpu) { --2.14.1
Vincent Guittot
maintainerRe: [PATCH v2 5/5] sched/fair: Fix use of find_idlest_group when local group is idlest.
Quoted 82 lines · Vincent Guittot
Quoted 34 lines · Brendan Jackman
Quoted 24 lines · Vincent Guittot
Quoted 11 lines · Brendan Jackman
find_idlest_groupcurrently returns NULL when the local group is idlest. The caller then continues thefind_idlest_groupsearch at a lower level of the current CPU'ssched_domainhierarchy. Howeverfind_idlest_group_cpuis not consulted and, crucially, @new_cpu is not updated. This means the search is pointless and we return @prev_cpu fromselect_task_rq_fair.This patch makes
find_idlest_groupreturn the idlest group, and never NULL, and then has the caller unconditionally continue to consultfind_idlest_group_cpuand update @new_cpu.Quoted 5 lines
* * *
An alternative, simpler, fix for this would be to initialize @new_cpu to @cpu instead of @prev_cpu, at the beginning of the new
find_idlest_cpu. However this would not fix the fact thatYes this is simpler
Quoted 3 lines
find_idlest_group_cpugoes unused, and we miss out on the bias toward a shallower-idle CPU, unlessfind_idlest_grouppicks a non-local group.Quoted 7 lines
I'm not sure to catch why it's not enough.
If no cpu ofsched_domainspan is allowed, we continue to returnprev_cpuBut if at least 1 cpu is allowed, the defaultnew_cpuis cpu in case it is really the idlest and no other group will be returned byfind_idlest_group
Otherwise,find_idlest_groupwill finally return another group than the local one when running withsd->childQuoted 1 line
This patch isn't about affinity but just about which group is idlest.
So this patch changes 2 things:
- don't return @prev if @cpu is the idlest one
- always callfind_idlest_group_cpueven for local groupThe 1st point is a bug but the 2nd one is more a matter of policy. Current implementation favors locality and load/capacity over current idle state of CPU which is only used at a last resort to select a cpu. What you are proposing, it's to increase the weight of the current idle state of cpus in the selection of the cpu in order to become sometime higher than the locality of even the load/capacity
Quoted 20 lines
Consider a 4 CPU system with 2 shared caches where CPU0's
sched_domainslook like:DIE: [0 1][2 3]
MC: [0][1]Suppose CPUs 0 and 1 are equally idle wrt load and util, but CPU1 is in a shallower idle state. Suppose all CPUs are allowed.
Assuming @cpu is 0, on the first iteration,
find_idlest_group(fig) will currently return NULL meaning [0 1], then on the second iteration it will return NULL meaning [0].With this patch, on the first iteration fig will return [0 1], then
find_idlest_group_cpu(figc) will return 1. Then on the second iteration, fig should return [1] (because it is biased towards the local group i.e. [@cpu] i.e. [1]). This is better because CPU1 is in a shallower idle state.Quoted 4 lines
So basically we're currently missing out on the biasing in figc, unless we at some point return a non-local group.
Does that make sense?
With your previous example if the load/capacity of CPU0 is significantly lower than CPU1, we will also select CPU1 instead of CPU0:
@cpu is 0.
fig returns local group [0 1]
figc returns 1
@new_cpu != @cpu so we don't go to child
Quoted 4 lines
cpu = new cpu
sd = NULL
weight = 4
sd stays null because weight ==tmp->span_weight(DIE)
You can forgot this example, i have mixed the direction of for_each_domain
Quoted 124 lines
we don't loop at lower level
fic returns CPU1Quoted 121 lines
Quoted 120 lines
Is there
sched_domaintopology where thesched_groupof lowest level is not with only 1 cpu ?Quoted 115 lines
If that alternative solution was preferred, then some code could be removed in recognition of the fact that when
find_idlest_group_cpuwas called, @cpu would never be a member of @group (because @group would be a non-local group, and since @sd is derived from @cpu, @cpu would always be in @sd's local group).Signed-off-by Brendan Jackman <[email protected]>Cc Dietmar Eggemann <[email protected]>Cc Vincent Guittot <[email protected]>Cc Josef Bacik <[email protected]>Cc Ingo Molnar <[email protected]>Cc Morten Rasmussen <[email protected]>Cc Peter Zijlstra <[email protected]>--- kernel/sched/fair.c | 29 ++++++++++------------------- 1 file changed, 10 insertions(+), 19 deletions(-)kernel/sched/fair.c +10
-20@@ -5384,11 +5384,10 @@ static unsigned long capacity_spare_wake(int cpu, struct task_struct *p)* Assumes p is allowed on at least one CPU in sd. */ static struct sched_group * -find_idlest_group (struct sched_domain *sd,struct task_struct *p, -int this_cpu,int sd_flag) +find_idlest_group (struct sched_domain *sd,struct task_struct *p,int sd_flag) { -struct sched_group *idlest =NULL , *group = sd->groups; -struct sched_group *most_spare_sg =NULL ; +struct sched_group *group = sd->groups, *local_group = sd->groups; +struct sched_group *idlest =NULL , *most_spare_sg =NULL ;unsigned long min_runnable_load =ULONG_MAX ;unsigned long this_runnable_load =ULONG_MAX ;unsigned long min_avg_load =ULONG_MAX , this_avg_load =ULONG_MAX ;@@ -5404,7 +5403,6 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p, do { unsigned long load, avg_load, runnable_load; unsigned long spare_cap, max_spare_cap; - int local_group; int i; /* Skip over this group if it has no CPUs allowed */@@ -5412,9 +5410,6 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p, &p->cpus_allowed))continue ; - local_group =cpumask_test_cpu (this_cpu, -sched_group_span (group)); -/* * Tally up the load of all CPUs in the group and find * the group containing the CPU with most spare capacity. @@ -5425,7 +5420,7 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p,for_each_cpu (i,sched_group_span (group)) {/* Bias balancing toward cpus of our domain */ -if (local_group) +if (group == local_group) load =source_load (i, load_idx);else load =target_load (i, load_idx);@@ -5446,7 +5441,7 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p, runnable_load = (runnable_load *SCHED_CAPACITY_SCALE ) / group->sgc->capacity; -if (local_group) { +if (group == local_group) { this_runnable_load = runnable_load; this_avg_load = avg_load; this_spare = max_spare_cap;@@ -5492,21 +5487,21 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p,if (this_spare >task_util (p) /2 && imbalance_scale*this_spare >100 *most_spare) -return NULL ; +return local_group;if (most_spare >task_util (p) /2 )return most_spare_sg; skip_spare:if (!idlest) -return NULL ; +return local_group;if (min_runnable_load > (this_runnable_load + imbalance)) -return NULL ; +return local_group;if ((this_runnable_load < (min_runnable_load + imbalance)) && (100 *this_avg_load < imbalance_scale*min_avg_load)) -return NULL ; +return local_group;return idlest; }@@ -5582,11 +5577,7 @@ static inline int find_idlest_cpu(struct sched_domain *sd, struct task_struct *pcontinue ; } - group =find_idlest_group (sd, p, cpu, sd_flag); -if (!group) { - sd = sd->child; -continue ; - } + group =find_idlest_group (sd, p, sd_flag); new_cpu =find_idlest_group_cpu (group, p, cpu);if (new_cpu == cpu) { --2.14.1
Re: [PATCH v2 5/5] sched/fair: Fix use of find_idlest_group when local group is idlest.
In reply to Vincent GuittotQuoted 35 lines · Vincent Guittot
Quoted 34 lines · Brendan Jackman
Quoted 31 lines · Vincent Guittot
Quoted 11 lines · Brendan Jackman
find_idlest_groupcurrently returns NULL when the local group is idlest. The caller then continues thefind_idlest_groupsearch at a lower level of the current CPU'ssched_domainhierarchy. Howeverfind_idlest_group_cpuis not consulted and, crucially, @new_cpu is not updated. This means the search is pointless and we return @prev_cpu fromselect_task_rq_fair.This patch makes
find_idlest_groupreturn the idlest group, and never NULL, and then has the caller unconditionally continue to consultfind_idlest_group_cpuand update @new_cpu.Quoted 5 lines
* * *
An alternative, simpler, fix for this would be to initialize @new_cpu to @cpu instead of @prev_cpu, at the beginning of the new
find_idlest_cpu. However this would not fix the fact thatYes this is simpler
Quoted 3 lines
find_idlest_group_cpugoes unused, and we miss out on the bias toward a shallower-idle CPU, unlessfind_idlest_grouppicks a non-local group.I'm not sure to catch why it's not enough.
If no cpu ofsched_domainspan is allowed, we continue to returnprev_cpuBut if at least 1 cpu is allowed, the defaultnew_cpuis cpu in case it is really the idlest and no other group will be returned byfind_idlest_group
Otherwise,find_idlest_groupwill finally return another group than the local one when running withsd->child
Quoted 7 lines
Quoted 1 line
This patch isn't about affinity but just about which group is idlest.
So this patch changes 2 things:
- don't return @prev if @cpu is the idlest one
- always callfind_idlest_group_cpueven for local groupThe 1st point is a bug but the 2nd one is more a matter of policy.
I didn't see it this way before but yes I suppose you're right.
Quoted 5 lines
Current implementation favors locality and load/capacity over current idle state of CPU which is only used at a last resort to select a cpu. What you are proposing, it's to increase the weight of the current idle state of cpus in the selection of the cpu in order to become sometime higher than the locality of even the load/capacity
Well, not just increase the weight, more give it a weight that is consistent whether or not find_idlest_group ever returns a non-local group.
OK, so I'll spin a v3 that just fixes the bug and doesn't change the policy wrt. using idle states.
Thanks a lot for this review.
Quoted 163 lines
Quoted 21 lines
Consider a 4 CPU system with 2 shared caches where CPU0's
sched_domainslook like:DIE: [0 1][2 3]
MC: [0][1]Suppose CPUs 0 and 1 are equally idle wrt load and util, but CPU1 is in a shallower idle state. Suppose all CPUs are allowed.
Assuming @cpu is 0, on the first iteration,
find_idlest_group(fig) will currently return NULL meaning [0 1], then on the second iteration it will return NULL meaning [0].With this patch, on the first iteration fig will return [0 1], then
find_idlest_group_cpu(figc) will return 1. Then on the second iteration, fig should return [1] (because it is biased towards the local group i.e. [@cpu] i.e. [1]). This is better because CPU1 is in a shallower idle state.Quoted 4 lines
So basically we're currently missing out on the biasing in figc, unless we at some point return a non-local group.
Does that make sense?
With your previous example if the load/capacity of CPU0 is significantly lower than CPU1, we will also select CPU1 instead of CPU0:
@cpu is 0.
fig returns local group [0 1]
figc returns 1
@new_cpu != @cpu so we don't go to childcpu = new cpu
sd = NULL
weight = 4
sd stays null because weight ==tmp->span_weight(DIE) we don't loop at lower level
fic returns CPU1Quoted 121 lines
Quoted 120 lines
Is there
sched_domaintopology where thesched_groupof lowest level is not with only 1 cpu ?Quoted 115 lines
If that alternative solution was preferred, then some code could be removed in recognition of the fact that when
find_idlest_group_cpuwas called, @cpu would never be a member of @group (because @group would be a non-local group, and since @sd is derived from @cpu, @cpu would always be in @sd's local group).Signed-off-by Brendan Jackman <[email protected]>Cc Dietmar Eggemann <[email protected]>Cc Vincent Guittot <[email protected]>Cc Josef Bacik <[email protected]>Cc Ingo Molnar <[email protected]>Cc Morten Rasmussen <[email protected]>Cc Peter Zijlstra <[email protected]>--- kernel/sched/fair.c | 29 ++++++++++------------------- 1 file changed, 10 insertions(+), 19 deletions(-)kernel/sched/fair.c +10
-20@@ -5384,11 +5384,10 @@ static unsigned long capacity_spare_wake(int cpu, struct task_struct *p)* Assumes p is allowed on at least one CPU in sd. */ static struct sched_group * -find_idlest_group (struct sched_domain *sd,struct task_struct *p, -int this_cpu,int sd_flag) +find_idlest_group (struct sched_domain *sd,struct task_struct *p,int sd_flag) { -struct sched_group *idlest =NULL , *group = sd->groups; -struct sched_group *most_spare_sg =NULL ; +struct sched_group *group = sd->groups, *local_group = sd->groups; +struct sched_group *idlest =NULL , *most_spare_sg =NULL ;unsigned long min_runnable_load =ULONG_MAX ;unsigned long this_runnable_load =ULONG_MAX ;unsigned long min_avg_load =ULONG_MAX , this_avg_load =ULONG_MAX ;@@ -5404,7 +5403,6 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p, do { unsigned long load, avg_load, runnable_load; unsigned long spare_cap, max_spare_cap; - int local_group; int i; /* Skip over this group if it has no CPUs allowed */@@ -5412,9 +5410,6 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p, &p->cpus_allowed))continue ; - local_group =cpumask_test_cpu (this_cpu, -sched_group_span (group)); -/* * Tally up the load of all CPUs in the group and find * the group containing the CPU with most spare capacity. @@ -5425,7 +5420,7 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p,for_each_cpu (i,sched_group_span (group)) {/* Bias balancing toward cpus of our domain */ -if (local_group) +if (group == local_group) load =source_load (i, load_idx);else load =target_load (i, load_idx);@@ -5446,7 +5441,7 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p, runnable_load = (runnable_load *SCHED_CAPACITY_SCALE ) / group->sgc->capacity; -if (local_group) { +if (group == local_group) { this_runnable_load = runnable_load; this_avg_load = avg_load; this_spare = max_spare_cap;@@ -5492,21 +5487,21 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p,if (this_spare >task_util (p) /2 && imbalance_scale*this_spare >100 *most_spare) -return NULL ; +return local_group;if (most_spare >task_util (p) /2 )return most_spare_sg; skip_spare:if (!idlest) -return NULL ; +return local_group;if (min_runnable_load > (this_runnable_load + imbalance)) -return NULL ; +return local_group;if ((this_runnable_load < (min_runnable_load + imbalance)) && (100 *this_avg_load < imbalance_scale*min_avg_load)) -return NULL ; +return local_group;return idlest; }@@ -5582,11 +5577,7 @@ static inline int find_idlest_cpu(struct sched_domain *sd, struct task_struct *pcontinue ; } - group =find_idlest_group (sd, p, cpu, sd_flag); -if (!group) { - sd = sd->child; -continue ; - } + group =find_idlest_group (sd, p, sd_flag); new_cpu =find_idlest_group_cpu (group, p, cpu);if (new_cpu == cpu) { --2.14.1