CSE Roadmap

Core tier · about 4 hours · 7 parts

Part 2 of 7 · 2 min read

Stack frames

In plain words: A stack of plates in a canteen has one rule: the last plate put on is the first one taken off. A function call works the same way. When a function is called, it gets a stack frame, a block at the top of the stack that holds its return address (where to continue after the call), the saved registers it must restore, and its local variables. When the function returns, the frame is dropped by moving the top of the stack back. The analogy stops in one place: the frames are not separate objects. They are consecutive bytes, and the only record of the "top" is one register, the stack pointer.

On x86-64 the stack grows toward lower addresses. The program below prints the address of a local variable in each of four nested calls:

static void f(int n){ int local=n;
  printf("depth %d: local at %p\n", n, (void*)&local);
  if(n<3) f(n+1); }
Depth Address of local Difference from the previous call
0 0x7ffdc95038a4
1 0x7ffdc9503874 48 bytes lower
2 0x7ffdc9503844 48 bytes lower
3 0x7ffdc9503814 48 bytes lower

Each call used 48 bytes of stack, with no optimisation (-O0). The size of a frame depends on the function and on the compiler. The cost of a call is small, since allocating a frame is one subtraction from the stack pointer, and freeing it is one addition. This is why a local variable is the cheapest memory in C. It is also why the memory of a frame must not be used after the function returns: the next call will overwrite it.

Stack frame

A stack frame is the block of stack memory that one function call uses, holding its return address, saved registers and local variables, which is created when the function is called and dropped when it returns.

Example: each call of f above used a frame of 48 bytes, so the stack pointer moved 48 bytes lower with every call.

Check yourself: 1. Which way does the stack grow on x86-64? 2. What does a frame hold? 3. Why is it wrong to return the address of a local variable?