Aliasing rules for Box<T>

[RalfJung]

What should the aliasing rules for Box be? Stacked Borrows says they are the same as &mut T. (With the exception that no protectors are being added, so a Box<T> may actually be deallocated while a function is running. However, if we adopt #252, then even this difference will probably disappear.)

However, @jonhoo has a usecase that is in conflict with this. @jonhoo maybe you could briefly summarize what that is about? In particular I am wondering if you think you should be able to pull the same tricks with &mut-- so far I treated it as a given that both Box and &mut should require uniqueness in pretty much the same way.

[jonhoo]

Thank you! The use-case I have is in https://github.com/jonhoo/rust-evmap, which provides concurrent read-only access to a map by keeping two copies of the map, one used by readers, and one used by the (singular) writer. Since the two maps generally hold the same keys and values, it's wasteful to duplicate all the keys and values between the maps. Instead, (my hope is) the values can be aliased so long as they are only either accessed by multiple readers, or by a single writer, at a time. Since aliasing is unsafe, evmap makes users opt into this aliasing using an unsafe ShallowCopy trait. Up until now, I've been implementing ShallowCopy for Box<T>, which makes it really easy to make cheap copies of the map for evmap — all the values are just aliased pointers, so the only memory duplication is the map itself. But, if Box can't be aliased, this won't work.

While the value could be a raw pointer, that would make the ergonomics of using evmap significantly more painful, since the caller would have to cast *mut T to &T any time they access the map, even though evmap already guarantees all the requirements for using the value as &T.

[RalfJung]

Could you give a concrete self-contained piece of code demonstrating what you mean by "aliasing a Box"? Is this representative?

[digama0]

@jonhoo I don't think there is any way to make the aliased Box<T> not UB, although you might be able to argue that it's not likely to be optimized badly given the current compiler and LLVM. My suggestion would be to use a pointer, because this correctly represents the semantics, but that leaves the ergonomic question.

I think you could make ShallowCopy have an associated type, where T::Shallow is T with any inner allocations like Box<U> replaced by *mut U, plus a deref-like method &T::Shallow -> &T that would allow you to recover the ergonomic version when accessing the read map. Both operations would be unsafe, but I don't think this triggers any insta-UB; it just leaves open the possibility of UB via data races if you start accessing the write map while the readers are using it.

[jonhoo]

@RalfJung The relevant code is this bit, which I hadn't looked at in a while and just realized is horribly not okay as it casts from const to mut:

fn shallow_copy(self: &Box<T>) -> ManuallyDrop<Box<T>> {
    ManuallyDrop::new(Box::from_raw(&**self as *const _ as *mut _))
}

But yes, your example would be a better way to illustrate the same thing. And my guess is you'll tell me that that is still casting from a const to a mut, which is Not Okay 😅

@digama0 Hmm, yes, I think your suggestion could probably work. It would still make it a little painful to actually generate the value to insert into the map, but an additional method might be able to help there (something like ShallowCopy::from_t). It gets ugly pretty quickly, but maybe that's just the way it has to be.. The other path would be to have a MyBox which internally just holds a raw pointer, which the compiler then wouldn't make the same no aliasing assumption about, but that's not very nice either.

I was definitely hoping there'd be a way for me to just use Box<T> as long as I respected the exclusiveness of &mut and never used after drop, but it sounds like that's unlikely to be okay.

[digama0]

Here's a toy version of the evmap code, enough to show the UB: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=4612588ebe044a19e4e72859b81fd443

[digama0]

Another way to look at the problem is that shallow_copy is actually a move according to the stacked borrows rules, even though the types don't make it obvious. When you call the function, it invalidates the pointer that it was given, so your oplog gets trashed and when you write the values the second time you don't have permission to read any of it, even though it is a bitwise copy of the values in the other map that you are allowed to read. Pointer provenance is weird.

[chorman0773]

Currently in lccc, the pointer field of Box is nonnull, aligned(align_of T), unique (which is the equivalent of noalias, except designed to actually be useful in optimizing rust code), as well as dereference_write(size_of T). (From these lines declaring Unique, and these lines for Box itself). This is, notably, exactly what would be emitted for &mut T, though it doesn't last for the entirity of the function, as destroying a box invalidates the pointer, so it's attribute "promises" cease to be in effect.
I can't see any Box particular optimizations that are enabled by this, basically just the standard ones that can be applied to &mut T.
I'd support making the aliasing rules for Box<T> the same as &mut T, so these optimizations can be performed there as well, but I could live without them.

[RalfJung]

@jonhoo

But yes, your example would be a better way to illustrate the same thing. And my guess is you'll tell me that that is still casting from a const to a mut, which is Not Okay sweat_smile

Basically, yeah. I am curious, if all Box here would be replaced by &'static mut, would you expect/want your code to still be okay? Basically I want to know if you think Box and &mut should differ, or if both should be weaker than Stacked Borrows makes them?

I can certainly imagine rules whereby &mut and Box only assert uniqueness when you write to them. That will carry a global (and hard to quantify) cost in terms of lost optimization potential though, in particular around moving write accesses up across unknown code. Maybe those optimizations are so hard to apply, or apply so rarely, that losing them is okay -- this is not a judgment call I can make.

We'll know a lot more about this design space once there is a concrete proposal that solves #133. Right now, all I can do is speculate.

@chorman0773

I'd support making the aliasing rules for Box the same as &mut T, so these optimizations can be performed there as well, but I could live without them.

I agree with this also just from a matter of simplicity -- not having yet another set of rules would be preferrable, I think.

[jonhoo]

@RalfJung Actually, no, I don't think I'd expect &'static mut to work the same way, because it having a &mut (to me) asserts perpetual exclusive access. I don't know exactly where that feeling comes from, but it just "feels like" it should be okay to have multiple ManuallyDrop<Box<T>> that point to the same T as long as you enforce the borrow rules for any references you take to that T. Whereas that doesn't feel true for &'static mut T, since it is already a reference that asserts an exclusive borrow. You couldn't have two &'static mut T around that both point to the same T, because, well, you're violating the &mut borrow rule directly.

I think maybe what's going on in my head is that the ManuallyDrop wrapper is what changes things. I _don't _ "feel" like it's okay to keep two Box<T> around that point to the same T; it only feels acceptable with the wrapper. In particular, I think in my head ManuallyDrop is an abdication of ownership — it implies that you don't really own the inner type, which means that you are not bound by the ownership rules for that type any more (though you are bound by the validity rules for the type).

[bjorn3]

ManuallyDrop doesn't imply that you don't really own the value to me. It merely supresses the drop implementation. In fact ManuallyDrop::into_inner is safe. If ManuallyDrop were to imply that you don't really oen the value, that method couldn't be safe as it makes you suddenly completely own the value.

[bjorn3]

Also you can safely go from ManuallyDrop<Box<T>> to &mut T, so any aliasing rules that apply to &mut T must also apply to ManuallyDrop<Box<T>>.

[chorman0773]

Well, that would fall under the "safety invariant", would it not? Though I do agree with the other point. I have a hard time seeing how ManuallyDrop<T> does not "own" a T.

…

On Fri, Nov 27, 2020 at 15:46 bjorn3 ***@***.***> wrote: Also you can safely go from ManuallyDrop<Box<T>> to &mut T, so any aliasing rules that apply to &mut T must also apply to ManuallyDrop<Box<T>>. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#258 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABGLD2ZE56YCR3D6JQCZF2LSSAF3PANCNFSM4T7NZQJA> .

[RustyYato]

In that case @jonhoo it may be better to use MaybeUninit<_> or UnsafeCell<_> instead of ManuallyDrop, because MaybeUninit does abdicate ownership (in your words) or UnsafeCell does remove the aliasing restrictions (which is the important bit here). You could have two MaybeUninit<Box<T>>/UnsafeCell<_> that "alias" each other, but you will have to use unsafe to access the values (which should be fine).

[nico-abram]

Are the aliasing rules around Box just the rules for std::ptr::Unique? (Does it make sense to make that distinction if it's still unstable?)

[chorman0773]

Are the aliasing rules around Box just the rules for std::ptr::Unique?

I don't believe Stacked Borrows special cases Unique, though I believe Unique happens to be an (unstable) implementation detail of how it special cases Box. As shown previously, my implementations treats it almost the same, adding the dereference_write attribute to Box. I would presume a standard implementation would be the same, that Unique necessarily doesn't promise you can use it to access memory, but it promises that if you can, nothing else can access the same memory.

[RalfJung]

I don't believe Stacked Borrows special cases Unique

Indeed it does not. That is an extension I hope I will be able to support eventually, and at that point I think Box will not be special-cased any more, but Unique will. Though as you said Unique does not imply dereferencable so Box probably still needs to be special-cased a bit.

@jonhoo

I think maybe what's going on in my head is that the ManuallyDrop wrapper is what changes things.

So, what about ManuallyDrop<&'static mut T> then? Your argument would mean that this does nit claim ownership the same way &mut does, but OTOH &mut already does not need dropping and one can also argue that ManuallyDrop should be a NOP on no-drop types.

[jonhoo]

Hehe, so, to be clear, I'm not really trying to say that my opinion here makes sense, just trying to explain my thinking for why I believed that this would work. Presented with the logic for why that's not the case, I agree with it, I'm just hoping that the explanation might help highlight a likely common misunderstanding that this aliasing behavior will lead to.

@bjorn3 Your point that ManuallyDrop::into_inner is safe is a very good one.

@RustyYato So, I'm hesitant to use MaybeUninit, because the type will never be uninitialized. UnsafeCell feels like a better wrapper type, but it also implies unsafe mutability (to me), whereas the Box itself isn't actually mutated. But maybe that's just a mental barrier I need to get past. On that note, would UnsafeCell<Box<T>> truly be okay to use in this setting? Won't the aliasing rules still get in the way when I take out a &mut Box<T> through the UnsafeCell?

@RalfJung ManuallyDrop<&'static mut T> to me still means that an exclusive borrow has been taken out on the T, which must requireq that value is not aliased. Whereas for ManuallyDrop<Box<T>>, no references exist to the T, so I can't be violating the borrowing rules. Again, my understanding here is likely flawed and leading me astray; I'm just trying to describe why I think I was surprised by this behavior.

[jonhoo]

A related question: do the same aliasing rules then apply to other owner heap types, like String and Vec<T>? After this discussion, I feel like the answer is likely yes..

[jonhoo]

I went down a deep deep rabbit hole trying to find a way to avoid violating the aliasing requirement for Box while still providing somewhat ergonomic (and sound) aliasing, and the (incomplete) result is the plan I've sketched in this comment: jonhoo/left-right#81 (comment). It may be interesting to some of you, and I would certainly love to hear your thoughts. Sorry in advance for the length, but the issues are complex :)

[RustyYato]

So, I'm hesitant to use MaybeUninit, because the type will never be uninitialized.

That's fair, however I see it more as "the normal validity peoperties don't necessarily apply", either because it's uninitialized or because you've done something special, like ShallowCopy

UnsafeCell feels like a better wrapper type, but it also implies unsafe mutability (to me), whereas the Box itself isn't actually mutated. But maybe that's just a mental barrier I need to get past. On that note, would UnsafeCell<Box<T>> truly be okay to use in this setting?

Don't you have unsafe mutability? You're sharing a Box that could be overwritten using a WriteGaurd. I might be wrong here, just another perspective. Personally I think that MaybeUninit is the better fit here

Won't the aliasing rules still get in the way when I take out a &mut Box<T> through the UnsafeCell?

Yes, but that's normal Rust, the issue right now is tou have UB even if you don't touch the box. Using UnsafeCell means that the aliasing rules are only enforced on use, not while the Box is just sitting there.

A related question: do the same aliasing rules then apply to other owner heap types, like String and Vec? After this discussion, I feel like the answer is likely yes..

I'm fairly certain that Vec uses Unique under the hood, and String uses Vec, so yes, both are affected.

[danielhenrymantilla]

@RustyYato how would you expect UnsafeCell to solve the aliasing guarantees? Both UnsafeCell<Box<T>> (owned), and Box<UnsafeCell<T>> express unique access to the UnsafeCell, and thus, to its contents (UnsafeCell allows writes through shared accesses to be non-UB, but it doesn't interact with already exclusive accesses : "UnsafeCell is magic w.r.t. &, not &mut").

@jonhoo MaybeUninit<_> is the de facto type used to erase / nullify the validity invariants of a type (moving them to be safety invariants), so if one wrapper should be able to remove this non-aliasing guarantee, it should be this one (that being said, Stacked Borrows / (no)-aliasing validity invariants sometimes behave a bit differently from the other validity invariants, so I'd like to hear @RalfJung's stance on this).

• Granted, I could see ManuallyDrop also working to remove some validity invariants (those that cannot be seen bitwise; e.g., ManuallyDrop<Box<T>> may be a dangling pointer), but since that one is a bit more subtle than MaybeUninit, when in doubt, using the latter is a way to err on the side of caution.

---

A related question: do the same aliasing rules then apply to other owner heap types, like String and Vec? After this discussion, I feel like the answer is likely yes..

When the length is 0, the inner pointers can dangle, so it's a bit less clearcut. That being said, it's also better to be careful about these things too. For instance, since a CString cannot be empty, that one definitely carries non-aliasing rules, c.f., rust-lang/rust#62553

• From the example in that issue,

  fn into_inner(self: CString) -> Box<[u8]> {
      unsafe {
          let ret = <*const _>::read(&self.inner);
          ::core::mem::forget(self);
          ret
      }
  }

  triggers Miri and is very likely UB; whereas:

  fn into_inner(self: CString) -> Box<[u8]> {
      let this = ::core::mem::ManuallyDrop::new(self);
      unsafe {
          <*const _>::read(&this.inner)
      }
  }

  is fine; And the one interesting to "re-study", is that the following should, imho, be fine too:

  fn into_inner(self: CString) -> Box<[u8]> {
      let this = ::core::mem::ManuallyDrop::new(self);
      unsafe {
          let ret = <*const _>::read(&this.inner);
          drop(this);
          ret
      }
  }

  • (with MaybeUninit it is definitely fine)

[RustyYato]

I was thinking that UnsafeCell would remove the problematic noalias attribute, but that was dubious, which is why I preferred MaybeUninit

[Diggsey]

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

Box<T> would be a simple wrapper around Unique<T> and so would have the same invariants. Instead of trying to alias boxes, code should wrap Shared<T> (or in the absence of such a type today, use raw pointers).

[chorman0773]

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

Unique is (unstable) in core. It can't deallocate anything, because it doesn't know how to allocate or deallocate.

Also, I'm curious how a Shared type could be defined that is permitted to deallocate on drop while being shared?

[jonhoo]

Yes, I think you're all right that UnsafeCell would not suffice to allow aliasing. I opted instead to try out the MaybeUninit route, and it seems promising so far. Of course, this could be just as unsound as the previous one without me realizing, but I think I'm now operating from a position of more understanding. You can take a look at what I came up with so far in https://github.com/jonhoo/rust-evmap/blob/4e83da000cfee94810eb790f25c1dc159def1b12/evmap/src/aliasing.rs. It boils down to copying a MaybeUninit<T> using std::ptr::read, and then being careful about dropping and when to hand out &T. See also jonhoo/left-right#83 for details.

I still feel like MaybeUninit is "overkill" for this case, since the only invariant I really want to erase is aliasing, but maybe it's the only choice at the moment.

[RalfJung]

@jonhoo

ManuallyDrop<&'static mut T> to me still means that an exclusive borrow has been taken out on the T, which must requireq that value is not aliased. Whereas for ManuallyDrop<Box>, no references exist to the T, so I can't be violating the borrowing rules. Again, my understanding here is likely flawed and leading me astray; I'm just trying to describe why I think I was surprised by this behavior.

Why you think that is exactly what I am trying to figure out by probing your intuition, so thanks for the response. :)

Unfortunately, I do not understand the reasoning though. What do you mean by "an exclusive borrow has been taken out on the T"? You seem to say that a mutable reference still exists in some sense, even when it is inside ManuallyDrop -- but at the same time you consider the Box wrapped in a ManuallyDrop to not really exist. Isn't that inconsistent?

@danielhenrymantilla

MaybeUninit<_> is the de facto type used to erase / nullify the validity invariants of a type (moving them to be safety invariants), so if one wrapper should be able to remove this non-aliasing guarantee, it should be this one (that being said, Stacked Borrows / (no)-aliasing validity invariants sometimes behave a bit differently from the other validity invariants, so I'd like to hear @RalfJung's stance on this).

I'd say MaybeUninit definitely erases any such requirement (and I hope we compile this correctly^^ there should be no noalias or dereferencable). But of course this is a heavy hammer, and one could imagine something that erases just the alias requirements, not more than that. In some sense that type is NonNull<T>. (Well, Box has to be aligned, not just non-null, but whatever.)

Granted, I could see ManuallyDrop also working to remove some validity invariants (those that cannot be seen bitwise; e.g., ManuallyDrop<Box> may be a dangling pointer), but since that one is a bit more subtle than MaybeUninit, when in doubt, using the latter is a way to err on the side of caution.

Ah, good call. I don't think we have a clear consensus yet on what ManuallyDrop does with aliasing. I don't even have a clear idea for what the trade-offs are here.

[elichai]

(Well, Box has to be aligned, not just non-null, but whatever.)

Am I smelling a AlignedNonNull<T>? ;)

More seriously, every time I read conversations about aliasing rules it sounds like we all want both fine grained control and a lot of optimizations, leading us to a lot of different types: &T / &mut T / Box<T> MaybeUninit<T>/NonNull<T>/ raw pointers / Unique<T> / UnsafeCell<T>(this is quite different then the rest though) and even new ways to obtain pointers (&raw T/&raw mut T)

[jonhoo]

@RalfJung

Why you think that is exactly what I am trying to figure out by probing your intuition, so thanks for the response. :)

❤️

Unfortunately, I do not understand the reasoning though. What do you mean by "an exclusive borrow has been taken out on the T"? You seem to say that a mutable reference still exists in some sense, even when it is inside ManuallyDrop -- but at the same time you consider the Box wrapped in a ManuallyDrop to not really exist. Isn't that inconsistent?

Yes, I suppose it is. 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.

But of course this is a heavy hammer, and one could imagine something that erases just the alias requirements, not more than that. In some sense that type is NonNull<T>. (Well, Box has to be aligned, not just non-null, but whatever.)

I'm hesitant to have a wrapper just for the pointer case. What's "nice" about MaybeUninit is that I can stick a Vec<T> in there just as easily as a Box<T>, and it still "nullifies" the aliasing rules for the inner type for me (at least that's my understanding from this discussion). The same isn't true for NonNull<T> since it is "just" one pointer.

Ah, good call. I don't think we have a clear consensus yet on what ManuallyDrop does with aliasing. I don't even have a clear idea for what the trade-offs are here.

I feel like ManuallyDrop should allow aliasing, but that's not okay since ManuallyDrop already has a safe API to access the inner type. Maybe a UnsafeManuallyDrop :p

[RalfJung]

I think maybe this boils down to "I don't feel like keeping two Box 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.

Okay, so you do not expect a symmetry between Box and &mut then. That is an interesting data-point, since I pretty much treated this as an axiom so far.

I'm hesitant to have a wrapper just for the pointer case. What's "nice" about MaybeUninit is that I can stick a Vec in there just as easily as a Box, and it still "nullifies" the aliasing rules for the inner type for me (at least that's my understanding from this discussion). The same isn't true for NonNull since it is "just" one pointer.

Vec is unlikely to have aliasing rules "if you don't use it", given that the size may be zero so there might not even be any memory there that aliasing could be applied to. But this is all idle speculation until we have a concrete proposal for Unique.

I feel like ManuallyDrop should allow aliasing, but that's not okay since ManuallyDrop already has a safe API to access the inner type. Maybe a UnsafeManuallyDrop :p

It could still be the case that the "validity invariant" of ManuallyDrop allows aliasing, but the "safety invariant" does not. But maybe that's a bit too tricky.

[chorman0773]

Vec is unlikely to have aliasing rules "if you don't use it", given that the size may be zero so there might not even be any memory there that aliasing could be applied to

I was thinking about giving Vec<T> the same aliasing rules as &mut [T]. This would work, as &mut [T], for size 0, has unique access to 0 bytes. I was actually thinking about opening an issue for that. More of a "would be nice" thing than something I definitely want to exploit, though. It would also depend on this issue, for sure.

[danielhenrymantilla]

It could still be the case that the "validity invariant" of ManuallyDrop allows aliasing, but the "safety invariant" does not. But maybe that's a bit too tricky.

FWIW, that's what I find most consistent, albeit maybe a bit subtle. I guess a good way to "show" what is subtle or tricky is to find an unintuitive code snippet, or a pair of code snippets whereby one is UB and the other is not, despise "intuition" telling they are equivalent (I like using implicit drop vs. explicit drop() for that).

It turns out I posted such a pair of snippets in a previous comment, but such snippets go in the other direction: that ManuallyDrops invariants being validity ones instead of safety ones are surprising:

Having:

struct CString {
    inner: Box<[u8]>, /* never empty */
}

then:

fn into_inner(self: CString) -> Box<[u8]> {
    let this = ::core::mem::ManuallyDrop::new(self);
    unsafe {
        <*const _>::read(&this.inner)
    }
}

is fine;

And I personally feel like the following should be fine too:

fn into_inner(self: CString) -> Box<[u8]> {
    let this = ::core::mem::ManuallyDrop::new(self);
    unsafe {
        let ret = <*const _>::read(&this.inner);
        drop(this);
        ret
    }
}

However, IIUC, that drop(this) would be UB, according to SB at least, if ManuallyDrop<CString> i.e., ManuallyDrop<Box<NonEmptySlice<u8>>>, was considered to have aliasing as part of its validity invariants.

Indeed, that would assert that the this pointer is not aliased, then invalidating any pointers derived ("reborrowed") from it, such as ret, making the returned ret be UB.

[digama0]

should the return types of those functions be *const [u8]? Because otherwise they look pretty trivial.

[RalfJung]

I was thinking about giving Vec the same aliasing rules as &mut [T]

The key difference is that &mut [T] is a primitive type so the language / Abstract Machine / Miri knows how to determine its length. The same is not true for Vec, and I do not think we want to change that.

However, IIUC, that drop(this) would be UB, according to SB at least, if ManuallyDrop i.e., ManuallyDrop<Box<NonEmptySlice>>, was considered to have aliasing as part of its validity invariants.

If aliasing requirements propagate through ManuallyDrop, that is true. As implemented in Miri right now, aliasing is not considered to propagate through any newtypes. However, that might be incompatible with what rustc is doing, where noalias/dereferencable is emitted for newtyped references/boxes. This is a knob we can turn either way, and even if aliasing requirements propagate through newtypes in general, ManuallyDrop could be made an exception.

[RalfJung]

I just realized I opened #326 as a duplicate of this... let's keep the newer one open since it probably has more up-to-date information.

Also, on this thing I wrote in my last post here almost 3 years ago...

This is a knob we can turn either way, and even if aliasing requirements propagate through newtypes in general, ManuallyDrop could be made an exception.

That's exactly what rust-lang/rfcs#3336 proposes. :)