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 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, 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 [ 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 => [ referenced(0:7..7): BOOL _ FALSE, 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, noSuchRealPage, permanentlyPinned, specialRealPageAvailable, specialRealPageInUse, cantBeWritten }; maxPinCount: PinCount = PinCount.LAST; lastVMPage: READONLY PageNumber; RMMapEntries: TYPE = RECORD[SEQUENCE COMPUTED RealPageNumber OF RMMapEntry]; GetVMMap: PROC [vmPage: PageNumber] RETURNS [entry: VMMapEntry] = 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}; vmStateLock: PRIVATE MONITORLOCK; freeList: PRIVATE RealPageNumber; freePages: PRIVATE INT; rmMap: PRIVATE LONG POINTER TO RMMapEntries; lastRealPage: PRIVATE RealPageNumber; AllocateRealMemoryForLocalFrames: ENTRY PROC [vmPage: PageNumber] = INLINE { 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]; Unpin: PROC [vmPage: PageNumber] RETURNS [outcome: Outcome]; AddToFreeList: PRIVATE PROC [realPage: RealPageNumber] = INLINE { rmMap[realPage].body _ free[next: freeList]; freeList _ realPage; freePages _ freePages.SUCC; }; pagesIn64K: PageCount = 65536/VM.wordsPerPage; logPagesIn64K: VM.LogPageCount = 16 - PrincOps.logWordsPerPage; allocationLock: MONITORLOCK; 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]; IsFree: --ENTRY-- PROC [vmPage: PageNumber] RETURNS [BOOL] = INLINE { 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 { 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: PROC [vmPage: PageNumber] RETURNS [state: PageState]; SetDataState: PROC [vmPage: PageNumber, dataState: DataState] RETURNS [outcome: Outcome]; MakeReadOnly: PROC [vmPage: PageNumber] RETURNS [outcome: Outcome]; MakeReadWrite: PROC [vmPage: PageNumber] RETURNS [outcome: Outcome]; 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]; Age: PROC [vmPage: PageNumber] RETURNS [outcome: Outcome]; GetCleaningCandidate: PROC [ desired: PageCount, comfortLevel: PageCount, tryHard: BOOL _ FALSE] RETURNS [Interval]; NoteDirtyVictim: PROC; 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]; 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. frameHeapPieceList: FrameHeapPiece; -- list of frame heap pieces, excluding large frames largeFrameList: LargeFrame; -- list of large frames (some allocated, some freed) InitializeTables: PROC; Crash: PROC = INLINE {DebuggerSwap.WorryCallDebugger[NIL]}; END. –VMInternal.mesa last edited by Levin on December 15, 1983 10:32 am 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 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. 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. The following field is used only during cleaning. 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. A pinned RMMapEntry so labelled represents a pinned real page to which VM.Unpin can be legally applied. A pinned RMMapEntry so labelled represents a real page that doesn't actually exist. 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). A pinned RMMapEntry so labelled represents a real page that is available for allocation by the SpecialRealMemory procedures in VMSideDoor. A pinned RMMapEntry so labelled represents a real page that has been allocated by the SpecialRealMemory procedures in VMSideDoor. A pinned RMMapEntry so labelled represents a real page for which a backing store write has failed. 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. We would like to say: LOOPHOLE[PrincOpsUtils.GetPageState]; Real Memory Allocation This procedure (and everything it calls) must be INLINE because it is invoked on the frame fault path. This procedure (actually, coroutine) allocates real memory and tentatively assigns it to the specified vmPage. Virtual Memory Allocation 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. 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'. 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. This procedure (and everything it calls) must be INLINE because it is invoked from VMInternal.AllocateRealMemoryInternal. State Examination and Modification ReadOnly <==> ReadWrite Utilities for VM.SwapIn and VM.Clean Aging Laundry process support I/O Interface Frame Fault Handler Structures The following data structures can be safely inspected only when interrupts are disabled and no procedures are called. Miscellaneous Ê – "Cedar" style˜Jšœ™Jšœ2™2J˜šÏk ˜ Jšœ œ˜'šœ œ˜Jšœr˜r—Jšœœ,˜?šœœ˜ Jšœ`˜`——J˜šœ œœ ˜)Jšœ˜%—J˜Jš˜J™J™ùJ™J™ÇJ™Jšœ™˜Jšœ œœ ˜Jšœ œœ ˜J˜Jšœ œœ ˜Jšœ œœ ˜!Jšœ œœ ˜JšœœÏc˜LJšœ œœ ˜#J˜Jšœœœ ˜'Jšœ œœœ˜"J˜š œ œœœ œœ˜5Jšœ˜šœ œœ˜*Jšœ ˜ šœ˜Jšœ˜Jšœå™åJšœœœ"˜V—Jšœ˜ ——J˜Jšœ œœ˜4Jš œœœœœœ ˜:J˜šœ œœœ˜5Jšœ¬™¬Jšœ>œ˜CJ˜šœœ˜3˜ Jšœ#˜#J˜J˜—šœ˜Jšœ1™1Jšœœœ˜!Jšœ€™€Jšœ&ž/˜UJšœ˜Jšœ˜—šœ ˜ Jšœ)ž=˜fJšœ˜Jšœ˜—Jšœ˜ —J˜—šœ œ˜šœ˜Jšœg™g—šœ˜JšœS™S—šœ˜Jšœ‡™‡—šœ˜JšœŠ™Š—šœ˜Jšœ™—šœ ˜ Jšœb™b—Jšœ˜—J˜Jšœ!œ˜&J˜šœ œ ˜ JšœÙœ%œ"™¥—J˜Jšœÿ™ÿJš œœœœœœ ˜LJ˜šÏnœœœ˜AJšœ<™—J˜šŸœœ*˜8Jšœ%œ+˜^—J˜šŸœœœ˜8Jš œœœ*œœ˜N—J˜—J˜Jšœ œ˜#J™J™™Jšœ œ œ˜!J˜Jšœ œ˜!Jšœ œœ˜J˜Jš œœœœœ˜,Jšœœ˜%J˜šŸ œœœœ˜LJ™fJšœKœœ˜]Jšœ_˜_Jšœ˜—J˜šŸœœœœ˜3Jš œ#œœœœ˜BJšœ˜J™n—J˜JšŸœœœ˜œ˜D—J˜J˜šœœ˜Jšœ ž$˜0Jšœž7˜IJšœ ž˜+Jšœž˜#Jšœ˜—J˜šŸœœ%œ˜@Jšœ/˜6—J˜JšŸ œœ*œ˜?J™—J™˜JšŸœœœ˜:J˜—J™˜šŸœœ˜Jšœ6œœ˜CJšœ ˜—J˜JšŸœœ˜—J™J™ ˜Jšœ œ˜"Jšœ œ$˜2J˜šŸœœ˜ Jšœd˜dJšœ%˜,—J˜JšŸœ œœœ˜?J˜—J™™Jšœœœ&ž?˜‡Jšœœ˜5J˜š œ œœ œœ˜+Jšœž˜;J˜ —J˜Jšœœœœ˜7š œœœ œœ˜7Jšœž˜9Jšœœž;˜YJšœœž ˜:Jšœ œœžœ ž˜Q—J˜Jšœ4žr˜¦J˜Jšœ œœœ˜/š œœœ œœ˜3Jšœ˜Jšœ˜Jšœ!˜!Jšœ œœžœ ž˜Q—J˜Jšœu™uJ˜Jšœ%ž4˜YJšœž4˜QJ™—J™ ˜JšŸœœ˜J˜JšŸœœœ!œ˜;J˜—Jšœ˜J˜J˜—…— >¥