miri/
provenance_gc.rs

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

miri/
provenance_gc.rs
