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                 let shifted_idx = u32::try_from(idx).unwrap().checked_add(1).unwrap();
  34                 $name(NonZeroU32::new(shifted_idx).unwrap())
  35             }
  36             fn index(self) -> usize {
  37                 // See the comment in `Self::new`.
  38                 // (This cannot underflow because self is NonZeroU32.)
  39                 usize::try_from(self.0.get() - 1).unwrap()
  40             }
  41         }
  42
  43         impl $name {
  44             pub fn to_u32_scalar<'tcx>(&self) -> Scalar<Tag> {
  45                 Scalar::from_u32(self.0.get())
  46             }
  47         }
  48     };
  49 }
  50
  51 declare_id!(MutexId);
  52
  53 /// The mutex state.
  54 #[derive(Default, Debug)]
  55 struct Mutex {
  56     /// The thread that currently owns the lock.
  57     owner: Option<ThreadId>,
  58     /// How many times the mutex was locked by the owner.
  59     lock_count: usize,
  60     /// The queue of threads waiting for this mutex.
  61     queue: VecDeque<ThreadId>,
  62 }
  63
  64 declare_id!(RwLockId);
  65
  66 /// The read-write lock state.
  67 #[derive(Default, Debug)]
  68 struct RwLock {
  69     /// The writer thread that currently owns the lock.
  70     writer: Option<ThreadId>,
  71     /// The readers that currently own the lock and how many times they acquired
  72     /// the lock.
  73     readers: HashMap<ThreadId, usize>,
  74     /// The queue of writer threads waiting for this lock.
  75     writer_queue: VecDeque<ThreadId>,
  76     /// The queue of reader threads waiting for this lock.
  77     reader_queue: VecDeque<ThreadId>,
  78 }
  79
  80 declare_id!(CondvarId);
  81
  82 /// A thread waiting on a conditional variable.
  83 #[derive(Debug)]
  84 struct CondvarWaiter {
  85     /// The thread that is waiting on this variable.
  86     thread: ThreadId,
  87     /// The mutex on which the thread is waiting.
  88     mutex: MutexId,
  89 }
  90
  91 /// The conditional variable state.
  92 #[derive(Default, Debug)]
  93 struct Condvar {
  94     waiters: VecDeque<CondvarWaiter>,
  95 }
  96
  97 /// The state of all synchronization variables.
  98 #[derive(Default, Debug)]
  99 pub(super) struct SynchronizationState {
 100     mutexes: IndexVec<MutexId, Mutex>,
 101     rwlocks: IndexVec<RwLockId, RwLock>,
 102     condvars: IndexVec<CondvarId, Condvar>,
 103 }
 104
 105 // Public interface to synchronization primitives. Please note that in most
 106 // cases, the function calls are infallible and it is the client's (shim
 107 // implementation's) responsibility to detect and deal with erroneous
 108 // situations.
 109 impl<'mir, 'tcx: 'mir> EvalContextExt<'mir, 'tcx> for crate::MiriEvalContext<'mir, 'tcx> {}
 110 pub trait EvalContextExt<'mir, 'tcx: 'mir>: crate::MiriEvalContextExt<'mir, 'tcx> {
 111     #[inline]
 112     /// Create state for a new mutex.
 113     fn mutex_create(&mut self) -> MutexId {
 114         let this = self.eval_context_mut();
 115         this.machine.threads.sync.mutexes.push(Default::default())
 116     }
 117
 118     #[inline]
 119     /// Get the id of the thread that currently owns this lock.
 120     fn mutex_get_owner(&mut self, id: MutexId) -> ThreadId {
 121         let this = self.eval_context_ref();
 122         this.machine.threads.sync.mutexes[id].owner.unwrap()
 123     }
 124
 125     #[inline]
 126     /// Check if locked.
 127     fn mutex_is_locked(&mut self, id: MutexId) -> bool {
 128         let this = self.eval_context_mut();
 129         this.machine.threads.sync.mutexes[id].owner.is_some()
 130     }
 131
 132     /// Lock by setting the mutex owner and increasing the lock count.
 133     fn mutex_lock(&mut self, id: MutexId, thread: ThreadId) {
 134         let this = self.eval_context_mut();
 135         let mutex = &mut this.machine.threads.sync.mutexes[id];
 136         if let Some(current_owner) = mutex.owner {
 137             assert_eq!(thread, current_owner, "mutex already locked by another thread");
 138             assert!(
 139                 mutex.lock_count > 0,
 140                 "invariant violation: lock_count == 0 iff the thread is unlocked"
 141             );
 142         } else {
 143             mutex.owner = Some(thread);
 144         }
 145         mutex.lock_count = mutex.lock_count.checked_add(1).unwrap();
 146     }
 147
 148     /// Try unlocking by decreasing the lock count and returning the old lock
 149     /// count. If the lock count reaches 0, release the lock and potentially
 150     /// give to a new owner. If the lock was not locked by `expected_owner`,
 151     /// return `None`.
 152     fn mutex_unlock(
 153         &mut self,
 154         id: MutexId,
 155         expected_owner: ThreadId,
 156     ) -> InterpResult<'tcx, Option<usize>> {
 157         let this = self.eval_context_mut();
 158         let mutex = &mut this.machine.threads.sync.mutexes[id];
 159         if let Some(current_owner) = mutex.owner {
 160             // Mutex is locked.
 161             if current_owner != expected_owner {
 162                 // Only the owner can unlock the mutex.
 163                 return Ok(None);
 164             }
 165             let old_lock_count = mutex.lock_count;
 166             mutex.lock_count = old_lock_count
 167                 .checked_sub(1)
 168                 .expect("invariant violation: lock_count == 0 iff the thread is unlocked");
 169             if mutex.lock_count == 0 {
 170                 mutex.owner = None;
 171                 // The mutex is completely unlocked. Try transfering ownership
 172                 // to another thread.
 173                 this.mutex_dequeue_and_lock(id);
 174             }
 175             Ok(Some(old_lock_count))
 176         } else {
 177             // Mutex is unlocked.
 178             Ok(None)
 179         }
 180     }
 181
 182     #[inline]
 183     /// Put the thread into the queue waiting for the mutex.
 184     fn mutex_enqueue_and_block(&mut self, id: MutexId, thread: ThreadId) {
 185         let this = self.eval_context_mut();
 186         assert!(this.mutex_is_locked(id), "queing on unlocked mutex");
 187         this.machine.threads.sync.mutexes[id].queue.push_back(thread);
 188         this.block_thread(thread);
 189     }
 190
 191     #[inline]
 192     /// Take a thread out of the queue waiting for the mutex, and lock
 193     /// the mutex for it. Returns `true` if some thread has the mutex now.
 194     fn mutex_dequeue_and_lock(&mut self, id: MutexId) -> bool {
 195         let this = self.eval_context_mut();
 196         if let Some(thread) = this.machine.threads.sync.mutexes[id].queue.pop_front() {
 197             this.unblock_thread(thread);
 198             this.mutex_lock(id, thread);
 199             true
 200         } else {
 201             false
 202         }
 203     }
 204
 205     #[inline]
 206     /// Create state for a new read write lock.
 207     fn rwlock_create(&mut self) -> RwLockId {
 208         let this = self.eval_context_mut();
 209         this.machine.threads.sync.rwlocks.push(Default::default())
 210     }
 211
 212     #[inline]
 213     /// Check if locked.
 214     fn rwlock_is_locked(&mut self, id: RwLockId) -> bool {
 215         let this = self.eval_context_mut();
 216         this.machine.threads.sync.rwlocks[id].writer.is_some()
 217             || this.machine.threads.sync.rwlocks[id].readers.is_empty().not()
 218     }
 219
 220     #[inline]
 221     /// Check if write locked.
 222     fn rwlock_is_write_locked(&mut self, id: RwLockId) -> bool {
 223         let this = self.eval_context_mut();
 224         this.machine.threads.sync.rwlocks[id].writer.is_some()
 225     }
 226
 227     /// Read-lock the lock by adding the `reader` the list of threads that own
 228     /// this lock.
 229     fn rwlock_reader_lock(&mut self, id: RwLockId, reader: ThreadId) {
 230         let this = self.eval_context_mut();
 231         assert!(!this.rwlock_is_write_locked(id), "the lock is write locked");
 232         let count = this.machine.threads.sync.rwlocks[id].readers.entry(reader).or_insert(0);
 233         *count = count.checked_add(1).expect("the reader counter overflowed");
 234     }
 235
 236     /// Try read-unlock the lock for `reader`. Returns `true` if succeeded,
 237     /// `false` if this `reader` did not hold the lock.
 238     fn rwlock_reader_unlock(&mut self, id: RwLockId, reader: ThreadId) -> bool {
 239         let this = self.eval_context_mut();
 240         match this.machine.threads.sync.rwlocks[id].readers.entry(reader) {
 241             Entry::Occupied(mut entry) => {
 242                 let count = entry.get_mut();
 243                 assert!(*count > 0, "rwlock locked with count == 0");
 244                 *count -= 1;
 245                 if *count == 0 {
 246                     entry.remove();
 247                 }
 248                 true
 249             }
 250             Entry::Vacant(_) => false,
 251         }
 252     }
 253
 254     #[inline]
 255     /// Put the reader in the queue waiting for the lock and block it.
 256     fn rwlock_enqueue_and_block_reader(
 257         &mut self,
 258         id: RwLockId,
 259         reader: ThreadId,
 260     ) {
 261         let this = self.eval_context_mut();
 262         assert!(this.rwlock_is_write_locked(id), "queueing on not write locked lock");
 263         this.machine.threads.sync.rwlocks[id].reader_queue.push_back(reader);
 264         this.block_thread(reader);
 265     }
 266
 267     #[inline]
 268     /// Take a reader out the queue waiting for the lock.
 269     /// Returns `true` if some thread got the rwlock.
 270     fn rwlock_dequeue_and_lock_reader(&mut self, id: RwLockId) -> bool {
 271         let this = self.eval_context_mut();
 272         if let Some(reader) = this.machine.threads.sync.rwlocks[id].reader_queue.pop_front() {
 273             this.unblock_thread(reader);
 274             this.rwlock_reader_lock(id, reader);
 275             true
 276         } else {
 277             false
 278         }
 279     }
 280
 281     #[inline]
 282     /// Lock by setting the writer that owns the lock.
 283     fn rwlock_writer_lock(&mut self, id: RwLockId, writer: ThreadId) {
 284         let this = self.eval_context_mut();
 285         assert!(!this.rwlock_is_locked(id), "the rwlock is already locked");
 286         this.machine.threads.sync.rwlocks[id].writer = Some(writer);
 287     }
 288
 289     #[inline]
 290     /// Try to unlock by removing the writer.
 291     fn rwlock_writer_unlock(&mut self, id: RwLockId) -> Option<ThreadId> {
 292         let this = self.eval_context_mut();
 293         this.machine.threads.sync.rwlocks[id].writer.take()
 294     }
 295
 296     #[inline]
 297     /// Put the writer in the queue waiting for the lock.
 298     fn rwlock_enqueue_and_block_writer(
 299         &mut self,
 300         id: RwLockId,
 301         writer: ThreadId,
 302     ) {
 303         let this = self.eval_context_mut();
 304         assert!(this.rwlock_is_locked(id), "queueing on unlocked lock");
 305         this.machine.threads.sync.rwlocks[id].writer_queue.push_back(writer);
 306         this.block_thread(writer);
 307     }
 308
 309     #[inline]
 310     /// Take the writer out the queue waiting for the lock.
 311     /// Returns `true` if some thread got the rwlock.
 312     fn rwlock_dequeue_and_lock_writer(&mut self, id: RwLockId) -> bool {
 313         let this = self.eval_context_mut();
 314         if let Some(writer) = this.machine.threads.sync.rwlocks[id].writer_queue.pop_front() {
 315             this.unblock_thread(writer);
 316             this.rwlock_writer_lock(id, writer);
 317             true
 318         } else {
 319             false
 320         }
 321     }
 322
 323     #[inline]
 324     /// Create state for a new conditional variable.
 325     fn condvar_create(&mut self) -> CondvarId {
 326         let this = self.eval_context_mut();
 327         this.machine.threads.sync.condvars.push(Default::default())
 328     }
 329
 330     #[inline]
 331     /// Is the conditional variable awaited?
 332     fn condvar_is_awaited(&mut self, id: CondvarId) -> bool {
 333         let this = self.eval_context_mut();
 334         !this.machine.threads.sync.condvars[id].waiters.is_empty()
 335     }
 336
 337     /// Mark that the thread is waiting on the conditional variable.
 338     fn condvar_wait(&mut self, id: CondvarId, thread: ThreadId, mutex: MutexId) {
 339         let this = self.eval_context_mut();
 340         let waiters = &mut this.machine.threads.sync.condvars[id].waiters;
 341         assert!(waiters.iter().all(|waiter| waiter.thread != thread), "thread is already waiting");
 342         waiters.push_back(CondvarWaiter { thread, mutex });
 343     }
 344
 345     /// Wake up some thread (if there is any) sleeping on the conditional
 346     /// variable.
 347     fn condvar_signal(&mut self, id: CondvarId) -> Option<(ThreadId, MutexId)> {
 348         let this = self.eval_context_mut();
 349         this.machine.threads.sync.condvars[id]
 350             .waiters
 351             .pop_front()
 352             .map(|waiter| (waiter.thread, waiter.mutex))
 353     }
 354
 355     #[inline]
 356     /// Remove the thread from the queue of threads waiting on this conditional variable.
 357     fn condvar_remove_waiter(&mut self, id: CondvarId, thread: ThreadId) {
 358         let this = self.eval_context_mut();
 359         this.machine.threads.sync.condvars[id].waiters.retain(|waiter| waiter.thread != thread);
 360     }
 361 }