1 //! Implementation of a data-race detector using Lamport Timestamps / Vector-clocks
2 //! based on the Dyamic Race Detection for C++:
3 //! https://www.doc.ic.ac.uk/~afd/homepages/papers/pdfs/2017/POPL.pdf
4 //! which does not report false-positives when fences are used, and gives better
5 //! accuracy in presence of read-modify-write operations.
7 //! This does not explore weak memory orders and so can still miss data-races
8 //! but should not report false-positives
10 //! Data-race definiton from(https://en.cppreference.com/w/cpp/language/memory_model#Threads_and_data_races):
11 //! a data race occurs between two memory accesses if they are on different threads, at least one operation
12 //! is non-atomic, at least one operation is a write and neither access happens-before the other. Read the link
13 //! for full definition.
15 //! This re-uses vector indexes for threads that are known to be unable to report data-races, this is valid
16 //! because it only re-uses vector indexes once all currently-active (not-terminated) threads have an internal
17 //! vector clock that happens-after the join operation of the candidate thread. Threads that have not been joined
18 //! on are not considered. Since the thread's vector clock will only increase and a data-race implies that
19 //! there is some index x where clock[x] > thread_clock, when this is true clock[candidate-idx] > thread_clock
20 //! can never hold and hence a data-race can never be reported in that vector index again.
21 //! This means that the thread-index can be safely re-used, starting on the next timestamp for the newly created
24 //! The sequentially consistant ordering corresponds to the ordering that the threads
25 //! are currently scheduled, this means that the data-race detector has no additional
26 //! logic for sequentially consistent accesses at the moment since they are indistinguishable
27 //! from acquire/release operations. If weak memory orderings are explored then this
28 //! may need to change or be updated accordingly.
30 //! Per the C++ spec for the memory model a sequentially consistent operation:
31 //! "A load operation with this memory order performs an acquire operation,
32 //! a store performs a release operation, and read-modify-write performs
33 //! both an acquire operation and a release operation, plus a single total
34 //! order exists in which all threads observe all modifications in the same
35 //! order (see Sequentially-consistent ordering below) "
36 //! So in the absence of weak memory effects a seq-cst load & a seq-cst store is identical
37 //! to a acquire load and a release store given the global sequentially consistent order
41 //! currently we have our own local copy of the currently active thread index and names, this is due
42 //! in part to the inability to access the current location of threads.active_thread inside the AllocExtra
43 //! read, write and deallocate functions and should be cleaned up in the future.
46 cell::{Cell, Ref, RefCell, RefMut},
52 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
53 use rustc_index::vec::{Idx, IndexVec};
54 use rustc_middle::{mir, ty::layout::TyAndLayout};
55 use rustc_target::abi::Size;
58 ImmTy, Immediate, InterpResult, MPlaceTy, MemPlaceMeta, MiriEvalContext, MiriEvalContextExt,
59 OpTy, Pointer, RangeMap, ScalarMaybeUninit, Tag, ThreadId, VClock, VSmallClockMap, VTimestamp,
63 pub type AllocExtra = VClockAlloc;
64 pub type MemoryExtra = Rc<GlobalState>;
66 /// Valid atomic read-write operations, alias of atomic::Ordering (not non-exhaustive).
67 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
76 /// Valid atomic read operations, subset of atomic::Ordering.
77 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
78 pub enum AtomicReadOp {
84 /// Valid atomic write operations, subset of atomic::Ordering.
85 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
86 pub enum AtomicWriteOp {
92 /// Valid atomic fence operations, subset of atomic::Ordering.
93 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
94 pub enum AtomicFenceOp {
101 /// The current set of vector clocks describing the state
102 /// of a thread, contains the happens-before clock and
103 /// additional metadata to model atomic fence operations.
104 #[derive(Clone, Default, Debug)]
105 struct ThreadClockSet {
106 /// The increasing clock representing timestamps
107 /// that happen-before this thread.
110 /// The set of timestamps that will happen-before this
111 /// thread once it performs an acquire fence.
112 fence_acquire: VClock,
114 /// The last timesamp of happens-before relations that
115 /// have been released by this thread by a fence.
116 fence_release: VClock,
119 impl ThreadClockSet {
120 /// Apply the effects of a release fence to this
121 /// set of thread vector clocks.
123 fn apply_release_fence(&mut self) {
124 self.fence_release.clone_from(&self.clock);
127 /// Apply the effects of a acquire fence to this
128 /// set of thread vector clocks.
130 fn apply_acquire_fence(&mut self) {
131 self.clock.join(&self.fence_acquire);
134 /// Increment the happens-before clock at a
137 fn increment_clock(&mut self, index: VectorIdx) {
138 self.clock.increment_index(index);
141 /// Join the happens-before clock with that of
142 /// another thread, used to model thread join
144 fn join_with(&mut self, other: &ThreadClockSet) {
145 self.clock.join(&other.clock);
149 /// Error returned by finding a data race
150 /// should be elaborated upon.
151 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
154 /// Externally stored memory cell clocks
155 /// explicitly to reduce memory usage for the
156 /// common case where no atomic operations
157 /// exists on the memory cell.
158 #[derive(Clone, PartialEq, Eq, Default, Debug)]
159 struct AtomicMemoryCellClocks {
160 /// The clock-vector of the timestamp of the last atomic
161 /// read operation performed by each thread.
162 /// This detects potential data-races between atomic read
163 /// and non-atomic write operations.
166 /// The clock-vector of the timestamp of the last atomic
167 /// write operation performed by each thread.
168 /// This detects potential data-races between atomic write
169 /// and non-atomic read or write operations.
170 write_vector: VClock,
172 /// Synchronization vector for acquire-release semantics
173 /// contains the vector of timestamps that will
174 /// happen-before a thread if an acquire-load is
175 /// performed on the data.
178 /// The Hash-Map of all threads for which a release
179 /// sequence exists in the memory cell, required
180 /// since read-modify-write operations do not
181 /// invalidate existing release sequences.
182 /// See page 6 of linked paper.
183 release_sequences: VSmallClockMap,
186 /// Memory Cell vector clock metadata
187 /// for data-race detection.
188 #[derive(Clone, PartialEq, Eq, Debug)]
189 struct MemoryCellClocks {
190 /// The vector-clock timestamp of the last write
191 /// corresponding to the writing threads timestamp.
194 /// The identifier of the vector index, corresponding to a thread
195 /// that performed the last write operation.
196 write_index: VectorIdx,
198 /// The vector-clock of the timestamp of the last read operation
199 /// performed by a thread since the last write operation occured.
200 /// It is reset to zero on each write operation.
203 /// Atomic acquire & release sequence tracking clocks.
204 /// For non-atomic memory in the common case this
205 /// value is set to None.
206 atomic_ops: Option<Box<AtomicMemoryCellClocks>>,
209 /// Create a default memory cell clocks instance
210 /// for uninitialized memory.
211 impl Default for MemoryCellClocks {
212 fn default() -> Self {
214 read: VClock::default(),
216 write_index: VectorIdx::MAX_INDEX,
222 impl MemoryCellClocks {
223 /// Load the internal atomic memory cells if they exist.
225 fn atomic(&self) -> Option<&AtomicMemoryCellClocks> {
226 match &self.atomic_ops {
227 Some(op) => Some(&*op),
232 /// Load or create the internal atomic memory metadata
233 /// if it does not exist.
235 fn atomic_mut(&mut self) -> &mut AtomicMemoryCellClocks {
236 self.atomic_ops.get_or_insert_with(Default::default)
239 /// Update memory cell data-race tracking for atomic
240 /// load acquire semantics, is a no-op if this memory was
241 /// not used previously as atomic memory.
244 clocks: &mut ThreadClockSet,
246 ) -> Result<(), DataRace> {
247 self.atomic_read_detect(clocks, index)?;
248 if let Some(atomic) = self.atomic() {
249 clocks.clock.join(&atomic.sync_vector);
254 /// Update memory cell data-race tracking for atomic
255 /// load relaxed semantics, is a no-op if this memory was
256 /// not used previously as atomic memory.
259 clocks: &mut ThreadClockSet,
261 ) -> Result<(), DataRace> {
262 self.atomic_read_detect(clocks, index)?;
263 if let Some(atomic) = self.atomic() {
264 clocks.fence_acquire.join(&atomic.sync_vector);
269 /// Update the memory cell data-race tracking for atomic
270 /// store release semantics.
271 fn store_release(&mut self, clocks: &ThreadClockSet, index: VectorIdx) -> Result<(), DataRace> {
272 self.atomic_write_detect(clocks, index)?;
273 let atomic = self.atomic_mut();
274 atomic.sync_vector.clone_from(&clocks.clock);
275 atomic.release_sequences.clear();
276 atomic.release_sequences.insert(index, &clocks.clock);
280 /// Update the memory cell data-race tracking for atomic
281 /// store relaxed semantics.
282 fn store_relaxed(&mut self, clocks: &ThreadClockSet, index: VectorIdx) -> Result<(), DataRace> {
283 self.atomic_write_detect(clocks, index)?;
284 let atomic = self.atomic_mut();
285 atomic.sync_vector.clone_from(&clocks.fence_release);
286 if let Some(release) = atomic.release_sequences.get(index) {
287 atomic.sync_vector.join(release);
289 atomic.release_sequences.retain_index(index);
293 /// Update the memory cell data-race tracking for atomic
294 /// store release semantics for RMW operations.
295 fn rmw_release(&mut self, clocks: &ThreadClockSet, index: VectorIdx) -> Result<(), DataRace> {
296 self.atomic_write_detect(clocks, index)?;
297 let atomic = self.atomic_mut();
298 atomic.sync_vector.join(&clocks.clock);
299 atomic.release_sequences.insert(index, &clocks.clock);
303 /// Update the memory cell data-race tracking for atomic
304 /// store relaxed semantics for RMW operations.
305 fn rmw_relaxed(&mut self, clocks: &ThreadClockSet, index: VectorIdx) -> Result<(), DataRace> {
306 self.atomic_write_detect(clocks, index)?;
307 let atomic = self.atomic_mut();
308 atomic.sync_vector.join(&clocks.fence_release);
312 /// Detect data-races with an atomic read, caused by a non-atomic write that does
313 /// not happen-before the atomic-read.
314 fn atomic_read_detect(
316 clocks: &ThreadClockSet,
318 ) -> Result<(), DataRace> {
319 log::trace!("Atomic read with vectors: {:#?} :: {:#?}", self, clocks);
320 if self.write <= clocks.clock[self.write_index] {
321 let atomic = self.atomic_mut();
322 atomic.read_vector.set_at_index(&clocks.clock, index);
329 /// Detect data-races with an atomic write, either with a non-atomic read or with
330 /// a non-atomic write.
331 fn atomic_write_detect(
333 clocks: &ThreadClockSet,
335 ) -> Result<(), DataRace> {
336 log::trace!("Atomic write with vectors: {:#?} :: {:#?}", self, clocks);
337 if self.write <= clocks.clock[self.write_index] && self.read <= clocks.clock {
338 let atomic = self.atomic_mut();
339 atomic.write_vector.set_at_index(&clocks.clock, index);
346 /// Detect races for non-atomic read operations at the current memory cell
347 /// returns true if a data-race is detected.
350 clocks: &ThreadClockSet,
352 ) -> Result<(), DataRace> {
353 log::trace!("Unsynchronized read with vectors: {:#?} :: {:#?}", self, clocks);
354 if self.write <= clocks.clock[self.write_index] {
355 let race_free = if let Some(atomic) = self.atomic() {
356 atomic.write_vector <= clocks.clock
361 self.read.set_at_index(&clocks.clock, index);
371 /// Detect races for non-atomic write operations at the current memory cell
372 /// returns true if a data-race is detected.
373 fn write_race_detect(
375 clocks: &ThreadClockSet,
377 ) -> Result<(), DataRace> {
378 log::trace!("Unsynchronized write with vectors: {:#?} :: {:#?}", self, clocks);
379 if self.write <= clocks.clock[self.write_index] && self.read <= clocks.clock {
380 let race_free = if let Some(atomic) = self.atomic() {
381 atomic.write_vector <= clocks.clock && atomic.read_vector <= clocks.clock
386 self.write = clocks.clock[index];
387 self.write_index = index;
388 self.read.set_zero_vector();
399 /// Evaluation context extensions.
400 impl<'mir, 'tcx: 'mir> EvalContextExt<'mir, 'tcx> for MiriEvalContext<'mir, 'tcx> {}
401 pub trait EvalContextExt<'mir, 'tcx: 'mir>: MiriEvalContextExt<'mir, 'tcx> {
402 /// Atomic variant of read_scalar_at_offset.
403 fn read_scalar_at_offset_atomic(
407 layout: TyAndLayout<'tcx>,
408 atomic: AtomicReadOp,
409 ) -> InterpResult<'tcx, ScalarMaybeUninit<Tag>> {
410 let this = self.eval_context_ref();
411 let op_place = this.deref_operand(op)?;
412 let offset = Size::from_bytes(offset);
414 // Ensure that the following read at an offset is within bounds.
415 assert!(op_place.layout.size >= offset + layout.size);
416 let value_place = op_place.offset(offset, MemPlaceMeta::None, layout, this)?;
417 this.read_scalar_atomic(value_place, atomic)
420 /// Atomic variant of write_scalar_at_offset.
421 fn write_scalar_at_offset_atomic(
425 value: impl Into<ScalarMaybeUninit<Tag>>,
426 layout: TyAndLayout<'tcx>,
427 atomic: AtomicWriteOp,
428 ) -> InterpResult<'tcx> {
429 let this = self.eval_context_mut();
430 let op_place = this.deref_operand(op)?;
431 let offset = Size::from_bytes(offset);
433 // Ensure that the following read at an offset is within bounds.
434 assert!(op_place.layout.size >= offset + layout.size);
435 let value_place = op_place.offset(offset, MemPlaceMeta::None, layout, this)?;
436 this.write_scalar_atomic(value.into(), value_place, atomic)
439 /// Perform an atomic read operation at the memory location.
440 fn read_scalar_atomic(
442 place: MPlaceTy<'tcx, Tag>,
443 atomic: AtomicReadOp,
444 ) -> InterpResult<'tcx, ScalarMaybeUninit<Tag>> {
445 let this = self.eval_context_ref();
446 let scalar = this.allow_data_races_ref(move |this| this.read_scalar(place.into()))?;
447 self.validate_atomic_load(place, atomic)?;
451 /// Perform an atomic write operation at the memory location.
452 fn write_scalar_atomic(
454 val: ScalarMaybeUninit<Tag>,
455 dest: MPlaceTy<'tcx, Tag>,
456 atomic: AtomicWriteOp,
457 ) -> InterpResult<'tcx> {
458 let this = self.eval_context_mut();
459 this.allow_data_races_mut(move |this| this.write_scalar(val, dest.into()))?;
460 self.validate_atomic_store(dest, atomic)
463 /// Perform a atomic operation on a memory location.
464 fn atomic_op_immediate(
466 place: MPlaceTy<'tcx, Tag>,
467 rhs: ImmTy<'tcx, Tag>,
471 ) -> InterpResult<'tcx, ImmTy<'tcx, Tag>> {
472 let this = self.eval_context_mut();
474 let old = this.allow_data_races_mut(|this| this.read_immediate(place.into()))?;
476 // Atomics wrap around on overflow.
477 let val = this.binary_op(op, old, rhs)?;
478 let val = if neg { this.unary_op(mir::UnOp::Not, val)? } else { val };
479 this.allow_data_races_mut(|this| this.write_immediate(*val, place.into()))?;
481 this.validate_atomic_rmw(place, atomic)?;
485 /// Perform an atomic exchange with a memory place and a new
486 /// scalar value, the old value is returned.
487 fn atomic_exchange_scalar(
489 place: MPlaceTy<'tcx, Tag>,
490 new: ScalarMaybeUninit<Tag>,
492 ) -> InterpResult<'tcx, ScalarMaybeUninit<Tag>> {
493 let this = self.eval_context_mut();
495 let old = this.allow_data_races_mut(|this| this.read_scalar(place.into()))?;
496 this.allow_data_races_mut(|this| this.write_scalar(new, place.into()))?;
497 this.validate_atomic_rmw(place, atomic)?;
501 /// Perform an atomic compare and exchange at a given memory location
502 /// on success an atomic RMW operation is performed and on failure
503 /// only an atomic read occurs.
504 fn atomic_compare_exchange_scalar(
506 place: MPlaceTy<'tcx, Tag>,
507 expect_old: ImmTy<'tcx, Tag>,
508 new: ScalarMaybeUninit<Tag>,
511 ) -> InterpResult<'tcx, Immediate<Tag>> {
512 let this = self.eval_context_mut();
514 // Failure ordering cannot be stronger than success ordering, therefore first attempt
515 // to read with the failure ordering and if successfull then try again with the success
516 // read ordering and write in the success case.
517 // Read as immediate for the sake of `binary_op()`
518 let old = this.allow_data_races_mut(|this| this.read_immediate(place.into()))?;
520 // `binary_op` will bail if either of them is not a scalar.
521 let eq = this.overflowing_binary_op(mir::BinOp::Eq, old, expect_old)?.0;
522 let res = Immediate::ScalarPair(old.to_scalar_or_uninit(), eq.into());
524 // Update ptr depending on comparison.
525 // if successful, perform a full rw-atomic validation
526 // otherwise treat this as an atomic load with the fail ordering.
528 this.allow_data_races_mut(|this| this.write_scalar(new, place.into()))?;
529 this.validate_atomic_rmw(place, success)?;
531 this.validate_atomic_load(place, fail)?;
534 // Return the old value.
538 /// Update the data-race detector for an atomic read occuring at the
539 /// associated memory-place and on the current thread.
540 fn validate_atomic_load(
542 place: MPlaceTy<'tcx, Tag>,
543 atomic: AtomicReadOp,
544 ) -> InterpResult<'tcx> {
545 let this = self.eval_context_ref();
546 this.validate_atomic_op(
550 move |memory, clocks, index, atomic| {
551 if atomic == AtomicReadOp::Relaxed {
552 memory.load_relaxed(&mut *clocks, index)
554 memory.load_acquire(&mut *clocks, index)
560 /// Update the data-race detector for an atomic write occuring at the
561 /// associated memory-place and on the current thread.
562 fn validate_atomic_store(
564 place: MPlaceTy<'tcx, Tag>,
565 atomic: AtomicWriteOp,
566 ) -> InterpResult<'tcx> {
567 let this = self.eval_context_ref();
568 this.validate_atomic_op(
572 move |memory, clocks, index, atomic| {
573 if atomic == AtomicWriteOp::Relaxed {
574 memory.store_relaxed(clocks, index)
576 memory.store_release(clocks, index)
582 /// Update the data-race detector for an atomic read-modify-write occuring
583 /// at the associated memory place and on the current thread.
584 fn validate_atomic_rmw(
586 place: MPlaceTy<'tcx, Tag>,
588 ) -> InterpResult<'tcx> {
590 let acquire = matches!(atomic, Acquire | AcqRel | SeqCst);
591 let release = matches!(atomic, Release | AcqRel | SeqCst);
592 let this = self.eval_context_ref();
593 this.validate_atomic_op(place, atomic, "Atomic RMW", move |memory, clocks, index, _| {
595 memory.load_acquire(clocks, index)?;
597 memory.load_relaxed(clocks, index)?;
600 memory.rmw_release(clocks, index)
602 memory.rmw_relaxed(clocks, index)
607 /// Update the data-race detector for an atomic fence on the current thread.
608 fn validate_atomic_fence(&mut self, atomic: AtomicFenceOp) -> InterpResult<'tcx> {
609 let this = self.eval_context_mut();
610 if let Some(data_race) = &this.memory.extra.data_race {
611 data_race.maybe_perform_sync_operation(move |index, mut clocks| {
612 log::trace!("Atomic fence on {:?} with ordering {:?}", index, atomic);
614 // Apply data-race detection for the current fences
615 // this treats AcqRel and SeqCst as the same as a acquire
616 // and release fence applied in the same timestamp.
617 if atomic != AtomicFenceOp::Release {
618 // Either Acquire | AcqRel | SeqCst
619 clocks.apply_acquire_fence();
621 if atomic != AtomicFenceOp::Acquire {
622 // Either Release | AcqRel | SeqCst
623 clocks.apply_release_fence();
633 /// Vector clock metadata for a logical memory allocation.
634 #[derive(Debug, Clone)]
635 pub struct VClockAlloc {
636 /// Range of Vector clocks, this gives each byte a potentially
637 /// unqiue set of vector clocks, but merges identical information
638 /// together for improved efficiency.
639 alloc_ranges: RefCell<RangeMap<MemoryCellClocks>>,
641 // Pointer to global state.
646 /// Create a new data-race allocation detector.
647 pub fn new_allocation(global: &MemoryExtra, len: Size) -> VClockAlloc {
649 global: Rc::clone(global),
650 alloc_ranges: RefCell::new(RangeMap::new(len, MemoryCellClocks::default())),
654 // Find an index, if one exists where the value
655 // in `l` is greater than the value in `r`.
656 fn find_gt_index(l: &VClock, r: &VClock) -> Option<VectorIdx> {
657 let l_slice = l.as_slice();
658 let r_slice = r.as_slice();
663 .find_map(|(idx, (&l, &r))| if l > r { Some(idx) } else { None })
665 if l_slice.len() > r_slice.len() {
666 // By invariant, if l_slice is longer
667 // then one element must be larger.
668 // This just validates that this is true
669 // and reports earlier elements first.
670 let l_remainder_slice = &l_slice[r_slice.len()..];
671 let idx = l_remainder_slice
674 .find_map(|(idx, &r)| if r == 0 { None } else { Some(idx) })
675 .expect("Invalid VClock Invariant");
681 .map(|idx| VectorIdx::new(idx))
684 /// Report a data-race found in the program.
685 /// This finds the two racing threads and the type
686 /// of data-race that occured. This will also
687 /// return info about the memory location the data-race
691 fn report_data_race<'tcx>(
692 global: &MemoryExtra,
693 range: &MemoryCellClocks,
696 pointer: Pointer<Tag>,
698 ) -> InterpResult<'tcx> {
699 let (current_index, current_clocks) = global.current_thread_state();
701 let (other_action, other_thread, other_clock) = if range.write
702 > current_clocks.clock[range.write_index]
704 // Convert the write action into the vector clock it
705 // represents for diagnostic purposes.
706 write_clock = VClock::new_with_index(range.write_index, range.write);
707 ("WRITE", range.write_index, &write_clock)
708 } else if let Some(idx) = Self::find_gt_index(&range.read, ¤t_clocks.clock) {
709 ("READ", idx, &range.read)
710 } else if !is_atomic {
711 if let Some(atomic) = range.atomic() {
712 if let Some(idx) = Self::find_gt_index(&atomic.write_vector, ¤t_clocks.clock)
714 ("ATOMIC_STORE", idx, &atomic.write_vector)
715 } else if let Some(idx) =
716 Self::find_gt_index(&atomic.read_vector, ¤t_clocks.clock)
718 ("ATOMIC_LOAD", idx, &atomic.read_vector)
721 "Failed to report data-race for non-atomic operation: no race found"
726 "Failed to report data-race for non-atomic operation: no atomic component"
730 unreachable!("Failed to report data-race for atomic operation")
733 // Load elaborated thread information about the racing thread actions.
734 let current_thread_info = global.print_thread_metadata(current_index);
735 let other_thread_info = global.print_thread_metadata(other_thread);
737 // Throw the data-race detection.
739 "Data race detected between {} on {} and {} on {}, memory({:?},offset={},size={})\
740 \n\t\t -current vector clock = {:?}\
741 \n\t\t -conflicting timestamp = {:?}",
747 pointer.offset.bytes(),
749 current_clocks.clock,
754 /// Detect data-races for an unsychronized read operation, will not perform
755 /// data-race detection if `multi-threaded` is false, either due to no threads
756 /// being created or if it is temporarily disabled during a racy read or write
757 /// operation for which data-race detection is handled separately, for example
758 /// atomic read operations.
759 pub fn read<'tcx>(&self, pointer: Pointer<Tag>, len: Size) -> InterpResult<'tcx> {
760 if self.global.multi_threaded.get() {
761 let (index, clocks) = self.global.current_thread_state();
762 let mut alloc_ranges = self.alloc_ranges.borrow_mut();
763 for (_, range) in alloc_ranges.iter_mut(pointer.offset, len) {
764 if let Err(DataRace) = range.read_race_detect(&*clocks, index) {
766 return Self::report_data_race(
782 // Shared code for detecting data-races on unique access to a section of memory
783 fn unique_access<'tcx>(
785 pointer: Pointer<Tag>,
788 ) -> InterpResult<'tcx> {
789 if self.global.multi_threaded.get() {
790 let (index, clocks) = self.global.current_thread_state();
791 for (_, range) in self.alloc_ranges.get_mut().iter_mut(pointer.offset, len) {
792 if let Err(DataRace) = range.write_race_detect(&*clocks, index) {
794 return Self::report_data_race(
810 /// Detect data-races for an unsychronized write operation, will not perform
811 /// data-race threads if `multi-threaded` is false, either due to no threads
812 /// being created or if it is temporarily disabled during a racy read or write
814 pub fn write<'tcx>(&mut self, pointer: Pointer<Tag>, len: Size) -> InterpResult<'tcx> {
815 self.unique_access(pointer, len, "Write")
818 /// Detect data-races for an unsychronized deallocate operation, will not perform
819 /// data-race threads if `multi-threaded` is false, either due to no threads
820 /// being created or if it is temporarily disabled during a racy read or write
822 pub fn deallocate<'tcx>(&mut self, pointer: Pointer<Tag>, len: Size) -> InterpResult<'tcx> {
823 self.unique_access(pointer, len, "Deallocate")
827 impl<'mir, 'tcx: 'mir> EvalContextPrivExt<'mir, 'tcx> for MiriEvalContext<'mir, 'tcx> {}
828 trait EvalContextPrivExt<'mir, 'tcx: 'mir>: MiriEvalContextExt<'mir, 'tcx> {
829 // Temporarily allow data-races to occur, this should only be
830 // used if either one of the appropiate `validate_atomic` functions
831 // will be called to treat a memory access as atomic or if the memory
832 // being accessed should be treated as internal state, that cannot be
833 // accessed by the interpreted program.
835 fn allow_data_races_ref<R>(&self, op: impl FnOnce(&MiriEvalContext<'mir, 'tcx>) -> R) -> R {
836 let this = self.eval_context_ref();
837 let old = if let Some(data_race) = &this.memory.extra.data_race {
838 data_race.multi_threaded.replace(false)
842 let result = op(this);
843 if let Some(data_race) = &this.memory.extra.data_race {
844 data_race.multi_threaded.set(old);
849 /// Same as `allow_data_races_ref`, this temporarily disables any data-race detection and
850 /// so should only be used for atomic operations or internal state that the program cannot
853 fn allow_data_races_mut<R>(
855 op: impl FnOnce(&mut MiriEvalContext<'mir, 'tcx>) -> R,
857 let this = self.eval_context_mut();
858 let old = if let Some(data_race) = &this.memory.extra.data_race {
859 data_race.multi_threaded.replace(false)
863 let result = op(this);
864 if let Some(data_race) = &this.memory.extra.data_race {
865 data_race.multi_threaded.set(old);
870 /// Generic atomic operation implementation,
871 /// this accesses memory via get_raw instead of
872 /// get_raw_mut, due to issues calling get_raw_mut
873 /// for atomic loads from read-only memory.
874 /// FIXME: is this valid, or should get_raw_mut be used for
875 /// atomic-stores/atomic-rmw?
876 fn validate_atomic_op<A: Debug + Copy>(
878 place: MPlaceTy<'tcx, Tag>,
882 &mut MemoryCellClocks,
886 ) -> Result<(), DataRace>,
887 ) -> InterpResult<'tcx> {
888 let this = self.eval_context_ref();
889 if let Some(data_race) = &this.memory.extra.data_race {
890 if data_race.multi_threaded.get() {
891 // Load and log the atomic operation.
892 let place_ptr = place.ptr.assert_ptr();
893 let size = place.layout.size;
895 &this.memory.get_raw(place_ptr.alloc_id)?.extra.data_race.as_ref().unwrap();
897 "Atomic op({}) with ordering {:?} on memory({:?}, offset={}, size={})",
901 place_ptr.offset.bytes(),
905 // Perform the atomic operation.
906 let data_race = &alloc_meta.global;
907 data_race.maybe_perform_sync_operation(|index, mut clocks| {
909 alloc_meta.alloc_ranges.borrow_mut().iter_mut(place_ptr.offset, size)
911 if let Err(DataRace) = op(range, &mut *clocks, index, atomic) {
913 return VClockAlloc::report_data_race(
926 // Log changes to atomic memory.
927 if log::log_enabled!(log::Level::Trace) {
928 for (_, range) in alloc_meta.alloc_ranges.borrow().iter(place_ptr.offset, size)
931 "Updated atomic memory({:?}, offset={}, size={}) to {:#?}",
932 place.ptr.assert_ptr().alloc_id,
933 place_ptr.offset.bytes(),
945 /// Extra metadata associated with a thread.
946 #[derive(Debug, Clone, Default)]
947 struct ThreadExtraState {
948 /// The current vector index in use by the
949 /// thread currently, this is set to None
950 /// after the vector index has been re-used
951 /// and hence the value will never need to be
952 /// read during data-race reporting.
953 vector_index: Option<VectorIdx>,
955 /// The name of the thread, updated for better
956 /// diagnostics when reporting detected data
958 thread_name: Option<Box<str>>,
960 /// Thread termination vector clock, this
961 /// is set on thread termination and is used
962 /// for joining on threads since the vector_index
963 /// may be re-used when the join operation occurs.
964 termination_vector_clock: Option<VClock>,
967 /// Global data-race detection state, contains the currently
968 /// executing thread as well as the vector-clocks associated
969 /// with each of the threads.
970 #[derive(Debug, Clone)]
971 pub struct GlobalState {
972 /// Set to true once the first additional
973 /// thread has launched, due to the dependency
974 /// between before and after a thread launch.
975 /// Any data-races must be recorded after this
976 /// so concurrent execution can ignore recording
978 multi_threaded: Cell<bool>,
980 /// Mapping of a vector index to a known set of thread
981 /// clocks, this is not directly mapping from a thread id
982 /// since it may refer to multiple threads.
983 vector_clocks: RefCell<IndexVec<VectorIdx, ThreadClockSet>>,
985 /// Mapping of a given vector index to the current thread
986 /// that the execution is representing, this may change
987 /// if a vector index is re-assigned to a new thread.
988 vector_info: RefCell<IndexVec<VectorIdx, ThreadId>>,
990 /// The mapping of a given thread to assocaited thread metadata.
991 thread_info: RefCell<IndexVec<ThreadId, ThreadExtraState>>,
993 /// The current vector index being executed.
994 current_index: Cell<VectorIdx>,
996 /// Potential vector indices that could be re-used on thread creation
997 /// values are inserted here on after the thread has terminated and
998 /// been joined with, and hence may potentially become free
999 /// for use as the index for a new thread.
1000 /// Elements in this set may still require the vector index to
1001 /// report data-races, and can only be re-used after all
1002 /// active vector-clocks catch up with the threads timestamp.
1003 reuse_candidates: RefCell<FxHashSet<VectorIdx>>,
1005 /// Counts the number of threads that are currently active
1006 /// if the number of active threads reduces to 1 and then
1007 /// a join operation occures with the remaining main thread
1008 /// then multi-threaded execution may be disabled.
1009 active_thread_count: Cell<usize>,
1011 /// This contains threads that have terminated, but not yet joined
1012 /// and so cannot become re-use candidates until a join operation
1014 /// The associated vector index will be moved into re-use candidates
1015 /// after the join operation occurs.
1016 terminated_threads: RefCell<FxHashMap<ThreadId, VectorIdx>>,
1020 /// Create a new global state, setup with just thread-id=0
1021 /// advanced to timestamp = 1.
1022 pub fn new() -> Self {
1023 let global_state = GlobalState {
1024 multi_threaded: Cell::new(false),
1025 vector_clocks: RefCell::new(IndexVec::new()),
1026 vector_info: RefCell::new(IndexVec::new()),
1027 thread_info: RefCell::new(IndexVec::new()),
1028 current_index: Cell::new(VectorIdx::new(0)),
1029 active_thread_count: Cell::new(1),
1030 reuse_candidates: RefCell::new(FxHashSet::default()),
1031 terminated_threads: RefCell::new(FxHashMap::default()),
1034 // Setup the main-thread since it is not explicitly created:
1035 // uses vector index and thread-id 0, also the rust runtime gives
1036 // the main-thread a name of "main".
1037 let index = global_state.vector_clocks.borrow_mut().push(ThreadClockSet::default());
1038 global_state.vector_info.borrow_mut().push(ThreadId::new(0));
1039 global_state.thread_info.borrow_mut().push(ThreadExtraState {
1040 vector_index: Some(index),
1041 thread_name: Some("main".to_string().into_boxed_str()),
1042 termination_vector_clock: None,
1048 // Try to find vector index values that can potentially be re-used
1049 // by a new thread instead of a new vector index being created.
1050 fn find_vector_index_reuse_candidate(&self) -> Option<VectorIdx> {
1051 let mut reuse = self.reuse_candidates.borrow_mut();
1052 let vector_clocks = self.vector_clocks.borrow();
1053 let vector_info = self.vector_info.borrow();
1054 let terminated_threads = self.terminated_threads.borrow();
1055 for &candidate in reuse.iter() {
1056 let target_timestamp = vector_clocks[candidate].clock[candidate];
1057 if vector_clocks.iter_enumerated().all(|(clock_idx, clock)| {
1058 // The thread happens before the clock, and hence cannot report
1059 // a data-race with this the candidate index.
1060 let no_data_race = clock.clock[candidate] >= target_timestamp;
1062 // The vector represents a thread that has terminated and hence cannot
1063 // report a data-race with the candidate index.
1064 let thread_id = vector_info[clock_idx];
1065 let vector_terminated =
1066 reuse.contains(&clock_idx) || terminated_threads.contains_key(&thread_id);
1068 // The vector index cannot report a race with the candidate index
1069 // and hence allows the candidate index to be re-used.
1070 no_data_race || vector_terminated
1072 // All vector clocks for each vector index are equal to
1073 // the target timestamp, and the thread is known to have
1074 // terminated, therefore this vector clock index cannot
1075 // report any more data-races.
1076 assert!(reuse.remove(&candidate));
1077 return Some(candidate);
1083 // Hook for thread creation, enabled multi-threaded execution and marks
1084 // the current thread timestamp as happening-before the current thread.
1086 pub fn thread_created(&self, thread: ThreadId) {
1087 let current_index = self.current_index();
1089 // Increment the number of active threads.
1090 let active_threads = self.active_thread_count.get();
1091 self.active_thread_count.set(active_threads + 1);
1093 // Enable multi-threaded execution, there are now two threads
1094 // so data-races are now possible.
1095 self.multi_threaded.set(true);
1097 // Load and setup the associated thread metadata
1098 let mut thread_info = self.thread_info.borrow_mut();
1099 thread_info.ensure_contains_elem(thread, Default::default);
1101 // Assign a vector index for the thread, attempting to re-use an old
1102 // vector index that can no longer report any data-races if possible.
1103 let created_index = if let Some(reuse_index) = self.find_vector_index_reuse_candidate() {
1104 // Now re-configure the re-use candidate, increment the clock
1105 // for the new sync use of the vector.
1106 let mut vector_clocks = self.vector_clocks.borrow_mut();
1107 vector_clocks[reuse_index].increment_clock(reuse_index);
1109 // Locate the old thread the vector was associated with and update
1110 // it to represent the new thread instead.
1111 let mut vector_info = self.vector_info.borrow_mut();
1112 let old_thread = vector_info[reuse_index];
1113 vector_info[reuse_index] = thread;
1115 // Mark the thread the vector index was associated with as no longer
1116 // representing a thread index.
1117 thread_info[old_thread].vector_index = None;
1121 // No vector re-use candidates available, instead create
1122 // a new vector index.
1123 let mut vector_info = self.vector_info.borrow_mut();
1124 vector_info.push(thread)
1127 // Mark the chosen vector index as in use by the thread.
1128 thread_info[thread].vector_index = Some(created_index);
1130 // Create a thread clock set if applicable.
1131 let mut vector_clocks = self.vector_clocks.borrow_mut();
1132 if created_index == vector_clocks.next_index() {
1133 vector_clocks.push(ThreadClockSet::default());
1136 // Now load the two clocks and configure the initial state.
1137 let (current, created) = vector_clocks.pick2_mut(current_index, created_index);
1139 // Advance the current thread before the synchronized operation.
1140 current.increment_clock(current_index);
1142 // Join the created with current, since the current threads
1143 // previous actions happen-before the created thread.
1144 created.join_with(current);
1146 // Advance both threads after the synchronized operation.
1147 current.increment_clock(current_index);
1148 created.increment_clock(created_index);
1151 /// Hook on a thread join to update the implicit happens-before relation
1152 /// between the joined thead and the current thread.
1154 pub fn thread_joined(&self, current_thread: ThreadId, join_thread: ThreadId) {
1155 let mut clocks_vec = self.vector_clocks.borrow_mut();
1156 let thread_info = self.thread_info.borrow();
1158 // Load the vector clock of the current thread.
1159 let current_index = thread_info[current_thread]
1161 .expect("Performed thread join on thread with no assigned vector");
1162 let current = &mut clocks_vec[current_index];
1164 // Load the associated vector clock for the terminated thread.
1165 let join_clock = thread_info[join_thread]
1166 .termination_vector_clock
1168 .expect("Joined with thread but thread has not terminated");
1170 // Pre increment clocks before atomic operation.
1171 current.increment_clock(current_index);
1173 // The join thread happens-before the current thread
1174 // so update the current vector clock.
1175 current.clock.join(join_clock);
1177 // Post increment clocks after atomic operation.
1178 current.increment_clock(current_index);
1180 // Check the number of active threads, if the value is 1
1181 // then test for potentially disabling multi-threaded execution.
1182 let active_threads = self.active_thread_count.get();
1183 if active_threads == 1 {
1184 // May potentially be able to disable multi-threaded execution.
1185 let current_clock = &clocks_vec[current_index];
1188 .all(|(idx, clocks)| clocks.clock[idx] <= current_clock.clock[idx])
1190 // The all thread termations happen-before the current clock
1191 // therefore no data-races can be reported until a new thread
1192 // is created, so disable multi-threaded execution.
1193 self.multi_threaded.set(false);
1197 // If the thread is marked as terminated but not joined
1198 // then move the thread to the re-use set.
1199 let mut termination = self.terminated_threads.borrow_mut();
1200 if let Some(index) = termination.remove(&join_thread) {
1201 let mut reuse = self.reuse_candidates.borrow_mut();
1202 reuse.insert(index);
1206 /// On thread termination, the vector-clock may re-used
1207 /// in the future once all remaining thread-clocks catch
1208 /// up with the time index of the terminated thread.
1209 /// This assiges thread termination with a unique index
1210 /// which will be used to join the thread
1211 /// This should be called strictly before any calls to
1212 /// `thread_joined`.
1214 pub fn thread_terminated(&self) {
1215 let current_index = self.current_index();
1217 // Increment the clock to a unique termination timestamp.
1218 let mut vector_clocks = self.vector_clocks.borrow_mut();
1219 let current_clocks = &mut vector_clocks[current_index];
1220 current_clocks.increment_clock(current_index);
1222 // Load the current thread id for the executing vector.
1223 let vector_info = self.vector_info.borrow();
1224 let current_thread = vector_info[current_index];
1226 // Load the current thread metadata, and move to a terminated
1227 // vector state. Setting up the vector clock all join operations
1229 let mut thread_info = self.thread_info.borrow_mut();
1230 let current = &mut thread_info[current_thread];
1231 current.termination_vector_clock = Some(current_clocks.clock.clone());
1233 // Add this thread as a candidate for re-use after a thread join
1235 let mut termination = self.terminated_threads.borrow_mut();
1236 termination.insert(current_thread, current_index);
1238 // Reduce the number of active threads, now that a thread has
1240 let mut active_threads = self.active_thread_count.get();
1241 active_threads -= 1;
1242 self.active_thread_count.set(active_threads);
1245 /// Hook for updating the local tracker of the currently
1246 /// enabled thread, should always be updated whenever
1247 /// `active_thread` in thread.rs is updated.
1249 pub fn thread_set_active(&self, thread: ThreadId) {
1250 let thread_info = self.thread_info.borrow();
1251 let vector_idx = thread_info[thread]
1253 .expect("Setting thread active with no assigned vector");
1254 self.current_index.set(vector_idx);
1257 /// Hook for updating the local tracker of the threads name
1258 /// this should always mirror the local value in thread.rs
1259 /// the thread name is used for improved diagnostics
1260 /// during a data-race.
1262 pub fn thread_set_name(&self, thread: ThreadId, name: String) {
1263 let name = name.into_boxed_str();
1264 let mut thread_info = self.thread_info.borrow_mut();
1265 thread_info[thread].thread_name = Some(name);
1268 /// Attempt to perform a synchronized operation, this
1269 /// will perform no operation if multi-threading is
1270 /// not currently enabled.
1271 /// Otherwise it will increment the clock for the current
1272 /// vector before and after the operation for data-race
1273 /// detection between any happens-before edges the
1274 /// operation may create.
1275 fn maybe_perform_sync_operation<'tcx>(
1277 op: impl FnOnce(VectorIdx, RefMut<'_, ThreadClockSet>) -> InterpResult<'tcx>,
1278 ) -> InterpResult<'tcx> {
1279 if self.multi_threaded.get() {
1280 let (index, mut clocks) = self.current_thread_state_mut();
1281 clocks.increment_clock(index);
1283 let (_, mut clocks) = self.current_thread_state_mut();
1284 clocks.increment_clock(index);
1289 /// Internal utility to identify a thread stored internally
1290 /// returns the id and the name for better diagnostics.
1291 fn print_thread_metadata(&self, vector: VectorIdx) -> String {
1292 let thread = self.vector_info.borrow()[vector];
1293 let thread_name = &self.thread_info.borrow()[thread].thread_name;
1294 if let Some(name) = thread_name {
1295 let name: &str = name;
1296 format!("Thread(id = {:?}, name = {:?})", thread.to_u32(), &*name)
1298 format!("Thread(id = {:?})", thread.to_u32())
1302 /// Acquire a lock, express that the previous call of
1303 /// `validate_lock_release` must happen before this.
1304 pub fn validate_lock_acquire(&self, lock: &VClock, thread: ThreadId) {
1305 let (index, mut clocks) = self.load_thread_state_mut(thread);
1306 clocks.increment_clock(index);
1307 clocks.clock.join(&lock);
1308 clocks.increment_clock(index);
1311 /// Release a lock handle, express that this happens-before
1312 /// any subsequent calls to `validate_lock_acquire`.
1313 pub fn validate_lock_release(&self, lock: &mut VClock, thread: ThreadId) {
1314 let (index, mut clocks) = self.load_thread_state_mut(thread);
1315 clocks.increment_clock(index);
1316 lock.clone_from(&clocks.clock);
1317 clocks.increment_clock(index);
1320 /// Release a lock handle, express that this happens-before
1321 /// any subsequent calls to `validate_lock_acquire` as well
1322 /// as any previous calls to this function after any
1323 /// `validate_lock_release` calls.
1324 pub fn validate_lock_release_shared(&self, lock: &mut VClock, thread: ThreadId) {
1325 let (index, mut clocks) = self.load_thread_state_mut(thread);
1326 clocks.increment_clock(index);
1327 lock.join(&clocks.clock);
1328 clocks.increment_clock(index);
1331 /// Load the vector index used by the given thread as well as the set of vector clocks
1332 /// used by the thread.
1334 fn load_thread_state_mut(&self, thread: ThreadId) -> (VectorIdx, RefMut<'_, ThreadClockSet>) {
1335 let index = self.thread_info.borrow()[thread]
1337 .expect("Loading thread state for thread with no assigned vector");
1338 let ref_vector = self.vector_clocks.borrow_mut();
1339 let clocks = RefMut::map(ref_vector, |vec| &mut vec[index]);
1343 /// Load the current vector clock in use and the current set of thread clocks
1344 /// in use for the vector.
1346 fn current_thread_state(&self) -> (VectorIdx, Ref<'_, ThreadClockSet>) {
1347 let index = self.current_index();
1348 let ref_vector = self.vector_clocks.borrow();
1349 let clocks = Ref::map(ref_vector, |vec| &vec[index]);
1353 /// Load the current vector clock in use and the current set of thread clocks
1354 /// in use for the vector mutably for modification.
1356 fn current_thread_state_mut(&self) -> (VectorIdx, RefMut<'_, ThreadClockSet>) {
1357 let index = self.current_index();
1358 let ref_vector = self.vector_clocks.borrow_mut();
1359 let clocks = RefMut::map(ref_vector, |vec| &mut vec[index]);
1363 /// Return the current thread, should be the same
1364 /// as the data-race active thread.
1366 fn current_index(&self) -> VectorIdx {
1367 self.current_index.get()