<> <> <> <> <> DIRECTORY PrincOps USING [flagsVacant, flagsClean, Port], PrincOpsUtils USING [DisableInterrupts, EnableInterrupts, GetReturnLink, SetReturnLink], VMEmergency USING [EmergencyList], VMInternal USING [AgeInternal, Crash, DataState, freeList, freePages, GetVMMap, InOut, lastRealPage, PageNumber, PageStateFromFlags, RealPageNumber, rmMap, RMMapEntry, SetVMMap, Victim, VMMapEntry, vmStateLock], VMStatistics USING [pinnedPages]; VMReplacementImpl: MONITOR LOCKS VMInternal.vmStateLock IMPORTS PrincOpsUtils, VMInternal, VMStatistics EXPORTS VMEmergency, VMInternal, VMStatistics SHARES VMInternal = BEGIN OPEN VMInternal; <> <<>> <<>> <> <<>> rmReclamations: PUBLIC INT _ 0; rmFreeList, rmOldClean, rmNewClean, rmDirty: PUBLIC INT _ 0; rmAllocPasses: PUBLIC INT _ 0; <> <<>> <> allocationRover: RealPageNumber _ RealPageNumber.FIRST; <> <<>> AllocateRealMemoryInternal: PUBLIC PROC [ vmPage: PageNumber, dirtyVictimOK: BOOL _ TRUE, pin: BOOL _ FALSE] RETURNS [victim: Victim] _ LOOPHOLE[@AwaitAllocateRealMemoryInternal]; <> <> <<>> 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: VMInternal.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 emergencyList = NIL => Crash[]; <> ENDCASE => { <> FOR i: NAT IN [0..emergencyList.max) DO vp: PageNumber = emergencyList.pages[i]; IF vp # 0 THEN { entry: VMMapEntry _ GetVMMap[vp]; WITH tE: entry SELECT InOut[entry] FROM in => { <> current _ tE.real; IF rmMap[current].rmState = pinned THEN VMStatistics.pinnedPages _ VMStatistics.pinnedPages - 1; rmMap[current] _ [ dataState: undefined, needsBackingStoreWrite: FALSE, body: reclaimable[virtual: vp]]; tE.state.flags _ PrincOps.flagsClean; SetVMMap[vp, entry]; GO TO foundOne; }; ENDCASE; }; ENDLOOP; Crash[]; EXITS foundOne => { emergencyList.change _ emergencyList.change - 1; }; }; 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 AND ~vDirty => { <> AgeInternal[victimP, vE]; secondPassWorthWhile _ TRUE; }; vDirty => { IF vRefed THEN AgeInternal[victimP, vE]; <> 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: VMInternal.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; }; <> emergencyList: PUBLIC VMEmergency.EmergencyList _ NIL; <> <<>> [] _ InitializeAllocateRealMemoryInternal[]; <<>> END.