From: Waiman Long <Waiman.Long@hp.com> To: Thomas Gleixner <tglx@linutronix.de>, Ingo Molnar <mingo@redhat.com>, "H. Peter Anvin" <hpa@zytor.com>, Peter Zijlstra <peterz@infradead.org> Cc: linux-arch@vger.kernel.org, x86@kernel.org, linux-kernel@vger.kernel.org, virtualization@lists.linux-foundation.org, xen-devel@lists.xenproject.org, kvm@vger.kernel.org, Paolo Bonzini <paolo.bonzini@gmail.com>, Konrad Rzeszutek Wilk <konrad.wilk@oracle.com>, Boris Ostrovsky <boris.ostrovsky@oracle.com>, "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>, Rik van Riel <riel@redhat.com>, Linus Torvalds <torvalds@linux-foundation.org>, Raghavendra K T <raghavendra.kt@linux.vnet.ibm.com>, David Vrabel <david.vrabel@citrix.com>, Oleg Nesterov <oleg@redhat.com>, Daniel J Blueman <daniel@numascale.com>, Scott J Norton <scott.norton@hp.com>, Douglas Hatch <doug.hatch@hp.com>, Waiman Long <Waiman.Long@hp.com>, "Peter Zijlstra (Intel)" <peterz@infradead.org> Subject: [PATCH v16 04/14] qspinlock: Extract out code snippets for the next patch Date: Fri, 24 Apr 2015 14:56:33 -0400 [thread overview] Message-ID: <1429901803-29771-5-git-send-email-Waiman.Long@hp.com> (raw) In-Reply-To: <1429901803-29771-1-git-send-email-Waiman.Long@hp.com> This is a preparatory patch that extracts out the following 2 code snippets to prepare for the next performance optimization patch. 1) the logic for the exchange of new and previous tail code words into a new xchg_tail() function. 2) the logic for clearing the pending bit and setting the locked bit into a new clear_pending_set_locked() function. This patch also simplifies the trylock operation before queuing by calling queue_spin_trylock() directly. Signed-off-by: Waiman Long <Waiman.Long@hp.com> Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org> --- include/asm-generic/qspinlock_types.h | 2 + kernel/locking/qspinlock.c | 79 ++++++++++++++++++++------------- 2 files changed, 50 insertions(+), 31 deletions(-) diff --git a/include/asm-generic/qspinlock_types.h b/include/asm-generic/qspinlock_types.h index 9c3f5c2..ef36613 100644 --- a/include/asm-generic/qspinlock_types.h +++ b/include/asm-generic/qspinlock_types.h @@ -58,6 +58,8 @@ typedef struct qspinlock { #define _Q_TAIL_CPU_BITS (32 - _Q_TAIL_CPU_OFFSET) #define _Q_TAIL_CPU_MASK _Q_SET_MASK(TAIL_CPU) +#define _Q_TAIL_MASK (_Q_TAIL_IDX_MASK | _Q_TAIL_CPU_MASK) + #define _Q_LOCKED_VAL (1U << _Q_LOCKED_OFFSET) #define _Q_PENDING_VAL (1U << _Q_PENDING_OFFSET) diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c index 0351f78..11f6ad9 100644 --- a/kernel/locking/qspinlock.c +++ b/kernel/locking/qspinlock.c @@ -97,6 +97,42 @@ static inline struct mcs_spinlock *decode_tail(u32 tail) #define _Q_LOCKED_PENDING_MASK (_Q_LOCKED_MASK | _Q_PENDING_MASK) /** + * clear_pending_set_locked - take ownership and clear the pending bit. + * @lock: Pointer to queue spinlock structure + * + * *,1,0 -> *,0,1 + */ +static __always_inline void clear_pending_set_locked(struct qspinlock *lock) +{ + atomic_add(-_Q_PENDING_VAL + _Q_LOCKED_VAL, &lock->val); +} + +/** + * xchg_tail - Put in the new queue tail code word & retrieve previous one + * @lock : Pointer to queue spinlock structure + * @tail : The new queue tail code word + * Return: The previous queue tail code word + * + * xchg(lock, tail) + * + * p,*,* -> n,*,* ; prev = xchg(lock, node) + */ +static __always_inline u32 xchg_tail(struct qspinlock *lock, u32 tail) +{ + u32 old, new, val = atomic_read(&lock->val); + + for (;;) { + new = (val & _Q_LOCKED_PENDING_MASK) | tail; + old = atomic_cmpxchg(&lock->val, val, new); + if (old == val) + break; + + val = old; + } + return old; +} + +/** * queue_spin_lock_slowpath - acquire the queue spinlock * @lock: Pointer to queue spinlock structure * @val: Current value of the queue spinlock 32-bit word @@ -178,15 +214,7 @@ void queue_spin_lock_slowpath(struct qspinlock *lock, u32 val) * * *,1,0 -> *,0,1 */ - for (;;) { - new = (val & ~_Q_PENDING_MASK) | _Q_LOCKED_VAL; - - old = atomic_cmpxchg(&lock->val, val, new); - if (old == val) - break; - - val = old; - } + clear_pending_set_locked(lock); return; /* @@ -203,37 +231,26 @@ queue: node->next = NULL; /* - * We have already touched the queueing cacheline; don't bother with - * pending stuff. - * - * trylock || xchg(lock, node) - * - * 0,0,0 -> 0,0,1 ; no tail, not locked -> no tail, locked. - * p,y,x -> n,y,x ; tail was p -> tail is n; preserving locked. + * We touched a (possibly) cold cacheline in the per-cpu queue node; + * attempt the trylock once more in the hope someone let go while we + * weren't watching. */ - for (;;) { - new = _Q_LOCKED_VAL; - if (val) - new = tail | (val & _Q_LOCKED_PENDING_MASK); - - old = atomic_cmpxchg(&lock->val, val, new); - if (old == val) - break; - - val = old; - } + if (queue_spin_trylock(lock)) + goto release; /* - * we won the trylock; forget about queueing. + * We have already touched the queueing cacheline; don't bother with + * pending stuff. + * + * p,*,* -> n,*,* */ - if (new == _Q_LOCKED_VAL) - goto release; + old = xchg_tail(lock, tail); /* * if there was a previous node; link it and wait until reaching the * head of the waitqueue. */ - if (old & ~_Q_LOCKED_PENDING_MASK) { + if (old & _Q_TAIL_MASK) { prev = decode_tail(old); WRITE_ONCE(prev->next, node); -- 1.7.1
WARNING: multiple messages have this Message-ID (diff)
From: Waiman Long <Waiman.Long@hp.com> To: Thomas Gleixner <tglx@linutronix.de>, Ingo Molnar <mingo@redhat.com>, "H. Peter Anvin" <hpa@zytor.com> Cc: linux-arch@vger.kernel.org, x86@kernel.org, linux-kernel@vger.kernel.org, virtualization@lists.linux-foundation.org, xen-devel@lists.xenproject.org, kvm@vger.kernel.org, Paolo Bonzini <paolo.bonzini@gmail.com>, Konrad Rzeszutek Wilk <konrad.wilk@oracle.com>, Boris Ostrovsky <boris.ostrovsky@oracle.com>, "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>, Rik van Riel <riel@redhat.com>, Linus Torvalds <torvalds@linux-foundation.org>, Raghavendra K T <raghavendra.kt@linux.vnet.ibm.com>, David Vrabel <david.vrabel@citrix.com>, Oleg Nesterov <oleg@redhat.com>, Daniel J Blueman <daniel@numascale.com>, Scott J Norton <scott.norton@hp.com>, Douglas Hatch <doug.hatch@hp.com>, Waiman Long <Waiman.Long@hp.com>, "Peter Zijlstra (Intel)" <peterz@infradead.org> Subject: [PATCH v16 04/14] qspinlock: Extract out code snippets for the next patch Date: Fri, 24 Apr 2015 14:56:33 -0400 [thread overview] Message-ID: <1429901803-29771-5-git-send-email-Waiman.Long@hp.com> (raw) In-Reply-To: <1429901803-29771-1-git-send-email-Waiman.Long@hp.com> This is a preparatory patch that extracts out the following 2 code snippets to prepare for the next performance optimization patch. 1) the logic for the exchange of new and previous tail code words into a new xchg_tail() function. 2) the logic for clearing the pending bit and setting the locked bit into a new clear_pending_set_locked() function. This patch also simplifies the trylock operation before queuing by calling queue_spin_trylock() directly. Signed-off-by: Waiman Long <Waiman.Long@hp.com> Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org> --- include/asm-generic/qspinlock_types.h | 2 + kernel/locking/qspinlock.c | 79 ++++++++++++++++++++------------- 2 files changed, 50 insertions(+), 31 deletions(-) diff --git a/include/asm-generic/qspinlock_types.h b/include/asm-generic/qspinlock_types.h index 9c3f5c2..ef36613 100644 --- a/include/asm-generic/qspinlock_types.h +++ b/include/asm-generic/qspinlock_types.h @@ -58,6 +58,8 @@ typedef struct qspinlock { #define _Q_TAIL_CPU_BITS (32 - _Q_TAIL_CPU_OFFSET) #define _Q_TAIL_CPU_MASK _Q_SET_MASK(TAIL_CPU) +#define _Q_TAIL_MASK (_Q_TAIL_IDX_MASK | _Q_TAIL_CPU_MASK) + #define _Q_LOCKED_VAL (1U << _Q_LOCKED_OFFSET) #define _Q_PENDING_VAL (1U << _Q_PENDING_OFFSET) diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c index 0351f78..11f6ad9 100644 --- a/kernel/locking/qspinlock.c +++ b/kernel/locking/qspinlock.c @@ -97,6 +97,42 @@ static inline struct mcs_spinlock *decode_tail(u32 tail) #define _Q_LOCKED_PENDING_MASK (_Q_LOCKED_MASK | _Q_PENDING_MASK) /** + * clear_pending_set_locked - take ownership and clear the pending bit. + * @lock: Pointer to queue spinlock structure + * + * *,1,0 -> *,0,1 + */ +static __always_inline void clear_pending_set_locked(struct qspinlock *lock) +{ + atomic_add(-_Q_PENDING_VAL + _Q_LOCKED_VAL, &lock->val); +} + +/** + * xchg_tail - Put in the new queue tail code word & retrieve previous one + * @lock : Pointer to queue spinlock structure + * @tail : The new queue tail code word + * Return: The previous queue tail code word + * + * xchg(lock, tail) + * + * p,*,* -> n,*,* ; prev = xchg(lock, node) + */ +static __always_inline u32 xchg_tail(struct qspinlock *lock, u32 tail) +{ + u32 old, new, val = atomic_read(&lock->val); + + for (;;) { + new = (val & _Q_LOCKED_PENDING_MASK) | tail; + old = atomic_cmpxchg(&lock->val, val, new); + if (old == val) + break; + + val = old; + } + return old; +} + +/** * queue_spin_lock_slowpath - acquire the queue spinlock * @lock: Pointer to queue spinlock structure * @val: Current value of the queue spinlock 32-bit word @@ -178,15 +214,7 @@ void queue_spin_lock_slowpath(struct qspinlock *lock, u32 val) * * *,1,0 -> *,0,1 */ - for (;;) { - new = (val & ~_Q_PENDING_MASK) | _Q_LOCKED_VAL; - - old = atomic_cmpxchg(&lock->val, val, new); - if (old == val) - break; - - val = old; - } + clear_pending_set_locked(lock); return; /* @@ -203,37 +231,26 @@ queue: node->next = NULL; /* - * We have already touched the queueing cacheline; don't bother with - * pending stuff. - * - * trylock || xchg(lock, node) - * - * 0,0,0 -> 0,0,1 ; no tail, not locked -> no tail, locked. - * p,y,x -> n,y,x ; tail was p -> tail is n; preserving locked. + * We touched a (possibly) cold cacheline in the per-cpu queue node; + * attempt the trylock once more in the hope someone let go while we + * weren't watching. */ - for (;;) { - new = _Q_LOCKED_VAL; - if (val) - new = tail | (val & _Q_LOCKED_PENDING_MASK); - - old = atomic_cmpxchg(&lock->val, val, new); - if (old == val) - break; - - val = old; - } + if (queue_spin_trylock(lock)) + goto release; /* - * we won the trylock; forget about queueing. + * We have already touched the queueing cacheline; don't bother with + * pending stuff. + * + * p,*,* -> n,*,* */ - if (new == _Q_LOCKED_VAL) - goto release; + old = xchg_tail(lock, tail); /* * if there was a previous node; link it and wait until reaching the * head of the waitqueue. */ - if (old & ~_Q_LOCKED_PENDING_MASK) { + if (old & _Q_TAIL_MASK) { prev = decode_tail(old); WRITE_ONCE(prev->next, node); -- 1.7.1
next prev parent reply other threads:[~2015-04-24 18:57 UTC|newest] Thread overview: 90+ messages / expand[flat|nested] mbox.gz Atom feed top 2015-04-24 18:56 [PATCH v16 00/14] qspinlock: a 4-byte queue spinlock with PV support Waiman Long 2015-04-24 18:56 ` [PATCH v16 01/14] qspinlock: A simple generic 4-byte queue spinlock Waiman Long 2015-04-24 18:56 ` Waiman Long 2015-04-24 18:56 ` Waiman Long 2015-04-24 18:56 ` Waiman Long 2015-05-08 13:25 ` [tip:locking/core] locking/qspinlock: Introduce a simple generic 4-byte queued spinlock tip-bot for Waiman Long 2015-04-24 18:56 ` [PATCH v16 02/14] qspinlock, x86: Enable x86-64 to use queue spinlock Waiman Long 2015-04-24 18:56 ` Waiman Long 2015-04-24 18:56 ` Waiman Long 2015-04-24 18:56 ` Waiman Long 2015-05-08 13:25 ` [tip:locking/core] locking/qspinlock, x86: Enable x86-64 to use queued spinlocks tip-bot for Waiman Long 2015-04-24 18:56 ` [PATCH v16 03/14] qspinlock: Add pending bit Waiman Long 2015-04-24 18:56 ` Waiman Long 2015-04-24 18:56 ` Waiman Long 2015-04-24 18:56 ` Waiman Long 2015-05-08 13:26 ` [tip:locking/core] locking/qspinlock: " tip-bot for Peter Zijlstra (Intel) 2015-04-24 18:56 ` [PATCH v16 04/14] qspinlock: Extract out code snippets for the next patch Waiman Long 2015-04-24 18:56 ` Waiman Long 2015-04-24 18:56 ` Waiman Long [this message] 2015-04-24 18:56 ` Waiman Long 2015-05-08 13:26 ` [tip:locking/core] locking/qspinlock: " tip-bot for Waiman Long 2015-04-24 18:56 ` [PATCH v16 05/14] qspinlock: Optimize for smaller NR_CPUS Waiman Long 2015-04-24 18:56 ` Waiman Long 2015-04-24 18:56 ` Waiman Long 2015-04-24 18:56 ` Waiman Long 2015-05-08 13:26 ` [tip:locking/core] locking/qspinlock: " tip-bot for Peter Zijlstra (Intel) 2015-04-24 18:56 ` [PATCH v16 06/14] qspinlock: Use a simple write to grab the lock Waiman Long 2015-04-24 18:56 ` Waiman Long 2015-04-24 18:56 ` Waiman Long 2015-04-24 18:56 ` Waiman Long 2015-05-08 13:27 ` [tip:locking/core] locking/qspinlock: " tip-bot for Waiman Long 2015-04-24 18:56 ` [PATCH v16 07/14] qspinlock: Revert to test-and-set on hypervisors Waiman Long 2015-04-24 18:56 ` Waiman Long 2015-04-24 18:56 ` Waiman Long 2015-05-08 13:27 ` [tip:locking/core] locking/qspinlock: " tip-bot for Peter Zijlstra (Intel) 2015-04-24 18:56 ` [PATCH v16 07/14] qspinlock: " Waiman Long 2015-04-24 18:56 ` [PATCH v16 08/14] pvqspinlock: Implement simple paravirt support for the qspinlock Waiman Long 2015-04-24 18:56 ` Waiman Long 2015-05-04 14:20 ` Peter Zijlstra 2015-05-04 14:20 ` Peter Zijlstra 2015-05-04 14:20 ` Peter Zijlstra 2015-05-04 17:15 ` Waiman Long 2015-05-04 17:15 ` Waiman Long 2015-05-04 17:15 ` Waiman Long 2015-05-08 13:27 ` [tip:locking/core] locking/pvqspinlock: " tip-bot for Waiman Long 2015-04-24 18:56 ` [PATCH v16 08/14] pvqspinlock: " Waiman Long 2015-04-24 18:56 ` [PATCH v16 09/14] pvqspinlock, x86: Implement the paravirt qspinlock call patching Waiman Long 2015-04-24 18:56 ` Waiman Long 2015-05-08 13:27 ` [tip:locking/core] locking/pvqspinlock, " tip-bot for Peter Zijlstra (Intel) 2015-05-30 4:09 ` Sasha Levin 2015-05-31 18:29 ` Waiman Long 2015-04-24 18:56 ` [PATCH v16 09/14] pvqspinlock, " Waiman Long 2015-04-24 18:56 ` Waiman Long 2015-04-24 18:56 ` [PATCH v16 10/14] pvqspinlock, x86: Enable PV qspinlock for KVM Waiman Long 2015-04-24 18:56 ` Waiman Long 2015-04-24 18:56 ` Waiman Long 2015-05-08 13:28 ` [tip:locking/core] locking/pvqspinlock, " tip-bot for Waiman Long 2015-04-24 18:56 ` [PATCH v16 11/14] pvqspinlock, x86: Enable PV qspinlock for Xen Waiman Long 2015-04-24 18:56 ` Waiman Long 2015-04-24 18:56 ` Waiman Long 2015-05-08 13:28 ` [tip:locking/core] locking/pvqspinlock, " tip-bot for David Vrabel 2015-04-24 18:56 ` [PATCH v16 12/14] pvqspinlock: Only kick CPU at unlock time Waiman Long 2015-04-24 18:56 ` Waiman Long 2015-04-24 18:56 ` Waiman Long 2015-04-24 18:56 ` [PATCH v16 13/14] pvqspinlock: Improve slowpath performance by avoiding cmpxchg Waiman Long 2015-04-24 18:56 ` Waiman Long 2015-04-24 18:56 ` Waiman Long 2015-04-29 18:11 ` Peter Zijlstra 2015-04-29 18:27 ` Linus Torvalds 2015-04-29 18:27 ` Linus Torvalds 2015-04-29 18:27 ` Linus Torvalds 2015-04-30 18:56 ` Waiman Long 2015-04-30 18:56 ` Waiman Long 2015-04-30 18:56 ` Waiman Long 2015-04-30 18:56 ` Waiman Long 2015-04-30 18:56 ` Waiman Long 2015-04-30 18:49 ` Waiman Long 2015-04-30 18:49 ` Waiman Long 2015-04-30 18:49 ` Waiman Long 2015-05-04 14:05 ` Peter Zijlstra 2015-05-04 14:05 ` Peter Zijlstra 2015-05-04 14:05 ` Peter Zijlstra 2015-05-04 17:18 ` Waiman Long 2015-05-04 17:18 ` Waiman Long 2015-05-04 17:18 ` Waiman Long 2015-04-29 18:11 ` Peter Zijlstra 2015-04-29 18:11 ` Peter Zijlstra 2015-04-24 18:56 ` [PATCH v16 14/14] pvqspinlock: Collect slowpath lock statistics Waiman Long 2015-04-24 18:56 ` Waiman Long 2015-04-24 18:56 ` Waiman Long
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=1429901803-29771-5-git-send-email-Waiman.Long@hp.com \ --to=waiman.long@hp.com \ --cc=boris.ostrovsky@oracle.com \ --cc=daniel@numascale.com \ --cc=david.vrabel@citrix.com \ --cc=doug.hatch@hp.com \ --cc=hpa@zytor.com \ --cc=konrad.wilk@oracle.com \ --cc=kvm@vger.kernel.org \ --cc=linux-arch@vger.kernel.org \ --cc=linux-kernel@vger.kernel.org \ --cc=mingo@redhat.com \ --cc=oleg@redhat.com \ --cc=paolo.bonzini@gmail.com \ --cc=paulmck@linux.vnet.ibm.com \ --cc=peterz@infradead.org \ --cc=raghavendra.kt@linux.vnet.ibm.com \ --cc=riel@redhat.com \ --cc=scott.norton@hp.com \ --cc=tglx@linutronix.de \ --cc=torvalds@linux-foundation.org \ --cc=virtualization@lists.linux-foundation.org \ --cc=x86@kernel.org \ --cc=xen-devel@lists.xenproject.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.