TB: new tests

30 files changed, 888 insertions, 0 deletions

diff --git a/src/tools/miri/tests/fail/tree-borrows/alternate-read-write.rs b/src/tools/miri/tests/fail/tree-borrows/alternate-read-write.rs
new file mode 100644
index 00000000000..122a8ff8752
--- /dev/null
+++ b/src/tools/miri/tests/fail/tree-borrows/alternate-read-write.rs
@@ -0,0 +1,19 @@
+//@compile-flags: -Zmiri-tree-borrows
+
+// Check that TB properly rejects alternating Reads and Writes, but tolerates
+// alternating only Reads to Reserved mutable references.
+pub fn main() {
+    let x = &mut 0u8;
+    let y = unsafe { &mut *(x as *mut u8) };
+    // Foreign Read, but this is a no-op from the point of view of y (still Reserved)
+    let _val = *x;
+    // Now we activate y, for this to succeed y needs to not have been Frozen
+    // by the previous operation
+    *y += 1; // Success
+    // This time y gets Frozen...
+    let _val = *x;
+    // ... and the next Write attempt fails.
+    *y += 1; // Failure //~ ERROR: /write access through .* is forbidden/
+    let _val = *x;
+    *y += 1; // Unreachable
+}
diff --git a/src/tools/miri/tests/fail/tree-borrows/alternate-read-write.stderr b/src/tools/miri/tests/fail/tree-borrows/alternate-read-write.stderr
new file mode 100644
index 00000000000..7c5bcd4e7b0
--- /dev/null
+++ b/src/tools/miri/tests/fail/tree-borrows/alternate-read-write.stderr
@@ -0,0 +1,14 @@
+error: Undefined Behavior: write access through <TAG> is forbidden because it is a child of <TAG> which is Frozen.
+  --> $DIR/alternate-read-write.rs:LL:CC
+   |
+LL |     *y += 1; // Failure
+   |     ^^^^^^^ write access through <TAG> is forbidden because it is a child of <TAG> which is Frozen.
+   |
+   = help: this indicates a potential bug in the program: it performed an invalid operation, but the Tree Borrows rules it violated are still experimental
+   = note: BACKTRACE:
+   = note: inside `main` at $DIR/alternate-read-write.rs:LL:CC
+
+note: some details are omitted, run with `MIRIFLAGS=-Zmiri-backtrace=full` for a verbose backtrace
+
+error: aborting due to previous error
+
diff --git a/src/tools/miri/tests/fail/tree-borrows/fragile-data-race.rs b/src/tools/miri/tests/fail/tree-borrows/fragile-data-race.rs
new file mode 100644
index 00000000000..215100de0a1
--- /dev/null
+++ b/src/tools/miri/tests/fail/tree-borrows/fragile-data-race.rs
@@ -0,0 +1,42 @@
+//! Race-condition-like interaction between a read and a reborrow.
+//! Even though no write or fake write occurs, reads have an effect on protected
+//! Reserved. This is a protected-retag/read data race, but is not *detected* as
+//! a data race violation because reborrows are not writes.
+//!
+//! This test is sensitive to the exact schedule so we disable preemption.
+//@compile-flags: -Zmiri-tree-borrows -Zmiri-preemption-rate=0
+use std::ptr::addr_of_mut;
+use std::thread;
+
+#[derive(Copy, Clone)]
+struct SendPtr(*mut u8);
+
+unsafe impl Send for SendPtr {}
+
+// First thread is just a reborrow, but for an instant `x` is
+// protected and thus vulnerable to foreign reads.
+fn thread_1(x: &mut u8) -> SendPtr {
+    thread::yield_now(); // make the other thread go first
+    SendPtr(x as *mut u8)
+}
+
+// Second thread simply performs a read.
+fn thread_2(x: &u8) {
+    let _val = *x;
+}
+
+fn main() {
+    let mut x = 0u8;
+    let x_1 = unsafe { &mut *addr_of_mut!(x) };
+    let xg = unsafe { &*addr_of_mut!(x) };
+
+    // The two threads are executed in parallel on aliasing pointers.
+    // UB occurs if the read of thread_2 occurs while the protector of thread_1
+    // is in place.
+    let hf = thread::spawn(move || thread_1(x_1));
+    let hg = thread::spawn(move || thread_2(xg));
+    let SendPtr(p) = hf.join().unwrap();
+    let () = hg.join().unwrap();
+
+    unsafe { *p = 1 }; //~ ERROR: /write access through .* is forbidden/
+}
diff --git a/src/tools/miri/tests/fail/tree-borrows/fragile-data-race.stderr b/src/tools/miri/tests/fail/tree-borrows/fragile-data-race.stderr
new file mode 100644
index 00000000000..a078d18d3b0
--- /dev/null
+++ b/src/tools/miri/tests/fail/tree-borrows/fragile-data-race.stderr
@@ -0,0 +1,14 @@
+error: Undefined Behavior: write access through <TAG> is forbidden because it is a child of <TAG> which is Frozen.
+  --> $DIR/fragile-data-race.rs:LL:CC
+   |
+LL |     unsafe { *p = 1 };
+   |              ^^^^^^ write access through <TAG> is forbidden because it is a child of <TAG> which is Frozen.
+   |
+   = help: this indicates a potential bug in the program: it performed an invalid operation, but the Tree Borrows rules it violated are still experimental
+   = note: BACKTRACE:
+   = note: inside `main` at $DIR/fragile-data-race.rs:LL:CC
+
+note: some details are omitted, run with `MIRIFLAGS=-Zmiri-backtrace=full` for a verbose backtrace
+
+error: aborting due to previous error
+
diff --git a/src/tools/miri/tests/fail/tree-borrows/outside-range.rs b/src/tools/miri/tests/fail/tree-borrows/outside-range.rs
new file mode 100644
index 00000000000..8450e1c168d
--- /dev/null
+++ b/src/tools/miri/tests/fail/tree-borrows/outside-range.rs
@@ -0,0 +1,22 @@
+//@compile-flags: -Zmiri-tree-borrows
+
+// Check that in the case of locations outside the range of a pointer,
+// protectors trigger if and only if the location has already been accessed
+fn main() {
+    unsafe {
+        let data = &mut [0u8, 1, 2, 3];
+        let raw = data.as_mut_ptr();
+        stuff(&mut *raw, raw);
+    }
+}
+
+unsafe fn stuff(x: &mut u8, y: *mut u8) {
+    let xraw = x as *mut u8;
+    // No issue here: location 1 is not accessed
+    *y.add(1) = 42;
+    // Still no issue: location 2 is not invalidated
+    let _val = *xraw.add(2);
+    // However protector triggers if location is both accessed and invalidated
+    let _val = *xraw.add(3);
+    *y.add(3) = 42; //~ ERROR: /write access through .* is forbidden/
+}
diff --git a/src/tools/miri/tests/fail/tree-borrows/outside-range.stderr b/src/tools/miri/tests/fail/tree-borrows/outside-range.stderr
new file mode 100644
index 00000000000..4396c63679e
--- /dev/null
+++ b/src/tools/miri/tests/fail/tree-borrows/outside-range.stderr
@@ -0,0 +1,19 @@
+error: Undefined Behavior: write access through <TAG> is forbidden because it is a foreign tag for <TAG>, which would hence change from Reserved to Disabled, but <TAG> is protected
+  --> $DIR/outside-range.rs:LL:CC
+   |
+LL |     *y.add(3) = 42;
+   |     ^^^^^^^^^^^^^^ write access through <TAG> is forbidden because it is a foreign tag for <TAG>, which would hence change from Reserved to Disabled, but <TAG> is protected
+   |
+   = help: this indicates a potential bug in the program: it performed an invalid operation, but the Tree Borrows rules it violated are still experimental
+   = note: BACKTRACE:
+   = note: inside `stuff` at $DIR/outside-range.rs:LL:CC
+note: inside `main`
+  --> $DIR/outside-range.rs:LL:CC
+   |
+LL |         stuff(&mut *raw, raw);
+   |         ^^^^^^^^^^^^^^^^^^^^^
+
+note: some details are omitted, run with `MIRIFLAGS=-Zmiri-backtrace=full` for a verbose backtrace
+
+error: aborting due to previous error
+
diff --git a/src/tools/miri/tests/fail/tree-borrows/read-to-local.rs b/src/tools/miri/tests/fail/tree-borrows/read-to-local.rs
new file mode 100644
index 00000000000..025b7ad22dc
--- /dev/null
+++ b/src/tools/miri/tests/fail/tree-borrows/read-to-local.rs
@@ -0,0 +1,14 @@
+//@compile-flags: -Zmiri-tree-borrows
+
+// Read to local variable kills reborrows *and* raw pointers derived from them.
+// This test would succeed under Stacked Borrows.
+fn main() {
+    unsafe {
+        let mut root = 6u8;
+        let mref = &mut root;
+        let ptr = mref as *mut u8;
+        *ptr = 0; // Write
+        assert_eq!(root, 0); // Parent Read
+        *ptr = 0; //~ ERROR: /write access through .* is forbidden/
+    }
+}
diff --git a/src/tools/miri/tests/fail/tree-borrows/read-to-local.stderr b/src/tools/miri/tests/fail/tree-borrows/read-to-local.stderr
new file mode 100644
index 00000000000..7d9367c87d0
--- /dev/null
+++ b/src/tools/miri/tests/fail/tree-borrows/read-to-local.stderr
@@ -0,0 +1,14 @@
+error: Undefined Behavior: write access through <TAG> is forbidden because it is a child of <TAG> which is Frozen.
+  --> $DIR/read-to-local.rs:LL:CC
+   |
+LL |         *ptr = 0;
+   |         ^^^^^^^^ write access through <TAG> is forbidden because it is a child of <TAG> which is Frozen.
+   |
+   = help: this indicates a potential bug in the program: it performed an invalid operation, but the Tree Borrows rules it violated are still experimental
+   = note: BACKTRACE:
+   = note: inside `main` at $DIR/read-to-local.rs:LL:CC
+
+note: some details are omitted, run with `MIRIFLAGS=-Zmiri-backtrace=full` for a verbose backtrace
+
+error: aborting due to previous error
+
diff --git a/src/tools/miri/tests/fail/tree-borrows/reserved/cell-protected-write.rs b/src/tools/miri/tests/fail/tree-borrows/reserved/cell-protected-write.rs
new file mode 100644
index 00000000000..872efe3ad59
--- /dev/null
+++ b/src/tools/miri/tests/fail/tree-borrows/reserved/cell-protected-write.rs
@@ -0,0 +1,34 @@
+//@compile-flags: -Zmiri-tree-borrows -Zmiri-tag-gc=0
+
+// Check how a Reserved with interior mutability
+// responds to a Foreign Write under a Protector
+#[path = "../../../utils/mod.rs"]
+mod utils;
+use utils::macros::*;
+
+use std::cell::UnsafeCell;
+
+fn main() {
+    unsafe {
+        let n = &mut UnsafeCell::new(0u8);
+        name!(n.get(), "base");
+        let x = &mut *(n as *mut UnsafeCell<_>);
+        name!(x.get(), "x");
+        let y = (&mut *n).get();
+        name!(y);
+        write_second(x, y);
+        unsafe fn write_second(x: &mut UnsafeCell<u8>, y: *mut u8) {
+            let alloc_id = alloc_id!(x.get());
+            name!(x.get(), "callee:x");
+            name!(x.get()=>1, "caller:x");
+            name!(y, "callee:y");
+            name!(y, "caller:y");
+            print_state!(alloc_id);
+            // Right before the faulty Write, x is
+            // - Reserved
+            // - with interior mut
+            // - Protected
+            *y = 1; //~ ERROR: /write access through .* is forbidden/
+        }
+    }
+}
diff --git a/src/tools/miri/tests/fail/tree-borrows/reserved/cell-protected-write.stderr b/src/tools/miri/tests/fail/tree-borrows/reserved/cell-protected-write.stderr
new file mode 100644
index 00000000000..8ae1c09470a
--- /dev/null
+++ b/src/tools/miri/tests/fail/tree-borrows/reserved/cell-protected-write.stderr
@@ -0,0 +1,28 @@
+──────────────────────────────────────────────────────────────────────
+Warning: this tree is indicative only. Some tags may have been hidden.
+0..  1
+| Re*|    └─┬──<TAG=base>
+| Re*|      ├─┬──<TAG=x>
+| Re*|      │ └─┬──<TAG=caller:x>
+| Re*|      │   └────<TAG=callee:x> Strongly protected
+| Re*|      └────<TAG=y,callee:y,caller:y>
+──────────────────────────────────────────────────────────────────────
+error: Undefined Behavior: write access through <TAG> (also named 'y,callee:y,caller:y') is forbidden because it is a foreign tag for <TAG> (also named 'callee:x'), which would hence change from Reserved to Disabled, but <TAG> (also named 'callee:x') is protected
+  --> $DIR/cell-protected-write.rs:LL:CC
+   |
+LL |             *y = 1;
+   |             ^^^^^^ write access through <TAG> (also named 'y,callee:y,caller:y') is forbidden because it is a foreign tag for <TAG> (also named 'callee:x'), which would hence change from Reserved to Disabled, but <TAG> (also named 'callee:x') is protected
+   |
+   = help: this indicates a potential bug in the program: it performed an invalid operation, but the Tree Borrows rules it violated are still experimental
+   = note: BACKTRACE:
+   = note: inside `main::write_second` at $DIR/cell-protected-write.rs:LL:CC
+note: inside `main`
+  --> $DIR/cell-protected-write.rs:LL:CC
+   |
+LL |         write_second(x, y);
+   |         ^^^^^^^^^^^^^^^^^^
+
+note: some details are omitted, run with `MIRIFLAGS=-Zmiri-backtrace=full` for a verbose backtrace
+
+error: aborting due to previous error
+
diff --git a/src/tools/miri/tests/fail/tree-borrows/reserved/int-protected-write.rs b/src/tools/miri/tests/fail/tree-borrows/reserved/int-protected-write.rs
new file mode 100644
index 00000000000..3a1205a84f7
--- /dev/null
+++ b/src/tools/miri/tests/fail/tree-borrows/reserved/int-protected-write.rs
@@ -0,0 +1,32 @@
+//@compile-flags: -Zmiri-tree-borrows -Zmiri-tag-gc=0
+
+#[path = "../../../utils/mod.rs"]
+mod utils;
+use utils::macros::*;
+
+// Check how a Reserved without interior mutability responds to a Foreign
+// Write when under a protector
+fn main() {
+    unsafe {
+        let n = &mut 0u8;
+        name!(n);
+        let x = &mut *(n as *mut _);
+        name!(x);
+        let y = (&mut *n) as *mut _;
+        name!(y);
+        write_second(x, y);
+        unsafe fn write_second(x: &mut u8, y: *mut u8) {
+            let alloc_id = alloc_id!(x);
+            name!(x, "callee:x");
+            name!(x=>1, "caller:x");
+            name!(y, "callee:y");
+            name!(y, "caller:y");
+            print_state!(alloc_id);
+            // Right before the faulty Write, x is
+            // - Reserved
+            // - Protected
+            // The Write turns it Disabled
+            *y = 0; //~ ERROR: /write access through .* is forbidden/
+        }
+    }
+}
diff --git a/src/tools/miri/tests/fail/tree-borrows/reserved/int-protected-write.stderr b/src/tools/miri/tests/fail/tree-borrows/reserved/int-protected-write.stderr
new file mode 100644
index 00000000000..a199fc0f0da
--- /dev/null
+++ b/src/tools/miri/tests/fail/tree-borrows/reserved/int-protected-write.stderr
@@ -0,0 +1,28 @@
+──────────────────────────────────────────────────────────────────────
+Warning: this tree is indicative only. Some tags may have been hidden.
+0..  1
+| Res|    └─┬──<TAG=n>
+| Res|      ├─┬──<TAG=x>
+| Res|      │ └─┬──<TAG=caller:x>
+| Res|      │   └────<TAG=callee:x> Strongly protected
+| Res|      └────<TAG=y,callee:y,caller:y>
+──────────────────────────────────────────────────────────────────────
+error: Undefined Behavior: write access through <TAG> (also named 'y,callee:y,caller:y') is forbidden because it is a foreign tag for <TAG> (also named 'callee:x'), which would hence change from Reserved to Disabled, but <TAG> (also named 'callee:x') is protected
+  --> $DIR/int-protected-write.rs:LL:CC
+   |
+LL |             *y = 0;
+   |             ^^^^^^ write access through <TAG> (also named 'y,callee:y,caller:y') is forbidden because it is a foreign tag for <TAG> (also named 'callee:x'), which would hence change from Reserved to Disabled, but <TAG> (also named 'callee:x') is protected
+   |
+   = help: this indicates a potential bug in the program: it performed an invalid operation, but the Tree Borrows rules it violated are still experimental
+   = note: BACKTRACE:
+   = note: inside `main::write_second` at $DIR/int-protected-write.rs:LL:CC
+note: inside `main`
+  --> $DIR/int-protected-write.rs:LL:CC
+   |
+LL |         write_second(x, y);
+   |         ^^^^^^^^^^^^^^^^^^
+
+note: some details are omitted, run with `MIRIFLAGS=-Zmiri-backtrace=full` for a verbose backtrace
+
+error: aborting due to previous error
+
diff --git a/src/tools/miri/tests/fail/tree-borrows/retag-data-race.rs b/src/tools/miri/tests/fail/tree-borrows/retag-data-race.rs
new file mode 100644
index 00000000000..8ef3d23e804
--- /dev/null
+++ b/src/tools/miri/tests/fail/tree-borrows/retag-data-race.rs
@@ -0,0 +1,28 @@
+//! Make sure that a retag acts like a read for the data race model.
+//! This is a retag/write race condition.
+//!
+//! This test is sensitive to the exact schedule so we disable preemption.
+//@compile-flags: -Zmiri-tree-borrows -Zmiri-preemption-rate=0
+#[derive(Copy, Clone)]
+struct SendPtr(*mut u8);
+
+unsafe impl Send for SendPtr {}
+
+unsafe fn thread_1(SendPtr(p): SendPtr) {
+    let _r = &*p;
+}
+
+unsafe fn thread_2(SendPtr(p): SendPtr) {
+    *p = 5; //~ ERROR: Data race detected between (1) Read on thread `<unnamed>` and (2) Write on thread `<unnamed>`
+}
+
+fn main() {
+    let mut x = 0;
+    let p = std::ptr::addr_of_mut!(x);
+    let p = SendPtr(p);
+
+    let t1 = std::thread::spawn(move || unsafe { thread_1(p) });
+    let t2 = std::thread::spawn(move || unsafe { thread_2(p) });
+    let _ = t1.join();
+    let _ = t2.join();
+}
diff --git a/src/tools/miri/tests/fail/tree-borrows/retag-data-race.stderr b/src/tools/miri/tests/fail/tree-borrows/retag-data-race.stderr
new file mode 100644
index 00000000000..f2cdfe7c314
--- /dev/null
+++ b/src/tools/miri/tests/fail/tree-borrows/retag-data-race.stderr
@@ -0,0 +1,25 @@
+error: Undefined Behavior: Data race detected between (1) Read on thread `<unnamed>` and (2) Write on thread `<unnamed>` at ALLOC. (2) just happened here
+  --> $DIR/retag-data-race.rs:LL:CC
+   |
+LL |     *p = 5;
+   |     ^^^^^^ Data race detected between (1) Read on thread `<unnamed>` and (2) Write on thread `<unnamed>` at ALLOC. (2) just happened here
+   |
+help: and (1) occurred earlier here
+  --> $DIR/retag-data-race.rs:LL:CC
+   |
+LL |     let _r = &*p;
+   |              ^^^
+   = help: this indicates a bug in the program: it performed an invalid operation, and caused Undefined Behavior
+   = help: see https://doc.rust-lang.org/nightly/reference/behavior-considered-undefined.html for further information
+   = note: BACKTRACE (of the first span):
+   = note: inside `thread_2` at $DIR/retag-data-race.rs:LL:CC
+note: inside closure
+  --> $DIR/retag-data-race.rs:LL:CC
+   |
+LL |     let t2 = std::thread::spawn(move || unsafe { thread_2(p) });
+   |                                                  ^^^^^^^^^^^
+
+note: some details are omitted, run with `MIRIFLAGS=-Zmiri-backtrace=full` for a verbose backtrace
+
+error: aborting due to previous error
+
diff --git a/src/tools/miri/tests/fail/tree-borrows/write-during-2phase.rs b/src/tools/miri/tests/fail/tree-borrows/write-during-2phase.rs
new file mode 100644
index 00000000000..6695d36306b
--- /dev/null
+++ b/src/tools/miri/tests/fail/tree-borrows/write-during-2phase.rs
@@ -0,0 +1,27 @@
+//@compile-flags: -Zmiri-tree-borrows
+
+// We invalidate a reference during a 2-phase borrow by doing a Foreign
+// Write in between the initial reborrow and function entry. UB occurs
+// on function entry when reborrow from a Disabled fails.
+// This test would pass under Stacked Borrows, but Tree Borrows
+// is more strict on 2-phase borrows.
+
+struct Foo(u64);
+impl Foo {
+    #[rustfmt::skip] // rustfmt is wrong about which line contains an error
+    fn add(&mut self, n: u64) -> u64 { //~ ERROR: /read access through .* is forbidden/
+        self.0 + n
+    }
+}
+
+pub fn main() {
+    let mut f = Foo(0);
+    let inner = &mut f.0 as *mut u64;
+    let _res = f.add(unsafe {
+        let n = f.0;
+        // This is the access at fault, but it's not immediately apparent because
+        // the reference that got invalidated is not under a Protector.
+        *inner = 42;
+        n
+    });
+}
diff --git a/src/tools/miri/tests/fail/tree-borrows/write-during-2phase.stderr b/src/tools/miri/tests/fail/tree-borrows/write-during-2phase.stderr
new file mode 100644
index 00000000000..e511eb9cf8f
--- /dev/null
+++ b/src/tools/miri/tests/fail/tree-borrows/write-during-2phase.stderr
@@ -0,0 +1,26 @@
+error: Undefined Behavior: read access through <TAG> is forbidden because it is a child of <TAG> which is Disabled.
+  --> $DIR/write-during-2phase.rs:LL:CC
+   |
+LL |     fn add(&mut self, n: u64) -> u64 {
+   |            ^^^^^^^^^ read access through <TAG> is forbidden because it is a child of <TAG> which is Disabled.
+   |
+   = help: this indicates a potential bug in the program: it performed an invalid operation, but the Tree Borrows rules it violated are still experimental
+   = note: BACKTRACE:
+   = note: inside `Foo::add` at $DIR/write-during-2phase.rs:LL:CC
+note: inside `main`
+  --> $DIR/write-during-2phase.rs:LL:CC
+   |
+LL |       let _res = f.add(unsafe {
+   |  ________________^
+LL | |         let n = f.0;
+LL | |         // This is the access at fault, but it's not immediately apparent because
+LL | |         // the reference that got invalidated is not under a Protector.
+LL | |         *inner = 42;
+LL | |         n
+LL | |     });
+   | |______^
+
+note: some details are omitted, run with `MIRIFLAGS=-Zmiri-backtrace=full` for a verbose backtrace
+
+error: aborting due to previous error
+
diff --git a/src/tools/miri/tests/pass/tree-borrows/2phase-interiormut.rs b/src/tools/miri/tests/pass/tree-borrows/2phase-interiormut.rs
new file mode 100644
index 00000000000..af52f53791a
--- /dev/null
+++ b/src/tools/miri/tests/pass/tree-borrows/2phase-interiormut.rs
@@ -0,0 +1,27 @@
+//@compile-flags: -Zmiri-tree-borrows
+
+// Counterpart to tests/fail/tree-borrows/write-during-2phase.rs,
+// this is the opposite situation: the Write is not problematic because
+// the Protector has not yet been added and the Reserved has interior
+// mutability.
+use core::cell::Cell;
+
+trait Thing: Sized {
+    fn do_the_thing(&mut self, _s: i32) {}
+}
+impl<T> Thing for Cell<T> {}
+
+fn main() {
+    let mut x = Cell::new(1);
+    let l = &x;
+
+    x.do_the_thing({
+        // Several Foreign accesses (both Reads and Writes) to the location
+        // being reborrowed. Reserved + unprotected + interior mut
+        // makes the pointer immune to everything as long as all accesses
+        // are child accesses to its parent pointer x.
+        x.set(3);
+        l.set(4);
+        x.get() + l.get()
+    });
+}
diff --git a/src/tools/miri/tests/pass/tree-borrows/cell-alternate-writes.rs b/src/tools/miri/tests/pass/tree-borrows/cell-alternate-writes.rs
new file mode 100644
index 00000000000..1bd94c6df67
--- /dev/null
+++ b/src/tools/miri/tests/pass/tree-borrows/cell-alternate-writes.rs
@@ -0,0 +1,27 @@
+//@compile-flags: -Zmiri-tree-borrows -Zmiri-tag-gc=0
+#[path = "../../utils/mod.rs"]
+mod utils;
+use utils::macros::*;
+
+use std::cell::UnsafeCell;
+
+// UnsafeCells use the parent tag, so it is possible to use them with
+// few restrictions when only among themselves.
+fn main() {
+    unsafe {
+        let data = &mut UnsafeCell::new(0u8);
+        name!(data.get(), "data");
+        let x = &*data;
+        name!(x.get(), "x");
+        let y = &*data;
+        name!(y.get(), "y");
+        let alloc_id = alloc_id!(data.get());
+        print_state!(alloc_id);
+        // y and x tolerate alternating Writes
+        *y.get() = 1;
+        *x.get() = 2;
+        *y.get() = 3;
+        *x.get() = 4;
+        print_state!(alloc_id);
+    }
+}
diff --git a/src/tools/miri/tests/pass/tree-borrows/cell-alternate-writes.stderr b/src/tools/miri/tests/pass/tree-borrows/cell-alternate-writes.stderr
new file mode 100644
index 00000000000..d4bc822b4bb
--- /dev/null
+++ b/src/tools/miri/tests/pass/tree-borrows/cell-alternate-writes.stderr
@@ -0,0 +1,10 @@
+──────────────────────────────────────────────────────────────────────
+Warning: this tree is indicative only. Some tags may have been hidden.
+0..  1
+| Re*|    └────<TAG=data,x,y>
+──────────────────────────────────────────────────────────────────────
+──────────────────────────────────────────────────────────────────────
+Warning: this tree is indicative only. Some tags may have been hidden.
+0..  1
+| Act|    └────<TAG=data,x,y>
+──────────────────────────────────────────────────────────────────────
diff --git a/src/tools/miri/tests/pass/tree-borrows/copy-nonoverlapping.rs b/src/tools/miri/tests/pass/tree-borrows/copy-nonoverlapping.rs
new file mode 100644
index 00000000000..23250d6e6df
--- /dev/null
+++ b/src/tools/miri/tests/pass/tree-borrows/copy-nonoverlapping.rs
@@ -0,0 +1,29 @@
+//@compile-flags: -Zmiri-tree-borrows
+
+// copy_nonoverlapping works regardless of the order in which we construct
+// the arguments.
+pub fn main() {
+    test_to_from();
+    test_from_to();
+}
+
+fn test_to_from() {
+    unsafe {
+        let data = &mut [0u64, 1];
+        let to = data.as_mut_ptr().add(1);
+        let from = data.as_ptr();
+        std::ptr::copy_nonoverlapping(from, to, 1);
+    }
+}
+
+// Stacked Borrows would not have liked this one because the `as_mut_ptr` reborrow
+// invalidates the earlier pointer obtained from `as_ptr`, but Tree Borrows is fine
+// with it.
+fn test_from_to() {
+    unsafe {
+        let data = &mut [0u64, 1];
+        let from = data.as_ptr();
+        let to = data.as_mut_ptr().add(1);
+        std::ptr::copy_nonoverlapping(from, to, 1);
+    }
+}
diff --git a/src/tools/miri/tests/pass/tree-borrows/end-of-protector.rs b/src/tools/miri/tests/pass/tree-borrows/end-of-protector.rs
new file mode 100644
index 00000000000..76bbc73e662
--- /dev/null
+++ b/src/tools/miri/tests/pass/tree-borrows/end-of-protector.rs
@@ -0,0 +1,32 @@
+//@compile-flags: -Zmiri-tree-borrows -Zmiri-tag-gc=0
+
+// Check that a protector goes back to normal behavior when the function
+// returns.
+#[path = "../../utils/mod.rs"]
+mod utils;
+use utils::macros::*;
+
+fn main() {
+    unsafe {
+        let data = &mut 0u8;
+        name!(data);
+        let alloc_id = alloc_id!(data);
+        let x = &mut *data;
+        name!(x);
+        print_state!(alloc_id);
+        do_nothing(x); // creates then removes a Protector for a child of x
+        let y = &mut *data;
+        name!(y);
+        print_state!(alloc_id);
+        // Invalidates the previous reborrow, but its Protector has been removed.
+        *y = 1;
+        print_state!(alloc_id);
+    }
+}
+
+unsafe fn do_nothing(x: &mut u8) {
+    name!(x, "callee:x");
+    name!(x=>1, "caller:x");
+    let alloc_id = alloc_id!(x);
+    print_state!(alloc_id);
+}
diff --git a/src/tools/miri/tests/pass/tree-borrows/end-of-protector.stderr b/src/tools/miri/tests/pass/tree-borrows/end-of-protector.stderr
new file mode 100644
index 00000000000..d08d6948320
--- /dev/null
+++ b/src/tools/miri/tests/pass/tree-borrows/end-of-protector.stderr
@@ -0,0 +1,32 @@
+──────────────────────────────────────────────────────────────────────
+Warning: this tree is indicative only. Some tags may have been hidden.
+0..  1
+| Res|    └─┬──<TAG=data>
+| Res|      └────<TAG=x>
+──────────────────────────────────────────────────────────────────────
+──────────────────────────────────────────────────────────────────────
+Warning: this tree is indicative only. Some tags may have been hidden.
+0..  1
+| Res|    └─┬──<TAG=data>
+| Res|      └─┬──<TAG=x>
+| Res|        └─┬──<TAG=caller:x>
+| Res|          └────<TAG=callee:x> Strongly protected
+──────────────────────────────────────────────────────────────────────
+──────────────────────────────────────────────────────────────────────
+Warning: this tree is indicative only. Some tags may have been hidden.
+0..  1
+| Res|    └─┬──<TAG=data>
+| Res|      ├─┬──<TAG=x>
+| Res|      │ └─┬──<TAG=caller:x>
+| Res|      │   └────<TAG=callee:x>
+| Res|      └────<TAG=y>
+──────────────────────────────────────────────────────────────────────
+──────────────────────────────────────────────────────────────────────
+Warning: this tree is indicative only. Some tags may have been hidden.
+0..  1
+| Act|    └─┬──<TAG=data>
+| Dis|      ├─┬──<TAG=x>
+| Dis|      │ └─┬──<TAG=caller:x>
+| Dis|      │   └────<TAG=callee:x>
+| Act|      └────<TAG=y>
+──────────────────────────────────────────────────────────────────────
diff --git a/src/tools/miri/tests/pass/tree-borrows/formatting.rs b/src/tools/miri/tests/pass/tree-borrows/formatting.rs
new file mode 100644
index 00000000000..9021c417638
--- /dev/null
+++ b/src/tools/miri/tests/pass/tree-borrows/formatting.rs
@@ -0,0 +1,73 @@
+//@compile-flags: -Zmiri-tree-borrows -Zmiri-tag-gc=0
+
+#[path = "../../utils/mod.rs"]
+mod utils;
+use utils::macros::*;
+
+// Check the formatting of the trees.
+fn main() {
+    unsafe {
+        alignment_check();
+        structure_check();
+    }
+}
+
+// Alignment check: we split the array at indexes with different amounts of
+// decimal digits to verify proper padding.
+unsafe fn alignment_check() {
+    let data: &mut [u8] = &mut [0; 1024];
+    name!(data.as_ptr()=>2, "data");
+    let alloc_id = alloc_id!(data.as_ptr());
+    let x = &mut data[1];
+    name!(x as *mut _, "data[1]");
+    *x = 1;
+    let x = &mut data[10];
+    name!(x as *mut _, "data[10]");
+    *x = 1;
+    let x = &mut data[100];
+    name!(x as *mut _, "data[100]");
+    *x = 1;
+    let _val = data[100]; // So that the above is Frz
+    let x = &mut data[1000];
+    name!(x as *mut _, "data[1000]");
+    *x = 1;
+    print_state!(alloc_id);
+}
+
+// Tree structure check: somewhat complex organization of reborrows.
+unsafe fn structure_check() {
+    let x = &0u8;
+    name!(x);
+    let xa = &*x;
+    name!(xa);
+    let xb = &*x;
+    name!(xb);
+    let xc = &*x;
+    name!(xc);
+    let xaa = &*xa;
+    name!(xaa);
+    let xab = &*xa;
+    name!(xab);
+    let xba = &*xb;
+    name!(xba);
+    let xbaa = &*xba;
+    name!(xbaa);
+    let xbaaa = &*xbaa;
+    name!(xbaaa);
+    let xbaaaa = &*xbaaa;
+    name!(xbaaaa);
+    let xca = &*xc;
+    name!(xca);
+    let xcb = &*xc;
+    name!(xcb);
+    let xcaa = &*xca;
+    name!(xcaa);
+    let xcab = &*xca;
+    name!(xcab);
+    let xcba = &*xcb;
+    name!(xcba);
+    let xcbb = &*xcb;
+    name!(xcbb);
+    let alloc_id = alloc_id!(x);
+    print_state!(alloc_id);
+}
diff --git a/src/tools/miri/tests/pass/tree-borrows/formatting.stderr b/src/tools/miri/tests/pass/tree-borrows/formatting.stderr
new file mode 100644
index 00000000000..a59775cf21f
--- /dev/null
+++ b/src/tools/miri/tests/pass/tree-borrows/formatting.stderr
@@ -0,0 +1,29 @@
+─────────────────────────────────────────────────────────────────────────────
+Warning: this tree is indicative only. Some tags may have been hidden.
+0..  1..  2.. 10.. 11..100..101..1000..1001..1024
+| Res| Act| Res| Act| Res| Act|  Res|  Act|  Res|    └─┬──<TAG=data>
+|----| Act|----|?Dis|----|?Dis| ----| ?Dis| ----|      ├────<TAG=data[1]>
+|----|----|----| Act|----|?Dis| ----| ?Dis| ----|      ├────<TAG=data[10]>
+|----|----|----|----|----| Frz| ----| ?Dis| ----|      ├────<TAG=data[100]>
+|----|----|----|----|----|----| ----|  Act| ----|      └────<TAG=data[1000]>
+─────────────────────────────────────────────────────────────────────────────
+──────────────────────────────────────────────────────────────────────
+Warning: this tree is indicative only. Some tags may have been hidden.
+0..  1
+| Frz|    └─┬──<TAG=x>
+| Frz|      ├─┬──<TAG=xa>
+| Frz|      │ ├────<TAG=xaa>
+| Frz|      │ └────<TAG=xab>
+| Frz|      ├─┬──<TAG=xb>
+| Frz|      │ └─┬──<TAG=xba>
+| Frz|      │   └─┬──<TAG=xbaa>
+| Frz|      │     └─┬──<TAG=xbaaa>
+| Frz|      │       └────<TAG=xbaaaa>
+| Frz|      └─┬──<TAG=xc>
+| Frz|        ├─┬──<TAG=xca>
+| Frz|        │ ├────<TAG=xcaa>
+| Frz|        │ └────<TAG=xcab>
+| Frz|        └─┬──<TAG=xcb>
+| Frz|          ├────<TAG=xcba>
+| Frz|          └────<TAG=xcbb>
+──────────────────────────────────────────────────────────────────────
diff --git a/src/tools/miri/tests/pass/tree-borrows/read-only-from-mut.rs b/src/tools/miri/tests/pass/tree-borrows/read-only-from-mut.rs
new file mode 100644
index 00000000000..4daf06c777e
--- /dev/null
+++ b/src/tools/miri/tests/pass/tree-borrows/read-only-from-mut.rs
@@ -0,0 +1,14 @@
+//@compile-flags: -Zmiri-tree-borrows
+
+// Tree Borrows has no issue with several mutable references existing
+// at the same time, as long as they are used only immutably.
+// I.e. multiple Reserved can coexist.
+pub fn main() {
+    unsafe {
+        let base = &mut 42u64;
+        let r1 = &mut *(base as *mut u64);
+        let r2 = &mut *(base as *mut u64);
+        let _l = *r1;
+        let _l = *r2;
+    }
+}
diff --git a/src/tools/miri/tests/pass/tree-borrows/reborrow-is-read.rs b/src/tools/miri/tests/pass/tree-borrows/reborrow-is-read.rs
new file mode 100644
index 00000000000..e3f3f2d4032
--- /dev/null
+++ b/src/tools/miri/tests/pass/tree-borrows/reborrow-is-read.rs
@@ -0,0 +1,24 @@
+//@compile-flags: -Zmiri-tree-borrows -Zmiri-tag-gc=0
+
+#[path = "../../utils/mod.rs"]
+mod utils;
+use utils::macros::*;
+
+// To check that a reborrow is counted as a Read access, we use a reborrow
+// with no additional Read to Freeze an Active pointer.
+
+fn main() {
+    unsafe {
+        let parent = &mut 0u8;
+        name!(parent);
+        let alloc_id = alloc_id!(parent);
+        let x = &mut *parent;
+        name!(x);
+        *x = 0; // x is now Active
+        print_state!(alloc_id);
+        let y = &mut *parent;
+        name!(y);
+        // Check in the debug output that x has been Frozen by the reborrow
+        print_state!(alloc_id);
+    }
+}
diff --git a/src/tools/miri/tests/pass/tree-borrows/reborrow-is-read.stderr b/src/tools/miri/tests/pass/tree-borrows/reborrow-is-read.stderr
new file mode 100644
index 00000000000..b9c52c20640
--- /dev/null
+++ b/src/tools/miri/tests/pass/tree-borrows/reborrow-is-read.stderr
@@ -0,0 +1,13 @@
+──────────────────────────────────────────────────────────────────────
+Warning: this tree is indicative only. Some tags may have been hidden.
+0..  1
+| Act|    └─┬──<TAG=parent>
+| Act|      └────<TAG=x>
+──────────────────────────────────────────────────────────────────────
+──────────────────────────────────────────────────────────────────────
+Warning: this tree is indicative only. Some tags may have been hidden.
+0..  1
+| Act|    └─┬──<TAG=parent>
+| Frz|      ├────<TAG=x>
+| Res|      └────<TAG=y>
+──────────────────────────────────────────────────────────────────────
diff --git a/src/tools/miri/tests/pass/tree-borrows/reserved.rs b/src/tools/miri/tests/pass/tree-borrows/reserved.rs
new file mode 100644
index 00000000000..d8a8c27568d
--- /dev/null
+++ b/src/tools/miri/tests/pass/tree-borrows/reserved.rs
@@ -0,0 +1,127 @@
+//@compile-flags: -Zmiri-tree-borrows -Zmiri-tag-gc=0
+
+#[path = "../../utils/mod.rs"]
+mod utils;
+use utils::macros::*;
+use utils::miri_extern::miri_write_to_stderr;
+
+use std::cell::UnsafeCell;
+
+// We exhaustively check that Reserved behaves as we want under all of the
+// following conditions:
+// - with or without interior mutability
+// - with or without a protector
+// - for a foreign read or write
+// Of these cases, those in this file are the ones that must not cause
+// immediate UB, and those that do are in tests/fail/tree-borrows/reserved/
+// and are the combinations [_ + protected + write]
+
+fn main() {
+    unsafe {
+        cell_protected_read();
+        cell_unprotected_read();
+        cell_unprotected_write();
+        int_protected_read();
+        int_unprotected_read();
+        int_unprotected_write();
+    }
+}
+
+unsafe fn print(msg: &str) {
+    miri_write_to_stderr(msg.as_bytes());
+    miri_write_to_stderr("\n".as_bytes());
+}
+
+unsafe fn read_second<T>(x: &mut T, y: *mut u8) {
+    name!(x as *mut T as *mut u8=>1, "caller:x");
+    name!(x as *mut T as *mut u8, "callee:x");
+    name!(y, "caller:y");
+    name!(y, "callee:y");
+    let _val = *y;
+}
+
+// Foreign Read on a interior mutable Protected Reserved turns it Frozen.
+unsafe fn cell_protected_read() {
+    print("[interior mut + protected] Foreign Read: Re* -> Frz");
+    let base = &mut UnsafeCell::new(0u8);
+    name!(base.get(), "base");
+    let alloc_id = alloc_id!(base.get());
+    let x = &mut *(base as *mut UnsafeCell<u8>);
+    name!(x.get(), "x");
+    let y = (&mut *base).get();
+    name!(y);
+    read_second(x, y); // Foreign Read for callee:x
+    print_state!(alloc_id);
+}
+
+// Foreign Read on an interior mutable pointer is a noop.
+unsafe fn cell_unprotected_read() {
+    print("[interior mut] Foreign Read: Re* -> Re*");
+    let base = &mut UnsafeCell::new(0u64);
+    name!(base.get(), "base");
+    let alloc_id = alloc_id!(base.get());
+    let x = &mut *(base as *mut UnsafeCell<_>);
+    name!(x.get(), "x");
+    let y = (&mut *base).get();
+    name!(y);
+    let _val = *y; // Foreign Read for x
+    print_state!(alloc_id);
+}
+
+// Foreign Write on an interior mutable pointer is a noop.
+// Also y must become Active.
+unsafe fn cell_unprotected_write() {
+    print("[interior mut] Foreign Write: Re* -> Re*");
+    let base = &mut UnsafeCell::new(0u64);
+    name!(base.get(), "base");
+    let alloc_id = alloc_id!(base.get());
+    let x = &mut *(base as *mut UnsafeCell<u64>);
+    name!(x.get(), "x");
+    let y = (&mut *base).get();
+    name!(y);
+    *y = 1; // Foreign Write for x
+    print_state!(alloc_id);
+}
+
+// Foreign Read on a Protected Reserved turns it Frozen.
+unsafe fn int_protected_read() {
+    print("[protected] Foreign Read: Res -> Frz");
+    let base = &mut 0u8;
+    let alloc_id = alloc_id!(base);
+    name!(base);
+    let x = &mut *(base as *mut u8);
+    name!(x);
+    let y = (&mut *base) as *mut u8;
+    name!(y);
+    read_second(x, y); // Foreign Read for callee:x
+    print_state!(alloc_id);
+}
+
+// Foreign Read on a Reserved is a noop.
+// Also y must become Active.
+unsafe fn int_unprotected_read() {
+    print("[] Foreign Read: Res -> Res");
+    let base = &mut 0u8;
+    name!(base);
+    let alloc_id = alloc_id!(base);
+    let x = &mut *(base as *mut u8);
+    name!(x);
+    let y = (&mut *base) as *mut u8;
+    name!(y);
+    let _val = *y; // Foreign Read for x
+    print_state!(alloc_id);
+}
+
+// Foreign Write on a Reserved turns it Disabled.
+unsafe fn int_unprotected_write() {
+    print("[] Foreign Write: Res -> Dis");
+    let base = &mut 0u8;
+    name!(base);
+    let alloc_id = alloc_id!(base);
+    let x = &mut *(base as *mut u8);
+    name!(x);
+    let y = (&mut *base) as *mut u8;
+    name!(y);
+    *y = 1; // Foreign Write for x
+    print_state!(alloc_id);
+}
diff --git a/src/tools/miri/tests/pass/tree-borrows/reserved.stderr b/src/tools/miri/tests/pass/tree-borrows/reserved.stderr
new file mode 100644
index 00000000000..d76ee0f8266
--- /dev/null
+++ b/src/tools/miri/tests/pass/tree-borrows/reserved.stderr
@@ -0,0 +1,52 @@
+[interior mut + protected] Foreign Read: Re* -> Frz
+──────────────────────────────────────────────────────────────────────
+Warning: this tree is indicative only. Some tags may have been hidden.
+0..  1
+| Re*|    └─┬──<TAG=base>
+| Re*|      ├─┬──<TAG=x>
+| Re*|      │ └─┬──<TAG=caller:x>
+| Frz|      │   └────<TAG=callee:x>
+| Re*|      └────<TAG=y,caller:y,callee:y>
+──────────────────────────────────────────────────────────────────────
+[interior mut] Foreign Read: Re* -> Re*
+──────────────────────────────────────────────────────────────────────
+Warning: this tree is indicative only. Some tags may have been hidden.
+0..  8
+| Re*|    └─┬──<TAG=base>
+| Re*|      ├────<TAG=x>
+| Re*|      └────<TAG=y>
+──────────────────────────────────────────────────────────────────────
+[interior mut] Foreign Write: Re* -> Re*
+──────────────────────────────────────────────────────────────────────
+Warning: this tree is indicative only. Some tags may have been hidden.
+0..  8
+| Act|    └─┬──<TAG=base>
+| Re*|      ├────<TAG=x>
+| Act|      └────<TAG=y>
+──────────────────────────────────────────────────────────────────────
+[protected] Foreign Read: Res -> Frz
+──────────────────────────────────────────────────────────────────────
+Warning: this tree is indicative only. Some tags may have been hidden.
+0..  1
+| Res|    └─┬──<TAG=base>
+| Res|      ├─┬──<TAG=x>
+| Res|      │ └─┬──<TAG=caller:x>
+| Frz|      │   └────<TAG=callee:x>
+| Res|      └────<TAG=y,caller:y,callee:y>
+──────────────────────────────────────────────────────────────────────
+[] Foreign Read: Res -> Res
+──────────────────────────────────────────────────────────────────────
+Warning: this tree is indicative only. Some tags may have been hidden.
+0..  1
+| Res|    └─┬──<TAG=base>
+| Res|      ├────<TAG=x>
+| Res|      └────<TAG=y>
+──────────────────────────────────────────────────────────────────────
+[] Foreign Write: Res -> Dis
+──────────────────────────────────────────────────────────────────────
+Warning: this tree is indicative only. Some tags may have been hidden.
+0..  1
+| Act|    └─┬──<TAG=base>
+| Dis|      ├────<TAG=x>
+| Act|      └────<TAG=y>
+──────────────────────────────────────────────────────────────────────
diff --git a/src/tools/miri/tests/pass/tree-borrows/transmute-unsafecell.rs b/src/tools/miri/tests/pass/tree-borrows/transmute-unsafecell.rs
new file mode 100644
index 00000000000..e1a9334ab54
--- /dev/null
+++ b/src/tools/miri/tests/pass/tree-borrows/transmute-unsafecell.rs
@@ -0,0 +1,13 @@
+//@compile-flags: -Zmiri-tree-borrows
+
+use core::cell::UnsafeCell;
+use core::mem;
+
+fn main() {
+    unsafe {
+        let x = &0i32;
+        // As long as we only read, transmuting this to UnsafeCell should be fine.
+        let cell_x: &UnsafeCell<i32> = mem::transmute(&x);
+        let _val = *cell_x.get();
+    }
+}