X-Git-Url: https://git.lizzy.rs/?a=blobdiff_plain;f=src%2Fdata_race.rs;h=e8071845c7d76240046ef8c3be17023474c772ad;hb=2670839e1af540a496a0d889fce9ad42529ecc11;hp=b9542f6e2d62c91938d521283562027f93bc6564;hpb=0b0264fc820d12d6c5e6f9f702bc33e8921bb110;p=rust.git diff --git a/src/data_race.rs b/src/data_race.rs index b9542f6e2d6..e8071845c7d 100644 --- a/src/data_race.rs +++ b/src/data_race.rs @@ -1,13 +1,21 @@ //! Implementation of a data-race detector using Lamport Timestamps / Vector-clocks -//! based on the Dyamic Race Detection for C++: +//! based on the Dynamic Race Detection for C++: //! https://www.doc.ic.ac.uk/~afd/homepages/papers/pdfs/2017/POPL.pdf //! which does not report false-positives when fences are used, and gives better //! accuracy in presence of read-modify-write operations. //! +//! The implementation contains modifications to correctly model the changes to the memory model in C++20 +//! regarding the weakening of release sequences: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0982r1.html. +//! Relaxed stores now unconditionally block all currently active release sequences and so per-thread tracking of release +//! sequences is not needed. +//! +//! The implementation also models races with memory allocation and deallocation via treating allocation and +//! deallocation as a type of write internally for detecting data-races. +//! //! This does not explore weak memory orders and so can still miss data-races //! but should not report false-positives //! -//! Data-race definiton from(https://en.cppreference.com/w/cpp/language/memory_model#Threads_and_data_races): +//! Data-race definition from(https://en.cppreference.com/w/cpp/language/memory_model#Threads_and_data_races): //! a data race occurs between two memory accesses if they are on different threads, at least one operation //! is non-atomic, at least one operation is a write and neither access happens-before the other. Read the link //! for full definition. @@ -21,7 +29,7 @@ //! This means that the thread-index can be safely re-used, starting on the next timestamp for the newly created //! thread. //! -//! The sequentially consistant ordering corresponds to the ordering that the threads +//! The sequentially consistent ordering corresponds to the ordering that the threads //! are currently scheduled, this means that the data-race detector has no additional //! logic for sequentially consistent accesses at the moment since they are indistinguishable //! from acquire/release operations. If weak memory orderings are explored then this @@ -37,6 +45,17 @@ //! to a acquire load and a release store given the global sequentially consistent order //! of the schedule. //! +//! The timestamps used in the data-race detector assign each sequence of non-atomic operations +//! followed by a single atomic or concurrent operation a single timestamp. +//! Write, Read, Write, ThreadJoin will be represented by a single timestamp value on a thread. +//! This is because extra increment operations between the operations in the sequence are not +//! required for accurate reporting of data-race values. +//! +//! As per the paper a threads timestamp is only incremented after a release operation is performed +//! so some atomic operations that only perform acquires do not increment the timestamp. Due to shared +//! code some atomic operations may increment the timestamp when not necessary but this has no effect +//! on the data-race detection code. +//! //! FIXME: //! currently we have our own local copy of the currently active thread index and names, this is due //! in part to the inability to access the current location of threads.active_thread inside the AllocExtra @@ -55,9 +74,9 @@ use rustc_target::abi::Size; use crate::{ - ImmTy, Immediate, InterpResult, MPlaceTy, MemPlaceMeta, MiriEvalContext, MiriEvalContextExt, - OpTy, Pointer, RangeMap, ScalarMaybeUninit, Tag, ThreadId, VClock, VSmallClockMap, VTimestamp, - VectorIdx, + ImmTy, Immediate, InterpResult, MPlaceTy, MemPlaceMeta, MemoryKind, MiriEvalContext, + MiriEvalContextExt, MiriMemoryKind, OpTy, Pointer, RangeMap, Scalar, ScalarMaybeUninit, Tag, + ThreadId, VClock, VTimestamp, VectorIdx, }; pub type AllocExtra = VClockAlloc; @@ -111,7 +130,7 @@ struct ThreadClockSet { /// thread once it performs an acquire fence. fence_acquire: VClock, - /// The last timesamp of happens-before relations that + /// The last timestamp of happens-before relations that /// have been released by this thread by a fence. fence_release: VClock, } @@ -174,13 +193,34 @@ struct AtomicMemoryCellClocks { /// happen-before a thread if an acquire-load is /// performed on the data. sync_vector: VClock, +} - /// The Hash-Map of all threads for which a release - /// sequence exists in the memory cell, required - /// since read-modify-write operations do not - /// invalidate existing release sequences. - /// See page 6 of linked paper. - release_sequences: VSmallClockMap, +/// Type of write operation: allocating memory +/// non-atomic writes and deallocating memory +/// are all treated as writes for the purpose +/// of the data-race detector. +#[derive(Copy, Clone, PartialEq, Eq, Debug)] +enum WriteType { + /// Allocate memory. + Allocate, + + /// Standard unsynchronized write. + Write, + + /// Deallocate memory. + /// Note that when memory is deallocated first, later non-atomic accesses + /// will be reported as use-after-free, not as data races. + /// (Same for `Allocate` above.) + Deallocate, +} +impl WriteType { + fn get_descriptor(self) -> &'static str { + match self { + WriteType::Allocate => "Allocate", + WriteType::Write => "Write", + WriteType::Deallocate => "Deallocate", + } + } } /// Memory Cell vector clock metadata @@ -195,8 +235,13 @@ struct MemoryCellClocks { /// that performed the last write operation. write_index: VectorIdx, + /// The type of operation that the write index represents, + /// either newly allocated memory, a non-atomic write or + /// a deallocation of memory. + write_type: WriteType, + /// The vector-clock of the timestamp of the last read operation - /// performed by a thread since the last write operation occured. + /// performed by a thread since the last write operation occurred. /// It is reset to zero on each write operation. read: VClock, @@ -206,20 +251,19 @@ struct MemoryCellClocks { atomic_ops: Option>, } -/// Create a default memory cell clocks instance -/// for uninitialized memory. -impl Default for MemoryCellClocks { - fn default() -> Self { +impl MemoryCellClocks { + /// Create a new set of clocks representing memory allocated + /// at a given vector timestamp and index. + fn new(alloc: VTimestamp, alloc_index: VectorIdx) -> Self { MemoryCellClocks { read: VClock::default(), - write: 0, - write_index: VectorIdx::MAX_INDEX, + write: alloc, + write_index: alloc_index, + write_type: WriteType::Allocate, atomic_ops: None, } } -} -impl MemoryCellClocks { /// Load the internal atomic memory cells if they exist. #[inline] fn atomic(&self) -> Option<&AtomicMemoryCellClocks> { @@ -272,8 +316,6 @@ fn store_release(&mut self, clocks: &ThreadClockSet, index: VectorIdx) -> Result self.atomic_write_detect(clocks, index)?; let atomic = self.atomic_mut(); atomic.sync_vector.clone_from(&clocks.clock); - atomic.release_sequences.clear(); - atomic.release_sequences.insert(index, &clocks.clock); Ok(()) } @@ -281,12 +323,13 @@ fn store_release(&mut self, clocks: &ThreadClockSet, index: VectorIdx) -> Result /// store relaxed semantics. fn store_relaxed(&mut self, clocks: &ThreadClockSet, index: VectorIdx) -> Result<(), DataRace> { self.atomic_write_detect(clocks, index)?; + + // The handling of release sequences was changed in C++20 and so + // the code here is different to the paper since now all relaxed + // stores block release sequences. The exception for same-thread + // relaxed stores has been removed. let atomic = self.atomic_mut(); atomic.sync_vector.clone_from(&clocks.fence_release); - if let Some(release) = atomic.release_sequences.get(index) { - atomic.sync_vector.join(release); - } - atomic.release_sequences.retain_index(index); Ok(()) } @@ -296,7 +339,6 @@ fn rmw_release(&mut self, clocks: &ThreadClockSet, index: VectorIdx) -> Result<( self.atomic_write_detect(clocks, index)?; let atomic = self.atomic_mut(); atomic.sync_vector.join(&clocks.clock); - atomic.release_sequences.insert(index, &clocks.clock); Ok(()) } @@ -374,6 +416,7 @@ fn write_race_detect( &mut self, clocks: &ThreadClockSet, index: VectorIdx, + write_type: WriteType, ) -> Result<(), DataRace> { log::trace!("Unsynchronized write with vectors: {:#?} :: {:#?}", self, clocks); if self.write <= clocks.clock[self.write_index] && self.read <= clocks.clock { @@ -385,6 +428,7 @@ fn write_race_detect( if race_free { self.write = clocks.clock[index]; self.write_index = index; + self.write_type = write_type; self.read.set_zero_vector(); Ok(()) } else { @@ -402,7 +446,7 @@ pub trait EvalContextExt<'mir, 'tcx: 'mir>: MiriEvalContextExt<'mir, 'tcx> { /// Atomic variant of read_scalar_at_offset. fn read_scalar_at_offset_atomic( &self, - op: OpTy<'tcx, Tag>, + op: &OpTy<'tcx, Tag>, offset: u64, layout: TyAndLayout<'tcx>, atomic: AtomicReadOp, @@ -414,13 +458,13 @@ fn read_scalar_at_offset_atomic( // Ensure that the following read at an offset is within bounds. assert!(op_place.layout.size >= offset + layout.size); let value_place = op_place.offset(offset, MemPlaceMeta::None, layout, this)?; - this.read_scalar_atomic(value_place, atomic) + this.read_scalar_atomic(&value_place, atomic) } /// Atomic variant of write_scalar_at_offset. fn write_scalar_at_offset_atomic( &mut self, - op: OpTy<'tcx, Tag>, + op: &OpTy<'tcx, Tag>, offset: u64, value: impl Into>, layout: TyAndLayout<'tcx>, @@ -433,17 +477,17 @@ fn write_scalar_at_offset_atomic( // Ensure that the following read at an offset is within bounds. assert!(op_place.layout.size >= offset + layout.size); let value_place = op_place.offset(offset, MemPlaceMeta::None, layout, this)?; - this.write_scalar_atomic(value.into(), value_place, atomic) + this.write_scalar_atomic(value.into(), &value_place, atomic) } /// Perform an atomic read operation at the memory location. fn read_scalar_atomic( &self, - place: MPlaceTy<'tcx, Tag>, + place: &MPlaceTy<'tcx, Tag>, atomic: AtomicReadOp, ) -> InterpResult<'tcx, ScalarMaybeUninit> { let this = self.eval_context_ref(); - let scalar = this.allow_data_races_ref(move |this| this.read_scalar(place.into()))?; + let scalar = this.allow_data_races_ref(move |this| this.read_scalar(&place.into()))?; self.validate_atomic_load(place, atomic)?; Ok(scalar) } @@ -452,31 +496,31 @@ fn read_scalar_atomic( fn write_scalar_atomic( &mut self, val: ScalarMaybeUninit, - dest: MPlaceTy<'tcx, Tag>, + dest: &MPlaceTy<'tcx, Tag>, atomic: AtomicWriteOp, ) -> InterpResult<'tcx> { let this = self.eval_context_mut(); - this.allow_data_races_mut(move |this| this.write_scalar(val, dest.into()))?; + this.allow_data_races_mut(move |this| this.write_scalar(val, &(*dest).into()))?; self.validate_atomic_store(dest, atomic) } /// Perform a atomic operation on a memory location. fn atomic_op_immediate( &mut self, - place: MPlaceTy<'tcx, Tag>, - rhs: ImmTy<'tcx, Tag>, + place: &MPlaceTy<'tcx, Tag>, + rhs: &ImmTy<'tcx, Tag>, op: mir::BinOp, neg: bool, atomic: AtomicRwOp, ) -> InterpResult<'tcx, ImmTy<'tcx, Tag>> { let this = self.eval_context_mut(); - let old = this.allow_data_races_mut(|this| this.read_immediate(place.into()))?; + let old = this.allow_data_races_mut(|this| this.read_immediate(&place.into()))?; // Atomics wrap around on overflow. - let val = this.binary_op(op, old, rhs)?; - let val = if neg { this.unary_op(mir::UnOp::Not, val)? } else { val }; - this.allow_data_races_mut(|this| this.write_immediate(*val, place.into()))?; + let val = this.binary_op(op, &old, rhs)?; + let val = if neg { this.unary_op(mir::UnOp::Not, &val)? } else { val }; + this.allow_data_races_mut(|this| this.write_immediate(*val, &(*place).into()))?; this.validate_atomic_rmw(place, atomic)?; Ok(old) @@ -486,46 +530,86 @@ fn atomic_op_immediate( /// scalar value, the old value is returned. fn atomic_exchange_scalar( &mut self, - place: MPlaceTy<'tcx, Tag>, + place: &MPlaceTy<'tcx, Tag>, new: ScalarMaybeUninit, atomic: AtomicRwOp, ) -> InterpResult<'tcx, ScalarMaybeUninit> { let this = self.eval_context_mut(); - let old = this.allow_data_races_mut(|this| this.read_scalar(place.into()))?; - this.allow_data_races_mut(|this| this.write_scalar(new, place.into()))?; + let old = this.allow_data_races_mut(|this| this.read_scalar(&place.into()))?; + this.allow_data_races_mut(|this| this.write_scalar(new, &(*place).into()))?; this.validate_atomic_rmw(place, atomic)?; Ok(old) } - /// Perform an atomic compare and exchange at a given memory location - /// on success an atomic RMW operation is performed and on failure - /// only an atomic read occurs. + /// Perform an conditional atomic exchange with a memory place and a new + /// scalar value, the old value is returned. + fn atomic_min_max_scalar( + &mut self, + place: &MPlaceTy<'tcx, Tag>, + rhs: ImmTy<'tcx, Tag>, + min: bool, + atomic: AtomicRwOp, + ) -> InterpResult<'tcx, ImmTy<'tcx, Tag>> { + let this = self.eval_context_mut(); + + let old = this.allow_data_races_mut(|this| this.read_immediate(&place.into()))?; + let lt = this.overflowing_binary_op(mir::BinOp::Lt, &old, &rhs)?.0.to_bool()?; + + let new_val = if min { + if lt { &old } else { &rhs } + } else { + if lt { &rhs } else { &old } + }; + + this.allow_data_races_mut(|this| this.write_immediate_to_mplace(**new_val, place))?; + + this.validate_atomic_rmw(&place, atomic)?; + + // Return the old value. + Ok(old) + } + + /// Perform an atomic compare and exchange at a given memory location. + /// On success an atomic RMW operation is performed and on failure + /// only an atomic read occurs. If `can_fail_spuriously` is true, + /// then we treat it as a "compare_exchange_weak" operation, and + /// some portion of the time fail even when the values are actually + /// identical. fn atomic_compare_exchange_scalar( &mut self, - place: MPlaceTy<'tcx, Tag>, - expect_old: ImmTy<'tcx, Tag>, + place: &MPlaceTy<'tcx, Tag>, + expect_old: &ImmTy<'tcx, Tag>, new: ScalarMaybeUninit, success: AtomicRwOp, fail: AtomicReadOp, + can_fail_spuriously: bool, ) -> InterpResult<'tcx, Immediate> { + use rand::Rng as _; let this = self.eval_context_mut(); // Failure ordering cannot be stronger than success ordering, therefore first attempt - // to read with the failure ordering and if successfull then try again with the success + // to read with the failure ordering and if successful then try again with the success // read ordering and write in the success case. // Read as immediate for the sake of `binary_op()` - let old = this.allow_data_races_mut(|this| this.read_immediate(place.into()))?; - + let old = this.allow_data_races_mut(|this| this.read_immediate(&(place.into())))?; // `binary_op` will bail if either of them is not a scalar. - let eq = this.overflowing_binary_op(mir::BinOp::Eq, old, expect_old)?.0; - let res = Immediate::ScalarPair(old.to_scalar_or_uninit(), eq.into()); + let eq = this.overflowing_binary_op(mir::BinOp::Eq, &old, expect_old)?.0; + // If the operation would succeed, but is "weak", fail some portion + // of the time, based on `rate`. + let rate = this.memory.extra.cmpxchg_weak_failure_rate; + let cmpxchg_success = eq.to_bool()? + && (!can_fail_spuriously || this.memory.extra.rng.borrow_mut().gen::() < rate); + let res = Immediate::ScalarPair( + old.to_scalar_or_uninit(), + Scalar::from_bool(cmpxchg_success).into(), + ); // Update ptr depending on comparison. // if successful, perform a full rw-atomic validation // otherwise treat this as an atomic load with the fail ordering. - if eq.to_bool()? { - this.allow_data_races_mut(|this| this.write_scalar(new, place.into()))?; + if cmpxchg_success { + this.allow_data_races_mut(|this| this.write_scalar(new, &(*place).into()))?; this.validate_atomic_rmw(place, success)?; } else { this.validate_atomic_load(place, fail)?; @@ -535,11 +619,11 @@ fn atomic_compare_exchange_scalar( Ok(res) } - /// Update the data-race detector for an atomic read occuring at the + /// Update the data-race detector for an atomic read occurring at the /// associated memory-place and on the current thread. fn validate_atomic_load( &self, - place: MPlaceTy<'tcx, Tag>, + place: &MPlaceTy<'tcx, Tag>, atomic: AtomicReadOp, ) -> InterpResult<'tcx> { let this = self.eval_context_ref(); @@ -557,11 +641,11 @@ fn validate_atomic_load( ) } - /// Update the data-race detector for an atomic write occuring at the + /// Update the data-race detector for an atomic write occurring at the /// associated memory-place and on the current thread. fn validate_atomic_store( &mut self, - place: MPlaceTy<'tcx, Tag>, + place: &MPlaceTy<'tcx, Tag>, atomic: AtomicWriteOp, ) -> InterpResult<'tcx> { let this = self.eval_context_ref(); @@ -579,11 +663,11 @@ fn validate_atomic_store( ) } - /// Update the data-race detector for an atomic read-modify-write occuring + /// Update the data-race detector for an atomic read-modify-write occurring /// at the associated memory place and on the current thread. fn validate_atomic_rmw( &mut self, - place: MPlaceTy<'tcx, Tag>, + place: &MPlaceTy<'tcx, Tag>, atomic: AtomicRwOp, ) -> InterpResult<'tcx> { use AtomicRwOp::*; @@ -622,38 +706,87 @@ fn validate_atomic_fence(&mut self, atomic: AtomicFenceOp) -> InterpResult<'tcx> // Either Release | AcqRel | SeqCst clocks.apply_release_fence(); } - Ok(()) + + // Increment timestamp in case of release semantics. + Ok(atomic != AtomicFenceOp::Acquire) }) } else { Ok(()) } } + + fn reset_vector_clocks(&mut self, ptr: Pointer, size: Size) -> InterpResult<'tcx> { + let this = self.eval_context_mut(); + if let Some(data_race) = &mut this.memory.extra.data_race { + if data_race.multi_threaded.get() { + let alloc_meta = + this.memory.get_raw_mut(ptr.alloc_id)?.extra.data_race.as_mut().unwrap(); + alloc_meta.reset_clocks(ptr.offset, size); + } + } + Ok(()) + } } /// Vector clock metadata for a logical memory allocation. #[derive(Debug, Clone)] pub struct VClockAlloc { - /// Range of Vector clocks, this gives each byte a potentially - /// unqiue set of vector clocks, but merges identical information - /// together for improved efficiency. + /// Assigning each byte a MemoryCellClocks. alloc_ranges: RefCell>, - // Pointer to global state. + /// Pointer to global state. global: MemoryExtra, } impl VClockAlloc { - /// Create a new data-race allocation detector. - pub fn new_allocation(global: &MemoryExtra, len: Size) -> VClockAlloc { + /// Create a new data-race detector for newly allocated memory. + pub fn new_allocation( + global: &MemoryExtra, + len: Size, + kind: MemoryKind, + ) -> VClockAlloc { + let (alloc_timestamp, alloc_index) = match kind { + // User allocated and stack memory should track allocation. + MemoryKind::Machine( + MiriMemoryKind::Rust | MiriMemoryKind::C | MiriMemoryKind::WinHeap, + ) + | MemoryKind::Stack => { + let (alloc_index, clocks) = global.current_thread_state(); + let alloc_timestamp = clocks.clock[alloc_index]; + (alloc_timestamp, alloc_index) + } + // Other global memory should trace races but be allocated at the 0 timestamp. + MemoryKind::Machine( + MiriMemoryKind::Global + | MiriMemoryKind::Machine + | MiriMemoryKind::Env + | MiriMemoryKind::ExternStatic + | MiriMemoryKind::Tls, + ) + | MemoryKind::CallerLocation + | MemoryKind::Vtable => (0, VectorIdx::MAX_INDEX), + }; VClockAlloc { global: Rc::clone(global), - alloc_ranges: RefCell::new(RangeMap::new(len, MemoryCellClocks::default())), + alloc_ranges: RefCell::new(RangeMap::new( + len, + MemoryCellClocks::new(alloc_timestamp, alloc_index), + )), + } + } + + fn reset_clocks(&mut self, offset: Size, len: Size) { + let mut alloc_ranges = self.alloc_ranges.borrow_mut(); + for (_, range) in alloc_ranges.iter_mut(offset, len) { + // Reset the portion of the range + *range = MemoryCellClocks::new(0, VectorIdx::MAX_INDEX); } } // Find an index, if one exists where the value // in `l` is greater than the value in `r`. fn find_gt_index(l: &VClock, r: &VClock) -> Option { + log::trace!("Find index where not {:?} <= {:?}", l, r); let l_slice = l.as_slice(); let r_slice = r.as_slice(); l_slice @@ -673,7 +806,7 @@ fn find_gt_index(l: &VClock, r: &VClock) -> Option { .enumerate() .find_map(|(idx, &r)| if r == 0 { None } else { Some(idx) }) .expect("Invalid VClock Invariant"); - Some(idx) + Some(idx + r_slice.len()) } else { None } @@ -683,9 +816,9 @@ fn find_gt_index(l: &VClock, r: &VClock) -> Option { /// Report a data-race found in the program. /// This finds the two racing threads and the type - /// of data-race that occured. This will also + /// of data-race that occurred. This will also /// return info about the memory location the data-race - /// occured in. + /// occurred in. #[cold] #[inline(never)] fn report_data_race<'tcx>( @@ -704,18 +837,18 @@ fn report_data_race<'tcx>( // Convert the write action into the vector clock it // represents for diagnostic purposes. write_clock = VClock::new_with_index(range.write_index, range.write); - ("WRITE", range.write_index, &write_clock) + (range.write_type.get_descriptor(), range.write_index, &write_clock) } else if let Some(idx) = Self::find_gt_index(&range.read, ¤t_clocks.clock) { - ("READ", idx, &range.read) + ("Read", idx, &range.read) } else if !is_atomic { if let Some(atomic) = range.atomic() { if let Some(idx) = Self::find_gt_index(&atomic.write_vector, ¤t_clocks.clock) { - ("ATOMIC_STORE", idx, &atomic.write_vector) + ("Atomic Store", idx, &atomic.write_vector) } else if let Some(idx) = Self::find_gt_index(&atomic.read_vector, ¤t_clocks.clock) { - ("ATOMIC_LOAD", idx, &atomic.read_vector) + ("Atomic Load", idx, &atomic.read_vector) } else { unreachable!( "Failed to report data-race for non-atomic operation: no race found" @@ -737,8 +870,7 @@ fn report_data_race<'tcx>( // Throw the data-race detection. throw_ub_format!( "Data race detected between {} on {} and {} on {}, memory({:?},offset={},size={})\ - \n\t\t -current vector clock = {:?}\ - \n\t\t -conflicting timestamp = {:?}", + \n(current vector clock = {:?}, conflicting timestamp = {:?})", action, current_thread_info, other_action, @@ -751,7 +883,7 @@ fn report_data_race<'tcx>( ) } - /// Detect data-races for an unsychronized read operation, will not perform + /// Detect data-races for an unsynchronized read operation, will not perform /// data-race detection if `multi-threaded` is false, either due to no threads /// being created or if it is temporarily disabled during a racy read or write /// operation for which data-race detection is handled separately, for example @@ -766,7 +898,7 @@ pub fn read<'tcx>(&self, pointer: Pointer, len: Size) -> InterpResult<'tcx> return Self::report_data_race( &self.global, range, - "READ", + "Read", false, pointer, len, @@ -784,17 +916,17 @@ fn unique_access<'tcx>( &mut self, pointer: Pointer, len: Size, - action: &str, + write_type: WriteType, ) -> InterpResult<'tcx> { if self.global.multi_threaded.get() { let (index, clocks) = self.global.current_thread_state(); for (_, range) in self.alloc_ranges.get_mut().iter_mut(pointer.offset, len) { - if let Err(DataRace) = range.write_race_detect(&*clocks, index) { + if let Err(DataRace) = range.write_race_detect(&*clocks, index, write_type) { // Report data-race return Self::report_data_race( &self.global, range, - action, + write_type.get_descriptor(), false, pointer, len, @@ -807,27 +939,27 @@ fn unique_access<'tcx>( } } - /// Detect data-races for an unsychronized write operation, will not perform + /// Detect data-races for an unsynchronized write operation, will not perform /// data-race threads if `multi-threaded` is false, either due to no threads /// being created or if it is temporarily disabled during a racy read or write /// operation pub fn write<'tcx>(&mut self, pointer: Pointer, len: Size) -> InterpResult<'tcx> { - self.unique_access(pointer, len, "Write") + self.unique_access(pointer, len, WriteType::Write) } - /// Detect data-races for an unsychronized deallocate operation, will not perform + /// Detect data-races for an unsynchronized deallocate operation, will not perform /// data-race threads if `multi-threaded` is false, either due to no threads /// being created or if it is temporarily disabled during a racy read or write /// operation pub fn deallocate<'tcx>(&mut self, pointer: Pointer, len: Size) -> InterpResult<'tcx> { - self.unique_access(pointer, len, "Deallocate") + self.unique_access(pointer, len, WriteType::Deallocate) } } impl<'mir, 'tcx: 'mir> EvalContextPrivExt<'mir, 'tcx> for MiriEvalContext<'mir, 'tcx> {} trait EvalContextPrivExt<'mir, 'tcx: 'mir>: MiriEvalContextExt<'mir, 'tcx> { // Temporarily allow data-races to occur, this should only be - // used if either one of the appropiate `validate_atomic` functions + // used if either one of the appropriate `validate_atomic` functions // will be called to treat a memory access as atomic or if the memory // being accessed should be treated as internal state, that cannot be // accessed by the interpreted program. @@ -875,7 +1007,7 @@ fn allow_data_races_mut( /// atomic-stores/atomic-rmw? fn validate_atomic_op( &self, - place: MPlaceTy<'tcx, Tag>, + place: &MPlaceTy<'tcx, Tag>, atomic: A, description: &str, mut op: impl FnMut( @@ -917,10 +1049,13 @@ fn validate_atomic_op( true, place_ptr, size, - ); + ) + .map(|_| true); } } - Ok(()) + + // This conservatively assumes all operations have release semantics + Ok(true) })?; // Log changes to atomic memory. @@ -987,7 +1122,7 @@ pub struct GlobalState { /// if a vector index is re-assigned to a new thread. vector_info: RefCell>, - /// The mapping of a given thread to assocaited thread metadata. + /// The mapping of a given thread to associated thread metadata. thread_info: RefCell>, /// The current vector index being executed. @@ -1004,7 +1139,7 @@ pub struct GlobalState { /// Counts the number of threads that are currently active /// if the number of active threads reduces to 1 and then - /// a join operation occures with the remaining main thread + /// a join operation occurs with the remaining main thread /// then multi-threaded execution may be disabled. active_thread_count: Cell, @@ -1124,6 +1259,8 @@ pub fn thread_created(&self, thread: ThreadId) { vector_info.push(thread) }; + log::trace!("Creating thread = {:?} with vector index = {:?}", thread, created_index); + // Mark the chosen vector index as in use by the thread. thread_info[thread].vector_index = Some(created_index); @@ -1136,20 +1273,18 @@ pub fn thread_created(&self, thread: ThreadId) { // Now load the two clocks and configure the initial state. let (current, created) = vector_clocks.pick2_mut(current_index, created_index); - // Advance the current thread before the synchronized operation. - current.increment_clock(current_index); - // Join the created with current, since the current threads // previous actions happen-before the created thread. created.join_with(current); // Advance both threads after the synchronized operation. + // Both operations are considered to have release semantics. current.increment_clock(current_index); created.increment_clock(created_index); } /// Hook on a thread join to update the implicit happens-before relation - /// between the joined thead and the current thread. + /// between the joined thread and the current thread. #[inline] pub fn thread_joined(&self, current_thread: ThreadId, join_thread: ThreadId) { let mut clocks_vec = self.vector_clocks.borrow_mut(); @@ -1167,16 +1302,11 @@ pub fn thread_joined(&self, current_thread: ThreadId, join_thread: ThreadId) { .as_ref() .expect("Joined with thread but thread has not terminated"); - // Pre increment clocks before atomic operation. - current.increment_clock(current_index); - // The join thread happens-before the current thread // so update the current vector clock. + // Is not a release operation so the clock is not incremented. current.clock.join(join_clock); - // Post increment clocks after atomic operation. - current.increment_clock(current_index); - // Check the number of active threads, if the value is 1 // then test for potentially disabling multi-threaded execution. let active_threads = self.active_thread_count.get(); @@ -1187,7 +1317,7 @@ pub fn thread_joined(&self, current_thread: ThreadId, join_thread: ThreadId) { .iter_enumerated() .all(|(idx, clocks)| clocks.clock[idx] <= current_clock.clock[idx]) { - // The all thread termations happen-before the current clock + // All thread terminations happen-before the current clock // therefore no data-races can be reported until a new thread // is created, so disable multi-threaded execution. self.multi_threaded.set(false); @@ -1206,7 +1336,7 @@ pub fn thread_joined(&self, current_thread: ThreadId, join_thread: ThreadId) { /// On thread termination, the vector-clock may re-used /// in the future once all remaining thread-clocks catch /// up with the time index of the terminated thread. - /// This assiges thread termination with a unique index + /// This assigns thread termination with a unique index /// which will be used to join the thread /// This should be called strictly before any calls to /// `thread_joined`. @@ -1274,14 +1404,14 @@ pub fn thread_set_name(&self, thread: ThreadId, name: String) { /// operation may create. fn maybe_perform_sync_operation<'tcx>( &self, - op: impl FnOnce(VectorIdx, RefMut<'_, ThreadClockSet>) -> InterpResult<'tcx>, + op: impl FnOnce(VectorIdx, RefMut<'_, ThreadClockSet>) -> InterpResult<'tcx, bool>, ) -> InterpResult<'tcx> { if self.multi_threaded.get() { - let (index, mut clocks) = self.current_thread_state_mut(); - clocks.increment_clock(index); - op(index, clocks)?; - let (_, mut clocks) = self.current_thread_state_mut(); - clocks.increment_clock(index); + let (index, clocks) = self.current_thread_state_mut(); + if op(index, clocks)? { + let (_, mut clocks) = self.current_thread_state_mut(); + clocks.increment_clock(index); + } } Ok(()) } @@ -1301,18 +1431,21 @@ fn print_thread_metadata(&self, vector: VectorIdx) -> String { /// Acquire a lock, express that the previous call of /// `validate_lock_release` must happen before this. + /// As this is an acquire operation, the thread timestamp is not + /// incremented. pub fn validate_lock_acquire(&self, lock: &VClock, thread: ThreadId) { - let (index, mut clocks) = self.load_thread_state_mut(thread); - clocks.increment_clock(index); + let (_, mut clocks) = self.load_thread_state_mut(thread); clocks.clock.join(&lock); - clocks.increment_clock(index); } /// Release a lock handle, express that this happens-before /// any subsequent calls to `validate_lock_acquire`. + /// For normal locks this should be equivalent to `validate_lock_release_shared` + /// since an acquire operation should have occurred before, however + /// for futex & condvar operations this is not the case and this + /// operation must be used. pub fn validate_lock_release(&self, lock: &mut VClock, thread: ThreadId) { let (index, mut clocks) = self.load_thread_state_mut(thread); - clocks.increment_clock(index); lock.clone_from(&clocks.clock); clocks.increment_clock(index); } @@ -1321,9 +1454,11 @@ pub fn validate_lock_release(&self, lock: &mut VClock, thread: ThreadId) { /// any subsequent calls to `validate_lock_acquire` as well /// as any previous calls to this function after any /// `validate_lock_release` calls. + /// For normal locks this should be equivalent to `validate_lock_release`. + /// This function only exists for joining over the set of concurrent readers + /// in a read-write lock and should not be used for anything else. pub fn validate_lock_release_shared(&self, lock: &mut VClock, thread: ThreadId) { let (index, mut clocks) = self.load_thread_state_mut(thread); - clocks.increment_clock(index); lock.join(&clocks.clock); clocks.increment_clock(index); }