The Call Stack: What Happens When a Function Is Called

Start with the problem

The last lesson said that every call creates fresh parameters and locals, and that they vanish when the call returns. But where do they live? A function can call another function that calls a third, and the machine must remember, for every call that is still in progress, its variables and the place where it should resume. With recursion, which comes in lesson 9, the very same function can be in progress many times at once.

Here is a small program with three nested calls. The trace follows it:

int g(int b) {
    return b + 1;
}
 
int f(int a) {
    return g(a * 2);
}
 
int main() {
    int r = f(3);
}

The machine needs a structure in which the most recent call is always the first to finish. That structure is a stack.

How the idea works

The stack. Each thread of a program gets a block of memory used as a last-in, first-out structure, called the call stack. A CPU register, the stack pointer, marks its top. On x86-64 and on most ARM systems the stack grows toward lower addresses, so pushing something moves the pointer down.

Frames. Every call that is in progress owns a frame, also called an activation record. A frame holds the return address, the call's parameters when they are not passed in registers, its local variables, and some saved registers and padding for alignment. The trace shows frames as cells, with main's at the bottom and the running call on top.

Calling and returning. The call instruction pushes the return address, the instruction after the call, and jumps to the function. The function reserves space for its locals by moving the stack pointer. On the way out it moves the pointer back and executes ret, which pops the return address and jumps to it. Steps 2 and 3 of the trace push frames, and steps 5 and 6 pop them. Pushing or popping a whole frame is a change to one register, which is why calls are cheap and why locals cost almost nothing to create.

Only the top frame runs. Every frame below it is paused at the call that created the frame above. A debugger shows this chain with the backtrace command, innermost call first, which is the command you met in module 1:

(gdb) backtrace
#0  g (b=6) at calls.cpp:2
#1  f (a=3) at calls.cpp:6
#2  main () at calls.cpp:10

Lifetime of locals. A local variable lives exactly as long as its frame. When the function returns, the storage becomes reusable immediately, but nothing erases the old bytes, as the stale cells in steps 5 to 7 show. That explains lesson 3: an uninitialized int total; is given bytes in a frame that an earlier call left behind, so it holds whatever that call wrote there.

Stack versus heap. The stack is for data that lives and dies with a call. Data that must outlive the call that created it needs another region, the heap, which a later module introduces.

Why it is correct

Calls nest like parentheses: whichever function was called last is the first to finish. A stack removes items in exactly that order, so the most recent frame is always the one to release, and the machine needs nothing beyond a single pointer to keep track. The return address stored in each frame lets every call return to its own caller, even when the same function is called from many places or from itself. And separate frames give each call its own variables, which is the independence of calls that lesson 5 relied on.

What it costs

Time. A call and return take a few cycles. The memory near the top of the stack is used constantly, so it nearly always sits in the CPU's fastest cache.

Space. Each frame costs at least the return address and its locals, usually tens of bytes. A function with a local array of 100,000 integers needs 400 KB for every call that is active.

The limit. The size of the stack is fixed when a thread starts. The main thread usually gets 8 MB on Linux, which ulimit -s shows, and 1 MB by default on Windows. Other threads often get less. If a frame of 100 bytes is used for each level of a simple recursion, 8 MB allows tens of thousands of levels, and fewer when the frames are larger. Going past the limit is a stack overflow, and the program is stopped by the operating system, typically with a segmentation fault on Linux.

Pitfalls and variations

Endless or very deep recursion. A function that calls itself without a stopping condition fills the stack and crashes, rather than running forever as a loop would.

Huge local arrays. A local array of ten million integers is 40 MB and overflows an 8 MB stack on its first call. Large data belongs in the heap, for example in a std::vector, which a later module covers.

Returning the address of a local. A pointer to a local variable points into a frame that has been popped. The memory is reused by the next call, so the program may work on one run and fail on another. GCC warns about it with -Wreturn-local-addr.

Overwriting the return address. Writing past the end of a local array can overwrite the return address stored in the frame, so that ret jumps where an attacker chooses. This is called stack smashing. Compilers defend with stack protectors (-fstack-protector), a small guard value that is checked before the function returns.

Frames that disappear. With optimization, the compiler may inline g into f, or turn the call at the end of f into a plain jump that reuses the frame. The frame then never appears in a backtrace, which is why debugging is easier at -O0.

Variations. Every thread has its own stack. Each platform's ABI decides details such as which arguments travel in registers and how frames are aligned, and Windows reserves extra space in every frame. C++20 coroutines keep their frames on the heap, so that a function can pause and resume.

Where it is used

Every function call in every compiled language works this way. Crash reports show a stack trace, which is the backtrace printed after a failure. Profilers sample the stack many times a second to find where time goes, and C++ exceptions work by walking back through the frames and destroying the locals in each one, a topic of a later module.

The next lesson, "Passing by Value, by Reference and by Const Reference", returns to the boundary between a caller and a function, and shows how to let a function work on the caller's variable itself without copying it.