Pages

Monday, June 10, 2013

Coroutines for the greater good

Functions are the basic blocks of our daily code. This mechanism provides extremely simple and powerful abstraction. We use the stack memory as our main work space, storing there local variables and the return address. When the function returns, it pops the return address from the stack and jumps to it, allowing to continue previous function execution.

Once the function returns all it's internal state (local variables) is destroyed and on next invocation of the function we basically need to start from scratch. We can overcome this situation by using some clever techniques but there is a better solution.

Coroutines allow us to return from function by preserving the current context. Such coroutine can yield by passing the execution to other function which may decide to call the original function again. When this happens the execution will resume from the point of yield.

Simple example for coroutines is the consumer-producer pattern. This use case can be implemented in the following way using coroutines:

void coroutiine__ producer()
{
  while (!queue_is_full(q)) {
    item_t *item = new_item();
    queue_insert(q, item);
  }
  coroutine_yield(consumer);
}

void coroutiine__ consumer()
{
  while (!queue_is_empty(q)) {
    item_t *item = queue_remove(q);
    consume_item(item);
  }
  coroutine_yield(producer);
}

One example of interesting usage for coroutines appears in the qemu project. Qemu is the workhorse of virtualization infrastructure and it is used extensively to provide devices emulation for hypervisors such as kvm and xen.

On Jan 2011 coroutines were introduced into the qemu code base. The authors wanted to use the coroutines power to overcome some of the complexity involved in handling asynchronous calls. Before coroutines, many operations that could block were performed in asynchronous way using callbacks. This lead to complicated code since chunks of code were separated into single steps each implemented as separate callback. Temporary structures were used to pass parameters to callbacks and the whole picture looked complicated and unreadable.

With introduction of coroutines, simple interface was established to invoke cooperative functions:

/* Creating and starting a coroutine is easy: */
    
coroutine = qemu_coroutine_create(my_coroutine);
qemu_coroutine_enter(coroutine, my_data);
    
/* The coroutine then executes until it returns or yields: */
    
void coroutine_fn my_coroutine(void *opaque)
{
  my_data_t *my_data = opaque;
    
  /* do some work */
  
  qemu_coroutine_yield();
  
  /* do some more work */
}

There are several implementations to the coroutines semantics inside the qemu:

  • coroutine-ucontext.c - implements coroutines using swapcontext system call and the sigsetjmp/siglongjmp calls. The former creates and switches to new stack and the later calls used to jump from one context to other.
  • coroutine-gthread.c - uses glib threads to create abstraction of coroutines. The actual switch between coroutines stops the current thread and activates next thread which executes the cooperative task.
  • coroutine-win32.c - Is the implementation on windows. Windows allows to implement coroutines easily using fibres system calls.
  • coroutine-sigaltstack.c - Unlike in the ucontext implementation, here sigaltstack system call is used to switch stack and create context which is later accessed using sigsetjmp/siglongjmp
Different programming languages have different implementations to the coroutines abstraction. One of the best resources on the coroutines in python, is the "A Curious Course on Coroutines and Concurrency" tutorial.