Can you break the lift?

I'd just use swap, instead. That gets rid of the UB message and seems more appropriate for your use-case, anyway.

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

1 Like

That's the problem, it's not. It's going from &UnsafeCell<T> to &mut UnsafeCell<T>.

Remember the signature of F is for<'a> FnOnce(&'a R) -> &'a mut R, substitute R = UnsafeCell<T> and you go from &UnsafeCell<T> to &mut UnsafeCell<T>.

At the moment the implementation uses replace. The signature of replace is fn(&mut T, T) -> T: the signature guarantees the absence of aliasing.

I've tried using String for the value of the node in your example, and I'm still surprised that Miri doesn't complain. I guess I'm lucky...

The code is:

pub fn replace<T>(dest: &mut T, src: T) -> T {
    // SAFETY: We read from `dest` but directly write `src` into it afterwards,
    // such that the old value is not duplicated. Nothing is dropped and
    // nothing here can panic.
    unsafe {
        let result = ptr::read(dest);
        ptr::write(dest, src);
        result
    }
}

I think the saving grace here is that the call to replace in lift doesn't drop the content of the slot (dest`), therefore the double-free never materialize.

1 Like

I love it!

I found it a bit difficult to follow -- it is Friday evening -- so I added some type annotations: see here.

I think it's a bit easier to see what's going on here with diagram:

  • root: Box<dyn Trait> -> (A) RefCell of inner: Box<dyn Trait> -> (B) Struct
  • Trait::foo() is applied to &root, returning &mut inner.
  • At this point, inner which pointed to (B) is switched, and now points to (A), and the box pointing to (B) is returned.
  • (A) now points to itself, it's been lifted, and therefore leaks due to the circular reference.

I'm not quite sure what Miri doesn't like here. Technically the RefCell should be borrowed forever, and therefore root too, due to the use of Box::leak, so I can see why Stacked Borrow would not be happy about the references/moves.

I think this could even use copy with copy_nonoverlapping; at least Miri doesn't complain.

It's a bit strange, though, because this is exactly what replace should be doing. Who wants to have the honor of bringing this to the attention of Miri developers?

swap deprives the caller from the possibility to do something smart with whatever used to be in slot. It's a bit sad.

That's the problem, it's not. It's going from &UnsafeCell<T> to &mut UnsafeCell<T> .

And? The implementation as given is fully sound. That's why Miri accepts it. If it didn't have the UnsafeCell<T>, then there are no sound implementations from &T -> &mut T that overlap (of course you know of many that don't). But &UnsafeCell<T> acts just like *mut T so we can derive a &mut T, from which we then derive &mut UnsafeCell<T> (still soundly). We cannot use the other &UnsafeCell<T> references, but they're able to be below the mut reference on the stack becuase they're SharedMut, not Shared

At the moment the implementation uses replace . The signature of replace is fn(&mut T, T) -> T : the signature guarantees the absence of aliasing.

Ah got it, yes you can't use replace, and have to use a swapping method or copying method which accounts for overlap. Your implementation was bad but the type signature can be implemented soundly.

I see you've figured out the rest of the details with replace issues.

I think this could even use copy with copy_nonoverlapping ; at least Miri doesn't complain.

It is necessary here, not for Miri but for LLVM. Miri doesn't and can't catch all UB, just those that violate the stacked borrows model. The code generator could create bad code if we claim that they never overlap.

swap deprives the caller from the possibility to do something smart with whatever used to be in slot . It's a bit sad.

The implementation using swap is a strictly stronger interface, is it not? And cleaner to boot.

let x = ...
let x = lift(x, ...)

this can be replaced with

let mut x = ...
lift(&mut x, ...)

Except now x can be any mut pointer, not just an owned value

I feel like, in general, miri just doesn’t complain in a lot of cases here because of certain stacked-borrows-related features being disabled by default. I recently learned about the flag -Ztrack-raw-pointers. (You can invoke it locally with an environment variable à la MIRIFLAGS=-Zmiri-track-raw-pointers cargo +nightly miri run.)

Tested 2 examples for now: It doesn’t complain about this one either with the flag

but it does complain about the approach with ptr::copy based on my example

In current rust, this operation (assuming it points to the same T) is always UB, even for T = UnsafeCell<U>.

2 Likes

Wouldn’t converting &mut U to &mut UnsafeCell<U> be sound though? Then you can do &UnsafeCell<U>.get()*mut Ucast*mut UnsafeCell<U>unsafe {&mut *(…)}&mut UnsafeCell<U>.

3 Likes

True, my gut says that &mut U -> &mut UnsafeCell<U> ought to be sound (since it is when in the other direction), but given your example and given how many times RalfJ has insisted on UnsafeCell not being special w.r.t. &mut, I actually have to conclude that such op thus may not be either.

See also: intrusive.md · GitHub

I agree that the UnsafeCell dance is pretty weird. I think each step is sound (or at least, there are situations were all of them are sound), however the result is that we get a &mut UnsafeCell<T> that may alias with other &UnsafeCell<T>, which sounds unsound. This kind of reminds me of Ref parameter incorrectly decorated with `noalias` attribute · Issue #63787 · rust-lang/rust · GitHub

It would be nice if the playground had an option to enable it.

1 Like

In current rust, this operation (assuming it points to the same T ) is always UB, even for T = UnsafeCell<U> .

Well yes, the operation is. The point is that there is another, sound say to do it with UnsafeCell in particular. The standard cast is generally UB but we can upgrade in a particular path.

In the end I don't think this UnsafeCell dance particularly matters. It's just part of the callback and just happens to be a way to pretend that we're using GhostCell (which is formally verified to be sound), and you can implement the same thing there.

The impact for Stacked borrows is just this:
For &UnsafeCell<T>, it is possible to have a &mut UnsafeCell<T> higher up in the stack. That's it. You can't use the &UnsafeCell<T> reference while the mutable reference exists (it guarantees uniqueness during its lifetime), but you can manage to safely acquire a &mut in the first place, which is impossible without UnsafeCell

So yes all of the operations are sound, it's just that &UnsafeCell<T> doesn't require immutability of the underlying T

1 Like

This was a separate issue. I accidentally moved in the ManuallyDrop::new line. Swapping the first two lines fixes it for me with your flag added.

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

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

You can't use a &GhostCell<'id, T> to get a &mut GhostCell<'id, T> though.

IMO the problem is actually that it guarantees uniqueness while it's not really unique.

You can't use a &GhostCell<'id, T> to get a &mut GhostCell<'id, T> though.

pub fn to_mut_cell<'a, 'brand, T>(c: &'a GhostCell<'brand, T>, t: &'a mut GhostToken<'brand>) -> &'a mut GhostCell<'brand, T> {
   GhostCell::from_mut(c.borrow_mut(t))
}

IMO the problem is actually that it guarantees uniqueness while it's not really unique.

It's a unique borrow. It doesn't guarantee global uniqueness, just unique access during its lifetime, in much the same way that you can derive a &mut T from an owned T without ever losing the original T (but making it statically inaccessible), you can derive a &mut UnsafeCell<T> from a &UnsafeCell<T>, making it and all its aliases (unsafely) inaccessible.

2 Likes

TIL that GhostCell has a from_mut method that returns &mut GhostCell<T>. I thought its API was like Cell's which returns only a &Cell<T>. Anyway, where is the formal proof that GhostCell::from_mut is sound? I can't seem to find it in the paper/coq proof.

The problem is, what does "unique access during its lifetime" means? Does it only mean that nobody else will access it? Or that no other pointer to it can exist except the one from the parent borrow? This may seem a bit extreme, but LLVM noalias model is closer to the latter.

This seems to imply that you also need to guarantee that all the &UnsafeCell<T> that point to the same data are also inaccessible while you hold a &mut UnsafeCell<T>, which wasn't the case in the original example with lift.

TIL that GhostCell has a from_mut method that returns &mut GhostCell<T> . I thought its API was like Cell 's which returns only a &Cell<T> . Anyway, where is the formal proof that GhostCell::from_mut is sound? I can't seem to find it in the paper/coq proof.

I couldn't actually find that as well. It's in the official Rust library but seemingly not proven: FP / ghostcell · GitLab. On the other hand, the fact that Cell's returns &Cell<T> is just a historical fluke. The repo as it happens types Cell::from_mut as returning &mut Cell<T>

The problem is, what does "unique access during its lifetime" means? Does it only mean that nobody else will access it? Or that no other pointer to it can exist except the one from the parent borrow? This may seem a bit extreme, but LLVM noalias model is closer to the latter.

Possibly, but I'm not sure that the actions LLVM takes will ever reflect that second point and my understanding is that it's practically about accessing it. Otherwise LLVM would be miscompiling just about all of Rust's code (and I'm aware that at one point it did with &mut)

This seems to imply that you also need to guarantee that all the &UnsafeCell<T> that point to the same data are also inaccessible while you hold a &mut UnsafeCell<T> , which wasn't the case in the original example with lift .

Again this is the case, but it's guaranteed by virtue of "I promise I won't do this". The usage within the code is sound because I haven't violated that, but it's still unsafe. Like all unsafe code, we could make it unsound by changing its surroundings, but in the form it exists there it's fully sound. You could summarize "You didn't guarantee X" by just saying "You wrote the unsafe keyword"

I think this is pretty rare because LLVM usually doesn't just shuffle instructions around, so when the borrow ends and you can use the aliased cell you can't really do much to cause damage. However in rust-lang/rust#63787 it was shown that you can exploit it to cause miscompilations, so it can generate UB.

By the way I've opened Can a `&UnsafeCell<T>` and a `&mut UnsafeCell<T>` alias? · Issue #284 · rust-lang/unsafe-code-guidelines · GitHub since that feels like a better place to discuss this stuff.

Undefined behavior is a language spec thing, it sounds like that miscompilation was a compiler bug. I.e. it was defined behavior but the compiler/LLVM didn't follow the definition. There's been plenty of miscompilations of fully safe / sound code.

Oh my bad; I had missed the change in the signature.

There's still an issue with aliasing; that is, using your UnsafeCell example which returns an alias of root doesn't work with swap because swap assumes non-overlapping inputs (it calls ptr::swap_nonoverlapping_one under the hood).

I think this could be handled by a check that there's no aliasing before swapping; before materializing the aliasing mutable references.

I am still quite uncomfortable with the UnsafeCell example; I'll take that discussion to the GitHub issue.

This leaks root when fun panics. Also you don’t need the pointers anymore to fight any lifetimes. Something like

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

    let result;
    unsafe {
        result = ptr::read(slot);
        ptr::copy(&root, slot, 1);
    }

    mem::forget(root);
    result
}

should do just fine, right?

(Unless if perhaps there’s harm in “touching” the root (for mem::forgetting it) after reading result because you might have two copies of the same value on the stack in this case… So perhaps even better back to a ManuallyDrop plus a guard object that drops it in case of a panic? :thinking: This whole unsafe code business is always really hard and subtle. I can’t wait for the formalization efforts to improve and miri to become more complete (so that it will eventually be able to guarantee that it’s really reporting any UB that happens at runtime).

No, that is wrong. Miri explicitly claims to be unable to detect all instances of Undefined Behavior, therefore Miri not complaining does not constitute evidence of soundness.

3 Likes