[PATCH] generic-ipi: fix deadlock in __smp_call_function_single

[PATCH] generic-ipi: fix deadlock in __smp_call_function_single

[Heiko Carstens]

From: Heiko Carstens <heiko.carstens@de.ibm.com>

Just got my 6 way machine to a state where cpu 0 is in an endless loop
within __smp_call_function_single.
All other cpus are idle.

The call trace on cpu 0 looks like this:

__smp_call_function_single
scheduler_tick
update_process_times
tick_sched_timer
__run_hrtimer
hrtimer_interrupt
clock_comparator_work
do_extint
ext_int_handler
----> timer irq
cpu_idle

__smp_call_function_single got called from nohz_balancer_kick (inlined)
with the remote cpu being 1, wait being 0 and the per cpu variable
remote_sched_softirq_cb (call_single_data) of the current cpu (0).

Then it loops forever when it tries to grab the lock of the
call_single_data, since it is already locked and enqueued on cpu 0.

My theory how this could have happened: for some reason the scheduler
decided to call __smp_call_function_single on it's own cpu, and sends
an IPI to itself. The interrupt stays pending since IRQs are disabled.
If then the hypervisor schedules the cpu away it might happen that upon
rescheduling both the IPI and the timer IRQ are pending.
If then interrupts are enabled again it depends which one gets scheduled
first.
If the timer interrupt gets delivered first we end up with the local
deadlock as seen in the calltrace above.

Let's make __smp_call_function_single check if the target cpu is the
current cpu and execute the function immediately just like
smp_call_function_single does. That should prevent at least the
scenario described here.

It might also be that the scheduler is not supposed to call
__smp_call_function_single with the remote cpu being the current cpu,
but that is a different issue.

Signed-off-by: Heiko Carstens <heiko.carstens@de.ibm.com>
---
 kernel/smp.c |   14 ++++++++++++--
 1 file changed, 12 insertions(+), 2 deletions(-)

diff --git a/kernel/smp.c b/kernel/smp.c
index 75c970c..f1427d8 100644
--- a/kernel/smp.c
+++ b/kernel/smp.c
@@ -376,8 +376,10 @@ EXPORT_SYMBOL_GPL(smp_call_function_any);
 void __smp_call_function_single(int cpu, struct call_single_data *data,
 				int wait)
 {
-	csd_lock(data);
+	unsigned int this_cpu;
+	unsigned long flags;
 
+	this_cpu = get_cpu();
 	/*
 	 * Can deadlock when called with interrupts disabled.
 	 * We allow cpu's that are not yet online though, as no one else can
@@ -387,7 +389,15 @@ void __smp_call_function_single(int cpu, struct call_single_data *data,
 	WARN_ON_ONCE(cpu_online(smp_processor_id()) && wait && irqs_disabled()
 		     && !oops_in_progress);
 
-	generic_exec_single(cpu, data, wait);
+	if (cpu == this_cpu) {
+		local_irq_save(flags);
+		data->func(data->info);
+		local_irq_restore(flags);
+	} else {
+		csd_lock(data);
+		generic_exec_single(cpu, data, wait);
+	}
+	put_cpu();
 }
 
 /**

Re: [PATCH] generic-ipi: fix deadlock in __smp_call_function_single

[Peter Zijlstra]

On Thu, 2010-09-09 at 15:50 +0200, Heiko Carstens wrote:
> From: Heiko Carstens <heiko.carstens@de.ibm.com>
> 
> Just got my 6 way machine to a state where cpu 0 is in an endless loop
> within __smp_call_function_single.
> All other cpus are idle.
> 
> The call trace on cpu 0 looks like this:
> 
> __smp_call_function_single
> scheduler_tick
> update_process_times
> tick_sched_timer
> __run_hrtimer
> hrtimer_interrupt
> clock_comparator_work
> do_extint
> ext_int_handler
> ----> timer irq
> cpu_idle
> 
> __smp_call_function_single got called from nohz_balancer_kick (inlined)
> with the remote cpu being 1, wait being 0 and the per cpu variable
> remote_sched_softirq_cb (call_single_data) of the current cpu (0).
> 
> Then it loops forever when it tries to grab the lock of the
> call_single_data, since it is already locked and enqueued on cpu 0.
> 
> My theory how this could have happened: for some reason the scheduler
> decided to call __smp_call_function_single on it's own cpu, and sends
> an IPI to itself. The interrupt stays pending since IRQs are disabled.
> If then the hypervisor schedules the cpu away it might happen that upon
> rescheduling both the IPI and the timer IRQ are pending.
> If then interrupts are enabled again it depends which one gets scheduled
> first.
> If the timer interrupt gets delivered first we end up with the local
> deadlock as seen in the calltrace above.
> 
> Let's make __smp_call_function_single check if the target cpu is the
> current cpu and execute the function immediately just like
> smp_call_function_single does. That should prevent at least the
> scenario described here.
> 
> It might also be that the scheduler is not supposed to call
> __smp_call_function_single with the remote cpu being the current cpu,
> but that is a different issue.
> 
> Signed-off-by: Heiko Carstens <heiko.carstens@de.ibm.com>

Right, so it looks like all other users of __smp_call_function_single()
do indeed ensure not to call it on self, but your patch does make sense.

Acked-by: Peter Zijlstra <a.p.zijlstra@chello.nl>

> ---
>  kernel/smp.c |   14 ++++++++++++--
>  1 file changed, 12 insertions(+), 2 deletions(-)
> 
> diff --git a/kernel/smp.c b/kernel/smp.c
> index 75c970c..f1427d8 100644
> --- a/kernel/smp.c
> +++ b/kernel/smp.c
> @@ -376,8 +376,10 @@ EXPORT_SYMBOL_GPL(smp_call_function_any);
>  void __smp_call_function_single(int cpu, struct call_single_data *data,
>  				int wait)
>  {
> -	csd_lock(data);
> +	unsigned int this_cpu;
> +	unsigned long flags;
>  
> +	this_cpu = get_cpu();
>  	/*
>  	 * Can deadlock when called with interrupts disabled.
>  	 * We allow cpu's that are not yet online though, as no one else can
> @@ -387,7 +389,15 @@ void __smp_call_function_single(int cpu, struct call_single_data *data,
>  	WARN_ON_ONCE(cpu_online(smp_processor_id()) && wait && irqs_disabled()
>  		     && !oops_in_progress);
>  
> -	generic_exec_single(cpu, data, wait);
> +	if (cpu == this_cpu) {
> +		local_irq_save(flags);
> +		data->func(data->info);
> +		local_irq_restore(flags);
> +	} else {
> +		csd_lock(data);
> +		generic_exec_single(cpu, data, wait);
> +	}
> +	put_cpu();
>  }
>  
>  /**

Re: [PATCH] generic-ipi: fix deadlock in __smp_call_function_single

[Jens Axboe]

On 2010-09-10 13:06, Peter Zijlstra wrote:
> On Thu, 2010-09-09 at 15:50 +0200, Heiko Carstens wrote:
>> From: Heiko Carstens <heiko.carstens@de.ibm.com>
>>
>> Just got my 6 way machine to a state where cpu 0 is in an endless loop
>> within __smp_call_function_single.
>> All other cpus are idle.
>>
>> The call trace on cpu 0 looks like this:
>>
>> __smp_call_function_single
>> scheduler_tick
>> update_process_times
>> tick_sched_timer
>> __run_hrtimer
>> hrtimer_interrupt
>> clock_comparator_work
>> do_extint
>> ext_int_handler
>> ----> timer irq
>> cpu_idle
>>
>> __smp_call_function_single got called from nohz_balancer_kick (inlined)
>> with the remote cpu being 1, wait being 0 and the per cpu variable
>> remote_sched_softirq_cb (call_single_data) of the current cpu (0).
>>
>> Then it loops forever when it tries to grab the lock of the
>> call_single_data, since it is already locked and enqueued on cpu 0.
>>
>> My theory how this could have happened: for some reason the scheduler
>> decided to call __smp_call_function_single on it's own cpu, and sends
>> an IPI to itself. The interrupt stays pending since IRQs are disabled.
>> If then the hypervisor schedules the cpu away it might happen that upon
>> rescheduling both the IPI and the timer IRQ are pending.
>> If then interrupts are enabled again it depends which one gets scheduled
>> first.
>> If the timer interrupt gets delivered first we end up with the local
>> deadlock as seen in the calltrace above.
>>
>> Let's make __smp_call_function_single check if the target cpu is the
>> current cpu and execute the function immediately just like
>> smp_call_function_single does. That should prevent at least the
>> scenario described here.
>>
>> It might also be that the scheduler is not supposed to call
>> __smp_call_function_single with the remote cpu being the current cpu,
>> but that is a different issue.
>>
>> Signed-off-by: Heiko Carstens <heiko.carstens@de.ibm.com>
> 
> Right, so it looks like all other users of __smp_call_function_single()
> do indeed ensure not to call it on self, but your patch does make sense.

I guess it depends on whether how bullet proof you want that (core) API
to be. We've traditionally had this kind of support in similar functions
so the caller doesn't have to check, so I guess the patch is fine with
me too.

For extra credit, the function documentation should be modified as well:

 * __smp_call_function_single(): Run a function on another CPU

Acked-by: Jens Axboe <jaxboe@fusionio.com>

-- 
Jens Axboe

Re: [PATCH] generic-ipi: fix deadlock in __smp_call_function_single

[Heiko Carstens]

On Fri, Sep 10, 2010 at 01:23:07PM +0200, Jens Axboe wrote:
> On 2010-09-10 13:06, Peter Zijlstra wrote:
> > Right, so it looks like all other users of __smp_call_function_single()
> > do indeed ensure not to call it on self, but your patch does make sense.
> 
> I guess it depends on whether how bullet proof you want that (core) API
> to be. We've traditionally had this kind of support in similar functions
> so the caller doesn't have to check, so I guess the patch is fine with
> me too.
> 
> For extra credit, the function documentation should be modified as well:
> 
>  * __smp_call_function_single(): Run a function on another CPU

Upated patch below. I also added documentation for the wait flag.


Subject: [PATCH] generic-ipi: fix deadlock in __smp_call_function_single

From: Heiko Carstens <heiko.carstens@de.ibm.com>

Just got my 6 way machine to a state where cpu 0 is in an endless loop
within __smp_call_function_single.
All other cpus are idle.

The call trace on cpu 0 looks like this:

__smp_call_function_single
scheduler_tick
update_process_times
tick_sched_timer
__run_hrtimer
hrtimer_interrupt
clock_comparator_work
do_extint
ext_int_handler
----> timer irq
cpu_idle

__smp_call_function_single got called from nohz_balancer_kick (inlined)
with the remote cpu being 1, wait being 0 and the per cpu variable
remote_sched_softirq_cb (call_single_data) of the current cpu (0).

Then it loops forever when it tries to grab the lock of the
call_single_data, since it is already locked and enqueued on cpu 0.

My theory how this could have happened: for some reason the scheduler
decided to call __smp_call_function_single on it's own cpu, and sends
an IPI to itself. The interrupt stays pending since IRQs are disabled.
If then the hypervisor schedules the cpu away it might happen that upon
rescheduling both the IPI and the timer IRQ are pending.
If then interrupts are enabled again it depends which one gets scheduled
first.
If the timer interrupt gets delivered first we end up with the local
deadlock as seen in the calltrace above.

Let's make __smp_call_function_single check if the target cpu is the
current cpu and execute the function immediately just like
smp_call_function_single does. That should prevent at least the
scenario described here.

It might also be that the scheduler is not supposed to call
__smp_call_function_single with the remote cpu being the current cpu,
but that is a different issue.

Acked-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Acked-by: Jens Axboe <jaxboe@fusionio.com>
Signed-off-by: Heiko Carstens <heiko.carstens@de.ibm.com>
---
 kernel/smp.c |   17 ++++++++++++++---
 1 file changed, 14 insertions(+), 3 deletions(-)

diff --git a/kernel/smp.c b/kernel/smp.c
index 75c970c..ed6aacf 100644
--- a/kernel/smp.c
+++ b/kernel/smp.c
@@ -365,9 +365,10 @@ call:
 EXPORT_SYMBOL_GPL(smp_call_function_any);
 
 /**
- * __smp_call_function_single(): Run a function on another CPU
+ * __smp_call_function_single(): Run a function on a specific CPU
  * @cpu: The CPU to run on.
  * @data: Pre-allocated and setup data structure
+ * @wait: If true, wait until function has completed on specified CPU.
  *
  * Like smp_call_function_single(), but allow caller to pass in a
  * pre-allocated data structure. Useful for embedding @data inside
@@ -376,8 +377,10 @@ EXPORT_SYMBOL_GPL(smp_call_function_any);
 void __smp_call_function_single(int cpu, struct call_single_data *data,
 				int wait)
 {
-	csd_lock(data);
+	unsigned int this_cpu;
+	unsigned long flags;
 
+	this_cpu = get_cpu();
 	/*
 	 * Can deadlock when called with interrupts disabled.
 	 * We allow cpu's that are not yet online though, as no one else can
@@ -387,7 +390,15 @@ void __smp_call_function_single(int cpu, struct call_single_data *data,
 	WARN_ON_ONCE(cpu_online(smp_processor_id()) && wait && irqs_disabled()
 		     && !oops_in_progress);
 
-	generic_exec_single(cpu, data, wait);
+	if (cpu == this_cpu) {
+		local_irq_save(flags);
+		data->func(data->info);
+		local_irq_restore(flags);
+	} else {
+		csd_lock(data);
+		generic_exec_single(cpu, data, wait);
+	}
+	put_cpu();
 }
 
 /**

[tip:core/urgent] generic-ipi: Fix deadlock in __smp_call_function_single

[tip-bot for Heiko Carstens]

Commit-ID:  27c379f7f89a4d558c685b5d89b5ba2fe79ae701
Gitweb:     http://git.kernel.org/tip/27c379f7f89a4d558c685b5d89b5ba2fe79ae701
Author:     Heiko Carstens <heiko.carstens@de.ibm.com>
AuthorDate: Fri, 10 Sep 2010 13:47:29 +0200
Committer:  Ingo Molnar <mingo@elte.hu>
CommitDate: Fri, 10 Sep 2010 16:48:40 +0200

generic-ipi: Fix deadlock in __smp_call_function_single

Just got my 6 way machine to a state where cpu 0 is in an
endless loop within __smp_call_function_single.
All other cpus are idle.

The call trace on cpu 0 looks like this:

 __smp_call_function_single
 scheduler_tick
 update_process_times
 tick_sched_timer
 __run_hrtimer
 hrtimer_interrupt
 clock_comparator_work
 do_extint
 ext_int_handler
 ----> timer irq
 cpu_idle

__smp_call_function_single() got called from nohz_balancer_kick()
(inlined) with the remote cpu being 1, wait being 0 and the per
cpu variable remote_sched_softirq_cb (call_single_data) of the
current cpu (0).

Then it loops forever when it tries to grab the lock of the
call_single_data, since it is already locked and enqueued on cpu 0.

My theory how this could have happened: for some reason the
scheduler decided to call __smp_call_function_single() on it's own
cpu, and sends an IPI to itself. The interrupt stays pending
since IRQs are disabled. If then the hypervisor schedules the
cpu away it might happen that upon rescheduling both the IPI and
the timer IRQ are pending. If then interrupts are enabled again
it depends which one gets scheduled first.
If the timer interrupt gets delivered first we end up with the
local deadlock as seen in the calltrace above.

Let's make __smp_call_function_single() check if the target cpu is
the current cpu and execute the function immediately just like
smp_call_function_single does. That should prevent at least the
scenario described here.

It might also be that the scheduler is not supposed to call
__smp_call_function_single with the remote cpu being the current
cpu, but that is a different issue.

Signed-off-by: Heiko Carstens <heiko.carstens@de.ibm.com>
Acked-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Acked-by: Jens Axboe <jaxboe@fusionio.com>
Cc: Venkatesh Pallipadi <venki@google.com>
Cc: Suresh Siddha <suresh.b.siddha@intel.com>
LKML-Reference: <20100910114729.GB2827@osiris.boeblingen.de.ibm.com>
Signed-off-by: Ingo Molnar <mingo@elte.hu>
---
 kernel/smp.c |   17 ++++++++++++++---
 1 files changed, 14 insertions(+), 3 deletions(-)

diff --git a/kernel/smp.c b/kernel/smp.c
index 75c970c..ed6aacf 100644
--- a/kernel/smp.c
+++ b/kernel/smp.c
@@ -365,9 +365,10 @@ call:
 EXPORT_SYMBOL_GPL(smp_call_function_any);
 
 /**
- * __smp_call_function_single(): Run a function on another CPU
+ * __smp_call_function_single(): Run a function on a specific CPU
  * @cpu: The CPU to run on.
  * @data: Pre-allocated and setup data structure
+ * @wait: If true, wait until function has completed on specified CPU.
  *
  * Like smp_call_function_single(), but allow caller to pass in a
  * pre-allocated data structure. Useful for embedding @data inside
@@ -376,8 +377,10 @@ EXPORT_SYMBOL_GPL(smp_call_function_any);
 void __smp_call_function_single(int cpu, struct call_single_data *data,
 				int wait)
 {
-	csd_lock(data);
+	unsigned int this_cpu;
+	unsigned long flags;
 
+	this_cpu = get_cpu();
 	/*
 	 * Can deadlock when called with interrupts disabled.
 	 * We allow cpu's that are not yet online though, as no one else can
@@ -387,7 +390,15 @@ void __smp_call_function_single(int cpu, struct call_single_data *data,
 	WARN_ON_ONCE(cpu_online(smp_processor_id()) && wait && irqs_disabled()
 		     && !oops_in_progress);
 
-	generic_exec_single(cpu, data, wait);
+	if (cpu == this_cpu) {
+		local_irq_save(flags);
+		data->func(data->info);
+		local_irq_restore(flags);
+	} else {
+		csd_lock(data);
+		generic_exec_single(cpu, data, wait);
+	}
+	put_cpu();
 }
 
 /**

Re: [PATCH] generic-ipi: fix deadlock in __smp_call_function_single

[Andrew Morton]

On Fri, 10 Sep 2010 13:06:57 +0200
Peter Zijlstra <peterz@infradead.org> wrote:

> On Thu, 2010-09-09 at 15:50 +0200, Heiko Carstens wrote:
> > From: Heiko Carstens <heiko.carstens@de.ibm.com>
> > 
> > Just got my 6 way machine to a state where cpu 0 is in an endless loop
> > within __smp_call_function_single.
> > All other cpus are idle.
> > 
> > The call trace on cpu 0 looks like this:
> > 
> > __smp_call_function_single
> > scheduler_tick
> > update_process_times
> > tick_sched_timer
> > __run_hrtimer
> > hrtimer_interrupt
> > clock_comparator_work
> > do_extint
> > ext_int_handler
> > ----> timer irq
> > cpu_idle
> > 
> > __smp_call_function_single got called from nohz_balancer_kick (inlined)
> > with the remote cpu being 1, wait being 0 and the per cpu variable
> > remote_sched_softirq_cb (call_single_data) of the current cpu (0).
> > 
> > Then it loops forever when it tries to grab the lock of the
> > call_single_data, since it is already locked and enqueued on cpu 0.
> > 
> > My theory how this could have happened: for some reason the scheduler
> > decided to call __smp_call_function_single on it's own cpu, and sends
> > an IPI to itself. The interrupt stays pending since IRQs are disabled.
> > If then the hypervisor schedules the cpu away it might happen that upon
> > rescheduling both the IPI and the timer IRQ are pending.
> > If then interrupts are enabled again it depends which one gets scheduled
> > first.
> > If the timer interrupt gets delivered first we end up with the local
> > deadlock as seen in the calltrace above.
> > 
> > Let's make __smp_call_function_single check if the target cpu is the
> > current cpu and execute the function immediately just like
> > smp_call_function_single does. That should prevent at least the
> > scenario described here.
> > 
> > It might also be that the scheduler is not supposed to call
> > __smp_call_function_single with the remote cpu being the current cpu,
> > but that is a different issue.
> > 
> > Signed-off-by: Heiko Carstens <heiko.carstens@de.ibm.com>
> 
> Right, so it looks like all other users of __smp_call_function_single()
> do indeed ensure not to call it on self

Yes, it's a cross-CPU call only.  If the scheduler called it for the
current CPU then that's a scheduler bug.

Where is this scheduler bug?  Did it occur because someone didn't
understand __smp_call_function_single()?  Or did it occur because the
scheduler code is doing something which its implementors did not expect
or intend?

> but your patch does make sense.

Maybe.  Or maybe it papers over a scheduler bug by gratuitously adding
additional code which no present callsites actually need.

The patch didn't update the __smp_call_function_single() kerneldoc. 
Compare it with smp_call_function_single() and note the subtle
difference between "a specific CPU" and the now incorrect "on another CPU".

Re: [PATCH] generic-ipi: fix deadlock in __smp_call_function_single

[Peter Zijlstra]

On Fri, 2010-09-10 at 17:28 -0700, Andrew Morton wrote:
> Where is this scheduler bug?  Did it occur because someone didn't
> understand __smp_call_function_single()?  Or did it occur because the
> scheduler code is doing something which its implementors did not expect
> or intend? 


It comes from 83cd4fe2 (sched: Change nohz idle load balancing logic to
push model), where nohz_balance_kick() simply needs to kick the
designated driver into action.

I take it Venki assumed __smp_call_function_single() works like
smp_call_function_single() where you can use it for the local cpu as
well.

I guess we could do something like the below as well, which would be
slightly faster since we don't actually need to call raise_softirq()
since we already set it for self a bit earlier in order to have it do
the regular load-balance actions.

Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
---
 kernel/sched_fair.c |   10 ++++++----
 1 files changed, 6 insertions(+), 4 deletions(-)

diff --git a/kernel/sched_fair.c b/kernel/sched_fair.c
index 9b5b4f8..c8ca1cb 100644
--- a/kernel/sched_fair.c
+++ b/kernel/sched_fair.c
@@ -3404,11 +3404,13 @@ static void nohz_balancer_kick(int cpu)
 	}
 
 	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);
+
+		if (ilb_cpu != cpu) {
+			struct call_single_data *cp;
+			cp = &per_cpu(remote_sched_softirq_cb, cpu);
+			__smp_call_function_single(ilb_cpu, cp, 0);
+		}
 	}
 	return;
 }

Re: [PATCH] generic-ipi: fix deadlock in __smp_call_function_single

[Venkatesh Pallipadi]

On Sat, Sep 11, 2010 at 2:20 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> On Fri, 2010-09-10 at 17:28 -0700, Andrew Morton wrote:
>> Where is this scheduler bug?  Did it occur because someone didn't
>> understand __smp_call_function_single()?  Or did it occur because the
>> scheduler code is doing something which its implementors did not expect
>> or intend?
>
>
> It comes from 83cd4fe2 (sched: Change nohz idle load balancing logic to
> push model), where nohz_balance_kick() simply needs to kick the
> designated driver into action.
>
> I take it Venki assumed __smp_call_function_single() works like
> smp_call_function_single() where you can use it for the local cpu as
> well.

Yes. This was an oversight while moving from using send_remote_softirq
to using __smp_call_function_single.
Also, as we don't have rq lock around this point, it seems possible
that the CPU that was busy and wants to kick idle load balance on
remote CPU, could have become idle and nominated itself as idle load
balancer.

Below patch looks good to me.

Acked-by: Venkatesh Pallipadi <venki@google.com>

I guess, we also need a WARN_ON_ONCE for (cpu == smp_processor_id())
in __smp_call_function_single(), as the eventual result of this bug
that Heiko saw was a deadlock

Thanks,
Venki

>
> I guess we could do something like the below as well, which would be
> slightly faster since we don't actually need to call raise_softirq()
> since we already set it for self a bit earlier in order to have it do
> the regular load-balance actions.
>
> Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
> ---
>  kernel/sched_fair.c |   10 ++++++----
>  1 files changed, 6 insertions(+), 4 deletions(-)
>
> diff --git a/kernel/sched_fair.c b/kernel/sched_fair.c
> index 9b5b4f8..c8ca1cb 100644
> --- a/kernel/sched_fair.c
> +++ b/kernel/sched_fair.c
> @@ -3404,11 +3404,13 @@ static void nohz_balancer_kick(int cpu)
>        }
>
>        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);
> +
> +               if (ilb_cpu != cpu) {
> +                       struct call_single_data *cp;
> +                       cp = &per_cpu(remote_sched_softirq_cb, cpu);
> +                       __smp_call_function_single(ilb_cpu, cp, 0);
> +               }
>        }
>        return;
>  }
>
>

Re: [PATCH] generic-ipi: fix deadlock in __smp_call_function_single

[Heiko Carstens]

On Sat, Sep 11, 2010 at 09:42:16AM -0700, Venkatesh Pallipadi wrote:
> On Sat, Sep 11, 2010 at 2:20 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> > On Fri, 2010-09-10 at 17:28 -0700, Andrew Morton wrote:
> >> Where is this scheduler bug?  Did it occur because someone didn't
> >> understand __smp_call_function_single()?  Or did it occur because the
> >> scheduler code is doing something which its implementors did not expect
> >> or intend?
> >
> >
> > It comes from 83cd4fe2 (sched: Change nohz idle load balancing logic to
> > push model), where nohz_balance_kick() simply needs to kick the
> > designated driver into action.
> >
> > I take it Venki assumed __smp_call_function_single() works like
> > smp_call_function_single() where you can use it for the local cpu as
> > well.
> 
> Yes. This was an oversight while moving from using send_remote_softirq
> to using __smp_call_function_single.
> Also, as we don't have rq lock around this point, it seems possible
> that the CPU that was busy and wants to kick idle load balance on
> remote CPU, could have become idle and nominated itself as idle load
> balancer.
> 
> Below patch looks good to me.
> 
> Acked-by: Venkatesh Pallipadi <venki@google.com>
> 
> I guess, we also need a WARN_ON_ONCE for (cpu == smp_processor_id())
> in __smp_call_function_single(), as the eventual result of this bug
> that Heiko saw was a deadlock

Either that or my generic IPI patch should be applied. At least to me
it was rather surprising to see that smp_call_function_single() and
__smp_call_function_single() behave differently when the 'remote' cpu
is the current cpu.

Re: [PATCH] generic-ipi: fix deadlock in __smp_call_function_single

[Suresh Siddha]

On Sat, 2010-09-11 at 09:42 -0700, Venkatesh Pallipadi wrote:
> Also, as we don't have rq lock around this point, it seems possible
> that the CPU that was busy and wants to kick idle load balance on
> remote CPU, could have become idle and nominated itself as idle load
> balancer.

A busy cpu (currently running something -- one task on the rq atleast)
can't become idle in the middle of trigger_load_balance().

What might be happening is similar what you said but the opposite of it.

cpu-x is idle which is also ilb_cpu
got a scheduler tick during idle
and the nohz_kick_needed() in trigger_load_balance() checks for
rq_x->nr_running which might not be zero (because of someone waking a
task on this rq etc) and this leads to the situation of the cpu-x
sending a kick to itself.

Perhaps the more appropriate patch would be(?):

Signed-off-by: Suresh Siddha <suresh.b.siddha@intel.com>
---
diff --git a/kernel/sched_fair.c b/kernel/sched_fair.c
index 134f7ed..5b5aa97 100644
--- a/kernel/sched_fair.c
+++ b/kernel/sched_fair.c
@@ -3632,7 +3632,7 @@ static inline int nohz_kick_needed(struct rq *rq, int cpu)
 	if (time_before(now, nohz.next_balance))
 		return 0;
 
-	if (!rq->nr_running)
+	if (rq->idle_at_tick)
 		return 0;
 
 	first_pick_cpu = atomic_read(&nohz.first_pick_cpu);

Re: [PATCH] generic-ipi: fix deadlock in __smp_call_function_single

[Peter Zijlstra]

On Mon, 2010-09-13 at 11:02 -0700, Suresh Siddha wrote:
> On Sat, 2010-09-11 at 09:42 -0700, Venkatesh Pallipadi wrote:
> > Also, as we don't have rq lock around this point, it seems possible
> > that the CPU that was busy and wants to kick idle load balance on
> > remote CPU, could have become idle and nominated itself as idle load
> > balancer.
> 
> A busy cpu (currently running something -- one task on the rq atleast)
> can't become idle in the middle of trigger_load_balance().
> 
> What might be happening is similar what you said but the opposite of it.
> 
> cpu-x is idle which is also ilb_cpu
> got a scheduler tick during idle
> and the nohz_kick_needed() in trigger_load_balance() checks for
> rq_x->nr_running which might not be zero (because of someone waking a
> task on this rq etc) and this leads to the situation of the cpu-x
> sending a kick to itself.

So what patches are we going to merge?

I share Heiko's opinion on that its somewhat surprising to have
__smp_call_function_single() differ in this detail from
smp_call_function_single() and think that merging his patch would be
good in that respect. But Andrew seemed to have reservations.

We can also merge either my or Suresh's patch (which I think makes
sense, but is kinda subtle) to avoid the needless self kick.

Hmm?

Re: [PATCH] generic-ipi: fix deadlock in __smp_call_function_single

[Heiko Carstens]

On Tue, Sep 14, 2010 at 10:03:47AM +0200, Peter Zijlstra wrote:
> On Mon, 2010-09-13 at 11:02 -0700, Suresh Siddha wrote:
> > On Sat, 2010-09-11 at 09:42 -0700, Venkatesh Pallipadi wrote:
> > > Also, as we don't have rq lock around this point, it seems possible
> > > that the CPU that was busy and wants to kick idle load balance on
> > > remote CPU, could have become idle and nominated itself as idle load
> > > balancer.
> > 
> > A busy cpu (currently running something -- one task on the rq atleast)
> > can't become idle in the middle of trigger_load_balance().
> > 
> > What might be happening is similar what you said but the opposite of it.
> > 
> > cpu-x is idle which is also ilb_cpu
> > got a scheduler tick during idle
> > and the nohz_kick_needed() in trigger_load_balance() checks for
> > rq_x->nr_running which might not be zero (because of someone waking a
> > task on this rq etc) and this leads to the situation of the cpu-x
> > sending a kick to itself.
> 
> So what patches are we going to merge?
> 
> I share Heiko's opinion on that its somewhat surprising to have
> __smp_call_function_single() differ in this detail from
> smp_call_function_single() and think that merging his patch would be
> good in that respect. But Andrew seemed to have reservations.
> 
> We can also merge either my or Suresh's patch (which I think makes
> sense, but is kinda subtle) to avoid the needless self kick.

I would prefer to see your's or Suresh's scheduler patch to be merged to
fix the bug.
My patch could be merged for 2.6.37 or be dropped in favour of a WARN_ON
in __smp_call_function_single() if remote cpu == current cpu.
However I think it would be better if smp_call_function_single() and
__smp_call_function_single() wouldn't differ here.

Re: [PATCH] generic-ipi: fix deadlock in __smp_call_function_single

[Suresh Siddha]

On Tue, 2010-09-14 at 04:19 -0700, Heiko Carstens wrote:
> > 
> > So what patches are we going to merge?
> > 
> > I share Heiko's opinion on that its somewhat surprising to have
> > __smp_call_function_single() differ in this detail from
> > smp_call_function_single() and think that merging his patch would be
> > good in that respect. But Andrew seemed to have reservations.
> > 
> > We can also merge either my or Suresh's patch (which I think makes
> > sense, but is kinda subtle) to avoid the needless self kick.

Peter, Can you please merge my patch instead of yours, as mine is more
appropriate here. And also I would like Heiko's patch also to be merged
as that brings smp_call_function_single() and
__smp_call_function_single() to similar behavior.

thanks,
suresh

> 
> I would prefer to see your's or Suresh's scheduler patch to be merged to
> fix the bug.
> My patch could be merged for 2.6.37 or be dropped in favour of a WARN_ON
> in __smp_call_function_single() if remote cpu == current cpu.
> However I think it would be better if smp_call_function_single() and
> __smp_call_function_single() wouldn't differ here.

Re: [PATCH] generic-ipi: fix deadlock in __smp_call_function_single

[Peter Zijlstra]

On Fri, 2010-09-17 at 15:12 -0700, Suresh Siddha wrote:
> On Tue, 2010-09-14 at 04:19 -0700, Heiko Carstens wrote:
> > > 
> > > So what patches are we going to merge?
> > > 
> > > I share Heiko's opinion on that its somewhat surprising to have
> > > __smp_call_function_single() differ in this detail from
> > > smp_call_function_single() and think that merging his patch would be
> > > good in that respect. But Andrew seemed to have reservations.
> > > 
> > > We can also merge either my or Suresh's patch (which I think makes
> > > sense, but is kinda subtle) to avoid the needless self kick.
> 
> Peter, Can you please merge my patch instead of yours, as mine is more
> appropriate here. And also I would like Heiko's patch also to be merged
> as that brings smp_call_function_single() and
> __smp_call_function_single() to similar behavior.

Sure can do. Thanks!

[tip:sched/urgent] sched: Fix nohz balance kick

[tip-bot for Suresh Siddha]

Commit-ID:  f6c3f1686e7ec1dd8725a9a3dcb857dfd0c7a5bf
Gitweb:     http://git.kernel.org/tip/f6c3f1686e7ec1dd8725a9a3dcb857dfd0c7a5bf
Author:     Suresh Siddha <suresh.b.siddha@intel.com>
AuthorDate: Mon, 13 Sep 2010 11:02:21 -0700
Committer:  Ingo Molnar <mingo@elte.hu>
CommitDate: Tue, 21 Sep 2010 13:50:50 +0200

sched: Fix nohz balance kick

There's a situation where the nohz balancer will try to wake itself:

cpu-x is idle which is also ilb_cpu
got a scheduler tick during idle
and the nohz_kick_needed() in trigger_load_balance() checks for
rq_x->nr_running which might not be zero (because of someone waking a
task on this rq etc) and this leads to the situation of the cpu-x
sending a kick to itself.

And this can cause a lockup.

Avoid this by not marking ourself eligible for kicking.

Signed-off-by: Suresh Siddha <suresh.b.siddha@intel.com>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
LKML-Reference: <1284400941.2684.19.camel@sbsiddha-MOBL3.sc.intel.com>
Signed-off-by: Ingo Molnar <mingo@elte.hu>
---
 kernel/sched_fair.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/kernel/sched_fair.c b/kernel/sched_fair.c
index a171138..db3f674 100644
--- a/kernel/sched_fair.c
+++ b/kernel/sched_fair.c
@@ -3630,7 +3630,7 @@ static inline int nohz_kick_needed(struct rq *rq, int cpu)
 	if (time_before(now, nohz.next_balance))
 		return 0;
 
-	if (!rq->nr_running)
+	if (rq->idle_at_tick)
 		return 0;
 
 	first_pick_cpu = atomic_read(&nohz.first_pick_cpu);

Re: [PATCH] generic-ipi: fix deadlock in __smp_call_function_single

[Ingo Molnar]

* Andrew Morton <akpm@linux-foundation.org> wrote:

> Maybe.  Or maybe it papers over a scheduler bug by gratuitously adding 
> additional code which no present callsites actually need.

Hm, indeed.

We now have the scheduler bug fixed upstream. Do we really need this 
patch?

> The patch didn't update the __smp_call_function_single() kerneldoc. 
> Compare it with smp_call_function_single() and note the subtle 
> difference between "a specific CPU" and the now incorrect "on another 
> CPU".

In any case this feedback didnt get addressed AFAICS.

	Ingo

Re: [PATCH] generic-ipi: fix deadlock in __smp_call_function_single

[Heiko Carstens]

On Sun, Sep 26, 2010 at 10:42:33AM +0200, Ingo Molnar wrote:
> 
> * Andrew Morton <akpm@linux-foundation.org> wrote:
> 
> > Maybe.  Or maybe it papers over a scheduler bug by gratuitously adding 
> > additional code which no present callsites actually need.
> 
> Hm, indeed.
> 
> We now have the scheduler bug fixed upstream. Do we really need this 
> patch?

General consensus was that it is good if smp_call_function_single() and
__smp_call_function_single() would behave the same if remote cpu == current
cpu.

If you're not applying this patch then at least at a WARN_ON() which triggers
when remote cpu == current cpu. I don't want to debug something like this
again.
 
> > The patch didn't update the __smp_call_function_single() kerneldoc. 
> > Compare it with smp_call_function_single() and note the subtle 
> > difference between "a specific CPU" and the now incorrect "on another 
> > CPU".
> 
> In any case this feedback didnt get addressed AFAICS.

It did get addressed in an updated patch which is the one which you
applied: http://lkml.org/lkml/2010/9/10/245

Re: [PATCH] generic-ipi: fix deadlock in __smp_call_function_single

[Ingo Molnar]

* Heiko Carstens <heiko.carstens@de.ibm.com> wrote:

> On Sun, Sep 26, 2010 at 10:42:33AM +0200, Ingo Molnar wrote:
> > 
> > * Andrew Morton <akpm@linux-foundation.org> wrote:
> > 
> > > Maybe.  Or maybe it papers over a scheduler bug by gratuitously adding 
> > > additional code which no present callsites actually need.
> > 
> > Hm, indeed.
> > 
> > We now have the scheduler bug fixed upstream. Do we really need this 
> > patch?
> 
> General consensus was that it is good if smp_call_function_single() 
> and __smp_call_function_single() would behave the same if remote cpu 
> == current cpu.
> 
> If you're not applying this patch then at least at a WARN_ON() which 
> triggers when remote cpu == current cpu. I don't want to debug 
> something like this again.

Would be nice to hear from Andrew whether he's still opposed to this 
patch. I've got the patch queued up, but dont want to send it to Linus 
against Andrew's objections.

> > > The patch didn't update the __smp_call_function_single() 
> > > kerneldoc. Compare it with smp_call_function_single() and note the 
> > > subtle difference between "a specific CPU" and the now incorrect 
> > > "on another CPU".
> > 
> > In any case this feedback didnt get addressed AFAICS.
> 
> It did get addressed in an updated patch which is the one which you 
> applied: http://lkml.org/lkml/2010/9/10/245

Indeed :-)

Thanks,

	Ingo