]> git.lizzy.rs Git - rust.git/blob - src/data_race.rs
Auto merge of #1814 - RalfJung:rustup, r=RalfJung
[rust.git] / src / data_race.rs
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 a 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     ImmTy, Immediate, InterpResult, MPlaceTy, MemPlaceMeta, MemoryKind, MiriEvalContext,
77     MiriEvalContextExt, MiriMemoryKind, OpTy, Pointer, RangeMap, Scalar, ScalarMaybeUninit, Tag,
78     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]
141     fn apply_release_fence(&mut self) {
142         self.fence_release.clone_from(&self.clock);
143     }
144
145     /// Apply the effects of a acquire fence to this
146     /// set of thread vector clocks.
147     #[inline]
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]
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.
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 {
216     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.
256     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]
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]
278     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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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 a atomic operation on a memory location.
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.
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.
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_to_mplace(**new_val, place))?;
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.
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.
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.
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.
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.
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 a 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     fn reset_vector_clocks(&mut self, ptr: Pointer<Tag>, size: Size) -> InterpResult<'tcx> {
718         let this = self.eval_context_mut();
719         if let Some(data_race) = &mut this.memory.extra.data_race {
720             if data_race.multi_threaded.get() {
721                 let alloc_meta =
722                     this.memory.get_alloc_extra_mut(ptr.alloc_id)?.0.data_race.as_mut().unwrap();
723                 alloc_meta.reset_clocks(ptr.offset, size);
724             }
725         }
726         Ok(())
727     }
728 }
729
730 /// Vector clock metadata for a logical memory allocation.
731 #[derive(Debug, Clone)]
732 pub struct VClockAlloc {
733     /// Assigning each byte a MemoryCellClocks.
734     alloc_ranges: RefCell<RangeMap<MemoryCellClocks>>,
735 }
736
737 impl VClockAlloc {
738     /// Create a new data-race detector for newly allocated memory.
739     pub fn new_allocation(
740         global: &MemoryExtra,
741         len: Size,
742         kind: MemoryKind<MiriMemoryKind>,
743     ) -> VClockAlloc {
744         let (alloc_timestamp, alloc_index) = match kind {
745             // User allocated and stack memory should track allocation.
746             MemoryKind::Machine(
747                 MiriMemoryKind::Rust | MiriMemoryKind::C | MiriMemoryKind::WinHeap,
748             )
749             | MemoryKind::Stack => {
750                 let (alloc_index, clocks) = global.current_thread_state();
751                 let alloc_timestamp = clocks.clock[alloc_index];
752                 (alloc_timestamp, alloc_index)
753             }
754             // Other global memory should trace races but be allocated at the 0 timestamp.
755             MemoryKind::Machine(
756                 MiriMemoryKind::Global
757                 | MiriMemoryKind::Machine
758                 | MiriMemoryKind::Env
759                 | MiriMemoryKind::ExternStatic
760                 | MiriMemoryKind::Tls,
761             )
762             | MemoryKind::CallerLocation
763             | MemoryKind::Vtable => (0, VectorIdx::MAX_INDEX),
764         };
765         VClockAlloc {
766             alloc_ranges: RefCell::new(RangeMap::new(
767                 len,
768                 MemoryCellClocks::new(alloc_timestamp, alloc_index),
769             )),
770         }
771     }
772
773     fn reset_clocks(&mut self, offset: Size, len: Size) {
774         let alloc_ranges = self.alloc_ranges.get_mut();
775         for (_, range) in alloc_ranges.iter_mut(offset, len) {
776             // Reset the portion of the range
777             *range = MemoryCellClocks::new(0, VectorIdx::MAX_INDEX);
778         }
779     }
780
781     // Find an index, if one exists where the value
782     // in `l` is greater than the value in `r`.
783     fn find_gt_index(l: &VClock, r: &VClock) -> Option<VectorIdx> {
784         log::trace!("Find index where not {:?} <= {:?}", l, r);
785         let l_slice = l.as_slice();
786         let r_slice = r.as_slice();
787         l_slice
788             .iter()
789             .zip(r_slice.iter())
790             .enumerate()
791             .find_map(|(idx, (&l, &r))| if l > r { Some(idx) } else { None })
792             .or_else(|| {
793                 if l_slice.len() > r_slice.len() {
794                     // By invariant, if l_slice is longer
795                     // then one element must be larger.
796                     // This just validates that this is true
797                     // and reports earlier elements first.
798                     let l_remainder_slice = &l_slice[r_slice.len()..];
799                     let idx = l_remainder_slice
800                         .iter()
801                         .enumerate()
802                         .find_map(|(idx, &r)| if r == 0 { None } else { Some(idx) })
803                         .expect("Invalid VClock Invariant");
804                     Some(idx + r_slice.len())
805                 } else {
806                     None
807                 }
808             })
809             .map(|idx| VectorIdx::new(idx))
810     }
811
812     /// Report a data-race found in the program.
813     /// This finds the two racing threads and the type
814     /// of data-race that occurred. This will also
815     /// return info about the memory location the data-race
816     /// occurred in.
817     #[cold]
818     #[inline(never)]
819     fn report_data_race<'tcx>(
820         global: &MemoryExtra,
821         range: &MemoryCellClocks,
822         action: &str,
823         is_atomic: bool,
824         pointer: Pointer<Tag>,
825         len: Size,
826     ) -> InterpResult<'tcx> {
827         let (current_index, current_clocks) = global.current_thread_state();
828         let write_clock;
829         let (other_action, other_thread, other_clock) = if range.write
830             > current_clocks.clock[range.write_index]
831         {
832             // Convert the write action into the vector clock it
833             // represents for diagnostic purposes.
834             write_clock = VClock::new_with_index(range.write_index, range.write);
835             (range.write_type.get_descriptor(), range.write_index, &write_clock)
836         } else if let Some(idx) = Self::find_gt_index(&range.read, &current_clocks.clock) {
837             ("Read", idx, &range.read)
838         } else if !is_atomic {
839             if let Some(atomic) = range.atomic() {
840                 if let Some(idx) = Self::find_gt_index(&atomic.write_vector, &current_clocks.clock)
841                 {
842                     ("Atomic Store", idx, &atomic.write_vector)
843                 } else if let Some(idx) =
844                     Self::find_gt_index(&atomic.read_vector, &current_clocks.clock)
845                 {
846                     ("Atomic Load", idx, &atomic.read_vector)
847                 } else {
848                     unreachable!(
849                         "Failed to report data-race for non-atomic operation: no race found"
850                     )
851                 }
852             } else {
853                 unreachable!(
854                     "Failed to report data-race for non-atomic operation: no atomic component"
855                 )
856             }
857         } else {
858             unreachable!("Failed to report data-race for atomic operation")
859         };
860
861         // Load elaborated thread information about the racing thread actions.
862         let current_thread_info = global.print_thread_metadata(current_index);
863         let other_thread_info = global.print_thread_metadata(other_thread);
864
865         // Throw the data-race detection.
866         throw_ub_format!(
867             "Data race detected between {} on {} and {} on {}, memory({:?},offset={},size={})\
868             \n(current vector clock = {:?}, conflicting timestamp = {:?})",
869             action,
870             current_thread_info,
871             other_action,
872             other_thread_info,
873             pointer.alloc_id,
874             pointer.offset.bytes(),
875             len.bytes(),
876             current_clocks.clock,
877             other_clock
878         )
879     }
880
881     /// Detect data-races for an unsynchronized read operation, will not perform
882     /// data-race detection if `multi-threaded` is false, either due to no threads
883     /// being created or if it is temporarily disabled during a racy read or write
884     /// operation for which data-race detection is handled separately, for example
885     /// atomic read operations.
886     pub fn read<'tcx>(
887         &self,
888         pointer: Pointer<Tag>,
889         len: Size,
890         global: &GlobalState,
891     ) -> InterpResult<'tcx> {
892         if global.multi_threaded.get() {
893             let (index, clocks) = global.current_thread_state();
894             let mut alloc_ranges = self.alloc_ranges.borrow_mut();
895             for (_, range) in alloc_ranges.iter_mut(pointer.offset, len) {
896                 if let Err(DataRace) = range.read_race_detect(&*clocks, index) {
897                     // Report data-race.
898                     return Self::report_data_race(global, range, "Read", false, pointer, len);
899                 }
900             }
901             Ok(())
902         } else {
903             Ok(())
904         }
905     }
906
907     // Shared code for detecting data-races on unique access to a section of memory
908     fn unique_access<'tcx>(
909         &mut self,
910         pointer: Pointer<Tag>,
911         len: Size,
912         write_type: WriteType,
913         global: &mut GlobalState,
914     ) -> InterpResult<'tcx> {
915         if global.multi_threaded.get() {
916             let (index, clocks) = global.current_thread_state();
917             for (_, range) in self.alloc_ranges.get_mut().iter_mut(pointer.offset, len) {
918                 if let Err(DataRace) = range.write_race_detect(&*clocks, index, write_type) {
919                     // Report data-race
920                     return Self::report_data_race(
921                         global,
922                         range,
923                         write_type.get_descriptor(),
924                         false,
925                         pointer,
926                         len,
927                     );
928                 }
929             }
930             Ok(())
931         } else {
932             Ok(())
933         }
934     }
935
936     /// Detect data-races for an unsynchronized write operation, will not perform
937     /// data-race threads if `multi-threaded` is false, either due to no threads
938     /// being created or if it is temporarily disabled during a racy read or write
939     /// operation
940     pub fn write<'tcx>(
941         &mut self,
942         pointer: Pointer<Tag>,
943         len: Size,
944         global: &mut GlobalState,
945     ) -> InterpResult<'tcx> {
946         self.unique_access(pointer, len, WriteType::Write, global)
947     }
948
949     /// Detect data-races for an unsynchronized deallocate operation, will not perform
950     /// data-race threads if `multi-threaded` is false, either due to no threads
951     /// being created or if it is temporarily disabled during a racy read or write
952     /// operation
953     pub fn deallocate<'tcx>(
954         &mut self,
955         pointer: Pointer<Tag>,
956         len: Size,
957         global: &mut GlobalState,
958     ) -> InterpResult<'tcx> {
959         self.unique_access(pointer, len, WriteType::Deallocate, global)
960     }
961 }
962
963 impl<'mir, 'tcx: 'mir> EvalContextPrivExt<'mir, 'tcx> for MiriEvalContext<'mir, 'tcx> {}
964 trait EvalContextPrivExt<'mir, 'tcx: 'mir>: MiriEvalContextExt<'mir, 'tcx> {
965     // Temporarily allow data-races to occur, this should only be
966     // used if either one of the appropriate `validate_atomic` functions
967     // will be called to treat a memory access as atomic or if the memory
968     // being accessed should be treated as internal state, that cannot be
969     // accessed by the interpreted program.
970     #[inline]
971     fn allow_data_races_ref<R>(&self, op: impl FnOnce(&MiriEvalContext<'mir, 'tcx>) -> R) -> R {
972         let this = self.eval_context_ref();
973         let old = if let Some(data_race) = &this.memory.extra.data_race {
974             data_race.multi_threaded.replace(false)
975         } else {
976             false
977         };
978         let result = op(this);
979         if let Some(data_race) = &this.memory.extra.data_race {
980             data_race.multi_threaded.set(old);
981         }
982         result
983     }
984
985     /// Same as `allow_data_races_ref`, this temporarily disables any data-race detection and
986     /// so should only be used for atomic operations or internal state that the program cannot
987     /// access.
988     #[inline]
989     fn allow_data_races_mut<R>(
990         &mut self,
991         op: impl FnOnce(&mut MiriEvalContext<'mir, 'tcx>) -> R,
992     ) -> R {
993         let this = self.eval_context_mut();
994         let old = if let Some(data_race) = &this.memory.extra.data_race {
995             data_race.multi_threaded.replace(false)
996         } else {
997             false
998         };
999         let result = op(this);
1000         if let Some(data_race) = &this.memory.extra.data_race {
1001             data_race.multi_threaded.set(old);
1002         }
1003         result
1004     }
1005
1006     /// Generic atomic operation implementation,
1007     /// this accesses memory via get_raw instead of
1008     /// get_raw_mut, due to issues calling get_raw_mut
1009     /// for atomic loads from read-only memory.
1010     /// FIXME: is this valid, or should get_raw_mut be used for
1011     /// atomic-stores/atomic-rmw?
1012     fn validate_atomic_op<A: Debug + Copy>(
1013         &self,
1014         place: &MPlaceTy<'tcx, Tag>,
1015         atomic: A,
1016         description: &str,
1017         mut op: impl FnMut(
1018             &mut MemoryCellClocks,
1019             &mut ThreadClockSet,
1020             VectorIdx,
1021             A,
1022         ) -> Result<(), DataRace>,
1023     ) -> InterpResult<'tcx> {
1024         let this = self.eval_context_ref();
1025         if let Some(data_race) = &this.memory.extra.data_race {
1026             if data_race.multi_threaded.get() {
1027                 // Load and log the atomic operation.
1028                 // Note that atomic loads are possible even from read-only allocations, so `get_alloc_extra_mut` is not an option.
1029                 let place_ptr = place.ptr.assert_ptr();
1030                 let size = place.layout.size;
1031                 let alloc_meta =
1032                     &this.memory.get_alloc_extra(place_ptr.alloc_id)?.data_race.as_ref().unwrap();
1033                 log::trace!(
1034                     "Atomic op({}) with ordering {:?} on memory({:?}, offset={}, size={})",
1035                     description,
1036                     &atomic,
1037                     place_ptr.alloc_id,
1038                     place_ptr.offset.bytes(),
1039                     size.bytes()
1040                 );
1041
1042                 // Perform the atomic operation.
1043                 data_race.maybe_perform_sync_operation(|index, mut clocks| {
1044                     for (_, range) in
1045                         alloc_meta.alloc_ranges.borrow_mut().iter_mut(place_ptr.offset, size)
1046                     {
1047                         if let Err(DataRace) = op(range, &mut *clocks, index, atomic) {
1048                             mem::drop(clocks);
1049                             return VClockAlloc::report_data_race(
1050                                 data_race,
1051                                 range,
1052                                 description,
1053                                 true,
1054                                 place_ptr,
1055                                 size,
1056                             )
1057                             .map(|_| true);
1058                         }
1059                     }
1060
1061                     // This conservatively assumes all operations have release semantics
1062                     Ok(true)
1063                 })?;
1064
1065                 // Log changes to atomic memory.
1066                 if log::log_enabled!(log::Level::Trace) {
1067                     for (_, range) in alloc_meta.alloc_ranges.borrow().iter(place_ptr.offset, size)
1068                     {
1069                         log::trace!(
1070                             "Updated atomic memory({:?}, offset={}, size={}) to {:#?}",
1071                             place.ptr.assert_ptr().alloc_id,
1072                             place_ptr.offset.bytes(),
1073                             size.bytes(),
1074                             range.atomic_ops
1075                         );
1076                     }
1077                 }
1078             }
1079         }
1080         Ok(())
1081     }
1082 }
1083
1084 /// Extra metadata associated with a thread.
1085 #[derive(Debug, Clone, Default)]
1086 struct ThreadExtraState {
1087     /// The current vector index in use by the
1088     /// thread currently, this is set to None
1089     /// after the vector index has been re-used
1090     /// and hence the value will never need to be
1091     /// read during data-race reporting.
1092     vector_index: Option<VectorIdx>,
1093
1094     /// The name of the thread, updated for better
1095     /// diagnostics when reporting detected data
1096     /// races.
1097     thread_name: Option<Box<str>>,
1098
1099     /// Thread termination vector clock, this
1100     /// is set on thread termination and is used
1101     /// for joining on threads since the vector_index
1102     /// may be re-used when the join operation occurs.
1103     termination_vector_clock: Option<VClock>,
1104 }
1105
1106 /// Global data-race detection state, contains the currently
1107 /// executing thread as well as the vector-clocks associated
1108 /// with each of the threads.
1109 // FIXME: it is probably better to have one large RefCell, than to have so many small ones.
1110 #[derive(Debug, Clone)]
1111 pub struct GlobalState {
1112     /// Set to true once the first additional
1113     /// thread has launched, due to the dependency
1114     /// between before and after a thread launch.
1115     /// Any data-races must be recorded after this
1116     /// so concurrent execution can ignore recording
1117     /// any data-races.
1118     multi_threaded: Cell<bool>,
1119
1120     /// Mapping of a vector index to a known set of thread
1121     /// clocks, this is not directly mapping from a thread id
1122     /// since it may refer to multiple threads.
1123     vector_clocks: RefCell<IndexVec<VectorIdx, ThreadClockSet>>,
1124
1125     /// Mapping of a given vector index to the current thread
1126     /// that the execution is representing, this may change
1127     /// if a vector index is re-assigned to a new thread.
1128     vector_info: RefCell<IndexVec<VectorIdx, ThreadId>>,
1129
1130     /// The mapping of a given thread to associated thread metadata.
1131     thread_info: RefCell<IndexVec<ThreadId, ThreadExtraState>>,
1132
1133     /// The current vector index being executed.
1134     current_index: Cell<VectorIdx>,
1135
1136     /// Potential vector indices that could be re-used on thread creation
1137     /// values are inserted here on after the thread has terminated and
1138     /// been joined with, and hence may potentially become free
1139     /// for use as the index for a new thread.
1140     /// Elements in this set may still require the vector index to
1141     /// report data-races, and can only be re-used after all
1142     /// active vector-clocks catch up with the threads timestamp.
1143     reuse_candidates: RefCell<FxHashSet<VectorIdx>>,
1144
1145     /// Counts the number of threads that are currently active
1146     /// if the number of active threads reduces to 1 and then
1147     /// a join operation occurs with the remaining main thread
1148     /// then multi-threaded execution may be disabled.
1149     active_thread_count: Cell<usize>,
1150
1151     /// This contains threads that have terminated, but not yet joined
1152     /// and so cannot become re-use candidates until a join operation
1153     /// occurs.
1154     /// The associated vector index will be moved into re-use candidates
1155     /// after the join operation occurs.
1156     terminated_threads: RefCell<FxHashMap<ThreadId, VectorIdx>>,
1157 }
1158
1159 impl GlobalState {
1160     /// Create a new global state, setup with just thread-id=0
1161     /// advanced to timestamp = 1.
1162     pub fn new() -> Self {
1163         let mut global_state = GlobalState {
1164             multi_threaded: Cell::new(false),
1165             vector_clocks: RefCell::new(IndexVec::new()),
1166             vector_info: RefCell::new(IndexVec::new()),
1167             thread_info: RefCell::new(IndexVec::new()),
1168             current_index: Cell::new(VectorIdx::new(0)),
1169             active_thread_count: Cell::new(1),
1170             reuse_candidates: RefCell::new(FxHashSet::default()),
1171             terminated_threads: RefCell::new(FxHashMap::default()),
1172         };
1173
1174         // Setup the main-thread since it is not explicitly created:
1175         // uses vector index and thread-id 0, also the rust runtime gives
1176         // the main-thread a name of "main".
1177         let index = global_state.vector_clocks.get_mut().push(ThreadClockSet::default());
1178         global_state.vector_info.get_mut().push(ThreadId::new(0));
1179         global_state.thread_info.get_mut().push(ThreadExtraState {
1180             vector_index: Some(index),
1181             thread_name: Some("main".to_string().into_boxed_str()),
1182             termination_vector_clock: None,
1183         });
1184
1185         global_state
1186     }
1187
1188     // Try to find vector index values that can potentially be re-used
1189     // by a new thread instead of a new vector index being created.
1190     fn find_vector_index_reuse_candidate(&self) -> Option<VectorIdx> {
1191         let mut reuse = self.reuse_candidates.borrow_mut();
1192         let vector_clocks = self.vector_clocks.borrow();
1193         let vector_info = self.vector_info.borrow();
1194         let terminated_threads = self.terminated_threads.borrow();
1195         for &candidate in reuse.iter() {
1196             let target_timestamp = vector_clocks[candidate].clock[candidate];
1197             if vector_clocks.iter_enumerated().all(|(clock_idx, clock)| {
1198                 // The thread happens before the clock, and hence cannot report
1199                 // a data-race with this the candidate index.
1200                 let no_data_race = clock.clock[candidate] >= target_timestamp;
1201
1202                 // The vector represents a thread that has terminated and hence cannot
1203                 // report a data-race with the candidate index.
1204                 let thread_id = vector_info[clock_idx];
1205                 let vector_terminated =
1206                     reuse.contains(&clock_idx) || terminated_threads.contains_key(&thread_id);
1207
1208                 // The vector index cannot report a race with the candidate index
1209                 // and hence allows the candidate index to be re-used.
1210                 no_data_race || vector_terminated
1211             }) {
1212                 // All vector clocks for each vector index are equal to
1213                 // the target timestamp, and the thread is known to have
1214                 // terminated, therefore this vector clock index cannot
1215                 // report any more data-races.
1216                 assert!(reuse.remove(&candidate));
1217                 return Some(candidate);
1218             }
1219         }
1220         None
1221     }
1222
1223     // Hook for thread creation, enabled multi-threaded execution and marks
1224     // the current thread timestamp as happening-before the current thread.
1225     #[inline]
1226     pub fn thread_created(&mut self, thread: ThreadId) {
1227         let current_index = self.current_index();
1228
1229         // Increment the number of active threads.
1230         let active_threads = self.active_thread_count.get();
1231         self.active_thread_count.set(active_threads + 1);
1232
1233         // Enable multi-threaded execution, there are now two threads
1234         // so data-races are now possible.
1235         self.multi_threaded.set(true);
1236
1237         // Load and setup the associated thread metadata
1238         let mut thread_info = self.thread_info.borrow_mut();
1239         thread_info.ensure_contains_elem(thread, Default::default);
1240
1241         // Assign a vector index for the thread, attempting to re-use an old
1242         // vector index that can no longer report any data-races if possible.
1243         let created_index = if let Some(reuse_index) = self.find_vector_index_reuse_candidate() {
1244             // Now re-configure the re-use candidate, increment the clock
1245             // for the new sync use of the vector.
1246             let vector_clocks = self.vector_clocks.get_mut();
1247             vector_clocks[reuse_index].increment_clock(reuse_index);
1248
1249             // Locate the old thread the vector was associated with and update
1250             // it to represent the new thread instead.
1251             let vector_info = self.vector_info.get_mut();
1252             let old_thread = vector_info[reuse_index];
1253             vector_info[reuse_index] = thread;
1254
1255             // Mark the thread the vector index was associated with as no longer
1256             // representing a thread index.
1257             thread_info[old_thread].vector_index = None;
1258
1259             reuse_index
1260         } else {
1261             // No vector re-use candidates available, instead create
1262             // a new vector index.
1263             let vector_info = self.vector_info.get_mut();
1264             vector_info.push(thread)
1265         };
1266
1267         log::trace!("Creating thread = {:?} with vector index = {:?}", thread, created_index);
1268
1269         // Mark the chosen vector index as in use by the thread.
1270         thread_info[thread].vector_index = Some(created_index);
1271
1272         // Create a thread clock set if applicable.
1273         let vector_clocks = self.vector_clocks.get_mut();
1274         if created_index == vector_clocks.next_index() {
1275             vector_clocks.push(ThreadClockSet::default());
1276         }
1277
1278         // Now load the two clocks and configure the initial state.
1279         let (current, created) = vector_clocks.pick2_mut(current_index, created_index);
1280
1281         // Join the created with current, since the current threads
1282         // previous actions happen-before the created thread.
1283         created.join_with(current);
1284
1285         // Advance both threads after the synchronized operation.
1286         // Both operations are considered to have release semantics.
1287         current.increment_clock(current_index);
1288         created.increment_clock(created_index);
1289     }
1290
1291     /// Hook on a thread join to update the implicit happens-before relation
1292     /// between the joined thread and the current thread.
1293     #[inline]
1294     pub fn thread_joined(&mut self, current_thread: ThreadId, join_thread: ThreadId) {
1295         let clocks_vec = self.vector_clocks.get_mut();
1296         let thread_info = self.thread_info.get_mut();
1297
1298         // Load the vector clock of the current thread.
1299         let current_index = thread_info[current_thread]
1300             .vector_index
1301             .expect("Performed thread join on thread with no assigned vector");
1302         let current = &mut clocks_vec[current_index];
1303
1304         // Load the associated vector clock for the terminated thread.
1305         let join_clock = thread_info[join_thread]
1306             .termination_vector_clock
1307             .as_ref()
1308             .expect("Joined with thread but thread has not terminated");
1309
1310         // The join thread happens-before the current thread
1311         // so update the current vector clock.
1312         // Is not a release operation so the clock is not incremented.
1313         current.clock.join(join_clock);
1314
1315         // Check the number of active threads, if the value is 1
1316         // then test for potentially disabling multi-threaded execution.
1317         let active_threads = self.active_thread_count.get();
1318         if active_threads == 1 {
1319             // May potentially be able to disable multi-threaded execution.
1320             let current_clock = &clocks_vec[current_index];
1321             if clocks_vec
1322                 .iter_enumerated()
1323                 .all(|(idx, clocks)| clocks.clock[idx] <= current_clock.clock[idx])
1324             {
1325                 // All thread terminations happen-before the current clock
1326                 // therefore no data-races can be reported until a new thread
1327                 // is created, so disable multi-threaded execution.
1328                 self.multi_threaded.set(false);
1329             }
1330         }
1331
1332         // If the thread is marked as terminated but not joined
1333         // then move the thread to the re-use set.
1334         let termination = self.terminated_threads.get_mut();
1335         if let Some(index) = termination.remove(&join_thread) {
1336             let reuse = self.reuse_candidates.get_mut();
1337             reuse.insert(index);
1338         }
1339     }
1340
1341     /// On thread termination, the vector-clock may re-used
1342     /// in the future once all remaining thread-clocks catch
1343     /// up with the time index of the terminated thread.
1344     /// This assigns thread termination with a unique index
1345     /// which will be used to join the thread
1346     /// This should be called strictly before any calls to
1347     /// `thread_joined`.
1348     #[inline]
1349     pub fn thread_terminated(&mut self) {
1350         let current_index = self.current_index();
1351
1352         // Increment the clock to a unique termination timestamp.
1353         let vector_clocks = self.vector_clocks.get_mut();
1354         let current_clocks = &mut vector_clocks[current_index];
1355         current_clocks.increment_clock(current_index);
1356
1357         // Load the current thread id for the executing vector.
1358         let vector_info = self.vector_info.get_mut();
1359         let current_thread = vector_info[current_index];
1360
1361         // Load the current thread metadata, and move to a terminated
1362         // vector state. Setting up the vector clock all join operations
1363         // will use.
1364         let thread_info = self.thread_info.get_mut();
1365         let current = &mut thread_info[current_thread];
1366         current.termination_vector_clock = Some(current_clocks.clock.clone());
1367
1368         // Add this thread as a candidate for re-use after a thread join
1369         // occurs.
1370         let termination = self.terminated_threads.get_mut();
1371         termination.insert(current_thread, current_index);
1372
1373         // Reduce the number of active threads, now that a thread has
1374         // terminated.
1375         let mut active_threads = self.active_thread_count.get();
1376         active_threads -= 1;
1377         self.active_thread_count.set(active_threads);
1378     }
1379
1380     /// Hook for updating the local tracker of the currently
1381     /// enabled thread, should always be updated whenever
1382     /// `active_thread` in thread.rs is updated.
1383     #[inline]
1384     pub fn thread_set_active(&self, thread: ThreadId) {
1385         let thread_info = self.thread_info.borrow();
1386         let vector_idx = thread_info[thread]
1387             .vector_index
1388             .expect("Setting thread active with no assigned vector");
1389         self.current_index.set(vector_idx);
1390     }
1391
1392     /// Hook for updating the local tracker of the threads name
1393     /// this should always mirror the local value in thread.rs
1394     /// the thread name is used for improved diagnostics
1395     /// during a data-race.
1396     #[inline]
1397     pub fn thread_set_name(&mut self, thread: ThreadId, name: String) {
1398         let name = name.into_boxed_str();
1399         let thread_info = self.thread_info.get_mut();
1400         thread_info[thread].thread_name = Some(name);
1401     }
1402
1403     /// Attempt to perform a synchronized operation, this
1404     /// will perform no operation if multi-threading is
1405     /// not currently enabled.
1406     /// Otherwise it will increment the clock for the current
1407     /// vector before and after the operation for data-race
1408     /// detection between any happens-before edges the
1409     /// operation may create.
1410     fn maybe_perform_sync_operation<'tcx>(
1411         &self,
1412         op: impl FnOnce(VectorIdx, RefMut<'_, ThreadClockSet>) -> InterpResult<'tcx, bool>,
1413     ) -> InterpResult<'tcx> {
1414         if self.multi_threaded.get() {
1415             let (index, clocks) = self.current_thread_state_mut();
1416             if op(index, clocks)? {
1417                 let (_, mut clocks) = self.current_thread_state_mut();
1418                 clocks.increment_clock(index);
1419             }
1420         }
1421         Ok(())
1422     }
1423
1424     /// Internal utility to identify a thread stored internally
1425     /// returns the id and the name for better diagnostics.
1426     fn print_thread_metadata(&self, vector: VectorIdx) -> String {
1427         let thread = self.vector_info.borrow()[vector];
1428         let thread_name = &self.thread_info.borrow()[thread].thread_name;
1429         if let Some(name) = thread_name {
1430             let name: &str = name;
1431             format!("Thread(id = {:?}, name = {:?})", thread.to_u32(), &*name)
1432         } else {
1433             format!("Thread(id = {:?})", thread.to_u32())
1434         }
1435     }
1436
1437     /// Acquire a lock, express that the previous call of
1438     /// `validate_lock_release` must happen before this.
1439     /// As this is an acquire operation, the thread timestamp is not
1440     /// incremented.
1441     pub fn validate_lock_acquire(&self, lock: &VClock, thread: ThreadId) {
1442         let (_, mut clocks) = self.load_thread_state_mut(thread);
1443         clocks.clock.join(&lock);
1444     }
1445
1446     /// Release a lock handle, express that this happens-before
1447     /// any subsequent calls to `validate_lock_acquire`.
1448     /// For normal locks this should be equivalent to `validate_lock_release_shared`
1449     /// since an acquire operation should have occurred before, however
1450     /// for futex & condvar operations this is not the case and this
1451     /// operation must be used.
1452     pub fn validate_lock_release(&self, lock: &mut VClock, thread: ThreadId) {
1453         let (index, mut clocks) = self.load_thread_state_mut(thread);
1454         lock.clone_from(&clocks.clock);
1455         clocks.increment_clock(index);
1456     }
1457
1458     /// Release a lock handle, express that this happens-before
1459     /// any subsequent calls to `validate_lock_acquire` as well
1460     /// as any previous calls to this function after any
1461     /// `validate_lock_release` calls.
1462     /// For normal locks this should be equivalent to `validate_lock_release`.
1463     /// This function only exists for joining over the set of concurrent readers
1464     /// in a read-write lock and should not be used for anything else.
1465     pub fn validate_lock_release_shared(&self, lock: &mut VClock, thread: ThreadId) {
1466         let (index, mut clocks) = self.load_thread_state_mut(thread);
1467         lock.join(&clocks.clock);
1468         clocks.increment_clock(index);
1469     }
1470
1471     /// Load the vector index used by the given thread as well as the set of vector clocks
1472     /// used by the thread.
1473     #[inline]
1474     fn load_thread_state_mut(&self, thread: ThreadId) -> (VectorIdx, RefMut<'_, ThreadClockSet>) {
1475         let index = self.thread_info.borrow()[thread]
1476             .vector_index
1477             .expect("Loading thread state for thread with no assigned vector");
1478         let ref_vector = self.vector_clocks.borrow_mut();
1479         let clocks = RefMut::map(ref_vector, |vec| &mut vec[index]);
1480         (index, clocks)
1481     }
1482
1483     /// Load the current vector clock in use and the current set of thread clocks
1484     /// in use for the vector.
1485     #[inline]
1486     fn current_thread_state(&self) -> (VectorIdx, Ref<'_, ThreadClockSet>) {
1487         let index = self.current_index();
1488         let ref_vector = self.vector_clocks.borrow();
1489         let clocks = Ref::map(ref_vector, |vec| &vec[index]);
1490         (index, clocks)
1491     }
1492
1493     /// Load the current vector clock in use and the current set of thread clocks
1494     /// in use for the vector mutably for modification.
1495     #[inline]
1496     fn current_thread_state_mut(&self) -> (VectorIdx, RefMut<'_, ThreadClockSet>) {
1497         let index = self.current_index();
1498         let ref_vector = self.vector_clocks.borrow_mut();
1499         let clocks = RefMut::map(ref_vector, |vec| &mut vec[index]);
1500         (index, clocks)
1501     }
1502
1503     /// Return the current thread, should be the same
1504     /// as the data-race active thread.
1505     #[inline]
1506     fn current_index(&self) -> VectorIdx {
1507         self.current_index.get()
1508     }
1509 }