Why write about Stack and Heap when there are already a lot of articles out there? I want to improve my writing skills so, I decided to write articles about things I find interesting. This article was supposed to be about how Rust manages memory through ownership. Then I thought “I should first write about Stack and Heap”. So, here we are).

To understand memory management first, we need to understand what the Stack and the Heap are. Stack and Heap are memory regions used by a process to store and read values. The memory of a running process can usually be divided in the following four regions:

• Text: Here is where our program instructions live. Our compiled program is loaded and stored in this region of the memory.
• Data: All the global variables are stored in this region.
• Stack: A contiguous chunk of memory that stores local variables, arguments and return addresses of functions (we will go deeper on this in the next section). Every process’ thread has its own Stack.
• Heap: Stores all the dynamically allocated memory. This region is shared among all threads of a process.

Stack

A process’ Stack is an actual implementation of the Stack data structure. It is fixed in size; we can not ask the operating system for more memory. This size depends mostly on the OS. In modern Linux systems, the maximum Stack size is 8 MB (you can check yours with the command ulimit -s).

Inside the Stack

Every time we call a function, a Stack frame (a chunk of contiguous memory containing all the information required by the recently called function) is created and placed on top of the Stack. And, every time a function ends, the Stack frame is popped from the Stack, automatically releasing all the memory used by it. Let’s see a minimal example on how the Stack is populated. Consider the following code:

fn sum(a: i32, b: i32) -> i32 {
    let result = a + b;
    result
}

fn square_sum(a: i32, b: i32) -> i32 {
    let sum_result = sum(a, b);
    let pow_result = sum_result * sum_result;
    pow_result
}

fn main() {
    let n1 = 2;
    let n2 = 5;
    let pow_result = square_sum(n1, n2);
    println!("Result: {}", pow_result);
}

The following diagram represents what happens with the Stack when the program is executed:

1. At the beginning, a Stack frame for the main function is created.
2. main calls square_sum, a Stack frame for square_sum is created.
3. square_sum calls sum, a Stack frame is created for sum.
4. After sum is called, its Stack frame is destroyed, releasing automatically all the memory it occupied.
5. After square_sum is called, its Stack frame is destroyed, releasing automatically all the memory it occupied.
6. main prints the result and ends. The operating system frees up all the remaining memory.

NOTE: Usually, the stack grow downwards!

Inside the Stack frame

The Stack frame is where all the local variables, arguments, and return address (this is used by the running process to know where the next code instruction to be executed is, after the function call ends) of a function live. The good news is that the user does not have to worry about allocating or de-allocating the memory used by it (neither with Heap allocations in safe Rust, but that is for another post). Given that the Stack is fixed in size, we can only store data that its size is known at compile time. For dynamic sized data (such as vectors), Heap memory is used (only a pointer to that part of the Heap memory and maybe some metadata is saved into the Stack). Let’s expand the above Stack diagrams to show the stack frame of each function:

How do we use the memory contained in the frame? We have two pointers that helps us with that:

• Stack Pointer (SP): Always points at the top of the Stack. When a Stack frame is created the new SP’s value is SP + size_of(new_Stack_frame). It will change any time a value is pushed onto or popped off the stack. When an executing function returns, it goes back to its previous size.
• Base Pointer (BP): Also known as Frame Pointer (FP). Points to the base of the current Stack frame. When a Stack frame is created, the BP gets the value SP had before adding the size of the new Stack frame. The BP is used to access the arguments and local variables of a function by adding/substracting the offset of the variable we want to access. For example, if we want to access the argument y, we need to read the address BP + 12 because, first, we have the return address that (let’s assume) is 4 bytes long, and then the argument x that is a 32 bits integer (4 bytes).

The layout presented here is just an example. Although, in reality, the frames contain the same information, how the data is organized depends on the machine architecture and the application binary interface (ABI).

This StackOverflow answer shows how the frame is constructed using x86 assembly.

Heap

In this context, “Heap” has nothing to do with the Heap data structure, it is just a name for the free memory pool.

The Heap is not fixed in size. We can ask for more memory, as long as it is available in the system, and free it if the allocated values are not needed anymore. Unlike Stack, when we are working with the Heap we have to take care of the allocation and deallocation of memory (in Rust, most allocation/deallocation logic is hidden behind abstractions). When we use the Heap, we are dynamically allocating memory. This comes in very handy when we are dealing with data which size is unknown at compile time (i.e. user input). In opposition to the Stack, the memory allocations are not sequential.

When a process wants to allocate some chunk of memory of a given size, the operating system first has to search for a free piece of memory with the needed size. After finding it, the OS locks it up (only that particular process can access that portion of the system memory) and returns the starting address of the block. This process leads to memory fragmentation (the data allocated in the Heap is not contiguous).

When we use the Heap, we also store some data in the Stack (at least a pointer to the allocated data). Consider the following code:

fn main() {
    let n1: Box<u8> = Box::new(42);
    let my_string = String::from("hello");

    println!("{} {}", my_string, n1);
}

NOTE: A Box is a smart pointer to a heap allocated value.

The following diagram shows the allocations made in the Stack and the Heap:

Writing and reading the Heap is slower than writing and reading the Stack for several reasons:

• For memory allocation, a process has to make a system call and wait for the OS to complete the process described above.
• Using the allocated memory (for writing or reading) involves at least one indirection (following the pointer allocated in the Stack).
• Under the right conditions, a program can be optimized to store some parts of the Stack inside the processor’s cache, making writing/reading operations blazingly fast.

Summary