load balancing fixes

From: Rik van Riel <[email protected]>

There are several ways in which update_sd_pick_busiest can end up picking an sd as "busiest" that has a below-average per-cpu load.

All of those could use the same correction that was previously only applied when the selected group has a group imbalance.

Additionally, the load balancing code will balance out the load between domains that are below their maximum capacity. This results in the load_above_capacity calculation underflowing, creating a giant unsigned number, which is then removed by the min() check below.

In situations where all the domains are overloaded, or where only the busiest domain is overloaded, that code is also superfluous, since the normal env->imbalance calculation will figure out how much to move. Remove the load_above_capacity calculation.

Signed-off-by Rik van Riel <[email protected]>

---
 kernel/sched/fair.c | 33 ++++++++-------------------------
 1 file changed, 8 insertions(+), 25 deletions(-)

kernel/sched/fair.c +0 -0

index 45943b2..a28bb3b 100644
@@ -6221,16 +6221,16 @@ void fix_small_imbalance(struct lb_env *env, struct sd_lb_stats *sds)
  */

kernel/sched/fair.c +7 -24

                /*
-                * In the group_imb case we cannot rely on group-wide averages
-                * to ensure cpu-load equilibrium, look at wider averages. XXX
+                * Busiest got picked because it is overloaded or imbalanced,
+                * but does not have an above-average load. Look at wider
+                * averages.
                 */
                busiest->load_per_task =
                        min(busiest->load_per_task, sds->avg_load);

@@ -6247,32 +6247,15 @@ static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *s
                return fix_small_imbalance(env, sds);
        }
 
-       if (!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_factor);
-
-               load_above_capacity *= (SCHED_LOAD_SCALE * SCHED_CAPACITY_SCALE);
-               load_above_capacity /= busiest->group_capacity;
-       }
-
        /*
         * We're trying to get all the cpus to the average_load, so we don't
         * want to push ourselves above the average load, nor do we wish to
-        * reduce the max loaded cpu below the average load. At the same time,
-        * 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.
+        * reduce the max loaded cpu below the average load.
+        * The per-cpu avg_load values and the group capacity determine
+        * how much load to move to equalise the imbalance.
         */
-       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 * busiest->group_capacity,
+               (busiest->avg_load - sds->avg_load) * busiest->group_capacity,
                (sds->avg_load - local->avg_load) * local->group_capacity
        ) / SCHED_CAPACITY_SCALE;
 
--

1.9.3

Quoted 6 lines · On 28 July 2014 20:16, <[email protected]> wrote:

From: Rik van Riel <[email protected]>

There are several ways in which update_sd_pick_busiest can end up picking an sd as "busiest" that has a below-average per-cpu load.

Quoted 8 lines

All of those could use the same correction that was previously only applied when the selected group has a group imbalance.

Additionally, the load balancing code will balance out the load between domains that are below their maximum capacity. This results in the load_above_capacity calculation underflowing, creating a giant unsigned number, which is then removed by the min() check below.

The load_above capacity can't underflow with current version. The underflow that you mention above, could occur with the change you are doing in patch 2 which can select a group which not overloaded nor imbalanced.

Quoted 4 lines

In situations where all the domains are overloaded, or where only the busiest domain is overloaded, that code is also superfluous, since the normal env->imbalance calculation will figure out how much to move. Remove the load_above_capacity calculation.

IMHO, we should not remove that part which is used by prefer_sibling

Originally, we had 2 type of busiest group: overloaded or imbalanced. You add a new one which has only a avg_load higher than other so you should handle this new case and keep the other ones unchanged

Quoted 12 lines

Signed-off-by Rik van Riel <[email protected]> ---

kernel/sched/fair.c | 33 ++++++++------------------------- 1 file changed, 8 insertions(+), 25 deletions(-)

kernel/sched/fair.c index renamed from kernel/sched/fair.c +0 -0

45943b2..a28bb3b 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -6221,16 +6221,16 @@ void fix_small_imbalance(struct lb_env *env, struct sd_lb_stats *sds) */ 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 *local, *busiest;

Quoted 4 lines

local = &sds->local_stat; busiest = &sds->busiest_stat;

- if (busiest->group_imb) { + if (busiest->avg_load
<= sds->avg_load) {

busiest->avg_load <= sds->avg_load is already handled in the fix_small_imbalance function, you should probably handle that here

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Quoted 16 lines · Vincent Guittot

Quoted 14 lines · On 28 July 2014 20:16, <[email protected]> wrote:

From: Rik van Riel <[email protected]>

There are several ways in which update_sd_pick_busiest can end up picking an sd as "busiest" that has a below-average per-cpu load.

All of those could use the same correction that was previously only applied when the selected group has a group imbalance.

Additionally, the load balancing code will balance out the load between domains that are below their maximum capacity. This results in the load_above_capacity calculation underflowing, creating a giant unsigned number, which is then removed by the min() check below.

Quoted 4 lines

The load_above capacity can't underflow with current version. The underflow that you mention above, could occur with the change you are doing in patch 2 which can select a group which not overloaded nor imbalanced.

With SD_ASYM_PACKING the current code can already hit the underflow.

You are right though that it does not become common until the second patch has been applied.

Quoted 5 lines

Quoted 4 lines

In situations where all the domains are overloaded, or where only the busiest domain is overloaded, that code is also superfluous, since the normal env->imbalance calculation will figure out how much to move. Remove the load_above_capacity calculation.

Quoted 7 lines

IMHO, we should not remove that part which is used by prefer_sibling

Originally, we had 2 type of busiest group: overloaded or imbalanced. You add a new one which has only a avg_load higher than other so you should handle this new case and keep the other ones unchanged

The "overloaded" case will simply degenerate into the first case, if we move enough load to make the domain no longer overloaded, but still above average.

In the case where the value calculated by the "overloaded" calculation is different from the above-average, the old code took the minimum of the two as how much to move.

The new case you ask for would simply take the other part of that difference, once a domain is no longer overloaded.

I cannot think of any case where keeping the "overloaded" code would result in the code behaving differently over the long term.

What am I overlooking?

Quoted 13 lines

Quoted 13 lines

Signed-off-by Rik van Riel <[email protected]> ---

kernel/sched/fair.c | 33 ++++++++------------------------- 1 file changed, 8 insertions(+), 25 deletions(-)

kernel/sched/fair.c index renamed from kernel/sched/fair.c +0 -0

45943b2..a28bb3b 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -6221,16 +6221,16 @@ void fix_small_imbalance(struct lb_env *env, struct sd_lb_stats *sds) */ 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 *local, *busiest;

Quoted 7 lines

Quoted 4 lines

local = &sds->local_stat; busiest = &sds->busiest_stat;

- if (busiest->group_imb) { + if (busiest->avg_load
<= sds->avg_load) {

busiest->avg_load <= sds->avg_load is already handled in the fix_small_imbalance function, you should probably handle that here

OK, I will move that code into fix_small_imbalance()

- --
All rights reversed
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1
Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/

iQEcBAEBAgAGBQJT17VRAAoJEM553pKExN6DHMgIAI4IQsezUS1B/t8FzgkUR+8K 7EPIlOmsKZN/odfC6G4TntfwJojlcOsIQlxJF+PNCoWU4U61THK+NXif2a9/rNUE 3ffsrhZVy576HExezkAOzC8Z+g+7Y8O77af1PkSWul6Y3Xb2lQGG8ey+gdkOZytQ vwTlGQHGiUqiJaA1aohkz45Zbv2o7m7qCHoNPNvE9qK3WEY0StgLRQgfny6cgHsM 079Ecx5A5p7W/zL9kvMELQtU1QI0c7PLEGSy5rT0+8moZdR9biQF9ktDkoNawOD1 DLPguz+ZbLZUNOLezC18k8FoqLxkBkZiXQ25f20AFnLkJM4HC3A9EP+SsVZVc+M= =1hLj
-----END PGP SIGNATURE-----

Quoted 5 lines · Rik van Riel

I cannot think of any case where keeping the "overloaded" code would result in the code behaving differently over the long term.

What am I overlooking?

IIUC the load_above_capacity is there to prevent the busiest group to become idle and you remove that protection

Quoted 4 lines

In situations where all the domains are overloaded, or where only the busiest domain is overloaded, that code is also superfluous, since the normal env->imbalance calculation will figure out how much to move. Remove the load_above_capacity calculation.

IMHO, we should not remove that part which is used by prefer_sibling

Originally, we had 2 type of busiest group: overloaded or imbalanced. You add a new one which has only a avg_load higher than other so you should handle this new case and keep the other ones unchanged

Quoted 6 lines · Vincent Guittot

Quoted 5 lines

In situations where all the domains are overloaded, or where only the busiest domain is overloaded, that code is also superfluous, since the normal env->imbalance calculation will figure out how much to move. Remove the load_above_capacity calculation.

Quoted 7 lines

IMHO, we should not remove that part which is used by prefer_sibling

Originally, we had 2 type of busiest group: overloaded or imbalanced. You add a new one which has only a avg_load higher than other so you should handle this new case and keep the other ones unchanged

Right, so we want that code for overloaded -> overloaded migrations such as not to cause idle cpus in an attempt to balance things. Idle cpus are worse than imbalance.

But in case of overloaded/imb -> !overloaded migrations we can allow it, and in fact want to allow it in order to balance idle cpus.

Quoted 7 lines

Right, so we want that code for overloaded -> overloaded migrations such as not to cause idle cpus in an attempt to balance things. Idle cpus are worse than imbalance.

But in case of overloaded/imb -> !overloaded migrations we can allow it, and in fact want to allow it in order to balance idle cpus.

In case the destination is over the average load, or the source is under the average load, fix_small_imbalance() determines env->imbalance.

The "load_above_capacity" calculation is only reached when busiest is busier than average, and the destination is under the average load. In that case, env->imbalance ends up as the minimum of busiest - avg and avg - target.

Is there any case where limiting it further to "load - capacity" from the busiest domain makes a difference?

Quoted 17 lines · Rik van Riel

Quoted 7 lines

Right, so we want that code for overloaded -> overloaded migrations such as not to cause idle cpus in an attempt to balance things. Idle cpus are worse than imbalance.

But in case of overloaded/imb -> !overloaded migrations we can allow it, and in fact want to allow it in order to balance idle cpus.

In case the destination is over the average load, or the source is under the average load, fix_small_imbalance() determines env->imbalance.

The "load_above_capacity" calculation is only reached when busiest is busier than average, and the destination is under the average load. In that case, env->imbalance ends up as the minimum of busiest - avg and avg - target.

Quoted 2 lines

Is there any case where limiting it further to "load - capacity" from the busiest domain makes a difference?

sadly yes; suppose 8 cpus in 2 groups and 9 tasks, 8 tasks of weight 10, 1 of 1024. The local group will have 5 tasks of 10, the busiest will have the remaining 4.

Quoted 10 lines · Vincent Guittot

Quoted 4 lines

In situations where all the domains are overloaded, or where only the busiest domain is overloaded, that code is also superfluous, since the normal env->imbalance calculation will figure out how much to move. Remove the load_above_capacity calculation.

IMHO, we should not remove that part which is used by prefer_sibling

Originally, we had 2 type of busiest group: overloaded or imbalanced. You add a new one which has only a avg_load higher than other so you should handle this new case and keep the other ones unchanged

Right, so we want that code for overloaded -> overloaded migrations such as not to cause idle cpus in an attempt to balance things. Idle cpus are worse than imbalance.

But in case of overloaded/imb -> !overloaded migrations we can allow it, and in fact want to allow it in order to balance idle cpus.

Quoted 12 lines · Peter Zijlstra

Quoted 10 lines · Vincent Guittot

Quoted 4 lines

In situations where all the domains are overloaded, or where only the busiest domain is overloaded, that code is also superfluous, since the normal env->imbalance calculation will figure out how much to move. Remove the load_above_capacity calculation.

IMHO, we should not remove that part which is used by prefer_sibling

Originally, we had 2 type of busiest group: overloaded or imbalanced. You add a new one which has only a avg_load higher than other so you should handle this new case and keep the other ones unchanged

Quoted 6 lines

Right, so we want that code for overloaded -> overloaded migrations such as not to cause idle cpus in an attempt to balance things. Idle cpus are worse than imbalance.

But in case of overloaded/imb -> !overloaded migrations we can allow it, and in fact want to allow it in order to balance idle cpus.

Which would be patch 3/2

---
Subject: sched,fair: Allow calculate_imbalance() to move idle cpus
From: Peter Zijlstra <[email protected]>
Date: Tue Jul 29 17:15:11 CEST 2014

Allow calculate_imbalance() to 'create' idle cpus in the busiest group if there are idle cpus in the local group.

Suggested-by Rik van Riel <[email protected]>

Signed-off-by Peter Zijlstra <[email protected]>

Link http://lkml.kernel.org/n/[email protected] open here

---
 kernel/sched/fair.c |   11 +++++------
 1 file changed, 5 insertions(+), 6 deletions(-)

kernel/sched/fair.c +5 -6

@@ -6273,12 +6273,11 @@ static inline void calculate_imbalance(s
                return fix_small_imbalance(env, sds);
        }
 
-       if (busiest->group_type == group_overloaded) {
-               /*
-                * 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.
-                */
+       /*
+        * If there aren't any idle cpus, avoid creating some.
+        */
+       if (busiest->group_type == group_overloaded &&
+           local->group_type   == group_overloaded) {
                load_above_capacity =
                        (busiest->sum_nr_running - busiest->group_capacity_factor);
 

FWIW, you can add my ack for the new version of the patchset which includes this patch

kernel/sched/fair.c +0 -2

@@ -6221,16 +6221,16 @@ void fix_small_imbalance(struct lb_env *env, struct sd_lb_stats *sds)
  */
 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 *local, *busiest;
 
 	local = &sds->local_stat;
 	busiest = &sds->busiest_stat;
 
-	if (busiest->group_imb) {

kernel/sched/fair.c +0 -2

@@ -6247,32 +6247,15 @@ static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *s
 		return fix_small_imbalance(env, sds);
 	}
 
-	if (!busiest->group_imb) {
-		/*

Quoted 6 lines

kernel/sched/fair.c +0 -2

@@ -6247,32 +6247,15 @@ static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *s
 		return fix_small_imbalance(env, sds);
 	}
 
-	if (!busiest->group_imb) {
-		/*

kernel/sched/fair.c static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *s · line 6261

Quoted 10 lines

kernel/sched/fair.c +0 -10

-		 * 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_factor);
-
-		load_above_capacity *= (SCHED_LOAD_SCALE * SCHED_CAPACITY_SCALE);
-		load_above_capacity /= busiest->group_capacity;
-	}

I think we want to retain that, esp. for the overloaded case. So that wants to be:

	if (busiest->sum_nr_running > busiest->group_capacity_factor)

Clearly it doesn't make sense for the !overload case, and we explicitly want to avoid it in the imb case.

Ah, wait, I think I see why you want that gone. I was only expecting a correction fix wrt changing pick_busiest(), not also behaviour changes.