What are the uniqueness guarantees of Box and Vec?

[RalfJung]

Box and Vec have internally used the Unique pointer type since Forever (TM). The intention was that that gives some some special aliasing rules. Box is even emitting noalias to LLVM, so we might have optimizations already exploit those aliasing rules.

However, it looks like none of this is actually surfaced in the documentation (Cc @saethlin), leading to a significant risk that code out there might violate whatever the aliasing rules end up being.

For whatever it's worth, Miri with Stacked Borrows does treat Box rather similar to &mut, but does not do anything special with Vec. I have ideas for how the Next Aliasing Model can treat Unique special (so Box itself no longer needs to be special, at least if we decide to "look into" private fields when applying aliasing rules which is its own whole separate discussion), bot nothing concrete yet.

For each of these types we basically have two options:

• Keep going with the intention of making them have aliasing guarantees. Then we should probably put something into the docs. This might be considered a breaking change by some.
• Give up on this plan (and, in the case of Box, remove the noalias and the special treatment in Miri). This will make some people very sad. Cc @Gankra @nikomatsakis

[chorman0773]

I think even that if Unique doesn't have alias rules, it's existance is useful. It's a NonNull owning raw pointer, and (aside from any aliasing considerations) can be written in user code.

[Gankra]

Unique doesn't "have" to have special semantics. It exists in case it's useful for it to, and to mark all the types that are "like box" if we ever figure out ways to make box magic more available to other types.

I don't have a good sense for how useful it is to make Box "smarter" but certainly we have a lot of anecdotal evidence that it leads to surprises/sadness. In particular I've been told that just moving a Box apparently invalidates even raw internal pointers, which, sounds miserable. Like I can get it from the strictest interpretation of "it's as if it was a local var" and certainly I wouldn't expect borrowck to ever let you get that cute, but it seems like unsafe code should be allowed to rely on Box/Vec having stable addresses since that's like, one of the major features of indirection!

[RalfJung]

Okay -- I don't really care if Unique exists or not when it doesn't have special semantics, so I removed that part from the OP.

I remember optimizing some tight Vec loops being a prime motivation for making Unique special (specifically, this might let the compiler know that the length field does not change, or some such thing).

[RalfJung]

I don't have a good sense for how useful it is to make Box "smarter" but certainly we have a lot of anecdotal evidence that it leads to surprises/sadness. In particular I've been told that just moving a Box apparently invalidates even raw internal pointers, which, sounds miserable. Like I can get it from the strictest interpretation of "it's as if it was a local var" and certainly I wouldn't expect borrowck to ever let you get that cute, but it seems like unsafe code should be allowed to rely on Box/Vec having stable addresses since that's like, one of the major features of indirection!

I can imagine relaxing the Box rules by a lot, but still keeping some special status. (That would probably happen with the Next Aliasing Model.)

[saethlin]

Just to make sure my position is clear here, I am in favor of removing noalias on Box. I'm thinking very much from the perspective of a Rust user, not a Rust implementer, so since the type Unique is an implementation detail I don't really have an opinion on it.

I think that noalias on Box it is distinctly unlike noalias on &mut, which has long been communicated to the community, in the vague terms that there are special optimizations possible on &mut due to its uniqueness guarantee. I never heard of such a thing for Box until I learned about Stacked Borrows. So I think if we need to declare current code UB under a formal memory model in order to provide the promised &mut optimizations, there's an argument that this is a resolution of conflicting promises that Rust made: stability versus this extra optimization power. But that argument does not apply to Box. As far as I can tell, the properties of Unique is something that Rust contributors have kept entirely to them/ourselves. So adding UB here is completely unexpected.

And I want to call out that under Stacked Borrows, if a pointer type behaves like &mut, it doesn't only provide aliasing guarantees as a function argument which is what noalias is traditionally focused on, from the perspective of a user, Box loses address stability. In particular, this program is UB:

fn main() {
    let b = Box::new(0u8);
    let ptr = &*b as *const u8;
    let _a = b;
    unsafe {
        println!("{}", *ptr);
    }
}

Exactly why it is UB depends on if you are considering Stacked Borrows with or without raw pointer tagging. But in any case, this is deeply surprising. What else is "A pointer type for heap allocation." (that's how the current docs describe it) good for, if not address stability?

Also the std::boxed and Box documentation does not mention the word "alias" and in only 2 places does it even mention the word "unique", and in that case it is used in the sense of the C++ std::unique_ptr's uniqueness: If you have 2 instances of this type, they point to different allocations.

[RalfJung]

And I want to call out that under Stacked Borrows, if a pointer type behaves like &mut, it doesn't only provide aliasing guarantees as a function argument which is what noalias is traditionally focused on, from the perspective of a user, Box loses address stability. In particular, this program is UB:
[...]
Exactly why it is UB depends on if you are considering Stacked Borrows with or without raw pointer tagging. But in any case, this is deeply surprising. What else is "A pointer type for heap allocation." (that's how the current docs describe it) good for, if not address stability?

What if the Next Aliasing Model made that not UB (by not doing "retagging" on Box as often as we do that on reference)? There is a huge design space of possible aliasing restrictions, and what Miri currently implements is among the most strict possible. The goal was precisely to get feedback about whether that is too strict and which patterns should be allowed by relaxing the rules.

With regards to keeping noalias or not, the following is most likely UB under LLVM noalias, so if that is also considered "too much UB" then indeed it seems best to just remove all aliasing restrictions entirely:

fn fun(x: Box<i32>, y: *mut i32) -> i32 {
  unsafe { *y = 5; }
  *x
}

let mut b = Box::new(16);
let ptr = *mut *b;
fun(b, ptr);

[saethlin]

I wish I knew if such code is written, because I suspect all crates that arrive in this situation are UB according to Stacked Borrows before they get to this call 😩

But from a more theoretical perspective, it's not clear to me that any author of Rust code would expect that function to be UB. I think we've done a pretty good job educating people via the docs that Box is just an RAII allocation. Such a change to retagging does get us out of the situation where it seems like Box isn't a stable pointer. So it might decrease the disbelief people experience when learning that Stacked Borrows thinks this code is invalid, but I'm still at a loss for how to explain to people how they could have possibly known that this code isn't valid.

[Gankra]

IMO it might be tolerable for a deref through the box to potentially invalidate pointers (ideally under looser rules based on the compiler "understanding" box and being able to do disjoint reborrows... so maybe it's semantically identical to &mut?), but moving the Box having side-effects is "too weird" without a really good explanation of why that might be problematic to allow.

I would tbh be fine with totally dropping noalias here, but I am not a Performance person.

[CAD97]

Just leaving my 2¢:

Much existing code does treat Box as a way to store a ptr::NonNull<T> which deallocs on drop, and then move it around while storing/using pointers into the heap allocation. (StableDeref, for all of its flaws, exists to encode this usage.) If at all possible, we should avoid making such usage UB.

However, usage that interleaves Box derefs with using internal pointers I don't think exists. At the very weakest, even though dereffing Box is a builtin, I think it's 100% safe to say that semantically it goes through the Deref[Mut] trait, thus applies a Retag (invalidating outstanding pointers via reference rules) when dereferenced.

However, I have a hard time saying that Ralf's example can be UB. I don't recall exactly how SB recurses into reference fields; if it wouldn't be UB with a definition of struct Box(&'static mut T), then it shouldn't be UB with the real Box.

Making moving a box into a function special, but allowing it when moving around in a single stack frame seems like a horrible state, because then refactoring out a function semantically changes the AM semantics.

My personal conclusion is that Box itself should not be noalias, and just apply retagging when derefferenced. (A shared retag when dereferenced to a shared place, a unique Retag when derefferenced to a unique place.)

---

It gets even more interesting with Vec, as we loosely imply that internal pointers are only invalidated when the Vec is reallocated. I believe making Vec unique would directly contradict this implication, at least if it ever retags stored bytes not directly being modified by a Vec operation.

[RalfJung]

However, I have a hard time saying that #326 (comment) can be UB. I don't recall exactly how SB recurses into reference fields; if it wouldn't be UB with a definition of struct Box(&'static mut T), then it shouldn't be UB with the real Box.

It's an open question (Cc #125). We can totally satisfy your axiom by making the Newtype(&'static mut T) version equally UB. ;)

[saethlin]

I am not a Performance person.

I kind of am. Or at least I fancy myself as. Or I try to be.

I just grabbed a few crates and tried running their benchmarks with -Zmutable-noalias=no then switching to -Zmutable-noalias=yes. On tinyvec and smallvec I see everything between a 37% improvement and a 139% regression. On nom I see between a 2% improvement and an 18% regression. On bincode I see improvements from 0% to 54%. I picked these crates because I wrote the benchmarks for tinyvec/smallvec and bincode, and someone suggested nom.

I looked at the regressions in smallvec and I cannot make any sense of them. The instructions in the hot part of the benchmark loop are almost entirely unchanged, but the structure of the benchmark loop surrounding them is rather different.

The changes in nom weren't big enough to be interesting.

The huge change in bincode definitely has to do with aliasing optimizations. It could be very interesting to keep an eye on that, because the code that basically vanishes from the profile is BufReader::buffer, and BufReader is implemented with a Box<[u8]>.

But overall the fact that we see such colossal regressions on microbenchmarks from providing more information to the compiler makes me question the wisdom of using current LLVM's ability to take advantage of noalias to make decisions about where to place it. It is possible that all those regressions will disappear.

---

It would be super cool if they were fixed soon, but I do not have the patience at the current time to minimize TinyVec or SmallVec into some LLVM IR that can be submitted in a report.

[chorman0773]

Actually, noting something for lccc's model specifically, it has

An implicit derive operation occurs in the following contexts:

• ...
• In a call instruction, when any parameter or corresponding argument is of a pointer type with a non-trivial validity attribute
• In an exit instruction, when returning from a function with a value of a pointer type with a non-trivial validity attribute or to a call site with a return type of such a pointer type.
• ...
  This only applies to xir pointer types - Box<T> is represented as a named type that refers to an aggregate definition. As far as lccc is concerned, this is true of all newtypes, with the exception of the internal (and unstable) Unique - which has an internal attribute that get's the frontend to translate the type in fields (although this doesn't affect calls, only loads and stores).

Of course, since rustc translates #[repr(transparent)] far earlier (vs. lccc, that currently handles them all the way in the backend), it may have more interesting concerns wrt. #[repr(transparent)] pub strucct Foo(&'static mut i32);.

(For those who care: a derive operation is xlang's generalization of an SB reborrow - strictly speaking it produces a new pointer from some computation on an existing one, asserting it's non-trivial validity, such as it's valid range or aliasing behaviour, in the process).

[nikomatsakis]

Interesting. To my mind, Box<T> is "claiming ownership" of its contents in much the same way that an &mut and friends do. I'll have to think more about it, but my kind of "rough take" on stacked borrows was that "safe types get their safe guarantees, and you use raw pointers otherwise". From that, I would expect that a function which takes a Box<T> as argument can assume, yes, that others are not accessing that memory.

That said, I also see that it would be nice to be able to allocate a box and move it around as a way to "remember" that the pointer needs to be freed later.

Tying the "uniqueness" to actually using the box may indeed be a reasonable compromise.

[Lokathor]

I've definitely used box as a way to say "handle the stupid allocation crap for me", but otherwise I've wanted only the pointing part and not the uniqueness and invalidating other pointers and all that stuff.

However, we could just add some simpler to use methods to our allocation system and "solve" the problem that way.