-- File: VMCacheMgr.mesa
-- Last edited by Levin: 12-Jul-82 15:27:57
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];
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.