Monday, 6 January 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.

8 comments:

  1. Awesome article, I am regular visitor of this website, keep up the good work, and I will be a regular visitor for a very long time.

    ReplyDelete
  2. This comment has been removed by the author.

    ReplyDelete
  3. Thanks for the article! I have a quesiton though: sometimes in the code I find the following line: qemu_coroutine_self(), what does it do? Thx

    ReplyDelete
  4. The coroutine APIs are documented in include/block/coroutine.h. Please look there to learn about the functions.

    ReplyDelete
  5. Hi Stefan,

    A question mostly about 'internals' of coroutine. Are there any threads that are created for running coroutine? or does it run as a part of main loop? Somehow that part is not clear.

    Thanks

    -abhijit

    ReplyDelete
    Replies
    1. There are different ways to implement coroutines but currently most implementations in QEMU rely on stack switching.

      That means QEMU coroutines are not native threads visible to the host kernel. Instead they restore the register state (including stack pointer) and jump to where the coroutine last yielded without using a native thread.

      The mechanism is somewhat similar to userspace threads or "green threads".

      Delete
  6. So in short this means a coroutine can exist in any AioContext right?

    Well - this question came from the following - I noticed when I started QEMU - I saw many sometimes as high as up to 70 threads were started when the OS was booting (they eventually settled down to 5 or 6) and I read a lot of Block I/O code using coroutines, so was wondering whether they were related in any way?

    ReplyDelete
    Replies
    1. Coroutines are independent of AioContext.

      QEMU uses thread pools for certain work like disk I/O requests. You probably saw worker threads for the thread pool. They terminate after sitting idle for a few seconds.

      Delete