Re: [PATCH] memory ordering in __kfifo primitives

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

On Thu, Aug 10, 2006 at 06:23:04PM +0200, Stelian Pop wrote:
> Le jeudi 10 août 2006 à 09:11 -0700, Paul E. McKenney a écrit :
> > On Thu, Aug 10, 2006 at 05:47:22PM +0200, Stelian Pop wrote:
> > > Le jeudi 10 août 2006 à 08:39 -0700, Paul E. McKenney a écrit :
> > > > On Thu, Aug 10, 2006 at 04:26:53PM +0200, Stelian Pop wrote:
> > > > > Le jeudi 10 août 2006 à 06:41 -0700, Paul E. McKenney a écrit :
> > > > > 
> > > > > > I am happy to go either way -- the patch with the memory barriers
> > > > > > (which does have the side-effect of slowing down kfifo_get() and
> > > > > > kfifo_put(), by the way), or a patch removing the comments saying
> > > > > > that it is OK to invoke __kfifo_get() and __kfifo_put() without
> > > > > > locking.
> > > > > > 
> > > > > > Any other thoughts on which is better?  (1) the memory barriers or
> > > > > > (2) requiring the caller hold appropriate locks across calls to
> > > > > > __kfifo_get() and __kfifo_put()?
> > > > > 
> > > > > If someone wants to use explicit locking, he/she can go with kfifo_get()
> > > > > instead of the __ version.
> > > > 
> > > > However, the kfifo_get()/kfifo_put() interfaces use the internal lock,
> > > 
> > > ... and the internal lock can be supplied by the user at kfifo_alloc()
> > > time.
> > 
> > Would that really work for them?  Looks to me like it would result
> > in self-deadlock if they passed in session->lock.
> 
> Yeah, it will deadlock if the lock is already taken before calling
> __kfifo_get and __kfifo_put.
> 
> > Or did you have something else in mind for them?
> 
> What I had in mind is to replace all occurences of:
> 	kfifo_alloc(..., NULL);
> 	...
> 	spin_lock(&session->lock)
> 	__kfifo_get()
> 	spin_unlock()
> 
> with the simpler:
> 	kfifo_alloc(..., &session->lock)
> 	...
> 	kfifo_get()

Fair enough!

> As for the occurences of:
> 	...
> 	spin_lock(&session->lock)
> 	do_something();
> 	__kifo_get();
> 
> well, there is not much we can do about them...

Agreed!

> Let's take this problem differently: is a memory barrier cheaper than a
> spinlock ? 

Almost always, yes.  But a spinlock is cheaper than a spinlock plus
a pair of memory barriers.

> If the answer is yes as I suspect, why should the kfifo API force the
> user to take a spinlock ?

My concern is that currently a majority of the calls to __kfifo_{get,put}()
are already holding a spinlock.

But if you could send me your tests for lock-free __kfifo_{get,put}(),
I would be happy to run them on weak-memory-consistency model machines
with the memory barriers.  And without the memory barriers -- we need
a test that fails in the latter case to prove that the memory barriers
really are in the right place and that all of them are present.

Does this sound reasonable?

						Thanx, Paul