BTreeVMImpl.mesa
Copyright © 1985 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) February 1, 1985 5:33:42 pm PST
Bob Hagmann July 4, 1986 7:28:33 am PDT
DIRECTORY
BTree USING [PageNumber, PagePtr, PageStorage, ReferencePage, ReferenceType, ReleasePage, statePage, UpdateState],
BTreeVM USING [CacheSize, FilePagesPerPage],
File USING [Handle, Info, PageCount, PageNumber, Read, SetSize, wordsPerPage, Write],
PrincOpsUtils USING [GetClockPulses],
Process USING [Detach],
SafeStorage USING [EnableFinalization, EstablishFinalization, FinalizationQueue, FQNext, NewFQ],
VM USING [AddressForPageNumber, Allocate, Free, Interval, PageNumberForAddress, PagesForWords];
BTreeVMImpl: CEDAR MONITOR
LOCKS h USING h: Handle
IMPORTS File, PrincOpsUtils, Process, SafeStorage, VM
EXPORTS BTreeVM
= BEGIN
Types and constants
CacheIndex: TYPE = [0 .. LAST[BTreeVM.CacheSize]];
noIndex: CacheIndex = LAST[CacheIndex];
Handle: TYPE = REF VMObject;
VMObject: PUBLIC TYPE = MONITORED RECORD [
handle: File.Handle,
filePages: File.PageCount,
base: File.PageNumber,
filePagesPerPage: BTreeVM.FilePagesPerPage,
vmPagesPerPage: CARDINAL,
rover: CacheIndex,
cache: REF Cache,
hits, misses, reads, writes, cumChainLength, cumReadWriteTime: LONG CARDINAL ← 0,
hashTable: PACKED SEQUENCE count: CARDINAL OF CacheIndex
];
Cache: TYPE = RECORD [PACKED SEQUENCE count: CacheIndex OF CacheEntry];
CacheEntry: TYPE = RECORD [
pNum: BTree.PageNumber,
ptr: BTree.PagePtr,
referenceCount: [0..256),
hash: CacheIndex,
empty, recentlyUsed, dirty: BOOLEAN
];
Public procedures
Open: PUBLIC PROC [ file: File.Handle, filePagesPerPage: BTreeVM.FilePagesPerPage,
cacheSize: BTreeVM.CacheSize, base: File.PageNumber ] RETURNS [ Handle ] =
BEGIN
h: Handle ← NEW[VMObject [2*cacheSize+1]];
h.handle ← file;
h.filePages ← 0; -- indicates that we don't know --
h.base ← base;
h.filePagesPerPage ← filePagesPerPage;
h.vmPagesPerPage ← VM.PagesForWords[File.wordsPerPage * filePagesPerPage];
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;
SafeStorage.EnableFinalization[h];
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
ENABLE UNWIND => NULL;
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 ! UNWIND => h.cache[i].empty ← TRUE;];
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
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 => 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
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 StoreCachePage[h, i]; -- is not the statePage; must be endOfUpdate; only page i is dirty
END;
END;
InnerRelease[NARROW[storage]];
END;
GetStats: PUBLIC ENTRY PROC [ h: Handle ] RETURNS [hits, misses, reads, writes, cumChainLength, cumReadWriteTime: LONG CARDINAL] =
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;
FreeBuffers: PUBLIC ENTRY PROC [ h: Handle ] =
BEGIN
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;
END;
Private procedures
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 ← 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
fileSizeForNPlus1: File.PageCount = (n+1)*h.filePagesPerPage + h.base;
IF h.filePages = 0 THEN h.filePages ← File.Info[h.handle].size;
IF h.filePages < fileSizeForNPlus1
THEN BEGIN
h.filePages ← fileSizeForNPlus1 + 8*h.filePagesPerPage;
File.SetSize[h.handle, h.filePages];
END;
END;
LoadCachePage: INTERNAL PROC [h: Handle, i: CacheIndex] =
BEGIN
then: LONG CARDINAL = PrincOpsUtils.GetClockPulses[];
TRUSTED {File.Read [file: h.handle, from: [h.base + h.cache[i].pNum*h.filePagesPerPage], nPages: h.filePagesPerPage, to: h.cache[i].ptr]};
h.cumReadWriteTime ← h.cumReadWriteTime + (PrincOpsUtils.GetClockPulses[]-then);
h.reads ← h.reads+1;
END;
StoreCachePage: INTERNAL PROC [h: Handle, i: CacheIndex] =
BEGIN
then: LONG CARDINAL = PrincOpsUtils.GetClockPulses[];
TRUSTED {File.Write[file: h.handle, to: [h.base + h.cache[i].pNum*h.filePagesPerPage], nPages: h.filePagesPerPage, from: h.cache[i].ptr]};
h.cumReadWriteTime ← h.cumReadWriteTime + (PrincOpsUtils.GetClockPulses[]-then);
h.writes ← h.writes+1;
h.cache[i].dirty ← FALSE;
END;
GetSpace: INTERNAL PROC [h: Handle] RETURNS [BTree.PagePtr] = TRUSTED
BEGIN
interval: VM.Interval = VM.Allocate[count: h.vmPagesPerPage];
RETURN [VM.AddressForPageNumber[interval.page]];
END;
ReleaseSpace: INTERNAL PROC [h: Handle, ptr: BTree.PagePtr] = TRUSTED
BEGIN
VM.Free[[page: VM.PageNumberForAddress[ptr], count: h.vmPagesPerPage]];
END;
Initialization and finalization
FinalizationProcess: PROC =
BEGIN
DO
h: Handle ← NARROW [SafeStorage.FQNext[finalizationQueue]];
FreeBuffers[h];
h ← NIL;
ENDLOOP;
END;
finalizationQueue: SafeStorage.FinalizationQueue ← SafeStorage.NewFQ[];
SafeStorage.EstablishFinalization[type: VMObject.CODE, npr: 0, fq: finalizationQueue];
TRUSTED {Process.Detach[FORK FinalizationProcess]};
END.
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.