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