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]; <> }; }. ΚBTreeVMImpl.mesa Copyright Σ 1985, 1986, 1988 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) May 11, 1988 11:07:14 pm PDT Bob Hagmann January 4, 1989 3:43:34 pm PST <> <> Types and constants Public procedures PROC [storage: PageStorage, number: PageNumber, type: ReferenceType] RETURNS [ptr: PagePtr] PROC [storage: PageStorage, number: PageNumber, update: UpdateState] is the statePage; can be either startOfUpdate or endOfUpdate is not the statePage; must be endOfUpdate; only page i is dirty 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. empty entry not currently being used not even recently used 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˜codešœ™KšœH™HKšœ"™"Kšœ™KšΟy ™ Kš ™ Kš™J™0K™*—K˜šΟk ˜ K˜Kšœ%™%Kšœžœq˜|Kšœ˜Kšžœ˜Kšœ™Kšœ žœj˜{Kšžœžœi˜qK˜—šΟn œžœž˜Kšžœžœ ˜Kšžœžœž˜7Kšžœ˜Kšœ˜—head™Icode2šœ žœ žœ˜2Mšœžœ ˜'Mšœžœ˜Mšœžœžœ ˜š œ žœžœž œžœ˜*Mšœ žœžœΟc˜)Mšœ žœ  ˜Mšœžœ  ˜Mšœ˜Mšœžœ˜Mšœžœ˜Mšœžœ˜Mš œ žœžœžœžœ ˜8Mšœ˜—Mš œžœžœžœžœžœ ˜Gšœ žœžœ˜Mšœ˜Mšœžœ˜ Mšœ˜Mšœžœ˜Mšœ˜Mšœž˜#Mšœ˜—Mšœžœžœ˜—™šŸœžœžœ žœžœBžœžœ ˜Mšœ žœ˜*Mšœ˜Mšœ˜Mšœžœžœ˜&M˜ Mšœ žœ˜ Mšœ žœ˜šžœžœž˜(Mšœžœ˜Mšœžœ˜Mšžœ˜—šžœžœžœž˜"Mšœ˜Mšžœ˜—Mšžœžœ#˜:Mšžœ˜ Mšœ˜—šŸ œžœ˜-MšžœBžœ™\šŸœžœž œ˜/Mšžœžœžœ˜Mšœžœ˜&Mšœ˜šžœ(žœ ž˜?Mšœ2˜2Mšžœžœ"žœ˜Išžœžœ ˜$M˜"Mšœ˜Mšœ˜Mšœ9˜9Mšœžœ˜Mšžœ žœžœžœ˜LMšœ$˜$Mšœ˜Mšœ˜—Mšžœ˜—Mšœžœ˜Mšœ:˜:Mšžœ žœžœ˜,Mšžœ žœ˜)Mšœ˜Mšœ˜—Mšœžœ ˜ Mšœ˜—Mšœžœžœ˜šŸ œžœ˜)Mšžœ@™DšŸ œžœž œ˜-Mšžœžœžœ˜Mšœ˜šžœ8žœ ž˜OMšžœžœžœ˜&Mš žœžœžœžœžœ˜2Mšžœ˜—Mš žœžœžœžœžœ˜EMšœ:˜:šžœžœ˜šžœ˜šžœ˜Mšœ<™<šžœ˜Mšžœ ,˜FMšžœ& ˜F—Mšœ˜—šžœ˜Mšœ?™?——Mšœ˜—Mšœ˜—Mšœ žœ ˜Mšœ˜—š Ÿœžœžœžœžœ ˜?Mšœ˜Mšœ˜—šŸ œž œžœ˜-Mšœ$˜$šžœžœž˜,Mšœžœ˜Mšžœ˜—šžœžœžœž˜"Mšœ˜Mšžœ˜—Mšœ˜—šŸ œž œžœ˜0šžœžœž˜,Mšžœžœžœ4žœ˜UMšœžœ˜Mšžœ˜—šžœžœžœž˜"Mšœ˜Mšžœ˜—Mšœ˜——™š Ÿ œžœžœ&žœžœžœ˜[Mšžœžœ ˜Mšœ˜—šŸ œžœžœ˜?Mšœ%˜%šžœžœž˜,šžœžœžœžœ˜3šžœ"˜$Mšžœ˜Mšžœ˜—Mšœ˜—Mšžœ˜—Mšžœžœ#˜CMšœ˜—Mšœžœžœ˜'Mšœžœžœ˜&šŸœžœžœ žœ˜JMšœ) œ Fœ ™Ššžœžœžœž˜-Mšœžœ˜'šžœžœž˜šœ˜Mšœ ™ Mšžœžœ˜:Mšœžœ˜ Mšœžœ˜Mšœ˜Mšžœ˜Mšœ˜—šœ  œ˜"Mšœ™šžœ˜Mšžœž˜$šžœ˜Mšœ™šžœž˜šžœ"˜$Mšžœžœ  ˜*Mšžœ˜——Mšžœ˜Mšœ˜——Mšœ˜—Mšžœ˜—Mšžœžœžœ˜0Mšžœ˜—šžœžœžœ˜Mšœžœ!˜-šžœ˜Mšžœ"˜&šžœžœ2žœ ž˜NMšžœžœ%žœ˜FMšžœžœžœ˜2Mšžœ˜——Mšœžœ˜Mšœ˜—Mšœžœ˜"Mšœ˜—šŸ œžœžœ%˜>Mšœžœ%˜6Mšœžœžœ˜,šžœžœžœ˜-Mšœ žœ˜Mš œžœžœžœžœžœ˜6Mšœ žœžœžœ ˜8Mšœ-˜-Mšžœ#˜%šžœž˜$Mšœžœžœ(˜8MšžœI˜KMšœ$˜$Mšžœ˜—Mšžœ˜Mšœ˜—Mšœ˜—šŸ œžœžœ˜;Mšœžœ ˜,šžœ˜ Mšœ ž œžœžœ˜DMšžœ'˜)MšœžœP˜WMšœ˜—Mšœ\˜\Mšœ ˜ Mšœ˜—šŸœžœžœ ˜=Mšœžœ ˜,šžœ˜ Mšœ ž œžœžœ˜DMšžœ'˜)MšžœP˜RMšžœ˜Mšœ˜—Mšœ\˜\Mšœ"˜"Mšœžœ˜Mšœ˜—š Ÿœžœžœ žœžœ˜GMšœžœžœ˜6Mšœ žœ žœ˜1Mšžœžœ&˜0Mšœ˜—šŸ œžœžœ#žœ˜GMšœžœžœ˜6Mšžœ žœ+˜