Atomics and lock free

Atomics and lock free

[Kurt Roeckx]

Hi,

We're looking into moving a reference counter from a lock to
atomics because the lock currently seems to be a bottleneck for
some workloads.

Some platforms don't seem to be proving lock free atomics, like
armv5.  My understanding is that if we use the atomics (C11 or gcc
built in) that it would use an external function that might
possible take a lock, or maybe do something else so that we get
the atomic behaviour we want.

Since we support platforms that don't have the atomics, we at
least need to still support the locks we take ourself.

Is there any benifit in taking a lock ourself when the atomics are
not lock free?  For instance we might have a lock per object
instead of some global lock.  But we'd probably need 2 kernel
calls when we take the lock ourself while it might be possible
that the atomics library can do it with only 1 system call,
probably with the kernel's help.

I'm also wondering why the library provides functions for checking
that it's lock free.  I guess it's to be able to make such a
decision, but it's not obvious.

Does someone have some guidance for what's the best to do?  Maybe
some information about how things are implemented?


Kurt

Re: Atomics and lock free

[Oleg Endo]

Hi,

On Sat, 2016-09-03 at 12:30 +0200, Kurt Roeckx wrote:
> Hi,
> 
> We're looking into moving a reference counter from a lock to
> atomics because the lock currently seems to be a bottleneck for
> some workloads.
> 
> Some platforms don't seem to be proving lock free atomics, like
> armv5.  My understanding is that if we use the atomics (C11 or gcc
> built in) that it would use an external function that might
> possible take a lock, or maybe do something else so that we get
> the atomic behaviour we want.
> 
> Since we support platforms that don't have the atomics, we at
> least need to still support the locks we take ourself.
> 
> Is there any benifit in taking a lock ourself when the atomics are
> not lock free?  For instance we might have a lock per object
> instead of some global lock.  But we'd probably need 2 kernel
> calls when we take the lock ourself while it might be possible
> that the atomics library can do it with only 1 system call,
> probably with the kernel's help.
> 
> I'm also wondering why the library provides functions for checking
> that it's lock free.  I guess it's to be able to make such a
> decision, but it's not obvious.
> 
> Does someone have some guidance for what's the best to do?  Maybe
> some information about how things are implemented?

Not sure on what kind of system you are but on single-core systems
there are generally two options:

- interrupt flipping
- rewindable atomic sequences

You could teach the ARM backend to emit the respective code for
__atomic* built-in functions.  If that's not an option, you can
implement the respective __atomic* functions in your own way and let
the compiler emit function calls.  If you use LTO the function calls
might get eliminated completely in the end.

Rewindable atomic sequences are supported by GCC on SH but can also be
done on other architectures of course.  See also the original work:

http://www.free-it.org/archiv/LT_History/2003/talks/170/paper.html

Unfortunately GCC doesn't have a generic implementation for those.  It
has to be explicitly implemented by the backend.

Cheers,
Oleg

Re: Atomics and lock free

[Kurt Roeckx]

On Sat, Sep 03, 2016 at 08:10:18PM +0900, Oleg Endo wrote:
> Hi,
> 
> On Sat, 2016-09-03 at 12:30 +0200, Kurt Roeckx wrote:
> > Hi,
> > 
> > We're looking into moving a reference counter from a lock to
> > atomics because the lock currently seems to be a bottleneck for
> > some workloads.
> > 
> > Some platforms don't seem to be proving lock free atomics, like
> > armv5.  My understanding is that if we use the atomics (C11 or gcc
> > built in) that it would use an external function that might
> > possible take a lock, or maybe do something else so that we get
> > the atomic behaviour we want.
> > 
> > Since we support platforms that don't have the atomics, we at
> > least need to still support the locks we take ourself.
> > 
> > Is there any benifit in taking a lock ourself when the atomics are
> > not lock free?  For instance we might have a lock per object
> > instead of some global lock.  But we'd probably need 2 kernel
> > calls when we take the lock ourself while it might be possible
> > that the atomics library can do it with only 1 system call,
> > probably with the kernel's help.
> > 
> > I'm also wondering why the library provides functions for checking
> > that it's lock free.  I guess it's to be able to make such a
> > decision, but it's not obvious.
> > 
> > Does someone have some guidance for what's the best to do?  Maybe
> > some information about how things are implemented?
> 
> Not sure on what kind of system you are but on single-core systems
> there are generally two options:
> 
> - interrupt flipping
> - rewindable atomic sequences
> 
> You could teach the ARM backend to emit the respective code for
> __atomic* built-in functions.  If that's not an option, you can
> implement the respective __atomic* functions in your own way and let
> the compiler emit function calls.  If you use LTO the function calls
> might get eliminated completely in the end.
> 
> Rewindable atomic sequences are supported by GCC on SH but can also be
> done on other architectures of course.  See also the original work:
> 
> http://www.free-it.org/archiv/LT_History/2003/talks/170/paper.html
> 
> Unfortunately GCC doesn't have a generic implementation for those.  It
> has to be explicitly implemented by the backend.

I'm more looking for general advice, the armv5 was just an
example.  For those cases were it's lock free it's obvious
that the performance is going to improve.  It's not for the cases
where it's not lock free.  And I'm trying to prevent it from
getting worse where it's not lock free.


Kurt

Re: Atomics and lock free

[Avi Kivity]

On 09/03/2016 01:30 PM, Kurt Roeckx wrote:
> Hi,
>
> We're looking into moving a reference counter from a lock to
> atomics because the lock currently seems to be a bottleneck for
> some workloads.
>
> Some platforms don't seem to be proving lock free atomics, like
> armv5.  My understanding is that if we use the atomics (C11 or gcc
> built in) that it would use an external function that might
> possible take a lock, or maybe do something else so that we get
> the atomic behaviour we want.
>
> Since we support platforms that don't have the atomics, we at
> least need to still support the locks we take ourself.
>
> Is there any benifit in taking a lock ourself when the atomics are
> not lock free?  For instance we might have a lock per object
> instead of some global lock.  But we'd probably need 2 kernel
> calls when we take the lock ourself while it might be possible
> that the atomics library can do it with only 1 system call,
> probably with the kernel's help.

If you're incrementing several counters, with your own locking you can 
increment them under a single lock, while using the atomics library 
might result in the lock being taken and released several times.

> I'm also wondering why the library provides functions for checking
> that it's lock free.  I guess it's to be able to make such a
> decision, but it's not obvious.
>
> Does someone have some guidance for what's the best to do?  Maybe
> some information about how things are implemented?
>
>
>