Proposal: Stack Walking

[RossTate]

Based on feedback from the discussion at the CG meeting, @fgmccabe and I would like to propose adding stack-walking primitives to WebAssembly based on the primer in WebAssembly/exception-handling#105. For those new to the topic, the following is a high-level description of the proposal.

Many high-level languages keep the stack as an abstract entity that is heavily used for implementing the language but which the programmer rarely directly manipulates. This proposal is for a small suite of primitives that enable language implementers to provide specific functionalities that depend on access to the stack but without compromising the security guarantees provided by WebAssembly. Examples of enabled functionalities include better support for language-provided garbage collection, better support for debugging, better support for exception handling, support for stack-allocated closures, support for simple yield and resume computations, and, in contemplated future extensions, support for stack switching and coroutining.

The core of the stack-walking functionality is centered around two features. The first feature is executable stack marks, which associate stack frames with executable code. This executable code can, for example, indicate what line of source code the stack frame corresponds to, can inform which 32-bit integers on the stack frame correspond to addresses that should not be collected as garbage, and can display the source-code-relevant contents of the current stack frame and even update the contents of the stack frame. The second feature is a framework for stack walking, which enables WebAssembly code to walk up the stack to find and execute these stack marks.
The stack-walking functionality imagined does not permit arbitrary inspection of stack frames nor of arbitrary locations on the stack. Rather, the regions of the stack that are intended to be inspected are declared as part of the stack-mark primitives. This is so that stack walking can be done in a safe manner within WebAssembly, keeping in line with WebAssembly’s existing security considerations, and furthermore can be designed independently of features such as memory-managed references, maintaining compatibility with low-resource engines.

We propose establishing a new activity to clarify and specify these primitives and to construct a formal proposal for adoption by the WebAssembly community.

[kmiller68]

This feels like a distraction to work around speccing a host provided GC. I can see why this would be useful for some runtimes that want to port to WASM but I don't think this is worth investigating at this time.

Maybe this makes sense in a non-web context but for hosts that already have their own GC this will cause enormous problems. In particular, for a host that doesn't have a precise GC already this is an extraordinary new overhead. Then they're all the problems that come with a platform that has two GCs interoperating, which is hard to get right even if both GCs were built with the other in mind. Then, even after we solve all of that, we'd still have to convince our security team that allowing malicious code to stack walk in a process that has your bank account number in memory is a good idea.

Thus, I think this committee would be much better served by focusing on a GC proposal. I understand that existing runtimes have very specific requirements but, frankly, there's no way I can see this shipping in the foreseeable future...

[KronicDeth]

For implementing Erlang green threads, we would really like the stack switching primitives. Can we get those without the parts that @kmiller68 finds objectionable?

[RossTate]

Ah, this is definitely in need of clarifying. This proposal is intended to be orthogonal to the GC proposal. In fact, until the very last feature—first-class stacks—the proposal makes no use of references whatsoever. The garbage collection we are talking about here is solely garbage in linear memory, i.e. the garbage that the host and the GC proposal currently has no intention of helping collect. There is also no expectation that the host's garbage collector would interact with this proposal at all. The proposal primitives themselves make no mention of garbage collection—garbage collection of linear memory just happens to be a known application of these primitives. @kmiller68, does that clarification address your concern?

[kmiller68]

Any of these stack marks require some way to enumerate all of them, correct? For runtimes with a conservative GC that's not something we track and would be a significant change. Right now, JSC just scans the C stack for anything that could be a pointer into the heap without worrying about if that frame is C++/JS/WASM, or even where frame boundaries are. None of our WASM pipelines have to know anything about where a value ended up being stored. So this proposal introduces an enormous VM overhead that didn't exist before. This is the biggest concern I have.

A very large percentage of DOM APIs require a JS object as a parameter. So, a developer needs to handle references in both directions, effectively meaning there are two GCs. The only other realistic option is to paint on a canvas, which is probably even worse from the end users perspective (e.g. accessibility, performance, etc). We have history of this with Flash. If we're going to expose API in WASM that enables a GC, I strongly want that to be the browser's GC first because those are integrated into the host already. The web platform as a whole already has a story for how this will work cleanly. I worry that if we go the other way and make this the first option it dramatically raises the bar for the true GC proposal as it now must significantly better than this for developers to adopt it.

[RossTate]

Enumeration of executable stack marks is done through stack walking and through code ranges, a generalization of the process used to find the handler for a given thrown exception. The host's GC does not need any awareness of them, for the same reason it (presumably) ignores exception-handling tables. It occurs to me that you might be thinking "executable" means something like a closure, and therefore something that might have references that need to be accounted for during garbage collection, but it's simply a compile-time-constant code pointer. It's hard for me to describe the implementation in a little text box, but I'm happy to chat with you about it. I think your concerns have already been addressed and are one reason I chose this particular design strategy over other variants.

As for linear-memory garbage collection, it is just one of many applications of stack primitives. It is also one of the easiest to implement using stack primitives. So we cannot make the other applications available without also making it possible for a module to use these primitives to implement its own linear-memory garbage collector. It's even the application that can be most easily implemented without these primitives.

I hear your concern about competition with the GC proposal. I also agree that the GC proposal should be the encouraged target for GC languages because it facilitates better cross-module memory management. But I am less concerned about the competition for a few reasons. One is precisely because it works better across modules, which on its own will prompt people to prefer the GC proposal. Another is that the GC proposal should be easier to target for many GC languages. And one more is that host-managed GC can be specialized to the machine at hand, like 32-bit vs. 64-bit, and does not have to operate behind wasm's safety, like scanning the stack directly rather than having to look for and execute stack marks via code ranges.

There is also an opportunity for the proposals to assist each other. In particular, the GC proposal(s) do not currently have a great plan for "complex" initialization patterns, such as constructors in Java and C#, especially across abstraction boundaries. I've been sketching out how one of the concepts from this proposal, namely stack-bound types (an example of which is stack-allocated closures), can be used to enable such complex initializations safely and across abstraction boundaries. And in the other direction, features like first-class stacks need host-managed garbage collection.

In the end, although both these proposals facilitate garbage collection, I believe they serve fairly complementary domains, and developers will simply target the means that most naturally fits their domain rather than jump through substantial hoops to use the other.

Does that reasoning jibe with you?

[aardappel]

I worry that if we go the other way and make this the first option it dramatically raises the bar for the true GC proposal as it now must significantly better than this for developers to adopt it.

It seems to me that technologies that give developers options tend to win, whereas trying to force developers to only follow one "right" way to do it never ends up well, especially if it's not the way they'd prefer.

While there is overlap, these are not competing proposals, there is significant amount of things you might want to bring to Wasm that are outside the realm of native GC that this technique could help with.

Also, I don't understand the "we should focus on the GC proposal".. we've been staring at the GC proposal mostly unmodified for 2+ years now, it is not like mere discussion of other potential Wasm features would take away time from its progress.

[jgravelle-google]

While there is overlap, these are not competing proposals, there is significant amount of things you might want to bring to Wasm that are outside the realm of native GC that this technique could help with.

As a general principle, I strongly believe we should have competing proposals. If the new proposal wins spec-developer mindshare, it's a sign that the old proposal was lacking. If someone magically comes up with a new, better Interface Types proposal that wins across all axes, I want that to ship. I'm not attached to our current proposal, I'm attached to solving the problem. If the new proposal solves the same problem and wins out on time-to-market, that's good news.

In general, proposals should compete on their own merits. If stack walking doesn't interop as nicely with host GCs, that's a point of non-overlap that is left unsolved. But if developers think that's good enough and don't find the lack of interop to be a problem, then it's good enough and we've made the world better. If we then never get around to implementing the GC proposal because there isn't enough incentive because we solved enough of peoples' problems, then we have solved their problems.

[RossTate]

Besides the issue of competition, it is important to make sure that this proposal wouldn't significantly complicate engine implementations. @kmiller68, should we video chat about this and afterwards write up what we think would clarify our intentions/perspectives here? I'm worried that text boxes aren't the best medium for getting on the same page about implementation details and concerns.

[RossTate]

@kmiller68, Filip, and I had a through discussion about this proposal with a number of important points considered. Here is a summary of the primary takeaways:

1. We clarified that the proposal does not significantly impact garbage collection for the host. However, it is worth noting that marks could notably complicate and constrain register allocation, imposing an indirect cost.
2. Many of the applications of stack walking could also be done using shadow stacks. Maybe there would be some costs to these shadow stacks, but it is reasonable to believe that they could work well enough, and possibly even just as well. As precedent to consider, C/C++ compilation to wasm uses a shadow stack.
3. There is a substantial security concern here. While stack walking is conceptually straightforward, there are a number of corner cases behind the scenes, and an off-by-one error in just one of these corner cases could be easily exploited.
4. The Garbage Collection proposal should be the encouraged target for GC languages for a number of reasons. However, if this proposal were to ship substantially before GC (which is quite plausible given the simplicity of stack walking in comparison to memory management), then even languages that would be served better by targeting the GC proposal would be pressured to instead target this proposal, establishing infrastructure that would be difficult/slow to turn over once the GC proposal eventually ships.
5. Given the cross-cutting nature of this proposal, there is reason to be concerned about compatibility with other major proposals, such as Type Imports, Garbage Collection, and Interface Types. It also seems likely that compatibility issues that arise would be more easily resolved through revisions to this proposal than to those, suggesting that those proposals should ship first.

All of these takeaways resonate with me. Note that in this discussion we focused specifically on stack marks and walking. We also focused on just understanding the proposal and relevant concerns, rather than what to do about them.

[aardappel]

As for (2), I believe there is potentially a significant cost for a language to move most/all of its values from the Wasm stack to a shadow stack, as you're missing out on many LLVM optimisations (e.g. Mem2Reg) and there being a big speed (and code size) difference between having all your values in locals/wasm stack vs accessing each of them over loads/stores with access to __stackpointer global etc.

This cost is especially problematic for languages where the bulk of the code has no need for a shadow stack, but it would be required just to support a single feature (like the ones enabled by stack walking mentioned above).

C++ currently only uses it where needed, which is infrequent in C++. For a language that would need access to all pointers this way would be a lot higher.

A shadow stack is a nice escape hatch to allow a language implementation to do "anything" that Wasm currently doesn't support, but it is a high price to pay, and will put an even bigger distance performance wise between it and "efficient" languages like C/C++/Rust. Stack Walking could fix that.

[fgmccabe]

One could go even further than this; and ask the question 'why does WASM even have local variables?' Everything could be done by manipulating memory -- shades of FORTRAN.

[kmiller68]

As for (2), I believe there is potentially a significant cost for a language to move most/all of its values from the Wasm stack to a shadow stack, as you're missing out on many LLVM optimisations (e.g. Mem2Reg) and there being a big speed (and code size) difference between having all your values in locals/wasm stack vs accessing each of them over loads/stores with access to __stackpointer global etc.

Why do the variables need to live in the shadow stack? For example, couldn't the LLVM raising to WASM just flush variables to that frame's shadow frame at escape sites. IIRC, from JSC's days compiling to LLVM, it's capable of tracking the location of any variable for you as long as you are careful enough.

[aardappel]

@kmiller68 I don't see how that is of any help if you need access to potentially all (pointer) variables for use in stack-walking. They'd all have to be on the shadow stack.

[kmiller68]

@aardappel Isn't that exactly what the WASM VM would have to do but on the native stack? To clarify, my proposal was not talking using the shadow frame as the source of truth for the function (I think this is called a Henderson Frame but it's been a while). I'm only saying that whenever a store happens to a variable you also store a copy to the shadow frame. This is functionally what the WASM VM is going to do anyway. For what it's worth, I also think this is no more complicated than tracing which variables are needed for the stack walking API. In fact, I would probably use the same abstraction to do both in my compiler.

The only optimization I can think of that stack marking can do, which shadow frames cannot, would be to figure out where callee save registers got saved in the callee. But doing that would potentially mean spilling every callee save on any host call (native or JS). It could also make walking the stack slower since you'll need to maintain callee save information. So it's not 100% clear if tracking callee save registers would actually be profitable, although it could be.