Zero-sized stack frames?

This function infinitely recurses and overflows the stack:

fn print_forever() {
  println!("hello");
  print_forever();
}

But I'm curious a to what's actually in that stack frame that take up space. AFAIK, there are no local variables (I don't think println expands to contain any, and the string is a constant), no parameters, no return value. The mental model I have is: if I was writing a struct to represent the stack frame for this function, it seems like it would be zero-sized. So why does this function still overflow?

Looking at it another way, I guess the question is also: "why can't it be optimised to just a syscall and a jump"? It strikes me as pretty similar to the classic 10 PRINT "hello"; 20 GOTO 10 BASIC programs, which of course have no such limitation.

Is this a limitation in rustc? LLVM? Or am I misunderstanding something (I presume it's this one :grin: ). Is it actually guaranteed semantics that a function like this will overflow and this sort of optimization is therefore "incorrect"?

P.S. Is there a way to visualise what the stack frame for some function would look like?

Thanks :grin:

1 Like

Well, you'd need to still store the "return address". That's 8 bytes per call.
The way function calls work on x86 is as follows - a call instruction pushes the offset of the next instruction (next pc) onto the stack, then jumps to the function. Why do we need this? Because when we do a ret instruction, we need to know where to return to.
On RISC architectures such as ARM or MIPS, there is a "link-register", to store the return address. But for recursive functions, the old contents of the link register needs to be saved on the stack before storing the new value there.

2 Likes

Every stack frame would consist of at least the return address, so that the program can continue after returning from the function.

It can - see tail-call optimization. This is just not guaranteed in Rust, but there are languages without explicit loops which guarantee this (mainly purely functional ones).

3 Likes

On my laptop and on Godbolt, the optimized version does happen to get tail-call optimization applied and the code just loops. But as @Cerber-Ursi said, it's not guaranteed in Rust.

Relatedly, Rust does have a keyword (become) reserved for explicit tail calls, but as far as I know it doesn't have a champion and hasn't seen movement in quite some time.

1 Like

Well, it doesn't in release mode. You can see in https://rust.godbolt.org/z/MedTY9vxj that it's just a loop.

But no, there's no guaranteed tail recursion in rust. LLVM will optimize things to that sometimes, but you must not rely on it. Maybe one day we'll get become -- the keyword's already reserved for it.

1 Like