Skip to contentSkip to conversation

sched: change nohz idle load balancing logic to push model

PATCH In review Suresh Siddha 9 participants 28 messages May 17, 2010 – Jun 9, 2010

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

cover sched: change nohz idle load balancing logic to push model

This is an updated version of patchset which is posted earlier at
http://lkml.org/lkml/2009/12/10/470

Description:
Existing nohz idle load balance logic uses the pull model, with one idle load balancer CPU nominated on any partially idle system and that balancer CPU not going into nohz mode. With the periodic tick, the balancer does the idle balancing on behalf of all the CPUs in nohz mode.

This is not very optimal and has few issues:
* the balancer will continue to have periodic ticks and wakeup frequently (HZ rate), even though it may not have any rebalancing to do on behalf of any of the idle CPUs.
* On x86 and CPUs that have APIC timer stoppage on idle CPUs, this periodic wakeup can result in an additional interrupt on a CPU doing the timer broadcast.

The alternative is to have a push model, where all idle CPUs can enter nohz mode and any busy CPU kicks one of the idle CPUs to take care of idle balancing on behalf of a group of idle CPUs.

Following patches switches idle load balancer to this push approach.

Updates from the previous version:

* Busy CPU uses send_remote_softirq() for invoking SCHED_SOFTIRQ on the idle load balancing cpu, which does the load balancing on behalf of all the idle CPUs.

* Dropped the per NUMA node nohz load balancing as it doesn't detect certain imbalance scenarios. This will be addressed later.

#1 lore raw

PATCH 1/7 softirq: Add a no local fallback option to send_remote_softirq

From: Venkatesh Pallipadi <[email protected]>
Subject: softirq: Add a no local fallback option to send_remote_softirq send_remote_softirq and __send_remote_softirq fallback to triggering the softirq on local CPU when __try_remote_softirq fails. In certain circumstances (like the SCHED_SOFTIRQ usage in following patch), the softirq should only run on target CPUs if it runs. This new option helps such callers.

As there seem to be no current users of send_remote_softirq in tree today, added this option to current API instead of introducing a new API.

---
 include/linux/interrupt.h |    5 +++--
 kernel/softirq.c          |   12 ++++++++----
 2 files changed, 11 insertions(+), 6 deletions(-)
include/linux/interrupt.h +3 -2
Index: tip/include/linux/interrupt.h
===================================================================
@@ -419,13 +419,14 @@ DECLARE_PER_CPU(struct list_head [NR_SOF
 /* Try to send a softirq to a remote cpu.  If this cannot be done, the
  * work will be queued to the local cpu.
  */
-extern void send_remote_softirq(struct call_single_data *cp, int cpu, int softirq);
+extern void send_remote_softirq(struct call_single_data *cp, int cpu,
+				int softirq, int fallback);
 
 /* Like send_remote_softirq(), but the caller must disable local cpu interrupts
  * and compute the current cpu, passed in as 'this_cpu'.
  */
 extern void __send_remote_softirq(struct call_single_data *cp, int cpu,
-				  int this_cpu, int softirq);
+				  int this_cpu, int softirq, int fallback);
 
 /* Tasklets --- multithreaded analogue of BHs.
 
kernel/softirq.c +8 -4
Index: tip/kernel/softirq.c
===================================================================
@@ -610,9 +610,12 @@ static int __try_remote_softirq(struct c
  *
  * Interrupts must be disabled.
  */
-void __send_remote_softirq(struct call_single_data *cp, int cpu, int this_cpu, int softirq)
+void __send_remote_softirq(struct call_single_data *cp, int cpu, int this_cpu,
+			   int softirq, int fallback)
 {
-	if (cpu == this_cpu || __try_remote_softirq(cp, cpu, softirq))
+	if (cpu == this_cpu)
+		__local_trigger(cp, softirq);
+	else if (__try_remote_softirq(cp, cpu, softirq) && fallback)
 		__local_trigger(cp, softirq);
 }
 EXPORT_SYMBOL(__send_remote_softirq);
@@ -626,14 +629,15 @@ EXPORT_SYMBOL(__send_remote_softirq);
  * Like __send_remote_softirq except that disabling interrupts and
  * computing the current cpu is done for the caller.
  */
-void send_remote_softirq(struct call_single_data *cp, int cpu, int softirq)
+void send_remote_softirq(struct call_single_data *cp, int cpu, int softirq,
+			 int fallback)
 {
 	unsigned long flags;
 	int this_cpu;
 
 	local_irq_save(flags);
 	this_cpu = smp_processor_id();
-	__send_remote_softirq(cp, cpu, this_cpu, softirq);
+	__send_remote_softirq(cp, cpu, this_cpu, softirq, fallback);
 	local_irq_restore(flags);
 }
 EXPORT_SYMBOL(send_remote_softirq);
#2 lore raw

PATCH 2/7 softirq: add init_remote_softirq_csd()

In reply to Suresh Siddha

Currently send_remote_softirq() API's don't allow single call_single_data struct(like per cpu call_single_data) to be used with multiple send_remote_softirq() calls in parallel (as each of the send_remote_softirq() call reinitializes the call_single_data overwriting the inflight usage.

Add a new init_remote_softirq_csd() which will init the call_single_data. Second send_remote_softirq() from the same cpu will now wait on the csd_lock() if the prior send_remote_softirq() is not complete.

Cc David S. Miller <[email protected]>
Cc Jens Axboe <[email protected]>
---
 include/linux/interrupt.h |    8 ++++++--
 kernel/softirq.c          |   41 +++++++++++++++++++++++++++--------------
 2 files changed, 33 insertions(+), 16 deletions(-)
kernel/softirq.c +27 -14
Index: tip/kernel/softirq.c
===================================================================
@@ -578,24 +578,23 @@ static void remote_softirq_receive(void 
 	local_irq_restore(flags);
 }
 
-static int __try_remote_softirq(struct call_single_data *cp, int cpu, int softirq)
+static int __try_remote_softirq(struct call_single_data *cp, int cpu)
 {
 	if (cpu_online(cpu)) {
-		cp->func = remote_softirq_receive;
-		cp->info = cp;
-		cp->flags = 0;
-		cp->priv = softirq;
-
 		__smp_call_function_single(cpu, cp, 0);
 		return 0;
 	}
 	return 1;
 }
 #else /* CONFIG_USE_GENERIC_SMP_HELPERS */
-static int __try_remote_softirq(struct call_single_data *cp, int cpu, int softirq)
+static int __try_remote_softirq(struct call_single_data *cp, int cpu)
 {
 	return 1;
 }
+static void remote_softirq_receive(void *data)
+{
+	return;
+}
 #endif
 
 /**
@@ -611,12 +610,12 @@ static int __try_remote_softirq(struct c
  * Interrupts must be disabled.
  */
 void __send_remote_softirq(struct call_single_data *cp, int cpu, int this_cpu,
-			   int softirq, int fallback)
+			   int fallback)
 {
 	if (cpu == this_cpu)
-		__local_trigger(cp, softirq);
-	else if (__try_remote_softirq(cp, cpu, softirq) && fallback)
-		__local_trigger(cp, softirq);
+		__local_trigger(cp, cp->priv);
+	else if (__try_remote_softirq(cp, cpu) && fallback)
+		__local_trigger(cp, cp->priv);
 }
 EXPORT_SYMBOL(__send_remote_softirq);
 
@@ -629,19 +628,33 @@ EXPORT_SYMBOL(__send_remote_softirq);
  * Like __send_remote_softirq except that disabling interrupts and
  * computing the current cpu is done for the caller.
  */
-void send_remote_softirq(struct call_single_data *cp, int cpu, int softirq,
-			 int fallback)
+void send_remote_softirq(struct call_single_data *cp, int cpu, int fallback)
 {
 	unsigned long flags;
 	int this_cpu;
 
 	local_irq_save(flags);
 	this_cpu = smp_processor_id();
-	__send_remote_softirq(cp, cpu, this_cpu, softirq, fallback);
+	__send_remote_softirq(cp, cpu, this_cpu, fallback);
 	local_irq_restore(flags);
 }
 EXPORT_SYMBOL(send_remote_softirq);
 
+/***
+ * init_remote_softirq_csd - initialize the smp_call_function_single()'s
+ * call single data that will be later used by send_remote_softirq()
+ * @cp: private SMP call function data area to be initialized
+ * @softirq: the softirq to be used for the work
+ */
+void init_remote_softirq_csd(struct call_single_data *cp, int softirq)
+{
+	cp->func = remote_softirq_receive;
+	cp->info = cp;
+	cp->flags = 0;
+	cp->priv = softirq;
+}
+EXPORT_SYMBOL(init_remote_softirq_csd);
+
 static int __cpuinit remote_softirq_cpu_notify(struct notifier_block *self,
 					       unsigned long action, void *hcpu)
 {
include/linux/interrupt.h +6 -2
Index: tip/include/linux/interrupt.h
===================================================================
@@ -420,13 +420,17 @@ DECLARE_PER_CPU(struct list_head [NR_SOF
  * work will be queued to the local cpu.
  */
 extern void send_remote_softirq(struct call_single_data *cp, int cpu,
-				int softirq, int fallback);
+				int fallback);
 
 /* Like send_remote_softirq(), but the caller must disable local cpu interrupts
  * and compute the current cpu, passed in as 'this_cpu'.
  */
 extern void __send_remote_softirq(struct call_single_data *cp, int cpu,
-				  int this_cpu, int softirq, int fallback);
+				  int this_cpu, int fallback);
+
+/* Initialize the call_single_data to be later used with send_remote_softirq().
+ */
+extern void init_remote_softirq_csd(struct call_single_data *cp, int softirq);
 
 /* Tasklets --- multithreaded analogue of BHs.
 
#3 lore raw

PATCH 3/7 softirq: avoid softirq_work_list for SCHED_SOFTIRQ when sent remotely

In reply to Suresh Siddha

There is no need to add the SCHED_SOFTIRQ work to the softirq_work_list when sent remotely. This is because any pending work associated with SCHED_SOFTIRQ need not be migrated to a new cpu when the current cpu is going down etc.

Also I am not sure how this softirq_work_list works for other softirqs. I don't see anyone removing the list entries from the softirq_work_list after it is handled on a remote cpu.

For now, just skip it for SCHED_SOFTIRQ.

Cc David S. Miller <[email protected]>
Cc Jens Axboe <[email protected]>
---
 kernel/softirq.c |    5 +++++
 1 file changed, 5 insertions(+)
kernel/softirq.c +5 -0
Index: tip/kernel/softirq.c
===================================================================
@@ -557,6 +557,11 @@ static void __local_trigger(struct call_
 {
 	struct list_head *head = &__get_cpu_var(softirq_work_list[softirq]);
 
+	if (softirq == SCHED_SOFTIRQ) {
+		raise_softirq_irqoff(softirq);
+		return;
+	}
+
 	list_add_tail(&cp->list, head);
 
 	/* Trigger the softirq only if the list was previously empty.  */
maintainer
#4 lore raw

Re: [patch 3/7] softirq: avoid softirq_work_list for SCHED_SOFTIRQ when sent remotely

Quoted 10 lines · Suresh Siddha

plain text document attachment (fix_local_trigger_remote_softirq_for_sched.patch)
There is no need to add the SCHED_SOFTIRQ work to the softirq_work_list when sent remotely. This is because any pending work associated with SCHED_SOFTIRQ need not be migrated to a new cpu when the current cpu is going down etc.

Also I am not sure how this softirq_work_list works for other softirqs. I don't see anyone removing the list entries from the softirq_work_list after it is handled on a remote cpu.

Most odd all that, Dave, Jens, what happened to all that remote_softirq stuff?

#5 lore raw

Re: [patch 3/7] softirq: avoid softirq_work_list for SCHED_SOFTIRQ when sent remotely

From: Peter Zijlstra <[email protected]>
Date: Thu, 20 May 2010 10:12:39 +0200

Quoted 2 lines

Most odd all that, Dave, Jens, what happened to all that remote_softirq stuff?

Nobody ended up using this remote softirq infrastructure, it can be completely deleted.

#6 lore raw

Re: [patch 3/7] softirq: avoid softirq_work_list for SCHED_SOFTIRQ when sent remotely

Quoted 8 lines · David Miller

From: Peter Zijlstra <[email protected]>
Date: Thu, 20 May 2010 10:12:39 +0200

Quoted 2 lines

Most odd all that, Dave, Jens, what happened to all that remote_softirq stuff?

Nobody ended up using this remote softirq infrastructure, it can be completely deleted.

What parts of it? There has been reworks of parts of the code since I added it, the block layer only uses __smp_call_function_single() to trigger remote softirqs.

Signature · 1 line
Jens Axboe
maintainer
#7 lore raw

Re: [patch 3/7] softirq: avoid softirq_work_list for SCHED_SOFTIRQ when sent remotely

Quoted 7 lines · Jens Axboe
Quoted 6 lines · David Miller

From: Peter Zijlstra <[email protected]>
Date: Thu, 20 May 2010 10:12:39 +0200

Quoted 2 lines

Most odd all that, Dave, Jens, what happened to all that remote_softirq stuff?

Quoted 6 lines
Quoted 2 lines

Nobody ended up using this remote softirq infrastructure, it can be completely deleted.

What parts of it? There has been reworks of parts of the code since I added it, the block layer only uses __smp_call_function_single() to trigger remote softirqs.

Right, so __smp_call_function_single() is the normal remote ipi stuff from kernel/smp.c, send_remote_softirq() is the pile of code in kernel/softirq.c that uses that to tickle remote softirqs.

The 'problem' seems to be that the remote softirq code (not the ipi bits) doesn't have any users and is quite complex and apparently incomplete.

Suresh, would it make sense to do as Jens does and simply use __smp_call_function_single() or do you think it still makes sense to have a small wrapper and maybe share that with Jens?

#8 lore raw

Re: [patch 3/7] softirq: avoid softirq_work_list for SCHED_SOFTIRQ when sent remotely

In reply to Jens Axboe

From: Jens Axboe <[email protected]>
Date: Thu, 20 May 2010 10:23:09 +0200

Quoted 7 lines · David Miller
Quoted 6 lines

From: Peter Zijlstra <[email protected]>
Date: Thu, 20 May 2010 10:12:39 +0200

Quoted 2 lines

Most odd all that, Dave, Jens, what happened to all that remote_softirq stuff?

Quoted 6 lines
Quoted 2 lines

Nobody ended up using this remote softirq infrastructure, it can be completely deleted.

What parts of it? There has been reworks of parts of the code since I added it, the block layer only uses __smp_call_function_single() to trigger remote softirqs.

And that's what the networking is using for RPS/RFS too.

#9 lore raw

PATCH 4/7 sched: Change nohz ilb logic from pull to push model

In reply to Suresh Siddha

From: Venkatesh Pallipadi <[email protected]>
Subject: sched: Change nohz ilb logic from pull to push model

In the new push model, all idle CPUs indeed go into nohz mode. There is still the concept of idle load balancer. Busy CPU kicks the nohz balancer when any of the nohz CPUs need idle load balancing. The kickee CPU does the idle load balancing on behalf of all idle CPUs instead of the normal idle balance.

This addresses the below two problems with the current nohz ilb logic:
* the balancer will continue to have periodic ticks and wakeup frequently, even though it may not have any rebalancing to do on behalf of any of the idle CPUs.
* On x86 and CPUs that have APIC timer stoppage on idle CPUs, this periodic wakeup can result in an additional interrupt on a CPU doing the timer broadcast.

---
 kernel/sched.c      |   13 +-
 kernel/sched_fair.c |  283 ++++++++++++++++++++++++++++++----------------------
 2 files changed, 177 insertions(+), 119 deletions(-)
kernel/sched_fair.c +167 -116
Index: tip/kernel/sched_fair.c
===================================================================
@@ -3081,10 +3081,26 @@ out_unlock:
 }
 
 #ifdef CONFIG_NO_HZ
+
+static DEFINE_PER_CPU(struct call_single_data, remote_sched_softirq_cb);
+
+/*
+ * idle load balancing details
+ * - One of the idle CPUs nominates itself as idle load_balancer, while
+ *   entering idle.
+ * - This idle load balancer CPU will also go into tickless mode when
+ *   it is idle, just like all other idle CPUs
+ * - When one of the busy CPUs notice that there may be an idle rebalancing
+ *   needed, they will kick the idle load balancer, which then does idle
+ *   load balancing for all the idle CPUs.
+ */
 static struct {
 	atomic_t load_balancer;
-	cpumask_var_t cpu_mask;
-	cpumask_var_t ilb_grp_nohz_mask;
+	atomic_t first_pick_cpu;
+	atomic_t second_pick_cpu;
+	cpumask_var_t idle_cpus_mask;
+	cpumask_var_t grp_idle_mask;
+	unsigned long next_balance;     /* in jiffy units */
 } nohz ____cacheline_aligned = {
 	.load_balancer = ATOMIC_INIT(-1),
 };
@@ -3141,17 +3157,17 @@ static inline struct sched_domain *lowes
  */
 static inline int is_semi_idle_group(struct sched_group *ilb_group)
 {
-	cpumask_and(nohz.ilb_grp_nohz_mask, nohz.cpu_mask,
+	cpumask_and(nohz.grp_idle_mask, nohz.idle_cpus_mask,
 					sched_group_cpus(ilb_group));
 
 	/*
 	 * A sched_group is semi-idle when it has atleast one busy cpu
 	 * and atleast one idle cpu.
 	 */
-	if (cpumask_empty(nohz.ilb_grp_nohz_mask))
+	if (cpumask_empty(nohz.grp_idle_mask))
 		return 0;
 
-	if (cpumask_equal(nohz.ilb_grp_nohz_mask, sched_group_cpus(ilb_group)))
+	if (cpumask_equal(nohz.grp_idle_mask, sched_group_cpus(ilb_group)))
 		return 0;
 
 	return 1;
@@ -3184,7 +3200,7 @@ static int find_new_ilb(int cpu)
 	 * Optimize for the case when we have no idle CPUs or only one
 	 * idle CPU. Don't walk the sched_domain hierarchy in such cases
 	 */
-	if (cpumask_weight(nohz.cpu_mask) < 2)
+	if (cpumask_weight(nohz.idle_cpus_mask) < 2)
 		goto out_done;
 
 	for_each_flag_domain(cpu, sd, SD_POWERSAVINGS_BALANCE) {
@@ -3192,7 +3208,7 @@ static int find_new_ilb(int cpu)
 
 		do {
 			if (is_semi_idle_group(ilb_group))
-				return cpumask_first(nohz.ilb_grp_nohz_mask);
+				return cpumask_first(nohz.grp_idle_mask);
 
 			ilb_group = ilb_group->next;
 
@@ -3200,42 +3216,61 @@ static int find_new_ilb(int cpu)
 	}
 
 out_done:
-	return cpumask_first(nohz.cpu_mask);
+	return nr_cpu_ids;
 }
 #else /*  (CONFIG_SCHED_MC || CONFIG_SCHED_SMT) */
 static inline int find_new_ilb(int call_cpu)
 {
-	return cpumask_first(nohz.cpu_mask);
+	return nr_cpu_ids;
 }
 #endif
 
 /*
+ * Kick a CPU to do the nohz balancing, if it is time for it. We pick the
+ * nohz_load_balancer CPU (if there is one) otherwise fallback to any idle
+ * CPU (if there is one).
+ */
+static void nohz_balancer_kick(int cpu)
+{
+	int ilb_cpu;
+
+	nohz.next_balance++;
+
+	ilb_cpu = get_nohz_load_balancer();
+	if (ilb_cpu < 0) {
+		ilb_cpu = cpumask_first(nohz.idle_cpus_mask);
+		if (ilb_cpu >= nr_cpu_ids)
+			return;
+	}
+
+	if (!cpu_rq(ilb_cpu)->nohz_balance_kick) {
+		struct call_single_data *cp;
+
+		cpu_rq(ilb_cpu)->nohz_balance_kick = 1;
+		cp = &per_cpu(remote_sched_softirq_cb, cpu);
+		send_remote_softirq(cp, ilb_cpu, 0);
+	}
+	return;
+}
+
+/*
  * 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..
+ * load balancing on behalf of all those cpus.
  *
- * 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()
+ * When the ilb owner becomes busy, we will not have new ilb owner until some
+ * idle CPU wakes up and goes back to idle or some busy CPU tries to kick
+ * idle load balancing by kicking one of the idle CPUs.
+ *
+ * Ticks are stopped for the ilb owner as well, with busy CPU kicking this
+ * ilb owner CPU in future (when there is a need for idle load balancing on
+ * behalf of all idle CPUs).
  */
 int select_nohz_load_balancer(int stop_tick)
 {
 	int cpu = smp_processor_id();
 
 	if (stop_tick) {
-		cpu_rq(cpu)->in_nohz_recently = 1;
-
 		if (!cpu_active(cpu)) {
 			if (atomic_read(&nohz.load_balancer) != cpu)
 				return 0;
@@ -3250,25 +3285,20 @@ int select_nohz_load_balancer(int stop_t
 			return 0;
 		}
 
-		cpumask_set_cpu(cpu, nohz.cpu_mask);
+		cpumask_set_cpu(cpu, nohz.idle_cpus_mask);
 
-		/* time for ilb owner also to sleep */
-		if (cpumask_weight(nohz.cpu_mask) == num_active_cpus()) {
-			if (atomic_read(&nohz.load_balancer) == cpu)
-				atomic_set(&nohz.load_balancer, -1);
-			return 0;
-		}
+		if (atomic_read(&nohz.first_pick_cpu) == cpu)
+			atomic_cmpxchg(&nohz.first_pick_cpu, cpu, nr_cpu_ids);
+		if (atomic_read(&nohz.second_pick_cpu) == cpu)
+			atomic_cmpxchg(&nohz.second_pick_cpu, cpu, nr_cpu_ids);
 
 		if (atomic_read(&nohz.load_balancer) == -1) {
-			/* make me the ilb owner */
-			if (atomic_cmpxchg(&nohz.load_balancer, -1, cpu) == -1)
-				return 1;
-		} else if (atomic_read(&nohz.load_balancer) == cpu) {
 			int new_ilb;
 
-			if (!(sched_smt_power_savings ||
-						sched_mc_power_savings))
-				return 1;
+			/* make me the ilb owner */
+			if (atomic_cmpxchg(&nohz.load_balancer, -1, cpu) != -1)
+				return 0;
+
 			/*
 			 * Check to see if there is a more power-efficient
 			 * ilb.
@@ -3279,13 +3309,13 @@ int select_nohz_load_balancer(int stop_t
 				resched_cpu(new_ilb);
 				return 0;
 			}
-			return 1;
+			return 0;
 		}
 	} else {
-		if (!cpumask_test_cpu(cpu, nohz.cpu_mask))
+		if (!cpumask_test_cpu(cpu, nohz.idle_cpus_mask))
 			return 0;
 
-		cpumask_clear_cpu(cpu, nohz.cpu_mask);
+		cpumask_clear_cpu(cpu, nohz.idle_cpus_mask);
 
 		if (atomic_read(&nohz.load_balancer) == cpu)
 			if (atomic_cmpxchg(&nohz.load_balancer, cpu, -1) != cpu)
@@ -3373,11 +3403,97 @@ out:
 		rq->next_balance = next_balance;
 }
 
+#ifdef CONFIG_NO_HZ
 /*
- * run_rebalance_domains is triggered when needed from the scheduler tick.
- * In CONFIG_NO_HZ case, the idle load balance owner will do the
+ * In CONFIG_NO_HZ case, the idle balance kickee will do the
  * rebalancing for all the cpus for whom scheduler ticks are stopped.
  */
+static void nohz_idle_balance(int this_cpu, enum cpu_idle_type idle)
+{
+	struct rq *this_rq = cpu_rq(this_cpu);
+	struct rq *rq;
+	int balance_cpu;
+
+	if (idle != CPU_IDLE || !this_rq->nohz_balance_kick)
+		return;
+
+	for_each_cpu(balance_cpu, nohz.idle_cpus_mask) {
+		if (balance_cpu == this_cpu)
+			continue;
+
+		/*
+		 * If this cpu gets work to do, stop the load balancing
+		 * work being done for other cpus. Next load
+		 * balancing owner will pick it up.
+		 */
+		if (need_resched()) {
+			this_rq->nohz_balance_kick = 0;
+			break;
+		}
+
+		rebalance_domains(balance_cpu, CPU_IDLE);
+
+		rq = cpu_rq(balance_cpu);
+		if (time_after(this_rq->next_balance, rq->next_balance))
+			this_rq->next_balance = rq->next_balance;
+	}
+	nohz.next_balance = this_rq->next_balance;
+	this_rq->nohz_balance_kick = 0;
+}
+
+/*
+ * Current heuristic for kicking the idle load balancer
+ * - first_pick_cpu is the one of the busy CPUs. It will kick
+ *   idle load balancer when it has more than one process active. This
+ *   eliminates the need for idle load balancing altogether when we have
+ *   only one running process in the system (common case).
+ * - If there are more than one busy CPU, idle load balancer may have
+ *   to run for active_load_balance to happen (i.e., two busy CPUs are
+ *   SMT or core siblings and can run better if they move to different
+ *   physical CPUs). So, second_pick_cpu is the second of the busy CPUs
+ *   which will kick idle load balancer as soon as it has any load.
+ */
+static inline int nohz_kick_needed(struct rq *rq, int cpu)
+{
+	unsigned long now = jiffies;
+	int ret;
+	int first_pick_cpu, second_pick_cpu;
+
+	if (time_before(now, nohz.next_balance))
+		return 0;
+
+	if (!rq->nr_running)
+		return 0;
+
+	first_pick_cpu = atomic_read(&nohz.first_pick_cpu);
+	second_pick_cpu = atomic_read(&nohz.second_pick_cpu);
+
+	if (first_pick_cpu < nr_cpu_ids && first_pick_cpu != cpu &&
+	    second_pick_cpu < nr_cpu_ids && second_pick_cpu != cpu)
+		return 0;
+
+	ret = atomic_cmpxchg(&nohz.first_pick_cpu, nr_cpu_ids, cpu);
+	if (ret == nr_cpu_ids || ret == cpu) {
+		atomic_cmpxchg(&nohz.second_pick_cpu, cpu, nr_cpu_ids);
+		if (rq->nr_running > 1)
+			return 1;
+	} else {
+		ret = atomic_cmpxchg(&nohz.second_pick_cpu, nr_cpu_ids, cpu);
+		if (ret == nr_cpu_ids || ret == cpu) {
+			if (rq->nr_running)
+				return 1;
+		}
+	}
+	return 0;
+}
+#else
+static void nohz_idle_balance(int this_cpu, enum cpu_idle_type idle) { }
+#endif
+
+/*
+ * run_rebalance_domains is triggered when needed from the scheduler tick.
+ * Also triggered for nohz idle balancing (with nohz_balancing_kick set).
+ */
 static void run_rebalance_domains(struct softirq_action *h)
 {
 	int this_cpu = smp_processor_id();
@@ -3387,37 +3503,12 @@ static void run_rebalance_domains(struct
 
 	rebalance_domains(this_cpu, idle);
 
-#ifdef CONFIG_NO_HZ
 	/*
-	 * If this cpu is the owner for idle load balancing, then do the
+	 * If this cpu has a pending nohz_balance_kick, then do the
 	 * balancing on behalf of the other idle cpus whose ticks are
 	 * stopped.
 	 */
-	if (this_rq->idle_at_tick &&
-	    atomic_read(&nohz.load_balancer) == this_cpu) {
-		struct rq *rq;
-		int balance_cpu;
-
-		for_each_cpu(balance_cpu, nohz.cpu_mask) {
-			if (balance_cpu == this_cpu)
-				continue;
-
-			/*
-			 * If this cpu gets work to do, stop the load balancing
-			 * work being done for other cpus. Next load
-			 * balancing owner will pick it up.
-			 */
-			if (need_resched())
-				break;
-
-			rebalance_domains(balance_cpu, CPU_IDLE);
-
-			rq = cpu_rq(balance_cpu);
-			if (time_after(this_rq->next_balance, rq->next_balance))
-				this_rq->next_balance = rq->next_balance;
-		}
-	}
-#endif
+	nohz_idle_balance(this_cpu, idle);
 }
 
 static inline int on_null_domain(int cpu)
@@ -3427,57 +3518,17 @@ static inline int on_null_domain(int cpu
 
 /*
  * Trigger the SCHED_SOFTIRQ if it is time to do periodic load balancing.
- *
- * In case of CONFIG_NO_HZ, this is the place where we nominate a new
- * idle load balancing owner or decide to stop the periodic load balancing,
- * if the whole system is idle.
  */
 static inline void trigger_load_balance(struct rq *rq, int cpu)
 {
-#ifdef CONFIG_NO_HZ
-	/*
-	 * If we were in the nohz mode recently and busy at the current
-	 * scheduler tick, then check if we need to nominate new idle
-	 * load balancer.
-	 */
-	if (rq->in_nohz_recently && !rq->idle_at_tick) {
-		rq->in_nohz_recently = 0;
-
-		if (atomic_read(&nohz.load_balancer) == cpu) {
-			cpumask_clear_cpu(cpu, nohz.cpu_mask);
-			atomic_set(&nohz.load_balancer, -1);
-		}
-
-		if (atomic_read(&nohz.load_balancer) == -1) {
-			int ilb = find_new_ilb(cpu);
-
-			if (ilb < nr_cpu_ids)
-				resched_cpu(ilb);
-		}
-	}
-
-	/*
-	 * If this cpu is idle and doing idle load balancing for all the
-	 * cpus with ticks stopped, is it time for that to stop?
-	 */
-	if (rq->idle_at_tick && atomic_read(&nohz.load_balancer) == cpu &&
-	    cpumask_weight(nohz.cpu_mask) == num_online_cpus()) {
-		resched_cpu(cpu);
-		return;
-	}
-
-	/*
-	 * If this cpu is idle and the idle load balancing is done by
-	 * someone else, then no need raise the SCHED_SOFTIRQ
-	 */
-	if (rq->idle_at_tick && atomic_read(&nohz.load_balancer) != cpu &&
-	    cpumask_test_cpu(cpu, nohz.cpu_mask))
-		return;
-#endif
 	/* Don't need to rebalance while attached to NULL domain */
 	if (time_after_eq(jiffies, rq->next_balance) &&
 	    likely(!on_null_domain(cpu)))
 		raise_softirq(SCHED_SOFTIRQ);
+#ifdef CONFIG_NO_HZ
+	else if (nohz_kick_needed(rq, cpu) && likely(!on_null_domain(cpu)))
+		nohz_balancer_kick(cpu);
+#endif
 }
 
 static void rq_online_fair(struct rq *rq)
kernel/sched.c +10 -3
Index: tip/kernel/sched.c
===================================================================
@@ -504,7 +504,7 @@ struct rq {
 	unsigned long cpu_load[CPU_LOAD_IDX_MAX];
 #ifdef CONFIG_NO_HZ
 	u64 nohz_stamp;
-	unsigned char in_nohz_recently;
+	unsigned char nohz_balance_kick;
 #endif
 	unsigned int skip_clock_update;
 
@@ -7605,6 +7605,11 @@ void __init sched_init(void)
 		rq->idle_stamp = 0;
 		rq->avg_idle = 2*sysctl_sched_migration_cost;
 		rq_attach_root(rq, &def_root_domain);
+#ifdef CONFIG_NO_HZ
+		rq->nohz_balance_kick = 0;
+		init_remote_softirq_csd(&per_cpu(remote_sched_softirq_cb, i),
+					SCHED_SOFTIRQ);
+#endif
 #endif
 		init_rq_hrtick(rq);
 		atomic_set(&rq->nr_iowait, 0);
@@ -7649,8 +7654,10 @@ void __init sched_init(void)
 	zalloc_cpumask_var(&nohz_cpu_mask, GFP_NOWAIT);
 #ifdef CONFIG_SMP
 #ifdef CONFIG_NO_HZ
-	zalloc_cpumask_var(&nohz.cpu_mask, GFP_NOWAIT);
-	alloc_cpumask_var(&nohz.ilb_grp_nohz_mask, GFP_NOWAIT);
+	zalloc_cpumask_var(&nohz.idle_cpus_mask, GFP_NOWAIT);
+	alloc_cpumask_var(&nohz.grp_idle_mask, GFP_NOWAIT);
+	atomic_set(&nohz.first_pick_cpu, nr_cpu_ids);
+	atomic_set(&nohz.second_pick_cpu, nr_cpu_ids);
 #endif
 	/* May be allocated at isolcpus cmdline parse time */
 	if (cpu_isolated_map == NULL)
#10 lore raw

Re: [patch 4/7] sched: Change nohz ilb logic from pull to push model

Quoted 9 lines · Suresh Siddha

From: Venkatesh Pallipadi <[email protected]>
Subject: sched: Change nohz ilb logic from pull to push model

In the new push model, all idle CPUs indeed go into nohz mode. There is still the concept of idle load balancer. Busy CPU kicks the nohz balancer when any of the nohz CPUs need idle load balancing. The kickee CPU does the idle load balancing on behalf of all idle CPUs instead of the normal idle balance.

Quoted 7 lines

This addresses the below two problems with the current nohz ilb logic:
* the balancer will continue to have periodic ticks and wakeup frequently, even though it may not have any rebalancing to do on behalf of any of the idle CPUs.
* On x86 and CPUs that have APIC timer stoppage on idle CPUs, this periodic wakeup can result in an additional interrupt on a CPU doing the timer broadcast.

How do we select the timer broadcast cpu today? Is it changes at all at run time? Maybe that CPU should be a good target for the timer migration so that additional CPU are not wokenup from idle states.

Quoted 290 lines
---
 kernel/sched.c      |   13 +-
 kernel/sched_fair.c |  283 ++++++++++++++++++++++++++++++----------------------
 2 files changed, 177 insertions(+), 119 deletions(-)

Index: tip/kernel/sched_fair.c
===================================================================

kernel/sched_fair.c +142 -45
@@ -3081,10 +3081,26 @@ out_unlock:
 }
 
 #ifdef CONFIG_NO_HZ
+
+static DEFINE_PER_CPU(struct call_single_data, remote_sched_softirq_cb);
+
+/*
+ * idle load balancing details
+ * - One of the idle CPUs nominates itself as idle load_balancer, while
+ *   entering idle.
+ * - This idle load balancer CPU will also go into tickless mode when
+ *   it is idle, just like all other idle CPUs
+ * - When one of the busy CPUs notice that there may be an idle rebalancing
+ *   needed, they will kick the idle load balancer, which then does idle
+ *   load balancing for all the idle CPUs.
+ */
 static struct {
 	atomic_t load_balancer;
-	cpumask_var_t cpu_mask;
-	cpumask_var_t ilb_grp_nohz_mask;
+	atomic_t first_pick_cpu;
+	atomic_t second_pick_cpu;
+	cpumask_var_t idle_cpus_mask;
+	cpumask_var_t grp_idle_mask;
+	unsigned long next_balance;     /* in jiffy units */
 } nohz ____cacheline_aligned = {
 	.load_balancer = ATOMIC_INIT(-1),
 };
@@ -3141,17 +3157,17 @@ static inline struct sched_domain *lowes
  */
 static inline int is_semi_idle_group(struct sched_group *ilb_group)
 {
-	cpumask_and(nohz.ilb_grp_nohz_mask, nohz.cpu_mask,
+	cpumask_and(nohz.grp_idle_mask, nohz.idle_cpus_mask,
 					sched_group_cpus(ilb_group));
 
 	/*
 	 * A sched_group is semi-idle when it has atleast one busy cpu
 	 * and atleast one idle cpu.
 	 */
-	if (cpumask_empty(nohz.ilb_grp_nohz_mask))
+	if (cpumask_empty(nohz.grp_idle_mask))
 		return 0;
 
-	if (cpumask_equal(nohz.ilb_grp_nohz_mask, sched_group_cpus(ilb_group)))
+	if (cpumask_equal(nohz.grp_idle_mask, sched_group_cpus(ilb_group)))
 		return 0;
 
 	return 1;
@@ -3184,7 +3200,7 @@ static int find_new_ilb(int cpu)
 	 * Optimize for the case when we have no idle CPUs or only one
 	 * idle CPU. Don't walk the sched_domain hierarchy in such cases
 	 */
-	if (cpumask_weight(nohz.cpu_mask) < 2)
+	if (cpumask_weight(nohz.idle_cpus_mask) < 2)
 		goto out_done;
 
 	for_each_flag_domain(cpu, sd, SD_POWERSAVINGS_BALANCE) {
@@ -3192,7 +3208,7 @@ static int find_new_ilb(int cpu)
 
 		do {
 			if (is_semi_idle_group(ilb_group))
-				return cpumask_first(nohz.ilb_grp_nohz_mask);
+				return cpumask_first(nohz.grp_idle_mask);
 
 			ilb_group = ilb_group->next;
 
@@ -3200,42 +3216,61 @@ static int find_new_ilb(int cpu)
 	}
 
 out_done:
-	return cpumask_first(nohz.cpu_mask);
+	return nr_cpu_ids;
 }
 #else /*  (CONFIG_SCHED_MC || CONFIG_SCHED_SMT) */
 static inline int find_new_ilb(int call_cpu)
 {
-	return cpumask_first(nohz.cpu_mask);
+	return nr_cpu_ids;
 }
 #endif
 
 /*
+ * Kick a CPU to do the nohz balancing, if it is time for it. We pick the
+ * nohz_load_balancer CPU (if there is one) otherwise fallback to any idle
+ * CPU (if there is one).
+ */
+static void nohz_balancer_kick(int cpu)
+{
+	int ilb_cpu;
+
+	nohz.next_balance++;
+
+	ilb_cpu = get_nohz_load_balancer();
+	if (ilb_cpu < 0) {
+		ilb_cpu = cpumask_first(nohz.idle_cpus_mask);
+		if (ilb_cpu >= nr_cpu_ids)
+			return;
+	}
+
+	if (!cpu_rq(ilb_cpu)->nohz_balance_kick) {
+		struct call_single_data *cp;
+
+		cpu_rq(ilb_cpu)->nohz_balance_kick = 1;
+		cp = &per_cpu(remote_sched_softirq_cb, cpu);
+		send_remote_softirq(cp, ilb_cpu, 0);
+	}
+	return;
+}
+
+/*
  * 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..
+ * load balancing on behalf of all those cpus.
  *
- * 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()
+ * When the ilb owner becomes busy, we will not have new ilb owner until some
+ * idle CPU wakes up and goes back to idle or some busy CPU tries to kick
+ * idle load balancing by kicking one of the idle CPUs.
+ *
+ * Ticks are stopped for the ilb owner as well, with busy CPU kicking this
+ * ilb owner CPU in future (when there is a need for idle load balancing on
+ * behalf of all idle CPUs).
  */
 int select_nohz_load_balancer(int stop_tick)
 {
 	int cpu = smp_processor_id();
 
 	if (stop_tick) {
-		cpu_rq(cpu)->in_nohz_recently = 1;
-
 		if (!cpu_active(cpu)) {
 			if (atomic_read(&nohz.load_balancer) != cpu)
 				return 0;
@@ -3250,25 +3285,20 @@ int select_nohz_load_balancer(int stop_t
 			return 0;
 		}
 
-		cpumask_set_cpu(cpu, nohz.cpu_mask);
+		cpumask_set_cpu(cpu, nohz.idle_cpus_mask);
 
-		/* time for ilb owner also to sleep */
-		if (cpumask_weight(nohz.cpu_mask) == num_active_cpus()) {
-			if (atomic_read(&nohz.load_balancer) == cpu)
-				atomic_set(&nohz.load_balancer, -1);
-			return 0;
-		}
+		if (atomic_read(&nohz.first_pick_cpu) == cpu)
+			atomic_cmpxchg(&nohz.first_pick_cpu, cpu, nr_cpu_ids);
+		if (atomic_read(&nohz.second_pick_cpu) == cpu)
+			atomic_cmpxchg(&nohz.second_pick_cpu, cpu, nr_cpu_ids);
 
 		if (atomic_read(&nohz.load_balancer) == -1) {
-			/* make me the ilb owner */
-			if (atomic_cmpxchg(&nohz.load_balancer, -1, cpu) == -1)
-				return 1;
-		} else if (atomic_read(&nohz.load_balancer) == cpu) {
 			int new_ilb;
 
-			if (!(sched_smt_power_savings ||
-						sched_mc_power_savings))
-				return 1;
+			/* make me the ilb owner */
+			if (atomic_cmpxchg(&nohz.load_balancer, -1, cpu) != -1)
+				return 0;
+
 			/*
 			 * Check to see if there is a more power-efficient
 			 * ilb.
@@ -3279,13 +3309,13 @@ int select_nohz_load_balancer(int stop_t
 				resched_cpu(new_ilb);
 				return 0;
 			}
-			return 1;
+			return 0;
 		}
 	} else {
-		if (!cpumask_test_cpu(cpu, nohz.cpu_mask))
+		if (!cpumask_test_cpu(cpu, nohz.idle_cpus_mask))
 			return 0;
 
-		cpumask_clear_cpu(cpu, nohz.cpu_mask);
+		cpumask_clear_cpu(cpu, nohz.idle_cpus_mask);
 
 		if (atomic_read(&nohz.load_balancer) == cpu)
 			if (atomic_cmpxchg(&nohz.load_balancer, cpu, -1) != cpu)
@@ -3373,11 +3403,97 @@ out:
 		rq->next_balance = next_balance;
 }
 
+#ifdef CONFIG_NO_HZ
 /*
- * run_rebalance_domains is triggered when needed from the scheduler tick.
- * In CONFIG_NO_HZ case, the idle load balance owner will do the
+ * In CONFIG_NO_HZ case, the idle balance kickee will do the
  * rebalancing for all the cpus for whom scheduler ticks are stopped.
  */
+static void nohz_idle_balance(int this_cpu, enum cpu_idle_type idle)
+{
+	struct rq *this_rq = cpu_rq(this_cpu);
+	struct rq *rq;
+	int balance_cpu;
+
+	if (idle != CPU_IDLE || !this_rq->nohz_balance_kick)
+		return;
+
+	for_each_cpu(balance_cpu, nohz.idle_cpus_mask) {
+		if (balance_cpu == this_cpu)
+			continue;
+
+		/*
+		 * If this cpu gets work to do, stop the load balancing
+		 * work being done for other cpus. Next load
+		 * balancing owner will pick it up.
+		 */
+		if (need_resched()) {
+			this_rq->nohz_balance_kick = 0;
+			break;
+		}
+
+		rebalance_domains(balance_cpu, CPU_IDLE);
+
+		rq = cpu_rq(balance_cpu);
+		if (time_after(this_rq->next_balance, rq->next_balance))
+			this_rq->next_balance = rq->next_balance;
+	}
+	nohz.next_balance = this_rq->next_balance;
+	this_rq->nohz_balance_kick = 0;
+}
+
+/*
+ * Current heuristic for kicking the idle load balancer
+ * - first_pick_cpu is the one of the busy CPUs. It will kick
+ *   idle load balancer when it has more than one process active. This
+ *   eliminates the need for idle load balancing altogether when we have
+ *   only one running process in the system (common case).
+ * - If there are more than one busy CPU, idle load balancer may have
+ *   to run for active_load_balance to happen (i.e., two busy CPUs are
+ *   SMT or core siblings and can run better if they move to different
+ *   physical CPUs). So, second_pick_cpu is the second of the busy CPUs
+ *   which will kick idle load balancer as soon as it has any load.
+ */
+static inline int nohz_kick_needed(struct rq *rq, int cpu)
+{
+	unsigned long now = jiffies;
+	int ret;
+	int first_pick_cpu, second_pick_cpu;
+
+	if (time_before(now, nohz.next_balance))
+		return 0;
+
+	if (!rq->nr_running)
+		return 0;
+
+	first_pick_cpu = atomic_read(&nohz.first_pick_cpu);
+	second_pick_cpu = atomic_read(&nohz.second_pick_cpu);
+
+	if (first_pick_cpu < nr_cpu_ids && first_pick_cpu != cpu &&
+	    second_pick_cpu < nr_cpu_ids && second_pick_cpu != cpu)
+		return 0;
+
+	ret = atomic_cmpxchg(&nohz.first_pick_cpu, nr_cpu_ids, cpu);
+	if (ret == nr_cpu_ids || ret == cpu) {
+		atomic_cmpxchg(&nohz.second_pick_cpu, cpu, nr_cpu_ids);

kernel/sched_fair.c out: · line 3487

Quoted 10 lines
kernel/sched_fair.c +10 -0
+		if (rq->nr_running > 1)
+			return 1;
+	} else {
+		ret = atomic_cmpxchg(&nohz.second_pick_cpu, nr_cpu_ids, cpu);
+		if (ret == nr_cpu_ids || ret == cpu) {
+			if (rq->nr_running)
+				return 1;
+		}
+	}
+	return 0;

Hi Suresh,

Can you please give more explanation on how the combination of first_pick_cpu and second_pick_cpu works. We need to kick an idle CPU whenever our cpu or group becomes overloaded right. We will have to prefer cores of other packages when more tasks become ready to run. So a notion of group overload is needed to kick new cpus. Also new idle CPUs that are kicked should come form other cores and packages instead or nearest sibling.

As per the current implementation a sibling thread may be kicked but it will not pull the task as the load balancer will be run on behalf of all idle cores in the system and then a appropriate idle core will pull the new task... correct?

--Vaidy

[snip]

#11 lore raw

Re: [patch 4/7] sched: Change nohz ilb logic from pull to push model

Quoted 19 lines · Vaidyanathan Srinivasan
Quoted 9 lines · Suresh Siddha

From: Venkatesh Pallipadi <[email protected]>
Subject: sched: Change nohz ilb logic from pull to push model

In the new push model, all idle CPUs indeed go into nohz mode. There is still the concept of idle load balancer. Busy CPU kicks the nohz balancer when any of the nohz CPUs need idle load balancing. The kickee CPU does the idle load balancing on behalf of all idle CPUs instead of the normal idle balance.

Quoted 7 lines

This addresses the below two problems with the current nohz ilb logic:
* the balancer will continue to have periodic ticks and wakeup frequently, even though it may not have any rebalancing to do on behalf of any of the idle CPUs.
* On x86 and CPUs that have APIC timer stoppage on idle CPUs, this periodic wakeup can result in an additional interrupt on a CPU doing the timer broadcast.

Quoted 3 lines

How do we select the timer broadcast cpu today? Is it changes at all at run time? Maybe that CPU should be a good target for the timer migration so that additional CPU are not wokenup from idle states.

It is based on who handles irq 0. Anyways, newer generation of cpu's doesn't have apic timer stoppage issue. If you want to do more intelligent timer migrations, then its better to address with a mechanism that works efficiently for all platforms.

Quoted 3 lines

Can you please give more explanation on how the combination of first_pick_cpu and second_pick_cpu works. We need to kick an idle CPU whenever our cpu or group becomes overloaded right.

With this change, the need for idle load balancing(/kicking an idle cpu to do idle load balancing on behalf of all idle cpus) is determined when there is only one cpu busy with more than 1 task or more than one cpu busy.

sched group is relevant only if we are balancing at a particular domain. Traversing all the groups and finding out the group load vs capacity from the busy cpu will add more overhead to the busy cpu.

We need more intelligence of when to do idle load balancing and when to stop it. Current proposal is a simple fix to address the idle core in a semi-idle laptop/netbooks to not have periodic ticks in idle.

Quoted 5 lines

We will have to
prefer cores of other packages when more tasks become ready to run. So a notion of group overload is needed to kick new cpus. Also new idle CPUs that are kicked should come form other cores and packages instead or nearest sibling.

Kicked cpu can be nearest idle core to the busy core. This can do idle load balancing and the actual load can move the far away core (for perf policy) or nearest core (for power-savings policy). Any intelligent heuristics to do this with minimal disturbance to busy cpu's are welcome.

Quoted 5 lines

As per the current implementation a sibling thread may be kicked but it will not pull the task as the load balancer will be run on behalf of all idle cores in the system and then a appropriate idle core will pull the new task... correct?

Yes.

thanks,
suresh

#12 lore raw

PATCH 5/7 sched: Change select_nohz_load_balancer to return void

In reply to Suresh Siddha

From: Venkatesh Pallipadi <[email protected]>
Subject: sched: Change select_nohz_load_balancer to return void

select_nohz_load_balancer used to return 1 when ticks are not to be stopped (idle_balancer), 0 otherwise. With change to nohz idle_balancer logic, all idle cpus can go to tickless mode and be woken up by a kick from one of the busy cpus, if and when idle balancing is required. As a result, select_nohz_load_balancer can return void.

---
 include/linux/sched.h    |    7 ++-----
 kernel/sched_fair.c      |   16 ++++++++--------
 kernel/time/tick-sched.c |    8 +-------
 3 files changed, 11 insertions(+), 20 deletions(-)
kernel/sched_fair.c +8 -8
Index: tip/kernel/sched_fair.c
===================================================================
@@ -3266,14 +3266,14 @@ static void nohz_balancer_kick(int cpu)
  * ilb owner CPU in future (when there is a need for idle load balancing on
  * behalf of all idle CPUs).
  */
-int select_nohz_load_balancer(int stop_tick)
+void select_nohz_load_balancer(int stop_tick)
 {
 	int cpu = smp_processor_id();
 
 	if (stop_tick) {
 		if (!cpu_active(cpu)) {
 			if (atomic_read(&nohz.load_balancer) != cpu)
-				return 0;
+				return;
 
 			/*
 			 * If we are going offline and still the leader,
@@ -3282,7 +3282,7 @@ int select_nohz_load_balancer(int stop_t
 			if (atomic_cmpxchg(&nohz.load_balancer, cpu, -1) != cpu)
 				BUG();
 
-			return 0;
+			return;
 		}
 
 		cpumask_set_cpu(cpu, nohz.idle_cpus_mask);
@@ -3297,7 +3297,7 @@ int select_nohz_load_balancer(int stop_t
 
 			/* make me the ilb owner */
 			if (atomic_cmpxchg(&nohz.load_balancer, -1, cpu) != -1)
-				return 0;
+				return;
 
 			/*
 			 * Check to see if there is a more power-efficient
@@ -3307,13 +3307,13 @@ int select_nohz_load_balancer(int stop_t
 			if (new_ilb < nr_cpu_ids && new_ilb != cpu) {
 				atomic_set(&nohz.load_balancer, -1);
 				resched_cpu(new_ilb);
-				return 0;
+				return;
 			}
-			return 0;
+			return;
 		}
 	} else {
 		if (!cpumask_test_cpu(cpu, nohz.idle_cpus_mask))
-			return 0;
+			return;
 
 		cpumask_clear_cpu(cpu, nohz.idle_cpus_mask);
 
@@ -3321,7 +3321,7 @@ int select_nohz_load_balancer(int stop_t
 			if (atomic_cmpxchg(&nohz.load_balancer, cpu, -1) != cpu)
 				BUG();
 	}
-	return 0;
+	return;
 }
 #endif
 
kernel/time/tick-sched.c +1 -7
Index: tip/kernel/time/tick-sched.c
===================================================================
@@ -408,13 +408,7 @@ void tick_nohz_stop_sched_tick(int inidl
 		 * the scheduler tick in nohz_restart_sched_tick.
 		 */
 		if (!ts->tick_stopped) {
-			if (select_nohz_load_balancer(1)) {
-				/*
-				 * sched tick not stopped!
-				 */
-				cpumask_clear_cpu(cpu, nohz_cpu_mask);
-				goto out;
-			}
+			select_nohz_load_balancer(1);
 
 			ts->idle_tick = hrtimer_get_expires(&ts->sched_timer);
 			ts->tick_stopped = 1;
include/linux/sched.h +2 -5
Index: tip/include/linux/sched.h
===================================================================
@@ -272,14 +272,11 @@ extern void task_rq_unlock_wait(struct t
 
 extern cpumask_var_t nohz_cpu_mask;
 #if defined(CONFIG_SMP) && defined(CONFIG_NO_HZ)
-extern int select_nohz_load_balancer(int cpu);
+extern void select_nohz_load_balancer(int stop_tick);
 extern int get_nohz_load_balancer(void);
 extern int nohz_ratelimit(int cpu);
 #else
-static inline int select_nohz_load_balancer(int cpu)
-{
-	return 0;
-}
+static inline void select_nohz_load_balancer(int stop_tick) { }
 
 static inline int nohz_ratelimit(int cpu)
 {
#13 lore raw

PATCH 6/7 sched: change nohz.load_balancer to be nr_cpu_ids based

In reply to Suresh Siddha

From: Venkatesh Pallipadi <[email protected]>
Subject: sched: change nohz.load_balancer to be nr_cpu_ids based

nohz.load_balancer was using -1 when it is not set to any cpu. Change it to nr_cpu_ids, making it similar to other such variables in this file.

---
 kernel/hrtimer.c    |    2 +-
 kernel/sched.c      |    1 +
 kernel/sched_fair.c |   26 ++++++++++++++++----------
 kernel/timer.c      |    2 +-
 4 files changed, 19 insertions(+), 12 deletions(-)
kernel/sched_fair.c +16 -10
Index: tip/kernel/sched_fair.c
===================================================================
@@ -3101,13 +3101,15 @@ static struct {
 	cpumask_var_t idle_cpus_mask;
 	cpumask_var_t grp_idle_mask;
 	unsigned long next_balance;     /* in jiffy units */
-} nohz ____cacheline_aligned = {
-	.load_balancer = ATOMIC_INIT(-1),
-};
+} nohz ____cacheline_aligned;
 
 int get_nohz_load_balancer(void)
 {
-	return atomic_read(&nohz.load_balancer);
+	int load_balancer = atomic_read(&nohz.load_balancer);
+	if (load_balancer >= nr_cpu_ids)
+		return nr_cpu_ids;
+
+	return load_balancer;
 }
 
 #if defined(CONFIG_SCHED_MC) || defined(CONFIG_SCHED_SMT)
@@ -3237,7 +3239,8 @@ static void nohz_balancer_kick(int cpu)
 	nohz.next_balance++;
 
 	ilb_cpu = get_nohz_load_balancer();
-	if (ilb_cpu < 0) {
+
+	if (ilb_cpu >= nr_cpu_ids) {
 		ilb_cpu = cpumask_first(nohz.idle_cpus_mask);
 		if (ilb_cpu >= nr_cpu_ids)
 			return;
@@ -3279,7 +3282,8 @@ void select_nohz_load_balancer(int stop_
 			 * If we are going offline and still the leader,
 			 * give up!
 			 */
-			if (atomic_cmpxchg(&nohz.load_balancer, cpu, -1) != cpu)
+			if (atomic_cmpxchg(&nohz.load_balancer, cpu,
+					   nr_cpu_ids) != cpu)
 				BUG();
 
 			return;
@@ -3292,11 +3296,12 @@ void select_nohz_load_balancer(int stop_
 		if (atomic_read(&nohz.second_pick_cpu) == cpu)
 			atomic_cmpxchg(&nohz.second_pick_cpu, cpu, nr_cpu_ids);
 
-		if (atomic_read(&nohz.load_balancer) == -1) {
+		if (atomic_read(&nohz.load_balancer) >= nr_cpu_ids) {
 			int new_ilb;
 
 			/* make me the ilb owner */
-			if (atomic_cmpxchg(&nohz.load_balancer, -1, cpu) != -1)
+			if (atomic_cmpxchg(&nohz.load_balancer, nr_cpu_ids,
+					   cpu) != nr_cpu_ids)
 				return;
 
 			/*
@@ -3305,7 +3310,7 @@ void select_nohz_load_balancer(int stop_
 			 */
 			new_ilb = find_new_ilb(cpu);
 			if (new_ilb < nr_cpu_ids && new_ilb != cpu) {
-				atomic_set(&nohz.load_balancer, -1);
+				atomic_set(&nohz.load_balancer, nr_cpu_ids);
 				resched_cpu(new_ilb);
 				return;
 			}
@@ -3318,7 +3323,8 @@ void select_nohz_load_balancer(int stop_
 		cpumask_clear_cpu(cpu, nohz.idle_cpus_mask);
 
 		if (atomic_read(&nohz.load_balancer) == cpu)
-			if (atomic_cmpxchg(&nohz.load_balancer, cpu, -1) != cpu)
+			if (atomic_cmpxchg(&nohz.load_balancer, cpu,
+					   nr_cpu_ids) != cpu)
 				BUG();
 	}
 	return;
kernel/sched.c +1 -0
Index: tip/kernel/sched.c
===================================================================
@@ -7656,6 +7656,7 @@ void __init sched_init(void)
 #ifdef CONFIG_NO_HZ
 	zalloc_cpumask_var(&nohz.idle_cpus_mask, GFP_NOWAIT);
 	alloc_cpumask_var(&nohz.grp_idle_mask, GFP_NOWAIT);
+	atomic_set(&nohz.load_balancer, nr_cpu_ids);
 	atomic_set(&nohz.first_pick_cpu, nr_cpu_ids);
 	atomic_set(&nohz.second_pick_cpu, nr_cpu_ids);
 #endif
kernel/hrtimer.c +1 -1
Index: tip/kernel/hrtimer.c
===================================================================
@@ -147,7 +147,7 @@ static int hrtimer_get_target(int this_c
 	if (!pinned && get_sysctl_timer_migration() && idle_cpu(this_cpu)) {
 		int preferred_cpu = get_nohz_load_balancer();
 
-		if (preferred_cpu >= 0)
+		if (preferred_cpu < nr_cpu_ids)
 			return preferred_cpu;
 	}
 #endif
kernel/timer.c +1 -1
Index: tip/kernel/timer.c
===================================================================
@@ -682,7 +682,7 @@ __mod_timer(struct timer_list *timer, un
 	if (!pinned && get_sysctl_timer_migration() && idle_cpu(cpu)) {
 		int preferred_cpu = get_nohz_load_balancer();
 
-		if (preferred_cpu >= 0)
+		if (preferred_cpu < nr_cpu_ids)
 			cpu = preferred_cpu;
 	}
 #endif
maintainer
#14 lore raw

Re: [patch 6/7] sched: change nohz.load_balancer to be nr_cpu_ids based

kernel/sched_fair.c static struct { · line 3113

Quoted 9 lines · Suresh Siddha

int get_nohz_load_balancer(void)
{

kernel/sched_fair.c +5 -1
-       return atomic_read(&nohz.load_balancer);
+       int load_balancer = atomic_read(&nohz.load_balancer);
+       if (load_balancer >= nr_cpu_ids)
+               return nr_cpu_ids;
+
+       return load_balancer;
 } 

How could it ever be > nr_cpu_ids, and thus, do we need that conditional?

#15 lore raw

PATCH 7/7 timers: use nearest busy cpu for migrating timers from an idle cpu

In reply to Suresh Siddha

Currently we are migrating the unpinned timers from an idle to the cpu doing idle load balancing (when all the cpus in the system are idle, there is no idle load balacncing cpu and timers get added to the same idle cpu where the request was made. So the current optimization works only on semi idle system).

And In semi idle system, we no longer have periodic ticks on the idle cpu doing the idle load balancing on behalf of all the cpu's. Using that cpu will add more delays to the timers than intended (as that cpu's timer base may not be uptodate wrt jiffies etc). This was causing mysterious slowdowns during boot etc.

For now, in the semi idle case, use the nearest busy cpu for migrating timers from an idle cpu. This is good for power-savings anyway.

---
 include/linux/sched.h |    2 +-
 kernel/hrtimer.c      |    8 ++------
 kernel/sched.c        |   13 +++++++++++++
 kernel/timer.c        |    8 ++------
 4 files changed, 18 insertions(+), 13 deletions(-)
kernel/hrtimer.c +2 -6
Index: tip/kernel/hrtimer.c
===================================================================
@@ -144,12 +144,8 @@ struct hrtimer_clock_base *lock_hrtimer_
 static int hrtimer_get_target(int this_cpu, int pinned)
 {
 #ifdef CONFIG_NO_HZ
-	if (!pinned && get_sysctl_timer_migration() && idle_cpu(this_cpu)) {
-		int preferred_cpu = get_nohz_load_balancer();
-
-		if (preferred_cpu < nr_cpu_ids)
-			return preferred_cpu;
-	}
+	if (!pinned && get_sysctl_timer_migration() && idle_cpu(this_cpu))
+		return get_nohz_timer_target();
 #endif
 	return this_cpu;
 }
kernel/sched.c +13 -0
Index: tip/kernel/sched.c
===================================================================
@@ -1201,6 +1201,19 @@ static void resched_cpu(int cpu)
 }
 
 #ifdef CONFIG_NO_HZ
+int get_nohz_timer_target(void)
+{
+	int cpu = smp_processor_id();
+	int i;
+	struct sched_domain *sd;
+
+	for_each_domain(cpu, sd) {
+		for_each_cpu(i, sched_domain_span(sd))
+			if (!idle_cpu(i))
+				return i;
+	}
+	return cpu;
+}
 /*
  * When add_timer_on() enqueues a timer into the timer wheel of an
  * idle CPU then this timer might expire before the next timer event
kernel/timer.c +2 -6
Index: tip/kernel/timer.c
===================================================================
@@ -679,12 +679,8 @@ __mod_timer(struct timer_list *timer, un
 	cpu = smp_processor_id();
 
 #if defined(CONFIG_NO_HZ) && defined(CONFIG_SMP)
-	if (!pinned && get_sysctl_timer_migration() && idle_cpu(cpu)) {
-		int preferred_cpu = get_nohz_load_balancer();
-
-		if (preferred_cpu < nr_cpu_ids)
-			cpu = preferred_cpu;
-	}
+	if (!pinned && get_sysctl_timer_migration() && idle_cpu(cpu))
+		cpu = get_nohz_timer_target();
 #endif
 	new_base = per_cpu(tvec_bases, cpu);
 
include/linux/sched.h +1 -1
Index: tip/include/linux/sched.h
===================================================================
@@ -273,7 +273,7 @@ extern void task_rq_unlock_wait(struct t
 extern cpumask_var_t nohz_cpu_mask;
 #if defined(CONFIG_SMP) && defined(CONFIG_NO_HZ)
 extern void select_nohz_load_balancer(int stop_tick);
-extern int get_nohz_load_balancer(void);
+extern int get_nohz_timer_target(void);
 extern int nohz_ratelimit(int cpu);
 #else
 static inline void select_nohz_load_balancer(int stop_tick) { }
#16 lore raw

Re: [patch 7/7] timers: use nearest busy cpu for migrating timers from an idle cpu

Quoted 11 lines · Suresh Siddha

Currently we are migrating the unpinned timers from an idle to the cpu doing idle load balancing (when all the cpus in the system are idle, there is no idle load balacncing cpu and timers get added to the same idle cpu where the request was made. So the current optimization works only on semi idle system).

And In semi idle system, we no longer have periodic ticks on the idle cpu doing the idle load balancing on behalf of all the cpu's. Using that cpu will add more delays to the timers than intended (as that cpu's timer base may not be uptodate wrt jiffies etc). This was causing mysterious slowdowns during boot etc.

Hi Suresh,

Can please give more info on why this caused delay in bootup or timer event. The jiffies should be updated even with the current push model right. We will still have some pinned timer on the idle cpu and the time base will have to be updated when the timer event happens.

Quoted 3 lines

For now, in the semi idle case, use the nearest busy cpu for migrating timers from an idle cpu. This is good for power-savings anyway.

Yes. This is good solution. But on a large system the only running cpu may accumulate too may timers that could affect the performance of the task running. We will need to test this out.

Quoted 38 lines
---
 include/linux/sched.h |    2 +-
 kernel/hrtimer.c      |    8 ++------
 kernel/sched.c        |   13 +++++++++++++
 kernel/timer.c        |    8 ++------
 4 files changed, 18 insertions(+), 13 deletions(-)

Index: tip/kernel/hrtimer.c
===================================================================

kernel/hrtimer.c +2 -6
@@ -144,12 +144,8 @@ struct hrtimer_clock_base *lock_hrtimer_
 static int hrtimer_get_target(int this_cpu, int pinned)
 {
 #ifdef CONFIG_NO_HZ
-	if (!pinned && get_sysctl_timer_migration() && idle_cpu(this_cpu)) {
-		int preferred_cpu = get_nohz_load_balancer();
-
-		if (preferred_cpu < nr_cpu_ids)
-			return preferred_cpu;
-	}
+	if (!pinned && get_sysctl_timer_migration() && idle_cpu(this_cpu))
+		return get_nohz_timer_target();
 #endif
 	return this_cpu;
 }

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

kernel/sched.c +3 -0
@@ -1201,6 +1201,19 @@ static void resched_cpu(int cpu)
 }
 
 #ifdef CONFIG_NO_HZ
+int get_nohz_timer_target(void)
+{
+	int cpu = smp_processor_id();

kernel/sched.c static void resched_cpu(int cpu) · line 1216

Quoted 10 lines
kernel/sched.c +10 -0
+	int i;
+	struct sched_domain *sd;
+
+	for_each_domain(cpu, sd) {
+		for_each_cpu(i, sched_domain_span(sd))
+			if (!idle_cpu(i))
+				return i;
+	}
+	return cpu;
+}

We will need a better way of finding the right CPU since this code will take longer time on a larger system with one or two busy cpus.

We should perhaps pick the cpu from the compliment of the current nohz.grp_idle_mask or something derived from these masks instead of searching in the sched domain. Only advantage I see is that we will get the busy CPU nearest as in same node which is better.

--Vaidy

[snip]

#17 lore raw

Re: [patch 7/7] timers: use nearest busy cpu for migrating timers from an idle cpu

Quoted 14 lines · Vaidyanathan Srinivasan
Quoted 11 lines · Suresh Siddha

Currently we are migrating the unpinned timers from an idle to the cpu doing idle load balancing (when all the cpus in the system are idle, there is no idle load balacncing cpu and timers get added to the same idle cpu where the request was made. So the current optimization works only on semi idle system).

And In semi idle system, we no longer have periodic ticks on the idle cpu doing the idle load balancing on behalf of all the cpu's. Using that cpu will add more delays to the timers than intended (as that cpu's timer base may not be uptodate wrt jiffies etc). This was causing mysterious slowdowns during boot etc.

Quoted 6 lines

Hi Suresh,

Can please give more info on why this caused delay in bootup or timer event. The jiffies should be updated even with the current push model right. We will still have some pinned timer on the idle cpu and the time base will have to be updated when the timer event happens.

with these changes, idle load balancer doesn't have periodic ticks in idle. So for that cpu, timer_jiffies in timer base won't be uptodate when another idle cpu adds timer to this cpu. So, we will introduce more delays for the timers than expected.

Quoted 6 lines
Quoted 2 lines

For now, in the semi idle case, use the nearest busy cpu for migrating timers from an idle cpu. This is good for power-savings anyway.

Yes. This is good solution. But on a large system the only running cpu may accumulate too may timers that could affect the performance of the task running. We will need to test this out.

Yes. It will be good to have an impact of this on big systems. If we see any performance issues, we can migrate the timers only when power-savings tunable is selected.

Quoted 19 lines
Quoted 5 lines

#ifdef CONFIG_NO_HZ

kernel/sched.c +3 -0
+int get_nohz_timer_target(void)
+{
+	int cpu = smp_processor_id();

kernel/sched.c static void resched_cpu(int cpu) · line 1216

Quoted 10 lines
kernel/sched.c +10 -0
+	int i;
+	struct sched_domain *sd;
+
+	for_each_domain(cpu, sd) {
+		for_each_cpu(i, sched_domain_span(sd))
+			if (!idle_cpu(i))
+				return i;
+	}
+	return cpu;
+}

We will need a better way of finding the right CPU since this code will take longer time on a larger system with one or two busy cpus.

Quoted 4 lines

We should perhaps pick the cpu from the compliment of the current nohz.grp_idle_mask or something derived from these masks instead of searching in the sched domain. Only advantage I see is that we will get the busy CPU nearest as in same node which is better.

Yes I wanted to migrate the timers to the nearest busy cpu aswell as distribute the load among all the busy cpus (if there are multiple cpu's busy).

thanks,
suresh

#18 lore raw
In reply to Suresh Siddha

Hi Suresh.

Quoted 29 lines · Suresh Siddha

This is an updated version of patchset which is posted earlier at
http://lkml.org/lkml/2009/12/10/470

Description:
Existing nohz idle load balance logic uses the pull model, with one idle load balancer CPU nominated on any partially idle system and that balancer CPU not going into nohz mode. With the periodic tick, the balancer does the idle balancing on behalf of all the CPUs in nohz mode.

This is not very optimal and has few issues:
* the balancer will continue to have periodic ticks and wakeup frequently (HZ rate), even though it may not have any rebalancing to do on behalf of any of the idle CPUs.
* On x86 and CPUs that have APIC timer stoppage on idle CPUs, this periodic wakeup can result in an additional interrupt on a CPU doing the timer broadcast.

The alternative is to have a push model, where all idle CPUs can enter nohz mode and any busy CPU kicks one of the idle CPUs to take care of idle balancing on behalf of a group of idle CPUs.

Following patches switches idle load balancer to this push approach.

Updates from the previous version:

* Busy CPU uses send_remote_softirq() for invoking SCHED_SOFTIRQ on the idle load balancing cpu, which does the load balancing on behalf of all the idle CPUs.

Quoted 5 lines

* Dropped the per NUMA node nohz load balancing as it doesn't detect certain imbalance scenarios. This will be addressed later.

Sounds great.

I'm in the middle of packing at the moment, but will try to find time to test the patches.

It might help to show the difference that the patch series makes (powertop output?)

Regards,

Nigel

#19 lore raw

Hey,

Quoted 29 lines · Suresh Siddha

This is an updated version of patchset which is posted earlier at
http://lkml.org/lkml/2009/12/10/470

Description:
Existing nohz idle load balance logic uses the pull model, with one idle load balancer CPU nominated on any partially idle system and that balancer CPU not going into nohz mode. With the periodic tick, the balancer does the idle balancing on behalf of all the CPUs in nohz mode.

This is not very optimal and has few issues:
* the balancer will continue to have periodic ticks and wakeup frequently (HZ rate), even though it may not have any rebalancing to do on behalf of any of the idle CPUs.
* On x86 and CPUs that have APIC timer stoppage on idle CPUs, this periodic wakeup can result in an additional interrupt on a CPU doing the timer broadcast.

The alternative is to have a push model, where all idle CPUs can enter nohz mode and any busy CPU kicks one of the idle CPUs to take care of idle balancing on behalf of a group of idle CPUs.

Following patches switches idle load balancer to this push approach.

Updates from the previous version:

* Busy CPU uses send_remote_softirq() for invoking SCHED_SOFTIRQ on the idle load balancing cpu, which does the load balancing on behalf of all the idle CPUs.

Quoted 5 lines

* Dropped the per NUMA node nohz load balancing as it doesn't detect certain imbalance scenarios. This will be addressed later.

This patchset works good on my notebook; the number of wakeups decreases from ~2.5 to ~1.6 when booting with init=/bin/bash, disabling cursor blinking and enabling USB autosuspend.

Thanks and best,
Dominik

maintainer
#20 lore raw
In reply to Suresh Siddha
Quoted 23 lines · Suresh Siddha

This is an updated version of patchset which is posted earlier at
http://lkml.org/lkml/2009/12/10/470

Description:
Existing nohz idle load balance logic uses the pull model, with one idle load balancer CPU nominated on any partially idle system and that balancer CPU not going into nohz mode. With the periodic tick, the balancer does the idle balancing on behalf of all the CPUs in nohz mode.

This is not very optimal and has few issues:
* the balancer will continue to have periodic ticks and wakeup frequently (HZ rate), even though it may not have any rebalancing to do on behalf of any of the idle CPUs.
* On x86 and CPUs that have APIC timer stoppage on idle CPUs, this periodic wakeup can result in an additional interrupt on a CPU doing the timer broadcast.

The alternative is to have a push model, where all idle CPUs can enter nohz mode and any busy CPU kicks one of the idle CPUs to take care of idle balancing on behalf of a group of idle CPUs.

Following patches switches idle load balancer to this push approach.

Quoted 8 lines

Updates from the previous version:

* Busy CPU uses send_remote_softirq() for invoking SCHED_SOFTIRQ on the idle load balancing cpu, which does the load balancing on behalf of all the idle CPUs.

* Dropped the per NUMA node nohz load balancing as it doesn't detect certain imbalance scenarios. This will be addressed later.

Looks good.

I think we want to keep init_remote_softirq_csd() and a function that directly triggers the relevant softirq and make the networking code and the block layer use that if possible -- and axe the rest of the send_remote_softirq() infrastructure.

Also, I think it makes sense to fold patches 4-6.

#21 lore raw
Quoted 6 lines · Peter Zijlstra

Looks good.

I think we want to keep init_remote_softirq_csd() and a function that directly triggers the relevant softirq and make the networking code and the block layer use that if possible -- and axe the rest of the send_remote_softirq() infrastructure.

For now, I ended up using __smp_call_function_single() and does away with all the remote softirq changes. If needed, we can remove the remote softirq infrastructure but it looks like the block remote softirq code looks similar to remote softirq code (like cpu notifiers for hotplug, and softirq triggering by adding the request to local queues etc). Both these things are not required for SCHED_SOFTIRQ and so I just ended up using simple __smp_call_function_single(). May be in future we can modify block and networking code to use remote softirq infrastructure.

Quoted 1 line

Also, I think it makes sense to fold patches 4-6.

Ok. I consolidated everything into this single patch(appended).

thanks,
suresh
---

From: Venkatesh Pallipadi <[email protected]>
Subject: sched: Change nohz ilb logic from pull to push model

In the new push model, all idle CPUs indeed go into nohz mode. There is still the concept of idle load balancer (performing the load balancing on behalf of all the idle cpu's in the system). Busy CPU kicks the nohz balancer when any of the nohz CPUs need idle load balancing. The kickee CPU does the idle load balancing on behalf of all idle CPUs instead of the normal idle balance.

This addresses the below two problems with the current nohz ilb logic:
* the idle load balancer continued to have periodic ticks during idle and wokeup frequently, even though it did not have any rebalancing to do on behalf of any of the idle CPUs.
* On x86 and CPUs that have APIC timer stoppage on idle CPUs, this periodic wakeup can result in a periodic additional interrupt on a CPU doing the timer broadcast.

Also currently we are migrating the unpinned timers from an idle to the cpu doing idle load balancing (when all the cpus in the system are idle, there is no idle load balancing cpu and timers get added to the same idle cpu where the request was made. So the existing optimization works only on semi idle system).

And In semi idle system, we no longer have periodic ticks on the idle load balancer CPU. Using that cpu will add more delays to the timers than intended (as that cpu's timer base may not be uptodate wrt jiffies etc). This was causing mysterious slowdowns during boot etc.

For now, in the semi idle case, use the nearest busy cpu for migrating timers from an idle cpu. This is good for power-savings anyway.

---
 include/linux/sched.h    |    9 -
 kernel/hrtimer.c         |    8 -
 kernel/sched.c           |   34 ++++
 kernel/sched_fair.c      |  322 ++++++++++++++++++++++++++++-------------------
 kernel/time/tick-sched.c |    8 -
 kernel/timer.c           |    8 -
 6 files changed, 233 insertions(+), 156 deletions(-)
kernel/sched_fair.c +194 -128
Index: tip/kernel/sched_fair.c
===================================================================
@@ -3081,13 +3081,40 @@ out_unlock:
 }
 
 #ifdef CONFIG_NO_HZ
+
+static DEFINE_PER_CPU(struct call_single_data, remote_sched_softirq_cb);
+
+static void trigger_sched_softirq(void *data)
+{
+	raise_softirq_irqoff(SCHED_SOFTIRQ);
+}
+
+static inline void init_sched_softirq_csd(struct call_single_data *csd)
+{
+	csd->func = trigger_sched_softirq;
+	csd->info = NULL;
+	csd->flags = 0;
+	csd->priv = 0;
+}
+
+/*
+ * idle load balancing details
+ * - One of the idle CPUs nominates itself as idle load_balancer, while
+ *   entering idle.
+ * - This idle load balancer CPU will also go into tickless mode when
+ *   it is idle, just like all other idle CPUs
+ * - When one of the busy CPUs notice that there may be an idle rebalancing
+ *   needed, they will kick the idle load balancer, which then does idle
+ *   load balancing for all the idle CPUs.
+ */
 static struct {
 	atomic_t load_balancer;
-	cpumask_var_t cpu_mask;
-	cpumask_var_t ilb_grp_nohz_mask;
-} nohz ____cacheline_aligned = {
-	.load_balancer = ATOMIC_INIT(-1),
-};
+	atomic_t first_pick_cpu;
+	atomic_t second_pick_cpu;
+	cpumask_var_t idle_cpus_mask;
+	cpumask_var_t grp_idle_mask;
+	unsigned long next_balance;     /* in jiffy units */
+} nohz ____cacheline_aligned;
 
 int get_nohz_load_balancer(void)
 {
@@ -3141,17 +3168,17 @@ static inline struct sched_domain *lowes
  */
 static inline int is_semi_idle_group(struct sched_group *ilb_group)
 {
-	cpumask_and(nohz.ilb_grp_nohz_mask, nohz.cpu_mask,
+	cpumask_and(nohz.grp_idle_mask, nohz.idle_cpus_mask,
 					sched_group_cpus(ilb_group));
 
 	/*
 	 * A sched_group is semi-idle when it has atleast one busy cpu
 	 * and atleast one idle cpu.
 	 */
-	if (cpumask_empty(nohz.ilb_grp_nohz_mask))
+	if (cpumask_empty(nohz.grp_idle_mask))
 		return 0;
 
-	if (cpumask_equal(nohz.ilb_grp_nohz_mask, sched_group_cpus(ilb_group)))
+	if (cpumask_equal(nohz.grp_idle_mask, sched_group_cpus(ilb_group)))
 		return 0;
 
 	return 1;
@@ -3184,7 +3211,7 @@ static int find_new_ilb(int cpu)
 	 * Optimize for the case when we have no idle CPUs or only one
 	 * idle CPU. Don't walk the sched_domain hierarchy in such cases
 	 */
-	if (cpumask_weight(nohz.cpu_mask) < 2)
+	if (cpumask_weight(nohz.idle_cpus_mask) < 2)
 		goto out_done;
 
 	for_each_flag_domain(cpu, sd, SD_POWERSAVINGS_BALANCE) {
@@ -3192,7 +3219,7 @@ static int find_new_ilb(int cpu)
 
 		do {
 			if (is_semi_idle_group(ilb_group))
-				return cpumask_first(nohz.ilb_grp_nohz_mask);
+				return cpumask_first(nohz.grp_idle_mask);
 
 			ilb_group = ilb_group->next;
 
@@ -3200,98 +3227,116 @@ static int find_new_ilb(int cpu)
 	}
 
 out_done:
-	return cpumask_first(nohz.cpu_mask);
+	return nr_cpu_ids;
 }
 #else /*  (CONFIG_SCHED_MC || CONFIG_SCHED_SMT) */
 static inline int find_new_ilb(int call_cpu)
 {
-	return cpumask_first(nohz.cpu_mask);
+	return nr_cpu_ids;
 }
 #endif
 
 /*
+ * Kick a CPU to do the nohz balancing, if it is time for it. We pick the
+ * nohz_load_balancer CPU (if there is one) otherwise fallback to any idle
+ * CPU (if there is one).
+ */
+static void nohz_balancer_kick(int cpu)
+{
+	int ilb_cpu;
+
+	nohz.next_balance++;
+
+	ilb_cpu = get_nohz_load_balancer();
+
+	if (ilb_cpu >= nr_cpu_ids) {
+		ilb_cpu = cpumask_first(nohz.idle_cpus_mask);
+		if (ilb_cpu >= nr_cpu_ids)
+			return;
+	}
+
+	if (!cpu_rq(ilb_cpu)->nohz_balance_kick) {
+		struct call_single_data *cp;
+
+		cpu_rq(ilb_cpu)->nohz_balance_kick = 1;
+		cp = &per_cpu(remote_sched_softirq_cb, cpu);
+		__smp_call_function_single(ilb_cpu, cp, 0);
+	}
+	return;
+}
+
+/*
  * 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...
+ * load balancing on behalf of all those cpus.
  *
- * 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..
+ * When the ilb owner becomes busy, we will not have new ilb owner until some
+ * idle CPU wakes up and goes back to idle or some busy CPU tries to kick
+ * idle load balancing by kicking one of the idle CPUs.
  *
- * 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()
+ * Ticks are stopped for the ilb owner as well, with busy CPU kicking this
+ * ilb owner CPU in future (when there is a need for idle load balancing on
+ * behalf of all idle CPUs).
  */
-int select_nohz_load_balancer(int stop_tick)
+void select_nohz_load_balancer(int stop_tick)
 {
 	int cpu = smp_processor_id();
 
 	if (stop_tick) {
-		cpu_rq(cpu)->in_nohz_recently = 1;
-
 		if (!cpu_active(cpu)) {
 			if (atomic_read(&nohz.load_balancer) != cpu)
-				return 0;
+				return;
 
 			/*
 			 * If we are going offline and still the leader,
 			 * give up!
 			 */
-			if (atomic_cmpxchg(&nohz.load_balancer, cpu, -1) != cpu)
+			if (atomic_cmpxchg(&nohz.load_balancer, cpu,
+					   nr_cpu_ids) != cpu)
 				BUG();
 
-			return 0;
+			return;
 		}
 
-		cpumask_set_cpu(cpu, nohz.cpu_mask);
+		cpumask_set_cpu(cpu, nohz.idle_cpus_mask);
 
-		/* time for ilb owner also to sleep */
-		if (cpumask_weight(nohz.cpu_mask) == num_active_cpus()) {
-			if (atomic_read(&nohz.load_balancer) == cpu)
-				atomic_set(&nohz.load_balancer, -1);
-			return 0;
-		}
+		if (atomic_read(&nohz.first_pick_cpu) == cpu)
+			atomic_cmpxchg(&nohz.first_pick_cpu, cpu, nr_cpu_ids);
+		if (atomic_read(&nohz.second_pick_cpu) == cpu)
+			atomic_cmpxchg(&nohz.second_pick_cpu, cpu, nr_cpu_ids);
 
-		if (atomic_read(&nohz.load_balancer) == -1) {
-			/* make me the ilb owner */
-			if (atomic_cmpxchg(&nohz.load_balancer, -1, cpu) == -1)
-				return 1;
-		} else if (atomic_read(&nohz.load_balancer) == cpu) {
+		if (atomic_read(&nohz.load_balancer) >= nr_cpu_ids) {
 			int new_ilb;
 
-			if (!(sched_smt_power_savings ||
-						sched_mc_power_savings))
-				return 1;
+			/* make me the ilb owner */
+			if (atomic_cmpxchg(&nohz.load_balancer, nr_cpu_ids,
+					   cpu) != nr_cpu_ids)
+				return;
+
 			/*
 			 * Check to see if there is a more power-efficient
 			 * ilb.
 			 */
 			new_ilb = find_new_ilb(cpu);
 			if (new_ilb < nr_cpu_ids && new_ilb != cpu) {
-				atomic_set(&nohz.load_balancer, -1);
+				atomic_set(&nohz.load_balancer, nr_cpu_ids);
 				resched_cpu(new_ilb);
-				return 0;
+				return;
 			}
-			return 1;
+			return;
 		}
 	} else {
-		if (!cpumask_test_cpu(cpu, nohz.cpu_mask))
-			return 0;
+		if (!cpumask_test_cpu(cpu, nohz.idle_cpus_mask))
+			return;
 
-		cpumask_clear_cpu(cpu, nohz.cpu_mask);
+		cpumask_clear_cpu(cpu, nohz.idle_cpus_mask);
 
 		if (atomic_read(&nohz.load_balancer) == cpu)
-			if (atomic_cmpxchg(&nohz.load_balancer, cpu, -1) != cpu)
+			if (atomic_cmpxchg(&nohz.load_balancer, cpu,
+					   nr_cpu_ids) != cpu)
 				BUG();
 	}
-	return 0;
+	return;
 }
 #endif
 
@@ -3373,11 +3418,97 @@ out:
 		rq->next_balance = next_balance;
 }
 
+#ifdef CONFIG_NO_HZ
 /*
- * run_rebalance_domains is triggered when needed from the scheduler tick.
- * In CONFIG_NO_HZ case, the idle load balance owner will do the
+ * In CONFIG_NO_HZ case, the idle balance kickee will do the
  * rebalancing for all the cpus for whom scheduler ticks are stopped.
  */
+static void nohz_idle_balance(int this_cpu, enum cpu_idle_type idle)
+{
+	struct rq *this_rq = cpu_rq(this_cpu);
+	struct rq *rq;
+	int balance_cpu;
+
+	if (idle != CPU_IDLE || !this_rq->nohz_balance_kick)
+		return;
+
+	for_each_cpu(balance_cpu, nohz.idle_cpus_mask) {
+		if (balance_cpu == this_cpu)
+			continue;
+
+		/*
+		 * If this cpu gets work to do, stop the load balancing
+		 * work being done for other cpus. Next load
+		 * balancing owner will pick it up.
+		 */
+		if (need_resched()) {
+			this_rq->nohz_balance_kick = 0;
+			break;
+		}
+
+		rebalance_domains(balance_cpu, CPU_IDLE);
+
+		rq = cpu_rq(balance_cpu);
+		if (time_after(this_rq->next_balance, rq->next_balance))
+			this_rq->next_balance = rq->next_balance;
+	}
+	nohz.next_balance = this_rq->next_balance;
+	this_rq->nohz_balance_kick = 0;
+}
+
+/*
+ * Current heuristic for kicking the idle load balancer
+ * - first_pick_cpu is the one of the busy CPUs. It will kick
+ *   idle load balancer when it has more than one process active. This
+ *   eliminates the need for idle load balancing altogether when we have
+ *   only one running process in the system (common case).
+ * - If there are more than one busy CPU, idle load balancer may have
+ *   to run for active_load_balance to happen (i.e., two busy CPUs are
+ *   SMT or core siblings and can run better if they move to different
+ *   physical CPUs). So, second_pick_cpu is the second of the busy CPUs
+ *   which will kick idle load balancer as soon as it has any load.
+ */
+static inline int nohz_kick_needed(struct rq *rq, int cpu)
+{
+	unsigned long now = jiffies;
+	int ret;
+	int first_pick_cpu, second_pick_cpu;
+
+	if (time_before(now, nohz.next_balance))
+		return 0;
+
+	if (!rq->nr_running)
+		return 0;
+
+	first_pick_cpu = atomic_read(&nohz.first_pick_cpu);
+	second_pick_cpu = atomic_read(&nohz.second_pick_cpu);
+
+	if (first_pick_cpu < nr_cpu_ids && first_pick_cpu != cpu &&
+	    second_pick_cpu < nr_cpu_ids && second_pick_cpu != cpu)
+		return 0;
+
+	ret = atomic_cmpxchg(&nohz.first_pick_cpu, nr_cpu_ids, cpu);
+	if (ret == nr_cpu_ids || ret == cpu) {
+		atomic_cmpxchg(&nohz.second_pick_cpu, cpu, nr_cpu_ids);
+		if (rq->nr_running > 1)
+			return 1;
+	} else {
+		ret = atomic_cmpxchg(&nohz.second_pick_cpu, nr_cpu_ids, cpu);
+		if (ret == nr_cpu_ids || ret == cpu) {
+			if (rq->nr_running)
+				return 1;
+		}
+	}
+	return 0;
+}
+#else
+static void nohz_idle_balance(int this_cpu, enum cpu_idle_type idle) { }
+#endif
+
+/*
+ * run_rebalance_domains is triggered when needed from the scheduler tick.
+ * Also triggered for nohz idle balancing (with nohz_balancing_kick set).
+ */
 static void run_rebalance_domains(struct softirq_action *h)
 {
 	int this_cpu = smp_processor_id();
@@ -3387,37 +3518,12 @@ static void run_rebalance_domains(struct
 
 	rebalance_domains(this_cpu, idle);
 
-#ifdef CONFIG_NO_HZ
 	/*
-	 * If this cpu is the owner for idle load balancing, then do the
+	 * If this cpu has a pending nohz_balance_kick, then do the
 	 * balancing on behalf of the other idle cpus whose ticks are
 	 * stopped.
 	 */
-	if (this_rq->idle_at_tick &&
-	    atomic_read(&nohz.load_balancer) == this_cpu) {
-		struct rq *rq;
-		int balance_cpu;
-
-		for_each_cpu(balance_cpu, nohz.cpu_mask) {
-			if (balance_cpu == this_cpu)
-				continue;
-
-			/*
-			 * If this cpu gets work to do, stop the load balancing
-			 * work being done for other cpus. Next load
-			 * balancing owner will pick it up.
-			 */
-			if (need_resched())
-				break;
-
-			rebalance_domains(balance_cpu, CPU_IDLE);
-
-			rq = cpu_rq(balance_cpu);
-			if (time_after(this_rq->next_balance, rq->next_balance))
-				this_rq->next_balance = rq->next_balance;
-		}
-	}
-#endif
+	nohz_idle_balance(this_cpu, idle);
 }
 
 static inline int on_null_domain(int cpu)
@@ -3427,57 +3533,17 @@ static inline int on_null_domain(int cpu
 
 /*
  * Trigger the SCHED_SOFTIRQ if it is time to do periodic load balancing.
- *
- * In case of CONFIG_NO_HZ, this is the place where we nominate a new
- * idle load balancing owner or decide to stop the periodic load balancing,
- * if the whole system is idle.
  */
 static inline void trigger_load_balance(struct rq *rq, int cpu)
 {
-#ifdef CONFIG_NO_HZ
-	/*
-	 * If we were in the nohz mode recently and busy at the current
-	 * scheduler tick, then check if we need to nominate new idle
-	 * load balancer.
-	 */
-	if (rq->in_nohz_recently && !rq->idle_at_tick) {
-		rq->in_nohz_recently = 0;
-
-		if (atomic_read(&nohz.load_balancer) == cpu) {
-			cpumask_clear_cpu(cpu, nohz.cpu_mask);
-			atomic_set(&nohz.load_balancer, -1);
-		}
-
-		if (atomic_read(&nohz.load_balancer) == -1) {
-			int ilb = find_new_ilb(cpu);
-
-			if (ilb < nr_cpu_ids)
-				resched_cpu(ilb);
-		}
-	}
-
-	/*
-	 * If this cpu is idle and doing idle load balancing for all the
-	 * cpus with ticks stopped, is it time for that to stop?
-	 */
-	if (rq->idle_at_tick && atomic_read(&nohz.load_balancer) == cpu &&
-	    cpumask_weight(nohz.cpu_mask) == num_online_cpus()) {
-		resched_cpu(cpu);
-		return;
-	}
-
-	/*
-	 * If this cpu is idle and the idle load balancing is done by
-	 * someone else, then no need raise the SCHED_SOFTIRQ
-	 */
-	if (rq->idle_at_tick && atomic_read(&nohz.load_balancer) != cpu &&
-	    cpumask_test_cpu(cpu, nohz.cpu_mask))
-		return;
-#endif
 	/* Don't need to rebalance while attached to NULL domain */
 	if (time_after_eq(jiffies, rq->next_balance) &&
 	    likely(!on_null_domain(cpu)))
 		raise_softirq(SCHED_SOFTIRQ);
+#ifdef CONFIG_NO_HZ
+	else if (nohz_kick_needed(rq, cpu) && likely(!on_null_domain(cpu)))
+		nohz_balancer_kick(cpu);
+#endif
 }
 
 static void rq_online_fair(struct rq *rq)
kernel/sched.c +31 -3
Index: tip/kernel/sched.c
===================================================================
@@ -504,7 +504,7 @@ struct rq {
 	unsigned long cpu_load[CPU_LOAD_IDX_MAX];
 #ifdef CONFIG_NO_HZ
 	u64 nohz_stamp;
-	unsigned char in_nohz_recently;
+	unsigned char nohz_balance_kick;
 #endif
 	unsigned int skip_clock_update;
 
@@ -1202,6 +1202,27 @@ static void resched_cpu(int cpu)
 
 #ifdef CONFIG_NO_HZ
 /*
+ * In the semi idle case, use the nearest busy cpu for migrating timers
+ * from an idle cpu.  This is good for power-savings.
+ *
+ * We don't do similar optimization for completely idle system, as
+ * selecting an idle cpu will add more delays to the timers than intended
+ * (as that cpu's timer base may not be uptodate wrt jiffies etc).
+ */
+int get_nohz_timer_target(void)
+{
+	int cpu = smp_processor_id();
+	int i;
+	struct sched_domain *sd;
+
+	for_each_domain(cpu, sd) {
+		for_each_cpu(i, sched_domain_span(sd))
+			if (!idle_cpu(i))
+				return i;
+	}
+	return cpu;
+}
+/*
  * When add_timer_on() enqueues a timer into the timer wheel of an
  * idle CPU then this timer might expire before the next timer event
  * which is scheduled to wake up that CPU. In case of a completely
@@ -7604,6 +7625,10 @@ void __init sched_init(void)
 		rq->idle_stamp = 0;
 		rq->avg_idle = 2*sysctl_sched_migration_cost;
 		rq_attach_root(rq, &def_root_domain);
+#ifdef CONFIG_NO_HZ
+		rq->nohz_balance_kick = 0;
+		init_sched_softirq_csd(&per_cpu(remote_sched_softirq_cb, i));
+#endif
 #endif
 		init_rq_hrtick(rq);
 		atomic_set(&rq->nr_iowait, 0);
@@ -7648,8 +7673,11 @@ void __init sched_init(void)
 	zalloc_cpumask_var(&nohz_cpu_mask, GFP_NOWAIT);
 #ifdef CONFIG_SMP
 #ifdef CONFIG_NO_HZ
-	zalloc_cpumask_var(&nohz.cpu_mask, GFP_NOWAIT);
-	alloc_cpumask_var(&nohz.ilb_grp_nohz_mask, GFP_NOWAIT);
+	zalloc_cpumask_var(&nohz.idle_cpus_mask, GFP_NOWAIT);
+	alloc_cpumask_var(&nohz.grp_idle_mask, GFP_NOWAIT);
+	atomic_set(&nohz.load_balancer, nr_cpu_ids);
+	atomic_set(&nohz.first_pick_cpu, nr_cpu_ids);
+	atomic_set(&nohz.second_pick_cpu, nr_cpu_ids);
 #endif
 	/* May be allocated at isolcpus cmdline parse time */
 	if (cpu_isolated_map == NULL)
include/linux/sched.h +3 -6
Index: tip/include/linux/sched.h
===================================================================
@@ -272,14 +272,11 @@ extern void task_rq_unlock_wait(struct t
 
 extern cpumask_var_t nohz_cpu_mask;
 #if defined(CONFIG_SMP) && defined(CONFIG_NO_HZ)
-extern int select_nohz_load_balancer(int cpu);
-extern int get_nohz_load_balancer(void);
+extern void select_nohz_load_balancer(int stop_tick);
+extern int get_nohz_timer_target(void);
 extern int nohz_ratelimit(int cpu);
 #else
-static inline int select_nohz_load_balancer(int cpu)
-{
-	return 0;
-}
+static inline void select_nohz_load_balancer(int stop_tick) { }
 
 static inline int nohz_ratelimit(int cpu)
 {
kernel/hrtimer.c +2 -6
Index: tip/kernel/hrtimer.c
===================================================================
@@ -144,12 +144,8 @@ struct hrtimer_clock_base *lock_hrtimer_
 static int hrtimer_get_target(int this_cpu, int pinned)
 {
 #ifdef CONFIG_NO_HZ
-	if (!pinned && get_sysctl_timer_migration() && idle_cpu(this_cpu)) {
-		int preferred_cpu = get_nohz_load_balancer();
-
-		if (preferred_cpu >= 0)
-			return preferred_cpu;
-	}
+	if (!pinned && get_sysctl_timer_migration() && idle_cpu(this_cpu))
+		return get_nohz_timer_target();
 #endif
 	return this_cpu;
 }
kernel/time/tick-sched.c +1 -7
Index: tip/kernel/time/tick-sched.c
===================================================================
@@ -408,13 +408,7 @@ void tick_nohz_stop_sched_tick(int inidl
 		 * the scheduler tick in nohz_restart_sched_tick.
 		 */
 		if (!ts->tick_stopped) {
-			if (select_nohz_load_balancer(1)) {
-				/*
-				 * sched tick not stopped!
-				 */
-				cpumask_clear_cpu(cpu, nohz_cpu_mask);
-				goto out;
-			}
+			select_nohz_load_balancer(1);
 
 			ts->idle_tick = hrtimer_get_expires(&ts->sched_timer);
 			ts->tick_stopped = 1;
kernel/timer.c +2 -6
Index: tip/kernel/timer.c
===================================================================
@@ -679,12 +679,8 @@ __mod_timer(struct timer_list *timer, un
 	cpu = smp_processor_id();
 
 #if defined(CONFIG_NO_HZ) && defined(CONFIG_SMP)
-	if (!pinned && get_sysctl_timer_migration() && idle_cpu(cpu)) {
-		int preferred_cpu = get_nohz_load_balancer();
-
-		if (preferred_cpu >= 0)
-			cpu = preferred_cpu;
-	}
+	if (!pinned && get_sysctl_timer_migration() && idle_cpu(cpu))
+		cpu = get_nohz_timer_target();
 #endif
 	new_base = per_cpu(tvec_bases, cpu);
 
maintainer
#22 lore raw
Quoted 29 lines · Suresh Siddha

From: Venkatesh Pallipadi <[email protected]>
Subject: sched: Change nohz ilb logic from pull to push model

In the new push model, all idle CPUs indeed go into nohz mode. There is still the concept of idle load balancer (performing the load balancing on behalf of all the idle cpu's in the system). Busy CPU kicks the nohz balancer when any of the nohz CPUs need idle load balancing. The kickee CPU does the idle load balancing on behalf of all idle CPUs instead of the normal idle balance.

This addresses the below two problems with the current nohz ilb logic:
* the idle load balancer continued to have periodic ticks during idle and wokeup frequently, even though it did not have any rebalancing to do on behalf of any of the idle CPUs.
* On x86 and CPUs that have APIC timer stoppage on idle CPUs, this periodic wakeup can result in a periodic additional interrupt on a CPU doing the timer broadcast.

Also currently we are migrating the unpinned timers from an idle to the cpu doing idle load balancing (when all the cpus in the system are idle, there is no idle load balancing cpu and timers get added to the same idle cpu where the request was made. So the existing optimization works only on semi idle system).

And In semi idle system, we no longer have periodic ticks on the idle load balancer CPU. Using that cpu will add more delays to the timers than intended (as that cpu's timer base may not be uptodate wrt jiffies etc). This was causing mysterious slowdowns during boot etc.

Quoted 6 lines

For now, in the semi idle case, use the nearest busy cpu for migrating timers from an idle cpu. This is good for power-savings anyway.

---

I sorted the conflict with Venki's update_cpu_load() patch as below.

Thanks!

---

kernel/sched_fair.c +5 -30
Index: linux-2.6/kernel/sched_fair.c
===================================================================
@@ -3446,6 +3446,9 @@ static void nohz_idle_balance(int this_c
 			break;
 		}
 
+		raw_spin_lock_irq(&rq->lock);
+		update_cpu_load(rq);
+		raw_spin_unlock_irq(&rq->lock);
 		rebalance_domains(balance_cpu, CPU_IDLE);
 
 		rq = cpu_rq(balance_cpu);
@@ -3518,40 +3521,12 @@ static void run_rebalance_domains(struct
 
 	rebalance_domains(this_cpu, idle);
 
-#ifdef CONFIG_NO_HZ
 	/*
-	 * If this cpu is the owner for idle load balancing, then do the
+	 * If this cpu has a pending nohz_balance_kick, then do the
 	 * balancing on behalf of the other idle cpus whose ticks are
 	 * stopped.
 	 */
-	if (this_rq->idle_at_tick &&
-	    atomic_read(&nohz.load_balancer) == this_cpu) {
-		struct rq *rq;
-		int balance_cpu;
-
-		for_each_cpu(balance_cpu, nohz.cpu_mask) {
-			if (balance_cpu == this_cpu)
-				continue;
-
-			/*
-			 * If this cpu gets work to do, stop the load balancing
-			 * work being done for other cpus. Next load
-			 * balancing owner will pick it up.
-			 */
-			if (need_resched())
-				break;
-
-			rq = cpu_rq(balance_cpu);
-			raw_spin_lock_irq(&rq->lock);
-			update_cpu_load(rq);
-			raw_spin_unlock_irq(&rq->lock);
-			rebalance_domains(balance_cpu, CPU_IDLE);
-
-			if (time_after(this_rq->next_balance, rq->next_balance))
-				this_rq->next_balance = rq->next_balance;
-		}
-	}
-#endif
+	nohz_idle_balance(this_cpu, idle);
 }
 
 static inline int on_null_domain(int cpu)
#23 lore raw

[tip:sched/core] sched: Change nohz idle load balancing logic to push model

In reply to Suresh Siddha
Commit-ID:  83cd4fe27ad8446619b2e030b171b858501de87d
Gitweb:     http://git.kernel.org/tip/83cd4fe27ad8446619b2e030b171b858501de87d
Author:     Venkatesh Pallipadi <[email protected]>
AuthorDate: Fri, 21 May 2010 17:09:41 -0700
Committer:  Ingo Molnar <[email protected]>
CommitDate: Wed, 9 Jun 2010 10:34:52 +0200

sched: Change nohz idle load balancing logic to push model

In the new push model, all idle CPUs indeed go into nohz mode. There is still the concept of idle load balancer (performing the load balancing on behalf of all the idle cpu's in the system). Busy CPU kicks the nohz balancer when any of the nohz CPUs need idle load balancing. The kickee CPU does the idle load balancing on behalf of all idle CPUs instead of the normal idle balance.

This addresses the below two problems with the current nohz ilb logic:
* the idle load balancer continued to have periodic ticks during idle and wokeup frequently, even though it did not have any rebalancing to do on behalf of any of the idle CPUs.
* On x86 and CPUs that have APIC timer stoppage on idle CPUs, this periodic wakeup can result in a periodic additional interrupt on a CPU doing the timer broadcast.

Also currently we are migrating the unpinned timers from an idle to the cpu doing idle load balancing (when all the cpus in the system are idle, there is no idle load balancing cpu and timers get added to the same idle cpu where the request was made. So the existing optimization works only on semi idle system).

And In semi idle system, we no longer have periodic ticks on the idle load balancer CPU. Using that cpu will add more delays to the timers than intended (as that cpu's timer base may not be uptodate wrt jiffies etc). This was causing mysterious slowdowns during boot etc.

For now, in the semi idle case, use the nearest busy cpu for migrating timers from an idle cpu. This is good for power-savings anyway.

LKML-Reference: <[email protected]>

---
 include/linux/sched.h    |    9 +-
 kernel/hrtimer.c         |    8 +-
 kernel/sched.c           |   34 +++++-
 kernel/sched_fair.c      |  329 ++++++++++++++++++++++++++++------------------
 kernel/time/tick-sched.c |    8 +-
 kernel/timer.c           |    8 +-
 6 files changed, 237 insertions(+), 159 deletions(-)
include/linux/sched.h +3 -6
index c2d4316..a3e5b1c 100644
@@ -271,14 +271,11 @@ extern int runqueue_is_locked(int cpu);
 
 extern cpumask_var_t nohz_cpu_mask;
 #if defined(CONFIG_SMP) && defined(CONFIG_NO_HZ)
-extern int select_nohz_load_balancer(int cpu);
-extern int get_nohz_load_balancer(void);
+extern void select_nohz_load_balancer(int stop_tick);
+extern int get_nohz_timer_target(void);
 extern int nohz_ratelimit(int cpu);
 #else
-static inline int select_nohz_load_balancer(int cpu)
-{
-	return 0;
-}
+static inline void select_nohz_load_balancer(int stop_tick) { }
 
 static inline int nohz_ratelimit(int cpu)
 {
kernel/hrtimer.c +2 -6
index 5c69e99..e934339 100644
@@ -144,12 +144,8 @@ struct hrtimer_clock_base *lock_hrtimer_base(const struct hrtimer *timer,
 static int hrtimer_get_target(int this_cpu, int pinned)
 {
 #ifdef CONFIG_NO_HZ
-	if (!pinned && get_sysctl_timer_migration() && idle_cpu(this_cpu)) {
-		int preferred_cpu = get_nohz_load_balancer();
-
-		if (preferred_cpu >= 0)
-			return preferred_cpu;
-	}
+	if (!pinned && get_sysctl_timer_migration() && idle_cpu(this_cpu))
+		return get_nohz_timer_target();
 #endif
 	return this_cpu;
 }
kernel/sched.c +31 -3
index a757f6b..132950b 100644
@@ -460,7 +460,7 @@ struct rq {
 	unsigned long last_load_update_tick;
 #ifdef CONFIG_NO_HZ
 	u64 nohz_stamp;
-	unsigned char in_nohz_recently;
+	unsigned char nohz_balance_kick;
 #endif
 	unsigned int skip_clock_update;
 
@@ -1195,6 +1195,27 @@ static void resched_cpu(int cpu)
 
 #ifdef CONFIG_NO_HZ
 /*
+ * In the semi idle case, use the nearest busy cpu for migrating timers
+ * from an idle cpu.  This is good for power-savings.
+ *
+ * We don't do similar optimization for completely idle system, as
+ * selecting an idle cpu will add more delays to the timers than intended
+ * (as that cpu's timer base may not be uptodate wrt jiffies etc).
+ */
+int get_nohz_timer_target(void)
+{
+	int cpu = smp_processor_id();
+	int i;
+	struct sched_domain *sd;
+
+	for_each_domain(cpu, sd) {
+		for_each_cpu(i, sched_domain_span(sd))
+			if (!idle_cpu(i))
+				return i;
+	}
+	return cpu;
+}
+/*
  * When add_timer_on() enqueues a timer into the timer wheel of an
  * idle CPU then this timer might expire before the next timer event
  * which is scheduled to wake up that CPU. In case of a completely
@@ -7791,6 +7812,10 @@ void __init sched_init(void)
 		rq->idle_stamp = 0;
 		rq->avg_idle = 2*sysctl_sched_migration_cost;
 		rq_attach_root(rq, &def_root_domain);
+#ifdef CONFIG_NO_HZ
+		rq->nohz_balance_kick = 0;
+		init_sched_softirq_csd(&per_cpu(remote_sched_softirq_cb, i));
+#endif
 #endif
 		init_rq_hrtick(rq);
 		atomic_set(&rq->nr_iowait, 0);
@@ -7835,8 +7860,11 @@ void __init sched_init(void)
 	zalloc_cpumask_var(&nohz_cpu_mask, GFP_NOWAIT);
 #ifdef CONFIG_SMP
 #ifdef CONFIG_NO_HZ
-	zalloc_cpumask_var(&nohz.cpu_mask, GFP_NOWAIT);
-	alloc_cpumask_var(&nohz.ilb_grp_nohz_mask, GFP_NOWAIT);
+	zalloc_cpumask_var(&nohz.idle_cpus_mask, GFP_NOWAIT);
+	alloc_cpumask_var(&nohz.grp_idle_mask, GFP_NOWAIT);
+	atomic_set(&nohz.load_balancer, nr_cpu_ids);
+	atomic_set(&nohz.first_pick_cpu, nr_cpu_ids);
+	atomic_set(&nohz.second_pick_cpu, nr_cpu_ids);
 #endif
 	/* May be allocated at isolcpus cmdline parse time */
 	if (cpu_isolated_map == NULL)
kernel/sched_fair.c +198 -131

448 lines not on this page · raw message

kernel/time/tick-sched.c +1 -7
index 1d7b9bc..5f171f0 100644
@@ -408,13 +408,7 @@ void tick_nohz_stop_sched_tick(int inidle)
 		 * the scheduler tick in nohz_restart_sched_tick.
 		 */
 		if (!ts->tick_stopped) {
-			if (select_nohz_load_balancer(1)) {
-				/*
-				 * sched tick not stopped!
-				 */
-				cpumask_clear_cpu(cpu, nohz_cpu_mask);
-				goto out;
-			}
+			select_nohz_load_balancer(1);
 
 			ts->idle_tick = hrtimer_get_expires(&ts->sched_timer);
 			ts->tick_stopped = 1;
kernel/timer.c +2 -6
index ee305c8..48d6aec 100644
@@ -679,12 +679,8 @@ __mod_timer(struct timer_list *timer, unsigned long expires,
 	cpu = smp_processor_id();
 
 #if defined(CONFIG_NO_HZ) && defined(CONFIG_SMP)
-	if (!pinned && get_sysctl_timer_migration() && idle_cpu(cpu)) {
-		int preferred_cpu = get_nohz_load_balancer();
-
-		if (preferred_cpu >= 0)
-			cpu = preferred_cpu;
-	}
+	if (!pinned && get_sysctl_timer_migration() && idle_cpu(cpu))
+		cpu = get_nohz_timer_target();
 #endif
 	new_base = per_cpu(tvec_bases, cpu);
 
#24 lore raw
In reply to Suresh Siddha

Hi.

I finally found the time to give this patch series a try. Minor updates were required, but I'm now running it against 2.6.34.

"Load balancing tick" is still number one in my powertop list of top causes of wakeups (sitting at ~60 to 80 per second as I type this, with ~170 wakeups per second total). Comparing this to the numbers I posted earlier, we seem to have a win.

I do wonder, though, whether further work could still be done. If I take one core offline, for example, I'm still getting load balancing ticks. Intuitively, I'd expect there to be no need for them with only one core available. But maybe I'm just ignorant of what's going on.

Regards,

Nigel

#25 lore raw

Hey,

Quoted 9 lines · Nigel Cunningham

"Load balancing tick" is still number one in my powertop list of top causes of wakeups (sitting at ~60 to 80 per second as I type this, with ~170 wakeups per second total). Comparing this to the numbers I posted earlier, we seem to have a win.

I do wonder, though, whether further work could still be done. If I take one core offline, for example, I'm still getting load balancing ticks. Intuitively, I'd expect there to be no need for them with only one core available. But maybe I'm just ignorant of what's going on.

Are you using HZ=1000, and is the CPU active ~ 6-8 % ? If so, is it just the regular timer tick while the CPU is active, and so not a real "wakeup"? (Or possibly double the number if both CPUs are active)

Best,
Dominik

#26 lore raw

Hi.

Quoted 8 lines · Dominik Brodowski

Hey,

Quoted 5 lines · Nigel Cunningham

"Load balancing tick" is still number one in my powertop list of top causes of wakeups (sitting at ~60 to 80 per second as I type this, with ~170 wakeups per second total). Comparing this to the numbers I posted earlier, we seem to have a win.

Quoted 8 lines
Quoted 4 lines

I do wonder, though, whether further work could still be done. If I take one core offline, for example, I'm still getting load balancing ticks. Intuitively, I'd expect there to be no need for them with only one core available. But maybe I'm just ignorant of what's going on.

Are you using HZ=1000, and is the CPU active ~ 6-8 % ? If so, is it just the regular timer tick while the CPU is active, and so not a real "wakeup"? (Or possibly double the number if both CPUs are active)

HZ is 1000, and the CPU running percentage in Powertop is low (2% when I'm not typing).

Regards,

Nigel

#27 lore raw

Hey

Quoted 14 lines · Nigel Cunningham
Quoted 13 lines · Dominik Brodowski

Hey,

Quoted 9 lines · Nigel Cunningham

"Load balancing tick" is still number one in my powertop list of top causes of wakeups (sitting at ~60 to 80 per second as I type this, with ~170 wakeups per second total). Comparing this to the numbers I posted earlier, we seem to have a win.

I do wonder, though, whether further work could still be done. If I take one core offline, for example, I'm still getting load balancing ticks. Intuitively, I'd expect there to be no need for them with only one core available. But maybe I'm just ignorant of what's going on.

Quoted 6 lines
Quoted 3 lines

Are you using HZ=1000, and is the CPU active ~ 6-8 % ? If so, is it just the regular timer tick while the CPU is active, and so not a real "wakeup"? (Or possibly double the number if both CPUs are active)

HZ is 1000, and the CPU running percentage in Powertop is low (2% when I'm not typing).

Still, that'd count for up to 4 % of the reported ticks. On my system, this phenomenon accounts pretty much for the events powertop calls "load balancin ticks". I wonder whether user- or kernelspace should be more smart to not consider something a wakeup event if it wasn't a wakeup, i.e. to ignore timer events from timer_stat / powertop if the CPU wasn't actually idle...

Best,
Dominik