Chapter 9 - Designing Re-Entrant Code

For a multitasking system to operate at its full potential, the kernel routines in the system must be "re-entrant". A re-entrant routine functions properly even if it is "re-entered" while it is executing. Routines that are not re-entrant will fail under these circumstances. There are two contexts where this is important: recursion and multitasking.

A recursive routine is one that calls itself; to ensure "re-entrancy with respect to recursion", a routine may modify only stack-based quantities such as data stack items and local variables (which are kept on the return stack).

Routines that modify only stack or task-private memory locations are "re-entrant with respect to multitasking". "Task-private" locations are those that can be accessed by one task only. A user variable is a task-private memory location. Routines that modify variables that are shared by more than one task are not re-entrant with respect to multitasking. They may work properly if used by only one task, but are prone to failure if they are called by multiple tasks.

A routine that is re-entrant with respect to recursion is automatically re-entrant with respect to multitasking, but the converse is not true. The rest of this discussion will focus on re-entrancy with respect to multitasking. If you are designing recursive routines, keep in mind that the rules for re-entrancy are stricter than those presented below.

The following definition (originally presented in Chapter 2) is re-entrant. The word calculates the volume and cross-sectional area of a cylinder, and modifies only the data stack and local variables (which are maintained on the return stack):

:  CYLINDER.STATISTICS    ( r1\r2 -- r3\r4 )
    \  r1 = radius, r2 = height, r3 = volume, r4 = cross-sectional area
    LOCALS{ f&height f&radius | f&area }
    f&radius  FDUP F*   PI  F*    \ cross-sectional area = πR**2
    TO f&area
    f&area f&height F*              ( -- volume = height * area )
    f&area                 ( -- volume\area )
    ;

The following version of this word is not re-entrant:

REAL: CYLINDER.AREA            \ define a self-fetching variable to hold area
:  CYLINDER.STATISTICS    ( r1\r2 -- r3\r4 )
    \  r1 = radius, r2 = height, r3 = volume, r4 = cross-sectional area
    LOCALS{ f&height f&radius  }
    f&radius  FDUP F*   PI  F*    \ cross-sectional area = πR**2
    TO CYLINDER.AREA
    CYLINDER.AREA f&height F*      ( -- volume = height * area )
    CYLINDER.AREA             ( -- volume\area )
    ;

This version uses a global self-fetching variable named CYLINDER.AREA. Assume that CYLINDER.STATISTICS is called by task #1, and that the multitasker's timeslicer transfers control to task#2 just before the final statement of the definition (that is, before the final invocation of CYLINDER.AREA). If task #2 now puts a radius and height on the stack and calls CYLINDER.STATISTICS, the value in the variable CYLINDER.AREA will be changed. When control returns to task#1, the area placed on the stack will be incorrect for that task. This shows how non-re-entrant code causes errors in multitasking systems.

Each task has its own user area, data and return stacks, POCKET, PAD, and TIB. To ensure re-entrancy, each task that uses the heap must have its own heap area. These memory areas are called "task-private" because only one task has access to them. To ensure re-entrancy, words should modify only stack-based quantities (including local variables) and task-private memory. Non-task-private memory such as the contents of variables and self-fetching variables should not be modified if the word is to be called by more than one task.

To ensure re-entrancy, data structures such as temporary matrices that hold intermediate results within a word must reside wholly on a stack or within a task-private heap. Recall that arrays and matrices have parameter fields that hold dimensioning information and a handle to the heap memory block. The parameter field of a globally defined array or matrix is allotted in the variable area when the data structure is defined. Because a function that uses such a globally defined temporary matrix could be called from multiple tasks, a parameter field in the variable area would make the routine non-re-entrant.

Stack frames solve the problem of how to create a parameter field for a temporary array or matrix while preserving re-entrancy. The temporary array/matrix parameter field can be created and kept on the data stack as a "stack frame", and using stack-based items preserves re-entrancy.

The kernel word STACK.FRAME allows a structure that has been defined with the structure defining words (see the previous chapter) to be instantiated on the data stack. STACK.FRAME expects a size (in bytes) of the structure to be placed on the data stack, allocates room on the stack, and returns on the top of the stack the extended address of the base of the stack frame. The word FRAME.DROP is used to remove the stack frame from the stack before the calling word finishes executing. The word PF.STACK.FRAME ("parameter-field-stack-frame") performs the operation of STACK.FRAME and then stores 0\0 into the first 4 bytes of the stack frame in the position where the heap xhandle will reside. Initializing the xhandle to zero is good programming practice, and PF.STACK.FRAME makes this easy to accomplish when allocating stack-based parameter fields.

For example, let's define a re-entrant version of a word that places the transpose of a source matrix into a destination matrix, even if the specified source and destination are the same. If the source and destination matrices are the same we must dimension a temporary matrix, place the transpose into it, and then copy the transpose back to the source. In the Chapter 6 discussion of arrays and matrices we defined the word #2.TRANSPOSED which can transpose a matrix, but only if the source and the destination are different matrices. We can use #2.TRANSPOSED to perform the actual transposition, but we'll add the capability of dimensioning a temporary data matrix to handle the case when the source and the destination are the same.

: #3.TRANSPOSED    ( src.xpfa\dest.xpfa -- )
    \ places the transpose of the source in the destination;
    \ the destination can be the same as the source
    LOCALS{ x&dest x&src | x&temporary }
    x&dest x&src X=                     ( source = destination?--)
    IF                        \ if source = destination...
        MATRIX.PF PF.STACK.FRAME         \ make room on stack for pf
        TO x&temporary                \ save temporary xpfa
        x&src x&temporary #2.TRANSPOSED        \ transpose is in temp matrix
        x&dest x&temporary SWAP.MATRIX        \ now x&dest has the answer
        x&temporary DELETED            \ delete the temporary matrix
        MATRIX.PF FRAME.DROP            \ clear frame off data stack
    ELSE                        \ else if source not= dest...
        x&src x&dest #2.TRANSPOSED        \ ...just do it
    ENDIF
    ;

The first line of the definition loads the source and destination xpfa's into 32-bit local variables, and creates an un-initialized local variable. The next line checks if the source and destination are equal. If they are not, the ELSE part of the conditional executes, and #2.TRANSPOSED can perform the operation directly. If the source equals the destination, however, #2.TRANSPOSED will not work, and we have to create a temporary destination matrix. The next line allocates space on the data stack for the parameter field of the temporary matrix. MATRIX.PF puts the size of the parameter field on the stack, and PF.STACK.FRAME allocates space for the parameter field on the data stack and initializes its heap handle to 0\0. The base xaddress of the stack frame is loaded into the local variable x&temporary, and the source and temporary matrix xpfa's are passed to #2.TRANSPOSED, which dimensions the temporary matrix and transposes the source into it. Next, SWAP.MATRIX interchanges the contents of the temporary and destination parameter fields so that x&dest is the transposed matrix and x&temporary points to the original matrix. Next the temporary matrix is deleted from the heap, and FRAME.DROP clears the temporary parameter field off the data stack.

This final definition is very similar to the actual definition of TRANSPOSED in QED-Forth. Many of the matrix words need temporary matrices to allow the source and destination matrices to be the same, and temporary matrices are always implemented using the stack-frame technique to ensure re-entrant operation of all of the kernel words. Thus all of the mathematics routines may be used in multitasking applications as described in the next chapter.