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 September 30, 1985 3:30:34 pm 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];
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.