Async — futures as state machines

Lesson 17 left one cost standing: every thread owns a stack and a place in the operating system's scheduler, so a server with ten thousand idle connections pays for ten thousand of them just to wait. This lesson compiles the pause into the code instead. An async fn becomes a state machine — a value that records which .await it stopped at and holds the locals still live there — and an ordinary library function drives such values on one thread. One new rule, pinning, makes the machine sound, because a paused function may hold references into itself. What it buys is waiting that costs bytes instead of threads, with no run-time system in the language; what it costs is a second dialect of Rust.

1 · The cost of waiting with threads

Picture a chat server with ten thousand open connections, of which perhaps a dozen have a message at any moment; the rest wait for their client to type. The simplest design is Lesson 17's: a thread per connection, looping read, handle, write and blocking in read. The code is straight-line and the borrow checker is content. The bill is in the threads.

Lesson 17 priced that unit: a standard-library thread is one operating-system thread with its own stack, 2 MiB by default for a spawned thread on Tier-1 platforms (the docs call the figure subject to change). Ten thousand connections ask for 20,000 MiB of stack (10,000 × 2 MiB) and ten thousand entries in the scheduler, almost all of them doing nothing. A stack is sized for the deepest call the thread might ever make; a waiting connection needs only the few values it will use when its data arrives.

So the goal is sharper than "fewer threads". We want a computation that can pause: stop in the middle of a function, give the thread back, and later continue from the same point with the same locals, on whatever thread is free. There are three ways to build one.

The third road is to compile the pause into the code: the compiler rewrites the function into a value that remembers where it stopped and which locals it still needs, and resuming it is a method call. No stack per task, no scheduler in the language; whoever holds the value decides when to resume it. So now we need to know exactly what that value must contain.

2 · Derive the state machine by hand

Take the smallest handler with two waits. It creates a 64-byte buffer for a request header, waits for the header, parses it, then creates a 1,024-byte buffer for the body, waits again, and reads the body. To pause at a wait the function must return to its caller; to resume, it must jump back to the statement after that wait with every local it will still use. Which locals are those? The ones live at the wait — used later on some path — the backward liveness Lesson 07 computes for borrows, now asked at the waits. At the first wait header is live; at the second only body is, because the header was last used before it.

So the paused function is a value with a tag — the number of the wait it is stopped at — and, for each wait, just the locals live there: an enum with one variant per wait, plus one for "not started" (Lesson 09). Written by hand, with std's two-case enum Poll (Ready(value) or Pending) as the result:

use std::task::Poll;
struct Buf<const N: usize> { bytes: [u8; N] }

enum Handler {                          // one variant per point where the body can stop
    Start,
    AtHeader { header: Buf<64> },       // stopped at wait 1: header is still needed
    AtBody { body: Buf<1024> },         // stopped at wait 2: only body is
}
impl Handler {
    fn resume(&mut self) -> Poll<u8> {  // run to the next wait; keep only what is live
        match self {
            Handler::Start => *self = Handler::AtHeader { header: Buf { bytes: [1; 64] } },
            Handler::AtHeader { header } => {
                let _kind = header.bytes[0];            // the last use of header
                *self = Handler::AtBody { body: Buf { bytes: [2; 1024] } };
            }
            Handler::AtBody { body } => return Poll::Ready(body.bytes[0]),
        }
        Poll::Pending
    }
}
fn main() {
    let mut h = Handler::Start;
    while h.resume().is_pending() { println!("suspended"); }
    println!("size_of::<Handler>() = {}", std::mem::size_of::<Handler>());
}

suspended
suspended
size_of::<Handler>() = 1025

Each call to resume runs from where the last one stopped to the next wait, stores what the rest of the function needs in the next variant, and returns Pending; when the body finishes it returns Ready. The machine is 1,025 bytes: one byte of tag plus the largest variant. The header and the body are never stored at the same time, so they share bytes.

Rust's syntax for writing the handler straight-line is async fn, with .await marking each point where it may pause; the compiler derives the enum. Calling an async fn runs none of its body — it returns the machine as a value — so size_of_val can weigh it. Below, tick() stands in for any operation that may have to wait (§3 writes a real one), and read for parsing:

struct Buf<const N: usize> { bytes: [u8; N] }
fn read(_byte: u8) {}
fn tick() -> std::future::Ready<()> { std::future::ready(()) }

async fn handler() {                  // header, then body
    let header = Buf { bytes: [1; 64] };
    tick().await;                     // live here: header
    read(header.bytes[0]);
    drop(header);                     // header's storage ends
    let body = Buf { bytes: [2; 1024] };
    tick().await;                     // live here: body
    read(body.bytes[0]);
}
async fn both() {                     // both needed across the same await
    let header = Buf { bytes: [1; 64] };
    let body = Buf { bytes: [2; 1024] };
    tick().await;                     // live here: header and body
    read(header.bytes[0]);
    read(body.bytes[0]);
}
fn main() {
    println!("handler: {} bytes", std::mem::size_of_val(&handler()));
    println!("both:    {} bytes", std::mem::size_of_val(&both()));
}

handler: 1026 bytes
both:    1090 bytes

The compiler's machine is 1,026 bytes: the tag plus the larger state — the 1,024-byte body and one byte more, because a state also holds the future it is waiting on (tick()'s one-byte future). When both buffers are live across one wait, that state holds both: 1,090 = 1 + 64 + 1,024 + 1. The size tracks the largest set of locals held across one wait, not the number of locals, and it is fixed at compile time: a future is an ordinary value that can sit in a queue with ten thousand others. One line in handler matters more than it looks, drop(header); §4 shows why.

Holding the future it awaits has one more consequence: a function that awaits itself would contain itself, a value of infinite size (Lesson 03's recursive type without a Box), so rustc rejects a directly recursive async fn with E0733 until the recursive call is boxed with Box::pin (§6 explains the "pin").

We have the value. Now we need the method every executor can call on every such value — what the hand-written resume becomes when it must work for machines nobody wrote by hand.

3 · The Future trait: poll, Pending, and the waker

Three requirements turn resume into the standard library's Future trait. It must never block: if the awaited event has not happened, it returns at once so the thread can run something else — hence Poll::Pending. It must tell whoever runs it when trying again is worthwhile, or an executor would poll everything forever — hence a Context carrying a waker. And it must be called on a machine that will not move, for a reason §6 derives — hence self: Pin<&mut Self>. Here is std's definition, copied:

use std::pin::Pin;
use std::task::{Context, Poll};

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

The contract, as the std docs state it: poll tries to finish without blocking; if it cannot, it returns Pending after arranging a wake-up — it keeps a clone of the Waker from the Context and calls wake when its event happens, and the executor then polls it again. The Waker is how a future reaches whatever runs it: poll me again, something changed.

.await is a poll in a loop. In the Reference's description: pin the operand and poll it with the current task's context; on Ready(v) the expression's value is v; on Pending the enclosing future itself returns Pending, and when it is polled again it resumes at this same .await. So Pending travels outward to the executor, resumption travels back inward, and nothing runs until someone polls. Here is a real Tick and a handler, polled by hand:

use std::pin::{Pin, pin};
use std::task::{Context, Poll, Waker};
struct Tick(bool);                               // not ready once, then ready
impl Future for Tick {
    type Output = ();
    fn poll(mut self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<()> {
        if self.0 { return Poll::Ready(()); }
        self.0 = true;
        cx.waker().wake_by_ref();                // "poll me again"
        Poll::Pending
    }
}
async fn handler() {
    println!("  body: start");
    Tick(false).await;
    println!("  body: resumed");
}
fn main() {
    let mut fut = pin!(handler());               // creating it prints nothing
    println!("created");
    let mut cx = Context::from_waker(Waker::noop());
    while fut.as_mut().poll(&mut cx).is_pending() { println!("poll returned Pending"); }
    println!("poll returned Ready");
}

created
  body: start
poll returned Pending
  body: resumed
poll returned Ready

Creating the future printed nothing: futures are lazy, and the compiler warns about one you create and never use. The body started at the first poll, and the Tick that was not ready made the whole handler return Pending, to resume exactly there on the next poll. Waker::noop() is a waker that does nothing, acceptable only because this loop polls regardless; pin! fixes the future in place (§6). Everything so far is two hand-picked bodies. The claim of §2, that a state holds what is live at its wait, should hold for any body, so we need a way to try bodies and compare with rustc.

4 · Build the state machine

The widget takes the body of an async fn in five kinds of statement, runs Lesson 07's backward liveness at every .await to find what each state saves, and lays those values out the way rustc 1.98.1 does. Every program it accepts is real Rust, given §2's Buf, read and tick and any function look that takes a &Buf<N>:

names.forEach(function (v) { var x = L[v]; x.end = (x.drop >= 0 && x.borrow < 0) ? x.drop : n; });
// Saved across await k: storage still live, and used after k (liveness) or borrowed before k (rule 3).
function savedAt(x, k) { return x.def < k && k < x.end && (x.last > k || (x.borrow >= 0 && x.borrow < k)); }
// …
// Rule 1: saved in two or more states -> the prefix every state shares.
items.forEach(function (it) { it.home = null; it.why = ''; });
states.forEach(function (st, j) {
  st.fields.forEach(function (it) {
    if (it.home === null) it.home = j;
    else if (it.home !== 'prefix') { it.home = 'prefix'; it.why = 'saved in two or more states'; }
  });
});
// …
// Rule 2: two values of different states whose storage overlaps cannot share bytes; rustc moves
// the one whose storage overlaps more values (on a tie, the later one) to the prefix.
function overlap(a, b) { return a.lo <= b.hi && b.lo <= a.hi; }
function degree(a) { return items.filter(function (b) { return overlap(a, b); }).length; }
items.forEach(function (a) {
  if (a.home === 'prefix') return;
  items.forEach(function (b) {
    if (!overlap(a, b) || b.home === 'prefix' || a.home === b.home) return;
    var loser = degree(a) > degree(b) ? a : b, other = loser === a ? b : a;
    if (loser.home !== 'prefix') { loser.home = 'prefix'; loser.why = 'storage overlaps ' + other.name + ', in another state'; }
  });
});

What to try. The first preset is §2's handler, statement for statement. Drag the slider up from 1. The first await makes a state, but header is saved only once use header arrives (a value is saved at a wait if something after the wait uses it), so the size goes 1, 2, 66, and at seven statements 1,026: the lower bound, the state byte plus the largest state, as if every state overlapped perfectly. "The same, header never dropped" has the same live values, yet its size is 1,090: header's storage runs to the closing brace while body exists, so they cannot share bytes and header moves to the prefix. "One buffer across two awaits" puts session in the prefix (a value needed in two states keeps one address): 290 bytes. "Borrowed, then dropped" is 1,090 although the header is dropped before the second wait; delete borrow header; and it falls to 1,026.

In practice: to keep a future small, end big values before the next .await, and give them a block to do it, since a move does not end the storage of a value that was ever borrowed. What the widget cannot show is who calls poll, and how that caller knows when.

5 · The executor is a library

Something has to call poll. In §3 it was a loop in main polling flat out; a real executor must sleep while nothing can make progress and wake exactly when a waker is called. The standard library's Wake trait turns any Arc<W> with a wake method into a Waker, and thread parking supplies the sleep. That is the whole executor:

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

struct Unpark(Thread);                            // to wake = to unpark the executor's thread
impl Wake for Unpark { fn wake(self: Arc<Self>) { self.0.unpark(); } }

fn block_on<F: Future>(fut: F) -> F::Output {     // the whole executor: a library function
    let mut fut = pin!(fut);
    let waker = Waker::from(Arc::new(Unpark(thread::current())));
    let mut cx = Context::from_waker(&waker);
    loop {
        if let Poll::Ready(out) = fut.as_mut().poll(&mut cx) { return out; }
        println!("executor: Pending, parking");
        thread::park();                           // sleep until some waker unparks us
    }
}

struct Tick(bool);                                // Pending once; the wake comes from elsewhere
impl Future for Tick {
    type Output = ();
    fn poll(mut self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<()> {
        if self.0 { return Poll::Ready(()); }
        self.0 = true;
        let waker = cx.waker().clone();
        thread::spawn(move || waker.wake());      // another thread says "try again"
        Poll::Pending
    }
}
fn main() {
    let n = block_on(async { Tick(false).await; 1024 });
    println!("task finished: {n}");
}

executor: Pending, parking
task finished: 1024

block_on pins the future, builds a waker whose wake unparks the executor's thread, and loops: poll; on Pending, park until woken; on Ready, return. The helper thread in Tick stands in for whatever eventually reports that the data is there; the point is that someone else calls wake, possibly from another thread, which is why Waker is Send and Sync. The standard library provides the trait, the waker machinery, pin! and the syntax, but no executor. That is why async fn main is rejected (E0752) unless a runtime's macro rewrites it into an ordinary main. As the Book puts it, Rust does not bundle an async runtime: you choose one, and runtimes such as Tokio are ordinary crates.

From one future to ten thousand is the same loop with a ready queue. A multi-task executor holds many futures, called tasks; a task's waker, when called, puts that task on the queue; the loop takes a ready task, polls it once, and parks when the queue is empty. Ten thousand idle connections are then ten thousand suspended state machines — each a state byte plus its largest state, 1,026 bytes for §2's toy handler — and one thread asleep until a waker fires. That answers the question we inherited: many tasks wait without a thread each, and the language ships no runtime, because the runtime is whichever library you called. But block_on did one thing without comment: it pinned the future before polling it.

6 · Why Pin

Borrowing across an .await is ordinary code: read into a buffer, keep a reference into it, wait for more. Here is the smallest version, and the obvious way to get the Pin<&mut _> that poll demands:

use std::pin::Pin;

async fn tick() {}

async fn parse() -> u8 {
    let buf = [7u8; 16];
    let cursor = &buf;                // a reference to another local of this future...
    tick().await;                     // ...held across an await
    cursor[0]
}

fn main() {
    let mut fut = parse();
    let pinned = Pin::new(&mut fut);  // Pin::new is only for Unpin types
}

error[E0277]: `{async fn body of parse()}` cannot be unpinned
  --> src/main.rs:14:27
   |
14 |     let pinned = Pin::new(&mut fut);  // Pin::new is only for Unpin types
   |                  -------- ^^^^^^^^ within `impl Future<Output = u8>`, the trait `Unpin` is not implemented for `{async fn body of parse()}`
   |                  |
   |                  required by a bound introduced by this call
   |
   = note: consider using the `pin!` macro
           consider using `Box::pin` if you need to access the pinned value outside of the current scope

Why refuse? At that .await, buf and cursor are both live, so both are fields of the same state — and cursor's value is the address of buf, a field of the very same value. The future points into itself. Lesson 08's side box built such a struct by hand and found it could be used where it was built but never moved, because a move copies bytes and changes the address the reference assumed. Here the compiler writes the struct for you, and a future must move at least once (the function that creates it returns it), so "never move" is too strong. If a started future could move — swapped, or pushed into a Vec that reallocates — cursor would keep the old address. In C++, where the default copy copies the pointer and not what it meant:

struct Parser {
    char buf[16] = "GET /";
    char* cursor = buf;              // points into this very object
};
std::vector<Parser> v(1);
v.push_back(Parser{});               // may reallocate: v[0] moves to a new buffer...
*v[0].cursor = 'P';                  // ...but its cursor still points at the old one

What could the language do? Forbid borrows across .await, and parse above stops compiling. Put every borrowed-across local on the heap, and each such wait costs a hidden allocation, against the budget. Fix the pointers when the value moves, as a C++ move constructor could — but a Rust move is a plain copy of bytes that runs no code (Lesson 04). Track it in lifetimes — but the borrow's region, which the source calls its lifetime, now reaches past a suspension into a value that can move, and no lifetime names "the address of my own field". What is left is a promise: once a future has been polled, it will not move again until it is dropped. Before the first poll it holds no self-references, so moving it is fine.

Pin is that promise attached to a pointer. In the std docs' terms, a Pin<&mut T> or Pin<Box<T>> guarantees that the pointee will not be moved or otherwise invalidated until it is dropped — provided T is not Unpin. It is not compiler magic: it withholds safe access to &mut T, which is all mem::swap would need to move the value, and since poll takes self: Pin<&mut Self>, nobody polls a future without having made the promise. Unpin is an auto trait for types that do not care where they live — almost every type — and the compiler marks every future made from async code as not Unpin, because it may hold references into itself. That is the error above: Pin::new makes no promise, so it takes only Unpin types. The note names two ways that do — pin on the heap, or in the current frame:

use std::pin::{Pin, pin};
async fn tick() {}
async fn parse() -> u8 { let buf = [7u8; 16]; let cursor = &buf; tick().await; cursor[0] }

fn main() {
    let on_heap: Pin<Box<_>> = Box::pin(parse());   // pinned on the heap
    let on_stack = pin!(parse());                   // pinned in this frame
    let mut count = 0;
    let ordinary = Pin::new(&mut count);            // fine: i32 is Unpin
}

Either way the pointee stays put while the pointer — the Box, or the pinned handle — moves freely; for an Unpin type such as i32, Pin is a plain wrapper. The mechanism is now complete: a state machine, a loop that polls it, and a promise that it stays put. What is left is the bill.

7 · What async costs

Two colours of function. An async fn can be awaited only from async code; ordinary code can call it, but gets back an inert value that something must poll. Nystrom's 2015 essay What Color is Your Function? named the split: every function has a colour, a red (async) function can be called only from a red one, and async/await makes the calls easier but still divides the world in two. In Rust the first symptom is a compile error:

async fn tick() {}

fn handler() {
    tick().await;                     // an ordinary fn cannot pause
}

The bridge from sync to async is an executor (block_on, §5).

Send is decided by the saved state. An executor that may move tasks between threads demands F: Send, and Lesson 16's structural rule applies to the state machine's fields: a future is Send only if everything it holds across an .await is — exactly the saved values the widget draws. Hold an Rc across a wait and the whole future is not Send:

use std::rc::Rc;

fn spawn<F: Future + Send + 'static>(_task: F) {}   // an executor that may move tasks between threads
async fn tick() {}

fn main() {
    spawn(async {
        let visits = Rc::new(0);          // Rc is not Send
        tick().await;                     // ...and it is held across this await
        println!("{visits}");
    });
}

error: future cannot be sent between threads safely
note: future is not `Send` as this value is used across an await
  --> src/main.rs:9:16
   |
 8 |         let visits = Rc::new(0);          // Rc is not Send
   |             ------ has type `Rc<i32>` which is not `Send`
 9 |         tick().await;                     // ...and it is held across this await
   |                ^^^^^ await occurs here, with `visits` maybe used later
note: required by a bound in `spawn`

The obvious local edit — drop(visits) after the println! and before the wait — is still rejected on this compiler. It is §4's rule 3 again: println! borrowed visits, and a value that was ever borrowed stays in the future until its scope ends, whatever you drop. A block ends the scope:

use std::rc::Rc;

fn spawn<F: Future + Send + 'static>(_task: F) {}
async fn tick() {}

fn main() {
    spawn(async {
        {
            let visits = Rc::new(0);
            println!("{visits}");
        }                                 // visits' scope ends before the await
        tick().await;
    });
}

Blocking stalls everyone. An executor thread runs one task's poll at a time, and nothing preempts it: a task that blocks inside poll — a synchronous file read, thread::sleep, a long computation — blocks every other task on that thread. The std docs ask that poll return quickly and send long work to a thread pool; a rule of thumb from a blog post by Ryhl is roughly 10 to 100 microseconds between .awaits. Async saves the memory and the thread switches of waiting; it does not make work faster.

Cancellation is drop. A future does nothing unless polled, so to cancel one you stop polling it and drop it. Dropping a suspended state machine drops the values saved in its current state, at that .await, and the code after it never runs:

use std::future::pending;
use std::task::{Context, Waker};

struct Conn(&'static str);                        // says when it is dropped
impl Drop for Conn { fn drop(&mut self) { println!("drop {}", self.0); } }
async fn handler() {
    let _conn = Conn("conn");
    pending::<()>().await;                        // suspended here, for good...
    println!("never printed");
}
fn main() {
    let mut fut = Box::pin(handler());
    let _ = fut.as_mut().poll(&mut Context::from_waker(Waker::noop()));
    println!("cancel");
    drop(fut);                                    // ...and dropped: conn's drop runs now
}

cancel
drop conn

That is clean — the future simply stops being polled, and destructors run (RAII at work) — and it is a new failure mode: every .await is a point where your function may silently stop. Code that must finish two steps together, such as writing a record and then its index, cannot assume the second step runs.

"Zero-cost", precisely. The state machine needs no allocation, no thread and no run-time system you did not choose, and its size is a compile-time constant. That is all zero-cost means here. The concepts are not free (colouring, pinning, Send bounds, cancellation points), and the layout is not optimal (§4's rules, the doubled arguments).

Common mistakes / failure modes

Checkpoint exercise

Where this points next

We answered with a value instead of a thread: a future is a compiler-built state machine, an executor is a library loop, and ten thousand futures wait on one sleeping thread. But count what we trusted. .await pins its operand with Pin::new_unchecked, an unsafe function (the Reference's description): a promise the checker does not verify. A Waker can be built from raw pointers and a hand-written table of functions. And long before this lesson, Rc, RefCell, Mutex and Vec counted owners, handed out exclusive access through a shared handle and reallocated buffers, none of it visible to the borrow checker. Each is a library type whose soundness someone asserted and the checker did not prove. So what is inside those types, what exactly is the compiler taking on trust, and who checks it?

Interview prompts

• What does an async fn compile to, and how big is it? (§2 — an anonymous state machine: a tag for the .await it is stopped at, plus the locals live there and the future it awaits; its size, fixed at compile time, is the largest state plus the tag.)
• Why is a future lazy, and what does .await do? (§3 — nothing runs until something calls poll; .await polls the inner future and, on Pending, makes the enclosing future return Pending, resuming at the same point next time.)
• What is a Waker for? (§3, §5 — a Pending future keeps a clone and calls wake when its event happens, so the executor re-polls that task instead of everything; it is Send and Sync because the wake may come from any thread.)
• Does Rust have a built-in async runtime? (§5 — no: std provides the trait, the waker types, pin! and the syntax; executors are library code, runtimes like Tokio are crates, and async fn main is rejected without one.)
• What does Pin guarantee, and why do futures need it? (§6 — that a pointee which is not Unpin is not moved until dropped; a started future may hold a reference into its own state, and a Rust move cannot run fix-up code.)
• When is a future Send, and how do you fix "future cannot be sent between threads safely"? (§7 — when everything it holds across an .await is Send; end the value's scope with a block before the await — a drop after a borrow does not count — or use a Send type.)
• Why is blocking inside async code a bug, and is async faster than threads? (§7 — a blocked poll stalls every task on its executor thread; async saves the stack and switch of waiting tasks, not the work.)
• How do you cancel a future, and what runs? (§7 — drop it: the values saved in its current state are dropped at that .await and the rest never runs, so every .await is a possible exit.)

Companion reads: Go · 08 Goroutines and the scheduler (the road with a run-time system), Go · 10 select and context (cancellation made explicit), C++ · 17 Threads (OS threads, each with its own stack: the baseline), and FP · 13 Laziness and streams (work described as a value until forced).