Function Calls and Stack Execution
Think of the call stack as a stack of sticky notes.
Learning Objectives
Describe exactly what happens when a function is called and when it returns.
Identify the parts of a stack frame: return address, saved registers, frame pointer, locals and outgoing arguments.
Explain calling conventions and ABIs, argument and return-value passing, prologues and epilogues.
Reason about nested calls, recursion, stack size, stack overflow, tail calls and inlining.
Explain exception stack unwinding, interrupt contexts, re-entrancy and how to read a stack trace.
Plain-Language Explanation
Think of the call stack as a stack of sticky notes. When main calls add_one, a new note — a stack frame — goes on top. It records where to come back to in main, plus room for add_one's own variables. When add_one finishes, its note is thrown away and execution continues in main exactly where it left off. A recursive function puts one note per active call on the pile; if the pile grows too tall, the program runs out of stack space and crashes.
Precise Technical Explanation
What happens when a function is called On x86-64 Linux (System V ABI), a call output = add_one(input):
The caller places arguments in registers (%edi for the first int).
call add_one pushes the return address (the instruction after the call) and jumps.
The callee's prologue may save the old frame pointer and reserve space for locals.
The body runs.
The result goes in %eax; the epilogue restores saved registers and the stack pointer.
ret pops the return address and jumps back; the caller copies %eax into output.
Call stack and stack frames The call stack is the region of a thread's stack holding one frame (activation record) per active call. A frame typically holds: the return address, the saved frame pointer, callee-saved registers the function uses, local variables that need memory, spill slots, and space for outgoing arguments that do not fit in registers.
Parameters and return values Language rules (C: by value) say *what* is passed; the ABI says *how*. Small results return in registers (%rax/%xmm0 on x86-64, x0/v0 on AArch64); large structures are returned through a hidden pointer supplied by the caller.
The address of the instruction following the call. On x86 it is pushed on the stack by call; on ARM and RISC-V it is placed in a *link register* (lr/ra) and saved on the stack only if the function calls others.
Saved registers and frame pointer ABIs split registers into caller-saved (a callee may overwrite them, so the caller saves what it needs) and callee-saved (a callee must restore them before returning — on x86-64: %rbx, %rbp, %r12–%r15). The frame pointer (%rbp, x29, fp) optionally points at a fixed place in the current frame; at -O2 GCC usually omits it and uses %rbp as an ordinary register.
Local variables and compiler register allocation Locals live in registers whenever possible. A local gets a stack slot only when there are not enough registers, when its address is taken, or at -O0 (where GCC keeps every variable in memory to make debugging easy).
Calling conventions and the ABI An Application Binary Interface defines everything two separately compiled pieces of code must agree on: argument registers, stack alignment (16 bytes at a call on x86-64), callee-saved registers, return conventions, type sizes and struct layout.
Integer/pointer arguments System V x86-64 (Linux, macOS) rdi, rsi, rdx, rcx, r8, r9 128-byte red zone below rsp Microsoft x64 (Windows) rcx, rdx, r8, r9
32-byte shadow space reserved by the caller AAPCS64 (AArch64) link register x30 return address in ra
Argument passing: registers, stack and language rules Arguments beyond the register set, and some large structures, go on the stack. Variadic functions (printf) have extra rules (on x86-64 %al holds the number of vector registers used).
Integers and pointers in the integer return register; floating point in a vector register; small structs in one or two registers; larger structs through caller-provided memory (the hidden pointer arrives as an argument).
Prologue and epilogue (architecture-dependent) The -O0 x86-64 pattern: push %rbp; mov %rsp,%rbp; sub $N,%rsp … leave; ret. Optimised code often has no prologue at all. AArch64 typically uses stp x29, x30, [sp, #-16]! … ldp x29, x30, [sp], #16; ret.
Nested function calls Each call adds a frame above the caller's; frames are removed in reverse order (last in, first out). Only the top frame executes; the rest are suspended at their call sites.
Stack growth direction (not universal) On x86, x86-64, ARM, AArch64 and RISC-V the stack grows toward lower addresses: a callee's frame has *lower* addresses than its caller's. Some historical architectures grew upward; the C standard says nothing about it.
Stack size and stack overflow Each thread's stack has a fixed maximum: Linux main thread 8 MiB by default (ulimit -s), Linux new threads 8 MiB (glibc default from the same limit), Windows 1 MiB, typical RTOS tasks a few hundred bytes to a few KiB. Exceeding it — deep recursion or huge local arrays — hits the guard page and the OS kills the process with SIGSEGV (Linux) or STATUS_STACK_OVERFLOW (Windows).
Recursion and recursive call frames Every active recursive call has its own frame and its own copies of locals. Memory use is proportional to the maximum depth, not the total number of calls.
Tail calls and tail-call optimization A call is a tail call if it is the last action of the function (return f(x);). Compilers may then reuse the current frame — replacing call + ret with a jmp — so tail recursion runs in constant stack space. C and C++ do not *guarantee* it; Scheme does; GCC and Clang do it at -O2 when the ABI allows.
Inlining and its debugging implications Inlining copies a function's body into the caller, removing the call entirely. It enables further optimizations, but the inlined function has no frame of its own, so debuggers and stack traces may skip it or show it as an "inlined frame" reconstructed from debug information.
Exceptions and stack unwinding When a C++ exception is thrown, the runtime walks the stack frame by frame using unwind tables (.eh_frame), runs the destructors of every automatic object in each abandoned frame, and stops at a matching catch. This "zero-cost" model costs nothing on the normal path but is slow when an exception is actually thrown. C has no exceptions; setjmp/longjmp jump across frames *without* running cleanup.
Interrupt stack/context overview for embedded systems An interrupt is an unplanned "call": the hardware saves part of the context (on Cortex-M: r0–r3, r12, lr, pc, xPSR — the stack frame is pushed automatically) and jumps to the handler. Handlers run on a dedicated stack (Cortex-M's main stack, MSP) or the interrupted task's stack depending on the architecture. Every task stack must leave room for the deepest nesting of interrupts.
Re-entrancy and stack-local state A function is re-entrant if it can be safely entered again before a previous invocation finished — from recursion, another thread or an interrupt. Functions that use only parameters and locals are re-entrant; functions with static or global state (strtok, classic rand) are not. Hence strtok_r and rand_r.
Stack trace reading A stack trace lists frames from the innermost (where the event happened) outward: #0 is the current function, #1 its caller, and so on. Each line shows a return address, ideally symbolised as function+offset (file:line). Read from the top to see *where*, from the bottom to see *how we got there*.
Debugging call stacks in an IDE Every debugger has a *Call Stack* window: selecting a frame shows that frame's locals and source position. "Step into", "step over" and "step out" move between frames. With optimised code, some frames may be missing (inlined) and some values "optimized out".
Why It Matters in Real Systems
Crash reports are stack traces. Stack overflows take down servers and firmware. Understanding frames lets you reason about recursion depth limits, the cost of calls, why debug and release stack traces differ, and how much stack every RTOS task needs.
Key Terms
Per-call record: return address, saved registers, locals Register holding the current top of the stack (rsp, sp)
Optional register pointing to a fixed place in the frame Where execution continues after the callee returns ABI / calling convention
Binary rules for calls: registers, stack, layout Prologue / epilogue
Instructions that set up / tear down a frame A call that is the function's last action
Walking and popping frames, running cleanup, during exception propagation
Safe to enter again before an earlier call finished
Memory Layout and Execution Flow
flowchart TB
subgraph Stack[Call stack - grows downward on x86-64]
M[main frame: input = 41, output = ?] --> A[add_one frame: return address into main, value = 41, result = 42]
endSyntax
No dedicated syntax: calls are ordinary function-call expressions. Compiler-specific helpers used below:
void *__builtin_frame_address(unsigned level); /* GCC/Clang: this frame (0) or a caller's */
void *__builtin_return_address(unsigned level); /* GCC/Clang: where this function returns */
#include <execinfo.h> /* glibc: backtrace(), backtrace_symbols_fd() */Complete Runnable Example
The specification's call trace, instrumented to print frame and variable addresses. GCC 11.2, -O0, x86-64 Linux.
The same function compiled without and with optimization:
#include <stdio.h>
int add_one(int value)
{
int result = value + 1;
printf(" add_one frame %p &value %p &result %p returns to %p\n",
__builtin_frame_address(0), (void *)&value, (void *)&result,
__builtin_return_address(0));
return result;
}
int main(void)
{
int input = 41;
printf("main frame %p &input %p\n", __builtin_frame_address(0), (void *)&input);
int output = add_one(input);
printf("output = %d\n", output);
return 0;
}cat > pure.c <<'EOF2'
int add_one(int value) { int result = value + 1; return result; }
EOF2
gcc -O0 -S -fno-asynchronous-unwind-tables pure.c -o o0.s
echo "--- add_one at -O0 (frame pointer, every variable in memory) ---"; sed -n '/^add_one:/,/ret/p' o0.s
gcc -O2 -S -fno-asynchronous-unwind-tables pure.c -o o2.s
echo "--- the same function at -O2 ---"; sed -n '/^add_one:/,/ret/p' o2.sLine-by-Line Explanation
__builtin_frame_address(0) returns this function's frame address (meaningful at -O0, where %rbp is a frame pointer).
&value is a stack slot: at -O0 GCC copies the register argument %edi into memory so a debugger can show it.
__builtin_return_address(0) is the address in main right after the call add_one instruction.
The -O0 assembly shows the prologue (push %rbp, mov %rsp,%rbp), the argument %edi stored into a stack slot, result kept in another slot, and the epilogue (pop %rbp, ret). A leaf function at -O0 may use the red zone below %rsp instead of moving the stack pointer.
At -O2 the entire function becomes one instruction plus ret: lea 1(%rdi), %eax computes value + 1 directly into the return register — no frame, no memory.
Expected Output
Output (one real run — addresses differ on each run):
Notice that add_one's frame address is *lower* than main's: the stack grows downward. The return address lies in the executable's code mapping (the 0x5… addresses at the bottom of the address space), not on the heap or stack.
main frame 0x7fff73bf4240 &input 0x7fff73bf4230
add_one frame 0x7fff73bf4220 &value 0x7fff73bf420c &result 0x7fff73bf4214 returns to 0x5d57ebdd6225
output = 42--- add_one at -O0 (frame pointer, every variable in memory) ---
add_one:
endbr64
pushq %rbp
movq %rsp, %rbp
movl %edi, -20(%rbp)
movl -20(%rbp), %eax
addl $1, %eax
movl %eax, -4(%rbp)
movl -4(%rbp), %eax
popq %rbp
ret
--- the same function at -O2 ---
add_one:
endbr64
leal 1(%rdi), %eax
retStep-by-Step Execution Trace
Stack (top first) main stores 41 in input mov input → %edi, call add_one pushes return address ret-addr, main prologue: push %rbp, mov %rsp,%rbp, sub add_one frame, ret-addr, main
result = value + 1 = 42, copied to %eax add_one frame, …
leave restores %rsp/%rbp; ret pops the return address
main stores %eax into output and prints 42
Interactive Visualization
Step forward and backward through calls and returns; try the recursive factorial with a configurable depth and watch frames pile up and disappear.
Common Mistakes and Failure Modes
Unbounded recursion (missing base case) or recursion depth proportional to untrusted input.
Huge local arrays — double grid[1000][1000]; is 8 MB, the entire default Linux stack.
Returning addresses of locals (Module 4).
Assuming frames look the same in release builds — optimised code inlines, omits frame pointers and keeps locals in registers.
Non-re-entrant functions in threads or interrupt handlers (strtok, localtime, printf in an ISR).
A stack overflow, made safe by running it in a shell with a deliberately small 1 MiB limit:
Output (one real run):
With a 1 MiB stack and roughly 300 bytes per frame, the program gets a little over 3,000 calls deep before touching the guard page. The kernel delivers SIGSEGV; the shell reports the crash.
#include <stdio.h>
#include <sys/resource.h>
static unsigned long depth;
static int dive(int n)
{
volatile char pad[256]; /* make each frame noticeably larger */
pad[0] = (char)n;
++depth;
if (depth % 1000 == 0) {
fprintf(stderr, "depth %lu\n", depth);
}
return dive(n + 1) + pad[0]; /* not a tail call: the frame must stay */
}
int main(void)
{
struct rlimit rl;
getrlimit(RLIMIT_STACK, &rl);
fprintf(stderr, "stack limit: %llu KiB\n", (unsigned long long)rl.rlim_cur / 1024);
return dive(0);
}gcc -std=c17 -O0 m05_overflow.c -o m05_overflow
( ulimit -s 1024; ./m05_overflow ) 2>&1 || echo "exit status $? = 128 + 11: the process was killed by SIGSEGV"stack limit: 1024 KiB
depth 1000
depth 2000
depth 3000
m05_overflow_run.sh: line 2: 19 Segmentation fault (core dumped) ./m05_overflow
exit status 139 = 128 + 11: the process was killed by SIGSEGVCorrected / Safe Pattern
When recursion is natural (trees), bound the depth explicitly or use an explicit stack data structure on the heap.
/* iterative instead of recursive: constant stack use */
unsigned long long factorial(unsigned n)
{
unsigned long long r = 1;
for (unsigned i = 2; i <= n; ++i) r *= i;
return r;
}
/* large working memory on the heap, not the stack */
double *grid = malloc(1000u * 1000u * sizeof *grid);Debugging and Diagnostic Techniques
Reading a real stack trace — glibc's backtrace() prints the return addresses of every active frame (-rdynamic exports function names so they can be symbolised):
Output (one real run):
Each line is binary(function+offset) [return address]: read top to bottom as "level3 was called by level2, called by level1, called by main, called by the C start-up code in libc". addr2line -e ./m05_backtrace -f <offset> or a debugger turns offsets into file and line numbers.
C++ exceptions unwind frames and run destructors on the way:
Destructors run innermost-first as each frame is abandoned, *before* the catch body runs.
#include <execinfo.h>
#include <stdio.h>
#include <unistd.h>
void level3(void)
{
void *frames[16];
int n = backtrace(frames, 16);
puts("stack trace, innermost frame first:");
fflush(stdout);
backtrace_symbols_fd(frames, n, STDOUT_FILENO);
}
void level2(void) { level3(); }
void level1(void) { level2(); }
int main(void)
{
level1();
return 0;
}stack trace, innermost frame first:
./m05_backtrace(level3+0x32)[0x606e480ef1fb]
./m05_backtrace(level2+0xd)[0x606e480ef25f]
./m05_backtrace(level1+0xd)[0x606e480ef26f]
./m05_backtrace(main+0xd)[0x606e480ef27f]
/lib/x86_64-linux-gnu/libc.so.6(+0x29d90)[0x74de5f429d90]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0x80)[0x74de5f429e40]
./m05_backtrace(_start+0x25)[0x606e480ef105]#include <iostream>
#include <stdexcept>
struct Guard {
const char *name;
explicit Guard(const char *n) : name(n) { std::cout << " enter " << name << '\n'; }
~Guard() { std::cout << " leave " << name << " (destructor)\n"; }
};
void inner() { Guard g("inner"); throw std::runtime_error("sensor timeout"); }
void middle() { Guard g("middle"); inner(); std::cout << "never printed\n"; }
int main()
{
try {
Guard g("main try-block");
middle();
} catch (const std::exception &e) {
std::cout << "caught: " << e.what() << '\n';
}
}enter main try-block
enter middle
enter inner
leave inner (destructor)
leave middle (destructor)
leave main try-block (destructor)
caught: sensor timeoutPerformance Implications
A call costs a few cycles — but prevents optimizations across the call boundary, which is why inlining small hot functions matters. Deep recursion touches many stack pages and hurts cache locality. Tail-call optimization and iterative rewrites keep stack use constant:
cat > tail.c <<'EOF'
unsigned long sum_to(unsigned long n, unsigned long acc)
{
if (n == 0) return acc;
return sum_to(n - 1, acc + n); /* tail call */
}
EOF
gcc -O0 -S -fno-asynchronous-unwind-tables tail.c -o tail0.s
gcc -O2 -S -fno-asynchronous-unwind-tables tail.c -o tail2.s
echo "calls to sum_to at -O0: $(grep -c 'call.*sum_to' tail0.s)"
echo "calls to sum_to at -O2: $(grep -c 'call.*sum_to' tail2.s)"
echo "--- -O2 body: the recursion became a loop ---"; sed -n '/^sum_to:/,/ret/p' tail2.scalls to sum_to at -O0: 1
calls to sum_to at -O2: 0
--- -O2 body: the recursion became a loop ---
sum_to:
endbr64
movq %rsi, %rax
testq %rdi, %rdi
je .L5
.p2align 4,,10
.p2align 3
.L2:
addq %rdi, %rax
subq $1, %rdi
jne .L2
.L5:
retSecurity and Safety Implications
Stack buffer overflows can overwrite saved registers and the return address. Mitigations: stack canaries (-fstack-protector-strong places a random value before the return address and checks it in the epilogue), shadow stacks (Intel CET, Arm GCS) that keep a protected copy of return addresses, non-executable stacks and ASLR. The real fix is bounds-checked code (Modules 8 and 9). Recursion on untrusted input is a denial-of-service risk.
Platform and Language Caveats
All register names, frame layouts and prologues above are x86-64 System V specifics; Windows x64, AArch64 and RISC-V differ.
Optimization changes everything physical about frames; the *logical* call stack (who called whom) is what the language guarantees.
Java, C#, Python and JavaScript have their own logical call stacks; deep recursion raises StackOverflowError, RecursionError or RangeError: Maximum call stack size exceeded instead of crashing the process (C#'s StackOverflowException cannot be caught and terminates the process).
Python limits recursion depth to 1000 by default (sys.getrecursionlimit()).
Real-World Application
Crash-reporting services (Sentry, Windows Error Reporting, Android tombstones) collect stack traces and symbolise them with debug files. RTOS engineers size each task's stack from measured high-water marks. Profilers sample stack traces thousands of times per second to build flame graphs.
Best Practices Checklist
[ ] Keep recursion depth bounded, or rewrite as iteration.
[ ] Put large buffers on the heap or in static storage.
[ ] Keep -fstack-protector-strong and other hardening flags enabled.
[ ] Use re-entrant APIs (strtok_r, localtime_r) in threaded and interrupt code.
[ ] Archive debug symbols so production stack traces can be symbolised.
[ ] Measure stack high-water marks on embedded targets.
Exercises
E1 · Beginner. Draw the call stack at the moment level3 runs in the backtrace example. Which frame is on top?
Answer: From top: level3, level2, level1, main, then C start-up frames. level3 is on top because it is the most recent call.
E2 · Intermediate. A recursive tree traversal uses 96 bytes per frame. The stack is 8 MiB. Roughly how deep can the tree be? Why is relying on this a bad idea?
Answer: About 8,388,608 / 96 ≈ 87,000 levels, minus what the rest of the program uses. Frame size changes with compiler, flags and code edits, threads may have smaller stacks, and a degenerate (list-shaped) tree from untrusted input reaches that depth easily.
E3 · Advanced challenge. Explain why return n * fact(n - 1); is *not* a tail call while return fact_acc(n - 1, acc * n); is, and confirm it with the -O2 assembly of both.
Answer: In the first, the multiplication happens *after* the recursive call returns, so the frame must survive. In the second, nothing remains to do after the call, so the frame can be reused (jmp or a loop instead of call). (GCC can sometimes turn the first form into a loop too by reassociating the multiplication — check the assembly rather than assuming.)
Quiz
? On x86-64 System V, where does the first integer argument of a function arrive?
+ In register %rdi :: rdi, rsi, rdx, rcx, r8, r9 carry the first six integer arguments.
- On the stack, just above the return address :: Only arguments beyond the sixth (or large structs) use the stack.
- In %rax :: rax holds the return value.
- In %rcx :: That is the Windows x64 convention.
? What runs while a C++ exception propagates out of a function?
- Nothing until the catch block :: Destructors of automatic objects run during unwinding.
+ Destructors of the automatic objects in each abandoned frame :: That is how RAII guarantees cleanup.
- free() on every heap allocation :: Only objects whose destructors free memory release it.
- The function's remaining statements :: They are skipped.
? Which can cause a stack overflow? (select all that apply)
+ Unbounded recursion :: Every call adds a frame.
+ A 16 MiB local array on Linux with default limits :: It exceeds the 8 MiB main-thread stack.
- A 16 MiB malloc :: Heap allocations do not use the stack.
- Calling many functions one after another :: Sequential calls reuse the same stack space.
? Why can an optimised stack trace be missing a function y
…Summary
Each call pushes a frame holding the return address, saved registers and locals; each return pops it. The ABI fixes how arguments and results travel. Optimization removes frames (inlining), frame pointers and memory slots, and can turn tail calls into jumps. Stack size is finite; overflow is fatal in C. Exceptions unwind frames and run destructors. Stack traces are read innermost first.
References and Further Reading
*System V ABI AMD64 Supplement*, chapter 3 (function calling sequence).
Microsoft Docs, "x64 calling convention"; Arm, "Procedure Call Standard for the Arm 64-bit Architecture (AAPCS64)".
Eli Bendersky, "Stack frame layout on x86-64".
Itanium C++ ABI, "Exception Handling" (used by GCC and Clang on Linux).