In the first article in this series, we laid some foundational groundwork by learning about Value and Reference types. We also learned about how Computer Memory works at a high level. I recommend that you read the article if you haven't before continuing.

In this article, we continue from where we left off and learn about Stack and Heap Memory. We will work through some code examples in Rust, with visualizations to make the concepts stick. Understanding Stack and Heap memory is fundamental to the ultimate goal, which is to learn what Ownership is in Rust and how it works.

Stack Memory

The Stack is a big block of memory that is designed to store data that has a known, fixed size (i.e., the size that doesn't change). In the contiguous giant array of memory slots in Computer Memory, some blocks of memory are dedicated to the Stack.

In Rust, each thread within a process has its own stack, typically with a fixed size defined during compilation. This stack is used for storing local variables, function call information, and other related data for the thread's execution.

Stack and Order

The Stack is strictly ordered:

The top objects are removed (or accessed) first
The bottom objects are removed (or accessed) last

The Stack is usually referred to as a first-in, last-out (FILO) structure. Think of it like a stack of books that is strictly ordered. The book that is further down will be the last book removed. And the book that was just placed at the start will be the first one out.

Placing new data on the stack is known as pushing onto the stack. While removing the element at the top of the stack is known as popping off the stack.

Stack Pointer and Stack Frame

Allocating new data on the stack is straightforward, as long as the memory location of the last data on the stack is known. That is, the top of the stack, new data is 'allocated on top of it'. What keeps track of the top of the stack is the Stack Pointer.

When a function is executed, the stack is used by the function to store data such as local variables, arguments, and the return address of the function. The portion of the stack allocated to a function for this purpose is the function's Stack Frame. As functions are called within other functions, their stack frames are stacked on top of each other.

Take, for example, the following function in Rust:

fn bar(j: i32) {
    let k = 20;
}

When this function is called and a value is passed for the j parameter, its stack frame can be visually represented as shown:

Let's walk through what happens when the following program runs:

fn bar(j: i32) {
    let k = 20;
}

fn main() {
    let x = 5;
    bar(x);
}

The execution starts with the main function:

A stack frame is created for the main function, and the stack frame is pushed onto the stack. The local variable x is stored in the stack frame
When the call to bar(x) is made, a stack frame for the bar function is also created. A copy of the value of the variable x is made to j.

The stack frame includes both j and k . This is because value types are copied by value, as explained in the previous article.
When execution of bar finishes, its stack frame is popped from the stack
When the execution of main finishes, its stack frame is also popped from the stack

Below is a visualization of this process:

Let's look closely into each of the stack frames:

Note: If you want to get a better understanding of this memory model and the syntax for the address, read the Memory Management section of the first article.

Let's walk through another execution of functions and how the stack frames are created, pushed onto the stack when the function is called, and popped off the stack when the function finishes execution.

Let's also look closer into the stack frames as they are being created:

A function only has access to the data within its stack frame; it cannot access data in another function's stack frame. If you need to share memory between different functions or keep it alive longer than a function's execution, you have to use Heap data.

Summary of Stack Memory

We have learned that Stack Memory is used to manage function data like local variables and arguments. We also learned in the previous article that Value Types are usually allocated on the Stack.

From what we learned about Stack Frames, they are created and pushed onto the stack when a function is invoked, and when the function finishes execution, the stack frames for it are popped off the Stack.

Value Types and Stack Memory

As we learned in the previous article, Value Types like integers, floating-point numbers, Booleans, characters, tuples and arrays are usually stored in Stack Memory.

The reason for this is that these types have a known size that is fixed. They can be easily stored on the stack and popped off.

It is easy to allocate and deallocate data on the Stack because of its order, and the stack pointer always points to the top of the stack. By default, Rust will store data on the stack whenever it can.

Heap Memory

In the previous article, we learned about reference types that are allocated on the Heap. We learned that these types are dynamically sized, meaning that they can grow in size.

This Heap Memory we are referring to is not the same as the Heap Data Structure. It is a block of memory that is available for your program to allocate data of unknown size at compile time or size that might change.

Unlike Stack Memory, which is strictly ordered (FILO), Heap Memory is less organized. Data can be allocated and deallocated in any order on the Heap.

Also, where we have each thread within a process having its own stack, the Heap is a shared pool of memory accessible to the entire program.

Data Allocation on the Heap

When data is to be allocated on the Heap:

You (or Rust) request for a certain amount of space
The Memory Allocator finds an empty spot in the Heap that is big enough for the space requested
The Memory Allocator marks the spot as 'being in use'
The Memory Allocator returns a pointer which is the memory address of that location

Parking Vectors by Vecteezy

Allocating data on the heap is like finding parking at a busy mall:

You request a specific parking space size.
The parking lot attendant (Memory Allocator) searches for an available parking spot that fits your request.
Once found, the attendant puts a 'reserved' sign (marks it as 'being in use') on that parking spot.
Finally, the attendant hands you a ticket (pointer) showing the address of your allocated parking space.

Deallocation on the Heap

Following the analogy of finding a parking spot at a busy mall, deallocating data on the Heap is like leaving a parking spot:

You notify the parking lot attendant (Memory Allocator) that you're leaving your parking spot.
The attendant removes the 'reserved' sign (marks it as 'available') from the spot.
You drive away without needing the ticket (pointer) anymore, freeing up the space for someone else to use.

So this is what happens during data deallocation on the Heap:

You (or Rust) release the allocated memory, indicating that you no longer need that space.
The Memory Allocator marks the spot as 'available' or 'free' for future use.
The previously allocated memory space is now accessible for reallocation, and the pointer referencing that space becomes invalid or unusable.

Allocating data on the Heap requires more work than on the Stack, as the Memory Allocator must first find a space big enough to hold the data. It must also perform bookkeeping to prepare for the next allocation.

Deallocating data on the Heap is also slower than accessing data on the stack. To access data on the Heap, the pointer to the heap is followed. The processor has to 'jump around' to wherever the pointer is pointing to in order to access the data. Unlike the Stack where each frame is stacked on top of the other and the Stack Pointer can access contiguous memory location by going down the stack.

Heap Allocation Code Example

To illustrate allocating data on the Heap in Rust, we will use the Box<T> type. Here is an example:

fn main() {
    let x = Box::new(5);
    let y = 34;
}

When main() is called, here is what happens in memory:

There are two local variables in main that space must be allocated for. The variable y has the value 42 which is a Value Type and can therefore be allocated on the Stack.

But what about x? x is of the type Box<i32>, and as we learned earlier, boxes allocate memory on the Heap. Box is a structure that has a pointer to the Heap.

Box::new() allocates some memory on the Heap and puts 5 there. The position in memory where 5 is allocated to is chosen by the Memory Allocator in no particular order, the memory will look like this:

The Memory Allocator chooses a memory location that is free somewhere on the Heap, in this case, it is the location 0x3FFFFFCE and it puts 5 in that location. The value of x on the stack is then a raw pointer to the place allocated on the Heap.

So, instead of x having the value 5 on the stack, it has a pointer to the location where 5 is stored on the Heap. The diagram above shows the Heap and Stack as they are both part of the Computer Memory (the RAM).

You can read about Memory Management in the first article in this series for more context.

Heap Vs Stack Memory

We learned that the Stack and Heap are both blocks of memory with different properties. The Stack is strictly ordered, and it is a first-in-last-out structure that stores data that has a fixed and known size at compile time.

The Heap, on the other hand, is less organized than the Stack and it holds data with unknown size at compile time or whose size can change.

We also learned that while each thread has its own stack, the heap is available and shared among different parts of a Rust program, enabling the allocation of dynamic memory that can be accessed across functions, threads, and modules within the same program.

Heap Memory and Rust Ownership

Ownership in Rust aims to manage heap data; this is why it is important to understand Heap Memory and which type of data is allocated to it.

As we will learn in subsequent articles in this series, the rules of Ownership applies to data that is allocated on the Heap.

Summary

In this second article in the Rust Ownership series, we continue to build on what we learned in the first article. We learned about the Stack and Heap Memory. How data is allocated to each of them and the differences in how they manage data.

We concluded by learning that ownership in Rust is towards managing Heap data. In the next article, we will learn about other concepts relating to ownership in Rust; Scope, References and Borrowing, and Ownership.

Sola's Blog