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 :weary:

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 https://github.com/rust-lang/unsafe-code-guidelines/issues/326#issuecomment-1095340564 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 https://github.com/rust-lang/unsafe-code-guidelines/issues/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.

[saethlin]

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.

The standard library doesn't provide an AliasableBox, so authors of unsafe code who want this behavior have used Box. Not only as a way to remember that the pointer needs to be freed, but as a way to allocate and deallocate (I don't mean to pick on tokio here, it's just what is at the top of my mind): https://github.com/tokio-rs/bytes/blob/724476982b35f094b59d160ecc02c042082ac604/src/bytes.rs#L942-L945

unsafe fn rebuild_boxed_slice(buf: *mut u8, offset: *const u8, len: usize) -> Box<[u8]> {
    let cap = (offset as usize - buf as usize) + len;
    Box::from_raw(slice::from_raw_parts_mut(buf, cap))
}

https://github.com/tokio-rs/tokio/blob/252b0fa9d557c241d64d8fcd95747a288429da00/tokio-util/src/sync/cancellation_token.rs#L551-L565

    fn decrement_refcount(&self, current_state: StateSnapshot) -> StateSnapshot {
        let current_state = self.atomic_update_state(current_state, |mut state: StateSnapshot| {
            state.refcount -= 1;
            state
        });

        // Drop the State if it is not referenced anymore
        if !current_state.has_refs() {
            // Safety: `CancellationTokenState` is always stored in refcounted
            // Boxes
            let _ = unsafe { Box::from_raw(self as *const Self as *mut Self) };
        }

        current_state
    }

[Diggsey]

This is something that could be addressed in an edition though, since the compiler can choose to emit noalias on a crate-by-crate basis. We could provide better tools for unsafe code (eg. AliasableBox) for crates on new editions to use.

[Lokathor]

Can't we provide better tools in all editions? There's no obvious reason for AliasableBox to not be available in all editions.

[Diggsey]

Of course we can, but we'd need to keep existing code that uses Box working on old editions.

[Lokathor]

So wouldn't Box always be noalias, in all editions? And then AliasBox would be a new type people could that's also in all editions? And code could transfer to AliasBox if that's what they actually intend?

It just seems exceedingly confusing to make such a subtle change over an edition when we know it's specifically affecting unsafe code. However it's set up, it should be the same across all editions.

[Diggsey]

Well the problem with that is the examples of existing code that is only correct when Box is not noalias, but that happens to work today.

[saethlin]

I worry about that kind of characterization, because that could apply to any increase in information that rustc feeds to LLVM. We shouldn't block all additions of LLVM attributes behind an edition, just because they may produce surprising compilation results for some users. That is why I am focusing on whether or not we should expect users to be familiar with semantics that are communicated to LLVM.

[saethlin]

The huge change in bincode definitely has to do with aliasing optimizations.

I did this same experiment but with the code that puts noalias on Box removed. I see the same improvements in the bincode benchmarks using BufReader. So whatever is happening there, it looks like noalias on &mut is sufficient.

[nico-abram]

Would it be useful/make sense to add an unstable flag to disable noalias on everything but &mut?

[CAD97]

While I'm thinking about it: adopting something like the storages API would allow that Box<T, Global> (the current, and the default) could use non-noalias semantics with a handle of ptr::NonNull<T> and Box<T, GlobalUnique> could use noalias semantics with a handle of ptr::Unique<T>, or vice-versa.

[saethlin]

Would it be useful/make sense to add an unstable flag to disable noalias on everything but &mut?

Who would use such a flag? A skim over the search for Zmutable-noalias results on https://cs.github.com turns up mostly forks of Rust and people turning it on (probably because they want maximum optimization and the code is old or they don't know it is the default?). I can find exactly one repo that sets -Zmutable-noalias=no, libhermit-rs, which has it turned off as a mitigation for UB in the codebase, and fuschia sets -Zmutable-noalias=off because of https://github.com/rust-lang/rust/issues/63818. That's it. I agree that it would be easier for people to do benchmark experiments if they had a flag instead of editing the compiler's source to remove noalias on Box, but we don't even have an ecosystem benchmark suite yet.

[RalfJung]

Unsurprisingly it turns out that Vec is full of aliasing violations, if you interpret its Unique like a suitably sized Box: https://github.com/rust-lang/rust/pull/94421.

[saethlin]

Miri surely does not like that PR, but it's not entirely due to the current implementation of Vec. The PR needs a lot of careful attention, and probably a better way to run Miri on it (running miri-test-libstd on a local checkout and manually dumping the cache is the best I could come up with, and that's quite an arduous procedure). For example, this diff trips right over the issue that the comment above it says to avoid:

    pub fn as_mut_ptr(&mut self) -> *mut T {
        // We shadow the slice method of the same name to avoid going through
        // `deref_mut`, which creates an intermediate reference.
-        let ptr = self.buf.ptr();
+        let ptr = self.buf.as_mut_ptr().cast::<T>();
        unsafe {
            assume(!ptr.is_null());
        }

There's also an issue where the extend impl when passed a slice produces an uninitialized Box.

(but yes, among other things, the IntoIter as it stands after that PR is unsound due to Box invalidation, and I expect there are other problems)

(oh whoops I read your comment here instead of commenting on that PR) sigh

[Gankra]

Something missing from this discussion (that I wasn't aware of) was that the understanding of Pin has matured a lot, and the compiler and miri understand that noalias must be applied more delicately when Pin is involved.

This code compiles and runs happily on miri (playground):

use core::pin::Pin;

fn fun(bocks: Pin<Box<i32>>, intrusive: *mut i32) -> i32 {
  unsafe { *intrusive = 5; }
  *bocks
}

fn main() {
  let mut bocks = Pin::new(Box::new(16));
  let ptr = (&mut *bocks) as *mut _;
  let result = fun(bocks, ptr);

  assert_eq!(result, 5);
}

If the answer to this situation is just "oh yes, if you're doing stable-address-reasoning or intrusive stuff with Box/Vec, you should wrap them in Pin to signal to the compiler that this is happening" that's... far less concerning, and kinda reasonable.

And for the record, Pin isn't being terribly magical with Box, this code also compiles and runs fine with Vec (just proving to myself that ergonomics don't fall over, I know miri can't catch anything here) (playground):

use core::pin::Pin;

fn fun(vec: Pin<Vec<i32>>, intrusive: *mut i32) -> i32 {
  unsafe { *intrusive = 5; }
  vec[1]
}

fn main() {
  let mut vec = Pin::new(vec![16, 27]);
  let ptr = (&mut vec[1]) as *mut _;
  let result = fun(vec, ptr);

  assert_eq!(result, 5);
}

[CAD97]

IIUC this is just the fact that the function argument protectors aren't recursive into struct fields -- the code also passes miri using ManuallyDrop instead of Pin (ignoring the memory leak of course), and would do so for any other newtype wrapper.

The actual relaxation is currently done for ?Unpin types. However, the exact extent of the "UnsafeMutCell" property, just like that of UnsafeCell, is under question; whether it should be applied granularly at a cell border or more loosely infect the entire containing type. If I understand the current state of things, @RalfJung believes that having the relaxation "infectious" is a desirable simplification of the model, and @chorman0773 is strongly arguing for more granular relaxation, as that maps well to their XIR model and allows them to process pre-monomorphization code.

Both models agree that pinning a pointer to an Unpin type is a complete no-op semantically, though.

[RalfJung]

Something missing from this discussion (that I wasn't aware of) was that the understanding of Pin has matured a lot, and the compiler and miri understand that noalias must be applied more delicately when Pin is involved.

I would describe this more as, codegen and miri have caved and added temporary hacks for making self-referential types with Pin not UB. A proper solution should still be found one day and then self-referential generators will be adjusted to use that. Cc https://github.com/rust-lang/unsafe-code-guidelines/issues/148

[Gankra]

So perhaps you need an Intrusive<i32> wrapper or something. Regardless, I think these key points hold:

• Pin exists to facilitate self-referential/stable-address/intrusive structures using safe pointer types
• To do this, there clearly must be an idiom to allow for Box<MyIntrusive> or (Box<MyInstrusive>, *mut MyIntrusive) to be moveable (I think this sort of thing is a core idiom for relocatable Futures?)
• Therefore even under the strictest possible interpretation of Unique/Box, there must presumably be some "correct" idiom that combines Pin and Box and lets you pass/return the Box as a Box whose destructor can be run automatically without invalidating internal pointers

Yeah?

[RalfJung]

Probably, Box<UnsafeAlias<T>> should be a version of Box that does not make uniqueness guarantees.

[Noratrieb]

There has been quite some discussion here about Box<T>, but barely any about Vec<T>. In my opinion, the case about vec is clearer than about box. We can't really make Vec<T> Unique. First of all, that would cause a lot of breakage - aliasing vec is currently ok, even if it's not specified to be so, and code relies on that fact.

But also, unsafe code wants to alias vecs in many ways, and making vec aliasable is directly useful for that code. For Box<T>, it's easy to say "just use raw pointers". Box to raw pointer migration is usually pretty simple (although I still am of the opinion that box should not be unique). But for vec, it's not that simple. Vec is doing some tricky things around reallocation, and expecting unsafe code that wants to alias vecs to reimplement all of this logic is unreasonable. And I doubt that there is any actual benefit from making Vec<T> Unique.

With this laid out, we get a new argument against Box<T> being Unique. If vec isn't unique, why should box be? The two types are similar, and this issue grouping them together is another sign of it. I think the two should be consistent with the aliasing rules as to not cause even more confusion for unsafe code. If we say that vec can't be unique, then box shouldn't be either.

Box<T> being aliasable is directly useful to a lot of unsafe code. And I like the "just a RAII pointer" model of box a lot more than the "owned reference" model - but that's just personal preference.

While I don't think that there is any performance impact of noalias on boxes, we might want to take a look at it anyways after rust-lang/rust#99436 has landed.

[saethlin]

How do you propose we assess the perf impact of noalias on boxes? rustc-perf has endorsed worse optimization as a perf improvement, because rustc can ask LLVM to do a lot more work but not benefit much from said work itself. So I suggest that the compiler's perf suite is not sufficient to determine what the perf implications are here.

Additionally, if anyone can find an example where removing noalias on Box<T> introduces a perf regression, I would like to see whether it is possible to recover the perf regression using T or &mut T instead.

If it is decided that we cannot determine a perf regression (or don't have the resources to investigate this) I think we should remove noalias from Box<T> on the basis that this is an aliasing guarantee that users do not expect. It is documented unstably only as a reaction to the implementation relying on undocumented guarantees, so the compiler would be just as within its rights to add back this attribute later (if perf regressions are reported) as it is to keep it now.

[Noratrieb]

I have added a new flag to rustc that disables the LLVM noalias attribute on Box<T> called -Zbox-noalias=no. This can now be used to assess the current performance impact of noalias on box. There was already a run to see whether it would make the compiler faster, rust-lang/rust#99527, and it revealed no performance impact. This isn't a great benchmark though as rustc mostly uses arenas and doesn't use Box<T> all that much. I (with the help of @conradludgate) have also done a few benchmarks of crates, see The Gist for the results. The results were rather inconclusive, and more benchmarking is needed to make sure that noalias really doesn't improve performance. I would love for people to run some benchmarks!

[XrXr]

How do the current rules, as implemented by codegen, interact with Box::into_raw? The current documentation draws parallel with &mut T, but it reads to me that it has stricter requirements. In particular, &'a mut T only asserts uniqueness over a, whereas the current wording reads like a mut borrow invalidates all derived pointers in perpetuity, and that it's UB to use them even after the box is consumed by Box::into_raw, where presumably the uniqueness assertion ends.

The aliasing rules for Box<T> are the same as for &mut T. Box<T> asserts uniqueness over its content. Using raw pointers derived from a box after that box has been mutated through, moved or borrowed as &mut T is not allowed.

I'm asking because I thought to write something like this:

use std::mem::MaybeUninit;
fn main() {
    let mut alloc = Box::new(MaybeUninit::uninit());
    let stable_ptr: *const i32 = alloc.as_ptr(); // in real code this gets stashed somewhere else
    alloc.write(128); // stand in for non trivial init (without `unsafe`). implicit mut borrow to call MaybeUninit::write
    let _for_dealloc_later = Box::into_raw(alloc);
    std::process::exit(unsafe { stable_ptr.read() });
}

which Stacked Borrows rejects, but codegen seems to be fine with:

; playground::main
; Function Attrs: noreturn nonlazybind uwtable
define internal void @_ZN10playground4main17h03f67cbecc7943cbE() unnamed_addr #4 personality ptr @rust_eh_personality {
start:
; call alloc::alloc::exchange_malloc
  %_16 = tail call fastcc ptr @_ZN5alloc5alloc15exchange_malloc17hc2840d7a656e336eE()
; call std::process::exit
  tail call void @_ZN3std7process4exit17h0304ff240336b59bE(i32 128) #10
  unreachable
}

It seemed to have done its own alias analysis before generating the LLVM IR.

I guess to be on the safe side I should use more unsafe and get away from Box as early as possible, so all the raw pointers are derived from the result of Box::into_raw, and not from when the box is live (even though they have the same address they have different provenance?).

[RalfJung]

I guess to be on the safe side I should use more unsafe and get away from Box as early as possible, so all the raw pointers are derived from the result of Box::into_raw, and not from when the box is live (even though they have the same address they have different provenance?).

Indeed, that is the correct approach. Mixing Box and raw ptr accesses to the same location is running a high risk of violating aliasing guarantees.

Note that there is no stability guarantee for codegen: codegen can become smarter about exploiting alias information any day. That's why Miri implements a much stricter check.

[chorman0773]

I don't believe I made my position explictly earlier in the issue, so I'll make it now. Box<T> in particular should not be special in this regard. In terms of user types, there is no alternative to Box possible (in terms of available operations and ergonomics) and in the current language there cannnot be an alternative (there are a number of proposals that are attempting to make such alternatives possible, but they are in various stages of development).

With references, if you don't want to enforce aliasing rules until you make an access, you can easily make a pub struct MyRef<'a,T: ?Sized>(*const T); pub struct MyMut<'a,T: ?Sized>(*mut T);, and with appropriate trait impls, these are almost interchangeable in terms of user code and uer ergonomics with &'a T and &'a mut T. This cannot be done with Box, thus if Box has special semantics, there is limited choice but to accept those special semantics, or forgo the ergonomics of using Box. While I can imagine optimizations that would make use of Box uniqueness, it's hard to imagine any that would have a benefit that wouldn't also exist from reference accesses (via Deref) that are performed. As a compiler developer: I'm willing to explore such optimizations in the future, where the type which they apply to has an alternative, either provided by the standard library or writable in user code, but I am also willing to forgo them while such an alternative does not exist.

Note that while the motivation against Vec in this case is limited compared to Box because you can (mostly - dropck_eyepatch) write Vec in completely user code, I think for consistency, there isn't a reason to make Vec<T> have aliasing rules either.

[RalfJung]

While I can imagine optimizations that would make use of Box uniqueness, it's hard to imagine any that would have a benefit that wouldn't also exist from reference accesses (via Deref) that are performed.

Plenty of optimizations rely on protectors, which are only possible for function arguments. The derefs of a Box performed inside some function cannot replace the aliasing requirements arising from when the Box is passed as an argument.

The solution to the problem you describe should be to make the behavior of Box also available to user-defined types; I don't view this as a great argument against Box aliasing requirements.

[chorman0773]

Plenty of optimizations rely on protectors, which are only possible for function arguments. The derefs of a Box performed inside some function cannot replace the aliasing requirements arising from when the Box is passed as an argument.

I'd be curious how true this is, or whether it's simply an artifact of llvm's limited expressibility (in terms of having dereferenceable and noalias). I'm fairly certain I could replicate a number of relevant &mut T/&T optimizations w/o protectors (xlang does not have an equivalent), and apply them to in-scope references. That being said, I will concede that you lose them for llvm today.

The solution to the problem you describe should be to make the behavior of Box also available to user-defined types; I don't view this as a great argument against Box aliasing requirements.

I think this would be a viable solution if it was made available. Until then, the world is what it is, and I can't see a user Box being writable in less than 2 years. I would accept AliasableBox in stdlib as an alternative, but that's also fun. More likely, if we make Box aliasable, and want to return to box-specific optimizations, UniqueBox could be made a thing just as easily as the converse (for some deifnition of "easily").

[RalfJung]

I'd be curious how true this is, or whether it's simply an artifact of llvm's limited expressibility (in terms of having dereferenceable and noalias). I'm fairly certain I could replicate a number of relevant &mut T/&T optimizations w/o protectors (xlang does not have an equivalent), and apply them to in-scope references. That being said, I will concede that you lose them for llvm today.

I think protectors are very much required. I've spun this into a separate thread on Zulip since it is mostly orthogonal to this issue.

[RalfJung]

Grandfathering in some comments from https://github.com/rust-lang/unsafe-code-guidelines/issues/258:

This comment states

I think maybe this boils down to "I don't feel like keeping two Box<T> to the same T if you never use it should be disallowed". Whereas I do feel like having two &mut T to the same T even if you don't use them should be disallowed. I guess to me the mere existence of a &mut T means that you cannot have any other references to that T.

FWIW, if Box were to become a regular Unique (unlike its current implementation in SB and TB that makes it more like &mut), then an unused box doesn't interfere with anything -- aliasing requirements only come up when the box is actually used. That is still compatible with noalias, but potentially incompatible with "dereferenceable on entry" (due to https://github.com/rust-lang/unsafe-code-guidelines/issues/435).

This comment says

My expectation is that Unique<T> would have the same aliasing guarantees as &mut but would free its contents when dropped.

That is incompatible with using Unique in Vec which might not actually have any memory behind that pointer.

[Kolsky]

Related question: TB mentions reborrowing of mutable references, but doesn't say anything about Box I think (or Box reborrowing specifically in this case). In other words, regardless of noalias, is this

let b1 = box stuff;
let b2 = Box::from_raw(&mut *b1);
_ = Box::into_raw(b2);
drop(b1);

allowed in the aliasing model? If not, but only due to Box also acting as T, will ManuallyDrop around it suffice? Or can b2 be used without moving its value?

[chorman0773]

I believe that's what this issue asks.

[RalfJung]

That example should be fine even under Stacked Borrows since everything is well-nested. You are basically "reborrowing" the Box.

[RalfJung]

@thomcc During an opsem meeting, someone mentioned that you are rather firmly against having any sort of aliasing restriction for Vec. I would be curious to hear more about that. Do you have concrete pieces of code that you think must work and are worried would break due to aliasing rules, or are you fundamentally opposed to any kind of aliasing requirement? Do you know what t-libs-api thinks about this?

Vec is defined via Unique and there at least used to be the intention to make Unique carry some noalias annotation, once we figure out what exactly that means.

[RustyYato]

I know that crates like typed_arena would break. https://docs.rs/typed-arena/latest/typed_arena/struct.Arena.html

It relies on Vec as the storage mechanism, and allows references into the Vec to persist across Vec::push. Which would break if Vec invalidated references into it after moves/borrows of the Vec.

I know this crate is unsound because it isn't hardened against malicious code, but the basic premise is currently sound.

[thomcc]

Unlike with Box, we've never documented that Vec has this restriction, and it's unintuitive. It also breaks a lot of reasonable use cases. I think having it on Vec requires quite a bit more justification than with anything else.

there at least used to be the intention to make Unique carry some noalias annotation

My understanding was it was more an indication that these are types which semantically could be noalias. Certainly for the time I've been working on the stdlib, Unique sticks around not because of noalias at all, but because it solves the common need of: "we want a NonNull<T> that also has PhantomData<T>".

Not for nothing, but understanding of aliasing semantics back then was not very firm, so I don't know that legacy holds much weight in my mind, especially when NonNull didn't exist when it was created.

Do you know what t-libs-api thinks about this?

No.

[RalfJung]

I don't think typed-arena would break. We have a prototype for Unique semantics, and while it doesn't yet entirely behave the way we'd like, at least our simple arena tests pass. That's why I was asking.

[RalfJung]

To elaborate a bit: retagging only happens when a pointer is moved by-value. For arenas, the moment the first element got created, the arena will not be moved any more -- everyone just has references to it. This means the Unique never gets retagged so we never have an aliasing violation.

Furthermore, Unique is different from references in that we can't know how much memory there is behind that pointer, so we only retag memory that is actually being accessed. This makes even the following code legal:

let mut v = vec![0, 1];
let ptr1 = v.as_mut_ptr();
let mut v2 = v;
let ptr2 = v.as_mut_ptr().add(1);
ptr1.write(0);
ptr2.write(0);

The aliasing requirements only start rejecting code when the same element gets accessed again with a freshly retagged pointer (e.g., if ptr2 above also pointed to index 0).

Vecs are moved rather rarely I think, so I don't think a lot of code would be affected by this. Of course that also means not a lot of code would benefit from the potential optimizations here.

Unlike with Box, we've never documented that Vec has this restriction, and it's unintuitive.

That is fair.

It also breaks a lot of reasonable use cases.

That is the part I am disputing. At least I have not seen evidence of that.