Disallow atomic operations on unshared objects?

[Liedtke]

It was pointed out in issue #97 (see this comment) that one of the design invariants of the shared-every-thing-threads proposal is to allow engines to have different representations for shared and unshared references.

With that in mind, the current design

Atomic accesses to references are deliberately restricted to anyref, shared anyref, and their subtypes [...]

seems to be creating a decent implementation overhead for something with little to no value: atomic instructions on unshared objects.

For V8 we don't have different representations for shared and unshared objects, however, they live on different "heaps".
Now, to support atomic operations on i64 on all platforms, we need to emit atomic operations on all platforms for 64 bit fields.
On arm this requires 8-Byte-alignment of all i64 fields in wasm objects.

As a result, we align all i64 fields (and for simplicity double fields as well) in shared objects to have an offset that is a multiple of 8 bytes and then we additionally align the start address of any object to 8 bytes. We don't do this on unshared objects, however, and it is unclear if we'd want to do the same for unshared objects.

This means, for any atomic operation we need extra code to support this non-feature of unshared atomic operations: For struct.atomic.get etc. it's rather trivial, we just emit a struct.get for them as if it never was an atomic operation.

For struct.atomic.rmw.add and alike, this however means that for unshared atomic operations the implementation work is higher than supporting the shared atomic operations: For the shared part we can reuse the code generation used for the corresponding linear wasm instructions. For the unshared part, we need to write new code generation emitting patterns like struct.set($s, i32.add($a, struct.get($s))). While that doesn't contain anything new, it still is extra work and complexity and I'm wondering why we should even allow struct.atomic.rmw.add and all other atomic instructions on unshared objects, especially if engines might not even emit atomic operations for them?¹

---

@eqrion What's the situation for SpiderMonkey regarding shared vs. unshared objects? Do you already have some support for it for JS? What's the situation with heap object alignment? Are they always 8-byte-aligned?
(V8 emits ldrexd on Arch32 for atomic i64 loads which requires 8-byte-alignment, so pointer-size alignment is not sufficient in that case for us.)

Footnotes

1. In theory we could emit more concise code on platforms that don't have these strict alignment requirements and then it could be argued that there is some benefit of using these atomic operations (similar to bulk operations) but that really isn't a goal of this proposal and it's questionable if there would be any community support for adding these instructions for unshared objects on its own (if it wasn't just included in this proposal). ↩

[tlively]

The reason to allow atomic operations on unshared objects is for symmetry with atomic operations on unshared memories from the original threads proposal, which we decided to allow in WebAssembly/threads#144.

The rationale there was to allow compilers to produce code using atomic instructions, but then defer the decision about whether to use a shared or unshared memory to link time. We have a slightly different situation with WasmGC because there are no existing toolchains (to my knowledge) that have a separate linker that cannot change compiled instructions, but I wouldn't want to rule it out in the future, either. It is a nice property that the same code can be generated for both multithreaded and single-threaded programs, with only the sharedness bit in type definitions being different.

[Liedtke]

We have a slightly different situation with WasmGC because there are no existing toolchains (to my knowledge) that have a separate linker that cannot change compiled instructions, but I wouldn't want to rule it out in the future, either.

Can't we rule that out because we have cast instructions to abstract heap types that might or might not have a shared marker? The same applies for blocks with a single result type which can be emitted directly or with the source type immediate of a br_on_cast, or local definitions, ...

So I don't see a good reason to significantly increase the implementation work for any engine that has significant differences between shared and unshared types.
Would we expect toolchains to use struct.atomic.rmw.add as a more compact binary encoding for unshared structs and would we think that's a valid use case even though atomicity doesn't really carry any meaning for an unshared heap?

Some engines might load-eliminate redundant atomic loads on unshared objects (V8 will do that because the atomic load for unshared structs is just a regular non-atomic load due to the described issue of it not being easily possible to use actual atomic hardware instructions) while some other engine might decide to treat these as atomic / volatile loads as specified by "user intent".

[Liedtke]

I accidentally fatfinger-closed the issue on the mobile UI and don't have the permissions to reopen... :/

[tlively]

All good questions :)

We have a slightly different situation with WasmGC because there are no existing toolchains (to my knowledge) that have a separate linker that cannot change compiled instructions, but I wouldn't want to rule it out in the future, either.

Can't we rule that out because we have cast instructions to abstract heap types that might or might not have a shared marker? The same applies for blocks with a single result type which can be emitted directly or with the source type immediate of a br_on_cast, or local definitions, ...

Yes, good point. This would only work if the toolchain never performed casts to shared abstract heap types, or if it could relocate such casts (but we don't currently have a prefix meaning non-shared, so such relocation would currently require shifting bytes around).

Would we expect toolchains to use struct.atomic.rmw.add as a more compact binary encoding for unshared structs and would we think that's a valid use case even though atomicity doesn't really carry any meaning for an unshared heap?

I would expect this only when the source code used atomics, but then was compiled into a single-threaded application (although of course we wouldn't be able to stop anyone from doing this in other situations as well; it just seems unlikely).

Some engines might load-eliminate redundant atomic loads on unshared objects (V8 will do that because the atomic load for unshared structs is just a regular non-atomic load due to the described issue of it not being easily possible to use actual atomic hardware instructions) while some other engine might decide to treat these as atomic / volatile loads as specified by "user intent".

I don't think this is a problem. Both implementation strategies would be spec-compliant, so it's fine if engines make different choices here.

[Liedtke]

The rationale there was to allow compilers to produce code using atomic instructions, but then defer the decision about whether to use a shared or unshared memory to link time.

Besides the arguments from above, I stumbled upon another reason why this is almost certainly not feasible:
To allow this "just use atomic instructions everywhere", it would be necessary to be able to replace struct.get / struct.set instructions with struct.atomic.get / struct.atomic.set which fails for anything in the externref / exnref / funcref hierarchies (and any new potentially shareable hierarchies like contref) as well as most value types.

So we already don't have the symmetry between struct.get and struct.atomic.get which is a very different situation than for the load / store instructions for linear memory which don't even know if they operate on shared or unshared memory.

As a side note, what will this mean for e.g. externref fields? Do we expect that toolchains will generate user-level locks to synchronize accesses to fields of such types?

[jakobkummerow]

FWIW, I find those two arguments convincing (for disallowing atomic operations on non-shared structs):
(1) There is no full symmetry between struct.get and struct.atomic.get anyway; the latter is not a general drop-in replacement for the former.
(2) Contrary to linear memory accesses, every struct.* operation always has enough local static type information to know whether it's operating on a shared or non-shared struct.

Being able to reuse function bodies while swapping out the type section is generally not realistic for a bunch of reasons (including but not limited to those two), so that scenario is not the equivalent of wanting functions to be agnostic to the sharedness bit of the memory that they're operating on.

[rossberg]

@Liedtke:

load / store instructions for linear memory which don't even know if they operate on shared or unshared memory.

@jakobkummerow:

Contrary to linear memory accesses, every struct.* operation always has enough local static type information to know whether it's operating on a shared or non-shared struct.

I'm confused what both of you mean. The static type of the memory that a load/store instruction refers to declares whether it's shared or not all the same. Where is the difference in that regard?

As for struct.atomic.get not being available for all types: perhaps that's a shortcoming of the proposal anyway. Accesses to fields with reference type must be non-tearing already, even for non-atomic access. That seems the harder implementation constraint, and once solving it requires something close to implementing atomic access anyway. Hence I'm not sure much is won by not extending atomic get/set instructions to all reference types (and v128).

[tlively]

To allow this "just use atomic instructions everywhere", it would be necessary to be able to replace struct.get / struct.set instructions with struct.atomic.get / struct.atomic.set which fails for anything in the externref / exnref / funcref hierarchies (and any new potentially shareable hierarchies like contref) as well as most value types.

To clarify, the point is not to "just use atomic instructions everywhere." That's not possible for exactly the reasons you pointed out. The point is to be able to lower the same source code to the same WebAssembly instructions no matter whether the types end up being compiled as shared or not. So atomic accessors only need to be allowed on unshared types precisely where they would be allowed on shared versions of those types. In other words we want symmetry between struct.atomic.get on shared structs and struct.atomic.get on unshared structs, not symmetry between struct.atomic.get and struct.get.

As for struct.atomic.get not being available for all types: perhaps that's a shortcoming of the proposal anyway. Accesses to fields with reference type must be non-tearing already, even for non-atomic access. That seems the harder implementation constraint, and once solving it requires something close to implementing atomic access anyway. Hence I'm not sure much is won by not extending atomic get/set instructions to all reference types (and v128).

It's not clear to me that guaranteeing tear-freedom would be harder or slower in general than guaranteeing various synchronization properties. @conrad-watt, what makes the most sense here?

[conrad-watt]

To understand the current state of things, we allow atomics on refs in the anyref hierarchy, but disallow them on other hierarchies?

As noted in the OP, we're designing the proposal with the expectation that shared types can have different representations to unshared types. In my head, one (among many!) advantage of this was that funcref could have a fat representation, while shared funcref could still be chosen to have a native-word representation, and this would allow us to specify efficient atomics on shared funcref. It would be unproblematic to allow atomics on unshared funcref even if it has a fat representation, since such accesses can just be compiled to bare loads and stores (that would tear in a concurrent setting but are fine in a sequential one).

So I'd be in favour of expanding atomics to all reference types (in fact I was incorrectly assuming this was already the case).

For v128, it's harder to offer atomics as there's no notion of a "shared" v128 with different representation. My expectation has been that if you want atomic manipulation of a v128 you would do user-level boxing with a shared struct (edit: or user-level locking).

[conrad-watt]

It's also true that if some runtime was strongheaded and really wanted its non-any shared reference types to have fat representations, it would probably need to insert locks around every relevant access to prevent tearing as @rossberg was alluding to above, in which case we could just allow atomics anyway (piggybacking off these locks).

[Liedtke]

Regarding allowing atomic operations on all value types: In the beginning I was also surprised that we don't have atomic get/set operations e.g. for f32 and f64. Then I checked a few GC-ed languages like Java, Kotlin, Dart and Go which all have atomics and none of them seem to have atomic operations on floating point values.

So I'm not sure if we'd solve any real problem by making atomic accesses valid on all value types.

The point is to be able to lower the same source code to the same WebAssembly instructions no matter whether the types end up being compiled as shared or not.

Thanks for clarifying. This still means: We expect this will be useful because there could be a sufficiently advanced toolchain that is able to convert the whole type section from shared to unshared and all their usages within the code (like the mentioned abstract casts to shared types), but this toolchain will not be able to replace a struct.atomic.get with a struct.get in that same run and rmw operations with the corresponding read-modify-write instruction sequences?
Instead, it would be much simpler and more useful if each WebAssembly runtime did these exact same transformations under the hood in a jit environment? :)
(And as I'm trying to point out, due to things like alignment these indeed are transformations of instructions for us because we can't just run all the atomic instructions on unshared objects.)

I'd expect that there'd be some hope for Binaryen to implement such a pass of converting shared-everything modules to "fully unshared" modules rewriting the type section, casts and instructions. After that I don't expect any other toolchain to really care about having to implement it because they can just call Binaryen for this use case which many of them anyways do to reduce binary size, do better optimizations etc.

@tlively Wouldn't such a pass be something that we'd want to have in Binaryen? Do you expect a big difference in complexity between rewriting the type section and casts only vs. also rewriting the atomic instructions?

[tlively]

The point is to be able to lower the same source code to the same WebAssembly instructions no matter whether the types end up being compiled as shared or not.

Thanks for clarifying. This still means: We expect this will be useful because there could be a sufficiently advanced toolchain that is able to convert the whole type section from shared to unshared and all their usages within the code (like the mentioned abstract casts to shared types), but this toolchain will not be able to replace a struct.atomic.get with a struct.get in that same run and rmw operations with the corresponding read-modify-write instruction sequences? Instead, it would be much simpler and more useful if each WebAssembly runtime did these exact same transformations under the hood in a jit environment? :)

Yes, pretty much :) This isn't as far-fetched as it may seem, though. The wasm-ld linker works exactly like a traditional linker in that it just memcopies code around and applies relocations without parsing individual instructions. If we want it to support WasmGC (which may be useful even if the rest of LLVM does not use WasmGC), and we want feature parity with linear memory Wasm, then this is what we'd have to do. Efficient separate compilation and linking is a fairly unexplored part of the WasmGC user space, but we know it will be a blocker for productionization at scale, so I think it's important that we don't paint ourselves into a corner here.

Most toolchains prefer for Binaryen to be an optional component, so having to depend on Binaryen (or more generally, any tool that has to parse and update the full module) here would be a materially worse outcome.

[Liedtke]

Efficient separate compilation and linking is a fairly unexplored part of the WasmGC user space, but we know it will be a blocker for productionization at scale, so I think it's important that we don't paint ourselves into a corner here.

I don't disagree with any of your points, I think I'm just seeing it from a different perspective: Right now there is an active decision to add atomic operations to unshared types as part of this proposal (as a feature).
My argument is that right now this might be a decent inconvenience for multiple engines and so far the use case for the "simple rewrite" tool still is very abstract and might require further changes (e.g. introducing an "unshared" byte marker which could be used to replace the shared byte marker in casts and other instructions taking a heap type immediate.

So not including these unshared atomics wouldn't really block any future work on it and on supporting such tooling because we could always "just" add it in a follow-up proposal with any other changes we'd want to do to support this use case better (and ideally we'd then have some tools that have clear interest in this and can provide guidance on whether the proposed features align with what we'd want to achieve.)

As long as V8 is the only engine though "complaining" that the unshared atomics add additional and potentially unneeded complexity, then my arguments aren't very strong.