Re: [RFC][PATCH 3/3] locking/qspinlock: Optimize for x86

[Peter Zijlstra]

On Wed, Sep 26, 2018 at 07:54:18PM +0200, Peter Zijlstra wrote:
> On Wed, Sep 26, 2018 at 12:30:36PM -0400, Waiman Long wrote:
> > On 09/26/2018 07:01 AM, Peter Zijlstra wrote:
> > > On x86 we cannot do fetch_or with a single instruction and end up
> > > using a cmpxchg loop, this reduces determinism. Replace the fetch_or
> > > with a very tricky composite xchg8 + load.
> > >
> > > The basic idea is that we use xchg8 to test-and-set the pending bit
> > > (when it is a byte) and then a load to fetch the whole word. Using
> > > two instructions of course opens a window we previously did not have.
> > > In particular the ordering between pending and tail is of interrest,
> > > because that is where the split happens.
> > >
> > > The claim is that if we order them, it all works out just fine. There
> > > are two specific cases where the pending,tail state changes:
> > >
> > >  - when the 3rd lock(er) comes in and finds pending set, it'll queue
> > >    and set tail; since we set tail while pending is set, the ordering
> > >    is split is not important (and not fundamentally different form
> > >    fetch_or). [*]
> > 
> > The split can cause some changes in behavior. The 3rd locker observes
> > the pending bit and set tail. The split load of the 2nd locker may make
> > it observe the tail and backout of the pending loop. As a result, the
> > 2nd locker will acquire the lock after the third locker in this case.
> > That won't happen with the original code.
> > 
> > I am not saying this is a problem. It is just something we should take
> > note on.
> 
> Right, good one. Yes that can happen.

I think I remember why I 'discounted' that scenario; the same can happen
with the fetch_or() but in a timing scenario.

Consider:

  CPU 0		CPU 1		CPU 2		CPU 3

  lock (->0,0,1)
		lock
		  trylock (fail)
		  tas-pending (->0,1,1)
		  wait-!locked
				lock
				  trylock (fail)
				  tas-pending (fail)
  unlock (->0,1,0)
		  acquire (->0,0,1)
						lock
						  trylock (fail)
				  (A) xchg-tail
						  tas-pending -> (x,1,1)
				  (B) xchg-tail

And then, depending on A/B x is either 0 or !0.

So the ordering of the concurrent lock attempts is always (obviously)
subject to timing, the split xchg-load thing just makes it 'worse'.