src/sync.rs

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