<> <> DIRECTORY PrincOps USING [flagsNone, flagsDirty, flagsVacant, InterimPageState, PageState, Port], PrincOpsUtils USING [ DisableInterrupts, EnableInterrupts, GetReturnLink, IsVacant, PageStateFromFlags, SetPageState, SetReturnLink], VM USING [nullInterval], VMBacking USING [BriefPageState], VMInternal USING [ AddToFreeList, AllocCount, CleanOutcome, Crash, DataState, GetVMMap, InitializeTables, InOut, Interval, maxPinCount, Outcome, PageCount, PageNumber, PageState, RealPageNumber, RMMapEntry, RMMapEntries, RMEntryPointer, SetVMMap, SwapInOutcome, Victim, VMMapEntry, VMPartition], VMSideDoor USING [], VMStatistics USING []; VMStateImpl: MONITOR LOCKS vmStateLock IMPORTS PrincOpsUtils, VMInternal EXPORTS VMBacking, VMInternal, VMSideDoor, VMStatistics SHARES VMInternal = BEGIN OPEN VMInternal; <<>> <> <<>> <> <<>> <> <<>> <> <<>> <> <<>> <> <> <> vmStateLock: PUBLIC MONITORLOCK; <> freeList: PUBLIC RealPageNumber; freePages: PUBLIC INT _ 0; rmMap: PUBLIC LONG POINTER TO RMMapEntries; lastRealPage: PUBLIC RealPageNumber; <> allocationRover: RealPageNumber _ RealPageNumber.FIRST; <> cleaningRover: RealPageNumber _ RealPageNumber.FIRST; <> checkIn: CONDITION _ [timeout: 0]; <> <<>> rmReclamations: PUBLIC INT _ 0; rmFreeList, rmOldClean, rmNewClean, rmDirty: PUBLIC INT _ 0; rmAllocPasses, rmCleanPasses: PUBLIC INT _ 0; readOnlyPages: PUBLIC INT _ 0; pinnedPages, trappedPages: PUBLIC INT _ 0; checkoutConflicts: PUBLIC INT _ 0; <<>> VirtualAllocation: PUBLIC PROC [partition: VMPartition] RETURNS [pagesAllocated, pagesFreed, pagesInPartition: PageCount] = { RETURN[ pagesAllocated: allocCounts[partition].pagesAllocated, pagesFreed: allocCounts[partition].pagesFreed, pagesInPartition: partitions[partition].count ] }; <> <<>> AssignSpecialRealMemory: PUBLIC SAFE PROC [interval: Interval] = TRUSTED { ERROR -- not yet implemented }; ReleaseSpecialRealMemory: PUBLIC SAFE PROC [interval: Interval] = TRUSTED { ERROR -- not yet implemented }; <<>> <<>> <> <<>> StateFromMapEntry: PUBLIC SAFE PROC [map: PrincOps.InterimPageState] RETURNS [VMBacking.BriefPageState] = TRUSTED { <> vmEntry: VMMapEntry _ [ state: PrincOpsUtils.PageStateFromFlags[map.flags], body: in[real: map.realPage] ]; WITH vmE: vmEntry SELECT InOut[vmEntry] FROM out => RETURN[ SELECT vmE.dataState FROM none => free, undefined => killed, ENDCASE => active ]; in => RETURN[active]; ENDCASE => ERROR; }; RecoverRealMemory: PUBLIC PROC = { <> vmPage: PageNumber _ 0; THROUGH [0..freePages) DO realPage: RealPageNumber = freeList; UNTIL PrincOpsUtils.IsVacant[vmPage] DO vmPage _ vmPage.SUCC; ENDLOOP; PrincOpsUtils.SetPageState[ vmPage, realPage, PrincOpsUtils.PageStateFromFlags[PrincOps.flagsNone]]; vmPage _ vmPage.SUCC; WITH rmMap[realPage] SELECT FROM rmE: free RMMapEntry => freeList _ rmE.next; ENDCASE => Crash[]; ENDLOOP; }; <<>> <> <<>> <> <<>> partitions: PUBLIC ARRAY VMPartition OF Interval; <<>> --*stats*-- allocCounts: PUBLIC ARRAY VMPartition OF AllocCount _ ALL[[0, 0, 0, 0]]; <> <<>> AllocateRealMemoryInternal: PUBLIC PROC [ vmPage: PageNumber, dirtyVictimOK: BOOL _ TRUE, pin: BOOL _ FALSE] RETURNS [victim: Victim] _ LOOPHOLE[@AwaitAllocateRealMemoryInternal]; <> Unpin: PUBLIC ENTRY PROC [vmPage: PageNumber] RETURNS [outcome: Outcome _ ok] = { vmEntry: VMMapEntry = GetCheckedInVMMap[vmPage]; WITH vmE: vmEntry SELECT InOut[vmEntry] FROM in => { rmE: RMEntryPointer = @rmMap[vmE.real]; WITH rmE: rmE SELECT FROM free => Crash[]; reclaimable => NULL; pinned => <> IF rmE.pinReason = normal THEN SELECT rmE.pinCount FROM 0 => Crash[]; 1 => { rmMap[vmE.real].body _ reclaimable[virtual: vmPage]; --*stats*-- pinnedPages _ pinnedPages.PRED; }; ENDCASE => rmE.pinCount _ rmE.pinCount - 1; ENDCASE; }; out => IF vmE.dataState = none THEN outcome _ addressFault; ENDCASE; }; <<>> <> State: PUBLIC ENTRY PROC [vmPage: PageNumber] RETURNS [state: PageState] = { <> vmEntry: VMMapEntry = GetVMMap[vmPage]; WITH vmE: vmEntry SELECT InOut[vmEntry] FROM out => state _ [ dataState: vmE.dataState, readOnly: vmE.readOnly, hasRealMemory: FALSE, needsCleaning: FALSE, pinCount: 0 ]; in => { rmE: RMEntryPointer = @rmMap[vmE.real]; state _ [ dataState: IF vmE.state.flags.dirty THEN changed ELSE rmE.dataState, readOnly: vmE.state.flags.readonly, hasRealMemory: TRUE, needsCleaning: vmE.state.flags.dirty OR rmE.needsBackingStoreWrite, pinCount: WITH rmE^ SELECT FROM pinned => pinCount, ENDCASE => 0 ]; }; ENDCASE; }; SetDataState: PUBLIC ENTRY PROC [vmPage: PageNumber, dataState: DataState] RETURNS [outcome: Outcome _ ok] = { <> vmEntry: VMMapEntry _ GetCheckedInVMMap[vmPage]; WITH vmE: vmEntry SELECT InOut[vmEntry] FROM out => IF vmE.dataState = none THEN outcome _ addressFault ELSE {vmE.dataState _ dataState; SetVMMap[vmPage, vmE]}; in => { rmE: RMEntryPointer = @rmMap[vmE.real]; SELECT dataState FROM none => { IF rmE.rmState = free THEN Crash[]; SetVMMap[vmPage, [state: PrincOpsUtils.PageStateFromFlags[PrincOps.flagsVacant], body: out[checkedOut: FALSE, readOnly: FALSE, dataState: dataState]] ]; AddToFreeList[vmE.real]; }; undefined => { WITH rmE: rmE SELECT FROM free => Crash[]; reclaimable => { SetVMMap[vmPage, [state: PrincOpsUtils.PageStateFromFlags[PrincOps.flagsVacant], body: out[checkedOut: FALSE, readOnly: FALSE, dataState: dataState]] ]; AddToFreeList[vmE.real]; }; pinned => { <> vmE.state.flags.dirty _ rmE.needsBackingStoreWrite _ FALSE; SetVMMap[vmPage, vmE]; rmE.dataState _ dataState; }; ENDCASE; }; unchanged => { newEntry: VMMapEntry; <> PrincOpsUtils.DisableInterrupts[]; newEntry _ GetVMMap[vmPage]; WITH newE: newEntry SELECT InOut[newEntry] FROM in => IF newE.state.flags.dirty THEN { rmE.needsBackingStoreWrite _ TRUE; newE.state.flags.dirty _ FALSE; SetVMMap[vmPage, newE]; }; out => Crash[]; ENDCASE; PrincOpsUtils.EnableInterrupts[]; rmE.dataState _ dataState; }; changed => rmE.dataState _ dataState; ENDCASE; }; ENDCASE; }; < ReadWrite>> MakeReadOnly: PUBLIC ENTRY PROC [vmPage: PageNumber] RETURNS [outcome: Outcome _ ok] = { <> vmEntry: VMMapEntry _ GetCheckedInVMMap[vmPage]; PrincOpsUtils.DisableInterrupts[]; vmEntry _ GetVMMap[vmPage]; -- reread map to ensure atomicity WITH vmE: vmEntry SELECT InOut[vmEntry] FROM out => IF vmE.dataState = none THEN outcome _ addressFault ELSE IF ~vmE.readOnly THEN { vmE.readOnly _ TRUE; SetVMMap[vmPage, vmE]; --*stats*-- readOnlyPages _ readOnlyPages.SUCC; }; in => IF ~vmE.state.flags.readonly THEN { IF vmE.state.flags.dirty THEN { rmMap[vmE.real].needsBackingStoreWrite _ TRUE; vmE.state.flags.dirty _ FALSE; rmMap[vmE.real].dataState _ changed; }; vmE.state.flags.readonly _ TRUE; SetVMMap[vmPage, vmE]; --*stats*-- readOnlyPages _ readOnlyPages.SUCC; }; ENDCASE; PrincOpsUtils.EnableInterrupts[]; }; MakeReadWrite: PUBLIC ENTRY PROC [vmPage: PageNumber] RETURNS [outcome: Outcome _ ok] = { <> vmEntry: VMMapEntry _ GetCheckedInVMMap[vmPage]; PrincOpsUtils.DisableInterrupts[]; vmEntry _ GetVMMap[vmPage]; -- reread map to ensure atomicity WITH vmE: vmEntry SELECT InOut[vmEntry] FROM out => IF vmE.dataState = none THEN outcome _ addressFault ELSE IF vmE.readOnly THEN { vmE.readOnly _ FALSE; SetVMMap[vmPage, vmE]; --*stats*-- readOnlyPages _ readOnlyPages.PRED; }; in => IF vmE.state.flags.readonly THEN { vmE.state.flags.readonly _ FALSE; SetVMMap[vmPage, vmE]; --*stats*-- readOnlyPages _ readOnlyPages.PRED; }; ENDCASE; PrincOpsUtils.EnableInterrupts[]; }; <> AllocateForSwapIn: PUBLIC ENTRY PROC [vmPage: PageNumber, kill, pin: BOOL] RETURNS [outcome: SwapInOutcome, victim: Victim] = { <> vmEntry: VMMapEntry _ GetCheckedInVMMap[vmPage]; 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 _ PrincOpsUtils.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: PrincOpsUtils.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: PrincOpsUtils.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: PrincOpsUtils.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: PrincOpsUtils.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: BOOL _ FALSE] RETURNS [interval: Interval _ VM.nullInterval] = { <> 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 firstPass) 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 firstPass) 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 THEN { firstPass _ FALSE; cleanPages _ 0; } ELSE EXIT; ~tryHard AND cleanPages >= comfortLevel => 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]; EXIT} ELSE cleanPages _ cleanPages.SUCC; }; out => NULL; -- probably being swapped in ENDCASE; }; ENDCASE => NULL; ENDLOOP; cleaningRover _ current; }; <<>> <> <<>> AwaitAllocateRealMemoryInternal: PORT [victim: Victim] RETURNS [vmPage: PageNumber, dirtyVictimOK, pin: BOOL]; InitializeAllocateRealMemoryInternal: PROC RETURNS [victim: Victim] = { LOOPHOLE[AwaitAllocateRealMemoryInternal, PrincOps.Port].dest _ PrincOpsUtils.GetReturnLink[]; DO vmPage: PageNumber; dirtyVictimOK, pin: BOOL; [vmPage, dirtyVictimOK, pin] _ AwaitAllocateRealMemoryInternal[victim]; <> PrincOpsUtils.SetReturnLink[LOOPHOLE[AwaitAllocateRealMemoryInternal, PrincOps.Port].dest]; BEGIN <> targetVMEntry: VMMapEntry _ GetVMMap[vmPage]; WITH tVM: targetVMEntry SELECT InOut[targetVMEntry] FROM out => { IF freePages > 0 THEN { <> victim _ [realPage: freeList, body: clean[]]; WITH rmMap[freeList] SELECT FROM rmE: free RMMapEntry => {freeList _ rmE.next; freePages _ freePages.PRED}; ENDCASE => Crash[]; -- free list trashed --*stats*-- rmFreeList _ rmFreeList.SUCC; } ELSE { <> current: RealPageNumber _ allocationRover; firstPass: BOOL _ TRUE; secondPassWorthWhile: BOOL _ FALSE; victimP: PageNumber; dirtyVictimState: {none, unreferenced, referenced} _ none; dirtyVictimRP: RealPageNumber; dirtyVictimDataState: DataState; DO IF current = RealPageNumber.FIRST THEN { current _ lastRealPage; --*stats*-- rmAllocPasses _ rmAllocPasses.SUCC; } ELSE current _ current.PRED; IF current = allocationRover THEN -- a pass has completed SELECT TRUE FROM firstPass AND secondPassWorthWhile => firstPass _ FALSE; dirtyVictimOK => IF dirtyVictimState ~= none THEN { --*stats*-- rmDirty _ rmDirty.SUCC; WITH rmMap[dirtyVictimRP] SELECT FROM rmE: reclaimable RMMapEntry => { victimP _ rmE.virtual; victim _ [realPage: dirtyVictimRP, body: dirty[vmPage: victimP]]; SetVMMap[victimP, [ state: PrincOpsUtils.PageStateFromFlags[PrincOps.flagsVacant], body: out[ checkedOut: FALSE, readOnly: GetVMMap[victimP].state.flags.readonly, dataState: dirtyVictimDataState]] ]; }; ENDCASE => Crash[]; -- dirtyVictimRP improperly set EXIT } ELSE Crash[]; -- all memory pinned or in transit ENDCASE => Crash[]; -- frame fault and no unpinned clean memory WITH rmMap[current] SELECT FROM rmE: free RMMapEntry => Crash[]; -- the free list is supposed to be empty rmE: reclaimable RMMapEntry => { victimE: VMMapEntry; <> PrincOpsUtils.DisableInterrupts[]; victimE _ GetVMMap[victimP _ rmE.virtual]; <> WITH vE: victimE SELECT InOut[victimE] FROM out => NULL; in => { vRefed: BOOL = vE.state.flags.referenced; vDirty: BOOL = vE.state.flags.dirty OR rmE.needsBackingStoreWrite; SELECT TRUE FROM vE.real ~= current => Crash[]; vRefed AND firstPass => { <> AgeInternal[victimP, vE]; IF ~vDirty THEN secondPassWorthWhile _ TRUE; }; vDirty => <> SELECT dirtyVictimState FROM none => { dirtyVictimState _ IF vRefed THEN referenced ELSE unreferenced; dirtyVictimRP _ current; dirtyVictimDataState _ IF vE.state.flags.dirty THEN changed ELSE rmE.dataState; }; unreferenced => NULL; referenced => IF ~vRefed THEN { dirtyVictimState _ unreferenced; dirtyVictimRP _ current; dirtyVictimDataState _ IF vE.state.flags.dirty THEN changed ELSE rmE.dataState; }; ENDCASE; ENDCASE => { <> victim _ [realPage: current, body: clean[]]; SetVMMap[victimP, [state: PrincOpsUtils.PageStateFromFlags[PrincOps.flagsVacant], body: out[ checkedOut: FALSE, readOnly: vE.state.flags.readonly, dataState: rmE.dataState]] ]; PrincOpsUtils.EnableInterrupts[]; --*stats*-- IF firstPass THEN rmOldClean _ rmOldClean.SUCC ELSE rmNewClean _ rmNewClean.SUCC; EXIT }; }; ENDCASE; PrincOpsUtils.EnableInterrupts[]; }; rmE: pinned RMMapEntry => NULL; ENDCASE; ENDLOOP; allocationRover _ current; -- advance round-robin pointer }; rmMap[victim.realPage] _ IF pin THEN RMMapEntry[dataState: tVM.dataState, needsBackingStoreWrite: FALSE, body: pinned[pinCount: 1]] ELSE RMMapEntry[dataState: tVM.dataState, needsBackingStoreWrite: FALSE, body: reclaimable[virtual: vmPage]]; --*stats*-- rmReclamations _ rmReclamations.SUCC; }; in => Crash[]; -- already has real memory ENDCASE; END; ENDLOOP; }; AgeInternal: PROC [vmPage: PageNumber, vmE: in VMMapEntry] = INLINE { <> IF vmE.state.flags.readonly AND vmE.state.flags.dirty THEN { rmMap[vmE.real].needsBackingStoreWrite _ TRUE; vmE.state.flags.dirty _ FALSE; rmMap[vmE.real].dataState _ changed; }; vmE.state.flags.referenced _ FALSE; SetVMMap[vmPage, vmE]; }; GetCheckedInVMMap: INTERNAL PROC [vmPage: PageNumber] RETURNS [vmEntry: VMMapEntry] = 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; --*stats*-- IF firstTime THEN {checkoutConflicts _ checkoutConflicts.SUCC; firstTime _ FALSE}; WAIT checkIn; ENDLOOP; }; <<>> <> <<>> InitializeTables[]; <> [] _ InitializeAllocateRealMemoryInternal[]; <<>> END.