Messages in this thread | | | Date | Tue, 2 Oct 2018 15:44:42 +0200 | From | Andrea Parri <> | Subject | Re: [RFC][PATCH 3/3] locking/qspinlock: Optimize for x86 |
| |
On Tue, Oct 02, 2018 at 02:22:09PM +0100, Will Deacon wrote: > On Tue, Oct 02, 2018 at 02:31:52PM +0200, Andrea Parri wrote: > > > 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. > > > > Thanks for pointing this out. I am wondering: can't we have a similar > > scenario with the current code (i.e., w/o these patches): what prevents > > the scenario reported below, following Peter's diagram, from happening? > > The xchg_tail() in step (7) reads from the fetch_or_acquire() in step (5), > so I don't think we can see a stale value in the subsequent (overlapping) > acquire load.
I see, thanks for the clarification.
Andrea
> > Will > > > CPU0 CPU1 CPU2 CPU3 > > > > 0) lock > > trylock -> (0,0,1) > > 1)lock > > trylock /* fail */ > > > > 2) lock > > trylock /* fail */ > > fetch_or_acquire -> (0,1,1) > > wait-locked > > > > 3) lock > > trylock /* fail */ > > goto queue > > > > 4) unlock -> (0,1,0) > > clr_pnd_set_lck -> (0,0,1) > > unlock -> (0,0,0) > > > > 5) fetch_or_acquire -> (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()
| |