The call stack and stack frames

Why this matters

You now know that each call gets fresh parameters and local variables, and that return somehow knows where to go back to. The mechanism behind both is the call stack, a region of memory that every C program uses on every call. Understanding it explains a lot at once: why local variables disappear when a function returns, why returning the address of a local variable is a classic bug, how recursion is even possible, what a debugger's "backtrace" shows, and what the famous "stack overflow" really is. It also prepares the ground for pointers and dynamic memory, where the difference between the stack and the heap becomes crucial.

A stack of frames

The process memory diagram from module 1 had a region called the stack. Every time a function is called, a block of memory called a stack frame (or activation record) is reserved on top of the stack for that call. When the function returns, its frame is released. Because the most recently called function is always the first to return, frames are added and removed in last-in, first-out order, like a stack of plates.

A frame typically holds:

• the return address: the instruction in the caller to continue from after the return;
• the caller's saved frame pointer, so the caller's frame can be restored;
• the function's local variables;
• copies of its parameters (on x86-64 the first six integer arguments arrive in registers, and at -O0 the function stores them into its frame).

The CPU keeps the address of the top of the stack in a register, the stack pointer (rsp on x86-64). Reserving a frame is just subtracting from the stack pointer; releasing it is adding back. That is why calling a function and creating local variables is extremely cheap: no searching for free memory, just arithmetic on one register.

Watching it happen

Take this program:

#include <stdio.h>

int inner(int z)
{
    int local_inner = z * 10;
    return local_inner;
}

int middle(int y)
{
    int local_middle = y + 1;
    return inner(local_middle);
}

int main(void)
{
    int local_main = 1;
    printf("result = %d\n", middle(local_main));
    return 0;
}

Here is the stack at each step. On Linux x86-64 the stack grows downward, toward lower addresses, so the newest frame is drawn at the bottom of the region but is called the "top" of the stack.

 1. in main            2. main calls middle(1)    3. middle calls inner(2)

 high addresses
 +----------------+    +----------------+         +----------------+
 | main           |    | main           |         | main           |
 |  local_main=1  |    |  local_main=1  |         |  local_main=1  |
 +----------------+    +----------------+         +----------------+
        ^ rsp          | ret -> main    |         | ret -> main    |
                       | middle         |         | middle         |
                       |  y=1           |         |  y=1           |
                       |  local_middle=2|         |  local_middle=2|
                       +----------------+         +----------------+
                              ^ rsp               | ret -> middle  |
                                                  | inner          |
                                                  |  z=2           |
                                                  |  local_inner=20|
                                                  +----------------+
 low addresses                                           ^ rsp

 4. inner returns 20: its frame is popped, rsp moves back up, middle resumes
 5. middle returns 20: its frame is popped, main resumes and prints "result = 20"

You can see the downward growth by printing the addresses of the locals (&x is the address of x, and %p prints an address; both are covered properly in the pointers module):

printf("main:   &local_main = %p\n", (void *)&local_main);

One run in the sandbox printed:

main:   &local_main = 0x7fff4ea1824c
middle: &local_middle = 0x7fff4ea1822c
inner:  &local_inner = 0x7fff4ea181fc
result = 20

The exact addresses change on every run (Linux randomizes where the stack starts, a security feature called ASLR), but each deeper call's locals sit at lower addresses: 0x...24c, 0x...22c, 0x...1fc.

The return address

How does return know where to go? The machine instruction call inner does two things: it pushes the address of the next instruction (the return address) onto the stack, then jumps to inner. At the end, the ret instruction pops that address off the stack and jumps to it.

 middle:
     ...
     call inner        ; push address of the next line, jump to inner
     mov  ...          ; <- the return address: execution resumes here

The return address sits in the frame right next to the local variables. Remember that: in the arrays module you will see what happens when a program writes past the end of a local array and overwrites it. Overwriting return addresses was the basis of the classic "stack smashing" exploits.

Why locals disappear

When a function returns, its frame is released simply by moving the stack pointer back. The bytes are not erased; they are just no longer reserved, and the next call will reuse that memory for its own frame. That is the precise meaning of lifetime: a local variable exists from the start of its block until the block ends. After that, its memory belongs to whoever is called next.

This gives two rules you must never break:

• A local variable's value does not survive between calls (unless it is static, covered in the last lesson of this module).
• Never keep using the address of a local variable after its function has returned. The memory will be reused; reading it is undefined behavior. The pointers module returns to this.

The debugger's view: backtraces

A debugger can walk the chain of frames, using the saved return addresses and frame pointers, and show you the whole path of calls that led to the current line. With gdb, stopped inside inner:

(gdb) bt
#0  inner (z=2) at v.c:5
#1  0x0000558c83a171ac in middle (y=1) at v.c:14
#2  0x0000558c83a171e2 in main () at v.c:21

Frame #0 is the running function. Each line below is a caller, paused at the line where it made the call, with its parameter values. When a program crashes, the backtrace is the first thing to look at. (The -g flag in our build command is what lets gdb show file names, line numbers and variable names. The debugging module teaches gdb properly.)

Stack overflow

The stack is not infinite. On Linux the default limit is 8 MB per program (ulimit -s prints 8192, in kilobytes). Each frame takes some of it: a few dozen bytes for a small function, more for one with large local arrays. If calls nest too deeply, the stack runs into the end of its region, the kernel detects an access to memory the program does not own, and kills the process with a segmentation fault.

A function that calls itself forever does exactly that. Here each frame contains a 1000-byte local array (arrays come in the next module), so the 8 MB stack fills after about 8000 calls:

depth 7000
depth 8000
Segmentation fault (core dumped)

The shell reports exit status 139, which is 128 + 11: killed by signal 11, SIGSEGV. gcc even warns about the obvious case at compile time:

w.c:5:6: warning: infinite recursion detected [-Winfinite-recursion]

This is where the name of a certain programming Q&A site comes from. Deep but finite recursion and large local arrays are the usual real-world causes. The next lesson, on recursion, shows how to make sure a recursive function stops.

Common mistakes

• Expecting a local to keep its value between calls. Each call gets a new frame; the old value is gone (and an uninitialized local starts with whatever bytes were there: garbage).
• Returning the address of a local variable. gcc warns function returns address of local variable [-Wreturn-local-addr]. Take that warning seriously.
• Huge local arrays. int big[10000000]; inside a function needs 40 MB of stack and crashes immediately. Large data belongs on the heap (module 8) or in static storage.
• Unbounded recursion. Every recursive function needs a base case that is always reached.

Recap

• Each call pushes a stack frame holding the return address, the saved frame pointer, locals and (at -O0) parameter copies; returning pops it. Frames come and go in LIFO order.
• The stack pointer register marks the top; on x86-64 Linux the stack grows toward lower addresses. Allocating a frame is just arithmetic, so calls and locals are cheap.
• call pushes the return address and ret pops it.
• A local variable's lifetime ends when its function returns; its memory is reused.
• A backtrace lists the active frames, newest first.
• The stack is limited (8 MB by default); too deep a call chain gives a segmentation fault.

Going further: compile the three-function example with -g, then in the sandbox terminal run gdb ./prog, type break inner, run, bt, and info frame. Try up and print local_middle to look at a caller's frame.