1use std::cell::RefCell;
2use std::fmt;
3use std::num::NonZero;
4
5use rustc_abi::Size;
6use rustc_data_structures::fx::{FxHashMap, FxHashSet};
7use rustc_middle::mir::RetagKind;
8use smallvec::SmallVec;
9
10use crate::*;
11pub mod stacked_borrows;
12pub mod tree_borrows;
13
14#[derive(Copy, Clone, Hash, PartialEq, Eq, PartialOrd, Ord)]
16pub struct BorTag(NonZero<u64>);
17
18impl BorTag {
19 pub fn new(i: u64) -> Option<Self> {
20 NonZero::new(i).map(BorTag)
21 }
22
23 pub fn get(&self) -> u64 {
24 self.0.get()
25 }
26
27 pub fn inner(&self) -> NonZero<u64> {
28 self.0
29 }
30
31 pub fn succ(self) -> Option<Self> {
32 self.0.checked_add(1).map(Self)
33 }
34
35 pub fn one() -> Self {
37 Self::new(1).unwrap()
38 }
39}
40
41impl std::default::Default for BorTag {
42 fn default() -> Self {
44 Self::one()
45 }
46}
47
48impl fmt::Debug for BorTag {
49 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
50 write!(f, "<{}>", self.0)
51 }
52}
53
54#[derive(Debug)]
56pub struct FrameState {
57 protected_tags: SmallVec<[(AllocId, BorTag); 2]>,
69}
70
71impl VisitProvenance for FrameState {
72 fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
73 for (id, tag) in &self.protected_tags {
80 visit(Some(*id), Some(*tag));
81 }
82 }
83}
84
85#[derive(Debug)]
87pub struct GlobalStateInner {
88 borrow_tracker_method: BorrowTrackerMethod,
90 next_ptr_tag: BorTag,
92 root_ptr_tags: FxHashMap<AllocId, BorTag>,
96 protected_tags: FxHashMap<BorTag, ProtectorKind>,
101 tracked_pointer_tags: FxHashSet<BorTag>,
103 retag_fields: RetagFields,
105}
106
107impl VisitProvenance for GlobalStateInner {
108 fn visit_provenance(&self, _visit: &mut VisitWith<'_>) {
109 }
113}
114
115pub type GlobalState = RefCell<GlobalStateInner>;
117
118impl fmt::Display for AccessKind {
119 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
120 match self {
121 AccessKind::Read => write!(f, "read access"),
122 AccessKind::Write => write!(f, "write access"),
123 }
124 }
125}
126
127#[derive(Copy, Clone, Debug)]
129pub enum RetagFields {
130 No,
132 Yes,
134 OnlyScalar,
137}
138
139#[derive(Copy, Clone, Debug, PartialEq, Eq)]
141pub enum ProtectorKind {
142 WeakProtector,
149
150 StrongProtector,
157}
158
159impl GlobalStateInner {
161 pub fn new(
162 borrow_tracker_method: BorrowTrackerMethod,
163 tracked_pointer_tags: FxHashSet<BorTag>,
164 retag_fields: RetagFields,
165 ) -> Self {
166 GlobalStateInner {
167 borrow_tracker_method,
168 next_ptr_tag: BorTag::one(),
169 root_ptr_tags: FxHashMap::default(),
170 protected_tags: FxHashMap::default(),
171 tracked_pointer_tags,
172 retag_fields,
173 }
174 }
175
176 fn new_ptr(&mut self) -> BorTag {
178 let id = self.next_ptr_tag;
179 self.next_ptr_tag = id.succ().unwrap();
180 id
181 }
182
183 pub fn new_frame(&mut self) -> FrameState {
184 FrameState { protected_tags: SmallVec::new() }
185 }
186
187 fn end_call(&mut self, frame: &machine::FrameExtra<'_>) {
188 for (_, tag) in &frame
189 .borrow_tracker
190 .as_ref()
191 .expect("we should have borrow tracking data")
192 .protected_tags
193 {
194 self.protected_tags.remove(tag);
195 }
196 }
197
198 pub fn root_ptr_tag(&mut self, id: AllocId, machine: &MiriMachine<'_>) -> BorTag {
199 self.root_ptr_tags.get(&id).copied().unwrap_or_else(|| {
200 let tag = self.new_ptr();
201 if self.tracked_pointer_tags.contains(&tag) {
202 machine.emit_diagnostic(NonHaltingDiagnostic::CreatedPointerTag(
203 tag.inner(),
204 None,
205 None,
206 ));
207 }
208 trace!("New allocation {:?} has rpot tag {:?}", id, tag);
209 self.root_ptr_tags.try_insert(id, tag).unwrap();
210 tag
211 })
212 }
213
214 pub fn remove_unreachable_allocs(&mut self, allocs: &LiveAllocs<'_, '_>) {
215 self.root_ptr_tags.retain(|id, _| allocs.is_live(*id));
216 }
217
218 pub fn borrow_tracker_method(&self) -> BorrowTrackerMethod {
219 self.borrow_tracker_method
220 }
221}
222
223#[derive(Debug, Copy, Clone, PartialEq, Eq)]
225pub enum BorrowTrackerMethod {
226 StackedBorrows,
228 TreeBorrows,
230}
231
232impl BorrowTrackerMethod {
233 pub fn instantiate_global_state(self, config: &MiriConfig) -> GlobalState {
234 RefCell::new(GlobalStateInner::new(
235 self,
236 config.tracked_pointer_tags.clone(),
237 config.retag_fields,
238 ))
239 }
240}
241
242impl GlobalStateInner {
243 pub fn new_allocation(
244 &mut self,
245 id: AllocId,
246 alloc_size: Size,
247 kind: MemoryKind,
248 machine: &MiriMachine<'_>,
249 ) -> AllocState {
250 match self.borrow_tracker_method {
251 BorrowTrackerMethod::StackedBorrows =>
252 AllocState::StackedBorrows(Box::new(RefCell::new(Stacks::new_allocation(
253 id, alloc_size, self, kind, machine,
254 )))),
255 BorrowTrackerMethod::TreeBorrows =>
256 AllocState::TreeBorrows(Box::new(RefCell::new(Tree::new_allocation(
257 id, alloc_size, self, kind, machine,
258 )))),
259 }
260 }
261}
262
263impl<'tcx> EvalContextExt<'tcx> for crate::MiriInterpCx<'tcx> {}
264pub trait EvalContextExt<'tcx>: crate::MiriInterpCxExt<'tcx> {
265 fn retag_ptr_value(
266 &mut self,
267 kind: RetagKind,
268 val: &ImmTy<'tcx>,
269 ) -> InterpResult<'tcx, ImmTy<'tcx>> {
270 let this = self.eval_context_mut();
271 let method = this.machine.borrow_tracker.as_ref().unwrap().borrow().borrow_tracker_method;
272 match method {
273 BorrowTrackerMethod::StackedBorrows => this.sb_retag_ptr_value(kind, val),
274 BorrowTrackerMethod::TreeBorrows => this.tb_retag_ptr_value(kind, val),
275 }
276 }
277
278 fn retag_place_contents(
279 &mut self,
280 kind: RetagKind,
281 place: &PlaceTy<'tcx>,
282 ) -> InterpResult<'tcx> {
283 let this = self.eval_context_mut();
284 let method = this.machine.borrow_tracker.as_ref().unwrap().borrow().borrow_tracker_method;
285 match method {
286 BorrowTrackerMethod::StackedBorrows => this.sb_retag_place_contents(kind, place),
287 BorrowTrackerMethod::TreeBorrows => this.tb_retag_place_contents(kind, place),
288 }
289 }
290
291 fn protect_place(&mut self, place: &MPlaceTy<'tcx>) -> InterpResult<'tcx, MPlaceTy<'tcx>> {
292 let this = self.eval_context_mut();
293 let method = this.machine.borrow_tracker.as_ref().unwrap().borrow().borrow_tracker_method;
294 match method {
295 BorrowTrackerMethod::StackedBorrows => this.sb_protect_place(place),
296 BorrowTrackerMethod::TreeBorrows => this.tb_protect_place(place),
297 }
298 }
299
300 fn expose_tag(&self, alloc_id: AllocId, tag: BorTag) -> InterpResult<'tcx> {
301 let this = self.eval_context_ref();
302 let method = this.machine.borrow_tracker.as_ref().unwrap().borrow().borrow_tracker_method;
303 match method {
304 BorrowTrackerMethod::StackedBorrows => this.sb_expose_tag(alloc_id, tag),
305 BorrowTrackerMethod::TreeBorrows => this.tb_expose_tag(alloc_id, tag),
306 }
307 }
308
309 fn give_pointer_debug_name(
310 &mut self,
311 ptr: Pointer,
312 nth_parent: u8,
313 name: &str,
314 ) -> InterpResult<'tcx> {
315 let this = self.eval_context_mut();
316 let method = this.machine.borrow_tracker.as_ref().unwrap().borrow().borrow_tracker_method;
317 match method {
318 BorrowTrackerMethod::StackedBorrows => {
319 this.tcx.tcx.dcx().warn("Stacked Borrows does not support named pointers; `miri_pointer_name` is a no-op");
320 interp_ok(())
321 }
322 BorrowTrackerMethod::TreeBorrows =>
323 this.tb_give_pointer_debug_name(ptr, nth_parent, name),
324 }
325 }
326
327 fn print_borrow_state(&mut self, alloc_id: AllocId, show_unnamed: bool) -> InterpResult<'tcx> {
328 let this = self.eval_context_mut();
329 let Some(borrow_tracker) = &this.machine.borrow_tracker else {
330 eprintln!("attempted to print borrow state, but no borrow state is being tracked");
331 return interp_ok(());
332 };
333 let method = borrow_tracker.borrow().borrow_tracker_method;
334 match method {
335 BorrowTrackerMethod::StackedBorrows => this.print_stacks(alloc_id),
336 BorrowTrackerMethod::TreeBorrows => this.print_tree(alloc_id, show_unnamed),
337 }
338 }
339
340 fn on_stack_pop(
341 &self,
342 frame: &Frame<'tcx, Provenance, FrameExtra<'tcx>>,
343 ) -> InterpResult<'tcx> {
344 let this = self.eval_context_ref();
345 let borrow_tracker = this.machine.borrow_tracker.as_ref().unwrap();
346 for (alloc_id, tag) in &frame
349 .extra
350 .borrow_tracker
351 .as_ref()
352 .expect("we should have borrow tracking data")
353 .protected_tags
354 {
355 let kind = this.get_alloc_info(*alloc_id).kind;
362 if matches!(kind, AllocKind::LiveData) {
363 let alloc_extra = this.get_alloc_extra(*alloc_id)?; let alloc_borrow_tracker = &alloc_extra.borrow_tracker.as_ref().unwrap();
365 alloc_borrow_tracker.release_protector(
366 &this.machine,
367 borrow_tracker,
368 *tag,
369 *alloc_id,
370 )?;
371 }
372 }
373 borrow_tracker.borrow_mut().end_call(&frame.extra);
374 interp_ok(())
375 }
376}
377
378#[derive(Debug, Clone)]
380pub enum AllocState {
381 StackedBorrows(Box<RefCell<stacked_borrows::AllocState>>),
383 TreeBorrows(Box<RefCell<tree_borrows::AllocState>>),
385}
386
387impl machine::AllocExtra<'_> {
388 #[track_caller]
389 pub fn borrow_tracker_sb(&self) -> &RefCell<stacked_borrows::AllocState> {
390 match self.borrow_tracker {
391 Some(AllocState::StackedBorrows(ref sb)) => sb,
392 _ => panic!("expected Stacked Borrows borrow tracking, got something else"),
393 }
394 }
395
396 #[track_caller]
397 pub fn borrow_tracker_sb_mut(&mut self) -> &mut RefCell<stacked_borrows::AllocState> {
398 match self.borrow_tracker {
399 Some(AllocState::StackedBorrows(ref mut sb)) => sb,
400 _ => panic!("expected Stacked Borrows borrow tracking, got something else"),
401 }
402 }
403
404 #[track_caller]
405 pub fn borrow_tracker_tb(&self) -> &RefCell<tree_borrows::AllocState> {
406 match self.borrow_tracker {
407 Some(AllocState::TreeBorrows(ref tb)) => tb,
408 _ => panic!("expected Tree Borrows borrow tracking, got something else"),
409 }
410 }
411}
412
413impl AllocState {
414 pub fn before_memory_read<'tcx>(
415 &self,
416 alloc_id: AllocId,
417 prov_extra: ProvenanceExtra,
418 range: AllocRange,
419 machine: &MiriMachine<'tcx>,
420 ) -> InterpResult<'tcx> {
421 match self {
422 AllocState::StackedBorrows(sb) =>
423 sb.borrow_mut().before_memory_read(alloc_id, prov_extra, range, machine),
424 AllocState::TreeBorrows(tb) =>
425 tb.borrow_mut().before_memory_access(
426 AccessKind::Read,
427 alloc_id,
428 prov_extra,
429 range,
430 machine,
431 ),
432 }
433 }
434
435 pub fn before_memory_write<'tcx>(
436 &mut self,
437 alloc_id: AllocId,
438 prov_extra: ProvenanceExtra,
439 range: AllocRange,
440 machine: &MiriMachine<'tcx>,
441 ) -> InterpResult<'tcx> {
442 match self {
443 AllocState::StackedBorrows(sb) =>
444 sb.get_mut().before_memory_write(alloc_id, prov_extra, range, machine),
445 AllocState::TreeBorrows(tb) =>
446 tb.get_mut().before_memory_access(
447 AccessKind::Write,
448 alloc_id,
449 prov_extra,
450 range,
451 machine,
452 ),
453 }
454 }
455
456 pub fn before_memory_deallocation<'tcx>(
457 &mut self,
458 alloc_id: AllocId,
459 prov_extra: ProvenanceExtra,
460 size: Size,
461 machine: &MiriMachine<'tcx>,
462 ) -> InterpResult<'tcx> {
463 match self {
464 AllocState::StackedBorrows(sb) =>
465 sb.get_mut().before_memory_deallocation(alloc_id, prov_extra, size, machine),
466 AllocState::TreeBorrows(tb) =>
467 tb.get_mut().before_memory_deallocation(alloc_id, prov_extra, size, machine),
468 }
469 }
470
471 pub fn remove_unreachable_tags(&self, tags: &FxHashSet<BorTag>) {
472 match self {
473 AllocState::StackedBorrows(sb) => sb.borrow_mut().remove_unreachable_tags(tags),
474 AllocState::TreeBorrows(tb) => tb.borrow_mut().remove_unreachable_tags(tags),
475 }
476 }
477
478 pub fn release_protector<'tcx>(
480 &self,
481 machine: &MiriMachine<'tcx>,
482 global: &GlobalState,
483 tag: BorTag,
484 alloc_id: AllocId, ) -> InterpResult<'tcx> {
486 match self {
487 AllocState::StackedBorrows(_sb) => interp_ok(()),
488 AllocState::TreeBorrows(tb) =>
489 tb.borrow_mut().release_protector(machine, global, tag, alloc_id),
490 }
491 }
492}
493
494impl VisitProvenance for AllocState {
495 fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
496 match self {
497 AllocState::StackedBorrows(sb) => sb.visit_provenance(visit),
498 AllocState::TreeBorrows(tb) => tb.visit_provenance(visit),
499 }
500 }
501}