9 Control Transfers

Control transfers are a generalization of the notion of a procedure or subroutine call. In the Mesa architecture, there is a single primitive called XFER, which effects a control transfer from one context to another (§9.3). Variations of this primitive are used to implement procedure calls, nested procedure calls, returns, coroutine transfers, traps, and process switches. Included in XFER is a mechanism for the allocation and destruction of local frames (activation records). This mechanism is described in §9.2.

Contexts are created (and destroyed) by transfers of control, the most common of which is a procedure call. Instructions that implement various forms of procedure call (local, external, nested, etc.) and procedure return are described in §9.4. The processor also implements a general coroutine facility based on ports (§9.4.5). Ports allow contexts to transfer control without destroying their state. The ports mechanism may be used to implement, among other things, non-preemptive scheduling of contexts. (Preemptive scheduling is the subject of $10, which discusses the process mechanism.)

Strictly speaking, the contents of the evaluation stack are also part of the state of a context, but the stack is not saved or restored by a control transfer. (It is preserved by a process switch; see §10.4.2) Instead, the stack is used to pass parameters and return results from one context to another. Before and after each transfer, the source and destination contexts must agree on the number and type of the stack elements. Because traps (§9.5) are also implemented as control transfers, there are cases in which the configuration of the stack is not known by the destination context- Therefore, certain instructions save and restore the contents of the evaluation stack and the stack pointer (§9.5.3). To implement a breakpoint mechanism for debugging, these instructions also preserve the context's break byte (§9.5.4).

Furthermore, control transfers do not modify the MDS (Main Data Space) or PSB (Process Status Block) registers. These registers are controlled by the process switching mechanism (Chapter 10). Transfers of control are limited to contexts residing in the current Main Data Space.

9.1 Control Links

Contexts are represented by control links, which have one of three formats The simplest form is a frame link, which is a pointer to a local frame. It represents a context as described above. An indirect link is a pointer to a control link, and is used to establish linkages for Control Transfers, nested procedures and ports. An indirect link is converted to a context by dereferencing it.

Finally, control links of type procedure descriptor are used to represent contexts that do not yet exist. They contain all the information necessary to create the context, as well as to transfer control to it after it has been created.

Control transfers take as an argument a destination control link. The least significant bits of the control link determine the type of transfer to be performed. They are encoded as follows:

Control Link: TYPE = LONG UNSPECIFIED;
ShortControlLink: TYPE = UNSPECIFIED;
LinkType: TYPE = {frame, procedure, indirect};
TaggedControlLink: TYPE = MACHINE DEPENDENT RECORD [
    data (0: 0..13): [O..377778),
    tag (0: 14..15): [0..3),
    fill (1): UNSPECIFIED];

ControlLinkType: PROCEDURE [link: ControlLink]
    RETURNS [LinkType] =
    BEGIN
    cl: TaggedControlLink = LOOPHOLE[link];
    RETURN [SELECT cl.tag FROM
        0 => frame,
        2 => indirect,
        ENDCASE => procedure];
     END;

The internal structure of each of the variants of a control link is described below, The useof control links during transfers of control is covered in the section on XFER (§9.3).

9.1.1 Frame Control Links

A frame control Link is used to transfer control to an existing context (for example, a return from a procedure). The link is a pointer to the local frame of the context.

FrameLink: TYPE = Local FramelHandle;

MakeFrameLink: PROCEDURE [link: ControlLink] RETURNS [FrameLink] =
    BEGIN
    IF ControlLinkType[link] # frame THEN ERROR;
    RETURN[LowHalf[link]];
    END;

Note that the frame handle points to the beginning of the frame variables, not to theoverhead words Frame links always point to local frames, never to global frames.

Programming Note: To ensure that the tag bits of a frame control link have the proper values, frames must be allocated at addresses that are zero modulo four.

Programming Note: The high-order word of a FrameLink is not used and may be left uninitialized by the programmer.

9.1.2 Indirect Control Links

An indirect control link is a short pointer to a control link.

Indirectlink: TYPE = POINTER TO ControlLink;

Makeindirectlink: PROCEDURE [link: ControlLink] RETURNS [IndirectLink] =
    BEGIN
    IF ControlLinkType[link] # indirect THEN ERROR;
    RETURN[LowHalf[iink]];
    END;

Indirect control links are used to establish linkages between contexts when calling nested procedures (§9.4.3) and ports §9.4.5).

Programming Note: To ensure that the tag bits of an indirect control link have the proper values, control links pointed to by indirect links must be allocated at addresses that are two modulo four.

Programming Note: The high-order word of an IndirectLink is not used and may be left uninitialized by the programmer.

9.1.3 Procedure Descriptors

A procedure descriptor is used to create a new context. It contains the information necessary to obtain the global frame pointer GF, the code segment pointer CB, the local frame pointer LF, and the starting PC value for the procedure. It consists of two fields:

ProcDesc: TYPE = MACHINE DEPENDENT RECORD [
    taggedGF(O):UNSPEClFIED,
    PC (1): CARDINAL];

MakeProcDesc: PROCEDURE [link: ControlLink] RETURNS [ProcDesc] =
    BEGIN
    IF ControlLinkType[link] # procedure THEN ERROR;
    RETURN[LOOPHOLE[link]];
    END;

The taggedGF is the global frame pointer or'ed with 1. This result becomes the new value of GF. The code base is then obtained from the global frame using CF. The PC field contains the starting byte PC for the procedure (relative to the code base (CB). The first byte of code contains the frame size index (fsi) for the local frame required. This index is used to allocate a local frame whose address is loaded into the LF register (see §9.2).

The following is a sketch of this process (ignoring traps and other types of control transfers). §9.3 contains a complete description.

proc: ProcDesc;...
    c- And[proc.taggedG F,  177776B];
    c8  ReadDblMds[@BlobalBase[~~].codebase];
    PC  proc. pc;  fsi : FSIndex = GetCodeBytej];
    PC+=PC 9 1;
    LF  Alloc[fsi];

The next section describes frame allocation in more detail.

9.2 Frame Allocation

The procedure call return mechanism and the Allocate Frame and Free Frame instructions allocate and free frames from the Frame Heap in the Main Data Space. The heap is accessed using a structure called the Allocation Vector, which begins at a fixed location in each Main Data Space. Allocate and Free Frame make use of two more primitive operations, Alloc and Free. Alloc takes a frame size index and returns the address of a frame of the requested size (or larger if indirection occurs). If Alloc cannot satisfy the request, it causes a fault (§10.4.3). Free takes a frame pointer and returns the frame to the appropriate list in the Allocation Vector. The structure of the Allocation Vector and the Frame Heap is illustrated in Figure 9.1.

9.2.l Frame Allocation Vector

To implement heap allocation, each Main Data Space contains a preallocated pool of frames of the most frequently used sizes The pool is organized as a vector of pointers to lists of frames of the same size, and frame sizes are encoded by their index into this vector Since frames begin on four-word boundaries, the low-order two bits of the pointers comprising the lists are not needed to address the frames. Instead, these bits are used as atag, encoded as shown below:

AV: POINTER TO AllocationVector = LOOPHOCE[mAV];
AllocationVector: TYPE = ARRAY FSIndex OF AVItem;

FSIndex: TYPE = [0..256);

AVItem: TYPE = MACHINE DEPENDENT RECORD [
    data (0: 0..13): [0..37777B],
    tag (0: 14..15): MACHINE DEPENDENT {frame, empty, indirect, unused}];

The frames of each size are arranged in a linked list, with the AVItem at the head of the list. If the tag field is frame (zero), the AVItem points to the first frame on the list, which will be the next one of this size allocated. The following routine is used to construct the frame pointer in this case:

AVFrame: PROCEDURE [avi: AVItem]
    RETURNS [LocalFrameHandle] =
    BEGIN
    IF avi.tag # frame THEN ERROR;
    RETURN[LOOPHOLE[avi]];
    END;

Note that the pointer addresses the first local variable of the frame. The frame actually begins at the frame address minus the size of the frame overhead (§3.2.2.2).


Figure 9.1 Frame Heap

When allocation occurs, AVFrame[AVItem] is returned to the requester. The contents of the word it points to (an AVItem, including tag bits) replaces the AV entry. Thus, frames are allocated from (and returned to) the head of the list, and the Allocation Vector entry usually points to the next frame to be allocated. The following routine decodes an AVItem into a pointer to the next item on the list:

AVLink PROCEDURE [avi: AVItem] RETURNS [POINTER TO AVItem] =
    BEGIN
    IF avi.tag # frame THEN ERROR;
    RETURN[LOOPHOLE[avi]];
    END;

The last frame in a list contains either an end-of-list tag (empty) or an indirect tag (indirect). When the last frame is allocated, its AVItem is stored in the Allocation Vector as described above. At the next request for a frame of that size, if the tag of the AVItem is indirect, its data field is used as a frame size index to access another (larger) frame list. This list may in turn contain an indirect tag. An indirect AVItem normally is placed in the last frame on a list, because a larger frame size may be needed if that list becomes exhausted. If the tag is empty, an exception occurs. Since several processes may share the same Main Data Space (and thus share the same Allocation Vector and Frame Heap), a fault rather than a trap is generated (§10.4.3).

The frame heap should contain enough frames to satisfy the majority of allocation requests. In response to an exception, the programmer can supply more frames of the appropriate size and retry the operation.

9.2.2 Frame Allocation Primitives

The Alloc and Free primitives are defined below. Note that the FrameFault routine, defined in §10.4.3, does not return control to Alloc; instead, it raises the Abort signal (§4.1).

Alloc: PROCEDURE [fsi: FSIndex] RETURNS [LocalFrameHandle] =
    BEGIN
    item: AVItem;
    slot: FSIndex  fsi;
    DO item  FetchMds[@AV[slot]];
        IF item.tag # indirect  THEN EXIT;
        IF item.data > LAST[FSIndex] THEN ERROR ;
        slot  item.data;
        ENDLOOP;
     IF item.tag = empty THEN FrameFault[fsi];
     StoreMds[@AV[slot]]  FetchMds[AVLink[item]];
     RETURN[AVFrame[item]];
     END;

Free: PROCEDURE [frame: Local FrameHandle] =
    BEGIN
    word: localWord = FetchMds[@LocalBase[frame].word]; 
    item: AVItem = FetchMds[@AV[word.fsi]];
    StoreMds[frame]  item;
    StoreMds[@Av[word.fsi]]  frame;
    END;

Note that no assignments are performed until all possibility of a trap or fault has passed. Routines that call Alloc and Free are mindful of the fact that they have side effects on the Frame Heap.

Programming Note: The Allocation Vector can be shorter than the maximum size specified above. In that case, it is the programmer's responsibility to ensure that no fsi greater than the size of the AV is used, since the processor does no dynamic bounds checking on fsi's.

Design Note: The actual frame sizes associated with each frame size index and the distribution of the number of frames of each size allocated is established by the programmer. Programmers can also designate certain fsi's for special purposes by ensuring that those indices are not generated in the fsi field of code-segment entry vectors. In addition, classes of frames (for instance, resident and non-resident frames) can be designated by using separate ranges of index values for each class. The architecture need not be aware of any of these properties of fsi's.

9.2.3 Frame Allocation Instructions

The Alloc and Free primitives are used by the control transfer instructions. Frames can also be allocated from the heap by programmers using the following instructions:

AF Allocate Frame

AF: PROCEDURE =
    BEGIN
    fsi: FSIndex = Pop[];
    Push[Alloc[fsi]];
    END;

FF Free Frame

FF:  PROCEDURE =
    BEGIN
    frame: LocalFrameHandle = Pop[];
    Free[frame];
    END;

Programming Note: Programmers can utilize all of the storage obtained by an Allocate Frame instruction, including frame overhead words. However, the frame size index in the overhead region must be preserved so that it is available for use by the Free primitive.

9.3 Control Transfer Primitive

The control transfer instructions, the trap mechanism, and the process-switching facility all make use of a primitive operation called XFER. The various forms of XFER are distinguished by the ways they generate the source and destination arguments, whether the current local frame is to be freed, their processing of the source and destination links, and some subtle differences in handling traps (discussed in §9.5).

The idea behind XFER is that a single primitive may be used to construct a variety of control disciplines, including procedure calls and returns, nested procedure calls, coroutine transfers, traps, and process switches.

Note: In the XFER code, nPC and nLF designate the new values of PC and LF, required because these registers cannot be modified due to the possibility of a trap or fault. Such temporaries for GF and CB are unnecessary, since the trap and fault routines do not reference them (§9.5.2, §10.4.3).

XferType: TYPE = MACHINE DEPENDENT {return(0), call(l), local(2),
    part(3), xfer(4), trap(5), processSwitch(6), unused(7));

XFER: PROCEDURE [
    dst: ControlLink, src: ShortControlLink,
    type: XferType, free: BOOLEAN  FALSE] =
    BEGIN
    nPC: CARDINAL;
    nLf: Local FrameHandle;
    push: BOOLEAN  FALSE;
    nDst: Controltink  dst;
    IF type = trap AND free THEN ERROR;
    WHILE ControlLinkType[nDst] = indirect DO
        link: Indirectlink  MakelndirectLink[nDst];
        IF type = trap THEN ERROR;
        nDst  ReadDblMds[link];
        push  TRUE;
        ENDLOOP;
    END;
    
...

In the case of an indirect control link, XFER follows the pointer until a frame link or procedure descriptor is located. The initial processing of a procedure descriptor was explained in §9.1.3; XFER completes the control transfer by initializing the local frame returned by Alloc with a pointer to the procedure's global frame and the procedure's return link (the source of the XFER).

If either the global frame pointer or PC are zero, the procedure descriptor is unbound and an UnboundTrap occurs. A CodeTrap is generated if the code base obtained from the global frame is odd. Recall also that the Alloc routine may generate a FrameFault (§9.2).

    SELECT ControlLinkType[nDst] FROM
        procedure =>
            BEGIN
            word: BytePair;
            proc: ProcDesc = MakeProcDesc[nDst];
            GF  And [proc.taggedGF, 077776B];
            IF GF = LOOPHOLE[O] THEN UnboundTrap[dst];
            CB  ReadDblMds[@GlobalBase[GF].codebase];
            IF Odd[LowHalf[CB]] THEN CodeTrap[GF];
            nPC  proc.pc;
            IF nPC = 0 THEN UnboundTrap[dst];
            word  ReadCode[nPC / 2]; 
            nLF  Alloc[
                IF nPC MOD 2 = 0 THEN word.left ELSE word.right];
            nPC  nPC + 1;
            StoreMds[@LocalBase[nLF].globallink]  GF;
            StoreMds[@LocalBase[nLF].returnlink]  src
            END;

...

Design Note: It is important to notice that, after the Alloc completes, references to the new local frame nLF can not cause page faults, since Alloc references the first variable of the frame, and the frame overhead words are guaranteed to be in the same page.

Programming Note: It is illegal for a program to write-protect any page pointed to by the frame allocation vector. Such frames would be successfully removed from the frame heap by Alloc>, but would be lost when the subsequent write-protect fault occurred.

Programming Note: CodeTraps can be used to implement a variety of features that depend on detecting all control transfers into a program. For example, this mechanism can be used by software to map code segments out of virtual memory. It can also be used (in conjunction with an auxiliary bit) to detect the first time control is passed to a program.

To effect a frame transfer, XFER loads the state from the destination, obtaining the PC and global frame from the local frame and the code base from the global frame. In addition to UnboundTrap and CodeTrap, a frame transfer can also result in a ControlTrap if the destination frame is zero, This trap is used to implement port linkages (§9.4.5), as well as to detect uninitialized control links.

    frame =>
        BEGIN
        frame: FrameLink = MakeFrameLink[nDst];
        IF frame = LOOPHOLE[O] THEN ControlTrap[src];
        nLF  frame;
        GF  FetchMds[@LocalBase[nLF].globallink];
        IF GF = LOOPHOLE[O] THEN UnboundTrap[dst];
        CB  ReadDblMds[@GlobalBase[GF].codebase];
        IF Odd[LowHalf[CB]] THEN CodeTrap[dst];
        nPC  FetchMds[@LocalBase[nLF].pc];
        IF nPC = 0 THEN UnboundTrap[dst];
        IF type = trap THEN
            BEGIN
            StoreMds[@LocalBase[nLF].returnlink]  src;
            Disablelnterrupt[];
            END;
        END;
    ENDCASE;
...

If the destination is a frame and the XFER is performing a trap, it saves the source of thetransfer in the return link of the destination and disables interrupts (see §9.5.2).

If the original destination was an indirect control link, the original source and destination links are left above the top of the stack so that the context receiving control can access them (for example, the Link Byte instruction §9.4.3 or the Port In instruction §9.4.5).

Finally, XFER will optionally free the current local frame to the frame heap. This feature isused by the return instructions and XFER and Free to implement context destruction.

    IF push THEN
        BEGIN
        Push[LowHalf[dst]];
        Discard[]; Discard[];
        END;
    IF free THEN Free[LF];
    LF  nLF; PC  nPC;
    CheckForXferTraps[dst: dst, type: type];
    Push[src];
    END;

Design Note: Because the current frame is running, references to LF by Free cannot cause page faults (but, Free may fault on the Allocation Vector).

Design Note: Page faults due to Free cannot occur (see §9.5.2) because traps never free the source frame. If traps did specify free = TRUE, the trapped context would be discarded.

Programming Note: It is illegal for a program to unmap or write-protect its current local or global frame or to modify explicitly the dirty or referenced map flags of either frame's first page using the map instructions (§3.1.2).

9.4 Control Transfer Instructions

Several types of control transfers are implemented using the XFER primitive: local function calls, external function calls, nested function calls, returns, and port calls are described in this section. The use of XFER to implement traps is discussed in §9.5.

All control transfers except Return (§9.4.4) begin by storing the PC in the local frame. When stored, the PC points to the beginning of the next instruction The stored value is therefore the byte offset of the instruction to be executed when the current local frame is resumed. (If the instruction causes a trap or fault, this value of the PC will be overwritten with savedPC by the trap or fault routine, so that the instruction will be restarted.)

9.4.1 Local Function Call

Local function calls are used to transfer to a procedure located in the current code segment. These instructions are optimizations of the XFER mechanism, made possible by the fact that a particular code segment is compiled as a single unit. Using these instuctions, the compiler can build the information necessary to find the procedure that should be called into the code itself, rather than by using a procedure descriptor, which would be the normal case.

The Local Function Call instruction is an optimized version of the procedure descriptor form of XFER that does not modify the current global frame pointer or code base, In thiscase, there is no possibility of a CodeTrap.

LFC Local Function Call

LFC: PROCEDURE =
    BEGIN
    word: BytePair;
    nPC: CARDINAL;
    nLF: Local FrameHandle;
    StoreMds[@LocalBase[LF].pc]  PC;
    nPC  GetCodeWord [];
    IF nPC = 0 THEN UnboundTrap[LOOPHOLE[LONG[0]]];
    word  ReadCode[nPC / 2];
    nLF  Alloc[IF nPC MOD 2 = 0 THEN word.left ELSE word.right];
    nPC  nPC + 1;
    StoreMds[@LocalBase[nLF].globallink]  GF;
    StoreMds[@LocalBase[nLF].returnlink]  LF;
    LF  nLF; PC  nPC;
    CheckForXferTraps[
        dst: LOOPHOLE[ProcDesc[taggedGF: OR[GF, 1],
        pc: PC - 1]], type: localCall];
    END;

Design Note: As in XFER, after the Alloc completes, references to the new local frame nLF cannot cause page faults.

9.4.2 External Function Calls

The external function calls transfer control to a control link contained in the global frame or code segment. The following routine is used to obtain the link:

FetchLink: PROCEDURE [offset: BYTE] RETURNS [ControlLink] =
    BEGIN
    word: GlobalWord = FetchMds[@GlobalBase[GF].word];
    RETURN[IF word.codelinks THEN ReadDbl[CB - LONG[(offset + 1) * 2]]
    ELSE ReadDblMds[GlobalBase[CB] - (offset + 1) * 2]];
    END;

Links are stored either just before the overhead words of the global frame or in an area preceding the code segment. A bit in the flag word of the current global frame indicates the link location (§3.2.2.2).

Design Note: If the links are stored in the code segment, they must be contained in the same 64K bank as the code base. This ensures that the calculation of the address of the link will not underflow in the low-order word or cause a borrow from the high-order word. Since frames are always completely contained in a Main Data Space, this calculation is also accurate if the links are stored in the global frame. Note, however, that the links do not necessarily lie in the same page as the beginning of the global frame or code segment.

The external function calls (and some other instructions) all make use of the routine below, which first saves the PC in the current frame and then XFERs to the destination, supplying LF as the source. The standard default for free is specified.

Call: PROCEDURE [dst: ControlLink] =
    BEGIN
    StoreMds[@LocalBase[LF].pc]
    PC  PC;
    XFER[dst: dst, src: LF type: call]; 
    END;

Single-byte external call instructions are provided for the first thirteen external links. A two-byte version uses alpha as the link number, which allows up to 256 external references per module.

EFCn External Function Call n

EFCn: PROCEDURE [n: [0..12]] =
    BEGIN
    Call[FetchLink[n]];
    END;

EFCB External Function Call Byte

EFCB: PROCEDURE =
    BEGIN alpha: BYTE = GetCodeByte[];
    Call[FetchLink[alpha]];
    END;

The Stack Function Call instruction XFERS to a control link obtained from the top of the stack.

SFC Stack Function Call

SFC: PROCEDURE =
    BEGIN
    link: ControlLink = PopLong[];
    Call[link];
    END;

The following instruction XFERs to control links in the System Data Table described in §9.5. The SD contains control links for kernel procedures that implement runtime support routines. Control links for trap handlers (§9.5.1) are also contained in the SD.

KFCB Kernel Function Call Byte

KFCB: PROCEDURE =
    BEGIN
    alpha: SDIndex = GetCodeByte[];
    Call[ReadDblMds[@SD[alpha]]];
    END;

9.4.3 Nested Function Calls

The Link Byte instruction is executed on entry to nested procedures. It establishes the static link to the enclosing context (the local frame of the lexically enclosing procedure). Link Byte recovers the original destination link of the last XFER (normally an indirectcontrol link) from above the stack, subtracts alpha, and stores the result in local zero.

LKB Link Byte

LKB: PROCEDURE =
    BEGIN
    alpha: BYTE = GetCodeByte[];
    link: ShortControLink;
    Recover[]; link  Pop[];
    StoreMds[LF]  link - alpha;
    END;

Programming Note: Because only control transfers through indirect control links leave source and destination links above the top of the stack, the LKB instruction must be executed after control transfers are made using indirect control links.

Programming Note: Nested procedure variables can be represented not by a procedure descriptor, but by a pointer to a procedure descriptor (an indirect link). In this case, the descriptor is allocated in the local frame of the enclosing procedure at an offset known to the programmer. This offset is used in the LKB instruction at the beginning of the nested procedure, which then uses local zero as the static link to access the enclosing procedure's variables. In order for the pointer to the descriptor to be recognized as an indirect controllink, the descriptor must be allocated at an address equal to two modulo four.

9.4.4 Returns

The following instructions are used to return from a procedure, freeing its frame. Note that the PC is not saved in the current local frame, since the frame is about to be deallocated.

RET Return

RET: PROCEDURE =
    BEGIN
    dst: ControlLink = LONG[FetchMds[@LocalBase[LF].returniink]];
    XFER[dst: dst, src: 0, type: return, free: TRUE];
    END;

Programming Note: Although there are separate local and external function call instructions, there is a single return, so that a context need not be concerned with how it was called.

9.4.5 Coroutine Transfers

The coroutine instructions are used to transfer control through ports, which are two-word structures located in the Main Data Space. Ports have the following runtime structure:

PortLink: TYPE = POINTER TO Port;

Port: TYPE = MACHINE DEPENDENT RECORD [
    inport(0): Framelink,
    unused(1): UNSPECIFIED,
    outport(2): ControlLink];

Ports are allocated in memory so that PortLinks are indirect control links. That is, they are found at addresses of two modulo four. When control is directed into a port, the inport is used as the destination of the XFER. If the inport is non-zero, it contains a pointer to a framethat is said to be pending on the port (ready to receive control). Otherwise, a ControlTrap results. When control is directed out of a port, the outport is used as the destination of the XFER. The outport may contain any type of control link, including a frame, a procedure, orthe address of another port. If it contains zero, the port is not linked to another context, and a ControlTrap results. Port calls are compatible with procedure calls, because contro can leave a context using a port call and enter a context that uses a procedure call discipline (and vice versa). The various cases are shown in figures 9.2-4.

The Port Out instruction obtains the destination port link from the stack. It saves the current PC and sets the inport to the current context. It then XFERs to the outport, specifying the port itself (not the current context) as the source of the transfer. The Port Out instruction is always immediately followed statically by a Port In instruction, as shown in figure 9.2-4.

PO Port Out

PO: PROCEDURE =
    BEGIN
    reserved: unspecified = Pop[];
    port: PortLink = Pop[];
    StoreMds[@LocalBase[LF].pc]  PC;
    StoreMds[@port.inport]  LF;
    XFER[dst: ReadDblMds[@port.outport], src: port, type: port];
    END;

POR Port Out Responding

POR: PROCEDURE =
    BEGIN
    PO[];
    END;

Programming Note: There are two Port Out instructions, with different opcodes but identical semantics. The trap handler uses them to determine the intended usage of the port if a ControlTrap occurs on the transfer. By convention, a sending port uses PO, and a responding port uses POR [2].

Programming Note: The high-order word of a PortLink is not used and may be left uninitialized by the programmer.

The Port In instruction saves the return link in the outport; that link had been left above the stack by the XFER invoked by the preceeding transfer instruction Note that if the return link is zero, the Port In was preceded dynamically by a Return (or Return Zero), and the link is not saved. The instruction also clears the inport, so that any transfer directed at the port will cause a control trap.


(1) Q has transferred to P via the PO at Q1. Control in in P, but not yet at P1. Q is pending on q.

(2) P as executed the PO at P1, and control has passed to Q. P is now pending on p, but Q has not yet executed the PI at Q2.

(3) q as executed the PI at Q2, saving the link (an indirect link to p>) in q.outport. Any attempt to transfer to Q through q will trap, since q.inport has been cleared. P remains pending on p.
Figure 9.2 Port to Port Control Transfers

(1) Control is in P, before PI; p.outport contains a precedure descriptor for Q.

(2) P as executed the PO at PI, and Q has been created. P is now pending on p, and Q's return link points to p.

(3) Q has executed the RET which called XFER[dst: p, src: 0]. P has executed the PI at P2, which has cleared p's inport.
Figure 9.3 Port to Procedure Control Transfers

(1) Control is in P (a precedure), about to execute the SFC at P1. The stack contains an indirect link to q. Q is pending on q.

(2) Control has passed to Q, and the PI at Q1 has been executed. The inport has been cleared, and the outport contains P (a frame handle).

(3) Q has executed the PO at Q2, returning control to P through the outport. Q is again pending on q.
Figure 9.4 Port to Port Control Transfers

PI Port In

PI: PROCEDURE =
    BEGIN
    port: PortLink;
    src: ShortControlLink;
    Recover[]; Recover[];
    src  Pop[];
    port  Pop[];
    StoreMds[@port.inport]  O;  
    IF src # 0 THEN
        StoreMds[@port.outport]  src;
    END;

Programming Note: Because only control transfers made through indirect control links leave source and destination links above the top of the stack, the PI instruction must only be executed after control has been transferred using an indirect control link.

Programming Note: If a preemption occurs before the Port In completes execution, another process may enter the port, since a frame is still pending on it. This would eventually lead to a situation in which two processes were executing in the same local frame. For this reason, ports cannot be shared by multiple processes

9.4.6 Link Instructions

The load link instruction loads a control link (or other data) from the global frame or the code segment onto the stack.

LLKB Load Link Byte

LLKB: PROCEDURE =
    BEGIN
    alpha: BYTE = GetCodeByte[];
    PushLong[FetchLink[alpha]];
    END;

The read link instructions perform a single- or double-word push using a pointer obtained from the link area.

RKIB Read Link Indirect Byte

RKIB: PROCEDURE =
    BEGIN
    alpha: BYTE = GetCodeByte[];
    ptr: LONG POINTER = FetchLink[alpha];
    Push[Fetch[ptr]];
    END;

RKDIB Read Link Double Indirect Byte

RKDIB: PROCEDURE =
    BEGIN
    alpha: BYTE = GetCodeByte[];
    ptr: LONG POINTER = FetchLink[alpha];
    Push[Fetch[ptr]];
    Push[Fetch[ptr + 1]];
    END;

9.5 Traps

Traps indicate the occurrence of exceptional conditions encountered in the course of instruction execution. In some cases, a trap indicates that a serious error has occurred, one which precludes continued execution of the context (for example, a StackError). In other cases, the trap will cause a software trap handler to take some corrective action and continue normal execution (e.g., CodeTrap). The trap handler is invoked using an XFER, which itself might generate a nested trap.

Both the XFER code in §9.3 and the trap routines defined in this section obey the restart rule given in §10.4.3.)

9.5.1 Trap Routines

The following paragraphs summarize the traps that can be generated by the processor. Trap handlers for traps other than EscOpcodeTrap are represented by control links located at preassigned indexes in the System Data table, which resides at a fixed address within each Main Data Space. The location of the System Data table and the assignments of indexes to trap conditions are given in Appendix A.

SD: POINTER TO SystemData = LOOPHOLE[mSD];
SystemData: TYPE = ARRAY SDIndex OF ControlLink;

SDIndex: TYPE = [0..256);

Trap handlers for unimplemented ESC or ESCL opcodes are represented by control links located in the ESC Trap Table, which resides at a fixed address within each Main Data Space. The ESC Trap Table is indexed by opcode value. Its location is given in Appendix A.

ETT: POINTER TO EscTrapTable = LOOPHOLE[mETT];
EscTrapTable: TYPE = ARRAY BYTE OF Control Link;

A brief explanation of each trap is given below, together with a description of its parameters and a reference to the section(s) that call the trap routine. Traps are listed alphabetically.

BoundsTrap: PROCEDURE [] = {TrapZero[@SD[sBoundsTrap]]};

The Bounds Check instruction generates this trap in response to an out-of range value (§5.2).

BreakTrap: PROCEDURE [] = {TrapZero[@SD[sBreakTrap]]};

This trap is invoked by the Break instruction (§9.5.4).

CodeTrap: PROCEDURE [gf: GIobalFrameHandle] =
    {TrapOne[@SD[sCodeTrap], gf]};

An XFER generates this trap if the code base of the destination context is odd. The parameter is the global frame of the new context (§9.3).

ControlTrap: PROCEDURE [src: ShortControlLink] =
    {TrapOne[@SD[sControlTrap], src]};

This trap is generated by an XFER if the destination of a frame transfer is zero. The parameter is the source of the original transfer (§9.3).

DivCheckTrap: PROCEDURE [] =
    {TrapZero[@SD[sDivCheckTrap]]};

The Long Unsigned Divide instruction generates this trap if the quotientwould overflow a single word (235.5).

DivZeroTrap: PROCEDURE [] =
    {TrapZero[@SD[sDivZeroTrap]]};

An attempt to divide by zero generates this trap (§5.5).

EscOpcodeTrap: PROCEDURE [opcode: BYTE] =
    {TrapOne[@TT[opcode],opcode]};

This trap is generated when instruction execution detects an unimplemented ESC or ESCL opcode (§10.4.4.3).

OpcodeTrap: PROCEDURE [opcode: BYTE] =
    {TrapOne[@SD[sOpcodeTrap], opcode]);

This trap is generated when instruction execution detects an unimplemented opcode (§10.2.4).

RescheduleError: PROCEDURE [] =
    {TrapZero[@SD[sRescheduleError]};

This trap is generated by the scheduler when the scheduler was entered at an inappropriate time. Inappropriate entry may be caused by interrupts having been disabled while a process opcode causing scheduler entry was being executed. If interrupts were disabled and a page fault, write-protect fault, or frame fault caused entry to the scheduler, the RescheduleError may also be called (§10.4.1).

StackError: PROCEDURE [] =
    {TrapZero[@SD[sStackError]};

Any instruction that manipulates the evaluation stack may cause this trap if the stack routines detect that the stack pointer SP would become illegal as a result of the operation (§3.3.2).

UnboundTrap: PROCEDURE [dst: ControlLink] =
    {TrapTwo[@SD[sUnboundTrap], dst]};

An XFER generates this trap whenever it encounters a zero destination control link or a zero PC. The parameter is the destination of the original transfer.

HardwareError: PROCEDURE [] =
    {TrapTwo[@SD[sHardwareError]]);

Miscellaneous machine-dependent hardware errors generate this trap.

Design Note: There are three exceptions to the restart rule: in the eventof a stack error, a reschedule error, or an interrupt error, the stateof the processor is undefined. These three traps represent fatal software errors from which it is generally impossible to resume execution. In a stack error (§3.3.2), the trapped context is not resumable. In a reschedule error (§10.4.1) or an interrupt error (§10.4.4.3), no process may continue execution.

Programming Note: Resuming a context that has experienced a stack error produces undefined results, as does continuation of process-scheduling after a reschedule error or an interrupt error. The processor reports these three conditions for debugging purposesonly; they never occur in correct programs.

9.5.2 Trap Processing

When a trap occurs, the action taken is similar to a normal control transfer to the traphandler, with the following differences:

The trap mechanism stores the trap parameters starting at local zero in the handler's frame. There can be up to four words of parameters (there are currently at most three). Because some instructions, including many XFERS, leave information above the top of the stack, the entire stack must be preserved unmodified; therefore, trap parameters cannot be passed on the stack.

For similar reasons, the XFER performed by the trap routine does not save its source and destination links above the top of the stack (see the description of XFER in §9.3).

Programming Note: This implies that trap handlers can not in general be nested procedures or ports, since these programs begin with instructions (Link Byte and Port In) that access the control links left above the top of the stack by the previous XFER.

If the transfer performed by the trap routine specifies a frame as its destination, XFER stores the source of the transfer in the return link of the trap handler and disables interrupts.

Design Note: Because several processes can share a Main Data Space (and therefore share the trap handlers in its System Data table), fixed-frame trap handlers are not re-entrant and must run with interrupts disabled. They also cannot cause traps or faults. Programming Note: The use of fixed-frame trap handlers should be restricted to the most primitive performance monitoring and debugging functions.

Design Note: Because traps are implemented as control transfers, the MDS register and the PSB register are not modified by trap processing. This implies that the trap handler runs in the same MDS (and in the same process) as the trapped context.

The precise actions that must be taken by the processor when a trap occurs are shown by TrapZero (no parameters), TrapOne (one parameter), TrapTwo (one long parameter), and the common Trap routine.

TrapZero: PROCEDURE [ptr: POINTER TO ControlLink] =
    BEGIN
    Trap[ptr];
    ERROR Abort;
    END;

TrapOne: PROCEDURE [ptr: POINTER TO ControlLink, parameter: UNSPECIFIED] =
    BEGIN
    Trap[ptr];
    StoreMds[LF]  parameter;
    ERROR Abort;
    END;

TrapTwo: PROCEDURE [ptr: POINTERTO ControlLink, parameter: LONG UNSPECIFIED] =
    BEGIN
    Trap[ptr];
    StoreMds[LF]  LowHalf[parameter];
    StoteMds[LF + 1]  HighHalf[parameter];
    ERROR Abort;
    END;

Trap: PROCEDURE [ptr: POINTER TO ControlLink] =
    BEGIN
    handler: ControlLink = ReadDblMds[ptr];
    PC  savedPC; SP  savedSP;
    IF ValidContext[] THEN
        StoreMds[@LocalBase[LF].pc]  PC;
    XFER[dst: handler, src: LF, type: trap];
    END;

Design Note: The storing of the trap parameter(s) cannot cause a page fault, because the XFER has already guaranteed the presence of the trap handlers first four locals (and its overhead words).

The trap routine must check that the context is valid before saving the PC. This covers the occurrence of a trap during a process switch before a valid frame has been obtained (see §10.4.1).

Design Note: Because the frame is currently running, saving the PC can not cause a pagefault.

Since the processor will always re-establish the initial state of the current instruction, all traps appear to occur between instructions. If an instruction causes more than one trap, the traps will occur sequentially, and the processor will restart the instruction when the handler for each trap returns. Because instructions are restarted rather than continued from the point of an exception, there is no need for a trap handler to consider the effects of multiple traps on a single instruction, nor does the handler need to concern itself with the continuation of partially completed instructions.

9.5.3 Trap Handlers

The complete state of a context includes not only the current local frame LF, but the evaluation stack (§3.3.2) and the break byte (§9.5.4) as well. Instructions are provided to dump and load this state using a state uector, defined as follows:

StateHandle: TYPE = LONG POINTER TO Statevector;

StateWord: TYPE = MACHINE DEPENDENT RECORD [
    break(0: 0..7),
    stkptr(0: 8..14): BYTE];

StateVector: TYPE = MACHINE DEPENDENT RECORD [
    stack(0): ARRAY [0..StackDepth) OF UNSPECIFIED,
    word(14): StateWord,
    frame(15): LocalFrameHandle,
    data(16): BLOCK];

Design Note: The size of a state vector is processor dependent (§10.4.2.1). Its minimum size, cSV, is given in Appendix A.

The state instructions make use of the routines below to save and restore the break byte, the stack pointer (and savedSP), and the evaluation stack. Since there are never more than two valid entries above the top of the stack, a maximum of SP + 2 entries need be saved.

SaveStack: PROCEDURE [state: StateHandle] =
    BEGIN
    FOR sp: StackPointer IN [O..MIN[SP + 2, StackDepth]) DO
        Store[@state.stack[sp]]  stack[sp];
        ENDLOOP;
    Store[@state.word]  StateWord[break, SP];
    SP  savedSP  0;
    break  0;
    END;

LoadStack: PROCEDURE [state: StateHandle] =
    BEGIN
    word: StateWord = Fetch[@state.word];
    FOR sp: StackPointer IN [0..MIN[word.stkptr + 2, StackDepth]) DO
       stack[sp]  Fetch[@state.stack[sp]];
       ENDLOOP;
    SP  savedSP  word.stkptr;
    break  word.break;
    END;

The first instruction executed by a trap handler will normally be a Dump Stack, which will empty the stack by saving its contents in the handler's local frame, at an offset given by alpha.

DSK Dump Stack

DSK: PROCEDURE
    BEGIN
    alpha: BYTE = GetCodeByte[];
    State: POINTER TO StateVector = LOOPHOLE[LF + alpha];
    SaveStack[LengthenPointer[state]];
    END;

Programming Note: Since trap parameters are stored starting at local zero, the programmer must arrange that the state vector referenced by the Dump Stack instruction is not allocated in the first four frame locations.

When the handler is ready to continue execution of the trapped context, it must reload thestack. The Load Stack instruction is available for this purpose.

LSK Load Stack

LSK: PROCEDURE =
    BEGIN
    alpha: BYTE = GetCodeByte[];
    state: POINTER TO StateVector = LOOPHOLE[LF + alpha];
    LoadStack[LengthenPointer[state];
    END;

Since the entire stack is reloaded, it is not necessary to preserve the stack's old contents in case of faults while reloading. If the Load Stack does fault, the stack may be only partiallyloaded, but the entire operation will be retried when execution resumes. After the stack is reloaded, the handler must resume the trapped context. There are two instructions available for this purpose: one that frees the handlers frame, and one that enables interrupts The programmer provides the source and destination of a control transfer-in the trap handler's frame. Typically, the source is zero, and the destination is the original trapped context. This will retry the instruction that caused the trap.

TransferDescriptor: TYPE = MACHINE DEPENDENT RECORD [
    src(0): ShortControlLink,
    reserved(1): UNSPECIFIED,
    dst(2): ControlLink];

XF XFER and Free

XF: PROCEDURE =
    BEGIN
    ptr: POINTER TO TransferDescriptor = LOOPHOLE[LF + GetCodeByte[]];
    XFER[
        dst: ReadDblMds[@ptr.dst], src: FetchMds[@ptr.src],
        type: xfer, free: TRUE];
    END;

XE XFER and Enable

XE: PROCEDURE =
    BEGIN
    ENABLE Abort => ERROR;
    ptr: POINTER TO TransferDescriptor = LOOPHOLE[LF + GetCodeByte[]];
    StoreMDS[@LocalBase[LF].pc]  PC;
    XFER[dst: ReadDblMds[@ptr.dst], src: FetchMds[@ptr.src], type: xfer];
    Enablelnterrupts[];
    END;

Programming Note: It is the programmer's responsibility to ensure that XFER and Enable does not cause a trap or fault (see §9.5.2). This instruction is intended for use by fixed frame trap handlers, which must run with interrupts disabled.

Programming Note: Some traps indicate error conditions that will normally be handled by software executed in place of the trapped instruction; re-execution may therefore be inappropriate. For example, the unimplemented instruction trap handler may choose to emulate the effects of the offending instruction in software. In this case, it is always possible for the trap handler to complete the instruction by advancing the program counter of the trapped context (and perhaps also adjusting the contents of the stack).

9.5.4 Breakpoints

The single byte Break instruction causes a distinguished trap when encountered in the instruction stream. It is used for program debugging. To install a breakpoint, the programmer replaces the opcode of the broken instruction with a Break instruction, remembering the original opcode value. When the processor attempts to execute the broken instruction, a trap to a software-supplied breakpoint handler results. (The processor's break byte is normally zero.) BreakTrap is defined in §9.5.2.

BRK Break

BRK: PROCEDURE =
    BEGIN
    IF break = 0 THEN BreakTrap[]
    ELSE
       BEGIN
       Dispatch[break];
       break  0;
       END;
    END;

As with all traps, the first instruction of the breakpoint trap handler should be a Dump Stack, which will save the state of the broken context. To proceed from a break point, the programmer can replace the Break instruction with the original opcode; however, it is usually desirable to leave the breakpoint in place, by first inserting the original opcode into the break field of the state vector of the, broken context, then performing a Load Stack instruction. The Load Stack sets the processor's break byte from the state vector. The Break instruction notices a non-zero break byte and dispatches on it (§4.5.1, rather than performing a breakpoint trap; it then clears the break byte when the broken instruction completes execution.

Design Note: It is important to notice that the break byte is not cleared until the broken instruction has completed execution successfully. In particular, if the dispatch on the original opcode results in a trap or fault, the break byte must be saved with the state of the trapped or faulted process, and the break byte associated with the new context (established by the trap or fault routine) must remain undisturbed. In the code above, the Abort signal raised by the trap or fault routine prevents execution of the statement break.

Programming Note: It is possible to place a breakpoint anywhere except in the current breakpoint trap handler itself. Also note that, if the break byte is ever set to zBRK, infinite recursion occurs.

9.5.5 Xfer Traps

A method of trapping to software on each transfer of control, conditioned by the trapxfers flag in the global frame of the destination, is available. It is intended for performance measurement and debugging.

CheckForXferTraps: PROCEDURE [dst: ControlLink, type: XferType] =
    BEGIN
    IF Odd[XTS] THEN
       BEGIN
       word: GlobalWord = FetchMds[@GlobalBase[GF].word];
       IF word.trapxfers THEN
           BEGIN
           XTS  Shift[XTS, -1];
           Trap[@SD[sXferTrap] ! Abort => ERROR];
           StoreMds[LF]  LowHalf[dst];
           StoreMds[LF + l]  HighHalf[dst];
           StoreMds[LF + 2]  type;
           ERROR Abort;
           END;
       END
    ELSE XTS  Shift[XTS, -1];
    END;

[last edited 4/11/99 9:08PM]