Darksonn/intrusive.md Secret

## intrusive.md

      
    Raw
  

              intrusive.md
            
          
    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:

Immutability guarantee. An immutable reference guarantees that between
any two uses of the same immutable reference, the value has not been
modified.
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:

Inside link_up(), we create pair_2.ptr pointing at pair_1.
When calling pair_1.get_value(), we create a mutable reference to pair_1.
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.