Re: [PATCH 1/10] Add generic helpers for arch IPI function calls

["Paul E. McKenney" <paulmck@linux.vnet.ibm.com>]

On Wed, Apr 30, 2008 at 01:34:57PM +0200, Jens Axboe wrote:
> On Wed, Apr 30 2008, Paul E. McKenney wrote:
> > On Tue, Apr 29, 2008 at 06:59:36AM -0700, Paul E. McKenney wrote:
> > > On Tue, Apr 29, 2008 at 09:26:21AM +0200, Jens Axboe wrote:
> > > > This adds kernel/smp.c which contains helpers for IPI function calls. In
> > > > addition to supporting the existing smp_call_function() in a more efficient
> > > > manner, it also adds a more scalable variant called smp_call_function_single()
> > > > for calling a given function on a single CPU only.
> > > > 
> > > > The core of this is based on the x86-64 patch from Nick Piggin, lots of
> > > > changes since then. "Alan D. Brunelle" <Alan.Brunelle@hp.com> has
> > > > contributed lots of fixes and suggestions as well.
> > > 
> > > Looks much better, but there still appears to be a potential deadlock
> > > with a CPU spinning waiting (indirectly) for a grace period to complete.
> > > Such spinning can prevent the grace period from ever completing.
> > > 
> > > See "!!!".
> > 
> > One additional question...  Why not handle memory allocation failure
> > by pretending that the caller to smp_call_function() had specified
> > "wait"?  The callee is in irq context, so cannot block, right?
> 
> (BTW a lot of thanks for your comments, I've read and understood most of
> it, I'll reply in due time - perhaps not until next week, I'll be gone
> from this afternoon and until monday).
> 
> We cannot always fallback to wait, unfortunately. If irqs are disabled,
> you could deadlock between two CPUs each waiting for each others IPI
> ack.

Good point!!!

> So the good question is how to handle the problem. The easiest would be
> to return ENOMEM and get rid of the fallback, but the fallback deadlocks
> are so far mostly in the theoretical realm since it PROBABLY would not
> occur in practice. But still no good enough, so I'm still toying with
> ideas on how to make it 100% bullet proof.

Here are some (probably totally broken) ideas:

1.	Global lock so that only one smp_call_function() in the
	system proceeds.  Additional calls would be spinning with
	irqs -enabled- on the lock, avoiding deadlock.  Kind of
	defeats the purpose of your list, though...

2.	Maintain a global mask of current targets of smp_call_function()
	CPUs.  A given CPU may proceed if it is not a current target
	and if none of its target CPUs are already in the mask.
	This mask would be manipulated under a global lock.

3.	As in #2 above, but use per-CPU counters.  This allows the
	current CPU to proceed if it is not a target, but also allows
	concurrent smp_call_function()s to proceed even if their
	lists of target CPUs overlap.

4.	#2 or #3, but where CPUs can proceed freely if their allocation
	succeeded.

5.	If a given CPU is waiting for other CPUs to respond, it polls
	its own list (with irqs disabled), thus breaking the deadlock.
	This means that you cannot call smp_call_function() while holding
	a lock that might be acquired by the called function, but that
	is not a new prohibition -- the only safe way to hold such a
	lock is with irqs disabled, and you are not allowed to call
	the smp_call_function() with irqs disabled in the first place
	(right?).

#5 might actually work...

						Thanx, Paul