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

Groups > linux.kernel > #1407654 > unrolled thread

[PATCH 1/2] locking/pvqspinlock: Fix missed PV wakeup problem

Started byWaiman Long <Waiman.Long@hpe.com>
First post2016-05-26 20:30 +0200
Last post2016-05-27 21:30 +0200
Articles 3 — 3 participants

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 1/2] locking/pvqspinlock: Fix missed PV wakeup problem Waiman Long <Waiman.Long@hpe.com> - 2016-05-26 20:30 +0200
    Re: [PATCH 1/2] locking/pvqspinlock: Fix missed PV wakeup problem Boqun Feng <boqun.feng@gmail.com> - 2016-05-27 09:50 +0200
      Re: [PATCH 1/2] locking/pvqspinlock: Fix missed PV wakeup problem Waiman Long <waiman.long@hpe.com> - 2016-05-27 21:30 +0200

#1407654 — [PATCH 1/2] locking/pvqspinlock: Fix missed PV wakeup problem

FromWaiman Long <Waiman.Long@hpe.com>
Date2016-05-26 20:30 +0200
Subject[PATCH 1/2] locking/pvqspinlock: Fix missed PV wakeup problem
Message-ID<rD8cF-1ms-5@gated-at.bofh.it>
Currently, calling pv_hash() and setting _Q_SLOW_VAL is only
done once for any pv_node. It is either in pv_kick_node() or in
pv_wait_head_or_lock(). Because of lock stealing, a pv_kick'ed node is
not guaranteed to get the lock before the spinning threshold expires
and has to call pv_wait() again. As a result, the new lock holder
won't see _Q_SLOW_VAL and so won't wake up the sleeping vCPU.

This patch fixes this missed PV wakeup problem by allowing multiple
_Q_SLOW_VAL settings within pv_wait_head_or_lock() and matching each
successful setting of _Q_SLOW_VAL to a pv_hash() call.

Reported-by: Pan Xinhui <xinhui.pan@linux.vnet.ibm.com>
Signed-off-by: Waiman Long <Waiman.Long@hpe.com>
---
 kernel/locking/qspinlock_paravirt.h |   48 ++++++++++++++++++++++------------
 1 files changed, 31 insertions(+), 17 deletions(-)

diff --git a/kernel/locking/qspinlock_paravirt.h b/kernel/locking/qspinlock_paravirt.h
index 21ede57..452d06d 100644
--- a/kernel/locking/qspinlock_paravirt.h
+++ b/kernel/locking/qspinlock_paravirt.h
@@ -369,12 +369,16 @@ static void pv_kick_node(struct qspinlock *lock, struct mcs_spinlock *node)
 	/*
 	 * Put the lock into the hash table and set the _Q_SLOW_VAL.
 	 *
-	 * As this is the same vCPU that will check the _Q_SLOW_VAL value and
-	 * the hash table later on at unlock time, no atomic instruction is
-	 * needed.
+	 * It is very unlikely that this will race with the _Q_SLOW_VAL setting
+	 * in pv_wait_head_or_lock(). However, we use cmpxchg() here to be
+	 * sure that we won't do a double pv_hash().
+	 *
+	 * As it is the lock holder, it won't race with
+	 * __pv_queued_spin_unlock().
 	 */
-	WRITE_ONCE(l->locked, _Q_SLOW_VAL);
-	(void)pv_hash(lock, pn);
+	if (likely(cmpxchg(&l->locked, _Q_LOCKED_VAL, _Q_SLOW_VAL)
+			== _Q_LOCKED_VAL))
+		pv_hash(lock, pn);
 }
 
 /*
@@ -389,18 +393,10 @@ pv_wait_head_or_lock(struct qspinlock *lock, struct mcs_spinlock *node)
 {
 	struct pv_node *pn = (struct pv_node *)node;
 	struct __qspinlock *l = (void *)lock;
-	struct qspinlock **lp = NULL;
 	int waitcnt = 0;
 	int loop;
 
 	/*
-	 * If pv_kick_node() already advanced our state, we don't need to
-	 * insert ourselves into the hash table anymore.
-	 */
-	if (READ_ONCE(pn->state) == vcpu_hashed)
-		lp = (struct qspinlock **)1;
-
-	/*
 	 * Tracking # of slowpath locking operations
 	 */
 	qstat_inc(qstat_pv_lock_slowpath, true);
@@ -422,11 +418,19 @@ pv_wait_head_or_lock(struct qspinlock *lock, struct mcs_spinlock *node)
 				goto gotlock;
 			cpu_relax();
 		}
-		clear_pending(lock);
 
+		/*
+		 * Make sure the lock value check below is executed after
+		 * all the previous loads.
+		 */
+		smp_rmb();
 
-		if (!lp) { /* ONCE */
-			lp = pv_hash(lock, pn);
+		/*
+		 * Set _Q_SLOW_VAL and hash the PV node, if necessary.
+		 */
+		if (READ_ONCE(l->locked) != _Q_SLOW_VAL) {
+			struct qspinlock **lp = pv_hash(lock, pn);
+			u8 locked;
 
 			/*
 			 * We must hash before setting _Q_SLOW_VAL, such that
@@ -439,7 +443,8 @@ pv_wait_head_or_lock(struct qspinlock *lock, struct mcs_spinlock *node)
 			 *
 			 * Matches the smp_rmb() in __pv_queued_spin_unlock().
 			 */
-			if (xchg(&l->locked, _Q_SLOW_VAL) == 0) {
+			locked = xchg(&l->locked, _Q_SLOW_VAL);
+			if (locked == 0) {
 				/*
 				 * The lock was free and now we own the lock.
 				 * Change the lock value back to _Q_LOCKED_VAL
@@ -447,9 +452,18 @@ pv_wait_head_or_lock(struct qspinlock *lock, struct mcs_spinlock *node)
 				 */
 				WRITE_ONCE(l->locked, _Q_LOCKED_VAL);
 				WRITE_ONCE(*lp, NULL);
+				clear_pending(lock);
 				goto gotlock;
+			} else if (unlikely(locked == _Q_SLOW_VAL)) {
+				/*
+				 * Racing with pv_kick_node(), need to undo
+				 * the pv_hash().
+				 */
+				WRITE_ONCE(*lp, NULL);
 			}
 		}
+		clear_pending(lock);	/* Enable lock stealing */
+
 		WRITE_ONCE(pn->state, vcpu_halted);
 		qstat_inc(qstat_pv_wait_head, true);
 		qstat_inc(qstat_pv_wait_again, waitcnt);
-- 
1.7.1

[toc] | [next] | [standalone]

#1407880

FromBoqun Feng <boqun.feng@gmail.com>
Date2016-05-27 09:50 +0200
Message-ID<rDkGR-yd-5@gated-at.bofh.it>
In reply to#1407654

[Multipart message — attachments visible in raw view] — view raw

Hi Waiman,

On Thu, May 26, 2016 at 02:21:57PM -0400, Waiman Long wrote:
> Currently, calling pv_hash() and setting _Q_SLOW_VAL is only
> done once for any pv_node. It is either in pv_kick_node() or in
> pv_wait_head_or_lock(). Because of lock stealing, a pv_kick'ed node is
> not guaranteed to get the lock before the spinning threshold expires
> and has to call pv_wait() again. As a result, the new lock holder
> won't see _Q_SLOW_VAL and so won't wake up the sleeping vCPU.
> 
> This patch fixes this missed PV wakeup problem by allowing multiple
> _Q_SLOW_VAL settings within pv_wait_head_or_lock() and matching each
> successful setting of _Q_SLOW_VAL to a pv_hash() call.
> 
> Reported-by: Pan Xinhui <xinhui.pan@linux.vnet.ibm.com>
> Signed-off-by: Waiman Long <Waiman.Long@hpe.com>
> ---
>  kernel/locking/qspinlock_paravirt.h |   48 ++++++++++++++++++++++------------
>  1 files changed, 31 insertions(+), 17 deletions(-)
> 
> diff --git a/kernel/locking/qspinlock_paravirt.h b/kernel/locking/qspinlock_paravirt.h
> index 21ede57..452d06d 100644
> --- a/kernel/locking/qspinlock_paravirt.h
> +++ b/kernel/locking/qspinlock_paravirt.h
> @@ -369,12 +369,16 @@ static void pv_kick_node(struct qspinlock *lock, struct mcs_spinlock *node)
>  	/*
>  	 * Put the lock into the hash table and set the _Q_SLOW_VAL.
>  	 *
> -	 * As this is the same vCPU that will check the _Q_SLOW_VAL value and
> -	 * the hash table later on at unlock time, no atomic instruction is
> -	 * needed.
> +	 * It is very unlikely that this will race with the _Q_SLOW_VAL setting
> +	 * in pv_wait_head_or_lock(). However, we use cmpxchg() here to be
> +	 * sure that we won't do a double pv_hash().
> +	 *
> +	 * As it is the lock holder, it won't race with
> +	 * __pv_queued_spin_unlock().
>  	 */
> -	WRITE_ONCE(l->locked, _Q_SLOW_VAL);
> -	(void)pv_hash(lock, pn);
> +	if (likely(cmpxchg(&l->locked, _Q_LOCKED_VAL, _Q_SLOW_VAL)
> +			== _Q_LOCKED_VAL))
> +		pv_hash(lock, pn);
>  }
>  
>  /*
> @@ -389,18 +393,10 @@ pv_wait_head_or_lock(struct qspinlock *lock, struct mcs_spinlock *node)
>  {
>  	struct pv_node *pn = (struct pv_node *)node;
>  	struct __qspinlock *l = (void *)lock;
> -	struct qspinlock **lp = NULL;
>  	int waitcnt = 0;
>  	int loop;
>  
>  	/*
> -	 * If pv_kick_node() already advanced our state, we don't need to
> -	 * insert ourselves into the hash table anymore.
> -	 */
> -	if (READ_ONCE(pn->state) == vcpu_hashed)
> -		lp = (struct qspinlock **)1;
> -
> -	/*
>  	 * Tracking # of slowpath locking operations
>  	 */
>  	qstat_inc(qstat_pv_lock_slowpath, true);
> @@ -422,11 +418,19 @@ pv_wait_head_or_lock(struct qspinlock *lock, struct mcs_spinlock *node)
>  				goto gotlock;
>  			cpu_relax();
>  		}
> -		clear_pending(lock);
>  
> +		/*
> +		 * Make sure the lock value check below is executed after
> +		 * all the previous loads.
> +		 */
> +		smp_rmb();
>  
> -		if (!lp) { /* ONCE */
> -			lp = pv_hash(lock, pn);
> +		/*
> +		 * Set _Q_SLOW_VAL and hash the PV node, if necessary.
> +		 */
> +		if (READ_ONCE(l->locked) != _Q_SLOW_VAL) {
> +			struct qspinlock **lp = pv_hash(lock, pn);
> +			u8 locked;
>  

Just out of curiosity, what if the following sequence happens:

	CPU 0			CPU 1
	=================	====================
	spin_lock():		spin_lock():
	  pv_kick_node(): 	  pv_wait_head_or_lock():
	  			  if (READ_ONCE(l->locked) != _Q_SLOW_VAL) { // True
				    pv_hash();

	    cmpxchg(&l->locked, _Q_LOCKED_VAL, _Q_SLOW_VAL);
	    pv_hash();
				    locked = xchg(&l->locked, _Q_SLOW_VAL);
	do_something();		    if(...) {
				    }
	spin_unlock():
	  pv_unhash();
				    else if (unlikely(locked == _Q_SLOW_VAL)) {
				    	WRITE_ONCE(*lp, NULL);

because pv_hash() on CPU 1 called before the one on CPU 0, therefore
the hash entry from CPU 1 is preceding the hash entry from CPU 0 in the
hash table, so that when pv_unhash() called, hash entry from CPU 1 will
be unhashed, however, the WRITE_ONCE(*lp, NULL) on CPU 1 will also
unhash the same entry, leaving that hash entry from CPU 0 not unhashed.

This could result in several interesting problems, right? ;-)

Am I missing something here?

Regards,
Boqun

>  			/*
>  			 * We must hash before setting _Q_SLOW_VAL, such that
> @@ -439,7 +443,8 @@ pv_wait_head_or_lock(struct qspinlock *lock, struct mcs_spinlock *node)
>  			 *
>  			 * Matches the smp_rmb() in __pv_queued_spin_unlock().
>  			 */
> -			if (xchg(&l->locked, _Q_SLOW_VAL) == 0) {
> +			locked = xchg(&l->locked, _Q_SLOW_VAL);
> +			if (locked == 0) {
>  				/*
>  				 * The lock was free and now we own the lock.
>  				 * Change the lock value back to _Q_LOCKED_VAL
> @@ -447,9 +452,18 @@ pv_wait_head_or_lock(struct qspinlock *lock, struct mcs_spinlock *node)
>  				 */
>  				WRITE_ONCE(l->locked, _Q_LOCKED_VAL);
>  				WRITE_ONCE(*lp, NULL);
> +				clear_pending(lock);
>  				goto gotlock;
> +			} else if (unlikely(locked == _Q_SLOW_VAL)) {
> +				/*
> +				 * Racing with pv_kick_node(), need to undo
> +				 * the pv_hash().
> +				 */
> +				WRITE_ONCE(*lp, NULL);
>  			}
>  		}
> +		clear_pending(lock);	/* Enable lock stealing */
> +
>  		WRITE_ONCE(pn->state, vcpu_halted);
>  		qstat_inc(qstat_pv_wait_head, true);
>  		qstat_inc(qstat_pv_wait_again, waitcnt);
> -- 
> 1.7.1
>

[toc] | [prev] | [next] | [standalone]

#1408253

FromWaiman Long <waiman.long@hpe.com>
Date2016-05-27 21:30 +0200
Message-ID<rDvCi-7ty-11@gated-at.bofh.it>
In reply to#1407880
On 05/27/2016 03:43 AM, Boqun Feng wrote:
> Hi Waiman,
>
> On Thu, May 26, 2016 at 02:21:57PM -0400, Waiman Long wrote:
>> Currently, calling pv_hash() and setting _Q_SLOW_VAL is only
>> done once for any pv_node. It is either in pv_kick_node() or in
>> pv_wait_head_or_lock(). Because of lock stealing, a pv_kick'ed node is
>> not guaranteed to get the lock before the spinning threshold expires
>> and has to call pv_wait() again. As a result, the new lock holder
>> won't see _Q_SLOW_VAL and so won't wake up the sleeping vCPU.
>>
>> This patch fixes this missed PV wakeup problem by allowing multiple
>> _Q_SLOW_VAL settings within pv_wait_head_or_lock() and matching each
>> successful setting of _Q_SLOW_VAL to a pv_hash() call.
>>
>> Reported-by: Pan Xinhui<xinhui.pan@linux.vnet.ibm.com>
>> Signed-off-by: Waiman Long<Waiman.Long@hpe.com>
>> ---
>>   kernel/locking/qspinlock_paravirt.h |   48 ++++++++++++++++++++++------------
>>   1 files changed, 31 insertions(+), 17 deletions(-)
>>
>> diff --git a/kernel/locking/qspinlock_paravirt.h b/kernel/locking/qspinlock_paravirt.h
>> index 21ede57..452d06d 100644
>> --- a/kernel/locking/qspinlock_paravirt.h
>> +++ b/kernel/locking/qspinlock_paravirt.h
>> @@ -369,12 +369,16 @@ static void pv_kick_node(struct qspinlock *lock, struct mcs_spinlock *node)
>>   	/*
>>   	 * Put the lock into the hash table and set the _Q_SLOW_VAL.
>>   	 *
>> -	 * As this is the same vCPU that will check the _Q_SLOW_VAL value and
>> -	 * the hash table later on at unlock time, no atomic instruction is
>> -	 * needed.
>> +	 * It is very unlikely that this will race with the _Q_SLOW_VAL setting
>> +	 * in pv_wait_head_or_lock(). However, we use cmpxchg() here to be
>> +	 * sure that we won't do a double pv_hash().
>> +	 *
>> +	 * As it is the lock holder, it won't race with
>> +	 * __pv_queued_spin_unlock().
>>   	 */
>> -	WRITE_ONCE(l->locked, _Q_SLOW_VAL);
>> -	(void)pv_hash(lock, pn);
>> +	if (likely(cmpxchg(&l->locked, _Q_LOCKED_VAL, _Q_SLOW_VAL)
>> +			== _Q_LOCKED_VAL))
>> +		pv_hash(lock, pn);
>>   }
>>
>>   /*
>> @@ -389,18 +393,10 @@ pv_wait_head_or_lock(struct qspinlock *lock, struct mcs_spinlock *node)
>>   {
>>   	struct pv_node *pn = (struct pv_node *)node;
>>   	struct __qspinlock *l = (void *)lock;
>> -	struct qspinlock **lp = NULL;
>>   	int waitcnt = 0;
>>   	int loop;
>>
>>   	/*
>> -	 * If pv_kick_node() already advanced our state, we don't need to
>> -	 * insert ourselves into the hash table anymore.
>> -	 */
>> -	if (READ_ONCE(pn->state) == vcpu_hashed)
>> -		lp = (struct qspinlock **)1;
>> -
>> -	/*
>>   	 * Tracking # of slowpath locking operations
>>   	 */
>>   	qstat_inc(qstat_pv_lock_slowpath, true);
>> @@ -422,11 +418,19 @@ pv_wait_head_or_lock(struct qspinlock *lock, struct mcs_spinlock *node)
>>   				goto gotlock;
>>   			cpu_relax();
>>   		}
>> -		clear_pending(lock);
>>
>> +		/*
>> +		 * Make sure the lock value check below is executed after
>> +		 * all the previous loads.
>> +		 */
>> +		smp_rmb();
>>
>> -		if (!lp) { /* ONCE */
>> -			lp = pv_hash(lock, pn);
>> +		/*
>> +		 * Set _Q_SLOW_VAL and hash the PV node, if necessary.
>> +		 */
>> +		if (READ_ONCE(l->locked) != _Q_SLOW_VAL) {
>> +			struct qspinlock **lp = pv_hash(lock, pn);
>> +			u8 locked;
>>
> Just out of curiosity, what if the following sequence happens:
>
> 	CPU 0			CPU 1
> 	=================	====================
> 	spin_lock():		spin_lock():
> 	  pv_kick_node(): 	  pv_wait_head_or_lock():
> 	  			  if (READ_ONCE(l->locked) != _Q_SLOW_VAL) { // True
> 				    pv_hash();
>
> 	    cmpxchg(&l->locked, _Q_LOCKED_VAL, _Q_SLOW_VAL);
> 	    pv_hash();
> 				    locked = xchg(&l->locked, _Q_SLOW_VAL);
> 	do_something();		    if(...) {
> 				    }
> 	spin_unlock():
> 	  pv_unhash();
> 				    else if (unlikely(locked == _Q_SLOW_VAL)) {
> 				    	WRITE_ONCE(*lp, NULL);
>
> because pv_hash() on CPU 1 called before the one on CPU 0, therefore
> the hash entry from CPU 1 is preceding the hash entry from CPU 0 in the
> hash table, so that when pv_unhash() called, hash entry from CPU 1 will
> be unhashed, however, the WRITE_ONCE(*lp, NULL) on CPU 1 will also
> unhash the same entry, leaving that hash entry from CPU 0 not unhashed.
>
> This could result in several interesting problems, right? ;-)

This is a very unlikely scenario, but I agree that it can happen. I 
think the only way to close this loophole is to make pv_unhash() atomic. 
By using pv_unhash() instead of WRITE_ONCE(), it should fix this issue. 
I will send out an updated patch to fix that.

Cheers,
Longman

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web