-- Copyright (C) 1981, 1982, 1984, 1985 by Xerox Corporation. All rights reserved. -- VMCacheMgr.mesa, HGM, 17-Sep-85 1:35:34 -- Last edited by Wobber: 2-Nov-82 10:19:21 -- Last edited by Gobbel: 18-May-81 17:27:32 -- Last edited by Levin: 30-Apr-81 13:04:02 DIRECTORY Heap USING [systemZone], Inline USING [LowHalf], Process USING [MsecToTicks, Yield], VMDefs USING [CantReadBackingStore, CantWriteBackingStore, Error, Page, pageSize], VMPrivate USING [ AcquirePage, CacheIndex, FileHandle, FileObject, HandleTable, IndexToHandle, nilCacheIndex, Object, PageHandle, PageIndex, PageObject, RemovePageFromTables, WritePageToFS], VMStorage USING [AllocatePage, FreePage]; VMCacheMgr: MONITOR IMPORTS Heap, Inline, Process, VMDefs, VMPrivate, VMStorage EXPORTS VMDefs, VMPrivate = 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 -- cacheState: CacheState; cacheStable: CONDITION; minCachePages, maxCachePages: CacheIndex; handles: LONG 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 -- Not Used, 15-Sep-85 16:26:55, HGM 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]; VMStorage.FreePage[page.pointer, page.index]; page.pointer ¬ NIL; 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: LONG POINTER TO HandleTable, min, max: CacheIndex, first: LONG POINTER] = BEGIN handles ¬ h; minCachePages ¬ min; maxCachePages ¬ max; firstBuffer ¬ first; rover ¬ FIRST[CacheIndex]; hopeForStateChange.timeout ¬ Process.MsecToTicks[100]; flushDisabled ¬ FALSE; buffersInUse ¬ 0; cacheState ¬ stable; cacheStable.timeout ¬ 0; 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.pointer # NIL THEN VMStorage.FreePage[page.pointer, page.index]; Heap.systemZone.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 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 AND unmap THEN RemovePageFromTables[page]; 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; Process.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.pointer = NIL)) 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 ¬ Heap.systemZone.NEW[ PageObject ¬ Object[ page[ state: unstable, age:, dirty: FALSE, errorStatus:, pointer: NIL, index: 0, pageStable: [timeout: 0], file: NIL, beingTaken: FALSE, page:, hashLink:, recordNextVda:, useCount: 0]]]; flushDisabled ¬ FALSE; END; BogusPageNumber: ERROR = CODE; EnsureBufferExists: PROCEDURE [index: CacheIndex] = -- ensures that the page in cache slot 'index' has an associated buffer. BEGIN page: PageHandle ¬ IndexToHandle[index]; IF page.pointer = NIL THEN { [page.pointer, page.index] ¬ VMStorage.AllocatePage[]; buffersInUse ¬ buffersInUse + 1; }; lastIndex ¬ MAX[lastIndex, page.index]; END; firstBuffer: LONG POINTER ¬ NIL; lastIndex: PageIndex ¬ 0; BogusAddress: ERROR = CODE; AddressToPageIndex: PUBLIC PROCEDURE [address: VMDefs.Page] RETURNS [PageIndex] = BEGIN offset: LONG CARDINAL = LOOPHOLE[address - firstBuffer]; pageNumber: LONG CARDINAL = offset/VMDefs.pageSize; index: PageIndex ¬ Inline.LowHalf[pageNumber]; IF pageNumber > lastIndex THEN ERROR BogusAddress; RETURN[index]; END; END.