src/sync.rs

   1 use std::collections::{hash_map::Entry, HashMap, VecDeque};
   2 use std::convert::TryFrom;
   3 use std::num::NonZeroU32;
   4 use std::ops::Not;
   5
   6 use rustc_index::vec::{Idx, IndexVec};
   7
   8 use crate::*;
   9
  10 /// We cannot use the `newtype_index!` macro because we have to use 0 as a
  11 /// sentinel value meaning that the identifier is not assigned. This is because
  12 /// the pthreads static initializers initialize memory with zeros (see the
  13 /// `src/shims/sync.rs` file).
  14 macro_rules! declare_id {
  15     ($name: ident) => {
  16         /// 0 is used to indicate that the id was not yet assigned and,
  17         /// therefore, is not a valid identifier.
  18         #[derive(Clone, Copy, Debug, PartialOrd, Ord, PartialEq, Eq, Hash)]
  19         pub struct $name(NonZeroU32);
  20
  21         impl $name {
  22             // Panics if `id == 0`.
  23             pub fn from_u32(id: u32) -> Self {
  24                 Self(NonZeroU32::new(id).unwrap())
  25             }
  26         }
  27
  28         impl Idx for $name {
  29             fn new(idx: usize) -> Self {
  30                 // We use 0 as a sentinel value (see the comment above) and,
  31                 // therefore, need to shift by one when converting from an index
  32                 // into a vector.
  33                 $name(NonZeroU32::new(u32::try_from(idx).unwrap() + 1).unwrap())
  34             }
  35             fn index(self) -> usize {
  36                 // See the comment in `Self::new`.
  37                 usize::try_from(self.0.get() - 1).unwrap()
  38             }
  39         }
  40
  41         impl $name {
  42             pub fn to_u32_scalar<'tcx>(&self) -> Scalar<Tag> {
  43                 Scalar::from_u32(self.0.get())
  44             }
  45         }
  46     };
  47 }
  48
  49 declare_id!(MutexId);
  50
  51 /// The mutex state.
  52 #[derive(Default, Debug)]
  53 struct Mutex {
  54     /// The thread that currently owns the lock.
  55     owner: Option<ThreadId>,
  56     /// How many times the mutex was locked by the owner.
  57     lock_count: usize,
  58     /// The queue of threads waiting for this mutex.
  59     queue: VecDeque<ThreadId>,
  60 }
  61
  62 declare_id!(RwLockId);
  63
  64 /// The read-write lock state.
  65 #[derive(Default, Debug)]
  66 struct RwLock {
  67     /// The writer thread that currently owns the lock.
  68     writer: Option<ThreadId>,
  69     /// The readers that currently own the lock and how many times they acquired
  70     /// the lock.
  71     readers: HashMap<ThreadId, usize>,
  72     /// The queue of writer threads waiting for this lock.
  73     writer_queue: VecDeque<ThreadId>,
  74     /// The queue of reader threads waiting for this lock.
  75     reader_queue: VecDeque<ThreadId>,
  76 }
  77
  78 declare_id!(CondvarId);
  79
  80 /// A thread waiting on a conditional variable.
  81 #[derive(Debug)]
  82 struct CondvarWaiter {
  83     /// The thread that is waiting on this variable.
  84     thread: ThreadId,
  85     /// The mutex on which the thread is waiting.
  86     mutex: MutexId,
  87 }
  88
  89 /// The conditional variable state.
  90 #[derive(Default, Debug)]
  91 struct Condvar {
  92     waiters: VecDeque<CondvarWaiter>,
  93 }
  94
  95 /// The state of all synchronization variables.
  96 #[derive(Default, Debug)]
  97 pub(super) struct SynchronizationState {
  98     mutexes: IndexVec<MutexId, Mutex>,
  99     rwlocks: IndexVec<RwLockId, RwLock>,
 100     condvars: IndexVec<CondvarId, Condvar>,
 101 }
 102
 103 // Public interface to synchronization primitives. Please note that in most
 104 // cases, the function calls are infallible and it is the client's (shim
 105 // implementation's) responsibility to detect and deal with erroneous
 106 // situations.
 107 impl<'mir, 'tcx: 'mir> EvalContextExt<'mir, 'tcx> for crate::MiriEvalContext<'mir, 'tcx> {}
 108 pub trait EvalContextExt<'mir, 'tcx: 'mir>: crate::MiriEvalContextExt<'mir, 'tcx> {
 109     #[inline]
 110     /// Create state for a new mutex.
 111     fn mutex_create(&mut self) -> MutexId {
 112         let this = self.eval_context_mut();
 113         this.machine.threads.sync.mutexes.push(Default::default())
 114     }
 115
 116     #[inline]
 117     /// Get the id of the thread that currently owns this lock.
 118     fn mutex_get_owner(&mut self, id: MutexId) -> ThreadId {
 119         let this = self.eval_context_ref();
 120         this.machine.threads.sync.mutexes[id].owner.unwrap()
 121     }
 122
 123     #[inline]
 124     /// Check if locked.
 125     fn mutex_is_locked(&mut self, id: MutexId) -> bool {
 126         let this = self.eval_context_mut();
 127         this.machine.threads.sync.mutexes[id].owner.is_some()
 128     }
 129
 130     /// Lock by setting the mutex owner and increasing the lock count.
 131     fn mutex_lock(&mut self, id: MutexId, thread: ThreadId) {
 132         let this = self.eval_context_mut();
 133         let mutex = &mut this.machine.threads.sync.mutexes[id];
 134         if let Some(current_owner) = mutex.owner {
 135             assert_eq!(thread, current_owner, "mutex already locked by another thread");
 136             assert!(
 137                 mutex.lock_count > 0,
 138                 "invariant violation: lock_count == 0 iff the thread is unlocked"
 139             );
 140         } else {
 141             mutex.owner = Some(thread);
 142         }
 143         mutex.lock_count = mutex.lock_count.checked_add(1).unwrap();
 144     }
 145
 146     /// Try unlocking by decreasing the lock count and returning the old owner
 147     /// and the old lock count. If the lock count reaches 0, release the lock
 148     /// and potentially give to a new owner. If the lock was not locked, return
 149     /// `None`.
 150     ///
 151     /// Note: It is the caller's responsibility to check that the thread that
 152     /// unlocked the lock actually is the same one, which owned it.
 153     fn mutex_unlock(&mut self, id: MutexId) -> InterpResult<'tcx, Option<(ThreadId, usize)>> {
 154         let this = self.eval_context_mut();
 155         let mutex = &mut this.machine.threads.sync.mutexes[id];
 156         if let Some(current_owner) = mutex.owner {
 157             // Mutex is locked.
 158             let old_lock_count = mutex.lock_count;
 159             mutex.lock_count = old_lock_count
 160                 .checked_sub(1)
 161                 .expect("invariant violation: lock_count == 0 iff the thread is unlocked");
 162             if mutex.lock_count == 0 {
 163                 mutex.owner = None;
 164                 // The mutex is completely unlocked. Try transfering ownership
 165                 // to another thread.
 166                 if let Some(new_owner) = this.mutex_dequeue(id) {
 167                     this.mutex_lock(id, new_owner);
 168                     this.unblock_thread(new_owner)?;
 169                 }
 170             }
 171             Ok(Some((current_owner, old_lock_count)))
 172         } else {
 173             // Mutex is unlocked.
 174             Ok(None)
 175         }
 176     }
 177
 178     #[inline]
 179     /// Put the thread into the queue waiting for the lock.
 180     fn mutex_enqueue(&mut self, id: MutexId, thread: ThreadId) {
 181         let this = self.eval_context_mut();
 182         this.machine.threads.sync.mutexes[id].queue.push_back(thread);
 183     }
 184
 185     #[inline]
 186     /// Take a thread out of the queue waiting for the lock.
 187     fn mutex_dequeue(&mut self, id: MutexId) -> Option<ThreadId> {
 188         let this = self.eval_context_mut();
 189         this.machine.threads.sync.mutexes[id].queue.pop_front()
 190     }
 191
 192     #[inline]
 193     /// Create state for a new read write lock.
 194     fn rwlock_create(&mut self) -> RwLockId {
 195         let this = self.eval_context_mut();
 196         this.machine.threads.sync.rwlocks.push(Default::default())
 197     }
 198
 199     #[inline]
 200     /// Check if locked.
 201     fn rwlock_is_locked(&mut self, id: RwLockId) -> bool {
 202         let this = self.eval_context_mut();
 203         this.machine.threads.sync.rwlocks[id].writer.is_some()
 204             || this.machine.threads.sync.rwlocks[id].readers.is_empty().not()
 205     }
 206
 207     #[inline]
 208     /// Check if write locked.
 209     fn rwlock_is_write_locked(&mut self, id: RwLockId) -> bool {
 210         let this = self.eval_context_mut();
 211         this.machine.threads.sync.rwlocks[id].writer.is_some()
 212     }
 213
 214     /// Read-lock the lock by adding the `reader` the list of threads that own
 215     /// this lock.
 216     fn rwlock_reader_lock(&mut self, id: RwLockId, reader: ThreadId) {
 217         let this = self.eval_context_mut();
 218         assert!(!this.rwlock_is_write_locked(id), "the lock is write locked");
 219         let count = this.machine.threads.sync.rwlocks[id].readers.entry(reader).or_insert(0);
 220         *count = count.checked_add(1).expect("the reader counter overflowed");
 221     }
 222
 223     /// Try read-unlock the lock for `reader`. Returns `true` if succeeded,
 224     /// `false` if this `reader` did not hold the lock.
 225     fn rwlock_reader_unlock(&mut self, id: RwLockId, reader: ThreadId) -> bool {
 226         let this = self.eval_context_mut();
 227         match this.machine.threads.sync.rwlocks[id].readers.entry(reader) {
 228             Entry::Occupied(mut entry) => {
 229                 let count = entry.get_mut();
 230                 *count -= 1;
 231                 if *count == 0 {
 232                     entry.remove();
 233                 }
 234                 true
 235             }
 236             Entry::Vacant(_) => false,
 237         }
 238     }
 239
 240     #[inline]
 241     /// Put the reader in the queue waiting for the lock and block it.
 242     fn rwlock_enqueue_and_block_reader(
 243         &mut self,
 244         id: RwLockId,
 245         reader: ThreadId,
 246     ) -> InterpResult<'tcx> {
 247         let this = self.eval_context_mut();
 248         assert!(this.rwlock_is_write_locked(id), "queueing on not write locked lock");
 249         this.machine.threads.sync.rwlocks[id].reader_queue.push_back(reader);
 250         this.block_thread(reader)
 251     }
 252
 253     #[inline]
 254     /// Take a reader out the queue waiting for the lock.
 255     fn rwlock_dequeue_reader(&mut self, id: RwLockId) -> Option<ThreadId> {
 256         let this = self.eval_context_mut();
 257         this.machine.threads.sync.rwlocks[id].reader_queue.pop_front()
 258     }
 259
 260     #[inline]
 261     /// Lock by setting the writer that owns the lock.
 262     fn rwlock_writer_lock(&mut self, id: RwLockId, writer: ThreadId) {
 263         let this = self.eval_context_mut();
 264         assert!(!this.rwlock_is_locked(id), "the lock is already locked");
 265         this.machine.threads.sync.rwlocks[id].writer = Some(writer);
 266     }
 267
 268     #[inline]
 269     /// Try to unlock by removing the writer.
 270     fn rwlock_writer_unlock(&mut self, id: RwLockId) -> Option<ThreadId> {
 271         let this = self.eval_context_mut();
 272         this.machine.threads.sync.rwlocks[id].writer.take()
 273     }
 274
 275     #[inline]
 276     /// Put the writer in the queue waiting for the lock.
 277     fn rwlock_enqueue_and_block_writer(
 278         &mut self,
 279         id: RwLockId,
 280         writer: ThreadId,
 281     ) -> InterpResult<'tcx> {
 282         let this = self.eval_context_mut();
 283         assert!(this.rwlock_is_locked(id), "queueing on unlocked lock");
 284         this.machine.threads.sync.rwlocks[id].writer_queue.push_back(writer);
 285         this.block_thread(writer)
 286     }
 287
 288     #[inline]
 289     /// Take the writer out the queue waiting for the lock.
 290     fn rwlock_dequeue_writer(&mut self, id: RwLockId) -> Option<ThreadId> {
 291         let this = self.eval_context_mut();
 292         this.machine.threads.sync.rwlocks[id].writer_queue.pop_front()
 293     }
 294
 295     #[inline]
 296     /// Create state for a new conditional variable.
 297     fn condvar_create(&mut self) -> CondvarId {
 298         let this = self.eval_context_mut();
 299         this.machine.threads.sync.condvars.push(Default::default())
 300     }
 301
 302     #[inline]
 303     /// Is the conditional variable awaited?
 304     fn condvar_is_awaited(&mut self, id: CondvarId) -> bool {
 305         let this = self.eval_context_mut();
 306         !this.machine.threads.sync.condvars[id].waiters.is_empty()
 307     }
 308
 309     /// Mark that the thread is waiting on the conditional variable.
 310     fn condvar_wait(&mut self, id: CondvarId, thread: ThreadId, mutex: MutexId) {
 311         let this = self.eval_context_mut();
 312         let waiters = &mut this.machine.threads.sync.condvars[id].waiters;
 313         assert!(waiters.iter().all(|waiter| waiter.thread != thread), "thread is already waiting");
 314         waiters.push_back(CondvarWaiter { thread, mutex });
 315     }
 316
 317     /// Wake up some thread (if there is any) sleeping on the conditional
 318     /// variable.
 319     fn condvar_signal(&mut self, id: CondvarId) -> Option<(ThreadId, MutexId)> {
 320         let this = self.eval_context_mut();
 321         this.machine.threads.sync.condvars[id]
 322             .waiters
 323             .pop_front()
 324             .map(|waiter| (waiter.thread, waiter.mutex))
 325     }
 326
 327     #[inline]
 328     /// Remove the thread from the queue of threads waiting on this conditional variable.
 329     fn condvar_remove_waiter(&mut self, id: CondvarId, thread: ThreadId) {
 330         let this = self.eval_context_mut();
 331         this.machine.threads.sync.condvars[id].waiters.retain(|waiter| waiter.thread != thread);
 332     }
 333 }