rust-lang / rust-lang/rust

ReferencePropagation introduces UB into code that is accepted by Stacked Borrows

Open
#132,898 10 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

A-mir-opt C-bug E-needs-investigation I-miscompile T-compiler WG-mir-opt
Dominant language
Rust
Stars
119k
Forks
16.1k
PR merge metrics
PR metrics pending

Description

This program is accepted by Stacked Borrows:

fn main() {
    struct Foo(u64);
    impl Foo {
        fn add(&mut self, n: u64) -> u64 {
            self.0 + n
        }
    }

    let mut f = Foo(0);
    let alias = &mut f.0 as *mut u64;
    let res = f.add(unsafe {
        *alias = 42;
        0
    });
    assert_eq!(res, 42);
}

That is a Stacked Borrows limitation; it is caused by the fact that 2-phase borrows cannot be modeled properly with just a Stack.
However, it also shows that defining an aliasing model that rejects this code is non-trivial, and we should be very careful with optimizations on such code until we have a clear plan for how to model this.

And yet, it turns out that running this code with mir-opt-level=2 introduces UB:

error: Undefined Behavior: trying to retag from <1484> for Unique permission at alloc702[0x0], but that tag does not exist in the borrow stack for this location
  --> 2phase.rs:4:16
   |
4  |         fn add(&mut self, n: u64) -> u64 {
   |                ^^^^^^^^^
   |                |
   |                trying to retag from <1484> for Unique permission at alloc702[0x0], but that tag does not exist in the borrow stack for this location
   |                this error occurs as part of function-entry retag at alloc702[0x0..0x8]
   |
   = help: this indicates a potential bug in the program: it performed an invalid operation, but the Stacked Borrows rules it violated are still experimental
   = help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information
help: <1484> was created by a SharedReadWrite retag at offsets [0x0..0x8]
  --> 2phase.rs:11:15
   |
11 |     let res = f.add(unsafe {
   |               ^
help: <1484> was later invalidated at offsets [0x0..0x8] by a write access
  --> 2phase.rs:14:9
   |
14 |         *alias = 42;
   |         ^^^^^^^^^^^
   = note: BACKTRACE (of the first span):
   = note: inside `main::Foo::add` at 2phase.rs:4:16: 4:25
note: inside `main`
  --> 2phase.rs:11:15
   |
11 |       let res = f.add(unsafe {
   |  _______________^
12 | |         // This is the access at fault, but it's not immediately apparent because
13 | |         // the reference that got invalidated is not under a Protector.
14 | |         *alias = 42;
15 | |         0
16 | |     });
   | |______^

This is quite surprising, I thought we were very conservative in terms of doing optimizations that rely on the aliasing model. I have not yet figured out where exactly this comes from.
Cc @rust-lang/opsem @rust-lang/wg-mir-opt @cjgillot

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with the provided 2phase.rs reproducer and run it with mir-opt-level=2, comparing the behavior without that optimization level. Trace the MIR optimization and function-entry retag around Foo::add and the alias invalidation shown in the diagnostic. Done means identifying the optimization that introduces the Stacked Borrows UB and defining a regression test or fix path.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
compilers
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.