[RFC,v2 1/3] sched: set loop_max after rq lock is taken

[RFC,v2 1/3] sched: set loop_max after rq lock is taken

[Uladzislau Rezki]

From: Uladzislau 2 Rezki <uladzislau2.rezki@sonymobile.com>

While doing a load balance there is a race in setting
loop_max variable since nr_running can be changed causing
incorect iteration loops.

As a result we may skip some candidates or check the same
tasks again.

Signed-off-by: Uladzislau 2 Rezki <uladzislau2.rezki@sonymobile.com>
---
 kernel/sched/fair.c | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 6559d19..4be7193 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -8073,12 +8073,17 @@ static int load_balance(int this_cpu, struct rq *this_rq,
 		 * correctly treated as an imbalance.
 		 */
 		env.flags |= LBF_ALL_PINNED;
-		env.loop_max  = min(sysctl_sched_nr_migrate, busiest->nr_running);
 
 more_balance:
 		raw_spin_lock_irqsave(&busiest->lock, flags);
 
 		/*
+		 * Set loop_max when rq's lock is taken to prevent a race.
+		 */
+		env.loop_max = min(sysctl_sched_nr_migrate,
+						busiest->nr_running);
+
+		/*
 		 * cur_ld_moved - load moved in current iteration
 		 * ld_moved     - cumulative load moved across iterations
 		 */
-- 
2.1.4

[RFC,v2 2/3] sched: set number of iterations to h_nr_running

[Uladzislau Rezki]

From: Uladzislau 2 Rezki <uladzislau2.rezki@sonymobile.com>

It is possible that busiest run queue has multiple RT tasks,
whereas no CFS tasks, that is why it is reasonable to use
h_nr_running instead, because a load balance only applies
for CFS related tasks.

Signed-off-by: Uladzislau 2 Rezki <uladzislau2.rezki@sonymobile.com>
---
 kernel/sched/fair.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 4be7193..232ef3c 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -8081,7 +8081,7 @@ static int load_balance(int this_cpu, struct rq *this_rq,
 		 * Set loop_max when rq's lock is taken to prevent a race.
 		 */
 		env.loop_max = min(sysctl_sched_nr_migrate,
-						busiest->nr_running);
+						busiest->cfs.h_nr_running);
 
 		/*
 		 * cur_ld_moved - load moved in current iteration
-- 
2.1.4

Re: [RFC,v2 2/3] sched: set number of iterations to h_nr_running

[Peter Zijlstra]

On Wed, Feb 08, 2017 at 09:43:28AM +0100, Uladzislau Rezki wrote:
> From: Uladzislau 2 Rezki <uladzislau2.rezki@sonymobile.com>
> 
> It is possible that busiest run queue has multiple RT tasks,
> whereas no CFS tasks, that is why it is reasonable to use
> h_nr_running instead, because a load balance only applies
> for CFS related tasks.

Sure, I suppose that makes sense, but then it would make even more sense
to do a more thorough audit of the code and make sure all remaining
rq::nr_running uses are correct.

Re: [RFC,v2 2/3] sched: set number of iterations to h_nr_running

[Uladzislau Rezki]

On Thu, Feb 9, 2017 at 1:20 PM, Peter Zijlstra <peterz@infradead.org> wrote:
> On Wed, Feb 08, 2017 at 09:43:28AM +0100, Uladzislau Rezki wrote:
>> From: Uladzislau 2 Rezki <uladzislau2.rezki@sonymobile.com>
>>
>> It is possible that busiest run queue has multiple RT tasks,
>> whereas no CFS tasks, that is why it is reasonable to use
>> h_nr_running instead, because a load balance only applies
>> for CFS related tasks.
>

>
> Sure, I suppose that makes sense, but then it would make even more sense
> to do a more thorough audit of the code and make sure all remaining
> rq::nr_running uses are correct.
>
Indeed. I did not want to touch othe places, due to my specific test case.
There are still a few raming places. I can prepare a new patch that covers
all of them if that is ok.

-- 
Uladzislau Rezki

[RFC,v2 3/3] sched: ignore task_h_load for CPU_NEWLY_IDLE

[Uladzislau Rezki]

From: Uladzislau 2 Rezki <uladzislau2.rezki@sonymobile.com>

A load balancer calculates imbalance factor for particular shed
domain and tries to steal up the prescribed amount of weighted load.
However, a small imbalance factor would sometimes prevent us from
stealing any tasks at all. When a CPU is newly idle, it should
steal first task which passes a migration criteria.

Signed-off-by: Uladzislau 2 Rezki <uladzislau2.rezki@sonymobile.com>
---
 kernel/sched/fair.c | 13 +++++++++++--
 1 file changed, 11 insertions(+), 2 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 232ef3c..29e0d7f 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -6802,6 +6802,14 @@ static int detach_tasks(struct lb_env *env)
 		if (env->idle != CPU_NOT_IDLE && env->src_rq->nr_running <= 1)
 			break;
 
+		/*
+		 * Another CPU can place tasks, since we do not hold dst_rq lock
+		 * while doing balancing. If newly idle CPU already got something,
+		 * give up to reduce latency.
+		 */
+		if (env->idle == CPU_NEWLY_IDLE && env->dst_rq->nr_running > 0)
+			break;
+
 		p = list_first_entry(tasks, struct task_struct, se.group_node);
 
 		env->loop++;
@@ -6824,8 +6832,9 @@ static int detach_tasks(struct lb_env *env)
 		if (sched_feat(LB_MIN) && load < 16 && !env->sd->nr_balance_failed)
 			goto next;
 
-		if ((load / 2) > env->imbalance)
-			goto next;
+		if (env->idle != CPU_NEWLY_IDLE)
+			if ((load / 2) > env->imbalance)
+				goto next;
 
 		detach_task(p, env);
 		list_add(&p->se.group_node, &env->tasks);
-- 
2.1.4

Re: [RFC,v2 3/3] sched: ignore task_h_load for CPU_NEWLY_IDLE

[Mike Galbraith]

On Wed, 2017-02-08 at 09:43 +0100, Uladzislau Rezki wrote:
> From: Uladzislau 2 Rezki <uladzislau2.rezki@sonymobile.com>
> 
> A load balancer calculates imbalance factor for particular shed
                                                             ^sched
> domain and tries to steal up the prescribed amount of weighted load.
> However, a small imbalance factor would sometimes prevent us from
> stealing any tasks at all. When a CPU is newly idle, it should
> steal first task which passes a migration criteria.
                         s/passes a/meets the
> 
> Signed-off-by: Uladzislau 2 Rezki <uladzislau2.rezki@sonymobile.com>
> ---
>  kernel/sched/fair.c | 13 +++++++++++--
>  1 file changed, 11 insertions(+), 2 deletions(-)
> 
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 232ef3c..29e0d7f 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> 	> 	> env->loop++;
> @@ -6824,8 +6832,9 @@ static int detach_tasks(struct lb_env *env)
>  > 	> 	> if (sched_feat(LB_MIN) && load < 16 && !env->sd->nr_balance_failed)
>  > 	> 	> 	> goto next;
>  
> -> 	> 	> if ((load / 2) > env->imbalance)
> -> 	> 	> 	> goto next;
> +> 	> 	> if (env->idle != CPU_NEWLY_IDLE)
> +> 	> 	> 	> if ((load / 2) > env->imbalance)
> +> 	> 	> 	> 	> goto next;

Those two ifs could be one ala if (foo && bar).

Re: [RFC,v2 3/3] sched: ignore task_h_load for CPU_NEWLY_IDLE

[Uladzislau Rezki]

>
> On Wed, 2017-02-08 at 09:43 +0100, Uladzislau Rezki wrote:
> > From: Uladzislau 2 Rezki <uladzislau2.rezki@sonymobile.com>
> >
> > A load balancer calculates imbalance factor for particular shed
>                                                              ^sched
Will fix that.

> > domain and tries to steal up the prescribed amount of weighted load.
> > However, a small imbalance factor would sometimes prevent us from
> > stealing any tasks at all. When a CPU is newly idle, it should
> > steal first task which passes a migration criteria.
>                          s/passes a/meets the
Will change the description.

> >
> > Signed-off-by: Uladzislau 2 Rezki <uladzislau2.rezki@sonymobile.com>
> > ---
> >  kernel/sched/fair.c | 13 +++++++++++--
> >  1 file changed, 11 insertions(+), 2 deletions(-)
> >
> > diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> > index 232ef3c..29e0d7f 100644
> > --- a/kernel/sched/fair.c
> > +++ b/kernel/sched/fair.c
> >       >       > env->loop++;
> > @@ -6824,8 +6832,9 @@ static int detach_tasks(struct lb_env *env)
> >  >    >       > if (sched_feat(LB_MIN) && load < 16 && !env->sd->nr_balance_failed)
> >  >    >       >       > goto next;
> >
> > ->    >       > if ((load / 2) > env->imbalance)
> > ->    >       >       > goto next;
> > +>    >       > if (env->idle != CPU_NEWLY_IDLE)
> > +>    >       >       > if ((load / 2) > env->imbalance)
> > +>    >       >       >       > goto next;
>
> Those two ifs could be one ala if (foo && bar).
Agree.

--
Uladzislau Rezki

Re: [RFC,v2 3/3] sched: ignore task_h_load for CPU_NEWLY_IDLE

[Peter Zijlstra]

On Wed, Feb 08, 2017 at 09:43:29AM +0100, Uladzislau Rezki wrote:
> From: Uladzislau 2 Rezki <uladzislau2.rezki@sonymobile.com>
> 
> A load balancer calculates imbalance factor for particular shed
> domain and tries to steal up the prescribed amount of weighted load.
> However, a small imbalance factor would sometimes prevent us from
> stealing any tasks at all. When a CPU is newly idle, it should
> steal first task which passes a migration criteria.
> 

So ideally we'd reduce the number of special cases instead of increase
them. Does this patch make an actual difference, if so how much and with
what workload?

Also, I suppose that if we finally manage to parameterize the whole
load-balancing to act on: nr_running/util/load depending on the domain
this all naturally falls into place.

Re: [RFC,v2 3/3] sched: ignore task_h_load for CPU_NEWLY_IDLE

[Uladzislau Rezki]

On Thu, Feb 9, 2017 at 1:22 PM, Peter Zijlstra <peterz@infradead.org> wrote:
> On Wed, Feb 08, 2017 at 09:43:29AM +0100, Uladzislau Rezki wrote:
>> From: Uladzislau 2 Rezki <uladzislau2.rezki@sonymobile.com>
>>
>> A load balancer calculates imbalance factor for particular shed
>> domain and tries to steal up the prescribed amount of weighted load.
>> However, a small imbalance factor would sometimes prevent us from
>> stealing any tasks at all. When a CPU is newly idle, it should
>> steal first task which passes a migration criteria.
>>

>
> So ideally we'd reduce the number of special cases instead of increase
> them.
>
I agree.

>
> Does this patch make an actual difference, if so how much and with
> what workload?
>
Yes, it does. I see a slight improvement when it comes to frame drops
(in my case drops per/two seconds). Basically a test case is left finger
swipe on the display (21 times, duration is 2 seconds + 1 second sleep
between iterations):

0   Framedrops:  7    5
1   Framedrops:  5    3
2   Framedrops:  8    5
3   Framedrops:  4    5
4   Framedrops:  3    3
5   Framedrops:  6    4
6   Framedrops:  3    2
7   Framedrops:  3    4
8   Framedrops:  5    3
9   Framedrops:  3    3
10 Framedrops:  7    4
11 Framedrops:  3    4
12 Framedrops:  3    3
13 Framedrops:  3    3
14 Framedrops:  3    5
15 Framedrops:  7    3
16 Framedrops:  5    3
17 Framedrops:  3    2
18 Framedrops:  5    3
19 Framedrops:  4    3
20 Framedrops:  3    2

max is 8 vs 5; min is 2 vs 3.

As for applied load, it is not significant and i would say is "light".

--
Uladzislau Rezki

Re: [RFC,v2 3/3] sched: ignore task_h_load for CPU_NEWLY_IDLE

[Peter Zijlstra]

On Thu, Feb 09, 2017 at 07:54:05PM +0100, Uladzislau Rezki wrote:

> > Does this patch make an actual difference, if so how much and with
> > what workload?
> >
> Yes, it does. I see a slight improvement when it comes to frame drops
> (in my case drops per/two seconds). Basically a test case is left finger
> swipe on the display (21 times, duration is 2 seconds + 1 second sleep
> between iterations):
> 
> 0   Framedrops:  7    5
> 1   Framedrops:  5    3
> 2   Framedrops:  8    5
> 3   Framedrops:  4    5
> 4   Framedrops:  3    3
> 5   Framedrops:  6    4
> 6   Framedrops:  3    2
> 7   Framedrops:  3    4
> 8   Framedrops:  5    3
> 9   Framedrops:  3    3
> 10 Framedrops:  7    4
> 11 Framedrops:  3    4
> 12 Framedrops:  3    3
> 13 Framedrops:  3    3
> 14 Framedrops:  3    5
> 15 Framedrops:  7    3
> 16 Framedrops:  5    3
> 17 Framedrops:  3    2
> 18 Framedrops:  5    3
> 19 Framedrops:  4    3
> 20 Framedrops:  3    2
> 
> max is 8 vs 5; min is 2 vs 3.
> 
> As for applied load, it is not significant and i would say is "light".

So that is useful information that should have been in the Changelog.

OK, can you respin this patch with adjusted Changelog and taking Mike's
feedback?

Also, I worry about the effects of this on !PREEMPT kernels, the first
hunk (which explicitly states is about latency) should be under
CONFIG_PREEMPT to match the similar case we already have in
detach_tasks().

But your second hunk, which ignores the actual load of tasks in favour
of just moving _something_ already, is utterly dangerous if not coupled
with these two other conditions, so arguably that too should be under
CONFIG_PREEMPT.

Re: [RFC,v2 3/3] sched: ignore task_h_load for CPU_NEWLY_IDLE

[Uladzislau Rezki]

On Mon, Feb 13, 2017 at 2:51 PM, Peter Zijlstra <peterz@infradead.org> wrote:
> On Thu, Feb 09, 2017 at 07:54:05PM +0100, Uladzislau Rezki wrote:
>
>> > Does this patch make an actual difference, if so how much and with
>> > what workload?
>> >
>> Yes, it does. I see a slight improvement when it comes to frame drops
>> (in my case drops per/two seconds). Basically a test case is left finger
>> swipe on the display (21 times, duration is 2 seconds + 1 second sleep
>> between iterations):
>>
>> 0   Framedrops:  7    5
>> 1   Framedrops:  5    3
>> 2   Framedrops:  8    5
>> 3   Framedrops:  4    5
>> 4   Framedrops:  3    3
>> 5   Framedrops:  6    4
>> 6   Framedrops:  3    2
>> 7   Framedrops:  3    4
>> 8   Framedrops:  5    3
>> 9   Framedrops:  3    3
>> 10 Framedrops:  7    4
>> 11 Framedrops:  3    4
>> 12 Framedrops:  3    3
>> 13 Framedrops:  3    3
>> 14 Framedrops:  3    5
>> 15 Framedrops:  7    3
>> 16 Framedrops:  5    3
>> 17 Framedrops:  3    2
>> 18 Framedrops:  5    3
>> 19 Framedrops:  4    3
>> 20 Framedrops:  3    2
>>
>> max is 8 vs 5; min is 2 vs 3.
>>
>> As for applied load, it is not significant and i would say is "light".
>
> So that is useful information that should have been in the Changelog.
>
> OK, can you respin this patch with adjusted Changelog and taking Mike's
> feedback?
>
Yes, i will prepare a patch accordingly, no problem.

>
> Also, I worry about the effects of this on !PREEMPT kernels, the first
> hunk (which explicitly states is about latency) should be under
> CONFIG_PREEMPT to match the similar case we already have in
> detach_tasks().
>
> But your second hunk, which ignores the actual load of tasks in favour
> of just moving _something_ already, is utterly dangerous if not coupled
> with these two other conditions, so arguably that too should be under
> CONFIG_PREEMPT.
>
I see your point. Will round both with CONFIG_PREEMPT.

--
Uladzislau Rezki

Re: [RFC,v2 3/3] sched: ignore task_h_load for CPU_NEWLY_IDLE

[Uladzislau Rezki]

>>
>> So that is useful information that should have been in the Changelog.
>>
>> OK, can you respin this patch with adjusted Changelog and taking Mike's
>> feedback?
>>
> Yes, i will prepare a patch accordingly, no problem.
>
>>
>> Also, I worry about the effects of this on !PREEMPT kernels, the first
>> hunk (which explicitly states is about latency) should be under
>> CONFIG_PREEMPT to match the similar case we already have in
>> detach_tasks().
>>
>> But your second hunk, which ignores the actual load of tasks in favour
>> of just moving _something_ already, is utterly dangerous if not coupled
>> with these two other conditions, so arguably that too should be under
>> CONFIG_PREEMPT.
>>
> I see your point. Will round both with CONFIG_PREEMPT.
>
I have upload a new patch, please find it here:
https://lkml.org/lkml/2017/2/14/334

-- 
Uladzislau Rezki

Re: [RFC,v2 3/3] sched: ignore task_h_load for CPU_NEWLY_IDLE

[Dietmar Eggemann]

On 02/14/2017 06:28 PM, Uladzislau Rezki wrote:
>>>
>>> So that is useful information that should have been in the Changelog.
>>>
>>> OK, can you respin this patch with adjusted Changelog and taking Mike's
>>> feedback?
>>>
>> Yes, i will prepare a patch accordingly, no problem.
>>
>>>
>>> Also, I worry about the effects of this on !PREEMPT kernels, the first
>>> hunk (which explicitly states is about latency) should be under
>>> CONFIG_PREEMPT to match the similar case we already have in
>>> detach_tasks().

This one uses #ifdef CONFIG_PREEMPT whereas you use 
IS_ENABLED(CONFIG_PREEMPT). Is there a particular reason for this?

>>> But your second hunk, which ignores the actual load of tasks in favour
>>> of just moving _something_ already, is utterly dangerous if not coupled
>>> with these two other conditions, so arguably that too should be under
>>> CONFIG_PREEMPT.
>>>
>> I see your point. Will round both with CONFIG_PREEMPT.
>>
> I have upload a new patch, please find it here:
> https://lkml.org/lkml/2017/2/14/334
>

Re: [RFC,v2 3/3] sched: ignore task_h_load for CPU_NEWLY_IDLE

[Uladzislau Rezki]

On Wed, Feb 15, 2017 at 7:58 PM, Dietmar Eggemann
<dietmar.eggemann@arm.com> wrote:
> On 02/14/2017 06:28 PM, Uladzislau Rezki wrote:
>>>>
>>>>
>>>> So that is useful information that should have been in the Changelog.
>>>>
>>>> OK, can you respin this patch with adjusted Changelog and taking Mike's
>>>> feedback?
>>>>
>>> Yes, i will prepare a patch accordingly, no problem.
>>>
>>>>
>>>> Also, I worry about the effects of this on !PREEMPT kernels, the first
>>>> hunk (which explicitly states is about latency) should be under
>>>> CONFIG_PREEMPT to match the similar case we already have in
>>>> detach_tasks().
>
>
> This one uses #ifdef CONFIG_PREEMPT whereas you use
> IS_ENABLED(CONFIG_PREEMPT). Is there a particular reason for this?
>
I just wanted to put it under one line instead of using #ifdefs in my
second hunk,
so that is a matter of taste. Also, please find below different
variants of how it can be
rewriten:

<variant 1>
#ifdef CONFIG_PREEMPT
    if (env->idle != CPU_NEWLY_IDLE)
#endif
        if ((load / 2) > env->imbalance)
            goto next;
<variant 1>

<variant 2>
#ifdef CONFIG_PREEMPT
    if (env->idle != CPU_NEWLY_IDLE &&
            (load / 2) > env->imbalance)
        goto next;
#else
    if ((load / 2) > env->imbalance)
        goto next;
#endif
<variant 2>

If somebody has any preferences or concerns, please comment, i will
re-spin the patch.

--
Uladzislau Rezki

Re: [RFC,v2 3/3] sched: ignore task_h_load for CPU_NEWLY_IDLE

[Uladzislau Rezki]

Hello.

Let's decide how to proceed with https://lkml.org/lkml/2017/2/14/334 patch.
Despite it is not a big change, i think it is important and ready to
be submited,
unless there are still any comments.

--
Uladzislau Rezki

On Thu, Feb 16, 2017 at 12:20 PM, Uladzislau Rezki <urezki@gmail.com> wrote:
> On Wed, Feb 15, 2017 at 7:58 PM, Dietmar Eggemann
> <dietmar.eggemann@arm.com> wrote:
>> On 02/14/2017 06:28 PM, Uladzislau Rezki wrote:
>>>>>
>>>>>
>>>>> So that is useful information that should have been in the Changelog.
>>>>>
>>>>> OK, can you respin this patch with adjusted Changelog and taking Mike's
>>>>> feedback?
>>>>>
>>>> Yes, i will prepare a patch accordingly, no problem.
>>>>
>>>>>
>>>>> Also, I worry about the effects of this on !PREEMPT kernels, the first
>>>>> hunk (which explicitly states is about latency) should be under
>>>>> CONFIG_PREEMPT to match the similar case we already have in
>>>>> detach_tasks().
>>
>>
>> This one uses #ifdef CONFIG_PREEMPT whereas you use
>> IS_ENABLED(CONFIG_PREEMPT). Is there a particular reason for this?
>>
> I just wanted to put it under one line instead of using #ifdefs in my
> second hunk,
> so that is a matter of taste. Also, please find below different
> variants of how it can be
> rewriten:
>
> <variant 1>
> #ifdef CONFIG_PREEMPT
>     if (env->idle != CPU_NEWLY_IDLE)
> #endif
>         if ((load / 2) > env->imbalance)
>             goto next;
> <variant 1>
>
> <variant 2>
> #ifdef CONFIG_PREEMPT
>     if (env->idle != CPU_NEWLY_IDLE &&
>             (load / 2) > env->imbalance)
>         goto next;
> #else
>     if ((load / 2) > env->imbalance)
>         goto next;
> #endif
> <variant 2>
>
> If somebody has any preferences or concerns, please comment, i will
> re-spin the patch.
>
> --
> Uladzislau Rezki

Re: [RFC,v2 1/3] sched: set loop_max after rq lock is taken

[Peter Zijlstra]

On Wed, Feb 08, 2017 at 09:43:27AM +0100, Uladzislau Rezki wrote:
> From: Uladzislau 2 Rezki <uladzislau2.rezki@sonymobile.com>
> 
> While doing a load balance there is a race in setting
> loop_max variable since nr_running can be changed causing
> incorect iteration loops.
> 
> As a result we may skip some candidates or check the same
> tasks again.

When doing the actual migration we'll drop this lock again and
nr_running can change again.

This cannot be done perfectly, all of load-balancing is riddled with
races like this, nobody cares.