Memory64, multithreading and the 128-bit atomics operations to combat the ABA problem

[juj]

In native lock-free programming, a tricky issue is the ABA problem, which is caused by two or more atomic mutations by other threads, occurring between an observer thread checking on a shared state variable.

https://en.wikipedia.org/wiki/ABA_problem

The common elegant solution for this is to use auxiliary information, which typically ends up with a shared state block of "2x sizeof(ptr)" kind of a setup. Native compilation targets allow performing atomic operations on such 128-bit quantities, on 64-bit platforms.

When porting Unity to use WebAssembly's Memory64, we now find ourselves in a pickle with this scheme. Multithreading libraries that Unity uses, perform 128-bit atomic operations on shared memory (the usual: load/store/cas/exchange/add/and/or/xor).

We are looking at removing these 128-bit CAS support in the library code that assume its existence. Have there been considerations for adding 128-bit atomic operation support to multithreading+memory64 modes, or would that be something possible to consider?

[sbc100]

Funny that this should up right now. I just wrote a design document for precise thread wakeups: https://github.com/emscripten-core/emscripten/blob/main/docs/design/01-precise-futex-wakeups.md.

In this design we use the low bit of the pointer to hold the signalling metadata. @tlively came up with this bit-packing approach. Presumably on wasm64 you could the high 20+ bits to store the aux information?

[sbc100]

BTW, do the 128-bit atomics in the codebase simply not work? i.e. do they fail to compile? Or does it just cause perf issues since it falls back to using a lock of some kind?

[juj]

They do compile, but with the warning that it compiles down to a non-lock-free construct:

error: large atomic operation may incur significant performance penalty; the access size (16 bytes) exceeds
the max lock-free size (8 bytes) [-Werror,-Watomic-alignment]

(in the above, the codebase had been built with -Werror=atomic-alignment in effect)

In 64-bit multithreaded builds, the result is not lock-free, and hence unsafe/incorrect for multithreaded synchronization. There is no fallback mechanism that could be used, that would fall back to an emulated lock for example.

[sbc100]

I confirmed clang is doing the right thing here, and generating calls to __atomic_store when the type is larger then i64. The code that gets called is:

https://github.com/llvm/llvm-project/blob/a9c655df69284995967fb61553bef589a706598e/compiler-rt/lib/builtins/atomic.c#L200-L212

So you can safely use 128-bit atomics in LLVM/clang, they will just be slower then <= 64-bit.

[juj]

Thanks - that's great to know. For some reason, I had an internal mental model of "if the atomics are not lock-free, you as a user need to ensure providing the locks", because otherwise one cannot perform regular memory loads or stores to the lock address without being correct.

There is an added requirement that all uses must go through that LLVM-implemented lock, so that will include having to use atomic load and store intrinsics for all accesses. (which sometimes is skipped e.g. in CAS loops, to avoid double atomic operations)

[sbc100]

Thanks - that's great to know. For some reason, I had an internal mental model of "if the atomics are not lock-free, you as a user need to ensure providing the locks", because otherwise one cannot perform regular memory loads or stores to the lock address without being correct.

There is an added requirement that all uses must go through that LLVM-implemented lock, so that will include having to use atomic load and store intrinsics for all accesses. (which sometimes is skipped e.g. in CAS loops, to avoid double atomic operations)

Yes, all users of >64-bit-wide atomic would have go though LLVM.

But I don't think that should be problem, at least not in emscripten, because, IIRC the non-llvm lower-level primitives don't go above 64-bit. i.e there is no emscripten_atomic_cas_u128 to match the emscripten_atomic_cas_u64 function.

The the other primitives I know go (C11 _Atomic, std::atomic, __sync_val_compare_and_swap) all go though llvm and do the right thing. So, I think its not possible today to some kind of mismatch.