The Stack
The Stack & The Heap · Memory & Systems track
6 min read
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.
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.
| Step | Instruction | What it does | rsp afterwards |
|---|---|---|---|
| 1 | call calculate (in main) | pushes the return address into main | 0x7fffffffe0e8 |
| 2 | push rbp (in calculate) | saves main's frame pointer | 0x7fffffffe0e0 |
| 3 | sub rsp, 16 | reserves 16 bytes for calculate's locals | 0x7fffffffe0d0 |
| 4 | call add | pushes the return address into calculate | 0x7fffffffe0c8 |
| 5 | push rbp (in add) | saves calculate's frame pointer | 0x7fffffffe0c0 |
| 6 | pop rbp (end of add) | restores calculate's frame pointer | 0x7fffffffe0c8 |
| 7 | ret | pops the return address and jumps to it | 0x7fffffffe0d0 |
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
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:
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:
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.
Try the Simulations
Stack Push & Pop
Push values onto the stack and pop them off. See how the stack pointer moves and LIFO ordering works.
Function Call & Return
Call a function that doubles a value. See how CALL saves the return address and RET jumps back.
Nested Function Calls
Call a function that calls another function. Watch the stack grow with return addresses as calls nest, then unwind as each function returns.