arch maintainers: RFC on spinlock refactoring

arch maintainers: RFC on spinlock refactoring

[Torvald Riegel]

We want to refactor the spinlock code (ie, pthread_spin* functions); the
goal is to improve the generic implementation and use it for as many
architectures as possible.  Stefan Liebler has started this work on the
s390 side.

I'd like to have input on some arch-specific questions from some of you.

Roughly, I think we should
* Finish Stefan's first patch that brings the generic spinlock code into
a good shape.
* Add some properties of atomic operations to each arch's
atomic-machine.h; for now, we're considering 1) whether atomic
read-modify-writes are implemented through CAS and 2) whether a CAS
always brings in the cache line in an exclusive state (ie, even when the
CAS would fail).
* Move as many architectures as we can without detailed review to the
generic spinlock.
* Integrate the spinlock code of the remaining archs; this may require
either extending the generic spinlock code (eg, if the arch comes with
more advanced spinning) or improving the atomics of those archs.
* Improve the back-off strategy; use microbenchmarks to justify changes.

archs that should be able to simply use the generic spinlock after
Stefan's first patch has been applied:
aarch64, microblaze, arm, m68k, s390, mips, nios2

alpha:
* Can we just use plain atomics instead of the custom code?

hppa:
* I suppose we can use generic once we've fixed the atomics (ie, make
atomic stores use the kernel atomics emulation too)?

tile:
* Contains custom back-off implementation.  We should discuss this
separately.
* Does CAS always bring in the cache line in exclusive state?  I guess
it doesn't?
* I suppose atomic_exchange can't be replaced with atomic_store?  Should
this be a flag so that this can be included in the generic code?
* What about trylock?  Keep it or use generic?

powerpc:
* I believe we should create versions of the atomic operations that have
MUTEX_HINT_ACQ set.  We started to discuss this a while ago, but this
died off.  We should pick up this thread again.

x86_64, i386:
* We should move to the generic code.  Confirming that there are no
performance regressions would be good.  As soon as generic spinlock adds
back-off, generic should perform better under contention.

ia64:
* Move to generic code.  Check that the back-off instruction is exposed
through the atomics interface.

sh:
* Use generic spinlock?

sparc:
* sparc64/sparcv9: Use generic spinlock? 
* sparc32 pre-v9: ?

Re: arch maintainers: RFC on spinlock refactoring

[Richard Henderson]

On 02/19/2017 05:23 AM, Torvald Riegel wrote:
> alpha:
> * Can we just use plain atomics instead of the custom code?

Yes.  There's nothing special at all about that code.


r~

Re: arch maintainers: RFC on spinlock refactoring

[Carlos O'Donell]

On 02/18/2017 01:23 PM, Torvald Riegel wrote:
> We want to refactor the spinlock code (ie, pthread_spin* functions); the
> goal is to improve the generic implementation and use it for as many
> architectures as possible.  Stefan Liebler has started this work on the
> s390 side.
> 
> I'd like to have input on some arch-specific questions from some of you.
> 
> Roughly, I think we should
> * Finish Stefan's first patch that brings the generic spinlock code into
> a good shape.
> * Add some properties of atomic operations to each arch's
> atomic-machine.h; for now, we're considering 1) whether atomic
> read-modify-writes are implemented through CAS and 2) whether a CAS
> always brings in the cache line in an exclusive state (ie, even when the
> CAS would fail).

OK.

> * Move as many architectures as we can without detailed review to the
> generic spinlock.
> * Integrate the spinlock code of the remaining archs; this may require
> either extending the generic spinlock code (eg, if the arch comes with
> more advanced spinning) or improving the atomics of those archs.
> * Improve the back-off strategy; use microbenchmarks to justify changes.

OK.

> archs that should be able to simply use the generic spinlock after
> Stefan's first patch has been applied:
> aarch64, microblaze, arm, m68k, s390, mips, nios2

> hppa:
> * I suppose we can use generic once we've fixed the atomics (ie, make
> atomic stores use the kernel atomics emulation too)?

Yes. My outstanding question is about pthread_spin_init() and the current
hppa implementation which uses atomic_exchange_rel (lock, 0) because it is
required to ensure the kernel helper is used and to ensure a true happens-before.

The nptl generic implementation just has *lock = 0.

-- 
Cheers,
Carlos.

Re: arch maintainers: RFC on spinlock refactoring

[Torvald Riegel]

On Mon, 2017-02-20 at 15:34 -0500, Carlos O'Donell wrote:
> On 02/18/2017 01:23 PM, Torvald Riegel wrote:
> > We want to refactor the spinlock code (ie, pthread_spin* functions); the
> > goal is to improve the generic implementation and use it for as many
> > architectures as possible.  Stefan Liebler has started this work on the
> > s390 side.
> > 
> > I'd like to have input on some arch-specific questions from some of you.
> > 
> > Roughly, I think we should
> > * Finish Stefan's first patch that brings the generic spinlock code into
> > a good shape.
> > * Add some properties of atomic operations to each arch's
> > atomic-machine.h; for now, we're considering 1) whether atomic
> > read-modify-writes are implemented through CAS and 2) whether a CAS
> > always brings in the cache line in an exclusive state (ie, even when the
> > CAS would fail).
> 
> OK.
> 
> > * Move as many architectures as we can without detailed review to the
> > generic spinlock.
> > * Integrate the spinlock code of the remaining archs; this may require
> > either extending the generic spinlock code (eg, if the arch comes with
> > more advanced spinning) or improving the atomics of those archs.
> > * Improve the back-off strategy; use microbenchmarks to justify changes.
> 
> OK.
> 
> > archs that should be able to simply use the generic spinlock after
> > Stefan's first patch has been applied:
> > aarch64, microblaze, arm, m68k, s390, mips, nios2
> 
> > hppa:
> > * I suppose we can use generic once we've fixed the atomics (ie, make
> > atomic stores use the kernel atomics emulation too)?
> 
> Yes. My outstanding question is about pthread_spin_init() and the current
> hppa implementation which uses atomic_exchange_rel (lock, 0) because it is
> required to ensure the kernel helper is used and to ensure a true happens-before.

OK.  So I'd just leave it to you to remove the custom spinlock code
(assuming that we get around to changing the spinlock earlier than we
get to fix the hppa atomics ;) ...).

> The nptl generic implementation just has *lock = 0.

Yes, Stefan's patch changes this to a atomic_store_release.

Re: arch maintainers: RFC on spinlock refactoring

[Chris Metcalf]

On 2/18/2017 1:23 PM, Torvald Riegel wrote:
> We want to refactor the spinlock code (ie, pthread_spin* functions); the
> goal is to improve the generic implementation and use it for as many
> architectures as possible.  Stefan Liebler has started this work on the
> s390 side.
>
> I'd like to have input on some arch-specific questions from some of you.
>
> Roughly, I think we should
> * Finish Stefan's first patch that brings the generic spinlock code into
> a good shape.
> * Add some properties of atomic operations to each arch's
> atomic-machine.h; for now, we're considering 1) whether atomic
> read-modify-writes are implemented through CAS and 2) whether a CAS
> always brings in the cache line in an exclusive state (ie, even when the
> CAS would fail).
> * Move as many architectures as we can without detailed review to the
> generic spinlock.
> * Integrate the spinlock code of the remaining archs; this may require
> either extending the generic spinlock code (eg, if the arch comes with
> more advanced spinning) or improving the atomics of those archs.
> * Improve the back-off strategy; use microbenchmarks to justify changes.
>
> [...]
>
> tile:
> * Contains custom back-off implementation.  We should discuss this
> separately.
> * Does CAS always bring in the cache line in exclusive state?  I guess
> it doesn't?
> * I suppose atomic_exchange can't be replaced with atomic_store?  Should
> this be a flag so that this can be included in the generic code?
> * What about trylock?  Keep it or use generic?

I'm happy to help think about this stuff for tile.  Sorry for the
delay since I'm having trouble catching up from February break
vacation with the kids :)

The back-off implementation was driven by our benchmarking with 64+
core systems, where we found that bounded exponential backoff was the
best way to ensure rapid overall system progress in the face of
relatively heavy locking load.  Tile's mesh interconnect carries
atomic requests from cores to the L3 cache, which is distributed
per-core.  That tends to make exponential backoff even more important
since otherwise the mesh gives preferential performance to nearer
cores over farther cores, so the farther cores can get starved in the
absence of backoff.

The CAS operation does not bring the cache line in at all; instead,
the operation is performed on the remote piece of the L3 core and the
reply message carries just the old memory value.  This is true for all
the atomics on TILE-Gx (CAS, exchange, fetch-and-add, fetch-and-and,
fetch-and-or, etc).  The architecture does this so that when lots of
atomics are being issued, we don't time invalidating local L2 caches.

I think switching to a generic trylock implementation would be fine;
as you can see, we haven't tried to optimize the tile version.  We
just use an atomic exchange (not pulling in any cache line, as
mentioned above) to try to set the lock state to "1".

One thing that's important to note is that the above is all about
TILE-Gx, our more recent 64-bit processor.  TILEPro, the older 32-bit
processor, had only a single atomic operation, a "test and set one",
which everything else is built on top of using kernel fast syscalls to
provide CAS and various other simple atomic patterns.  I believe this
is similar to the existing sparc32 atomic support.  As a result, on
TILEPro you have to use "atomic exchange" (via the kernel fast
syscall) to implement atomic store, since a plain store can race with
the kernel implementation of atomics.  This isn't true on TILE-Gx,
where an atomic store really can be just a plain store operation.

-- 
Chris Metcalf, Mellanox Technologies
http://www.mellanox.com

Re: arch maintainers: RFC on spinlock refactoring

[Carlos O'Donell]

On 03/09/2017 02:32 PM, Chris Metcalf wrote:
> One thing that's important to note is that the above is all about
> TILE-Gx, our more recent 64-bit processor.  TILEPro, the older 32-bit
> processor, had only a single atomic operation, a "test and set one",
> which everything else is built on top of using kernel fast syscalls to
> provide CAS and various other simple atomic patterns.  I believe this
> is similar to the existing sparc32 atomic support.  As a result, on
> TILEPro you have to use "atomic exchange" (via the kernel fast
> syscall) to implement atomic store, since a plain store can race with
> the kernel implementation of atomics.  This isn't true on TILE-Gx,
> where an atomic store really can be just a plain store operation.

Right, TILEPro is therefore like hppa in this regard, every atomic
operation has to go into the kernel because you have to use the same
set of locks in the kernel to ensure happens-before between the threads.

-- 
Cheers,
Carlos.