The last time Hackerfall tried to access this page, it returned a not found error. A cached version of the page is below, or click here to continue anyway

# What is "the stack"? - Julia Evans

Last week I was at Papers We Love, my new favorite meetup. And someone mentioned "the stack" in passing, and I decided to ask -- what is that, really? I talked about it with Julian (who, like many people I know, is the best).

The basic question I want to answer here is -- why do people sometimes discuss "the stack" like it's some kind of revered fundamental object? (the answer is going to turn out to be "because it is", and I'm going to try to make that as concrete as I can.)

### Calling a function

Let's talk about the basics before it gets weird. Suppose you're in a programming language. Any progamming language. Most languages have the concept of a "function" and "calling a function".

Whenever you call a function, you also need to return from that function. So, as a simple example --

``````def elephant(x):
value = panda(x)
return value + 2

def panda(y):
return y * 3
``````

So if we call `elephant(3)`, we're going to call `panda(3)` next, and we need to remember that we were in `elephant` before.

Normally programming languages keep track of this information in a data structure called the call stack, which you can imagine like

``````1) elephant <-- you were here before
2) panda <-- you are here now
``````

### Calling a function in C (and why C is special)

Most languages have some kind of call stack data structure. Python! Ruby! C! Java! But that could be anything, right?

For a long time I've been vaguely confused about this, because I often hear references to "stack smashing" or "stack overflows" or "setting a stack size", like there's a canonical stack that all programs have. And there is a One True Stack!

As in most cases with the One True Anything on Linux, the One True Call Stack is the C call stack.

To understand why, it helps to to look at a C program and what it compiles to. I wrote one for this blog post:

``````#include <stdio.h>

int main() {
blah(3);
printf("Penguin!\n");
}

int blah(int x) {
return x;
}
``````

Pretty simple! When your CPU runs programs, it's ultimately running assembly instructions. Let's look at the assembly instructions for this program:

``````\$ gcc -o hello hello.c
\$ objdump -d hello
address       instructions (binary)   instructions (english)
00000000004004f4 <main>:
4004f4:       55                      push   %rbp
4004f5:       48 89 e5                mov    %rsp,%rbp
4004f8:       bf 03 00 00 00          mov    \$0x3,%edi
4004fd:       e8 0c 00 00 00          callq  40050e <blah>
400502:       bf 0c 06 40 00          mov    \$0x40060c,%edi
400507:       e8 e4 fe ff ff          callq  4003f0 <[emailÂ protected]>
40050c:       5d                      pop    %rbp
40050d:       c3                      retq

000000000040050e <blah>:
40050e:       55                      push   %rbp
40050f:       48 89 e5                mov    %rsp,%rbp
400512:       89 7d fc                mov    %edi,-0x4(%rbp)
400515:       8b 45 fc                mov    -0x4(%rbp),%eax
400518:       5d                      pop    %rbp
400519:       c3                      retq
40051a:       90                      nop
40051b:       90                      nop
40051c:       90                      nop
``````

Delightfully, this is very simple -- all of the assembly code for both these two functions fits on a page!

We have two functions: `main` and `blah`. We're lucky that `blah` is a Very Simple Function: it only has 4 kinds of instructions in it, `push`, `pop`, `mov`, and `retq`. This is where we get into...

### Assembly instructions and The Stack

What does `push %rbp` mean? It means "put the address in %rbp on The Stack". But what does it mean to put something on the Stack-with-a-capital-S?

Well, this is where we get to the very important stack pointer. There's a special register called `%rsp` where, conventionally, an address called the stack pointer is stored.

Imagine that I have a region in memory like this. I've used 64 bit increments because I have a 64-bit processor.

``````address         value
832               4
824               29328323
816               283842
808               128
``````

Now suppose the address in `%rsp` is 808. Then `push 3` would mean "decrement %rsp and put 3 at the next lowest address in memory". So we'd have

``````address          value
832               4
824               29328323
816               283842
808               128
800               3
``````

This means that the `push` and `pop` instructions both make very fundamental assumptions about the memory layout of your program -- that `%rsp` represents an address they can access, and that the memory there is split up into 8 byte (64 bit) chunks that represent the current stack.

Next up, we need to discuss retq and callq. `retq` needs to return to main after the function `blah()` is done running. How does that even work?

Well! When we execute the instruction `callq`, the address `0x00400502` gets pushed onto the stack (where `%rsp` is). Then when we later execute `retq`, it can look in the stack and discover that it needs to go back to the address `0x00400502` to continue program execution. If we changed that address in the stack to be something totally different, the program wouldn't know how to execute anymore! It would do something Very Different.

I found it pretty surprising that the x86 assembly instruction set knows about the C stack pointer and how the stack in C is laid out. Of course, you could invent your own new smart stack format, but you wouldn't be able to use the `callq` and `retq` instructions to call functions.

### Which came first, the chicken or the egg?

I just said that this is the "C stack format", and the assembly assumes that everything is like C. But of course it could be the other away around -- maybe the x86 instruction set came first, with its assumptions about how the One True Stack is organized, and then C conformed to that! And you could write a C compiler that uses a totally different stack format and is incompatible with every other program!

I don't know. Maybe you will tell me which came first -- the compilers that laid out the stack this way, or the instructions! Did all this get decided in the 80s? in the 90s? in the 70s?

In any case, it seems like we're stuck with those choices now. Except!

### What if you wrote your own stack format?

Since we are curious experimenters, we are brought to the obvious question -- what would happen if we wrote our own stack format that was incompatible with the C stack? What if we used the One True Stack Pointer `%rsp` for our own nefarious purposes?

This isn't a theoretical question at all -- Rust actually has a different calling convention from C, which means it sets up its stack differently.

This isn't a super big deal in Rust -- if you want to call a C function from Rust, you can tell the compiler "hey just be normal like C for a bit, okay?". And you can tell it to expose Rust functions like they were C functions. It's fine.

But you do need to be aware of it, if you're a prospective weird-stack-programming-language author or user! For instance! If you want to use gdb with Rust, and you want to get a stack trace ("what function did I call before I called this one?") -- that wouldn't normally work. gdb would not know how to interpret the stack! But Rust implements libbacktrace, which tells GDB how the stack information corresponds to a stack trace.

If you read the README there carefully, you'll notice that Rust's libbacktrace only works with ELF binaries! This means that you can't get Rust stack traces with gdb on OS X or Windows, only in Linux/BSDs/other operating systems that ues ELF binaries. That actually really sucks! There are consequences to having an unusual stack format, and real work you need to do to make the rest of the world understand you.

### fascinating.

I was really surprised that assembly instructions make assumptions about how memory is organized and what information is in which registers. This explains why people talk about The Stack like it's this fundamental data structure instead of just one choice about how you could organize your program. It kind of is!

If you want to more fun things to read, there's a great article Understanding C by learning assembly which discusses using GDB to inspect memory and see exactly what's going on when you run a C program. It's super fun.

There is so much to know! @yrp604 on twitter just told me that on ARM you can choose which direction the stack grows! Whoa.

Thanks to Ouz Kayral, Kamal Marhubi, and Julian Squires for discussing this with me!