by
The co-routine package gives the B programmer a flow-of-control mechanism more flexible than the normal function call/return hierarchy. This document outlines what distinguishes co-routines from regular groups of functions, and how this distinction is implemented using the programming language B.
Co-routines are of particular use in file processing, and simulation applications.
In file processing, co-routines enable the programmer to separate records or characters in time, rather than in space (i.e. physical file position), and view his program in terms of data flow from module to module, rather than flow of control.
In simulation, co-routines allow a more natural modelling of of a set of co-operating processes. It should be stressed that although co-routines share a number of properties of asynchronous processes (preservation of local variables etc.), which make modelling easy, co-routines are not separate processes, and the user must still manage flow of control between them.
For a formal definition of a co-routine, and a full explanation of the fundamental concepts, the reader is referred to the technical literature (Knuth, CACM etc.).
The current state of execution of a function can be largely described by its program instruction counter (IC) and its stack frame and pointer. The IC gives the location where execution is proceeding, and the stack frame provides the values of all arguments and other storage local to the function. If the IC, stack frame, and stack pointer are preserved when it is desired to to suspend a function, then a function may be resumed at the exact point of suspension by restoring these values.
In regular functions, the current state of the function is lost when the function returns; the only way the state may be preserved when transferring to another function is to call the other function as a subroutine of the first. Then, of course, the state of the subroutine must be lost when it returns to resume execution in its caller.
In a like manner, one can conceive of a group of functions, such as constitute a program, which can only preserve its state by calling other groups of functions (programs) as sub-programs. The state of a sub-program, as with the state of a called function, vanishes when the sub-program returns to its caller. The states of both the caller and callee cannot be easily preserved.
Co-routines, on the other hand, are groups of functions which have been given a mechanism for preserving their states before transferring to other co-routines. Transfers among co-routines do not involve the regular caller/callee hierarchy, and the states of all co-routines may be thought of as existing concurrently.
The B package supplies a set of basic primitives to allow co-routine processing: CREATE, RESUME, and DESTROY. CREATE will allocate and initialize a function control vector (FCV) to create an instance of a co-routine. RESUME will pass control from one co-routine to another. DESTROY will recover the space allocated for the FCV of a defunct co-routine.
Although the above three routines are sufficient for co-routine processing the B package supplies a number of additional features to make programming easier.
Each co-routine has a vector of user specified size (possibly zero) allocated with its FCV. This is particularly useful in simulation to store such things as the head and tail pointers of a list of transactions, queued for a server modeled by that co-routine.
The B package also supports a parent-child relationship between co-routines. Besides the use of RESUME, a another co-routine may be invoked by the use of CALL. This establishes the calling routine as the parent of the called routine (the child). A child co-routine may transfer control to its parent with with a call to DETACH, without explicitly naming or knowing the identity of the parent. The parent is inherited by any routine RESUME'd by the child. In fact the routine that does the DETACH is normally not the co-routine named in the original CALL by the parent.
For break key handling, routine .COBRK allows the user to specify a co-routine to which control will be passed whenever the break key is hit.
There are several information routines that a user may invoke to query his state. TYPE tells how a co-routine last received control; PASSER returns the address of the FCV of the routine to last pass control to a specific co-routine; CALLER returns the address of the FCV of the parent co-routine; WMI returns the address of the FCV of the current co-routine; finally SSIZE determines the amount of user specified description there is in a FCV.
There are two more routines for changing state. CALLBY artificially sets the parent, and ENDING determines what happens if a co-routine does a standard function return instead of a CALL, RESUME or DETACH.
In B, a co-routine is implemented as a group of functions which have been given their own stack. This independent stack is used by the functions which are part of the co-routine, in the same manner as the main B stack is used by functions in a regular B program. In fact, the functions of a regular B program themselves constitute a valid co-routine: a group of functions with their own stack. In regular (non-co-routine) B programs, the main B stack and its group of functions constitute the only group of functions, and the only stack, and the fact that this group of functions is really an implicitly created co-routine is completely transparent to the user.
The stack given to a co-routine is used only by the functions which are part of that co-routine. This allows the stack to be retained until explicitly destroyed, thus preserving the state of all the functions which make up the co-routine. In keeping with the concept that the states of all co-routines exist concurrently, the states of all B co-routines, as preserved on their independent stacks, also exist concurrently.
There are special B library subroutines used to create, destroy, and transfer control among co-routines. These all make use of a co-routine's Function Control Vector (FCV), which both describes the co-routine's current state and points to its stack. This FCV is also referred to as a "stack descriptor". The FCV contains information about the location, size, and use of the co-routine's stack, the manner in which the co-routine was invoked, and some optional user-supplied vector space.
The co-routine's stack itself supplies the address at which the co-routine was last suspended. This information is in the form of a return address saved in the linkage section of the function in the co-routine in which execution was suspended. This is the address at which the suspended function, and co-routine, will resume execution when control next passes to it.
Within a co-routine, which is to say within a group of functions using a common stack, function call and return proceed normally. The same conventions and mechanisms operate as in a regular B program using the main B stack. Just as it is possible to "walk off the end" of the main B stack, you can walk off the end of a co-routine's stack. Non-local GOTOs work, but only within the stack of the co-routine; it is not possible to GOTO a function in another co-routine, since the GOTO searches for its destination on the current stack only. Programming inside a co-routine is almost identical to programming in a regular B program since, as mentioned previously, every B program is actually an implicit co-routine.
A B-style co-routine is a group of functions which have been given their own stack and stack descriptor (FCV). These are both allocated, initialized, and associated with a user-specified entry function by the library routine CREATE:
fcv = create( [stksiz, [usrsiz,]] usrfunc [,arg]* );
CREATE returns the pointer to the newly allocated and initialized function control vector. All references to the co-routine must be via library functions which themselves work through this returned FCV pointer.
This description applies to the FCV which describes the main B stack, as well as the FCVs which describe stacks for co-routines. Except for the template FCV describing the main B stack, which is constructed during B setup, a FCV is allocated and initialized during a call to CREATE.
The FCV is divided into two parts:
The layout of the FCV is as follows; offsets are with respect to either the co-routine pointer (cp=x6) while in the co-routine, or the FCV pointer returned by CREATE at any time:
Offset Upper Lower Comments ------ ----- ----- -------- -8 tsx1 entry Used to make initial entry -7 4 nargs Nargs word for entry routine -6 tra falloff Transfer to falloff routine -5 caller size FCV of caller; size of fcv -4 passer type FCV of passer; type of pass -3 top base Absolute stack addresses -2 high space High water mark; user info size -1 sp Safe store for stack pointer 0 start of user info <== co-routine pointer 1 2 . user info vector . . <size> top of user info vector
The FCV contains the description of the co-routine. It stores the address it was at when it was suspended, as well as pointers to the caller (parent) and passer (brother) co-routines.
The first time the co-routine is entered, it is by a transfer to FCV[-8]. The bottom three words of the FCV make up a "function template" which calls the user-supplied entry function to the co-routine. If the entry function ever returns, it will be to this function template, and the "tra falloff" instruction will be executed. This will transfer control to the falloff routine. Normally this is equivalent to doing a DETACH, but may be set by use of ENDING. The use of a function template sets x1 so that NARGS works correctly.
The template FCV describing the main B stack is located in the entry routine .SETU.. While in your main program, the co-routine pointer (cp=x6) points to .SETU.-6. This is the value of the FCV pointer for a regular B program, and the value returned by WMI. Because of the special status of the main program in a B environment, the "caller" and "passer" fields in the FCV for the main B stack are explicitly initialized to zero. The meaning of this is more fully described below, in the section on MAIN as a co-routine.
The FCV for the main B stack contains the absolute stack addresses in the upper and lower halves of .SETU.-9 (FCV[-3]). The current high water mark stack usage is in the upper half of .SETU.-8 (FCV[-2],upper). If the stack is severely overwritten, or the registers altered, reference may be made to these locations in .SETU. to determine the actual location in memory of the main B stack.
The stack allocated for the co-routine described by a FCV is normally contiguous with the top (high address) of the user info vector. The notable exception is the main B stack, which is not contiguous with the FCV, but is allocated dynamically from available memory. The stack start is rounded up to an odd boundary and the absolute high and low addresses of the stack are placed in the upper and lower halves of FCV[-3].
When the stack monitoring routines are loaded with your program, the internal library routine .ENTRY performs a stack bound check before entering each B function. These routines are loaded automatically unless the "-Nodebugtables" option of the B command is used, in which case "Use=.bound" will load the checking routines explicitly.
When the stack overflow checking code is being used, the stack high water mark is monitored with respect to the absolute stack addresses. If the high water mark ever runs off the top of the stack, an error message is printed and your program aborts.
If the monitoring routines have been loaded and the stack descriptor (FCV) and coroutine pointer (cp=x6) are intact after an abort, the debugger BOFF is able to interpret and print the stack bounds information from the FCV.
CREATE constructs a set of valid stack frames for the user's entry function at the bottom of the newly allocated stack for the co-routine, by copying over the arguments supplied in the call to CREATE and by setting up the call/return linkage.
The linkage section in the stack frame of the user's entry function to the new co-routine (take a moment to digest this), is initialized with a return address which leads into a small "driver" routine. This driver routine will eventually call the user's entry function, as stored in the FCV of the co-routine of which the user's entry function is the start.
Co-routines are always entered via these return addresses; however, they usually lead directly into the function in the co-routine in which execution was suspended, rather than into the driver routine. The return address pointing into the driver routine is needed only when a co-routine is first entered. Priming the return address to point to the driver routine means that when this co-routine is transferred to, it will be into the driver routine, which will invoke the user's entry function. The mechanism of passing control between co-routines is described in more detail below.
Below the stack frame constructed and initialized for the user's entry function is the stack frame set up for use by the driver routine. Below that is an empty stack frame containing a zero in the word which normally contains the value of the stack pointer of the previous function. This zero indicates that there is no previous function, and that this stack frame is the rock-bottom of this particular stack. The zero is used by internal library functions, such as .GOTO, which scan down the linked list of stack pointers, to determine the bottom end of the stack. The bottom of the main B stack is also flagged by an empty stack frame containing a zero previous stack pointer.
There is a small "driver" routine which handles the initial entry into a co-routine, and also the exit from the co-routine if done via a regular B "return" or "return(value)" statement from the user's entry function. (The latter mode of exit is termed "falling off the end" of the co-routine.) This driver loop uses the stack frame set up immediately below the stack frame initialized for and used by the user's entry function.
After a co-routine has been created and initialized (both FCV and stack) by CREATE, it may be started up by any of the three library functions CALL, RESUME, or DETACH. The stack of the newly-created co-routine has been primed by CREATE with a return address which leads into the driver routine. When the co-routine is entered, via this return address, the driver routine transfers to a "function template" on the bottom of the FCV for this co-routine:
tsx1 coroentry zero 4,nargs tra falloff
This function template has been initialized to contain a standard B function call to the user-supplied entry function of the co-routine: "coroentry". If in the course of execution the user's entry function executes a normal B function return statement, the return will be to the "tra falloff" instruction of this template, which will return control to the driver routine: "falloff".
Entry into a co-routine is always via one of the three library functions for co-routine control transfer: CALL, RESUME, or DETACH. These functions always use a return address, saved in the stack of the destination co-routine, as their entry point to the destination co-routine. More detail on these return address transfers is provided below, in the section on transfer of control between co-routines.
If the top level function of a co-routine, i.e. the user-specified entry function, executes a normal B function return statement, the function returns to the "function template" on the bottom of the FCV for the co-routine and the "tra falloff" instruction transfers control back to the driver routine. The driver routine then sets a flag in the parent of this co-routine which tells the parent that the transfer of control which is about to take place is a result of "falling off" the end of a child co-routine. The driver routine then enters DETACH, which transfers control to the parent co-routine.
As it leaves the child co-routine, DETACH sets the return address on the child co-routine's stack to point back into the function it is leaving, which in this case is the driver routine. When this co-routine is next transferred into, by the return address saved on its stack, the driver loop will be returned to. The driver loop then circles around and again transfers to the function template on the bottom of the FCV for this co-routine. The template still contains the address of the user's entry function, and the entry function will be re-entered from the start. In this way, thanks to the driver routine, resuming a co-routine after it has "fallen off the end" starts the co-routine over from the beginning.
When a co-routine which has "fallen off the end" is restarted from the beginning, the arguments which were supplied in the initial call to CREATE are not re-initialized to their CREATE values. The arguments were copied to the stack of the user's entry function at the time of the call to CREATE; they can not be re-copied, and will have whatever value the user's entry function left in them at the time it did its function return. The single exception to this is the first argument, which may be supplied fresh by passing it as an argument to the library routine effecting the transfer of control.
Both the driver routine and the DETACH it performs are given an artificially large "framsi" (maximum stack used by this function) parameter which includes the area of the co-routine's stack containing the copied arguments to the user's entry function. This protects this area of the stack, and prevents it from being overwritten by asynchronous function calls which need to use the stack.
Transfer of control between co-routines is effected through standard function calls to the (nonstandard) B library routines CALL, RESUME, or DETACH. Except for the setting of the parent co-routine by CALL, and the use of that parent as the destination co-routine by DETACH, each of these routines functions in essentially the same manner. We will consider a transfer of control, via any of the above routines, from an originating co-routine to a destination co-routine.
Since, normally, called functions must return to their callers, it is apparent that these library routines employ some trickery to allow them to be called in one co-routine and to have control then end up in another co-routine. There is also some fiddling with stacks, since not only are we resuming some other function, that function is using a completely different stack, the stack of the destination co-routine, from the stack used by the originating co-routine.
Each of the three library routines is called using the standard B convention which uses routine .ENTRY to bump the stack and save the return address. This return address is saved in the linkage section of the stack frame of the currently executing function in the co-routine, as usual. This return address is the point at which this function, and hence the whole co-routine, is being suspended.
The trick comes in mid-function, where the library routines all switch their stack pointers to point to the stack of the destination co-routine, and execute a standard B function return via routine .RETRN. Instead of getting the return address just saved on the stack of the originating co-routine, because of the change of stack pointers, .RETRN picks up the return address from the stack of the destination co-routine. This return address would have been put there by .ENTRY during the entry to the last library routine (CALL, RESUME, or DETACH) which transferred control out of the destination co-routine. Resumption of the destination co-routine is made through this return address in the destination co-routine's stack, and the destination co-routine is resumed at a point immediately following the call to the library routine which transferred control out.
In this way, the call to one of these library routines is started in an originating co-routine, but is completed using the stack and return address of a different destination co-routine. Since control is coming back into the resumed co-routine using the return address saved when control last transferred out, we resume the destination co-routine at exactly the place it was left. The return address saved on the stack of the originating co-routine will not be used until some other co-routine calls one of the three library functions to transfer control to the co-routine.
Since co-routines are, in theory, all considered equal, in the sense that no co-routine should be considered a subroutine of any other, one expects the mechanism of transfer between co-routines to be a reflection of this equality. In actual fact, the provision of three types of control transfer between co-routines is an effort to provide some form of hierarchy and history to these transfers to facilitate determining just how and from where control passes into a co-routine. This mechanism eliminates some of the user's book-keeping overhead necessary to monitor this flow of control.
An executing co-routine is permitted access, via library functions, to three pieces of information concerning its history: its caller, its passer, and how it gained control. This information is preserved in the FCV of each co-routine:
The preservation of this co-routine history frees the user from the task of keeping track of such history. It allows CALL to be used in establishing a "parent" co-routine, to which its "children" (co-routines CALLed by the parent) return by DETACH. RESUME becomes a "sideways" transfer which passes on its caller. Co-routines RESUMEd from the child of a parent also become children of that parent; the CALLer field is inherited across a RESUME.
It should be apparent that RESUMEing the co-routine you are currently in does nothing; it merely transfers control into the library routine, then right back into the same co-routine again. CALLing the co-routine you are currently in also does nothing to the flow of control, but it sets the parent of the co-routine to itself. Subsequent DETACHes will do nothing, since the resumed parent is the co-routine itself.
The exact GMAP code used to implement each of CALL, RESUME, and DETACH may be found in or near the source for the CREATE library routine. The following itemized summary of the actions of these library routines, plus "falling off the end" of a co-routine, is distilled from this GMAP source:
(The following actions are performed by a section of code common to each of CALL, RESUME, DETACH, and "fall off".)
As mentioned previously, a regular B program is actually an implicitly created instance of a co-routine, complete with its own stack and initialized FCV. This means that, using the FCV which describes your main program, you may CALL or RESUME your main program as if it were a co-routine you created. There is, however, a catch.
The source of the difficulty lies in the answer to the question "Who is the caller of my main program?". Philosophically, the answer to this might be "the operating system", and you would expect that a DETACH from your main program would return you to whatever invoked your program as a whole. That this is not what actually happens is philosophically disappointing, but perhaps empirically more useful in the long run.
In actual fact, the caller field in the FCV of your main B program is explicitly initialized to zero. Any attempt to use DETACH from your main program without first having artificially set its caller (via CALLBY), will result in an attempt to address FCV control words below memory location zero, resulting in an immediate memory fault and the ungraceful end of your program. Although inconsistent with the logic of co-routines as a whole, this situation is justified on the grounds that any DETACH done from your main program (or from any co-routine simply RESUMEd by your main program) is likely an error which should be caught. If you really want it, program termination may be performed anywhere by calling EXIT, or from within MAIN by a standard B function return statement.
A second inconsistency is evident when you "fall off the end" of the co-routine which is your main program. In all co-routines which you explicitly create, falling off the end is equivalent to doing a DETACH. From your main program, falling off the end (doing a return from MAIN) terminates your program. This happens regardless of the validity of the caller field in your main program's FCV, which is perhaps just as well, considering the disaster of doing a DETACH with a zero caller field.
The above difficulties lie only with the implicit co-routine which is your main B program, i.e. to the co-routine which uses the main B stack. It is perfectly permissible to pass any of the functions of your main B program (including MAIN) to a call to CREATE, in which case the resulting co-routine is explicit, does not use the main B stack, and does not suffer from any of the above limitations/features.