Rollup merge of #118029 - saethlin:allocid-gc, r=RalfJung

Expand Miri's BorTag GC to a Provenance GC

As suggested in https://github.com/rust-lang/miri/issues/3080#issuecomment-1732505573

We previously solved memory growth issues associated with the Stacked Borrows and Tree Borrows runtimes with a GC. But of course we also have state accumulation associated with whole allocations elsewhere in the interpreter, and this PR starts tackling those.

To do this, we expand the visitor for the GC so that it can visit a BorTag or an AllocId. Instead of collecting all live AllocIds into a single HashSet, we just collect from the Machine itself then go through an accessor `InterpCx::is_alloc_live` which checks a number of allocation data structures in the core interpreter. This avoids the overhead of all the inserts that collecting their keys would require.

r? ``@RalfJung``

13 files changed, 46 insertions, 11 deletions

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
index 465679b72c3..3769575765e 100644
--- 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
@@ -1,4 +1,4 @@
-//@compile-flags: -Zmiri-tree-borrows -Zmiri-tag-gc=0
+//@compile-flags: -Zmiri-tree-borrows -Zmiri-provenance-gc=0
 
 // Check how a Reserved with interior mutability
 // responds to a Foreign Write under a Protector
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
index 1e6e2eebd26..e2956759d0b 100644
--- 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
@@ -1,4 +1,4 @@
-//@compile-flags: -Zmiri-tree-borrows -Zmiri-tag-gc=0
+//@compile-flags: -Zmiri-tree-borrows -Zmiri-provenance-gc=0
 
 #[path = "../../../utils/mod.rs"]
 #[macro_use]
diff --git a/src/tools/miri/tests/pass-dep/extra_fn_ptr_gc.rs b/src/tools/miri/tests/pass-dep/extra_fn_ptr_gc.rs
new file mode 100644
index 00000000000..716119a0fc3
--- /dev/null
+++ b/src/tools/miri/tests/pass-dep/extra_fn_ptr_gc.rs
@@ -0,0 +1,21 @@
+//@ignore-target-windows: No libc on Windows
+//@compile-flags: -Zmiri-permissive-provenance
+
+#[path = "../utils/mod.rs"]
+mod utils;
+
+type GetEntropyFn = unsafe extern "C" fn(*mut u8, libc::size_t) -> libc::c_int;
+
+fn main() {
+    let name = "getentropy\0";
+    let addr = unsafe { libc::dlsym(libc::RTLD_DEFAULT, name.as_ptr() as *const _) as usize };
+    // If the GC does not account for the extra_fn_ptr entry that this dlsym just added, this GC
+    // run will delete our entry for the base addr of the function pointer we will transmute to,
+    // and the call through the function pointer will report UB.
+    utils::run_provenance_gc();
+
+    let ptr = addr as *mut libc::c_void;
+    let func: GetEntropyFn = unsafe { std::mem::transmute(ptr) };
+    let dest = &mut [0u8];
+    unsafe { func(dest.as_mut_ptr(), dest.len()) };
+}
diff --git a/src/tools/miri/tests/pass/0weak_memory_consistency.rs b/src/tools/miri/tests/pass/0weak_memory_consistency.rs
index abfe3b0adeb..1cbccb2eebd 100644
--- a/src/tools/miri/tests/pass/0weak_memory_consistency.rs
+++ b/src/tools/miri/tests/pass/0weak_memory_consistency.rs
@@ -1,4 +1,6 @@
-//@compile-flags: -Zmiri-ignore-leaks -Zmiri-disable-stacked-borrows
+//@compile-flags: -Zmiri-ignore-leaks -Zmiri-disable-stacked-borrows -Zmiri-provenance-gc=10000
+// This test's runtime explodes if the GC interval is set to 1 (which we do in CI), so we
+// override it internally back to the default frequency.
 
 // The following tests check whether our weak memory emulation produces
 // any inconsistent execution outcomes
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
index 398b542ed4c..e6310f8eda6 100644
--- a/src/tools/miri/tests/pass/tree_borrows/cell-alternate-writes.rs
+++ b/src/tools/miri/tests/pass/tree_borrows/cell-alternate-writes.rs
@@ -1,4 +1,4 @@
-//@compile-flags: -Zmiri-tree-borrows -Zmiri-tag-gc=0
+//@compile-flags: -Zmiri-tree-borrows -Zmiri-provenance-gc=0
 #[path = "../../utils/mod.rs"]
 #[macro_use]
 mod utils;
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
index fecc3360434..4d941850e54 100644
--- a/src/tools/miri/tests/pass/tree_borrows/end-of-protector.rs
+++ b/src/tools/miri/tests/pass/tree_borrows/end-of-protector.rs
@@ -1,4 +1,4 @@
-//@compile-flags: -Zmiri-tree-borrows -Zmiri-tag-gc=0
+//@compile-flags: -Zmiri-tree-borrows -Zmiri-provenance-gc=0
 
 // Check that a protector goes back to normal behavior when the function
 // returns.
diff --git a/src/tools/miri/tests/pass/tree_borrows/formatting.rs b/src/tools/miri/tests/pass/tree_borrows/formatting.rs
index f22c408ad25..c4360f0dbb9 100644
--- a/src/tools/miri/tests/pass/tree_borrows/formatting.rs
+++ b/src/tools/miri/tests/pass/tree_borrows/formatting.rs
@@ -1,4 +1,4 @@
-//@compile-flags: -Zmiri-tree-borrows -Zmiri-tag-gc=0
+//@compile-flags: -Zmiri-tree-borrows -Zmiri-provenance-gc=0
 
 #[path = "../../utils/mod.rs"]
 #[macro_use]
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
index a38cd6d2894..7a5fd395c7f 100644
--- a/src/tools/miri/tests/pass/tree_borrows/reborrow-is-read.rs
+++ b/src/tools/miri/tests/pass/tree_borrows/reborrow-is-read.rs
@@ -1,4 +1,4 @@
-//@compile-flags: -Zmiri-tree-borrows -Zmiri-tag-gc=0
+//@compile-flags: -Zmiri-tree-borrows -Zmiri-provenance-gc=0
 
 #[path = "../../utils/mod.rs"]
 #[macro_use]
diff --git a/src/tools/miri/tests/pass/tree_borrows/reserved.rs b/src/tools/miri/tests/pass/tree_borrows/reserved.rs
index 8d0beab66f4..ef47d30e2ef 100644
--- a/src/tools/miri/tests/pass/tree_borrows/reserved.rs
+++ b/src/tools/miri/tests/pass/tree_borrows/reserved.rs
@@ -1,4 +1,4 @@
-//@compile-flags: -Zmiri-tree-borrows -Zmiri-tag-gc=0
+//@compile-flags: -Zmiri-tree-borrows -Zmiri-provenance-gc=0
 
 #[path = "../../utils/mod.rs"]
 #[macro_use]
diff --git a/src/tools/miri/tests/pass/tree_borrows/unique.rs b/src/tools/miri/tests/pass/tree_borrows/unique.rs
index 44e2e813625..6c5ed9efcee 100644
--- a/src/tools/miri/tests/pass/tree_borrows/unique.rs
+++ b/src/tools/miri/tests/pass/tree_borrows/unique.rs
@@ -1,5 +1,5 @@
 //@revisions: default uniq
-//@compile-flags: -Zmiri-tree-borrows -Zmiri-tag-gc=0
+//@compile-flags: -Zmiri-tree-borrows -Zmiri-provenance-gc=0
 //@[uniq]compile-flags: -Zmiri-unique-is-unique
 
 #![feature(ptr_internals)]
diff --git a/src/tools/miri/tests/pass/tree_borrows/vec_unique.rs b/src/tools/miri/tests/pass/tree_borrows/vec_unique.rs
index e5d0a683a72..8d0f4bd0fe7 100644
--- a/src/tools/miri/tests/pass/tree_borrows/vec_unique.rs
+++ b/src/tools/miri/tests/pass/tree_borrows/vec_unique.rs
@@ -1,5 +1,5 @@
 //@revisions: default uniq
-//@compile-flags: -Zmiri-tree-borrows -Zmiri-tag-gc=0
+//@compile-flags: -Zmiri-tree-borrows -Zmiri-provenance-gc=0
 //@[uniq]compile-flags: -Zmiri-unique-is-unique
 
 #![feature(vec_into_raw_parts)]
diff --git a/src/tools/miri/tests/utils/miri_extern.rs b/src/tools/miri/tests/utils/miri_extern.rs
index c0ef2c50641..7363c189840 100644
--- a/src/tools/miri/tests/utils/miri_extern.rs
+++ b/src/tools/miri/tests/utils/miri_extern.rs
@@ -84,7 +84,7 @@ extern "Rust" {
     ///
     /// The format of what this emits is unstable and may change at any time. In particular, users should be
     /// aware that Miri will periodically attempt to garbage collect the contents of all stacks. Callers of
-    /// this function may wish to pass `-Zmiri-tag-gc=0` to disable the GC.
+    /// this function may wish to pass `-Zmiri-provenance-gc=0` to disable the GC.
     ///
     /// This function is extremely unstable. At any time the format of its output may change, its signature may
     /// change, or it may be removed entirely.
@@ -137,4 +137,9 @@ extern "Rust" {
         out: *mut std::ffi::c_char,
         out_size: usize,
     ) -> usize;
+
+    /// Run the provenance GC. The GC will run automatically at some cadence,
+    /// but in tests we want to for sure run it at certain points to check
+    /// that it doesn't break anything.
+    pub fn miri_run_provenance_gc();
 }
diff --git a/src/tools/miri/tests/utils/mod.rs b/src/tools/miri/tests/utils/mod.rs
index 7b7dc231a50..6386162e095 100644
--- a/src/tools/miri/tests/utils/mod.rs
+++ b/src/tools/miri/tests/utils/mod.rs
@@ -9,3 +9,10 @@ mod miri_extern;
 
 pub use fs::*;
 pub use miri_extern::*;
+
+pub fn run_provenance_gc() {
+    // SAFETY: No preconditions. The GC is fine to run at any time.
+    unsafe {
+        miri_run_provenance_gc()
+    }
+}