Are sound self-referential structs possible without boxing?

help
#1

The following example of how one might try to implement a self-referential struct is unsound.

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

struct SelfRef {
    value: UnsafeCell<u64>,
    ptr: *const u64,
    _pin: PhantomPinned,
}

impl SelfRef {
    fn new(value: u64) -> Self {
        Self {
            value: UnsafeCell::new(value),
            ptr: std::ptr::null(),
            _pin: PhantomPinned,
        }
    }
    fn set_ptr(self: Pin<&mut Self>) {
        let me = unsafe { Pin::into_inner_unchecked(self) };
        let ptr = &mut me.ptr;
        let value = me.value.get();
        *ptr = value;
    }
    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 self_ref = SelfRef::new(10);
    futures::pin_mut!(self_ref);
    
    self_ref.as_mut().set_ptr();
    println!("{}", self_ref.get_value());
}

playground

If you run the above with miri, you will see that it encounters UB. As I understand it, this is because when we call get_value, we create a unique reference to SelfRef, and hence we assert exclusive access to the struct, including all of its fields. This invalidates the *const u64 we stored in the struct, as it was created before we asserted unique access to value.

Note that in the above I use that an &mut UnsafeCell<T> still asserts exclusive access to the T. As far as I can see, this is indeed the case. The assumption that UnsafeCell turns off is the opposite, namely that an &UnsafeCell<T> does not assert that the T is immutable.

What does the compiler even do when it constructs a future with async/await? As far as I can see there is simply no way to fix the above code.

(Note that if we allow boxing of the value field, it is ok as the &mut SelfRef does not assert exclusive access through raw pointers recursively.)

2 Likes
#2

I believe this is being discussed in Resolve unsound interaction between self-referential generators (incl. async fn) and noalias · Issue #63818 · rust-lang/rust · GitHub, if I'm not mistaken

2 Likes
#3

As far as making miri happy is concerned, something like

fn get_value(self: Pin<&mut Self>) -> u64 {
    let me = unsafe { self.get_unchecked_mut() };
    let ptr = me.ptr;
    assert!(!ptr.is_null());
    let _me = me as *mut _;
    unsafe { *ptr }
}

is enough.

Furthermore, finding an approach that would make my personal intuition of “sound unsafe code” happy, one could go this far:

fn get_value(self: Pin<&mut Self>) -> u64 {
    let me = unsafe { self.get_unchecked_mut() };
    let ptr = me.ptr;
    assert!(!ptr.is_null());
    let _me = me as *mut _ as usize;
    let ptr_usize = ptr as usize;
    unsafe { *(ptr_usize as *const u64) }
}

Also, I really have to put reading into the details of stacked borrows higher on my TODO list.

#4

Yeah, but that's just this again. It would still be unsound with LLVM's noalias turned on for mutable references.

That doesn't seem sound to me. Maybe if you added ptr_usize - _me to the me pointer, it would be better.

1 Like
#5

Oh, I see, I hadn’t really read that post yet.

Does replacing ptr_usize with _me + ptr_usize - _me (all of these are integers!) really make a semantic difference? Also, this is somewhat of an LLVM question now, right? (Plus the question of what kind of LLVM Rust emits..)

#6

Box<T> contains an Unique<T> which should be special cased for this:

#7

Right, to do it with boxing, you must Box::into_raw and store it as a raw pointer, which you manually drop in the destructor.

#8

I really meant adding the difference between _me and ptr_usize to the original me pointer, avoiding the integer schenaniganz.

#9

Ah, okay.. well, I was thinking ahead here to a situation where we don’t know anymore if ptr points directly to a field of me or to some (other) heap location instead. I can imagine self-referential structs where both possibilities can happen.

#10

Just casting to integers and back to pointers seems incredibly sketchy to me. Anyway, even if we considered adding offsets to me for this case, there are other cases that also ought to work when pinned, but have the same issue without this workaround.

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

struct PairSelfRef {
    value: UnsafeCell<u64>,
    ptr: *const u64,
    _pin: PhantomPinned,
}

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

impl PairSelfRef {
    fn new(value: u64) -> Self {
        Self {
            value: UnsafeCell::new(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 = PairSelfRef::new(10);
    let pair_2 = PairSelfRef::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

#11

I feel like this could have changed if UnsafeCell::get_mut wasn't stabilized.

#12

You may also want to use the aliasable crate which provides an AliasableBox so you can reduce usage of unsafe and not have to implement Send + Sync manually.

#13

@Kestrer The case with boxing is not that interesting to me. I mostly want to know if there is any way to do this soundly without boxing.

#14

This issue is also being tracked in the UCG repository. I opened an issue similar to this on Miri where I managed to satify it using a similar workaround to @steffahn's, but RalfJung did mention that it wasn't a valid way to implement self-referential types. So I don't think this is possible soundly (even if Miri does not complain).

1 Like
#15

FYI, in that example’s API, one could drop one of the PairSelfRef before calling get_value on the other, dereferencing a dangling pointer.

#16

Good point, but you can fix that with the proper destructors.

#17

I think it would still be unsound because destructors are not guaranteed to run. For example:

let mut pair_1 = Box::pin(PairSelfRef::new(10));
let mut pair_2 = Box::pin(PairSelfRef::new(20));

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

std::mem::forget(pair_1);

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

Pin guarantees that if the destructors don't run, then the memory is leaked and hence the pointer would not be dangling.

1 Like
#19

FWIW, there's now a way to test this: the -Zmiri-track-raw-pointers flag. It will not work on code that use int-to-ptr casts, but for raw-ptr-only code it tracks provenance properly.

Of course that example code uses int-to-ptr casts precisely to get around the provenance tracking. This will have to be allowed somehow and it will be interesting to see what LLVM will do here...

You are very right to be cautious. :wink:

1 Like