by Waiman Long

[permalink] [raw]

Subject: Re: [PATCH 02/10] locking/qspinlock: Remove unbounded cmpxchg loop from locking slowpath

2018-04-06 21:12:28

by Paul E. McKenney

[permalink] [raw]

Subject: Re: [PATCH 02/10] locking/qspinlock: Remove unbounded cmpxchg loop from locking slowpath

On Fri, Apr 06, 2018 at 04:50:19PM -0400, Waiman Long wrote:
> On 04/05/2018 12:58 PM, Will Deacon wrote:
> > The qspinlock locking slowpath utilises a "pending" bit as a simple form
> > of an embedded test-and-set lock that can avoid the overhead of explicit
> > queuing in cases where the lock is held but uncontended. This bit is
> > managed using a cmpxchg loop which tries to transition the uncontended
> > lock word from (0,0,0) -> (0,0,1) or (0,0,1) -> (0,1,1).
> >
> > Unfortunately, the cmpxchg loop is unbounded and lockers can be starved
> > indefinitely if the lock word is seen to oscillate between unlocked
> > (0,0,0) and locked (0,0,1). This could happen if concurrent lockers are
> > able to take the lock in the cmpxchg loop without queuing and pass it
> > around amongst themselves.
> >
> > This patch fixes the problem by unconditionally setting _Q_PENDING_VAL
> > using atomic_fetch_or, and then inspecting the old value to see whether
> > we need to spin on the current lock owner, or whether we now effectively
> > hold the lock. The tricky scenario is when concurrent lockers end up
> > queuing on the lock and the lock becomes available, causing us to see
> > a lockword of (n,0,0). With pending now set, simply queuing could lead
> > to deadlock as the head of the queue may not have observed the pending
> > flag being cleared. Conversely, if the head of the queue did observe
> > pending being cleared, then it could transition the lock from (n,0,0) ->
> > (0,0,1) meaning that any attempt to "undo" our setting of the pending
> > bit could race with a concurrent locker trying to set it.
> >
> > We handle this race by preserving the pending bit when taking the lock
> > after reaching the head of the queue and leaving the tail entry intact
> > if we saw pending set, because we know that the tail is going to be
> > updated shortly.
> >
> > Cc: Peter Zijlstra <[email protected]>
> > Cc: Ingo Molnar <[email protected]>
> > Signed-off-by: Will Deacon <[email protected]>
> > ---
>
> The pending bit was added to the qspinlock design to counter performance
> degradation compared with ticket lock for workloads with light
> spinlock contention. I run my spinlock stress test on a Intel Skylake
> server running the vanilla 4.16 kernel vs a patched kernel with this
> patchset. The locking rates with different number of locking threads
> were as follows:
>
> # of threads 4.16 kernel patched 4.16 kernel
> ------------ ----------- -------------------
> 1 7,417 kop/s 7,408 kop/s
> 2 5,755 kop/s 4,486 kop/s
> 3 4,214 kop/s 4,169 kop/s
> 4 4,396 kop/s 4,383 kop/s
>
> The 2 contending threads case is the one that exercise the pending bit
> code path the most. So it is obvious that this is the one that is most
> impacted by this patchset. The differences in the other cases are mostly
> noise or maybe just a little bit on the 3 contending threads case.
>
> I am not against this patch, but we certainly need to find out a way to
> bring the performance number up closer to what it is before applying
> the patch.

It would indeed be good to not be in the position of having to trade off
forward-progress guarantees against performance, but that does appear to
be where we are at the moment.

Thanx, Paul

2018-04-07 05:24:49

by Boqun Feng

[permalink] [raw]

Subject: Re: [PATCH 08/10] locking/qspinlock: Merge struct __qspinlock into struct qspinlock

On Thu, Apr 05, 2018 at 05:59:05PM +0100, Will Deacon wrote:
> struct __qspinlock provides a handy union of fields so that
> subcomponents of the lockword can be accessed by name, without having to
> manage shifts and masks explicitly and take endianness into account.
>
> This is useful in qspinlock.h and also potentially in arch headers, so
> move the struct __qspinlock into struct qspinlock and kill the extra
> definition.
>
> Cc: Peter Zijlstra <[email protected]>
> Cc: Ingo Molnar <[email protected]>
> Signed-off-by: Will Deacon <[email protected]>

As I said in the IRC, it's glad to see such a merge ;-)

Acked-by: Boqun Feng <[email protected]>

Regards,
Boqun

> ---
> arch/x86/include/asm/qspinlock.h | 2 +-
> arch/x86/include/asm/qspinlock_paravirt.h | 3 +-
> include/asm-generic/qspinlock_types.h | 32 +++++++++++++++++++--
> kernel/locking/qspinlock.c | 46 ++-----------------------------
> kernel/locking/qspinlock_paravirt.h | 34 ++++++++---------------
> 5 files changed, 46 insertions(+), 71 deletions(-)
>
> diff --git a/arch/x86/include/asm/qspinlock.h b/arch/x86/include/asm/qspinlock.h
> index 5e16b5d40d32..90b0b0ed8161 100644
> --- a/arch/x86/include/asm/qspinlock.h
> +++ b/arch/x86/include/asm/qspinlock.h
> @@ -16,7 +16,7 @@
> */
> static inline void native_queued_spin_unlock(struct qspinlock *lock)
> {
> - smp_store_release((u8 *)lock, 0);
> + smp_store_release(&lock->locked, 0);
> }
>
> #ifdef CONFIG_PARAVIRT_SPINLOCKS
> diff --git a/arch/x86/include/asm/qspinlock_paravirt.h b/arch/x86/include/asm/qspinlock_paravirt.h
> index 923307ea11c7..9ef5ee03d2d7 100644
> --- a/arch/x86/include/asm/qspinlock_paravirt.h
> +++ b/arch/x86/include/asm/qspinlock_paravirt.h
> @@ -22,8 +22,7 @@ PV_CALLEE_SAVE_REGS_THUNK(__pv_queued_spin_unlock_slowpath);
> *
> * void __pv_queued_spin_unlock(struct qspinlock *lock)
> * {
> - * struct __qspinlock *l = (void *)lock;
> - * u8 lockval = cmpxchg(&l->locked, _Q_LOCKED_VAL, 0);
> + * u8 lockval = cmpxchg(&lock->locked, _Q_LOCKED_VAL, 0);
> *
> * if (likely(lockval == _Q_LOCKED_VAL))
> * return;
> diff --git a/include/asm-generic/qspinlock_types.h b/include/asm-generic/qspinlock_types.h
> index 034acd0c4956..0763f065b975 100644
> --- a/include/asm-generic/qspinlock_types.h
> +++ b/include/asm-generic/qspinlock_types.h
> @@ -29,13 +29,41 @@
> #endif
>
> typedef struct qspinlock {
> - atomic_t val;
> + union {
> + atomic_t val;
> +
> + /*
> + * By using the whole 2nd least significant byte for the
> + * pending bit, we can allow better optimization of the lock
> + * acquisition for the pending bit holder.
> + */
> +#ifdef __LITTLE_ENDIAN
> + struct {
> + u8 locked;
> + u8 pending;
> + };
> + struct {
> + u16 locked_pending;
> + u16 tail;
> + };
> +#else
> + struct {
> + u16 tail;
> + u16 locked_pending;
> + };
> + struct {
> + u8 reserved[2];
> + u8 pending;
> + u8 locked;
> + };
> +#endif
> + };
> } arch_spinlock_t;
>
> /*
> * Initializier
> */
> -#define __ARCH_SPIN_LOCK_UNLOCKED { ATOMIC_INIT(0) }
> +#define __ARCH_SPIN_LOCK_UNLOCKED { .val = ATOMIC_INIT(0) }
>
> /*
> * Bitfields in the atomic value:
> diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c
> index c8b57d375b49..3ad8786a47e2 100644
> --- a/kernel/locking/qspinlock.c
> +++ b/kernel/locking/qspinlock.c
> @@ -114,40 +114,6 @@ static inline __pure struct mcs_spinlock *decode_tail(u32 tail)
>
> #define _Q_LOCKED_PENDING_MASK (_Q_LOCKED_MASK | _Q_PENDING_MASK)
>
> -/*
> - * By using the whole 2nd least significant byte for the pending bit, we
> - * can allow better optimization of the lock acquisition for the pending
> - * bit holder.
> - *
> - * This internal structure is also used by the set_locked function which
> - * is not restricted to _Q_PENDING_BITS == 8.
> - */
> -struct __qspinlock {
> - union {
> - atomic_t val;
> -#ifdef __LITTLE_ENDIAN
> - struct {
> - u8 locked;
> - u8 pending;
> - };
> - struct {
> - u16 locked_pending;
> - u16 tail;
> - };
> -#else
> - struct {
> - u16 tail;
> - u16 locked_pending;
> - };
> - struct {
> - u8 reserved[2];
> - u8 pending;
> - u8 locked;
> - };
> -#endif
> - };
> -};
> -
> #if _Q_PENDING_BITS == 8
> /**
> * clear_pending_set_locked - take ownership and clear the pending bit.
> @@ -159,9 +125,7 @@ struct __qspinlock {
> */
> static __always_inline void clear_pending_set_locked(struct qspinlock *lock)
> {
> - struct __qspinlock *l = (void *)lock;
> -
> - WRITE_ONCE(l->locked_pending, _Q_LOCKED_VAL);
> + WRITE_ONCE(lock->locked_pending, _Q_LOCKED_VAL);
> }
>
> /*
> @@ -176,13 +140,11 @@ static __always_inline void clear_pending_set_locked(struct qspinlock *lock)
> */
> static __always_inline u32 xchg_tail(struct qspinlock *lock, u32 tail)
> {
> - struct __qspinlock *l = (void *)lock;
> -
> /*
> * Use release semantics to make sure that the MCS node is properly
> * initialized before changing the tail code.
> */
> - return (u32)xchg_release(&l->tail,
> + return (u32)xchg_release(&lock->tail,
> tail >> _Q_TAIL_OFFSET) << _Q_TAIL_OFFSET;
> }
>
> @@ -237,9 +199,7 @@ static __always_inline u32 xchg_tail(struct qspinlock *lock, u32 tail)
> */
> static __always_inline void set_locked(struct qspinlock *lock)
> {
> - struct __qspinlock *l = (void *)lock;
> -
> - WRITE_ONCE(l->locked, _Q_LOCKED_VAL);
> + WRITE_ONCE(lock->locked, _Q_LOCKED_VAL);
> }
>
>
> diff --git a/kernel/locking/qspinlock_paravirt.h b/kernel/locking/qspinlock_paravirt.h
> index 6ee477765e6c..2711940429f5 100644
> --- a/kernel/locking/qspinlock_paravirt.h
> +++ b/kernel/locking/qspinlock_paravirt.h
> @@ -87,8 +87,6 @@ struct pv_node {
> #define queued_spin_trylock(l) pv_hybrid_queued_unfair_trylock(l)
> static inline bool pv_hybrid_queued_unfair_trylock(struct qspinlock *lock)
> {
> - struct __qspinlock *l = (void *)lock;
> -
> /*
> * Stay in unfair lock mode as long as queued mode waiters are
> * present in the MCS wait queue but the pending bit isn't set.
> @@ -97,7 +95,7 @@ static inline bool pv_hybrid_queued_unfair_trylock(struct qspinlock *lock)
> int val = atomic_read(&lock->val);
>
> if (!(val & _Q_LOCKED_PENDING_MASK) &&
> - (cmpxchg_acquire(&l->locked, 0, _Q_LOCKED_VAL) == 0)) {
> + (cmpxchg_acquire(&lock->locked, 0, _Q_LOCKED_VAL) == 0)) {
> qstat_inc(qstat_pv_lock_stealing, true);
> return true;
> }
> @@ -117,16 +115,12 @@ static inline bool pv_hybrid_queued_unfair_trylock(struct qspinlock *lock)
> #if _Q_PENDING_BITS == 8
> static __always_inline void set_pending(struct qspinlock *lock)
> {
> - struct __qspinlock *l = (void *)lock;
> -
> - WRITE_ONCE(l->pending, 1);
> + WRITE_ONCE(lock->pending, 1);
> }
>
> static __always_inline void clear_pending(struct qspinlock *lock)
> {
> - struct __qspinlock *l = (void *)lock;
> -
> - WRITE_ONCE(l->pending, 0);
> + WRITE_ONCE(lock->pending, 0);
> }
>
> /*
> @@ -136,10 +130,8 @@ static __always_inline void clear_pending(struct qspinlock *lock)
> */
> static __always_inline int trylock_clear_pending(struct qspinlock *lock)
> {
> - struct __qspinlock *l = (void *)lock;
> -
> - return !READ_ONCE(l->locked) &&
> - (cmpxchg_acquire(&l->locked_pending, _Q_PENDING_VAL,
> + return !READ_ONCE(lock->locked) &&
> + (cmpxchg_acquire(&lock->locked_pending, _Q_PENDING_VAL,
> _Q_LOCKED_VAL) == _Q_PENDING_VAL);
> }
> #else /* _Q_PENDING_BITS == 8 */
> @@ -384,7 +376,6 @@ static void pv_wait_node(struct mcs_spinlock *node, struct mcs_spinlock *prev)
> static void pv_kick_node(struct qspinlock *lock, struct mcs_spinlock *node)
> {
> struct pv_node *pn = (struct pv_node *)node;
> - struct __qspinlock *l = (void *)lock;
>
> /*
> * If the vCPU is indeed halted, advance its state to match that of
> @@ -413,7 +404,7 @@ static void pv_kick_node(struct qspinlock *lock, struct mcs_spinlock *node)
> * the hash table later on at unlock time, no atomic instruction is
> * needed.
> */
> - WRITE_ONCE(l->locked, _Q_SLOW_VAL);
> + WRITE_ONCE(lock->locked, _Q_SLOW_VAL);
> (void)pv_hash(lock, pn);
> }
>
> @@ -428,7 +419,6 @@ static u32
> pv_wait_head_or_lock(struct qspinlock *lock, struct mcs_spinlock *node)
> {
> struct pv_node *pn = (struct pv_node *)node;
> - struct __qspinlock *l = (void *)lock;
> struct qspinlock **lp = NULL;
> int waitcnt = 0;
> int loop;
> @@ -479,13 +469,13 @@ pv_wait_head_or_lock(struct qspinlock *lock, struct mcs_spinlock *node)
> *
> * Matches the smp_rmb() in __pv_queued_spin_unlock().
> */
> - if (xchg(&l->locked, _Q_SLOW_VAL) == 0) {
> + if (xchg(&lock->locked, _Q_SLOW_VAL) == 0) {
> /*
> * The lock was free and now we own the lock.
> * Change the lock value back to _Q_LOCKED_VAL
> * and unhash the table.
> */
> - WRITE_ONCE(l->locked, _Q_LOCKED_VAL);
> + WRITE_ONCE(lock->locked, _Q_LOCKED_VAL);
> WRITE_ONCE(*lp, NULL);
> goto gotlock;
> }
> @@ -493,7 +483,7 @@ pv_wait_head_or_lock(struct qspinlock *lock, struct mcs_spinlock *node)
> WRITE_ONCE(pn->state, vcpu_hashed);
> qstat_inc(qstat_pv_wait_head, true);
> qstat_inc(qstat_pv_wait_again, waitcnt);
> - pv_wait(&l->locked, _Q_SLOW_VAL);
> + pv_wait(&lock->locked, _Q_SLOW_VAL);
>
> /*
> * Because of lock stealing, the queue head vCPU may not be
> @@ -518,7 +508,6 @@ pv_wait_head_or_lock(struct qspinlock *lock, struct mcs_spinlock *node)
> __visible void
> __pv_queued_spin_unlock_slowpath(struct qspinlock *lock, u8 locked)
> {
> - struct __qspinlock *l = (void *)lock;
> struct pv_node *node;
>
> if (unlikely(locked != _Q_SLOW_VAL)) {
> @@ -547,7 +536,7 @@ __pv_queued_spin_unlock_slowpath(struct qspinlock *lock, u8 locked)
> * Now that we have a reference to the (likely) blocked pv_node,
> * release the lock.
> */
> - smp_store_release(&l->locked, 0);
> + smp_store_release(&lock->locked, 0);
>
> /*
> * At this point the memory pointed at by lock can be freed/reused,
> @@ -573,7 +562,6 @@ __pv_queued_spin_unlock_slowpath(struct qspinlock *lock, u8 locked)
> #ifndef __pv_queued_spin_unlock
> __visible void __pv_queued_spin_unlock(struct qspinlock *lock)
> {
> - struct __qspinlock *l = (void *)lock;
> u8 locked;
>
> /*
> @@ -581,7 +569,7 @@ __visible void __pv_queued_spin_unlock(struct qspinlock *lock)
> * unhash. Otherwise it would be possible to have multiple @lock
> * entries, which would be BAD.
> */
> - locked = cmpxchg_release(&l->locked, _Q_LOCKED_VAL, 0);
> + locked = cmpxchg_release(&lock->locked, _Q_LOCKED_VAL, 0);
> if (likely(locked == _Q_LOCKED_VAL))
> return;
>
> --
> 2.1.4
>

Attachments:

(No filename) (10.81 kB)
signature.asc (499.00 B)
Download all attachments

2018-04-07 05:46:22

On Thu, Sep 20, 2018 at 06:08:32PM +0200, Peter Zijlstra wrote:
> Another approach might be to use something like:
>
> val = xchg_relaxed(&lock->locked_pending, _Q_PENDING_VAL | _Q_LOCKED_VAL);
> val |= atomic_read_acquire(&lock->val) & _Q_TAIL_MASK;
>
> combined with something like:
>
> /* 0,0,0 -> 0,1,1 - we won trylock */
> if (!(val & _Q_LOCKED_MASK)) {

That one doesn't actually work... let me think about this more.

> clear_pending(lock);
> return;
> }
>
> /* 0,0,1 -> 0,1,1 - we won pending */
> if (!(val & ~_Q_LOCKED_MASK)) {
> ...
> }
>
> /* *,0,1 -> *,1,1 - we won pending, but there's queueing */
> if (!(val & _Q_PENDING_VAL))
> clear_pending(lock);
>
> ...
>
>
> Hmmm?