tor_rtmock/task.rs
1//! Executor for running tests with mocked environment
2//!
3//! See [`MockExecutor`]
4
5use std::any::Any;
6use std::cell::Cell;
7use std::collections::VecDeque;
8use std::fmt::{self, Debug, Display};
9use std::future::Future;
10use std::io::{self, Write as _};
11use std::iter;
12use std::panic::{AssertUnwindSafe, catch_unwind, panic_any};
13use std::pin::{Pin, pin};
14use std::sync::{Arc, Mutex, MutexGuard, Weak};
15use std::task::{Context, Poll, RawWaker, RawWakerVTable, Waker};
16
17use futures::FutureExt as _;
18use futures::pin_mut;
19use futures::task::{FutureObj, Spawn, SpawnError};
20
21use assert_matches::assert_matches;
22use educe::Educe;
23use itertools::Either::{self, *};
24use itertools::{chain, izip};
25use slotmap_careful::DenseSlotMap;
26use std::backtrace::Backtrace;
27use strum::EnumIter;
28
29// NB: when using traced_test, the trace! and error! output here is generally suppressed
30// in tests of other crates. To see it, you can write something like this
31// (in the dev-dependencies of the crate whose tests you're running):
32// tracing-test = { version = "0.2.4", features = ["no-env-filter"] }
33use tracing::{error, trace};
34
35use oneshot_fused_workaround::{self as oneshot, Canceled};
36use tor_error::error_report;
37use tor_rtcompat::join_set::FuturesJoinSet;
38use tor_rtcompat::{Blocking, JoinSetProvider, ToplevelBlockOn};
39
40use Poll::*;
41use TaskState::*;
42
43/// Type-erased future, one for each of our (normal) tasks
44type TaskFuture = FutureObj<'static, ()>;
45
46/// Future for the argument to `block_on`, which is handled specially
47type MainFuture<'m> = Pin<&'m mut dyn Future<Output = ()>>;
48
49//---------- principal data structures ----------
50
51/// Executor for running tests with mocked environment
52///
53/// For test cases which don't actually wait for anything in the real world.
54///
55/// This is the executor.
56/// It implements [`Spawn`] and [`ToplevelBlockOn`]
57///
58/// It will usually be used as part of a `MockRuntime`.
59///
60/// To run futures, call [`ToplevelBlockOn::block_on`]
61///
62/// # Restricted environment
63///
64/// Tests run with this executor must not attempt to block
65/// on anything "outside":
66/// every future that anything awaits must (eventually) be woken directly
67/// *by some other task* in the same test case.
68///
69/// (By directly we mean that the [`Waker::wake`] call is made
70/// by that waking future, before that future itself awaits anything.)
71///
72/// # Panics
73///
74/// The executor will panic
75/// if the toplevel future (passed to `block_on`)
76/// doesn't complete (without externally blocking),
77/// but instead waits for something.
78///
79/// The executor will malfunction or panic if reentered.
80/// (Eg, if `block_on` is reentered.)
81#[derive(Clone, Default, Educe)]
82#[educe(Debug)]
83pub struct MockExecutor {
84 /// Mutable state
85 #[educe(Debug(ignore))]
86 shared: Arc<Shared>,
87}
88
89/// Shared state and ancillary information
90///
91/// This is always within an `Arc`.
92#[derive(Default)]
93struct Shared {
94 /// Shared state
95 data: Mutex<Data>,
96 /// Condition variable for thread scheduling
97 ///
98 /// Signaled when [`Data.thread_to_run`](struct.Data.html#structfield.thread_to_run)
99 /// is modified.
100 thread_condvar: std::sync::Condvar,
101}
102
103/// Task id, module to hide `Ti` alias
104mod task_id {
105 slotmap_careful::new_key_type! {
106 /// Task ID, usually called `TaskId`
107 ///
108 /// Short name in special `task_id` module so that [`Debug`] is nice
109 pub(super) struct Ti;
110 }
111}
112use task_id::Ti as TaskId;
113
114/// Executor's state
115///
116/// ### Task state machine
117///
118/// A task is created in `tasks`, `Awake`, so also in `awake`.
119///
120/// When we poll it, we take it out of `awake` and set it to `Asleep`,
121/// and then call `poll()`.
122/// Any time after that, it can be made `Awake` again (and put back onto `awake`)
123/// by the waker ([`ActualWaker`], wrapped in [`Waker`]).
124///
125/// The task's future is of course also present here in this data structure.
126/// However, during poll we must release the lock,
127/// so we cannot borrow the future from `Data`.
128/// Instead, we move it out. So `Task.fut` is an `Option`.
129///
130/// ### "Main" task - the argument to `block_on`
131///
132/// The signature of `BlockOn::block_on` accepts a non-`'static` future
133/// (and a non-`Send`/`Sync` one).
134///
135/// So we cannot store that future in `Data` because `Data` is `'static`.
136/// Instead, this main task future is passed as an argument down the call stack.
137/// In the data structure we simply store a placeholder, `TaskFutureInfo::Main`.
138#[derive(Educe, derive_more::Debug)]
139#[educe(Default)]
140struct Data {
141 /// Tasks
142 ///
143 /// Includes tasks spawned with `spawn`,
144 /// and also the future passed to `block_on`.
145 #[debug("{:?}", DebugTasks(self, || tasks.keys()))]
146 tasks: DenseSlotMap<TaskId, Task>,
147
148 /// `awake` lists precisely: tasks that are `Awake`, plus maybe stale `TaskId`s
149 ///
150 /// Tasks are pushed onto the *back* when woken,
151 /// so back is the most recently woken.
152 #[debug("{:?}", DebugTasks(self, || awake.iter().cloned()))]
153 awake: VecDeque<TaskId>,
154
155 /// If a future from `progress_until_stalled` exists
156 progressing_until_stalled: Option<ProgressingUntilStalled>,
157
158 /// Scheduling policy
159 scheduling: SchedulingPolicy,
160
161 /// (Sub)thread we want to run now
162 ///
163 /// At any one time only one thread is meant to be running.
164 /// Other threads are blocked in condvar wait, waiting for this to change.
165 ///
166 /// **Modified only** within
167 /// [`thread_context_switch_send_instruction_to_run`](Shared::thread_context_switch_send_instruction_to_run),
168 /// which takes responsibility for preserving the following **invariants**:
169 ///
170 /// 1. no-one but the named thread is allowed to modify this field.
171 /// 2. after modifying this field, signal `thread_condvar`
172 #[educe(Default(expression = "ThreadDescriptor::Executor"))]
173 thread_to_run: ThreadDescriptor,
174}
175
176/// How we should schedule?
177#[derive(Debug, Clone, Default, EnumIter)]
178#[non_exhaustive]
179pub enum SchedulingPolicy {
180 /// Task *most* recently woken is run
181 ///
182 /// This is the default.
183 ///
184 /// It will expose starvation bugs if a task never sleeps.
185 /// (Which is a good thing in tests.)
186 #[default]
187 Stack,
188 /// Task *least* recently woken is run.
189 Queue,
190}
191
192/// Record of a single task
193///
194/// Tracks a spawned task, or the main task (the argument to `block_on`).
195///
196/// Stored in [`Data`]`.tasks`.
197struct Task {
198 /// For debugging output
199 desc: String,
200 /// Has this been woken via a waker? (And is it in `Data.awake`?)
201 ///
202 /// **Set to `Awake` only by [`Task::set_awake`]**,
203 /// preserving the invariant that
204 /// every `Awake` task is in [`Data.awake`](struct.Data.html#structfield.awake).
205 state: TaskState,
206 /// The actual future (or a placeholder for it)
207 ///
208 /// May be `None` briefly in the executor main loop, because we've
209 /// temporarily moved it out so we can poll it,
210 /// or if this is a Subthread task which is currently running sync code
211 /// (in which case we're blocked in the executor waiting to be
212 /// woken up by [`thread_context_switch`](Shared::thread_context_switch).
213 ///
214 /// Note that the `None` can be observed outside the main loop, because
215 /// the main loop unlocks while it polls, so other (non-main-loop) code
216 /// might see it.
217 fut: Option<TaskFutureInfo>,
218}
219
220/// A future as stored in our record of a [`Task`]
221#[derive(Educe)]
222#[educe(Debug)]
223enum TaskFutureInfo {
224 /// The [`Future`]. All is normal.
225 Normal(#[educe(Debug(ignore))] TaskFuture),
226 /// The future isn't here because this task is the main future for `block_on`
227 Main,
228 /// This task is actually a [`Subthread`](MockExecutor::subthread_spawn)
229 ///
230 /// Instead of polling it, we'll switch to it with
231 /// [`thread_context_switch`](Shared::thread_context_switch).
232 Subthread,
233}
234
235/// State of a task - do we think it needs to be polled?
236///
237/// Stored in [`Task`]`.state`.
238#[derive(Debug)]
239enum TaskState {
240 /// Awake - needs to be polled
241 ///
242 /// Established by [`waker.wake()`](Waker::wake)
243 Awake,
244 /// Asleep - does *not* need to be polled
245 ///
246 /// Established each time just before we call the future's [`poll`](Future::poll)
247 Asleep(Vec<SleepLocation>),
248}
249
250/// Actual implementor of `Wake` for use in a `Waker`
251///
252/// Futures (eg, channels from [`futures`]) will use this to wake a task
253/// when it should be polled.
254///
255/// This type must not be `Cloned` with the `Data` lock held.
256/// Consequently, a `Waker` mustn't either.
257struct ActualWaker {
258 /// Executor state
259 ///
260 /// The Waker mustn't to hold a strong reference to the executor,
261 /// since typically a task holds a future that holds a Waker,
262 /// and the executor holds the task - so that would be a cycle.
263 data: Weak<Shared>,
264
265 /// Which task this is
266 id: TaskId,
267}
268
269/// State used for an in-progress call to
270/// [`progress_until_stalled`][`MockExecutor::progress_until_stalled`]
271///
272/// If present in [`Data`], an (async) call to `progress_until_stalled`
273/// is in progress.
274///
275/// The future from `progress_until_stalled`, [`ProgressUntilStalledFuture`]
276/// is a normal-ish future.
277/// It can be polled in the normal way.
278/// When it is polled, it looks here, in `finished`, to see if it's `Ready`.
279///
280/// The future is made ready, and woken (via `waker`),
281/// by bespoke code in the task executor loop.
282///
283/// When `ProgressUntilStalledFuture` (maybe completes and) is dropped,
284/// its `Drop` impl is used to remove this from `Data.progressing_until_stalled`.
285#[derive(Debug)]
286struct ProgressingUntilStalled {
287 /// Have we, in fact, stalled?
288 ///
289 /// Made `Ready` by special code in the executor loop
290 finished: Poll<()>,
291
292 /// Waker
293 ///
294 /// Signalled by special code in the executor loop
295 waker: Option<Waker>,
296}
297
298/// Future from
299/// [`progress_until_stalled`][`MockExecutor::progress_until_stalled`]
300///
301/// See [`ProgressingUntilStalled`] for an overview of this aspect of the contraption.
302///
303/// Existence of this struct implies `Data.progressing_until_stalled` is `Some`.
304/// There can only be one at a time.
305#[derive(Educe)]
306#[educe(Debug)]
307struct ProgressUntilStalledFuture {
308 /// Executor's state; this future's state is in `.progressing_until_stalled`
309 #[educe(Debug(ignore))]
310 shared: Arc<Shared>,
311}
312
313/// Identifies a thread we know about - the executor thread, or a Subthread
314///
315/// Not related to `std::thread::ThreadId`.
316///
317/// See [`spawn_subthread`](MockExecutor::subthread_spawn) for definition of a Subthread.
318///
319/// This being a thread-local and not scoped by which `MockExecutor` we're talking about
320/// means that we can't cope if there are multiple `MockExecutor`s involved in the same thread.
321/// That's OK (and documented).
322#[derive(Copy, Clone, Eq, PartialEq, derive_more::Debug)]
323enum ThreadDescriptor {
324 /// Foreign - neither the (running) executor, nor a Subthread
325 #[debug("FOREIGN")]
326 Foreign,
327 /// The executor.
328 #[debug("Exe")]
329 Executor,
330 /// This task, which is a Subthread.
331 #[debug("{_0:?}")]
332 Subthread(TaskId),
333}
334
335/// Marker indicating that this task is a Subthread, not an async task.
336///
337/// See [`spawn_subthread`](MockExecutor::subthread_spawn) for definition of a Subthread.
338#[derive(Copy, Clone, Debug, Eq, PartialEq, Ord, PartialOrd)]
339struct IsSubthread;
340
341/// [`Shared::subthread_yield`] should set our task awake before switching to the executor
342#[derive(Copy, Clone, Debug, Eq, PartialEq, Ord, PartialOrd)]
343struct SetAwake;
344
345thread_local! {
346 /// Identifies this thread.
347 pub static THREAD_DESCRIPTOR: Cell<ThreadDescriptor> = const {
348 Cell::new(ThreadDescriptor::Foreign)
349 };
350}
351
352//---------- creation ----------
353
354impl MockExecutor {
355 /// Make a `MockExecutor` with default parameters
356 pub fn new() -> Self {
357 Self::default()
358 }
359
360 /// Make a `MockExecutor` with a specific `SchedulingPolicy`
361 pub fn with_scheduling(scheduling: SchedulingPolicy) -> Self {
362 Data {
363 scheduling,
364 ..Default::default()
365 }
366 .into()
367 }
368}
369
370impl From<Data> for MockExecutor {
371 fn from(data: Data) -> MockExecutor {
372 let shared = Shared {
373 data: Mutex::new(data),
374 thread_condvar: std::sync::Condvar::new(),
375 };
376 MockExecutor {
377 shared: Arc::new(shared),
378 }
379 }
380}
381
382//---------- spawning ----------
383
384impl MockExecutor {
385 /// Spawn a task and return something to identify it
386 ///
387 /// `desc` should `Display` as some kind of short string (ideally without spaces)
388 /// and will be used in the `Debug` impl and trace log messages from `MockExecutor`.
389 ///
390 /// The returned value is an opaque task identifier which is very cheap to clone
391 /// and which can be used by the caller in debug logging,
392 /// if it's desired to correlate with the debug output from `MockExecutor`.
393 /// Most callers will want to ignore it.
394 ///
395 /// This method is infallible. (The `MockExecutor` cannot be shut down.)
396 pub fn spawn_identified(
397 &self,
398 desc: impl Display,
399 fut: impl Future<Output = ()> + Send + 'static,
400 ) -> impl Debug + Clone + Send + 'static {
401 self.spawn_internal(desc.to_string(), FutureObj::from(Box::new(fut)))
402 }
403
404 /// Spawn a task and return its output for further usage
405 ///
406 /// `desc` should `Display` as some kind of short string (ideally without spaces)
407 /// and will be used in the `Debug` impl and trace log messages from `MockExecutor`.
408 pub fn spawn_join<T: Debug + Send + 'static>(
409 &self,
410 desc: impl Display,
411 fut: impl Future<Output = T> + Send + 'static,
412 ) -> impl Future<Output = T> {
413 let (tx, rx) = oneshot::channel();
414 self.spawn_identified(desc, async move {
415 let res = fut.await;
416 tx.send(res)
417 .expect("Failed to send future's output, did future panic?");
418 });
419 rx.map(|m| m.expect("Failed to receive future's output"))
420 }
421
422 /// Spawn a task and return its `TaskId`
423 ///
424 /// Convenience method for use by `spawn_identified` and `spawn_obj`.
425 /// The future passed to `block_on` is not handled here.
426 fn spawn_internal(&self, desc: String, fut: TaskFuture) -> TaskId {
427 let mut data = self.shared.lock();
428 data.insert_task(desc, TaskFutureInfo::Normal(fut))
429 }
430}
431
432impl Data {
433 /// Insert a task given its `TaskFutureInfo` and return its `TaskId`.
434 fn insert_task(&mut self, desc: String, fut: TaskFutureInfo) -> TaskId {
435 let state = Awake;
436 let id = self.tasks.insert(Task {
437 state,
438 desc,
439 fut: Some(fut),
440 });
441 self.awake.push_back(id);
442 trace!("MockExecutor spawned {:?}={:?}", id, self.tasks[id]);
443 id
444 }
445}
446
447impl Spawn for MockExecutor {
448 fn spawn_obj(&self, future: TaskFuture) -> Result<(), SpawnError> {
449 self.spawn_internal("spawn_obj".into(), future);
450 Ok(())
451 }
452}
453
454impl Blocking for MockExecutor {
455 type ThreadHandle<T: Send + 'static> = Pin<Box<dyn Future<Output = T>>>;
456
457 fn spawn_blocking<F, T>(&self, f: F) -> Self::ThreadHandle<T>
458 where
459 F: FnOnce() -> T + Send + 'static,
460 T: Send + 'static,
461 {
462 assert_matches!(
463 THREAD_DESCRIPTOR.get(),
464 ThreadDescriptor::Executor | ThreadDescriptor::Subthread(_),
465 "MockExecutor::spawn_blocking_io only allowed from future or subthread, being run by this executor"
466 );
467 Box::pin(
468 self.subthread_spawn("spawn_blocking", f)
469 .map(|x| x.expect("Error in spawn_blocking subthread.")),
470 )
471 }
472
473 fn reenter_block_on<F>(&self, future: F) -> F::Output
474 where
475 F: Future,
476 F::Output: Send + 'static,
477 {
478 self.subthread_block_on_future(future)
479 }
480}
481
482impl JoinSetProvider for MockExecutor {
483 type JoinSet<T: Send + Sync + 'static> = FuturesJoinSet<T, Self>;
484
485 fn new_join_set<T>(&self) -> Self::JoinSet<T>
486 where
487 T: Send + Sync + 'static,
488 {
489 FuturesJoinSet::new(self.clone())
490 }
491}
492
493//---------- block_on ----------
494
495impl ToplevelBlockOn for MockExecutor {
496 fn block_on<F>(&self, input_fut: F) -> F::Output
497 where
498 F: Future,
499 {
500 let mut value: Option<F::Output> = None;
501
502 // Box this just so that we can conveniently control precisely when it's dropped.
503 // (We could do this with Option and Pin::set but that seems clumsier.)
504 let mut input_fut = Box::pin(input_fut);
505
506 let run_store_fut = {
507 let value = &mut value;
508 let input_fut = &mut input_fut;
509 async {
510 trace!("MockExecutor block_on future...");
511 let t = input_fut.await;
512 trace!("MockExecutor block_on future returned...");
513 *value = Some(t);
514 trace!("MockExecutor block_on future exiting.");
515 }
516 };
517
518 {
519 pin_mut!(run_store_fut);
520
521 let main_id = self
522 .shared
523 .lock()
524 .insert_task("main".into(), TaskFutureInfo::Main);
525 trace!("MockExecutor {main_id:?} is task for block_on");
526 self.execute_to_completion(run_store_fut);
527 }
528
529 #[allow(clippy::let_and_return)] // clarity
530 let value = value.take().unwrap_or_else(|| {
531 // eprintln can be captured by libtest, but the debug_dump goes to io::stderr.
532 // use the latter, so that the debug dump is prefixed by this message.
533 let _: io::Result<()> = writeln!(io::stderr(), "all futures blocked, crashing...");
534 // write to tracing too, so the tracing log is clear about when we crashed
535 error!("all futures blocked, crashing...");
536
537 // Sequencing here is subtle.
538 //
539 // We should do the dump before dropping the input future, because the input
540 // future is likely to own things that, when dropped, wake up other tasks,
541 // rendering the dump inaccurate.
542 //
543 // But also, dropping the input future may well drop a ProgressUntilStalledFuture
544 // which then reenters us. More generally, we mustn't call user code
545 // with the lock held.
546 //
547 // And, we mustn't panic with the data lock held.
548 //
549 // If value was Some, then this closure is dropped without being called,
550 // which drops the future after it has yielded the value, which is correct.
551 {
552 let mut data = self.shared.lock();
553 data.debug_dump();
554 }
555 drop(input_fut);
556
557 panic!(
558 r"
559all futures blocked. waiting for the real world? or deadlocked (waiting for each other) ?
560"
561 );
562 });
563
564 value
565 }
566}
567
568//---------- execution - core implementation ----------
569
570impl MockExecutor {
571 /// Keep polling tasks until nothing more can be done
572 ///
573 /// Ie, stop when `awake` is empty and `progressing_until_stalled` is `None`.
574 fn execute_to_completion(&self, mut main_fut: MainFuture) {
575 trace!("MockExecutor execute_to_completion...");
576 loop {
577 self.execute_until_first_stall(main_fut.as_mut());
578
579 // Handle `progressing_until_stalled`
580 let pus_waker = {
581 let mut data = self.shared.lock();
582 let pus = &mut data.progressing_until_stalled;
583 trace!("MockExecutor execute_to_completion PUS={:?}", &pus);
584 let Some(pus) = pus else {
585 // No progressing_until_stalled, we're actually done.
586 break;
587 };
588 assert_eq!(
589 pus.finished, Pending,
590 "ProgressingUntilStalled finished twice?!"
591 );
592 pus.finished = Ready(());
593
594 // Release the lock temporarily so that ActualWaker::clone doesn't deadlock
595 let waker = pus
596 .waker
597 .take()
598 .expect("ProgressUntilStalledFuture not ever polled!");
599 drop(data);
600 let waker_copy = waker.clone();
601 let mut data = self.shared.lock();
602
603 let pus = &mut data.progressing_until_stalled;
604 if let Some(double) = pus
605 .as_mut()
606 .expect("progressing_until_stalled updated under our feet!")
607 .waker
608 .replace(waker)
609 {
610 panic!("double progressing_until_stalled.waker! {double:?}");
611 }
612
613 waker_copy
614 };
615 pus_waker.wake();
616 }
617 trace!("MockExecutor execute_to_completion done");
618 }
619
620 /// Keep polling tasks until `awake` is empty
621 ///
622 /// (Ignores `progressing_until_stalled` - so if one is active,
623 /// will return when all other tasks have blocked.)
624 ///
625 /// # Panics
626 ///
627 /// Might malfunction or panic if called reentrantly
628 fn execute_until_first_stall(&self, main_fut: MainFuture) {
629 trace!("MockExecutor execute_until_first_stall ...");
630
631 assert_eq!(
632 THREAD_DESCRIPTOR.get(),
633 ThreadDescriptor::Foreign,
634 "MockExecutor executor re-entered"
635 );
636 THREAD_DESCRIPTOR.set(ThreadDescriptor::Executor);
637
638 let r = catch_unwind(AssertUnwindSafe(|| self.executor_main_loop(main_fut)));
639
640 THREAD_DESCRIPTOR.set(ThreadDescriptor::Foreign);
641
642 match r {
643 Ok(()) => trace!("MockExecutor execute_until_first_stall done."),
644 Err(e) => {
645 trace!("MockExecutor executor, or async task, panicked!");
646 panic_any(e)
647 }
648 }
649 }
650
651 /// Keep polling tasks until `awake` is empty (inner, executor main loop)
652 ///
653 /// This is only called from [`MockExecutor::execute_until_first_stall`],
654 /// so it could also be called `execute_until_first_stall_inner`.
655 fn executor_main_loop(&self, mut main_fut: MainFuture) {
656 'outer: loop {
657 // Take a `Awake` task off `awake` and make it `Asleep`
658 let (id, mut fut) = 'inner: loop {
659 let mut data = self.shared.lock();
660 let Some(id) = data.schedule() else {
661 break 'outer;
662 };
663 let Some(task) = data.tasks.get_mut(id) else {
664 trace!("MockExecutor {id:?} vanished");
665 continue;
666 };
667 task.state = Asleep(vec![]);
668 let fut = task.fut.take().expect("future missing from task!");
669 break 'inner (id, fut);
670 };
671
672 // Poll the selected task
673 trace!("MockExecutor {id:?} polling...");
674 let waker = ActualWaker::make_waker(&self.shared, id);
675 let mut cx = Context::from_waker(&waker);
676 let r: Either<Poll<()>, IsSubthread> = match &mut fut {
677 TaskFutureInfo::Normal(fut) => Left(fut.poll_unpin(&mut cx)),
678 TaskFutureInfo::Main => Left(main_fut.as_mut().poll(&mut cx)),
679 TaskFutureInfo::Subthread => Right(IsSubthread),
680 };
681
682 // Deal with the returned `Poll`
683 let _fut_drop_late;
684 {
685 let mut data = self.shared.lock();
686 let task = data
687 .tasks
688 .get_mut(id)
689 .expect("task vanished while we were polling it");
690
691 match r {
692 Left(Pending) => {
693 trace!("MockExecutor {id:?} -> Pending");
694 if task.fut.is_some() {
695 panic!("task reinserted while we polled it?!");
696 }
697 // The task might have been woken *by its own poll method*.
698 // That's why we set it to `Asleep` *earlier* rather than here.
699 // All we need to do is put the future back.
700 task.fut = Some(fut);
701 }
702 Left(Ready(())) => {
703 trace!("MockExecutor {id:?} -> Ready");
704 // Oh, it finished!
705 // It might be in `awake`, but that's allowed to contain stale tasks,
706 // so we *don't* need to scan that list and remove it.
707 data.tasks.remove(id);
708 // It is important that we don't drop `fut` until we have released
709 // the data lock, since it is an external type and might try to reenter
710 // us (eg by calling spawn). If we do that here, we risk deadlock.
711 // So, move `fut` to a variable with scope outside the block with `data`.
712 _fut_drop_late = fut;
713 }
714 Right(IsSubthread) => {
715 trace!("MockExecutor {id:?} -> Ready, waking Subthread");
716 // Task is a subthread, which has called thread_context_switch
717 // to switch to us. We "poll" it by switching back.
718
719 // Put back `TFI::Subthread`, which was moved out temporarily, above.
720 task.fut = Some(fut);
721
722 self.shared.thread_context_switch(
723 data,
724 ThreadDescriptor::Executor,
725 ThreadDescriptor::Subthread(id),
726 );
727
728 // Now, if the Subthread still exists, that's because it's switched
729 // back to us, and is waiting in subthread_block_on_future again.
730 // Or it might have ended, in which case it's not in `tasks` any more.
731 // In any case we can go back to scheduling futures.
732 }
733 }
734 }
735 }
736 }
737}
738
739impl Data {
740 /// Return the next task to run
741 ///
742 /// The task is removed from `awake`, but **`state` is not set to `Asleep`**.
743 /// The caller must restore the invariant!
744 fn schedule(&mut self) -> Option<TaskId> {
745 use SchedulingPolicy as SP;
746 match self.scheduling {
747 SP::Stack => self.awake.pop_back(),
748 SP::Queue => self.awake.pop_front(),
749 }
750 }
751}
752
753impl ActualWaker {
754 /// Obtain a strong reference to the executor's data
755 fn upgrade_data(&self) -> Option<Arc<Shared>> {
756 self.data.upgrade()
757 }
758
759 /// Wake the task corresponding to this `ActualWaker`
760 ///
761 /// This is like `<Self as std::task::Wake>::wake()` but takes `&self`, not `Arc`
762 fn wake(&self) {
763 let Some(data) = self.upgrade_data() else {
764 // The executor is gone! Don't try to wake.
765 return;
766 };
767 let mut data = data.lock();
768 let data = &mut *data;
769 trace!("MockExecutor {:?} wake", &self.id);
770 let Some(task) = data.tasks.get_mut(self.id) else {
771 return;
772 };
773 task.set_awake(self.id, &mut data.awake);
774 }
775
776 /// Create and return a `Waker` for task `id`
777 fn make_waker(shared: &Arc<Shared>, id: TaskId) -> Waker {
778 ActualWaker {
779 data: Arc::downgrade(shared),
780 id,
781 }
782 .new_waker()
783 }
784}
785
786//---------- "progress until stalled" functionality ----------
787
788impl MockExecutor {
789 /// Run tasks in the current executor until every other task is waiting
790 ///
791 /// # Panics
792 ///
793 /// Might malfunction or panic if more than one such call is running at once.
794 ///
795 /// (Ie, you must `.await` or drop the returned `Future`
796 /// before calling this method again.)
797 ///
798 /// Must be called and awaited within a future being run by `self`.
799 pub fn progress_until_stalled(&self) -> impl Future<Output = ()> + use<> {
800 let mut data = self.shared.lock();
801 assert!(
802 data.progressing_until_stalled.is_none(),
803 "progress_until_stalled called more than once"
804 );
805 trace!("MockExecutor progress_until_stalled...");
806 data.progressing_until_stalled = Some(ProgressingUntilStalled {
807 finished: Pending,
808 waker: None,
809 });
810 ProgressUntilStalledFuture {
811 shared: self.shared.clone(),
812 }
813 }
814}
815
816impl Future for ProgressUntilStalledFuture {
817 type Output = ();
818
819 fn poll(self: Pin<&mut Self>, cx: &mut Context) -> Poll<()> {
820 let waker = cx.waker().clone();
821 let mut data = self.shared.lock();
822 let pus = data.progressing_until_stalled.as_mut();
823 trace!("MockExecutor progress_until_stalled polling... {:?}", &pus);
824 let pus = pus.expect("ProgressingUntilStalled missing");
825 pus.waker = Some(waker);
826 pus.finished
827 }
828}
829
830impl Drop for ProgressUntilStalledFuture {
831 fn drop(&mut self) {
832 self.shared.lock().progressing_until_stalled = None;
833 }
834}
835
836//---------- (sub)threads ----------
837
838impl MockExecutor {
839 /// Spawn a "Subthread", for processing in a sync context
840 ///
841 /// `call` will be run on a separate thread, called a "Subthread".
842 ///
843 /// But it will **not run simultaneously** with the executor,
844 /// nor with other Subthreads.
845 /// So Subthreads are somewhat like coroutines.
846 ///
847 /// `call` must be capable of making progress without waiting for any other Subthreads.
848 /// `call` may wait for async futures, using
849 /// [`subthread_block_on_future`](MockExecutor::subthread_block_on_future).
850 ///
851 /// Subthreads may be used for cpubound activity,
852 /// or synchronous IO (such as large volumes of disk activity),
853 /// provided that the synchronous code will reliably make progress,
854 /// without waiting (directly or indirectly) for any async task or Subthread -
855 /// except via `subthread_block_on_future`.
856 ///
857 /// # Subthreads vs raw `std::thread` threads
858 ///
859 /// Programs using `MockExecutor` may use `std::thread` threads directly.
860 /// However, this is not recommended. There are severe limitations:
861 ///
862 /// * Only a Subthread can re-enter the async context from sync code:
863 /// this must be done with
864 /// using [`subthread_block_on_future`](MockExecutor::subthread_block_on_future).
865 /// (Re-entering the executor with
866 /// [`block_on`](tor_rtcompat::ToplevelBlockOn::block_on)
867 /// is not allowed.)
868 /// * If async tasks want to suspend waiting for synchronous code,
869 /// the synchronous code must run on a Subthread.
870 /// This allows the `MockExecutor` to know when
871 /// that synchronous code is still making progress.
872 /// (This is needed for
873 /// [`progress_until_stalled`](MockExecutor::progress_until_stalled)
874 /// and the facilities which use it, such as
875 /// [`MockRuntime::advance_until_stalled`](crate::MockRuntime::advance_until_stalled).)
876 /// * Subthreads never run in parallel -
877 /// they only run as scheduled deterministically by the `MockExecutor`.
878 /// So using Subthreads eliminates a source of test nonndeterminism.
879 /// (Execution order is still varied due to explicitly varying the scheduling policy.)
880 ///
881 /// # Panics, abuse, and malfunctions
882 ///
883 /// If `call` panics and unwinds, `spawn_subthread` yields `Err`.
884 /// The application code should to do something about it if this happens,
885 /// typically, logging errors, tearing things down, or failing a test case.
886 ///
887 /// If the executor doesn't run, the subthread will not run either, and will remain stuck.
888 /// (So, typically, if the thread supposed to run the executor panics,
889 /// for example because a future or the executor itself panics,
890 /// all the subthreads will become stuck - effectively, they'll be leaked.)
891 ///
892 /// `spawn_subthread` panics if OS thread spawning fails.
893 /// (Like `std::thread::spawn()` does.)
894 ///
895 /// `MockExecutor`s will malfunction or panic if
896 /// any executor invocation method (eg `block_on`) is called on a Subthread.
897 pub fn subthread_spawn<T: Send + 'static>(
898 &self,
899 desc: impl Display,
900 call: impl FnOnce() -> T + Send + 'static,
901 ) -> impl Future<Output = Result<T, Box<dyn Any + Send>>> + Unpin + Send + Sync + 'static {
902 let desc = desc.to_string();
903 let (output_tx, output_rx) = oneshot::channel();
904
905 // NB: we don't know which thread we're on!
906 // In principle we might be on another Subthread.
907 // So we can't context switch here. That would be very confusing.
908 //
909 // Instead, we prepare the new Subthread as follows:
910 // - There is a task in the executor
911 // - The task is ready to be polled, whenever the executor decides to
912 // - The thread starts running right away, but immediately waits until it is scheduled
913 // See `subthread_entrypoint`.
914
915 {
916 let mut data = self.shared.lock();
917 let id = data.insert_task(desc.clone(), TaskFutureInfo::Subthread);
918
919 let _: std::thread::JoinHandle<()> = std::thread::Builder::new()
920 .name(desc)
921 .spawn({
922 let shared = self.shared.clone();
923 move || shared.subthread_entrypoint(id, call, output_tx)
924 })
925 .expect("spawn failed");
926 }
927
928 output_rx.map(|r| {
929 r.unwrap_or_else(|_: Canceled| panic!("Subthread cancelled but should be impossible!"))
930 })
931 }
932
933 /// Call an async `Future` from a Subthread
934 ///
935 /// Blocks the Subthread, and arranges to run async tasks,
936 /// including `fut`, until `fut` completes.
937 ///
938 /// `fut` is polled on the executor thread, not on the Subthread.
939 /// (We may change that in the future, allowing passing a non-`Send` future.)
940 ///
941 /// # Panics, abuse, and malfunctions
942 ///
943 /// `subthread_block_on_future` will malfunction or panic
944 /// if called on a thread that isn't a Subthread from the same `MockExecutor`
945 /// (ie a thread made with [`spawn_subthread`](MockExecutor::subthread_spawn)).
946 ///
947 /// If `fut` itself panics, the executor will panic.
948 ///
949 /// If the executor isn't running, `subthread_block_on_future` will hang indefinitely.
950 /// See `spawn_subthread`.
951 pub fn subthread_block_on_future<T: Send + 'static>(&self, fut: impl Future<Output = T>) -> T {
952 let id = match THREAD_DESCRIPTOR.get() {
953 ThreadDescriptor::Subthread(id) => id,
954 ThreadDescriptor::Executor => {
955 panic!("subthread_block_on_future called from MockExecutor thread (async task?)")
956 }
957 ThreadDescriptor::Foreign => panic!(
958 "subthread_block_on_future called on foreign thread (not spawned with spawn_subthread)"
959 ),
960 };
961 trace!("MockExecutor thread {id:?}, subthread_block_on_future...");
962 let mut fut = pin!(fut);
963
964 // We yield once before the first poll, and once after Ready, to shake up the
965 // execution order a bit, depending on the scheduling policy.
966 let yield_ = |set_awake| self.shared.subthread_yield(id, set_awake);
967 yield_(Some(SetAwake));
968
969 let ret = loop {
970 // Poll the provided future
971 trace!("MockExecutor thread {id:?}, s.t._block_on_future polling...");
972 let waker = ActualWaker::make_waker(&self.shared, id);
973 let mut cx = Context::from_waker(&waker);
974 let r: Poll<T> = fut.as_mut().poll(&mut cx);
975
976 if let Ready(r) = r {
977 trace!("MockExecutor thread {id:?}, s.t._block_on_future poll -> Ready");
978 break r;
979 }
980
981 // Pending. Switch back to the executor thread.
982 // When the future becomes ready, the Waker will be woken, waking the task,
983 // so that the executor will "poll" us again.
984 trace!("MockExecutor thread {id:?}, s.t._block_on_future poll -> Pending");
985
986 yield_(None);
987 };
988
989 yield_(Some(SetAwake));
990
991 trace!("MockExecutor thread {id:?}, subthread_block_on_future complete.");
992
993 ret
994 }
995}
996
997impl Shared {
998 /// Main entrypoint function for a Subthread
999 ///
1000 /// Entered on a new `std::thread` thread created by
1001 /// [`subthread_spawn`](MockExecutor::subthread_spawn).
1002 ///
1003 /// When `call` completes, sends its returned value `T` to `output_tx`.
1004 fn subthread_entrypoint<T: Send + 'static>(
1005 self: Arc<Self>,
1006 id: TaskId,
1007 call: impl FnOnce() -> T + Send + 'static,
1008 output_tx: oneshot::Sender<Result<T, Box<dyn Any + Send>>>,
1009 ) {
1010 THREAD_DESCRIPTOR.set(ThreadDescriptor::Subthread(id));
1011 trace!("MockExecutor thread {id:?}, entrypoint");
1012
1013 // We start out Awake, but we wait for the executor to tell us to run.
1014 // This will be done the first time the task is "polled".
1015 {
1016 let data = self.lock();
1017 self.thread_context_switch_waitfor_instruction_to_run(
1018 data,
1019 ThreadDescriptor::Subthread(id),
1020 );
1021 }
1022
1023 trace!("MockExecutor thread {id:?}, entering user code");
1024
1025 // Run the user's actual thread function.
1026 // This will typically reenter us via subthread_block_on_future.
1027 let ret = catch_unwind(AssertUnwindSafe(call));
1028
1029 trace!("MockExecutor thread {id:?}, completed user code");
1030
1031 // This makes the return value from subthread_spawn ready.
1032 // It will be polled by the executor in due course, presumably.
1033
1034 output_tx.send(ret).unwrap_or_else(
1035 #[allow(clippy::unnecessary_lazy_evaluations)]
1036 |_| {}, // receiver dropped, maybe executor dropped or something?
1037 );
1038
1039 {
1040 let mut data = self.lock();
1041
1042 // Never poll this task again (so never schedule this thread)
1043 let _: Task = data.tasks.remove(id).expect("Subthread task vanished!");
1044
1045 // Tell the executor it is scheduled now.
1046 // We carry on exiting, in parallel (holding the data lock).
1047 self.thread_context_switch_send_instruction_to_run(
1048 &mut data,
1049 ThreadDescriptor::Subthread(id),
1050 ThreadDescriptor::Executor,
1051 );
1052 }
1053 }
1054
1055 /// Yield back to the executor from a subthread
1056 ///
1057 /// Checks that things are in order
1058 /// (in particular, that this task is in the data structure as a subhtread)
1059 /// and switches to the executor thread.
1060 ///
1061 /// The caller must arrange that the task gets woken.
1062 ///
1063 /// With [`SetAwake`], sets our task awake, so that we'll be polled
1064 /// again as soon as we get to the top of the executor's queue.
1065 /// Otherwise, we'll be reentered after someone wakes a [`Waker`] for the task.
1066 fn subthread_yield(&self, us: TaskId, set_awake: Option<SetAwake>) {
1067 let mut data = self.lock();
1068 {
1069 let data = &mut *data;
1070 let task = data.tasks.get_mut(us).expect("Subthread task vanished!");
1071 match &task.fut {
1072 Some(TaskFutureInfo::Subthread) => {}
1073 other => panic!("subthread_block_on_future but TFI {other:?}"),
1074 };
1075 if let Some(SetAwake) = set_awake {
1076 task.set_awake(us, &mut data.awake);
1077 }
1078 }
1079 self.thread_context_switch(
1080 data,
1081 ThreadDescriptor::Subthread(us),
1082 ThreadDescriptor::Executor,
1083 );
1084 }
1085
1086 /// Switch from (sub)thread `us` to (sub)thread `them`
1087 ///
1088 /// Returns when someone calls `thread_context_switch(.., us)`.
1089 fn thread_context_switch(
1090 &self,
1091 mut data: MutexGuard<Data>,
1092 us: ThreadDescriptor,
1093 them: ThreadDescriptor,
1094 ) {
1095 trace!("MockExecutor thread {us:?}, switching to {them:?}");
1096 self.thread_context_switch_send_instruction_to_run(&mut data, us, them);
1097 self.thread_context_switch_waitfor_instruction_to_run(data, us);
1098 }
1099
1100 /// Instruct the (sub)thread `them` to run
1101 ///
1102 /// Update `thread_to_run`, which will wake up `them`'s
1103 /// call to `thread_context_switch_waitfor_instruction_to_run`.
1104 ///
1105 /// Must be called from (sub)thread `us`.
1106 /// Part of `thread_context_switch`, not normally called directly.
1107 fn thread_context_switch_send_instruction_to_run(
1108 &self,
1109 data: &mut MutexGuard<Data>,
1110 us: ThreadDescriptor,
1111 them: ThreadDescriptor,
1112 ) {
1113 assert_eq!(data.thread_to_run, us);
1114 data.thread_to_run = them;
1115 self.thread_condvar.notify_all();
1116 }
1117
1118 /// Await an instruction for this thread, `us`, to run
1119 ///
1120 /// Waits for `thread_to_run` to be `us`,
1121 /// waiting for `thread_condvar` as necessary.
1122 ///
1123 /// Part of `thread_context_switch`, not normally called directly.
1124 fn thread_context_switch_waitfor_instruction_to_run(
1125 &self,
1126 data: MutexGuard<Data>,
1127 us: ThreadDescriptor,
1128 ) {
1129 #[allow(let_underscore_lock)]
1130 let _: MutexGuard<_> = self
1131 .thread_condvar
1132 .wait_while(data, |data| {
1133 let live = data.thread_to_run;
1134 let resume = live == us;
1135 if resume {
1136 trace!("MockExecutor thread {us:?}, resuming");
1137 } else {
1138 trace!("MockExecutor thread {us:?}, waiting for {live:?}");
1139 }
1140 // We're in `.wait_while`, not `.wait_until`. Confusing.
1141 !resume
1142 })
1143 .expect("data lock poisoned");
1144 }
1145}
1146
1147//---------- ancillary and convenience functions ----------
1148
1149/// Trait to let us assert at compile time that something is nicely `Sync` etc.
1150#[allow(dead_code)] // yes, we don't *use* anything from this trait
1151trait EnsureSyncSend: Sync + Send + 'static {}
1152impl EnsureSyncSend for ActualWaker {}
1153impl EnsureSyncSend for MockExecutor {}
1154
1155impl MockExecutor {
1156 /// Return the number of tasks running in this executor
1157 ///
1158 /// One possible use is for a test case to check that task(s)
1159 /// that ought to have exited, have indeed done so.
1160 ///
1161 /// In the usual case, the answer will be at least 1,
1162 /// because it counts the future passed to
1163 /// [`block_on`](MockExecutor::block_on)
1164 /// (perhaps via [`MockRuntime::test_with_various`](crate::MockRuntime::test_with_various)).
1165 pub fn n_tasks(&self) -> usize {
1166 self.shared.lock().tasks.len()
1167 }
1168}
1169
1170impl Shared {
1171 /// Lock and obtain the guard
1172 ///
1173 /// Convenience method which panics on poison
1174 fn lock(&self) -> MutexGuard<Data> {
1175 self.data.lock().expect("data lock poisoned")
1176 }
1177}
1178
1179impl Task {
1180 /// Set task `id` to `Awake` and arrange that it will be polled.
1181 fn set_awake(&mut self, id: TaskId, data_awake: &mut VecDeque<TaskId>) {
1182 match self.state {
1183 Awake => {}
1184 Asleep(_) => {
1185 self.state = Awake;
1186 data_awake.push_back(id);
1187 }
1188 }
1189 }
1190}
1191
1192//---------- ActualWaker as RawWaker ----------
1193
1194/// Using [`ActualWaker`] in a [`RawWaker`]
1195///
1196/// We need to make a
1197/// [`Waker`] (the safe, type-erased, waker, used by actual futures)
1198/// which contains an
1199/// [`ActualWaker`] (our actual waker implementation, also safe).
1200///
1201/// `std` offers `Waker::from<Arc<impl Wake>>`.
1202/// But we want a bespoke `Clone` implementation, so we don't want to use `Arc`.
1203///
1204/// So instead, we implement the `RawWaker` API in terms of `ActualWaker`.
1205/// We keep the `ActualWaker` in a `Box`, and actually `clone` it (and the `Box`).
1206///
1207/// SAFETY
1208///
1209/// * The data pointer is `Box::<ActualWaker>::into_raw()`
1210/// * We share these when we clone
1211/// * No-one is allowed `&mut ActualWaker` unless there are no other clones
1212/// * So we may make references `&ActualWaker`
1213impl ActualWaker {
1214 /// Wrap up an [`ActualWaker`] as a type-erased [`Waker`] for passing to futures etc.
1215 fn new_waker(self) -> Waker {
1216 unsafe { Waker::from_raw(self.raw_new()) }
1217 }
1218
1219 /// Helper: wrap up an [`ActualWaker`] as a [`RawWaker`].
1220 fn raw_new(self) -> RawWaker {
1221 let self_: Box<ActualWaker> = self.into();
1222 let self_: *mut ActualWaker = Box::into_raw(self_);
1223 let self_: *const () = self_ as _;
1224 RawWaker::new(self_, &RAW_WAKER_VTABLE)
1225 }
1226
1227 /// Implementation of [`RawWakerVTable`]'s `clone`
1228 unsafe fn raw_clone(self_: *const ()) -> RawWaker {
1229 unsafe {
1230 let self_: *const ActualWaker = self_ as _;
1231 let self_: &ActualWaker = self_.as_ref().unwrap_unchecked();
1232 let copy: ActualWaker = self_.clone();
1233 copy.raw_new()
1234 }
1235 }
1236
1237 /// Implementation of [`RawWakerVTable`]'s `wake`
1238 unsafe fn raw_wake(self_: *const ()) {
1239 unsafe {
1240 Self::raw_wake_by_ref(self_);
1241 Self::raw_drop(self_);
1242 }
1243 }
1244
1245 /// Implementation of [`RawWakerVTable`]'s `wake_ref_by`
1246 unsafe fn raw_wake_by_ref(self_: *const ()) {
1247 unsafe {
1248 let self_: *const ActualWaker = self_ as _;
1249 let self_: &ActualWaker = self_.as_ref().unwrap_unchecked();
1250 self_.wake();
1251 }
1252 }
1253
1254 /// Implementation of [`RawWakerVTable`]'s `drop`
1255 unsafe fn raw_drop(self_: *const ()) {
1256 unsafe {
1257 let self_: *mut ActualWaker = self_ as _;
1258 let self_: Box<ActualWaker> = Box::from_raw(self_);
1259 drop(self_);
1260 }
1261 }
1262}
1263
1264/// vtable for `Box<ActualWaker>` as `RawWaker`
1265//
1266// This ought to be in the impl block above, but
1267// "associated `static` items are not allowed"
1268static RAW_WAKER_VTABLE: RawWakerVTable = RawWakerVTable::new(
1269 ActualWaker::raw_clone,
1270 ActualWaker::raw_wake,
1271 ActualWaker::raw_wake_by_ref,
1272 ActualWaker::raw_drop,
1273);
1274
1275//---------- Sleep location tracking and dumping ----------
1276
1277/// We record "where a future went to sleep" as (just) a backtrace
1278///
1279/// This type alias allows us to mock `Backtrace` for miri.
1280/// (It also insulates from future choices about sleep location representation.0
1281#[cfg(not(miri))]
1282type SleepLocation = Backtrace;
1283
1284impl Data {
1285 /// Dump tasks and their sleep location backtraces
1286 fn dump_backtraces(&self, f: &mut fmt::Formatter) -> fmt::Result {
1287 for (id, task) in self.tasks.iter() {
1288 let prefix = |f: &mut fmt::Formatter| write!(f, "{id:?}={task:?}: ");
1289 match &task.state {
1290 Awake => {
1291 prefix(f)?;
1292 writeln!(f, "awake")?;
1293 }
1294 Asleep(locs) => {
1295 let n = locs.len();
1296 for (i, loc) in locs.iter().enumerate() {
1297 prefix(f)?;
1298 writeln!(f, "asleep, backtrace {i}/{n}:\n{loc}",)?;
1299 }
1300 if n == 0 {
1301 prefix(f)?;
1302 writeln!(f, "asleep, no backtraces, Waker never cloned, stuck!",)?;
1303 }
1304 }
1305 }
1306 }
1307 writeln!(
1308 f,
1309 "\nNote: there might be spurious traces, see docs for MockExecutor::debug_dump\n"
1310 )?;
1311 Ok(())
1312 }
1313}
1314
1315/// Track sleep locations via `<Waker as Clone>`.
1316///
1317/// See [`MockExecutor::debug_dump`] for the explanation.
1318impl Clone for ActualWaker {
1319 fn clone(&self) -> Self {
1320 let id = self.id;
1321
1322 if let Some(data) = self.upgrade_data() {
1323 // If the executor is gone, there is nothing to adjust
1324 let mut data = data.lock();
1325 if let Some(task) = data.tasks.get_mut(self.id) {
1326 match &mut task.state {
1327 Awake => trace!("MockExecutor cloned waker for awake task {id:?}"),
1328 Asleep(locs) => locs.push(SleepLocation::force_capture()),
1329 }
1330 } else {
1331 trace!("MockExecutor cloned waker for dead task {id:?}");
1332 }
1333 }
1334
1335 ActualWaker {
1336 data: self.data.clone(),
1337 id,
1338 }
1339 }
1340}
1341
1342//---------- API for full debug dump ----------
1343
1344/// Debugging dump of a `MockExecutor`'s state
1345///
1346/// Returned by [`MockExecutor::as_debug_dump`]
1347//
1348// Existence implies backtraces have been resolved
1349//
1350// We use `Either` so that we can also use this internally when we have &mut Data.
1351pub struct DebugDump<'a>(Either<&'a Data, MutexGuard<'a, Data>>);
1352
1353impl MockExecutor {
1354 /// Dump the executor's state including backtraces of waiting tasks, to stderr
1355 ///
1356 /// This is considerably more extensive than simply
1357 /// `MockExecutor as Debug`.
1358 ///
1359 /// (This is a convenience method, which wraps
1360 /// [`MockExecutor::as_debug_dump()`].
1361 ///
1362 /// ### Backtrace salience (possible spurious traces)
1363 ///
1364 /// **Summary**
1365 ///
1366 /// The technique used to capture backtraces when futures sleep is not 100% exact.
1367 /// It will usually show all the actual sleeping sites,
1368 /// but it might also show other backtraces which were part of
1369 /// the implementation of some complex relevant future.
1370 ///
1371 /// **Details**
1372 ///
1373 /// When a future's implementation wants to sleep,
1374 /// it needs to record the [`Waker`] (from the [`Context`])
1375 /// so that the "other end" can call `.wake()` on it later,
1376 /// when the future should be woken.
1377 ///
1378 /// Since `Context.waker()` gives `&Waker`, borrowed from the `Context`,
1379 /// the future must clone the `Waker`,
1380 /// and it must do so in within the `poll()` call.
1381 ///
1382 /// A future which is waiting in a `select!` will typically
1383 /// show multiple traces, one for each branch.
1384 /// But,
1385 /// if a future sleeps on one thing, and then when polled again later,
1386 /// sleeps on something different, without waking up in between,
1387 /// both backtrace locations will be shown.
1388 /// And,
1389 /// a complicated future contraption *might* clone the `Waker` more times.
1390 /// So not every backtrace will necessarily be informative.
1391 ///
1392 /// ### Panics
1393 ///
1394 /// Panics on write errors.
1395 pub fn debug_dump(&self) {
1396 self.as_debug_dump().to_stderr();
1397 }
1398
1399 /// Dump the executor's state including backtraces of waiting tasks
1400 ///
1401 /// This is considerably more extensive than simply
1402 /// `MockExecutor as Debug`.
1403 ///
1404 /// Returns an object for formatting with [`Debug`].
1405 /// To simply print the dump to stderr (eg in a test),
1406 /// use [`.debug_dump()`](MockExecutor::debug_dump).
1407 ///
1408 /// **Backtrace salience (possible spurious traces)** -
1409 /// see [`.debug_dump()`](MockExecutor::debug_dump).
1410 pub fn as_debug_dump(&self) -> DebugDump {
1411 let data = self.shared.lock();
1412 DebugDump(Right(data))
1413 }
1414}
1415
1416impl Data {
1417 /// Convenience function: dump including backtraces, to stderr
1418 fn debug_dump(&mut self) {
1419 DebugDump(Left(self)).to_stderr();
1420 }
1421}
1422
1423impl DebugDump<'_> {
1424 /// Convenience function: dump tasks and backtraces to stderr
1425 #[allow(clippy::wrong_self_convention)] // "to_stderr" doesn't mean "convert to stderr"
1426 fn to_stderr(self) {
1427 write!(io::stderr().lock(), "{:?}", self)
1428 .unwrap_or_else(|e| error_report!(e, "failed to write debug dump to stderr"));
1429 }
1430}
1431
1432//---------- bespoke Debug impls ----------
1433
1434impl Debug for DebugDump<'_> {
1435 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1436 let self_: &Data = &self.0;
1437
1438 writeln!(f, "MockExecutor state:\n{self_:#?}")?;
1439 writeln!(f, "MockExecutor task dump:")?;
1440 self_.dump_backtraces(f)?;
1441
1442 Ok(())
1443 }
1444}
1445
1446// See `impl Debug for Data` for notes on the output
1447impl Debug for Task {
1448 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1449 let Task { desc, state, fut } = self;
1450 write!(f, "{:?}", desc)?;
1451 write!(f, "=")?;
1452 match fut {
1453 None => write!(f, "P")?,
1454 Some(TaskFutureInfo::Normal(_)) => write!(f, "f")?,
1455 Some(TaskFutureInfo::Main) => write!(f, "m")?,
1456 Some(TaskFutureInfo::Subthread) => write!(f, "T")?,
1457 }
1458 match state {
1459 Awake => write!(f, "W")?,
1460 Asleep(locs) => write!(f, "s{}", locs.len())?,
1461 };
1462 Ok(())
1463 }
1464}
1465
1466/// Helper: `Debug`s as a list of tasks, given the `Data` for lookups and a list of the ids
1467///
1468/// `Task`s in `Data` are printed as `Ti(ID)"SPEC"=FLAGS"`.
1469///
1470/// `FLAGS` are:
1471///
1472/// * `T`: this task is for a Subthread (from subthread_spawn).
1473/// * `P`: this task is being polled (its `TaskFutureInfo` is absent)
1474/// * `f`: this is a normal task with a future and its future is present in `Data`
1475/// * `m`: this is the main task from `block_on`
1476///
1477/// * `W`: the task is awake
1478/// * `s<n>`: the task is asleep, and `<n>` is the number of recorded sleeping locations
1479//
1480// We do it this way because the naive dump from derive is very expansive
1481// and makes it impossible to see the wood for the trees.
1482// This very compact representation it easier to find a task of interest in the output.
1483//
1484// This is implemented in `impl Debug for Task`.
1485//
1486//
1487// rustc doesn't think automatically-derived Debug impls count for whether a thing is used.
1488// This has caused quite some fallout. https://github.com/rust-lang/rust/pull/85200
1489// I think derive_more emits #[automatically_derived], so that even though we use this
1490// in our Debug impl, that construction is unused.
1491#[allow(dead_code)]
1492struct DebugTasks<'d, F>(&'d Data, F);
1493
1494// See `impl Debug for Data` for notes on the output
1495impl<F, I> Debug for DebugTasks<'_, F>
1496where
1497 F: Fn() -> I,
1498 I: Iterator<Item = TaskId>,
1499{
1500 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1501 let DebugTasks(data, ids) = self;
1502 for (id, delim) in izip!(ids(), chain!(iter::once(""), iter::repeat(" ")),) {
1503 write!(f, "{delim}{id:?}")?;
1504 match data.tasks.get(id) {
1505 None => write!(f, "-")?,
1506 Some(task) => write!(f, "={task:?}")?,
1507 }
1508 }
1509 Ok(())
1510 }
1511}
1512
1513/// Mock `Backtrace` for miri
1514///
1515/// See also the not-miri `type SleepLocation`, alias above.
1516#[cfg(miri)]
1517mod miri_sleep_location {
1518 #[derive(Debug, derive_more::Display)]
1519 #[display("<SleepLocation>")]
1520 pub(super) struct SleepLocation {}
1521
1522 impl SleepLocation {
1523 pub(super) fn force_capture() -> Self {
1524 SleepLocation {}
1525 }
1526 }
1527}
1528#[cfg(miri)]
1529use miri_sleep_location::SleepLocation;
1530
1531#[cfg(test)]
1532mod test {
1533 // @@ begin test lint list maintained by maint/add_warning @@
1534 #![allow(clippy::bool_assert_comparison)]
1535 #![allow(clippy::clone_on_copy)]
1536 #![allow(clippy::dbg_macro)]
1537 #![allow(clippy::mixed_attributes_style)]
1538 #![allow(clippy::print_stderr)]
1539 #![allow(clippy::print_stdout)]
1540 #![allow(clippy::single_char_pattern)]
1541 #![allow(clippy::unwrap_used)]
1542 #![allow(clippy::unchecked_time_subtraction)]
1543 #![allow(clippy::useless_vec)]
1544 #![allow(clippy::needless_pass_by_value)]
1545 #![allow(clippy::string_slice)] // See arti#2571
1546 //! <!-- @@ end test lint list maintained by maint/add_warning @@ -->
1547 use super::*;
1548 use futures::channel::mpsc;
1549 use futures::{SinkExt as _, StreamExt as _};
1550 use strum::IntoEnumIterator;
1551 use tracing::info;
1552
1553 #[cfg(not(miri))] // trace! asks for the time, which miri doesn't support
1554 use tracing_test::traced_test;
1555
1556 fn various_mock_executors() -> impl Iterator<Item = MockExecutor> {
1557 // This duplicates the part of the logic in MockRuntime::test_with_various which
1558 // relates to MockExecutor, because we don't have a MockRuntime::builder.
1559 // The only parameter to MockExecutor is its scheduling policy, so this seems fine.
1560 SchedulingPolicy::iter().map(|scheduling| {
1561 eprintln!("===== MockExecutor::with_scheduling({scheduling:?}) =====");
1562 MockExecutor::with_scheduling(scheduling)
1563 })
1564 }
1565
1566 #[cfg_attr(not(miri), traced_test)]
1567 #[test]
1568 fn simple() {
1569 let runtime = MockExecutor::default();
1570 let val = runtime.block_on(async { 42 });
1571 assert_eq!(val, 42);
1572 }
1573
1574 #[cfg_attr(not(miri), traced_test)]
1575 #[test]
1576 fn stall() {
1577 let runtime = MockExecutor::default();
1578
1579 runtime.block_on({
1580 let runtime = runtime.clone();
1581 async move {
1582 const N: usize = 3;
1583 let (mut txs, mut rxs): (Vec<_>, Vec<_>) =
1584 (0..N).map(|_| mpsc::channel::<usize>(5)).unzip();
1585
1586 let mut rx_n = rxs.pop().unwrap();
1587
1588 for (i, mut rx) in rxs.into_iter().enumerate() {
1589 runtime.spawn_identified(i, {
1590 let mut txs = txs.clone();
1591 async move {
1592 loop {
1593 eprintln!("task {i} rx...");
1594 let v = rx.next().await.unwrap();
1595 let nv = v + 1;
1596 eprintln!("task {i} rx {v}, tx {nv}");
1597 let v = nv;
1598 txs[v].send(v).await.unwrap();
1599 }
1600 }
1601 });
1602 }
1603
1604 dbg!();
1605 #[allow(deprecated)] // TODO(#2386)
1606 let _: mpsc::TryRecvError = rx_n.try_next().unwrap_err();
1607
1608 dbg!();
1609 runtime.progress_until_stalled().await;
1610
1611 dbg!();
1612 #[allow(deprecated)] // TODO(#2386)
1613 let _: mpsc::TryRecvError = rx_n.try_next().unwrap_err();
1614
1615 dbg!();
1616 txs[0].send(0).await.unwrap();
1617
1618 dbg!();
1619 runtime.progress_until_stalled().await;
1620
1621 dbg!();
1622 let r = rx_n.next().await;
1623 assert_eq!(r, Some(N - 1));
1624
1625 dbg!();
1626 #[allow(deprecated)] // TODO(#2386)
1627 let _: mpsc::TryRecvError = rx_n.try_next().unwrap_err();
1628
1629 runtime.spawn_identified("tx", {
1630 let txs = txs.clone();
1631 async {
1632 eprintln!("sending task...");
1633 for (i, mut tx) in txs.into_iter().enumerate() {
1634 eprintln!("sending 0 to {i}...");
1635 tx.send(0).await.unwrap();
1636 }
1637 eprintln!("sending task done");
1638 }
1639 });
1640
1641 runtime.debug_dump();
1642
1643 for i in 0..txs.len() {
1644 eprintln!("main {i} wait stall...");
1645 runtime.progress_until_stalled().await;
1646 eprintln!("main {i} rx wait...");
1647 let r = rx_n.next().await;
1648 eprintln!("main {i} rx = {r:?}");
1649 assert!(r == Some(0) || r == Some(N - 1));
1650 }
1651
1652 eprintln!("finishing...");
1653 runtime.progress_until_stalled().await;
1654 eprintln!("finished.");
1655 }
1656 });
1657 }
1658
1659 #[cfg_attr(not(miri), traced_test)]
1660 #[test]
1661 fn spawn_blocking() {
1662 let runtime = MockExecutor::default();
1663
1664 runtime.block_on({
1665 let runtime = runtime.clone();
1666 async move {
1667 let thr_1 = runtime.spawn_blocking(|| 42);
1668 let thr_2 = runtime.spawn_blocking(|| 99);
1669
1670 assert_eq!(thr_2.await, 99);
1671 assert_eq!(thr_1.await, 42);
1672 }
1673 });
1674 }
1675
1676 #[cfg_attr(not(miri), traced_test)]
1677 #[test]
1678 fn drop_reentrancy() {
1679 // Check that dropping a completed task future is done *outside* the data lock.
1680 // Involves a contrived future whose Drop impl reenters the executor.
1681 //
1682 // If `_fut_drop_late = fut` in execute_until_first_stall (the main loop)
1683 // is replaced with `drop(fut)` (dropping the future at the wrong moment),
1684 // we do indeed get deadlock, so this test case is working.
1685
1686 struct ReentersOnDrop {
1687 runtime: MockExecutor,
1688 }
1689 impl Future for ReentersOnDrop {
1690 type Output = ();
1691 fn poll(self: Pin<&mut Self>, _cx: &mut Context) -> Poll<()> {
1692 Poll::Ready(())
1693 }
1694 }
1695 impl Drop for ReentersOnDrop {
1696 fn drop(&mut self) {
1697 self.runtime
1698 .spawn_identified("dummy", futures::future::ready(()));
1699 }
1700 }
1701
1702 for runtime in various_mock_executors() {
1703 runtime.block_on(async {
1704 runtime.spawn_identified("trapper", {
1705 let runtime = runtime.clone();
1706 ReentersOnDrop { runtime }
1707 });
1708 });
1709 }
1710 }
1711
1712 #[cfg_attr(not(miri), traced_test)]
1713 #[test]
1714 fn subthread_oneshot() {
1715 for runtime in various_mock_executors() {
1716 runtime.block_on(async {
1717 let (tx, rx) = oneshot::channel();
1718 info!("spawning subthread");
1719 let thr = runtime.subthread_spawn("thr1", {
1720 let runtime = runtime.clone();
1721 move || {
1722 info!("subthread_block_on_future...");
1723 let i = runtime.subthread_block_on_future(rx).unwrap();
1724 info!("subthread_block_on_future => {i}");
1725 i + 1
1726 }
1727 });
1728 info!("main task sending");
1729 tx.send(12).unwrap();
1730 info!("main task sent");
1731 let r = thr.await.unwrap();
1732 info!("main task thr => {r}");
1733 assert_eq!(r, 13);
1734 });
1735 }
1736 }
1737
1738 #[cfg_attr(not(miri), traced_test)]
1739 #[test]
1740 fn subthread_pingpong() {
1741 for runtime in various_mock_executors() {
1742 runtime.block_on(async {
1743 let (mut i_tx, mut i_rx) = mpsc::channel(1);
1744 let (mut o_tx, mut o_rx) = mpsc::channel(1);
1745 info!("spawning subthread");
1746 let thr = runtime.subthread_spawn("thr", {
1747 let runtime = runtime.clone();
1748 move || {
1749 while let Some(i) = {
1750 info!("thread receiving ...");
1751 runtime.subthread_block_on_future(i_rx.next())
1752 } {
1753 let o = i + 12;
1754 info!("thread received {i}, sending {o}");
1755 runtime.subthread_block_on_future(o_tx.send(o)).unwrap();
1756 info!("thread sent {o}");
1757 }
1758 info!("thread exiting");
1759 42
1760 }
1761 });
1762 for i in 0..2 {
1763 info!("main task sending {i}");
1764 i_tx.send(i).await.unwrap();
1765 info!("main task sent {i}");
1766 let o = o_rx.next().await.unwrap();
1767 info!("main task recv => {o}");
1768 assert_eq!(o, i + 12);
1769 }
1770 info!("main task dropping sender");
1771 drop(i_tx);
1772 info!("main task awaiting thread");
1773 let r = thr.await.unwrap();
1774 info!("main task complete");
1775 assert_eq!(r, 42);
1776 });
1777 }
1778 }
1779}