Is `transmute(usize)` as `Option<&T>` sound?

help
1

The story: in one of my projects I need to play a game with tagged pointers so I could save some memory. More specifically:

#[repr(align(2))]
struct Data(i32);

struct TaggedPtr(usize, PhantomData<Data>);

impl TaggedPtr {
    fn null() -> Self {
        TagedPtr(0, PhantomData)
    }

    fn new(data: i32) => Self {
        TaggedPtr(Box::into_raw(Box::new(Data(data))) as usize, PhantomData)
    }

    fn tag(&mut self, tag: bool) {
        // this is sound since #[align(2)] guarantees LSB of the pointer is 0
        if tag { self.0 |= 1; } else { self.0 &= !1; }
    }

    fn as_ref(&self) -> Option<&Data> {
        transmute(self.0 & !1) // <--- is this sound? The Option<&T> should be represented as 0 for None
    }
}

So can I perform a transmute like this if I'm 100% sure input is correct?

UPD: please pay attention that I'm transmuting between usize and Option<&T>, Data is not really involved here.

2

Based on what @RalfJung has written about pointers and integer casts, it sounds like it's okay. It has to be, because it's considered sound to use memcpy to move pointers around, and what you're doing really isn't different from what memcpy does. (you're using OR to manipulate individual bits, but memcpy uses SIMD intrinsics to move around multiple pointers at once in a single byte vector, so both of them need to track provenance in a way that can track individual pieces of the pointer)

1 Like
3

as_ref seems UB to me, Option and TaggedPtr aren't repr(C) and the nomicon says:

Transmuting between non-repr(C) types is UB

You could add an if to make it correct.

I'm not sure repr(align(2)) is necessary, Data is already aligned to 4 bytes.

4

It should probably be written as:

match self.0 & !1 {
    0 => None,
    n => Some(&*(n as *const Data)),
}
4 Likes
5

Add #[repr(C)] or #[repr(transparent)] to Data to ensure it's represented the same as an i32. Then use a match like @notriddle suggested to create the Option. It might be okay to transmute, but why risk it when you can do a clearly okay pointer cast?

3 Likes
6

Could you please explain why do I need #[trasparent] in this case? I'm confused because I'm not creating a reference to i32 but a ref to Data itself, I'm not making any assumptions about representation of Data (except LSB is zero but this is pretty sound AFAICS)

7

The unsafe code guideline has a section regarding the layout of Option<&T> https://github.com/rust-lang/unsafe-code-guidelines/blob/master/reference/src/layout/enums.md#discriminant-elision-on-option-like-enums.
If I'm reading correctly, it is guaranteed that Option<&T> has the same layout as &T except "all zeros" bit-pattern represents the None. Thus, your code is sound (but I'm not an expert!).

8

Yes, this is how it's done for now. But it doesn't get optimized in debug mode and this is quite a heavy used part of the code. Profiler tells me transmute could speed it up to 35% and I'm quite concerned about tests' run time

9

This is an excellent point and the the reason why I'm asking in the first place. But please note: I'm not transmuting between Data and Option, I'm transmuting between usize and Option<&T>. Both usize and &T are repr(C) but I'm not sure about Option so here I am.

10

Your reference was originally created from a Box<i32>, so the reference points to an i32. Turning such a reference into a &Data requires that they have equivalent layout.

1 Like
11

Oops, this is a typo, the code is updated. In production I don't do Box::new(i32), I do Box::new(Data(i32))

12

Ok, citing unafe-code-guidelines:

Option-like enums where the payload defines at least one niche value are guaranteed to be represented using the same memory layout as their payload. ... niche values are used to represent the unit variant.

The niche of a type determines invalid bit-patterns that will be used by layout optimizations.
For example, &mut T has at least one niche, the "all zeros" bit-pattern. This niche is used by layout optimizations like " enum discriminant elision" to guarantee that Option<&mut T> has the same size as &mut T .

&T has "all zeros" niche value too, hence I'm deriving from here: Option<&T> is guaranteed to have the same layout as &T when Some and "all zeros" pattern when None. This is the same layout as for *const T, so as long as usize contains a valid address the transmute is valid.

Please correct me if I'm wrong.

1 Like
13

You're right, TaggedPtr doesn't come into play. Option isn't repr anything but @pcpthm could be right and Option<&T> is a special case where no UB occurs? I don't know.
But layout isn't enough, this code doesn't trigger any warning from the compiler nor Miri, but is UB:

struct TwoInt(u32, u32);
fn main() {
    let x = TwoInt(0, 1);
    let y: u64 = unsafe {std::mem::transmute(x)};
}
14

Nothing's special about Option here: non-null optimization is guaranteed in certain circumstances, see my comment above.

In your example you're transmuting between (u32, u32) and u64, but they do not have the same layout, that's why it's UB.

15

It seems to me that it should be defined behaviour based on the link @pcpthm posted:

Option-like enums where the payload defines at least one niche value are guaranteed to be represented using the same memory layout as their payload. This is called discriminant elision , as there is no explicit discriminant value stored anywhere. Instead, niche values are used to represent the unit variant.

The most common example is that Option<&u8> can be represented as an nullable &u8 reference -- the None variant is then represented using the niche value zero. This is because a valid &u8 value can never be zero, so if we see a zero value, we know that this must be None variant.

Example. The type Option<&u32> will be represented at runtime as a nullable pointer. FFI interop often depends on this property.

Example. As fn types are non-nullable, the type Option<extern "C" fn()> will be represented at runtime as a nullable function pointer (which is therefore equivalent to a C function pointer) . FFI interop often depends on this property.

unsafe-code-guidelines

Additionally by running this playground with miri (under tools), we can see that miri does not detect any undefined behaviour from the code.

Of course miri is not proof that it is defined behaviour, but at least it means that this is what the compiler does today.

16

Well, if my understanding is correct, the code you provided is not UB provided that TwoInt had size 8 and align 4 (but Rust compiler can choose other layouts).
Thus,

struct TwoInt(u32, u32);
fn main() {
    let x = TwoInt(0, 1);
    assert!(size_of::<TwoInt>() == 8 && align_of::<TwoInt>() == 4);
    let y: u64 = unsafe {std::mem::transmute(x)};
}

is never UB (but can fail the assertion).

17

The transmute of TwoInt is undefined behaviour, exactly because it would be valid for the compiler to do something different than what it did here.

For example, it might still have swapped the fields.

18

See this:

The layout of a type is its size, alignment, offsets, and the recursive layouts of its fields.

In your example, TwoInt and u64 have the same size but different alignment, so it's UB nonetheless

EDIT: yes, alignment is the same, but offsets are not nailed down. As @alice noted here, compiler might have swapped the fields just fine.

But if TwoInts were repr(C) it would be OK since fields couldn't be reordered and no additional padding bytes are involved

19

transmute doesn't require alignment (of the value itself, not about "inner types") to be the same, at least not mentioned in the document https://doc.rust-lang.org/std/intrinsics/fn.transmute.html.

Yes, the value of y can be two different values depending on the layout (also endianness) with my assumption. But it is only an unspecified behavior (the behavior is only in a defined set, in this case, of size two), not an undefined behavior UB (the behavior can be anything). (I'm 80% sure about this).

20

This is UB at least because nomicon says

Transmuting between non-repr(C) types is UB

TwoInts is not repr(C). Full stop.