[PATCH v6 0/6] locking/qspinlock: Enhance pvqspinlock performance

[PATCH v6 0/6] locking/qspinlock: Enhance pvqspinlock performance

[Waiman Long]

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

[Waiman Long]

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.

Signed-off-by: Waiman Long <Waiman.Long@hpe.com>
---
 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(-)

diff --git a/arch/x86/include/asm/qspinlock.h b/arch/x86/include/asm/qspinlock.h
index 9d51fae..053e70d 100644
--- a/arch/x86/include/asm/qspinlock.h
+++ b/arch/x86/include/asm/qspinlock.h
@@ -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;
diff --git a/include/asm-generic/qspinlock.h b/include/asm-generic/qspinlock.h
index 83bfb87..efbd1fd 100644
--- a/include/asm-generic/qspinlock.h
+++ b/include/asm-generic/qspinlock.h
@@ -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
diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c
index 337c881..28a15c7 100644
--- a/kernel/locking/qspinlock.c
+++ b/kernel/locking/qspinlock.c
@@ -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 */
 
-- 
1.7.1

Re: [PATCH v6 1/6] locking/qspinlock: relaxes cmpxchg & xchg ops in native code

[Davidlohr Bueso]

On Fri, 11 Sep 2015, Waiman Long wrote:

>@@ -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

Re: [PATCH v6 1/6] locking/qspinlock: relaxes cmpxchg & xchg ops in native code

[Peter Zijlstra]

On Fri, Sep 11, 2015 at 03:27:44PM -0700, Davidlohr Bueso wrote:
> On Fri, 11 Sep 2015, Waiman Long wrote:
> 
> >@@ -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.

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

[Waiman Long]

On 09/14/2015 08:06 AM, Peter Zijlstra wrote:
> On Fri, Sep 11, 2015 at 03:27:44PM -0700, Davidlohr Bueso wrote:
>> On Fri, 11 Sep 2015, Waiman Long wrote:
>>
>>> @@ -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.
> 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

[Waiman Long]

On 09/11/2015 06:27 PM, Davidlohr Bueso wrote:
> On Fri, 11 Sep 2015, Waiman Long wrote:
>
>> @@ -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

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

[Waiman Long]

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 so is removed.

Signed-off-by: Waiman Long <Waiman.Long@hpe.com>
Reviewed-by: Davidlohr Bueso <dave@stgolabs.net>
---
 kernel/locking/qspinlock_paravirt.h |    6 +-----
 1 files changed, 1 insertions(+), 5 deletions(-)

diff --git a/kernel/locking/qspinlock_paravirt.h b/kernel/locking/qspinlock_paravirt.h
index c8e6e9a..f0450ff 100644
--- a/kernel/locking/qspinlock_paravirt.h
+++ b/kernel/locking/qspinlock_paravirt.h
@@ -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
-- 
1.7.1

[tip:locking/core] locking/pvqspinlock: Kick the PV CPU unconditionally when _Q_SLOW_VAL

[tip-bot for Waiman Long]

Commit-ID:  93edc8bd7750ff3cae088bfca453ea73dc9004a4
Gitweb:     http://git.kernel.org/tip/93edc8bd7750ff3cae088bfca453ea73dc9004a4
Author:     Waiman Long <Waiman.Long@hpe.com>
AuthorDate: Fri, 11 Sep 2015 14:37:34 -0400
Committer:  Ingo Molnar <mingo@kernel.org>
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.

Signed-off-by: Waiman Long <Waiman.Long@hpe.com>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Reviewed-by: Davidlohr Bueso <dave@stgolabs.net>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Douglas Hatch <doug.hatch@hp.com>
Cc: H. Peter Anvin <hpa@zytor.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Scott J Norton <scott.norton@hp.com>
Cc: Thomas Gleixner <tglx@linutronix.de>
Link: http://lkml.kernel.org/r/1441996658-62854-3-git-send-email-Waiman.Long@hpe.com
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 kernel/locking/qspinlock_paravirt.h | 6 +-----
 1 file changed, 1 insertion(+), 5 deletions(-)

diff --git a/kernel/locking/qspinlock_paravirt.h b/kernel/locking/qspinlock_paravirt.h
index c8e6e9a..f0450ff 100644
--- a/kernel/locking/qspinlock_paravirt.h
+++ b/kernel/locking/qspinlock_paravirt.h
@@ -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

[Waiman Long]

The 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%

Signed-off-by: Waiman Long <Waiman.Long@hpe.com>
---
 arch/x86/include/asm/qspinlock_paravirt.h |   59 +++++++++++++++++++++++++++++
 kernel/locking/qspinlock_paravirt.h       |   43 +++++++++++++--------
 2 files changed, 86 insertions(+), 16 deletions(-)

diff --git a/arch/x86/include/asm/qspinlock_paravirt.h b/arch/x86/include/asm/qspinlock_paravirt.h
index b002e71..3001972 100644
--- a/arch/x86/include/asm/qspinlock_paravirt.h
+++ b/arch/x86/include/asm/qspinlock_paravirt.h
@@ -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
diff --git a/kernel/locking/qspinlock_paravirt.h b/kernel/locking/qspinlock_paravirt.h
index f0450ff..4bd323d 100644
--- a/kernel/locking/qspinlock_paravirt.h
+++ b/kernel/locking/qspinlock_paravirt.h
@@ -308,23 +308,14 @@ static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node)
 }
 
 /*
- * PV version of the unlock function to be used in stead of
- * queued_spin_unlock().
+ * PV versions of the unlock fastpath and slowpath functions to be used
+ * instead of queued_spin_unlock().
  */
-__visible void __pv_queued_spin_unlock(struct qspinlock *lock)
+__visible void
+__pv_queued_spin_unlock_slowpath(struct qspinlock *lock, u8 locked)
 {
 	struct __qspinlock *l = (void *)lock;
 	struct pv_node *node;
-	u8 locked;
-
-	/*
-	 * We must not unlock if SLOW, because in that case we must first
-	 * unhash. Otherwise it would be possible to have multiple @lock
-	 * entries, which would be BAD.
-	 */
-	locked = cmpxchg(&l->locked, _Q_LOCKED_VAL, 0);
-	if (likely(locked == _Q_LOCKED_VAL))
-		return;
 
 	if (unlikely(locked != _Q_SLOW_VAL)) {
 		WARN(!debug_locks_silent,
@@ -363,12 +354,32 @@ __visible void __pv_queued_spin_unlock(struct qspinlock *lock)
 	 */
 	pv_kick(node->cpu);
 }
+
 /*
  * Include the architecture specific callee-save thunk of the
  * __pv_queued_spin_unlock(). This thunk is put together with
- * __pv_queued_spin_unlock() near the top of the file to make sure
- * that the callee-save thunk and the real unlock function are close
- * to each other sharing consecutive instruction cachelines.
+ * __pv_queued_spin_unlock() to make the callee-save thunk and the real unlock
+ * function close to each other sharing consecutive instruction cachelines.
+ * Alternatively, architecture specific version of __pv_queued_spin_unlock()
+ * can be defined.
  */
 #include <asm/qspinlock_paravirt.h>
 
+#ifndef __pv_queued_spin_unlock
+__visible void __pv_queued_spin_unlock(struct qspinlock *lock)
+{
+	struct __qspinlock *l = (void *)lock;
+	u8 locked;
+
+	/*
+	 * We must not unlock if SLOW, because in that case we must first
+	 * unhash. Otherwise it would be possible to have multiple @lock
+	 * entries, which would be BAD.
+	 */
+	locked = cmpxchg(&l->locked, _Q_LOCKED_VAL, 0);
+	if (likely(locked == _Q_LOCKED_VAL))
+		return;
+
+	__pv_queued_spin_unlock_slowpath(lock, locked);
+}
+#endif /* __pv_queued_spin_unlock */
-- 
1.7.1

[PATCH v6 4/6] locking/pvqspinlock: Collect slowpath lock statistics

[Waiman Long]

This 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

Signed-off-by: Waiman Long <Waiman.Long@hpe.com>
---
 arch/x86/Kconfig                    |    7 ++
 kernel/locking/qspinlock_paravirt.h |  171 ++++++++++++++++++++++++++++++++++-
 2 files changed, 173 insertions(+), 5 deletions(-)

diff --git a/arch/x86/Kconfig b/arch/x86/Kconfig
index f37010f..d08828f 100644
--- a/arch/x86/Kconfig
+++ b/arch/x86/Kconfig
@@ -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
diff --git a/kernel/locking/qspinlock_paravirt.h b/kernel/locking/qspinlock_paravirt.h
index 4bd323d..2d71768 100644
--- a/kernel/locking/qspinlock_paravirt.h
+++ b/kernel/locking/qspinlock_paravirt.h
@@ -41,6 +41,147 @@ struct pv_node {
 };
 
 /*
+ * PV qspinlock statistics
+ */
+enum pv_qlock_stat {
+	pvstat_wait_head,
+	pvstat_wait_node,
+	pvstat_wait_again,
+	pvstat_kick_wait,
+	pvstat_kick_unlock,
+	pvstat_spurious,
+	pvstat_hops,
+	pvstat_num	/* Total number of statistics counts */
+};
+
+#ifdef CONFIG_QUEUED_LOCK_STAT
+/*
+ * Collect pvqspinlock statiatics
+ */
+#include <linux/debugfs.h>
+#include <linux/sched.h>
+
+static const char * const stat_fsnames[pvstat_num] = {
+	[pvstat_wait_head]   = "wait_head_count",
+	[pvstat_wait_node]   = "wait_node_count",
+	[pvstat_wait_again]  = "wait_again_count",
+	[pvstat_kick_wait]   = "kick_wait_count",
+	[pvstat_kick_unlock] = "kick_unlock_count",
+	[pvstat_spurious]    = "spurious_wakeup",
+	[pvstat_hops]	     = "hash_hops_count",
+};
+
+static atomic_t pvstats[pvstat_num];
+
+/*
+ * pv_kick_latencies = sum of all pv_kick latencies in ns
+ * pv_wake_latencies = sum of all wakeup latencies in ns
+ *
+ * Avg kick latency   = pv_kick_latencies/kick_unlock_count
+ * Avg wake latency   = pv_wake_latencies/kick_wait_count
+ * Avg # of hops/hash = hash_hops_count/kick_unlock_count
+ */
+static atomic64_t pv_kick_latencies, pv_wake_latencies;
+static DEFINE_PER_CPU(u64, pv_kick_time);
+
+/*
+ * Reset all the statistics counts if set
+ */
+static bool reset_cnts __read_mostly;
+
+/*
+ * Initialize debugfs for the PV qspinlock statistics
+ */
+static int __init pv_qspinlock_debugfs(void)
+{
+	struct dentry *d_pvqlock = debugfs_create_dir("pv-qspinlock", NULL);
+	int i;
+
+	if (!d_pvqlock)
+		pr_warn("Could not create 'pv-qspinlock' debugfs directory\n");
+
+	for (i = 0; i < pvstat_num; i++)
+		debugfs_create_u32(stat_fsnames[i], 0444, d_pvqlock,
+				  (u32 *)&pvstats[i]);
+	debugfs_create_u64("kick_latencies", 0444, d_pvqlock,
+			   (u64 *)&pv_kick_latencies);
+	debugfs_create_u64("wake_latencies", 0444, d_pvqlock,
+			   (u64 *)&pv_wake_latencies);
+	debugfs_create_bool("reset_cnts", 0644, d_pvqlock, (u32 *)&reset_cnts);
+	return 0;
+}
+fs_initcall(pv_qspinlock_debugfs);
+
+/*
+ * Reset all the counts
+ */
+static noinline void pvstat_reset(void)
+{
+	int i;
+
+	for (i = 0; i < pvstat_num; i++)
+		atomic_set(&pvstats[i], 0);
+	atomic64_set(&pv_kick_latencies, 0);
+	atomic64_set(&pv_wake_latencies, 0);
+	reset_cnts = 0;
+}
+
+/*
+ * Increment the PV qspinlock statistics counts
+ */
+static inline void pvstat_inc(enum pv_qlock_stat stat)
+{
+	atomic_inc(&pvstats[stat]);
+	if (unlikely(reset_cnts))
+		pvstat_reset();
+}
+
+/*
+ * PV hash hop count
+ */
+static inline void pvstat_hop(int hopcnt)
+{
+	atomic_add(hopcnt, &pvstats[pvstat_hops]);
+}
+
+/*
+ * Replacement function for pv_kick()
+ */
+static inline void __pv_kick(int cpu)
+{
+	u64 start = sched_clock();
+
+	*per_cpu_ptr(&pv_kick_time, cpu) = start;
+	pv_kick(cpu);
+	atomic64_add(sched_clock() - start, &pv_kick_latencies);
+}
+
+/*
+ * Replacement function for pv_wait()
+ */
+static inline void __pv_wait(u8 *ptr, u8 val)
+{
+	u64 *pkick_time = this_cpu_ptr(&pv_kick_time);
+
+	*pkick_time = 0;
+	pv_wait(ptr, val);
+	if (*pkick_time) {
+		atomic64_add(sched_clock() - *pkick_time, &pv_wake_latencies);
+		pvstat_inc(pvstat_kick_wait);
+	}
+}
+
+#define pv_kick(c)	__pv_kick(c)
+#define pv_wait(p, v)	__pv_wait(p, v)
+
+#else /* CONFIG_QUEUED_LOCK_STAT */
+
+static inline void pvstat_inc(enum pv_qlock_stat stat)	{ }
+static inline void pvstat_hop(int hopcnt)		{ }
+
+#endif /* CONFIG_QUEUED_LOCK_STAT */
+
+/*
  * Lock and MCS node addresses hash table for fast lookup
  *
  * Hashing is done on a per-cacheline basis to minimize the need to access
@@ -100,10 +241,13 @@ static struct qspinlock **pv_hash(struct qspinlock *lock, struct pv_node *node)
 {
 	unsigned long offset, hash = hash_ptr(lock, pv_lock_hash_bits);
 	struct pv_hash_entry *he;
+	int hopcnt = 0;
 
 	for_each_hash_entry(he, offset, hash) {
+		hopcnt++;
 		if (!cmpxchg(&he->lock, NULL, lock)) {
 			WRITE_ONCE(he->node, node);
+			pvstat_hop(hopcnt);
 			return &he->lock;
 		}
 	}
@@ -164,9 +308,10 @@ static void pv_init_node(struct mcs_spinlock *node)
 static void pv_wait_node(struct mcs_spinlock *node)
 {
 	struct pv_node *pn = (struct pv_node *)node;
+	int waitcnt = 0;
 	int loop;
 
-	for (;;) {
+	for (;; waitcnt++) {
 		for (loop = SPIN_THRESHOLD; loop; loop--) {
 			if (READ_ONCE(node->locked))
 				return;
@@ -184,15 +329,22 @@ static void pv_wait_node(struct mcs_spinlock *node)
 		 */
 		smp_store_mb(pn->state, vcpu_halted);
 
-		if (!READ_ONCE(node->locked))
+		if (!READ_ONCE(node->locked)) {
+			pvstat_inc(pvstat_wait_node);
+			if (waitcnt)
+				pvstat_inc(pvstat_wait_again);
 			pv_wait(&pn->state, vcpu_halted);
+		}
 
 		/*
-		 * If pv_kick_node() changed us to vcpu_hashed, retain that value
-		 * so that pv_wait_head() knows to not also try to hash this lock.
+		 * If pv_kick_node() changed us to vcpu_hashed, retain that
+		 * value so that pv_wait_head() knows to not also try to hash
+		 * this lock.
 		 */
 		cmpxchg(&pn->state, vcpu_halted, vcpu_running);
 
+		if (READ_ONCE(node->locked))
+			break;
 		/*
 		 * If the locked flag is still not set after wakeup, it is a
 		 * spurious wakeup and the vCPU should wait again. However,
@@ -200,6 +352,7 @@ static void pv_wait_node(struct mcs_spinlock *node)
 		 * So it is better to spin for a while in the hope that the
 		 * MCS lock will be released soon.
 		 */
+		pvstat_inc(pvstat_spurious);
 	}
 
 	/*
@@ -250,6 +403,7 @@ static void pv_wait_head(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;
 
 	/*
@@ -259,7 +413,7 @@ static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node)
 	if (READ_ONCE(pn->state) == vcpu_hashed)
 		lp = (struct qspinlock **)1;
 
-	for (;;) {
+	for (;; waitcnt++) {
 		for (loop = SPIN_THRESHOLD; loop; loop--) {
 			if (!READ_ONCE(l->locked))
 				return;
@@ -290,14 +444,20 @@ static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node)
 				return;
 			}
 		}
+		pvstat_inc(pvstat_wait_head);
+		if (waitcnt)
+			pvstat_inc(pvstat_wait_again);
 		pv_wait(&l->locked, _Q_SLOW_VAL);
 
+		if (!READ_ONCE(l->locked))
+			return;
 		/*
 		 * The unlocker should have freed the lock before kicking the
 		 * CPU. So if the lock is still not free, it is a spurious
 		 * wakeup and so the vCPU should wait again after spinning for
 		 * a while.
 		 */
+		pvstat_inc(pvstat_spurious);
 	}
 
 	/*
@@ -352,6 +512,7 @@ __pv_queued_spin_unlock_slowpath(struct qspinlock *lock, u8 locked)
 	 * vCPU is harmless other than the additional latency in completing
 	 * the unlock.
 	 */
+	pvstat_inc(pvstat_kick_unlock);
 	pv_kick(node->cpu);
 }
 
-- 
1.7.1

Re: [PATCH v6 4/6] locking/pvqspinlock: Collect slowpath lock statistics

[Davidlohr Bueso]

On Fri, 11 Sep 2015, Waiman Long wrote:

>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

[Waiman Long]

On 09/11/2015 07:13 PM, Davidlohr Bueso wrote:
> On Fri, 11 Sep 2015, Waiman Long wrote:
>
>> 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

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

[Davidlohr Bueso]

On Mon, 14 Sep 2015, Waiman Long wrote:

>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

[Waiman Long]

On 09/14/2015 05:41 PM, Davidlohr Bueso wrote:
> On Mon, 14 Sep 2015, Waiman Long wrote:
>
>> 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).

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

[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.

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.

Signed-off-by: Waiman Long <Waiman.Long@hpe.com>
---
 kernel/locking/qspinlock.c          |   19 +++---
 kernel/locking/qspinlock_paravirt.h |  116 ++++++++++++++++++++++++++++-------
 2 files changed, 102 insertions(+), 33 deletions(-)

diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c
index 28a15c7..1be1aab 100644
--- a/kernel/locking/qspinlock.c
+++ b/kernel/locking/qspinlock.c
@@ -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
diff --git a/kernel/locking/qspinlock_paravirt.h b/kernel/locking/qspinlock_paravirt.h
index 2d71768..9fd49a2 100644
--- a/kernel/locking/qspinlock_paravirt.h
+++ b/kernel/locking/qspinlock_paravirt.h
@@ -41,6 +41,30 @@ 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).
+ *
+ * A little bit of unfairness here can improve performance without many
+ * of the downsides of a real unfair lock.
+ */
+#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;
+}
+
+/*
  * PV qspinlock statistics
  */
 enum pv_qlock_stat {
@@ -51,6 +75,7 @@ enum pv_qlock_stat {
 	pvstat_kick_unlock,
 	pvstat_spurious,
 	pvstat_hops,
+	pvstat_utrylock,
 	pvstat_num	/* Total number of statistics counts */
 };
 
@@ -69,6 +94,7 @@ static const char * const stat_fsnames[pvstat_num] = {
 	[pvstat_kick_unlock] = "kick_unlock_count",
 	[pvstat_spurious]    = "spurious_wakeup",
 	[pvstat_hops]	     = "hash_hops_count",
+	[pvstat_utrylock]    = "utrylock_count",
 };
 
 static atomic_t pvstats[pvstat_num];
@@ -145,6 +171,20 @@ static inline void pvstat_hop(int hopcnt)
 }
 
 /*
+ * PV unfair trylock count
+ */
+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)
+
+/*
  * Replacement function for pv_kick()
  */
 static inline void __pv_kick(int cpu)
@@ -338,8 +378,8 @@ static void pv_wait_node(struct mcs_spinlock *node)
 
 		/*
 		 * If pv_kick_node() changed us to vcpu_hashed, retain that
-		 * value so that pv_wait_head() knows to not also try to hash
-		 * this lock.
+		 * value so that pv_wait_head_and_lock() knows to not also
+		 * try to hash this lock.
 		 */
 		cmpxchg(&pn->state, vcpu_halted, vcpu_running);
 
@@ -365,8 +405,9 @@ static void pv_wait_node(struct mcs_spinlock *node)
 /*
  * Called after setting next->locked = 1 when we're the lock owner.
  *
- * Instead of waking the waiters stuck in pv_wait_node() advance their state such
- * that they're waiting in pv_wait_head(), this avoids a wake/sleep cycle.
+ * Instead of waking the waiters stuck in pv_wait_node() advance their state
+ * such that they're waiting in pv_wait_head_and_lock(), this avoids a
+ * wake/sleep cycle.
  */
 static void pv_kick_node(struct qspinlock *lock, struct mcs_spinlock *node)
 {
@@ -398,13 +439,15 @@ static void pv_kick_node(struct qspinlock *lock, struct mcs_spinlock *node)
  * Wait for l->locked to become clear; halt the vcpu after a short spin.
  * __pv_queued_spin_unlock() will wake us.
  */
-static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node)
+static int pv_wait_head_and_lock(struct qspinlock *lock,
+				 struct mcs_spinlock *node, u32 tail)
 {
 	struct pv_node *pn = (struct pv_node *)node;
+	struct mcs_spinlock *next;
 	struct __qspinlock *l = (void *)lock;
 	struct qspinlock **lp = NULL;
 	int waitcnt = 0;
-	int loop;
+	int loop, old;
 
 	/*
 	 * If pv_kick_node() already advanced our state, we don't need to
@@ -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))
-				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();
 		}
 
@@ -434,14 +481,15 @@ static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node)
 			 *
 			 * Matches the smp_rmb() in __pv_queued_spin_unlock().
 			 */
-			if (!cmpxchg(&l->locked, _Q_LOCKED_VAL, _Q_SLOW_VAL)) {
+			if (xchg(&l->locked, _Q_SLOW_VAL) == 0) {
 				/*
-				 * The lock is free and _Q_SLOW_VAL has never
-				 * been set. Therefore we need to unhash before
-				 * getting the lock.
+				 * 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(*lp, NULL);
-				return;
+				goto gotlock;
 			}
 		}
 		pvstat_inc(pvstat_wait_head);
@@ -449,22 +497,46 @@ static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node)
 			pvstat_inc(pvstat_wait_again);
 		pv_wait(&l->locked, _Q_SLOW_VAL);
 
-		if (!READ_ONCE(l->locked))
-			return;
 		/*
 		 * The unlocker should have freed the lock before kicking the
 		 * CPU. So if the lock is still not free, it is a spurious
-		 * wakeup and so the vCPU should wait again after spinning for
-		 * a while.
+		 * wakeup or another vCPU has stolen the lock. The current
+		 * vCPU should spin again.
 		 */
-		pvstat_inc(pvstat_spurious);
+		if (READ_ONCE(l->locked))
+			pvstat_inc(pvstat_spurious);
 	}
 
+gotlock:
 	/*
-	 * Lock is unlocked now; the caller will acquire it without waiting.
-	 * As with pv_wait_node() we rely on the caller to do a load-acquire
-	 * for us.
+	 * We now have the lock. We need to either clear the tail code or
+	 * notify the next one in queue as the new queue head.
 	 */
+	old = atomic_read(&lock->val);
+	while ((old & _Q_TAIL_MASK) == tail) {
+		int val;
+		int new = old & ~_Q_TAIL_MASK;
+
+		/*
+		 * We are the only one in the queue, so clear the tail code
+		 * and return.
+		 */
+		val = atomic_cmpxchg(&lock->val, old, new);
+		if (old == val)
+			goto done;
+		old = val;
+	}
+
+	/*
+	 * contended path; wait for next, release.
+	 */
+	while (!(next = READ_ONCE(node->next)))
+		cpu_relax();
+
+	arch_mcs_spin_unlock_contended(&next->locked);
+	pv_kick_node(lock, next);
+done:
+	return 1;
 }
 
 /*
@@ -489,7 +561,7 @@ __pv_queued_spin_unlock_slowpath(struct qspinlock *lock, u8 locked)
 	 * so we need a barrier to order the read of the node data in
 	 * pv_unhash *after* we've read the lock being _Q_SLOW_VAL.
 	 *
-	 * Matches the cmpxchg() in pv_wait_head() setting _Q_SLOW_VAL.
+	 * Matches the cmpxchg() in pv_wait_head_and_lock() setting _Q_SLOW_VAL.
 	 */
 	smp_rmb();
 
-- 
1.7.1

Re: [PATCH v6 5/6] locking/pvqspinlock: Allow 1 lock stealing attempt

[Peter Zijlstra]

On Fri, Sep 11, 2015 at 02:37:37PM -0400, Waiman Long wrote:
> +#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);
> +
> +	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

[Waiman Long]

On 09/14/2015 09:57 AM, Peter Zijlstra wrote:
> On Fri, Sep 11, 2015 at 02:37:37PM -0400, Waiman Long wrote:
>> +#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);
>> +
>> +	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

Re: [PATCH v6 5/6] locking/pvqspinlock: Allow 1 lock stealing attempt

[Peter Zijlstra]

On Fri, Sep 11, 2015 at 02:37:37PM -0400, Waiman Long wrote:
> 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.

> @@ -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))
> -				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

[Waiman Long]

On 09/14/2015 10:00 AM, Peter Zijlstra wrote:
> On Fri, Sep 11, 2015 at 02:37:37PM -0400, Waiman Long wrote:
>> 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.
>> @@ -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))
>> -				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.

 > 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

[Waiman Long]

On 09/14/2015 03:15 PM, Waiman Long wrote:
> On 09/14/2015 10:00 AM, Peter Zijlstra wrote:
>> On Fri, Sep 11, 2015 at 02:37:37PM -0400, Waiman Long wrote:
>>> 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.
>>> @@ -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))
>>> -                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.

Oh! I misread the diff, the code was OK.

Cheers,
Longman

Re: [PATCH v6 5/6] locking/pvqspinlock: Allow 1 lock stealing attempt

[Peter Zijlstra]

On Mon, Sep 14, 2015 at 03:15:20PM -0400, Waiman Long wrote:
> On 09/14/2015 10:00 AM, Peter Zijlstra wrote:
> >On Fri, Sep 11, 2015 at 02:37:37PM -0400, Waiman Long wrote:
> >>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.

> >>@@ -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))
> >>-				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)
> > {
> >     :
> >         /*
> >         * 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.

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

[Waiman Long]

On 09/15/2015 04:24 AM, Peter Zijlstra wrote:
> On Mon, Sep 14, 2015 at 03:15:20PM -0400, Waiman Long wrote:
>> On 09/14/2015 10:00 AM, Peter Zijlstra wrote:
>>> On Fri, Sep 11, 2015 at 02:37:37PM -0400, Waiman Long wrote:
>>>> 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.
>>>> @@ -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))
>>>> -				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)
>>> {
>>>      :
>>>          /*
>>>          * 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.
> 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.

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

--------------------------------------------------------------------------------------------------------

--- a/kernel/locking/qspinlock_paravirt.h
+++ b/kernel/locking/qspinlock_paravirt.h
@@ -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 qspinl
         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.
+        * 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 */

Re: [PATCH v6 5/6] locking/pvqspinlock: Allow 1 lock stealing attempt

[Peter Zijlstra]

On Tue, Sep 15, 2015 at 11:29:14AM -0400, Waiman Long wrote:

> 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

[Waiman Long]

On 09/16/2015 11:01 AM, Peter Zijlstra wrote:
> On Tue, Sep 15, 2015 at 11:29:14AM -0400, Waiman Long wrote:
>
>> 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.
>

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

Re: [PATCH v6 5/6] locking/pvqspinlock: Allow 1 lock stealing attempt

[Peter Zijlstra]

On Fri, Sep 11, 2015 at 02:37:37PM -0400, Waiman Long wrote:
> 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.


> @@ -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.

> -	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

[Waiman Long]

On 09/14/2015 10:04 AM, Peter Zijlstra wrote:
> On Fri, Sep 11, 2015 at 02:37:37PM -0400, Waiman Long wrote:
>> 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.
>
>> @@ -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;

My previous mail has clarified where the lock stealing happen. Will add 
the necessary comment to the patch.

> 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.
>
>> -	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

[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.

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.

Signed-off-by: Waiman Long <Waiman.Long@hpe.com>
---
 kernel/locking/qspinlock.c          |    5 ++-
 kernel/locking/qspinlock_paravirt.h |   52 +++++++++++++++++++++++++++++++++-
 2 files changed, 53 insertions(+), 4 deletions(-)

diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c
index 1be1aab..319e823 100644
--- a/kernel/locking/qspinlock.c
+++ b/kernel/locking/qspinlock.c
@@ -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);
 	}
 
diff --git a/kernel/locking/qspinlock_paravirt.h b/kernel/locking/qspinlock_paravirt.h
index 9fd49a2..57ed38b 100644
--- a/kernel/locking/qspinlock_paravirt.h
+++ b/kernel/locking/qspinlock_paravirt.h
@@ -23,6 +23,22 @@
 #define _Q_SLOW_VAL	(3U << _Q_LOCKED_OFFSET)
 
 /*
+ * Queue Node Adaptive Spinning
+ *
+ * A queue node vCPU will stop spinning if the following conditions are true:
+ * 1) vCPU in the previous node is not running
+ * 2) current vCPU has not been halted before
+ *
+ * The one lock stealing attempt allowed at slowpath entry mitigates the
+ * slight slowdown for non-overcommitted guest with this aggressive wait-early
+ * mechanism.
+ *
+ * The status of the previous node will be checked at fixed interval
+ * controlled by PV_PREV_CHECK_MASK.
+ */
+#define PV_PREV_CHECK_MASK	0xff
+
+/*
  * Queue node uses: vcpu_running & vcpu_halted.
  * Queue head uses: vcpu_running & vcpu_hashed.
  */
@@ -71,6 +87,7 @@ enum pv_qlock_stat {
 	pvstat_wait_head,
 	pvstat_wait_node,
 	pvstat_wait_again,
+	pvstat_wait_early,
 	pvstat_kick_wait,
 	pvstat_kick_unlock,
 	pvstat_spurious,
@@ -90,6 +107,7 @@ static const char * const stat_fsnames[pvstat_num] = {
 	[pvstat_wait_head]   = "wait_head_count",
 	[pvstat_wait_node]   = "wait_node_count",
 	[pvstat_wait_again]  = "wait_again_count",
+	[pvstat_wait_early]  = "wait_early_count",
 	[pvstat_kick_wait]   = "kick_wait_count",
 	[pvstat_kick_unlock] = "kick_unlock_count",
 	[pvstat_spurious]    = "spurious_wakeup",
@@ -328,6 +346,20 @@ static struct pv_node *pv_unhash(struct qspinlock *lock)
 }
 
 /*
+ * Return true if when it is time to check the previous node which is not
+ * in a running state.
+ */
+static inline bool
+pv_wait_early(struct pv_node *node, struct pv_node *prev, int loop)
+{
+
+	if ((loop & PV_PREV_CHECK_MASK) != 0)
+		return false;
+
+	return READ_ONCE(prev->state) != vcpu_running;
+}
+
+/*
  * Initialize the PV part of the mcs_spinlock node.
  */
 static void pv_init_node(struct mcs_spinlock *node)
@@ -345,16 +377,25 @@ static void pv_init_node(struct mcs_spinlock *node)
  * pv_kick_node() is used to set _Q_SLOW_VAL and fill in hash table on its
  * behalf.
  */
-static void pv_wait_node(struct mcs_spinlock *node)
+static void pv_wait_node(struct mcs_spinlock *node, struct mcs_spinlock *prev)
 {
 	struct pv_node *pn = (struct pv_node *)node;
+	struct pv_node *pp = (struct pv_node *)prev;
 	int waitcnt = 0;
 	int loop;
+	bool wait_early;
 
 	for (;; waitcnt++) {
-		for (loop = SPIN_THRESHOLD; loop; loop--) {
+		for (wait_early = false, loop = SPIN_THRESHOLD; loop; loop--) {
 			if (READ_ONCE(node->locked))
 				return;
+			/*
+			 * Wait early only if it has not been halted before.
+			 */
+			if (!waitcnt && pv_wait_early(pn, pp, loop)) {
+				wait_early = true;
+				break;
+			}
 			cpu_relax();
 		}
 
@@ -457,6 +498,12 @@ static int pv_wait_head_and_lock(struct qspinlock *lock,
 		lp = (struct qspinlock **)1;
 
 	for (;; waitcnt++) {
+		/*
+		 * Set correct vCPU state to be used by queue node wait-early
+		 * mechanism.
+		 */
+		WRITE_ONCE(pn->state, vcpu_running);
+
 		for (loop = SPIN_THRESHOLD; loop; loop--) {
 			/*
 			 * Try to acquire the lock when it is free.
@@ -492,6 +539,7 @@ static int pv_wait_head_and_lock(struct qspinlock *lock,
 				goto gotlock;
 			}
 		}
+		WRITE_ONCE(pn->state, vcpu_halted);
 		pvstat_inc(pvstat_wait_head);
 		if (waitcnt)
 			pvstat_inc(pvstat_wait_again);
-- 
1.7.1

Re: [PATCH v6 6/6] locking/pvqspinlock: Queue node adaptive spinning

[Peter Zijlstra]

On Fri, Sep 11, 2015 at 02:37:38PM -0400, Waiman Long wrote:
> 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.
> 
> 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

[Waiman Long]

On 09/14/2015 10:10 AM, Peter Zijlstra wrote:
> On Fri, Sep 11, 2015 at 02:37:38PM -0400, Waiman Long wrote:
>> 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.
>>
>> 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

Re: [PATCH v6 6/6] locking/pvqspinlock: Queue node adaptive spinning

[Peter Zijlstra]

On Mon, Sep 14, 2015 at 03:37:32PM -0400, Waiman Long wrote:
> 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

[Waiman Long]

On 09/15/2015 04:38 AM, Peter Zijlstra wrote:
> On Mon, Sep 14, 2015 at 03:37:32PM -0400, Waiman Long wrote:
>> 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

Re: [PATCH v6 6/6] locking/pvqspinlock: Queue node adaptive spinning

[Peter Zijlstra]

On Tue, Sep 15, 2015 at 11:32:14AM -0400, Waiman Long wrote:
> On 09/15/2015 04:38 AM, Peter Zijlstra wrote:
> >On Mon, Sep 14, 2015 at 03:37:32PM -0400, Waiman Long wrote:
> >>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.

Ah, yes I see, we do not have storage for the lock holder. Yes you're
right.