Why not enforce externref confinement in runtime?

[mraleph]

Shared-Everything Threads proposal says:

The entire point of the shared annotation is to prevent unshareable embedder values from being shared across threads.

Why not enforce this property dynamically instead of introducing a transitive restriction into the type system? Each externref could carry around some sort of "ownership token" and trying to pass an externref back to the embedder would perform an embedder specific ownership check and cause an error when ownership restrictions do not allow that.

The way things are currently specified in the proposal make it rather challenging, because a single non-shareable reference poisons the whole type IIUC making it non-shareable. This makes it challenging to compile languages where everything is shareable by default.

Consider for example, Java. Everything is shareable there, including containers like ArrayList or Object[]. Now consider what happens we create a subclass of Object which contains a reference to a DOM node inside. Such type can't be shared between threads - so it can't be shared. But that means neither can be Object and Object[] and ArrayList. This breaks uniformity of the representation which is present in the original language.

This is closely related to #5 - I actually think toolchains are going to have a very hard time, unless the source language itself has this "partitioning" into shared and non-shared parts built in.

cc @mkustermann
cc @tlively @syg

[conrad-watt]

Why not enforce this property dynamically instead of introducing a transitive restriction into the type system? Each externref could carry around some sort of "ownership token" and trying to pass an externref back to the embedder would perform an embedder specific ownership check and cause an error when ownership restrictions do not allow that.

It's not enough to prevent exernref from being used (i.e. passed back to the embedder) in another thread. It's even unsafe for an externref in one thread to be captured in another thread, because Web engine GCs won't know how to keep the things it's pointing to live cross-thread. For example, imagine allocating a JS object in one thread, then transferring it as an externref to another thread, and then later transferring it back to the first thread. An engine would need to make sure that anything rooted by the JS object in the first thread isn't collected in the interim - @syg can go into more detail regarding why this is believed to be impractical (esp. in more complicated scenarios based on the above involving cycles).

The immediate next step is to ask why we can't insert dynamic checks at the moment an object would be transferred/leaked between threads, but then the complication is that the "moment of transfer" of an object can be highly implicit (e.g. another object transitively pointing to it could be transferred instead). This has led us to think that static annotations are the right thing, but I'd be happy to discuss other ideas that take the above concerns into account.

I actually think toolchains are going to have a very hard time, unless the source language itself has this "partitioning" into shared and non-shared parts built in.

Realistically, these source languages are likely going to just mark everything in Wasm shared, and then work out how to recover acceptable JS interop using one of the thread-local mechanisms we're proposing.

Now consider what happens we create a subclass of Object which contains a reference to a DOM node inside.

I think the case where the source language wants to hold a strong reference to a DOM node cross-thread is one of the hardest to support in Wasm. But to some extent I think this is an inherent friction in the Web platform (because of the issues with cross-thread GC I sketched above).

There are possible compromises - instead of the compiled Wasm code holding the DOM node as a true reference type, it could more easily hold a scalar handle that points to a slot in a table of DOM nodes managed in JS via thread-local functions called from shared Wasm.

[mraleph]

There are possible compromises - instead of the compiled Wasm code holding the DOM node as a true reference type, it could more easily hold a scalar handle that points to a slot in a table of DOM nodes managed in JS via thread-local functions called from shared Wasm.

I just want to point out that this design has GC complications and can potentially lead to leaks if unused incorrectly. Consider the following:

• You need to make sure that DOM node reference is pruned when it is no longer needed - this means you need to somehow tie the lifetime of that reference to the lifetime of the object which contains scalar handle. This can probably be done by attaching a finalizer (via FinalizationRegistry) to the Wasm GC object which contains the reference. (Though as @syg pointed out this might not even work in the initial implementation - I assume FinalizationRegistry might just leak in the same way WeakMap leaks)
• If you accidentally create a cycle (struct retains a DOM node, DOM node transitively references struct) then this cycle will leak because this cycle goes indirectly through a global array which strongly retains the DOM node.

That's why externref exists to begin with - it avoids these complications with GC.

[milindsmart]

I want to ask a narrow question regarding wasm access to Web API host objects like DOM, but which is related to what you said.

There is a proposal to load wasm modules using <script type="module"/>, and surely wasm will get direct access to Web API stuff someday. On that day, is it not viable to choose to have all processing happen via wasm interacting with the DOM etc.? In this case, won't it be possible to have a strong reference within wasm, rather than the weak one it can have right now because it has to interop with JS?

[mraleph]

Why not enforce this property dynamically instead of introducing a transitive restriction into the type system? Each externref could carry around some sort of "ownership token" and trying to pass an externref back to the embedder would perform an embedder specific ownership check and cause an error when ownership restrictions do not allow that.

It's not enough to prevent exernref from being used (i.e. passed back to the embedder) in another thread. It's even unsafe for an externref in one thread to be captured in another thread, because Web engine GCs won't know how to keep the things it's pointing to live cross-thread. For example, imagine allocating a JS object in one thread, then transferring it as an externref to another thread, and then later transferring it back to the first thread. An engine would need to make sure that anything rooted by the JS object in the first thread isn't collected in the interim - @syg can go into more detail regarding why this is believed to be impractical (esp. in more complicated scenarios based on the above involving cycles).

My assumption was that all objects exist within the same unified heap, but reading this doc - it seems we are designing towards a system where there is a shared heap (for shared objects) and a number of individual unshared heaps. In such design of course you would prefer to avoid shared -> unshared references because having such references would mean that you need to perform GC across shared & unshared heaps at the same time to fully reclaim garbage.

I don't entirely understand why this design is preferred to be honest. You can't collect shared heap without some amount of synchronizations with threads touching unshared heaps anyway (because unshared heaps are pointing into shared heap).

Is it that we want to support GC within unshared heaps without safepointing all threads touching shared heap? If that's an important property we could still achieve it by employing a WB which tracks shared -> unshared references (similar to generational collection). You could perform "minor" collections of unshared heaps without fully marking through the whole shared heap.

There is also a question of how things like WeakMap work - consider a situation where you take a shared object and put it into WeakMap as a key and use some unshared object as a value. Now you have a situation where there is not direct reference from shared object to unshared object, but liveness of unshared object is connected to liveness of shared object. So you can't really perform independent GC anyway you need a GC which works across both heaps. I looked at https://github.com/tc39/proposal-structs and it does not seem to consider this situation at all.

[syg]

Your technical points match my hunch, @mraleph.

The reason that we do not want to require a unified heap basically boils down to allowing existing implementation ship the least risky thing. We're designing an interoperable spec with independent implementations, and "risky" here is admittedly a qualitative thing. Rearchitecting to a unified heap, I feel like, is a high risk thing (but also high reward! for the exact reasons you give). One can argue that the complexities required on top of an isolated heap GC is in fact more risky than rearchitecting to a unified heap, but that's a value judgment that falls on the GC team, and so, having a spec that doesn't require a unified heap to be viable seems less risky.

Edit: to add some more color, rearchitecting to a unified heap is high risk from the perspective of a production VM that must not regress existing workloads.

I would imagine that most of the allocation is going to be on the shared heap anyway.

When compiling from Java, yeah. But when running a web app that uses the same VM that doesn't use multithreaded WasmGC at all, I feel like no? I mean for GCs you gotta tune them for something, right? It seems pretty risky to say, tune them for this cool shiny new feature. It seems less risky to say keep them tuned to the existing workloads.

[conrad-watt]

@syg just to fully understand, if I have an ephemeron with shared key and unshared value, thread-local GC is still possible so long as the shared key is assumed to be reachable during thread-local GC for the purpose of deciding whether to keep-alive and trace the ephemeron's value?

[syg]

What do you mean by "possible"? Thread-local GC is possible in that it won't prevent GC from running and collecting other things it deems dead. But in the case you describe, cycles will result in that ephemeron leaking forever, which is the problem.

[conrad-watt]

My understanding is the following:

• We're envisaging a GC/allocation strategy where there are thread-local unshared heaps and a separate "shared heap", and threads can mostly perform thread-local GC of JS things in thread-local unshared heaps, but occasionally there needs to be a "stop-the-world" GC so that the shared heap can be traced.

• Having arbitrary "shared-> unshared" edges would be incompatible with this plan as it would be impossible to do thread-local GC (can never identify any objects as collectable thread-locally since other threads may be pointing to them).

• However shared->unshared ephemerons are compatible with this plan - during thread-local GC the shared key is assumed to be reachable, and any cycles are identified during the stop-the-world GC (which treats the shared key "normally").

I'm trying to work out if I'm understanding this last point correctly (although if I'm misunderstanding any of the previous points, please also correct me!).

[syg]

I think that's an accurate understanding of an incremental implementation strategy from an isolated heaps starting point. How desirable and performant this strategy is debatable!

From the user code's point of view, it kind of depends on the use pattern of TLS. The hypothesis is that TLS is to be used sparingly. If you stick all your global roots in TLS cells, that's gonna make your world leak.

[mkustermann]

The reason that we do not want to require a unified heap basically boils down to allowing existing implementation ship the least risky thing.

The proposal adds threads & shared types & atomics. So clearly the engines will have to support a unified heap that mutators can concurrently allocate into and concurrently update. That work is unavoidable.

So the argument isn't about the GC / compiler technology (which has to be built anyway) but rather the risk of externrefs, browser embedder layer, correct?

As somewhat elaborated above as well, having multiple heaps, that can be collected independently, but have pointers one way (and weak references the other way) is a technically highly complex, risky thing. It also may deliver sub-par performance due to maintaining remembered sets not only from old to new generation but from one heap to another, the associated write barriers etc. And since the static types tell which heap an object gets allocated into, and languages may compile most of their types to sharable types, it may cause high overhead (as one has to do all this tracking) even for objects that may die very quickly and are never actually shared / concurrently accessed. Also if the heaps are imbalanced (most is shared or most is non-shared) then being able to independently collect isn't that useful.

The hope is that WebAssembly is going to be alive for many years to come, so I think it would be the wrong choice to guide it's specification based on short term thinking (more engineering work in JS engines, ...) at the expense of actual usefulness.

Edit: to add some more color, rearchitecting to a unified heap is high risk from the perspective of a production VM that must not regress existing workloads.

Existing workloads don't use threading & shared memory, so how can they be regressed?

Also one can introduce the capability to spawn a different execution environment that shares nothing with the original heap, but then require those execution environments to communicate with each other via message passing.

Shared and unshared types are never subtypes of one another. The subtype relationships among shared abstract types mirrors the subtype relationships among unshared abstract types.

This is a very problematic aspect. It means there's no top-type. WasmGC is mainly targeted by managed, object-oriented languages. If the language is soundly typed (e.g. Dart, Java, C#, ...) then it almost always has a top type (with some that have value types that are boxable into into top types). The spec as written now makes it extremely hard for those languages to compile to it.

One could think that those languages should simply compile only to shared types, problem solved. Though the problem isn't solved, because those languages have to interact with host objects (aka externrefs) that aren't usable in shared types. Special casing string is nice, but strings will not be the only host object those languages interact with.

Changing all these source languages to have the shared concept in their type systems, for the purpose of targeting wasm (which isn't the main target of those languages), seems very hard.

With current proposal an app will have to choose: Either you can use shared multi threading, but not interact with host objects. Or you can interact with host objects but not use shared multithreading.

=> It will simply hinder the usefulness of this in the first place.

So the suggestion I made (and @mraleph wrote down above) to instead put responsibility on the embedder to check at-access-time seems much preferred. It will make WasmGC multi threading a much more useful technology.

[conrad-watt]

Existing workloads don't use threading & shared memory, so how can they be regressed?

Existing workloads that allocate objects on independent thread-local heaps, and expect GC to be possible thread-locally (i.e. all existing JS code) may be regressed if Web engines transition fully to all objects instead being allocated on a unified heap that requires global sync points for GC. Absent an unprecedented and heroic PR campaign, any feature we propose for Wasm can't have such a clear risk of regressing existing JS (a much larger proportion of the Web).

This proposal is quite a big step in adding further shared memory concurrency to the Web. It may not get us all the way to native language runtime levels of concurrent access, but we're starting from relatively little and working under a lot of platform constraints.

Changing all these source languages to have the shared concept in their type systems, for the purpose of targeting wasm (which isn't the main target of those languages), seems very hard.

I'd expect languages to compile everything to a shared type, and then interact with host externref objects using a handle discipline as I sketched at the end of this post. I agree with @mraleph's response that leaks are a concern. We've discussed some immediate ways to approach this:

1. the source language exposes manual resource management of handles at the source level - e.g. an explicit DOM_node_handle type and drop_DOM_node_handle function rather than a source-level view of a runtime GC-d DOM_node type (which is a fiction anyway unless the Web can relax its restrictions on concurrent access/GC of JS objects);
2. the source language switches to an alternative (async?) model for interacting with a JS host, e.g. in the DOM case, a shared virtual DOM that is periodically sync'd with the main thread
3. the compilation scheme for the source language tries to do something clever with FinalizationRegistry or lifetime analysis/inference, accepting some leaks if the user tries to do particularly contorted things.

[mraleph]

Existing workloads that allocate objects on independent thread-local heaps, and expect GC to be possible thread-locally (i.e. all existing JS code) may be regressed if Web engines transition fully to all objects instead being allocated on a unified heap that requires global sync points for GC.

I am not sure anything really regresses for the existing JS code. If page does not use workers - nothing changes for it. It's heap can be collected in isolation. If page uses workers then you can still partition worker heaps and collect them independently unless page has opted into shared memory by allocating a shared struct or instantiated a Wasm module which spans both main thread and worker thread (details on how to determine which threads Wasm module "spans" is a bit of an open question for me, I guess).

Once you have created the possibility of shared memory you merge heaps into one and perform "global" GC.

In this formulation I don't think there is any actual regression to the behavior of the existing code.

You can do even more sophisticated design where thread local minor heap collections are facilitated via write barriers.