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

Groups > linux.kernel > #1444073 > unrolled thread

Re: [PATCH v2 2/5] locking/pvqspinlock: Fix missed PV wakeup problem

Started byPeter Zijlstra <peterz@infradead.org>
First post2016-07-15 10:50 +0200
Last post2016-07-21 08:50 +0200
Articles 7 — 5 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

  Re: [PATCH v2 2/5] locking/pvqspinlock: Fix missed PV wakeup problem Peter Zijlstra <peterz@infradead.org> - 2016-07-15 10:50 +0200
    Re: [PATCH v2 2/5] locking/pvqspinlock: Fix missed PV wakeup problem Pan Xinhui <xinhui@linux.vnet.ibm.com> - 2016-07-15 11:40 +0200
      Re: [PATCH v2 2/5] locking/pvqspinlock: Fix missed PV wakeup problem Peter Zijlstra <peterz@infradead.org> - 2016-07-15 12:10 +0200
        Re: [PATCH v2 2/5] locking/pvqspinlock: Fix missed PV wakeup problem Peter Zijlstra <peterz@infradead.org> - 2016-07-15 18:40 +0200
          Re: [PATCH v2 2/5] locking/pvqspinlock: Fix missed PV wakeup problem Boqun Feng <boqun.feng@gmail.com> - 2016-07-16 03:20 +0200
            Re: [PATCH v2 2/5] locking/pvqspinlock: Fix missed PV wakeup problem Wanpeng Li <kernellwp@gmail.com> - 2016-07-18 01:30 +0200
          Re: [PATCH v2 2/5] locking/pvqspinlock: Fix missed PV wakeup problem xinhui <xinhui.pan@linux.vnet.ibm.com> - 2016-07-21 08:50 +0200

#1444073 — Re: [PATCH v2 2/5] locking/pvqspinlock: Fix missed PV wakeup problem

FromPeter Zijlstra <peterz@infradead.org>
Date2016-07-15 10:50 +0200
SubjectRe: [PATCH v2 2/5] locking/pvqspinlock: Fix missed PV wakeup problem
Message-ID<rV6YO-4Gq-15@gated-at.bofh.it>
So the reason I never get around to this is because the patch stinks.

It simply doesn't make sense... Remember, the harder you make a reviewer
work the less likely the review will be done.

Present things in clear concise language and draw a picture.

On Tue, May 31, 2016 at 12:53:48PM -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().

So far so good....

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

*brain melts* what!? pv_kick'ed node reads like pv_kick_node() and that
doesn't make any kind of sense.

I'm thinking you're trying to say this:


CPU0			CPU1			CPU2

__pv_queued_spin_unlock_slowpath()
  ...
  smp_store_release(&l->locked, 0);
			__pv_queued_spin_lock_slowpath()
			  ...
			  pv_queued_spin_steal_lock()
			    cmpxchg(&l->locked, 0, _Q_LOCKED_VAL) == 0


						pv_wait_head_or_lock()

  pv_kick(node->cpu);  ---------------------->	  pv_wait(&l->locked, _Q_SLOW_VAL);

			__pv_queued_spin_unlock()
			  cmpxchg(&l->locked, _Q_LOCKED_VAL, 0) == _Q_LOCKED_VAL

						  for () {
						    trylock_clear_pending();
						    cpu_relax();
						  }

						  pv_wait(&l->locked, _Q_SLOW_VAL);


Which is indeed 'bad', but not fatal, note that the later pv_wait() will
not in fact go wait, since l->locked will _not_ be _Q_SLOW_VAL.

Is this indeed the 3 CPU scenario you tried to describe in a scant 4
lines of text, or is there more to it?

[toc] | [next] | [standalone]

#1444118

FromPan Xinhui <xinhui@linux.vnet.ibm.com>
Date2016-07-15 11:40 +0200
Message-ID<rV7Lc-5c0-15@gated-at.bofh.it>
In reply to#1444073

在 16/7/15 16:47, Peter Zijlstra 写道:
>
> So the reason I never get around to this is because the patch stinks.
>
> It simply doesn't make sense... Remember, the harder you make a reviewer
> work the less likely the review will be done.
>
> Present things in clear concise language and draw a picture.
>
> On Tue, May 31, 2016 at 12:53:48PM -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().
>
> So far so good....
>
>> 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.
>
waiman, it might be "as a result, the head node will not really enter wait state because ->locked is not_Q_SLOW_VAL, the pv_wait will return directly."

> *brain melts* what!? pv_kick'ed node reads like pv_kick_node() and that
> doesn't make any kind of sense.
>
> I'm thinking you're trying to say this:
>
>
> CPU0			CPU1			CPU2
>
> __pv_queued_spin_unlock_slowpath()
>   ...
>   smp_store_release(&l->locked, 0);
> 			__pv_queued_spin_lock_slowpath()
> 			  ...
> 			  pv_queued_spin_steal_lock()
> 			    cmpxchg(&l->locked, 0, _Q_LOCKED_VAL) == 0
>
>
> 						pv_wait_head_or_lock()
>
>   pv_kick(node->cpu);  ---------------------->	  pv_wait(&l->locked, _Q_SLOW_VAL);
>
> 			__pv_queued_spin_unlock()
> 			  cmpxchg(&l->locked, _Q_LOCKED_VAL, 0) == _Q_LOCKED_VAL
>
> 						  for () {
> 						    trylock_clear_pending();
> 						    cpu_relax();
> 						  }
>
> 						  pv_wait(&l->locked, _Q_SLOW_VAL);
>
>
> Which is indeed 'bad', but not fatal, note that the later pv_wait() will
> not in fact go wait, since l->locked will _not_ be _Q_SLOW_VAL.
>
hi, Peter

the problem is that "this later pv_wait will do nothing as l->locked is not _Q_SLOW_VAL",
So it is not paravirt friendly then. we will go into the trylock loop again and again until the lock is unlocked.

So if we are kicked by the unlock_slowpath, and the lock is stealed by someone else,  we need hash its node again and set l->locked to _Q_SLOW_VAL, then enter pv_wait.

but I am worried about lock stealing. could the node in the queue starve for a long time? I notice the latency of pv_wait on an over-commited guest can be bigger than 300us. I have not seen such starving case, but I think it is possible to happen.

thanks
xinhui

> Is this indeed the 3 CPU scenario you tried to describe in a scant 4
> lines of text, or is there more to it?
>

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

#1444144

FromPeter Zijlstra <peterz@infradead.org>
Date2016-07-15 12:10 +0200
Message-ID<rV8ee-5Bf-31@gated-at.bofh.it>
In reply to#1444118
On Fri, Jul 15, 2016 at 05:39:46PM +0800, Pan Xinhui wrote:
> >I'm thinking you're trying to say this:
> >
> >
> >CPU0			CPU1			CPU2
> >
> >__pv_queued_spin_unlock_slowpath()
> >  ...
> >  smp_store_release(&l->locked, 0);
> >			__pv_queued_spin_lock_slowpath()
> >			  ...
> >			  pv_queued_spin_steal_lock()
> >			    cmpxchg(&l->locked, 0, _Q_LOCKED_VAL) == 0
> >
> >
> >						pv_wait_head_or_lock()
> >
> >  pv_kick(node->cpu);  ---------------------->	  pv_wait(&l->locked, _Q_SLOW_VAL);
> >
> >			__pv_queued_spin_unlock()
> >			  cmpxchg(&l->locked, _Q_LOCKED_VAL, 0) == _Q_LOCKED_VAL
> >
> >						  for () {
> >						    trylock_clear_pending();
> >						    cpu_relax();
> >						  }
> >
> >						  pv_wait(&l->locked, _Q_SLOW_VAL);
> >
> >
> >Which is indeed 'bad', but not fatal, note that the later pv_wait() will
> >not in fact go wait, since l->locked will _not_ be _Q_SLOW_VAL.

> 
> the problem is that "this later pv_wait will do nothing as l->locked
> is not _Q_SLOW_VAL", So it is not paravirt friendly then. we will go
> into the trylock loop again and again until the lock is unlocked.

Agreed, which is 'bad'. But the patch spoke about a missing wakeup,
which is worse, as that would completely inhibit progress.

> So if we are kicked by the unlock_slowpath, and the lock is stealed by
> someone else,  we need hash its node again and set l->locked to
> _Q_SLOW_VAL, then enter pv_wait.

Right, let me go think about this a bit.

> but I am worried about lock stealing. could the node in the queue
> starve for a long time? I notice the latency of pv_wait on an
> over-commited guest can be bigger than 300us. I have not seen such
> starving case, but I think it is possible to happen.

I share that worry, which is why we limit the steal attempt to one.
But yes, theoretically its possible to starve things AFAICT.

We've not come up with sensible way to completely avoid starvation.

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

#1444434

FromPeter Zijlstra <peterz@infradead.org>
Date2016-07-15 18:40 +0200
Message-ID<rVejE-K7-15@gated-at.bofh.it>
In reply to#1444144
On Fri, Jul 15, 2016 at 12:07:03PM +0200, Peter Zijlstra wrote:
> > So if we are kicked by the unlock_slowpath, and the lock is stealed by
> > someone else,  we need hash its node again and set l->locked to
> > _Q_SLOW_VAL, then enter pv_wait.
> 
> Right, let me go think about this a bit.

Urgh, brain hurt.

So I _think_ the below does for it but I could easily have missed yet
another case.

Waiman's patch has the problem that it can have two pv_hash() calls for
the same lock in progress and I'm thinking that means we can hit the
BUG() in pv_hash() due to that.

If we can't, it still has a problem because its not telling us either.



--- a/kernel/locking/qspinlock_paravirt.h
+++ b/kernel/locking/qspinlock_paravirt.h
@@ -20,7 +20,8 @@
  * native_queued_spin_unlock().
  */
 
-#define _Q_SLOW_VAL	(3U << _Q_LOCKED_OFFSET)
+#define _Q_HASH_VAL	(3U << _Q_LOCKED_OFFSET)
+#define _Q_SLOW_VAL	(7U << _Q_LOCKED_OFFSET)
 
 /*
  * Queue Node Adaptive Spinning
@@ -36,14 +37,11 @@
  */
 #define PV_PREV_CHECK_MASK	0xff
 
-/*
- * Queue node uses: vcpu_running & vcpu_halted.
- * Queue head uses: vcpu_running & vcpu_hashed.
- */
 enum vcpu_state {
-	vcpu_running = 0,
-	vcpu_halted,		/* Used only in pv_wait_node */
-	vcpu_hashed,		/* = pv_hash'ed + vcpu_halted */
+	vcpu_node_running = 0,
+	vcpu_node_halted,
+	vcpu_head_running,
+	vcpu_head_halted,
 };
 
 struct pv_node {
@@ -263,7 +261,7 @@ pv_wait_early(struct pv_node *prev, int
 	if ((loop & PV_PREV_CHECK_MASK) != 0)
 		return false;
 
-	return READ_ONCE(prev->state) != vcpu_running;
+	return READ_ONCE(prev->state) & 1;
 }
 
 /*
@@ -311,20 +309,19 @@ static void pv_wait_node(struct mcs_spin
 		 *
 		 * Matches the cmpxchg() from pv_kick_node().
 		 */
-		smp_store_mb(pn->state, vcpu_halted);
+		smp_store_mb(pn->state, vcpu_node_halted);
 
-		if (!READ_ONCE(node->locked)) {
-			qstat_inc(qstat_pv_wait_node, true);
-			qstat_inc(qstat_pv_wait_early, wait_early);
-			pv_wait(&pn->state, vcpu_halted);
-		}
+		if (READ_ONCE(node->locked))
+			return;
+
+		qstat_inc(qstat_pv_wait_node, true);
+		qstat_inc(qstat_pv_wait_early, wait_early);
+		pv_wait(&pn->state, vcpu_node_halted);
 
 		/*
-		 * If pv_kick_node() changed us to vcpu_hashed, retain that
-		 * value so that pv_wait_head_or_lock() knows to not also try
-		 * to hash this lock.
+		 * If pv_kick_node() advanced us, retain that state.
 		 */
-		cmpxchg(&pn->state, vcpu_halted, vcpu_running);
+		cmpxchg(&pn->state, vcpu_node_halted, vcpu_node_running);
 
 		/*
 		 * If the locked flag is still not set after wakeup, it is a
@@ -362,18 +359,17 @@ static void pv_kick_node(struct qspinloc
 	 *
 	 * Matches with smp_store_mb() and cmpxchg() in pv_wait_node()
 	 */
-	if (cmpxchg(&pn->state, vcpu_halted, vcpu_hashed) != vcpu_halted)
+	if (cmpxchg(&pn->state, vcpu_node_halted, vcpu_head_running) != vcpu_node_halted)
 		return;
 
 	/*
-	 * 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.
+	 * See pv_wait_head_or_lock(). We have to hash and force the unlock
+	 * into the slow path to deliver the actual kick for waking.
 	 */
-	WRITE_ONCE(l->locked, _Q_SLOW_VAL);
-	(void)pv_hash(lock, pn);
+	if (cmpxchg(&l->locked, _Q_LOCKED_VAL, _Q_HASH_VAL) == _Q_LOCKED_VAL) {
+		(void)pv_hash(lock, pn);
+		smp_store_release(&l->locked, _Q_SLOW_VAL);
+	}
 }
 
 /*
@@ -388,28 +384,22 @@ pv_wait_head_or_lock(struct qspinlock *l
 {
 	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);
 
 	for (;; waitcnt++) {
+		u8 locked;
+
 		/*
 		 * Set correct vCPU state to be used by queue node wait-early
 		 * mechanism.
 		 */
-		WRITE_ONCE(pn->state, vcpu_running);
+		WRITE_ONCE(pn->state, vcpu_head_running);
 
 		/*
 		 * Set the pending bit in the active lock spinning loop to
@@ -423,33 +413,38 @@ pv_wait_head_or_lock(struct qspinlock *l
 		}
 		clear_pending(lock);
 
+		/*
+		 * We want to go sleep; ensure we're hashed so that
+		 * __pv_queued_spin_unlock_slow() can find us for a wakeup.
+		 */
+		locked = cmpxchg(&l->locked, _Q_LOCKED_VAL, _Q_HASH_VAL);
+		switch (locked) {
+		/*
+		 * We're not hashed yet, either we're fresh from pv_wait_node()
+		 * or __pv_queued_spin_unlock_slow() unhashed us but we lost
+		 * the trylock to a steal and have to re-hash.
+		 */
+		case _Q_LOCKED_VAL:
+			(void)pv_hash(lock, pn);
+			smp_store_release(&l->locked, _Q_SLOW_VAL);
+			break;
 
-		if (!lp) { /* ONCE */
-			lp = pv_hash(lock, pn);
+		/*
+		 * pv_kick_node() is hashing us, wait for it.
+		 */
+		case _Q_HASH_VAL:
+			while (READ_ONCE(l->locked) == _Q_HASH_VAL)
+				cpu_relax();
+			break;
 
-			/*
-			 * We must hash before setting _Q_SLOW_VAL, such that
-			 * when we observe _Q_SLOW_VAL in __pv_queued_spin_unlock()
-			 * we'll be sure to be able to observe our hash entry.
-			 *
-			 *   [S] <hash>                 [Rmw] l->locked == _Q_SLOW_VAL
-			 *       MB                           RMB
-			 * [RmW] l->locked = _Q_SLOW_VAL  [L] <unhash>
-			 *
-			 * Matches the smp_rmb() in __pv_queued_spin_unlock().
-			 */
-			if (xchg(&l->locked, _Q_SLOW_VAL) == 0) {
-				/*
-				 * 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);
-				goto gotlock;
-			}
+		/*
+		 * Ooh, unlocked, try and grab it.
+		 */
+		case 0:
+			continue;
 		}
-		WRITE_ONCE(pn->state, vcpu_hashed);
+
+		WRITE_ONCE(pn->state, vcpu_head_halted);
 		qstat_inc(qstat_pv_wait_head, true);
 		qstat_inc(qstat_pv_wait_again, waitcnt);
 		pv_wait(&l->locked, _Q_SLOW_VAL);
@@ -480,7 +475,7 @@ __pv_queued_spin_unlock_slowpath(struct
 	struct __qspinlock *l = (void *)lock;
 	struct pv_node *node;
 
-	if (unlikely(locked != _Q_SLOW_VAL)) {
+	if (unlikely(locked != _Q_SLOW_VAL && locked != _Q_HASH_VAL)) {
 		WARN(!debug_locks_silent,
 		     "pvqspinlock: lock 0x%lx has corrupted value 0x%x!\n",
 		     (unsigned long)lock, atomic_read(&lock->val));
@@ -488,18 +483,17 @@ __pv_queued_spin_unlock_slowpath(struct
 	}
 
 	/*
-	 * A failed cmpxchg doesn't provide any memory-ordering guarantees,
-	 * so we need a barrier to order the read of the node data in
-	 * pv_unhash *after* we've read the lock being _Q_SLOW_VAL.
-	 *
-	 * Matches the cmpxchg() in pv_wait_head_or_lock() setting _Q_SLOW_VAL.
+	 * Wait until the hash-bucket is complete.
 	 */
-	smp_rmb();
+	while (READ_ONCE(l->locked) == _Q_HASH_VAL)
+		cpu_relax();
 
 	/*
-	 * Since the above failed to release, this must be the SLOW path.
-	 * Therefore start by looking up the blocked node and unhashing it.
+	 * Must first observe _Q_SLOW_VAL in order to observe
+	 * consistent hash bucket.
 	 */
+	smp_rmb();
+
 	node = pv_unhash(lock);
 
 	/*

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

#1444715

FromBoqun Feng <boqun.feng@gmail.com>
Date2016-07-16 03:20 +0200
Message-ID<rVmqR-5Lg-5@gated-at.bofh.it>
In reply to#1444434

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

On Fri, Jul 15, 2016 at 06:35:56PM +0200, Peter Zijlstra wrote:
> On Fri, Jul 15, 2016 at 12:07:03PM +0200, Peter Zijlstra wrote:
> > > So if we are kicked by the unlock_slowpath, and the lock is stealed by
> > > someone else,  we need hash its node again and set l->locked to
> > > _Q_SLOW_VAL, then enter pv_wait.
> > 
> > Right, let me go think about this a bit.
> 
> Urgh, brain hurt.
> 
> So I _think_ the below does for it but I could easily have missed yet
> another case.
> 
> Waiman's patch has the problem that it can have two pv_hash() calls for
> the same lock in progress and I'm thinking that means we can hit the
> BUG() in pv_hash() due to that.
> 

I think Waiman's patch does have the problem of two pv_hash() calls for
the same lock in progress. As I mentioned in the first version:

http://lkml.kernel.org/g/20160527074331.GB8096@insomnia

And he tried to address this in the patch #3 of this series. However,
I think what is proper here is either to reorder patch 2 and 3 or to
merge patch 2 and 3, otherwise, we are introducing a bug in the middle
of this series.

Thoughts, Waiman?

That said, I found Peter's way is much simpler and easier to understand
;-)

> If we can't, it still has a problem because its not telling us either.
> 
> 
> 
> --- a/kernel/locking/qspinlock_paravirt.h
> +++ b/kernel/locking/qspinlock_paravirt.h
> @@ -20,7 +20,8 @@
>   * native_queued_spin_unlock().
>   */
>  
> -#define _Q_SLOW_VAL	(3U << _Q_LOCKED_OFFSET)
> +#define _Q_HASH_VAL	(3U << _Q_LOCKED_OFFSET)
> +#define _Q_SLOW_VAL	(7U << _Q_LOCKED_OFFSET)
>  
>  /*
>   * Queue Node Adaptive Spinning
> @@ -36,14 +37,11 @@
>   */
>  #define PV_PREV_CHECK_MASK	0xff
>  
> -/*
> - * Queue node uses: vcpu_running & vcpu_halted.
> - * Queue head uses: vcpu_running & vcpu_hashed.
> - */
>  enum vcpu_state {
> -	vcpu_running = 0,
> -	vcpu_halted,		/* Used only in pv_wait_node */
> -	vcpu_hashed,		/* = pv_hash'ed + vcpu_halted */
> +	vcpu_node_running = 0,
> +	vcpu_node_halted,
> +	vcpu_head_running,

We actually don't need this extra running state, right? Because nobody
cares about the difference between two running states right now.

> +	vcpu_head_halted,
>  };
>  
>  struct pv_node {
> @@ -263,7 +261,7 @@ pv_wait_early(struct pv_node *prev, int
>  	if ((loop & PV_PREV_CHECK_MASK) != 0)
>  		return false;
>  
> -	return READ_ONCE(prev->state) != vcpu_running;
> +	return READ_ONCE(prev->state) & 1;
>  }
>  
>  /*
> @@ -311,20 +309,19 @@ static void pv_wait_node(struct mcs_spin
>  		 *
>  		 * Matches the cmpxchg() from pv_kick_node().
>  		 */
> -		smp_store_mb(pn->state, vcpu_halted);
> +		smp_store_mb(pn->state, vcpu_node_halted);
>  
> -		if (!READ_ONCE(node->locked)) {
> -			qstat_inc(qstat_pv_wait_node, true);
> -			qstat_inc(qstat_pv_wait_early, wait_early);
> -			pv_wait(&pn->state, vcpu_halted);
> -		}
> +		if (READ_ONCE(node->locked))
> +			return;
> +
> +		qstat_inc(qstat_pv_wait_node, true);
> +		qstat_inc(qstat_pv_wait_early, wait_early);
> +		pv_wait(&pn->state, vcpu_node_halted);
>  
>  		/*
> -		 * If pv_kick_node() changed us to vcpu_hashed, retain that
> -		 * value so that pv_wait_head_or_lock() knows to not also try
> -		 * to hash this lock.
> +		 * If pv_kick_node() advanced us, retain that state.
>  		 */
> -		cmpxchg(&pn->state, vcpu_halted, vcpu_running);
> +		cmpxchg(&pn->state, vcpu_node_halted, vcpu_node_running);
>  
>  		/*
>  		 * If the locked flag is still not set after wakeup, it is a
> @@ -362,18 +359,17 @@ static void pv_kick_node(struct qspinloc
>  	 *
>  	 * Matches with smp_store_mb() and cmpxchg() in pv_wait_node()
>  	 */
> -	if (cmpxchg(&pn->state, vcpu_halted, vcpu_hashed) != vcpu_halted)
> +	if (cmpxchg(&pn->state, vcpu_node_halted, vcpu_head_running) != vcpu_node_halted)
>  		return;
>  
>  	/*
> -	 * 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.
> +	 * See pv_wait_head_or_lock(). We have to hash and force the unlock
> +	 * into the slow path to deliver the actual kick for waking.
>  	 */
> -	WRITE_ONCE(l->locked, _Q_SLOW_VAL);
> -	(void)pv_hash(lock, pn);
> +	if (cmpxchg(&l->locked, _Q_LOCKED_VAL, _Q_HASH_VAL) == _Q_LOCKED_VAL) {
> +		(void)pv_hash(lock, pn);
> +		smp_store_release(&l->locked, _Q_SLOW_VAL);
> +	}
>  }
>  
>  /*
> @@ -388,28 +384,22 @@ pv_wait_head_or_lock(struct qspinlock *l
>  {
>  	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);
>  
>  	for (;; waitcnt++) {
> +		u8 locked;
> +
>  		/*
>  		 * Set correct vCPU state to be used by queue node wait-early
>  		 * mechanism.
>  		 */
> -		WRITE_ONCE(pn->state, vcpu_running);
> +		WRITE_ONCE(pn->state, vcpu_head_running);
>  
>  		/*
>  		 * Set the pending bit in the active lock spinning loop to
> @@ -423,33 +413,38 @@ pv_wait_head_or_lock(struct qspinlock *l
>  		}
>  		clear_pending(lock);
>  
> +		/*
> +		 * We want to go sleep; ensure we're hashed so that
> +		 * __pv_queued_spin_unlock_slow() can find us for a wakeup.
> +		 */
> +		locked = cmpxchg(&l->locked, _Q_LOCKED_VAL, _Q_HASH_VAL);
> +		switch (locked) {
> +		/*
> +		 * We're not hashed yet, either we're fresh from pv_wait_node()
> +		 * or __pv_queued_spin_unlock_slow() unhashed us but we lost
> +		 * the trylock to a steal and have to re-hash.
> +		 */
> +		case _Q_LOCKED_VAL:
> +			(void)pv_hash(lock, pn);
> +			smp_store_release(&l->locked, _Q_SLOW_VAL);
> +			break;
>  
> -		if (!lp) { /* ONCE */
> -			lp = pv_hash(lock, pn);
> +		/*
> +		 * pv_kick_node() is hashing us, wait for it.
> +		 */
> +		case _Q_HASH_VAL:
> +			while (READ_ONCE(l->locked) == _Q_HASH_VAL)
> +				cpu_relax();
> +			break;
>  
> -			/*
> -			 * We must hash before setting _Q_SLOW_VAL, such that
> -			 * when we observe _Q_SLOW_VAL in __pv_queued_spin_unlock()
> -			 * we'll be sure to be able to observe our hash entry.
> -			 *
> -			 *   [S] <hash>                 [Rmw] l->locked == _Q_SLOW_VAL
> -			 *       MB                           RMB
> -			 * [RmW] l->locked = _Q_SLOW_VAL  [L] <unhash>
> -			 *
> -			 * Matches the smp_rmb() in __pv_queued_spin_unlock().
> -			 */
> -			if (xchg(&l->locked, _Q_SLOW_VAL) == 0) {
> -				/*
> -				 * 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);
> -				goto gotlock;
> -			}
> +		/*
> +		 * Ooh, unlocked, try and grab it.
> +		 */
> +		case 0:
> +			continue;
>  		}
> -		WRITE_ONCE(pn->state, vcpu_hashed);
> +
> +		WRITE_ONCE(pn->state, vcpu_head_halted);
>  		qstat_inc(qstat_pv_wait_head, true);
>  		qstat_inc(qstat_pv_wait_again, waitcnt);
>  		pv_wait(&l->locked, _Q_SLOW_VAL);
> @@ -480,7 +475,7 @@ __pv_queued_spin_unlock_slowpath(struct
>  	struct __qspinlock *l = (void *)lock;
>  	struct pv_node *node;
>  
> -	if (unlikely(locked != _Q_SLOW_VAL)) {
> +	if (unlikely(locked != _Q_SLOW_VAL && locked != _Q_HASH_VAL)) {
>  		WARN(!debug_locks_silent,
>  		     "pvqspinlock: lock 0x%lx has corrupted value 0x%x!\n",
>  		     (unsigned long)lock, atomic_read(&lock->val));
> @@ -488,18 +483,17 @@ __pv_queued_spin_unlock_slowpath(struct
>  	}
>  
>  	/*
> -	 * A failed cmpxchg doesn't provide any memory-ordering guarantees,
> -	 * so we need a barrier to order the read of the node data in
> -	 * pv_unhash *after* we've read the lock being _Q_SLOW_VAL.
> -	 *
> -	 * Matches the cmpxchg() in pv_wait_head_or_lock() setting _Q_SLOW_VAL.
> +	 * Wait until the hash-bucket is complete.
>  	 */
> -	smp_rmb();
> +	while (READ_ONCE(l->locked) == _Q_HASH_VAL)
> +		cpu_relax();
>  

This does give a chance to let the lock waiter block the lock holder,
right? Considering a lock queue head's vcpu is preempted before it could
set the lock to _Q_SLOW_VAL.

Could we do something like this here:

	if (unlikely(cmpxchg(l->locked, _Q_HASH_VAL, 0) == _Q_HASH_VAL))
		return;
		
And in pv_wait_head_or_lock()

	locked = cmpxchg(&l->locked, _Q_LOCKED_VAL, _Q_HASH_VAL);
	switch(locked) {
		case _Q_LOCKED_VAL:
			(void)pv_hash(lock, pn);
			locked = cmpxchg_release(&l->locked, _Q_HASH_VAL, _Q_SLOW_VAL);

			/*
			 * Only the holder will change the ->locked from
			 * _Q_HASH_VAL to another value, if this
			 * happens, the holder has already released the
			 * lock without trying to wake the head, in this
			 * case, we need to unhash ourselves and there
			 * is a great chance we can get the locke.
			 */
			if (unlikely(locked != _Q_HASH_VAL)) {
				pv_unhash(lock, pn);
				if (!cmpxchg_relaxed(&l->locked, 0, _Q_LOCKED_VAL)
					goto gotlock;
			}
			break;



Wrote those in my mailbox, may miss something.

Thoughts?

Regards,
Boqun

>  	/*
> -	 * Since the above failed to release, this must be the SLOW path.
> -	 * Therefore start by looking up the blocked node and unhashing it.
> +	 * Must first observe _Q_SLOW_VAL in order to observe
> +	 * consistent hash bucket.
>  	 */
> +	smp_rmb();
> +
>  	node = pv_unhash(lock);
>  
>  	/*

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

#1445140

FromWanpeng Li <kernellwp@gmail.com>
Date2016-07-18 01:30 +0200
Message-ID<rW3Fv-6X1-1@gated-at.bofh.it>
In reply to#1444715
2016-07-18 7:10 GMT+08:00 Waiman Long <waiman.long@hpe.com>:
> On 07/17/2016 07:07 PM, Waiman Long wrote:
>>
>> On 07/15/2016 09:16 PM, Boqun Feng wrote:
>>>
>>> On Fri, Jul 15, 2016 at 06:35:56PM +0200, Peter Zijlstra wrote:
>>>>
>>>> On Fri, Jul 15, 2016 at 12:07:03PM +0200, Peter Zijlstra wrote:
>>>>>>
>>>>>> So if we are kicked by the unlock_slowpath, and the lock is stealed by
>>>>>> someone else,  we need hash its node again and set l->locked to
>>>>>> _Q_SLOW_VAL, then enter pv_wait.
>>>>>
>>>>> Right, let me go think about this a bit.
>>>>
>>>> Urgh, brain hurt.
>>>>
>>>> So I _think_ the below does for it but I could easily have missed yet
>>>> another case.
>>>>
>>>> Waiman's patch has the problem that it can have two pv_hash() calls for
>>>> the same lock in progress and I'm thinking that means we can hit the
>>>> BUG() in pv_hash() due to that.
>>>>
>>> I think Waiman's patch does have the problem of two pv_hash() calls for
>>> the same lock in progress. As I mentioned in the first version:
>>>
>>> http://lkml.kernel.org/g/20160527074331.GB8096@insomnia
>>>
>>> And he tried to address this in the patch #3 of this series. However,
>>> I think what is proper here is either to reorder patch 2 and 3 or to
>>> merge patch 2 and 3, otherwise, we are introducing a bug in the middle
>>> of this series.
>>>
>>> Thoughts, Waiman?
>>
>>
>> Patches 2 and 3 can be reversed.
>>
>>>
>>> That said, I found Peter's way is much simpler and easier to understand
>>> ;-)
>>
>>
>> I agree. Peter's patch is better than mine.
>>
>>>> If we can't, it still has a problem because its not telling us either.
>>>>
>>>>
>>>>
>>>> --- a/kernel/locking/qspinlock_paravirt.h
>>>> +++ b/kernel/locking/qspinlock_paravirt.h
>>>> @@ -20,7 +20,8 @@
>>>>    * native_queued_spin_unlock().
>>>>    */
>>>>
>>>> -#define _Q_SLOW_VAL    (3U<<  _Q_LOCKED_OFFSET)
>>>> +#define _Q_HASH_VAL    (3U<<  _Q_LOCKED_OFFSET)
>>>> +#define _Q_SLOW_VAL    (7U<<  _Q_LOCKED_OFFSET)
>>>>
>>>>   /*
>>>>    * Queue Node Adaptive Spinning
>>>> @@ -36,14 +37,11 @@
>>>>    */
>>>>   #define PV_PREV_CHECK_MASK    0xff
>>>>
>>>> -/*
>>>> - * Queue node uses: vcpu_running&  vcpu_halted.
>>>> - * Queue head uses: vcpu_running&  vcpu_hashed.
>>>> - */
>>>>   enum vcpu_state {
>>>> -    vcpu_running = 0,
>>>> -    vcpu_halted,        /* Used only in pv_wait_node */
>>>> -    vcpu_hashed,        /* = pv_hash'ed + vcpu_halted */
>>>> +    vcpu_node_running = 0,
>>>> +    vcpu_node_halted,
>>>> +    vcpu_head_running,
>>>
>>> We actually don't need this extra running state, right? Because nobody
>>> cares about the difference between two running states right now.
>>
>>
>> That addresses the problem in Xinhui patch that changed the state from
>> halted to hashed. With that separation, that change is no longer necessary.
>
>
> Oh, I meant Wanpeng's double hash race patch, not Xinhui's patch.

This patch can base on the top of mine, I think it has already done this way. :)

Regards,
Wanpeng Li

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

#1447644

Fromxinhui <xinhui.pan@linux.vnet.ibm.com>
Date2016-07-21 08:50 +0200
Message-ID<rXfXX-3QS-3@gated-at.bofh.it>
In reply to#1444434

On 2016年07月16日 00:35, Peter Zijlstra wrote:
> On Fri, Jul 15, 2016 at 12:07:03PM +0200, Peter Zijlstra wrote:
>>> So if we are kicked by the unlock_slowpath, and the lock is stealed by
>>> someone else,  we need hash its node again and set l->locked to
>>> _Q_SLOW_VAL, then enter pv_wait.
>>
>> Right, let me go think about this a bit.
>
> Urgh, brain hurt.
>
> So I _think_ the below does for it but I could easily have missed yet
> another case.
>
> Waiman's patch has the problem that it can have two pv_hash() calls for
> the same lock in progress and I'm thinking that means we can hit the
> BUG() in pv_hash() due to that.
>
> If we can't, it still has a problem because its not telling us either.
>
>
>
> --- a/kernel/locking/qspinlock_paravirt.h
> +++ b/kernel/locking/qspinlock_paravirt.h
> @@ -20,7 +20,8 @@
>    * native_queued_spin_unlock().
>    */
>
> -#define _Q_SLOW_VAL	(3U << _Q_LOCKED_OFFSET)
> +#define _Q_HASH_VAL	(3U << _Q_LOCKED_OFFSET)
> +#define _Q_SLOW_VAL	(7U << _Q_LOCKED_OFFSET)
>
>   /*
>    * Queue Node Adaptive Spinning
> @@ -36,14 +37,11 @@
>    */
>   #define PV_PREV_CHECK_MASK	0xff
>
> -/*
> - * Queue node uses: vcpu_running & vcpu_halted.
> - * Queue head uses: vcpu_running & vcpu_hashed.
> - */
>   enum vcpu_state {
> -	vcpu_running = 0,
> -	vcpu_halted,		/* Used only in pv_wait_node */
> -	vcpu_hashed,		/* = pv_hash'ed + vcpu_halted */
> +	vcpu_node_running = 0,
> +	vcpu_node_halted,
> +	vcpu_head_running,
> +	vcpu_head_halted,
>   };
>
>   struct pv_node {
> @@ -263,7 +261,7 @@ pv_wait_early(struct pv_node *prev, int
>   	if ((loop & PV_PREV_CHECK_MASK) != 0)
>   		return false;
>
> -	return READ_ONCE(prev->state) != vcpu_running;
> +	return READ_ONCE(prev->state) & 1;
>   }
>
>   /*
> @@ -311,20 +309,19 @@ static void pv_wait_node(struct mcs_spin
>   		 *
>   		 * Matches the cmpxchg() from pv_kick_node().
>   		 */
> -		smp_store_mb(pn->state, vcpu_halted);
> +		smp_store_mb(pn->state, vcpu_node_halted);
>
> -		if (!READ_ONCE(node->locked)) {
> -			qstat_inc(qstat_pv_wait_node, true);
> -			qstat_inc(qstat_pv_wait_early, wait_early);
> -			pv_wait(&pn->state, vcpu_halted);
> -		}
> +		if (READ_ONCE(node->locked))
> +			return;
> +
> +		qstat_inc(qstat_pv_wait_node, true);
> +		qstat_inc(qstat_pv_wait_early, wait_early);
> +		pv_wait(&pn->state, vcpu_node_halted);
>
>   		/*
> -		 * If pv_kick_node() changed us to vcpu_hashed, retain that
> -		 * value so that pv_wait_head_or_lock() knows to not also try
> -		 * to hash this lock.
> +		 * If pv_kick_node() advanced us, retain that state.
>   		 */
> -		cmpxchg(&pn->state, vcpu_halted, vcpu_running);
> +		cmpxchg(&pn->state, vcpu_node_halted, vcpu_node_running);
>
>   		/*
>   		 * If the locked flag is still not set after wakeup, it is a
> @@ -362,18 +359,17 @@ static void pv_kick_node(struct qspinloc
>   	 *
>   	 * Matches with smp_store_mb() and cmpxchg() in pv_wait_node()
>   	 */
> -	if (cmpxchg(&pn->state, vcpu_halted, vcpu_hashed) != vcpu_halted)
> +	if (cmpxchg(&pn->state, vcpu_node_halted, vcpu_head_running) != vcpu_node_halted)
well, I think it should be
if (cmpxchg(&pn->state, vcpu_node_halted, vcpu_head_halted) != vcpu_node_halted)

yes, the node has been the *head*, but the running state does not change.

others looks ok to me.

>   		return;
>
>   	/*
> -	 * 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.
> +	 * See pv_wait_head_or_lock(). We have to hash and force the unlock
> +	 * into the slow path to deliver the actual kick for waking.
>   	 */
> -	WRITE_ONCE(l->locked, _Q_SLOW_VAL);
> -	(void)pv_hash(lock, pn);
> +	if (cmpxchg(&l->locked, _Q_LOCKED_VAL, _Q_HASH_VAL) == _Q_LOCKED_VAL) {
> +		(void)pv_hash(lock, pn);
> +		smp_store_release(&l->locked, _Q_SLOW_VAL);
> +	}
>   }
>
>   /*
> @@ -388,28 +384,22 @@ pv_wait_head_or_lock(struct qspinlock *l
>   {
>   	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);
>
>   	for (;; waitcnt++) {
> +		u8 locked;
> +
>   		/*
>   		 * Set correct vCPU state to be used by queue node wait-early
>   		 * mechanism.
>   		 */
> -		WRITE_ONCE(pn->state, vcpu_running);
> +		WRITE_ONCE(pn->state, vcpu_head_running);
>
>   		/*
>   		 * Set the pending bit in the active lock spinning loop to
> @@ -423,33 +413,38 @@ pv_wait_head_or_lock(struct qspinlock *l
>   		}
>   		clear_pending(lock);
>
> +		/*
> +		 * We want to go sleep; ensure we're hashed so that
> +		 * __pv_queued_spin_unlock_slow() can find us for a wakeup.
> +		 */
> +		locked = cmpxchg(&l->locked, _Q_LOCKED_VAL, _Q_HASH_VAL);
> +		switch (locked) {
> +		/*
> +		 * We're not hashed yet, either we're fresh from pv_wait_node()
> +		 * or __pv_queued_spin_unlock_slow() unhashed us but we lost
> +		 * the trylock to a steal and have to re-hash.
> +		 */
> +		case _Q_LOCKED_VAL:
> +			(void)pv_hash(lock, pn);
> +			smp_store_release(&l->locked, _Q_SLOW_VAL);
> +			break;
>
> -		if (!lp) { /* ONCE */
> -			lp = pv_hash(lock, pn);
> +		/*
> +		 * pv_kick_node() is hashing us, wait for it.
> +		 */
> +		case _Q_HASH_VAL:
> +			while (READ_ONCE(l->locked) == _Q_HASH_VAL)
> +				cpu_relax();
> +			break;
>
> -			/*
> -			 * We must hash before setting _Q_SLOW_VAL, such that
> -			 * when we observe _Q_SLOW_VAL in __pv_queued_spin_unlock()
> -			 * we'll be sure to be able to observe our hash entry.
> -			 *
> -			 *   [S] <hash>                 [Rmw] l->locked == _Q_SLOW_VAL
> -			 *       MB                           RMB
> -			 * [RmW] l->locked = _Q_SLOW_VAL  [L] <unhash>
> -			 *
> -			 * Matches the smp_rmb() in __pv_queued_spin_unlock().
> -			 */
> -			if (xchg(&l->locked, _Q_SLOW_VAL) == 0) {
> -				/*
> -				 * 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);
> -				goto gotlock;
> -			}
> +		/*
> +		 * Ooh, unlocked, try and grab it.
> +		 */
> +		case 0:
> +			continue;
>   		}
> -		WRITE_ONCE(pn->state, vcpu_hashed);
> +
> +		WRITE_ONCE(pn->state, vcpu_head_halted);
>   		qstat_inc(qstat_pv_wait_head, true);
>   		qstat_inc(qstat_pv_wait_again, waitcnt);
>   		pv_wait(&l->locked, _Q_SLOW_VAL);
> @@ -480,7 +475,7 @@ __pv_queued_spin_unlock_slowpath(struct
>   	struct __qspinlock *l = (void *)lock;
>   	struct pv_node *node;
>
> -	if (unlikely(locked != _Q_SLOW_VAL)) {
> +	if (unlikely(locked != _Q_SLOW_VAL && locked != _Q_HASH_VAL)) {
>   		WARN(!debug_locks_silent,
>   		     "pvqspinlock: lock 0x%lx has corrupted value 0x%x!\n",
>   		     (unsigned long)lock, atomic_read(&lock->val));
> @@ -488,18 +483,17 @@ __pv_queued_spin_unlock_slowpath(struct
>   	}
>
>   	/*
> -	 * A failed cmpxchg doesn't provide any memory-ordering guarantees,
> -	 * so we need a barrier to order the read of the node data in
> -	 * pv_unhash *after* we've read the lock being _Q_SLOW_VAL.
> -	 *
> -	 * Matches the cmpxchg() in pv_wait_head_or_lock() setting _Q_SLOW_VAL.
> +	 * Wait until the hash-bucket is complete.
>   	 */
> -	smp_rmb();
> +	while (READ_ONCE(l->locked) == _Q_HASH_VAL)
> +		cpu_relax();
>
>   	/*
> -	 * Since the above failed to release, this must be the SLOW path.
> -	 * Therefore start by looking up the blocked node and unhashing it.
> +	 * Must first observe _Q_SLOW_VAL in order to observe
> +	 * consistent hash bucket.
>   	 */
> +	smp_rmb();
> +
>   	node = pv_unhash(lock);
>
>   	/*
>

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web