Where the top of the stack is on x86

February 4th, 2011 at 7:24 am

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 [1].

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.

http://eli.thegreenplace.net/wp-content/uploads/2011/02/plates.png

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:

http://eli.thegreenplace.net/wp-content/uploads/2011/02/stack1.png

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 [2]. 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 and popping 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:

http://eli.thegreenplace.net/wp-content/uploads/2011/02/stack2.png

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 [3]. 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:

http://eli.thegreenplace.net/wp-content/uploads/2011/02/stack3.png

Similarly, the pop instruction takes a value off the top of stack and places it in its operand, increasing the stack pointer afterwards. In other words, this:

pop eax

Is equivalent to this:

mov eax, [esp]
add esp, 4

So, again, taking the previous diagram (after the push) as a starting point, pop eax will do the following:

http://eli.thegreenplace.net/wp-content/uploads/2011/02/stack4.png

And the value 0xDEADBEEF will be written into eax. Note that 0xDEADBEEF also stays at address 0x9080ABC8, since we did nothing to overwrite it yet.

Stack frames and calling conventions

When looking at assembly code generated from C, you will find a lot of interesting patterns. Perhaps the most recognizable pattern is the way parameters are passed into functions using the stack, and the way local variables are allocated on the stack [4].

I’ll demonstrate this with a simple C program:

int foobar(int a, int b, int c)
{
    int xx = a + 2;
    int yy = b + 3;
    int zz = c + 4;
    int sum = xx + yy + zz;

    return xx * yy * zz + sum;
}

int main()
{
    return foobar(77, 88, 99);
}

Both the arguments passed into foobar and the local variables of that function, along with some other data, are going to be stored on the stack when foobar is called. This set of data on the stack is called a frame for this function. Right before the return statement, the stack frame for foobar looks like this:

http://eli.thegreenplace.net/wp-content/uploads/2011/02/stackframe1.png

The green data were pushed onto the stack by the calling function, and the blue ones by foobar itself.

Compiled with gcc into assembly as follows:

gcc -masm=intel -S z.c -o z.s

The following assembly listing is generated for foobar. I commented it heavily for easy understanding:

_foobar:
    ; ebp must be preserved across calls. Since
    ; this function modifies it, it must be
    ; saved.
    ;
    push    ebp

    ; From now on, ebp points to the current stack
    ; frame of the function
    ;
    mov     ebp, esp

    ; Make space on the stack for local variables
    ;
    sub     esp, 16

    ; eax <-- a. eax += 2. then store eax in xx
    ;
    mov     eax, DWORD PTR [ebp+8]
    add     eax, 2
    mov     DWORD PTR [ebp-4], eax

    ; eax <-- b. eax += 3. then store eax in yy
    ;
    mov     eax, DWORD PTR [ebp+12]
    add     eax, 3
    mov     DWORD PTR [ebp-8], eax

    ; eax <-- c. eax += 4. then store eax in zz
    ;
    mov     eax, DWORD PTR [ebp+16]
    add     eax, 4
    mov     DWORD PTR [ebp-12], eax

    ; add xx + yy + zz and store it in sum
    ;
    mov     eax, DWORD PTR [ebp-8]
    mov     edx, DWORD PTR [ebp-4]
    lea     eax, [edx+eax]
    add     eax, DWORD PTR [ebp-12]
    mov     DWORD PTR [ebp-16], eax

    ; Compute final result into eax, which
    ; stays there until return
    ;
    mov     eax, DWORD PTR [ebp-4]
    imul    eax, DWORD PTR [ebp-8]
    imul    eax, DWORD PTR [ebp-12]
    add     eax, DWORD PTR [ebp-16]

    ; The leave instruction here is equivalent to:
    ;
    ;   mov esp, ebp
    ;   pop ebp
    ;
    ; Which cleans the allocated locals and restores
    ; ebp.
    ;
    leave
    ret

Since esp keeps moving as the function executes, ebp (base pointer, also known as frame pointer in other architectures) is used as a convenient anchor relatively to which all function arguments and locals can be found. Arguments are above ebp in the stack (hence the positive offset when accessing them), while locals are below ebp in the stack.

http://eli.thegreenplace.net/wp-content/uploads/hline.jpg
[1] 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.
[2] 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.
[3] There are several instructions x86 defines in the "push family". I’m demonstrating push since it’s the simplest and most generally applicable.
[4] This only applies to some calling conventions and architectures, of course. In others, some parameters are passed in registers.

Related posts:

  1. Stack frame layout on x86-64
  2. Position Independent Code (PIC) in shared libraries on x64
  3. when bit endianness matters
  4. Position Independent Code (PIC) in shared libraries
  5. Load-time relocation of shared libraries

30 Responses to “Where the top of the stack is on x86”

  1. Iouri GoussevNo Gravatar Says:

    Thanks, I love learning how software works at low-level.

  2. Michael AyeNo Gravatar Says:

    As this is published on Planet Python, why not put a nice example in here how to simulate a stack with a list? Not sure what the agreement officially is, but I was just a bit puzzled to find a post on the Planet Python feed that not once mentions Python.
    Otherwise, good information, thanks!

  3. elibenNo Gravatar Says:

    Michael,

    I also don’t know what the “agreement” officially is with Planet Python, but there are quite a few non-Python related articles out there. For my blog, I think they’re aggregating the programming category which includes Python, but also my other posts on programming. I’m sorry if it disturbs you.

  4. Kent JohnsonNo Gravatar Says:

    This is not special to x86, this is the way the stack works on every architecture I am familiar with.

  5. Joe BrandtNo Gravatar Says:

    Things get more interesting if you add some erroneous code:

    memset(&y, 0, sizeof(y) * 4); // zeros 16 bytes

    What happens? Well y is zeroed, but the value of x, the stored ebp and return address are also trashed. This is the source of many bugs and security exploits.
    So its important to note that although the stack grows toward low addresses, arrays and their elements go from low to high addresses.

  6. elibenNo Gravatar Says:

    Kent,

    I agree. I was focusing on x86 here but the same may be said about many other architectures.

    Joe,

    Indeed, and not terminating local buffers properly will allow attackers to overwrite the function return address, jumping to their malicious code. Regarding the extra notice, this article assumes some non-basic level of programming understanding. I’m hope understanding where array indices grow is included in that understanding :-)

  7. IgnatiusNo Gravatar Says:

    This subject material should be familiar with someone who went through a formalized computer science core in the ’90s, however that being said, it seems many young developers have come from other fields, or the approach to CS has changed such that these fundamentals are no longer favored.

    The care and attention to detail so common throughout your articles, displayed in your use of informative illustrations, code snippets and generously sprinkled with warnings of common pitfalls/misconceptions, is a service to the community. Further, I can not detect ego or hubris, but only a desire to share with others your hard won information, for this I wanted to express my thanks.

  8. Eversor1No Gravatar Says:

    Your article admits that the association “may be confusing to some people”. I suggest that it may be confusing to all people because the words top and bottom do not correctly explain what they are representing in your explanation, and are frankly misused. Instead of trying to alter the dictionary definition of “top” and “bottom” why not just change the terminology as applied to the stack? This seems to be a simple enough solution. Your pushes and pops affect the bottom of the stack.

  9. elibenNo Gravatar Says:

    Ignatius,

    Thanks for the kind words :-)

    Eversor1,

    The dictionary is hardly relevant here. Wishful thinking about changing the terminology as applied to the stack can be a pleasant thought exercise, but in the end of the day you open Intel’s x86 programmer’s manual, and read on the push instruction (emphasis is mine):

    Decrements the stack pointer and then stores the source operand on the top of the stack.

    My intention in this article is just to clarify things and I freely admit there’s a confusion in the terminology.

  10. JasonNo Gravatar Says:

    Thank you. I don’t have a formal programming education and my head has always hurt when working in languages where I have to manipulate data on the stack directly. You’re elegant post has set my head straight (upside down) and I can now fully visualize what is happening and suspect I won’t have future headaches. Thank you again!

  11. jkNo Gravatar Says:

    Great article! :-)

    Eversor1:

    I think its all about perspective anyway. For example, I think of memory in the opposite way that is illustrated here such that the lower addresses are shown at the top of the page (rotate these diagrams 180 degrees). In this case the “high” and “low” refers to the numbering of the addresses and not their position on the page. This is how disassemblers typically show sections of memory as well. Conveniently, this view also makes the whole top and bottom thing intuitive.

  12. Phil MayesNo Gravatar Says:

    “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.”

    But every core dump ever printed was in this format. After a while, you become directionally agnostic (bidirectional??).

  13. Nicolas DumazetNo Gravatar Says:

    Amazing, I came here from Planet Python, and I’m happy that some “off-topic” non-Python posts pop up from time to time. I wasn’t educated in the 90′s, but it has been at least 5 years since I last worked with some registers. It’s good to freshen up a bit!

  14. frankNo Gravatar Says:

    Thanks a lot i never understand in deep the stack.. so thanks a lot
    LUC

  15. frankNo Gravatar Says:

    ehm.. as Phil Mayes wrote seems that there is a error..about high address and low address in the last diagram? is it? then where is located the return foobar? is it located at EBP+4(return adress)?
    regards
    Luc

  16. le kommieNo Gravatar Says:

    When compiling the example on 64-bit Linux (GCC: (Ubuntu/Linaro 4.5.2-8ubuntu4) 4.5.2″), use the following command line to compile into assembler:

    gcc -masm=intel -march=i386 -m32 -S z.c -o z.m

    Not using -march and -m32 will produce a completely different output.

  17. elibenNo Gravatar Says:

    le kommie,

    Good point. I was compiling this on a 32-bit Ubuntu. To compile 32-bit objects on 64-bit Ubuntu, indeed some special flags have to be passed.

  18. candidoNo Gravatar Says:

    Hi,

    a very good webblog. I am primer with C and assembly programming, level of these 3 references ( –C programming: a Modern Aproach, –A Computer System: A programmers perspective, –Introduction to Computer Organizationwith x86-64 Assembly language & GNU/Linux) and for stack research I just begin studing with the topic: shellcode injected in stack of a vulnerable program STACK OVERWRITING and the problem is that i am searching for a good book or reference about this topic and i have not had succeeded. The reference Shellcode Handbook is out of date and today SO have a lot of security ( stack bound check, canarys, non executable, stack, etc ….), so for a track of book examples I need updated it and me conclusion is that i need today linux kernel security concepts background. I can see that you are expert on unix environment, so, I would like know some update reference about that. My plaform is linux/GNU, ubuntu10.04 distribution 32 bits arch and toolbox (GNU emacs, gcc 4.4.3, gdb 6.8)

    Thanks in advance
    Cándido Aramburu
    Universidad Publica de Navarra
    candido@unavarra.es

  19. elibenNo Gravatar Says:

    candido,

    I’m not familiar with books on this topic

  20. MattNo Gravatar Says:

    Just wanted to say thanks. Your straightforward explanation cleared up a lot of my confusion regarding the stack frame. It has been an excellent supplement to my OS class.

  21. vaibhavNo Gravatar Says:

    Thanks a lot for such a wonderful article :)
    Keep writing!

  22. SreeNo Gravatar Says:

    ‘Can anyone tell me how to find the starting address of stack and heap?’
    ‘Also i want information about how to find where the stack and heap overlaps?’

  23. geek42No Gravatar Says:

    1, the stack concept are explained brief in CSAPP( i read the CSAPP2e)

    2, the order is follow the endian order , this might be the keypoint, but the enture of position of BOS might could limit the memory usage, just a personal opinion

  24. LeonNo Gravatar Says:

    Just use diagrams that have lower addresses on the top and the whole article becomes obsolete.

  25. elibenNo Gravatar Says:

    Leon,

    And yet, many resources prefer to keep the “top” actually on top. If you draw the low addresses on top, then the concept of “above” and “below” becomes inverted and confusing.

    Let’s say I want to describe where locals are. I say “they are below ebp”. With the diagrams as shown in this post, this makes sense visually. Invert them, though, and it will stop making sense.

    So things are not so simple, I think.

  26. NimeshNo Gravatar Says:

    Thanks! This site is the best.

  27. jucestainNo Gravatar Says:

    Great article; great website! Appreciate the time and effort you spent writing these up.

  28. Dongseon LeeNo Gravatar Says:

    Thanks a lot. I havn’t found any information about the stack structure except your article. It’s great and precise.

  29. KotNo Gravatar Says:

    In the listing for foobar, shouldn’t it be

    push %ebp
    mov %esp, %ebp

    ?

    and restore esp from epb, and pop ebp at the end?

  30. KotNo Gravatar Says:

    Sorry missed that you were using intel syntax here…

Leave a Reply

To post code with preserved formatting, enclose it in `backticks` (even multiple lines)