miri/
provenance_gc.rs

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

miri/
provenance_gc.rs
