11
\$\begingroup\$

This is a quick and dirty implementation of coroutines that implements yield by saving and restoring the stack to and from the heap. Here's an earlier version, which does the most naive possible thing, and just allocates enough space on the stack for every possible coroutine. The relevant bits from the current code are below, and the whole thing is here.

I'm open to feedback both on pretty much anything: completely different approaches, how to restructure this approach, bugs, idiomatic C style pointers, etc.

An obvious performance improvement would be to use ucontext, but that seems to be deprecated and somewhat broken on Mac OS X (although it works fine on the linux distros I've tried). I'm not sure what the next step is to make this 'better'.

typedef void (*coroutine_cb)();

static void scheduler(coroutine_cb);
static int spawn(coroutine_cb);
static void yield(int);

jmp_buf scheduler_jmp;
void *scheduler_rbp;
int coro_pid;

coroutine_cb scheduler_next_coro;

#define MAX_COROS 100

struct {
  jmp_buf jmp;
  void *stack;
  long stack_sz;
} coroutines[MAX_COROS];

static void scheduler(coroutine_cb coro)
{
  printf("starting the scheduler...\n");
  static int max_pid = 1;

  // we move down 0x1000 to give scheduler space to call functions and allocate stack variables without having them get
  // overwritten by the memcpy below. Before we did this, we had to manually copy memory instead of using memcpy
  // because we would overwrite memcpy's stack
  scheduler_rbp = __builtin_frame_address(0) - 0x1000;
  scheduler_next_coro = coro;
  int value = setjmp(scheduler_jmp);
  // value == 0 means just starting
  // value == -1 means spawning new coroutine
  // value positive means hop back to a specific pid
  if (value == 0 || value == -1)
  {
    coro_pid = max_pid++;
    printf("about to run coro %d...\n", coro_pid);
    char *buf = alloca(0x2000); // was 0x1000 when we didn't allocate extra space for scheduler stack
    asm volatile("" :: "m" (buf));
    scheduler_next_coro();
    assert(0);
  }
  else
  {
    printf("jumped back to scheduler (pid --> %d) (coro_pid --> %d)...\n", value, coro_pid);
    // restore coroutine marked by value (pid)
    coro_pid = value;

    int stack_sz; 
    stack_sz = coroutines[coro_pid].stack_sz;
    memcpy(scheduler_rbp - stack_sz, coroutines[coro_pid].stack, stack_sz);
    longjmp(coroutines[coro_pid].jmp, 1);
    assert(0);
  }
}

static void yield(int pid)
{
  // take current rbp
  void *rbp = __builtin_frame_address(0);
  void *fudgy_rsp = (char *)rbp - 0x100;
  assert(scheduler_rbp > rbp);

  long stack_sz = (char *)scheduler_rbp - (char *)fudgy_rsp;
  void *stack = malloc(stack_sz);

  /*
   * Marek: check how overflowing stack actually works, because
   * we're actually copying data beyond our stack frame.
   */
  memcpy(stack, fudgy_rsp, stack_sz);
  coroutines[coro_pid].stack = stack;
  coroutines[coro_pid].stack_sz = stack_sz;

  if (!setjmp(coroutines[coro_pid].jmp))
  {
    longjmp(scheduler_jmp, pid);
    assert(0);
  }
  else
  {
    // our stack is already good to go at this point
    return;
  }
}

/*
 *
 */
static int spawn(coroutine_cb coro)
{
  scheduler_next_coro = coro;
  yield(-1);
  return 0; // need to get pid
}

int main()
{
  scheduler(f);
  assert(0);
  return 0;
}
\$\endgroup\$
  • \$\begingroup\$ Apart from BSD linux. \$\endgroup\$ – Martin York Aug 25 '13 at 21:10
  • \$\begingroup\$ Are you trying to implement coroutines or userland threads? \$\endgroup\$ – idoby Aug 25 '13 at 23:08
7
\$\begingroup\$

Things you did well on:

  • Overall, this looks like a pretty decent little bit of code. It looks like some research went into this
  • I like the comments. Everywhere I was confused on something, there was a comment to clarify. You also didn't go overboard with them!

Things you could improve on:

Preprocessor:

  • Group all of your #defines at the top of your code, just after your #imports. Otherwise you will have to jump around your code to find them.

Initialization:

  • typedef your structs.

    struct {
      jmp_buf jmp;
      void *stack;
      long stack_sz;
    } coroutines[MAX_COROS];
    

    The typedef means you no longer have to write struct all over the place. That not only saves keystrokes, it also can make the code cleaner since it provides a smidgen more abstraction.

  • You can initialize some variables right away.

    int stack_sz; 
    stack_sz = coroutines[coro_pid].stack_sz;
    
    int stack_sz = coroutines[coro_pid].stack_sz;
    

Syntax:

  • You use print() where it is unneeded.

    printf("starting the scheduler...\n");
    

    You can use puts() instead.

    puts("Starting the scheduler...");
    

Memory:

  • You allocated memory to stack, but never free it.

    void *stack = malloc(stack_sz);
    

    Failure to deallocate memory using free leads to buildup of non-reusable memory, which is no longer used by the program. This wastes memory resources and can lead to allocation failures when these resources are exhausted.

    free(stack);
    

Comments:

  • You could use the /* ... */ comment format instead of the // ... format when commenting over multiple lines.

    // value == 0 means just starting
    // value == -1 means spawning new coroutine
    // value positive means hop back to a specific pid
    

    You could also condense your comments down a bit.

    /* 
     * If 'value' is 0, it is just starting; if -1 it is spawning.
     * If 'value' is positive, we "hop" to a specific PID.
     */
    

Resources:

\$\endgroup\$
  • \$\begingroup\$ Why is puts better than printf here? \$\endgroup\$ – d33tah Oct 22 '15 at 22:38
  • \$\begingroup\$ @d33tah printf() is used to format strings for printing to the string. Since we are not formatting our string, we can avoid the processes that printf() would use to search for these formatting delimiters and therefore be more efficient in printing the text (miniscule, but measureable). It also avoids the need to put the \n at the end of the line, which can be a common mistake. \$\endgroup\$ – syb0rg Oct 22 '15 at 22:41
  • \$\begingroup\$ On the other side, it makes it easier to add data if you leave printf instead of puts - you just add some %d for example and an extra argument. I wonder if printf is actually slower if you're not really doing anything... The only extra work I would expect it to do is format string parsing. \$\endgroup\$ – d33tah Oct 22 '15 at 22:43
  • 1
    \$\begingroup\$ @d33tah Agreed that it would be easier, but that doesn't mean that is the best practice. goto makes some things easier, doesn't make that a good practice. As for it being slower, printf() must transverse the entire string to search for delimiters and then manipulate them (an O(n) operation at least), whereas printing the string without formatting it is more straightforward (should be an O(1) operation). \$\endgroup\$ – syb0rg Oct 22 '15 at 22:47
  • \$\begingroup\$ I agree on both of your points, thanks for explaining! \$\endgroup\$ – d33tah Oct 22 '15 at 22:49
3
\$\begingroup\$

No concrete suggestion for improvement at this time, but I'd just like to point out that your use of assert(0) is brilliant. It emphasizes to other programmers that those positions in the code are unreachable, and enforces it during development time. Also, assertions are the right mechanism to use, since those positions in the code would only be reachable due to programmer error, not due to unanticipated runtime conditions.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.