Functions and Call Stack Frames

Start with the problem

One of the most elusive bugs in C involves returning data from a function. Consider a function designed to generate a formatted timestamp string:

#include <stdio.h>
 
char *format_timestamp(int seconds) {
    char buffer[32];
    snprintf(buffer, sizeof(buffer), "Time: %02d:%02d", seconds / 60, seconds % 60);
    return buffer; /* Warning: function returns address of local variable */
}
 
void log_event(void) {
    char dummy[64];
    for (int i = 0; i < 64; i++) dummy[i] = 'X';
}
 
int main(void) {
    char *time_str = format_timestamp(125);
    printf("Captured: %s\n", time_str);
    
    log_event();
    printf("After logging: %s\n", time_str);
    return 0;
}

When compiled, modern compilers emit a warning: function returns address of local variable.

If a programmer ignores the warning and runs the binary, the first print statement might appear to work:

Captured: Time: 02:05

The string was printed. The memory address was valid. But then log_event() runs, and the second print statement produces garbage or crashes:

After logging: XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Why did the content of time_str change spontaneously even though no code modified time_str?

Now consider parameter passing. A programmer writes a function to swap two numbers:

void swap(int a, int b) {
    int temp = a;
    a = b;
    b = temp;
}

The programmer calls swap(x, y) in main(). Inside swap(), the numbers exchange values. But once swap() finishes and control returns to main(), x and y remain unchanged.

To write correct systems code, you must understand how functions physically run on hardware: how the call stack grows and shrinks, how stack frames are constructed in assembly, how parameters travel between functions, and why automatic variables cease to exist the instant a function returns.

How the idea works

Every thread in a C program owns an isolated memory region known as the call stack.

The call stack operates as a Last-In, First-Out (LIFO) data structure. On modern architectures like x86 and ARM, the stack grows downward in memory, from higher virtual addresses toward lower virtual addresses.

Higher Memory Addresses
┌─────────────────────────────────┐
│ main() Stack Frame              │
│   ├── Local variable 'result'   │
│   └── Return Address to crt0    │
├─────────────────────────────────┤
│ square() Stack Frame            │
│   ├── Return Address to main()  │
│   ├── Saved Base Pointer (RBP)  │
│   └── Local variable 'temp'     │  ◄── Stack Pointer (RSP)
└─────────────────────────────────┘
Lower Memory Addresses (Grows downward)

In the trace above, each step documents the lifecycle of a stack frame as main() invokes square(4) and processes the result.

1. Stack Frame Anatomy and Registers

Two hardware CPU registers coordinate the active stack frame:

• Stack Pointer (RSP on x86-64): Points directly to the current top (lowest address) of the stack. Pushing a value onto the stack decrements RSP; popping increments RSP.
• Base Pointer / Frame Pointer (RBP on x86-64): Anchors a fixed reference address within the current function's frame. Local variables and passed parameters are addressed as positive or negative byte offsets from RBP.

A single stack frame (or activation record) encapsulates:

1. The arguments passed to the function (if not passed in registers).
2. The return address: the instruction pointer address where execution must resume after this function completes.
3. The saved base pointer: the caller's RBP value, so it can be restored upon return.
4. The local variables allocated inside the function body.
5. Saved register states that the function is required to preserve.

2. The Mechanics of Calling Conventions (System V AMD64 ABI)

A calling convention is an architectural standard defining how functions exchange data, which registers hold arguments, and which registers must be preserved.

On 64-bit Linux, macOS, and BSD systems, the standard convention is the System V AMD64 ABI:

• Argument Registers: The first six integer or pointer parameters are passed in specific hardware registers:
  1. First argument: RDI
  2. Second argument: RSI
  3. Third argument: RDX
  4. Fourth argument: RCX
  5. Fifth argument: R8
  6. Sixth argument: R9
• Floating-Point Arguments: The first eight floating-point values pass through vector registers XMM0 through XMM7.
• Excess Arguments: Any argument beyond the sixth is pushed onto the stack in reverse order before the function call.
• Return Values: Integer and pointer return values are placed in register RAX. Floating-point return values are placed in XMM0.

(Note: On 64-bit Windows, the Microsoft x64 calling convention uses four registers instead: RCX, RDX, R8, and R9.)

3. Step-by-Step Execution: Prologue to Epilogue

Let us trace what machine instructions execute during square(4):

Step A: The Call Instruction (Caller)

In main(), step 2 loads 4 into EDI. The CPU executes the call square instruction:

1. The CPU pushes the address of the next instruction in main() (the return address) onto the stack. This decrements RSP by 8 bytes.
2. The instruction pointer (RIP) jumps to the entry address of square.

Step B: Function Prologue (Callee)

The first instructions executed inside square() construct the new stack frame (step 3 of the trace):

pushq   %rbp          # 1. Save caller's RBP on the stack (RSP drops by 8)
movq    %rsp, %rbp    # 2. Anchor current frame: RBP now equals RSP
subq    $16, %rsp     # 3. Reserve 16 bytes of stack space for locals

Now, any reference to the local variable temp is addressed relative to the frame pointer: -4(%rbp).

Step C: Execution and Return Value

In step 4, the multiplication produces 16. The value is stored in temp at -4(%rbp) and loaded into register EAX:

movl    $16, -4(%rbp)
movl    -4(%rbp), %eax # Place return value in EAX

Step D: Function Epilogue (Callee)

To finish, square() tears down its frame and returns control to the caller (step 5 of the trace):

movq    %rbp, %rsp    # 1. Collapse local stack space; RSP returns to RBP
popq    %rbp          # 2. Restore caller's RBP from stack (RSP increments by 8)
ret                   # 3. Pop return address off stack into RIP and jump

Step E: Resuming in Caller

In step 6, execution resumes in main() immediately following the call instruction. The return value 16 sits ready in register EAX.

Why it is correct

Why is function memory managed via a dynamic downward-growing stack rather than fixed static allocations per function?

Reentrancy and Recursion Support

In early languages like Fortran I, local variables occupied fixed static addresses in RAM. If a function called itself recursively, the new invocation overwrote the local variables of the active caller, corrupting state.

By allocating a new stack frame dynamically on every call:

• Each invocation of a function receives its own distinct memory frame on top of the stack.
• A recursive function can call itself hundreds of times; each instance preserves its own local variables at a distinct memory offset.
• When the inner call returns, its frame is popped, cleanly revealing the caller frame underneath without any state corruption.

Single-Instruction Memory Reclamation

Stack memory allocation and deallocation require virtually zero runtime bookkeeping.

• To allocate 64 bytes of local variables: the CPU executes a single subtraction instruction (subq $64, %rsp).
• To deallocate 64 bytes: the CPU executes a single addition instruction (addq $64, %rsp).

There are no free-lists, fragmentation tables, or garbage collection scans. Allocating and freeing stack memory takes one clock cycle.

What it costs

Understanding stack mechanics clarifies the concrete resource boundaries of function execution:

Physical Stack Size Limits

Unlike the heap—which can scale to many gigabytes—the call stack has a strictly enforced upper boundary managed by the operating system kernel:

• Linux / macOS Default: 8 Megabytes (ulimit -s)
• Windows Default: 1 Megabyte
• Embedded Microcontrollers: Often 2 Kilobytes to 16 Kilobytes

If deep recursion or massive local arrays push RSP beyond the allocated stack guard page, the operating system triggers a memory protection fault:

void blow_stack(void) {
    /* Allocating a 10 MB buffer on the stack */
    char huge_buffer[10 * 1024 * 1024]; 
    huge_buffer[0] = 'A'; /* CRASH: Segmentation fault (Stack Overflow) */
}

The stack pointer steps past the guard page boundary, and the kernel terminates the process immediately.

Tail Call Optimization (TCO)

When the final statement of a function is a direct return of another function call, optimizing compilers can perform Tail Call Optimization:

int factorial_tail(int n, int acc) {
    if (n <= 1) return acc;
    return factorial_tail(n - 1, n * acc); /* Tail call */
}

Instead of emitting a call instruction that pushes a new stack frame, the compiler reuses the current stack frame, overwrites the argument registers, and emits an unconditional jump (jmp).

A recursive function that would normally consume 100,000 stack frames runs in O(1) constant stack space, eliminating the risk of stack overflow entirely.

Pitfalls and variations

Pitfall 1: Returning Pointers to Automatic Stack Variables

Returning a pointer to a local array or struct is among the most catastrophic undefined behavior vectors in C:

int *get_counter(void) {
    int counter = 42;
    return &counter; /* DANGEROUS: Returning pointer to stack memory */
}

When get_counter() returns, its stack frame is marked dead. The physical bytes in RAM where counter was stored still contain the value 42 for a few microseconds.

However, the very next function call (printf or another subroutine) may reuse that stack space, overwriting the value. Any future dereference of the returned pointer accesses corrupted data.

To return data safely:

1. Pass a pre-allocated destination buffer from the caller.
2. Use dynamically allocated storage with an explicit ownership rule; heap allocation is introduced later in the track.
3. Declare the variable as static (persists for the entire program lifetime).

Pitfall 2: The Pass-by-Value Illusion

Every argument in C is passed by value. The parameter declared in the function prototype receives a brand-new copy of the passed value:

void modify(int val) {
    val = 999; /* Modifies only the local stack copy */
}
 
int main(void) {
    int x = 10;
    modify(x);
    /* x is STILL 10 */
}

To allow a function to modify a caller variable, you must pass the memory address of the variable explicitly:

void modify(int *val_ptr) {
    *val_ptr = 999; /* Dereferences pointer to modify caller memory */
}
 
int main(void) {
    int x = 10;
    modify(&x);
    /* x is now 999 */
}

Pitfall 3: Stack Canaries and Buffer Overflows

When a local array is written beyond its allocated bounds, it writes upward into higher stack addresses—overwriting the saved RBP and the return address:

Low Memory ──► [ Local Array ] [ Saved RBP ] [ Return Address ] ──► High Memory
                                                     ▲
                              Overwritten by attack! ┘

When the function executes ret, the CPU jumps to whatever corrupted address was placed in the return address slot. This vulnerability is the root cause of buffer overflow exploits.

Modern compilers defend against this by inserting stack canaries (-fstack-protector):

1. In the prologue, a random secret value from the OS kernel is pushed onto the stack immediately before the saved RBP.
2. In the epilogue, the compiler checks if the canary value has changed.
3. If a buffer overflow altered the canary, the runtime aborts immediately (*** stack smashing detected ***) before the ret instruction can jump to corrupted code.

Where it is used

Direct visibility into the call stack is foundational across systems tools and debugging:

• Debuggers and Profilers (GDB, LLDB, Valgrind): The backtrace (bt) command in GDB works by walking the linked list of saved RBP frame pointers up the stack, reading return addresses to reconstruct the sequence of active function calls.
• Kernel Exception Handling: When a hardware interrupt or page fault occurs, the CPU automatically pushes the interrupted user program's instruction pointer (RIP), stack pointer (RSP), and flags onto the kernel stack in a hardware interrupt frame before entering the operating system kernel driver.
• Coroutines and User-Space Schedulers: Libraries implementing lightweight cooperative threads (green threads or coroutines) achieve context switching by manually saving CPU registers and swapping the RSP register to point to an alternate block of stack memory.

In the next lesson, we will examine how variables live inside and outside these stack frames: mastering variable lifetimes, storage classes (static, extern, auto), and compilation linkage models across multi-file programs.