Coroutines in C (long)
A. Lester Buck
buck at siswat.UUCP
Mon Nov 20 10:15:30 AEST 1989
A while back, I posted to comp.sources.wanted for coroutine packages for C.
I got a few leads, found a few good sources on my own, and ended up
implementing my own small package from a year old posting by Peter da Silva
(thanks Peter!) that I had saved but forgotten in my comp.lang.c archives
(in a file called "coroutines" yet).
==================
>From jls at attctc
I have found two sets of code, one very rough, but perhaps a good starting
point. First, the PC Technical Journal did a series on Multi Tasking a couple
of years ago -- a lot of BBS systems have the TJOS c source files. They just
cover starting and stopping multiple threads scheduled by the timer tick. No
critical sections, no blocking of one thread for I/O, no protection from
multiple calls to DOS, etc. (I also have heard rumors that the Doctor Dobbs
Journal ran a similar series, comlete with code.)
I found another package (on a big xenix BBS system) called CTASK. This was a
rather complete multitasking package for C under MS DOS, and seems to have
most of the stuff missing from TJOS. Here's an excerpt from the docs:
CTask
A Multitasking Kernel for C
Version 1.1 Released 88-07-01
Public Domain Software written by
Thomas Wagner
Patschkauer Weg 31
D-1000 Berlin 33
West Germany
BIXmail: twagner
Introduction
CTask is a set of routines that allow your C program to execute
functions in parallel, without you having to build in sophisti-
cated polling and switching schemes. CTask handles the switching
of processor time with a priority based, preemptive scheduler, and
provides a fairly complete set of routines for inter-task communi-
cation, event signalling, and task interlocking. CTask also in-
cludes a number of drivers for MS-DOS that build on the basic
functions to allow you to include serial I/O, printer buffering,
and concurrent access to DOS functions into your programs with
little programming effort.
An Example
To illustrate one possible use of CTask, let me elaborate on the
following example. Say you just finished your nifty telecommuni-
cations program, complete with download protocols, scripts, and
everything. But wouldn't it be nice to be able to print the file
you just downloaded while receiving the next, and edit a comment
to some previous message without interrupting the transmission? So
you take those editor routines from a previous project, plug them
in, and - oops, how do you switch back and forth between editing,
communication and printing? The answer to this is CTask. CTask
allows your C program to do many different things at the same time
by switching the processor between the tasks you define. And since
most of the time your program is waiting for some slow device
(like the human hand) to provide feedback, this switching is com-
pletely transparent, and will not noticeably slow your program
Thomas Wagner, Berlin,Germany
This package is in an arc file about 200K bytes called CTASK11A.ARC. I
found it on the XBBS author's BBS, but have seen it on other systems that
run XBBS. This package sounds like what you are looking for.
==================
>From ...!uw-beaver!sumax!steven!cac
I use the coroutine package from the Icon folks at U. Ariz.
==================
I also got a note from someone at the Austin Codeworks that one of their
packages also includes coroutine support, but I didn't save that message.
The November 1989 issue of Computer Language magazine has a multitasking
theme, including an article on "Pre-emptive Tasking in C++". This article
refers to a previous article from October 1988, "A Multitasking Kernel for C
Programmers", which is a nice non-premptive set of code, is quite portable
and supports threads, pipes, messages, semaphores, and more. The only
suggestion I would make for this system is to use the Microsoft C5.1 /Gs
switch to disable stack probes, instead of the kludge of setting STKHQQ=0 in
the assembly piece.
I didn't get the CL issue until after I had another working implementation,
which is given here. I probably would have used the Oct 88 CL code if
I was to do it again.
Here is an old posting on coroutines by Peter da Silva. The part I don't
understand here is that this appears to be a complete C implementation of a
coroutine package, but the context switch function is called switch()!
Peter, can you design this stuff on the fly as you type it in (I am
impressed!!!), or was this translated from another language? I can't see
how it ever compiled in C.
======================
>From nuchat!sugar!peter Fri Mar 25 07:06:36 1988
Path: siswat!nuchat!sugar!peter
From: peter at sugar.UUCP (Peter da Silva)
Newsgroups: comp.lang.misc,comp.unix.wizards,comp.lang.c
Subject: Re: From Modula to Oberon
Summary: C almost supports coroutines. Her's what it needs.
Message-ID: <1758 at sugar.UUCP>
Date: 25 Mar 88 13:06:36 GMT
References: <2827 at enea.se><1557 at pasteur.Berkeley.Edu><3764 at bloom-beacon.MIT.EDU><1139 at PT.CS.CMU.EDU>
Organization: Sugar Land UNIX - Houston, TX
Lines: 100
In article <1139 at PT.CS.CMU.EDU>, edw at IUS1.CS.CMU.EDU (Eddie Wyatt) writes:
>>
>> The debate about CLU iterators misses an important point: CLU iterators are
>>coroutines, which C does not have.
Coroutines in 'C' are easy to implement, though. Why, this whole O/S we're
reading news on (UNIX) is written as a set of coroutines in 'C'. (yes, it's
a simplification... but not much of one).
I'd like to see the following functions become standard in 'C':
COROUTINE -- Build a jmp_buf for a coroutine.
int coroutine(jump, entry, stack, stacksize);
struct jmp_buf *jump;
void (*entry)();
char *stack;
int stacksize;
This sets up the stack and jmp_buf so that a call to "longjmp(jmp_buf)"
will appear to be a call to entry(). It will return an error only if the
stack isn't large enough for a small routine that does nothing but call
the following function:
int switch(from, to, status)
struct jmp_buf *from, *to;
int status;
{
int code;
if(!(code=setjmp(from)))
longjmp(to, status);
return code;
}
Voila! Co-routines! Lightweight processes (best if you have the Berkeley
signal handler, I guess, so you could run it off alarms...):
struct proc {
struct proc *next;
struct proc *prev;
char *stack;
struct jmp_buf context;
};
struct proc *runq; /* doubly linked circular queue */
sleep()
{
struct proc *self;
/* do nothing if no procs or I'm alone */
if(!runq)
return;
if(runq->next == runq)
return;
self = runq;
runq = runq->next;
switch(&self->context, &runq->context, 1);
}
int spawn(entry, stacksize)
void (*entry)();
int stacksize;
{
struct proc *p;
if(!(p = malloc(sizeof *p)))
return 0;
if(!(p->stack = malloc(stacksize))) {
free(p);
return 0;
}
if(!coroutine(p, entry, p->stack, stacksize)) {
free(p->stack);
free(p);
return 0;
}
p->stacksize = p;
p->next = runq->next;
p->prev = runq;
runq->next->prev = p;
runq->next = p;
return p;
}
int delete(p) /* note, this version doesn't allow a process to delete itself! */
struct process *p;
{
if(p==runq)
return 0;
p->next->prev = p->prev;
p->prev->next = p->next;
free(p->stack);
free(p);
}
--
-- Peter da Silva `-_-' ...!hoptoad!academ!uhnix1!sugar!peter
-- Disclaimer: These U aren't mere opinions... these are *values*.
=======================
Here is my implementation of the above design, with assembly language
support for Microsoft C5.1. This code extends the setjmp/longjmp routines
in Microsoft C to include the stack segment in the jmp_buf. Do not
#include <setjmp.h> in any code using this package. Compile all your code
with "/AL /Au /Gs". (Large model, stack segment reg != data segment reg,
and disable stack probes.) Since this code mallocs the stack to be used for
each process, /Au prevents fun stuff like "i=1; array[1] != array[i]". I
used this for a terminal emulator product that supports N independent serial
input streams. A typical test program that exercises the coroutines is
included at the end, though you will need to change the test functions
called for serial input.
This code went into a quick demo that works fine, but may still have some
subtle bugs, and some of the fancy junk I put in the setjmp/longjmp assembly
on stack overflow has not been tested. If anyone does find bugs, I would
appreciate hearing about them.
(I did this for a client under contract, but since I got the design from
Usenet, it only seems right to give something useful back.)
A. Lester Buck ...!texbell!moray!siswat!buck
-------------------cut here--------------------cut here---------------------
#To unpack, delete all lines before this and feed to /bin/sh
echo setjmp.asm 1>&2
sed -e 's/^X//' >setjmp.asm <<'END'
X; @(#)setjmp.asm 1.3 89/11/19 15:27:46
X
X; setjmp.asm - setjmp, longjmp, coroutine support
X
X page 55,132
X
Xreturn_offset EQU word ptr [bp+0]
Xreturn_segment EQU word ptr [bp+2]
XARG_jmpbuf EQU dword ptr [bp+4]
XARG_status EQU word ptr [bp+8]
X
Xjmpbuf struc
Xbp_save dw ? ; bp
Xdi_save dw ? ; di
Xsi_save dw ? ; si
Xstack_offset dw ? ; stack
Xstack_segment dw ? ; address
Xentry_offset dw ? ; entry
Xentry_segment dw ? ; address
Xds_save dw ? ; ds
Xjmpbuf ends
X
X.model large
X.code
X
X
X PUBLIC _setjmp
X_setjmp PROC
X; destroys ax, bx, cx, dx
X mov ax, bp ; save registers, but not on stack
X mov bp, sp ; set frame pointer
X mov dx, ds
X lds bx, ARG_jmpbuf ; DS:BX -> jmpbuf
X mov [bx].bp_save, ax
X mov [bx].di_save, di
X mov [bx].si_save, si
X mov [bx].stack_offset, sp
X mov cx, ss ; save stack segment
X mov [bx].stack_segment, cx
X mov cx, return_offset
X mov [bx].entry_offset, cx
X mov cx, return_segment
X mov [bx].entry_segment, cx
X mov [bx].ds_save, dx
X mov ds, dx ; restore registers
X mov bp, ax
X xor ax, ax
X retf
X_setjmp ENDP
X
X
X PUBLIC _longjmp
X_longjmp PROC
X; destroys ax, bx, cx, dx
X mov bp, sp ; set frame pointer
X mov ax, ARG_status ; set return value
X or ax, ax ; insure non-zero
X jnz skip
X inc ax
Xskip:
X lds bx, ARG_jmpbuf ; DS:BX -> jmpbuf
X mov di, [bx].di_save
X mov si, [bx].si_save
X mov dx, [bx].stack_segment
X mov ss, dx ; do stack switch
X mov sp, [bx].stack_offset ; new sp must be next instruction
X mov bp, sp ; new frame pointer
X mov cx, [bx].entry_offset ; set saved return address
X mov return_offset, cx
X mov cx, [bx].entry_segment
X mov return_segment, cx
X mov bp, [bx].bp_save
X mov ds, [bx].ds_save
X retf
X_longjmp ENDP
X
X
X
X;
X; int coroutine(context, entry, stack, stacksize)
X;
X; struct jmp_buf *context;
X; void (*entry)();
X; char *stack;
X; int stacksize;
X;
X; Setup stack and entry in jmp_buf so that a call to
X; "longjump(jmp_buf)" will appear to be a call to entry().
X; It will return an error only if the stack isn't large
X; enough for a small routine that does nothing but call
X; swap().
X;
X; returns true(1) on success, false(0) on failure
X;
X
X PUBLIC _coroutine
XARG_context EQU dword ptr [bp+4]
XARG_entry_offset EQU word ptr [bp+8]
XARG_entry_segment EQU word ptr [bp+10]
XARG_stack_offset EQU word ptr [bp+12]
XARG_stack_segment EQU word ptr [bp+14]
XARG_stacksize EQU word ptr [bp+16]
X
X
X_coroutine PROC
X mov ax, bp
X mov bp, sp
X cmp ARG_stacksize, 050h ; minimum stacksize
X jnb stack_ok
X mov bp, ax
X xor ax, ax ; error return
X retf
Xstack_ok:
X mov dx, ds
X lds bx, ARG_context
X mov [bx].bp_save, ax ; save BP and DS, restore later
X mov [bx].ds_save, dx
X mov cx, ARG_entry_offset
X mov [bx].entry_offset,cx
X mov cx, ARG_entry_segment
X mov [bx].entry_segment,cx
X mov ax, ARG_stack_offset
X add ax, ARG_stacksize
X jnc nocarry
Xfixss: ; correct for SP overflow
X ; make largest possible SP
X mov cx, 4
X shr ax, cl
X inc ax
X add ARG_stack_segment, ax ; fixup SS
X mov ax, ARG_stack_offset ; subtract one paragraph from SP
X and ax, 0Fh
X sub ax, 10h
Xnocarry:
X sub ax, 4 ; make room for return address
X ; in longjmp
X ; (ignore possible carry)
X mov [bx].stack_offset, ax
X mov cx, ARG_stack_segment
X mov [bx].stack_segment, cx
X mov ax, return_segment ; save return address in registers
X mov cx, return_offset
X; mov ss, [bx].stack_segment ; switch to new stack
X; mov sp, [bx].stack_offset
X; push ax ; form return address on new stack
X; push cx
X
X
X mov dx, [bx].ds_save ; restore registers
X mov ax, [bx].bp_save
X mov [bx].bp_save, 0 ; set indeterminate registers to zero
X mov [bx].si_save, 0
X mov [bx].di_save, 0
X mov ds, dx
X mov bp, ax
X mov ax, 1 ; successful return
X retf
X_coroutine ENDP
X
X END
END
echo corout.h 1>&2
sed -e 's/^X//' >corout.h <<'END'
X/* @(#)corout.h 1.2 89/11/19 15:28:07 */
X
X#define STACKSIZE (0x2000) /* I use 8K stack/process */
X
Xstruct jmp_buf {
X int bp;
X int di;
X int si;
X void (*stack)();
X void (*entry)();
X int ds;
X};
X
Xstruct proc {
X struct proc *next;
X struct proc *prev;
X struct jmp_buf context;
X char *stack;
X int stacksize;
X};
X
Xextern struct proc *runq; /* doubly linked circular queue */
X
Xextern struct proc *spawn();
Xextern void sleep();
END
echo corout.c 1>&2
sed -e 's/^X//' >corout.c <<'END'
X/* @(#)corout.c 1.4 89/11/19 15:27:56 */
X
X#include <stdio.h>
X#include <malloc.h>
X#include "corout.h"
X#include "screen.h"
X
Xstatic
Xint
Xswap(from, to, status)
Xstruct jmp_buf *from, *to;
Xint status;
X{
X int code;
X
X if(!(code=setjmp(from))) {
X longjmp(to, status);
X }
X
X return code;
X}
X
Xvoid
Xsleep()
X{
X struct proc *self;
X /* do nothing if no procs or I'm alone */
X if (!runq) {
X return;
X }
X if (runq->next == runq) {
X return;
X }
X
X self = runq;
X runq = runq->next;
X swap(&self->context, &runq->context, 1);
X}
X
Xstruct proc *
Xspawn(entry, stacksize)
Xvoid (*entry)();
Xint stacksize;
X{
X struct proc *p;
X
X if(!(p = (struct proc *)malloc(sizeof *p))) {
X printf("spawn: malloc struct proc failed\n");
X return 0;
X }
X if(!(p->stack = malloc(stacksize))) {
X printf("spawn: malloc stack area failed\n");
X free(p);
X return 0;
X }
X if(!coroutine(&p->context, entry, p->stack, stacksize)) {
X printf("spawn: coroutine returned failure\n");
X free(p->stack);
X free(p);
X return 0;
X }
X p->stacksize = stacksize;
X if (!runq) { /* if this is first process */
X runq = p->next = p->prev = p;
X return p;
X }
X p->next = runq->next;
X p->prev = runq;
X runq->next->prev = p;
X runq->next = p;
X return p;
X}
X
X/* this version does allow a process to delete itself, */
X/* but not necessarily successfully... */
Xint
Xdelete(p)
Xstruct proc *p;
X{
X p->next->prev = p->prev;
X p->prev->next = p->next;
X free(p->stack);
X free(p);
X}
END
echo tstco.c 1>&2
sed -e 's/^X//' >tstco.c <<'END'
X/* @(#)tstco.c 1.2 89/11/19 15:02:11 */
X
X/* testco.c - test coroutine package */
X
X#include "corout.h"
X
Xstruct proc *runq; /* doubly linked circular queue */
X
Xvoid
Xkilltime()
X{
X long i;
X for (i=0; i<100000; i++) {
X }
X}
X
Xvoid
Xscreen0()
X{
X int c;
X while(1) {
X if ((c=serial_in(0)) != -1) {
X printf("screen0: got %x \'%c\'\n", c);
X } else {
X sleep();
X }
X }
X}
X
Xvoid
Xscreen1()
X{
X int c;
X while(1) {
X if ((c=serial_in(1)) != -1) {
X printf("screen1: got %x \'%c\'\n", c);
X } else {
X sleep();
X }
X }
X}
X
Xvoid
Xscreen2()
X{
X int c;
X while(1) {
X if ((c=serial_in(2)) != -1) {
X printf("screen2: got %x \'%c\'\n", c);
X } else {
X sleep();
X }
X }
X}
X
Xvoid
Xscreen3()
X{
X int c;
X while(1) {
X if ((c=serial_in(3)) != -1) {
X printf("screen3: got %x \'%c\'\n", c);
X } else {
X sleep();
X }
X }
X}
X
Xstruct jmp_buf jump;
Xint ret;
X
Xmain()
X{
X if ((ret=setjmp(&jump)) != 0) {
X exit(ret);
X }
X
X if (!spawn(screen0, 0x1000)) {
X printf("spawn screen1 failed\n");
X longjmp(&jump, 1);
X }
X if (!spawn(screen1, 0x1000)) {
X printf("spawn screen1 failed\n");
X longjmp(&jump, 1);
X }
X if (!spawn(screen2, 0x1000)) {
X printf("spawn screen1 failed\n");
X longjmp(&jump, 1);
X }
X if (!spawn(screen3, 0x1000)) {
X printf("spawn screen2 failed\n");
X longjmp(&jump, 1);
X }
X longjmp(&runq->context);
X printf("screen0 returned, exiting\n");
X longjmp(&jump, 0);
X}
X
END
--
A. Lester Buck ...!texbell!moray!siswat!buck
More information about the Comp.lang.c
mailing list