Stackful coroutines in C.

• Async coroutines which can pause, waiting for a future.
• Generator coroutines used as generators for loops.
• Coroutine the coroutine engine used by Async and Generator.

Your code doesn't need to do anything special to be a coroutine, and only standard, or commonly available libraries are needed.

Prerequisites

The goal was to make a system which can be used 'out of the box'. These libraries rely on as much as possible on C's cross-platform comfort zone. C's standard libraries are used as far as possible, but, as threads.h is not usually supported, pthread.h has been used instead.

You will need to build & link the code as part of your system - coroutine/async.c, coroutine/generator.c and coroutine/coroutine.c - ensure the headers, include/*, are available on your include path.

Quick Start

Async

To run an Async program:

#include "async.h"
main(){
    Async_StartSystem();
    void *res = NULL;
    bool canceled = Async_Run(asyncmain, &param, &res);
    Async_StopSystem();
}

Async runs tasks, switching between them when the current task waits on an Async_Future. asyncmain() is run as a task. The start function for any task looks like this:

bool mytask(void *param, void **res){

    // do your thing here

    return canceled;
}

When Task returns from its start function, it returns whether it was canceled. Canceled Tasks are assumed to have not finished what they were doing.

Within your async task, create Async_Tasks and Async_Task_Await() them when you want to wait for their result:

Async_Task task1;
Async_Task_ctor(&task1, adifferenttask, &task1param);

void *result;
bool canceled = Async_Task_Await(&task1, &result);

Async_Task_dtor(&task1);

// use the result

When a task needs to wait for something, and wants to allow other tasks to run, it should use a Future:

Async_Future future;
Async_Future_ctor(&future);

// pass the future to the background-thing-which-might-take-a-while

void *res;
bool canceled = Async_Future_Await(&future, &res);

Async_Future_dtor(&future);

When the background-thing-which-might-take-a-while has a result:

Async_Future_SetResult(future, false, result);

Generators

The coroutine system needs to be started, either through Async_StartSystem(), or directly with Coroutine_StartSystem() if you don't want to do async things.

You will need a generator function:

void *yield_my_things(void *param){
    bool domore = true;

        // loop/call functions to find more values to yield, and when you have one:
        domore = Generator_Yield(thing);
        // .. if domore is false, exit your generator - it is being destructed

    // not actually used by generators, but this is a useful convention for bubbling
    // the flag out to calling functions.
    return (void *)domore;
}

And to use it:

Generator gen;
Generator_ctor(&gen, yield_my_things, "..");
void *thing;
while(Generator_Next(&gen, &thing)){
    // use thing - a value yielded by your generator
}
Generator_dtor(&gen);

Coroutines

While you can use coroutines directly, it's designed as a system to support more useful patterns, like Async and Generators.

The Coroutines system must be started:

Coroutine_StartSystem();
// use coroutines here
Coroutine_StopSystem();

Your coroutine will need to have a start function:

void *start(void *param){
    ...
}

When there is no coroutine running, start your 'main' coroutine:

void *result = Coroutine_Run(comain, param);

Create other coroutines like this:

Coroutine *cor = Coroutine_New(start);

When you want a Coroutine to run, or to return from a yield:

Coroutine_Continue(cor, value, run_early);

value will be start function's parameter, or the value returned from the yield.

Within the Coroutine, to yield a value:

void *Coroutine_Yield(value, on_yield, void *me);

The on_yield function is called after the coroutine has been 'wait'ed, but before the next coroutine is resumed.

How it Works

The coroutine system uses the stack, divided into smaller stacks, for the coroutines. This means you may need to consider whether the coroutine stack size, set by COROUTINE_STARTUP_STACK_SIZE, is right for your coroutines, and whether your stack size is enough for the number of coroutines you might run concurrently.

As each of your thread has its own stack - the coroutine system can be run (or not) independantly on each of your threads. For some special cases, you may want to adjust each of your thread's stack sizes depending on how it is used.

Style

The style is influenced by C++. For example, where possible, a Something *Something_New(a, b, c) and Something_Delete(Something *), where a Something is malloced, will have corresponding Somthing_ctor(Somthing *, a, b, c) and Something_dtor(Something *) to initialise and finalise a Something on the stack, or within another object. Using .._ctor() and .._dtor() will be faster as they avoid the malloc() and free().

Something *oneofthem = Something_New();
// use oneofthem
Something_Delete(oneofthem);

Can be also be done like this, and this will run faster:

Something oneofthem;
Something_ctor(&oneofthem);
// use oneofthem
Something_dtor(&oneofthem);

The exception is Coroutine_New() and Coroutine_Delete(). The returned Coroutine is somewhere on your thread's stack - its memory is managed by the coroutine system, and is allocated and freed quickly.

Usage

When you are using coroutines or generators:

void *myfunc(void *){
    // your function here
}

Coroutine_StartSystem();
Coroutine_Run(myfunc, (void *)myparam);
Coroutine_StopSystem();

If you also use async, then:

bool myfunc(void *myparam, void **res){
    // your async function here
}

Async_StartSystem();
void *res = NULL;
bool canceled = Async_Run(myfunc, myparam, &res);
Async_StopSystem();

While the system is started, you can make many calls to Coroutine_Run() or Async_Run(). A running system is thread local - each thread you want to use coroutines on will need to be Coroutine_StartSystem()ed or Async_StartSystem()ed.

Stack Overruns

The C stack is divided down into smaller stacks. There's one to give some work room between ..StartSystem() and ..Run(), and one for each coroutine. These have guard markers which are checked to see if the stack has overrun. If there is a stack overrun, the system cannot continue - a message is output and the programe exited. There's a number of ways to avoid this issue:

• Use less stack. This is, sometimes, the right advice, especially if the startup stack overrins. The expectation is that very little is done between .._StartSystem() and ..Run(). If your situation needs more doing, you can...

• increase the stack size. Adjust COROUTINE_STACK_SIZE (for startup) or COROUTINE_STARTUP_STACK_SIZE (for coroutines) as appropriate. If your use case is even more demanding, such as if you want 1000s of coroutines (so you need small stack chunks), /and/ some of them can recurse an unknown amount (so you need a deep stack for that coroutine), then you can...

• monitor stack headroom, and add another stack chunk if you need to:

In this last case you'll need to add some code at key points:

void *myfunction(void *param){
    if (Coroutine_GetStackHeadroom() < MIN_ALLOWED_STACK){
        return Coroutine_Chain(myfunction, param);
    }
    // do everything normally
}

More realistically:

struct myfunctionparams {
    int a;
    char *b;
    struct dog *d;
}

void *mychain(void *param){
    struct myfunctionparams *myparams = (struct myfunctionparams *)params;
    return (void *)myfunction(myparams->a, myparams->b, *myparams->d);
}

int myfunction(int a, char *b, struct dog d){
    if (Coroutine_GetStackHeadroom() < MIN_ALLOWED_STACK){
        struct myfunctionparams params = {
            a,
            b,
            &d
        };
        return (int)Coroutine_Chain(mychain, &params);
    }
}

API

Async

The pattern for using async is:

void *myasyncmaintask(void *param){
    // do your main async task things here, like starting more tasks
}

Async_StartSystem();
void *res = NULL;
bool canceled = Async_Run(myasyncmaintask, NULL, &res);
Async_StopSystem();

To create and wait for an async task:

Async_Task task1;
Async_Task_ctor(&task1, asynctask1, &task1param);
void *res = NULL;
bool canceled = Async_Task_Await(&task1, void **res)
Async_Task_dtor(&task1);

or, if you prefer new & delete:

Async_Task *task1 = Async_Task_New(asynctask1, &task1param);
void *res = NULL;
bool canceled = Async_Task_Await(task1, void **res)
Async_Task_Delete(task1);

Inside your task, when there is something to wait for and you want other tasks to run while your task is waiting, you will need a future:

Async_Future future;
Async_Future_ctor(&future);

// keep &future to hand for when the background thing completes
bool canceled = Async_Future_Await(&future, NULL);

Async_Future_dtor(&future);

Async_Future_New() and Async_Future_Delete() are also available if you prefer that style.

Inside the callback when the background thing is complete:

// result is a void *
Async_Future_SetResult(future, result, false);

or, if something went wrong:

// exception is a void *
Async_Future_SetResult(future, exception, true);

Back in the task, you can respond to the future:

... Async_Future_Await has returned
if (canceled){
    // exit quickly - you've been canceled
    // you could, for example, use the future's result as an exception, or error code here
}
// carry on - the future's result may be an actual result, that's up to you

void Async_Future_ctor(Async_Future *fut)

Initialise a future. When you no longer need it, use Async_Future_dtor().

Async_Future *Async_Future_New()

Allocate and initialise a future, When you no longer need it, use Async_Future_Delete().

Returns the new Async_Future

void Async_Future_dtor(Async_Future *fut)

fut

The Async_Future being destructed

Destruct a future previously constructed with Async_Future_ctor().

void Async_Future_Delete(Async_Future *fut)

Delete (finalise and free) a future previously new'ed with Async_Future_New()

void Async_Future_SetResult(Async_Future fut, bool canceled, void value)

Set the result of a future. This has an effect only the first time its done, ie a completed future can't be canceled and a canceled future can;t be completed.

bool Async_Future_GetResult(Async_Future fut, void *res)

Get the result of a future. The return value is whether it was canceled. res may be NULL.

typedef void (Future_Watcher)(void me, Async_Future *fut)

A Future_Watcher is a callback called when a future is done. The me parameter is the one passed to Async_Future_AddWatcher(). fut is the future which has just completed.

void Async_Future_AddWatcher(Async_Future fut, Future_Watcher watcher, void me)

Add a watcher (callback) to be called when the future is done. If the future is already complete, watcher is immediately called. The me value is passed to the watcher as its me parameter.

void Async_Future_RemoveWatcher(Async_Future fut, Future_Watcher watcher, void me)

Remove a watcher from a future.

bool Async_Future_Await(Async_Future fut, void *res)

Generator

The pattern for a Generator is:

A loop which uses the Generator

Generator gen;
Generator_ctor(&gen, mygen, &param);

void *value;
while(Generator_Next(&gen, &value)){
    // use value here
}
// value is now the return value from the Generator

Generator_dtor(&gen);

Or:

Generator *gen = Generator_New(mygen, &param);

void *value;
while(Generator_Next(gen, &value)){
    // use value here
}

Generator_Delete(gen);

Generators yield a series of void *s - what the void *s mean is up to you. Generator_Next() returns a bool to indicate whether the Generator has finished.

A generator function

void *mygen(void *param){
    bool domore = true;
    // The parameter is a pointer to a string of chars
    for (char *str = param; *str; ++str) {
        // The value yielded is a pointer to a character in the string
        domore = Generator_Yield(str);
        if (!domore){
            break;
        }
    }

    return (void *)domore;
}

The bool returned from Generator_Yield() indicates whether the generator function should yield more values. When it is false the Generator is being finalised - your generator function should close files, and release any other resources it has claimed, before exiting.

void Generator_ctor(Generator gen, void (start)(void ), void *param)

Initialise a Generator

Generator gen;
Generator_ctor(&gen, mystart, &params);

// Generator is used

// ... later:
Generator_dtor(&gen);

Generator Generator_New(void ()(void ), void *)

new a Generator - malloc it and initialise it.

Generator *gen = Generator_New(mystart, &params);

// Generator is used

// ... later:
Generator_Delete(gen);

void Generator_dtor(Generator *gen)

Finalise a Generator. Once a Generator is no longer needed, it must be finalised:

// earlier...
Generator gen;
Generator_ctor(&gen, mystart, &params);

// Generator is used

// the Generator is no longer needed
Generator_dtor(&gen);

void Generator_Delete(Generator *)

Finalise then free() a Generator. Once a newed Generator is no longer needed, it must be deleted:

// earlier...
Generator *gen = Generator_New(mystart, &params);

// Generator is used

// the Generator is no longer needed
Generator_Delete(gen);

bool Generator_Next(Generator , void *value)

Get the next value yielded by the Generator.

void *value;
while(Generator_Next(gen, &value)){
    // use value here
}

When true is returned, value is the value yielded by the Generator. When false is returned, value is the value returned when the Generator returned - the Generator has finished.

bool Generator_Yield(void *)

Yield a value from a Generator function.

bool domore = Generator_Yield(value);

value is then provided by Generator_Next() as the next value from the generator. The bool returned by Generator_Yield() indicates whether more values should be provided by your generator function. When true provide more values if possible. When false close files, free memory, free up any other resources and return. false is returned when the Generator is being finalised.

Coroutine

void Coroutine_StartSystem();

Start the coroutine system on this thread. When you've finished with Coroutine call Coroutine_Stop(). Coroutine can be started & stopped many times on one thread. The total stack allowed for all coroutines running on a thread is the size of the call stack on that thread.

void Coroutine_StopSystem();

Stop the coroutine system on this thread.

Coroutine_Start

void *(*)(void *param)

The entry function for a coroutine. The param is the value passed to Coroutine_Continue, and the void * return value can be accessed through the Coroutine object using Coroutine_GetValue().

Coroutine *Coroutine_New(Coroutine_Start start)

Create a new Coroutine. The Coroutine system must be started to create a Coroutine. The stack size available to the coroutine will be COROUTINE_STACK_SIZE defined in coroutine.h. When you have finished with your Coroutine, use Coroutine_Delete() to delete it.

void Coroutine_Run_Coroutine(Coroutine cor, void value)

Run the Coroutine and return when it returns. This is how to start coroutines running in the coroutine system. It is an error for the run coroutine to return before all other coroutines have completed.

void Coroutine_Run(Coroutine_Start start, void value)

Convenience wrapper for Coroutine_Run_Coroutine which creates the Coroutine and retrieves its result.

void Coroutine_Delete(Coroutine *cor)

Use Coroutine_Delete() to delete a coroutine when it is no longer needed.

void Coroutine_Continue(Coroutine cor, void value, bool early)

Continue the given Coroutine. value is passed to the coroutine, as param to the start function, or as the return value from Coroutine_Yield. early determines whether the continued coroutine is added to the head of tail of the list of runable coroutines.

void Coroutine_Yield(void value, Coroutine_YieldCallback on_yield, void *this)

Yield value from the current coroutine; this coroutine is moved to the list of coroutines waiting to be continued. The next runable coroutine is run - either by its start routine being called with value as its param, or by valuebeing returned from its Coroutine_Yield().

void Coroutine_GetValue(Coroutine cor)

Return the Coroutine's value - the value last yielded, or returned by its start routine.

Coroutine *Coroutine_GetActive()

Return whihc coroutine is currently running, ie the caller's Coroutine.

bool Coroutine_IsRunning(Coroutine *cor)

Return whether the given coroutine is still running - it may be running, ready to run, or waiting to be continued, but won't have returned from its start function.

int Coroutine_GetStackHeadroom()

Return the headroom available in the current coroutine's stack. This can be used to detect when your coroutine is nearing its stack limit, and then use Coroutine_Chain() to continue in a new chunk of coroutine stack.

bool Coroutine_HasCoroutinesInFreePool()

Return whether the coroutine system has any coroutine stacks available in its coroutine stack free pool.

void *Coroutine_GetCStackTop()

Return an address which is near to the top of used C stack.

void Coroutine_Chain(Coroutine_Start start, void value)

Run start with value on a new coroutine, and return its return value. It is expected that Coroutine_Chain() will be used when your coroutine is running short of stack - it is not an alternative to Coroutine_Run().