Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Thread 'rustc' has overflowed its stack on dumb program #75577

Open
AuroransSolis opened this issue Aug 16, 2020 · 12 comments
Open

Thread 'rustc' has overflowed its stack on dumb program #75577

AuroransSolis opened this issue Aug 16, 2020 · 12 comments
Labels
C-bug Category: This is a bug. E-needs-test Call for participation: An issue has been fixed and does not reproduce, but no test has been added. I-ICE Issue: The compiler panicked, giving an Internal Compilation Error (ICE) ❄️ S-has-mcve Status: A Minimal Complete and Verifiable Example has been found for this issue T-compiler Relevant to the compiler team, which will review and decide on the PR/issue.

Comments

@AuroransSolis
Copy link

AuroransSolis commented Aug 16, 2020 •
edited by rustbot
Loading

It's me again! Back this time with something that throws a spanner in the works for rustc without it taking multiple hundred gigabytes of memory and several days to compile. It's an Advent of Code challenge once more - and this time I tried to solve everything at compile time with macro abuse and types. Here's a small example using the setup I made in the playground (input is on line 181), and here's the large example that causes the error (as a gist since it times out in the playground). I have just a little bit of a hunch that #![recursion_limit="50000"] basically being required has something to do with the error:

auro@auro-desktop ~/projects/aoc_2018_d5_ct $ time cargo run
   Compiling aoc_2018_d5_ct v0.1.0 (/home/auro/projects/aoc_2018_d5_ct)

thread 'rustc' has overflowed its stack
fatal runtime error: stack overflow
error: could not compile `aoc_2018_d5_ct`.

Caused by:
  process didn't exit successfully: `rustc --crate-name aoc_2018_d5_ct --edition=2018 src/main.rs --error-format=json --json=diagnostic-rendered-ansi --crate-type bin --emit=dep-info,link -Cembed-bitcode=no -C debuginfo=2 -C metadata=8d4922b265418474 -C extra-filename=-8d4922b265418474 --out-dir /home/auro/projects/aoc_2018_d5_ct/target/debug/deps -C incremental=/home/auro/projects/aoc_2018_d5_ct/target/debug/incremental -L dependency=/home/auro/projects/aoc_2018_d5_ct/target/debug/deps --extern paste=/home/auro/projects/aoc_2018_d5_ct/target/debug/deps/libpaste-56ec6c5ce13200bb.so` (signal: 6, SIGABRT: process abort signal)

I feel like an apology is in order for anyone who tries figuring out what's going wrong here, so: I'm deeply, deeply, sorry.
@AuroransSolis
Copy link
Author

Oh yeah, also, here's a backtrace of rustc from when I ran it in gdb. https://gist.github.com/AuroransSolis/9f3b7bb1c1a1cdbdc6f9469aa7d0f9df

@jonas-schievink jonas-schievink added C-bug Category: This is a bug. I-ICE Issue: The compiler panicked, giving an Internal Compilation Error (ICE) ❄️ T-compiler Relevant to the compiler team, which will review and decide on the PR/issue. labels Aug 16, 2020
@nagisa nagisa added E-easy Call for participation: Easy difficulty. Experience needed to fix: Not much. Good first issue. E-mentor Call for participation: This issue has a mentor. Use #t-compiler/help on Zulip for discussion. labels Aug 23, 2020
@nagisa
Copy link
Member

nagisa commented Aug 23, 2020 •
edited
Loading

This is probably not too hard to fix, so marking it as a E-easy for a contributor to pick up. A well positioned ensure_sufficient_stack should be enough. All that’s left is to find where exactly to put it!

Instructions

The stacktrace posted above is incomplete. So the first thing you will want to do is to compile the provided reproducer program under a debugger and extract the couple dozen of the stack frames at the bottom of the stack. This should inform you as to where exactly in the compiler the recursion is entered. Once you have that information available, you will have to find the corresponding code in the codebase and add a call to ensure_sufficient_stack to break up the recursion.

Spoiler: bottom frames of stack 
#43960 0x00007f377c420ee9 in <alloc::vec::Vec<T> as core::clone::Clone>::clone () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43961 0x00007f377c3f8c1f in <rustc_ast::ast::Ty as core::clone::Clone>::clone () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43962 0x00007f377c3edfa5 in <core::iter::adapters::Cloned<I> as core::iter::traits::iterator::Iterator>::fold ()
   from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43963 0x00007f377c41fa9b in <alloc::vec::Vec<T> as core::clone::Clone>::clone () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43964 0x00007f377c4008d9 in <rustc_ast::ptr::P<T> as core::clone::Clone>::clone () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43965 0x00007f377c420ee9 in <alloc::vec::Vec<T> as core::clone::Clone>::clone () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43966 0x00007f377c3f8c1f in <rustc_ast::ast::Ty as core::clone::Clone>::clone () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43967 0x00007f377c3edfa5 in <core::iter::adapters::Cloned<I> as core::iter::traits::iterator::Iterator>::fold ()
   from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43968 0x00007f377c41fa9b in <alloc::vec::Vec<T> as core::clone::Clone>::clone () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43969 0x00007f377c4008d9 in <rustc_ast::ptr::P<T> as core::clone::Clone>::clone () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43970 0x00007f377c420ee9 in <alloc::vec::Vec<T> as core::clone::Clone>::clone () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43971 0x00007f377c3f8c1f in <rustc_ast::ast::Ty as core::clone::Clone>::clone () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43972 0x00007f377c3d0881 in rustc_parse::parser::ty::<impl rustc_parse::parser::Parser>::parse_ty_common () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43973 0x00007f377c3cbc82 in rustc_parse::parser::path::<impl rustc_parse::parser::Parser>::parse_generic_arg ()
   from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43974 0x00007f377c3cae9b in rustc_parse::parser::path::<impl rustc_parse::parser::Parser>::parse_angle_args ()
   from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43975 0x00007f377c3c87bd in rustc_parse::parser::path::<impl rustc_parse::parser::Parser>::parse_path_segment ()
   from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43976 0x00007f377c3c7f01 in rustc_parse::parser::path::<impl rustc_parse::parser::Parser>::parse_path_segments ()
   from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43977 0x00007f377c3c7d63 in rustc_parse::parser::path::<impl rustc_parse::parser::Parser>::parse_path () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43978 0x00007f377c3d3b28 in rustc_parse::parser::ty::<impl rustc_parse::parser::Parser>::parse_ty_common () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43979 0x00007f377c3cbc82 in rustc_parse::parser::path::<impl rustc_parse::parser::Parser>::parse_generic_arg ()
   from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43980 0x00007f377c3cae9b in rustc_parse::parser::path::<impl rustc_parse::parser::Parser>::parse_angle_args ()
   from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43981 0x00007f377c3c87bd in rustc_parse::parser::path::<impl rustc_parse::parser::Parser>::parse_path_segment ()
   from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43982 0x00007f377c3c7f01 in rustc_parse::parser::path::<impl rustc_parse::parser::Parser>::parse_path_segments ()
   from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43983 0x00007f377c3c7d63 in rustc_parse::parser::path::<impl rustc_parse::parser::Parser>::parse_path () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43984 0x00007f377c3d3b28 in rustc_parse::parser::ty::<impl rustc_parse::parser::Parser>::parse_ty_common () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43985 0x00007f377c3bc351 in rustc_parse::parser::nonterminal::<impl rustc_parse::parser::Parser>::parse_nonterminal ()
   from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43986 0x00007f377c2f335c in rustc_expand::mbe::macro_parser::parse_tt () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43987 0x00007f377c2f6726 in <rustc_expand::mbe::macro_rules::MacroRulesMacroExpander as rustc_expand::base::TTMacroExpander>::expand ()
   from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43988 0x00007f377c30b6da in rustc_expand::expand::MacroExpander::fully_expand_fragment () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43989 0x00007f377c30a860 in rustc_expand::expand::MacroExpander::expand_crate () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43990 0x00007f377a5de07c in rustc_session::utils::<impl rustc_session::session::Session>::time () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43991 0x00007f377a62da4e in rustc_interface::passes::configure_and_expand_inner () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43992 0x00007f377a5f6469 in rustc_interface::passes::configure_and_expand::{{closure}} () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43993 0x00007f377a5eb97f in rustc_data_structures::box_region::PinnedGenerator<I,A,R>::new () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43994 0x00007f377a62ca45 in rustc_interface::passes::configure_and_expand () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43995 0x00007f377a677b78 in rustc_interface::queries::Queries::expansion () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43996 0x00007f377a32ac07 in rustc_interface::queries::<impl rustc_interface::interface::Compiler>::enter () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43997 0x00007f377a2c0da7 in rustc_span::with_source_map () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43998 0x00007f377a32c893 in rustc_interface::interface::create_compiler_and_run () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43999 0x00007f377a30b14a in scoped_tls::ScopedKey<T>::set () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#44000 0x00007f377a31f633 in std::sys_common::backtrace::__rust_begin_short_backtrace () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#44001 0x00007f377a2ab3ae in core::ops::function::FnOnce::call_once{{vtable-shim}} () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#44002 0x00007f3779a5b0da in <alloc::boxed::Box<F> as core::ops::function::FnOnce<A>>::call_once () at /rustc/663d2f5cd3163f17eddb74ee1e028d542255f21a/library/alloc/src/boxed.rs:1042
#44003 <alloc::boxed::Box<F> as core::ops::function::FnOnce<A>>::call_once () at /rustc/663d2f5cd3163f17eddb74ee1e028d542255f21a/library/alloc/src/boxed.rs:1042
#44004 std::sys::unix::thread::Thread::new::thread_start () at library/std/src/sys/unix/thread.rs:87
#44005 0x00007f3779999ead in start_thread () from /nix/store/aqq6367snc1zh3fs1pc4j4zm5h80vkkz-glibc-2.31/lib/libpthread.so.0
#44006 0x00007f37798b9d2f in clone () from /nix/store/aqq6367snc1zh3fs1pc4j4zm5h80vkkz-glibc-2.31/lib/libc.so.6
Spoiler: where in the code change needs to be made

Looking at the stack trace you will see that the recursion begins with a call to <rustc_ast::ast::Ty as core::clone::Clone>::clone(). From the source code for ast::Ty it can be seen that Clone is derived and that Ty contains a TyKind. TyKind is then recursive and also derives a Clone, so for deeply nested types this will indeed trigger a stack overflow.

Manually implementing Clone to introuce the necessary break-up is then probably the most appropriate quick solution.

I encourage you to ping me here or on Zulip if you need additional help.

@chansuke
Copy link
Contributor

Hi. I'd like to work on this issue

@chansuke
Copy link
Contributor

@rustbot claim

@hbina
Copy link
Contributor

hbina commented Sep 20, 2020

I am literally unable to test if my changes fix this problem because 13.6 GB RAM and 2GB swap is not enough to test it....But if I understood this correctly, the solution is to simply implement Clone and execute the clone as a lambda inside ensure_sufficient_stack.

@hbina hbina mentioned this issue Sep 20, 2020
Merged
@tesuji
Copy link
Contributor

tesuji commented Sep 21, 2020 •
edited
Loading

@hbina Please remove the close/fix keyword from #76985 body until we have tests for this issue.

@rustbot rustbot added E-needs-mcve Call for participation: This issue has a repro, but needs a Minimal Complete and Verifiable Example E-needs-test Call for participation: An issue has been fixed and does not reproduce, but no test has been added. labels Sep 21, 2020
bors added a commit to rust-lang-ci/rust that referenced this issue Oct 7, 2020
@bors
Auto merge of rust-lang#76985 - hbina:clone_check, r=estebank
91a79fb 
Prevent stack overflow in deeply nested types.

Related issue rust-lang#75577 (?)

Unfortunately, I am unable to test whether this actually solves the problem because apparently, 12GB RAM + 2GB swap is not enough to compile the (admittedly toy) source file.
@estebank
Copy link
Contributor

@AuroransSolis could you test this again in your environment with the latest nightly?

@AuroransSolis
Copy link
Author

I tried briefly and it quickly claimed 25GB of memory (10GB of RAM and 15GB of swap), causing my displays to freeze and forcing me to use a teletype to kill it. I'll try again overnight tonight and see what happens.

@AuroransSolis
Copy link
Author

AuroransSolis commented Oct 12, 2020 •
edited
Loading

Attempted again. Turns out my 16GB of memory and 256GB of swap wasn't enough. It ate up all of it and the kernel sent it a SIGKILL. I suppose this just further confirms my categorizing this as a dumb program.

Update: friend of mine will be loaning me a 2TB drive to use as a swap disk. Once I get that I'll try again to make sure there's no further issues.

@AuroransSolis
Copy link
Author

That's a possibility. I'll try again with about half the input later this evening and update here after doing so.

@BlackHoleFox
Copy link
Contributor

I attempted to reproduce this on my Windows system but it looks like Windows won't give it enough page space to continue:

cargo +nightly run
   Compiling paste v1.0.3
   Compiling macro_testing v0.1.0 (C:\Users\user\Downloads\macro_testing)
thread 'rustc' panicked at 'unable to allocate fiber: The paging file is too small for this operation to complete. (os error 1455)', C:\Users\runneradmin\.cargo\registry\src\git.luolix.top-1ecc6299db9ec823\stacker-0.1.12\src\lib.rs:352:21
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

error: internal compiler error: unexpected panic

note: the compiler unexpectedly panicked. this is a bug.

note: we would appreciate a bug report: https://github.com/rust-lang/rust/issues/new?labels=C-bug%2C+I-ICE%2C+T-compiler&template=ice.md

note: rustc 1.50.0-nightly (fe982319a 2020-11-19) running on x86_64-pc-windows-msvc

note: compiler flags: -C embed-bitcode=no -C debuginfo=2 -C incremental --crate-type bin

note: some of the compiler flags provided by cargo are hidden

query stack during panic:
end of query stack

thread 'rustc' has overflowed its stack
error: could not compile `macro_testing`

Caused by:
  process didn't exit successfully: `rustc --crate-name macro_testing --edition=2018 src\main.rs --error-format=json --json=diagnostic-rendered-ansi --crate-type bin --emit=dep-info,link -C embed-bitcode=no -C debuginfo=2 -C metadata=4f528d08987c48f9 --out-dir C:\Users\user\Downloads\macro_testing\target\debug\deps -C incremental=C:\Users\user\Downloads\macro_testing\target\debug\incremental -L dependency=C:\Users\user\Downloads\macro_testing\target\debug\deps --extern paste=C:\Users\user\Downloads\macro_testing\target\debug\deps\paste-4388445a40bd90ce.dll` (exit code: 0xc00000fd, STATUS_STACK_OVERFLOW)

This ended up taking ~130GB of swap space and 64GB of RAM before ICEing.

@JohnTitor JohnTitor removed the E-mentor Call for participation: This issue has a mentor. Use #t-compiler/help on Zulip for discussion. label Apr 4, 2021
@LegionMammal978
Copy link
Contributor

LegionMammal978 commented Jul 29, 2021 •
edited
Loading

@nagisa, I did some testing on this and have come up with a minimal example. As written, it produces the same stack trace as the original program using a debug build of nightly-2020-08-15. However, it only requires ~16 GB of RAM on a modern nightly build and builds for ~30 s on my machine before overflowing the stack.

#![recursion_limit = "1000000000"]

pub struct Test<T>(T);

macro_rules! big_type {
    (0, $ty:ty, $t1:tt) => { Test<$ty> };
    (0, $ty:ty, $t1:tt, $($t:tt),+) => { big_type!(0, Test<$ty>, $($t),+) };
    (1, $($t:tt),+) => { big_type!(0, (), $($t, $t),+) };
    (2, $($t:tt),+) => { big_type!(1, $($t, $t),+) };
    (3, $($t:tt),+) => { big_type!(2, $($t, $t),+) };
    (4, $($t:tt),+) => { big_type!(3, $($t, $t),+) };
    (5, $($t:tt),+) => { big_type!(4, $($t, $t),+) };
    (6, $($t:tt),+) => { big_type!(5, $($t, $t),+) };
    (7, $($t:tt),+) => { big_type!(6, $($t, $t),+) };
    (8, $($t:tt),+) => { big_type!(7, $($t, $t),+) };
    (9, $($t:tt),+) => { big_type!(8, $($t, $t),+) };
    (10, $($t:tt),+) => { big_type!(9, $($t, $t),+) };
    (11, $($t:tt),+) => { big_type!(10, $($t, $t),+) };
    (12, $($t:tt),+) => { big_type!(11, $($t, $t),+) };
    (13, $($t:tt),+) => { big_type!(12, $($t, $t),+) };
    (14, $($t:tt),+) => { big_type!(13, $($t, $t),+) };
    (15, $($t:tt),+) => { big_type!(14, $($t, $t),+) };
    (16, $($t:tt),+) => { big_type!(15, $($t, $t),+) };
}

pub fn test(_: big_type!(13, _)) {}

As you suspected, the original issue was in <Ty as Clone>::clone(), which has since been fixed by #76985. In the ad-hoc notation I've been using to debug this issue, the recursive loop looked like this:

[compiler/rustc_ast/src/ast.rs] <Ty as Clone>::clone()
[compiler/rustc_ast/src/ast.rs] <TyKind as Clone>::clone()
[compiler/rustc_ast/src/ast.rs] <Path as Clone>::clone()
[library/alloc/src/vec.rs] <Vec<PathSegment> as Clone>::clone()
[...]
[compiler/rustc_ast/src/ast.rs] <PathSegment as Clone>::clone()
[library/core/src/option.rs] <Option<P<GenericArgs>> as Clone>::clone()
[compiler/rustc_ast/src/ptr.rs] <P<GenericArgs> as Clone>::clone()
[compiler/rustc_ast/src/ast.rs] <GenericArgs as Clone>::clone()
[compiler/rustc_ast/src/ast.rs] <AngleBracketedArgs as Clone>::clone()
[library/alloc/src/vec.rs] <Vec<AngleBracketedArg> as Clone>::clone()
[...]
[compiler/rustc_ast/src/ast.rs] <AngleBracketedArg as Clone>::clone()
[compiler/rustc_ast/src/ast.rs] <GenericArg as Clone>::clone()
[compiler/rustc_ast/src/ptr.rs] <P<Ty> as Clone>::clone()
[compiler/rustc_ast/src/ast.rs] <Ty as Clone>::clone()

However, if we want the compiler to support deeply nested types such as these, there are several other recursive loops which need to be broken up with ensure_sufficient_stack(). To begin, I tested the remainder of these loops with a more direct macro recursion:

#![recursion_limit = "1000000000"]

pub struct Test<T>(T);

macro_rules! big_type {
    (0, $t:ty) => { Test<$t> };
    (1, $t:ty) => { big_type!(0, big_type!(0, $t)) };
    (2, $t:ty) => { big_type!(1, big_type!(1, $t)) };
    (3, $t:ty) => { big_type!(2, big_type!(2, $t)) };
    (4, $t:ty) => { big_type!(3, big_type!(3, $t)) };
    (5, $t:ty) => { big_type!(4, big_type!(4, $t)) };
    (6, $t:ty) => { big_type!(5, big_type!(5, $t)) };
    (7, $t:ty) => { big_type!(6, big_type!(6, $t)) };
    (8, $t:ty) => { big_type!(7, big_type!(7, $t)) };
    (9, $t:ty) => { big_type!(8, big_type!(8, $t)) };
    (10, $t:ty) => { big_type!(9, big_type!(9, $t)) };
    (11, $t:ty) => { big_type!(10, big_type!(10, $t)) };
    (12, $t:ty) => { big_type!(11, big_type!(11, $t)) };
    (13, $t:ty) => { big_type!(12, big_type!(12, $t)) };
    (14, $t:ty) => { big_type!(13, big_type!(13, $t)) };
    (15, $t:ty) => { big_type!(14, big_type!(14, $t)) };
    (16, $t:ty) => { big_type!(15, big_type!(15, $t)) };
}

pub fn test(_: big_type!(12, ())) {}

For whatever reason, this didn't trigger the original <Ty as Clone>::clone() crash. However, it did cause rustc to crash on this loop:

[compiler/rustc_ast_lowering/src/lib.rs] LoweringContext::lower_ty_direct()
[compiler/rustc_ast_lowering/src/lib.rs] LoweringContext::lower_path_ty()
[compiler/rustc_ast_lowering/src/path.rs] LoweringContext::lower_qpath()
[...]
[compiler/rustc_ast_lowering/src/path.rs] LoweringContext::lower_qpath::{closure@37}()
[compiler/rustc_ast_lowering/src/path.rs] LoweringContext::lower_path_segment()
[compiler/rustc_ast_lowering/src/path.rs] LoweringContext::lower_angle_bracketed_parameter_data()
[...]
[compiler/rustc_ast_lowering/src/path.rs] LoweringContext::lower_angle_bracketed_parameter_data::{closure@381}()
[compiler/rustc_ast_lowering/src/lib.rs] LoweringContext::lower_generic_arg()
[compiler/rustc_ast_lowering/src/lib.rs] LoweringContext::lower_ty_direct()

When I added ensure_sufficient_stack() to LoweringContext::lower_ty_direct(), rustc crashed on this loop:

[compiler/rustc_resolve/src/late/lifetimes.rs] <LifetimeContext as Visitor>::visit_ty()
[compiler/rustc_resolve/src/late/lifetimes.rs] <LifetimeContext as Visitor>::visit_path()
[compiler/rustc_resolve/src/late/lifetimes.rs] LifetimeContext::visit_segment_args()
[compiler/rustc_resolve/src/late/lifetimes.rs] LifetimeContext::with<LifetimeContext::visit_segment_args::{closure@2544}>()
[compiler/rustc_resolve/src/late/lifetimes.rs] LifetimeContext::visit_segment_args::{closure@2544}()
[compiler/rustc_resolve/src/late/lifetimes.rs] <LifetimeContext as Visitor>::visit_ty()

When I added ensure_sufficient_stack() to <LifetimeContext as Visitor>::visit_ty(), rustc crashed on this loop:

[compiler/rustc_typeck/src/astconv/mod.rs] <dyn AstConv>::ast_ty_to_ty()
[compiler/rustc_typeck/src/astconv/mod.rs] <dyn AstConv>::ast_ty_to_ty_inner()
[compiler/rustc_typeck/src/astconv/mod.rs] <dyn AstConv>::res_to_ty()
[compiler/rustc_typeck/src/astconv/mod.rs] <dyn AstConv>::ast_path_to_ty()
[compiler/rustc_typeck/src/astconv/mod.rs] <dyn AstConv>::ast_path_substs_for_ty()
[compiler/rustc_typeck/src/astconv/mod.rs] <dyn AstConv>::create_substs_for_ast_path()
[compiler/rustc_typeck/src/astconv/generics.rs] <dyn AstConv>::create_substs_for_generic_args()
[compiler/rustc_typeck/src/astconv/mod.rs] <<dyn AstConv>::create_substs_for_ast_path::SubstsForAstPathCtxt as CreateSubstsForGenericArgsCtxt>::provided_kind()
[compiler/rustc_typeck/src/astconv/mod.rs] <dyn AstConv>::ast_ty_to_ty()

When I added ensure_sufficient_stack() to <dyn AstConv>::ast_ty_to_ty_inner(), rustc crashed on this loop:

[compiler/rustc_codegen_llvm/src/debuginfo/metadata.rs] metadata::type_metadata()
[compiler/rustc_codegen_llvm/src/debuginfo/metadata.rs] RecursiveTypeDescription::finalize()
[compiler/rustc_codegen_llvm/src/debuginfo/metadata.rs] MemberDescriptionFactory::create_member_descriptions()
[compiler/rustc_codegen_llvm/src/debuginfo/metadata.rs] StructMemberDescriptionFactory::create_member_descriptions()
[...]
[compiler/rustc_codegen_llvm/src/debuginfo/metadata.rs] StructMemberDescriptionFactory::create_member_descriptions::{closure@1223}()
[compiler/rustc_codegen_llvm/src/debuginfo/metadata.rs] metadata::type_metadata()

When I added ensure_sufficient_stack() to metadata::type_metadata(), rustc crashed on this loop:

[compiler/rustc_query_system/src/dep_graph/graph.rs] DepGraph::<DepKind>::try_mark_previous_green::<QueryCtxt>()
[compiler/rustc_query_system/src/dep_graph/graph.rs] DepGraph::<DepKind>::try_mark_parent_green::<QueryCtxt>()
[compiler/rustc_query_system/src/dep_graph/graph.rs] DepGraph::<DepKind>::try_mark_previous_green::<QueryCtxt>()

When I added ensure_sufficient_stack() to DepGraph::try_mark_parent_green(), rustc crashed on this loop:

[compiler/rustc_codegen_ssa/src/debuginfo/type_names.rs] type_names::push_debuginfo_type_name()
[compiler/rustc_codegen_ssa/src/debuginfo/type_names.rs] type_names::push_generic_params_internal()
[compiler/rustc_codegen_ssa/src/debuginfo/type_names.rs] type_names::push_debuginfo_type_name()

When I added ensure_sufficient_stack() to type_names::push_debuginfo_type_name(), rustc crashed on this loop:

[compiler/rustc_middle/src/ty/print/mod.rs] <Ty as Print<FmtPrinter<&mut Formatter>>>::print()
[compiler/rustc_middle/src/ty/print/pretty.rs] <FmtPrinter<&mut Formatter> as PrettyPrinter>::pretty_print_type()
[compiler/rustc_middle/src/ty/print/pretty.rs] <FmtPrinter<&mut Formatter> as Printer>::print_def_path()
[compiler/rustc_middle/src/ty/print/mod.rs] <FmtPrinter<&mut Formatter> as Printer>::default_print_def_path()
[compiler/rustc_middle/src/ty/print/pretty.rs] <FmtPrinter<&mut Formatter> as Printer>::path_generic_args()
[compiler/rustc_middle/src/ty/print/pretty.rs] <FmtPrinter<&mut Formatter> as PrettyPrinter>::generic_delimiters()
[compiler/rustc_middle/src/ty/print/pretty.rs] <FmtPrinter<&mut Formatter> as Printer>::path_generic_args::{closure@1568}()
[compiler/rustc_middle/src/ty/print/pretty.rs] <FmtPrinter<&mut Formatter> as PrettyPrinter>::path_generic_args::{closure@1568}()
[compiler/rustc_middle/src/ty/print/pretty.rs] <FmtPrinter<&mut Formatter> as PrettyPrinter>::comma_sep<FmtPrinter<&mut Formatter>, GenericArg, Filter<Cloned<Iter<GenericArg>>, <FmtPrinter<&mut Formatter> as Printer>::path_generic_args::{closure@1568}>>()
[compiler/rustc_middle/src/ty/print/pretty.rs] <GenericArgs as Print<FmtPrinter<&mut Formatter>>>::print()
[compiler/rustc_middle/src/ty/print/mod.rs] <Ty as Print<FmtPrinter<&mut Formatter>>>::print()

When I added ensure_sufficient_stack() to PrettyPrinter::pretty_print_type(), rustc crashed on this loop:

[compiler/rustc_codegen_llvm/src/type_of.rs] <TyAndLayout as LayoutLlvmExt>::llvm_type()
[compiler/rustc_codegen_llvm/src/type_of.rs] type_of::struct_llfields()
[compiler/rustc_codegen_llvm/src/type_of.rs] <TyAndLayout as LayoutLlvmExt>::llvm_type()

When I added ensure_sufficient_stack() to <TyAndLayout as LayoutLlvmExt>::llvm_type(), rustc crashed on this loop in LLVM:

[src/llvm-project/llvm/lib/IR/Verifier.cpp] Verifier::visitMDNode()
[src/llvm-project/llvm/lib/IR/Verifier.cpp] Verifier::visitMDNode()

This loop would be tricky to fix; as a quick hack, I re-exported the stacker crate as rustc_data_structures::stack::stacker and added stacker::grow(16 * 1024 * 1024, ...) around the call to llvm::LLVMRustWriteOutputFile() in rustc_codegen_llvm::back::write::write_output_file(). When I did that, rustc was able to successfully build the library.

I also tested some variations on the second program. Most of them hit the same recursive loops as the original, but two of them revealed some new problematic loops. The first was this one:

#![recursion_limit = "1000000000"]

pub trait Trait { type Type; }
impl<T> Trait for T { type Type = Self; }

macro_rules! big_type {
    (0, $t:ty) => { <$t as Trait>::Type };
    (1, $t:ty) => { big_type!(0, big_type!(0, $t)) };
    (2, $t:ty) => { big_type!(1, big_type!(1, $t)) };
    (3, $t:ty) => { big_type!(2, big_type!(2, $t)) };
    (4, $t:ty) => { big_type!(3, big_type!(3, $t)) };
    (5, $t:ty) => { big_type!(4, big_type!(4, $t)) };
    (6, $t:ty) => { big_type!(5, big_type!(5, $t)) };
    (7, $t:ty) => { big_type!(6, big_type!(6, $t)) };
    (8, $t:ty) => { big_type!(7, big_type!(7, $t)) };
    (9, $t:ty) => { big_type!(8, big_type!(8, $t)) };
    (10, $t:ty) => { big_type!(9, big_type!(9, $t)) };
    (11, $t:ty) => { big_type!(10, big_type!(10, $t)) };
    (12, $t:ty) => { big_type!(11, big_type!(11, $t)) };
    (13, $t:ty) => { big_type!(12, big_type!(12, $t)) };
    (14, $t:ty) => { big_type!(13, big_type!(13, $t)) };
    (15, $t:ty) => { big_type!(14, big_type!(14, $t)) };
    (16, $t:ty) => { big_type!(15, big_type!(15, $t)) };
}

pub fn test(_: big_type!(13, ())) {}

When I attempted to compile it with the fixes above, rustc crashed on this loop:

[compiler/rustc_trait_selection/src/traits/project.rs] <AssocTypeNormalizer as TypeFolder>::fold_ty()
[compiler/rustc_middle/src/ty/structural_impls.rs] <Ty as TypeFoldable>::super_fold_with::<AssocTypeNormalizer>()
[compiler/rustc_middle/src/ty/fold.rs] <ProjectionTy as TypeFoldable>::fold_with<AssocTypeNormalizer>()
[compiler/rustc_middle/src/ty/sty.rs] <ProjectionTy as TypeFoldable>::super_fold_with<AssocTypeNormalizer>()
[compiler/rustc_middle/src/ty/fold.rs] <SubstsRef as TypeFoldable>::fold_with<AssocTypeNormalizer>()
[compiler/rustc_middle/src/ty/subst.rs] <SubstsRef as TypeFoldable>::super_fold_with<AssocTypeNormalizer>()
[compiler/rustc_middle/src/ty/fold.rs] <GenericArg as TypeFoldable>::fold_with<AssocTypeNormalizer>()
[compiler/rustc_middle/src/ty/subst.rs] <GenericArg as TypeFoldable>::super_fold_with<AssocTypeNormalizer>()
[compiler/rustc_middle/src/ty/structural_impls.rs] <Ty as TypeFoldable>::fold_with::<AssocTypeNormalizer>()
[compiler/rustc_trait_selection/src/traits/project.rs] <AssocTypeNormalizer as TypeFolder>::fold_ty()

This was fixed when I added ensure_sufficient_stack() to <AssocTypeNormalizer as TypeFolder>::fold_ty().

After that, I tried a variation with deeply nested expressions, which was the second variation that yielded new recursive loops:

#![recursion_limit = "1000000000"]

macro_rules! big_expr {
    (0, $e:expr) => { ($e) };
    (1, $e:expr) => { big_expr!(0, big_expr!(0, $e)) };
    (2, $e:expr) => { big_expr!(1, big_expr!(1, $e)) };
    (3, $e:expr) => { big_expr!(2, big_expr!(2, $e)) };
    (4, $e:expr) => { big_expr!(3, big_expr!(3, $e)) };
    (5, $e:expr) => { big_expr!(4, big_expr!(4, $e)) };
    (6, $e:expr) => { big_expr!(5, big_expr!(5, $e)) };
    (7, $e:expr) => { big_expr!(6, big_expr!(6, $e)) };
    (8, $e:expr) => { big_expr!(7, big_expr!(7, $e)) };
    (9, $e:expr) => { big_expr!(8, big_expr!(8, $e)) };
    (10, $e:expr) => { big_expr!(9, big_expr!(9, $e)) };
    (11, $e:expr) => { big_expr!(10, big_expr!(10, $e)) };
    (12, $e:expr) => { big_expr!(11, big_expr!(11, $e)) };
    (13, $e:expr) => { big_expr!(12, big_expr!(12, $e)) };
    (14, $e:expr) => { big_expr!(13, big_expr!(13, $e)) };
    (15, $e:expr) => { big_expr!(14, big_expr!(14, $e)) };
    (16, $e:expr) => { big_expr!(15, big_expr!(15, $e)) };
}

pub const TEST: () = big_expr!(16, ());

It caused rustc to crash on this loop:

[compiler/rustc_ast_passes/src/ast_validation.rs] <AstValidator as Visitor>::visit_expr()
[compiler/rustc_ast/src/visit.rs] visit::walk_expr::<AstValidator>()
[compiler/rustc_ast_passes/src/ast_validation.rs] <AstValidator as Visitor>::visit_expr()

When I added ensure_sufficient_stack() to visit::walk_expr(), rustc crashed on this loop:

[library/core/src/ptr/mod.rs] ptr::drop_in_place<Expr>()
[library/core/src/ptr/mod.rs] ptr::drop_in_place<ExprKind>()
[library/core/src/ptr/mod.rs] ptr::drop_in_place<P<Expr>>()
[library/core/src/ptr/mod.rs] ptr::drop_in_place<Box<Expr>>()
[library/core/src/ptr/mod.rs] ptr::drop_in_place<Expr>()

This loop was a real pain to fix, since one can't just add ensure_sufficient_stack() to a Drop::drop() implementation. I eventually decided that I needed to wrap one of the offending fields in a ManuallyDrop<_>, then call ensure_sufficient_stack(|| unsafe { ManuallyDrop::drop(&mut self.field) }) within a drop() implementation. Since P<_> is the only type of the three that isn't regularly destructured, I decided to replace its ptr: Box<T> with a ptr: ManuallyDrop<Box<T>> and implement <P<_> as Drop>::drop(). This required some additional unsafe code in functions that extract the contained value. Once I did that, rustc successfully compiled the library.

I plan on putting these fixes into a PR, but I have a few questions I'd like to ask first.

  • Suppose some visitor type has an entry point A and recursive loops A -> B -> C -> A and A -> D -> E -> A. Where is the best place to insert ensure_sufficient_stack()? In my own testing, I've mostly opted to enclose the entire body of A in ensure_sufficient_stack(); this is the simplest method, but it has the greatest overhead, especially when the recursion occurs only rarely. Another option is to insert it between the A -> B and A -> D calls; this has less overhead, but it requires ensure_sufficient_stack() to be written many more times, and it can be difficult to determine which of A's outgoing calls can lead to recursion. The last option is to insert it between the C -> A and E -> A calls; this has the least overhead, but it could cause issues in the future if someone wrote A -> F -> G -> A without knowing to add ensure_sufficient_stack() to the G -> A call. In the current codebase, I've also seen ensure_sufficient_stack() used when entering a recursive loop and nowhere else, but I don't believe that is correct.

  • There is a comment above the definition of rustc_data_structures::stack::STACK_PER_RECURSION:

      // Only the first stack that is pushed, grows exponentially (2^n * STACK_PER_RECURSION) from then
  // on. This flag has performance relevant characteristics. Don't set it too high.
  const STACK_PER_RECURSION: usize = 1 * 1024 * 1024; // 1MB

    The exponential growth worried me somewhat, since it could possibly mask issues in recursive loops called by other recursive loops. When I looked at the definition of stacker::maybe_grow(), however, I could not find anything that could add more than STACK_PER_RECURSION to the stack at a time. Either the comment is wrong, or my eyes are deceiving me. Would you have any idea how I could test this?

  • Is the solution of adding ManuallyDrop<_> to P<_> a valid solution to stack overflows caused by dropping AST nodes? It appears to work correctly, but ManuallyDrop<_> is almost never used in the compiler codebase, and I'm not sure if there's a more proper alternative.

  • What would be the cleanest way to prevent a stack overflow in LLVM's internal visitors? Since they can recurse arbitrarily deep, calling ensure_sufficient_stack() once at the call site would be insufficient. It seems that one would need to expose stacker::maybe_grow through the rustc_data_structures::stack module, somehow traverse the AST to determine its maximum depth, then use that to calculate the necessary stack space ahead of time. I haven't looked much into rustc's middle end, though, and I wouldn't have any idea where or how to perform the traversal.

@LegionMammal978 LegionMammal978 mentioned this issue Jan 19, 2022
Closed
@oli-obk oli-obk removed the E-easy Call for participation: Easy difficulty. Experience needed to fix: Not much. Good first issue. label Jul 4, 2022
@workingjubilee workingjubilee added S-has-mcve Status: A Minimal Complete and Verifiable Example has been found for this issue and removed E-needs-mcve Call for participation: This issue has a repro, but needs a Minimal Complete and Verifiable Example labels Dec 25, 2023
@chansuke chansuke removed their assignment Aug 8, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
C-bug Category: This is a bug. E-needs-test Call for participation: An issue has been fixed and does not reproduce, but no test has been added. I-ICE Issue: The compiler panicked, giving an Internal Compilation Error (ICE) ❄️ S-has-mcve Status: A Minimal Complete and Verifiable Example has been found for this issue T-compiler Relevant to the compiler team, which will review and decide on the PR/issue.
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Fix stack overflows when compiling high-recursion_limit programs LegionMammal978/rust