Use tasklet to balance sched domains.

Call rebalance_tick (renamed to rebalance_domains) from a tasklet.

We calculate the earliest time for each layer of sched domains to be
rescanned (this is the rescan time for idle) and use the earliest
of those to schedule the tasklet again via a new field "next_balance"
added to struct rq.

Note that using a tasklet serialized load balancing for the whole system.
Timer interrupts are staggered. If load balancing finishes before
the next timer interrupt occurs (very likely) then load balancing
will happen as before.

However, if load balancing takes too much time then we will only
let one load balance run at a time. The processors that were not
able to load balance will continue to attempt to run tasklet_schedule()
from scheduler_tick() on each clock tick until they are successful.

Serializing load balancing like this avoids concurrent scans over
processors and avoids lock contention.

In a system that is particularly slow or that has lots of processors
this may result in load balancing becoming serialized for good.

Signed-off-by: Christoph Lameter <clameter@sgi.com>

Index: linux-2.6.19-rc4-mm2/kernel/sched.c
===================================================================
--- linux-2.6.19-rc4-mm2.orig/kernel/sched.c	2006-11-10 22:42:39.000000000 -0600
+++ linux-2.6.19-rc4-mm2/kernel/sched.c	2006-11-10 22:44:56.749870566 -0600
@@ -228,6 +228,7 @@ struct rq {
 	unsigned long expired_timestamp;
 	unsigned long long timestamp_last_tick;
 	struct task_struct *curr, *idle;
+	unsigned long next_balance;
 	struct mm_struct *prev_mm;
 	struct prio_array *active, *expired, arrays[2];
 	int best_expired_prio;
@@ -2842,7 +2843,8 @@ static void update_load(struct rq *this_
 }
 
 /*
- * rebalance_tick will get called every timer tick, on every CPU.
+ * rebalance_domains is triggered when needed via a tasklet from the
+ * scheduler tick.
  *
  * It checks each scheduling domain to see if it is due to be balanced,
  * and initiates a balancing operation if so.
@@ -2850,9 +2852,10 @@ static void update_load(struct rq *this_
  * Balancing parameters are set up in arch_init_sched_domains.
  */
 
-static void
-rebalance_tick(int this_cpu, struct rq *this_rq)
+static void rebalance_domains(unsigned long dummy)
 {
+	int this_cpu = smp_processor_id();
+	struct rq *this_rq = cpu_rq(this_cpu);
 	unsigned long interval;
 	struct sched_domain *sd;
 	/*
@@ -2861,6 +2864,8 @@ rebalance_tick(int this_cpu, struct rq *
 	 */
 	enum idle_type idle = !this_rq->nr_running ?
 				SCHED_IDLE : NOT_IDLE;
+	/* Earliest time when we have to call rebalance_domains again */
+	unsigned long next_balance = jiffies + 60*HZ;
 
 	for_each_domain(this_cpu, sd) {
 		if (!(sd->flags & SD_LOAD_BALANCE))
@@ -2886,8 +2891,13 @@ rebalance_tick(int this_cpu, struct rq *
 			}
 			sd->last_balance += interval;
 		}
+		next_balance = min(next_balance,
+				sd->last_balance + sd->balance_interval);
 	}
+	this_rq->next_balance = next_balance;
 }
+
+DECLARE_TASKLET(rebalance, &rebalance_domains, 0L);
 #else
 /*
  * on UP we do not need to balance between CPUs:
@@ -3139,7 +3149,8 @@ void scheduler_tick(void)
 		task_running_tick(rq, p);
 #ifdef CONFIG_SMP
 	update_load(rq);
-	rebalance_tick(cpu, rq);
+	if (jiffies >= rq->next_balance)
+		tasklet_schedule(&rebalance);
 #endif
 }