-- 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.