The Call Stack: Frames, Return Addresses and Overflows

A function call is a few writes to memory and a return is a jump to an address read back from it. Step one of four small programs and watch the stack, highest address at the top: amber for each write, blue for each read, and slots that a popped frame left behind stay drawn, dim, because nothing erased them.

Worked example — The Call Stack: Frames, Return Addresses and Overflows

Calls made	5
Deepest point, in frames	5
Stack used at the deepest point	60 of 128 bytes
Result	120

These are the values the calculator shows when the page opens. Change any input above to recompute them.

Loading interactive simulation...

Lesson

The theory — The Call Stack: Frames, Return Addresses and Overflows

The call stack is a region of memory where each function call gets a frame: here its argument, the return address (where the caller resumes), the caller's saved frame pointer, and its local variables. The stack pointer marks the lowest address in use; a call moves it down by a frame and a return moves it back up. A recursion d calls deep with frames of f bytes needs d·f bytes of stack.

What each symbol means

d: the depth: frames on the stack at once
f: the bytes in one frame: 12 here, plus 4 per local variable

Assumes: A 32-bit machine in the classic C calling convention: 4-byte slots, the stack growing toward lower addresses, arguments passed on the stack, a frame pointer kept in every frame. Real 64-bit conventions pass the first arguments in registers, compilers may leave the frame pointer out, and on ARM a function that calls nothing can keep its return address in a register, so real frames differ in size and layout from these three slots.

The return address is a number in memory, and an array can write over it 🖖

Press Six values into four. copy has room for four ints in buf, and buf[0] is at the lowest address, so buf[4] and buf[5] are simply the next two slots up. Those are the slots the call built: the saved frame pointer, then the return address. The loop never checks its index, so the fifth value replaces the frame pointer and the sixth, 0x46464646, replaces the return address. When copy returns, the processor reads that slot and jumps where it says. With four values it returns to 0x08048400 as it should; with five it still returns there, carrying a broken frame pointer back to main. This is a stack buffer overflow. In November 1988 the Morris worm broke into fingerd this way: fingerd read its input into a 512-byte buffer with no limit on how much it read.

A variable you never set holds what the last call left there 🖖

Press Leftover value. set puts 42 in its local variable and returns. Returning moves the stack pointer up and erases nothing. peek is then called from the same place, so its frame lands on the same addresses, and its local y sits at address 1008, exactly where x was. peek never writes y, so reading it returns 42. C calls reading an uninitialised variable undefined behaviour: the language promises nothing, and an optimising compiler may not read the slot at all. When the read does happen, it finds whatever the last write to that address left there.

The stack holds one path through the calls, not all of them 🖖

Set fib to 10. It makes 177 calls, yet at its deepest the stack holds 10 frames, 120 bytes, because a call's frame is popped before its sibling's is pushed: the stack only ever holds the chain from fib(10) down to the call running now. fact(11) makes 11 calls, about a sixteenth as many, and overflows, because its chain is 11 frames long and needs 132 bytes. For these two functions each call does a fixed amount of work besides its recursive calls, so counting calls measures the time; the depth of the longest chain measures the stack.

Problem solved in full

How deep can recursion go? 4 steps
Press fact(11) overflows. The page's stack holds 128 bytes. Microsoft's linker gives a program 1 MB of stack by default; take that as 1 MiB, 1,048,576 bytes, with this page's frames. How deep can fact go? How deep if each call also keeps one 4-byte local? And how much stack does fib(30) need, against how many calls it makes?

Open this problem in the tool
1. One frame here is an argument, a return address and a saved frame pointer: 3 × 4 = 12 bytes. 128 / 12 = 10.67, so ten frames fit, and fact(11) needs 11 × 12 = 132 bytes. The results table prints the overflow.
  
  $f = 3 \times 4 = 12, ⌊ \frac{128}{12} ⌋ = 10, 11 \times 12 = 132 > 128$
2. 1,048,576 / 12 = 87,381.33, so 87,381 frames fit: fact could recurse 87,381 levels before the stack runs out, long after its answer has outgrown a 32-bit int, which happens at 13! = 6,227,020,800.
  
  $⌊ \frac{1 048 576}{12} ⌋ = 87381$
3. With one 4-byte local each frame is 16 bytes, and 1,048,576 / 16 = 65,536 exactly.
  
  $f = 16 : \frac{1 048 576}{16} = 65536$
4. fib(30)'s longest chain is 30 frames, 30 × 12 = 360 bytes. Its calls number 2·F(31) − 1, where F(31) = 1,346,269 is the 31st Fibonacci number: 2,692,537 calls.
  
  $d = 30 : 30 \times 12 = 360, 2 F_{31} - 1 = 2 \times 1346269 - 1 = 2692537$
Answer

87,381 levels, or 65,536 with one local. fib(30) needs 360 bytes of stack for 2,692,537 calls. Depth decides the stack; for fib, the number of calls decides the time.

$d_{m a x} = ⌊ \frac{S}{f} ⌋ = 87381 (f = 12), 65536 (f = 16)$

Learning path

How a computer runs a program

References (2)

The worked problem's stack size: the linker's default reservation: Microsoft Learn, "/STACK (Stack allocations)," C/C++ build reference, updated 23 February 2022.
The first insight's 1988 example: fingerd's unbounded read into a 512-byte buffer on the stack: Bob Page, "A Report on the Internet Worm." University of Lowell, 7 November 1988 (copy hosted at Toronto Metropolitan University).

By the 42Math team · Reviewed against published sources. Corrections welcome.