<> <> <> <> <> <> <> <> <> DIRECTORY Basics, <<<>>> BTree USING [PageNumber, PagePtr, PageSize, PageStorage, ReferencePage, ReferenceType, ReleasePage, statePage, UpdateState], BTreeVM, IO, <<<>>> 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 <> IO, <> SafeStorage, VM EXPORTS BTreeVM = { <> 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; <> 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 = { <> 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 = { <> 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 { <> 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]; <> }; }; 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; }; <> 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] = { <> 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 => { <> 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 => { <> IF h.cache[i].recentlyUsed THEN h.cache[i].recentlyUsed _ FALSE ELSE { <> 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] = { <> 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.reads _ h.stats.reads+1; }; StoreCachePage: INTERNAL PROC [h: Handle, i: CacheIndex] = { <> 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.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]]; }; <> 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]; <> }; }. <> <> <<>>