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'.
