Futures as Write-Once Cells: Polling, Waking, and Cancellation

A future is a value representing a computation that may not have finished. The representation is not a thread waiting on a condition variable, and it is not a callback registered somewhere in the runtime. It is a state machine with a single transition from pending to ready, plus a place to put the result. Everything else about futures follows from the fact that this cell is written at most once.

The write-once rule is what makes a future shareable without a lock in the common case, and it is what makes “who gets the value” unambiguous: the first observer of the ready state sees it, and all later observers see the same value. It is also why cancellation cannot be expressed as “write a different value” and needs its own mechanism.

The three states and the handoff between them

Inside a future’s shared cell there is a state word and, once ready, a result. The state is one of pending, ready, or consumed: a small enum, usually packed into an atomic integer alongside flags. A completer (a timer, an I/O completion, another task’s join) transitions pending to ready and stores the result. A consumer transitions ready to consumed and takes the result. Fewer than three states is not enough: with only pending and ready, either the result is written before the flag flips, and a consumer can observe the flag before the bytes, or the flag flips first and the consumer takes a cell that is still empty.

Because the transition is a compare-and-swap on a single word, two completers racing produce exactly one winner and one no-op, and two consumers racing produce one value and one None. The absent case is not an error: it means the future was already taken.

The interesting case is the reverse race, a consumer polling at the same moment the completer fires. If the consumer’s poll sees pending and registers interest, and the completer’s transition happens just after, the consumer must be woken or it will sleep forever on a completed future. The waker protocol exists to close exactly that window, and it closes in one of two ways: the completer loads the registered waker while holding the same lock it uses to flip the state, so a completer that publishes the state always has a waker to call; or the registering side stores the waker first and then re-loads the state, calling the waker itself if the completion has already landed. The illustration below takes the second route.

This is why a future that never registers a waker is not merely inefficient. It is correct only if the executor polls it in a loop, and an executor built around blocking on a readiness queue does not.

Poll is a non-blocking probe with a contract

The poll interface is deliberately narrow: poll returns Ready with the output, or Pending and arranges that the current task be woken when progress becomes possible. The contract has three parts, and all three are load-bearing.

First, poll must not block. An implementation that performs a blocking read inside poll stalls the executor thread that called it, and since that thread multiplexes many tasks, the stall is not local. The I/O layer therefore has to be non-blocking and report “would block” as pending, which is why async I/O is inseparable from the readiness APIs of the platform.

Second, a future that returns pending must have registered a waker. Registering after the check is a lost-wakeup bug; the order is check, then register, or register and then check under the same lock.

Third, poll after completion may panic or return the same value; implementations differ, and code should not rely on the second poll. This is the future-side analogue of the consumed state above.

use std::future::Future;
use std::pin::Pin;
use std::sync::atomic::{AtomicU8, Ordering};
use std::sync::{Arc, Mutex};
use std::task::{Context, Poll, Waker};

const PENDING: u8 = 0;
const READY: u8 = 1;
const TAKEN: u8 = 2;

struct Cell<T> { state: AtomicU8, value: Mutex<Option<T>>, waker: Mutex<Option<Waker>> }

impl<T> Cell<T> {
    fn complete(&self, v: T) {
        let mut slot = self.value.lock().unwrap(); // held across the flip
        if self.state.compare_exchange(PENDING, READY, Ordering::Release, Ordering::Relaxed).is_err() {
            return; // a second completion loses the race and does nothing
        }
        *slot = Some(v);
        drop(slot);
        if let Some(w) = self.waker.lock().unwrap().take() { w.wake(); }
    }
}

The consumer side is a Future over an Arc of that cell; it takes the value at most once and reports None on every later poll.

struct Wait<T>(Arc<Cell<T>>);

impl<T> Future for Wait<T> {
    type Output = Option<T>;

    fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Option<T>> {
        let cell = &self.0;
        match cell.state.load(Ordering::Acquire) {
            READY => {
                cell.state.store(TAKEN, Ordering::Relaxed);
                Poll::Ready(cell.value.lock().unwrap().take())
            }
            TAKEN => Poll::Ready(None),
            _ => {
                // Register, then re-check: a completion that landed in between wakes us here.
                *cell.waker.lock().unwrap() = Some(cx.waker().clone());
                if cell.state.load(Ordering::Acquire) == READY { cx.waker().wake_by_ref(); }
                Poll::Pending
            }
        }
    }
}

The orderings in those blocks are each doing work. The compare-and-swap publishes READY with a release store and the consumer’s acquire load pairs with it; the result itself is written while the completer holds the value lock across that swap, so a consumer that observes READY and then takes the lock cannot see the flag before the value. The re-check after registration closes the window where a completion lands between the load and the registration.

A future written without persisted state of this kind is either one that completes on the first poll or one that loses its place between polls, and every suspension point in an async function becomes a variant of such a machine in the compiler’s desugaring.

Why the waker is a trait object and not a channel

A waker is a handle that can schedule the task that owns the future. It carries a raw pointer to executor-specific data plus a vtable, so waking is a virtual call and nothing more. A per-wake allocation would be unacceptable at the message rates that async runtimes target: a task that is woken once per incoming packet would allocate once per packet, and the allocator would become the throughput limit.

Wakers are cloneable and reference counted because a future may register the same waker with several sources, a read and a timeout for instance. Whichever fires first wakes the task; the others may still hold a clone and will wake it again later, which must be harmless. That requirement, “a spurious wake is safe”, is why poll must be idempotent in the pending direction: an executor may poll a task whose readiness has since been consumed by another source, and the task must simply re-check.

The executor side is a queue of woken tasks plus worker threads that drain it. Nothing in the future knows which thread will poll it next, and in a work-stealing executor it may be a different thread each time. That is the reason a future’s state must be safe to move between threads and why the compiler’s state machines are Send only when every held value is.

Cancellation is a drop, not a message

Because a future is a value, cancelling it means dropping it. No signal is sent, no flag is checked, and the future is not asked to stop; its destructor runs, and any partially completed work is simply abandoned. That is a strong and unusual property: cancellation is immediate and cannot be refused.

The cost is that the abandoned future may have left side effects in an intermediate state. A send that reached the socket but whose acknowledgement was never read, a lock guard released mid-protocol, a partially written buffer; none of these are visible to the dropper. This is the cancel-safety problem, and it is the reason library APIs are classified as cancel-safe or not: a select-like combinator that polls several futures and takes the first to complete will drop the losers, so the losers must tolerate being dropped at any await point. The discipline required to write such code is treated in Cooperative Cancellation and the Cancel-Safety Contract.

Timeouts are the common case. A timeout combinator holds the inner future, polls it, and also polls a timer; if the timer wins, the inner future is dropped where it stood. This composes well because drop is deterministic in the language’s ownership model, since the future’s locals are dropped in reverse declaration order, but it composes badly with resources whose release requires an acknowledgement from the other side, since the drop cannot wait.

What the cell cannot express

The write-once cell has no notion of progress, so a future cannot report “40 percent done”. It has no notion of multiple values, so a stream is a separate abstraction: a future that yields Ready(Some(item)) repeatedly with a resumable state, polled until Ready(None). It has no notion of priority, so fairness among ready tasks is entirely the executor’s business, and an executor with a single queue makes no fairness promise at all.

And it has no notion of scope. A future spawned onto a runtime has no structural relationship to the code that spawned it; nothing in the type system says the parent will outlive the child or that the parent waits for it. Establishing that relationship requires a separate construct layered on top, which is what Structured Concurrency and the Task Scope describes.