BTreeVMImpl.mesa
Cache to support the Taft's IFS BTree
Created by M. D. Schroeder
Last Edited by: Taft, March 25, 1983 3:28 pm
Last Edited by: Schroeder, March 25, 1983 3:25 pm
DIRECTORY
BTree: TYPE USING [ PageStorage, PageNumber, PagePtr, ReferencePage, ReferenceType, ReleasePage, statePage, UpdateState ],
BTreeVM,
File: TYPE USING [ Capability, GetSize, PageCount, PageNumber, SetSize ],
-- Process: TYPE USING [ Detach ],
-- RTTypesBasic: TYPE USING [EstablishFinalization, FinalizationQueue, FQNext, NewFQ ],
Space: TYPE USING [ CopyIn, CopyOut, Create, Handle, LongPointer, Map, WindowOrigin, virtualMemory ],
System: TYPE USING [ GetClockPulses, Pulses ];
BTreeVMImpl: CEDAR MONITOR
LOCKS h USING h: Handle
IMPORTS File, --Process, RTTypesBasic,-- Space, System
EXPORTS BTreeVM
= BEGIN
CacheIndex: TYPE = [0 .. LAST[BTreeVM.CacheSize]];
noIndex: CacheIndex = LAST[CacheIndex];
Handle: TYPE = REF VMObject;
VMObject: PUBLIC TYPE = MONITORED RECORD [
fp: File.Capability,
filePages: File.PageCount,
base: File.PageNumber,
filePagesPerPage: BTreeVM.FilePagesPerPage,
updateStateOnDisk: BTree.UpdateState,
updateStateInCache: BTree.UpdateState,
longUpdate: BOOLEAN,
rover: CacheIndex,
cache: REF Cache,
hits, misses, reads, writes, cumChainLength: LONG CARDINAL ← 0,
cumReadWriteTime: System.Pulses ← [0],
hashTable: PACKED SEQUENCE count: CARDINAL OF CacheIndex
];
Cache: TYPE = RECORD [PACKED SEQUENCE count: CacheIndex OF CacheEntry];
CacheEntry: TYPE = RECORD [
pNum: BTree.PageNumber,
space: Space.Handle,
ptr: BTree.PagePtr,
referenceCount: [0..256),
hash: CacheIndex,
empty, recentlyUsed, dirty: BOOLEAN
];
Open:
PUBLIC
PROC [ file: File.Capability, filePagesPerPage: BTreeVM.FilePagesPerPage,
cacheSize: BTreeVM.CacheSize, base: File.PageNumber ]
RETURNS [ Handle ] =
BEGIN
h: Handle ← NEW[VMObject [2*cacheSize+1]];
h.fp ← file;
h.filePages ← 0; -- indicates that we don't know --
h.base ← base;
h.filePagesPerPage ← filePagesPerPage;
h.updateStateOnDisk ← endOfUpdate;
h.updateStateInCache ← endOfUpdate;
h.longUpdate ← FALSE;
h.rover ← 0;
h.cache ← NEW[Cache[cacheSize]];
FOR i: CacheIndex
IN [0 .. h.cache.count)
DO
h.cache[i].ptr ← NIL;
h.cache[i].empty ← TRUE;
ENDLOOP;
FOR c:
CARDINAL
IN [0..h.count)
DO
h.hashTable[c] ← noIndex;
ENDLOOP;
RETURN [h];
END;
ReferencePage:
PUBLIC BTree.ReferencePage =
PROC [storage: PageStorage, number: PageNumber, type: ReferenceType]
RETURNS [ptr: PagePtr]
BEGIN
InnerReference:
ENTRY
PROCEDURE [h: Handle] =
INLINE
BEGIN
hash: CARDINAL = HashIndex[h, number];
i: CacheIndex;
FOR i ← h.hashTable[hash], h.cache[i].hash
UNTIL i = noIndex
DO
h.cumChainLength ← h.cumChainLength+1;
IF h.cache[i].pNum = number THEN { h.hits ← h.hits+1; EXIT };
REPEAT
FINISHED =>
BEGIN
-- not found --
h.misses ← h.misses+1;
i ← GetEmptyCacheEntry[h];
h.cache[i].pNum ← number;
h.cache[i].empty ← FALSE;
IF type # new THEN LoadCachePage[h, i];
h.cache[i].hash ← h.hashTable[hash];
h.hashTable[hash] ← i;
END;
ENDLOOP;
h.cache[i].recentlyUsed ← TRUE;
h.cache[i].referenceCount ← h.cache[i].referenceCount + 1;
IF type # read THEN h.cache[i].dirty ← TRUE;
IF type = new THEN ExtendFile[h, number];
ptr ← h.cache[i].ptr;
END;
InnerReference[NARROW[storage]];
END;
PageNotInUse: ERROR = CODE;
ReleasePage:
PUBLIC BTree.ReleasePage =
PROC [storage: PageStorage, number: PageNumber, update: UpdateState]
BEGIN
InnerRelease:
ENTRY
PROCEDURE [h: Handle] =
INLINE
BEGIN
i: CacheIndex;
FOR i ← h.hashTable[HashIndex[h, number]], h.cache[i].hash
UNTIL i = noIndex
DO
IF h.cache[i].pNum = number THEN EXIT;
REPEAT FINISHED => ERROR PageNotInUse;
ENDLOOP;
IF h.cache[i].referenceCount = 0
THEN ERROR PageNotInUse
ELSE h.cache[i].referenceCount ← h.cache[i].referenceCount - 1;
IF update # unchanged
THEN
BEGIN
IF number = BTree.statePage
THEN
BEGIN
-- is the statePage; can be either startOfUpdate or endOfUpdate
h.updateStateInCache ← update;
IF NOT h.longUpdate
THEN
BEGIN
IF update = startOfUpdate
THEN StoreCachePage[h, i] -- only this page is dirty, so just write it
ELSE WriteDirtyPagesWithStatePageLast[h]; -- many pages possibly dirty
END
ELSE
BEGIN
-- write only to get startOfUpdate on the disk
IF h.updateStateOnDisk = endOfUpdate
THEN StoreCachePage[h, i];
END;
END
ELSE
BEGIN
-- is not the statePage; must be endOfUpdate
IF NOT h.longUpdate
Only page i is dirty
THEN StoreCachePage[h, i];
END;
END;
END;
InnerRelease[NARROW[storage]];
END;
StartLongUpdate:
PUBLIC
ENTRY
PROC [ h: Handle ] =
{ h.longUpdate ← TRUE };
EndLongUpdate:
PUBLIC
ENTRY
PROC [ h: Handle ] =
BEGIN
IF h.longUpdate
THEN
BEGIN
WriteDirtyPagesWithStatePageLast[h];
h.longUpdate ← FALSE;
END;
END;
GetStats:
PUBLIC
ENTRY
PROC [ h: Handle ]
RETURNS [hits, misses, reads, writes, cumChainLength:
LONG
CARDINAL, cumReadWriteTime: System.Pulses] =
BEGIN
RETURN [hits: h.hits, misses: h.misses, reads: h.reads, writes: h.writes, cumChainLength: h.cumChainLength, cumReadWriteTime: h.cumReadWriteTime];
END;
HashIndex: INTERNAL PROC [h: Handle, pNum: BTree.PageNumber]
RETURNS [CARDINAL] = INLINE { RETURN [pNum MOD h.count] };
WriteDirtyPagesWithStatePageLast:
INTERNAL
PROC [ h: Handle ] =
BEGIN
statePageIndex: CacheIndex ← noIndex;
FOR i: CacheIndex
IN [0 .. h.cache.count)
DO
IF NOT h.cache[i].empty AND h.cache[i].dirty
THEN
BEGIN
IF h.cache[i].pNum = BTree.statePage
THEN statePageIndex ← i
ELSE StoreCachePage[h, i];
END;
ENDLOOP;
IF statePageIndex # noIndex THEN StoreCachePage[h, statePageIndex];
END;
CacheEntryNotInHashTable: ERROR = CODE;
NoAvailableCacheEntries: ERROR = CODE;
GetEmptyCacheEntry:
INTERNAL
PROC [h: Handle]
RETURNS [i: CacheIndex] =
The cache entry that is returned is empty; it has a valid space and a useCount of zero. It may be assocaited with a page by setting pNum.
BEGIN
FOR cntr:
CARDINAL
IN [0..2*h.cache.count)
DO
i ← (h.rover + cntr) MOD h.cache.count;
SELECT
TRUE
FROM
h.cache[i].empty =>
BEGIN -- empty entry
IF h.cache[i].ptr = NIL
THEN h.cache[i].ptr ← Space.LongPointer[h.cache[i].space ← GetSpace[h]];
h.cache[i].recentlyUsed ← FALSE;
h.cache[i].dirty ← FALSE;
h.cache[i].referenceCount ← 0;
EXIT;
END;
h.cache[i].referenceCount = 0 =>
BEGIN -- not currently being used
IF h.cache[i].recentlyUsed
THEN h.cache[i].recentlyUsed ← FALSE
ELSE
BEGIN
-- not even recently used
IF h.cache[i].dirty
THEN
IF h.cache[i].pNum = BTree.statePage
THEN LOOP -- never force out the statePage
ELSE StoreCachePage[h, i];
EXIT;
END;
END;
ENDCASE;
REPEAT FINISHED => ERROR NoAvailableCacheEntries
ENDLOOP;
IF
NOT h.cache[i].empty
THEN
BEGIN
hx: CARDINAL = HashIndex[h, h.cache[i].pNum];
IF h.hashTable[hx] = i
THEN h.hashTable[hx] ← h.cache[i].hash
ELSE
FOR j: CacheIndex ← h.hashTable[hx], h.cache[j].hash
UNTIL j = noIndex
DO
IF h.cache[j].hash = i THEN {h.cache[j].hash ← h.cache[i].hash; EXIT};
REPEAT FINISHED => ERROR CacheEntryNotInHashTable;
ENDLOOP;
h.cache[i].empty ← TRUE;
END;
h.rover ← (i+1) MOD h.cache.count;
END;
ExtendFile:
INTERNAL
PROC [h: Handle, n: BTree.PageNumber] =
BEGIN
filePageForNPlus1: File.PageNumber = (n+1)*h.filePagesPerPage + h.base;
IF h.filePages = 0 THEN h.filePages ← File.GetSize[h.fp];
IF h.filePages < filePageForNPlus1
THEN
BEGIN
h.filePages ← filePageForNPlus1 + 8*h.filePagesPerPage;
TRUSTED {File.SetSize[h.fp, h.filePages]};
END;
END;
LoadCachePage:
INTERNAL
PROC [h: Handle, i: CacheIndex] =
BEGIN
w: Space.WindowOrigin = [file: h.fp, base: h.base + h.cache[i].pNum*h.filePagesPerPage];
then: System.Pulses = System.GetClockPulses[];
TRUSTED {Space.CopyIn [space: h.cache[i].space, window: w]};
h.cumReadWriteTime ← [h.cumReadWriteTime + (System.GetClockPulses[]-then)];
h.reads ← h.reads+1;
END;
StoreCachePage:
INTERNAL
PROC [h: Handle, i: CacheIndex] =
BEGIN
w: Space.WindowOrigin = [file: h.fp, base: h.base + h.cache[i].pNum*h.filePagesPerPage];
then: System.Pulses = System.GetClockPulses[];
TRUSTED {Space.CopyOut [space: h.cache[i].space, window: w]};
h.cumReadWriteTime ← [h.cumReadWriteTime + (System.GetClockPulses[]-then)];
h.writes ← h.writes+1;
h.cache[i].dirty ← FALSE;
IF h.cache[i].pNum = BTree.statePage THEN h.updateStateOnDisk ← h.updateStateInCache;
END;
GetSpace:
INTERNAL
PROC [h: Handle]
RETURNS [s: Space.Handle] =
TRUSTED
BEGIN
s ← Space.Create[size: h.filePagesPerPage, parent: Space.virtualMemory];
Space.Map[space: s];
END;
END.