Stack architecture demystified
Written by Eli Bendersky   
Monday, 28 February 2011
Article Index
Stack architecture demystified
Stack frames and calling conventions

 

Eli Bendersky resolves the confusion over stack architecture with the help of some diagrams. He focuses on the Intel x86 but it equally applicable to other architectures.

Where the top of the stack is on x86

I’ve noticed more than once that some programmers are confused about the direction in which the stack grows on x86, and what "top of the stack" and "bottom of the stack" mean. It appears that this confusion is caused by a basic mismatch in the way people are used to thinking about stacks, and in the way the stack on x86 actually behaves. It doesn’t help that some online resources mistakenly call the top of the stack "bottom". The version presented here is the correct one of x86, since it relies on terminology defined in Intel’s x86 architecture manuals.

In this article, I intend to resolve this confusion with a few helpful diagrams.

The stack analogy

Back to the basics. The stack analogy is sometimes demonstrated to new students of computing with a stack of plates. You push a plate onto the stack and pop a plate off the stack. The top of the stack is where your next plate goes when pushing, and from where you take a plate when popping.

Hardware stacks

In computers, the stack is usually a specially treated region of memory. In the abstract sense, the analogy applies – you push data by placing it on the top of the stack, and pop data by taking it from the top of the stack. Note that this doesn’t address the issue of where the top of the stack is located in memory.

The stack in x86

Herein lies the source of the confusion. Intel’s x86 architecture places its stack "head down". It starts at some address and grows down to a lower address. Here’s how it looks:

stack1

 

 

So when we say "top of the stack" on x86, we actually mean the lowest address in the memory area occupied by the stack. This may be unnatural for some people. (You may try to fix the confusion by viewing memory with its low addresses at the top and high addresses at the bottom. While this would indeed make stack movement more natural, it would also mean that increasing some memory address would take it down in the graphical representation, which is probably even more counter-intuitive.) As long as we keep the diagram shown above firmly in mind, however, we should be OK.

While we’re at it, let’s see how some common idioms of x86 assembly programming map to this graphical representation.

Pushing data with the stack pointer

The x86 architecture reserves a special register for working with the stack – ESP (Extended Stack Pointer). The ESP, by definition, always points to the top of the stack:

stack2

In this diagram, address 0x9080ABCC is the top of the stack. The word located in it is some "foo" and ESP contains the address 0x9080ABCC – in other words, points to it.

To push new data onto the stack we use the push instruction - note there are several instructions x86 defines in the "push family". I’m demonstrating push since it’s the simplest and most generally applicable.  What push does is first decrement esp by 4, and then store its operand in the location esp points to. So this:

push eax

is actually equivalent to this:

sub esp, 4
mov [esp], eax

Taking the previous diagram as the starting point, and supposing that eax held the venerable value 0xDEADBEEF, after the push the stack will look as follows:

stack3



Last Updated ( Monday, 28 February 2011 )