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