Skip to main content

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}