What about: invalid not-used-again values? Is "validity on typed copy" enough?

[RalfJung]

(Taken from #69 (comment).)

How do we feel about this code -- UB or not?

fn main() { unsafe {
    let mut x = Some(&0); 
    match x {
        Some(ref mut b) => {
            let u = b as *mut &i32 as *mut usize;
            // Just writing into a *mut u8
            *u = 0;
        }
        None => panic!(),
    }
    assert!(x.is_some());
} }

This "magically" changes the discriminant. OTOH, it is very similar to

fn main() { unsafe {
    let mut x = Some(&0); 
    (&mut x as *mut _ as *mut usize) = 0;
    assert!(x.is_some());
} }

which is definitely allowed (it makes assumptions about layout, but we do guarantee layout of Option<&T>.

Other examples:

fn main() { unsafe {
  let mut x = true;
  let xptr = &mut x as *mut bool as *mut u8;
  *xptr = 2;
} }

fn main() { unsafe {
    let mut x = Some(true); 
    match x {
        Some(ref mut b) => {
            let u = b as *mut bool as *mut u8;
            // Just writing into a *mut u8
            *u = 2;
        }
        None => panic!(),
    }
    assert!(x.is_some());
} }

#![feature(rustc_attrs)]

#[rustc_layout_scalar_valid_range_start(1)]
#[repr(transparent)]
pub(crate) struct NonZero(u32);

fn main() { unsafe {
    let mut x = Some(NonZero(1)); 
    match x {
        Some(NonZero(ref mut c)) => {
            // Just writing 0 into an &mut u32
            *c = 0;
        }
        None => panic!(),
    }
    assert!(x.is_some());
} }

[hanna-kruppe]

To clarify, the last example doesn't need the unsafe {}, right? It's not "safe code" (you can modify it to be unquestionably UB by omitting the Option and reading x after the end) but that's due to the use of #[rustc_layout_scalar_valid_range_start], not due to any individual operation in main.

[RalfJung]

@rkruppe It needs the unsafe, we have fixed unsafety checks in rustc to require an unsafe block to create a reference into a rustc_layout_scalar_valid_range_start struct.

[RalfJung]

See #189 for me describing this problem again. ;)

An interesting observation: the following code is certainly fine; FFI code does something like this all the time when using Option<&T> on the interface:

fn main() {
    let mut x = Some(NonZeroU32::new(1).unwrap());
    let xref = &mut x as *mut _ as *mut u32;
    unsafe { *xref = 0 };
    println!("{:?}", x);
}

Operationally, this is basically the same as the problematic

use std::num::NonZeroU32;

fn main() {
    let mut x = Some(NonZeroU32::new(1).unwrap());
    let xref = match x {
        Some(ref mut c) => c as *mut NonZeroU32 as *mut u32,
        None => panic!(),
    };
    unsafe { *xref = 0 }; // writing 0 into a `*mut u32`
    println!("{:?}", x);
}

To distinguish the two, xref would need to have some kind of "provenance" remembering that it was created from a pointer to NonZeroU32, not a pointer to u32.

[CAD97]

Just some musings I came up with:

When moving a !Copy type, invalidating the old name is obviously correct.

Example:

let a: Thing1 = default();
let aref = &a as *const _;
let b: Thing2 = transmute(a);
// `aref` is invalid _even if_ we guaranteed `b` were in the same physical location
// as a logical move has occurred

So maybe the last copy of a Copy value could be a move as well?

Example:

let mut x = Some(&0);
match x {
    Some(ref mut b) => {
        let u = b as *mut bool as *mut u8;
        // `b` is no longer required to be valid, as it has been "moved"
        // Just writing into a *mut u8
        *u = 2;
    }
    None => panic!(),
}
dbg!(x);

On the other hand, the origin provenance makes sense as well. Using this example for clarity:

let mut x = Some(NonZeroU32::new(1).unwrap());
let xref = match x {
    Some(ref mut c) => c as *mut NonZeroU32 as *mut u32,
    None => panic!(),
};
unsafe { *xref = 0 }; // writing 0 into a `*mut u32`
dbg!(x);

It "makes sense" that the c binding only "owns" the right to write to the NonZeroU32.

Naively, it feels like this should behave the same as

let mut x = (1u32, 0u32);
let x1ref = &mut x.1 as *mut u32;
let xref = xref.sub(1) as *mut (u32, u32);
*xref = (0, 0);
dbg!(x);

Specifically, it's taking a reference into the "interior" of an allocated object and "upgrading" it to a pointer to the full object to write the full object. It just so happens that the physical pointers are the same.

My intuition here is suggesting something like guaranteed niche optimizations shouldn't matter for what operations you are allowed do with a pointer, just how you're able to accomplish said operations, as well as what memory reinterpretation is allowed. I don't know how practical that is, but it seems somewhat logical. (e.g. <*const Option<NonZeroU32>>::cast::<u32> is valid because of the guaranteed niche optimization, but <*const NonZeroU32>::cast::<Option<NonZeroU32>> is not valid, even if said pointer lives in that type (unless it was derived from a wider pointer).)

[RalfJung]

Specifically, it's taking a reference into the "interior" of an allocated object and "upgrading" it to a pointer to the full object to write the full object. It just so happens that the physical pointers are the same.

Yes, that is a way to look at it. Your "upgrading" example would be rejected by Stacked Borrows because that pointer is not allowed to write to the "outer" memory.
On the other hand, physical overlap is the thing that matters for aliasing, which is what Stacked Borrows is all about.
And note that there is nothing in the validity machinery that has any problem with deriving "outer" pointers from "inner" pointers". Only Stacked Borrows cares.

[RalfJung]

(Moved to new issue)

[thomcc]

I asked about this on zulip, and was told to write my use case for why I'm doing it here. Here's more words about it than you asked for:

I'm trying to write a highly tuned string type, using as many performance tricks as I can manage without hurting the average case. This includes (among other tricks) zero-cost conversion from &'static str, using atomic refcounts + clone-on-write for large strings, and of course, why I'm here, the classic small-string-optimization/inline-string-optimization well known from its use in C++ stdlibs.

While I have a bunch of representations, all of them except SSO are more-or-less representationally equivalent (keeps most branches out of the non-small path). When in the SSO case though, it is essentially [u8; size_of::<String>()] where the last byte is used for length and tags.

It's very important to me* that I not increase the size relative to std::string::String, and that includes for representing things like Option<String> or Result<String, E>.

This means I need the NonNull byte pointer, and can't use this as a union, even though conceptually it's used as one. This all means it just looks like a pretty normal string:

#[repr(C)]
pub struct String {
    data: NonNull<u8>,
    len: usize,
    cap_flags: CapFlags, // just a usize**
}

But it's a bit of a lie -- I just interpret &mut self as a &mut [u8; N] when writing as a small string, and &self as a &[u8; N] when reading as one. The only true parts about it when we're small are that NonNull stays zeroed, and that CapFlags

Anyway, The issue is this: naively, the push_byte code (e.g. the part of the code handling when an ascii character is the arg to push for the small string case ended up needing too many checks to avoid writing to NonNull<u8> -- essentially you want to ask a subset of (on 64 bit) 'are our first 7 bytes nul' && 'is the incoming c == '\0'' && 'will it get written to the 8th byte'. this is hot code, so more checks, even if they're correctly predicted, are bad.***

I tried a bit, and am probably going to try harder****, but ultimately ended up just performing the write unconditionally, and testing if afterwards our first field when read as a usize is zero (if it is quickly writing a non-zero to that byte and calling a #[cold] function).

This is a branch in a relatively hot path that I'm annoyed with (it's easily predictable but oh my god it seems like such a ridiculous edge case), but it ended up with better codegen than the alternatives I've tried so far. That said I haven't really finished tuning things so it's very possible that sort of write/read pattern is ultimately problematic in other ways...

Anyway that was extremely rambling, but probably at least explained enough to get a good idea of the picture.

---

* Mostly because I suspect it matters a lot in practice, even though llvm makes the cost of memcpys often hard to measure. I doubt increasing memcpy traffic would be favorable for very much rust code...

** CapFlags is a transparent wrapper for a usize that just holds both the capacity and two flag bits, while managing endian-specific stuff to keep them in the right place so that reading flags from it and from the final byte of the string both work.

*** The most promising is probably the c == '\0' test, which the compiler should be able to do away with when c is constant (which appears to be the common case for arguments to push much of the time), and should be rare enough. Unfortunately, the only place this is convenient to punt it to is the non-ascii push case (which is less hot, but very far from cold), and doing so isn't exactly ideal...

**** since this makes me uncomfortable -- and rightfully so, wasn't properly accounting for the case where a macro that can expand to contain profiling data could possibly panic if the right --cfg was passed...

(alright thats it i'm leaving before i think to give one of my footnotes a footnote)

[RalfJung]

@digama0 raised concerns about this current "feature" of the semantics proposed so far. They also say

I won't elaborate on it more in this thread, but my proposal could enforce this property without requiring a typed memory.

I assume this is using the same notion of "typed memory" as I do, i.e., a memory that contains types in its state. I am curious how you want to do that -- the proposal so far says

The property we would like to establish is that when the lifetime of the &mut b ends, b is again valid at type bool, but in an operational model we can't just say that, so instead, when &mut b as *mut bool is executed, we push on the borrow stack of b a record that, when popped, reasserts the bool invariant at this byte.

So this sounds to me like bool is stored in the borrow stack, which is part of memory. So I would call this "typed memory".

[digama0]

The memory doesn't contain bool on the borrow stack, it contains one of a small set of predicates on bytes representing byte sized slices of a validity property. One of those predicates is "this byte is 0 or 1", so in that sense yes it's put bool on the stack, but that doesn't mean that you have some recursive type going into the memory or a chicken and egg problem defining what types and memory are.

[RalfJung]

predicates on bytes

That's what a type is, though... so even if you managed to "hack" around my particular definition of "typed memory", this still shares all the same problems of having a ton of shadow state that programmers (and tools like Miri) need to keep track of. You just have semantic types (i.e., predicates on values) in your memory instead of the usual syntactic types.

I do agree that something like this could work, and indeed it is the most elegant working proposal I have seen so far. :-)
But I am worried that it still adds a lot of complexity without enough benefit.

recursive type going into the memory or a chicken and egg problem defining what types and memory are.

What makes typed memory hard to use in C/C++ is not the "chicken and egg" problem of formally defining it; indeed there is no problem at all there, e.g. the original CompCert memory model was typed -- but they moved away from typed memory since then.

[digama0]

I think the term "typed memory" is not doing us favors here. To me, that implies that a value has a type in memory from now until it is deallocated, and any access to that memory at another type is UB. In my proposal, the type is only asserted on reads, on writes, and when a mut borrow ends (also thought of as a write). In the intervening period unsafe code can write whatever it likes.

We are already carrying quite a bit of shadow state in memory, including in particular the tags of unique references that have been converted to raw pointers. So the necessary information is already present; it might be possible to just look up the type of the reference with that tag and simulate a write to it (using the type it was declared as), so that would avoid any type state altogether. The point is really that the mutable borrow should not be able to be dropped while bad memory is in it, and a simulated write has exactly the right effect. The only tricky thing is the timing of the write but stacked borrows handles that well enough using the borrow stack.

[chorman0773]

any access to that memory at another type is UB

This is actually not the case, typed memory does not imply strict aliasing (C and C++ have both, but they are constructed through different parts of the standards). Other than that, I do agreee. Rust shouldn't adopt a model that imposes typed memory, but I don't think asserting that memory written through a mutable reference (and derivatives of that reference) as being valid at drop is fair. In the absense of #77 requiring it (which bring the UB to wherever the mutable reference becomes active again, through SB or another mechanism), this is a fair substitute. Ideally, a write to the inner field of an Option<T> should not be able affect the entire Option. This means that when T is niche-optimizing, it should be impossible to correctly (where correct shall mean the absense of undefined behaviour) write an invalid value to the inner field.

[RalfJung]

I think the term "typed memory" is not doing us favors here. To me, that implies that a value has a type in memory from now until it is deallocated, and any access to that memory at another type is UB. In my proposal, the type is only asserted on reads, on writes, and when a mut borrow ends (also thought of as a write). In the intervening period unsafe code can write whatever it likes.

If it is asserted on writes, then how can it write whatever it likes? All writes need to be of the right type. If that's not "typed memory", I do not know what is.

We are already carrying quite a bit of shadow state in memory, including in particular the tags of unique references that have been converted to raw pointers. So the necessary information is already present;

Indeed the aliasing model requires all these tags as shadow state. But you are proposing to add even more shadow state. So far the shadow state is completely type-agnostic (except for UnsafeCell), which is very convenient when doing low-level stuff by casting pointers back and forth.

I think the shadow state should be the absolute minimum that we need for good optimizations.

it might be possible to just look up the type of the reference with that tag and simulate a write to it (using the type it was declared as)

Ah, what a hack. ;) This makes a couple of assumptions though about only one such reference existing or all such references having the same type, which is not necessarily true.

@chorman0773

I don't think asserting that memory written through a mutable reference (and derivatives of that reference) as being valid at drop is fair.

Do you mean "I do think"?

Ideally, a write to the inner field of an Option should not be able affect the entire Option. This means that when T is niche-optimizing, it should be impossible to correctly (where correct shall mean the absense of undefined behaviour) write an invalid value to the inner field.

But why? I don't agree, and you just stated a preference without giving arguments. There need to be good arguments for every extra bit of UB, usually in the form of optimizations that outweigh the cost of the extra proof obligation and mental burden for programmers.

[RalfJung]

it should be impossible to correctly (where correct shall mean the absense of undefined behaviour) write an invalid value to the inner field.

That is not even the case with the proposal on the table, is it? Validity is checked when the borrow item is removed from the stack; in the mean time other code could break and then restore the invariant and that would be allowed.

[chorman0773]

Validity is checked when the borrow item is removed from the stack; in the mean time other code could break and then restore the invariant and that would be allowed.

To the point where it can affect surrounding code, I don't believe this can apply. If we assert validity whenever a &mut is dropped from the borrow stack, you can't possibly observe the field itself, except through the &mut in a broken-invariant state, and therefore you can't observe the effects on the Option.

As for why, an Option<T> is fundamentally equivalent to the C

union Option{
    struct{bool engaged; T value;} Some;
    struct{bool engaged;} None;
};

not-withstanding layout rules. C says you can't reach the engaged field or the Outer Struct from the value field, and SB says the same AFAIK (I believe it also says you can't reach the outer struct from the inner engaged, but C would permit that). I think this should be a valid assertion even when T has a niche, or is a dependant type that may have a niche. By protecting validity at &mut drop, we can maintain the assertion for these types. This increases the potential optimizations for dependant (not-yet monomorphized) types, which reduces the number of times optimizations need to be performed (I know rustc can perform MIR optimizations, though idk if it performs optimizations in dependant contexts)

[RalfJung]

To the point where it can affect surrounding code, I don't believe this can apply. If we assert validity whenever a &mut is dropped from the borrow stack, you can't possibly observe the field itself, except through the &mut in a broken-invariant state, and therefore you can't observe the effects on the Option.

Okay, so you would be fine with temporarily violating the invariant. That would also still permit @thomcc's usecase.

FWIW, I think the easiest way to implement this in Miri would be to add type information somewhere here. That makes item bigger, which is a problem as we have a lot of those, and it adds the 'tcx lifetime everywhere, but I think it should work. And similarly, in a formal mathematical semantics I'd probably add a syntactic type rather than a "predicate on values", that will be easier to handle -- it maintains countability and decidable equality and all these things you want to have for your machine state.

not-withstanding layout rules. C says you can't reach the engaged field or the Outer Struct from the value field, and SB says the same AFAIK (I believe it also says you can't reach the outer struct from the inner engaged, but C would permit that).

Essentially, yes, though the details differ greatly between Stacked Borrows and C. Also note that in Stacked Borrows all of this is only true for references; with raw pointers, there are no such restrictions. (Mixing references and raw ptrs is more complicated, no need to get into this now.)

I think this should be a valid assertion even when T has a niche, or is a dependant type that may have a niche. By protecting validity at &mut drop, we can maintain the assertion for these types. This increases the potential optimizations for dependant (not-yet monomorphized) types, which reduces the number of times optimizations need to be performed (I know rustc can perform MIR optimizations, though idk if it performs optimizations in dependant contexts)

I would be curious for a concrete example of such an optimization. (Also I think what you call "dependent" is what is usually called "generic" in Rust; dependent types are something else. Just trying to make sure I correctly understand the words you are using.)

It seems like you want to provide the fiction that the embedded niche is a separate field in a disjoint location. First of all let me note that this fiction cannot be entirely held up -- when concurrency is involved, whether or not two things overlap in memory matters a lot, so UnsafeCell has to disable niches or else Option<UnsafeCell<bool>> would go horribly wrong. Your proposal does not change this.

So the question is one of how close niches can be to behave like "normal fields"; they will always have to be treated separately. Also note that in MIR, the niche is not just a normal field -- it can only be interacted with through special MIR operations (Statement::SetDiscriminant and Rvalue::Discriminant). Any optimization that wants to work on niches would need special treatment for that case anyway. IOW, it's not like Stacked Borrows the way it works right now requires special care around niches -- it is that something like your proposal would allow a more "stacked-borrows-like" treatment of SetDiscriminant and Discriminant. As mentioned before, the question is if such things come up often enough, i.e. if such optimizations can be applied often enough, to justify the extra complexity.

[RalfJung]

Another note: if we end up deciding for #77 that validity of a reference is just about its bits, then your proposal would have the strange consequence that a &mut bool pointing to a non-bool byte is itself valid, but when you reborrow that reference and then pop the reborrow off the stack, now you have UB. Basically you end up with "depth 1 validity on mutable reference invalidation", which is somewhat odd.

[RalfJung]

I just realized there is a larger problem with your proposal: everything in SB is per-location, but validity invariants are not! When we are popping an &mut tag off the stack, that doesn't mean this reference is entirely invalid, just that it is invalid for this location. There is no place where Stacked Borrows "knows that a reference has been dropped".

So to implement your proposal we'd actually have to keep track of how many locations a tag is active for, or something like that, and even then I am not convinced it would work out... maybe that is checking some things too late then.

[digama0]

I meant using only the pub portions, yes. I didn't write out the module wrapping.

(FYI I noticed this after writing the original comment and rewrote this section, see the edit.)

Note that checking for writing an illegal NonZeroU8 is very checkable!

Indeed it is, and I would expect Miri to notice such things assuming it appears as language UB. In the particular case of NonZeroU8 I believe it is language UB because the niche optimization is exposed to the compiler; without that I would expect it to be library UB and hence not caught by Miri unless there was a debug_assert or similar in new_unchecked.

It isn't typed memory, it is limited providence. Specifically, it is providence where you are limited to writing exactly 00000000 to the location, no fundamentally different than saying that you aren't allowed to write 0000000000000000 there.

That's not how provenance works (at least in the current implementation). There is no pointer provenance that says you can't write 0 to a location. If you have p: &mut NonZeroU8 then it is undefined behavior to do *p = NonZeroU8::new_unchecked(0) because this is doing a typed copy at type NonZeroU8 with value 0. However, you can still write 0 to that location:

let p: &mut NonZeroU8 = &mut NonZeroU8::new(1);
// *p = NonZeroU8::new_unchecked(0); // UB
// *(p as *mut NonZeroU8) = NonZeroU8::new_unchecked(0); // still UB
*(p as *mut NonZeroU8 as *mut u8) = 0; // DB
// println!("{}", *p); // UB, because we are reading 0 at type NonZeroU8

The validity invariant depends only on the type you are writing at, as determined by the static type of the things on each side of the = or the type of the pointer in ptr::write or ptr::read. When we write 0 to a &mut NonZeroU8 like this, it becomes UB to read (or drop the underlying memory, although that doesn't matter in this case), so this is usually UB fairly soon afterward, but the important part is that the write itself isn't UB, because *p is just a byte in memory, with no provenance that remembers that 0 shouldn't be placed in that location.

[CAD97]

And my example shows that pointer provenance remembering what type it's "really" writing to isn't tractable, either.

The problem with it is that raw pointer operations necessarily don't change provenance.

If you have *mut E (for my example), it's perfectly valid to write 0x00_01 or 0x01_01 to it. But when you split the pointer into *mut E.discriminant and *mut E.value, what happens? All that these pointers "know" from their provenance is what byte of E they're pointing to; notably not which discriminant is currently in memory.

Essentially, this is the example where you have *mut Option<NonZero>, just written out a bit more.

I also strongly expect that bytewise memcpy should be implementable inside the abstract machine (given a byte type exists). memcpy existing means that a) a typed copy can be replaced with a bytewise untyped copy, and b) it must be valid to write temporarily invalid bytes to memory via such. (As an example, consider writing 0x0000 on top of 0x0101 "at type E.")

---

There are two "solutions" to this I know of so far, neither of which are particularly nice.

• In addition to validity checks on typed copy, add validity checks on SB tag pop. (As an optimization, this can be done only for Raw tags, since only they can do a "wrongly" typed copy.) However, this is messy for a number of reasons:
  • SB tags currently don't care about the actual contents of memory, and this is a nice property to maintain.
  • SB tags are currently byte granularity, and this is a nice property to maintain.
  • You can pop only a single byte of a larger value's SB tags; how does that even check validity?
  • Basically, while this is a direct "patch the hole" solution, it doesn't work in practice.
• Add to pointer provenance the validity rules for the bytes they have provenance over. This is also messy for a number of reasons:
  • Validity is a many-byte question, but you can write a single byte at a time. How do you determine if that byte is valid to write?
  • Rust memory is completely untyped, and this is a nice property to maintain. Putting the typing into the pointers is a cute trick to avoid typed memory basically in name only.
  • With the untyped memory, it's currently the case that you can write whatever junk you want into a pointer's pointee bytes, so long as you fix it up before anyone else sees.

So, TL;DR of that: there isn't even a known way to say the OP example is UB without a major restructuring of how SB's model of the AM semantics works.

(And if you want to go earn your PhD making a formally sound competing model to SB, then I say glhf!)

[soundlogic2236]

Rust memory is completely untyped, and this is a nice property to maintain. Putting the typing into the pointers is a cute trick to avoid typed memory basically in name only.

So, I would actually disagree with this being typed memory "basically in name only". I think it more resembles a "capability" model. #316 I think in part comes down to how permissions get restricted and unrestricted as passed through various phases of the memory lifecycle. The memory is untyped and very general in providence, but the allocator may impose restrictions when the memory leaves, which the allocator itself doesn't have to obey once it is passed back, as long as it was the allocator that imposed those restrictions. The memory remaining untyped for the entire program while the pointers carry further restrictions plays a valuable role.

However, I think the memcopy problem is a pretty big one here. If we have a NonZeroU64, then with a handwritten memcopy and the loop unrolled, we might do a sequence of 8-bit writes which may involve removing all the ones before we write back a single zero. While calling another function that gets to observe the NonZeroU64 would have problems, this seems to clearly show we can't say that the illegality happens at the moment of writing.

However, this code having radically different meaning based on T still feels extremely uncomfortable to me:

fn func1<T, F: FnOnce(&mut T)>(mut v: Option<T>, f: F) -> bool {
    match &mut v {
        Some(ref mut b) => f(b),
        None => (),
    }
    return true;
}
fn func2<T, F: FnOnce(&mut T)>(mut v: Option<T>, f: F) -> bool {
    match v {
        Some(ref mut b) => f(b),
        None => return true,
    };
    return v.is_some();
}

When T is u8, there is I believe no way to get these functions to differ without undefined behavior. Even if I extrapolate out the location and try to write a pointer there, MIRI complains. However, when T is something like a NonZeroU8, suddenly func2 can start returning false without MIRI batting an eye.

We can also imagine a 'hard mode' memcopy, where it spreads the writes across multiple threads for some reason. I do feel even this should be legal.

But when I think about the actual reasoning I think justifies it, it comes out as something between the two options given. Something like "this write is allowed through this pointer, when this pointer promised to obey certain rules, because by the time it will be observed (see: popping tags) I promise that someone will have fixed this up".

When I try to imagine formalizing this, it seems like the most general way would be something like... when you hand out a pointer, you get to set the rules that then get triggered when tags are popped and such, and even if it is transmuted or such that can only narrow the rules further. This... also seems like it helps with the nested allocator case in some ways, but... the level of generality of this sort of reasoning makes me worry about actually implementing it into a checker.

It seems like the general pattern here would be saying that pointers/references get to encode generators for predicates that get written every time they are used to write, and then get checked on read. Having functions generating functions as a basic building block for providence checking at least sounds bad.

But the actually relevant ones there seem... at lot easier to handle. Owning an allocation seems the most complicated in a lot of ways, but is the primary thing stacked borrows was made to solve.. Leaving the selected constructor in the same state that it was when the inner reference was made seems downright trivial in comparison.

[RalfJung]

When T is u8, there is I believe no way to get these functions to differ without undefined behavior. Even if I extrapolate out the location and try to write a pointer there, MIRI complains. However, when T is something like a NonZeroU8, suddenly func2 can start returning false without MIRI batting an eye.

I view this as a consequence of doing layout optimizations. It's not surprising that for code doing byte-wise accesses, this has consequences. Reordering fields also changes some otherwise 'generic' properties in code working on (T1, T2, T3).

But the actually relevant ones there seem... at lot easier to handle. Owning an allocation seems the most complicated in a lot of ways, but is the primary thing stacked borrows was made to solve.. Leaving the selected constructor in the same state that it was when the inner reference was made seems downright trivial in comparison.

It doesn't seem trivial to me. 🤷 Stacked Borrows doesn't really do anything with 'ownership', it 'just' checks that the sequence of pointer accesses made to a byte of memory makes sense (and it does that independently for each byte).

The 'selected constructor' is a very subtle concept -- it basically doesn't exist on the Abstract Machine, it is an emergent property that comes up after interpreting a bunch of bytes using a given type, and with types like Option<NonZeroU64> it non-trivially relies on the correlation of a whole bunch of neighboring bytes. The C memory model tries to impose type-driven structure on memory (values are stored in memory as a 'tree' of nested structs/arrays) whole also supporting byte-level accesses and that is complicated. I don't think we should do any of that for Rust.

[CAD97]

(Ignoring the opsem,) I would like to argue that asserting validity at expiry typically matches developer reasoning better, and better behaves like safety invariant does.

I argue that semantically, the OP example¹ is similar to e.g. the practice of as_bytes_mut(&mut str) -> &mut [u8] or &mut T -> &mut MaybeUninit<T>. You know the memory exists and is writable, so you temporarily allow writing more bytes than the type otherwise would allow, but you need to clean up and put valid safe bytes in before returning control to the parent safe type.

Obviously the safe interface still requires restoring the type-valid (and type-safe) bytes. This is about the validity requirement. For that, I still hold my previously stated position that we have and should keep untyped memory, and that means only doing type-dependent assertions when doing a typed operation (copy, maybe retag; pop is untyped).

The observation is that restoring the invariants before exiting through the invariant-holder matches the usual patterns, and diverging from this for unsafe opsem is a difference that will need to be learned.

Footnotes

1. fn main() { unsafe {
       let mut x = Some(&0); 
       match x {
           Some(ref mut b) => {
               let u = b as *mut &i32 as *mut usize;
               // Just writing into a *mut usize
               *u = 0;
           }
           None => unreachable!(),
       }
       assert!(x.is_some());
   } }
   

   ↩

[CAD97]

So, TL;DR of that: there isn't even a known way to say the OP example is UB without a major restructuring of how SB's model of the AM semantics works.

I have a proposal for an opsem which could disallow the OP example (at least as written): use a protected tag for match produced references, like the protectors used for function arguments.

Aside: This of course presumes that function protectors assert something about the referenced memory. This is currently not the case, but doing a read on retag/protector (therefore asserting byte-validity of the referee) is at least possible.

Restated: this would make

unsafe fn oops(x: &mut &i32) {
    (x as *mut &usize as *mut usize).write(0);
}
fn main() { unsafe {
    let mut z = Some(&0);
    match z {
        Some(ref mut b) => oops(b),
        None => unreachable!(),
    }
    assert!(z.is_none());
} }

the same opsem as without the function.

There is an important caveat to inserting protectors on match-introduced references, though: unlike in functions, NLL allows invalidating the reference before it is lexically inaccessible, e.g.

fn main() { unsafe {
    let mut z = Some(&0);
    match z {
        Some(ref mut b) => {
            (x as *mut &i32 as *mut usize).write(0);
            assert!(z.is_none());
        }
        None => unreachable!(),
    }
} }

Issuing protectors here thus requires removing the protector when the borrow is invalidated non-lexically. This information may not be available in the current structure of MIR, and would need to be added during MIR borrowck.

This limits the viability of the approach somewhat.

(Protectors could additionally be used on any introduced reference with this semantic of scheduling the removal of the protector.)

Also to note: this is not to advocate for this approach, just to note it as an approach.

noted later: there's a significant flaw with this approach: using a parent raw pointer does not cause the child reference to be known to be invalidated.

[RalfJung]

@CAD97 so you are arguing that we should not have UB for "invalid values on tag invalidation", but you are also proposing an opsem for achieving exactly that thing you don't want? That's a bit confusing so I am trying to make sure I understand you correctly here. :)

[CAD97]

My position is roughly summarized as

• untyped memory implies that writing only cares about future reads
• unprotected¹ tag invalidation clearly shouldn't throw UB for invalid values
  • in part, because type information has been lost by then
  • in part, because these tags can be bytewise invalidated
• despite my previous assertion otherwise, it is possible to prevent invalid not-used-again values without a complete overhaul to the SB model
  • specifically, because when removing a tag protector, the type information is available to do a typed read, validating byte validity
  • this is not currently done, but could be done, and may potentially be beneficial or desired
• and we could potentially add protectors within a function
  • e.g. references manifested by match patterns could reasonably be considered protected
  • but this has to deal with the fact that we do allow non-lexical lifetime invalidation
  • new: and this means that match protectors would make a parent raw pointer behave differently than a parent reference²

Footnotes

1. as in, invalidated by access through a tag before it on the borrow stack, rather than preventing use of tags before it until actively popped/unprotected ↩

2. consider

   let mut place = 0i32;
   let ptr = &mut raw place;
   match *ptr {
       ref mut x => {
           *ptr = 1; // here
       }
   }
   

   here this must be valid if ptr: &mut i32, but placing a protector on x would make this UB with ptr: *mut i32, as the lifetime of x is not statically known to be invalidated. ↩

[CAD97]

An interesting variant of invalid-not-used-again values came up on Zulip w.r.t. MIR drop elaboration:

// only ever instantiated at <T=bool>
unsafe fn drop_uninit<T>() {
    let mut x = std::mem::zeroed::<T>();
    let p = addr_of_mut!(x) as *mut MaybeUninit<u8>;
    p.write(MaybeUninit::uninit());
    // Drop(x) <- current MIR
    // drop_in_place(&mut x); // <- proposal
}

fn main() {
    unsafe { drop_uninit::<bool>(); }
}

This is very similar to an example in the OP

  let mut x = true;
  let xptr = &mut x as *mut bool as *mut u8;
  *xptr = 2;

but perhaps slightly more interesting due to writing undef and the framing w.r.t. generic MIR rather than concrete.

[RalfJung]

FWIW the Drop in current MIR takes a place, not a value, so it is pretty much the same as drop_in_place(&mut x).

[RalfJung]

FWIW https://github.com/rust-lang/rfcs/blob/master/text/2195-really-tagged-unions.md contains an example that expects at least temporary violation of the validity invariant of an &mut T to be allowed.