The Stack and Calling Conventions

A function can be called from many places. A print function might be called a thousand times from all over a program, and each time it has to return to the right spot. Functions also call other functions, which call others in turn, and a function can even call itself. Every one of those calls needs somewhere to remember its way back and to keep its own working values, and the newest call is always the first to finish. That's exactly what a stack is good at.

The stack

A stack is like a pile of plates: you can only put a plate on top, or take the top one off. The last one put on is the first one taken off. In a computer, the stack is simply an area of memory, plus a register that points at the value on top: the stack pointer, rsp on x86-64 and sp on RISC-V.

One detail surprises everyone: on x86 and RISC-V, the stack grows downwards. Putting a value on the stack, a push, first moves the stack pointer down by 8 bytes and then writes the value there. Taking it off, a pop, reads the value and moves the stack pointer back up.

Every thread gets its own stack. On Linux, the main thread's stack starts small and grows when needed, up to a limit, which on the computer this book was written on is 8 MB.

Call and return

The x86 call instruction does two things: it pushes the return address, the address of the instruction right after the call, and then jumps to the function. When the function is done, ret pops that address off the stack and jumps back to it. Because each call pushes its own return address, calls can nest as deep as you like, and they always unwind in the right order.

RISC-V does it a little differently. Its jal ("jump and link") instruction puts the return address in a register, ra, instead of on the stack, and ret jumps to whatever address ra holds. That's faster, because it doesn't touch memory. But a function that calls another function must first save its own ra on the stack, or the inner call would overwrite it.

Calling conventions

When one function calls another, they need to agree on the details. Which registers hold the arguments? Where does the result go? Which registers may the called function change, and which must it leave as it found them? This agreement is called a calling convention, and it's part of the ABI (application binary interface): the rules that let code compiled by different compilers, even from different languages, work together. A Rust program can call a C library, and Python can call both, because they all follow the same convention.

                       x86-64 Linux, macOS       RISC-V
arguments 1 to 6       rdi rsi rdx rcx r8 r9     a0 a1 a2 a3 a4 a5 (a6 a7)
more arguments         on the stack              on the stack
result                 rax                       a0
return address         on the stack              ra
callee-saved           rbx rbp r12–r15           s0–s11, sp
                       (a function must put these back as they were)
caller-saved           everything else           t0–t6, a0–a7, ra
                       (a function may change these freely)

Callee-saved registers are a promise: if a function wants to use rbx, it must save the old value first (usually on the stack) and restore it before returning. Caller-saved registers carry no promise: if the caller needs a value in rcx to survive a call, it has to save it itself. Splitting the registers this way means that most small functions never need to save anything at all.

The convention also says the stack pointer must be a multiple of 16 when a call is made, so that the fast instructions that move 16 bytes at a time always find their data neatly lined up. Conventions differ between systems: 64-bit Windows passes the first four arguments in rcx, rdx, r8 and r9 instead. Code built for one won't work with the other without help.

Stack frames and recursion

The part of the stack that belongs to one call is its stack frame: its return address, any registers it had to save, and its local variables. When the function returns, its frame is simply abandoned by moving the stack pointer back up. That's why local variables disappear when a function ends: their memory is reused by the next call.

Because each call gets a fresh frame, a function can safely call itself. This is recursion. The factorial of a number, n! = n × (n − 1) × … × 1, is the classic example: fact(n) = n × fact(n − 1), with fact(1) = 1. Each call waits, with its own n saved on the stack, while the call below it works out its part:

Many compilers also give each frame a fixed reference point, the frame pointer (rbp on x86-64, s0 on RISC-V), so that local variables can be found at fixed distances from it while the stack pointer moves. Debuggers follow the chain of frames to show you which functions called which.

When the stack goes wrong

The stack has a limit. A recursion that never stops keeps pushing frames until the stack runs out. Below the stack, the kernel leaves an unmapped guard page (Chapter 10), so the next push causes a page fault, and the program is ended with a "Segmentation fault". This is a stack overflow, the error that gave a famous programmers' website its name.

A worse problem is a buffer overflow. Local variables sit in the stack frame right next to the saved registers and the return address. If a program copies data into a local array without checking its size, the extra bytes run past the end of the array and overwrite whatever is next. When the function returns, it jumps to wherever the overwritten return address says. In 1988 the Morris worm, one of the first programs to spread across the internet, got into computers exactly this way.

Today's systems defend themselves in several layers:

• Stack canaries: the compiler puts a secret value between the local variables and the return address, and checks it before returning. Ubuntu's compiler does this by default.
• Non-executable stacks: the page tables mark the stack as data only (Chapter 10), so bytes written there can't be run as instructions.
• Address randomisation (ASLR): the stack, libraries and program are placed at different random addresses every time, so an attacker can't know where to jump.
• Shadow stacks: the processor keeps a second, protected copy of every return address, and stops the program if ret finds that the two don't match. The computer this book was written on supports this, as Intel's CET.

Better still is never writing past the end of an array at all. Newer languages like Rust and Go check every array access, so this whole kind of bug can't happen in ordinary code.

Meanwhile, inside a real CPU

Here's the factorial function from the demo, written by hand in x86-64 assembly, with a _start that asks for fact(5). It follows the Linux calling convention: n arrives in rdi and the answer leaves in rax.

_start:
    mov edi, 5              # compute fact(5)
    call fact
    mov edi, eax            # exit status = the answer
    mov eax, 60
    syscall

fact:                       # n arrives in rdi; the answer goes in rax
    cmp rdi, 1
    jg recurse              # n > 1: work it out
    mov eax, 1              # fact(1) = 1
    ret
recurse:
    push rdi                # save n: the call will need rdi
    dec rdi                 # argument for the call: n - 1
    call fact               # rax = fact(n - 1)
    pop rdi                 # get n back
    imul rax, rdi           # rax = n * fact(n - 1)
    ret

$ as -o fact.o fact.s && ld -o fact fact.o
$ ./fact
$ echo $?
120                                    ← 5 × 4 × 3 × 2 × 1

In the machine code, the inner call is e8 eb ff ff ff: the opcode e8 followed by a distance of −21 bytes, measured from the next instruction back to the start of fact. Here's the RISC-V version, assembled but not run, as we have no RISC-V machine. It saves ra and n in a 16-byte frame it makes for itself:

fact:                       # n arrives in a0; the answer goes in a0
    li   t0, 1
    bgt  a0, t0, recurse    # n > 1: work it out
    li   a0, 1              # fact(1) = 1
    ret
recurse:
    addi sp, sp, -16        # make room for two values on the stack
    sd   ra, 8(sp)          # save our return address
    sd   a0, 0(sp)          # save n
    addi a0, a0, -1         # argument for the call: n - 1
    call fact               # a0 = fact(n - 1)
    ld   t0, 0(sp)          # get n back
    mul  a0, a0, t0         # a0 = n * fact(n - 1)
    ld   ra, 8(sp)          # get our return address back
    addi sp, sp, 16         # give the stack space back
    ret

The debugger gdb can stop a C version of the program at its deepest point and print the backtrace: the chain of calls in progress, read straight from the stack frames. Each frame of this unoptimised C version takes 32 bytes.

$ gdb -batch -ex 'break fact if n==1' -ex run -ex bt ./factm     (trimmed)
#0  fact (n=1) at factm.c:2
#1  0x0000555555555157 in fact (n=2) at factm.c:4
#2  0x0000555555555157 in fact (n=3) at factm.c:4
#3  0x0000555555555157 in fact (n=4) at factm.c:4
#4  0x0000555555555157 in fact (n=5) at factm.c:4
#5  0x0000555555555170 in main () at factm.c:6

Every fact frame shows the same return address, …5157: the instruction just after the recursive call. Next, a function that calls itself forever, with each call using 48 bytes of stack. It crashed after 174,596 calls: 174,596 × 48 bytes is about 8 MB, the stack limit.

$ ulimit -s
8192                                   ← kilobytes: 8 MB
$ ./deep
each call uses 48 bytes of stack
crashed at depth 174596

The C function from the buffer overflow demo, run for real with a 40-letter name. With Ubuntu's default stack protector, the canary catches it; without it, the return address is overwritten and the program crashes:

$ ./smash AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
Hello, AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
*** stack smashing detected ***: terminated
Aborted (core dumped)
$ ./smash-unprotected AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
Hello, AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
Segmentation fault (core dumped)

Finally, address randomisation at work. Three runs of the same command, three different places for the stack:

$ grep stack /proc/self/maps     (three times)
7ffec87b7000-7ffec87d9000 rw-p 00000000 00:00 0      [stack]
7fff1dd5c000-7fff1dd7e000 rw-p 00000000 00:00 0      [stack]
7ffd00f62000-7ffd00f84000 rw-p 00000000 00:00 0      [stack]

Try it yourself

1. RSP is 0x7ffe1000. The program does two pushes and one pop. What's RSP now?
   Show answer

   Two pushes: down 16 bytes, to 0x7ffe0ff0. One pop: up 8, to 0x7ffe0ff8.
2. Why doesn't a RISC-V function that calls no other functions need to save ra on the stack?
   Show answer

   Nothing will overwrite ra while it runs, because only a jal or call changes it. It can return with ret directly, without touching memory at all.
3. Our x86 program computes fact(5). How many bytes of stack are in use when fact(1) is running?
   Show answer

   The call from _start pushes 8 bytes. Each of fact(5), fact(4), fact(3) and fact(2) pushes n and then a return address: 16 bytes each. That's 8 + 4 × 16 = 72 bytes.
4. A function wants to use rbx for its own work. What must it do under the Linux x86-64 convention?
   Show answer

   rbx is callee-saved, so the function must save the old value first (for example with push rbx) and restore it before returning (pop rbx). Its caller expects to find rbx unchanged.
5. With an 8 MB stack and 48 bytes per call, how many calls should fit? We measured 174,596. Why a little fewer?
   Show answer

   8 × 1,048,576 ÷ 48 = 174,762. Some of the stack was already in use before the first call: the program's arguments and environment, and the frames of main and the startup code.

What we learned

• The stack is an area of memory used last-in, first-out; it grows downwards, and the stack pointer marks its top.
• call pushes a return address and ret pops it; RISC-V's jal keeps it in ra, which non-leaf functions must save.
• A calling convention fixes where arguments and results go and which registers each side must preserve, so separately compiled code works together.
• Each call gets a stack frame for its return address, saved registers and local variables, which is what makes recursion work.
• Stack overflows hit a guard page; buffer overflows can overwrite return addresses, so systems add canaries, non-executable stacks, ASLR and shadow stacks.

Writing all of this by hand is slow and error-prone. Next we meet the programs that do it for us: compilers and linkers, which turn a language like C into machine code and stitch the pieces together.