Skip to contentSkip to conversation

Patch: dynticks: idle load balancing

RFC In review Siddha, Suresh B 5 participants 25 messages Dec 12, 2006 – Feb 24, 2007

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

RFC 1/1 Patch: dynticks: idle load balancing

Appended patch attempts to fix the process idle load balancing in the presence of dynticks. cpus for which ticks are stopped will sleep till the next event wakes it up. Potentially these sleeps can be for large durations and during which today, there is no idle load balancing being done. There was some discussion happened(last year) on this topic on lkml, where two main approaches were gettting debated. One is to back off the idle load balancing for bigger intervals and the second is a watchdog mechanism where the busy cpu will trigger the load balance on an idle cpu. Both of these mechanisms have its drawbacks.

For the first mechanism, defining the interval will be tricky and if it is too much, then the response time will also be high and we won't be able to respond for sudden changes in the load. If it is small, then we won't be able to save power.

Second mechanism will be making changes to the busy load balancing(which will be doing more load balancing work, while the current busy task on that cpu is eagerly waiting for the cpu cycles). Also busy load balancing intervals are quite different from idle load balancing intervals. Similar to the first mechanism, we won't be able to respond quickly to change in loads. And also figuring out that a cpu is heavily loaded and where that extra load need to moved, is some what difficult job, especially so in the case of hierarchical scheduler domains.

Appended patch takes a third route which nominates an owner among the idle cpus, which does the idle load balancing on behalf of the other idle cpus. And once all the cpus are completely idle, then we can stop this idle load balancing too. Checks added in fast path are minimized. Whenever there are busy cpus in the system, there will be an owner(idle cpu) doing the system wide idle load balancing. If we nominate this owner carefully(like an idle core in a busy package), we can minimize the power wasted also.

Some of the questions I have are: Will this single owner become bottleneck? Idle load balancing is now serialized among all the idle cpus. This perhaps will add some delays in load movement to different idle cpus. IMO, these delays will be small and tolerable. If this comes out to be a concern, we can offload the actual load movement work to the idle cpu, where the load will be finally run.

Any more optimizations we can do to start/stop_sched_tick() routines to track this info more efficiently?

Comments and review feedback welcome. Minimal testing done on couple of i386 platforms. Perf testing yet to be done.

thanks,
suresh
---
Track the cpus for which ticks are stopped and one among these cpus will be doing the idle load balancing on behalf of all the remaining cpus. If the ticks are stopped for all the cpus in the system, idle load balancing will stop at that moment. And restarts as soon as there is a busy cpu in the system.

TBD: Select the appropriate idle cpu for doing this idle load balancing. Such as an idle core in a busy package(which has a busy core). Selecting an idle thread as the owner when there are other busy thread siblings is not a good idea.

We can also think of offloading the task movements from the idle load balancing owner to the idle cpu on behalf of which this work is being done.

---

include/linux/sched.h +8 -0
diff -pNru linux-2.6.19-mm1/include/linux/sched.h linux/include/linux/sched.h
@@ -195,6 +195,14 @@ extern void sched_init_smp(void);
 extern void init_idle(struct task_struct *idle, int cpu);
 
 extern cpumask_t nohz_cpu_mask;
+#ifdef CONFIG_SMP
+extern int select_notick_load_balancer(int cpu);
+#else
+static inline int select_notick_load_balancer(int cpu)
+{
+	return 0;
+}
+#endif
 
 /*
  * Only dump TASK_* tasks. (-1 for all tasks)
kernel/hrtimer.c +6 -0
diff -pNru linux-2.6.19-mm1/kernel/hrtimer.c linux/kernel/hrtimer.c
@@ -600,6 +600,9 @@ void hrtimer_stop_sched_tick(void)
 		 * the scheduler tick in hrtimer_restart_sched_tick.
 		 */
 		if (!cpu_base->tick_stopped) {
+			if (select_notick_load_balancer(1))
+				goto end;
+
 			cpu_base->idle_tick = cpu_base->sched_timer.expires;
 			cpu_base->tick_stopped = 1;
 			cpu_base->idle_jiffies = last_jiffies;
@@ -616,6 +619,7 @@ void hrtimer_stop_sched_tick(void)
 			raise_softirq_irqoff(TIMER_SOFTIRQ);
 	}
 
+end:
 	local_irq_restore(flags);
 }
 
@@ -630,6 +634,8 @@ void hrtimer_restart_sched_tick(void)
 	unsigned long ticks;
 	ktime_t now, delta;
 
+	select_notick_load_balancer(0);
+
 	if (!cpu_base->hres_active || !cpu_base->tick_stopped)
 		return;
 
kernel/sched.c +124 -2

172 lines not on this page · raw message

#1 lore raw
Quoted 10 lines · Siddha, Suresh B

Appended patch attempts to fix the process idle load balancing in the presence of dynticks. cpus for which ticks are stopped will sleep till the next event wakes it up. Potentially these sleeps can be for large durations and during which today, there is no idle load balancing being done. There was some discussion happened(last year) on this topic on lkml, where two main approaches were gettting debated. One is to back off the idle load balancing for bigger intervals and the second is a watchdog mechanism where the busy cpu will trigger the load balance on an idle cpu. Both of these mechanisms have its drawbacks.

nice work! I have added your patch to -rt. Btw., it needs the patch below to work on 64-bit.

Ingo

kernel/sched.c +1 -1
Index: linux/kernel/sched.c
===================================================================
@@ -1170,7 +1170,7 @@ static void resched_task(struct task_str
 static void resched_cpu(int cpu)
 {
 	struct rq *rq = cpu_rq(cpu);
-	unsigned int flags;
+	unsigned long flags;
 
 	spin_lock_irqsave(&rq->lock, flags);
 	resched_task(cpu_curr(cpu));
#2 lore raw
Quoted 11 lines · Ingo Molnar
Quoted 10 lines

Appended patch attempts to fix the process idle load balancing in the presence of dynticks. cpus for which ticks are stopped will sleep till the next event wakes it up. Potentially these sleeps can be for large durations and during which today, there is no idle load balancing being done. There was some discussion happened(last year) on this topic on lkml, where two main approaches were gettting debated. One is to back off the idle load balancing for bigger intervals and the second is a watchdog mechanism where the busy cpu will trigger the load balance on an idle cpu. Both of these mechanisms have its drawbacks.

Quoted 2 lines

nice work! I have added your patch to -rt. Btw., it needs the patch below to work on 64-bit.

there's another bug as well: in schedule() resched_cpu() is called with the current runqueue held in two places, which is deadlock potential. The easiest fix for this is to use trylock - find the patch for that. This is a hint only anyway - and if a CPU is idle its runqueue will be lockable. (fixing it via double-locking is easy in the first call site, but the second one looks harder)

Ingo

kernel/sched.c +4 -2
Index: linux/kernel/sched.c
===================================================================
@@ -1167,12 +1167,14 @@ static void resched_task(struct task_str
 	if (!tsk_is_polling(p))
 		smp_send_reschedule(cpu);
 }
+
 static void resched_cpu(int cpu)
 {
 	struct rq *rq = cpu_rq(cpu);
-	unsigned int flags;
+	unsigned long flags;
 
-	spin_lock_irqsave(&rq->lock, flags);
+	if (!spin_trylock_irqsave(&rq->lock, flags))
+		return;
 	resched_task(cpu_curr(cpu));
 	spin_unlock_irqrestore(&rq->lock, flags);
 }
#3 lore raw
Quoted 2 lines · Ingo Molnar

there's another bug as well: in schedule() resched_cpu() is called with the current runqueue held in two places, which is deadlock potential.

resched_cpu() was getting called after prepare_task_switch() which releases the current runqueue lock. Isn't it?

Quoted 2 lines

The easiest fix for this is to use trylock - find the patch for that. This is a hint only anyway - and if a CPU is idle its runqueue will be

Though I don't see a potential deadlock, I like this optimization.

thanks,
suresh

Quoted 26 lines

lockable. (fixing it via double-locking is easy in the first call site, but the second one looks harder)

Ingo

Index: linux/kernel/sched.c
===================================================================

kernel/sched.c +4 -2
@@ -1167,12 +1167,14 @@ static void resched_task(struct task_str
 	if (!tsk_is_polling(p))
 		smp_send_reschedule(cpu);
 }
+
 static void resched_cpu(int cpu)
 {
 	struct rq *rq = cpu_rq(cpu);
-	unsigned int flags;
+	unsigned long flags;
 
-	spin_lock_irqsave(&rq->lock, flags);
+	if (!spin_trylock_irqsave(&rq->lock, flags))
+		return;
 	resched_task(cpu_curr(cpu));
 	spin_unlock_irqrestore(&rq->lock, flags);
 }
#4 lore raw
Quoted 6 lines · Siddha, Suresh B
Quoted 2 lines · Ingo Molnar

there's another bug as well: in schedule() resched_cpu() is called with the current runqueue held in two places, which is deadlock potential.

resched_cpu() was getting called after prepare_task_switch() which releases the current runqueue lock. Isn't it?

no, it doesnt release it. The finish stage is what releases it.

the other problem is load_balance(): there this_rq is locked and you call resched_cpu() unconditionally.

Ingo

#5 lore raw
Quoted 11 lines · Ingo Molnar
Quoted 6 lines · Siddha, Suresh B
Quoted 2 lines · Ingo Molnar

there's another bug as well: in schedule() resched_cpu() is called with the current runqueue held in two places, which is deadlock potential.

resched_cpu() was getting called after prepare_task_switch() which releases the current runqueue lock. Isn't it?

no, it doesnt release it. The finish stage is what releases it.

I see.

Quoted 2 lines

the other problem is load_balance(): there this_rq is locked and you call resched_cpu() unconditionally.

But here resched_cpu() was called after double_rq_unlock().

thanks,
suresh

#6 lore raw
Quoted 4 lines · Siddha, Suresh B
Quoted 2 lines

the other problem is load_balance(): there this_rq is locked and you call resched_cpu() unconditionally.

But here resched_cpu() was called after double_rq_unlock().

yeah, you are right - the schedule() one is/was the only problem.

Ingo

#7 lore raw
In reply to Siddha, Suresh B

find below another bugfix for the dynticks-sched patch. (this bug caused crashed under a stresstest)

Ingo

---
 kernel/sched.c |    2 ++
 1 file changed, 2 insertions(+)
kernel/sched.c +2 -0
Index: linux/kernel/sched.c
===================================================================
@@ -3015,6 +3015,8 @@ static void run_rebalance_domains(struct
 restart:
 	if (idle_cpu(local_cpu) && notick.load_balancer == local_cpu) {
 		this_cpu = first_cpu(cpus);
+		if (unlikely(this_cpu >= NR_CPUS))
+			return;
 		this_rq = cpu_rq(this_cpu);
 		cpu_clear(this_cpu, cpus);
 	}
#8 lore raw

kernel/sched.c static void run_rebalance_domains(struct · line 3019

Quoted 5 lines · Ingo Molnar

restart:

kernel/sched.c +2 -0
 	if (idle_cpu(local_cpu) && notick.load_balancer == local_cpu) {
 		this_cpu = first_cpu(cpus);
+		if (unlikely(this_cpu >= NR_CPUS))
+			return;

oops.

There is window when local_cpu is cleared from notick.cpumask
but the notick.load_balancer still points to local_cpu..
This can also be corrected by first resetting the notick.load_balancer before clearing that cpu from notick.cpumask in select_notick_load_balancer()

thanks,
suresh

#9 lore raw

Suresh,

on the latest -rt kernel, when the dynticks load-balancer is enabled, then a dual-core Core2 Duo test-system increases its irq rate from the normal 15/17 per second to 300-400/sec - on a completely idle system(!). Any idea what's going on? I'll disable the load balancer for now.

Ingo

#10 lore raw

Sorry for the delayed response. I was away on vacation.

Please let me know if you still see this issue with the latest -rt kernel.

thanks,
suresh

Quoted 9 lines · Ingo Molnar

Suresh,

on the latest -rt kernel, when the dynticks load-balancer is enabled, then a dual-core Core2 Duo test-system increases its irq rate from the normal 15/17 per second to 300-400/sec - on a completely idle system(!). Any idea what's going on? I'll disable the load balancer for now.

Ingo

#11 lore raw
Quoted 7 lines · Suresh B

Please let me know if you still see this issue with the latest -rt kernel.

Quoted 4 lines · Ingo Molnar

on the latest -rt kernel, when the dynticks load-balancer is enabled, then a dual-core Core2 Duo test-system increases its irq rate from the normal 15/17 per second to 300-400/sec - on a completely idle system(!). Any idea what's going on? I'll disable the load balancer for now.

Ok. got time to look into this.

The answer is simple. load_balancing in the recent kernels is happening using SCHED_SOFTIRQ and in -rt tree that happens not in the idle process context but in the context of softirqd for SCHED_SOFTIRQ.

This breaks the dynticks load balancer and also the regular idle load balancing too :(

Am on to fixing the problem now :)

thanks,
suresh

#12 lore raw

PATCH 1/2 sched: fix idle load balancing in softirqd context

In reply to Siddha, Suresh B

Periodic load balancing in recent kernels happen in the softirq. In certain -rt configurations, these softirqs are handled in softirqd context. And hence the check for idle processor was always returning busy (as nr_running > 1).

This patch captures the idle information at the tick and passes this info to softirq context through an element 'idle_at_tick' in rq.

---

kernel/sched.c +5 -8
diff -pNru linux-2.6.20.x86_64/kernel/sched.c linux/kernel/sched.c
@@ -240,6 +240,7 @@ struct rq {
 	unsigned long raw_weighted_load;
 #ifdef CONFIG_SMP
 	unsigned long cpu_load[3];
+	unsigned char idle_at_tick;
 #endif
 	unsigned long long nr_switches;
 
@@ -3350,12 +3351,7 @@ static void run_rebalance_domains(struct
 	struct rq *this_rq = cpu_rq(this_cpu);
 	unsigned long interval;
 	struct sched_domain *sd;
-	/*
-	 * We are idle if there are no processes running. This
-	 * is valid even if we are the idle process (SMT).
-	 */
-	enum idle_type idle = !this_rq->nr_running ?
-				SCHED_IDLE : NOT_IDLE;
+	enum idle_type idle = this_rq->idle_at_tick ? SCHED_IDLE : NOT_IDLE;
 	/* Earliest time when we have to call run_rebalance_domains again */
 	unsigned long next_balance = jiffies + 60*HZ;
 
@@ -3651,20 +3647,21 @@ void scheduler_tick(void)
 {
 	unsigned long long now = sched_clock();
 	struct task_struct *p = current;
-	int cpu = smp_processor_id();
+	int cpu = smp_processor_id(), idle_at_tick = idle_cpu(cpu);
 	struct rq *rq = cpu_rq(cpu);
 
 	BUG_ON(!irqs_disabled());
 
 	update_cpu_clock(p, rq, now);
 
-	if (p == rq->idle)
+	if (idle_at_tick)
 		/* Task on the idle queue */
 		wake_priority_sleeper(rq);
 	else
 		task_running_tick(rq, p);
 #ifdef CONFIG_SMP
 	update_load(rq);
+	rq->idle_at_tick = idle_at_tick;
 	if (time_after_eq(jiffies, rq->next_balance))
 		raise_softirq(SCHED_SOFTIRQ);
 #endif
#13 lore raw

PATCH 2/2 sched: dynticks idle load balancing - v2

Changes since v1:

- Move the idle load balancer selection from schedule() to the first busy scheduler_tick() after restarting the tick. This will avoid the unnecessay ownership changes when softirq's(which are run in softirqd context in certain -rt configurations) like timer, sched are invoked for every idle tick that happens.

- Misc cleanups.

---
Fix the process idle load balancing in the presence of dynticks. cpus for which ticks are stopped will sleep till the next event wakes it up. Potentially these sleeps can be for large durations and during which today, there is no periodic idle load balancing being done.

This patch nominates an owner among the idle cpus, which does the idle load balancing on behalf of the other idle cpus. And once all the cpus are completely idle, then we can stop this idle load balancing too. Checks added in fast path are minimized. Whenever there are busy cpus in the system, there will be an owner(idle cpu) doing the system wide idle load balancing.

Open items:
1. Intelligent owner selection (like an idle core in a busy package).
2. Merge with rcu's nohz_cpu_mask?

---

include/linux/sched.h +8 -0
diff -pNru linux-2.6.20.x86_64/include/linux/sched.h linux/include/linux/sched.h
@@ -237,6 +237,14 @@ extern void sched_init_smp(void);
 extern void init_idle(struct task_struct *idle, int cpu);
 
 extern cpumask_t nohz_cpu_mask;
+#if defined(CONFIG_SMP) && defined(CONFIG_NO_HZ)
+extern int select_nohz_load_balancer(int cpu);
+#else
+static inline int select_nohz_load_balancer(int cpu)
+{
+	return 0;
+}
+#endif
 
 /*
  * Only dump TASK_* tasks. (-1 for all tasks)
kernel/sched.c +180 -8

240 lines not on this page · raw message

kernel/time/tick-sched.c +6 -0
diff -pNru linux-2.6.20.x86_64/kernel/time/tick-sched.c linux/kernel/time/tick-sched.c
@@ -241,6 +241,11 @@ void tick_nohz_stop_sched_tick(void)
 		 * the scheduler tick in nohz_restart_sched_tick.
 		 */
 		if (!ts->tick_stopped) {
+			if (select_nohz_load_balancer(1)) {
+				cpu_clear(cpu, nohz_cpu_mask);
+				goto out;
+			}
+
 			ts->idle_tick = ts->sched_timer.expires;
 			ts->tick_stopped = 1;
 			ts->idle_jiffies = last_jiffies;
@@ -297,6 +302,7 @@ void tick_nohz_restart_sched_tick(void)
 	now = ktime_get();
 
 	local_irq_disable();
+	select_nohz_load_balancer(0);
 	tick_do_update_jiffies64(now);
 	cpu_clear(cpu, nohz_cpu_mask);
 
#14 lore raw

Re: [patch 2/2] sched: dynticks idle load balancing - v2

Quoted 23 lines · Suresh B

Changes since v1:

- Move the idle load balancer selection from schedule() to the first busy scheduler_tick() after restarting the tick. This will avoid the unnecessay ownership changes when softirq's(which are run in softirqd context in certain -rt configurations) like timer, sched are invoked for every idle tick that happens.

- Misc cleanups.

---
Fix the process idle load balancing in the presence of dynticks. cpus for which ticks are stopped will sleep till the next event wakes it up. Potentially these sleeps can be for large durations and during which today, there is no periodic idle load balancing being done.

This patch nominates an owner among the idle cpus, which does the idle load balancing on behalf of the other idle cpus. And once all the cpus are completely idle, then we can stop this idle load balancing too. Checks added in fast path are minimized. Whenever there are busy cpus in the system, there will be an owner(idle cpu) doing the system wide idle load balancing.

Quoted 4 lines

Open items:
1. Intelligent owner selection (like an idle core in a busy package).
2. Merge with rcu's nohz_cpu_mask?

I spose I'll hold my nose and merge this, but it creates too much of a mess to be mergeable into the CPU scheduler, IMO.

Can we please do something to reduce the ifdef density? And if possible, all the newly-added returns-from-the-middle-of-a-function?

Quoted 32 lines
kernel/sched.c +32 -0
+#ifdef CONFIG_NO_HZ
+static struct {
+	int load_balancer;
+	cpumask_t  cpu_mask;
+} nohz ____cacheline_aligned = {
+	.load_balancer = -1,
+	.cpu_mask = CPU_MASK_NONE,
+};
+
+/*
+ * This routine will try to nominate the ilb (idle load balancing)
+ * owner among the cpus whose ticks are stopped. ilb owner will do the idle
+ * load balancing on behalf of all those cpus. If all the cpus in the system
+ * go into this tickless mode, then there will be no ilb owner (as there is
+ * no need for one) and all the cpus will sleep till the next wakeup event
+ * arrives...
+ *
+ * For the ilb owner, tick is not stopped. And this tick will be used
+ * for idle load balancing. ilb owner will still be part of
+ * nohz.cpu_mask..
+ *
+ * While stopping the tick, this cpu will become the ilb owner if there
+ * is no other owner. And will be the owner till that cpu becomes busy
+ * or if all cpus in the system stop their ticks at which point
+ * there is no need for ilb owner.
+ *
+ * When the ilb owner becomes busy, it nominates another owner, during the
+ * next busy scheduler_tick()
+ */
+int select_nohz_load_balancer(int stop_tick)
+{
+	int cpu = smp_processor_id();

kernel/sched.c static void update_load(struct rq *this_ · line 3396

Quoted 10 lines
kernel/sched.c +10 -0
+
+	if (stop_tick) {
+		cpu_set(cpu, nohz.cpu_mask);
+		cpu_rq(cpu)->in_nohz_recently = 1;
+
+		/*
+		 * If we are going offline and still the leader, give up!
+		 */
+		if (cpu_is_offline(cpu) && nohz.load_balancer == cpu) {
+			if (cmpxchg(&nohz.load_balancer,  cpu, -1) != cpu)

So we require that architectures which implement CONFIG_NO_HZ also implement cmpxchg.

Quoted 35 lines
kernel/sched.c +31 -0
+				BUG();
+			return 0;
+		}
+
+		/* time for ilb owner also to sleep */
+		if (cpus_weight(nohz.cpu_mask) == num_online_cpus()) {
+			if (nohz.load_balancer == cpu)
+				nohz.load_balancer = -1;
+			return 0;
+		}
+
+		if (nohz.load_balancer == -1) {
+			/* make me the ilb owner */
+			if (cmpxchg(&nohz.load_balancer, -1, cpu) == -1)
+				return 1;
+		} else if (nohz.load_balancer == cpu)
+			return 1;
+	} else {
+		if (!cpu_isset(cpu, nohz.cpu_mask))
+			return 0;
+
+		cpu_clear(cpu, nohz.cpu_mask);
+
+		if (nohz.load_balancer == cpu)
+			if (cmpxchg(&nohz.load_balancer,  cpu, -1) != cpu)
+				BUG();
+	}
+	return 0;
+}
+#endif
+
 /*
  * run_rebalance_domains is triggered when needed from the scheduler tick.
  *

kernel/sched.c static DEFINE_SPINLOCK(balancing); · line 3442

Quoted 9 lines
kernel/sched.c +3 -3
@@ -3347,15 +3437,46 @@ static DEFINE_SPINLOCK(balancing);
 
 static void run_rebalance_domains(struct softirq_action *h)
 {
-	int this_cpu = smp_processor_id(), balance = 1;
-	struct rq *this_rq = cpu_rq(this_cpu);
-	unsigned long interval;
+	int balance_cpu = smp_processor_id(), balance;
+	struct rq *balance_rq = cpu_rq(balance_cpu);
+	unsigned long interval, next_balance;

One definition per line is preferred.

Quoted 21 lines
kernel/sched.c +19 -1
 	struct sched_domain *sd;
-	enum idle_type idle = this_rq->idle_at_tick ? SCHED_IDLE : NOT_IDLE;
+	enum idle_type idle;
+
+#ifdef CONFIG_NO_HZ
+	cpumask_t cpus = nohz.cpu_mask;
+	int local_cpu = balance_cpu;
+	struct rq *local_rq = balance_rq;
+
+restart:
+
+	if (local_rq->idle_at_tick && nohz.load_balancer == local_cpu) {
+		if (need_resched())
+			return;
+
+		balance_cpu = first_cpu(cpus);
+		if (unlikely(balance_cpu >= NR_CPUS))
+			return;
+		balance_rq = cpu_rq(balance_cpu);
+		cpu_clear(balance_cpu, cpus);
+	}

kernel/sched.c static DEFINE_SPINLOCK(balancing); · line 3472

Quoted 10 lines
kernel/sched.c +10 -0
+
+	/*
+	 * We must be doing idle load balancing for some other idle cpu
+	 */
+	if (local_cpu != balance_cpu)
+		idle = SCHED_IDLE;
+	else
+#endif
+		idle = balance_rq->idle_at_tick ? SCHED_IDLE : NOT_IDLE;
+

It's not just that this is an eyesore (it is) - it introduces some ongoing maintenance problems. I expect this can be pulled out into a separate function with no loss in quality of generated code.

And that function would be a nice site for a nice comment explaining the design. Why do we return if need_resched()? What is the significance of (balance_cpu >= NR_CPUS)?

Quoted 26 lines
kernel/sched.c +6 -4
+
 	/* Earliest time when we have to call run_rebalance_domains again */
-	unsigned long next_balance = jiffies + 60*HZ;
+	next_balance = jiffies + 60*HZ;
+
+	for_each_domain(balance_cpu, sd) {
 
-	for_each_domain(this_cpu, sd) {
 		if (!(sd->flags & SD_LOAD_BALANCE))
 			continue;
 
@@ -3374,7 +3495,7 @@ static void run_rebalance_domains(struct
 		}
 
 		if (time_after_eq(jiffies, sd->last_balance + interval)) {
-			if (load_balance(this_cpu, this_rq, sd, idle, &balance)) {
+			if (load_balance(balance_cpu, balance_rq, sd, idle, &balance)) {
 				/*
 				 * We've pulled tasks over so either we're no
 				 * longer idle, or one of our SMT siblings is
@@ -3398,7 +3519,16 @@ out:
 		if (!balance)
 			break;
 	}
-	this_rq->next_balance = next_balance;
+	balance_rq->next_balance = next_balance;

kernel/sched.c out: · line 3532

Quoted 10 lines
kernel/sched.c +9 -0
+
+#ifdef CONFIG_NO_HZ
+	if (local_rq->idle_at_tick && nohz.load_balancer == local_cpu) {
+		if (time_after(next_balance, local_rq->next_balance))
+			local_rq->next_balance = next_balance;
+	    	if (!cpus_empty(cpus))
+			goto restart;
+	}
+#endif
 }

A goto in an ifdef :(

Perhaps it can be removed by teaching the caller to call this function again?

#15 lore raw

Re: [patch 2/2] sched: dynticks idle load balancing - v2

Quoted 18 lines · Andrew Morton

On Fri, 16 Feb 2007 18:08:42 -0800

kernel/sched.c static void update_load(struct rq *this_ · line 3396

Quoted 13 lines
kernel/sched.c +13 -0
+int select_nohz_load_balancer(int stop_tick)
+{
+	int cpu = smp_processor_id();
+
+	if (stop_tick) {
+		cpu_set(cpu, nohz.cpu_mask);
+		cpu_rq(cpu)->in_nohz_recently = 1;
+
+		/*
+		 * If we are going offline and still the leader, give up!
+		 */
+		if (cpu_is_offline(cpu) && nohz.load_balancer == cpu) {
+			if (cmpxchg(&nohz.load_balancer,  cpu, -1) != cpu)

So we require that architectures which implement CONFIG_NO_HZ also implement cmpxchg.

Just use atomic_cmpxchg, please.

#16 lore raw

PATCH 1/1 sched: dynticks idle load balancing - v3

In reply to Andrew Morton
Quoted 2 lines · Andrew Morton

I spose I'll hold my nose and merge this, but it creates too much of a mess to be mergeable into the CPU scheduler, IMO.

Cleaned up patch appended. Please drop sched-dynticks-idle-load-balancing-v2.patch and include this instead.

thanks,
suresh
---

Fix the process idle load balancing in the presence of dynticks. cpus for which ticks are stopped will sleep till the next event wakes it up. Potentially these sleeps can be for large durations and during which today, there is no periodic idle load balancing being done.

This patch nominates an owner among the idle cpus, which does the idle load balancing on behalf of the other idle cpus. And once all the cpus are completely idle, then we can stop this idle load balancing too. Checks added in fast path are minimized. Whenever there are busy cpus in the system, there will be an owner(idle cpu) doing the system wide idle load balancing.

Open items:
1. Intelligent owner selection (like an idle core in a busy package).
2. Merge with rcu's nohz_cpu_mask?

---

include/linux/sched.h +8 -0
diff -pNru linus-2.6/include/linux/sched.h linux/include/linux/sched.h
@@ -194,6 +194,14 @@ extern void sched_init_smp(void);
 extern void init_idle(struct task_struct *idle, int cpu);
 
 extern cpumask_t nohz_cpu_mask;
+#if defined(CONFIG_SMP) && defined(CONFIG_NO_HZ)
+extern int select_nohz_load_balancer(int cpu);
+#else
+static inline int select_nohz_load_balancer(int cpu)
+{
+	return 0;
+}
+#endif
 
 /*
  * Only dump TASK_* tasks. (-1 for all tasks)
kernel/sched.c +211 -13

284 lines not on this page · raw message

kernel/time/tick-sched.c +9 -0
diff -pNru linus-2.6/kernel/time/tick-sched.c linux/kernel/time/tick-sched.c
@@ -215,6 +215,14 @@ void tick_nohz_stop_sched_tick(void)
 		 * the scheduler tick in nohz_restart_sched_tick.
 		 */
 		if (!ts->tick_stopped) {
+			if (select_nohz_load_balancer(1)) {
+				/*
+				 * sched tick not stopped!
+				 */
+				cpu_clear(cpu, nohz_cpu_mask);
+				goto out;
+			}
+
 			ts->idle_tick = ts->sched_timer.expires;
 			ts->tick_stopped = 1;
 			ts->idle_jiffies = last_jiffies;
@@ -271,6 +279,7 @@ void tick_nohz_restart_sched_tick(void)
 	now = ktime_get();
 
 	local_irq_disable();
+	select_nohz_load_balancer(0);
 	tick_do_update_jiffies64(now);
 	cpu_clear(cpu, nohz_cpu_mask);
 
#17 lore raw

Re: [patch 2/2] sched: dynticks idle load balancing - v2

In reply to Siddha, Suresh B
Quoted 17 lines · Suresh B

Changes since v1:

- Move the idle load balancer selection from schedule() to the first busy scheduler_tick() after restarting the tick. This will avoid the unnecessay ownership changes when softirq's(which are run in softirqd context in certain -rt configurations) like timer, sched are invoked for every idle tick that happens.

- Misc cleanups.

---
Fix the process idle load balancing in the presence of dynticks. cpus for which ticks are stopped will sleep till the next event wakes it up. Potentially these sleeps can be for large durations and during which today, there is no periodic idle load balancing being done.

Quoted 5 lines

This patch nominates an owner among the idle cpus, which does the idle load balancing on behalf of the other idle cpus. And once all the cpus are completely idle, then we can stop this idle load balancing too. Checks added in fast path are minimized. Whenever there are busy cpus in the system, there will be an owner(idle cpu) doing the system wide idle load balancing.

This is really ugly, sorry :(

My suggestion for handling this was to increase the maximum balance interval for an idle CPU, and just implement a global shutdown when the entire system goes idle.

The former should take care of the power savings issues for bare metal hardware, and the latter should solve performance problems for many idle SMP guests. It should take very little code to implement.

If that approach doesn't cut it, then at least we can have some numbers to see how much better yours is so we can justify including it.

If you are against my approach, then I can have a try at coding it up if you like?

#18 lore raw

Re: [patch 2/2] sched: dynticks idle load balancing - v2

Quoted 1 line · Nick Piggin

This is really ugly, sorry :(

hm. myself and others too thought it was a simple and nice idea.

Quoted 7 lines

My suggestion for handling this was to increase the maximum balance interval for an idle CPU, and just implement a global shutdown when the entire system goes idle.

The former should take care of the power savings issues for bare metal hardware, and the latter should solve performance problems for many idle SMP guests. It should take very little code to implement.

coming to max balance interval will be challenging. It needs to save power and at the same time respond to load changes fast enough.

Quoted 5 lines

If that approach doesn't cut it, then at least we can have some numbers to see how much better yours is so we can justify including it.

If you are against my approach, then I can have a try at coding it up if you like?

Sure. If you can provide a patch, I will be glad to provide power and performance comparision numbers with both the approaches.

thanks,
suresh

#19 lore raw

Re: [patch 2/2] sched: dynticks idle load balancing - v2

Quoted 4 lines · Suresh B
Quoted 1 line · Nick Piggin

This is really ugly, sorry :(

hm. myself and others too thought it was a simple and nice idea.

The idea is not bad. I won't guarantee mine will be as good or better, but I think it is sensible to try implementing the simplest approach first, so we can get a baseline to justify more complexity against...

Your code just needs work, but if it really produces good results then it should be able to be made into a mergeable patch.

Quoted 10 lines
Quoted 7 lines

My suggestion for handling this was to increase the maximum balance interval for an idle CPU, and just implement a global shutdown when the entire system goes idle.

The former should take care of the power savings issues for bare metal hardware, and the latter should solve performance problems for many idle SMP guests. It should take very little code to implement.

coming to max balance interval will be challenging. It needs to save power and at the same time respond to load changes fast enough.

Yep.

Quoted 8 lines
Quoted 5 lines

If that approach doesn't cut it, then at least we can have some numbers to see how much better yours is so we can justify including it.

If you are against my approach, then I can have a try at coding it up if you like?

Sure. If you can provide a patch, I will be glad to provide power and performance comparision numbers with both the approaches.

OK that would be good. I'll see if I can code something up by next week.

Thanks,
Nick

#20 lore raw

Re: [patch 1/2] sched: fix idle load balancing in softirqd context

In reply to Siddha, Suresh B
Quoted 7 lines · Suresh B

Periodic load balancing in recent kernels happen in the softirq. In certain -rt configurations, these softirqs are handled in softirqd context. And hence the check for idle processor was always returning busy (as nr_running > 1).

This patch captures the idle information at the tick and passes this info to softirq context through an element 'idle_at_tick' in rq.

I haven't had the time yet to look too detailed at this patch.

kernel/sched.c void scheduler_tick(void) · line 3651

Quoted 12 lines

---

{

kernel/sched.c +1 -1
 	unsigned long long now = sched_clock();
 	struct task_struct *p = current;
-	int cpu = smp_processor_id();
+	int cpu = smp_processor_id(), idle_at_tick = idle_cpu(cpu);
 	struct rq *rq = cpu_rq(cpu);

But I would recommend that the idle_at_tick should be on a separate line.

I'll try to look deeper at your patches tomorrow. I've also found that I'm having some latency problems in -rt that I think might be related to migration.

-- Steve

#21 lore raw

Re: [patch 1/2] sched: fix idle load balancing in softirqd context

Quoted 7 lines · Steven Rostedt

kernel/sched.c void scheduler_tick(void) · line 3651

Quoted 4 lines · Suresh B
kernel/sched.c +1 -1
-	int cpu = smp_processor_id();
+	int cpu = smp_processor_id(), idle_at_tick = idle_cpu(cpu);
 	struct rq *rq = cpu_rq(cpu);

But I would recommend that the idle_at_tick should be on a separate line.

Ok.

Quoted 3 lines

I'll try to look deeper at your patches tomorrow. I've also found that I'm having some latency problems in -rt that I think might be related to migration.

There is one more issue, I have observed in -rt tree.

raise_softirq_irqoff() is unconditionally doing the wakeup_softirqd() But unless the CONFIG_PREEMPT_SOFTIRQS is configured, do_softirq() will process the softirq's like TIMER_SOFTIRQ and SCHED_SOFTIRQ in the process context. So it looks like we are unnecessarily waking the softirqd's corresponding to those softirq's.

thanks,
suresh

#22 lore raw

Re: [patch 1/2] sched: fix idle load balancing in softirqd context

In reply to Siddha, Suresh B

kernel/sched.c void scheduler_tick(void) · line 3650

Quoted 1 line · Suresh B
kernel/sched.c +1 -0
+	int cpu = smp_processor_id(), idle_at_tick = idle_cpu(cpu);

argh. Please, do

	int cpu = smp_processor_id();
	int idle_at_tick = idle_cpu(cpu);
#23 lore raw
In reply to Ingo Molnar
Quoted 1 line · Ingo Molnar

The easiest fix for this is to use trylock - find the patch for that.

FYI, i have released 2.6.19-rt14 with your patch integrated into it as well - it's looking good so far in my testing. (the yum repository will be updated in a few minutes.)

Ingo

#24 lore raw
In reply to Siddha, Suresh B
Quoted 3 lines · Suresh B

Comments and review feedback welcome. Minimal testing done on couple of i386 platforms. Perf testing yet to be done.

Nice work!

Quoted 10 lines

thanks,
suresh
---

diff -pNru linux-2.6.19-mm1/include/linux/sched.h linux/include/linux/sched.h

include/linux/sched.h extern void sched_init_smp(void); · line 201

Quoted 7 lines
include/linux/sched.h +4 -0
@@ -195,6 +195,14 @@ extern void sched_init_smp(void);
 extern void init_idle(struct task_struct *idle, int cpu);
 
 extern cpumask_t nohz_cpu_mask;
+#ifdef CONFIG_SMP
+extern int select_notick_load_balancer(int cpu);
+#else
+static inline int select_notick_load_balancer(int cpu)

Later on in the actual code, the parameter is named stop_tick, which makes sense. You should change the name here too so it's not confusing when looking later on at the code.

Quoted 4 lines
include/linux/sched.h +4 -0
+{
+	return 0;
+}
+#endif

[...]

Quoted 25 lines
include/linux/sched.h +25 -0
+
+/*
+ * This routine will try to nominate the ilb (idle load balancing)
+ * owner among the cpus whose ticks are stopped. ilb owner will do the idle
+ * load balancing on behalf of all those cpus. If all the cpus in the system
+ * go into this tickless mode, then there will be no ilb owner (as there is
+ * no need for one) and all the cpus will sleep till the next wakeup event
+ * arrives...
+ *
+ * For the ilb owner, tick is not stopped. And this tick will be used
+ * for idle load balancing. ilb owner will still be part of
+ * notick.cpu_mask..
+ *
+ * While stopping the tick, this cpu will become the ilb owner if there
+ * is no other owner. And will be the owner till that cpu becomes busy
+ * or if all cpus in the system stop their ticks at which point
+ * there is no need for ilb owner.
+ *
+ * When the ilb owner becomes busy, it nominates another owner, during the
+ * schedule()
+ */
+int select_notick_load_balancer(int stop_tick)
+{
+	int cpu = smp_processor_id();
+

[...]

include/linux/sched.h switch_tasks: · line 3672

Quoted 13 lines
include/linux/sched.h +6 -0
+#ifdef CONFIG_NO_HZ
+	if (idle_cpu(local_cpu) && notick.load_balancer == local_cpu &&
+	    !cpus_empty(cpus))
+		goto restart;
+#endif
 }
 #else
 /*
@@ -3562,6 +3669,21 @@ switch_tasks:
 		++*switch_count;
 
 		prepare_task_switch(rq, next);
+#if defined(CONFIG_HZ) && defined(CONFIG_SMP)

Ah! so this is where the CONFIG_NO_HZ mistake came in ;)

Quoted 5 lines
include/linux/sched.h +5 -0
+		if (prev == rq->idle && notick.load_balancer == -1) {
+			/*
+			 * simple selection for now: Nominate the first cpu in
+			 * the notick list to be the next ilb owner.
+			 *

include/linux/sched.h switch_tasks: · line 3687

Quoted 10 lines
include/linux/sched.h +9 -0
+			 * TBD: Traverse the sched domains and nominate
+			 * the nearest cpu in the notick.cpu_mask.
+			 */
+			int ilb = first_cpu(notick.cpu_mask);
+
+			if (ilb != NR_CPUS)
+				resched_cpu(ilb);
+		}
+#endif
 		prev = context_switch(rq, prev, next);

-- Steve