Skip to content

Commit e22bdbc

Browse files
rust-timerrust-timer
authored
Unrolled build for rust-lang#118029
Rollup merge of rust-lang#118029 - saethlin:allocid-gc, r=RalfJung Expand Miri's BorTag GC to a Provenance GC As suggested in rust-lang/miri#3080 (comment) We previously solved memory growth issues associated with the Stacked Borrows and Tree Borrows runtimes with a GC. But of course we also have state accumulation associated with whole allocations elsewhere in the interpreter, and this PR starts tackling those. To do this, we expand the visitor for the GC so that it can visit a BorTag or an AllocId. Instead of collecting all live AllocIds into a single HashSet, we just collect from the Machine itself then go through an accessor `InterpCx::is_alloc_live` which checks a number of allocation data structures in the core interpreter. This avoids the overhead of all the inserts that collecting their keys would require. r? ``@RalfJung``
2 parents e24e5af + 9ada654 commit e22bdbc

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

45 files changed

+459
-316
lines changed

‎compiler/rustc_const_eval/src/const_eval/machine.rs

+8
Original file line numberDiff line numberDiff line change
@@ -107,6 +107,14 @@ impl<K: Hash + Eq, V> interpret::AllocMap<K, V> for FxIndexMap<K, V> {
107107
FxIndexMap::contains_key(self, k)
108108
}
109109

110+
#[inline(always)]
111+
fn contains_key_ref<Q: ?Sized + Hash + Eq>(&self, k: &Q) -> bool
112+
where
113+
K: Borrow<Q>,
114+
{
115+
FxIndexMap::contains_key(self, k)
116+
}
117+
110118
#[inline(always)]
111119
fn insert(&mut self, k: K, v: V) -> Option<V> {
112120
FxIndexMap::insert(self, k, v)

‎compiler/rustc_const_eval/src/interpret/machine.rs

+8
Original file line numberDiff line numberDiff line change
@@ -49,6 +49,14 @@ pub trait AllocMap<K: Hash + Eq, V> {
4949
where
5050
K: Borrow<Q>;
5151

52+
/// Callers should prefer [`AllocMap::contains_key`] when it is possible to call because it may
53+
/// be more efficient. This function exists for callers that only have a shared reference
54+
/// (which might make it slightly less efficient than `contains_key`, e.g. if
55+
/// the data is stored inside a `RefCell`).
56+
fn contains_key_ref<Q: ?Sized + Hash + Eq>(&self, k: &Q) -> bool
57+
where
58+
K: Borrow<Q>;
59+
5260
/// Inserts a new entry into the map.
5361
fn insert(&mut self, k: K, v: V) -> Option<V>;
5462

‎compiler/rustc_const_eval/src/interpret/memory.rs

+9
Original file line numberDiff line numberDiff line change
@@ -692,6 +692,15 @@ impl<'mir, 'tcx: 'mir, M: Machine<'mir, 'tcx>> InterpCx<'mir, 'tcx, M> {
692692
Ok((&mut alloc.extra, machine))
693693
}
694694

695+
/// Check whether an allocation is live. This is faster than calling
696+
/// [`InterpCx::get_alloc_info`] if all you need to check is whether the kind is
697+
/// [`AllocKind::Dead`] because it doesn't have to look up the type and layout of statics.
698+
pub fn is_alloc_live(&self, id: AllocId) -> bool {
699+
self.tcx.try_get_global_alloc(id).is_some()
700+
|| self.memory.alloc_map.contains_key_ref(&id)
701+
|| self.memory.extra_fn_ptr_map.contains_key(&id)
702+
}
703+
695704
/// Obtain the size and alignment of an allocation, even if that allocation has
696705
/// been deallocated.
697706
pub fn get_alloc_info(&self, id: AllocId) -> (Size, Align, AllocKind) {

‎compiler/rustc_middle/src/mir/interpret/mod.rs

-7
Original file line numberDiff line numberDiff line change
@@ -525,13 +525,6 @@ impl<'tcx> TyCtxt<'tcx> {
525525
self.alloc_map.lock().reserve()
526526
}
527527

528-
/// Miri's provenance GC needs to see all live allocations. The interpreter manages most
529-
/// allocations but some are managed by [`TyCtxt`] and without this method the interpreter
530-
/// doesn't know their [`AllocId`]s are in use.
531-
pub fn iter_allocs<F: FnMut(AllocId)>(self, func: F) {
532-
self.alloc_map.lock().alloc_map.keys().copied().for_each(func)
533-
}
534-
535528
/// Reserves a new ID *if* this allocation has not been dedup-reserved before.
536529
/// Should only be used for "symbolic" allocations (function pointers, vtables, statics), we
537530
/// don't want to dedup IDs for "real" memory!

‎src/ci/docker/host-x86_64/x86_64-gnu-tools/checktools.sh

+10-1
Original file line numberDiff line numberDiff line change
@@ -25,7 +25,16 @@ cat /tmp/toolstate/toolstates.json
2525
python3 "$X_PY" test --stage 2 check-tools
2626
python3 "$X_PY" test --stage 2 src/tools/clippy
2727
python3 "$X_PY" test --stage 2 src/tools/rustfmt
28-
python3 "$X_PY" test --stage 2 src/tools/miri
28+
29+
# Testing Miri is a bit more complicated.
30+
# We set the GC interval to the shortest possible value (0 would be off) to increase the chance
31+
# that bugs which only surface when the GC runs at a specific time are more likely to cause CI to fail.
32+
# This significantly increases the runtime of our test suite, or we'd do this in PR CI too.
33+
if [[ -z "${PR_CI_JOB:-}" ]]; then
34+
MIRIFLAGS=-Zmiri-provenance-gc=1 python3 "$X_PY" test --stage 2 src/tools/miri
35+
else
36+
python3 "$X_PY" test --stage 2 src/tools/miri
37+
fi
2938
# We natively run this script on x86_64-unknown-linux-gnu and x86_64-pc-windows-msvc.
3039
# Also cover some other targets via cross-testing, in particular all tier 1 targets.
3140
export BOOTSTRAP_SKIP_TARGET_SANITY=1 # we don't need `cc` for these targets

‎src/tools/miri/.github/workflows/ci.yml

+1-1
Original file line numberDiff line numberDiff line change
@@ -37,7 +37,7 @@ jobs:
3737

3838
- name: Set the tag GC interval to 1 on linux
3939
if: runner.os == 'Linux'
40-
run: echo "MIRIFLAGS=-Zmiri-tag-gc=1" >> $GITHUB_ENV
40+
run: echo "MIRIFLAGS=-Zmiri-provenance-gc=1" >> $GITHUB_ENV
4141

4242
# Cache the global cargo directory, but NOT the local `target` directory which
4343
# we cannot reuse anyway when the nightly changes (and it grows quite large

‎src/tools/miri/README.md

+4-4
Original file line numberDiff line numberDiff line change
@@ -411,10 +411,10 @@ to Miri failing to detect cases of undefined behavior in a program.
411411
without an explicit value), `none` means it never recurses, `scalar` means it only recurses for
412412
types where we would also emit `noalias` annotations in the generated LLVM IR (types passed as
413413
individual scalars or pairs of scalars). Setting this to `none` is **unsound**.
414-
* `-Zmiri-tag-gc=<blocks>` configures how often the pointer tag garbage collector runs. The default
415-
is to search for and remove unreachable tags once every `10000` basic blocks. Setting this to
416-
`0` disables the garbage collector, which causes some programs to have explosive memory usage
417-
and/or super-linear runtime.
414+
* `-Zmiri-provenance-gc=<blocks>` configures how often the pointer provenance garbage collector runs.
415+
The default is to search for and remove unreachable provenance once every `10000` basic blocks. Setting
416+
this to `0` disables the garbage collector, which causes some programs to have explosive memory
417+
usage and/or super-linear runtime.
418418
* `-Zmiri-track-alloc-id=<id1>,<id2>,...` shows a backtrace when the given allocations are
419419
being allocated or freed. This helps in debugging memory leaks and
420420
use after free bugs. Specifying this argument multiple times does not overwrite the previous

‎src/tools/miri/src/bin/miri.rs

+2-2
Original file line numberDiff line numberDiff line change
@@ -531,10 +531,10 @@ fn main() {
531531
Err(err) => show_error!("-Zmiri-report-progress requires a `u32`: {}", err),
532532
};
533533
miri_config.report_progress = Some(interval);
534-
} else if let Some(param) = arg.strip_prefix("-Zmiri-tag-gc=") {
534+
} else if let Some(param) = arg.strip_prefix("-Zmiri-provenance-gc=") {
535535
let interval = match param.parse::<u32>() {
536536
Ok(i) => i,
537-
Err(err) => show_error!("-Zmiri-tag-gc requires a `u32`: {}", err),
537+
Err(err) => show_error!("-Zmiri-provenance-gc requires a `u32`: {}", err),
538538
};
539539
miri_config.gc_interval = interval;
540540
} else if let Some(param) = arg.strip_prefix("-Zmiri-measureme=") {

‎src/tools/miri/src/borrow_tracker/mod.rs

+13-9
Original file line numberDiff line numberDiff line change
@@ -75,8 +75,8 @@ pub struct FrameState {
7575
protected_tags: SmallVec<[(AllocId, BorTag); 2]>,
7676
}
7777

78-
impl VisitTags for FrameState {
79-
fn visit_tags(&self, _visit: &mut dyn FnMut(BorTag)) {
78+
impl VisitProvenance for FrameState {
79+
fn visit_provenance(&self, _visit: &mut VisitWith<'_>) {
8080
// `protected_tags` are already recorded by `GlobalStateInner`.
8181
}
8282
}
@@ -110,10 +110,10 @@ pub struct GlobalStateInner {
110110
unique_is_unique: bool,
111111
}
112112

113-
impl VisitTags for GlobalStateInner {
114-
fn visit_tags(&self, visit: &mut dyn FnMut(BorTag)) {
113+
impl VisitProvenance for GlobalStateInner {
114+
fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
115115
for &tag in self.protected_tags.keys() {
116-
visit(tag);
116+
visit(None, Some(tag));
117117
}
118118
// The only other candidate is base_ptr_tags, and that does not need visiting since we don't ever
119119
// GC the bottommost/root tag.
@@ -236,6 +236,10 @@ impl GlobalStateInner {
236236
tag
237237
})
238238
}
239+
240+
pub fn remove_unreachable_allocs(&mut self, allocs: &LiveAllocs<'_, '_, '_>) {
241+
self.base_ptr_tags.retain(|id, _| allocs.is_live(*id));
242+
}
239243
}
240244

241245
/// Which borrow tracking method to use
@@ -503,11 +507,11 @@ impl AllocState {
503507
}
504508
}
505509

506-
impl VisitTags for AllocState {
507-
fn visit_tags(&self, visit: &mut dyn FnMut(BorTag)) {
510+
impl VisitProvenance for AllocState {
511+
fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
508512
match self {
509-
AllocState::StackedBorrows(sb) => sb.visit_tags(visit),
510-
AllocState::TreeBorrows(tb) => tb.visit_tags(visit),
513+
AllocState::StackedBorrows(sb) => sb.visit_provenance(visit),
514+
AllocState::TreeBorrows(tb) => tb.visit_provenance(visit),
511515
}
512516
}
513517
}

‎src/tools/miri/src/borrow_tracker/stacked_borrows/mod.rs

+3-3
Original file line numberDiff line numberDiff line change
@@ -462,10 +462,10 @@ impl Stacks {
462462
}
463463
}
464464

465-
impl VisitTags for Stacks {
466-
fn visit_tags(&self, visit: &mut dyn FnMut(BorTag)) {
465+
impl VisitProvenance for Stacks {
466+
fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
467467
for tag in self.exposed_tags.iter().copied() {
468-
visit(tag);
468+
visit(None, Some(tag));
469469
}
470470
}
471471
}

‎src/tools/miri/src/borrow_tracker/tree_borrows/diagnostics.rs

+1-1
Original file line numberDiff line numberDiff line change
@@ -200,7 +200,7 @@ impl<'tcx> Tree {
200200
/// Climb the tree to get the tag of a distant ancestor.
201201
/// Allows operations on tags that are unreachable by the program
202202
/// but still exist in the tree. Not guaranteed to perform consistently
203-
/// if `tag-gc=1`.
203+
/// if `provenance-gc=1`.
204204
fn nth_parent(&self, tag: BorTag, nth_parent: u8) -> Option<BorTag> {
205205
let mut idx = self.tag_mapping.get(&tag).unwrap();
206206
for _ in 0..nth_parent {

‎src/tools/miri/src/borrow_tracker/tree_borrows/tree.rs

+3-3
Original file line numberDiff line numberDiff line change
@@ -742,11 +742,11 @@ impl Tree {
742742
}
743743
}
744744

745-
impl VisitTags for Tree {
746-
fn visit_tags(&self, visit: &mut dyn FnMut(BorTag)) {
745+
impl VisitProvenance for Tree {
746+
fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
747747
// To ensure that the root never gets removed, we visit it
748748
// (the `root` node of `Tree` is not an `Option<_>`)
749-
visit(self.nodes.get(self.root).unwrap().tag)
749+
visit(None, Some(self.nodes.get(self.root).unwrap().tag))
750750
}
751751
}
752752

‎src/tools/miri/src/concurrency/data_race.rs

+5-5
Original file line numberDiff line numberDiff line change
@@ -790,9 +790,9 @@ pub struct VClockAlloc {
790790
alloc_ranges: RefCell<RangeMap<MemoryCellClocks>>,
791791
}
792792

793-
impl VisitTags for VClockAlloc {
794-
fn visit_tags(&self, _visit: &mut dyn FnMut(BorTag)) {
795-
// No tags here.
793+
impl VisitProvenance for VClockAlloc {
794+
fn visit_provenance(&self, _visit: &mut VisitWith<'_>) {
795+
// No tags or allocIds here.
796796
}
797797
}
798798

@@ -1404,8 +1404,8 @@ pub struct GlobalState {
14041404
pub track_outdated_loads: bool,
14051405
}
14061406

1407-
impl VisitTags for GlobalState {
1408-
fn visit_tags(&self, _visit: &mut dyn FnMut(BorTag)) {
1407+
impl VisitProvenance for GlobalState {
1408+
fn visit_provenance(&self, _visit: &mut VisitWith<'_>) {
14091409
// We don't have any tags.
14101410
}
14111411
}

‎src/tools/miri/src/concurrency/init_once.rs

+3-3
Original file line numberDiff line numberDiff line change
@@ -45,10 +45,10 @@ pub(super) struct InitOnce<'mir, 'tcx> {
4545
data_race: VClock,
4646
}
4747

48-
impl<'mir, 'tcx> VisitTags for InitOnce<'mir, 'tcx> {
49-
fn visit_tags(&self, visit: &mut dyn FnMut(BorTag)) {
48+
impl<'mir, 'tcx> VisitProvenance for InitOnce<'mir, 'tcx> {
49+
fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
5050
for waiter in self.waiters.iter() {
51-
waiter.callback.visit_tags(visit);
51+
waiter.callback.visit_provenance(visit);
5252
}
5353
}
5454
}

‎src/tools/miri/src/concurrency/sync.rs

+3-3
Original file line numberDiff line numberDiff line change
@@ -181,10 +181,10 @@ pub(crate) struct SynchronizationState<'mir, 'tcx> {
181181
pub(super) init_onces: IndexVec<InitOnceId, InitOnce<'mir, 'tcx>>,
182182
}
183183

184-
impl<'mir, 'tcx> VisitTags for SynchronizationState<'mir, 'tcx> {
185-
fn visit_tags(&self, visit: &mut dyn FnMut(BorTag)) {
184+
impl<'mir, 'tcx> VisitProvenance for SynchronizationState<'mir, 'tcx> {
185+
fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
186186
for init_once in self.init_onces.iter() {
187-
init_once.visit_tags(visit);
187+
init_once.visit_provenance(visit);
188188
}
189189
}
190190
}

‎src/tools/miri/src/concurrency/thread.rs

+19-19
Original file line numberDiff line numberDiff line change
@@ -43,7 +43,7 @@ pub enum TlsAllocAction {
4343
}
4444

4545
/// Trait for callbacks that can be executed when some event happens, such as after a timeout.
46-
pub trait MachineCallback<'mir, 'tcx>: VisitTags {
46+
pub trait MachineCallback<'mir, 'tcx>: VisitProvenance {
4747
fn call(&self, ecx: &mut InterpCx<'mir, 'tcx, MiriMachine<'mir, 'tcx>>) -> InterpResult<'tcx>;
4848
}
4949

@@ -228,8 +228,8 @@ impl<'mir, 'tcx> Thread<'mir, 'tcx> {
228228
}
229229
}
230230

231-
impl VisitTags for Thread<'_, '_> {
232-
fn visit_tags(&self, visit: &mut dyn FnMut(BorTag)) {
231+
impl VisitProvenance for Thread<'_, '_> {
232+
fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
233233
let Thread {
234234
panic_payloads: panic_payload,
235235
last_error,
@@ -242,17 +242,17 @@ impl VisitTags for Thread<'_, '_> {
242242
} = self;
243243

244244
for payload in panic_payload {
245-
payload.visit_tags(visit);
245+
payload.visit_provenance(visit);
246246
}
247-
last_error.visit_tags(visit);
247+
last_error.visit_provenance(visit);
248248
for frame in stack {
249-
frame.visit_tags(visit)
249+
frame.visit_provenance(visit)
250250
}
251251
}
252252
}
253253

254-
impl VisitTags for Frame<'_, '_, Provenance, FrameExtra<'_>> {
255-
fn visit_tags(&self, visit: &mut dyn FnMut(BorTag)) {
254+
impl VisitProvenance for Frame<'_, '_, Provenance, FrameExtra<'_>> {
255+
fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
256256
let Frame {
257257
return_place,
258258
locals,
@@ -266,22 +266,22 @@ impl VisitTags for Frame<'_, '_, Provenance, FrameExtra<'_>> {
266266
} = self;
267267

268268
// Return place.
269-
return_place.visit_tags(visit);
269+
return_place.visit_provenance(visit);
270270
// Locals.
271271
for local in locals.iter() {
272272
match local.as_mplace_or_imm() {
273273
None => {}
274274
Some(Either::Left((ptr, meta))) => {
275-
ptr.visit_tags(visit);
276-
meta.visit_tags(visit);
275+
ptr.visit_provenance(visit);
276+
meta.visit_provenance(visit);
277277
}
278278
Some(Either::Right(imm)) => {
279-
imm.visit_tags(visit);
279+
imm.visit_provenance(visit);
280280
}
281281
}
282282
}
283283

284-
extra.visit_tags(visit);
284+
extra.visit_provenance(visit);
285285
}
286286
}
287287

@@ -341,8 +341,8 @@ pub struct ThreadManager<'mir, 'tcx> {
341341
timeout_callbacks: FxHashMap<ThreadId, TimeoutCallbackInfo<'mir, 'tcx>>,
342342
}
343343

344-
impl VisitTags for ThreadManager<'_, '_> {
345-
fn visit_tags(&self, visit: &mut dyn FnMut(BorTag)) {
344+
impl VisitProvenance for ThreadManager<'_, '_> {
345+
fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
346346
let ThreadManager {
347347
threads,
348348
thread_local_alloc_ids,
@@ -353,15 +353,15 @@ impl VisitTags for ThreadManager<'_, '_> {
353353
} = self;
354354

355355
for thread in threads {
356-
thread.visit_tags(visit);
356+
thread.visit_provenance(visit);
357357
}
358358
for ptr in thread_local_alloc_ids.borrow().values() {
359-
ptr.visit_tags(visit);
359+
ptr.visit_provenance(visit);
360360
}
361361
for callback in timeout_callbacks.values() {
362-
callback.callback.visit_tags(visit);
362+
callback.callback.visit_provenance(visit);
363363
}
364-
sync.visit_tags(visit);
364+
sync.visit_provenance(visit);
365365
}
366366
}
367367

‎src/tools/miri/src/concurrency/weak_memory.rs

+3-3
Original file line numberDiff line numberDiff line change
@@ -108,15 +108,15 @@ pub struct StoreBufferAlloc {
108108
store_buffers: RefCell<RangeObjectMap<StoreBuffer>>,
109109
}
110110

111-
impl VisitTags for StoreBufferAlloc {
112-
fn visit_tags(&self, visit: &mut dyn FnMut(BorTag)) {
111+
impl VisitProvenance for StoreBufferAlloc {
112+
fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
113113
let Self { store_buffers } = self;
114114
for val in store_buffers
115115
.borrow()
116116
.iter()
117117
.flat_map(|buf| buf.buffer.iter().map(|element| &element.val))
118118
{
119-
val.visit_tags(visit);
119+
val.visit_provenance(visit);
120120
}
121121
}
122122
}

0 commit comments

Comments
 (0)