-
Notifications
You must be signed in to change notification settings - Fork 19
A few other folks and I spent some time refining our understanding of the design space here after the in-person CG meeting, so I wanted to share a summary of what we worked through. Additional ideas and observations welcome!
Avoiding cycle detection in engines requires garbage in generator loops
To make it impossible to create unreachable cycles between suspended continuations, continuation references can be internally represented as pointers to single-use wrapper objects containing pointers to the underlying stack resources. The pointers in the wrapper objects are cleared whenever they are used to resume a continuation and a new wrapper object is allocated every time a continuation suspends. Setting up an unreachable cycle between continuations would involve resuming one of them to pass it a reference to the other, but that same resumption would break the cycle by clearing the reference that the other continuation holds. Allocating and freeing these wrapper objects may be a significant cost for uses such as tight generator loops.
Garbage-free generator loops require cycle detection in engines
To avoid generating garbage in tight generator loops, the internal representation of continuation references must contain pointers to the underlying stack resources rather than to single-use wrapper objects. These pointers remaining valid across multiple resumes makes it possible to create unreachable cycles between resumable continuations that simple reference counting would be unable to free.
All reactions
Replies: 5 comments 28 replies
I am not sure GC is a particularly informative consideration. For example, it is pretty easy to make all the fiber instructions operate on a table of fibers without fiberref being a first-class value. From what I've heard, this table approach lines up well with how non-WasmGC producers are likely to work with fibers. For example, GC languages compiling to linear memory via root scanning have indicated they need a table of all fibers so that they can scan them for refs-as-ints during their own implementation of GC. This also makes it easier for resource-concerned engines to cap how many fibers an application can have by limiting the maximum total size of fiber tables. For WasmGC producers/engines, there can be a small "combining" extension that makes fiberref a first-class value and adds the obvious counterparts, much like the function references proposal does now.
All reactions
For example, GC languages compiling to linear memory via root scanning have indicated they need a table of all fibers so that they can scan them for refs-as-ints during their own implementation of GC.
Can you elaborate? Like what specifically within them is being scanned? I'm not quite sure what's being spelled out here.
All reactions
A number of GC languages have indicated they plan to target linear memory (implementing their own GC in linear memory) and would like WebAssembly/design#1459 (which has been approved for Phase 1) to facilitate finding i32s representing object references (presiding in linear memory). When combined with stack-switching, this requires being able to scan suspended stacks, as well as the active stack, and as such they need a table of all (suspended) stacks to enumerate over.
All reactions
Oh okay. Thanks for the explanation.
All reactions
I like the idea of making it a table. It's pretty easy for such non-GC producers to just track it with a free list. That does come with a caveat, though: there's not really any way to shrink tables after.
All reactions
Good point. In general, there seems to be a trend pushing for wasm to give more control to letting applications manage their own resources.
All reactions
@RossTate On an tangential note, it makes me wonder how useful the GC proposal is really, especially if/when refs get similar treatment to block memory. By that point, you could just use tables to wrap anything from the outside world.
I could still see it being useful in that GC'd languages wouldn't have to ship an entire collector as part of their result, but it wouldn't be necessary or even all that useful for most non-GC lanugages when compiled to WebAssembly.
All reactions
The proposal of using a wrapper to the underlying stack is exactly how OCaml implements suspended continuations, though the motivation for this choice is different. OCaml uses it to ensure "at most once" resumption of continuations. Allocation & GC are not the bottleneck in our use cases.
Does the table of fibers approach somehow avoid the problem of unreachable cycles between suspended continuations? I assume that continuations are merely indices into the table? If that's the case, it would not be possible to know whether there are cycles, would it?
In addition, some other mechanism would be needed to ensure the "at most once"/one-shot resumption property for continuations and avoid the analogue of "use-after-free" bug. One approach to avoid the "use-after-free" bug might be to represent continuations as a pair of an index into the table and a counter, the counter is incremented every time the continuation is resumed. Before resuming a continuation, one would need to check that the counter value in the continuation reference matches the current counter value at that index in the table. With the wrapper-based approach, "user-after-free" bug is avoided at the cost of an allocation per suspension.
All reactions
The main concern is that some systems want to be able to guard themselves against erroneous applications, which implies that they need to be able to reliably reclaim the app's memory after its termination, even if the application leaked. Otherwise, a buggy app could compromise the host, even if the host is otherwise able to abort and clear out misbehaved apps.
Stack tables would seem to fall in the same category as reclaiming linear memory. If all applications referencing a stack table have terminated, then the stack table (and typically its contained stacks) can be reclaimed.
All reactions
(And of course, table entries are first-class anyway in the presence of table.get/set.)
I'm assuming that engines that would be interested in this approach wouldn't allow table.get/set, just like how MVP Wasm didn't have table.get/set.
All reactions
@tlively, I'm not sure what you envision, but table.get/set are standard now, so if we want to specify anything we need to specify it in a way that is meaningful in the context of the full language. (Also, telling engines to forego the standard to solve their problem is equivalent to admitting that the language does not address their use case.)
All reactions
@rossberg ... does not address their use case
Indeed. But, in fact, many language implementers do not see being able to use WasmGC in the foreseeable future (go-lang, Scheme, Swift, Erlang to name a small sample).
However, I do think that this is kind of orthogonal to table set/get.
All reactions
@fgmccabe, sure, I don't think WasmGC has anything to do with this question.
All reactions
Another idea came to mind. We already know that to support multithreaded work-stealing, we will (eventually) need a notion of "shareable" stacks that contain only "shareable" references. To be more precise, it's okay for an active stack to (temporarily) have non-shareable references, but they need to be guaranteed to be off the stack by the time any suspension occurs. There's various ways to achieve this (so I won't go into illustrating one), but it occurs to me that non-wasmgc engines could reuse a slight variant of the same device to require a suspended stack to have no references. That is, such an active stack could temporarily use references (e.g. fetching a fiberref from a table in order to switch to it) so long as they're not stored on the stack (e.g. not stored in a local) at any point a suspension could occur. This would prevent cycles while not requiring all stack instructions to operate on a table. It would also be helpful for even WasmGC engines, as it would allow them to skip scanning such stacks except during "deep" phases cleaning up instance objects and code objects.
All reactions
64 bits should be enough. 2^64-1 ~= 10^20 seconds at 1 switch/nano amounts to 584 years before a roll over.
All reactions
@fgmccabe Wrong thread (though my fault—I didn't realize Discussions supported threads when I first posted this, so I moved the relevant portions to the relevant subthreads after the fact).
All reactions
-
😄 1
I feel the overhead concerns are a little bit overblown regarding GC-style cycle collection for stacks. Realistically speaking, you're more likely to see hundreds at most for embedded runtimes, and at that scale, a mark and sweep algorithm is actually realistic. If they pack the mark/sweep bits separately, even 1000 of those is literally just 250 bytes (1 bit in-use + 1 bit allocated) of overhead compared to 4000 bytes just for the saved stack pointers alone. I don't see this scale presenting very many perf problems personally.
For larger embedded systems, I expect there to be enough headroom that most runtimes would be willing to support WasmGC anyways, so I doubt it'd be too much of an issue, but even 10k (also an exceptionally high number) isn't too bad to enumerate IMHO.
All reactions
In our design discussions we are targeting for a potential number of suspended computations of approximately 1 million. This is based on reported use cases for languages like Kotlin.
All reactions
That's fair. I was just focusing on the embedded side. At the scale of a million, I was thinking it's more likely the runtime would just be offering WasmGC as well (and so they could fuse stack management into that).
Of course, I'm open to being proven wrong here. And of course, while Kotlin's a garbage collected language, Rust and C++ certainly aren't, and those might be a little more compelling in terms of not doing reference counting.
Alternatively, just specifying cycles that don't go through GC'd structs may/must leak is a valid solution. Might not be the prettiest, but the simple way may very well be the best way.