Storing an object as &Header, but reading the data past the end of the header

[thomcc]

This is related to #2 but the read is not out of bounds of the allocation, not being written to by other threads, not the bytes of a &mut Blah, etc. That is to say, really the code is trying to model a dynamically sized type, that for one reason or another does not support (Note that ther are a number of custom DST proposals).

So, I heard that it was UB for you to have a &T and read outside the bounds of that T, even if conceptually it's a totally in-bounds read. E.g. T here may be a ZST, or it may be a header after which a trailing array is expected, or standing that sits at the head of a trailing array, or it may be a struct that's the common shared fields of some set of other struct... These are pretty common in unsafe code as it's a pattern which is both legal and useful in C and C++.

It's pretty common in Rust too:

• It's not unheard of in C apis to use a #[repr(C)] struct Foo { _priv: [u8; 0] }, as this is what bindgen uses. Some of these APIs then go on use &Foo in the Rust code. (This is essentially a workaround for a lack of a stable extern Type). This code doesn't read the data, so the only issue would be if we told LLVM it could assume things about the pointer that turn out to be untrue in a situation like cross-lang LTO, probably.

• Similarly, I've seen other FFI code that used a struct CStr([u8; 0]) for a similar purpose — as a version of std::ffi::CStr that you can actually pass to C directly. (I even almost did this for ffi_support::FfiStr, but went with a pointer inside so I could easily check for code passing in null).

• bitvec has a BitSlice type which acts a lot like a slice that magically has bit-level indexing. Internally it's something like struct BitSlice { _mem: [()] } which lets it behave like an unsized type, The "pointer" and length are both specially encoded values that contain both the actual pointer/length as well as bit-level offsets for tracking where withing byte things are. There are a lot of reasons this might be illegal, but I had not thought mem::size_of_val returning the wrong value was the actual one.

• anyhow::Error internally wraps a Box<ErrorImpl<()>>, where ErrorImpl<T> contains a vtable, a backtrace, and then the T. ErrorImpl<()> is used as it behaves as the "common header" for real ErrorImpl values. On construction, Box<ErrorImpl<T>> is converted to Box<ErrorImpl<()>>, when stored in the Error.

  Whenever a method is called that needs to delegate to the vtable, the Box<ErrorImpl<()>> is converted into the right pointer type for the vtable function (one of &ErrorImpl<()>, &mut ErrorImpl<()>, Box<ErrorImpl<()>>) which is called with that pointer. The first thing the vtable function generally does is convert the reference to e.g. &ErrorImpl<T>, example: https://github.com/dtolnay/anyhow/blob/99c982128458fecb8d1d7aff9478dd77dac0ee3b/src/error.rs#L538-L545. (I had always kind of thought it wasn't okay to use Box<T> here, but I'm surprised that stuff like &ErrorImpl<()> to &ErrorImpl<RealType> isn't okay either).

• wio-rs contains VariableSizedBox which provides this pattern in a library form, and IIUC is mostly intended for the flexible-array-member case. The API attempts to launder pointers to the object, which is... very non-obvious. It seems like it plausibly avoids the issue here, though, but it's insanely subtle, and if this is the recommended pattern, I suspect it will need a very good nomicon entry. https://github.com/retep998/wio-rs/blob/9bf021178b2d02485f1bd35e6cff41bf52d4a9a2/src/vsb.rs#L98-L113

• I do something similar in arcstr, where there's a header and a variable length segment that trails it. I avoided issues here by luck, as I took great care to avoid ever putting the inner type behind a reference. This was lucky since I wasn't aware of this at all, and did it for other reasons. This was painful as it required field hard-coding offsets.

• This isn't to say anything of the numerous C or C++ apis which expose polymorphism in this way — In c++ this is how single non-virtual inheritance is represented, so it's especially common, although it was common in C too. Additionally, C code with a flexible array member is in tons of places, and not just windows APIs.

This is just a few off the top — there's a lot of unsafe code that does this. Personally, I had thought it was allowed so long as you don't go past the actual bounds of the allocation, it makes some sense that it's not though, unfortunately. (Somehow, I don't think I've ever had miri trouble me about it, but it's seeming like it's just because of luck && coincidence more than anything else).

Anyway, I think if this is UB we should start being way more vocal about it, because it's a totally legal pattern in C and C++, and common.

[thomcc]

Anecdotally, I think why I thought this was allowed is it mirror how some other functionality of references behave. In particular converting &'a T => &'static T is legal, so long as you only ever use the T within its actual lifetime. (And in the case of &mut, so long as the &mut really is granting exclusive access).

Additionally, the fact that in many other cases we're allowed to "pun" memory and have it just work the way we expect gave me a false sense of security here.

[burdges]

At least if using C FFIs then you want extern type for this. See rust-lang/rfcs#1861
rust-lang/rfcs#2255 rust-lang/rfcs#2984

[RalfJung]

As you noted, this looks like a duplicate of #134.

Note that all of these things are allowed to raw pointers. So all of these APIs that you describe can be implemented, as long as only raw pointer and no references are used.

But for references, this would be a serious problem as it breaks a very powerful optimization:

fn optimized(x: &mut i32, f: impl FnOnce()) {
  *x = 5; // This write is redundant and can be removed, according to Stacked Borrows (under unwind=abort)
  f();
  *x = 6;
}

If we allow reads outside the bounds of the given reference, we can no longer do this optimization!

fn print_neighbor(x: &mut i32) {
  // use some unsafe code to read the memory at `x - 4` and print that to stdout
}

fn counterexample() {
  let mut pair = (0, 0);
  optimized(&mut pair.0, || print_neighbor(&mut pair.1));
}

The optimization changes what gets printed to stdout. Optimizations that change program behavior are illegal, so we cannot do this optimization -- except if the program has UB. That's why it is very important that the above program has UB.

(Things get even worse if we also allow writes outside the range indicated by the type. At that point I do not know how to still have any useful optimizations.)

[Diggsey]

Hmm, I have code which does this because using raw pointers everywhere results in really horrible code. It implements a "thin vec" type, where the length and capacity are stored inside the allocation.

#[repr(C)]
#[repr(align(4))]
struct Header {
    len: usize,
    cap: usize,
}

(The items are stored inline following the header)

All the internal methods are implemented on the Header type, and take &self or &mut self, and then use pointer arthmatic from self to access the items known to follow.

This is one of several "thin" wrapper types that each have their own header type. Rewriting them all to use raw pointers would result in very messy and hard to read code, not to mention less safe (since atm the unsafe parts can be fairly contained).

This Header type can never exist on the stack or as part of another data-structure, so perhaps there's some way to exploit that? A couple of ideas spring to mind:

1. Limit the scope of UB to cases where the struct is on the stack or is contained within another type. This leaves the compiler free to optimize the case you mentioned above.

2. Allow types to opt-in to being unsized, and prohibit these optimizations on these types.

[Diggsey]

3. Have some kind of provenance rule similar to the &mut/& provenance for raw pointers discussed in Differences between *const T and *mut T. Initially *const T pointers are forever read-only? #257, but for layout, where all that matters is how the original pointer was obtained.

   So, the initial pointer returned from alloc() is allowed to access anywhere in the allocation. References derived directly from that pointer are also allowed to access anywhere, but as soon as you go through a field access, you're then constrained to the layout of that field.

[RalfJung]

One difference between my example and the desired use-cases is that not only is the pointer used "out of bounds", there also is another pointer that actually accesses those out-of-bounds parts. Maybe that could help.

Here's the rough idea: if we have a mutable reference p: &mut (i32, i32), then if we create two derived references, say &mut p.0 and &mut p.1, this all can only work out if the derived references are used in a disjoint way. Currently this is enforced by pre-determining which memory which reference may use: only the one described by its type. If we remove the type from the picture, we'd instead have to dynamically track which locations are used by both references, and then raise an error the moment those sets stop being disjoint.

I am sure interesting corner cases will show up when this gets actually implemented. But this will require a significant rework of Stacked Borrows -- basically a whole new model, based on what we learned with the first one. I certainly hope to pursue this project at some point, but unfortunately that won't happen in the near future.

[burdges]

As for implementation corner cases, there exists some consensus in the RFCs linked above that size_of_val, align_of_val, and even Box::drop all require the type's size without dereferencing, and thus should panic when passed such truly unsized types via thin pointers, including extern types.

[thomcc]

@RalfJung Yeah, I would have assumed your example was invalid, and you figured it out but it's much broader and more dodgy than what I'm asking for.

That said, your suggested solution of tracking this based on the locations the references may use sounds extremely nice and easy to reason about!

I think I'm already a huge fan, since it matches my mental model very closely — That is, in a situation like this where I have a &T and read outside of it, in reality my &T just extends to those locations I access dynamically, but still follows &T semantics (similar to how DSTs work, but obviously not supporting size_of_val). Ditto for &mut T. The way I reason about "follows &T semantics" is more or less based on memory locations (I've certainly been trying to reason about it closer to how stacked borrows is currently formulated though, ...).

Also, it feels like this model would allow #243, which is... important for memory allocators.

that won't happen in the near future.

Honestly, just the notion that there's a potential model in the distant future that fits better with the code that is out there in the wild makes me very optimistic, since I had thought stacked borrows was mostly in a final tweaking phase and major changes weren't in the cards.

I was kind of getting pretty worried about how bad the the fallout was going to be, so it makes me feel better.

(Off topic, but related to you not having time: I saw you finished your PhD recently, congrats! Hope you're able to relax at some point and manage to land somewhere nice)

[RalfJung]

Also, it feels like this model would allow #243, which is... important for memory allocators.

Ah yes, that would be nice.

I am also worried about how much the current semantics relies on computing the size of a value; if we ever get custom DST that would be a total nightmare. So something more based on "what locations is this actually used for" would also help here.

OTOH some optimizations rely on introducing extra reads/writes that were not present before; I cannot imagine how those would work without taking into account the size of a type. Basically, everything related to protectors seems to rely pretty fundamentally on saying in advance that some region of memory "belongs to" this reference. But maybe it suffices to consider these a lower bound for what the reference may do, as opposed to now where this region also serves as an upper bound.

Honestly, just the notion that there's a potential model in the distant future that fits better with the code that is out there in the wild makes me very optimistic, since I had thought stacked borrows was mostly in a final tweaking phase and major changes weren't in the cards.

More research will be needed to show if this model is indeed viable. But as far as I am concerned, Stacked Borrows is the first word in terms of (precisely worked out) aliasing models for Rust, not the last.

(Off topic, but related to you not having time: I saw you finished your PhD recently, congrats! Hope you're able to relax at some point and manage to land somewhere nice)

Thanks! :) But what is that "relax" thing you are talking about? ;)

[thomcc]

But maybe it suffices to consider these a lower bound for what the reference may do, as opposed to now where this region also serves as an upper bound.

Yes, that seems totally reasonable, and also fits with what unsafe code I've seen in the wild does/assumes (as well as my personal mental model).

It's also easy to teach/explain why a too-large reference is bad (compiler allowed to insert speculative and spurious reads/writes), whereas it seems much harder to explain a too-small one (providence, stacked borrows).

Even C tends not to have a pointer refer to a larger type than reality — although I believe it is legal for SomeUnion* to actually only be a pointer to one of the members. Using this is rare though, and Rust code which wants to emulate it can just use raw pointers.