Various load-balance cleanups/optimizations -v2
Peter Zijlstra
maintainercover Various load-balance cleanups/optimizations -v2
After poking at them a little more I feel somewhat more confident.
I found one more bug, but this one was my own fault, we should also clear sds->busiest_stat.avg_load because update_sd_pick_busiest() reads that before we set it.
Moved the memset optimization and the fix for that into a separate patch.
Other than that, there's a sched_domain degenerate fix; and a new way to detect group_imb (which relies on the sched_domain fix).
Peter Zijlstra
maintainerPATCH 1/10 sched: Remove one division operation in find_busiest_queue()
From: Joonsoo Kim <[email protected]>
Remove one division operation in find_busiest_queue() by using crosswise multiplication:
wl_i / power_i > wl_j / power_j := wl_i * power_j > wl_j * power_i
--- kernel/sched/fair.c | 9 ++++----- 1 file changed, 4 insertions(+), 5 deletions(-)
kernel/sched/fair.c +4 -5
@@ -5018,7 +5018,7 @@ static struct rq *find_busiest_queue(str struct sched_group *group) {struct rq *busiest =NULL , *rq; -unsigned long max_load =0 ; +unsigned long busiest_load =0 , busiest_power =SCHED_POWER_SCALE ;int i;for_each_cpu (i,sched_group_cpus (group)) {
@@ -5049,10 +5049,9 @@ static struct rq *find_busiest_queue(str* the load can be moved away from the cpu that is potentially * running at a lower capacity. */ - wl = (wl *SCHED_POWER_SCALE ) / power; - -if (wl > max_load) { - max_load = wl; +if (wl * busiest_power > busiest_load * power) { + busiest_load = wl; + busiest_power = power; busiest = rq; } }
Re: [PATCH 01/10] sched: Remove one division operation in find_busiest_queue()
Quoted 19 lines · Peter Zijlstra
From: Joonsoo Kim <[email protected]>
Remove one division operation in
find_busiest_queue()by using crosswise multiplication:
wl_i/power_i>wl_j/power_j:=
wl_i*power_j>wl_j*power_iSigned-off-by Joonsoo Kim <[email protected]>[peterz: expanded changelog]Signed-off-by Peter Zijlstra <[email protected]>--- kernel/sched/fair.c | 9 ++++----- 1 file changed, 4 insertions(+), 5 deletions(-)
kernel/sched/fair.c static struct rq *find_busiest_queue(str · line 5021
Quoted 5 lines
kernel/sched/fair.c +1
-1@@ -5018,7 +5018,7 @@ static struct rq *find_busiest_queue(str struct sched_group *group) {struct rq *busiest =NULL , *rq; -unsigned long max_load =0 ; +unsigned long busiest_load =0 , busiest_power =SCHED_POWER_SCALE ;
Initializing this to SCHED_POWER_SCALE assigns a meaning that isn't really there. How about just 1?
kernel/sched/fair.c static struct rq *find_busiest_queue(str · line 5055
Quoted 11 lines
kernel/sched/fair.c +0
-4int i;for_each_cpu (i,sched_group_cpus (group)) {@@ -5049,10 +5049,9 @@ static struct rq *find_busiest_queue(str* the load can be moved away from the cpu that is potentially * running at a lower capacity. */ - wl = (wl *SCHED_POWER_SCALE ) / power; - -if (wl > max_load) { - max_load = wl;
A comment wouldn't hurt here.
Quoted 8 lines
kernel/sched/fair.c +3
-0+if (wl * busiest_power > busiest_load * power) { + busiest_load = wl; + busiest_power = power; busiest = rq; } }
Peter Zijlstra
maintainerRe: [PATCH 01/10] sched: Remove one division operation in find_busiest_queue()
Quoted 9 lines · Paul Turner
kernel/sched/fair.c static struct rq *find_busiest_queue(str · line 5021
Quoted 6 lines
wl_i / power_i > wl_j / power_j := wl_i * power_j > wl_j * power_i struct rq *busiest = NULL, *rq;kernel/sched/fair.c +1
-1-unsigned long max_load =0 ; +unsigned long busiest_load =0 , busiest_power =SCHED_POWER_SCALE ;Initializing this to
SCHED_POWER_SCALEassigns a meaning that isn't really there. How about just 1?
Right, 1 works, all we really need is for wl to be > 0.
Quoted 13 lines
kernel/sched/fair.c static struct rq *find_busiest_queue(str · line 5055
Quoted 11 lines
int i; for_each_cpu(i, sched_group_cpus(group)) {kernel/sched/fair.c +0
-4@@ -5049,10 +5049,9 @@ static struct rq *find_busiest_queue(str* the load can be moved away from the cpu that is potentially * running at a lower capacity. */ - wl = (wl *SCHED_POWER_SCALE ) / power; - -if (wl > max_load) { - max_load = wl;A comment wouldn't hurt here.
Agreed, something like so?
/*
* Since we're looking for max(wl_i / power_i) crosswise multiplication
* to rid ourselves of the division works out to:
* wl_i * power_j > wl_j * power_i; where j is our previous maximum. */
Quoted 8 lines
Quoted 8 lines
kernel/sched/fair.c +3
-0+if (wl * busiest_power > busiest_load * power) { + busiest_load = wl; + busiest_power = power; busiest = rq; } }
Peter Zijlstra
maintainerPATCH 2/10 sched: Factor out code to should_we_balance()
In reply to Peter ZijlstraFrom: Joonsoo Kim <[email protected]>
Now checking whether this cpu is appropriate to balance or not is embedded into update_sg_lb_stats() and this checking has no direct relationship to this function. There is not enough reason to place this checking at update_sg_lb_stats(), except saving one iteration for sched_group_cpus.
In this patch, I factor out this checking to should_we_balance() function. And before doing actual work for load_balancing, check whether this cpu is appropriate to balance via should_we_balance(). If this cpu is not a candidate for balancing, it quit the work immediately.
With this change, we can save two memset cost and can expect better compiler optimization.
Below is result of this patch.
* Vanilla *
text data bss dec hex filename 34499 1136 116 35751 8ba7 kernel/sched/fair.o
* Patched *
text data bss dec hex filename 34243 1136 116 35495 8aa7 kernel/sched/fair.o
In addition, rename @balance to @should_balance in order to represent its purpose more clearly.
--- kernel/sched/fair.c | 111 +++++++++++++++++++++++++--------------------------- 1 file changed, 54 insertions(+), 57 deletions(-)
kernel/sched/fair.c +54 -57
@@ -4510,22 +4510,17 @@ fix_small_capacity(struct sched_domain ** @group: sched_group whose statistics are to be updated. * @load_idx: Load index of sched_domain of this_cpu for load calc. * @local_group: Does group contain this_cpu. -* @balance: Should we balance. * @sgs: variable to hold the statistics for this group. */ static inline void update_sg_lb_stats (struct lb_env *env,struct sched_group *group,int load_idx, -int local_group,int *balance,struct sg_lb_stats *sgs) +int local_group,struct sg_lb_stats *sgs) {unsigned long nr_running, max_nr_running, min_nr_running;unsigned long load, max_cpu_load, min_cpu_load; -unsigned int balance_cpu =-1 , first_idle_cpu =0 ;unsigned long avg_load_per_task =0 ;int i; -if (local_group) - balance_cpu =group_balance_cpu (group); -/* Tally up the load of all CPUs in the group */ max_cpu_load =0 ; min_cpu_load = ~0UL ;
@@ -4538,15 +4533,9 @@ static inline void update_sg_lb_stats(st nr_running = rq->nr_running;/* Bias balancing toward cpus of our domain */ -if (local_group) { -if (idle_cpu (i) && !first_idle_cpu && -cpumask_test_cpu (i,sched_group_mask (group))) { - first_idle_cpu =1 ; - balance_cpu = i; - } - +if (local_group) load =target_load (i, load_idx); - }else { +else { load =source_load (i, load_idx);if (load > max_cpu_load) max_cpu_load = load;
@@ -4566,22 +4555,9 @@ static inline void update_sg_lb_stats(st sgs->idle_cpus++; } -/* -* First idle cpu or the first cpu(busiest) in this sched group -* is eligible for doing load balancing at this and above -* domains. In the newly idle case, we will allow all the cpu's -* to do the newly idle load balance. -*/ -if (local_group) { -if (env->idle !=CPU_NEWLY_IDLE ) { -if (balance_cpu != env->dst_cpu) { - *balance =0 ; -return ; - } -update_group_power (env->sd, env->dst_cpu); - }else if (time_after_eq (jiffies, group->sgp->next_update)) -update_group_power (env->sd, env->dst_cpu); - } +if (local_group && (env->idle !=CPU_NEWLY_IDLE || +time_after_eq (jiffies, group->sgp->next_update))) +update_group_power (env->sd, env->dst_cpu);/* Adjust by relative CPU power of the group */ sgs->avg_load = (sgs->group_load*SCHED_POWER_SCALE ) / group->sgp->power;
@@ -4663,7 +4639,7 @@ static bool update_sd_pick_busiest(struc* @sds: variable to hold the statistics for this sched_domain. */ static inline void update_sd_lb_stats (struct lb_env *env, -int *balance,struct sd_lb_stats *sds) +struct sd_lb_stats *sds) {struct sched_domain *child = env->sd->child;struct sched_group *sg = env->sd->groups;
@@ -4680,10 +4656,7 @@ static inline void update_sd_lb_stats(st local_group =cpumask_test_cpu (env->dst_cpu,sched_group_cpus (sg));memset (&sgs,0 ,sizeof (sgs)); -update_sg_lb_stats (env, sg, load_idx, local_group, balance, &sgs); - -if (local_group && !(*balance)) -return ; +update_sg_lb_stats (env, sg, load_idx, local_group, &sgs); sds->total_load += sgs.group_load; sds->total_pwr += sg->sgp->power;
@@ -4916,8 +4889,6 @@ static inline void calculate_imbalance(s* to restore balance. * * @env: The load balancing environment. -* @balance: Pointer to a variable indicating if this_cpu -* is the appropriate cpu to perform load balancing at this_level. * * Return: - The busiest group if imbalance exists. * - If no imbalance and user has opted for power-savings balance,
@@ -4925,7 +4896,7 @@ static inline void calculate_imbalance(s* put to idle by rebalancing its tasks onto our group. */ static struct sched_group * -find_busiest_group (struct lb_env *env,int *balance) +find_busiest_group (struct lb_env *env) {struct sd_lb_stats sds;
@@ -4935,14 +4906,7 @@ find_busiest_group(struct lb_env *env, i* Compute the various statistics relavent for load balancing at * this level. */ -update_sd_lb_stats (env, balance, &sds); - -/* -* this_cpu is not the appropriate cpu to perform load balancing at -* this level. -*/ -if (!(*balance)) - goto ret; +update_sd_lb_stats (env, &sds);if ((env->idle ==CPU_IDLE || env->idle ==CPU_NEWLY_IDLE ) &&check_asym_packing (env, &sds))
@@ -5006,7 +4970,6 @@ find_busiest_group(struct lb_env *env, ireturn sds.busiest; out_balanced: -ret: env->imbalance =0 ;return NULL ; }
@@ -5088,13 +5051,47 @@ static int need_active_balance(struct lbstatic int active_load_balance_cpu_stop (void *data); +static int should_we_balance (struct lb_env *env) +{ +struct sched_group *sg = env->sd->groups; +struct cpumask *sg_cpus, *sg_mask; +int cpu, balance_cpu =-1 ; + +/* +* In the newly idle case, we will allow all the cpu's +* to do the newly idle load balance. +*/ +if (env->idle ==CPU_NEWLY_IDLE ) +return 1 ; + + sg_cpus =sched_group_cpus (sg); + sg_mask =sched_group_mask (sg); +/* Try to find first idle cpu */ +for_each_cpu_and (cpu, sg_cpus, env->cpus) { +if (!cpumask_test_cpu (cpu, sg_mask) || !idle_cpu (cpu)) +continue ; + + balance_cpu = cpu; +break ; + } + +if (balance_cpu ==-1 ) + balance_cpu =group_balance_cpu (sg); + +/* +* First idle cpu or the first cpu(busiest) in this sched group +* is eligible for doing load balancing at this and above domains. +*/ +return balance_cpu != env->dst_cpu; +} +/* * Check this_cpu to ensure it is balanced within domain. Attempt to move * tasks if there is an imbalance. */ static int load_balance (int this_cpu,struct rq *this_rq,struct sched_domain *sd,enum cpu_idle_type idle, -int *balance) +int *should_balance) {int ld_moved, cur_ld_moved, active_balance =0 ;struct sched_group *group;
@@ -5123,12 +5120,11 @@ static int load_balance(int this_cpu, stschedstat_inc (sd, lb_count[idle]); -redo: - group =find_busiest_group (&env, balance); - -if (*balance ==0 ) +if (!(*should_balance =should_we_balance (&env))) goto out_balanced; +redo: + group =find_busiest_group (&env);if (!group) {schedstat_inc (sd, lb_nobusyg[idle]); goto out_balanced;
@@ -5340,7 +5336,7 @@ void idle_balance(int this_cpu, struct rrcu_read_lock ();for_each_domain (this_cpu, sd) {unsigned long interval; -int balance =1 ; +int should_balance;if (!(sd->flags &SD_LOAD_BALANCE ))continue ;
@@ -5348,7 +5344,8 @@ void idle_balance(int this_cpu, struct rif (sd->flags &SD_BALANCE_NEWIDLE ) {/* If we've pulled tasks over stop searching: */ pulled_task =load_balance (this_cpu, this_rq, - sd,CPU_NEWLY_IDLE , &balance); + sd,CPU_NEWLY_IDLE , + &should_balance); } interval =msecs_to_jiffies (sd->balance_interval);
@@ -5586,7 +5583,7 @@ void update_max_interval(void)*/ static void rebalance_domains (int cpu,enum cpu_idle_type idle) { -int balance =1 ; +int should_balance =1 ;struct rq *rq =cpu_rq (cpu);unsigned long interval;struct sched_domain *sd;
@@ -5618,7 +5615,7 @@ static void rebalance_domains(int cpu, e }if (time_after_eq (jiffies, sd->last_balance + interval)) { -if (load_balance (cpu, rq, sd, idle, &balance)) { +if (load_balance (cpu, rq, sd, idle, &should_balance)) {/* * The LBF_SOME_PINNED logic could have changed * env->dst_cpu, so we can't know our idle
@@ -5641,7 +5638,7 @@ static void rebalance_domains(int cpu, e* CPU in our sched group which is doing load balancing more * actively. */ -if (!balance) +if (!should_balance)break ; }rcu_read_unlock ();
Re: [PATCH 02/10] sched: Factor out code to should_we_balance()
Quoted 66 lines · Peter Zijlstra
From: Joonsoo Kim <[email protected]>
Now checking whether this cpu is appropriate to balance or not is embedded into
update_sg_lb_stats()and this checking has no direct relationship to this function. There is not enough reason to place this checking atupdate_sg_lb_stats(), except saving one iteration forsched_group_cpus.In this patch, I factor out this checking to
should_we_balance()function. And before doing actual work forload_balancing, check whether this cpu is appropriate to balance viashould_we_balance(). If this cpu is not a candidate for balancing, it quit the work immediately.With this change, we can save two memset cost and can expect better compiler optimization.
Below is result of this patch.
* Vanilla *
text data bss dec hex filename 34499 1136 116 35751 8ba7 kernel/sched/fair.o* Patched *
text data bss dec hex filename 34243 1136 116 35495 8aa7 kernel/sched/fair.oIn addition, rename @balance to @should_balance in order to represent its purpose more clearly.
Signed-off-by Joonsoo Kim <[email protected]>[peterz: style changes and a fix in should_we_balance() ]Signed-off-by Peter Zijlstra <[email protected]>--- kernel/sched/fair.c | 111 +++++++++++++++++++++++++--------------------------- 1 file changed, 54 insertions(+), 57 deletions(-)kernel/sched/fair.c +1
-6@@ -4510,22 +4510,17 @@ fix_small_capacity(struct sched_domain ** @group: sched_group whose statistics are to be updated. * @load_idx: Load index of sched_domain of this_cpu for load calc. * @local_group: Does group contain this_cpu. -* @balance: Should we balance. * @sgs: variable to hold the statistics for this group. */ static inline void update_sg_lb_stats (struct lb_env *env,struct sched_group *group,int load_idx, -int local_group,int *balance,struct sg_lb_stats *sgs) +int local_group,struct sg_lb_stats *sgs) {unsigned long nr_running, max_nr_running, min_nr_running;unsigned long load, max_cpu_load, min_cpu_load; -unsigned int balance_cpu =-1 , first_idle_cpu =0 ;unsigned long avg_load_per_task =0 ;int i; -if (local_group) - balance_cpu =group_balance_cpu (group); -/* Tally up the load of all CPUs in the group */ max_cpu_load =0 ; min_cpu_load = ~0UL ;@@ -4538,15 +4533,9 @@ static inline void update_sg_lb_stats(st nr_running = rq->nr_running;
kernel/sched/fair.c static inline void update_sg_lb_stats(st · line 4537
Quoted 10 lines
kernel/sched/fair.c +1
-7/* Bias balancing toward cpus of our domain */ -if (local_group) { -if (idle_cpu (i) && !first_idle_cpu && -cpumask_test_cpu (i,sched_group_mask (group))) { - first_idle_cpu =1 ; - balance_cpu = i; - } - +if (local_group) load =target_load (i, load_idx);
Keep the braces here:
if (local_group) {
load = target_load(i, load_idx);
} else {
...Quoted 144 lines
kernel/sched/fair.c +43
-35- }else { +else { load =source_load (i, load_idx);if (load > max_cpu_load) max_cpu_load = load;@@ -4566,22 +4555,9 @@ static inline void update_sg_lb_stats(st sgs->idle_cpus++; } -/* -* First idle cpu or the first cpu(busiest) in this sched group -* is eligible for doing load balancing at this and above -* domains. In the newly idle case, we will allow all the cpu's -* to do the newly idle load balance. -*/ -if (local_group) { -if (env->idle !=CPU_NEWLY_IDLE ) { -if (balance_cpu != env->dst_cpu) { - *balance =0 ; -return ; - } -update_group_power (env->sd, env->dst_cpu); - }else if (time_after_eq (jiffies, group->sgp->next_update)) -update_group_power (env->sd, env->dst_cpu); - } +if (local_group && (env->idle !=CPU_NEWLY_IDLE || +time_after_eq (jiffies, group->sgp->next_update))) +update_group_power (env->sd, env->dst_cpu);/* Adjust by relative CPU power of the group */ sgs->avg_load = (sgs->group_load*SCHED_POWER_SCALE ) / group->sgp->power;@@ -4663,7 +4639,7 @@ static bool update_sd_pick_busiest(struc* @sds: variable to hold the statistics for this sched_domain. */ static inline void update_sd_lb_stats (struct lb_env *env, -int *balance,struct sd_lb_stats *sds) +struct sd_lb_stats *sds) {struct sched_domain *child = env->sd->child;struct sched_group *sg = env->sd->groups;@@ -4680,10 +4656,7 @@ static inline void update_sd_lb_stats(st local_group =cpumask_test_cpu (env->dst_cpu,sched_group_cpus (sg));memset (&sgs,0 ,sizeof (sgs)); -update_sg_lb_stats (env, sg, load_idx, local_group, balance, &sgs); - -if (local_group && !(*balance)) -return ; +update_sg_lb_stats (env, sg, load_idx, local_group, &sgs); sds->total_load += sgs.group_load; sds->total_pwr += sg->sgp->power;@@ -4916,8 +4889,6 @@ static inline void calculate_imbalance(s* to restore balance. * * @env: The load balancing environment. -* @balance: Pointer to a variable indicating if this_cpu -* is the appropriate cpu to perform load balancing at this_level. * * Return: - The busiest group if imbalance exists. * - If no imbalance and user has opted for power-savings balance, @@ -4925,7 +4896,7 @@ static inline void calculate_imbalance(s* put to idle by rebalancing its tasks onto our group. */ static struct sched_group * -find_busiest_group (struct lb_env *env,int *balance) +find_busiest_group (struct lb_env *env) {struct sd_lb_stats sds;@@ -4935,14 +4906,7 @@ find_busiest_group(struct lb_env *env, i* Compute the various statistics relavent for load balancing at * this level. */ -update_sd_lb_stats (env, balance, &sds); - -/* -* this_cpu is not the appropriate cpu to perform load balancing at -* this level. -*/ -if (!(*balance)) - goto ret; +update_sd_lb_stats (env, &sds);if ((env->idle ==CPU_IDLE || env->idle ==CPU_NEWLY_IDLE ) &&check_asym_packing (env, &sds))@@ -5006,7 +4970,6 @@ find_busiest_group(struct lb_env *env, ireturn sds.busiest; out_balanced: -ret: env->imbalance =0 ;return NULL ; }@@ -5088,13 +5051,47 @@ static int need_active_balance(struct lbstatic int active_load_balance_cpu_stop (void *data); +static int should_we_balance (struct lb_env *env) +{ +struct sched_group *sg = env->sd->groups; +struct cpumask *sg_cpus, *sg_mask; +int cpu, balance_cpu =-1 ; + +/* +* In the newly idle case, we will allow all the cpu's +* to do the newly idle load balance. +*/ +if (env->idle ==CPU_NEWLY_IDLE ) +return 1 ; + + sg_cpus =sched_group_cpus (sg); + sg_mask =sched_group_mask (sg); +/* Try to find first idle cpu */ +for_each_cpu_and (cpu, sg_cpus, env->cpus) { +if (!cpumask_test_cpu (cpu, sg_mask) || !idle_cpu (cpu)) +continue ; + + balance_cpu = cpu; +break ; + } + +if (balance_cpu ==-1 ) + balance_cpu =group_balance_cpu (sg); + +/* +* First idle cpu or the first cpu(busiest) in this sched group +* is eligible for doing load balancing at this and above domains. +*/ +return balance_cpu != env->dst_cpu; +} +/* * Check this_cpu to ensure it is balanced within domain. Attempt to move * tasks if there is an imbalance. */ static int load_balance (int this_cpu,struct rq *this_rq,struct sched_domain *sd,enum cpu_idle_type idle, -int *balance) +int *should_balance) {int ld_moved, cur_ld_moved, active_balance =0 ;struct sched_group *group;
kernel/sched/fair.c static int load_balance(int this_cpu, st · line 5124
Quoted 9 lines
kernel/sched/fair.c +1
-4@@ -5123,12 +5120,11 @@ static int load_balance(int this_cpu, stschedstat_inc (sd, lb_count[idle]); -redo: - group =find_busiest_group (&env, balance); - -if (*balance ==0 ) +if (!(*should_balance =should_we_balance (&env))) goto out_balanced;
Given we always initialize *should_balance where we care, it might be more readable to write this as:
if (!should_we_balance(&env)) {
*continue_balancing = 0;
goto out_balanced;
}
[ With a rename to can_balance ]
kernel/sched/fair.c static int load_balance(int this_cpu, st · line 5126
Quoted 2 lines
kernel/sched/fair.c +1
-0+redo:
One behavioral change worth noting here is that in the redo case if a CPU has become idle we'll continue trying to load-balance in the !new-idle case.
This could be unpleasant in the case where a package has a pinned busy core allowing this and a newly idle cpu to start dueling for load.
While more deterministically bad in this case now, it could racily do this before anyway so perhaps not worth worrying about immediately.
Quoted 44 lines
kernel/sched/fair.c +6
-4+ group =find_busiest_group (&env);if (!group) {schedstat_inc (sd, lb_nobusyg[idle]); goto out_balanced;@@ -5340,7 +5336,7 @@ void idle_balance(int this_cpu, struct rrcu_read_lock ();for_each_domain (this_cpu, sd) {unsigned long interval; -int balance =1 ; +int should_balance;if (!(sd->flags &SD_LOAD_BALANCE ))continue ;@@ -5348,7 +5344,8 @@ void idle_balance(int this_cpu, struct rif (sd->flags &SD_BALANCE_NEWIDLE ) {/* If we've pulled tasks over stop searching: */ pulled_task =load_balance (this_cpu, this_rq, - sd,CPU_NEWLY_IDLE , &balance); + sd,CPU_NEWLY_IDLE , + &should_balance); } interval =msecs_to_jiffies (sd->balance_interval);@@ -5586,7 +5583,7 @@ void update_max_interval(void)*/ static void rebalance_domains (int cpu,enum cpu_idle_type idle) { -int balance =1 ; +int should_balance =1 ;struct rq *rq =cpu_rq (cpu);unsigned long interval;struct sched_domain *sd;@@ -5618,7 +5615,7 @@ static void rebalance_domains(int cpu, e }if (time_after_eq (jiffies, sd->last_balance + interval)) { -if (load_balance (cpu, rq, sd, idle, &balance)) { +if (load_balance (cpu, rq, sd, idle, &should_balance)) {/* * The LBF_SOME_PINNED logic could have changed * env->dst_cpu, so we can't know our idle
kernel/sched/fair.c static void rebalance_domains(int cpu, e · line 5644
Quoted 8 lines
kernel/sched/fair.c +1
-1@@ -5641,7 +5638,7 @@ static void rebalance_domains(int cpu, e* CPU in our sched group which is doing load balancing more * actively. */ -if (!balance) +if (!should_balance)break ; }rcu_read_unlock ();
Peter Zijlstra
maintainerRe: [PATCH 02/10] sched: Factor out code to should_we_balance()
Quoted 11 lines · Paul Turner
Quoted 2 lines · Peter Zijlstra
+ if (
local_group)load = target_load(i, load_idx);Keep the braces here:
if (local_group) { load = target_load(i, load_idx); } else { ...
Right you are, I misplaced that hunk in the next patch.
Quoted 11 lines
Quoted 11 lines
kernel/sched/fair.c +1
-1- }else { +else { load =source_load (i, load_idx);if (load > max_cpu_load) max_cpu_load = load;@@ -5123,12 +5120,11 @@ static int load_balance(int this_cpu, stschedstat_inc (sd, lb_count[idle]);
Quoted 9 lines
kernel/sched/fair.c static int load_balance(int this_cpu, st · line 5124
Quoted 6 lines
kernel/sched/fair.c +1
-4-redo: - group =find_busiest_group (&env, balance); - -if (*balance ==0 ) +if (!(*should_balance =should_we_balance (&env))) goto out_balanced;Given we always initialize
*should_balancewhere we care, it might be more readable to write this as:
Ah, but we don't actually, idle_balance() doesn't initialize should_balance -- easy enough to fix though.
Quoted 6 lines
if (!should_we_balance(&env)) {
*continue_balancing= 0;
gotoout_balanced;
}[ With a rename to
can_balance]
You confused me, your code implied %s/should_balance/continue_balancing/g but now you suggest %%s/should_balance/can_balance/g ?
I'm fine with either.
Quoted 7 lines
kernel/sched/fair.c static int load_balance(int this_cpu, st · line 5126
Quoted 2 lines
kernel/sched/fair.c +1
-0+redo:One behavioral change worth noting here is that in the redo case if a CPU has become idle we'll continue trying to load-balance in the !new-idle case.
Quoted 5 lines
This could be unpleasant in the case where a package has a pinned busy core allowing this and a newly idle cpu to start dueling for load.
While more deterministically bad in this case now, it could racily do this before anyway so perhaps not worth worrying about immediately.
Ah, because the old code would effectively redo the check and find the idle cpu and thereby our cpu would no longer be the balance_cpu.
Indeed. And I don't think this was an intentional change. I'll go put the redo back before should_we_balance().
Re: [PATCH 02/10] sched: Factor out code to should_we_balance()
Quoted 10 lines · Peter Zijlstra
Quoted 10 lines
Quoted 2 lines
+redo:
One behavioral change worth noting here is that in the redo case if a CPU has become idle we'll continue trying to load-balance in the !new-idle case.
This could be unpleasant in the case where a package has a pinned busy core allowing this and a newly idle cpu to start dueling for load.
Quoted 8 lines
Quoted 2 lines
While more deterministically bad in this case now, it could racily do this before anyway so perhaps not worth worrying about immediately.
Ah, because the old code would effectively redo the check and find the idle cpu and thereby our cpu would no longer be the
balance_cpu.Indeed. And I don't think this was an intentional change. I'll go put the redo back before
should_we_balance().
Ah, yes.
It isn't my intention. Please fix it.
Thanks.
Re: [PATCH 02/10] sched: Factor out code to should_we_balance()
In reply to Peter ZijlstraQuoted 36 lines · Peter Zijlstra
Quoted 11 lines · Paul Turner
Quoted 2 lines · Peter Zijlstra
+ if (
local_group)load = target_load(i, load_idx);Keep the braces here:
if (local_group) { load = target_load(i, load_idx); } else { ...Right you are, I misplaced that hunk in the next patch.
Quoted 11 lines
Quoted 11 lines
kernel/sched/fair.c +1
-1- }else { +else { load =source_load (i, load_idx);if (load > max_cpu_load) max_cpu_load = load;@@ -5123,12 +5120,11 @@ static int load_balance(int this_cpu, stschedstat_inc (sd, lb_count[idle]);Quoted 9 lines
kernel/sched/fair.c static int load_balance(int this_cpu, st · line 5124
Quoted 6 lines
kernel/sched/fair.c +1
-4-redo: - group =find_busiest_group (&env, balance); - -if (*balance ==0 ) +if (!(*should_balance =should_we_balance (&env))) goto out_balanced;Given we always initialize
*should_balancewhere we care, it might be more readable to write this as:
Quoted 2 lines
Ah, but we don't actually,
idle_balance()doesn't initializeshould_balance-- easy enough to fix though.
I should have been more explicit here.
idle_balance() doesn't initialize it, but it completely ignores the result; it's just passing something in case a write occurs. (Arguably it should be int unused = 1 instead of int balance = 1)
Quoted 6 lines
Quoted 6 lines
if (!should_we_balance(&env)) {
*continue_balancing= 0;
gotoout_balanced;
}
Quoted 7 lines
Quoted 1 line
[ With a rename to
can_balance]You confused me, your code implied %s/should_balance/continue_balancing/g but now you suggest %%s/should_balance/can_balance/g ?
I'm fine with either.
My bad, I started typing this comment, then went and looked at other parts of the patch and came back to it :)
I think continue_balancing is more clear.
Quoted 11 lines
Quoted 11 lines
kernel/sched/fair.c static int load_balance(int this_cpu, st · line 5126
Quoted 3 lines
kernel/sched/fair.c +1
-0+redo:One behavioral change worth noting here is that in the redo case if a CPU has become idle we'll continue trying to load-balance in the !new-idle case.
This could be unpleasant in the case where a package has a pinned busy core allowing this and a newly idle cpu to start dueling for load.
Quoted 9 lines
Quoted 2 lines
While more deterministically bad in this case now, it could racily do this before anyway so perhaps not worth worrying about immediately.
Ah, because the old code would effectively redo the check and find the idle cpu and thereby our cpu would no longer be the
balance_cpu.Indeed. And I don't think this was an intentional change. I'll go put the redo back before
should_we_balance().
I was trying to get through the rest of these today but I'm out of time. I should be able to finish reviewing the other patches in the set tomorrow.
Peter Zijlstra
maintainerPATCH 3/10 sched: Clean-up struct sd_lb_stat
In reply to Peter ZijlstraFrom: Joonsoo Kim <[email protected]>
There is no reason to maintain separate variables for this_group and busiest_group in sd_lb_stat, except saving some space. But this structure is always allocated in stack, so this saving isn't really benificial [peterz: reducing stack space is good; in this case readability increases enough that I think its still beneficial]
This patch unify these variables, so IMO, readability may be improved.
--- kernel/sched/fair.c | 225 +++++++++++++++++++++++++--------------------------- 1 file changed, 112 insertions(+), 113 deletions(-)
kernel/sched/fair.c +112 -113
@@ -4277,36 +4277,6 @@ static unsigned long task_h_load(struct/********** Helpers for find_busiest_group ************************/ /* -* sd_lb_stats - Structure to store the statistics of a sched_domain -* during load balancing. -*/ -struct sd_lb_stats { -struct sched_group *busiest;/* Busiest group in this sd */ -struct sched_group *this;/* Local group in this sd */ -unsigned long total_load;/* Total load of all groups in sd */ -unsigned long total_pwr;/* Total power of all groups in sd */ -unsigned long avg_load;/* Average load across all groups in sd */ - -/** Statistics of this group */ -unsigned long this_load; -unsigned long this_load_per_task; -unsigned long this_nr_running; -unsigned long this_has_capacity; -unsigned int this_idle_cpus; - -/* Statistics of the busiest group */ -unsigned int busiest_idle_cpus; -unsigned long max_load; -unsigned long busiest_load_per_task; -unsigned long busiest_nr_running; -unsigned long busiest_group_capacity; -unsigned long busiest_has_capacity; -unsigned int busiest_group_weight; - -int group_imb;/* Is there imbalance in this sd */ -}; - -/* * sg_lb_stats - stats of a sched_group required for load_balancing */ struct sg_lb_stats {
@@ -4314,6 +4284,7 @@ struct sg_lb_stats {unsigned long group_load;/* Total load over the CPUs of the group */ unsigned long sum_nr_running;/* Nr tasks running in the group */ unsigned long sum_weighted_load;/* Weighted load of group's tasks */ +unsigned long load_per_task;unsigned long group_capacity;unsigned long idle_cpus;unsigned long group_weight;
@@ -4321,6 +4292,21 @@ struct sg_lb_stats {int group_has_capacity;/* Is there extra capacity in the group? */ }; +/* +* sd_lb_stats - Structure to store the statistics of a sched_domain +* during load balancing. +*/ +struct sd_lb_stats { +struct sched_group *busiest;/* Busiest group in this sd */ +struct sched_group *this;/* Local group in this sd */ +unsigned long total_load;/* Total load of all groups in sd */ +unsigned long total_pwr;/* Total power of all groups in sd */ +unsigned long avg_load;/* Average load across all groups in sd */ + +struct sg_lb_stats this_stat;/* Statistics of this group */ +struct sg_lb_stats busiest_stat;/* Statistics of the busiest group */ +}; +/** * get_sd_load_idx - Obtain the load index for a given sched domain. * @sd: The sched_domain whose load_idx is to be obtained.
@@ -4533,10 +4519,11 @@ static inline void update_sg_lb_stats(st nr_running = rq->nr_running;/* Bias balancing toward cpus of our domain */ -if (local_group) +if (local_group) { load =target_load (i, load_idx); -else { + }else { load =source_load (i, load_idx); +if (load > max_cpu_load) max_cpu_load = load;if (min_cpu_load > load)
@@ -4578,10 +4565,12 @@ static inline void update_sg_lb_stats(st (max_nr_running - min_nr_running) > 1) sgs->group_imb = 1; - sgs->group_capacity =DIV_ROUND_CLOSEST (group->sgp->power, -SCHED_POWER_SCALE ); + sgs->group_capacity = +DIV_ROUND_CLOSEST (group->sgp->power,SCHED_POWER_SCALE ); +if (!sgs->group_capacity) sgs->group_capacity =fix_small_capacity (env->sd, group); + sgs->group_weight = group->group_weight;if (sgs->group_capacity > sgs->sum_nr_running)
@@ -4606,7 +4595,7 @@ static bool update_sd_pick_busiest(struc struct sched_group *sg, struct sg_lb_stats *sgs) { -if (sgs->avg_load <= sds->max_load) +if (sgs->avg_load <= sds->busiest_stat.avg_load)return false;if (sgs->sum_nr_running > sgs->group_capacity)
@@ -4643,7 +4632,7 @@ static inline void update_sd_lb_stats(st {struct sched_domain *child = env->sd->child;struct sched_group *sg = env->sd->groups; -struct sg_lb_stats sgs; +struct sg_lb_stats tmp_sgs;int load_idx, prefer_sibling =0 ;if (child && child->flags &SD_PREFER_SIBLING )
@@ -4652,14 +4641,17 @@ static inline void update_sd_lb_stats(st load_idx =get_sd_load_idx (env->sd, env->idle); do { + struct sg_lb_stats *sgs = &tmp_sgs; int local_group; local_group = cpumask_test_cpu(env->dst_cpu, sched_group_cpus(sg)); - memset(&sgs, 0, sizeof(sgs)); - update_sg_lb_stats(env, sg, load_idx, local_group, &sgs); + if (local_group) { + sds->this = sg; + sgs = &sds->this_stat; + } - sds->total_load += sgs.group_load; - sds->total_pwr += sg->sgp->power; + memset(sgs, 0, sizeof(*sgs)); + update_sg_lb_stats(env, sg, load_idx, local_group, sgs); /* * In case the child domain prefers tasks go to siblings
@@ -4671,26 +4663,17 @@ static inline void update_sd_lb_stats(st* heaviest group when it is already under-utilized (possible * with a large weight task outweighs the tasks on the system). */ -if (prefer_sibling && !local_group && sds->this_has_capacity) - sgs.group_capacity =min (sgs.group_capacity,1UL ); +if (prefer_sibling && !local_group && + sds->this && sds->this_stat.group_has_capacity) + sgs->group_capacity =min (sgs->group_capacity,1UL ); -if (local_group) { - sds->this_load = sgs.avg_load; - sds->this = sg; - sds->this_nr_running = sgs.sum_nr_running; - sds->this_load_per_task = sgs.sum_weighted_load; - sds->this_has_capacity = sgs.group_has_capacity; - sds->this_idle_cpus = sgs.idle_cpus; - }else if (update_sd_pick_busiest (env, sds, sg, &sgs)) { - sds->max_load = sgs.avg_load; +/* Now, start updating sd_lb_stats */ + sds->total_load += sgs->group_load; + sds->total_pwr += sg->sgp->power; + +if (!local_group &&update_sd_pick_busiest (env, sds, sg, sgs)) { sds->busiest = sg; - sds->busiest_nr_running = sgs.sum_nr_running; - sds->busiest_idle_cpus = sgs.idle_cpus; - sds->busiest_group_capacity = sgs.group_capacity; - sds->busiest_load_per_task = sgs.sum_weighted_load; - sds->busiest_has_capacity = sgs.group_has_capacity; - sds->busiest_group_weight = sgs.group_weight; - sds->group_imb = sgs.group_imb; + sds->busiest_stat = *sgs; } sg = sg->next;
@@ -4734,8 +4717,8 @@ static int check_asym_packing(struct lb_if (env->dst_cpu > busiest_cpu)return 0 ; - env->imbalance =DIV_ROUND_CLOSEST ( - sds->max_load * sds->busiest->sgp->power,SCHED_POWER_SCALE ); + env->imbalance =DIV_ROUND_CLOSEST (sds->busiest_stat.avg_load * + sds->busiest->sgp->power,SCHED_POWER_SCALE );return 1 ; }
@@ -4753,24 +4736,23 @@ void fix_small_imbalance(struct lb_env *unsigned long tmp, pwr_now =0 , pwr_move =0 ;unsigned int imbn =2 ;unsigned long scaled_busy_load_per_task; +struct sg_lb_stats *this, *busiest; -if (sds->this_nr_running) { - sds->this_load_per_task /= sds->this_nr_running; -if (sds->busiest_load_per_task > - sds->this_load_per_task) - imbn =1 ; - }else { - sds->this_load_per_task = -cpu_avg_load_per_task (env->dst_cpu); - } + this = &sds->this_stat; + busiest = &sds->busiest_stat; + +if (!this->sum_nr_running) + this->load_per_task =cpu_avg_load_per_task (env->dst_cpu); +else if (busiest->load_per_task > this->load_per_task) + imbn =1 ; - scaled_busy_load_per_task = sds->busiest_load_per_task - *SCHED_POWER_SCALE ; - scaled_busy_load_per_task /= sds->busiest->sgp->power; + scaled_busy_load_per_task = + (busiest->load_per_task *SCHED_POWER_SCALE ) / + sds->busiest->sgp->power; -if (sds->max_load - sds->this_load + scaled_busy_load_per_task >= - (scaled_busy_load_per_task * imbn)) { - env->imbalance = sds->busiest_load_per_task; +if (busiest->avg_load - this->avg_load + scaled_busy_load_per_task >= + (scaled_busy_load_per_task * imbn)) { + env->imbalance = busiest->load_per_task;return ; }
@@ -4781,33 +4763,36 @@ void fix_small_imbalance(struct lb_env **/ pwr_now += sds->busiest->sgp->power * -min (sds->busiest_load_per_task, sds->max_load); +min (busiest->load_per_task, busiest->avg_load); pwr_now += sds->this->sgp->power * -min (sds->this_load_per_task, sds->this_load); +min (this->load_per_task, this->avg_load); pwr_now /=SCHED_POWER_SCALE ;/* Amount of load we'd subtract */ - tmp = (sds->busiest_load_per_task *SCHED_POWER_SCALE ) / + tmp = (busiest->load_per_task *SCHED_POWER_SCALE ) / sds->busiest->sgp->power; -if (sds->max_load > tmp) +if (busiest->avg_load > tmp) { pwr_move += sds->busiest->sgp->power * -min (sds->busiest_load_per_task, sds->max_load - tmp); +min (busiest->load_per_task, + busiest->avg_load - tmp); + }/* Amount of load we'd add */ -if (sds->max_load * sds->busiest->sgp->power < - sds->busiest_load_per_task *SCHED_POWER_SCALE ) - tmp = (sds->max_load * sds->busiest->sgp->power) / +if (busiest->avg_load * sds->busiest->sgp->power < + busiest->load_per_task *SCHED_POWER_SCALE ) { + tmp = (busiest->avg_load * sds->busiest->sgp->power) / sds->this->sgp->power; -else - tmp = (sds->busiest_load_per_task *SCHED_POWER_SCALE ) / + }else { + tmp = (busiest->load_per_task *SCHED_POWER_SCALE ) / sds->this->sgp->power; + } pwr_move += sds->this->sgp->power * -min (sds->this_load_per_task, sds->this_load + tmp); +min (this->load_per_task, this->avg_load + tmp); pwr_move /=SCHED_POWER_SCALE ;/* Move if we gain throughput */ if (pwr_move > pwr_now) - env->imbalance = sds->busiest_load_per_task; + env->imbalance = busiest->load_per_task; }/**
@@ -4819,11 +4804,22 @@ void fix_small_imbalance(struct lb_env *static inline void calculate_imbalance (struct lb_env *env,struct sd_lb_stats *sds) {unsigned long max_pull, load_above_capacity = ~0UL ; +struct sg_lb_stats *this, *busiest; - sds->busiest_load_per_task /= sds->busiest_nr_running; -if (sds->group_imb) { - sds->busiest_load_per_task = -min (sds->busiest_load_per_task, sds->avg_load); + this = &sds->this_stat; +if (this->sum_nr_running) { + this->load_per_task = + this->sum_weighted_load / this->sum_nr_running; + } + + busiest = &sds->busiest_stat; +/* busiest must have some tasks */ + busiest->load_per_task = + busiest->sum_weighted_load / busiest->sum_nr_running; + +if (busiest->group_imb) { + busiest->load_per_task = +min (busiest->load_per_task, sds->avg_load); }/*
@@ -4831,20 +4827,19 @@ static inline void calculate_imbalance(s* max load less than avg load(as we skip the groups at or below * its cpu_power, while calculating max_load..) */ -if (sds->max_load < sds->avg_load) { +if (busiest->avg_load < sds->avg_load) { env->imbalance =0 ;return fix_small_imbalance (env, sds); } -if (!sds->group_imb) { +if (!busiest->group_imb) {/* * Don't want to pull so many tasks that a group would go idle. */ - load_above_capacity = (sds->busiest_nr_running - - sds->busiest_group_capacity); + load_above_capacity = + (busiest->sum_nr_running - busiest->group_capacity); load_above_capacity *= (SCHED_LOAD_SCALE *SCHED_POWER_SCALE ); - load_above_capacity /= sds->busiest->sgp->power; }
@@ -4858,12 +4853,14 @@ static inline void calculate_imbalance(s* Be careful of negative numbers as they'll appear as very large values * with unsigned longs. */ - max_pull =min (sds->max_load - sds->avg_load, load_above_capacity); + max_pull =min (busiest->avg_load - sds->avg_load, + load_above_capacity);/* How much load to actually move to equalise the imbalance */ - env->imbalance =min (max_pull * sds->busiest->sgp->power, - (sds->avg_load - sds->this_load) * sds->this->sgp->power) - /SCHED_POWER_SCALE ; + env->imbalance =min ( + max_pull * sds->busiest->sgp->power, + (sds->avg_load - this->avg_load) * sds->this->sgp->power + ) /SCHED_POWER_SCALE ;/* * if *imbalance is less than the average load per runnable task
@@ -4871,9 +4868,8 @@ static inline void calculate_imbalance(s* a think about bumping its value to force at least one task to be * moved */ -if (env->imbalance < sds->busiest_load_per_task) +if (env->imbalance < busiest->load_per_task)return fix_small_imbalance (env, sds); - }/******* find_busiest_group() helpers end here *********************/
@@ -4895,9 +4891,9 @@ static inline void calculate_imbalance(s* return the least loaded group whose CPUs can be * put to idle by rebalancing its tasks onto our group. */ -static struct sched_group * -find_busiest_group (struct lb_env *env) +static struct sched_group *find_busiest_group (struct lb_env *env) { +struct sg_lb_stats *this, *busiest;struct sd_lb_stats sds;memset (&sds,0 ,sizeof (sds));
@@ -4907,13 +4903,15 @@ find_busiest_group(struct lb_env *env)* this level. */ update_sd_lb_stats (env, &sds); + this = &sds.this_stat; + busiest = &sds.busiest_stat;if ((env->idle ==CPU_IDLE || env->idle ==CPU_NEWLY_IDLE ) &&check_asym_packing (env, &sds))return sds.busiest;/* There is no busy sibling group to pull tasks from */ -if (!sds.busiest || sds.busiest_nr_running ==0 ) +if (!sds.busiest || busiest->sum_nr_running ==0 ) goto out_balanced; sds.avg_load = (SCHED_POWER_SCALE * sds.total_load) / sds.total_pwr;
@@ -4923,26 +4921,26 @@ find_busiest_group(struct lb_env *env)* work because they assumes all things are equal, which typically * isn't true due to cpus_allowed constraints and the like. */ -if (sds.group_imb) +if (busiest->group_imb) goto force_balance;/* SD_BALANCE_NEWIDLE trumps SMP nice when underutilized */ -if (env->idle ==CPU_NEWLY_IDLE && sds.this_has_capacity && - !sds.busiest_has_capacity) +if (env->idle ==CPU_NEWLY_IDLE && this->group_has_capacity && + !busiest->group_has_capacity) goto force_balance;/* * If the local group is more busy than the selected busiest group * don't try and pull any tasks. */ -if (sds.this_load >= sds.max_load) +if (this->avg_load >= busiest->avg_load) goto out_balanced;/* * Don't pull any tasks if this group is already above the domain * average load. */ -if (sds.this_load >= sds.avg_load) +if (this->avg_load >= sds.avg_load) goto out_balanced;if (env->idle ==CPU_IDLE ) {
@@ -4952,15 +4950,16 @@ find_busiest_group(struct lb_env *env)* there is no imbalance between this and busiest group * wrt to idle cpu's, it is balanced. */ -if ((sds.this_idle_cpus <= sds.busiest_idle_cpus +1 ) && - sds.busiest_nr_running <= sds.busiest_group_weight) +if ((this->idle_cpus <= busiest->idle_cpus +1 ) && + busiest->sum_nr_running <= busiest->group_weight) goto out_balanced; }else {/* * In the CPU_NEWLY_IDLE, CPU_NOT_IDLE cases, use * imbalance_pct to be conservative. */ -if (100 * sds.max_load <= env->sd->imbalance_pct * sds.this_load) +if (100 * busiest->avg_load <= + env->sd->imbalance_pct * this->avg_load) goto out_balanced; }
Re: [PATCH 03/10] sched: Clean-up struct sd_lb_stat
Quoted 374 lines · Peter Zijlstra
From: Joonsoo Kim <[email protected]>
There is no reason to maintain separate variables for
this_groupandbusiest_groupinsd_lb_stat, except saving some space. But this structure is always allocated in stack, so this saving isn't really benificial [peterz: reducing stack space is good; in this case readability increases enough that I think its still beneficial]This patch unify these variables, so IMO, readability may be improved.
Signed-off-by Joonsoo Kim <[email protected]>[peterz: lots of style edits, a few fixes and a rename]Signed-off-by Peter Zijlstra <[email protected]>--- kernel/sched/fair.c | 225 +++++++++++++++++++++++++--------------------------- 1 file changed, 112 insertions(+), 113 deletions(-)kernel/sched/fair.c +98
-102@@ -4277,36 +4277,6 @@ static unsigned long task_h_load(struct/********** Helpers for find_busiest_group ************************/ /* -* sd_lb_stats - Structure to store the statistics of a sched_domain -* during load balancing. -*/ -struct sd_lb_stats { -struct sched_group *busiest;/* Busiest group in this sd */ -struct sched_group *this;/* Local group in this sd */ -unsigned long total_load;/* Total load of all groups in sd */ -unsigned long total_pwr;/* Total power of all groups in sd */ -unsigned long avg_load;/* Average load across all groups in sd */ - -/** Statistics of this group */ -unsigned long this_load; -unsigned long this_load_per_task; -unsigned long this_nr_running; -unsigned long this_has_capacity; -unsigned int this_idle_cpus; - -/* Statistics of the busiest group */ -unsigned int busiest_idle_cpus; -unsigned long max_load; -unsigned long busiest_load_per_task; -unsigned long busiest_nr_running; -unsigned long busiest_group_capacity; -unsigned long busiest_has_capacity; -unsigned int busiest_group_weight; - -int group_imb;/* Is there imbalance in this sd */ -}; - -/* * sg_lb_stats - stats of a sched_group required for load_balancing */ struct sg_lb_stats {@@ -4314,6 +4284,7 @@ struct sg_lb_stats {unsigned long group_load;/* Total load over the CPUs of the group */ unsigned long sum_nr_running;/* Nr tasks running in the group */ unsigned long sum_weighted_load;/* Weighted load of group's tasks */ +unsigned long load_per_task;unsigned long group_capacity;unsigned long idle_cpus;unsigned long group_weight;@@ -4321,6 +4292,21 @@ struct sg_lb_stats {int group_has_capacity;/* Is there extra capacity in the group? */ }; +/* +* sd_lb_stats - Structure to store the statistics of a sched_domain +* during load balancing. +*/ +struct sd_lb_stats { +struct sched_group *busiest;/* Busiest group in this sd */ +struct sched_group *this;/* Local group in this sd */ +unsigned long total_load;/* Total load of all groups in sd */ +unsigned long total_pwr;/* Total power of all groups in sd */ +unsigned long avg_load;/* Average load across all groups in sd */ + +struct sg_lb_stats this_stat;/* Statistics of this group */ +struct sg_lb_stats busiest_stat;/* Statistics of the busiest group */ +}; +/** * get_sd_load_idx - Obtain the load index for a given sched domain. * @sd: The sched_domain whose load_idx is to be obtained. @@ -4533,10 +4519,11 @@ static inline void update_sg_lb_stats(st nr_running = rq->nr_running;/* Bias balancing toward cpus of our domain */ -if (local_group) +if (local_group) { load =target_load (i, load_idx); -else { + }else { load =source_load (i, load_idx); +if (load > max_cpu_load) max_cpu_load = load;if (min_cpu_load > load)@@ -4578,10 +4565,12 @@ static inline void update_sg_lb_stats(st (max_nr_running - min_nr_running) > 1) sgs->group_imb =1 ; - sgs->group_capacity =DIV_ROUND_CLOSEST (group->sgp->power, -SCHED_POWER_SCALE ); + sgs->group_capacity = +DIV_ROUND_CLOSEST (group->sgp->power,SCHED_POWER_SCALE ); +if (!sgs->group_capacity) sgs->group_capacity =fix_small_capacity (env->sd, group); + sgs->group_weight = group->group_weight;if (sgs->group_capacity > sgs->sum_nr_running)@@ -4606,7 +4595,7 @@ static bool update_sd_pick_busiest(struc struct sched_group *sg, struct sg_lb_stats *sgs) { -if (sgs->avg_load <= sds->max_load) +if (sgs->avg_load <= sds->busiest_stat.avg_load)return false;if (sgs->sum_nr_running > sgs->group_capacity)@@ -4643,7 +4632,7 @@ static inline void update_sd_lb_stats(st {struct sched_domain *child = env->sd->child;struct sched_group *sg = env->sd->groups; -struct sg_lb_stats sgs; +struct sg_lb_stats tmp_sgs;int load_idx, prefer_sibling =0 ;if (child && child->flags &SD_PREFER_SIBLING )@@ -4652,14 +4641,17 @@ static inline void update_sd_lb_stats(st load_idx =get_sd_load_idx (env->sd, env->idle); do { + struct sg_lb_stats *sgs = &tmp_sgs; int local_group; local_group = cpumask_test_cpu(env->dst_cpu, sched_group_cpus(sg)); - memset(&sgs, 0, sizeof(sgs)); - update_sg_lb_stats(env, sg, load_idx, local_group, &sgs); + if (local_group) { + sds->this = sg; + sgs = &sds->this_stat; + } - sds->total_load += sgs.group_load; - sds->total_pwr += sg->sgp->power; + memset(sgs, 0, sizeof(*sgs)); + update_sg_lb_stats(env, sg, load_idx, local_group, sgs); /* * In case the child domain prefers tasks go to siblings@@ -4671,26 +4663,17 @@ static inline void update_sd_lb_stats(st* heaviest group when it is already under-utilized (possible * with a large weight task outweighs the tasks on the system). */ -if (prefer_sibling && !local_group && sds->this_has_capacity) - sgs.group_capacity =min (sgs.group_capacity,1UL ); +if (prefer_sibling && !local_group && + sds->this && sds->this_stat.group_has_capacity) + sgs->group_capacity =min (sgs->group_capacity,1UL ); -if (local_group) { - sds->this_load = sgs.avg_load; - sds->this = sg; - sds->this_nr_running = sgs.sum_nr_running; - sds->this_load_per_task = sgs.sum_weighted_load; - sds->this_has_capacity = sgs.group_has_capacity; - sds->this_idle_cpus = sgs.idle_cpus; - }else if (update_sd_pick_busiest (env, sds, sg, &sgs)) { - sds->max_load = sgs.avg_load; +/* Now, start updating sd_lb_stats */ + sds->total_load += sgs->group_load; + sds->total_pwr += sg->sgp->power; + +if (!local_group &&update_sd_pick_busiest (env, sds, sg, sgs)) { sds->busiest = sg; - sds->busiest_nr_running = sgs.sum_nr_running; - sds->busiest_idle_cpus = sgs.idle_cpus; - sds->busiest_group_capacity = sgs.group_capacity; - sds->busiest_load_per_task = sgs.sum_weighted_load; - sds->busiest_has_capacity = sgs.group_has_capacity; - sds->busiest_group_weight = sgs.group_weight; - sds->group_imb = sgs.group_imb; + sds->busiest_stat = *sgs; } sg = sg->next;@@ -4734,8 +4717,8 @@ static int check_asym_packing(struct lb_if (env->dst_cpu > busiest_cpu)return 0 ; - env->imbalance =DIV_ROUND_CLOSEST ( - sds->max_load * sds->busiest->sgp->power,SCHED_POWER_SCALE ); + env->imbalance =DIV_ROUND_CLOSEST (sds->busiest_stat.avg_load * + sds->busiest->sgp->power,SCHED_POWER_SCALE );return 1 ; }@@ -4753,24 +4736,23 @@ void fix_small_imbalance(struct lb_env *unsigned long tmp, pwr_now =0 , pwr_move =0 ;unsigned int imbn =2 ;unsigned long scaled_busy_load_per_task; +struct sg_lb_stats *this, *busiest; -if (sds->this_nr_running) { - sds->this_load_per_task /= sds->this_nr_running; -if (sds->busiest_load_per_task > - sds->this_load_per_task) - imbn =1 ; - }else { - sds->this_load_per_task = -cpu_avg_load_per_task (env->dst_cpu); - } + this = &sds->this_stat; + busiest = &sds->busiest_stat; + +if (!this->sum_nr_running) + this->load_per_task =cpu_avg_load_per_task (env->dst_cpu); +else if (busiest->load_per_task > this->load_per_task) + imbn =1 ; - scaled_busy_load_per_task = sds->busiest_load_per_task - *SCHED_POWER_SCALE ; - scaled_busy_load_per_task /= sds->busiest->sgp->power; + scaled_busy_load_per_task = + (busiest->load_per_task *SCHED_POWER_SCALE ) / + sds->busiest->sgp->power; -if (sds->max_load - sds->this_load + scaled_busy_load_per_task >= - (scaled_busy_load_per_task * imbn)) { - env->imbalance = sds->busiest_load_per_task; +if (busiest->avg_load - this->avg_load + scaled_busy_load_per_task >= + (scaled_busy_load_per_task * imbn)) { + env->imbalance = busiest->load_per_task;return ; }@@ -4781,33 +4763,36 @@ void fix_small_imbalance(struct lb_env **/ pwr_now += sds->busiest->sgp->power * -min (sds->busiest_load_per_task, sds->max_load); +min (busiest->load_per_task, busiest->avg_load); pwr_now += sds->this->sgp->power * -min (sds->this_load_per_task, sds->this_load); +min (this->load_per_task, this->avg_load); pwr_now /=SCHED_POWER_SCALE ;/* Amount of load we'd subtract */ - tmp = (sds->busiest_load_per_task *SCHED_POWER_SCALE ) / + tmp = (busiest->load_per_task *SCHED_POWER_SCALE ) / sds->busiest->sgp->power; -if (sds->max_load > tmp) +if (busiest->avg_load > tmp) { pwr_move += sds->busiest->sgp->power * -min (sds->busiest_load_per_task, sds->max_load - tmp); +min (busiest->load_per_task, + busiest->avg_load - tmp); + }/* Amount of load we'd add */ -if (sds->max_load * sds->busiest->sgp->power < - sds->busiest_load_per_task *SCHED_POWER_SCALE ) - tmp = (sds->max_load * sds->busiest->sgp->power) / +if (busiest->avg_load * sds->busiest->sgp->power < + busiest->load_per_task *SCHED_POWER_SCALE ) { + tmp = (busiest->avg_load * sds->busiest->sgp->power) / sds->this->sgp->power; -else - tmp = (sds->busiest_load_per_task *SCHED_POWER_SCALE ) / + }else { + tmp = (busiest->load_per_task *SCHED_POWER_SCALE ) / sds->this->sgp->power; + } pwr_move += sds->this->sgp->power * -min (sds->this_load_per_task, sds->this_load + tmp); +min (this->load_per_task, this->avg_load + tmp); pwr_move /=SCHED_POWER_SCALE ;/* Move if we gain throughput */ if (pwr_move > pwr_now) - env->imbalance = sds->busiest_load_per_task; + env->imbalance = busiest->load_per_task; }/** @@ -4819,11 +4804,22 @@ void fix_small_imbalance(struct lb_env *static inline void calculate_imbalance (struct lb_env *env,struct sd_lb_stats *sds) {unsigned long max_pull, load_above_capacity = ~0UL ; +struct sg_lb_stats *this, *busiest; - sds->busiest_load_per_task /= sds->busiest_nr_running; -if (sds->group_imb) { - sds->busiest_load_per_task = -min (sds->busiest_load_per_task, sds->avg_load); + this = &sds->this_stat; +if (this->sum_nr_running) { + this->load_per_task = + this->sum_weighted_load / this->sum_nr_running; + } + + busiest = &sds->busiest_stat; +/* busiest must have some tasks */ + busiest->load_per_task = + busiest->sum_weighted_load / busiest->sum_nr_running; + +if (busiest->group_imb) { + busiest->load_per_task = +min (busiest->load_per_task, sds->avg_load); }/* @@ -4831,20 +4827,19 @@ static inline void calculate_imbalance(s* max load less than avg load(as we skip the groups at or below * its cpu_power, while calculating max_load..) */ -if (sds->max_load < sds->avg_load) { +if (busiest->avg_load < sds->avg_load) { env->imbalance =0 ;return fix_small_imbalance (env, sds); } -if (!sds->group_imb) { +if (!busiest->group_imb) {/* * Don't want to pull so many tasks that a group would go idle. */ - load_above_capacity = (sds->busiest_nr_running - - sds->busiest_group_capacity); + load_above_capacity = + (busiest->sum_nr_running - busiest->group_capacity); load_above_capacity *= (SCHED_LOAD_SCALE *SCHED_POWER_SCALE ); - load_above_capacity /= sds->busiest->sgp->power; }@@ -4858,12 +4853,14 @@ static inline void calculate_imbalance(s* Be careful of negative numbers as they'll appear as very large values * with unsigned longs. */ - max_pull =min (sds->max_load - sds->avg_load, load_above_capacity); + max_pull =min (busiest->avg_load - sds->avg_load, + load_above_capacity);/* How much load to actually move to equalise the imbalance */ - env->imbalance =min (max_pull * sds->busiest->sgp->power, - (sds->avg_load - sds->this_load) * sds->this->sgp->power) - /SCHED_POWER_SCALE ; + env->imbalance =min ( + max_pull * sds->busiest->sgp->power, + (sds->avg_load - this->avg_load) * sds->this->sgp->power + ) /SCHED_POWER_SCALE ;/* * if *imbalance is less than the average load per runnable task @@ -4871,9 +4868,8 @@ static inline void calculate_imbalance(s* a think about bumping its value to force at least one task to be * moved */ -if (env->imbalance < sds->busiest_load_per_task) +if (env->imbalance < busiest->load_per_task)return fix_small_imbalance (env, sds); - }/******* find_busiest_group() helpers end here *********************/
kernel/sched/fair.c static inline void calculate_imbalance(s · line 4896
Quoted 8 lines
kernel/sched/fair.c +2
-2@@ -4895,9 +4891,9 @@ static inline void calculate_imbalance(s* return the least loaded group whose CPUs can be * put to idle by rebalancing its tasks onto our group. */ -static struct sched_group * -find_busiest_group (struct lb_env *env) +static struct sched_group *find_busiest_group (struct lb_env *env) { +struct sg_lb_stats *this, *busiest;
"this" is a little confusing to read; mainly because elsewhere we've tied this to "this cpu" whereas the local sched group is arger. (Not to mention the obvious OOP-land overloading of "this->".)
Perhaps %s/this/local/ for sg_lb_stat references? Including this_stat -> local_stat on sd_lb_stats?
Quoted 53 lines
kernel/sched/fair.c +8
-6struct sd_lb_stats sds;memset (&sds,0 ,sizeof (sds));@@ -4907,13 +4903,15 @@ find_busiest_group(struct lb_env *env)* this level. */ update_sd_lb_stats (env, &sds); + this = &sds.this_stat; + busiest = &sds.busiest_stat;if ((env->idle ==CPU_IDLE || env->idle ==CPU_NEWLY_IDLE ) &&check_asym_packing (env, &sds))return sds.busiest;/* There is no busy sibling group to pull tasks from */ -if (!sds.busiest || sds.busiest_nr_running ==0 ) +if (!sds.busiest || busiest->sum_nr_running ==0 ) goto out_balanced; sds.avg_load = (SCHED_POWER_SCALE * sds.total_load) / sds.total_pwr;@@ -4923,26 +4921,26 @@ find_busiest_group(struct lb_env *env)* work because they assumes all things are equal, which typically * isn't true due to cpus_allowed constraints and the like. */ -if (sds.group_imb) +if (busiest->group_imb) goto force_balance;/* SD_BALANCE_NEWIDLE trumps SMP nice when underutilized */ -if (env->idle ==CPU_NEWLY_IDLE && sds.this_has_capacity && - !sds.busiest_has_capacity) +if (env->idle ==CPU_NEWLY_IDLE && this->group_has_capacity && + !busiest->group_has_capacity) goto force_balance;/* * If the local group is more busy than the selected busiest group * don't try and pull any tasks. */ -if (sds.this_load >= sds.max_load) +if (this->avg_load >= busiest->avg_load) goto out_balanced;/* * Don't pull any tasks if this group is already above the domain * average load. */ -if (sds.this_load >= sds.avg_load) +if (this->avg_load >= sds.avg_load) goto out_balanced;if (env->idle ==CPU_IDLE ) {
kernel/sched/fair.c find_busiest_group(struct lb_env *env) · line 4954
Quoted 7 lines
kernel/sched/fair.c +2
-2@@ -4952,15 +4950,16 @@ find_busiest_group(struct lb_env *env)* there is no imbalance between this and busiest group * wrt to idle cpu's, it is balanced. */ -if ((sds.this_idle_cpus <= sds.busiest_idle_cpus +1 ) && - sds.busiest_nr_running <= sds.busiest_group_weight) +if ((this->idle_cpus <= busiest->idle_cpus +1 ) && + busiest->sum_nr_running <= busiest->group_weight)
While we're improving readability: idle_cpus < busiest->idle_cpus ?
This check has always been a little oddly asymmetric in that:
group_weight - sum_nr_running <= idle_cpus
This allows the case where our group has pulled lots of work to one of its cpus, but not yet spread that out, but still keep trying to balance because idle_cpus is high.
This is more food for thought since this patch is not changing functionality.
kernel/sched/fair.c find_busiest_group(struct lb_env *env) · line 4965
Quoted 13 lines
kernel/sched/fair.c +2
-1goto out_balanced; }else {/* * In the CPU_NEWLY_IDLE, CPU_NOT_IDLE cases, use * imbalance_pct to be conservative. */ -if (100 * sds.max_load <= env->sd->imbalance_pct * sds.this_load) +if (100 * busiest->avg_load <= + env->sd->imbalance_pct * this->avg_load) goto out_balanced; }
Peter Zijlstra
maintainerRe: [PATCH 03/10] sched: Clean-up struct sd_lb_stat
Quoted 9 lines · Paul Turner
Quoted 1 line · Peter Zijlstra
+ struct
sg_lb_stats*this, *busiest;"this" is a little confusing to read; mainly because elsewhere we've tied this to "this cpu" whereas the local sched group is arger. (Not to mention the obvious OOP-land overloading of "this->".)
Perhaps %s/this/local/ for
sg_lb_statreferences? Includingthis_stat->local_statonsd_lb_stats?
fair enough, I'll edit the thing to be local.
Quoted 10 lines
kernel/sched/fair.c find_busiest_group(struct lb_env *env) · line 4954
Quoted 8 lines
kernel/sched/fair.c +2
-2@@ -4952,15 +4950,16 @@ find_busiest_group(struct lb_env *env)* there is no imbalance between this and busiest group * wrt to idle cpu's, it is balanced. */ -if ((sds.this_idle_cpus <= sds.busiest_idle_cpus +1 ) && - sds.busiest_nr_running <= sds.busiest_group_weight) +if ((this->idle_cpus <= busiest->idle_cpus +1 ) && + busiest->sum_nr_running <= busiest->group_weight)While we're improving readability:
idle_cpus<busiest->idle_cpus?
Right, took that.
Quoted 8 lines
This check has always been a little oddly asymmetric in that:
group_weight-sum_nr_running<=idle_cpusThis allows the case where our group has pulled lots of work to one of its cpus, but not yet spread that out, but still keep trying to balance because
idle_cpusis high.This is more food for thought since this patch is not changing functionality.
Right, I saw the same and made a note to look at it later. I suppose later never happens though :/
Re: [PATCH 03/10] sched: Clean-up struct sd_lb_stat
In reply to Peter ZijlstraQuoted 21 lines · Peter Zijlstra
From: Joonsoo Kim <[email protected]>
There is no reason to maintain separate variables for
this_groupandbusiest_groupinsd_lb_stat, except saving some space. But this structure is always allocated in stack, so this saving isn't really benificial [peterz: reducing stack space is good; in this case readability increases enough that I think its still beneficial]This patch unify these variables, so IMO, readability may be improved.
Signed-off-by Joonsoo Kim <[email protected]>[peterz: lots of style edits, a few fixes and a rename]Signed-off-by Peter Zijlstra <[email protected]>--- kernel/sched/fair.c | 225 +++++++++++++++++++++++++--------------------------- 1 file changed, 112 insertions(+), 113 deletions(-)
kernel/sched/fair.c static unsigned long task_h_load(struct · line 4277
Quoted 1 line
kernel/sched/fair.c +0
-0@@ -4277,36 +4277,6 @@ static unsigned long task_h_load(struct
[snip]...
kernel/sched/fair.c static int check_asym_packing(struct lb_ · line 4722
Quoted 5 lines
kernel/sched/fair.c +2
-2- env->imbalance =DIV_ROUND_CLOSEST ( - sds->max_load * sds->busiest->sgp->power,SCHED_POWER_SCALE ); + env->imbalance =DIV_ROUND_CLOSEST (sds->busiest_stat.avg_load * + sds->busiest->sgp->power,SCHED_POWER_SCALE );
I am wondering whether we could change this line as below is more appropriate, since it would avoid the division here:
env->imbalance = (sds->busiest_stat.avg_load * sds->busiest->sgp->power)
>> SCHED_POWER_SHIFT;I am not sure whether compiler would be smarter enough to covert into
kernel/sched/fair.c static unsigned long task_h_load(struct · line 4281
Quoted 1 line
kernel/sched/fair.c +0
-0> operation,
if it see SCHED_POWER_SCALE is 1024 here.
Thanks,
Lei
Re: [PATCH 03/10] sched: Clean-up struct sd_lb_stat
Quoted 30 lines · Lei Wen
Quoted 21 lines · Peter Zijlstra
From: Joonsoo Kim <[email protected]>
There is no reason to maintain separate variables for
this_groupandbusiest_groupinsd_lb_stat, except saving some space. But this structure is always allocated in stack, so this saving isn't really benificial [peterz: reducing stack space is good; in this case readability increases enough that I think its still beneficial]This patch unify these variables, so IMO, readability may be improved.
Signed-off-by Joonsoo Kim <[email protected]>[peterz: lots of style edits, a few fixes and a rename]Signed-off-by Peter Zijlstra <[email protected]>--- kernel/sched/fair.c | 225 +++++++++++++++++++++++++--------------------------- 1 file changed, 112 insertions(+), 113 deletions(-)kernel/sched/fair.c static unsigned long task_h_load(struct · line 4277
Quoted 1 line
kernel/sched/fair.c +0
-0@@ -4277,36 +4277,6 @@ static unsigned long task_h_load(struct[snip]...
kernel/sched/fair.c static int check_asym_packing(struct lb_ · line 4722
Quoted 5 lines
kernel/sched/fair.c +2
-2- env->imbalance =DIV_ROUND_CLOSEST ( - sds->max_load * sds->busiest->sgp->power,SCHED_POWER_SCALE ); + env->imbalance =DIV_ROUND_CLOSEST (sds->busiest_stat.avg_load * + sds->busiest->sgp->power,SCHED_POWER_SCALE );
Quoted 8 lines
I am wondering whether we could change this line as below is more appropriate, since it would avoid the division here:
env->imbalance = (sds->busiest_stat.avg_load * sds->busiest->sgp->power) >> SCHED_POWER_SHIFT;I am not sure whether compiler would be smarter enough to covert into
kernel/sched/fair.c static unsigned long task_h_load(struct · line 4281
Quoted 1 line
kernel/sched/fair.c +0
-0> operation,if it see
SCHED_POWER_SCALEis 1024 here.
This would change the rounding. Fortunately, gcc is smart enough to handle this.
Re: [PATCH 03/10] sched: Clean-up struct sd_lb_stat
Quoted 36 lines · Paul Turner
Quoted 35 lines · Lei Wen
Quoted 21 lines · Peter Zijlstra
From: Joonsoo Kim <[email protected]>
There is no reason to maintain separate variables for
this_groupandbusiest_groupinsd_lb_stat, except saving some space. But this structure is always allocated in stack, so this saving isn't really benificial [peterz: reducing stack space is good; in this case readability increases enough that I think its still beneficial]This patch unify these variables, so IMO, readability may be improved.
Signed-off-by Joonsoo Kim <[email protected]>[peterz: lots of style edits, a few fixes and a rename]Signed-off-by Peter Zijlstra <[email protected]>--- kernel/sched/fair.c | 225 +++++++++++++++++++++++++--------------------------- 1 file changed, 112 insertions(+), 113 deletions(-)kernel/sched/fair.c static unsigned long task_h_load(struct · line 4277
Quoted 1 line
kernel/sched/fair.c +0
-0@@ -4277,36 +4277,6 @@ static unsigned long task_h_load(struct[snip]...
kernel/sched/fair.c static int check_asym_packing(struct lb_ · line 4722
Quoted 5 lines
kernel/sched/fair.c +2
-2- env->imbalance =DIV_ROUND_CLOSEST ( - sds->max_load * sds->busiest->sgp->power,SCHED_POWER_SCALE ); + env->imbalance =DIV_ROUND_CLOSEST (sds->busiest_stat.avg_load * + sds->busiest->sgp->power,SCHED_POWER_SCALE );I am wondering whether we could change this line as below is more appropriate, since it would avoid the division here:
env->imbalance = (sds->busiest_stat.avg_load * sds->busiest->sgp->power) >> SCHED_POWER_SHIFT;
Quoted 6 lines
Quoted 3 lines
I am not sure whether compiler would be smarter enough to covert into
kernel/sched/fair.c static unsigned long task_h_load(struct · line 4281
Quoted 1 line
kernel/sched/fair.c +0
-0> operation,if it see
SCHED_POWER_SCALEis 1024 here.This would change the rounding. Fortunately, gcc is smart enough to handle this.
Indeed, I check the assembly code, and it is really smart to do the changes.
Thanks,
Lei
Peter Zijlstra
maintainerPATCH 4/10 sched, fair: Shrink sg_lb_stats and play memset games
In reply to Peter ZijlstraWe can shrink sg_lb_stats because rq::nr_running is an 'unsigned int' and cpu numbers are 'int'
Before:
sgs: /* size: 72, cachelines: 2, members: 10 */
sds: /* size: 184, cachelines: 3, members: 7 */
After:
sgs: /* size: 56, cachelines: 1, members: 10 */
sds: /* size: 152, cachelines: 3, members: 7 */
Further we can avoid clearing all of sds since we do a total clear/assignment of sg_stats in update_sg_lb_stats() with exception of busiest_stat.avg_load which is referenced in update_sd_pick_busiest().
--- kernel/sched/fair.c | 42 +++++++++++++++++++++++++++++++++++------- 1 file changed, 35 insertions(+), 7 deletions(-)
kernel/sched/fair.c +35 -7
@@ -4282,12 +4282,12 @@ static unsigned long task_h_load(structstruct sg_lb_stats {unsigned long avg_load;/*Avg load across the CPUs of the group */ unsigned long group_load;/* Total load over the CPUs of the group */ -unsigned long sum_nr_running;/* Nr tasks running in the group */ unsigned long sum_weighted_load;/* Weighted load of group's tasks */ unsigned long load_per_task; -unsigned long group_capacity; -unsigned long idle_cpus; -unsigned long group_weight; +unsigned int sum_nr_running;/* Nr tasks running in the group */ +unsigned int group_capacity; +unsigned int idle_cpus; +unsigned int group_weight;int group_imb;/* Is there an imbalance in the group ? */ int group_has_capacity;/* Is there extra capacity in the group? */ };
@@ -4303,10 +4303,38 @@ struct sd_lb_stats {unsigned long total_pwr;/* Total power of all groups in sd */ unsigned long avg_load;/* Average load across all groups in sd */ -struct sg_lb_stats this_stat;/* Statistics of this group */ struct sg_lb_stats busiest_stat;/* Statistics of the busiest group */ +struct sg_lb_stats this_stat;/* Statistics of this group */ }; +static inline void init_sd_lb_stats (struct sd_lb_stats *sds) +{ +/* +* struct sd_lb_stats { +* struct sched_group * busiest; // 0 8 +* struct sched_group * this; // 8 8 +* long unsigned int total_load; // 16 8 +* long unsigned int total_pwr; // 24 8 +* long unsigned int avg_load; // 32 8 +* struct sg_lb_stats { +* long unsigned int avg_load; // 40 8 +* long unsigned int group_load; // 48 8 +* ... +* } busiest_stat; // 40 56 +* struct sg_lb_stats this_stat; // 96 56 +* +* // size: 152, cachelines: 3, members: 7 +* // last cacheline: 24 bytes +* }; +* +* Skimp on the clearing to avoid duplicate work. We can avoid clearing +* this_stat because update_sg_lb_stats() does a full clear/assignment. +* We must however clear busiest_stat::avg_load because +* update_sd_pick_busiest() reads this before assignment. +*/ + memset(sds, 0, offsetof(struct sd_lb_stats, busiest_stat.group_load)); +} +/** * get_sd_load_idx - Obtain the load index for a given sched domain. * @sd: The sched_domain whose load_idx is to be obtained.
@@ -4665,7 +4693,7 @@ static inline void update_sd_lb_stats(st*/ if (prefer_sibling && !local_group && sds->this && sds->this_stat.group_has_capacity) - sgs->group_capacity =min (sgs->group_capacity,1UL ); + sgs->group_capacity =min (sgs->group_capacity,1U );/* Now, start updating sd_lb_stats */ sds->total_load += sgs->group_load;
@@ -4896,7 +4924,7 @@ static struct sched_group *find_busiest_struct sg_lb_stats *this, *busiest;struct sd_lb_stats sds; -memset (&sds,0 ,sizeof (sds)); +init_sd_lb_stats (&sds);/* * Compute the various statistics relavent for load balancing at
Re: [PATCH 04/10] sched, fair: Shrink sg_lb_stats and play memset games
Quoted 16 lines · Peter Zijlstra
kernel/sched/fair.c +16
-0+static inline void init_sd_lb_stats (struct sd_lb_stats *sds) +{ +/* +* struct sd_lb_stats { +* struct sched_group * busiest; // 0 8 +* struct sched_group * this; // 8 8 +* long unsigned int total_load; // 16 8 +* long unsigned int total_pwr; // 24 8 +* long unsigned int avg_load; // 32 8 +* struct sg_lb_stats { +* long unsigned int avg_load; // 40 8 +* long unsigned int group_load; // 48 8 +* ... +* } busiest_stat; // 40 56 +* struct sg_lb_stats this_stat; // 96 56 +*
kernel/sched/fair.c struct sd_lb_stats { · line 4335
Quoted 10 lines
kernel/sched/fair.c +10
-0+* // size: 152, cachelines: 3, members: 7 +* // last cacheline: 24 bytes +* }; +* +* Skimp on the clearing to avoid duplicate work. We can avoid clearing +* this_stat because update_sg_lb_stats() does a full clear/assignment. +* We must however clear busiest_stat::avg_load because +* update_sd_pick_busiest() reads this before assignment. +*/ + memset(sds, 0, offsetof(struct sd_lb_stats, busiest_stat.group_load));
Hello, Peter.
IMHO, this is so tricky.
With below change, we can simply do 'offsetof(struct sd_lb_stats, busiest_stat)'.
@@ -4546,7 +4546,7 @@ static bool update_sd_pick_busiest(struct lb_env *env,
struct sched_group *sg, struct sg_lb_stats *sgs)
{
- if (sgs->avg_load <= sds->busiest_stat.avg_load)
+ if (!sds->busiest && sgs->avg_load <= sds->busiest_stat.avg_load)
return false;
if (sgs->sum_nr_running > sgs->group_capacity)Thanks.
Re: [PATCH 04/10] sched, fair: Shrink sg_lb_stats and play memset games
Quoted 35 lines · Joonsoo Kim
Quoted 16 lines · Peter Zijlstra
kernel/sched/fair.c +16
-0+static inline void init_sd_lb_stats (struct sd_lb_stats *sds) +{ +/* +* struct sd_lb_stats { +* struct sched_group * busiest; // 0 8 +* struct sched_group * this; // 8 8 +* long unsigned int total_load; // 16 8 +* long unsigned int total_pwr; // 24 8 +* long unsigned int avg_load; // 32 8 +* struct sg_lb_stats { +* long unsigned int avg_load; // 40 8 +* long unsigned int group_load; // 48 8 +* ... +* } busiest_stat; // 40 56 +* struct sg_lb_stats this_stat; // 96 56 +* kernel/sched/fair.c struct sd_lb_stats { · line 4335
Quoted 10 lines
kernel/sched/fair.c +10
-0+* // size: 152, cachelines: 3, members: 7 +* // last cacheline: 24 bytes +* }; +* +* Skimp on the clearing to avoid duplicate work. We can avoid clearing +* this_stat because update_sg_lb_stats() does a full clear/assignment. +* We must however clear busiest_stat::avg_load because +* update_sd_pick_busiest() reads this before assignment. +*/ + memset(sds, 0, offsetof(struct sd_lb_stats, busiest_stat.group_load));Hello, Peter.
IMHO, this is so tricky.
With below change, we can simply do 'offsetof(struct sd_lb_stats, busiest_stat)'.
Review static bool update_sd_pick_busiest(struct lb_env *env, · line 4552
Quoted 8 lines
(quoted diff) +1
-1@@ -4546,7 +4546,7 @@ static bool update_sd_pick_busiest(struct lb_env *env, struct sched_group *sg, struct sg_lb_stats *sgs) { - if (sgs->avg_load <= sds->busiest_stat.avg_load) + if (!sds->busiest && sgs->avg_load <= sds->busiest_stat.avg_load) return false; if (sgs->sum_nr_running > sgs->group_capacity)
Sorry, instead of !sds->busiest, it should be sds->busiest. :)
Thanks.
Peter Zijlstra
maintainerRe: [PATCH 04/10] sched, fair: Shrink sg_lb_stats and play memset games
Quoted 10 lines · Joonsoo Kim
Quoted 10 lines
With below change, we can simply do '
offsetof(struct sd_lb_stats, busiest_stat)'.(quoted diff) +1
-1@@ -4546,7 +4546,7 @@ static bool update_sd_pick_busiest(struct lb_env *env, struct sched_group *sg, struct sg_lb_stats *sgs) { - if (sgs->avg_load <= sds->busiest_stat.avg_load) + if (!sds->busiest && sgs->avg_load <= sds->busiest_stat.avg_load) return false;
Quoted 4 lines
Review static bool update_sd_pick_busiest(struct lb_env *env, · line 4552
Quoted 2 lines
(quoted diff) +0
-0if (sgs->sum_nr_running > sgs->group_capacity)Sorry, instead of !sds->busiest, it should be
sds->busiest. :)
Of course ;-) However I'm not sure which I prefer.. adding this extra condition or having the initialization extra tricky. I'll sit on it a little longer.
Peter Zijlstra
maintainerRe: [PATCH 04/10] sched, fair: Shrink sg_lb_stats and play memset games
In reply to Joonsoo KimQuoted 30 lines · Joonsoo Kim
Quoted 16 lines · Peter Zijlstra
kernel/sched/fair.c +16
-0+static inline void init_sd_lb_stats (struct sd_lb_stats *sds) +{ +/* +* struct sd_lb_stats { +* struct sched_group * busiest; // 0 8 +* struct sched_group * this; // 8 8 +* long unsigned int total_load; // 16 8 +* long unsigned int total_pwr; // 24 8 +* long unsigned int avg_load; // 32 8 +* struct sg_lb_stats { +* long unsigned int avg_load; // 40 8 +* long unsigned int group_load; // 48 8 +* ... +* } busiest_stat; // 40 56 +* struct sg_lb_stats this_stat; // 96 56 +* kernel/sched/fair.c struct sd_lb_stats { · line 4335
Quoted 10 lines
kernel/sched/fair.c +10
-0+* // size: 152, cachelines: 3, members: 7 +* // last cacheline: 24 bytes +* }; +* +* Skimp on the clearing to avoid duplicate work. We can avoid clearing +* this_stat because update_sg_lb_stats() does a full clear/assignment. +* We must however clear busiest_stat::avg_load because +* update_sd_pick_busiest() reads this before assignment. +*/ + memset(sds, 0, offsetof(struct sd_lb_stats, busiest_stat.group_load));Hello, Peter.
Quoted 1 line
IMHO, this is so tricky.
Agreed, hence the somewhat elaborate comment :/
Review static bool update_sd_pick_busiest(struct lb_env *env, · line 4552
Quoted 11 lines
With below change, we can simply do '
offsetof(struct sd_lb_stats, busiest_stat)'.(quoted diff) +1
-1@@ -4546,7 +4546,7 @@ static bool update_sd_pick_busiest(struct lb_env *env, struct sched_group *sg, struct sg_lb_stats *sgs) { - if (sgs->avg_load <= sds->busiest_stat.avg_load) + if (!sds->busiest && sgs->avg_load <= sds->busiest_stat.avg_load) return false; if (sgs->sum_nr_running > sgs->group_capacity)
Indeed, thanks!
Re: [PATCH 04/10] sched, fair: Shrink sg_lb_stats and play memset games
In reply to Peter ZijlstraQuoted 63 lines · Peter Zijlstra
We can shrink
sg_lb_statsbecauserq::nr_runningis an 'unsigned int' and cpu numbers are 'int'Before:
sgs: /* size: 72, cachelines: 2, members: 10 */
sds: /* size: 184, cachelines: 3, members: 7 */After:
sgs: /* size: 56, cachelines: 1, members: 10 */
sds: /* size: 152, cachelines: 3, members: 7 */Further we can avoid clearing all of sds since we do a total clear/assignment of
sg_statsinupdate_sg_lb_stats()with exception of busiest_stat.avg_load which is referenced inupdate_sd_pick_busiest().Signed-off-by Peter Zijlstra <[email protected]>--- kernel/sched/fair.c | 42 +++++++++++++++++++++++++++++++++++------- 1 file changed, 35 insertions(+), 7 deletions(-)kernel/sched/fair.c +20
-5@@ -4282,12 +4282,12 @@ static unsigned long task_h_load(structstruct sg_lb_stats {unsigned long avg_load;/*Avg load across the CPUs of the group */ unsigned long group_load;/* Total load over the CPUs of the group */ -unsigned long sum_nr_running;/* Nr tasks running in the group */ unsigned long sum_weighted_load;/* Weighted load of group's tasks */ unsigned long load_per_task; -unsigned long group_capacity; -unsigned long idle_cpus; -unsigned long group_weight; +unsigned int sum_nr_running;/* Nr tasks running in the group */ +unsigned int group_capacity; +unsigned int idle_cpus; +unsigned int group_weight;int group_imb;/* Is there an imbalance in the group ? */ int group_has_capacity;/* Is there extra capacity in the group? */ };@@ -4303,10 +4303,38 @@ struct sd_lb_stats {unsigned long total_pwr;/* Total power of all groups in sd */ unsigned long avg_load;/* Average load across all groups in sd */ -struct sg_lb_stats this_stat;/* Statistics of this group */ struct sg_lb_stats busiest_stat;/* Statistics of the busiest group */ +struct sg_lb_stats this_stat;/* Statistics of this group */ }; +static inline void init_sd_lb_stats (struct sd_lb_stats *sds) +{ +/* +* struct sd_lb_stats { +* struct sched_group * busiest; // 0 8 +* struct sched_group * this; // 8 8 +* long unsigned int total_load; // 16 8 +* long unsigned int total_pwr; // 24 8 +* long unsigned int avg_load; // 32 8 +* struct sg_lb_stats { +* long unsigned int avg_load; // 40 8 +* long unsigned int group_load; // 48 8 +* ... +* } busiest_stat; // 40 56 +* struct sg_lb_stats this_stat; // 96 56
kernel/sched/fair.c struct sd_lb_stats { · line 4334
Quoted 10 lines
kernel/sched/fair.c +10
-0+* +* // size: 152, cachelines: 3, members: 7 +* // last cacheline: 24 bytes +* }; +* +* Skimp on the clearing to avoid duplicate work. We can avoid clearing +* this_stat because update_sg_lb_stats() does a full clear/assignment. +* We must however clear busiest_stat::avg_load because +* update_sd_pick_busiest() reads this before assignment. +*/
Does gcc seriously not get this right if we just write:
sds->busiest = NULL;
sds->local = NULL;
....
etc.?
Quoted 26 lines
kernel/sched/fair.c +5
-2+ memset(sds, 0, offsetof(struct sd_lb_stats, busiest_stat.group_load)); +} +/** * get_sd_load_idx - Obtain the load index for a given sched domain. * @sd: The sched_domain whose load_idx is to be obtained. @@ -4665,7 +4693,7 @@ static inline void update_sd_lb_stats(st*/ if (prefer_sibling && !local_group && sds->this && sds->this_stat.group_has_capacity) - sgs->group_capacity =min (sgs->group_capacity,1UL ); + sgs->group_capacity =min (sgs->group_capacity,1U );/* Now, start updating sd_lb_stats */ sds->total_load += sgs->group_load;@@ -4896,7 +4924,7 @@ static struct sched_group *find_busiest_struct sg_lb_stats *this, *busiest;struct sd_lb_stats sds; -memset (&sds,0 ,sizeof (sds)); +init_sd_lb_stats (&sds);/* * Compute the various statistics relavent for load balancing at
Peter Zijlstra
maintainerRe: [PATCH 04/10] sched, fair: Shrink sg_lb_stats and play memset games
Quoted 31 lines · Paul Turner
Quoted 15 lines
kernel/sched/fair.c +15
-0+static inline void init_sd_lb_stats (struct sd_lb_stats *sds) +{ +/* +* struct sd_lb_stats { +* struct sched_group * busiest; // 0 8 +* struct sched_group * this; // 8 8 +* long unsigned int total_load; // 16 8 +* long unsigned int total_pwr; // 24 8 +* long unsigned int avg_load; // 32 8 +* struct sg_lb_stats { +* long unsigned int avg_load; // 40 8 +* long unsigned int group_load; // 48 8 +* ... +* } busiest_stat; // 40 56 +* struct sg_lb_stats this_stat; // 96 56 kernel/sched/fair.c struct sd_lb_stats { · line 4334
Quoted 10 lines
kernel/sched/fair.c +10
-0+* +* // size: 152, cachelines: 3, members: 7 +* // last cacheline: 24 bytes +* }; +* +* Skimp on the clearing to avoid duplicate work. We can avoid clearing +* this_stat because update_sg_lb_stats() does a full clear/assignment. +* We must however clear busiest_stat::avg_load because +* update_sd_pick_busiest() reads this before assignment. +*/ Does gcc seriously not get this right if we just write:
sds->busiest= NULL;
sds->local= NULL;
....
Quoted 1 line
etc.?
There's a thought ;-) How about something like this?
sds = (struct sd_lb_stats){
.busiest = NULL,
.local = NULL,
.busiest_stat = {
.avg_load = 0,
},};
C99 named initializers should ignore all unmentioned fields, and I think we don't actually touch any of the other fields unless something is set.
Peter Zijlstra
maintainerPATCH 5/10 sched, fair: Remove duplicate load_per_task computations
In reply to Peter ZijlstraSince we already compute (but don't store) the sgs load_per_task value in update_sg_lb_stats() we might as well store it and not re-compute it later on.
--- kernel/sched/fair.c | 13 ++----------- 1 file changed, 2 insertions(+), 11 deletions(-)
kernel/sched/fair.c +2 -11
@@ -4504,7 +4504,6 @@ static inline void update_sg_lb_stats(st {unsigned long nr_running, max_nr_running, min_nr_running;unsigned long load, max_cpu_load, min_cpu_load; -unsigned long avg_load_per_task =0 ;int i;/* Tally up the load of all CPUs in the group */
@@ -4559,9 +4558,9 @@ static inline void update_sg_lb_stats(st* the hierarchy? */ if (sgs->sum_nr_running) - avg_load_per_task = sgs->sum_weighted_load / sgs->sum_nr_running; + sgs->load_per_task = sgs->sum_weighted_load / sgs->sum_nr_running; -if ((max_cpu_load - min_cpu_load) >= avg_load_per_task && +if ((max_cpu_load - min_cpu_load) >= sgs->load_per_task && (max_nr_running - min_nr_running) >1 ) sgs->group_imb =1 ;
@@ -4807,15 +4806,7 @@ static inline void calculate_imbalance(sstruct sg_lb_stats *this, *busiest; this = &sds->this_stat; -if (this->sum_nr_running) { - this->load_per_task = - this->sum_weighted_load / this->sum_nr_running; - } - busiest = &sds->busiest_stat; -/* busiest must have some tasks */ - busiest->load_per_task = - busiest->sum_weighted_load / busiest->sum_nr_running;if (busiest->group_imb) { busiest->load_per_task =
Peter Zijlstra
maintainerPATCH 6/10 sched, fair: Make group power more consitent
In reply to Peter ZijlstraFor easier access, less dereferences and more consisent value, store the group power in update_sg_lb_stats() and use it thereafter. The actual value in sched_group::sched_group_power::power can change throughout the load-balance pass if we're unlucky.
--- kernel/sched/fair.c | 49 ++++++++++++++++++++++++++----------------------- 1 file changed, 26 insertions(+), 23 deletions(-)
kernel/sched/fair.c +26 -23
@@ -4284,6 +4284,7 @@ struct sg_lb_stats {unsigned long group_load;/* Total load over the CPUs of the group */ unsigned long sum_weighted_load;/* Weighted load of group's tasks */ unsigned long load_per_task; +unsigned long group_power;unsigned int sum_nr_running;/* Nr tasks running in the group */ unsigned int group_capacity;unsigned int idle_cpus;
@@ -4320,11 +4321,11 @@ static inline void init_sd_lb_stats(stru* long unsigned int avg_load; // 40 8 * long unsigned int group_load; // 48 8 * ... -* } busiest_stat; // 40 56 -* struct sg_lb_stats this_stat; // 96 56 +* } busiest_stat; // 40 64 +* struct sg_lb_stats this_stat; // 104 64 * -* // size: 152, cachelines: 3, members: 7 -* // last cacheline: 24 bytes +* // size: 168, cachelines: 3, members: 7 +* // last cacheline: 40 bytes * }; * * Skimp on the clearing to avoid duplicate work. We can avoid clearing
@@ -4574,7 +4575,8 @@ static inline void update_sg_lb_stats(stupdate_group_power (env->sd, env->dst_cpu);/* Adjust by relative CPU power of the group */ - sgs->avg_load = (sgs->group_load*SCHED_POWER_SCALE ) / group->sgp->power; + sgs->group_power = group->sgp->power; + sgs->avg_load = (sgs->group_load*SCHED_POWER_SCALE ) / sgs->group_power;/* * Consider the group unbalanced when the imbalance is larger
@@ -4593,7 +4595,7 @@ static inline void update_sg_lb_stats(st sgs->group_imb =1 ; sgs->group_capacity = -DIV_ROUND_CLOSEST (group->sgp->power,SCHED_POWER_SCALE ); +DIV_ROUND_CLOSEST (sgs->group_power,SCHED_POWER_SCALE );if (!sgs->group_capacity) sgs->group_capacity =fix_small_capacity (env->sd, group);
@@ -4696,7 +4698,7 @@ static inline void update_sd_lb_stats(st/* Now, start updating sd_lb_stats */ sds->total_load += sgs->group_load; - sds->total_pwr += sg->sgp->power; + sds->total_pwr += sgs->group_power;if (!local_group &&update_sd_pick_busiest (env, sds, sg, sgs)) { sds->busiest = sg;
@@ -4744,8 +4746,9 @@ static int check_asym_packing(struct lb_if (env->dst_cpu > busiest_cpu)return 0 ; - env->imbalance =DIV_ROUND_CLOSEST (sds->busiest_stat.avg_load * - sds->busiest->sgp->power,SCHED_POWER_SCALE ); + env->imbalance =DIV_ROUND_CLOSEST ( + sds->busiest_stat.avg_load * sds->busiest_stat.group_power, +SCHED_POWER_SCALE );return 1 ; }
@@ -4775,7 +4778,7 @@ void fix_small_imbalance(struct lb_env * scaled_busy_load_per_task = (busiest->load_per_task *SCHED_POWER_SCALE ) / - sds->busiest->sgp->power; + busiest->group_power;if (busiest->avg_load - this->avg_load + scaled_busy_load_per_task >= (scaled_busy_load_per_task * imbn)) {
@@ -4789,32 +4792,32 @@ void fix_small_imbalance(struct lb_env ** moving them. */ - pwr_now += sds->busiest->sgp->power * + pwr_now += busiest->group_power *min (busiest->load_per_task, busiest->avg_load); - pwr_now += sds->this->sgp->power * + pwr_now += this->group_power *min (this->load_per_task, this->avg_load); pwr_now /=SCHED_POWER_SCALE ;/* Amount of load we'd subtract */ tmp = (busiest->load_per_task *SCHED_POWER_SCALE ) / - sds->busiest->sgp->power; + busiest->group_power;if (busiest->avg_load > tmp) { - pwr_move += sds->busiest->sgp->power * + pwr_move += busiest->group_power *min (busiest->load_per_task, busiest->avg_load - tmp); }/* Amount of load we'd add */ -if (busiest->avg_load * sds->busiest->sgp->power < +if (busiest->avg_load * busiest->group_power < busiest->load_per_task *SCHED_POWER_SCALE ) { - tmp = (busiest->avg_load * sds->busiest->sgp->power) / - sds->this->sgp->power; + tmp = (busiest->avg_load * busiest->group_power) / + this->group_power; }else { tmp = (busiest->load_per_task *SCHED_POWER_SCALE ) / - sds->this->sgp->power; + this->group_power; } - pwr_move += sds->this->sgp->power * -min (this->load_per_task, this->avg_load + tmp); + pwr_move += this->group_power * +min (this->load_per_task, this->avg_load + tmp); pwr_move /=SCHED_POWER_SCALE ;/* Move if we gain throughput */
@@ -4859,7 +4862,7 @@ static inline void calculate_imbalance(s (busiest->sum_nr_running - busiest->group_capacity); load_above_capacity *= (SCHED_LOAD_SCALE *SCHED_POWER_SCALE ); - load_above_capacity /= sds->busiest->sgp->power; + load_above_capacity /= busiest->group_power; }/*
@@ -4877,8 +4880,8 @@ static inline void calculate_imbalance(s/* How much load to actually move to equalise the imbalance */ env->imbalance =min ( - max_pull * sds->busiest->sgp->power, - (sds->avg_load - this->avg_load) * sds->this->sgp->power + max_pull * busiest->group_power, + (sds->avg_load - this->avg_load) * this->group_power ) /SCHED_POWER_SCALE ;/*
Re: [PATCH 06/10] sched, fair: Make group power more consitent
On 08/19/2013 09:31 PM, Peter Zijlstra wrote:
Peter Zijlstra
maintainerPATCH 7/10 sched, fair: Optimize find_busiest_queue()
In reply to Peter ZijlstraUse for_each_cpu_and() and thereby avoid computing the capacity for CPUs we know we're not interested in.
--- kernel/sched/fair.c | 5 +---- 1 file changed, 1 insertion(+), 4 deletions(-)
kernel/sched/fair.c +1 -4
@@ -4977,7 +4977,7 @@ static struct rq *find_busiest_queue(strunsigned long busiest_load =0 , busiest_power =SCHED_POWER_SCALE ;int i; -for_each_cpu (i,sched_group_cpus (group)) { +for_each_cpu_and (i,sched_group_cpus (group), env->cpus) {unsigned long power =power_of (i);unsigned long capacity =DIV_ROUND_CLOSEST (power,SCHED_POWER_SCALE );
@@ -4986,9 +4986,6 @@ static struct rq *find_busiest_queue(strif (!capacity) capacity =fix_small_capacity (env->sd, group); -if (!cpumask_test_cpu (i, env->cpus)) -continue ; - rq =cpu_rq (i); wl =weighted_cpuload (i);
Re: [PATCH 07/10] sched, fair: Optimize find_busiest_queue()
Hi Peter,
On 08/19/2013 09:31 PM, Peter Zijlstra wrote:
In the load balancing code, looks to me that cpumask_copy(cpus, cpu_active_mask) is not updating the env.cpus at all, before calling find_busiest_group(). Am I missing something?
Should not cpumask_copy() below be before we update the env.cpus parameter?
static int load_balance(int this_cpu, struct rq *this_rq,
struct sched_domain *sd, enum cpu_idle_type idle, int *balance)
{
int ld_moved, cur_ld_moved, active_balance = 0;
struct sched_group *group;
struct rq *busiest;
unsigned long flags;
struct cpumask *cpus = __get_cpu_var(load_balance_mask);
struct lb_env env = {
.sd = sd,
.dst_cpu = this_cpu,
.dst_rq = this_rq,
.dst_grpmask = sched_group_cpus(sd->groups),
.idle = idle,
.loop_break = sched_nr_migrate_break,
.cpus = cpus,
};
/*
* For NEWLY_IDLE load_balancing, we don't need to consider
* other cpus in our group
*/
if (idle == CPU_NEWLY_IDLE)
env.dst_grpmask = NULL;
cpumask_copy(cpus, cpu_active_mask);
schedstat_inc(sd, lb_count[idle]);
redo:
group = find_busiest_group(&env, balance);Regards
Preeti U Murthy
Peter Zijlstra
maintainerRe: [PATCH 07/10] sched, fair: Optimize find_busiest_queue()
Quoted 9 lines · Preeti U Murthy
Hi Peter,
On 08/19/2013 09:31 PM, Peter Zijlstra wrote:
In the load balancing code, looks to me that
cpumask_copy(cpus, cpu_active_mask)is not updating the env.cpus at all, before callingfind_busiest_group(). Am I missing something?Should not
cpumask_copy()below be before we update the env.cpus parameter?
Nah, its all pointers.
Preeti U Murthy
Reviewed-byRe: [PATCH 07/10] sched, fair: Optimize find_busiest_queue()
Quoted 5 lines · Peter Zijlstra
Quoted 4 lines · Preeti U Murthy
Hi Peter,
On 08/19/2013 09:31 PM, Peter Zijlstra wrote:
Quoted 8 lines
Quoted 5 lines
In the load balancing code, looks to me that
cpumask_copy(cpus, cpu_active_mask)is not updating the env.cpus at all, before callingfind_busiest_group(). Am I missing something?Should not
cpumask_copy()below be before we update the env.cpus parameter?Nah, its all pointers.
Yikes! Of course :P
Re: [PATCH 07/10] sched, fair: Optimize find_busiest_queue()
In reply to Peter ZijlstraQuoted 20 lines · Peter Zijlstra
Use
for_each_cpu_and()and thereby avoid computing the capacity for CPUs we know we're not interested in.Signed-off-by Peter Zijlstra <[email protected]>--- kernel/sched/fair.c | 5 +---- 1 file changed, 1 insertion(+), 4 deletions(-)kernel/sched/fair.c +1
-1@@ -4977,7 +4977,7 @@ static struct rq *find_busiest_queue(strunsigned long busiest_load =0 , busiest_power =SCHED_POWER_SCALE ;int i; -for_each_cpu (i,sched_group_cpus (group)) { +for_each_cpu_and (i,sched_group_cpus (group), env->cpus) {unsigned long power =power_of (i);unsigned long capacity =DIV_ROUND_CLOSEST (power,SCHED_POWER_SCALE );
kernel/sched/fair.c static struct rq *find_busiest_queue(str · line 4990
Quoted 8 lines
kernel/sched/fair.c +0
-3@@ -4986,9 +4986,6 @@ static struct rq *find_busiest_queue(strif (!capacity) capacity =fix_small_capacity (env->sd, group); -if (!cpumask_test_cpu (i, env->cpus)) -continue ; - rq =cpu_rq (i); wl =weighted_cpuload (i);
There's no need to actually do the divisions immediately below this also.
e.g.
unsigned long max_load_power = SCHED_POWER_SCALE;
...
if (wl * max_load_power > max_load * power) {
max_load = wl;
max_load_power = power;
...
This would actually end up being a little more accurate even.
[ Alternatively without caching max_load_power we could compare wl * power vs max_load * SCHED_POWER_SCALE. ]
Peter Zijlstra
maintainerRe: [PATCH 07/10] sched, fair: Optimize find_busiest_queue()
Quoted 31 lines · Paul Turner
Quoted 11 lines · Peter Zijlstra
+++
b/kernel/sched/fair.c(quoted diff) +1
-1@@ -4977,7 +4977,7 @@ static struct rq *find_busiest_queue(str unsigned long busiest_load = 0, busiest_power = SCHED_POWER_SCALE; int i; - for_each_cpu(i, sched_group_cpus(group)) { + for_each_cpu_and(i, sched_group_cpus(group), env->cpus) { unsigned long power = power_of(i); unsigned long capacity = DIV_ROUND_CLOSEST(power, SCHED_POWER_SCALE);Review static struct rq *find_busiest_queue(str · line 4990
Quoted 8 lines
(quoted diff) +0
-3@@ -4986,9 +4986,6 @@ static struct rq *find_busiest_queue(str if (!capacity) capacity = fix_small_capacity(env->sd, group); - if (!cpumask_test_cpu(i, env->cpus)) - continue; - rq = cpu_rq(i); wl = weighted_cpuload(i);There's no need to actually do the divisions immediately below this also.
e.g.
unsigned longmax_load_power=SCHED_POWER_SCALE;
...if (wl * max_load_power > max_load * power) { max_load = wl; max_load_power = power; ...
Quoted 4 lines
This would actually end up being a little more accurate even.
[ Alternatively without caching
max_load_powerwe could compare wl * power vsmax_load*SCHED_POWER_SCALE. ]
You've got me confused again. You're talking about something like the below?
I suppose the problem with that is that we could keep selecting the busiest rq with an unmovable task due to:
move_tasks():
if ((load / 2) > env->imbalance) goto next;
That said, the condition in fbq() should at least be modified to match this. Now the entire capacity crap comes from:
bdb94aa sched: Try to deal with low capacity
But thinking a little more about it, if power drops that low imbalance is likely to be _huge_ and we'd not meet that condition. Now if only I wrote a more comprehensive Changelog and explained why that wouldn't be the case. /me kicks himself.
---
kernel/sched/fair.c +3 -19
@@ -4990,28 +4990,12 @@ static struct sched_group *find_busiest_static struct rq *find_busiest_queue (struct lb_env *env,struct sched_group *group) { -struct rq *busiest =NULL , *rq;unsigned long busiest_load =0 , busiest_power =1 ; +struct rq *busiest =NULL ;int i;for_each_cpu_and (i,sched_group_cpus (group), env->cpus) { -unsigned long power =power_of (i); -unsigned long capacity =DIV_ROUND_CLOSEST (power, -SCHED_POWER_SCALE ); -unsigned long wl; - -if (!capacity) - capacity =fix_small_capacity (env->sd, group); - - rq =cpu_rq (i); - wl =weighted_cpuload (i); - -/* -* When comparing with imbalance, use weighted_cpuload() -* which is not scaled with the cpu power. -*/ -if (capacity && rq->nr_running ==1 && wl > env->imbalance) -continue ; +unsigned long wl =weighted_cpuload (i);/* * For the load comparisons with the other cpu's, consider
@@ -5027,7 +5011,7 @@ static struct rq *find_busiest_queue(strif (wl * busiest_power > busiest_load * power) { busiest_load = wl; busiest_power = power; - busiest = rq; + busiest =cpu_rq (i); } }
Re: [PATCH 07/10] sched, fair: Optimize find_busiest_queue()
Quoted 32 lines · Peter Zijlstra
Quoted 31 lines · Paul Turner
Quoted 11 lines · Peter Zijlstra
+++
b/kernel/sched/fair.c(quoted diff) +1
-1@@ -4977,7 +4977,7 @@ static struct rq *find_busiest_queue(str unsigned long busiest_load = 0, busiest_power = SCHED_POWER_SCALE; int i; - for_each_cpu(i, sched_group_cpus(group)) { + for_each_cpu_and(i, sched_group_cpus(group), env->cpus) { unsigned long power = power_of(i); unsigned long capacity = DIV_ROUND_CLOSEST(power, SCHED_POWER_SCALE);Review static struct rq *find_busiest_queue(str · line 4990
Quoted 8 lines
(quoted diff) +0
-3@@ -4986,9 +4986,6 @@ static struct rq *find_busiest_queue(str if (!capacity) capacity = fix_small_capacity(env->sd, group); - if (!cpumask_test_cpu(i, env->cpus)) - continue; - rq = cpu_rq(i); wl = weighted_cpuload(i);There's no need to actually do the divisions immediately below this also.
e.g.
unsigned longmax_load_power=SCHED_POWER_SCALE;
...if (wl * max_load_power > max_load * power) { max_load = wl; max_load_power = power; ...
Quoted 7 lines
Quoted 4 lines
This would actually end up being a little more accurate even.
[ Alternatively without caching
max_load_powerwe could compare wl * power vsmax_load*SCHED_POWER_SCALE. ]You've got me confused again. You're talking about something like the below?
Nevermind, I was looking at a tip tree as I reviewed this one. What I was suggesting was exactly:
"[PATCH 01/10] sched: Remove one division operation in find_busiest_queue()"
Quoted 62 lines
I suppose the problem with that is that we could keep selecting the busiest rq with an unmovable task due to:
move_tasks():if ((load / 2) > env->imbalance) goto next;That said, the condition in
fbq()should at least be modified to match this. Now the entire capacity crap comes from:bdb94aa sched: Try to deal with low capacity
But thinking a little more about it, if power drops that low imbalance is likely to be _huge_ and we'd not meet that condition. Now if only I wrote a more comprehensive Changelog and explained why that wouldn't be the case. /me kicks himself.
---
kernel/sched/fair.c +3
-19@@ -4990,28 +4990,12 @@ static struct sched_group *find_busiest_static struct rq *find_busiest_queue (struct lb_env *env,struct sched_group *group) { -struct rq *busiest =NULL , *rq;unsigned long busiest_load =0 , busiest_power =1 ; +struct rq *busiest =NULL ;int i;for_each_cpu_and (i,sched_group_cpus (group), env->cpus) { -unsigned long power =power_of (i); -unsigned long capacity =DIV_ROUND_CLOSEST (power, -SCHED_POWER_SCALE ); -unsigned long wl; - -if (!capacity) - capacity =fix_small_capacity (env->sd, group); - - rq =cpu_rq (i); - wl =weighted_cpuload (i); - -/* -* When comparing with imbalance, use weighted_cpuload() -* which is not scaled with the cpu power. -*/ -if (capacity && rq->nr_running ==1 && wl > env->imbalance) -continue ; +unsigned long wl =weighted_cpuload (i);/* * For the load comparisons with the other cpu's, consider @@ -5027,7 +5011,7 @@ static struct rq *find_busiest_queue(strif (wl * busiest_power > busiest_load * power) { busiest_load = wl; busiest_power = power; - busiest = rq; + busiest =cpu_rq (i); } }
Peter Zijlstra
maintainerPATCH 8/10 sched, fair: Rework and comment the group_imb code
In reply to Peter ZijlstraRik reported some weirdness due to the group_imb code. As a start to looking at it, clean it up a little and add a few explanatory comments.
--- kernel/sched/fair.c | 123 +++++++++++++++++++++++++++++++++++++--------------- 1 file changed, 89 insertions(+), 34 deletions(-)
kernel/sched/fair.c +89 -34
@@ -4491,6 +4491,81 @@ fix_small_capacity(struct sched_domain *return 0 ; } +/* +* Group imbalance indicates (and tries to solve) the problem where balancing +* groups is inadequate due to tsk_cpus_allowed() constraints. +* +* Imagine a situation of two groups of 4 cpus each and 4 tasks each with a +* cpumask covering 1 cpu of the first group and 3 cpus of the second group. +* Something like: +* +* { 0 1 2 3 } { 4 5 6 7 } +* * * * * +* +* If we were to balance group-wise we'd place two tasks in the first group and +* two tasks in the second group. Clearly this is undesired as it will overload +* cpu 3 and leave one of the cpus in the second group unused. +* +* The current solution to this issue is detecting the skew in the first group +* by noticing it has a cpu that is overloaded while the remaining cpus are +* idle -- or rather, there's a distinct imbalance in the cpus; see +* sg_imbalanced(). +* +* When this is so detected; this group becomes a candidate for busiest; see +* update_sd_pick_busiest(). And calculcate_imbalance() and +* find_busiest_group() avoid some of the usual balance conditional to allow it +* to create an effective group imbalance. +* +* This is a somewhat tricky proposition since the next run might not find the +* group imbalance and decide the groups need to be balanced again. A most +* subtle and fragile situation. +*/ + +struct sg_imb_stats { +unsigned long max_nr_running, min_nr_running; +unsigned long max_cpu_load, min_cpu_load; +}; + +static inline void init_sg_imb_stats (struct sg_imb_stats *sgi) +{ + sgi->max_cpu_load = sgi->max_nr_running =0UL ; + sgi->min_cpu_load = sgi->min_nr_running = ~0UL ; +} + +static inline void +update_sg_imb_stats (struct sg_imb_stats *sgi, +unsigned long load,unsigned long nr_running) +{ +if (load > sgi->max_cpu_load) + sgi->max_cpu_load = load; +if (sgi->min_cpu_load > load) + sgi->min_cpu_load = load; + +if (nr_running > sgi->max_nr_running) + sgi->max_nr_running = nr_running; +if (sgi->min_nr_running > nr_running) + sgi->min_nr_running = nr_running; +} + +static inline int +sg_imbalanced (struct sg_lb_stats *sgs,struct sg_imb_stats *sgi) +{ +/* +* Consider the group unbalanced when the imbalance is larger +* than the average weight of a task. +* +* APZ: with cgroup the avg task weight can vary wildly and +* might not be a suitable number - should we keep a +* normalized nr_running number somewhere that negates +* the hierarchy? +*/ +if ((sgi->max_cpu_load - sgi->min_cpu_load) >= sgs->load_per_task && + (sgi->max_nr_running - sgi->min_nr_running) >1 ) +return 1 ; + +return 0 ; +} +/** * update_sg_lb_stats - Update sched_group's statistics for load balancing. * @env: The load balancing environment.
@@ -4503,15 +4578,12 @@ static inline void update_sg_lb_stats(st struct sched_group *group, int load_idx, int local_group, struct sg_lb_stats *sgs) { - unsigned long nr_running, max_nr_running, min_nr_running; -unsigned long load, max_cpu_load, min_cpu_load; + struct sg_imb_stats sgi; +unsigned long nr_running; +unsigned long load;int i; -/* Tally up the load of all CPUs in the group */ - max_cpu_load =0 ; - min_cpu_load = ~0UL ; - max_nr_running =0 ; - min_nr_running = ~0UL ; +init_sg_imb_stats (&sgi);for_each_cpu_and (i,sched_group_cpus (group), env->cpus) {struct rq *rq =cpu_rq (i);
@@ -4523,16 +4595,7 @@ static inline void update_sg_lb_stats(st load =target_load (i, load_idx); }else { load =source_load (i, load_idx); - -if (load > max_cpu_load) - max_cpu_load = load; -if (min_cpu_load > load) - min_cpu_load = load; - -if (nr_running > max_nr_running) - max_nr_running = nr_running; -if (min_nr_running > nr_running) - min_nr_running = nr_running; +update_sg_imb_stats (&sgi, load, nr_running); } sgs->group_load += load;
@@ -4550,21 +4613,10 @@ static inline void update_sg_lb_stats(st sgs->group_power = group->sgp->power; sgs->avg_load = (sgs->group_load*SCHED_POWER_SCALE ) / sgs->group_power; -/* -* Consider the group unbalanced when the imbalance is larger -* than the average weight of a task. -* -* APZ: with cgroup the avg task weight can vary wildly and -* might not be a suitable number - should we keep a -* normalized nr_running number somewhere that negates -* the hierarchy? -*/ if (sgs->sum_nr_running) sgs->load_per_task = sgs->sum_weighted_load / sgs->sum_nr_running; -if ((max_cpu_load - min_cpu_load) >= sgs->load_per_task && - (max_nr_running - min_nr_running) >1 ) - sgs->group_imb =1 ; + sgs->group_imb =sg_imbalanced (sgs, &sgi); sgs->group_capacity =DIV_ROUND_CLOSEST (sgs->group_power,SCHED_POWER_SCALE );
@@ -4812,6 +4864,10 @@ static inline void calculate_imbalance(s busiest = &sds->busiest_stat;if (busiest->group_imb) { +/* +* In the group_imb case we cannot rely on group-wide averages +* to ensure cpu-load equilibrium, look at wider averages. XXX +*/ busiest->load_per_task =min (busiest->load_per_task, sds->avg_load); }
@@ -4829,6 +4885,8 @@ static inline void calculate_imbalance(sif (!busiest->group_imb) {/* * Don't want to pull so many tasks that a group would go idle. +* Except of course for the group_imb case, since then we might +* have to drop below capacity to reach cpu-load equilibrium. */ load_above_capacity = (busiest->sum_nr_running - busiest->group_capacity);
@@ -4844,11 +4902,8 @@ static inline void calculate_imbalance(s* we also don't want to reduce the group load below the group capacity * (so that we can implement power-savings policies etc). Thus we look * for the minimum possible imbalance. -* Be careful of negative numbers as they'll appear as very large values -* with unsigned longs. */ - max_pull =min (busiest->avg_load - sds->avg_load, - load_above_capacity); + max_pull =min (busiest->avg_load - sds->avg_load, load_above_capacity);/* How much load to actually move to equalise the imbalance */ env->imbalance = min(
@@ -4912,7 +4967,7 @@ static struct sched_group *find_busiest_/* * If the busiest group is imbalanced the below checks don't -* work because they assumes all things are equal, which typically +* work because they assume all things are equal, which typically * isn't true due to cpus_allowed constraints and the like. */ if (busiest->group_imb)
Peter Zijlstra
maintainerPATCH 9/10 sched, fair: Fix the sd_parent_degenerate() code
In reply to Peter ZijlstraI found that on my wsm box I had a redundant domain:
[ 0.949769] CPU0 attaching sched-domain: [ 0.953765] domain 0: span 0,12 level SIBLING [ 0.958335] groups: 0 (cpu_power = 587) 12 (cpu_power = 588) [ 0.964548] domain 1: span 0-5,12-17 level MC [ 0.969206] groups: 0,12 (cpu_power = 1175) 1,13 (cpu_power = 1176) 2,14 (cpu_power = 1176) 3,15 (cpu_power = 1176) 4,16 (cpu_power = 1176) 5,17 (cpu_power = 1176) [ 0.984993] domain 2: span 0-5,12-17 level CPU [ 0.989822] groups: 0-5,12-17 (cpu_power = 7055) [ 0.995049] domain 3: span 0-23 level NUMA [ 0.999620] groups: 0-5,12-17 (cpu_power = 7055) 6-11,18-23 (cpu_power = 7056)
Note how domain 2 has only a single group and spans the same CPUs as domain 1. We should not keep such domains and do in fact have code to prune these.
It turns out that the 'new' SD_PREFER_SIBLING flag causes this, it makes sd_parent_degenerate() fail on the CPU domain. We can easily fix this by 'ignoring' the SD_PREFER_SIBLING bit and transfering it to whatever domain ends up covering the span.
With this patch the domains now look like this:
[ 0.950419] CPU0 attaching sched-domain: [ 0.954454] domain 0: span 0,12 level SIBLING [ 0.959039] groups: 0 (cpu_power = 587) 12 (cpu_power = 588) [ 0.965271] domain 1: span 0-5,12-17 level MC [ 0.969936] groups: 0,12 (cpu_power = 1175) 1,13 (cpu_power = 1176) 2,14 (cpu_power = 1176) 3,15 (cpu_power = 1176) 4,16 (cpu_power = 1176) 5,17 (cpu_power = 1176) [ 0.985737] domain 2: span 0-23 level NUMA [ 0.990231] groups: 0-5,12-17 (cpu_power = 7055) 6-11,18-23 (cpu_power = 7056)
--- kernel/sched/core.c | 10 +++++++++- 1 file changed, 9 insertions(+), 1 deletion(-)
kernel/sched/core.c +9 -1
@@ -4948,7 +4948,8 @@ sd_parent_degenerate(struct sched_domainSD_BALANCE_FORK |SD_BALANCE_EXEC |SD_SHARE_CPUPOWER | - SD_SHARE_PKG_RESOURCES); +SD_SHARE_PKG_RESOURCES | + SD_PREFER_SIBLING);if (nr_node_ids ==1 ) pflags &= ~SD_SERIALIZE ; }
@@ -5157,6 +5158,13 @@ cpu_attach_domain(struct sched_domain *s tmp->parent = parent->parent;if (parent->parent) parent->parent->child = tmp; +/* +* Transfer SD_PREFER_SIBLING down in case of a +* degenerate parent; the spans match for this +* so the property transfers. +*/ +if (parent->flags &SD_PREFER_SIBLING ) + tmp->flags |=SD_PREFER_SIBLING ;destroy_sched_domain (parent, cpu); }else tmp = tmp->parent;
Re: [PATCH 09/10] sched, fair: Fix the sd_parent_degenerate() code
Quoted 53 lines · Peter Zijlstra
I found that on my wsm box I had a redundant domain:
[ 0.949769] CPU0 attaching sched-domain: [ 0.953765] domain 0: span 0,12 level SIBLING [ 0.958335] groups: 0 (cpu_power = 587) 12 (cpu_power = 588) [ 0.964548] domain 1: span 0-5,12-17 level MC [ 0.969206] groups: 0,12 (cpu_power = 1175) 1,13 (cpu_power = 1176) 2,14 (cpu_power = 1176) 3,15 (cpu_power = 1176) 4,16 (cpu_power = 1176) 5,17 (cpu_power = 1176) [ 0.984993] domain 2: span 0-5,12-17 level CPU [ 0.989822] groups: 0-5,12-17 (cpu_power = 7055) [ 0.995049] domain 3: span 0-23 level NUMA [ 0.999620] groups: 0-5,12-17 (cpu_power = 7055) 6-11,18-23 (cpu_power = 7056)Note how domain 2 has only a single group and spans the same CPUs as domain 1. We should not keep such domains and do in fact have code to prune these.
It turns out that the 'new'
SD_PREFER_SIBLINGflag causes this, it makessd_parent_degenerate()fail on the CPU domain. We can easily fix this by 'ignoring' theSD_PREFER_SIBLINGbit and transfering it to whatever domain ends up covering the span.With this patch the domains now look like this:
[ 0.950419] CPU0 attaching sched-domain: [ 0.954454] domain 0: span 0,12 level SIBLING [ 0.959039] groups: 0 (cpu_power = 587) 12 (cpu_power = 588) [ 0.965271] domain 1: span 0-5,12-17 level MC [ 0.969936] groups: 0,12 (cpu_power = 1175) 1,13 (cpu_power = 1176) 2,14 (cpu_power = 1176) 3,15 (cpu_power = 1176) 4,16 (cpu_power = 1176) 5,17 (cpu_power = 1176) [ 0.985737] domain 2: span 0-23 level NUMA [ 0.990231] groups: 0-5,12-17 (cpu_power = 7055) 6-11,18-23 (cpu_power = 7056)Signed-off-by Peter Zijlstra <[email protected]>--- kernel/sched/core.c | 10 +++++++++- 1 file changed, 9 insertions(+), 1 deletion(-)kernel/sched/core.c +2
-1@@ -4948,7 +4948,8 @@ sd_parent_degenerate(struct sched_domainSD_BALANCE_FORK |SD_BALANCE_EXEC |SD_SHARE_CPUPOWER | - SD_SHARE_PKG_RESOURCES); +SD_SHARE_PKG_RESOURCES | + SD_PREFER_SIBLING);if (nr_node_ids ==1 ) pflags &= ~SD_SERIALIZE ; }@@ -5157,6 +5158,13 @@ cpu_attach_domain(struct sched_domain *s tmp->parent = parent->parent;if (parent->parent) parent->parent->child = tmp;
kernel/sched/core.c cpu_attach_domain(struct sched_domain *s · line 5170
Quoted 10 lines
kernel/sched/core.c +7
-0+/* +* Transfer SD_PREFER_SIBLING down in case of a +* degenerate parent; the spans match for this +* so the property transfers. +*/ +if (parent->flags &SD_PREFER_SIBLING ) + tmp->flags |=SD_PREFER_SIBLING ;destroy_sched_domain (parent, cpu); }else tmp = tmp->parent;
Peter Zijlstra
maintainerRe: [PATCH 09/10] sched, fair: Fix the sd_parent_degenerate() code
Quoted 9 lines · Paul Turner
Quoted 9 lines
kernel/sched/core.c +5
-0@@ -5157,6 +5158,13 @@ cpu_attach_domain(struct sched_domain *s tmp->parent = parent->parent;if (parent->parent) parent->parent->child = tmp; +/* +* Transfer SD_PREFER_SIBLING down in case of a +* degenerate parent; the spans match for this +* so the property transfers. +*/
Quoted 8 lines
kernel/sched/core.c cpu_attach_domain(struct sched_domain *s · line 5170
Quoted 6 lines
kernel/sched/core.c +2
-0+if (parent->flags &SD_PREFER_SIBLING ) + tmp->flags |=SD_PREFER_SIBLING ;destroy_sched_domain (parent, cpu); }else tmp = tmp->parent;Reviewed-by Paul Turner <[email protected]>
BTW, did that comment make sense to you or would you suggest something different? I had/am having a hard time with that comment. Somehow it leaves me wanting. I know I understand the issue now, but I'll doubt the comment will suffice in a years time :/
Re: [PATCH 09/10] sched, fair: Fix the sd_parent_degenerate() code
Quoted 19 lines · Peter Zijlstra
Quoted 9 lines · Paul Turner
Quoted 9 lines
kernel/sched/core.c +5
-0@@ -5157,6 +5158,13 @@ cpu_attach_domain(struct sched_domain *s tmp->parent = parent->parent;if (parent->parent) parent->parent->child = tmp; +/* +* Transfer SD_PREFER_SIBLING down in case of a +* degenerate parent; the spans match for this +* so the property transfers. +*/ Quoted 8 lines
kernel/sched/core.c cpu_attach_domain(struct sched_domain *s · line 5170
Quoted 6 lines
kernel/sched/core.c +2
-0+if (parent->flags &SD_PREFER_SIBLING ) + tmp->flags |=SD_PREFER_SIBLING ;destroy_sched_domain (parent, cpu); }else tmp = tmp->parent;Reviewed-by Paul Turner <[email protected]>
Quoted 4 lines
BTW, did that comment make sense to you or would you suggest something different? I had/am having a hard time with that comment. Somehow it leaves me wanting. I know I understand the issue now, but I'll doubt the comment will suffice in a years time :/
The comment made sense to me :)
Signature · 1 line
All rights reversed.
Re: [PATCH 09/10] sched, fair: Fix the sd_parent_degenerate() code
Quoted 20 lines · Rik van Riel
Quoted 19 lines · Peter Zijlstra
Quoted 17 lines · Paul Turner
Quoted 5 lines
kernel/sched/core.c +0
-0@@ -5157,6 +5158,13 @@ cpu_attach_domain(struct sched_domain *s tmp->parent = parent->parent;if (parent->parent) parent->parent->child = tmp;kernel/sched/core.c cpu_attach_domain(struct sched_domain *s · line 5170
Quoted 10 lines
kernel/sched/core.c +7
-0+/* +* Transfer SD_PREFER_SIBLING down in case of a +* degenerate parent; the spans match for this +* so the property transfers. +*/ +if (parent->flags &SD_PREFER_SIBLING ) + tmp->flags |=SD_PREFER_SIBLING ;destroy_sched_domain (parent, cpu); }else tmp = tmp->parent;Reviewed-by Paul Turner <[email protected]>
Quoted 6 lines
Quoted 4 lines
BTW, did that comment make sense to you or would you suggest something different? I had/am having a hard time with that comment. Somehow it leaves me wanting. I know I understand the issue now, but I'll doubt the comment will suffice in a years time :/
The comment made sense to me :)
It makes sense once you read the code. That we push down is somehow counter intuitive in the reading.
Quoted 3 lines
--
All rights reversed.
Peter Zijlstra
maintainerRFC PATCH 10/10 sched, fair: Rewrite group_imb trigger
In reply to Peter ZijlstraChange the group_imb detection from the old 'load-spike' detector to an actual imbalance detector. We set it from the lower domain balance pass when it fails to create a balance in the presence of task affinities.
The advantage is that this should no longer generate the false positive group_imb conditions generated by transient load spikes from the normal balancing/bulk-wakeup etc. behaviour.
While I haven't actually observed those they could happen.
I'm not entirely happy with this patch; it somehow feels a little fragile.
Nor does it solve the biggest issue I have with the group_imb code; it it still a fragile construct in that once we 'fixed' the imbalance we'll not detect the group_imb again and could end up re-creating it.
That said, this patch does seem to preserve behaviour for the described degenerate case. In particular on my 2*6*2 wsm-ep:
taskset -c 3-11 bash -c 'for ((i=0;i<9;i++)) do while :; do :; done & done'
ends up with 9 spinners, each on their own CPU; whereas if you disable the group_imb code that typically doesn't happen (you'll get one pair sharing a CPU most of the time).
--- kernel/sched/fair.c | 90 +++++++++++++++++---------------------------------- kernel/sched/sched.h | 1 2 files changed, 31 insertions(+), 60 deletions(-)
kernel/sched/fair.c +30 -60
@@ -3906,7 +3906,8 @@ static unsigned long __read_mostly max_l#define LBF_ALL_PINNED 0x01#define LBF_NEED_BREAK 0x02 -#define LBF_SOME_PINNED 0x04 +#define LBF_DST_PINNED 0x04 +#define LBF_SOME_PINNED 0x08struct lb_env {struct sched_domain *sd;
@@ -3997,6 +3998,8 @@ int can_migrate_task(struct task_structschedstat_inc (p, se.statistics.nr_failed_migrations_affine); + env->flags |=LBF_SOME_PINNED ; +/* * Remember if this task can be migrated to any other cpu in * our sched_group. We may want to revisit it if we couldn't
@@ -4005,13 +4008,13 @@ int can_migrate_task(struct task_struct* Also avoid computing new_dst_cpu if we have already computed * one in current iteration. */ -if (!env->dst_grpmask || (env->flags &LBF_SOME_PINNED )) +if (!env->dst_grpmask || (env->flags &LBF_DST_PINNED ))return 0 ;/* Prevent to re-select dst_cpu via env's cpus */ for_each_cpu_and (cpu, env->dst_grpmask, env->cpus) {if (cpumask_test_cpu (cpu,tsk_cpus_allowed (p))) { - env->flags |=LBF_SOME_PINNED ; + env->flags |=LBF_DST_PINNED ; env->new_dst_cpu = cpu;break ; }
@@ -4535,13 +4538,12 @@ fix_small_capacity(struct sched_domain ** cpu 3 and leave one of the cpus in the second group unused. * * The current solution to this issue is detecting the skew in the first group -* by noticing it has a cpu that is overloaded while the remaining cpus are -* idle -- or rather, there's a distinct imbalance in the cpus; see -* sg_imbalanced(). +* by noticing the lower domain failed to reach balance and had difficulty +* moving tasks due to affinity constraints. * * When this is so detected; this group becomes a candidate for busiest; see * update_sd_pick_busiest(). And calculcate_imbalance() and -* find_busiest_group() avoid some of the usual balance conditional to allow it +* find_busiest_group() avoid some of the usual balance conditions to allow it * to create an effective group imbalance. * * This is a somewhat tricky proposition since the next run might not find the
@@ -4549,49 +4551,9 @@ fix_small_capacity(struct sched_domain ** subtle and fragile situation. */ -struct sg_imb_stats { -unsigned long max_nr_running, min_nr_running; -unsigned long max_cpu_load, min_cpu_load; -}; - -static inline void init_sg_imb_stats (struct sg_imb_stats *sgi) +static inline int sg_imbalanced (struct sched_group *group) { - sgi->max_cpu_load = sgi->max_nr_running =0UL ; - sgi->min_cpu_load = sgi->min_nr_running = ~0UL ; -} - -static inline void -update_sg_imb_stats (struct sg_imb_stats *sgi, -unsigned long load,unsigned long nr_running) -{ -if (load > sgi->max_cpu_load) - sgi->max_cpu_load = load; -if (sgi->min_cpu_load > load) - sgi->min_cpu_load = load; - -if (nr_running > sgi->max_nr_running) - sgi->max_nr_running = nr_running; -if (sgi->min_nr_running > nr_running) - sgi->min_nr_running = nr_running; -} - -static inline int -sg_imbalanced (struct sg_lb_stats *sgs,struct sg_imb_stats *sgi) -{ -/* -* Consider the group unbalanced when the imbalance is larger -* than the average weight of a task. -* -* APZ: with cgroup the avg task weight can vary wildly and -* might not be a suitable number - should we keep a -* normalized nr_running number somewhere that negates -* the hierarchy? -*/ -if ((sgi->max_cpu_load - sgi->min_cpu_load) >= sgs->load_per_task && - (sgi->max_nr_running - sgi->min_nr_running) >1 ) -return 1 ; - -return 0 ; +return group->sgp->imbalance; }/**
@@ -4606,25 +4568,20 @@ static inline void update_sg_lb_stats(st struct sched_group *group, int load_idx, int local_group, struct sg_lb_stats *sgs) { - struct sg_imb_stats sgi; unsigned long nr_running;unsigned long load;int i; -init_sg_imb_stats (&sgi); -for_each_cpu_and (i,sched_group_cpus (group), env->cpus) {struct rq *rq =cpu_rq (i); nr_running = rq->nr_running;/* Bias balancing toward cpus of our domain */ -if (local_group) { +if (local_group) load =target_load (i, load_idx); - }else { +else load =source_load (i, load_idx); -update_sg_imb_stats (&sgi, load, nr_running); - } sgs->group_load += load; sgs->sum_nr_running += nr_running;
@@ -4644,7 +4601,7 @@ static inline void update_sg_lb_stats(stif (sgs->sum_nr_running) sgs->load_per_task = sgs->sum_weighted_load / sgs->sum_nr_running; - sgs->group_imb =sg_imbalanced (sgs, &sgi); + sgs->group_imb =sg_imbalanced (group); sgs->group_capacity =DIV_ROUND_CLOSEST (sgs->group_power,SCHED_POWER_SCALE );
@@ -5167,6 +5124,7 @@ static int load_balance(int this_cpu, st int *should_balance) {int ld_moved, cur_ld_moved, active_balance =0 ; +struct sched_domain *sd_parent = sd->parent;struct sched_group *group;struct rq *busiest;unsigned long flags;
@@ -5269,11 +5227,11 @@ static int load_balance(int this_cpu, st* moreover subsequent load balance cycles should correct the * excess load moved. */ -if ((env.flags &LBF_SOME_PINNED ) && env.imbalance >0 ) { +if ((env.flags &LBF_DST_PINNED ) && env.imbalance >0 ) { env.dst_rq =cpu_rq (env.new_dst_cpu); env.dst_cpu = env.new_dst_cpu; - env.flags &= ~LBF_SOME_PINNED ; + env.flags &= ~LBF_DST_PINNED ; env.loop =0 ; env.loop_break = sched_nr_migrate_break;
@@ -5287,6 +5245,18 @@ static int load_balance(int this_cpu, st goto more_balance; } +/* +* We failed to reach balance because of affinity. +*/ +if (sd_parent) { +int *group_imbalance = &sd_parent->groups->sgp->imbalance; + +if ((env.flags &LBF_SOME_PINNED ) && env.imbalance >0 ) { + *group_imbalance =1 ; + }else if (*group_imbalance) + *group_imbalance =0 ; + } +/* All tasks on this runqueue were pinned by CPU affinity */ if (unlikely (env.flags &LBF_ALL_PINNED )) {cpumask_clear_cpu (cpu_of (busiest), cpus);
@@ -5690,7 +5660,7 @@ static void rebalance_domains(int cpu, eif (time_after_eq (jiffies, sd->last_balance + interval)) {if (load_balance (cpu, rq, sd, idle, &should_balance)) {/* -* The LBF_SOME_PINNED logic could have changed +* The LBF_DST_PINNED logic could have changed * env->dst_cpu, so we can't know our idle * state even if we migrated tasks. Update it. */
kernel/sched/sched.h +1 -0
@@ -605,6 +605,7 @@ struct sched_group_power {*/ unsigned int power, power_orig;unsigned long next_update; +int imbalance;/* XXX unrelated to power but shared group state */ /* * Number of busy cpus in this group. */
Quoted 11 lines · Peter Zijlstra
After poking at them a little more I feel somewhat more confident.
I found one more bug, but this one was my own fault, we should also clear
sds->busiest_stat.avg_loadbecauseupdate_sd_pick_busiest()reads that before we set it.Moved the memset optimization and the fix for that into a separate patch.
Other than that, there's a
sched_domaindegenerate fix; and a new way to detectgroup_imb(which relies on thesched_domainfix).
I'm fine to my patches with your changes.
Thanks!
Peter Zijlstra
maintainer[RFC][PATCH 11/10] sched, fair: Reduce local_group logic
In reply to Peter ZijlstraSubject: sched, fair: Reduce local_group logic
From: Peter Zijlstra <[email protected]>
Date: Wed Aug 28 10:32:32 CEST 2013
Try and reduce the local_group logic by pulling most of it into update_sd_lb_stats.
We could completely get rid of the local_group variable, but that results in two calls to update_sg_lb_stats() and that blows up the object size by about 2k :/
--- kernel/sched/fair.c | 29 +++++++++++++++++------------ 1 file changed, 17 insertions(+), 12 deletions(-)
kernel/sched/fair.c +17 -12
@@ -4561,6 +4561,8 @@ static inline void update_sg_lb_stats(stunsigned long load;int i; +memset (sgs,0 ,sizeof (*sgs)); +for_each_cpu_and (i,sched_group_cpus (group), env->cpus) {struct rq *rq =cpu_rq (i);
@@ -4579,10 +4581,6 @@ static inline void update_sg_lb_stats(st sgs->idle_cpus++; } -if (local_group && (env->idle !=CPU_NEWLY_IDLE || -time_after_eq (jiffies, group->sgp->next_update))) -update_group_power (env->sd, env->dst_cpu); -/* Adjust by relative CPU power of the group */ sgs->group_power = group->sgp->power; sgs->avg_load = (sgs->group_load*SCHED_POWER_SCALE ) / sgs->group_power;
@@ -4675,11 +4673,17 @@ static inline void update_sd_lb_stats(stif (local_group) { sds->local = sg; sgs = &sds->local_stat; + +if (env->idle !=CPU_NEWLY_IDLE || +time_after_eq (jiffies, sg->sgp->next_update)) +update_group_power (env->sd, env->dst_cpu); } -memset (sgs,0 ,sizeof (*sgs));update_sg_lb_stats (env, sg, load_idx, local_group, sgs); +if (local_group) + goto next_group; +/* * In case the child domain prefers tasks go to siblings * first, lower the sg capacity to one so that we'll try
@@ -4690,19 +4694,20 @@ static inline void update_sd_lb_stats(st* heaviest group when it is already under-utilized (possible * with a large weight task outweighs the tasks on the system). */ -if (prefer_sibling && !local_group && - sds->local && sds->local_stat.group_has_capacity) +if (prefer_sibling && sds->local && + sds->local_stat.group_has_capacity) sgs->group_capacity =min (sgs->group_capacity,1U ); -/* Now, start updating sd_lb_stats */ - sds->total_load += sgs->group_load; - sds->total_pwr += sgs->group_power; - -if (!local_group &&update_sd_pick_busiest (env, sds, sg, sgs)) { +if (update_sd_pick_busiest (env, sds, sg, sgs)) { sds->busiest = sg; sds->busiest_stat = *sgs; } +next_group: +/* Now, start updating sd_lb_stats */ + sds->total_load += sgs->group_load; + sds->total_pwr += sgs->group_power; + sg = sg->next; }while (sg != env->sd->groups); }
Peter Zijlstra
maintainerRe: [RFC][PATCH 11/10] sched, fair: Reduce local_group logic
# ls -la defconfig-build/kernel/sched/fair.o* -rw-r--r-- 1 root root 760688 Aug 28 10:53 defconfig-build/kernel/sched/fair.o -rw-r--r-- 1 root root 758160 Aug 28 10:36 defconfig-build/kernel/sched/fair.o.orig
---
kernel/sched/fair.c +9 -11
@@ -4553,9 +4553,9 @@ static inline int sg_imbalanced(struct s* @local_group: Does group contain this_cpu. * @sgs: variable to hold the statistics for this group. */ -static inline void update_sg_lb_stats (struct lb_env *env, +static void update_sg_lb_stats (struct lb_env *env,struct sched_group *group,int load_idx, -int local_group,struct sg_lb_stats *sgs) +int group_bias,struct sg_lb_stats *sgs) {unsigned long nr_running;unsigned long load;
@@ -4568,8 +4568,7 @@ static inline void update_sg_lb_stats(st nr_running = rq->nr_running; -/* Bias balancing toward cpus of our domain */ -if (local_group) +if (group_bias) load =target_load (i, load_idx);else load =source_load (i, load_idx);
@@ -4667,22 +4666,21 @@ static inline void update_sd_lb_stats(st do { struct sg_lb_stats *sgs = &tmp_sgs; - int local_group; - local_group = cpumask_test_cpu(env->dst_cpu, sched_group_cpus(sg)); - if (local_group) { + if (cpumask_test_cpu(env->dst_cpu, sched_group_cpus(sg))) { sds->local = sg; sgs = &sds->local_stat; if (env->idle != CPU_NEWLY_IDLE || time_after_eq(jiffies, sg->sgp->next_update)) update_group_power(env->sd, env->dst_cpu); - } - - update_sg_lb_stats(env, sg, load_idx, local_group, sgs); - if (local_group) + /* Bias balancing toward cpus of our domain */ + update_sg_lb_stats(env, sg, load_idx, 1, sgs); goto next_group; + } + + update_sg_lb_stats(env, sg, load_idx, 0, sgs); /* * In case the child domain prefers tasks go to siblings
Peter Zijlstra
maintainerRe: [RFC][PATCH 11/10] sched, fair: Reduce local_group logic
In reply to Peter Zijlstrakernel/sched/fair.c static inline void update_sd_lb_stats(st · line 4699
Quoted 7 lines · Peter Zijlstra
kernel/sched/fair.c +2
-0@@ -4690,19 +4694,20 @@ static inline void update_sd_lb_stats(st* heaviest group when it is already under-utilized (possible * with a large weight task outweighs the tasks on the system). */ +if (prefer_sibling && sds->local && + sds->local_stat.group_has_capacity) sgs->group_capacity =min (sgs->group_capacity,1U );
While we're here, I think its always true that sds->local is set, because env->dst_cpu should always be part of the local group and the local group is always sd->groups and since that now directly skips to next_group we'll not get here without this being true.
Hmm?
Quoted 14 lines
kernel/sched/fair.c +6
-0+if (update_sd_pick_busiest (env, sds, sg, sgs)) { sds->busiest = sg; sds->busiest_stat = *sgs; } +next_group: +/* Now, start updating sd_lb_stats */ + sds->total_load += sgs->group_load; + sds->total_pwr += sgs->group_power; + sg = sg->next; }while (sg != env->sd->groups); }
Peter Zijlstra
maintainer[PATCH 12/10] sched, fair: Fix group power_orig computation
In reply to Peter ZijlstraSubject: sched, fair: Fix group power_orig computation
From: Peter Zijlstra <[email protected]>
Date: Wed Aug 28 11:44:39 CEST 2013
When looking at the code I noticed we don't actually compute sgp->power_orig correctly for groups, fix that.
Currently the only consumer of that value is fix_small_capacity() which is only used on POWER7+ and that code excludes this case by being limited to SD_SHARE_CPUPOWER which is only ever set on the SMT domain which must be the lowest domain and this has singleton groups.
So nothing should be affected by this change.
--- kernel/sched/fair.c | 40 ++++++++++++++++++++++++++-------------- 1 file changed, 26 insertions(+), 14 deletions(-)
kernel/sched/fair.c +11 -5
@@ -4448,7 +4448,7 @@ void update_group_power(struct sched_dom {struct sched_domain *child = sd->child;struct sched_group *group, *sdg = sd->groups; -unsigned long power; +unsigned long power, power_orig;unsigned long interval; interval =msecs_to_jiffies (sd->balance_interval);
@@ -4460,7 +4460,7 @@ void update_group_power(struct sched_domreturn ; } - power =0 ; + power_orig = power =0 ;if (child->flags &SD_OVERLAP ) {/*
@@ -4468,8 +4468,12 @@ void update_group_power(struct sched_dom* span the current group. */ -for_each_cpu (cpu,sched_group_cpus (sdg)) - power +=power_of (cpu); +for_each_cpu (cpu,sched_group_cpus (sdg)) { +struct sched_group *sg =cpu_rq (cpu)->sd->groups; + + power_orig += sg->sgp->power_orig; + power += sg->sgp->power; + } }else {/* * !SD_OVERLAP domains can assume that child groups
@@ -4478,12 +4482,14 @@ void update_group_power(struct sched_dom group = child->groups;do { + power_orig += group->sgp->power_orig; power += group->sgp->power; group = group->next; }while (group != child->groups); } - sdg->sgp->power_orig = sdg->sgp->power = power; + sdg->sgp->power_orig = power_orig; + sdg->sgp->power = power; }/*
Peter Zijlstra
maintainer[PATCH 13/10] sched, fair: Rework and comment the group_capacity code
In reply to Peter ZijlstraSubject: sched, fair: Rework and comment the group_capacity code
From: Peter Zijlstra <[email protected]>
Date: Wed Aug 28 11:50:34 CEST 2013
Pull out the group_capacity computation so that we can more clearly comment its issues.
--- kernel/sched/fair.c | 32 ++++++++++++++++++++++++-------- 1 file changed, 24 insertions(+), 8 deletions(-)
kernel/sched/fair.c +24 -8
@@ -4551,6 +4551,27 @@ static inline int sg_imbalanced(struct sreturn group->sgp->imbalance; } +/* +* Compute the group capacity. +* +* For now the capacity is simply the number of power units in the group_power. +* A power unit represents a full core. +* +* This has an issue where N*frac(smt_power) >= 1, in that case we'll see extra +* 'cores' that aren't actually there. +*/ +static inline int sg_capacity (struct lb_env *env,struct sched_group *group) +{ + +unsigned int power = group->sgp->power; +unsigned int capacity =DIV_ROUND_CLOSEST (power,SCHED_POWER_SCALE ); + +if (!capacity) + capacity =fix_small_capacity (env->sd, group); + +return capacity; +} +/** * update_sg_lb_stats - Update sched_group's statistics for load balancing. * @env: The load balancing environment.
@@ -4594,16 +4615,11 @@ static inline void update_sg_lb_stats(stif (sgs->sum_nr_running) sgs->load_per_task = sgs->sum_weighted_load / sgs->sum_nr_running; - sgs->group_imb =sg_imbalanced (group); - - sgs->group_capacity = -DIV_ROUND_CLOSEST (sgs->group_power,SCHED_POWER_SCALE ); - -if (!sgs->group_capacity) - sgs->group_capacity =fix_small_capacity (env->sd, group); - sgs->group_weight = group->group_weight; + sgs->group_imb =sg_imbalanced (group); + sgs->group_capacity =sg_capacity (env, group); +if (sgs->group_capacity > sgs->sum_nr_running) sgs->group_has_capacity =1 ; }
Peter Zijlstra
maintainer[RFC][PATCH 14/10] sched, fair: Fix the group_capacity computation
In reply to Peter ZijlstraSubject: sched, fair: Fix the group_capacity computation
From: Peter Zijlstra <[email protected]>
Date: Wed Aug 28 12:40:38 CEST 2013
Do away with 'phantom' cores due to N*frac(smt_power) >= 1 by limiting the capacity to the actual number of cores.
The assumption of 1 < smt_power < 2 is an actual requirement because of what SMT is so this should work regardless of the SMT implementation.
It can still be defeated by creative use of cpu hotplug, but if you're one of those freaks, you get to live with it.
--- kernel/sched/fair.c | 20 +++++++++++++------- 1 file changed, 13 insertions(+), 7 deletions(-)
kernel/sched/fair.c +13 -7
@@ -4554,18 +4554,24 @@ static inline int sg_imbalanced(struct s/* * Compute the group capacity. * -* For now the capacity is simply the number of power units in the group_power. -* A power unit represents a full core. -* -* This has an issue where N*frac(smt_power) >= 1, in that case we'll see extra -* 'cores' that aren't actually there. +* Avoid the issue where N*frac(smt_power) >= 1 creates 'phantom' cores by +* first dividing out the smt factor and computing the actual number of cores +* and limit power unit capacity with that. */ static inline int sg_capacity (struct lb_env *env,struct sched_group *group) { +unsigned int capacity, smt, cpus; +unsigned int power, power_orig; + + power = group->sgp->power; + power_orig = group->sgp->power_orig; + cpus = group->group_weight; -unsigned int power = group->sgp->power; -unsigned int capacity =DIV_ROUND_CLOSEST (power,SCHED_POWER_SCALE ); +/* smt := ceil(cpus / power), assumes: 1 < smt_power < 2 */ + smt =DIV_ROUND_UP (SCHED_POWER_SCALE * cpus, power_orig); + capacity = cpus / smt;/* cores */ + capacity =min_t (capacity,DIV_ROUND_CLOSEST (power,SCHED_POWER_SCALE ));if (!capacity) capacity =fix_small_capacity (env->sd, group);
Vincent Guittot
maintainerRe: [RFC][PATCH 14/10] sched, fair: Fix the group_capacity computation
Quoted 8 lines · Peter Zijlstra
Subject: sched, fair: Fix the
group_capacitycomputation
From: Peter Zijlstra <[email protected]>
Date: Wed Aug 28 12:40:38 CEST 2013Do away with 'phantom' cores due to N*frac(smt_power) >= 1 by limiting the capacity to the actual number of cores.
Peter,
your patch also solves the 'phantom' big cores that can appear on HMP system because big cores have a cpu_power >= SCHED_POWER_SCALE in order to express a higher capacity than LITTLE cores.
Acked-by Vincent Guittot <[email protected]>
Vincent
Quoted 46 lines
The assumption of 1 <
smt_power< 2 is an actual requirement because of what SMT is so this should work regardless of the SMT implementation.It can still be defeated by creative use of cpu hotplug, but if you're one of those freaks, you get to live with it.
Signed-off-by Peter Zijlstra <[email protected]>--- kernel/sched/fair.c | 20 +++++++++++++------- 1 file changed, 13 insertions(+), 7 deletions(-)kernel/sched/fair.c +13
-7@@ -4554,18 +4554,24 @@ static inline int sg_imbalanced(struct s/* * Compute the group capacity. * -* For now the capacity is simply the number of power units in the group_power. -* A power unit represents a full core. -* -* This has an issue where N*frac(smt_power) >= 1, in that case we'll see extra -* 'cores' that aren't actually there. +* Avoid the issue where N*frac(smt_power) >= 1 creates 'phantom' cores by +* first dividing out the smt factor and computing the actual number of cores +* and limit power unit capacity with that. */ static inline int sg_capacity (struct lb_env *env,struct sched_group *group) { +unsigned int capacity, smt, cpus; +unsigned int power, power_orig; + + power = group->sgp->power; + power_orig = group->sgp->power_orig; + cpus = group->group_weight; -unsigned int power = group->sgp->power; -unsigned int capacity =DIV_ROUND_CLOSEST (power,SCHED_POWER_SCALE ); +/* smt := ceil(cpus / power), assumes: 1 < smt_power < 2 */ + smt =DIV_ROUND_UP (SCHED_POWER_SCALE * cpus, power_orig); + capacity = cpus / smt;/* cores */ + capacity =min_t (capacity,DIV_ROUND_CLOSEST (power,SCHED_POWER_SCALE ));if (!capacity) capacity =fix_small_capacity (env->sd, group);