<> <> <> <> <> <> DIRECTORY PrincOps USING [flagsNone, flagsReadOnly], PrincOpsUtils USING [LongCopy], Process USING [GetPriority, Priority, priorityFaultHandlers, SetPriority], ProcessorFace USING [SetMP], VM USING [AddressForPageNumber, Allocate, CantAllocate, DataState, Interval, IOErrorType, nullInterval, PageCount, PageNumber, PageState, wordsPerPage], VMInternal USING [AllocateForSwapIn, Age, CleanDone, CleanOutcome, ConsiderCleaning, Crash, DoIO, FinishAllocateSpecialRealMemory, FinishReleaseSpecialRealMemory, HasBackingStorage, IOResult, lastVMPage, MakeReadOnly, MakeReadWrite, NoteFreePages, NoteDirtyVictim, Outcome, PrepareToAllocateSpecialRealMemory, PrepareToReleaseSpecialRealMemory, RealPageNumber, SetDataState, SetPageFlags, State, SpecialMemoryOutcome, swapBufferSize, SwapInDone, SwapInDoneWithoutIO, SwapInOutcome, Unpin, Victim, VictimWriteDone], VMSideDoor USING [], VMStatistics USING []; VMOpsImpl: MONITOR IMPORTS PrincOpsUtils, Process, ProcessorFace, VM, VMInternal EXPORTS VM, VMSideDoor, VMStatistics = BEGIN OPEN VM; <> <<>> debugging: BOOL = TRUE; ShowWhatsUp: PROC [code: CARDINAL] = INLINE { IF debugging THEN ProcessorFace.SetMP[code]; }; <<>> <> <<>> swapBufferSize: PageCount = VMInternal.swapBufferSize; reservedPriority: Process.Priority = Process.priorityFaultHandlers; swapBuffer: Interval _ VM.nullInterval; -- allocated on the first call of ReserveSwapBuffer <> swapBufferReserved: BOOL _ FALSE; swapBufferAvailable: CONDITION _ [timeout: 0]; CallerBug: ERROR = CODE; <<>> <> swapInCalls, swapInVirtualRuns, swapInPhysicalRuns: PUBLIC INT _ 0; swapInPages, swapInAlreadyIn, swapInNoRead, swapInReads: PUBLIC INT _ 0; swapInDirtyVictims, swapInFailedToCleanVictims: PUBLIC INT _ 0; cleanCalls, cleanVirtualRuns, cleanPhysicalRuns: PUBLIC INT _ 0; cleanPages, cleanWrites, cleanCantWrites: PUBLIC INT _ 0; cleanCheckOutCleans, cleanUnneededCheckOutCleans: PUBLIC INT _ 0; <<>> <<>> <> CantDoIO: PUBLIC SAFE ERROR [reason: IOErrorType, page: PageNumber] = CODE; AddressFault: PUBLIC SAFE ERROR [address: LONG POINTER] = CODE; WriteProtectFault: PUBLIC SAFE ERROR [address: LONG POINTER] = CODE; <> State: PUBLIC SAFE PROC [page: PageNumber] RETURNS [state: PageState] = TRUSTED { ValidateInterval[[page, 1]]; RETURN[VMInternal.State[page]] }; SetDataState: PROC [interval: Interval, dataState: DataState] = { SetOneDataState: PROC[vmPage: PageNumber] RETURNS [VMInternal.Outcome] = { RETURN[VMInternal.SetDataState[vmPage, dataState]] }; DoInterval[interval, SetOneDataState]; IF dataState = $none THEN VMInternal.NoteFreePages[interval]; }; Free: PUBLIC UNSAFE PROC[interval: Interval] = { SetDataState[interval, none]; }; Kill, MakeUndefined: PUBLIC UNSAFE PROC[interval: Interval] = { SetDataState[interval, undefined]; }; MakeUnchanged: PUBLIC SAFE PROC[interval: Interval] = TRUSTED { SetDataState[interval, unchanged]; }; MakeChanged: PUBLIC SAFE PROC[interval: Interval] = TRUSTED { SetDataState[interval, changed]; }; SwapIn: PUBLIC UNSAFE PROC [interval: Interval, kill: BOOL _ FALSE, pin: BOOL _ FALSE, nextPage: PageNumber _ 0] = TRUSTED { <> <<1) Disk reads are not requested individually; rather, runs of consecutive swapped-out pages are built up and passed to the DoReads procedure, which typically can initiate all reads as a single disk request.>> <<2) DoReads (actually, VMInternal.DoIO) breaks up a run of virtual page reads into runs of physically contiguous disk page reads. Typically, the entire virtual page run will be a single physical page run.>> <<3) The call of DoReads after a virtual page run has been completed is generally deferred until the first page of the next run is known. This permits DoReads to issue the physical I/O request and follow it immediately with a request to seek to the starting disk address of the subsequent run.>> <<4) The swap buffer (and the state vector needed to protect it) are not acquired until it is known that a disk operation will occur. This optimizes the frequent case of kill=pin=TRUE, which is used by the file system's Read operation.>> <<5) The swap buffer is of fixed size, and a request to SwapIn an interval larger than the swap buffer may be broken into multiple calls of DoReads, and consequently multiple disk requests, even though the interval could have been swapped in with a single disk request. The size chosen for the swap buffer is supposed to be large enough that this is a rare event.>> <<6) Dirty victims cause the virtual page run being built up to be terminated and DoReads called immediately. Dirty victims are supposed to occur rarely; if they don't, the Laundry process isn't working properly. For the same reason, no attempt is made to build up writes of dirty victims into successive runs.>> pagesInSwapBuffer: PageCount _ 0; haveSwapBuffer: BOOL _ FALSE; swapBufferBase: PageNumber; DoReads: PROC [subsequentSeek: PageNumber] = { swapIndex: PageCount _ 0; --*stats*-- IF pagesInSwapBuffer > 0 THEN swapInVirtualRuns _ swapInVirtualRuns.SUCC; UNTIL swapIndex >= pagesInSwapBuffer DO ioResult: VMInternal.IOResult; countDone: PageCount; CleanUpAndReportError: PROC = --INLINE-- { failedIndex: PageCount = swapIndex + countDone; errorType: IOErrorType; FOR page: PageCount IN [swapIndex..pagesInSwapBuffer) DO VMInternal.SwapInDone[ vmPage: swapBufferBase + page, bufferPage: swapBuffer.page + page, worked: page < failedIndex ]; ENDLOOP; ReleaseSwapBuffer[]; -- pagesInSwapBuffer _ 0; SELECT ioResult FROM labelCheck => errorType _ software; someOtherError => errorType _ hardware; ENDCASE => VMInternal.Crash[]; ERROR CantDoIO[reason: errorType, page: swapBufferBase + failedIndex] }; --*stats*-- swapInPhysicalRuns _ swapInPhysicalRuns.SUCC; [ioResult, countDone] _ VMInternal.DoIO[ direction: read, backingPage: swapBufferBase+swapIndex, interval: [swapBuffer.page+swapIndex, pagesInSwapBuffer-swapIndex], subsequentSeek: subsequentSeek]; IF ioResult ~= ok THEN CleanUpAndReportError[]; FOR page: PageCount IN [swapIndex..swapIndex + countDone) DO VMInternal.SwapInDone[ vmPage: swapBufferBase + page, bufferPage: swapBuffer.page + page, worked: TRUE ]; ENDLOOP; swapIndex _ swapIndex + countDone; ENDLOOP; pagesInSwapBuffer _ 0; }; AddToSwapBuffer: PROC [vmPage: PageNumber, rmPage: VMInternal.RealPageNumber] = { IF ~haveSwapBuffer THEN {ReserveSwapBuffer[]; haveSwapBuffer _ TRUE}; IF SwapBufferEmpty[] THEN swapBufferBase _ vmPage; <> VMInternal.SetPageFlags[ virtual: swapBuffer.page+pagesInSwapBuffer, real: rmPage, flags: PrincOps.flagsNone]; pagesInSwapBuffer _ pagesInSwapBuffer.SUCC; }; SwapBufferEmpty: PROC RETURNS [empty: BOOL] = INLINE { RETURN[pagesInSwapBuffer = 0]}; SwapBufferFull: PROC RETURNS [full: BOOL] = INLINE { RETURN[pagesInSwapBuffer = swapBuffer.count]}; CleanVictim: PROC [ winner: PageNumber, victim: dirty VMInternal.Victim, willReadWinner: BOOL] RETURNS [worked: BOOL] = { <> AddToSwapBuffer[victim.vmPage, victim.realPage]; <> worked _ VMInternal.DoIO[ direction: write, backingPage: swapBufferBase, interval: [swapBuffer.page, 1], subsequentSeek: IF willReadWinner THEN winner ELSE 0].result = ok; --*stats*-- IF worked THEN swapInDirtyVictims _ swapInDirtyVictims.SUCC ELSE swapInFailedToCleanVictims _ swapInFailedToCleanVictims.SUCC; VMInternal.VictimWriteDone[winner, swapBuffer.page, victim, worked]; pagesInSwapBuffer _ 0; VMInternal.NoteDirtyVictim[]; }; state: {reading, skipping} _ reading; -- initially skipping would also be OK, but less efficient page: PageNumber _ interval.page; --*stats*-- swapInCalls _ swapInCalls.SUCC; ValidateInterval[interval]; UNTIL page >= interval.page+interval.count DO outcome: VMInternal.SwapInOutcome; victim: VMInternal.Victim; [outcome, victim] _ VMInternal.AllocateForSwapIn[vmPage: page, kill: kill, pin: pin, dontWait: haveSwapBuffer]; <> IF outcome = couldntCheckOut THEN { IF haveSwapBuffer THEN { DoReads[subsequentSeek: 0]; ReleaseSwapBuffer[]; haveSwapBuffer _ FALSE; }; [outcome, victim] _ VMInternal.AllocateForSwapIn[vmPage: page, kill: kill, pin: pin, dontWait: FALSE]; }; --*stats*-- swapInPages _ swapInPages.SUCC; SELECT outcome FROM noReadNecessary => { <> --*stats*-- swapInNoRead _ swapInNoRead.SUCC; WITH victim: victim SELECT FROM dirty => { DoReads[subsequentSeek: victim.vmPage]; IF ~CleanVictim[page, victim, FALSE] THEN LOOP; }; ENDCASE; VMInternal.SwapInDoneWithoutIO[vmPage: page, victim: victim]; state _ skipping; }; needsRead => { <> --*stats*-- swapInReads _ swapInReads.SUCC; SELECT state FROM reading => { <> WITH victim: victim SELECT FROM dirty => { DoReads[subsequentSeek: victim.vmPage]; IF ~CleanVictim[page, victim, TRUE] THEN LOOP; }; ENDCASE; IF SwapBufferFull[] THEN DoReads[subsequentSeek: page]; }; skipping => { <> DoReads[subsequentSeek: page]; WITH victim: victim SELECT FROM dirty => IF ~CleanVictim[page, victim, TRUE] THEN LOOP; ENDCASE; state _ reading; }; ENDCASE; AddToSwapBuffer[page, victim.realPage]; }; alreadyIn => { <> --*stats*-- swapInAlreadyIn _ swapInAlreadyIn.SUCC; state _ skipping; }; addressFault => { <> DoReads[subsequentSeek: 0]; IF haveSwapBuffer THEN ReleaseSwapBuffer[]; ERROR AddressFault[address: AddressForPageNumber[page]]; }; writeFault => { <> DoReads[subsequentSeek: 0]; IF haveSwapBuffer THEN ReleaseSwapBuffer[]; ERROR WriteProtectFault[address: AddressForPageNumber[page]]; }; ENDCASE => VMInternal.Crash[]; page _ page.SUCC; ENDLOOP; DoReads[subsequentSeek: nextPage]; IF haveSwapBuffer THEN ReleaseSwapBuffer[]; }; Touch: PUBLIC SAFE PROC [interval: Interval] = TRUSTED { SwapIn[interval: interval, kill: FALSE, pin: FALSE]; }; Pin: PUBLIC SAFE PROC [interval: Interval] = TRUSTED { SwapIn[interval: interval, kill: FALSE, pin: TRUE]; }; Unpin: PUBLIC SAFE PROC [interval: Interval] = TRUSTED { <> DoInterval[interval, VMInternal.Unpin]; }; MakeReadOnly: PUBLIC SAFE PROC [interval: Interval] = TRUSTED { <> DoInterval[interval, VMInternal.MakeReadOnly]; }; MakeReadWrite: PUBLIC SAFE PROC [interval: Interval] = TRUSTED { <> DoInterval[interval, VMInternal.MakeReadWrite]; }; Clean: PUBLIC SAFE PROC [interval: Interval] = TRUSTED { <> pagesInSwapBuffer, dirtyPagesInSwapBuffer: PageCount _ 0; haveSwapBuffer: BOOL _ FALSE; swapBufferBase: PageNumber; DoWrites: PROC [subsequentSeek: PageNumber] = { swapIndex: PageCount _ 0; --*stats*-- IF dirtyPagesInSwapBuffer > 0 THEN cleanVirtualRuns _ cleanVirtualRuns.SUCC; <> FOR page: PageCount IN [dirtyPagesInSwapBuffer..pagesInSwapBuffer) DO VMInternal.CleanDone[ vmPage: swapBufferBase + page, bufferPage: swapBuffer.page + page, worked: TRUE ]; ENDLOOP; --*stats*-- cleanUnneededCheckOutCleans _ cleanUnneededCheckOutCleans + pagesInSwapBuffer - dirtyPagesInSwapBuffer; pagesInSwapBuffer _ dirtyPagesInSwapBuffer; UNTIL swapIndex >= pagesInSwapBuffer DO ioResult: VMInternal.IOResult; countDone: PageCount; CleanUpAndReportError: PROC = --INLINE-- { failedIndex: PageCount = swapIndex + countDone; errorType: IOErrorType; FOR page: PageCount IN [swapIndex..pagesInSwapBuffer) DO VMInternal.CleanDone[ vmPage: swapBufferBase + page, bufferPage: swapBuffer.page + page, worked: page < failedIndex ]; ENDLOOP; ReleaseSwapBuffer[]; -- pagesInSwapBuffer _ 0; SELECT ioResult FROM labelCheck => errorType _ software; someOtherError => errorType _ hardware; ENDCASE => VMInternal.Crash[]; ERROR CantDoIO[reason: errorType, page: swapBufferBase + failedIndex] }; --*stats*-- cleanPhysicalRuns _ cleanPhysicalRuns.SUCC; [ioResult, countDone] _ VMInternal.DoIO[ direction: write, backingPage: swapBufferBase+swapIndex, interval: [swapBuffer.page+swapIndex, pagesInSwapBuffer-swapIndex], subsequentSeek: subsequentSeek]; --*stats*-- cleanPages _ cleanPages + countDone; IF ioResult ~= ok THEN CleanUpAndReportError[]; FOR page: PageCount IN [swapIndex..swapIndex + countDone) DO VMInternal.CleanDone[ vmPage: swapBufferBase + page, bufferPage: swapBuffer.page + page, worked: TRUE ]; ENDLOOP; swapIndex _ swapIndex + countDone; ENDLOOP; pagesInSwapBuffer _ dirtyPagesInSwapBuffer _ 0; }; AddToSwapBuffer: PROC [vmPage: PageNumber, real: VMInternal.RealPageNumber] = { IF ~haveSwapBuffer THEN {ReserveSwapBuffer[]; haveSwapBuffer _ TRUE}; IF SwapBufferEmpty[] THEN swapBufferBase _ vmPage; <> VMInternal.SetPageFlags[ virtual: swapBuffer.page+pagesInSwapBuffer, real: real, flags: PrincOps.flagsReadOnly]; pagesInSwapBuffer _ pagesInSwapBuffer.SUCC; }; SwapBufferEmpty: PROC RETURNS [empty: BOOL] = INLINE { RETURN[pagesInSwapBuffer = 0]}; SwapBufferFull: PROC RETURNS [full: BOOL] = INLINE { RETURN[pagesInSwapBuffer = swapBuffer.count]}; state: {writing, skipping} _ writing; page: PageNumber _ interval.page; --*stats*-- cleanCalls _ cleanCalls.SUCC; ValidateInterval[interval]; UNTIL page >= interval.page+interval.count DO outcome: VMInternal.CleanOutcome _ cantWrite; realPage: VMInternal.RealPageNumber; IF VMInternal.HasBackingStorage[page] THEN [outcome, realPage] _ VMInternal.ConsiderCleaning[ vmPage: page, checkOutClean: ~SwapBufferEmpty[] AND ~SwapBufferFull[]]; SELECT outcome FROM checkedOutClean => { <> --*stats*-- cleanCheckOutCleans _ cleanCheckOutCleans.SUCC; AddToSwapBuffer[page, realPage]; }; needsWrite => { <> --*stats*-- cleanWrites _ cleanWrites.SUCC; SELECT state FROM writing => { <> IF SwapBufferFull[] THEN DoWrites[subsequentSeek: page]; }; skipping => { <> state _ writing; DoWrites[subsequentSeek: page]; }; ENDCASE; AddToSwapBuffer[page, realPage]; dirtyPagesInSwapBuffer _ pagesInSwapBuffer; }; cantWrite => { <> --*stats*-- cleanCantWrites _ cleanCantWrites.SUCC; state _ skipping; }; addressFault => { <> DoWrites[subsequentSeek: 0]; IF haveSwapBuffer THEN ReleaseSwapBuffer[]; ERROR AddressFault[address: AddressForPageNumber[page]]; }; ENDCASE => VMInternal.Crash[]; page _ page.SUCC; ENDLOOP; DoWrites[subsequentSeek: 0]; IF haveSwapBuffer THEN ReleaseSwapBuffer[]; }; Age: PUBLIC SAFE PROC [interval: Interval] = TRUSTED { DoInterval[interval, VMInternal.Age]; }; <> <<>> AssignSpecialRealMemory: PUBLIC SAFE PROC [interval: Interval] = TRUSTED { buffer: PageNumber; specialPage: PageNumber; pagesCopied: CARDINAL _ 0; pagesRead: CARDINAL _ 0; pagesSkipped: CARDINAL _ 0; AssignSpecialRealMemoryPage: PROC [vmPage: PageNumber] RETURNS [outcome: VMInternal.Outcome _ $ok]= { smo: VMInternal.SpecialMemoryOutcome _ VMInternal.PrepareToAllocateSpecialRealMemory[vmPage, buffer, specialPage]; SELECT smo FROM needsCopy => { PrincOpsUtils.LongCopy[ from: AddressForPageNumber[buffer], to: AddressForPageNumber[specialPage], nwords: wordsPerPage ]; pagesCopied _ pagesCopied + 1; }; needsIO => { errorType: IOErrorType; SELECT VMInternal.DoIO[ direction: read, backingPage: vmPage, interval: [specialPage, 1], subsequentSeek: vmPage+1].result FROM ok => GO TO allIsWell; labelCheck => errorType _ software; someOtherError => errorType _ hardware; ENDCASE => VMInternal.Crash[]; VMInternal.FinishAllocateSpecialRealMemory[vmPage, buffer, specialPage, FALSE]; ReleaseSwapBuffer[]; ERROR CantDoIO[reason: errorType, page: vmPage]; EXITS allIsWell => pagesRead _ pagesRead + 1; }; noTransfer => pagesSkipped _ pagesSkipped + 1; addressFault => RETURN[$addressFault]; badParameter => {ReleaseSwapBuffer[]; ERROR CallerBug}; noMemory => {ReleaseSwapBuffer[]; ERROR CantDoIO[software, vmPage]}; ENDCASE; VMInternal.FinishAllocateSpecialRealMemory[vmPage, buffer, specialPage, TRUE]; }; ReserveSwapBuffer[]; specialPage _ (buffer _ swapBuffer.page) + swapBuffer.count - 1; DoInterval[interval, AssignSpecialRealMemoryPage]; ReleaseSwapBuffer[]; }; ReleaseSpecialRealMemory: PUBLIC SAFE PROC [interval: Interval] = TRUSTED { specialPage: PageNumber; pagesWritten: CARDINAL _ 0; pagesSkipped: CARDINAL _ 0; ReleaseSpecialRealMemoryPage: PROC [vmPage: PageNumber] RETURNS [outcome: VMInternal.Outcome _ $ok]= { smo: VMInternal.SpecialMemoryOutcome _ VMInternal.PrepareToReleaseSpecialRealMemory[vmPage, specialPage]; SELECT smo FROM needsIO => { errorType: IOErrorType; SELECT VMInternal.DoIO[ direction: write, backingPage: vmPage, interval: [specialPage, 1], subsequentSeek: vmPage+1].result FROM ok => GO TO allIsWell; labelCheck => errorType _ software; someOtherError => errorType _ hardware; ENDCASE => VMInternal.Crash[]; VMInternal.FinishReleaseSpecialRealMemory[vmPage, specialPage, FALSE]; ReleaseSwapBuffer[]; ERROR CantDoIO[reason: errorType, page: vmPage]; EXITS allIsWell => pagesWritten _ pagesWritten + 1; }; noTransfer => pagesSkipped _ pagesSkipped + 1; addressFault => RETURN[$addressFault]; badParameter => {ReleaseSwapBuffer[]; ERROR CallerBug}; noMemory => {ReleaseSwapBuffer[]; ERROR CantDoIO[software, vmPage]}; ENDCASE => VMInternal.Crash[]; VMInternal.FinishReleaseSpecialRealMemory[vmPage, specialPage, TRUE]; }; ReserveSwapBuffer[]; specialPage _ swapBuffer.page; DoInterval[interval, ReleaseSpecialRealMemoryPage]; ReleaseSwapBuffer[]; }; <<>> <<>> <> DoInterval: --EXTERNAL-- PROC [ interval: Interval, perPage: PROC [vmPage: PageNumber] RETURNS [outcome: VMInternal.Outcome]] = { ValidateInterval[interval]; FOR page: PageNumber IN [interval.page..interval.page+interval.count) DO SELECT perPage[page] FROM $ok => NULL; $addressFault => ERROR AddressFault[AddressForPageNumber[page]]; ENDCASE => VMInternal.Crash[]; ENDLOOP; }; <<>> ValidateInterval: --EXTERNAL-- PROC [interval: Interval] = { IF interval.page + interval.count > VMInternal.lastVMPage + 1 THEN ERROR AddressFault[AddressForPageNumber[VMInternal.lastVMPage + 1]] }; ReserveSwapBuffer: PROC = INLINE { ReserveSwapBufferEntry: ENTRY PROC = INLINE { WHILE swapBufferReserved DO WAIT swapBufferAvailable; ENDLOOP; swapBufferReserved _ TRUE; }; ReserveStateVector[]; ReserveSwapBufferEntry[]; IF swapBuffer.count = 0 THEN swapBuffer _ VM.Allocate[count: swapBufferSize ! VM.CantAllocate => VMInternal.Crash[]]; }; ReleaseSwapBuffer: PROC = INLINE { ReleaseSwapBufferEntry: ENTRY PROC = INLINE { swapBufferReserved _ FALSE; NOTIFY swapBufferAvailable; }; ReleaseSwapBufferEntry[]; ReleaseStateVector[]; }; <<>> <> <> <> <> <> <<>> stateVectorReserved: BOOL _ FALSE; stateVectorAvailable: CONDITION _ [timeout: 0]; oldPriority: Process.Priority; ReserveStateVector: PROC = INLINE { ReserveInner: ENTRY PROC = INLINE { WHILE stateVectorReserved DO WAIT stateVectorAvailable; ENDLOOP; stateVectorReserved _ TRUE; }; ReserveInner[]; oldPriority _ Process.GetPriority[]; IF oldPriority ~= reservedPriority THEN Process.SetPriority[reservedPriority]; }; ReleaseStateVector: PROC = INLINE { ReleaseInner: ENTRY PROC = INLINE { stateVectorReserved _ FALSE; NOTIFY stateVectorAvailable; }; p: Process.Priority = oldPriority; ReleaseInner[]; IF p ~= reservedPriority THEN Process.SetPriority[p]; }; END.