DIRECTORY Basics USING [ BITAND, BITRSHIFT, BITXOR ], Rope USING [ ROPE ], YggDIDMap USING [ NullRun, Run ], YggFile USING [ Error, PageCount, PageNumber ], YggFileInternal USING [AllocWord, PTAllocBitmap, SegmentMetadata]; YggFileSeqmentImpl: CEDAR MONITOR LOCKS segment.first USING segment: LIST OF YggFileInternal.SegmentMetadata IMPORTS Basics, YggFile EXPORTS YggFileInternal = { ROPE: TYPE ~ Rope.ROPE; bitIn32BitWord: TYPE = INT [0..32); debugging: BOOL _ TRUE; IsUsed: PUBLIC ENTRY PROC [segment: LIST OF YggFileInternal.SegmentMetadata, page: YggFile.PageNumber] RETURNS [inUse: BOOL _ FALSE] ~ { high: INT; low5bits: bitIn32BitWord; alloc: YggFileInternal.AllocWord; [high, low5bits] _ decomposePageNo[page]; TRUSTED {alloc _ segment.first.vmAddressForShadowAllocMap[high];}; RETURN [alloc.bits[low5bits] ]; }; SetPageUsed: PUBLIC ENTRY PROC [segment: LIST OF YggFileInternal.SegmentMetadata, page: YggFile.PageNumber, inUse: BOOL] RETURNS [wasInUse: BOOL _ FALSE] ~ { high: INT; low5bits: bitIn32BitWord; alloc: YggFileInternal.AllocWord; [high, low5bits] _ decomposePageNo[page]; TRUSTED {alloc _ segment.first.vmAddressForShadowAllocMap[high];}; IF alloc.bits[low5bits] THEN RETURN[TRUE] ELSE { alloc.bits[low5bits] _ TRUE; RETURN[FALSE]; }; }; Alloc: PUBLIC ENTRY PROC [segment: LIST OF YggFileInternal.SegmentMetadata, first: YggFile.PageNumber, size, min: YggFile.PageCount, minPage, maxPage: YggFile.PageNumber] RETURNS [given: YggDIDMap.Run] ~ { ENABLE UNWIND => NULL; pos: YggFile.PageNumber; realMaxPage: YggFile.PageNumber; IF segment.first.freePages < size THEN RETURN WITH ERROR YggFile.Error[volumeFull]; IF size = 0 THEN RETURN[YggDIDMap.NullRun]; realMaxPage _ [MIN[segment.first.numberOfPages, maxPage]]; pos _ IF first = 0 THEN segment.first.rover ELSE first; IF pos < minPage OR pos > maxPage THEN pos _ minPage; min _ MAX[ MIN[min, size], 1 ]; -- otherwise the algorithm doesn't work! THROUGH [0 .. (realMaxPage-minPage+min-1)/min] DO IF pos >= realMaxPage THEN pos _ [minPage]; IF NOT IsUsedInternal[segment, pos] THEN { start, end: YggFile.PageNumber _ pos; given.pages _ 1; WHILE start > 0 AND given.pages < size DO IF IsUsedInternal[segment, [start-1]] THEN EXIT; start _ [start-1]; given.pages _ given.pages + 1; ENDLOOP; WHILE end < segment.first.numberOfPages-1 AND given.pages < size DO IF IsUsedInternal[segment, [end+1]] THEN EXIT; end _ [end+1]; given.pages _ given.pages + 1; ENDLOOP; IF given.pages >= min THEN { given.firstPage _ start; EXIT }; }; pos _ [pos+min]; REPEAT FINISHED => RETURN[YggDIDMap.NullRun]; ENDLOOP; doFreeOrAllocate[segment.first.vmAddressForShadowAllocMap, [segmentId: segment.first.segmentId, segmentPage: given.firstPage, firstPage: 0, pages: given.pages, leader: FALSE], TRUE]; IF first = 0 THEN segment.first.rover _ [given.firstPage]; }; StableAlloc: PUBLIC ENTRY PROC [segment: LIST OF YggFileInternal.SegmentMetadata, run: YggDIDMap.Run] ~ { doFreeOrAllocate[segment.first.vmAddressForSegmentAllocMap, run, TRUE]; }; Free: PUBLIC ENTRY PROC [segment: LIST OF YggFileInternal.SegmentMetadata, run: YggDIDMap.Run] ~ { doFreeOrAllocate[segment.first.vmAddressForShadowAllocMap, run, FALSE]; }; StableFree: PUBLIC ENTRY PROC [segment: LIST OF YggFileInternal.SegmentMetadata, run: YggDIDMap.Run] ~ { doFreeOrAllocate[segment.first.vmAddressForSegmentAllocMap, run, FALSE]; }; IsUsedInternal: INTERNAL PROC [segment: LIST OF YggFileInternal.SegmentMetadata, page: YggFile.PageNumber] RETURNS [inUse: BOOL _ FALSE] ~ { high: INT; low5bits: bitIn32BitWord; alloc: YggFileInternal.AllocWord; [high, low5bits] _ decomposePageNo[page]; TRUSTED {alloc _ segment.first.vmAddressForShadowAllocMap[high];}; RETURN [alloc.bits[low5bits] ]; }; decomposePageNo: PROC [page: YggFile.PageNumber] RETURNS [high: INT, low5bits: bitIn32BitWord] ~ { low5bits _ Basics.BITAND[page, 01Fh]; high _ Basics.BITRSHIFT[page, 5]; }; doFreeOrAllocate: INTERNAL PROC [vmAddressForWhateverBitmap: YggFileInternal.PTAllocBitmap, run: YggDIDMap.Run, allocation: BOOL] ~ { currentPage: CARD _ run.segmentPage; pagesLeft: CARD _ run.pages; high: INT; low5bits: bitIn32BitWord; bitsToDo: bitIn32BitWord; alloc: YggFileInternal.AllocWord; [high, low5bits] _ decomposePageNo[[currentPage]]; bitsToDo _ MIN[32-low5bits, pagesLeft]; IF bitsToDo > 0 THEN { TRUSTED {alloc _ vmAddressForWhateverBitmap[high];}; FOR bitNo: bitIn32BitWord IN [low5bits..low5bits+bitsToDo) DO IF debugging AND alloc.bits[bitNo] = allocation THEN ERROR; alloc.bits[bitNo] _ allocation; ENDLOOP; TRUSTED {vmAddressForWhateverBitmap[high] _ alloc}; currentPage _ currentPage + bitsToDo; pagesLeft _ pagesLeft - bitsToDo; }; IF pagesLeft # 0 THEN { pagesToDo: CARD; pagesToDo _ decomposePageNo[[pagesLeft]].high; [high, low5bits] _ decomposePageNo[[currentPage]]; IF pagesToDo > 0 THEN { allOnesOrAllZeros: YggFileInternal.AllocWord _ IF allocation THEN LOOPHOLE[0] ELSE LOOPHOLE[0FFFFFFFFh]; FOR c: CARD IN [high..high+pagesToDo) DO TRUSTED {IF debugging AND Basics.BITXOR[LOOPHOLE[allOnesOrAllZeros], LOOPHOLE[vmAddressForWhateverBitmap[c]]] # 0 THEN ERROR; }; TRUSTED {vmAddressForWhateverBitmap[c] _ allOnesOrAllZeros;}; currentPage _ currentPage + 32; pagesLeft _ pagesLeft - 32; ENDLOOP; }; [high, low5bits] _ decomposePageNo[[currentPage]]; bitsToDo _ MIN[32-low5bits, pagesLeft]; IF bitsToDo > 0 THEN { TRUSTED {alloc _ vmAddressForWhateverBitmap[high];}; FOR bitNo: bitIn32BitWord IN [low5bits..low5bits+bitsToDo) DO IF debugging AND alloc.bits[bitNo] = allocation THEN ERROR; alloc.bits[bitNo] _ allocation; ENDLOOP; TRUSTED {vmAddressForWhateverBitmap[high] _ alloc}; currentPage _ currentPage + bitsToDo; pagesLeft _ pagesLeft - bitsToDo; }; }; }; }. YggFileSeqmentImpl.mesa Copyright ำ 1988 by Xerox Corporation. All rights reserved. Bob Hagmann June 30, 1988 8:43:31 am PDT Access to per-segment data structures The first version of this code was created by editing LogicalVolumeImpl. Data types and variables Exported procedures for allocation Test to see if a page is in-use. This test is done under the monitor, but no guarantee is made about how long the result will be true. This flavor of test is for the shadow bitmap. Test to see if a page is in-use, and set it to "inUse". This test is done under the monitor, but no guarantee is made about how long the result will be true. This flavor of operation is for the shadow bitmap. Find a logical run marked free in the in-memory bitmap. May be smaller than "size", but is never smaller than "min" if anything is allocated. If given.pages is 0 then no pages allocated. This flavor of allocation is for the shadow bitmap. To make the allocation stable, StableAlloc must be called with the run. Restrict run length to LAST[CARDINAL], to maximize runs per run-table page Loop probing for a free page at "min" intervals Expand around "pos" to see if there's a run of size at least "min" Set the disk resident bitmap for this run. The tid is a top level transaction that is trying to commit. Add the dance for Camelot to pin and log the page(s) of the bitmap Mark the logical run free in the in-memory (shadow) bitmap. Mark the logical run free in the stable bitmap. Add the dance for Camelot to pin and log the page(s) of the bitmap Internal procedures Test to see if a page is in-use. This test is done under the monitor, but no guarantee is made about how long the result will be true. This flavor of test is for the shadow bitmap. Mark the logical run free in the in-memory (shadow) bitmap. Do individual bits on non-entire word ******** Volume Allocation Map ******** --FileInternal.-- Alloc: PUBLIC ENTRY PROC [volume: Volume, first: VolumeFormat.LogicalPage, size, min: VolumeFormat.LogicalPageCount, minPage, maxPage: VolumeFormat.LogicalPage, largeFile: BOOL] RETURNS [given: VolumeFormat.LogicalRun] = TRUSTED { ENABLE UNWIND => NULL; Restrict run length to LAST[CARDINAL], to maximize runs per run-table page reqSize: VolumeFormat.RunPageCount = MIN[size,LAST[VolumeFormat.RunPageCount]]; pos: VolumeFormat.LogicalPage; vam: VAM; realMaxPage: VolumeFormat.LogicalPage; WHILE volume.checkpointing DO WAIT notCheckpointing ENDLOOP; IF volume.vamStatus # ok THEN RETURN WITH ERROR File.Error[volume.vamStatus]; IF volume.free < size THEN RETURN WITH ERROR File.Error[volumeFull]; IF size = 0 THEN RETURN[[first: first, size: 0]]; -- main algorithm gives at least one page vam _ volume.vam; realMaxPage _ [MIN[vam.size, maxPage]]; pos _ IF first = 0 THEN vam.rover ELSE first; IF pos < minPage OR pos > maxPage THEN pos _ minPage; min _ MAX[ MIN[min, reqSize], 1 ]; -- otherwise the algorithm doesn't work! Loop probing for a free page at "min" intervals THROUGH [0 .. (realMaxPage-minPage+min-1)/min] DO IF pos >= realMaxPage THEN pos _ [minPage]; IF NOT Used[vam, pos] THEN { Expand around "pos" to see if there's a run of size at least "min" start, end: VolumeFormat.LogicalPage _ pos; given.size _ 1; WHILE start > 0 AND given.size < reqSize DO IF Used[vam, [start-1]] THEN EXIT; start _ [start-1]; given.size _ given.size + 1; ENDLOOP; WHILE end < vam.size-1 AND given.size < reqSize DO IF Used[vam, [end+1]] THEN EXIT; end _ [end+1]; given.size _ given.size + 1; ENDLOOP; IF given.size >= min THEN { given.first _ start; EXIT }; }; pos _ [pos+min]; REPEAT FINISHED => RETURN WITH ERROR File.Error[volumeFull] ENDLOOP; volume.vamChanged _ TRUE; FOR i: INT IN [0..given.size) DO [] _ SetUsed[volume, [given.first+i], TRUE]; ENDLOOP; IF volume.labeled THEN { IF first = 0 THEN vam.rover _ given.first; } ELSE { IF largeFile THEN volume.largeVAMrover _ given.first ELSE volume.smallVAMrover _ given.first; IF volume.volatileVAM AND volume.vamStable THEN { -- vam is no longer stable why: File.RC; volume.vamStable _ FALSE; volume.root.vamStable _ FALSE; why _ RootTransfer[volume: volume, direction: write]; IF why # ok THEN RETURN WITH ERROR File.Error[why]; }; }; ConsiderFlushing[volume]; }; ส F˜codešœ™Kšœ<™