Call stack exhaustion (overflow) in parser with a very large generated file

[sunshowers]

Code

Can't provide a minimal example for obvious reasons :)

$ git clone https://github.com/bytecodealliance/wasmtime/
$ cd wasmtime
$ git checkout 87817f38a128caa76eaa6a3c3c8ceac81a329a3e
$ cd cranelift/codegen
$ RUST_MIN_STACK=1048576 cargo +1.80.0 build

On my Linux x86_64 system this deterministically crashes in the rustc parser due to call stack exhaustion (i.e. a call stack overflow). The full output is here. (Note I haven't built a Rust compiler with symbols, because I have enough information to establish the cause without needing symbols.)

The file that's failing to parse is this one. It is an autogenerated file called isle_opt.rs, and is generated by the cranelift-codegen build script.

This also reproduces with rustc 1.82.0-nightly (f8060d282 2024-07-30).

What's the RUST_MIN_STACK doing, you might ask? Well, long story behind this, but I got here by first diagnosing the issue on illumos, which crashed in the same spot with the same crate (illumos stack trace), without requiring RUST_MIN_STACK to be set.

• In fact, on illumos, the issue occurs whether RUST_MIN_STACK is set to 1MiB, 2MiB (default) or 4MiB. This is consistent with the description below.

What's happening is:

• This file in cranelift-codegen is triggering the crash by requiring more than 1MiB of stack space.
  • The rustc parser running against cranelift-codegen needs more than 1MiB of stack space, but less than 2MiB.
• Had this bug occurred on other platforms like Linux, this issue would have been a showstopper. However, it wasn't visible on those platforms because:
  • Threads created by Rust use a 2MiB stack by default.
  • rustc requests a 1MiB stack segment with a 100KiB red zone.
  • On other platforms like Linux, stacker can see that well over 100KiB of stack space is left, and so it does not allocate a new segment.
  • On illumos, this logic doesn't exist. stacker cannot see how much stack was left, and so it unconditionally allocates a new 1MiB segment.
  • This 1MiB stack is simply not enough to parse isle_opt.rs.

With RUST_MIN_STACK used to set a stack size <= 1MiB, we would expect that:

1. rustc calls stacker as before.
2. There are two possibilities: either stacker decides there is enough stack space and doesn't create a new segment, or it decides there isn't enough and does create a new 1MiB segment.
3. In either case, 1MiB is simply not enough to parse cranelift-codegen, and the program crashes.

To the best of my understanding, this is a bug in rustc's use of stacker. The fact that 1MiB just isn't enough to parse that file was being masked by the default stack size of 2MiB.

I think the fix is that rustc should be calling stacker more often in its recursive sections -- if it did, then stacker would allocate a new segment as soon as less than 100KiB of stack space was available.

(A secondary issue is that stacker should be able to detect stack sizes on illumos -- I'll try sending a PR for that separately.)

Meta

Reproes with both:

rustc --version --verbose:

rustc 1.80.0 (051478957 2024-07-21)
binary: rustc
commit-hash: 051478957371ee0084a7c0913941d2a8c4757bb9
commit-date: 2024-07-21
host: x86_64-unknown-linux-gnu
release: 1.80.0
LLVM version: 18.1.7

and

rustc 1.82.0-nightly (f8060d282 2024-07-30)
binary: rustc
commit-hash: f8060d282d42770fadd73905e3eefb85660d3278
commit-date: 2024-07-30
host: x86_64-unknown-linux-gnu
release: 1.82.0-nightly
LLVM version: 18.1.7

Error output

https://gist.github.com/sunshowers/3ac000e5a5022acd3f07886a16a39520

[sunshowers]

Note that cranelift-codegen is part of the Rust toolchain -- I encountered this bug while trying to build Rust on illumos.

As a practical matter, this currently makes it impossible for developers on illumos to make a Rust build natively, or even run commands like ./x.py check. Currently, the only way to build rustc on illumos is to cross-compile from another OS like Linux.

(To unblock myself, I built rustc targeting illumos from Linux, with this patch applied. This worked.)

[sunshowers]

(A secondary issue is that stacker should be able to detect stack sizes on illumos -- I'll try sending a PR for that separately.)

That PR is https://github.com/rust-lang/stacker/pull/88.

[lovasoa]

The file doesn't need to be very big to crash the compiler. Here is the smallest file that crashes rustc on my computer; it's 12Kb bad.zip

$ (echo 'fn main(){' && printf %12023s |tr " " "(") | rustc /dev/stdin
error: rustc interrupted by SIGSEGV, printing backtrace

/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-198d7b2c3cb4a0cb.so(+0x303b5c6)[0x7f607003b5c6]
/lib64/libc.so.6(+0x40d00)[0x7f606ce4fd00]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/rustc(+0x4b571)[0x55935ed2f571]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/rustc(+0x4de44)[0x55935ed31e44]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/rustc(+0x4c2c3)[0x55935ed302c3]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/rustc(+0x4c5b2)[0x55935ed305b2]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/rustc(+0x5719e)[0x55935ed3b19e]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/rustc(+0x56087)[0x55935ed3a087]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/rustc(+0x24c52)[0x55935ed08c52]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/rustc(+0x5398a)[0x55935ed3798a]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/rustc(+0x5408c)[0x55935ed3808c]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/rustc(+0x27e4e)[0x55935ed0be4e]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/rustc(+0x1ed36)[0x55935ed02d36]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-198d7b2c3cb4a0cb.so(+0x44003b4)[0x7f60714003b4]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-198d7b2c3cb4a0cb.so(+0x520102d)[0x7f607220102d]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-198d7b2c3cb4a0cb.so(+0x5200f3c)[0x7f6072200f3c]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-198d7b2c3cb4a0cb.so(+0x440cfde)[0x7f607140cfde]

### cycle encountered after 17 frames with period 18
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-198d7b2c3cb4a0cb.so(+0x440cc92)[0x7f607140cc92]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-198d7b2c3cb4a0cb.so(+0x440cc92)[0x7f607140cc92]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-198d7b2c3cb4a0cb.so(+0x440cc92)[0x7f607140cc92]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-198d7b2c3cb4a0cb.so(+0x440cc92)[0x7f607140cc92]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-198d7b2c3cb4a0cb.so(+0x440cc92)[0x7f607140cc92]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-198d7b2c3cb4a0cb.so(+0x440cc92)[0x7f607140cc92]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-198d7b2c3cb4a0cb.so(+0x440cc92)[0x7f607140cc92]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-198d7b2c3cb4a0cb.so(+0x440cc92)[0x7f607140cc92]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-198d7b2c3cb4a0cb.so(+0x440cc92)[0x7f607140cc92]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-198d7b2c3cb4a0cb.so(+0x440cc92)[0x7f607140cc92]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-198d7b2c3cb4a0cb.so(+0x440cc92)[0x7f607140cc92]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-198d7b2c3cb4a0cb.so(+0x440cc92)[0x7f607140cc92]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-198d7b2c3cb4a0cb.so(+0x440cc92)[0x7f607140cc92]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-198d7b2c3cb4a0cb.so(+0x440cc92)[0x7f607140cc92]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-198d7b2c3cb4a0cb.so(+0x440cc92)[0x7f607140cc92]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-198d7b2c3cb4a0cb.so(+0x440cc92)[0x7f607140cc92]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-198d7b2c3cb4a0cb.so(+0x440cc92)[0x7f607140cc92]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-198d7b2c3cb4a0cb.so(+0x440cc92)[0x7f607140cc92]
### recursed 13 times

/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-198d7b2c3cb4a0cb.so(+0x440cc92)[0x7f607140cc92]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-198d7b2c3cb4a0cb.so(+0x440cc92)[0x7f607140cc92]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-198d7b2c3cb4a0cb.so(+0x440cc92)[0x7f607140cc92]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-198d7b2c3cb4a0cb.so(+0x440cc92)[0x7f607140cc92]
/home/ophir/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-198d7b2c3cb4a0cb.so(+0x440cc92)[0x7f607140cc92]

note: rustc unexpectedly overflowed its stack! this is a bug
note: maximum backtrace depth reached, frames may have been lost
note: we would appreciate a report at https://github.com/rust-lang/rust
help: you can increase rustc's stack size by setting RUST_MIN_STACK=16777216
note: backtrace dumped due to SIGSEGV! resuming signal
Segmentation fault (core dumped)

In a similar situation, Clang generates a nice message pointing to the error in the input file:

$ (echo 'int main(){' && printf %12023s |tr " " "(") | clang -x c -
<stdin>:2:257: fatal error: bracket nesting level exceeded maximum of 256
<stdin>:2:257: note: use -fbracket-depth=N to increase maximum nesting level
1 error generated.