Rust #2: Lifetimes, Owners and Borrowers, OH MY!

One of the abilities that Rust promises is memory safety, and I'm here to say that it delivers. So much so, that I will not use a programming language for low-level systems programming that doesn't have the same promises now.

Microsoft discovered that 70% of their bugs were memory safety issues (reference), which means such bugs would be impossible to create if their software were written using Rust.

So what are the memory safety issues, and how does Rust make them impossible to produce?

Memory safety

Memory safety, in a nutshell, is making it impossible to access (reading or writing) memory that you shouldn't. For example:

• Writing to memory that is read-only. Examples of read-only memory are your code and string literals.
• Reading from or writing to memory you haven't allocated specifically from the your operating system.
• Accessing the area of your stack that isn't used by local variables or parameters.
• Dereferencing a null pointer.
• Writing to memory at the same time as another thread of your program is accessing it.

So how do such bad memory operations occur? Other languages (such as C++) make it easy for you to execute such bad operations as they do not protect you from them. This is why much software crashes all the time. Let's go through them.

Use after free

This means that after you free your memory and give it back to the operating system for reuse, you go ahead and continue using it. This can be caused in most languages by pointer aliasing. This means that your code has more than one pointer pointing to some memory, perhaps in different parts of your code. When one pointer is used to free some memory, the other pointers now "dangle". This means, they point to nothing. And so the main reason use-after-free occurs is when these other pointers continue to be used. That can lead to a crash (or segmentation fault). Look at this C++ code to demonstrate how this can happen:

std::vector<int> v;
v.push(1);
const int& ref_v = v[0];  // a
v.push(2); // b
std::cout << "v[0] = " << ref_v; // c

In the line a, we take a reference, which is a pointer, to the first element of the C++ vector. After we push the next value in line b, it is possible that the memory used by the vector is moved because it needs to be enlarged. This will invalidate the reference stored in ref_v. It is, in effect, pointing to garbage. Then we use it in line c - a use-after-free bug.

Double free

Another problem, which is really a use-after-free bug, is when memory is given back to the operating system more than once, either through the same pointer, or via aliasing pointers. This can lead to a crash.

Using uninitialised memory

This is when memory that is either allocated on the heap or the stack is not initialised to good data, and then later the program uses it assuming it is. This means your data will have random values in it, and if your data is a pointer, it means that your code will be more likely to access invalid memory addresses. That can lead to a crash.

Buffer underflow and overflow

This happens if while reading and writing to a block of memory, you access past the end or beginning of that block. For example, you allocate an array of 10 items, but ask for the 11th. This can, if you're lucky, cause a segmentation fault and crash your program. If you're unlucky, it can corrupt the data around that memory area and you won't see the effects of that issue until much later, making it hard to pinpoint where the problem occurred. Buffer overflows and underflows are the source of many security issues too.

Null dereferencing

Tony Hoare once called this his "billion dollar mistake". Setting a pointer to address 0, otherwise called null, usually means, in most programming languages, "this pointer points to nothing". Unfortunately, in those languages, there is nothing stopping you from using the pointer still. Trying to access address 0 on most operating systems will result in an immediate crash. This is usually the easiest bug to track down and fix, but still, you don't want them occurring after you release your software.

Data races

A data race occurs when one thread is writing to memory and another thread is reading or writing to it at the same time. This can lead to any thread reading or writing the wrong information.

Imagine this function being run at exactly the same time on two threads:

int gCounter = 0;

void increment_counter()
{
    int counter = gCounter; // a
    counter = counter + 1; // b
    gCounter = counter; // c
}

You'd expect the answer to be 2 after both functions have completed. However, if thread 1 executes lines a and b after thread 2 has executed line a and before it has executed line c, both threads will write 1 to gCounter. This is called a data race. Although this is often not a crash bug, it can be amazingly hard to track down. This is because unless those or similar conditions happen, you will not have a data race. So, in more complex situations, your application may run correctly 99% of the time, resulting in you desperately trying to recreate that 1% occurrence to track down the bug.

In software development, there is nothing worse than trying to fix a bug you cannot recreate.

Rust to the Rescue

All those bugs I've described above are impossible to occur if you write your program in Rust and avoid its unsafe keyword (used to lower Rust's shields when you need to). They are impossible to occur because any such attempt to produce those bugs results in a compilation error. This means that you can't even start a program with those bugs. This is a huge win for programmers.

So how does it do this? It is achieved using its memory model of ownership and borrowing. The 'borrow checker' is the analytical part of the compiler that will track and detect these memory issues. And when you first use Rust, you will butt heads with the borrow checker and hate it. But eventually, as you realise the borrow checker is always right, you will learn to love it and it will be your best friend in writing software.

Ownership

Every data used in Rust is owned by a single variable and ONLY one variable. When this variable goes out of scope, the data is deleted. Rust, therefore, always knows when to deallocate memory: as soon as the owner goes out of scope. This is why you can allocate memory and not care about deallocating it. You cannot do this in other languages because there might be two references to the data. Deallocating when one reference goes out of scope will cause a dangling pointer so those languages do not automatically deallocate.

When you assign a variable to another, or pass a variable to a function, you transfer ownership because you cannot break the one-owner rule. Examine this code:

let a = vec![1, 2, 3];
let b = a;  // Ownership of vector is transferred to b.
let c = a;  // Compiler error!  a does not own any data.

In line 1, the a variable owns the vector [1, 2, 3]. In line 2, by assigning a to b, you transfer ownership. The variable b now owns the vector, and as a result a owns nothing. It is a compilation error to use a afterwards. So as a result, in line 3 you would get a compilation error.

The same thing occurs when passing variables to functions:

fn print_vector(v: Vec<i32>) {
    println!("{}", v);
}
...
let a = vec![1, 2, 3]
print_vector(a);
println!("{}", a);   // Compilation error!!!

By using a as a parameter to print_vector, you transfer ownership to print_vector's local variable v. When v goes out of scope as the function ends, the compiler knows to destroy the vector. Using a afterwards is a compilation error.

If we just had these ownership rules, programming in Rust would be very hard to do, because as soon as you call a function, you've lost the use of your variables. This is where borrowing comes in.

Borrowing

When you own a book and you want to let someone else read it, but still want to own the book afterwards, you lend it. That is, the other person receiving your book 'borrows' it with the understanding that they will give it back. This is essentially Rust's borrowing model.

But there's slightly more to it. When you lend out some data, you can choose to do it mutably or immutably. That is, the borrower may have permission to change the data, or not. This is important. Rust allows infinite immutable borrows as long as there is not a single mutable borrow. Likewise, Rust allows only a single mutable borrow, if and only if, there are no immutable borrows. This simple rule makes data races impossible. Put a different way, if your function has a mutable borrow, you know for a fact that it is the ONLY reference to the data and you're free to change it.

A borrow in Rust is symbolised by a & symbol before the type. You are essentially creating a pointer. Looking at an example:

let a = vec![1, 2, 3];
let b = &a;
let c = &a;

This time line 3 is allowed and this code will compile. Rust allows as many immutable references (they are immutable by default) as you would like. Also bear in mind that the owner can still mutate the vector as in this example:

let mut a = vec![1, 2, 3];
let b = &a;
let c = &a;
a.push(4);

But didn't we break the rule that we can't mutate data if we have immutable borrows? No, because Rust is smart enough to see, in this example, that b and c are not used any more and a is free to mutate its data.

If we had this, however:

let mut a = vec![1, 2, 3];
let b = &a;
let c = &a;
a.push(4);
println!("{:?}", b);

then we would have a compilation error. By using b in the println! statement, we are using an immutable borrow at the same time as we are mutating the data. Remember, as in the C++ example above, pushing more data can move the memory used by the vector and invalidate b and c causing a use-after-free bug.

To mutably borrow we use the mut keyword after the &. Let us look at the increment_counter function above rewritten in Rust:

fn increment_counter(counter: &mut i32) {
    *counter = *counter + 1;
}

Note, you can't have global mutable variables in Rust unless you use the unsafe keyword to change them, so we pass it as a parameter. We're only talking about safe Rust in this article for now.

Also note, for mutable borrows you must use the * operator to dereference them.

Slices

Slices are views on an area of memory. They are sometimes called fat pointers. They consist of a pointer and a length. Unlike C++, where a pointer can pointer to a single or multiple values, in Rust a better distinction is made. A borrow, mutable or otherwise, always references a single data value. To reference multiple data values, slices are used.

Slices cannot own data because, by definition, they are views on already existing data. So they are borrows. You can always identify a slice by the type &[T] where T is any data type. Without the ampersand, the type [T] is just a fixed array and needs to be owned.

Indexing a slice at runtime incurs a bounds check. Trying to access a slice using an index that is equal or larger than its size will cause a panic and your program will exit if the panic is not trapped. This stops the buffer overflow bug. Also, buffer underflows cannot occur because slice indices are always unsigned. That is, you cannot have an index less than 0.

As in other borrows, mutable slices are written as &mut [T].

Also, in Rust there is a type str, which is an alias for [char], so whenever you see &str, think of it as a slice of a character array. String literals will have the type &str as they are sliced views on static data in your executable. So in this code:

let a = "hello";

a is of type &str.

Lifetimes

If you store a borrowed reference to some data and its owner goes out of scope, will you not have a dangling pointer? In short, no, and that is where lifetimes come in.

Every variable in Rust has a lifetime and Rust ensures that ALL borrowed references have the same lifetime or shorter than the owner that lent the reference. So in the example above, Rust would not allow you to assign a borrowed reference to another variable unless Rust could prove that the variable had a equal or shorter lifetime than the owner.

This means, that when the owner goes out of scope, Rust knows for a fact there are no other references and it is safe to destroy the data.

Lifetime syntax is written as 'name where name can be anything. Usually, these lifetime annotations can be implied. For example, when you write:

fn substr(s: &str, index: usize, len: usize) -> &str;

the compiler is really seeing:

fn substr<'a>(s: &'a str, index: usize, len: usize) -> &'a str;

I have chosen a as the name of the lifetime. And as you can see, the lifetime of the result must match the lifetime of the input parameter s. This makes sense as the function will return a reference to the data passed in as s. Notice, that the lifetime annotation is declared within <...> next to the function's name.

The implied lifetime annotations are called lifetime elision. Rust has various rules for eliding lifetimes. If your function is more complicated, the compiler might complain and you will have to add the annotations yourself. If you're interested you can find more information here.

There is another lifetime that data can have and that is 'static. This means that the data lasts as long as the program itself. Functions have lifetimes of 'static for example. Also literal strings are immutable character slices (i.e. &str) with a lifetime of 'static.

Another place where lifetime annotation occurs is if you have references (immutably borrowed or otherwise) inside structures. For example:

struct Person {
    name: &str,
    age: u32,
}

will give a compilation error:

error[E0106]: missing lifetime specifier
 --> test.rs:2:11
  |
2 |     name: &str,
  |           ^ expected named lifetime parameter
  |
help: consider introducing a named lifetime parameter
  |
1 | struct Person<'a> {
2 |     name: &'a str,
  |

and the Rust compiler will give you a nice hint on how to fix it. This ensures that an instance of the Person structure cannot outlive the data that name references. If it did, we'd have a dangling pointer.

Summary of Syntax

Below, for convenience, I summarise the syntax used for the different types of data:

Bugs begone!

I'd like to go over the different bug classes again and discuss how Rust makes them impossible.

Use After Free

Ownership and lifetime rules ensure that when the owner finally needs to be destroyed, there are no other references to it. This is because references caused by borrowing cannot outlive the owners.

Double Delete

Deletion can only occur when the owner goes out of scope. Because Rust only allows a single owner of data, there cannot be another owner going out of scope later. You cannot delete data via a borrowed reference either.

Uninitialised Data

I didn't talk about this before, but Rust insists on all new variables to be initialised. You cannot do this, for example:

let mut a: i32;
println!("{}", a);
a = 42;

a is undefined when println! is executed and so the compiler stops this from happening. However, it is OK to initialise a on a different statement as long as you don't use a before you do so:

// This is OK
let a: i32;
a = 42;

Note that a doesn't even have to be defined mut because Rust sees that the a = 42 statement is in fact an initialisation and not a mutation.

Buffer Overflow and Underflow

Buffer overflows are impossible because Rust, at compile time and runtime, bounds-checks array accesses. Any violation will result in a panic.

Buffer underflows are impossible because you cannot use signed indices.

Null Dereferencing

Safe Rust doesn't allow you to dereference pointers. Also, borrowed references cannot be null either. Therefore, it is impossible to dereference a null pointer. If you do wish to have a type that could point to some data or not, Rust provides the Option enum, which I will be visiting in my next blog.

Data Races

Rust does not allow more than one mutable reference (via borrowing or ownership), and it doesn't allow any mutable references if a single immutable reference exists. This means that given a mutable reference, Rust guarantees that this is the only way you can mutate it at that time. Therefore, data races cannot occur.

A Word about the Copy Trait

When I said that passing a variable to a function or assigning it to another transfers ownership, I was telling you half the story. For some built-in types, by default, are marked by the Copy trait. I will talk about traits another time, but essentially it means that the type is marked with a property. That property allows the compiler to copy the data byte-for-byte into the new variable or parameter. This means that ownership is not transferred but a new owner is created with a copy of the data.

This is why in the examples above I used vectors to demonstrate transfer of ownership as Vec does not implement the Copy trait. Types that do implement it are so-called POD types (Pieces Of Data) such as i32, u32, f32, char etc. Because of this, the following code is correct:

let a = 42; // a is an i32, which implements the Copy trait
let b = a;
let c = a;

Both b and c become owners of the copy of a's data. So, both b and c will hold the value 42.

You can also implement the Copy trait easily for a structure as long as all its fields also implement the Copy trait:

#[derive(Copy, Clone)]
struct Person {
    name: String,
    age: u32,
}

Also note that the Clone trait must also be implemented if Copy is. The Clone trait provides the clone() method on the type and is required to do the actual copy. After adding the #[derive(Copy, Clone)] statement, this code is possible:

let p = Person { name: String::from("Matt"), age: 48 };
let a = p;
let b = p;

Both b and c will hold different instances of Person but contain the same values.

Conclusion

I hope this helps with groking what borrowing an ownership means and how it a) avoids memory bugs; and b) allows the compiler to deallocate data at the right time so Rust does not need a garbage collector.

Please let me know in the discussion if there are details I have wrong or left out. I am always interested in improving this text.

Next blog will talk about Option and Result enum types.