Rust: A Unique Perspective (2019)

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.

Unique access

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.

Unique ownership

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 y

For 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 y

In 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 owns the T items inside
it, and a Box owns the T that it points to.

Unique borrowing

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.

Unique references can’t be copied

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 here

However, 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.

Shared access

A 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.

Shared ownership

One way to share a value of type T is to create an Rc, 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 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 memory

Because 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.

Shared borrowing

Since Rc doesn’t have unique access to its T, it can’t give out a
unique &mut T reference (unless it checks at run time that the reference
count is equal to 1, so it is not actually shared). But it can give out a
shared reference to T, whose type is written &T. (This is also called
an “immutable reference.”)

A shared reference is another “borrowed” type which can’t outlive its
referent. 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).

Thread safety

Astute readers might notice that merely cloning an Rc 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 T on a single other thread,
  where one thread at a time has exclusive access. 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 implements neither of these traits, so an Rc 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 type, which is exactly like
Rc except that it implements Send, and uses atomic operations to
synchronize access to its reference counts. This can make Arc 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 or &T).

Shared mutability

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 could go wrong?

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 reference 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).

UnsafeCell

To fix the problem of aliasing assumptions, we need UnsafeCell. 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 solves only one of the three problems listed above. Next, we’ll
see some ways to solve the other two problems: pointer invalidation and data
races.

Multi-threaded shared mutability

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 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 at the
  same time, the second thread 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 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 capture shared references like &Mutex instead of
Arc>.

Single-threaded shared mutability

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 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 is okay, because there are no shared pointers to that data – only to
  the Cell 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 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, 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.

Summary

To summarize some key ideas:

• Rust has two types of references: unique and shared.
• Unique mutable access is easy.
• Shared immutable access is easy.
• Shared mutable access is hard.
• This is true for both single-threaded and multi-threaded programs.

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:

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.

Want to know more?

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.