Page Numbers: Yes First Page: 51 X: 527 Y: 10.5"
Margins: Binding: 13
Odd Heading: Not-on-first-page

Alto/Mesa Segment Package

Even Heading:

Alto/Mesa Segment Package

Alto/Mesa Segment Package
October 1980

The Mesa virtual memory (VM) is organized as a vector of pages of size PageSize words; the last page is MaxVMPage. VM is occupied by segments: a segment is an integral number of pages in length and the words in a segment are all linearly addressable; segments have no empty holes in them. There are two variants of segments: data and file. Data segments are associated directly with memory and are not swappable or movable; file segments correspond to contiguous groups of pages in a file and may be swapped in and out of virtual memory.

Client programs access segments using SegmentHandles, which are pointers to SegmentObjects. A SegmentObject contains the information necessary to describe the segment. Although there are some routines that deal with SegmentHandles, segments themselves are not especially interesting unless they are discriminated as to their data or file variant.

Client programs access file segments using FileSegmentHandles, which are pointers to file SegmentObjects. A file segment contains sufficient information to compute the address of the segment in virtual memory if that segment is swapped in. Internally, the segmentation package maintains a set of objects called FileObjects: a file object, among other things, contains the file’s disk address and serial number, as well as its access rights. The association between a segment and a file is made when the segment is created. The Alto/Mesa file package is documented in a separate section.

Segments may also be pages in VM rather than attached to a file. Such data segments are not swappable or movable in any way (relative to the Mesa virtual memory). Thus, absolute pointers into a data segment are valid for the lifetime of the segment. DataSegmentHandles and data SegmentObjects are used to record information about these segments. See SegmentDefs for further details.

Segments

As mentioned above, segment objects come in two varieties: data segments and file segments. The following structure contains the necessary information:

SegmentHandle: TYPE = POINTER TO SegmentObject;

SegmentType: TYPE = {data, file};

SegmentObject: -- actually one variant of Object; the type SegmentObject = segment Object.
. . .
VMpage: [0..MaxVMPage],-- VM page number
info: SELECT type: SegmentType FROM
data => [
type: DataSegmentType ← UnknownDS,-- type of data segment
pages: [1..PagesPerMDS],-- number of pages
. . .],
file => [
swappedin: BOOLEAN, -- TRUE iff segment is in
write: BOOLEAN,-- access options
class: FileSegmentClass,-- {code, other}
inuse: BOOLEAN,-- software LRU bit
lock: SegLockCount,-- locking reference count
pages: [1..PagesPerMDS],-- number of pages, beginning with base
file: FileHandle,-- see the file package
base: PageNumber,-- first page of the file to include
. . .],
ENDCASE];

The procedures which manipulate undiscriminated segments are:

VMtoSegment: PROCEDURE [a: POINTER] RETURNS [SegmentHandle];

The handle for the segment containing the specified address (as currently laid out in memory) is returned. NIL is returned if no segment contains the segment; this does not imply that the page containing the address is free, however, since it may be reserved for some operation currently in progress.

SegmentAddress: PROCEDURE [seg: SegmentHandle] RETURNS [POINTER];

The address of the beginning of the segment is returned; NIL is returned if the segment is a file segment and not currently swapped in. To guarantee the validity of the address the segment should be locked when this procedure is called (see below), since the system may swap out file segments that are not locked. Beware of dangling references!

Data Segments

Data segments are associated only with virtual memory (there is no swapping file) and are never moved or swapped out.

DataSegmentHandle: TYPE = POINTER TO DataSegmentObject;

DataSegmentObject: TYPE = data SegmentObject;

The procedures which manipulate data segments are:

NewDataSegment: PROCEDURE [base: PageNumber, pages: PageCount]
RETURNS [DataSegmentHandle];

Creates a new data segment and returns a handle for it. If base is DefaultBase then the segment is allowed to begin on any free page in memory. If base is an actual page number (in [0..MaxVMPage]), an attempt is made to place the segment at that location. Note that pages should not be defaulted.

DataSegmentAddress: PROCEDURE [seg: DataSegmentHandle] RETURNS [POINTER];

Returns a pointer to the base of the segment in virtual memory. In the current implementation, segments always begin on a page boundary.

VMtoDataSegment: PROCEDURE [a: POINTER] RETURNS [DataSegmentHandle];

The handle for the segment containing the specified address (as currently laid out in memory) is returned. NIL is returned if no data segment contains it; this does not imply that the page containing the address is free, however, since it may be assigned to a file segment, or reserved for some operation currently in progress.

DeleteDataSegment: PROCEDURE [seg: DataSegmentHandle];

The specified data segment is deleted and its segment object freed. When a segment is successfully deleted, any VM that it occupied becomes free.

EnumerateDataSegments: PROCEDURE [
proc: PROCEDURE [DataSegmentHandle] RETURNS [BOOLEAN]]
RETURNS [DataSegmentHandle];

Calls proc once for each data segment currently defined. If proc returns TRUE, EnumerateDataSegments returns the handle of the last segment processed. If the end of the set of data segments is reached, NIL is returned.

As a debugging aid, data segments now have types.

DataSegmentType: TYPE = CARDINAL[0..377B];

The Debugger’s COremap command will now display the type of the data segment. Defined types are:

UnknownDS: DataSegmentType = 0;

FrameDS: DataSegmentType = 1;

TableDS: DataSegmentType = 2;

HeapDS: DataSegmentType = 3;

SystemDS: DataSegmentType = 4;

BitmapDS: DataSegmentType = 5;

StreamBufferDS: DataSegmentType = 6;

Clients can supply their own type which will be printed numerically. Clients should use type values greater than 20B to allow room for more common types to be printed symbolically by the Debugger.

File Segments

Unlike data segments, file segments are associated with a contiguous group of pages in a file and are therefore swappable. Pointers into a file segment are valid only while it is swapped in (and locked so that it will not be swapped out). A file segment that is swapped out occupies no space in virtual memory other than the segment object which describes it. If the LRU bit (inuse) is set, the swapper will ignore this segment on its first search for free pages. The swapper resets this bit, so the segment will be considered for swapping if a second pass is necessary.

FileSegmentHandle: TYPE = POINTER TO FileSegmentObject;

FileSegmentObject: TYPE = file SegmentObject;

To create new file segments, use

NewFileSegment: PROCEDURE [
file: FileHandle, base: PageNumber, pages: PageCount, access: AccessOptions]
RETURNS [FileSegmentHandle];

Creates a new segment and returns a handle for it. The segment is associated with the corresponding file pages, but the file is not opened and the segment is not swapped in. If base is DefaultBase, the segment will begin with the first data page of the file, and if pages is DefaultPages, it will include the last page of the file. Although it is generally not done, a segment can begin with the leader page (page zero) of a file. Finally, if access is DefaultAccess, read access is assumed.

If the access specifies that changing the data is permitted, then whenever it is necessary to swap this segment out and remove its pages from memory, pages will be written to the file (the Alto has no hardware to detect if the pages have actually been changed). It is possible to change the segment’s access (by setting the write bit, for example), provided the file to which it is attached has the appropriate access rights.

FileSegmentAddress: PROCEDURE [seg: FileSegmentHandle] RETURNS [POINTER];

The address of the beginning of the segment is returned. The signal SwapError is raised if the segment is not currently swapped in. To guarantee the validity of the address, the segment should be locked when this procedure is called (see below), since the system may swap out file segments which are not locked. Beware of dangling references!

VMtoFileSegment: PROCEDURE [a: POINTER] RETURNS [FileSegmentHandle];

The handle of the file segment containing the specified address (as currently laid out in memory) is returned. NIL is returned if no file segment contains it. This does not imply that the page containing the address is free, however; it may be assigned to a data segment, or reserved for a segment currently being swapped in.

DeleteFileSegment: PROCEDURE [seg: FileSegmentHandle];

The specified file segment is deleted and its segment object is released. If the segment is swapped in, it is first swapped out (it should not be locked). If there are no other segments associated with this segment’s file (the file’s segcount is zero), then ReleaseFile is called to release the FileObject. When a segment is successfully deleted, any VM which it may have occupied becomes free.

EnumerateFileSegments: PROCEDURE [
proc: PROCEDURE [FileSegmentHandle] RETURNS [BOOLEAN]]
RETURNS [FileSegmentHandle];

Calls proc once for each data segment currently defined. If proc returns TRUE, EnumerateFileSegments returns the handle of the last segment processed. If the end of the set of data segments is reached, NIL is returned.

If file segments are created while EnumerateFileSegments is in control, it is not guaranteed that they will be included in the sequence of FileSegmentHandles passed to proc.

Window Segments

A window segment is similar to a file segment, except that the base and pages fields of the segment may be altered (using the procedures described below) after it is created, in order to slide the window around in a file or to vary the window’s size. In reality, all file segments are in fact window segments, and may be moved with the following procedure:

MoveFileSegment: PROCEDURE [
seg: FileSegmentHandle, base: PageNumber, pages: PageCount];

If the segment is swapped in, it is first swapped out (it should not be locked). The segment is then moved to the new location in the segment’s file, but it is not swapped in. The base and pages are defaulted as in NewFileSegment.

Fine point: in the current implementation, the disk address of the original segment is retained as a hint about the new location, thus improving performance considerably when a one page segment is slid forward or backward in a file.

If the original and final position of the segment overlap, there is no guarantee that the overlapping pages are actually written, nor is it guaranteed that a minimum number of pages are transferred.

Swapping Segments

A segment can be swapped into and out of VM. The procedures and signals which implement this are described in this section:

SwapIn: PROCEDURE [seg: FileSegmentHandle];

Swaps in the specified segment (if it is swapped out), opening the associated file if necessary; locks it so it won’t be moved or swapped out. A SwapError will result if the segment already has MaxSegLocks locks on it, or if the segment’s file has MaxRefs segments currently attached to it and swapped in.

To unlock a segment (allow it to be swapped), use the procedure

Unlock: PROCEDURE [seg: FileSegmentHandle];

Unlocks the specifed segment so that it can be swapped out. Note that locking behaves like reference counting, so that locks (performed by SwapIn) must be properly paired with Unlocks.

A segment is swapped out using

SwapOut: PROCEDURE [seg: FileSegmentHandle];

Swaps out the specified segment, writing the pages back to the file if the segment’s access makes this necessary, and free the segment’s VM pages. If the segment is locked, a SwapError will be generated.

A program may explicitly request that the file pages corresponding to a segment be updated by calling:

SwapUp: PROCEDURE [seg: FileSegmentHandle];

Write the pages of the segment back to the file if the access requires it. This operation does not unlock the segment or free the segment’s VM pages.

Note that neither SwapIn, SwapOut, or SwapUp are capable of extending a file (physically adding pages or bytes to it) based on the size of a segment. Segments may be attached only to pages of a file that are already allocated on the disk (and chained together). Extending (or contracting) a file must be done using other mechanisms (for example, see SetEndOfFile in the file package).

Signals

The following signals may be generated by the segment package:

InvalidSegmentSize: SIGNAL [pages: PageCount];

In NewDataSegment or NewFileSegment a zero length segment has been requested, or the length exceeds the size of virtual memory.

InsufficientVM: SIGNAL [needed: PageCount];

In NewDataSegment or SwapIn there is not enough contiguous memory to accomodate a segment; needed is the number of pages that are actually required. If resumed, the allocation will be retryed; this gives the catcher of this signal a chance to free up some VM. Users can free VM pages by deleting data segments and by allowing locked segments to become swappable (see also the section below on swapping strategies).

VMnotFree: SIGNAL [base: PageNumber, pages: PageCount];

In NewDataSegment the base was not DefaultBase and the specified memory pages were not free.

SwapError: SIGNAL [seg: FileSegmentHandle];

An invalid swapping operation was attempted with seg.

SegmentFault: SIGNAL [seg: FileSegmentHandle, pages: PageCount];

End of file was encountered while attempting to swap the segment in or out; pages is the actual number of pages in the segment. If pages is greater than zero then the signal may be resumed; the segment will be truncated accordingly (of course, this will not alter the file length).

Low Level Memory Allocation

Operations are provided for users that have a need to control memory allocation at a lower level than provided above. Allocation is controlled by the information in an AllocInfo (which is passed along with each operation).

AllocInfo: TYPE = RECORD [
effort: {hard, easy},
direction: {topdown, bottomup},
. . . ];

If the effort field is hard, unlocked read-only file segments will be pushed out of the way. The direction field specifies the direction of the search for a hole. In the above procedures, data segments are allocated topdown, and file segments are allocated bottomup. The following constants have been defined:

EasyUp: AllocInfo = [effort: easy, direction: bottomup];

EasyDown: AllocInfo = [effort: easy, direction: topdown];

HardUp: AllocInfo = [effort: hard, direction: bottomup];

HardDown: AllocInfo = [effort: hard, direction: topdown];

The operations which perform low-level memory allocation are:

MakeDataSegment: PROCEDURE [
base: PageNumber, pages: PageCount, info: AllocInfo ← EasyDown]
RETURNS [DataSegmentHandle];

Acts like NewDataSegment, except info is passed as an additional parameter; the same restrictions apply and the same signals may be generated.

MakeSwappedIn: PROCEDURE [
seg: FileSegmentHandle, base: PageNumber, info: AllocInfo ← EasyUp];

Acts like SwapIn, except info and base are passed as additional parameters; the same restrictions apply and the same signals may be generated. If base is DefaultBase then the segment is allowed to begin on any free page in memory. If base is an actual page number (in [0..MaxVMPage]), an attempt is made to place the segment at that location (VMnotFree will be raised if the specified pages are not available).

Swapping Strategies

A mechanism is provided for informing the segmentation package of emergency measures which can be taken when the signal InsufficientVM is (about to be) generated. These measures take the form of SwappingProcedures which, when called by the swapping manager, attempt to make more room in virtual memory and return a BOOLEAN indicating their success or failure to do so. The swapping manager invokes each procedure in turn, retrying the allocation after each procedure which has indicated success, until sufficient memory is obtained. If all such procedures indicate failure, the signal InsufficientVM is raised (the swapping manager is not crying wolf!).

The swapping strategies are maintained as a linked list of SwapStrategy nodes whose procedures are invoked from head to tail.

SwappingProcedure: TYPE = PROCEDURE [
needed: PageCount, info: AllocInfo, seg: SegmentHandle]
RETURNS [BOOLEAN];

The parameters supplied to swapping procedures allow them to make intelligent decisions about making room: needed is the number of pages requested, info the AllocInfo supplied to the allocator, and seg the file segment that will use the allocated memory (NIL if unknown).

SwapStrategy: TYPE = RECORD [
link: POINTER TO SwapStrategy,
proc: SwappingProcedure];

The swapping manager initializes the list with a single node which invokes code swapping as a last resort.

StrategyList: POINTER TO SwapStrategy ← @LastResort;

LastResort: SwapStrategy = SwapStrategy[NIL, TryCodeSwapping].

Swapping procedures are added to and removed from the list by the procedures:

AddSwapStrategy: PROCEDURE [strategy: POINTER TO SwapStrategy];

The specified strategy node strategy is added to the head of the list of swapping procedures. If strategy is already on the list, its position and content are not disturbed.

RemoveSwapStrategy: PROCEDURE [strategy: POINTER TO SwapStrategy];

The specified strategy node is removed from the list of swapping procedures.

Currently, TryCodeSwapping uses an (approximately) LRU (least-recently-used) algorithm to choose a code segment to swap out. Only code segments which are not locked are considered. Unlocked read-only file segments are also swapped out by TryCodeSwapping.

Since it is unattractive to require that the code for swapping strategies (other than TryCodeSwapping) be locked, swapping procedures should observe the following conventions: If such a procedure obtains a state in which it has nothing to swap, it should either remove the node containing itself from the strategy list or change the procedure in the node to be

CantSwap: SwappingProcedure;

Because CantSwap is part of the swapping manager (and therefore locked), this will avoid swapping in a strategy procedure which knows it has nothing to do.

Miscellaneous Procedures

The following procedures implement conversion between memory addresses and virtual memory page numbers.

PageFromAddress: PROCEDURE [a: POINTER] RETURNS [PageNumber];

AddressFromPage: PROCEDURE [p: PageNumber] RETURNS [POINTER];

PagePointer: PROCEDURE [a: POINTER] RETURNS [POINTER];

PagePointer returns the address of the beginning of the page which contains its argument.

The following procedures implement conversion between FileSegments and DataSegments. Note that both segments must exist at the time of the call, and neither is destroyed. They must be of the same length (a SwapError will result otherwise).

CopyDataToFileSegment: PROCEDURE [
dataseg: DataSegmentHandle, fileseg: FileSegmentHandle];

Initializes a file segment to have the contents of a data segment.

CopyFileToDataSegment: PROCEDURE [
fileseg: FileSegmentHandle, dataseg: DataSegmentHandle];

Initializes a data segment to have the contents of the file segment.

Extended Memory Operations

Configuration Information

The Mesa runtime system has an internal data structure that contains information about the hardware configuration of the machine on which it is running. Clients may obtain a copy of this data structure by calling GetMemoryConfig and should normally test for the existence of extended memory by examining the useXM field. The extant banks of memory are indicated by MemoryConfig.banks, which is a bit mask (e.g., MemoryConfig.banks=140000B implies that banks zero and one exist).

BankIndex: TYPE = [0..17B];

ControlStoreType: TYPE = {Ram0, RamandRom, Ram3k, unknown};

MachineType: TYPE = {unknown0, AltoI, AltoII, AltoIIXM, . . . };

MemoryConfig: TYPE = MACHINE DEPENDENT RECORD [
reserved: [0..37B],
AltoType: MachineType,
xmMicroCode: BOOLEAN,
useXM: BOOLEAN,
mdsBank: BankIndex,
controlStore: ControlStoreType,
banks: [0..177777B],
mesaMicrocodeVersion: [0..177777B]];

memConfig: PUBILC READONLY MemoryConfig;

GetMemoryConfig: PROCEDURE RETURNS [MemoryConfig] = INLINE
BEGIN RETURN[memConfig] END;

The field memConfig.useXM is true if and only if the following conditions hold:

1)the machine is an Alto II with XM modifications (AltoType = AltoIIXM),

2)the Alto has more than one memory bank installed (banks ~= 100000B),

3)the Alto has a 3K RAM, or it has a second ROM containing an appropriate version of the XMesa microcode.

The microcode version field tells only the microcode version, not the Mesa release number. (See the Mesa User’s Handbook, Appendix G, for a discussion of microcode versions)

Extended Memory Management

The facilities described in this section can be used regardless of the state of useXM.

Segments in extended memory are created with the usual primitives in SegmentDefs. However, additional "default" parameter values for those procedures that expect a VM base page number have been provided. DefaultMDSBase requests allocation anywhere in the MDS. DefaultXMBase requests allocation anywhere in the extended memory banks but not in the MDS. DefaultBase0, DefaultBase1, DefaultBase2 and DefaultBase3 request allocation in particular banks. DefaultANYBase requests allocation anywhere in the extended memory banks or the MDS. DefaultBase is equivalent to DefaultANYBase if the segment is a code segment, otherwise, it is equivalent to DefaultMDSBase.

The following procedures convert between segment handles and long pointers, and work for segments anywhere in the 20-bit address space.

LongVMtoSegment: PROCEDURE [a: LONG POINTER] RETURNS [SegmentHandle];

LongSegmentAddress: PROCEDURE [seg: SegmentHandle] RETURNS [LONG POINTER];

LongVMtoDataSegment: PROCEDURE [a: LONG POINTER] RETURNS [DataSegmentHandle];

LongDataSegmentAddress: PROCEDURE [seg: DataSegmentHandle]
RETURNS [LONG POINTER];

LongVMtoFileSegment: PROCEDURE [a: LONG POINTER] RETURNS [FileSegmentHandle];

LongFileSegmentAddress: PROCEDURE [seg: FileSegmentHandle]
RETURNS [LONG POINTER];

The following definitions are in AltoDefs; they define parameters of the extended memory system.

MaxVMPage: CARDINAL = 7777B;

MaxMDSPage: CARDINAL = 377B;

PagesPerMDS: CARDINAL = MaxMDSPage+1;

The following procedures convert between page numbers and long pointers, and are analogous to AddressFromPage and PageFromAddress.

LongAddressFromPage: PROCEDURE [page: AltoDefs.PageNumber]
RETURNS [lp: LONG POINTER];

PageFromLongAddress: PROCEDURE [lp: LONG POINTER]
RETURNS [page: AltoDefs.PageNumber];

The following procedures check the validity of long pointers and page numbers and raise the indicated errors.

ValidateVMPage: PROCEDURE [page: UNSPECIFIED];

InvalidVMPage: ERROR [page: UNSPECIFIED];

ValidateLongPointer: PROCEDURE [a: LONG UNSPECIFIED];

InvalidLongPointer: ERROR [lp: LONG UNSPECIFIED];

Restrictions, Limitations, and "Features"

Bank Registers. Mesa assumes it has exclusive control of the emulator bank register on AltoIIXMs. Client programs must not attempt to alter the bank register, but rather must use the public interfaces for moving data to and from extended memory (see LongCOPY and BitBlt, above).

Segment Alignment. Segments may not cross bank boundaries. The first page of each non-MDS bank is reserved for internal allocation tables.

Swapper Algorithms. The swapper loads a segment into extended memory by first swapping it into primary memory, then copying it to extended memory and releasing the MDS memory space. Thus, if the MDS is so full that the requested segment cannot be swapped in, InsufficientVM will be raised, even though sufficient space for the segment may exist in other banks. (Analogous comments apply when swapping out segments that must be written to disk.)