Memory Organization
|
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.
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.
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.
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 POINTERs, 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.
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.
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;
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;
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.
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).
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.
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.
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.
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.
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.
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 MDSs 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).
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: 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;
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.
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
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
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.
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.
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;
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: PROCEDURE =
BEGIN alpha BYTE = GetCodeByte[];
ptr: POINTER = Pop[];
IF alpha ~IN[1..4] THEN ERROR;
Push[FetchMds[ptr - alpha]];
END;
WOB: PROCEDURE =
BEGIN
alpha BYTE = GetCodeByte[];
ptr: POINTER = Pop[];
IF alpha ~IN[1..4] THEN ERROR;
StoreMds[ptr - alpha] Pop[];
END;
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.
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:
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 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.
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.
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.
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:
Some operations leave results or partial results above the top of the stack, that is, at stack[SP] and 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.
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.
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.
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.
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.
The wakeup pending register records the occurrence of wakeups that will later be translated into interrupts by the processor (see §10.4.4).
The wakeup disable counter is used to control interrupt processing (see §10.4.4).
The process timeout counter is used to time out waiting processes (see §10.4.5).
The xfer trap status is used to control trapping of control transfers (see §9.5.5).
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.
The register instructions read and write the contents of the programmer-visible registers defined in the previous sections.
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.
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.
[last edited 3/24/99 12:22AM]
3.3.2 Evaluation Stack
StackDepth: CARDINAL = cSS;
StackPointer: TYPE = [0..StackDepth);
stack: ARRAY [0..StackDepth) OF UNSPECIFIED;
StackCounter: PROCEDURE RETURNS [StackPointer] =
BEGIN
RETURN[SP];
END;
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;
MinimalStack: PROCEDURE =
BEGIN
IF SP # O THEN StackError[];
END;
Recover: PROCEDURE =
BEGIN
IF SP = StackDepth THEN StackError[];
SP
SP + 1;
END;
Discard: PROCEDURE =
BEGIN
IF SP = 0 THEN StackError[];
SP SP - 1;
END;
3.3.3 Data and Status Registers
PID: READONLY ARRAY [0..4) OF UNSPECIFIED;
MP: CARDINAL;
IT: LONG CARDINAL;
WM: READONLY CARDINAL;
WP: CARDINAL;
WDC: CARDINAL;
PTC: CARDINAL;
XTS: CARDINAL;
3.3.4 Register Instructions
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;
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).
Previous
[TOC]
Next