<> <> <> <<>> <> <> <<>> 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; }; }; }; <<>> <<******** Volume Allocation Map ********>> <<>> <<>> <<>> <<>> <<>> << --FileInternal.-->> <> < NULL;>> <> <> <> <> <> <> <> <> <> <> <> <> < maxPage THEN pos _ minPage;>> <> <> <> <= realMaxPage THEN pos _ [minPage];>> <> <> <> <> < 0 AND given.size < reqSize>> <> <> <> <> <> <> <> <= min THEN { given.first _ start; EXIT };>> <<};>> <> < RETURN WITH ERROR File.Error[volumeFull]>> <> <> <> <<[] _ SetUsed[volume, [given.first+i], TRUE];>> <> <> <> <<}>> <> <> <> <> <> <> <> <> <<};>> <<};>> <> <<};>> <<>> }. <<>>