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(TreeBorrowsParams),
230}
231
232#[derive(Debug, Copy, Clone, PartialEq, Eq)]
234pub struct TreeBorrowsParams {
235 pub precise_interior_mut: bool,
236}
237
238impl BorrowTrackerMethod {
239 pub fn instantiate_global_state(self, config: &MiriConfig) -> GlobalState {
240 RefCell::new(GlobalStateInner::new(
241 self,
242 config.tracked_pointer_tags.clone(),
243 config.retag_fields,
244 ))
245 }
246
247 pub fn get_tree_borrows_params(self) -> TreeBorrowsParams {
248 match self {
249 BorrowTrackerMethod::TreeBorrows(params) => params,
250 _ => panic!("can only be called when `BorrowTrackerMethod` is `TreeBorrows`"),
251 }
252 }
253}
254
255impl GlobalStateInner {
256 pub fn new_allocation(
257 &mut self,
258 id: AllocId,
259 alloc_size: Size,
260 kind: MemoryKind,
261 machine: &MiriMachine<'_>,
262 ) -> AllocState {
263 match self.borrow_tracker_method {
264 BorrowTrackerMethod::StackedBorrows =>
265 AllocState::StackedBorrows(Box::new(RefCell::new(Stacks::new_allocation(
266 id, alloc_size, self, kind, machine,
267 )))),
268 BorrowTrackerMethod::TreeBorrows { .. } =>
269 AllocState::TreeBorrows(Box::new(RefCell::new(Tree::new_allocation(
270 id, alloc_size, self, kind, machine,
271 )))),
272 }
273 }
274}
275
276impl<'tcx> EvalContextExt<'tcx> for crate::MiriInterpCx<'tcx> {}
277pub trait EvalContextExt<'tcx>: crate::MiriInterpCxExt<'tcx> {
278 fn retag_ptr_value(
279 &mut self,
280 kind: RetagKind,
281 val: &ImmTy<'tcx>,
282 ) -> InterpResult<'tcx, ImmTy<'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_ptr_value(kind, val),
287 BorrowTrackerMethod::TreeBorrows { .. } => this.tb_retag_ptr_value(kind, val),
288 }
289 }
290
291 fn retag_place_contents(
292 &mut self,
293 kind: RetagKind,
294 place: &PlaceTy<'tcx>,
295 ) -> InterpResult<'tcx> {
296 let this = self.eval_context_mut();
297 let method = this.machine.borrow_tracker.as_ref().unwrap().borrow().borrow_tracker_method;
298 match method {
299 BorrowTrackerMethod::StackedBorrows => this.sb_retag_place_contents(kind, place),
300 BorrowTrackerMethod::TreeBorrows { .. } => this.tb_retag_place_contents(kind, place),
301 }
302 }
303
304 fn protect_place(&mut self, place: &MPlaceTy<'tcx>) -> InterpResult<'tcx, MPlaceTy<'tcx>> {
305 let this = self.eval_context_mut();
306 let method = this.machine.borrow_tracker.as_ref().unwrap().borrow().borrow_tracker_method;
307 match method {
308 BorrowTrackerMethod::StackedBorrows => this.sb_protect_place(place),
309 BorrowTrackerMethod::TreeBorrows { .. } => this.tb_protect_place(place),
310 }
311 }
312
313 fn expose_tag(&self, alloc_id: AllocId, tag: BorTag) -> InterpResult<'tcx> {
314 let this = self.eval_context_ref();
315 let method = this.machine.borrow_tracker.as_ref().unwrap().borrow().borrow_tracker_method;
316 match method {
317 BorrowTrackerMethod::StackedBorrows => this.sb_expose_tag(alloc_id, tag),
318 BorrowTrackerMethod::TreeBorrows { .. } => this.tb_expose_tag(alloc_id, tag),
319 }
320 }
321
322 fn give_pointer_debug_name(
323 &mut self,
324 ptr: Pointer,
325 nth_parent: u8,
326 name: &str,
327 ) -> InterpResult<'tcx> {
328 let this = self.eval_context_mut();
329 let method = this.machine.borrow_tracker.as_ref().unwrap().borrow().borrow_tracker_method;
330 match method {
331 BorrowTrackerMethod::StackedBorrows => {
332 this.tcx.tcx.dcx().warn("Stacked Borrows does not support named pointers; `miri_pointer_name` is a no-op");
333 interp_ok(())
334 }
335 BorrowTrackerMethod::TreeBorrows { .. } =>
336 this.tb_give_pointer_debug_name(ptr, nth_parent, name),
337 }
338 }
339
340 fn print_borrow_state(&mut self, alloc_id: AllocId, show_unnamed: bool) -> InterpResult<'tcx> {
341 let this = self.eval_context_mut();
342 let Some(borrow_tracker) = &this.machine.borrow_tracker else {
343 eprintln!("attempted to print borrow state, but no borrow state is being tracked");
344 return interp_ok(());
345 };
346 let method = borrow_tracker.borrow().borrow_tracker_method;
347 match method {
348 BorrowTrackerMethod::StackedBorrows => this.print_stacks(alloc_id),
349 BorrowTrackerMethod::TreeBorrows { .. } => this.print_tree(alloc_id, show_unnamed),
350 }
351 }
352
353 fn on_stack_pop(
354 &self,
355 frame: &Frame<'tcx, Provenance, FrameExtra<'tcx>>,
356 ) -> InterpResult<'tcx> {
357 let this = self.eval_context_ref();
358 let borrow_tracker = this.machine.borrow_tracker.as_ref().unwrap();
359 for (alloc_id, tag) in &frame
362 .extra
363 .borrow_tracker
364 .as_ref()
365 .expect("we should have borrow tracking data")
366 .protected_tags
367 {
368 let kind = this.get_alloc_info(*alloc_id).kind;
375 if matches!(kind, AllocKind::LiveData) {
376 let alloc_extra = this.get_alloc_extra(*alloc_id)?; let alloc_borrow_tracker = &alloc_extra.borrow_tracker.as_ref().unwrap();
378 alloc_borrow_tracker.release_protector(
379 &this.machine,
380 borrow_tracker,
381 *tag,
382 *alloc_id,
383 )?;
384 }
385 }
386 borrow_tracker.borrow_mut().end_call(&frame.extra);
387 interp_ok(())
388 }
389}
390
391#[derive(Debug, Clone)]
393pub enum AllocState {
394 StackedBorrows(Box<RefCell<stacked_borrows::AllocState>>),
396 TreeBorrows(Box<RefCell<tree_borrows::AllocState>>),
398}
399
400impl machine::AllocExtra<'_> {
401 #[track_caller]
402 pub fn borrow_tracker_sb(&self) -> &RefCell<stacked_borrows::AllocState> {
403 match self.borrow_tracker {
404 Some(AllocState::StackedBorrows(ref sb)) => sb,
405 _ => panic!("expected Stacked Borrows borrow tracking, got something else"),
406 }
407 }
408
409 #[track_caller]
410 pub fn borrow_tracker_sb_mut(&mut self) -> &mut RefCell<stacked_borrows::AllocState> {
411 match self.borrow_tracker {
412 Some(AllocState::StackedBorrows(ref mut sb)) => sb,
413 _ => panic!("expected Stacked Borrows borrow tracking, got something else"),
414 }
415 }
416
417 #[track_caller]
418 pub fn borrow_tracker_tb(&self) -> &RefCell<tree_borrows::AllocState> {
419 match self.borrow_tracker {
420 Some(AllocState::TreeBorrows(ref tb)) => tb,
421 _ => panic!("expected Tree Borrows borrow tracking, got something else"),
422 }
423 }
424}
425
426impl AllocState {
427 pub fn before_memory_read<'tcx>(
428 &self,
429 alloc_id: AllocId,
430 prov_extra: ProvenanceExtra,
431 range: AllocRange,
432 machine: &MiriMachine<'tcx>,
433 ) -> InterpResult<'tcx> {
434 match self {
435 AllocState::StackedBorrows(sb) =>
436 sb.borrow_mut().before_memory_read(alloc_id, prov_extra, range, machine),
437 AllocState::TreeBorrows(tb) =>
438 tb.borrow_mut().before_memory_access(
439 AccessKind::Read,
440 alloc_id,
441 prov_extra,
442 range,
443 machine,
444 ),
445 }
446 }
447
448 pub fn before_memory_write<'tcx>(
449 &mut self,
450 alloc_id: AllocId,
451 prov_extra: ProvenanceExtra,
452 range: AllocRange,
453 machine: &MiriMachine<'tcx>,
454 ) -> InterpResult<'tcx> {
455 match self {
456 AllocState::StackedBorrows(sb) =>
457 sb.get_mut().before_memory_write(alloc_id, prov_extra, range, machine),
458 AllocState::TreeBorrows(tb) =>
459 tb.get_mut().before_memory_access(
460 AccessKind::Write,
461 alloc_id,
462 prov_extra,
463 range,
464 machine,
465 ),
466 }
467 }
468
469 pub fn before_memory_deallocation<'tcx>(
470 &mut self,
471 alloc_id: AllocId,
472 prov_extra: ProvenanceExtra,
473 size: Size,
474 machine: &MiriMachine<'tcx>,
475 ) -> InterpResult<'tcx> {
476 match self {
477 AllocState::StackedBorrows(sb) =>
478 sb.get_mut().before_memory_deallocation(alloc_id, prov_extra, size, machine),
479 AllocState::TreeBorrows(tb) =>
480 tb.get_mut().before_memory_deallocation(alloc_id, prov_extra, size, machine),
481 }
482 }
483
484 pub fn remove_unreachable_tags(&self, tags: &FxHashSet<BorTag>) {
485 match self {
486 AllocState::StackedBorrows(sb) => sb.borrow_mut().remove_unreachable_tags(tags),
487 AllocState::TreeBorrows(tb) => tb.borrow_mut().remove_unreachable_tags(tags),
488 }
489 }
490
491 pub fn release_protector<'tcx>(
493 &self,
494 machine: &MiriMachine<'tcx>,
495 global: &GlobalState,
496 tag: BorTag,
497 alloc_id: AllocId, ) -> InterpResult<'tcx> {
499 match self {
500 AllocState::StackedBorrows(_sb) => interp_ok(()),
501 AllocState::TreeBorrows(tb) =>
502 tb.borrow_mut().release_protector(machine, global, tag, alloc_id),
503 }
504 }
505}
506
507impl VisitProvenance for AllocState {
508 fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
509 match self {
510 AllocState::StackedBorrows(sb) => sb.visit_provenance(visit),
511 AllocState::TreeBorrows(tb) => tb.visit_provenance(visit),
512 }
513 }
514}