locking/qspinlock: Enhance pvqspinlock performance
Subsystems (3)
v6 cover locking/qspinlock: Enhance pvqspinlock performance
v5->v6:
- Added a new patch 1 to relax the cmpxchg and xchg operations in the native code path to reduce performance overhead on non-x86 architectures.
- Updated the unconditional PV kick patch as suggested by PeterZ.
- Added a new patch to allow one lock stealing attempt at slowpath entry point to reduce performance penalty due to lock waiter preemption.
- Removed the pending bit and kick-ahead patches as they didn't show any noticeable performance improvement on top of the lock stealing patch.
- Simplified the adaptive spinning patch as the lock stealing patch allows more aggressive pv_wait() without much performance penalty in non-overcommitted VMs.
v4->v5:
- Rebased the patch to the latest tip tree.
- Corrected the comments and commit log for patch 1.
- Removed the v4 patch 5 as PV kick deferment is no longer needed with the new tip tree.
- Simplified the adaptive spinning patch (patch 6) & improve its performance a bit further.
- Re-ran the benchmark test with the new patch.
v3->v4:
- Patch 1: add comment about possible racing condition in PV unlock.
- Patch 2: simplified the pv_pending_lock() function as suggested by Davidlohr.
- Move PV unlock optimization patch forward to patch 4 & rerun performance test.
v2->v3:
- Moved deferred kicking enablement patch forward & move back the kick-ahead patch to make the effect of kick-ahead more visible.
- Reworked patch 6 to make it more readable.
- Reverted back to use state as a tri-state variable instead of adding an additional bistate variable.
- Added performance data for different values of PV_KICK_AHEAD_MAX.
- Add a new patch to optimize PV unlock code path performance.
v1->v2:
- Take out the queued unfair lock patches
- Add a patch to simplify the PV unlock code
- Move pending bit and statistics collection patches to the front
- Keep vCPU kicking in pv_kick_node(), but defer it to unlock time when appropriate.
- Change the wait-early patch to use adaptive spinning to better balance the difference effect on normal and over-committed guests.
- Add patch-to-patch performance changes in the patch commit logs.
This patchset tries to improve the performance of both regular and over-commmitted VM guests. The adaptive spinning patch was inspired by the "Do Virtual Machines Really Scale?" blog from Sanidhya Kashyap.
Patch 1 relaxes the memory order restriction of atomic operations by using less restrictive _acquire and _release variants of cmpxchg() and xchg(). This will reduce performance overhead when ported to other non-x86 architectures.
Patch 2 simplifies the unlock code by removing the unnecessary state check.
Patch 2 adds pending bit support to pvqspinlock improving performance at light load.
Patch 3 optimizes the PV unlock code path performance for x86-64 architecture.
Patch 4 allows the collection of various count data that are useful to see what is happening in the system. They do add a bit of overhead when enabled slowing performance a tiny bit.
Patch 5 allows one lock stealing attempt at slowpath entry. This causes a pretty big performance improvement for over-committed VM guests.
Patch 6 enables adaptive spinning in the queue nodes. This patch leads to further performance improvement in over-committed guest, though it is not as big as the previous patch.
Waiman Long (6):
locking/qspinlock: relaxes cmpxchg & xchg ops in native code locking/pvqspinlock: Unconditional PV kick with _Q_SLOW_VAL locking/pvqspinlock, x86: Optimize PV unlock code path locking/pvqspinlock: Collect slowpath lock statistics locking/pvqspinlock: Allow 1 lock stealing attempt locking/pvqspinlock: Queue node adaptive spinning
arch/x86/Kconfig | 7 + arch/x86/include/asm/qspinlock.h | 2 +- arch/x86/include/asm/qspinlock_paravirt.h | 59 +++++ include/asm-generic/qspinlock.h | 6 +- kernel/locking/qspinlock.c | 45 +++-- kernel/locking/qspinlock_paravirt.h | 378 +++++++++++++++++++++++++---- 6 files changed, 431 insertions(+), 66 deletions(-)
PATCH v6 1/6 locking/qspinlock: relaxes cmpxchg & xchg ops in native code
This patch replaces the cmpxchg() and xchg() calls in the native qspinlock code with more relaxed versions of those calls to enable other architectures to adopt queued spinlocks with less performance overhead.
--- arch/x86/include/asm/qspinlock.h | 2 +- include/asm-generic/qspinlock.h | 6 +++--- kernel/locking/qspinlock.c | 21 +++++++++++++++++---- 3 files changed, 21 insertions(+), 8 deletions(-)
arch/x86/include/asm/qspinlock.h +1 -1
@@ -46,7 +46,7 @@ static inline bool virt_queued_spin_lock(struct qspinlock *lock)if (!static_cpu_has (X86_FEATURE_HYPERVISOR ))return false; -while (atomic_cmpxchg (&lock->val,0 , _Q_LOCKED_VAL) !=0 ) +while (atomic_cmpxchg_acquire (&lock->val,0 , _Q_LOCKED_VAL) !=0 )cpu_relax ();return true;
include/asm-generic/qspinlock.h +3 -3
@@ -62,7 +62,7 @@ static __always_inline int queued_spin_is_contended(struct qspinlock *lock) static __always_inline int queued_spin_trylock(struct qspinlock *lock) {if (!atomic_read (&lock->val) && - (atomic_cmpxchg (&lock->val,0 , _Q_LOCKED_VAL) ==0 )) + (atomic_cmpxchg_acquire (&lock->val,0 , _Q_LOCKED_VAL) ==0 ))return 1 ;return 0 ; }
@@ -77,7 +77,7 @@ static __always_inline void queued_spin_lock(struct qspinlock *lock) {u32 val; - val =atomic_cmpxchg (&lock->val,0 , _Q_LOCKED_VAL); + val =atomic_cmpxchg_acquire (&lock->val,0 , _Q_LOCKED_VAL);if (likely (val ==0 ))return ;queued_spin_lock_slowpath (lock, val);
@@ -93,7 +93,7 @@ static __always_inline void queued_spin_unlock(struct qspinlock *lock)/* * smp_mb__before_atomic() in order to guarantee release semantics */ -smp_mb__before_atomic_dec (); +smp_mb__before_atomic (); atomic_sub(_Q_LOCKED_VAL, &lock->val); }#endif
kernel/locking/qspinlock.c +17 -4
@@ -176,7 +176,12 @@ static __always_inline u32 xchg_tail(struct qspinlock *lock, u32 tail) {struct __qspinlock *l = (void *)lock; -return (u32 )xchg (&l->tail, tail >> _Q_TAIL_OFFSET) << _Q_TAIL_OFFSET; +/* +* Use release semantics to make sure that the MCS node is properly +* initialized before changing the tail code. +*/ +return (u32 )xchg_release (&l->tail, + tail >> _Q_TAIL_OFFSET) << _Q_TAIL_OFFSET; }#else /* _Q_PENDING_BITS == 8 */
@@ -208,7 +213,11 @@ static __always_inline u32 xchg_tail(struct qspinlock *lock, u32 tail)for (;;) { new = (val & _Q_LOCKED_PENDING_MASK) | tail; - old =atomic_cmpxchg (&lock->val, val, new); +/* +* Use release semantics to make sure that the MCS node is +* properly initialized before changing the tail code. +*/ + old =atomic_cmpxchg_release (&lock->val, val, new);if (old == val)break ;
@@ -319,7 +328,7 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)if (val == new) new |= _Q_PENDING_VAL; - old =atomic_cmpxchg (&lock->val, val, new); + old =atomic_cmpxchg_acquire (&lock->val, val, new);if (old == val)break ;
@@ -426,7 +435,11 @@ queue:set_locked (lock);break ; } - old =atomic_cmpxchg (&lock->val, val, _Q_LOCKED_VAL); +/* +* The smp_load_acquire() call above has provided the necessary +* acquire semantics required for locking. +*/ + old =atomic_cmpxchg_relaxed (&lock->val, val, _Q_LOCKED_VAL);if (old == val) goto release;/* No contention */
Signature · 1 line
1.7.1
Re: [PATCH v6 1/6] locking/qspinlock: relaxes cmpxchg & xchg ops in native code
arch/x86/include/asm/qspinlock.h static inline bool virt_queued_spin_lock(struct qspinlock *lock) · line 50
Quoted 7 lines · Waiman Long
arch/x86/include/asm/qspinlock.h +1
-1@@ -46,7 +46,7 @@ static inline bool virt_queued_spin_lock(struct qspinlock *lock)if (!static_cpu_has (X86_FEATURE_HYPERVISOR ))return false; -while (atomic_cmpxchg (&lock->val,0 , _Q_LOCKED_VAL) !=0 ) +while (atomic_cmpxchg_acquire (&lock->val,0 , _Q_LOCKED_VAL) !=0 )cpu_relax ();
This code has changed with Peter's recent ccas fix. And the whole virt_queued_spin_lock() thing will now be under pv configs. So this doesn't apply to native code anymore, so it looks like it should be dropped altogether.
Thanks,
Davidlohr
Peter Zijlstra
maintainerRe: [PATCH v6 1/6] locking/qspinlock: relaxes cmpxchg & xchg ops in native code
Quoted 6 lines · Davidlohr Bueso
Quoted 4 lines · Waiman Long
arch/x86/include/asm/qspinlock.h +0
-0@@ -46,7 +46,7 @@ static inline bool virt_queued_spin_lock(struct qspinlock *lock)if (!static_cpu_has (X86_FEATURE_HYPERVISOR ))return false;
Quoted 7 lines
arch/x86/include/asm/qspinlock.h static inline bool virt_queued_spin_lock(struct qspinlock *lock) · line 50
Quoted 3 lines
arch/x86/include/asm/qspinlock.h +1
-1-while (atomic_cmpxchg (&lock->val,0 , _Q_LOCKED_VAL) !=0 ) +while (atomic_cmpxchg_acquire (&lock->val,0 , _Q_LOCKED_VAL) !=0 )cpu_relax ();This code has changed with Peter's recent ccas fix. And the whole
virt_queued_spin_lock()thing will now be under pv configs. So this doesn't apply to native code anymore, so it looks like it should be dropped altogether.
Yeah, it also doesn't make sense, this ix x86 arch code, x86 cannot do cmpxchg_acquire. Then again, I suppose we could argue its of documentation value..
Re: [PATCH v6 1/6] locking/qspinlock: relaxes cmpxchg & xchg ops in native code
Quoted 13 lines · Peter Zijlstra
Quoted 6 lines · Davidlohr Bueso
Quoted 4 lines · Waiman Long
arch/x86/include/asm/qspinlock.h +0
-0@@ -46,7 +46,7 @@ static inline bool virt_queued_spin_lock(struct qspinlock *lock)if (!static_cpu_has (X86_FEATURE_HYPERVISOR ))return false;Quoted 6 lines
arch/x86/include/asm/qspinlock.h static inline bool virt_queued_spin_lock(struct qspinlock *lock) · line 50
Quoted 3 lines
arch/x86/include/asm/qspinlock.h +1
-1-while (atomic_cmpxchg (&lock->val,0 , _Q_LOCKED_VAL) !=0 ) +while (atomic_cmpxchg_acquire (&lock->val,0 , _Q_LOCKED_VAL) !=0 )cpu_relax ();This code has changed with Peter's recent ccas fix. And the whole
virt_queued_spin_lock()thing will now be under pv configs. So this doesn't apply to native code anymore, so it looks like it should be dropped altogether.
Quoted 3 lines
Yeah, it also doesn't make sense, this ix x86 arch code, x86 cannot do
cmpxchg_acquire. Then again, I suppose we could argue its of documentation value..
Yes, it is to be consistent with the change in asm_generic qspinlock.h. We can certainly skip that.
Cheers,
Longman
Re: [PATCH v6 1/6] locking/qspinlock: relaxes cmpxchg & xchg ops in native code
In reply to Davidlohr BuesoQuoted 15 lines · Davidlohr Bueso
arch/x86/include/asm/qspinlock.h static inline bool virt_queued_spin_lock(struct · line 51
Quoted 8 lines · Waiman Long
arch/x86/include/asm/qspinlock.h +1
-1@@ -46,7 +46,7 @@ static inline bool virt_queued_spin_lock(struct qspinlock *lock)if (!static_cpu_has (X86_FEATURE_HYPERVISOR ))return false; -while (atomic_cmpxchg (&lock->val,0 , _Q_LOCKED_VAL) !=0 ) +while (atomic_cmpxchg_acquire (&lock->val,0 , _Q_LOCKED_VAL) !=0 )cpu_relax ();This code has changed with Peter's recent ccas fix. And the whole
virt_queued_spin_lock()thing will now be under pv configs. So this doesn't apply to native code anymore, so it looks like it should be dropped altogether.
Quoted 2 lines
Thanks,
Davidlohr
You are right. Patch 1 needs to be updated on top of PeterZ latest patch.
Cheers,
Longman
PATCH v6 2/6 locking/pvqspinlock: Unconditional PV kick with _Q_SLOW_VAL
In reply to Waiman LongIf _Q_SLOW_VAL has been set, the vCPU state must have been vcpu_hashed. The extra check at the end of __pv_queued_spin_unlock() is unnecessary and so is removed.
--- kernel/locking/qspinlock_paravirt.h | 6 +----- 1 files changed, 1 insertions(+), 5 deletions(-)
kernel/locking/qspinlock_paravirt.h +1 -5
@@ -267,7 +267,6 @@ static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node) }if (!lp) {/* ONCE */ -WRITE_ONCE (pn->state, vcpu_hashed); lp =pv_hash (lock, pn);/*
@@ -275,11 +274,9 @@ static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node)* when we observe _Q_SLOW_VAL in __pv_queued_spin_unlock() * we'll be sure to be able to observe our hash entry. * -* [S] pn->state * [S] <hash> [Rmw] l->locked == _Q_SLOW_VAL * MB RMB * [RmW] l->locked = _Q_SLOW_VAL [L] <unhash> -* [L] pn->state * * Matches the smp_rmb() in __pv_queued_spin_unlock(). */
@@ -364,8 +361,7 @@ __visible void __pv_queued_spin_unlock(struct qspinlock *lock)* vCPU is harmless other than the additional latency in completing * the unlock. */ -if (READ_ONCE (node->state) == vcpu_hashed) -pv_kick (node->cpu); +pv_kick (node->cpu); }/* * Include the architecture specific callee-save thunk of the
Signature · 1 line
1.7.1
tip-bot for Waiman Long
merge bot[tip:locking/core] locking/pvqspinlock: Kick the PV CPU unconditionally when _Q_SLOW_VAL
locking/pvqspinlock: Kick the PV CPU unconditionally when _Q_SLOW_VAL
Commit-ID: 93edc8bd7750ff3cae088bfca453ea73dc9004a4 Gitweb: http://git.kernel.org/tip/93edc8bd7750ff3cae088bfca453ea73dc9004a4 Author: Waiman Long <[email protected]> AuthorDate: Fri, 11 Sep 2015 14:37:34 -0400 Committer: Ingo Molnar <[email protected]> CommitDate: Fri, 18 Sep 2015 09:27:29 +0200
locking/pvqspinlock: Kick the PV CPU unconditionally when _Q_SLOW_VAL
If _Q_SLOW_VAL has been set, the vCPU state must have been vcpu_hashed. The extra check at the end of __pv_queued_spin_unlock() is unnecessary and can be removed.
--- kernel/locking/qspinlock_paravirt.h | 6 +----- 1 file changed, 1 insertion(+), 5 deletions(-)
kernel/locking/qspinlock_paravirt.h +1 -5
@@ -267,7 +267,6 @@ static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node) }if (!lp) {/* ONCE */ -WRITE_ONCE (pn->state, vcpu_hashed); lp =pv_hash (lock, pn);/*
@@ -275,11 +274,9 @@ static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node)* when we observe _Q_SLOW_VAL in __pv_queued_spin_unlock() * we'll be sure to be able to observe our hash entry. * -* [S] pn->state * [S] <hash> [Rmw] l->locked == _Q_SLOW_VAL * MB RMB * [RmW] l->locked = _Q_SLOW_VAL [L] <unhash> -* [L] pn->state * * Matches the smp_rmb() in __pv_queued_spin_unlock(). */
@@ -364,8 +361,7 @@ __visible void __pv_queued_spin_unlock(struct qspinlock *lock)* vCPU is harmless other than the additional latency in completing * the unlock. */ -if (READ_ONCE (node->state) == vcpu_hashed) -pv_kick (node->cpu); +pv_kick (node->cpu); }/* * Include the architecture specific callee-save thunk of the
PATCH v6 3/6 locking/pvqspinlock, x86: Optimize PV unlock code path
In reply to Waiman LongThe unlock function in queued spinlocks was optimized for better performance on bare metal systems at the expense of virtualized guests.
For x86-64 systems, the unlock call needs to go through a PV_CALLEE_SAVE_REGS_THUNK() which saves and restores 8 64-bit registers before calling the real __pv_queued_spin_unlock() function. The thunk code may also be in a separate cacheline from __pv_queued_spin_unlock().
This patch optimizes the PV unlock code path by:
1) Moving the unlock slowpath code from the fastpath into a separate __pv_queued_spin_unlock_slowpath() function to make the fastpath as simple as possible..
2) For x86-64, hand-coded an assembly function to combine the register saving thunk code with the fastpath code. Only registers that are used in the fastpath will be saved and restored. If the fastpath fails, the slowpath function will be called via another PV_CALLEE_SAVE_REGS_THUNK(). For 32-bit, it falls back to the C __pv_queued_spin_unlock() code as the thunk saves and restores only one 32-bit register.
With a microbenchmark of 5M lock-unlock loop, the table below shows the execution times before and after the patch with different number of threads in a VM running on a 32-core Westmere-EX box with x86-64 4.2-rc1 based kernels:
Threads Before patch After patch % Change
------- ------------ ----------- --------
1 134.1 ms 119.3 ms -11%
2 1286 ms 953 ms -26%
3 3715 ms 3480 ms -6.3%
4 4092 ms 3764 ms -8.0%--- arch/x86/include/asm/qspinlock_paravirt.h | 59 +++++++++++++++++++++++++++++ kernel/locking/qspinlock_paravirt.h | 43 +++++++++++++-------- 2 files changed, 86 insertions(+), 16 deletions(-)
arch/x86/include/asm/qspinlock_paravirt.h +59 -0
@@ -1,6 +1,65 @@#ifndef __ASM_QSPINLOCK_PARAVIRT_H#define __ASM_QSPINLOCK_PARAVIRT_H +/* +* For x86-64, PV_CALLEE_SAVE_REGS_THUNK() saves and restores 8 64-bit +* registers. For i386, however, only 1 32-bit register needs to be saved +* and restored. So an optimized version of __pv_queued_spin_unlock() is +* hand-coded for 64-bit, but it isn't worthwhile to do it for 32-bit. +*/ +#ifdef CONFIG_64BIT + +PV_CALLEE_SAVE_REGS_THUNK (__pv_queued_spin_unlock_slowpath); +#define __pv_queued_spin_unlock __pv_queued_spin_unlock +#define PV_UNLOCK "__raw_callee_save___pv_queued_spin_unlock" +#define PV_UNLOCK_SLOWPATH "__raw_callee_save___pv_queued_spin_unlock_slowpath" + +/* +* Optimized assembly version of __raw_callee_save___pv_queued_spin_unlock +* which combines the registers saving trunk and the body of the following +* C code: +* +* void __pv_queued_spin_unlock(struct qspinlock *lock) +* { +* struct __qspinlock *l = (void *)lock; +* u8 lockval = cmpxchg(&l->locked, _Q_LOCKED_VAL, 0); +* +* if (likely(lockval == _Q_LOCKED_VAL)) +* return; +* pv_queued_spin_unlock_slowpath(lock, lockval); +* } +* +* For x86-64, +* rdi = lock (first argument) +* rsi = lockval (second argument) +* rdx = internal variable (set to 0) +*/ +asm(".pushsection .text;" +".globl " PV_UNLOCK ";" +".align 4,0x90;" +PV_UNLOCK ": " +"push %rdx;" +"mov $0x1,%eax;" +"xor %edx,%edx;" +"lock cmpxchg %dl,(%rdi);" +"cmp $0x1,%al;" +"jne .slowpath;" +"pop %rdx;" +"ret;" +".slowpath: " +"push %rsi;" +"movzbl %al,%esi;" +"call " PV_UNLOCK_SLOWPATH ";" +"pop %rsi;" +"pop %rdx;" +"ret;" +".size " PV_UNLOCK ", .-" PV_UNLOCK ";" +".popsection" ); + +#else /* CONFIG_64BIT */ + +extern void __pv_queued_spin_unlock (struct qspinlock *lock);PV_CALLEE_SAVE_REGS_THUNK (__pv_queued_spin_unlock); +#endif /* CONFIG_64BIT */ #endif
kernel/locking/qspinlock_paravirt.h +27 -16
62 lines not on this page · raw message
Signature · 1 line
1.7.1
PATCH v6 4/6 locking/pvqspinlock: Collect slowpath lock statistics
In reply to Waiman LongThis patch enables the accumulation of kicking and waiting related PV qspinlock statistics when the new QUEUED_LOCK_STAT configuration option is selected. It also enables the collection of kicking and wakeup latencies which have a heavy dependency on the CPUs being used.
The measured latencies for different CPUs are:
CPU Wakeup Kicking --- ------ ------- Haswell-EX 63.6us 7.4us Westmere-EX 67.6us 9.3us
The measured latencies varied a bit from run-to-run. The wakeup latency is much higher than the kicking latency.
A sample of statistics counts after system bootup (with vCPU overcommit) was:
hash_hops_count=9001
kick_latencies=138047878
kick_unlock_count=9001
kick_wait_count=9000
spurious_wakeup=3
wait_again_count=2
wait_head_count=10
wait_node_count=8994
wake_latencies=713195944
--- arch/x86/Kconfig | 7 ++ kernel/locking/qspinlock_paravirt.h | 171 ++++++++++++++++++++++++++++++++++- 2 files changed, 173 insertions(+), 5 deletions(-)
arch/x86/Kconfig +7 -0
@@ -719,6 +719,13 @@ config PARAVIRT_SPINLOCKS If you are unsure how to answer this question, answer Y. +config QUEUED_LOCK_STAT + bool "Paravirt queued lock statistics" + depends on PARAVIRT && DEBUG_FS && QUEUED_SPINLOCKS + ---help--- + Enable the collection of statistical data on the behavior of + paravirtualized queued spinlocks and report them on debugfs. + source "arch/x86/xen/Kconfig" config KVM_GUEST
kernel/locking/qspinlock_paravirt.h +166 -5
245 lines not on this page · raw message
Signature · 1 line
1.7.1
Re: [PATCH v6 4/6] locking/pvqspinlock: Collect slowpath lock statistics
Quoted 12 lines · Waiman Long
A sample of statistics counts after system bootup (with vCPU overcommit) was:
hash_hops_count=9001
kick_latencies=138047878
kick_unlock_count=9001
kick_wait_count=9000
spurious_wakeup=3
wait_again_count=2
wait_head_count=10
wait_node_count=8994
wake_latencies=713195944
Any reason you chose not to make the stats per-cpu? The locking numbers don't have to be exact, so you can easily get away with it and suffer from much less overhead that resorting to atomics. Obviously assuming that reading/collecting the stats is done infrequently, such as between workloads or at bootup as you did.
Thanks,
Davidlohr
Re: [PATCH v6 4/6] locking/pvqspinlock: Collect slowpath lock statistics
Quoted 15 lines · Davidlohr Bueso
Quoted 12 lines · Waiman Long
A sample of statistics counts after system bootup (with vCPU overcommit) was:
hash_hops_count=9001
kick_latencies=138047878
kick_unlock_count=9001
kick_wait_count=9000
spurious_wakeup=3
wait_again_count=2
wait_head_count=10
wait_node_count=8994
wake_latencies=713195944
Quoted 8 lines
Any reason you chose not to make the stats per-cpu? The locking numbers don't have to be exact, so you can easily get away with it and suffer from much less overhead that resorting to atomics. Obviously assuming that reading/collecting the stats is done infrequently, such as between workloads or at bootup as you did.
Thanks,
Davidlohr
You can't use debugfs if we want to have per-cpu stats. We will have to use sysfs instead. This will require more code changes. It is certainly doable, but we have to choose between simplicity and performance overhead. Right now, I am assuming that lock PV lockstat is used primarily for debugging purpose and won't be enabled on production system. If we want to have this capability in production systems, we will certainly need to change it to per-cpu stats and use sysfs instead.
The original PV ticketlock code used debugfs and I was just following its footstep. Do you think it is worthwhile to have this capability available on production system by default?
Cheers,
Longman
Re: [PATCH v6 4/6] locking/pvqspinlock: Collect slowpath lock statistics
Quoted 3 lines · Waiman Long
You can't use debugfs if we want to have per-cpu stats. We will have to use sysfs instead. This will require more code changes. It is certainly doable, but we have to choose between simplicity and performance overhead. Right now, I am assuming that lock PV lockstat is used primarily for debugging purpose and won't be enabled on production system. If we want to have this capability in production systems, we will certainly need to change it to per-cpu stats and use sysfs instead.
The original PV ticketlock code used debugfs and I was just following its footstep. Do you think it is worthwhile to have this capability available on production system by default?
If we can prove that the overhead is small enough, and do it correctly (ie see how we do vmstats), it would be _very_ useful data to have enabled by default for debugging performance issues; methinks. But right now we have nowhere near that kind of data, not even with this atomic variant -- although I recall you did mention a workload in a previous iteration (which would be good to have in the changelog).
Re: [PATCH v6 4/6] locking/pvqspinlock: Collect slowpath lock statistics
Quoted 4 lines · Davidlohr Bueso
Quoted 2 lines · Waiman Long
You can't use debugfs if we want to have per-cpu stats. We will have to use sysfs instead. This will require more code changes. It is certainly doable, but we have to choose between simplicity and performance overhead. Right now, I am assuming that lock PV lockstat is used primarily for debugging purpose and won't be enabled on production system. If we want to have this capability in production systems, we will certainly need to change it to per-cpu stats and use sysfs instead.
Quoted 8 lines
Quoted 1 line
The original PV ticketlock code used debugfs and I was just following its footstep. Do you think it is worthwhile to have this capability available on production system by default?
If we can prove that the overhead is small enough, and do it correctly (ie see how we do vmstats), it would be _very_ useful data to have enabled by default for debugging performance issues; methinks. But right now we have nowhere near that kind of data, not even with this atomic variant -- although I recall you did mention a workload in a previous iteration (which would be good to have in the changelog).
Using the per-cpu stats, the overhead should be pretty small as atomic instructions are not needed. I would probably need to encapsulate the stat code into another header file (e.g. qspinlock_pvstat.h) to avoid making the qspinlock_paravirt.h too complex. This will probably be a separate patch once this patch series can be merged.
Cheers,
Longman
PATCH v6 5/6 locking/pvqspinlock: Allow 1 lock stealing attempt
In reply to Waiman LongThis patch allows one attempt for the lock waiter to steal the lock when entering the PV slowpath. This helps to reduce the performance penalty caused by lock waiter preemption while not having much of the downsides of a real unfair lock.
Linux kernel builds were run in KVM guest on an 8-socket, 4 cores/socket Westmere-EX system and a 4-socket, 8 cores/socket Haswell-EX system. Both systems are configured to have 32 physical CPUs. The kernel build times before and after the patch were:
Westmere Haswell
Patch 32 vCPUs 48 vCPUs 32 vCPUs 48 vCPUs ----- -------- -------- -------- -------- Before patch 3m15.6s 10m56.1s 1m44.1s 5m29.1s
After patch 3m02.3s 5m00.2s 1m43.7s 3m03.5s
For the overcommited case (48 vCPUs), this patch is able to reduce kernel build time by more than 54% for Westmere and 44% for Haswell.
--- kernel/locking/qspinlock.c | 19 +++--- kernel/locking/qspinlock_paravirt.h | 116 ++++++++++++++++++++++++++++------- 2 files changed, 102 insertions(+), 33 deletions(-)
kernel/locking/qspinlock.c +8 -11
@@ -248,17 +248,15 @@ static __always_inline void set_locked(struct qspinlock *lock) static __always_inline void __pv_init_node(struct mcs_spinlock *node) { } static __always_inline void __pv_wait_node(struct mcs_spinlock *node) { } -static __always_inline void __pv_kick_node(struct qspinlock *lock, -struct mcs_spinlock *node) { } -static __always_inline void __pv_wait_head(struct qspinlock *lock, -struct mcs_spinlock *node) { } - +static __always_inline bool __pv_wait_head_and_lock(struct qspinlock *lock, +struct mcs_spinlock *node, +u32 tail) + {return false; }#define pv_enabled () false#define pv_init_node __pv_init_node#define pv_wait_node __pv_wait_node -#define pv_kick_node __pv_kick_node -#define pv_wait_head __pv_wait_head +#define pv_wait_head_and_lock __pv_wait_head_and_lock#ifdef CONFIG_PARAVIRT_SPINLOCKS #define queued_spin_lock_slowpath native_queued_spin_lock_slowpath
@@ -416,7 +414,8 @@ queue:* does not imply a full barrier. * */ -pv_wait_head (lock, node); +if (pv_wait_head_and_lock (lock, node, tail)) + goto release;while ((val =smp_load_acquire (&lock->val.counter)) & _Q_LOCKED_PENDING_MASK)cpu_relax ();
@@ -453,7 +452,6 @@ queue:cpu_relax ();arch_mcs_spin_unlock_contended (&next->locked); -pv_kick_node (lock, next); release:/*
@@ -474,8 +472,7 @@ EXPORT_SYMBOL(queued_spin_lock_slowpath);#undef pv_init_node#undef pv_wait_node -#undef pv_kick_node -#undef pv_wait_head +#undef pv_wait_head_and_lock#undef queued_spin_lock_slowpath#define queued_spin_lock_slowpath __pv_queued_spin_lock_slowpath
kernel/locking/qspinlock_paravirt.h +94 -22
198 lines not on this page · raw message
Signature · 1 line
1.7.1
Peter Zijlstra
maintainerRe: [PATCH v6 5/6] locking/pvqspinlock: Allow 1 lock stealing attempt
Quoted 16 lines · Waiman Long
kernel/locking/qspinlock_paravirt.h +15
-0+#define queued_spin_trylock (l) pv_queued_spin_trylock_unfair(l) +static inline bool pv_queued_spin_trylock_unfair (struct qspinlock *lock) +{ +struct __qspinlock *l = (void *)lock; + +if (READ_ONCE (l->locked)) +return 0 ; +/* +* Wait a bit here to ensure that an actively spinning vCPU has a fair +* chance of getting the lock. +*/ +cpu_relax (); + +return cmpxchg (&l->locked,0 , _Q_LOCKED_VAL) ==0 ; +}
kernel/locking/qspinlock_paravirt.h struct pv_node {
Quoted 10 lines
kernel/locking/qspinlock_paravirt.h +10
-0+static inline int pvstat_trylock_unfair (struct qspinlock *lock) +{ +int ret =pv_queued_spin_trylock_unfair (lock); + +if (ret) +pvstat_inc (pvstat_utrylock); +return ret; +} +#undef queued_spin_trylock +#define queued_spin_trylock (l) pvstat_trylock_unfair(l)
These aren't actually ever used...
Re: [PATCH v6 5/6] locking/pvqspinlock: Allow 1 lock stealing attempt
Quoted 19 lines · Peter Zijlstra
Quoted 18 lines · Waiman Long
kernel/locking/qspinlock_paravirt.h +18
-0+#define queued_spin_trylock (l) pv_queued_spin_trylock_unfair(l) +static inline bool pv_queued_spin_trylock_unfair (struct qspinlock *lock) +{ +struct __qspinlock *l = (void *)lock; + +if (READ_ONCE (l->locked)) +return 0 ; +/* +* Wait a bit here to ensure that an actively spinning vCPU has a fair +* chance of getting the lock. +*/ +cpu_relax (); + +return cmpxchg (&l->locked,0 , _Q_LOCKED_VAL) ==0 ; +} +static inline int pvstat_trylock_unfair (struct qspinlock *lock) +{ +int ret =pv_queued_spin_trylock_unfair (lock);
Quoted 8 lines
kernel/locking/qspinlock_paravirt.h static inline void pvstat_hop(int hopcnt) · line 185
Quoted 7 lines
kernel/locking/qspinlock_paravirt.h +7
-0+ +if (ret) +pvstat_inc (pvstat_utrylock); +return ret; +} +#undef queued_spin_trylock +#define queued_spin_trylock (l) pvstat_trylock_unfair(l)These aren't actually ever used...
The pvstat_trylock_unfair() is within the CONFIG_QUEUED_LOCK_STAT block. It will only be activated when the config parameter is set. Otherwise, pv_queued_spin_trylock_unfair() will be used without any counting.
It is used provide count of how many unfair trylock has successfully got the lock.
Cheers,
Longman
Peter Zijlstra
maintainerRe: [PATCH v6 5/6] locking/pvqspinlock: Allow 1 lock stealing attempt
In reply to Waiman LongQuoted 10 lines · Waiman Long
This patch allows one attempt for the lock waiter to steal the lock when entering the PV slowpath. This helps to reduce the performance penalty caused by lock waiter preemption while not having much of the downsides of a real unfair lock.
kernel/locking/qspinlock_paravirt.h +0
-1@@ -415,8 +458,12 @@ static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node)for (;; waitcnt++) {for (loop =SPIN_THRESHOLD ; loop; loop--) { -if (!READ_ONCE (l->locked))
kernel/locking/qspinlock_paravirt.h static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node) · line 469
Quoted 10 lines
kernel/locking/qspinlock_paravirt.h +6
-1-return ; +/* +* Try to acquire the lock when it is free. +*/ +if (!READ_ONCE (l->locked) && + (cmpxchg (&l->locked,0 , _Q_LOCKED_VAL) ==0 )) + goto gotlock;cpu_relax (); }
This isn't _once_, this is once per 'wakeup'. And note that interrupts unrelated to the kick can equally wake the vCPU up.
Re: [PATCH v6 5/6] locking/pvqspinlock: Allow 1 lock stealing attempt
Quoted 7 lines · Peter Zijlstra
Quoted 6 lines · Waiman Long
This patch allows one attempt for the lock waiter to steal the lock when entering the PV slowpath. This helps to reduce the performance penalty caused by lock waiter preemption while not having much of the downsides of a real unfair lock.
(quoted diff) +0
-0@@ -415,8 +458,12 @@ static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node)
Quoted 16 lines
kernel/locking/qspinlock_paravirt.h static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node) · line 469
Quoted 13 lines
kernel/locking/qspinlock_paravirt.h +6
-2for (;; waitcnt++) {for (loop =SPIN_THRESHOLD ; loop; loop--) { -if (!READ_ONCE (l->locked)) -return ; +/* +* Try to acquire the lock when it is free. +*/ +if (!READ_ONCE (l->locked)&& + (cmpxchg (&l->locked,0 , _Q_LOCKED_VAL) ==0 )) + goto gotlock;cpu_relax (); }This isn't _once_, this is once per 'wakeup'. And note that interrupts unrelated to the kick can equally wake the vCPU up.
Oh! There is a minor bug that I shouldn't need to have a second READ_ONCE() call here.
As this is the queue head, finding the lock free entitles the vCPU to own the lock. However, because of lock stealing, I can't just write a 1 to the lock and assume thing is all set. That is why I need to use cmpxchg() to make sure that the queue head vCPU can actually get the lock without the lock stolen underneath. I don't count that as lock stealing as it is the rightful owner of the lock.
I am sorry that I should have added a comment to clarify that. Will do so in the next update.
Quoted 10 lines
void
queued_spin_lock_slowpath(struct qspinlock *lock, u32 val){ : /* * 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. */ if (queued_spin_trylock(lock)) goto release;
This is the only place where I consider lock stealing happens. Again, I should have a comment in pv_queued_spin_trylock_unfair() to say where it will be called.
Cheers,
Longman
Re: [PATCH v6 5/6] locking/pvqspinlock: Allow 1 lock stealing attempt
Quoted 26 lines · Waiman Long
Quoted 8 lines · Peter Zijlstra
Quoted 7 lines · Waiman Long
This patch allows one attempt for the lock waiter to steal the lock when entering the PV slowpath. This helps to reduce the performance penalty caused by lock waiter preemption while not having much of the downsides of a real unfair lock.
(quoted diff) +0
-0@@ -415,8 +458,12 @@ static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node)Quoted 16 lines
kernel/locking/qspinlock_paravirt.h static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node) · line 468
Quoted 13 lines
kernel/locking/qspinlock_paravirt.h +6
-2for (;; waitcnt++) {for (loop =SPIN_THRESHOLD ; loop; loop--) { -if (!READ_ONCE (l->locked)) -return ; +/* +* Try to acquire the lock when it is free. +*/ +if (!READ_ONCE (l->locked)&& + (cmpxchg (&l->locked,0 , _Q_LOCKED_VAL) ==0 )) + goto gotlock;cpu_relax (); }This isn't _once_, this is once per 'wakeup'. And note that interrupts unrelated to the kick can equally wake the vCPU up.
Quoted 1 line
Oh! There is a minor bug that I shouldn't need to have a second
READ_ONCE()call here.
Oh! I misread the diff, the code was OK.
Cheers,
Longman
Peter Zijlstra
maintainerRe: [PATCH v6 5/6] locking/pvqspinlock: Allow 1 lock stealing attempt
In reply to Waiman LongQuoted 3 lines · Waiman Long
Quoted 2 lines · Peter Zijlstra
Quoted 1 line · Waiman Long
This patch allows one attempt for the lock waiter to steal the lock
^^^
Quoted 33 lines
Quoted 23 lines
Quoted 9 lines
when entering the PV slowpath. This helps to reduce the performance penalty caused by lock waiter preemption while not having much of the downsides of a real unfair lock.
kernel/locking/qspinlock_paravirt.h +0
-1@@ -415,8 +458,12 @@ static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node)for (;; waitcnt++) {for (loop =SPIN_THRESHOLD ; loop; loop--) { -if (!READ_ONCE (l->locked))kernel/locking/qspinlock_paravirt.h static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node) · line 469
Quoted 10 lines
kernel/locking/qspinlock_paravirt.h +6
-1-return ; +/* +* Try to acquire the lock when it is free. +*/ +if (!READ_ONCE (l->locked)&& + (cmpxchg (&l->locked,0 , _Q_LOCKED_VAL) ==0 )) + goto gotlock;cpu_relax (); }This isn't _once_, this is once per 'wakeup'. And note that interrupts unrelated to the kick can equally wake the vCPU up.
void
queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)Quoted 9 lines
{ : /* * 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. */ if (queued_spin_trylock(lock)) goto release;
Quoted 3 lines
This is the only place where I consider lock stealing happens. Again, I should have a comment in
pv_queued_spin_trylock_unfair()to say where it will be called.
But you're not adding that..
What you did add is a steal in pv_wait_head(), and its not even once per pv_wait_head, its inside the spin loop (I read it wrong yesterday).
So that makes the entire Changelog complete crap. There isn't _one_ attempt, and there is absolutely no fairness left.
Re: [PATCH v6 5/6] locking/pvqspinlock: Allow 1 lock stealing attempt
Quoted 39 lines · Peter Zijlstra
Quoted 3 lines · Waiman Long
Quoted 2 lines · Peter Zijlstra
Quoted 1 line · Waiman Long
This patch allows one attempt for the lock waiter to steal the lock
^^^Quoted 30 lines
Quoted 21 lines
Quoted 8 lines
when entering the PV slowpath. This helps to reduce the performance penalty caused by lock waiter preemption while not having much of the downsides of a real unfair lock.
(quoted diff) +0
-1@@ -415,8 +458,12 @@ static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node) for (;; waitcnt++) { for (loop = SPIN_THRESHOLD; loop; loop--) { - if (!READ_ONCE(l->locked))Review static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node) · line 469
Quoted 10 lines
(quoted diff) +6
-1- return; + /* + * Try to acquire the lock when it is free. + */ + if (!READ_ONCE(l->locked)&& + (cmpxchg(&l->locked, 0, _Q_LOCKED_VAL) == 0)) + goto gotlock; cpu_relax(); }This isn't _once_, this is once per 'wakeup'. And note that interrupts unrelated to the kick can equally wake the vCPU up.
voidqueued_spin_lock_slowpath(struct qspinlock *lock, u32 val)Quoted 9 lines
{ : /* * 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. */ if (queued_spin_trylock(lock)) goto release;Quoted 3 lines
This is the only place where I consider lock stealing happens. Again, I should have a comment in
pv_queued_spin_trylock_unfair()to say where it will be called.
Quoted 7 lines
But you're not adding that..
What you did add is a steal in
pv_wait_head(), and its not even once perpv_wait_head, its inside the spin loop (I read it wrong yesterday).So that makes the entire Changelog complete crap. There isn't _one_ attempt, and there is absolutely no fairness left.
Only the queue head vCPU will be in pv_wait_head() spinning to acquire the lock. The other vCPUs in the queue will still be spinning on their MCS nodes. The only competitors for the lock are those vCPUs that have just entered slowpath and execute the queued_spin_trylock() function once before being queued. That is what I mean by each task having only one chance of stealing the lock. Maybe the following code changes can make this point clearer.
Cheers,
Longman
--------------------------------------------------------------------------------------------------------
kernel/locking/qspinlock_paravirt.h +18 -8
@@ -59,7 +59,8 @@ struct pv_node {/* * Allow one unfair trylock when entering the PV slowpath to reduce the * performance impact of lock waiter preemption (either explicitly via -* pv_wait or implicitly via PLE). +* pv_wait or implicitly via PLE). This function will be called once when +* a lock waiter enter the slowpath before being queued. * * A little bit of unfairness here can improve performance without many * of the downsides of a real unfair lock.
@@ -72,8 +73,8 @@ static inline bool pv_queued_spin_trylock_unfair(struct qspinlif (READ_ONCE (l->locked))return 0 ;/* -* Wait a bit here to ensure that an actively spinning vCPU has a fair -* chance of getting the lock. +* Wait a bit here to ensure that an actively spinning queue head vCPU +* has a fair chance of getting the lock. */ cpu_relax ();
@@ -504,14 +505,23 @@ static int pv_wait_head_and_lock(struct qspinlock *lock,*/ WRITE_ONCE (pn->state, vcpu_running); -for (loop =SPIN_THRESHOLD ; loop; loop--) { + loop =SPIN_THRESHOLD ; +while (loop) {/* -* Try to acquire the lock when it is free. +* Spin until the lock is free */ -if (!READ_ONCE (l->locked) && - (cmpxchg (&l->locked,0 , _Q_LOCKED_VAL) ==0 )) +for (; loop &&READ_ONCE (l->locked); loop--) +cpu_relax (); +/* +* Seeing the lock is free, this queue head vCPU is +* the rightful next owner of the lock. However, the +* lock may have just been stolen by another task which +* has entered the slowpath. So we need to use atomic +* operation to make sure that we really get the lock. +* Otherwise, we have to wait again. +*/ +if (cmpxchg (&l->locked,0 , _Q_LOCKED_VAL) ==0 ) goto gotlock; -cpu_relax (); }if (!lp) {/* ONCE */
Peter Zijlstra
maintainerRe: [PATCH v6 5/6] locking/pvqspinlock: Allow 1 lock stealing attempt
Quoted 2 lines · Waiman Long
Only the queue head vCPU will be in
pv_wait_head()spinning to acquire the lock.
But what will guarantee fwd progress for the lock that is the head?
Suppose CPU0 becomes head and enters the /* claim the lock */ loop.
Then CPU1 comes in, steals it in pv_wait_head(). CPU1 releases, CPU1 re-acquires and _again_ steals in pv_wait_head(), etc..
All the while CPU0 doesn't go anywhere.
Re: [PATCH v6 5/6] locking/pvqspinlock: Allow 1 lock stealing attempt
Quoted 4 lines · Peter Zijlstra
Quoted 2 lines · Waiman Long
Only the queue head vCPU will be in
pv_wait_head()spinning to acquire the lock.
Quoted 9 lines
But what will guarantee fwd progress for the lock that is the head?
Suppose CPU0 becomes head and enters the /* claim the lock */ loop.
Then CPU1 comes in, steals it in
pv_wait_head(). CPU1 releases, CPU1 re-acquires and _again_ steals inpv_wait_head(), etc..All the while CPU0 doesn't go anywhere.
That can't happen. For a given lock, there can only be 1 queue head spinning on the lock at any instance in time. If CPU0 was the head, another CPU could not become head until CPU0 got the lock and pass the MCS lock bit to the next one in the queue. As I said in earlier mail, the only place where lock stealing can happen is in the pv_queued_spin_trylock_unfair() function where I purposely inserted a cpu_relax() to allow an actively spinning queue head CPU a better chance of getting the lock. Once a CPU enters the queue. It won't try to acquire the lock until it becomes the head and there is one and only one head.
Cheers,
Longman
Peter Zijlstra
maintainerRe: [PATCH v6 5/6] locking/pvqspinlock: Allow 1 lock stealing attempt
In reply to Waiman Longkernel/locking/qspinlock.c queue: · line 416
Quoted 10 lines · Waiman Long
This patch allows one attempt for the lock waiter to steal the lock when entering the PV slowpath. This helps to reduce the performance penalty caused by lock waiter preemption while not having much of the downsides of a real unfair lock.
kernel/locking/qspinlock.c +0
-0@@ -416,7 +414,8 @@ queue:* does not imply a full barrier. * */
If it really were once, like the Changelog says it is, then you could have simply added:
if (pv_try_steal_lock(...)) goto release;
here, and not wrecked pv_wait_head() like you did. Note that if you do it like this, you also do not need to play games with the hash, because you'll never get into that situation.
Quoted 6 lines
kernel/locking/qspinlock.c +2
-1-pv_wait_head (lock, node); +if (pv_wait_head_and_lock (lock, node, tail)) + goto release;while ((val =smp_load_acquire (&lock->val.counter)) & _Q_LOCKED_PENDING_MASK)cpu_relax ();
Re: [PATCH v6 5/6] locking/pvqspinlock: Allow 1 lock stealing attempt
Quoted 13 lines · Peter Zijlstra
kernel/locking/qspinlock.c queue: · line 416
Quoted 9 lines · Waiman Long
This patch allows one attempt for the lock waiter to steal the lock when entering the PV slowpath. This helps to reduce the performance penalty caused by lock waiter preemption while not having much of the downsides of a real unfair lock.
kernel/locking/qspinlock.c +0
-0@@ -416,7 +414,8 @@ queue:* does not imply a full barrier. * */ If it really were once, like the Changelog says it is, then you could have simply added:
Quoted 2 lines
if (pv_try_steal_lock(...)) goto release;
My previous mail has clarified where the lock stealing happen. Will add the necessary comment to the patch.
Quoted 10 lines
here, and not wrecked
pv_wait_head()like you did. Note that if you do it like this, you also do not need to play games with the hash, because you'll never get into that situation.kernel/locking/qspinlock.c queue: · line 421
Quoted 6 lines
kernel/locking/qspinlock.c +2
-1-pv_wait_head (lock, node); +if (pv_wait_head_and_lock (lock, node, tail)) + goto release;while ((val =smp_load_acquire (&lock->val.counter))& _Q_LOCKED_PENDING_MASK)cpu_relax ();
Because we need to use atomic op to get the lock, we can't use the native logic to do the acquire. I know it is kind of hacky, but I don't have a good alternative here.
Cheers,
Longman
PATCH v6 6/6 locking/pvqspinlock: Queue node adaptive spinning
In reply to Waiman LongIn an overcommitted guest where some vCPUs have to be halted to make forward progress in other areas, it is highly likely that a vCPU later in the spinlock queue will be spinning while the ones earlier in the queue would have been halted. The spinning in the later vCPUs is then just a waste of precious CPU cycles because they are not going to get the lock soon as the earlier ones have to be woken up and take their turn to get the lock.
This patch implements an adaptive spinning mechanism where the vCPU will call pv_wait() if the following conditions are true:
1) the vCPU has not been halted before;
2) the previous vCPU is not running.
Linux kernel builds were run in KVM guest on an 8-socket, 4 cores/socket Westmere-EX system and a 4-socket, 8 cores/socket Haswell-EX system. Both systems are configured to have 32 physical CPUs. The kernel build times before and after the patch were:
Westmere Haswell
Patch 32 vCPUs 48 vCPUs 32 vCPUs 48 vCPUs
----- -------- -------- -------- --------
Before patch 3m02.3s 5m00.2s 1m43.7s 3m03.5s After patch 3m03.0s 4m37.5s 1m43.0s 2m47.2s
For 32 vCPUs, this patch doesn't cause any noticeable change in performance. For 48 vCPUs (over-committed), there is about 8% performance improvement.
--- kernel/locking/qspinlock.c | 5 ++- kernel/locking/qspinlock_paravirt.h | 52 +++++++++++++++++++++++++++++++++- 2 files changed, 53 insertions(+), 4 deletions(-)
kernel/locking/qspinlock.c +3 -2
@@ -247,7 +247,8 @@ static __always_inline void set_locked(struct qspinlock *lock)*/ static __always_inline void __pv_init_node(struct mcs_spinlock *node) { } -static __always_inline void __pv_wait_node(struct mcs_spinlock *node) { } +static __always_inline void __pv_wait_node(struct mcs_spinlock *node, +struct mcs_spinlock *prev) { } static __always_inline bool __pv_wait_head_and_lock(struct qspinlock *lock,struct mcs_spinlock *node,u32 tail)
@@ -398,7 +399,7 @@ queue: prev =decode_tail (old);WRITE_ONCE (prev->next, node); -pv_wait_node (node); +pv_wait_node (node, prev);arch_mcs_spin_lock_contended (&node->locked); }
kernel/locking/qspinlock_paravirt.h +50 -2
102 lines not on this page · raw message
Signature · 1 line
1.7.1
Peter Zijlstra
maintainerRe: [PATCH v6 6/6] locking/pvqspinlock: Queue node adaptive spinning
Quoted 8 lines · Waiman Long
In an overcommitted guest where some vCPUs have to be halted to make forward progress in other areas, it is highly likely that a vCPU later in the spinlock queue will be spinning while the ones earlier in the queue would have been halted. The spinning in the later vCPUs is then just a waste of precious CPU cycles because they are not going to get the lock soon as the earlier ones have to be woken up and take their turn to get the lock.
Quoted 5 lines
This patch implements an adaptive spinning mechanism where the vCPU will call
pv_wait()if the following conditions are true:1) the vCPU has not been halted before;
2) the previous vCPU is not running.
Why 1? For the mutex adaptive stuff we only care about the lock holder running, right?
Re: [PATCH v6 6/6] locking/pvqspinlock: Queue node adaptive spinning
Quoted 9 lines · Peter Zijlstra
Quoted 8 lines · Waiman Long
In an overcommitted guest where some vCPUs have to be halted to make forward progress in other areas, it is highly likely that a vCPU later in the spinlock queue will be spinning while the ones earlier in the queue would have been halted. The spinning in the later vCPUs is then just a waste of precious CPU cycles because they are not going to get the lock soon as the earlier ones have to be woken up and take their turn to get the lock.
Quoted 7 lines
Quoted 5 lines
This patch implements an adaptive spinning mechanism where the vCPU will call
pv_wait()if the following conditions are true:1) the vCPU has not been halted before;
2) the previous vCPU is not running.Why 1? For the mutex adaptive stuff we only care about the lock holder running, right?
The wait-early once logic was there because of the kick-ahead patch as I don't want a recently kicked vCPU near the head of the queue to go back to sleep too early. However, without kick-ahead, a woken up vCPU should now be at the queue head. Indeed, we can remove that check and simplify the logic.
BTW, the queue head vCPU at pv_wait_head_and_lock() doesn't wait early, it will spin the full threshold as there is no way for it to figure out if the lock holder is running or not.
Cheers,
Longman
Peter Zijlstra
maintainerRe: [PATCH v6 6/6] locking/pvqspinlock: Queue node adaptive spinning
Quoted 3 lines · Waiman Long
BTW, the queue head vCPU at
pv_wait_head_and_lock()doesn't wait early, it will spin the full threshold as there is no way for it to figure out if the lock holder is running or not.
We can know its cpu id, right? Surely we should then be able to figure out if its active or not, I'm thinking the KVM/Xen know these things somewhere.
Re: [PATCH v6 6/6] locking/pvqspinlock: Queue node adaptive spinning
Quoted 7 lines · Peter Zijlstra
Quoted 3 lines · Waiman Long
BTW, the queue head vCPU at
pv_wait_head_and_lock()doesn't wait early, it will spin the full threshold as there is no way for it to figure out if the lock holder is running or not.We can know its cpu id, right? Surely we should then be able to figure out if its active or not, I'm thinking the KVM/Xen know these things somewhere.
We can make a guess of the lock holder cpu id by peeking at previous MCS node. However, if the current lock holder got the lock without entering the queue or it got the lock by stealing, we won't have information of what CPU it is.
Cheers,
Longman
Peter Zijlstra
maintainerRe: [PATCH v6 6/6] locking/pvqspinlock: Queue node adaptive spinning
Quoted 5 lines · Waiman Long
Quoted 4 lines · Peter Zijlstra
Quoted 3 lines · Waiman Long
BTW, the queue head vCPU at
pv_wait_head_and_lock()doesn't wait early, it will spin the full threshold as there is no way for it to figure out if the lock holder is running or not.
Quoted 8 lines
Quoted 3 lines
We can know its cpu id, right? Surely we should then be able to figure out if its active or not, I'm thinking the KVM/Xen know these things somewhere.
We can make a guess of the lock holder cpu id by peeking at previous MCS node. However, if the current lock holder got the lock without entering the queue or it got the lock by stealing, we won't have information of what CPU it is.
Ah, yes I see, we do not have storage for the lock holder. Yes you're right.