Machine Level Stacks

COMP124 Lectures 2021-02-24

A stack is a memory arrangement for storing and retrieving information. The order of storing an retrieving values from the stack can be described as LIFO (last in first out).

The alternative would be a queue which is FIFO.

Operations

The operations on stacks are push and pop.

• Pushing a will push the contents of a to the stack.
• Popping a will pop the top data from the stack and load it into a.

Machine Level Stacks

PUSH and POP instructions make used of the stack pointer register ESP. This holds the address of the item which is currently on top of the stack.

In x86 architecture the stack goes down in memory.

PUSH and POP

The push instruction:

• Decrements the address in ESP so that it points to a free space on the stack.
• Writes an item to the memory location pointed to by the ESP.

The POP instruction:

• Fetches the item addressed by the ESP.
• Increments the ESP by the correct amount to remove the item from the stack.

It is the programmers responsibility to ensure that items are not left on the stack when no longer needed.

The Stack in Memory

The stack grows downwards in memory and the program is stored upwards in memory.

In this diagram:

• ESP - Stack pointer
• EIP - Instruction pointer

The locations increase by 4-bytes each time due to the 32-bit word length.

Adjusting the Stack

Items can also be removed from the stack, or space reserved on top of the stack, by directly altering the stack pointer:

	add esp, 8	; take 8 bytes off the stack
	
	sub esp, 256	; create 256 bytes of space on stack