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

Groups > linux.kernel > #1270309 > unrolled thread

Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

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 4/4] locking: Introduce smp_cond_acquire() Peter Zijlstra <peterz@infradead.org> - 2015-11-16 17:00 +0100
    Re: [PATCH 4/4] locking: Introduce smp_cond_acquire() Peter Zijlstra <peterz@infradead.org> - 2015-11-16 17:10 +0100
      Re: [PATCH 4/4] locking: Introduce smp_cond_acquire() Will Deacon <will.deacon@arm.com> - 2015-11-16 17:30 +0100
        Re: [PATCH 4/4] locking: Introduce smp_cond_acquire() "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2015-11-16 17:50 +0100
          Re: [PATCH 4/4] locking: Introduce smp_cond_acquire() Will Deacon <will.deacon@arm.com> - 2015-11-16 17:50 +0100
            Re: [PATCH 4/4] locking: Introduce smp_cond_acquire() "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2015-11-16 18:20 +0100
        Re: [PATCH 4/4] locking: Introduce smp_cond_acquire() Linus Torvalds <torvalds@linux-foundation.org> - 2015-11-16 23:00 +0100
          Re: [PATCH 4/4] locking: Introduce smp_cond_acquire() Will Deacon <will.deacon@arm.com> - 2015-11-17 13:00 +0100
            Re: [PATCH 4/4] locking: Introduce smp_cond_acquire() "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2015-11-17 22:10 +0100
              Re: [PATCH 4/4] locking: Introduce smp_cond_acquire() Will Deacon <will.deacon@arm.com> - 2015-11-18 12:30 +0100
                Re: [PATCH 4/4] locking: Introduce smp_cond_acquire() Will Deacon <will.deacon@arm.com> - 2015-11-19 19:10 +0100
                  Re: [PATCH 4/4] locking: Introduce smp_cond_acquire() Peter Zijlstra <peterz@infradead.org> - 2015-11-20 11:20 +0100

#1270309 — Re: [PATCH 4/4] locking: Introduce smp_cond_acquire()

On Thu, Nov 12, 2015 at 10:21:39AM -0800, Linus Torvalds wrote:
> Now, the point of spin_unlock_wait() (and "spin_is_locked()") should
> generally be that you have some external ordering guarantee that
> guarantees that the lock has been taken. For example, for the IPC
> semaphores, we do either one of:
> 
>  (a) get large lock, then - once you hold that lock - wait for each small lock
> 
> or
> 
>  (b) get small lock, then - once you hold that lock - check that the
> largo lock is unlocked
> 
> and that's the case we should really worry about.  The other uses of
> spin_unlock_wait() should have similar "I have other reasons to know
> I've seen that the lock was taken, or will never be taken after this
> because XYZ".

I don't think this is true for the usage in do_exit(), we have no
knowledge on if pi_lock is taken or not. We just want to make sure that
_if_ it were taken, we wait until it is released.

But I'm not sure where task_work_run() sits, at first reading it appears
to also not be true -- there doesn't appear to be a reason we know a
lock to be held.

It does however appear true for the usage in completion_done(), where by
having tested x->done, we know a pi_lock _was_ held.

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

#1270318

On Mon, Nov 16, 2015 at 04:56:58PM +0100, Peter Zijlstra wrote:
> On Thu, Nov 12, 2015 at 10:21:39AM -0800, Linus Torvalds wrote:
> > Now, the point of spin_unlock_wait() (and "spin_is_locked()") should
> > generally be that you have some external ordering guarantee that
> > guarantees that the lock has been taken. For example, for the IPC
> > semaphores, we do either one of:
> > 
> >  (a) get large lock, then - once you hold that lock - wait for each small lock
> > 
> > or
> > 
> >  (b) get small lock, then - once you hold that lock - check that the
> > largo lock is unlocked
> > 
> > and that's the case we should really worry about.  The other uses of
> > spin_unlock_wait() should have similar "I have other reasons to know
> > I've seen that the lock was taken, or will never be taken after this
> > because XYZ".
> 
> I don't think this is true for the usage in do_exit(), we have no
> knowledge on if pi_lock is taken or not. We just want to make sure that
> _if_ it were taken, we wait until it is released.

And unless PPC would move to using RCsc locks with a SYNC in
spin_lock(), I don't think it makes sense to add
smp_mb__after_unlock_lock() to all tsk->pi_lock instances to fix this.
As that is far more expensive than flipping the exit path to do
spin_lock()+spin_unlock().
--
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]

#1270331

On Mon, Nov 16, 2015 at 05:04:45PM +0100, Peter Zijlstra wrote:
> On Mon, Nov 16, 2015 at 04:56:58PM +0100, Peter Zijlstra wrote:
> > On Thu, Nov 12, 2015 at 10:21:39AM -0800, Linus Torvalds wrote:
> > > Now, the point of spin_unlock_wait() (and "spin_is_locked()") should
> > > generally be that you have some external ordering guarantee that
> > > guarantees that the lock has been taken. For example, for the IPC
> > > semaphores, we do either one of:
> > > 
> > >  (a) get large lock, then - once you hold that lock - wait for each small lock
> > > 
> > > or
> > > 
> > >  (b) get small lock, then - once you hold that lock - check that the
> > > largo lock is unlocked
> > > 
> > > and that's the case we should really worry about.  The other uses of
> > > spin_unlock_wait() should have similar "I have other reasons to know
> > > I've seen that the lock was taken, or will never be taken after this
> > > because XYZ".
> > 
> > I don't think this is true for the usage in do_exit(), we have no
> > knowledge on if pi_lock is taken or not. We just want to make sure that
> > _if_ it were taken, we wait until it is released.
> 
> And unless PPC would move to using RCsc locks with a SYNC in
> spin_lock(), I don't think it makes sense to add
> smp_mb__after_unlock_lock() to all tsk->pi_lock instances to fix this.
> As that is far more expensive than flipping the exit path to do
> spin_lock()+spin_unlock().

... or we upgrade spin_unlock_wait to a LOCK operation, which might be
slightly cheaper than spin_lock()+spin_unlock().

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

#1270365

On Mon, Nov 16, 2015 at 04:24:53PM +0000, Will Deacon wrote:
> On Mon, Nov 16, 2015 at 05:04:45PM +0100, Peter Zijlstra wrote:
> > On Mon, Nov 16, 2015 at 04:56:58PM +0100, Peter Zijlstra wrote:
> > > On Thu, Nov 12, 2015 at 10:21:39AM -0800, Linus Torvalds wrote:
> > > > Now, the point of spin_unlock_wait() (and "spin_is_locked()") should
> > > > generally be that you have some external ordering guarantee that
> > > > guarantees that the lock has been taken. For example, for the IPC
> > > > semaphores, we do either one of:
> > > > 
> > > >  (a) get large lock, then - once you hold that lock - wait for each small lock
> > > > 
> > > > or
> > > > 
> > > >  (b) get small lock, then - once you hold that lock - check that the
> > > > largo lock is unlocked
> > > > 
> > > > and that's the case we should really worry about.  The other uses of
> > > > spin_unlock_wait() should have similar "I have other reasons to know
> > > > I've seen that the lock was taken, or will never be taken after this
> > > > because XYZ".
> > > 
> > > I don't think this is true for the usage in do_exit(), we have no
> > > knowledge on if pi_lock is taken or not. We just want to make sure that
> > > _if_ it were taken, we wait until it is released.
> > 
> > And unless PPC would move to using RCsc locks with a SYNC in
> > spin_lock(), I don't think it makes sense to add
> > smp_mb__after_unlock_lock() to all tsk->pi_lock instances to fix this.
> > As that is far more expensive than flipping the exit path to do
> > spin_lock()+spin_unlock().
> 
> ... or we upgrade spin_unlock_wait to a LOCK operation, which might be
> slightly cheaper than spin_lock()+spin_unlock().

Or we supply a heavyweight version of spin_unlock_wait() that forces
the cache miss.  But I bet that the difference in overhead between
spin_lock()+spin_unlock() and the heavyweight version would be down in
the noise.

							Thanx, Paul

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

#1270367

On Mon, Nov 16, 2015 at 08:44:43AM -0800, Paul E. McKenney wrote:
> On Mon, Nov 16, 2015 at 04:24:53PM +0000, Will Deacon wrote:
> > On Mon, Nov 16, 2015 at 05:04:45PM +0100, Peter Zijlstra wrote:
> > > On Mon, Nov 16, 2015 at 04:56:58PM +0100, Peter Zijlstra wrote:
> > > > On Thu, Nov 12, 2015 at 10:21:39AM -0800, Linus Torvalds wrote:
> > > > > Now, the point of spin_unlock_wait() (and "spin_is_locked()") should
> > > > > generally be that you have some external ordering guarantee that
> > > > > guarantees that the lock has been taken. For example, for the IPC
> > > > > semaphores, we do either one of:
> > > > > 
> > > > >  (a) get large lock, then - once you hold that lock - wait for each small lock
> > > > > 
> > > > > or
> > > > > 
> > > > >  (b) get small lock, then - once you hold that lock - check that the
> > > > > largo lock is unlocked
> > > > > 
> > > > > and that's the case we should really worry about.  The other uses of
> > > > > spin_unlock_wait() should have similar "I have other reasons to know
> > > > > I've seen that the lock was taken, or will never be taken after this
> > > > > because XYZ".
> > > > 
> > > > I don't think this is true for the usage in do_exit(), we have no
> > > > knowledge on if pi_lock is taken or not. We just want to make sure that
> > > > _if_ it were taken, we wait until it is released.
> > > 
> > > And unless PPC would move to using RCsc locks with a SYNC in
> > > spin_lock(), I don't think it makes sense to add
> > > smp_mb__after_unlock_lock() to all tsk->pi_lock instances to fix this.
> > > As that is far more expensive than flipping the exit path to do
> > > spin_lock()+spin_unlock().
> > 
> > ... or we upgrade spin_unlock_wait to a LOCK operation, which might be
> > slightly cheaper than spin_lock()+spin_unlock().
> 
> Or we supply a heavyweight version of spin_unlock_wait() that forces
> the cache miss.  But I bet that the difference in overhead between
> spin_lock()+spin_unlock() and the heavyweight version would be down in
> the noise.

I'm not so sure. If the lock is ticket-based, then spin_lock() has to
queue for its turn, whereas spin_unlock_wait could just wait for the
next unlock.

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

#1270398

On Mon, Nov 16, 2015 at 04:46:36PM +0000, Will Deacon wrote:
> On Mon, Nov 16, 2015 at 08:44:43AM -0800, Paul E. McKenney wrote:
> > On Mon, Nov 16, 2015 at 04:24:53PM +0000, Will Deacon wrote:
> > > On Mon, Nov 16, 2015 at 05:04:45PM +0100, Peter Zijlstra wrote:
> > > > On Mon, Nov 16, 2015 at 04:56:58PM +0100, Peter Zijlstra wrote:
> > > > > On Thu, Nov 12, 2015 at 10:21:39AM -0800, Linus Torvalds wrote:
> > > > > > Now, the point of spin_unlock_wait() (and "spin_is_locked()") should
> > > > > > generally be that you have some external ordering guarantee that
> > > > > > guarantees that the lock has been taken. For example, for the IPC
> > > > > > semaphores, we do either one of:
> > > > > > 
> > > > > >  (a) get large lock, then - once you hold that lock - wait for each small lock
> > > > > > 
> > > > > > or
> > > > > > 
> > > > > >  (b) get small lock, then - once you hold that lock - check that the
> > > > > > largo lock is unlocked
> > > > > > 
> > > > > > and that's the case we should really worry about.  The other uses of
> > > > > > spin_unlock_wait() should have similar "I have other reasons to know
> > > > > > I've seen that the lock was taken, or will never be taken after this
> > > > > > because XYZ".
> > > > > 
> > > > > I don't think this is true for the usage in do_exit(), we have no
> > > > > knowledge on if pi_lock is taken or not. We just want to make sure that
> > > > > _if_ it were taken, we wait until it is released.
> > > > 
> > > > And unless PPC would move to using RCsc locks with a SYNC in
> > > > spin_lock(), I don't think it makes sense to add
> > > > smp_mb__after_unlock_lock() to all tsk->pi_lock instances to fix this.
> > > > As that is far more expensive than flipping the exit path to do
> > > > spin_lock()+spin_unlock().
> > > 
> > > ... or we upgrade spin_unlock_wait to a LOCK operation, which might be
> > > slightly cheaper than spin_lock()+spin_unlock().
> > 
> > Or we supply a heavyweight version of spin_unlock_wait() that forces
> > the cache miss.  But I bet that the difference in overhead between
> > spin_lock()+spin_unlock() and the heavyweight version would be down in
> > the noise.
> 
> I'm not so sure. If the lock is ticket-based, then spin_lock() has to
> queue for its turn, whereas spin_unlock_wait could just wait for the
> next unlock.

Fair point, and it actually applies to high-contention spinlocks as well,
just a bit less deterministically.  OK, given that I believe that we do
see high contention on the lock in question, I withdraw any objections
to a heavy-weight form of spin_unlock_wait().

							Thanx, Paul

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

#1270628

On Mon, Nov 16, 2015 at 8:24 AM, Will Deacon <will.deacon@arm.com> wrote:
>
> ... or we upgrade spin_unlock_wait to a LOCK operation, which might be
> slightly cheaper than spin_lock()+spin_unlock().

So traditionally the real concern has been the cacheline ping-pong
part of spin_unlock_wait(). I think adding a memory barrier (that
doesn't force any exclusive states, just ordering) to it is fine, but
I don't think we want to necessarily have it have to get the cacheline
into exclusive state.

Because if spin_unlock_wait() ends up having to get the spinlock
cacheline (for example, by writing the same value back with a SC), I
don't think spin_unlock_wait() will really be all that much cheaper
than just getting the spinlock, and in that case we shouldn't play
complicated ordering games.

On another issue:

I'm also looking at the ARM documentation for strx, and the
_documentation_ says that it has no stronger ordering than a "store
release", but I'm starting to wonder if that is actually true.

Because I do end up thinking that it does have the same "control
dependency" to all subsequent writes (but not reads). So reads after
the SC can percolate up, but I think writes are restricted.

Why? In order for the SC to be able to return success, the write
itself may not have been actually done yet, but the cacheline for the
write must have successfully be turned into exclusive ownership.
Agreed?

That means that by the time a SC returns success, no other CPU can see
the old value of the spinlock any more. So by the time any subsequent
stores in the locked region can be visible to any other CPU's, the
locked value of the lock itself has to be visible too.

Agreed?

So I think that in effect, when a spinlock is implemnted with LL/SC,
the loads inside the locked region are only ordered wrt the acquire on
the LL, but the stores can be considered ordered wrt the SC.

No?

So I think a _successful_ SC - is still more ordered than just any
random store with release consistency.

Of course, I'm not sure that actually *helps* us, because I think the
problem tends to be loads in the locked region moving up earlier than
the actual store that sets the lock, but maybe it makes some
difference.

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

#1271117

Hi Linus,

On Mon, Nov 16, 2015 at 01:58:49PM -0800, Linus Torvalds wrote:
> On Mon, Nov 16, 2015 at 8:24 AM, Will Deacon <will.deacon@arm.com> wrote:
> >
> > ... or we upgrade spin_unlock_wait to a LOCK operation, which might be
> > slightly cheaper than spin_lock()+spin_unlock().
> 
> So traditionally the real concern has been the cacheline ping-pong
> part of spin_unlock_wait(). I think adding a memory barrier (that
> doesn't force any exclusive states, just ordering) to it is fine, but
> I don't think we want to necessarily have it have to get the cacheline
> into exclusive state.

The problem is, I don't think the memory-barrier buys you anything in
the context of Boqun's example. In fact, he already had smp_mb() either
side of the spin_unlock_wait() and its still broken on arm64 and ppc.

Paul is proposing adding a memory barrier after spin_lock() in the racing
thread, but I personally think people will forget to add that.

> Because if spin_unlock_wait() ends up having to get the spinlock
> cacheline (for example, by writing the same value back with a SC), I
> don't think spin_unlock_wait() will really be all that much cheaper
> than just getting the spinlock, and in that case we shouldn't play
> complicated ordering games.

It was the lock-fairness guarantees that I was concerned about. A
spin_lock could place you into a queue, so you're no longer waiting for
a single spin_unlock(), you're now waiting for *all* the spin_unlocks
by the CPUs preceding you in the queue.

> On another issue:
> 
> I'm also looking at the ARM documentation for strx, and the
> _documentation_ says that it has no stronger ordering than a "store
> release", but I'm starting to wonder if that is actually true.
> 
> Because I do end up thinking that it does have the same "control
> dependency" to all subsequent writes (but not reads). So reads after
> the SC can percolate up, but I think writes are restricted.
> 
> Why? In order for the SC to be able to return success, the write
> itself may not have been actually done yet, but the cacheline for the
> write must have successfully be turned into exclusive ownership.
> Agreed?

If the LL/SC logic hangs off the coherency logic, then yes, but there
are other ways to build this (using a seperate "exclusive monitor" block)
and the architecture caters for this, too. See below.

> That means that by the time a SC returns success, no other CPU can see
> the old value of the spinlock any more. So by the time any subsequent
> stores in the locked region can be visible to any other CPU's, the
> locked value of the lock itself has to be visible too.
> 
> Agreed?

No. A successful SC is *not* multi-copy atomic, but you're right to
point out that it provides more guarantees than a plain store. In
particular, a successful SC cannot return its success value until its
corresponding write has fixed its place in the coherence order for the
location that it is updating.

To be more concrete (simplified AArch64 asm, X1 and X2 hold addresses of
zero-initialised locations):


P0
LDXR	X0, [X1]
ADD	X0, X0, #1
STXR	X0, [X1]	// Succeeds

P1
LDR	X0, [X1]	// Reads 1
<dependency>
STR	#1, [X2]

P2
LDR	X0, [X2]	// Reads 1
<dependency>
LDR	X0, [X1]	// **Not required to read 1**


However:

P0
LDXR	X0, [X1]
ADD	X0, X0, #1
STXR	X0, [X1]	// Succeeds

P1
LDR	X0, [X1]	// Reads 1
<dependency>
STR	#1, [X2]

P2
LDR	X0, [X2]	// Reads 1
<dependency>
STR	#2, [X1]	// Location at [X1] must be ordered {0->1->2}


We can also extend this example so that P2 instead does:

P2
LDR	X0, [X2]	// Reads 1
<dependency>
LDXR	X0, [X1]
ADD	X0, X0, #1
STXR	X0, [X1]	// Succeeds; location at [x1] must be ordered {0->1->2}

i.e. the STXR cannot succeed until the coherence order has been resolved,
which also requires the LDXR to return the up-to-date value.

> So I think that in effect, when a spinlock is implemnted with LL/SC,
> the loads inside the locked region are only ordered wrt the acquire on
> the LL, but the stores can be considered ordered wrt the SC.
> 
> No?

I initially fell into the same trap because a control dependency between
a load and a store is sufficient to create order (i.e. we don't speculate
writes). An SC is different, though, because the control dependency can
be resolved without the write being multi-copy atomic, whereas a read is
required to return its data (i.e. complete) before the control hazard can
be resolved.

I think that all of this means I should either:

  (1) Update the arm64 spin_unlock_wait to use LDXR/STXR (perhaps with
      acquire semantics?)

- or -

  (2) Replace spin_unlock_wait with spin_lock; spin_unlock, my worries
      about queuing notwithstanding.

The cacheline ping-pong in (1) can be mitigated somewhat by the use of
wfe, so it won't be any worse than a spin_lock().

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

#1271653

On Tue, Nov 17, 2015 at 11:51:10AM +0000, Will Deacon wrote:
> Hi Linus,
> 
> On Mon, Nov 16, 2015 at 01:58:49PM -0800, Linus Torvalds wrote:
> > On Mon, Nov 16, 2015 at 8:24 AM, Will Deacon <will.deacon@arm.com> wrote:
> > >
> > > ... or we upgrade spin_unlock_wait to a LOCK operation, which might be
> > > slightly cheaper than spin_lock()+spin_unlock().
> > 
> > So traditionally the real concern has been the cacheline ping-pong
> > part of spin_unlock_wait(). I think adding a memory barrier (that
> > doesn't force any exclusive states, just ordering) to it is fine, but
> > I don't think we want to necessarily have it have to get the cacheline
> > into exclusive state.
> 
> The problem is, I don't think the memory-barrier buys you anything in
> the context of Boqun's example. In fact, he already had smp_mb() either
> side of the spin_unlock_wait() and its still broken on arm64 and ppc.
> 
> Paul is proposing adding a memory barrier after spin_lock() in the racing
> thread, but I personally think people will forget to add that.

A mechanical check would certainly make me feel better about it, so that
any lock that was passed to spin_unlock_wait() was required to have all
acquisitions followed by smp_mb__after_unlock_lock() or some such.
But I haven't yet given up on finding a better solution.

							Thanx, Paul

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

#1272101

On Tue, Nov 17, 2015 at 01:01:09PM -0800, Paul E. McKenney wrote:
> On Tue, Nov 17, 2015 at 11:51:10AM +0000, Will Deacon wrote:
> > On Mon, Nov 16, 2015 at 01:58:49PM -0800, Linus Torvalds wrote:
> > > On Mon, Nov 16, 2015 at 8:24 AM, Will Deacon <will.deacon@arm.com> wrote:
> > > >
> > > > ... or we upgrade spin_unlock_wait to a LOCK operation, which might be
> > > > slightly cheaper than spin_lock()+spin_unlock().
> > > 
> > > So traditionally the real concern has been the cacheline ping-pong
> > > part of spin_unlock_wait(). I think adding a memory barrier (that
> > > doesn't force any exclusive states, just ordering) to it is fine, but
> > > I don't think we want to necessarily have it have to get the cacheline
> > > into exclusive state.
> > 
> > The problem is, I don't think the memory-barrier buys you anything in
> > the context of Boqun's example. In fact, he already had smp_mb() either
> > side of the spin_unlock_wait() and its still broken on arm64 and ppc.
> > 
> > Paul is proposing adding a memory barrier after spin_lock() in the racing
> > thread, but I personally think people will forget to add that.
> 
> A mechanical check would certainly make me feel better about it, so that
> any lock that was passed to spin_unlock_wait() was required to have all
> acquisitions followed by smp_mb__after_unlock_lock() or some such.
> But I haven't yet given up on finding a better solution.

Right-o. I'll hack together the arm64 spin_unlock_wait fix, but hold off
merging it for a few weeks in case we get struck by a sudden flash of
inspiration.

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

#1273350

On Wed, Nov 18, 2015 at 11:25:14AM +0000, Will Deacon wrote:
> On Tue, Nov 17, 2015 at 01:01:09PM -0800, Paul E. McKenney wrote:
> > On Tue, Nov 17, 2015 at 11:51:10AM +0000, Will Deacon wrote:
> > > On Mon, Nov 16, 2015 at 01:58:49PM -0800, Linus Torvalds wrote:
> > > > On Mon, Nov 16, 2015 at 8:24 AM, Will Deacon <will.deacon@arm.com> wrote:
> > > > >
> > > > > ... or we upgrade spin_unlock_wait to a LOCK operation, which might be
> > > > > slightly cheaper than spin_lock()+spin_unlock().
> > > > 
> > > > So traditionally the real concern has been the cacheline ping-pong
> > > > part of spin_unlock_wait(). I think adding a memory barrier (that
> > > > doesn't force any exclusive states, just ordering) to it is fine, but
> > > > I don't think we want to necessarily have it have to get the cacheline
> > > > into exclusive state.
> > > 
> > > The problem is, I don't think the memory-barrier buys you anything in
> > > the context of Boqun's example. In fact, he already had smp_mb() either
> > > side of the spin_unlock_wait() and its still broken on arm64 and ppc.
> > > 
> > > Paul is proposing adding a memory barrier after spin_lock() in the racing
> > > thread, but I personally think people will forget to add that.
> > 
> > A mechanical check would certainly make me feel better about it, so that
> > any lock that was passed to spin_unlock_wait() was required to have all
> > acquisitions followed by smp_mb__after_unlock_lock() or some such.
> > But I haven't yet given up on finding a better solution.
> 
> Right-o. I'll hack together the arm64 spin_unlock_wait fix, but hold off
> merging it for a few weeks in case we get struck by a sudden flash of
> inspiration.

For completeness, here's what I've currently got. I've failed to measure
any performance impact on my 8-core systems, but that's not surprising.

Will

--->8

From da14adc1aef2f12b7a7def4d6b7dde254a91ebf1 Mon Sep 17 00:00:00 2001
From: Will Deacon <will.deacon@arm.com>
Date: Thu, 19 Nov 2015 17:48:31 +0000
Subject: [PATCH] arm64: spinlock: serialise spin_unlock_wait against
 concurrent lockers

Boqun Feng reported a rather nasty ordering issue with spin_unlock_wait
on architectures implementing spin_lock with LL/SC sequences and acquire
semantics:

 | CPU 1                   CPU 2                     CPU 3
 | ==================      ====================      ==============
 |                                                   spin_unlock(&lock);
 |                         spin_lock(&lock):
 |                           r1 = *lock; // r1 == 0;
 |                         o = READ_ONCE(object); // reordered here
 | object = NULL;
 | smp_mb();
 | spin_unlock_wait(&lock);
 |                           *lock = 1;
 | smp_mb();
 | o->dead = true;
 |                         if (o) // true
 |                           BUG_ON(o->dead); // true!!

The crux of the problem is that spin_unlock_wait(&lock) can return on
CPU 1 whilst CPU 2 is in the process of taking the lock. This can be
resolved by upgrading spin_unlock_wait to a LOCK operation, forcing it
to serialise against a concurrent locker and giving it acquire semantics
in the process (although it is not at all clear whether this is needed -
different callers seem to assume different things about the barrier
semantics and architectures are similarly disjoint in their
implementations of the macro).

This patch implements spin_unlock_wait using an LL/SC sequence with
acquire semantics on arm64. For v8.1 systems with the LSE atomics, the
exclusive writeback is omitted, since the spin_lock operation is
indivisible and no intermediate state can be observed.

Signed-off-by: Will Deacon <will.deacon@arm.com>
---
 arch/arm64/include/asm/spinlock.h | 24 ++++++++++++++++++++++--
 1 file changed, 22 insertions(+), 2 deletions(-)

diff --git a/arch/arm64/include/asm/spinlock.h b/arch/arm64/include/asm/spinlock.h
index c85e96d174a5..b531791a75ff 100644
--- a/arch/arm64/include/asm/spinlock.h
+++ b/arch/arm64/include/asm/spinlock.h
@@ -26,9 +26,29 @@
  * The memory barriers are implicit with the load-acquire and store-release
  * instructions.
  */
+static inline void arch_spin_unlock_wait(arch_spinlock_t *lock)
+{
+	unsigned int tmp;
+	arch_spinlock_t lockval;
 
-#define arch_spin_unlock_wait(lock) \
-	do { while (arch_spin_is_locked(lock)) cpu_relax(); } while (0)
+	asm volatile(
+"	sevl\n"
+"1:	wfe\n"
+"2:	ldaxr	%w0, %2\n"
+"	eor	%w1, %w0, %w0, ror #16\n"
+"	cbnz	%w1, 1b\n"
+	ARM64_LSE_ATOMIC_INSN(
+	/* LL/SC */
+"	stxr	%w1, %w0, %2\n"
+	/* Serialise against any concurrent lockers */
+"	cbnz	%w1, 2b\n",
+	/* LSE atomics */
+"	nop\n"
+"	nop\n")
+	: "=&r" (lockval), "=&r" (tmp), "+Q" (*lock)
+	:
+	: "memory");
+}
 
 #define arch_spin_lock_flags(lock, flags) arch_spin_lock(lock)
 
-- 
2.1.4

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

#1273937

On Thu, Nov 19, 2015 at 06:01:52PM +0000, Will Deacon wrote:
> For completeness, here's what I've currently got. I've failed to measure
> any performance impact on my 8-core systems, but that's not surprising.

> +static inline void arch_spin_unlock_wait(arch_spinlock_t *lock)
> +{
> +	unsigned int tmp;
> +	arch_spinlock_t lockval;
>
> +	asm volatile(
> +"	sevl\n"
> +"1:	wfe\n"

Using WFE here would lower the cacheline bouncing pressure a bit I
imagine. Sure we still pull it over into S(hared) after every store
but we don't keep banging on it making the initial e(X)clusive grab
hard.

> +"2:	ldaxr	%w0, %2\n"
> +"	eor	%w1, %w0, %w0, ror #16\n"
> +"	cbnz	%w1, 1b\n"
> +	ARM64_LSE_ATOMIC_INSN(
> +	/* LL/SC */
> +"	stxr	%w1, %w0, %2\n"
> +	/* Serialise against any concurrent lockers */
> +"	cbnz	%w1, 2b\n",
> +	/* LSE atomics */
> +"	nop\n"
> +"	nop\n")

I find these ARM64_LSE macro thingies aren't always easy to read, its
fairly easy to overlook the ',' separating the v8 and v8.1 parts, esp.
if you have further interleaving comments like in the above.

> +	: "=&r" (lockval), "=&r" (tmp), "+Q" (*lock)
> +	:
> +	: "memory");
> +}
--
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