If you really want to avoid the native call stack from being exhausted by in-wasm recursion, another interesting avenue to pursue besides a bytecode interpreter would be a continuation passing style code transformation to use only `return_call` instructions from the tail call proposal, which don't add new native stack frames. If you combine that with a code instrumentation to check the remaining space on the linear memory stack, I believe you would be safe from unexpected stack exhaustion as long as you stayed within wasm.
On Mon, Nov 4, 2019 at 12:49 PM Brion Vibber <[email protected]> wrote: > There are two distinct stacks to deal with in the emscripten world: the > native call stack and the linear memory stack. > > The linear memory stack is maintained by convention within the WebAssembly > code, with the stack pointer in a global variable which points at a region > of linear memory, and is just used for stack-allocating data that needs to > have its address taken or otherwise cannot fit in locals. A function that > doesn't allocate stack data might make recursive calls without ever moving > the linear memory stack pointer, or a single function might allocate huge > amounts of data dynamically. But you can access that stack pointer and see > how close you are to the edge. > > Meanwhile the native call stack is where the "real" stack frames for > native, JS, and WebAssembly functions live, and from WebAssembly or JS you > have _very_ few means to introspect it. In particular note that JS/Wasm > engines will prevent too-deep recursion safely -- but using vendor-specific > limits with no consistency or standards. > > The good news is that too-deep recursion has reasonably predictable > behavior _after the fact_ -- a trap/exception is thrown on a too-deep call > for the native call stack, which will unwind all the Wasm functions on the > stack up to the nearest JS catch block. > > The bad news is that there's no checking _ahead of time_ for the native > call stack. You either have to try to maintain a depth counter yourself > along with external knowledge of how deep various browser implementations > allow the stack to get, or you let them run until they die and then clean > up. This requires carefully keeping track of what happens when an exception > gets thrown, and proper cleanup may require adding explicit > exception-handling try/catch blocks to intermediate functions, which means > call-outs between Wasm and JS. > > -- brion > > > On Mon, Nov 4, 2019 at 12:11 PM Hostile Fork <[email protected]> > wrote: > >> I'm asking from the perspective of writing a language interpreter...where >> each user function call increases the stack depth of the underlying C >> interpreter by some amount. (Similar to a CPython implementation.) >> >> I know there is a tactic of rethinking your language to use a >> bytecode--in which recursions in code the user writes don't increase the >> stack depth of the C interpreter. This means you expand your user's stack >> with something like a malloc()...hence "stack overflow" isn't a >> standards-breaking-semantic-failure-of-C, it's just conventional "memory >> exhaustion" and you can catch it. (Similar to a PyPy implementation.) >> >> But--here's my thinking: running in a browser isn't exactly "bare >> metal". You've got a whole JavaScript engine and an instrumentable WASM >> backend that can pull off things like Asyncify. Should you *really* have >> to throw in another layer of bytecode, *just* to get enough awareness to >> gracefully prevent stack overflow crashes? Isn't there some kind of way to >> say "I'm going to call this WASM function, and the compiler knows it would >> take up N amount of stack, so tell me if I have that much before I call >> it"? And if it is recursive, couldn't it have some relation in it to give >> it the self awareness to say how much just *one* call would make, along >> with a promise to check before it decides to make another? >> >> Just wondering if anyone out there is thinking along these lines. But if >> not, then... >> >> ...is there any chance at being able to get some measure on a thread of >> about how much space is left on the stack, enough to make a bit of informed >> guesswork in recursive routines of whether they want to recurse further? >> I'm not supper happy with the CPython method of telling users "guess an >> integer recursion limit, if you crash irrecoverably then lower it, if you >> think you can raise it without crashing then give it a shot". >> >> Thanks, >> --Brian >> http://hostilefork.com >> >> -- >> You received this message because you are subscribed to the Google Groups >> "emscripten-discuss" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to [email protected]. >> To view this discussion on the web visit >> https://groups.google.com/d/msgid/emscripten-discuss/5b3b2f19-96b9-46fd-b131-5af8abb86d6a%40googlegroups.com >> <https://groups.google.com/d/msgid/emscripten-discuss/5b3b2f19-96b9-46fd-b131-5af8abb86d6a%40googlegroups.com?utm_medium=email&utm_source=footer> >> . >> > -- > You received this message because you are subscribed to the Google Groups > "emscripten-discuss" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To view this discussion on the web visit > https://groups.google.com/d/msgid/emscripten-discuss/CAFnWYT%3DYNJbKcWZB0mGNsKKqNynW9BXY1Wsucsi%2B%2Bz5wGpd8Kw%40mail.gmail.com > <https://groups.google.com/d/msgid/emscripten-discuss/CAFnWYT%3DYNJbKcWZB0mGNsKKqNynW9BXY1Wsucsi%2B%2Bz5wGpd8Kw%40mail.gmail.com?utm_medium=email&utm_source=footer> > . > -- You received this message because you are subscribed to the Google Groups "emscripten-discuss" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/emscripten-discuss/CAJZD_EUMNvLL8%3D8JOiBsAZ92i3LxEMrfffUfnM41bKGnq5V56g%40mail.gmail.com.
