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 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 ]; 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 = 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 = 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; 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] = 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; 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. تBTreeVMImpl.mesa Copyright c 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 Types and constants Public procedures PROC [storage: PageStorage, number: PageNumber, type: ReferenceType] RETURNS [ptr: PagePtr] PROC [storage: PageStorage, number: PageNumber, update: UpdateState] Private procedures 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. Initialization and finalization 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. ‌ت– "Cedar" styleکheadڑœ™Icodeڑœ دmœ1™