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

[nikomatsakis]

@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 (https://github.com/rust-lang/rust/issues/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

[nikomatsakis]

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

[Centril]

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... ;)

[nagisa]

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

[RalfJung]

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.

[RalfJung]

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?

[arielb1]

@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.

[RalfJung]

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.

[arielb1]

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.

[pnkfelix]

seems best to be conservative (in terms of erring on the side of rejecting a larger set of sound programs) and do this now, if we can land a backportable patch in time for the edition.

(In other words, I'm in favor of moving forward on this proposal)

[pnkfelix]

triage: We discussed this in the NLL team meeting last night, and essentially decided that we think we will make a fix for this in the master branch without backporting it.

The main risk implied by that decision is that there may be 6 weeks of 2018 edition code that writes code similar to that of fn two_phase_overlapping that is subsequently outlawed by the subsequent version of Rust.

• However, we also think there will be some pressure to issue a point release after the initial release anyway. So it may not be a full 6 weeks of code that we have to deal with.
• Also, in case you thought that this case is rare in practice ... we discovered on PR #56301 the cruel irony that the new code to test the Stacked Borrows model was, unbeknownst to its author (@RalfJung), actually "fundamentally relies on the thing @RalfJung was suggesting to not allow"

[pnkfelix]

also, in terms of triage: I don't think we need to discuss this at the T-compiler meeting. It may or may not merit discussion at the T-lang meeting, given that WG-compiler-nll is planning to plug this hole; just not in a manner that we'd backport to beta...

[alexcrichton]

Removing from the 2018 edition milestone due to https://github.com/rust-lang/rust/issues/56254#issuecomment-442829785

[scottmcm]

Lang team discussion:

• Everyone seems fine with prohibiting this for now, though generally the the code was considered reasonable.
• There was some concern about details of the stability promise here, and thus whether it's justifyable to disable it once it's in a stable release.

[joshtriplett]

Is there some documentation of why exactly the model prohibits this, and what it would take to have a model that doesn't? Because in particular, it seems like you could have a region for p that ends after p.len() and then call x.push after that region ends.

[nikomatsakis]

I feel a bit torn. The fact that we see various bits of code using this makes me a bit reluctant to rule it out, and a bit more inclined to consider extending stacked borrows to account for it, though it depends on how big of a mess results. It'd be nice however to do that evaluation without time pressure, which is what gives me some incentive to want to rule it out -- and then see what it takes to allow it again.

[joshtriplett]

@nikomatsakis Likewise. I don't want to put anyone under pressure to cope with this, but I do think we ought to accept this code.

[RalfJung]

Is there some documentation of why exactly the model prohibits this, and what it would take to have a model that doesn't?

The basic model is described in this long blog-post of mine.

Model for Limited Two-Phase Borrows

The changes required to that model to support "limited two-phase borrows" (i.e., two-phase borrows that kill existing shared borrows when they are created) are trivial: When retagging for a two-phase borrow, we follow all the usual steps of retagging for a mutable borrow, and then we re-borrow the new borrow for a shared borrow. Done.

After let w = &2phase *v;, this means that I can read through both w and v (i.e., no "rewriting" that replaces v by w is required). The stack, roughly speaking, looks like [...; Uniq(v); Uniq(w); Shr]; frozen (I am abusing notation to avoid explicit timestamps). Reading through a mutable reference first checks if that reference still has a matching item on the stack (both of them do), and then it does not pop because reading from a frozen location does not require popping.

However, creating a mutable reference still acts like a "virtual write" to this location, which of course means that outstanding, existing borrows get killed. The reasoning for this is that after creating a mutable reference, we usually want to be sure that there are no aliases.

I have implemented this model (it is waiting for a PR to land), and it accepts this test-case. (The entire rest of the miri test suite does not seem to rely on two-phase borrows.)

Model for Unlimited Two-Phase Borrows

The problem with not killing existing shared borrows is that when the two-phase borrows is created, we cannot yet push it to the stack. It would have to "go below" the existing shared borrows so as to not invalidate them.

We could maybe put it directly above the item matching the borrow we re-borrow from. I don't like this for two reasons: First, it kills the stack discipline. Second, one can imagine several sound extensions of two-phase borrows (and indeed @arielb1 has imagined all of them^^) that this cannot scale to. For example, in this model, creating a new two-phase borrow would still have to kill outstanding two-phase borrows. Today it seems like you don't want to support this, but given that "it doesn't introduce UB in a naive translation to LLVM" seems to be a sufficient justification, I wouldn't be surprised if a year from now y'all come to me and said "uh, now we'd really rather like to support these other things as well" and then we have to re-design two-phase stacked borrows. ;)

I had another idea that should fix these problems. But I haven't had the time to implement it yet, so there may be unforeseen consequences. In this model, we add a new kind of "tag" that a pointer can carry: Beyond Uniq(Timestamp) and Shr(Timestamp), it can also carry TwoPhase { base: Timestamp, this: Timestamp }. Now we proceed as follows:

• When creating a two-phase borrow, we tag it with TwoPhase and record the timestamp of the borrow this is created from, as well as the current timestamp. We do not push a new item to the stack, and we act like a read through the mutable borrow we are created from. This keeps existing shared borrows alive.
• When reading through a two-phase borrow, we are happy finding a match for either of our two timestamps (or a Shr/frozen, that also always works).
• When writing through a two-phase borrow, we pop until the first of our two timestamps appears. If that is this, we are good. If that is base, we just found the activation point, and we push this.

This means that two-phase borrows delay the pushing of "their" item (the activation) to their first write (where a re-borrow to a "full" &mut counts as a write), which I think is the intention.

The downsides of this model are:

• Tags just got almost twice as big. If we ever want to have a valgrind implementation of this, that could become a serious issue. Valgrind currently supports up to twice as many bits of "metadata" attached to a value than the size of the value, so two ptr-sizes worth of a tag per ptr. We would have entirely used up this budget. From what I understand, this could be increased, but of course that comes at a performance cost. And even in miri, making pointers larger will increase the size of pretty much every data structure. There is a limit to how much complexity we can add to the model before checking it becomes infeasible, and I think checkability is a crucial requirement for any kind of UB we introduce (we should learn from C's mistakes instead of repeating them).
• While this model supports situations such as "creating two 2-phase-reborrows and only deciding at run-time which one to write through (invalidating the other)", it may not always behave in the most permissive way when creating a 2-phase-borrow from a 2-phase-borrow: In that case, we have to either require that the older 2-phase borrow be activated first (killing outstanding shared references at that point), or the younger 2-phase-borrow would actually "borrow" from the original mutable reference the older one comes from (meaning that after activating the younger 2-phase borrow, the older one may not ever be written to again), or we do something dynamic depending on whether the older 2-phase borrow has already been activated (which would likely mean, if it hasn't been activated yet it may never be activated). Mitigating this would require adding a "list of parents" to the tag of a 2-phase-borrow or storing that somewhere out-of-band. Keep in mind that the more complicated we make the extra state we add for this, the more difficult it will be to reason about it and to keep it in your head as you are writing unsafe code / compiler optimizations.

Extreme proposal

One issue I have here is that the only constraint for 2-phase-borrows seems to be "it must be sound in a naive memory model". This is in direct conflict with the expressed desire to have stronger invariants for references, that unsafe code must also follow. Are there any constraints in terms of optimizations you still want to perform, or invariants you still want to uphold, that would put another limit on how far 2-phase-borrows are supposed to go?

Just to map out the design space a bit, here's a really extreme proposal that essentially gives up on tracking for 2-phase borrows: A 2-phase-borrow is just a copy of the mutable reference it is created from. This means that after let w = &2phase *v;, Stacked Borrows would treat v and w as equivalent, and unsafe could would be allowed to perform interleaved accesses through these pointers:

let w = &2phase *v;
let vraw = v as *mut _; // let's assume this wouldn't reborrow, but just cast
let wraw = w as *mut _; // let's assume this wouldn't reborrow, but just cast
// Now this is okay, as both pointers carry the same tag
*vraw = 4;
*wraw = 5;
*vraw = 6;
*wraw = 7;

The borrow checker would still have to impose some restrictions (writing to w could invalidate v if that points into an enum variant, for example), but 2-phase-borrows (better called "aliasing mutable borrows" at this point) would not be subject to any restrictions from Stacked Borrows.

I have not implemented this model, but I think it would be feasible. Of course, this would maximally pessimize compiler transformations as the two pointers would now indeed be allowed to alias. But that's what you get if you don't want to impose any limitations on how far 2-phase borrows should go :)

[pnkfelix]

T-compiler triage: I am planning on taking point on this during this week.

[pnkfelix]

T-compiler triage: No movement in last week because I was distracted by other NLL stuff.

[nikomatsakis]

I'm trying to decide how to move forward here. It's clear that there is no consensus as to whether or not to accept or reject this pattern yet -- @joshtriplett has expressed a clear desire to accept it, on the general basis of "it seems like code that people write and is not naively harmful". On the other hand, @RalfJung has made a case for rejecting it. That case is largely predicated on the complexity resulting from trying to model this pattern in the "stacked borrows" and unsafe code guidelines proposal. Both of these seem like strong arguments to me.

Additionally, there are fair amount of unknowns here. For one thing, the "stacked borrows" model itself is somewhat in its "infancy". Maybe we'll come up with a good way to model this in stacked borrows, or maybe we'll make some other changes to stacked borrows in the meantime. It's sort of hard to assess the impact on optimizations / unsafe code author "mental models" at this point I think. We also don't really know how common this pattern is in practice yet.

This seems to suggest that it would be prudent to adopt a future proof approach, where we reject this pattern but keep alive a desire to evaluate how it would be accepted in two-phase borrows.

I think this is not that difficult to implement, it probably requires two PRs:

• One to refactor so that match desugaring no longer uses 2PB at all.
• Then another to reject starting a 2PB when there are live, pre-existing shared borrows.

Would everyone be ok with that? I'm trying to decide how much work that first refactoring is, since that is the main job here, and in some sense it may be "wasted work" if we wind up accepting the pattern now.

I'm tempted to say we should try it and at least do a crater run though.

[nikomatsakis]

Some discussion on Zulip about implementation details of the refactoring.

[Centril]

@nikomatsakis

I'm trying to decide how to move forward here. It's clear that there is no consensus as to whether or not to accept or reject this pattern yet -- @joshtriplett has expressed a clear desire to accept it, on the general basis of "it seems like code that people write and is not naively harmful".

My desire for accepting it is that I believe that it fits with people's mental model that let-expansion or let-reduction should be possible without having any effects either on static or dynamic semantics. This isn't always true, but trying to lessen the number of cases where it isn't helps to make the language feel smoother and easier to learn.

This seems to suggest that it would be prudent to adopt a future proof approach, where we reject this pattern but keep alive a desire to evaluate how it would be accepted in two-phase borrows.

I think this is not _that_ difficult to implement, it probably requires two PRs:

• One to refactor so that match desugaring no longer uses 2PB at all.

• Then another to reject starting a 2PB when there are live, pre-existing shared borrows.

Would everyone be ok with that? I'm trying to decide how much work that first refactoring is, since that is the main job here, and in some sense it may be "wasted work" if we wind up accepting the pattern now.

I'm tempted to say we should try it and at least do a crater run though.

I do think this is the right approach; tho I would suggest turning point 2) into "reject + factor into a feature-gate" so that we can experiment with a world where let-expansion does work. Since I don't know how feasible that is, I leave that merely as a point for consideration.

[nikomatsakis]

tho I would suggest turning point 2) into "reject + factor into a feature-gate" so that we can experiment with a world where let-expansion does work. Since I don't know how feasible that is, I leave that merely as a point for consideration

Yes, I am happy with that compromise.

[RalfJung]

My desire for accepting it is that I believe that it fits with people's mental model that let-expansion or let-reduction should be possible without having any effects either on static or dynamic semantics. This isn't always true, but trying to lessen the number of cases where it isn't helps to make the language feel smoother and easier to learn.

I don't even consider this example (on the original post here) to be let-expansion. Rust is a language where multiple uses of the same variable make a difference, and that example replaced some of the uses of x by p -- IMO if your intuition says that this should be okay, then your intuition does not take into account the linear nature of Rust.

---

For one thing, the "stacked borrows" model itself is somewhat in its "infancy". Maybe we'll come up with a good way to model this in stacked borrows, or maybe we'll make some other changes to stacked borrows in the meantime.

Fully agreed. One thing I have been wondering about is whether there is a good way to make the model less aggressive about "creating a reference is like a memory access". That rule also causes other problems, like around raw reborrows and around custom DSTs. We might also want to use some less aggressive tracking like that for raw pointers to fix @arielb1's example where Stacked Borrows is still too weak for noalias.

OTOH, relaxing that rule has entirely unknown effects on which optimizations we can perform, and I felt it's best to start with as much UB as possible since it's always easier to make fewer things UB later.

---

I am particularly curious what y'all think about my last suggestion (the "extreme proposal" above), to essentially give up on alias tracking for two-phase borrows because the goal anyway is to accept as much code as possible. That's actually not a very complicated model, and I think it accepts all code anybody has ever proposed to accept as part of 2PB and more, but it also maximally pessimizes potential optimizations.

[pnkfelix]

triage: put myself back on assignee list to try to ensure I get back on board here

[pnkfelix]

visiting for T-compiler triage. @matthewjasper has done epic prep work in PR #57609. Once that's finished, we'll be in an appropriate position to implement this.

[matthewjasper]

@RalfJung

We _could_ maybe put it directly above the item matching the borrow we re-borrow from.

This doesn't seem to be as bad as you're saying. Just to be clear, what is your objection to the following, apart from being ad hoc.

The actual change that we need (for now) is that creating a two-phase borrow doesn't unfreeze the stack if it does not pop anything else from it. So if we create a two-phase borrow with tag 10 at timestamp 100, from a unique reference with tag 2 the stack changes:

[Uniq(2); Uniq(4); Shr]; unfrozen -> [Uniq(2); Uniq(10)]; frozen(100)
[Uniq(2)]; frozen(50) -> [Uniq(2), Uniq(10)]; frozen(50)
[Uniq(2); Uniq(4); Shr]; frozen(50) -> [Uniq(2); Uniq(10)]; frozen(100)

Then when we activate the two-phase borrow (which always moves it at the moment):

[Uniq(2); Uniq(10)]; frozen -> [Uniq(2); Uniq(10); Uniq(11)];
[Uniq(2); ..]; -> ERROR

[RalfJung]

That doesn't entirely work because if there is an UnsafeCell, there'll be a Shr on the stack that we have to preserve. Your suggestion relies on all Shr being the same, but @arielb1 keeps reminding me that we cannot keep it like that forever.

[matthewjasper]

Model for Unlimited Two-Phase Borrows

Tags just got almost twice as big.

Mitigating this would require adding a "list of parents" to the tag of a 2-phase-borrow or storing that somewhere out-of-band.

So I've thinking if there's a way to do this that avoids these problems, before I give up and admit that our choice is between minimal two-phase borrows and transmute_copy two-phase borrows.

Instead of storing the base in the tag we instead store it on the stack, below the item for the two-phase borrow. More precisely, we add variants

TwoPhase(Timestamp), // Maybe this could be merged with a future Shr(Timepstamp) item
Activates(Timestamp),

When we create a two-phase borrow with tag Uniq(t) (maybe this should be TwoPhase(t), but it doesn't really affect much) from a reference with tag Uniq(u)* we push Activates(u), TwoPhase(t) on to the stack.

When we write through a two-phase borrow, if we find a TwoPhase(t) on the stack, we pop it, check the next item, which must be an Activates(u), then pop until Uniq(u) is on top of the stack, then push Uniq(t)** onto the stack.

• We can also create a two-phase borrow from a raw pointer, in with case I guess there can be an ActivatesShared stack item until Shr items get timestamps back.
  ** Currently the only activations of two-phase borrows are from retags, and we never use a two-phase borrow after it's activated, so this isn't needed for now.

[RalfJung]

So basically you are saying we should give up on the stack discipline, push stuff into the middle of the stack to remember where the activation is?

You are saying "push Activates(u), TwoPhase(t) on to the stack", but it if gets pushed to the top I do not see how this encodes the necessary information.

[matthewjasper]

No, it goes on the top (except for the freeze). The necessary information is "the items on the stack that were on the stack when we created the two-phase borrow are still there", and what borrow we came from (so that we know what to remove when we activate the two-phase borrow).

[RalfJung]

Uh. I see.

As a first gut-level reaction I have to say I think I prefer violating the stack discipline.^^

[RalfJung]

Also see the tracking issue at https://github.com/rust-lang/rust/issues/59159

[pnkfelix]

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.

[RalfJung]

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()
        })
    ;
}

[RalfJung]

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: https://github.com/rust-lang/miri/pull/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

[RalfJung]

@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.

[Manishearth]

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)

[pnkfelix]

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.