Stacked Borrows' interior mutability is per-location: enum discriminants can surprisingly change

[RalfJung]

Stacked Borrows does per-location tracking of whether something has interior mutability. This means if the discriminant is stored on the same location as an UnsafeCell, it can surprisingly change:

/// Sets `x` to `None`.
fn evil<T>(x: &Option<Cell<&T>>) {
    assert_eq!(
        mem::size_of_val(x), mem::size_of_val(x.as_ref().unwrap()),
        "layout optimization did not kick in?",
    );
    unsafe { *(x as *const _ as *mut usize) = 0; }
}

fn main() {
    let my = Some(Cell::new(&0));
    evil(&my);
    dbg!(my);
}

This passes in Miri and prints "None".

Note that right now, this would pass in Miri even with no enum layout optimizations as I simplified the handling of interior mutability (see rust-lang/miri#931). The old, more precise handling was a total mess and basically impossible to reason about. But even the most precise handling I can imagine would still allow the code above.

Cc @nikomatsakis @eddyb

[nikomatsakis]

@RalfJung I've been wondering about this general thing ever since you told me that that unsafe-cell was probably going to become "infectious" up to the enclosing enum.

Clearly there is some kind of "gap" between the patterns that the borrow checker enforces and the actions that stacked borrows allows here. I mean, this isn't surprising, it will always be the case, but this feels a bit different than the sorts of "overapproximations" I expected.

I'm not too worried about it, but I could see it leading to some surprising results in the compiler. As an example, imagine that we have x: Option<(u32, Cell<u32>)>. What this seems to imply is that the path x.as<Some>.0 is something which could be changed by raw pointer writes, is that correct?

Anyway, your example here feels like it's in the same vein. Our optimizations are relying on the UnsafeCell<&T> type only ever having a valid &T stored into it, but you're violating that expectation. If you think of the discriminant as a kind of "pseudo-field" (that takes 0 bits in this case), it seems analogous to the case of (Discriminant, Cell<&T>), where you are writing to the Discriminant field "unexpectedly", right?

I think perhaps we could live with this, but I also sense that it will be the cause of compiler bugs, because we'll want to be reasoning about paths and overlap (much as, e.g., the borrow checker does) and we'll have to be careful.

[Diggsey]

I don't understand what this has to do with UnsafeCell? I tried this example locally with Miri and it also passed:

use std::num::NonZeroUsize;

fn test(v: &mut NonZeroUsize) {
    let p = (v as *mut NonZeroUsize) as *mut usize;
    unsafe { *p = 0; }
}

fn main() {
    let mut opt = NonZeroUsize::new(1);

    println!("{:?}", opt);
    test(opt.as_mut().unwrap());
    println!("{:?}", opt);
}

I would not expect unsafe code to be allowed to set opt to None in this case either.

Maybe I'm going off on a tangent here, but is the intent for unsafe code to be allowed to "temporarily" violate the requirements of the type if it has exclusive access and "fixes it" before returning?

I could see why that would be specific to UnsafeCell because then other code (or even other threads) could still have references to the outer Option and see the invalid state. If that's desirable, then maybe UnsafeCell should be treated as never having any niches for layout optimisation.

[RalfJung]

I don't understand what this has to do with UnsafeCell? I tried this example locally with Miri and it also passed:

This is a distinct but related issue: #84.

[Diggsey]

Could you clarify what makes them distinct?

Does this example capture the distinction?

fn should_be_fine(v: &mut NonZeroUsize) {
    let p = (v as *mut NonZeroUsize) as *mut usize;
    unsafe { *p = 0; }
    unsafe { *p = 1; }
}

fn should_be_ub(v: &UnsafeCell<NonZeroUsize>) {
    let p = v.get() as *mut usize;
    unsafe { *p = 0; }
    unsafe { *p = 1; }
}

ie. the first is valid because the violation is not visible outside the function, whereas the second is invalid because another thread could be observing an Option containing the UnsafeCell.

[gnzlbg]

@Diggsey the difference is shown here (playground):

// this enum has layout: (discriminant: i32, MaybeUninit<UnsafeCell<i32>>)
// the discriminant field is Freeze, but the UnsafeCell is !Freeze
enum E {
    A(UnsafeCell<i32>),
    B, 
}

// E::B does not contain any !Freeze fields, and 
// can be put in read-only memory
// => it is illegal to try to modify the memory of this static
static B: E = E::B;

// miri accepts this code:
unsafe { *(&B as *const _ as *mut i32) = 0; }

Note that the layout of the enum is (discriminant, data: MaybeUninit<UnsafeCell>). If the enum is put in mutable storage (e.g. a let mut), then one can take a pointer to the discriminant or the data, and modify those. However, if the enum is put in read-only store (e.g. a let, a static, etc.), one can modify the data (it's !Freeze), but the discriminant is read only (the discriminant is Freeze - it is not in an UnsafeCell).

This is subtly different from #84, where the enum discriminant is put inside the data field via an enum layout optimization. In #84, depending on whether the data-field can be modified or not, the discriminant can be modified through it or not. Here, the discriminant can only be modified if it is put in mut memory. However, if the enum contains a data field that's UnsafeCell, miri currently allows modifying the whole enum layout on read only memory (EDIT: that is, if the enum contains an UnsafeCell, the whole enum is considered as being inside a big UnsafeCell).

In particular, if you actually were to replace the enum with the (i32, MaybeUninit<UnsafeCell>) aggregate (playground), then miri properly errors with:

error[E0080]: Miri evaluation error: 
    no item granting write access to tag <untagged> found in borrow stack

which says that you don't have write access to modify the discriminant field. I'd expect the same error to have triggered for the enum E case.

[Diggsey]

Thanks, that explains it more clearly. The stacked borrows blog describes a "location" as a memory location (a byte address essentially) so I found the title and description confusing. It seems like the issue is that interior mutability is tracked per-value rather than per-location, and that's what leads to the problem?

Otherwise (without enum layout optimisation) the discriminant would be at a different location than the unsafe cell, and there would be no issue.

[RalfJung]

It seems like the issue is that interior mutability is tracked per-value rather than per-location, and that's what leads to the problem?

No idea what you mean by "per-value" here, but Stacked Borrows is definitely working "per-location" as in memory location.

Otherwise (without enum layout optimisation) the discriminant would be at a different location than the unsafe cell, and there would be no issue.

There is a separate issue where when seeing an instance of type Option<Cell<i32>>, even though there are no layout optimizations, we would have to read memory to figure out if this is in the None or Some branch. Doing memory accesses as part of the "administrative work" that Stacked Borrows does is extremely hard to reason about, since either those accesses themselves are subject to Stacked Borrows restrictions (leading to a crazy kind of recursion) or they are not (meaning they are the only accesses that ignore Stacked Borrows, which at the very least breaks all of our formal proofs of optimizations and might also actually break these optimizations).

@nikomatsakis

As an example, imagine that we have x: Option<(u32, Cell)>. What this seems to imply is that the path x.as.0 is something which could be changed by raw pointer writes, is that correct?

Yes.

And TBH, I'd really like to also do this for simpler types like (u32, Cell<u32>). We might have to move to a more complicated structure than a stack, and if we do the fact that the same pointer can have different permissions on different locations (like an &(u32, Cell<u32>) being a read-only ptr for the first 4 bytes but a read-write ptr for the last 4 bytes) makes that insanely complicated. I am worried that the resulting model will be more complicated than either unsafe code authors or compiler authors can reason about properly.

Anyway, your example here feels like it's in the same vein.

I am confused, this is basically the same example, how is it just "in the same vein"?

[nikomatsakis]

@RalfJung

I am confused, this is basically the same example, how is it just "in the same vein"?

Maybe it's the same example. I think the difference I was referring to is just that, in your example, modifying the value also changed the (implicit) discriminant, and hence switched from Some to None. In my example, the data inside the Option is a tuple, so modifying the first half of the tuple doesn't change from Some to None but just changes the value itself.

And TBH, I'd really like to also do this for simpler types like (u32, Cell<u32>)

I somewhat lean this way as well. The loss of precision feels worth it in exchange for a relatively simple rule regarding "how infectious" an UnsafeCell is. It's pretty hard for me to predict, though, how this might affect optimizations and the like.

[RalfJung]

Some recent discussion on Zulip led to the idea that we can view #84 and this issue as one and the same if we make it about "pointers where writing some values to them is okay but writing other values is immediate UB". That is not the only way either of these issues could be resolved, but if we had such pointers than for both #84 and this issue clearly we'd have 'maximal UB'.

That said, for mutable references we actually might want to allow "temporarily" violating the invariant, as long as everything is fine when the reference expires. For mutation of shared data via interior mutability, that is not an option.