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

Topic: stacked borrows violation in slice iterators

RalfJ (Oct 29 2018 at 12:57, on Zulip):

Finally I found a stacked borrows violation :D was about time. iter_mut for slices is UB according to my model.

RalfJ (Oct 29 2018 at 12:58, on Zulip):

concretely, when len is called on, that activates self, which -- being a unique reference -- invalidates the previously created raw ptr

RalfJ (Oct 29 2018 at 12:58, on Zulip):

(please don't git blame that code or it'll say that I wrote it^^ but in my defense, the previous code had the same problem)

RalfJ (Oct 29 2018 at 13:01, on Zulip):

we could make this legal by saying that a borrow from which you reborrow just has to be reactivatable, but doesnt get reactivated

RalfJ (Oct 29 2018 at 13:05, on Zulip):

I like this because it replaces a special case during reborrowing.

kennytm (Oct 29 2018 at 13:17, on Zulip):

it is really a violation? the self here is a DST &mut [T] which in memory is a (*mut T, usize) pair, and calling len() shouldn't really touch the data pointer part at all

RalfJ (Oct 29 2018 at 13:34, on Zulip):

@kennytm fat references are considered a primitive

RalfJ (Oct 29 2018 at 13:35, on Zulip):

I think it would be strange if &[T; 3] was properly tracked but &[T] was not

RalfJ (Oct 29 2018 at 13:42, on Zulip):

so when &mut [T] is coerced to &[T], that's a "use" of the src reference, and the destination of that reference (the place it denotes) is the entire slice

RalfJ (Oct 29 2018 at 15:17, on Zulip):

with this, the following is now allowed (used to be a compile-fail test):

fn test(r: &mut RefCell<i32>) {
    let x = &*r; // not freezing because interior mutability
    let mut x_ref = x.borrow_mut();
    let x_inner : &mut i32 = &mut *x_ref; // Uniq reference
    let x_evil = x_inner as *mut _;
        let x_inner_shr = &*x_inner; // frozen
        let y = &*r; // outer ref, not freezing
        let x_inner_shr = &*x_inner; // freezing again
    // Our old raw should be dead by now
    unsafe { *x_evil = 0; } // this falls back to some Raw higher up the stack
    *x_inner = 12; //~ ERROR Mut reference with non-reactivatable tag

fn main() {
    test(&mut RefCell::new(0));
RalfJ (Oct 29 2018 at 15:17, on Zulip):

basically, shared reborrowing from x_inner no longer reactivates x_inner, so x_evil is still usable

RalfJ (Oct 29 2018 at 15:18, on Zulip):

reasoning being basically that "shared reborrow" doesnt mean nobody else has stuff. any actual use of x_inner would still invalidate x_evil, of course.

RalfJ (Oct 29 2018 at 16:12, on Zulip):

but this has other conseqeuences... we now allow this:

// A callee may not read the destination of our `&mut` without
// us noticing.

fn main() {
    let mut x = 15;
    let xraw = &mut x as *mut _;
    let xref = unsafe { &mut *xraw }; // derived from raw, so using raw is still okay...
    let _val = *xref; // ...but any use of raw will invalidate our ref.

fn callee(xraw: *mut i32) {
    // We are a bit sneaky: We first create a shared ref, exploiting the reborrowing rules,
    // and then we read through that.
    let shr = unsafe { &*xraw };
    let _val = *shr;
RalfJ (Oct 29 2018 at 16:13, on Zulip):

which is a problem because it means that &mut actually doesnt mean nobody else can access this memory; it only means nobody else can write to this memory. reads would be allowed.

RalfJ (Oct 29 2018 at 16:27, on Zulip):

@nikomatsakis so we pretty much have to either make iter_mut UB, or we cannot rule out reads from locations we have &mut to

nikomatsakis (Oct 29 2018 at 16:52, on Zulip):

I'll have to re-read this about 22 times probably but @RalfJ something I am wondering about is:

In your original example, the call to self.len() "just" accesses the len field (ultimately).

I guess part of the problem is that the fns are not inlined?

nikomatsakis (Oct 29 2018 at 16:53, on Zulip):

This is of course a somewhat common course of "spurious" borrow-check errors too -- that is, having some &self or &mut self method that only accesses one or two fields -- but you can't call it because you have outstanding borrows of some other fields.

Nicole Mazzuca (Oct 29 2018 at 18:08, on Zulip):

I want to make iter_mut UB, to be honest. They should be storing len in the same place they store ptr

Nicole Mazzuca (Oct 29 2018 at 18:09, on Zulip):

I feel like allowing this will have unintended consequences with interior mutability, although I can't think of anything right now.

Jake Goulding (Oct 29 2018 at 18:14, on Zulip):

make iter_mut UB

I assume this means the current implementation of it, not... the entire concept, right?

Nicole Mazzuca (Oct 29 2018 at 18:38, on Zulip):

yes lol :P

RalfJ (Oct 29 2018 at 18:43, on Zulip):

@nikomatsakis yes the problem is that a reborrow-to-shr behaves like a read (and then initiating the new ref) -- a principle which sounds so nice I'd like to keep it. :D so this is "using" self (reading from it), which invalidates all borrows derived-from self, including ptr.

RalfJ (Oct 29 2018 at 18:44, on Zulip):

@Nicole Mazzuca I do not see the connection to interior mutability, but the problem I see is that we have to prevent people from reading locations we have the exclusive access to

RalfJ (Oct 29 2018 at 18:45, on Zulip):

and I have not yet found a set of rules that would do that, and allow this code

Nicole Mazzuca (Oct 29 2018 at 18:58, on Zulip):

all it requires is to put the call to len in the right place

Nicole Mazzuca (Oct 29 2018 at 18:58, on Zulip):

@RalfJ right, interior mutability allows mutating through a read-only pointer, tho. Assume it's an &mut [Cell<T>] - then .len() is also allowed to mutate the actual elements as well

RalfJ (Oct 29 2018 at 18:58, on Zulip):

hm... we could say that it is okay to read through a mut ptr (without activating it) if "on top of it" in the stack, all we have is raw and frz entries.

RalfJ (Oct 29 2018 at 18:58, on Zulip):

@Nicole Mazzuca sure, but with interior mutability we do much less precise tracking anyway

Nicole Mazzuca (Oct 29 2018 at 19:00, on Zulip):

@RalfJ now, sure. in the future, I'd like to have much more tracking, especially with &mut pointers

RalfJ (Oct 29 2018 at 19:00, on Zulip):

but hm I think I see what you mean... if we allow this ref to be created even though there is a raw above it, then later when someone writes all we see is a raw at the top, and it is okay to write to an unfrozen raw

RalfJ (Oct 29 2018 at 19:00, on Zulip):

oh &mut doesnt care about interior mutability. only & does.

RalfJ (Oct 29 2018 at 19:01, on Zulip):

the question, I guess, is if that is a problem

Nicole Mazzuca (Oct 29 2018 at 19:01, on Zulip):

right, but if you allow going from &mut -> & while stacking borrows...

nikomatsakis (Oct 29 2018 at 19:03, on Zulip):

@RalfJ very interesting. Particularly since I would very much like to lift this limitation of the borrow checker at some point (so that you can have some way to declare — or maybe infer? — what fields a given reference can be used to access). In any case, it sort of "makes sense" that this code would be illegal when you look at it from that angle (since the borrow checker would reject), but it may be a common pattern in practice.

RalfJ (Oct 29 2018 at 19:03, on Zulip):

why would len writing be a problem? self would "know" about it because the ref used to write is derived-from self, and ptr is raw so it cannot care about others writing.

Nicole Mazzuca (Oct 29 2018 at 19:04, on Zulip):

@RalfJ I'm not saying it is an issue, I'm just saying I'd be worried about it being an issue.

RalfJ (Oct 29 2018 at 19:29, on Zulip):

ah, none of what I thought of will work

RalfJ (Oct 29 2018 at 19:29, on Zulip):

because there are some more reborrows

RalfJ (Oct 29 2018 at 19:31, on Zulip):

concretely, calling as_mut_ptr reborrows self, creating some new unique borrows. the Raw then gets derived from them. I cannot think of any reasonable way in which we allow using self to create a new borrow without invalidating those exclusive reborrows, which would be a fundamental departure from the stack discipline.

RalfJ (Oct 29 2018 at 19:37, on Zulip):

in particular, for these Uniq items on the stack that we would be "skipping", there might be someone relying on their ref being, well, unique. So allowing this kind of code is fundamentally incompatible with optimizations based on the assumption "nobody else can even read from my &mut".

nikomatsakis (Oct 29 2018 at 21:13, on Zulip):

I can see why, yes, very interesting

RalfJ (Oct 30 2018 at 07:54, on Zulip):

hm, interestingly though this can happen even in safe code... with the infamous "you can reborrow the same &mut to & many times"...

RalfJ (Oct 30 2018 at 07:54, on Zulip):

that, combined with the fact that most uses of an &mut are actually a reborrow, makes it so that there are other Uniq on the stack, I just failed to check for them in my implementation so far

RalfJ (Oct 30 2018 at 07:54, on Zulip):

so what I considered the "most permissive approach" doesnt even accept all safe code

RalfJ (Oct 30 2018 at 14:45, on Zulip):

okay I understood where my mistake was about accepting all that safe code. iter_mut is still a problem though.

RalfJ (Oct 30 2018 at 14:46, on Zulip):

I found something that accepts iter_mut, but it's a rather bad hack: When we do a read, and we have to pop stuff from the stack, instead of popping all of it was just pop the Uniq. I think that maintains the exclusivity guarantee we want. However, it means we do not actually have follow a stack discipline any more.

nikomatsakis (Oct 30 2018 at 15:20, on Zulip):

okay I understood where my mistake was about accepting all that safe code. iter_mut is still a problem though.

so safe code is ok now? :)

RalfJ (Oct 30 2018 at 15:20, on Zulip):

the one in the test suite is, anyway ;)

RalfJ (Oct 30 2018 at 15:21, on Zulip):

and iter_mut is, well, okay-ish. I don't like the fact that we no longer have a stack.

RalfJ (Nov 05 2018 at 15:06, on Zulip):

I re-did a large chunk of the model, though the core stayed the same, fixing "partially interior mutable data" at Interestingly that also fixed slice iterators. I still have to understand how and why.

RalfJ (Nov 07 2018 at 18:11, on Zulip):

The thing that makes this possible is the implementation of the following rule, which subsumes a bunch of previous rules for handling the "mut can be shared multiple times" situation: When reading, if you are using a ptr with a Uniq tag, and if that tag is in the stack, then we only have to push until the next shared tag, not until the Uniq tag.

RalfJ (Nov 07 2018 at 18:11, on Zulip):

In this case, this means that after leaking the &mut to raw, if we then create a shared reference from the &mut, that just reactivates the raw (which is already active). So the code is legal.

RalfJ (Nov 07 2018 at 18:18, on Zulip):

The reason this is okay is that popping the stack on reactivate is for the benefit of arguing that Uniq is unique: If any other reference was used or created, that would pop us off the stack first. But this is not in conflict with this new special rule, because that rule only helps if there already are Shr tags on top of the Uniq in the stack.

RalfJ (Nov 07 2018 at 18:29, on Zulip):

previously this was somewhat more asymmetric; if the location was frozen we would have an exception like that but if it just was shared for other reasons, we would not

Last update: Jul 02 2020 at 12:45UTC