sched: set loop_max after rq lock is taken

RFC In review Uladzislau Rezki 4 participants 16 messages Feb 8, 2017 – Mar 8, 2017 Scheduler

lore

Share & tools

lore

Uladzislau Rezki

author

2017-02-08 08:52 UTC #0 lore raw

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

From: Uladzislau 2 Rezki <[email protected]>

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 <[email protected]>

---
 kernel/sched/fair.c | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)

kernel/sched/fair.c +6 -1

index 6559d19..4be7193 100644
@@ -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
 		 */

Signature · 1 line

2.1.4

Uladzislau Rezki

author

2017-02-08 08:50 UTC #1 lore raw

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

From: Uladzislau 2 Rezki <[email protected]>

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 <[email protected]>

---
 kernel/sched/fair.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

kernel/sched/fair.c +1 -1

index 4be7193..232ef3c 100644
@@ -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

Signature · 1 line

2.1.4

Peter Zijlstra

maintainer

2017-02-09 13:38 UTC #2 lore raw

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

Quoted 6 lines · Uladzislau Rezki

From: Uladzislau 2 Rezki <[email protected]>
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.

Uladzislau Rezki

author

2017-02-09 19:00 UTC #3 lore raw

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

Quoted 10 lines · Peter Zijlstra

Quoted 6 lines · Uladzislau Rezki
From: Uladzislau 2 Rezki <[email protected]>
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.

Quoted 4 lines

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.

Signature · 1 line

Uladzislau Rezki

Uladzislau Rezki

author

2017-02-08 08:52 UTC #4 lore raw

RFC v2 3/3 sched: ignore task_h_load for CPU_NEWLY_IDLE

In reply to Uladzislau Rezki

From: Uladzislau 2 Rezki <[email protected]>

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 <[email protected]>

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

kernel/sched/fair.c +11 -2

index 232ef3c..29e0d7f 100644
@@ -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);

Signature · 1 line

2.1.4

Mike Galbraith

2017-02-08 09:27 UTC #5 lore raw

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

Quoted 3 lines · Uladzislau Rezki

From: Uladzislau 2 Rezki <[email protected]>
A load balancer calculates imbalance factor for particular shed

^sched

Quoted 4 lines

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

Quoted 12 lines

Signed-off-by Uladzislau 2 Rezki <[email protected]>
---
 kernel/sched/fair.c | 13 +++++++++++--
 1 file changed, 11 insertions(+), 2 deletions(-)
kernel/sched/fair.c +0 -0
index 232ef3c..29e0d7f 100644
	> 	> env->loop++;

kernel/sched/fair.c static int detach_tasks(struct lb_env *env) · line 6837

Quoted 8 lines

kernel/sched/fair.c +3 -2

@@ -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).

Uladzislau Rezki

author

2017-02-09 10:13 UTC #6 lore raw

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

Quoted 6 lines · Uladzislau Rezki

Quoted 3 lines
From: Uladzislau 2 Rezki <[email protected]>
A load balancer calculates imbalance factor for particular shed
^sched

Will fix that.

Quoted 5 lines

Quoted 4 lines
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.

Quoted 15 lines

Signed-off-by Uladzislau 2 Rezki <[email protected]>

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

kernel/sched/fair.c +0 -0

index 232ef3c..29e0d7f 100644
      >       > 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;

Quoted 7 lines

kernel/sched/fair.c static int detach_tasks(struct lb_env *env) · line 6837
Quoted 5 lines
kernel/sched/fair.c +3 -2
->    >       > 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

Peter Zijlstra

maintainer

2017-02-09 12:23 UTC #7 lore raw

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

In reply to Uladzislau Rezki

Quoted 8 lines · Uladzislau Rezki

From: Uladzislau 2 Rezki <[email protected]>
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.

Uladzislau Rezki

author

2017-02-09 19:01 UTC #8 lore raw

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

Quoted 11 lines · Peter Zijlstra

Quoted 8 lines · Uladzislau Rezki
From: Uladzislau 2 Rezki <[email protected]>
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.

Quoted 3 lines

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

I agree.

Quoted 4 lines

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

Peter Zijlstra

maintainer

2017-02-13 13:51 UTC #9 lore raw

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

Quoted 30 lines · Uladzislau Rezki

Quoted 3 lines
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

Quoted 3 lines

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.

Uladzislau Rezki

author

2017-02-13 17:17 UTC #10 lore raw

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

Quoted 32 lines · Peter Zijlstra

Quoted 30 lines · Uladzislau Rezki
Quoted 3 lines
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

Quoted 9 lines

Quoted 3 lines
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.

Quoted 11 lines

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

Uladzislau Rezki

author

2017-02-14 18:28 UTC #11 lore raw

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

Quoted 14 lines

Quoted 6 lines
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.
Quoted 6 lines
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().

Quoted 7 lines

Quoted 5 lines
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

Signature · 1 line

Uladzislau Rezki

Dietmar Eggemann

reviewer

2017-02-15 18:58 UTC #12 lore raw

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

Quoted 6 lines · Uladzislau Rezki

Quoted 6 lines
Quoted 6 lines
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?

Quoted 7 lines

Quoted 7 lines
Yes, i will prepare a patch accordingly, no problem.
Quoted 5 lines
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?

Quoted 10 lines

Quoted 7 lines
Quoted 5 lines
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

author

2017-02-16 11:20 UTC #13 lore raw

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

Quoted 11 lines · Dietmar Eggemann

Quoted 10 lines · Uladzislau Rezki
Quoted 10 lines
Quoted 7 lines
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.
Quoted 1 line

Quoted 9 lines

Quoted 4 lines
Quoted 4 lines
Quoted 4 lines
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:

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

#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

Uladzislau Rezki

author

2017-03-08 15:36 UTC #14 lore raw

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

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

Quoted 52 lines · Uladzislau Rezki

Quoted 11 lines · Dietmar Eggemann
Quoted 10 lines · Uladzislau Rezki
Quoted 10 lines
Quoted 7 lines
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.
Quoted 1 line
Quoted 9 lines
Quoted 4 lines
Quoted 4 lines
Quoted 4 lines
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

Peter Zijlstra

maintainer

2017-02-09 13:35 UTC #15 lore raw

In reply to Uladzislau Rezki

Quoted 8 lines · Uladzislau Rezki

From: Uladzislau 2 Rezki <[email protected]>
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.