miri/borrow_tracker/tree_borrows/
mod.rs1use rustc_abi::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::{AccessKind, GlobalState, GlobalStateInner, ProtectorKind};
9use crate::concurrency::data_race::{NaReadType, NaWriteType};
10use crate::*;
11
12pub mod diagnostics;
13mod foreign_access_skipping;
14mod perms;
15mod tree;
16mod tree_visitor;
17mod unimap;
18mod wildcard;
19
20#[cfg(test)]
21mod exhaustive;
22
23use self::perms::Permission;
24pub use self::tree::Tree;
25
26pub type AllocState = Tree;
27
28impl<'tcx> Tree {
29 pub fn new_allocation(
31 id: AllocId,
32 size: Size,
33 state: &mut GlobalStateInner,
34 _kind: MemoryKind,
35 machine: &MiriMachine<'tcx>,
36 ) -> Self {
37 let tag = state.root_ptr_tag(id, machine); let span = machine.current_user_relevant_span();
39 Tree::new(tag, size, span)
40 }
41
42 pub fn before_memory_access(
45 &mut self,
46 access_kind: AccessKind,
47 alloc_id: AllocId,
48 prov: ProvenanceExtra,
49 range: AllocRange,
50 machine: &MiriMachine<'tcx>,
51 ) -> InterpResult<'tcx> {
52 trace!(
53 "{} with tag {:?}: {:?}, size {}",
54 access_kind,
55 prov,
56 interpret::Pointer::new(alloc_id, range.start),
57 range.size.bytes(),
58 );
59 let global = machine.borrow_tracker.as_ref().unwrap();
60 let span = machine.current_user_relevant_span();
61 self.perform_access(
62 prov,
63 range,
64 access_kind,
65 diagnostics::AccessCause::Explicit(access_kind),
66 global,
67 alloc_id,
68 span,
69 )
70 }
71
72 pub fn before_memory_deallocation(
74 &mut self,
75 alloc_id: AllocId,
76 prov: ProvenanceExtra,
77 size: Size,
78 machine: &MiriMachine<'tcx>,
79 ) -> InterpResult<'tcx> {
80 let global = machine.borrow_tracker.as_ref().unwrap();
81 let span = machine.current_user_relevant_span();
82 self.dealloc(prov, alloc_range(Size::ZERO, size), global, alloc_id, span)
83 }
84
85 pub fn release_protector(
92 &mut self,
93 machine: &MiriMachine<'tcx>,
94 global: &GlobalState,
95 tag: BorTag,
96 alloc_id: AllocId, ) -> InterpResult<'tcx> {
98 let span = machine.current_user_relevant_span();
99 self.perform_protector_end_access(tag, global, alloc_id, span)?;
100
101 self.update_exposure_for_protector_release(tag);
102
103 interp_ok(())
104 }
105}
106
107#[derive(Debug, Clone, Copy)]
109pub struct NewPermission {
110 freeze_perm: Permission,
112 nonfreeze_perm: Permission,
114 outside_perm: Permission,
116 protector: Option<ProtectorKind>,
119}
120
121impl<'tcx> NewPermission {
122 fn new(
126 pointee: Ty<'tcx>,
127 ref_mutability: Option<Mutability>,
128 retag_kind: RetagKind,
129 cx: &crate::MiriInterpCx<'tcx>,
130 ) -> Option<Self> {
131 let ty_is_unpin = pointee.is_unpin(*cx.tcx, cx.typing_env())
132 && pointee.is_unsafe_unpin(*cx.tcx, cx.typing_env());
133 let ty_is_freeze = pointee.is_freeze(*cx.tcx, cx.typing_env());
134 let is_protected = retag_kind == RetagKind::FnEntry;
135
136 let implicit_writes = cx
138 .machine
139 .borrow_tracker
140 .as_ref()
141 .unwrap()
142 .borrow()
143 .borrow_tracker_method
144 .get_tree_borrows_params()
145 .implicit_writes;
146
147 if matches!(ref_mutability, Some(Mutability::Mut) | None if !ty_is_unpin) {
148 return None;
151 }
152
153 enum Part {
154 InsideFrozen,
155 InsideUnsafeCell,
156 Outside,
157 }
158 use Part::*;
159
160 let perm = |part: Part| {
161 let frozen = match part {
164 InsideFrozen => true,
165 InsideUnsafeCell => false,
166 Outside => ty_is_freeze,
167 };
168 match ref_mutability {
169 Some(Mutability::Not) =>
171 if frozen {
172 Permission::new_frozen()
173 } else {
174 Permission::new_cell()
175 },
176 Some(Mutability::Mut) => {
178 if is_protected && implicit_writes && !matches!(part, Outside) {
179 Permission::new_unique()
181 } else if is_protected || frozen {
182 Permission::new_reserved_frz()
185 } else {
186 Permission::new_reserved_im()
187 }
188 }
189 None =>
191 if is_protected && implicit_writes && !matches!(part, Outside) {
192 Permission::new_unique()
194 } else if is_protected || frozen {
195 Permission::new_reserved_frz()
198 } else {
199 Permission::new_reserved_im()
200 },
201 }
202 };
203
204 Some(NewPermission {
205 freeze_perm: perm(InsideFrozen),
206 nonfreeze_perm: perm(InsideUnsafeCell),
207 outside_perm: perm(Outside),
208 protector: is_protected.then_some(if ref_mutability.is_some() {
209 ProtectorKind::StrongProtector
211 } else {
212 ProtectorKind::WeakProtector
214 }),
215 })
216 }
217}
218
219impl<'tcx> EvalContextPrivExt<'tcx> for crate::MiriInterpCx<'tcx> {}
223trait EvalContextPrivExt<'tcx>: crate::MiriInterpCxExt<'tcx> {
224 fn tb_reborrow(
226 &mut self,
227 place: &MPlaceTy<'tcx>, ptr_size: Size,
229 new_perm: NewPermission,
230 new_tag: BorTag,
231 ) -> InterpResult<'tcx, Option<Provenance>> {
232 let this = self.eval_context_mut();
233 this.check_ptr_access(place.ptr(), ptr_size, CheckInAllocMsg::Dereferenceable)?;
235
236 let log_creation = |this: &MiriInterpCx<'tcx>,
238 loc: Option<(AllocId, Size, ProvenanceExtra)>| -> InterpResult<'tcx> {
240 let global = this.machine.borrow_tracker.as_ref().unwrap().borrow();
241 let ty = place.layout.ty;
242 if global.tracked_pointer_tags.contains(&new_tag) {
243 let ty_is_freeze = ty.is_freeze(*this.tcx, this.typing_env());
244 let kind_str =
245 if ty_is_freeze {
246 format!("initial state {} (pointee type {ty})", new_perm.freeze_perm)
247 } else {
248 format!("initial state {}/{} outside/inside UnsafeCell (pointee type {ty})", new_perm.freeze_perm, new_perm.nonfreeze_perm)
249 };
250 this.emit_diagnostic(NonHaltingDiagnostic::CreatedPointerTag(
251 new_tag.inner(),
252 Some(kind_str),
253 loc.map(|(alloc_id, base_offset, orig_tag)| (alloc_id, alloc_range(base_offset, ptr_size), orig_tag)),
254 ));
255 }
256 drop(global); interp_ok(())
258 };
259
260 trace!("Reborrow of size {:?}", ptr_size);
261 let Ok((alloc_id, base_offset, parent_prov)) = this.ptr_try_get_alloc_id(place.ptr(), 0)
264 else {
265 assert_eq!(ptr_size, Size::ZERO); let new_prov = place.ptr().provenance;
269 trace!("reborrow of size 0: reusing {:?} (pointee {})", place.ptr(), place.layout.ty,);
270 log_creation(this, None)?;
271 return interp_ok(new_prov);
273 };
274 let new_prov = Provenance::Concrete { alloc_id, tag: new_tag };
275
276 log_creation(this, Some((alloc_id, base_offset, parent_prov)))?;
277
278 trace!(
279 "reborrow: reference {:?} derived from {:?} (pointee {}): {:?}, size {}",
280 new_tag,
281 parent_prov,
282 place.layout.ty,
283 interpret::Pointer::new(alloc_id, base_offset),
284 ptr_size.bytes()
285 );
286
287 if let Some(protect) = new_perm.protector {
288 this.frame_mut()
292 .extra
293 .borrow_tracker
294 .as_mut()
295 .unwrap()
296 .protected_tags
297 .push((alloc_id, new_tag));
298 this.machine
299 .borrow_tracker
300 .as_mut()
301 .expect("We should have borrow tracking data")
302 .get_mut()
303 .protected_tags
304 .insert(new_tag, protect);
305 }
306
307 let alloc_kind = this.get_alloc_info(alloc_id).kind;
308 if !matches!(alloc_kind, AllocKind::LiveData) {
309 assert_eq!(ptr_size, Size::ZERO); return interp_ok(Some(new_prov));
313 }
314
315 let protected = new_perm.protector.is_some();
316 let precise_interior_mut = this
317 .machine
318 .borrow_tracker
319 .as_mut()
320 .unwrap()
321 .get_mut()
322 .borrow_tracker_method
323 .get_tree_borrows_params()
324 .precise_interior_mut;
325
326 let loc_state = |frozen: bool| -> LocationState {
328 let perm = if frozen { new_perm.freeze_perm } else { new_perm.nonfreeze_perm };
329 let sifa = perm.strongest_idempotent_foreign_access(protected);
330
331 if perm.associated_access().is_some() {
332 LocationState::new_accessed(perm, sifa)
333 } else {
334 LocationState::new_non_accessed(perm, sifa)
335 }
336 };
337 let inside_perms = if !precise_interior_mut {
338 let ty_is_freeze = place.layout.ty.is_freeze(*this.tcx, this.typing_env());
340 DedupRangeMap::new(ptr_size, loc_state(ty_is_freeze))
341 } else {
342 let mut perms_map = DedupRangeMap::new(
344 ptr_size,
345 LocationState::new_accessed(
346 Permission::new_disabled(),
347 IdempotentForeignAccess::None,
348 ),
349 );
350 this.visit_freeze_sensitive(place, ptr_size, |range, frozen| {
351 let state = loc_state(frozen);
352 for (_loc_range, loc) in perms_map.iter_mut(range.start, range.size) {
353 *loc = state;
354 }
355 interp_ok(())
356 })?;
357 perms_map
358 };
359
360 let alloc_extra = this.get_alloc_extra(alloc_id)?;
361 let mut tree_borrows = alloc_extra.borrow_tracker_tb().borrow_mut();
362
363 for (perm_range, loc_state) in inside_perms.iter_all() {
364 if let Some(access) = loc_state.permission().associated_access() {
365 if access == AccessKind::Write
370 && this.get_alloc_mutability(alloc_id).unwrap().is_not()
371 {
372 throw_ub!(WriteToReadOnly(alloc_id))
373 }
374
375 let range_in_alloc = AllocRange {
377 start: Size::from_bytes(perm_range.start) + base_offset,
378 size: Size::from_bytes(perm_range.end - perm_range.start),
379 };
380
381 tree_borrows.perform_access(
382 parent_prov,
383 range_in_alloc,
384 access,
385 diagnostics::AccessCause::Reborrow(access),
386 this.machine.borrow_tracker.as_ref().unwrap(),
387 alloc_id,
388 this.machine.current_user_relevant_span(),
389 )?;
390
391 if range_in_alloc.size.bytes() > 0 {
393 if let Some(data_race) = alloc_extra.data_race.as_vclocks_ref() {
394 match access {
395 AccessKind::Read =>
396 data_race.read_non_atomic(
397 alloc_id,
398 range_in_alloc,
399 NaReadType::Retag,
400 Some(place.layout.ty),
401 &this.machine,
402 )?,
403 AccessKind::Write =>
404 data_race.write_non_atomic(
405 alloc_id,
406 range_in_alloc,
407 NaWriteType::Retag,
408 Some(place.layout.ty),
409 &this.machine,
410 )?,
411 };
412 }
413 }
414 }
415 }
416
417 tree_borrows.new_child(
419 base_offset,
420 parent_prov,
421 new_tag,
422 inside_perms,
423 new_perm.outside_perm,
424 protected,
425 this.machine.current_user_relevant_span(),
426 )?;
427
428 interp_ok(Some(new_prov))
429 }
430
431 fn tb_retag_place(
432 &mut self,
433 place: &MPlaceTy<'tcx>,
434 new_perm: NewPermission,
435 ) -> InterpResult<'tcx, MPlaceTy<'tcx>> {
436 let this = self.eval_context_mut();
437
438 let reborrow_size =
444 this.size_and_align_of_val(place)?.map(|(size, _)| size).unwrap_or(place.layout.size);
445 trace!("Creating new permission: {:?} with size {:?}", new_perm, reborrow_size);
446
447 let new_tag = this.machine.borrow_tracker.as_mut().unwrap().get_mut().new_ptr();
454
455 let new_prov = this.tb_reborrow(place, reborrow_size, new_perm, new_tag)?;
457
458 interp_ok(place.clone().map_provenance(|_| new_prov.unwrap()))
462 }
463
464 fn tb_retag_reference(
466 &mut self,
467 val: &ImmTy<'tcx>,
468 new_perm: NewPermission,
469 ) -> InterpResult<'tcx, ImmTy<'tcx>> {
470 let this = self.eval_context_mut();
471 let place = this.imm_ptr_to_mplace(val)?;
472 let new_place = this.tb_retag_place(&place, new_perm)?;
473 interp_ok(ImmTy::from_immediate(new_place.to_ref(this), val.layout))
474 }
475}
476
477impl<'tcx> EvalContextExt<'tcx> for crate::MiriInterpCx<'tcx> {}
478pub trait EvalContextExt<'tcx>: crate::MiriInterpCxExt<'tcx> {
479 fn tb_retag_ptr_value(
482 &mut self,
483 kind: RetagKind,
484 val: &ImmTy<'tcx>,
485 ) -> InterpResult<'tcx, ImmTy<'tcx>> {
486 let this = self.eval_context_mut();
487 let new_perm = match val.layout.ty.kind() {
488 &ty::Ref(_, pointee, mutability) =>
489 NewPermission::new(pointee, Some(mutability), kind, this),
490 _ => None,
491 };
492 if let Some(new_perm) = new_perm {
493 this.tb_retag_reference(val, new_perm)
494 } else {
495 interp_ok(val.clone())
496 }
497 }
498
499 fn tb_retag_place_contents(
501 &mut self,
502 kind: RetagKind,
503 place: &PlaceTy<'tcx>,
504 ) -> InterpResult<'tcx> {
505 let this = self.eval_context_mut();
506 let mut visitor = RetagVisitor { ecx: this, kind };
507 return visitor.visit_value(place);
508
509 struct RetagVisitor<'ecx, 'tcx> {
511 ecx: &'ecx mut MiriInterpCx<'tcx>,
512 kind: RetagKind,
513 }
514 impl<'ecx, 'tcx> RetagVisitor<'ecx, 'tcx> {
515 #[inline(always)] fn retag_ptr_inplace(
517 &mut self,
518 place: &PlaceTy<'tcx>,
519 new_perm: Option<NewPermission>,
520 ) -> InterpResult<'tcx> {
521 if let Some(new_perm) = new_perm {
522 let val = self.ecx.read_immediate(&self.ecx.place_to_op(place)?)?;
523 let val = self.ecx.tb_retag_reference(&val, new_perm)?;
524 self.ecx.write_immediate(*val, place)?;
525 }
526 interp_ok(())
527 }
528 }
529 impl<'ecx, 'tcx> ValueVisitor<'tcx, MiriMachine<'tcx>> for RetagVisitor<'ecx, 'tcx> {
530 type V = PlaceTy<'tcx>;
531
532 #[inline(always)]
533 fn ecx(&self) -> &MiriInterpCx<'tcx> {
534 self.ecx
535 }
536
537 fn visit_box(&mut self, box_ty: Ty<'tcx>, place: &PlaceTy<'tcx>) -> InterpResult<'tcx> {
541 if box_ty.is_box_global(*self.ecx.tcx) {
543 let pointee = place.layout.ty.builtin_deref(true).unwrap();
544 let new_perm =
545 NewPermission::new(pointee, None, self.kind, self.ecx);
546 self.retag_ptr_inplace(place, new_perm)?;
547 }
548 interp_ok(())
549 }
550
551 fn visit_value(&mut self, place: &PlaceTy<'tcx>) -> InterpResult<'tcx> {
552 if place.layout.is_sized() && place.layout.size < self.ecx.pointer_size() {
557 return interp_ok(());
558 }
559
560 match place.layout.ty.kind() {
562 &ty::Ref(_, pointee, mutability) => {
563 let new_perm =
564 NewPermission::new(pointee, Some(mutability), self.kind, self.ecx);
565 self.retag_ptr_inplace(place, new_perm)?;
566 }
567 ty::RawPtr(_, _) => {
568 }
573 ty::Adt(adt, _) if adt.is_box() => {
574 self.walk_value(place)?;
578 }
579 ty::Adt(adt, _) if adt.is_maybe_dangling() => {
580 }
582 _ => {
583 self.walk_value(place)?;
585 }
586 }
587 interp_ok(())
588 }
589 }
590 }
591
592 fn tb_protect_place(&mut self, place: &MPlaceTy<'tcx>) -> InterpResult<'tcx, MPlaceTy<'tcx>> {
597 let this = self.eval_context_mut();
598
599 let new_perm = NewPermission {
601 freeze_perm: Permission::new_reserved_frz(),
606 nonfreeze_perm: Permission::new_reserved_frz(),
607 outside_perm: Permission::new_reserved_frz(),
608 protector: Some(ProtectorKind::StrongProtector),
609 };
610 this.tb_retag_place(place, new_perm)
611 }
612
613 fn tb_expose_tag(&self, alloc_id: AllocId, tag: BorTag) -> InterpResult<'tcx> {
615 let this = self.eval_context_ref();
616
617 let kind = this.get_alloc_info(alloc_id).kind;
621 match kind {
622 AllocKind::LiveData => {
623 let alloc_extra = this.get_alloc_extra(alloc_id)?;
627 trace!("Tree Borrows tag {tag:?} exposed in {alloc_id:?}");
628
629 let global = this.machine.borrow_tracker.as_ref().unwrap();
630 let protected_tags = &global.borrow().protected_tags;
631 let protected = protected_tags.contains_key(&tag);
632 alloc_extra.borrow_tracker_tb().borrow_mut().expose_tag(tag, protected);
633 }
634 AllocKind::Function
635 | AllocKind::VTable
636 | AllocKind::TypeId
637 | AllocKind::Dead
638 | AllocKind::VaList => {
639 }
641 }
642 interp_ok(())
643 }
644
645 fn print_tree(&mut self, alloc_id: AllocId, show_unnamed: bool) -> InterpResult<'tcx> {
647 let this = self.eval_context_mut();
648 let alloc_extra = this.get_alloc_extra(alloc_id)?;
649 let tree_borrows = alloc_extra.borrow_tracker_tb().borrow();
650 let borrow_tracker = &this.machine.borrow_tracker.as_ref().unwrap().borrow();
651 tree_borrows.print_tree(&borrow_tracker.protected_tags, show_unnamed)
652 }
653
654 fn tb_give_pointer_debug_name(
658 &mut self,
659 ptr: Pointer,
660 nth_parent: u8,
661 name: &str,
662 ) -> InterpResult<'tcx> {
663 let this = self.eval_context_mut();
664 let (tag, alloc_id) = match ptr.provenance {
665 Some(Provenance::Concrete { tag, alloc_id }) => (tag, alloc_id),
666 Some(Provenance::Wildcard) => {
667 eprintln!("Can't give the name {name} to wildcard pointer");
668 return interp_ok(());
669 }
670 None => {
671 eprintln!("Can't give the name {name} to pointer without provenance");
672 return interp_ok(());
673 }
674 };
675 let alloc_extra = this.get_alloc_extra(alloc_id)?;
676 let mut tree_borrows = alloc_extra.borrow_tracker_tb().borrow_mut();
677 tree_borrows.give_pointer_debug_name(tag, nth_parent, name)
678 }
679}