peter@ficc.uu.net (Peter da Silva) (08/12/89)
This is a followup to a discussion on threads on comp.unix.wizards... Isn't it about time that there was some effort made to provide a standard coroutine library in C. I realise that some systems (ones with strict hardware stacks) wouldn't be able to implement this, but it'd be workable on a wide variety of systems... First, let's define a structure containing a co-routine's current context. This structure is machine dependent, and contains a co-routines stack and the register set when it's not running. context = cocreate(func, stacksize, ...); This creates a context for a coroutine. The actual arguments need to be hashed out, but obviously need an initial PC and entry point. The rest of the arguments could be passed directly to the coroutine when it's started up. cocall(context); This transfers control to the coroutine until it calls cocall(). It's roughly equivalent to doing a setjmp() in the current context and a longjmp() into the context of the new routine. In fact on a lot of systems it could even be implemented that way. I believe that's how the V7 UNIX kernel did it. Libraries like the BSD one where longjmp unwinds the stack would of course have to have an explicit implementation. codelete(context); This deletes the context and cleans up any resources it was using. These routines together would allow the portable implementation of threads on a wide variety of systems, if they became widespread. These are strictly non-preemptive threads, but that's an advantage if you want to call the C library from more than the mainline... routines in libc are not even vaguely reentrant, but they are almost all (with the exception of strtok() and a few others) serially reusable. -- Peter da Silva, Xenix Support, Ferranti International Controls Corporation. Business: peter@ficc.uu.net, +1 713 274 5180. | "The sentence I am now Personal: peter@sugar.hackercorp.com. `-_-' | writing is the sentence Quote: Have you hugged your wolf today? 'U` | you are now reading"
karl@haddock.ima.isc.com (Karl Heuer) (08/14/89)
In article <5663@ficc.uu.net> peter@ficc.uu.net (Peter da Silva) writes: >Isn't it about time that there was some effort made to provide a standard >coroutine library in C. Wasn't there such a library (cofork(), cowait(), etc.) for the pdp11 back in V6 or early V7? I never used it, but I recall having seen it described. Karl W. Z. Heuer (ima!haddock!karl or karl@haddock.isc.com), The Walking Lint
peter@ficc.uu.net (Peter da Silva) (08/14/89)
In article <14281@haddock.ima.isc.com>, karl@haddock.ima.isc.com (Karl Heuer) writes: > Wasn't there such a library (cofork(), cowait(), etc.) for the pdp11 back in > V6 or early V7? I never used it, but I recall having seen it described. There's no reference to it in my 2.9BSD manual, but that's hardly "early V7". I'm thinking of writing code for this, but I'd like to know what's already out there. -- Peter da Silva, Xenix Support, Ferranti International Controls Corporation. Business: peter@ficc.uu.net, +1 713 274 5180. | "The sentence I am now Personal: peter@sugar.hackercorp.com. `-_-' | writing is the sentence Quote: Have you hugged your wolf today? 'U` | you are now reading"
henry@utzoo.uucp (Henry Spencer) (08/14/89)
In article <5667@ficc.uu.net> peter@ficc.uu.net (Peter da Silva) writes: >> Wasn't there such a library (cofork(), cowait(), etc.) for the pdp11 back in >> V6 or early V7? I never used it, but I recall having seen it described. > >There's no reference to it in my 2.9BSD manual, but that's hardly "early V7". I remember it -- dimly -- from V6. It definitely wasn't in any V7 that I saw. -- V7 /bin/mail source: 554 lines.| Henry Spencer at U of Toronto Zoology 1989 X.400 specs: 2200+ pages. | uunet!attcan!utzoo!henry henry@zoo.toronto.edu
bvs@light.uucp (Bakul Shah) (08/15/89)
In article <5667@ficc.uu.net> peter@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>
idall@augean.OZ (Ian Dall) (08/15/89)
In article <14281@haddock.ima.isc.com> karl@haddock.ima.isc.com (Karl Heuer) writes: >In article <5663@ficc.uu.net> peter@ficc.uu.net (Peter da Silva) writes: >>Isn't it about time that there was some effort made to provide a standard >>coroutine library in C. > >Wasn't there such a library (cofork(), cowait(), etc.) for the pdp11 back in >V6 or early V7? I never used it, but I recall having seen it described. My V6 manual (chapter 7) documents crfork, crread, crwrite, crexch and cprior. It says "The activation record for each function execution is dynamically allocated rather than stacked." It goes on to say that there is a big overhead in doing this! It is however possible to specify an alternate stack as an optional argument to crfork and avoid this overhead. The scheme seems workable but portable implimentation is no doubt impossible and it may not be possible to impliment at all on some machines. Would making the coroutine functions compiler "builtin" inline functions allow implimentation on a larger variety of machines? What sort of problems do you want coroutines for? I seem to have survived about 14 years of programming without ever using them! -- Ian Dall life (n). A sexually transmitted disease which afflicts some people more severely than others. idall@augean.oz
richard@aiai.ed.ac.uk (Richard Tobin) (08/15/89)
In article <14281@haddock.ima.isc.com> karl@haddock.ima.isc.com (Karl Heuer) writes: >Wasn't there such a library (cofork(), cowait(), etc.) for the pdp11 back in >V6 or early V7? I never used it, but I recall having seen it described. Yes, it's in section VII (user-maintained subroutines) of the Sixth Edition (May 75) manual. The routines were actually called crfork(), crexit(), crread(), crwrite() crexch() and crprior(). -- Richard -- Richard Tobin, JANET: R.Tobin@uk.ac.ed AI Applications Institute, ARPA: R.Tobin%uk.ac.ed@nsfnet-relay.ac.uk Edinburgh University. UUCP: ...!ukc!ed.ac.uk!R.Tobin
peter@ficc.uu.net (Peter da Silva) (08/16/89)
In article <563@augean.OZ>, idall@augean.OZ (Ian Dall) writes: > The scheme seems workable > but portable implimentation is no doubt impossible No, which is why the basic routines need to be standardised, at least to the point where people implementing them on different compilers can agree to the names and calling conventions. > and it may not be possible > to impliment at all on some machines. True, but machines like that are likely to cause problems with varargs, setjmp/longjmp, and so on as well. > Would making the coroutine functions > compiler "builtin" inline functions allow implimentation on a larger variety > of machines? Probably not. The difficulty is dealing with exotic stacks, not where the code is done. As a thought experiment consider the case of making the cocall from a subroutine of the coroutine... if inline code was needed that would not be possible. > What sort of problems do you want coroutines for? I seem to have survived about > 14 years of programming without ever using them! Mainly for the sort of event-loop programming endemic to windowing systems. It would be easier to code this sort of application if minithreads were available. -- Peter da Silva, Xenix Support, Ferranti International Controls Corporation. Business: peter@ficc.uu.net, +1 713 274 5180. | "The sentence I am now Personal: peter@sugar.hackercorp.com. `-_-' | writing is the sentence Quote: Have you hugged your wolf today? 'U` | you are now reading"
joe@modcomp.UUCP (08/16/89)
> Isn't it about time that there was some effort made to provide a standard > coroutine library in C. At the last meeting, POSIX 1003.4 voted in a thread proposal which was worded in such a way that a coroutine implementation, done entirely with library changes, would be able to meet the standard. Thus, while this standard is technically an operating system rather than a C standard, it potentially could become the de-facto way to do coroutines/threads in C under any environment. joe korty uunet!modcomp!joe
poser@csli.Stanford.EDU (Bill Poser) (08/16/89)
Another application of the same sorts of facilities used to implement coroutines is for generator functions, i.e. functions that generate a new member of some set each time they are called. Such functions are useful for pattern matching. I have also found them useful when I needed to obtain strings contained in heterogeneous data structures (e.g. arrays and hash tables containing different kinds of objects) and sort and format information coming from all of them. To get each string you call the generator function for one of the types of data. The generator functions know the details of how the data is stored and how to traverse the data structure. But they all return objects of the same type (strings) and you keep control over storage allocation, sorting, formatting etc. in one place. Generator functions can be implemented by hand by using static variables to save the necessary state information, but this gets hairy very quickly. If one can suspend the function rather than return from it (which means, essentially, saving the stack frame) generators easy to write. This is a nice facility of ICON.
gwyn@smoke.BRL.MIL (Doug Gwyn) (08/16/89)
In article <5695@ficc.uu.net> peter@ficc.uu.net (Peter da Silva) writes: >> What sort of problems do you want coroutines for? I seem to have survived about >> 14 years of programming without ever using them! >Mainly for the sort of event-loop programming endemic to windowing systems. >It would be easier to code this sort of application if minithreads were >available. Ah, you raise an interesting point. EVENT LOOPS SUCK. Rob Pike has some interesting comments on this and suggestions for a better approach in his article "A Concurrent Window System" in the Spring 1989 issue of Computing Systems (The Journal of the USENIX Association) (Vol. 2 No. 2).
peter@ficc.uu.net (Peter da Silva) (08/16/89)
Generators in 'C'... I guess you could use coroutines to implement
something like Icon generators, but Smalltalk generators might be
easier. There's more to Icon generators than the function itself...
how do you do !every write(factor(192))!?
Generators in Smalltalk are implemented differently than in Icon.
You set up methods for getting the first and next element of the
sequence, and use instance variables (if necessary) to maintain
state. This is more conventional, and wouldn't require coroutines.
gen = NewGenerator(Factor);
x = gen->First(192);
while(x) {
Write(x);
x = gen->Next();
}
This is a job (removes glasses, or is that classes?) for C++?
--
Peter da Silva, Xenix Support, Ferranti International Controls Corporation.
Business: peter@ficc.uu.net, +1 713 274 5180. | "The sentence I am now
Personal: peter@sugar.hackercorp.com. `-_-' | writing is the sentence
Quote: Have you hugged your wolf today? 'U` | you are now reading"peter@ficc.uu.net (Peter da Silva) (08/16/89)
In article <10747@smoke.BRL.MIL>, gwyn@smoke.BRL.MIL (Doug Gwyn) writes: > In article <5695@ficc.uu.net> peter@ficc.uu.net (Peter da Silva) writes: > >> What sort of problems do you want coroutines for? [actually someone else wrote that] > >Mainly for the sort of event-loop programming endemic to windowing systems. > Ah, you raise an interesting point. EVENT LOOPS SUCK. #pragma begin arthur-dent-voice Yes, well that's the point isn't it? #pragma end arthur-dent-voice Going to threads is a moderately nice way to work around the problem. -- Peter da Silva, Xenix Support, Ferranti International Controls Corporation. Business: peter@ficc.uu.net, +1 713 274 5180. | "The sentence I am now Personal: peter@sugar.hackercorp.com. `-_-' | writing is the sentence Quote: Have you hugged your wolf today? 'U` | you are now reading"
poser@csli.Stanford.EDU (Bill Poser) (08/17/89)
In article <5710@ficc.uu.net> peter@ficc.uu.net (Peter da Silva) writes: >Generators in 'C'... I guess you could use coroutines to implement >something like Icon generators, but Smalltalk generators might be >easier. There's more to Icon generators than the function itself... >how do you do !every write(factor(192))!? It seems to me that this question confuses implementation of generators, that is, having multiple calls to factor() return the several factors, and goal-oriented evaluation, where the "every" construct (as well as others, some implicit) causes write() to be called until it fails which in turn causes factor() to be called until it fails, which happens when it runs out of results to return. Goal-oriented evaluation a la Icon does indeed require more than saving stack frames, but implementing the generator itself doesn't. >Generators in Smalltalk are implemented differently than in Icon. >You set up methods for getting the first and next element of the >sequence, and use instance variables (if necessary) to maintain >state. This is more conventional, and wouldn't require coroutines. I'm not sure I understand how this solves the problem. Using instance variables is pretty much like using statics in C to store the state information, but the real problem is in implementing the method for getting the next element in the sequence. It is that method that is going to need the state information, and when the control structure gets even moderately complicated, saving the state information without saving the whole stack frame gets to be a pain. For example, here is a generator that returns pointers to strings matching a given regular expression. The array commands contains structures whose name member is a character pointer. comcnt is the number of array elements. char * AproposBuiltins(re) regexp *re; { static int i = 0; char *retval; while(i < comcnt){ if(regexec(re,retval = commands[i].name)){ ++i; return(retval); } else ++i; } /* If we get here there are no more matches */ i = 0; /* Reset for next search */ return((char *) 0); } We make the loop index static and we also have to complicate the control structure a bit over a simple loop traversal, but it isn't too bad. How about traversing a two dimensional array? We would not only have to make both array indices static, but we would have to keep track of whether it was time to increment the outer loop index or whether we should reenter the inner loop right away. But if we save the stack frame, including not only the auto variables but the program counter, we have all the information we need no matter how complex the control structure. What is similar to coroutine support is language support for the equivalent of the Icon "suspend" primitive, which returns a value but saves the stack frame. To my (limited) knowledge, Smalltalk does not provide support for this. Isn't the Smalltalk method of implementing generators just doing it by hand as in the above C example, with instance variables playing the role of statics?
peter@ficc.uu.net (Peter da Silva) (08/17/89)
In article <10109@csli.Stanford.EDU>, poser@csli.Stanford.EDU (Bill Poser) writes: > I'm not sure I understand how this solves the problem. Using instance > variables is pretty much like using statics in C to store the state > information, Not really, because it can be concurrently reused. It's more like using a handle to hold the state information. But as you say it can get to be a pain if the state information is complex... > For example, here is a generator that returns pointers to strings > matching a given regular expression. Looks good, and coroutines could be used to implement this... you'd want to pass an extra argument, the context of the calling routine. Let's say the coroutine functions are: context = co_create(entry, stack, ...); Creates context, passes arguments to it, transfers control to it. stuff = co_call(context, stuff); /* void *stuff */ stuff will be return value from co_call in other context. status = co_delete(context); Deletes context. It's an error to delete yourself. context = co_self(); Returns own context. Then we'd call AproposBuiltins like... AproposContext = co_create(AproposBuiltins, DEFAULT_STACK, re, co_self()); while(co_call(AproposContext, NULL)) { ... } co_delete(AproposContext); (changes marked with !, additions with +) > char * ! AproposBuiltins(re, context) > regexp *re; + context *context; > { ! int i = 0; > char *retval; + + co_call(context, NULL); /* return from co_create */ > > while(i < comcnt){ ! if(regexec(re,retval = commands[i].name)) ! co_call(context, retval); ! ++i; > } > > /* If we get here there are no more matches */ > > i = 0; /* Reset for next search */ ! co_call(context, NULL); + blow_up(); /* Should never get here!!!!! */ > } -- Peter da Silva, *NIX support guy @ Ferranti International Controls Corporation. Biz: peter@ficc.uu.net, +1 713 274 5180. Fun: peter@sugar.hackercorp.com. `-_-' "Optimization is not some mystical state of grace, it is an intricate act U of human labor which carries real costs and real risks." -- Tom Neff
hinton@netcom.UUCP (Greg Hinton) (08/18/89)
In article <5663@ficc.uu.net> peter@ficc.uu.net (Peter da Silva) writes: >Isn't it about time that there was some effort made to provide a standard >coroutine library in C. >These routines together would allow the portable implementation of threads >on a wide variety of systems, if they became widespread. Isn't this precisely what the language Concurrent C attempts? "Concurrent C is the result of an effort to enhance C so that it can be used to write concurrent programs that can run efficiently on single computers, on loosely-coupled distributed computer networks, or on tightly-coupled multiprocessors. Concurrent C is an upward-compatible extension of C. These extensions include mechanisms for the declaration and creation of processes, for process synchronization and interaction, and for process termination and abortion." _The_Concurrent_C_Programming_Language_, Gehani & Roome, p. xii. Anyone know any more about this language? -- Greg Hinton INET: hinton@netcom.uucp UUCP: ...!uunet!apple!netcom!hinton
peter@ficc.uu.net (Peter da Silva) (08/18/89)
In article <2151@netcom.UUCP>, hinton@netcom.UUCP (Greg Hinton) writes: > In article <5663@ficc.uu.net> peter@ficc.uu.net (Peter da Silva) writes: > >Isn't it about time that there was some effort made to provide a standard > >coroutine library in C. > >These routines together would allow the portable implementation of threads > >on a wide variety of systems, if they became widespread. > Isn't this precisely what the language Concurrent C attempts? Concurrent C is a different language. I can't take a couple of pages of code and use them to implement threads for a C compiler and library I don't have the source to. In many C compilers I wouldn't even need to write any assembly code, since setjmp/longjmp can be used to implement the context switch. This is not nearly as ambitious a project as Concurrent C. -- Peter da Silva, *NIX support guy @ Ferranti International Controls Corporation. Biz: peter@ficc.uu.net, +1 713 274 5180. Fun: peter@sugar.hackercorp.com. `-_-' "Optimization is not some mystical state of grace, it is an intricate act U of human labor which carries real costs and real risks." -- Tom Neff
schwartz@shire.cs.psu.edu (Scott Schwartz) (08/19/89)
In article <2151@netcom.UUCP> hinton@netcom.UUCP (Greg Hinton) writes: [ concurrent c ... ] | Anyone know any more about this language? Yes... anything in particular you want to know? If you are looking for an endorsement, psu cs uses it in some operating systems classes. (Having used things like concurrent euclid in the past.) -- Scott Schwartz <schwartz@shire.cs.psu.edu>
bvs@light.uucp (Bakul Shah) (08/20/89)
In article <5773@ficc.uu.net> peter@ficc.uu.net (Peter da Silva) writes: > > In many C compilers I wouldn't even need >to write any assembly code, since setjmp/longjmp can be used to implement >the context switch. You are better off not depending on setjmp/longjmp for this because 1. In addition to jumping where a setjmp() was done, longjmp() pops zero or more frames (activation records) off the top of frame stack. 2. A longjmp() is guaranteed to work only if it is called on the same stack as its corresponding setjmp(). 3. On some machines, one must rely on the stack being the same to properly implement setjmp/longjmp. 4. Some implementations use longjmp()'s property of *shortening* the stack to catch an invalid use of longjmp (e.g. `longjmp botch' message on 4.3 bsd). 5. In a context switch you don't want to pop frames, you want to switch stacks. Even in cases where you can get away with using them for coroutine `context switch' now, the compiler vendor may rightfully decide to check for 4. above in a later version. It would be nice to have a standardized (but optional) coroutine facility (if an implementation provides it, one can depend on a standard inteface and behavior) but there is not reason to mix them up with setjmp/longjmp. By keeping the two concepts separate you would not add any additional constraints on or be constrained by setjmp/longjmp. -- Bakul Shah <..!{ames,sun,ucbvax,uunet}!amdcad!light!bvs>
peter@ficc.uu.net (Peter da Silva) (08/21/89)
In article <1989Aug19.230124.860@light.uucp>, bvs@light.uucp (Bakul Shah) writes: > In article <5773@ficc.uu.net> peter@ficc.uu.net (Peter da Silva) writes: > > In many C compilers I wouldn't even need > >to write any assembly code, since setjmp/longjmp can be used to implement > >the context switch. > You are better off not depending on setjmp/longjmp for this because I'm not depending on setjmp/longjmp. I'm just pointing out that, *in many C compilers* it is possible to use setjmp/longjmp to implement the context switch. In my original posting on this subject I went into more detail on this subject. I am well aware of the Berkeley VAX compiler's stack unwinding on a longjmp. > Even in cases where you can get away with using them for coroutine > `context switch' now, the compiler vendor may rightfully decide to > check for 4. above in a later version. True. The compiler vendor can also change their calling sequence and invalidate your low level context-switch routines. A new version of the compiler is effectively a new compiler and a new porting effort for routines like this. Hopefully if they become standardised the compiler vendor will include them in the new release. > It would be nice to have a standardized (but optional) coroutine > facility (if an implementation provides it, one can depend on a standard > inteface and behavior) but there is not reason to mix them up with > setjmp/longjmp. You should pop back a few stack levels yourself :->, and have a look at my original proposal. I do keep the two concepts seperate, but designing things so a naive implementation of setjmp/longjmp (store all regs in jmp_buf in setjmp, restore them and do a return in longjmp) can be used to bootstrap the system is IMO a good idea. -- Peter da Silva, *NIX support guy @ Ferranti International Controls Corporation. Biz: peter@ficc.uu.net, +1 713 274 5180. Fun: peter@sugar.hackercorp.com. `-_-' "Optimization is not some mystical state of grace, it is an intricate act U of human labor which carries real costs and real risks." -- Tom Neff
sam@lfcs.ed.ac.uk (S. Manoharan) (08/23/89)
In article <5773@ficc.uu.net> peter@ficc.uu.net (Peter da Silva) writes: > > In many C compilers I wouldn't even need >to write any assembly code, since setjmp/longjmp can be used to implement >the context switch. I have a question. Consider these functions: event1() event2() { { . . . . . . get_resourceX(); . . . /*resume:*/ . . . . . . } } event1() requsts for resourceX. If resourceX is not available then I want event1() to suspend, and some other event, say event2() to start. Perhaps, event2() could make the resourceX available. Once the resourceX is available, I want the function event1() to start from the /*resume:*/ point. (The code upto the /*resume:*/ point in event1() should not be re-executed) Intutively, it appears the co-routines could be applied in this context. Am I correct? And then, is there an easy way to tackle this problem? Since there could be a number of event?()s, I think setjmp() and longjmp() would be of no help. Janet: sam@uk.ac.ed.lfcs S. Manoharan Uucp : ..!mcvax!ukc!lfcs!sam Dept of Computer Science Arpa : sam%lfcs.ed.ac.uk@nsfnet-relay.ac.uk University of Edinburgh Voice: 031-667 5076 (home) Edinburgh EH9 3JZ UK.
mouse@mcgill-vision.UUCP (der Mouse) (08/28/89)
In article <10109@csli.Stanford.EDU>, poser@csli.Stanford.EDU (Bill Poser) writes: > In article <5710@ficc.uu.net> peter@ficc.uu.net (Peter da Silva) writes: >> Generators in Smalltalk are implemented differently than in Icon. >> You set up methods for getting the first and next element of the >> sequence, and use instance variables (if necessary) to maintain >> state. This is more conventional, and wouldn't require coroutines. > I'm not sure I understand how this solves the problem. Using > instance variables is pretty much like using statics in C to store > the state information, but the real problem is in implementing the > method for getting the next element in the sequence. [...What's > needed is] the equivalent of the Icon "suspend" primitive, which > returns a value but saves the stack frame. Right. > Isn't the Smalltalk method of implementing generators just doing it > by hand as in the above C example, with instance variables playing > the role of statics? Doing a generator in C this way works fine - provided only one copy of each generator is active at once. Suppose we write a generator that returns numbers in sequence, from 0 up: generate_Z() { static int i = 0; return(i++); } This works fine if we use it in simple applications. But try to use two copies of it to drive two nested loops, for example, and you'll get a little surprise.... The `instance variable' approach, while not as nice as the Icon way, is nicer than using statics in C. (C can do this, but as far as I can see you need to fake instances: typedef struct generator_Z_state { int i; } ZZZ; /* typedef for brevity */ char *new_generator_Z() { struct ZZZ z; /* char * for data hiding */ z = (ZZZ *)malloc(sizeof(ZZZ)); z->i = 0; return((char *)z); } int generator_Z(state) char *state; { return(((ZZZ *)state)->i++); } destroy_generator_Z(state) char *state; { free(state); } which is a bit ugly, but sometimes necessary. This would of course be nicer in some other language, C++ for example, which is better suited to object-oriented coding.) der Mouse old: mcgill-vision!mouse new: mouse@larry.mcrcim.mcgill.edu
peter@ficc.uu.net (Peter da Silva) (08/28/89)
In article <214@castle.ed.ac.uk>, sam@lfcs.ed.ac.uk (S. Manoharan) writes: > In article <5773@ficc.uu.net> peter@ficc.uu.net (Peter da Silva) writes: > >In many C compilers I wouldn't even need to write any assembly code, since > >setjmp/longjmp can be used to implement the context switch. [ problem deleted to save space ] > Intutively, it appears the co-routines could be applied in this > context. Am I correct? I believe so. > And then, is there an easy way to tackle this problem? Have a look at my article a couple of weeks back where I introduced this subject, then implement coroutines :->. In existing, portable, C... no. > Since there could be a number of event?()s, I think setjmp() > and longjmp() would be of no help. The naive implementation of setjmp() is to save all the registers in jmp_buf. The corresponding naive implementation of longjmp is to restore those registers and return. If this implementation is used, it should be possible to create a fake stack frame and register set in a jmp_buf and tranfer control to it using longjmp. This is, of course, hideously non-portable. But if the calling sequence for coroutines can be standardized then this non-portable code could be hidden inside co_call() and friends. -- Peter da Silva, *NIX support guy @ Ferranti International Controls Corporation. Biz: peter@ficc.uu.net, +1 713 274 5180. Fun: peter@sugar.hackercorp.com. `-_-' "Just once I'd like to meet an alien menace that isn't immune to bullets" 'U` -- The Brigadier, Dr Who.
gwyn@smoke.BRL.MIL (Doug Gwyn) (08/29/89)
In article <5899@ficc.uu.net> peter@ficc.uu.net (Peter da Silva) writes: >If this implementation is used, it should be possible to create >a fake stack frame and register set in a jmp_buf and tranfer control to it >using longjmp. You need separate (non-overlapping) stacks, not just a stack frame. Otherwise the coroutines will step on each other's <DELETED>.
peter@ficc.uu.net (Peter da Silva) (08/29/89)
In article <10861@smoke.BRL.MIL>, gwyn@smoke.BRL.MIL (Doug Gwyn) writes: > In article <5899@ficc.uu.net> peter@ficc.uu.net (Peter da Silva) writes: > >If [simple setjmp] is used, it should be possible to create > >a fake stack frame and register set in a jmp_buf and tranfer control to it > >using longjmp. > You need separate (non-overlapping) stacks, not just a stack frame. > Otherwise the coroutines will step on each other's <DELETED>. You're right, I should have spelled that out. I sort of assumed that anyone who had been following this discussion would figure that out... but of course someone who was following the discussion wouldn't have asked the question in the first place. I'll try to be clearer in the future and not assume that people will glark stuff like that from context. -- Peter da Silva, *NIX support guy @ Ferranti International Controls Corporation. Biz: peter@ficc.uu.net, +1 713 274 5180. Fun: peter@sugar.hackercorp.com. `-_-' "Just once I'd like to meet an alien menace that isn't immune to bullets" 'U` -- The Brigadier, Dr Who.
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!buckpeter@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