Understanding the Stack

In computer science, a stack is a data structure that follows the Last In, First Out (LIFO) principle. It is linear data structure.

Imagine a stack of plates in a cafeteria; you can only add or remove plates from the top of the stack. Similarly, in a programming context, a stack is a collection of elements where insertion and deletion occur at the same end, known as the top of the stack.

How Does a Stack Work?

1. Push: When you add an item to the stack, it's placed on top of the existing items. This operation is called “push.”
2. Pop: When you remove an item from the stack, the item on top is removed first. This operation is called “pop.”

Key Characteristics of Stacks:

• LIFO Principle: The last item added to the stack is the first one to be removed.
• Fixed Size or Dynamic: Depending on the implementation, a stack can have a fixed size or dynamically grow and shrink as needed.
• Access Limited to Top: Access to stack elements is typically limited to the top of the stack.

Stack in x86

The stack is an integral part of the x86 architecture. The x86 architecture provides hardware support for stack operations through dedicated stack-related instructions and registers.

In x86 Assembly, the stack is a region of memory used to store temporary data, such as function parameters and local variables during program execution.

• In x86 architecture the stack grows downwards.

Memory Layout:

• In x86 architecture, memory addresses start from 0x00000000 and go up to 0xFFFFFFFF (In a 32-bit system).
• The stack grows downward in memory, starting from the higher memory addresses and moving towards lower memory addresses.

Stack Pointer (*SP):

• It a special-purpose register that holds the memory address of the top of the stack.
• As data is pushed onto the stack, the value of the SP (Stack Pointer) decreases.

Higher Memory Addresses
         |-----------------|
         |  First Item     | <--- Base Pointer (BP)
         |-----------------|
         |  . . .          |
         |-----------------|
         |  Next Item      |
         |-----------------|
         |  Last Item      | <--- Stack Pointer (SP)
         |-----------------|
Lower Memory Addresses

As data is pushed onto the stack, the stack pointer (ESP) decrements, moving towards lower memory addresses.
The last item pushed onto the stack is at the top, and the first item pushed onto the stack is at the bottom.

Base Pointer:

• Base Pointer points to the base of the current stack in memory. The stack frame is a region of memory allocated for a function's local variables, parameters, return address.
• It provides a fixed reference point within the stack frame.

What is a Stack Frame?

A stack frame, also known as an activation record, is a data structure used to store information about a function or subroutine call. When a function is called, a new stack frame is created on the call stack to hold information such as the function's parameters, local variables, return address, and the state of the calling function.

1. Return Address:
   1. The address in memory to which the control should return after the function call is complete.
2. Parameters:
   1. Values passed to the function as arguments.
3. Local Variables:
   1. Variables declared within the function.
4. Saved Registers:
   1. Registers that need to be preserved across function calls.
5. Frame Pointer (Optional):
   1. A pointer that points to the base of the current stack frame.

Why does the stack grow downwards?

The reason that the stack grows downwards is probably historical. When the computers were big and occupied a whole room, it was easy to divide memory into two parts, one for the heap and one for the stack. Of course, it was unknown how big the heap and the stack would be during program execution, so this solution was the simplest possible.

Structure of a Stack Frame (x86 Assembly):

; Function prologue
push ebp            ; Save base pointer
mov ebp, esp        ; Set base pointer to current stack pointer
sub esp, <size>     ; Allocate space for local variables

; Function epilogue
mov esp, ebp        ; Restore stack pointer
pop ebp             ; Restore base pointer
ret                 ; Return from function

Explanation:

1. Function Prologue:
   1. push ebp: Save the current base pointer onto the stack. This instruction pushes the value of base pointer (EBP) onto the stack. This is done to save the previous base value, which will be restored later in the epilogue.
   2. mov ebp, esp: Set the base pointer to the current stack pointer, establishing a new stack frame. Here, the current stack pointer (ESP) is copied into the base pointer (EBP). This establishes a new base pointer for the function, allowing easy access to function parameters and local variables relative to this new frame of reference.
   3. sub esp, <size>: Allocate space on the stack for local variables. <size> represents the total size needed for local variables. size is in bytes. This instruction adjusts the stack pointer to allocate space for local variables. <size> represents the total size needed for local variables. By subtracting this value from ESP, the stack grows downwards to make room for the function's local data.
2. Function Epilogue:
   1. mov esp, ebp: Restore the stack pointer to the base pointer, deallocating the space reserved for local variables. This instruction moves the base pointer (ebp) back into the stack pointer (esp). By doing this, the stack pointer is set back to its original position before this function was called. This action effectively deallocated the space allocated for local variables and parameters on the stack.
   2. pop ebp: Restore the previous base pointer. After moving the stack pointer back to its original position, the previous base pointer (ebp) is restored. This is achieved by popping the value from the stack into the ebp register.
   3. ret: Return from the function, popping the return address from the stack and jumping to that address.

Prologue: The prologue of a function in assembly language is the set of instructions executed at the beginning of the function. It typically performs tasks such as setting up the function's stack frame and saving any necessary register values.

• It is executed at the beginning of a function.
• Its main purpose is to setup the function's environment before its main body of code executed.

1. Save the Previous Frame Pointer (EBP): The first step in the function prologue is to save the value of the previous frame pointer (EBP). This is important because it allows the function to access the calling function’s stack frame later. This is typically done by pushing the value of EBP onto the stack. push ebp ; Save the previous frame pointer
2. Set up the New Frame Pointer (EBP): After saving the previous EBP, the next step is to set up the new frame pointer (EBP) to point to the current stack frame. This is typically done by moving the value of the stack pointer (ESP) into the base pointer (EBP) register. mov ebp, esp ; Set up the new frame pointer
3. Allocate Space for Local Variables: Once the frame pointer is set up, the function needs to allocate space on the stack for its local variables. This is done by subtracting the total size of local variables from the stack pointer. sub esp, 16  ; Allocate space for 16 bytes of local variables

There is an  equivalent instruction for this:

• enter instruction: Sets up a stack frame for a procedure.
  • Syntax: enter <stack_size>, <nesting_level>
  • Example: enter 8, 0
  • Explanation:
    • The enter instruction is used to set up a stack frame at the beginning of a procedure.
    • It allocates space on the stack for local variables and sets up the base pointer (ebp) for accessing these variables.
• leave instruction: Cleans up the stack frame of a procedure.
  • Syntax: leave
  • Example: leave
  • Explanation:
    • The leave instruction is used to clean up the stack frame at the end of a procedure.
    • It restores the stack pointer (esp) and base pointer (ebp) to their values before the procedure was called.

Epilogue: The epilogue of a function is responsible for cleaning up the stack and restoring the previous state before returning control to the calling function.

• It is a set of instructions that are executed at the end of a function.
• Its main purpose is to clean up the function's environment and prepare for its return to the calling function.

1. Restore the Stack Pointer (ESP): The first step in the function epilogue is to restore the stack pointer (ESP) to its original value before the function is called. This is typically done by moving the value of the base pointer (EBP) into the stack pointer.  mov esp, ebp   ; Restore the stack pointer
2. Restore the Previous Frame Pointer (EBP): After restoring the stack pointer, the next step is to restore the previous frame pointer (EBP). This is typically done by popping the value from the stack back into the EBP register. pop ebp  ; Restore the previous frame pointer
3. Additional Cleanup or Operations: Depending on the specific requirements of the function, there may be additional cleanup steps or other operations in the epilogue. This could include restoring registers, handling return values, or performing other cleanup tasks. mov eax, 0 ; Set return values to 0
   This function's return (if any) is typically stored in the appropriate register, such as EAX for integer return values.

Push and Pop Instruction

push Instruction

This instruction is used to add data onto the stack.

Syntax:

push <value>

Example:push eax

This instruction pushes the value of the specified register or memory location onto the top of the stack. It decreases the stack pointer (esp) by the size of the data being pushed and then copies the data onto the stack.

pop Instruction

This instruction removes data from the stack.

Syntax:

pop <destination>

Example: pop ebx

his instruction pops the top value from the stack and stores it in the specified register or memory location. It increases the stack pointer (esp) by the size of the data being popped.