07 Feb 2019

Rust: A unique perspective

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<T> owns the T items inside it, and a Box<T> 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<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 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<T> 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<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 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<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).

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<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 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<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 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<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 capture shared references like &Mutex<T> instead of Arc<Mutex<T>>.

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

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:

	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.

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.

from Hacker News https://ift.tt/zQw3dq0