[Advanced Rust] 1.4. Memory Part 2 - Stack Memory, Stack Frames, and Stack Pointer

1.4.1. Memory Regions

Programs have many memory regions; not all of them are on DRAM. Three especially important regions are stack memory, heap memory, and static memory.

Compared with heap memory, stack memory is faster, while heap memory is slower.

1.4.2. Stack Memory

There is an axiom: “When in doubt, prefer the stack.” But if you want to put data on the stack, the compiler must know the size of the type. In other words: “When in doubt, prefer a type that implements Sized.”

The stack is a region of memory that the program uses as temporary storage for function calls.

Why is it called a stack? Because entries on the stack are LIFO (Last In, First Out).

Stack Frame

Each time a function is called, a contiguous block of memory is allocated at the top of the stack. This is called a stack frame.

Near the bottom of the stack is the frame for main, and as functions are called, the remaining frames are pushed onto the stack.

A function’s frame contains all the variables inside that function, as well as the parameters passed to it. When the function returns, its frame is reclaimed.

The bytes that make up the values of a function’s local variables are not immediately erased, but accessing them is unsafe because they may be overwritten by later function calls if the later call’s frame overlaps the reclaimed one. Even if they are not overwritten, they may still contain values that can no longer be used, such as values that were moved out when the function returned.

Stack frames are also called activation frames or allocation records. Only when activation frames are allocated on the stack do we call them stack frames.

Each stack frame has a different size. During a function call, the stack frame contains the function’s state. When one function is called inside another, the original function’s state is frozen for the moment.

Stack frames provide space for function parameters, pointers to the original call stack, and local variables (excluding data allocated on the heap).

The main task of the stack is to create space for local variables, because all variables on the stack are adjacent to one another, which makes them faster to find.

Let’s look at an example:

fn main() {
    let pw = "justok";
    let is_string = is_strong(pw);
}

fn is_strong(password: String) -> bool {
    password.len() > 5
}

Output:

error[E0308]: mismatched types
 --> src/main.rs:3:31
  |
3 |     let is_string = is_strong(pw);
  |                     --------- ^^ expected `String`, found `&str`
  |                     |
  |                     arguments to this function are incorrect
  |
note: function defined here
 --> src/main.rs:6:4
  |
6 | fn is_strong(password: String) -> bool {
  |    ^^^^^^^^^ ----------------
help: try using a conversion method
  |
3 |     let is_string = is_strong(pw.to_string());
  |                                 ++++++++++++

The problem is obvious: pw is of type &str, while the parameter of is_strong is of type String.

Our goal is to make is_strong compatible with both &str and String. That sounds simple, but it is actually a little tricky: a String owns a heap buffer, while an &str is only a fat pointer to some UTF-8 bytes that may live in static memory, on the heap, or elsewhere. Converting between these two types is not trivial.

Consider the revised code:

fn is_strong<T: AsRef<str>>(password: T) -> bool {
    password.as_ref().len() > 5
}

This treats the incoming parameter as a reference to str.

We could also write it like this:

fn is_strong<T: Into<String>>(password: T) -> bool {
    password.into().len() > 5
}

This converts the incoming parameter into a String. But these versions involve quite a bit of conversion.

We could also write:

use std::fmt::Display;

fn is_strong<T: Display>(password: T) -> bool {
    password.to_string().len() > 5
}

This converts the parameter to a String using to_string and then operates on it. This is even slower than the previous approach.

Stack Pointer

As the program executes, the CPU maintains a cursor that keeps updating and reflects the current address of the current stack frame. This cursor is called the stack pointer.

As functions keep calling other functions, the stack grows (the stack pointer starts at the stack frame), and the stack pointer value decreases (because memory addresses get larger the closer you are to the stack frame); when a function returns, the stack pointer value increases (when the function returns, its frame is reclaimed, and the cursor moves toward the stack frame, so the value becomes larger).

When the Stack Frame Disappears

The fact that stack frames eventually disappear is closely related to Rust’s notion of lifetimes. Any variable stored on the stack becomes inaccessible after its frame disappears.

So, the lifetime of any variable on the stack can be at most as long as the lifetime of its frame.