buck@siswat.UUCP (A. Lester Buck) (11/20/89)
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@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@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@sugar.UUCP> Date: 25 Mar 88 13:06:36 GMT References: <2827@enea.se><1557@pasteur.Berkeley.Edu><3764@bloom-beacon.MIT.EDU><1139@PT.CS.CMU.EDU> Organization: Sugar Land UNIX - Houston, TX Lines: 100 In article <1139@PT.CS.CMU.EDU>, edw@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
peter@ficc.uu.net (Peter da Silva) (11/21/89)
Yeh, that was pretty much designed on the fly. It never occurred to me that it might not be a smart idea to call the switch routine switch(). I have done a similar implementation on Forth, about 8 years ago now, so it wasn't done completely cold. It *was* a redesign, though, and without access to the original code. Thanks for the ego boost. You could have kept quiet about the "switch()" business, though... :-> -- `-_-' Peter da Silva <peter@ficc.uu.net> <peter@sugar.lonestar.org>. 'U` -------------- +1 713 274 5180. "ERROR: trust not in UUCP routing tables" -- MAILER-DAEMON@mcsun.EU.net