Skip to contentSkip to conversation

sched: Improve load balancing in the presence of idle CPUs

PATCH Jason Low 5 participants 30 messages Mar 30, 2015 – Apr 14, 2015 Scheduler

lore
Share & tools
lore

Jason Low

author
#0 lore raw

Hi Preeti,

I noticed that another commit 4a725627f21d converted the check in nohz_kick_needed() from idle_cpu() to rq->idle_balance, causing a potentially outdated value to be used if this cpu is able to pull tasks using rebalance_domains(), and nohz_kick_needed() directly returning false.

Would this patch also help address some of the issue you are seeing?

---
 kernel/sched/fair.c |    4 ++--
 1 files changed, 2 insertions(+), 2 deletions(-)
kernel/sched/fair.c +2 -2
index fdae26e..ba8ec1a 100644
@@ -7644,7 +7644,7 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 		 * balancing owner will pick it up.
 		 */
 		if (need_resched())
-			break;
+			goto end;
 
 		rq = cpu_rq(balance_cpu);
 
@@ -7687,7 +7687,7 @@ static inline bool nohz_kick_needed(struct rq *rq)
 	int nr_busy, cpu = rq->cpu;
 	bool kick = false;
 
-	if (unlikely(rq->idle_balance))
+	if (unlikely(idle_cpu(cpu)))
 		return false;
 
        /*
Signature · 1 line
1.7.2.5
#1 lore raw

Hi Jason,

Quoted 7 lines · Jason Low

Hi Preeti,

I noticed that another commit 4a725627f21d converted the check in nohz_kick_needed() from idle_cpu() to rq->idle_balance, causing a potentially outdated value to be used if this cpu is able to pull tasks using rebalance_domains(), and nohz_kick_needed() directly returning false.

I see that rebalance_domains() will be run at the end of the scheduler tick interrupt handling. trigger_load_balance() only sets the softirq, it does not call rebalance_domains() immediately. So the call graph would be:

rq->idle_balance = idle_cpu()
|____trigger_load_balance()
|_____raise SCHED_SOFTIRQ - we are handling interrupt,hence defer
|____nohz_kick_needed()
|____rebalance_domains() run through the softirqd.

Correct me if I am wrong but since we do not pull any load between the rq->idle_balance update and nohz_kick_needed(), we are safe in reading rq->idle_balance in nohz_kick_needed().

Quoted 13 lines

Would this patch also help address some of the issue you are seeing?

---
 kernel/sched/fair.c |    4 ++--
 1 files changed, 2 insertions(+), 2 deletions(-)
kernel/sched/fair.c +0 -0
index fdae26e..ba8ec1a 100644

kernel/sched/fair.c static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle) · line 7647

Quoted 5 lines
kernel/sched/fair.c +1 -1
@@ -7644,7 +7644,7 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 		 * balancing owner will pick it up.
 		 */
 		if (need_resched())
-			break;
+			goto end;

Why is this hunk needed?

Regards
Preeti U Murthy

Quoted 13 lines
kernel/sched/fair.c +1 -1
 		rq = cpu_rq(balance_cpu);
 
@@ -7687,7 +7687,7 @@ static inline bool nohz_kick_needed(struct rq *rq)
 	int nr_busy, cpu = rq->cpu;
 	bool kick = false;
 
-	if (unlikely(rq->idle_balance))
+	if (unlikely(idle_cpu(cpu)))
 		return false;
 
        /*
author
#2 lore raw
Quoted 11 lines · Preeti U Murthy

Hi Jason,

Quoted 7 lines · Jason Low

Hi Preeti,

I noticed that another commit 4a725627f21d converted the check in nohz_kick_needed() from idle_cpu() to rq->idle_balance, causing a potentially outdated value to be used if this cpu is able to pull tasks using rebalance_domains(), and nohz_kick_needed() directly returning false.

Quoted 4 lines

I see that rebalance_domains() will be run at the end of the scheduler tick interrupt handling. trigger_load_balance() only sets the softirq, it does not call rebalance_domains() immediately. So the call graph would be:

Oh right, since that only sets the softirq, this wouldn't be the issue, though we would need these changes if we were to incorporate any sort of nohz_kick_needed() logic into the nohz_idle_balance() code path correct?

#3 lore raw
Quoted 12 lines · Jason Low
Quoted 11 lines · Preeti U Murthy

Hi Jason,

Quoted 7 lines · Jason Low

Hi Preeti,

I noticed that another commit 4a725627f21d converted the check in nohz_kick_needed() from idle_cpu() to rq->idle_balance, causing a potentially outdated value to be used if this cpu is able to pull tasks using rebalance_domains(), and nohz_kick_needed() directly returning false.

Quoted 8 lines
Quoted 4 lines

I see that rebalance_domains() will be run at the end of the scheduler tick interrupt handling. trigger_load_balance() only sets the softirq, it does not call rebalance_domains() immediately. So the call graph would be:

Oh right, since that only sets the softirq, this wouldn't be the issue, though we would need these changes if we were to incorporate any sort of nohz_kick_needed() logic into the nohz_idle_balance() code path correct?

I am sorry I don't quite get this. Can you please elaborate?

Regards
Preeti U Murthy

Quoted 1 line
#4 lore raw
Quoted 19 lines · Preeti U Murthy
Quoted 17 lines · Jason Low
Quoted 15 lines · Preeti U Murthy

Hi Jason,

Quoted 7 lines · Jason Low

Hi Preeti,

I noticed that another commit 4a725627f21d converted the check in nohz_kick_needed() from idle_cpu() to rq->idle_balance, causing a potentially outdated value to be used if this cpu is able to pull tasks using rebalance_domains(), and nohz_kick_needed() directly returning false.

I see that rebalance_domains() will be run at the end of the scheduler tick interrupt handling. trigger_load_balance() only sets the softirq, it does not call rebalance_domains() immediately. So the call graph would be:

Quoted 5 lines
Quoted 3 lines

Oh right, since that only sets the softirq, this wouldn't be the issue, though we would need these changes if we were to incorporate any sort of nohz_kick_needed() logic into the nohz_idle_balance() code path correct?

I am sorry I don't quite get this. Can you please elaborate?

I think the scenario is that we are in nohz_idle_balance() and decide to bail out because we have pulled some tasks, but before leaving nohz_idle_balance() we want to check if more balancing is necessary using nohz_kick_needed() and potentially kick somebody to continue.

Note that the balance cpu is currently skipped in nohz_idle_balance(), but if it wasn't the scenario would be possible.

In that case, we can't rely on rq->idle_balance as it would not be up-to-date. Also, we may even want to use nohz_kick_needed(rq) where rq != this_rq, in which case we probably also want an updated status. It seems that rq->idle_balance is only updated at each tick.

Or maybe I'm all wrong :)

author
#29 lore raw
In reply to Preeti U Murthy
Quoted 14 lines · Preeti U Murthy

kernel/sched/fair.c static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle) · line 7647

Quoted 10 lines · Jason Low
kernel/sched/fair.c +1 -1
index fdae26e..ba8ec1a 100644
@@ -7644,7 +7644,7 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 		 * balancing owner will pick it up.
 		 */
 		if (need_resched())
-			break;
+			goto end;

Why is this hunk needed?

In terms of the change in the need_resched() case, if the current CPU doesn't complete iterating all of the CPUs, then this will make it not update nohz.next_balance. This is so we can continue the balancing with the next balancing owner without too much delay.

author
#5 lore raw
In reply to Morten Rasmussen
Quoted 26 lines · Morten Rasmussen
Quoted 19 lines · Preeti U Murthy
Quoted 17 lines · Jason Low
Quoted 15 lines · Preeti U Murthy

Hi Jason,

Quoted 7 lines · Jason Low

Hi Preeti,

I noticed that another commit 4a725627f21d converted the check in nohz_kick_needed() from idle_cpu() to rq->idle_balance, causing a potentially outdated value to be used if this cpu is able to pull tasks using rebalance_domains(), and nohz_kick_needed() directly returning false.

I see that rebalance_domains() will be run at the end of the scheduler tick interrupt handling. trigger_load_balance() only sets the softirq, it does not call rebalance_domains() immediately. So the call graph would be:

Quoted 5 lines
Quoted 3 lines

Oh right, since that only sets the softirq, this wouldn't be the issue, though we would need these changes if we were to incorporate any sort of nohz_kick_needed() logic into the nohz_idle_balance() code path correct?

I am sorry I don't quite get this. Can you please elaborate?

Quoted 7 lines

I think the scenario is that we are in nohz_idle_balance() and decide to bail out because we have pulled some tasks, but before leaving nohz_idle_balance() we want to check if more balancing is necessary using nohz_kick_needed() and potentially kick somebody to continue.

Note that the balance cpu is currently skipped in nohz_idle_balance(), but if it wasn't the scenario would be possible.

This scenario would also be possible if we call rebalance_domains() first again.

I'm wondering if adding the nohz_kick_needed(), ect... in nohz_idle_balance() can address the 10 second latency issue while still calling rebalance_domains() first, since it seems more ideal to try balancing on the current awake CPU first, as you also have mentioned

Quoted 4 lines

In that case, we can't rely on rq->idle_balance as it would not be up-to-date. Also, we may even want to use nohz_kick_needed(rq) where rq != this_rq, in which case we probably also want an updated status. It seems that rq->idle_balance is only updated at each tick.

Yup, that's about what I was describing.

author
#7 lore raw
In reply to Morten Rasmussen
Quoted 8 lines · Morten Rasmussen
Quoted 1 line · Preeti U Murthy

I am sorry I don't quite get this. Can you please elaborate?

I think the scenario is that we are in nohz_idle_balance() and decide to bail out because we have pulled some tasks, but before leaving nohz_idle_balance() we want to check if more balancing is necessary using nohz_kick_needed() and potentially kick somebody to continue.

Also, below is an example patch.

(Without the conversion to idle_cpu(), the check for rq->idle_balance would not be accurate anymore)

---
 kernel/sched/fair.c |   17 ++++++++++-------
 1 files changed, 10 insertions(+), 7 deletions(-)
kernel/sched/fair.c +10 -7
index fdae26e..7749a14 100644
@@ -7620,6 +7620,8 @@ out:
 }
 
 #ifdef CONFIG_NO_HZ_COMMON
+static inline bool nohz_kick_needed(struct rq *rq);
+
 /*
  * In CONFIG_NO_HZ_COMMON case, the idle balance kickee will do the
  * rebalancing for all the cpus for whom scheduler ticks are stopped.
@@ -7629,6 +7631,7 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 	int this_cpu = this_rq->cpu;
 	struct rq *rq;
 	int balance_cpu;
+	bool done_balancing = false;
 
 	if (idle != CPU_IDLE ||
 	    !test_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu)))
@@ -7644,7 +7647,7 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 		 * balancing owner will pick it up.
 		 */
 		if (need_resched())
-			break;
+			goto end;
 
 		rq = cpu_rq(balance_cpu);
 
@@ -7663,9 +7666,12 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 		if (time_after(this_rq->next_balance, rq->next_balance))
 			this_rq->next_balance = rq->next_balance;
 	}
+	done_balancing = true;
 	nohz.next_balance = this_rq->next_balance;
 end:
 	clear_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu));
+	if (!done_balancing && nohz_kick_needed(this_rq))
+		nohz_balancer_kick();
 }
 
 /*
@@ -7687,7 +7693,7 @@ static inline bool nohz_kick_needed(struct rq *rq)
 	int nr_busy, cpu = rq->cpu;
 	bool kick = false;
 
-	if (unlikely(rq->idle_balance))
+	if (unlikely(idle_cpu(cpu)))
 		return false;
 
        /*
@@ -7757,16 +7763,13 @@ static void run_rebalance_domains(struct softirq_action *h)
 	enum cpu_idle_type idle = this_rq->idle_balance ?
 						CPU_IDLE : CPU_NOT_IDLE;
 
+	rebalance_domains(this_rq, idle);
 	/*
 	 * If this cpu has a pending nohz_balance_kick, then do the
 	 * balancing on behalf of the other idle cpus whose ticks are
-	 * stopped. Do nohz_idle_balance *before* rebalance_domains to
-	 * give the idle cpus a chance to load balance. Else we may
-	 * load balance only within the local sched_domain hierarchy
-	 * and abort nohz_idle_balance altogether if we pull some load.
+	 * stopped.
 	 */
 	nohz_idle_balance(this_rq, idle);
-	rebalance_domains(this_rq, idle);
 }
 
 /*
Signature · 1 line
1.7.2.5
#8 lore raw
Quoted 78 lines · Jason Low
Quoted 8 lines · Morten Rasmussen
Quoted 1 line · Preeti U Murthy

I am sorry I don't quite get this. Can you please elaborate?

I think the scenario is that we are in nohz_idle_balance() and decide to bail out because we have pulled some tasks, but before leaving nohz_idle_balance() we want to check if more balancing is necessary using nohz_kick_needed() and potentially kick somebody to continue.

Also, below is an example patch.

(Without the conversion to idle_cpu(), the check for rq->idle_balance would not be accurate anymore)

---
 kernel/sched/fair.c |   17 ++++++++++-------
 1 files changed, 10 insertions(+), 7 deletions(-)
kernel/sched/fair.c +9 -2
index fdae26e..7749a14 100644
@@ -7620,6 +7620,8 @@ out:
 }
 
 #ifdef CONFIG_NO_HZ_COMMON
+static inline bool nohz_kick_needed(struct rq *rq);
+
 /*
  * In CONFIG_NO_HZ_COMMON case, the idle balance kickee will do the
  * rebalancing for all the cpus for whom scheduler ticks are stopped.
@@ -7629,6 +7631,7 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 	int this_cpu = this_rq->cpu;
 	struct rq *rq;
 	int balance_cpu;
+	bool done_balancing = false;
 
 	if (idle != CPU_IDLE ||
 	    !test_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu)))
@@ -7644,7 +7647,7 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 		 * balancing owner will pick it up.
 		 */
 		if (need_resched())
-			break;
+			goto end;
 
 		rq = cpu_rq(balance_cpu);
 
@@ -7663,9 +7666,12 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 		if (time_after(this_rq->next_balance, rq->next_balance))
 			this_rq->next_balance = rq->next_balance;
 	}
+	done_balancing = true;
 	nohz.next_balance = this_rq->next_balance;
 end:
 	clear_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu));
+	if (!done_balancing && nohz_kick_needed(this_rq))
+		nohz_balancer_kick();
 }
 
 /*
@@ -7687,7 +7693,7 @@ static inline bool nohz_kick_needed(struct rq *rq)
 	int nr_busy, cpu = rq->cpu;
 	bool kick = false;
 
-	if (unlikely(rq->idle_balance))
+	if (unlikely(idle_cpu(cpu)))
 		return false;
 
        /*
@@ -7757,16 +7763,13 @@ static void run_rebalance_domains(struct softirq_action *h)
 	enum cpu_idle_type idle = this_rq->idle_balance ?
 						CPU_IDLE : CPU_NOT_IDLE;
 
+	rebalance_domains(this_rq, idle);
 	/*
 	 * If this cpu has a pending nohz_balance_kick, then do the

kernel/sched/fair.c static void run_rebalance_domains(struct softirq_action *h) · line 7773

Quoted 10 lines
kernel/sched/fair.c +1 -5
 	 * balancing on behalf of the other idle cpus whose ticks are
-	 * stopped. Do nohz_idle_balance *before* rebalance_domains to
-	 * give the idle cpus a chance to load balance. Else we may
-	 * load balance only within the local sched_domain hierarchy
-	 * and abort nohz_idle_balance altogether if we pull some load.
+	 * stopped.
 	 */
 	nohz_idle_balance(this_rq, idle);
-	rebalance_domains(this_rq, idle);
 }

Ok this patch looks good. Let me test to find out if scheduling behavior improves.

Regards
Preeti U Murthy

Quoted 3 lines
kernel/sched/fair.c +0 -0
 /*
 
#6 lore raw
In reply to Jason Low
Quoted 32 lines · Jason Low
Quoted 30 lines · Morten Rasmussen
Quoted 19 lines · Preeti U Murthy
Quoted 17 lines · Jason Low
Quoted 15 lines · Preeti U Murthy

Hi Jason,

Quoted 7 lines · Jason Low

Hi Preeti,

I noticed that another commit 4a725627f21d converted the check in nohz_kick_needed() from idle_cpu() to rq->idle_balance, causing a potentially outdated value to be used if this cpu is able to pull tasks using rebalance_domains(), and nohz_kick_needed() directly returning false.

I see that rebalance_domains() will be run at the end of the scheduler tick interrupt handling. trigger_load_balance() only sets the softirq, it does not call rebalance_domains() immediately. So the call graph would be:

Quoted 5 lines
Quoted 3 lines

Oh right, since that only sets the softirq, this wouldn't be the issue, though we would need these changes if we were to incorporate any sort of nohz_kick_needed() logic into the nohz_idle_balance() code path correct?

I am sorry I don't quite get this. Can you please elaborate?

I think the scenario is that we are in nohz_idle_balance() and decide to bail out because we have pulled some tasks, but before leaving nohz_idle_balance() we want to check if more balancing is necessary using nohz_kick_needed() and potentially kick somebody to continue.

Quoted 5 lines
Quoted 2 lines

Note that the balance cpu is currently skipped in nohz_idle_balance(), but if it wasn't the scenario would be possible.

This scenario would also be possible if we call rebalance_domains() first again.

Yes.

Quoted 4 lines

I'm wondering if adding the nohz_kick_needed(), ect... in nohz_idle_balance() can address the 10 second latency issue while still calling rebalance_domains() first, since it seems more ideal to try balancing on the current awake CPU first, as you also have mentioned

I believe it could. That is where I was going with the chain-of-kicks idea. I think the main cause of the unacceptable you are observing is due to nohz_kicks only being issued at the tick. So if the balancer pulls for itself first and bails out the next kick won't be issued until the next tick or even multiple ticks later depending on nohz.next_balance.

I haven't figured out if there is a reason for delaying the next nohz_idle_balance() though.

#9 lore raw
In reply to Jason Low
Quoted 78 lines · Jason Low
Quoted 8 lines · Morten Rasmussen
Quoted 1 line · Preeti U Murthy

I am sorry I don't quite get this. Can you please elaborate?

I think the scenario is that we are in nohz_idle_balance() and decide to bail out because we have pulled some tasks, but before leaving nohz_idle_balance() we want to check if more balancing is necessary using nohz_kick_needed() and potentially kick somebody to continue.

Also, below is an example patch.

(Without the conversion to idle_cpu(), the check for rq->idle_balance would not be accurate anymore)

---
 kernel/sched/fair.c |   17 ++++++++++-------
 1 files changed, 10 insertions(+), 7 deletions(-)
kernel/sched/fair.c +9 -2
index fdae26e..7749a14 100644
@@ -7620,6 +7620,8 @@ out:
 }
 
 #ifdef CONFIG_NO_HZ_COMMON
+static inline bool nohz_kick_needed(struct rq *rq);
+
 /*
  * In CONFIG_NO_HZ_COMMON case, the idle balance kickee will do the
  * rebalancing for all the cpus for whom scheduler ticks are stopped.
@@ -7629,6 +7631,7 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 	int this_cpu = this_rq->cpu;
 	struct rq *rq;
 	int balance_cpu;
+	bool done_balancing = false;
 
 	if (idle != CPU_IDLE ||
 	    !test_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu)))
@@ -7644,7 +7647,7 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 		 * balancing owner will pick it up.
 		 */
 		if (need_resched())
-			break;
+			goto end;
 
 		rq = cpu_rq(balance_cpu);
 
@@ -7663,9 +7666,12 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 		if (time_after(this_rq->next_balance, rq->next_balance))
 			this_rq->next_balance = rq->next_balance;
 	}
+	done_balancing = true;
 	nohz.next_balance = this_rq->next_balance;
 end:
 	clear_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu));
+	if (!done_balancing && nohz_kick_needed(this_rq))
+		nohz_balancer_kick();
 }
 
 /*
@@ -7687,7 +7693,7 @@ static inline bool nohz_kick_needed(struct rq *rq)
 	int nr_busy, cpu = rq->cpu;
 	bool kick = false;
 
-	if (unlikely(rq->idle_balance))
+	if (unlikely(idle_cpu(cpu)))
 		return false;
 
        /*
@@ -7757,16 +7763,13 @@ static void run_rebalance_domains(struct softirq_action *h)
 	enum cpu_idle_type idle = this_rq->idle_balance ?
 						CPU_IDLE : CPU_NOT_IDLE;
 
+	rebalance_domains(this_rq, idle);
 	/*
 	 * If this cpu has a pending nohz_balance_kick, then do the

kernel/sched/fair.c static void run_rebalance_domains(struct softirq_action *h) · line 7773

Quoted 10 lines
kernel/sched/fair.c +1 -5
 	 * balancing on behalf of the other idle cpus whose ticks are
-	 * stopped. Do nohz_idle_balance *before* rebalance_domains to
-	 * give the idle cpus a chance to load balance. Else we may
-	 * load balance only within the local sched_domain hierarchy
-	 * and abort nohz_idle_balance altogether if we pull some load.
+	 * stopped.
 	 */
 	nohz_idle_balance(this_rq, idle);
-	rebalance_domains(this_rq, idle);
 }

I think this should reduce the latency Preeti is seeing and avoid unnecessary wake-ups, however, it may not be quite as aggressive in spreading tasks quickly. It will stop the chain-of-kicks as soon as the balancer cpu has pulled only one task. The source cpu may still be having two tasks and other cpus may still have more than two tasks running.

Depending on how bad it is, we could consider kicking another cpu if the imbalance is still significant after the balancer cpu has pulled a task.

author
#10 lore raw
Quoted 7 lines · Morten Rasmussen
Quoted 4 lines · Jason Low

Also, below is an example patch.

(Without the conversion to idle_cpu(), the check for rq->idle_balance would not be accurate anymore)

Quoted 6 lines

I think this should reduce the latency Preeti is seeing and avoid unnecessary wake-ups, however, it may not be quite as aggressive in spreading tasks quickly. It will stop the chain-of-kicks as soon as the balancer cpu has pulled only one task. The source cpu may still be having two tasks and other cpus may still have more than two tasks running.

Yeah, good point. I'll wait and see if Preeti finds this to improve scheduling behavior. If this only helps a little though, we can also try to make it more aggressive in spreading tasks.

Quoted 2 lines

Depending on how bad it is, we could consider kicking another cpu if the imbalance is still significant after the balancer cpu has pulled a task.

#11 lore raw
In reply to Jason Low
Quoted 52 lines · Jason Low
Quoted 8 lines · Morten Rasmussen
Quoted 1 line · Preeti U Murthy

I am sorry I don't quite get this. Can you please elaborate?

I think the scenario is that we are in nohz_idle_balance() and decide to bail out because we have pulled some tasks, but before leaving nohz_idle_balance() we want to check if more balancing is necessary using nohz_kick_needed() and potentially kick somebody to continue.

Also, below is an example patch.

(Without the conversion to idle_cpu(), the check for rq->idle_balance would not be accurate anymore)

---
 kernel/sched/fair.c |   17 ++++++++++-------
 1 files changed, 10 insertions(+), 7 deletions(-)
kernel/sched/fair.c +4 -1
index fdae26e..7749a14 100644
@@ -7620,6 +7620,8 @@ out:
 }
 
 #ifdef CONFIG_NO_HZ_COMMON
+static inline bool nohz_kick_needed(struct rq *rq);
+
 /*
  * In CONFIG_NO_HZ_COMMON case, the idle balance kickee will do the
  * rebalancing for all the cpus for whom scheduler ticks are stopped.
@@ -7629,6 +7631,7 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 	int this_cpu = this_rq->cpu;
 	struct rq *rq;
 	int balance_cpu;
+	bool done_balancing = false;
 
 	if (idle != CPU_IDLE ||
 	    !test_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu)))
@@ -7644,7 +7647,7 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 		 * balancing owner will pick it up.
 		 */
 		if (need_resched())
-			break;
+			goto end;
 
 		rq = cpu_rq(balance_cpu);
 
@@ -7663,9 +7666,12 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 		if (time_after(this_rq->next_balance, rq->next_balance))
 			this_rq->next_balance = rq->next_balance;

kernel/sched/fair.c static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle) · line 7677

Quoted 10 lines
kernel/sched/fair.c +3 -0
 	}
+	done_balancing = true;
 	nohz.next_balance = this_rq->next_balance;
 end:
 	clear_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu));
+	if (!done_balancing && nohz_kick_needed(this_rq))
+		nohz_balancer_kick();
 }
 
 

I think we can get rid of the done_balancing boolean and make it a bit easier to read if we change the above code to

kernel/sched/fair.c +7 -2
index bcfe320..08317dc 100644
@@ -7557,8 +7557,13 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
                 * work being done for other cpus. Next load
                 * balancing owner will pick it up.
                 */
-               if (need_resched())
-                       break;
+               if (need_resched()) {
+                       /* preparing to bail, kicking other cpu to continue */
+                       clear_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu));
+                       if (nohz_kick_needed(this_rq))
+                               nohz_balance_kick();
+                       return;
+               }
 
                rq = cpu_rq(balance_cpu);
 

Thanks.

Tim

#15 lore raw
In reply to Jason Low
Quoted 81 lines · Jason Low
Quoted 8 lines · Morten Rasmussen
Quoted 1 line · Preeti U Murthy

I am sorry I don't quite get this. Can you please elaborate?

I think the scenario is that we are in nohz_idle_balance() and decide to bail out because we have pulled some tasks, but before leaving nohz_idle_balance() we want to check if more balancing is necessary using nohz_kick_needed() and potentially kick somebody to continue.

Also, below is an example patch.

(Without the conversion to idle_cpu(), the check for rq->idle_balance would not be accurate anymore)

---
 kernel/sched/fair.c |   17 ++++++++++-------
 1 files changed, 10 insertions(+), 7 deletions(-)
kernel/sched/fair.c +9 -3
index fdae26e..7749a14 100644
@@ -7620,6 +7620,8 @@ out:
 }
 
 #ifdef CONFIG_NO_HZ_COMMON
+static inline bool nohz_kick_needed(struct rq *rq);
+
 /*
  * In CONFIG_NO_HZ_COMMON case, the idle balance kickee will do the
  * rebalancing for all the cpus for whom scheduler ticks are stopped.
@@ -7629,6 +7631,7 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 	int this_cpu = this_rq->cpu;
 	struct rq *rq;
 	int balance_cpu;
+	bool done_balancing = false;
 
 	if (idle != CPU_IDLE ||
 	    !test_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu)))
@@ -7644,7 +7647,7 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 		 * balancing owner will pick it up.
 		 */
 		if (need_resched())
-			break;
+			goto end;
 
 		rq = cpu_rq(balance_cpu);
 
@@ -7663,9 +7666,12 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 		if (time_after(this_rq->next_balance, rq->next_balance))
 			this_rq->next_balance = rq->next_balance;
 	}
+	done_balancing = true;
 	nohz.next_balance = this_rq->next_balance;
 end:
 	clear_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu));
+	if (!done_balancing && nohz_kick_needed(this_rq))
+		nohz_balancer_kick();
 }
 
 /*
@@ -7687,7 +7693,7 @@ static inline bool nohz_kick_needed(struct rq *rq)
 	int nr_busy, cpu = rq->cpu;
 	bool kick = false;
 
-	if (unlikely(rq->idle_balance))
+	if (unlikely(idle_cpu(cpu)))
 		return false;
 
        /*
@@ -7757,16 +7763,13 @@ static void run_rebalance_domains(struct softirq_action *h)
 	enum cpu_idle_type idle = this_rq->idle_balance ?
 						CPU_IDLE : CPU_NOT_IDLE;
 
+	rebalance_domains(this_rq, idle);
 	/*
 	 * If this cpu has a pending nohz_balance_kick, then do the
 	 * balancing on behalf of the other idle cpus whose ticks are
-	 * stopped. Do nohz_idle_balance *before* rebalance_domains to

kernel/sched/fair.c static void run_rebalance_domains(struct softirq_action *h) · line 7775

Quoted 10 lines
kernel/sched/fair.c +1 -4
-	 * give the idle cpus a chance to load balance. Else we may
-	 * load balance only within the local sched_domain hierarchy
-	 * and abort nohz_idle_balance altogether if we pull some load.
+	 * stopped.
 	 */
 	nohz_idle_balance(this_rq, idle);
-	rebalance_domains(this_rq, idle);
 }
 
 /*

Solution 1: As exists in the mainline
Solution 2: nohz_idle_balance(); rebalance_domains() on the ILB CPU Solution 3: Above patch.

I observe that Solution 3 is not as aggressive in spreading load as Solution 2. With Solution 2, the load gets spread within the first 3-4 seconds, while with Solution3, the load gets spread within the first 6-7 seconds. I think this is because, the above patch decides to further nohz_idle_load_balance() based on the load on the current ILB CPU which has most likely pulled just one task. This will abort further load balancing. However, Solution 3 is certainly better at spreading load than Solution 1.

Wrt IPIs, I see that Solution 2 results in increase in the number of IPIs by around 2% over Solution 3, probably for the same reason that Morten pointed out.

Regards
Preeti U Murthy

author
#12 lore raw
In reply to Tim Chen
Quoted 10 lines · Tim Chen

I think we can get rid of the done_balancing boolean and make it a bit easier to read if we change the above code to

kernel/sched/fair.c +0 -0
index bcfe320..08317dc 100644
@@ -7557,8 +7557,13 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
                 * work being done for other cpus. Next load
                 * balancing owner will pick it up.

kernel/sched/fair.c static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle) · line 7566

Quoted 10 lines
kernel/sched/fair.c +7 -2
                 */
-               if (need_resched())
-                       break;
+               if (need_resched()) {
+                       /* preparing to bail, kicking other cpu to continue */
+                       clear_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu));
+                       if (nohz_kick_needed(this_rq))
+                               nohz_balance_kick();
+                       return;
+               }

Hi Tim,

We would also need the nohz_kick_needed/nohz_balance_kick if we initially find that the current CPU is not idle (at the beginning of nohz_idle_balance). In the above case, we would need to add the code to 2 locations.

Would it be better to still keep the done_balancing to avoid having duplicate code?

#13 lore raw
Quoted 24 lines · Jason Low
Quoted 10 lines · Tim Chen

I think we can get rid of the done_balancing boolean and make it a bit easier to read if we change the above code to

kernel/sched/fair.c +0 -0
index bcfe320..08317dc 100644
@@ -7557,8 +7557,13 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
                 * work being done for other cpus. Next load
                 * balancing owner will pick it up.

kernel/sched/fair.c static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle) · line 7566

Quoted 10 lines
kernel/sched/fair.c +7 -2
                 */
-               if (need_resched())
-                       break;
+               if (need_resched()) {
+                       /* preparing to bail, kicking other cpu to continue */
+                       clear_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu));
+                       if (nohz_kick_needed(this_rq))
+                               nohz_balance_kick();
+                       return;
+               }

Hi Tim,

Quoted 8 lines

We would also need the nohz_kick_needed/nohz_balance_kick if we initially find that the current CPU is not idle (at the beginning of nohz_idle_balance). In the above case, we would need to add the code to 2 locations.

Would it be better to still keep the done_balancing to avoid having duplicate code?

How about consolidating the code for passing the nohz balancing and call it at both places. Something like below. Make the code more readable.

Tim

kernel/sched/fair.c +17 -5
index 40667cb..16f6904 100644
@@ -7531,6 +7531,15 @@ out:
 }
 
 #ifdef CONFIG_NO_HZ_COMMON
+static inline int nohz_kick_needed(struct rq *rq);
+
+static void inline pass_nohz_balance(struct rq *this_rq, int this_cpu)
+{
+       clear_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu));
+       if (nohz_kick_needed(this_rq))
+               nohz_balancer_kick();
+}
+
 /*
  * In CONFIG_NO_HZ_COMMON case, the idle balance kickee will do the
  * rebalancing for all the cpus for whom scheduler ticks are stopped.
@@ -7542,8 +7551,10 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
        int balance_cpu;
 
        if (idle != CPU_IDLE ||
-           !test_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu)))
-               goto end;
+           !test_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu))) {
+               pass_nohz_balance(this_rq, this_cpu);
+               return;
+       }
 
        for_each_cpu(balance_cpu, nohz.idle_cpus_mask) {
                if (balance_cpu == this_cpu || !idle_cpu(balance_cpu))
@@ -7554,8 +7565,10 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
                 * work being done for other cpus. Next load
                 * balancing owner will pick it up.
                 */
-               if (need_resched())
-                       break;
+               if (need_resched()) {
+                       pass_nohz_balance(this_rq, this_cpu);
+                       return;
+               }
 
                rq = cpu_rq(balance_cpu);
 
@@ -7575,7 +7588,6 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
                        this_rq->next_balance = rq->next_balance;
        }
        nohz.next_balance = this_rq->next_balance;
-end:
        clear_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu));
 }
 
author
#14 lore raw
Quoted 27 lines · Tim Chen

How about consolidating the code for passing the nohz balancing and call it at both places. Something like below. Make the code more readable.

Tim

kernel/sched/fair.c +9 -0
index 40667cb..16f6904 100644
@@ -7531,6 +7531,15 @@ out:
 }
 
 #ifdef CONFIG_NO_HZ_COMMON
+static inline int nohz_kick_needed(struct rq *rq);
+
+static void inline pass_nohz_balance(struct rq *this_rq, int this_cpu)
+{
+       clear_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu));
+       if (nohz_kick_needed(this_rq))
+               nohz_balancer_kick();
+}
+
 /*
  * In CONFIG_NO_HZ_COMMON case, the idle balance kickee will do the
  * rebalancing for all the cpus for whom scheduler ticks are stopped.

kernel/sched/fair.c static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle) · line 7557

Quoted 9 lines
kernel/sched/fair.c +4 -2
@@ -7542,8 +7551,10 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
        int balance_cpu;
 
        if (idle != CPU_IDLE ||
-           !test_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu)))
-               goto end;
+           !test_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu))) {
+               pass_nohz_balance(this_rq, this_cpu);
+               return;
+       }

Sure, this can make it more readable. This also avoids the need for the goto, in addition to removing the done_balancing boolean.

Thanks,
Jason

author
#16 lore raw
In reply to Preeti U Murthy
Quoted 7 lines · Preeti U Murthy

Solution 1: As exists in the mainline
Solution 2: nohz_idle_balance(); rebalance_domains() on the ILB CPU Solution 3: Above patch.

I observe that Solution 3 is not as aggressive in spreading load as Solution 2. With Solution 2, the load gets spread within the first 3-4 seconds,

hmm, so 3-4 seconds still sounds like a long time.

Quoted 4 lines

while with Solution3, the load gets spread within the first 6-7 seconds. I think this is because, the above patch decides to further nohz_idle_load_balance() based on the load on the current ILB CPU which has most likely pulled just one task.

Okay, so perhaps we can also try continuing nohz load balancing if we find that there are overloaded CPUs in the system.

author
#17 lore raw
Quoted 2 lines · Jason Low

Okay, so perhaps we can also try continuing nohz load balancing if we find that there are overloaded CPUs in the system.

Something like the following.

---

kernel/sched/fair.c +23 -12
index fdae26e..d636bf7 100644
@@ -7620,6 +7620,16 @@ out:
 }
 
 #ifdef CONFIG_NO_HZ_COMMON
+static inline bool nohz_kick_needed(struct rq *rq);
+
+static inline void pass_nohz_balance(struct rq *this_rq, int this_cpu)
+{
+	clear_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu));
+	nohz.next_balance = jiffies;
+	if (nohz_kick_needed(this_rq))
+		nohz_balancer_kick();
+}
+
 /*
  * In CONFIG_NO_HZ_COMMON case, the idle balance kickee will do the
  * rebalancing for all the cpus for whom scheduler ticks are stopped.
@@ -7631,8 +7641,10 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 	int balance_cpu;
 
 	if (idle != CPU_IDLE ||
-	    !test_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu)))
-		goto end;
+	    !test_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu))) {
+		pass_nohz_balance(this_rq, this_cpu);
+		return;
+	}
 
 	for_each_cpu(balance_cpu, nohz.idle_cpus_mask) {
 		if (balance_cpu == this_cpu || !idle_cpu(balance_cpu))
@@ -7643,8 +7655,10 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 		 * work being done for other cpus. Next load
 		 * balancing owner will pick it up.
 		 */
-		if (need_resched())
-			break;
+		if (need_resched()) {
+			pass_nohz_balance(this_rq, this_cpu);
+			return;
+		}
 
 		rq = cpu_rq(balance_cpu);
 
@@ -7664,7 +7678,6 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 			this_rq->next_balance = rq->next_balance;
 	}
 	nohz.next_balance = this_rq->next_balance;
-end:
 	clear_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu));
 }
 
@@ -7687,7 +7700,7 @@ static inline bool nohz_kick_needed(struct rq *rq)
 	int nr_busy, cpu = rq->cpu;
 	bool kick = false;
 
-	if (unlikely(rq->idle_balance))
+	if (unlikely(idle_cpu(cpu)))
 		return false;
 
        /*
@@ -7707,7 +7720,7 @@ static inline bool nohz_kick_needed(struct rq *rq)
 	if (time_before(now, nohz.next_balance))
 		return false;
 
-	if (rq->nr_running >= 2)
+	if (rq->nr_running >= 2 || rq->rd->overload)
 		return true;
 
 	rcu_read_lock();
@@ -7757,16 +7770,14 @@ static void run_rebalance_domains(struct softirq_action *h)
 	enum cpu_idle_type idle = this_rq->idle_balance ?
 						CPU_IDLE : CPU_NOT_IDLE;
 
+	rebalance_domains(this_rq, idle);
+
 	/*
 	 * If this cpu has a pending nohz_balance_kick, then do the
 	 * balancing on behalf of the other idle cpus whose ticks are
-	 * stopped. Do nohz_idle_balance *before* rebalance_domains to
-	 * give the idle cpus a chance to load balance. Else we may
-	 * load balance only within the local sched_domain hierarchy
-	 * and abort nohz_idle_balance altogether if we pull some load.
+	 * stopped.
 	 */
 	nohz_idle_balance(this_rq, idle);
-	rebalance_domains(this_rq, idle);
 }
 
 /*
#18 lore raw
Quoted 13 lines · Jason Low
Quoted 2 lines · Jason Low

Okay, so perhaps we can also try continuing nohz load balancing if we find that there are overloaded CPUs in the system.

Something like the following.

---

kernel/sched/fair.c +0 -0
index fdae26e..d636bf7 100644

kernel/sched/fair.c out: · line 7628

Quoted 9 lines
kernel/sched/fair.c +6 -0
@@ -7620,6 +7620,16 @@ out:
 }
 
 #ifdef CONFIG_NO_HZ_COMMON
+static inline bool nohz_kick_needed(struct rq *rq);
+
+static inline void pass_nohz_balance(struct rq *this_rq, int this_cpu)
+{
+	clear_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu));
+	nohz.next_balance = jiffies;

Why are we updating nohz.next_balance here?

kernel/sched/fair.c static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle) · line 7643

Quoted 11 lines
kernel/sched/fair.c +4 -0
+	if (nohz_kick_needed(this_rq))
+		nohz_balancer_kick();
+}
+
 /*
  * In CONFIG_NO_HZ_COMMON case, the idle balance kickee will do the
  * rebalancing for all the cpus for whom scheduler ticks are stopped.
@@ -7631,8 +7641,10 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 	int balance_cpu;
 
 	if (idle != CPU_IDLE ||

Would it make sense to add need_resched here like
http://mid.gmane.org/[email protected]

Quoted 9 lines
kernel/sched/fair.c +4 -2
-	    !test_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu)))
-		goto end;
+	    !test_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu))) {
+		pass_nohz_balance(this_rq, this_cpu);
+		return;
+	}
 
 	for_each_cpu(balance_cpu, nohz.idle_cpus_mask) {
 		if (balance_cpu == this_cpu || !idle_cpu(balance_cpu))

<snipped >

kernel/sched/fair.c static inline bool nohz_kick_needed(struct rq *rq) · line 7704

Quoted 7 lines
kernel/sched/fair.c +1 -1
@@ -7687,7 +7700,7 @@ static inline bool nohz_kick_needed(struct rq *rq)
 	int nr_busy, cpu = rq->cpu;
 	bool kick = false;
 
-	if (unlikely(rq->idle_balance))
+	if (unlikely(idle_cpu(cpu)))
 		return false;

The only other place that we use idle_balance is run_rebalance_domains(). Would it make sense to just use idle_cpu() in run_rebalance_domains() and remove rq->idle_balance?

Quoted 33 lines
kernel/sched/fair.c +4 -6
        /*
@@ -7707,7 +7720,7 @@ static inline bool nohz_kick_needed(struct rq *rq)
 	if (time_before(now, nohz.next_balance))
 		return false;
 
-	if (rq->nr_running >= 2)
+	if (rq->nr_running >= 2 || rq->rd->overload)
 		return true;
 
 	rcu_read_lock();
@@ -7757,16 +7770,14 @@ static void run_rebalance_domains(struct softirq_action *h)
 	enum cpu_idle_type idle = this_rq->idle_balance ?
 						CPU_IDLE : CPU_NOT_IDLE;
 
+	rebalance_domains(this_rq, idle);
+
 	/*
 	 * If this cpu has a pending nohz_balance_kick, then do the
 	 * balancing on behalf of the other idle cpus whose ticks are
-	 * stopped. Do nohz_idle_balance *before* rebalance_domains to
-	 * give the idle cpus a chance to load balance. Else we may
-	 * load balance only within the local sched_domain hierarchy
-	 * and abort nohz_idle_balance altogether if we pull some load.
+	 * stopped.
 	 */
 	nohz_idle_balance(this_rq, idle);
-	rebalance_domains(this_rq, idle);
 }
 
 /*
Signature · 2 lines
Thanks and Regards
Srikar Dronamraju
author
#19 lore raw
Quoted 17 lines · Srikar Dronamraju
Quoted 15 lines · Jason Low
Quoted 2 lines · Jason Low

Okay, so perhaps we can also try continuing nohz load balancing if we find that there are overloaded CPUs in the system.

Something like the following.

---

kernel/sched/fair.c +0 -0
index fdae26e..d636bf7 100644
@@ -7620,6 +7620,16 @@ out:
 }
 
Quoted 9 lines

kernel/sched/fair.c out: · line 7628

Quoted 7 lines
kernel/sched/fair.c +6 -0
 #ifdef CONFIG_NO_HZ_COMMON
+static inline bool nohz_kick_needed(struct rq *rq);
+
+static inline void pass_nohz_balance(struct rq *this_rq, int this_cpu)
+{
+	clear_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu));
+	nohz.next_balance = jiffies;

Why are we updating nohz.next_balance here?

This was just to make sure that since we're continuing the balancing on another CPU that the nohz next_balance is guaranteed to be "now".

Quoted 10 lines
Quoted 10 lines
kernel/sched/fair.c +4 -0
+	if (nohz_kick_needed(this_rq))
+		nohz_balancer_kick();
+}
+
 /*
  * In CONFIG_NO_HZ_COMMON case, the idle balance kickee will do the
  * rebalancing for all the cpus for whom scheduler ticks are stopped.
@@ -7631,8 +7641,10 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 	int balance_cpu;
 
Quoted 4 lines

kernel/sched/fair.c static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle) · line 7643

Quoted 1 line
kernel/sched/fair.c +0 -0
 	if (idle != CPU_IDLE ||

Would it make sense to add need_resched here like
http://mid.gmane.org/[email protected]

Yeah, we could have incorporated adding the need_resched there too for testing purposes.

Though that probably wouldn't make too much of a difference in performance with this patch, since this also modified the need_resched() check in the loop + nohz.next_balance. So I think it would still be fine to test this without the added need_resched().

author
#23 lore raw
In reply to Srikar Dronamraju
Quoted 5 lines · Srikar Dronamraju
Quoted 4 lines · Jason Low
kernel/sched/fair.c +0 -0
@@ -7687,7 +7700,7 @@ static inline bool nohz_kick_needed(struct rq *rq)
 	int nr_busy, cpu = rq->cpu;
 	bool kick = false;
 
Quoted 8 lines

kernel/sched/fair.c static inline bool nohz_kick_needed(struct rq *rq) · line 7704

Quoted 3 lines
kernel/sched/fair.c +1 -1
-	if (unlikely(rq->idle_balance))
+	if (unlikely(idle_cpu(cpu)))
 		return false;

The only other place that we use idle_balance is run_rebalance_domains(). Would it make sense to just use idle_cpu() in run_rebalance_domains() and remove rq->idle_balance?

Hi Srikar,

So the idle_balance is used for storing the idle state of the CPU before calling the softirq, for load balancing decisions. In that case, we may need to keep this extra variable in order to store that information.

#24 lore raw
Quoted 15 lines · Jason Low
Quoted 5 lines · Srikar Dronamraju
Quoted 4 lines · Jason Low
kernel/sched/fair.c +0 -0
@@ -7687,7 +7700,7 @@ static inline bool nohz_kick_needed(struct rq *rq)
 	int nr_busy, cpu = rq->cpu;
 	bool kick = false;
 
Quoted 8 lines

kernel/sched/fair.c static inline bool nohz_kick_needed(struct rq *rq) · line 7704

Quoted 3 lines
kernel/sched/fair.c +1 -1
-	if (unlikely(rq->idle_balance))
+	if (unlikely(idle_cpu(cpu)))
 		return false;

The only other place that we use idle_balance is run_rebalance_domains(). Would it make sense to just use idle_cpu() in run_rebalance_domains() and remove rq->idle_balance?

Quoted 6 lines

Hi Srikar,

So the idle_balance is used for storing the idle state of the CPU before calling the softirq, for load balancing decisions. In that case, we may need to keep this extra variable in order to store that information.

I am not sure if you got what I wanted to convey.

rq->idle_balance gets updated at every scheduler_tick() but the only user of rq->idle_balance (after your change) seems to be run_rebalance_domains(). Now can we remove rq->idle_balance. This would mean we would have to call idle_cpu() instead of using rq->idle_balance in run_rebalance_domains(). (similar to what your above change)

That way we can reduce the rq struct size and we might end up calling idle_cpu() lesser number of times.

Signature · 2 lines
Thanks and Regards
Srikar Dronamraju
author
#25 lore raw
Quoted 8 lines · Srikar Dronamraju

rq->idle_balance gets updated at every scheduler_tick() but the only user of rq->idle_balance (after your change) seems to be run_rebalance_domains(). Now can we remove rq->idle_balance. This would mean we would have to call idle_cpu() instead of using rq->idle_balance in run_rebalance_domains(). (similar to what your above change)

That way we can reduce the rq struct size and we might end up calling idle_cpu() lesser number of times.

Yeah, we may also include another patch for that.

Taking a look at rebalance_domains(), we're already updating the "idle" value using idle_cpu() after attempting load balancing anyway, so there may not be much point in the extra parameter.

#20 lore raw
In reply to Jason Low
Quoted 11 lines
Quoted 10 lines

kernel/sched/fair.c out: · line 7628

Quoted 8 lines

#ifdef CONFIG_NO_HZ_COMMON

kernel/sched/fair.c +6 -0
+static inline bool nohz_kick_needed(struct rq *rq);
+
+static inline void pass_nohz_balance(struct rq *this_rq, int this_cpu)
+{
+	clear_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu));
+	nohz.next_balance = jiffies;

Why are we updating nohz.next_balance here?

Quoted 3 lines

This was just to make sure that since we're continuing the balancing on another CPU that the nohz next_balance is guaranteed to be "now".

Since we are in nohz_idle_balance(), nohz.next_balance is guaranteed be less than now. We do check for time_before(now, nohz.next_balance) in nohz_kick_needed(). So in effect we are incrementing the nohz.next_balance.

While updating nohz.next_balance may not cause any issues, it atleast look redundant to me.

At this point, I also wanted to understand why we do "nohz.next_balance++" nohz_balancer_kick()?

Quoted 5 lines
Quoted 5 lines

kernel/sched/fair.c out: · line 7633

Quoted 5 lines
kernel/sched/fair.c +4 -0
+	if (nohz_kick_needed(this_rq))
+		nohz_balancer_kick();
+}
+
 /*

--
Thanks and Regards
Srikar Dronamraju

#26 lore raw
In reply to Jason Low

Hi Jason,

Quoted 4 lines · Jason Low
Quoted 2 lines · Jason Low

Okay, so perhaps we can also try continuing nohz load balancing if we find that there are overloaded CPUs in the system.

Sorry about the delay. Ok I will test out the below patch and share the results.

Regards
Preeti U Murthy

Quoted 99 lines

Something like the following.

---

kernel/sched/fair.c +23 -12
index fdae26e..d636bf7 100644
@@ -7620,6 +7620,16 @@ out:
 }
 
 #ifdef CONFIG_NO_HZ_COMMON
+static inline bool nohz_kick_needed(struct rq *rq);
+
+static inline void pass_nohz_balance(struct rq *this_rq, int this_cpu)
+{
+	clear_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu));
+	nohz.next_balance = jiffies;
+	if (nohz_kick_needed(this_rq))
+		nohz_balancer_kick();
+}
+
 /*
  * In CONFIG_NO_HZ_COMMON case, the idle balance kickee will do the
  * rebalancing for all the cpus for whom scheduler ticks are stopped.
@@ -7631,8 +7641,10 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 	int balance_cpu;
 
 	if (idle != CPU_IDLE ||
-	    !test_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu)))
-		goto end;
+	    !test_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu))) {
+		pass_nohz_balance(this_rq, this_cpu);
+		return;
+	}
 
 	for_each_cpu(balance_cpu, nohz.idle_cpus_mask) {
 		if (balance_cpu == this_cpu || !idle_cpu(balance_cpu))
@@ -7643,8 +7655,10 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 		 * work being done for other cpus. Next load
 		 * balancing owner will pick it up.
 		 */
-		if (need_resched())
-			break;
+		if (need_resched()) {
+			pass_nohz_balance(this_rq, this_cpu);
+			return;
+		}
 
 		rq = cpu_rq(balance_cpu);
 
@@ -7664,7 +7678,6 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 			this_rq->next_balance = rq->next_balance;
 	}
 	nohz.next_balance = this_rq->next_balance;
-end:
 	clear_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu));
 }
 
@@ -7687,7 +7700,7 @@ static inline bool nohz_kick_needed(struct rq *rq)
 	int nr_busy, cpu = rq->cpu;
 	bool kick = false;
 
-	if (unlikely(rq->idle_balance))
+	if (unlikely(idle_cpu(cpu)))
 		return false;
 
        /*
@@ -7707,7 +7720,7 @@ static inline bool nohz_kick_needed(struct rq *rq)
 	if (time_before(now, nohz.next_balance))
 		return false;
 
-	if (rq->nr_running >= 2)
+	if (rq->nr_running >= 2 || rq->rd->overload)
 		return true;
 
 	rcu_read_lock();
@@ -7757,16 +7770,14 @@ static void run_rebalance_domains(struct softirq_action *h)
 	enum cpu_idle_type idle = this_rq->idle_balance ?
 						CPU_IDLE : CPU_NOT_IDLE;
 
+	rebalance_domains(this_rq, idle);
+
 	/*
 	 * If this cpu has a pending nohz_balance_kick, then do the
 	 * balancing on behalf of the other idle cpus whose ticks are
-	 * stopped. Do nohz_idle_balance *before* rebalance_domains to
-	 * give the idle cpus a chance to load balance. Else we may
-	 * load balance only within the local sched_domain hierarchy
-	 * and abort nohz_idle_balance altogether if we pull some load.
+	 * stopped.
 	 */
 	nohz_idle_balance(this_rq, idle);
-	rebalance_domains(this_rq, idle);
 }
 
 /*
author
#21 lore raw
In reply to Srikar Dronamraju
Quoted 11 lines · Srikar Dronamraju
Quoted 11 lines
Quoted 10 lines

kernel/sched/fair.c out: · line 7628

Quoted 8 lines

#ifdef CONFIG_NO_HZ_COMMON

kernel/sched/fair.c +6 -0
+static inline bool nohz_kick_needed(struct rq *rq);
+
+static inline void pass_nohz_balance(struct rq *this_rq, int this_cpu)
+{
+	clear_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu));
+	nohz.next_balance = jiffies;

Why are we updating nohz.next_balance here?

Quoted 7 lines
Quoted 3 lines

This was just to make sure that since we're continuing the balancing on another CPU that the nohz next_balance is guaranteed to be "now".

Since we are in nohz_idle_balance(), nohz.next_balance is guaranteed be less than now. We do check for time_before(now, nohz.next_balance) in nohz_kick_needed(). So in effect we are incrementing the nohz.next_balance.

Hi Srikar,

If now is equal to nohz.next_balance, we may attempt nohz_balancer_kick().

After it does nohz.next_balance++ in nohz_balancer_kick(), now can be 1 less than the new nohz.next_balance value by the time nohz_idle_balance() is attempted(). Without updating nohz.next_balance, the time_before(now, nohz.next_balance) check in nohz_kick_needed() may cause it to return false.

author
#22 lore raw
In reply to Srikar Dronamraju
Quoted 2 lines · Srikar Dronamraju

At this point, I also wanted to understand why we do "nohz.next_balance++" nohz_balancer_kick()?

So this looks like something that was added to avoid nohz_balancer_kick() getting called too frequently. Otherwise, it may get called in each trigger_load_balance(), even when another CPU has already been kicked to do balancing.

author
#27 lore raw
In reply to Preeti U Murthy
Quoted 26 lines
Quoted 26 lines

---

kernel/sched/fair.c +10 -0
index fdae26e..d636bf7 100644
@@ -7620,6 +7620,16 @@ out:
 }
 
 #ifdef CONFIG_NO_HZ_COMMON
+static inline bool nohz_kick_needed(struct rq *rq);
+
+static inline void pass_nohz_balance(struct rq *this_rq, int this_cpu)
+{
+	clear_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu));
+	nohz.next_balance = jiffies;
+	if (nohz_kick_needed(this_rq))
+		nohz_balancer_kick();
+}
+
 /*
  * In CONFIG_NO_HZ_COMMON case, the idle balance kickee will do the
  * rebalancing for all the cpus for whom scheduler ticks are stopped.
@@ -7631,8 +7641,10 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 	int balance_cpu;
 
Quoted 7 lines

kernel/sched/fair.c static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle) · line 7647

Quoted 7 lines
kernel/sched/fair.c +4 -2
 	if (idle != CPU_IDLE ||
-	    !test_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu)))
-		goto end;
+	    !test_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu))) {
+		pass_nohz_balance(this_rq, this_cpu);
+		return;
+	}

hmm, so taking a look at the patch again, it looks like we pass nohz balance even when the NOHZ_BALANCE_KICK is not set on the current CPU. We should separate the 2 conditions:

    if (!test_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu)))
        return;

    if (idle != CPU_IDLE) {
        /* another CPU continue balancing */
        pass_nohz_balance(this_rq, this_cpu);
        return;
    }

In general, separating the check also optimizes nohz_idle_balance() to avoid clearing the bit when it is not set.

author
#28 lore raw
Quoted 4 lines · Jason Low

hmm, so taking a look at the patch again, it looks like we pass nohz balance even when the NOHZ_BALANCE_KICK is not set on the current CPU. We should separate the 2 conditions:

Quoted 8 lines
    if (!test_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu)))
        return;

    if (idle != CPU_IDLE) {
        /* another CPU continue balancing */
        pass_nohz_balance(this_rq, this_cpu);
        return;
    }

Here's the example patch with the above update.

---

kernel/sched/fair.c +26 -13
index ffeaa41..9aa48f7 100644
@@ -7622,6 +7622,16 @@ out:
 }
 
 #ifdef CONFIG_NO_HZ_COMMON
+static inline bool nohz_kick_needed(struct rq *rq);
+
+static inline void pass_nohz_balance(struct rq *this_rq, int this_cpu)
+{
+	clear_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu));
+	nohz.next_balance = jiffies;
+	if (nohz_kick_needed(this_rq))
+		nohz_balancer_kick();
+}
+
 /*
  * In CONFIG_NO_HZ_COMMON case, the idle balance kickee will do the
  * rebalancing for all the cpus for whom scheduler ticks are stopped.
@@ -7632,9 +7642,13 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 	struct rq *rq;
 	int balance_cpu;
 
-	if (idle != CPU_IDLE ||
-	    !test_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu)))
-		goto end;
+	if (!test_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu)))
+		return;
+
+	if (idle != CPU_IDLE) {
+		pass_nohz_balance(this_rq, this_cpu);
+		return;
+	}
 
 	for_each_cpu(balance_cpu, nohz.idle_cpus_mask) {
 		if (balance_cpu == this_cpu || !idle_cpu(balance_cpu))
@@ -7645,8 +7659,10 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 		 * work being done for other cpus. Next load
 		 * balancing owner will pick it up.
 		 */
-		if (need_resched())
-			break;
+		if (need_resched()) {
+			pass_nohz_balance(this_rq, this_cpu);
+			return;
+		}
 
 		rq = cpu_rq(balance_cpu);
 
@@ -7666,7 +7682,6 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 			this_rq->next_balance = rq->next_balance;
 	}
 	nohz.next_balance = this_rq->next_balance;
-end:
 	clear_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu));
 }
 
@@ -7689,7 +7704,7 @@ static inline bool nohz_kick_needed(struct rq *rq)
 	int nr_busy, cpu = rq->cpu;
 	bool kick = false;
 
-	if (unlikely(rq->idle_balance))
+	if (unlikely(idle_cpu(cpu)))
 		return false;
 
        /*
@@ -7709,7 +7724,7 @@ static inline bool nohz_kick_needed(struct rq *rq)
 	if (time_before(now, nohz.next_balance))
 		return false;
 
-	if (rq->nr_running >= 2)
+	if (rq->nr_running >= 2 || rq->rd->overload)
 		return true;
 
 	rcu_read_lock();
@@ -7759,16 +7774,14 @@ static void run_rebalance_domains(struct softirq_action *h)
 	enum cpu_idle_type idle = this_rq->idle_balance ?
 						CPU_IDLE : CPU_NOT_IDLE;
 
+	rebalance_domains(this_rq, idle);
+
 	/*
 	 * If this cpu has a pending nohz_balance_kick, then do the
 	 * balancing on behalf of the other idle cpus whose ticks are
-	 * stopped. Do nohz_idle_balance *before* rebalance_domains to
-	 * give the idle cpus a chance to load balance. Else we may
-	 * load balance only within the local sched_domain hierarchy
-	 * and abort nohz_idle_balance altogether if we pull some load.
+	 * stopped.
 	 */
 	nohz_idle_balance(this_rq, idle);
-	rebalance_domains(this_rq, idle);
 }
 
 /*