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. 6 //! 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. 11 //! 12 //! The implementation also models races with memory allocation and deallocation via treating allocation and 13 //! deallocation as a type of write internally for detecting data-races. 14 //! 15 //! This does not explore weak memory orders and so can still miss data-races 16 //! but should not report false-positives 17 //! 18 //! Data-race definition from(https://en.cppreference.com/w/cpp/language/memory_model#Threads_and_data_races): 19 //! a data race occurs between two memory accesses if they are on different threads, at least one operation 20 //! is non-atomic, at least one operation is a write and neither access happens-before the other. Read the link 21 //! for full definition. 22 //! 23 //! This re-uses vector indexes for threads that are known to be unable to report data-races, this is valid 24 //! because it only re-uses vector indexes once all currently-active (not-terminated) threads have an internal 25 //! vector clock that happens-after the join operation of the candidate thread. Threads that have not been joined 26 //! on are not considered. Since the thread's vector clock will only increase and a data-race implies that 27 //! there is some index x where clock[x] > thread_clock, when this is true clock[candidate-idx] > thread_clock 28 //! can never hold and hence a data-race can never be reported in that vector index again. 29 //! This means that the thread-index can be safely re-used, starting on the next timestamp for the newly created 30 //! thread. 31 //! 32 //! The sequentially consistent ordering corresponds to the ordering that the threads 33 //! are currently scheduled, this means that the data-race detector has no additional 34 //! logic for sequentially consistent accesses at the moment since they are indistinguishable 35 //! from acquire/release operations. If weak memory orderings are explored then this 36 //! may need to change or be updated accordingly. 37 //! 38 //! Per the C++ spec for the memory model a sequentially consistent operation: 39 //! "A load operation with this memory order performs an acquire operation, 40 //! a store performs a release operation, and read-modify-write performs 41 //! both an acquire operation and a release operation, plus a single total 42 //! order exists in which all threads observe all modifications in the same 43 //! order (see Sequentially-consistent ordering below) " 44 //! So in the absence of weak memory effects a seq-cst load & a seq-cst store is identical 45 //! to an acquire load and a release store given the global sequentially consistent order 46 //! of the schedule. 47 //! 48 //! The timestamps used in the data-race detector assign each sequence of non-atomic operations 49 //! followed by a single atomic or concurrent operation a single timestamp. 50 //! Write, Read, Write, ThreadJoin will be represented by a single timestamp value on a thread. 51 //! This is because extra increment operations between the operations in the sequence are not 52 //! required for accurate reporting of data-race values. 53 //! 54 //! As per the paper a threads timestamp is only incremented after a release operation is performed 55 //! so some atomic operations that only perform acquires do not increment the timestamp. Due to shared 56 //! code some atomic operations may increment the timestamp when not necessary but this has no effect 57 //! on the data-race detection code. 58 //! 59 //! FIXME: 60 //! currently we have our own local copy of the currently active thread index and names, this is due 61 //! in part to the inability to access the current location of threads.active_thread inside the AllocExtra 62 //! read, write and deallocate functions and should be cleaned up in the future. 63 64 use std::{ 65 cell::{Cell, Ref, RefCell, RefMut}, 66 fmt::Debug, 67 mem, 68 }; 69 70 use rustc_data_structures::fx::{FxHashMap, FxHashSet}; 71 use rustc_index::vec::{Idx, IndexVec}; 72 use rustc_middle::{mir, ty::layout::TyAndLayout}; 73 use rustc_target::abi::Size; 74 75 use crate::{ 76 AllocId, AllocRange, ImmTy, Immediate, InterpResult, MPlaceTy, MemPlaceMeta, MemoryKind, 77 MiriEvalContext, MiriEvalContextExt, MiriMemoryKind, OpTy, Pointer, RangeMap, Scalar, 78 ScalarMaybeUninit, Tag, ThreadId, VClock, VTimestamp, VectorIdx, 79 }; 80 81 pub type AllocExtra = VClockAlloc; 82 pub type MemoryExtra = GlobalState; 83 84 /// Valid atomic read-write operations, alias of atomic::Ordering (not non-exhaustive). 85 #[derive(Copy, Clone, PartialEq, Eq, Debug)] 86 pub enum AtomicRwOp { 87 Relaxed, 88 Acquire, 89 Release, 90 AcqRel, 91 SeqCst, 92 } 93 94 /// Valid atomic read operations, subset of atomic::Ordering. 95 #[derive(Copy, Clone, PartialEq, Eq, Debug)] 96 pub enum AtomicReadOp { 97 Relaxed, 98 Acquire, 99 SeqCst, 100 } 101 102 /// Valid atomic write operations, subset of atomic::Ordering. 103 #[derive(Copy, Clone, PartialEq, Eq, Debug)] 104 pub enum AtomicWriteOp { 105 Relaxed, 106 Release, 107 SeqCst, 108 } 109 110 /// Valid atomic fence operations, subset of atomic::Ordering. 111 #[derive(Copy, Clone, PartialEq, Eq, Debug)] 112 pub enum AtomicFenceOp { 113 Acquire, 114 Release, 115 AcqRel, 116 SeqCst, 117 } 118 119 /// The current set of vector clocks describing the state 120 /// of a thread, contains the happens-before clock and 121 /// additional metadata to model atomic fence operations. 122 #[derive(Clone, Default, Debug)] 123 struct ThreadClockSet { 124 /// The increasing clock representing timestamps 125 /// that happen-before this thread. 126 clock: VClock, 127 128 /// The set of timestamps that will happen-before this 129 /// thread once it performs an acquire fence. 130 fence_acquire: VClock, 131 132 /// The last timestamp of happens-before relations that 133 /// have been released by this thread by a fence. 134 fence_release: VClock, 135 } 136 137 impl ThreadClockSet { 138 /// Apply the effects of a release fence to this 139 /// set of thread vector clocks. 140 #[inline] apply_release_fence(&mut self)141 fn apply_release_fence(&mut self) { 142 self.fence_release.clone_from(&self.clock); 143 } 144 145 /// Apply the effects of an acquire fence to this 146 /// set of thread vector clocks. 147 #[inline] apply_acquire_fence(&mut self)148 fn apply_acquire_fence(&mut self) { 149 self.clock.join(&self.fence_acquire); 150 } 151 152 /// Increment the happens-before clock at a 153 /// known index. 154 #[inline] increment_clock(&mut self, index: VectorIdx)155 fn increment_clock(&mut self, index: VectorIdx) { 156 self.clock.increment_index(index); 157 } 158 159 /// Join the happens-before clock with that of 160 /// another thread, used to model thread join 161 /// operations. join_with(&mut self, other: &ThreadClockSet)162 fn join_with(&mut self, other: &ThreadClockSet) { 163 self.clock.join(&other.clock); 164 } 165 } 166 167 /// Error returned by finding a data race 168 /// should be elaborated upon. 169 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)] 170 pub struct DataRace; 171 172 /// Externally stored memory cell clocks 173 /// explicitly to reduce memory usage for the 174 /// common case where no atomic operations 175 /// exists on the memory cell. 176 #[derive(Clone, PartialEq, Eq, Default, Debug)] 177 struct AtomicMemoryCellClocks { 178 /// The clock-vector of the timestamp of the last atomic 179 /// read operation performed by each thread. 180 /// This detects potential data-races between atomic read 181 /// and non-atomic write operations. 182 read_vector: VClock, 183 184 /// The clock-vector of the timestamp of the last atomic 185 /// write operation performed by each thread. 186 /// This detects potential data-races between atomic write 187 /// and non-atomic read or write operations. 188 write_vector: VClock, 189 190 /// Synchronization vector for acquire-release semantics 191 /// contains the vector of timestamps that will 192 /// happen-before a thread if an acquire-load is 193 /// performed on the data. 194 sync_vector: VClock, 195 } 196 197 /// Type of write operation: allocating memory 198 /// non-atomic writes and deallocating memory 199 /// are all treated as writes for the purpose 200 /// of the data-race detector. 201 #[derive(Copy, Clone, PartialEq, Eq, Debug)] 202 enum WriteType { 203 /// Allocate memory. 204 Allocate, 205 206 /// Standard unsynchronized write. 207 Write, 208 209 /// Deallocate memory. 210 /// Note that when memory is deallocated first, later non-atomic accesses 211 /// will be reported as use-after-free, not as data races. 212 /// (Same for `Allocate` above.) 213 Deallocate, 214 } 215 impl WriteType { get_descriptor(self) -> &'static str216 fn get_descriptor(self) -> &'static str { 217 match self { 218 WriteType::Allocate => "Allocate", 219 WriteType::Write => "Write", 220 WriteType::Deallocate => "Deallocate", 221 } 222 } 223 } 224 225 /// Memory Cell vector clock metadata 226 /// for data-race detection. 227 #[derive(Clone, PartialEq, Eq, Debug)] 228 struct MemoryCellClocks { 229 /// The vector-clock timestamp of the last write 230 /// corresponding to the writing threads timestamp. 231 write: VTimestamp, 232 233 /// The identifier of the vector index, corresponding to a thread 234 /// that performed the last write operation. 235 write_index: VectorIdx, 236 237 /// The type of operation that the write index represents, 238 /// either newly allocated memory, a non-atomic write or 239 /// a deallocation of memory. 240 write_type: WriteType, 241 242 /// The vector-clock of the timestamp of the last read operation 243 /// performed by a thread since the last write operation occurred. 244 /// It is reset to zero on each write operation. 245 read: VClock, 246 247 /// Atomic acquire & release sequence tracking clocks. 248 /// For non-atomic memory in the common case this 249 /// value is set to None. 250 atomic_ops: Option<Box<AtomicMemoryCellClocks>>, 251 } 252 253 impl MemoryCellClocks { 254 /// Create a new set of clocks representing memory allocated 255 /// at a given vector timestamp and index. new(alloc: VTimestamp, alloc_index: VectorIdx) -> Self256 fn new(alloc: VTimestamp, alloc_index: VectorIdx) -> Self { 257 MemoryCellClocks { 258 read: VClock::default(), 259 write: alloc, 260 write_index: alloc_index, 261 write_type: WriteType::Allocate, 262 atomic_ops: None, 263 } 264 } 265 266 /// Load the internal atomic memory cells if they exist. 267 #[inline] atomic(&self) -> Option<&AtomicMemoryCellClocks>268 fn atomic(&self) -> Option<&AtomicMemoryCellClocks> { 269 match &self.atomic_ops { 270 Some(op) => Some(&*op), 271 None => None, 272 } 273 } 274 275 /// Load or create the internal atomic memory metadata 276 /// if it does not exist. 277 #[inline] atomic_mut(&mut self) -> &mut AtomicMemoryCellClocks278 fn atomic_mut(&mut self) -> &mut AtomicMemoryCellClocks { 279 self.atomic_ops.get_or_insert_with(Default::default) 280 } 281 282 /// Update memory cell data-race tracking for atomic 283 /// load acquire semantics, is a no-op if this memory was 284 /// not used previously as atomic memory. load_acquire( &mut self, clocks: &mut ThreadClockSet, index: VectorIdx, ) -> Result<(), DataRace>285 fn load_acquire( 286 &mut self, 287 clocks: &mut ThreadClockSet, 288 index: VectorIdx, 289 ) -> Result<(), DataRace> { 290 self.atomic_read_detect(clocks, index)?; 291 if let Some(atomic) = self.atomic() { 292 clocks.clock.join(&atomic.sync_vector); 293 } 294 Ok(()) 295 } 296 297 /// Update memory cell data-race tracking for atomic 298 /// load relaxed semantics, is a no-op if this memory was 299 /// not used previously as atomic memory. load_relaxed( &mut self, clocks: &mut ThreadClockSet, index: VectorIdx, ) -> Result<(), DataRace>300 fn load_relaxed( 301 &mut self, 302 clocks: &mut ThreadClockSet, 303 index: VectorIdx, 304 ) -> Result<(), DataRace> { 305 self.atomic_read_detect(clocks, index)?; 306 if let Some(atomic) = self.atomic() { 307 clocks.fence_acquire.join(&atomic.sync_vector); 308 } 309 Ok(()) 310 } 311 312 /// Update the memory cell data-race tracking for atomic 313 /// store release semantics. store_release(&mut self, clocks: &ThreadClockSet, index: VectorIdx) -> Result<(), DataRace>314 fn store_release(&mut self, clocks: &ThreadClockSet, index: VectorIdx) -> Result<(), DataRace> { 315 self.atomic_write_detect(clocks, index)?; 316 let atomic = self.atomic_mut(); 317 atomic.sync_vector.clone_from(&clocks.clock); 318 Ok(()) 319 } 320 321 /// Update the memory cell data-race tracking for atomic 322 /// store relaxed semantics. store_relaxed(&mut self, clocks: &ThreadClockSet, index: VectorIdx) -> Result<(), DataRace>323 fn store_relaxed(&mut self, clocks: &ThreadClockSet, index: VectorIdx) -> Result<(), DataRace> { 324 self.atomic_write_detect(clocks, index)?; 325 326 // The handling of release sequences was changed in C++20 and so 327 // the code here is different to the paper since now all relaxed 328 // stores block release sequences. The exception for same-thread 329 // relaxed stores has been removed. 330 let atomic = self.atomic_mut(); 331 atomic.sync_vector.clone_from(&clocks.fence_release); 332 Ok(()) 333 } 334 335 /// Update the memory cell data-race tracking for atomic 336 /// store release semantics for RMW operations. rmw_release(&mut self, clocks: &ThreadClockSet, index: VectorIdx) -> Result<(), DataRace>337 fn rmw_release(&mut self, clocks: &ThreadClockSet, index: VectorIdx) -> Result<(), DataRace> { 338 self.atomic_write_detect(clocks, index)?; 339 let atomic = self.atomic_mut(); 340 atomic.sync_vector.join(&clocks.clock); 341 Ok(()) 342 } 343 344 /// Update the memory cell data-race tracking for atomic 345 /// store relaxed semantics for RMW operations. rmw_relaxed(&mut self, clocks: &ThreadClockSet, index: VectorIdx) -> Result<(), DataRace>346 fn rmw_relaxed(&mut self, clocks: &ThreadClockSet, index: VectorIdx) -> Result<(), DataRace> { 347 self.atomic_write_detect(clocks, index)?; 348 let atomic = self.atomic_mut(); 349 atomic.sync_vector.join(&clocks.fence_release); 350 Ok(()) 351 } 352 353 /// Detect data-races with an atomic read, caused by a non-atomic write that does 354 /// not happen-before the atomic-read. atomic_read_detect( &mut self, clocks: &ThreadClockSet, index: VectorIdx, ) -> Result<(), DataRace>355 fn atomic_read_detect( 356 &mut self, 357 clocks: &ThreadClockSet, 358 index: VectorIdx, 359 ) -> Result<(), DataRace> { 360 log::trace!("Atomic read with vectors: {:#?} :: {:#?}", self, clocks); 361 if self.write <= clocks.clock[self.write_index] { 362 let atomic = self.atomic_mut(); 363 atomic.read_vector.set_at_index(&clocks.clock, index); 364 Ok(()) 365 } else { 366 Err(DataRace) 367 } 368 } 369 370 /// Detect data-races with an atomic write, either with a non-atomic read or with 371 /// a non-atomic write. atomic_write_detect( &mut self, clocks: &ThreadClockSet, index: VectorIdx, ) -> Result<(), DataRace>372 fn atomic_write_detect( 373 &mut self, 374 clocks: &ThreadClockSet, 375 index: VectorIdx, 376 ) -> Result<(), DataRace> { 377 log::trace!("Atomic write with vectors: {:#?} :: {:#?}", self, clocks); 378 if self.write <= clocks.clock[self.write_index] && self.read <= clocks.clock { 379 let atomic = self.atomic_mut(); 380 atomic.write_vector.set_at_index(&clocks.clock, index); 381 Ok(()) 382 } else { 383 Err(DataRace) 384 } 385 } 386 387 /// Detect races for non-atomic read operations at the current memory cell 388 /// returns true if a data-race is detected. read_race_detect( &mut self, clocks: &ThreadClockSet, index: VectorIdx, ) -> Result<(), DataRace>389 fn read_race_detect( 390 &mut self, 391 clocks: &ThreadClockSet, 392 index: VectorIdx, 393 ) -> Result<(), DataRace> { 394 log::trace!("Unsynchronized read with vectors: {:#?} :: {:#?}", self, clocks); 395 if self.write <= clocks.clock[self.write_index] { 396 let race_free = if let Some(atomic) = self.atomic() { 397 atomic.write_vector <= clocks.clock 398 } else { 399 true 400 }; 401 if race_free { 402 self.read.set_at_index(&clocks.clock, index); 403 Ok(()) 404 } else { 405 Err(DataRace) 406 } 407 } else { 408 Err(DataRace) 409 } 410 } 411 412 /// Detect races for non-atomic write operations at the current memory cell 413 /// returns true if a data-race is detected. write_race_detect( &mut self, clocks: &ThreadClockSet, index: VectorIdx, write_type: WriteType, ) -> Result<(), DataRace>414 fn write_race_detect( 415 &mut self, 416 clocks: &ThreadClockSet, 417 index: VectorIdx, 418 write_type: WriteType, 419 ) -> Result<(), DataRace> { 420 log::trace!("Unsynchronized write with vectors: {:#?} :: {:#?}", self, clocks); 421 if self.write <= clocks.clock[self.write_index] && self.read <= clocks.clock { 422 let race_free = if let Some(atomic) = self.atomic() { 423 atomic.write_vector <= clocks.clock && atomic.read_vector <= clocks.clock 424 } else { 425 true 426 }; 427 if race_free { 428 self.write = clocks.clock[index]; 429 self.write_index = index; 430 self.write_type = write_type; 431 self.read.set_zero_vector(); 432 Ok(()) 433 } else { 434 Err(DataRace) 435 } 436 } else { 437 Err(DataRace) 438 } 439 } 440 } 441 442 /// Evaluation context extensions. 443 impl<'mir, 'tcx: 'mir> EvalContextExt<'mir, 'tcx> for MiriEvalContext<'mir, 'tcx> {} 444 pub trait EvalContextExt<'mir, 'tcx: 'mir>: MiriEvalContextExt<'mir, 'tcx> { 445 /// Atomic variant of read_scalar_at_offset. read_scalar_at_offset_atomic( &self, op: &OpTy<'tcx, Tag>, offset: u64, layout: TyAndLayout<'tcx>, atomic: AtomicReadOp, ) -> InterpResult<'tcx, ScalarMaybeUninit<Tag>>446 fn read_scalar_at_offset_atomic( 447 &self, 448 op: &OpTy<'tcx, Tag>, 449 offset: u64, 450 layout: TyAndLayout<'tcx>, 451 atomic: AtomicReadOp, 452 ) -> InterpResult<'tcx, ScalarMaybeUninit<Tag>> { 453 let this = self.eval_context_ref(); 454 let op_place = this.deref_operand(op)?; 455 let offset = Size::from_bytes(offset); 456 457 // Ensure that the following read at an offset is within bounds. 458 assert!(op_place.layout.size >= offset + layout.size); 459 let value_place = op_place.offset(offset, MemPlaceMeta::None, layout, this)?; 460 this.read_scalar_atomic(&value_place, atomic) 461 } 462 463 /// Atomic variant of write_scalar_at_offset. write_scalar_at_offset_atomic( &mut self, op: &OpTy<'tcx, Tag>, offset: u64, value: impl Into<ScalarMaybeUninit<Tag>>, layout: TyAndLayout<'tcx>, atomic: AtomicWriteOp, ) -> InterpResult<'tcx>464 fn write_scalar_at_offset_atomic( 465 &mut self, 466 op: &OpTy<'tcx, Tag>, 467 offset: u64, 468 value: impl Into<ScalarMaybeUninit<Tag>>, 469 layout: TyAndLayout<'tcx>, 470 atomic: AtomicWriteOp, 471 ) -> InterpResult<'tcx> { 472 let this = self.eval_context_mut(); 473 let op_place = this.deref_operand(op)?; 474 let offset = Size::from_bytes(offset); 475 476 // Ensure that the following read at an offset is within bounds. 477 assert!(op_place.layout.size >= offset + layout.size); 478 let value_place = op_place.offset(offset, MemPlaceMeta::None, layout, this)?; 479 this.write_scalar_atomic(value.into(), &value_place, atomic) 480 } 481 482 /// Perform an atomic read operation at the memory location. read_scalar_atomic( &self, place: &MPlaceTy<'tcx, Tag>, atomic: AtomicReadOp, ) -> InterpResult<'tcx, ScalarMaybeUninit<Tag>>483 fn read_scalar_atomic( 484 &self, 485 place: &MPlaceTy<'tcx, Tag>, 486 atomic: AtomicReadOp, 487 ) -> InterpResult<'tcx, ScalarMaybeUninit<Tag>> { 488 let this = self.eval_context_ref(); 489 let scalar = this.allow_data_races_ref(move |this| this.read_scalar(&place.into()))?; 490 this.validate_atomic_load(place, atomic)?; 491 Ok(scalar) 492 } 493 494 /// Perform an atomic write operation at the memory location. write_scalar_atomic( &mut self, val: ScalarMaybeUninit<Tag>, dest: &MPlaceTy<'tcx, Tag>, atomic: AtomicWriteOp, ) -> InterpResult<'tcx>495 fn write_scalar_atomic( 496 &mut self, 497 val: ScalarMaybeUninit<Tag>, 498 dest: &MPlaceTy<'tcx, Tag>, 499 atomic: AtomicWriteOp, 500 ) -> InterpResult<'tcx> { 501 let this = self.eval_context_mut(); 502 this.allow_data_races_mut(move |this| this.write_scalar(val, &(*dest).into()))?; 503 this.validate_atomic_store(dest, atomic) 504 } 505 506 /// Perform an atomic operation on a memory location. atomic_op_immediate( &mut self, place: &MPlaceTy<'tcx, Tag>, rhs: &ImmTy<'tcx, Tag>, op: mir::BinOp, neg: bool, atomic: AtomicRwOp, ) -> InterpResult<'tcx, ImmTy<'tcx, Tag>>507 fn atomic_op_immediate( 508 &mut self, 509 place: &MPlaceTy<'tcx, Tag>, 510 rhs: &ImmTy<'tcx, Tag>, 511 op: mir::BinOp, 512 neg: bool, 513 atomic: AtomicRwOp, 514 ) -> InterpResult<'tcx, ImmTy<'tcx, Tag>> { 515 let this = self.eval_context_mut(); 516 517 let old = this.allow_data_races_mut(|this| this.read_immediate(&place.into()))?; 518 519 // Atomics wrap around on overflow. 520 let val = this.binary_op(op, &old, rhs)?; 521 let val = if neg { this.unary_op(mir::UnOp::Not, &val)? } else { val }; 522 this.allow_data_races_mut(|this| this.write_immediate(*val, &(*place).into()))?; 523 524 this.validate_atomic_rmw(place, atomic)?; 525 Ok(old) 526 } 527 528 /// Perform an atomic exchange with a memory place and a new 529 /// scalar value, the old value is returned. atomic_exchange_scalar( &mut self, place: &MPlaceTy<'tcx, Tag>, new: ScalarMaybeUninit<Tag>, atomic: AtomicRwOp, ) -> InterpResult<'tcx, ScalarMaybeUninit<Tag>>530 fn atomic_exchange_scalar( 531 &mut self, 532 place: &MPlaceTy<'tcx, Tag>, 533 new: ScalarMaybeUninit<Tag>, 534 atomic: AtomicRwOp, 535 ) -> InterpResult<'tcx, ScalarMaybeUninit<Tag>> { 536 let this = self.eval_context_mut(); 537 538 let old = this.allow_data_races_mut(|this| this.read_scalar(&place.into()))?; 539 this.allow_data_races_mut(|this| this.write_scalar(new, &(*place).into()))?; 540 this.validate_atomic_rmw(place, atomic)?; 541 Ok(old) 542 } 543 544 /// Perform an conditional atomic exchange with a memory place and a new 545 /// scalar value, the old value is returned. atomic_min_max_scalar( &mut self, place: &MPlaceTy<'tcx, Tag>, rhs: ImmTy<'tcx, Tag>, min: bool, atomic: AtomicRwOp, ) -> InterpResult<'tcx, ImmTy<'tcx, Tag>>546 fn atomic_min_max_scalar( 547 &mut self, 548 place: &MPlaceTy<'tcx, Tag>, 549 rhs: ImmTy<'tcx, Tag>, 550 min: bool, 551 atomic: AtomicRwOp, 552 ) -> InterpResult<'tcx, ImmTy<'tcx, Tag>> { 553 let this = self.eval_context_mut(); 554 555 let old = this.allow_data_races_mut(|this| this.read_immediate(&place.into()))?; 556 let lt = this.overflowing_binary_op(mir::BinOp::Lt, &old, &rhs)?.0.to_bool()?; 557 558 let new_val = if min { 559 if lt { &old } else { &rhs } 560 } else { 561 if lt { &rhs } else { &old } 562 }; 563 564 this.allow_data_races_mut(|this| this.write_immediate(**new_val, &(*place).into()))?; 565 566 this.validate_atomic_rmw(&place, atomic)?; 567 568 // Return the old value. 569 Ok(old) 570 } 571 572 /// Perform an atomic compare and exchange at a given memory location. 573 /// On success an atomic RMW operation is performed and on failure 574 /// only an atomic read occurs. If `can_fail_spuriously` is true, 575 /// then we treat it as a "compare_exchange_weak" operation, and 576 /// some portion of the time fail even when the values are actually 577 /// identical. atomic_compare_exchange_scalar( &mut self, place: &MPlaceTy<'tcx, Tag>, expect_old: &ImmTy<'tcx, Tag>, new: ScalarMaybeUninit<Tag>, success: AtomicRwOp, fail: AtomicReadOp, can_fail_spuriously: bool, ) -> InterpResult<'tcx, Immediate<Tag>>578 fn atomic_compare_exchange_scalar( 579 &mut self, 580 place: &MPlaceTy<'tcx, Tag>, 581 expect_old: &ImmTy<'tcx, Tag>, 582 new: ScalarMaybeUninit<Tag>, 583 success: AtomicRwOp, 584 fail: AtomicReadOp, 585 can_fail_spuriously: bool, 586 ) -> InterpResult<'tcx, Immediate<Tag>> { 587 use rand::Rng as _; 588 let this = self.eval_context_mut(); 589 590 // Failure ordering cannot be stronger than success ordering, therefore first attempt 591 // to read with the failure ordering and if successful then try again with the success 592 // read ordering and write in the success case. 593 // Read as immediate for the sake of `binary_op()` 594 let old = this.allow_data_races_mut(|this| this.read_immediate(&(place.into())))?; 595 // `binary_op` will bail if either of them is not a scalar. 596 let eq = this.overflowing_binary_op(mir::BinOp::Eq, &old, expect_old)?.0; 597 // If the operation would succeed, but is "weak", fail some portion 598 // of the time, based on `rate`. 599 let rate = this.memory.extra.cmpxchg_weak_failure_rate; 600 let cmpxchg_success = eq.to_bool()? 601 && (!can_fail_spuriously || this.memory.extra.rng.get_mut().gen::<f64>() < rate); 602 let res = Immediate::ScalarPair( 603 old.to_scalar_or_uninit(), 604 Scalar::from_bool(cmpxchg_success).into(), 605 ); 606 607 // Update ptr depending on comparison. 608 // if successful, perform a full rw-atomic validation 609 // otherwise treat this as an atomic load with the fail ordering. 610 if cmpxchg_success { 611 this.allow_data_races_mut(|this| this.write_scalar(new, &(*place).into()))?; 612 this.validate_atomic_rmw(place, success)?; 613 } else { 614 this.validate_atomic_load(place, fail)?; 615 } 616 617 // Return the old value. 618 Ok(res) 619 } 620 621 /// Update the data-race detector for an atomic read occurring at the 622 /// associated memory-place and on the current thread. validate_atomic_load( &self, place: &MPlaceTy<'tcx, Tag>, atomic: AtomicReadOp, ) -> InterpResult<'tcx>623 fn validate_atomic_load( 624 &self, 625 place: &MPlaceTy<'tcx, Tag>, 626 atomic: AtomicReadOp, 627 ) -> InterpResult<'tcx> { 628 let this = self.eval_context_ref(); 629 this.validate_atomic_op( 630 place, 631 atomic, 632 "Atomic Load", 633 move |memory, clocks, index, atomic| { 634 if atomic == AtomicReadOp::Relaxed { 635 memory.load_relaxed(&mut *clocks, index) 636 } else { 637 memory.load_acquire(&mut *clocks, index) 638 } 639 }, 640 ) 641 } 642 643 /// Update the data-race detector for an atomic write occurring at the 644 /// associated memory-place and on the current thread. validate_atomic_store( &mut self, place: &MPlaceTy<'tcx, Tag>, atomic: AtomicWriteOp, ) -> InterpResult<'tcx>645 fn validate_atomic_store( 646 &mut self, 647 place: &MPlaceTy<'tcx, Tag>, 648 atomic: AtomicWriteOp, 649 ) -> InterpResult<'tcx> { 650 let this = self.eval_context_mut(); 651 this.validate_atomic_op( 652 place, 653 atomic, 654 "Atomic Store", 655 move |memory, clocks, index, atomic| { 656 if atomic == AtomicWriteOp::Relaxed { 657 memory.store_relaxed(clocks, index) 658 } else { 659 memory.store_release(clocks, index) 660 } 661 }, 662 ) 663 } 664 665 /// Update the data-race detector for an atomic read-modify-write occurring 666 /// at the associated memory place and on the current thread. validate_atomic_rmw( &mut self, place: &MPlaceTy<'tcx, Tag>, atomic: AtomicRwOp, ) -> InterpResult<'tcx>667 fn validate_atomic_rmw( 668 &mut self, 669 place: &MPlaceTy<'tcx, Tag>, 670 atomic: AtomicRwOp, 671 ) -> InterpResult<'tcx> { 672 use AtomicRwOp::*; 673 let acquire = matches!(atomic, Acquire | AcqRel | SeqCst); 674 let release = matches!(atomic, Release | AcqRel | SeqCst); 675 let this = self.eval_context_mut(); 676 this.validate_atomic_op(place, atomic, "Atomic RMW", move |memory, clocks, index, _| { 677 if acquire { 678 memory.load_acquire(clocks, index)?; 679 } else { 680 memory.load_relaxed(clocks, index)?; 681 } 682 if release { 683 memory.rmw_release(clocks, index) 684 } else { 685 memory.rmw_relaxed(clocks, index) 686 } 687 }) 688 } 689 690 /// Update the data-race detector for an atomic fence on the current thread. validate_atomic_fence(&mut self, atomic: AtomicFenceOp) -> InterpResult<'tcx>691 fn validate_atomic_fence(&mut self, atomic: AtomicFenceOp) -> InterpResult<'tcx> { 692 let this = self.eval_context_mut(); 693 if let Some(data_race) = &mut this.memory.extra.data_race { 694 data_race.maybe_perform_sync_operation(move |index, mut clocks| { 695 log::trace!("Atomic fence on {:?} with ordering {:?}", index, atomic); 696 697 // Apply data-race detection for the current fences 698 // this treats AcqRel and SeqCst as the same as an acquire 699 // and release fence applied in the same timestamp. 700 if atomic != AtomicFenceOp::Release { 701 // Either Acquire | AcqRel | SeqCst 702 clocks.apply_acquire_fence(); 703 } 704 if atomic != AtomicFenceOp::Acquire { 705 // Either Release | AcqRel | SeqCst 706 clocks.apply_release_fence(); 707 } 708 709 // Increment timestamp in case of release semantics. 710 Ok(atomic != AtomicFenceOp::Acquire) 711 }) 712 } else { 713 Ok(()) 714 } 715 } 716 } 717 718 /// Vector clock metadata for a logical memory allocation. 719 #[derive(Debug, Clone)] 720 pub struct VClockAlloc { 721 /// Assigning each byte a MemoryCellClocks. 722 alloc_ranges: RefCell<RangeMap<MemoryCellClocks>>, 723 } 724 725 impl VClockAlloc { 726 /// Create a new data-race detector for newly allocated memory. new_allocation( global: &MemoryExtra, len: Size, kind: MemoryKind<MiriMemoryKind>, ) -> VClockAlloc727 pub fn new_allocation( 728 global: &MemoryExtra, 729 len: Size, 730 kind: MemoryKind<MiriMemoryKind>, 731 ) -> VClockAlloc { 732 let (alloc_timestamp, alloc_index) = match kind { 733 // User allocated and stack memory should track allocation. 734 MemoryKind::Machine( 735 MiriMemoryKind::Rust | MiriMemoryKind::C | MiriMemoryKind::WinHeap, 736 ) 737 | MemoryKind::Stack => { 738 let (alloc_index, clocks) = global.current_thread_state(); 739 let alloc_timestamp = clocks.clock[alloc_index]; 740 (alloc_timestamp, alloc_index) 741 } 742 // Other global memory should trace races but be allocated at the 0 timestamp. 743 MemoryKind::Machine( 744 MiriMemoryKind::Global 745 | MiriMemoryKind::Machine 746 | MiriMemoryKind::Env 747 | MiriMemoryKind::ExternStatic 748 | MiriMemoryKind::Tls, 749 ) 750 | MemoryKind::CallerLocation => (0, VectorIdx::MAX_INDEX), 751 }; 752 VClockAlloc { 753 alloc_ranges: RefCell::new(RangeMap::new( 754 len, 755 MemoryCellClocks::new(alloc_timestamp, alloc_index), 756 )), 757 } 758 } 759 760 // Find an index, if one exists where the value 761 // in `l` is greater than the value in `r`. find_gt_index(l: &VClock, r: &VClock) -> Option<VectorIdx>762 fn find_gt_index(l: &VClock, r: &VClock) -> Option<VectorIdx> { 763 log::trace!("Find index where not {:?} <= {:?}", l, r); 764 let l_slice = l.as_slice(); 765 let r_slice = r.as_slice(); 766 l_slice 767 .iter() 768 .zip(r_slice.iter()) 769 .enumerate() 770 .find_map(|(idx, (&l, &r))| if l > r { Some(idx) } else { None }) 771 .or_else(|| { 772 if l_slice.len() > r_slice.len() { 773 // By invariant, if l_slice is longer 774 // then one element must be larger. 775 // This just validates that this is true 776 // and reports earlier elements first. 777 let l_remainder_slice = &l_slice[r_slice.len()..]; 778 let idx = l_remainder_slice 779 .iter() 780 .enumerate() 781 .find_map(|(idx, &r)| if r == 0 { None } else { Some(idx) }) 782 .expect("Invalid VClock Invariant"); 783 Some(idx + r_slice.len()) 784 } else { 785 None 786 } 787 }) 788 .map(|idx| VectorIdx::new(idx)) 789 } 790 791 /// Report a data-race found in the program. 792 /// This finds the two racing threads and the type 793 /// of data-race that occurred. This will also 794 /// return info about the memory location the data-race 795 /// occurred in. 796 #[cold] 797 #[inline(never)] report_data_race<'tcx>( global: &MemoryExtra, range: &MemoryCellClocks, action: &str, is_atomic: bool, ptr_dbg: Pointer<AllocId>, ) -> InterpResult<'tcx>798 fn report_data_race<'tcx>( 799 global: &MemoryExtra, 800 range: &MemoryCellClocks, 801 action: &str, 802 is_atomic: bool, 803 ptr_dbg: Pointer<AllocId>, 804 ) -> InterpResult<'tcx> { 805 let (current_index, current_clocks) = global.current_thread_state(); 806 let write_clock; 807 let (other_action, other_thread, other_clock) = if range.write 808 > current_clocks.clock[range.write_index] 809 { 810 // Convert the write action into the vector clock it 811 // represents for diagnostic purposes. 812 write_clock = VClock::new_with_index(range.write_index, range.write); 813 (range.write_type.get_descriptor(), range.write_index, &write_clock) 814 } else if let Some(idx) = Self::find_gt_index(&range.read, ¤t_clocks.clock) { 815 ("Read", idx, &range.read) 816 } else if !is_atomic { 817 if let Some(atomic) = range.atomic() { 818 if let Some(idx) = Self::find_gt_index(&atomic.write_vector, ¤t_clocks.clock) 819 { 820 ("Atomic Store", idx, &atomic.write_vector) 821 } else if let Some(idx) = 822 Self::find_gt_index(&atomic.read_vector, ¤t_clocks.clock) 823 { 824 ("Atomic Load", idx, &atomic.read_vector) 825 } else { 826 unreachable!( 827 "Failed to report data-race for non-atomic operation: no race found" 828 ) 829 } 830 } else { 831 unreachable!( 832 "Failed to report data-race for non-atomic operation: no atomic component" 833 ) 834 } 835 } else { 836 unreachable!("Failed to report data-race for atomic operation") 837 }; 838 839 // Load elaborated thread information about the racing thread actions. 840 let current_thread_info = global.print_thread_metadata(current_index); 841 let other_thread_info = global.print_thread_metadata(other_thread); 842 843 // Throw the data-race detection. 844 throw_ub_format!( 845 "Data race detected between {} on {} and {} on {} at {:?} (current vector clock = {:?}, conflicting timestamp = {:?})", 846 action, 847 current_thread_info, 848 other_action, 849 other_thread_info, 850 ptr_dbg, 851 current_clocks.clock, 852 other_clock 853 ) 854 } 855 856 /// Detect data-races for an unsynchronized read operation, will not perform 857 /// data-race detection if `multi-threaded` is false, either due to no threads 858 /// being created or if it is temporarily disabled during a racy read or write 859 /// operation for which data-race detection is handled separately, for example 860 /// atomic read operations. read<'tcx>( &self, alloc_id: AllocId, range: AllocRange, global: &GlobalState, ) -> InterpResult<'tcx>861 pub fn read<'tcx>( 862 &self, 863 alloc_id: AllocId, 864 range: AllocRange, 865 global: &GlobalState, 866 ) -> InterpResult<'tcx> { 867 if global.multi_threaded.get() { 868 let (index, clocks) = global.current_thread_state(); 869 let mut alloc_ranges = self.alloc_ranges.borrow_mut(); 870 for (offset, range) in alloc_ranges.iter_mut(range.start, range.size) { 871 if let Err(DataRace) = range.read_race_detect(&*clocks, index) { 872 // Report data-race. 873 return Self::report_data_race( 874 global, 875 range, 876 "Read", 877 false, 878 Pointer::new(alloc_id, offset), 879 ); 880 } 881 } 882 Ok(()) 883 } else { 884 Ok(()) 885 } 886 } 887 888 // Shared code for detecting data-races on unique access to a section of memory unique_access<'tcx>( &mut self, alloc_id: AllocId, range: AllocRange, write_type: WriteType, global: &mut GlobalState, ) -> InterpResult<'tcx>889 fn unique_access<'tcx>( 890 &mut self, 891 alloc_id: AllocId, 892 range: AllocRange, 893 write_type: WriteType, 894 global: &mut GlobalState, 895 ) -> InterpResult<'tcx> { 896 if global.multi_threaded.get() { 897 let (index, clocks) = global.current_thread_state(); 898 for (offset, range) in self.alloc_ranges.get_mut().iter_mut(range.start, range.size) { 899 if let Err(DataRace) = range.write_race_detect(&*clocks, index, write_type) { 900 // Report data-race 901 return Self::report_data_race( 902 global, 903 range, 904 write_type.get_descriptor(), 905 false, 906 Pointer::new(alloc_id, offset), 907 ); 908 } 909 } 910 Ok(()) 911 } else { 912 Ok(()) 913 } 914 } 915 916 /// Detect data-races for an unsynchronized write operation, will not perform 917 /// data-race threads if `multi-threaded` is false, either due to no threads 918 /// being created or if it is temporarily disabled during a racy read or write 919 /// operation write<'tcx>( &mut self, alloc_id: AllocId, range: AllocRange, global: &mut GlobalState, ) -> InterpResult<'tcx>920 pub fn write<'tcx>( 921 &mut self, 922 alloc_id: AllocId, 923 range: AllocRange, 924 global: &mut GlobalState, 925 ) -> InterpResult<'tcx> { 926 self.unique_access(alloc_id, range, WriteType::Write, global) 927 } 928 929 /// Detect data-races for an unsynchronized deallocate operation, will not perform 930 /// data-race threads if `multi-threaded` is false, either due to no threads 931 /// being created or if it is temporarily disabled during a racy read or write 932 /// operation deallocate<'tcx>( &mut self, alloc_id: AllocId, range: AllocRange, global: &mut GlobalState, ) -> InterpResult<'tcx>933 pub fn deallocate<'tcx>( 934 &mut self, 935 alloc_id: AllocId, 936 range: AllocRange, 937 global: &mut GlobalState, 938 ) -> InterpResult<'tcx> { 939 self.unique_access(alloc_id, range, WriteType::Deallocate, global) 940 } 941 } 942 943 impl<'mir, 'tcx: 'mir> EvalContextPrivExt<'mir, 'tcx> for MiriEvalContext<'mir, 'tcx> {} 944 trait EvalContextPrivExt<'mir, 'tcx: 'mir>: MiriEvalContextExt<'mir, 'tcx> { 945 // Temporarily allow data-races to occur, this should only be 946 // used if either one of the appropriate `validate_atomic` functions 947 // will be called to treat a memory access as atomic or if the memory 948 // being accessed should be treated as internal state, that cannot be 949 // accessed by the interpreted program. 950 #[inline] allow_data_races_ref<R>(&self, op: impl FnOnce(&MiriEvalContext<'mir, 'tcx>) -> R) -> R951 fn allow_data_races_ref<R>(&self, op: impl FnOnce(&MiriEvalContext<'mir, 'tcx>) -> R) -> R { 952 let this = self.eval_context_ref(); 953 let old = if let Some(data_race) = &this.memory.extra.data_race { 954 data_race.multi_threaded.replace(false) 955 } else { 956 false 957 }; 958 let result = op(this); 959 if let Some(data_race) = &this.memory.extra.data_race { 960 data_race.multi_threaded.set(old); 961 } 962 result 963 } 964 965 /// Same as `allow_data_races_ref`, this temporarily disables any data-race detection and 966 /// so should only be used for atomic operations or internal state that the program cannot 967 /// access. 968 #[inline] allow_data_races_mut<R>( &mut self, op: impl FnOnce(&mut MiriEvalContext<'mir, 'tcx>) -> R, ) -> R969 fn allow_data_races_mut<R>( 970 &mut self, 971 op: impl FnOnce(&mut MiriEvalContext<'mir, 'tcx>) -> R, 972 ) -> R { 973 let this = self.eval_context_mut(); 974 let old = if let Some(data_race) = &this.memory.extra.data_race { 975 data_race.multi_threaded.replace(false) 976 } else { 977 false 978 }; 979 let result = op(this); 980 if let Some(data_race) = &this.memory.extra.data_race { 981 data_race.multi_threaded.set(old); 982 } 983 result 984 } 985 986 /// Generic atomic operation implementation validate_atomic_op<A: Debug + Copy>( &self, place: &MPlaceTy<'tcx, Tag>, atomic: A, description: &str, mut op: impl FnMut( &mut MemoryCellClocks, &mut ThreadClockSet, VectorIdx, A, ) -> Result<(), DataRace>, ) -> InterpResult<'tcx>987 fn validate_atomic_op<A: Debug + Copy>( 988 &self, 989 place: &MPlaceTy<'tcx, Tag>, 990 atomic: A, 991 description: &str, 992 mut op: impl FnMut( 993 &mut MemoryCellClocks, 994 &mut ThreadClockSet, 995 VectorIdx, 996 A, 997 ) -> Result<(), DataRace>, 998 ) -> InterpResult<'tcx> { 999 let this = self.eval_context_ref(); 1000 if let Some(data_race) = &this.memory.extra.data_race { 1001 if data_race.multi_threaded.get() { 1002 let size = place.layout.size; 1003 let (alloc_id, base_offset, ptr) = this.memory.ptr_get_alloc(place.ptr)?; 1004 // Load and log the atomic operation. 1005 // Note that atomic loads are possible even from read-only allocations, so `get_alloc_extra_mut` is not an option. 1006 let alloc_meta = 1007 &this.memory.get_alloc_extra(alloc_id)?.data_race.as_ref().unwrap(); 1008 log::trace!( 1009 "Atomic op({}) with ordering {:?} on {:?} (size={})", 1010 description, 1011 &atomic, 1012 ptr, 1013 size.bytes() 1014 ); 1015 1016 // Perform the atomic operation. 1017 data_race.maybe_perform_sync_operation(|index, mut clocks| { 1018 for (offset, range) in 1019 alloc_meta.alloc_ranges.borrow_mut().iter_mut(base_offset, size) 1020 { 1021 if let Err(DataRace) = op(range, &mut *clocks, index, atomic) { 1022 mem::drop(clocks); 1023 return VClockAlloc::report_data_race( 1024 data_race, 1025 range, 1026 description, 1027 true, 1028 Pointer::new(alloc_id, offset), 1029 ) 1030 .map(|_| true); 1031 } 1032 } 1033 1034 // This conservatively assumes all operations have release semantics 1035 Ok(true) 1036 })?; 1037 1038 // Log changes to atomic memory. 1039 if log::log_enabled!(log::Level::Trace) { 1040 for (_offset, range) in alloc_meta.alloc_ranges.borrow().iter(base_offset, size) 1041 { 1042 log::trace!( 1043 "Updated atomic memory({:?}, size={}) to {:#?}", 1044 ptr, 1045 size.bytes(), 1046 range.atomic_ops 1047 ); 1048 } 1049 } 1050 } 1051 } 1052 Ok(()) 1053 } 1054 } 1055 1056 /// Extra metadata associated with a thread. 1057 #[derive(Debug, Clone, Default)] 1058 struct ThreadExtraState { 1059 /// The current vector index in use by the 1060 /// thread currently, this is set to None 1061 /// after the vector index has been re-used 1062 /// and hence the value will never need to be 1063 /// read during data-race reporting. 1064 vector_index: Option<VectorIdx>, 1065 1066 /// The name of the thread, updated for better 1067 /// diagnostics when reporting detected data 1068 /// races. 1069 thread_name: Option<Box<str>>, 1070 1071 /// Thread termination vector clock, this 1072 /// is set on thread termination and is used 1073 /// for joining on threads since the vector_index 1074 /// may be re-used when the join operation occurs. 1075 termination_vector_clock: Option<VClock>, 1076 } 1077 1078 /// Global data-race detection state, contains the currently 1079 /// executing thread as well as the vector-clocks associated 1080 /// with each of the threads. 1081 // FIXME: it is probably better to have one large RefCell, than to have so many small ones. 1082 #[derive(Debug, Clone)] 1083 pub struct GlobalState { 1084 /// Set to true once the first additional 1085 /// thread has launched, due to the dependency 1086 /// between before and after a thread launch. 1087 /// Any data-races must be recorded after this 1088 /// so concurrent execution can ignore recording 1089 /// any data-races. 1090 multi_threaded: Cell<bool>, 1091 1092 /// Mapping of a vector index to a known set of thread 1093 /// clocks, this is not directly mapping from a thread id 1094 /// since it may refer to multiple threads. 1095 vector_clocks: RefCell<IndexVec<VectorIdx, ThreadClockSet>>, 1096 1097 /// Mapping of a given vector index to the current thread 1098 /// that the execution is representing, this may change 1099 /// if a vector index is re-assigned to a new thread. 1100 vector_info: RefCell<IndexVec<VectorIdx, ThreadId>>, 1101 1102 /// The mapping of a given thread to associated thread metadata. 1103 thread_info: RefCell<IndexVec<ThreadId, ThreadExtraState>>, 1104 1105 /// The current vector index being executed. 1106 current_index: Cell<VectorIdx>, 1107 1108 /// Potential vector indices that could be re-used on thread creation 1109 /// values are inserted here on after the thread has terminated and 1110 /// been joined with, and hence may potentially become free 1111 /// for use as the index for a new thread. 1112 /// Elements in this set may still require the vector index to 1113 /// report data-races, and can only be re-used after all 1114 /// active vector-clocks catch up with the threads timestamp. 1115 reuse_candidates: RefCell<FxHashSet<VectorIdx>>, 1116 1117 /// Counts the number of threads that are currently active 1118 /// if the number of active threads reduces to 1 and then 1119 /// a join operation occurs with the remaining main thread 1120 /// then multi-threaded execution may be disabled. 1121 active_thread_count: Cell<usize>, 1122 1123 /// This contains threads that have terminated, but not yet joined 1124 /// and so cannot become re-use candidates until a join operation 1125 /// occurs. 1126 /// The associated vector index will be moved into re-use candidates 1127 /// after the join operation occurs. 1128 terminated_threads: RefCell<FxHashMap<ThreadId, VectorIdx>>, 1129 } 1130 1131 impl GlobalState { 1132 /// Create a new global state, setup with just thread-id=0 1133 /// advanced to timestamp = 1. new() -> Self1134 pub fn new() -> Self { 1135 let mut global_state = GlobalState { 1136 multi_threaded: Cell::new(false), 1137 vector_clocks: RefCell::new(IndexVec::new()), 1138 vector_info: RefCell::new(IndexVec::new()), 1139 thread_info: RefCell::new(IndexVec::new()), 1140 current_index: Cell::new(VectorIdx::new(0)), 1141 active_thread_count: Cell::new(1), 1142 reuse_candidates: RefCell::new(FxHashSet::default()), 1143 terminated_threads: RefCell::new(FxHashMap::default()), 1144 }; 1145 1146 // Setup the main-thread since it is not explicitly created: 1147 // uses vector index and thread-id 0, also the rust runtime gives 1148 // the main-thread a name of "main". 1149 let index = global_state.vector_clocks.get_mut().push(ThreadClockSet::default()); 1150 global_state.vector_info.get_mut().push(ThreadId::new(0)); 1151 global_state.thread_info.get_mut().push(ThreadExtraState { 1152 vector_index: Some(index), 1153 thread_name: Some("main".to_string().into_boxed_str()), 1154 termination_vector_clock: None, 1155 }); 1156 1157 global_state 1158 } 1159 1160 // Try to find vector index values that can potentially be re-used 1161 // by a new thread instead of a new vector index being created. find_vector_index_reuse_candidate(&self) -> Option<VectorIdx>1162 fn find_vector_index_reuse_candidate(&self) -> Option<VectorIdx> { 1163 let mut reuse = self.reuse_candidates.borrow_mut(); 1164 let vector_clocks = self.vector_clocks.borrow(); 1165 let vector_info = self.vector_info.borrow(); 1166 let terminated_threads = self.terminated_threads.borrow(); 1167 for &candidate in reuse.iter() { 1168 let target_timestamp = vector_clocks[candidate].clock[candidate]; 1169 if vector_clocks.iter_enumerated().all(|(clock_idx, clock)| { 1170 // The thread happens before the clock, and hence cannot report 1171 // a data-race with this the candidate index. 1172 let no_data_race = clock.clock[candidate] >= target_timestamp; 1173 1174 // The vector represents a thread that has terminated and hence cannot 1175 // report a data-race with the candidate index. 1176 let thread_id = vector_info[clock_idx]; 1177 let vector_terminated = 1178 reuse.contains(&clock_idx) || terminated_threads.contains_key(&thread_id); 1179 1180 // The vector index cannot report a race with the candidate index 1181 // and hence allows the candidate index to be re-used. 1182 no_data_race || vector_terminated 1183 }) { 1184 // All vector clocks for each vector index are equal to 1185 // the target timestamp, and the thread is known to have 1186 // terminated, therefore this vector clock index cannot 1187 // report any more data-races. 1188 assert!(reuse.remove(&candidate)); 1189 return Some(candidate); 1190 } 1191 } 1192 None 1193 } 1194 1195 // Hook for thread creation, enabled multi-threaded execution and marks 1196 // the current thread timestamp as happening-before the current thread. 1197 #[inline] thread_created(&mut self, thread: ThreadId)1198 pub fn thread_created(&mut self, thread: ThreadId) { 1199 let current_index = self.current_index(); 1200 1201 // Increment the number of active threads. 1202 let active_threads = self.active_thread_count.get(); 1203 self.active_thread_count.set(active_threads + 1); 1204 1205 // Enable multi-threaded execution, there are now two threads 1206 // so data-races are now possible. 1207 self.multi_threaded.set(true); 1208 1209 // Load and setup the associated thread metadata 1210 let mut thread_info = self.thread_info.borrow_mut(); 1211 thread_info.ensure_contains_elem(thread, Default::default); 1212 1213 // Assign a vector index for the thread, attempting to re-use an old 1214 // vector index that can no longer report any data-races if possible. 1215 let created_index = if let Some(reuse_index) = self.find_vector_index_reuse_candidate() { 1216 // Now re-configure the re-use candidate, increment the clock 1217 // for the new sync use of the vector. 1218 let vector_clocks = self.vector_clocks.get_mut(); 1219 vector_clocks[reuse_index].increment_clock(reuse_index); 1220 1221 // Locate the old thread the vector was associated with and update 1222 // it to represent the new thread instead. 1223 let vector_info = self.vector_info.get_mut(); 1224 let old_thread = vector_info[reuse_index]; 1225 vector_info[reuse_index] = thread; 1226 1227 // Mark the thread the vector index was associated with as no longer 1228 // representing a thread index. 1229 thread_info[old_thread].vector_index = None; 1230 1231 reuse_index 1232 } else { 1233 // No vector re-use candidates available, instead create 1234 // a new vector index. 1235 let vector_info = self.vector_info.get_mut(); 1236 vector_info.push(thread) 1237 }; 1238 1239 log::trace!("Creating thread = {:?} with vector index = {:?}", thread, created_index); 1240 1241 // Mark the chosen vector index as in use by the thread. 1242 thread_info[thread].vector_index = Some(created_index); 1243 1244 // Create a thread clock set if applicable. 1245 let vector_clocks = self.vector_clocks.get_mut(); 1246 if created_index == vector_clocks.next_index() { 1247 vector_clocks.push(ThreadClockSet::default()); 1248 } 1249 1250 // Now load the two clocks and configure the initial state. 1251 let (current, created) = vector_clocks.pick2_mut(current_index, created_index); 1252 1253 // Join the created with current, since the current threads 1254 // previous actions happen-before the created thread. 1255 created.join_with(current); 1256 1257 // Advance both threads after the synchronized operation. 1258 // Both operations are considered to have release semantics. 1259 current.increment_clock(current_index); 1260 created.increment_clock(created_index); 1261 } 1262 1263 /// Hook on a thread join to update the implicit happens-before relation 1264 /// between the joined thread and the current thread. 1265 #[inline] thread_joined(&mut self, current_thread: ThreadId, join_thread: ThreadId)1266 pub fn thread_joined(&mut self, current_thread: ThreadId, join_thread: ThreadId) { 1267 let clocks_vec = self.vector_clocks.get_mut(); 1268 let thread_info = self.thread_info.get_mut(); 1269 1270 // Load the vector clock of the current thread. 1271 let current_index = thread_info[current_thread] 1272 .vector_index 1273 .expect("Performed thread join on thread with no assigned vector"); 1274 let current = &mut clocks_vec[current_index]; 1275 1276 // Load the associated vector clock for the terminated thread. 1277 let join_clock = thread_info[join_thread] 1278 .termination_vector_clock 1279 .as_ref() 1280 .expect("Joined with thread but thread has not terminated"); 1281 1282 // The join thread happens-before the current thread 1283 // so update the current vector clock. 1284 // Is not a release operation so the clock is not incremented. 1285 current.clock.join(join_clock); 1286 1287 // Check the number of active threads, if the value is 1 1288 // then test for potentially disabling multi-threaded execution. 1289 let active_threads = self.active_thread_count.get(); 1290 if active_threads == 1 { 1291 // May potentially be able to disable multi-threaded execution. 1292 let current_clock = &clocks_vec[current_index]; 1293 if clocks_vec 1294 .iter_enumerated() 1295 .all(|(idx, clocks)| clocks.clock[idx] <= current_clock.clock[idx]) 1296 { 1297 // All thread terminations happen-before the current clock 1298 // therefore no data-races can be reported until a new thread 1299 // is created, so disable multi-threaded execution. 1300 self.multi_threaded.set(false); 1301 } 1302 } 1303 1304 // If the thread is marked as terminated but not joined 1305 // then move the thread to the re-use set. 1306 let termination = self.terminated_threads.get_mut(); 1307 if let Some(index) = termination.remove(&join_thread) { 1308 let reuse = self.reuse_candidates.get_mut(); 1309 reuse.insert(index); 1310 } 1311 } 1312 1313 /// On thread termination, the vector-clock may re-used 1314 /// in the future once all remaining thread-clocks catch 1315 /// up with the time index of the terminated thread. 1316 /// This assigns thread termination with a unique index 1317 /// which will be used to join the thread 1318 /// This should be called strictly before any calls to 1319 /// `thread_joined`. 1320 #[inline] thread_terminated(&mut self)1321 pub fn thread_terminated(&mut self) { 1322 let current_index = self.current_index(); 1323 1324 // Increment the clock to a unique termination timestamp. 1325 let vector_clocks = self.vector_clocks.get_mut(); 1326 let current_clocks = &mut vector_clocks[current_index]; 1327 current_clocks.increment_clock(current_index); 1328 1329 // Load the current thread id for the executing vector. 1330 let vector_info = self.vector_info.get_mut(); 1331 let current_thread = vector_info[current_index]; 1332 1333 // Load the current thread metadata, and move to a terminated 1334 // vector state. Setting up the vector clock all join operations 1335 // will use. 1336 let thread_info = self.thread_info.get_mut(); 1337 let current = &mut thread_info[current_thread]; 1338 current.termination_vector_clock = Some(current_clocks.clock.clone()); 1339 1340 // Add this thread as a candidate for re-use after a thread join 1341 // occurs. 1342 let termination = self.terminated_threads.get_mut(); 1343 termination.insert(current_thread, current_index); 1344 1345 // Reduce the number of active threads, now that a thread has 1346 // terminated. 1347 let mut active_threads = self.active_thread_count.get(); 1348 active_threads -= 1; 1349 self.active_thread_count.set(active_threads); 1350 } 1351 1352 /// Hook for updating the local tracker of the currently 1353 /// enabled thread, should always be updated whenever 1354 /// `active_thread` in thread.rs is updated. 1355 #[inline] thread_set_active(&self, thread: ThreadId)1356 pub fn thread_set_active(&self, thread: ThreadId) { 1357 let thread_info = self.thread_info.borrow(); 1358 let vector_idx = thread_info[thread] 1359 .vector_index 1360 .expect("Setting thread active with no assigned vector"); 1361 self.current_index.set(vector_idx); 1362 } 1363 1364 /// Hook for updating the local tracker of the threads name 1365 /// this should always mirror the local value in thread.rs 1366 /// the thread name is used for improved diagnostics 1367 /// during a data-race. 1368 #[inline] thread_set_name(&mut self, thread: ThreadId, name: String)1369 pub fn thread_set_name(&mut self, thread: ThreadId, name: String) { 1370 let name = name.into_boxed_str(); 1371 let thread_info = self.thread_info.get_mut(); 1372 thread_info[thread].thread_name = Some(name); 1373 } 1374 1375 /// Attempt to perform a synchronized operation, this 1376 /// will perform no operation if multi-threading is 1377 /// not currently enabled. 1378 /// Otherwise it will increment the clock for the current 1379 /// vector before and after the operation for data-race 1380 /// detection between any happens-before edges the 1381 /// operation may create. maybe_perform_sync_operation<'tcx>( &self, op: impl FnOnce(VectorIdx, RefMut<'_, ThreadClockSet>) -> InterpResult<'tcx, bool>, ) -> InterpResult<'tcx>1382 fn maybe_perform_sync_operation<'tcx>( 1383 &self, 1384 op: impl FnOnce(VectorIdx, RefMut<'_, ThreadClockSet>) -> InterpResult<'tcx, bool>, 1385 ) -> InterpResult<'tcx> { 1386 if self.multi_threaded.get() { 1387 let (index, clocks) = self.current_thread_state_mut(); 1388 if op(index, clocks)? { 1389 let (_, mut clocks) = self.current_thread_state_mut(); 1390 clocks.increment_clock(index); 1391 } 1392 } 1393 Ok(()) 1394 } 1395 1396 /// Internal utility to identify a thread stored internally 1397 /// returns the id and the name for better diagnostics. print_thread_metadata(&self, vector: VectorIdx) -> String1398 fn print_thread_metadata(&self, vector: VectorIdx) -> String { 1399 let thread = self.vector_info.borrow()[vector]; 1400 let thread_name = &self.thread_info.borrow()[thread].thread_name; 1401 if let Some(name) = thread_name { 1402 let name: &str = name; 1403 format!("Thread(id = {:?}, name = {:?})", thread.to_u32(), &*name) 1404 } else { 1405 format!("Thread(id = {:?})", thread.to_u32()) 1406 } 1407 } 1408 1409 /// Acquire a lock, express that the previous call of 1410 /// `validate_lock_release` must happen before this. 1411 /// As this is an acquire operation, the thread timestamp is not 1412 /// incremented. validate_lock_acquire(&self, lock: &VClock, thread: ThreadId)1413 pub fn validate_lock_acquire(&self, lock: &VClock, thread: ThreadId) { 1414 let (_, mut clocks) = self.load_thread_state_mut(thread); 1415 clocks.clock.join(&lock); 1416 } 1417 1418 /// Release a lock handle, express that this happens-before 1419 /// any subsequent calls to `validate_lock_acquire`. 1420 /// For normal locks this should be equivalent to `validate_lock_release_shared` 1421 /// since an acquire operation should have occurred before, however 1422 /// for futex & condvar operations this is not the case and this 1423 /// operation must be used. validate_lock_release(&self, lock: &mut VClock, thread: ThreadId)1424 pub fn validate_lock_release(&self, lock: &mut VClock, thread: ThreadId) { 1425 let (index, mut clocks) = self.load_thread_state_mut(thread); 1426 lock.clone_from(&clocks.clock); 1427 clocks.increment_clock(index); 1428 } 1429 1430 /// Release a lock handle, express that this happens-before 1431 /// any subsequent calls to `validate_lock_acquire` as well 1432 /// as any previous calls to this function after any 1433 /// `validate_lock_release` calls. 1434 /// For normal locks this should be equivalent to `validate_lock_release`. 1435 /// This function only exists for joining over the set of concurrent readers 1436 /// in a read-write lock and should not be used for anything else. validate_lock_release_shared(&self, lock: &mut VClock, thread: ThreadId)1437 pub fn validate_lock_release_shared(&self, lock: &mut VClock, thread: ThreadId) { 1438 let (index, mut clocks) = self.load_thread_state_mut(thread); 1439 lock.join(&clocks.clock); 1440 clocks.increment_clock(index); 1441 } 1442 1443 /// Load the vector index used by the given thread as well as the set of vector clocks 1444 /// used by the thread. 1445 #[inline] load_thread_state_mut(&self, thread: ThreadId) -> (VectorIdx, RefMut<'_, ThreadClockSet>)1446 fn load_thread_state_mut(&self, thread: ThreadId) -> (VectorIdx, RefMut<'_, ThreadClockSet>) { 1447 let index = self.thread_info.borrow()[thread] 1448 .vector_index 1449 .expect("Loading thread state for thread with no assigned vector"); 1450 let ref_vector = self.vector_clocks.borrow_mut(); 1451 let clocks = RefMut::map(ref_vector, |vec| &mut vec[index]); 1452 (index, clocks) 1453 } 1454 1455 /// Load the current vector clock in use and the current set of thread clocks 1456 /// in use for the vector. 1457 #[inline] current_thread_state(&self) -> (VectorIdx, Ref<'_, ThreadClockSet>)1458 fn current_thread_state(&self) -> (VectorIdx, Ref<'_, ThreadClockSet>) { 1459 let index = self.current_index(); 1460 let ref_vector = self.vector_clocks.borrow(); 1461 let clocks = Ref::map(ref_vector, |vec| &vec[index]); 1462 (index, clocks) 1463 } 1464 1465 /// Load the current vector clock in use and the current set of thread clocks 1466 /// in use for the vector mutably for modification. 1467 #[inline] current_thread_state_mut(&self) -> (VectorIdx, RefMut<'_, ThreadClockSet>)1468 fn current_thread_state_mut(&self) -> (VectorIdx, RefMut<'_, ThreadClockSet>) { 1469 let index = self.current_index(); 1470 let ref_vector = self.vector_clocks.borrow_mut(); 1471 let clocks = RefMut::map(ref_vector, |vec| &mut vec[index]); 1472 (index, clocks) 1473 } 1474 1475 /// Return the current thread, should be the same 1476 /// as the data-race active thread. 1477 #[inline] current_index(&self) -> VectorIdx1478 fn current_index(&self) -> VectorIdx { 1479 self.current_index.get() 1480 } 1481 } 1482