1 use std::collections::{hash_map::Entry, HashMap, VecDeque};
2 use std::num::NonZeroU32;
7 use rustc_index::vec::{Idx, IndexVec};
11 /// We cannot use the `newtype_index!` macro because we have to use 0 as a
12 /// sentinel value meaning that the identifier is not assigned. This is because
13 /// the pthreads static initializers initialize memory with zeros (see the
14 /// `src/shims/sync.rs` file).
15 macro_rules! declare_id {
17 /// 0 is used to indicate that the id was not yet assigned and,
18 /// therefore, is not a valid identifier.
19 #[derive(Clone, Copy, Debug, PartialOrd, Ord, PartialEq, Eq, Hash)]
20 pub struct $name(NonZeroU32);
23 // Panics if `id == 0`.
24 pub fn from_u32(id: u32) -> Self {
25 Self(NonZeroU32::new(id).unwrap())
30 fn new(idx: usize) -> Self {
31 // We use 0 as a sentinel value (see the comment above) and,
32 // therefore, need to shift by one when converting from an index
34 let shifted_idx = u32::try_from(idx).unwrap().checked_add(1).unwrap();
35 $name(NonZeroU32::new(shifted_idx).unwrap())
37 fn index(self) -> usize {
38 // See the comment in `Self::new`.
39 // (This cannot underflow because self is NonZeroU32.)
40 usize::try_from(self.0.get() - 1).unwrap()
45 pub fn to_u32_scalar<'tcx>(&self) -> Scalar<Provenance> {
46 Scalar::from_u32(self.0.get())
55 #[derive(Default, Debug)]
57 /// The thread that currently owns the lock.
58 owner: Option<ThreadId>,
59 /// How many times the mutex was locked by the owner.
61 /// The queue of threads waiting for this mutex.
62 queue: VecDeque<ThreadId>,
63 /// Data race handle, this tracks the happens-before
64 /// relationship between each mutex access. It is
65 /// released to during unlock and acquired from during
66 /// locking, and therefore stores the clock of the last
67 /// thread to release this mutex.
71 declare_id!(RwLockId);
73 /// The read-write lock state.
74 #[derive(Default, Debug)]
76 /// The writer thread that currently owns the lock.
77 writer: Option<ThreadId>,
78 /// The readers that currently own the lock and how many times they acquired
80 readers: HashMap<ThreadId, usize>,
81 /// The queue of writer threads waiting for this lock.
82 writer_queue: VecDeque<ThreadId>,
83 /// The queue of reader threads waiting for this lock.
84 reader_queue: VecDeque<ThreadId>,
85 /// Data race handle for writers, tracks the happens-before
86 /// ordering between each write access to a rwlock and is updated
87 /// after a sequence of concurrent readers to track the happens-
88 /// before ordering between the set of previous readers and
89 /// the current writer.
90 /// Contains the clock of the last thread to release a writer
91 /// lock or the joined clock of the set of last threads to release
92 /// shared reader locks.
94 /// Data race handle for readers, this is temporary storage
95 /// for the combined happens-before ordering for between all
96 /// concurrent readers and the next writer, and the value
97 /// is stored to the main data_race variable once all
98 /// readers are finished.
99 /// Has to be stored separately since reader lock acquires
100 /// must load the clock of the last write and must not
101 /// add happens-before orderings between shared reader
103 data_race_reader: VClock,
106 declare_id!(CondvarId);
108 /// A thread waiting on a conditional variable.
110 struct CondvarWaiter {
111 /// The thread that is waiting on this variable.
113 /// The mutex on which the thread is waiting.
117 /// The conditional variable state.
118 #[derive(Default, Debug)]
120 waiters: VecDeque<CondvarWaiter>,
121 /// Tracks the happens-before relationship
122 /// between a cond-var signal and a cond-var
123 /// wait during a non-suprious signal event.
124 /// Contains the clock of the last thread to
125 /// perform a futex-signal.
130 #[derive(Default, Debug)]
132 waiters: VecDeque<FutexWaiter>,
133 /// Tracks the happens-before relationship
134 /// between a futex-wake and a futex-wait
135 /// during a non-spurious wake event.
136 /// Contains the clock of the last thread to
137 /// perform a futex-wake.
141 /// A thread waiting on a futex.
144 /// The thread that is waiting on this futex.
146 /// The bitset used by FUTEX_*_BITSET, or u32::MAX for other operations.
150 /// The state of all synchronization variables.
151 #[derive(Default, Debug)]
152 pub(super) struct SynchronizationState {
153 mutexes: IndexVec<MutexId, Mutex>,
154 rwlocks: IndexVec<RwLockId, RwLock>,
155 condvars: IndexVec<CondvarId, Condvar>,
156 futexes: HashMap<u64, Futex>,
159 // Private extension trait for local helper methods
160 impl<'mir, 'tcx: 'mir> EvalContextExtPriv<'mir, 'tcx> for crate::MiriEvalContext<'mir, 'tcx> {}
161 trait EvalContextExtPriv<'mir, 'tcx: 'mir>: crate::MiriEvalContextExt<'mir, 'tcx> {
162 /// Take a reader out of the queue waiting for the lock.
163 /// Returns `true` if some thread got the rwlock.
165 fn rwlock_dequeue_and_lock_reader(&mut self, id: RwLockId) -> bool {
166 let this = self.eval_context_mut();
167 if let Some(reader) = this.machine.threads.sync.rwlocks[id].reader_queue.pop_front() {
168 this.unblock_thread(reader);
169 this.rwlock_reader_lock(id, reader);
176 /// Take the writer out of the queue waiting for the lock.
177 /// Returns `true` if some thread got the rwlock.
179 fn rwlock_dequeue_and_lock_writer(&mut self, id: RwLockId) -> bool {
180 let this = self.eval_context_mut();
181 if let Some(writer) = this.machine.threads.sync.rwlocks[id].writer_queue.pop_front() {
182 this.unblock_thread(writer);
183 this.rwlock_writer_lock(id, writer);
190 /// Take a thread out of the queue waiting for the mutex, and lock
191 /// the mutex for it. Returns `true` if some thread has the mutex now.
193 fn mutex_dequeue_and_lock(&mut self, id: MutexId) -> bool {
194 let this = self.eval_context_mut();
195 if let Some(thread) = this.machine.threads.sync.mutexes[id].queue.pop_front() {
196 this.unblock_thread(thread);
197 this.mutex_lock(id, thread);
205 // Public interface to synchronization primitives. Please note that in most
206 // cases, the function calls are infallible and it is the client's (shim
207 // implementation's) responsibility to detect and deal with erroneous
209 impl<'mir, 'tcx: 'mir> EvalContextExt<'mir, 'tcx> for crate::MiriEvalContext<'mir, 'tcx> {}
210 pub trait EvalContextExt<'mir, 'tcx: 'mir>: crate::MiriEvalContextExt<'mir, 'tcx> {
212 /// Create state for a new mutex.
213 fn mutex_create(&mut self) -> MutexId {
214 let this = self.eval_context_mut();
215 this.machine.threads.sync.mutexes.push(Default::default())
219 /// Provides the closure with the next MutexId. Creates that mutex if the closure returns None,
220 /// otherwise returns the value from the closure
221 fn mutex_get_or_create<F>(&mut self, existing: F) -> InterpResult<'tcx, MutexId>
223 F: FnOnce(&mut MiriEvalContext<'mir, 'tcx>, MutexId) -> InterpResult<'tcx, Option<MutexId>>,
225 let this = self.eval_context_mut();
226 let next_index = this.machine.threads.sync.mutexes.next_index();
227 if let Some(old) = existing(this, next_index)? {
230 let new_index = this.machine.threads.sync.mutexes.push(Default::default());
231 assert_eq!(next_index, new_index);
237 /// Get the id of the thread that currently owns this lock.
238 fn mutex_get_owner(&mut self, id: MutexId) -> ThreadId {
239 let this = self.eval_context_ref();
240 this.machine.threads.sync.mutexes[id].owner.unwrap()
245 fn mutex_is_locked(&self, id: MutexId) -> bool {
246 let this = self.eval_context_ref();
247 this.machine.threads.sync.mutexes[id].owner.is_some()
250 /// Lock by setting the mutex owner and increasing the lock count.
251 fn mutex_lock(&mut self, id: MutexId, thread: ThreadId) {
252 let this = self.eval_context_mut();
253 let mutex = &mut this.machine.threads.sync.mutexes[id];
254 if let Some(current_owner) = mutex.owner {
255 assert_eq!(thread, current_owner, "mutex already locked by another thread");
257 mutex.lock_count > 0,
258 "invariant violation: lock_count == 0 iff the thread is unlocked"
261 mutex.owner = Some(thread);
263 mutex.lock_count = mutex.lock_count.checked_add(1).unwrap();
264 if let Some(data_race) = &this.machine.data_race {
265 data_race.validate_lock_acquire(&mutex.data_race, thread);
269 /// Try unlocking by decreasing the lock count and returning the old lock
270 /// count. If the lock count reaches 0, release the lock and potentially
271 /// give to a new owner. If the lock was not locked by `expected_owner`,
273 fn mutex_unlock(&mut self, id: MutexId, expected_owner: ThreadId) -> Option<usize> {
274 let this = self.eval_context_mut();
275 let mutex = &mut this.machine.threads.sync.mutexes[id];
276 if let Some(current_owner) = mutex.owner {
278 if current_owner != expected_owner {
279 // Only the owner can unlock the mutex.
282 let old_lock_count = mutex.lock_count;
283 mutex.lock_count = old_lock_count
285 .expect("invariant violation: lock_count == 0 iff the thread is unlocked");
286 if mutex.lock_count == 0 {
288 // The mutex is completely unlocked. Try transfering ownership
289 // to another thread.
290 if let Some(data_race) = &this.machine.data_race {
291 data_race.validate_lock_release(&mut mutex.data_race, current_owner);
293 this.mutex_dequeue_and_lock(id);
297 // Mutex is not locked.
303 /// Put the thread into the queue waiting for the mutex.
304 fn mutex_enqueue_and_block(&mut self, id: MutexId, thread: ThreadId) {
305 let this = self.eval_context_mut();
306 assert!(this.mutex_is_locked(id), "queing on unlocked mutex");
307 this.machine.threads.sync.mutexes[id].queue.push_back(thread);
308 this.block_thread(thread);
312 /// Create state for a new read write lock.
313 fn rwlock_create(&mut self) -> RwLockId {
314 let this = self.eval_context_mut();
315 this.machine.threads.sync.rwlocks.push(Default::default())
319 /// Provides the closure with the next RwLockId. Creates that RwLock if the closure returns None,
320 /// otherwise returns the value from the closure
321 fn rwlock_get_or_create<F>(&mut self, existing: F) -> InterpResult<'tcx, RwLockId>
324 &mut MiriEvalContext<'mir, 'tcx>,
326 ) -> InterpResult<'tcx, Option<RwLockId>>,
328 let this = self.eval_context_mut();
329 let next_index = this.machine.threads.sync.rwlocks.next_index();
330 if let Some(old) = existing(this, next_index)? {
333 let new_index = this.machine.threads.sync.rwlocks.push(Default::default());
334 assert_eq!(next_index, new_index);
341 fn rwlock_is_locked(&self, id: RwLockId) -> bool {
342 let this = self.eval_context_ref();
343 let rwlock = &this.machine.threads.sync.rwlocks[id];
345 "rwlock_is_locked: {:?} writer is {:?} and there are {} reader threads (some of which could hold multiple read locks)",
348 rwlock.readers.len(),
350 rwlock.writer.is_some() || rwlock.readers.is_empty().not()
354 /// Check if write locked.
355 fn rwlock_is_write_locked(&self, id: RwLockId) -> bool {
356 let this = self.eval_context_ref();
357 let rwlock = &this.machine.threads.sync.rwlocks[id];
358 trace!("rwlock_is_write_locked: {:?} writer is {:?}", id, rwlock.writer);
359 rwlock.writer.is_some()
362 /// Read-lock the lock by adding the `reader` the list of threads that own
364 fn rwlock_reader_lock(&mut self, id: RwLockId, reader: ThreadId) {
365 let this = self.eval_context_mut();
366 assert!(!this.rwlock_is_write_locked(id), "the lock is write locked");
367 trace!("rwlock_reader_lock: {:?} now also held (one more time) by {:?}", id, reader);
368 let rwlock = &mut this.machine.threads.sync.rwlocks[id];
369 let count = rwlock.readers.entry(reader).or_insert(0);
370 *count = count.checked_add(1).expect("the reader counter overflowed");
371 if let Some(data_race) = &this.machine.data_race {
372 data_race.validate_lock_acquire(&rwlock.data_race, reader);
376 /// Try read-unlock the lock for `reader` and potentially give the lock to a new owner.
377 /// Returns `true` if succeeded, `false` if this `reader` did not hold the lock.
378 fn rwlock_reader_unlock(&mut self, id: RwLockId, reader: ThreadId) -> bool {
379 let this = self.eval_context_mut();
380 let rwlock = &mut this.machine.threads.sync.rwlocks[id];
381 match rwlock.readers.entry(reader) {
382 Entry::Occupied(mut entry) => {
383 let count = entry.get_mut();
384 assert!(*count > 0, "rwlock locked with count == 0");
387 trace!("rwlock_reader_unlock: {:?} no longer held by {:?}", id, reader);
390 trace!("rwlock_reader_unlock: {:?} held one less time by {:?}", id, reader);
393 Entry::Vacant(_) => return false, // we did not even own this lock
395 if let Some(data_race) = &this.machine.data_race {
396 data_race.validate_lock_release_shared(&mut rwlock.data_race_reader, reader);
399 // The thread was a reader. If the lock is not held any more, give it to a writer.
400 if this.rwlock_is_locked(id).not() {
401 // All the readers are finished, so set the writer data-race handle to the value
402 // of the union of all reader data race handles, since the set of readers
403 // happen-before the writers
404 let rwlock = &mut this.machine.threads.sync.rwlocks[id];
405 rwlock.data_race.clone_from(&rwlock.data_race_reader);
406 this.rwlock_dequeue_and_lock_writer(id);
412 /// Put the reader in the queue waiting for the lock and block it.
413 fn rwlock_enqueue_and_block_reader(&mut self, id: RwLockId, reader: ThreadId) {
414 let this = self.eval_context_mut();
415 assert!(this.rwlock_is_write_locked(id), "read-queueing on not write locked rwlock");
416 this.machine.threads.sync.rwlocks[id].reader_queue.push_back(reader);
417 this.block_thread(reader);
421 /// Lock by setting the writer that owns the lock.
422 fn rwlock_writer_lock(&mut self, id: RwLockId, writer: ThreadId) {
423 let this = self.eval_context_mut();
424 assert!(!this.rwlock_is_locked(id), "the rwlock is already locked");
425 trace!("rwlock_writer_lock: {:?} now held by {:?}", id, writer);
426 let rwlock = &mut this.machine.threads.sync.rwlocks[id];
427 rwlock.writer = Some(writer);
428 if let Some(data_race) = &this.machine.data_race {
429 data_race.validate_lock_acquire(&rwlock.data_race, writer);
434 /// Try to unlock by removing the writer.
435 fn rwlock_writer_unlock(&mut self, id: RwLockId, expected_writer: ThreadId) -> bool {
436 let this = self.eval_context_mut();
437 let rwlock = &mut this.machine.threads.sync.rwlocks[id];
438 if let Some(current_writer) = rwlock.writer {
439 if current_writer != expected_writer {
440 // Only the owner can unlock the rwlock.
443 rwlock.writer = None;
444 trace!("rwlock_writer_unlock: {:?} unlocked by {:?}", id, expected_writer);
445 // Release memory to both reader and writer vector clocks
446 // since this writer happens-before both the union of readers once they are finished
447 // and the next writer
448 if let Some(data_race) = &this.machine.data_race {
449 data_race.validate_lock_release(&mut rwlock.data_race, current_writer);
450 data_race.validate_lock_release(&mut rwlock.data_race_reader, current_writer);
452 // The thread was a writer.
454 // We are prioritizing writers here against the readers. As a
455 // result, not only readers can starve writers, but also writers can
457 if this.rwlock_dequeue_and_lock_writer(id) {
458 // Someone got the write lock, nice.
460 // Give the lock to all readers.
461 while this.rwlock_dequeue_and_lock_reader(id) {
472 /// Put the writer in the queue waiting for the lock.
473 fn rwlock_enqueue_and_block_writer(&mut self, id: RwLockId, writer: ThreadId) {
474 let this = self.eval_context_mut();
475 assert!(this.rwlock_is_locked(id), "write-queueing on unlocked rwlock");
476 this.machine.threads.sync.rwlocks[id].writer_queue.push_back(writer);
477 this.block_thread(writer);
481 /// Create state for a new conditional variable.
482 fn condvar_create(&mut self) -> CondvarId {
483 let this = self.eval_context_mut();
484 this.machine.threads.sync.condvars.push(Default::default())
488 /// Provides the closure with the next CondvarId. Creates that Condvar if the closure returns None,
489 /// otherwise returns the value from the closure
490 fn condvar_get_or_create<F>(&mut self, existing: F) -> InterpResult<'tcx, CondvarId>
493 &mut MiriEvalContext<'mir, 'tcx>,
495 ) -> InterpResult<'tcx, Option<CondvarId>>,
497 let this = self.eval_context_mut();
498 let next_index = this.machine.threads.sync.condvars.next_index();
499 if let Some(old) = existing(this, next_index)? {
502 let new_index = this.machine.threads.sync.condvars.push(Default::default());
503 assert_eq!(next_index, new_index);
509 /// Is the conditional variable awaited?
510 fn condvar_is_awaited(&mut self, id: CondvarId) -> bool {
511 let this = self.eval_context_mut();
512 !this.machine.threads.sync.condvars[id].waiters.is_empty()
515 /// Mark that the thread is waiting on the conditional variable.
516 fn condvar_wait(&mut self, id: CondvarId, thread: ThreadId, mutex: MutexId) {
517 let this = self.eval_context_mut();
518 let waiters = &mut this.machine.threads.sync.condvars[id].waiters;
519 assert!(waiters.iter().all(|waiter| waiter.thread != thread), "thread is already waiting");
520 waiters.push_back(CondvarWaiter { thread, mutex });
523 /// Wake up some thread (if there is any) sleeping on the conditional
525 fn condvar_signal(&mut self, id: CondvarId) -> Option<(ThreadId, MutexId)> {
526 let this = self.eval_context_mut();
527 let current_thread = this.get_active_thread();
528 let condvar = &mut this.machine.threads.sync.condvars[id];
529 let data_race = &this.machine.data_race;
531 // Each condvar signal happens-before the end of the condvar wake
532 if let Some(data_race) = data_race {
533 data_race.validate_lock_release(&mut condvar.data_race, current_thread);
535 condvar.waiters.pop_front().map(|waiter| {
536 if let Some(data_race) = data_race {
537 data_race.validate_lock_acquire(&condvar.data_race, waiter.thread);
539 (waiter.thread, waiter.mutex)
544 /// Remove the thread from the queue of threads waiting on this conditional variable.
545 fn condvar_remove_waiter(&mut self, id: CondvarId, thread: ThreadId) {
546 let this = self.eval_context_mut();
547 this.machine.threads.sync.condvars[id].waiters.retain(|waiter| waiter.thread != thread);
550 fn futex_wait(&mut self, addr: u64, thread: ThreadId, bitset: u32) {
551 let this = self.eval_context_mut();
552 let futex = &mut this.machine.threads.sync.futexes.entry(addr).or_default();
553 let waiters = &mut futex.waiters;
554 assert!(waiters.iter().all(|waiter| waiter.thread != thread), "thread is already waiting");
555 waiters.push_back(FutexWaiter { thread, bitset });
558 fn futex_wake(&mut self, addr: u64, bitset: u32) -> Option<ThreadId> {
559 let this = self.eval_context_mut();
560 let current_thread = this.get_active_thread();
561 let futex = &mut this.machine.threads.sync.futexes.get_mut(&addr)?;
562 let data_race = &this.machine.data_race;
564 // Each futex-wake happens-before the end of the futex wait
565 if let Some(data_race) = data_race {
566 data_race.validate_lock_release(&mut futex.data_race, current_thread);
569 // Wake up the first thread in the queue that matches any of the bits in the bitset.
570 futex.waiters.iter().position(|w| w.bitset & bitset != 0).map(|i| {
571 let waiter = futex.waiters.remove(i).unwrap();
572 if let Some(data_race) = data_race {
573 data_race.validate_lock_acquire(&futex.data_race, waiter.thread);
579 fn futex_remove_waiter(&mut self, addr: u64, thread: ThreadId) {
580 let this = self.eval_context_mut();
581 if let Some(futex) = this.machine.threads.sync.futexes.get_mut(&addr) {
582 futex.waiters.retain(|waiter| waiter.thread != thread);