Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1197915 > unrolled thread

[PATCH v4 0/7] locking/qspinlock: Enhance pvqspinlock performance

Back to article view | Back to linux.kernel

Contents

  [PATCH v4 0/7] locking/qspinlock: Enhance pvqspinlock performance Waiman Long <Waiman.Long@hp.com> - 2015-08-01 04:30 +0200
    [PATCH v4 3/7] locking/pvqspinlock: Collect slowpath lock statistics Waiman Long <Waiman.Long@hp.com> - 2015-08-01 04:30 +0200

#1197915 — [PATCH v4 0/7] locking/qspinlock: Enhance pvqspinlock performance

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 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 slowing performance a tiny bit.

Patch 4 optimizes the PV unlock code path performance for x86-64
architecture.

Patch 5 is an enablement patch for deferring vCPU kickings from the
lock side to the unlock side.

Patch 6 enables multiple vCPU kick-ahead's at unlock time, outside of
the critical section which can improve performance in overcommitted
guests and sometime even in normal guests.

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

Patches 2 & 4 improves performance of common uncontended and lightly
contended cases. Patches 5-7 are for improving performance in
over-committed VM guests.

Performance measurements were done on a 32-CPU Westmere-EX and
Haswell-EX systems. The Westmere-EX system got the most performance
gain from patch 5, whereas the Haswell-EX system got the most gain
from patch 6 for over-committed guests.

The table below shows the Linux kernel build times for various
values of PV_KICK_AHEAD_MAX on an over-committed 48-vCPU guest on
the Westmere-EX system:

  PV_KICK_AHEAD_MAX	Patches 1-5	Patches 1-6
  -----------------	-----------	-----------
	  1		  9m46.9s	 11m10.1s
	  2		  9m40.2s	 10m08.3s
	  3		  9m36.8s	  9m49.8s
	  4		  9m35.9s	  9m38.7s
	  5		  9m35.1s	  9m33.0s
	  6		  9m35.7s	  9m28.5s

With patches 1-5, the performance wasn't very sensitive to different
PV_KICK_AHEAD_MAX values. Adding patch 6 into the mix, however, changes
the picture quite dramatically. There is a performance regression if
PV_KICK_AHEAD_MAX is too small. Starting with a value of 4, increasing
PV_KICK_AHEAD_MAX only gets us a minor benefit.

Waiman Long (7):
  locking/pvqspinlock: Unconditional PV kick with _Q_SLOW_VAL
  locking/pvqspinlock: Add pending bit support
  locking/pvqspinlock: Collect slowpath lock statistics
  locking/pvqspinlock, x86: Optimize PV unlock code path
  locking/pvqspinlock: Enable deferment of vCPU kicking to unlock call
  locking/pvqspinlock: Allow vCPUs kick-ahead
  locking/pvqspinlock: Queue node adaptive spinning

 arch/x86/Kconfig                          |    7 +
 arch/x86/include/asm/qspinlock_paravirt.h |   59 +++
 kernel/locking/qspinlock.c                |   38 ++-
 kernel/locking/qspinlock_paravirt.h       |  546 +++++++++++++++++++++++++++--
 4 files changed, 612 insertions(+), 38 deletions(-)

 v3-to-v4 diff:

 arch/x86/include/asm/qspinlock_paravirt.h |    5 +--
 kernel/locking/qspinlock_paravirt.h       |   45 +++++++++++++++++-----------
 2 files changed, 29 insertions(+), 21 deletions(-)

diff --git a/arch/x86/include/asm/qspinlock_paravirt.h b/arch/x86/include/asm/qspinlock_paravirt.h
index 46f0f82..3001972 100644
--- a/arch/x86/include/asm/qspinlock_paravirt.h
+++ b/arch/x86/include/asm/qspinlock_paravirt.h
@@ -9,10 +9,10 @@
  */
 #ifdef CONFIG_64BIT
 
-PV_CALLEE_SAVE_REGS_THUNK(pv_queued_spin_unlock_slowpath);
+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"
+#define PV_UNLOCK_SLOWPATH	"__raw_callee_save___pv_queued_spin_unlock_slowpath"
 
 /*
  * Optimized assembly version of __raw_callee_save___pv_queued_spin_unlock
@@ -46,7 +46,6 @@ asm(".pushsection .text;"
     "jne   .slowpath;"
     "pop   %rdx;"
     "ret;"
-    "nop;"
     ".slowpath: "
     "push   %rsi;"
     "movzbl %al,%esi;"
diff --git a/kernel/locking/qspinlock_paravirt.h b/kernel/locking/qspinlock_paravirt.h
index 56c3717..d04911b 100644
--- a/kernel/locking/qspinlock_paravirt.h
+++ b/kernel/locking/qspinlock_paravirt.h
@@ -463,16 +463,16 @@ static int pv_pending_lock(struct qspinlock *lock, u32 val)
 	/*
 	 * wait for in-progress pending->locked hand-overs
 	 */
-	if (val == _Q_PENDING_VAL) {
-		while (((val = atomic_read(&lock->val)) == _Q_PENDING_VAL) &&
-			loop--)
-			cpu_relax();
+	while ((val == _Q_PENDING_VAL) && loop) {
+		cpu_relax();
+		val = atomic_read(&lock->val);
+		loop--;
 	}
 
 	/*
 	 * trylock || pending
 	 */
-	for (;;) {
+	for (;; loop--) {
 		if (val & ~_Q_LOCKED_MASK)
 			goto queue;
 		new = _Q_LOCKED_VAL;
@@ -481,7 +481,7 @@ static int pv_pending_lock(struct qspinlock *lock, u32 val)
 		old = atomic_cmpxchg(&lock->val, val, new);
 		if (old == val)
 			break;
-		if (loop-- <= 0)
+		if (!loop)
 			goto queue;
 	}
 
@@ -490,16 +490,18 @@ static int pv_pending_lock(struct qspinlock *lock, u32 val)
 	/*
 	 * We are pending, wait for the owner to go away.
 	 */
-	while (((val = smp_load_acquire(&lock->val.counter)) & _Q_LOCKED_MASK)
-		&& (loop-- > 0))
-		cpu_relax();
-
-	if (!(val & _Q_LOCKED_MASK)) {
-		clear_pending_set_locked(lock);
-		goto gotlock;
+	for (; loop; loop--, cpu_relax()) {
+		val = smp_load_acquire(&lock->val.counter);
+		if (!(val & _Q_LOCKED_MASK)) {
+			clear_pending_set_locked(lock);
+			pvstat_inc(pvstat_pend_lock);
+			goto gotlock;
+		}
 	}
+
 	/*
-	 * Clear the pending bit and fall back to queuing
+	 * Fail to acquire the lock within the spinning period,
+	 * so clear the pending bit and fall back to queuing.
 	 */
 	clear_pending(lock);
 	pvstat_inc(pvstat_pend_fail);
@@ -719,11 +721,11 @@ static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node)
 }
 
 /*
- * PV version of the unlock fastpath and slowpath functions 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_slowpath(struct qspinlock *lock, u8 lockval)
+__pv_queued_spin_unlock_slowpath(struct qspinlock *lock, u8 lockval)
 {
 	struct __qspinlock *l = (void *)lock;
 	struct pv_node *node, *next;
@@ -771,6 +773,13 @@ pv_queued_spin_unlock_slowpath(struct qspinlock *lock, u8 lockval)
 	/*
 	 * 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.
+	 *
+	 * As smp_store_release() is not a full barrier, adding a check to
+	 * the node->state doesn't guarantee the checking is really done
+	 * after clearing the lock byte since they are in 2 separate
+	 * cachelines and so hardware can reorder them. So either we insert
+	 * memory barrier here and in the corresponding pv_wait_head()
+	 * function or we do an unconditional kick which is what is done here.
 	 */
 	pvstat_inc(pvstat_unlock_kick);
 	pv_kick(node->cpu);
@@ -803,6 +812,6 @@ __visible void __pv_queued_spin_unlock(struct qspinlock *lock)
 	if (likely(lockval == _Q_LOCKED_VAL))
 		return;
 
-	pv_queued_spin_unlock_slowpath(lock, lockval);
+	__pv_queued_spin_unlock_slowpath(lock, lockval);
 }
 #endif /* __pv_queued_spin_unlock */
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [next] | [standalone]

#1197916 — [PATCH v4 3/7] locking/pvqspinlock: Collect slowpath lock statistics

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_hops_count=43
kick_latencies=5783565492
kick_time_count=640269
lock_kick_count=640238
pending_fail_count=10672
pending_lock_count=2946871
spurious_wakeup=14
unlock_kick_count=38
wait_again_count=4
wait_head_count=41
wait_node_count=640242
wake_latencies=42491684295

Signed-off-by: Waiman Long <Waiman.Long@hp.com>
---
 arch/x86/Kconfig                    |    7 ++
 kernel/locking/qspinlock_paravirt.h |  179 ++++++++++++++++++++++++++++++++++-
 2 files changed, 182 insertions(+), 4 deletions(-)

diff --git a/arch/x86/Kconfig b/arch/x86/Kconfig
index b3a1a5d..e89080b 100644
--- a/arch/x86/Kconfig
+++ b/arch/x86/Kconfig
@@ -685,6 +685,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 5325877..3552aa9 100644
--- a/kernel/locking/qspinlock_paravirt.h
+++ b/kernel/locking/qspinlock_paravirt.h
@@ -44,6 +44,153 @@ struct pv_node {
 };
 
 /*
+ * PV qspinlock statistics
+ */
+enum pv_qlock_stat {
+	pvstat_wait_head,
+	pvstat_wait_node,
+	pvstat_wait_again,
+	pvstat_kick_time,
+	pvstat_lock_kick,
+	pvstat_unlock_kick,
+	pvstat_pend_lock,
+	pvstat_pend_fail,
+	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_time]   = "kick_time_count",
+	[pvstat_lock_kick]   = "lock_kick_count",
+	[pvstat_unlock_kick] = "unlock_kick_count",
+	[pvstat_pend_lock]   = "pending_lock_count",
+	[pvstat_pend_fail]   = "pending_fail_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/(lock_kick_count + unlock_kick_count)
+ * Avg wake latency   = pv_wake_latencies/kick_time_count
+ * Avg # of hops/hash = hash_hops_count/unlock_kick_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_time);
+	}
+}
+
+#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
@@ -103,10 +250,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;
 		}
 	}
@@ -201,6 +351,7 @@ static int pv_pending_lock(struct qspinlock *lock, u32 val)
 		val = smp_load_acquire(&lock->val.counter);
 		if (!(val & _Q_LOCKED_MASK)) {
 			clear_pending_set_locked(lock);
+			pvstat_inc(pvstat_pend_lock);
 			goto gotlock;
 		}
 	}
@@ -210,11 +361,13 @@ static int pv_pending_lock(struct qspinlock *lock, u32 val)
 	 * so clear the pending bit and fall back to queuing.
 	 */
 	clear_pending(lock);
+	pvstat_inc(pvstat_pend_fail);
 
 queue:
 	return 0;
 
 gotlock:
+	pvstat_inc(pvstat_pend_lock);
 	return 1;
 }
 
@@ -225,9 +378,10 @@ gotlock:
 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;
@@ -245,14 +399,20 @@ 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);
+		}
 
 		/*
 		 * Reset the vCPU state to avoid unncessary CPU kicking
 		 */
 		WRITE_ONCE(pn->state, 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,
@@ -260,6 +420,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);
 	}
 	/*
 	 * By now our node->locked should be 1 and our caller will not actually
@@ -285,8 +446,10 @@ static void pv_kick_node(struct mcs_spinlock *node)
 	 *
 	 * See the comment in pv_wait_node().
 	 */
-	if (xchg(&pn->state, vcpu_running) == vcpu_halted)
+	if (xchg(&pn->state, vcpu_running) == vcpu_halted) {
+		pvstat_inc(pvstat_lock_kick);
 		pv_kick(pn->cpu);
+	}
 }
 
 /*
@@ -298,9 +461,10 @@ 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;
 
-	for (;;) {
+	for (;; waitcnt++) {
 		for (loop = SPIN_THRESHOLD; loop; loop--) {
 			if (!READ_ONCE(l->locked))
 				return;
@@ -328,14 +492,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);
 	}
 
 	/*
@@ -394,6 +564,7 @@ __visible void __pv_queued_spin_unlock(struct qspinlock *lock)
 	 * memory barrier here and in the corresponding pv_wait_head()
 	 * function or we do an unconditional kick which is what is done here.
 	 */
+	pvstat_inc(pvstat_unlock_kick);
 	pv_kick(node->cpu);
 }
 /*
-- 
1.7.1

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web