-- File: VMCacheMgr.mesa -- Last edited by Levin: 12-Apr-83 11:28:46 DIRECTORY LogDefs USING [DisplayNumber], ProcessDefs USING [MsecToTicks, Yield], VMDefs USING [CantReadBackingStore, CantWriteBackingStore, Error], VMPrivate USING [ AcquirePage, AddressToMDSPage, CacheIndex, FileHandle, FileObject, HandleTable, IndexToHandle, loggingEnabled, MDSPageToAddress, nilCacheIndex, nilMDSPage, Object, PageHandle, PageObject, RemovePageFromTables, WriteEnable, WritePageToFS, WriteProtect], VMSpecial USING [], VMStorage USING [AllocatePage, FreePage, longTerm]; VMCacheMgr: MONITOR LOCKS lock^ IMPORTS LogDefs, ProcessDefs, VMDefs, VMPrivate, VMStorage EXPORTS VMDefs, VMPrivate, VMSpecial = BEGIN OPEN VMPrivate; -- The VMCache manager synchronizes access to the cache data structures. However, -- there is a subtlety involving the PruneCache procedure, which is invoked when -- storage is low. This procedure may be invoked at essentially arbitrary times and -- must be able to acquire the cache. To prevent deadlock, storage allocation -- requests generated by VMCacheOps must either be made outside the cache mutual -- exclusion or must temporarily disable the PruneCache. Examples occur in -- EnsureBufferExists, which calls AllocatePage, and FillCacheSlot, which calls -- the node-level allocator. -- Types and Related Constants -- CacheState: TYPE = {stable, unstable}; VictimClass: TYPE = { available, nil, cleanOver, dirtyOver, cleanUnder, dirtyUnder, none}; -- Global Variables -- lock: POINTER TO MONITORLOCK; LOCK: MONITORLOCK; cacheState: CacheState; cacheStable: CONDITION; minCachePages, maxCachePages: CacheIndex; handles: POINTER TO HandleTable; buffersInUse: CacheIndex; rover: CacheIndex; flushDisabled: BOOLEAN; -- Miscellaneous Declarations -- hopeForStateChange: CONDITION; PageInUse: ERROR = CODE; -- Types Exported to VMDefs -- FileObject: PUBLIC TYPE = VMPrivate.FileObject; -- Procedures and Signals Exported to VMSpecial -- PruneCache: PUBLIC PROCEDURE [pages: CARDINAL] RETURNS [BOOLEAN] = BEGIN StealOneBuffer: PROCEDURE = -- releases a single page buffer. BEGIN victim: CacheIndex; page: PageHandle; [victim, ] _ LiberateCacheSlot[bufferRequired: TRUE]; page _ IndexToHandle[victim]; WriteEnable[page.buffer]; VMStorage.FreePage[MDSPageToAddress[page.buffer]]; page.buffer _ nilMDSPage; buffersInUse _ buffersInUse - 1; END; IF flushDisabled OR buffersInUse <= minCachePages THEN RETURN[FALSE]; AcquireCache[]; IF pages = 1 THEN StealOneBuffer[] ELSE UNTIL buffersInUse <= minCachePages DO StealOneBuffer[]; ENDLOOP; ReleaseCache[]; RETURN[TRUE] END; -- Procedures and Signals Exported to VMPrivate -- InitializeVMCacheMgr: PUBLIC PROCEDURE [ h: POINTER TO HandleTable, min, max: CacheIndex] = BEGIN lock _ @LOCK; handles _ h; minCachePages _ min; maxCachePages _ max; rover _ FIRST[CacheIndex]; hopeForStateChange.timeout _ ProcessDefs.MsecToTicks[100]; flushDisabled _ FALSE; buffersInUse _ 0; cacheState _ stable; cacheStable.timeout _ 0; IF loggingEnabled THEN LogDefs.DisplayNumber["VM Cache Pages"L, [short[@buffersInUse]]]; END; FinalizeVMCacheMgr: PUBLIC PROCEDURE = BEGIN FOR index: CacheIndex IN [0..handles.nHandles) DO page: PageHandle _ handles[index]; IF page ~= NIL THEN BEGIN IF ~(page.useCount = 0 AND page.file = NIL) THEN ERROR PageInUse; IF page.buffer ~= nilMDSPage THEN BEGIN WriteEnable[page.buffer]; VMStorage.FreePage[MDSPageToAddress[page.buffer]]; END; VMStorage.longTerm.FREE[@page]; END; ENDLOOP; END; -- Cache Mutual Exclusion -- AcquireCache: PUBLIC ENTRY PROCEDURE = BEGIN UNTIL cacheState = stable DO WAIT cacheStable; ENDLOOP; cacheState _ unstable; END; ReleaseCache: PUBLIC ENTRY PROCEDURE = {cacheState _ stable; NOTIFY cacheStable}; -- Cache Management -- AllocateCacheIndex: PUBLIC PROCEDURE RETURNS [CacheIndex] = BEGIN page: PageHandle; victim: CacheIndex; vc: VictimClass; AcquireCache[]; [victim, vc] _ LiberateCacheSlot[bufferRequired: FALSE]; IF vc = nil THEN FillCacheSlot[victim]; page _ IndexToHandle[victim]; page.state _ unstable; ReleaseCache[]; EnsureBufferExists[victim]; RETURN[victim] END; EnumerateCachePagesInFile: PUBLIC PROCEDURE [ file: FileHandle, proc: PROCEDURE [page: PageHandle] RETURNS [found, unmap: BOOLEAN]] RETURNS [outcome: BOOLEAN] = BEGIN outcome _ FALSE; DO pagesBeingTaken: BOOLEAN _ FALSE; slot, last: CacheIndex; AcquireCache[]; slot _ last _ rover; DO page: PageHandle = handles[slot]; IF page ~= NIL AND page.file = file THEN IF page.beingTaken OR page.state = unstable THEN pagesBeingTaken _ TRUE ELSE BEGIN unmap: BOOLEAN; page.useCount _ page.useCount + 1; [found: outcome, unmap: unmap] _ proc[page ! UNWIND => ReleaseCache[]]; IF (page.useCount _ page.useCount - 1) = 0 THEN IF unmap THEN RemovePageFromTables[page] ELSE WriteProtect[page.buffer]; IF outcome THEN {ReleaseCache[]; RETURN}; END; slot _ IF slot = maxCachePages - 1 THEN FIRST[CacheIndex] ELSE slot + 1; IF slot = last THEN EXIT; ENDLOOP; ReleaseCache[]; IF ~pagesBeingTaken THEN EXIT; ProcessDefs.Yield[]; ENDLOOP; END; -- Internal Procedures -- -- Cache Management -- EnumerateCacheSlots: PROCEDURE [ proc: PROCEDURE [slot: CacheIndex] RETURNS [BOOLEAN]] RETURNS [BOOLEAN] = BEGIN slot: CacheIndex _ rover; last: CacheIndex _ rover; DO IF proc[slot] THEN RETURN[TRUE]; slot _ IF slot = maxCachePages - 1 THEN FIRST[CacheIndex] ELSE slot + 1; IF slot = last THEN RETURN[FALSE]; ENDLOOP; END; LiberateCacheSlot: PROCEDURE [bufferRequired: BOOLEAN] RETURNS [victim: CacheIndex, vc: VictimClass] = -- uses FindPotentialVictim to locate a candidate, writes the victim out to disk -- if dirty, and, if necessary, removes it from the mapping tables. BEGIN DO page: PageHandle; [victim, vc] _ FindPotentialVictim[bufferRequired]; SELECT vc FROM nil, available => EXIT; ENDCASE; page _ IndexToHandle[victim]; IF page.dirty THEN BEGIN OPEN VMDefs; AcquirePage[page]; page.beingTaken _ TRUE; -- ensure page doesn't disappear ReleaseCache[]; WritePageToFS[page: page, wait: TRUE ! CantReadBackingStore, CantWriteBackingStore, Error => CONTINUE]; AcquireCache[]; page.beingTaken _ FALSE; IF page.dirty OR page.useCount > 0 THEN LOOP; END; RemovePageFromTables[page]; EXIT; ENDLOOP; END; FindPotentialVictim: PROCEDURE [bufferRequired: BOOLEAN] RETURNS [victim: CacheIndex, vc: VictimClass] = -- INLINE -- -- locates a candidate victim slot in the cache, using the replacement algorithm. -- For normal replacement purposes, 'bufferRequired' should be FALSE. However, if -- the selected victim must have a buffer already allocated (e.g., as when returning -- buffer space to the Mesa runtime), then 'bufferRequired' should be TRUE. BEGIN CheckSlot: PROCEDURE [slot: CacheIndex] RETURNS [stopLooking: BOOLEAN] = -- classifies and potentially selects as a possible victim the page in cache -- slot 'slot'. Returns TRUE when a "first-rate" victim has been found. BEGIN page: PageHandle = handles[slot]; -- don't use IndexToHandle, since NIL is OK. file: FileHandle; newvc: VictimClass; stopLooking _ FALSE; BEGIN -- inner block permits 'MightBeDone' to access 'page' and 'newvc' IF page = NIL THEN {newvc _ nil; GO TO MightBeDone}; IF page.useCount ~= 0 OR page.state = unstable OR page.beingTaken THEN RETURN; IF page.file = NIL THEN {newvc _ available; GO TO MightBeDone}; IF page.age = new THEN RETURN; file _ page.file; newvc _ IF page.dirty THEN IF file.useCount <= file.cachePages THEN dirtyUnder ELSE dirtyOver ELSE IF file.useCount <= file.cachePages THEN cleanUnder ELSE cleanOver; IF newvc < vc THEN {vc _ newvc; victim _ slot}; IF vc = cleanOver THEN stopLooking _ TRUE; EXITS MightBeDone => BEGIN -- newvc is either nil or available IF bufferRequired AND (newvc = nil OR (newvc = available AND page.buffer = nilMDSPage)) THEN RETURN; victim _ slot; vc _ newvc; stopLooking _ TRUE; END; END; END; AgeSlot: PROCEDURE [slot: CacheIndex] RETURNS [BOOLEAN] = -- marks the indicated cache slot 'old', if it is legitimate to do so. Note -- that we need not test for page.beingTaken, since such a page is already -- marked old. BEGIN page: PageHandle = handles[slot]; -- don't use IndexToHandle, since NIL is OK. IF page ~= NIL AND page.useCount = 0 AND page.file ~= NIL AND page.state = stable THEN page.age _ old; RETURN[FALSE] END; WaitForBetterTimes: ENTRY PROCEDURE = INLINE -- in desperation, we delay for a while. {WAIT hopeForStateChange}; DO victim _ nilCacheIndex; vc _ none; [] _ EnumerateCacheSlots[CheckSlot]; SELECT vc FROM available, nil => EXIT; none => -- no old, stealable pages are present in the cache BEGIN [] _ EnumerateCacheSlots[AgeSlot]; -- age everything [] _ EnumerateCacheSlots[CheckSlot]; IF vc ~= none THEN EXIT; -- things are very grim... ReleaseCache[]; WaitForBetterTimes[]; AcquireCache[]; END; ENDCASE => -- cleanOver, cleanUnder, dirtyOver, dirtyUnder BEGIN -- age all cache slots between 'rover' and 'victim', inclusive. -- Note: we expand EnumerateCacheSlots inline for efficiency. See notes -- on AgeSlot, above. slot: CacheIndex _ rover; DO page: PageHandle = handles[slot]; IF page ~= NIL AND page.useCount = 0 AND page.file ~= NIL AND page.state = stable THEN page.age _ old; IF slot = victim THEN EXIT; slot _ IF slot = maxCachePages - 1 THEN FIRST[CacheIndex] ELSE slot + 1; ENDLOOP; EXIT END; ENDLOOP; rover _ victim; END; FillCacheSlot: PROCEDURE [index: CacheIndex] = INLINE -- creates a page object and associated buffer, marks it 'available', and places -- it in cache slot 'index'. BEGIN page: PageHandle; flushDisabled _ TRUE; -- tough break, Mesa handles[index] _ page _ VMStorage.longTerm.NEW[PageObject _ Object[page[ state: unstable, age: , dirty: FALSE, errorStatus: , buffer: nilMDSPage, pageStable: [timeout: 0], file: NIL, beingTaken: FALSE, page: , hashLink: , recordNextVda: , useCount: 0]]]; flushDisabled _ FALSE; END; EnsureBufferExists: PROCEDURE [index: CacheIndex] = -- ensures that the page in cache slot 'index' has an associated buffer. BEGIN page: PageHandle _ IndexToHandle[index]; IF page.buffer = nilMDSPage THEN BEGIN page.buffer _ AddressToMDSPage[VMStorage.AllocatePage[]]; buffersInUse _ buffersInUse + 1; END ELSE WriteEnable[page.buffer]; END; END.