Skip to contentSkip to conversation

sched/fair: limit load balance redo times at the same sched_domain level

RFC PATCH In review Aubrey Li 4 participants 11 messages Jan 25, 2021 – Feb 24, 2021 Scheduler

lore
Share & tools
lore

Aubrey Li

author
#0 lore raw

RFC PATCH 1/1 sched/fair: limit load balance redo times at the same sched_domain level

A long-tail load balance cost is observed on the newly idle path, this is caused by a race window between the first nr_running check of the busiest runqueue and its nr_running recheck in detach_tasks.

Before the busiest runqueue is locked, the tasks on the busiest runqueue could be pulled by other CPUs and nr_running of the busiest runqueu becomes 1, this causes detach_tasks breaks with LBF_ALL_PINNED flag set, and triggers load_balance redo at the same sched_domain level.

In order to find the new busiest sched_group and CPU, load balance will recompute and update the various load statistics, which eventually leads to the long-tail load balance cost.

This patch introduces a variable(sched_nr_lb_redo) to limit load balance redo times, combined with sysctl_sched_nr_migrate, the max load balance cost is reduced from 100+ us to 70+ us, measured on a 4s x86 system with 192 logical CPUs.

Cc Andi Kleen <[email protected]>
Cc Tim Chen <[email protected]>
Cc Srinivas Pandruvada <[email protected]>
Cc Rafael J. Wysocki <[email protected]>
---
 kernel/sched/fair.c | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)
kernel/sched/fair.c +6 -1
index ae7ceba..b59f371 100644
@@ -7407,6 +7407,8 @@ struct lb_env {
 	unsigned int		loop;
 	unsigned int		loop_break;
 	unsigned int		loop_max;
+	unsigned int		redo_cnt;
+	unsigned int		redo_max;
 
 	enum fbq_type		fbq_type;
 	enum migration_type	migration_type;
@@ -9525,6 +9527,7 @@ static int should_we_balance(struct lb_env *env)
 	return group_balance_cpu(sg) == env->dst_cpu;
 }
 
+static const unsigned int sched_nr_lb_redo = 1;
 /*
  * Check this_cpu to ensure it is balanced within domain. Attempt to move
  * tasks if there is an imbalance.
@@ -9547,6 +9550,7 @@ static int load_balance(int this_cpu, struct rq *this_rq,
 		.dst_grpmask    = sched_group_span(sd->groups),
 		.idle		= idle,
 		.loop_break	= sched_nr_migrate_break,
+		.redo_max	= sched_nr_lb_redo,
 		.cpus		= cpus,
 		.fbq_type	= all,
 		.tasks		= LIST_HEAD_INIT(env.tasks),
@@ -9682,7 +9686,8 @@ static int load_balance(int this_cpu, struct rq *this_rq,
 			 * destination group that is receiving any migrated
 			 * load.
 			 */
-			if (!cpumask_subset(cpus, env.dst_grpmask)) {
+			if (!cpumask_subset(cpus, env.dst_grpmask) &&
+					++env.redo_cnt < env.redo_max) {
 				env.loop = 0;
 				env.loop_break = sched_nr_migrate_break;
 				goto redo;
Signature · 1 line
2.7.4
maintainer
#1 lore raw
Quoted 8 lines · Aubrey Li

A long-tail load balance cost is observed on the newly idle path, this is caused by a race window between the first nr_running check of the busiest runqueue and its nr_running recheck in detach_tasks.

Before the busiest runqueue is locked, the tasks on the busiest runqueue could be pulled by other CPUs and nr_running of the busiest runqueu becomes 1, this causes detach_tasks breaks with LBF_ALL_PINNED

We should better detect that when trying to detach task like below

kernel/sched/fair.c +10 -0
@@ -7688,6 +7688,16 @@ static int detach_tasks(struct lb_env *env)
 
        lockdep_assert_held(&env->src_rq->lock);
 
+       /*
+        * Another CPU has emptied this runqueue in the meantime.
+        * Just return and leave the load_balance properly.
+        */
+       if (env->src_rq->nr_running <= 1 && !env->loop) {
+               /* Clear the flag as we will not test any task */
+               env->flags &= ~LBF_ALL_PINNED;
+               return 0;
+       }
+
        if (env->imbalance <= 0)
                return 0;
 
Quoted 62 lines

flag set, and triggers load_balance redo at the same sched_domain level.

In order to find the new busiest sched_group and CPU, load balance will recompute and update the various load statistics, which eventually leads to the long-tail load balance cost.

This patch introduces a variable(sched_nr_lb_redo) to limit load balance redo times, combined with sysctl_sched_nr_migrate, the max load balance cost is reduced from 100+ us to 70+ us, measured on a 4s x86 system with 192 logical CPUs.

Cc Andi Kleen <[email protected]>
Cc Tim Chen <[email protected]>
Cc Srinivas Pandruvada <[email protected]>
Cc Rafael J. Wysocki <[email protected]>
---
 kernel/sched/fair.c | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)
kernel/sched/fair.c +6 -2
index ae7ceba..b59f371 100644
@@ -7407,6 +7407,8 @@ struct lb_env {
        unsigned int            loop;
        unsigned int            loop_break;
        unsigned int            loop_max;
+       unsigned int            redo_cnt;
+       unsigned int            redo_max;
 
        enum fbq_type           fbq_type;
        enum migration_type     migration_type;
@@ -9525,6 +9527,7 @@ static int should_we_balance(struct lb_env *env)
        return group_balance_cpu(sg) == env->dst_cpu;
 }
 
+static const unsigned int sched_nr_lb_redo = 1;
 /*
  * Check this_cpu to ensure it is balanced within domain. Attempt to move
  * tasks if there is an imbalance.
@@ -9547,6 +9550,7 @@ static int load_balance(int this_cpu, struct rq *this_rq,
                .dst_grpmask    = sched_group_span(sd->groups),
                .idle           = idle,
                .loop_break     = sched_nr_migrate_break,
+               .redo_max       = sched_nr_lb_redo,
                .cpus           = cpus,
                .fbq_type       = all,
                .tasks          = LIST_HEAD_INIT(env.tasks),
@@ -9682,7 +9686,8 @@ static int load_balance(int this_cpu, struct rq *this_rq,
                         * destination group that is receiving any migrated
                         * load.
                         */
-                       if (!cpumask_subset(cpus, env.dst_grpmask)) {
+                       if (!cpumask_subset(cpus, env.dst_grpmask) &&
+                                       ++env.redo_cnt < env.redo_max) {
                                env.loop = 0;
                                env.loop_break = sched_nr_migrate_break;
                                goto redo;
--

2.7.4

#2 lore raw
Quoted 11 lines · Vincent Guittot
Quoted 8 lines · Aubrey Li

A long-tail load balance cost is observed on the newly idle path, this is caused by a race window between the first nr_running check of the busiest runqueue and its nr_running recheck in detach_tasks.

Before the busiest runqueue is locked, the tasks on the busiest runqueue could be pulled by other CPUs and nr_running of the busiest runqueu becomes 1, this causes detach_tasks breaks with LBF_ALL_PINNED

We should better detect that when trying to detach task like below

This should be a compromise from my understanding. If we give up load balance this time due to the race condition, we do reduce the load balance cost on the newly idle path, but if there is an imbalance indeed at the same sched_domain level, we have to wait the next softirq entry to handle that imbalance. This means the tasks on the second busiest runqueue have to stay longer, which could introduce tail latency as well. That's why I introduced a variable to control the redo loops. I'll send this to the benchmark queue to see if it makes any difference.

Thanks,
-Aubrey

Quoted 83 lines
kernel/sched/fair.c +10 -0
@@ -7688,6 +7688,16 @@ static int detach_tasks(struct lb_env *env)
 
        lockdep_assert_held(&env->src_rq->lock);
 
+       /*
+        * Another CPU has emptied this runqueue in the meantime.
+        * Just return and leave the load_balance properly.
+        */
+       if (env->src_rq->nr_running <= 1 && !env->loop) {
+               /* Clear the flag as we will not test any task */
+               env->flags &= ~LBF_ALL_PINNED;
+               return 0;
+       }
+
        if (env->imbalance <= 0)
                return 0;
 
Quoted 63 lines

flag set, and triggers load_balance redo at the same sched_domain level.

In order to find the new busiest sched_group and CPU, load balance will recompute and update the various load statistics, which eventually leads to the long-tail load balance cost.

This patch introduces a variable(sched_nr_lb_redo) to limit load balance redo times, combined with sysctl_sched_nr_migrate, the max load balance cost is reduced from 100+ us to 70+ us, measured on a 4s x86 system with 192 logical CPUs.

Cc Andi Kleen <[email protected]>
Cc Tim Chen <[email protected]>
Cc Srinivas Pandruvada <[email protected]>
Cc Rafael J. Wysocki <[email protected]>
---
 kernel/sched/fair.c | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)
kernel/sched/fair.c +6 -2
index ae7ceba..b59f371 100644
@@ -7407,6 +7407,8 @@ struct lb_env {
        unsigned int            loop;
        unsigned int            loop_break;
        unsigned int            loop_max;
+       unsigned int            redo_cnt;
+       unsigned int            redo_max;
 
        enum fbq_type           fbq_type;
        enum migration_type     migration_type;
@@ -9525,6 +9527,7 @@ static int should_we_balance(struct lb_env *env)
        return group_balance_cpu(sg) == env->dst_cpu;
 }
 
+static const unsigned int sched_nr_lb_redo = 1;
 /*
  * Check this_cpu to ensure it is balanced within domain. Attempt to move
  * tasks if there is an imbalance.
@@ -9547,6 +9550,7 @@ static int load_balance(int this_cpu, struct rq *this_rq,
                .dst_grpmask    = sched_group_span(sd->groups),
                .idle           = idle,
                .loop_break     = sched_nr_migrate_break,
+               .redo_max       = sched_nr_lb_redo,
                .cpus           = cpus,
                .fbq_type       = all,
                .tasks          = LIST_HEAD_INIT(env.tasks),
@@ -9682,7 +9686,8 @@ static int load_balance(int this_cpu, struct rq *this_rq,
                         * destination group that is receiving any migrated
                         * load.
                         */
-                       if (!cpumask_subset(cpus, env.dst_grpmask)) {
+                       if (!cpumask_subset(cpus, env.dst_grpmask) &&
+                                       ++env.redo_cnt < env.redo_max) {
                                env.loop = 0;
                                env.loop_break = sched_nr_migrate_break;
                                goto redo;
--

2.7.4

maintainer
#3 lore raw
Quoted 12 lines · Aubrey
Quoted 10 lines · Vincent Guittot
Quoted 8 lines · Aubrey Li

A long-tail load balance cost is observed on the newly idle path, this is caused by a race window between the first nr_running check of the busiest runqueue and its nr_running recheck in detach_tasks.

Before the busiest runqueue is locked, the tasks on the busiest runqueue could be pulled by other CPUs and nr_running of the busiest runqueu becomes 1, this causes detach_tasks breaks with LBF_ALL_PINNED

Quoted 5 lines
Quoted 1 line

We should better detect that when trying to detach task like below

This should be a compromise from my understanding. If we give up load balance this time due to the race condition, we do reduce the load balance cost on the newly idle path, but if there is an imbalance indeed at the same sched_domain

Redo path is there in case, LB has found an imbalance but it can't move some loads from this busiest rq to dest rq because of some cpu affinity. So it tries to fix the imbalance by moving load onto another rq of the group. In your case, the imbalance has disappeared because it has already been pulled by another rq so you don't have to try to find another imbalance. And I would even say you should not in order to let other level to take a chance to spread the load

Quoted 4 lines

level, we have to wait the next softirq entry to handle that imbalance. This means the tasks on the second busiest runqueue have to stay longer, which could introduce tail latency as well. That's why I introduced a variable to control the redo loops. I'll send this to the benchmark queue to see if it makes any

TBH, I don't like multiplying the number of knobs

Quoted 89 lines

difference.

Thanks,
-Aubrey

Quoted 83 lines
kernel/sched/fair.c +10 -0
@@ -7688,6 +7688,16 @@ static int detach_tasks(struct lb_env *env)
 
        lockdep_assert_held(&env->src_rq->lock);
 
+       /*
+        * Another CPU has emptied this runqueue in the meantime.
+        * Just return and leave the load_balance properly.
+        */
+       if (env->src_rq->nr_running <= 1 && !env->loop) {
+               /* Clear the flag as we will not test any task */
+               env->flags &= ~LBF_ALL_PINNED;
+               return 0;
+       }
+
        if (env->imbalance <= 0)
                return 0;
 
Quoted 63 lines

flag set, and triggers load_balance redo at the same sched_domain level.

In order to find the new busiest sched_group and CPU, load balance will recompute and update the various load statistics, which eventually leads to the long-tail load balance cost.

This patch introduces a variable(sched_nr_lb_redo) to limit load balance redo times, combined with sysctl_sched_nr_migrate, the max load balance cost is reduced from 100+ us to 70+ us, measured on a 4s x86 system with 192 logical CPUs.

Cc Andi Kleen <[email protected]>
Cc Tim Chen <[email protected]>
Cc Srinivas Pandruvada <[email protected]>
Cc Rafael J. Wysocki <[email protected]>
---
 kernel/sched/fair.c | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)
kernel/sched/fair.c +6 -2
index ae7ceba..b59f371 100644
@@ -7407,6 +7407,8 @@ struct lb_env {
        unsigned int            loop;
        unsigned int            loop_break;
        unsigned int            loop_max;
+       unsigned int            redo_cnt;
+       unsigned int            redo_max;
 
        enum fbq_type           fbq_type;
        enum migration_type     migration_type;
@@ -9525,6 +9527,7 @@ static int should_we_balance(struct lb_env *env)
        return group_balance_cpu(sg) == env->dst_cpu;
 }
 
+static const unsigned int sched_nr_lb_redo = 1;
 /*
  * Check this_cpu to ensure it is balanced within domain. Attempt to move
  * tasks if there is an imbalance.
@@ -9547,6 +9550,7 @@ static int load_balance(int this_cpu, struct rq *this_rq,
                .dst_grpmask    = sched_group_span(sd->groups),
                .idle           = idle,
                .loop_break     = sched_nr_migrate_break,
+               .redo_max       = sched_nr_lb_redo,
                .cpus           = cpus,
                .fbq_type       = all,
                .tasks          = LIST_HEAD_INIT(env.tasks),
@@ -9682,7 +9686,8 @@ static int load_balance(int this_cpu, struct rq *this_rq,
                         * destination group that is receiving any migrated
                         * load.
                         */
-                       if (!cpumask_subset(cpus, env.dst_grpmask)) {
+                       if (!cpumask_subset(cpus, env.dst_grpmask) &&
+                                       ++env.redo_cnt < env.redo_max) {
                                env.loop = 0;
                                env.loop_break = sched_nr_migrate_break;
                                goto redo;
--

2.7.4

#4 lore raw
Quoted 19 lines · Vincent Guittot
Quoted 12 lines · Aubrey
Quoted 10 lines · Vincent Guittot
Quoted 8 lines · Aubrey Li

A long-tail load balance cost is observed on the newly idle path, this is caused by a race window between the first nr_running check of the busiest runqueue and its nr_running recheck in detach_tasks.

Before the busiest runqueue is locked, the tasks on the busiest runqueue could be pulled by other CPUs and nr_running of the busiest runqueu becomes 1, this causes detach_tasks breaks with LBF_ALL_PINNED

Quoted 5 lines
Quoted 1 line

We should better detect that when trying to detach task like below

This should be a compromise from my understanding. If we give up load balance this time due to the race condition, we do reduce the load balance cost on the newly idle path, but if there is an imbalance indeed at the same sched_domain

Quoted 7 lines

Redo path is there in case, LB has found an imbalance but it can't move some loads from this busiest rq to dest rq because of some cpu affinity. So it tries to fix the imbalance by moving load onto another rq of the group. In your case, the imbalance has disappeared because it has already been pulled by another rq so you don't have to try to find another imbalance. And I would even say you should not in order to let other level to take a chance to spread the load

Here is one simple case I have seen:
1) CPU_a becomes idle and invoke newly idle balance
2) Group_b is found as the busiest group
3) CPU_b_1 is found as the busiest CPU, nr_running = 5
4) detach_tasks check CPU_b_1's run queue again, nr_running = 1, goto redo
5) Group_b is still found as the busiest group
6) This time CPU_b_2 is found as the busiest CPU, nr_running = 3
7) detach_tasks successfully, 2 tasks moved.

If we skipped redo,
- CPU_a exit load balance and remain idle
- tasks stay on CPU_b_2's runqueue, wait for the next load balancing

The two tasks could have been moved to the idle CPU and get executed immediately.

Quoted 8 lines
Quoted 5 lines

level, we have to wait the next softirq entry to handle that imbalance. This means the tasks on the second busiest runqueue have to stay longer, which could introduce tail latency as well. That's why I introduced a variable to control the redo loops. I'll send this to the benchmark queue to see if it makes any

TBH, I don't like multiplying the number of knobs
I see.

Thanks,
-Aubrey

#5 lore raw
In reply to Vincent Guittot

Hi Vincent,

Sorry for the delay, I just returned from Chinese New Year holiday.

Quoted 27 lines · Vincent Guittot
Quoted 12 lines · Aubrey
Quoted 10 lines · Vincent Guittot
Quoted 8 lines · Aubrey Li

A long-tail load balance cost is observed on the newly idle path, this is caused by a race window between the first nr_running check of the busiest runqueue and its nr_running recheck in detach_tasks.

Before the busiest runqueue is locked, the tasks on the busiest runqueue could be pulled by other CPUs and nr_running of the busiest runqueu becomes 1, this causes detach_tasks breaks with LBF_ALL_PINNED

Quoted 5 lines
Quoted 1 line

We should better detect that when trying to detach task like below

This should be a compromise from my understanding. If we give up load balance this time due to the race condition, we do reduce the load balance cost on the newly idle path, but if there is an imbalance indeed at the same sched_domain

Redo path is there in case, LB has found an imbalance but it can't move some loads from this busiest rq to dest rq because of some cpu affinity. So it tries to fix the imbalance by moving load onto another rq of the group. In your case, the imbalance has disappeared because it has already been pulled by another rq so you don't have to try to find another imbalance. And I would even say you should not in order to let other level to take a chance to spread the load

Quoted 6 lines
Quoted 4 lines

level, we have to wait the next softirq entry to handle that imbalance. This means the tasks on the second busiest runqueue have to stay longer, which could introduce tail latency as well. That's why I introduced a variable to control the redo loops. I'll send this to the benchmark queue to see if it makes any

TBH, I don't like multiplying the number of knobs

Sure, I can take your approach, :)

Quoted 5 lines
Quoted 5 lines
Quoted 5 lines
kernel/sched/fair.c +0 -0
@@ -7688,6 +7688,16 @@ static int detach_tasks(struct lb_env *env)
 
Quoted 7 lines
Quoted 7 lines

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

Quoted 7 lines
kernel/sched/fair.c +5 -0
        lockdep_assert_held(&env->src_rq->lock);
 
+       /*
+        * Another CPU has emptied this runqueue in the meantime.
+        * Just return and leave the load_balance properly.
+        */
+       if (env->src_rq->nr_running <= 1 && !env->loop) {

May I know why !env->loop is needed here? IIUC, if detach_tasks is invoked from LBF_NEED_BREAK, env->loop could be non-zero, but as long as src_rq's nr_running <=1, we should return immediately with LBF_ALL_PINNED flag cleared.

How about the following change?

kernel/sched/fair.c +4 -1
index 04a3ce20da67..1761d33accaa 100644
@@ -7683,8 +7683,11 @@ static int detach_tasks(struct lb_env *env)
 		 * We don't want to steal all, otherwise we may be treated likewise,
 		 * which could at worst lead to a livelock crash.
 		 */
-		if (env->idle != CPU_NOT_IDLE && env->src_rq->nr_running <= 1)
+		if (env->idle != CPU_NOT_IDLE && env->src_rq->nr_running <= 1) {
+			/* Clear the flag as we will not test any task */
+			env->flag &= ~LBF_ALL_PINNED;
 			break;
+		}
 
 		p = list_last_entry(tasks, struct task_struct, se.group_node);
 

Thanks,
-Aubrey

maintainer
#6 lore raw
Quoted 49 lines · Aubrey

Hi Vincent,

Sorry for the delay, I just returned from Chinese New Year holiday.

Quoted 27 lines · Vincent Guittot
Quoted 12 lines · Aubrey
Quoted 10 lines · Vincent Guittot
Quoted 8 lines · Aubrey Li

A long-tail load balance cost is observed on the newly idle path, this is caused by a race window between the first nr_running check of the busiest runqueue and its nr_running recheck in detach_tasks.

Before the busiest runqueue is locked, the tasks on the busiest runqueue could be pulled by other CPUs and nr_running of the busiest runqueu becomes 1, this causes detach_tasks breaks with LBF_ALL_PINNED

Quoted 5 lines
Quoted 1 line

We should better detect that when trying to detach task like below

This should be a compromise from my understanding. If we give up load balance this time due to the race condition, we do reduce the load balance cost on the newly idle path, but if there is an imbalance indeed at the same sched_domain

Redo path is there in case, LB has found an imbalance but it can't move some loads from this busiest rq to dest rq because of some cpu affinity. So it tries to fix the imbalance by moving load onto another rq of the group. In your case, the imbalance has disappeared because it has already been pulled by another rq so you don't have to try to find another imbalance. And I would even say you should not in order to let other level to take a chance to spread the load

Quoted 6 lines
Quoted 4 lines

level, we have to wait the next softirq entry to handle that imbalance. This means the tasks on the second busiest runqueue have to stay longer, which could introduce tail latency as well. That's why I introduced a variable to control the redo loops. I'll send this to the benchmark queue to see if it makes any

TBH, I don't like multiplying the number of knobs

Sure, I can take your approach, :)

Quoted 7 lines
Quoted 7 lines
Quoted 7 lines
kernel/sched/fair.c +0 -0
@@ -7688,6 +7688,16 @@ static int detach_tasks(struct lb_env *env)
 
        lockdep_assert_held(&env->src_rq->lock);
 
Quoted 7 lines
Quoted 5 lines
Quoted 5 lines

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

Quoted 5 lines
kernel/sched/fair.c +5 -0
+       /*
+        * Another CPU has emptied this runqueue in the meantime.
+        * Just return and leave the load_balance properly.
+        */
+       if (env->src_rq->nr_running <= 1 && !env->loop) {

May I know why !env->loop is needed here? IIUC, if detach_tasks is invoked

IIRC, my point was to do the test only when trying to detach the 1st task. A lot of things can happen when a break is involved but TBH I can't remember a precise UC. It may be over cautious

Quoted 10 lines

from LBF_NEED_BREAK, env->loop could be non-zero, but as long as src_rq's nr_running <=1, we should return immediately with LBF_ALL_PINNED flag cleared.

How about the following change?

kernel/sched/fair.c +0 -0
index 04a3ce20da67..1761d33accaa 100644

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

Quoted 5 lines
kernel/sched/fair.c +1 -1
@@ -7683,8 +7683,11 @@ static int detach_tasks(struct lb_env *env)
                 * We don't want to steal all, otherwise we may be treated likewise,
                 * which could at worst lead to a livelock crash.
                 */
-               if (env->idle != CPU_NOT_IDLE && env->src_rq->nr_running <= 1)
+               if (env->idle != CPU_NOT_IDLE && env->src_rq->nr_running <= 1) {

IMO, we must do the test before: while (!list_empty(tasks)) {

because src_rq might have become empty if waiting tasks have been pulled by another cpu and the running one became idle in the meantime

Quoted 9 lines
kernel/sched/fair.c +3 -0
+                       /* Clear the flag as we will not test any task */
+                       env->flag &= ~LBF_ALL_PINNED;
                        break;
+               }
 
                p = list_last_entry(tasks, struct task_struct, se.group_node);
 

Thanks,
-Aubrey

#7 lore raw
Quoted 58 lines · Vincent Guittot
Quoted 49 lines · Aubrey

Hi Vincent,

Sorry for the delay, I just returned from Chinese New Year holiday.

Quoted 27 lines · Vincent Guittot
Quoted 12 lines · Aubrey
Quoted 10 lines · Vincent Guittot
Quoted 8 lines · Aubrey Li

A long-tail load balance cost is observed on the newly idle path, this is caused by a race window between the first nr_running check of the busiest runqueue and its nr_running recheck in detach_tasks.

Before the busiest runqueue is locked, the tasks on the busiest runqueue could be pulled by other CPUs and nr_running of the busiest runqueu becomes 1, this causes detach_tasks breaks with LBF_ALL_PINNED

Quoted 5 lines
Quoted 1 line

We should better detect that when trying to detach task like below

This should be a compromise from my understanding. If we give up load balance this time due to the race condition, we do reduce the load balance cost on the newly idle path, but if there is an imbalance indeed at the same sched_domain

Redo path is there in case, LB has found an imbalance but it can't move some loads from this busiest rq to dest rq because of some cpu affinity. So it tries to fix the imbalance by moving load onto another rq of the group. In your case, the imbalance has disappeared because it has already been pulled by another rq so you don't have to try to find another imbalance. And I would even say you should not in order to let other level to take a chance to spread the load

Quoted 6 lines
Quoted 4 lines

level, we have to wait the next softirq entry to handle that imbalance. This means the tasks on the second busiest runqueue have to stay longer, which could introduce tail latency as well. That's why I introduced a variable to control the redo loops. I'll send this to the benchmark queue to see if it makes any

TBH, I don't like multiplying the number of knobs

Sure, I can take your approach, :)

Quoted 7 lines
Quoted 7 lines
Quoted 7 lines
kernel/sched/fair.c +0 -0
@@ -7688,6 +7688,16 @@ static int detach_tasks(struct lb_env *env)
 
        lockdep_assert_held(&env->src_rq->lock);
 
Quoted 7 lines
Quoted 5 lines
Quoted 5 lines

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

Quoted 5 lines
kernel/sched/fair.c +5 -0
+       /*
+        * Another CPU has emptied this runqueue in the meantime.
+        * Just return and leave the load_balance properly.
+        */
+       if (env->src_rq->nr_running <= 1 && !env->loop) {

May I know why !env->loop is needed here? IIUC, if detach_tasks is invoked

Quoted 3 lines

IIRC, my point was to do the test only when trying to detach the 1st task. A lot of things can happen when a break is involved but TBH I can't remember a precise UC. It may be over cautious

When the break happens, rq unlock and local irq restored, so it's still possible the rq is emptied by another CPU.

Quoted 19 lines
Quoted 11 lines

from LBF_NEED_BREAK, env->loop could be non-zero, but as long as src_rq's nr_running <=1, we should return immediately with LBF_ALL_PINNED flag cleared.

How about the following change?

kernel/sched/fair.c +0 -0
index 04a3ce20da67..1761d33accaa 100644

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

Quoted 5 lines
kernel/sched/fair.c +1 -1
@@ -7683,8 +7683,11 @@ static int detach_tasks(struct lb_env *env)
                 * We don't want to steal all, otherwise we may be treated likewise,
                 * which could at worst lead to a livelock crash.
                 */
-               if (env->idle != CPU_NOT_IDLE && env->src_rq->nr_running <= 1)
+               if (env->idle != CPU_NOT_IDLE && env->src_rq->nr_running <= 1) {

IMO, we must do the test before: while (!list_empty(tasks)) {

Quoted 2 lines

because src_rq might have become empty if waiting tasks have been pulled by another cpu and the running one became idle in the meantime

Okay, after the running one became idle, it still has LBF_ALL_PINNED, which needs to be cleared as well. Thanks!

Quoted 10 lines
Quoted 10 lines
kernel/sched/fair.c +3 -0
+                       /* Clear the flag as we will not test any task */
+                       env->flag &= ~LBF_ALL_PINNED;
                        break;
+               }
 
                p = list_last_entry(tasks, struct task_struct, se.group_node);
 

Thanks,
-Aubrey

#8 lore raw
In reply to Aubrey Li
Quoted 18 lines · Aubrey Li

A long-tail load balance cost is observed on the newly idle path, this is caused by a race window between the first nr_running check of the busiest runqueue and its nr_running recheck in detach_tasks.

Before the busiest runqueue is locked, the tasks on the busiest runqueue could be pulled by other CPUs and nr_running of the busiest runqueu becomes 1, this causes detach_tasks breaks with LBF_ALL_PINNED flag set, and triggers load_balance redo at the same sched_domain level.

In order to find the new busiest sched_group and CPU, load balance will recompute and update the various load statistics, which eventually leads to the long-tail load balance cost.

This patch introduces a variable(sched_nr_lb_redo) to limit load balance redo times, combined with sysctl_sched_nr_migrate, the max load balance cost is reduced from 100+ us to 70+ us, measured on a 4s x86 system with 192 logical CPUs.

Quoted 5 lines
Cc Andi Kleen <[email protected]>
Cc Tim Chen <[email protected]>
Cc Srinivas Pandruvada <[email protected]>
Cc Rafael J. Wysocki <[email protected]>

If redo_max is a constant, why is it not a #define instead of increasing the size of lb_env?

Signature · 2 lines
Mel Gorman
SUSE Labs
#9 lore raw
Quoted 19 lines · Mel Gorman
Quoted 18 lines · Aubrey Li

A long-tail load balance cost is observed on the newly idle path, this is caused by a race window between the first nr_running check of the busiest runqueue and its nr_running recheck in detach_tasks.

Before the busiest runqueue is locked, the tasks on the busiest runqueue could be pulled by other CPUs and nr_running of the busiest runqueu becomes 1, this causes detach_tasks breaks with LBF_ALL_PINNED flag set, and triggers load_balance redo at the same sched_domain level.

In order to find the new busiest sched_group and CPU, load balance will recompute and update the various load statistics, which eventually leads to the long-tail load balance cost.

This patch introduces a variable(sched_nr_lb_redo) to limit load balance redo times, combined with sysctl_sched_nr_migrate, the max load balance cost is reduced from 100+ us to 70+ us, measured on a 4s x86 system with 192 logical CPUs.

Quoted 9 lines
Quoted 5 lines
Cc Andi Kleen <[email protected]>
Cc Tim Chen <[email protected]>
Cc Srinivas Pandruvada <[email protected]>
Cc Rafael J. Wysocki <[email protected]>

If redo_max is a constant, why is it not a #define instead of increasing the size of lb_env?

I followed the existing variable sched_nr_migrate_break, I think this might be a tunable as well.

Thanks,
-Aubrey

#10 lore raw
Quoted 26 lines · Aubrey
Quoted 25 lines · Mel Gorman
Quoted 23 lines · Aubrey Li

A long-tail load balance cost is observed on the newly idle path, this is caused by a race window between the first nr_running check of the busiest runqueue and its nr_running recheck in detach_tasks.

Before the busiest runqueue is locked, the tasks on the busiest runqueue could be pulled by other CPUs and nr_running of the busiest runqueu becomes 1, this causes detach_tasks breaks with LBF_ALL_PINNED flag set, and triggers load_balance redo at the same sched_domain level.

In order to find the new busiest sched_group and CPU, load balance will recompute and update the various load statistics, which eventually leads to the long-tail load balance cost.

This patch introduces a variable(sched_nr_lb_redo) to limit load balance redo times, combined with sysctl_sched_nr_migrate, the max load balance cost is reduced from 100+ us to 70+ us, measured on a 4s x86 system with 192 logical CPUs.

Cc Andi Kleen <[email protected]>
Cc Tim Chen <[email protected]>
Cc Srinivas Pandruvada <[email protected]>
Cc Rafael J. Wysocki <[email protected]>
Quoted 7 lines
Quoted 3 lines

If redo_max is a constant, why is it not a #define instead of increasing the size of lb_env?

I followed the existing variable sched_nr_migrate_break, I think this might be a tunable as well.

I don't think it is, the tunable is sched_nr_migrate and it's not clear to me at all why sched_nr_migrate_break is not also a #define. It just happens that sched_nr_migrate == sched_nr_migrate_break by default.

Signature · 2 lines
Mel Gorman
SUSE Labs