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

miri/
provenance_gc.rs
