[Indigo]<Cedar>VM>VMInternal.mesa!1

VMInternal.mesa

last edited by Levin on December 15, 1983 10:32 am

DIRECTORY

DebuggerSwap USING [WorryCallDebugger],

PrincOps USING [

AllocationVectorSize, flagsClean, flagsVacant, Frame, FrameSizeIndex, logWordsPerPage, PageState, RealPageNumber],

PrincOpsUtils USING [GetPageState, SetPageFlags, SetPageState],

VM USING [

DataState, Interval, LogPageCount, PageCount, PageState, PageNumber, VMPartition, wordsPerPage];

VMInternal: DEFINITIONS LOCKS vmStateLock

IMPORTS PrincOpsUtils, DebuggerSwap =

BEGIN

This interface is private to the implementation of the virtual memory system. It implements the representation of the PageState (see VM interface for the definition of this type) and provides appropriate mutual exclusion in its manipulation. It also provides the primitives for allocation of real memory, since this is intimately associated with alterations in the PageState.

Those quantities declared PRIVATE are logically part of the implementation and should not be used by the clients of this interface. This declarations appear here only because of INLINE dependencies.

VMMap and RMMap

PageState: TYPE = VM.PageState;

DataState: TYPE = VM.DataState;

Interval: TYPE = VM.Interval;

PageNumber: TYPE = VM.PageNumber;

PageCount: TYPE = VM.PageCount;

RealPageNumber: TYPE = PrincOps.RealPageNumber; -- 16M words of real memory

VMPartition: TYPE = VM.VMPartition;

DataLocation: PRIVATE TYPE = {in, out};

PinCount: PRIVATE TYPE = CARDINAL;

VMMapEntry: PRIVATE TYPE = MACHINE DEPENDENT RECORD [

state(0): PrincOps.PageState,

body(1): SELECT COMPUTED DataLocation FROM

in => [real(1): RealPageNumber],

out => [

fill(1:0..11): [0..7777B] ← 0,

There is a slight subtlety in the interpretation of the following fields. If 'dataState' = none, 'readOnly' isn't meaningful, but if 'checkedOut' is TRUE, the page is not available for allocation. This is used to handle certain special cases in the address space (like page 0) which should never be allocated and which should cause address faults if access is attempted. The only places this special case encoding has to be inspected are the IsFree and AllocateForSwapIn procedures.

checkedOut(1:12..12): BOOL, readOnly(1:13..13): BOOL, dataState(1:14..15): DataState],

ENDCASE];

RMState: PRIVATE TYPE = {free, reclaimable, pinned};

RMEntryPointer: PRIVATE TYPE = LONG POINTER TO RMMapEntry;

RMMapEntry: PRIVATE TYPE = MACHINE DEPENDENT RECORD [

The following two fields are not used in the 'free' variant. However, for coding convenience, they appear here rather than in both the 'reclaimable' and 'pinned' variants.

dataState(0:0..1): DataState, needsBackingStoreWrite(0:2..2): BOOL,

available(0:3..4): [0..3] ← 0,

body(0:5..31): SELECT rmState(0:5..6): RMState FROM

free => [

availableF(0:7..15): [0..777B] ← 0,

next(1:0..15): RealPageNumber

reclaimable => [

The following field is used only during cleaning.

referenced(0:7..7): BOOL ← FALSE,

In principle, 'virtual' should be a VM.PageNumber. However, the implementation is presently limited to a 24-bit virtual address (16 bit PageNumber) by the practicalities of backing storage size. Accordingly, we can save a word in the representation here.

virtualHigh(0:8..15): [0..377B] ← 0, -- will eventually extend 'virtual' to 24 bits.

virtual(1:0..15): WORD

pinned => [

pinReason(0:7..15): PinReason ← normal, -- not essential, could be encoded in large 'pinCount' values

pinCount(1:0..15): PinCount

]

ENDCASE];

PinReason: TYPE = {

normal,

A pinned RMMapEntry so labelled represents a pinned real page to which VM.Unpin can be legally applied.

noSuchRealPage,

A pinned RMMapEntry so labelled represents a real page that doesn't actually exist.

permanentlyPinned,

A pinned RMMapEntry so labelled represents a real page that is set aside for special purposes and is never to be used (e.g., the Germ).

specialRealPageAvailable,

A pinned RMMapEntry so labelled represents a real page that is available for allocation by the SpecialRealMemory procedures in VMSideDoor.

specialRealPageInUse,

A pinned RMMapEntry so labelled represents a real page that has been allocated by the SpecialRealMemory procedures in VMSideDoor.

cantBeWritten

A pinned RMMapEntry so labelled represents a real page for which a backing store write has failed.

};

maxPinCount: PinCount = PinCount.LAST;

lastVMPage: READONLY PageNumber;

This is the highest virtual page number supported by the hardware map. It is set at initialization time and never changed. It is intended to be used for (explicit) validation of PageNumber values passed through the VM interface. Note that this value is NOT the same as VMSideDoor.vmPages-1.

We use the following representation instead of a DESCRIPTOR because we want to permit the RMMap to have 2^16 entries. The length field of a DESCRIPTOR is constrained to be 16 bits and is assumed to be 0-origin. A non-COMPUTED SEQUENCE isn't much better.

RMMapEntries: TYPE = RECORD[SEQUENCE COMPUTED RealPageNumber OF RMMapEntry];

GetVMMap: PROC [vmPage: PageNumber] RETURNS [entry: VMMapEntry] =

We would like to say: LOOPHOLE[PrincOpsUtils.GetPageState];

INLINE {RETURN[LOOPHOLE[PrincOpsUtils.GetPageState[vmPage]]]};

SetVMMap: PROC [vmPage: PageNumber, entry: VMMapEntry] =

INLINE {PrincOpsUtils.SetPageState[vmPage, LOOPHOLE[entry, in VMMapEntry].real, entry.state]};

InOut: PROC [entry: VMMapEntry] RETURNS [DataLocation] =

INLINE {RETURN[IF entry.state.flags = PrincOps.flagsVacant THEN out ELSE in]};

Outcome: TYPE = {ok, addressFault};

Real Memory Allocation

vmStateLock: PRIVATE MONITORLOCK;

freeList: PRIVATE RealPageNumber;

freePages: PRIVATE INT;

rmMap: PRIVATE LONG POINTER TO RMMapEntries;

lastRealPage: PRIVATE RealPageNumber;

AllocateRealMemoryForLocalFrames: ENTRY PROC [vmPage: PageNumber] = INLINE {

This procedure (and everything it calls) must be INLINE because it is invoked on the frame fault path.

victim: Victim = AllocateRealMemoryInternal[vmPage: vmPage, dirtyVictimOK: FALSE, pin: TRUE];

PrincOpsUtils.SetPageFlags[virtual: vmPage, real: victim.realPage, flags: PrincOps.flagsClean];

};

AllocateRealMemoryInternal: PRIVATE READONLY PROC [

vmPage: PageNumber, dirtyVictimOK: BOOL ← TRUE, pin: BOOL ← FALSE]

RETURNS [victim: Victim];

This procedure (actually, coroutine) allocates real memory and tentatively assigns it to the specified vmPage.

Unpin: PROC [vmPage: PageNumber] RETURNS [outcome: Outcome];

AddToFreeList: PRIVATE PROC [realPage: RealPageNumber] = INLINE {

rmMap[realPage].body ← free[next: freeList];

freeList ← realPage;

freePages ← freePages.SUCC;

};

Virtual Memory Allocation

pagesIn64K: PageCount = 65536/VM.wordsPerPage;

logPagesIn64K: VM.LogPageCount = 16 - PrincOps.logWordsPerPage;

allocationLock: MONITORLOCK;

This lock is used to serialize calls on AllocateVirtualMemoryInternal from multiple processes. It must not be the same lock used by the implementation of most of the procedures in the VM interface (if it were, a deadlock would result if a frame fault occurred in the implementation of one of those procedures). This lock is used by VM.Allocate and the VMFaultsImpl.AllocateForLocalFrames, below.

AllocationOutcome: TYPE = {ok, notFound, badParameters};

AllocCount: TYPE = RECORD [ --*stats*--

requests: INT,

requestsSatisfied: INT,

pagesAllocated: INT,

pagesFreed: INT

];

Partitions: TYPE = ARRAY VMPartition OF Interval;

--*stats*-- allocCounts: ARRAY VMPartition OF AllocCount;

partitions: Partitions;

NoteFreePages: PROC [interval: Interval];

UpdateVMLimit: PROC [pages: PageCount];

AllocateVirtualMemoryInternal: READONLY PROC [

count: PageCount, partition: VM.VMPartition ← normalVM, subRange: Interval ← [0, 0],

start: PageNumber ← 0, alignment: VM.LogPageCount ← 0, in64K: BOOL ← FALSE]

RETURNS [outcome: AllocationOutcome, interval: Interval];

This procedure (actually a coroutine) searches the specified 'partition' of virtual memory for an interval such that (1) for each page in interval, State[page].data = none, (2) interval.count = count, (3) if subRange.count >= count, then 'interval' is contained in 'subRange', (4) interval.page MOD 2^alignment is zero, (5) if start is non-zero, then interval.page-start is minimal, (6) if in64K is TRUE, then the interval doesn't span a 64K word boundary. If such an interval is found, it is returned ('outcome' is 'ok') and, for every page in 'interval', State[page] = [data: undefined, readOnly: FALSE, hasRealMemory: FALSE, pinCount: 0]. If no such interval can be found, 'outcome' becomes 'notFound'.

IsFree: --ENTRY-- PROC [vmPage: PageNumber] RETURNS [BOOL] = INLINE {

This procedure returns TRUE iff the argument VM page is available for allocation. Because of the representation of the VMMap, it need not be an entry procedure. It (and everything it calls) must be INLINE because it is invoked from VMInternal.AllocateRealMemoryInternal.

vmEntry: VMMapEntry = GetVMMap[vmPage];

WITH vmE: vmEntry SELECT InOut[vmEntry] FROM

in => RETURN[FALSE];

out => RETURN[vmE.dataState = none AND ~vmE.checkedOut];

ENDCASE => ERROR;

};

MarkAllocated: PROC [vmPage: PageNumber] = INLINE {

This procedure (and everything it calls) must be INLINE because it is invoked from VMInternal.AllocateRealMemoryInternal.

vmEntry: VMMapEntry ← GetVMMap[vmPage];

WITH vmE: vmEntry SELECT InOut[vmEntry] FROM

in => Crash[];

out =>

IF vmE.dataState = none THEN {vmE.dataState ← undefined; SetVMMap[vmPage, vmE]}

ELSE Crash[];

ENDCASE;

};

State Examination and Modification

State: PROC [vmPage: PageNumber] RETURNS [state: PageState];

SetDataState: PROC [vmPage: PageNumber, dataState: DataState] RETURNS [outcome: Outcome];

ReadOnly <==> ReadWrite

MakeReadOnly: PROC [vmPage: PageNumber] RETURNS [outcome: Outcome];

MakeReadWrite: PROC [vmPage: PageNumber] RETURNS [outcome: Outcome];

Utilities for VM.SwapIn and VM.Clean

swapBufferSize: PageCount = 50;

SwapInOutcome: TYPE = {

noReadNecessary, -- victim has been claimed; read unnecessary (dataState = undefined)

alreadyIn, -- page already swapped in; no victim has been claimed

needsRead, -- victim claimed; read required

addressFault, -- page not allocated

writeFault -- page is read only

};

VictimState: TYPE = {clean, dirty};

Victim: TYPE = RECORD [

realPage: RealPageNumber,

body: SELECT victimState: VictimState FROM

clean => NULL,

dirty => [vmPage: PageNumber],

ENDCASE];

AllocateForSwapIn: PROC [vmPage: PageNumber, kill, pin: BOOL]

RETURNS [outcome: SwapInOutcome, victim: Victim];

SwapInDone: PROC [vmPage, bufferPage: PageNumber, worked: BOOL];

SwapInDoneWithoutIO: PROC [vmPage: PageNumber, victim: Victim];

VictimWriteDone: PROC [

vmPage, bufferPage: PageNumber, victim: dirty Victim, worked: BOOL];

CleanOutcome: TYPE = {

cantWrite, -- none of the following cases apply

checkedOutClean, -- page is clean and swappable and checkOutClean = TRUE

needsWrite, -- page is dirty and swappable

addressFault -- page not allocated

};

ConsiderCleaning: PROC [vmPage: PageNumber, checkOutClean: BOOL]

RETURNS [outcome: CleanOutcome, real: RealPageNumber];

CleanDone: PROC [vmPage, bufferPage: PageNumber, worked: BOOL];

Aging

Age: PROC [vmPage: PageNumber] RETURNS [outcome: Outcome];

Laundry process support

GetCleaningCandidate: PROC [

desired: PageCount, comfortLevel: PageCount, tryHard: BOOL ← FALSE]

RETURNS [Interval];

NoteDirtyVictim: PROC;

I/O Interface

IODirection: TYPE = {read, write};

IOResult: TYPE = {ok, labelCheck, someOtherError};

DoIO: PROC [

direction: IODirection, backingPage: PageNumber, interval: Interval, subsequentSeek: PageNumber ← 0]

RETURNS [result: IOResult, done: PageCount];

HasBackingStorage: SAFE PROC [page: PageNumber] RETURNS [BOOL];

Frame Fault Handler Structures

AnyFrameSizeIndex: TYPE = CARDINAL [0..PrincOps.AllocationVectorSize); -- note that an AnyFrameSizeIndex immediately precedes a Frame.

NormalFrameSizeIndex: TYPE = PrincOps.FrameSizeIndex;

FsiFrame: TYPE = MACHINE DEPENDENT RECORD [

fsi(0): AnyFrameSizeIndex, -- must be at 3 MOD 4 boundary.

frame(1): local PrincOps.Frame];

FrameHeapPiece: TYPE = POINTER TO FrameHeapPieceHeader;

FrameHeapPieceHeader: TYPE = MACHINE DEPENDENT RECORD [

next(0): FrameHeapPiece, -- must be at 0 MOD 4 boundary.

wordsAllocated(1): CARDINAL, -- actually [0..VM.PagesToWords[PrincOps.shortPointerSpan]]

wordsInUse(2): CARDINAL, -- assert: wordsInUse MOD 4 = 3

fsiFrame(3): ARRAY [0..0) OF --WORD-- FsiFrame]; -- must be at 3 MOD 4 boundary.

largeFrameThresholdFsi: NormalFrameSizeIndex = 14; -- frames this size or larger will be allocated in an integral number of pages, and reclaimed when they are freed.

LargeFrame: TYPE = POINTER TO LargeFrameHeader;

LargeFrameHeader: TYPE = MACHINE DEPENDENT RECORD [

next(0): LargeFrame,

prev(1): LargeFrame,

trueFsi(2): NormalFrameSizeIndex,

fsiFrame(3): ARRAY [0..0) OF --WORD-- FsiFrame]; -- must be at 3 MOD 4 boundary.

The following data structures can be safely inspected only when interrupts are disabled and no procedures are called.

frameHeapPieceList: FrameHeapPiece; -- list of frame heap pieces, excluding large frames

largeFrameList: LargeFrame; -- list of large frames (some allocated, some freed)

Miscellaneous

InitializeTables: PROC;

Crash: PROC = INLINE {DebuggerSwap.WorryCallDebugger[NIL]};

END.