Chapter 1. Basics of Rust Concurrency

Statics

There are several ways to create something that’s not owned by a single thread. The simplest one is a static value, which is "owned" by the entire program, instead of an individual thread. In the following example, both threads can access X, but neither of them owns it:

static X: [i32; 3] = [1, 2, 3];

thread::spawn(|| dbg!(&X));
thread::spawn(|| dbg!(&X));

A static item has a constant initializer, is never dropped, and already exists before the main function of the program even starts. Every thread can borrow it, since it’s guaranteed to always exist.

Leaking

Another way to share ownership is by leaking an allocation. Using Box::leak, one can release ownership of a Box, promising to never drop it. From that point on, the Box will live forever, without an owner, allowing it to be borrowed by any thread for as long as the program runs.

let x: &'static [i32; 3] = Box::leak(Box::new([1, 2, 3]));

thread::spawn(move || dbg!(x));
thread::spawn(move || dbg!(x));

The move closure might make it look like we’re moving ownership into the threads, but a closer look at the type of x reveals that we’re only giving the threads a reference to the data.

Note how the 'static lifetime doesn’t mean that the value lived since the start of the program, but only that it lives to the end of the program. The past is simply not relevant.

The downside of leaking a Box is that we’re leaking memory. We allocate something, but never drop and deallocate it. This can be fine if it happens only a limited number of times. But if we keep doing this, the program will slowly run out of memory.

Reference Counting

To make sure that shared data gets dropped and deallocated, we can’t completely give up its ownership. Instead, we can share ownership. By keeping track of the number of owners, we can make sure the value is dropped only when there are no owners left.

The Rust standard library provides this functionality through the std::rc::Rc type, short for "reference counted." It is very similar to a Box, except cloning it will not allocate anything new, but instead increment a counter stored next to the contained value. Both the original and cloned Rc will refer to the same allocation; they share ownership.

use std::rc::Rc;

let a = Rc::new([1, 2, 3]);
let b = a.clone();

assert_eq!(a.as_ptr(), b.as_ptr()); // Same allocation!

Dropping an Rc will decrement the counter. Only the last Rc, which will see the counter drop to zero, will be the one dropping and deallocating the contained data.

If we were to try to send an Rc to another thread, however, we would run into the following compiler error:

error[E0277]: `Rc` cannot be sent between threads safely
    |
8   |     thread::spawn(move || dbg!(b));
    |                   ^^^^^^^^^^^^^^^

As it turns out, Rc is not thread safe (more on that in "Thread Safety: Send and Sync"). If multiple threads had an Rc to the same allocation, they might try to modify the reference counter at the same time, which can give unpredictable results.

Instead, we can use std::sync::Arc, which stands for "atomically reference counted." It’s identical to Rc, except it guarantees that modifications to the reference counter are indivisible atomic operations, making it safe to use it with multiple threads. (More on that in Chapter 2.)

use std::sync::Arc;

let a = Arc::new([1, 2, 3]); 1
let b = a.clone(); 2

thread::spawn(move || dbg!(a)); 3
thread::spawn(move || dbg!(b)); 3

Because ownership is shared, reference counting pointers (Rc<T> and Arc<T>) have the same restrictions as shared references (&T). They do not give you mutable access to their contained value, since the value might be borrowed by other code at the same time.

For example, if we were to try to sort the slice of integers in an Arc<[i32]>, the compiler would stop us from doing so, telling us that we’re not allowed to mutate the data:

error[E0596]: cannot borrow data in an `Arc` as mutable
  |
6 |     a.sort();
  |     ^^^^^^^^

Cell

A std::cell::Cell<T> simply wraps a T, but allows mutations through a shared reference. To avoid undefined behavior, it only allows you to copy the value out (if T is Copy), or replace it with another value as a whole. In addition, it can only be used within a single thread.

Let’s take a look at an example similar to the one in the previous section, but this time using Cell<i32> instead of i32:

use std::cell::Cell;

fn f(a: &Cell<i32>, b: &Cell<i32>) {
    let before = a.get();
    b.set(b.get() + 1);
    let after = a.get();
    if before != after {
        x(); // might happen
    }
}

Unlike last time, it is now possible for the if condition to be true. Because a Cell<i32> has interior mutability, the compiler can no longer assume its value won’t change as long as we have a shared reference to it. Both a and b might refer to the same value, such that mutating through b might affect a as well. It may still assume, however, that no other threads are accessing the cells concurrently.

The restrictions on a Cell are not always easy to work with. Since it can’t directly let us borrow the value it holds, we need to move a value out (leaving something in its place), modify it, then put it back, to mutate its contents:

fn f(v: &Cell<Vec<i32>>) {
    let mut v2 = v.take(); // Replaces the contents of the Cell with an empty Vec
    v2.push(1);
    v.set(v2); // Put the modified Vec back
}

RefCell

Unlike a regular Cell, a std::cell::RefCell does allow you to borrow its contents, at a small runtime cost. A RefCell<T> does not only hold a T, but also holds a counter that keeps track of any outstanding borrows. If you try to borrow it while it is already mutably borrowed (or vice-versa), it will panic, which avoids undefined behavior. Just like a Cell, a RefCell can only be used within a single thread.

Borrowing the contents of RefCell is done by calling borrow or borrow_mut:

use std::cell::RefCell;

fn f(v: &RefCell<Vec<i32>>) {
    v.borrow_mut().push(1); // We can modify the `Vec` directly.
}

While Cell and RefCell can be very useful, they become rather useless when we need to do something with multiple threads. So let’s move on to the types that are relevant for concurrency.

Mutex and RwLock

An RwLock or reader-writer lock is the concurrent version of a RefCell. An RwLock<T> holds a T and tracks any outstanding borrows. However, unlike a RefCell, it does not panic on conflicting borrows. Instead, it blocks the current thread—​putting it to sleep—​while waiting for conflicting borrows to disappear. We’ll just have to patiently wait for our turn with the data, after the other threads are done with it.

Borrowing the contents of an RwLock is called locking. By locking it we temporarily block concurrent conflicting borrows, allowing us to borrow it without causing data races.

A Mutex is very similar, but conceptually slightly simpler. Instead of keeping track of the number of shared and exclusive borrows like an RwLock, it only allows exclusive borrows.

We’ll go more into detail on these types in "Locking: Mutexes and RwLocks".

Atomics

The atomic types represent the concurrent version of a Cell, and are the main topic of Chapters 2 and 3. Like a Cell, they avoid undefined behavior by making us copy values in and out as a whole, without letting us borrow the contents directly.

Unlike a Cell, though, they cannot be of arbitrary size. Because of this, there is no generic Atomic<T> type for any T, but there are only specific atomic types such as AtomicU32 and AtomicPtr<T>. Which ones are available depends on the platform, since they require support from the processor to avoid data races. (We’ll dive into that in Chapter 7.)

Since they are so limited in size, atomics often don’t directly contain the information that needs to be shared between threads. Instead, they are often used as a tool to make it possible to share other—​often bigger—​things between threads. When atomics are used to say something about other data, things can get surprisingly complicated.

UnsafeCell

An UnsafeCell is the primitive building block for interior mutability.

An UnsafeCell<T> wraps a T, but does not come with any conditions or restrictions to avoid undefined behavior. Instead, its get() method just gives a raw pointer to the value it wraps, which can only be meaningfully used in unsafe blocks. It leaves it up to the user to use it in a way that does not cause any undefined behavior.

Most commonly, an UnsafeCell is not used directly, but wrapped in another type that provides safety through a limited interface, such as Cell or Mutex. All types with interior mutability—​including all types discussed above—​are built on top of UnsafeCell.

Rust’s Mutex

The Rust standard library provides this functionality through std::sync::Mutex<T>. It is generic over a type T, which is the type of the data the mutex is protecting. By making this T part of the mutex, the data can only be accessed through the mutex, allowing for a safe interface that can guarantee all threads will uphold the agreement.

To ensure a locked mutex can only be unlocked by the thread that locked it, it does not have an unlock() method. Instead, its lock() method returns a special type called a MutexGuard. This guard represents the guarantee that we have locked the mutex. It behaves like an exclusive reference through the DerefMut trait, giving us exclusive access to the data the mutex protects. Unlocking the mutex is done by dropping the guard. When we drop the guard, we give up our ability to access the data, and the Drop implementation of the guard will unlock the mutex.

Let’s take a look at an example to see a mutex in practice:

use std::sync::Mutex;

fn main() {
    let n = Mutex::new(0);
    thread::scope(|s| {
        for _ in 0..10 {
            s.spawn(|| {
                let mut guard = n.lock().unwrap();
                for _ in 0..100 {
                    *guard += 1;
                }
            });
        }
    });
    assert_eq!(n.into_inner().unwrap(), 1000);
}

Here, we have a Mutex<i32>, a mutex protecting an integer, and we spawn ten threads to each increment the integer one hundred times. Each thread will first lock the mutex to obtain a MutexGuard, and then use that guard to access the integer and modify it. The guard is implicitly dropped right after, when that variable goes out of scope.

After the threads are done, we can safely remove the protection from the integer through into_inner(). The into_inner method takes ownership of the mutex, which guarantees that nothing else can have a reference to the mutex anymore, making locking unnecessary.

Even though the increments happen in steps of one, a thread observing the integer would only ever see multiples of 100, since it can only look at the integer when the mutex is unlocked. Effectively, thanks to the mutex, the one hundred increments together are now a single indivisible—​atomic—​operation.

To clearly see the effect of the mutex, we can make each thread wait a second before unlocking the mutex:

use std::time::Duration;

fn main() {
    let n = Mutex::new(0);
    thread::scope(|s| {
        for _ in 0..10 {
            s.spawn(|| {
                let mut guard = n.lock().unwrap();
                for _ in 0..100 {
                    *guard += 1;
                }
                thread::sleep(Duration::from_secs(1)); // New!
            });
        }
    });
    assert_eq!(n.into_inner().unwrap(), 1000);
}

When you run the program now, you will see that it takes about 10 seconds to complete. Each thread only waits for one second, but the mutex ensures that only one thread at a time can do so.

If we drop the guard—and therefore unlock the mutex—before sleeping one second, we will see it happen in parallel instead:

fn main() {
    let n = Mutex::new(0);
    thread::scope(|s| {
        for _ in 0..10 {
            s.spawn(|| {
                let mut guard = n.lock().unwrap();
                for _ in 0..100 {
                    *guard += 1;
                }
                drop(guard); // New: drop the guard before sleeping!
                thread::sleep(Duration::from_secs(1));
            });
        }
    });
    assert_eq!(n.into_inner().unwrap(), 1000);
}

With this change, this program takes only about one second, since now the 10 threads can execute their one-second sleep at the same time. This shows the importance of keeping the amount of time a mutex is locked as short as possible. Keeping a mutex locked longer than necessary can completely nullify any benefits of parallelism, effectively forcing everything to happen serially instead.

Lock Poisoning

The unwrap() calls in the examples above relate to lock poisoning.

A Mutex in Rust gets marked as poisoned when a thread panics while holding the lock. When that happens, the Mutex will no longer be locked, but calling its lock method will result in an Err to indicate it has been poisoned.

This is a mechanism to protect against leaving the data that’s protected by a mutex in an inconsistent state. In our example above, if a thread would panic after incrementing the integer fewer than 100 times, the mutex would unlock and the integer would be left in an unexpected state where it is no longer a multiple of 100, possibly breaking assumptions made by other threads. Automatically marking the mutex as poisoned in that case forces the user to handle this possibility.

Calling lock() on a poisoned mutex still locks the mutex. The Err returned by lock() contains the MutexGuard, allowing us to correct an inconsistent state if necessary.

While lock poisoning might seem like a powerful mechanism, recovering from a potentially inconsistent state is not often done in practice. Most code either disregards poison or uses unwrap() to panic if the lock was poisoned, effectively propagating panics to all users of the mutex.

Reader-Writer Lock

A mutex is only concerned with exclusive access. The MutexGuard will provide us an exclusive reference (&mut T) to the protected data, even if we only wanted to look at the data and a shared reference (&T) would have sufficed.

A reader-writer lock is a slightly more complicated version of a mutex that understands the difference between exclusive and shared access, and can provide either. It has three states: unlocked, locked by a single writer (for exclusive access), and locked by any number of readers (for shared access). It is commonly used for data that is often read by multiple threads, but only updated once in a while.

The Rust standard library provides this lock through the std::sync::RwLock<T> type. It works similarly to the standard Mutex, except its interface is mostly split in two parts. Instead of a single lock() method, it has a read() and write() method for locking as either a reader or a writer. It comes with two guard types, one for readers and one for writers: RwLockReadGuard and RwLockWriteGuard. The former only implements Deref to behave like a shared reference to the protected data, while the latter also implements DerefMut to behave like an exclusive reference.

It is effectively the multi-threaded version of RefCell, dynamically tracking the number of references to ensure the borrow rules are upheld.

Both Mutex<T> and RwLock<T> require T to be Send, because they can be used to send a T to another thread. An RwLock<T> additionally requires T to also implement Sync, because it allows multiple threads to hold a shared reference (&T) to the protected data. (Strictly speaking, you can create a lock for a T that doesn’t fulfill these requirements, but you wouldn’t be able to share it between threads as the lock itself won’t implement Sync.)

The Rust standard library provides only one general purpose RwLock type, but its implementation depends on the operating system. There are many subtle variations between reader-writer lock implementations. Most implementations will block new readers when there is a writer waiting, even when the lock is already read-locked. This is done to prevent writer starvation, a situation where many readers collectively keep the lock from ever unlocking, never allowing any writer to update the data.

Thread Parking

One way to wait for a notification from another thread is called thread parking. A thread can park itself, which puts it to sleep, stopping it from consuming any CPU cycles. Another thread can then unpark the parked thread, waking it up from its nap.

Thread parking is available through the std::thread::park() function. For unparking, you call the unpark() method on a Thread object representing the thread that you want to unpark. Such an object can be obtained from the join handle returned by spawn, or by the thread itself through std::thread::current().

Let’s dive into an example that uses a mutex to share a queue between two threads. In the following example, a newly spawned thread will consume items from the queue, while the main thread will insert a new item into the queue every second. Thread parking is used to make the consuming thread wait when the queue is empty.

use std::collections::VecDeque;

fn main() {
    let queue = Mutex::new(VecDeque::new());

    thread::scope(|s| {
        // Consuming thread
        let t = s.spawn(|| loop {
            let item = queue.lock().unwrap().pop_front();
            if let Some(item) = item {
                dbg!(item);
            } else {
                thread::park();
            }
        });

        // Producing thread
        for i in 0.. {
            queue.lock().unwrap().push_back(i);
            t.thread().unpark();
            thread::sleep(Duration::from_secs(1));
        }
    });
}

The consuming thread runs an infinite loop in which it pops items out of the queue to display them using the dbg macro. When the queue is empty, it stops and goes to sleep using the park() function. If it gets unparked, the park() call returns, and the loop continues, popping items from the queue again until it is empty. And so on.

The producing thread produces a new number every second by pushing it into the queue. Every time it adds an item, it uses the unpark() method on the Thread object that refers to the consuming thread to unpark it. That way, the consuming thread gets woken up to process the new element.

An important observation to make here is that this program would still be theoretically correct, although inefficient, if we remove parking. This is important, because park() does not guarantee that it will only return because of a matching unpark(). While somewhat rare, it might have spurious wake-ups. Our example deals with that just fine, because the consuming thread will lock the queue, see that it is empty, and directly unlock it and park itself again.

An important property of thread parking is that a call to unpark() before the thread parks itself does not get lost. The request to unpark is still recorded, and the next time the thread tries to park itself, it clears that request and directly continues without actually going to sleep. To see why that is critical for correct operation, let’s go through a possible ordering of the steps executed by both threads:

1. The consuming thread—let’s call it C—locks the queue.

2. C tries to pop an item from the queue, but it is empty, resulting in None.

3. C unlocks the queue.

4. The producing thread, which we’ll call P, locks the queue.

5. P pushes a new item onto the queue.

6. P unlocks the queue again.

7. P calls unpark() to notify C that there are new items.

8. C calls park() to go to sleep, to wait for more items.

While there is most likely only a very brief moment between releasing the queue in step 3 and parking in step 8, steps 4 through 7 could potentially happen in that moment before the thread parks itself. If unpark() would do nothing if the thread wasn’t parked, the notification would be lost. The consuming thread would still be waiting, even if there were an item in the queue. Thanks to unpark requests getting saved for a future call to park(), we don’t have to worry about this.

However, unpark requests don’t stack up. Calling unpark() two times and then calling park() two times afterwards still results in the thread going to sleep. The first park() clears the request and returns directly, but the second one goes to sleep as usual.

This means that in our example above it’s important that we only park the thread if we’ve seen the queue is empty, rather than park it after every processed item. While it’s extremely unlikely to happen in this example because of the huge (one second) sleep, it’s possible for multiple unpark() calls to wake up only a single park() call.

Unfortunately, this does mean that if unpark() is called right after park() returns, but before the queue gets locked and emptied out, the unpark() call was unnecessary but still causes the next park() call to instantly return. This results in the (empty) queue getting locked and unlocked an extra time. While this doesn’t affect the correctness of the program, it does affect its efficiency and performance.

This mechanism works well for simple situations like in our example, but quickly breaks down when things get more complicated. For example, if we had multiple consumer threads taking items from the same queue, the producer thread would have no way of knowing which of the consumers is actually waiting and should be woken up. The producer will have to know exactly when a consumer is waiting, and what condition it is waiting for.

Condition Variables

Condition variables are a more commonly used option for waiting for something to happen to data protected by a mutex. They have two basic operations: wait and notify. Threads can wait on a condition variable, after which they can be woken up when another thread notifies that same condition variable. Multiple threads can wait on the same condition variable, and notifications can either be sent to one waiting thread, or to all of them.

This means that we can create a condition variable for specific events or conditions we’re interested in, such as the queue being non-empty, and wait on that condition. Any thread that causes that event or condition to happen then notifies the condition variable, without having to know which or how many threads are interested in that notification.

To avoid the issue of missing notifications in the brief moment between unlocking a mutex and waiting for a condition variable, condition variables provide a way to atomically unlock the mutex and start waiting. This means there is simply no possible moment for notifications to get lost.

The Rust standard library provides a condition variable as std::sync::Condvar. Its wait method takes a MutexGuard that proves we’ve locked the mutex. It first unlocks the mutex and goes to sleep. Later, when woken up, it relocks the mutex and returns a new MutexGuard (which proves that the mutex is locked again).

It has two notify functions: notify_one to wake up just one waiting thread (if any), and notify_all to wake them all up.

Let’s modify the example we used for thread parking to use Condvar instead:

use std::sync::Condvar;

let queue = Mutex::new(VecDeque::new());
let not_empty = Condvar::new();

thread::scope(|s| {
    s.spawn(|| {
        loop {
            let mut q = queue.lock().unwrap();
            let item = loop {
                if let Some(item) = q.pop_front() {
                    break item;
                } else {
                    q = not_empty.wait(q).unwrap();
                }
            };
            drop(q);
            dbg!(item);
        }
    });

    for i in 0.. {
        queue.lock().unwrap().push_back(i);
        not_empty.notify_one();
        thread::sleep(Duration::from_secs(1));
    }
});

We had to change a few things:

• We now not only have a Mutex containing the queue, but also a Condvar to communicate the "not empty" condition.

• We no longer need to know which thread to wake up, so we don’t store the return value from spawn anymore. Instead, we notify the consumer through the condition variable with the notify_one method.

• Unlocking, waiting, and relocking is all done by the wait method. We had to restructure the control flow a bit to be able to pass the guard to the wait method, while still dropping it before processing an item.

Now we can spawn as many consuming threads as we like, and even spawn more later, without having to change anything. The condition variable takes care of delivering the notifications to whichever thread is interested.

If we had a more complicated system with threads that are interested in different conditions, we could define a Condvar for each condition. For example, we could define one to indicate the queue is non-empty and another one to indicate it is empty. Then each thread would wait for whichever condition is relevant to what they are doing.

Normally, a Condvar is only ever used together with a single Mutex. If two threads try to concurrently wait on a condition variable using two different mutexes, it might cause a panic.

A downside of a Condvar is that it only works when used together with a Mutex, but for most use cases that is perfectly fine, as that’s exactly what’s already used to protect the data anyway.

Both thread::park() and Condvar::wait() also have a variant with a time limit: thread::park_timeout() and Condvar::wait_timeout(). These take a Duration as an extra argument, which is the time after which it should give up waiting for a notification and unconditionally wake up.