-- Copyright (C) 1981, 1982, 1984, 1985 by Xerox Corporation. All rights reserved.
-- VMCacheOps.mesa, HGM, 17-Sep-85 2:20:57
-- Last edited by Wobber: 2-Nov-82 10:30:47
-- Last edited by Levin: 30-Apr-81 14:27:42
DIRECTORY
Heap USING [systemZone],
Inline USING [BITXOR, HighByte, LowByte, LowHalf],
VMDefs USING [
CantReadBackingStore, CantWriteBackingStore, Page, PageAddress, PageNumber, Start],
VMPrivate USING [
AcquireCache, AcquirePage, AddressToPageIndex, AllocateCacheIndex, CacheIndex,
FileHandle, FileObject, FinalizeVMCacheMgr, HandleTable, InitializeVMCacheMgr,
PageIndex, nilCacheIndex, PageHandle, ReleaseCache,
ReleasePage, ValidateFile, ValidatePageNumber, WaitUntilStable];
VMCacheOps: PROGRAM
IMPORTS Heap, Inline, VMDefs, VMPrivate
EXPORTS VMDefs, VMPrivate =
BEGIN OPEN VMDefs, VMPrivate;
-- Types and Related Constants --
handles: LONG POINTER TO HandleTable;
hashTable: PACKED ARRAY HashIndex OF CacheIndex;
PageMap: TYPE = PACKED ARRAY PageIndex OF CacheIndex;
pageMap: PageMap;
hashBins: CARDINAL = 97;
HashIndex: TYPE = [0..hashBins);
-- 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, index];
ReleaseCache[];
RETURN[page.pointer]
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, 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[page.pointer]
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, first: LONG POINTER] =
BEGIN
handles ← Heap.systemZone.NEW[HandleTable [max]];
FOR index: CacheIndex IN [0..max) DO handles[index] ← NIL; ENDLOOP;
FOR vmpage: PageIndex IN PageIndex DO
pageMap[vmpage] ← nilCacheIndex; ENDLOOP;
FOR bin: HashIndex IN HashIndex DO hashTable[bin] ← nilCacheIndex; ENDLOOP;
InitializeVMCacheMgr[handles, min, max, first];
END;
FinalizeVMCache: PUBLIC PROCEDURE = {
FinalizeVMCacheMgr[]; Heap.systemZone.FREE[@handles]};
-- Handle Table Management --
AddressToHandle: PUBLIC PROCEDURE [address: VMDefs.Page] RETURNS [PageHandle] =
BEGIN
RETURN[IndexToHandle[pageMap[AddressToPageIndex[address]]]];
END;
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;
-- 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.index];
IncrementFileUseCount[page.file];
END;
-- Page Table Management --
BogusPageIndex: ERROR = CODE;
EnterInPageTable: PUBLIC PROCEDURE [page: PageHandle, index: CacheIndex] =
BEGIN
IF index > PageIndex.LAST THEN ERROR BogusPageIndex;
IF pageMap[page.index] # nilCacheIndex THEN ERROR AttemptToReusePageMapSlot;
pageMap[page.index] ← 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.index];
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
XORBytes: PROCEDURE [word: UNSPECIFIED] RETURNS [UNSPECIFIED] = INLINE
-- XORs the two bytes of 'word'.
BEGIN
RETURN[Inline.BITXOR[Inline.HighByte[word], Inline.LowByte[word]]];
END;
RETURN[XORBytes[Inline.BITXOR[Inline.LowHalf[addr.file], addr.page]] MOD hashBins]
END;
-- Page Table Management --
RemoveFromPageTable: PROCEDURE [page: PageHandle] =
-- destroys the correspondance between page 'page.pointer' and the page object.
BEGIN
IF IndexToHandle[pageMap[page.index]] # page THEN ERROR InconsistentPageMap;
pageMap[page.index] ← nilCacheIndex;
END;
-- 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.