Skip to main content
Be Bitwise

The Stack

The Stack & The Heap · Memory & Systems track

6 min read

Part ofSystems Programming Companion, week 4

In this module

Last In, First Out

The stack is a region of memory that operates as a LIFO (Last In, First Out) data structure. Think of a stack of plates: you always add to the top, and remove from the top. The CPU uses this structure to manage function calls, and it's astonishingly cheap to do so.

Stack Frames

Every time your program calls a function, a new stack frame is pushed onto the stack. Each frame contains:

  • Return address - where to resume execution after the function finishes
  • Saved registers - register values from the calling function that need to be preserved
  • Local variables - the function's own variables
  • Function arguments - the parameters passed to the function, when there are too many to fit in registers

When the function returns, its stack frame is popped off, and execution continues at the return address. All the local variables in that frame are effectively gone.

Key Concept

Every function call creates a stack frame containing the return address, saved registers, local variables, and arguments. When the function returns, its frame is popped off the stack and the memory is reclaimed instantly.

The Stack Pointer

The CPU has a dedicated register called the stack pointer (SP) that always points to the top of the stack. On x86-64 it's called rsp. Call a function, and the stack pointer moves downward (to a lower address) to make room for the new frame. When the function returns, it moves back up. No bookkeeping required, just a pointer adjustment.

This is why stack allocation is so fast. Carving out space for local variables is literally subtracting a number from the stack pointer. Freeing it is adding the number back. No searching for free blocks, no fragmentation, no garbage collector chewing through pointers in the background.

A Concrete Example

Consider this call chain: main() calls calculate(), which calls add(). The stack grows like this:

When add() returns, its frame is removed and the stack pointer moves up to calculate(). When calculate() returns, the same thing again. The stack always unwinds in the exact reverse order of the calls; there's no other way for it to behave.

Worked Example: Following rsp

Here's the same chain on x86-64 Linux, built without optimisation, with rsp tracked at every step. Say main is about to call calculate and rsp holds 0x7fffffffe0f0.

StepInstructionWhat it doesrsp afterwards
1call calculate (in main)pushes the return address into main0x7fffffffe0e8
2push rbp (in calculate)saves main's frame pointer0x7fffffffe0e0
3sub rsp, 16reserves 16 bytes for calculate's locals0x7fffffffe0d0
4call addpushes the return address into calculate0x7fffffffe0c8
5push rbp (in add)saves calculate's frame pointer0x7fffffffe0c0
6pop rbp (end of add)restores calculate's frame pointer0x7fffffffe0c8
7retpops the return address and jumps to it0x7fffffffe0d0

Step through the same seven rows below. Each row of the drawing is one 8-byte slot, and after step 6 keep an eye on the slots that fade out.

main → calculate → add

Step 0 of 7
main is about to call calculate
rsp = 0x7fffffffe0f0
0x7fffffffe0f0main's frame← rsp
0x7fffffffe0e8·
0x7fffffffe0e0·
0x7fffffffe0d8·
0x7fffffffe0d0·
0x7fffffffe0c8·
0x7fffffffe0c0·

Higher addresses at the top. Each row is one 8-byte slot. Faded rows sit below rsp: popped, but not erased.

Every push takes 8 bytes off rsp, and every pop gives 8 back. By step 7, rsp sits exactly where it did after step 3, and calculate carries on as if add had never happened. Nothing was erased, though. The bytes add left behind are still in memory below rsp, waiting to be overwritten by the next call. That's why reading an uninitialised local variable in C often gives you a value left over from some earlier function.

The push rbp steps are there because this build keeps frame pointers. Switch optimisation on and GCC and Clang turn on -fomit-frame-pointer from -O1 upwards, so rbp becomes an ordinary register and locals are addressed straight off rsp. Your table would lose steps 2 and 5 and a pop at each exit.

You might notice add never subtracted anything from rsp. On x86-64 Linux, a function that calls nothing else may use the 128 bytes just below rsp (the red zone) without reserving them, because nothing else will push there while it runs. It's a small saving, and compilers take it.

C won't show you rsp, but it will show you where locals end up. Each function below prints the address of one of its own variables:

Try itAdd a fourth function that add() calls and predict its address before you run it.
C (GCC 9.2.0)

Every callee's local sits at a lower address than its caller's, so the stack is growing downwards. Then, when main calls add() directly, add's local lands at (or very near) the address calculate's had. That frame was popped, and the space simply gets reused.

Limitations

The stack has a fixed maximum size, typically 1 to 8 MB, set when the thread is created. On Linux, ulimit -s shows the main thread's limit, usually 8,192 KB. Nest too many function calls or shove too much local data on, and you hit a stack overflow. It's one of the most famous errors in programming, and the classic culprit is a recursive function with no base case (or a base case that never triggers).

Predict: a recursive function has a 1 KB local array. With an 8 MB stack, roughly how deep can the recursion go?

Around 8,000 calls. Each frame needs the 1,024-byte array plus the return address, saved rbp and some alignment padding, so a little over 1 KB. 8 MB divided by that is just under 8,192. The exact number depends on what the compiler adds to each frame, but the order of magnitude is what matters: a deep recursion with big locals runs out of stack long before it runs out of RAM.

Check the sum for yourself. This recurses 1,000 calls deep with a 1 KB array in every frame and measures how far the stack moved:

Try itSet DEPTH to 100000 and run it again.
C (GCC 9.2.0)

Expect a little over 1,024 bytes per frame. Push DEPTH to 100000 and you're asking for around 100 MB of stack, far more than the runner allows, so the run ends in a segmentation fault (SIGSEGV) well before the last call.