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

Groups > linux.kernel > #1223030 > unrolled thread

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

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  [PATCH v6 5/6] locking/pvqspinlock: Allow 1 lock stealing attempt Waiman Long <Waiman.Long@hpe.com> - 2015-09-11 20:40 +0200
    Re: [PATCH v6 5/6] locking/pvqspinlock: Allow 1 lock stealing attempt Peter Zijlstra <peterz@infradead.org> - 2015-09-14 16:00 +0200
      Re: [PATCH v6 5/6] locking/pvqspinlock: Allow 1 lock stealing attempt Waiman Long <waiman.long@hpe.com> - 2015-09-14 21:10 +0200
    Re: [PATCH v6 5/6] locking/pvqspinlock: Allow 1 lock stealing attempt Peter Zijlstra <peterz@infradead.org> - 2015-09-14 16:10 +0200
      Re: [PATCH v6 5/6] locking/pvqspinlock: Allow 1 lock stealing attempt Waiman Long <waiman.long@hpe.com> - 2015-09-14 21:20 +0200
        Re: [PATCH v6 5/6] locking/pvqspinlock: Allow 1 lock stealing attempt Waiman Long <waiman.long@hpe.com> - 2015-09-14 21:40 +0200
        Re: [PATCH v6 5/6] locking/pvqspinlock: Allow 1 lock stealing attempt Peter Zijlstra <peterz@infradead.org> - 2015-09-15 10:30 +0200
          Re: [PATCH v6 5/6] locking/pvqspinlock: Allow 1 lock stealing attempt Waiman Long <waiman.long@hpe.com> - 2015-09-15 17:30 +0200
            Re: [PATCH v6 5/6] locking/pvqspinlock: Allow 1 lock stealing attempt Peter Zijlstra <peterz@infradead.org> - 2015-09-16 17:10 +0200
              Re: [PATCH v6 5/6] locking/pvqspinlock: Allow 1 lock stealing attempt Waiman Long <waiman.long@hpe.com> - 2015-09-17 17:10 +0200
    Re: [PATCH v6 5/6] locking/pvqspinlock: Allow 1 lock stealing attempt Peter Zijlstra <peterz@infradead.org> - 2015-09-14 16:10 +0200
      Re: [PATCH v6 5/6] locking/pvqspinlock: Allow 1 lock stealing attempt Waiman Long <waiman.long@hpe.com> - 2015-09-14 21:20 +0200

#1223030 — [PATCH v6 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.  This helps to reduce the performance
penalty caused by lock waiter preemption while not having much of
the downsides of a real unfair lock.

Linux kernel builds were run in KVM guest on an 8-socket, 4
cores/socket Westmere-EX system and a 4-socket, 8 cores/socket
Haswell-EX system. Both systems are configured to have 32 physical
CPUs. The kernel build times before and after the patch were:

                    Westmere                    Haswell
  Patch         32 vCPUs    48 vCPUs    32 vCPUs    48 vCPUs
  -----         --------    --------    --------    --------
  Before patch   3m15.6s    10m56.1s     1m44.1s     5m29.1s
  After patch    3m02.3s     5m00.2s     1m43.7s     3m03.5s

For the overcommited case (48 vCPUs), this patch is able to reduce
kernel build time by more than 54% for Westmere and 44% for Haswell.

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

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

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

#1224176

On Fri, Sep 11, 2015 at 02:37:37PM -0400, Waiman Long wrote:
> +#define queued_spin_trylock(l)	pv_queued_spin_trylock_unfair(l)
> +static inline bool pv_queued_spin_trylock_unfair(struct qspinlock *lock)
> +{
> +	struct __qspinlock *l = (void *)lock;
> +
> +	if (READ_ONCE(l->locked))
> +		return 0;
> +	/*
> +	 * Wait a bit here to ensure that an actively spinning vCPU has a fair
> +	 * chance of getting the lock.
> +	 */
> +	cpu_relax();
> +
> +	return cmpxchg(&l->locked, 0, _Q_LOCKED_VAL) == 0;
> +}

> +static inline int pvstat_trylock_unfair(struct qspinlock *lock)
> +{
> +	int ret = pv_queued_spin_trylock_unfair(lock);
> +
> +	if (ret)
> +		pvstat_inc(pvstat_utrylock);
> +	return ret;
> +}
> +#undef  queued_spin_trylock
> +#define queued_spin_trylock(l)	pvstat_trylock_unfair(l)

These aren't actually ever used...
--
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]

#1224414

On 09/14/2015 09:57 AM, Peter Zijlstra wrote:
> On Fri, Sep 11, 2015 at 02:37:37PM -0400, Waiman Long wrote:
>> +#define queued_spin_trylock(l)	pv_queued_spin_trylock_unfair(l)
>> +static inline bool pv_queued_spin_trylock_unfair(struct qspinlock *lock)
>> +{
>> +	struct __qspinlock *l = (void *)lock;
>> +
>> +	if (READ_ONCE(l->locked))
>> +		return 0;
>> +	/*
>> +	 * Wait a bit here to ensure that an actively spinning vCPU has a fair
>> +	 * chance of getting the lock.
>> +	 */
>> +	cpu_relax();
>> +
>> +	return cmpxchg(&l->locked, 0, _Q_LOCKED_VAL) == 0;
>> +}
>> +static inline int pvstat_trylock_unfair(struct qspinlock *lock)
>> +{
>> +	int ret = pv_queued_spin_trylock_unfair(lock);
>> +
>> +	if (ret)
>> +		pvstat_inc(pvstat_utrylock);
>> +	return ret;
>> +}
>> +#undef  queued_spin_trylock
>> +#define queued_spin_trylock(l)	pvstat_trylock_unfair(l)
> These aren't actually ever used...

The pvstat_trylock_unfair() is within the CONFIG_QUEUED_LOCK_STAT block. 
It will only be activated when the config parameter is set. Otherwise, 
pv_queued_spin_trylock_unfair() will be used without any counting.

It is used provide count of how many unfair trylock has successfully got 
the lock.

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

#1224184

On Fri, Sep 11, 2015 at 02:37:37PM -0400, Waiman Long wrote:
> This patch allows one attempt for the lock waiter to steal the lock
> when entering the PV slowpath.  This helps to reduce the performance
> penalty caused by lock waiter preemption while not having much of
> the downsides of a real unfair lock.

> @@ -415,8 +458,12 @@ static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node)
>  
>  	for (;; waitcnt++) {
>  		for (loop = SPIN_THRESHOLD; loop; loop--) {
> -			if (!READ_ONCE(l->locked))
> -				return;
> +			/*
> +			 * Try to acquire the lock when it is free.
> +			 */
> +			if (!READ_ONCE(l->locked) &&
> +			   (cmpxchg(&l->locked, 0, _Q_LOCKED_VAL) == 0))
> +				goto gotlock;
>  			cpu_relax();
>  		}
>  

This isn't _once_, this is once per 'wakeup'. And note that interrupts
unrelated to the kick can equally wake the vCPU up.

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

#1224416

On 09/14/2015 10:00 AM, Peter Zijlstra wrote:
> On Fri, Sep 11, 2015 at 02:37:37PM -0400, Waiman Long wrote:
>> This patch allows one attempt for the lock waiter to steal the lock
>> when entering the PV slowpath.  This helps to reduce the performance
>> penalty caused by lock waiter preemption while not having much of
>> the downsides of a real unfair lock.
>> @@ -415,8 +458,12 @@ static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node)
>>
>>   	for (;; waitcnt++) {
>>   		for (loop = SPIN_THRESHOLD; loop; loop--) {
>> -			if (!READ_ONCE(l->locked))
>> -				return;
>> +			/*
>> +			 * Try to acquire the lock when it is free.
>> +			 */
>> +			if (!READ_ONCE(l->locked)&&
>> +			   (cmpxchg(&l->locked, 0, _Q_LOCKED_VAL) == 0))
>> +				goto gotlock;
>>   			cpu_relax();
>>   		}
>>
> This isn't _once_, this is once per 'wakeup'. And note that interrupts
> unrelated to the kick can equally wake the vCPU up.
>

Oh! There is a minor bug that I shouldn't need to have a second 
READ_ONCE() call here.

As this is the queue head, finding the lock free entitles the vCPU to 
own the lock. However, because of lock stealing, I can't just write a 1 
to the lock and assume thing is all set. That is why I need to use 
cmpxchg() to make sure that the queue head vCPU can actually get the 
lock without the lock stolen underneath. I don't count that as lock 
stealing as it is the rightful owner of the lock.

I am sorry that I should have added a comment to clarify that. Will do 
so in the next update.

 > void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)
 > {
 >     :
 >         /*
 >         * We touched a (possibly) cold cacheline in the per-cpu queue 
node;
 >         * attempt the trylock once more in the hope someone let go 
while we
 >         * weren't watching.
 >         */
 >        if (queued_spin_trylock(lock))
 >                goto release;

This is the only place where I consider lock stealing happens. Again, I 
should have a comment in pv_queued_spin_trylock_unfair() to say where it 
will be called.

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

#1224425

On 09/14/2015 03:15 PM, Waiman Long wrote:
> On 09/14/2015 10:00 AM, Peter Zijlstra wrote:
>> On Fri, Sep 11, 2015 at 02:37:37PM -0400, Waiman Long wrote:
>>> This patch allows one attempt for the lock waiter to steal the lock
>>> when entering the PV slowpath.  This helps to reduce the performance
>>> penalty caused by lock waiter preemption while not having much of
>>> the downsides of a real unfair lock.
>>> @@ -415,8 +458,12 @@ static void pv_wait_head(struct qspinlock 
>>> *lock, struct mcs_spinlock *node)
>>>
>>>       for (;; waitcnt++) {
>>>           for (loop = SPIN_THRESHOLD; loop; loop--) {
>>> -            if (!READ_ONCE(l->locked))
>>> -                return;
>>> +            /*
>>> +             * Try to acquire the lock when it is free.
>>> +             */
>>> +            if (!READ_ONCE(l->locked)&&
>>> +               (cmpxchg(&l->locked, 0, _Q_LOCKED_VAL) == 0))
>>> +                goto gotlock;
>>>               cpu_relax();
>>>           }
>>>
>> This isn't _once_, this is once per 'wakeup'. And note that interrupts
>> unrelated to the kick can equally wake the vCPU up.
>>
>
> Oh! There is a minor bug that I shouldn't need to have a second 
> READ_ONCE() call here.

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

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

#1224754

On Mon, Sep 14, 2015 at 03:15:20PM -0400, Waiman Long wrote:
> On 09/14/2015 10:00 AM, Peter Zijlstra wrote:
> >On Fri, Sep 11, 2015 at 02:37:37PM -0400, Waiman Long wrote:
> >>This patch allows one attempt for the lock waiter to steal the lock
                      ^^^

> >>when entering the PV slowpath.  This helps to reduce the performance
> >>penalty caused by lock waiter preemption while not having much of
> >>the downsides of a real unfair lock.

> >>@@ -415,8 +458,12 @@ static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node)
> >>
> >>  	for (;; waitcnt++) {
> >>  		for (loop = SPIN_THRESHOLD; loop; loop--) {
> >>-			if (!READ_ONCE(l->locked))
> >>-				return;
> >>+			/*
> >>+			 * Try to acquire the lock when it is free.
> >>+			 */
> >>+			if (!READ_ONCE(l->locked)&&
> >>+			   (cmpxchg(&l->locked, 0, _Q_LOCKED_VAL) == 0))
> >>+				goto gotlock;
> >>  			cpu_relax();
> >>  		}
> >>
> >This isn't _once_, this is once per 'wakeup'. And note that interrupts
> >unrelated to the kick can equally wake the vCPU up.

> > void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)
> > {
> >     :
> >         /*
> >         * We touched a (possibly) cold cacheline in the per-cpu queue node;
> >         * attempt the trylock once more in the hope someone let go while we
> >         * weren't watching.
> >         */
> >        if (queued_spin_trylock(lock))
> >                goto release;
> 
> This is the only place where I consider lock stealing happens. Again, I
> should have a comment in pv_queued_spin_trylock_unfair() to say where it
> will be called.

But you're not adding that..

What you did add is a steal in pv_wait_head(), and its not even once per
pv_wait_head, its inside the spin loop (I read it wrong yesterday).

So that makes the entire Changelog complete crap. There isn't _one_
attempt, and there is absolutely no fairness left.
--
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]

#1225306

On 09/15/2015 04:24 AM, Peter Zijlstra wrote:
> On Mon, Sep 14, 2015 at 03:15:20PM -0400, Waiman Long wrote:
>> On 09/14/2015 10:00 AM, Peter Zijlstra wrote:
>>> On Fri, Sep 11, 2015 at 02:37:37PM -0400, Waiman Long wrote:
>>>> This patch allows one attempt for the lock waiter to steal the lock
>                        ^^^
>
>>>> when entering the PV slowpath.  This helps to reduce the performance
>>>> penalty caused by lock waiter preemption while not having much of
>>>> the downsides of a real unfair lock.
>>>> @@ -415,8 +458,12 @@ static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node)
>>>>
>>>>   	for (;; waitcnt++) {
>>>>   		for (loop = SPIN_THRESHOLD; loop; loop--) {
>>>> -			if (!READ_ONCE(l->locked))
>>>> -				return;
>>>> +			/*
>>>> +			 * Try to acquire the lock when it is free.
>>>> +			 */
>>>> +			if (!READ_ONCE(l->locked)&&
>>>> +			   (cmpxchg(&l->locked, 0, _Q_LOCKED_VAL) == 0))
>>>> +				goto gotlock;
>>>>   			cpu_relax();
>>>>   		}
>>>>
>>> This isn't _once_, this is once per 'wakeup'. And note that interrupts
>>> unrelated to the kick can equally wake the vCPU up.
>>> void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)
>>> {
>>>      :
>>>          /*
>>>          * We touched a (possibly) cold cacheline in the per-cpu queue node;
>>>          * attempt the trylock once more in the hope someone let go while we
>>>          * weren't watching.
>>>          */
>>>         if (queued_spin_trylock(lock))
>>>                 goto release;
>> This is the only place where I consider lock stealing happens. Again, I
>> should have a comment in pv_queued_spin_trylock_unfair() to say where it
>> will be called.
> But you're not adding that..
>
> What you did add is a steal in pv_wait_head(), and its not even once per
> pv_wait_head, its inside the spin loop (I read it wrong yesterday).
>
> So that makes the entire Changelog complete crap. There isn't _one_
> attempt, and there is absolutely no fairness left.

Only the queue head vCPU will be in pv_wait_head() spinning to acquire 
the lock. The other vCPUs in the queue will still be spinning on their 
MCS nodes. The only competitors for the lock are those vCPUs that have 
just entered slowpath and execute the queued_spin_trylock() function 
once before being queued. That is what I mean by each task having only 
one chance of stealing the lock. Maybe the following code changes can 
make this point clearer.

Cheers,
Longman

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

--- a/kernel/locking/qspinlock_paravirt.h
+++ b/kernel/locking/qspinlock_paravirt.h
@@ -59,7 +59,8 @@ struct pv_node {
  /*
   * Allow one unfair trylock when entering the PV slowpath to reduce the
   * performance impact of lock waiter preemption (either explicitly via
- * pv_wait or implicitly via PLE).
+ * pv_wait or implicitly via PLE). This function will be called once when
+ * a lock waiter enter the slowpath before being queued.
   *
   * A little bit of unfairness here can improve performance without many
   * of the downsides of a real unfair lock.
@@ -72,8 +73,8 @@ static inline bool 
pv_queued_spin_trylock_unfair(struct qspinl
         if (READ_ONCE(l->locked))
                 return 0;
         /*
-        * Wait a bit here to ensure that an actively spinning vCPU has 
a fair
-        * chance of getting the lock.
+        * Wait a bit here to ensure that an actively spinning queue 
head vCPU
+        * has a fair chance of getting the lock.
          */
         cpu_relax();

@@ -504,14 +505,23 @@ static int pv_wait_head_and_lock(struct qspinlock 
*lock,
                  */
                 WRITE_ONCE(pn->state, vcpu_running);

-               for (loop = SPIN_THRESHOLD; loop; loop--) {
+               loop = SPIN_THRESHOLD;
+               while (loop) {
                         /*
-                        * Try to acquire the lock when it is free.
+                        * Spin until the lock is free
                          */
-                       if (!READ_ONCE(l->locked) &&
-                          (cmpxchg(&l->locked, 0, _Q_LOCKED_VAL) == 0))
+                       for (; loop && READ_ONCE(l->locked); loop--)
+                               cpu_relax();
+                       /*
+                        * Seeing the lock is free, this queue head vCPU is
+                        * the rightful next owner of the lock. However, the
+                        * lock may have just been stolen by another 
task which
+                        * has entered the slowpath. So we need to use 
atomic
+                        * operation to make sure that we really get the 
lock.
+                        * Otherwise, we have to wait again.
+                        */
+                       if (cmpxchg(&l->locked, 0, _Q_LOCKED_VAL) == 0)
                                 goto gotlock;
-                       cpu_relax();
                 }

                 if (!lp) { /* ONCE */


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

#1226178

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

> Only the queue head vCPU will be in pv_wait_head() spinning to acquire the
> lock.

But what will guarantee fwd progress for the lock that is the head?

Suppose CPU0 becomes head and enters the /* claim the lock */ loop.

Then CPU1 comes in, steals it in pv_wait_head(). CPU1 releases, CPU1
re-acquires and _again_ steals in pv_wait_head(), etc..

All the while CPU0 doesn't go anywhere.

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

#1227099

On 09/16/2015 11:01 AM, Peter Zijlstra wrote:
> On Tue, Sep 15, 2015 at 11:29:14AM -0400, Waiman Long wrote:
>
>> Only the queue head vCPU will be in pv_wait_head() spinning to acquire the
>> lock.
> But what will guarantee fwd progress for the lock that is the head?
>
> Suppose CPU0 becomes head and enters the /* claim the lock */ loop.
>
> Then CPU1 comes in, steals it in pv_wait_head(). CPU1 releases, CPU1
> re-acquires and _again_ steals in pv_wait_head(), etc..
>
> All the while CPU0 doesn't go anywhere.
>

That can't happen. For a given lock, there can only be 1 queue head 
spinning on the lock at any instance in time. If CPU0 was the head, 
another CPU could not become head until CPU0 got the lock and pass the 
MCS lock bit to the next one in the queue. As I said in earlier mail, 
the only place where lock stealing can happen is in the 
pv_queued_spin_trylock_unfair() function where I purposely inserted a 
cpu_relax() to allow an actively spinning queue head CPU a better chance 
of getting the lock. Once a CPU enters the queue. It won't try to 
acquire the lock until it becomes the head and there is one and only one 
head.

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

#1224188

On Fri, Sep 11, 2015 at 02:37:37PM -0400, Waiman Long wrote:
> This patch allows one attempt for the lock waiter to steal the lock
> when entering the PV slowpath.  This helps to reduce the performance
> penalty caused by lock waiter preemption while not having much of
> the downsides of a real unfair lock.


> @@ -416,7 +414,8 @@ queue:
>  	 * does not imply a full barrier.
>  	 *
>  	 */

If it really were once, like the Changelog says it is, then you could
have simply added:

	if (pv_try_steal_lock(...))
		goto release;

here, and not wrecked pv_wait_head() like you did. Note that if you do
it like this, you also do not need to play games with the hash, because
you'll never get into that situation.

> -	pv_wait_head(lock, node);
> +	if (pv_wait_head_and_lock(lock, node, tail))
> +		goto release;
>  	while ((val = smp_load_acquire(&lock->val.counter)) & _Q_LOCKED_PENDING_MASK)
>  		cpu_relax();
>  
--
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]

#1224417

On 09/14/2015 10:04 AM, Peter Zijlstra wrote:
> On Fri, Sep 11, 2015 at 02:37:37PM -0400, Waiman Long wrote:
>> This patch allows one attempt for the lock waiter to steal the lock
>> when entering the PV slowpath.  This helps to reduce the performance
>> penalty caused by lock waiter preemption while not having much of
>> the downsides of a real unfair lock.
>
>> @@ -416,7 +414,8 @@ queue:
>>   	 * does not imply a full barrier.
>>   	 *
>>   	 */
> If it really were once, like the Changelog says it is, then you could
> have simply added:
>
> 	if (pv_try_steal_lock(...))
> 		goto release;

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

> here, and not wrecked pv_wait_head() like you did. Note that if you do
> it like this, you also do not need to play games with the hash, because
> you'll never get into that situation.
>
>> -	pv_wait_head(lock, node);
>> +	if (pv_wait_head_and_lock(lock, node, tail))
>> +		goto release;
>>   	while ((val = smp_load_acquire(&lock->val.counter))&  _Q_LOCKED_PENDING_MASK)
>>   		cpu_relax();
>>

Because we need to use atomic op to get the lock, we can't use the 
native logic to do the acquire. I know it is kind of hacky, but I don't 
have a good alternative here.

Cheers,
Longman
--
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