BTreeVMImpl.mesa
Copyright Ó 1985, 1986, 1988 by Xerox Corporation. All rights reserved.
Cache to support the BTree package
Created by M. D. Schroeder
Schroeder, June 10, 1983 3:04 pm
Taft, November 30, 1983 10:03 am
Levin, August 9, 1983 10:28 am
Russ Atkinson (RRA) May 11, 1988 11:07:14 pm PDT
Bob Hagmann January 4, 1989 3:43:34 pm PST
DIRECTORY
Basics,
<<BasicTime USING [GetClockPulses],>>
BTree USING [PageNumber, PagePtr, PageSize, PageStorage, ReferencePage, ReferenceType, ReleasePage, statePage, UpdateState],
BTreeVM,
IO,
<<Process USING [Detach],>>
SafeStorage USING [CantEstablishFinalization, EnableFinalization, EstablishFinalization, FinalizationQueue, FQNext, NewFQ],
VM USING [AddressForPageNumber, Free, Interval, PageNumber, PageNumberForAddress, PagesForBytes, SimpleAllocate];
BTreeVMImpl:
CEDAR
MONITOR
LOCKS h USING h: Handle
IMPORTS <<BasicTime,>>
IO, <<Process,>> SafeStorage,
VM
EXPORTS BTreeVM
= {
Types and constants
CacheIndex: TYPE = [0 .. LAST[BTreeVM.CacheSize]];
noIndex: CacheIndex = LAST[CacheIndex];
Stats: TYPE = BTreeVM.Stats;
Handle: TYPE = REF VMObject;
VMObject:
PUBLIC
TYPE =
MONITORED
RECORD [
backing: IO.STREAM, -- the backing stream
pageLength: INT, -- in bytes
offset: CARD, -- in bytes
rover: CacheIndex,
cache: REF Cache,
stats: REF Stats,
aDifferentField: INT ← 123,
hashTable: PACKED SEQUENCE count: CARDINAL OF CacheIndex
];
Cache: TYPE = RECORD [PACKED SEQUENCE count: CacheIndex OF CacheEntry];
CacheEntry:
TYPE =
RECORD [
pNum: BTree.PageNumber,
start: INT,
ptr: BTree.PagePtr,
referenceCount: INT,
hash: CacheIndex,
empty, recentlyUsed, dirty: BOOLEAN
];
useFinalization: BOOL ← FALSE;
Public procedures
Open:
PUBLIC
PROC [backing:
IO.
STREAM, pageSize: BTree.PageSize,
cacheSize: BTreeVM.CacheSize, offset:
CARD]
RETURNS [Handle] = {
h: Handle ← NEW[VMObject [2*cacheSize+1]];
h.backing ← backing;
h.offset ← offset;
h.pageLength ← pageSize * BYTES[WORD];
h.rover ← 0;
h.cache ← NEW[Cache[cacheSize]];
h.stats ← NEW[Stats];
FOR i: CacheIndex
IN [0 .. cacheSize)
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;
IF useFinalization THEN SafeStorage.EnableFinalization[h];
RETURN [h];
};
ReferencePage:
PUBLIC BTree.ReferencePage = {
PROC [storage: PageStorage, number: PageNumber, type: ReferenceType]
RETURNS [ptr: PagePtr]
InnerReference:
ENTRY
PROCEDURE [h: Handle] = {
ENABLE UNWIND => NULL;
hash: CARDINAL = HashIndex[h, number];
i: CacheIndex;
FOR i ← h.hashTable[hash], h.cache[i].hash
UNTIL i = noIndex
DO
h.stats.cumChainLength ← h.stats.cumChainLength+1;
IF h.cache[i].pNum = number THEN { h.stats.hits ← h.stats.hits+1; EXIT };
REPEAT
FINISHED => {
-- not found --
h.stats.misses ← h.stats.misses+1;
i ← GetEmptyCacheEntry[h];
h.cache[i].pNum ← number;
h.cache[i].start ← h.offset+h.cache[i].pNum*h.pageLength;
h.cache[i].empty ← FALSE;
IF type # new THEN LoadCachePage[h, i ! UNWIND => h.cache[i].empty ← TRUE;];
h.cache[i].hash ← h.hashTable[hash];
h.hashTable[hash] ← i;
};
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;
};
InnerReference[NARROW[storage]];
};
PageNotInUse: ERROR = CODE;
ReleasePage:
PUBLIC BTree.ReleasePage = {
PROC [storage: PageStorage, number: PageNumber, update: UpdateState]
InnerRelease:
ENTRY
PROCEDURE [h: Handle] = {
ENABLE UNWIND => NULL;
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 => RETURN WITH ERROR PageNotInUse;
ENDLOOP;
IF h.cache[i].referenceCount = 0 THEN RETURN WITH ERROR PageNotInUse;
h.cache[i].referenceCount ← h.cache[i].referenceCount - 1;
IF update # unchanged
THEN {
IF number = BTree.statePage
THEN {
is the statePage; can be either startOfUpdate or endOfUpdate
IF update = startOfUpdate
THEN StoreCachePage[h, i] -- only this page is dirty, so just write it
ELSE WriteDirtyPagesWithStatePageLast[h]; -- many pages possibly dirty
}
ELSE StoreCachePage[h, i];
is not the statePage; must be endOfUpdate; only page i is dirty
};
};
InnerRelease[NARROW[storage]];
};
GetStats:
PUBLIC
ENTRY
PROC [ h: Handle, stats:
REF Stats ] = {
stats ← h.stats;
};
FlushCache:
PUBLIC ENTRY
PROC [h: Handle] = {
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;
};
FreeBuffers:
PUBLIC ENTRY
PROC [ h: Handle ] = {
FOR i: CacheIndex
IN [0 .. h.cache.count)
DO
IF h.cache[i].ptr # NIL THEN {ReleaseSpace[h, h.cache[i].ptr]; h.cache[i].ptr ← NIL};
h.cache[i].empty ← TRUE;
ENDLOOP;
FOR c:
CARDINAL
IN [0..h.count)
DO
h.hashTable[c] ← noIndex;
ENDLOOP;
};
Private procedures
HashIndex:
INTERNAL
PROC [h: Handle, pNum: BTree.PageNumber]
RETURNS [
CARDINAL] =
INLINE {
RETURN [pNum MOD h.count];
};
WriteDirtyPagesWithStatePageLast:
INTERNAL
PROC [h: Handle] = {
statePageIndex: CacheIndex ← noIndex;
FOR i: CacheIndex
IN [0 .. h.cache.count)
DO
IF
NOT h.cache[i].empty
AND h.cache[i].dirty
THEN {
IF h.cache[i].pNum = BTree.statePage
THEN statePageIndex ← i
ELSE StoreCachePage[h, i];
};
ENDLOOP;
IF statePageIndex # noIndex THEN StoreCachePage[h, statePageIndex];
};
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.
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 => {
empty entry
IF h.cache[i].ptr = NIL THEN h.cache[i].ptr ← GetSpace[h];
h.cache[i].recentlyUsed ← FALSE;
h.cache[i].dirty ← FALSE;
h.cache[i].referenceCount ← 0;
EXIT;
};
h.cache[i].referenceCount = 0 =>
{
not currently being used
IF h.cache[i].recentlyUsed
THEN h.cache[i].recentlyUsed ← FALSE
ELSE {
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;
};
};
ENDCASE;
REPEAT FINISHED => ERROR NoAvailableCacheEntries
ENDLOOP;
IF
NOT h.cache[i].empty
THEN {
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;
};
h.rover ← (i+1) MOD h.cache.count;
};
ExtendFile:
INTERNAL
PROC [h: Handle, n: BTree.PageNumber] = {
desiredBytes: INT ← h.offset + ((n+1) * h.pageLength);
currentBytes: INT ← IO.GetLength[h.backing];
IF desiredBytes < currentBytes
THEN
TRUSTED {
localBytes: NAT = 256;
packed: PACKED ARRAY [0..localBytes) OF BYTE ← ALL[0];
basePtr: POINTER TO Basics.RawBytes = LOOPHOLE[@packed];
desiredBytes ← desiredBytes + 8*h.pageLength;
IO.SetIndex[h.backing, currentBytes];
WHILE desiredBytes > currentBytes
DO
delta: INT ← MIN[desiredBytes-currentBytes, localBytes];
IO.UnsafePutBlock[h.backing, [base: basePtr, startIndex: 0, count: delta]];
currentBytes ← currentBytes + delta;
ENDLOOP;
IO.Flush[h.backing];
};
};
LoadCachePage:
INTERNAL
PROC [h: Handle, i: CacheIndex] = {
<<then: CARD = BasicTime.GetClockPulses[];>>
TRUSTED {
basePtr: LONG POINTER TO Basics.RawBytes = LOOPHOLE[h.cache[i].ptr];
IO.SetIndex[h.backing, h.cache[i].start];
[] ← IO.UnsafeGetBlock[h.backing, [base: basePtr, startIndex: 0, count: h.pageLength]];
};
<<h.stats.cumReadWriteTime ← h.stats.cumReadWriteTime + (BasicTime.GetClockPulses[]-then);>>
h.stats.reads ← h.stats.reads+1;
};
StoreCachePage:
INTERNAL
PROC [h: Handle, i: CacheIndex] = {
<<then: CARD = BasicTime.GetClockPulses[];>>
TRUSTED {
basePtr: LONG POINTER TO Basics.RawBytes = LOOPHOLE[h.cache[i].ptr];
IO.SetIndex[h.backing, h.cache[i].start];
IO.UnsafePutBlock[h.backing, [base: basePtr, startIndex: 0, count: h.pageLength]];
IO.Flush[h.backing];
};
<<h.stats.cumReadWriteTime ← h.stats.cumReadWriteTime + (BasicTime.GetClockPulses[]-then);>>
h.stats.writes ← h.stats.writes+1;
h.cache[i].dirty ← FALSE;
};
GetSpace:
INTERNAL
PROC [h: Handle]
RETURNS [BTree.PagePtr] =
TRUSTED {
count: VM.PageNumber = VM.PagesForBytes[h.pageLength];
interval: VM.Interval = VM.SimpleAllocate[count];
RETURN [VM.AddressForPageNumber[interval.page]];
};
ReleaseSpace:
INTERNAL
PROC [h: Handle, ptr: BTree.PagePtr] =
TRUSTED {
count: VM.PageNumber = VM.PagesForBytes[h.pageLength];
VM.Free[[page: VM.PageNumberForAddress[ptr], count: count]];
};
Initialization and finalization
FinalizationProcess:
PROC = {
IF useFinalization
THEN {
DO
h: Handle ← NARROW [SafeStorage.FQNext[finalizationQueue]];
FreeBuffers[h];
h ← NIL;
ENDLOOP;
};
};
finalizationQueue: SafeStorage.FinalizationQueue;
IF useFinalization
THEN {
finalizationQueue ← SafeStorage.NewFQ[];
SafeStorage.EstablishFinalization[type: VMObject.CODE, npr: 0, fq: finalizationQueue ! SafeStorage.CantEstablishFinalization => CONTINUE];
<<TRUSTED {Process.Detach[FORK FinalizationProcess]};>>
};
}.
Bob Hagmann September 30, 1985 3:26:46 pm PDT
added UNWIND to NULL in ReferencePage and ReleasePage. It is necessary to release the monitor lock in ReferencePage during a salvage when trying to overcome hardware errors in the FS BTree.