Implementing a Simple Rust Executor

Most of this article is based on aysnc-book and explains how to implement a simple executor. The project is available at simple-executor.

Asynchronous programming in Rust involves three important concepts: Future, executor, and reactor. When an executor polls a Future, it passes a waker to the Future. The reactor then waits for the events involved in the Future and, when an event completes, uses this waker to wake the executor so that it can continue executing the Future.

Future

The core of asynchronous programming in Rust is the Future trait. The Future trait has an associated type, Output, which is the result returned when the Future completes. The executor polls the Future step by step until it completes.

1
2
3
4
5
6
7
8
pub trait Future {
#[stable(feature = "futures_api", since = "1.36.0")]
type Output;

#[lang = "poll"]
#[stable(feature = "futures_api", since = "1.36.0")]
fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output>;
}

When a Future is submitted to the executor, the executor polls it. If it returns Poll::Ready(Result), the Future is finished. If it returns Poll::Pending, the Future needs to be submitted to the executor again the next time it can be polled. This is done by calling Waker’s wake method.

What is a Waker?

When a task is ready to run, the Waker is responsible for waking the task and submitting it to the executor, such as by using Waker’s wake or wake_by_ref methods. The difference is that wake consumes ownership of the waker.

Implementing a TimerFuture

Defining TimerFuture

Below, we implement a simple TimerFuture. For simplicity, when Timer is initialized, we spawn a thread. After sleeping for the specified duration, it submits the Timer to the executor again. Therefore, we need a state to indicate whether sleeping has finished, and we also need to store a Waker to resubmit the Timer after sleeping ends. The definition is as follows:

1
2
3
4
pub struct TimerFuture {
completed: bool,
waker: Option<Waker>,
}

Since we need another thread to modify TimerFuture’s completed state and use the waker to resubmit the Future to the executor upon completion, we can encapsulate these two fields together.

1
2
3
4
5
6
7
8
struct Inner {
completed: bool,
waker: Option<Waker>,
}

pub struct TimerFuture {
inner: Inner
}

Because we need to share and modify the fields across threads, we also need to wrap them in Arc and Mutex.

1
2
3
pub struct TimerFuture {
inner: Arc<Mutex<Inner>>
}

At this point, we have defined a simple TimerFuture struct. Next, we need to implement the Future trait for TimerFuture.

Implementing the Future trait

We do not need TimerFuture to produce any result, so we can simply set the associated type Output to the unit type (). When polling, we check completed’s state. If it is true, we return Poll::Ready(()); otherwise, we return Pending and copy the context’s waker to TimerFuture’s waker, so that the waker can wake this task when sleeping ends.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
impl Future for TimerFuture {
type Output = ();

fn poll(
self: std::pin::Pin<&mut Self>,
cx: &mut std::task::Context<'_>,
) -> std::task::Poll<Self::Output> {
let mut shared_state = self.inner.shared_state.lock().unwrap();
if shared_state.completed {
Poll::Ready(())
} else {
shared_state.waker = Some(cx.waker().clone());
Poll::Pending
}
}
}

executor

Rust Futures are lazy and can be driven by awaiting them in async functions. So who executes Futures? The answer is the Future executor. The executor polls a Future when progress can be made (for example, when a socket has data to read or is writable). Initially, the executor polls the Future once; subsequently, when the Future can make progress, the wake method submits it to the executor again.

Here, we can first abstract a spawner to handle the initial Future submission. Since a Future itself does not know how to submit itself to the executor, we can encapsulate the Future and its means of interacting with the executor in a Task struct. Instead of submitting a Future directly, we submit a Task. How do we interact with the executor? Again, for simplicity, we use a channel. The spawner holds a reference to the channel’s sending end, and each Task also holds a reference to the channel’s sending end.

At this point, what the executor does becomes obvious: it holds the channel’s receiving end and continually consumes Tasks from the channel and executes them in a large loop.

Implementing Task

Based on the above, we can simply pin a Future on the heap to obtain a BoxFuture, define the BoxFuture’s lifetime as static, and set Output to the unit type. In addition, because the Future may need to run on different threads, it needs to implement the Send and Sync traits. We can wrap the Future in a Mutex to obtain Sync and Send capabilities through Mutex. We can then define Task as follows:

1
2
3
4
struct Task {
future: Mutex<Option<BoxFuture<'static, ()>>>,
sync_sender: SyncSender<Task>, // Submit the Task to the executor through the sender
}

To poll a Future, we need a waker so that wake can inform the executor that the Future is ready to run again. We expect a Task to submit itself to the executor again when woken, so we can implement the ArcWake trait for Task. This allows us to use wake_ref() or into_waker() to convert Arc<impl ArcWake> into a Waker. The concrete implementation is as follows: when woken, it sends the task to the channel again.

1
2
3
4
5
6
7
8
9
impl ArcWake for Task {
fn wake_by_ref(arc_self: &Arc<Self>) {
let cloned = arc_self.clone();
arc_self
.task_sender
.send(cloned)
.expect("too many tasks queued");
}
}

Implementing Spawner

Spwaner holds the channel’s sending end, whose contents are Arc<Task>.

1
2
3
struct Spwaner {
sync_sender: SyncSender<Arc<Task>>
}

Why do we need Arc? To make it convenient to use waker_ref() directly later when constructing a Waker.

1
2
3
4
5
6
pub fn waker_ref<W>(wake: &Arc<W>) -> WakerRef<'_>
where
W: ArcWake,
{
...
}

We also need to implement the spwan method for Spawner so that it can submit Futures.

1
2
3
4
5
6
7
8
9
10
impl Spawner {
pub fn spawn(&self, future: impl Future<Output = ()> + 'static + Send) {
let future = future.boxed();
let task = Arc::new(Task {
future: Mutex::new(future),
sync_sender: self.sync_sender.clone(),
});
self.sync_sender.send(task).expect("too many tasks queued");
}
}

Implementing Executor

Executor holds the channel’s receiving end.

1
2
3
pub struct Executor {
receiver: Receiver<Arc<Task>>,
}

We implement the run method for executor. Upon receiving a task, it first takes the future out of it, constructs a waker, then constructs a context, and finally polls the Future. Recall the TimerFuture implementation: when polling returns pending, we pass the waker to it, and when sleeping ends, this waker wakes the task.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
impl Executor {
pub fn run(&self) {
while let Ok(task) = self.receiver.recv() {
let mut future_slot = task.future.lock().unwrap();
if let Some(mut future) = future_slot.take() {
let waker = waker_ref(&task);
let cx = &mut Context::from_waker(&waker);
if future.as_mut().poll(cx).is_pending() {
*future_slot = Some(future);
}
}
}
}
}

Getting this simple executor running

First, we need to create a Spwaner and an Executor.

1
2
3
4
5
pub fn new_executor_and_spawner() -> (Executor, Spawner) {
const MAX_QUEUED_TASKS: usize = 10_000;
let (sync_sender, receiver) = sync_channel(MAX_QUEUED_TASKS);
(Executor { receiver }, Spawner { sync_sender })
}

Now we can complete the main method.

1
2
3
4
5
6
7
8
9
10
11
12
13
fn main() {
let (executor, spawner) = new_executor_and_spawner();

spawner.spawn(async {
println!("{:?}", Instant::now());
TimerFuture::new(Duration::new(2, 0)).await;
println!("{:?}", Instant::now());
});

drop(spawner); // The purpose of drop is to let the executor know there are no more tasks to run

executor.run();
}

Summary

Implementing a simple executor is still relatively easy. The next step is to write a genuinely functional runtime based on mio. Now I have something to do during the National Day holiday, hehe.

Author: suikammd
Link: https://suikammd.github.io/2021/09/28/simple-executor/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.