The Stack

Don’t get stuck on understanding the stack!

The Stack

In Memory management, the stack (a logical component used by programs to manage temporary data, function calls, and local variables ) is a manifestation of the stack data structure where data is added (pushed) or removed (popped) in a last-in-first-out (LIFO) manner.

During program execution and control, the stack manages the function calls, parameters, local variables, and return addresses of active subroutines (functions) of a program.

It’s important before we boil things down to the stack that we remind ourselves how the memory (RAM) works in general program execution flow (CPU).

The program execution cycle is dependent on two core components: the CPU, for data and instruction processing (Arithmetic, Logic) and the memory (RAM) where the instructions and data are stored. The relationship between the components is straightforward where the the CPU fetches data and instructions from the memory and stores data back after processing.

The processor has registers – small and high-speed storage locations that temporarily hold data, instructions, or addresses. Program execution in the CPU involves the manipulation of general data registers and speccial registers that include RIP (Instruction Pointer), RSP (Stack Pointer), and RBP (Base Pointer), which work in tandem with the stack to manage data, control flow, and return addresses.

So in this article, we’ll explore the stack and the specifics of what happens during a x86-64 bit program function call, how its registers are affected, and how the stack operates as a crucial part of function calls and returns.

Anatomy of a Function Call and The Stack

So an interesting question beckons, how does the memory and registers store these data/instructions for efficient access by the CPU during a program’s execution. The memory is divided into cells –each with a unique address and a cell being an individual storage area for data/instruction.

You might have heard “The stack grows downwards” which refers to the way the stack expands as new data (i.e local variables) are pushed onto it. In most architectures, including x86 and x86_64, the stack starts at a high memory address and grows towards lower memory addresses as new data is added.

When a function is called, several steps occur, including the change in RIP, RSP, and RBP register values, which directly impacts the stack. Here’s an example sequence for calling a function named sub_function in main_function

Step 1: Pushing the Return Address

The return address, which is the address of the next instruction to be executed after the function call, is pushed directly onto the stack rather than being stored in any specific register –this makes the address retrivable during a return (ret) call. This is a crucial part of the function call process because it allows the program to “remember” where to return after the function completes its execution.

Here’s a more detailed look at what happens:

• When the call instruction is executed, it first pushes the return address (the address of the next instruction in the calling function) onto the stack.
• This push operation decrements the RSP register to allocate space on the stack and stores the return address at this new address and becomes top on the stack.
• The RIP register is then updated to point to the starting address of the called function.

Step 2: Setting Up the Stack Frame

1. RBP Backup: To create a stable reference point for the new function’s stack frame, the current RBP value (from main_function) is pushed onto the stack. This step allows the program to restore the caller’s stack frame after the function completes.

2. RBP Update: The RBP register is then updated to the current RSP value, establishing it as the base pointer for the function’s stack frame. Now, RBP (Base Pointer) marks the start of sub_function’s stack frame.

3. RSP Update for Local Variables: The stack pointer (RSP) is decremented by a value that depends on the size of local variables required by sub_function. This adjustment reserves space on the stack for these variables.

Visual Example of Stack Layout after Setup

After setting up the stack frame, the stack might look like this:

Function Execution - Manipulating Data and Registers

During function execution, local variables and function parameters are accessed using offsets from the RBP register, allowing consistent access to data without affecting RSP, which might change due to push/pop operations. The RIP register continues pointing to each instruction in sub_function, ensuring sequential execution of the function’s code.

Returning from a Function

Once the function’s tasks are complete, it needs to return control to the caller function (main_function in our example). This process involves reversing the stack setup steps taken at the start of the function:

1. RSP Update (Deallocate Local Variables): The RSP register is incremented to remove local variables, cleaning up the stack frame for the function.

2. Restoring the Previous RBP: The RBP value is popped from the stack, restoring the caller’s (main’s) base pointer.

3. Returning to the Caller (Updating RIP): Finally, the return address (stored at the current RSP location) is popped from the stack and loaded into the RIP register. This action transfers control back to the calling function, where the execution continues after the call to sub_function.

Example Walk-through with Assembly (x86-64)

Let’s examine this process with assembly code for a simple example:

main:
    call example_function   ; Call to example_function
    mox rip, 0x03; Execution will resume here after example_function returns

example_function:
    push rbp                ; Save caller's RBP
    mov rbp, rsp            ; Set new RBP for current stack frame
    sub rsp, 0x20           ; Allocate space for local variables (32 bytes)
    ; Function code here...
    add rsp, 0x20           ; Deallocate local variables
    pop rbp                 ; Restore caller's RBP
    ret                     ; Return, popping return address into RIP

In this example:

• push rbp: Saves the caller’s RBP on the stack.
• mov rbp, rsp: Sets RBP for example_function.
• sub rsp, 0x20: Allocates 32 bytes for local variables.
• add rsp, 0x20 and pop rbp: Clean up the stack before returning.

The ret instruction at the end of example_function is crucial as it pops the return address from the stack into the RIP, sending control back to the caller.