FerrousPath

Level 4 · Expert· Lesson 7 of 9 · 45 min

Async internals: build an executor

The Future contract, wakers and RawWaker, a leaf future backed by a timer thread, and a complete multi-task executor in a hundred lines.

async/await is syntax over a small, precise protocol. This lesson implements both sides of it — a future that waits for a timer, and an executor that runs many tasks — using only the standard library. After it, Tokio is no longer magic.

The contract

pub trait Future {
    type Output;
    fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output>;
}

Rules every implementation and every caller must respect:

  1. poll must return quickly. It makes whatever progress is possible without blocking.
  2. If it returns Poll::Pending, it must have arranged for cx.waker() — the waker from this call — to be woken when progress becomes possible.
  3. After Poll::Ready, the future must not be polled again.
  4. Spurious polls are allowed: a future must tolerate being polled without having been woken.
  5. Wake-ups may arrive from any thread, at any time, including during poll. A waker is Send + Sync + Clone.

The executor’s side: poll a task when it is woken, and not otherwise.

What async compiles to

async fn add_slowly(a: u32, b: u32) -> u32 {
    let x = step(a).await; // suspension point 1
    let y = step(b).await; // suspension point 2
    x + y
}

async fn step(n: u32) -> u32 { n }

The compiler turns this into, roughly, an enum with one variant per suspension point, each holding the variables that are live across it:

enum AddSlowly {
    Start { a: u32, b: u32 },
    AwaitingFirst { b: u32, fut: Step },
    AwaitingSecond { x: u32, fut: Step },
    Done,
}

poll is a match on the state that polls the inner future, and either returns Pending (staying in the same state) or stores the result and falls through to the next state. Consequences you can now explain:

  • The future’s size is the largest set of locals live across any await — a big array held across an await bloats the whole task.
  • A recursive async fn would have infinite size; it must box (Box::pin) the recursive call.
  • A reference to a local held across an await makes the struct self-referential, hence Pin.
  • The future is Send only if everything held across an await is Send.

A leaf future

Combinators and async blocks only delegate. At the bottom there must be leaf futures that integrate with an event source and call the waker. Real runtimes use a reactor over epoll, kqueue or IOCP. Ours uses a thread:

use std::future::Future;
use std::pin::Pin;
use std::sync::{Arc, Mutex};
use std::task::{Context, Poll, Waker};
use std::thread;
use std::time::Duration;

struct Shared {
    done: bool,
    waker: Option<Waker>,
}

pub struct Sleep {
    shared: Arc<Mutex<Shared>>,
}

impl Sleep {
    pub fn new(duration: Duration) -> Self {
        let shared = Arc::new(Mutex::new(Shared { done: false, waker: None }));
        let for_thread = Arc::clone(&shared);
        thread::spawn(move || {
            thread::sleep(duration);
            let mut s = for_thread.lock().unwrap();
            s.done = true;
            if let Some(waker) = s.waker.take() {
                waker.wake(); // tell the executor: poll that task again
            }
        });
        Sleep { shared }
    }
}

impl Future for Sleep {
    type Output = ();

    fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<()> {
        let mut s = self.shared.lock().unwrap();
        if s.done {
            return Poll::Ready(());
        }
        // Always store the waker from the most recent poll.
        match &s.waker {
            Some(w) if w.will_wake(cx.waker()) => {}
            _ => s.waker = Some(cx.waker().clone()),
        }
        Poll::Pending
    }
}

fn main() {
    // Drive it by hand with a waker that does nothing, to see the protocol.
    let mut sleep = std::pin::pin!(Sleep::new(Duration::from_millis(50)));
    let mut cx = Context::from_waker(Waker::noop());
    println!("first poll:  {:?}", sleep.as_mut().poll(&mut cx));
    thread::sleep(Duration::from_millis(100));
    println!("second poll: {:?}", sleep.as_mut().poll(&mut cx));
}

The lock closes a race: the timer thread sets done and takes the waker under the same mutex in which poll checks done and stores the waker. Without it, the wake-up could fall between the check and the store and be lost forever — the classic lost wake-up.

block_on: the smallest executor

To run one future to completion, poll it, and park the thread until its waker fires:

use std::future::Future;
use std::pin::pin;
use std::sync::Arc;
use std::task::{Context, Poll, Wake, Waker};
use std::thread::{self, Thread};

struct ThreadWaker(Thread);

impl Wake for ThreadWaker {
    fn wake(self: Arc<Self>) {
        self.0.unpark();
    }
}

pub fn block_on<F: Future>(future: F) -> F::Output {
    let mut future = pin!(future);
    let waker = Waker::from(Arc::new(ThreadWaker(thread::current())));
    let mut cx = Context::from_waker(&waker);
    loop {
        match future.as_mut().poll(&mut cx) {
            Poll::Ready(value) => return value,
            Poll::Pending => thread::park(), // sleep until wake() unparks us
        }
    }
}

fn main() {
    let answer = block_on(async {
        let a = async { 40 }.await;
        a + 2
    });
    println!("{answer}");
}

std::task::Wake builds a Waker from an Arc<impl Wake>. Underneath, a Waker is a RawWaker: a data pointer plus a hand-written vtable of four functions (clone, wake, wake_by_ref, drop) — a manual trait object, so that executors can avoid Arc when they need to, as embedded ones do. thread::park tolerates an unpark that arrives first, so there is no lost wake-up here either.

A multi-task executor

Now the real thing: many tasks, a run queue, and spawn. A task owns its future; its waker pushes the task back onto the queue.

use std::future::Future;
use std::pin::Pin;
use std::sync::mpsc::{channel, Receiver, Sender};
use std::sync::{Arc, Mutex};
use std::task::{Context, Poll, Wake, Waker};
use std::thread;
use std::time::{Duration, Instant};

// ---------- the leaf future from above ----------
struct Shared { done: bool, waker: Option<Waker> }
struct Sleep { shared: Arc<Mutex<Shared>> }

impl Sleep {
    fn new(d: Duration) -> Self {
        let shared = Arc::new(Mutex::new(Shared { done: false, waker: None }));
        let t = Arc::clone(&shared);
        thread::spawn(move || {
            thread::sleep(d);
            let mut s = t.lock().unwrap();
            s.done = true;
            if let Some(w) = s.waker.take() { w.wake(); }
        });
        Sleep { shared }
    }
}

impl Future for Sleep {
    type Output = ();
    fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<()> {
        let mut s = self.shared.lock().unwrap();
        if s.done { return Poll::Ready(()); }
        s.waker = Some(cx.waker().clone());
        Poll::Pending
    }
}

// ---------- the executor ----------
type BoxFuture = Pin<Box<dyn Future<Output = ()> + Send>>;

struct Task {
    /// `None` once the future has completed.
    future: Mutex<Option<BoxFuture>>,
    /// Where to send this task when it is woken.
    queue: Sender<Arc<Task>>,
}

impl Wake for Task {
    fn wake(self: Arc<Self>) {
        // Waking = scheduling. If the executor is gone, there is nothing to do.
        let _ = self.queue.send(Arc::clone(&self));
    }
}

#[derive(Clone)]
struct Spawner {
    queue: Sender<Arc<Task>>,
}

impl Spawner {
    fn spawn(&self, future: impl Future<Output = ()> + Send + 'static) {
        let task = Arc::new(Task {
            future: Mutex::new(Some(Box::pin(future))),
            queue: self.queue.clone(),
        });
        self.queue.send(task).expect("executor is running");
    }
}

struct Executor {
    ready: Receiver<Arc<Task>>,
}

fn new_executor() -> (Executor, Spawner) {
    let (queue, ready) = channel();
    (Executor { ready }, Spawner { queue })
}

impl Executor {
    /// Runs until every task has finished and every Spawner and Waker has been dropped.
    fn run(&self) {
        while let Ok(task) = self.ready.recv() {
            let mut slot = task.future.lock().unwrap();
            if let Some(mut future) = slot.take() {
                let waker = Waker::from(Arc::clone(&task));
                let mut cx = Context::from_waker(&waker);
                if future.as_mut().poll(&mut cx).is_pending() {
                    *slot = Some(future); // not done: keep it for the next wake-up
                }
                // If Ready, the future is dropped here and the task is finished.
            }
        }
    }
}

fn main() {
    let (executor, spawner) = new_executor();
    let start = Instant::now();

    for id in 1..=3u64 {
        let inner = spawner.clone();
        spawner.spawn(async move {
            println!("[{:>3} ms] task {id} started", start.elapsed().as_millis());
            Sleep::new(Duration::from_millis(100 * id)).await;
            println!("[{:>3} ms] task {id} woke up", start.elapsed().as_millis());
            if id == 3 {
                // Tasks can spawn tasks.
                inner.spawn(async move {
                    Sleep::new(Duration::from_millis(50)).await;
                    println!("[{:>3} ms] child of task 3 done", start.elapsed().as_millis());
                });
            }
        });
    }

    drop(spawner); // so `run` can end once all tasks are done
    executor.run();
    println!("all tasks finished in {} ms on one thread", start.elapsed().as_millis());
}

Run it: three tasks sleep concurrently on a single executor thread, and the total is about 350 ms rather than the 650 ms a sequential run would need.

How termination works: the channel closes when every Sender is gone. Senders live in the Spawners and inside each Task — and a task stays alive only while it sits in the queue or some Waker (held by a timer thread) refers to it. When the last task completes, the last sender drops, recv returns Err, and run exits. Ownership does the bookkeeping.

From this to Tokio

Everything a production runtime adds is refinement of the pieces above:

Our executor A production runtime
One thread draining an mpsc channel A pool of worker threads, each with a local queue, stealing work from each other
Mutex<Option<BoxFuture>> per task One allocation holding header, future and output, with an atomic state word (idle / scheduled / running / complete) so that a wake during poll re-schedules exactly once
A thread per timer A reactor: one epoll/kqueue/IOCP call waiting on all sockets, plus a hierarchical timer wheel; it stores wakers keyed by event source
No JoinHandle The task’s output slot plus a second waker for whoever awaits the handle
Tasks run until they yield Cooperative budgeting: a task that has done too much work is forced to yield so others are not starved
Send futures only LocalSet / current-thread runtimes for !Send futures

Design questions you can now reason about: Why must spawned futures be 'static? (The task outlives the spawning stack frame.) Why is wake() required to be cheap and non-reentrant? (It may be called from an interrupt handler or from inside poll.) Why do select! and join! on many futures re-poll all of them on any wake-up, and why does FuturesUnordered give each child its own waker instead?

Exercises

  1. Add a JoinHandle<T> to the executor: spawn returns a future that resolves to the task’s output. You need a shared slot with Option<T> and Option<Waker>.
  2. Write async fn yield_now() — a future that returns Pending once after calling cx.waker().wake_by_ref(). Use it to show two tasks interleaving.
  3. Replace the thread-per-Sleep with one timer thread holding a BinaryHeap<(Instant, Waker)> — a miniature reactor.
  4. Make the executor multi-threaded: share the receiver behind a Mutex among four worker threads. What must change so a task woken while it is being polled is not polled concurrently or lost?
  5. Implement a RawWaker vtable by hand for the block_on thread waker, without Arc.

Check your understanding

Pick an answer to see the explanation.

  1. 1.What must a future do before returning Poll::Pending?

  2. 2.Why should a leaf future store the *latest* waker on every poll rather than only the first?

  3. 3.In the executor from this lesson, what does wake() do?

Key terms in this lesson

Finished the lesson and the exercises?