Skip to content

Instantly share code, notes, and snippets.

@Darksonn
Last active Aug 31, 2021
Embed
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) };
        assert!(!me.ptr.is_null());
        unsafe { *me.ptr }
    }
}

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

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

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

playground

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) };
        assert!(!me.ptr.is_null());
        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/main.rs:30:18
   |
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 https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information

   = note: inside `Pair::get_value` at src/main.rs:30:18
note: inside `main` at src/main.rs:43:20
  --> src/main.rs:43:20
   |
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/function.rs:227:5
   = 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/backtrace.rs:125:18
   = note: inside closure at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:66:18
   = 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/function.rs:259:13
   = 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/panicking.rs:379:40
   = 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/panicking.rs:343:19
   = 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/panic.rs:396:14
   = note: inside `std::rt::lang_start_internal` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:51:25
   = note: inside `std::rt::lang_start::<()>` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:65:5

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.

@eaglgenes101

This comment has been minimized.

Copy link

@eaglgenes101 eaglgenes101 commented Mar 6, 2021

I don't quite follow why the accesses by &mut references are needed at

        let me = unsafe { Pin::into_inner_unchecked(self) };

and

    left.ptr = &mut right.value;
    right.ptr = &mut left.value;

Couldn't these parts be done (in a rather fiddly and ugly manner) without the mutable references?

@Darksonn

This comment has been minimized.

Copy link
Owner Author

@Darksonn Darksonn commented Mar 6, 2021

@eaglgenes101 Even if you change get_value to take an immutable reference so calling the method doesn't invalidate it, the point is moot. In real-world use-cases, you need mutable access, and creating a safe interface is still impossible even if you don't, because the owner of pair1 can always create a mutable reference to it, e.g. by calling Pin::as_mut on it, which we can't stop the user from doing. playground

@comex

This comment has been minimized.

Copy link

@comex comex commented Mar 7, 2021

Yes, but if value is stored in an UnsafeCell, then both get_value and set_value can take Pin<&self> and you no longer have unsoundness. Or store it in Cell or RefCell to reduce unnecessary unsafe.

Creating a safe interface is still a problem. Ironically, this is also the problem encountered by Pin itself. Normally, if you have a variable, you can move it, breaking the Pin guarantee. pin_mut! works around this by first defining the variable, then taking a reference to it (and wrapping it in Pin), then defining a second variable with the same name as the first. Because it has the same name, there's no way for the user to refer to the first variable, so they can't move it; they can only access the variable through the previously taken reference.

You could use the same approach to prevent mutable references from being taken. There would be a PinNeverMutable type (maybe with a shorter name), with the same guarantee as Pin plus the additional guarantee that the referent will never have a mutable reference taken to it. And there would be a macro that works like pin_mut!, but taking an immutable reference and wrapping it in a PinNeverMutable.

That said, it would definitely be nicer to just have UnsafeAliasedCell.

@Darksonn

This comment has been minimized.

Copy link
Owner Author

@Darksonn Darksonn commented Mar 8, 2021

In the real world use-cases in Tokio, the intrusive structs would typically be used in manual Future impls, whose trait signature requires that the method takes a Pin<&mut Self>. Trying to avoid the creation of mutable references to them is impossible.

@Jerald

This comment has been minimized.

Copy link

@Jerald Jerald commented Mar 10, 2021

I'm just trying to make sure I understand here, and it does seem like this isn't just something I'm confused about.

Does taking a &mut Self trigger the uniqueness guarantee for the entire allocation of Self? It seems that has to be the case. If it weren't, the intrusive data could be locked away inside some field of Self; even though you're invalidating pointers to Self the pointer to data within self would be valid.

@Darksonn

This comment has been minimized.

Copy link
Owner Author

@Darksonn Darksonn commented Mar 10, 2021

Does taking a &mut Self trigger the uniqueness guarantee for the entire allocation of Self?

Yes.

@Jerald

This comment has been minimized.

Copy link

@Jerald Jerald commented Mar 10, 2021

I don't have much experience with async, futures, Pin, etc. That said, based on what I've read it seems like it should be possible to sort of flip the situation on its head by lifting the storage and the value pointer into two separate allocations within another object. I can't imagine I'm the first to think of this, so I'm curious why it's not applicable. The playground example (based on the one linked above) passes miri without issue.

A simple example:

struct OuterPair {
    pair: Pair,
    value: UnsafeCell<u64>,
    _pin: PhantomPinned,
}

struct Pair {
    ptr: *const u64,
    _pin: PhantomPinned,
}

With this new situation, rather than Pair holding both the pointer to its value and the storage for another value, OuterPair holds the storage separately while Pair just holds the pointer to its value. This means that a Pin<&mut Pair> won't invalidate a pointer to the storage associated with it, only a Pin<&mut OuterPair> would do that. The notable downside seems to be one of ergonomics, as now you need to carry around both a Pair and the ptr to the associated storage.

Full playground example.

In the playground example, I've used a modified version of the futures::pin_mut! macro that takes an OuterPair and rather than just turning it into Pin<&mut OuterPair>, additionally projects it down to Pin<&mut Pair>. It shadows this on the same identifier so that after the macro call, the original OuterPair is inaccessible. As far as I can tell this provides the safety guarantees that allows Pin::new_unchecked to be valid, just like with the original futures::pin_mut!.

@Darksonn

This comment has been minimized.

Copy link
Owner Author

@Darksonn Darksonn commented Mar 11, 2021

@Jerald That is a quite interesting approach, and it does seem to be sound at a first glance. Unfortunately it doesn't really solve Tokio's real use case because how of incredibly restrictive the ergonomics issues are. It would also not be composable, e.g. how would you implement join given two self-referential futures?

@godmar

This comment has been minimized.

Copy link

@godmar godmar commented Jul 23, 2021

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

noalias was reenabled eleven days (March 22, 2021) after this note was written - has that affected tokio?

@Darksonn

This comment has been minimized.

Copy link
Owner Author

@Darksonn Darksonn commented Jul 23, 2021

Nobody reported any issues during that incident, though we did try to mitigate the issues by making a release with #3654.

@jasoncarr0

This comment has been minimized.

Copy link

@jasoncarr0 jasoncarr0 commented Jul 27, 2021

Jerald's solution definitely seems like it may work under Stacked Borrows / LLVM. I believe it would work very easily in cases where there already needs to be an indirection (since a smart pointer may be used instead). But otherwise it could possibly be provided with a macro, or a wrapper struct? With Pair<Left, Right> containing a Right, but being part of an OuterPair<Left, Right> which is (Left, Pair<Left, Right>). It could make the ergonomics sufficient for Join

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