diff options
111 files changed, 3785 insertions, 203 deletions
diff --git a/src/tools/miri/.github/workflows/ci.yml b/src/tools/miri/.github/workflows/ci.yml index 138a69974e1..b71f48e4644 100644 --- a/src/tools/miri/.github/workflows/ci.yml +++ b/src/tools/miri/.github/workflows/ci.yml @@ -54,8 +54,8 @@ jobs: # contains package information of crates installed via `cargo install`. ~/.cargo/.crates.toml ~/.cargo/.crates2.json - key: ${{ runner.os }}-cargo-${{ hashFiles('**/Cargo.lock') }} - restore-keys: ${{ runner.os }}-cargo + key: ${{ runner.os }}-cargo-reset20230315-${{ hashFiles('**/Cargo.lock') }} + restore-keys: ${{ runner.os }}-cargo-reset20230315 - name: Install rustup-toolchain-install-master if: ${{ steps.cache.outputs.cache-hit != 'true' }} @@ -106,8 +106,8 @@ jobs: # contains package information of crates installed via `cargo install`. ~/.cargo/.crates.toml ~/.cargo/.crates2.json - key: ${{ runner.os }}-cargo-${{ hashFiles('**/Cargo.lock') }} - restore-keys: ${{ runner.os }}-cargo + key: ${{ runner.os }}-cargo-reset20230315-${{ hashFiles('**/Cargo.lock') }} + restore-keys: ${{ runner.os }}-cargo-reset20230315 - name: Install rustup-toolchain-install-master if: ${{ steps.cache.outputs.cache-hit != 'true' }} diff --git a/src/tools/miri/CONTRIBUTING.md b/src/tools/miri/CONTRIBUTING.md index 476075e9c91..bcdb623b090 100644 --- a/src/tools/miri/CONTRIBUTING.md +++ b/src/tools/miri/CONTRIBUTING.md @@ -129,18 +129,15 @@ development version of Miri using ./miri install ``` -and then you can use it as if it was installed by `rustup`. Make sure you use -the same toolchain when calling `cargo miri` that you used when installing Miri! -Usually this means you have to write `cargo +miri miri ...` to select the `miri` -toolchain that was installed by `./miri toolchain`. +and then you can use it as if it was installed by `rustup` as a component of the +`miri` toolchain. Note that the `miri` and `cargo-miri` executables are placed +in the `miri` toolchain's sysroot to prevent conflicts with other toolchains. +The Miri binaries in the `cargo` bin directory (usually `~/.cargo/bin`) are managed by rustup. There's a test for the cargo wrapper in the `test-cargo-miri` directory; run `./run-test.py` in there to execute it. Like `./miri test`, this respects the `MIRI_TEST_TARGET` environment variable to execute the test for another target. -Note that installing Miri like this will "take away" Miri management from `rustup`. -If you want to later go back to a rustup-installed Miri, run `rustup update`. - ### Using a modified standard library Miri re-builds the standard library into a custom sysroot, so it is fairly easy diff --git a/src/tools/miri/README.md b/src/tools/miri/README.md index 1086d0481c8..b70f7e0e556 100644 --- a/src/tools/miri/README.md +++ b/src/tools/miri/README.md @@ -15,6 +15,8 @@ for example: or an invalid enum discriminant) * **Experimental**: Violations of the [Stacked Borrows] rules governing aliasing for reference types +* **Experimental**: Violations of the Tree Borrows aliasing rules, as an optional + alternative to [Stacked Borrows] * **Experimental**: Data races On top of that, Miri will also tell you about memory leaks: when there is memory @@ -225,6 +227,26 @@ degree documented below): reduced feature set. We might ship Miri with a nightly even when some features on these targets regress. +### Running tests in parallel + +Though it implements Rust threading, Miri itself is a single-threaded interpreter. +This means that when running `cargo miri test`, you will probably see a dramatic +increase in the amount of time it takes to run your whole test suite due to the +inherent interpreter slowdown and a loss of parallelism. + +You can get your test suite's parallelism back by running `cargo miri nextest run -jN` +(note that you will need [`cargo-nextest`](https://nexte.st) installed). +This works because `cargo-nextest` collects a list of all tests then launches a +separate `cargo miri run` for each test. You will need to specify a `-j` or `--test-threads`; +by default `cargo miri nextest run` runs one test at a time. For more details, see the +[`cargo-nextest` Miri documentation](https://nexte.st/book/miri.html). + +Note: This one-test-per-process model means that `cargo miri test` is able to detect data +races where two tests race on a shared resource, but `cargo miri nextest run` will not detect +such races. + +Note: `cargo-nextest` does not support doctests, see https://github.com/nextest-rs/nextest/issues/16 + ### Common Problems When using the above instructions, you may encounter a number of confusing compiler @@ -337,9 +359,11 @@ to Miri failing to detect cases of undefined behavior in a program. * `-Zmiri-disable-data-race-detector` disables checking for data races. Using this flag is **unsound**. This implies `-Zmiri-disable-weak-memory-emulation`. * `-Zmiri-disable-stacked-borrows` disables checking the experimental - [Stacked Borrows] aliasing rules. This can make Miri run faster, but it also - means no aliasing violations will be detected. Using this flag is **unsound** - (but the affected soundness rules are experimental). + aliasing rules to track borrows ([Stacked Borrows] and Tree Borrows). + This can make Miri run faster, but it also means no aliasing violations will + be detected. Using this flag is **unsound** (but the affected soundness rules + are experimental). Later flags take precedence: borrow tracking can be reactivated + by `-Zmiri-tree-borrows`. * `-Zmiri-disable-validation` disables enforcing validity invariants, which are enforced by default. This is mostly useful to focus on other failures (such as out-of-bounds accesses) first. Setting this flag means Miri can miss bugs @@ -401,6 +425,9 @@ to Miri failing to detect cases of undefined behavior in a program. * `-Zmiri-track-weak-memory-loads` shows a backtrace when weak memory emulation returns an outdated value from a load. This can help diagnose problems that disappear under `-Zmiri-disable-weak-memory-emulation`. +* `-Zmiri-tree-borrows` replaces [Stacked Borrows] with the Tree Borrows rules. + The soundness rules are already experimental without this flag, but even more + so with this flag. * `-Zmiri-force-page-size=<num>` overrides the default page size for an architecture, in multiples of 1k. `4` is default for most targets. This value should always be a power of 2 and nonzero. @@ -415,7 +442,7 @@ Some native rustc `-Z` flags are also very relevant for Miri: functions. This is needed so that Miri can execute such functions, so Miri sets this flag per default. * `-Zmir-emit-retag` controls whether `Retag` statements are emitted. Miri - enables this per default because it is needed for [Stacked Borrows]. + enables this per default because it is needed for [Stacked Borrows] and Tree Borrows. Moreover, Miri recognizes some environment variables: @@ -481,120 +508,8 @@ binaries, and as such worth documenting: ## Miri `extern` functions Miri provides some `extern` functions that programs can import to access -Miri-specific functionality: - -```rust -#[cfg(miri)] -extern "Rust" { - /// Miri-provided extern function to mark the block `ptr` points to as a "root" - /// for some static memory. This memory and everything reachable by it is not - /// considered leaking even if it still exists when the program terminates. - /// - /// `ptr` has to point to the beginning of an allocated block. - fn miri_static_root(ptr: *const u8); - - // Miri-provided extern function to get the amount of frames in the current backtrace. - // The `flags` argument must be `0`. - fn miri_backtrace_size(flags: u64) -> usize; - - /// Miri-provided extern function to obtain a backtrace of the current call stack. - /// This writes a slice of pointers into `buf` - each pointer is an opaque value - /// that is only useful when passed to `miri_resolve_frame`. - /// `buf` must have `miri_backtrace_size(0) * pointer_size` bytes of space. - /// The `flags` argument must be `1`. - fn miri_get_backtrace(flags: u64, buf: *mut *mut ()); - - /// Miri-provided extern function to resolve a frame pointer obtained - /// from `miri_get_backtrace`. The `flags` argument must be `1`, - /// and `MiriFrame` should be declared as follows: - /// - /// ```rust - /// #[repr(C)] - /// struct MiriFrame { - /// // The size of the name of the function being executed, encoded in UTF-8 - /// name_len: usize, - /// // The size of filename of the function being executed, encoded in UTF-8 - /// filename_len: usize, - /// // The line number currently being executed in `filename`, starting from '1'. - /// lineno: u32, - /// // The column number currently being executed in `filename`, starting from '1'. - /// colno: u32, - /// // The function pointer to the function currently being executed. - /// // This can be compared against function pointers obtained by - /// // casting a function (e.g. `my_fn as *mut ()`) - /// fn_ptr: *mut () - /// } - /// ``` - /// - /// The fields must be declared in exactly the same order as they appear in `MiriFrame` above. - /// This function can be called on any thread (not just the one which obtained `frame`). - fn miri_resolve_frame(frame: *mut (), flags: u64) -> MiriFrame; - - /// Miri-provided extern function to get the name and filename of the frame provided by `miri_resolve_frame`. - /// `name_buf` and `filename_buf` should be allocated with the `name_len` and `filename_len` fields of `MiriFrame`. - /// The flags argument must be `0`. - fn miri_resolve_frame_names(ptr: *mut (), flags: u64, name_buf: *mut u8, filename_buf: *mut u8); - - /// Miri-provided extern function to begin unwinding with the given payload. - /// - /// This is internal and unstable and should not be used; we give it here - /// just to be complete. - fn miri_start_panic(payload: *mut u8) -> !; - - /// Miri-provided extern function to get the internal unique identifier for the allocation that a pointer - /// points to. If this pointer is invalid (not pointing to an allocation), interpretation will abort. - /// - /// This is only useful as an input to `miri_print_borrow_stacks`, and it is a separate call because - /// getting a pointer to an allocation at runtime can change the borrow stacks in the allocation. - /// This function should be considered unstable. It exists only to support `miri_print_borrow_stacks` and so - /// inherits all of its instability. - fn miri_get_alloc_id(ptr: *const ()) -> u64; - - /// Miri-provided extern function to print (from the interpreter, not the program) the contents of all - /// borrow stacks in an allocation. The leftmost tag is the bottom of the stack. - /// 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 is extremely unstable. At any time the format of its output may change, its signature may - /// change, or it may be removed entirely. - fn miri_print_borrow_stacks(alloc_id: u64); - - /// Miri-provided extern function to print (from the interpreter, not the - /// program) the contents of a section of program memory, as bytes. Bytes - /// written using this function will emerge from the interpreter's stdout. - fn miri_write_to_stdout(bytes: &[u8]); - - /// Miri-provided extern function to print (from the interpreter, not the - /// program) the contents of a section of program memory, as bytes. Bytes - /// written using this function will emerge from the interpreter's stderr. - fn miri_write_to_stderr(bytes: &[u8]); - - /// Miri-provided extern function to allocate memory from the interpreter. - /// - /// This is useful when no fundamental way of allocating memory is - /// available, e.g. when using `no_std` + `alloc`. - fn miri_alloc(size: usize, align: usize) -> *mut u8; - - /// Miri-provided extern function to deallocate memory. - fn miri_dealloc(ptr: *mut u8, size: usize, align: usize); - - /// Convert a path from the host Miri runs on to the target Miri interprets. - /// Performs conversion of path separators as needed. - /// - /// Usually Miri performs this kind of conversion automatically. However, manual conversion - /// might be necessary when reading an environment variable that was set on the host - /// (such as TMPDIR) and using it as a target path. - /// - /// Only works with isolation disabled. - /// - /// `in` must point to a null-terminated string, and will be read as the input host path. - /// `out` must point to at least `out_size` many bytes, and the result will be stored there - /// with a null terminator. - /// Returns 0 if the `out` buffer was large enough, and the required size otherwise. - fn miri_host_to_target_path(path: *const std::ffi::c_char, out: *mut std::ffi::c_char, out_size: usize) -> usize; -} -``` +Miri-specific functionality. They are declared in +[/tests/utils/miri\_extern.rs](/tests/utils/miri_extern.rs). ## Contributing and getting help diff --git a/src/tools/miri/ci.sh b/src/tools/miri/ci.sh index 60450d09815..ef52a37fe31 100755 --- a/src/tools/miri/ci.sh +++ b/src/tools/miri/ci.sh @@ -62,8 +62,8 @@ function run_tests { if [ "$HOST_TARGET" = x86_64-unknown-linux-gnu ]; then # These act up on Windows (`which miri` produces a filename that does not exist?!?), # so let's do this only on Linux. Also makes sure things work without these set. - export RUSTC=$(which rustc) - export MIRI=$(which miri) + export RUSTC=$(which rustc) # Produces a warning unless we also set MIRI + export MIRI=$(rustc +miri --print sysroot)/bin/miri fi mkdir -p .cargo echo 'build.rustc-wrapper = "thisdoesnotexist"' > .cargo/config.toml diff --git a/src/tools/miri/miri b/src/tools/miri/miri index 0c0bbbc7020..1073ff499ba 100755 --- a/src/tools/miri/miri +++ b/src/tools/miri/miri @@ -6,8 +6,8 @@ USAGE=$(cat <<"EOF" ./miri install <flags>: Installs the miri driver and cargo-miri. <flags> are passed to `cargo install`. Sets up the rpath such that the installed binary should work in any -working directory. However, the rustup toolchain when invoking `cargo miri` -needs to be the same one used for `./miri install`. +working directory. Note that the binaries are placed in the `miri` toolchain +sysroot, to prevent conflicts with other toolchains. ./miri build <flags>: Just build miri. <flags> are passed to `cargo build`. @@ -281,8 +281,9 @@ find_sysroot() { case "$COMMAND" in install) # "--locked" to respect the Cargo.lock file if it exists. - $CARGO install $CARGO_EXTRA_FLAGS --path "$MIRIDIR" --force --locked "$@" - $CARGO install $CARGO_EXTRA_FLAGS --path "$MIRIDIR"/cargo-miri --force --locked "$@" + # Install binaries to the miri toolchain's sysroot so they do not interact with other toolchains. + $CARGO install $CARGO_EXTRA_FLAGS --path "$MIRIDIR" --force --locked --root "$SYSROOT" "$@" + $CARGO install $CARGO_EXTRA_FLAGS --path "$MIRIDIR"/cargo-miri --force --locked --root "$SYSROOT" "$@" ;; check) # Check, and let caller control flags. diff --git a/src/tools/miri/rust-version b/src/tools/miri/rust-version index 53ec1ba0821..18c2561242a 100644 --- a/src/tools/miri/rust-version +++ b/src/tools/miri/rust-version @@ -1 +1 @@ -c4e0cd966062ca67daed20775f4e8a60c28e57df +511364e7874dba9649a264100407e4bffe7b5425 diff --git a/src/tools/miri/src/bin/miri.rs b/src/tools/miri/src/bin/miri.rs index a2caeb97297..6fe3fa7fb1b 100644 --- a/src/tools/miri/src/bin/miri.rs +++ b/src/tools/miri/src/bin/miri.rs @@ -32,7 +32,7 @@ use rustc_middle::{ }; use rustc_session::{config::CrateType, search_paths::PathKind, CtfeBacktrace}; -use miri::{BacktraceStyle, ProvenanceMode, RetagFields}; +use miri::{BacktraceStyle, BorrowTrackerMethod, ProvenanceMode, RetagFields}; struct MiriCompilerCalls { miri_config: miri::MiriConfig, @@ -317,6 +317,8 @@ fn main() { miri_config.validate = false; } else if arg == "-Zmiri-disable-stacked-borrows" { miri_config.borrow_tracker = None; + } else if arg == "-Zmiri-tree-borrows" { + miri_config.borrow_tracker = Some(BorrowTrackerMethod::TreeBorrows); } else if arg == "-Zmiri-disable-data-race-detector" { miri_config.data_race_detector = false; miri_config.weak_memory_emulation = false; diff --git a/src/tools/miri/src/borrow_tracker/mod.rs b/src/tools/miri/src/borrow_tracker/mod.rs index 9f6cbe7f3c7..ed958329f95 100644 --- a/src/tools/miri/src/borrow_tracker/mod.rs +++ b/src/tools/miri/src/borrow_tracker/mod.rs @@ -11,6 +11,7 @@ use rustc_target::abi::Size; use crate::*; pub mod stacked_borrows; +pub mod tree_borrows; pub type CallId = NonZeroU64; @@ -230,8 +231,10 @@ impl GlobalStateInner { /// Which borrow tracking method to use #[derive(Debug, Copy, Clone, PartialEq, Eq)] pub enum BorrowTrackerMethod { - /// Stacked Borrows, as implemented in borrow_tracker/stacked + /// Stacked Borrows, as implemented in borrow_tracker/stacked_borrows StackedBorrows, + /// Tree borrows, as implemented in borrow_tracker/tree_borrows + TreeBorrows, } impl BorrowTrackerMethod { @@ -258,6 +261,10 @@ impl GlobalStateInner { AllocState::StackedBorrows(Box::new(RefCell::new(Stacks::new_allocation( id, alloc_size, self, kind, machine, )))), + BorrowTrackerMethod::TreeBorrows => + AllocState::TreeBorrows(Box::new(RefCell::new(Tree::new_allocation( + id, alloc_size, self, kind, machine, + )))), } } } @@ -273,6 +280,7 @@ pub trait EvalContextExt<'mir, 'tcx: 'mir>: crate::MiriInterpCxExt<'mir, 'tcx> { let method = this.machine.borrow_tracker.as_ref().unwrap().borrow().borrow_tracker_method; match method { BorrowTrackerMethod::StackedBorrows => this.sb_retag_ptr_value(kind, val), + BorrowTrackerMethod::TreeBorrows => this.tb_retag_ptr_value(kind, val), } } @@ -285,6 +293,7 @@ pub trait EvalContextExt<'mir, 'tcx: 'mir>: crate::MiriInterpCxExt<'mir, 'tcx> { let method = this.machine.borrow_tracker.as_ref().unwrap().borrow().borrow_tracker_method; match method { BorrowTrackerMethod::StackedBorrows => this.sb_retag_place_contents(kind, place), + BorrowTrackerMethod::TreeBorrows => this.tb_retag_place_contents(kind, place), } } @@ -293,6 +302,7 @@ pub trait EvalContextExt<'mir, 'tcx: 'mir>: crate::MiriInterpCxExt<'mir, 'tcx> { let method = this.machine.borrow_tracker.as_ref().unwrap().borrow().borrow_tracker_method; match method { BorrowTrackerMethod::StackedBorrows => this.sb_retag_return_place(), + BorrowTrackerMethod::TreeBorrows => this.tb_retag_return_place(), } } @@ -301,6 +311,34 @@ pub trait EvalContextExt<'mir, 'tcx: 'mir>: crate::MiriInterpCxExt<'mir, 'tcx> { let method = this.machine.borrow_tracker.as_ref().unwrap().borrow().borrow_tracker_method; match method { BorrowTrackerMethod::StackedBorrows => this.sb_expose_tag(alloc_id, tag), + BorrowTrackerMethod::TreeBorrows => this.tb_expose_tag(alloc_id, tag), + } + } + + fn give_pointer_debug_name( + &mut self, + ptr: Pointer<Option<Provenance>>, + nth_parent: u8, + name: &str, + ) -> InterpResult<'tcx> { + let this = self.eval_context_mut(); + let method = this.machine.borrow_tracker.as_ref().unwrap().borrow().borrow_tracker_method; + match method { + BorrowTrackerMethod::StackedBorrows => { + this.tcx.tcx.sess.warn("Stacked Borrows does not support named pointers; `miri_pointer_name` is a no-op"); + Ok(()) + } + BorrowTrackerMethod::TreeBorrows => + this.tb_give_pointer_debug_name(ptr, nth_parent, name), + } + } + + fn print_borrow_state(&mut self, alloc_id: AllocId, show_unnamed: bool) -> InterpResult<'tcx> { + let this = self.eval_context_mut(); + let method = this.machine.borrow_tracker.as_ref().unwrap().borrow().borrow_tracker_method; + match method { + BorrowTrackerMethod::StackedBorrows => this.print_stacks(alloc_id), + BorrowTrackerMethod::TreeBorrows => this.print_tree(alloc_id, show_unnamed), } } } @@ -310,6 +348,8 @@ pub trait EvalContextExt<'mir, 'tcx: 'mir>: crate::MiriInterpCxExt<'mir, 'tcx> { pub enum AllocState { /// Data corresponding to Stacked Borrows StackedBorrows(Box<RefCell<stacked_borrows::AllocState>>), + /// Data corresponding to Tree Borrows + TreeBorrows(Box<RefCell<tree_borrows::AllocState>>), } impl machine::AllocExtra { @@ -328,6 +368,14 @@ impl machine::AllocExtra { _ => panic!("expected Stacked Borrows borrow tracking, got something else"), } } + + #[track_caller] + pub fn borrow_tracker_tb(&self) -> &RefCell<tree_borrows::AllocState> { + match self.borrow_tracker { + Some(AllocState::TreeBorrows(ref tb)) => tb, + _ => panic!("expected Tree Borrows borrow tracking, got something else"), + } + } } impl AllocState { @@ -341,6 +389,14 @@ impl AllocState { match self { AllocState::StackedBorrows(sb) => sb.borrow_mut().before_memory_read(alloc_id, prov_extra, range, machine), + AllocState::TreeBorrows(tb) => + tb.borrow_mut().before_memory_access( + AccessKind::Read, + alloc_id, + prov_extra, + range, + machine, + ), } } @@ -354,6 +410,14 @@ impl AllocState { match self { AllocState::StackedBorrows(sb) => sb.get_mut().before_memory_write(alloc_id, prov_extra, range, machine), + AllocState::TreeBorrows(tb) => + tb.get_mut().before_memory_access( + AccessKind::Write, + alloc_id, + prov_extra, + range, + machine, + ), } } @@ -367,12 +431,15 @@ impl AllocState { match self { AllocState::StackedBorrows(sb) => sb.get_mut().before_memory_deallocation(alloc_id, prov_extra, range, machine), + AllocState::TreeBorrows(tb) => + tb.get_mut().before_memory_deallocation(alloc_id, prov_extra, range, machine), } } pub fn remove_unreachable_tags(&self, tags: &FxHashSet<BorTag>) { match self { AllocState::StackedBorrows(sb) => sb.borrow_mut().remove_unreachable_tags(tags), + AllocState::TreeBorrows(tb) => tb.borrow_mut().remove_unreachable_tags(tags), } } } @@ -381,6 +448,7 @@ impl VisitTags for AllocState { fn visit_tags(&self, visit: &mut dyn FnMut(BorTag)) { match self { AllocState::StackedBorrows(sb) => sb.visit_tags(visit), + AllocState::TreeBorrows(tb) => tb.visit_tags(visit), } } } diff --git a/src/tools/miri/src/borrow_tracker/tree_borrows/diagnostics.rs b/src/tools/miri/src/borrow_tracker/tree_borrows/diagnostics.rs new file mode 100644 index 00000000000..97bbdee1d44 --- /dev/null +++ b/src/tools/miri/src/borrow_tracker/tree_borrows/diagnostics.rs @@ -0,0 +1,592 @@ +use rustc_data_structures::fx::FxHashMap; + +use std::fmt; +use std::ops::Range; + +use crate::borrow_tracker::tree_borrows::{ + err_tb_ub, perms::Permission, tree::LocationState, unimap::UniIndex, +}; +use crate::borrow_tracker::{AccessKind, ProtectorKind}; +use crate::*; + +/// Some information that is irrelevant for the algorithm but very +/// convenient to know about a tag for debugging and testing. +#[derive(Clone, Debug)] +pub struct NodeDebugInfo { + /// The tag in question. + pub tag: BorTag, + /// Name(s) that were associated with this tag (comma-separated). + /// Typically the name of the variable holding the corresponding + /// pointer in the source code. + /// Helps match tag numbers to human-readable names. + pub name: Option<String>, +} +impl NodeDebugInfo { + /// New node info with a name. + pub fn new(tag: BorTag) -> Self { + Self { tag, name: None } + } + + /// Add a name to the tag. If a same tag is associated to several pointers, + /// it can have several names which will be separated by commas. + fn add_name(&mut self, name: &str) { + if let Some(ref mut prev_name) = &mut self.name { + prev_name.push(','); + prev_name.push_str(name); + } else { + self.name = Some(String::from(name)); + } + } +} + +impl fmt::Display for NodeDebugInfo { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + if let Some(ref name) = self.name { + write!(f, "{tag:?} (also named '{name}')", tag = self.tag) + } else { + write!(f, "{tag:?}", tag = self.tag) + } + } +} + +impl<'tcx> Tree { + /// Climb the tree to get the tag of a distant ancestor. + /// Allows operations on tags that are unreachable by the program + /// but still exist in the tree. Not guaranteed to perform consistently + /// if `tag-gc=1`. + fn nth_parent(&self, tag: BorTag, nth_parent: u8) -> Option<BorTag> { + let mut idx = self.tag_mapping.get(&tag).unwrap(); + for _ in 0..nth_parent { + let node = self.nodes.get(idx).unwrap(); + idx = node.parent?; + } + Some(self.nodes.get(idx).unwrap().tag) + } + + /// Debug helper: assign name to tag. + pub fn give_pointer_debug_name( + &mut self, + tag: BorTag, + nth_parent: u8, + name: &str, + ) -> InterpResult<'tcx> { + let tag = self.nth_parent(tag, nth_parent).unwrap(); + let idx = self.tag_mapping.get(&tag).unwrap(); + if let Some(node) = self.nodes.get_mut(idx) { + node.debug_info.add_name(name); + } else { + eprintln!("Tag {tag:?} (to be named '{name}') not found!"); + } + Ok(()) + } + + /// Debug helper: determines if the tree contains a tag. + pub fn is_allocation_of(&self, tag: BorTag) -> bool { + self.tag_mapping.contains_key(&tag) + } +} + +#[derive(Debug, Clone, Copy)] +pub(super) enum TransitionError { + /// This access is not allowed because some parent tag has insufficient permissions. + /// For example, if a tag is `Frozen` and encounters a child write this will + /// produce a `ChildAccessForbidden(Frozen)`. + /// This kind of error can only occur on child accesses. + ChildAccessForbidden(Permission), + /// A protector was triggered due to an invalid transition that loses + /// too much permissions. + /// For example, if a protected tag goes from `Active` to `Frozen` due + /// to a foreign write this will produce a `ProtectedTransition(Active, Frozen)`. + /// This kind of error can only occur on foreign accesses. + ProtectedTransition(Permission, Permission), + /// Cannot deallocate because some tag in the allocation is strongly protected. + /// This kind of error can only occur on deallocations. + ProtectedDealloc, +} + +/// Failures that can occur during the execution of Tree Borrows procedures. +pub(super) struct TbError<'node> { + /// What failure occurred. + pub error_kind: TransitionError, + /// The tag on which the error was triggered. + /// On protector violations, this is the tag that was protected. + /// On accesses rejected due to insufficient permissions, this is the + /// tag that lacked those permissions. + pub faulty_tag: &'node NodeDebugInfo, + /// Whether this was a Read or Write access. This field is ignored + /// when the error was triggered by a deallocation. + pub access_kind: AccessKind, + /// Which tag the access that caused this error was made through, i.e. + /// which tag was used to read/write/deallocate. + pub tag_of_access: &'node NodeDebugInfo, +} + +impl TbError<'_> { + /// Produce a UB error. + pub fn build<'tcx>(self) -> InterpErrorInfo<'tcx> { + use TransitionError::*; + err_tb_ub(match self.error_kind { + ChildAccessForbidden(perm) => { + format!( + "{kind} through {initial} is forbidden because it is a child of {current} which is {perm}.", + kind=self.access_kind, + initial=self.tag_of_access, + current=self.faulty_tag, + perm=perm, + ) + } + ProtectedTransition(start, end) => { + format!( + "{kind} through {initial} is forbidden because it is a foreign tag for {current}, which would hence change from {start} to {end}, but {current} is protected", + current=self.faulty_tag, + start=start, + end=end, + kind=self.access_kind, + initial=self.tag_of_access, + ) + } + ProtectedDealloc => { + format!( + "the allocation of {initial} also contains {current} which is strongly protected, cannot deallocate", + initial=self.tag_of_access, + current=self.faulty_tag, + ) + } + }).into() + } +} + +type S = &'static str; +/// Pretty-printing details +/// +/// Example: +/// ``` +/// DisplayFmtWrapper { +/// top: '>', +/// bot: '<', +/// warning_text: "Some tags have been hidden", +/// } +/// ``` +/// will wrap the entire text with +/// ```text +/// >>>>>>>>>>>>>>>>>>>>>>>>>> +/// Some tags have been hidden +/// +/// [ main display here ] +/// +/// <<<<<<<<<<<<<<<<<<<<<<<<<< +/// ``` +struct DisplayFmtWrapper { + /// Character repeated to make the upper border. + top: char, + /// Character repeated to make the lower border. + bot: char, + /// Warning about some tags (unnamed) being hidden. + warning_text: S, +} + +/// Formating of the permissions on each range. +/// +/// Example: +/// ``` +/// DisplayFmtPermission { +/// open: "[", +/// sep: "|", +/// close: "]", +/// uninit: "___", +/// range_sep: "..", +/// } +/// ``` +/// will show each permission line as +/// ```text +/// 0.. 1.. 2.. 3.. 4.. 5 +/// [Act|Res|Frz|Dis|___] +/// ``` +struct DisplayFmtPermission { + /// Text that starts the permission block. + open: S, + /// Text that separates permissions on different ranges. + sep: S, + /// Text that ends the permission block. + close: S, + /// Text to show when a permission is not initialized. + /// Should have the same width as a `Permission`'s `.short_name()`, i.e. + /// 3 if using the `Res/Act/Frz/Dis` notation. + uninit: S, + /// Text to separate the `start` and `end` values of a range. + range_sep: S, +} + +/// Formating of the tree structure. +/// +/// Example: +/// ``` +/// DisplayFmtPadding { +/// join_middle: "|-", +/// join_last: "'-", +/// join_haschild: "-+-", +/// join_default: "---", +/// indent_middle: "| ", +/// indent_last: " ", +/// } +/// ``` +/// will show the tree as +/// ```text +/// -+- root +/// |--+- a +/// | '--+- b +/// | '---- c +/// |--+- d +/// | '---- e +/// '---- f +/// ``` +struct DisplayFmtPadding { + /// Connector for a child other than the last. + join_middle: S, + /// Connector for the last child. Should have the same width as `join_middle`. + join_last: S, + /// Connector for a node that itself has a child. + join_haschild: S, + /// Connector for a node that does not have a child. Should have the same width + /// as `join_haschild`. + join_default: S, + /// Indentation when there is a next child. + indent_middle: S, + /// Indentation for the last child. + indent_last: S, +} +/// How to show whether a location has been accessed +/// +/// Example: +/// ``` +/// DisplayFmtAccess { +/// yes: " ", +/// no: "?", +/// meh: "_", +/// } +/// ``` +/// will show states as +/// ```text +/// Act +/// ?Res +/// ____ +/// ``` +struct DisplayFmtAccess { + /// Used when `State.initialized = true`. + yes: S, + /// Used when `State.initialized = false`. + /// Should have the same width as `yes`. + no: S, + /// Used when there is no `State`. + /// Should have the same width as `yes`. + meh: S, +} + +/// All parameters to determine how the tree is formated. +struct DisplayFmt { + wrapper: DisplayFmtWrapper, + perm: DisplayFmtPermission, + padding: DisplayFmtPadding, + accessed: DisplayFmtAccess, +} +impl DisplayFmt { + /// Print the permission with the format + /// ` Res`/` Re*`/` Act`/` Frz`/` Dis` for accessed locations + /// and `?Res`/`?Re*`/`?Act`/`?Frz`/`?Dis` for unaccessed locations. + fn print_perm(&self, perm: Option<LocationState>) -> String { + if let Some(perm) = perm { + format!( + "{ac}{st}", + ac = if perm.is_initialized() { self.accessed.yes } else { self.accessed.no }, + st = perm.permission().short_name(), + ) + } else { + format!("{}{}", self.accessed.meh, self.perm.uninit) + } + } + + /// Print the tag with the format `<XYZ>` if the tag is unnamed, + /// and `<XYZ=name>` if the tag is named. + fn print_tag(&self, tag: BorTag, name: &Option<String>) -> String { + let printable_tag = tag.get(); + if let Some(name) = name { + format!("<{printable_tag}={name}>") + } else { + format!("<{printable_tag}>") + } + } + + /// Print extra text if the tag has a protector. + fn print_protector(&self, protector: Option<&ProtectorKind>) -> &'static str { + protector + .map(|p| { + match *p { + ProtectorKind::WeakProtector => " Weakly protected", + ProtectorKind::StrongProtector => " Strongly protected", + } + }) + .unwrap_or("") + } +} + +/// Track the indentation of the tree. +struct DisplayIndent { + curr: String, +} +impl DisplayIndent { + fn new() -> Self { + Self { curr: " ".to_string() } + } + + /// Increment the indentation by one. Note: need to know if this + /// is the last child or not because the presence of other children + /// changes the way the indentation is shown. + fn increment(&mut self, formatter: &DisplayFmt, is_last: bool) { + self.curr.push_str(if is_last { + formatter.padding.indent_last + } else { + formatter.padding.indent_middle + }); + } + + /// Pop the last level of indentation. + fn decrement(&mut self, formatter: &DisplayFmt) { + for _ in 0..formatter.padding.indent_last.len() { + let _ = self.curr.pop(); + } + } + + /// Print the current indentation. + fn write(&self, s: &mut String) { + s.push_str(&self.curr); + } +} + +/// Repeat a character a number of times. +fn char_repeat(c: char, n: usize) -> String { + std::iter::once(c).cycle().take(n).collect::<String>() +} + +/// Extracted information from the tree, in a form that is readily accessible +/// for printing. I.e. resolve parent-child pointers into an actual tree, +/// zip permissions with their tag, remove wrappers, stringify data. +struct DisplayRepr { + tag: BorTag, + name: Option<String>, + rperm: Vec<Option<LocationState>>, + children: Vec<DisplayRepr>, +} + +impl DisplayRepr { + fn from(tree: &Tree, show_unnamed: bool) -> Option<Self> { + let mut v = Vec::new(); + extraction_aux(tree, tree.root, show_unnamed, &mut v); + let Some(root) = v.pop() else { + if show_unnamed { + unreachable!("This allocation contains no tags, not even a root. This should not happen."); + } + eprintln!("This allocation does not contain named tags. Use `miri_print_borrow_state(_, true)` to also print unnamed tags."); + return None; + }; + assert!(v.is_empty()); + return Some(root); + + fn extraction_aux( + tree: &Tree, + idx: UniIndex, + show_unnamed: bool, + acc: &mut Vec<DisplayRepr>, + ) { + let node = tree.nodes.get(idx).unwrap(); + let name = node.debug_info.name.clone(); + let children_sorted = { + let mut children = node.children.iter().cloned().collect::<Vec<_>>(); + children.sort_by_key(|idx| tree.nodes.get(*idx).unwrap().tag); + children + }; + if !show_unnamed && name.is_none() { + // We skip this node + for child_idx in children_sorted { + extraction_aux(tree, child_idx, show_unnamed, acc); + } + } else { + // We take this node + let rperm = tree + .rperms + .iter_all() + .map(move |(_offset, perms)| { + let perm = perms.get(idx); + perm.cloned() + }) + .collect::<Vec<_>>(); + let mut children = Vec::new(); + for child_idx in children_sorted { + extraction_aux(tree, child_idx, show_unnamed, &mut children); + } + acc.push(DisplayRepr { tag: node.tag, name, rperm, children }); + } + } + } + fn print( + &self, + fmt: &DisplayFmt, + indenter: &mut DisplayIndent, + protected_tags: &FxHashMap<BorTag, ProtectorKind>, + ranges: Vec<Range<u64>>, + print_warning: bool, + ) { + let mut block = Vec::new(); + // Push the header and compute the required paddings for the body. + // Header looks like this: `0.. 1.. 2.. 3.. 4.. 5.. 6.. 7.. 8`, + // and is properly aligned with the `|` of the body. + let (range_header, range_padding) = { + let mut header_top = String::new(); + header_top.push_str("0.."); + let mut padding = Vec::new(); + for (i, range) in ranges.iter().enumerate() { + if i > 0 { + header_top.push_str(fmt.perm.range_sep); + } + let s = range.end.to_string(); + let l = s.chars().count() + fmt.perm.range_sep.chars().count(); + { + let target_len = + fmt.perm.uninit.chars().count() + fmt.accessed.yes.chars().count() + 1; + let tot_len = target_len.max(l); + let header_top_pad_len = target_len.saturating_sub(l); + let body_pad_len = tot_len.saturating_sub(target_len); + header_top.push_str(&format!("{}{}", char_repeat(' ', header_top_pad_len), s)); + padding.push(body_pad_len); + } + } + ([header_top], padding) + }; + for s in range_header { + block.push(s); + } + // This is the actual work + print_aux( + self, + &range_padding, + fmt, + indenter, + protected_tags, + true, /* root _is_ the last child */ + &mut block, + ); + // Then it's just prettifying it with a border of dashes. + { + let wr = &fmt.wrapper; + let max_width = { + let block_width = block.iter().map(|s| s.chars().count()).max().unwrap(); + if print_warning { + block_width.max(wr.warning_text.chars().count()) + } else { + block_width + } + }; + eprintln!("{}", char_repeat(wr.top, max_width)); + if print_warning { + eprintln!("{}", wr.warning_text,); + } + for line in block { + eprintln!("{line}"); + } + eprintln!("{}", char_repeat(wr.bot, max_width)); + } + + // Here is the function that does the heavy lifting + fn print_aux( + tree: &DisplayRepr, + padding: &[usize], + fmt: &DisplayFmt, + indent: &mut DisplayIndent, + protected_tags: &FxHashMap<BorTag, ProtectorKind>, + is_last_child: bool, + acc: &mut Vec<String>, + ) { + let mut line = String::new(); + // Format the permissions on each range. + // Looks like `| Act| Res| Res| Act|`. + line.push_str(fmt.perm.open); + for (i, (perm, &pad)) in tree.rperm.iter().zip(padding.iter()).enumerate() { + if i > 0 { + line.push_str(fmt.perm.sep); + } + let show_perm = fmt.print_perm(*perm); + line.push_str(&format!("{}{}", char_repeat(' ', pad), show_perm)); + } + line.push_str(fmt.perm.close); + // Format the tree structure. + // Main difficulty is handling the indentation properly. + indent.write(&mut line); + { + // padding + line.push_str(if is_last_child { + fmt.padding.join_last + } else { + fmt.padding.join_middle + }); + line.push_str(fmt.padding.join_default); + line.push_str(if tree.children.is_empty() { + fmt.padding.join_default + } else { + fmt.padding.join_haschild + }); + line.push_str(fmt.padding.join_default); + line.push_str(fmt.padding.join_default); + } + line.push_str(&fmt.print_tag(tree.tag, &tree.name)); + let protector = protected_tags.get(&tree.tag); + line.push_str(fmt.print_protector(protector)); + // Push the line to the accumulator then recurse. + acc.push(line); + let nb_children = tree.children.len(); + for (i, child) in tree.children.iter().enumerate() { + indent.increment(fmt, is_last_child); + print_aux(child, padding, fmt, indent, protected_tags, i + 1 == nb_children, acc); + indent.decrement(fmt); + } + } + } +} + +const DEFAULT_FORMATTER: DisplayFmt = DisplayFmt { + wrapper: DisplayFmtWrapper { + top: '─', + bot: '─', + warning_text: "Warning: this tree is indicative only. Some tags may have been hidden.", + }, + perm: DisplayFmtPermission { open: "|", sep: "|", close: "|", uninit: "---", range_sep: ".." }, + padding: DisplayFmtPadding { + join_middle: "├", + join_last: "└", + indent_middle: "│ ", + indent_last: " ", + join_haschild: "┬", + join_default: "─", + }, + accessed: DisplayFmtAccess { yes: " ", no: "?", meh: "-" }, +}; + +impl<'tcx> Tree { + /// Display the contents of the tree. + pub fn print_tree( + &self, + protected_tags: &FxHashMap<BorTag, ProtectorKind>, + show_unnamed: bool, + ) -> InterpResult<'tcx> { + let mut indenter = DisplayIndent::new(); + let ranges = self.rperms.iter_all().map(|(range, _perms)| range).collect::<Vec<_>>(); + if let Some(repr) = DisplayRepr::from(self, show_unnamed) { + repr.print( + &DEFAULT_FORMATTER, + &mut indenter, + protected_tags, + ranges, + /* print warning message about tags not shown */ !show_unnamed, + ); + } + Ok(()) + } +} diff --git a/src/tools/miri/src/borrow_tracker/tree_borrows/mod.rs b/src/tools/miri/src/borrow_tracker/tree_borrows/mod.rs new file mode 100644 index 00000000000..2297ceb1259 --- /dev/null +++ b/src/tools/miri/src/borrow_tracker/tree_borrows/mod.rs @@ -0,0 +1,539 @@ +use log::trace; + +use rustc_target::abi::{Abi, Size}; + +use crate::borrow_tracker::{AccessKind, GlobalStateInner, ProtectorKind, RetagFields}; +use rustc_middle::{ + mir::{Mutability, RetagKind}, + ty::{ + self, + layout::{HasParamEnv, LayoutOf}, + Ty, + }, +}; + +use crate::*; + +mod diagnostics; +mod perms; +mod tree; +mod unimap; +use perms::Permission; +pub use tree::Tree; + +pub type AllocState = Tree; + +pub fn err_tb_ub<'tcx>(msg: String) -> InterpError<'tcx> { + err_machine_stop!(TerminationInfo::TreeBorrowsUb { msg }) +} + +impl<'tcx> Tree { + /// Create a new allocation, i.e. a new tree + pub fn new_allocation( + id: AllocId, + size: Size, + state: &mut GlobalStateInner, + _kind: MemoryKind<machine::MiriMemoryKind>, + machine: &MiriMachine<'_, 'tcx>, + ) -> Self { + let tag = state.base_ptr_tag(id, machine); // Fresh tag for the root + Tree::new(tag, size) + } + + /// Check that an access on the entire range is permitted, and update + /// the tree. + pub fn before_memory_access( + &mut self, + access_kind: AccessKind, + alloc_id: AllocId, + prov: ProvenanceExtra, + range: AllocRange, + machine: &MiriMachine<'_, 'tcx>, + ) -> InterpResult<'tcx> { + trace!( + "{} with tag {:?}: {:?}, size {}", + access_kind, + prov, + Pointer::new(alloc_id, range.start), + range.size.bytes(), + ); + // TODO: for now we bail out on wildcard pointers. Eventually we should + // handle them as much as we can. + let tag = match prov { + ProvenanceExtra::Concrete(tag) => tag, + ProvenanceExtra::Wildcard => return Ok(()), + }; + let global = machine.borrow_tracker.as_ref().unwrap(); + self.perform_access(access_kind, tag, range, global) + } + + /// Check that this pointer has permission to deallocate this range. + pub fn before_memory_deallocation( + &mut self, + _alloc_id: AllocId, + prov: ProvenanceExtra, + range: AllocRange, + machine: &MiriMachine<'_, 'tcx>, + ) -> InterpResult<'tcx> { + // TODO: for now we bail out on wildcard pointers. Eventually we should + // handle them as much as we can. + let tag = match prov { + ProvenanceExtra::Concrete(tag) => tag, + ProvenanceExtra::Wildcard => return Ok(()), + }; + let global = machine.borrow_tracker.as_ref().unwrap(); + self.dealloc(tag, range, global) + } + + pub fn expose_tag(&mut self, _tag: BorTag) { + // TODO + } +} + +/// Policy for a new borrow. +#[derive(Debug, Clone, Copy)] +struct NewPermission { + /// Whether this borrow requires a read access on its parent. + /// `perform_read_access` is `true` for all pointers marked `dereferenceable`. + perform_read_access: bool, + /// Which permission should the pointer start with. + initial_state: Permission, + /// Whether this pointer is part of the arguments of a function call. + /// `protector` is `Some(_)` for all pointers marked `noalias`. + protector: Option<ProtectorKind>, +} + +impl<'tcx> NewPermission { + /// Determine NewPermission of the reference from the type of the pointee. + fn from_ref_ty( + pointee: Ty<'tcx>, + mutability: Mutability, + kind: RetagKind, + cx: &crate::MiriInterpCx<'_, 'tcx>, + ) -> Option<Self> { + let ty_is_freeze = pointee.is_freeze(*cx.tcx, cx.param_env()); + let ty_is_unpin = pointee.is_unpin(*cx.tcx, cx.param_env()); + let initial_state = match mutability { + Mutability::Mut if ty_is_unpin => Permission::new_unique_2phase(ty_is_freeze), + Mutability::Not if ty_is_freeze => Permission::new_frozen(), + // Raw pointers never enter this function so they are not handled. + // However raw pointers are not the only pointers that take the parent + // tag, this also happens for `!Unpin` `&mut`s and interior mutable + // `&`s, which are excluded above. + _ => return None, + }; + // This field happens to be redundant since right now we always do a read, + // but it could be useful in the future. + let perform_read_access = true; + + let protector = (kind == RetagKind::FnEntry).then_some(ProtectorKind::StrongProtector); + Some(Self { perform_read_access, initial_state, protector }) + } + + // Boxes are not handled by `from_ref_ty`, they need special behavior + // implemented here. + fn from_box_ty( + ty: Ty<'tcx>, + kind: RetagKind, + cx: &crate::MiriInterpCx<'_, 'tcx>, + ) -> Option<Self> { + let pointee = ty.builtin_deref(true).unwrap().ty; + pointee.is_unpin(*cx.tcx, cx.param_env()).then_some(()).map(|()| { + // Regular `Unpin` box, give it `noalias` but only a weak protector + // because it is valid to deallocate it within the function. + let ty_is_freeze = ty.is_freeze(*cx.tcx, cx.param_env()); + Self { + perform_read_access: true, + initial_state: Permission::new_unique_2phase(ty_is_freeze), + protector: (kind == RetagKind::FnEntry).then_some(ProtectorKind::WeakProtector), + } + }) + } +} + +/// Retagging/reborrowing. +/// Policy on which permission to grant to each pointer should be left to +/// the implementation of NewPermission. +impl<'mir: 'ecx, 'tcx: 'mir, 'ecx> EvalContextPrivExt<'mir, 'tcx, 'ecx> + for crate::MiriInterpCx<'mir, 'tcx> +{ +} +trait EvalContextPrivExt<'mir: 'ecx, 'tcx: 'mir, 'ecx>: crate::MiriInterpCxExt<'mir, 'tcx> { + /// Returns the `AllocId` the reborrow was done in, if there is some actual + /// memory associated with this pointer. Returns `None` if there is no actual + /// memory allocated. Also checks that the reborrow of size `ptr_size` is + /// within bounds of the allocation. + /// + /// Also returns the tag that the pointer should get, which is essentially + /// `if new_perm.is_some() { new_tag } else { parent_tag }` along with + /// some logging (always) and fake reads (if `new_perm` is + /// `Some(NewPermission { perform_read_access: true }`). + fn tb_reborrow( + &mut self, + place: &MPlaceTy<'tcx, Provenance>, // parent tag extracted from here + ptr_size: Size, + new_perm: Option<NewPermission>, + new_tag: BorTag, + ) -> InterpResult<'tcx, Option<(AllocId, BorTag)>> { + let this = self.eval_context_mut(); + + // It is crucial that this gets called on all code paths, to ensure we track tag creation. + let log_creation = |this: &MiriInterpCx<'mir, 'tcx>, + loc: Option<(AllocId, Size, ProvenanceExtra)>| // alloc_id, base_offset, orig_tag + -> InterpResult<'tcx> { + let global = this.machine.borrow_tracker.as_ref().unwrap().borrow(); + let ty = place.layout.ty; + if global.tracked_pointer_tags.contains(&new_tag) { + let kind_str = format!("{new_perm:?} (pointee type {ty})"); + this.emit_diagnostic(NonHaltingDiagnostic::CreatedPointerTag( + new_tag.inner(), + Some(kind_str), + loc.map(|(alloc_id, base_offset, orig_tag)| (alloc_id, alloc_range(base_offset, ptr_size), orig_tag)), + )); + } + drop(global); // don't hold that reference any longer than we have to + Ok(()) + }; + + let (alloc_id, base_offset, parent_prov) = if ptr_size > Size::ZERO { + this.ptr_get_alloc_id(place.ptr)? + } else { + match this.ptr_try_get_alloc_id(place.ptr) { + Ok(data) => data, + Err(_) => { + // This pointer doesn't come with an AllocId, so there's no + // memory to do retagging in. + trace!( + "reborrow of size 0: reference {:?} derived from {:?} (pointee {})", + new_tag, + place.ptr, + place.layout.ty, + ); + log_creation(this, None)?; + return Ok(None); + } + } + }; + let orig_tag = match parent_prov { + ProvenanceExtra::Wildcard => return Ok(None), // TODO: handle wildcard pointers + ProvenanceExtra::Concrete(tag) => tag, + }; + + // Protection against trying to get a reference to a vtable: + // vtables do not have an alloc_extra so the call to + // `get_alloc_extra` that follows fails. + let (alloc_size, _align, alloc_kind) = this.get_alloc_info(alloc_id); + if ptr_size == Size::ZERO && !matches!(alloc_kind, AllocKind::LiveData) { + return Ok(Some((alloc_id, orig_tag))); + } + + log_creation(this, Some((alloc_id, base_offset, parent_prov)))?; + + // Ensure we bail out if the pointer goes out-of-bounds (see miri#1050). + if base_offset + ptr_size > alloc_size { + throw_ub!(PointerOutOfBounds { + alloc_id, + alloc_size, + ptr_offset: this.target_usize_to_isize(base_offset.bytes()), + ptr_size, + msg: CheckInAllocMsg::InboundsTest + }); + } + + trace!( + "reborrow: reference {:?} derived from {:?} (pointee {}): {:?}, size {}", + new_tag, + orig_tag, + place.layout.ty, + Pointer::new(alloc_id, base_offset), + ptr_size.bytes() + ); + + let Some(new_perm) = new_perm else { return Ok(Some((alloc_id, orig_tag))); }; + + if let Some(protect) = new_perm.protector { + // We register the protection in two different places. + // This makes creating a protector slower, but checking whether a tag + // is protected faster. + this.frame_mut().extra.borrow_tracker.as_mut().unwrap().protected_tags.push(new_tag); + this.machine + .borrow_tracker + .as_mut() + .expect("We should have borrow tracking data") + .get_mut() + .protected_tags + .insert(new_tag, protect); + } + + let alloc_extra = this.get_alloc_extra(alloc_id)?; + let range = alloc_range(base_offset, ptr_size); + let mut tree_borrows = alloc_extra.borrow_tracker_tb().borrow_mut(); + + if new_perm.perform_read_access { + // Count this reborrow as a read access + let global = &this.machine.borrow_tracker.as_ref().unwrap(); + tree_borrows.perform_access(AccessKind::Read, orig_tag, range, global)?; + if let Some(data_race) = alloc_extra.data_race.as_ref() { + data_race.read(alloc_id, range, &this.machine)?; + } + } + + // Record the parent-child pair in the tree. + tree_borrows.new_child(orig_tag, new_tag, new_perm.initial_state, range)?; + Ok(Some((alloc_id, new_tag))) + } + + /// Retags an indidual pointer, returning the retagged version. + fn tb_retag_reference( + &mut self, + val: &ImmTy<'tcx, Provenance>, + new_perm: Option<NewPermission>, + ) -> InterpResult<'tcx, ImmTy<'tcx, Provenance>> { + let this = self.eval_context_mut(); + // We want a place for where the ptr *points to*, so we get one. + let place = this.ref_to_mplace(val)?; + + // Get a lower bound of the size of this place. + // (When `extern type` are involved, use the size of the known prefix.) + let size = this + .size_and_align_of_mplace(&place)? + .map(|(size, _)| size) + .unwrap_or(place.layout.size); + + // This new tag is not guaranteed to actually be used. + // + // If you run out of tags, consider the following optimization: adjust `tb_reborrow` + // so that rather than taking as input a fresh tag and deciding whether it uses this + // one or the parent it instead just returns whether a new tag should be created. + // This will avoid creating tags than end up never being used. + let new_tag = this.machine.borrow_tracker.as_mut().unwrap().get_mut().new_ptr(); + + // Compute the actual reborrow. + let reborrowed = this.tb_reborrow(&place, size, new_perm, new_tag)?; + + // Adjust pointer. + let new_place = place.map_provenance(|p| { + p.map(|prov| { + match reborrowed { + Some((alloc_id, actual_tag)) => { + // If `reborrow` could figure out the AllocId of this ptr, hard-code it into the new one. + // Even if we started out with a wildcard, this newly retagged pointer is tied to that allocation. + Provenance::Concrete { alloc_id, tag: actual_tag } + } + None => { + // Looks like this has to stay a wildcard pointer. + assert!(matches!(prov, Provenance::Wildcard)); + Provenance::Wildcard + } + } + }) + }); + + // Return new pointer. + Ok(ImmTy::from_immediate(new_place.to_ref(this), val.layout)) + } +} + +impl<'mir, 'tcx: 'mir> EvalContextExt<'mir, 'tcx> for crate::MiriInterpCx<'mir, 'tcx> {} +pub trait EvalContextExt<'mir, 'tcx: 'mir>: crate::MiriInterpCxExt<'mir, 'tcx> { + /// Retag a pointer. References are passed to `from_ref_ty` and + /// raw pointers are never reborrowed. + fn tb_retag_ptr_value( + &mut self, + kind: RetagKind, + val: &ImmTy<'tcx, Provenance>, + ) -> InterpResult<'tcx, ImmTy<'tcx, Provenance>> { + let this = self.eval_context_mut(); + let new_perm = if let &ty::Ref(_, pointee, mutability) = val.layout.ty.kind() { + NewPermission::from_ref_ty(pointee, mutability, kind, this) + } else { + None + }; + this.tb_retag_reference(val, new_perm) + } + + /// Retag all pointers that are stored in this place. + fn tb_retag_place_contents( + &mut self, + kind: RetagKind, + place: &PlaceTy<'tcx, Provenance>, + ) -> InterpResult<'tcx> { + let this = self.eval_context_mut(); + let retag_fields = this.machine.borrow_tracker.as_mut().unwrap().get_mut().retag_fields; + let mut visitor = RetagVisitor { ecx: this, kind, retag_fields }; + return visitor.visit_value(place); + + // The actual visitor. + struct RetagVisitor<'ecx, 'mir, 'tcx> { + ecx: &'ecx mut MiriInterpCx<'mir, 'tcx>, + kind: RetagKind, + retag_fields: RetagFields, + } + impl<'ecx, 'mir, 'tcx> RetagVisitor<'ecx, 'mir, 'tcx> { + #[inline(always)] // yes this helps in our benchmarks + fn retag_ptr_inplace( + &mut self, + place: &PlaceTy<'tcx, Provenance>, + new_perm: Option<NewPermission>, + ) -> InterpResult<'tcx> { + let val = self.ecx.read_immediate(&self.ecx.place_to_op(place)?)?; + let val = self.ecx.tb_retag_reference(&val, new_perm)?; + self.ecx.write_immediate(*val, place)?; + Ok(()) + } + } + impl<'ecx, 'mir, 'tcx> MutValueVisitor<'mir, 'tcx, MiriMachine<'mir, 'tcx>> + for RetagVisitor<'ecx, 'mir, 'tcx> + { + type V = PlaceTy<'tcx, Provenance>; + + #[inline(always)] + fn ecx(&mut self) -> &mut MiriInterpCx<'mir, 'tcx> { + self.ecx + } + + fn visit_box(&mut self, place: &PlaceTy<'tcx, Provenance>) -> InterpResult<'tcx> { + let new_perm = NewPermission::from_box_ty(place.layout.ty, self.kind, self.ecx); + self.retag_ptr_inplace(place, new_perm) + } + + fn visit_value(&mut self, place: &PlaceTy<'tcx, Provenance>) -> InterpResult<'tcx> { + // If this place is smaller than a pointer, we know that it can't contain any + // pointers we need to retag, so we can stop recursion early. + // This optimization is crucial for ZSTs, because they can contain way more fields + // than we can ever visit. + if place.layout.is_sized() && place.layout.size < self.ecx.pointer_size() { + return Ok(()); + } + + // Check the type of this value to see what to do with it (retag, or recurse). + match place.layout.ty.kind() { + &ty::Ref(_, pointee, mutability) => { + let new_perm = + NewPermission::from_ref_ty(pointee, mutability, self.kind, self.ecx); + self.retag_ptr_inplace(place, new_perm)?; + } + ty::RawPtr(_) => { + // We definitely do *not* want to recurse into raw pointers -- wide raw + // pointers have fields, and for dyn Trait pointees those can have reference + // type! + // We also do not want to reborrow them. + } + ty::Adt(adt, _) if adt.is_box() => { + // Recurse for boxes, they require some tricky handling and will end up in `visit_box` above. + // (Yes this means we technically also recursively retag the allocator itself + // even if field retagging is not enabled. *shrug*) + self.walk_value(place)?; + } + _ => { + // Not a reference/pointer/box. Only recurse if configured appropriately. + let recurse = match self.retag_fields { + RetagFields::No => false, + RetagFields::Yes => true, + RetagFields::OnlyScalar => { + // Matching `ArgAbi::new` at the time of writing, only fields of + // `Scalar` and `ScalarPair` ABI are considered. + matches!(place.layout.abi, Abi::Scalar(..) | Abi::ScalarPair(..)) + } + }; + if recurse { + self.walk_value(place)?; + } + } + } + + Ok(()) + } + } + } + + /// After a stack frame got pushed, retag the return place so that we are sure + /// it does not alias with anything. + /// + /// This is a HACK because there is nothing in MIR that would make the retag + /// explicit. Also see <https://github.com/rust-lang/rust/issues/71117>. + fn tb_retag_return_place(&mut self) -> InterpResult<'tcx> { + let this = self.eval_context_mut(); + //this.debug_hint_location(); + let return_place = &this.frame().return_place; + if return_place.layout.is_zst() { + // There may not be any memory here, nothing to do. + return Ok(()); + } + // We need this to be in-memory to use tagged pointers. + let return_place = this.force_allocation(&return_place.clone())?; + + // We have to turn the place into a pointer to use the existing code. + // (The pointer type does not matter, so we use a raw pointer.) + let ptr_layout = this.layout_of(this.tcx.mk_mut_ptr(return_place.layout.ty))?; + let val = ImmTy::from_immediate(return_place.to_ref(this), ptr_layout); + // Reborrow it. With protection! That is part of the point. + // FIXME: do we truly want a 2phase borrow here? + let new_perm = Some(NewPermission { + initial_state: Permission::new_unique_2phase(/*freeze*/ false), + perform_read_access: true, + protector: Some(ProtectorKind::StrongProtector), + }); + let val = this.tb_retag_reference(&val, new_perm)?; + // And use reborrowed pointer for return place. + let return_place = this.ref_to_mplace(&val)?; + this.frame_mut().return_place = return_place.into(); + + Ok(()) + } + + /// Mark the given tag as exposed. It was found on a pointer with the given AllocId. + fn tb_expose_tag(&mut self, alloc_id: AllocId, tag: BorTag) -> InterpResult<'tcx> { + let this = self.eval_context_mut(); + + // Function pointers and dead objects don't have an alloc_extra so we ignore them. + // This is okay because accessing them is UB anyway, no need for any Tree Borrows checks. + // NOT using `get_alloc_extra_mut` since this might be a read-only allocation! + let (_size, _align, kind) = this.get_alloc_info(alloc_id); + match kind { + AllocKind::LiveData => { + // This should have alloc_extra data, but `get_alloc_extra` can still fail + // if converting this alloc_id from a global to a local one + // uncovers a non-supported `extern static`. + let alloc_extra = this.get_alloc_extra(alloc_id)?; + trace!("Stacked Borrows tag {tag:?} exposed in {alloc_id:?}"); + alloc_extra.borrow_tracker_tb().borrow_mut().expose_tag(tag); + } + AllocKind::Function | AllocKind::VTable | AllocKind::Dead => { + // No tree borrows on these allocations. + } + } + Ok(()) + } + + /// Display the tree. + fn print_tree(&mut self, alloc_id: AllocId, show_unnamed: bool) -> InterpResult<'tcx> { + let this = self.eval_context_mut(); + let alloc_extra = this.get_alloc_extra(alloc_id)?; + let tree_borrows = alloc_extra.borrow_tracker_tb().borrow(); + let borrow_tracker = &this.machine.borrow_tracker.as_ref().unwrap().borrow(); + tree_borrows.print_tree(&borrow_tracker.protected_tags, show_unnamed) + } + + /// Give a name to the pointer, usually the name it has in the source code (for debugging). + /// The name given is `name` and the pointer that receives it is the `nth_parent` + /// of `ptr` (with 0 representing `ptr` itself) + fn tb_give_pointer_debug_name( + &mut self, + ptr: Pointer<Option<Provenance>>, + nth_parent: u8, + name: &str, + ) -> InterpResult<'tcx> { + let this = self.eval_context_mut(); + let (tag, alloc_id) = match ptr.provenance { + Some(Provenance::Concrete { tag, alloc_id }) => (tag, alloc_id), + _ => { + eprintln!("Can't give the name {name} to Wildcard pointer"); + return Ok(()); + } + }; + let alloc_extra = this.get_alloc_extra(alloc_id)?; + let mut tree_borrows = alloc_extra.borrow_tracker_tb().borrow_mut(); + tree_borrows.give_pointer_debug_name(tag, nth_parent, name) + } +} diff --git a/src/tools/miri/src/borrow_tracker/tree_borrows/perms.rs b/src/tools/miri/src/borrow_tracker/tree_borrows/perms.rs new file mode 100644 index 00000000000..04b8e1df576 --- /dev/null +++ b/src/tools/miri/src/borrow_tracker/tree_borrows/perms.rs @@ -0,0 +1,307 @@ +use std::cmp::{Ordering, PartialOrd}; +use std::fmt; + +use crate::borrow_tracker::tree_borrows::tree::AccessRelatedness; +use crate::borrow_tracker::AccessKind; + +/// The activation states of a pointer +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +enum PermissionPriv { + /// represents: a local reference that has not yet been written to; + /// allows: child reads, foreign reads, foreign writes if type is freeze; + /// rejects: child writes (Active), foreign writes (Disabled, except if type is not freeze). + /// special case: behaves differently when protected to adhere more closely to noalias + Reserved { ty_is_freeze: bool }, + /// represents: a unique pointer; + /// allows: child reads, child writes; + /// rejects: foreign reads (Frozen), foreign writes (Disabled). + Active, + /// represents: a shared pointer; + /// allows: all read accesses; + /// rejects child writes (UB), foreign writes (Disabled). + Frozen, + /// represents: a dead pointer; + /// allows: all foreign accesses; + /// rejects: all child accesses (UB). + Disabled, +} +use PermissionPriv::*; + +impl PartialOrd for PermissionPriv { + /// PermissionPriv is ordered as follows: + /// - Reserved(_) < Active < Frozen < Disabled; + /// - different kinds of `Reserved` (with or without interior mutability) + /// are incomparable to each other. + fn partial_cmp(&self, other: &Self) -> Option<Ordering> { + use Ordering::*; + Some(match (self, other) { + (a, b) if a == b => Equal, + (Disabled, _) => Greater, + (_, Disabled) => Less, + (Frozen, _) => Greater, + (_, Frozen) => Less, + (Active, _) => Greater, + (_, Active) => Less, + (Reserved { .. }, Reserved { .. }) => return None, + }) + } +} + +/// This module controls how each permission individually reacts to an access. +/// Although these functions take `protected` as an argument, this is NOT because +/// we check protector violations here, but because some permissions behave differently +/// when protected. +mod transition { + use super::*; + /// A child node was read-accessed: UB on Disabled, noop on the rest. + fn child_read(state: PermissionPriv, _protected: bool) -> Option<PermissionPriv> { + Some(match state { + Disabled => return None, + // The inner data `ty_is_freeze` of `Reserved` is always irrelevant for Read + // accesses, since the data is not being mutated. Hence the `{ .. }` + readable @ (Reserved { .. } | Active | Frozen) => readable, + }) + } + + /// A non-child node was read-accessed: noop on non-protected Reserved, advance to Frozen otherwise. + fn foreign_read(state: PermissionPriv, protected: bool) -> Option<PermissionPriv> { + use Option::*; + Some(match state { + // The inner data `ty_is_freeze` of `Reserved` is always irrelevant for Read + // accesses, since the data is not being mutated. Hence the `{ .. }` + res @ Reserved { .. } if !protected => res, + Reserved { .. } => Frozen, // protected reserved + Active => Frozen, + non_writeable @ (Frozen | Disabled) => non_writeable, + }) + } + + /// A child node was write-accessed: `Reserved` must become `Active` to obtain + /// write permissions, `Frozen` and `Disabled` cannot obtain such permissions and produce UB. + fn child_write(state: PermissionPriv, _protected: bool) -> Option<PermissionPriv> { + Some(match state { + // A write always activates the 2-phase borrow, even with interior + // mutability + Reserved { .. } | Active => Active, + Frozen | Disabled => return None, + }) + } + + /// A non-child node was write-accessed: this makes everything `Disabled` except for + /// non-protected interior mutable `Reserved` which stay the same. + fn foreign_write(state: PermissionPriv, protected: bool) -> Option<PermissionPriv> { + Some(match state { + cell @ Reserved { ty_is_freeze: false } if !protected => cell, + _ => Disabled, + }) + } + + /// Dispatch handler depending on the kind of access and its position. + pub(super) fn perform_access( + kind: AccessKind, + rel_pos: AccessRelatedness, + child: PermissionPriv, + protected: bool, + ) -> Option<PermissionPriv> { + match (kind, rel_pos.is_foreign()) { + (AccessKind::Write, true) => foreign_write(child, protected), + (AccessKind::Read, true) => foreign_read(child, protected), + (AccessKind::Write, false) => child_write(child, protected), + (AccessKind::Read, false) => child_read(child, protected), + } + } +} + +impl PermissionPriv { + /// Determines whether a transition that occured is compatible with the presence + /// of a Protector. This is not included in the `transition` functions because + /// it would distract from the few places where the transition is modified + /// because of a protector, but not forbidden. + fn protector_allows_transition(self, new: Self) -> bool { + match (self, new) { + _ if self == new => true, + // It is always a protector violation to not be readable anymore + (_, Disabled) => false, + // In the case of a `Reserved` under a protector, both transitions + // `Reserved => Active` and `Reserved => Frozen` can legitimately occur. + // The first is standard (Child Write), the second is for Foreign Writes + // on protected Reserved where we must ensure that the pointer is not + // written to in the future. + (Reserved { .. }, Active) | (Reserved { .. }, Frozen) => true, + // This pointer should have stayed writeable for the whole function + (Active, Frozen) => false, + _ => unreachable!("Transition from {self:?} to {new:?} should never be possible"), + } + } +} + +/// Public interface to the state machine that controls read-write permissions. +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub struct Permission(PermissionPriv); + +impl fmt::Display for Permission { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!( + f, + "{}", + match self.0 { + PermissionPriv::Reserved { .. } => "Reserved", + PermissionPriv::Active => "Active", + PermissionPriv::Frozen => "Frozen", + PermissionPriv::Disabled => "Disabled", + } + ) + } +} + +impl Permission { + /// Default initial permission of the root of a new tree. + pub fn new_root() -> Self { + Self(Active) + } + + /// Default initial permission of a reborrowed mutable reference. + pub fn new_unique_2phase(ty_is_freeze: bool) -> Self { + Self(Reserved { ty_is_freeze }) + } + + /// Default initial permission of a reborrowed shared reference + pub fn new_frozen() -> Self { + Self(Frozen) + } + + /// Pretty-printing. Needs to be here and not in diagnostics.rs + /// because `Self` is private. + pub fn short_name(self) -> &'static str { + // Make sure there are all of the same length as each other + // and also as `diagnostics::DisplayFmtPermission.uninit` otherwise + // alignment will be incorrect. + match self.0 { + Reserved { ty_is_freeze: true } => "Res", + Reserved { ty_is_freeze: false } => "Re*", + Active => "Act", + Frozen => "Frz", + Disabled => "Dis", + } + } + + /// Check that there are no complaints from a possible protector. + /// + /// Note: this is not in charge of checking that there *is* a protector, + /// it should be used as + /// ``` + /// let no_protector_error = if is_protected(tag) { + /// old_perm.protector_allows_transition(new_perm) + /// }; + /// ``` + pub fn protector_allows_transition(self, new: Self) -> bool { + self.0.protector_allows_transition(new.0) + } + + /// Apply the transition to the inner PermissionPriv. + pub fn perform_access( + kind: AccessKind, + rel_pos: AccessRelatedness, + old_perm: Self, + protected: bool, + ) -> Option<Self> { + let old_state = old_perm.0; + transition::perform_access(kind, rel_pos, old_state, protected).map(Self) + } +} + +#[cfg(test)] +mod propagation_optimization_checks { + pub use super::*; + + mod util { + pub use super::*; + impl PermissionPriv { + /// Enumerate all states + pub fn all() -> impl Iterator<Item = PermissionPriv> { + vec![ + Active, + Reserved { ty_is_freeze: true }, + Reserved { ty_is_freeze: false }, + Frozen, + Disabled, + ] + .into_iter() + } + } + + impl AccessKind { + /// Enumerate all AccessKind. + pub fn all() -> impl Iterator<Item = AccessKind> { + use AccessKind::*; + [Read, Write].into_iter() + } + } + + impl AccessRelatedness { + /// Enumerate all relative positions + pub fn all() -> impl Iterator<Item = AccessRelatedness> { + use AccessRelatedness::*; + [This, StrictChildAccess, AncestorAccess, DistantAccess].into_iter() + } + } + } + + #[test] + // For any kind of access, if we do it twice the second should be a no-op. + // Even if the protector has disappeared. + fn all_transitions_idempotent() { + use transition::*; + for old in PermissionPriv::all() { + for (old_protected, new_protected) in [(true, true), (true, false), (false, false)] { + for access in AccessKind::all() { + for rel_pos in AccessRelatedness::all() { + if let Some(new) = perform_access(access, rel_pos, old, old_protected) { + assert_eq!( + new, + perform_access(access, rel_pos, new, new_protected).unwrap() + ); + } + } + } + } + } + } + + #[test] + fn foreign_read_is_noop_after_write() { + use transition::*; + let old_access = AccessKind::Write; + let new_access = AccessKind::Read; + for old in PermissionPriv::all() { + for (old_protected, new_protected) in [(true, true), (true, false), (false, false)] { + for rel_pos in AccessRelatedness::all().filter(|rel| rel.is_foreign()) { + if let Some(new) = perform_access(old_access, rel_pos, old, old_protected) { + assert_eq!( + new, + perform_access(new_access, rel_pos, new, new_protected).unwrap() + ); + } + } + } + } + } + + #[test] + // Check that all transitions are consistent with the order on PermissionPriv, + // i.e. Reserved -> Active -> Frozen -> Disabled + fn access_transitions_progress_increasing() { + use transition::*; + for old in PermissionPriv::all() { + for protected in [true, false] { + for access in AccessKind::all() { + for rel_pos in AccessRelatedness::all() { + if let Some(new) = perform_access(access, rel_pos, old, protected) { + assert!(old <= new); + } + } + } + } + } + } +} diff --git a/src/tools/miri/src/borrow_tracker/tree_borrows/tree.rs b/src/tools/miri/src/borrow_tracker/tree_borrows/tree.rs new file mode 100644 index 00000000000..86416a0eb1b --- /dev/null +++ b/src/tools/miri/src/borrow_tracker/tree_borrows/tree.rs @@ -0,0 +1,554 @@ +//! In this file we handle the "Tree" part of Tree Borrows, i.e. all tree +//! traversal functions, optimizations to trim branches, and keeping track of +//! the relative position of the access to each node being updated. This of course +//! also includes the definition of the tree structure. +//! +//! Functions here manipulate permissions but are oblivious to them: as +//! the internals of `Permission` are private, the update process is a black +//! box. All we need to know here are +//! - the fact that updates depend only on the old state, the status of protectors, +//! and the relative position of the access; +//! - idempotency properties asserted in `perms.rs` (for optimizations) + +use smallvec::SmallVec; + +use rustc_const_eval::interpret::InterpResult; +use rustc_data_structures::fx::FxHashSet; +use rustc_target::abi::Size; + +use crate::borrow_tracker::tree_borrows::{ + diagnostics::{NodeDebugInfo, TbError, TransitionError}, + unimap::{UniEntry, UniIndex, UniKeyMap, UniValMap}, + Permission, +}; +use crate::borrow_tracker::{AccessKind, GlobalState, ProtectorKind}; +use crate::*; + +/// Data for a single *location*. +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub(super) struct LocationState { + /// This pointer's current permission + permission: Permission, + /// A location is initialized when it is child accessed for the first time, + /// and it then stays initialized forever. + /// Before initialization we still apply some preemptive transitions on + /// `permission` to know what to do in case it ever gets initialized, + /// but these can never cause any immediate UB. There can however be UB + /// the moment we attempt to initalize (i.e. child-access) because some + /// foreign access done between the creation and the initialization is + /// incompatible with child accesses. + initialized: bool, + /// Strongest foreign access whose effects have already been applied to + /// this node and all its children since the last child access. + /// This is `None` if the most recent access is a child access, + /// `Some(Write)` if at least one foreign write access has been applied + /// since the previous child access, and `Some(Read)` if at least one + /// foreign read and no foreign write have occurred since the last child access. + latest_foreign_access: Option<AccessKind>, +} + +impl LocationState { + /// Default initial state has never been accessed and has been subjected to no + /// foreign access. + fn new(permission: Permission) -> Self { + Self { permission, initialized: false, latest_foreign_access: None } + } + + /// Record that this location was accessed through a child pointer by + /// marking it as initialized + fn with_access(mut self) -> Self { + self.initialized = true; + self + } + + pub fn is_initialized(&self) -> bool { + self.initialized + } + + pub fn permission(&self) -> Permission { + self.permission + } +} + +/// Tree structure with both parents and children since we want to be +/// able to traverse the tree efficiently in both directions. +#[derive(Clone, Debug)] +pub struct Tree { + /// Mapping from tags to keys. The key obtained can then be used in + /// any of the `UniValMap` relative to this allocation, i.e. both the + /// `nodes` and `rperms` of the same `Tree`. + /// The parent-child relationship in `Node` is encoded in terms of these same + /// keys, so traversing the entire tree needs exactly one access to + /// `tag_mapping`. + pub(super) tag_mapping: UniKeyMap<BorTag>, + /// All nodes of this tree. + pub(super) nodes: UniValMap<Node>, + /// Maps a tag and a location to a perm, with possible lazy + /// initialization. + /// + /// NOTE: not all tags registered in `nodes` are necessarily in all + /// ranges of `rperms`, because `rperms` is in part lazily initialized. + /// Just because `nodes.get(key)` is `Some(_)` does not mean you can safely + /// `unwrap` any `perm.get(key)`. + /// + /// We do uphold the fact that `keys(perms)` is a subset of `keys(nodes)` + pub(super) rperms: RangeMap<UniValMap<LocationState>>, + /// The index of the root node. + pub(super) root: UniIndex, +} + +/// A node in the borrow tree. Each node is uniquely identified by a tag via +/// the `nodes` map of `Tree`. +#[derive(Clone, Debug)] +pub(super) struct Node { + /// The tag of this node. + pub tag: BorTag, + /// All tags except the root have a parent tag. + pub parent: Option<UniIndex>, + /// If the pointer was reborrowed, it has children. + // FIXME: bench to compare this to FxHashSet and to other SmallVec sizes + pub children: SmallVec<[UniIndex; 4]>, + /// Either `Reserved` or `Frozen`, the permission this tag will be lazily initialized + /// to on the first access. + default_initial_perm: Permission, + /// Some extra information useful only for debugging purposes + pub debug_info: NodeDebugInfo, +} + +/// Data given to the transition function +struct NodeAppArgs<'node> { + /// Node on which the transition is currently being applied + node: &'node Node, + /// Mutable access to its permissions + perm: UniEntry<'node, LocationState>, + /// Relative position of the access + rel_pos: AccessRelatedness, +} +/// Data given to the error handler +struct ErrHandlerArgs<'node, InErr> { + /// Kind of error that occurred + error_kind: InErr, + /// Tag that triggered the error (not the tag that was accessed, + /// rather the parent tag that had insufficient permissions or the + /// non-parent tag that had a protector). + faulty_tag: &'node NodeDebugInfo, +} +/// Internal contents of `Tree` with the minimum of mutable access for +/// the purposes of the tree traversal functions: the permissions (`perms`) can be +/// updated but not the tree structure (`tag_mapping` and `nodes`) +struct TreeVisitor<'tree> { + tag_mapping: &'tree UniKeyMap<BorTag>, + nodes: &'tree UniValMap<Node>, + perms: &'tree mut UniValMap<LocationState>, +} + +/// Whether to continue exploring the children recursively or not. +enum ContinueTraversal { + Recurse, + SkipChildren, +} + +impl<'tree> TreeVisitor<'tree> { + // Applies `f_propagate` to every vertex of the tree top-down in the following order: first + // all ancestors of `start`, then `start` itself, then children of `start`, then the rest. + // This ensures that errors are triggered in the following order + // - first invalid accesses with insufficient permissions, closest to the root first, + // - then protector violations, closest to `start` first. + // + // `f_propagate` should follow the following format: for a given `Node` it updates its + // `Permission` depending on the position relative to `start` (given by an + // `AccessRelatedness`). + // It outputs whether the tree traversal for this subree should continue or not. + fn traverse_parents_this_children_others<InnErr, OutErr>( + mut self, + start: BorTag, + f_propagate: impl Fn(NodeAppArgs<'_>) -> Result<ContinueTraversal, InnErr>, + err_builder: impl Fn(ErrHandlerArgs<'_, InnErr>) -> OutErr, + ) -> Result<(), OutErr> +where { + struct TreeVisitAux<NodeApp, ErrHandler> { + f_propagate: NodeApp, + err_builder: ErrHandler, + stack: Vec<(UniIndex, AccessRelatedness)>, + } + impl<NodeApp, InnErr, OutErr, ErrHandler> TreeVisitAux<NodeApp, ErrHandler> + where + NodeApp: Fn(NodeAppArgs<'_>) -> Result<ContinueTraversal, InnErr>, + ErrHandler: Fn(ErrHandlerArgs<'_, InnErr>) -> OutErr, + { + fn pop(&mut self) -> Option<(UniIndex, AccessRelatedness)> { + self.stack.pop() + } + + /// Apply the function to the current `tag`, and push its children + /// to the stack of future tags to visit. + fn exec_and_visit( + &mut self, + this: &mut TreeVisitor<'_>, + tag: UniIndex, + exclude: Option<UniIndex>, + rel_pos: AccessRelatedness, + ) -> Result<(), OutErr> { + // 1. apply the propagation function + let node = this.nodes.get(tag).unwrap(); + let recurse = + (self.f_propagate)(NodeAppArgs { node, perm: this.perms.entry(tag), rel_pos }) + .map_err(|error_kind| { + (self.err_builder)(ErrHandlerArgs { + error_kind, + faulty_tag: &node.debug_info, + }) + })?; + // 2. add the children to the stack for future traversal + if matches!(recurse, ContinueTraversal::Recurse) { + let child_rel = rel_pos.for_child(); + for &child in node.children.iter() { + // some child might be excluded from here and handled separately + if Some(child) != exclude { + self.stack.push((child, child_rel)); + } + } + } + Ok(()) + } + } + + let start_idx = self.tag_mapping.get(&start).unwrap(); + let mut stack = TreeVisitAux { f_propagate, err_builder, stack: Vec::new() }; + { + let mut path_ascend = Vec::new(); + // First climb to the root while recording the path + let mut curr = start_idx; + while let Some(ancestor) = self.nodes.get(curr).unwrap().parent { + path_ascend.push((ancestor, curr)); + curr = ancestor; + } + // Then descend: + // - execute f_propagate on each node + // - record children in visit + while let Some((ancestor, next_in_path)) = path_ascend.pop() { + // Explore ancestors in descending order. + // `next_in_path` is excluded from the recursion because it + // will be the `ancestor` of the next iteration. + // It also needs a different `AccessRelatedness` than the other + // children of `ancestor`. + stack.exec_and_visit( + &mut self, + ancestor, + Some(next_in_path), + AccessRelatedness::StrictChildAccess, + )?; + } + }; + // All (potentially zero) ancestors have been explored, call f_propagate on start + stack.exec_and_visit(&mut self, start_idx, None, AccessRelatedness::This)?; + // up to this point we have never popped from `stack`, hence if the + // path to the root is `root = p(n) <- p(n-1)... <- p(1) <- p(0) = start` + // then now `stack` contains + // `[<children(p(n)) except p(n-1)> ... <children(p(1)) except p(0)> <children(p(0))>]`, + // all of which are for now unexplored. + // This is the starting point of a standard DFS which will thus + // explore all non-ancestors of `start` in the following order: + // - all descendants of `start`; + // - then the unexplored descendants of `parent(start)`; + // ... + // - until finally the unexplored descendants of `root`. + while let Some((tag, rel_pos)) = stack.pop() { + stack.exec_and_visit(&mut self, tag, None, rel_pos)?; + } + Ok(()) + } +} + +impl Tree { + /// Create a new tree, with only a root pointer. + pub fn new(root_tag: BorTag, size: Size) -> Self { + let root_perm = Permission::new_root(); + let mut tag_mapping = UniKeyMap::default(); + let root_idx = tag_mapping.insert(root_tag); + let nodes = { + let mut nodes = UniValMap::<Node>::default(); + nodes.insert( + root_idx, + Node { + tag: root_tag, + parent: None, + children: SmallVec::default(), + default_initial_perm: root_perm, + debug_info: NodeDebugInfo::new(root_tag), + }, + ); + nodes + }; + let rperms = { + let mut perms = UniValMap::default(); + perms.insert(root_idx, LocationState::new(root_perm).with_access()); + RangeMap::new(size, perms) + }; + Self { root: root_idx, nodes, rperms, tag_mapping } + } +} + +impl<'tcx> Tree { + /// Insert a new tag in the tree + pub fn new_child( + &mut self, + parent_tag: BorTag, + new_tag: BorTag, + default_initial_perm: Permission, + range: AllocRange, + ) -> InterpResult<'tcx> { + assert!(!self.tag_mapping.contains_key(&new_tag)); + let idx = self.tag_mapping.insert(new_tag); + let parent_idx = self.tag_mapping.get(&parent_tag).unwrap(); + // Create the node + self.nodes.insert( + idx, + Node { + tag: new_tag, + parent: Some(parent_idx), + children: SmallVec::default(), + default_initial_perm, + debug_info: NodeDebugInfo::new(new_tag), + }, + ); + // Register new_tag as a child of parent_tag + self.nodes.get_mut(parent_idx).unwrap().children.push(idx); + // Initialize perms + let perm = LocationState::new(default_initial_perm).with_access(); + for (_range, perms) in self.rperms.iter_mut(range.start, range.size) { + perms.insert(idx, perm); + } + Ok(()) + } + + /// Deallocation requires + /// - a pointer that permits write accesses + /// - the absence of Strong Protectors anywhere in the allocation + pub fn dealloc( + &mut self, + tag: BorTag, + range: AllocRange, + global: &GlobalState, + ) -> InterpResult<'tcx> { + self.perform_access(AccessKind::Write, tag, range, global)?; + let access_info = &self.nodes.get(self.tag_mapping.get(&tag).unwrap()).unwrap().debug_info; + for (_range, perms) in self.rperms.iter_mut(range.start, range.size) { + TreeVisitor { nodes: &self.nodes, tag_mapping: &self.tag_mapping, perms } + .traverse_parents_this_children_others( + tag, + |args: NodeAppArgs<'_>| -> Result<ContinueTraversal, TransitionError> { + let NodeAppArgs { node, .. } = args; + if global.borrow().protected_tags.get(&node.tag) + == Some(&ProtectorKind::StrongProtector) + { + Err(TransitionError::ProtectedDealloc) + } else { + Ok(ContinueTraversal::Recurse) + } + }, + |args: ErrHandlerArgs<'_, TransitionError>| -> InterpErrorInfo<'tcx> { + let ErrHandlerArgs { error_kind, faulty_tag } = args; + TbError { + faulty_tag, + access_kind: AccessKind::Write, + error_kind, + tag_of_access: access_info, + } + .build() + }, + )?; + } + Ok(()) + } + + /// Maps the following propagation procedure to each range: + /// - initialize if needed; + /// - compute new state after transition; + /// - check that there is no protector that would forbid this; + /// - record this specific location as accessed. + pub fn perform_access( + &mut self, + access_kind: AccessKind, + tag: BorTag, + range: AllocRange, + global: &GlobalState, + ) -> InterpResult<'tcx> { + let access_info = &self.nodes.get(self.tag_mapping.get(&tag).unwrap()).unwrap().debug_info; + for (_range, perms) in self.rperms.iter_mut(range.start, range.size) { + TreeVisitor { nodes: &self.nodes, tag_mapping: &self.tag_mapping, perms } + .traverse_parents_this_children_others( + tag, + |args: NodeAppArgs<'_>| -> Result<ContinueTraversal, TransitionError> { + let NodeAppArgs { node, mut perm, rel_pos } = args; + + let old_state = + perm.or_insert_with(|| LocationState::new(node.default_initial_perm)); + + // Optimize the tree traversal. + // The optimization here consists of observing thanks to the tests + // `foreign_read_is_noop_after_write` and `all_transitions_idempotent` + // that if we apply twice in a row the effects of a foreign access + // we can skip some branches. + // "two foreign accesses in a row" occurs when `perm.latest_foreign_access` is `Some(_)` + // AND the `rel_pos` of the current access corresponds to a foreign access. + if rel_pos.is_foreign() { + let new_access_noop = + match (old_state.latest_foreign_access, access_kind) { + // Previously applied transition makes the new one a guaranteed + // noop in the two following cases: + // (1) justified by `foreign_read_is_noop_after_write` + (Some(AccessKind::Write), AccessKind::Read) => true, + // (2) justified by `all_transitions_idempotent` + (Some(old), new) if old == new => true, + // In all other cases there has been a recent enough + // child access that the effects of the new foreign access + // need to be applied to this subtree. + _ => false, + }; + if new_access_noop { + // Abort traversal if the new transition is indeed guaranteed + // to be noop. + return Ok(ContinueTraversal::SkipChildren); + } else { + // Otherwise propagate this time, and also record the + // access that just occurred so that we can skip the propagation + // next time. + old_state.latest_foreign_access = Some(access_kind); + } + } else { + // A child access occurred, this breaks the streak of "two foreign + // accesses in a row" and we reset this field. + old_state.latest_foreign_access = None; + } + + let old_perm = old_state.permission; + let protected = global.borrow().protected_tags.contains_key(&node.tag); + let new_perm = + Permission::perform_access(access_kind, rel_pos, old_perm, protected) + .ok_or(TransitionError::ChildAccessForbidden(old_perm))?; + if protected + // Can't trigger Protector on uninitialized locations + && old_state.initialized + && !old_perm.protector_allows_transition(new_perm) + { + return Err(TransitionError::ProtectedTransition(old_perm, new_perm)); + } + old_state.permission = new_perm; + old_state.initialized |= !rel_pos.is_foreign(); + Ok(ContinueTraversal::Recurse) + }, + |args: ErrHandlerArgs<'_, TransitionError>| -> InterpErrorInfo<'tcx> { + let ErrHandlerArgs { error_kind, faulty_tag } = args; + TbError { faulty_tag, access_kind, error_kind, tag_of_access: access_info } + .build() + }, + )?; + } + Ok(()) + } +} + +/// Integration with the BorTag garbage collector +impl Tree { + pub fn remove_unreachable_tags(&mut self, live_tags: &FxHashSet<BorTag>) { + assert!(self.keep_only_needed(self.root, live_tags)); // root can't be removed + } + + /// Traverses the entire tree looking for useless tags. + /// Returns true iff the tag it was called on is still live or has live children, + /// and removes from the tree all tags that have no live children. + /// + /// NOTE: This leaves in the middle of the tree tags that are unreachable but have + /// reachable children. There is a potential for compacting the tree by reassigning + /// children of dead tags to the nearest live parent, but it must be done with care + /// not to remove UB. + /// + /// Example: Consider the tree `root - parent - child`, with `parent: Frozen` and + /// `child: Reserved`. This tree can exist. If we blindly delete `parent` and reassign + /// `child` to be a direct child of `root` then Writes to `child` are now permitted + /// whereas they were not when `parent` was still there. + fn keep_only_needed(&mut self, idx: UniIndex, live: &FxHashSet<BorTag>) -> bool { + let node = self.nodes.get(idx).unwrap(); + // FIXME: this function does a lot of cloning, a 2-pass approach is possibly + // more efficient. It could consist of + // 1. traverse the Tree, collect all useless tags in a Vec + // 2. traverse the Vec, remove all tags previously selected + // Bench it. + let children: SmallVec<_> = node + .children + .clone() + .into_iter() + .filter(|child| self.keep_only_needed(*child, live)) + .collect(); + let no_children = children.is_empty(); + let node = self.nodes.get_mut(idx).unwrap(); + node.children = children; + if !live.contains(&node.tag) && no_children { + // All of the children and this node are unreachable, delete this tag + // from the tree (the children have already been deleted by recursive + // calls). + // Due to the API of UniMap we must absolutely call + // `UniValMap::remove` for the key of this tag on *all* maps that used it + // (which are `self.nodes` and every range of `self.rperms`) + // before we can safely apply `UniValMap::forget` to truly remove + // the tag from the mapping. + let tag = node.tag; + self.nodes.remove(idx); + for perms in self.rperms.iter_mut_all() { + perms.remove(idx); + } + self.tag_mapping.remove(&tag); + // The tag has been deleted, inform the caller + false + } else { + // The tag is still live or has live children, it must be kept + true + } + } +} + +impl VisitTags for Tree { + fn visit_tags(&self, visit: &mut dyn FnMut(BorTag)) { + // To ensure that the root never gets removed, we visit it + // (the `root` node of `Tree` is not an `Option<_>`) + visit(self.nodes.get(self.root).unwrap().tag) + } +} + +/// Relative position of the access +#[derive(Clone, Copy, Debug, PartialEq, Eq)] +pub enum AccessRelatedness { + /// The accessed pointer is the current one + This, + /// The accessed pointer is a (transitive) child of the current one. + // Current pointer is excluded (unlike in some other places of this module + // where "child" is inclusive). + StrictChildAccess, + /// The accessed pointer is a (transitive) parent of the current one. + // Current pointer is excluded. + AncestorAccess, + /// The accessed pointer is neither of the above. + // It's a cousin/uncle/etc., something in a side branch. + // FIXME: find a better name ? + DistantAccess, +} + +impl AccessRelatedness { + /// Check that access is either Ancestor or Distant, i.e. not + /// a transitive child (initial pointer included). + pub fn is_foreign(self) -> bool { + matches!(self, AccessRelatedness::AncestorAccess | AccessRelatedness::DistantAccess) + } + + /// Given the AccessRelatedness for the parent node, compute the AccessRelatedness + /// for the child node. This function assumes that we propagate away from the initial + /// access. + pub fn for_child(self) -> Self { + use AccessRelatedness::*; + match self { + AncestorAccess | This => AncestorAccess, + StrictChildAccess | DistantAccess => DistantAccess, + } + } +} diff --git a/src/tools/miri/src/borrow_tracker/tree_borrows/unimap.rs b/src/tools/miri/src/borrow_tracker/tree_borrows/unimap.rs new file mode 100644 index 00000000000..c1d452ca89e --- /dev/null +++ b/src/tools/miri/src/borrow_tracker/tree_borrows/unimap.rs @@ -0,0 +1,304 @@ +//! This module implements the `UniMap`, which is a way to get efficient mappings +//! optimized for the setting of `tree_borrows/tree.rs`. +//! +//! A `UniKeyMap<K>` is a (slow) mapping from `K` to `UniIndex`, +//! and `UniValMap<V>` is a (fast) mapping from `UniIndex` to `V`. +//! Thus a pair `(UniKeyMap<K>, UniValMap<V>)` acts as a virtual `HashMap<K, V>`. +//! +//! Because of the asymmetry in access time, the use-case for `UniMap` is the following: +//! a tuple `(UniKeyMap<K>, Vec<UniValMap<V>>)` is much more efficient than +//! the equivalent `Vec<HashMap<K, V>>` it represents if all maps have similar +//! sets of keys. + +#![allow(dead_code)] + +use std::hash::Hash; + +use rustc_data_structures::fx::FxHashMap; + +/// Intermediate key between a UniKeyMap and a UniValMap. +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub struct UniIndex { + idx: u32, +} + +/// From K to UniIndex +#[derive(Debug, Clone, Default)] +pub struct UniKeyMap<K> { + /// Underlying map that does all the hard work. + /// Key invariant: the contents of `deassigned` are disjoint from the + /// keys of `mapping`, and together they form the set of contiguous integers + /// `0 .. (mapping.len() + deassigned.len())`. + mapping: FxHashMap<K, u32>, + /// Indexes that can be reused: memory gain when the map gets sparse + /// due to many deletions. + deassigned: Vec<u32>, +} + +/// From UniIndex to V +#[derive(Debug, Clone, PartialEq, Eq)] +pub struct UniValMap<V> { + /// The mapping data. Thanks to Vec we get both fast accesses, and + /// a memory-optimal representation if there are few deletions. + data: Vec<Option<V>>, +} + +impl<V> Default for UniValMap<V> { + fn default() -> Self { + Self { data: Vec::default() } + } +} + +impl<K> UniKeyMap<K> +where + K: Hash + Eq, +{ + /// How many keys/index pairs are currently active. + pub fn len(&self) -> usize { + self.mapping.len() + } + + /// Whether this key has an associated index or not. + pub fn contains_key(&self, key: &K) -> bool { + self.mapping.contains_key(key) + } + + /// Assign this key to a new index. Panics if the key is already assigned, + /// use `get_or_insert` for a version that instead returns the existing + /// assignment. + #[track_caller] + pub fn insert(&mut self, key: K) -> UniIndex { + // We want an unused index. First we attempt to find one from `deassigned`, + // and if `deassigned` is empty we generate a fresh index. + let idx = self.deassigned.pop().unwrap_or_else(|| { + // `deassigned` is empty, so all keys in use are already in `mapping`. + // The next available key is `mapping.len()`. + self.mapping.len().try_into().expect("UniMap ran out of useable keys") + }); + if self.mapping.insert(key, idx).is_some() { + panic!( + "This key is already assigned to a different index; either use `get_or_insert` instead if you care about this data, or first call `remove` to undo the preexisting assignment." + ); + }; + UniIndex { idx } + } + + /// If it exists, the index this key maps to. + pub fn get(&self, key: &K) -> Option<UniIndex> { + self.mapping.get(key).map(|&idx| UniIndex { idx }) + } + + /// Either get a previously existing entry, or create a new one if it + /// is not yet present. + pub fn get_or_insert(&mut self, key: K) -> UniIndex { + self.get(&key).unwrap_or_else(|| self.insert(key)) + } + + /// Return whatever index this key was using to the deassigned pool. + /// + /// Note: calling this function can be dangerous. If the index still exists + /// somewhere in a `UniValMap` and is reassigned by the `UniKeyMap` then + /// it will inherit the old value of a completely unrelated key. + /// If you `UniKeyMap::remove` a key you should make sure to also `UniValMap::remove` + /// the associated `UniIndex` from ALL `UniValMap`s. + /// + /// Example of such behavior: + /// ``` + /// let mut keymap = UniKeyMap::<char>::default(); + /// let mut valmap = UniValMap::<char>::default(); + /// // Insert 'a' -> _ -> 'A' + /// let idx_a = keymap.insert('a'); + /// valmap.insert(idx_a, 'A'); + /// // Remove 'a' -> _, but forget to remove _ -> 'A' + /// keymap.remove(&'a'); + /// // valmap.remove(idx_a); // If we uncomment this line the issue is fixed + /// // Insert 'b' -> _ + /// let idx_b = keymap.insert('b'); + /// let val_b = valmap.get(idx_b); + /// assert_eq!(val_b, Some('A')); // Oh no + /// // assert_eq!(val_b, None); // This is what we would have expected + /// ``` + pub fn remove(&mut self, key: &K) { + if let Some(idx) = self.mapping.remove(key) { + self.deassigned.push(idx); + } + } +} + +impl<V> UniValMap<V> { + /// Whether this index has an associated value. + pub fn contains_idx(&self, idx: UniIndex) -> bool { + self.data.get(idx.idx as usize).and_then(Option::as_ref).is_some() + } + + /// Reserve enough space to insert the value at the right index. + fn extend_to_length(&mut self, len: usize) { + if len > self.data.len() { + let nb = len - self.data.len(); + self.data.reserve(nb); + for _ in 0..nb { + self.data.push(None); + } + } + } + + /// Assign a value to the index. Permanently overwrites any previous value. + pub fn insert(&mut self, idx: UniIndex, val: V) { + self.extend_to_length(idx.idx as usize + 1); + self.data[idx.idx as usize] = Some(val) + } + + /// Get the value at this index, if it exists. + pub fn get(&self, idx: UniIndex) -> Option<&V> { + self.data.get(idx.idx as usize).and_then(Option::as_ref) + } + + /// Get the value at this index mutably, if it exists. + pub fn get_mut(&mut self, idx: UniIndex) -> Option<&mut V> { + self.data.get_mut(idx.idx as usize).and_then(Option::as_mut) + } + + /// Delete any value associated with this index. Ok even if the index + /// has no associated value. + pub fn remove(&mut self, idx: UniIndex) { + if idx.idx as usize >= self.data.len() { + return; + } + self.data[idx.idx as usize] = None; + } +} + +/// An access to a single value of the map. +pub struct UniEntry<'a, V> { + inner: &'a mut Option<V>, +} + +impl<'a, V> UniValMap<V> { + /// Get a wrapper around a mutable access to the value corresponding to `idx`. + pub fn entry(&'a mut self, idx: UniIndex) -> UniEntry<'a, V> { + self.extend_to_length(idx.idx as usize + 1); + UniEntry { inner: &mut self.data[idx.idx as usize] } + } +} + +impl<'a, V> UniEntry<'a, V> { + /// Insert in the map and get the value. + pub fn or_insert_with<F>(&mut self, default: F) -> &mut V + where + F: FnOnce() -> V, + { + if self.inner.is_none() { + *self.inner = Some(default()); + } + self.inner.as_mut().unwrap() + } +} + +mod tests { + use super::*; + + #[test] + fn extend_to_length() { + let mut km = UniValMap::<char>::default(); + km.extend_to_length(10); + assert!(km.data.len() == 10); + km.extend_to_length(0); + assert!(km.data.len() == 10); + km.extend_to_length(10); + assert!(km.data.len() == 10); + km.extend_to_length(11); + assert!(km.data.len() == 11); + } + + #[derive(Default)] + struct MapWitness<K, V> { + key: UniKeyMap<K>, + val: UniValMap<V>, + map: FxHashMap<K, V>, + } + + impl<K, V> MapWitness<K, V> + where + K: Copy + Hash + Eq, + V: Copy + Eq + std::fmt::Debug, + { + fn insert(&mut self, k: K, v: V) { + // UniMap + let i = self.key.get_or_insert(k); + self.val.insert(i, v); + // HashMap + self.map.insert(k, v); + // Consistency: nothing to check + } + + fn get(&self, k: &K) { + // UniMap + let v1 = self.key.get(k).and_then(|i| self.val.get(i)); + // HashMap + let v2 = self.map.get(k); + // Consistency + assert_eq!(v1, v2); + } + + fn get_mut(&mut self, k: &K) { + // UniMap + let v1 = self.key.get(k).and_then(|i| self.val.get_mut(i)); + // HashMap + let v2 = self.map.get_mut(k); + // Consistency + assert_eq!(v1, v2); + } + fn remove(&mut self, k: &K) { + // UniMap + if let Some(i) = self.key.get(k) { + self.val.remove(i); + } + self.key.remove(k); + // HashMap + self.map.remove(k); + // Consistency: nothing to check + } + } + + #[test] + fn consistency_small() { + let mut m = MapWitness::<u64, char>::default(); + m.insert(1, 'a'); + m.insert(2, 'b'); + m.get(&1); + m.get_mut(&2); + m.remove(&2); + m.insert(1, 'c'); + m.get(&1); + m.insert(3, 'd'); + m.insert(4, 'e'); + m.insert(4, 'f'); + m.get(&2); + m.get(&3); + m.get(&4); + m.get(&5); + m.remove(&100); + m.get_mut(&100); + m.get(&100); + } + + #[test] + fn consistency_large() { + use std::collections::hash_map::DefaultHasher; + use std::hash::{Hash, Hasher}; + let mut hasher = DefaultHasher::new(); + let mut map = MapWitness::<u64, u64>::default(); + for i in 0..1000 { + i.hash(&mut hasher); + let rng = hasher.finish(); + let op = rng % 3 == 0; + let key = (rng / 2) % 50; + let val = (rng / 100) % 1000; + if op { + map.insert(key, val); + } else { + map.get(&key); + } + } + } +} diff --git a/src/tools/miri/src/diagnostics.rs b/src/tools/miri/src/diagnostics.rs index 035c0e64233..3c13118122c 100644 --- a/src/tools/miri/src/diagnostics.rs +++ b/src/tools/miri/src/diagnostics.rs @@ -22,6 +22,10 @@ pub enum TerminationInfo { help: Option<String>, history: Option<TagHistory>, }, + TreeBorrowsUb { + msg: String, + // FIXME: incomplete + }, Int2PtrWithStrictProvenance, Deadlock, MultipleSymbolDefinitions { @@ -61,6 +65,7 @@ impl fmt::Display for TerminationInfo { "integer-to-pointer casts and `ptr::from_exposed_addr` are not supported with `-Zmiri-strict-provenance`" ), StackedBorrowsUb { msg, .. } => write!(f, "{msg}"), + TreeBorrowsUb { msg } => write!(f, "{msg}"), Deadlock => write!(f, "the evaluated program deadlocked"), MultipleSymbolDefinitions { link_name, .. } => write!(f, "multiple definitions of symbol `{link_name}`"), @@ -184,7 +189,8 @@ pub fn report_error<'tcx, 'mir>( Abort(_) => Some("abnormal termination"), UnsupportedInIsolation(_) | Int2PtrWithStrictProvenance => Some("unsupported operation"), - StackedBorrowsUb { .. } | DataRace { .. } => Some("Undefined Behavior"), + StackedBorrowsUb { .. } | TreeBorrowsUb { .. } | DataRace { .. } => + Some("Undefined Behavior"), Deadlock => Some("deadlock"), MultipleSymbolDefinitions { .. } | SymbolShimClashing { .. } => None, }; @@ -212,6 +218,12 @@ pub fn report_error<'tcx, 'mir>( } } helps + }, + TreeBorrowsUb { .. } => { + let helps = vec![ + (None, format!("this indicates a potential bug in the program: it performed an invalid operation, but the Tree Borrows rules it violated are still experimental")), + ]; + helps } MultipleSymbolDefinitions { first, first_crate, second, second_crate, .. } => vec![ diff --git a/src/tools/miri/src/eval.rs b/src/tools/miri/src/eval.rs index 8443e907938..a32b18595b5 100644 --- a/src/tools/miri/src/eval.rs +++ b/src/tools/miri/src/eval.rs @@ -87,7 +87,7 @@ pub struct MiriConfig { pub env: Vec<(OsString, OsString)>, /// Determine if validity checking is enabled. pub validate: bool, - /// Determines if Stacked Borrows is enabled. + /// Determines if Stacked Borrows or Tree Borrows is enabled. pub borrow_tracker: Option<BorrowTrackerMethod>, /// Controls alignment checking. pub check_alignment: AlignmentCheck, @@ -134,7 +134,7 @@ pub struct MiriConfig { pub preemption_rate: f64, /// Report the current instruction being executed every N basic blocks. pub report_progress: Option<u32>, - /// Whether Stacked Borrows retagging should recurse into fields of datatypes. + /// Whether Stacked Borrows and Tree Borrows retagging should recurse into fields of datatypes. pub retag_fields: RetagFields, /// The location of a shared object file to load when calling external functions /// FIXME! consider allowing users to specify paths to multiple SO files, or to a directory diff --git a/src/tools/miri/src/helpers.rs b/src/tools/miri/src/helpers.rs index ed3dd741a8b..21a413002d0 100644 --- a/src/tools/miri/src/helpers.rs +++ b/src/tools/miri/src/helpers.rs @@ -1,5 +1,6 @@ pub mod convert; +use std::any::Any; use std::cmp; use std::iter; use std::num::NonZeroUsize; @@ -23,7 +24,23 @@ use rand::RngCore; use crate::*; -impl<'mir, 'tcx: 'mir> EvalContextExt<'mir, 'tcx> for crate::MiriInterpCx<'mir, 'tcx> {} +/// A trait to work around not having trait object upcasting: +/// Add `AsAny` as supertrait and your trait objects can be turned into `&dyn Any` on which you can +/// then call `downcast`. +pub trait AsAny: Any { + fn as_any(&self) -> &dyn Any; + fn as_any_mut(&mut self) -> &mut dyn Any; +} +impl<T: Any> AsAny for T { + #[inline(always)] + fn as_any(&self) -> &dyn Any { + self + } + #[inline(always)] + fn as_any_mut(&mut self) -> &mut dyn Any { + self + } +} // This mapping should match `decode_error_kind` in // <https://github.com/rust-lang/rust/blob/master/library/std/src/sys/unix/mod.rs>. @@ -119,6 +136,7 @@ fn try_resolve_did(tcx: TyCtxt<'_>, path: &[&str], namespace: Option<Namespace>) } } +impl<'mir, 'tcx: 'mir> EvalContextExt<'mir, 'tcx> for crate::MiriInterpCx<'mir, 'tcx> {} pub trait EvalContextExt<'mir, 'tcx: 'mir>: crate::MiriInterpCxExt<'mir, 'tcx> { /// Checks if the given crate/module exists. fn have_module(&self, path: &[&str]) -> bool { diff --git a/src/tools/miri/src/lib.rs b/src/tools/miri/src/lib.rs index f64f216520f..01d0f01d319 100644 --- a/src/tools/miri/src/lib.rs +++ b/src/tools/miri/src/lib.rs @@ -9,6 +9,7 @@ #![feature(nonzero_ops)] #![feature(local_key_cell_methods)] #![feature(is_terminal)] +#![feature(round_ties_even)] // Configure clippy and other lints #![allow( clippy::collapsible_else_if, @@ -94,6 +95,7 @@ pub use crate::shims::EvalContextExt as _; pub use crate::borrow_tracker::stacked_borrows::{ EvalContextExt as _, Item, Permission, Stack, Stacks, }; +pub use crate::borrow_tracker::tree_borrows::{EvalContextExt as _, Tree}; pub use crate::borrow_tracker::{ BorTag, BorrowTrackerMethod, CallId, EvalContextExt as _, RetagFields, }; diff --git a/src/tools/miri/src/machine.rs b/src/tools/miri/src/machine.rs index 969c81f7e32..eaa441d22ec 100644 --- a/src/tools/miri/src/machine.rs +++ b/src/tools/miri/src/machine.rs @@ -38,7 +38,7 @@ pub const SIGRTMAX: i32 = 42; /// Extra data stored with each stack frame pub struct FrameExtra<'tcx> { - /// Extra data for Stacked Borrows. + /// Extra data for the Borrow Tracker. pub borrow_tracker: Option<borrow_tracker::FrameState>, /// If this is Some(), then this is a special "catch unwind" frame (the frame of `try_fn` @@ -146,7 +146,7 @@ impl fmt::Display for MiriMemoryKind { pub enum Provenance { Concrete { alloc_id: AllocId, - /// Stacked Borrows tag. + /// Borrow Tracker tag. tag: BorTag, }, Wildcard, @@ -195,7 +195,7 @@ impl fmt::Debug for Provenance { } else { write!(f, "[{alloc_id:?}]")?; } - // Print Stacked Borrows tag. + // Print Borrow Tracker tag. write!(f, "{tag:?}")?; } Provenance::Wildcard => { diff --git a/src/tools/miri/src/shims/foreign_items.rs b/src/tools/miri/src/shims/foreign_items.rs index 03275ed4ed1..73439133af2 100644 --- a/src/tools/miri/src/shims/foreign_items.rs +++ b/src/tools/miri/src/shims/foreign_items.rs @@ -232,6 +232,19 @@ pub trait EvalContextExt<'mir, 'tcx: 'mir>: crate::MiriInterpCxExt<'mir, 'tcx> { } } + /// Read bytes from a `(ptr, len)` argument + fn read_byte_slice<'i>(&'i self, bytes: &OpTy<'tcx, Provenance>) -> InterpResult<'tcx, &'i [u8]> + where + 'mir: 'i, + { + let this = self.eval_context_ref(); + let (ptr, len) = this.read_immediate(bytes)?.to_scalar_pair(); + let ptr = ptr.to_pointer(this)?; + let len = len.to_target_usize(this)?; + let bytes = this.read_bytes_ptr_strip_provenance(ptr, Size::from_bytes(len))?; + Ok(bytes) + } + /// Emulates calling a foreign item, failing if the item is not supported. /// This function will handle `goto_block` if needed. /// Returns Ok(None) if the foreign item was completely handled @@ -427,13 +440,27 @@ pub trait EvalContextExt<'mir, 'tcx: 'mir>: crate::MiriInterpCxExt<'mir, 'tcx> { })?; this.write_scalar(Scalar::from_u64(alloc_id.0.get()), dest)?; } - "miri_print_borrow_stacks" => { - let [id] = this.check_shim(abi, Abi::Rust, link_name, args)?; + "miri_print_borrow_state" => { + let [id, show_unnamed] = this.check_shim(abi, Abi::Rust, link_name, args)?; let id = this.read_scalar(id)?.to_u64()?; + let show_unnamed = this.read_scalar(show_unnamed)?.to_bool()?; if let Some(id) = std::num::NonZeroU64::new(id) { - this.print_stacks(AllocId(id))?; + this.print_borrow_state(AllocId(id), show_unnamed)?; } } + "miri_pointer_name" => { + // This associates a name to a tag. Very useful for debugging, and also makes + // tests more strict. + let [ptr, nth_parent, name] = this.check_shim(abi, Abi::Rust, link_name, args)?; + let ptr = this.read_pointer(ptr)?; + let nth_parent = this.read_scalar(nth_parent)?.to_u8()?; + let name = this.read_byte_slice(name)?; + // We must make `name` owned because we need to + // end the shared borrow from `read_byte_slice` before we can + // start the mutable borrow for `give_pointer_debug_name`. + let name = String::from_utf8_lossy(name).into_owned(); + this.give_pointer_debug_name(ptr, nth_parent, &name)?; + } "miri_static_root" => { let [ptr] = this.check_shim(abi, Abi::Rust, link_name, args)?; let ptr = this.read_pointer(ptr)?; @@ -487,12 +514,8 @@ pub trait EvalContextExt<'mir, 'tcx: 'mir>: crate::MiriInterpCxExt<'mir, 'tcx> { // Writes some bytes to the interpreter's stdout/stderr. See the // README for details. "miri_write_to_stdout" | "miri_write_to_stderr" => { - let [bytes] = this.check_shim(abi, Abi::Rust, link_name, args)?; - let (ptr, len) = this.read_immediate(bytes)?.to_scalar_pair(); - let ptr = ptr.to_pointer(this)?; - let len = len.to_target_usize(this)?; - let msg = this.read_bytes_ptr_strip_provenance(ptr, Size::from_bytes(len))?; - + let [msg] = this.check_shim(abi, Abi::Rust, link_name, args)?; + let msg = this.read_byte_slice(msg)?; // Note: we're ignoring errors writing to host stdout/stderr. let _ignore = match link_name.as_str() { "miri_write_to_stdout" => std::io::stdout().write_all(msg), diff --git a/src/tools/miri/src/shims/intrinsics/mod.rs b/src/tools/miri/src/shims/intrinsics/mod.rs index d21a1560699..9ecbb18ef5a 100644 --- a/src/tools/miri/src/shims/intrinsics/mod.rs +++ b/src/tools/miri/src/shims/intrinsics/mod.rs @@ -157,6 +157,7 @@ pub trait EvalContextExt<'mir, 'tcx: 'mir>: crate::MiriInterpCxExt<'mir, 'tcx> { | "ceilf32" | "truncf32" | "roundf32" + | "rintf32" => { let [f] = check_arg_count(args)?; // FIXME: Using host floats. @@ -174,6 +175,7 @@ pub trait EvalContextExt<'mir, 'tcx: 'mir>: crate::MiriInterpCxExt<'mir, 'tcx> { "ceilf32" => f.ceil(), "truncf32" => f.trunc(), "roundf32" => f.round(), + "rintf32" => f.round_ties_even(), _ => bug!(), }; this.write_scalar(Scalar::from_u32(f.to_bits()), dest)?; @@ -192,6 +194,7 @@ pub trait EvalContextExt<'mir, 'tcx: 'mir>: crate::MiriInterpCxExt<'mir, 'tcx> { | "ceilf64" | "truncf64" | "roundf64" + | "rintf64" => { let [f] = check_arg_count(args)?; // FIXME: Using host floats. @@ -209,6 +212,7 @@ pub trait EvalContextExt<'mir, 'tcx: 'mir>: crate::MiriInterpCxExt<'mir, 'tcx> { "ceilf64" => f.ceil(), "truncf64" => f.trunc(), "roundf64" => f.round(), + "rintf64" => f.round_ties_even(), _ => bug!(), }; this.write_scalar(Scalar::from_u64(f.to_bits()), dest)?; diff --git a/src/tools/miri/src/shims/unix/fs.rs b/src/tools/miri/src/shims/unix/fs.rs index d05c4d98fad..1eca389e984 100644 --- a/src/tools/miri/src/shims/unix/fs.rs +++ b/src/tools/miri/src/shims/unix/fs.rs @@ -17,7 +17,6 @@ use crate::shims::os_str::bytes_to_os_str; use crate::*; use shims::os_str::os_str_to_bytes; use shims::time::system_time_to_duration; -use shims::unix::linux::fd::epoll::Epoll; #[derive(Debug)] pub struct FileHandle { @@ -25,17 +24,9 @@ pub struct FileHandle { writable: bool, } -pub trait FileDescriptor: std::fmt::Debug { +pub trait FileDescriptor: std::fmt::Debug + helpers::AsAny { fn name(&self) -> &'static str; - fn as_file_handle<'tcx>(&self) -> InterpResult<'tcx, &FileHandle> { - throw_unsup_format!("{} cannot be used as FileHandle", self.name()); - } - - fn as_epoll_handle<'tcx>(&mut self) -> InterpResult<'tcx, &mut Epoll> { - throw_unsup_format!("not an epoll file descriptor"); - } - fn read<'tcx>( &mut self, _communicate_allowed: bool, @@ -69,7 +60,9 @@ pub trait FileDescriptor: std::fmt::Debug { fn dup(&mut self) -> io::Result<Box<dyn FileDescriptor>>; - fn is_tty(&self) -> bool; + fn is_tty(&self) -> bool { + false + } #[cfg(unix)] fn as_unix_host_fd(&self) -> Option<i32> { @@ -82,10 +75,6 @@ impl FileDescriptor for FileHandle { "FILE" } - fn as_file_handle<'tcx>(&self) -> InterpResult<'tcx, &FileHandle> { - Ok(self) - } - fn read<'tcx>( &mut self, communicate_allowed: bool, @@ -271,10 +260,6 @@ impl FileDescriptor for NullOutput { fn dup(&mut self) -> io::Result<Box<dyn FileDescriptor>> { Ok(Box::new(NullOutput)) } - - fn is_tty(&self) -> bool { - false - } } #[derive(Debug)] @@ -694,7 +679,12 @@ pub trait EvalContextExt<'mir, 'tcx: 'mir>: crate::MiriInterpCxExt<'mir, 'tcx> { } else if this.tcx.sess.target.os == "macos" && cmd == this.eval_libc_i32("F_FULLFSYNC") { if let Some(file_descriptor) = this.machine.file_handler.handles.get(&fd) { // FIXME: Support fullfsync for all FDs - let FileHandle { file, writable } = file_descriptor.as_file_handle()?; + let FileHandle { file, writable } = + file_descriptor.as_any().downcast_ref::<FileHandle>().ok_or_else(|| { + err_unsup_format!( + "`F_FULLFSYNC` is only supported on file-backed file descriptors" + ) + })?; let io_result = maybe_sync_file(file, *writable, File::sync_all); this.try_unwrap_io_result(io_result) } else { @@ -1530,7 +1520,12 @@ pub trait EvalContextExt<'mir, 'tcx: 'mir>: crate::MiriInterpCxExt<'mir, 'tcx> { Ok(Scalar::from_i32( if let Some(file_descriptor) = this.machine.file_handler.handles.get_mut(&fd) { // FIXME: Support ftruncate64 for all FDs - let FileHandle { file, writable } = file_descriptor.as_file_handle()?; + let FileHandle { file, writable } = + file_descriptor.as_any().downcast_ref::<FileHandle>().ok_or_else(|| { + err_unsup_format!( + "`ftruncate64` is only supported on file-backed file descriptors" + ) + })?; if *writable { if let Ok(length) = length.try_into() { let result = file.set_len(length); @@ -1571,7 +1566,10 @@ pub trait EvalContextExt<'mir, 'tcx: 'mir>: crate::MiriInterpCxExt<'mir, 'tcx> { if let Some(file_descriptor) = this.machine.file_handler.handles.get(&fd) { // FIXME: Support fsync for all FDs - let FileHandle { file, writable } = file_descriptor.as_file_handle()?; + let FileHandle { file, writable } = + file_descriptor.as_any().downcast_ref::<FileHandle>().ok_or_else(|| { + err_unsup_format!("`fsync` is only supported on file-backed file descriptors") + })?; let io_result = maybe_sync_file(file, *writable, File::sync_all); this.try_unwrap_io_result(io_result) } else { @@ -1593,7 +1591,12 @@ pub trait EvalContextExt<'mir, 'tcx: 'mir>: crate::MiriInterpCxExt<'mir, 'tcx> { if let Some(file_descriptor) = this.machine.file_handler.handles.get(&fd) { // FIXME: Support fdatasync for all FDs - let FileHandle { file, writable } = file_descriptor.as_file_handle()?; + let FileHandle { file, writable } = + file_descriptor.as_any().downcast_ref::<FileHandle>().ok_or_else(|| { + err_unsup_format!( + "`fdatasync` is only supported on file-backed file descriptors" + ) + })?; let io_result = maybe_sync_file(file, *writable, File::sync_data); this.try_unwrap_io_result(io_result) } else { @@ -1638,7 +1641,12 @@ pub trait EvalContextExt<'mir, 'tcx: 'mir>: crate::MiriInterpCxExt<'mir, 'tcx> { if let Some(file_descriptor) = this.machine.file_handler.handles.get(&fd) { // FIXME: Support sync_data_range for all FDs - let FileHandle { file, writable } = file_descriptor.as_file_handle()?; + let FileHandle { file, writable } = + file_descriptor.as_any().downcast_ref::<FileHandle>().ok_or_else(|| { + err_unsup_format!( + "`sync_data_range` is only supported on file-backed file descriptors" + ) + })?; let io_result = maybe_sync_file(file, *writable, File::sync_data); Ok(Scalar::from_i32(this.try_unwrap_io_result(io_result)?)) } else { @@ -1942,7 +1950,16 @@ impl FileMetadata { ) -> InterpResult<'tcx, Option<FileMetadata>> { let option = ecx.machine.file_handler.handles.get(&fd); let file = match option { - Some(file_descriptor) => &file_descriptor.as_file_handle()?.file, + Some(file_descriptor) => + &file_descriptor + .as_any() + .downcast_ref::<FileHandle>() + .ok_or_else(|| { + err_unsup_format!( + "obtaining metadata is only supported on file-backed file descriptors" + ) + })? + .file, None => return ecx.handle_not_found().map(|_: i32| None), }; let metadata = file.metadata(); diff --git a/src/tools/miri/src/shims/unix/linux/fd.rs b/src/tools/miri/src/shims/unix/linux/fd.rs index fd4927fa10c..3c4a678e598 100644 --- a/src/tools/miri/src/shims/unix/linux/fd.rs +++ b/src/tools/miri/src/shims/unix/linux/fd.rs @@ -80,7 +80,10 @@ pub trait EvalContextExt<'mir, 'tcx: 'mir>: crate::MiriInterpCxExt<'mir, 'tcx> { let event = EpollEvent { events, data }; if let Some(epfd) = this.machine.file_handler.handles.get_mut(&epfd) { - let epfd = epfd.as_epoll_handle()?; + let epfd = epfd + .as_any_mut() + .downcast_mut::<Epoll>() + .ok_or_else(|| err_unsup_format!("non-epoll FD passed to `epoll_ctl`"))?; epfd.file_descriptors.insert(fd, event); Ok(Scalar::from_i32(0)) @@ -89,7 +92,10 @@ pub trait EvalContextExt<'mir, 'tcx: 'mir>: crate::MiriInterpCxExt<'mir, 'tcx> { } } else if op == epoll_ctl_del { if let Some(epfd) = this.machine.file_handler.handles.get_mut(&epfd) { - let epfd = epfd.as_epoll_handle()?; + let epfd = epfd + .as_any_mut() + .downcast_mut::<Epoll>() + .ok_or_else(|| err_unsup_format!("non-epoll FD passed to `epoll_ctl`"))?; epfd.file_descriptors.remove(&fd); Ok(Scalar::from_i32(0)) @@ -148,7 +154,10 @@ pub trait EvalContextExt<'mir, 'tcx: 'mir>: crate::MiriInterpCxExt<'mir, 'tcx> { let numevents = 0; if let Some(epfd) = this.machine.file_handler.handles.get_mut(&epfd) { - let _epfd = epfd.as_epoll_handle()?; + let _epfd = epfd + .as_any_mut() + .downcast_mut::<Epoll>() + .ok_or_else(|| err_unsup_format!("non-epoll FD passed to `epoll_wait`"))?; // FIXME return number of events ready when scheme for marking events ready exists Ok(Scalar::from_i32(numevents)) diff --git a/src/tools/miri/src/shims/unix/linux/fd/epoll.rs b/src/tools/miri/src/shims/unix/linux/fd/epoll.rs index e33673fecf6..a429caaf8f4 100644 --- a/src/tools/miri/src/shims/unix/linux/fd/epoll.rs +++ b/src/tools/miri/src/shims/unix/linux/fd/epoll.rs @@ -32,18 +32,10 @@ impl FileDescriptor for Epoll { "epoll" } - fn as_epoll_handle<'tcx>(&mut self) -> InterpResult<'tcx, &mut Epoll> { - Ok(self) - } - fn dup(&mut self) -> io::Result<Box<dyn FileDescriptor>> { Ok(Box::new(self.clone())) } - fn is_tty(&self) -> bool { - false - } - fn close<'tcx>( self: Box<Self>, _communicate_allowed: bool, diff --git a/src/tools/miri/src/shims/unix/linux/fd/event.rs b/src/tools/miri/src/shims/unix/linux/fd/event.rs index b28a6e0c56e..1db020bb7b6 100644 --- a/src/tools/miri/src/shims/unix/linux/fd/event.rs +++ b/src/tools/miri/src/shims/unix/linux/fd/event.rs @@ -28,10 +28,6 @@ impl FileDescriptor for Event { Ok(Box::new(Event { val: self.val.clone() })) } - fn is_tty(&self) -> bool { - false - } - fn close<'tcx>( self: Box<Self>, _communicate_allowed: bool, diff --git a/src/tools/miri/src/shims/unix/linux/fd/socketpair.rs b/src/tools/miri/src/shims/unix/linux/fd/socketpair.rs index f9e56b4a2b4..6adae88235f 100644 --- a/src/tools/miri/src/shims/unix/linux/fd/socketpair.rs +++ b/src/tools/miri/src/shims/unix/linux/fd/socketpair.rs @@ -19,10 +19,6 @@ impl FileDescriptor for SocketPair { Ok(Box::new(SocketPair)) } - fn is_tty(&self) -> bool { - false - } - fn close<'tcx>( self: Box<Self>, _communicate_allowed: bool, diff --git a/src/tools/miri/tests/compiletest.rs b/src/tools/miri/tests/compiletest.rs index 1d7ed34c59a..21eaeabe6ad 100644 --- a/src/tools/miri/tests/compiletest.rs +++ b/src/tools/miri/tests/compiletest.rs @@ -139,8 +139,9 @@ regexes! { STDOUT: // Windows file paths r"\\" => "/", - // erase Stacked Borrows tags + // erase borrow tags "<[0-9]+>" => "<TAG>", + "<[0-9]+=" => "<TAG=", } regexes! { @@ -149,8 +150,9 @@ regexes! { r"\.rs:[0-9]+:[0-9]+(: [0-9]+:[0-9]+)?" => ".rs:LL:CC", // erase alloc ids "alloc[0-9]+" => "ALLOC", - // erase Stacked Borrows tags + // erase borrow tags "<[0-9]+>" => "<TAG>", + "<[0-9]+=" => "<TAG=", // erase whitespace that differs between platforms r" +at (.*\.rs)" => " at $1", // erase generics in backtraces diff --git a/src/tools/miri/tests/fail/stacked_borrows/retag_data_race_read.rs b/src/tools/miri/tests/fail/stacked_borrows/retag_data_race_read.rs index a63cd03366f..0637e08af9b 100644 --- a/src/tools/miri/tests/fail/stacked_borrows/retag_data_race_read.rs +++ b/src/tools/miri/tests/fail/stacked_borrows/retag_data_race_read.rs @@ -1,4 +1,4 @@ -//! Make sure that a retag acts like a write for the data race model. +//! Make sure that a retag acts like a read for the data race model. //@compile-flags: -Zmiri-preemption-rate=0 #[derive(Copy, Clone)] struct SendPtr(*mut u8); 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/adjacent-allocs.rs b/src/tools/miri/tests/pass/adjacent-allocs.rs index 0051c62121c..cbf41d68b57 100644 --- a/src/tools/miri/tests/pass/adjacent-allocs.rs +++ b/src/tools/miri/tests/pass/adjacent-allocs.rs @@ -1,3 +1,5 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows //@compile-flags: -Zmiri-permissive-provenance fn ensure_allocs_can_be_adjacent() { diff --git a/src/tools/miri/tests/pass/associated-const.rs b/src/tools/miri/tests/pass/associated-const.rs index 2ff08ffc4bf..331fbfcefde 100644 --- a/src/tools/miri/tests/pass/associated-const.rs +++ b/src/tools/miri/tests/pass/associated-const.rs @@ -1,3 +1,5 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows trait Foo { const ID: i32; } diff --git a/src/tools/miri/tests/pass/assume_bug.rs b/src/tools/miri/tests/pass/assume_bug.rs index e14f875c022..662b9015088 100644 --- a/src/tools/miri/tests/pass/assume_bug.rs +++ b/src/tools/miri/tests/pass/assume_bug.rs @@ -1,3 +1,5 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows fn main() { vec![()].into_iter(); } diff --git a/src/tools/miri/tests/pass/atomic.rs b/src/tools/miri/tests/pass/atomic.rs index e3d80a78916..60b8ff87b59 100644 --- a/src/tools/miri/tests/pass/atomic.rs +++ b/src/tools/miri/tests/pass/atomic.rs @@ -1,3 +1,5 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows //@compile-flags: -Zmiri-strict-provenance #![feature(strict_provenance, strict_provenance_atomic_ptr)] use std::sync::atomic::{ diff --git a/src/tools/miri/tests/pass/available-parallelism.rs b/src/tools/miri/tests/pass/available-parallelism.rs index eb4d09b1f54..77fb78424ba 100644 --- a/src/tools/miri/tests/pass/available-parallelism.rs +++ b/src/tools/miri/tests/pass/available-parallelism.rs @@ -1,3 +1,5 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows fn main() { assert_eq!(std::thread::available_parallelism().unwrap().get(), 1); } diff --git a/src/tools/miri/tests/pass/box-custom-alloc.rs b/src/tools/miri/tests/pass/box-custom-alloc.rs index ef432a86d46..155e3d74ab9 100644 --- a/src/tools/miri/tests/pass/box-custom-alloc.rs +++ b/src/tools/miri/tests/pass/box-custom-alloc.rs @@ -1,3 +1,5 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows #![allow(incomplete_features)] // for trait upcasting #![feature(allocator_api, trait_upcasting)] diff --git a/src/tools/miri/tests/pass/box.rs b/src/tools/miri/tests/pass/box.rs index 7bbe7be516b..3bb481aab88 100644 --- a/src/tools/miri/tests/pass/box.rs +++ b/src/tools/miri/tests/pass/box.rs @@ -1,3 +1,5 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows -Zmiri-permissive-provenance #![feature(ptr_internals)] fn main() { diff --git a/src/tools/miri/tests/pass/box.stderr b/src/tools/miri/tests/pass/box.stack.stderr index 4c2fb40e110..4c2fb40e110 100644 --- a/src/tools/miri/tests/pass/box.stderr +++ b/src/tools/miri/tests/pass/box.stack.stderr diff --git a/src/tools/miri/tests/pass/box.stdout b/src/tools/miri/tests/pass/box.stack.stdout index 230ef368da6..230ef368da6 100644 --- a/src/tools/miri/tests/pass/box.stdout +++ b/src/tools/miri/tests/pass/box.stack.stdout diff --git a/src/tools/miri/tests/pass/box.tree.stdout b/src/tools/miri/tests/pass/box.tree.stdout new file mode 100644 index 00000000000..230ef368da6 --- /dev/null +++ b/src/tools/miri/tests/pass/box.tree.stdout @@ -0,0 +1,3 @@ +pair_foo = PairFoo { fst: Foo(42), snd: Foo(1337) } +foo #0 = Foo(42) +foo #1 = Foo(1337) diff --git a/src/tools/miri/tests/pass/btreemap.rs b/src/tools/miri/tests/pass/btreemap.rs index 040c648d474..b7c0406becc 100644 --- a/src/tools/miri/tests/pass/btreemap.rs +++ b/src/tools/miri/tests/pass/btreemap.rs @@ -1,3 +1,5 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows //@compile-flags: -Zmiri-strict-provenance #![feature(btree_drain_filter)] use std::collections::{BTreeMap, BTreeSet}; diff --git a/src/tools/miri/tests/pass/cast-rfc0401-vtable-kinds.rs b/src/tools/miri/tests/pass/cast-rfc0401-vtable-kinds.rs index d76c23633da..ccf96b99672 100644 --- a/src/tools/miri/tests/pass/cast-rfc0401-vtable-kinds.rs +++ b/src/tools/miri/tests/pass/cast-rfc0401-vtable-kinds.rs @@ -1,3 +1,5 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows // Check that you can cast between different pointers to trait objects // whose vtable have the same kind (both lengths, or both trait pointers). diff --git a/src/tools/miri/tests/pass/concurrency/channels.rs b/src/tools/miri/tests/pass/concurrency/channels.rs index 53b57942d76..43086756b03 100644 --- a/src/tools/miri/tests/pass/concurrency/channels.rs +++ b/src/tools/miri/tests/pass/concurrency/channels.rs @@ -1,3 +1,5 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows //@compile-flags: -Zmiri-strict-provenance use std::sync::mpsc::{channel, sync_channel}; diff --git a/src/tools/miri/tests/pass/concurrency/sync.rs b/src/tools/miri/tests/pass/concurrency/sync.rs index 19ea6c130bd..3bd1e542407 100644 --- a/src/tools/miri/tests/pass/concurrency/sync.rs +++ b/src/tools/miri/tests/pass/concurrency/sync.rs @@ -1,3 +1,5 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows //@compile-flags: -Zmiri-disable-isolation -Zmiri-strict-provenance use std::sync::{Arc, Barrier, Condvar, Mutex, Once, RwLock}; diff --git a/src/tools/miri/tests/pass/concurrency/sync.stdout b/src/tools/miri/tests/pass/concurrency/sync.stack.stdout index f2c036a1735..f2c036a1735 100644 --- a/src/tools/miri/tests/pass/concurrency/sync.stdout +++ b/src/tools/miri/tests/pass/concurrency/sync.stack.stdout diff --git a/src/tools/miri/tests/pass/concurrency/sync.tree.stdout b/src/tools/miri/tests/pass/concurrency/sync.tree.stdout new file mode 100644 index 00000000000..f2c036a1735 --- /dev/null +++ b/src/tools/miri/tests/pass/concurrency/sync.tree.stdout @@ -0,0 +1,20 @@ +before wait +before wait +before wait +before wait +before wait +before wait +before wait +before wait +before wait +before wait +after wait +after wait +after wait +after wait +after wait +after wait +after wait +after wait +after wait +after wait diff --git a/src/tools/miri/tests/pass/concurrency/thread_locals.rs b/src/tools/miri/tests/pass/concurrency/thread_locals.rs index b19e56312f3..13c11b55775 100644 --- a/src/tools/miri/tests/pass/concurrency/thread_locals.rs +++ b/src/tools/miri/tests/pass/concurrency/thread_locals.rs @@ -1,3 +1,5 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows //@compile-flags: -Zmiri-strict-provenance //! The main purpose of this test is to check that if we take a pointer to diff --git a/src/tools/miri/tests/pass/concurrency/tls_lib_drop.rs b/src/tools/miri/tests/pass/concurrency/tls_lib_drop.rs index 7ccafec6037..bd06eec9cd5 100644 --- a/src/tools/miri/tests/pass/concurrency/tls_lib_drop.rs +++ b/src/tools/miri/tests/pass/concurrency/tls_lib_drop.rs @@ -1,3 +1,6 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows + use std::cell::RefCell; use std::thread; diff --git a/src/tools/miri/tests/pass/concurrency/tls_lib_drop.stdout b/src/tools/miri/tests/pass/concurrency/tls_lib_drop.stack.stdout index b7877820a0c..b7877820a0c 100644 --- a/src/tools/miri/tests/pass/concurrency/tls_lib_drop.stdout +++ b/src/tools/miri/tests/pass/concurrency/tls_lib_drop.stack.stdout diff --git a/src/tools/miri/tests/pass/concurrency/tls_lib_drop.tree.stdout b/src/tools/miri/tests/pass/concurrency/tls_lib_drop.tree.stdout new file mode 100644 index 00000000000..b7877820a0c --- /dev/null +++ b/src/tools/miri/tests/pass/concurrency/tls_lib_drop.tree.stdout @@ -0,0 +1,5 @@ +Dropping: 8 (should be before 'Continue main 1'). +Dropping: 8 (should be before 'Continue main 1'). +Continue main 1. +Joining: 7 (should be before 'Continue main 2'). +Continue main 2. diff --git a/src/tools/miri/tests/pass/disable-alignment-check.rs b/src/tools/miri/tests/pass/disable-alignment-check.rs index 366aff4a9f8..fdcacc6cea4 100644 --- a/src/tools/miri/tests/pass/disable-alignment-check.rs +++ b/src/tools/miri/tests/pass/disable-alignment-check.rs @@ -1,3 +1,5 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows //@compile-flags: -Zmiri-disable-alignment-check fn main() { diff --git a/src/tools/miri/tests/pass/dyn-arbitrary-self.rs b/src/tools/miri/tests/pass/dyn-arbitrary-self.rs index 256c72add92..94cf465e884 100644 --- a/src/tools/miri/tests/pass/dyn-arbitrary-self.rs +++ b/src/tools/miri/tests/pass/dyn-arbitrary-self.rs @@ -1,3 +1,5 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows #![feature(arbitrary_self_types, unsize, coerce_unsized, dispatch_from_dyn)] #![feature(rustc_attrs)] diff --git a/src/tools/miri/tests/pass/extern_types.rs b/src/tools/miri/tests/pass/extern_types.rs index aa4c65ea892..7ac93577f0c 100644 --- a/src/tools/miri/tests/pass/extern_types.rs +++ b/src/tools/miri/tests/pass/extern_types.rs @@ -1,3 +1,5 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows -Zmiri-permissive-provenance #![feature(extern_types)] extern "C" { diff --git a/src/tools/miri/tests/pass/extern_types.stderr b/src/tools/miri/tests/pass/extern_types.stack.stderr index 2e18f693058..2e18f693058 100644 --- a/src/tools/miri/tests/pass/extern_types.stderr +++ b/src/tools/miri/tests/pass/extern_types.stack.stderr diff --git a/src/tools/miri/tests/pass/float.rs b/src/tools/miri/tests/pass/float.rs index ce62fb0de04..fee5ca44ffb 100644 --- a/src/tools/miri/tests/pass/float.rs +++ b/src/tools/miri/tests/pass/float.rs @@ -1,4 +1,5 @@ #![feature(stmt_expr_attributes)] +#![feature(round_ties_even)] #![allow(arithmetic_overflow)] use std::fmt::Debug; use std::hint::black_box; @@ -9,6 +10,7 @@ fn main() { more_casts(); ops(); nan_casts(); + rounding(); } // Helper function to avoid promotion so that this tests "run-time" casts, not CTFE. @@ -553,3 +555,31 @@ fn nan_casts() { assert!(nan1_32.is_nan()); assert!(nan2_32.is_nan()); } + +fn rounding() { + // Test cases taken from the library's tests for this feature + // f32 + assert_eq(2.5f32.round_ties_even(), 2.0f32); + assert_eq(1.0f32.round_ties_even(), 1.0f32); + assert_eq(1.3f32.round_ties_even(), 1.0f32); + assert_eq(1.5f32.round_ties_even(), 2.0f32); + assert_eq(1.7f32.round_ties_even(), 2.0f32); + assert_eq(0.0f32.round_ties_even(), 0.0f32); + assert_eq((-0.0f32).round_ties_even(), -0.0f32); + assert_eq((-1.0f32).round_ties_even(), -1.0f32); + assert_eq((-1.3f32).round_ties_even(), -1.0f32); + assert_eq((-1.5f32).round_ties_even(), -2.0f32); + assert_eq((-1.7f32).round_ties_even(), -2.0f32); + // f64 + assert_eq(2.5f64.round_ties_even(), 2.0f64); + assert_eq(1.0f64.round_ties_even(), 1.0f64); + assert_eq(1.3f64.round_ties_even(), 1.0f64); + assert_eq(1.5f64.round_ties_even(), 2.0f64); + assert_eq(1.7f64.round_ties_even(), 2.0f64); + assert_eq(0.0f64.round_ties_even(), 0.0f64); + assert_eq((-0.0f64).round_ties_even(), -0.0f64); + assert_eq((-1.0f64).round_ties_even(), -1.0f64); + assert_eq((-1.3f64).round_ties_even(), -1.0f64); + assert_eq((-1.5f64).round_ties_even(), -2.0f64); + assert_eq((-1.7f64).round_ties_even(), -2.0f64); +} diff --git a/src/tools/miri/tests/pass/stacked-borrows/future-self-referential.rs b/src/tools/miri/tests/pass/future-self-referential.rs index 6994def16a1..763eceeb6f0 100644 --- a/src/tools/miri/tests/pass/stacked-borrows/future-self-referential.rs +++ b/src/tools/miri/tests/pass/future-self-referential.rs @@ -1,3 +1,6 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows + use std::future::*; use std::marker::PhantomPinned; use std::pin::*; diff --git a/src/tools/miri/tests/pass/generator.rs b/src/tools/miri/tests/pass/generator.rs index 06f48666c55..e059c7114e3 100644 --- a/src/tools/miri/tests/pass/generator.rs +++ b/src/tools/miri/tests/pass/generator.rs @@ -1,3 +1,5 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows #![feature(generators, generator_trait, never_type)] use std::fmt::Debug; diff --git a/src/tools/miri/tests/pass/hashmap.rs b/src/tools/miri/tests/pass/hashmap.rs index 29ddd6c59a1..7224e357c6f 100644 --- a/src/tools/miri/tests/pass/hashmap.rs +++ b/src/tools/miri/tests/pass/hashmap.rs @@ -1,3 +1,5 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows use std::collections::HashMap; use std::hash::BuildHasher; diff --git a/src/tools/miri/tests/pass/intptrcast.rs b/src/tools/miri/tests/pass/intptrcast.rs index e7ff90cb6bf..42b6f433420 100644 --- a/src/tools/miri/tests/pass/intptrcast.rs +++ b/src/tools/miri/tests/pass/intptrcast.rs @@ -1,3 +1,5 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows //@compile-flags: -Zmiri-permissive-provenance use std::mem; diff --git a/src/tools/miri/tests/pass/linked-list.rs b/src/tools/miri/tests/pass/linked-list.rs index 7377f9f60b0..36df30070cb 100644 --- a/src/tools/miri/tests/pass/linked-list.rs +++ b/src/tools/miri/tests/pass/linked-list.rs @@ -1,3 +1,5 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows #![feature(linked_list_cursors)] use std::collections::LinkedList; diff --git a/src/tools/miri/tests/pass/many_shr_bor.rs b/src/tools/miri/tests/pass/many_shr_bor.rs index 376b41dd6e2..aa960aa147a 100644 --- a/src/tools/miri/tests/pass/many_shr_bor.rs +++ b/src/tools/miri/tests/pass/many_shr_bor.rs @@ -1,3 +1,5 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows // Make sure validation can handle many overlapping shared borrows for different parts of a data structure use std::cell::RefCell; diff --git a/src/tools/miri/tests/pass/memleak_ignored.rs b/src/tools/miri/tests/pass/memleak_ignored.rs index 60e06094e17..bba3207ee4c 100644 --- a/src/tools/miri/tests/pass/memleak_ignored.rs +++ b/src/tools/miri/tests/pass/memleak_ignored.rs @@ -1,3 +1,5 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows //@compile-flags: -Zmiri-ignore-leaks fn main() { diff --git a/src/tools/miri/tests/pass/option_box_transmute_ptr.rs b/src/tools/miri/tests/pass/option_box_transmute_ptr.rs index 0786db1ef89..0ba6607a5d4 100644 --- a/src/tools/miri/tests/pass/option_box_transmute_ptr.rs +++ b/src/tools/miri/tests/pass/option_box_transmute_ptr.rs @@ -1,3 +1,5 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows // This tests that the size of Option<Box<i32>> is the same as *const i32. fn option_box_deref() -> i32 { let val = Some(Box::new(42)); diff --git a/src/tools/miri/tests/pass/pointers.rs b/src/tools/miri/tests/pass/pointers.rs index d1340a04e04..1525ded6151 100644 --- a/src/tools/miri/tests/pass/pointers.rs +++ b/src/tools/miri/tests/pass/pointers.rs @@ -1,3 +1,5 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows //@compile-flags: -Zmiri-permissive-provenance #![feature(ptr_metadata, const_raw_ptr_comparison)] diff --git a/src/tools/miri/tests/pass/provenance.rs b/src/tools/miri/tests/pass/provenance.rs index c411f748a06..835daa36cfc 100644 --- a/src/tools/miri/tests/pass/provenance.rs +++ b/src/tools/miri/tests/pass/provenance.rs @@ -1,3 +1,5 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows #![feature(strict_provenance)] #![feature(pointer_byte_offsets)] use std::{mem, ptr}; diff --git a/src/tools/miri/tests/pass/ptr_int_casts.rs b/src/tools/miri/tests/pass/ptr_int_casts.rs index 3044ac092b7..a2fcd098107 100644 --- a/src/tools/miri/tests/pass/ptr_int_casts.rs +++ b/src/tools/miri/tests/pass/ptr_int_casts.rs @@ -1,3 +1,5 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows //@compile-flags: -Zmiri-permissive-provenance use std::mem; use std::ptr; diff --git a/src/tools/miri/tests/pass/ptr_int_from_exposed.rs b/src/tools/miri/tests/pass/ptr_int_from_exposed.rs index ef7ff34d26b..35a52d0220b 100644 --- a/src/tools/miri/tests/pass/ptr_int_from_exposed.rs +++ b/src/tools/miri/tests/pass/ptr_int_from_exposed.rs @@ -1,3 +1,5 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows //@compile-flags: -Zmiri-permissive-provenance #![feature(strict_provenance)] diff --git a/src/tools/miri/tests/pass/ptr_int_transmute.rs b/src/tools/miri/tests/pass/ptr_int_transmute.rs index ba50480c539..d99c25413e6 100644 --- a/src/tools/miri/tests/pass/ptr_int_transmute.rs +++ b/src/tools/miri/tests/pass/ptr_int_transmute.rs @@ -1,3 +1,5 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows // Test what happens when we read parts of a pointer. // Related to <https://github.com/rust-lang/rust/issues/69488>. fn ptr_partial_read() { diff --git a/src/tools/miri/tests/pass/rc.rs b/src/tools/miri/tests/pass/rc.rs index 569dbc459a5..6375abcd232 100644 --- a/src/tools/miri/tests/pass/rc.rs +++ b/src/tools/miri/tests/pass/rc.rs @@ -1,3 +1,5 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows //@compile-flags: -Zmiri-strict-provenance #![feature(new_uninit)] #![feature(get_mut_unchecked)] diff --git a/src/tools/miri/tests/pass/send-is-not-static-par-for.rs b/src/tools/miri/tests/pass/send-is-not-static-par-for.rs index 642f75ecc09..458312508d2 100644 --- a/src/tools/miri/tests/pass/send-is-not-static-par-for.rs +++ b/src/tools/miri/tests/pass/send-is-not-static-par-for.rs @@ -1,3 +1,5 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows use std::sync::Mutex; fn par_for<I, F>(iter: I, f: F) diff --git a/src/tools/miri/tests/pass/slices.rs b/src/tools/miri/tests/pass/slices.rs index a56b97a5088..a99e921150b 100644 --- a/src/tools/miri/tests/pass/slices.rs +++ b/src/tools/miri/tests/pass/slices.rs @@ -1,3 +1,5 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows //@compile-flags: -Zmiri-strict-provenance #![feature(new_uninit)] #![feature(slice_as_chunks)] diff --git a/src/tools/miri/tests/pass/stacked-borrows/stack-printing.rs b/src/tools/miri/tests/pass/stacked-borrows/stack-printing.rs index 3ca937ae13d..74761a89cb9 100644 --- a/src/tools/miri/tests/pass/stacked-borrows/stack-printing.rs +++ b/src/tools/miri/tests/pass/stacked-borrows/stack-printing.rs @@ -7,7 +7,7 @@ use std::{ extern "Rust" { fn miri_get_alloc_id(ptr: *const u8) -> u64; - fn miri_print_borrow_stacks(alloc_id: u64); + fn miri_print_borrow_state(alloc_id: u64, show_unnamed: bool); } fn get_alloc_id(ptr: *const u8) -> u64 { @@ -15,7 +15,9 @@ fn get_alloc_id(ptr: *const u8) -> u64 { } fn print_borrow_stacks(alloc_id: u64) { - unsafe { miri_print_borrow_stacks(alloc_id) } + unsafe { + miri_print_borrow_state(alloc_id, /* ignored: show_unnamed */ false) + } } fn main() { diff --git a/src/tools/miri/tests/pass/threadleak_ignored.rs b/src/tools/miri/tests/pass/threadleak_ignored.rs index a5f81573e96..d4899856194 100644 --- a/src/tools/miri/tests/pass/threadleak_ignored.rs +++ b/src/tools/miri/tests/pass/threadleak_ignored.rs @@ -1,3 +1,5 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows //@compile-flags: -Zmiri-ignore-leaks //! Test that leaking threads works, and that their destructors are not executed. diff --git a/src/tools/miri/tests/pass/threadleak_ignored.stderr b/src/tools/miri/tests/pass/threadleak_ignored.stack.stderr index 7557f49c758..7557f49c758 100644 --- a/src/tools/miri/tests/pass/threadleak_ignored.stderr +++ b/src/tools/miri/tests/pass/threadleak_ignored.stack.stderr diff --git a/src/tools/miri/tests/pass/threadleak_ignored.tree.stderr b/src/tools/miri/tests/pass/threadleak_ignored.tree.stderr new file mode 100644 index 00000000000..7557f49c758 --- /dev/null +++ b/src/tools/miri/tests/pass/threadleak_ignored.tree.stderr @@ -0,0 +1 @@ +Dropping 0 diff --git a/src/tools/miri/tests/pass/transmute_ptr.rs b/src/tools/miri/tests/pass/transmute_ptr.rs index fd9d457e440..ce6d86b7068 100644 --- a/src/tools/miri/tests/pass/transmute_ptr.rs +++ b/src/tools/miri/tests/pass/transmute_ptr.rs @@ -1,3 +1,5 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows #![feature(strict_provenance)] use std::{mem, ptr}; 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(); + } +} diff --git a/src/tools/miri/tests/pass/unsized.rs b/src/tools/miri/tests/pass/unsized.rs index d9beac4327d..c9046dc3c76 100644 --- a/src/tools/miri/tests/pass/unsized.rs +++ b/src/tools/miri/tests/pass/unsized.rs @@ -1,3 +1,5 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows #![feature(unsized_tuple_coercion)] #![feature(unsized_fn_params)] diff --git a/src/tools/miri/tests/pass/vec.rs b/src/tools/miri/tests/pass/vec.rs index 30a28bc5803..06ec2f99172 100644 --- a/src/tools/miri/tests/pass/vec.rs +++ b/src/tools/miri/tests/pass/vec.rs @@ -1,3 +1,5 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows //@compile-flags: -Zmiri-strict-provenance #![feature(iter_advance_by, iter_next_chunk)] diff --git a/src/tools/miri/tests/pass/vecdeque.rs b/src/tools/miri/tests/pass/vecdeque.rs index 6f56f9d103e..dfbf9bb83c1 100644 --- a/src/tools/miri/tests/pass/vecdeque.rs +++ b/src/tools/miri/tests/pass/vecdeque.rs @@ -1,3 +1,5 @@ +//@revisions: stack tree +//@[tree]compile-flags: -Zmiri-tree-borrows //@compile-flags: -Zmiri-strict-provenance use std::collections::VecDeque; diff --git a/src/tools/miri/tests/pass/vecdeque.stdout b/src/tools/miri/tests/pass/vecdeque.stack.stdout index 63de960ee2b..63de960ee2b 100644 --- a/src/tools/miri/tests/pass/vecdeque.stdout +++ b/src/tools/miri/tests/pass/vecdeque.stack.stdout diff --git a/src/tools/miri/tests/pass/vecdeque.tree.stdout b/src/tools/miri/tests/pass/vecdeque.tree.stdout new file mode 100644 index 00000000000..63de960ee2b --- /dev/null +++ b/src/tools/miri/tests/pass/vecdeque.tree.stdout @@ -0,0 +1,2 @@ +[2, 2] Iter([2, 2], []) +Iter([], []) diff --git a/src/tools/miri/tests/utils/macros.rs b/src/tools/miri/tests/utils/macros.rs new file mode 100644 index 00000000000..de223410fba --- /dev/null +++ b/src/tools/miri/tests/utils/macros.rs @@ -0,0 +1,61 @@ +#![allow(unused_macros)] +#![allow(unused_macro_rules)] +#![allow(unused_imports)] + +/// `alloc_id!(ptr)`: obtain the allocation id from a pointer. +/// +/// `ptr` should be any pointer or reference that can be converted with `_ as *const u8`. +/// +/// The id obtained can be passed directly to `print_state!`. +macro_rules! alloc_id { + ($ptr:expr) => { + crate::utils::miri_extern::miri_get_alloc_id($ptr as *const u8 as *const ()) + }; +} + +/// `print_state!(alloc_id, show_unnamed)`: print the internal state of the borrow +/// tracker (stack or tree). +/// +/// `alloc_id` should be obtained from `alloc_id!`. +/// +/// `show_unnamed` is an optional boolean that determines if Tree Borrows displays +/// tags that have not been given a name. Defaults to `false`. +macro_rules! print_state { + ($alloc_id:expr) => { + crate::utils::macros::print_state!($alloc_id, false); + }; + ($alloc_id:expr, $show:expr) => { + crate::utils::miri_extern::miri_print_borrow_state($alloc_id, $show); + }; +} + +/// `name!(ptr => nth_parent, name)`: associate `name` to the `nth_parent` of `ptr`. +/// +/// `ptr` should be any pointer or reference that can be converted with `_ as *const u8`. +/// +/// `nth_parent` is an optional `u8` that defaults to 0. The corresponding ancestor +/// of the tag of `ptr` will be searched: 0 for `ptr` itself, 1 for the direct parent +/// of `ptr`, 2 for the grandparent, etc. If `nth_parent` is not specified, +/// then `=>` should also not be included. +/// +/// `name` is an optional string that will be used as the name. Defaults to +/// `stringify!($ptr)` the name of `ptr` in the source code. +macro_rules! name { + ($ptr:expr, $name:expr) => { + crate::utils::macros::name!($ptr => 0, $name); + }; + ($ptr:expr) => { + crate::utils::macros::name!($ptr => 0, stringify!($ptr)); + }; + ($ptr:expr => $nb:expr) => { + crate::utils::macros::name!($ptr => $nb, stringify!($ptr)); + }; + ($ptr:expr => $nb:expr, $name:expr) => { + let name = $name.as_bytes(); + crate::utils::miri_extern::miri_pointer_name($ptr as *const u8 as *const (), $nb, name); + }; +} + +pub(crate) use alloc_id; +pub(crate) use name; +pub(crate) use print_state; diff --git a/src/tools/miri/tests/utils/miri_extern.rs b/src/tools/miri/tests/utils/miri_extern.rs new file mode 100644 index 00000000000..6c4298c613b --- /dev/null +++ b/src/tools/miri/tests/utils/miri_extern.rs @@ -0,0 +1,142 @@ +#![allow(dead_code)] + +#[repr(C)] +/// Layout of the return value of `miri_resolve_frame`, +/// with fields in the exact same order. +pub struct MiriFrame { + // The size of the name of the function being executed, encoded in UTF-8 + pub name_len: usize, + // The size of filename of the function being executed, encoded in UTF-8 + pub filename_len: usize, + // The line number currently being executed in `filename`, starting from '1'. + pub lineno: u32, + // The column number currently being executed in `filename`, starting from '1'. + pub colno: u32, + // The function pointer to the function currently being executed. + // This can be compared against function pointers obtained by + // casting a function (e.g. `my_fn as *mut ()`) + pub fn_ptr: *mut (), +} + +#[cfg(miri)] +extern "Rust" { + /// Miri-provided extern function to mark the block `ptr` points to as a "root" + /// for some static memory. This memory and everything reachable by it is not + /// considered leaking even if it still exists when the program terminates. + /// + /// `ptr` has to point to the beginning of an allocated block. + pub fn miri_static_root(ptr: *const u8); + + // Miri-provided extern function to get the amount of frames in the current backtrace. + // The `flags` argument must be `0`. + pub fn miri_backtrace_size(flags: u64) -> usize; + + /// Miri-provided extern function to obtain a backtrace of the current call stack. + /// This writes a slice of pointers into `buf` - each pointer is an opaque value + /// that is only useful when passed to `miri_resolve_frame`. + /// `buf` must have `miri_backtrace_size(0) * pointer_size` bytes of space. + /// The `flags` argument must be `1`. + pub fn miri_get_backtrace(flags: u64, buf: *mut *mut ()); + + /// Miri-provided extern function to resolve a frame pointer obtained + /// from `miri_get_backtrace`. The `flags` argument must be `1`. + /// + /// This function can be called on any thread (not just the one which obtained `frame`). + pub fn miri_resolve_frame(frame: *mut (), flags: u64) -> MiriFrame; + + /// Miri-provided extern function to get the name and filename of the frame provided by `miri_resolve_frame`. + /// `name_buf` and `filename_buf` should be allocated with the `name_len` and `filename_len` fields of `MiriFrame`. + /// The flags argument must be `0`. + pub fn miri_resolve_frame_names( + ptr: *mut (), + flags: u64, + name_buf: *mut u8, + filename_buf: *mut u8, + ); + + /// Miri-provided extern function to begin unwinding with the given payload. + /// + /// This is internal and unstable and should not be used; we give it here + /// just to be complete. + pub fn miri_start_panic(payload: *mut u8) -> !; + + /// Miri-provided extern function to get the internal unique identifier for the allocation that a pointer + /// points to. If this pointer is invalid (not pointing to an allocation), interpretation will abort. + /// + /// This is only useful as an input to `miri_print_borrow_stacks`, and it is a separate call because + /// getting a pointer to an allocation at runtime can change the borrow stacks in the allocation. + /// This function should be considered unstable. It exists only to support `miri_print_borrow_stacks` and so + /// inherits all of its instability. + pub fn miri_get_alloc_id(ptr: *const ()) -> u64; + + /// Miri-provided extern function to print (from the interpreter, not the program) the contents of all + /// borrows in an allocation. + /// + /// If Stacked Borrows is running, this prints all the stacks. The leftmost tag is the bottom of the stack. + /// + /// If Tree borrows is running, this prints on the left the permissions of each tag on each range, + /// an on the right the tree structure of the tags. If some tags were named via `miri_pointer_name`, + /// their names appear here. + /// + /// If additionally `show_unnamed` is `false` then tags that did *not* receive a name will be hidden. + /// Ensure that either the important tags have been named, or `show_unnamed = true`. + /// Note: as Stacked Borrows does not have tag names at all, `show_unnamed` is ignored and all tags are shown. + /// In general, unless you strongly want some tags to be hidden (as is the case in `tree-borrows` tests), + /// `show_unnamed = true` should be the default. + /// + /// 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 is extremely unstable. At any time the format of its output may change, its signature may + /// change, or it may be removed entirely. + pub fn miri_print_borrow_state(alloc_id: u64, show_unnamed: bool); + + /// Miri-provided extern function to associate a name to the nth parent of a tag. + /// Typically the name given would be the name of the program variable that holds the pointer. + /// Unreachable tags can still be named by using nonzero `nth_parent` and a child tag. + /// + /// This function does nothing under Stacked Borrows, since Stacked Borrows's implementation + /// of `miri_print_borrow_state` does not show the names. + /// + /// Under Tree Borrows, the names also appear in error messages. + pub fn miri_pointer_name(ptr: *const (), nth_parent: u8, name: &[u8]); + + /// Miri-provided extern function to print (from the interpreter, not the + /// program) the contents of a section of program memory, as bytes. Bytes + /// written using this function will emerge from the interpreter's stdout. + pub fn miri_write_to_stdout(bytes: &[u8]); + + /// Miri-provided extern function to print (from the interpreter, not the + /// program) the contents of a section of program memory, as bytes. Bytes + /// written using this function will emerge from the interpreter's stderr. + pub fn miri_write_to_stderr(bytes: &[u8]); + + /// Miri-provided extern function to allocate memory from the interpreter. + /// + /// This is useful when no fundamental way of allocating memory is + /// available, e.g. when using `no_std` + `alloc`. + pub fn miri_alloc(size: usize, align: usize) -> *mut u8; + + /// Miri-provided extern function to deallocate memory. + pub fn miri_dealloc(ptr: *mut u8, size: usize, align: usize); + + /// Convert a path from the host Miri runs on to the target Miri interprets. + /// Performs conversion of path separators as needed. + /// + /// Usually Miri performs this kind of conversion automatically. However, manual conversion + /// might be necessary when reading an environment variable that was set on the host + /// (such as TMPDIR) and using it as a target path. + /// + /// Only works with isolation disabled. + /// + /// `in` must point to a null-terminated string, and will be read as the input host path. + /// `out` must point to at least `out_size` many bytes, and the result will be stored there + /// with a null terminator. + /// Returns 0 if the `out` buffer was large enough, and the required size otherwise. + pub fn miri_host_to_target_path( + path: *const std::ffi::c_char, + out: *mut std::ffi::c_char, + out_size: usize, + ) -> usize; +} diff --git a/src/tools/miri/tests/utils/mod.rs b/src/tools/miri/tests/utils/mod.rs new file mode 100644 index 00000000000..e1ea77e4df8 --- /dev/null +++ b/src/tools/miri/tests/utils/mod.rs @@ -0,0 +1,2 @@ +pub mod macros; +pub mod miri_extern; |