1 use std::collections::{hash_map::Entry, HashMap, VecDeque};
2 use std::convert::TryFrom;
3 use std::num::NonZeroU32;
8 use rustc_index::vec::{Idx, IndexVec};
12 /// We cannot use the `newtype_index!` macro because we have to use 0 as a
13 /// sentinel value meaning that the identifier is not assigned. This is because
14 /// the pthreads static initializers initialize memory with zeros (see the
15 /// `src/shims/sync.rs` file).
16 macro_rules! declare_id {
18 /// 0 is used to indicate that the id was not yet assigned and,
19 /// therefore, is not a valid identifier.
20 #[derive(Clone, Copy, Debug, PartialOrd, Ord, PartialEq, Eq, Hash)]
21 pub struct $name(NonZeroU32);
24 // Panics if `id == 0`.
25 pub fn from_u32(id: u32) -> Self {
26 Self(NonZeroU32::new(id).unwrap())
31 fn new(idx: usize) -> Self {
32 // We use 0 as a sentinel value (see the comment above) and,
33 // therefore, need to shift by one when converting from an index
35 let shifted_idx = u32::try_from(idx).unwrap().checked_add(1).unwrap();
36 $name(NonZeroU32::new(shifted_idx).unwrap())
38 fn index(self) -> usize {
39 // See the comment in `Self::new`.
40 // (This cannot underflow because self is NonZeroU32.)
41 usize::try_from(self.0.get() - 1).unwrap()
46 pub fn to_u32_scalar<'tcx>(&self) -> Scalar<Tag> {
47 Scalar::from_u32(self.0.get())
56 #[derive(Default, Debug)]
58 /// The thread that currently owns the lock.
59 owner: Option<ThreadId>,
60 /// How many times the mutex was locked by the owner.
62 /// The queue of threads waiting for this mutex.
63 queue: VecDeque<ThreadId>,
66 declare_id!(RwLockId);
68 /// The read-write lock state.
69 #[derive(Default, Debug)]
71 /// The writer thread that currently owns the lock.
72 writer: Option<ThreadId>,
73 /// The readers that currently own the lock and how many times they acquired
75 readers: HashMap<ThreadId, usize>,
76 /// The queue of writer threads waiting for this lock.
77 writer_queue: VecDeque<ThreadId>,
78 /// The queue of reader threads waiting for this lock.
79 reader_queue: VecDeque<ThreadId>,
82 declare_id!(CondvarId);
84 /// A thread waiting on a conditional variable.
86 struct CondvarWaiter {
87 /// The thread that is waiting on this variable.
89 /// The mutex on which the thread is waiting.
93 /// The conditional variable state.
94 #[derive(Default, Debug)]
96 waiters: VecDeque<CondvarWaiter>,
99 /// The state of all synchronization variables.
100 #[derive(Default, Debug)]
101 pub(super) struct SynchronizationState {
102 mutexes: IndexVec<MutexId, Mutex>,
103 rwlocks: IndexVec<RwLockId, RwLock>,
104 condvars: IndexVec<CondvarId, Condvar>,
107 // Private extension trait for local helper methods
108 impl<'mir, 'tcx: 'mir> EvalContextExtPriv<'mir, 'tcx> for crate::MiriEvalContext<'mir, 'tcx> {}
109 trait EvalContextExtPriv<'mir, 'tcx: 'mir>: crate::MiriEvalContextExt<'mir, 'tcx> {
110 /// Take a reader out of the queue waiting for the lock.
111 /// Returns `true` if some thread got the rwlock.
113 fn rwlock_dequeue_and_lock_reader(&mut self, id: RwLockId) -> bool {
114 let this = self.eval_context_mut();
115 if let Some(reader) = this.machine.threads.sync.rwlocks[id].reader_queue.pop_front() {
116 this.unblock_thread(reader);
117 this.rwlock_reader_lock(id, reader);
124 /// Take the writer out of the queue waiting for the lock.
125 /// Returns `true` if some thread got the rwlock.
127 fn rwlock_dequeue_and_lock_writer(&mut self, id: RwLockId) -> bool {
128 let this = self.eval_context_mut();
129 if let Some(writer) = this.machine.threads.sync.rwlocks[id].writer_queue.pop_front() {
130 this.unblock_thread(writer);
131 this.rwlock_writer_lock(id, writer);
138 /// Take a thread out of the queue waiting for the mutex, and lock
139 /// the mutex for it. Returns `true` if some thread has the mutex now.
141 fn mutex_dequeue_and_lock(&mut self, id: MutexId) -> bool {
142 let this = self.eval_context_mut();
143 if let Some(thread) = this.machine.threads.sync.mutexes[id].queue.pop_front() {
144 this.unblock_thread(thread);
145 this.mutex_lock(id, thread);
153 // Public interface to synchronization primitives. Please note that in most
154 // cases, the function calls are infallible and it is the client's (shim
155 // implementation's) responsibility to detect and deal with erroneous
157 impl<'mir, 'tcx: 'mir> EvalContextExt<'mir, 'tcx> for crate::MiriEvalContext<'mir, 'tcx> {}
158 pub trait EvalContextExt<'mir, 'tcx: 'mir>: crate::MiriEvalContextExt<'mir, 'tcx> {
160 /// Create state for a new mutex.
161 fn mutex_create(&mut self) -> MutexId {
162 let this = self.eval_context_mut();
163 this.machine.threads.sync.mutexes.push(Default::default())
167 /// Get the id of the thread that currently owns this lock.
168 fn mutex_get_owner(&mut self, id: MutexId) -> ThreadId {
169 let this = self.eval_context_ref();
170 this.machine.threads.sync.mutexes[id].owner.unwrap()
175 fn mutex_is_locked(&self, id: MutexId) -> bool {
176 let this = self.eval_context_ref();
177 this.machine.threads.sync.mutexes[id].owner.is_some()
180 /// Lock by setting the mutex owner and increasing the lock count.
181 fn mutex_lock(&mut self, id: MutexId, thread: ThreadId) {
182 let this = self.eval_context_mut();
183 let mutex = &mut this.machine.threads.sync.mutexes[id];
184 if let Some(current_owner) = mutex.owner {
185 assert_eq!(thread, current_owner, "mutex already locked by another thread");
187 mutex.lock_count > 0,
188 "invariant violation: lock_count == 0 iff the thread is unlocked"
191 mutex.owner = Some(thread);
193 mutex.lock_count = mutex.lock_count.checked_add(1).unwrap();
196 /// Try unlocking by decreasing the lock count and returning the old lock
197 /// count. If the lock count reaches 0, release the lock and potentially
198 /// give to a new owner. If the lock was not locked by `expected_owner`,
203 expected_owner: ThreadId,
205 let this = self.eval_context_mut();
206 let mutex = &mut this.machine.threads.sync.mutexes[id];
207 if let Some(current_owner) = mutex.owner {
209 if current_owner != expected_owner {
210 // Only the owner can unlock the mutex.
213 let old_lock_count = mutex.lock_count;
214 mutex.lock_count = old_lock_count
216 .expect("invariant violation: lock_count == 0 iff the thread is unlocked");
217 if mutex.lock_count == 0 {
219 // The mutex is completely unlocked. Try transfering ownership
220 // to another thread.
221 this.mutex_dequeue_and_lock(id);
225 // Mutex is not locked.
231 /// Put the thread into the queue waiting for the mutex.
232 fn mutex_enqueue_and_block(&mut self, id: MutexId, thread: ThreadId) {
233 let this = self.eval_context_mut();
234 assert!(this.mutex_is_locked(id), "queing on unlocked mutex");
235 this.machine.threads.sync.mutexes[id].queue.push_back(thread);
236 this.block_thread(thread);
240 /// Create state for a new read write lock.
241 fn rwlock_create(&mut self) -> RwLockId {
242 let this = self.eval_context_mut();
243 this.machine.threads.sync.rwlocks.push(Default::default())
248 fn rwlock_is_locked(&self, id: RwLockId) -> bool {
249 let this = self.eval_context_ref();
250 let rwlock = &this.machine.threads.sync.rwlocks[id];
252 "rwlock_is_locked: {:?} writer is {:?} and there are {} reader threads (some of which could hold multiple read locks)",
253 id, rwlock.writer, rwlock.readers.len(),
255 rwlock.writer.is_some()|| rwlock.readers.is_empty().not()
259 /// Check if write locked.
260 fn rwlock_is_write_locked(&self, id: RwLockId) -> bool {
261 let this = self.eval_context_ref();
262 let rwlock = &this.machine.threads.sync.rwlocks[id];
263 trace!("rwlock_is_write_locked: {:?} writer is {:?}", id, rwlock.writer);
264 rwlock.writer.is_some()
267 /// Read-lock the lock by adding the `reader` the list of threads that own
269 fn rwlock_reader_lock(&mut self, id: RwLockId, reader: ThreadId) {
270 let this = self.eval_context_mut();
271 assert!(!this.rwlock_is_write_locked(id), "the lock is write locked");
272 trace!("rwlock_reader_lock: {:?} now also held (one more time) by {:?}", id, reader);
273 let count = this.machine.threads.sync.rwlocks[id].readers.entry(reader).or_insert(0);
274 *count = count.checked_add(1).expect("the reader counter overflowed");
277 /// Try read-unlock the lock for `reader` and potentially give the lock to a new owner.
278 /// Returns `true` if succeeded, `false` if this `reader` did not hold the lock.
279 fn rwlock_reader_unlock(&mut self, id: RwLockId, reader: ThreadId) -> bool {
280 let this = self.eval_context_mut();
281 match this.machine.threads.sync.rwlocks[id].readers.entry(reader) {
282 Entry::Occupied(mut entry) => {
283 let count = entry.get_mut();
284 assert!(*count > 0, "rwlock locked with count == 0");
287 trace!("rwlock_reader_unlock: {:?} no longer held by {:?}", id, reader);
290 trace!("rwlock_reader_unlock: {:?} held one less time by {:?}", id, reader);
293 Entry::Vacant(_) => return false, // we did not even own this lock
295 // The thread was a reader. If the lock is not held any more, give it to a writer.
296 if this.rwlock_is_locked(id).not() {
297 this.rwlock_dequeue_and_lock_writer(id);
303 /// Put the reader in the queue waiting for the lock and block it.
304 fn rwlock_enqueue_and_block_reader(
309 let this = self.eval_context_mut();
310 assert!(this.rwlock_is_write_locked(id), "read-queueing on not write locked rwlock");
311 this.machine.threads.sync.rwlocks[id].reader_queue.push_back(reader);
312 this.block_thread(reader);
316 /// Lock by setting the writer that owns the lock.
317 fn rwlock_writer_lock(&mut self, id: RwLockId, writer: ThreadId) {
318 let this = self.eval_context_mut();
319 assert!(!this.rwlock_is_locked(id), "the rwlock is already locked");
320 trace!("rwlock_writer_lock: {:?} now held by {:?}", id, writer);
321 this.machine.threads.sync.rwlocks[id].writer = Some(writer);
325 /// Try to unlock by removing the writer.
326 fn rwlock_writer_unlock(&mut self, id: RwLockId, expected_writer: ThreadId) -> bool {
327 let this = self.eval_context_mut();
328 let rwlock = &mut this.machine.threads.sync.rwlocks[id];
329 if let Some(current_writer) = rwlock.writer {
330 if current_writer != expected_writer {
331 // Only the owner can unlock the rwlock.
334 rwlock.writer = None;
335 trace!("rwlock_writer_unlock: {:?} unlocked by {:?}", id, expected_writer);
336 // The thread was a writer.
338 // We are prioritizing writers here against the readers. As a
339 // result, not only readers can starve writers, but also writers can
341 if this.rwlock_dequeue_and_lock_writer(id) {
342 // Someone got the write lock, nice.
344 // Give the lock to all readers.
345 while this.rwlock_dequeue_and_lock_reader(id) {
356 /// Put the writer in the queue waiting for the lock.
357 fn rwlock_enqueue_and_block_writer(
362 let this = self.eval_context_mut();
363 assert!(this.rwlock_is_locked(id), "write-queueing on unlocked rwlock");
364 this.machine.threads.sync.rwlocks[id].writer_queue.push_back(writer);
365 this.block_thread(writer);
369 /// Create state for a new conditional variable.
370 fn condvar_create(&mut self) -> CondvarId {
371 let this = self.eval_context_mut();
372 this.machine.threads.sync.condvars.push(Default::default())
376 /// Is the conditional variable awaited?
377 fn condvar_is_awaited(&mut self, id: CondvarId) -> bool {
378 let this = self.eval_context_mut();
379 !this.machine.threads.sync.condvars[id].waiters.is_empty()
382 /// Mark that the thread is waiting on the conditional variable.
383 fn condvar_wait(&mut self, id: CondvarId, thread: ThreadId, mutex: MutexId) {
384 let this = self.eval_context_mut();
385 let waiters = &mut this.machine.threads.sync.condvars[id].waiters;
386 assert!(waiters.iter().all(|waiter| waiter.thread != thread), "thread is already waiting");
387 waiters.push_back(CondvarWaiter { thread, mutex });
390 /// Wake up some thread (if there is any) sleeping on the conditional
392 fn condvar_signal(&mut self, id: CondvarId) -> Option<(ThreadId, MutexId)> {
393 let this = self.eval_context_mut();
394 this.machine.threads.sync.condvars[id]
397 .map(|waiter| (waiter.thread, waiter.mutex))
401 /// Remove the thread from the queue of threads waiting on this conditional variable.
402 fn condvar_remove_waiter(&mut self, id: CondvarId, thread: ThreadId) {
403 let this = self.eval_context_mut();
404 this.machine.threads.sync.condvars[id].waiters.retain(|waiter| waiter.thread != thread);