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

Groups > linux.kernel > #1710880 > unrolled thread

Re: [RESEND PATCH v5] locking/pvqspinlock: Relax cmpxchg's to improve performance on some archs

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: [RESEND PATCH v5] locking/pvqspinlock: Relax cmpxchg's to  improve performance on some archs Will Deacon <will.deacon@arm.com> - 2017-08-14 14:10 +0200
    Re: [RESEND PATCH v5] locking/pvqspinlock: Relax cmpxchg's to improve  performance on some archs Waiman Long <longman@redhat.com> - 2017-08-14 17:10 +0200
      Re: [RESEND PATCH v5] locking/pvqspinlock: Relax cmpxchg's to  improve performance on some archs Will Deacon <will.deacon@arm.com> - 2017-08-14 18:10 +0200
    Re: [RESEND PATCH v5] locking/pvqspinlock: Relax cmpxchg's to  improve performance on some archs Peter Zijlstra <peterz@infradead.org> - 2017-08-14 20:50 +0200
      Re: [RESEND PATCH v5] locking/pvqspinlock: Relax cmpxchg's to  improve performance on some archs Will Deacon <will.deacon@arm.com> - 2017-08-15 20:50 +0200
        Re: [RESEND PATCH v5] locking/pvqspinlock: Relax cmpxchg's to  improve performance on some archs Peter Zijlstra <peterz@infradead.org> - 2017-08-21 13:00 +0200
          Re: [RESEND PATCH v5] locking/pvqspinlock: Relax cmpxchg's to  improve performance on some archs Will Deacon <will.deacon@arm.com> - 2017-08-21 20:10 +0200
            Re: [RESEND PATCH v5] locking/pvqspinlock: Relax cmpxchg's to  improve performance on some archs Peter Zijlstra <peterz@infradead.org> - 2017-08-21 21:30 +0200
              Re: [RESEND PATCH v5] locking/pvqspinlock: Relax cmpxchg's to  improve performance on some archs Peter Zijlstra <peterz@infradead.org> - 2017-08-21 21:50 +0200
                Re: [RESEND PATCH v5] locking/pvqspinlock: Relax cmpxchg's to improve  performance on some archs Waiman Long <longman@redhat.com> - 2017-08-22 17:40 +0200
              Re: [RESEND PATCH v5] locking/pvqspinlock: Relax cmpxchg's to  improve performance on some archs Will Deacon <will.deacon@arm.com> - 2017-08-22 12:50 +0200

#1710880 — Re: [RESEND PATCH v5] locking/pvqspinlock: Relax cmpxchg's to improve performance on some archs

On Fri, Aug 11, 2017 at 11:06:01AM +0200, Peter Zijlstra wrote:
> On Thu, Aug 10, 2017 at 02:18:30PM -0400, Waiman Long wrote:
> > On 08/10/2017 12:22 PM, Waiman Long wrote:
> > > On 08/10/2017 12:15 PM, Peter Zijlstra wrote:
> 
> > >> Might as well do an explicit:
> > >>
> > >> 	smp_mb__before_atomic()
> > >> 	cmpxchg_relaxed()
> > >> 	smp_mb__after_atomic()
> > >>
> > >> I suppose and not introduce new primitives.
> > 
> > I think we don't need smp_mb__after_atomic(). The read has to be fully
> > ordered, but the write part may not need it as the control dependency of
> > the old value should guard against incorrect action. Right?
> 
> You'd think that, but IIRC there was something funny about using the SC
> return flag for control dependencies. Will?

Yeah, that's right, you can't use the STXR status flag to create control
dependencies.

Will

[toc] | [next] | [standalone]

#1711006 — Re: [RESEND PATCH v5] locking/pvqspinlock: Relax cmpxchg's to improve performance on some archs

On 08/14/2017 08:01 AM, Will Deacon wrote:
> On Fri, Aug 11, 2017 at 11:06:01AM +0200, Peter Zijlstra wrote:
>> On Thu, Aug 10, 2017 at 02:18:30PM -0400, Waiman Long wrote:
>>> On 08/10/2017 12:22 PM, Waiman Long wrote:
>>>> On 08/10/2017 12:15 PM, Peter Zijlstra wrote:
>>>>> Might as well do an explicit:
>>>>>
>>>>> 	smp_mb__before_atomic()
>>>>> 	cmpxchg_relaxed()
>>>>> 	smp_mb__after_atomic()
>>>>>
>>>>> I suppose and not introduce new primitives.
>>> I think we don't need smp_mb__after_atomic(). The read has to be fully
>>> ordered, but the write part may not need it as the control dependency of
>>> the old value should guard against incorrect action. Right?
>> You'd think that, but IIRC there was something funny about using the SC
>> return flag for control dependencies. Will?
> Yeah, that's right, you can't use the STXR status flag to create control
> dependencies.
>
> Will

Actually, the code sequence that I plan to use are:

        smp_mb__before_atomic();
        if (cmpxchg_relaxed(&pn->state, vcpu_halted, vcpu_hashed)
            != vcpu_halted)
                return;

        WRITE_ONCE(l->locked, _Q_SLOW_VAL);
        (void)pv_hash(lock, pn);

I am planning to use the comparison of the returned value (pn->state)
again vcpu_halted as the control dependency. I don't see how the status
flag of STXR is affecting this.

Cheers,
Longman

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

#1711123

On Mon, Aug 14, 2017 at 11:01:10AM -0400, Waiman Long wrote:
> On 08/14/2017 08:01 AM, Will Deacon wrote:
> > On Fri, Aug 11, 2017 at 11:06:01AM +0200, Peter Zijlstra wrote:
> >> On Thu, Aug 10, 2017 at 02:18:30PM -0400, Waiman Long wrote:
> >>> On 08/10/2017 12:22 PM, Waiman Long wrote:
> >>>> On 08/10/2017 12:15 PM, Peter Zijlstra wrote:
> >>>>> Might as well do an explicit:
> >>>>>
> >>>>> 	smp_mb__before_atomic()
> >>>>> 	cmpxchg_relaxed()
> >>>>> 	smp_mb__after_atomic()
> >>>>>
> >>>>> I suppose and not introduce new primitives.
> >>> I think we don't need smp_mb__after_atomic(). The read has to be fully
> >>> ordered, but the write part may not need it as the control dependency of
> >>> the old value should guard against incorrect action. Right?
> >> You'd think that, but IIRC there was something funny about using the SC
> >> return flag for control dependencies. Will?
> > Yeah, that's right, you can't use the STXR status flag to create control
> > dependencies.
> >
> > Will
> 
> Actually, the code sequence that I plan to use are:
> 
>         smp_mb__before_atomic();
>         if (cmpxchg_relaxed(&pn->state, vcpu_halted, vcpu_hashed)
>             != vcpu_halted)
>                 return;
> 
>         WRITE_ONCE(l->locked, _Q_SLOW_VAL);
>         (void)pv_hash(lock, pn);
> 
> I am planning to use the comparison of the returned value (pn->state)
> again vcpu_halted as the control dependency. I don't see how the status
> flag of STXR is affecting this.

Thanks for the context. I agree that you've got a control dependency in this
case, so the WRITE_ONCE will be ordered after the LL part of the cmpxchg. It
could still be reordered with respect to the write part, however.

Will

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

#1711349

On Mon, Aug 14, 2017 at 01:01:22PM +0100, Will Deacon wrote:
> Yeah, that's right, you can't use the STXR status flag to create control
> dependencies.

Just for my elucidation; you can't use it to create a control dependency
on the store, but you can use it to create a control dependency on the
corresponding load, right?

Now, IIRC, we've defined control dependencies as being LOAD->STORE
ordering, so in that respect nothing is lost. But maybe we should
explicitly mention that if the LOAD is part of an (otherwise) atomic RmW
the STORE is not constrained.

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

#1712420

On Mon, Aug 14, 2017 at 08:47:11PM +0200, Peter Zijlstra wrote:
> On Mon, Aug 14, 2017 at 01:01:22PM +0100, Will Deacon wrote:
> > Yeah, that's right, you can't use the STXR status flag to create control
> > dependencies.
> 
> Just for my elucidation; you can't use it to create a control dependency
> on the store, but you can use it to create a control dependency on the
> corresponding load, right?

Hmm, sort of, but I'd say that the reads are really ordered due to
read-after-read ordering in that case. Control dependencies to loads
don't give you order.

> Now, IIRC, we've defined control dependencies as being LOAD->STORE
> ordering, so in that respect nothing is lost. But maybe we should
> explicitly mention that if the LOAD is part of an (otherwise) atomic RmW
> the STORE is not constrained.

I could well be misreading your suggestion, but it feels like that's too
weak. You can definitely still have control dependencies off the LL part
of the LL/SC pair, just not off the SC part.

E.g. this version of LB is forbidden on arm64:

P0:
if (atomic_inc_return_relaxed(&x) == 2)
	atomic_set(&y, 1);

P1:
if (atomic_inc_return_relaxed(&y) == 2)
	atomic_set(&x, 1);

Perhaps when you say "the STORE", you mean the store in the atomic RmW,
rather than the store in the LOAD->STORE control dependency?

Will

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

#1716310

On Tue, Aug 15, 2017 at 07:40:35PM +0100, Will Deacon wrote:
> On Mon, Aug 14, 2017 at 08:47:11PM +0200, Peter Zijlstra wrote:
> > On Mon, Aug 14, 2017 at 01:01:22PM +0100, Will Deacon wrote:
> > > Yeah, that's right, you can't use the STXR status flag to create control
> > > dependencies.
> > 
> > Just for my elucidation; you can't use it to create a control dependency
> > on the store, but you can use it to create a control dependency on the
> > corresponding load, right?
> 
> Hmm, sort of, but I'd say that the reads are really ordered due to
> read-after-read ordering in that case. Control dependencies to loads
> don't give you order.

No, I meant _from_ the LL load, not _to_ a later load.

> > Now, IIRC, we've defined control dependencies as being LOAD->STORE
> > ordering, so in that respect nothing is lost. But maybe we should
> > explicitly mention that if the LOAD is part of an (otherwise) atomic RmW
> > the STORE is not constrained.
> 
> I could well be misreading your suggestion, but it feels like that's too
> weak. You can definitely still have control dependencies off the LL part
> of the LL/SC pair, just not off the SC part.
> 
> E.g. this version of LB is forbidden on arm64:
> 
> P0:
> if (atomic_inc_return_relaxed(&x) == 2)
> 	atomic_set(&y, 1);
> 
> P1:
> if (atomic_inc_return_relaxed(&y) == 2)
> 	atomic_set(&x, 1);
> 
> Perhaps when you say "the STORE", you mean the store in the atomic RmW,
> rather than the store in the LOAD->STORE control dependency?

Yes. So I was looking to exclude (SC) STORE -> STORE order through
control dependencies.

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

#1716772

On Mon, Aug 21, 2017 at 12:55:08PM +0200, Peter Zijlstra wrote:
> On Tue, Aug 15, 2017 at 07:40:35PM +0100, Will Deacon wrote:
> > On Mon, Aug 14, 2017 at 08:47:11PM +0200, Peter Zijlstra wrote:
> > > On Mon, Aug 14, 2017 at 01:01:22PM +0100, Will Deacon wrote:
> > > > Yeah, that's right, you can't use the STXR status flag to create control
> > > > dependencies.
> > > 
> > > Just for my elucidation; you can't use it to create a control dependency
> > > on the store, but you can use it to create a control dependency on the
> > > corresponding load, right?
> > 
> > Hmm, sort of, but I'd say that the reads are really ordered due to
> > read-after-read ordering in that case. Control dependencies to loads
> > don't give you order.
> 
> No, I meant _from_ the LL load, not _to_ a later load.

Sorry, I'm still not following enough to give you a definitive answer on
that. Could you give an example, please? These sequences usually run in
a loop, so the conditional branch back (based on the status flag) is where
the read-after-read comes in.

Any control dependencies from the loaded data exist regardless of the status
flag.

> > > Now, IIRC, we've defined control dependencies as being LOAD->STORE
> > > ordering, so in that respect nothing is lost. But maybe we should
> > > explicitly mention that if the LOAD is part of an (otherwise) atomic RmW
> > > the STORE is not constrained.
> > 
> > I could well be misreading your suggestion, but it feels like that's too
> > weak. You can definitely still have control dependencies off the LL part
> > of the LL/SC pair, just not off the SC part.
> > 
> > E.g. this version of LB is forbidden on arm64:
> > 
> > P0:
> > if (atomic_inc_return_relaxed(&x) == 2)
> > 	atomic_set(&y, 1);
> > 
> > P1:
> > if (atomic_inc_return_relaxed(&y) == 2)
> > 	atomic_set(&x, 1);
> > 
> > Perhaps when you say "the STORE", you mean the store in the atomic RmW,
> > rather than the store in the LOAD->STORE control dependency?
> 
> Yes. So I was looking to exclude (SC) STORE -> STORE order through
> control dependencies.

Ok, good.

Will

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

#1716799

On Mon, Aug 21, 2017 at 07:00:02PM +0100, Will Deacon wrote:
> > No, I meant _from_ the LL load, not _to_ a later load.
> 
> Sorry, I'm still not following enough to give you a definitive answer on
> that. Could you give an example, please? These sequences usually run in
> a loop, so the conditional branch back (based on the status flag) is where
> the read-after-read comes in.
> 
> Any control dependencies from the loaded data exist regardless of the status
> flag.

Basically what Waiman ended up doing, something like:

        if (cmpxchg_relaxed(&pn->state, vcpu_halted, vcpu_hashed) != vcpu_halted)
                return;

        WRITE_ONCE(l->locked, _Q_SLOW_VAL);

Where the STORE depends on the LL value being 'complete'.


For any RmW we can only create a control dependency from the LOAD. The
the same could be done for something like:

	if (atomic_inc_not_zero(&obj->refs))
		WRITE_ONCE(obj->foo, 1);

Where we only do the STORE if we acquire the reference. While the
WRITE_ONCE() will not be ordered against the increment, it is ordered
against the LL and we know it must not be 0.

Per the LL/SC loop we'll have observed a !0 value and committed the SC
(which need not be visible or ordered against any later store) but both
STORES (SC and the WRITE_ONCE) must be after the ->refs LOAD.

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

#1716822

On Mon, Aug 21, 2017 at 09:25:50PM +0200, Peter Zijlstra wrote:
> On Mon, Aug 21, 2017 at 07:00:02PM +0100, Will Deacon wrote:
> > > No, I meant _from_ the LL load, not _to_ a later load.
> > 
> > Sorry, I'm still not following enough to give you a definitive answer on
> > that. Could you give an example, please? These sequences usually run in
> > a loop, so the conditional branch back (based on the status flag) is where
> > the read-after-read comes in.
> > 
> > Any control dependencies from the loaded data exist regardless of the status
> > flag.
> 
> Basically what Waiman ended up doing, something like:
> 
>         if (cmpxchg_relaxed(&pn->state, vcpu_halted, vcpu_hashed) != vcpu_halted)
>                 return;
> 
>         WRITE_ONCE(l->locked, _Q_SLOW_VAL);
> 
> Where the STORE depends on the LL value being 'complete'.
> 
> 
> For any RmW we can only create a control dependency from the LOAD. The
> the same could be done for something like:
> 
> 	if (atomic_inc_not_zero(&obj->refs))
> 		WRITE_ONCE(obj->foo, 1);

Obviously I meant the hypothetical atomic_inc_not_zero_relaxed() here,
otherwise all the implied smp_mb() spoil the game.

> Where we only do the STORE if we acquire the reference. While the
> WRITE_ONCE() will not be ordered against the increment, it is ordered
> against the LL and we know it must not be 0.
> 
> Per the LL/SC loop we'll have observed a !0 value and committed the SC
> (which need not be visible or ordered against any later store) but both
> STORES (SC and the WRITE_ONCE) must be after the ->refs LOAD.

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

#1717505 — Re: [RESEND PATCH v5] locking/pvqspinlock: Relax cmpxchg's to improve performance on some archs

On 08/21/2017 03:42 PM, Peter Zijlstra wrote:
> On Mon, Aug 21, 2017 at 09:25:50PM +0200, Peter Zijlstra wrote:
>> On Mon, Aug 21, 2017 at 07:00:02PM +0100, Will Deacon wrote:
>>>> No, I meant _from_ the LL load, not _to_ a later load.
>>> Sorry, I'm still not following enough to give you a definitive answer on
>>> that. Could you give an example, please? These sequences usually run in
>>> a loop, so the conditional branch back (based on the status flag) is where
>>> the read-after-read comes in.
>>>
>>> Any control dependencies from the loaded data exist regardless of the status
>>> flag.
>> Basically what Waiman ended up doing, something like:
>>
>>         if (cmpxchg_relaxed(&pn->state, vcpu_halted, vcpu_hashed) != vcpu_halted)
>>                 return;
>>
>>         WRITE_ONCE(l->locked, _Q_SLOW_VAL);
>>
>> Where the STORE depends on the LL value being 'complete'.
>>

pn->state == vcpu_halted is the prerequisite of putting _Q_SLOW_VAL into
the lock. The order of writing vcpu_hashed into pn->state doesn't really
matter. The cmpxchg_relaxed() here should synchronize with the cmpxchg()
in pv_wait_node().

Cheers,
Longman

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

#1717306

On Mon, Aug 21, 2017 at 09:25:50PM +0200, Peter Zijlstra wrote:
> On Mon, Aug 21, 2017 at 07:00:02PM +0100, Will Deacon wrote:
> > > No, I meant _from_ the LL load, not _to_ a later load.
> > 
> > Sorry, I'm still not following enough to give you a definitive answer on
> > that. Could you give an example, please? These sequences usually run in
> > a loop, so the conditional branch back (based on the status flag) is where
> > the read-after-read comes in.
> > 
> > Any control dependencies from the loaded data exist regardless of the status
> > flag.
> 
> Basically what Waiman ended up doing, something like:
> 
>         if (cmpxchg_relaxed(&pn->state, vcpu_halted, vcpu_hashed) != vcpu_halted)
>                 return;
> 
>         WRITE_ONCE(l->locked, _Q_SLOW_VAL);
> 
> Where the STORE depends on the LL value being 'complete'.

Yup, that's ordered as you would expect. Thanks for the example!

Will

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web