Auto merge of #104054 - RalfJung:byte-provenance, r=oli-obk

interpret: support for per-byte provenance

Also factors the provenance map into its own module.

The third commit does the same for the init mask. I can move it in a separate PR if you prefer.

Fixes https://github.com/rust-lang/miri/issues/2181

r? `@oli-obk`

11 files changed, 220 insertions, 88 deletions

diff --git a/src/test/ui-fulldeps/uninit_mask.rs b/src/test/ui-fulldeps/uninit_mask.rs
deleted file mode 100644
index 84ce291016a..00000000000
--- a/src/test/ui-fulldeps/uninit_mask.rs
+++ /dev/null
@@ -1,28 +0,0 @@
-// run-pass
-// ignore-cross-compile
-// ignore-stage1
-
-#![feature(rustc_private)]
-
-extern crate rustc_middle;
-extern crate rustc_target;
-
-use rustc_middle::mir::interpret::InitMask;
-use rustc_target::abi::Size;
-
-fn main() {
-    let mut mask = InitMask::new(Size::from_bytes(500), false);
-    assert!(!mask.get(Size::from_bytes(499)));
-    mask.set(Size::from_bytes(499), true);
-    assert!(mask.get(Size::from_bytes(499)));
-    mask.set_range_inbounds(Size::from_bytes(100), Size::from_bytes(256), true);
-    for i in 0..100 {
-        assert!(!mask.get(Size::from_bytes(i)));
-    }
-    for i in 100..256 {
-        assert!(mask.get(Size::from_bytes(i)));
-    }
-    for i in 256..499 {
-        assert!(!mask.get(Size::from_bytes(i)));
-    }
-}
diff --git a/src/tools/miri/src/diagnostics.rs b/src/tools/miri/src/diagnostics.rs
index ec81ffd3cd5..0cfa3812e40 100644
--- a/src/tools/miri/src/diagnostics.rs
+++ b/src/tools/miri/src/diagnostics.rs
@@ -229,13 +229,13 @@ pub fn report_error<'tcx, 'mir>(
                 Unsupported(
                     UnsupportedOpInfo::ThreadLocalStatic(_) |
                     UnsupportedOpInfo::ReadExternStatic(_) |
-                    UnsupportedOpInfo::PartialPointerOverwrite(_) | // we make memory uninit instead
+                    UnsupportedOpInfo::PartialPointerOverwrite(_) |
+                    UnsupportedOpInfo::PartialPointerCopy(_) |
                     UnsupportedOpInfo::ReadPointerAsBytes
                 ) =>
                     panic!("Error should never be raised by Miri: {kind:?}", kind = e.kind()),
                 Unsupported(
-                    UnsupportedOpInfo::Unsupported(_) |
-                    UnsupportedOpInfo::PartialPointerCopy(_)
+                    UnsupportedOpInfo::Unsupported(_)
                 ) =>
                     vec![(None, format!("this is likely not a bug in the program; it indicates that the program performed an operation that the interpreter does not support"))],
                 UndefinedBehavior(UndefinedBehaviorInfo::AlignmentCheckFailed { .. })
diff --git a/src/tools/miri/src/machine.rs b/src/tools/miri/src/machine.rs
index 231a99c1d03..5887d26462b 100644
--- a/src/tools/miri/src/machine.rs
+++ b/src/tools/miri/src/machine.rs
@@ -133,7 +133,7 @@ impl fmt::Display for MiriMemoryKind {
 }
 
 /// Pointer provenance.
-#[derive(Debug, Clone, Copy)]
+#[derive(Clone, Copy)]
 pub enum Provenance {
     Concrete {
         alloc_id: AllocId,
@@ -176,18 +176,9 @@ static_assert_size!(Pointer<Provenance>, 24);
 #[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
 static_assert_size!(Scalar<Provenance>, 32);
 
-impl interpret::Provenance for Provenance {
-    /// We use absolute addresses in the `offset` of a `Pointer<Provenance>`.
-    const OFFSET_IS_ADDR: bool = true;
-
-    /// We cannot err on partial overwrites, it happens too often in practice (due to unions).
-    const ERR_ON_PARTIAL_PTR_OVERWRITE: bool = false;
-
-    fn fmt(ptr: &Pointer<Self>, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        let (prov, addr) = ptr.into_parts(); // address is absolute
-        write!(f, "{:#x}", addr.bytes())?;
-
-        match prov {
+impl fmt::Debug for Provenance {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        match self {
             Provenance::Concrete { alloc_id, sb } => {
                 // Forward `alternate` flag to `alloc_id` printing.
                 if f.alternate() {
@@ -202,9 +193,13 @@ impl interpret::Provenance for Provenance {
                 write!(f, "[wildcard]")?;
             }
         }
-
         Ok(())
     }
+}
+
+impl interpret::Provenance for Provenance {
+    /// We use absolute addresses in the `offset` of a `Pointer<Provenance>`.
+    const OFFSET_IS_ADDR: bool = true;
 
     fn get_alloc_id(self) -> Option<AllocId> {
         match self {
diff --git a/src/tools/miri/src/tag_gc.rs b/src/tools/miri/src/tag_gc.rs
index 5aa653632f3..73712348f0d 100644
--- a/src/tools/miri/src/tag_gc.rs
+++ b/src/tools/miri/src/tag_gc.rs
@@ -127,7 +127,7 @@ impl VisitTags for Operand<Provenance> {
 
 impl VisitTags for Allocation<Provenance, AllocExtra> {
     fn visit_tags(&self, visit: &mut dyn FnMut(SbTag)) {
-        for (_size, prov) in self.provenance().iter() {
+        for prov in self.provenance().provenances() {
             prov.visit_tags(visit);
         }
 
diff --git a/src/tools/miri/tests/fail/copy_half_a_pointer.rs b/src/tools/miri/tests/fail/copy_half_a_pointer.rs
deleted file mode 100644
index e1dcdda7fdf..00000000000
--- a/src/tools/miri/tests/fail/copy_half_a_pointer.rs
+++ /dev/null
@@ -1,21 +0,0 @@
-//@normalize-stderr-test: "\+0x[48]" -> "+HALF_PTR"
-#![allow(dead_code)]
-
-// We use packed structs to get around alignment restrictions
-#[repr(packed)]
-struct Data {
-    pad: u8,
-    ptr: &'static i32,
-}
-
-static G: i32 = 0;
-
-fn main() {
-    let mut d = Data { pad: 0, ptr: &G };
-
-    // Get a pointer to the beginning of the Data struct (one u8 byte, then the pointer bytes).
-    let d_alias = &mut d as *mut _ as *mut *const u8;
-    unsafe {
-        let _x = d_alias.read_unaligned(); //~ERROR: unable to copy parts of a pointer
-    }
-}
diff --git a/src/tools/miri/tests/fail/copy_half_a_pointer.stderr b/src/tools/miri/tests/fail/copy_half_a_pointer.stderr
deleted file mode 100644
index 21797757084..00000000000
--- a/src/tools/miri/tests/fail/copy_half_a_pointer.stderr
+++ /dev/null
@@ -1,14 +0,0 @@
-error: unsupported operation: unable to copy parts of a pointer from memory at ALLOC+HALF_PTR
-  --> $DIR/copy_half_a_pointer.rs:LL:CC
-   |
-LL |         let _x = d_alias.read_unaligned();
-   |                  ^^^^^^^^^^^^^^^^^^^^^^^^ unable to copy parts of a pointer from memory at ALLOC+HALF_PTR
-   |
-   = help: this is likely not a bug in the program; it indicates that the program performed an operation that the interpreter does not support
-   = note: BACKTRACE:
-   = note: inside `main` at $DIR/copy_half_a_pointer.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/pointer_partial_overwrite.rs b/src/tools/miri/tests/fail/provenance/pointer_partial_overwrite.rs
index 63f0649b8ed..d3a68fbdd01 100644
--- a/src/tools/miri/tests/fail/pointer_partial_overwrite.rs
+++ b/src/tools/miri/tests/fail/provenance/pointer_partial_overwrite.rs
@@ -2,16 +2,13 @@
 //@compile-flags: -Zmiri-disable-alignment-check -Zmiri-disable-stacked-borrows -Zmiri-disable-validation
 
 // Test what happens when we overwrite parts of a pointer.
-// Also see <https://github.com/rust-lang/miri/issues/2181>.
 
 fn main() {
     let mut p = &42;
     unsafe {
         let ptr: *mut _ = &mut p;
-        *(ptr as *mut u8) = 123; // if we ever support 8 bit pointers, this is gonna cause
-        // "attempted to interpret some raw bytes as a pointer address" instead of
-        // "attempted to read undefined bytes"
+        *(ptr as *mut u8) = 123; // this removes provenance from one of the bytes, meaning the entire ptr is considered to have no provenance.
     }
-    let x = *p; //~ ERROR: this operation requires initialized memory
+    let x = *p; //~ ERROR: no provenance
     panic!("this should never print: {}", x);
 }
diff --git a/src/tools/miri/tests/fail/pointer_partial_overwrite.stderr b/src/tools/miri/tests/fail/provenance/pointer_partial_overwrite.stderr
index 7d10b75e880..06e5ede8c77 100644
--- a/src/tools/miri/tests/fail/pointer_partial_overwrite.stderr
+++ b/src/tools/miri/tests/fail/provenance/pointer_partial_overwrite.stderr
@@ -1,8 +1,8 @@
-error: Undefined Behavior: using uninitialized data, but this operation requires initialized memory
+error: Undefined Behavior: dereferencing pointer failed: $HEX[noalloc] is a dangling pointer (it has no provenance)
   --> $DIR/pointer_partial_overwrite.rs:LL:CC
    |
 LL |     let x = *p;
-   |             ^^ using uninitialized data, but this operation requires initialized memory
+   |             ^^ dereferencing pointer failed: $HEX[noalloc] is a dangling pointer (it has no provenance)
    |
    = 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
diff --git a/src/tools/miri/tests/fail/uninit_buffer_with_provenance.rs b/src/tools/miri/tests/fail/uninit_buffer_with_provenance.rs
new file mode 100644
index 00000000000..170bc6e1ed1
--- /dev/null
+++ b/src/tools/miri/tests/fail/uninit_buffer_with_provenance.rs
@@ -0,0 +1,32 @@
+//@error-pattern: memory is uninitialized at [0x4..0x8]
+//@normalize-stderr-test: "a[0-9]+" -> "ALLOC"
+#![feature(strict_provenance)]
+
+// Test printing allocations that contain single-byte provenance.
+
+use std::alloc::{alloc, dealloc, Layout};
+use std::mem::{self, MaybeUninit};
+use std::slice::from_raw_parts;
+
+fn byte_with_provenance<T>(val: u8, prov: *const T) -> MaybeUninit<u8> {
+    let ptr = prov.with_addr(val as usize);
+    let bytes: [MaybeUninit<u8>; mem::size_of::<*const ()>()] = unsafe { mem::transmute(ptr) };
+    let lsb = if cfg!(target_endian = "little") { 0 } else { bytes.len() - 1 };
+    bytes[lsb]
+}
+
+fn main() {
+    let layout = Layout::from_size_align(16, 8).unwrap();
+    unsafe {
+        let ptr = alloc(layout);
+        let ptr_raw = ptr.cast::<MaybeUninit<u8>>();
+        *ptr_raw.add(0) = byte_with_provenance(0x42, &42u8);
+        *ptr.add(1) = 0x12;
+        *ptr.add(2) = 0x13;
+        *ptr_raw.add(3) = byte_with_provenance(0x43, &0u8);
+        let slice1 = from_raw_parts(ptr, 8);
+        let slice2 = from_raw_parts(ptr.add(8), 8);
+        drop(slice1.cmp(slice2));
+        dealloc(ptr, layout);
+    }
+}
diff --git a/src/tools/miri/tests/fail/uninit_buffer_with_provenance.stderr b/src/tools/miri/tests/fail/uninit_buffer_with_provenance.stderr
new file mode 100644
index 00000000000..715d76aa1c2
--- /dev/null
+++ b/src/tools/miri/tests/fail/uninit_buffer_with_provenance.stderr
@@ -0,0 +1,32 @@
+error: Undefined Behavior: reading memory at ALLOC[0x0..0x8], but memory is uninitialized at [0x4..0x8], and this operation requires initialized memory
+  --> RUSTLIB/core/src/slice/cmp.rs:LL:CC
+   |
+LL |         let mut order = unsafe { memcmp(left.as_ptr(), right.as_ptr(), len) as isize };
+   |                                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ reading memory at ALLOC[0x0..0x8], but memory is uninitialized at [0x4..0x8], and this operation requires initialized memory
+   |
+   = 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:
+   = note: inside `<u8 as core::slice::cmp::SliceOrd>::compare` at RUSTLIB/core/src/slice/cmp.rs:LL:CC
+   = note: inside `core::slice::cmp::<impl std::cmp::Ord for [u8]>::cmp` at RUSTLIB/core/src/slice/cmp.rs:LL:CC
+note: inside `main` at $DIR/uninit_buffer_with_provenance.rs:LL:CC
+  --> $DIR/uninit_buffer_with_provenance.rs:LL:CC
+   |
+LL |         drop(slice1.cmp(slice2));
+   |              ^^^^^^^^^^^^^^^^^^
+
+note: some details are omitted, run with `MIRIFLAGS=-Zmiri-backtrace=full` for a verbose backtrace
+
+Uninitialized memory occurred at ALLOC[0x4..0x8], in this allocation:
+ALLOC (Rust heap, size: 16, align: 8) {
+    ╾42[ALLOC]<TAG> (1 ptr byte)╼ 12 13 ╾43[ALLOC]<TAG> (1 ptr byte)╼ __ __ __ __ __ __ __ __ __ __ __ __ │ ━..━░░░░░░░░░░░░
+}
+ALLOC (global (static or const), size: 1, align: 1) {
+    2a                                              │ *
+}
+ALLOC (global (static or const), size: 1, align: 1) {
+    00                                              │ .
+}
+
+error: aborting due to previous error
+
diff --git a/src/tools/miri/tests/pass/provenance.rs b/src/tools/miri/tests/pass/provenance.rs
new file mode 100644
index 00000000000..b18d903e36c
--- /dev/null
+++ b/src/tools/miri/tests/pass/provenance.rs
@@ -0,0 +1,139 @@
+#![feature(strict_provenance)]
+#![feature(pointer_byte_offsets)]
+use std::{mem, ptr};
+
+const PTR_SIZE: usize = mem::size_of::<&i32>();
+
+fn main() {
+    basic();
+    partial_overwrite_then_restore();
+    bytewise_ptr_methods();
+    bytewise_custom_memcpy();
+    bytewise_custom_memcpy_chunked();
+}
+
+/// Some basic smoke tests for provenance.
+fn basic() {
+    let x = &42;
+    let ptr = x as *const i32;
+    let addr: usize = unsafe { mem::transmute(ptr) }; // an integer without provenance
+    // But we can give provenance back via `with_addr`.
+    let ptr_back = ptr.with_addr(addr);
+    assert_eq!(unsafe { *ptr_back }, 42);
+
+    // It is preserved by MaybeUninit.
+    let addr_mu: mem::MaybeUninit<usize> = unsafe { mem::transmute(ptr) };
+    let ptr_back: *const i32 = unsafe { mem::transmute(addr_mu) };
+    assert_eq!(unsafe { *ptr_back }, 42);
+}
+
+/// Overwrite one byte of a pointer, then restore it.
+fn partial_overwrite_then_restore() {
+    unsafe fn ptr_bytes<'x>(ptr: &'x mut *const i32) -> &'x mut [mem::MaybeUninit<u8>; PTR_SIZE] {
+        mem::transmute(ptr)
+    }
+
+    // Returns a value with the same provenance as `x` but 0 for the integer value.
+    // `x` must be initialized.
+    unsafe fn zero_with_provenance(x: mem::MaybeUninit<u8>) -> mem::MaybeUninit<u8> {
+        let ptr = [x; PTR_SIZE];
+        let ptr: *const i32 = mem::transmute(ptr);
+        let mut ptr = ptr.with_addr(0);
+        ptr_bytes(&mut ptr)[0]
+    }
+
+    unsafe {
+        let ptr = &42;
+        let mut ptr = ptr as *const i32;
+        // Get a bytewise view of the pointer.
+        let ptr_bytes = ptr_bytes(&mut ptr);
+
+        // The highest bytes must be 0 for this to work.
+        let hi = if cfg!(target_endian = "little") { ptr_bytes.len() - 1 } else { 0 };
+        assert_eq!(*ptr_bytes[hi].as_ptr().cast::<u8>(), 0);
+        // Overwrite provenance on the last byte.
+        ptr_bytes[hi] = mem::MaybeUninit::new(0);
+        // Restore it from the another byte.
+        ptr_bytes[hi] = zero_with_provenance(ptr_bytes[1]);
+
+        // Now ptr should be good again.
+        assert_eq!(*ptr, 42);
+    }
+}
+
+fn bytewise_ptr_methods() {
+    let mut ptr1 = &1;
+    let mut ptr2 = &2;
+
+    // Swap them, bytewise.
+    unsafe {
+        ptr::swap_nonoverlapping(
+            &mut ptr1 as *mut _ as *mut mem::MaybeUninit<u8>,
+            &mut ptr2 as *mut _ as *mut mem::MaybeUninit<u8>,
+            mem::size_of::<&i32>(),
+        );
+    }
+
+    // Make sure they still work.
+    assert_eq!(*ptr1, 2);
+    assert_eq!(*ptr2, 1);
+
+    // TODO: also test ptr::swap, ptr::copy, ptr::copy_nonoverlapping.
+}
+
+fn bytewise_custom_memcpy() {
+    unsafe fn memcpy<T>(to: *mut T, from: *const T) {
+        let to = to.cast::<mem::MaybeUninit<u8>>();
+        let from = from.cast::<mem::MaybeUninit<u8>>();
+        for i in 0..mem::size_of::<T>() {
+            let b = from.add(i).read();
+            to.add(i).write(b);
+        }
+    }
+
+    let ptr1 = &1;
+    let mut ptr2 = &2;
+
+    // Copy, bytewise.
+    unsafe { memcpy(&mut ptr2, &ptr1) };
+
+    // Make sure they still work.
+    assert_eq!(*ptr1, 1);
+    assert_eq!(*ptr2, 1);
+}
+
+fn bytewise_custom_memcpy_chunked() {
+    unsafe fn memcpy<T>(to: *mut T, from: *const T) {
+        assert!(mem::size_of::<T>() % mem::size_of::<usize>() == 0);
+        let count = mem::size_of::<T>() / mem::size_of::<usize>();
+        let to = to.cast::<mem::MaybeUninit<usize>>();
+        let from = from.cast::<mem::MaybeUninit<usize>>();
+        for i in 0..count {
+            let b = from.add(i).read();
+            to.add(i).write(b);
+        }
+    }
+
+    // Prepare an array where pointers are stored at... interesting... offsets.
+    let mut data = [0usize; 2 * PTR_SIZE];
+    let mut offsets = vec![];
+    for i in 0..mem::size_of::<usize>() {
+        // We have 2*PTR_SIZE room for each of these pointers.
+        let base = i * 2 * PTR_SIZE;
+        // This one is mis-aligned by `i`.
+        let offset = base + i;
+        offsets.push(offset);
+        // Store it there.
+        unsafe { data.as_mut_ptr().byte_add(offset).cast::<&i32>().write_unaligned(&42) };
+    }
+
+    // Now memcpy that.
+    let mut data2 = [0usize; 2 * PTR_SIZE];
+    unsafe { memcpy(&mut data2, &data) };
+
+    // And check the result.
+    for &offset in &offsets {
+        let ptr = unsafe { data2.as_ptr().byte_add(offset).cast::<&i32>().read_unaligned() };
+        assert_eq!(*ptr, 42);
+    }
+}