miri/borrow_tracker/tree_borrows/
mod.rs1use rustc_abi::{BackendRepr, Size};
2use rustc_middle::mir::{Mutability, RetagKind};
3use rustc_middle::ty::layout::HasTypingEnv;
4use rustc_middle::ty::{self, Ty};
5
6use self::foreign_access_skipping::IdempotentForeignAccess;
7use self::tree::LocationState;
8use crate::borrow_tracker::{GlobalState, GlobalStateInner, ProtectorKind};
9use crate::concurrency::data_race::NaReadType;
10use crate::*;
11
12pub mod diagnostics;
13mod foreign_access_skipping;
14mod perms;
15mod tree;
16mod unimap;
17
18#[cfg(test)]
19mod exhaustive;
20
21use self::perms::Permission;
22pub use self::tree::Tree;
23
24pub type AllocState = Tree;
25
26impl<'tcx> Tree {
27 pub fn new_allocation(
29 id: AllocId,
30 size: Size,
31 state: &mut GlobalStateInner,
32 _kind: MemoryKind,
33 machine: &MiriMachine<'tcx>,
34 ) -> Self {
35 let tag = state.root_ptr_tag(id, machine); let span = machine.current_span();
37 Tree::new(tag, size, span)
38 }
39
40 pub fn before_memory_access(
43 &mut self,
44 access_kind: AccessKind,
45 alloc_id: AllocId,
46 prov: ProvenanceExtra,
47 range: AllocRange,
48 machine: &MiriMachine<'tcx>,
49 ) -> InterpResult<'tcx> {
50 trace!(
51 "{} with tag {:?}: {:?}, size {}",
52 access_kind,
53 prov,
54 interpret::Pointer::new(alloc_id, range.start),
55 range.size.bytes(),
56 );
57 let tag = match prov {
60 ProvenanceExtra::Concrete(tag) => tag,
61 ProvenanceExtra::Wildcard => return interp_ok(()),
62 };
63 let global = machine.borrow_tracker.as_ref().unwrap();
64 let span = machine.current_span();
65 self.perform_access(
66 tag,
67 Some((range, access_kind, diagnostics::AccessCause::Explicit(access_kind))),
68 global,
69 alloc_id,
70 span,
71 )
72 }
73
74 pub fn before_memory_deallocation(
76 &mut self,
77 alloc_id: AllocId,
78 prov: ProvenanceExtra,
79 size: Size,
80 machine: &MiriMachine<'tcx>,
81 ) -> InterpResult<'tcx> {
82 let tag = match prov {
85 ProvenanceExtra::Concrete(tag) => tag,
86 ProvenanceExtra::Wildcard => return interp_ok(()),
87 };
88 let global = machine.borrow_tracker.as_ref().unwrap();
89 let span = machine.current_span();
90 self.dealloc(tag, alloc_range(Size::ZERO, size), global, alloc_id, span)
91 }
92
93 pub fn expose_tag(&mut self, _tag: BorTag) {
94 }
96
97 pub fn release_protector(
104 &mut self,
105 machine: &MiriMachine<'tcx>,
106 global: &GlobalState,
107 tag: BorTag,
108 alloc_id: AllocId, ) -> InterpResult<'tcx> {
110 let span = machine.current_span();
111 self.perform_access(tag, None, global, alloc_id, span)
113 }
114}
115
116#[derive(Debug, Clone, Copy)]
118pub struct NewPermission {
119 freeze_perm: Permission,
121 freeze_access: bool,
123 nonfreeze_perm: Permission,
125 nonfreeze_access: bool,
128 outside_perm: Permission,
130 protector: Option<ProtectorKind>,
133}
134
135impl<'tcx> NewPermission {
136 fn new(
140 pointee: Ty<'tcx>,
141 ref_mutability: Option<Mutability>,
142 retag_kind: RetagKind,
143 cx: &crate::MiriInterpCx<'tcx>,
144 ) -> Option<Self> {
145 let ty_is_unpin = pointee.is_unpin(*cx.tcx, cx.typing_env());
146 let ty_is_freeze = pointee.is_freeze(*cx.tcx, cx.typing_env());
147 let is_protected = retag_kind == RetagKind::FnEntry;
148
149 if matches!(ref_mutability, Some(Mutability::Mut) | None if !ty_is_unpin) {
150 return None;
153 }
154
155 let freeze_perm = match ref_mutability {
156 Some(Mutability::Not) => Permission::new_frozen(),
158 _ => Permission::new_reserved_frz(),
160 };
161 let nonfreeze_perm = match ref_mutability {
162 Some(Mutability::Not) => Permission::new_cell(),
164 _ if is_protected => Permission::new_reserved_frz(),
166 _ => Permission::new_reserved_im(),
168 };
169
170 let initial_access = |perm: &Permission| !perm.is_cell();
172
173 Some(NewPermission {
174 freeze_perm,
175 freeze_access: initial_access(&freeze_perm),
176 nonfreeze_perm,
177 nonfreeze_access: initial_access(&nonfreeze_perm),
178 outside_perm: if ty_is_freeze { freeze_perm } else { nonfreeze_perm },
179 protector: is_protected.then_some(if ref_mutability.is_some() {
180 ProtectorKind::StrongProtector
182 } else {
183 ProtectorKind::WeakProtector
185 }),
186 })
187 }
188}
189
190impl<'tcx> EvalContextPrivExt<'tcx> for crate::MiriInterpCx<'tcx> {}
194trait EvalContextPrivExt<'tcx>: crate::MiriInterpCxExt<'tcx> {
195 fn tb_reborrow(
197 &mut self,
198 place: &MPlaceTy<'tcx>, ptr_size: Size,
200 new_perm: NewPermission,
201 new_tag: BorTag,
202 ) -> InterpResult<'tcx, Option<Provenance>> {
203 let this = self.eval_context_mut();
204 this.check_ptr_access(place.ptr(), ptr_size, CheckInAllocMsg::Dereferenceable)?;
206
207 let log_creation = |this: &MiriInterpCx<'tcx>,
209 loc: Option<(AllocId, Size, ProvenanceExtra)>| -> InterpResult<'tcx> {
211 let global = this.machine.borrow_tracker.as_ref().unwrap().borrow();
212 let ty = place.layout.ty;
213 if global.tracked_pointer_tags.contains(&new_tag) {
214 let ty_is_freeze = ty.is_freeze(*this.tcx, this.typing_env());
215 let kind_str =
216 if ty_is_freeze {
217 format!("initial state {} (pointee type {ty})", new_perm.freeze_perm)
218 } else {
219 format!("initial state {}/{} outside/inside UnsafeCell (pointee type {ty})", new_perm.freeze_perm, new_perm.nonfreeze_perm)
220 };
221 this.emit_diagnostic(NonHaltingDiagnostic::CreatedPointerTag(
222 new_tag.inner(),
223 Some(kind_str),
224 loc.map(|(alloc_id, base_offset, orig_tag)| (alloc_id, alloc_range(base_offset, ptr_size), orig_tag)),
225 ));
226 }
227 drop(global); interp_ok(())
229 };
230
231 trace!("Reborrow of size {:?}", ptr_size);
232 let (alloc_id, base_offset, parent_prov) = match this.ptr_try_get_alloc_id(place.ptr(), 0) {
233 Ok(data) => {
234 data
237 }
238 Err(_) => {
239 assert_eq!(ptr_size, Size::ZERO); trace!(
243 "reborrow of size 0: reference {:?} derived from {:?} (pointee {})",
244 new_tag,
245 place.ptr(),
246 place.layout.ty,
247 );
248 log_creation(this, None)?;
249 return interp_ok(place.ptr().provenance);
251 }
252 };
253 log_creation(this, Some((alloc_id, base_offset, parent_prov)))?;
254
255 let orig_tag = match parent_prov {
256 ProvenanceExtra::Wildcard => return interp_ok(place.ptr().provenance), ProvenanceExtra::Concrete(tag) => tag,
258 };
259
260 trace!(
261 "reborrow: reference {:?} derived from {:?} (pointee {}): {:?}, size {}",
262 new_tag,
263 orig_tag,
264 place.layout.ty,
265 interpret::Pointer::new(alloc_id, base_offset),
266 ptr_size.bytes()
267 );
268
269 if let Some(protect) = new_perm.protector {
270 this.frame_mut()
274 .extra
275 .borrow_tracker
276 .as_mut()
277 .unwrap()
278 .protected_tags
279 .push((alloc_id, new_tag));
280 this.machine
281 .borrow_tracker
282 .as_mut()
283 .expect("We should have borrow tracking data")
284 .get_mut()
285 .protected_tags
286 .insert(new_tag, protect);
287 }
288
289 let alloc_kind = this.get_alloc_info(alloc_id).kind;
290 if !matches!(alloc_kind, AllocKind::LiveData) {
291 assert_eq!(ptr_size, Size::ZERO); return interp_ok(Some(Provenance::Concrete { alloc_id, tag: new_tag }));
295 }
296
297 let protected = new_perm.protector.is_some();
298 let precise_interior_mut = this
299 .machine
300 .borrow_tracker
301 .as_mut()
302 .unwrap()
303 .get_mut()
304 .borrow_tracker_method
305 .get_tree_borrows_params()
306 .precise_interior_mut;
307
308 let loc_state = |frozen: bool| -> LocationState {
310 let (perm, access) = if frozen {
311 (new_perm.freeze_perm, new_perm.freeze_access)
312 } else {
313 (new_perm.nonfreeze_perm, new_perm.nonfreeze_access)
314 };
315 let sifa = perm.strongest_idempotent_foreign_access(protected);
316 if access {
317 LocationState::new_accessed(perm, sifa)
318 } else {
319 LocationState::new_non_accessed(perm, sifa)
320 }
321 };
322 let inside_perms = if !precise_interior_mut {
323 let ty_is_freeze = place.layout.ty.is_freeze(*this.tcx, this.typing_env());
325 let state = loc_state(ty_is_freeze);
326 DedupRangeMap::new(ptr_size, state)
327 } else {
328 let mut perms_map: DedupRangeMap<LocationState> = DedupRangeMap::new(
330 ptr_size,
331 LocationState::new_accessed(
332 Permission::new_disabled(),
333 IdempotentForeignAccess::None,
334 ),
335 );
336 this.visit_freeze_sensitive(place, ptr_size, |range, frozen| {
337 let state = loc_state(frozen);
338 for (_loc_range, loc) in perms_map.iter_mut(range.start, range.size) {
339 *loc = state;
340 }
341 interp_ok(())
342 })?;
343 perms_map
344 };
345
346 let alloc_extra = this.get_alloc_extra(alloc_id)?;
347 let mut tree_borrows = alloc_extra.borrow_tracker_tb().borrow_mut();
348
349 for (perm_range, perm) in inside_perms.iter_all() {
350 if perm.accessed() {
351 let range_in_alloc = AllocRange {
354 start: Size::from_bytes(perm_range.start) + base_offset,
355 size: Size::from_bytes(perm_range.end - perm_range.start),
356 };
357
358 tree_borrows.perform_access(
359 orig_tag,
360 Some((range_in_alloc, AccessKind::Read, diagnostics::AccessCause::Reborrow)),
361 this.machine.borrow_tracker.as_ref().unwrap(),
362 alloc_id,
363 this.machine.current_span(),
364 )?;
365
366 if range_in_alloc.size.bytes() > 0 {
368 if let Some(data_race) = alloc_extra.data_race.as_vclocks_ref() {
369 data_race.read(
370 alloc_id,
371 range_in_alloc,
372 NaReadType::Retag,
373 Some(place.layout.ty),
374 &this.machine,
375 )?
376 }
377 }
378 }
379 }
380
381 tree_borrows.new_child(
383 base_offset,
384 orig_tag,
385 new_tag,
386 inside_perms,
387 new_perm.outside_perm,
388 protected,
389 this.machine.current_span(),
390 )?;
391 drop(tree_borrows);
392
393 interp_ok(Some(Provenance::Concrete { alloc_id, tag: new_tag }))
394 }
395
396 fn tb_retag_place(
397 &mut self,
398 place: &MPlaceTy<'tcx>,
399 new_perm: NewPermission,
400 ) -> InterpResult<'tcx, MPlaceTy<'tcx>> {
401 let this = self.eval_context_mut();
402
403 let reborrow_size =
409 this.size_and_align_of_val(place)?.map(|(size, _)| size).unwrap_or(place.layout.size);
410 trace!("Creating new permission: {:?} with size {:?}", new_perm, reborrow_size);
411
412 let new_tag = this.machine.borrow_tracker.as_mut().unwrap().get_mut().new_ptr();
419
420 let new_prov = this.tb_reborrow(place, reborrow_size, new_perm, new_tag)?;
422
423 interp_ok(place.clone().map_provenance(|_| new_prov.unwrap()))
427 }
428
429 fn tb_retag_reference(
431 &mut self,
432 val: &ImmTy<'tcx>,
433 new_perm: NewPermission,
434 ) -> InterpResult<'tcx, ImmTy<'tcx>> {
435 let this = self.eval_context_mut();
436 let place = this.ref_to_mplace(val)?;
437 let new_place = this.tb_retag_place(&place, new_perm)?;
438 interp_ok(ImmTy::from_immediate(new_place.to_ref(this), val.layout))
439 }
440}
441
442impl<'tcx> EvalContextExt<'tcx> for crate::MiriInterpCx<'tcx> {}
443pub trait EvalContextExt<'tcx>: crate::MiriInterpCxExt<'tcx> {
444 fn tb_retag_ptr_value(
447 &mut self,
448 kind: RetagKind,
449 val: &ImmTy<'tcx>,
450 ) -> InterpResult<'tcx, ImmTy<'tcx>> {
451 let this = self.eval_context_mut();
452 let new_perm = match val.layout.ty.kind() {
453 &ty::Ref(_, pointee, mutability) =>
454 NewPermission::new(pointee, Some(mutability), kind, this),
455 _ => None,
456 };
457 if let Some(new_perm) = new_perm {
458 this.tb_retag_reference(val, new_perm)
459 } else {
460 interp_ok(val.clone())
461 }
462 }
463
464 fn tb_retag_place_contents(
466 &mut self,
467 kind: RetagKind,
468 place: &PlaceTy<'tcx>,
469 ) -> InterpResult<'tcx> {
470 let this = self.eval_context_mut();
471 let options = this.machine.borrow_tracker.as_mut().unwrap().get_mut();
472 let retag_fields = options.retag_fields;
473 let mut visitor = RetagVisitor { ecx: this, kind, retag_fields };
474 return visitor.visit_value(place);
475
476 struct RetagVisitor<'ecx, 'tcx> {
478 ecx: &'ecx mut MiriInterpCx<'tcx>,
479 kind: RetagKind,
480 retag_fields: RetagFields,
481 }
482 impl<'ecx, 'tcx> RetagVisitor<'ecx, 'tcx> {
483 #[inline(always)] fn retag_ptr_inplace(
485 &mut self,
486 place: &PlaceTy<'tcx>,
487 new_perm: Option<NewPermission>,
488 ) -> InterpResult<'tcx> {
489 if let Some(new_perm) = new_perm {
490 let val = self.ecx.read_immediate(&self.ecx.place_to_op(place)?)?;
491 let val = self.ecx.tb_retag_reference(&val, new_perm)?;
492 self.ecx.write_immediate(*val, place)?;
493 }
494 interp_ok(())
495 }
496 }
497 impl<'ecx, 'tcx> ValueVisitor<'tcx, MiriMachine<'tcx>> for RetagVisitor<'ecx, 'tcx> {
498 type V = PlaceTy<'tcx>;
499
500 #[inline(always)]
501 fn ecx(&self) -> &MiriInterpCx<'tcx> {
502 self.ecx
503 }
504
505 fn visit_box(&mut self, box_ty: Ty<'tcx>, place: &PlaceTy<'tcx>) -> InterpResult<'tcx> {
509 if box_ty.is_box_global(*self.ecx.tcx) {
511 let pointee = place.layout.ty.builtin_deref(true).unwrap();
512 let new_perm =
513 NewPermission::new(pointee, None, self.kind, self.ecx);
514 self.retag_ptr_inplace(place, new_perm)?;
515 }
516 interp_ok(())
517 }
518
519 fn visit_value(&mut self, place: &PlaceTy<'tcx>) -> InterpResult<'tcx> {
520 if place.layout.is_sized() && place.layout.size < self.ecx.pointer_size() {
525 return interp_ok(());
526 }
527
528 match place.layout.ty.kind() {
530 &ty::Ref(_, pointee, mutability) => {
531 let new_perm =
532 NewPermission::new(pointee, Some(mutability), self.kind, self.ecx);
533 self.retag_ptr_inplace(place, new_perm)?;
534 }
535 ty::RawPtr(_, _) => {
536 }
541 ty::Adt(adt, _) if adt.is_box() => {
542 self.walk_value(place)?;
546 }
547 _ => {
548 let recurse = match self.retag_fields {
550 RetagFields::No => false,
551 RetagFields::Yes => true,
552 RetagFields::OnlyScalar => {
553 matches!(
556 place.layout.backend_repr,
557 BackendRepr::Scalar(..) | BackendRepr::ScalarPair(..)
558 )
559 }
560 };
561 if recurse {
562 self.walk_value(place)?;
563 }
564 }
565 }
566 interp_ok(())
567 }
568 }
569 }
570
571 fn tb_protect_place(&mut self, place: &MPlaceTy<'tcx>) -> InterpResult<'tcx, MPlaceTy<'tcx>> {
576 let this = self.eval_context_mut();
577
578 let new_perm = NewPermission {
580 freeze_perm: Permission::new_reserved_frz(),
585 freeze_access: true,
586 nonfreeze_perm: Permission::new_reserved_frz(),
587 nonfreeze_access: true,
588 outside_perm: Permission::new_reserved_frz(),
589 protector: Some(ProtectorKind::StrongProtector),
590 };
591 this.tb_retag_place(place, new_perm)
592 }
593
594 fn tb_expose_tag(&self, alloc_id: AllocId, tag: BorTag) -> InterpResult<'tcx> {
596 let this = self.eval_context_ref();
597
598 let kind = this.get_alloc_info(alloc_id).kind;
602 match kind {
603 AllocKind::LiveData => {
604 let alloc_extra = this.get_alloc_extra(alloc_id)?;
608 trace!("Tree Borrows tag {tag:?} exposed in {alloc_id:?}");
609 alloc_extra.borrow_tracker_tb().borrow_mut().expose_tag(tag);
610 }
611 AllocKind::Function | AllocKind::VTable | AllocKind::TypeId | AllocKind::Dead => {
612 }
614 }
615 interp_ok(())
616 }
617
618 fn print_tree(&mut self, alloc_id: AllocId, show_unnamed: bool) -> InterpResult<'tcx> {
620 let this = self.eval_context_mut();
621 let alloc_extra = this.get_alloc_extra(alloc_id)?;
622 let tree_borrows = alloc_extra.borrow_tracker_tb().borrow();
623 let borrow_tracker = &this.machine.borrow_tracker.as_ref().unwrap().borrow();
624 tree_borrows.print_tree(&borrow_tracker.protected_tags, show_unnamed)
625 }
626
627 fn tb_give_pointer_debug_name(
631 &mut self,
632 ptr: Pointer,
633 nth_parent: u8,
634 name: &str,
635 ) -> InterpResult<'tcx> {
636 let this = self.eval_context_mut();
637 let (tag, alloc_id) = match ptr.provenance {
638 Some(Provenance::Concrete { tag, alloc_id }) => (tag, alloc_id),
639 _ => {
640 eprintln!("Can't give the name {name} to Wildcard pointer");
641 return interp_ok(());
642 }
643 };
644 let alloc_extra = this.get_alloc_extra(alloc_id)?;
645 let mut tree_borrows = alloc_extra.borrow_tracker_tb().borrow_mut();
646 tree_borrows.give_pointer_debug_name(tag, nth_parent, name)
647 }
648}