Implement stack overflow protection for webassembly

[markshannon]

Implementing stack overflow protection for webassembly is tricky, as there are two stacks:

1. The hidden webassembly stack
2. The stack used for C stack objects that can have their address taken

We need to avoid overflowing either. It generally seems that the first stack is the one most vulnerable to overflow, so perhaps a simple counter would work.

@brettcannon
@hoodmane

Linked PRs

• GH-130397: use __stack_high and __stack_low LLVM WASM attributes #131855

[hoodmane]

If the spilled stack ever overflows, we can just recompile and make it bigger whereas the wasm stack size is determined by the runtime and can't easily be made bigger. At least for Emscripten run in the browser. Perhaps with wasmtime we can easily ask the runtime to make the stack bigger.

[markshannon]

This is about runtime detection of stack limits, rather than increasing the stack size.

Is it possible to get the size of the wasm stack from the browser or wasmtime?
Also is it possible to get the current stack depth?

Alternatively, is it possible to catch a stack overflow in JS? We could maybe write a JS helper function to probe the stack.

[hoodmane]

It's possible to catch a js stack overflow. I've used the probe approach before but unfortunately the ratio of the number of js stack frames it takes to overflow vs the number of wasm frames is inconsistent between V8 and spider monkey. They have similar apparent wasm stack sizes but spider monkey can handle many more nested js frames than V8 iirc.

[hoodmane]

I think in node there are ways to query the stack size and depth but it is not part of the web standard and I think browsers don't include any such APIs unless you start the browser in a debug mode.

[brettcannon]

I don't think wasmtime specifically, or WASI in general, provides an API exposing stack details. As Hood said, the best you can probably do is set the stack larger than you're expecting when you launch the WebAssembly host and have Python's stack detection try to handle things, but I know that negates the point of what you're trying to do.

[FFY00]

GH-131770 — here's a relevant issue that went unnoticed in the CI due to GH-131769.

[markshannon]

The related issues all seem to be parser failures in test_compile.
Is that correct?

Maybe we should temporarily reduce the limit when parsing?

[brettcannon]

The related issues all seem to be parser failures in test_compile. Is that correct?

Not anymore. With a checkout from yesterday running ./cross-build/wasm32-wasip1/python.sh -m test:

3 tests failed:
    test_ast test_ttk_textonly test_unparse

test_ast

0:00:00 [1/1] test_ast
Failed to import test module: test.test_ast.test_ast
Traceback (most recent call last):
  File "/Lib/unittest/loader.py", line 426, in _find_test_path
    module = self._get_module_from_name(name)
  File "/Lib/unittest/loader.py", line 367, in _get_module_from_name
    __import__(name)
    ~~~~~~~~~~^^^^^^
  File "/Lib/test/test_ast/test_ast.py", line 26, in <module>
    from test.test_ast.snippets import (
        eval_tests, eval_results, exec_tests, exec_results, single_tests, single_results
    )
MemoryError: Parser stack overflowed - Python source too complex to parse

test_ttk_textonly

0:00:00 [1/1] test_ttk_textonly
test test_ttk_textonly crashed -- Traceback (most recent call last):
  File "/Lib/test/libregrtest/single.py", line 210, in _runtest_env_changed_exc
    _load_run_test(result, runtests)
    ~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^
  File "/Lib/test/libregrtest/single.py", line 155, in _load_run_test
    test_mod = importlib.import_module(module_name)
  File "/Lib/importlib/__init__.py", line 88, in import_module
    return _bootstrap._gcd_import(name[level:], package, level)
           ~~~~~~~~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "<frozen importlib._bootstrap>", line 1398, in _gcd_import
  File "<frozen importlib._bootstrap>", line 1371, in _find_and_load
  File "<frozen importlib._bootstrap>", line 1342, in _find_and_load_unlocked
  File "<frozen importlib._bootstrap>", line 938, in _load_unlocked
  File "<frozen importlib._bootstrap_external>", line 758, in exec_module
  File "<frozen importlib._bootstrap_external>", line 896, in get_code
  File "<frozen importlib._bootstrap_external>", line 826, in source_to_code
  File "<frozen importlib._bootstrap>", line 491, in _call_with_frames_removed
MemoryError: Parser stack overflowed - Python source too complex to parse

test_unparse which only fails in a full test suite run

0:04:54 [446/489/2] test_unparse
test test_unparse failed -- Traceback (most recent call last):
  File "/Lib/test/test_unparse.py", line 136, in check_ast_roundtrip
    ast1 = ast.parse(code1, **kwargs)
  File "/Lib/ast.py", line 46, in parse
    return compile(source, filename, mode, flags,
                   _feature_version=feature_version, optimize=optimize)
MemoryError: Parser stack overflowed - Python source too complex to parse

[brettcannon]

Here is a code snippet taken from test_ttk_textonly that will crash the interpreter upon import:

def test_format_layoutlist(self):
    def sample(indent=0, indent_size=2):
        return ttk._format_layoutlist(
        [('a', {'other': [1, 2, 3], 'children':
            [('b', {'children':
                [('c', {'children':
                    [('d', {'nice': 'opt'})], 'something': (1, 2)
                })]
            })]
        })], indent=indent, indent_size=indent_size)[0]

This results in:

➲ cross-build/wasm32-wasip1/python.sh tester.py
RecursionError: Stack overflow (used 128 kB) while calling a Python object
Normalization failed: type=MemoryError args=<unknown>

Maybe @pablogsal has an idea of how the parser might be using just enough memory on this snippet of code to fail?

[pablogsal]

Maybe @pablogsal has an idea of how the parser might be using just enough memory on this snippet of code to fail?

I don't understand why this is making it fail. Before, we had a hardcoded limit of 4000 levels for wasi and 6000 for non wasi, which was not failing. Maybe we are being a bit conservative? The parser will recurse naturally as it is exploring the grammar space. I assume for this code it may go 300 / 400 levels deep. According to GCC the average stack size of the parser rules is 118 bytes ( using -fstack-usage and inspecting the Parser/parser.su file). So 400 frames would be 47550 bytes. Seems that we are using 3 times that or so here but looks possible since gcc only reports the 'known' size of the stack.

[brettcannon]

I tried increasing the default value using the new stack protections system in #131770 (comment) , but it either continued to raise MemoryError or actually blew out the stack.