1 //! Implements threads.
3 use std::cell::RefCell;
4 use std::collections::hash_map::Entry;
5 use std::convert::TryFrom;
6 use std::num::TryFromIntError;
7 use std::time::{Duration, Instant, SystemTime};
11 use rustc_data_structures::fx::FxHashMap;
12 use rustc_hir::def_id::DefId;
13 use rustc_index::vec::{Idx, IndexVec};
14 use rustc_middle::ty::{self, Instance};
16 use crate::sync::SynchronizationState;
19 #[derive(Clone, Copy, Debug, PartialEq, Eq)]
20 pub enum SchedulingAction {
21 /// Execute step on the active thread.
23 /// Execute a timeout callback.
24 ExecuteTimeoutCallback,
25 /// Execute destructors of the active thread.
31 /// Timeout callbacks can be created by synchronization primitives to tell the
32 /// scheduler that they should be called once some period of time passes.
33 type TimeoutCallback<'mir, 'tcx> =
34 Box<dyn FnOnce(&mut InterpCx<'mir, 'tcx, Evaluator<'mir, 'tcx>>) -> InterpResult<'tcx> + 'tcx>;
36 /// A thread identifier.
37 #[derive(Clone, Copy, Debug, PartialOrd, Ord, PartialEq, Eq, Hash)]
38 pub struct ThreadId(u32);
40 /// The main thread. When it terminates, the whole application terminates.
41 const MAIN_THREAD: ThreadId = ThreadId(0);
44 pub fn to_u32(self) -> u32 {
49 impl Idx for ThreadId {
50 fn new(idx: usize) -> Self {
51 ThreadId(u32::try_from(idx).unwrap())
54 fn index(self) -> usize {
55 usize::try_from(self.0).unwrap()
59 impl TryFrom<u64> for ThreadId {
60 type Error = TryFromIntError;
61 fn try_from(id: u64) -> Result<Self, Self::Error> {
62 u32::try_from(id).map(|id_u32| Self(id_u32))
66 impl From<u32> for ThreadId {
67 fn from(id: u32) -> Self {
73 pub fn to_u32_scalar<'tcx>(&self) -> Scalar<Tag> {
74 Scalar::from_u32(u32::try_from(self.0).unwrap())
78 /// The state of a thread.
79 #[derive(Debug, Copy, Clone, PartialEq, Eq)]
80 pub enum ThreadState {
81 /// The thread is enabled and can be executed.
83 /// The thread tried to join the specified thread and is blocked until that
84 /// thread terminates.
85 BlockedOnJoin(ThreadId),
86 /// The thread is blocked on some synchronization primitive. It is the
87 /// responsibility of the synchronization primitives to track threads that
88 /// are blocked by them.
90 /// The thread has terminated its execution. We do not delete terminated
91 /// threads (FIXME: why?).
95 /// The join status of a thread.
96 #[derive(Debug, Copy, Clone, PartialEq, Eq)]
97 enum ThreadJoinStatus {
98 /// The thread can be joined.
100 /// A thread is detached if its join handle was destroyed and no other
101 /// thread can join it.
103 /// The thread was already joined by some thread and cannot be joined again.
108 pub struct Thread<'mir, 'tcx> {
110 /// Name of the thread.
111 thread_name: Option<Vec<u8>>,
112 /// The virtual call stack.
113 stack: Vec<Frame<'mir, 'tcx, Tag, FrameData<'tcx>>>,
115 join_status: ThreadJoinStatus,
118 impl<'mir, 'tcx> Thread<'mir, 'tcx> {
119 /// Check if the thread is done executing (no more stack frames). If yes,
120 /// change the state to terminated and return `true`.
121 fn check_terminated(&mut self) -> bool {
122 if self.state == ThreadState::Enabled {
123 if self.stack.is_empty() {
124 self.state = ThreadState::Terminated;
131 /// Get the name of the current thread, or `<unnamed>` if it was not set.
132 fn thread_name(&self) -> &[u8] {
133 if let Some(ref thread_name) = self.thread_name {
141 impl<'mir, 'tcx> std::fmt::Debug for Thread<'mir, 'tcx> {
142 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
143 write!(f, "{}({:?}, {:?})", String::from_utf8_lossy(self.thread_name()), self.state, self.join_status)
147 impl<'mir, 'tcx> Default for Thread<'mir, 'tcx> {
148 fn default() -> Self {
150 state: ThreadState::Enabled,
153 join_status: ThreadJoinStatus::Joinable,
158 /// A specific moment in time.
162 RealTime(SystemTime),
166 /// How long do we have to wait from now until the specified time?
167 fn get_wait_time(&self) -> Duration {
169 Time::Monotonic(instant) => instant.saturating_duration_since(Instant::now()),
170 Time::RealTime(time) =>
171 time.duration_since(SystemTime::now()).unwrap_or(Duration::new(0, 0)),
176 /// Callbacks are used to implement timeouts. For example, waiting on a
177 /// conditional variable with a timeout creates a callback that is called after
178 /// the specified time and unblocks the thread. If another thread signals on the
179 /// conditional variable, the signal handler deletes the callback.
180 struct TimeoutCallbackInfo<'mir, 'tcx> {
181 /// The callback should be called no earlier than this time.
183 /// The called function.
184 callback: TimeoutCallback<'mir, 'tcx>,
187 impl<'mir, 'tcx> std::fmt::Debug for TimeoutCallbackInfo<'mir, 'tcx> {
188 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
189 write!(f, "TimeoutCallback({:?})", self.call_time)
193 /// A set of threads.
195 pub struct ThreadManager<'mir, 'tcx> {
196 /// Identifier of the currently active thread.
197 active_thread: ThreadId,
198 /// Threads used in the program.
200 /// Note that this vector also contains terminated threads.
201 threads: IndexVec<ThreadId, Thread<'mir, 'tcx>>,
202 /// This field is pub(crate) because the synchronization primitives
203 /// (`crate::sync`) need a way to access it.
204 pub(crate) sync: SynchronizationState,
205 /// A mapping from a thread-local static to an allocation id of a thread
206 /// specific allocation.
207 thread_local_alloc_ids: RefCell<FxHashMap<(DefId, ThreadId), AllocId>>,
208 /// A flag that indicates that we should change the active thread.
209 yield_active_thread: bool,
210 /// Callbacks that are called once the specified time passes.
211 timeout_callbacks: FxHashMap<ThreadId, TimeoutCallbackInfo<'mir, 'tcx>>,
214 impl<'mir, 'tcx> Default for ThreadManager<'mir, 'tcx> {
215 fn default() -> Self {
216 let mut threads = IndexVec::new();
217 // Create the main thread and add it to the list of threads.
218 let mut main_thread = Thread::default();
219 // The main thread can *not* be joined on.
220 main_thread.join_status = ThreadJoinStatus::Detached;
221 threads.push(main_thread);
223 active_thread: ThreadId::new(0),
225 sync: SynchronizationState::default(),
226 thread_local_alloc_ids: Default::default(),
227 yield_active_thread: false,
228 timeout_callbacks: FxHashMap::default(),
233 impl<'mir, 'tcx: 'mir> ThreadManager<'mir, 'tcx> {
234 /// Check if we have an allocation for the given thread local static for the
236 fn get_thread_local_alloc_id(&self, def_id: DefId) -> Option<AllocId> {
237 self.thread_local_alloc_ids.borrow().get(&(def_id, self.active_thread)).cloned()
240 /// Set the allocation id as the allocation id of the given thread local
241 /// static for the active thread.
243 /// Panics if a thread local is initialized twice for the same thread.
244 fn set_thread_local_alloc_id(&self, def_id: DefId, new_alloc_id: AllocId) {
245 self.thread_local_alloc_ids
247 .insert((def_id, self.active_thread), new_alloc_id)
251 /// Borrow the stack of the active thread.
252 fn active_thread_stack(&self) -> &[Frame<'mir, 'tcx, Tag, FrameData<'tcx>>] {
253 &self.threads[self.active_thread].stack
256 /// Mutably borrow the stack of the active thread.
257 fn active_thread_stack_mut(&mut self) -> &mut Vec<Frame<'mir, 'tcx, Tag, FrameData<'tcx>>> {
258 &mut self.threads[self.active_thread].stack
261 /// Create a new thread and returns its id.
262 fn create_thread(&mut self) -> ThreadId {
263 let new_thread_id = ThreadId::new(self.threads.len());
264 self.threads.push(Default::default());
268 /// Set an active thread and return the id of the thread that was active before.
269 fn set_active_thread_id(&mut self, id: ThreadId) -> ThreadId {
270 let active_thread_id = self.active_thread;
271 self.active_thread = id;
272 assert!(self.active_thread.index() < self.threads.len());
276 /// Get the id of the currently active thread.
277 fn get_active_thread_id(&self) -> ThreadId {
281 /// Get the total number of threads that were ever spawn by this program.
282 fn get_total_thread_count(&self) -> usize {
286 /// Has the given thread terminated?
287 fn has_terminated(&self, thread_id: ThreadId) -> bool {
288 self.threads[thread_id].state == ThreadState::Terminated
291 /// Enable the thread for execution. The thread must be terminated.
292 fn enable_thread(&mut self, thread_id: ThreadId) {
293 assert!(self.has_terminated(thread_id));
294 self.threads[thread_id].state = ThreadState::Enabled;
297 /// Get a mutable borrow of the currently active thread.
298 fn active_thread_mut(&mut self) -> &mut Thread<'mir, 'tcx> {
299 &mut self.threads[self.active_thread]
302 /// Get a shared borrow of the currently active thread.
303 fn active_thread_ref(&self) -> &Thread<'mir, 'tcx> {
304 &self.threads[self.active_thread]
307 /// Mark the thread as detached, which means that no other thread will try
308 /// to join it and the thread is responsible for cleaning up.
309 fn detach_thread(&mut self, id: ThreadId) -> InterpResult<'tcx> {
310 if self.threads[id].join_status != ThreadJoinStatus::Joinable {
311 throw_ub_format!("trying to detach thread that was already detached or joined");
313 self.threads[id].join_status = ThreadJoinStatus::Detached;
317 /// Mark that the active thread tries to join the thread with `joined_thread_id`.
318 fn join_thread(&mut self, joined_thread_id: ThreadId) -> InterpResult<'tcx> {
319 if self.threads[joined_thread_id].join_status != ThreadJoinStatus::Joinable {
320 throw_ub_format!("trying to join a detached or already joined thread");
322 if joined_thread_id == self.active_thread {
323 throw_ub_format!("trying to join itself");
328 .all(|thread| thread.state != ThreadState::BlockedOnJoin(joined_thread_id)),
329 "a joinable thread already has threads waiting for its termination"
331 // Mark the joined thread as being joined so that we detect if other
332 // threads try to join it.
333 self.threads[joined_thread_id].join_status = ThreadJoinStatus::Joined;
334 if self.threads[joined_thread_id].state != ThreadState::Terminated {
335 // The joined thread is still running, we need to wait for it.
336 self.active_thread_mut().state = ThreadState::BlockedOnJoin(joined_thread_id);
338 "{:?} blocked on {:?} when trying to join",
346 /// Set the name of the active thread.
347 fn set_thread_name(&mut self, new_thread_name: Vec<u8>) {
348 self.active_thread_mut().thread_name = Some(new_thread_name);
351 /// Get the name of the active thread.
352 fn get_thread_name(&self) -> &[u8] {
353 self.active_thread_ref().thread_name()
356 /// Put the thread into the blocked state.
357 fn block_thread(&mut self, thread: ThreadId) {
358 let state = &mut self.threads[thread].state;
359 assert_eq!(*state, ThreadState::Enabled);
360 *state = ThreadState::BlockedOnSync;
363 /// Put the blocked thread into the enabled state.
364 fn unblock_thread(&mut self, thread: ThreadId) {
365 let state = &mut self.threads[thread].state;
366 assert_eq!(*state, ThreadState::BlockedOnSync);
367 *state = ThreadState::Enabled;
370 /// Change the active thread to some enabled thread.
371 fn yield_active_thread(&mut self) {
372 // We do not yield immediately, as swapping out the current stack while executing a MIR statement
373 // could lead to all sorts of confusion.
374 // We should only switch stacks between steps.
375 self.yield_active_thread = true;
378 /// Register the given `callback` to be called once the `call_time` passes.
380 /// The callback will be called with `thread` being the active thread, and
381 /// the callback may not change the active thread.
382 fn register_timeout_callback(
386 callback: TimeoutCallback<'mir, 'tcx>,
388 self.timeout_callbacks
389 .insert(thread, TimeoutCallbackInfo { call_time, callback })
393 /// Unregister the callback for the `thread`.
394 fn unregister_timeout_callback_if_exists(&mut self, thread: ThreadId) {
395 self.timeout_callbacks.remove(&thread);
398 /// Get a callback that is ready to be called.
399 fn get_ready_callback(&mut self) -> Option<(ThreadId, TimeoutCallback<'mir, 'tcx>)> {
400 // We iterate over all threads in the order of their indices because
401 // this allows us to have a deterministic scheduler.
402 for thread in self.threads.indices() {
403 match self.timeout_callbacks.entry(thread) {
404 Entry::Occupied(entry) =>
405 if entry.get().call_time.get_wait_time() == Duration::new(0, 0) {
406 return Some((thread, entry.remove().callback));
408 Entry::Vacant(_) => {}
414 /// Decide which action to take next and on which thread.
416 /// The currently implemented scheduling policy is the one that is commonly
417 /// used in stateless model checkers such as Loom: run the active thread as
418 /// long as we can and switch only when we have to (the active thread was
419 /// blocked, terminated, or has explicitly asked to be preempted).
420 fn schedule(&mut self) -> InterpResult<'tcx, SchedulingAction> {
421 // Check whether the thread has **just** terminated (`check_terminated`
422 // checks whether the thread has popped all its stack and if yes, sets
423 // the thread state to terminated).
424 if self.threads[self.active_thread].check_terminated() {
425 // Check if we need to unblock any threads.
426 for (i, thread) in self.threads.iter_enumerated_mut() {
427 if thread.state == ThreadState::BlockedOnJoin(self.active_thread) {
428 trace!("unblocking {:?} because {:?} terminated", i, self.active_thread);
429 thread.state = ThreadState::Enabled;
432 return Ok(SchedulingAction::ExecuteDtors);
434 if self.threads[MAIN_THREAD].state == ThreadState::Terminated {
435 // The main thread terminated; stop the program.
436 if self.threads.iter().any(|thread| thread.state != ThreadState::Terminated) {
437 // FIXME: This check should be either configurable or just emit
438 // a warning. For example, it seems normal for a program to
439 // terminate without waiting for its detached threads to
440 // terminate. However, this case is not trivial to support
441 // because we also probably do not want to consider the memory
442 // owned by these threads as leaked.
443 throw_unsup_format!("the main thread terminated without waiting for other threads");
445 return Ok(SchedulingAction::Stop);
447 // At least for `pthread_cond_timedwait` we need to report timeout when
448 // the function is called already after the specified time even if a
449 // signal is received before the thread gets scheduled. Therefore, we
450 // need to schedule all timeout callbacks before we continue regular
454 // https://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_cond_timedwait.html#
455 let potential_sleep_time =
456 self.timeout_callbacks.values().map(|info| info.call_time.get_wait_time()).min();
457 if potential_sleep_time == Some(Duration::new(0, 0)) {
458 return Ok(SchedulingAction::ExecuteTimeoutCallback);
460 // No callbacks scheduled, pick a regular thread to execute.
461 if self.threads[self.active_thread].state == ThreadState::Enabled
462 && !self.yield_active_thread
464 // The currently active thread is still enabled, just continue with it.
465 return Ok(SchedulingAction::ExecuteStep);
467 // We need to pick a new thread for execution.
468 for (id, thread) in self.threads.iter_enumerated() {
469 if thread.state == ThreadState::Enabled {
470 if !self.yield_active_thread || id != self.active_thread {
471 self.active_thread = id;
476 self.yield_active_thread = false;
477 if self.threads[self.active_thread].state == ThreadState::Enabled {
478 return Ok(SchedulingAction::ExecuteStep);
480 // We have not found a thread to execute.
481 if self.threads.iter().all(|thread| thread.state == ThreadState::Terminated) {
482 unreachable!("all threads terminated without the main thread terminating?!");
483 } else if let Some(sleep_time) = potential_sleep_time {
484 // All threads are currently blocked, but we have unexecuted
485 // timeout_callbacks, which may unblock some of the threads. Hence,
486 // sleep until the first callback.
487 std::thread::sleep(sleep_time);
488 Ok(SchedulingAction::ExecuteTimeoutCallback)
490 throw_machine_stop!(TerminationInfo::Deadlock);
495 // Public interface to thread management.
496 impl<'mir, 'tcx: 'mir> EvalContextExt<'mir, 'tcx> for crate::MiriEvalContext<'mir, 'tcx> {}
497 pub trait EvalContextExt<'mir, 'tcx: 'mir>: crate::MiriEvalContextExt<'mir, 'tcx> {
498 /// Get a thread-specific allocation id for the given thread-local static.
499 /// If needed, allocate a new one.
501 /// FIXME: This method should be replaced as soon as
502 /// https://github.com/rust-lang/rust/issues/70685 gets fixed.
503 fn get_or_create_thread_local_alloc_id(&self, def_id: DefId) -> InterpResult<'tcx, AllocId> {
504 let this = self.eval_context_ref();
506 if let Some(new_alloc_id) = this.machine.threads.get_thread_local_alloc_id(def_id) {
507 // We already have a thread-specific allocation id for this
508 // thread-local static.
511 // We need to allocate a thread-specific allocation id for this
512 // thread-local static.
514 // At first, we invoke the `const_eval_raw` query and extract the
515 // allocation from it. Unfortunately, we have to duplicate the code
516 // from `Memory::get_global_alloc` that does this.
518 // Then we store the retrieved allocation back into the `alloc_map`
519 // to get a fresh allocation id, which we can use as a
520 // thread-specific allocation id for the thread-local static.
521 if tcx.is_foreign_item(def_id) {
522 throw_unsup_format!("foreign thread-local statics are not supported");
524 // Invoke the `const_eval_raw` query.
525 let instance = Instance::mono(tcx.tcx, def_id);
526 let gid = GlobalId { instance, promoted: None };
528 tcx.const_eval_raw(ty::ParamEnv::reveal_all().and(gid)).map_err(|err| {
529 // no need to report anything, the const_eval call takes care of that
531 assert!(tcx.is_static(def_id));
534 let id = raw_const.alloc_id;
535 // Extract the allocation from the query result.
536 let allocation = tcx.global_alloc(id).unwrap_memory();
537 // Create a new allocation id for the same allocation in this hacky
538 // way. Internally, `alloc_map` deduplicates allocations, but this
539 // is fine because Miri will make a copy before a first mutable
541 let new_alloc_id = tcx.create_memory_alloc(allocation);
542 this.machine.threads.set_thread_local_alloc_id(def_id, new_alloc_id);
548 fn create_thread(&mut self) -> ThreadId {
549 let this = self.eval_context_mut();
550 this.machine.threads.create_thread()
554 fn detach_thread(&mut self, thread_id: ThreadId) -> InterpResult<'tcx> {
555 let this = self.eval_context_mut();
556 this.machine.threads.detach_thread(thread_id)
560 fn join_thread(&mut self, joined_thread_id: ThreadId) -> InterpResult<'tcx> {
561 let this = self.eval_context_mut();
562 this.machine.threads.join_thread(joined_thread_id)
566 fn set_active_thread(&mut self, thread_id: ThreadId) -> ThreadId {
567 let this = self.eval_context_mut();
568 this.machine.threads.set_active_thread_id(thread_id)
572 fn get_active_thread(&self) -> ThreadId {
573 let this = self.eval_context_ref();
574 this.machine.threads.get_active_thread_id()
578 fn get_total_thread_count(&self) -> usize {
579 let this = self.eval_context_ref();
580 this.machine.threads.get_total_thread_count()
584 fn has_terminated(&self, thread_id: ThreadId) -> bool {
585 let this = self.eval_context_ref();
586 this.machine.threads.has_terminated(thread_id)
590 fn enable_thread(&mut self, thread_id: ThreadId) {
591 let this = self.eval_context_mut();
592 this.machine.threads.enable_thread(thread_id);
596 fn active_thread_stack(&self) -> &[Frame<'mir, 'tcx, Tag, FrameData<'tcx>>] {
597 let this = self.eval_context_ref();
598 this.machine.threads.active_thread_stack()
602 fn active_thread_stack_mut(&mut self) -> &mut Vec<Frame<'mir, 'tcx, Tag, FrameData<'tcx>>> {
603 let this = self.eval_context_mut();
604 this.machine.threads.active_thread_stack_mut()
608 fn set_active_thread_name(&mut self, new_thread_name: Vec<u8>) {
609 let this = self.eval_context_mut();
610 this.machine.threads.set_thread_name(new_thread_name);
614 fn get_active_thread_name<'c>(&'c self) -> &'c [u8]
618 let this = self.eval_context_ref();
619 this.machine.threads.get_thread_name()
623 fn block_thread(&mut self, thread: ThreadId) {
624 let this = self.eval_context_mut();
625 this.machine.threads.block_thread(thread);
629 fn unblock_thread(&mut self, thread: ThreadId) {
630 let this = self.eval_context_mut();
631 this.machine.threads.unblock_thread(thread);
635 fn yield_active_thread(&mut self) {
636 let this = self.eval_context_mut();
637 this.machine.threads.yield_active_thread();
641 fn register_timeout_callback(
645 callback: TimeoutCallback<'mir, 'tcx>,
647 let this = self.eval_context_mut();
648 this.machine.threads.register_timeout_callback(thread, call_time, callback);
652 fn unregister_timeout_callback_if_exists(&mut self, thread: ThreadId) {
653 let this = self.eval_context_mut();
654 this.machine.threads.unregister_timeout_callback_if_exists(thread);
657 /// Execute a timeout callback on the callback's thread.
659 fn run_timeout_callback(&mut self) -> InterpResult<'tcx> {
660 let this = self.eval_context_mut();
661 let (thread, callback) =
662 this.machine.threads.get_ready_callback().expect("no callback found");
663 // This back-and-forth with `set_active_thread` is here because of two
665 // 1. Make the caller and not the callback responsible for changing
667 // 2. Make the scheduler the only place that can change the active
669 let old_thread = this.set_active_thread(thread);
671 this.set_active_thread(old_thread);
675 /// Decide which action to take next and on which thread.
677 fn schedule(&mut self) -> InterpResult<'tcx, SchedulingAction> {
678 let this = self.eval_context_mut();
679 this.machine.threads.schedule()