async_executor/lib.rs
1//! Async executors.
2//!
3//! This crate provides two reference executors that trade performance for
4//! functionality. They should be considered reference executors that are "good
5//! enough" for most use cases. For more specialized use cases, consider writing
6//! your own executor on top of [`async-task`].
7//!
8//! [`async-task`]: https://crates.io/crates/async-task
9//!
10//! # Examples
11//!
12//! ```
13//! use async_executor::Executor;
14//! use futures_lite::future;
15//!
16//! // Create a new executor.
17//! let ex = Executor::new();
18//!
19//! // Spawn a task.
20//! let task = ex.spawn(async {
21//! println!("Hello world");
22//! });
23//!
24//! // Run the executor until the task completes.
25//! future::block_on(ex.run(task));
26//! ```
27
28#![warn(
29 missing_docs,
30 missing_debug_implementations,
31 rust_2018_idioms,
32 clippy::undocumented_unsafe_blocks
33)]
34#![doc(
35 html_favicon_url = "https://raw.githubusercontent.com/smol-rs/smol/master/assets/images/logo_fullsize_transparent.png"
36)]
37#![doc(
38 html_logo_url = "https://raw.githubusercontent.com/smol-rs/smol/master/assets/images/logo_fullsize_transparent.png"
39)]
40#![cfg_attr(docsrs, feature(doc_cfg))]
41#![allow(clippy::unused_unit)] // false positive fixed in Rust 1.89
42
43extern crate alloc;
44
45use alloc::rc::Rc;
46use alloc::sync::Arc;
47use alloc::vec::Vec;
48use core::fmt;
49use core::marker::PhantomData;
50use core::panic::{RefUnwindSafe, UnwindSafe};
51use core::pin::Pin;
52use core::sync::atomic::{AtomicBool, AtomicPtr, Ordering};
53use core::task::{Context, Poll, Waker};
54use std::sync::{Mutex, MutexGuard, PoisonError, RwLock, TryLockError};
55
56use async_task::{Builder, Runnable};
57use concurrent_queue::ConcurrentQueue;
58use futures_lite::{future, prelude::*};
59use pin_project_lite::pin_project;
60use slab::Slab;
61
62#[cfg(feature = "static")]
63mod static_executors;
64
65#[doc(no_inline)]
66pub use async_task::{FallibleTask, Task};
67#[cfg(feature = "static")]
68#[cfg_attr(docsrs, doc(cfg(any(feature = "static"))))]
69pub use static_executors::*;
70
71/// An async executor.
72///
73/// # Examples
74///
75/// A multi-threaded executor:
76///
77/// ```
78/// use async_channel::unbounded;
79/// use async_executor::Executor;
80/// use easy_parallel::Parallel;
81/// use futures_lite::future;
82///
83/// let ex = Executor::new();
84/// let (signal, shutdown) = unbounded::<()>();
85///
86/// Parallel::new()
87/// // Run four executor threads.
88/// .each(0..4, |_| future::block_on(ex.run(shutdown.recv())))
89/// // Run the main future on the current thread.
90/// .finish(|| future::block_on(async {
91/// println!("Hello world!");
92/// drop(signal);
93/// }));
94/// ```
95pub struct Executor<'a> {
96 /// The executor state.
97 state: AtomicPtr<State>,
98
99 /// Makes the `'a` lifetime invariant.
100 _marker: PhantomData<core::cell::UnsafeCell<&'a ()>>,
101}
102
103// SAFETY: Executor stores no thread local state that can be accessed via other thread.
104unsafe impl Send for Executor<'_> {}
105// SAFETY: Executor internally synchronizes all of it's operations internally.
106unsafe impl Sync for Executor<'_> {}
107
108impl UnwindSafe for Executor<'_> {}
109impl RefUnwindSafe for Executor<'_> {}
110
111impl fmt::Debug for Executor<'_> {
112 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
113 debug_executor(self, "Executor", f)
114 }
115}
116
117impl<'a> Executor<'a> {
118 /// Creates a new executor.
119 ///
120 /// # Examples
121 ///
122 /// ```
123 /// use async_executor::Executor;
124 ///
125 /// let ex = Executor::new();
126 /// ```
127 pub const fn new() -> Self {
128 Self {
129 state: AtomicPtr::new(core::ptr::null_mut()),
130 _marker: PhantomData,
131 }
132 }
133
134 /// Returns `true` if there are no unfinished tasks.
135 ///
136 /// # Examples
137 ///
138 /// ```
139 /// use async_executor::Executor;
140 ///
141 /// let ex = Executor::new();
142 /// assert!(ex.is_empty());
143 ///
144 /// let task = ex.spawn(async {
145 /// println!("Hello world");
146 /// });
147 /// assert!(!ex.is_empty());
148 ///
149 /// assert!(ex.try_tick());
150 /// assert!(ex.is_empty());
151 /// ```
152 pub fn is_empty(&self) -> bool {
153 self.state().active().is_empty()
154 }
155
156 /// Spawns a task onto the executor.
157 ///
158 /// # Examples
159 ///
160 /// ```
161 /// use async_executor::Executor;
162 ///
163 /// let ex = Executor::new();
164 ///
165 /// let task = ex.spawn(async {
166 /// println!("Hello world");
167 /// });
168 /// ```
169 pub fn spawn<T: Send + 'a>(&self, future: impl Future<Output = T> + Send + 'a) -> Task<T> {
170 let mut active = self.state().active();
171
172 // SAFETY: `T` and the future are `Send`.
173 unsafe { self.spawn_inner(future, &mut active) }
174 }
175
176 /// Spawns many tasks onto the executor.
177 ///
178 /// As opposed to the [`spawn`] method, this locks the executor's inner task lock once and
179 /// spawns all of the tasks in one go. With large amounts of tasks this can improve
180 /// contention.
181 ///
182 /// For very large numbers of tasks the lock is occasionally dropped and re-acquired to
183 /// prevent runner thread starvation. It is assumed that the iterator provided does not
184 /// block; blocking iterators can lock up the internal mutex and therefore the entire
185 /// executor.
186 ///
187 /// ## Example
188 ///
189 /// ```
190 /// use async_executor::Executor;
191 /// use futures_lite::{stream, prelude::*};
192 /// use core::future::ready;
193 ///
194 /// # futures_lite::future::block_on(async {
195 /// let mut ex = Executor::new();
196 ///
197 /// let futures = [
198 /// ready(1),
199 /// ready(2),
200 /// ready(3)
201 /// ];
202 ///
203 /// // Spawn all of the futures onto the executor at once.
204 /// let mut tasks = vec![];
205 /// ex.spawn_many(futures, &mut tasks);
206 ///
207 /// // Await all of them.
208 /// let results = ex.run(async move {
209 /// stream::iter(tasks).then(|x| x).collect::<Vec<_>>().await
210 /// }).await;
211 /// assert_eq!(results, [1, 2, 3]);
212 /// # });
213 /// ```
214 ///
215 /// [`spawn`]: Executor::spawn
216 pub fn spawn_many<T: Send + 'a, F: Future<Output = T> + Send + 'a>(
217 &self,
218 futures: impl IntoIterator<Item = F>,
219 handles: &mut impl Extend<Task<F::Output>>,
220 ) {
221 let mut active = Some(self.state().active());
222
223 // Convert the futures into tasks.
224 let tasks = futures.into_iter().enumerate().map(move |(i, future)| {
225 // SAFETY: `T` and the future are `Send`.
226 let task = unsafe { self.spawn_inner(future, active.as_mut().unwrap()) };
227
228 // Yield the lock every once in a while to ease contention.
229 if i.wrapping_sub(1) % 500 == 0 {
230 drop(active.take());
231 active = Some(self.state().active());
232 }
233
234 task
235 });
236
237 // Push the tasks to the user's collection.
238 handles.extend(tasks);
239 }
240
241 /// Spawn a future while holding the inner lock.
242 ///
243 /// # Safety
244 ///
245 /// If this is an `Executor`, `F` and `T` must be `Send`.
246 unsafe fn spawn_inner<T: 'a>(
247 &self,
248 future: impl Future<Output = T> + 'a,
249 active: &mut Slab<Waker>,
250 ) -> Task<T> {
251 // Remove the task from the set of active tasks when the future finishes.
252 let entry = active.vacant_entry();
253 let index = entry.key();
254 let state = self.state_as_arc();
255 let future = AsyncCallOnDrop::new(future, move || drop(state.active().try_remove(index)));
256
257 // Create the task and register it in the set of active tasks.
258 //
259 // SAFETY:
260 //
261 // If `future` is not `Send`, this must be a `LocalExecutor` as per this
262 // function's unsafe precondition. Since `LocalExecutor` is `!Sync`,
263 // `try_tick`, `tick` and `run` can only be called from the origin
264 // thread of the `LocalExecutor`. Similarly, `spawn` can only be called
265 // from the origin thread, ensuring that `future` and the executor share
266 // the same origin thread. The `Runnable` can be scheduled from other
267 // threads, but because of the above `Runnable` can only be called or
268 // dropped on the origin thread.
269 //
270 // `future` is not `'static`, but we make sure that the `Runnable` does
271 // not outlive `'a`. When the executor is dropped, the `active` field is
272 // drained and all of the `Waker`s are woken. Then, the queue inside of
273 // the `Executor` is drained of all of its runnables. This ensures that
274 // runnables are dropped and this precondition is satisfied.
275 //
276 // `self.schedule()` is `Send`, `Sync` and `'static`, as checked below.
277 // Therefore we do not need to worry about what is done with the
278 // `Waker`.
279 let (runnable, task) = Builder::new()
280 .propagate_panic(true)
281 .spawn_unchecked(|()| future, self.schedule());
282 entry.insert(runnable.waker());
283
284 runnable.schedule();
285 task
286 }
287
288 /// Attempts to run a task if at least one is scheduled.
289 ///
290 /// Running a scheduled task means simply polling its future once.
291 ///
292 /// # Examples
293 ///
294 /// ```
295 /// use async_executor::Executor;
296 ///
297 /// let ex = Executor::new();
298 /// assert!(!ex.try_tick()); // no tasks to run
299 ///
300 /// let task = ex.spawn(async {
301 /// println!("Hello world");
302 /// });
303 /// assert!(ex.try_tick()); // a task was found
304 /// ```
305 pub fn try_tick(&self) -> bool {
306 self.state().try_tick()
307 }
308
309 /// Runs a single task.
310 ///
311 /// Running a task means simply polling its future once.
312 ///
313 /// If no tasks are scheduled when this method is called, it will wait until one is scheduled.
314 ///
315 /// # Examples
316 ///
317 /// ```
318 /// use async_executor::Executor;
319 /// use futures_lite::future;
320 ///
321 /// let ex = Executor::new();
322 ///
323 /// let task = ex.spawn(async {
324 /// println!("Hello world");
325 /// });
326 /// future::block_on(ex.tick()); // runs the task
327 /// ```
328 pub async fn tick(&self) {
329 self.state().tick().await;
330 }
331
332 /// Runs the executor until the given future completes.
333 ///
334 /// # Examples
335 ///
336 /// ```
337 /// use async_executor::Executor;
338 /// use futures_lite::future;
339 ///
340 /// let ex = Executor::new();
341 ///
342 /// let task = ex.spawn(async { 1 + 2 });
343 /// let res = future::block_on(ex.run(async { task.await * 2 }));
344 ///
345 /// assert_eq!(res, 6);
346 /// ```
347 pub async fn run<T>(&self, future: impl Future<Output = T>) -> T {
348 self.state().run(future).await
349 }
350
351 /// Returns a function that schedules a runnable task when it gets woken up.
352 fn schedule(&self) -> impl Fn(Runnable) + Send + Sync + 'static {
353 let state = self.state_as_arc();
354
355 // TODO: If possible, push into the current local queue and notify the ticker.
356 move |runnable| {
357 let result = state.queue.push(runnable);
358 debug_assert!(result.is_ok()); // Since we use unbounded queue, push will never fail.
359 state.notify();
360 }
361 }
362
363 /// Returns a pointer to the inner state.
364 #[inline]
365 fn state_ptr(&self) -> *const State {
366 #[cold]
367 fn alloc_state(atomic_ptr: &AtomicPtr<State>) -> *mut State {
368 let state = Arc::new(State::new());
369 // TODO: Switch this to use cast_mut once the MSRV can be bumped past 1.65
370 let ptr = Arc::into_raw(state) as *mut State;
371 if let Err(actual) = atomic_ptr.compare_exchange(
372 core::ptr::null_mut(),
373 ptr,
374 Ordering::AcqRel,
375 Ordering::Acquire,
376 ) {
377 // SAFETY: This was just created from Arc::into_raw.
378 drop(unsafe { Arc::from_raw(ptr) });
379 actual
380 } else {
381 ptr
382 }
383 }
384
385 let mut ptr = self.state.load(Ordering::Acquire);
386 if ptr.is_null() {
387 ptr = alloc_state(&self.state);
388 }
389 ptr
390 }
391
392 /// Returns a reference to the inner state.
393 #[inline]
394 fn state(&self) -> &State {
395 // SAFETY: So long as an Executor lives, it's state pointer will always be valid
396 // when accessed through state_ptr.
397 unsafe { &*self.state_ptr() }
398 }
399
400 // Clones the inner state Arc
401 #[inline]
402 fn state_as_arc(&self) -> Arc<State> {
403 // SAFETY: So long as an Executor lives, it's state pointer will always be a valid
404 // Arc when accessed through state_ptr.
405 let arc = unsafe { Arc::from_raw(self.state_ptr()) };
406 let clone = arc.clone();
407 std::mem::forget(arc);
408 clone
409 }
410}
411
412impl Drop for Executor<'_> {
413 fn drop(&mut self) {
414 let ptr = *self.state.get_mut();
415 if ptr.is_null() {
416 return;
417 }
418
419 // SAFETY: As ptr is not null, it was allocated via Arc::new and converted
420 // via Arc::into_raw in state_ptr.
421 let state = unsafe { Arc::from_raw(ptr) };
422
423 let mut active = state.active();
424 for w in active.drain() {
425 w.wake();
426 }
427 drop(active);
428
429 while state.queue.pop().is_ok() {}
430 }
431}
432
433impl<'a> Default for Executor<'a> {
434 fn default() -> Self {
435 Self::new()
436 }
437}
438
439/// A thread-local executor.
440///
441/// The executor can only be run on the thread that created it.
442///
443/// # Examples
444///
445/// ```
446/// use async_executor::LocalExecutor;
447/// use futures_lite::future;
448///
449/// let local_ex = LocalExecutor::new();
450///
451/// future::block_on(local_ex.run(async {
452/// println!("Hello world!");
453/// }));
454/// ```
455pub struct LocalExecutor<'a> {
456 /// The inner executor.
457 inner: Executor<'a>,
458
459 /// Makes the type `!Send` and `!Sync`.
460 _marker: PhantomData<Rc<()>>,
461}
462
463impl UnwindSafe for LocalExecutor<'_> {}
464impl RefUnwindSafe for LocalExecutor<'_> {}
465
466impl fmt::Debug for LocalExecutor<'_> {
467 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
468 debug_executor(&self.inner, "LocalExecutor", f)
469 }
470}
471
472impl<'a> LocalExecutor<'a> {
473 /// Creates a single-threaded executor.
474 ///
475 /// # Examples
476 ///
477 /// ```
478 /// use async_executor::LocalExecutor;
479 ///
480 /// let local_ex = LocalExecutor::new();
481 /// ```
482 pub const fn new() -> Self {
483 Self {
484 inner: Executor::new(),
485 _marker: PhantomData,
486 }
487 }
488
489 /// Returns `true` if there are no unfinished tasks.
490 ///
491 /// # Examples
492 ///
493 /// ```
494 /// use async_executor::LocalExecutor;
495 ///
496 /// let local_ex = LocalExecutor::new();
497 /// assert!(local_ex.is_empty());
498 ///
499 /// let task = local_ex.spawn(async {
500 /// println!("Hello world");
501 /// });
502 /// assert!(!local_ex.is_empty());
503 ///
504 /// assert!(local_ex.try_tick());
505 /// assert!(local_ex.is_empty());
506 /// ```
507 pub fn is_empty(&self) -> bool {
508 self.inner().is_empty()
509 }
510
511 /// Spawns a task onto the executor.
512 ///
513 /// # Examples
514 ///
515 /// ```
516 /// use async_executor::LocalExecutor;
517 ///
518 /// let local_ex = LocalExecutor::new();
519 ///
520 /// let task = local_ex.spawn(async {
521 /// println!("Hello world");
522 /// });
523 /// ```
524 pub fn spawn<T: 'a>(&self, future: impl Future<Output = T> + 'a) -> Task<T> {
525 let mut active = self.inner().state().active();
526
527 // SAFETY: This executor is not thread safe, so the future and its result
528 // cannot be sent to another thread.
529 unsafe { self.inner().spawn_inner(future, &mut active) }
530 }
531
532 /// Spawns many tasks onto the executor.
533 ///
534 /// As opposed to the [`spawn`] method, this locks the executor's inner task lock once and
535 /// spawns all of the tasks in one go. With large amounts of tasks this can improve
536 /// contention.
537 ///
538 /// It is assumed that the iterator provided does not block; blocking iterators can lock up
539 /// the internal mutex and therefore the entire executor. Unlike [`Executor::spawn`], the
540 /// mutex is not released, as there are no other threads that can poll this executor.
541 ///
542 /// ## Example
543 ///
544 /// ```
545 /// use async_executor::LocalExecutor;
546 /// use futures_lite::{stream, prelude::*};
547 /// use core::future::ready;
548 ///
549 /// # futures_lite::future::block_on(async {
550 /// let mut ex = LocalExecutor::new();
551 ///
552 /// let futures = [
553 /// ready(1),
554 /// ready(2),
555 /// ready(3)
556 /// ];
557 ///
558 /// // Spawn all of the futures onto the executor at once.
559 /// let mut tasks = vec![];
560 /// ex.spawn_many(futures, &mut tasks);
561 ///
562 /// // Await all of them.
563 /// let results = ex.run(async move {
564 /// stream::iter(tasks).then(|x| x).collect::<Vec<_>>().await
565 /// }).await;
566 /// assert_eq!(results, [1, 2, 3]);
567 /// # });
568 /// ```
569 ///
570 /// [`spawn`]: LocalExecutor::spawn
571 pub fn spawn_many<T: 'a, F: Future<Output = T> + 'a>(
572 &self,
573 futures: impl IntoIterator<Item = F>,
574 handles: &mut impl Extend<Task<F::Output>>,
575 ) {
576 let mut active = self.inner().state().active();
577
578 // Convert all of the futures to tasks.
579 let tasks = futures.into_iter().map(|future| {
580 // SAFETY: This executor is not thread safe, so the future and its result
581 // cannot be sent to another thread.
582 unsafe { self.inner().spawn_inner(future, &mut active) }
583
584 // As only one thread can spawn or poll tasks at a time, there is no need
585 // to release lock contention here.
586 });
587
588 // Push them to the user's collection.
589 handles.extend(tasks);
590 }
591
592 /// Attempts to run a task if at least one is scheduled.
593 ///
594 /// Running a scheduled task means simply polling its future once.
595 ///
596 /// # Examples
597 ///
598 /// ```
599 /// use async_executor::LocalExecutor;
600 ///
601 /// let ex = LocalExecutor::new();
602 /// assert!(!ex.try_tick()); // no tasks to run
603 ///
604 /// let task = ex.spawn(async {
605 /// println!("Hello world");
606 /// });
607 /// assert!(ex.try_tick()); // a task was found
608 /// ```
609 pub fn try_tick(&self) -> bool {
610 self.inner().try_tick()
611 }
612
613 /// Runs a single task.
614 ///
615 /// Running a task means simply polling its future once.
616 ///
617 /// If no tasks are scheduled when this method is called, it will wait until one is scheduled.
618 ///
619 /// # Examples
620 ///
621 /// ```
622 /// use async_executor::LocalExecutor;
623 /// use futures_lite::future;
624 ///
625 /// let ex = LocalExecutor::new();
626 ///
627 /// let task = ex.spawn(async {
628 /// println!("Hello world");
629 /// });
630 /// future::block_on(ex.tick()); // runs the task
631 /// ```
632 pub async fn tick(&self) {
633 self.inner().tick().await
634 }
635
636 /// Runs the executor until the given future completes.
637 ///
638 /// # Examples
639 ///
640 /// ```
641 /// use async_executor::LocalExecutor;
642 /// use futures_lite::future;
643 ///
644 /// let local_ex = LocalExecutor::new();
645 ///
646 /// let task = local_ex.spawn(async { 1 + 2 });
647 /// let res = future::block_on(local_ex.run(async { task.await * 2 }));
648 ///
649 /// assert_eq!(res, 6);
650 /// ```
651 pub async fn run<T>(&self, future: impl Future<Output = T>) -> T {
652 self.inner().run(future).await
653 }
654
655 /// Returns a reference to the inner executor.
656 fn inner(&self) -> &Executor<'a> {
657 &self.inner
658 }
659}
660
661impl<'a> Default for LocalExecutor<'a> {
662 fn default() -> Self {
663 Self::new()
664 }
665}
666
667/// The state of a executor.
668struct State {
669 /// The global queue.
670 queue: ConcurrentQueue<Runnable>,
671
672 /// Local queues created by runners.
673 local_queues: RwLock<Vec<Arc<ConcurrentQueue<Runnable>>>>,
674
675 /// Set to `true` when a sleeping ticker is notified or no tickers are sleeping.
676 notified: AtomicBool,
677
678 /// A list of sleeping tickers.
679 sleepers: Mutex<Sleepers>,
680
681 /// Currently active tasks.
682 active: Mutex<Slab<Waker>>,
683}
684
685impl State {
686 /// Creates state for a new executor.
687 const fn new() -> Self {
688 Self {
689 queue: ConcurrentQueue::unbounded(),
690 local_queues: RwLock::new(Vec::new()),
691 notified: AtomicBool::new(true),
692 sleepers: Mutex::new(Sleepers {
693 count: 0,
694 wakers: Vec::new(),
695 free_ids: Vec::new(),
696 }),
697 active: Mutex::new(Slab::new()),
698 }
699 }
700
701 /// Returns a reference to currently active tasks.
702 fn active(&self) -> MutexGuard<'_, Slab<Waker>> {
703 self.active.lock().unwrap_or_else(PoisonError::into_inner)
704 }
705
706 /// Notifies a sleeping ticker.
707 #[inline]
708 fn notify(&self) {
709 if self
710 .notified
711 .compare_exchange(false, true, Ordering::AcqRel, Ordering::Acquire)
712 .is_ok()
713 {
714 let waker = self
715 .sleepers
716 .lock()
717 .unwrap_or_else(PoisonError::into_inner)
718 .notify();
719 if let Some(w) = waker {
720 w.wake();
721 }
722 }
723 }
724
725 pub(crate) fn try_tick(&self) -> bool {
726 match self.queue.pop() {
727 Err(_) => false,
728 Ok(runnable) => {
729 // Notify another ticker now to pick up where this ticker left off, just in case
730 // running the task takes a long time.
731 self.notify();
732
733 // Run the task.
734 runnable.run();
735 true
736 }
737 }
738 }
739
740 pub(crate) async fn tick(&self) {
741 let runnable = Ticker::new(self).runnable().await;
742 runnable.run();
743 }
744
745 pub async fn run<T>(&self, future: impl Future<Output = T>) -> T {
746 let mut runner = Runner::new(self);
747 let mut rng = fastrand::Rng::new();
748
749 // A future that runs tasks forever.
750 let run_forever = async {
751 loop {
752 for _ in 0..200 {
753 let runnable = runner.runnable(&mut rng).await;
754 runnable.run();
755 }
756 future::yield_now().await;
757 }
758 };
759
760 // Run `future` and `run_forever` concurrently until `future` completes.
761 future.or(run_forever).await
762 }
763}
764
765/// A list of sleeping tickers.
766struct Sleepers {
767 /// Number of sleeping tickers (both notified and unnotified).
768 count: usize,
769
770 /// IDs and wakers of sleeping unnotified tickers.
771 ///
772 /// A sleeping ticker is notified when its waker is missing from this list.
773 wakers: Vec<(usize, Waker)>,
774
775 /// Reclaimed IDs.
776 free_ids: Vec<usize>,
777}
778
779impl Sleepers {
780 /// Inserts a new sleeping ticker.
781 fn insert(&mut self, waker: &Waker) -> usize {
782 let id = match self.free_ids.pop() {
783 Some(id) => id,
784 None => self.count + 1,
785 };
786 self.count += 1;
787 self.wakers.push((id, waker.clone()));
788 id
789 }
790
791 /// Re-inserts a sleeping ticker's waker if it was notified.
792 ///
793 /// Returns `true` if the ticker was notified.
794 fn update(&mut self, id: usize, waker: &Waker) -> bool {
795 for item in &mut self.wakers {
796 if item.0 == id {
797 item.1.clone_from(waker);
798 return false;
799 }
800 }
801
802 self.wakers.push((id, waker.clone()));
803 true
804 }
805
806 /// Removes a previously inserted sleeping ticker.
807 ///
808 /// Returns `true` if the ticker was notified.
809 fn remove(&mut self, id: usize) -> bool {
810 self.count -= 1;
811 self.free_ids.push(id);
812
813 for i in (0..self.wakers.len()).rev() {
814 if self.wakers[i].0 == id {
815 self.wakers.remove(i);
816 return false;
817 }
818 }
819 true
820 }
821
822 /// Returns `true` if a sleeping ticker is notified or no tickers are sleeping.
823 fn is_notified(&self) -> bool {
824 self.count == 0 || self.count > self.wakers.len()
825 }
826
827 /// Returns notification waker for a sleeping ticker.
828 ///
829 /// If a ticker was notified already or there are no tickers, `None` will be returned.
830 fn notify(&mut self) -> Option<Waker> {
831 if self.wakers.len() == self.count {
832 self.wakers.pop().map(|item| item.1)
833 } else {
834 None
835 }
836 }
837}
838
839/// Runs task one by one.
840struct Ticker<'a> {
841 /// The executor state.
842 state: &'a State,
843
844 /// Set to a non-zero sleeper ID when in sleeping state.
845 ///
846 /// States a ticker can be in:
847 /// 1) Woken.
848 /// 2a) Sleeping and unnotified.
849 /// 2b) Sleeping and notified.
850 sleeping: usize,
851}
852
853impl<'a> Ticker<'a> {
854 /// Creates a ticker.
855 fn new(state: &'a State) -> Self {
856 Self { state, sleeping: 0 }
857 }
858
859 /// Moves the ticker into sleeping and unnotified state.
860 ///
861 /// Returns `false` if the ticker was already sleeping and unnotified.
862 fn sleep(&mut self, waker: &Waker) -> bool {
863 let mut sleepers = self
864 .state
865 .sleepers
866 .lock()
867 .unwrap_or_else(PoisonError::into_inner);
868
869 match self.sleeping {
870 // Move to sleeping state.
871 0 => {
872 self.sleeping = sleepers.insert(waker);
873 }
874
875 // Already sleeping, check if notified.
876 id => {
877 if !sleepers.update(id, waker) {
878 return false;
879 }
880 }
881 }
882
883 self.state
884 .notified
885 .store(sleepers.is_notified(), Ordering::Release);
886
887 true
888 }
889
890 /// Moves the ticker into woken state.
891 fn wake(&mut self) {
892 if self.sleeping != 0 {
893 let mut sleepers = self
894 .state
895 .sleepers
896 .lock()
897 .unwrap_or_else(PoisonError::into_inner);
898 sleepers.remove(self.sleeping);
899
900 self.state
901 .notified
902 .store(sleepers.is_notified(), Ordering::Release);
903 }
904 self.sleeping = 0;
905 }
906
907 /// Waits for the next runnable task to run.
908 async fn runnable(&mut self) -> Runnable {
909 self.runnable_with(|| self.state.queue.pop().ok()).await
910 }
911
912 /// Waits for the next runnable task to run, given a function that searches for a task.
913 async fn runnable_with(&mut self, mut search: impl FnMut() -> Option<Runnable>) -> Runnable {
914 future::poll_fn(|cx| {
915 loop {
916 match search() {
917 None => {
918 // Move to sleeping and unnotified state.
919 if !self.sleep(cx.waker()) {
920 // If already sleeping and unnotified, return.
921 return Poll::Pending;
922 }
923 }
924 Some(r) => {
925 // Wake up.
926 self.wake();
927
928 // Notify another ticker now to pick up where this ticker left off, just in
929 // case running the task takes a long time.
930 self.state.notify();
931
932 return Poll::Ready(r);
933 }
934 }
935 }
936 })
937 .await
938 }
939}
940
941impl Drop for Ticker<'_> {
942 fn drop(&mut self) {
943 // If this ticker is in sleeping state, it must be removed from the sleepers list.
944 if self.sleeping != 0 {
945 let mut sleepers = self
946 .state
947 .sleepers
948 .lock()
949 .unwrap_or_else(PoisonError::into_inner);
950 let notified = sleepers.remove(self.sleeping);
951
952 self.state
953 .notified
954 .store(sleepers.is_notified(), Ordering::Release);
955
956 // If this ticker was notified, then notify another ticker.
957 if notified {
958 drop(sleepers);
959 self.state.notify();
960 }
961 }
962 }
963}
964
965/// A worker in a work-stealing executor.
966///
967/// This is just a ticker that also has an associated local queue for improved cache locality.
968struct Runner<'a> {
969 /// The executor state.
970 state: &'a State,
971
972 /// Inner ticker.
973 ticker: Ticker<'a>,
974
975 /// The local queue.
976 local: Arc<ConcurrentQueue<Runnable>>,
977
978 /// Bumped every time a runnable task is found.
979 ticks: usize,
980}
981
982impl<'a> Runner<'a> {
983 /// Creates a runner and registers it in the executor state.
984 fn new(state: &'a State) -> Self {
985 let runner = Self {
986 state,
987 ticker: Ticker::new(state),
988 local: Arc::new(ConcurrentQueue::bounded(512)),
989 ticks: 0,
990 };
991 state
992 .local_queues
993 .write()
994 .unwrap_or_else(PoisonError::into_inner)
995 .push(runner.local.clone());
996 runner
997 }
998
999 /// Waits for the next runnable task to run.
1000 async fn runnable(&mut self, rng: &mut fastrand::Rng) -> Runnable {
1001 let runnable = self
1002 .ticker
1003 .runnable_with(|| {
1004 // Try the local queue.
1005 if let Ok(r) = self.local.pop() {
1006 return Some(r);
1007 }
1008
1009 // Try stealing from the global queue.
1010 if let Ok(r) = self.state.queue.pop() {
1011 steal(&self.state.queue, &self.local);
1012 return Some(r);
1013 }
1014
1015 // Try stealing from other runners.
1016 if let Ok(local_queues) = self.state.local_queues.try_read() {
1017 // Pick a random starting point in the iterator list and rotate the list.
1018 let n = local_queues.len();
1019 let start = rng.usize(..n);
1020 let iter = local_queues
1021 .iter()
1022 .chain(local_queues.iter())
1023 .skip(start)
1024 .take(n);
1025
1026 // Remove this runner's local queue.
1027 let iter = iter.filter(|local| !Arc::ptr_eq(local, &self.local));
1028
1029 // Try stealing from each local queue in the list.
1030 for local in iter {
1031 steal(local, &self.local);
1032 if let Ok(r) = self.local.pop() {
1033 return Some(r);
1034 }
1035 }
1036 }
1037
1038 None
1039 })
1040 .await;
1041
1042 // Bump the tick counter.
1043 self.ticks = self.ticks.wrapping_add(1);
1044
1045 if self.ticks % 64 == 0 {
1046 // Steal tasks from the global queue to ensure fair task scheduling.
1047 steal(&self.state.queue, &self.local);
1048 }
1049
1050 runnable
1051 }
1052}
1053
1054impl Drop for Runner<'_> {
1055 fn drop(&mut self) {
1056 // Remove the local queue.
1057 self.state
1058 .local_queues
1059 .write()
1060 .unwrap_or_else(PoisonError::into_inner)
1061 .retain(|local| !Arc::ptr_eq(local, &self.local));
1062
1063 // Re-schedule remaining tasks in the local queue.
1064 while let Ok(r) = self.local.pop() {
1065 r.schedule();
1066 }
1067 }
1068}
1069
1070/// Steals some items from one queue into another.
1071fn steal<T>(src: &ConcurrentQueue<T>, dest: &ConcurrentQueue<T>) {
1072 // Half of `src`'s length rounded up.
1073 let mut count = (src.len() + 1) / 2;
1074
1075 if count > 0 {
1076 // Don't steal more than fits into the queue.
1077 if let Some(cap) = dest.capacity() {
1078 count = count.min(cap - dest.len());
1079 }
1080
1081 // Steal tasks.
1082 for _ in 0..count {
1083 if let Ok(t) = src.pop() {
1084 assert!(dest.push(t).is_ok());
1085 } else {
1086 break;
1087 }
1088 }
1089 }
1090}
1091
1092/// Debug implementation for `Executor` and `LocalExecutor`.
1093fn debug_executor(executor: &Executor<'_>, name: &str, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1094 // Get a reference to the state.
1095 let ptr = executor.state.load(Ordering::Acquire);
1096 if ptr.is_null() {
1097 // The executor has not been initialized.
1098 struct Uninitialized;
1099
1100 impl fmt::Debug for Uninitialized {
1101 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1102 f.write_str("<uninitialized>")
1103 }
1104 }
1105
1106 return f.debug_tuple(name).field(&Uninitialized).finish();
1107 }
1108
1109 // SAFETY: If the state pointer is not null, it must have been
1110 // allocated properly by Arc::new and converted via Arc::into_raw
1111 // in state_ptr.
1112 let state = unsafe { &*ptr };
1113
1114 debug_state(state, name, f)
1115}
1116
1117/// Debug implementation for `Executor` and `LocalExecutor`.
1118fn debug_state(state: &State, name: &str, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1119 /// Debug wrapper for the number of active tasks.
1120 struct ActiveTasks<'a>(&'a Mutex<Slab<Waker>>);
1121
1122 impl fmt::Debug for ActiveTasks<'_> {
1123 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1124 match self.0.try_lock() {
1125 Ok(lock) => fmt::Debug::fmt(&lock.len(), f),
1126 Err(TryLockError::WouldBlock) => f.write_str("<locked>"),
1127 Err(TryLockError::Poisoned(err)) => fmt::Debug::fmt(&err.into_inner().len(), f),
1128 }
1129 }
1130 }
1131
1132 /// Debug wrapper for the local runners.
1133 struct LocalRunners<'a>(&'a RwLock<Vec<Arc<ConcurrentQueue<Runnable>>>>);
1134
1135 impl fmt::Debug for LocalRunners<'_> {
1136 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1137 match self.0.try_read() {
1138 Ok(lock) => f
1139 .debug_list()
1140 .entries(lock.iter().map(|queue| queue.len()))
1141 .finish(),
1142 Err(TryLockError::WouldBlock) => f.write_str("<locked>"),
1143 Err(TryLockError::Poisoned(_)) => f.write_str("<poisoned>"),
1144 }
1145 }
1146 }
1147
1148 /// Debug wrapper for the sleepers.
1149 struct SleepCount<'a>(&'a Mutex<Sleepers>);
1150
1151 impl fmt::Debug for SleepCount<'_> {
1152 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1153 match self.0.try_lock() {
1154 Ok(lock) => fmt::Debug::fmt(&lock.count, f),
1155 Err(TryLockError::WouldBlock) => f.write_str("<locked>"),
1156 Err(TryLockError::Poisoned(_)) => f.write_str("<poisoned>"),
1157 }
1158 }
1159 }
1160
1161 f.debug_struct(name)
1162 .field("active", &ActiveTasks(&state.active))
1163 .field("global_tasks", &state.queue.len())
1164 .field("local_runners", &LocalRunners(&state.local_queues))
1165 .field("sleepers", &SleepCount(&state.sleepers))
1166 .finish()
1167}
1168
1169/// Runs a closure when dropped.
1170struct CallOnDrop<F: FnMut()>(F);
1171
1172impl<F: FnMut()> Drop for CallOnDrop<F> {
1173 fn drop(&mut self) {
1174 (self.0)();
1175 }
1176}
1177
1178pin_project! {
1179 /// A wrapper around a future, running a closure when dropped.
1180 struct AsyncCallOnDrop<Fut, Cleanup: FnMut()> {
1181 #[pin]
1182 future: Fut,
1183 cleanup: CallOnDrop<Cleanup>,
1184 }
1185}
1186
1187impl<Fut, Cleanup: FnMut()> AsyncCallOnDrop<Fut, Cleanup> {
1188 fn new(future: Fut, cleanup: Cleanup) -> Self {
1189 Self {
1190 future,
1191 cleanup: CallOnDrop(cleanup),
1192 }
1193 }
1194}
1195
1196impl<Fut: Future, Cleanup: FnMut()> Future for AsyncCallOnDrop<Fut, Cleanup> {
1197 type Output = Fut::Output;
1198
1199 fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output> {
1200 self.project().future.poll(cx)
1201 }
1202}
1203
1204fn _ensure_send_and_sync() {
1205 use futures_lite::future::pending;
1206
1207 fn is_send<T: Send>(_: T) {}
1208 fn is_sync<T: Sync>(_: T) {}
1209 fn is_static<T: 'static>(_: T) {}
1210
1211 is_send::<Executor<'_>>(Executor::new());
1212 is_sync::<Executor<'_>>(Executor::new());
1213
1214 let ex = Executor::new();
1215 is_send(ex.run(pending::<()>()));
1216 is_sync(ex.run(pending::<()>()));
1217 is_send(ex.tick());
1218 is_sync(ex.tick());
1219 is_send(ex.schedule());
1220 is_sync(ex.schedule());
1221 is_static(ex.schedule());
1222
1223 /// ```compile_fail
1224 /// use async_executor::LocalExecutor;
1225 /// use futures_lite::future::pending;
1226 ///
1227 /// fn is_send<T: Send>(_: T) {}
1228 /// fn is_sync<T: Sync>(_: T) {}
1229 ///
1230 /// is_send::<LocalExecutor<'_>>(LocalExecutor::new());
1231 /// is_sync::<LocalExecutor<'_>>(LocalExecutor::new());
1232 ///
1233 /// let ex = LocalExecutor::new();
1234 /// is_send(ex.run(pending::<()>()));
1235 /// is_sync(ex.run(pending::<()>()));
1236 /// is_send(ex.tick());
1237 /// is_sync(ex.tick());
1238 /// ```
1239 fn _negative_test() {}
1240}