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

Groups > linux.kernel > #1406661 > unrolled thread

[PATCH] pv-qspinlock: Try to re-hash the lock after spurious_wakeup

Started byPan Xinhui <xinhui.pan@linux.vnet.ibm.com>
First post2016-05-25 08:20 +0200
Last post2016-05-30 11:00 +0200
Articles 5 — 3 participants

Back to article view | Back to linux.kernel

Contents

  [PATCH] pv-qspinlock: Try to re-hash the lock after spurious_wakeup Pan Xinhui <xinhui.pan@linux.vnet.ibm.com> - 2016-05-25 08:20 +0200
    Re: [PATCH] pv-qspinlock: Try to re-hash the lock after spurious_wakeup Waiman Long <waiman.long@hpe.com> - 2016-05-26 20:50 +0200
      Re: [PATCH] pv-qspinlock: Try to re-hash the lock after spurious_wakeup xinhui <xinhui.pan@linux.vnet.ibm.com> - 2016-05-27 12:40 +0200
        Re: [PATCH] pv-qspinlock: Try to re-hash the lock after spurious_wakeup Waiman Long <waiman.long@hpe.com> - 2016-05-28 05:50 +0200
          Re: [PATCH] pv-qspinlock: Try to re-hash the lock after spurious_wakeup xinhui <xinhui.pan@linux.vnet.ibm.com> - 2016-05-30 11:00 +0200

#1406661 — [PATCH] pv-qspinlock: Try to re-hash the lock after spurious_wakeup

FromPan Xinhui <xinhui.pan@linux.vnet.ibm.com>
Date2016-05-25 08:20 +0200
Subject[PATCH] pv-qspinlock: Try to re-hash the lock after spurious_wakeup
Message-ID<rCAkG-5XU-15@gated-at.bofh.it>
In pv_wait_head_or_lock, if there is a spurious_wakeup, and it fails to
get the lock as there is lock stealing, then after a short spin, we need
hash the lock again and enter pv_wait to yield.

Currently after a spurious_wakeup, as l->locked is not _Q_SLOW_VAL,
pv_wait might do nothing and return directly, that is not
paravirt-friendly because pv_wait_head_or_lock will just spin on the
lock then.

Signed-off-by: Pan Xinhui <xinhui.pan@linux.vnet.ibm.com>
---
 kernel/locking/qspinlock_paravirt.h | 39 +++++++++++++++++++++++++++++--------
 1 file changed, 31 insertions(+), 8 deletions(-)

diff --git a/kernel/locking/qspinlock_paravirt.h b/kernel/locking/qspinlock_paravirt.h
index 2bbffe4..3482ce9 100644
--- a/kernel/locking/qspinlock_paravirt.h
+++ b/kernel/locking/qspinlock_paravirt.h
@@ -429,14 +429,15 @@ static void pv_kick_node(struct qspinlock *lock, struct mcs_spinlock *node)
 		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.
+	 * Put the lock into the hash table and set the _Q_SLOW_VAL later
 	 */
-	WRITE_ONCE(l->locked, _Q_SLOW_VAL);
 	(void)pv_hash(lock, pn);
+
+	/*
+	* Match the smp_load_acquire in pv_wait_head_or_lock()
+	* We mush set the _Q_SLOW_VAL after hash.
+	*/
+	smp_store_release(&l->locked, _Q_SLOW_VAL);
 }
 
 /*
@@ -454,6 +455,7 @@ pv_wait_head_or_lock(struct qspinlock *lock, struct mcs_spinlock *node)
 	struct qspinlock **lp = NULL;
 	int waitcnt = 0;
 	int loop;
+	u8 lock_val;
 
 	/*
 	 * If pv_kick_node() already advanced our state, we don't need to
@@ -487,7 +489,7 @@ pv_wait_head_or_lock(struct qspinlock *lock, struct mcs_spinlock *node)
 		clear_pending(lock);
 
 
-		if (!lp) { /* ONCE */
+		if (!lp) {
 			lp = pv_hash(lock, pn);
 
 			/*
@@ -517,6 +519,13 @@ pv_wait_head_or_lock(struct qspinlock *lock, struct mcs_spinlock *node)
 		qstat_inc(qstat_pv_wait_again, waitcnt);
 
 		/*
+		* make sure pv_kick_node has hashed the lock, so after pv_wait
+		* if ->locked is not _Q_SLOW_VAL, we can hash the lock again.
+		*/
+		if (lp == (struct qspinlock **)1
+				&& smp_load_acquire(&l->locked) == _Q_SLOW_VAL)
+			lp = (struct qspinlock **)2;
+		/*
 		 * Pass in the previous node vCPU nmber which is likely to be
 		 * the lock holder vCPU. This additional information may help
 		 * the hypervisor to give more resource to that vCPU so that
@@ -525,13 +534,27 @@ pv_wait_head_or_lock(struct qspinlock *lock, struct mcs_spinlock *node)
 		 */
 		pv_wait(&l->locked, _Q_SLOW_VAL, pn->prev_cpu);
 
+		lock_val = READ_ONCE(l->locked);
+
+		/* if ->locked is zero, then lock owner has unhashed the lock
+		 * if ->locked is _Q_LOCKED_VAL,
+		 * 1) pv_kick_node didnot hash the lock, and lp != 0x1
+		 * 2) lock stealing, lock owner has unhashed the lock too
+		 * 3) race with pv_kick_node, if lp == 2, we know it has hashed
+		 * the lock and the lock is unhashed in unlock()
+		 * if ->lock is _Q_SLOW_VAL, spurious_wakeup?
+		*/
+		if (lock_val != _Q_SLOW_VAL) {
+			if (lock_val == 0 || lp != (struct qspinlock **)1)
+				lp = 0;
+		}
 		/*
 		 * The unlocker should have freed the lock before kicking the
 		 * CPU. So if the lock is still not free, it is a spurious
 		 * wakeup or another vCPU has stolen the lock. The current
 		 * vCPU should spin again.
 		 */
-		qstat_inc(qstat_pv_spurious_wakeup, READ_ONCE(l->locked));
+		qstat_inc(qstat_pv_spurious_wakeup, lock_val);
 	}
 
 	/*
-- 
1.9.1

[toc] | [next] | [standalone]

#1407666

FromWaiman Long <waiman.long@hpe.com>
Date2016-05-26 20:50 +0200
Message-ID<rD8w2-1sN-11@gated-at.bofh.it>
In reply to#1406661
On 05/25/2016 02:09 AM, Pan Xinhui wrote:
> In pv_wait_head_or_lock, if there is a spurious_wakeup, and it fails to
> get the lock as there is lock stealing, then after a short spin, we need
> hash the lock again and enter pv_wait to yield.
>
> Currently after a spurious_wakeup, as l->locked is not _Q_SLOW_VAL,
> pv_wait might do nothing and return directly, that is not
> paravirt-friendly because pv_wait_head_or_lock will just spin on the
> lock then.
>
> Signed-off-by: Pan Xinhui<xinhui.pan@linux.vnet.ibm.com>
> ---
>   kernel/locking/qspinlock_paravirt.h | 39 +++++++++++++++++++++++++++++--------
>   1 file changed, 31 insertions(+), 8 deletions(-)

Is this a problem you can easily reproduce on PPC? I have not observed 
this issue when testing on x86.

>
> diff --git a/kernel/locking/qspinlock_paravirt.h b/kernel/locking/qspinlock_paravirt.h
> index 2bbffe4..3482ce9 100644
> --- a/kernel/locking/qspinlock_paravirt.h
> +++ b/kernel/locking/qspinlock_paravirt.h
> @@ -429,14 +429,15 @@ static void pv_kick_node(struct qspinlock *lock, struct mcs_spinlock *node)
>   		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.
> +	 * Put the lock into the hash table and set the _Q_SLOW_VAL later
>   	 */
> -	WRITE_ONCE(l->locked, _Q_SLOW_VAL);
>   	(void)pv_hash(lock, pn);
> +
> +	/*
> +	* Match the smp_load_acquire in pv_wait_head_or_lock()
> +	* We mush set the _Q_SLOW_VAL after hash.
> +	*/
> +	smp_store_release(&l->locked, _Q_SLOW_VAL);
>   }
>
>   /*
> @@ -454,6 +455,7 @@ pv_wait_head_or_lock(struct qspinlock *lock, struct mcs_spinlock *node)
>   	struct qspinlock **lp = NULL;
>   	int waitcnt = 0;
>   	int loop;
> +	u8 lock_val;
>
>   	/*
>   	 * If pv_kick_node() already advanced our state, we don't need to
> @@ -487,7 +489,7 @@ pv_wait_head_or_lock(struct qspinlock *lock, struct mcs_spinlock *node)
>   		clear_pending(lock);
>
>
> -		if (!lp) { /* ONCE */
> +		if (!lp) {
>   			lp = pv_hash(lock, pn);
>
>   			/*
> @@ -517,6 +519,13 @@ pv_wait_head_or_lock(struct qspinlock *lock, struct mcs_spinlock *node)
>   		qstat_inc(qstat_pv_wait_again, waitcnt);
>
>   		/*
> +		* make sure pv_kick_node has hashed the lock, so after pv_wait
> +		* if ->locked is not _Q_SLOW_VAL, we can hash the lock again.
> +		*/
> +		if (lp == (struct qspinlock **)1
> +				&&  smp_load_acquire(&l->locked) == _Q_SLOW_VAL)
> +			lp = (struct qspinlock **)2;
> +		/*
>   		 * Pass in the previous node vCPU nmber which is likely to be
>   		 * the lock holder vCPU. This additional information may help
>   		 * the hypervisor to give more resource to that vCPU so that
> @@ -525,13 +534,27 @@ pv_wait_head_or_lock(struct qspinlock *lock, struct mcs_spinlock *node)
>   		 */
>   		pv_wait(&l->locked, _Q_SLOW_VAL, pn->prev_cpu);
>
> +		lock_val = READ_ONCE(l->locked);
> +
> +		/* if ->locked is zero, then lock owner has unhashed the lock
> +		 * if ->locked is _Q_LOCKED_VAL,
> +		 * 1) pv_kick_node didnot hash the lock, and lp != 0x1
> +		 * 2) lock stealing, lock owner has unhashed the lock too
> +		 * 3) race with pv_kick_node, if lp == 2, we know it has hashed
> +		 * the lock and the lock is unhashed in unlock()
> +		 * if ->lock is _Q_SLOW_VAL, spurious_wakeup?
> +		*/
> +		if (lock_val != _Q_SLOW_VAL) {
> +			if (lock_val == 0 || lp != (struct qspinlock **)1)
> +				lp = 0;
> +		}

It is a bit hard to verify the correctness of these checks as many 
variables are involved. Instead, I posted an alternative way to solve 
this problem by focusing just on the atomic setting of _Q_SLOW_VAL which 
should be easier to understand and verified. Would you mind testing that 
patch to see if it can fix the problem that you see?

Cheers,
Longman

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

#1407987

Fromxinhui <xinhui.pan@linux.vnet.ibm.com>
Date2016-05-27 12:40 +0200
Message-ID<rDnln-2f3-3@gated-at.bofh.it>
In reply to#1407666
On 2016年05月27日 02:31, Waiman Long wrote:
> On 05/25/2016 02:09 AM, Pan Xinhui wrote:
>> In pv_wait_head_or_lock, if there is a spurious_wakeup, and it fails to
>> get the lock as there is lock stealing, then after a short spin, we need
>> hash the lock again and enter pv_wait to yield.
>>
>> Currently after a spurious_wakeup, as l->locked is not _Q_SLOW_VAL,
>> pv_wait might do nothing and return directly, that is not
>> paravirt-friendly because pv_wait_head_or_lock will just spin on the
>> lock then.
>>
>> Signed-off-by: Pan Xinhui<xinhui.pan@linux.vnet.ibm.com>
>> ---
>>   kernel/locking/qspinlock_paravirt.h | 39 +++++++++++++++++++++++++++++--------
>>   1 file changed, 31 insertions(+), 8 deletions(-)
>
> Is this a problem you can easily reproduce on PPC? I have not observed this issue when testing on x86.
>
Hi, Waiman
	I notice the spurious_wakeup count is very high when I do benchmark tests and stress tests. So after a simple investigation,
I find pv_wait_head_or_lock() just keep loops.

	Here is my story, in my pv-qspinlcok patchset V1&&v2, pv_wait on ppc ignore the first two parameters of *ptr and val, that makes lock_stealing hit too much.
and when I change SPIN_THRESHOLD to a small value, system is very much unstable because waiter will enter pv_wait quickly and no one will kick waiter's cpu if
we enter pv_wait twice thanks to the lock_stealing.
	So what I do in my pv-qspinlcok patchset V3 is that add if (*ptr == val) in pv_wait. However as I mentioned above, then spurious_wakeup count is too high, that also means our cpu
slice is wasted.
	
thanks
xinhui
>> diff --git a/kernel/locking/qspinlock_paravirt.h b/kernel/locking/qspinlock_paravirt.h
>> index 2bbffe4..3482ce9 100644
>> --- a/kernel/locking/qspinlock_paravirt.h
>> +++ b/kernel/locking/qspinlock_paravirt.h
>> @@ -429,14 +429,15 @@ static void pv_kick_node(struct qspinlock *lock, struct mcs_spinlock *node)
>>           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.
>> +     * Put the lock into the hash table and set the _Q_SLOW_VAL later
>>        */
>> -    WRITE_ONCE(l->locked, _Q_SLOW_VAL);
>>       (void)pv_hash(lock, pn);
>> +
>> +    /*
>> +    * Match the smp_load_acquire in pv_wait_head_or_lock()
>> +    * We mush set the _Q_SLOW_VAL after hash.
>> +    */
>> +    smp_store_release(&l->locked, _Q_SLOW_VAL);
>>   }
>>
>>   /*
>> @@ -454,6 +455,7 @@ pv_wait_head_or_lock(struct qspinlock *lock, struct mcs_spinlock *node)
>>       struct qspinlock **lp = NULL;
>>       int waitcnt = 0;
>>       int loop;
>> +    u8 lock_val;
>>
>>       /*
>>        * If pv_kick_node() already advanced our state, we don't need to
>> @@ -487,7 +489,7 @@ pv_wait_head_or_lock(struct qspinlock *lock, struct mcs_spinlock *node)
>>           clear_pending(lock);
>>
>>
>> -        if (!lp) { /* ONCE */
>> +        if (!lp) {
>>               lp = pv_hash(lock, pn);
>>
>>               /*
>> @@ -517,6 +519,13 @@ pv_wait_head_or_lock(struct qspinlock *lock, struct mcs_spinlock *node)
>>           qstat_inc(qstat_pv_wait_again, waitcnt);
>>
>>           /*
>> +        * make sure pv_kick_node has hashed the lock, so after pv_wait
>> +        * if ->locked is not _Q_SLOW_VAL, we can hash the lock again.
>> +        */
>> +        if (lp == (struct qspinlock **)1
>> +                &&  smp_load_acquire(&l->locked) == _Q_SLOW_VAL)
>> +            lp = (struct qspinlock **)2;
>> +        /*
>>            * Pass in the previous node vCPU nmber which is likely to be
>>            * the lock holder vCPU. This additional information may help
>>            * the hypervisor to give more resource to that vCPU so that
>> @@ -525,13 +534,27 @@ pv_wait_head_or_lock(struct qspinlock *lock, struct mcs_spinlock *node)
>>            */
>>           pv_wait(&l->locked, _Q_SLOW_VAL, pn->prev_cpu);
>>
>> +        lock_val = READ_ONCE(l->locked);
>> +
>> +        /* if ->locked is zero, then lock owner has unhashed the lock
>> +         * if ->locked is _Q_LOCKED_VAL,
>> +         * 1) pv_kick_node didnot hash the lock, and lp != 0x1
>> +         * 2) lock stealing, lock owner has unhashed the lock too
>> +         * 3) race with pv_kick_node, if lp == 2, we know it has hashed
>> +         * the lock and the lock is unhashed in unlock()
>> +         * if ->lock is _Q_SLOW_VAL, spurious_wakeup?
>> +        */
>> +        if (lock_val != _Q_SLOW_VAL) {
>> +            if (lock_val == 0 || lp != (struct qspinlock **)1)
>> +                lp = 0;
>> +        }
>
> It is a bit hard to verify the correctness of these checks as many variables are involved. Instead, I posted an alternative way to solve this problem by focusing just on the atomic setting of _Q_SLOW_VAL which should be easier to understand and verified. Would you mind testing that patch to see if it can fix the problem that you see?
>
> Cheers,
> Longman
>

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

#1408373

FromWaiman Long <waiman.long@hpe.com>
Date2016-05-28 05:50 +0200
Message-ID<rDDq9-3OF-1@gated-at.bofh.it>
In reply to#1407987
On 05/27/2016 06:32 AM, xinhui wrote:
>
> On 2016年05月27日 02:31, Waiman Long wrote:
>> On 05/25/2016 02:09 AM, Pan Xinhui wrote:
>>> In pv_wait_head_or_lock, if there is a spurious_wakeup, and it fails to
>>> get the lock as there is lock stealing, then after a short spin, we 
>>> need
>>> hash the lock again and enter pv_wait to yield.
>>>
>>> Currently after a spurious_wakeup, as l->locked is not _Q_SLOW_VAL,
>>> pv_wait might do nothing and return directly, that is not
>>> paravirt-friendly because pv_wait_head_or_lock will just spin on the
>>> lock then.
>>>
>>> Signed-off-by: Pan Xinhui<xinhui.pan@linux.vnet.ibm.com>
>>> ---
>>>   kernel/locking/qspinlock_paravirt.h | 39 
>>> +++++++++++++++++++++++++++++--------
>>>   1 file changed, 31 insertions(+), 8 deletions(-)
>>
>> Is this a problem you can easily reproduce on PPC? I have not 
>> observed this issue when testing on x86.
>>
> Hi, Waiman
>     I notice the spurious_wakeup count is very high when I do 
> benchmark tests and stress tests. So after a simple investigation,
> I find pv_wait_head_or_lock() just keep loops.
>

That shouldn't happen in normal case. When testing on x86, I typically 
get the following stat data for an over-commited guest:

pv_lock_slowpath=9256211
pv_lock_stealing=36398363
pv_spurious_wakeup=311
pv_wait_again=294
pv_wait_early=3255605
pv_wait_head=173
pv_wait_node=3256280

The queue head don't call pv_wait that often. There are a bit of 
spurious wakeup, but it is mostly caused by lock stealing. How long is a 
cpu_relax() in PPC takes?

>     Here is my story, in my pv-qspinlcok patchset V1&&v2, pv_wait on 
> ppc ignore the first two parameters of *ptr and val, that makes 
> lock_stealing hit too much.

The pvqspinlock code does depend on pv_wait() doing a final check to see 
if the lock value change. The code may not work reliably without that.

> and when I change SPIN_THRESHOLD to a small value, system is very much 
> unstable because waiter will enter pv_wait quickly and no one will 
> kick waiter's cpu if
> we enter pv_wait twice thanks to the lock_stealing.
>     So what I do in my pv-qspinlcok patchset V3 is that add if (*ptr 
> == val) in pv_wait. However as I mentioned above, then spurious_wakeup 
> count is too high, that also means our cpu
> slice is wasted.

The SPIN_THRESHOLD should be sufficiently big. A small value will cause 
too many waits and wake-up's which may not be good. Anyway, more testing 
and tuning may be needed to make the pvqspinlock code work well with PPC.

Cheers,
Longman

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

#1408894

Fromxinhui <xinhui.pan@linux.vnet.ibm.com>
Date2016-05-30 11:00 +0200
Message-ID<rErdg-1TA-51@gated-at.bofh.it>
In reply to#1408373

On 2016年05月28日 11:41, Waiman Long wrote:
> On 05/27/2016 06:32 AM, xinhui wrote:
>>
>> On 2016年05月27日 02:31, Waiman Long wrote:
>>> On 05/25/2016 02:09 AM, Pan Xinhui wrote:
>>>> In pv_wait_head_or_lock, if there is a spurious_wakeup, and it fails to
>>>> get the lock as there is lock stealing, then after a short spin, we need
>>>> hash the lock again and enter pv_wait to yield.
>>>>
>>>> Currently after a spurious_wakeup, as l->locked is not _Q_SLOW_VAL,
>>>> pv_wait might do nothing and return directly, that is not
>>>> paravirt-friendly because pv_wait_head_or_lock will just spin on the
>>>> lock then.
>>>>
>>>> Signed-off-by: Pan Xinhui<xinhui.pan@linux.vnet.ibm.com>
>>>> ---
>>>>   kernel/locking/qspinlock_paravirt.h | 39 +++++++++++++++++++++++++++++--------
>>>>   1 file changed, 31 insertions(+), 8 deletions(-)
>>>
>>> Is this a problem you can easily reproduce on PPC? I have not observed this issue when testing on x86.
>>>
>> Hi, Waiman
>>     I notice the spurious_wakeup count is very high when I do benchmark tests and stress tests. So after a simple investigation,
>> I find pv_wait_head_or_lock() just keep loops.
>>
>
> That shouldn't happen in normal case. When testing on x86, I typically get the following stat data for an over-commited guest:
>
> pv_lock_slowpath=9256211
> pv_lock_stealing=36398363
> pv_spurious_wakeup=311
> pv_wait_again=294
> pv_wait_early=3255605
> pv_wait_head=173
> pv_wait_node=3256280
>
OK, here is the result after run command  perf bench sched messaging -g 512

pv_lock_slowpath=2331407
pv_lock_stealing=192038
pv_spurious_wakeup=236319
pv_wait_again=215668
pv_wait_early=177299
pv_wait_head=9206
pv_wait_node=228781

> The queue head don't call pv_wait that often. There are a bit of spurious wakeup, but it is mostly caused by lock stealing. How long is a cpu_relax() in PPC takes?
>
946012160 cpu_relax loops with 10 seconds. So if SPIN_THRESHOLD is 1<<15, it costs 0.3ms to spin on the lock. How about x86?

And only 10134976 pv_wait/pv_kick hyper-call loops within 10 seconds. so every hyper-call itself(the so-called latency) costs less than 1us.

>>     Here is my story, in my pv-qspinlcok patchset V1&&v2, pv_wait on ppc ignore the first two parameters of *ptr and val, that makes lock_stealing hit too much.
>
> The pvqspinlock code does depend on pv_wait() doing a final check to see if the lock value change. The code may not work reliably without that.
>
agree, So pv_wait now do the check of *ptr and val.

>> and when I change SPIN_THRESHOLD to a small value, system is very much unstable because waiter will enter pv_wait quickly and no one will kick waiter's cpu if
>> we enter pv_wait twice thanks to the lock_stealing.
>>     So what I do in my pv-qspinlcok patchset V3 is that add if (*ptr == val) in pv_wait. However as I mentioned above, then spurious_wakeup count is too high, that also means our cpu
>> slice is wasted.
>
> The SPIN_THRESHOLD should be sufficiently big. A small value will cause too many waits and wake-up's which may not be good. Anyway, more testing and tuning may be needed to make the pvqspinlock code work well with PPC.
>
agree , but I think the SPIN_THRESHOLD (1<<15) for ppc is a little large.

I even come up with an idea that make SPIN_THRESHOLD an extern variable on ppc. But I am busy and I wonder if it's worth doing that.

> Cheers,
> Longman
>

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web