miri/
provenance_gc.rs

1use either::Either;
2use rustc_data_structures::fx::FxHashSet;
3
4use crate::*;
5
6pub type VisitWith<'a> = dyn FnMut(Option<AllocId>, Option<BorTag>) + 'a;
7
8pub trait VisitProvenance {
9    fn visit_provenance(&self, visit: &mut VisitWith<'_>);
10}
11
12// Trivial impls for types that do not contain any provenance
13macro_rules! no_provenance {
14    ($($ty:ident)+) => {
15        $(
16            impl VisitProvenance for $ty {
17                fn visit_provenance(&self, _visit: &mut VisitWith<'_>) {}
18            }
19        )+
20    }
21}
22no_provenance!(i8 i16 i32 i64 isize u8 u16 u32 u64 usize ThreadId);
23
24impl<T: VisitProvenance> VisitProvenance for Option<T> {
25    fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
26        if let Some(x) = self {
27            x.visit_provenance(visit);
28        }
29    }
30}
31
32impl<A, B> VisitProvenance for (A, B)
33where
34    A: VisitProvenance,
35    B: VisitProvenance,
36{
37    fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
38        self.0.visit_provenance(visit);
39        self.1.visit_provenance(visit);
40    }
41}
42
43impl<T: VisitProvenance> VisitProvenance for std::cell::RefCell<T> {
44    fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
45        self.borrow().visit_provenance(visit)
46    }
47}
48
49impl VisitProvenance for BorTag {
50    fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
51        visit(None, Some(*self))
52    }
53}
54
55impl VisitProvenance for AllocId {
56    fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
57        visit(Some(*self), None)
58    }
59}
60
61impl VisitProvenance for Provenance {
62    fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
63        if let Provenance::Concrete { alloc_id, tag, .. } = self {
64            visit(Some(*alloc_id), Some(*tag));
65        }
66    }
67}
68
69impl VisitProvenance for StrictPointer {
70    fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
71        let (prov, _offset) = self.into_parts();
72        prov.visit_provenance(visit);
73    }
74}
75
76impl VisitProvenance for Pointer {
77    fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
78        let (prov, _offset) = self.into_parts();
79        prov.visit_provenance(visit);
80    }
81}
82
83impl VisitProvenance for Scalar {
84    fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
85        match self {
86            Scalar::Ptr(ptr, _) => ptr.visit_provenance(visit),
87            Scalar::Int(_) => (),
88        }
89    }
90}
91
92impl VisitProvenance for IoError {
93    fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
94        use crate::shims::io_error::IoError::*;
95        match self {
96            LibcError(_name) => (),
97            WindowsError(_name) => (),
98            HostError(_io_error) => (),
99            Raw(scalar) => scalar.visit_provenance(visit),
100        }
101    }
102}
103
104impl VisitProvenance for Immediate<Provenance> {
105    fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
106        match self {
107            Immediate::Scalar(s) => {
108                s.visit_provenance(visit);
109            }
110            Immediate::ScalarPair(s1, s2) => {
111                s1.visit_provenance(visit);
112                s2.visit_provenance(visit);
113            }
114            Immediate::Uninit => {}
115        }
116    }
117}
118
119impl VisitProvenance for MemPlaceMeta<Provenance> {
120    fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
121        match self {
122            MemPlaceMeta::Meta(m) => m.visit_provenance(visit),
123            MemPlaceMeta::None => {}
124        }
125    }
126}
127
128impl VisitProvenance for ImmTy<'_> {
129    fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
130        (**self).visit_provenance(visit)
131    }
132}
133
134impl VisitProvenance for MPlaceTy<'_> {
135    fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
136        self.ptr().visit_provenance(visit);
137        self.meta().visit_provenance(visit);
138    }
139}
140
141impl VisitProvenance for PlaceTy<'_> {
142    fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
143        match self.as_mplace_or_local() {
144            Either::Left(mplace) => mplace.visit_provenance(visit),
145            Either::Right(_) => (),
146        }
147    }
148}
149
150impl VisitProvenance for OpTy<'_> {
151    fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
152        match self.as_mplace_or_imm() {
153            Either::Left(mplace) => mplace.visit_provenance(visit),
154            Either::Right(imm) => imm.visit_provenance(visit),
155        }
156    }
157}
158
159impl VisitProvenance for Allocation<Provenance, AllocExtra<'_>, MiriAllocBytes> {
160    fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
161        for prov in self.provenance().provenances() {
162            prov.visit_provenance(visit);
163        }
164
165        self.extra.visit_provenance(visit);
166    }
167}
168
169impl VisitProvenance for crate::MiriInterpCx<'_> {
170    fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
171        // Visit the contents of the allocations and the IDs themselves, to account for all
172        // live allocation IDs and all provenance in the allocation bytes, even if they are leaked.
173        // We do *not* visit all the `AllocId` of the live allocations; we tried that and adding
174        // them all to the live set is too expensive. Instead we later do liveness check by
175        // checking both "is this alloc id live" and "is it mentioned anywhere else in
176        // the interpreter state".
177        self.memory.alloc_map().iter(|it| {
178            for (_id, (_kind, alloc)) in it {
179                alloc.visit_provenance(visit);
180            }
181        });
182        // And all the other machine values.
183        self.machine.visit_provenance(visit);
184    }
185}
186
187pub struct LiveAllocs<'a, 'tcx> {
188    collected: FxHashSet<AllocId>,
189    ecx: &'a MiriInterpCx<'tcx>,
190}
191
192impl LiveAllocs<'_, '_> {
193    pub fn is_live(&self, id: AllocId) -> bool {
194        self.collected.contains(&id) || self.ecx.is_alloc_live(id)
195    }
196}
197
198fn remove_unreachable_tags<'tcx>(ecx: &mut MiriInterpCx<'tcx>, tags: FxHashSet<BorTag>) {
199    // Avoid iterating all allocations if there's no borrow tracker anyway.
200    if ecx.machine.borrow_tracker.is_some() {
201        ecx.memory.alloc_map().iter(|it| {
202            for (_id, (_kind, alloc)) in it {
203                alloc.extra.borrow_tracker.as_ref().unwrap().remove_unreachable_tags(&tags);
204            }
205        });
206    }
207}
208
209fn remove_unreachable_allocs<'tcx>(ecx: &mut MiriInterpCx<'tcx>, allocs: FxHashSet<AllocId>) {
210    let allocs = LiveAllocs { ecx, collected: allocs };
211    ecx.machine.allocation_spans.borrow_mut().retain(|id, _| allocs.is_live(*id));
212    ecx.machine.symbolic_alignment.borrow_mut().retain(|id, _| allocs.is_live(*id));
213    ecx.machine.alloc_addresses.borrow_mut().remove_unreachable_allocs(&allocs);
214    if let Some(borrow_tracker) = &ecx.machine.borrow_tracker {
215        borrow_tracker.borrow_mut().remove_unreachable_allocs(&allocs);
216    }
217    // Clean up core (non-Miri-specific) state.
218    ecx.remove_unreachable_allocs(&allocs.collected);
219}
220
221impl<'tcx> EvalContextExt<'tcx> for crate::MiriInterpCx<'tcx> {}
222pub trait EvalContextExt<'tcx>: MiriInterpCxExt<'tcx> {
223    fn run_provenance_gc(&mut self) {
224        let this = self.eval_context_mut();
225
226        // We collect all tags and AllocId from every part of the interpreter.
227        let mut tags = FxHashSet::default();
228        let mut alloc_ids = FxHashSet::default();
229        this.visit_provenance(&mut |id, tag| {
230            if let Some(id) = id {
231                alloc_ids.insert(id);
232            }
233            if let Some(tag) = tag {
234                tags.insert(tag);
235            }
236        });
237
238        // Based on this, clean up the interpreter state.
239        remove_unreachable_tags(this, tags);
240        remove_unreachable_allocs(this, alloc_ids);
241    }
242}
miri/provenance_gc.rs

miri/
provenance_gc.rs
