DIRECTORY BootFileChanges USING [PageStateFromFlags, PageValue], 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, RealPageNumber, RMEntryPointer, rmMap, RMMapEntry, SetVMMap, SwapInOutcome, Victim, VMMapEntry, vmStateLock], VMStatistics USING [ checkoutConflicts, pinnedPages, rmCleanPasses, trappedPages]; VMSwapImpl: MONITOR LOCKS VMInternal.vmStateLock IMPORTS BootFileChanges, 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 _ BootFileChanges.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: BootFileChanges.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: BootFileChanges.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: BootFileChanges.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: BootFileChanges.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}; IF firstTime THEN {checkoutConflicts _ checkoutConflicts.SUCC; firstTime _ FALSE}; WAIT checkIn; ENDLOOP; }; END. DVMSwapImpl.mesa Copyright c 1984 by Xerox Corporation. All rights reserved. Russ Atkinson, June 8, 1984 6:46:56 pm PDT Bob Hagmann, May 4, 1984 1:32:54 pm PDT Utilities for VM.SwapIn and VM.Clean This is a specialized procedure for VM.SwapIn. Note: the rmMap entry has now been updated for eventual association (by SwapInDone) with vmPage. Strictly speaking, we should disable interrupts, reread the map, clear the dirty bit, and set the map before enabling interrupts. This will avoid losing the referenced bit. However, since the page is being killed, the referenced bit isn't very interesting now anyway. This is a specialized procedure for VM.SwapIn. "bufferPage" should be a page whose VMMapEntry is "in" and whose real page matches the one returned for the corresponding "vmPage" by AllocateForSwapIn, above. In either case above, 'vmPage' has been checked back in, so... Now we make the swap buffer page vacant. This SetVMMap implicitly cleared the "checkedOut" bit, so... Restore victim's map entry, but pin the page (permanently), since it can't be written out. The only way anyone will discover this happened is by looking at the counter in VMStatistics. Check the original page back in. Make the swap buffer page vacant. This is a specialized procedure for VM.Clean. Interrupts must be disabled if the map entry says "present", so that the test for "dirty" and subsequent setting of "vacant" are atomic. Interrupts need not be disabled if the map entry says "vacant", but it doesn't hurt, since we spend minimal time in that state and it simplifies the code. This is a specialized procedure for VM.Clean. "bufferPage" should be a page whose VMMapEntry is "in" and whose real page matches the one returned for the corresponding "vmPage" by ConsiderCleaning, above. The above SetVMMap implicitly cleared the "checkedOut" bit, so we must wake up any potential waiters. Aging Interrupts must be disabled if the map entry says present, so that the resetting of "referenced" is atomic. Interrupts need not be disabled if the map entry says "vacant", but it doesn't hurt, since we spend minimal time in that state and it simplifies the code. This is a specialized procedure for VM.Age. Laundry process support We could probably get away without claiming the monitor lock. This procedure constructs an interval surrounding it whose 'dirty' and 'referenced' states are the same as 'vP'. It implicitly uses 'desired' and 'firstPass' and updates 'cleaningRover'. We have completed a scan of real memory. INTERNAL procedures A note in VMInternal.VMMapEntry explains the following non-intuitive test. *stats*-- Ê Ä˜šœ™Jšœ Ïmœ1™Jšœ`™`J˜—šœ˜Jšœ'˜'J˜šžœžœ˜Jšœ™Jšžœžœžœžœ˜LJšœ5žœ˜;J˜Jšœ˜J˜—šžœžœ˜ šžœ žœž˜J˜šœ˜Jšœ+˜+JšÏc œžœ˜+J˜—šœ ˜ Jšžœžœ ˜BJšžœ ˜ —Jšžœ˜—J˜—J˜—Jšžœ˜—J˜—J˜š Ÿ œžœžœžœ*žœ˜PJšœÏ™ÏJ˜'šžœžœž˜,šœ˜Jšœ/˜/šžœžœž˜3˜Jšœ&˜&šžœžœ˜š  ˜ šžœ ž˜Jšœ˜Jšœ$žœ˜)Jšœžœ˜Jšžœ˜——šœ.˜.Jšœ žœžœ˜:—Jšœ˜J˜—šžœ˜Jšžœžœ ˜#Jšœ˜Jšœžœ˜J˜J˜—Jšœ>™>Jšž œ ˜J™(Jšœžœ˜&Jšœ˜Jšœ˜J˜—J˜Jšžœ˜—J˜—Jšœ˜Jšžœ˜—J˜J˜—šŸœžœžœžœ)˜OJ˜'šžœžœž˜,šœ˜šœ˜šœ*˜*Jšœ žœžœ˜:—Jšœ˜Jšœ˜—Jšœ<™žœ˜GJ˜'šžœžœž˜,šœ˜šžœ žœ˜Jšœ¹™¹˜Jšœ?˜?Jšœ˜—Jšœ.˜.Jšžœžœ ˜#šœ˜Jšœ2žœ˜7Jšœ5˜5—J˜%Jš  œžœ˜+Jš  œžœ˜-Jšœ ™ Jšœžœ˜Jšœ˜Jšž œ ˜J˜—Jšœ!™!Jšœ žœ˜&Jšœ˜Jšœ˜J˜—Jšœ˜Jšžœ˜—J˜—J˜šŸœžœ%žœ˜MJšžœ2˜9J™-Jšœ¤™¤J˜J˜"J˜šžœžœž˜,Jšœžœžœžœ ˜Jšœ˜Jšœ.˜.šžœ žœž˜Jšœ˜šœ˜Jšœžœžœ˜Bšžœžœ žœ˜ ˜Jšœ@˜@šœ ˜ Jšœ žœ˜Jšœ#˜#Jšœ žœžœ žœ˜CJšœ˜——Jšœ. ˜EJ˜J˜—šœ ˜ šžœžœž˜Jšœ˜Jšœ!˜!Jšžœ˜——J˜—Jšœ˜Jšžœ˜—J˜—Jšžœ˜—J˜!J˜—J˜š Ÿ œžœžœžœ*žœ˜OJšœÍ™ÍJ˜'šžœžœž˜,šœ˜Jšœ/˜/šžœžœž˜3šœ˜Jšœ*˜*šžœžœž˜šœ˜šœ˜šœ*˜*Jšœ žœ˜D—Jšœ˜J˜—Jšžœžœ ˜&šžœžœ˜Jšœ  ˜?Jšœžœ˜#J˜—šžœ˜šœ ˜ Jšœ2žœ˜7Jšœ5˜5—Jš  œžœ˜+Jš  œžœ˜-Jšœ˜—Jšœ˜Jšœe™eJšž œ ˜J˜—J˜Jšžœ˜—J˜—Jšœ˜Jšžœ˜—Jšœžœ˜Jšœ˜Jšœ˜Jšœ˜—Jšœ˜Jšžœ˜—J˜—J˜J˜—™J˜šŸœžœžœ˜OJšœ‡™‡J™+J˜Jšœ"˜"J˜šžœžœž˜,Jšœžœžœ˜;Jšœ˜Jšžœ˜—Jšœ!˜!J˜—J™—™J˜šŸœžœžœžœ˜)JšœB˜BJšžœžœS˜sJšœ=™=Jšœ žœžœ˜šŸœžœžœžœ˜MJšœmžœM™»Jš œžœžœžœžœ˜IJ˜Jšœ˜šžœž˜#Jšœ#žœ˜(Jšœ'˜'šžœžœž˜,˜šžœžœž˜ šœ˜šžœžœ ˜.Jšœžœž˜9Jš œžœžœžœžœ˜Q——Jšœžœ˜Jšœ ˜ Jšžœ˜——Jšœžœ˜ Jšžœ˜—Jšœ˜Jšžœ˜—šžœžœ žœž˜?Jšœžœ˜Jšœ'˜'šžœžœž˜,˜šžœžœž˜ šœ˜šžœžœ ˜.Jšœžœž˜9Jš œžœžœžœžœ˜Q——Jšœžœ˜Jšœ ˜ Jšžœ˜——Jšœžœ˜ Jšžœ˜—Jšœ ˜ Jšžœ˜—Jšœ%žœ˜*J˜—Jšœ˜Jšœ(˜(Jšœžœžœ˜šž˜šžœžœžœ˜(Jšœ˜Jš  œžœ˜/J˜—Jšžœžœ˜šžœžœž˜šœ˜Jšœ(™(šžœ žœžœžœ˜=Jšœ žœ˜Jšœ˜Jšœ˜—Jšžœžœ˜ —šœžœž˜4Jšœ˜Jšžœ˜J˜—Jšžœ˜—šžœžœž˜šœ ˜ Jšœ˜Jšœ#˜#šžœžœž˜,˜Jšœžœ˜)Jšœžœžœ˜BJšžœžœ ˜$šžœž˜ Jšžœžœ žœž˜3Jšžœ<žœ˜E—Jšžœžœ˜"J˜—Jšœžœ ˜*Jšžœ˜—J˜—Jšžœžœ˜—Jšžœ˜—Jšœ˜Jšœ˜Jšœ˜J˜J˜——J™™J˜š Ÿœžœžœ žœžœ˜MJšžœ žœžœžœ˜>Jšœ žœžœ˜šž˜Jšœ˜šžœžœž˜,Jšœžœ˜ šœ˜JšœJ™JJšžœžœžœžœ˜5—Jšžœ˜—Jšžœ žœ žœžœ˜(šœ ™ Jšžœ žœ(žœžœ˜R—Jšžœ ˜ Jšžœ˜—Jšœ˜J˜——Jšžœ˜J˜J˜J˜J˜—…—'À?È