Previous [TOC] Next

| 3 Memory Organization

This chapter describes the memory structures of the Mesa processor. It discusses the virtual memory, distinguished regions of the virtual memory called Main Data Spaces, and the programmer-accessible memories of the processor. This chapter also identifies most of the data structures residing in these memories used by the processor. The chapters on control transfers (§9) and the process mechanism (§10) define other structures in detail.

### 3.1 Virtual Memory

All Mesa processors implement a large virtual address space. Virtual memory is organized as a single uniform array of words shared by all processes, addressed by thirty-two bit virtual addresses. A virtual address is mapped into a real address before an actual fetch or store operation occurs. Virtual addresses are represented by either long or short pointers.

For mapping purposes, virtual and real memory are further structured as a uniform array of pages. A page is a contiguous array of 256 words whose address is a multiple of the page size. (Therefore, it lies on a page boundary.)

    PageSize: CARDINAL = 256;
    PageNumber: TYPE = LONG CARDINAL; -- [0..224)
    Page: TYPE = ARRAY [0..PageSize) OF UNSPECIFIED;

Note: Although a `PageNumber` is actually a subrange of `LONG CARDINAL`, the current version of the Mesa language does not support this feature.

Both virtual and real memory consist of up to 224 pages (232 sixteen-bit words).

    RealPageNumber: TYPE = PageNumber;
    VirtualPageNumber: TYPE = PageNumber;

A block of 256 pages aligned on a 64K-word boundary is called a bank. Unless otherwise noted, all memory sizes are stated in units of sixteen-bit words; for example, banks are 64K words.

A virtual address occupies two words: the smallest virtual address is zero and the largest is 232-l. The most significant bit of the address is numbered zero. The least significant is numbered thirty-one. Virtual addresses are represented by values of type `LONG POINTER`. As with all `LONG` data types, when a long pointer is stored in memory, the least significant word appears at the lower-numbered address (§2.3.1).

Within distinguished regions of the virtual memory, called Main Data Spaces, data can be referenced using short pointers. These addresses occupy a single word and are represented by values of type `POINTER`. §3.2 discusses the structures contained in Main Data Spaces and the conversion of short to long pointers .

Design Note: Mesa processors may implement virtual and real address spaces smaller than 232 words (see below). Regardless of the actual size of virtual memory, long pointers always occupy two words, and the unused bits must be zero.

### 3.1.1. Virtual Memory Mapping

Virtual addresses are mapped into real addresses via the mapping mechanism. The implementation of the mapping operations is processor-dependent, and it is modeled in this document by the operations ReadMap and WriteMap. Logically, these operations implement an array of real page numbers indexed by virtual page number, except that the array can have holes, allowing for an associative or hashed implementation.

The address-translation process is identical for all memory accesses, whether they originate from the processor or from I/O devices. There is no method for bypassing the address-translation mechanism and directly referencing a main memory location using a real address. The virtual-to-real mapping can always be determined using the map instructions (§3.1.2).

Like virtual memory, real memory is referenced by thirty-two bit addresses in the range [0..223-1). However, the real address space is not necessarily contiguous or complete; there may be gaps where no real memory resides, and some models of the processor may implement less than 232 words of real memory. The size of a gap in the real address space must always be a multiple of the page size and begin on a page boundary.

The mapping mechanism identifies the real page that corresponds to a given virtual page (if any). Each virtual page is mapped individually, and a contiguous region of virtual memory does not necessarily correspond to a contiguous block of real memory. A thirty-two bit virtual address is mapped into a thirty-two bit real address, as illustrated in Figure 3.1.

The mapping mechanism is described by an array, indexed by the virtual page number, containing the associated real page numbers. It also contains the access flags, some of which are processor-dependent. The flags have the following format, although some reserved bits may not be present in all implementations of the processor:

    MapFlags: TYPE = MACHINE DEPENDENT RECORD [
        reserved(0: 0..12): UNSPECIFIED[O..17777B],
        protected(0: 13..13): BOOLEAN,
        dirty(0: 14..14): BOOLEAN,
        referenced(0: 15..15): BOOLEAN];

Design Note: The processor returns zero as the value of each unimplemented reserved bit. Any unimplemented bits supplied by the programmer when writing the map are ignored.

Figure 3.1 Virtual Memory Mapping

The flags encode access properties of the real page, if one is assigned. These bits can be read and written both by the processor and by the programmer using the map instructions defined in §3.1.2. Three of the flags, protected, dirty, and referenced, are defined by the architecture. Other processor-dependent flags (up to thirteen) may also be defined. The write-protect bit (protected) is set by the programmer. It prohibits writing into the page, causing a write-protect fault if a store is attempted. The dirty bit (dirty) is set by the processor if a store is done into a non-write protected page. The referenced bit (referenced) is set by the processor on any read or write access of a word within the page.

A distinguished encoding of the flags called vacant signifies that the virtual page is not present in real memory (that is, it is unmapped). If a read or write operation is performed on a page with flag bits set to vacant, a page fault occurs.

    Vacant: PROCEDURE [flags: MapFlags] RETURNS [BOOLEAN] =
        BEGIN
        RETURN[flags.protected AND flags.dirty AND ~flags.referenced];
        END;

The mapping operation is defined by the following routine, which maps a virtual address into a real address. Both types of addresses are represented by `LONG POINTER`s, but the Mesa Memory Organization dereferencing operator () is applied only to real addresses in the instruction descriptions that follow.

    Map: PROCEDURE [virtual: LONG POINTER, op: (read, write}]
        RETURNS [real: LONG POINTER] =
        BEGIN
        mf: MapFlags;
        rp: RealPageNumber;
        adrs: LONG CARDINAL = LOOPHOLE[virtual];
        vp: VirtualPageNumber = adrs/PageSize;
        wa: LONG CARDINAL = adrs MOD PageSize;
        [flags: mf, real: rp]  ReadMap[vp];
        IF Vacant[mf] THEN PageFault[virtual];
        IF op = write THEN
            IF mf.protected THEN WriteProtectFault[virtual]
            ELSE mf.dirty  TRUE;
        mf.referenced  TRUE;
        WriteMap[virtual: vp, flags: mf, real: rp];
        RETURN[LOOPHOLE[rp * PageSize + wa]];
        END;

Note: The PageFault and WriteProtectFault routines do not return control to Map. Instead, they raise the Abort signal (§10.1.1).

The operations ReadMap and WriteMap are implementation-dependent, and are described by the following interface:

    ReadMap PROCEDURE [virtual: VirtualPageNumber]
        RETURNS [flags: MapFlags, real: RealPageNumber];

    WriteMap: PROCEDURE [
        virtual: VirtualPageNumber, flags: MapFlags, real: RealPageNumber];

These operations have the following properties (see also §3.1.2):

It is illegal to attempt to map more than one virtual page to the same real page. This restriction allows an associative or hashed implementation of the map in which there is only one map entry for each real memory page.

In the case where ReadMap returns flags indicating vacant, the value of the real page number returned by the operation is undefined.

In the case where WriteMap is supplied with flags indicating vacant, the value of the real page number supplied by the caller is ignored.

Implementation Note: Each implementation of the processor may handle out-of-bounds virtual addresses differently. The hardware may be designed to make ReadMap and WriteMap return the appropriate flags for this condition. Otherwise, SetMap and GetMapFlags can be used to do address checking.

Programming Note: The maximum size of virtual memory can be determined by attempting to map a real page to each possible virtual page and then checking the flags of its map entry for vacant.

### 3.1.2 Memory Map Instructions

The map instructions are used to maintain the correspondence between virtual and real pages. The SetMap instruction replaces an entry in the map. GetMapFlags reads the flags and real page number from a map entry, given a virtual page number; SetMapFlags reads an entry and updates it with new flags obtained from the stack, provided the flags do not indicate vacancy. Note that SetMap and SetMapFlags must atomically update the map, and that no mapping operations may occur while the map is being updated.

Implementation Note: The atomicity requirements on SetMap and GetMapFlags may be replaced with a rule allowing only one processor in the system ever to write the map. Such a rule would imply that the privileged processor must preset the map flags for each addressing operation performed by the other processors or I/O controllers.

Programming Note: It is illegal to map more than one virtual page to the same real page, so the results of such an operation are undefined. A detailed discussion of the properties of the map can be found in the previous section.

The stack and the Push(Long) and Pop(Long) routines are defined in §3.3.2.

#### SM Set Map

If the flags specify that the page is vacant, Set Map ignores the real page number, except to pop it from the stack.

    SM: PROCEDURE =
        BEGIN
        mf: MapFlags = Pop[];
        rp: RealPageNumber = PopLong[];
        vp: VirtualPageNumber = PopLong[];
        WriteMap[virtual: vp, flags: mf, real: rp];
        END;

#### GMF Get Map Flags

If the flags returned indicate a vacant map entry, the real page number is undefined.

    GMF: PROCEDURE =
        BEGIN
        mf: Mapflags;
        rp: RealPageNumber;
        vp: VirtualPageNumber = PopLong[];
        [flags: mf, real: rp]  ReadMap[vp];
        Push[mf]; PushLong[rp];
        END;

#### SMF Set Map Flags

If the old flags indicate a vacant entry, the real page number is undefined, and the new flags taken from the stack are ignored.

    SMF: PROCEDURE =
        BEGIN
        mf: Mapflags;
        rp: RealPageNumber;
        newMf: MapFlags = Pop[];
        vp: VirtualPageNumber = PopLong[];
        [flags: mf, real: rp]  ReadMap[vp];
        Push[mf];
        PushLong[rp];
        IF ~Vacant[mf] THEN
            WriteMap[virtual: vp, flags: newMf, real: rp];
        END;

Programming Note: SetMapFlags cannot change the status of an entry from vacant to non-vacant, since that would require a new real page number. SetMap must be used for this purpose.

### 3.1.3 Virtual Memory Access

In the code that follows, the Fetch and Store routines are used to perform the mapping operation. They return a `LONG POINTER` that is the real address produced by Map. This notation allows the use of the Mesa operator () to dereference the pointers Wherever this operator appears, a real memory access takes place, and all real memory accesses are denoted by this operator. There are no virtual address dereferences in this document, and the code does not make use of Mesa's implicit pointer-dereferencing rules Notice that wherever calls on Fetch or Store appear, a page fault or write-protect fault might result (in the form of an Abort signal (see §10.4.3).

    Fetch PROCEDURE [virtual: LONG POINTER]
        RETURNS [real: LONG POINTER] =
        BEGIN
        RETURN[Map[virtual, read]];
        END;

    Store: PROCEDURE [virtual: LONG POINTER]
        RETURNS [real: LONG POINTER] =
        BEGIN
        RETURN[Map[virtual, write]];
        END;

To allow convenient access to double-word structures, the following operation is also defined, which checks for faults on each word of the data:

    ReadDbl: PROCEDURE [virtual: LONG POINTER]
        RETURNS [data: LONG UNSPECIFIED] =
        BEGIN
        temp: Long;
        temp.low  Fetch[virtual];
        temp.high  Fetch[virtual + 1];
        RETURN[LOOPHOLE[temp]];
        END;

Design Note: There are currently no requirements to provide a double-word store operation that is atomic with respect to page faults (see §4.6.1).

### 3.1.4 Virtual Memory Data Structures

This section summarizes the data structures of the architecture that are global to the entire virtual memory. Other structures are local to and replicated in each Main Data Space, and are described in §3.2.2. The overall structure of virtual memory is illustrated in Figure 3.2.

### 3.1.4.1 Reserved Locations

A contiguous area beginning at page zero of virtual memory is reserved for the booting process (see §4.7). Page zero normally is not used thereafter. It should not be allocated by the programmer, so that most uses of zero long pointers will cause faults.

    PageZero: LONG POINTER = LOOPHOLE[LONG[O]];

During booting, the initialization process may construct and store in main memory information about the machine configuration, device and controller identification, diagnostic information, and error status, in addition to the software necessary for initial program bootstrap. The format, content, and size of this area is processor-dependent; however, it is always contained within the first 64K of virtual memory (called bank zero) beginning at page zero.

    BootArea: LONG POINTER TO BootData = LOOPHOLE[LONG[O]];
    BootData: TYPE = BLOCK;

On most processors, one or more pages are reserved for communication between I/O devices or controllers and the processor. The format, content, size, and location of this area is processor-dependent; however, it is always contained within the first 64K of virtual memory.

    IOArea: LONG POINTER TO IOData;
    IOData TYPE = BLOCK;

Other reserved virtual memory locations may be assigned by the programmer. Real memory locations may be reserved for I/O devices, but these areas must be mappable to any virtual memory address by the programmer.

Figure 3.2 Virtual Memory Structure

### 3.1.4.2 Process Data Structures

The Process Data Area (PDA) contains information recording the state of each process and a pool of state vectors used to save the state of a preempted process. Substructures of the `PDA` support the handling of faults, interrupts, and timeouts.

    PDA: LONG POINTER TO ProcessDataArea;

The structure and content of the Process Data Area are described in §10.1.1. The location of the `PDA` is defined in Appendix A.

### 3.1.4.3 Code Segments

An arbitrary number of code segments may be allocated anywhere in virtual memory other than in the reserved locations. (The BootArea may include code, however.) A code segment contains read-only instructions and constants for the procedures that comprise a Mesa program module; it is never modified during the course of normal execution. A code segment is relocatable without modification; no information in a code segment depends on its location in virtual memory.

Figure 3.3 Code Segment

The beginning of the currently-executing code segment is pointed to by the `CB` register (the code base, a long pointer). The code segment is quad-word aligned (that is, `CB` modulo 4 = 0), and no part of a code segment may cross a 64K word boundary. These restrictions must be enforced by the programmer.

    CodeSegment: TYPE = MACHINE DEPENDENT RECORD [
        available(0): ARRAY [0..4) OF UNSPECIFIED,
        code(4): BLOCK];

Note: The array code is of zero length, and is just a place-holder in the record declaration for the beginning of the actual code bytes for the code segment.

In addition to a small amount of space available to the programmer, the code segment may contain a number of control links located immediately before the word pointed to by the code base (control links are described in §9.1). These links are used to call procedures or reference variables in other program modules. The links must also be contained in the same 64K bank as the rest of the code segment.

The program counter (`PC`) points to instruction or operand bytes in the code segment. It is a byte offset, relative to the code base. The code bytes are addressed left-to-right within a word, byte zero being bits zero through seven, byte one being bits eight to fifteen. Since the program counter is sixteen bits, it can reference up to 64K bytes of code starting at the code base. (This is the maximum size of a code segment.)

Design Note: It is illegal for a program to unmap the page to which the `PC` currently points, to clear the referenced bit, or to modify the dirty bit of that page. It is also illegal to write into the current code segment pointed to by `CB`.

Implementation Note: These restrictions allow the processor to cache a portion of the current instruction stream and the map entry of the current code page, and to set its map flags only when the page is first referenced.

Several instructions use the code base in conjunction with a word offset into the code segment to obtain operands. These instructions call the following routine:

    ReadCode: PROCEDURE [offset: CARDINAL]
        RETURNS [UNSPECIFIED] =
        RETURN[Fetch[CB + LONG[offset]]];
        END;

Programming Note: Because code segments do not cross 64K boundaries, the calculation `CB + LONG[offset]` can be implemented as a short addition of the `offset` to the least significant word of the code base, with no possibility of overflow into the high-order word.

### 3.2 Main Data Spaces

A Main Data Space (`MDS`) is a contiguous region of 64K words of virtual memory. All short pointers access memory locations within an `MDS`, and all local and global frames (§3.2.2.2) are allocated within an `MDS`. The purpose of Main Data Spaces is to allow the most commonly used data structures to be referenced by single word rather than long (double word) pointers.

    MdsHandle: TYPE = LONG POINTER TO MainDataSpace;
    MainDataSpace TYPE = BLOCK;

Main Data Spaces are 64K-word aligned and thus do not cross 64K word boundaries. Several `MDS`s can be allocated in virtual memory, but only one is current; its address is contained in the thirty-two bit `MDS` register (§3.3.1).

### 3.2.1 Main Data Space Access

A short pointer is a sixteen-bit quantity that addresses a location within the current `MDS` relative to its base. To construct a thirty-two bit virtual address from a short pointer, it is simply added to the `MDS` register. The following routine is used to perform this conversion:

    LengthenPointer: PROCEDURE [ptr: POINTER]
        RETURNS [LONG POINTER] =
        BEGIN
        offset: CARDINAL = LOOPHOLE[ptr];
        RETURN[MDS + LONG[offset]];
        END;

Design Note: Because the `MDS` is 64K-word aligned and short pointers are restricted to a 64K range within the `MDS`, a concatenation operation can replace the addition that appears above. All operations on short pointers are performed modulo 216, ignoring overflow.

Programming Note: A Main Data Space can be less than 64K, but the processor is ignorant of the size of the current `MDS`. It is up to the programmer to ensure that short pointers do not exceed the actual size of the `MDS`.

The Lengthen Pointer instruction converts a short pointer to a long pointer using LengthenPointer. Notice that it treats zero (the standard value of `NIL`) as a special case.

#### LP Lengthen Pointer

    LP: PROCEDURE =
        BEGIN
        ptr: POINTER = Pop[];
        PushLong[
            IF ptr = LOOPHOLE[O] THEN LONG[O]
            ELSE LengthenPointer[ptr]];
        END;

The routines below are defined in terms of Fetch, Store and ReadDbl (§3.1.3) for mapping short pointers. They use the value of the `MDS` register to lengthen the short pointers.

    FetchMds: PROCEDURE [ptr: POINTER]
        RETURNS [real: LONG POINTER] =
        BEGIN
        RETURN[Fetch[LengthenPointer[ptr]]];
        END;

    StoreMds: PROCEDURE [ptr: POINTER]
        RETURNS [real: LONG POINTER] =
        BEGIN
        RETURN[Store[LengthenPointer[ptr]]];
        END;

    ReadDblMds: PROCEDURE [ptr: POINTER]
        RETURNS [data: LONG UNSPECIFIED] =
        BEGIN
        RETURN[ReadDbl[LengthenPointer[ptr]]];
        END;

### 3.2.2 Main Data Space Data Structures

The following sections summarize the data structures contained in each Main Data Space. These include page zero, the control-transfer data structures, and local and global frames. Other structures in the `MDS` may be allocated by the programmer.

### 3.2.2.1. Reserved Locations

The data structures given in this section are located at fixed addresses in each Main Data Space; when not specified here, their locations are defined in Appendix A. Page zero of each `MDS` is not normally used (except during the booting process; see §4.7). It should not be allocated by the programmer, so that most references through zero short pointers will cause faults.

Each Main Data Space contains an Allocation Vector `(AV)`, a System Data table `(SD)`, and an ESC Trap Table (`ETT`). These data structures are used by the control-transfer mechanism described in detail in §9. A brief summary is contained below:

    AV: POINTER TO AllocationVector;

The procedure-calling mechanism allocates space for local variables dynamically from a frame heap, rather than a stack. This method allows for arbitrary control-transfer disciplines in addition to simple call-return. It also allows several processes to share the same heap. The Allocation Vector is used to maintain the heap and to simplify the allocation and deallocation of frames, so that the common cases can be implemented by the processor. The details of the allocation mechanism are described in §9.2.

    SD: POINTER TO SystemData;

The System Data table is used to contain pointers (in the form of control links; see §9.1) to the trap-handling routines called when the processor determines that execution of the current instruction cannot be completed. (Details of the trap mechanism are described in §9.5.) This table is also used to contain pointers (also in the form of control links) to commonly used runtime facilities (see §9.4.2).

    ETT: POINTER TO EscTrapTable;

The ESC Trap table is used to contain pointers (in the form of control links; see §9.1) to trap handling routines called when the program executes an ESC or ESCL opcode which is implemented in software. (Details of the trap mechanism are described in §9.5.)

### 3.2.2.2 Local and Global Frames

To minimize the amount of addressing information needed to specify the location of an operand (and to maximize locality of reference), variables declared in Mesa programs and procedures are stored in frames and referenced relative to the beginning of these structures. Frames are contiguous linear structures in virtual memory that reside entirely within a Main Data Space. They are referenced relative to the `MDS` register using short pointers.

Programming Note: Except for the restriction that frames are contained entirely within a Main Data Space, the maximum size of a frame is not specified by the architecture.

Frames are of two types.

- Global frames contain the global variables declared in a program module. They are allocated statically when the module is loaded.
- Local frames contain the local variables declared in a procedure. They are allocated dynamically when the procedure is called, and they are deallocated when it returns. In addition to local and global variables, frames contain a small amount of overhead information used to record the size of the frame along with the linkages between procedure calls, between procedures and their containing modules, and between modules and their corresponding code segments. The details are described below.

Global Frames

A global frame represents an instance of a program module. It contains the module's globally-declared variables, preceded by a few overhead words. The first global variable is called global zero, the next global one, and so on.

    GlobalFrameHandle: TYPE = POINTER TO GlobalVariables;
    GlobalVariables TYPE = BLOCK;

Design Note: Global zero must be quad-word aligned. The overhead words and the first four global variables must lie in the same page. This alignment simplifies page-faulting.

Figure 3.4 Global frame

The overhead words contain the location of the code segment from which instructions will be fetched when the module executes (the codebase field). These words also contain the flag bits trapxfers and codelinks used during control transfers §9.3). Their remaining fields are available for use by the software.

    GlobalFrameBase: TYPE = POINTER TO GlobalOverhead;

    GlobalWord = MACHINE DEPENDENT RECORD [
        available(0: 0..13): [0..37777B],
        trapxfers(0: 14..14): BOOLEAN,
        codelinks(0: 15..15): BOOLEAN];

    GlobalOverhead: TYPE = MACHINE DEPENDENT RECORD [
        available(0): UNSPECIFIED,
        word(1): GlobalWord,
        codebase(2): LONG POINTER TO CodeSegment,
        global(4): GlobalVariables];

Note: The array GlobalVariables is of zero length, It is just a place-holder in the record declaration for the starting address of the global variables.

The following routine is used to convert a global frame handle to a pointer to its overhead words:

    GlobalBase: PROCEDURE [frame: GlobalFrameHandle]
        RETURNS [GlobalFrameBase] =
        BEGIN
        RETURN[LOOPHOLE[frame - SIZE[GlobalOverhead]]];
        END;

Design Note: If a program modifies the overhead words of its own global frame, this modification may have no effect on their values as seen by the processor until the next control transfer into that module. This feature allows the processor to cache this (read only) information in internal registers.

In addition to the overhead words, a number of control links can be located immediately before the global frame's overhead words. These links are used to call procedures and to reference variables in other program modules. Control links and the codelinks bit are discussed in §9. Also, see the Load Link instruction in §9.4.2.

Local Frames

A local frame represents an instance of a procedure. It contains the procedure's locally-declared variables, preceded by a few overhead words. The first local variable is called local zero, the next local one, and so on.

    LocalFrameHandle: TYPE = POINTER TO LocalVariables;
    LocalVariables TYPE = BLOCK;

Design Note: Local zero and the overhead words must be quad-word aligned. The overhead words and the first four local variables must lie in the same page. This alignment simplifies page-faulting.

The overhead words contain the byte-relative location in the code segment from which instructions will be fetched when the procedure executes (the pc field). The globallink points to the procedure's global frame. It is used to gain access to the procedure's global variables. (It points to global zero, not to the overhead words.) The returnlink is a control link that normally points to the local frame of the procedure that created the current local frame (by a transfer of control; see §9.3). The overhead words also contain the frame's size, represented by a frame-size index (§9.2). The remaining field is available for use by the software.

Figure 3.5 Local frame

    LocalFrameBase: TYPE = POINTER TO LocalOverhead;

    LocalWord: TYPE = MACHINE DEPENDENT RECORD [
        available(0: 0..7): BYTE,
        fsi(0 8..15): FSIndex];

    LocalOverhead: TYPE = MACHINE DEPENDENT RECORD [
        word(0): LocalWord,
        returnlink(1): ShortControlLink,
        globallink(2): GlobalFrameHandle,
        pc(3): CARDINAL,
        local(4) LocalVariables];

Note: The array LocalVariables is of zero length. It is just a place-holder in the record declaration for the starting address of the local variables.

The following routine is used to convert a local frame handle into a pointer to its overhead words.

    LocalBase: PROCEDURE [frame: LocalFrameHandle]
        RETURNS [LocalFrameBase] =
        BEGIN
        RETURN[LOOPHOLE[frame - SIZE[LocalOverhead]]];
        END;

### 3.2.3 Frame Overhead Access

The overhead instructions are used to access overhead words of local and global frames. Read Overhead Byte obtains a pointer to a frame from the stack and moves a word from the overhead of that frame to the stack. Write Overhead Byte obtains a pointer to a frame from the stack and moves a word from the stack to the overhead of that frame.

Programming Note: Overhead words of frames must be accessed only by the overhead instructions. This restriction allows implementations to cache overhead words.

Programming Note: The programmer must ensure that the alpha byte (§4.2) in the overhead instructions is within the interval [l..4].

#### ROB Read Overhead Byte

    ROB: PROCEDURE =
        BEGIN alpha BYTE = GetCodeByte[];
        ptr: POINTER = Pop[];
        IF alpha ~IN[1..4] THEN ERROR;
        Push[FetchMds[ptr - alpha]];
        END;

#### WOB Write Overhead Byte

    WOB: PROCEDURE =
        BEGIN
        alpha BYTE = GetCodeByte[];
        ptr: POINTER = Pop[];
        IF alpha ~IN[1..4] THEN ERROR;
        StoreMds[ptr - alpha]  Pop[];
        END;

### 3.3 Processor Memories

This section describes those processor memories (usually called registers) visible to the programmer. An implementation of the architecture will typically include other internal registers as well. Several control registers are used to direct the execution of programs The evaluation stack, which replaces the general-purpose registers found in most processor architectures, is also described. The data and status registers available to the programmer are listed, and the instructions used to access registers are defined.

### 3.3.1 Control Registers

The registers described below designate the process currently being executed by the processor, the Main Data Space in which it is executing, the frames to which it has direct access, and the location of the instructions being interpreted. All of the registers declared as pointer types contain virtual-memory addresses.

The state of the current process is recorded in a Process State Block (`PSB`). Its index into a table of such blocks located in the Process Data Area is contained in the register `PSB`.

    PSB: Psblndex;

The process state block contains, among other things, a pointer to the `MDS` in which the process is running. It also contains either a pointer to the process' local frame or a pointer to another structure (a State Vector) containing the process' evaluation stack (§3.3.2) and frame pointer. Details of the process structures are contained in §10.

The virtual address of the current Main Data Space is contained in the `MDS` register. The value of this register normally is changed only by a process switch (see §10). It can also be read and written using the register instructions (§3.3.4).

    MDS: MdsHandle;

Implementation Note: Because the address of the `MDS` is always a multiple of 64K, `MDS` can be implemented using a sixteen-bit register.

Before a program can be run, an execution environment called a context must be established for it. In addition to a Main Data Space, a context includes:

- a pointer to the program's code segment,
- a pointer to its current instruction (the program counter), and
- pointers to its local and global data.

This information is stored in the overhead words of the program's local and global frame (§3.2.2.2).

The processor includes dedicated registers (described below) that contain pointers to the current local frame, global frame, and code segment, along with the current program counter. These registers are updated by the control-transfer instructions described in §9. Notice that a local frame is sufficient to determine all of the other registers: given a local frame pointer, the program counter is obtained from its pc field, the global frame pointer from its globallink field, and the code segment address from the global frame's codebase field. For this reason, the terms frame and context are often used interchangeably in the PrincOps, as are the terms control transfer and context switch.

The address of the local frame of the current context is contained in the sixteen-bit register, `LF` (a short pointer). Its value is obtained directly from a Process State Block, from a State Vector, or via a control transfer (§9).

    LF: LocalFrameHandle;

To access the overhead words of the current local frame, the procedure `LocalBase[LF]` is used. The register `LF` points to local zero, not to the overhead words. The format of a local frame is defined in §3.2.2.2.

The address of the global frame of the current context is contained in the sixteen bit register `GF` (a short pointer). Its value is obtained using `LocalBase[LF].globallink`.

    GF: GlobalFrameHandle;

To access the overhead words of the current global frame, the procedure `GlobalBase[GF]` is used; the register `GF` points to global zero, not to the overhead words. The format of a global frame is defined in §3.2.2.2.

The address of the code segment of the current context is contained in the register `CB` (the code base, a long pointer). Its value is obtained using `GlobalBase[CB].codebase`. The format of a code segment is described in §3.1.4.3.

    CB: LONG POINTER To CodeSegment;

The current offset into the code stream is contained in the register `PC` (the program counter). It contains the byte offset, relative to the code base, `CB`, of the next byte to be fetched. It is obtained initially (on a control transfer) using `LocalBase[LF].pc` or from an entry vector.

    PC: CARDINAL;

Except during execution of jump instructions and control transfers, the is maintained by the instruction-fetch routine GetCodeByte described in §4.3.

### 3.3.2 Evaluation Stack

The Evaluation Stack (usually just called the stack) is an array of registers normally accessed in a last in, first out manner. It is used as the source and destination of most transfers to and from memory. It is also used to pass parameters and results from one context to another during control transfers. Most arithmetic and logical operators also obtain their operands from the stack and return their results to the stack.

Figure 3.6 Evaluation Stack

The stack is represented by an array of StackDepth words and the Push and Pop routines. The variable `SP` (the stack pointer) indexes the next word above the top of the stack, so that the stack is empty when `SP = 0` and full when `SP = StackDepth`. The StackCount routine returns the number of words currently on the stack. The value of `cSS`, the stack size, is given in Appendix A.

    StackDepth: CARDINAL = cSS;
    StackPointer: TYPE = [0..StackDepth);
    stack: ARRAY [0..StackDepth) OF UNSPECIFIED;

    StackCounter: PROCEDURE RETURNS [StackPointer] =
        BEGIN
        RETURN[SP];
        END;

Push (PushLong) adds a word (two words) to the top; Pop (PopLong) removes the top word (two words) from the stack. If a push or pop would cause the stack pointer to be incremented or decremented out of range, a trap is generated.

Programming Note: The state of the stack after a stack error is undefined. Such an error is always fatal: it is illegal to resume a program that has generated a stack error (§4.6.1, §9.5).

Implementation Note: A stack error must always be detected by the processor, but it need not be reported during the execution of the instruction that caused it. This allows for pipelining in the arithmetic unit of the processor. A speedy report about the stack error (by the processor) is helpful for debugging, however. Otherwise, if another process switch occurs, the wrong process may be indicated as having a problem.

    Push: PROCEDURE [data: UNSPECIFIED] =
        BEGIN
        IF SP = StackDepth THEN StackError[];
        stack[SP]  data;
        sp  SP + 1;
        END;

    Pop: PROCEDURE RETURNS [UNSPECIFIED] =
        BEGIN
        IF SP = 0 THEN StackError[];
        SP  SP - 1;
        RETURN[stack[SP]];
        END;

    PushLong: PROCEDURE [data: LONG UNSPECIFIED] =
        BEGIN
        Push[LowHalf[data]];
        Push[HighHalf[data]];
        END;

    PopLong: PROCEDURE RETURNS [LONG UNSPECIFIED] =
        BEGIN
        long: Long;
        long.high  Pop[];
        long.low  Pop[];
        RETURN[LOOPHOLE[long]];
        END;

Note that double-word quantities are placed on the stack so that the least significant word is at the lower-numbered stack index (that is, on the bottom).

The stack is the primary source of instruction operands and the primary destination of results. The load instructions push words from memory onto the stack. The store instructions pop the stack into memory. The conditional jump instructions test words on the top of the stack and branch based on the result. The arithmetic instructions (or operands) pop their operands from the stack and push a result back onto the stack. Indirect instructions find their pointers on the stack.

Normally, the stack may contain results of previous computations that are to be combined with the result of the current instruction by execution of the operations following. However, a few instructions are minimal stack; that is, they require that the stack be empty except for their operands. These instructions call the following routine after popping their operands from the stack:

    MinimalStack: PROCEDURE =
        BEGIN
        IF SP # O THEN StackError[];
        END;

Some operations leave results or partial results above the top of the stack, that is, at `stack[SP]` and . These results are not normally used, but they can be obtained using a Recover instruction (§5.1), which increments the stack pointer without disturbing the stack's contents. There is a corresponding Discard instruction that discards the top element of the stack by decrementing the stack pointer. These instructions are implemented using the following routines:

    Recover: PROCEDURE =
        BEGIN
        IF SP = StackDepth THEN StackError[];
        SP  SP + 1;
        END;

    Discard: PROCEDURE =
        BEGIN
        IF SP = 0 THEN StackError[];
        SP  SP - 1;
        END;

The Multiply instruction (§5.5) provides an example of the use of Recover. It leaves the most significant word of a double-word result above the top of the stack. This allows a single instruction to function as both a single and a double-precision operation.

In no cases are more than two words left above the top of the stack, and at most SP + 2 elements of the stack need be stored when its contents are saved (see §9.5.3).

Since the stack may not actually be implemented as an array, certain words left above the top of the stack may be lost. In particular, if more than two Recover instructions are executed sequentially, the excess Recovers may yield undefined results. In addition,even if they are not actually destroyed by the instruction, the original stack operands may not be recovered if the instruction changed the contents of the stack and changed the value of the stack pointer. (For example, one can not in general recover the original dividend after a divide, but the operand of a store instruction can always be recovered.) Exceptions to this rule are those instructions that leave results explicitly above the top of the stack. These values can always be obtained by Recovers (for example, MUL, and DIV).

Implementation Note: The intention of these restrictions is to allow the top few elements of the stack to be implemented using fast registers as a cache. The restrictions limit the cases in which the contents of the cache must be written back to the stack.

### 3.3.3 Data and Status Registers

The following additional data and status registers are accessible to the programmer using the register instructions (§3.3.4). In some models of the processor, these actually may be implemented in main memory or other auxiliary storage. Each processor has a unique identification number guaranteed to be different from all others. This register is read-only.

    PID: READONLY ARRAY [0..4) OF UNSPECIFIED;

Design Note: Currently, only 48 bits are implemented, and the first (high-order) word must be zero.

Most models of the processor include a maintenance panel for displaying error and status information to service personnel. This register is optional; if it is present, it is a write-only register.

    MP: CARDINAL;

The interval timer allows high-resolution measurements of program performance and external events. It is incremented by one, modulo 232, at a constant rate. The units of the timer, called pulses, are processor-dependent, but must be in the range 1-100 microseconds.

    IT: LONG CARDINAL;

The wakeup mask register contains a bit mask indicating which interrupt levels are assigned for internal use by the processor (see §10.4.4). It is read only.

    WM: READONLY CARDINAL;

The wakeup pending register records the occurrence of wakeups that will later be translated into interrupts by the processor (see §10.4.4).

    WP: CARDINAL;

The wakeup disable counter is used to control interrupt processing (see §10.4.4).

    WDC: CARDINAL;

The process timeout counter is used to time out waiting processes (see §10.4.5).

    PTC: CARDINAL;

The xfer trap status is used to control trapping of control transfers (see §9.5.5).

    XTS: CARDINAL;

Additional data and status registers may be present in the processor and available to the programmer. Inclusion of the IEEE standard floating-point instructions may add such registers. Details of the format and content of these registers are under development.

### 3.3.4 Register Instructions

The register instructions read and write the contents of the programmer-visible registers defined in the previous sections.

#### RRIT Read Register IT

    RRIT: PROCEDURE =
        BEGIN
        PushLong[IT];
        END;

#### RRMDS Read Register MDS

    RRMDS: PROCEDURE =
        BEGIN
        Push[HighHalf[MDS]];
        END;

#### RRPSB Read Register PSB

    RRPSB: PROCEDURE =
        BEGIN
        Push[Handle[PSB]];
        END;

#### RRPTC Read Register PTC

    RRPTC: PROCEDURE =
        BEGIN
        Push[PTC];
        END;

#### RRWDC Read Register WDC

    RRWDC: PROCEDURE =
        BEGIN
        Push[WDC];
        END;

#### RRWP Read Register WP

    RRWP: PROCEDURE =
        BEGIN
        Push[WP];
        END;

#### RRXTS Read Register XTS

    RRXTS: PROCEDURE =
        BEGIN Push[XTS];
        END;

#### WRIT Write Register IT

    WRIT: PROCEDURE =
        BEGIN
        IT  PopLong[];
        END;

#### WRMDS Write Register MDS

    WRMDS: PROCEDURE =
        BEGIN
        MDS  LongShift[LONG[Pop[], WordSize];
        END;

#### WRM Write Register MP

    WRMP: PROCEDURE =
        BEGIN
        MP  Pop[];
        END;

#### WRPSB Write Register PSB

    WRPSB: PROCEDURE =
        BEGIN
        PSB  Index[Pop[]];
        END;

#### WRPTC Write Register PTC

    WRPTC: PROCEDURE =
        BEGIN
        PTC  Pop[];
        time  IT;
        END;

#### WRWDC Write Register WDC

    WRWDC: PROCEDURE =
        BEGIN
        WDC  Pop[];
        END;

#### WRWP Write Register WP

    WRWP: PROCEDURE =
        BEGIN
        WP  Pop[];
        END;

#### WRXTS Write Register XTS

    WRXTS: PROCEDURE =
        BEGIN
        XTS  Pop[];
        END;

Programming Note: Reading (writing) a write-only (read-only) register yields undefined results.

Programming Note: Writing the `MDS` register does not modify the other registers that define the current context. Matching local and global frames must exist in the new `MDS` at the `MDS` relative locations pointed to by the `LF` and `GF` registers.

The following table lists the sections in which each of these registers is defined (if it is not discussed in detail above). Unless otherwise noted, the register can be both read and written by the programmer.

`PSB` | Current Process State Block handle (§10.1.1).
`MDS` | Current Main Data Space address.
`PID` | Quad word processor id, read only.
`MP` | Maintenance panel, write only.
`IT` | Double word interval timer.
`WM` | Wakeup mask register, read only (§10.4.4).
`WP` | Wakeup pending register (§10.4.4.1).
`WDC` | Wakeup disable counter (§10.4.4.3).
`PTC` | Process timeout counter (§10.4.5).
`XTS` | Xfer trap status (§9.5.5).

Programming Note: The current local frame register (`LF`) and global frame register (`GF`) can be read using the `LA0` and `GA0` instructions (§7.2). They can be written by a control transfer (§9.4). The current code base (`CB`) can be obtained from the global frame.

Previous [TOC] Next

[last edited 3/24/99 12:22AM]