DIRECTORY BTree: TYPE USING [PageNumber, PagePtr, PageStorage, ReferencePage, ReferenceType, ReleasePage, statePage, UpdateState], BTreeVM, File: TYPE USING [Handle, Info, PageCount, PageNumber, Read, SetSize, wordsPerPage, Write], PrincOpsUtils: TYPE USING [GetClockPulses], VM USING [Allocate, Interval, PageNumberToAddress, WordsToPages]; BTreeVMImpl: CEDAR MONITOR LOCKS h USING h: Handle IMPORTS File, PrincOpsUtils, 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, updateStateOnDisk: BTree.UpdateState, updateStateInCache: BTree.UpdateState, longUpdate: BOOLEAN, 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.WordsToPages[File.wordsPerPage * 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 ] = BEGIN h.longUpdate _ TRUE; END; 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, 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; 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; IF h.cache[i].pNum = BTree.statePage THEN h.updateStateOnDisk _ h.updateStateInCache; END; GetSpace: INTERNAL PROC [h: Handle] RETURNS [BTree.PagePtr] = TRUSTED BEGIN interval: VM.Interval = VM.Allocate[count: h.vmPagesPerPage]; RETURN [VM.PageNumberToAddress[interval.page]]; END; END. و BTreeVMImpl.mesa Cache to support the BTree package Created by M. D. Schroeder Last Edited by: Schroeder, June 10, 1983 3:04 pm Taft, June 9, 1983 3:27 pm PROC [storage: PageStorage, number: PageNumber, type: ReferenceType] RETURNS [ptr: PagePtr] PROC [storage: PageStorage, number: PageNumber, update: UpdateState] Only page i is dirty 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. ‌ت:– "Cedar" styleکJ™Jڑœ™JکJڑœ"™"JکJڑœ™Jک™J™ J™—JکJڑدk ک کJڑœ‌œ‌œgکxJڑœکJڑœ‌œ‌œKک[Jڑœ‌œ‌œک+Jڑœ‌œ9کAJک—Jکڑœ ‌ کJڑ‌œ‌œ کJڑ‌œکJڑ‌œکJڑœ‌کJکJکJڑœ‌œ ‌œک2JکJڑœ‌œک(Jڑœ‌œ‌œ کJکڑ œ ‌œ‌œ‌ œ‌œک*JڑœکJڑœکJڑœکJڑœ+ک+Jڑœ‌œکJڑœ%ک%Jڑœ&ک&Jڑœ‌œکJڑœکJڑœ‌œکJڑœ?‌œ‌œکQJڑ œ‌œ‌œ‌œ‌œک8Jڑœک—JکJڑœ‌œ‌œ‌œ‌œ‌œ کGJکڑœ‌œ‌œکJڑœکJڑœکJڑœکJڑœکJڑœ‌ک#Jڑœک—JکJکڑدnœ‌œ‌œx‌œ ک‌Jڑ‌کJڑœ‌œک*JڑœکJڑœدc"ک3JکJڑœ&ک&JڑœIکIJڑœ"ک"Jڑœ#ک#Jڑœ‌œکJکJڑœ ‌œک ڑ‌œ‌œ‌ک,Jڑœ‌œکJڑœ‌œکJڑ‌œک—ڑ‌œ‌œ‌œ‌ک"JڑœکJڑ‌œک—Jڑ‌œکJڑ‌œک—JکJ™ڑ‍ œ‌œک+Jڑ‌œB‌œ™\Jڑ‌کڑ‍œ‌œ‌ œ‌ک4Jڑ‌کJڑœ‌œک&Jڑœکڑ‌œ(‌œ ‌ک?Jک&Jڑ‌œ‌œ‌œک=ڑ‌œ‌œ‌œںک(JکJڑœکJڑœکJڑœ‌œکJڑ‌œ‌œک'Jڑœ$ک$JڑœکJڑ‌œک—Jڑ‌œک—Jڑœ‌œکJڑœ:ک:Jڑ‌œ ‌œ‌œک,Jڑ‌œ‌œک)JڑœکJڑ‌œک—Jڑœ‌œک Jڑ‌œک—JکJکJڑœ‌œ‌œکJکڑ‍œ‌œک'Jڑ‌œ@™DJڑ‌کڑ‍œ‌œ‌ œ‌ک2Jڑ‌کJڑœکڑ‌œ8‌œ ‌کOJڑ‌œ‌œ‌œک&Jڑ‌œ‌œ‌œک&Jڑ‌œک—Jڑ‌œک Jڑ‌œ‌œ کJڑ‌œ;ک?Jڑ‌œکڑ‌œ‌ک Jڑ‌œکڑ‌œ‌œں?کJJڑœکJڑ‌œ‌œ کڑ‌œ‌ک Jڑ‌œکJڑ‌œں,کFJڑ‌œ&ںکFJڑ‌ک—ڑ‌œ‌œں.ک9Jڑ‌œ"ک$Jڑ‌œکJڑ‌œک—Jڑ‌ک—ڑ‌œ‌œں,ک7Jڑ‌œ‌œ کJ™Jڑ‌œکJڑ‌œک—Jڑ‌œک—Jڑ‌œک—Jڑœ ‌œکJڑ‌œک—JکJکڑ‍œ‌œ‌œک2Jڑ‌کJڑœ‌œکJڑ‌œک—JکJکڑ‍ œ‌œ‌œک0Jڑ‌کڑ‌œ‌کJڑ‌کJڑœ$ک$Jڑœ‌œکJڑ‌œک—Jڑ‌œک—JکJکڑ‍œ‌œ‌œ‌œ‌œA‌œ‌œک‚Jڑ‌کJڑ‌œŒک’Jڑ‌œک—JکJکڑ‍ œ‌œ‌œک-Jڑ‌کJڑœ$ک$ڑ‌œ‌œ‌ک,Jڑœ‌œکJڑ‌œک—ڑ‌œ‌œ‌œ‌ک"JڑœکJڑ‌œک—Jڑ‌œک—JکJکJڑ‍ œ‌œ‌œ&‌œ‌œ‌œ‌œ‌œکxJکJکڑ‍ œ‌œ‌œک?Jڑ‌کJڑœ%ک%ڑ‌œ‌œ‌ک,Jڑ‌œ‌œ‌œک,ڑ‌œ‌ک Jڑ‌œ"ک$Jڑ‌œکJڑ‌œکJڑ‌œک—Jڑ‌œک—Jڑ‌œ‌œ#کCJڑ‌œکJک—JکJڑœ‌œ‌œک'Jڑœ‌œ‌œک&Jکڑ‍œ‌œ‌œ ‌œکHJڑœ)ںœںFœں™ٹJڑ‌کڑ‌œ‌œ‌œ‌ک-Jڑœ‌œک'ڑ‌œ‌œ‌کڑœکJڑ‌œںکJڑ‌œ‌کJڑ‌œک"Jڑœ‌œک Jڑœ‌œکJڑœکJڑ‌œکJڑ‌œک—ڑœ ک Jڑ‌œںک!Jڑ‌œکJڑ‌œ‌ک$ڑ‌œ‌œںک%ڑ‌œ‌کJڑ‌œ"ک$Jڑ‌œ‌œں ک*Jڑ‌œک—Jڑ‌œکJڑ‌œک—Jڑ‌œک—Jڑ‌œک—Jڑ‌œ‌œ‌œک0Jڑ‌œک—ڑ‌œ‌œ‌œ‌ک"Jڑœ‌œ!ک-Jڑ‌œکJڑ‌œ"ک&ڑ‌œ‌œ2‌œ ‌کNJڑ‌œ‌œ%‌œکFJڑ‌œ‌œ‌œک2Jڑ‌œک—Jڑœ‌œکJڑ‌œک—Jڑœ‌œک"Jڑ‌œک—JکJکڑ‍ œ‌œ‌œ#ک