Coroutines in one page of C

I've written a single page implementation of coroutines in C using setjmp/longjmp and just a little bit of inline assembly. The article is at embeddedrelated.com. Here's an example C program using coroutines – equivalent to the Python code:

def iterate(max_x, max_y):
  for x in range(max_x):
    for y in range(max_y):
      yield x,y

for x,y in iterate(2,2):
  print x,y

In C:

#include <stdio.h>
#include "coroutine.h"

typedef struct {
  coroutine* c;
  int max_x, max_y;
  int x, y;
} iter;

void iterate(void* p) {
  iter* it = (iter*)p;
  int x,y;
  for(x=0; x<it->max_x; x++) {
    for(y=0; y<it->max_y; y++) {
      it->x = x;
      it->y = y;
      yield(it->c);
    }
  }
}

#define N 1024

int main() {
  coroutine c;
  int stack[N];
  iter it = {&c, 3, 2};
  start(&c, &iterate, &it, stack+N);
  while(next(&c)) {
    printf("x=%d y=%dn", it.x, it.y);
  }
}

Yeah it's a bit longer, or perhaps more than a bit longer. But it's still very useful at times. Check it out!

9 comments ↓

#1 Tanim Islam on 08.20.13 at 7:51 am

In your python routine, should you not replace the "range" with "xrange," at least to preserve the spirit of using a pure python iterable?

#2 John Regehr on 08.20.13 at 9:49 am

This line looks like undefined behavior to me, but probably it is reliably compiled in practice:

start_params* p = ((start_params*)sp)-1;

#3 Yossi Kreinin on 08.20.13 at 11:49 am

@Tanim Islam: yeah, I just figured "range" is more mnemonic for someone not knowing Python and so reading it as pseudocode.

@John Regehr: very possibly it's undefined :) I'm not very good at C's semantics, really; I know I can carve out a struct out of a byte array in some cases but not others, and I was never completely sure which are which. With this type of code, I know I'll be able to maintain it as compilers/platforms change over the years but it's not because I'm trusting my formal understanding of C as much as because I trust that I can make sense of the assembly coming out of the compiler and how it's wrong and why. I wonder if start() in general is at all possible to defend in terms of C's semantics – for instance the fiddling with $sp and $fp, not to mention the FRAME_SZ constant.

BTW I discovered that on my platform for which I originally started writing this stuff, setjmp is broken in that it assumes 32b floating point registers on 32b processor variants; that's because the newlib version is from 1993 when there were just two variants of the machine – all registers 32b or all registers 64b, ints as well as floats. So the part which is supposedly correct according to C's semantics will need to be rewritten…

#4 David Janke on 08.20.13 at 11:55 am

also, xrange is not part of python 3… and range is now a Sequence

#5 Jon on 09.06.13 at 5:57 pm

Hi – this is cool. I'm going to play with it over the weekend. :)

I'm wondering if you've seen this other implementation of C coroutines? It probably has an uglier API, but I think it works by expanding macros into switch statements, which is possibly more portable, I'm not sure. It'd be interesting to see a comparison between the two.

http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html

#6 Yossi Kreinin on 09.06.13 at 11:27 pm

Indeed it's more portable; the downside is, you can only yield at the top level of your coroutine – that is, the coroutine can't itself call functions and have one of them yield control to the producer. That's because calling functions that yield requires multiple call stacks.

#7 Michael Moser on 09.24.13 at 8:05 pm

Thanks for the article,

Now there is another trick for solving lack of getcontext: if jmp_buf is an array of values then one can infer the index that stores the stack pointer and change jmp_buf directly.

Also: a very useful feature for coroutines is to have a guard page at the end of the stack; otherwise one will never know if the program ran out of the limited stack space (if one wants to service lots of coroutines, then that's what it gets)

#8 Yossi Kreinin on 09.24.13 at 10:36 pm

You could change the sp (and fp) directly by knowing which libc you're targeting; you'd need to deal with the fact that your local variables could have been rendered invalid by that when comping back from setjmp through longjmp though.

As to guard pages – if you have paging, you probably have getcontext… Non-Unix operating systems might have paging or they could have other memory protection features; I'm on an OS which doesn't use paging, for instance.

#9 Sagi on 04.20.14 at 4:09 am

For c++ programmers Boost appears to include Coroutines too

http://www.boost.org/doc/libs/1_53_0/libs/coroutine
/doc/html/coroutine/intro.html

Leave a Comment