How does the stack work in assembly language?

bplus picture bplus · Feb 17, 2009 · Viewed 117.8k times · Source

I'm currently trying to understand how the stack works, so I've decided teach myself some assembly language, I'm using this book:

http://savannah.nongnu.org/projects/pgubook/

I'm using Gas and doing my development on Linux Mint.

I'm a bit confused by something:

As far as I was aware a stack is simply a data structure. So I assumed if I was coding in assembly I'd have to implement the stack myself. However this doesn't seem to be the case as there are commands like

pushl
popl

So when coding in assembly for the x86 architecture and using the Gas syntax: is the stack just a data structure that's already implemented? Or is it actually implemented at the hardware level? Or is it something else? Also would most assembly languages for other chip sets have the stack already implemented?

I know this is a bit of a foolish question but I'm actually quite confused by this.

Answer

Henry B picture Henry B · Feb 17, 2009

I think primarily you're getting confused between a program's stack and any old stack.

A Stack

Is an abstract data structure which consists of information in a Last In First Out system. You put arbitrary objects onto the stack and then you take them off again, much like an in/out tray, the top item is always the one that is taken off and you always put on to the top.

A Programs Stack

Is a stack, it's a section of memory that is used during execution, it generally has a static size per program and frequently used to store function parameters. You push the parameters onto the stack when you call a function and the function either address the stack directly or pops off the variables from the stack.

A programs stack isn't generally hardware (though it's kept in memory so it can be argued as such), but the Stack Pointer which points to a current area of the Stack is generally a CPU register. This makes it a bit more flexible than a LIFO stack as you can change the point at which the stack is addressing.

You should read and make sure you understand the wikipedia article as it gives a good description of the Hardware Stack which is what you are dealing with.

There is also this tutorial which explains the stack in terms of the old 16bit registers but could be helpful and another one specifically about the stack.

From Nils Pipenbrinck:

It's worthy of note that some processors do not implement all of the instructions for accessing and manipulating the stack (push, pop, stack pointer, etc) but the x86 does because of it's frequency of use. In these situations if you wanted a stack you would have to implement it yourself (some MIPS and some ARM processors are created without stacks).

For example, in MIPs a push instruction would be implemented like:

addi $sp, $sp, -4  # Decrement stack pointer by 4  
sw   $t0, ($sp)   # Save $t0 to stack  

and a Pop instruction would look like:

lw   $t0, ($sp)   # Copy from stack to $t0  
addi $sp, $sp, 4   # Increment stack pointer by 4