Coroutines in C

[Bakul Shah]

In article <5667 at ficc.uu.net> peter at ficc.uu.net (Peter da Silva) writes:
>
>I'm thinking of writing code for this, but I'd like to know what's already
>out there.

Rob Warnock and I built a simple simulation toolkit a few years ago.
The toolkit routines could be grouped in three conceptual layers,
with layer N depending on layer N-1.

    3:  simulation kernel
    2:  condition variables and priority-queues
    1:  coroutines

To build a complete simulation a user would provide layer 4
consisting of output display and monitoring routines and routines
that model the simulated objects themselves.

Layers 2 & 3 interfaces were stolen from Concurrent Euclid, layer 1
interface from BLISS.  In this note I will focus on the lowest
layer.  For more info on the simulation kit please see our paper "A
simple simulation toolkit in C" in Proceedings of USENIX conference,
Summer 1984, Salt Lake City, Utah.

The coroutine interface consisted of three routines:

    struct process *
    co_create(stack_address, stack_size, exit_handler,
	      function, arg1, arg2, .. argN);

	Initialize a stack in the given space and return a new
	process (that is what we called the co-routine handler).
	The stack is setup so that the first time someone does a
	co_resume on this process, `function' is entered as if it
	had been called as a normal routine. `exit_handler', which
	could be NULL, gets called when this process exits (or
	returns from function).  It can be used for any cleanups on
	exit.

    co_resume(other_process)

	Resume `other process'.  If other_process was never called,
	this call will start it up.  Else, this co_resume continues
	where other_process had done a co_resume.  The caller of
	co_resume is suspended at this point.

    co_exit(return_value)

	Cleanup any magic co_create had to do and call any user
	specified handler in co_create.  Co_exit gets called
	automatically if the top level function returns.

Struct process starts out with machine specific area to store its
state but an application could extend this struct to stash info
specific to it (our simulation kit made use of this feature).

We had to implement co_resume and co_exit in (68000) assembly
language and co_create in highly machine depenedent C code.  The
upper two layers were completely machine independent.

If I were to do this again today, I would change a couple of things
to remove some machine dependencies from the interface:

    struct co_routine *
    co_create(stack_descr, exit_handler, function, argc, argv);

	`stack_descr' hides machine specific info to build new
	stacks.  There are some processors (such as the amd29000)
	which require multiple stacks.  Different environments may
	have different constraints on such stacks, and it is best to
	provide a separate, machine specific call to create a co-
	routine stack.

Our co-routine interface is strictly uniprocessing: co_resume
suspends its caller so at any given time only one process is
``running''.  I would add a routine to resume another process
without suspending the caller to allow for a multi-processor
implementation.  Resuming a running process would return an error.

Note that we can't have co_suspend at this level because there is
*no implicit* scheduling.  A process must explicitly hand over the
processor it is running on to someone else.

In our scheme the second layer implemented condition queues and
provided wait() and signal().  Wait() put a process on a condition
queue.  Signal() suspended the signalling process and ran the
signalled process.  This in turn was sufficient to implement mutual
exclusion.  I would probably extend wait to allow a process to wait
on multiple conditions.  When any one of the wait conditions becomes
true, the process is taken off from all queues and run.

Different schemes appropriate in different situations may also be
built on top of the co-routine layer, which is why I would be
hesitant to extend it any further.

-- Bakul Shah <..!{ames,sun,ucbvax,uunet}!amdcad!light!bvs>