Stream: t-lang/wg-unsafe-code-guidelines

Topic: Abomonation UB


Frank McSherry (Sep 06 2019 at 14:16, on Zulip):

Recently brought to my attention by @Hadrien Grasland in (https://github.com/TimelyDataflow/abomonation/issues/17) that reconstructing a & T is 1. UB in abomonation because of (at least) the dereferenceable tag promised as soon as a &mut T is instantiated (its fields are then correctly populated, but are initially invalid), and 2. hard to do with NonNull<T> as navigating the structure of T is challenging without a reference due to (I imagine) the lack of field dereferences to NonNull<FieldOfT> .

No clue if this is on anyone's radar, but I personally hold abomonation as a bit of a test for whether a language is suitable for a certain type of systems programming. If it is hard to go from bytes to typed data, without several allocations along the way, that is worth understanding as a something that is possibly being traded away. No intent to claim that either is the right trade-off, just calling out that there is one here either to make, or work to avoid making!

rkruppe (Sep 06 2019 at 14:50, on Zulip):

FWIW problem 2 will be solved (though not necessarily very ergonomically for NonNull, raw pointers have it better) by <https://github.com/rust-lang/rfcs/pull/2582> which enabled field projections through raw pointers without involving any references or other UB traps

Shnatsel (Sep 06 2019 at 17:24, on Zulip):

FWIW there are also https://crates.io/crates/plain and https://crates.io/crates/zerocopy crates to do type punning safely. I wonder if the same issue applies to them as well?
The latter comes with custom derives making sure it's OK, although @Daniel Henry-Mantilla managed to get the same thing validated using pure macro_rules! in https://github.com/m4b/goblin/pull/182

Shnatsel (Sep 06 2019 at 17:26, on Zulip):

Nevermind, I misunderstood the problem.

Frank McSherry (Sep 07 2019 at 15:42, on Zulip):

FWIW problem 2 will be solved

This sounds promising, thanks for the heads up! I apologize for the random drive-bys, but it feels like a full-time job to keep up with things here. I'm hoping that dropping in with an anxiously phrased lament isn't taken the wrong way (actual intent: "important to some! if not all!").

RalfJ (Sep 15 2019 at 13:06, on Zulip):

@Frank McSherry thanks for the comment, it is much appreciated!

RalfJ (Sep 15 2019 at 13:06, on Zulip):

indeed abomonation is something I'd like Rust to support

RalfJ (Sep 15 2019 at 13:06, on Zulip):

so, when you see things that worry you in that regard, please keep us informed :)

RalfJ (Sep 15 2019 at 13:07, on Zulip):

note that dereferencable just says that the reference points to allocated memory

RalfJ (Sep 15 2019 at 13:07, on Zulip):

but for Rust right now we also demand that it points to something valid at the given type -- that's https://github.com/rust-lang/unsafe-code-guidelines/issues/77

RalfJ (Sep 15 2019 at 13:07, on Zulip):

I suppose that's what you are worried about here?

Frank McSherry (Sep 15 2019 at 14:29, on Zulip):

Thanks @RalfJ!

In Abomonation, it's not necessarily the case that the pointer points at allocated memory. We've just pulled a &mut [u8] off the wire, let's say, and would like to start looking at it as a Vec<String>. If we transmute to a &mut Vec<String> with the plan of filling in the pointers, we have a problem as there is some amount of time between the cast and the assignment to the fields. They are never read before being written, but .. I suspect that doesn't save any bacon.

Frank McSherry (Sep 15 2019 at 14:31, on Zulip):

More specifically, none of the pointers are read before being written; length fields and such may well be (we could possibly write the pointer first, but we want to read the len to make sure that the extent of memory described is in bounds before forming a vector whose length could overrun our allocation).

Frank McSherry (Sep 15 2019 at 14:32, on Zulip):

This is all negotiable if it turns out there is a safer way to go from partially allocated memory to in-memory representations (I'm sure there are rules, that they are subtle, and that in my ignorance I am violating many of them).

Frank McSherry (Sep 15 2019 at 14:37, on Zulip):

And, in case it isn't clear, the only reason to have a cast to a mutable reference (as opposed to an assignment from a newly constructed value) is that it is the only way I know to get access to the fields (as I can't guess the layout and sniff around for the length field). Though, another reason might be that with large types only changing the locations that matter could be a win vs overwriting the whole struct.

gnzlbg (Sep 15 2019 at 16:28, on Zulip):

How are you transmuting a &mut [u8] to a &mut Vec<String> ?

RalfJ (Sep 16 2019 at 09:59, on Zulip):

If we transmute to a &mut Vec<String> with the plan of filling in the pointers

if you want to fill it, that means this reference does point to 24 bytes worth of allocated memory, right?
"dereferencable" is not recursive. &mut Vec<String> just means "there's 24 bytes worth of memory there".

Well, at least that's the LLVM side of things. Rust has more aggressive UB, but the pointer in a Vec is a raw one, so Rust will not assume that pointer to be valid, and I don't think it ever could.

RalfJ (Sep 16 2019 at 10:01, on Zulip):

so I don't think I see where there are dangling pointers (not pointing to allocated memory) here in a poblematic way. I am more worried about references you are creating into the backing buffer. or things like NonNull being violated (the ptr in a Vec must never be NULL, and that also means that a &mut Vec<String> must never point to data where that ptr is null -- Rust's validity reuqirement is recursive right now)

gnzlbg (Sep 16 2019 at 10:05, on Zulip):

but the pointer in a Vec is a raw one, so Rust will not assume that pointer to be valid, and I don't think it ever could.

The pointer in a Vec is a Unique<T>, so Rust will assume a couple of things about it (IIRC Unique is a NonNull<T> wrapper with PhantomData and Send/Sync, so this will impact dropck and other things, but NonNull is probably the most important thing as you mentioned)

RalfJ (Sep 16 2019 at 10:11, on Zulip):

right, I meant that we do not assume the ptr to point to allocated memory

RalfJ (Sep 16 2019 at 10:11, on Zulip):

it actually frequently does not, after Vec::new()

Frank McSherry (Sep 18 2019 at 12:57, on Zulip):

if you want to fill it, that means this reference does point to 24 bytes worth of allocated memory, right?

Frank McSherry (Sep 18 2019 at 13:06, on Zulip):

How are you transmuting a &mut [u8] to a &mut Vec<String> ?

Why, std::mem::transmute of course. ;)

I'm apparently the sort of person who keeps nice people like @RalfJ up at night.

RalfJ (Sep 18 2019 at 20:47, on Zulip):

Why, std::mem::transmute of course. ;)

but they don't have the same size.^^

RalfJ (Sep 18 2019 at 20:48, on Zulip):

I'm apparently the sort of person who keeps nice people like @RalfJ up at night.

why, in this thread all I did was during "reasonable" times? ;) (I am in UTC+2)

RalfJ (Sep 18 2019 at 20:49, on Zulip):

At least the language of "points to a valid instance" shakes one up on this (probably healthy). Perhaps we are over-anxious about the potential UB here.

yeah, well, "valid" is still up in the air. but Vec's field in question is a Unique<T>, so what is "valid" for Unique<T>? Well, it cannot be dereferencable(size-of-T) because Vec::new() actually returns non-dereferencable stuff...

RalfJ (Sep 18 2019 at 20:50, on Zulip):

as long as the definition of non-NULL is the same across the encoding and decoding binaries

oh you people have sick minds.^^
Rust does not support platforms where NULL is not the same as "all bits are 0".

gnzlbg (Sep 19 2019 at 07:03, on Zulip):

Well, it cannot be dereferencable(size-of-T) because Vec::new() actually returns non-dereferencable stuff...

There is a "dereferenceable_or_null(size-of-T)" LLVM attribute

gnzlbg (Sep 19 2019 at 07:04, on Zulip):

The problem the pointer of a Vec cannot be dereferenceable is that the size-of-T must be known at compile-time, but for a vec, how many elements you actually have isn't known till run-time

gnzlbg (Sep 19 2019 at 07:04, on Zulip):

There are ways that you could use to communicate this to LLVM though

gnzlbg (Sep 19 2019 at 07:05, on Zulip):

e.g. you could pass the pointer to an identity-like (ptr*, len) -> ptr function that uses the usable_size attribute

gnzlbg (Sep 19 2019 at 07:05, on Zulip):

to tell LLVM that ptr points to an allocation of length len

Hadrien Grasland (Oct 01 2019 at 19:23, on Zulip):

Err... I... have a new one for this thread.

Hadrien Grasland (Oct 01 2019 at 19:25, on Zulip):

Do you think that this evil trick for bypassing an annoying aspect of the borrow checker triggers &mut aliasing UB?

pub fn evil<'bytes>(bytes: &'bytes mut [u8]) -> &'bytes mut [u8] {
    unsafe {
        let bytes_uc: &'bytes UnsafeCell<[u8]> = std::mem::transmute(bytes);
        {
            let bytes: &'bytes mut [u8] = &mut *bytes_uc.get();
            // ... do stuff with "bytes", without leaking references out of the scope ...
        }
        let bytes: &'bytes mut [u8] = &mut *bytes_uc.get();
        bytes
    }
}
Hadrien Grasland (Oct 01 2019 at 19:26, on Zulip):

I think it doesn't, and my rationale is that "bytes" is moved out of the way by the initial transmute, and only "bytes_uc" remains. But I might be wrong.

Hadrien Grasland (Oct 01 2019 at 19:36, on Zulip):

For context, this is a dirty way to work around an unpleasant situation where 1/the borrow checker decides to borrow "bytes" forever, 2/I believe that this borrow lifetime choice is overly pessimistic for my use case, and 3/I do not manage to find a way to rephrase my API in such a manner that it doesn't do that.

Hadrien Grasland (Oct 01 2019 at 20:40, on Zulip):

OK... as it turns out, my actual API does not take an &'bytes mut [u8] but a generic S: DerefMut<Target=[u8]> + 'bytes, and this means that I can use UnsafeCell in a much more straightforward way which I'm pretty sure is correct:

pub fn less_evil<'bytes, S: DerefMut<Target=[u8]> + 'bytes>(bytes: S) -> S {
    unsafe {
        let bytes_uc = UnsafeCell::new(bytes);
        {
            let bytes = &'bytes mut [u8] = (*bytes_uc.get()).deref_mut();
            // ... do whatever horrible stuff is necessary without leaking references ...
        }
        bytes_uc.into_inner()
    }
}

So... problem solved, perhaps? Although I'm still interested in 1/API design tips to avoid perpetual borrows (thus removing the need for this unsafe trickery entirely), and 2/opinions on whether the above trick was UB or not. I might end up wanting to use it again someday...

HeroicKatora (Oct 01 2019 at 21:21, on Zulip):

Why are you more sure? DerefMut is a user trait that can call arbitrary code whereas the previous code block had effectively only pointer casts. UnsafeCell only covers S and not the dreferenced bytes. I'm still not sure why you'd need an UnsafeCell in the first place because that doesn't contain any conflicting borrows or other abominations The lifetime ascription let bytes: &'bytes mut [u8] looks wrong now, the type S lives at least that long but that doesn mean bytes does.

HeroicKatora (Oct 01 2019 at 21:48, on Zulip):

The comments also mention Clones and Copies of bytes but it does no such thing, it only creates new references to the very same bytes.
UnsafeCell is probably not the right tool for getting rid of borrow check, simply casting the reference to a pointer achieves the very same thing without that. I also don't get what rustc is supposedly complaining about in the first place. Here is your example without any UnsafeCell or any other unsafe in fact. This appears to have the exact same observable effects, in my eyes, and compiles just fine.
https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=49e0fc46352010e04f6e811c4e4f6c77
It may be an issue that your type ascriptions are too strong. For example, manually mentioning lifetime 'bytes forces the compiler to borrow the object for that whole lifetime, which actively sabotages any possible shorter lifetime that NLL may be able to assign to that reference.

RalfJ (Oct 09 2019 at 13:24, on Zulip):

Do you think that this evil trick triggers &mut aliasing UB?

for Stacked Borrows, lifetimes don't matter. so the innermost bytes having a longer lifetime does not matter, so I think under Stacked Borrows your first snippet is okay. did you try running it in Miri with a few input sizes?
but it does make me wonder why you need that "fake" long lifetime? certainly if any reference derived from that is used after the outer bytes gets created, you got UB. (not using the same variable name 3 times would make this code easier to discuss...)

RalfJ (Oct 09 2019 at 13:24, on Zulip):

@Hadrien Grasland ^

Hadrien Grasland (Oct 09 2019 at 16:46, on Zulip):

Whoops, for some reason zulip didn't send me a notification e-mail when I expected it to. Apologies, @HeroicKatora .

Hadrien Grasland (Oct 09 2019 at 16:48, on Zulip):

Anyhow, here's more context on what I'm trying to do.

Hadrien Grasland (Oct 09 2019 at 16:51, on Zulip):

Currently, Abomonation can only serialize types which own all of their data, such as bool or Box<T> where T: 'static. This limitation is artificial though: if we can serialize heap-allocated data, we can serialize stack references in exactly the same manner. As I recently ended up in a situation where being able to serialize a type which contains references would be convenient, I tried to implement Abomonation support for those.

Hadrien Grasland (Oct 09 2019 at 16:52, on Zulip):

...but then I found out an unpleasant truth which had been known in serde circles for a while: although _serializing_ data which contains references is fine, _deserializing_ such data must be done with care.

Hadrien Grasland (Oct 09 2019 at 16:56, on Zulip):

To see why, consider the following type, for example:

struct Foo<'y> {
    x: bool,
    y: &'y str,
}

Serializing a Foo<'y> of any lifetime is fine. Abomonation will just memcpy the Foo<'y>'s data into the target bytes, followed by a memcpy of the data of string y. So far, so good.

Hadrien Grasland (Oct 09 2019 at 17:00, on Zulip):

However, in-place deserialization of Foo<'y> from &'bytes mut [u8] is only fine if 'bytes: 'y, because during the deserialization process, Abomonation will overwrite Foo's y field to point to neighboring bytes in the serialized data. This means that Abomonation will actually put an &'bytes str where an &'y str is expected. Which is only safe (and therefore respectful of Rust's reference subtyping rules) when &'bytes str is strictly longer-lived than &'y str, i.e. 'bytes: 'y.

Hadrien Grasland (Oct 09 2019 at 17:02, on Zulip):

Which means that, for example, Abomonation should not allow deserialization of a Foo<'static> from stack-allocated bytes, because then the user could make a copy of _what rustc thinks of as a &'static str_, drop the bytes, and get a dangling reference.

Hadrien Grasland (Oct 09 2019 at 17:04, on Zulip):

Now, as mentioned before, this problem was already encountered by serde, and a fine solution was found there: bound the deserialization trait and function so that only memory-safe deserializations are allowed. This is the meaning of the 'de lifetime in serde's Deserialize<'de> trait, as explained here.

Hadrien Grasland (Oct 09 2019 at 17:09, on Zulip):

That design generally made sense in abomonation too, so I mostly reused it as-is, ending up with this deserialization function signature:

pub unsafe fn decode<'bytes, T: Exhume<'bytes>>(bytes: &'bytes mut [u8]) -> Option<(&'bytes T, &'bytes mut [u8])>

But then I encountered trouble while porting an abomonation feature which serde doesn't have, namely the Abomonated type.

Hadrien Grasland (Oct 09 2019 at 17:16, on Zulip):

You see, like any reference-based abstraction, abomonation deserialization has this problem that it's hard to move your deserialized data around in the program. One could try to use something like owning-ref in order to bring the serialized data and corresponding bytes together, but then one ends up with a self-referential type, which is Rust jargon for intense self-imposed pain.

Hadrien Grasland (Oct 09 2019 at 17:20, on Zulip):

As an alternative, abomonation provides built-in support for owned deserialized data in the form of the Abomonated type, which is essentially an owned slice of bytes that happens to contain a correct binary representation for a serialized type of a certain T, and implements a Deref<Target=T> that simply casts a pointer to the beginning to that slice of bytes into an &T.

Hadrien Grasland (Oct 09 2019 at 17:25, on Zulip):

(Now, the astute reader will have noticed that this actually cannot work with all "slice of bytes" types, because moving e.g. an [u8; N] will result in inner self-pointer invalidation. Well, that's why Abomonated's constructor is unsafe: we accept any DerefMut<Target=T>, but we actually would like to accept something more restrictive like owning-ref's StableDeref. Since Rust's stdlib has nothing of the sort at this point in time, we make the constructor unsafe and ask users to please not build an Abomonated out of those owned slices of bytes. Anyway, that's not the heart of the issue here...)

Hadrien Grasland (Oct 09 2019 at 17:38, on Zulip):

Now, before abomonation had reference support, Abomonated was defined like this...

pub struct Abomonated<T, S: DerefMut<Target=[u8]>> {
    phantom: PhantomData<T>,
    decoded: S,
}

...and its constructor was defined in an impl block that looked like this:

impl<T: Abomonation, S: DerefMut<Target=[u8]>> Abomonated<T, S> {
    // ... blah blah blah we'll eat your cat if S is an array blah blah blah
     pub unsafe fn new(mut bytes: S) -> Option<Self> {

...but now I have this 'bytes lifetime to take care of. Essentially, I must check that S lives long enough to make deserialization of a T from it sensible. This is what I ended up with:

impl<'bytes, T, S> Abomonated<T, S>
    where S: DerefMut<Target=[u8]> + 'bytes,
          T: Abomonation<'bytes>,
{

...where Abomonation<'bytes> is a supertrait of Exhume<'bytes> which also includes serialization (which TBH I currently don't need for Abomonated, Exhume<'bytes> would also work).

Hadrien Grasland (Oct 09 2019 at 17:40, on Zulip):

However, doing that effectively borrows bytes forever, which is how I ended up engaging in the kind of horrible borrow checker workarounds described earlier.

Hadrien Grasland (Oct 09 2019 at 17:42, on Zulip):

I tried various variants, including various variations of...

impl<'bytes, 'abo, S: DerefMut<Target=[u8]> + 'bytes, T: Abomonation<'abo>> Abomonated<T, S>

...but none could avoid the "slice borrowed forever" problem. And in the end, I convinced myself that this was an intrinsic defect of the kind of API that I had built for decode() above. For which I don't have a better idea...

Hadrien Grasland (Oct 09 2019 at 17:45, on Zulip):

Oh, well, now I'm taking a shortcut. Actually, there is one signature that almost got there, which used HRTBs...

impl<T, S: DerefMut<Target=[u8]>> Abomonated<T, S>
    where for<'abo> T: Abomonation<'abo> {

...but after a while, I realized that this excluded use of any type T that contains references with Abomonated which isn't terribly satisfying either.

Hadrien Grasland (Oct 09 2019 at 17:51, on Zulip):

In the end, what I am doing _is_ kind of fishy. After all, my bytes do end up containing self-referential deserialized data, even if rustc doesn't really know about that fact. Therefore, I'm not entirely surprised that building Abomonated entails working around the borrow checker to some degree.

Hadrien Grasland (Oct 09 2019 at 17:52, on Zulip):

OTOH, I'd like my workaround to be correct, and you seem to imply that it isn't yet. Need to think about it some more, then...

Hadrien Grasland (Oct 09 2019 at 18:09, on Zulip):

More generally, though, this decode() API redesign has been a source of pain in other areas, such as unit tests. Previously, the part of abomonation's unit tests that makes sure round trip serialization works used to look like this:

fn _test_pass<T: Abomonation+Eq>(record: T) {
    let mut bytes = Vec::new();
    unsafe { encode(&record, &mut bytes).unwrap(); }
    {
        let (result, rest) = unsafe { decode::<T>(&mut bytes[..]) }.unwrap();
        assert!(&record == result);
        assert!(rest.len() == 0);
    }
}

Take abomonable data, serialize it, deserialize it, and make sure that we get the same data. Simple enough.

However, in my PR for reference support, I had to change that test into this:

// FIXME: I could not find an API which allows _test_pass to allocate a Vec
//        internally without restricting the set of allowed Abomonation impls.
fn _test_pass<'bytes, T>(mut bytes: &'bytes mut Vec<u8>, record: T)
    where T: Abomonation<'bytes> + Debug + Eq
{
    unsafe { encode(&record, &mut bytes).unwrap(); }
    {
        let (result, rest) = unsafe { decode::<T>(&mut bytes[..]) }.unwrap();
        assert_eq!(&record, result);
        assert_eq!(rest.len(), 0);
    }
}

Notice that the test must now take a Vec as input, instead of being allowed to create said Vec internally. This is the only trick I've found to express an Abomonation trait bound that is compatible with reference-based types so far. Again, higher-ranked trait bounds would forbid testing of any type that contains references altogether...

Hadrien Grasland (Oct 09 2019 at 18:12, on Zulip):

Now, this specific change feels just wrong. There has to be a way to express the deserialization lifetime constraint of types that contain references, in a fashion that does not randomly break clients of decode(). But although I've been trying various things for a while, I have yet to find that way.

Hadrien Grasland (Oct 09 2019 at 18:29, on Zulip):

Hope that clarifies the situation. I've tried hard to provide reduced toy examples that avoid spelling out the full complexity of the problem, but it seems that people always end up wondering what's the problem when looking only at the reduced examples ;)

comex (Oct 10 2019 at 05:57, on Zulip):

Have you tried it in miri?

Hadrien Grasland (Oct 10 2019 at 06:19, on Zulip):

Miri's happy with the UnsafeCell-based version, as well as a different version that just creates two &mut [u8] to the same bytes without mem::forget-ing the first one before using the second one. I thought that was UB, but apparently it's not under Stacked Borrows / NLL.

RalfJ (Oct 10 2019 at 08:22, on Zulip):

Miri's happy with the UnsafeCell-based version, as well as a different version that just creates two &mut [u8] to the same bytes without mem::forget-ing the first one before using the second one. I thought that was UB, but apparently it's not under Stacked Borrows / NLL.

it is UB if the liveness ranges of the two references overlap

RalfJ (Oct 10 2019 at 08:23, on Zulip):

and as explained elsewhere, mem::forget on a reference is a bad idea. all it does is extend its liveness range because you are adding another "use"

RalfJ (Oct 10 2019 at 08:24, on Zulip):

@Hadrien Grasland you seem to be thinking along the lines of my 2017 "types as contracts" proposal, but that turned out to be unworkable. too complicated, and too much existing code it is not compatible with.

Hadrien Grasland (Oct 10 2019 at 10:06, on Zulip):

Miri's happy with the UnsafeCell-based version, as well as a different version that just creates two &mut [u8] to the same bytes without mem::forget-ing the first one before using the second one. I thought that was UB, but apparently it's not under Stacked Borrows / NLL.

it is UB if the liveness ranges of the two references overlap

Yes, and I am uneasy about that. I would really like to make it a compiler error to reuse the first reference after creating the second one, as opposed to silent UB that is only detected when running miri. If allowed, mem::forget would have allowed me to clarify that problem in the code.

RalfJ (Oct 10 2019 at 18:33, on Zulip):

you could try moving instead of reborrowing by adding some braces

RalfJ (Oct 10 2019 at 18:33, on Zulip):

{bytes} instead of bytes

Hadrien Grasland (Oct 10 2019 at 18:39, on Zulip):

May I ask for a slightly more fleshed out code example, starting from this base?

pub fn evil_foo<'bytes, T>(bytes: &'bytes mut [u8]) -> &'bytes mut [u8]
    where T: InPlaceDeserialize<'bytes>
{
    unsafe {
        let (ptr, len) = (bytes.as_mut_ptr(), bytes.len());
        // NOTE: I would like to make the original "bytes" unusable from here on
        //       to avoid accidental &mut aliasing with "bytes2"

        {
            let bytes2 = std::slice::from_raw_parts_mut::<'bytes, _>(ptr, len);
            deserialize2::<T>(bytes2);
        }

        std::slice::from_raw_parts_mut::<'bytes, _>(ptr, len)
    }
}
RalfJ (Oct 10 2019 at 18:41, on Zulip):

oh hm there's two uses...
well here's a "silly" solution: add let bytes = (); :P

RalfJ (Oct 10 2019 at 18:43, on Zulip):

shadowing FTW...

Hadrien Grasland (Oct 10 2019 at 18:48, on Zulip):

Nice trick, I could live with that!
(IIRC, that's also the trick used by that crate for stack pinning whose name I have forgotten, right?)

RalfJ (Oct 10 2019 at 18:50, on Zulip):

yeah, I've seen it before

simulacrum (Oct 10 2019 at 18:53, on Zulip):

you can also just do let bytes: (); maybe even without the () annotation -- that'll prevent all uses

simulacrum (Oct 10 2019 at 18:53, on Zulip):

though in this case it probably doesn't matter

Last update: Nov 19 2019 at 17:50UTC