daryl@mitre.arpa (08/17/87)
>I am looking for information concerning re-entrant subroutines. >To be specific what type of things to look out for when writing a >subroutine that needs to be re-entrant. Any input or reading >suggestions is appreciated! First, I apologize for posting this lengthy reply to info-unix, but I've tried sending this directly to the requestor several times from a couple of our machines and the mail always gets returned. Electronic-mail will never mature until it is reliable! Until E-mail becomes universally reliable, secondary contact routes (telephone, U.S. Mail, etc.) are advantageous. Generally --- A re-entrant procedure "...operates only on variables in registers or in separate data segments associated with the job; it never stores into, nor does it alter itself." OPERATING SYSTEMS; Madnick/Donovan; McGraw-Hill Book Company 1974; pg 179. "A pure or re-entrant procedure is one that does not alter itself or contain data or any locations that are altered." SYSTEMS PROGRAMMING; Donovan; McGraw-Hill Book Company 1972; pg 327. Re-entrant programs "...must not modify themselves in such a way that, when control is taken away from them, another transaction can interfere with the modification." DESIGN OF REAL-TIME COMPUTER SYSTEMS; Martin; Prentice-Hall 1967; pg 148.; (NOTE: My favorite definition of "re-entrant", it covers all cases.) Specifically --- If a procedure has no variable that is shared concurently with another procedure (including another invocation of itself) it is re-entrant. If a procedure must input from a shared resource (variable, array, device, etc.), then if the shared input resource is guarenteed to not change while the procedure is executing, the procedure is conditionally re-entrant. Re-entrancy is easily assured on machines which implement stack architecture by following these rules: 1) If all registers used by the subroutine/function are preserved upon entering and restored upon exiting, and ... 2) If all variables declared by the subroutine are declared to be stack variables and ... 3) If all the subroutine's input variables are passed by value (instead of reference) and ... 4) The program does not modify its own text (code) area! (NOTE: This is a corrolary to #2 above.) then the subroutine/function is guarenteed to be re-entrant. Condition 1 above is easily assured by inspection of the assembler code generated by the compiler. (Or by faith in the compiler.) Conditions 2 and 3 above may be violated if the programmer can assure that: A) Non stack variables are constant during the execution of individual invocations of the subroutine/function. B) Input variables passed by reference are constant during the execution individual invocations of the subroutine/function. Good programming practice dictates that condition 4 must never be violated! Similar restrictions apply to subroutines/functions which access files. The input data that is actually examined, must be guarenteed to be constant during execution of individual invocations of the subroutine/function. A common examples of re-entrant routines are compilers on multi-user machines where there needs to be only one re-entrant program in memory. Multiple users can use the same copy of the compiler instructions to operate on separate input and output files. a) The compiler uses temporary variables on the stack. b) Non stack variables, (compiler switches, etc.) are constant. c) Input information (source file) is constant. d) Output information (object file) produced by each invocation of the compiler is written into separate files. Re-entrant routines sometimes group input and output parameters into a "structure" that serves as both input and output for the routine. The structure usually contains input/output variables and temporary "global" variables used by the routine during individual invocations of the procedure. This type of grouping permits each invocation of the routine to require only a single pointer to the input/output block. This technique permits easy assurance that each invocation is working with unique input/output data and variables that will remain constant (not be corrupted by other invocations of the routine) during the invocation. Examples of this technique are device drivers. Device drivers usually require an I/O block that specifies the transaction, returns status of the operation, and remembers intermediate states of the transaction. Another technique is to use totally separate memory partitions for the data area of separate invocations of a procedure (such as a compiler). This is the case in virtual memory multi-user systems. Re-entrancy is assured by adherence to rules 1-4 above. However, it is possible to use a strictly non re-entrant routine (one that violates one or more of the rules above) in a manner which seems to be re-entrant. In otherwords, re-entrancy is like mathematical integration across multiple variables. If a variable remains constant during the period of integration, then it may be factored out of the integal and the complexity of the integration is reduced. Conversely a perfectly valid integral will break down if an assumed constant in the integration becomes a variable. Any routine which uses external variables or shared resources is, strictly speaking, non re-entrant. However, as long as the offending variables or resources are assured to remain constant during the period of execution of all individual invocations of the procedure, and do not adversly affect other routines then the procedure may be considered conditionally re-entrant. Finally, "re-entrant" is not to be confused with "recursive". Recursion requires that the routine be designed in such a way as to be able to call itself. A recursive routine may be re-entrant. A re-entrant routine is not necessarily recursive. D.A.R.Y.L. Daryl Crandall The MITRE Corporation daryl@gateway.mitre.ORG Mailstop Z425 daryl@mitre-gateway.arpa 7525 Colshire Dr. daryl@dash.mitre.ORG McLean VA, 22102 daryl@mitre.ORG (703) 883-7278