Atomicity: lock-free guarantees

[jfbastien]

TL;DR: make all accesses of 1, 2 and 4 bytes "always" lock-free, wider access "maybe".

C++11 has a concept of "atomicity" where an operations is either entirely observable, or not at all. This guarantee is on a per object basis, during the object's lifetime—for our purpose this is equivalent to per memory location. This is irrespective of the object's size, but does require proper natural alignment (UB if not naturally aligned).

Not all hardware have load/store of wide sizes (indeed, atomics can have any size!), the language therefore offers an is_lock_free method on the std::atomic class. This is a per-type property, but it's effectively based on size. This method is determined at runtime (i.e. it is not constexpr), but it's effectively known at load time because it can't change during program execution.

Using an atomic of non-atomic size relies on the runtime using a global lock (or a shard of global locks) to seamlessly prevent partial reads or writes. Normal loads/stores are unaffected, only atomics of unusual sizes go through this lock.

C has ATOMIC_*_LOCK_FREE macros for BOOL, CHAR, CHAR16_T, CHAR32_T, WCHAR_T, SHORT, INT, LONG, LLONG, POINTER, which can be used at compile time. These macros are a tribool: never lock-free, sometimes lock free, always lock free.

There is a proposal to add constexpr atomic::is_always_lock_free to the languages.

Note: things are a bit more complicated because C11 decided to standardize is_lock_free as taking a pointer to the object as well. Implementations ignore that pointer, I suggest we do the same.

In all 3 cases we (WebAssembly implementors) need to decide what we want to guarantee. The runtime checks are easy (look at current machine, return that), the shard of global locks is easy (it's an implementation detail), but the compile-time guarantee of "yes this will always be lock free on all platforms WebAssembly will ever support" isn't that easy to make, and it's binding forever.

Having such a guarantee is pretty important: it's silly to write a lock-free algorithm if the datastructure is atomic through a lock (i.e. isn't actually lock free!). A good example for 64-bit lock-free being useful is a doubly-linked list where 2 pointers use up 64 bits.

@sunfishcode points out:

• ppc32, ppc64, x86-32, x86-64, sparcv9, systemz, bpf, mips32, mips64, arm32, and arm64 can all do int32 lock-free.
• ppc64, x86-64, arm64, sparcv9, systemz, bpf, and mips64 can all do int64 lock-free.

I think we can safely say 1, 2 and 4 byte accesses are always lock-free (even if you can't do a byte load you can always cmpxchg a wider size).

[sunfishcode]

I would also like to propose that 8-byte accesses also be guaranteed to be lock-free in 64-bit mode. This would mean that some 32-bit platforms (like ppc32, mips32) wouldn't be able to run 64-bit wasm, though some (like x86-32) can, but as detailed above, all known relevant 64-bit platforms would be fine.

[titzer]

Is lock-freedom observable? E.g. would it be possible for an implementation to "violate" lock-freedom in a way that is observable to the program? Or is this more of a performance advisory?

[jfbastien]

It's mostly a performance advisory (albeit a significant one), but it is potentially possible to observe. A few examples:

• When accessing the same memory location of non-lock-free size with atomic accesses as well as non-atomic accesses (this is UB).
• A non-lock-free atomic access straddles a page boundary with different page protections.
• During signal handling or asynchronous / timer events.
• Communicating through shared memory (mmap based physical page sharing) with other wasm instances or non-wasm agents (potentially in other processes).

[kg]

How does this interact with unaligned access? Also, does 4-byte lock-free status guarantee that 1-byte and 2-byte IOs are lock-free? I can imagine an architecture where a 1-byte write turns into read-4-into-temp, write-1-into-temp, write-4-from-temp, in which case it would be very much not lock-free.

[lukewagner]

Since PostMVP.md#threads already mentions the goal of providing atomic ops and Atomics.isLockFree(size) is already in the SharedArrayBuffer draft, is what you're ultimately proposing that we explicitly mention that we'd add a wasm equivalent (new AST op, is a constant function, so foldable) of Atomics.isLockFree? If so, sgtm.

[jfbastien]

@kg your two questions:

• Unaligned accesses of atomics are UB in C++. In wasm we should spec it as potentially tearing (local effect only).
• 1 and 2 byte lock-free can be implemented as a cmpxchg of 4-byte values, with mask / shift / or of the 1 or 2 byte value into the 4 bytes.

@lukewagner I basically want to figure out what LLVM should do (both for constexpr as well as for the runtime function), because @sunfishcode's clang patch ran into this issue. Can we promise that 1, 2 and 4 byte accesses will always be lock-free, forever, for all architectures wasm will ever support?

[lukewagner]

I like the idea of shooting for the best semantics we can get, but I'm not sure mandating is_lock_free(1|2|4)=true wins us anything: either it will be true on all archs forever, or it won't and the wasm impl on this arch will be forced to lie (have is_lock_free return true but implement with a lock); what choice does it have? Semantically, both cases behave the same. The difference is that in the latter case, the engine is lying so wasm code that could have used the information doesn't have it.

[jfbastien]

@lukewagner lying isn't an option IMO :-)
We're allowed to say one of three things for each size:

1. Always lock-free;
2. Never lock-free;
3. Sometimes lock-free (and then give is_lock_free a true/false value at load time, based on the actual architecture).

The most conservative is to say "sometimes" in all cases, which is what I asked @sunfishcode to do in clang for now.

[kg]

@jfbastien

1 and 2 byte lock-free can be implemented as a cmpxchg of 4-byte values, with mask / shift / or of the 1 or 2 byte value into the 4 bytes.

Are you proposing that as a part of the '1/2/4-byte accesses are atomic' guarantee, we require conforming implementations to turn all sub-4-byte accesses into cmpxchg? That seems catastrophically non-performant.

[jfbastien]

@kg I indeed am, and it's lock-free so cheaper than the alternative :-)

[jfbastien]

@kg to clarify, I'm talking about atomic accesses only, not regular load/store.

[lukewagner]

@jfbastien Ok, then it sounds like we agree (to not require is_lock_free(1|2|4)=true) unless you're positing that no future arch will ever drop support for atomic 1/2/4-byte aligned accesses.

[sunfishcode]

@luke I am positing that no future arch will ever drop support for lock-free 1/2/4-byte atomic accesses. The arch survey mentioned above includes all major architectures, and beyond that, the C++ memory model encourages architectures to do so, and is one of the pillars of our work here.

[jfbastien]

I sure hope architectures support 1-byte atomics forever :-)
2 is questionable, but...
4-bytes seems like the accepted minimum for anything we'd care about, and in a pinch can be used to do 2 with cmpxchg.
8 is still out there for some architectures, but seems to be slowly making its way in.
16 is oh-so-tantalizing, but not everyone has the luxury of lock cmpxchg16b.
And don't get me started on the wonders of transactional memory, where I get an L1's worth of dirty pages!

So I tend to agree with @sunfishcode and count on 4 being 4eva.