07 Feb 2019
The Rust programming language is designed to ensure memory safety, using a mix of compile-time and run-time checks to stop programs from accessing invalid pointers or sharing memory across threads without proper synchronization.
The way Rust does this is usually introduced in terms of mutable and immutable borrowing and lifetimes. This makes sense, because these are mechanisms that Rust programmers must use directly. They describe what the Rust compiler checks when it compiles a program.
However, there is another way to explain Rust. This alternate story focuses on unique versus shared access to memory. I believe this version is useful for understanding why various checks exist and how they provide memory safety.
Most experienced Rust programmers are already familiar with this concept.
Five years ago, Niko Matsakis even proposed changing the “mut” keyword to
“uniq” to emphasize it. My goal is to make these important
ideas more accesssible to beginning and intermediate Rust programmers.
This is a very quick introduction that skips over many details to focus on high-level concepts. It should complement the official Rust documentation, not supplant it.
The first key observation is: If a variable has unique access to a value, then it is safe to mutate it.
By safe, I mean memory-safe: free from invalid pointer accesses, data races, or other causes of undefined behavior. And by unique access, I mean that while this variable is alive, there are no other variables that can be used to read or write any part of the same value.
Unique access makes memory safety very simple: If there are no other pointers to the value, then you don’t need to worry about invalidating them. Similarly, if variables on other threads can’t access the value, you needn’t worry about synchronization.
One form of unique access is ownership. When you initialize a variable with a value, it becomes the sole owner of that value. Because the value has just one owner, the owner can safely mutate the value, destroy it, or transfer it to a new owner.
Depending on the type of the value, assigning a value to a new variable will either move it or copy it. Either way, unique ownership is preserved. For a move type, the old owner becomes inaccessible after the move, so we still have one value owned by one variable:
let x = vec![1, 2, 3];
let y = x; // move ownership from x to y
// can’t access x after moving its value to yFor a copy type, the value is duplicated, so we end up with two values owned by two variables:
let x = 1;
let y = x; // copy the value of x into yIn this case, each variable ends up with a separate, independent value. Mutating one will not affect the other.
One value might be owned by another value, rather than directly by a variable.
For example, a struct owns its fields, a Vec<T> owns the T items inside
it, and a Box<T> owns the T that it points to.
If you have unique access to a value of type T, you can borrow a unique
reference to that value. A unique reference to a T has type &mut T.
Because it’s safe to mutate when you have a unique reference, unique references are also called “mutable references.“
The Rust compiler enforces this uniqueness at compile time. In any region of code where the unique reference may be used, no other reference to any part of the same value may exist, and even the owner of that value may not move or destroy it. Violating this rule triggers a compiler error.
A reference only borrows the value, and must return it to its owner.
This means that the reference can be used to mutate the value, but not to move
or destroy it (unless it overwrites it with a new value, for example using
replace). Just like in real life, you need to give back what you’ve
borrowed.
Borrowing a value is like locking it. Just like a mutex lock in a multi-threaded program, it’s usually best to hold a borrowed reference for as little time as possible. Storing a unique reference in a long-lived data structure will prevent any other use of the value for as long as that structure exists.
An &mut T cannot be copied or cloned, because this would result in
two ”unique” references to the same value. It can only be moved:
let mut a = 1;
let x = &mut a;
let y = x; // move the reference from x into y
// x is no longer accessible hereHowever, you can temporarily ”re-borrow” from a unique reference. This gives a new unique reference to the same value, but the original reference can no longer be accessed until the new one goes out of scope or is no longer used (depending on which version of Rust you are using):
let mut a = 1;
let x = &mut a;
{
let y = &mut *x;
// x is "re-borrowed" and cannot be used while y is alive
*y = 4; // y has unique access and can mutate `a`
}
// x becomes accessible again after y is dead
*x += 1; // now x has unique access again and can mutate the value
assert_eq!(*x, 5);Re-borrowing happens implicitly when you call a function that takes a unique reference. This greatly simplifies code that passes unique references around, but can confuse programmers who are just learning about these restrictions.
fn f(n: &mut i32) { *n = 2 }
let mut a = 1;
let x = &mut a;
f(x); // x is re-borrowed rather than moved
dbg!(*x); // x is accessible again hereA value is shared if there are multiple variables that are alive at the same time that can be used to access it.
While a value is shared, we have to be a lot more careful about mutating it. Writing to the value through one variable could invalidate pointers held by other variables, or cause a data race with readers or writers on other threads.
Rust ensures that you can read from a value only while no variables can write to it, and you can write to a value only while no other variables can read or write to it. In other words, you can have a unique writer, or multiple readers, but not both at once. Some Rust types enforce this at compile time and others at run time, but the principle is always the same.
One way to share a value of type T is to create an Rc<T>, or
“reference-counted pointer to T”. This allocates space on the heap for a T,
plus some extra space for reference counting (tracking the number of pointers
to the value). Then you can call Rc::clone to increment the reference count
and receive another Rc<T> that points to the same value:
let x = Rc::new(1);
let y = x.clone();
// x and y hold two different Rc that point to the same memoryBecause the T lives on the heap and x and y just hold pointers to it, it
can outlive any particular pointer. It will be destroyed only when the last
of the pointers is dropped. This is called shared ownership.
A shared reference to T, or &T, is another “borrowed” type which can’t
outlive its referent. This is also called an “immutable reference.”
The compiler ensures that a shared reference can’t be created while a unique reference exists to any part of the same value, and vice-versa. And (just like unique references) the owner isn’t allowed to drop/move/mutate the value while any shared references are alive.
If you have unique access to a value, you can produce many shared references
or one unique reference to it. However, if you only have shared access to a
value, you can’t produce a unique reference (at least, not without some
additional checks, which I’ll discuss soon). One consequence of this is that
you can convert an &mut T to an &T, but not vice-versa.
Because multiple shared references are allowed, an &T can be copied/cloned
(unlike &mut T).
let mut a = 1;
let x = &a;
let y = x; // copy the reference
// both x and y are accessible hereAstute readers might notice that merely cloning an Rc<T> mutates a value in
memory, since it modifies the reference count. This could cause a data race
if another clone of the Rc were accessed at the same time on a different
thread! The compiler solves this in typical Rust fashion: By refusing to
compile any program that passes an Rc to a different thread.
Rust has two built-in traits that it uses to mark types that can be accessed safely by other threads:
T: Send means it’s safe to access a value of T on any thread,
if that thread has exclusive access to that value. A value of this type
can be moved to another thread by unique ownership, or borrowed on another
thread by unique reference (&mut T). A more descriptive name for this
trait might be UniqueThreadSafe.
T: Sync means it’s safe for many threads to access a T
simultaneously, with each thread having shared access.
Values of such types can be accessed on other threads via shared ownership
or shared references (&T). A more descriptive name would be
SharedThreadSafe.
Rc<T> implements neither of these traits, so an Rc<T> cannot be moved or
borrowed into a variable on a different thread. It is forever trapped on the
thread where it was born.
The standard library also offers an Arc<T> type, which is exactly like
Rc<T> except that it implements Send, and uses atomic operations to
synchronize access to its reference counts. This can make Arc<T> a little
more expensive at run time, but it allows multiple threads to share a value
safely.
These traits are not mutually exclusive. Many types are both Send and
Sync, meaning that it’s safe to give unique access to one other thread (for
example, moving the value itself or sending an &mut T reference) or shared
access to many threads (for example, sending multiple Arc<T> or &T).
So far, we’ve seen that sharing is safe when values are not mutated, and mutation is safe when values are not shared. But what if we want to share and mutate a value? The Rust standard library provides several different mechanisms for shared mutability.
The official documentation also calls this “interior mutability” because it lets you mutate a value that is “inside” of an immutable value. This terminology can be confusing: What does it mean for the exterior to be “immutable” if its interior is mutable? I prefer “shared mutability” which puts the spotlight on a different question: How can you safely mutate a value while it is shared?
What’s the big deal about shared mutation? Let’s start by listing some of the ways it could go wrong:
First, mutating a value can cause pointer invalidation. For example, pushing to a vector might cause it to reallocate its buffer. If there are other variables that contained addresses of items in the buffer, they would now point to deallocated memory. Or, mutating an enum might overwrite a value of one type with a value of a different type. A pointer to the old value will now be pointing at memory occupied by the wrong type. Either of these cases would trigger undefined behavior.
Second, it could violate aliasing assumptions. For example, the optimizing
compiler assumes by default that the referent of an &T will not
change while the reference exists. It might re-order code based on this
assumption, leading to undefined behavior when the assumption is violated.
Third, if one thread mutates a value at the same time that another thread is accessing it, this causes a data race unless both threads use synchronization primitives to prevent their operations from overlapping. Data races can cause arbitrary undefined behavior (in part because data races can also violate assumptions made by the optimizer during code generation).
To fix the problem of aliasing assumptions, we need UnsafeCell<T>. The
compiler knows about this type and treats it specially: It tells the optimizer
that the value inside an UnsafeCell is not subject to the usual restrictions
on aliasing.
Safe Rust code doesn’t use UnsafeCell directly. Instead, it’s used by
libraries (including the standard library) that provide APIs for safe shared
mutability. All of the shared mutable types discussed in the following
sections use UnsafeCell internally.
UnsafeCell alone solves only one of the three problems listed above (the
compiler’s aliasing assumptions). To provide safe shared mutation, we will
also need to solve the other two problems: pointer invalidation and data
races.
Rust programs can safely mutate a value that’s shared across threads, as long as the basic rules of unique and shared access are enforced: Only one thread at a time may have unique access to a value, and only this thread can mutate it. When no thread has unique access, then many threads may have shared access, but the value can’t be mutated while they do.
Rust has two main types that allow thread-safe shared mutation:
Mutex<T> allows one thread at a time to “lock” a mutex and get unique
access to its contents. If a second thread tries to lock the mutex, it will
block until the first thread unlocks it. Since Mutex provides access to
only one thread at a time, it can be used to share any type that implements
the Send (“unique thread-safe”) trait.
RwLock<T> is similar but has two different types of lock: A “write”
lock that provides unique access, and a “read” lock that provides shared
access. It will allow many threads to hold read locks at the same time, but
only one thread can hold a write lock. If one thread tries to write while
other threads are reading (or vice-versa), it will block until the other
threads release their locks. Since RwLock provides both unique and shared
access, its contents must implement both Send (“unique thread-safe”) and
Sync (“shared thread-safe”).
These types prevent pointer invalidation by using run-time checks to enforce the rules of unique and shared borrowing. They prevent data races by using synchronization primitives provided by the platform’s native threading system.
In addition, various atomic types allow safe shared mutation of individual primitive values. These prevent data races by using compiler intrinsics that provide synchronized operations, and they prevent pointer invalidation by refusing to give out references to their contents; you can only read from them or write to them by value.
All these types are only useful when shared by multiple threads, so they are
often used in combination with Arc. Because Arc lets multiple threads
share ownership of a value, it works with threads that might outlive the
function that spawns them (and therefore can’t borrow references from it).
However, scoped threads are guaranteed to terminate before their spawning
function, so they can use shared borrowing (&Mutex<T>) instead of
shared ownership (Arc<Mutex<T>>).
The standard library also has two types that allow safe shared mutation
within a single thread. These types don’t implement the Sync trait, so the
compiler won’t let you share them across multiple threads. This neatly avoids
data races, and also means that these types don’t need atomic operations
(which are potentially expensive).
Cell<T> solves the problem of pointer invalidation by forbidding
pointers to its contents. Like the atomic types mentioned above, you can only
read from it or write to it by value. Changing the data “inside” of the
Cell<T> is okay, because there are no shared pointers to that data – only to
the Cell<T> itself, whose type and address do not change when you mutate its
interior. (Now we see why “interior mutability” is also a useful concept.)
Many Rust types are useless without references, so Cell is often too
restrictive. RefCell<T> allows you to borrow either unique or shared
references to its contents, but it keeps count of how many borrowers are alive
at a time. Like RwLock, it allows one unique reference or many shared
references, but not both at once. It enforces this rule using run-time
checks. (But since it’s used within a single thread, it can’t block the
thread while waiting for other borrowers to finish. Instead, it panics
if a program violates its borrowing rules.)
These types are often used in combination with Rc<T>, so that a value shared
by multiple owners can still be mutated safely. They may also be used for
mutating values behind shared references. The std::cell docs have some
examples.
To summarize some key ideas:
We also saw a couple of ways to classify Rust types. Here’s a table showing some of the most common types according to this classification scheme:
| Unique | Shared | |
|---|---|---|
| Borrowed | &mut T |
&T |
| Owned | T, Box<T> |
Rc<T>, Arc<T> |
I hope that thinking of these types in terms of uniqueness and sharing will help you understand how and why they work, as it helped me.
As I said at the start, this is just a quick introduction and glosses over many details. The exact rules about unique and shared access in Rust are still being worked out. The Aliasing chapter of the Rustonomicon explains more, and Ralf Jung’s Stacked Borrows model is the start of a more complete and formal definition of the rules.
If you want to know more about how shared mutability can lead to memory-unsafety, read The Problem With Single-threaded Shared Mutability by Manish Goregaokar.
The Swift language has an approach to memory safety that is similar in some ways, though its exact mechanisms are different. You might be interested in its recently-introduced Exclusivity Enforcement feature, and the Ownership Manifesto that originally described its design and rationale.