[NLL] prohibit "two-phase borrows" with existing borrows?

@RalfJung

@RalfJung raised this example in which the "two-phase" borrow of x is compatible with a pre-existing share:

fn two_phase_overlapping1() {
    let mut x = vec![];
    let p = &x;
    x.push(p.len());
}

This poses a problem for stacked borrows, as well as for the potential refactoring of moving stacked borrows into MIR lowering (#53198) -- roughly for the same reason. It might be nice to change this, but -- if so -- we've got to move quick!

cc @arielb1 @pnkfelix

(It's actually not clear if we would want to backport this -- ideally we would, but it's probably a corner case.)

Nominated for discussion on the next T-lang meeting since this seems to a affect the type system in observable ways and because I'd like to understand this better... provided that we can wait until Thursday... ;)

I only have theoretical knowledge of NLL’s implementation but it seems extremely hard to forbid this…?

From what I hear it's actually easy, we just have an additional constraint that such that when the two-phase borrow starts, all existing loans for that ref get killed (like they usually would for a mutable ref).

The problem is the "fake read" desugaring we do to make sure that match arms cannot mutate the discriminee:

fn foo(x: Option<String>) {
  match x {
    Some(mut ref s) if s.starts_with("hello") => s.push_str(" world!"),
    _ => {},
  }
}

Becomes something like

_fake1 = &shallow x;
_fake2 = &(x as Some).0;
// switch on discriminant
s_for_guard = &mut2phase (x as Some).0;
s_for_guard_ref = &s_for_guard;
// guard, using *s_for_guard_ref instead of s
FakeRead(_fake1);
FakeRead (_fake2);
s = s_for_guard;
// Arm as usual

When s_for_guard is created, we create a new mutable ref to something that has outstanding shared refs.

@arielb1

I once proposed an alternative to this desugaring that avoids 2-phase-borrows. I was told (by @arielb1 and probably others) it doesn't work because it doesn't preserve pointer identity (if the guard compares addresses it'd notice), but I actually don't see why: I think all pointers are the same as in the desugaring above. Namely, we should do:

_fake1 = &shallow x;
_fake2 = &(x as Some).0;
// switch on discriminant
s_for_guard = &(x as Some).0;
s_for_guard_ref = fake_mut(&s_for_guard);
// guard, using *s_for_guard_ref instead of s
FakeRead(_fake1);
FakeRead (_fake2);
s = &mut (x as Some).0;
// Arm as usual

where fake_mut is

fn fake_mut<'a, 'b, T>(x: &'a &'b T) -> &'a &'b mut T {
  std::mem::transmute(x)
}

fake_mut is actually safe to call with any possible x. And the pointers are exactly the same as in the desugaring above. So why does this not work?

@RalfJung

@RalfJung

In this translation, addr_of(s_for_guard) != addr_of(s), while in the previous translation it can be. However, I'm not sure how important this property is, and in any case, addr_of(s_for_guard) != addr(s) today.

And if we really wanted to preserve this property, we could have s be a union between &T and &mut T.

However, I'm not sure how important this property is, and in any case, addr_of(s_for_guard) != addr(s) today.

Okay, so we agree that my proposal doesn't break more than what we currently do -- but it might be harder to fix (if we care).

And if we really wanted to preserve this property, we could have s be a union between &T and &mut T

It would however still be the case that the mutable reference was created after the guard runs, which could be observable in terms of Stacked Borrows / LLVM noalias.

@RalfJung

Okay, so we agree that my proposal doesn't break more than what we currently do -- but it might be harder to fix (if we care).

Sure enough. So I think @RalfJung's solution (having an &&mut T -> &&T transmute, 2 addresses for ref/ref mut bindings in guards, and 2-phase borrows rejecting existing borrows) is actually fine.

Auto merge of #58739 - matthewjasper:more-restrictive-tpb, r=<try>

Also see the tracking issue at #59159

Now that PR #58739 has landed, this is no longer P-high priority.

(I wouldn't call it "resolved" until we settle the question of what model we will end up using. But we may want to still close this issue and open a different one to track that work?)

In any case, re-prioritizing this as P-medium.

EDIT: Nvm, someone added the #[allow] exactly because of this and I am blind.^^ Srroy for the noise.

~~Are they really all prohibited? The following function is accepted, and this does look like an overlapping 2PB to me:~~

fn with_interior_mutability() {
    use std::cell::Cell;

    trait Thing: Sized {
        fn do_the_thing(&mut self, _s: i32) {}
    }

    impl<T> Thing for Cell<T> {}

    let mut x = Cell::new(1);
    let l = &x;

    #[allow(unknown_lints, mutable_borrow_reservation_conflict)]
    x
        .do_the_thing({
            x.set(3);
            l.set(4); // This is an example of overlapping 2PB! l was created before the implicit mutable borrow of x as receiver of this call.
            x.get() + l.get()
        })
    ;
}

@matthewjasper

FWIW, I was able to support the two-phase-borrows test cases with outstanding lones that @matthewjasper wrote in a refurbished version of Stacked Borrows (Miri PR: rust-lang/miri#695).

There'll be a blog post about this soon (TM). I am not sure if this is the model we want (in fact I think it is not, but for reasons mostly unrelated to two-phase borrows), and I have little idea of the consequences this will have on optimizations.

EDIT: The blog post is out

@Manishearth

@Manishearth discovered an intersting piece of code that was not accepted by Stacked Borrows 2.0:

fn unsafe_cell_2phase() { unsafe {
    let x = &UnsafeCell::new(vec![]); // Tag(0)
    // Stack: [0: SharedReadWrite]

    let x2 = &*x; // Tag(1)
    // Stack: [0: SharedReadWrite, 1: SharedReadWrite]

    (*x.get()).push(0); // The raw ptr returned by get: Tag(2)
    // Stack: [0: SharedReadWrite, 2: SharedReadWrite, 1: SharedReadWrite]
    // Then it gets two-phase-reborrows as a unique with Tag(3):
    // Stack: [0: SharedReadWrite, 2: SharedReadWrite, 3: Unique, 1: SharedReadWrite]
    // And then 3 gets reborrows as a "proper" unique with Tag(4)
    // Stack: [0: SharedReadWrite, 2: SharedReadWrite, 3: Unique, 4: Unique]

    // Now this is UB because x2's tag is not in the stack any more.
    let _val = (*x2.get()).get(0);
} }

I have annotated what happens with the stack. The issue is that we add the Unique tag "in the middle" of a bunch of existing SharedRW, and that's bad -- a block of consecutive SharedRW should be treated together, almost as if it was a single item.

I tried to fix this by supporting two-phase borrows "for real": I added a new TwoPhase kind of permission that, on the first write, turns into a Unique. I changed creating two-phase borrows such that the item gets added on top of a block of consecutive SharedReadWrite. That makes the above example pass. Unfortunately, it breaks another example involving two-phase borrows of interior mutable data (example courtesy of @matthewjasper):

fn with_interior_mutability() {
    use std::cell::Cell;

    trait Thing: Sized {
        fn do_the_thing(&mut self, _s: i32) {}
    }

    impl<T> Thing for Cell<T> {}

    let mut x = Cell::new(1);
    let l = &x;

    x
        .do_the_thing({
            x.set(3);
            l.set(4);
            x.get() + l.get()
        })
    ;
}

What happens here is that after creating the two-phase borrow, we end up with a stack like [x: Unique, x_for_do_the_thing: TwoPhase, l: SharedRW]. Then we do another (anonymous) shared reborrow for x (for x.set(3)), which gets added just above x, and we write to it, which kills x_for_do_the_thing and l because neither are part of the same block of consecutive SharedRW. I think @matthewjasper's scheme described above has the same problem.

The issue here is (and this kind of came up before already) that the stack just does not encode enough information about which pointer is derived from which. We'd want to know that l and x_for_do_the_thing are both direct children of x, such that adding more SharedRW-children does not affect any of the existing children (unless they are Unique).

So, for now I basically gave up and made two-phase borrows carry SharedRW permission. That's slightly better than the Raw proposal I made back with Stacked Borrows 1, because at least we still properly track the pointer and do not confuse it with raw pointers, but it does mean that you can read from the parent pointer even after the "activation point" (which is not a special point any more really) and still use the child two-phase pointer afterwards.

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)

Just a quick note: If we are still interested in gathering data about how much code was affected by adding the restriction to two-phase borrows, one source of data I had not considered is the set of commits that land that reference the lint's tracking issue #59159

(I count thirteen commits as of today that reference the lint issue.)

It won't be a complete list, of course, but it is a different data source than say crater.

Auto merge of rust-lang#96268 - jackh726:remove-mutable_borrow_reserv…

Navigation Menu

Repository navigation

[NLL] prohibit "two-phase borrows" with existing borrows? #56254

37 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

[NLL] prohibit "two-phase borrows" with existing borrows? #56254

Description

Activity

nikomatsakis commented on Nov 26, 2018

Centril commented on Nov 27, 2018

nagisa commented on Nov 27, 2018

RalfJung commented on Nov 28, 2018

RalfJung commented on Nov 28, 2018

arielb1 commented on Nov 28, 2018

RalfJung commented on Nov 28, 2018

arielb1 commented on Nov 28, 2018

37 remaining items

RalfJung commented on Mar 30, 2019

pnkfelix commented on Apr 11, 2019

RalfJung commented on Apr 15, 2019

RalfJung commented on Apr 17, 2019

RalfJung commented on May 19, 2019

Manishearth commented on May 20, 2019

pnkfelix commented on Jul 10, 2019

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions