-- File: VMCacheOps.mesa
-- Last edited by Wobber: 2-Nov-82 10:30:47
-- Last edited by Levin: 30-Apr-81 14:27:42
DIRECTORY
Inline USING [BITXOR],
VMDefs USING [
CantReadBackingStore, CantWriteBackingStore, Page, PageAddress, Start],
VMPrivate USING [
AcquireCache, AcquirePage, AddressToMDSPage, AllocateCacheIndex, CacheIndex,
FileHandle, FileObject, FinalizeVMCacheMgr, HandleTable, InitializeVMCacheMgr,
MDSPageNumber, MDSPageToAddress, nilCacheIndex, PageHandle, ReleaseCache,
ReleasePage, ValidateFile, ValidatePageNumber, WaitUntilStable],
VMStorage USING [longTerm];
VMCacheOps: PROGRAM
IMPORTS Inline, VMDefs, VMPrivate, VMStorage EXPORTS VMDefs, VMPrivate =
BEGIN OPEN VMDefs, VMPrivate;
-- Types and Related Constants --
PageMap: TYPE = PACKED ARRAY MDSPageNumber OF CacheIndex;
HashIndex: TYPE = [0..HashBins);
HashBins: CARDINAL = 97;
-- Global Variables --
handles: POINTER TO HandleTable;
pageMap: PageMap;
hashTable: PACKED ARRAY HashIndex OF CacheIndex;
-- Miscellaneous Declarations --
AttemptToReusePageMapSlot: ERROR = CODE;
BadAddress: ERROR = CODE;
IllegalCacheIndex: ERROR = CODE;
IllegalPageState: ERROR = CODE;
InconsistentHandleMap: ERROR = CODE;
InconsistentHashTable: ERROR = CODE;
InconsistentPageMap: ERROR = CODE;
-- Procedures and Signals Exported to VMDefs --
FileObject: PUBLIC TYPE = VMPrivate.FileObject;
-- Page Object Allocation --
AllocatePage: PUBLIC PROCEDURE RETURNS [Page] =
BEGIN
index: CacheIndex = AllocateCacheIndex[];
page: PageHandle = IndexToHandle[index];
page.useCount ← 1;
page.file ← NIL;
page.age ← new;
page.dirty ← FALSE;
page.state ← stable;
AcquireCache[];
EnterInPageTable[page.buffer, index];
ReleaseCache[];
RETURN[MDSPageToAddress[page.buffer]]
END;
Release: PUBLIC PROCEDURE [page: Page] =
BEGIN
p: PageHandle;
AcquireCache[];
p ← AddressToHandle[page];
IF p.useCount = 0 THEN ERROR IllegalPageState;
IF (p.useCount ← p.useCount - 1) = 0 AND p.file = NIL THEN
RemoveFromPageTable[p];
ReleaseCache[];
END;
Deactivate: PUBLIC PROCEDURE [page: Page] =
BEGIN
p: PageHandle;
AcquireCache[];
p ← AddressToHandle[page];
SELECT p.useCount FROM
0 => ERROR IllegalPageState;
1 =>
IF ~p.dirty THEN RemovePageFromTables[p]
ELSE {p.age ← old; ReleaseCache[]; VMDefs.Start[page]; AcquireCache[]};
ENDCASE;
p.useCount ← p.useCount - 1;
ReleaseCache[];
END;
-- Core/Disk Mapping --
UsePage: PUBLIC PROCEDURE [addr: PageAddress] RETURNS [Page] =
BEGIN
oldindex, newindex: CacheIndex;
page: PageHandle;
ValidateAddress[addr];
AcquireCache[];
IF (oldindex ← LookupInHashTable[addr]) = nilCacheIndex THEN
BEGIN
ReleaseCache[];
page ← IndexToHandle[newindex ← AllocateCacheIndex[]];
page.file ← addr.file;
page.page ← addr.page;
AcquireCache[];
page.state ← stable;
IF (oldindex ← LookupInHashTable[addr]) = nilCacheIndex THEN {
EnterInPageTable[page.buffer, newindex]; EnterInHashTable[page]}
ELSE
-- someone slipped the requested page in ahead us; abandon our page
{page.file ← NIL; page ← IndexToHandle[oldindex]};
END
ELSE page ← IndexToHandle[oldindex];
AcquirePage[page];
page.dirty ← FALSE;
page.useCount ← page.useCount + 1;
MarkPageUsableAndRelease[page];
RETURN[MDSPageToAddress[page.buffer]]
END;
RemapPage: PUBLIC PROCEDURE [page: Page, addr: PageAddress] =
BEGIN
p: PageHandle;
index: CacheIndex;
ValidateAddress[addr];
AcquireCache[];
p ← AddressToHandle[page];
AcquirePage[p];
IF p.useCount ~= 1 THEN ERROR IllegalPageState;
index ← LookupInHashTable[addr];
IF index ~= nilCacheIndex THEN
BEGIN -- previous contents of 'addr' is in cache
oldPage: PageHandle = IndexToHandle[index];
IF oldPage = p THEN {MarkPageUsableAndRelease[p]; RETURN};
oldPage.useCount ← oldPage.useCount + 1;
ReleaseCache[];
IF WaitUntilStable[
oldPage, writing !
CantReadBackingStore, CantWriteBackingStore => CONTINUE] = unstable THEN
ReleasePage[oldPage];
AcquireCache[];
-- throw away old contents, even if dirty
IF (oldPage.useCount ← oldPage.useCount - 1) = 0 THEN {
IF ~oldPage.beingTaken THEN RemovePageFromTables[oldPage]}
ELSE ERROR BadAddress;
END;
RemoveFromHashTable[p];
p.file ← addr.file;
p.page ← addr.page;
p.dirty ← TRUE;
EnterInHashTable[p];
MarkPageUsableAndRelease[p];
END;
UnmapPage: PUBLIC PROCEDURE [page: Page] =
BEGIN
p: PageHandle;
AcquireCache[];
p ← AddressToHandle[page];
AcquirePage[p];
IF p.useCount ~= 1 THEN ERROR IllegalPageState;
RemoveFromHashTable[p];
p.file ← NIL;
MarkPageUsableAndRelease[p];
END;
PageToPageAddress: PUBLIC PROCEDURE [page: Page] RETURNS [PageAddress] =
BEGIN
p: PageHandle;
addr: PageAddress;
AcquireCache[];
p ← AddressToHandle[page];
AcquirePage[p];
IF p.useCount = 0 OR p.file = NIL THEN ERROR IllegalPageState;
addr ← [p.file, p.page];
ReleasePage[p];
ReleaseCache[];
RETURN[addr]
END;
-- Procedures and Signals Exported to VMPrivate --
-- Start/Stop --
InitializeVMCache: PUBLIC PROCEDURE [min, max: CacheIndex] =
BEGIN
handles ← VMStorage.longTerm.NEW[HandleTable [max]];
FOR index: CacheIndex IN [0..max) DO handles[index] ← NIL; ENDLOOP;
FOR vmpage: MDSPageNumber IN MDSPageNumber DO
pageMap[vmpage] ← nilCacheIndex; ENDLOOP;
FOR bin: HashIndex IN HashIndex DO hashTable[bin] ← nilCacheIndex; ENDLOOP;
InitializeVMCacheMgr[handles, min, max];
END;
FinalizeVMCache: PUBLIC PROCEDURE = {
FinalizeVMCacheMgr[]; VMStorage.longTerm.FREE[@handles]};
-- Handle Table Management --
IndexToHandle: PUBLIC PROCEDURE [index: CacheIndex]
RETURNS [handle: PageHandle] =
BEGIN
IF index = nilCacheIndex THEN ERROR IllegalCacheIndex;
IF (handle ← handles[index]) = NIL THEN ERROR InconsistentHandleMap;
RETURN
END;
AddressToHandle: PUBLIC PROCEDURE [address: Page] RETURNS [PageHandle] = {
RETURN[IndexToHandle[AddressToIndex[address]]]};
HandleToAddress: PUBLIC PROCEDURE [page: PageHandle] RETURNS [Page] = {
RETURN[MDSPageToAddress[page.buffer]]};
-- Hash Table Management --
LookupInHashTable: PUBLIC PROCEDURE [addr: PageAddress]
RETURNS [index: CacheIndex] =
BEGIN
index ← hashTable[Hash[addr]];
UNTIL index = nilCacheIndex DO
page: PageHandle ← IndexToHandle[index];
IF page.file = addr.file AND page.page = addr.page THEN RETURN;
index ← page.hashLink;
ENDLOOP;
RETURN
END;
EnterInHashTable: PUBLIC PROCEDURE [page: PageHandle] =
BEGIN
bin: HashIndex = Hash[PageAddress[page.file, page.page]];
page.hashLink ← hashTable[bin];
hashTable[bin] ← pageMap[page.buffer];
IncrementFileUseCount[page.file];
END;
-- Page Table Management --
EnterInPageTable: PUBLIC PROCEDURE [page: MDSPageNumber, index: CacheIndex] =
BEGIN
IF pageMap[page] ~= nilCacheIndex THEN ERROR AttemptToReusePageMapSlot;
pageMap[page] ← index;
END;
-- Miscellaneous Procedures --
RemovePageFromTables: PUBLIC PROCEDURE [page: PageHandle] =
BEGIN
RemoveFromHashTable[page];
RemoveFromPageTable[page];
page.file ← NIL;
END;
-- Internal Procedures --
-- Hash Table Management --
RemoveFromHashTable: PROCEDURE [page: PageHandle] =
-- delinks the argument page from the hash table.
BEGIN
ci: CacheIndex = pageMap[page.buffer];
bin: HashIndex;
IF page.file = NIL THEN RETURN;
bin ← Hash[PageAddress[page.file, page.page]];
IF hashTable[bin] = nilCacheIndex THEN GO TO badTable;
IF ci = hashTable[bin] THEN hashTable[bin] ← page.hashLink
ELSE
BEGIN
prev: PageHandle ← IndexToHandle[hashTable[bin]];
UNTIL prev.hashLink = nilCacheIndex DO
IF prev.hashLink = ci THEN {prev.hashLink ← page.hashLink; EXIT};
prev ← IndexToHandle[prev.hashLink];
REPEAT FINISHED => GO TO badTable;
ENDLOOP;
END;
DecrementFileUseCount[page.file];
EXITS badTable => ERROR InconsistentHashTable;
END;
Hash: PROCEDURE [addr: PageAddress] RETURNS [HashIndex] =
-- produces HashIndex for 'addr' into hashTable.
BEGIN
Bytes: TYPE = MACHINE DEPENDENT RECORD [high: [0..255], low: [0..255]];
XORBytes: PROCEDURE [word: UNSPECIFIED] RETURNS [UNSPECIFIED] = INLINE
-- XORs the two bytes of 'word'.
BEGIN OPEN w: LOOPHOLE[word, Bytes];
RETURN[Inline.BITXOR[w.low, w.high]];
END;
RETURN[XORBytes[Inline.BITXOR[addr.file, addr.page]] MOD HashBins]
END;
-- Page Table Management --
RemoveFromPageTable: PROCEDURE [page: PageHandle] =
-- destroys the correspondance between (MDS) page 'page.buffer' and the page object.
BEGIN
IF IndexToHandle[pageMap[page.buffer]] ~= page THEN ERROR InconsistentPageMap;
pageMap[page.buffer] ← nilCacheIndex;
END;
-- Handle Table Management --
AddressToIndex: PROCEDURE [address: Page] RETURNS [CacheIndex] = INLINE
-- maps an (MDS) address to the CacheIndex for the corresponding page.
{RETURN[pageMap[AddressToMDSPage[address]]]};
-- Miscellaneous Procedures --
ValidateAddress: PROCEDURE [addr: PageAddress] =
BEGIN ValidateFile[addr.file]; ValidatePageNumber[addr.page]; END;
MarkPageUsableAndRelease: PROCEDURE [page: PageHandle] =
BEGIN
page.age ← new;
page.errorStatus ← ok;
ReleasePage[page];
ReleaseCache[];
END;
IncrementFileUseCount: PROCEDURE [file: FileHandle] = INLINE {
file.useCount ← file.useCount + 1};
DecrementFileUseCount: PROCEDURE [file: FileHandle] = INLINE {
file.useCount ← file.useCount - 1};
END.