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
bors [Sun, 5 Jun 2022 18:37:07 +0000 (18:37 +0000)]
Auto merge of #2197 - RalfJung:round-robin, r=RalfJung
make Miri's scheduler proper round-robin
When thread N blocks or yields, we activate thread N+1 next, rather than always activating thread 0. This should guarantee that as long as all threads regularly yield, each thread eventually takes a step again.
Fixes the "multiple loops that yield playing ping-pong" part of https://github.com/rust-lang/miri/issues/1388.
`@cbeuw` I hope this doesn't screw up the scheduler-dependent tests you are adding in your PR.
bors [Sun, 5 Jun 2022 15:18:39 +0000 (15:18 +0000)]
Auto merge of #2189 - RalfJung:clippy, r=RalfJung
run Clippy on CI
and fix some things it complains about. Also use `rustup-toolchain` script on CI (reduces code duplication, and good thing to make sure it keeps working, since we recommend it in the docs).
I left `ui_test` out for now; I'll leave those nits to `@oli-obk.` ;)
bors [Wed, 1 Jun 2022 13:01:22 +0000 (13:01 +0000)]
Auto merge of #2174 - RalfJung:summary, r=oli-obk
print list of failed tests in summary
compiletest does this and it is quite useful; see e.g. [here](https://github.com/rust-lang/rust/runs/6473917188?check_suite_focus=true). Example output:
bors [Wed, 1 Jun 2022 07:22:31 +0000 (07:22 +0000)]
Auto merge of #2173 - RalfJung:rustlib, r=oli-obk
different strategy for normalizing Rust stdlib path
`-Zremap-cwd-prefix` has some [unintended side-effects](https://github.com/rust-lang/miri/issues/2172), so we could use regexp-based normalization instead. Unfortunately, this will fail if the user's home directory contains a space.