[PATCH] fix init_idle() locking problem

[PATCH] fix init_idle() locking problem

[Bjorn Helgaas]

When starting up secondary CPUs, most architectures do something
like this:

	do_boot_cpu(int cpu)
	{
		idle = fork_by_hand();
		wake_up_forked_process(idle);
		init_idle(idle, cpu);

init_idle() removes "idle" from its runqueue, but there's a window
between looking up the runqueue and locking it, where another CPU
can move "idle" to a different runqueue, i.e., via load_balance().

This is based on 2.6.6.

===== kernel/sched.c 1.261 vs edited =====
--- 1.261/kernel/sched.c	Mon Apr 26 23:07:43 2004
+++ edited/kernel/sched.c	Mon May 10 09:59:54 2004
@@ -2660,11 +2660,18 @@
 
 void __init init_idle(task_t *idle, int cpu)
 {
-	runqueue_t *idle_rq = cpu_rq(cpu), *rq = cpu_rq(task_cpu(idle));
+	runqueue_t *idle_rq = cpu_rq(cpu), *rq;
 	unsigned long flags;
 
+repeat_lock_runqueues:
+	rq = task_rq(idle);
 	local_irq_save(flags);
 	double_rq_lock(idle_rq, rq);
+	if (rq != task_rq(idle)) {
+		double_rq_unlock(idle_rq, rq);
+		local_irq_restore(flags);
+		goto repeat_lock_runqueues;
+	}
 
 	idle_rq->curr = idle_rq->idle = idle;
 	deactivate_task(idle, rq);

Re: [PATCH] fix init_idle() locking problem

[Ingo Molnar]

* Bjorn Helgaas <bjorn.helgaas@hp.com> wrote:

> When starting up secondary CPUs, most architectures do something like
> this:
> 
> 	do_boot_cpu(int cpu)
> 	{
> 		idle = fork_by_hand();
> 		wake_up_forked_process(idle);
> 		init_idle(idle, cpu);
> 
> init_idle() removes "idle" from its runqueue, but there's a window
> between looking up the runqueue and locking it, where another CPU can
> move "idle" to a different runqueue, i.e., via load_balance().

the sched-domains patches that are now in BK solve this problem in a
cleaner way: the rule is that no cross-CPU balancing is allowed until
all CPUs have booted up.

This is enforced by having a boot-time sched-domains tree (initialized
very early on, prior setting up any IRQ sources, in sched_init()), that
isolates each and every CPU from each other - so load_balance() cannot
balance away an idle task. Once all CPUs have booted up the arch can
'cross-connect' all the CPUs and scheduling will begin for real.

this two-phase approach enabled us to reduce alot of the early-boot
scheduling nastiness.

[ btw., your patch does not seem to be correct anyway - if an online CPU
'steals' the new idle task then it will also most likely run it - and
that is disastrous for any CLONE_IDLETASK task. (e.g. on x86 the EIP has
random content, most likely crashing that CPU.) ]

the hotplug CPU code of course must be (and is) extra careful about
installing the new idle task.

	Ingo

Re: [PATCH] fix init_idle() locking problem

[Bjorn Helgaas]

On Tuesday 11 May 2004 3:39 am, Ingo Molnar wrote:
> * Bjorn Helgaas <bjorn.helgaas@hp.com> wrote:
> > init_idle() removes "idle" from its runqueue, but there's a window
> > between looking up the runqueue and locking it, where another CPU can
> > move "idle" to a different runqueue, i.e., via load_balance().
> 
> the sched-domains patches that are now in BK solve this problem in a
> cleaner way: the rule is that no cross-CPU balancing is allowed until
> all CPUs have booted up.

Thanks for fixing this the right way.  I'll try it out in the next couple
days.  Nice coincidence that all the sched-domains stuff went in the
same day :-)

> [ btw., your patch does not seem to be correct anyway - if an online CPU
> 'steals' the new idle task then it will also most likely run it - and
> that is disastrous for any CLONE_IDLETASK task. (e.g. on x86 the EIP has
> random content, most likely crashing that CPU.) ]

I'm sure my patch wasn't complete, but it did address something
that still looks strange to me.  The current code is:

	void __init init_idle(task_t *idle, int cpu)
	{
	        runqueue_t *idle_rq = cpu_rq(cpu), *rq = cpu_rq(task_cpu(idle));
	        unsigned long flags;

	        local_irq_save(flags);
	        double_rq_lock(idle_rq, rq);

	        idle_rq->curr = idle_rq->idle = idle;

The fact that we look up the runqueue, lock it, and use it without
rechecking that we got the correct one certainly is suspicious at
the micro point of view.

But, if you say this window is not a problem anymore because of the
larger design, I'll take your word for it.

Bjorn