1 //! Implementation of a data-race detector using Lamport Timestamps / Vector-clocks
2 //! based on the Dynamic 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 //! The implementation contains modifications to correctly model the changes to the memory model in C++20
8 //! regarding the weakening of release sequences: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0982r1.html.
9 //! Relaxed stores now unconditionally block all currently active release sequences and so per-thread tracking of release
10 //! sequences is not needed.
12 //! This does not explore weak memory orders and so can still miss data-races
13 //! but should not report false-positives
15 //! Data-race definition from(https://en.cppreference.com/w/cpp/language/memory_model#Threads_and_data_races):
16 //! a data race occurs between two memory accesses if they are on different threads, at least one operation
17 //! is non-atomic, at least one operation is a write and neither access happens-before the other. Read the link
18 //! for full definition.
20 //! This re-uses vector indexes for threads that are known to be unable to report data-races, this is valid
21 //! because it only re-uses vector indexes once all currently-active (not-terminated) threads have an internal
22 //! vector clock that happens-after the join operation of the candidate thread. Threads that have not been joined
23 //! on are not considered. Since the thread's vector clock will only increase and a data-race implies that
24 //! there is some index x where clock[x] > thread_clock, when this is true clock[candidate-idx] > thread_clock
25 //! can never hold and hence a data-race can never be reported in that vector index again.
26 //! This means that the thread-index can be safely re-used, starting on the next timestamp for the newly created
29 //! The sequentially consistent ordering corresponds to the ordering that the threads
30 //! are currently scheduled, this means that the data-race detector has no additional
31 //! logic for sequentially consistent accesses at the moment since they are indistinguishable
32 //! from acquire/release operations. If weak memory orderings are explored then this
33 //! may need to change or be updated accordingly.
35 //! Per the C++ spec for the memory model a sequentially consistent operation:
36 //! "A load operation with this memory order performs an acquire operation,
37 //! a store performs a release operation, and read-modify-write performs
38 //! both an acquire operation and a release operation, plus a single total
39 //! order exists in which all threads observe all modifications in the same
40 //! order (see Sequentially-consistent ordering below) "
41 //! So in the absence of weak memory effects a seq-cst load & a seq-cst store is identical
42 //! to a acquire load and a release store given the global sequentially consistent order
45 //! The timestamps used in the data-race detector assign each sequence of non-atomic operations
46 //! followed by a single atomic or concurrent operation a single timestamp.
47 //! Write, Read, Write, ThreadJoin will be represented by a single timestamp value on a thread.
48 //! This is because extra increment operations between the operations in the sequence are not
49 //! required for accurate reporting of data-race values.
51 //! As per the paper a threads timestamp is only incremented after a release operation is performed
52 //! so some atomic operations that only perform acquires do not increment the timestamp. Due to shared
53 //! code some atomic operations may increment the timestamp when not necessary but this has no effect
54 //! on the data-race detection code.
57 //! currently we have our own local copy of the currently active thread index and names, this is due
58 //! in part to the inability to access the current location of threads.active_thread inside the AllocExtra
59 //! read, write and deallocate functions and should be cleaned up in the future.
62 cell::{Cell, Ref, RefCell, RefMut},
68 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
69 use rustc_index::vec::{Idx, IndexVec};
70 use rustc_middle::{mir, ty::layout::TyAndLayout};
71 use rustc_target::abi::Size;
74 ImmTy, Immediate, InterpResult, MPlaceTy, MemPlaceMeta, MiriEvalContext, MiriEvalContextExt,
75 OpTy, Pointer, RangeMap, ScalarMaybeUninit, Tag, ThreadId, VClock, VTimestamp,
79 pub type AllocExtra = VClockAlloc;
80 pub type MemoryExtra = Rc<GlobalState>;
82 /// Valid atomic read-write operations, alias of atomic::Ordering (not non-exhaustive).
83 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
92 /// Valid atomic read operations, subset of atomic::Ordering.
93 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
94 pub enum AtomicReadOp {
100 /// Valid atomic write operations, subset of atomic::Ordering.
101 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
102 pub enum AtomicWriteOp {
108 /// Valid atomic fence operations, subset of atomic::Ordering.
109 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
110 pub enum AtomicFenceOp {
117 /// The current set of vector clocks describing the state
118 /// of a thread, contains the happens-before clock and
119 /// additional metadata to model atomic fence operations.
120 #[derive(Clone, Default, Debug)]
121 struct ThreadClockSet {
122 /// The increasing clock representing timestamps
123 /// that happen-before this thread.
126 /// The set of timestamps that will happen-before this
127 /// thread once it performs an acquire fence.
128 fence_acquire: VClock,
130 /// The last timestamp of happens-before relations that
131 /// have been released by this thread by a fence.
132 fence_release: VClock,
135 impl ThreadClockSet {
136 /// Apply the effects of a release fence to this
137 /// set of thread vector clocks.
139 fn apply_release_fence(&mut self) {
140 self.fence_release.clone_from(&self.clock);
143 /// Apply the effects of a acquire fence to this
144 /// set of thread vector clocks.
146 fn apply_acquire_fence(&mut self) {
147 self.clock.join(&self.fence_acquire);
150 /// Increment the happens-before clock at a
153 fn increment_clock(&mut self, index: VectorIdx) {
154 self.clock.increment_index(index);
157 /// Join the happens-before clock with that of
158 /// another thread, used to model thread join
160 fn join_with(&mut self, other: &ThreadClockSet) {
161 self.clock.join(&other.clock);
165 /// Error returned by finding a data race
166 /// should be elaborated upon.
167 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
170 /// Externally stored memory cell clocks
171 /// explicitly to reduce memory usage for the
172 /// common case where no atomic operations
173 /// exists on the memory cell.
174 #[derive(Clone, PartialEq, Eq, Default, Debug)]
175 struct AtomicMemoryCellClocks {
176 /// The clock-vector of the timestamp of the last atomic
177 /// read operation performed by each thread.
178 /// This detects potential data-races between atomic read
179 /// and non-atomic write operations.
182 /// The clock-vector of the timestamp of the last atomic
183 /// write operation performed by each thread.
184 /// This detects potential data-races between atomic write
185 /// and non-atomic read or write operations.
186 write_vector: VClock,
188 /// Synchronization vector for acquire-release semantics
189 /// contains the vector of timestamps that will
190 /// happen-before a thread if an acquire-load is
191 /// performed on the data.
195 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
199 /// Standard unsynchronized write.
201 /// Deallocate memory
205 fn get_descriptor(self) -> &'static str {
207 WriteType::Allocate => "ALLOCATE",
208 WriteType::Write => "WRITE",
209 WriteType::Deallocate => "DEALLOCATE",
214 /// Memory Cell vector clock metadata
215 /// for data-race detection.
216 #[derive(Clone, PartialEq, Eq, Debug)]
217 struct MemoryCellClocks {
218 /// The vector-clock timestamp of the last write
219 /// corresponding to the writing threads timestamp.
222 /// The identifier of the vector index, corresponding to a thread
223 /// that performed the last write operation.
224 write_index: VectorIdx,
226 /// The type of operation that the write index represents,
227 /// either newly allocated memory, a non-atomic write or
228 /// a deallocation of memory.
229 write_type: WriteType,
231 /// The vector-clock of the timestamp of the last read operation
232 /// performed by a thread since the last write operation occurred.
233 /// It is reset to zero on each write operation.
236 /// Atomic acquire & release sequence tracking clocks.
237 /// For non-atomic memory in the common case this
238 /// value is set to None.
239 atomic_ops: Option<Box<AtomicMemoryCellClocks>>,
242 impl MemoryCellClocks {
244 /// Create a new set of clocks representing memory allocated
245 /// at a given vector timestamp and index.
246 fn new(alloc: VTimestamp, alloc_index: VectorIdx) -> Self {
248 read: VClock::default(),
250 write_index: alloc_index,
251 write_type: WriteType::Allocate,
256 /// Load the internal atomic memory cells if they exist.
258 fn atomic(&self) -> Option<&AtomicMemoryCellClocks> {
259 match &self.atomic_ops {
260 Some(op) => Some(&*op),
265 /// Load or create the internal atomic memory metadata
266 /// if it does not exist.
268 fn atomic_mut(&mut self) -> &mut AtomicMemoryCellClocks {
269 self.atomic_ops.get_or_insert_with(Default::default)
272 /// Update memory cell data-race tracking for atomic
273 /// load acquire semantics, is a no-op if this memory was
274 /// not used previously as atomic memory.
277 clocks: &mut ThreadClockSet,
279 ) -> Result<(), DataRace> {
280 self.atomic_read_detect(clocks, index)?;
281 if let Some(atomic) = self.atomic() {
282 clocks.clock.join(&atomic.sync_vector);
287 /// Update memory cell data-race tracking for atomic
288 /// load relaxed semantics, is a no-op if this memory was
289 /// not used previously as atomic memory.
292 clocks: &mut ThreadClockSet,
294 ) -> Result<(), DataRace> {
295 self.atomic_read_detect(clocks, index)?;
296 if let Some(atomic) = self.atomic() {
297 clocks.fence_acquire.join(&atomic.sync_vector);
302 /// Update the memory cell data-race tracking for atomic
303 /// store release semantics.
304 fn store_release(&mut self, clocks: &ThreadClockSet, index: VectorIdx) -> Result<(), DataRace> {
305 self.atomic_write_detect(clocks, index)?;
306 let atomic = self.atomic_mut();
307 atomic.sync_vector.clone_from(&clocks.clock);
311 /// Update the memory cell data-race tracking for atomic
312 /// store relaxed semantics.
313 fn store_relaxed(&mut self, clocks: &ThreadClockSet, index: VectorIdx) -> Result<(), DataRace> {
314 self.atomic_write_detect(clocks, index)?;
316 // The handling of release sequences was changed in C++20 and so
317 // the code here is different to the paper since now all relaxed
318 // stores block release sequences. The exception for same-thread
319 // relaxed stores has been removed.
320 let atomic = self.atomic_mut();
321 atomic.sync_vector.clone_from(&clocks.fence_release);
325 /// Update the memory cell data-race tracking for atomic
326 /// store release semantics for RMW operations.
327 fn rmw_release(&mut self, clocks: &ThreadClockSet, index: VectorIdx) -> Result<(), DataRace> {
328 self.atomic_write_detect(clocks, index)?;
329 let atomic = self.atomic_mut();
330 atomic.sync_vector.join(&clocks.clock);
334 /// Update the memory cell data-race tracking for atomic
335 /// store relaxed semantics for RMW operations.
336 fn rmw_relaxed(&mut self, clocks: &ThreadClockSet, index: VectorIdx) -> Result<(), DataRace> {
337 self.atomic_write_detect(clocks, index)?;
338 let atomic = self.atomic_mut();
339 atomic.sync_vector.join(&clocks.fence_release);
343 /// Detect data-races with an atomic read, caused by a non-atomic write that does
344 /// not happen-before the atomic-read.
345 fn atomic_read_detect(
347 clocks: &ThreadClockSet,
349 ) -> Result<(), DataRace> {
350 log::trace!("Atomic read with vectors: {:#?} :: {:#?}", self, clocks);
351 if self.write <= clocks.clock[self.write_index] {
352 let atomic = self.atomic_mut();
353 atomic.read_vector.set_at_index(&clocks.clock, index);
360 /// Detect data-races with an atomic write, either with a non-atomic read or with
361 /// a non-atomic write.
362 fn atomic_write_detect(
364 clocks: &ThreadClockSet,
366 ) -> Result<(), DataRace> {
367 log::trace!("Atomic write with vectors: {:#?} :: {:#?}", self, clocks);
368 if self.write <= clocks.clock[self.write_index] && self.read <= clocks.clock {
369 let atomic = self.atomic_mut();
370 atomic.write_vector.set_at_index(&clocks.clock, index);
377 /// Detect races for non-atomic read operations at the current memory cell
378 /// returns true if a data-race is detected.
381 clocks: &ThreadClockSet,
383 ) -> Result<(), DataRace> {
384 log::trace!("Unsynchronized read with vectors: {:#?} :: {:#?}", self, clocks);
385 if self.write <= clocks.clock[self.write_index] {
386 let race_free = if let Some(atomic) = self.atomic() {
387 atomic.write_vector <= clocks.clock
392 self.read.set_at_index(&clocks.clock, index);
402 /// Detect races for non-atomic write operations at the current memory cell
403 /// returns true if a data-race is detected.
404 fn write_race_detect(
406 clocks: &ThreadClockSet,
408 write_type: WriteType,
409 ) -> Result<(), DataRace> {
410 log::trace!("Unsynchronized write with vectors: {:#?} :: {:#?}", self, clocks);
411 if self.write <= clocks.clock[self.write_index] && self.read <= clocks.clock {
412 let race_free = if let Some(atomic) = self.atomic() {
413 atomic.write_vector <= clocks.clock && atomic.read_vector <= clocks.clock
418 self.write = clocks.clock[index];
419 self.write_index = index;
420 self.write_type = write_type;
421 self.read.set_zero_vector();
432 /// Evaluation context extensions.
433 impl<'mir, 'tcx: 'mir> EvalContextExt<'mir, 'tcx> for MiriEvalContext<'mir, 'tcx> {}
434 pub trait EvalContextExt<'mir, 'tcx: 'mir>: MiriEvalContextExt<'mir, 'tcx> {
435 /// Atomic variant of read_scalar_at_offset.
436 fn read_scalar_at_offset_atomic(
440 layout: TyAndLayout<'tcx>,
441 atomic: AtomicReadOp,
442 ) -> InterpResult<'tcx, ScalarMaybeUninit<Tag>> {
443 let this = self.eval_context_ref();
444 let op_place = this.deref_operand(op)?;
445 let offset = Size::from_bytes(offset);
447 // Ensure that the following read at an offset is within bounds.
448 assert!(op_place.layout.size >= offset + layout.size);
449 let value_place = op_place.offset(offset, MemPlaceMeta::None, layout, this)?;
450 this.read_scalar_atomic(value_place, atomic)
453 /// Atomic variant of write_scalar_at_offset.
454 fn write_scalar_at_offset_atomic(
458 value: impl Into<ScalarMaybeUninit<Tag>>,
459 layout: TyAndLayout<'tcx>,
460 atomic: AtomicWriteOp,
461 ) -> InterpResult<'tcx> {
462 let this = self.eval_context_mut();
463 let op_place = this.deref_operand(op)?;
464 let offset = Size::from_bytes(offset);
466 // Ensure that the following read at an offset is within bounds.
467 assert!(op_place.layout.size >= offset + layout.size);
468 let value_place = op_place.offset(offset, MemPlaceMeta::None, layout, this)?;
469 this.write_scalar_atomic(value.into(), value_place, atomic)
472 /// Perform an atomic read operation at the memory location.
473 fn read_scalar_atomic(
475 place: MPlaceTy<'tcx, Tag>,
476 atomic: AtomicReadOp,
477 ) -> InterpResult<'tcx, ScalarMaybeUninit<Tag>> {
478 let this = self.eval_context_ref();
479 let scalar = this.allow_data_races_ref(move |this| this.read_scalar(place.into()))?;
480 self.validate_atomic_load(place, atomic)?;
484 /// Perform an atomic write operation at the memory location.
485 fn write_scalar_atomic(
487 val: ScalarMaybeUninit<Tag>,
488 dest: MPlaceTy<'tcx, Tag>,
489 atomic: AtomicWriteOp,
490 ) -> InterpResult<'tcx> {
491 let this = self.eval_context_mut();
492 this.allow_data_races_mut(move |this| this.write_scalar(val, dest.into()))?;
493 self.validate_atomic_store(dest, atomic)
496 /// Perform a atomic operation on a memory location.
497 fn atomic_op_immediate(
499 place: MPlaceTy<'tcx, Tag>,
500 rhs: ImmTy<'tcx, Tag>,
504 ) -> InterpResult<'tcx, ImmTy<'tcx, Tag>> {
505 let this = self.eval_context_mut();
507 let old = this.allow_data_races_mut(|this| this.read_immediate(place.into()))?;
509 // Atomics wrap around on overflow.
510 let val = this.binary_op(op, old, rhs)?;
511 let val = if neg { this.unary_op(mir::UnOp::Not, val)? } else { val };
512 this.allow_data_races_mut(|this| this.write_immediate(*val, place.into()))?;
514 this.validate_atomic_rmw(place, atomic)?;
518 /// Perform an atomic exchange with a memory place and a new
519 /// scalar value, the old value is returned.
520 fn atomic_exchange_scalar(
522 place: MPlaceTy<'tcx, Tag>,
523 new: ScalarMaybeUninit<Tag>,
525 ) -> InterpResult<'tcx, ScalarMaybeUninit<Tag>> {
526 let this = self.eval_context_mut();
528 let old = this.allow_data_races_mut(|this| this.read_scalar(place.into()))?;
529 this.allow_data_races_mut(|this| this.write_scalar(new, place.into()))?;
530 this.validate_atomic_rmw(place, atomic)?;
534 /// Perform an atomic compare and exchange at a given memory location.
535 /// On success an atomic RMW operation is performed and on failure
536 /// only an atomic read occurs.
537 fn atomic_compare_exchange_scalar(
539 place: MPlaceTy<'tcx, Tag>,
540 expect_old: ImmTy<'tcx, Tag>,
541 new: ScalarMaybeUninit<Tag>,
544 ) -> InterpResult<'tcx, Immediate<Tag>> {
545 let this = self.eval_context_mut();
547 // Failure ordering cannot be stronger than success ordering, therefore first attempt
548 // to read with the failure ordering and if successful then try again with the success
549 // read ordering and write in the success case.
550 // Read as immediate for the sake of `binary_op()`
551 let old = this.allow_data_races_mut(|this| this.read_immediate(place.into()))?;
553 // `binary_op` will bail if either of them is not a scalar.
554 let eq = this.overflowing_binary_op(mir::BinOp::Eq, old, expect_old)?.0;
555 let res = Immediate::ScalarPair(old.to_scalar_or_uninit(), eq.into());
557 // Update ptr depending on comparison.
558 // if successful, perform a full rw-atomic validation
559 // otherwise treat this as an atomic load with the fail ordering.
561 this.allow_data_races_mut(|this| this.write_scalar(new, place.into()))?;
562 this.validate_atomic_rmw(place, success)?;
564 this.validate_atomic_load(place, fail)?;
567 // Return the old value.
571 /// Update the data-race detector for an atomic read occurring at the
572 /// associated memory-place and on the current thread.
573 fn validate_atomic_load(
575 place: MPlaceTy<'tcx, Tag>,
576 atomic: AtomicReadOp,
577 ) -> InterpResult<'tcx> {
578 let this = self.eval_context_ref();
579 this.validate_atomic_op(
583 move |memory, clocks, index, atomic| {
584 if atomic == AtomicReadOp::Relaxed {
585 memory.load_relaxed(&mut *clocks, index)
587 memory.load_acquire(&mut *clocks, index)
593 /// Update the data-race detector for an atomic write occurring at the
594 /// associated memory-place and on the current thread.
595 fn validate_atomic_store(
597 place: MPlaceTy<'tcx, Tag>,
598 atomic: AtomicWriteOp,
599 ) -> InterpResult<'tcx> {
600 let this = self.eval_context_ref();
601 this.validate_atomic_op(
605 move |memory, clocks, index, atomic| {
606 if atomic == AtomicWriteOp::Relaxed {
607 memory.store_relaxed(clocks, index)
609 memory.store_release(clocks, index)
615 /// Update the data-race detector for an atomic read-modify-write occurring
616 /// at the associated memory place and on the current thread.
617 fn validate_atomic_rmw(
619 place: MPlaceTy<'tcx, Tag>,
621 ) -> InterpResult<'tcx> {
623 let acquire = matches!(atomic, Acquire | AcqRel | SeqCst);
624 let release = matches!(atomic, Release | AcqRel | SeqCst);
625 let this = self.eval_context_ref();
626 this.validate_atomic_op(place, atomic, "Atomic RMW", move |memory, clocks, index, _| {
628 memory.load_acquire(clocks, index)?;
630 memory.load_relaxed(clocks, index)?;
633 memory.rmw_release(clocks, index)
635 memory.rmw_relaxed(clocks, index)
640 /// Update the data-race detector for an atomic fence on the current thread.
641 fn validate_atomic_fence(&mut self, atomic: AtomicFenceOp) -> InterpResult<'tcx> {
642 let this = self.eval_context_mut();
643 if let Some(data_race) = &this.memory.extra.data_race {
644 data_race.maybe_perform_sync_operation(move |index, mut clocks| {
645 log::trace!("Atomic fence on {:?} with ordering {:?}", index, atomic);
647 // Apply data-race detection for the current fences
648 // this treats AcqRel and SeqCst as the same as a acquire
649 // and release fence applied in the same timestamp.
650 if atomic != AtomicFenceOp::Release {
651 // Either Acquire | AcqRel | SeqCst
652 clocks.apply_acquire_fence();
654 if atomic != AtomicFenceOp::Acquire {
655 // Either Release | AcqRel | SeqCst
656 clocks.apply_release_fence();
659 // Increment timestamp in case of release semantics.
660 Ok(atomic != AtomicFenceOp::Acquire)
668 /// Vector clock metadata for a logical memory allocation.
669 #[derive(Debug, Clone)]
670 pub struct VClockAlloc {
671 /// Assigning each byte a MemoryCellClocks.
672 alloc_ranges: RefCell<RangeMap<MemoryCellClocks>>,
674 /// Pointer to global state.
680 /// Create a new data-race detector for newly allocated memory.
681 pub fn new_allocation(global: &MemoryExtra, len: Size, track_alloc: bool) -> VClockAlloc {
682 let (alloc_timestamp, alloc_index) = if track_alloc {
683 let (alloc_index, clocks) = global.current_thread_state();
684 let alloc_timestamp = clocks.clock[alloc_index];
685 (alloc_timestamp, alloc_index)
687 (0, VectorIdx::MAX_INDEX)
690 global: Rc::clone(global),
691 alloc_ranges: RefCell::new(RangeMap::new(
692 len, MemoryCellClocks::new(alloc_timestamp, alloc_index)
697 // Find an index, if one exists where the value
698 // in `l` is greater than the value in `r`.
699 fn find_gt_index(l: &VClock, r: &VClock) -> Option<VectorIdx> {
700 let l_slice = l.as_slice();
701 let r_slice = r.as_slice();
706 .find_map(|(idx, (&l, &r))| if l > r { Some(idx) } else { None })
708 if l_slice.len() > r_slice.len() {
709 // By invariant, if l_slice is longer
710 // then one element must be larger.
711 // This just validates that this is true
712 // and reports earlier elements first.
713 let l_remainder_slice = &l_slice[r_slice.len()..];
714 let idx = l_remainder_slice
717 .find_map(|(idx, &r)| if r == 0 { None } else { Some(idx) })
718 .expect("Invalid VClock Invariant");
724 .map(|idx| VectorIdx::new(idx))
727 /// Report a data-race found in the program.
728 /// This finds the two racing threads and the type
729 /// of data-race that occurred. This will also
730 /// return info about the memory location the data-race
734 fn report_data_race<'tcx>(
735 global: &MemoryExtra,
736 range: &MemoryCellClocks,
739 pointer: Pointer<Tag>,
741 ) -> InterpResult<'tcx> {
742 let (current_index, current_clocks) = global.current_thread_state();
744 let (other_action, other_thread, other_clock) = if range.write
745 > current_clocks.clock[range.write_index]
747 // Convert the write action into the vector clock it
748 // represents for diagnostic purposes.
749 write_clock = VClock::new_with_index(range.write_index, range.write);
750 (range.write_type.get_descriptor(), range.write_index, &write_clock)
751 } else if let Some(idx) = Self::find_gt_index(&range.read, ¤t_clocks.clock) {
752 ("READ", idx, &range.read)
753 } else if !is_atomic {
754 if let Some(atomic) = range.atomic() {
755 if let Some(idx) = Self::find_gt_index(&atomic.write_vector, ¤t_clocks.clock)
757 ("ATOMIC_STORE", idx, &atomic.write_vector)
758 } else if let Some(idx) =
759 Self::find_gt_index(&atomic.read_vector, ¤t_clocks.clock)
761 ("ATOMIC_LOAD", idx, &atomic.read_vector)
764 "Failed to report data-race for non-atomic operation: no race found"
769 "Failed to report data-race for non-atomic operation: no atomic component"
773 unreachable!("Failed to report data-race for atomic operation")
776 // Load elaborated thread information about the racing thread actions.
777 let current_thread_info = global.print_thread_metadata(current_index);
778 let other_thread_info = global.print_thread_metadata(other_thread);
780 // Throw the data-race detection.
782 "Data race detected between {} on {} and {} on {}, memory({:?},offset={},size={})\
783 \n\t\t -current vector clock = {:?}\
784 \n\t\t -conflicting timestamp = {:?}",
790 pointer.offset.bytes(),
792 current_clocks.clock,
797 /// Detect data-races for an unsynchronized read operation, will not perform
798 /// data-race detection if `multi-threaded` is false, either due to no threads
799 /// being created or if it is temporarily disabled during a racy read or write
800 /// operation for which data-race detection is handled separately, for example
801 /// atomic read operations.
802 pub fn read<'tcx>(&self, pointer: Pointer<Tag>, len: Size) -> InterpResult<'tcx> {
803 if self.global.multi_threaded.get() {
804 let (index, clocks) = self.global.current_thread_state();
805 let mut alloc_ranges = self.alloc_ranges.borrow_mut();
806 for (_, range) in alloc_ranges.iter_mut(pointer.offset, len) {
807 if let Err(DataRace) = range.read_race_detect(&*clocks, index) {
809 return Self::report_data_race(
825 // Shared code for detecting data-races on unique access to a section of memory
826 fn unique_access<'tcx>(
828 pointer: Pointer<Tag>,
830 write_type: WriteType,
831 ) -> InterpResult<'tcx> {
832 if self.global.multi_threaded.get() {
833 let (index, clocks) = self.global.current_thread_state();
834 for (_, range) in self.alloc_ranges.get_mut().iter_mut(pointer.offset, len) {
835 if let Err(DataRace) = range.write_race_detect(&*clocks, index, write_type) {
837 return Self::report_data_race(
840 write_type.get_descriptor(),
853 /// Detect data-races for an unsynchronized write operation, will not perform
854 /// data-race threads if `multi-threaded` is false, either due to no threads
855 /// being created or if it is temporarily disabled during a racy read or write
857 pub fn write<'tcx>(&mut self, pointer: Pointer<Tag>, len: Size) -> InterpResult<'tcx> {
858 self.unique_access(pointer, len, WriteType::Write)
861 /// Detect data-races for an unsynchronized deallocate operation, will not perform
862 /// data-race threads if `multi-threaded` is false, either due to no threads
863 /// being created or if it is temporarily disabled during a racy read or write
865 pub fn deallocate<'tcx>(&mut self, pointer: Pointer<Tag>, len: Size) -> InterpResult<'tcx> {
866 self.unique_access(pointer, len, WriteType::Deallocate)
870 impl<'mir, 'tcx: 'mir> EvalContextPrivExt<'mir, 'tcx> for MiriEvalContext<'mir, 'tcx> {}
871 trait EvalContextPrivExt<'mir, 'tcx: 'mir>: MiriEvalContextExt<'mir, 'tcx> {
872 // Temporarily allow data-races to occur, this should only be
873 // used if either one of the appropriate `validate_atomic` functions
874 // will be called to treat a memory access as atomic or if the memory
875 // being accessed should be treated as internal state, that cannot be
876 // accessed by the interpreted program.
878 fn allow_data_races_ref<R>(&self, op: impl FnOnce(&MiriEvalContext<'mir, 'tcx>) -> R) -> R {
879 let this = self.eval_context_ref();
880 let old = if let Some(data_race) = &this.memory.extra.data_race {
881 data_race.multi_threaded.replace(false)
885 let result = op(this);
886 if let Some(data_race) = &this.memory.extra.data_race {
887 data_race.multi_threaded.set(old);
892 /// Same as `allow_data_races_ref`, this temporarily disables any data-race detection and
893 /// so should only be used for atomic operations or internal state that the program cannot
896 fn allow_data_races_mut<R>(
898 op: impl FnOnce(&mut MiriEvalContext<'mir, 'tcx>) -> R,
900 let this = self.eval_context_mut();
901 let old = if let Some(data_race) = &this.memory.extra.data_race {
902 data_race.multi_threaded.replace(false)
906 let result = op(this);
907 if let Some(data_race) = &this.memory.extra.data_race {
908 data_race.multi_threaded.set(old);
913 /// Generic atomic operation implementation,
914 /// this accesses memory via get_raw instead of
915 /// get_raw_mut, due to issues calling get_raw_mut
916 /// for atomic loads from read-only memory.
917 /// FIXME: is this valid, or should get_raw_mut be used for
918 /// atomic-stores/atomic-rmw?
919 fn validate_atomic_op<A: Debug + Copy>(
921 place: MPlaceTy<'tcx, Tag>,
925 &mut MemoryCellClocks,
929 ) -> Result<(), DataRace>,
930 ) -> InterpResult<'tcx> {
931 let this = self.eval_context_ref();
932 if let Some(data_race) = &this.memory.extra.data_race {
933 if data_race.multi_threaded.get() {
934 // Load and log the atomic operation.
935 let place_ptr = place.ptr.assert_ptr();
936 let size = place.layout.size;
938 &this.memory.get_raw(place_ptr.alloc_id)?.extra.data_race.as_ref().unwrap();
940 "Atomic op({}) with ordering {:?} on memory({:?}, offset={}, size={})",
944 place_ptr.offset.bytes(),
948 // Perform the atomic operation.
949 let data_race = &alloc_meta.global;
950 data_race.maybe_perform_sync_operation(|index, mut clocks| {
952 alloc_meta.alloc_ranges.borrow_mut().iter_mut(place_ptr.offset, size)
954 if let Err(DataRace) = op(range, &mut *clocks, index, atomic) {
956 return VClockAlloc::report_data_race(
967 // This conservatively assumes all operations have release semantics
971 // Log changes to atomic memory.
972 if log::log_enabled!(log::Level::Trace) {
973 for (_, range) in alloc_meta.alloc_ranges.borrow().iter(place_ptr.offset, size)
976 "Updated atomic memory({:?}, offset={}, size={}) to {:#?}",
977 place.ptr.assert_ptr().alloc_id,
978 place_ptr.offset.bytes(),
990 /// Extra metadata associated with a thread.
991 #[derive(Debug, Clone, Default)]
992 struct ThreadExtraState {
993 /// The current vector index in use by the
994 /// thread currently, this is set to None
995 /// after the vector index has been re-used
996 /// and hence the value will never need to be
997 /// read during data-race reporting.
998 vector_index: Option<VectorIdx>,
1000 /// The name of the thread, updated for better
1001 /// diagnostics when reporting detected data
1003 thread_name: Option<Box<str>>,
1005 /// Thread termination vector clock, this
1006 /// is set on thread termination and is used
1007 /// for joining on threads since the vector_index
1008 /// may be re-used when the join operation occurs.
1009 termination_vector_clock: Option<VClock>,
1012 /// Global data-race detection state, contains the currently
1013 /// executing thread as well as the vector-clocks associated
1014 /// with each of the threads.
1015 #[derive(Debug, Clone)]
1016 pub struct GlobalState {
1017 /// Set to true once the first additional
1018 /// thread has launched, due to the dependency
1019 /// between before and after a thread launch.
1020 /// Any data-races must be recorded after this
1021 /// so concurrent execution can ignore recording
1023 multi_threaded: Cell<bool>,
1025 /// Mapping of a vector index to a known set of thread
1026 /// clocks, this is not directly mapping from a thread id
1027 /// since it may refer to multiple threads.
1028 vector_clocks: RefCell<IndexVec<VectorIdx, ThreadClockSet>>,
1030 /// Mapping of a given vector index to the current thread
1031 /// that the execution is representing, this may change
1032 /// if a vector index is re-assigned to a new thread.
1033 vector_info: RefCell<IndexVec<VectorIdx, ThreadId>>,
1035 /// The mapping of a given thread to associated thread metadata.
1036 thread_info: RefCell<IndexVec<ThreadId, ThreadExtraState>>,
1038 /// The current vector index being executed.
1039 current_index: Cell<VectorIdx>,
1041 /// Potential vector indices that could be re-used on thread creation
1042 /// values are inserted here on after the thread has terminated and
1043 /// been joined with, and hence may potentially become free
1044 /// for use as the index for a new thread.
1045 /// Elements in this set may still require the vector index to
1046 /// report data-races, and can only be re-used after all
1047 /// active vector-clocks catch up with the threads timestamp.
1048 reuse_candidates: RefCell<FxHashSet<VectorIdx>>,
1050 /// Counts the number of threads that are currently active
1051 /// if the number of active threads reduces to 1 and then
1052 /// a join operation occurs with the remaining main thread
1053 /// then multi-threaded execution may be disabled.
1054 active_thread_count: Cell<usize>,
1056 /// This contains threads that have terminated, but not yet joined
1057 /// and so cannot become re-use candidates until a join operation
1059 /// The associated vector index will be moved into re-use candidates
1060 /// after the join operation occurs.
1061 terminated_threads: RefCell<FxHashMap<ThreadId, VectorIdx>>,
1065 /// Create a new global state, setup with just thread-id=0
1066 /// advanced to timestamp = 1.
1067 pub fn new() -> Self {
1068 let global_state = GlobalState {
1069 multi_threaded: Cell::new(false),
1070 vector_clocks: RefCell::new(IndexVec::new()),
1071 vector_info: RefCell::new(IndexVec::new()),
1072 thread_info: RefCell::new(IndexVec::new()),
1073 current_index: Cell::new(VectorIdx::new(0)),
1074 active_thread_count: Cell::new(1),
1075 reuse_candidates: RefCell::new(FxHashSet::default()),
1076 terminated_threads: RefCell::new(FxHashMap::default()),
1079 // Setup the main-thread since it is not explicitly created:
1080 // uses vector index and thread-id 0, also the rust runtime gives
1081 // the main-thread a name of "main".
1082 let index = global_state.vector_clocks.borrow_mut().push(ThreadClockSet::default());
1083 global_state.vector_info.borrow_mut().push(ThreadId::new(0));
1084 global_state.thread_info.borrow_mut().push(ThreadExtraState {
1085 vector_index: Some(index),
1086 thread_name: Some("main".to_string().into_boxed_str()),
1087 termination_vector_clock: None,
1093 // Try to find vector index values that can potentially be re-used
1094 // by a new thread instead of a new vector index being created.
1095 fn find_vector_index_reuse_candidate(&self) -> Option<VectorIdx> {
1096 let mut reuse = self.reuse_candidates.borrow_mut();
1097 let vector_clocks = self.vector_clocks.borrow();
1098 let vector_info = self.vector_info.borrow();
1099 let terminated_threads = self.terminated_threads.borrow();
1100 for &candidate in reuse.iter() {
1101 let target_timestamp = vector_clocks[candidate].clock[candidate];
1102 if vector_clocks.iter_enumerated().all(|(clock_idx, clock)| {
1103 // The thread happens before the clock, and hence cannot report
1104 // a data-race with this the candidate index.
1105 let no_data_race = clock.clock[candidate] >= target_timestamp;
1107 // The vector represents a thread that has terminated and hence cannot
1108 // report a data-race with the candidate index.
1109 let thread_id = vector_info[clock_idx];
1110 let vector_terminated =
1111 reuse.contains(&clock_idx) || terminated_threads.contains_key(&thread_id);
1113 // The vector index cannot report a race with the candidate index
1114 // and hence allows the candidate index to be re-used.
1115 no_data_race || vector_terminated
1117 // All vector clocks for each vector index are equal to
1118 // the target timestamp, and the thread is known to have
1119 // terminated, therefore this vector clock index cannot
1120 // report any more data-races.
1121 assert!(reuse.remove(&candidate));
1122 return Some(candidate);
1128 // Hook for thread creation, enabled multi-threaded execution and marks
1129 // the current thread timestamp as happening-before the current thread.
1131 pub fn thread_created(&self, thread: ThreadId) {
1132 let current_index = self.current_index();
1134 // Increment the number of active threads.
1135 let active_threads = self.active_thread_count.get();
1136 self.active_thread_count.set(active_threads + 1);
1138 // Enable multi-threaded execution, there are now two threads
1139 // so data-races are now possible.
1140 self.multi_threaded.set(true);
1142 // Load and setup the associated thread metadata
1143 let mut thread_info = self.thread_info.borrow_mut();
1144 thread_info.ensure_contains_elem(thread, Default::default);
1146 // Assign a vector index for the thread, attempting to re-use an old
1147 // vector index that can no longer report any data-races if possible.
1148 let created_index = if let Some(reuse_index) = self.find_vector_index_reuse_candidate() {
1149 // Now re-configure the re-use candidate, increment the clock
1150 // for the new sync use of the vector.
1151 let mut vector_clocks = self.vector_clocks.borrow_mut();
1152 vector_clocks[reuse_index].increment_clock(reuse_index);
1154 // Locate the old thread the vector was associated with and update
1155 // it to represent the new thread instead.
1156 let mut vector_info = self.vector_info.borrow_mut();
1157 let old_thread = vector_info[reuse_index];
1158 vector_info[reuse_index] = thread;
1160 // Mark the thread the vector index was associated with as no longer
1161 // representing a thread index.
1162 thread_info[old_thread].vector_index = None;
1166 // No vector re-use candidates available, instead create
1167 // a new vector index.
1168 let mut vector_info = self.vector_info.borrow_mut();
1169 vector_info.push(thread)
1172 // Mark the chosen vector index as in use by the thread.
1173 thread_info[thread].vector_index = Some(created_index);
1175 // Create a thread clock set if applicable.
1176 let mut vector_clocks = self.vector_clocks.borrow_mut();
1177 if created_index == vector_clocks.next_index() {
1178 vector_clocks.push(ThreadClockSet::default());
1181 // Now load the two clocks and configure the initial state.
1182 let (current, created) = vector_clocks.pick2_mut(current_index, created_index);
1184 // Join the created with current, since the current threads
1185 // previous actions happen-before the created thread.
1186 created.join_with(current);
1188 // Advance both threads after the synchronized operation.
1189 // Both operations are considered to have release semantics.
1190 current.increment_clock(current_index);
1191 created.increment_clock(created_index);
1194 /// Hook on a thread join to update the implicit happens-before relation
1195 /// between the joined thread and the current thread.
1197 pub fn thread_joined(&self, current_thread: ThreadId, join_thread: ThreadId) {
1198 let mut clocks_vec = self.vector_clocks.borrow_mut();
1199 let thread_info = self.thread_info.borrow();
1201 // Load the vector clock of the current thread.
1202 let current_index = thread_info[current_thread]
1204 .expect("Performed thread join on thread with no assigned vector");
1205 let current = &mut clocks_vec[current_index];
1207 // Load the associated vector clock for the terminated thread.
1208 let join_clock = thread_info[join_thread]
1209 .termination_vector_clock
1211 .expect("Joined with thread but thread has not terminated");
1214 // The join thread happens-before the current thread
1215 // so update the current vector clock.
1216 // Is not a release operation so the clock is not incremented.
1217 current.clock.join(join_clock);
1219 // Check the number of active threads, if the value is 1
1220 // then test for potentially disabling multi-threaded execution.
1221 let active_threads = self.active_thread_count.get();
1222 if active_threads == 1 {
1223 // May potentially be able to disable multi-threaded execution.
1224 let current_clock = &clocks_vec[current_index];
1227 .all(|(idx, clocks)| clocks.clock[idx] <= current_clock.clock[idx])
1229 // All thread terminations happen-before the current clock
1230 // therefore no data-races can be reported until a new thread
1231 // is created, so disable multi-threaded execution.
1232 self.multi_threaded.set(false);
1236 // If the thread is marked as terminated but not joined
1237 // then move the thread to the re-use set.
1238 let mut termination = self.terminated_threads.borrow_mut();
1239 if let Some(index) = termination.remove(&join_thread) {
1240 let mut reuse = self.reuse_candidates.borrow_mut();
1241 reuse.insert(index);
1245 /// On thread termination, the vector-clock may re-used
1246 /// in the future once all remaining thread-clocks catch
1247 /// up with the time index of the terminated thread.
1248 /// This assigns thread termination with a unique index
1249 /// which will be used to join the thread
1250 /// This should be called strictly before any calls to
1251 /// `thread_joined`.
1253 pub fn thread_terminated(&self) {
1254 let current_index = self.current_index();
1256 // Increment the clock to a unique termination timestamp.
1257 let mut vector_clocks = self.vector_clocks.borrow_mut();
1258 let current_clocks = &mut vector_clocks[current_index];
1259 current_clocks.increment_clock(current_index);
1261 // Load the current thread id for the executing vector.
1262 let vector_info = self.vector_info.borrow();
1263 let current_thread = vector_info[current_index];
1265 // Load the current thread metadata, and move to a terminated
1266 // vector state. Setting up the vector clock all join operations
1268 let mut thread_info = self.thread_info.borrow_mut();
1269 let current = &mut thread_info[current_thread];
1270 current.termination_vector_clock = Some(current_clocks.clock.clone());
1272 // Add this thread as a candidate for re-use after a thread join
1274 let mut termination = self.terminated_threads.borrow_mut();
1275 termination.insert(current_thread, current_index);
1277 // Reduce the number of active threads, now that a thread has
1279 let mut active_threads = self.active_thread_count.get();
1280 active_threads -= 1;
1281 self.active_thread_count.set(active_threads);
1284 /// Hook for updating the local tracker of the currently
1285 /// enabled thread, should always be updated whenever
1286 /// `active_thread` in thread.rs is updated.
1288 pub fn thread_set_active(&self, thread: ThreadId) {
1289 let thread_info = self.thread_info.borrow();
1290 let vector_idx = thread_info[thread]
1292 .expect("Setting thread active with no assigned vector");
1293 self.current_index.set(vector_idx);
1296 /// Hook for updating the local tracker of the threads name
1297 /// this should always mirror the local value in thread.rs
1298 /// the thread name is used for improved diagnostics
1299 /// during a data-race.
1301 pub fn thread_set_name(&self, thread: ThreadId, name: String) {
1302 let name = name.into_boxed_str();
1303 let mut thread_info = self.thread_info.borrow_mut();
1304 thread_info[thread].thread_name = Some(name);
1307 /// Attempt to perform a synchronized operation, this
1308 /// will perform no operation if multi-threading is
1309 /// not currently enabled.
1310 /// Otherwise it will increment the clock for the current
1311 /// vector before and after the operation for data-race
1312 /// detection between any happens-before edges the
1313 /// operation may create.
1314 fn maybe_perform_sync_operation<'tcx>(
1316 op: impl FnOnce(VectorIdx, RefMut<'_, ThreadClockSet>) -> InterpResult<'tcx, bool>,
1317 ) -> InterpResult<'tcx> {
1318 if self.multi_threaded.get() {
1319 let (index, clocks) = self.current_thread_state_mut();
1320 if op(index, clocks)? {
1321 let (_, mut clocks) = self.current_thread_state_mut();
1322 clocks.increment_clock(index);
1328 /// Internal utility to identify a thread stored internally
1329 /// returns the id and the name for better diagnostics.
1330 fn print_thread_metadata(&self, vector: VectorIdx) -> String {
1331 let thread = self.vector_info.borrow()[vector];
1332 let thread_name = &self.thread_info.borrow()[thread].thread_name;
1333 if let Some(name) = thread_name {
1334 let name: &str = name;
1335 format!("Thread(id = {:?}, name = {:?})", thread.to_u32(), &*name)
1337 format!("Thread(id = {:?})", thread.to_u32())
1341 /// Acquire a lock, express that the previous call of
1342 /// `validate_lock_release` must happen before this.
1343 /// As this is an acquire operation, the thread timestamp is not
1345 pub fn validate_lock_acquire(&self, lock: &VClock, thread: ThreadId) {
1346 let (_, mut clocks) = self.load_thread_state_mut(thread);
1347 clocks.clock.join(&lock);
1350 /// Release a lock handle, express that this happens-before
1351 /// any subsequent calls to `validate_lock_acquire`.
1352 /// For normal locks this should be equivalent to `validate_lock_release_shared`
1353 /// since an acquire operation should have occurred before, however
1354 /// for futex & condvar operations this is not the case and this
1355 /// operation must be used.
1356 pub fn validate_lock_release(&self, lock: &mut VClock, thread: ThreadId) {
1357 let (index, mut clocks) = self.load_thread_state_mut(thread);
1358 lock.clone_from(&clocks.clock);
1359 clocks.increment_clock(index);
1362 /// Release a lock handle, express that this happens-before
1363 /// any subsequent calls to `validate_lock_acquire` as well
1364 /// as any previous calls to this function after any
1365 /// `validate_lock_release` calls.
1366 /// For normal locks this should be equivalent to `validate_lock_release`.
1367 /// This function only exists for joining over the set of concurrent readers
1368 /// in a read-write lock and should not be used for anything else.
1369 pub fn validate_lock_release_shared(&self, lock: &mut VClock, thread: ThreadId) {
1370 let (index, mut clocks) = self.load_thread_state_mut(thread);
1371 lock.join(&clocks.clock);
1372 clocks.increment_clock(index);
1375 /// Load the vector index used by the given thread as well as the set of vector clocks
1376 /// used by the thread.
1378 fn load_thread_state_mut(&self, thread: ThreadId) -> (VectorIdx, RefMut<'_, ThreadClockSet>) {
1379 let index = self.thread_info.borrow()[thread]
1381 .expect("Loading thread state for thread with no assigned vector");
1382 let ref_vector = self.vector_clocks.borrow_mut();
1383 let clocks = RefMut::map(ref_vector, |vec| &mut vec[index]);
1387 /// Load the current vector clock in use and the current set of thread clocks
1388 /// in use for the vector.
1390 fn current_thread_state(&self) -> (VectorIdx, Ref<'_, ThreadClockSet>) {
1391 let index = self.current_index();
1392 let ref_vector = self.vector_clocks.borrow();
1393 let clocks = Ref::map(ref_vector, |vec| &vec[index]);
1397 /// Load the current vector clock in use and the current set of thread clocks
1398 /// in use for the vector mutably for modification.
1400 fn current_thread_state_mut(&self) -> (VectorIdx, RefMut<'_, ThreadClockSet>) {
1401 let index = self.current_index();
1402 let ref_vector = self.vector_clocks.borrow_mut();
1403 let clocks = RefMut::map(ref_vector, |vec| &mut vec[index]);
1407 /// Return the current thread, should be the same
1408 /// as the data-race active thread.
1410 fn current_index(&self) -> VectorIdx {
1411 self.current_index.get()