Ownership

Ownership and Borrowing

Rust’s unique approach to memory management







What is memory management?

(and why is it hard?)









Little vs Big Data

Little Data

  • fixed size, known at compile time
  • bool, char, i32, f64, usize, …
  • copies quickly

Big Data:

  • variable size, unknown at compile time
  • String, Vec<T>, HashMap<K,V>, …
  • copies slowly

Most PLs manage memory with the stack and heap.








Little Data Lives on the Stack

fn main() {
    let n = 5;      // L1
    let y = inc(n); // L3
    println!("n: {}, y: {}", n, y);
}

fn inc(x: i32) -> i32 {
    x + 1           // L2
}

Little data on the Stack

Little data lives on the stack

Variables live in stack frames mapping variables to values

  • At L1 frame for main holds n = 5
  • At L2 frame for inc holds x = 5
  • At L3 frame for main holds n = 5 and y = 6

Frames are organized into a stack of currently-called-functions.

  • At L2 frame for main above the frame for inc

Entire frame is freed or deallocated on function return






Little Data Copies Quickly

When an expression reads a little-data variable, its value is copied from its slot in the stack frame

Reads Copy Variables

  • At L2 the value of n is copied into y

  • At L3 the value of n is left unchanged, even after changing y









Big Data Copies Slowly

Cannot copy big data quickly!

Big Data Copies Slowly









Big data lives on the Heap

Big data is stored on the heap

References Copy Quickly

Can quickly copy references to data!

… but a and b refer to the same data on the heap









Sharing is Hard!

Why?









Sharing with Manual Management (C, C++)

Programmer explicitly alloc and free memory

  • Zero runtime overhead

Problem: Unsafe

  • Free too early (Dangling references!)
  • Forget to free (Leaks!)
  • Double-free (Vulnerabilities!)








Sharing with Garbage Collection (Java, Python, Haskell)

Runtime that looks for and reclaims unused memory

  • Memory safe (can only use “valid” memory that has not been freed)

as the program runs; in other languages,

Problem: Unpredictable

  • GC can kick in and introduce pauses at unpredictable times









Sharing breaks local reasoning

(But my personal reason…)

Ground can change beneath your feet!

(Makes concurrency really hard)









Rust’s Secret Sauce: Ownership

The key idea in Rust’s ownership system is in three rules:

  1. Each value in Rust has an owner.
  2. There can only be a single owner at any time.
  3. Value is dropped (reclaimed) when owner goes out of scope.

Unique value proposition: memory safety without GC











Ownership Ingredients

  1. Scope
  2. Drop
  3. Ownership
  4. Move/Transfer









1. Scope

Scope is the “area” within a program for which a name is valid.

{                                 // s not valid here; not yet declared
   let s = String::from("hello"); // s is valid from this point on
   // ...
   // do stuff with s
   // ...
}                                 // scope is over; s no longer valid









2. Drop/Free when Owner Goes Out of Scope

Scope is the “area” within a program for which a name is valid.

{                                 // s not valid here; not yet declared
   let s = String::from("hello"); // s is valid from this point on
   // ...
   // do stuff with s
   // ...
}                                 // scope is over; DROP/FREE `s`
Drop when owner out of scope










3. (Unique) Ownership

Heap data has a single unique owner … assignment transfers or moves ownership.

Move ownership on assignment
















QUIZ

What will be printed by this code?

fn main() {
   let a = String::from("hello"); // `a` is the unique owner
   let b = a;                     // ownership of heap data MOVED to `b`
   println!("a is {a}");          // what will be printed?
}









4. Move/Transfers Ownership

Assignment moves ownernship … cannot then use a moved value

fn main() {
   let a = String::from("hello"); // `a` is the unique owner
   let b = a;                     // ownership of heap data MOVED to `b`
   println!("a is {a}");          // what will be printed?
}

Compiler rejects with error:

error[E0382]: borrow of moved value: `a`
  --> src/main.rs:20:20
   |
18 |    let a = String::from("hello");
   |        - move occurs because `a` has type `String`, which does not implement the `Copy` trait
19 |    let b = a;
   |            - value moved here
20 |    println!("a is {a}");
   |                    ^ value borrowed here after move
   |
help: consider cloning the value if the performance cost is acceptable
   |
19 |    let b = a.clone();
   |             ++++++++

Notes

  1. String does not implement the Copy trait.
  2. Consider .clone() if you want to copy data instead of moving it.









4. Clone (if you really can’t move …)

Assignment moves ownernship … cannot then use a moved value

… if you must then you have to explicitly clone the data

fn main() {
   let a = String::from("hello"); // `a` is unique owner
   let b = a.clone();             // `b` is unique owner of a clone
   println!("a is {a}");          // OK
}
Big data can be cloned()










Recap: Copy vs Move

Consider these two examples:

Little Data Is Copied

{
  let x = 5;                   // x comes into scope
  let y = x;                   // x is copied into y
  println!("x is {x}");        // x and y are both valid
}

Big Data is Moved

let x = String::from("hello"); // x comes into scope
let y = x;                     // x is moved into y
println!("x is {x}");          // ERROR: `x` value is moved!












QUIZ

What happens on assignment?

fn main() {
    let s = String::from("hello");
    s = String::from("ahoy");
    println!("{s}, world!");
}









Cannot Assign to Immutable Variable

let x creates an immutable variable by default – you cannot re-assign it!

fn main() {
    let s = String::from("hello");  // s comes into scope
    s = String::from("ahoy");       // ERROR: cannot assign twice to immutable variable
}

Produces an error

error[E0384]: cannot assign twice to immutable variable `s`
 --> src/main.rs:7:5
  |
6 |     let s = String::from("hello");
  |         - first assignment to `s`
7 |     s = String::from("ahoy");
  |     ^ cannot assign twice to immutable variable
  |
help: consider making this binding mutable
  |
6 |     let mut s = String::from("hello");
  |         +++

Read the error message carefully!









Re-assigning Variables

fn main() {
    let mut s = String::from("hello");  // s comes into scope
    s = String::from("ahoy");           // s is re-assigned
                                        // old value DROPPED
    println!("{s}, world!");            // prints "ahoy, world!"
}







Mutating Data

String can be mutated (i.e. changed)

fn main() {
    let mut s = String::from("hello");
    s.push_str(", world!");  // push_str() appends a literal to a String
    println!("{s}");         // prints "hello, world!"
}

QUIZ What happens if we replace let mut with just let s?







QUIZ: Function Calls

What happens when we run?

fn main() {
    let mut s = String::from("hello");
    call_me_string(s);
    println!("{s}, world!");
}

fn call_me_string(x: String) {
    println!("Thanks for calling me with {x}!");
}








QUIZ: Function Calls

What happens when we run?

fn main() {
    let mut s = 42;             // s comes into scope
    call_me_i32(s);
    println!("{s}, world!");    // prints "ahoy, world!"
}

fn call_me_i32(x: i32) {
    println!("Thanks for calling me with {x}!");
}








Fn Parameters: Little Data ==> Copy

What happens when we run?

fn main() {
    let mut s = 42;
    call_me_i32(s);             // `s` is COPY into `x`
    println!("{s}, world!");    // prints "42, world!"
}

fn call_me_i32(x: i32) {
    println!("Thanks for calling me with {x}!");
}

Try it out on aquascope

  • s is copied into parameter x
  • x gets printed …
  • s is still valid after the call











Fn Parameters: Big Data ==> Move

What happens when we run?

fn main() {
    let mut s = String::from("hello");  // s comes into scope
    call_me_string(s);                  // s is MOVED into `x`
    println!("{s}, world!");            // compile-time error!
}

fn call_me_string(x: String) {
    println!("Thanks for calling me with {x}!");
    // x goes out of scope and is DROPPED
}

Try it out on aquascope

  • s is moved into parameter x
  • x gets printed …
  • s is not valid after the call!











QUIZ

What happens when we run the following program?

fn burp() -> String {
    let s = String::from("burp"); // s comes into scope
    s                             // s is moved out to the caller
}

fn say_length(z: String) {
    let n = z.len();              // get length of z
    println!("length of z = {n}");
}

fn main() {
    let s1 = burp();
    println!("(a) s1 is {s1}");
    say_length(s1);
    println!("(b) s1 is {s1}");
}










Returns Copy (Little) or Move (Big) Too!

fn burp() -> String {
    let s = String::from("burp"); // `s` comes into scope
    s                             // `s` is moved out to the caller
}

fn say_length(z: String) {
    let n = z.len();              // get length of `z`
    println!("length of z = {n}");
}                                 // `z` goes out of scope and is DROPPED


fn main() {
    let s1 = burp();             // burp() moves its return into s1
    println!("(a) s1 is {s1}");
    say_length(s1);              // s1 is moved into say_length()
    println!("(b) s1 is {s1}");  // ERROR: s1 value is MOVED!
}

QUIZ How to modify say_length so we can print s1 after the call?












Don’t drop, return

Don’t drop, return 
fn say_length(z: String) -> String {
    let n = z.len();              // get length of `z`
    println!("length of z = {n}");
    z                             // `z` MOVED to return value
}


fn main() {
    let s1 = burp();             // burp() moves its return into s1
    println!("(a) s1 is {s1}");  // prints "(a) s1 is burp"
    let s1 = say_length(s1);     // s1 is moved into say_length()
    println!("(b) s1 is {s1}");  // prints "(b) s1 is burp"
}

… but seriously, this is rather clunky!

How to simplify say_length?










Rust’s Secret Sauce: Ownership + Borrowing

Unique value proposition: memory safety without GC

  1. Each value in Rust has an owner.
  2. There can only be a single owner at any time.
  3. Value is dropped (reclaimed) when owner goes out of scope.

To “access” data, no need to take ownership, just borrow









Borrowing with References

&T is a reference to a value of type T

fn say(z: &String) {    // L2 `z` is a reference to a String
    let n = z.len();    //     get length of `z`
    println!("length of z = {n}");
}                       // `z` exits scope, but NOT DROPPED, `z` NOT-OWNER

So say_length takes a reference to a String

fn main() {
    let s = read_file("moby_dick.txt"); // L1 read_file() moves its return into `s`
    say(&s);                            // `s` BORROWED by say()
                                        // L3 `s` RETURNED by say()
}                                       // `s` exits scope, is DROPPED

You can borrow from the owner but you have to give it back

data can be borrowed










Rust’s Secret Sauce: Ownership + Borrowing

Unique value proposition: memory safety without GC

  1. Each value in Rust has an owner.
  2. There can only be a single owner at any time.
  3. Value is dropped (reclaimed) when owner goes out of scope.

To “access” data, no need to take ownership, just borrow

  • &T gives a reference to a T i.e. lets you borrow access to T









Mutating through References

Recall that String can be mutated (i.e. changed) e.g.

fn main() {
    let mut s = String::from("yo!");
    s.push_str(", world!");
    println!("{s}"); // prints out "yo!, world!"
}








QUIZ

What happens if we try

fn main() {
    let mut s = String::from("yo!");
    change(s);
    println!("{s}");
}

fn change(z: &String) {
    z.push_str(", world!");
}








Mutating Requires Mutable References (Borrows)

We can only mutate data through a mutable reference &mut T

fn main() {
    let mut s = String::from("yo!");
    change(&mut s);
    println!("{s}");
}

fn change(z: &mut String) {
    z.push_str(", world!");
}








QUIZ

What about little data? For example, what happens if we try

fn main() {
    let x = 42;
    say(&x);
    println!("haha {x}");
}

fn say(z: &i32) {
    println!("hoho {x}");
}











Prints

hoho 42
haha 42

QUIZ

What happens if we try

fn main() {
    let x = 42;
    change(&x);
    println!("haha {x}");
}

fn change(z: &i32) {
    z = z + 1;
}















Compiler error!

  1. Can’t do z + 1 as z is a reference;
  2. Can’t re-assign z as it is an immutable reference!












(Re)-Assignment Requires Mutable References (Borrows)

We can only reassign data through a mutable reference &mut T

fn main() {
    let mut x = 42;
    change(&mut x);
    println!("haha {x}");
}

fn change(z: &mut i32) {
    *z = *z + 1;
}
Updating Data on Stack








Rust’s Secret Sauce: Ownership + Borrowing

Unique value proposition: memory safety without GC

  1. Each value in Rust has an owner.
  2. There can only be a single owner at any time.
  3. Value is dropped (reclaimed) when owner goes out of scope.

To “access” data, no need to take ownership, just borrow

  • &T gives a reference to a T i.e. lets you read access to T
  • &mut T gives a mutable reference to a T i.e. lets you write access to T

Both references return ownership to whoever they “borrowed” from…

But why two kinds of references?









QUIZ

Why two kinds of references (&T vs &mut T)?

fn quizA() {
    let mut s = String::from("yo!");
    let r1 = &s;
    let r2 = &s;
    println!("{} and {}", r1, r2);
}

fn quizB() {
    let mut s = String::from("yo!");
    let r1 = &s;
    let r2 = &mut s;
    println!("{} and {}", r1, r2);
}

What happens when you run quizA and quizB?










Shared vs Mutable Borrows

At any given time, you can have either

  • many shared references(&T) or

  • single mutable reference (&mut T)

Often called the sharing XOR mutability rule

But … why?















Mutation can Invalidate References

i.e. the “ground can change beneath your feet”

fn quizA() {
    let mut s = String::from("yo!");
    let r = &s;         // shared borrow
    change(&mut s);     // mutable borrow
    println!("{}", r);  // reuse shared borrow
}

What could change do to s that would make r invalid?















e.g. enlarge it, so it needs to be shifted in memory, or …










Mutation can Invalidate References

i.e. the “ground can change beneath your feet”

fn main() {
  let mut v = vec![10, 20, 30]; // create a vector of 3 elements
  let last = &v[2];             // shared reference to last elem
  println!("last = {}", *last); // prints 30
  change(&mut v);               // mutate vector, removing last element!
  println!("last = {}", *last); // YIKES! what does this print?
}

fn change(z: &mut Vec<i32>) {
    z.pop();
}

After change, the references last refers to ???

The reference is now dangling or invalid

Sharing XOR Mutability rule prevents this!

Multiple shared references are OK, as none of them can change the data!










QUIZ

What happens when we run the following program?

fn main() {
  let mut v = vec![10, 20, 30];
  let r0 = &v[0];
  let r1 = &v[1];
  let r2 = &v[2];
  println!("elems are {:?}, {:?}, {:?}", *r0, *r1, *r2);
  let mr = &mut v;
  change(mr);
  change(mr);
  println!("v is {:?}", v);
}

fn change(z: &mut Vec<i32>) {
    z.pop();
}










Sharing XOR Mutability

fn main() {
  let mut v = vec![10, 20, 30];
  let r0 = &v[0];
  let r1 = &v[1];
  let r2 = &v[2];
  println!("elems are {:?}, {:?}, {:?}", *r0, *r1, *r2);
  let mr = &mut v;
  change(mr);
  change(mr);
  println!("v is {:?}", v);
}

fn change(z: &mut Vec<i32>) {
    z.pop();
}

Q Why is programm accepted by compiler?










A The shared borrows r0, r1, r2 are unused after the first println!, so the compiler considers them out of scope before the mutable borrow mr is created!

Sharing XOR Mutability












Sharing XOR Mutability

fn main() {
  let mut v = vec![10, 20, 30];
  let r0 = &v[0];
  let r1 = &v[1];
  let r2 = &v[2];
  println!("elems are {:?}, {:?}, {:?}", *r0, *r1, *r2);
  let mr = &mut v;
  change(mr);
  change(mr);
  println!("r1 is {:?}", *r1);
}

Q Why is program rejected by compiler?










A The shared borrows r1 overlaps with the mutable borrow mr because r1 is used after mr is created!

Sharing XOR Mutability











Rust’s Secret Sauce: Ownership + Borrowing

Unique value proposition: memory safety without GC

  1. Each value in Rust has an owner.
  2. There can only be a single owner at any time.
  3. Value is dropped (reclaimed) when owner goes out of scope.

To “access” data, no need to take ownership, just borrow

  • &T gives a reference to a T i.e. lets you read access to T
  • &mut T gives a mutable reference to a T i.e. lets you write access to T
  • At any given time, you can have many shared or single mutable reference









Material Inspired by

  • https://rust-book.cs.brown.edu/ch04-01-what-is-ownership.html
  • https://doc.rust-lang.org/book/ch04-01-what-is-ownership.html