Skip to contentSkip to conversation

locking/qspinlock: Enhance pvqspinlock performance

PATCH Superseded Waiman Long 6 participants 25 messages Jul 15, 2015 – Aug 3, 2015

Subsystems (5)

v2 of 5 Superseded Latest is v5 →

lore
Share & tools
lore
#0 lore raw

v2 cover locking/qspinlock: Enhance pvqspinlock 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 normal and over-commmitted VM guests. The kick-ahead and adaptive spinning patches are inspired by the "Do Virtual Machines Really Scale?" blog from Sanidhya Kashyap.

Patch 1 simplifies the unlock code by doing unconditional vCPU kick when _Q_SLOW_VAL is set as the chance of spurious wakeup showing up in the statistical data that I collected was very low (1 or 2 occasionally).

Patch 2 adds pending bit support to pvqspinlock improving performance at light load.

Patch 3 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. This will slow the system a little bit.

Patch 4 enables multiple vCPU kicks at unlock time, outside of the critical section. Coupled with patch 5 which defers kicking to unlock time, this will improve system performance in overcommitted guests and sometime even in normal guests.

Patch 6 enables adaptive spinning in the queue nodes. This patch can lead to pretty big performance increase in over-committed guest at the expense of a slight performance hit in normal guests.

Waiman Long (6):
locking/pvqspinlock: Unconditional PV kick with _Q_SLOW_VAL locking/pvqspinlock: Add pending bit support locking/pvqspinlock: Collect slowpath lock statistics locking/pvqspinlock: Allow vCPUs kick-ahead locking/pvqspinlock: Opportunistically defer kicking to unlock time locking/pvqspinlock: Queue node adaptive spinning

 arch/x86/Kconfig                    |    7 +
 kernel/locking/qspinlock.c          |   38 +++-
 kernel/locking/qspinlock_paravirt.h |  452 +++++++++++++++++++++++++++++++++--
 3 files changed, 473 insertions(+), 24 deletions(-)
#1 lore raw

PATCH v2 1/6 locking/pvqspinlock: Unconditional PV kick with _Q_SLOW_VAL

The smp_store_release() is not a full barrier. In order to avoid missed wakeup, we may need to add memory barrier around locked and cpu state variables adding to complexity. As the chance of spurious wakeup is very low, it is easier and safer to just do an unconditional kick at unlock time.

---
 kernel/locking/qspinlock_paravirt.h |    4 +---
 1 files changed, 1 insertions(+), 3 deletions(-)
kernel/locking/qspinlock_paravirt.h +1 -3
index 04ab181..f2f4807 100644
@@ -239,7 +239,6 @@ static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node)
 			cpu_relax();
 		}
 
-		WRITE_ONCE(pn->state, vcpu_halted);
 		if (!lp) { /* ONCE */
 			lp = pv_hash(lock, pn);
 			/*
@@ -311,8 +310,7 @@ __visible void __pv_queued_spin_unlock(struct qspinlock *lock)
 	 * At this point the memory pointed at by lock can be freed/reused,
 	 * however we can still use the pv_node to kick the CPU.
 	 */
-	if (READ_ONCE(node->state) == vcpu_halted)
-		pv_kick(node->cpu);
+	pv_kick(node->cpu);
 }
 /*
  * Include the architecture specific callee-save thunk of the
Signature · 1 line
1.7.1
maintainer
#2 lore raw

Re: [PATCH v2 1/6] locking/pvqspinlock: Unconditional PV kick with _Q_SLOW_VAL

Quoted 5 lines · Waiman Long

The smp_store_release() is not a full barrier. In order to avoid missed wakeup, we may need to add memory barrier around locked and cpu state variables adding to complexity. As the chance of spurious wakeup is very low, it is easier and safer to just do an unconditional kick at unlock time.

I have the below patch. We need that rmb in there anyhow for the hash to work.

---
Subject: locking/pvqspinlock: Order pv_unhash after cmpxchg on unlock slowpath
From: Will Deacon <[email protected]>
Date: Mon, 13 Jul 2015 16:58:30 +0100

When we unlock in __pv_queued_spin_unlock, a failed cmpxchg on the lock value indicates that we need to take the slow-path and unhash the corresponding node blocked on the lock.

Since a failed cmpxchg does not provide any memory-ordering guarantees, it is possible that the node data could be read before the cmpxchg on weakly-ordered architectures and therefore return a stale value, leading to hash corruption and/or a BUG().

This patch adds an smb_rmb() following the failed cmpxchg operation, so that the unhashing is ordered after the lock has been checked.

---
 kernel/locking/qspinlock_paravirt.h |   23 ++++++++++++++++++-----
 1 file changed, 18 insertions(+), 5 deletions(-)
kernel/locking/qspinlock_paravirt.h +18 -5
@@ -244,13 +244,17 @@ static void pv_wait_head(struct qspinloc
 		if (!lp) { /* ONCE */
 			lp = pv_hash(lock, pn);
 			/*
-			 * lp must be set before setting _Q_SLOW_VAL
+			 * We must hash before setting _Q_SLOW_VAL, such that
+			 * when we observe _Q_SLOW_VAL in __pv_queued_spin_unlock()
+			 * we'll be sure to be able to observe our hash entry.
 			 *
-			 * [S] lp = lock                [RmW] l = l->locked = 0
-			 *     MB                             MB
-			 * [S] l->locked = _Q_SLOW_VAL  [L]   lp
+			 *   [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 cmpxchg() in __pv_queued_spin_unlock().
+			 * Matches the smp_rmb() in __pv_queued_spin_unlock().
 			 */
 			if (!cmpxchg(&l->locked, _Q_LOCKED_VAL, _Q_SLOW_VAL)) {
 				/*
@@ -306,6 +310,15 @@ __visible void __pv_queued_spin_unlock(s
 	}
 
 	/*
+	 * A failed cmpxchg doesn't provide any memory-ordering guarantees,
+	 * 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.
+	 */
+	smp_rmb();
+
+	/*
 	 * Since the above failed to release, this must be the SLOW path.
 	 * Therefore start by looking up the blocked node and unhashing it.
 	 */
#3 lore raw

Re: [PATCH v2 1/6] locking/pvqspinlock: Unconditional PV kick with _Q_SLOW_VAL

Quoted 64 lines · Peter Zijlstra
Quoted 5 lines · Waiman Long

The smp_store_release() is not a full barrier. In order to avoid missed wakeup, we may need to add memory barrier around locked and cpu state variables adding to complexity. As the chance of spurious wakeup is very low, it is easier and safer to just do an unconditional kick at unlock time.

I have the below patch. We need that rmb in there anyhow for the hash to work.

---
Subject: locking/pvqspinlock: Order pv_unhash after cmpxchg on unlock slowpath
From: Will Deacon<[email protected]>
Date: Mon, 13 Jul 2015 16:58:30 +0100

When we unlock in __pv_queued_spin_unlock, a failed cmpxchg on the lock value indicates that we need to take the slow-path and unhash the corresponding node blocked on the lock.

Since a failed cmpxchg does not provide any memory-ordering guarantees, it is possible that the node data could be read before the cmpxchg on weakly-ordered architectures and therefore return a stale value, leading to hash corruption and/or a BUG().

This patch adds an smb_rmb() following the failed cmpxchg operation, so that the unhashing is ordered after the lock has been checked.

---
  kernel/locking/qspinlock_paravirt.h |   23 ++++++++++++++++++-----
  1 file changed, 18 insertions(+), 5 deletions(-)
kernel/locking/qspinlock_paravirt.h +9 -5
@@ -244,13 +244,17 @@ static void pv_wait_head(struct qspinloc
  		if (!lp) { /* ONCE */
  			lp = pv_hash(lock, pn);
  			/*
-			 * lp must be set before setting _Q_SLOW_VAL
+			 * We must hash before setting _Q_SLOW_VAL, such that
+			 * when we observe _Q_SLOW_VAL in __pv_queued_spin_unlock()
+			 * we'll be sure to be able to observe our hash entry.
  			 *
-			 * [S] lp = lock                [RmW] l = l->locked = 0
-			 *     MB                             MB
-			 * [S] l->locked = _Q_SLOW_VAL  [L]   lp
+			 *   [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 cmpxchg() in __pv_queued_spin_unlock().
+			 * Matches the smp_rmb() in __pv_queued_spin_unlock().
  			 */
  			if (!cmpxchg(&l->locked, _Q_LOCKED_VAL, _Q_SLOW_VAL)) {
  				/*

kernel/locking/qspinlock_paravirt.h __visible void __pv_queued_spin_unlock(s · line 319

Quoted 10 lines
kernel/locking/qspinlock_paravirt.h +7 -0
@@ -306,6 +310,15 @@ __visible void __pv_queued_spin_unlock(s
  	}
 
  	/*
+	 * A failed cmpxchg doesn't provide any memory-ordering guarantees,
+	 * 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.
+	 */
+	smp_rmb();

According to memory_barriers.txt, cmpxchg() is a full memory barrier. It didn't say a failed cmpxchg will lose its memory guarantee. So is the documentation right? Or is that true for some architectures? I think it is not true for x86.

Cheers,
Longman

maintainer
#4 lore raw

Re: [PATCH v2 1/6] locking/pvqspinlock: Unconditional PV kick with _Q_SLOW_VAL

Quoted 13 lines · Waiman Long

kernel/locking/qspinlock_paravirt.h __visible void __pv_queued_spin_unlock(s · line 319

Quoted 8 lines · Peter Zijlstra
kernel/locking/qspinlock_paravirt.h +7 -0
 	/*
+	 * A failed cmpxchg doesn't provide any memory-ordering guarantees,
+	 * 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.
+	 */
+	smp_rmb();

According to memory_barriers.txt, cmpxchg() is a full memory barrier. It didn't say a failed cmpxchg will lose its memory guarantee. So is the documentation right?

The documentation is not entirely clear on this; but there are hints that this is so.

Quoted 2 lines

Or is that true for some architectures? I think it is not true for x86.

On x86 LOCK CMPXCHG is always a sync point, but yes there are archs for which a failed cmpxchg does _NOT_ provide any barrier semantics.

The reason I started looking was because Will made Argh64 one of those.

author Acked-by
#5 lore raw

Re: [PATCH v2 1/6] locking/pvqspinlock: Unconditional PV kick with _Q_SLOW_VAL

Quoted 16 lines · Peter Zijlstra
Quoted 12 lines · Waiman Long

kernel/locking/qspinlock_paravirt.h __visible void __pv_queued_spin_unlock(s · line 319

Quoted 8 lines · Peter Zijlstra

/*

kernel/locking/qspinlock_paravirt.h +7 -0
+	 * A failed cmpxchg doesn't provide any memory-ordering guarantees,
+	 * 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.
+	 */
+	smp_rmb();

According to memory_barriers.txt, cmpxchg() is a full memory barrier. It didn't say a failed cmpxchg will lose its memory guarantee. So is the documentation right?

The documentation is not entirely clear on this; but there are hints that this is so.

Quoted 6 lines
Quoted 2 lines

Or is that true for some architectures? I think it is not true for x86.

On x86 LOCK CMPXCHG is always a sync point, but yes there are archs for which a failed cmpxchg does _NOT_ provide any barrier semantics.

The reason I started looking was because Will made Argh64 one of those.

That is what I suspected. In that case, I am fine with the patch as smp_rmb() is an nop in x86 anyway.

BTW, I think we also need to update the documentation to make it clear that a failed cmpxchg() or atomic_cmpxchg() may not be a full memory barrier as most people may not be aware of that.

Cheers,
Longman

#6 lore raw

Re: [PATCH v2 1/6] locking/pvqspinlock: Unconditional PV kick with _Q_SLOW_VAL

Quoted 23 lines · Waiman Long
Quoted 22 lines · Peter Zijlstra
Quoted 10 lines · Waiman Long

kernel/locking/qspinlock_paravirt.h __visible void __pv_queued_spin_unlock(s · line 319

Quoted 9 lines · Peter Zijlstra
      /*

+ * A failed cmpxchg doesn't provide any memory-ordering
guarantees,

kernel/locking/qspinlock_paravirt.h +6 -0
+     * 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.
+     */
+    smp_rmb();
Quoted 3 lines

According to memory_barriers.txt, cmpxchg() is a full memory barrier. It didn't say a failed cmpxchg will lose its memory guarantee. So is the documentation right?

The documentation is not entirely clear on this; but there are hints that this is so.

Quoted 2 lines

Or is that true for some architectures? I think it is not true for x86.

On x86 LOCK CMPXCHG is always a sync point, but yes there are archs for which a failed cmpxchg does _NOT_ provide any barrier semantics.

Quoted 8 lines
Quoted 1 line

The reason I started looking was because Will made Argh64 one of those.

That is what I suspected. In that case, I am fine with the patch as smp_rmb() is an nop in x86 anyway.

BTW, I think we also need to update the documentation to make it clear that a failed cmpxchg() or atomic_cmpxchg() may not be a full memory barrier as most people may not be aware of that.

I suspect that there may be other places in the kernel that have similar problem. An alternative will be to strengthen cmpxchg() in architectures like arm64 to act as full memory barrier no matter the result and defined relaxed version with no such guarantee.

Cheers,
Longman

#7 lore raw

Re: [PATCH v2 1/6] locking/pvqspinlock: Unconditional PV kick with _Q_SLOW_VAL

Quoted 30 lines · Waiman Long
Quoted 29 lines · Waiman Long
Quoted 18 lines · Peter Zijlstra
Quoted 10 lines · Waiman Long

Review

Quoted 9 lines · Peter Zijlstra
      /*

+ * A failed cmpxchg doesn't provide any memory-ordering
guarantees,

(quoted diff) +6 -0
+     * 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.
+     */
+    smp_rmb();
Quoted 4 lines

According to memory_barriers.txt, cmpxchg() is a full memory barrier. It
didn't say a failed cmpxchg will lose its memory guarantee. So is the documentation right?

The documentation is not entirely clear on this; but there are hints that this is so.

Quoted 6 lines
Quoted 2 lines

Or is that true for some architectures? I think it is not true for x86.

On x86 LOCK CMPXCHG is always a sync point, but yes there are archs for which a failed cmpxchg does _NOT_ provide any barrier semantics.

The reason I started looking was because Will made Argh64 one of those.

That is what I suspected. In that case, I am fine with the patch as smp_rmb() is an nop in x86 anyway.

Quoted 6 lines
Quoted 6 lines

BTW, I think we also need to update the documentation to make it clear that a failed cmpxchg() or atomic_cmpxchg() may not be a full memory barrier as most people may not be aware of that.

I already have a small patch for the Documentation (see below -- Peter, you can pick this up too if you like).

Quoted 4 lines

I suspect that there may be other places in the kernel that have similar problem. An alternative will be to strengthen cmpxchg() in architectures like arm64 to act as full memory barrier no matter the result and defined relaxed version with no such guarantee.

Could do, but I don't think the ordering requirements are needed in the vast majority of cases (as in, this case was the only one we could find) and it gets really muddy when you want to define the semantics of something like a failed cmpxchg_release.

Will

--->8

commit b2fdae71bdb621f62450076af4126cd8bca22918

Author: Will Deacon <[email protected]>
Date:   Mon Jul 13 12:27:30 2015 +0100

documentation: Clarify failed cmpxchg memory ordering semantics

A failed cmpxchg does not provide any memory ordering guarantees, a property that is used to optimise the cmpxchg implementations on Alpha, PowerPC and arm64.

This patch updates atomic_ops.txt and memory-barriers.txt to reflect this.

Cc Peter Zijlstra <[email protected]>
Documentation/atomic_ops.txt +3 -1
index dab6da3382d9..b19fc34efdb1 100644
@@ -266,7 +266,9 @@ with the given old and new values. Like all atomic_xxx operations,
 atomic_cmpxchg will only satisfy its atomicity semantics as long as all
 other accesses of *v are performed through atomic_xxx operations.
 
-atomic_cmpxchg must provide explicit memory barriers around the operation.
+atomic_cmpxchg must provide explicit memory barriers around the operation,
+although if the comparison fails then no memory ordering guarantees are
+required.
 
 The semantics for atomic_cmpxchg are the same as those defined for 'cas'
 below.
Documentation/memory-barriers.txt +3 -3
index 13feb697271f..18fc860df1be 100644
@@ -2383,9 +2383,7 @@ about the state (old or new) implies an SMP-conditional general memory barrier
 explicit lock operations, described later).  These include:
 
 	xchg();
-	cmpxchg();
 	atomic_xchg();			atomic_long_xchg();
-	atomic_cmpxchg();		atomic_long_cmpxchg();
 	atomic_inc_return();		atomic_long_inc_return();
 	atomic_dec_return();		atomic_long_dec_return();
 	atomic_add_return();		atomic_long_add_return();
@@ -2398,7 +2396,9 @@ explicit lock operations, described later).  These include:
 	test_and_clear_bit();
 	test_and_change_bit();
 
-	/* when succeeds (returns 1) */
+	/* when succeeds */
+	cmpxchg();
+	atomic_cmpxchg();		atomic_long_cmpxchg();
 	atomic_add_unless();		atomic_long_add_unless();
 
 These are used for such things as implementing ACQUIRE-class and RELEASE-class
#8 lore raw

[tip:locking/core] locking/Documentation: Clarify failed cmpxchg( ) memory ordering semantics

locking/Documentation: Clarify failed cmpxchg() memory ordering semantics
Commit-ID:  ed2de9f74ecbbf3063d29b2334e7b455d7f35189
Gitweb:     http://git.kernel.org/tip/ed2de9f74ecbbf3063d29b2334e7b455d7f35189
Author:     Will Deacon <[email protected]>
AuthorDate: Thu, 16 Jul 2015 16:10:06 +0100
Committer:  Ingo Molnar <[email protected]>
CommitDate: Mon, 3 Aug 2015 10:57:09 +0200

locking/Documentation: Clarify failed cmpxchg() memory ordering semantics

A failed cmpxchg does not provide any memory ordering guarantees, a property that is used to optimise the cmpxchg implementations on Alpha, PowerPC and arm64.

This patch updates atomic_ops.txt and memory-barriers.txt to reflect this.

Cc Andrew Morton <[email protected]>
Cc Davidlohr Bueso <[email protected]>
Cc Douglas Hatch <[email protected]>
Cc H. Peter Anvin <[email protected]>
Cc Jonathan Corbet <[email protected]>
Cc Linus Torvalds <[email protected]>
Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Scott J Norton <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Waiman Long <[email protected]>
---
 Documentation/atomic_ops.txt      | 4 +++-
 Documentation/memory-barriers.txt | 6 +++---
 2 files changed, 6 insertions(+), 4 deletions(-)
Documentation/atomic_ops.txt +3 -1
index dab6da3..b19fc34 100644
@@ -266,7 +266,9 @@ with the given old and new values. Like all atomic_xxx operations,
 atomic_cmpxchg will only satisfy its atomicity semantics as long as all
 other accesses of *v are performed through atomic_xxx operations.
 
-atomic_cmpxchg must provide explicit memory barriers around the operation.
+atomic_cmpxchg must provide explicit memory barriers around the operation,
+although if the comparison fails then no memory ordering guarantees are
+required.
 
 The semantics for atomic_cmpxchg are the same as those defined for 'cas'
 below.
Documentation/memory-barriers.txt +3 -3
index 13feb69..18fc860 100644
@@ -2383,9 +2383,7 @@ about the state (old or new) implies an SMP-conditional general memory barrier
 explicit lock operations, described later).  These include:
 
 	xchg();
-	cmpxchg();
 	atomic_xchg();			atomic_long_xchg();
-	atomic_cmpxchg();		atomic_long_cmpxchg();
 	atomic_inc_return();		atomic_long_inc_return();
 	atomic_dec_return();		atomic_long_dec_return();
 	atomic_add_return();		atomic_long_add_return();
@@ -2398,7 +2396,9 @@ explicit lock operations, described later).  These include:
 	test_and_clear_bit();
 	test_and_change_bit();
 
-	/* when succeeds (returns 1) */
+	/* when succeeds */
+	cmpxchg();
+	atomic_cmpxchg();		atomic_long_cmpxchg();
 	atomic_add_unless();		atomic_long_add_unless();
 
 These are used for such things as implementing ACQUIRE-class and RELEASE-class
#9 lore raw

Re: [tip:locking/core] locking/Documentation: Clarify failed cmpxchg( ) memory ordering semantics

Quoted 41 lines · tip-bot for Will Deacon
Commit-ID:  ed2de9f74ecbbf3063d29b2334e7b455d7f35189
Gitweb:     http://git.kernel.org/tip/ed2de9f74ecbbf3063d29b2334e7b455d7f35189
Author:     Will Deacon <[email protected]>
AuthorDate: Thu, 16 Jul 2015 16:10:06 +0100
Committer:  Ingo Molnar <[email protected]>
CommitDate: Mon, 3 Aug 2015 10:57:09 +0200

locking/Documentation: Clarify failed cmpxchg() memory ordering semantics

A failed cmpxchg does not provide any memory ordering guarantees, a property that is used to optimise the cmpxchg implementations on Alpha, PowerPC and arm64.

This patch updates atomic_ops.txt and memory-barriers.txt to reflect this.

Cc Andrew Morton <[email protected]>
Cc Davidlohr Bueso <[email protected]>
Cc Douglas Hatch <[email protected]>
Cc H. Peter Anvin <[email protected]>
Cc Jonathan Corbet <[email protected]>
Cc Linus Torvalds <[email protected]>
Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Scott J Norton <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Waiman Long <[email protected]>
---
 Documentation/atomic_ops.txt      | 4 +++-
 Documentation/memory-barriers.txt | 6 +++---
 2 files changed, 6 insertions(+), 4 deletions(-)
Documentation/atomic_ops.txt +0 -0
index dab6da3..b19fc34 100644

Documentation/atomic_ops.txt with the given old and new values. Like all atomic_xxx operations, · line 271

Quoted 7 lines
Documentation/atomic_ops.txt +3 -1
@@ -266,7 +266,9 @@ with the given old and new values. Like all atomic_xxx operations,
 atomic_cmpxchg will only satisfy its atomicity semantics as long as all
 other accesses of *v are performed through atomic_xxx operations.
 
-atomic_cmpxchg must provide explicit memory barriers around the operation.
+atomic_cmpxchg must provide explicit memory barriers around the operation,
+although if the comparison fails then no memory ordering guarantees are
+required.

Thanks, I also stumbled upon this with the wake-q stuff.

#10 lore raw

PATCH v2 2/6 locking/pvqspinlock: Add pending bit support

In reply to Waiman Long

Like the native qspinlock, using the pending bit when it is lightly loaded to acquire the lock is faster than going through the PV queuing process which is even slower than the native queuing process. It also avoids loading two additional cachelines (the MCS and PV nodes).

This patch adds the pending bit support for PV qspinlock. The pending bit code has a smaller spin threshold (1<<10). It will default back to the queuing method if it cannot acquired the lock within a certain time limit.

On a VM with 32 vCPUs on a 32-core Westmere-EX box, the kernel build times on 4.2-rc1 based kernels were:

Kernel Build Time Sys Time
------ ---------- --------
w/o patch 3m28.5s 28m17.5s
with patch 3m19.3s 23m55.7s

Using a locking microbenchmark on the same system, the locking rates in (kops/s) were:

Threads Rate w/o patch Rate with patch
------- -------------- ---------------
2 (same socket) 6,515,265 7,077,476
2 (diff sockets) 2,967,145 4,353,851

---
 kernel/locking/qspinlock.c          |   27 ++++++++++++++-
 kernel/locking/qspinlock_paravirt.h |   66 +++++++++++++++++++++++++++++++++++
 2 files changed, 92 insertions(+), 1 deletions(-)
kernel/locking/qspinlock.c +26 -1
index 38c4920..6518ee9 100644
@@ -162,6 +162,17 @@ static __always_inline void clear_pending_set_locked(struct qspinlock *lock)
 	WRITE_ONCE(l->locked_pending, _Q_LOCKED_VAL);
 }
 
+/**
+ * clear_pending - clear the pending bit.
+ * @lock: Pointer to queued spinlock structure
+ */
+static __always_inline void clear_pending(struct qspinlock *lock)
+{
+	struct __qspinlock *l = (void *)lock;
+
+	WRITE_ONCE(l->pending, 0);
+}
+
 /*
  * xchg_tail - Put in the new queue tail code word & retrieve previous one
  * @lock : Pointer to queued spinlock structure
@@ -193,6 +204,15 @@ static __always_inline void clear_pending_set_locked(struct qspinlock *lock)
 }
 
 /**
+ * clear_pending - clear the pending bit.
+ * @lock: Pointer to queued spinlock structure
+ */
+static __always_inline void clear_pending(struct qspinlock *lock)
+{
+	atomic_add(-_Q_PENDING_VAL, &lock->val);
+}
+
+/**
  * xchg_tail - Put in the new queue tail code word & retrieve previous one
  * @lock : Pointer to queued spinlock structure
  * @tail : The new queue tail code word
@@ -245,6 +265,7 @@ static __always_inline void __pv_wait_head(struct qspinlock *lock,
 					   struct mcs_spinlock *node) { }
 
 #define pv_enabled()		false
+#define pv_pending_lock(l, v)	false
 
 #define pv_init_node		__pv_init_node
 #define pv_wait_node		__pv_wait_node
@@ -286,8 +307,11 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)
 
 	BUILD_BUG_ON(CONFIG_NR_CPUS >= (1U << _Q_TAIL_CPU_BITS));
 
-	if (pv_enabled())
+	if (pv_enabled()) {
+		if (pv_pending_lock(lock, val))
+			return;	/* Got the lock via pending bit */
 		goto queue;
+	}
 
 	if (virt_queued_spin_lock(lock))
 		return;
@@ -463,6 +487,7 @@ EXPORT_SYMBOL(queued_spin_lock_slowpath);
 #undef pv_wait_node
 #undef pv_kick_node
 #undef pv_wait_head
+#undef pv_pending_lock
 
 #undef  queued_spin_lock_slowpath
 #define queued_spin_lock_slowpath	__pv_queued_spin_lock_slowpath
kernel/locking/qspinlock_paravirt.h +66 -0

78 lines not on this page · raw message

Signature · 1 line
1.7.1
#11 lore raw

PATCH v2 3/6 locking/pvqspinlock: Collect slowpath lock statistics

In reply to 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	89.8us		 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 a kernel build (no CPU overcommit) was:

hash_count=93
hash_hops_count=93
kick_latencies=6997535456
kick_time_count=755426
lock_kick_count=755354
pending_fail_count=10619
pending_lock_count=2912098
spurious_wakeup=8
unlock_kick_count=87
wait_head_count=91
wait_node_count=755359
wake_latencies=51052626984

---
 arch/x86/Kconfig                    |    7 ++
 kernel/locking/qspinlock_paravirt.h |  165 ++++++++++++++++++++++++++++++++++-
 2 files changed, 170 insertions(+), 2 deletions(-)
arch/x86/Kconfig +7 -0
index 55bced1..299a1c4 100644
@@ -679,6 +679,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 +163 -2

230 lines not on this page · raw message

Signature · 1 line
1.7.1
#12 lore raw

PATCH v2 4/6 locking/pvqspinlock: Allow vCPUs kick-ahead

In reply to Waiman Long

Frequent CPU halting (vmexit) and CPU kicking (vmenter) lengthens critical section and block forward progress. This patch implements a kick-ahead mechanism where the unlocker will kick the queue head vCPUs as well as up to four additional vCPUs next to the queue head if they were halted. The kickings are done after exiting the critical section to improve parallelism.

The amount of kick-ahead allowed depends on the number of vCPUs in the VM guest. This patch, by itself, won't do much as most of the kickings are currently done at lock time. Coupled with the next patch that defers lock time kicking to unlock time, it should improve overall system performance in a busy overcommitted guest.

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 3m25.0s 10m34.1s 2m02.0s 15m35.9s
After patch 3m27.4s 10m32.0s 2m00.8s 14m52.5s

There wasn't too much difference before and after the patch.

---
 kernel/locking/qspinlock_paravirt.h |   77 +++++++++++++++++++++++++++++++++-
 1 files changed, 74 insertions(+), 3 deletions(-)
kernel/locking/qspinlock_paravirt.h +74 -3
index c8485c4..f3ceeff 100644
@@ -51,6 +51,7 @@ enum pv_qlock_stat {
 	pvstat_kick_time,
 	pvstat_lock_kick,
 	pvstat_unlock_kick,
+	pvstat_kick_ahead,
 	pvstat_pend_lock,
 	pvstat_pend_fail,
 	pvstat_spurious,
@@ -72,6 +73,7 @@ static const char * const stat_fsnames[pvstat_num] = {
 	[pvstat_kick_time]   = "kick_time_count",
 	[pvstat_lock_kick]   = "lock_kick_count",
 	[pvstat_unlock_kick] = "unlock_kick_count",
+	[pvstat_kick_ahead]  = "kick_ahead_count",
 	[pvstat_pend_lock]   = "pending_lock_count",
 	[pvstat_pend_fail]   = "pending_fail_count",
 	[pvstat_spurious]    = "spurious_wakeup",
@@ -85,7 +87,8 @@ 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/(lock_kick_count + unlock_kick_count)
+ * Avg kick latency = pv_kick_latencies/
+ *		     (lock_kick_count + unlock_kick_count + kick_ahead_count)
  * Avg wake latency = pv_wake_latencies/kick_time_count
  */
 static atomic64_t pv_kick_latencies, pv_wake_latencies;
@@ -217,6 +220,12 @@ static struct pv_hash_entry *pv_lock_hash;
 static unsigned int pv_lock_hash_bits __read_mostly;
 
 /*
+ * Allow kick-ahead of vCPUs at unlock time
+ */
+#define PV_KICK_AHEAD_MAX	4
+static int pv_kick_ahead __read_mostly;
+
+/*
  * Allocate memory for the PV qspinlock hash buckets
  *
  * This function should be called from the paravirt spinlock initialization
@@ -224,7 +233,16 @@ static unsigned int pv_lock_hash_bits __read_mostly;
  */
 void __init __pv_init_lock_hash(void)
 {
-	int pv_hash_size = ALIGN(4 * num_possible_cpus(), PV_HE_PER_LINE);
+	int ncpus = num_possible_cpus();
+	int pv_hash_size = ALIGN(4 * ncpus, PV_HE_PER_LINE);
+	int i;
+
+	/*
+	 * The minimum number of vCPUs required in each kick-ahead level
+	 */
+	static const u8 kick_ahead_threshold[PV_KICK_AHEAD_MAX] = {
+		4, 8, 16, 32
+	};
 
 	if (pv_hash_size < PV_HE_MIN)
 		pv_hash_size = PV_HE_MIN;
@@ -238,6 +256,18 @@ void __init __pv_init_lock_hash(void)
 					       pv_hash_size, 0, HASH_EARLY,
 					       &pv_lock_hash_bits, NULL,
 					       pv_hash_size, pv_hash_size);
+	/*
+	 * Enable the unlock kick ahead mode according to the number of
+	 * vCPUs available.
+	 */
+	for (i = PV_KICK_AHEAD_MAX; i > 0; i--)
+		if (ncpus >= kick_ahead_threshold[i - 1]) {
+			pv_kick_ahead = i;
+			break;
+		}
+	if (pv_kick_ahead)
+		pr_info("PV unlock kick ahead level %d enabled\n",
+			pv_kick_ahead);
 }
 
 #define for_each_hash_entry(he, offset, hash)						\
@@ -424,6 +454,25 @@ static void pv_wait_node(struct mcs_spinlock *node)
 }
 
 /*
+ * Helper to get the address of the next kickable node
+ * The node has to be in the halted state and is being transitioned to
+ * running state by this function. Otherwise, NULL will be returned.
+ */
+static inline struct pv_node *pv_get_kick_node(struct pv_node *node)
+{
+	struct pv_node *next = (struct pv_node *)READ_ONCE(node->mcs.next);
+
+	if (!next)
+		return NULL;
+
+	if ((READ_ONCE(next->state) != vcpu_halted) ||
+	    (xchg(&next->state, vcpu_running) != vcpu_halted))
+		next = NULL;	/* No kicking is needed */
+
+	return next;
+}
+
+/*
  * Called after setting next->locked = 1, used to wake those stuck in
  * pv_wait_node().
  */
@@ -510,7 +559,8 @@ static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node)
 __visible void __pv_queued_spin_unlock(struct qspinlock *lock)
 {
 	struct __qspinlock *l = (void *)lock;
-	struct pv_node *node;
+	struct pv_node *node, *nxt, *next[PV_KICK_AHEAD_MAX];
+	int i, nr_kick;
 
 	/*
 	 * We must not unlock if SLOW, because in that case we must first
@@ -527,6 +577,19 @@ __visible void __pv_queued_spin_unlock(struct qspinlock *lock)
 	node = pv_unhash(lock);
 
 	/*
+	 * Implement unlock kick-ahead
+	 *
+	 * Access the next group of nodes, if available, and prepare to kick
+	 * them after releasing the lock if they are in the halted state. This
+	 * should improve performance on an overcommitted system.
+	 */
+	for (nr_kick = 0, nxt = node; nr_kick < pv_kick_ahead; nr_kick++) {
+		nxt = next[nr_kick] = pv_get_kick_node(nxt);
+		if (!nxt)
+			break;
+	}
+
+	/*
 	 * Now that we have a reference to the (likely) blocked pv_node,
 	 * release the lock.
 	 */
@@ -538,6 +601,14 @@ __visible void __pv_queued_spin_unlock(struct qspinlock *lock)
 	 */
 	pvstat_inc(pvstat_unlock_kick);
 	pv_kick(node->cpu);
+
+	/*
+	 * Kick the next group of vCPUs, if available.
+	 */
+	for (i = 0; i < nr_kick; i++) {
+		pvstat_inc(pvstat_kick_ahead);
+		pv_kick(next[i]->cpu);
+	}
 }
 /*
  * Include the architecture specific callee-save thunk of the
Signature · 1 line
1.7.1
maintainer
#13 lore raw

Re: [PATCH v2 4/6] locking/pvqspinlock: Allow vCPUs kick-ahead

Quoted 18 lines · Waiman Long

Frequent CPU halting (vmexit) and CPU kicking (vmenter) lengthens critical section and block forward progress. This patch implements a kick-ahead mechanism where the unlocker will kick the queue head vCPUs as well as up to four additional vCPUs next to the queue head if they were halted. The kickings are done after exiting the critical section to improve parallelism.

The amount of kick-ahead allowed depends on the number of vCPUs in the VM guest. This patch, by itself, won't do much as most of the kickings are currently done at lock time. Coupled with the next patch that defers lock time kicking to unlock time, it should improve overall system performance in a busy overcommitted guest.

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:

Quoted 7 lines

Westmere Haswell
Patch 32 vCPUs 48 vCPUs 32 vCPUs 48 vCPUs
----- -------- -------- -------- --------
Before patch 3m25.0s 10m34.1s 2m02.0s 15m35.9s
After patch 3m27.4s 10m32.0s 2m00.8s 14m52.5s

There wasn't too much difference before and after the patch.

That means either the patch isn't worth it, or as you seem to imply its in the wrong place in this series.

Quoted 5 lines
kernel/locking/qspinlock_paravirt.h +0 -1
@@ -224,7 +233,16 @@ static unsigned int pv_lock_hash_bits __read_mostly;
  */
 void __init __pv_init_lock_hash(void)
 {
-	int pv_hash_size = ALIGN(4 * num_possible_cpus(), PV_HE_PER_LINE);

kernel/locking/qspinlock_paravirt.h static unsigned int pv_lock_hash_bits __read_mostly; · line 245

Quoted 10 lines
kernel/locking/qspinlock_paravirt.h +10 -0
+	int ncpus = num_possible_cpus();
+	int pv_hash_size = ALIGN(4 * ncpus, PV_HE_PER_LINE);
+	int i;
+
+	/*
+	 * The minimum number of vCPUs required in each kick-ahead level
+	 */
+	static const u8 kick_ahead_threshold[PV_KICK_AHEAD_MAX] = {
+		4, 8, 16, 32
+	};

You are aware we have ilog2(), right?

kernel/locking/qspinlock_paravirt.h void __init __pv_init_lock_hash(void) · line 267

Quoted 9 lines
kernel/locking/qspinlock_paravirt.h +9 -0
+	/*
+	 * Enable the unlock kick ahead mode according to the number of
+	 * vCPUs available.
+	 */
+	for (i = PV_KICK_AHEAD_MAX; i > 0; i--)
+		if (ncpus >= kick_ahead_threshold[i - 1]) {
+			pv_kick_ahead = i;
+			break;
+		}

That's missing { }.

kernel/locking/qspinlock_paravirt.h void __init __pv_init_lock_hash(void) · line 270

Quoted 3 lines
kernel/locking/qspinlock_paravirt.h +3 -0
+	if (pv_kick_ahead)
+		pr_info("PV unlock kick ahead level %d enabled\n",
+			pv_kick_ahead);

Idem.

That said, I still really dislike this patch, it again seems a random bunch of hacks.

You also do not offer any support for any of the magic numbers..

#14 lore raw

Re: [PATCH v2 4/6] locking/pvqspinlock: Allow vCPUs kick-ahead

Quoted 25 lines · Peter Zijlstra
Quoted 24 lines · Waiman Long

Frequent CPU halting (vmexit) and CPU kicking (vmenter) lengthens critical section and block forward progress. This patch implements a kick-ahead mechanism where the unlocker will kick the queue head vCPUs as well as up to four additional vCPUs next to the queue head if they were halted. The kickings are done after exiting the critical section to improve parallelism.

The amount of kick-ahead allowed depends on the number of vCPUs in the VM guest. This patch, by itself, won't do much as most of the kickings are currently done at lock time. Coupled with the next patch that defers lock time kicking to unlock time, it should improve overall system performance in a busy overcommitted guest.

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 3m25.0s 10m34.1s 2m02.0s 15m35.9s
After patch 3m27.4s 10m32.0s 2m00.8s 14m52.5s

Quoted 3 lines
Quoted 1 line

There wasn't too much difference before and after the patch.

That means either the patch isn't worth it, or as you seem to imply its in the wrong place in this series.

It needs to be coupled with the next patch to be effective as most of the kicking are happening at the lock side, instead of at the unlock side. If you look at the sample pvqspinlock stats in patch 3:

lock_kick_count=755354
unlock_kick_count=87

The number of unlock kicks is negligible compared with the lock kicks. Patch 5 does have a dependency on patch 4 unless we make it unconditionally defers kicking to the unlock call which was what I had done in the v1 patch. The reason why I change this in v2 is because I found a very slight performance degradation in doing so.

Quoted 8 lines
Quoted 8 lines
kernel/locking/qspinlock_paravirt.h +3 -1
@@ -224,7 +233,16 @@ static unsigned int pv_lock_hash_bits __read_mostly;
   */
  void __init __pv_init_lock_hash(void)
  {
-	int pv_hash_size = ALIGN(4 * num_possible_cpus(), PV_HE_PER_LINE);
+	int ncpus = num_possible_cpus();
+	int pv_hash_size = ALIGN(4 * ncpus, PV_HE_PER_LINE);
+	int i;
Quoted 8 lines

kernel/locking/qspinlock_paravirt.h static unsigned int pv_lock_hash_bits __read_mostly; · line 245

Quoted 7 lines
kernel/locking/qspinlock_paravirt.h +7 -0
+
+	/*
+	 * The minimum number of vCPUs required in each kick-ahead level
+	 */
+	static const u8 kick_ahead_threshold[PV_KICK_AHEAD_MAX] = {
+		4, 8, 16, 32
+	};

You are aware we have ilog2(), right?

Right, I am not aware of ilog2(). I am going to use that instead.

Quoted 11 lines

kernel/locking/qspinlock_paravirt.h void __init __pv_init_lock_hash(void) · line 267

Quoted 9 lines
kernel/locking/qspinlock_paravirt.h +9 -0
+	/*
+	 * Enable the unlock kick ahead mode according to the number of
+	 * vCPUs available.
+	 */
+	for (i = PV_KICK_AHEAD_MAX; i>  0; i--)
+		if (ncpus>= kick_ahead_threshold[i - 1]) {
+			pv_kick_ahead = i;
+			break;
+		}

That's missing { }.

Quoted 4 lines

kernel/locking/qspinlock_paravirt.h void __init __pv_init_lock_hash(void) · line 270

Quoted 3 lines
kernel/locking/qspinlock_paravirt.h +3 -0
+	if (pv_kick_ahead)
+		pr_info("PV unlock kick ahead level %d enabled\n",
+			pv_kick_ahead);

Idem.

Will fix the {} problems.

Quoted 2 lines

That said, I still really dislike this patch, it again seems a random bunch of hacks.

Any suggestions to make it better suit your taste?

Quoted 1 line

You also do not offer any support for any of the magic numbers..

I chose 4 for PV_KICK_AHEAD_MAX as I didn't see much performance difference when I did a kick-ahead of 5. Also, it may be too unfair to the vCPU that was doing the kicking if the number is too big. Another magic number is pv_kick_ahead number. This one is kind of arbitrary. Right now I do a log2, but it can be divided by 4 (rshift 2) as well.

Cheers,
Longman

maintainer
#15 lore raw

Re: [PATCH v2 4/6] locking/pvqspinlock: Allow vCPUs kick-ahead

Quoted 34 lines · Waiman Long
Quoted 25 lines · Peter Zijlstra
Quoted 24 lines · Waiman Long

Frequent CPU halting (vmexit) and CPU kicking (vmenter) lengthens critical section and block forward progress. This patch implements a kick-ahead mechanism where the unlocker will kick the queue head vCPUs as well as up to four additional vCPUs next to the queue head if they were halted. The kickings are done after exiting the critical section to improve parallelism.

The amount of kick-ahead allowed depends on the number of vCPUs in the VM guest. This patch, by itself, won't do much as most of the kickings are currently done at lock time. Coupled with the next patch that defers lock time kicking to unlock time, it should improve overall system performance in a busy overcommitted guest.

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 3m25.0s 10m34.1s 2m02.0s 15m35.9s
After patch 3m27.4s 10m32.0s 2m00.8s 14m52.5s

Quoted 3 lines
Quoted 1 line

There wasn't too much difference before and after the patch.

That means either the patch isn't worth it, or as you seem to imply its in the wrong place in this series.

It needs to be coupled with the next patch to be effective as most of the kicking are happening at the lock side, instead of at the unlock side. If you look at the sample pvqspinlock stats in patch 3:

Quoted 8 lines

lock_kick_count=755354
unlock_kick_count=87

The number of unlock kicks is negligible compared with the lock kicks. Patch 5 does have a dependency on patch 4 unless we make it unconditionally defers kicking to the unlock call which was what I had done in the v1 patch. The reason why I change this in v2 is because I found a very slight performance degradation in doing so.

This way we cannot see the gains of the proposed complexity. So put it in a place where you can.

Quoted 7 lines
Quoted 1 line

You also do not offer any support for any of the magic numbers..

I chose 4 for PV_KICK_AHEAD_MAX as I didn't see much performance difference when I did a kick-ahead of 5. Also, it may be too unfair to the vCPU that was doing the kicking if the number is too big. Another magic number is pv_kick_ahead number. This one is kind of arbitrary. Right now I do a log2, but it can be divided by 4 (rshift 2) as well.

So what was the difference between 1-2-3-4 ? I would be thinking one extra kick is the biggest help, no?

#16 lore raw

Re: [PATCH v2 4/6] locking/pvqspinlock: Allow vCPUs kick-ahead

Quoted 37 lines · Peter Zijlstra
Quoted 36 lines · Waiman Long
Quoted 25 lines · Peter Zijlstra
Quoted 24 lines · Waiman Long

Frequent CPU halting (vmexit) and CPU kicking (vmenter) lengthens critical section and block forward progress. This patch implements a kick-ahead mechanism where the unlocker will kick the queue head vCPUs as well as up to four additional vCPUs next to the queue head if they were halted. The kickings are done after exiting the critical section to improve parallelism.

The amount of kick-ahead allowed depends on the number of vCPUs in the VM guest. This patch, by itself, won't do much as most of the kickings are currently done at lock time. Coupled with the next patch that defers lock time kicking to unlock time, it should improve overall system performance in a busy overcommitted guest.

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 3m25.0s 10m34.1s 2m02.0s 15m35.9s
After patch 3m27.4s 10m32.0s 2m00.8s 14m52.5s

Quoted 3 lines
Quoted 1 line

There wasn't too much difference before and after the patch.

That means either the patch isn't worth it, or as you seem to imply its in the wrong place in this series.

It needs to be coupled with the next patch to be effective as most of the kicking are happening at the lock side, instead of at the unlock side. If you look at the sample pvqspinlock stats in patch 3:

lock_kick_count=755354
unlock_kick_count=87

Quoted 7 lines
Quoted 5 lines

The number of unlock kicks is negligible compared with the lock kicks. Patch 5 does have a dependency on patch 4 unless we make it unconditionally defers kicking to the unlock call which was what I had done in the v1 patch. The reason why I change this in v2 is because I found a very slight performance degradation in doing so.

This way we cannot see the gains of the proposed complexity. So put it in a place where you can.

OK, I will see what I can do to make the performance change more visible on a patch-by-patch basis.

Quoted 8 lines
Quoted 6 lines
Quoted 1 line

You also do not offer any support for any of the magic numbers..

I chose 4 for PV_KICK_AHEAD_MAX as I didn't see much performance difference when I did a kick-ahead of 5. Also, it may be too unfair to the vCPU that was doing the kicking if the number is too big. Another magic number is pv_kick_ahead number. This one is kind of arbitrary. Right now I do a log2, but it can be divided by 4 (rshift 2) as well.

So what was the difference between 1-2-3-4 ? I would be thinking one extra kick is the biggest help, no?

I was seeing diminishing returns with more kicks. I can add a table on that in the next patch.

Cheers,
Longman

#17 lore raw

PATCH v2 5/6 locking/pvqspinlock: Opportunistically defer kicking to unlock time

In reply to Waiman Long

Performing CPU kicking at lock time can be a bit faster if there is no kick-ahead. On the other hand, deferring it to unlock time is preferrable when kick-ahead can be performed or when the VM guest is having too few vCPUs that a vCPU may be kicked twice before getting the lock. This patch implements the deferring kicking when either one of the above 2 conditions is true.

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 3m27.4s 10m32.0s 2m00.8s 14m52.5s
After patch 3m01.3s 9m50.9s 2m00.5s 13m28.1s

On Westmere, both 32/48 vCPUs case showed some sizeable increase in performance. For Haswell, there was some improvement in the overcommitted (48 vCPUs) case.

---
 kernel/locking/qspinlock.c          |    6 +-
 kernel/locking/qspinlock_paravirt.h |   71 +++++++++++++++++++++++++++--------
 2 files changed, 58 insertions(+), 19 deletions(-)
kernel/locking/qspinlock.c +3 -3
index 6518ee9..94fdd27 100644
@@ -259,8 +259,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_kick_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) { }
 
@@ -464,7 +464,7 @@ queue:
 		cpu_relax();
 
 	arch_mcs_spin_unlock_contended(&next->locked);
-	pv_kick_node(next);
+	pv_kick_node(lock, next);
 
 release:
 	/*
kernel/locking/qspinlock_paravirt.h +55 -16

121 lines not on this page · raw message

Signature · 1 line
1.7.1
#18 lore raw

Re: [PATCH v2 5/6] locking/pvqspinlock: Opportunistically defer kicking to unlock time

Quoted 18 lines · Waiman Long

Performing CPU kicking at lock time can be a bit faster if there is no kick-ahead. On the other hand, deferring it to unlock time is preferrable when kick-ahead can be performed or when the VM guest is having too few vCPUs that a vCPU may be kicked twice before getting the lock. This patch implements the deferring kicking when either one of the above 2 conditions is true.

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 3m27.4s 10m32.0s 2m00.8s 14m52.5s
After patch 3m01.3s 9m50.9s 2m00.5s 13m28.1s

Quoted 6 lines

On Westmere, both 32/48 vCPUs case showed some sizeable increase in performance. For Haswell, there was some improvement in the overcommitted (48 vCPUs) case.

---

Hi Waiman,

For virtual guests, from my experiments, lock waiter preemption was the main concern especially with fair locks.
I find that these set of patches are in right direction to address them.

Thanks for the patches.

maintainer
#19 lore raw

Re: [PATCH v2 5/6] locking/pvqspinlock: Opportunistically defer kicking to unlock time

In reply to Waiman Long
Quoted 54 lines · Waiman Long
kernel/locking/qspinlock_paravirt.h +36 -3
+static void pv_kick_node(struct qspinlock *lock, struct mcs_spinlock *node)
 {
 	struct pv_node *pn = (struct pv_node *)node;
 
+	if (xchg(&pn->state, vcpu_running) == vcpu_running)
+		return;
+
 	/*
+	 * Kicking the next node at lock time can actually be a bit faster
+	 * than doing it at unlock time because the critical section time
+	 * overlaps with the wakeup latency of the next node. However, if the
+	 * VM is too overcommmitted, it can happen that we need to kick the
+	 * CPU again at unlock time (double-kick). To avoid that and also to
+	 * fully utilize the kick-ahead functionality at unlock time,
+	 * the kicking will be deferred under either one of the following
+	 * 2 conditions:
 	 *
+	 * 1) The VM guest has too few vCPUs that kick-ahead is not even
+	 *    enabled. In this case, the chance of double-kick will be
+	 *    higher.
+	 * 2) The node after the next one is also in the halted state.
 	 *
+	 * In this case, the hashed flag is set to indicate that hashed
+	 * table has been filled and _Q_SLOW_VAL is set.
 	 */
-	if (xchg(&pn->state, vcpu_running) == vcpu_halted) {
-		pvstat_inc(pvstat_lock_kick);
-		pv_kick(pn->cpu);
+	if ((!pv_kick_ahead || pv_get_kick_node(pn, 1)) &&
+	    (xchg(&pn->hashed, 1) == 0)) {
+		struct __qspinlock *l = (void *)lock;
+
+		/*
+		 * As this is the same vCPU that will check the _Q_SLOW_VAL
+		 * value and the hash table later on at unlock time, no atomic
+		 * instruction is needed.
+		 */
+		WRITE_ONCE(l->locked, _Q_SLOW_VAL);
+		(void)pv_hash(lock, pn);
+		return;
 	}
+
+	/*
+	 * Kicking the vCPU even if it is not really halted is safe.
+	 */
+	pvstat_inc(pvstat_lock_kick);
+	pv_kick(pn->cpu);
 }
 
 /*
@@ -513,6 +545,13 @@ static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node)
 			cpu_relax();
 		}
 

kernel/locking/qspinlock_paravirt.h static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node) · line 557

Quoted 10 lines
kernel/locking/qspinlock_paravirt.h +7 -0
+		if (!lp && (xchg(&pn->hashed, 1) == 1))
+			/*
+			 * The hashed table & _Q_SLOW_VAL had been filled
+			 * by the lock holder.
+			 */
+			lp = (struct qspinlock **)-1;
+
 		if (!lp) { /* ONCE */
 			lp = pv_hash(lock, pn);
 			/*

*groan*, so you complained the previous version of this patch was too complex, but let me say I vastly preferred it to this one :/

#20 lore raw

Re: [PATCH v2 5/6] locking/pvqspinlock: Opportunistically defer kicking to unlock time

Quoted 55 lines · Peter Zijlstra
Quoted 54 lines · Waiman Long
kernel/locking/qspinlock_paravirt.h +36 -3
+static void pv_kick_node(struct qspinlock *lock, struct mcs_spinlock *node)
  {
  	struct pv_node *pn = (struct pv_node *)node;
 
+	if (xchg(&pn->state, vcpu_running) == vcpu_running)
+		return;
+
  	/*
+	 * Kicking the next node at lock time can actually be a bit faster
+	 * than doing it at unlock time because the critical section time
+	 * overlaps with the wakeup latency of the next node. However, if the
+	 * VM is too overcommmitted, it can happen that we need to kick the
+	 * CPU again at unlock time (double-kick). To avoid that and also to
+	 * fully utilize the kick-ahead functionality at unlock time,
+	 * the kicking will be deferred under either one of the following
+	 * 2 conditions:
  	 *
+	 * 1) The VM guest has too few vCPUs that kick-ahead is not even
+	 *    enabled. In this case, the chance of double-kick will be
+	 *    higher.
+	 * 2) The node after the next one is also in the halted state.
  	 *
+	 * In this case, the hashed flag is set to indicate that hashed
+	 * table has been filled and _Q_SLOW_VAL is set.
  	 */
-	if (xchg(&pn->state, vcpu_running) == vcpu_halted) {
-		pvstat_inc(pvstat_lock_kick);
-		pv_kick(pn->cpu);
+	if ((!pv_kick_ahead || pv_get_kick_node(pn, 1))&&
+	    (xchg(&pn->hashed, 1) == 0)) {
+		struct __qspinlock *l = (void *)lock;
+
+		/*
+		 * As this is the same vCPU that will check the _Q_SLOW_VAL
+		 * value and the hash table later on at unlock time, no atomic
+		 * instruction is needed.
+		 */
+		WRITE_ONCE(l->locked, _Q_SLOW_VAL);
+		(void)pv_hash(lock, pn);
+		return;
  	}
+
+	/*
+	 * Kicking the vCPU even if it is not really halted is safe.
+	 */
+	pvstat_inc(pvstat_lock_kick);
+	pv_kick(pn->cpu);
  }
 
  /*
@@ -513,6 +545,13 @@ static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node)
  			cpu_relax();
  		}
 
Quoted 12 lines

kernel/locking/qspinlock_paravirt.h static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node) · line 557

Quoted 10 lines
kernel/locking/qspinlock_paravirt.h +7 -0
+		if (!lp&&  (xchg(&pn->hashed, 1) == 1))
+			/*
+			 * The hashed table&  _Q_SLOW_VAL had been filled
+			 * by the lock holder.
+			 */
+			lp = (struct qspinlock **)-1;
+
  		if (!lp) { /* ONCE */
  			lp = pv_hash(lock, pn);
  			/*

*groan*, so you complained the previous version of this patch was too complex, but let me say I vastly preferred it to this one :/

I said it was complex as maintaining a tri-state variable needed more thought than 2 bi-state variables. I can revert it back to the tri-state variable as doing an unconditional kick in unlock simplifies the code at pv_wait_head().

Cheers,
Longman

maintainer
#21 lore raw

Re: [PATCH v2 5/6] locking/pvqspinlock: Opportunistically defer kicking to unlock time

Quoted 9 lines · Waiman Long
Quoted 2 lines · Peter Zijlstra

*groan*, so you complained the previous version of this patch was too complex, but let me say I vastly preferred it to this one :/

I said it was complex as maintaining a tri-state variable needed more thought than 2 bi-state variables. I can revert it back to the tri-state variable as doing an unconditional kick in unlock simplifies the code at pv_wait_head().

Well, your state space isn't shrunk, you just use more variables and I'm not entirely sure that actually matters.

What also doesn't help is that mixing with the kicking code.

#22 lore raw

PATCH v2 6/6 locking/pvqspinlock: Queue node adaptive spinning

In reply to 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.

Reducing the spinning threshold is found to improve performance in an overcommitted VM guest, but decrease performance when there is no overcommittment.

This patch implements an adaptive spinning mechanism where the vCPU will call pv_wait() earlier under the following 3 conditions:
1) the previous vCPU is in the halted state;
2) the current vCPU is at least 2 nodes away from the lock holder;
3) there are a lot of pv_wait() for the current vCPU recently.

If all the conditions are true, it will spin less before calling pv_wait().

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 3m01.3s 9m50.9s 2m00.5s 13m28.1s
After patch 3m06.2s 9m38.0s 2m01.8s 9m06.9s

This patch seemed to cause a little bit of performance degraduation for 32 vCPUs. For 48 vCPUs, there was some performance for Westmere and a big performance jump for Haswell.

---
 kernel/locking/qspinlock.c          |    5 +-
 kernel/locking/qspinlock_paravirt.h |   93 ++++++++++++++++++++++++++++++++--
 2 files changed, 90 insertions(+), 8 deletions(-)
kernel/locking/qspinlock.c +3 -2
index 94fdd27..da39d43 100644
@@ -258,7 +258,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 void __pv_kick_node(struct qspinlock *lock,
 					   struct mcs_spinlock *node) { }
 static __always_inline void __pv_wait_head(struct qspinlock *lock,
@@ -415,7 +416,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 +87 -6

148 lines not on this page · raw message

Signature · 1 line
1.7.1
maintainer
#23 lore raw

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

Quoted 50 lines · Waiman Long
kernel/locking/qspinlock_paravirt.h +41 -2
+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;
+	bool wait_early, can_wait_early;
 	int loop;
 
 	for (;;) {
-		for (loop = SPIN_THRESHOLD; loop; loop--) {
+		/*
+		 * Spin less if the previous vCPU was in the halted state
+		 * and it is not the queue head.
+		 */
+		can_wait_early = (pn->waithist > PV_WAITHIST_THRESHOLD);
+		wait_early = can_wait_early && !READ_ONCE(prev->locked) &&
+			     (READ_ONCE(pp->state) == vcpu_halted);
+		loop = wait_early ? QNODE_SPIN_THRESHOLD_SHORT
+				  : QNODE_SPIN_THRESHOLD;
+		for (; loop; loop--, cpu_relax()) {
+			bool halted;
+
 			if (READ_ONCE(node->locked))
 				return;
-			cpu_relax();
+
+			if (!can_wait_early || (loop & QNODE_SPIN_CHECK_MASK))
+				continue;
+
+			/*
+			 * Look for state transition at previous node.
+			 *
+			 * running => halted:
+			 *	call pv_wait() now if kick-ahead is enabled
+			 *	or reduce spin threshold to
+			 *	QNODE_SPIN_THRESHOLD_SHORT or less.
+			 * halted => running:
+			 *	reset spin threshold to QNODE_SPIN_THRESHOLD
+			 */
+			halted = (READ_ONCE(pp->state) == vcpu_halted) &&
+				 !READ_ONCE(prev->locked);
+			if (wait_early == halted)
+				continue;
+			wait_early = halted;
+
+			if (!wait_early)
+				loop = QNODE_SPIN_THRESHOLD;
+			else if (pv_kick_ahead)
+				break;
+			else if (loop > QNODE_SPIN_THRESHOLD_SHORT)
+				loop = QNODE_SPIN_THRESHOLD_SHORT;

kernel/locking/qspinlock_paravirt.h gotlock: · line 493

Quoted 10 lines
kernel/locking/qspinlock_paravirt.h +9 -0
 		}
+		if (wait_early)
+			pvstat_inc(pvstat_wait_early);
+
+		/*
+		 * A pv_wait while !wait_early has higher weight than when
+		 * wait_early is true.
+		 */
+		if (pn->waithist < PV_WAITHIST_MAX)
+			pn->waithist += wait_early ? 1 : PV_WAIT_INC;

So when you looked at this patch, you didn't go like, OMFG!?

So what was wrong with something like:

static inline int pv_spin_threshold(struct pv_node *prev)

{
	if (READ_ONCE(prev->locked)) /* it can run, wait for it */
		return SPIN_THRESHOLD;

	if (READ_ONCE(prev->state) == vcpu_halted) /* its not running, do not wait */
		return 1;

	return SPIN_THRESHOLD;
}

static void pv_wait_head(...)

{
	for (;;) {
		for (loop = pv_spin_threshold(pp); loop; loop--) {
			if (READ_ONCE(node->locked))
				return;
			cpu_relax();
		}

		if (!lp) {
			...
		}
		pv_wait(&l->locked, _Q_SLOW_VAL);
	}
}

What part of: "keep it simple" and "gradual complexity" have you still not grasped?

#24 lore raw

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

Quoted 92 lines · Peter Zijlstra
Quoted 50 lines · Waiman Long
kernel/locking/qspinlock_paravirt.h +41 -2
+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;
+	bool wait_early, can_wait_early;
  	int loop;
 
  	for (;;) {
-		for (loop = SPIN_THRESHOLD; loop; loop--) {
+		/*
+		 * Spin less if the previous vCPU was in the halted state
+		 * and it is not the queue head.
+		 */
+		can_wait_early = (pn->waithist>  PV_WAITHIST_THRESHOLD);
+		wait_early = can_wait_early&&  !READ_ONCE(prev->locked)&&
+			     (READ_ONCE(pp->state) == vcpu_halted);
+		loop = wait_early ? QNODE_SPIN_THRESHOLD_SHORT
+				  : QNODE_SPIN_THRESHOLD;
+		for (; loop; loop--, cpu_relax()) {
+			bool halted;
+
  			if (READ_ONCE(node->locked))
  				return;
-			cpu_relax();
+
+			if (!can_wait_early || (loop&  QNODE_SPIN_CHECK_MASK))
+				continue;
+
+			/*
+			 * Look for state transition at previous node.
+			 *
+			 * running =>  halted:
+			 *	call pv_wait() now if kick-ahead is enabled
+			 *	or reduce spin threshold to
+			 *	QNODE_SPIN_THRESHOLD_SHORT or less.
+			 * halted =>  running:
+			 *	reset spin threshold to QNODE_SPIN_THRESHOLD
+			 */
+			halted = (READ_ONCE(pp->state) == vcpu_halted)&&
+				 !READ_ONCE(prev->locked);
+			if (wait_early == halted)
+				continue;
+			wait_early = halted;
+
+			if (!wait_early)
+				loop = QNODE_SPIN_THRESHOLD;
+			else if (pv_kick_ahead)
+				break;
+			else if (loop>  QNODE_SPIN_THRESHOLD_SHORT)
+				loop = QNODE_SPIN_THRESHOLD_SHORT;

kernel/locking/qspinlock_paravirt.h gotlock: · line 493

Quoted 10 lines
kernel/locking/qspinlock_paravirt.h +9 -0
  		}
+		if (wait_early)
+			pvstat_inc(pvstat_wait_early);
+
+		/*
+		 * A pv_wait while !wait_early has higher weight than when
+		 * wait_early is true.
+		 */
+		if (pn->waithist<  PV_WAITHIST_MAX)
+			pn->waithist += wait_early ? 1 : PV_WAIT_INC;

So when you looked at this patch, you didn't go like, OMFG!?

So what was wrong with something like:

static inline int pv_spin_threshold(struct pv_node *prev)

{
	if (READ_ONCE(prev->locked)) /* it can run, wait for it */
		return SPIN_THRESHOLD;

	if (READ_ONCE(prev->state) == vcpu_halted) /* its not running, do not wait */
		return 1;

	return SPIN_THRESHOLD;
}

static void pv_wait_head(...)

{
	for (;;) {
		for (loop = pv_spin_threshold(pp); loop; loop--) {
			if (READ_ONCE(node->locked))
				return;
			cpu_relax();
		}

		if (!lp) {
			...
		}
		pv_wait(&l->locked, _Q_SLOW_VAL);
	}
}
Quoted 2 lines

What part of: "keep it simple" and "gradual complexity" have you still not grasped?

I confess that I was a bit sloppy in that part of the code. I want to get it out for review ASAP without doing too much fine tuning as I expect at least a few iterations for this patchset. I will certainly change it in the new patch. Anyway, thanks for the great suggestion.

Cheers,
Longman