lkml.org 
[lkml]   [2018]   [Oct]   [1]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: [RFC][PATCH 3/3] locking/qspinlock: Optimize for x86
    On Mon, Oct 01, 2018 at 06:17:00PM +0100, Will Deacon wrote:
    > Hi Peter,
    >
    > Thanks for chewing up my afternoon ;)

    I'll get you a beer in EDI ;-)

    > On Wed, Sep 26, 2018 at 01:01:20PM +0200, Peter Zijlstra wrote:

    > > /**
    > > + * set_pending_fetch_acquire - fetch the whole lock value and set pending and locked
    > > + * @lock : Pointer to queued spinlock structure
    > > + * Return: The previous lock value
    > > + *
    > > + * *,*,* -> *,1,*
    > > + */
    > > +static __always_inline u32 set_pending_fetch_acquire(struct qspinlock *lock)
    > > +{
    > > +#if defined(_Q_NO_FETCH_OR) && _Q_PENDING_BITS == 8
    > > + u32 val;
    > > +
    > > + /*
    > > + * For the !LL/SC archs that do not have a native atomic_fetch_or
    > > + * but do have a native xchg (x86) we can do trickery and avoid the
    > > + * cmpxchg-loop based fetch-or to improve determinism.
    > > + *
    > > + * We first xchg the pending byte to set PENDING, and then issue a load
    > > + * for the rest of the word and mask out the pending byte to compute a
    > > + * 'full' value.
    > > + */
    > > + val = xchg_relaxed(&lock->pending, 1) << _Q_PENDING_OFFSET;
    >
    > If we make this an xchg_acquire(), can we drop the smp_mb__after_atomic()
    > and use a plain atomic_read() to get the rest of the word?

    I did consider that; but I confused myself so many times I stuck with
    this one. Primarily because on x86 it doesn't matter one way or the
    other and smp_mb() are 'easier' to reason about.

    > But actually,
    > consider this scenario with your patch:
    >
    > 1. CPU0 sees a locked val, and is about to do your xchg_relaxed() to set
    > pending.
    >
    > 2. CPU1 comes in and sets pending, spins on locked
    >
    > 3. CPU2 sees a pending and locked val, and is about to enter the head of
    > the waitqueue (i.e. it's right before xchg_tail()).
    >
    > 4. The locked holder unlock()s, CPU1 takes the lock() and then unlock()s
    > it, so pending and locked are now 0.
    >
    > 5. CPU0 sets pending and reads back zeroes for the other fields
    >
    > 6. CPU0 clears pending and sets locked -- it now has the lock
    >
    > 7. CPU2 updates tail, sees it's at the head of the waitqueue and spins
    > for locked and pending to go clear. However, it reads a stale value
    > from step (4) and attempts the atomic_try_cmpxchg() to take the lock.
    >
    > 8. CPU2 will fail the cmpxchg(), but then go ahead and set locked. At this
    > point we're hosed, because both CPU2 and CPU0 have the lock.

    Let me draw a picture of that..


    CPU0 CPU1 CPU2 CPU3

    0) lock
    trylock -> (0,0,1)
    1)lock
    trylock /* fail */

    2) lock
    trylock /* fail */
    tas-pending -> (0,1,1)
    wait-locked

    3) lock
    trylock /* fail */
    tas-pending /* fail */

    4) unlock -> (0,1,0)
    clr_pnd_set_lck -> (0,0,1)
    unlock -> (0,0,0)

    5) tas-pending -> (0,1,0)
    read-val -> (0,1,0)
    6) clr_pnd_set_lck -> (0,0,1)
    7) xchg_tail -> (n,0,1)
    load_acquire <- (n,0,0) (from-4)
    8) cmpxchg /* fail */
    set_locked()

    > Is there something I'm missing that means this can't happen? I suppose
    > cacheline granularity ends up giving serialisation between (4) and (7),
    > but I'd *much* prefer not to rely on that because it feels horribly
    > fragile.

    Well, on x86 atomics are fully ordered, so the xchg_tail() does in
    fact have smp_mb() in and that should order it sufficient for that not
    to happen I think.

    But in general, yes ick. Alternatively, making xchg_tail an ACQUIRE
    doesn't seem too far out..

    > Another idea I was playing with was adding test_and_set_bit_acquire()
    > for this, because x86 has an instruction for that, right?

    LOCK BTS, yes. So it can do a full 32bit RmW, but it cannot return the
    old value of the word, just the old bit (in CF).

    I suppose you get rid of the whole mixed size thing, but you still have
    the whole two instruction thing.

    > > + /*
    > > + * Ensures the tail load happens after the xchg().
    > > + *
    > > + * lock unlock (a)
    > > + * xchg ---------------.
    > > + * (b) lock unlock +----- fetch_or
    > > + * load ---------------'
    > > + * lock unlock (c)
    > > + *
    >
    > I failed miserably at parsing this comment :(
    >
    > I think the main issue is that I don't understand how to read the little
    > diagram you've got.

    Where fetch_or() is indivisible and has happens-before (a) and
    happens-after (c), the new thing is in fact divisible and has
    happens-in-between (b).

    Of the happens-in-between (b), we can either get a new concurrent
    locker, or make progress of an extant concurrent locker because an
    unlock happened.

    But the rest of the text might indeed be very confused. I think I wrote
    the bulk of that when I was in fact doing a xchg16 on locked_pending,
    but that's fundamentally broken. I did edit it afterwards, but that
    might have just made it worse.

    \
     
     \ /
      Last update: 2018-10-01 22:01    [W:4.619 / U:0.548 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site