Stack and Heap

The first thing to understand about ownership is to know about the stack and heap memory. This concept will be quite easy if you have learned C or C++, since they are almost the same.

Stack Memory

If you simply declare a variable in a function, then it will live in the stack. For example, the code below declares some such variables:

fn main() {
    let a = 1;
    let y = plus_one(a);
}

fn plus_one(x: i32) -> i32 {
    x + 1
}

The variables a, x, and y are all allocated and deallocated automatically, just like C/C++ compiler.

Heap Memory

Rust and C/C++ are totally the same in terms of the stack memory. However, for the heap memory, that an another story. Instead of letting programmers control all the heap memory manually, the Rust compiler takes over the work and uses a lot of constraints to avoid common problems, or UB (undefined behavior).

Rust provides a construct called Box for allocating data on the heap.

let a = Box::new([0; 1_000_000]);

The above code declares an array that lives in the heap and a pointer a that lives in the stack.

As mentioned above, Rust automatically frees the heap memory, but when should a box’s heap memory be deallocated? Well, the intuition tells us, when a box doesn’t have any pointers pointing to it, then it can be freed, that’s exactly how garbage collection works in some other languages (JAVA, C#, etc.). Rust uses a different management that is based on scope:

If a variable owns a box, when Rust deallocates the variable’s stack memory, then Rust deallocates the box’s heap memory.

So here comes the term “own”, but let’s talk about the references first.

References

Let’s say we want to design a function that takes 2 strings as input and prints them on one line. The most intuitive way to do that is like the following:

fn main() {
    let s1 = String::from("Hello");
    let s2 = String::from("world");
    greet(s1, s2);
    println!("{} {}!", s1, s2);
}

fn greet(t1: String, t2: String) {
    println!("{} {}!", t1, t2);
}

But we will get errors when we compile the code. The error message tells us that s1 and s2 have been moved. It is because some types (e.g., String, Vec, Box) don’t implement the Copy trait. For the types that implement Copy (e.g., i32), they also live on the stack by the way, the similar code won’t result in an error, since the function just takes the value of the variables. If we don’t want to move the variables, the reference is what we need.

Like C/C++, Rust uses ampersand (&) and asterisk (*) to represent reference and dereference.

fn main() {
    let s1 = String::from("Hello");
    let s2 = String::from("world");
    greet(&s1, &s2);
    println!("{} {}!", s1, s2);
    
    let mut n: Box<i32> = Box::new(1);
    let a = *n;
    *n += 1;
    println!("a = {a}, n = {n}"); // output: a = 1, n = 2
}

fn greet(t1: &String, t2: &String) {
    println!("{} {}!", t1, t2);
}

From the above code we can see how reference and dereference work.

Yes, but…

References are powerful, but they may cause a lot of problems (if you have written pointers in C/C++, you would know what I mean). For example, executing the following code will lead to undefined behavior:

let mut v: Vec<i32> = vec![1, 2, 3];
let n: &i32 = &v[2];
v.push(4);
println!("n = {n}"); // UB: pointer used after its pointee is freed

In this case, when we push an item into v, the program will deallocate the original array and allocate a bigger array, which makes n point to an invalid memory space.

In order to avoid this problem, we need to add some constraints when we want to mutate some data. The borrow checker is designed to do this.

Borrow Checker

The main idea of the borrow checker is that all the variables have three permissions on their data:

  • Read: data can be copied to another location.
  • Write: data can be mutated.
  • Own: data can be moved or freed.

These permissions don’t wholly represent their behavior at runtime. They describe what does compiler thinks about the program be the program is executed.

By default, a variable has Read and Own permissions on its data. If a variable has mut when it has been declared, then it would have Write as well.

There is one thing that needs to be highlighted: the permissions can be changed. Let’s see the following example:

let mut v: Vec<i32> = vec![1, 2, 3]; // [v: R W O]
let n: &i32 = &v[2];                 // [v: R - -] [n: R - O] [*n: R - -]
println!("n = {n}");                 // [v: R W O] [n: - - -] [*n: - - -]
v.push(4);                           // [v: - - -] [n: - - -] [*n: - - -]

When we have a pointer n that points to v, the data in v has been borrowed by n. Three things happen:

  • The borrow removes the Write and Own permissions from v, but it can still be read.
  • n has gained the Read and Own permissions. It’s not writable since it wasn’t marked mut.
  • *n has gained the Read permission.

Please note that the permissions of n and *n are different. Because accessing data through reference is not the same as modifying the reference itself. You can take the code below as an example:

let mut v: Vec<i32> = vec![1, 2, 3]; // [v: R W O]

let mut t: &i32 = &v[0];             // [v: R - -] [t: R W O] [*t: R - -]
t = &v[1];                           // [v: R - -] [t: R W O] [*t: R - -]
println!("t = {t}");                 // [v: R W O] [t: - - -] [*t: - - -]

let n: &mut i32 = &mut v[2];         // [v: - - -] [n: R - O] [*n: R W -]
*n = 0;                              // [v: R W O] [n: - - -] [*n: - - -]
println!("{:?}", v);

Ending

Let’s end here for now. I will continue writing this article as soon as I have learned more advanced ideas about Rust ownership.