bors [Tue, 21 Jun 2022 07:39:16 +0000 (07:39 +0000)]
Auto merge of #2249 - dtolnay-contrib:rustfmt3, r=oli-obk
Format tests with rustfmt (151-200 of 300)
Extracted from #2097.
This PR is still only doing the easy cases with no comments involved.
In the next PRs after this, I'll start grouping by common comment patterns, e.g. all the cases resembling https://github.com/rust-lang/miri/pull/2097#discussion_r862436672 together in one PR.
bors [Tue, 21 Jun 2022 02:51:35 +0000 (02:51 +0000)]
Auto merge of #2244 - dtolnay-contrib:rustfmt0, r=RalfJung
Format tests and benches with rustfmt (1-50 of 300)
Extracted from #2097.
I filtered this PR to contain exclusively "easy" cases to start off with, i.e. where there is no compiletest_rs (or other) comment in the vicinity that might need to get manually repositioned.
bors [Mon, 20 Jun 2022 05:23:46 +0000 (05:23 +0000)]
Auto merge of #2242 - dtolnay-contrib:rustfmtskip, r=RalfJung
Add rustfmt::skip to some files
Extracted from https://github.com/rust-lang/miri/pull/2097.
Five of the files being skipped here are because rustfmt is buggy (https://github.com/rust-lang/rustfmt/issues/5391; see the error messages below). The other two have clearly preferable manual formatting.
David Tolnay [Sat, 30 Apr 2022 18:07:36 +0000 (11:07 -0700)]
Add rustfmt::skip to some files
Five of the files being skipped here are because rustfmt is buggy (see
the error messages below). The others have clearly preferable manual
formatting.
bors [Sat, 18 Jun 2022 15:10:56 +0000 (15:10 +0000)]
Auto merge of #2228 - cbeuw:futex-fix, r=RalfJung
Prevent futex_wait from actually waiting if a concurrent waker was executed before us
Fixes #2223
Two SC fences were placed in `futex_wake` (after the caller has changed `addr`), and in `futex_wait` (before we read `addr`). This guarantees that `futex_wait` sees the value written to `addr` before the last `futex_wake` call, should one exists, and avoid going into sleep with no one else to wake us up.
https://github.com/rust-lang/miri/blob/ada7b72a879d79aaa06f0a2a95edd520615da1a2/src/concurrency/weak_memory.rs#L324-L326
Earlier I proposed to use `fetch_add(0)` to read the latest value in MO, though this isn't the proper way to do it and breaks aliasing: syscall caller may pass in a `*const` from a `&` and Miri complains about write to a `SharedReadOnly` location, causing this test to fail.
https://github.com/rust-lang/miri/blob/ada7b72a879d79aaa06f0a2a95edd520615da1a2/tests/pass/concurrency/linux-futex.rs#L56-L68
bors [Mon, 13 Jun 2022 16:08:54 +0000 (16:08 +0000)]
Auto merge of #2207 - RalfJung:ui_test_parallelism, r=oli-obk
ui_test: ensure all worker threads stay around
Also organize files such that the by far slowest test (weak_memory/consistency) always starts first. It still finishes last on my system... even after I halved the iteration count.
bors [Thu, 9 Jun 2022 14:20:42 +0000 (14:20 +0000)]
Auto merge of #2219 - saethlin:more-benchmarks, r=RalfJung
Add more bench-cargo-miri programs
These example programs are derived from long-running (>15 minutes) tests in the test suites of highly-downloaded crates (if I have my way, that runtime will not be correct for long). They should serve as realistic but also somewhat pathological workloads for the interpreter.
The unicode program stresses the code which looks for adjacent and equal stacks to merge them.
The backtraces program has an uncommonly large working set of borrow tags per borrow stack.
This also updates the .gitignore to ignore files commonly emitted in the course of using these benchmark programs.
---
The benchmark programs are so-named to avoid confusingly duplicating the names of the crates they are benchmarking. Is that a good idea? I started doing this so that I could use `cargo add` but now I'm not entirely sold on the names.
Ben Kimock [Wed, 8 Jun 2022 23:32:43 +0000 (19:32 -0400)]
Add more bench-cargo-miri programs
These example programs are derived from long-running (>15 minutes) tests
in the test suites of highly-downloaded crates. They should serve as
realistic but also somewhat pathological workloads for the interpreter.
The unicode program stresses the code which looks for adjacent and equal
stacks to merge them.
The backtrace program has an uncommonly large working set of borrow tags
per borrow stack.
This also updates the .gitignore to ignore files commonly emitted in the
course of using these benchmark programs.
bors [Tue, 7 Jun 2022 01:48:57 +0000 (01:48 +0000)]
Auto merge of #2208 - RalfJung:preempt, r=RalfJung
Make scheduler preemptive
This is actually fairly easy. :D I just roll the dice on each terminator to decide whether we want to yield the active thread. I think with this we are also justified to no longer show "experimental" warnings when a thread is spawned. :)
bors [Mon, 6 Jun 2022 19:30:38 +0000 (19:30 +0000)]
Auto merge of #1963 - cbeuw:weak-memory, r=RalfJung
Weak memory emulation using store buffers
This implements the second half of the [Lidbury & Donaldson paper](https://www.doc.ic.ac.uk/~afd/homepages/papers/pdfs/2017/POPL.pdf): weak memory emulation using store buffers. A store buffer is created over a memory range on atomic access. Stores will push store elements into the buffer and loads will search through the buffer in reverse modification order, determine which store elements are valid for the current load, and pick one randomly.
This implementation will never generate weak memory behaviours forbidden by the C++11 model, but it is incapable of producing all possible weak behaviours allowed by the model. There are certain weak behaviours observable on real hardware but not while using this.
Note that this implementation does not take into account of C++20's memory model revision to SC accesses and fences introduced by [P0668](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0668r5.html). This implementation is not fully correct under the revised C++20 model and may generate behaviours C++20 disallows.
Rust follows the C++20 memory model (except for the Consume ordering and some operations not performable through C++'s std::atomic<T> API). It is therefore possible for this implementation to generate behaviours never observable when the same program is compiled and run natively. Unfortunately, no literature exists at the time of writing which proposes an implementable and C++20-compatible relaxed memory model that supports all atomic operation existing in Rust. The closest one is [A Promising Semantics for Relaxed-Memory Concurrency](https://www.cs.tau.ac.il/~orilahav/papers/popl17.pdf) by Jeehoon Kang et al. However, this model lacks SC accesses and is therefore unusable by Miri (SC accesses are everywhere in library code).
Safe/sound Rust allows for more operations on atomic locations than the C++20 atomic API was intended to allow, such as non-atomically accessing a previously atomically accessed location, or accessing previously atomically accessed locations with a differently sized operation (such as accessing the top 16 bits of an `AtomicU32`). These scenarios are generally left undefined in formalisations of C++ memory model, even though they [became possible](https://lists.isocpp.org/std-discussion/2022/05/1662.php) in C++20 with `std::atomic_ref<T>`. In Rust, these operations can only be done through a `&mut AtomicFoo` reference or one derived from it, therefore these operations can only happen after all previous accesses on the same locations. This implementation is adapted to accommodate these.
----------
TODOs:
- [x] Add tests cases that actually demonstrate weak memory behaviour (even if they are scheduler dependent)
- [x] Change `{mutex, rwlock, cond, srwlock}_get_or_create_id` functions under `src/shims` to use atomic RMWs instead of separate read -> check if need to create a new one -> write steps
- [x] Make sure Crossbeam tests still pass (https://github.com/crossbeam-rs/crossbeam/pull/831)
- [x] Move as much weak-memory related code as possible into `weak_memory.rs`
- [x] Remove "weak memory effects are not emulated" warnings
- [x] Accommodate certain mixed size and mixed atomicity accesses Rust allows on top of the C++ model