sched: make update_sd_pick_busiest return true on a busier sd
PATCH 1/1 sched: make update_sd_pick_busiest return true on a busier sd
Currently update_sd_pick_busiest only returns true when an sd is overloaded, or for SD_ASYM_PACKING when a domain is busier than average and a higher numbered domain than the target.
This breaks load balancing between domains that are not overloaded, in the !SD_ASYM_PACKING case. This patch makes update_sd_pick_busiest return true when the busiest sd yet is encountered.
On a 4 node system, this seems to result in the load balancer finally putting 1 thread of a 4 thread test run of "perf bench numa mem" on each node, where before the load was generally not spread across all nodes.
Behaviour for SD_ASYM_PACKING does not seem to match the comment, in that groups with below average load average are ignored, but I have no hardware to test that so I have left the behaviour of that code unchanged.
--- kernel/sched/fair.c | 18 +++++++++++------- 1 file changed, 11 insertions(+), 7 deletions(-)
kernel/sched/fair.c +11 -7
@@ -5942,16 +5942,20 @@ static bool update_sd_pick_busiest(struct lb_env *env,* numbered CPUs in the group, therefore mark all groups * higher than ourself as busy. */ -if ((env->sd->flags &SD_ASYM_PACKING ) && sgs->sum_nr_running && - env->dst_cpu <group_first_cpu (sg)) { -if (!sds->busiest) -return true; +if (env->sd->flags &SD_ASYM_PACKING ) { +if (sgs->sum_nr_running && env->dst_cpu <group_first_cpu (sg)) { +if (!sds->busiest) +return true; -if (group_first_cpu (sds->busiest) >group_first_cpu (sg)) -return true; +if (group_first_cpu (sds->busiest) >group_first_cpu (sg)) +return true; + } + +return false; } -return false; +/* See above: sgs->avg_load > sds->busiest_stat.avg_load */ +return true; }#ifdef CONFIG_NUMA_BALANCING
Vincent Guittot
maintainerQuoted 44 lines · Rik van Riel
Currently
update_sd_pick_busiestonly returns true when an sd is overloaded, or forSD_ASYM_PACKINGwhen a domain is busier than average and a higher numbered domain than the target.This breaks load balancing between domains that are not overloaded, in the !SD_ASYM_PACKING case. This patch makes
update_sd_pick_busiestreturn true when the busiest sd yet is encountered.On a 4 node system, this seems to result in the load balancer finally putting 1 thread of a 4 thread test run of "perf bench numa mem" on each node, where before the load was generally not spread across all nodes.
Behaviour for
SD_ASYM_PACKINGdoes not seem to match the comment, in that groups with below average load average are ignored, but I have no hardware to test that so I have left the behaviour of that code unchanged.--- kernel/sched/fair.c | 18 +++++++++++------- 1 file changed, 11 insertions(+), 7 deletions(-)kernel/sched/fair.c +4
-6@@ -5942,16 +5942,20 @@ static bool update_sd_pick_busiest(struct lb_env *env,* numbered CPUs in the group, therefore mark all groups * higher than ourself as busy. */ -if ((env->sd->flags &SD_ASYM_PACKING ) && sgs->sum_nr_running && - env->dst_cpu <group_first_cpu (sg)) { -if (!sds->busiest) -return true; +if (env->sd->flags &SD_ASYM_PACKING ) { +if (sgs->sum_nr_running && env->dst_cpu <group_first_cpu (sg)) { +if (!sds->busiest) +return true; -if (group_first_cpu (sds->busiest) >group_first_cpu (sg)) -return true;
kernel/sched/fair.c static bool update_sd_pick_busiest(struct lb_env *env, · line 5958
Quoted 10 lines
kernel/sched/fair.c +7
-1+if (group_first_cpu (sds->busiest) >group_first_cpu (sg)) +return true; + } + +return false; } -return false; +/* See above: sgs->avg_load > sds->busiest_stat.avg_load */ +return true;
Hi Rik,
I can see one issue with a default return set to true. You increase the number of time where we will not effectively migrate a task because we don't ensure that we will take the overloaded group if there is one. We can be in a situation where a group is overloaded but the load_balance will select a not overloaded group with an average load higher than sched_domain average value just because it is checked after.
Regarding your issue with "perf bench numa mem" that is not spread on all nodes, SD_PREFER_SIBLING flag (of DIE level) should do the job by reducing the capacity of "not local DIE" group at NUMA level to 1 task during the load balance computation. So you should have 1 task per sched_group at NUMA level.
Vincent
Quoted 9 lines
kernel/sched/fair.c +0
-1}#ifdef CONFIG_NUMA_BALANCING --To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Quoted 48 lines · Vincent Guittot
Quoted 37 lines · Rik van Riel
Currently
update_sd_pick_busiestonly returns true when an sd is overloaded, or forSD_ASYM_PACKINGwhen a domain is busier than average and a higher numbered domain than the target.This breaks load balancing between domains that are not overloaded, in the !SD_ASYM_PACKING case. This patch makes
update_sd_pick_busiestreturn true when the busiest sd yet is encountered.On a 4 node system, this seems to result in the load balancer finally putting 1 thread of a 4 thread test run of "perf bench numa mem" on each node, where before the load was generally not spread across all nodes.
Behaviour for
SD_ASYM_PACKINGdoes not seem to match the comment, in that groups with below average load average are ignored, but I have no hardware to test that so I have left the behaviour of that code unchanged.Cc: [email protected] Cc: [email protected] Signed-off-by: Rik van Riel <[email protected]> ---
kernel/sched/fair.c| 18 +++++++++++------- 1 file changed, 11 insertions(+), 7 deletions(-)kernel/sched/fair.c index renamed from kernel/sched/fair.c +0
-0fea7d33..ff4ddba 100644 ---
a/kernel/sched/fair.c+++b/kernel/sched/fair.c@@ -5942,16 +5942,20 @@ static bool update_sd_pick_busiest(structlb_env*env, * numbered CPUs in the group, therefore mark all groups * higher than ourself as busy.
*/ - if ((env->sd->flags&SD_ASYM_PACKING) &&sgs->sum_nr_running&& -env->dst_cpu<group_first_cpu(sg)) { - if (!sds->busiest) -
return true; + if (env->sd->flags&SD_ASYM_PACKING) { +
if (sgs->sum_nr_running&&env->dst_cpu<group_first_cpu(sg)) {
+ if (!sds->busiest) +
return true;Quoted 7 lines
- if (
group_first_cpu(sds->busiest)>group_first_cpu(sg)) - return true; +
if (group_first_cpu(sds->busiest)>group_first_cpu(sg)) +
return true; + } + + return false; }- return false; + /* See above:
sgs->avg_load>sds->busiest_stat.avg_load*/ + return true;Hi Rik,
Quoted 7 lines
I can see one issue with a default return set to true. You increase the number of time where we will not effectively migrate a task because we don't ensure that we will take the overloaded group if there is one. We can be in a situation where a group is overloaded but the
load_balancewill select a not overloaded group with an average load higher thansched_domainaverage value just because it is checked after.
Look at the first line of update_sd_pick_busiest()
static bool update_sd_pick_busiest(struct lb_env *env,
struct sd_lb_stats *sds, struct sched_group *sg, struct sg_lb_stats *sgs)
{
if (sgs->avg_load <= sds->busiest_stat.avg_load)
return false;If the group load is less than the busiest, we have already returned false, and will not get to the code that I changed.
Quoted 5 lines
Regarding your issue with "perf bench numa mem" that is not spread on all nodes,
SD_PREFER_SIBLINGflag (of DIE level) should do the job by reducing the capacity of "not local DIE" group at NUMA level to 1 task during the load balance computation. So you should have 1 task persched_groupat NUMA level.
That did not actually happen in my tests. I almost always ended up having only 0 tasks on one node.
- --
All rights reversed
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1
Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/
iQEcBAEBAgAGBQJT0lzDAAoJEM553pKExN6D/8oH/3TmBwlIpj/H7pbs4ucvfigx WBgjkA0U/snXA8D/oRicIpX2+N42wwnmME/E20mhVjqUAvrDLbfaWoJC3UJ6Qx08 GUeKxOBxbf1FypOmLyfKuQrMOojO585TX76n43MZnsfxzCJUIL6x6MQOE+Tbutx9 6Y0VCz1uw9BdwnEuP0fObMrExMOlmb2JSiWiCuf8uAorWiArv8TZvBxt5W093ONO bRDywJ8sMFVwgQ0TZLPEBFsRAcGuPhHx/FJZuOb/F/NWopaaZD3tt4gM3VDaq4ir z+Qvhboql2EdydoYZV+O4VBWI7gFtT2+vLpUteaYmFR3Zx5VtneSwyCwtk6yk0c= =tZ6L
-----END PGP SIGNATURE-----
Vincent Guittot
maintainerQuoted 66 lines · Rik van Riel
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1Quoted 48 lines · Vincent Guittot
Quoted 37 lines · Rik van Riel
Currently
update_sd_pick_busiestonly returns true when an sd is overloaded, or forSD_ASYM_PACKINGwhen a domain is busier than average and a higher numbered domain than the target.This breaks load balancing between domains that are not overloaded, in the !SD_ASYM_PACKING case. This patch makes
update_sd_pick_busiestreturn true when the busiest sd yet is encountered.On a 4 node system, this seems to result in the load balancer finally putting 1 thread of a 4 thread test run of "perf bench numa mem" on each node, where before the load was generally not spread across all nodes.
Behaviour for
SD_ASYM_PACKINGdoes not seem to match the comment, in that groups with below average load average are ignored, but I have no hardware to test that so I have left the behaviour of that code unchanged.Cc: [email protected] Cc: [email protected] Signed-off-by: Rik van Riel <[email protected]> ---
kernel/sched/fair.c| 18 +++++++++++------- 1 file changed, 11 insertions(+), 7 deletions(-)kernel/sched/fair.c index renamed from kernel/sched/fair.c +0
-0fea7d33..ff4ddba 100644 ---
a/kernel/sched/fair.c+++b/kernel/sched/fair.c@@ -5942,16 +5942,20 @@ static bool update_sd_pick_busiest(structlb_env*env, * numbered CPUs in the group, therefore mark all groups * higher than ourself as busy.
*/ - if ((env->sd->flags&SD_ASYM_PACKING) &&sgs->sum_nr_running&& -env->dst_cpu<group_first_cpu(sg)) { - if (!sds->busiest) -
return true; + if (env->sd->flags&SD_ASYM_PACKING) { +
if (sgs->sum_nr_running&&env->dst_cpu<group_first_cpu(sg)) {
+ if (!sds->busiest) +
return true;Quoted 7 lines
- if (
group_first_cpu(sds->busiest)>group_first_cpu(sg)) - return true; +
if (group_first_cpu(sds->busiest)>group_first_cpu(sg)) +
return true; + } + + return false; }- return false; + /* See above:
sgs->avg_load>sds->busiest_stat.avg_load*/ + return true;Hi Rik,
Quoted 7 lines
I can see one issue with a default return set to true. You increase the number of time where we will not effectively migrate a task because we don't ensure that we will take the overloaded group if there is one. We can be in a situation where a group is overloaded but the
load_balancewill select a not overloaded group with an average load higher thansched_domainaverage value just because it is checked after.Look at the first line of
update_sd_pick_busiest()static bool update_sd_pick_busiest(struct
lb_env*env,
structsd_lb_stats*sds, structsched_group*sg, structsg_lb_stats*sgs)
Quoted 6 lines
{ if (sgs->avg_load <= sds->busiest_stat.avg_load) return false;If the group load is less than the busiest, we have already returned false, and will not get to the code that I changed.
My point was that if a sched_group A with 1 task has got a higher avg_load than a sched_group with 2 tasks, we will select sched_group A whereas we should select the other group
Furthermore, update_sd_lb_stats will always return a busiest group even an idle one. This will increase the number of failed load balance and the time spent in the it.
Vincent
Quoted 24 lines
Quoted 6 lines
Regarding your issue with "perf bench numa mem" that is not spread on all nodes,
SD_PREFER_SIBLINGflag (of DIE level) should do the job by reducing the capacity of "not local DIE" group at NUMA level to 1 task during the load balance computation. So you should have 1 task persched_groupat NUMA level.That did not actually happen in my tests. I almost always ended up having only 0 tasks on one node.
- --
All rights reversed
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1
Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/iQEcBAEBAgAGBQJT0lzDAAoJEM553pKExN6D/8oH/3TmBwlIpj/H7pbs4ucvfigx WBgjkA0U/snXA8D/oRicIpX2+N42wwnmME/E20mhVjqUAvrDLbfaWoJC3UJ6Qx08 GUeKxOBxbf1FypOmLyfKuQrMOojO585TX76n43MZnsfxzCJUIL6x6MQOE+Tbutx9 6Y0VCz1uw9BdwnEuP0fObMrExMOlmb2JSiWiCuf8uAorWiArv8TZvBxt5W093ONO bRDywJ8sMFVwgQ0TZLPEBFsRAcGuPhHx/FJZuOb/F/NWopaaZD3tt4gM3VDaq4ir z+Qvhboql2EdydoYZV+O4VBWI7gFtT2+vLpUteaYmFR3Zx5VtneSwyCwtk6yk0c= =tZ6L
-----END PGP SIGNATURE-----
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Quoted 60 lines · Vincent Guittot
Quoted 50 lines · Vincent Guittot
Quoted 50 lines
Quoted 50 lines · Rik van Riel
Quoted 38 lines
Currently
update_sd_pick_busiestonly returns true when an sd is overloaded, or forSD_ASYM_PACKINGwhen a domain is busier than average and a higher numbered domain than the target.This breaks load balancing between domains that are not overloaded, in the !SD_ASYM_PACKING case. This patch makes
update_sd_pick_busiestreturn true when the busiest sd yet is encountered.On a 4 node system, this seems to result in the load balancer finally putting 1 thread of a 4 thread test run of "perf bench numa mem" on each node, where before the load was generally not spread across all nodes.
Behaviour for
SD_ASYM_PACKINGdoes not seem to match the comment, in that groups with below average load average are ignored, but I have no hardware to test that so I have left the behaviour of that code unchanged.Signed-off-by Rik van Riel <[email protected]> ---
kernel/sched/fair.c| 18 +++++++++++------- 1 file changed, 11 insertions(+), 7 deletions(-)kernel/sched/fair.c +1
-0+++ b/kernel/sched/fair.c @@ -5942,16 +5942,20 @@ staticbool update_sd_pick_busiest(struct
lb_env*env, * numbered CPUs in the group, therefore mark all groups * higher than
ourself as busy. */ - if ((env->sd->flags&SD_ASYM_PACKING) &&sgs->sum_nr_running&& -env->dst_cpu<group_first_cpu(sg)) { - if
(!sds->busiest) - return true; + if (env->sd->flags&SD_ASYM_PACKING) { + if (sgs->sum_nr_running&&env->dst_cpu<group_first_cpu(sg)) { +
if (!sds->busiest) + return true;Quoted 8 lines
- if (
group_first_cpu(sds->busiest)>group_first_cpu(sg)) - return true;
+ if (group_first_cpu(sds->busiest)>group_first_cpu(sg))
+ return true; + } + + return
false; }- return false; + /* See above:
sgs->avg_loadQuoted 1 line
sds->busiest_stat.avg_load*/ + return true;Hi Rik,
Quoted 7 lines
Quoted 7 lines
Quoted 7 lines
I can see one issue with a default return set to true. You increase the number of time where we will not effectively migrate a task because we don't ensure that we will take the overloaded group if there is one. We can be in a situation where a group is overloaded but the
load_balancewill select a not overloaded group with an average load higher thansched_domainaverage value just because it is checked after.
Quoted 13 lines
Look at the first line of
update_sd_pick_busiest()static bool
update_sd_pick_busiest(struct lb_env *env, struct sd_lb_stats *sds, struct sched_group *sg, struct sg_lb_stats *sgs){ if (sgs->avg_load<=sds->busiest_stat.avg_load) return false;If the group load is less than the busiest, we have already returned false, and will not get to the code that I changed.
Quoted 3 lines
My point was that if a
sched_groupA with 1 task has got a higheravg_loadthan asched_groupwith 2 tasks, we will selectsched_groupA whereas we should select the other group
The code already does that, with or without my patch.
If it runs into group A first, that "return false" above will be hit for group B.
Quoted 3 lines
Quoted 3 lines
Furthermore,
update_sd_lb_statswill always return a busiest group even an idle one. This will increase the number of failed load balance and the time spent in the it.
If the busiest group found is idle, surely find_busiest_group will see that and goto out_balanced ?
There are several safety checks in find_busiest_group to make sure NULL is returned when the imbalance found is too small to bother doing anything about.
- --
All rights reversed
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1
Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/
iQEcBAEBAgAGBQJT0m3fAAoJEM553pKExN6D1xMH/3BOTeD9aiu/nVCWnfJIdRUB 2owogPLFDlcbUekzGkjIxc4lYWj/ANVk5jOibcOLutckSJXphDc1KhqYYXaNM6rm NfoFM0//HGxJgIWMKGWYWJosPdFdrvLxNRwn8+yBnZh9el15GQSBvhKjrCeolNo2 Yy6AqicqvoMXMnzcONcAxyxwH0b6CRFuGHIOAvzjXGUvSKTU7fs1zPRAVxfORbbp HfiOybqNJW+EnH7xhJU+GSZi+X+agnRS4/axfc48FZH01/P+k21cYougC7kMxxHA MGP1YtnNYGFBqCX5QwGgw5NkMgHYNCCREh+uLwsgGCN/bkmuHJm+JcbQOQlRoRY= =v9O8
-----END PGP SIGNATURE-----
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Quoted 5 lines · Vincent Guittot
Regarding your issue with "perf bench numa mem" that is not spread on all nodes,
SD_PREFER_SIBLINGflag (of DIE level) should do the job by reducing the capacity of "not local DIE" group at NUMA level to 1 task during the load balance computation. So you should have 1 task persched_groupat NUMA level.
Looking at the code some more, it is clear why this does not happen. If sd->flags & SD_NUMA, then SD_PREFER_SIBLING will never be set.
On a related note, that part of the load balancing code probably needs to be rewritten to deal with unequal group_capacity_factors anyway.
Say that one group has a group_capacity_factor twice that of another group.
The group with the smaller group_capacity_factor is overloaded by a factor 1.3. The larger group is loaded by a factor 0.8. This means the larger group has a higher load than the first group, and the current code in update_sd_pick_busiest will not select the overloaded group as the busiest one, due to not scaling load with the capacity...
static bool update_sd_pick_busiest(struct lb_env *env,
struct sd_lb_stats *sds, struct sched_group *sg, struct sg_lb_stats *sgs)
{
if (sgs->avg_load <= sds->busiest_stat.avg_load)
return false;I believe we may need to factor the group_capacity_factor into this calculation, in order to properly identify which group is busiest.
However, if we do that we may need to get rid of the SD_PREFER_SIBLING hack that forces group_capacity_factor to 1 on domains that have SD_PREFER_SIBLING set.
I suspect that should be ok though, if we make sure update_sd_pick_busiest does the right thing...
- --
All rights reversed
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1
Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/
iQEcBAEBAgAGBQJT0mOCAAoJEM553pKExN6DHq4H/2THfH33d+JYvfOq95OpGLaD HATAp8Dv0kTiGjnbZrHPp8TqqgLLXuM6HhLvsvURuhoJw6F/nOX6qOQWEtjcMyYp omShkDSLnPjs/0Iwf9vNocT7K7Sn3Gk0hOj6+ICW7wchyug8JYtuiHunP8pYrpzW G6l2qHMRqRs5mSENY/uWwH9qh6Z6jcfDoDDDKRTNBe0z67FzwMnX1IYCUA6XOBsZ iRdXe8E0CIgio+ek8HVzRm5sUlkRyfJpTXJj+pemVJhTrNCCbMGTHxzADU4Ngc8S +JQ+G6bsHz9R4pffsuzYFbL0avK0mm5SrjCIatE7MX171dQJ1cKpju+fAmnwuNg= =EAzG
-----END PGP SIGNATURE-----
Peter Zijlstra
maintainerQuoted 18 lines · Rik van Riel
On a related note, that part of the load balancing code probably needs to be rewritten to deal with unequal
group_capacity_factorsanyway.Say that one group has a
group_capacity_factortwice that of another group.The group with the smaller
group_capacity_factoris overloaded by a factor 1.3. The larger group is loaded by a factor 0.8. This means the larger group has a higher load than the first group, and the current code inupdate_sd_pick_busiestwill not select the overloaded group as the busiest one, due to not scaling load with the capacity...static bool update_sd_pick_busiest(struct
lb_env*env,
structsd_lb_stats*sds, structsched_group*sg, structsg_lb_stats*sgs)
Quoted 7 lines
{ if (sgs->avg_load <= sds->busiest_stat.avg_load) return false;I believe we may need to factor the
group_capacity_factorinto this calculation, in order to properly identify which group is busiest.
(sorry, going through this backwards, I'll get to the actual patch in a bit)
Note how update_sg_lb_stats() where we compute sgs->avg_load we do divide by sgs->group_capacity.
(also, curse this renaming of stuff)
The group_capacity_factor is something ugly and Vincent was going to poke at that.
Vincent Guittot
maintainerQuoted 11 lines · Rik van Riel
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1Quoted 5 lines · Vincent Guittot
Regarding your issue with "perf bench numa mem" that is not spread on all nodes,
SD_PREFER_SIBLINGflag (of DIE level) should do the job by reducing the capacity of "not local DIE" group at NUMA level to 1 task during the load balance computation. So you should have 1 task persched_groupat NUMA level.
Quoted 3 lines
Looking at the code some more, it is clear why this does not happen. If
sd->flags&SD_NUMA, thenSD_PREFER_SIBLINGwill never be set.
I don't have a lot of experience on NUMA system and how their sched_domain topology is described but IIUC, you don't have other sched_domain level than NUMA ones ? otherwise the flag should be present in one of the non NUMA level (SMT, MC or DIE)
Quoted 9 lines
On a related note, that part of the load balancing code probably needs to be rewritten to deal with unequal
group_capacity_factorsanyway.Say that one group has a
group_capacity_factortwice that of another group.
Quoted 7 lines
The group with the smaller
group_capacity_factoris overloaded by a factor 1.3. The larger group is loaded by a factor 0.8. This means the larger group has a higher load than the first group, and the current code inupdate_sd_pick_busiestwill not select the overloaded group as the busiest one, due to not scaling load with the capacity...
AFAICT, sgs->avg_load is weighted by the capacity in update_sg_lb_stats
Quoted 8 lines
static bool update_sd_pick_busiest(struct
lb_env*env,
structsd_lb_stats*sds, structsched_group*sg, structsg_lb_stats*sgs){ if (sgs->avg_load <= sds->busiest_stat.avg_load) return false;
Quoted 7 lines
I believe we may need to factor the
group_capacity_factorinto this calculation, in order to properly identify which group is busiest.However, if we do that we may need to get rid of the
SD_PREFER_SIBLINGhack that forcesgroup_capacity_factorto 1 on domains that haveSD_PREFER_SIBLINGset.
I'm working on a patchset that get ride of capacity_factor (as mentioned by Peter) and directly uses capacity instead. I should send the v4 next week.
Vincent
Quoted 18 lines
I suspect that should be ok though, if we make sure
update_sd_pick_busiestdoes the right thing...- --
All rights reversed
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1
Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/iQEcBAEBAgAGBQJT0mOCAAoJEM553pKExN6DHq4H/2THfH33d+JYvfOq95OpGLaD HATAp8Dv0kTiGjnbZrHPp8TqqgLLXuM6HhLvsvURuhoJw6F/nOX6qOQWEtjcMyYp omShkDSLnPjs/0Iwf9vNocT7K7Sn3Gk0hOj6+ICW7wchyug8JYtuiHunP8pYrpzW G6l2qHMRqRs5mSENY/uWwH9qh6Z6jcfDoDDDKRTNBe0z67FzwMnX1IYCUA6XOBsZ iRdXe8E0CIgio+ek8HVzRm5sUlkRyfJpTXJj+pemVJhTrNCCbMGTHxzADU4Ngc8S +JQ+G6bsHz9R4pffsuzYFbL0avK0mm5SrjCIatE7MX171dQJ1cKpju+fAmnwuNg= =EAzG
-----END PGP SIGNATURE-----
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Quoted 10 lines · Vincent Guittot
Quoted 7 lines · Vincent Guittot
Quoted 6 lines
Quoted 6 lines
Regarding your issue with "perf bench numa mem" that is not spread on all nodes,
SD_PREFER_SIBLINGflag (of DIE level) should do the job by reducing the capacity of "not local DIE" group at NUMA level to 1 task during the load balance computation. So you should have 1 task persched_groupat NUMA level.
Quoted 8 lines
Quoted 3 lines
Looking at the code some more, it is clear why this does not happen. If
sd->flags&SD_NUMA, thenSD_PREFER_SIBLINGwill never be set.I don't have a lot of experience on NUMA system and how their
sched_domaintopology is described but IIUC, you don't have othersched_domainlevel than NUMA ones ? otherwise the flag should be present in one of the non NUMA level (SMT, MC or DIE)
The system I am testing on has 3 or 4 sched_domain levels, one for each HT sibling(?), one for each core, one for each node/socket, and one parent domain for the whole system.
SD_PREFER_SIBLING should be set at the HT sibling level and at the core level.
However, it is not set at the levels above that.
That means the SD_PREFER_SIBLING flag does its thing within each CPU core and between cores on a socket, but not between NUMA nodes...
Quoted 6 lines
Quoted 3 lines
On a related note, that part of the load balancing code probably needs to be rewritten to deal with unequal
group_capacity_factorsanyway.AFAICT,
sgs->avg_loadis weighted by the capacity inupdate_sg_lb_stats
Indeed, I dug into that code after sending the email, and found that piece of the code just before I read Peter's email pointing it out to me.
Quoted 3 lines
I'm working on a patchset that get ride of
capacity_factor(as mentioned by Peter) and directly uses capacity instead. I should send the v4 next week.
I am looking forward to anything that will make this code easier to follow :)
- --
All rights reversed
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1
Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/
iQEcBAEBAgAGBQJT0nQMAAoJEM553pKExN6DeFAIAK7KHHRl+lfWIxiZGRyarYHL SHJydCA4a9Lkd2D60dULGWY/8ylB8+IMfwv69/jXHZzbxlg7Nu1+da7ZUF3Lx35k AYxpOhC94eTJvp9KQX2W0nGiDZ0Di7YnWAWdoLsd1kZZDZjd82gtLVh63ossWZlF hn+YH6E4n0iAe6CZ2PO4QMz7dDYVGzUnKuuQVZKl3DBJWSe6ZvcBhDS4xDT+uUe1 IheA5aQcY8XmAkcXbLs736iBiOCKH6Jts6trJUPaVxw3jkD8lI/CMuMss2dk7RPH xl3Y8CKridywdtvGN6WrOwzUxVBxaEN1da/VuN7nF4OnoipYApSWwKTBe9wd7rQ= =AsCN
-----END PGP SIGNATURE-----
Peter Zijlstra
maintainerQuoted 4 lines · Rik van Riel
Currently
update_sd_pick_busiestonly returns true when an sd is overloaded, or forSD_ASYM_PACKINGwhen a domain is busier than average and a higher numbered domain than the target.
Quoted 8 lines
This breaks load balancing between domains that are not overloaded, in the !SD_ASYM_PACKING case. This patch makes
update_sd_pick_busiestreturn true when the busiest sd yet is encountered.On a 4 node system, this seems to result in the load balancer finally putting 1 thread of a 4 thread test run of "perf bench numa mem" on each node, where before the load was generally not spread across all nodes.
So for !ASYM the code is effectively:
return sgs->avg_load > sds->busiest_stat.avg_load;
I'd like to at least add a clause that makes overloaded groups prioritized over !overloaded groups.
Also, like we found earlier, calculate_imbalance() relies on the sum_nr_running > group_capacity_factor thing, which you've just 'wrecked', so we'd need an update to that part too.
Quoted 4 lines
Behaviour for
SD_ASYM_PACKINGdoes not seem to match the comment, in that groups with below average load average are ignored, but I have no hardware to test that so I have left the behaviour of that code unchanged.
Mikey, does that stuff work as expected?
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Quoted 17 lines · Peter Zijlstra
Quoted 9 lines · Rik van Riel
Currently
update_sd_pick_busiestonly returns true when an sd is overloaded, or forSD_ASYM_PACKINGwhen a domain is busier than average and a higher numbered domain than the target.This breaks load balancing between domains that are not overloaded, in the !SD_ASYM_PACKING case. This patch makes
update_sd_pick_busiestreturn true when the busiest sd yet is encountered.Quoted 4 lines
On a 4 node system, this seems to result in the load balancer finally putting 1 thread of a 4 thread test run of "perf bench numa mem" on each node, where before the load was generally not spread across all nodes.
So for !ASYM the code is effectively:
Quoted 8 lines
return
sgs->avg_load>sds->busiest_stat.avg_load;I'd like to at least add a clause that makes overloaded groups prioritized over !overloaded groups.
Also, like we found earlier,
calculate_imbalance()relies on thesum_nr_running>group_capacity_factorthing, which you've just 'wrecked', so we'd need an update to that part too.
I guess that would mean update_sd_pick_busiest would look like this for the !ASYM case:
1) remembering whether busiest is overloaded
2) if (sgs->busiest_stat.overloaded && !sgs->overloaded)
return false;
3) if (sgs->avg_load > sds->busiest_stat.avg_load)
return true;
Quoted 6 lines
Quoted 4 lines
Behaviour for
SD_ASYM_PACKINGdoes not seem to match the comment, in that groups with below average load average are ignored, but I have no hardware to test that so I have left the behaviour of that code unchanged.Mikey, does that stuff work as expected?
I suspect it does not, due to the checks above the SD_ASYM_PACKAGING code occasionally overriding the SD_ASYM_PACKAGING code.
Also, the ASYM code may rely on CPU numbers not being interleaved between groups, the "env->dst_cpu < group_first_cpu(sg)" check would probably fail to pull all load onto group 0 if CPU numbers were distributed like this:
group 0: 0 2 4 6
group 1: 1 3 5 7
- --
All rights reversed
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1
Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/
iQEcBAEBAgAGBQJT0nt9AAoJEM553pKExN6DdiYH/jnO9c8f9VNIPD6ibsuG0JXO HgMJVhYY4YA/kP3wvdOOjLNwAohivCqd41ZMe7jw5K25aJ6/PIT9BN4iImSnPbgw JPLzUyvMF+hl6/rfmKJnpYSpTOqxbZllmbJPEXJMc0biizftA1u7aoO88ufHsZbq vZOZLHieHaiMSJ5J5sHpGaWWLw3hS4Ba0HJmUSlV+sbqSX6yZmcDFoQlvYlzfybK Q2HFVU3WGtYcOIxgJB1NVcn+axok8+O8kI8lQpWSzpewZN6fRKqZMVnmIvEKK15C stE3U8zXz6eYrlko5J0YyRcL5OPCE/tr4V5CRPonIvsLXmAmrMra5Ev4Dc/4Rr4= =hZqS
-----END PGP SIGNATURE-----
Peter Zijlstra
maintainerQuoted 14 lines · Rik van Riel
Quoted 10 lines
So for !ASYM the code is effectively:
return
sgs->avg_load>sds->busiest_stat.avg_load;I'd like to at least add a clause that makes overloaded groups prioritized over !overloaded groups.
Also, like we found earlier,
calculate_imbalance()relies on thesum_nr_running>group_capacity_factorthing, which you've just 'wrecked', so we'd need an update to that part too.I guess that would mean
update_sd_pick_busiestwould look like this for the !ASYM case:
Quoted 7 lines
1) remembering whether busiest is overloaded
2) if (
sgs->busiest_stat.overloaded&& !sgs->overloaded)return false;3) if (
sgs->avg_load>sds->busiest_stat.avg_load)return true;
Right. So the situation I was worried about is where we have say 8 +nice tasks in one group and 2 -nice in another. So the group with 2 tasks can actually be 'heavier' but not fully utilized. In that case we want to pull tasks from the lighter but overloaded group.
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Quoted 20 lines · Peter Zijlstra
Quoted 19 lines · Rik van Riel
Quoted 10 lines
So for !ASYM the code is effectively:
return
sgs->avg_load>sds->busiest_stat.avg_load;I'd like to at least add a clause that makes overloaded groups
prioritized over !overloaded groups.Also, like we found earlier,
calculate_imbalance()relies on thesum_nr_running>group_capacity_factorthing, which you've just 'wrecked', so we'd need an update to that part too.I guess that would mean
update_sd_pick_busiestwould look like this for the !ASYM case:1) remembering whether busiest is overloaded
2) if (
sgs->busiest_stat.overloaded&& !sgs->overloaded) return false;
Quoted 6 lines
Quoted 1 line
3) if (
sgs->avg_load>sds->busiest_stat.avg_load) return true;Right. So the situation I was worried about is where we have say 8 +nice tasks in one group and 2 -nice in another. So the group with 2 tasks can actually be 'heavier' but not fully utilized. In that case we want to pull tasks from the lighter but overloaded group.
I can certainly create a new patch that makes update_sd_pick_busiest do just that.
Vincent, any objections to me fixing update_sd_pick_busiest now, or will that conflict with your code cleanups?
- --
All rights reversed
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1
Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/
iQEcBAEBAgAGBQJT0oRWAAoJEM553pKExN6DRdoH/2VsMEbeRdr9o99CYV3hK2bj OT4O5xlz47aBq+/J3Sp35DZKtQ8PpYICNoNzddyF5Blr7ZcXB2OQj5Cv5Lj3Dtcs q/AnJAN+6mDNq4B3aVfTb3BMDcrSz8LNdpNwVM80gfvbcZkcWIYWF2FigShIggMZ bKz4cC5hVphtYR/WH6gnb5dXwgXBGYatwYsDXnVw6SLRbXcwYrB646SmZYXDVcER bOj5IAjdfAlFkLbeow6OaX1arBrd6lyKfVI4Mzr848dqLBrJvmPvx/R4Z8EzPN2H Gv4kqU7s9CAk1QOZLHWAOCDjG7PdMZfkS7WEZnQinMIutBK/jYJ4IXY8NNeS96I= =OcR0
-----END PGP SIGNATURE-----
Vincent Guittot
maintainerQuoted 31 lines · Rik van Riel
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1Quoted 20 lines · Peter Zijlstra
Quoted 19 lines · Rik van Riel
Quoted 10 lines
So for !ASYM the code is effectively:
return
sgs->avg_load>sds->busiest_stat.avg_load;I'd like to at least add a clause that makes overloaded groups
prioritized over !overloaded groups.Also, like we found earlier,
calculate_imbalance()relies on thesum_nr_running>group_capacity_factorthing, which you've just 'wrecked', so we'd need an update to that part too.I guess that would mean
update_sd_pick_busiestwould look like this for the !ASYM case:1) remembering whether busiest is overloaded
2) if (
sgs->busiest_stat.overloaded&& !sgs->overloaded) return false;Quoted 6 lines
Quoted 1 line
3) if (
sgs->avg_load>sds->busiest_stat.avg_load) return true;Right. So the situation I was worried about is where we have say 8 +nice tasks in one group and 2 -nice in another. So the group with 2 tasks can actually be 'heavier' but not fully utilized. In that case we want to pull tasks from the lighter but overloaded group.
Quoted 5 lines
I can certainly create a new patch that makes
update_sd_pick_busiestdo just that.Vincent, any objections to me fixing
update_sd_pick_busiestnow, or will that conflict with your code cleanups?
It will probably conflict with my patchset which also modify update_sd_pick_busiest but we should be able to manage the conflict. So feel free to send a patch that fix the description above and we will see how to handle the conflict when it will occur
Vincent
Quoted 15 lines
- --
All rights reversed
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1
Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/iQEcBAEBAgAGBQJT0oRWAAoJEM553pKExN6DRdoH/2VsMEbeRdr9o99CYV3hK2bj OT4O5xlz47aBq+/J3Sp35DZKtQ8PpYICNoNzddyF5Blr7ZcXB2OQj5Cv5Lj3Dtcs q/AnJAN+6mDNq4B3aVfTb3BMDcrSz8LNdpNwVM80gfvbcZkcWIYWF2FigShIggMZ bKz4cC5hVphtYR/WH6gnb5dXwgXBGYatwYsDXnVw6SLRbXcwYrB646SmZYXDVcER bOj5IAjdfAlFkLbeow6OaX1arBrd6lyKfVI4Mzr848dqLBrJvmPvx/R4Z8EzPN2H Gv4kqU7s9CAk1QOZLHWAOCDjG7PdMZfkS7WEZnQinMIutBK/jYJ4IXY8NNeS96I= =OcR0
-----END PGP SIGNATURE-----
PATCH v2 1/1 sched: make update_sd_pick_busiest return true on a busier sd
Subject: sched: make update_sd_pick_busiest return true on a busier sd
Currently update_sd_pick_busiest only identifies the busiest sd that is either overloaded, or has a group imbalance. When no sd is imbalanced or overloaded, the load balancer fails to find the busiest domain.
This breaks load balancing between domains that are not overloaded, in the !SD_ASYM_PACKING case. This patch makes update_sd_pick_busiest return true when the busiest sd yet is encountered.
Behaviour for SD_ASYM_PACKING does not seem to match the comment, but I have no hardware to test that so I have left the behaviour of that code unchanged.
It is unclear what to do with the group_imb condition. Should group_imb override a busier load? If so, should we fix calculate_imbalance to return a sensible number when the "busiest" node found has a below average load? We probably need to fix calculate_imbalance anyway, to deal with an overloaded group that happens to have a below average load...
--- kernel/sched/fair.c | 18 +++++++++++++----- 1 file changed, 13 insertions(+), 5 deletions(-)
kernel/sched/fair.c +13 -5
@@ -5949,6 +5949,11 @@ static inline void update_sg_lb_stats(struct lb_env *env, sgs->group_has_free_capacity =1 ; } +static bool group_overloaded (struct sg_lb_stats *sgs) +{ +return sgs->sum_nr_running > sgs->group_capacity_factor; +} +/** * update_sd_pick_busiest - return 1 on busiest group * @env: The load balancing environment.
@@ -5957,7 +5962,7 @@ static inline void update_sg_lb_stats(struct lb_env *env,* @sgs: sched_group statistics * * Determine if @sg is a busier group than the previously selected -* busiest group. +* busiest group. * * Return: %true if @sg is a busier group than the previously selected * busiest group. %false otherwise.
@@ -5967,13 +5972,17 @@ static bool update_sd_pick_busiest(struct lb_env *env, struct sched_group *sg, struct sg_lb_stats *sgs) { + if (group_overloaded(sgs) && !group_overloaded(&sds->busiest_stat)) + return true; +if (sgs->avg_load <= sds->busiest_stat.avg_load)return false; -if (sgs->sum_nr_running > sgs->group_capacity_factor) +if (sgs->group_imb)return true; -if (sgs->group_imb) +/* This is the busiest node. */ +if (!(env->sd->flags &SD_ASYM_PACKING ))return true;/*
@@ -5981,8 +5990,7 @@ static bool update_sd_pick_busiest(struct lb_env *env,* numbered CPUs in the group, therefore mark all groups * higher than ourself as busy. */ -if ((env->sd->flags &SD_ASYM_PACKING ) && sgs->sum_nr_running && - env->dst_cpu <group_first_cpu (sg)) { +if (sgs->sum_nr_running && env->dst_cpu <group_first_cpu (sg)) {if (!sds->busiest)return true;
Vincent Guittot
maintainerQuoted 11 lines · Rik van Riel
Subject: sched: make
update_sd_pick_busiestreturn true on a busier sdCurrently
update_sd_pick_busiestonly identifies the busiest sd that is either overloaded, or has a group imbalance. When no sd is imbalanced or overloaded, the load balancer fails to find the busiest domain.This breaks load balancing between domains that are not overloaded, in the !SD_ASYM_PACKING case. This patch makes
update_sd_pick_busiestreturn true when the busiest sd yet is encountered.
Quoted 6 lines
Behaviour for
SD_ASYM_PACKINGdoes not seem to match the comment, but I have no hardware to test that so I have left the behaviour of that code unchanged.It is unclear what to do with the
group_imbcondition. Shouldgroup_imboverride a busier load? If so, should we fix
IMHO, group_imb should have a lower priority compared to overloaded group because it generates active migration whereas the use of overloaded group could solve the imbalance with normal migration Then, AFAICT, we already have a special way to compute imbalance when group_imb is set
Quoted 38 lines
calculate_imbalanceto return a sensible number when the "busiest" node found has a below average load? We probably need to fixcalculate_imbalanceanyway, to deal with an overloaded group that happens to have a below average load...--- kernel/sched/fair.c | 18 +++++++++++++----- 1 file changed, 13 insertions(+), 5 deletions(-)kernel/sched/fair.c +6
-1@@ -5949,6 +5949,11 @@ static inline void update_sg_lb_stats(struct lb_env *env, sgs->group_has_free_capacity =1 ; } +static bool group_overloaded (struct sg_lb_stats *sgs) +{ +return sgs->sum_nr_running > sgs->group_capacity_factor; +} +/** * update_sd_pick_busiest - return 1 on busiest group * @env: The load balancing environment. @@ -5957,7 +5962,7 @@ static inline void update_sg_lb_stats(struct lb_env *env,* @sgs: sched_group statistics * * Determine if @sg is a busier group than the previously selected -* busiest group. +* busiest group. * * Return: %true if @sg is a busier group than the previously selected * busiest group. %false otherwise.
kernel/sched/fair.c static bool update_sd_pick_busiest(struct lb_env *env, · line 5975
Quoted 4 lines
kernel/sched/fair.c +1
-0@@ -5967,13 +5972,17 @@ static bool update_sd_pick_busiest(struct lb_env *env,struct sched_group *sg, struct sg_lb_stats *sgs) { + if (group_overloaded(sgs) && !group_overloaded(&sds->busiest_stat))
The 1st time you run update_sd_pick_busiest, group_capacity_factor and sum_nr_running of sds->busiest_stat are uninitialized.
kernel/sched/fair.c static bool update_sd_pick_busiest(struct lb_env *env, · line 5977
Quoted 2 lines
kernel/sched/fair.c +2
-0+return true; +
IIUC your new test sequence, you haven't solved the following use case:
group A has 3 tasks and is overloaded
group B has 2 tasks and is not overloaded but its avg_load is higher than group B (either because of nice priority or because of average runnable time)
The test of group A will return true because it is overloaded and not the empty busiest_stat
But, the test of group B will also return true because of !(env->sd->flags & SD_ASYM_PACKING)
So at the end you are selecting the group B which is not overloaded
Quoted 24 lines
kernel/sched/fair.c +4
-4if (sgs->avg_load <= sds->busiest_stat.avg_load)return false; -if (sgs->sum_nr_running > sgs->group_capacity_factor) +if (sgs->group_imb)return true; -if (sgs->group_imb) +/* This is the busiest node. */ +if (!(env->sd->flags &SD_ASYM_PACKING ))return true;/* @@ -5981,8 +5990,7 @@ static bool update_sd_pick_busiest(struct lb_env *env,* numbered CPUs in the group, therefore mark all groups * higher than ourself as busy. */ -if ((env->sd->flags &SD_ASYM_PACKING ) && sgs->sum_nr_running && - env->dst_cpu <group_first_cpu (sg)) { +if (sgs->sum_nr_running && env->dst_cpu <group_first_cpu (sg)) {if (!sds->busiest)return true;
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Quoted 43 lines · Vincent Guittot
Quoted 13 lines · Rik van Riel
Subject: sched: make
update_sd_pick_busiestreturn true on a busier sdCurrently
update_sd_pick_busiestonly identifies the busiest sd that is either overloaded, or has a group imbalance. When no sd is imbalanced or overloaded, the load balancer fails to find the busiest domain.This breaks load balancing between domains that are not overloaded, in the !SD_ASYM_PACKING case. This patch makes
update_sd_pick_busiestreturn true when the busiest sd yet is encountered.Quoted 6 lines
Behaviour for
SD_ASYM_PACKINGdoes not seem to match the comment, but I have no hardware to test that so I have left the behaviour of that code unchanged.It is unclear what to do with the
group_imbcondition. Shouldgroup_imboverride a busier load? If so, should we fixIMHO,
group_imbshould have a lower priority compared to overloaded group because it generates active migration whereas the use of overloaded group could solve the imbalance with normal migration Then, AFAICT, we already have a special way to compute imbalance whengroup_imbis setQuoted 16 lines
calculate_imbalanceto return a sensible number when the "busiest" node found has a below average load? We probably need to fixcalculate_imbalanceanyway, to deal with an overloaded group that happens to have a below average load...Cc: [email protected] Cc: [email protected] Signed-off-by: Rik van Riel <[email protected]> ---
kernel/sched/fair.c| 18 +++++++++++++----- 1 file changed, 13 insertions(+), 5 deletions(-)kernel/sched/fair.c index renamed from kernel/sched/fair.c +0
-045943b2..c96044f 100644 ---
a/kernel/sched/fair.c+++b/kernel/sched/fair.c@@ -5949,6 +5949,11 @@ static inline void update_sg_lb_stats(structlb_env*env,sgs->group_has_free_capacity= 1; }
Quoted 16 lines
Quoted 5 lines
+static bool
group_overloaded(struct sg_lb_stats *sgs)+{ + returnsgs->sum_nr_running>sgs->group_capacity_factor; +} + /** *update_sd_pick_busiest- return 1 on busiest group * @env:
The load balancing environment. @@ -5957,7 +5962,7 @@ static inline void update_sg_lb_stats(structlb_env*env, * @sgs:Quoted 8 lines
sched_groupstatistics * * Determine if @sg is a busier group than the previously selected - * busiest group. + * busiest group. * * Return: %true if @sg is a busier group than the previously selected * busiest group. %false otherwise. @@ -5967,13 +5972,17 @@ static boolupdate_sd_pick_busiest(struct lb_env *env, struct sched_group *sg, struct sg_lb_stats *sgs){ + if (group_overloaded(sgs)&& !group_overloaded(&sds->busiest_stat))The 1st time you run
update_sd_pick_busiest,group_capacity_factorandsum_nr_runningofsds->busiest_statare uninitialized.
Good point, init_sd_lb_stats only zeroes out a few fields.
I will fix this in the next version.
Quoted 4 lines
Quoted 1 line
+ return true; +
IIUC your new test sequence, you haven't solved the following use case:
Fixed in the next version, with Peter's idea.
- --
All rights reversed
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1
Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/
iQEcBAEBAgAGBQJT1mZ8AAoJEM553pKExN6DpPAH/A+a9Lbz/pV8uFGG3RRrs2gI l8rhgtVLEM0uiDTDavB/D1GBnWcxfNbg6o/yF7dTXDA+sWltztZISi6dZ9JpEhww 0wK3rOD6t+VYpu6OaA2rIp2p2o12ou2d8ipjimjGf9gGD8i6vZiGOfTytsSateZH X9pSQ5Tv63ES8m3DeLcXEy+YQVunyLD83aTwSpziBFKUGguttTvvqEx5MutxVQyA Wx7hqX4VTR2oC3mS6djzK/hp0OmpZL4WKmnqUgjm11k0+UvBc1MnYE937CHixOdQ GjfIgk+G8EGVucbKFfhgwrNFfemL4MXxSVxMMor1lMFt9yFKcwoSMRS40mcH+Rw= =qENP
-----END PGP SIGNATURE-----
Peter Zijlstra
maintainerQuoted 15 lines · Rik van Riel
Subject: sched: make
update_sd_pick_busiestreturn true on a busier sdCurrently
update_sd_pick_busiestonly identifies the busiest sd that is either overloaded, or has a group imbalance. When no sd is imbalanced or overloaded, the load balancer fails to find the busiest domain.This breaks load balancing between domains that are not overloaded, in the !SD_ASYM_PACKING case. This patch makes
update_sd_pick_busiestreturn true when the busiest sd yet is encountered.Behaviour for
SD_ASYM_PACKINGdoes not seem to match the comment, but I have no hardware to test that so I have left the behaviour of that code unchanged.
Quoted 6 lines
It is unclear what to do with the
group_imbcondition. Shouldgroup_imboverride a busier load? If so, should we fixcalculate_imbalanceto return a sensible number when the "busiest" node found has a below average load? We probably need to fixcalculate_imbalanceanyway, to deal with an overloaded group that happens to have a below average load...
I think we want overloaded > group_imb > other. So prefer overloaded groups, imbalanced groups if no overloaded and anything else if no overloaded and imbalanced thingies.
If you look at the comment near sg_imbalanced(), in that case we want to move tasks from the first group to the second, even though the second group would be the heaviest.
enum group_type {
group_other = 0,
group_imbalanced,
group_overloaded,
};
static enum group_type group_classify(struct sg_lb_stats *sgs)
{
if (sgs->sum_nr_running > sgs->group_capacity_factor)
return group_overloaded;
if (sgs->group_imb)
return group_imbalanced;
return group_other;
}kernel/sched/fair.c static inline void update_sg_lb_stats(struct lb_env *env, · line 5965
Quoted 9 lines
/**
*update_sd_pick_busiest- return 1 on busiest group
* @env: The load balancing environment.kernel/sched/fair.c +1
-1@@ -5957,7 +5962,7 @@ static inline void update_sg_lb_stats(struct lb_env *env,* @sgs: sched_group statistics * * Determine if @sg is a busier group than the previously selected -* busiest group. +* busiest group.
We really need that extra trailing whitespace, yes? ;-)
kernel/sched/fair.c static bool update_sd_pick_busiest(struct lb_env *env, · line 5974
Quoted 6 lines
kernel/sched/fair.c +0
-0* Return: %true if @sg is a busier group than the previously selected * busiest group. %false otherwise. @@ -5967,13 +5972,17 @@ static bool update_sd_pick_busiest(struct lb_env *env,struct sched_group *sg, struct sg_lb_stats *sgs) {
if (group_classify(sgs) < group_classify(&sds->busiest_stats)) return false;
kernel/sched/fair.c static bool update_sd_pick_busiest(struct lb_env *env, · line 5988
Quoted 9 lines
kernel/sched/fair.c +2
-0if (sgs->avg_load <= sds->busiest_stat.avg_load)return false; +/* This is the busiest node. */ +if (!(env->sd->flags &SD_ASYM_PACKING ))return true;/*
We could replace sg_lb_stats::group_imb with the above and avoid the endless recomputation I suppose.
Also, we still need a little change to calculate_imbalance() where we assume sum_nr_running > group_capacity_factor.
Michael Neuling
Acked-byQuoted 25 lines · Peter Zijlstra
Quoted 4 lines · Rik van Riel
Currently
update_sd_pick_busiestonly returns true when an sd is overloaded, or forSD_ASYM_PACKINGwhen a domain is busier than average and a higher numbered domain than the target.Quoted 8 lines
This breaks load balancing between domains that are not overloaded, in the !SD_ASYM_PACKING case. This patch makes
update_sd_pick_busiestreturn true when the busiest sd yet is encountered.On a 4 node system, this seems to result in the load balancer finally putting 1 thread of a 4 thread test run of "perf bench numa mem" on each node, where before the load was generally not spread across all nodes.
So for !ASYM the code is effectively:
return sgs->avg_load > sds->busiest_stat.avg_load;I'd like to at least add a clause that makes overloaded groups prioritized over !overloaded groups.
Also, like we found earlier,
calculate_imbalance()relies on thesum_nr_running>group_capacity_factorthing, which you've just 'wrecked', so we'd need an update to that part too.
Quoted 6 lines
Quoted 4 lines
Behaviour for
SD_ASYM_PACKINGdoes not seem to match the comment, in that groups with below average load average are ignored, but I have no hardware to test that so I have left the behaviour of that code unchanged.Mikey, does that stuff work as expected?
Sorry for the slow response. v1 and v2 both pass testing on POWER7. So FWIW...
Mikey