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 log::trace;
   7
   8 use rustc_index::vec::{Idx, IndexVec};
   9
  10 use crate::*;
  11
  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 {
  17     ($name: ident) => {
  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);
  22
  23         impl $name {
  24             // Panics if `id == 0`.
  25             pub fn from_u32(id: u32) -> Self {
  26                 Self(NonZeroU32::new(id).unwrap())
  27             }
  28         }
  29
  30         impl Idx for $name {
  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
  34                 // into a vector.
  35                 let shifted_idx = u32::try_from(idx).unwrap().checked_add(1).unwrap();
  36                 $name(NonZeroU32::new(shifted_idx).unwrap())
  37             }
  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()
  42             }
  43         }
  44
  45         impl $name {
  46             pub fn to_u32_scalar<'tcx>(&self) -> Scalar<Tag> {
  47                 Scalar::from_u32(self.0.get())
  48             }
  49         }
  50     };
  51 }
  52
  53 declare_id!(MutexId);
  54
  55 /// The mutex state.
  56 #[derive(Default, Debug)]
  57 struct Mutex {
  58     /// The thread that currently owns the lock.
  59     owner: Option<ThreadId>,
  60     /// How many times the mutex was locked by the owner.
  61     lock_count: usize,
  62     /// The queue of threads waiting for this mutex.
  63     queue: VecDeque<ThreadId>,
  64 }
  65
  66 declare_id!(RwLockId);
  67
  68 /// The read-write lock state.
  69 #[derive(Default, Debug)]
  70 struct RwLock {
  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
  74     /// the lock.
  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>,
  80 }
  81
  82 declare_id!(CondvarId);
  83
  84 /// A thread waiting on a conditional variable.
  85 #[derive(Debug)]
  86 struct CondvarWaiter {
  87     /// The thread that is waiting on this variable.
  88     thread: ThreadId,
  89     /// The mutex on which the thread is waiting.
  90     mutex: MutexId,
  91 }
  92
  93 /// The conditional variable state.
  94 #[derive(Default, Debug)]
  95 struct Condvar {
  96     waiters: VecDeque<CondvarWaiter>,
  97 }
  98
  99 /// The futex state.
 100 #[derive(Default, Debug)]
 101 struct Futex {
 102     waiters: VecDeque<FutexWaiter>,
 103 }
 104
 105 /// A thread waiting on a futex.
 106 #[derive(Debug)]
 107 struct FutexWaiter {
 108     /// The thread that is waiting on this futex.
 109     thread: ThreadId,
 110 }
 111
 112 /// The state of all synchronization variables.
 113 #[derive(Default, Debug)]
 114 pub(super) struct SynchronizationState {
 115     mutexes: IndexVec<MutexId, Mutex>,
 116     rwlocks: IndexVec<RwLockId, RwLock>,
 117     condvars: IndexVec<CondvarId, Condvar>,
 118     futexes: HashMap<Pointer<stacked_borrows::Tag>, Futex>,
 119 }
 120
 121 // Private extension trait for local helper methods
 122 impl<'mir, 'tcx: 'mir> EvalContextExtPriv<'mir, 'tcx> for crate::MiriEvalContext<'mir, 'tcx> {}
 123 trait EvalContextExtPriv<'mir, 'tcx: 'mir>: crate::MiriEvalContextExt<'mir, 'tcx> {
 124     /// Take a reader out of the queue waiting for the lock.
 125     /// Returns `true` if some thread got the rwlock.
 126     #[inline]
 127     fn rwlock_dequeue_and_lock_reader(&mut self, id: RwLockId) -> bool {
 128         let this = self.eval_context_mut();
 129         if let Some(reader) = this.machine.threads.sync.rwlocks[id].reader_queue.pop_front() {
 130             this.unblock_thread(reader);
 131             this.rwlock_reader_lock(id, reader);
 132             true
 133         } else {
 134             false
 135         }
 136     }
 137
 138     /// Take the writer out of the queue waiting for the lock.
 139     /// Returns `true` if some thread got the rwlock.
 140     #[inline]
 141     fn rwlock_dequeue_and_lock_writer(&mut self, id: RwLockId) -> bool {
 142         let this = self.eval_context_mut();
 143         if let Some(writer) = this.machine.threads.sync.rwlocks[id].writer_queue.pop_front() {
 144             this.unblock_thread(writer);
 145             this.rwlock_writer_lock(id, writer);
 146             true
 147         } else {
 148             false
 149         }
 150     }
 151
 152     /// Take a thread out of the queue waiting for the mutex, and lock
 153     /// the mutex for it. Returns `true` if some thread has the mutex now.
 154     #[inline]
 155     fn mutex_dequeue_and_lock(&mut self, id: MutexId) -> bool {
 156         let this = self.eval_context_mut();
 157         if let Some(thread) = this.machine.threads.sync.mutexes[id].queue.pop_front() {
 158             this.unblock_thread(thread);
 159             this.mutex_lock(id, thread);
 160             true
 161         } else {
 162             false
 163         }
 164     }
 165 }
 166
 167 // Public interface to synchronization primitives. Please note that in most
 168 // cases, the function calls are infallible and it is the client's (shim
 169 // implementation's) responsibility to detect and deal with erroneous
 170 // situations.
 171 impl<'mir, 'tcx: 'mir> EvalContextExt<'mir, 'tcx> for crate::MiriEvalContext<'mir, 'tcx> {}
 172 pub trait EvalContextExt<'mir, 'tcx: 'mir>: crate::MiriEvalContextExt<'mir, 'tcx> {
 173     #[inline]
 174     /// Create state for a new mutex.
 175     fn mutex_create(&mut self) -> MutexId {
 176         let this = self.eval_context_mut();
 177         this.machine.threads.sync.mutexes.push(Default::default())
 178     }
 179
 180     #[inline]
 181     /// Get the id of the thread that currently owns this lock.
 182     fn mutex_get_owner(&mut self, id: MutexId) -> ThreadId {
 183         let this = self.eval_context_ref();
 184         this.machine.threads.sync.mutexes[id].owner.unwrap()
 185     }
 186
 187     #[inline]
 188     /// Check if locked.
 189     fn mutex_is_locked(&self, id: MutexId) -> bool {
 190         let this = self.eval_context_ref();
 191         this.machine.threads.sync.mutexes[id].owner.is_some()
 192     }
 193
 194     /// Lock by setting the mutex owner and increasing the lock count.
 195     fn mutex_lock(&mut self, id: MutexId, thread: ThreadId) {
 196         let this = self.eval_context_mut();
 197         let mutex = &mut this.machine.threads.sync.mutexes[id];
 198         if let Some(current_owner) = mutex.owner {
 199             assert_eq!(thread, current_owner, "mutex already locked by another thread");
 200             assert!(
 201                 mutex.lock_count > 0,
 202                 "invariant violation: lock_count == 0 iff the thread is unlocked"
 203             );
 204         } else {
 205             mutex.owner = Some(thread);
 206         }
 207         mutex.lock_count = mutex.lock_count.checked_add(1).unwrap();
 208     }
 209
 210     /// Try unlocking by decreasing the lock count and returning the old lock
 211     /// count. If the lock count reaches 0, release the lock and potentially
 212     /// give to a new owner. If the lock was not locked by `expected_owner`,
 213     /// return `None`.
 214     fn mutex_unlock(
 215         &mut self,
 216         id: MutexId,
 217         expected_owner: ThreadId,
 218     ) -> Option<usize> {
 219         let this = self.eval_context_mut();
 220         let mutex = &mut this.machine.threads.sync.mutexes[id];
 221         if let Some(current_owner) = mutex.owner {
 222             // Mutex is locked.
 223             if current_owner != expected_owner {
 224                 // Only the owner can unlock the mutex.
 225                 return None;
 226             }
 227             let old_lock_count = mutex.lock_count;
 228             mutex.lock_count = old_lock_count
 229                 .checked_sub(1)
 230                 .expect("invariant violation: lock_count == 0 iff the thread is unlocked");
 231             if mutex.lock_count == 0 {
 232                 mutex.owner = None;
 233                 // The mutex is completely unlocked. Try transfering ownership
 234                 // to another thread.
 235                 this.mutex_dequeue_and_lock(id);
 236             }
 237             Some(old_lock_count)
 238         } else {
 239             // Mutex is not locked.
 240             None
 241         }
 242     }
 243
 244     #[inline]
 245     /// Put the thread into the queue waiting for the mutex.
 246     fn mutex_enqueue_and_block(&mut self, id: MutexId, thread: ThreadId) {
 247         let this = self.eval_context_mut();
 248         assert!(this.mutex_is_locked(id), "queing on unlocked mutex");
 249         this.machine.threads.sync.mutexes[id].queue.push_back(thread);
 250         this.block_thread(thread);
 251     }
 252
 253     #[inline]
 254     /// Create state for a new read write lock.
 255     fn rwlock_create(&mut self) -> RwLockId {
 256         let this = self.eval_context_mut();
 257         this.machine.threads.sync.rwlocks.push(Default::default())
 258     }
 259
 260     #[inline]
 261     /// Check if locked.
 262     fn rwlock_is_locked(&self, id: RwLockId) -> bool {
 263         let this = self.eval_context_ref();
 264         let rwlock = &this.machine.threads.sync.rwlocks[id];
 265         trace!(
 266             "rwlock_is_locked: {:?} writer is {:?} and there are {} reader threads (some of which could hold multiple read locks)",
 267             id, rwlock.writer, rwlock.readers.len(),
 268         );
 269         rwlock.writer.is_some()|| rwlock.readers.is_empty().not()
 270     }
 271
 272     #[inline]
 273     /// Check if write locked.
 274     fn rwlock_is_write_locked(&self, id: RwLockId) -> bool {
 275         let this = self.eval_context_ref();
 276         let rwlock = &this.machine.threads.sync.rwlocks[id];
 277         trace!("rwlock_is_write_locked: {:?} writer is {:?}", id, rwlock.writer);
 278         rwlock.writer.is_some()
 279     }
 280
 281     /// Read-lock the lock by adding the `reader` the list of threads that own
 282     /// this lock.
 283     fn rwlock_reader_lock(&mut self, id: RwLockId, reader: ThreadId) {
 284         let this = self.eval_context_mut();
 285         assert!(!this.rwlock_is_write_locked(id), "the lock is write locked");
 286         trace!("rwlock_reader_lock: {:?} now also held (one more time) by {:?}", id, reader);
 287         let count = this.machine.threads.sync.rwlocks[id].readers.entry(reader).or_insert(0);
 288         *count = count.checked_add(1).expect("the reader counter overflowed");
 289     }
 290
 291     /// Try read-unlock the lock for `reader` and potentially give the lock to a new owner.
 292     /// Returns `true` if succeeded, `false` if this `reader` did not hold the lock.
 293     fn rwlock_reader_unlock(&mut self, id: RwLockId, reader: ThreadId) -> bool {
 294         let this = self.eval_context_mut();
 295         match this.machine.threads.sync.rwlocks[id].readers.entry(reader) {
 296             Entry::Occupied(mut entry) => {
 297                 let count = entry.get_mut();
 298                 assert!(*count > 0, "rwlock locked with count == 0");
 299                 *count -= 1;
 300                 if *count == 0 {
 301                     trace!("rwlock_reader_unlock: {:?} no longer held by {:?}", id, reader);
 302                     entry.remove();
 303                 } else {
 304                     trace!("rwlock_reader_unlock: {:?} held one less time by {:?}", id, reader);
 305                 }
 306             }
 307             Entry::Vacant(_) => return false, // we did not even own this lock
 308         }
 309         // The thread was a reader. If the lock is not held any more, give it to a writer.
 310         if this.rwlock_is_locked(id).not() {
 311             this.rwlock_dequeue_and_lock_writer(id);
 312         }
 313         true
 314     }
 315
 316     #[inline]
 317     /// Put the reader in the queue waiting for the lock and block it.
 318     fn rwlock_enqueue_and_block_reader(
 319         &mut self,
 320         id: RwLockId,
 321         reader: ThreadId,
 322     ) {
 323         let this = self.eval_context_mut();
 324         assert!(this.rwlock_is_write_locked(id), "read-queueing on not write locked rwlock");
 325         this.machine.threads.sync.rwlocks[id].reader_queue.push_back(reader);
 326         this.block_thread(reader);
 327     }
 328
 329     #[inline]
 330     /// Lock by setting the writer that owns the lock.
 331     fn rwlock_writer_lock(&mut self, id: RwLockId, writer: ThreadId) {
 332         let this = self.eval_context_mut();
 333         assert!(!this.rwlock_is_locked(id), "the rwlock is already locked");
 334         trace!("rwlock_writer_lock: {:?} now held by {:?}", id, writer);
 335         this.machine.threads.sync.rwlocks[id].writer = Some(writer);
 336     }
 337
 338     #[inline]
 339     /// Try to unlock by removing the writer.
 340     fn rwlock_writer_unlock(&mut self, id: RwLockId, expected_writer: ThreadId) -> bool {
 341         let this = self.eval_context_mut();
 342         let rwlock = &mut this.machine.threads.sync.rwlocks[id];
 343         if let Some(current_writer) = rwlock.writer {
 344             if current_writer != expected_writer {
 345                 // Only the owner can unlock the rwlock.
 346                 return false;
 347             }
 348             rwlock.writer = None;
 349             trace!("rwlock_writer_unlock: {:?} unlocked by {:?}", id, expected_writer);
 350             // The thread was a writer.
 351             //
 352             // We are prioritizing writers here against the readers. As a
 353             // result, not only readers can starve writers, but also writers can
 354             // starve readers.
 355             if this.rwlock_dequeue_and_lock_writer(id) {
 356                 // Someone got the write lock, nice.
 357             } else {
 358                 // Give the lock to all readers.
 359                 while this.rwlock_dequeue_and_lock_reader(id) {
 360                     // Rinse and repeat.
 361                 }
 362             }
 363             true
 364         } else {
 365             false
 366         }
 367     }
 368
 369     #[inline]
 370     /// Put the writer in the queue waiting for the lock.
 371     fn rwlock_enqueue_and_block_writer(
 372         &mut self,
 373         id: RwLockId,
 374         writer: ThreadId,
 375     ) {
 376         let this = self.eval_context_mut();
 377         assert!(this.rwlock_is_locked(id), "write-queueing on unlocked rwlock");
 378         this.machine.threads.sync.rwlocks[id].writer_queue.push_back(writer);
 379         this.block_thread(writer);
 380     }
 381
 382     #[inline]
 383     /// Create state for a new conditional variable.
 384     fn condvar_create(&mut self) -> CondvarId {
 385         let this = self.eval_context_mut();
 386         this.machine.threads.sync.condvars.push(Default::default())
 387     }
 388
 389     #[inline]
 390     /// Is the conditional variable awaited?
 391     fn condvar_is_awaited(&mut self, id: CondvarId) -> bool {
 392         let this = self.eval_context_mut();
 393         !this.machine.threads.sync.condvars[id].waiters.is_empty()
 394     }
 395
 396     /// Mark that the thread is waiting on the conditional variable.
 397     fn condvar_wait(&mut self, id: CondvarId, thread: ThreadId, mutex: MutexId) {
 398         let this = self.eval_context_mut();
 399         let waiters = &mut this.machine.threads.sync.condvars[id].waiters;
 400         assert!(waiters.iter().all(|waiter| waiter.thread != thread), "thread is already waiting");
 401         waiters.push_back(CondvarWaiter { thread, mutex });
 402     }
 403
 404     /// Wake up some thread (if there is any) sleeping on the conditional
 405     /// variable.
 406     fn condvar_signal(&mut self, id: CondvarId) -> Option<(ThreadId, MutexId)> {
 407         let this = self.eval_context_mut();
 408         this.machine.threads.sync.condvars[id]
 409             .waiters
 410             .pop_front()
 411             .map(|waiter| (waiter.thread, waiter.mutex))
 412     }
 413
 414     #[inline]
 415     /// Remove the thread from the queue of threads waiting on this conditional variable.
 416     fn condvar_remove_waiter(&mut self, id: CondvarId, thread: ThreadId) {
 417         let this = self.eval_context_mut();
 418         this.machine.threads.sync.condvars[id].waiters.retain(|waiter| waiter.thread != thread);
 419     }
 420
 421     fn futex_wait(&mut self, addr: Pointer<stacked_borrows::Tag>, thread: ThreadId) {
 422         let this = self.eval_context_mut();
 423         let waiters = &mut this.machine.threads.sync.futexes.entry(addr).or_default().waiters;
 424         assert!(waiters.iter().all(|waiter| waiter.thread != thread), "thread is already waiting");
 425         waiters.push_back(FutexWaiter { thread });
 426     }
 427
 428     fn futex_wake(&mut self, addr: Pointer<stacked_borrows::Tag>) -> Option<ThreadId> {
 429         let this = self.eval_context_mut();
 430         let waiters = &mut this.machine.threads.sync.futexes.get_mut(&addr)?.waiters;
 431         waiters.pop_front().map(|waiter| waiter.thread)
 432     }
 433 }