Are Formal Stack Overflow Semantics In WASM + Emscripten a Possibility?

[Hostile Fork]

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

[Brion Vibber]

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

--
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 emscripten-disc...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/emscripten-discuss/5b3b2f19-96b9-46fd-b131-5af8abb86d6a%40googlegroups.com.

[Thomas Lively]

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.

To view this discussion on the web visit https://groups.google.com/d/msgid/emscripten-discuss/CAFnWYT%3DYNJbKcWZB0mGNsKKqNynW9BXY1Wsucsi%2B%2Bz5wGpd8Kw%40mail.gmail.com.

[Brion Vibber]

On Mon, Nov 4, 2019, 1:50 PM 'Thomas Lively' via emscripten-discuss <emscripte...@googlegroups.com> wrote:

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.

Do you know if the tail call proposal is implemented in any engines yet? That would be very useful for emulators doing dynamic recompilation as well.

-- brion

[Thomas Lively]

It's implemented behind the `--experimental-wasm-return-call` flag in V8 and is supported by emscripten with `-mtail-call`. I don't know about other engines, though.

--

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 emscripten-disc...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/emscripten-discuss/CAFnWYTnHkHaxOS1YHLiao7uws4vi1r-2-HUX-FkyL%2BFaAKMXXg%40mail.gmail.com.

[Hostile Fork]

Hi Brion, thanks for the information!  (Sorry, I posted earlier in the week then got a bit busy...)

On Monday, November 4, 2019 at 3:49:39 PM UTC-5, Brion Vibber wrote:

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.

That could be useful -if- you had associated atomicity guarantees.  But is even malloc() itself guaranteed to -either- successfully execute -or- throw a stack overflow, leaving the heap in a safe state?  Or might a stack overflow happen in mid-bookkeeping of the C library functions?

malloc()'s atomicity would be a necessary (but not sufficient) condition to get safe stack overflow handling in a C-to-WASM program.  You still need some knowledge of how to bracket composite code of your own with an "all of these operations will run, or none do" mechanic.

(Can that even be achieved in plain JavaScript, or can stack overflows occur from within "system" calls there as well?)

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.

Okay... so the concept of the "locals" that *aren't* stack allocated, would thus live in the "native stack" somewhere (?)

But you can access that stack pointer and see how close you are to the edge.

If there's no other choice but this, it would be good to have it documented how to do "right" and put into some regression test.  A previous trick we used for detecting stack growth direction and measurement stopped working with the binaryen update:

https://github.com/metaeducation/ren-c/blob/8f0dd1347b38958c0dff5c8e36256148eaf3de15/src/core/b-init.c#L114

I'm not sure what broke.  I had suspected it was because the frames were being allocated from the heap and not following any pattern (which wold be free game according to the spec).  But it doesn't sound like you're saying it does that...

Thanks!

--Brian

http://hostilefork.com

[Sam Clegg]

The problem is that even if you can detect when you are nearing
exhaustion of linear memory (and thus exhaustion of shadow stack
space), you have no way to know when you are nearing the VM's stack
limit. IIUC the stack limit of the VM is implementation defined and
can't be relied upon which means that currently I don't think its
possible to do what you are trying to do.

Also note that the shadow stack (the one you can measure) only grows
when you use address taken local variables (or alloca) so in general I
would expect to grow more slowly and the invisible VM stack which is
going to grow by a non-zero amount on each call (I don't think any JS
VMs currently implement automatic tail calls).

> --
> 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 emscripten-disc...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/emscripten-discuss/a8417cf2-e473-4f1b-97ee-219b8e0de7ad%40googlegroups.com.

[Hostile Fork]

On Friday, November 8, 2019 at 8:27:13 PM UTC-5, Sam Clegg wrote:

IIUC the stack limit of the VM is implementation defined and
can't be relied upon which means that currently I don't think its
possible to do what you are trying to do.

Alas.  :-(  To try and establish a sort of baseline about stack overflow handling in JavaScript hosts, I posted a question on...Stack Overflow:

    https://stackoverflow.com/q/58908855/

It's my attempt to clear the air a bit about whether or not there is such a thing as "safe" recovery from a JavaScript out-of-stack RangeError.  My suspicion seems to be confirmed--that the JS spec does not have the systemic rigor to support it coherently.  Even if there's some level at which a particular engine guarantees atomicity to avoid certain internal corruptions, the portions of the language implemented in JavaScript itself would likely not have any such bulletproofing.  That's to say nothing of your own usermode code, which cannot maintain invariants when there's no firm ground to stand on.

There's a suggestion that coding directly in Wasm could offer enough confidence to build some kind of transaction mechanic.  But with C being a layer of abstraction atop that, I do not believe Emscripten has this safety.  e.g. the following code was always was in state `1` when the RangeError is trapped...and I'd guess that's the internals of malloc():

    int state = 0;  // 1=malloc(), 2=free(), 3=recurse() itself

    EMSCRIPTEN_KEEPALIVE

    void recurse(int depth) {  // I called this from a JS try...catch 

        if (depth == 0)

            return;

        state = 1;

        void *dummy = malloc(depth);  // overflowed in here

        state = 2;

        free(dummy);

        state = 3;

        recurse(depth - 1);

        state = 0;

    }

I don't know an easy way to *prove* the heap can get corrupted by this.  If anyone can build a repro case that does so, that might be an interesting emscripten GitHub issue for anyone researching the topic to find (even if resolved: WontFix)  Maybe there's a clang equivalent to mcheck() to get this proof?

...BUT what I'd really like to see would be something in the tooling that helped mitigate this.  It is unfortunate to force people into a shallow-stack custom bytecode interpreter just to get the sole benefit of (hopeful) safe recovery from stack overflows.  I'll re-suggest that building to Wasm and having the hooks into the compiler (like those used to accomplish Asyncify) could permit a stack cost model, and you could choose to force a stack overflow *before* running operations that might otherwise overflow in mid-operation.  Analogous to:

    void transaction(void) {

        void *data = malloc(...);

        /* dostuff */

        free(data);

    }

    void whatever(void) {

        /* ... */

        crash_if_not_enough_stack_for(transaction);

        transaction();  // guaranteed to run if we get here

        /* ... */

    }

Again: I'm aware that you can abstract away the C into your own universe where you attempt something analogous (though much slower).  It's just frustrating to already be inside of virtualized machines when doing so--and to be operating on guesswork even then--with the ball punted from '89 getting kicked even further down the road.  :-/  If Wasm could be a turning point to more of a RTOS/embedded mindset, that could really help raise the bar on software reliability...and strengthen the argument for Wasm as the future.

Best,

--Brian

http://hostilefork.com