Skip to contentSkip to conversation

sched/fair: Don't increase sd->balance_interval on newidle balance

PATCH In review Valentin Schneider 3 participants 8 messages Sep 25, 2018 – Sep 26, 2018 Scheduler

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 sched/fair: Don't increase sd->balance_interval on newidle balance

When load_balance() fails to move some load because of task affinity, we end up increasing sd->balance_interval to delay the next periodic balance in the hopes that next time we look, that annoying pinned task(s) will be gone.

However, idle_balance() pays no attention to sd->balance_interval, yet it will still lead to an increase in balance_interval in case of pinned tasks.

If we're going through several newidle balances (e.g. we have a periodic task), this can lead to a huge increase of the balance_interval in a very small amount of time.

To prevent that, don't increase the balance interval when going through a newidle balance.

---
 kernel/sched/fair.c | 19 ++++++++++++++-----
 1 file changed, 14 insertions(+), 5 deletions(-)
kernel/sched/fair.c +14 -5
index 6bd142d..620910d 100644
@@ -8782,13 +8782,22 @@ static int load_balance(int this_cpu, struct rq *this_rq,
 	sd->nr_balance_failed = 0;
 
 out_one_pinned:
+	ld_moved = 0;
+
+	/*
+	 * idle_balance() disregards balance intervals, so we could repeatedly
+	 * reach this code, which would lead to balance_interval skyrocketting
+	 * in a short amount of time. Skip the balance_interval increase logic
+	 * to avoid that.
+	 */
+	if (env.idle == CPU_NEWLY_IDLE)
+		goto out;
+
 	/* tune up the balancing interval */
-	if (((env.flags & LBF_ALL_PINNED) &&
-			sd->balance_interval < MAX_PINNED_INTERVAL) ||
-			(sd->balance_interval < sd->max_interval))
+	if ((env.flags & LBF_ALL_PINNED &&
+	     sd->balance_interval < MAX_PINNED_INTERVAL) ||
+	    (sd->balance_interval < sd->max_interval))
 		sd->balance_interval *= 2;
-
-	ld_moved = 0;
 out:
 	return ld_moved;
 }

--
2.7.4

maintainer
#1 lore raw
Quoted 5 lines · Valentin Schneider

When load_balance() fails to move some load because of task affinity, we end up increasing sd->balance_interval to delay the next periodic balance in the hopes that next time we look, that annoying pinned task(s) will be gone.

It's not about hope but to minimize useless periodic load balance as there is no possibility to balance anything

Quoted 4 lines

However, idle_balance() pays no attention to sd->balance_interval, yet it will still lead to an increase in balance_interval in case of pinned tasks.

I would say that this makes sense as there is no way to pull the pinned task on this rq so running periodic load balance (busy or idle) is a waste of time and resources

Quoted 3 lines

If we're going through several newidle balances (e.g. we have a periodic task), this can lead to a huge increase of the

This only happen when overload is set which means that there are tasks on another CPU but this one can't pull one of them.

Can you give us details about the use case that you care about ?

Also, If the interval reaches a value that becomes a problem for you why don't you reduce the max_interval with sysfs ? This max interval can be reach in several other occasions

Quoted 26 lines

balance_interval in a very small amount of time.

To prevent that, don't increase the balance interval when going through a newidle balance.

---
 kernel/sched/fair.c | 19 ++++++++++++++-----
 1 file changed, 14 insertions(+), 5 deletions(-)
kernel/sched/fair.c +8 -0
index 6bd142d..620910d 100644
@@ -8782,13 +8782,22 @@ static int load_balance(int this_cpu, struct rq *this_rq,
        sd->nr_balance_failed = 0;
 
 out_one_pinned:
+       ld_moved = 0;
+
+       /*
+        * idle_balance() disregards balance intervals, so we could repeatedly
+        * reach this code, which would lead to balance_interval skyrocketting
+        * in a short amount of time. Skip the balance_interval increase logic
+        * to avoid that.
+        */

kernel/sched/fair.c static int load_balance(int this_cpu, struct rq *this_rq, · line 8799

Quoted 10 lines
kernel/sched/fair.c +6 -3
+       if (env.idle == CPU_NEWLY_IDLE)
+               goto out;
+
        /* tune up the balancing interval */
-       if (((env.flags & LBF_ALL_PINNED) &&
-                       sd->balance_interval < MAX_PINNED_INTERVAL) ||
-                       (sd->balance_interval < sd->max_interval))
+       if ((env.flags & LBF_ALL_PINNED &&
+            sd->balance_interval < MAX_PINNED_INTERVAL) ||
+           (sd->balance_interval < sd->max_interval))

This looks like a code cleanup that is not related to the subject

Quoted 9 lines
kernel/sched/fair.c +0 -3
                sd->balance_interval *= 2;
-
-       ld_moved = 0;
 out:
        return ld_moved;
 }
--

2.7.4

#2 lore raw

Hi,

Quoted 12 lines · Vincent Guittot
Quoted 5 lines · Valentin Schneider

When load_balance() fails to move some load because of task affinity, we end up increasing sd->balance_interval to delay the next periodic balance in the hopes that next time we look, that annoying pinned task(s) will be gone.

It's not about hope but to minimize useless periodic load balance as there is no possibility to balance anything

Quoted 1 line
Quoted 8 lines
Quoted 3 lines

However, idle_balance() pays no attention to sd->balance_interval, yet it will still lead to an increase in balance_interval in case of pinned tasks.

I would say that this makes sense as there is no way to pull the pinned task on this rq so running periodic load balance (busy or idle) is a waste of time and resources

Increasing the delay for the next periodic balance when there's pinned tasks makes sense. The issue I have here is that the balance_interval can potentially be doubled at every failed idle_balance() without waiting for a sufficient amount of time.

When going through periodic balance, load_balance() is gated by:

    time_after_eq(jiffies, sd->last_balance + interval)

So if we previously ran load_balance() and failed to pull anything because of task affinity, we'll wait for at least the new interval before attempting another load_balance().

On the other hand, idle_balance() will call load_balance() regardless of balance_interval values. So if the task composition allows it, we can repeatedly fail to load_balance() and thus double balance_interval at every idle_balance() "tick". So you can go from 8ms to 512ms in a few successive idle_balance()s, whereas periodic balance would have to wait for at least the sum of all intermediate balance_intervals leading to 512 (8, 16, 32, etc).

Quoted 9 lines
Quoted 3 lines

If we're going through several newidle balances (e.g. we have a periodic task), this can lead to a huge increase of the

This only happen when overload is set which means that there are tasks on another CPU but this one can't pull one of them.

Can you give us details about the use case that you care about ?

It's the same as I presented last week - devlib (some python target communication library I use) has some phase where it spawns at lot of tasks at once to do some setup (busybox, shutils, bash...). Some of those tasks are pinned to a particular CPU, and that can lead to failed load_balance() - and to make things worse, there's a lot of idle_balance() in there.

Eventually when I start running my actual workload a few ~100ms later, it's impacted by that balance_interval increase.

Admittedly that's a specific use-case, but I don't think this quick increase is something that was intended.

Quoted 4 lines

Also, If the interval reaches a value that becomes a problem for you why don't you reduce the max_interval with sysfs ? This max interval can be reach in several other occasions

True, although I saw that as an unwanted behaviour rather than a tuning problem.

Quoted 30 lines
Quoted 30 lines

balance_interval in a very small amount of time.

To prevent that, don't increase the balance interval when going through a newidle balance.

---
 kernel/sched/fair.c | 19 ++++++++++++++-----
 1 file changed, 14 insertions(+), 5 deletions(-)
kernel/sched/fair.c +11 -0
index 6bd142d..620910d 100644
@@ -8782,13 +8782,22 @@ static int load_balance(int this_cpu, struct rq *this_rq,
        sd->nr_balance_failed = 0;
 
 out_one_pinned:
+       ld_moved = 0;
+
+       /*
+        * idle_balance() disregards balance intervals, so we could repeatedly
+        * reach this code, which would lead to balance_interval skyrocketting
+        * in a short amount of time. Skip the balance_interval increase logic
+        * to avoid that.
+        */
+       if (env.idle == CPU_NEWLY_IDLE)
+               goto out;
+
        /* tune up the balancing interval */
Quoted 9 lines

kernel/sched/fair.c static int load_balance(int this_cpu, struct rq *this_rq, · line 8799

Quoted 6 lines
kernel/sched/fair.c +3 -3
-       if (((env.flags & LBF_ALL_PINNED) &&
-                       sd->balance_interval < MAX_PINNED_INTERVAL) ||
-                       (sd->balance_interval < sd->max_interval))
+       if ((env.flags & LBF_ALL_PINNED &&
+            sd->balance_interval < MAX_PINNED_INTERVAL) ||
+           (sd->balance_interval < sd->max_interval))

This looks like a code cleanup that is not related to the subject

Absolutely, I figured I could get away with it but if that's preferred I can split that more clearly

Quoted 9 lines
Quoted 9 lines
kernel/sched/fair.c +0 -3
                sd->balance_interval *= 2;
-
-       ld_moved = 0;
 out:
        return ld_moved;
 }
--

2.7.4

maintainer
#3 lore raw
Quoted 49 lines · Valentin Schneider

Hi,

Quoted 12 lines · Vincent Guittot
Quoted 5 lines · Valentin Schneider

When load_balance() fails to move some load because of task affinity, we end up increasing sd->balance_interval to delay the next periodic balance in the hopes that next time we look, that annoying pinned task(s) will be gone.

It's not about hope but to minimize useless periodic load balance as there is no possibility to balance anything

Quoted 1 line
Quoted 8 lines
Quoted 3 lines

However, idle_balance() pays no attention to sd->balance_interval, yet it will still lead to an increase in balance_interval in case of pinned tasks.

I would say that this makes sense as there is no way to pull the pinned task on this rq so running periodic load balance (busy or idle) is a waste of time and resources

Increasing the delay for the next periodic balance when there's pinned tasks makes sense. The issue I have here is that the balance_interval can potentially be doubled at every failed idle_balance() without waiting for a sufficient amount of time.

When going through periodic balance, load_balance() is gated by:

    time_after_eq(jiffies, sd->last_balance + interval)

So if we previously ran load_balance() and failed to pull anything because of task affinity, we'll wait for at least the new interval before attempting another load_balance().

On the other hand, idle_balance() will call load_balance() regardless of balance_interval values. So if the task composition allows it, we can repeatedly fail to load_balance() and thus double balance_interval at every idle_balance() "tick". So you can go from 8ms to 512ms in a few successive idle_balance()s, whereas periodic balance would have to wait for at least the sum of all intermediate balance_intervals leading to 512 (8, 16, 32, etc).

Quoted 4 lines
Quoted 3 lines

If we're going through several newidle balances (e.g. we have a periodic task), this can lead to a huge increase of the

Quoted 7 lines
Quoted 5 lines

This only happen when overload is set which means that there are tasks on another CPU but this one can't pull one of them.

Can you give us details about the use case that you care about ?

It's the same as I presented last week - devlib (some python target communication

ok. you mean at linaro connect

Quoted 10 lines

library I use) has some phase where it spawns at lot of tasks at once to do some setup (busybox, shutils, bash...). Some of those tasks are pinned to a particular CPU, and that can lead to failed load_balance() - and to make things worse, there's a lot of idle_balance() in there.

Eventually when I start running my actual workload a few ~100ms later, it's impacted by that balance_interval increase.

Admittedly that's a specific use-case, but I don't think this quick increase is something that was intended.

Yes, this really sounds like a specific use-case. Unluckily you find a way to reach max interval quite easily/every time with your test set-up but keep in mind that this can also happen in real system life and without using the newly idle path.
So if it's a problem to have a interval at max value for your unitary test, it probably means that it's a problem for the system and the max value is too high

Taking advantage of all load_balance event to update the interval makes sense to me. It seems that you care about a short and regular balance interval more that minimizing overhead of load balancing. At the opposite, i'm sure that you don't complain if newly idle load balance resets the interval to min value and overwrite what the periodic load balance set up previously :-)

Quoted 48 lines
Quoted 5 lines

Also, If the interval reaches a value that becomes a problem for you why don't you reduce the max_interval with sysfs ? This max interval can be reach in several other occasions

True, although I saw that as an unwanted behaviour rather than a tuning problem.

Quoted 30 lines
Quoted 30 lines

balance_interval in a very small amount of time.

To prevent that, don't increase the balance interval when going through a newidle balance.

---
 kernel/sched/fair.c | 19 ++++++++++++++-----
 1 file changed, 14 insertions(+), 5 deletions(-)
kernel/sched/fair.c +11 -0
index 6bd142d..620910d 100644
@@ -8782,13 +8782,22 @@ static int load_balance(int this_cpu, struct rq *this_rq,
        sd->nr_balance_failed = 0;
 
 out_one_pinned:
+       ld_moved = 0;
+
+       /*
+        * idle_balance() disregards balance intervals, so we could repeatedly
+        * reach this code, which would lead to balance_interval skyrocketting
+        * in a short amount of time. Skip the balance_interval increase logic
+        * to avoid that.
+        */
+       if (env.idle == CPU_NEWLY_IDLE)
+               goto out;
+
        /* tune up the balancing interval */
Quoted 9 lines

kernel/sched/fair.c static int load_balance(int this_cpu, struct rq *this_rq, · line 8799

Quoted 6 lines
kernel/sched/fair.c +3 -3
-       if (((env.flags & LBF_ALL_PINNED) &&
-                       sd->balance_interval < MAX_PINNED_INTERVAL) ||
-                       (sd->balance_interval < sd->max_interval))
+       if ((env.flags & LBF_ALL_PINNED &&
+            sd->balance_interval < MAX_PINNED_INTERVAL) ||
+           (sd->balance_interval < sd->max_interval))

This looks like a code cleanup that is not related to the subject

Quoted 2 lines

Absolutely, I figured I could get away with it but if that's preferred I can split that more clearly

That's easier to make separate review.

Quoted 10 lines
Quoted 10 lines
Quoted 10 lines
kernel/sched/fair.c +0 -3
                sd->balance_interval *= 2;
-
-       ld_moved = 0;
 out:
        return ld_moved;
 }
--

2.7.4

#4 lore raw
Quoted 9 lines · Vincent Guittot

On Wed, 26 Sep 2018 at 11:35, Valentin Schneider
[...]

Quoted 4 lines
Quoted 2 lines

Can you give us details about the use case that you care about ?

It's the same as I presented last week - devlib (some python target communication

ok. you mean at linaro connect

Yeah, sorry.

Quoted 11 lines
Quoted 10 lines

library I use) has some phase where it spawns at lot of tasks at once to do some setup (busybox, shutils, bash...). Some of those tasks are pinned to a particular CPU, and that can lead to failed load_balance() - and to make things worse, there's a lot of idle_balance() in there.

Eventually when I start running my actual workload a few ~100ms later, it's impacted by that balance_interval increase.

Admittedly that's a specific use-case, but I don't think this quick increase is something that was intended.

Quoted 8 lines

Yes, this really sounds like a specific use-case. Unluckily you find a way to reach max interval quite easily/every time with your test set-up but keep in mind that this can also happen in real system life and without using the newly idle path.
So if it's a problem to have a interval at max value for your unitary test, it probably means that it's a problem for the system and the max value is too high

Limiting the max value for those tests is actually a good point, and I think I'll give it a shot. However...

Quoted 7 lines

Taking advantage of all load_balance event to update the interval makes sense to me. It seems that you care about a short and regular balance interval more that minimizing overhead of load balancing. At the opposite, i'm sure that you don't complain if newly idle load balance resets the interval to min value and overwrite what the periodic load balance set up previously :-)

...My concern is more about increasing balance_interval faster than we should. The proposed "fix" is to prevent any balance_interval increase when going through idle_balance(), but Patrick (added in cc) suggested offline that we could simply limit the rate at which we do these increases, so that they match what we do in rebalance_domains().

We'd still increase balance_interval on failed newidle load_balance(), but we wouldn't increase from min to max in e.g. 50ms. Would that work better for you?

Quoted 1 line
Quoted 1 line

[...]

maintainer
#5 lore raw
Quoted 51 lines · Valentin Schneider
Quoted 9 lines · Vincent Guittot

On Wed, 26 Sep 2018 at 11:35, Valentin Schneider
[...]

Quoted 4 lines
Quoted 2 lines

Can you give us details about the use case that you care about ?

It's the same as I presented last week - devlib (some python target communication

ok. you mean at linaro connect

Yeah, sorry.

Quoted 11 lines
Quoted 10 lines

library I use) has some phase where it spawns at lot of tasks at once to do some setup (busybox, shutils, bash...). Some of those tasks are pinned to a particular CPU, and that can lead to failed load_balance() - and to make things worse, there's a lot of idle_balance() in there.

Eventually when I start running my actual workload a few ~100ms later, it's impacted by that balance_interval increase.

Admittedly that's a specific use-case, but I don't think this quick increase is something that was intended.

Quoted 8 lines

Yes, this really sounds like a specific use-case. Unluckily you find a way to reach max interval quite easily/every time with your test set-up but keep in mind that this can also happen in real system life and without using the newly idle path.
So if it's a problem to have a interval at max value for your unitary test, it probably means that it's a problem for the system and the max value is too high

Limiting the max value for those tests is actually a good point, and I think I'll give it a shot. However...

Quoted 7 lines

Taking advantage of all load_balance event to update the interval makes sense to me. It seems that you care about a short and regular balance interval more that minimizing overhead of load balancing. At the opposite, i'm sure that you don't complain if newly idle load balance resets the interval to min value and overwrite what the periodic load balance set up previously :-)

...My concern is more about increasing balance_interval faster than we should. The proposed "fix" is to prevent any balance_interval increase when going through idle_balance(), but Patrick (added in cc) suggested offline that we could simply limit the rate at which we do these increases, so that they match what we do in rebalance_domains().

Quoted 3 lines

We'd still increase balance_interval on failed newidle load_balance(), but we wouldn't increase from min to max in e.g. 50ms. Would that work better for you?

adding a rate limite would be a reasonnable solution.

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines

[...]

maintainer
#6 lore raw
In reply to Vincent Guittot
Quoted 21 lines · Vincent Guittot

On Wed, 26 Sep 2018 at 11:35, Valentin Schneider

Quoted 10 lines

library I use) has some phase where it spawns at lot of tasks at once to do some setup (busybox, shutils, bash...). Some of those tasks are pinned to a particular CPU, and that can lead to failed load_balance() - and to make things worse, there's a lot of idle_balance() in there.

Eventually when I start running my actual workload a few ~100ms later, it's impacted by that balance_interval increase.

Admittedly that's a specific use-case, but I don't think this quick increase is something that was intended.

Yes, this really sounds like a specific use-case. Unluckily you find a way to reach max interval quite easily/every time with your test set-up but keep in mind that this can also happen in real system life and without using the newly idle path.
So if it's a problem to have a interval at max value for your unitary test, it probably means that it's a problem for the system and the max value is too high

Quoted 6 lines

Taking advantage of all load_balance event to update the interval makes sense to me. It seems that you care about a short and regular balance interval more that minimizing overhead of load balancing. At the opposite, i'm sure that you don't complain if newly idle load balance resets the interval to min value and overwrite what the periodic load balance set up previously :-)

Well, we've excluded newidle balance from updating such stats before. So in that respect the patch proposed by Valentin isn't weird.

Consider for example:

58b26c4c0257 ("sched: Increment cache_nice_tries only on periodic lb")

In general I think it makes perfect sense to exclude newidle balance from such stats; you get much more stable results from the regular balance.

maintainer
#7 lore raw
Quoted 33 lines · Peter Zijlstra
Quoted 21 lines · Vincent Guittot

On Wed, 26 Sep 2018 at 11:35, Valentin Schneider

Quoted 10 lines

library I use) has some phase where it spawns at lot of tasks at once to do some setup (busybox, shutils, bash...). Some of those tasks are pinned to a particular CPU, and that can lead to failed load_balance() - and to make things worse, there's a lot of idle_balance() in there.

Eventually when I start running my actual workload a few ~100ms later, it's impacted by that balance_interval increase.

Admittedly that's a specific use-case, but I don't think this quick increase is something that was intended.

Yes, this really sounds like a specific use-case. Unluckily you find a way to reach max interval quite easily/every time with your test set-up but keep in mind that this can also happen in real system life and without using the newly idle path.
So if it's a problem to have a interval at max value for your unitary test, it probably means that it's a problem for the system and the max value is too high

Quoted 6 lines

Taking advantage of all load_balance event to update the interval makes sense to me. It seems that you care about a short and regular balance interval more that minimizing overhead of load balancing. At the opposite, i'm sure that you don't complain if newly idle load balance resets the interval to min value and overwrite what the periodic load balance set up previously :-)

Well, we've excluded newidle balance from updating such stats before. So in that respect the patch proposed by Valentin isn't weird.

Quoted 7 lines

Consider for example:

58b26c4c0257 ("sched: Increment cache_nice_tries only on periodic lb")

In general I think it makes perfect sense to exclude newidle balance from such stats; you get much more stable results from the regular balance.

Ok so in this case we should exclude all update of the interval during newly idle and not only some of them