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

Topic: safety of stable containers


Manish Goregaokar (May 14 2019 at 20:41, on Zulip):

@RalfJ Hi, I just miri-checked the elsa crate. It provides FrozenMap and FrozenVec using StableDeref: i.e. these are collections you can push to while holding references to their elements, because they give you references to their dereffed elements: a FrozenMap<String> will give you &str (which will not change on .push())

My mutable_arena example fails miri: https://github.com/Manishearth/elsa/blob/master/examples/mutable_arena.rs#L56 (miri doesn't support examples yet, move it in tree and turn it into a binary)

I get this error: https://gist.github.com/Manishearth/0b053abd89fa3ad92ad00a8118923491

Talking to @eddyb it seems like the issue is that this creates an &mut Vec<T> from the unsafecell while holding on to &T::Derefs obtained from the vec. This is supposed to be safe here because the T::Derefs are stored behind an allocation, so we're not actually borrowing the vec itself, and Vec::push does not touch these elements.

Is this the UB here? What's the solution moving forward for stable containers then? They're a pretty crucial thing for caching and stuff, and the alternative is basically to implement bespoke collections each time.

RalfJ (May 14 2019 at 21:00, on Zulip):

@Manish Goregaokar without having seen the details yet (hopefully I will have some time for that tomorrow), this sounds like a duplicate of this problem to me. Basically, this is currently UB:

fn main() {
    let mut v = Vec::with_capacity(10);
    v.push(0);
    let v0 = unsafe { &mut *(&mut v[0] as *mut _) }; // laundering the lifetime -- we take care that `v` does not reallocate, so that's okay.
    v.push(1);
    let _val = *v0;
}

We should probably have an issue about this.

RalfJ (May 14 2019 at 21:03, on Zulip):

even this weaker form is UB, for the same reason:

fn main() {
    let mut v = Vec::with_capacity(10);
    v.push(0);
    let v0 = unsafe { &*(&v[0] as *const _) }; // laundering the lifetime -- we take care that `v` does not reallocate, so that's okay.
    v.push(1);
    let _val = *v0;
}

Vec::push currently creates a mutable ref covering all elements, which invalidates all previously created interior pointers.

Manish Goregaokar (May 14 2019 at 21:05, on Zulip):

@RalfJ similar, but not quite

Manish Goregaokar (May 14 2019 at 21:07, on Zulip):

What we're doing is this:

 let mut v = Vec::new();
v.push(Box::new(1));
 let v0 : &u32 = unsafe { &*(&*v[0] as *const u32) };
v.push(Box::new(1));
let val = *v0;
Manish Goregaokar (May 14 2019 at 21:08, on Zulip):

As in, we're relying on the fact that Vec::push does not change anything except for moving the inline values (but not any allocations)

Manish Goregaokar (May 14 2019 at 21:08, on Zulip):

But yes from a UB guidelines pov this is probably similar

Alan Jeffrey (May 14 2019 at 21:10, on Zulip):

@Manish Goregaokar does reasoning about the correctness of FrozenVec and friends need reasoning about the StableDeref invariantas?

Alan Jeffrey (May 14 2019 at 21:11, on Zulip):

if so, it might be difficult to persuade Miri that FrozenVec is OK :/

RalfJ (May 15 2019 at 08:17, on Zulip):

As in, we're relying on the fact that Vec::push does not change anything except for moving the inline values (but not any allocations)

Hm. Your example code is accepted by Miri though, as I would have expected.

RalfJ (May 15 2019 at 08:18, on Zulip):

@Alan Jeffrey why that? Of course Miri cannot show that any possible interaction is okay, but a concrete execution should be UB-free if the abstraction is correct.

RalfJ (May 15 2019 at 08:20, on Zulip):

@Manish Goregaokar FWIW, that data structure reminds me of https://github.com/rust-lang/miri/blob/master/src/mono_hash_map.rs ^^

RalfJ (May 15 2019 at 08:26, on Zulip):

self-contained example: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=f07c6c9021435fc52dd67827635b1370
(not a safe API any more but that shouldnt matter when looking at a concrete execution)

RalfJ (May 15 2019 at 09:20, on Zulip):

the reference/pointer in question points to the Vec itself, not its contents or so

RalfJ (May 15 2019 at 09:37, on Zulip):

oh... this is interesting. seems to be some bad interaction with what I do for 2-phase borrows.

RalfJ (May 15 2019 at 09:39, on Zulip):

I think this is the same issue:

use std::cell::UnsafeCell;

fn main() { unsafe {
    let x = &UnsafeCell::new(vec![]);
    let x2 = &*x;
    (*x.get()).push(0);
    let _val = (*x2.get()).get(0);
} }
RalfJ (May 15 2019 at 09:41, on Zulip):

Cc @Matthew Jasper

RalfJ (May 15 2019 at 09:42, on Zulip):

specifically, this does a two-phase borrow from a raw pointer, which I did not think was a thing

RalfJ (May 15 2019 at 09:43, on Zulip):

and so there are a bunch of SharedReadWrite that can all happily coexist, but the 2phase-borrow now adds a Unique right in the middle of them, which means the ones further up get invalidated once the two-phase borrow gets activated.

RalfJ (May 15 2019 at 09:46, on Zulip):

confirmed, removing the thing that supports two-phase borrows with outstanding shared references fixes my self-contained version of the elsa testcase

RalfJ (May 15 2019 at 10:04, on Zulip):

lol, I literally had this as a comment in the code:

        // TODO: With `two_phase == true`, this performs a weak reborrow for a `Unique`. That
        // can lead to some possibly surprising effects, if the parent permission is
        // `SharedReadWrite` then we now have a `Unique` in the middle of them, which "splits"
        // them in terms of what remains valid when the `Unique` gets used.  Is that really
        // what we want?

Now I know the answer: no, it is not what we want. ;)

Alan Jeffrey (May 15 2019 at 14:09, on Zulip):

@RalfJ true, the StableDeref invariants are only needed for proving that all safe uses of FrozenVec have defined behaviour, not a particular concrete execution.

Manish Goregaokar (May 15 2019 at 14:53, on Zulip):

@Alan Jeffrey yes, but only to the extent that a particular impl of StableDeref should be used in a safe way

Manish Goregaokar (May 15 2019 at 14:54, on Zulip):

Like, if StableDeref is a problem so is every other unsafe trait

Manish Goregaokar (May 15 2019 at 15:03, on Zulip):

@RalfJ sorry, I'm a bit ignorant about the internals of this: does this mean the Elsa test case is fine?

Manish Goregaokar (May 15 2019 at 15:03, on Zulip):

And it's Miri that needs patching?

Manish Goregaokar (May 15 2019 at 15:04, on Zulip):

And yep! Your self contained test case is exactly what we're doing

RalfJ (May 15 2019 at 15:18, on Zulip):

it does mean that this particular error is not Elsa's fault but Miri's.

RalfJ (May 15 2019 at 15:19, on Zulip):

thanks for posting this! the only way to get decent test coverage here is to crowdsource that stuff, so I am happy to see this work :D

RalfJ (May 15 2019 at 15:19, on Zulip):

but also this will keep me and my colleague busy for a bit while we update the implementation, documentation, formalization and proof ;)

Matthew Jasper (May 15 2019 at 16:41, on Zulip):

specifically, this does a two-phase borrow from a raw pointer, which I did not think was a thing

Well the borrow kind is marked as two-phase, but the borrow checker doesn't track the borrow (i.e. it's treated as just a read/write).

RalfJ (May 19 2019 at 12:03, on Zulip):

@Manish Goregaokar the fixed Miri just landed in rustc, so if you could try again with the next nightly (tomorrow), that'd be great.

Manish Goregaokar (May 19 2019 at 16:35, on Zulip):

Thank you!! Will do.

RalfJ (May 21 2019 at 08:40, on Zulip):

@Manish Goregaokar

Nightly miri now passes all of the elsa tests except for sync.rs (which uses threads, which miri doesn't like because of the dynamic loading)

awesome! Notice that threads are also themselves unsupported, the interpreter machine just has no concept of there being more than 1 stack.

RalfJ (May 21 2019 at 08:41, on Zulip):

if you want to have Miri as part of your CI, I can help make that happen :)

Manish Goregaokar (May 21 2019 at 14:34, on Zulip):

@RalfJ miri needs an --example argument for that :)

RalfJ (May 21 2019 at 14:35, on Zulip):

oh, these are not testcases?

RalfJ (May 21 2019 at 14:36, on Zulip):

hm. our cargo wrapper already is a mess :( we should somehow reuse cargo's way of selecting which binaries to build/run...

RalfJ (May 21 2019 at 14:38, on Zulip):

I just opened an issue for this: https://github.com/rust-lang/miri/issues/739

RalfJ (May 21 2019 at 14:38, on Zulip):

we could really use some help here :D

Manish Goregaokar (May 21 2019 at 17:57, on Zulip):

@RalfJ I wanted to patch that but your arg parsing is kinda a mess lol

Manish Goregaokar (May 21 2019 at 17:57, on Zulip):

(not necessarily blaming you, it's fine for the purpose it serves, it's just hard to extend)

Manish Goregaokar (May 21 2019 at 17:57, on Zulip):

Might fix it anyway later

RalfJ (May 21 2019 at 17:58, on Zulip):

arg parsing is kinda a mess

that's putting it kindly^^

RalfJ (May 21 2019 at 17:59, on Zulip):

but it clearly does need a rewrite, not an extension

RalfJ (May 21 2019 at 18:00, on Zulip):

and you can blame me, you wouldn't be entirely wrong. ;) I didn't start it, but I went down a route of arg parsing that I knew was wrong. my only excuse is that I care a lot about the semantics Miri implements, and wanted to just get the rest done quickly.

Manish Goregaokar (May 21 2019 at 18:03, on Zulip):

Maybe I'll just swap in clap

Manish Goregaokar (May 21 2019 at 18:03, on Zulip):

That's not easy either, miri also takes in normal rustc args I think

RalfJ (May 21 2019 at 18:07, on Zulip):

yeah... the general form is cargo miri <optional verb> <args for the cargo wrapper> -- <args for the miri driver, which includes rustc args> -- <args for the application being run>

RalfJ (May 21 2019 at 18:08, on Zulip):

so we'd only want to use clap until the first --, and leave the rest uninterpreted. is that possible?

Last update: Nov 19 2019 at 17:50UTC