2 ms·

What does Rust promise if I infinitely recursively call a function which can not be tail optimized? Eventually the stack will exceed either available memory or

by jws 11y ago

What does Rust promise if I infinitely recursively call a function which can not be tail optimized? Eventually the stack will exceed either available memory or available address space, what then?

wofo 11y ago
IIRC Rust will then abort the process with a SIGILL and display a generic error message.
kibwen 11y ago
This is easy to test with a program consisting of `fn main() { main() }`: https://play.rust-lang.org/ https://play.rust-lang.org/ In release mode LLVM seems to be optimizing out the entire program due to dead-code elimination (or maybe sibling-call elimination?), but in debug this is what you get: <anon>:1:1: 3:2 warning: function cannot return without recurring, #[warn(unconditional_recursion)] on by default <anon>:1 fn main() { <anon>:2 main() <anon>:3 } <anon>:2:5: 2:11 note: recursive call site <anon>:2 main() ^~~~~~ <anon>:1:1: 3:2 help: a `loop` may express intention better if this is on purpose thread '<main>' has overflowed its stack fatal runtime error: stack overflow playpen: application terminated abnormally with signal 4 (Illegal instruction) Even though Rust doesn't guarantee stack probes on any OS but Windows at the moment (LLVM patches pending), Rust does guarantee guard pages on all platforms (AFAIK), and assuming that a function's stack frame is always less than a page (which I think should be true), then Rust does indeed seem to guarantee that such an overflow will raise SIGILL.
- dbaupp 11y ago
  I don't think that example is directly relevant: it's tail recursive, and the code still compiles (so there's still runtime behaviour to consider). Additionally, the warning is emitted in both release and debug modes, but only covers "obvious" cases of infinite recursion: it won't say anything about functions that could recur deeply, or infinite recursion that is tricky to prove is infinite. In any case, the Rust language, when it gets guarantees (i.e. a spec), will at the very least guarantee that stack overflow doesn't result in memory corruption, it may not be too opinionated on how exactly implementations make this guarantee. As you say, the rustc compiler currently handles it by guard pages and aborting but not perfectly (it's not hard to have a large stack frame: `let x = [0; 10000]`).
  - kibwen 11y ago
    I'm confused by all your points. The fact that this function is tail recursive doesn't matter, because TCE isn't happening when compiled in debug mode (it would matter if Rust had some other memory-unsafety mitigation that was only enabled in debug mode, but it doesn't), so the stack overflow it exhibits is no different from the stack overflow in a non-tail-recursive function. As for the warning, I wasn't talking about that at all, in fact, I was considering leaving it out of the comment entirely. The relevant part of the output is the final three lines. As for `let x = [0; 10000000];`, that's missing the point of the question that I was responding to, which was concerned with the consequences of stack overflow via recursion, which is moot if the function immediately overflows its stack to begin with.

by jws 11y ago

What does Rust promise if I infinitely recursively call a function which can not be tail optimized? Eventually the stack will exceed either available memory or available address space, what then?

wofo 11y ago

IIRC Rust will then abort the process with a SIGILL and display a generic error message.

kibwen 11y ago

This is easy to test with a program consisting of `fn main() { main() }`: https://play.rust-lang.org/ https://play.rust-lang.org/ In release mode LLVM seems to be optimizing out the entire program due to dead-code elimination (or maybe sibling-call elimination?), but in debug this is what you get: <anon>:1:1: 3:2 warning: function cannot return without recurring, #[warn(unconditional_recursion)] on by default <anon>:1 fn main() { <anon>:2 main() <anon>:3 } <anon>:2:5: 2:11 note: recursive call site <anon>:2 main() ^~~~~~ <anon>:1:1: 3:2 help: a `loop` may express intention better if this is on purpose thread '<main>' has overflowed its stack fatal runtime error: stack overflow playpen: application terminated abnormally with signal 4 (Illegal instruction) Even though Rust doesn't guarantee stack probes on any OS but Windows at the moment (LLVM patches pending), Rust does guarantee guard pages on all platforms (AFAIK), and assuming that a function's stack frame is always less than a page (which I think should be true), then Rust does indeed seem to guarantee that such an overflow will raise SIGILL.

dbaupp 11y ago
I don't think that example is directly relevant: it's tail recursive, and the code still compiles (so there's still runtime behaviour to consider). Additionally, the warning is emitted in both release and debug modes, but only covers "obvious" cases of infinite recursion: it won't say anything about functions that could recur deeply, or infinite recursion that is tricky to prove is infinite. In any case, the Rust language, when it gets guarantees (i.e. a spec), will at the very least guarantee that stack overflow doesn't result in memory corruption, it may not be too opinionated on how exactly implementations make this guarantee. As you say, the rustc compiler currently handles it by guard pages and aborting but not perfectly (it's not hard to have a large stack frame: `let x = [0; 10000]`).
- kibwen 11y ago
  I'm confused by all your points. The fact that this function is tail recursive doesn't matter, because TCE isn't happening when compiled in debug mode (it would matter if Rust had some other memory-unsafety mitigation that was only enabled in debug mode, but it doesn't), so the stack overflow it exhibits is no different from the stack overflow in a non-tail-recursive function. As for the warning, I wasn't talking about that at all, in fact, I was considering leaving it out of the comment entirely. The relevant part of the output is the final three lines. As for `let x = [0; 10000000];`, that's missing the point of the question that I was responding to, which was concerned with the consequences of stack overflow via recursion, which is moot if the function immediately overflows its stack to begin with.