Re: Refactoring atomics as llsc?

[Rich Felker <dalias@libc.org>]

On Wed, May 20, 2015 at 08:33:23AM +0300, Timo Teras wrote:
> On Wed, 20 May 2015 01:11:08 -0400
> Rich Felker <dalias@libc.org> wrote:
> 
> > Of course the big outlier is x86, which is not llsc based but has
> > actual atomic primitives at the instruction level. If we defined the
> > sc() primitive to take 3 args instead of 2 (address, old value from
> > ll, new value to conditionally store; most archs would ignore the old
> > value argument) then we could model x86 with ll being a plain load and
> > sc being cmpxchg to allow any new custom primitives to work using
> > cmpxchg. Then we would just continue providing custom versions of all
> > the old a_* ops (a_cas, a_fetch_add, a_inc, a_dec, a_and, a_or,
> > a_swap) to take advantage of the x86 instructions. These versions
> > could probably be shared by all x86 variants (i386, x86_64, x32) since
> > they're operating on 32-bit values and the asm should be the same.
> 
> I wonder if calling that kind of emulation ll()/sc() would be
> misleading. load-linked store-conditional has stronger guarantees. sc
> will fail if the cache-line was invalidated in-between, thread was
> pre-empted etc.
> 
> Using cmpxchg can be used to emulate it only when the user is aware of
> ABA problem (some other thread may have changed the value behind us
> multiple times). Such emulation is of course ok for a_fetch_add, etc.
> But one needs to be more careful if using pointers (and trying to make
> sure the same pointer was not first removed and later re-added).
> 
> And if you want to optimize the above mentioned cases, one really needs
> to know if it's true ll+sc, or write the synchronization differently.
> In these cases the algorithm is often implemented twice with the
> different available atomics.

Yes. The intent is not to expose ll/sc to musl source files, merely to
use them as a basis for generic implementations of the existing atomic
primitives and perhaps some new ones that might be interesting for
improvements to semaphores or for other special tasks. You're right
that we should be careful, if doing a 'fake' ll/sc, to document that
it is only usable for direct value operations not subject to ABA
issues. As long as we don't go adding new atomic ops on pointers
(other than the a_cas_p we have now) I don't see any such issues being
likely to arise, though.

Rich