How does the stack work in assembly language?

Question

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 1

The stack already exists, so you can assume that when writing your code. The stack contains the return addresses of the functions, the local variables and the variables which are passed between functions. There are also stack registers such as BP, SP (Stack Pointer) built-in that you can use, hence the built-in commands you have mentioned. If the stack wasn't already implemented, functions couldn't run, and code flow couldn't work.

Answer 2

The stack is "implemented" by means of the stack pointer, which (assuming x86 architecture here) points into the stack segment. Every time something is pushed on the stack (by means of pushl, call, or a similar stack opcode), it is written to the address the stack pointer points to, and the stack pointer decremented (stack is growing downwards, i.e. smaller addresses). When you pop something off the stack (popl, ret), the stack pointer is incremented and the value read off the stack.

In a user-space application, the stack is already set up for you when your application starts. In a kernel-space environment, you have to set up the stack segment and the stack pointer first...

Answer 3

You confuse an abstract stack and the hardware implemented stack. The latter is already implemented.

Answer 4

Regarding whether the stack is implemented in the hardware, this Wikipedia article might help.

Some processors families, such as the x86, have special instructions for manipulating the stack of the currently executing thread. Other processor families, including PowerPC and MIPS, do not have explicit stack support, but instead rely on convention and delegate stack management to the operating system's Application Binary Interface (ABI).

That article and the others it links to might be useful to get a feel for stack usage in processors.

Answer 5

You are correct that a stack is a data structure. Often, data structures (stacks included) you work with are abstract and exist as a representation in memory.

The stack you are working with in this case has a more material existence- it maps directly to real physical registers in the processor. As a data structure, stacks are FILO (first in, last out) structures that ensure data is removed in the reverse order it was entered. See the StackOverflow logo for a visual! ;)

You are working with the instruction stack. This is the stack of actual instructions you are feeding the processor.

Answer 6

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 instructino would look like:

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

Answer 7

I haven't seen the Gas assembler specifically, but in general the stack is "implemented" by maintaining a reference to the location in memory where the top of the stack resides. The memory location is stored in a register, which has different names for different architectures, but can be thought of as the stack pointer register.

The pop and push commands are implemented in most architectures for you by building upon micro instructions. However, some "Educational Architectures" require you implement them your self. Functionally, push would be implemented somewhat like this:

   load the address in the stack pointer register to a gen. purpose register x
   store data y at the location x
   increment stack pointer register by size of y

Also, some architectures store the last used memory address as the Stack Pointer. Some store the next available address.

Answer 8

You are correct that a stack is 'just' a data structure. Here, however, it refers to a hardware implemented stack used for a special purpose --"The Stack".

Many people have commented about hardware implemented stack versus the (software)stack data structure. I would like to add that there are three major stack structure types -

1. A call stack -- Which is the one you are asking about! It stores function parameters and return address etc. Do read Chapter 4 ( All about 4th page i.e. page 53)functions in that book. There is a good explanation.
2. A generic stack Which you might use in your program to do something special...
3. A generic hardware stack
   I am not sure about this, but I remember reading somewhere that there is a general purpose hardware implemented stack available in some architectures. If anyone knows whether this is correct, please do comment.

The first thing to know is the architecture you are programming for, which the book explains (I just looked it up --link). To really understand things, I suggest that you learn about the memory, addressing, registers and architecture of x86 (I assume thats what you are learning --from the book).

Answer 9

The call stack is implemented by the x86 instruction set and the operating system.

Instructions like push and pop adjust the stack pointer while the operating system takes care of allocating memory as the stack grows for each thread.

The fact that the x86 stack "grows down" from higher to lower addresses make this architecture more susceptible to the buffer overflow attack.