Monday, January 6, 2014

Coroutines in QEMU: The basics

Many developers struggle with coroutines the first time they encounter them in QEMU. In this blog post I explain what coroutines are and how to use them.

Callback hell in event-driven programs

QEMU is an event-driven program with a main loop that invokes callback functions when file descriptors or timers become ready. Callbacks become hard to manage when multiple steps are needed as part of a single high-level operation:

/* 3-step process written using callbacks */
void start(void)
{
    send("Hi, what's your name? ", step1);
}

void step1(void)
{
    read_line(step2);
}

void step2(const char *name)
{
    send("Hello, %s\n", name, step3);
}

void step3(void)
{
    /* done! */
}

"Callback hell" is the name for a confusing nest of callback functions which sometimes emerges in such programs. In QEMU we faced this challenge and looked for a solution to replace callbacks.

Instead of splitting logic across callbacks and manually marshalling data between them, we wanted to write sequential code even where event loop iterations are required:

/* 3-step process using coroutines */
void coroutine_fn say_hello(void)
{
    const char *name;

    co_send("Hi, what's your name? ");
    name = co_read_line();
    co_send("Hello, %s\n", name);
    /* done! */
}

The coroutine version is much easier to understand because the code is sequential. Under the hood the coroutine version returns back to the event loop just like the callback version. Therefore the code still uses the event loop but it can be written like a sequential program.

Coroutines as cooperative threads

Coroutines are cooperatively scheduled threads of control. There is no preemption timer that switches between coroutines periodically, instead switching between coroutines is always explicit. Coroutines run until termination or an explicit yield.

Cooperative scheduling makes writing coroutine code simpler than writing multi-threaded code. Only one coroutine executes at a time and it cannot be interrupted. In many cases this eliminates the need for locks since other coroutines cannot interfere while the current coroutine is running.

In other words, coroutines allow multiple tasks to be executed concurrently in a disciplined fashion.

The QEMU coroutine API

The coroutine API is documented in include/block/coroutine.h. The main functions are:

typedef void coroutine_fn CoroutineEntry(void *opaque);
Coroutine *qemu_coroutine_create(CoroutineEntry *entry);

When a new coroutine is started, it will begin executing the entry function. The caller can pass an opaque pointer to data needed by the coroutine. If you are familiar with multi-threaded programming, this interface is similar to pthread_create(3).

The new coroutine is executed by calling qemu_coroutine_enter():

void qemu_coroutine_enter(Coroutine *coroutine, void *opaque);

If the coroutine needs to wait for an event such as I/O completion or user input, it calls qemu_coroutine_yield():

void coroutine_fn qemu_coroutine_yield(void);

The yield function transfers control back to the qemu_coroutine_enter() caller. The coroutine can be re-entered at a later point in time by calling qemu_coroutine_enter(), for example, when an I/O request has completed.

Conclusion

Coroutines make it possible to write sequential code that is actually executed across multiple iterations of the event loop. This is useful for code that needs to perform blocking I/O and would quickly become messy if split into a chain of callback functions. Transfer of control is always explicit using enter/yield, and there is no scheduler that automatically switches between coroutines.

QEMU provides additional primitives on top of the coroutine API for wait queues, mutexes, and timers. In a future blog post I will explain how to use these primitives.