AlpineEnvironment: TYPE USING [ PageNumber ],
AlpFile: TYPE USING [ GetSize, Handle, PageCount, PageRun, ReadPages, RESULTPageBuffer, SetSize, VALUEPageBuffer, WritePages ],
BasicTime: TYPE USING [ GetClockPulses, Pulses ],
BTree: TYPE USING [ PageStorage, PageNumber, PagePtr, ReferencePage, ReferenceType, ReleasePage, statePage, UpdateState ],
BTreeAlpineVM,
-- Process: TYPE USING [ Detach ],
-- RTTypesBasic: TYPE USING [EstablishFinalization, FinalizationQueue, FQNext, NewFQ ],
PrincOps: TYPE USING [wordsPerPage],
VM: TYPE USING [ AddressForPageNumber, Allocate, Interval ];
BTreeAlpineVMImpl:
CEDAR MONITOR
LOCKS h USING h: Handle
IMPORTS AlpFile, BasicTime, --Process, RTTypesBasic,-- VM
EXPORTS BTreeAlpineVM
= BEGIN
CacheIndex: TYPE = [0 .. LAST[BTreeAlpineVM.CacheSize]];
noIndex: CacheIndex = LAST[CacheIndex];
Handle: TYPE = REF VMObject;
VMObject:
PUBLIC
TYPE =
MONITORED
RECORD [
fp: AlpFile.Handle,
filePages: AlpFile.PageCount,
base: AlpineEnvironment.PageNumber,
filePagesPerPage: BTreeAlpineVM.FilePagesPerPage,
updateStateOnDisk: BTree.UpdateState,
updateStateInCache: BTree.UpdateState,
longUpdate: BOOLEAN,
rover: CacheIndex,
cache: REF Cache,
hits, misses, reads, writes, cumChainLength: LONG CARDINAL ← 0,
cumReadWriteTime: BasicTime.Pulses ← 0,
hashTable: PACKED SEQUENCE count: CARDINAL OF CacheIndex
];
Cache: TYPE = RECORD [PACKED SEQUENCE count: CacheIndex OF CacheEntry];
CacheEntry:
TYPE =
RECORD [
pNum: BTree.PageNumber,
interval: VM.Interval,
ptr: BTree.PagePtr,
referenceCount: [0..256),
hash: CacheIndex,
empty, recentlyUsed, dirty: BOOLEAN
];
Open:
PUBLIC
PROC [ file: AlpFile.Handle, filePagesPerPage: BTreeAlpineVM.FilePagesPerPage,
cacheSize: BTreeAlpineVM.CacheSize, base: AlpineEnvironment.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;
ReOpen:
PUBLIC
PROC [handle: Handle, file: AlpFile.Handle, base: AlpineEnvironment.PageNumber] =
BEGIN
FlushCache[handle];
handle.fp ← file;
handle.filePages ← 0;
handle.base ← base;
handle.updateStateOnDisk ← endOfUpdate;
handle.updateStateInCache ← endOfUpdate;
handle.longUpdate ← FALSE;
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 ] =
BEGIN
h.longUpdate ← TRUE;
END;
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: BasicTime.Pulses] =
BEGIN
RETURN [hits: h.hits, misses: h.misses, reads: h.reads, writes: h.writes, cumChainLength: h.cumChainLength, cumReadWriteTime: h.cumReadWriteTime];
END;
FlushCache:
PUBLIC ENTRY
PROC [ h: Handle ] =
BEGIN
WriteDirtyPagesWithStatePageLast[h];
FOR i: CacheIndex
IN [0 .. h.cache.count)
DO
h.cache[i].empty ← TRUE;
ENDLOOP;
FOR c:
CARDINAL
IN [0..h.count)
DO
h.hashTable[c] ← noIndex;
ENDLOOP;
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 interval 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 TRUSTED {
h.cache[i].interval ← VM.Allocate[count: h.filePagesPerPage];
h.cache[i].ptr ← VM.AddressForPageNumber[h.cache[i].interval.page]};
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: AlpineEnvironment.PageNumber = (n+1)*h.filePagesPerPage + h.base;
TRUSTED {IF h.filePages = 0 THEN h.filePages ← AlpFile.GetSize[h.fp]};
IF h.filePages < filePageForNPlus1
THEN
BEGIN
h.filePages ← filePageForNPlus1 + 8*h.filePagesPerPage;
TRUSTED {AlpFile.SetSize[h.fp, h.filePages]};
END;
END;
LoadCachePage:
INTERNAL
PROC [h: Handle, i: CacheIndex] =
TRUSTED BEGIN
pageRun: AlpFile.PageRun;
buffer: AlpFile.RESULTPageBuffer;
then: BasicTime.Pulses = BasicTime.GetClockPulses[];
buffer ← DESCRIPTOR[VM.AddressForPageNumber[h.cache[i].interval.page], h.filePagesPerPage*PrincOps.wordsPerPage];
pageRun ← [h.base + h.cache[i].pNum*h.filePagesPerPage, h.filePagesPerPage];
AlpFile.ReadPages[h.fp, pageRun, buffer];
h.cumReadWriteTime ← h.cumReadWriteTime + (BasicTime.GetClockPulses[]-then);
h.reads ← h.reads+1;
END;
StoreCachePage:
INTERNAL
PROC [h: Handle, i: CacheIndex] =
TRUSTED BEGIN
pageRun: AlpFile.PageRun;
buffer: AlpFile.VALUEPageBuffer;
then: BasicTime.Pulses = BasicTime.GetClockPulses[];
buffer ← DESCRIPTOR[VM.AddressForPageNumber[h.cache[i].interval.page], h.filePagesPerPage*PrincOps.wordsPerPage];
pageRun ← [h.base + h.cache[i].pNum*h.filePagesPerPage, h.filePagesPerPage];
AlpFile.WritePages[h.fp, pageRun, buffer];
h.cumReadWriteTime ← h.cumReadWriteTime + (BasicTime.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;
END.