Skip to content

Use stacker to prevent stack overflow from depth-first query evaluation. #41884

New issue

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

#

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

Already on GitHub? # to your account

Jump to bottom
Closed
eddyb opened this issue May 10, 2017 · 5 comments · Fixed by #55617
Closed

Use stacker to prevent stack overflow from depth-first query evaluation. #41884

eddyb opened this issue May 10, 2017 · 5 comments · Fixed by #55617
Labels
C-enhancement Category: An issue proposing an enhancement or a PR with one. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue.

Comments

@eddyb
Copy link
Member

eddyb commented May 10, 2017 •
edited by nikomatsakis
Loading

stacker is:

A library to help grow the stack when it runs out of space.

This is an implementation of manually instrumented segmented stacks where points in a program's control flow are annotated with "maybe grow the stack here". Each point of annotation indicates how far away from the end of the stack it's allowed to be, plus the amount of stack to allocate if it does reach the end.

Once a program has reached the end of its stack, a temporary stack on the heap is allocated and is switched to for the duration of a closure.

Recent PRs that might be relevant: #41625 (MIR inlining) and #41676 (macro expansion).

Also related: #40161, a meta issue for places where deep recursion arise.

cc @rust-lang/compiler
@eddyb eddyb added the T-compiler Relevant to the compiler team, which will review and decide on the PR/issue. label May 10, 2017
@eddyb
Copy link
Member Author

eddyb commented May 10, 2017

(Blocked on #41847 which will make it easier to use crates.io libraries in the compiler)

@jonas-schievink
Copy link
Contributor

Stacker only seems to support i686 and x86-64 at the moment

@jonas-schievink
Copy link
Contributor

(did GitHub eat my previous comment?)

Note that stacker only supports i686 and x86-64 at the moment. While this does cover all tier 1 platforms, it might make maintaining the lower tiers harder.

@nikomatsakis
Copy link
Contributor

@jonas-schievink presumably we could gracefully fall back to the current solution of "really big stack", and encourage lower tiers to extend stacker.

@alexcrichton
Copy link
Member

Ah yeah only i686/x86_64 are supported, but that's just because of the assembly routines, which should hopefully be very easy to port to new platforms! (they're quite small).

I think @nikomatsakis has a good point though that we'd just want to disable it on non-supported platforms beacause there's also OS-specific logic for discovering the stack limit in addition to arch-specific logic for the assembly.

PRs are of course always welcome to improve it!

A few side notes for the library as well:

  • Panics may or may not work currently, but wrapping everything in catch_unwind with a propagate shouldn't be too hard
  • I'm not sure if this strategy is sound on Windows, which historically I think has weird restrictions about stack pointers. I'm not sure though, it may be just fine!

This was referenced Jun 8, 2017
Closed
Closed
@Mark-Simulacrum Mark-Simulacrum added the C-enhancement Category: An issue proposing an enhancement or a PR with one. label Jul 27, 2017
@oli-obk oli-obk mentioned this issue Nov 2, 2018
Merged
bors added a commit that referenced this issue Nov 6, 2018
@bors
Auto merge of #55617 - oli-obk:stacker, r=<try>
2b10b3d 
Prevent compiler stack overflow for deeply recursive code

I was unable to write a test that

1. runs in under 1s
2. overflows on my machine without this patch

The following reproduces the issue, but I don't think it's sensible to include a test that takes 30s to compile. We can now easily squash newly appearing overflows by the strategic insertion of calls to `ensure_sufficient_stack`.

```rust
// compile-pass

#![recursion_limit="1000000"]

macro_rules! chain {
    (EE $e:expr) => {$e.sin()};
    (RECURSE $i:ident $e:expr) => {chain!($i chain!($i chain!($i chain!($i $e))))};
    (Z $e:expr) => {chain!(RECURSE EE $e)};
    (Y $e:expr) => {chain!(RECURSE Z $e)};
    (X $e:expr) => {chain!(RECURSE Y $e)};
    (A $e:expr) => {chain!(RECURSE X $e)};
    (B $e:expr) => {chain!(RECURSE A $e)};
    (C $e:expr) => {chain!(RECURSE B $e)};
    // causes overflow on x86_64 linux
    // less than 1 second until overflow on test machine
    // after overflow has been fixed, takes 30s to compile :/
    (D $e:expr) => {chain!(RECURSE C $e)};
    (E $e:expr) => {chain!(RECURSE D $e)};
    (F $e:expr) => {chain!(RECURSE E $e)};
    // more than 10 seconds
    (G $e:expr) => {chain!(RECURSE F $e)};
    (H $e:expr) => {chain!(RECURSE G $e)};
    (I $e:expr) => {chain!(RECURSE H $e)};
    (J $e:expr) => {chain!(RECURSE I $e)};
    (K $e:expr) => {chain!(RECURSE J $e)};
    (L $e:expr) => {chain!(RECURSE L $e)};
}

fn main() {
    let x = chain!(D 42.0_f32);
}
```

fixes #55471
fixes #41884
fixes #40161
fixes #34844
fixes #32594

cc @alexcrichton @rust-lang/compiler

I looked at all code that checks the recursion limit and inserted stack growth calls where appropriate.
bors added a commit that referenced this issue Nov 13, 2018
@bors
Auto merge of #55617 - oli-obk:stacker, r=<try>
5009042 
Prevent compiler stack overflow for deeply recursive code

I was unable to write a test that

1. runs in under 1s
2. overflows on my machine without this patch

The following reproduces the issue, but I don't think it's sensible to include a test that takes 30s to compile. We can now easily squash newly appearing overflows by the strategic insertion of calls to `ensure_sufficient_stack`.

```rust
// compile-pass

#![recursion_limit="1000000"]

macro_rules! chain {
    (EE $e:expr) => {$e.sin()};
    (RECURSE $i:ident $e:expr) => {chain!($i chain!($i chain!($i chain!($i $e))))};
    (Z $e:expr) => {chain!(RECURSE EE $e)};
    (Y $e:expr) => {chain!(RECURSE Z $e)};
    (X $e:expr) => {chain!(RECURSE Y $e)};
    (A $e:expr) => {chain!(RECURSE X $e)};
    (B $e:expr) => {chain!(RECURSE A $e)};
    (C $e:expr) => {chain!(RECURSE B $e)};
    // causes overflow on x86_64 linux
    // less than 1 second until overflow on test machine
    // after overflow has been fixed, takes 30s to compile :/
    (D $e:expr) => {chain!(RECURSE C $e)};
    (E $e:expr) => {chain!(RECURSE D $e)};
    (F $e:expr) => {chain!(RECURSE E $e)};
    // more than 10 seconds
    (G $e:expr) => {chain!(RECURSE F $e)};
    (H $e:expr) => {chain!(RECURSE G $e)};
    (I $e:expr) => {chain!(RECURSE H $e)};
    (J $e:expr) => {chain!(RECURSE I $e)};
    (K $e:expr) => {chain!(RECURSE J $e)};
    (L $e:expr) => {chain!(RECURSE L $e)};
}

fn main() {
    let x = chain!(D 42.0_f32);
}
```

fixes #55471
fixes #41884
fixes #40161
fixes #34844
fixes #32594

cc @alexcrichton @rust-lang/compiler

I looked at all code that checks the recursion limit and inserted stack growth calls where appropriate.
@nagisa nagisa mentioned this issue Sep 30, 2019
Closed
Centril added a commit to Centril/rust that referenced this issue Mar 18, 2020
@Centril
Rollup merge of rust-lang#55617 - oli-obk:stacker, r=oli-obk,nagisa
d6e0e11 
Prevent compiler stack overflow for deeply recursive code

I was unable to write a test that

1. runs in under 1s
2. overflows on my machine without this patch

The following reproduces the issue, but I don't think it's sensible to include a test that takes 30s to compile. We can now easily squash newly appearing overflows by the strategic insertion of calls to `ensure_sufficient_stack`.

```rust
// compile-pass

#![recursion_limit="1000000"]

macro_rules! chain {
    (EE $e:expr) => {$e.sin()};
    (RECURSE $i:ident $e:expr) => {chain!($i chain!($i chain!($i chain!($i $e))))};
    (Z $e:expr) => {chain!(RECURSE EE $e)};
    (Y $e:expr) => {chain!(RECURSE Z $e)};
    (X $e:expr) => {chain!(RECURSE Y $e)};
    (A $e:expr) => {chain!(RECURSE X $e)};
    (B $e:expr) => {chain!(RECURSE A $e)};
    (C $e:expr) => {chain!(RECURSE B $e)};
    // causes overflow on x86_64 linux
    // less than 1 second until overflow on test machine
    // after overflow has been fixed, takes 30s to compile :/
    (D $e:expr) => {chain!(RECURSE C $e)};
    (E $e:expr) => {chain!(RECURSE D $e)};
    (F $e:expr) => {chain!(RECURSE E $e)};
    // more than 10 seconds
    (G $e:expr) => {chain!(RECURSE F $e)};
    (H $e:expr) => {chain!(RECURSE G $e)};
    (I $e:expr) => {chain!(RECURSE H $e)};
    (J $e:expr) => {chain!(RECURSE I $e)};
    (K $e:expr) => {chain!(RECURSE J $e)};
    (L $e:expr) => {chain!(RECURSE L $e)};
}

fn main() {
    let x = chain!(D 42.0_f32);
}
```

fixes rust-lang#55471
fixes rust-lang#41884
fixes rust-lang#40161
fixes rust-lang#34844
fixes rust-lang#32594

cc @alexcrichton @rust-lang/compiler

I looked at all code that checks the recursion limit and inserted stack growth calls where appropriate.
@bors bors closed this as completed in 97f3eee May 7, 2020
# for free to join this conversation on GitHub. Already have an account? # to comment
Assignees
No one assigned
Labels
C-enhancement Category: An issue proposing an enhancement or a PR with one. 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.

Prevent compiler stack overflow for deeply recursive code oli-obk/rust
5 participants
@alexcrichton @eddyb @nikomatsakis @jonas-schievink @Mark-Simulacrum