How does GC work w.r.t thread-local-globals?

[lukewagner]

I was trying to think through how a JS embedder's GC would define liveness w.r.t thread-local globals (including WebAssembly.Function({ threadLocal: true })) and it seemed like there were roughly two options, each with significant downsides. But maybe I'm missing another option?

So in the first option, a thread-local-global's thread-local contents are only considered live if there is some reachable path from the Worker's (thread-local) roots to a wasm exported shared function (or shared table or any other shared wasm JS API object) whose entrained (instance) closure state points to that thread-local-global. The downside of this approach is that if wasm stores some state into a thread-local-global from a worker, and then the shared wasm instance becomes temporarily unreachable from that worker, and then a GC occurs, and then the shared wasm instance becomes reachable again on that worker (via some other worker that held onto a reference and sent it back over), the thread-local-global state can get observably reset.

To fix this, the second option is to say that a thread-local-global's entire contents (the cells of all threads) are considered live if the thread-local-global is reachable from a shared wasm instance reachable from any worker. Thus, in the above temporarily-unreachable scenario, the worker's thread-local state would not get reset because some other worker held onto a reference to the shared wasm instance. But now there are two downsides:

1. we've introduced a shared→unshared GC edge, so now a JS GC needs to trace through unshared worker heaps to collect all unreachable cycles
2. once a particular worker touches a particular shared wasm instance (where "touches" can have various eager or lazy definitions), any thread-local storage stays alive until the shared wasm instance is fully unreachable, even if the thread never touches the shared wasm instance again, representing a potential leak.

Assuming there's not a clean way out of this, I do wonder if maybe this is a signal that perhaps thread-local-globals aren't the right technical approach to the TLS problem -- that they put too much magic in the engine and that a lower-level approach might be appropriate. FWIW, I think a variation of the "thread-id" approach could avoid this problem (putting control in guest-code's hands instead).

[tlively]

I know @conrad-watt has thought a lot about this in the context of the thread-local JS function wrappers as well.

Also cc @syg in case you've already thought about this and arrived at a conclusion for the JS side of things.

[syg]

@lukewagner The sketch I've thought about is your second option. The first option doesn't work because it's very surprising if TLS is programmatically available, for the scenario you've discovered.

To your two points, it is correct that (1) TLS fundamentally introduces a restricted kind of shared -> unshared edge, where, because the per thread nature of TLS, the shared -> unshared edge cannot escape the current thread that is viewing the edge. It is also the case that this requires at least a marking phase that can view the object closure of all threads. The semantics of TLS corresponds exactly to a per-thread JS WeakMap (i.e. ephemerons) where the keys are shared. To collect those ephemerons, the shared keys have to die, and since they're shared, that means they're unreachable from every thread.

Edit: The only phases of GC that requires a global view of the world is marking + nulling of dead weak ephemerons. Actual sweeping, compaction, etc, can proceed independently. This is of course a complication, but does not require a full global GC for every phase.

I hear and share some of the leak worries you point out in (2). I don't know if I'd strictly think about it as a leak but as an optimization opportunity that we can explore. Somewhat analogous to this, IMO, is the closure entrainment problem in JS closures. If an outer function has closed-over bindings x and y that are actually used disjointly by separate inner functions, the environment still ends up keeping both alive even if one of the inner closures dies. I know V8 explored doing environment splitting and found it didn't pay for itself, and I've tried and failed similarly for SpiderMonkey in the past. For TLS, the different closed-over bindings are the different per-thread cells.

FWIW, I think a variation of the "thread-id" approach could avoid this problem (putting control in guest-code's hands instead).

What are you thinking of here? Manual management can be done in the automatic TLS world as well by nulling out your own thread's cell, just as one can work around the closure entrainment problem by nulling out unused upvars.

[lukewagner]

It is also the case that this requires at least a marking phase that can view the object closure of all threads.

This seems a bit unfortunate. I had thought that the design of shared otherwise ensured that an implementation could treat all edges from unshared heaps into the shared heap as roots, avoiding the need to ever trace everything at once (which could be pretty tricky to retrofit into preexisting sprawling GC implementations (and their trace hooks...)). If that is otherwise the case and it's just this one particular facet of the design that changes the situation, that seems like a pretty significant cost.

What are you thinking of here?

Despite liking the attractiveness of having a single unified "thread-local global" concept, I was thinking of splitting out the two concrete problems we have:

1. What is a high-performance replacement for an instance-per-thread-global (which can, in the non-aliased case, be stored directly in the "VM context" struct that engines tend to keep a register pointing to, allowing single load/store accesses)?
2. How does shared wasm call into unshared JS functions in worker threads?

I think the solution to both involves avoiding any shared→unshared GC edges, but in different ways owing to the different constraints:

• For (1), we only need one or two i64 values (even wasm-gc just wants to index a shared array stored in a shared global), but we want to be able to access them Really Fast from core wasm via an instruction that ultimately loads from the "VM context".
• For (2), we need to hold an unshared JS function reference, but we can also solve the problem wholly at the JS API level and I think it's "ok" if there's a tiny bit more indirection/overhead compared to (1).

So digging into the solutions I was imagining, at a high-level:

• For (1), I think we can't have a thread-scoped variable, since in a Web Worker context, this becomes a Worker-scoped global value, which I think is considered a non-starter for folks for the usual "no global singleton state" JS reason. Instead, I was imagining a stack-scoped variable, created afresh every time a new wasm "stack" is created, which, today, is every time JS calls into wasm. (JSPI suspend/resume would maintain the same stack.) A stack-scoped variable starts as 0, and we offer instructions to read/write it analogous to local.get/local.set. Thus, JS calling into wasm from a worker can pass in a (param i64) which wasm then writes into a stack-scoped variable and accesses for the duration of the call. If we offer more than one stack-scoped variable, we can use it for the shadow-stack-pointer, thread-id, guest-thread-local-data-base-pointer, etc.
• For (2), I think the key is to have the GC edge go directly from an unshared JS function export wrapper to the table of unshared JS functions callable via imports. This unshared JS function export wrapper would be created from a shared JS function export wrapper by a "bind" method that took as an argument the table of unshared JS functions. There is an inherent "dynamic scoping" going on here (which I expect one could formalize as the export wrapper installing an effect handler for the effect of "call an unshared JS function with this index"). But what this buys us is that, if the export wrappers become unreachable, the unshared imports also become unreachable, all based on unshared local GC. The problem I outlined above with option 1 thus goes away because, once the export wrapper become unreachable, you have to create new export wrappers (binding them to new import-callable functions) if you want to call into the shared wasm instance in the future. With careful design (giving the JS engine the right invariants at the right time), I expect this could be optimized to the same degree as the current SharedFunction({ thread-local: true }) idea.

Sorry for the not-succinct-yet-not-complete answer; I mostly wanted to try to lay out the alternative in enough detail to contrast with the thread-local approach.

[lukewagner]

I don't understand what (1) is about, I'll let the Wasm folks chime in. Like, Java and Kotlin and whatever have TLS with fixed semantics. I don't understand the stack lifetime thing.

I probably wasn't clear about this, but I think (1) is sufficient for a toolchain to implement regular TLS semantics. The difference is that the TLS array is in guest wasm state, not internal wasm engine state. If the language semantics are to leak; that is easy enough to achieve, but it's the guest code toolchain that's making that choice.

For (2), do I understand correctly that the semantics you're envisioning is exactly like ephemeron semantics with shared keys, except the liveness of the ephemeron depends on the liveness of the key in the viewing thread only?

I forget exactly what all "ephemeron semantics" entails, but I think maybe yes? GC-wise, I think it's equivalent to a private strong reference (say, stored in an internal slot) from the unshared export function wrapper to a JS array holding normal JS functions.

[syg]

I probably wasn't clear about this, but I think (1) is sufficient for a toolchain to implement regular TLS semantics. The difference is that the TLS array is in guest wasm state, not internal wasm engine state. If the language semantics are to leak; that is easy enough to achieve, but it's the guest code toolchain that's making that choice.

If the language semantics are to not leak, then how do you envision that to be supported?

I forget exactly what all "ephemeron semantics" entails, but I think maybe yes? GC-wise, I think it's equivalent to a private strong reference (say, stored in an internal slot) from the unshared export function wrapper to a JS array holding normal JS functions.

By "ephemeron semantics" I meant (k, v) pairs where liveness of k implies liveness of v. I was asking if what you had in mind was the same as TLS, except the (k, v) pair can die when k became unreachable at a point in time in v's thread only as opposed to becoming unreachable from every thread, thus requiring recreation.

The crux of the issue seems to me to the "depending on GC timing, user code will need to recreate all its wrappers" thing. That seems pretty bad to me?

[lukewagner]

If the language semantics are to not leak, then how do you envision that to be supported?

It's mostly a question of who is doing the leaking; if wasm guest code leaks linear memory or rooted GC memory, that's not the wasm engine's fault. But at least the wasm guest code is controlling the allocation, so in theory it can do smarter things than the wasm engine, based on the its knowledge of the source language semantics. It's not a huge deal, but we do have this general theme of allowing wasm guest code to control allocation as much as we can allow (see the recent overhaul of the exception-handling proposal to avoid a tiny implicit exception stack).

The crux of the issue seems to me to the "depending on GC timing, user code will need to recreate all its wrappers" thing. That seems pretty bad to me?

What I was describing doesn't depend on GC timing at all: if the export wrappers become unreachable, you can't call them anymore... because they're unreachable. And since the export wrapper objects determine which unshared function imports are callable, when the export wrapper becomes unreachable, so does the configured set of imports. It's just a different runtime semantics than with thread-locals.

[syg]

What I was describing doesn't depend on GC timing at all: if the export wrappers become unreachable, you can't call them anymore... because they're unreachable. And since the export wrapper objects determine which unshared function imports are callable, when the export wrapper becomes unreachable, so does the configured set of imports. It's just a different runtime semantics than with thread-locals.

I think you're just asking for thread-locals with different liveness semantics, where the TLS cell can be independently collected per cell.

I don't think that's the right semantics for general TLS because it is too surprising, since for programmatically created TLS keys in general you don't know if your thread will observe it in the future by being postMessaged the TLS key again. That said your argument though is narrower, and is really just about the syscall table to call out to JS. Maybe there's room for both TLS cells with all-thread lifetimes and per-thread lifetimes.

[lukewagner]

Yes, agreed; I don't think you'd properly call either of the 2 things I'm suggesting above "TLS". From a source-language POV, I agree that these primitives are probably too low-level for direct developer use if what you really wanted was TLS, but in wasm, we're primarily interested in providing the lowest-level primitives we can (with as little magic in the engine as possible), allowing compilers to build up the higher-level semantics.

[tlively]

If I understand the high-order bit here, @lukewagner is concerned about requiring GCs to support shared-to-unshared edges. As @syg mentioned, these edges are already allowed without any kind of TLS if you allow shared objects to be keys in WeakMaps. It's also worth noting that the proposal as currently worded does not allow core Wasm to store unshared references in TLS globals, so these shared-to-unshared edges are only possible if the embedder gets involved. @lukewagner, what embedders are you concerned about having to support this? JS engines? Non-Web Wasm engines that use off-the-shelf GCs? I want to make sure we're all on the same page about the scope of this discussion.

[eqrion]

@syg

The above is a cycle: sobj1 keeps-alive t1obj keeps-alive sobj2 keeps-alive t2obj keeps-alive sobj1. This, as @lukewagner correctly points out above, requires a GC that has a global view of all heaps, or a unified heap GC.

A "global view", while required, can be incrementally implemented. I have prototyped this in V8 in its isolated-heaps world. You need a global stop-the-world safepoint once in a while to mark the entire world.

This is not as bad as it sounds because you've stopped the entire world and you can saturate all the cores to do parallel marking, since no mutators are running. There are complications with pausing other mutators' incremental marking phases that can be overcome by using an out-of-line marking bitmap, for instance. Also, a STW safepoint is required anyway to collect the shared heap.

I don't think we can assume that a global mark phase is a minor addition if we've already accepted STW safepoints.

In your example, the thread local objects may contain DOM nodes or other embedder objects that are not in the JS heap, but are refcounted instead. In Gecko we collect these cycles using per-thread cycle collector that cooperates with the JS GC. If we have a global mark phase, we'll need to update the Gecko cycle collector to be global as well. From some preliminary discussions, we don't believe this will be an easy task.

[conrad-watt]

@eqrion can a non-shared Wasm struct (edit: or function) already be a WeakMap key, or is this not allowed?

EDIT (copying from other thread):

I also think that a user shouldn't be reasoning in the margins about surprising ways to keep objects rooted. From the point of view of keeping TLS functioning, they should just remember to keep the thread-local function rooted in each thread they want to use it. I think one could also construct surprising WeakMap behaviours in pure JS, so I'm not sure that Wasm is much stranger here.

[conrad-watt]

My understanding on where the boundary lies is a bit fuzzy in this case. Would or wouldn't the possibility of non-deterministic trapping show up in the core Wasm spec?

@rossberg only in the host function call semantics, where it's already present

[eqrion]

I believe a non-shared wasm struct/func can already be a WeakMap key.

I also think that a user shouldn't be reasoning in the margins about surprising ways to keep objects rooted. From the point of view of keeping TLS functioning, they should just remember to keep the thread-local function rooted in each thread they want to use it. I think one could also construct surprising WeakMap behaviours in pure JS, so I'm not sure that Wasm is much stranger here.

I still feel like the flavor 2 semantics are more surprising. My understanding is that during one of these independent GC's we could treat the weak keys (thread-local functions) as not-rooted, then see if we still find them through tracing. But we cannot trace through any shared state, as that may be mutated under our feet. So it's not enough to store your thread-local in a shared global, table, struct, or array, it needs to be stored in unshared state or an import (because imports are immutable, which makes them also special). So the definition of what's a root changes from normal JS.

The other dimension is that it seems likely that other engines are going to want to implement the flavor 1 semantics, at which point those intricacies are no longer an issue. I've generally found that no one (including mega cap software corporations) tests on Firefox, so I would be very concerned about portability hazards here. And any issues that show up will be the non-deterministic very difficult to debug kind.

[conrad-watt]

So the definition of what's a root changes from normal JS.

Since we currently don't have any shared objects that can hold references, I think we have some opportunity to set fresh expectations here. The way I see it, the user story is that so long as a thread-local function is kept alive in the way that an ordinary (unshared) JS object is normally kept alive (e.g. by holding it in some persistent JS context), everything "just works". It can be put in other places like a shared table, but this doesn't satisfy the above (since ordinary JS objects can't be placed there). I'd expect that toolchains would normally just keep all thread-local functions they're manipulating alive in their generated JS anyway, so you'd need someone really hammering the edge-cases manually to see implementation differences.

The other dimension is that it seems likely that other engines are going to want to implement the flavor 1 semantics, at which point those intricacies are no longer an issue.

I agree flavour 1 semantics is preferable. I'm concerned about your point that implementing it without leaks seems non-trivial though. Currently I'd still prefer some form of thread-local function (even flavour 2) in comparison to switching to a shared-non-suspendable semantics as a way to get JS interaction.

[syg]

My hope would be to avoid these really-complex GC tradeoff questions (e.g.: "should I add a whole new mode to my GC... or just leak because maybe it's fine in 99% of apps") by exploring the lower-level design I sketched above, which, to reiterate, I think is sufficient to implement TLS (as a source-level language construct) while also having a more-efficient low-level implementation for access and indirect calls.

@lukewagner Starting a separate thread for the clarifying question. 2 questions:

1. Is my Flavor 2 an accurate characterization of your lower-level design? Or did you have something else in mind?
2. If Flavor 2 is an accurate characterization, can you sketch how tooling can implement a non-leaking TLS on top? I'm not entirely sure it's possible. Much like how WeakRef and FinalizationRegistry doesn't let you collect cycles across the JS<>Wasm boundary.

Edit: The only answer I have to (2) is "we'll give you less expressivity by also disallowing shared objects as keys in WeakMaps". That strikes me as a bad position since it disallows composition due to the implementation limitations of today.

[lukewagner]

My claim is that having collectible cycles of GC references that cross workers via shared structs and shared arrays is expressivity that must be directly provided by the runtime.

Yes, I think this is a valid motivation to have shared + wasm-gc. But I don't think this should bleed over into the design of "a new wasm feature that can be used to implement TLS", which is an orthogonal feature.

An important framing for this feature is that technically, we don't even need to add anything at all (thread-local or stack-local storage). A compiler could manually thread a thread-local pointer through all calls via params and implement all forms of TLS in terms of that, and so what we're talking about here is an optimization over that. (To wit: lacking any thread- or goroutine-local storage features, apparently the accepted idiom in the Go world is to manually thread a context parameter through all calls. And SpiderMonkey does this too (b/c TLS is slow) with the cx parameter.) So if we wanted to really scope down this shared-everything-threads proposal to an MVP, we could just punt the whole feature.

[tlively]

I don't think this is something we should punt discussion on b/c it seems like a lower-level, simpler alternative to all these issues with a built-in TLS feature.

To make this proposal palatable to toolchain authors, I think it's important that we don't regress the expressivity of TLS. In the current instance-per-thread model, toolchain authors can store any static number of TLS variables of any type, so that should be possible in the shared-everything model as well.

Whether the new mechanism is thread-local variables or stack-local variables or something else, limiting the number and type of the variables seems overly restrictive for the same reasons that limiting the number and type of normal WebAssembly globals would have been overly restrictive. We could have said that globals can only have type i64 and for anything else they must store indices into tables or memories, but that would have been a pain. We could also have said that you're limited to a small handful of globals, but that would have inhibited composition of modules that need their own globals for their own separate purposes.

[lukewagner]

I appreciate the attractiveness of having a drop-in replacement for instance-per-thread globals; if it weren't for all the subtle GC and runtime implications (which we haven't really touched on yet), it seems like a logical feature. But it also seems like more of an artifact of the abnormal instance-per-thread model than an essential requirement or feature of an abstract CPU. In particular, on a typical native platform, it is userspace that manages the dynamically-sized thread-local block (allowing different OSes, language runtimes, linkage schemes, etc to use different impl strategies). It also seems like there are multiple options at a toolchain's disposal for how to transition existing instance-per-thread usage with minimal disruption, especially given that not all cases of thread-local variables can be represented in instance-per-thread-globals currently and thus a fallback path (that stores thread-locals in linear memory) should already exist.

[tlively]

In particular, on a typical native platform, it is userspace that manages the dynamically-sized thread-local block (allowing different OSes, language runtimes, linkage schemes, etc to use different impl strategies).

Indeed, following this pattern is one of the goals of the current thread-local globals design, although we might be thinking of different definitions of "dynamically-sized" here. We discarded other designs that did not allow the engine to know the size of a module's TLS block at compile time, but we still want to allow modules to declare an (effectively) arbitrary fixed amount of TLS, just like they can with locals and globals. No part of WebAssembly today achieves being low-level by restricting the number or type of something that can be declared.

In the context of a JS engine that can compile and instantiate an arbitrary number of Wasm modules at arbitrary times, their "static" TLS is of course not actually static, but in that context there is no expectation of anything being low-level, so I think that's ok.

if it weren't for all the subtle GC and runtime implications (which we haven't really touched on yet), it seems like a logical feature.

I think @syg has fairly well covered the various points in the design space trading off expressivity and requirements imposed by the GC. If shared WasmGC objects are to be usable as keys in WeakMap and FinalizationRegistry, which they must be to avoid regressions in expressivity from non-shared WasmGC, the GC already has to support shared-to-unshared edges and cycles. So if our TLS-enabling mechanism (whatever it looks like) also imposes that requirement, that's no more burden on the GC than we already had. Are there more GC and runtime implications that we haven't considered?

---

One source of disagreement here is that @syg and I are starting from what we believe are reasonable requirements on the expressivity of WasmGC (and JS) and are happy to accept the consequences those have for the runtime and GC, whereas @lukewagner, you're starting with reasonable (anti-)requirements for the GC and runtime and you're happy to accept the limitations on expressiveness those imply. Unfortunately we cannot have all the expressiveness we want and also avoid new complexity in the GCs. I doubt we will be able to resolve this via GH discussion :)

[lukewagner]

Yes, I agree that there is a fundamental tradeoff to discuss here involving engine complexity, runtime performance and ease of toolchain use and that there's not a free lunch here. My main point is that we should fully articulate and discuss the pros/cons and not (yet) take the "thread-local-globals" cluster of design points for granted.

[eqrion]

One source of disagreement here is that @syg and I are starting from what we believe are reasonable requirements on the expressivity of WasmGC (and JS) and are happy to accept the consequences those have for the runtime and GC, whereas @lukewagner, you're starting with reasonable (anti-)requirements for the GC and runtime and you're happy to accept the limitations on expressiveness those imply. Unfortunately we cannot have all the expressiveness we want and also avoid new complexity in the GCs. I doubt we will be able to resolve this via GH discussion :)

I know that I'm biased here, but I do believe that historically we have given precedence to engine difficulties over wasm expressiveness in the past. From SM's initial research into having the global TLS lifetime semantics (AKA shared objects as keys in weakmaps), we think there are some significant difficulties here (see my earlier comment about embedder's with cycle collectors). If there's no other way to progress, then that could be something we just figure out. But if we have other possible solutions, I think we need to investigate those first.

[fitzgen]

I know that I'm biased here, but I do believe that historically we have given precedence to engine difficulties over wasm expressiveness in the past.

The example that immediately leaps to my mind is how Wasm has avoided irreducible control flow due to existing engines' architectural constraints.

[eqrion]

If I may make an impassioned statement about this whole thing -- adding parallelism to a managed runtime is not a point solution with a scoped implementation. It's a big deal. It will enable use cases that were previously impossible, and those use cases will likely have very different performance characteristics than the existing runtimes are tuned for. It seems that if we're successful here, then it's likely that all competitive, production VMs will want to rethink their current architectures. That may lead to projects of significant difficulty.

But that's a long road, and the only real choice is to start incrementally. I'd like us to start with more expressivity even if their initial implementations suck in some way (e.g. always leak), because my hunch is that will turn away fewer folks who try to adopt.

I agree there's a lot of potential here, and I'm not afraid of long term incremental work. My feedback here is just trying to ensure there is actually a viable path to getting the first step standardized in a reasonable time frame.

Re: expressivity, that's true to a degree, but the other side is that too much expressivity can lead to poor enough performance and behavior (in a feature motivated by performance) that can lead to it not being viable. Expressivity can be added over time, never removed. And again, it's one thing if there is no other option. But I think there is more to the design space here.

Re: always leaking, IMO that's not a viable initial implementation for a shipping threading feature.

[syg]

Re: always leaking, IMO that's not a viable initial implementation for a shipping threading feature.

Responding narrowly to just this point, my claim is the following chain of reasoning:

• Cross-worker cycles is only collectible by the host GC; there is no building block we can spec that would make these collectible in userland (except the ability to hook into the GC's marking phase itself, which is a nonstarter)
• Shared structs as WeakMap keys is equivalent in expressivity to cross-worker cycles
• Disallowing cross-worker cycles and shared structs as WeakMap keys means the only choice in userland is to use a strong map for apps that need to compile dynamic TLS or an equivalent feature
• Using a strong map is actually worse than allowing shared structs as WeakMap keys but not collecting cycles; in the former everything in the map leaks, in the latter only cycles leak, and non-cycles remain collectible
• Therefore, if the choice is to disallow shared structs as WeakMap keys in the MVP for implementation complexity, that is equivalent to always leaking (but actually even worse!)
• So, if solving for engine constraints in this case means user programs have to leak everything anyway, we should start with the more expressive thing and implement the complex GC support incrementally

[syg]

Additional disclaimer: the expressivity I've been talking about are really for expressing dynamic TLS or other programmatic means to associate unshared data with shared data. For declarative TLS where everything is already a root, there are much superior implementation strategies. The two domains are orthogonal.

[eqrion]

@syg can you elaborate on the distinction between dynamic and declarative TLS in the context of WebAssembly where module are proposed to declare TLS but are programmatically created? I think in that case it all becomes dynamic, but I just need to make sure that's what you mean.

[eqrion]

For those interested, I posted an alternative to thread-local globals and functions in #42.