Am I triggering undefined behavior here?

1

I want to have a byte slice that is statically guaranteed to have the same size as a type. So I came up with basically this:

/// Bytes of the same size as `T`.
#[repr(packed)]
pub struct Bytes<T: ?Sized> {
    buf: ManuallyDrop<T>,
}

impl<T: ?Sized> Bytes<T> {
    /// This *is* unsafe!
    /// 
    /// Why? Because padding bytes might have undefined values.
    pub unsafe fn from_ref(value_ref: &T) -> &Bytes<T> {
        &*Self::from_ptr(value_ref)
    }   

    pub fn from_ptr(value_ptr: *const T) -> *const Bytes<T> {
        unsafe { mem::transmute(value_ptr) }
    }   
}

impl<T> Bytes<T> {
    pub fn from_slice(buf: &[u8]) -> &Bytes<T> {
        assert_eq!(buf.len(), mem::size_of::<T>());
        unsafe {
            &*Self::from_ptr(buf.as_ptr() as *const T)
        }   
    }
}

impl<T> AsRef<[u8]> for Bytes<T> {
    #[inline(always)]
    fn as_ref(&self) -> &[u8] {
        unsafe {
            slice::from_raw_parts(self as *const Self as *const u8,
                                                 mem::size_of::<T>())
        }
    }
}

MIRI appears to be ok with this, allowing access to every byte in the slice if Bytes is created from a slice, and panicking as expected if (unsafely) created from a reference and padding bytes are accessed.

My question is if this construction is risking UB by creating an invalid reference to an invalid value? (e.g. Bytes<bool>)

I'm careful to never actually access this reference except a byte slice, and the only safe way to create a Bytes reference is to create it from a slice, which appears to avoid the notorious access to undefined values source of UB seen in mem::uninitialized() (note how I haven't provided any way of creating an actual Bytes value). Finally, because of #[repr(packed)] the alignment doesn't matter.

1 Like
2

This is unclear to me. I'm not sure that access to padding through a &[u8] slice is a resolved question in rust, currently. Do you have a source on the matter? I think I remember that the value of the padding isn't "fixed" but may change at every access, meaning that the slice doesn't upheld the invariants normally expected from an immutable slice (namely, that its content won't change). This might be a silly idea, but I wonder if it wouldn't be better defined with a slice of &[Cell<u8>]?

I'm afraid I don't understand what this achieves. In my understanding #[repr(packed)] may also cause runtime errors when trying to build a reference to a packed structs?

Nitpick, but can't your Bytes::from_ptr method be rewritten to avoid the use of mem::transmute:

    pub fn from_ptr(value_ptr: *const T) -> *const Bytes<T> {
        value_ptr as *const Bytes<T>
    }

?

3

This is unclear to me. I’m not sure that access to padding through a &[u8] slice is a resolved question in rust, currently. Do you have a source on the matter? I think I remember that the value of the padding isn’t “fixed” but may change at every access, meaning that the slice doesn’t upheld the invariants normally expected from an immutable slice (namely, that its content won’t change). This might be a silly idea, but I wonder if it wouldn’t be better defined with a slice of &[Cell<u8>] ?

Rust maybe not. But my understanding is it's moving towards that as it's a hard error in MIRI.

I’m afraid I don’t understand what this achieves. In my understanding #[repr(packed)] may also cause runtime errors when trying to build a reference to a packed structs?

Without the #[repr(packed)] you can't create a reference to Bytes<T> from a slice, as the alignment of a [u8] slice is 1 while T might be higher. Again, that might not actually matter in Rust, but it's an error in MIRI.

Nitpick, but can’t your Bytes::from_ptr method be rewritten to avoid the use of mem::transmute

Good catch! Thanks.

4

This all looks sound to me, as Bytes<T> is just a fancy [u8; size_of::<T>]. So long as you never turn &Bytes into &T, there's no chance of an invalid reference existing.

2 Likes
5

Interesting! So basically reference safety isn't transitive?

6

OK, I see now that you addressed this in the comments of your Bytes::from_ref method:

/// This *is* unsafe!
/// 
/// Why? Because padding bytes might have undefined values.

I now read this as:

/// # Safety
///
/// T must not contain any padding for a call to this method to be safe.

(now I'm sad that we don't have a std::repr::has_padding<T>() to at least panic in this case and make the function safe)

Regarding your question, to the best of my knowledge I'm unable to give a definitive answer, but I can at least reformulate it according to my understanding:

You are wondering whether Bytes::from_slice is actually safe, given that it point to an inner ManuallyDrop<T> that can contain an invalid value for T (e.g., if T == bool and I pass &[8u8] to that function).

This function performs the following operations:

  1. Check the size of the input buffer
  2. Turn the pointer to the input buffer into a pointer to T
  3. Call from_ptr to turn the pointer to the input buffer (that was turned into a pointer to T) into a pointer to Bytes<T>
  4. (unsafely) dereference the result to get a Bytes<T>
  5. Take a reference to the dereferenced result to get a &Bytes<T>.

The only unsafe operation in that list is 4., so to me it boils down to whether or not that pointer is safe to dereference, which in turn in my understanding depends on which casts are allowed between pointers (as-in, casting from *const U and *const V is always allowed, but dereferencing the resulting pointer isn't always).

In my understanding, but I may very well be wrong here (as evidenced by CAD97 not seeing anything wrong with the code), I'd lean towards this being an unsafe pointer cast. In my limited understanding, to be able to dereference a pointer v of type *const V obtained from a pointer u of type *const U, the following must hold:

  1. u must have been obtained from a valid &U
  2. U and V must have the same size and V must have an alignment lower or equal as U's alignment
    1. U and V must have the repr(C) representation and have the same fields in the same order, or
    2. V must have the repr(transparent) representation and have a single non zero-sized field of a type W, such that U=W or 3.2. transitively holds for U and W
  4. There definitely are special cases for casting pointers from/to primitives types

Again, this is just my understanding (and I don't think I've seen the rules for pointer-cast safety written anywhere), which may very well be wrong (or at least too restrictive, or too simplistically formulated), but I'd lean to say that the example is not safe under these rules, because you are dereferencing a pointer that was obtained from a *const T into a Bytes<T>, and Bytes<T> doesn't have repr(transparent). Even if it did, I think that the cast from the slice pointer into the *const T might already make the pointer undereferenceable for non-primitive or repr(C) types.

7

Actually, I was wrong! [playground] ManuallyDrop<T> shares the validity invariants of T. This means that you're constructing an invalid representation, which is insta-UB. Here's an example that constructs the invalid value; Miri doesn't catch it, but that's a bug.

Safety is transitive, but you've never materialized a &T. You have a &Bytes<T> that contains a ManuallyDrop<T> (you need to use MaybeUninit as your store type to strip the validity invariant, though).

This is actually almost correct. The one addition is that any explicit repr tag that defines the layout will work. I think #[repr(packed)] does this, though I'm not willing to bet anything of worth on it without someone more in on unsafe weighing in.

2 Likes
8

See the miri bug tracker.

Miri doesn't enforce validity through references, as doing so borders on prohibitively expensive. (Miri is already painfully flow for anything smaller than toy examples, as a reference machine rather than an efficient one).

However, any use of the reference certainly does use the validity invariant to describe how to interact with the backing value, so you're in tough waters if you're transmuting types with anything more strict than trivial validity and no padding.

We're (wg-unsafe, I'm not a member though) still figuring out exactly what the requirements should be. Unsafe playing with layout will always be difficult.

Hopefully const generics are sometime by the end of 2020 so you can just do literally [u8; {mem::size_of<T>}].

9

Ah, so to be clear, I'm well aware of the invariant on ManuallyDrop. But I think you helped rephrase my question: is the reference to the invalid representation alone enough to trigger UB, or do you need an undefined representation?

My understanding is the danger with undefined memory is LLVM specifically has many optimizations based on, for instance, removing code paths with references to undefined values. Here however I'm not triggering that behavior - just invalid representations which I'm careful not to ever access.

However, any use of the reference certainly does use the validity invariant to describe how to interact with the backing value

Exactly: in this case I don't have any code that would actually interact with the backing value, other than perhaps the drop impl for ManuallyDrop, which of course does nothing.

Hopefully const generics are sometime by the end of 2020 so you can just do literally [u8; {mem::size_of<T>}] .

Actually if I only wanted this for sized types I could implement it today with MaybeUninit:

#[repr(packed)]
struct Bytes<T> {
    inner: MaybeUninit<T>,
}

Essentially while MaybeUninit neither guarantees that the bit representation will be valid or even defined, Bytes would guarantee that the bits would at least be defined and thus safely accessible as a [u8] slice.

But MaybeUninit requires T: Sized right now, so that solution doesn't work for unsized types. In my actual codebase I defined a Pointee trait that for types for which the layout can be calculated from pointer metadata. Thus my real AsRef impl looks like:

impl<T: ?Sized + Pointee> AsRef<[u8]> for Bytes<T> {
    #[inline(always)]
    fn as_ref(&self) -> &[u8] {
        unsafe {
            let ptr_t = self as *const Self as *const T;
            let layout = T::layout(T::metadata(ptr_t));
            slice::from_raw_parts(self as *const Self as *const u8, layout.size())
        }   
    }   
}

...with the Pointee trait used to determine the size of the type. Pointee meanwhile is:

pub trait Pointee {
    type Metadata : Copy;

    fn layout(metadata: Self::Metadata) -> Layout;

    fn metadata(ptr: *const Self) -> Self::Metadata;
}

As for the motivation for all this: in-place "deserialization" of types with bit-representations carefully constrained to be compatible with mem-mapping.

Note that my other option is to make something like:

struct Bytes<'a, T: ?Sized> {
    marker: PhantomData<&'a ()>,
    ptr: *const T,
}

...but then I need a separate BytesMut and so on. :confused: Much more ergonomic if Bytes is an unsized type.

2 Likes
10

As far as we're certain about Rust's memory model: we don't know. Unfortunately right now it's not much more specific than "what LLVM does" and "what Miri checks", so most of the questions can't be answered definitively.

However, it is likely that when a function is called with &T as an argument, that the T is required to be valid.

The version wrapping a pointer is sure to be sound. The version wrapping the pointee, I'm not confident in answering either way. It really sounds like you need a custom DST, though.

11

Here's the open issue on deciding the validity of references:
https://github.com/rust-lang/unsafe-code-guidelines/issues/77

2 Likes
12

As far as we’re certain about Rust’s memory model: we don’t know. Unfortunately right now it’s not much more specific than “what LLVM does” and “what Miri checks”, so most of the questions can’t be answered definitively.

I had a feeling I might have run into the edge of what's well-defined. :slight_smile:

However, it is likely that when a function is called with &T as an argument, that the T is required to be valid.

Fair enough if that's just true. I'm curious though: what kind of optimizations would be made possible by having that as a requirement? LLVM obviously has poison values and all kind of similar things for undefined bits; I'm not aware of similar optimizations for invalid bit values behind references that aren't dereferenced.

The version wrapping a pointer is sure to be sound. The version wrapping the pointee, I’m not confident in answering either way. It really sounds like you need a custom DST, though.

What do you mean by a custom DST? You mean, like a compiler built-in? Or something implemented with a future custom DST feature? (I of course basically am doing custom DST's in my use-case, just not with specific language or compiler support)

Seems to me that extending MaybeUninit<T> to unsized types is obviously useful, as it'd give you a notion of a reference to memory that may or may not be valid for T, but with a known size if the type's size can be determined solely from pointer metadata. That'll definitely be always true for slices; and currently is true if I understand correctly for trait objects.

13

One of the cases that has been brought forward for why we should require &T to point to a valid T is that people want &! to be uninhabited so that functions taking &! can be just removed from the binary.

Also, you seem to assume that a &[u8] can point to any data. That is far from clear. The relevant discussion for that is here, but the summary is that we might want to require u8 to be initialized, which means that e.g. the 2nd byte of a (u8, u16) (which is padding, assuming it gets laid out in the order I wrote it) is not a valid u8.

At this point I have to insert the mandatory warning that mem-mapping interacts very badly with Rust's reference guarantees. See this discussion for further details.

Congrats, you managed to hit 3 edge-cases at once. :wink:

5 Likes
14

If the intention is just to always contain a valid T inside the Bytes<T>, you can make the API unsafe and this will always work.

If you just want a generic way to express an array of u8 that has the same size as T, then you can write type A<T> = [u8; {mem::size_of::<T>()}]; on stable Rust today (playground).

For unsized fields, what you are doing sounds ok-ish.

15

We add the dereferencable attribute to references declared in the function arguments. This means LLVM is free to assume they're readable (thus it is free to introduce "spurious" speculative reads), which means you may end up with data in an invalid representation on your stack, which means uh-oh.

3 Likes
16

One of the cases that has been brought forward for why we should require &T to point to a valid T is that people want &! to be uninhabited so that functions taking &! can be just removed from the binary.

Ah, that's a good point! ! has size 0, so my current API would happily create a &Bytes<!> reference, which isn't good. It's a pity the size of ! couldn't be defined as, say, usize::MAX instead. Though I can already think of a lot of reasons why that would cause problems. :confused:

Unfortunately, I think that issue alone is a good enough reason to just stick with the obviously correct implementation where Bytes<T> et al. are just wrappers around a pointer.

Also, you seem to assume that a &[u8] can point to any data.

Actually I don't: note how my example at the top makes Bytes::from_ref() be unsafe because padding bytes don't have defined values. It's only creation from a slice that's safe.

At this point I have to insert the mandatory warning that mem-mapping interacts very badly with Rust’s reference guarantees. See this discussion for further details.

I think for my specific use-case I think I'm OK with that, as this would be basically for an object database where other processes writing to the to the file is already a disaster.

FWIW the big picture motivation of mem-map is predictable memory usage: I want it to be easy to write code that accesses data stored persistently with "normal" Rust API's based on returning references and the like. If deserialization creates a copy of the data being deserialized, you can't easily do that without also risking unbounded memory usage.

For a simplified example, imagine an API for a persistently stored key-value tree:

impl KeyValueTree<T> {
    fn get(&self, idx: u64) -> Option<&T>;
}

Who owns &T if it had to be deserialized? You can put Ref<T> wrappers everywhere that deallocate the deserialized T when it goes out of scope, but that gets ugly fast in my particular use-case (I've tried a prototype along those lines before). Mem-mapping appears to have the potential to neatly side-steps this problem, essentially letting the OS's page cache do all the work. (in fact, I suspect memmap will be a bit slower than the alternative for various reasons, but I'm more concerned about having a persistant data API that's easy to use and "just works")

1 Like
17

In my eyes this is no different than the problem with bool. The only difference between bool and ! is that the former has 2 valid bit patterns and the latter has 0. :slight_smile:

I see, makes sense!

That sounds reasonable.

1 Like
18

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.