<> <> <> <> <> DIRECTORY BTree: TYPE USING [ PageStorage, PageNumber, PagePtr, ReferencePage, ReferenceType, ReleasePage, statePage, UpdateState ], BTreeVM, File: TYPE USING [ Capability, GetSize, PageCount, PageNumber, SetSize ], -- Process: TYPE USING [ Detach ], -- RTTypesBasic: TYPE USING [EstablishFinalization, FinalizationQueue, FQNext, NewFQ ], Space: TYPE USING [ CopyIn, CopyOut, Create, Handle, LongPointer, Map, WindowOrigin, virtualMemory ], System: TYPE USING [ GetClockPulses, Pulses ]; BTreeVMImpl: CEDAR MONITOR LOCKS h USING h: Handle IMPORTS File, --Process, RTTypesBasic,-- Space, System EXPORTS BTreeVM = BEGIN CacheIndex: TYPE = [0 .. LAST[BTreeVM.CacheSize]]; noIndex: CacheIndex = LAST[CacheIndex]; Handle: TYPE = REF VMObject; VMObject: PUBLIC TYPE = MONITORED RECORD [ fp: File.Capability, filePages: File.PageCount, base: File.PageNumber, filePagesPerPage: BTreeVM.FilePagesPerPage, updateStateOnDisk: BTree.UpdateState, updateStateInCache: BTree.UpdateState, longUpdate: BOOLEAN, rover: CacheIndex, cache: REF Cache, hits, misses, reads, writes, cumChainLength: LONG CARDINAL _ 0, cumReadWriteTime: System.Pulses _ [0], hashTable: PACKED SEQUENCE count: CARDINAL OF CacheIndex ]; Cache: TYPE = RECORD [PACKED SEQUENCE count: CacheIndex OF CacheEntry]; CacheEntry: TYPE = RECORD [ pNum: BTree.PageNumber, space: Space.Handle, ptr: BTree.PagePtr, referenceCount: [0..256), hash: CacheIndex, empty, recentlyUsed, dirty: BOOLEAN ]; Open: PUBLIC PROC [ file: File.Capability, filePagesPerPage: BTreeVM.FilePagesPerPage, cacheSize: BTreeVM.CacheSize, base: File.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; <<>> ReferencePage: PUBLIC BTree.ReferencePage = <> 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 = <> 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 <> THEN StoreCachePage[h, i]; END; END; END; InnerRelease[NARROW[storage]]; END; StartLongUpdate: PUBLIC ENTRY PROC [ h: Handle ] = { h.longUpdate _ TRUE }; 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: System.Pulses] = BEGIN RETURN [hits: h.hits, misses: h.misses, reads: h.reads, writes: h.writes, cumChainLength: h.cumChainLength, cumReadWriteTime: h.cumReadWriteTime]; 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 _ Space.LongPointer[h.cache[i].space _ 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 filePageForNPlus1: File.PageNumber = (n+1)*h.filePagesPerPage + h.base; IF h.filePages = 0 THEN h.filePages _ File.GetSize[h.fp]; IF h.filePages < filePageForNPlus1 THEN BEGIN h.filePages _ filePageForNPlus1 + 8*h.filePagesPerPage; TRUSTED {File.SetSize[h.fp, h.filePages]}; END; END; LoadCachePage: INTERNAL PROC [h: Handle, i: CacheIndex] = BEGIN w: Space.WindowOrigin = [file: h.fp, base: h.base + h.cache[i].pNum*h.filePagesPerPage]; then: System.Pulses = System.GetClockPulses[]; TRUSTED {Space.CopyIn [space: h.cache[i].space, window: w]}; h.cumReadWriteTime _ [h.cumReadWriteTime + (System.GetClockPulses[]-then)]; h.reads _ h.reads+1; END; StoreCachePage: INTERNAL PROC [h: Handle, i: CacheIndex] = BEGIN w: Space.WindowOrigin = [file: h.fp, base: h.base + h.cache[i].pNum*h.filePagesPerPage]; then: System.Pulses = System.GetClockPulses[]; TRUSTED {Space.CopyOut [space: h.cache[i].space, window: w]}; h.cumReadWriteTime _ [h.cumReadWriteTime + (System.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; GetSpace: INTERNAL PROC [h: Handle] RETURNS [s: Space.Handle] = TRUSTED BEGIN s _ Space.Create[size: h.filePagesPerPage, parent: Space.virtualMemory]; Space.Map[space: s]; END; END. <<>>