Writing an invalid value through a reference the caller can never use again

[ais523]

I want to write code that looks like the following:

pub fn drop_in_place_static<T>(r: &'static mut T) -> &'static mut MaybeUninit<T> {
    // Safety: r: 'static, so nobody else can ever use this reference again,
    // except through r2 (which assumes only that the referenced memory is a
    // `MaybeUninit<T>`), and all valid `T` are also valid `MaybeUninit<T>`.
    let r2: &'static mut MaybeUninit<T> = unsafe { core::mem::transmute(r) };

    // Safety: `r2` was transmuted from a reference to a `T`, so must be initialized.
    unsafe { r2.assume_init_drop(); }
    *r2 = MaybeUninit::uninit();
    r2
}

I was under the impression (I think from a mis-remembered #524) that this was already something that was guaranteed to be sound (on the basis that you can change the memory referenced by a &mut T arbitrarily as long as you leave a valid T in the memory by the time the reference's lifetime ends, and an &'static mut T's lifetime never ends so you can just change the memory arbitrarily forever), but trying to find where the guarantee was actually made, I couldn't find it.

Instead, I found #84, which is a bit concerning for code like this because some of the potential solutions to #84 would consider code like this to be undefined behavior (although, as far as I can tell, the solution currently under discussion doesn't).

Note that (as this is intended to be a safe API that's sound for arbitrary safe code to use) I'm concerned that restricting this to types T that have no niche might not be sufficient, because Rust has APIs that convert references to niched types to references to the entire non-niched memory containing them (such as Cell::from_mut), so it is possible that a reference might have a non-niched type even if references an enum field whose niche is being used to store a discriminant. I didn't find any such APIs that return mutable references, but it seems plausible that one might be added (or already exist).

My question is: has there actually been / could there be a commitment made that such code is sound (in the sense that choosing a solution to #84 that makes it unsound would be considered a breaking change)? Or is this something which is still subject to change, and thus should be avoided at present?

(I have two main motivations for wanting this function. One is to make sound code easier to write: I'm trying to produce a set of safe wrappers for unsafe primitives that can be used to write certain sorts of low-level code without needing further unsafe, meaning that the compiler could prove it to be sound as long as the primitives were sound, and this one is one of the more useful ones. The other is for optimization purposes: writing the equivalent of this using raw pointers instead misses a huge number of optimizations, whereas using references instead gives the compiler more aliasing information and this leads to better-optimized code as a consequence.)

[ia0]

I'm probably missing something but it seems *r2 = MaybeUninit::uninit(); is the only problematic statement, and based on your motivations it doesn't seem necessary. Removing that statement wouldn't solve your problem?

[RalfJung]

Yeah I think the jury in #84 is still out on whether it is okay to temporarily change the encoded discriminant of a surrounding enum even if nobody looks at it again... so if there are arguments to only require the enum discriminant to be the same again the next time someone checks it, that'd be interesting.

But I also agree with @ia0 that it is unclear why you are even bothering with overwriting that memory with "uninit" here.

[ais523]

I'm probably missing something but it seems *r2 = MaybeUninit::uninit(); is the only problematic statement, and based on your motivations it doesn't seem necessary. Removing that statement wouldn't solve your problem?

It wouldn't make any difference if you removed it, because a safe-code caller could do this:

pub fn drop_in_place_and_uninitialise<T>(r: &'static mut T) -> &'static mut MaybeUninit<T> {
    let r2 = drop_in_place_static(r);
    *r2 = MaybeUninit::uninit();
    r2
}

and recreate the deinitialising version.

Part of the requirement for being sound is that the code has to have defined behaviour in combination with any possible safe code, including code that does things like this. So if the deinitialisation is making the function unsound, then the function without the deinitialisation is also unsound.

(One of the main reasons why doing this is useful at all is that it allows the caller to repurpose the memory containing the previously dropped object without using unsafe code, and that might involve overwriting it with a value of another type, which might contain uninitialised bytes. So this isn't even a particularly unlikely usage scenario.)

[ia0]

I see. Indeed the cast to MaybeUninit<T> possibly widens the "subobject" provenance (or whatever we come up for the enum fields situation). I forgot safe code could write to MaybeUninit<T>.

But then, do you need the output to be MaybeUninit<T> or could it be your own opaque type? (which safe code can't write to)

[ais523]

Unfortunately, you can't have the "safe code can't write to" constraint in current Rust; safe Rust code can write through any &mut reference using mem::swap or mem::replace (and can even write through any Pin<&mut> reference using Pin::set). You would thus need to ensure that the opaque return type would have the same validity constraint as T, but it is in general impossible to create an uninitialized value of such a type in generic code (because if you don't have a value of T available to copy the bits from, you can't prove that whatever bit pattern you happen to pick isn't a niche of T).

---

The broader context to all of this is that I'm working on the general problem of code that wants to store reference-like or smart-pointer-like values that have the aliasing property of "as long as this value is alive, nobody will read or write to the referenced memory, except via this reference/pointer-like thing". It is very common for people to want to use Rust's &mut to represent this (because it has almost the right semantics), but &'a mut's semantics are actually "for the entire lifetime 'a, which starts and ends in the same stack frame, nobody will read or write to the referenced memory, except via this reference/pointer-like thing", which is not quite the same.

Some examples of cases where the difference matters:

• borrows of the inside of a RefCell
• Box with a custom allocator
• coroutines that contain variables of mutable reference type (because Rust's coroutines are stackless, their execution can jump around between stack frames and thus the lifetime of the mutable reference might start in one stack frame and end in another)

In all these cases, Rust currently isn't capable of doing alias-based optimisations: a noalias specifier would be incorrect (and from the Stack Borrows / Tree Borrows point of view, you end up violating a protector if you try to write them in terms of regular &mut), so the current implementation uses alternatives that do not optimise (raw pointers for cell::RefMut and for Box, and a double reference for coroutines created by async) or that are unsound (e.g. coroutines created by gen, rust-lang/rust#159443).

I've been investigating two approaches to try to regain the performance (by giving Rust and LLVM access to aliasing information that's weak enough to be accurate to what is actually done with the memory, but strong enough to nonetheless be useful for optimization). One is to create a mutable reference type with weaker aliasing guarantees, either in addition to &mut, or even by silghtly weakening the guarantees on &mut so that it can be used in more places (that's what #590 was meant to be about, but it ended up getting a bit lost along the way). The other approach is to keep the noalias, and to avoid violating the noalias by ensuring that all uses of the memory are "based on" all previous uses, which from the Rust (and Stacked Borrows / Tree Borrows) point of view means that every use of the memory must reborrow from the previous use; that naturally leads to a requirement for a "reborrow this &mut T as &mut MaybeUninit<T>" operation, which is what this issue is about.

[RalfJung]

borrows of the inside of a RefCell

This one could use a "&mut but without the protectors" kind of type. That's just not something we have currently. I am not sure it provides enough benefits for us to want to add it -- currently we can't really map that to anything in LLVM I think.

Box with a custom allocator

This one simply does not qualify for "as long as this value is alive, nobody will read or write to the referenced memory, except via this reference/pointer-like thing". The pointer in the Box will be passed back into dealloc and can arbitrarily alias with other pointers inside the allocator there. At no point here did any pointer stop being alive. (It's unclear what a "value" being alive should mean as values only ever exist within a single statement in Rust. There are no values in memory, just bytes.) So I think you're just mistaken in having this one in your list.

We (Nia and me) do have plans for custom allocators with optimizations. They amount to adding a new NativeAllocator wrapper that will add the requisite LLVM attribute and will carry a bunch restrictions similar to rust-lang/rust#159720 in its documentation. It will also only work for StaticAllocators (as defined in rust-lang/rust#157428).

[ia0]

Unfortunately, you can't have the "safe code can't write to" constraint in current Rust; safe Rust code can write through any &mut reference

Sorry, I meant something like this:

#[repr(transparent)]
pub struct Tombstone<T: 'static>(&'static mut T);

impl<T> Tombstone<T> {
    pub fn drop_in_place(r: &'static mut T) -> Self {
        unsafe { std::ptr::drop_in_place(r) };
        Self(r)
    }

    pub fn init_in_place(self, v: T) -> &'static mut T {
        let Self(r) = self;
        unsafe { std::ptr::write(r, v) };
        r
    }
}

While subobject provenance is uncertain, you can't have a safe "drop in place" function that takes a &mut and returns a &mut as in your top post. So you must return an opaque type like Tombstone.

[ais523]

borrows of the inside of a RefCell

This one could use a "&mut but without the protectors" kind of type. That's just not something we have currently. I am not sure it
provides enough benefits for us to want to add it -- currently we can't really map that to anything in LLVM I think.

I actually believe it's possible to implement this (for RefCell's RefMut, at least) using exposed provenance: before dropping a RefMut, you expose the provenance of the reference to the part of the RefCell that stores the value, and when creating a new RefMut, you start with the address of the part of the RefCell that stores the value and then make it into a pointer using the exposed provenance (and then reborrow it into a reference). Because the new reference has the same address and provenance as the old one, it is the same reference, and thus you can write through it without violating the noalias because that only bans writing through a different reference. (This needs special cases for the first ever reference, and for allowing for potential moves of the RefCell, but they are straightforward.)

Box with a custom allocator

This one simply does not qualify for "as long as this value is alive, nobody will read or write to the referenced memory, except via this reference/pointer-like thing". The pointer in the Box will be passed back into dealloc and can arbitrarily alias with other pointers inside the allocator there.

This is not a mistake, but it's an awkward disconnect between the opsem that's suitable for boxes and the opsem that Rust currently uses.

The way it would work would be for the Box to hold a reference, but to convert the reference into a pointer before passing it into dealloc, and for the reference to only enforce uniqueness / lack of aliases while the reference existed (so it wouldn't matter what happened inside dealloc). This is conceptually simple, but it's very at odds with the way that Stacked Borrows works (because Stacked Borrows assumes that as long as a pointer derived from a reference has usable provenance, all that reference's invariants must hold, whereas this requires ending the invariants of a reference while still holding onto a pointer that was derived from it).

What I'm trying to do is to figure out a way to try to make these incompatible approaches more compatible with each other. There are special cases where it works even in current Rust (e.g. if the allocator remembers the provenance from deallocations and then reuses that provenance whenever it reuses the same memory for future allocations, then you don't get any conflicts with safe-Rust opsem models; indeed, such allocators can be written in safe Rust even at the moment, so any opsem that supports safe Rust must support such allocators). Gaining full compatibility is likely to need new language features, but it seems unwise to propose those until I have a good understanding of what the current limitations are, and can point to them as justification.

[RalfJung]

I actually believe it's possible to implement this (for RefCell's RefMut, at least) using exposed provenance

I have no idea what you are talking about. You cannot communicate anything precise to the compiler using exposed provenance. And if you don't want to communicate the precise semantics to the compiler, you can just do what we do today -- use raw pointers (and stay with strict provenance).
There is no meaningful sense in which exposed provenance can "implement" these semantics.

When I said "map to LLVM" I meant "give LLVM enough information so it can use this for optimizations". It is obviously possible to map RefCell to LLVM in a UB-free way, we're already doing that today. It's just not useful to add a new reference type in Rust if it compiles exactly like raw pointers. (Your proposal gives the compiler even less information than raw pointers which makes no sense at all.)

The way it would work would be for the Box to hold a reference, but to convert the reference into a pointer before passing it into dealloc, and for the reference to only enforce uniqueness / lack of aliases while the reference existed (so it wouldn't matter what happened inside dealloc). This is conceptually simple,

Lol, there's nothing simple about this.^^ Please give a description as an operational semantics in Tree Borrows style if you want to convince us that this is simple.

Anyway this is veering very far from the original question. I have recorded this as an explicit open question in #84. I think this issue can be closed then? This issue here now is more about "let's invent an entirely new aliasing model" than about that sub-question...

[ais523]

I actually believe it's possible to implement this (for RefCell's RefMut, at least) using exposed provenance

I have no idea what you are talking about. You cannot communicate anything precise to the compiler using exposed provenance. And if you don't want to communicate the precise semantics to the compiler, you can just do what we do today -- use raw pointers (and stay with strict provenance). There is no meaningful sense in which exposed provenance can "implement" these semantics.

You can: using references together with exposed provenance gives more precise aliasing guarantees than using raw pointers together with strict provenance. I implemented a (mutable-borrow-only) RefCell in this style in order to demonstrate: https://rust.godbolt.org/z/7jd5x55P5 (Note that this code is very close to a known LLVM miscompile, so I added a command line option to disable the optimisation pass containing the miscompile, to ensure that the comparison remains valid.)

LLVM is unaware that two std::cell::RefMut do not alias with each other, so it cannot vectorise the copy loop. I consider this to be a fairly serious missed optimisation, because the gains from vectorising are usually very large. Meanwhile, LLVM does know that two MyRefMut do not alias (because they are both mutable references and thus noalias), so it can vectorise that copy loop. The exposed provenance is used in order to avoid breaking the semantics of noalias / violating the Stacked Borrows protectors (and more specifically, is being used to communicate something precise: the precise moment at which the noalias requirement is supposed to end).

Lol, there's nothing simple about this.^^ Please give a description as an operational semantics in Tree Borrows style if you want to convince us that this is simple.

The core of Stacked Borrows is also conceptually pretty simple (with the complexities largely being around things like two-phase borrows and protectors), but nonetheless takes a while to write up in a properly formal style, and to ensure that it permits all the optimisations that people would expect it to permit. I am interested in working on something like this, but I can't guarantee that I can produce a properly formal semantics in the short-to-medium term. (Indeed, part of the reason I ask questions like this is to understand what the relevant constraints on the aliasing model are, in order to help inform what it should be.)

Anyway this is veering very far from the original question.

I agree. It can be frustrating to engage with this repository sometimes, because I tend to ask questions which need a lot of context to understand the motivation for. The questions can be hard to answer correctly without context, but the context is too big to really fit in one thread and thus tends to derail it. I consider this an undesirable outcome, but am not sure how to prevent it happening.

Anyway this is veering very far from the original question. I have recorded this as an explicit open question in #84. I think this issue can be closed then? This issue here now is more about "let's invent an entirely new aliasing model" than about that sub-question...

Yes, I think this is sufficient: I wanted to know whether or not this was presently guaranteed to be sound, and we seem to be in agreement that this is currently an open question (and thus unwise to rely on in the short term, even though it may still end up becoming a guarantee in the long term). The wider questions about the aliasing model are important but this is the wrong place for them.

[RalfJung]

The core of Stacked Borrows is also conceptually pretty simple (with the complexities largely being around things like two-phase borrows and protectors), but nonetheless takes a while to write up in a properly formal style, and to ensure that it permits all the optimisations that people would expect it to permit. I am interested in working on something like this, but I can't guarantee that I can produce a properly formal semantics in the short-to-medium term. (Indeed, part of the reason I ask questions like this is to understand what the relevant constraints on the aliasing model are, in order to help inform what it should be.)

Writing it up formally and making sure it handles corner cases correctly is a lot of work. But even a kind of hand-wavy description can help a lot, as long as the state space is spelled out reasonably precisely (even informally).

I agree. It can be frustrating to engage with this repository sometimes, because I tend to ask questions which need a lot of context to understand the motivation for. The questions can be hard to answer correctly without context, but the context is too big to really fit in one thread and thus tends to derail it. I consider this an undesirable outcome, but am not sure how to prevent it happening.

I also experience some frustration with your issues since I can't really figure out what goal you are trying to achieve. For this specific issue I think you're trying to do too many things in one issue. Personally I considered the question about "why are you overwriting" answered when you mentioned that the caller could do it in safe code. Everything after was just moving the thread off-topic without a clear reason.

I don't think an issue here is the right venue for general undirected exploration / "here are some vague ideas for a new reference type". That's better suited for a blog post laying out the vague ideas and a Zulip thread discussing them. In this repo we are trying to figure out the exact semantics of the existing language, not designing new semantics for new language features (such as new reference types). So I consider proposals like yours to be largely off-topic here. Maybe that is part of the reason for the frustration -- you are trying to turn this issue tracker into something it is not meant to be. Or maybe I misunderstood the nature of your issues.

[ais523]

I was in fact writing such a blog post when I submitted this issue. I had asserted in the draft blog post that it was safe to write a value of the wrong type through a reference as long as the original reference was never used again, realised I needed a source for that, then came over to this repository to try to find it (and once I couldn't find it, created the issue).

The blog post is not actually about changes to the aliasing model – rather, it's about how to write code within the existing aliasing model without undefined behavior and without the loss of optimisation you get if you use raw pointers. Doing this sort of thing necessarily means that you're constantly running up against corner cases of the aliasing model because if you stay away from the area that's tricky to reason about, you also stay away from the area that provides the optimisations.

I will still probably be able to write the blog post, but will need to restructure it significantly, because this lack of guarantee means that the simple examples I was hoping to use are no longer simple and thus no longer work as an introduction to the topic. I'll have to figure out a different way to introduce it instead.

[RalfJung]

You can: using references together with exposed provenance gives more precise aliasing guarantees than using raw pointers together with strict provenance. I implemented a (mutable-borrow-only) RefCell in this style in order to demonstrate: https://rust.godbolt.org/z/7jd5x55P5 (Note that this code is very close to a known LLVM miscompile, so I added a command line option to disable the optimisation pass containing the miscompile, to ensure that the comparison remains valid.)

I don't think this code is sound. The self.value.get() invalidates the provenance that was exposed by a previous MyRefMut::drop, causing UB if that provenance is still protected (e.g. because the MyRefMut was passed into a function).

But we are really veering very far away from this issue now so let's continue this one on Zulip please.

I was in fact writing such a blog post when I submitted this issue.

Ah, nice. :)

I will still probably be able to write the blog post, but will need to restructure it significantly, because this lack of guarantee means that the simple examples I was hoping to use are no longer simple and thus no longer work as an introduction to the topic. I'll have to figure out a different way to introduce it instead.

Well, you could also turn it into an argument for why we should allow this particular pattern. The reason we haven't fixed those rules yet is that we are still collecting data, after all. I am quite skeptical about the entire UB in #84, so personally I'd be fine with say that it's only UB if someone actually uses the parent pointer again to read the discriminant -- but I don't know how the team feels about that.