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

Groups > linux.kernel > #1197911 > unrolled thread

[PATCH v4 1/7] locking/pvqspinlock: Unconditional PV kick with _Q_SLOW_VAL

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 v4 1/7] locking/pvqspinlock: Unconditional PV kick with _Q_SLOW_VAL Waiman Long <Waiman.Long@hp.com> - 2015-08-01 04:30 +0200
    RE: [PATCH v4 1/7] locking/pvqspinlock: Unconditional PV kick with  _Q_SLOW_VAL "Long, Wai Man" <waiman.long@hp.com> - 2015-08-01 22:20 +0200
    Re: [PATCH v4 1/7] locking/pvqspinlock: Unconditional PV kick with  _Q_SLOW_VAL Peter Zijlstra <peterz@infradead.org> - 2015-08-02 00:30 +0200
      Re: [PATCH v4 1/7] locking/pvqspinlock: Unconditional PV kick with  _Q_SLOW_VAL Davidlohr Bueso <dave@stgolabs.net> - 2015-08-03 20:30 +0200
        Re: [PATCH v4 1/7] locking/pvqspinlock: Unconditional PV kick with  _Q_SLOW_VAL Peter Zijlstra <peterz@infradead.org> - 2015-08-03 20:40 +0200
          Re: [PATCH v4 1/7] locking/pvqspinlock: Unconditional PV kick with  _Q_SLOW_VAL Davidlohr Bueso <dave@stgolabs.net> - 2015-08-03 21:10 +0200
            Re: [PATCH v4 1/7] locking/pvqspinlock: Unconditional PV kick with  _Q_SLOW_VAL Peter Zijlstra <peterz@infradead.org> - 2015-08-03 22:00 +0200
      Re: [PATCH v4 1/7] locking/pvqspinlock: Unconditional PV kick with  _Q_SLOW_VAL Waiman Long <waiman.long@hp.com> - 2015-08-04 05:30 +0200

#1197911 — [PATCH v4 1/7] locking/pvqspinlock: Unconditional PV kick with _Q_SLOW_VAL

The smp_store_release() is not a full barrier. In order to avoid missed
wakeup, we may need to add memory barrier around locked and cpu state
variables adding to complexity. As the chance of spurious wakeup is very
low, it is easier and safer to just do an unconditional kick at unlock
time.

Signed-off-by: Waiman Long <Waiman.Long@hp.com>
---
 kernel/locking/qspinlock_paravirt.h |   11 ++++++++---
 1 files changed, 8 insertions(+), 3 deletions(-)

diff --git a/kernel/locking/qspinlock_paravirt.h b/kernel/locking/qspinlock_paravirt.h
index 15d3733..2dd4b39 100644
--- a/kernel/locking/qspinlock_paravirt.h
+++ b/kernel/locking/qspinlock_paravirt.h
@@ -240,7 +240,6 @@ static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node)
 			cpu_relax();
 		}
 
-		WRITE_ONCE(pn->state, vcpu_halted);
 		if (!lp) { /* ONCE */
 			lp = pv_hash(lock, pn);
 			/*
@@ -320,9 +319,15 @@ __visible void __pv_queued_spin_unlock(struct qspinlock *lock)
 	/*
 	 * At this point the memory pointed at by lock can be freed/reused,
 	 * however we can still use the pv_node to kick the CPU.
+	 *
+	 * As smp_store_release() is not a full barrier, adding a check to
+	 * the node->state doesn't guarantee the checking is really done
+	 * after clearing the lock byte since they are in 2 separate
+	 * cachelines and so hardware can reorder them. So either we insert
+	 * memory barrier here and in the corresponding pv_wait_head()
+	 * function or we do an unconditional kick which is what is done here.
 	 */
-	if (READ_ONCE(node->state) == vcpu_halted)
-		pv_kick(node->cpu);
+	pv_kick(node->cpu);
 }
 /*
  * Include the architecture specific callee-save thunk of the
-- 
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]

#1198048 — RE: [PATCH v4 1/7] locking/pvqspinlock: Unconditional PV kick with _Q_SLOW_VAL

RGF2aWRsb2hyLA0KDQpJIGFtIHNvcnJ5IHRoYXQgSSBmb3Jnb3QgdG8gcHV0IGluIHlvdXIgdGFn
Lg0KDQpDaGVlcnMsDQpMb25nbWFuDQoNCi0tLS0tT3JpZ2luYWwgTWVzc2FnZS0tLS0tDQpGcm9t
OiBsaW51eC1rZXJuZWwtb3duZXJAdmdlci5rZXJuZWwub3JnIFttYWlsdG86bGludXgta2VybmVs
LW93bmVyQHZnZXIua2VybmVsLm9yZ10gT24gQmVoYWxmIE9mIERhdmlkbG9ociBCdWVzbw0KU2Vu
dDogU2F0dXJkYXksIEF1Z3VzdCAwMSwgMjAxNSAyOjAxIFBNDQpUbzogTG9uZywgV2FpIE1hbg0K
Q2M6IFBldGVyIFppamxzdHJhOyBJbmdvIE1vbG5hcjsgVGhvbWFzIEdsZWl4bmVyOyBILiBQZXRl
ciBBbnZpbjsgeDg2QGtlcm5lbC5vcmc7IGxpbnV4LWtlcm5lbEB2Z2VyLmtlcm5lbC5vcmc7IE5v
cnRvbiwgU2NvdHQgSjsgSGF0Y2gsIERvdWdsYXMgQiAoSFBTIExpbnV4IFBNKQ0KU3ViamVjdDog
UmU6IFtQQVRDSCB2NCAxLzddIGxvY2tpbmcvcHZxc3BpbmxvY2s6IFVuY29uZGl0aW9uYWwgUFYg
a2ljayB3aXRoIF9RX1NMT1dfVkFMDQoNCk9uIEZyaSwgMjAxNS0wNy0zMSBhdCAyMjoyMSAtMDQw
MCwgV2FpbWFuIExvbmcgd3JvdGU6DQo+IFRoZSBzbXBfc3RvcmVfcmVsZWFzZSgpIGlzIG5vdCBh
IGZ1bGwgYmFycmllci4gSW4gb3JkZXIgdG8gYXZvaWQgDQo+IG1pc3NlZCB3YWtldXAsIHdlIG1h
eSBuZWVkIHRvIGFkZCBtZW1vcnkgYmFycmllciBhcm91bmQgbG9ja2VkIGFuZCBjcHUgDQo+IHN0
YXRlIHZhcmlhYmxlcyBhZGRpbmcgdG8gY29tcGxleGl0eS4gQXMgdGhlIGNoYW5jZSBvZiBzcHVy
aW91cyB3YWtldXAgDQo+IGlzIHZlcnkgbG93LCBpdCBpcyBlYXNpZXIgYW5kIHNhZmVyIHRvIGp1
c3QgZG8gYW4gdW5jb25kaXRpb25hbCBraWNrIA0KPiBhdCB1bmxvY2sgdGltZS4NCj4gDQo+IFNp
Z25lZC1vZmYtYnk6IFdhaW1hbiBMb25nIDxXYWltYW4uTG9uZ0BocC5jb20+DQoNClBsZWFzZSBr
ZWVwIHRhZ3MgZnJvbSBwcmV2aW91cyB2ZXJzaW9ucyA7KQ0KDQotLQ0KVG8gdW5zdWJzY3JpYmUg
ZnJvbSB0aGlzIGxpc3Q6IHNlbmQgdGhlIGxpbmUgInVuc3Vic2NyaWJlIGxpbnV4LWtlcm5lbCIg
aW4gdGhlIGJvZHkgb2YgYSBtZXNzYWdlIHRvIG1ham9yZG9tb0B2Z2VyLmtlcm5lbC5vcmcgTW9y
ZSBtYWpvcmRvbW8gaW5mbyBhdCAgaHR0cDovL3ZnZXIua2VybmVsLm9yZy9tYWpvcmRvbW8taW5m
by5odG1sDQpQbGVhc2UgcmVhZCB0aGUgRkFRIGF0ICBodHRwOi8vd3d3LnR1eC5vcmcvbGttbC8N
Cg==
--
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]

#1198356 — Re: [PATCH v4 1/7] locking/pvqspinlock: Unconditional PV kick with _Q_SLOW_VAL

On Fri, Jul 31, 2015 at 10:21:58PM -0400, Waiman Long wrote:
> The smp_store_release() is not a full barrier. In order to avoid missed
> wakeup, we may need to add memory barrier around locked and cpu state
> variables adding to complexity. As the chance of spurious wakeup is very
> low, it is easier and safer to just do an unconditional kick at unlock
> time.
> 
> Signed-off-by: Waiman Long <Waiman.Long@hp.com>
> ---
>  kernel/locking/qspinlock_paravirt.h |   11 ++++++++---
>  1 files changed, 8 insertions(+), 3 deletions(-)
> 
> diff --git a/kernel/locking/qspinlock_paravirt.h b/kernel/locking/qspinlock_paravirt.h
> index 15d3733..2dd4b39 100644
> --- a/kernel/locking/qspinlock_paravirt.h
> +++ b/kernel/locking/qspinlock_paravirt.h
> @@ -240,7 +240,6 @@ static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node)
>  			cpu_relax();
>  		}
>  
> -		WRITE_ONCE(pn->state, vcpu_halted);
>  		if (!lp) { /* ONCE */
>  			lp = pv_hash(lock, pn);
>  			/*
> @@ -320,9 +319,15 @@ __visible void __pv_queued_spin_unlock(struct qspinlock *lock)
>  	/*
>  	 * At this point the memory pointed at by lock can be freed/reused,
>  	 * however we can still use the pv_node to kick the CPU.
> +	 *
> +	 * As smp_store_release() is not a full barrier, adding a check to
> +	 * the node->state doesn't guarantee the checking is really done
> +	 * after clearing the lock byte

This is true, but _WHY_ is that a problem ?

                                         since they are in 2 separate
> +	 * cachelines and so hardware can reorder them. 

That's just gibberish, even in the same cacheline stuff can get
reordered.

                                                        So either we insert
> +	 * memory barrier here and in the corresponding pv_wait_head()
> +	 * function or we do an unconditional kick which is what is done here.

why, why why ? You've added words, but you've not actually described
what the problem is you're trying to fix.

AFAICT the only thing we really care about here is that the load in
question happens _after_ we observe SLOW, and that is still true.

The order against the unlock is irrelevant.

So we set ->state before we hash and before we set SLOW. Given that
we've seen SLOW, we must therefore also see ->state.

If ->state == halted, this means the CPU in question is blocked and the
pv_node will not get re-used -- if it does get re-used, it wasn't
blocked and we don't care either.

Therefore, ->cpu is stable and we'll kick it into action.

How do you end up not waking a waiting cpu? Explain that.

>  	 */
> -	if (READ_ONCE(node->state) == vcpu_halted)
> -		pv_kick(node->cpu);
> +	pv_kick(node->cpu);
>  }

Also, this patch clearly isn't against my tree.

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

#1199149 — Re: [PATCH v4 1/7] locking/pvqspinlock: Unconditional PV kick with _Q_SLOW_VAL

On Sun, 2015-08-02 at 00:29 +0200, Peter Zijlstra wrote:
> That's just gibberish, even in the same cacheline stuff can get
> reordered.

true dat

> 
>                                                         So either we insert
> > +	 * memory barrier here and in the corresponding pv_wait_head()
> > +	 * function or we do an unconditional kick which is what is done here.
> 
> why, why why ? You've added words, but you've not actually described
> what the problem is you're trying to fix.
> 
> AFAICT the only thing we really care about here is that the load in
> question happens _after_ we observe SLOW, and that is still true.
> 
> The order against the unlock is irrelevant.
> 
> So we set ->state before we hash and before we set SLOW. Given that
> we've seen SLOW, we must therefore also see ->state.
> 
> If ->state == halted, this means the CPU in question is blocked and the
> pv_node will not get re-used -- if it does get re-used, it wasn't
> blocked and we don't care either.

Right, if it does get re-used, we were burning SPIN_THRESHOLD and racing
only wastes a few spins, afaict. In fact this is explicitly stated:

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

The thing I like about this patch is that it simplifies the
pv_kick/pv_wait flow, not having to depend on minutia like ->state
checking. But the condition about spurious wakeups is already there, so
really nothing changes.

Thanks,
Davidlohr

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

#1199170 — Re: [PATCH v4 1/7] locking/pvqspinlock: Unconditional PV kick with _Q_SLOW_VAL

On Mon, Aug 03, 2015 at 11:22:09AM -0700, Davidlohr Bueso wrote:
> On Sun, 2015-08-02 at 00:29 +0200, Peter Zijlstra wrote:
> > That's just gibberish, even in the same cacheline stuff can get
> > reordered.
> 
> true dat
> 
> > 
> >                                                         So either we insert
> > > +	 * memory barrier here and in the corresponding pv_wait_head()
> > > +	 * function or we do an unconditional kick which is what is done here.
> > 
> > why, why why ? You've added words, but you've not actually described
> > what the problem is you're trying to fix.
> > 
> > AFAICT the only thing we really care about here is that the load in
> > question happens _after_ we observe SLOW, and that is still true.
> > 
> > The order against the unlock is irrelevant.
> > 
> > So we set ->state before we hash and before we set SLOW. Given that
> > we've seen SLOW, we must therefore also see ->state.
> > 
> > If ->state == halted, this means the CPU in question is blocked and the
> > pv_node will not get re-used -- if it does get re-used, it wasn't
> > blocked and we don't care either.
> 
> Right, if it does get re-used, we were burning SPIN_THRESHOLD and racing
> only wastes a few spins, afaict. In fact this is explicitly stated:
> 
> 		/*
> 		 * 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.
> 		 */
> 
> The thing I like about this patch is that it simplifies the
> pv_kick/pv_wait flow, not having to depend on minutia like ->state
> checking. But the condition about spurious wakeups is already there, so
> really nothing changes.

OK, so there's no 'fix'? The patch claims we can loose a wakeup and I
just don't see how that is true.
--
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]

#1199192 — Re: [PATCH v4 1/7] locking/pvqspinlock: Unconditional PV kick with _Q_SLOW_VAL

On Mon, 2015-08-03 at 20:37 +0200, Peter Zijlstra wrote:
> OK, so there's no 'fix'? The patch claims we can loose a wakeup and I
> just don't see how that is true.

Taking another look, I think you could hit something like this:

CPU0 (lock):					CPU1 (unlock):
  pv_wait_head					  __pv_queued_spin_unlock
						    <load ->state> [bogus ->state != halted]
    <spin>					    smp_store_release(&l->locked, 0);
						    
    WRITE_ONCE(pn->state, vcpu_halted);             
    pv_wait(&l->locked, _Q_SLOW_VAL);		    if (->state == vcpu_halted)
					              pv_kick(node->cpu); <-- missing wakeup, never called

So basically you can miss a wakeup if node->state load is done while the
locking thread is spinning and hasn't gotten a chance to update the
state to halted. That would also imply that it occurs right when the
threshold limit is about to be reached.

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

#1199231 — Re: [PATCH v4 1/7] locking/pvqspinlock: Unconditional PV kick with _Q_SLOW_VAL

On Mon, Aug 03, 2015 at 12:09:42PM -0700, Davidlohr Bueso wrote:
> On Mon, 2015-08-03 at 20:37 +0200, Peter Zijlstra wrote:
> > OK, so there's no 'fix'? The patch claims we can loose a wakeup and I
> > just don't see how that is true.
> 
> Taking another look, I think you could hit something like this:
> 
> CPU0 (lock):					CPU1 (unlock):
>   pv_wait_head					  __pv_queued_spin_unlock
> 						    <load ->state> [bogus ->state != halted]

I don't think this can happen, see below, IF you take the slow path, you
_must_ see halted.

>     <spin>					    smp_store_release(&l->locked, 0);
> 						    
>     WRITE_ONCE(pn->state, vcpu_halted);             
>     pv_wait(&l->locked, _Q_SLOW_VAL);		    if (->state == vcpu_halted)
> 					              pv_kick(node->cpu); <-- missing wakeup, never called
> 
> So basically you can miss a wakeup if node->state load is done while the
> locking thread is spinning and hasn't gotten a chance to update the
> state to halted. That would also imply that it occurs right when the
> threshold limit is about to be reached.

	pv_wait_head()			__pv_queued_spin_unlock()

	[S] node->state = halted
	[S] hash(lock, node)
	    MB
	[S] ->locked = SLOW
	    MB
					[L] ->locked == SLOW
					    RMB
					[L] node = unhash(lock)
					[L] node->state == halted
					    RELEASE
					[S] ->locked = 0

					   kick(node->cpu)
	   CLI
	[L] ->locked

If we don't see SLOW, nothing to be done. If we do, we _must_ then also
see ->state == halted and will kick.

And note that the load of node->state _cannot_ be pushed up further, it
depends on the load of node, which in turn depends on the load of
->locked.

So I'm still not seeing it. You cannot miss a kick.
--
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]

#1199393 — Re: [PATCH v4 1/7] locking/pvqspinlock: Unconditional PV kick with _Q_SLOW_VAL

On 08/01/2015 06:29 PM, Peter Zijlstra wrote:
> On Fri, Jul 31, 2015 at 10:21:58PM -0400, Waiman Long wrote:
>> The smp_store_release() is not a full barrier. In order to avoid missed
>> wakeup, we may need to add memory barrier around locked and cpu state
>> variables adding to complexity. As the chance of spurious wakeup is very
>> low, it is easier and safer to just do an unconditional kick at unlock
>> time.
>>
>> Signed-off-by: Waiman Long<Waiman.Long@hp.com>
>> ---
>>   kernel/locking/qspinlock_paravirt.h |   11 ++++++++---
>>   1 files changed, 8 insertions(+), 3 deletions(-)
>>
>> diff --git a/kernel/locking/qspinlock_paravirt.h b/kernel/locking/qspinlock_paravirt.h
>> index 15d3733..2dd4b39 100644
>> --- a/kernel/locking/qspinlock_paravirt.h
>> +++ b/kernel/locking/qspinlock_paravirt.h
>> @@ -240,7 +240,6 @@ static void pv_wait_head(struct qspinlock *lock, struct mcs_spinlock *node)
>>   			cpu_relax();
>>   		}
>>
>> -		WRITE_ONCE(pn->state, vcpu_halted);
>>   		if (!lp) { /* ONCE */
>>   			lp = pv_hash(lock, pn);
>>   			/*
>> @@ -320,9 +319,15 @@ __visible void __pv_queued_spin_unlock(struct qspinlock *lock)
>>   	/*
>>   	 * At this point the memory pointed at by lock can be freed/reused,
>>   	 * however we can still use the pv_node to kick the CPU.
>> +	 *
>> +	 * As smp_store_release() is not a full barrier, adding a check to
>> +	 * the node->state doesn't guarantee the checking is really done
>> +	 * after clearing the lock byte
> This is true, but _WHY_ is that a problem ?
>
>                                           since they are in 2 separate
>> +	 * cachelines and so hardware can reorder them.
> That's just gibberish, even in the same cacheline stuff can get
> reordered.
>
>                                                          So either we insert
>> +	 * memory barrier here and in the corresponding pv_wait_head()
>> +	 * function or we do an unconditional kick which is what is done here.
> why, why why ? You've added words, but you've not actually described
> what the problem is you're trying to fix.
>
> AFAICT the only thing we really care about here is that the load in
> question happens _after_ we observe SLOW, and that is still true.
>
> The order against the unlock is irrelevant.
>
> So we set ->state before we hash and before we set SLOW. Given that
> we've seen SLOW, we must therefore also see ->state.
>
> If ->state == halted, this means the CPU in question is blocked and the
> pv_node will not get re-used -- if it does get re-used, it wasn't
> blocked and we don't care either.
>
> Therefore, ->cpu is stable and we'll kick it into action.
>
> How do you end up not waking a waiting cpu? Explain that.
>

Yes, it is safe in the current code. In some versions of my pvqspinlock 
patch, I was resetting the state back to running in pv_wait_head(). This 
causes race problem.

The current code, however, will not reset the state back to running and 
so the check is redundant. I will clarify that in the next patch.

>>   	*/
>> -	if (READ_ONCE(node->state) == vcpu_halted)
>> -		pv_kick(node->cpu);
>> +	pv_kick(node->cpu);
>>   }
> Also, this patch clearly isn't against my tree.
>

Yes, I was backing against the latest tip tree. As some of the files in 
the patch were modified in the latest tip tree, I will rebase my patch 
and update it.

Please let me know if I should be using your tree instead.

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