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

Groups > linux.kernel > #1259848 > unrolled thread

[PATCH tip/locking/core v9 0/6] locking/qspinlock: Enhance pvqspinlock

Back to article view | Back to linux.kernel

Contents

  [PATCH tip/locking/core v9 0/6] locking/qspinlock: Enhance pvqspinlock  Waiman Long <Waiman.Long@hpe.com> - 2015-10-31 00:30 +0100
    [PATCH tip/locking/core v9 1/6] locking/qspinlock: Use _acquire/_release versions of cmpxchg & xchg Waiman Long <Waiman.Long@hpe.com> - 2015-10-31 00:30 +0100
    [PATCH tip/locking/core v9 2/6] locking/qspinlock: prefetch next node cacheline Waiman Long <Waiman.Long@hpe.com> - 2015-10-31 00:30 +0100
      Re: [PATCH tip/locking/core v9 2/6] locking/qspinlock: prefetch next  node cacheline Peter Zijlstra <peterz@infradead.org> - 2015-11-02 17:40 +0100
        Re: [PATCH tip/locking/core v9 2/6] locking/qspinlock: prefetch next  node cacheline Peter Zijlstra <peterz@infradead.org> - 2015-11-03 00:00 +0100
          Re: [PATCH tip/locking/core v9 2/6] locking/qspinlock: prefetch next  node cacheline Waiman Long <waiman.long@hpe.com> - 2015-11-05 17:50 +0100
            Re: [PATCH tip/locking/core v9 2/6] locking/qspinlock: prefetch next  node cacheline Peter Zijlstra <peterz@infradead.org> - 2015-11-05 18:00 +0100
        Re: [PATCH tip/locking/core v9 2/6] locking/qspinlock: prefetch next  node cacheline Waiman Long <waiman.long@hpe.com> - 2015-11-05 17:10 +0100
          Re: [PATCH tip/locking/core v9 2/6] locking/qspinlock: prefetch next  node cacheline Peter Zijlstra <peterz@infradead.org> - 2015-11-05 17:40 +0100
            Re: [PATCH tip/locking/core v9 2/6] locking/qspinlock: prefetch next  node cacheline Waiman Long <waiman.long@hpe.com> - 2015-11-05 18:00 +0100
    [PATCH tip/locking/core v9 5/6] locking/pvqspinlock: Allow 1 lock stealing attempt Waiman Long <Waiman.Long@hpe.com> - 2015-10-31 00:30 +0100
      Re: [PATCH tip/locking/core v9 5/6] locking/pvqspinlock: Allow 1  lock stealing attempt Peter Zijlstra <peterz@infradead.org> - 2015-11-06 16:00 +0100
        Re: [PATCH tip/locking/core v9 5/6] locking/pvqspinlock: Allow 1  lock stealing attempt Waiman Long <waiman.long@hpe.com> - 2015-11-06 18:50 +0100
          Re: [PATCH tip/locking/core v9 5/6] locking/pvqspinlock: Allow 1  lock stealing attempt Peter Zijlstra <peterz@infradead.org> - 2015-11-09 18:40 +0100
            Re: [PATCH tip/locking/core v9 5/6] locking/pvqspinlock: Allow 1  lock stealing attempt Waiman Long <waiman.long@hpe.com> - 2015-11-09 21:00 +0100
    [PATCH tip/locking/core v9 6/6] locking/pvqspinlock: Queue node adaptive spinning Waiman Long <Waiman.Long@hpe.com> - 2015-10-31 00:30 +0100
      Re: [PATCH tip/locking/core v9 6/6] locking/pvqspinlock: Queue node  adaptive spinning Peter Zijlstra <peterz@infradead.org> - 2015-11-06 16:10 +0100
        Re: [PATCH tip/locking/core v9 6/6] locking/pvqspinlock: Queue node  adaptive spinning Waiman Long <waiman.long@hpe.com> - 2015-11-06 19:00 +0100
          Re: [PATCH tip/locking/core v9 6/6] locking/pvqspinlock: Queue node  adaptive spinning Peter Zijlstra <peterz@infradead.org> - 2015-11-06 21:40 +0100
            Re: [PATCH tip/locking/core v9 6/6] locking/pvqspinlock: Queue node  adaptive spinning Waiman Long <waiman.long@hpe.com> - 2015-11-09 18:00 +0100
              Re: [PATCH tip/locking/core v9 6/6] locking/pvqspinlock: Queue node  adaptive spinning Peter Zijlstra <peterz@infradead.org> - 2015-11-09 18:40 +0100
    [PATCH tip/locking/core v9 3/6] locking/pvqspinlock, x86: Optimize PV unlock code path Waiman Long <Waiman.Long@hpe.com> - 2015-10-31 00:30 +0100
    [PATCH tip/locking/core v9 4/6] locking/pvqspinlock: Collect slowpath lock statistics Waiman Long <Waiman.Long@hpe.com> - 2015-10-31 00:30 +0100
      Re: [PATCH tip/locking/core v9 4/6] locking/pvqspinlock: Collect  slowpath lock statistics Peter Zijlstra <peterz@infradead.org> - 2015-11-02 17:50 +0100
        Re: [PATCH tip/locking/core v9 4/6] locking/pvqspinlock: Collect  slowpath lock statistics Waiman Long <waiman.long@hpe.com> - 2015-11-05 17:30 +0100
          Re: [PATCH tip/locking/core v9 4/6] locking/pvqspinlock: Collect  slowpath lock statistics Peter Zijlstra <peterz@infradead.org> - 2015-11-05 17:50 +0100
            Re: [PATCH tip/locking/core v9 4/6] locking/pvqspinlock: Collect  slowpath lock statistics Waiman Long <waiman.long@hpe.com> - 2015-11-05 18:00 +0100
              Re: [PATCH tip/locking/core v9 4/6] locking/pvqspinlock: Collect  slowpath lock statistics Peter Zijlstra <peterz@infradead.org> - 2015-11-05 18:10 +0100
                Re: [PATCH tip/locking/core v9 4/6] locking/pvqspinlock: Collect  slowpath lock statistics Waiman Long <waiman.long@hpe.com> - 2015-11-05 18:40 +0100

Page 1 of 2  [1] 2  Next page →

#1259848 — [PATCH tip/locking/core v9 0/6] locking/qspinlock: Enhance pvqspinlock

v8->v9:
 - Added a new patch 2 which tried to prefetch the cacheline of the
   next MCS node in order to reduce the MCS unlock latency when it
   was time to do the unlock.
 - Changed the slowpath statistics counters implementation in patch
   4 from atomic_t to per-cpu variables to reduce performance overhead
   and used sysfs instead of debugfs to return the consolidated counts
   and data.

v7->v8:
 - Annotated the use of each _acquire/_release variants in qspinlock.c.
 - Used the available pending bit in the lock stealing patch to disable
   lock stealing when the queue head vCPU is actively spinning on the
   lock to avoid lock starvation.
 - Restructured the lock stealing patch to reduce code duplication.
 - Verified that the waitcnt processing will be compiled away if
   QUEUED_LOCK_STAT isn't enabled.

v6->v7:
 - Removed arch/x86/include/asm/qspinlock.h from patch 1.
 - Removed the unconditional PV kick patch as it has been merged
   into tip.
 - Changed the pvstat_inc() API to add a new condition parameter.
 - Added comments and rearrange code in patch 4 to clarify where
   lock stealing happened.
 - In patch 5, removed the check for pv_wait count when deciding when
   to wait early.
 - Updated copyrights and email address.

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 attempts to prefetch the cacheline of the next MCS node to
reduce latency in the MCS unlock operation.

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

Patch 4 allows the collection of various slowpath statistics counter
data that are useful to see what is happening in the system. Per-cpu
counters are used to minimize performance overhead.

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: Use _acquire/_release versions of cmpxchg & xchg
  locking/qspinlock: prefetch next node cacheline
  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                          |    8 +
 arch/x86/include/asm/qspinlock_paravirt.h |   59 ++++++
 include/asm-generic/qspinlock.h           |    9 +-
 kernel/locking/qspinlock.c                |   99 +++++++---
 kernel/locking/qspinlock_paravirt.h       |  221 +++++++++++++++++----
 kernel/locking/qspinlock_stat.h           |  310 +++++++++++++++++++++++++++++
 6 files changed, 638 insertions(+), 68 deletions(-)
 create mode 100644 kernel/locking/qspinlock_stat.h

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

#1259849 — [PATCH tip/locking/core v9 1/6] locking/qspinlock: Use _acquire/_release versions of cmpxchg & xchg

This patch replaces the cmpxchg() and xchg() calls in the native
qspinlock code with the more relaxed _acquire or _release versions of
those calls to enable other architectures to adopt queued spinlocks
with less memory barrier performance overhead.

Signed-off-by: Waiman Long <Waiman.Long@hpe.com>
---
 include/asm-generic/qspinlock.h |    9 +++++----
 kernel/locking/qspinlock.c      |   29 ++++++++++++++++++++++++-----
 2 files changed, 29 insertions(+), 9 deletions(-)

diff --git a/include/asm-generic/qspinlock.h b/include/asm-generic/qspinlock.h
index e2aadbc..39e1cb2 100644
--- a/include/asm-generic/qspinlock.h
+++ b/include/asm-generic/qspinlock.h
@@ -12,8 +12,9 @@
  * GNU General Public License for more details.
  *
  * (C) Copyright 2013-2015 Hewlett-Packard Development Company, L.P.
+ * (C) Copyright 2015 Hewlett-Packard Enterprise Development LP
  *
- * Authors: Waiman Long <waiman.long@hp.com>
+ * Authors: Waiman Long <waiman.long@hpe.com>
  */
 #ifndef __ASM_GENERIC_QSPINLOCK_H
 #define __ASM_GENERIC_QSPINLOCK_H
@@ -62,7 +63,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 +78,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 +94,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 87e9ce6..7868418 100644
--- a/kernel/locking/qspinlock.c
+++ b/kernel/locking/qspinlock.c
@@ -14,8 +14,9 @@
  * (C) Copyright 2013-2015 Hewlett-Packard Development Company, L.P.
  * (C) Copyright 2013-2014 Red Hat, Inc.
  * (C) Copyright 2015 Intel Corp.
+ * (C) Copyright 2015 Hewlett-Packard Enterprise Development LP
  *
- * Authors: Waiman Long <waiman.long@hp.com>
+ * Authors: Waiman Long <waiman.long@hpe.com>
  *          Peter Zijlstra <peterz@infradead.org>
  */
 
@@ -176,7 +177,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 +214,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 +329,11 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)
 		if (val == new)
 			new |= _Q_PENDING_VAL;
 
-		old = atomic_cmpxchg(&lock->val, val, new);
+		/*
+		 * Acquire semantic is required here as the function may
+		 * return immediately if the lock was free.
+		 */
+		old = atomic_cmpxchg_acquire(&lock->val, val, new);
 		if (old == val)
 			break;
 
@@ -426,7 +440,12 @@ 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. At most two
+		 * iterations of this loop may be ran.
+		 */
+		old = atomic_cmpxchg_relaxed(&lock->val, val, _Q_LOCKED_VAL);
 		if (old == val)
 			goto release;	/* No contention */
 
-- 
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] | [next] | [standalone]

#1259851 — [PATCH tip/locking/core v9 2/6] locking/qspinlock: prefetch next node cacheline

A queue head CPU, after acquiring the lock, will have to notify
the next CPU in the wait queue that it has became the new queue
head. This involves loading a new cacheline from the MCS node of the
next CPU. That operation can be expensive and add to the latency of
locking operation.

This patch addes code to optmistically prefetch the next MCS node
cacheline if the next pointer is defined and it has been spinning
for the MCS lock for a while. This reduces the locking latency and
improves the system throughput.

Using a locking microbenchmark on a Haswell-EX system, this patch
can improve throughput by about 5%.

Signed-off-by: Waiman Long <Waiman.Long@hpe.com>
---
 kernel/locking/qspinlock.c |   21 +++++++++++++++++++++
 1 files changed, 21 insertions(+), 0 deletions(-)

diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c
index 7868418..c1c8a1a 100644
--- a/kernel/locking/qspinlock.c
+++ b/kernel/locking/qspinlock.c
@@ -396,6 +396,7 @@ queue:
 	 * p,*,* -> n,*,*
 	 */
 	old = xchg_tail(lock, tail);
+	next = NULL;
 
 	/*
 	 * if there was a previous node; link it and wait until reaching the
@@ -407,6 +408,16 @@ queue:
 
 		pv_wait_node(node);
 		arch_mcs_spin_lock_contended(&node->locked);
+
+		/*
+		 * While waiting for the MCS lock, the next pointer may have
+		 * been set by another lock waiter. We optimistically load
+		 * the next pointer & prefetch the cacheline for writing
+		 * to reduce latency in the upcoming MCS unlock operation.
+		 */
+		next = READ_ONCE(node->next);
+		if (next)
+			prefetchw(next);
 	}
 
 	/*
@@ -426,6 +437,15 @@ queue:
 		cpu_relax();
 
 	/*
+	 * If the next pointer is defined, we are not tail anymore.
+	 * In this case, claim the spinlock & release the MCS lock.
+	 */
+	if (next) {
+		set_locked(lock);
+		goto mcs_unlock;
+	}
+
+	/*
 	 * claim the lock:
 	 *
 	 * n,0,0 -> 0,0,1 : lock, uncontended
@@ -458,6 +478,7 @@ queue:
 	while (!(next = READ_ONCE(node->next)))
 		cpu_relax();
 
+mcs_unlock:
 	arch_mcs_spin_unlock_contended(&next->locked);
 	pv_kick_node(lock, next);
 
-- 
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] | [next] | [standalone]

#1260779 — Re: [PATCH tip/locking/core v9 2/6] locking/qspinlock: prefetch next node cacheline

On Fri, Oct 30, 2015 at 07:26:33PM -0400, Waiman Long wrote:
> A queue head CPU, after acquiring the lock, will have to notify
> the next CPU in the wait queue that it has became the new queue
> head. This involves loading a new cacheline from the MCS node of the
> next CPU. That operation can be expensive and add to the latency of
> locking operation.
> 
> This patch addes code to optmistically prefetch the next MCS node
> cacheline if the next pointer is defined and it has been spinning
> for the MCS lock for a while. This reduces the locking latency and
> improves the system throughput.
> 
> Using a locking microbenchmark on a Haswell-EX system, this patch
> can improve throughput by about 5%.

How does it affect IVB-EX (which you were testing earlier IIRC)?

> Signed-off-by: Waiman Long <Waiman.Long@hpe.com>
> ---
>  kernel/locking/qspinlock.c |   21 +++++++++++++++++++++
>  1 files changed, 21 insertions(+), 0 deletions(-)
> 
> diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c
> index 7868418..c1c8a1a 100644
> --- a/kernel/locking/qspinlock.c
> +++ b/kernel/locking/qspinlock.c
> @@ -396,6 +396,7 @@ queue:
>  	 * p,*,* -> n,*,*
>  	 */
>  	old = xchg_tail(lock, tail);
> +	next = NULL;
>  
>  	/*
>  	 * if there was a previous node; link it and wait until reaching the
> @@ -407,6 +408,16 @@ queue:
>  
>  		pv_wait_node(node);
>  		arch_mcs_spin_lock_contended(&node->locked);
> +
> +		/*
> +		 * While waiting for the MCS lock, the next pointer may have
> +		 * been set by another lock waiter. We optimistically load
> +		 * the next pointer & prefetch the cacheline for writing
> +		 * to reduce latency in the upcoming MCS unlock operation.
> +		 */
> +		next = READ_ONCE(node->next);
> +		if (next)
> +			prefetchw(next);
>  	}

OK so far I suppose. Since we already read node->locked, which is in the
same cacheline, also reading node->next isn't extra pressure. And we can
then prefetch that cacheline.

>  	/*
> @@ -426,6 +437,15 @@ queue:
>  		cpu_relax();
>  
>  	/*
> +	 * If the next pointer is defined, we are not tail anymore.
> +	 * In this case, claim the spinlock & release the MCS lock.
> +	 */
> +	if (next) {
> +		set_locked(lock);
> +		goto mcs_unlock;
> +	}
> +
> +	/*
>  	 * claim the lock:
>  	 *
>  	 * n,0,0 -> 0,0,1 : lock, uncontended
> @@ -458,6 +478,7 @@ queue:
>  	while (!(next = READ_ONCE(node->next)))
>  		cpu_relax();
>  
> +mcs_unlock:
>  	arch_mcs_spin_unlock_contended(&next->locked);
>  	pv_kick_node(lock, next);
>  

This however appears an independent optimization. Is it worth it? Would
we not already have observed a val != tail in this case? At which point
we're just adding extra code for no gain.

That is, if we observe @next, must we then not also observe val != tail?
--
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] | [next] | [standalone]

#1261044 — Re: [PATCH tip/locking/core v9 2/6] locking/qspinlock: prefetch next node cacheline

On Mon, Nov 02, 2015 at 05:36:26PM +0100, Peter Zijlstra wrote:
> On Fri, Oct 30, 2015 at 07:26:33PM -0400, Waiman Long wrote:
> > @@ -426,6 +437,15 @@ queue:
> >  		cpu_relax();
> >  
> >  	/*
> > +	 * If the next pointer is defined, we are not tail anymore.
> > +	 * In this case, claim the spinlock & release the MCS lock.
> > +	 */
> > +	if (next) {
> > +		set_locked(lock);
> > +		goto mcs_unlock;
> > +	}
> > +
> > +	/*
> >  	 * claim the lock:
> >  	 *
> >  	 * n,0,0 -> 0,0,1 : lock, uncontended
> > @@ -458,6 +478,7 @@ queue:
> >  	while (!(next = READ_ONCE(node->next)))
> >  		cpu_relax();
> >  
> > +mcs_unlock:
> >  	arch_mcs_spin_unlock_contended(&next->locked);
> >  	pv_kick_node(lock, next);
> >  
> 
> This however appears an independent optimization. Is it worth it? Would
> we not already have observed a val != tail in this case? At which point
> we're just adding extra code for no gain.
> 
> That is, if we observe @next, must we then not also observe val != tail?

Not quite; the ordering is the other way around. If we observe next we
must also observe val != tail. But its a narrow thing. Is it really
worth it?
--
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] | [next] | [standalone]

#1263417 — Re: [PATCH tip/locking/core v9 2/6] locking/qspinlock: prefetch next node cacheline

On 11/02/2015 05:54 PM, Peter Zijlstra wrote:
> On Mon, Nov 02, 2015 at 05:36:26PM +0100, Peter Zijlstra wrote:
>> On Fri, Oct 30, 2015 at 07:26:33PM -0400, Waiman Long wrote:
>>> @@ -426,6 +437,15 @@ queue:
>>>   		cpu_relax();
>>>
>>>   	/*
>>> +	 * If the next pointer is defined, we are not tail anymore.
>>> +	 * In this case, claim the spinlock&  release the MCS lock.
>>> +	 */
>>> +	if (next) {
>>> +		set_locked(lock);
>>> +		goto mcs_unlock;
>>> +	}
>>> +
>>> +	/*
>>>   	 * claim the lock:
>>>   	 *
>>>   	 * n,0,0 ->  0,0,1 : lock, uncontended
>>> @@ -458,6 +478,7 @@ queue:
>>>   	while (!(next = READ_ONCE(node->next)))
>>>   		cpu_relax();
>>>
>>> +mcs_unlock:
>>>   	arch_mcs_spin_unlock_contended(&next->locked);
>>>   	pv_kick_node(lock, next);
>>>
>> This however appears an independent optimization. Is it worth it? Would
>> we not already have observed a val != tail in this case? At which point
>> we're just adding extra code for no gain.
>>
>> That is, if we observe @next, must we then not also observe val != tail?
> Not quite; the ordering is the other way around. If we observe next we
> must also observe val != tail. But its a narrow thing. Is it really
> worth it?

If we observe next, we will observe val != tail sooner or later. It is 
not possible for it to clear the tail code in the lock. The tail xchg 
will guarantee that.

Another alternative is to do something like

+    if (!next)
          while (!(next = READ_ONCE(node->next)))
             cpu_relax();

Please let me know if that is more acceptable to you.

Cheers,
Longman
--
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] | [next] | [standalone]

#1263427 — Re: [PATCH tip/locking/core v9 2/6] locking/qspinlock: prefetch next node cacheline

On Thu, Nov 05, 2015 at 11:42:27AM -0500, Waiman Long wrote:
> If we observe next, we will observe val != tail sooner or later. It is not
> possible for it to clear the tail code in the lock. The tail xchg will
> guarantee that.
> 
> Another alternative is to do something like
> 
> +    if (!next)
>          while (!(next = READ_ONCE(node->next)))
>             cpu_relax();
> 

Yes maybe, although the main reason I fell over this was because it was
a separate change (and not mentioned in the Changelog).

Although the above would need braces (per CodingStyle), so:

	if (!next) {
		while (!(next = READ_ONCE(node->next)))
			cpu_relax();
	}



--
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] | [next] | [standalone]

#1263369 — Re: [PATCH tip/locking/core v9 2/6] locking/qspinlock: prefetch next node cacheline

On 11/02/2015 11:36 AM, Peter Zijlstra wrote:
> On Fri, Oct 30, 2015 at 07:26:33PM -0400, Waiman Long wrote:
>> A queue head CPU, after acquiring the lock, will have to notify
>> the next CPU in the wait queue that it has became the new queue
>> head. This involves loading a new cacheline from the MCS node of the
>> next CPU. That operation can be expensive and add to the latency of
>> locking operation.
>>
>> This patch addes code to optmistically prefetch the next MCS node
>> cacheline if the next pointer is defined and it has been spinning
>> for the MCS lock for a while. This reduces the locking latency and
>> improves the system throughput.
>>
>> Using a locking microbenchmark on a Haswell-EX system, this patch
>> can improve throughput by about 5%.
> How does it affect IVB-EX (which you were testing earlier IIRC)?

My testing on IVB-EX indicated that if the critical section is really 
short, the change may actually slow thing a bit in some cases. However, 
when the critical section is long enough that the prefetch overhead can 
be hidden within the lock acquisition loop, there will be a performance 
boost.

>> Signed-off-by: Waiman Long<Waiman.Long@hpe.com>
>> ---
>>   kernel/locking/qspinlock.c |   21 +++++++++++++++++++++
>>   1 files changed, 21 insertions(+), 0 deletions(-)
>>
>> diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c
>> index 7868418..c1c8a1a 100644
>> --- a/kernel/locking/qspinlock.c
>> +++ b/kernel/locking/qspinlock.c
>> @@ -396,6 +396,7 @@ queue:
>>   	 * p,*,* ->  n,*,*
>>   	 */
>>   	old = xchg_tail(lock, tail);
>> +	next = NULL;
>>
>>   	/*
>>   	 * if there was a previous node; link it and wait until reaching the
>> @@ -407,6 +408,16 @@ queue:
>>
>>   		pv_wait_node(node);
>>   		arch_mcs_spin_lock_contended(&node->locked);
>> +
>> +		/*
>> +		 * While waiting for the MCS lock, the next pointer may have
>> +		 * been set by another lock waiter. We optimistically load
>> +		 * the next pointer&  prefetch the cacheline for writing
>> +		 * to reduce latency in the upcoming MCS unlock operation.
>> +		 */
>> +		next = READ_ONCE(node->next);
>> +		if (next)
>> +			prefetchw(next);
>>   	}
> OK so far I suppose. Since we already read node->locked, which is in the
> same cacheline, also reading node->next isn't extra pressure. And we can
> then prefetch that cacheline.
>
>>   	/*
>> @@ -426,6 +437,15 @@ queue:
>>   		cpu_relax();
>>
>>   	/*
>> +	 * If the next pointer is defined, we are not tail anymore.
>> +	 * In this case, claim the spinlock&  release the MCS lock.
>> +	 */
>> +	if (next) {
>> +		set_locked(lock);
>> +		goto mcs_unlock;
>> +	}
>> +
>> +	/*
>>   	 * claim the lock:
>>   	 *
>>   	 * n,0,0 ->  0,0,1 : lock, uncontended
>> @@ -458,6 +478,7 @@ queue:
>>   	while (!(next = READ_ONCE(node->next)))
>>   		cpu_relax();
>>
>> +mcs_unlock:
>>   	arch_mcs_spin_unlock_contended(&next->locked);
>>   	pv_kick_node(lock, next);
>>
> This however appears an independent optimization. Is it worth it? Would
> we not already have observed a val != tail in this case? At which point
> we're just adding extra code for no gain.
>
> That is, if we observe @next, must we then not also observe val != tail?

Observing next implies val != tail, but the reverse may not be true. The 
branch is done before we observe val != tail. Yes, it is an optimization 
to avoid reading node->next again if we have already observed next. I 
have observed a very minor performance boost with that change without 
the prefetch.

Cheers,
Longman

--
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] | [next] | [standalone]

#1263407 — Re: [PATCH tip/locking/core v9 2/6] locking/qspinlock: prefetch next node cacheline

On Thu, Nov 05, 2015 at 11:06:48AM -0500, Waiman Long wrote:

> >How does it affect IVB-EX (which you were testing earlier IIRC)?
> 
> My testing on IVB-EX indicated that if the critical section is really short,
> the change may actually slow thing a bit in some cases. However, when the
> critical section is long enough that the prefetch overhead can be hidden
> within the lock acquisition loop, there will be a performance boost.

> >>@@ -426,6 +437,15 @@ queue:
> >>  		cpu_relax();
> >>
> >>  	/*
> >>+	 * If the next pointer is defined, we are not tail anymore.
> >>+	 * In this case, claim the spinlock&  release the MCS lock.
> >>+	 */
> >>+	if (next) {
> >>+		set_locked(lock);
> >>+		goto mcs_unlock;
> >>+	}
> >>+
> >>+	/*
> >>  	 * claim the lock:
> >>  	 *
> >>  	 * n,0,0 ->  0,0,1 : lock, uncontended
> >>@@ -458,6 +478,7 @@ queue:
> >>  	while (!(next = READ_ONCE(node->next)))
> >>  		cpu_relax();
> >>
> >>+mcs_unlock:
> >>  	arch_mcs_spin_unlock_contended(&next->locked);
> >>  	pv_kick_node(lock, next);
> >>
> >This however appears an independent optimization. Is it worth it? Would
> >we not already have observed a val != tail in this case? At which point
> >we're just adding extra code for no gain.
> >
> >That is, if we observe @next, must we then not also observe val != tail?
> 
> Observing next implies val != tail, but the reverse may not be true. The
> branch is done before we observe val != tail. Yes, it is an optimization to
> avoid reading node->next again if we have already observed next. I have
> observed a very minor performance boost with that change without the
> prefetch.

This is all good information to have in the Changelog. And since these
are two independent changes, two patches would have been the right
format.
--
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] | [next] | [standalone]

#1263425 — Re: [PATCH tip/locking/core v9 2/6] locking/qspinlock: prefetch next node cacheline

On 11/05/2015 11:39 AM, Peter Zijlstra wrote:
> On Thu, Nov 05, 2015 at 11:06:48AM -0500, Waiman Long wrote:
>
>>> How does it affect IVB-EX (which you were testing earlier IIRC)?
>> My testing on IVB-EX indicated that if the critical section is really short,
>> the change may actually slow thing a bit in some cases. However, when the
>> critical section is long enough that the prefetch overhead can be hidden
>> within the lock acquisition loop, there will be a performance boost.
>>>> @@ -426,6 +437,15 @@ queue:
>>>>   		cpu_relax();
>>>>
>>>>   	/*
>>>> +	 * If the next pointer is defined, we are not tail anymore.
>>>> +	 * In this case, claim the spinlock&   release the MCS lock.
>>>> +	 */
>>>> +	if (next) {
>>>> +		set_locked(lock);
>>>> +		goto mcs_unlock;
>>>> +	}
>>>> +
>>>> +	/*
>>>>   	 * claim the lock:
>>>>   	 *
>>>>   	 * n,0,0 ->   0,0,1 : lock, uncontended
>>>> @@ -458,6 +478,7 @@ queue:
>>>>   	while (!(next = READ_ONCE(node->next)))
>>>>   		cpu_relax();
>>>>
>>>> +mcs_unlock:
>>>>   	arch_mcs_spin_unlock_contended(&next->locked);
>>>>   	pv_kick_node(lock, next);
>>>>
>>> This however appears an independent optimization. Is it worth it? Would
>>> we not already have observed a val != tail in this case? At which point
>>> we're just adding extra code for no gain.
>>>
>>> That is, if we observe @next, must we then not also observe val != tail?
>> Observing next implies val != tail, but the reverse may not be true. The
>> branch is done before we observe val != tail. Yes, it is an optimization to
>> avoid reading node->next again if we have already observed next. I have
>> observed a very minor performance boost with that change without the
>> prefetch.
> This is all good information to have in the Changelog. And since these
> are two independent changes, two patches would have been the right
> format.

Yep, I will separate it into 2 patches and include additional 
information in the changelog.

Cheers,
Longman
--
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] | [next] | [standalone]

#1259852 — [PATCH tip/locking/core v9 5/6] locking/pvqspinlock: Allow 1 lock stealing attempt

This patch allows one attempt for the lock waiter to steal the lock
when entering the PV slowpath. To prevent lock starvation, the pending
bit will be set by the queue head vCPU when it is in the active lock
spinning loop to disable any lock stealing attempt.  This helps to
reduce the performance penalty caused by lock waiter preemption while
not having much of the downsides of a real unfair lock.

The pv_wait_head() function was renamed as pv_wait_head_lock() as it
was modified to acquire the lock before returning. This is necessary
because of possible lock stealing attempts from other tasks.

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          |   52 ++++++++++-------
 kernel/locking/qspinlock_paravirt.h |  111 ++++++++++++++++++++++++++++-------
 kernel/locking/qspinlock_stat.h     |   16 +++++
 3 files changed, 136 insertions(+), 43 deletions(-)

diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c
index c1c8a1a..39c6a43 100644
--- a/kernel/locking/qspinlock.c
+++ b/kernel/locking/qspinlock.c
@@ -251,15 +251,16 @@ 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 u32  __pv_wait_head_lock(struct qspinlock *lock,
+						struct mcs_spinlock *node)
+						{ return 0; }
 
 #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_lock	__pv_wait_head_lock
 
 #ifdef CONFIG_PARAVIRT_SPINLOCKS
 #define queued_spin_lock_slowpath	native_queued_spin_lock_slowpath
@@ -431,35 +432,44 @@ queue:
 	 * sequentiality; this is because the set_locked() function below
 	 * does not imply a full barrier.
 	 *
+	 * The PV pv_wait_head_lock function, if active, will acquire the lock
+	 * and return a non-zero value. So we have to skip the
+	 * smp_load_acquire() call. As the next PV queue head hasn't been
+	 * designated yet, there is no way for the locked value to become
+	 * _Q_SLOW_VAL. So both the redundant set_locked() and the
+	 * atomic_cmpxchg_relaxed() calls will be safe. The cost of the
+	 * redundant set_locked() call below should be negligible, too.
+	 *
+	 * If PV isn't active, 0 will be returned instead.
 	 */
-	pv_wait_head(lock, node);
-	while ((val = smp_load_acquire(&lock->val.counter)) & _Q_LOCKED_PENDING_MASK)
-		cpu_relax();
+	val = pv_wait_head_lock(lock, node);
+	if (!val) {
+		while ((val = smp_load_acquire(&lock->val.counter))
+				& _Q_LOCKED_PENDING_MASK)
+			cpu_relax();
+		/*
+		 * Claim the lock now:
+		 *
+		 * 0,0 -> 0,1
+		 */
+		set_locked(lock);
+		val |= _Q_LOCKED_VAL;
+	}
 
 	/*
 	 * If the next pointer is defined, we are not tail anymore.
-	 * In this case, claim the spinlock & release the MCS lock.
 	 */
-	if (next) {
-		set_locked(lock);
+	if (next)
 		goto mcs_unlock;
-	}
 
 	/*
-	 * claim the lock:
-	 *
-	 * n,0,0 -> 0,0,1 : lock, uncontended
-	 * *,0,0 -> *,0,1 : lock, contended
-	 *
 	 * If the queue head is the only one in the queue (lock value == tail),
-	 * clear the tail code and grab the lock. Otherwise, we only need
-	 * to grab the lock.
+	 * we have to clear the tail code.
 	 */
 	for (;;) {
-		if (val != tail) {
-			set_locked(lock);
+		if ((val & _Q_TAIL_MASK) != tail)
 			break;
-		}
+
 		/*
 		 * The smp_load_acquire() call above has provided the necessary
 		 * acquire semantics required for locking. At most two
@@ -502,7 +512,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_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 aaeeefb..24ccc9f 100644
--- a/kernel/locking/qspinlock_paravirt.h
+++ b/kernel/locking/qspinlock_paravirt.h
@@ -41,6 +41,56 @@ struct pv_node {
 };
 
 /*
+ * Allow one unfair trylock when entering the PV slowpath when the pending
+ * bit isn't set to reduce the performance impact of lock waiter preemption
+ *
+ * By replacing the regular queued_spin_trylock() with the function below,
+ * it 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.
+ */
+#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;
+
+	return !(atomic_read(&lock->val) & _Q_LOCKED_PENDING_MASK) &&
+		(cmpxchg(&l->locked, 0, _Q_LOCKED_VAL) == 0);
+}
+
+/*
+ * The pending bit is used by the queue head vCPU to indicate that it
+ * is actively spinning on the lock and no lock stealing is allowed.
+ */
+#if _Q_PENDING_BITS == 8
+static __always_inline void clear_pending(struct qspinlock *lock)
+{
+	struct __qspinlock *l = (void *)lock;
+
+	WRITE_ONCE(l->pending, 0);
+}
+
+static __always_inline void set_pending(struct qspinlock *lock)
+{
+	struct __qspinlock *l = (void *)lock;
+
+	WRITE_ONCE(l->pending, 1);
+}
+#else /* _Q_PENDING_BITS == 8 */
+static __always_inline void clear_pending(struct qspinlock *lock)
+{
+	atomic_clear_mask(&lock->val, _Q_PENDING_MASK);
+}
+
+static __always_inline void set_pending(struct qspinlock *lock)
+{
+	atomic_set_mask(&lock->val, _Q_PENDING_MASK);
+}
+#endif /* _Q_PENDING_BITS == 8 */
+
+/*
  * Include queued spinlock statistics code
  */
 #include "qspinlock_stat.h"
@@ -202,8 +252,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_lock() knows to not also try
+		 * to hash this lock.
 		 */
 		cmpxchg(&pn->state, vcpu_halted, vcpu_running);
 
@@ -227,8 +277,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_lock(), this avoids a
+ * wake/sleep cycle.
  */
 static void pv_kick_node(struct qspinlock *lock, struct mcs_spinlock *node)
 {
@@ -257,10 +308,13 @@ 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.
+ * Wait for l->locked to become clear and acquire the lock;
+ * halt the vcpu after a short spin.
  * __pv_queued_spin_unlock() will wake us.
+ *
+ * The current value of the lock will be returned for additional processing.
  */
-static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node)
+static u32 pv_wait_head_lock(struct qspinlock *lock, struct mcs_spinlock *node)
 {
 	struct pv_node *pn = (struct pv_node *)node;
 	struct __qspinlock *l = (void *)lock;
@@ -276,11 +330,24 @@ static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node)
 		lp = (struct qspinlock **)1;
 
 	for (;; waitcnt++) {
+		/*
+		 * Set the pending bit in the active lock spinning loop to
+		 * disable lock stealing. However, the pending bit check in
+		 * pv_queued_spin_trylock_unfair() and the setting/clearing
+		 * of pending bit here aren't memory barriers. So a cmpxchg()
+		 * is used to acquire the lock to be sure.
+		 */
+		set_pending(lock);
 		for (loop = SPIN_THRESHOLD; loop; loop--) {
-			if (!READ_ONCE(l->locked))
-				return;
+			if (!READ_ONCE(l->locked) &&
+			   (cmpxchg(&l->locked, 0, _Q_LOCKED_VAL) == 0)) {
+				clear_pending(lock);
+				goto gotlock;
+			}
 			cpu_relax();
 		}
+		clear_pending(lock);
+
 
 		if (!lp) { /* ONCE */
 			lp = pv_hash(lock, pn);
@@ -296,36 +363,36 @@ 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;
 			}
 		}
 		qstat_inc(qstat_pv_wait_head, true);
 		qstat_inc(qstat_pv_wait_again, waitcnt);
 		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.
 		 */
-		qstat_inc(qstat_pv_spurious_wakeup, true);
+		qstat_inc(qstat_pv_spurious_wakeup, READ_ONCE(l->locked));
 	}
 
 	/*
-	 * 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.
+	 * The cmpxchg() or xchg() call before coming here provides the
+	 * acquire semantics for locking.
 	 */
+gotlock:
+	return (u32)atomic_read(&lock->val);
 }
 
 /*
@@ -350,7 +417,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_lock() setting _Q_SLOW_VAL.
 	 */
 	smp_rmb();
 
diff --git a/kernel/locking/qspinlock_stat.h b/kernel/locking/qspinlock_stat.h
index 16b84b2..1d87065 100644
--- a/kernel/locking/qspinlock_stat.h
+++ b/kernel/locking/qspinlock_stat.h
@@ -22,6 +22,7 @@
  *   pv_kick_wake	- # of vCPU kicks used for computing pv_latency_wake
  *   pv_latency_kick	- average latency (ns) of vCPU kick operation
  *   pv_latency_wake	- average latency (ns) from vCPU kick to wakeup
+ *   pv_lock_stealing	- # of lock stealing operations
  *   pv_spurious_wakeup	- # of spurious wakeups
  *   pv_wait_again	- # of vCPU wait's that happened after a vCPU kick
  *   pv_wait_head	- # of vCPU wait's at the queue head
@@ -43,6 +44,7 @@ enum qlock_stats {
 	qstat_pv_kick_wake,
 	qstat_pv_latency_kick,
 	qstat_pv_latency_wake,
+	qstat_pv_lock_stealing,
 	qstat_pv_spurious_wakeup,
 	qstat_pv_wait_again,
 	qstat_pv_wait_head,
@@ -66,6 +68,7 @@ static const char * const qstat_names[qstat_num + 1] = {
 	[qstat_pv_spurious_wakeup] = "pv_spurious_wakeup",
 	[qstat_pv_latency_kick]	   = "pv_latency_kick",
 	[qstat_pv_latency_wake]    = "pv_latency_wake",
+	[qstat_pv_lock_stealing]   = "pv_lock_stealing",
 	[qstat_pv_wait_again]      = "pv_wait_again",
 	[qstat_pv_wait_head]       = "pv_wait_head",
 	[qstat_pv_wait_node]       = "pv_wait_node",
@@ -283,6 +286,19 @@ static inline void __pv_wait(u8 *ptr, u8 val)
 #define pv_kick(c)	__pv_kick(c)
 #define pv_wait(p, v)	__pv_wait(p, v)
 
+/*
+ * PV unfair trylock count tracking function
+ */
+static inline int qstat_trylock_unfair(struct qspinlock *lock)
+{
+	int ret = pv_queued_spin_trylock_unfair(lock);
+
+	qstat_inc(qstat_pv_lock_stealing, ret);
+	return ret;
+}
+#undef  queued_spin_trylock
+#define queued_spin_trylock(l)	qstat_trylock_unfair(l)
+
 #else /* CONFIG_QUEUED_LOCK_STAT */
 
 static inline void qstat_inc(enum qlock_stats stat, bool cond)	{ }
-- 
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] | [next] | [standalone]

#1264072 — Re: [PATCH tip/locking/core v9 5/6] locking/pvqspinlock: Allow 1 lock stealing attempt

On Fri, Oct 30, 2015 at 07:26:36PM -0400, Waiman Long wrote:

> @@ -431,35 +432,44 @@ queue:
>  	 * sequentiality; this is because the set_locked() function below
>  	 * does not imply a full barrier.
>  	 *
> +	 * The PV pv_wait_head_lock function, if active, will acquire the lock
> +	 * and return a non-zero value. So we have to skip the
> +	 * smp_load_acquire() call. As the next PV queue head hasn't been
> +	 * designated yet, there is no way for the locked value to become
> +	 * _Q_SLOW_VAL. So both the redundant set_locked() and the
> +	 * atomic_cmpxchg_relaxed() calls will be safe. The cost of the
> +	 * redundant set_locked() call below should be negligible, too.
> +	 *
> +	 * If PV isn't active, 0 will be returned instead.
>  	 */
> -	pv_wait_head(lock, node);
> -	while ((val = smp_load_acquire(&lock->val.counter)) & _Q_LOCKED_PENDING_MASK)
> -		cpu_relax();
> +	val = pv_wait_head_lock(lock, node);
> +	if (!val) {
> +		while ((val = smp_load_acquire(&lock->val.counter))
> +				& _Q_LOCKED_PENDING_MASK)
> +			cpu_relax();
> +		/*
> +		 * Claim the lock now:
> +		 *
> +		 * 0,0 -> 0,1
> +		 */
> +		set_locked(lock);
> +		val |= _Q_LOCKED_VAL;
> +	}
>  
>  	/*
>  	 * If the next pointer is defined, we are not tail anymore.
> -	 * In this case, claim the spinlock & release the MCS lock.
>  	 */
> -	if (next) {
> -		set_locked(lock);
> +	if (next)
>  		goto mcs_unlock;
> -	}
>  
>  	/*
> -	 * claim the lock:
> -	 *
> -	 * n,0,0 -> 0,0,1 : lock, uncontended
> -	 * *,0,0 -> *,0,1 : lock, contended
> -	 *
>  	 * If the queue head is the only one in the queue (lock value == tail),
> -	 * clear the tail code and grab the lock. Otherwise, we only need
> -	 * to grab the lock.
> +	 * we have to clear the tail code.
>  	 */
>  	for (;;) {
> -		if (val != tail) {
> -			set_locked(lock);
> +		if ((val & _Q_TAIL_MASK) != tail)
>  			break;
> -		}
> +
>  		/*
>  		 * The smp_load_acquire() call above has provided the necessary
>  		 * acquire semantics required for locking. At most two

*urgh*, last time we had:

+	if (pv_wait_head_or_steal())
+		goto stolen;
	while ((val = smp_load_acquire(&lock->val.counter)) & _Q_LOCKED_PENDING_MASK)
		cpu_relax();

	...

+stolen:
	while (!(next = READ_ONCE(node->next)))
		cpu_relax();

	...

Now you completely overhaul the native code.. what happened?

> -static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node)
> +static u32 pv_wait_head_lock(struct qspinlock *lock, struct mcs_spinlock *node)
>  {
>  	struct pv_node *pn = (struct pv_node *)node;
>  	struct __qspinlock *l = (void *)lock;
> @@ -276,11 +330,24 @@ static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node)
>  		lp = (struct qspinlock **)1;
>  
>  	for (;; waitcnt++) {
> +		/*
> +		 * Set the pending bit in the active lock spinning loop to
> +		 * disable lock stealing. However, the pending bit check in
> +		 * pv_queued_spin_trylock_unfair() and the setting/clearing
> +		 * of pending bit here aren't memory barriers. So a cmpxchg()
> +		 * is used to acquire the lock to be sure.
> +		 */
> +		set_pending(lock);

OK, so we mark ourselves 'pending' such that a new lock() will not steal
and is forced to queue behind us.

>  		for (loop = SPIN_THRESHOLD; loop; loop--) {
> -			if (!READ_ONCE(l->locked))
> -				return;
> +			if (!READ_ONCE(l->locked) &&
> +			   (cmpxchg(&l->locked, 0, _Q_LOCKED_VAL) == 0)) {
> +				clear_pending(lock);
> +				goto gotlock;

Would not: cmpxchg(&l->locked_pending, _Q_PENDING_VAL, _Q_LOCKED_VAL),
make sense to avoid the clear_pending() call?

> +			}
>  			cpu_relax();
>  		}
> +		clear_pending(lock);
> +


--
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] | [next] | [standalone]

#1264194 — Re: [PATCH tip/locking/core v9 5/6] locking/pvqspinlock: Allow 1 lock stealing attempt

On 11/06/2015 09:50 AM, Peter Zijlstra wrote:
> On Fri, Oct 30, 2015 at 07:26:36PM -0400, Waiman Long wrote:
>
>> @@ -431,35 +432,44 @@ queue:
>>   	 * sequentiality; this is because the set_locked() function below
>>   	 * does not imply a full barrier.
>>   	 *
>> +	 * The PV pv_wait_head_lock function, if active, will acquire the lock
>> +	 * and return a non-zero value. So we have to skip the
>> +	 * smp_load_acquire() call. As the next PV queue head hasn't been
>> +	 * designated yet, there is no way for the locked value to become
>> +	 * _Q_SLOW_VAL. So both the redundant set_locked() and the
>> +	 * atomic_cmpxchg_relaxed() calls will be safe. The cost of the
>> +	 * redundant set_locked() call below should be negligible, too.
>> +	 *
>> +	 * If PV isn't active, 0 will be returned instead.
>>   	 */
>> -	pv_wait_head(lock, node);
>> -	while ((val = smp_load_acquire(&lock->val.counter))&  _Q_LOCKED_PENDING_MASK)
>> -		cpu_relax();
>> +	val = pv_wait_head_lock(lock, node);
>> +	if (!val) {
>> +		while ((val = smp_load_acquire(&lock->val.counter))
>> +				&  _Q_LOCKED_PENDING_MASK)
>> +			cpu_relax();
>> +		/*
>> +		 * Claim the lock now:
>> +		 *
>> +		 * 0,0 ->  0,1
>> +		 */
>> +		set_locked(lock);
>> +		val |= _Q_LOCKED_VAL;
>> +	}
>>
>>   	/*
>>   	 * If the next pointer is defined, we are not tail anymore.
>> -	 * In this case, claim the spinlock&  release the MCS lock.
>>   	 */
>> -	if (next) {
>> -		set_locked(lock);
>> +	if (next)
>>   		goto mcs_unlock;
>> -	}
>>
>>   	/*
>> -	 * claim the lock:
>> -	 *
>> -	 * n,0,0 ->  0,0,1 : lock, uncontended
>> -	 * *,0,0 ->  *,0,1 : lock, contended
>> -	 *
>>   	 * If the queue head is the only one in the queue (lock value == tail),
>> -	 * clear the tail code and grab the lock. Otherwise, we only need
>> -	 * to grab the lock.
>> +	 * we have to clear the tail code.
>>   	 */
>>   	for (;;) {
>> -		if (val != tail) {
>> -			set_locked(lock);
>> +		if ((val&  _Q_TAIL_MASK) != tail)
>>   			break;
>> -		}
>> +
>>   		/*
>>   		 * The smp_load_acquire() call above has provided the necessary
>>   		 * acquire semantics required for locking. At most two
> *urgh*, last time we had:
>
> +	if (pv_wait_head_or_steal())
> +		goto stolen;
> 	while ((val = smp_load_acquire(&lock->val.counter))&  _Q_LOCKED_PENDING_MASK)
> 		cpu_relax();
>
> 	...
>
> +stolen:
> 	while (!(next = READ_ONCE(node->next)))
> 		cpu_relax();
>
> 	...
>
> Now you completely overhaul the native code.. what happened?

I want to reuse as much of the existing native code as possible instead 
of duplicating that in the PV function. The only difference now is that 
the PV function will acquire that lock. Semantically, I don't want to 
call the lock acquisition as lock stealing as the queue head is entitled 
to get the lock next. I can rename pv_queued_spin_trylock_unfair() to 
pv_queued_spin_steal_lock() to emphasize the fact that this is the 
routine where lock stealing happens.

>> -static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node)
>> +static u32 pv_wait_head_lock(struct qspinlock *lock, struct mcs_spinlock *node)
>>   {
>>   	struct pv_node *pn = (struct pv_node *)node;
>>   	struct __qspinlock *l = (void *)lock;
>> @@ -276,11 +330,24 @@ static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node)
>>   		lp = (struct qspinlock **)1;
>>
>>   	for (;; waitcnt++) {
>> +		/*
>> +		 * Set the pending bit in the active lock spinning loop to
>> +		 * disable lock stealing. However, the pending bit check in
>> +		 * pv_queued_spin_trylock_unfair() and the setting/clearing
>> +		 * of pending bit here aren't memory barriers. So a cmpxchg()
>> +		 * is used to acquire the lock to be sure.
>> +		 */
>> +		set_pending(lock);
> OK, so we mark ourselves 'pending' such that a new lock() will not steal
> and is forced to queue behind us.

Yes, this ensures that lock starvation will not happens.

>
>>   		for (loop = SPIN_THRESHOLD; loop; loop--) {
>> -			if (!READ_ONCE(l->locked))
>> -				return;
>> +			if (!READ_ONCE(l->locked)&&
>> +			   (cmpxchg(&l->locked, 0, _Q_LOCKED_VAL) == 0)) {
>> +				clear_pending(lock);
>> +				goto gotlock;
> Would not: cmpxchg(&l->locked_pending, _Q_PENDING_VAL, _Q_LOCKED_VAL),
> make sense to avoid the clear_pending() call?

I can combine cmpxchg() and clear_pending() into a new helper function 
as its implementation will differ depends on NR_CPUS.

Cheers,
Longman
--
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] | [next] | [standalone]

#1265892 — Re: [PATCH tip/locking/core v9 5/6] locking/pvqspinlock: Allow 1 lock stealing attempt

On Fri, Nov 06, 2015 at 12:47:49PM -0500, Waiman Long wrote:
> On 11/06/2015 09:50 AM, Peter Zijlstra wrote:
> >*urgh*, last time we had:
> >
> >+	if (pv_wait_head_or_steal())
> >+		goto stolen;
> >	while ((val = smp_load_acquire(&lock->val.counter))&  _Q_LOCKED_PENDING_MASK)
> >		cpu_relax();
> >
> >	...
> >
> >+stolen:
> >	while (!(next = READ_ONCE(node->next)))
> >		cpu_relax();
> >
> >	...
> >
> >Now you completely overhaul the native code.. what happened?
> 
> I want to reuse as much of the existing native code as possible instead of
> duplicating that in the PV function. The only difference now is that the PV
> function will acquire that lock.

Right; and while I doubt it hurts the native case (you did benchmark it
I hope), I'm not too keen on the end result code wise.

Maybe just keep the above.

> Semantically, I don't want to call the lock
> acquisition as lock stealing as the queue head is entitled to get the lock
> next. 

Fair enough I suppose, pv_wait_head_or_lock() then?

> I can rename pv_queued_spin_trylock_unfair() to
> pv_queued_spin_steal_lock() to emphasize the fact that this is the routine
> where lock stealing happens.

OK.

--
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] | [next] | [standalone]

#1265976 — Re: [PATCH tip/locking/core v9 5/6] locking/pvqspinlock: Allow 1 lock stealing attempt

On 11/09/2015 12:29 PM, Peter Zijlstra wrote:
> On Fri, Nov 06, 2015 at 12:47:49PM -0500, Waiman Long wrote:
>> On 11/06/2015 09:50 AM, Peter Zijlstra wrote:
>>> *urgh*, last time we had:
>>>
>>> +	if (pv_wait_head_or_steal())
>>> +		goto stolen;
>>> 	while ((val = smp_load_acquire(&lock->val.counter))&   _Q_LOCKED_PENDING_MASK)
>>> 		cpu_relax();
>>>
>>> 	...
>>>
>>> +stolen:
>>> 	while (!(next = READ_ONCE(node->next)))
>>> 		cpu_relax();
>>>
>>> 	...
>>>
>>> Now you completely overhaul the native code.. what happened?
>> I want to reuse as much of the existing native code as possible instead of
>> duplicating that in the PV function. The only difference now is that the PV
>> function will acquire that lock.
> Right; and while I doubt it hurts the native case (you did benchmark it
> I hope), I'm not too keen on the end result code wise.
>
> Maybe just keep the above.

I can jump over the smp_load_acquire() for PV instead of adding an 
additional if block. For the native code, the only thing that was added 
was an additional masking of val with _Q_TAIL_MASK which I don't think 
will make too much of a difference.
>
>> Semantically, I don't want to call the lock
>> acquisition as lock stealing as the queue head is entitled to get the lock
>> next.
> Fair enough I suppose, pv_wait_head_or_lock() then?
>

I am fine with that name.

>> I can rename pv_queued_spin_trylock_unfair() to
>> pv_queued_spin_steal_lock() to emphasize the fact that this is the routine
>> where lock stealing happens.
> OK.
>

Cheers,
Longman
--
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] | [next] | [standalone]

#1259854 — [PATCH tip/locking/core v9 6/6] locking/pvqspinlock: Queue node adaptive spinning

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 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 |   45 +++++++++++++++++++++++++++++++++-
 kernel/locking/qspinlock_stat.h     |    3 ++
 3 files changed, 49 insertions(+), 4 deletions(-)

diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c
index 39c6a43..685c14e 100644
--- a/kernel/locking/qspinlock.c
+++ b/kernel/locking/qspinlock.c
@@ -248,7 +248,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 u32  __pv_wait_head_lock(struct qspinlock *lock,
@@ -407,7 +408,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 24ccc9f..df2dfd5 100644
--- a/kernel/locking/qspinlock_paravirt.h
+++ b/kernel/locking/qspinlock_paravirt.h
@@ -23,6 +23,19 @@
 #define _Q_SLOW_VAL	(3U << _Q_LOCKED_OFFSET)
 
 /*
+ * Queue Node Adaptive Spinning
+ *
+ * A queue node vCPU will stop spinning if the vCPU in the previous node is
+ * not running. 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.
  */
@@ -202,6 +215,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 *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)
@@ -219,17 +246,23 @@ 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;
 
 	/* waitcnt processing will be compiled out if !QUEUED_LOCK_STAT */
 	for (;; waitcnt++) {
-		for (loop = SPIN_THRESHOLD; loop; loop--) {
+		for (wait_early = false, loop = SPIN_THRESHOLD; loop; loop--) {
 			if (READ_ONCE(node->locked))
 				return;
+			if (pv_wait_early(pp, loop)) {
+				wait_early = true;
+				break;
+			}
 			cpu_relax();
 		}
 
@@ -247,6 +280,7 @@ static void pv_wait_node(struct mcs_spinlock *node)
 		if (!READ_ONCE(node->locked)) {
 			qstat_inc(qstat_pv_wait_node, true);
 			qstat_inc(qstat_pv_wait_again, waitcnt);
+			qstat_inc(qstat_pv_wait_early, wait_early);
 			pv_wait(&pn->state, vcpu_halted);
 		}
 
@@ -331,6 +365,12 @@ static u32 pv_wait_head_lock(struct qspinlock *lock, struct mcs_spinlock *node)
 
 	for (;; waitcnt++) {
 		/*
+		 * Set correct vCPU state to be used by queue node wait-early
+		 * mechanism.
+		 */
+		WRITE_ONCE(pn->state, vcpu_running);
+
+		/*
 		 * Set the pending bit in the active lock spinning loop to
 		 * disable lock stealing. However, the pending bit check in
 		 * pv_queued_spin_trylock_unfair() and the setting/clearing
@@ -374,6 +414,7 @@ static u32 pv_wait_head_lock(struct qspinlock *lock, struct mcs_spinlock *node)
 				goto gotlock;
 			}
 		}
+		WRITE_ONCE(pn->state, vcpu_halted);
 		qstat_inc(qstat_pv_wait_head, true);
 		qstat_inc(qstat_pv_wait_again, waitcnt);
 		pv_wait(&l->locked, _Q_SLOW_VAL);
diff --git a/kernel/locking/qspinlock_stat.h b/kernel/locking/qspinlock_stat.h
index 1d87065..937aef3 100644
--- a/kernel/locking/qspinlock_stat.h
+++ b/kernel/locking/qspinlock_stat.h
@@ -25,6 +25,7 @@
  *   pv_lock_stealing	- # of lock stealing operations
  *   pv_spurious_wakeup	- # of spurious wakeups
  *   pv_wait_again	- # of vCPU wait's that happened after a vCPU kick
+ *   pv_wait_early	- # of early vCPU wait's
  *   pv_wait_head	- # of vCPU wait's at the queue head
  *   pv_wait_node	- # of vCPU wait's at a non-head queue node
  *
@@ -47,6 +48,7 @@ enum qlock_stats {
 	qstat_pv_lock_stealing,
 	qstat_pv_spurious_wakeup,
 	qstat_pv_wait_again,
+	qstat_pv_wait_early,
 	qstat_pv_wait_head,
 	qstat_pv_wait_node,
 	qstat_num,	/* Total number of statistics counters */
@@ -70,6 +72,7 @@ static const char * const qstat_names[qstat_num + 1] = {
 	[qstat_pv_latency_wake]    = "pv_latency_wake",
 	[qstat_pv_lock_stealing]   = "pv_lock_stealing",
 	[qstat_pv_wait_again]      = "pv_wait_again",
+	[qstat_pv_wait_early]      = "pv_wait_early",
 	[qstat_pv_wait_head]       = "pv_wait_head",
 	[qstat_pv_wait_node]       = "pv_wait_node",
 	[qstat_reset_cnts]         = "reset_counters",
-- 
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] | [next] | [standalone]

#1264074 — Re: [PATCH tip/locking/core v9 6/6] locking/pvqspinlock: Queue node adaptive spinning

On Fri, Oct 30, 2015 at 07:26:37PM -0400, Waiman Long wrote:
> +++ b/kernel/locking/qspinlock_paravirt.h
> @@ -23,6 +23,19 @@
>  #define _Q_SLOW_VAL	(3U << _Q_LOCKED_OFFSET)
>  
>  /*
> + * Queue Node Adaptive Spinning
> + *
> + * A queue node vCPU will stop spinning if the vCPU in the previous node is
> + * not running. 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.
>   */
> @@ -202,6 +215,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 *prev, int loop)
> +{
> +
> +	if ((loop & PV_PREV_CHECK_MASK) != 0)
> +		return false;
> +
> +	return READ_ONCE(prev->state) != vcpu_running;
> +}

So it appears to me the sole purpose of PV_PREV_CHECK_MASK it to avoid
touching the prev->state cacheline too hard. Yet that is not mentioned
anywhere above.


> +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;
>  
>  	/* waitcnt processing will be compiled out if !QUEUED_LOCK_STAT */
>  	for (;; waitcnt++) {
> -		for (loop = SPIN_THRESHOLD; loop; loop--) {
> +		for (wait_early = false, loop = SPIN_THRESHOLD; loop; loop--) {
>  			if (READ_ONCE(node->locked))
>  				return;
> +			if (pv_wait_early(pp, loop)) {
> +				wait_early = true;
> +				break;
> +			}
>  			cpu_relax();
>  		}
>  

So if prev points to another node, it will never see vcpu_running. Was
that fully intended?

FYI, I think I've now seen all patches ;-)
--
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] | [next] | [standalone]

#1264206 — Re: [PATCH tip/locking/core v9 6/6] locking/pvqspinlock: Queue node adaptive spinning

On 11/06/2015 10:01 AM, Peter Zijlstra wrote:
> On Fri, Oct 30, 2015 at 07:26:37PM -0400, Waiman Long wrote:
>> +++ b/kernel/locking/qspinlock_paravirt.h
>> @@ -23,6 +23,19 @@
>>   #define _Q_SLOW_VAL	(3U<<  _Q_LOCKED_OFFSET)
>>
>>   /*
>> + * Queue Node Adaptive Spinning
>> + *
>> + * A queue node vCPU will stop spinning if the vCPU in the previous node is
>> + * not running. 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.
>>    */
>> @@ -202,6 +215,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 *prev, int loop)
>> +{
>> +
>> +	if ((loop&  PV_PREV_CHECK_MASK) != 0)
>> +		return false;
>> +
>> +	return READ_ONCE(prev->state) != vcpu_running;
>> +}
> So it appears to me the sole purpose of PV_PREV_CHECK_MASK it to avoid
> touching the prev->state cacheline too hard. Yet that is not mentioned
> anywhere above.

Yes, that is true. I will add a comment to that effect.

>
>> +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;
>>
>>   	/* waitcnt processing will be compiled out if !QUEUED_LOCK_STAT */
>>   	for (;; waitcnt++) {
>> -		for (loop = SPIN_THRESHOLD; loop; loop--) {
>> +		for (wait_early = false, loop = SPIN_THRESHOLD; loop; loop--) {
>>   			if (READ_ONCE(node->locked))
>>   				return;
>> +			if (pv_wait_early(pp, loop)) {
>> +				wait_early = true;
>> +				break;
>> +			}
>>   			cpu_relax();
>>   		}
>>
> So if prev points to another node, it will never see vcpu_running. Was
> that fully intended?

I had added code in pv_wait_head_or_lock to set the state appropriately 
for the queue head vCPU.

         for (;; waitcnt++) {
                 /*
+                * Set correct vCPU state to be used by queue node 
wait-early
+                * mechanism.
+                */
+               WRITE_ONCE(pn->state, vcpu_running);
+
+               /*
                  * Set the pending bit in the active lock spinning loop to
                  * disable lock stealing. However, the pending bit check in
                  * pv_queued_spin_trylock_unfair() and the setting/clearing
@@ -374,6 +414,7 @@ static u32 pv_wait_head_lock(struct qspinlock *lock, 
struct mcs_spinlock *node)
                                 goto gotlock;
                         }
                 }
+               WRITE_ONCE(pn->state, vcpu_halted);

> FYI, I think I've now seen all patches ;-)

Thanks for the review. I will work on fixing the issues you identified 
and issue a new patch series next week.

Cheers,
Longman
--
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] | [next] | [standalone]

#1264458 — Re: [PATCH tip/locking/core v9 6/6] locking/pvqspinlock: Queue node adaptive spinning

On Fri, Nov 06, 2015 at 12:54:06PM -0500, Waiman Long wrote:
> >>+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;
> >>
> >>  	/* waitcnt processing will be compiled out if !QUEUED_LOCK_STAT */
> >>  	for (;; waitcnt++) {
> >>-		for (loop = SPIN_THRESHOLD; loop; loop--) {
> >>+		for (wait_early = false, loop = SPIN_THRESHOLD; loop; loop--) {
> >>  			if (READ_ONCE(node->locked))
> >>  				return;
> >>+			if (pv_wait_early(pp, loop)) {
> >>+				wait_early = true;
> >>+				break;
> >>+			}
> >>  			cpu_relax();
> >>  		}
> >>
> >So if prev points to another node, it will never see vcpu_running. Was
> >that fully intended?
> 
> I had added code in pv_wait_head_or_lock to set the state appropriately for
> the queue head vCPU.

Yes, but that's the head, for nodes we'll always have halted or hashed.
--
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] | [next] | [standalone]

#1265860 — Re: [PATCH tip/locking/core v9 6/6] locking/pvqspinlock: Queue node adaptive spinning

On 11/06/2015 03:37 PM, Peter Zijlstra wrote:
> On Fri, Nov 06, 2015 at 12:54:06PM -0500, Waiman Long wrote:
>>>> +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;
>>>>
>>>>   	/* waitcnt processing will be compiled out if !QUEUED_LOCK_STAT */
>>>>   	for (;; waitcnt++) {
>>>> -		for (loop = SPIN_THRESHOLD; loop; loop--) {
>>>> +		for (wait_early = false, loop = SPIN_THRESHOLD; loop; loop--) {
>>>>   			if (READ_ONCE(node->locked))
>>>>   				return;
>>>> +			if (pv_wait_early(pp, loop)) {
>>>> +				wait_early = true;
>>>> +				break;
>>>> +			}
>>>>   			cpu_relax();
>>>>   		}
>>>>
>>> So if prev points to another node, it will never see vcpu_running. Was
>>> that fully intended?
>> I had added code in pv_wait_head_or_lock to set the state appropriately for
>> the queue head vCPU.
> Yes, but that's the head, for nodes we'll always have halted or hashed.

The node state was initialized to be vcpu_running. In pv_wait_node(), it 
will be changed to vcpu_halted before sleeping and back to vcpu_running 
after that. So it is not true that it is either halted or hashed.

In case, it was changed to vcpu_hashed, it will be changed back to 
vcpu_running in pv_wait_head_lock before entering the active spinning 
loop. There are definitely a small amount of time where the node state 
does not reflect the actual vCPU state, but that is the best we can do 
so far.

Cheers,
Longman
--
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] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | linux.kernel

csiph-web