<> <> <> <> <<>> DIRECTORY PrincOps USING [flagsDirty, flagsVacant, PageFlags, PageState], PrincOpsUtils USING [DisableInterrupts, EnableInterrupts], VM USING [nullInterval], VMInternal USING [AddToFreeList, AgeInternal, AllocateRealMemoryInternal, checkIn, cleaningRover, CleanOutcome, Crash, GetVMMap, InOut, Interval, lastRealPage, LaundryMode, maxPinCount, Outcome, PageCount, PageNumber, PageStateFromFlags, RealPageNumber, RMEntryPointer, rmMap, RMMapEntry, SetVMMap, SwapInOutcome, Victim, VMMapEntry, vmStateLock], VMStatistics USING [checkoutConflicts, pinnedPages, rmCleanPasses, trappedPages]; VMSwapImpl: MONITOR LOCKS VMInternal.vmStateLock IMPORTS PrincOpsUtils, VMInternal, VMStatistics EXPORTS VMInternal SHARES VMInternal = BEGIN OPEN VMInternal, VMStatistics; <> AllocateForSwapIn: PUBLIC ENTRY PROC [vmPage: PageNumber, kill, pin: BOOL, dontWait: BOOL] RETURNS [outcome: SwapInOutcome, victim: Victim] = { <> vmEntry: VMMapEntry; success: BOOL; [vmEntry, success] _ GetCheckedInVMMap[vmPage, dontWait]; IF ~success THEN RETURN [outcome: couldntCheckOut, victim: NULL]; WITH vmE: vmEntry SELECT InOut[vmEntry] FROM out => { IF vmE.dataState = none THEN RETURN [outcome: addressFault, victim: NULL]; IF kill THEN IF vmE.readOnly THEN RETURN [outcome: writeFault, victim: NULL] ELSE vmE.dataState _ undefined; outcome _ IF vmE.dataState = undefined THEN noReadNecessary ELSE needsRead; vmE.checkedOut _ TRUE; SetVMMap[vmPage, vmE]; victim _ AllocateRealMemoryInternal[vmPage: vmPage, pin: pin]; <> }; in => { rmE: RMEntryPointer = @rmMap[vmE.real]; outcome _ alreadyIn; IF kill THEN { <> IF vmE.state.flags.readonly THEN RETURN [outcome: writeFault, victim: NULL]; vmE.state.flags.dirty _ rmE.needsBackingStoreWrite _ FALSE; SetVMMap[vmPage, vmE]; rmE.dataState _ undefined; }; IF pin THEN { WITH rmE: rmE SELECT FROM free => Crash[]; reclaimable => { rmMap[vmE.real].body _ pinned[pinCount: 1]; --*stats*-- pinnedPages _ pinnedPages.SUCC; }; pinned => IF rmE.pinCount < maxPinCount THEN rmE.pinCount _ rmE.pinCount + 1 ELSE Crash[]; ENDCASE; }; }; ENDCASE; }; SwapInDone: PUBLIC ENTRY PROC [vmPage, bufferPage: PageNumber, worked: BOOL] = { <> vmEntry: VMMapEntry _ GetVMMap[vmPage]; WITH vmE: vmEntry SELECT InOut[vmEntry] FROM out => { bufferEntry: VMMapEntry _ GetVMMap[bufferPage]; WITH bE: bufferEntry SELECT InOut[bufferEntry] FROM in => { rmE: RMEntryPointer = @rmMap[bE.real]; IF worked THEN { --*stats*-- SELECT rmE.rmState FROM free => Crash[]; pinned => pinnedPages _ pinnedPages.SUCC; reclaimable => NULL; ENDCASE; bE.state _ VMInternal.PageStateFromFlags[ [readonly: vmE.readOnly, dirty: FALSE, referenced: TRUE]]; SetVMMap[vmPage, bE]; } ELSE { IF rmE.rmState = free THEN Crash[]; AddToFreeList[bE.real]; vmE.checkedOut _ FALSE; SetVMMap[vmPage, vmEntry]; }; <> BROADCAST checkIn; <> vmE.checkedOut _ vmE.readOnly _ FALSE; vmE.dataState _ undefined; SetVMMap[bufferPage, vmE]; }; out => Crash[]; ENDCASE; }; in => Crash[]; ENDCASE; }; SwapInDoneWithoutIO: PUBLIC ENTRY PROC [vmPage: PageNumber, victim: Victim] = { vmEntry: VMMapEntry = GetVMMap[vmPage]; WITH vmE: vmEntry SELECT InOut[vmEntry] FROM out => { SetVMMap[vmPage, [ state: VMInternal.PageStateFromFlags[ [readonly: vmE.readOnly, dirty: FALSE, referenced: TRUE]], body: in[victim.realPage] ]]; <> BROADCAST checkIn; --*stats*-- SELECT rmMap[victim.realPage].rmState FROM free => Crash[]; pinned => pinnedPages _ pinnedPages.SUCC; reclaimable => NULL; ENDCASE; }; in => Crash[]; ENDCASE; }; VictimWriteDone: PUBLIC ENTRY PROC [ vmPage, bufferPage: PageNumber, victim: dirty Victim, worked: BOOL] = { vmEntry: VMMapEntry _ GetVMMap[vmPage]; WITH vmE: vmEntry SELECT InOut[vmEntry] FROM out => { IF ~worked THEN { <> victimEntry: VMMapEntry = [ state: VMInternal.PageStateFromFlags[PrincOps.flagsDirty], body: in[victim.realPage]]; rmE: RMEntryPointer = @rmMap[victim.realPage]; IF rmE.rmState = free THEN Crash[]; rmE^ _ [ dataState: vmE.dataState, needsBackingStoreWrite: TRUE, body: pinned[pinReason: cantBeWritten, pinCount: 1]]; SetVMMap[victim.vmPage, victimEntry]; --*stats*-- pinnedPages _ pinnedPages.SUCC; --*stats*-- trappedPages _ trappedPages.SUCC; <> vmE.checkedOut _ FALSE; SetVMMap[vmPage, vmE]; BROADCAST checkIn; }; <> vmE.readOnly _ vmE.checkedOut _ FALSE; vmE.dataState _ undefined; SetVMMap[bufferPage, vmE]; }; in => Crash[]; ENDCASE; }; ConsiderCleaning: PUBLIC ENTRY PROC [vmPage: PageNumber, checkOutClean: BOOL] RETURNS [outcome: CleanOutcome, real: RealPageNumber] = { <> <> vmEntry: VMMapEntry; PrincOpsUtils.DisableInterrupts[]; vmEntry _ GetVMMap[vmPage]; WITH vmE: vmEntry SELECT InOut[vmEntry] FROM out => outcome _ IF vmE.dataState = none THEN addressFault ELSE cantWrite; in => { rmE: RMEntryPointer = @rmMap[real _ vmE.real]; WITH rmE: rmE SELECT FROM free => Crash[]; reclaimable => { dirty: BOOL = vmE.state.flags.dirty OR rmE.needsBackingStoreWrite; IF dirty OR checkOutClean THEN { newEntry: VMMapEntry = [ state: VMInternal.PageStateFromFlags[PrincOps.flagsVacant], body: out[ checkedOut: TRUE, readOnly: vmE.state.flags.readonly, dataState: IF vmE.state.flags.dirty THEN changed ELSE rmE.dataState ]]; rmE.referenced _ vmE.state.flags.referenced; -- save until CleanDone SetVMMap[vmPage, newEntry]; }; outcome _ SELECT TRUE FROM dirty => needsWrite, checkOutClean => checkedOutClean, ENDCASE => cantWrite; }; pinned => outcome _ cantWrite; ENDCASE; }; ENDCASE; PrincOpsUtils.EnableInterrupts[]; }; CleanDone: PUBLIC ENTRY PROC [vmPage, bufferPage: PageNumber, worked: BOOL] = { <> vmEntry: VMMapEntry _ GetVMMap[vmPage]; WITH vmE: vmEntry SELECT InOut[vmEntry] FROM out => { bufferEntry: VMMapEntry _ GetVMMap[bufferPage]; WITH bE: bufferEntry SELECT InOut[bufferEntry] FROM in => { rmEntry: RMEntryPointer = @rmMap[bE.real]; WITH rmE: rmEntry SELECT FROM reclaimable => { newEntry: VMMapEntry = [ state: VMInternal.PageStateFromFlags[ [readonly: vmE.readOnly, dirty: FALSE, referenced: rmE.referenced]], body: in[real: bE.real] ]; IF rmE.virtual ~= vmPage THEN Crash[]; IF worked THEN { rmE.dataState _ vmE.dataState; -- computed by ConsiderCleaning rmE.needsBackingStoreWrite _ FALSE; } ELSE { rmEntry^ _ [ dataState: vmE.dataState, needsBackingStoreWrite: TRUE, body: pinned[pinReason: cantBeWritten, pinCount: 1]]; --*stats*-- pinnedPages _ pinnedPages.SUCC; --*stats*-- trappedPages _ trappedPages.SUCC; }; SetVMMap[vmPage, newEntry]; <> BROADCAST checkIn; }; free, pinned => Crash[]; ENDCASE; }; out => Crash[]; ENDCASE; vmE.checkedOut _ FALSE; vmE.dataState _ undefined; SetVMMap[bufferPage, vmE]; }; in => Crash[]; ENDCASE; }; <> Age: PUBLIC ENTRY PROC [vmPage: PageNumber] RETURNS [outcome: Outcome _ ok] = { <> <> vmEntry: VMMapEntry; PrincOpsUtils.DisableInterrupts[]; vmEntry _ GetVMMap[vmPage]; WITH vmE: vmEntry SELECT InOut[vmEntry] FROM out => IF vmE.dataState = none THEN outcome _ addressFault; in => AgeInternal[vmPage, vmE]; ENDCASE; PrincOpsUtils.EnableInterrupts[]; }; <<>> <> GetCleaningCandidate: PUBLIC ENTRY PROC [ desired: PageCount, comfortLevel: PageCount, tryHard: LaundryMode] RETURNS [interval: Interval _ VM.nullInterval, cleanSkipped: PageCount _ 0, passes: INT, rover: RealPageNumber] = { <> firstPass: BOOL _ TRUE; ExpandAroundVP: PROC [vP: PageNumber] RETURNS [interval: Interval] = INLINE { <> lowerLimit: PageNumber = (IF vP < desired THEN 0 ELSE vP - desired).SUCC; p: PageNumber _ vP; interval.page _ vP; UNTIL interval.page = lowerLimit DO vmPage: PageNumber = interval.page.PRED; vmEntry: VMMapEntry = GetVMMap[vmPage]; WITH vmE: vmEntry SELECT InOut[vmEntry] FROM in => WITH rmMap[vmE.real] SELECT FROM rmE: reclaimable RMMapEntry => IF rmE.virtual ~= vmPage OR -- in swap buffer ~(vmE.state.flags.dirty OR rmE.needsBackingStoreWrite) OR (vmE.state.flags.referenced AND tryHard = casual AND (vP-vmPage > 5)) THEN EXIT; rmE: pinned RMMapEntry => EXIT; rmE: free RMMapEntry => Crash[]; ENDCASE; out => EXIT; ENDCASE; interval.page _ vmPage; ENDLOOP; UNTIL (p - interval.page).SUCC = desired OR p = lastRealPage DO vmPage: PageNumber = p.SUCC; vmEntry: VMMapEntry = GetVMMap[vmPage]; WITH vmE: vmEntry SELECT InOut[vmEntry] FROM in => WITH rmMap[vmE.real] SELECT FROM rmE: reclaimable RMMapEntry => IF rmE.virtual ~= vmPage OR -- in swap buffer ~(vmE.state.flags.dirty OR rmE.needsBackingStoreWrite) OR (vmE.state.flags.referenced AND tryHard = casual AND (vP-vmPage > 5)) THEN EXIT; rmE: pinned RMMapEntry => EXIT; rmE: free RMMapEntry => Crash[]; ENDCASE; out => EXIT; ENDCASE; p _ vmPage; ENDLOOP; interval.count _ (p - interval.page).SUCC; }; cleanPages: PageCount _ 0; current: RealPageNumber _ cleaningRover; recentDirtyFound: BOOL _ FALSE; DO IF current = RealPageNumber.FIRST THEN { current _ lastRealPage; --*stats*-- rmCleanPasses _ rmCleanPasses.SUCC; } ELSE current _ current.PRED; SELECT TRUE FROM current = cleaningRover => <> IF firstPass AND recentDirtyFound AND tryHard # casual THEN { firstPass _ FALSE; cleanPages _ 0; } ELSE EXIT; tryHard = casual AND cleanPages >= comfortLevel => { cleanSkipped _ cleanPages; EXIT; }; ENDCASE; WITH rmMap[current] SELECT FROM rmE: reclaimable RMMapEntry => { vP: PageNumber = rmE.virtual; vmEntry: VMMapEntry = GetVMMap[vP]; WITH vmE: vmEntry SELECT InOut[vmEntry] FROM in => { refed: BOOL = vmE.state.flags.referenced; dirty: BOOL = vmE.state.flags.dirty OR rmE.needsBackingStoreWrite; IF vmE.real ~= current THEN Crash[]; IF dirty THEN IF refed AND firstPass THEN recentDirtyFound _ TRUE ELSE {interval _ ExpandAroundVP[vP]; cleanSkipped _ cleanPages; EXIT} ELSE cleanPages _ cleanPages.SUCC; }; out => NULL; -- probably being swapped in ENDCASE; }; ENDCASE => NULL; ENDLOOP; cleaningRover _ current; passes _ rmCleanPasses; rover _ cleaningRover; }; <<>> <> GetCheckedInVMMap: INTERNAL PROC [vmPage: PageNumber, dontWait: BOOL _ FALSE] RETURNS [vmEntry: VMMapEntry, success: BOOL _ TRUE] = INLINE { firstTime: BOOL _ TRUE; DO vmEntry _ GetVMMap[vmPage]; WITH vmE: vmEntry SELECT InOut[vmEntry] FROM in => EXIT; out => <> IF ~vmE.checkedOut OR vmE.dataState = none THEN EXIT; ENDCASE; IF dontWait THEN {success_ FALSE; EXIT}; <<*stats*-->> IF firstTime THEN {checkoutConflicts _ checkoutConflicts.SUCC; firstTime _ FALSE}; WAIT checkIn; ENDLOOP; }; END.