Can you break the lift?

Or otherwise said, is the lift function presented below actually safe?


What's is this function useful for?

I am trying to write a doubly linked-list, and found myself hitting a wall when I tried to implement the append function. For a simplified view of the code, imagine that a node in the list is:

struct List<T>(Option<(HalfPtr<T>, HalfPtr<T>)>);

struct Node<T> {
    value: T,
    prev: Option<HalfPtr<T>>,  // None if head.
    next: Option<HalfPtr<T>>,  // None if tail.
}

type HalfPtr<T> = SomeRc<SomeCell<Node<T>>>;

Now, in the course of the append function, you are provided two lists, and you should "steal" the content of the second and append it to the first:

fn append(&mut self, other: &mut Self) {
    // Let's cut the interesting case: both are non-empty.

    let (new_head, mid_tail) = self.0.take().unwrap();
    let (mid_head, new_tail) = other.0.take().unwrap();

    mid_tail.borrow_mut().next = Some(mid_head);
    mid_head.borrow_mut().prev = Some(mid_tail); // Oh wait, mid_head was moved!

    self.0 = Some((new_head, new_tail));
}

The realization here is that after the lists are connected, you don't retain any pointer to the "mid" nodes. This is why you hand-over mid_head, and would like to hand-over mid_tail. But how?


The idea I've been toying with is to use a function I've called lift, and declared as such:

fn lift<R, F>(root: R, fun: F) -> R
where
    F: for<'a> FnOnce(&'a R) -> &'a mut R;

Which is used so:

lift(mid_tail, |mid_tail| {
    let mid_head = mid_tail.borrow().prev;
    mid_head.borrow_mut()
});

The exact definition is of course, unsafe:

fn lift<R, F>(root: R, fun: F) -> R
where
    F: for<'a> FnOnce(&'a R) -> &'a mut R,
{
    let slot = fun(&root) as *mut R;

    mem::replace(unsafe { &mut *slot }, root)
}

And I've been wondering whether the function is, actually, safe.

The key observation here is that the lifetime of slot is, ultimately, tied down to the lifetime of root -- it's derived from it -- and the definition of lift ensures that the lifetime of root outlives that of slot hence it looks fine.

But I am wondering whether it is fine.

MIRI seems fine with this program, but didn't take the issue in the broken version either so...


Note: previous version, broken by @SkyFire13 who realized that allowing the caller to specify the reference allowed exfiltrating the reference:

fn lift<'a, R, F>(root: R, fun: F) -> R
where
    F: FnOnce(&'a R) -> &'a mut R,
{
    //  Circumvent the borrow-checker; we're going to move `root` after borrowing from it.
    let reference = &root as *const R;

    let slot = fun(unsafe { *reference });

    mem::replace(slot, root)
}

One big problem I can see is that 'a is choosen by the caller. What if it chooses 'static? I would change the signature to something like:

    fn lift<R, F>(root: R, fun: F) -> R
    where
        F: for<'a> FnOnce(&'a R) -> &'a mut R;

The next problem is its actual usefulness. Tthere aren't many ways to get an &'a mut R from an &'a R. The only ways I can think of is calling RefCell::borrow_mut and then RefMut::leaking it, or using Box::leak to get a &'static mut R, both of which aren't really viable. In fact I double this snippet will ever work:

If that .borrow_mut() is like the one of an RefCell then this won't work, because the guard will be dropped at the end of the closure.

1 Like

It is useful, with GhostCell, at least, since then the borrow's lifetime is not tied to a temporary :wink:

That is indeed problematic. It allows exfiltration of the reference, which would be unsafe.

I'm still not quite comfortable with for<'a>.

I would expect that for<'a> would essentially require R: 'static:

  • &'a mut R must be valid for all 'a.
  • &'a mut R is only valid if R: 'a.
  • for<'a> means that 'a could be 'static.

I decided to try it, though, and it works:

use std::{
    cell::UnsafeCell,
    mem,
};

fn lift<R, F>(root: R, fun: F) -> R
where
    F: for<'a> FnOnce(&'a R) -> &'a mut R,
{
    let slot = fun(&root) as *mut R;

    mem::replace(unsafe { &mut *slot }, root)
}

struct Node<T> {
    value: T,
    next: UnsafeCell<Option<Box<Self>>>,
}

fn main() {
    let hello = "Hello".to_string();

    let node = Box::new(Node {
        value: &hello,
        next: UnsafeCell::new(None),
    });

    println!("{:?}", node.value);

    let previous = lift(Some(node), |some_node| {
        let node = some_node.as_ref().unwrap();
        unsafe { &mut *node.next.get() }
    });

    assert!(previous.is_none());
}

Note: this is going to leak; by "it works" I meant MIRI was happy enough with it. It only complained about the leak.

And I'm honestly not sure why Node can contain a local reference (hence not 'static) in this case.

I'm going to go ahead and edit the post with the new version of lift; thanks @SkiFire13 .

With GhostCell it could theoretically work, however I think the for<'a> approach would be too restrictive for it since you would need a &'a mut GhostToken<'id> for any 'a that the closure might be called with.

AFAIK for<'a> automatically restricts the set of possible 'a so that the trait/bound is well formed. In other words, it's not R that has to "adapt" to any 'a, but it's the set of possible 'as that is adapted to R.

This appears to be sound with the rank 2 type as best I can tell. As always though, safety is not modular

  1. First recognize that according to the type signature for F, it can be instantiated to any particular concrete lifetime. In particular, before we have any unsafe code, it guarantees no dangling references if we instantiate it to say, the lifetime up until the mem::replace line. That is to say, there can be no references root, except the one accessed through slot.

  2. For the section starting at mem::replace, we know that there are no other active borrows (from section 1, by instantiating at the short lifetime). As such, we can compute everything with raw pointers, we only have to re-establish the validity of data after the critical section (NOTE: this is where non-modular unsafety could sneak in; other types might have validity constraints which would be violated by this, but every standard Rust type should remain valid after the move, which is simpler but would still need proof).

So the main threat to look out for might be incompatibility with data structures which rely on pinning somehow

I'm skeptical about the function's soundness. What error message do you get when not using unsafe?

fn lift<R, F>(root: R, fun: F) -> R
where
    F: for<'a> FnOnce(&'a R) -> &'a mut R,
{
    mem::replace(fun(&root), root)
}

I assume it will complain about root still being borrowed while trying to be moved. If that's the case, no matter what magic you use, what you're doing is unsound, because raw pointers still operate on a relaxed lifetime model, i.e. when you move a value, all pointers created from references tied to the lifetime of another reference from the moved value will become invalid. Using the pointer, anyway can be the source of a use-after-free.

I'd guess, what you want is to return &'b mut R where 'b: 'a. There is only one theoretically possible way to express this with a reference and that is to move the declaration of 'b to the function declaration of lift.

fn lift<'b, R, F>(root: R, fun: F) -> R
where
    F: for<'a> FnOnce(&'a R) -> &'b mut R,
    'b: 'a
{
    mem::replace(fun(&root), root)
}

I do not know if this works as-is or if it can be done, at all. If not, the only remaining way is to return a *mut R, instead, but that'd require the caller to abide by certain restrictions, i.e. lift would have to be declared as unsafe or you create a custom return type, that imposes unsafe restrictions on its creation. lift itself wouldn't be able to enforce these restrictions through the type system, in this case.

This still allows 'b to be 'a, so you didn't actually changed anything

1 Like

Indeed, if 'a is 'b, then it wouldn't compile. However, IIUC, it'd compile if 'b lives longer than 'a and since 'b is provided by the caller, it's possible to provide a sufficient lifetime. The current method does not offer this flexibility, i.e. the returned reference must not outlive 'a, but that is exactly what's happening.

Are you sure about that?

I can imagine this check would be intended to catch issues with returning part of an object -- that is, if you have r and return &r.a, then moving r also moves r.a. However, a case need to be made for indirect references, that is if r contains a Box<T>, then while the address of the Box itself changes as r is moved, the address of T doesn't.

This seems like an important distinction, because the signature of fun guarantees that the address returned is not internal to root:

  • fun cannot return root, as this would lead to having both a reference and mutable reference to the same value.
  • fun cannot return a reference to a value inline within root itself, because R cannot contain an R.

Therefore, fun has to return an indirect reference to another instance of R, which itself guarantees the stability of the address as root moves.

To my knowledge, Rust does not perform any of the logical implications you mention. All it looks at are the lifetimes and what it may look at in the future are the raw pointers. When you move root, all attached lifetimes are destroyed, i.e. 'a becomes invalid when calling mem::replace and in return, any pointers created from references with that lifetime also become invalid to dereference. In conclusion, the function invokes UB for all possible inputs and Rust could replace the function body with whatever it likes.

EDIT: You may want to dive into Stacked Borrows. The gist of it is, that raw pointers are not as raw as you may think. Rust still wants to be able to perform certain optimizations, even if lifetimes aren't tracked. The worst thing about raw pointers is, that the rules aren't set in stone, yet, so I recommend being pessimistic about what's OK to do and what not.

1 Like

Having read the stacked borrows model, I think the situation is pretty unclear honestly.

I'm not seeing an issue with stacked borrows here, but I would agree that it's not clear and relies on subtleties in the case of overlap.

The key thing is a very careful sequence of events:

  • Get a SharedMutable pointer (possibly but most likely not) derived from the borrow (but if it's derived then it has to point to UnsafeCell or the caller triggered UB in their passed lambda)
  • Read the value into new memory from the first borrow (this isn't incompatible with anything because it must have already been under an UnsafeCell if it overlapped!)
  • Write into the pointer from step 1 (We use our SharedMut is at the top of the stack! The caller already created the borrow so this is safe)

Done!
We now return the value to the caller (and all of our borrows are gone)
Importantly, the value we have must now be in a valid state, but that's it. That's the only safety condition that we need to meet.

Miri even accepts this trivial version that returns the exact same pointer from &T to &mut T (under an UnsafeCell)
https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=bd605e3130a39ea38af98cb62a09ad83

So I think the very simple summary which better boils down the thinking above:

  • The caller has to produce a function &T -> &mut T. There's only two ways for the caller to do this: either the memory of the return doesn't overlap with the memory of the argument, or if it does overlap, it must be under an UnsafeCell. Otherwise the caller would be triggering UB.

  • Because of this, stacked borrows is fine because all of our borrows to the memory either don't overlap, or point to an UnsafeCell (and so are all compatible even if it looks questionable)

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=69186bdfe6efe52b988bbb68ea3a23a5

You can't pass my_f to lift because it has signature for<'a, 'r> fn(&'a MyT<'r>) -> &'a mut MyT<'a>, while lift asks for a for<'a> fn(&'a MyT<'r>) -> &'a mut MyT<'r> where 'r is fixed before the for<'a>. You can't get a &'a mut MyT<'r> because you want it to store the input reference, which has lifetime 'a and is always shorter than 'r.

3 Likes

I freaked out for a bit, until I realized that this callback was UB in the first place.

(If it were not, it would clearly have broken lift)

@mattieum that callback isn't UB... and if it was then Miri would have yelled at it. It's critical that it is going from &UnsafeCell, because &UnsafeCell can alias with mutable references to its interior without causing UB. That's the whole point of UnsafeCell.

I'm not seeing how it actually breaks lift though. It would swap the value with itself, causing lift to become a no-op.

Although what you might have to do is make sure that whichever swap implementations are called (in which case you inline mem::replace) do not assume the inputs can't overlap. They might, although for sized types it can only be trivial overlap.

I can get miri unhappy with this.

use std::{cell::RefCell, mem};

fn lift<R, F>(root: R, fun: F) -> R
where
    F: for<'a> FnOnce(&'a R) -> &'a mut R,
{
    let slot = fun(&root) as *mut R;

    mem::replace(unsafe { &mut *slot }, root)
}

struct Struct;

#[allow(clippy::mut_from_ref)]
trait Trait {
    fn foo(&self) -> &mut Box<dyn Trait>;
}

impl Trait for RefCell<Box<dyn Trait>> {
    fn foo(&self) -> &mut Box<dyn Trait> {
        &mut **Box::leak(Box::new(self.borrow_mut()))
    }
}
impl Trait for Struct {
    fn foo(&self) -> &mut std::boxed::Box<dyn Trait> {
        unimplemented!()
    }
}

fn main() {
    let r = Box::new(RefCell::new(Box::new(Struct) as Box<dyn Trait>)) as Box<dyn Trait>;
    lift(r, |b| b.foo());
}

   Compiling playground v0.0.1 (/playground)
    Finished dev [unoptimized + debuginfo] target(s) in 1.44s
     Running `/playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/cargo-miri target/x86_64-unknown-linux-gnu/debug/playground`
error: Undefined Behavior: trying to reborrow for Unique at alloc1443+0x8, but parent tag <3170> does not have an appropriate item in the borrow stack
   --> /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/mem/mod.rs:817:1
    |
817 | / pub const fn replace<T>(dest: &mut T, src: T) -> T {
818 | |     // SAFETY: We read from `dest` but directly write `src` into it afterwards,
819 | |     // such that the old value is not duplicated. Nothing is dropped and
820 | |     // nothing here can panic.
...   |
825 | |     }
826 | | }
    | |_^ trying to reborrow for Unique at alloc1443+0x8, but parent tag <3170> does not have an appropriate item in the 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 `std::mem::replace::<std::boxed::Box<dyn Trait>>` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/mem/mod.rs:817:1
note: inside `lift::<std::boxed::Box<dyn Trait>, [closure@src/main.rs:32:13: 32:24]>` at src/main.rs:9:5
   --> src/main.rs:9:5
    |
9   |     mem::replace(unsafe { &mut *slot }, root)
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `main` at src/main.rs:32:5
   --> src/main.rs:32:5
    |
32  |     lift(r, |b| b.foo());
    |     ^^^^^^^^^^^^^^^^^^^^
    = 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:49: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:401: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:365: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:433: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:34:21
    = 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:48:5

error: aborting due to previous error
3 Likes

So it seems it's erroring on an intrinsics::forget call inside ptr::write which needs to borrow the src, but it's been invalidated by the move.

Why is it that intrinsics::forget is writing to the src? Trying to manually inline a bunch to diagnose and fix it. I think there may be some undocumented UB case in ptr::write.

In any case it looks like we can fix it fairly easily by wrapping up the data in ManuallyDrop. I've written up a version of the function that takes this into account and replaces the copy_nonoverlapping with copy.
It is wildly low-level, but handles @steffahn's case without any UB (we do get a nice warning about the leak in that example ofc)

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=7c62dbb5d976881b4a5283b31481f948

fn lift<R, F>(root: R, fun: F) -> R
where
    F: for<'a> FnOnce(&'a R) -> &'a mut R,
{
    let slot = fun(&root) as *mut R as *mut ManuallyDrop<R>;
    let root = ManuallyDrop::new(root);

    unsafe {
        let result = ptr::read(slot);
        ptr::copy(&root as *const _, slot, 1);
        ManuallyDrop::into_inner(result)
    }
}