Skip to content

Instantly share code, notes, and snippets.

Last active May 6, 2022
What would you like to do?

Tokio currently uses a technique known as intrusive linked lists, which can significantly reduce the number of memory allocations in async code, but it has come to our attention that intrusive lists are unsound due to a limitation of the Rust language.

This issue is related to #63818, which comes from the same root cause, but that issue is specifically about the ramifications of this on generators (including async/await).

What are intrusive linked lists?

An intrusive linked list is a linked list where the nodes are stored directly inside objects owned by the user of the list. These objects would typically use some raw pointers stored in each struct, pointing at the other structs. By following the raw pointers, you can traverse the list of objects, no matter where they are stored.

Naturally the above design would break if any of the objects were moved, as this would invalidate the pointers pointing at that object. To avoid this, we use the Pin type, which lets the owner of the object promise us that it will never be moved, and therefore our pointers cannot be invalidated in this manner.

A simple example of an intrusive collection would be the following Pair type:

use std::pin::Pin;
use std::marker::PhantomPinned;

// There are some issues related to destructors with this type,
// but those are besides the point. You can ignore them.
struct Pair {
    value: u64,
    ptr: *const u64,
    _pin: PhantomPinned,

fn link_up(left: Pin<&mut Pair>, right: Pin<&mut Pair>) {
    let left = unsafe { left.get_unchecked_mut() };
    let right = unsafe { right.get_unchecked_mut() };
    left.ptr = &mut right.value;
    right.ptr = &mut left.value;

impl Pair {
    fn new(value: u64) -> Self {
        Self {
            value: value,
            ptr: std::ptr::null(),
            _pin: PhantomPinned,
    fn get_value(self: Pin<&mut Self>) -> u64 {
        let me = unsafe { Pin::into_inner_unchecked(self) };
        unsafe { *me.ptr }

fn main() {
    let pair_1 = Pair::new(10);
    let pair_2 = Pair::new(20);

    link_up(pair_1.as_mut(), pair_2.as_mut());

    println!("{}", pair_1.get_value());
    println!("{}", pair_2.get_value());


With the above type, you can link up two values of type Pair, and each can access the value stored in the other. Since the values are pinned, neither can be moved again, so the pointers remain valid. Note that either part of the pair can still be dropped, which would invalidate the other pointer, however it is possible to work around this issue with an appropriate destructor. (This does not run into trouble with mem::forget because Pin guarantees that either the destructor runs or the memory is leaked, and the raw pointer stays valid if the memory is leaked.)

How Tokio uses intrusive lists

Tokio generally uses intrusive lists to store wakers for tools that need to store a variable amount of wakers. A good example is our Mutex type, where we need to store a new waker for every call to Mutex::lock, and since there can be any number of calls to lock, the mutex may end up storing any number of wakers.

One way to handle this is store the wakers in a vector or a type like slab, but this involves a collection that grows with the number of wakers, and if shrinking these allocations is not properly handled, you can end up with apparent memory leaks, like what happened here. Strictly speaking, this is not a memory leak, as the memory is deallocated when the broadcast channel is dropped, but if that broadcast channel is kept around forever, then it is effectively a leak.

Intrusive collections help sidestep this issue entirely, because whenever you call lock, you get a Future that you need to keep polling until the lock is successfully acquired. Why not store the waker directly in the Future? This would mean that the callers of lock provides the necessary memory for storing their wakers, and since the Future is typically stored on the stack of the async function that called lock, we do not even need a separate allocation for the waker. Finally, since a Future must be pinned to be polled, we can indeed build up an intrusive linked list through these futures.

The problem with intrusive lists (and self-referential structs)

Let us go back to our example. We had the following function:

impl Pair {
    fn get_value(self: Pin<&mut Self>) -> u64 {
        let me = unsafe { Pin::into_inner_unchecked(self) };
        unsafe { *me.ptr }

To call this function, you must provide a Pin<&mut Pair>, i.e. you must create a mutable reference to the Pair. Unfortunately for our Pair, mutable references must by definition be unique references. The way this should be interpreted when raw pointers are involved is that whenever you create or use a mutable reference to some value, all raw pointers to that value are invalidated (excluding the raw pointer the reference was created from) (calm down everyone, ordinary linked lists are not impossible). In this context, invalidated means that although it is OK if the raw pointer still exists, it is undefined behaviour to ever use that raw pointer to access the value.

To see this in the example from before, open the example in the playground, and select "Miri" under the "Tools" dropdown. It will fail with the following error:

error: Undefined Behavior: no item granting read access to tag <untagged> at alloc1389 found in borrow stack.
  --> src/
30 |         unsafe { *me.ptr }
   |                  ^^^^^^^ no item granting read access to tag <untagged> at alloc1389 found in borrow stack.
   = help: this indicates a potential bug in the program: it performed an invalid operation, but the rules it violated are still experimental
   = help: see for further information

   = note: inside `Pair::get_value` at src/
note: inside `main` at src/
  --> src/
43 |     println!("{}", pair_2.get_value());
   |                    ^^^^^^^^^^^^^^^^^^
   = note: inside `<fn() as std::ops::FnOnce<()>>::call_once - shim(fn())` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/
   = note: inside `std::sys_common::backtrace::__rust_begin_short_backtrace::<fn(), ()>` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sys_common/
   = note: inside closure at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/
   = note: inside `std::ops::function::impls::<impl std::ops::FnOnce<()> for &dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe>::call_once` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/
   = note: inside `std::panicking::r#try::do_call::<&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe, i32>` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/
   = note: inside `std::panicking::r#try::<i32, &dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe>` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/
   = note: inside `std::panic::catch_unwind::<&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe, i32>` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/
   = note: inside `std::rt::lang_start_internal` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/
   = note: inside `std::rt::lang_start::<()>` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/

Notice how it fails at the second call to get_value. This is because the call to pair_1.get_value() invalidates the raw pointer to pair_1 inside pair_2, and once we try to use that raw pointer, we trigger UB.

Why does UnsafeCell not help?

At first glance, many people, including myself, thought that the problem can be solved by wrapping value in an UnsafeCell, but unfortunately this is not the case. To understand why, you need to understand the guarantees that various types of references provide:

  1. Immutability guarantee. An immutable reference guarantees that between any two uses of the same immutable reference, the value has not been modified.
  2. Uniqueness guarantee. A mutable reference guarantees that between any two uses of the same mutable reference, no other pointer or reference has accessed the value. It also guarantees that if the mutable reference was used between any two uses of any other pointer/reference to the same value, then the mutable reference was created from that other pointer/reference (possibly recursively).

An UnsafeCell turns off the immutability guarantee, i.e. if you have an &UnsafeCell<T>, then the value of the T is allowed to change between uses of the &UnsafeCell<T>. (But if you create an &T to the value, then it may still not change, even if the T is inside an UnsafeCell.)

Unfortunately our intrusive list also violates the uniqueness guarantee, as can be seen from the following access pattern:

  1. Inside link_up(), we create pair_2.ptr pointing at pair_1.
  2. When calling pair_1.get_value(), we create a mutable reference to pair_1.
  3. Inside pair_2.get_value(), we use pair_2.ptr, which points at pair_1.

So by the uniqueness requirement from earlier, a mutable reference to pair_1 was used between two uses of pair_2.ptr, and therefore the mutable reference must have been created from pair_2.ptr. Since it was not created from pair_2.ptr, this is undefined behaviour.

An UnsafeCell does not do anything to disable the uniqueness requirement, so it does not solve the issue. (To be clear, intrusive collections need to disable both guarantees, not just the uniqueness guarantee.)

A note on boxing

One important thing to note is that this problem can be solved by boxing. This is because a raw pointer disables both guarantees in the sense that an &mut *mut T or &*mut T does not guarantee anything whatsoever about the T. By storing the shared value inside a *mut T created with Box::into_raw, the code is perfectly sound, and to avoid a memory leak, you can destroy the box in the destructor.

You can find an example of how you can adjust the previous pair example to be correct using this technique here. This example still has the problem where the pointer can become dangling if one half of the pair is dropped, but this can be solved with the right destructor.

Unfortunately the entire point in using intrusive collections is to avoid memory allocations, so boxing is not really a solution. There are much simpler and safer solutions if we are OK with boxing them.

A note on self-referential types

Note that all self-referential structs (unless they use boxing) are unsound due to the same problem, including the opaque types generated by async/await. In this case, the pointer that gets invalidated is stored inside the struct itself, but it is still invalidated.

The problems this causes for async/await are tracked here. The compiler avoids miscompilation because the noalias LLVM optimization is turned off, so LLVM does not make use of the uniqueness guarantee to optimize code. Still, this doesn't make async/await sound. The async/await syntax is lowered to MIR, and that MIR has undefined behaviour according to Rust's MIR semantics. This is a problem on a similar scale as it is for user-written code. (Source: private communication with Ralf Jung.)

One approach to resolving this

As also discussed in this comment, this problem can be resolved by adding a hypothetical UnsafeAliasedCell type, which turns off the uniqueness guarantee analogously to how UnsafeCell turns off the immutability guarantee. The struct from before would become

struct Pair {
    value: UnsafeAliasedCell<u64>,
    ptr: *const u64,
    _pin: PhantomPinned,

and calling Pair::get_value would not invalidate the pointer in the other pair, since the &mut Pair works as an &mut UnsafeAliasedCell<u64>, which does not guarantee exclusive access to the u64.

Copy link

Darksonn commented May 1, 2022

@louy2 Miri will avoid considering mutable references to !Unpin types exclusive to make this kind of code testable with miri. However, it should be noted that this isn't a promise that it is now defined behavior—miri just accepts it for now.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment