<> <> <> <<>> <> <> <<>> DIRECTORY Basics USING [ BITAND, bitsPerByte, BITXOR, RawBytes ], Camelot USING [DSLogOldValueNewValue, DSPinObject, optrT, tidT ], PBasics USING [ BITAND, BITRSHIFT, BITXOR, ByteBlt ], Process USING [ MsecToTicks, SetTimeout ], Rope USING [ ROPE ], YggDIDMap USING [ NullRun, Run ], YggEnvironment USING [dsPort], YggFile USING [ bytesPerPage, Error, PageCount, PageNumber ], YggFileInternal USING [AllocWord, PTAllocBitmap, RunOpsList, SegmentMetadata, SegmentMetadataList]; YggFileSegmentImpl: CEDAR MONITOR LOCKS segment.first USING segment: YggFileInternal.SegmentMetadataList IMPORTS Basics, Camelot, PBasics, Process, YggEnvironment, YggFile EXPORTS YggFileInternal = { <> ROPE: TYPE ~ Rope.ROPE; bitIn32BitWord: TYPE = CARD [0..32); debugging: BOOL _ TRUE; <> IsUsed: PUBLIC ENTRY PROC [segment: YggFileInternal.SegmentMetadataList, 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: YggFileInternal.SegmentMetadataList, 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: YggFileInternal.SegmentMetadataList, 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.segmentPage _ start; EXIT }; }; pos _ [pos+min]; REPEAT FINISHED => RETURN[YggDIDMap.NullRun]; ENDLOOP; segment.first.freePages _ segment.first.freePages - given.pages; doFreeOrAllocate[segment.first.vmAddressForShadowAllocMap, [segmentId: segment.first.segmentId, segmentPage: given.segmentPage, firstPage: 0, pages: given.pages, leader: FALSE], TRUE]; IF first = 0 THEN segment.first.rover _ [given.firstPage]; given.segmentId _ segment.first.segmentId; given.leader _ FALSE; given.firstPage _ 0; }; StableAlloc: PUBLIC ENTRY PROC [segment: YggFileInternal.SegmentMetadataList, run: YggDIDMap.Run, tid: Camelot.tidT] ~ { <> InnerStableAllocOrFree[segment, run, tid, TRUE]; }; <<>> InnerStableAllocOrFree: INTERNAL PROC [segment: YggFileInternal.SegmentMetadataList, run: YggDIDMap.Run, tid: Camelot.tidT, allocation: BOOL] ~ { <> oldValue: REF Basics.RawBytes; optr: Camelot.optrT; firstByte: INT; lastByte: INT; size: CARD32; optr.segmentId _ segment.first.segmentId; optr.highOffset _ 0; firstByte _ run.segmentPage/Basics.bitsPerByte; lastByte _ (run.segmentPage + run.pages - 1)/Basics.bitsPerByte; size _ lastByte - firstByte + 1; optr.lowOffset _ YggFile.bytesPerPage*segment.first.offsetToFirstAllocPage + firstByte; [] _ Camelot.DSPinObject[dsPort: YggEnvironment.dsPort, tid: tid, optr: optr, size: size, raiseSignal: TRUE]; IF BYTES[UNIT] = 2 AND (optr.lowOffset MOD 2 =1 OR size MOD 2 =1) THEN { -- byte addressing doesn't work (e. g. Dorado) and we are not word alligned evenFirstByte: INT; evenLastBytePlusOne: INT; evenSize: CARD32; evenOptr: Camelot.optrT; evenFirstByte _ PBasics.BITAND[firstByte, 0FFFFFFFEH]; evenLastBytePlusOne _ PBasics.BITAND[lastByte + 2, 0FFFFFFFEH]; evenSize _ evenLastBytePlusOne - evenFirstByte; evenOptr _ optr; evenOptr.lowOffset _ PBasics.BITAND[evenOptr.lowOffset, 0FFFFFFFEH]; oldValue _ NEW[Basics.RawBytes[evenSize]]; TRUSTED {IF evenSize # PBasics.ByteBlt[to: [blockPointer: LOOPHOLE[oldValue], startIndex: 0, stopIndexPlusOne: evenSize], from: [blockPointer: LOOPHOLE[segment.first.vmAddressForSegmentAllocMap], startIndex: evenFirstByte, stopIndexPlusOne: evenLastBytePlusOne]] THEN ERROR;}; doFreeOrAllocate[segment.first.vmAddressForSegmentAllocMap, run, allocation]; [] _ Camelot.DSLogOldValueNewValue[dsPort: YggEnvironment.dsPort, tid: tid, optr: evenOptr, oldValue: LOOPHOLE[oldValue], oldValueCnt: evenSize, newValue: LOOPHOLE[segment.first.vmAddressForSegmentAllocMap+evenFirstByte/BYTES[UNIT]], newValueCnt: evenSize, raiseSignal: TRUE]; } ELSE { -- byte addressing works oldValue _ NEW[Basics.RawBytes[size]]; TRUSTED {IF size # PBasics.ByteBlt[to: [blockPointer: LOOPHOLE[oldValue], startIndex: 0, stopIndexPlusOne: size], from: [blockPointer: LOOPHOLE[segment.first.vmAddressForSegmentAllocMap], startIndex: firstByte, stopIndexPlusOne: lastByte + 1]] THEN ERROR;}; doFreeOrAllocate[segment.first.vmAddressForSegmentAllocMap, run, allocation]; [] _ Camelot.DSLogOldValueNewValue[dsPort: YggEnvironment.dsPort, tid: tid, optr: optr, oldValue: LOOPHOLE[oldValue], oldValueCnt: size, newValue: LOOPHOLE[segment.first.vmAddressForSegmentAllocMap+firstByte/BYTES[UNIT]], newValueCnt: size, raiseSignal: TRUE]; }; }; <<>> Free: PUBLIC ENTRY PROC [segment: YggFileInternal.SegmentMetadataList, run: YggDIDMap.Run] ~ { <> InnerFree[segment, run]; }; <<>> InnerFree: INTERNAL PROC [segment: YggFileInternal.SegmentMetadataList, run: YggDIDMap.Run] ~ { <> doFreeOrAllocate[segment.first.vmAddressForShadowAllocMap, run, FALSE]; segment.first.freePages _ segment.first.freePages + run.pages; }; <<>> StableFree: PUBLIC ENTRY PROC [segment: YggFileInternal.SegmentMetadataList, run: YggDIDMap.Run, tid: Camelot.tidT] ~ { <> InnerStableAllocOrFree[segment, run, tid, FALSE]; }; AllocAndFree: PUBLIC ENTRY PROC [segment: YggFileInternal.SegmentMetadataList, tid: Camelot.tidT, runOpsList: YggFileInternal.RunOpsList] ~ { <> <> FOR rol: YggFileInternal.RunOpsList _ runOpsList, rol.rest UNTIL rol = NIL DO SELECT rol.first.opOnRun FROM stableAlloc => { InnerStableAllocOrFree[segment: segment, run: rol.first.run, tid: tid, allocation: TRUE]; SetLatches[segment: segment, run: rol.first.run, tid: tid]; }; stableFree => { InnerStableAllocOrFree[segment: segment, run: rol.first.run, tid: tid, allocation: FALSE]; SetLatches[segment: segment, run: rol.first.run, tid: tid]; }; stableAndVolatileFree => { InnerStableAllocOrFree[segment: segment, run: rol.first.run, tid: tid, allocation: FALSE]; InnerFree[segment: segment, run: rol.first.run]; SetLatches[segment: segment, run: rol.first.run, tid: tid]; }; volatileFree => { InnerFree[segment: segment, run: rol.first.run]; }; ENDCASE => ERROR; ENDLOOP; }; <> myLatch: CONDITION; ComLatch: TYPE = RECORD[tid: Camelot.tidT, firstPage: INT, lastPage: INT]; CommitFileLatches: CommitLatchList _ NIL; CommitLatchList: TYPE = LIST OF CommitLatchRep; CommitLatchRep: TYPE = RECORD[ segment: YggFileInternal.SegmentMetadataList, latchList: LIST OF ComLatch ]; SetLatches: INTERNAL PROC [segment: YggFileInternal.SegmentMetadataList, run: YggDIDMap.Run, tid: Camelot.tidT] ~ { cfl: CommitLatchList _ NIL; firstPage: INT; lastPage: INT; firstPage _ PBasics.BITAND[run.segmentPage, 0FFFFFFF8H]; lastPage _ PBasics.BITAND[run.segmentPage + run.pages + 6, 0FFFFFFF8H]; FOR cfl _ CommitFileLatches, cfl.rest UNTIL cfl = NIL DO IF cfl.first.segment = segment THEN EXIT; REPEAT FINISHED => { CommitFileLatches _ CONS[[segment, NIL], CommitFileLatches]; cfl _ CommitFileLatches; }; ENDLOOP; DO doAWait: BOOL _ FALSE; FOR ll: LIST OF ComLatch _ cfl.first.latchList, ll.rest UNTIL ll = NIL DO IF ll.first.tid = tid THEN LOOP ELSE { IF lastPage < ll.first.firstPage OR firstPage > ll.first.lastPage THEN LOOP; doAWait _ TRUE; }; ENDLOOP; IF doAWait THEN WAIT myLatch ELSE EXIT; ENDLOOP; cfl.first.latchList _ CONS[[tid, firstPage, lastPage], cfl.first.latchList]; }; ClearLatches: PUBLIC ENTRY PROC [segment: YggFileInternal.SegmentMetadataList, tid: Camelot.tidT] ~ { <> cfl: CommitLatchList _ NIL; FOR cfl _ CommitFileLatches, cfl.rest UNTIL cfl = NIL DO IF cfl.first.segment = segment THEN EXIT; ENDLOOP; IF cfl # NIL THEN { prevLatchList: LIST OF ComLatch _ NIL; FOR ll: LIST OF ComLatch _ cfl.first.latchList, ll.rest UNTIL ll = NIL DO IF ll.first.tid = tid THEN { IF prevLatchList # NIL THEN prevLatchList.rest _ ll.rest ELSE cfl.first.latchList _ ll.rest; } ELSE prevLatchList _ ll; ENDLOOP; BROADCAST myLatch; }; }; <> IsUsedInternal: INTERNAL PROC [segment: YggFileInternal.SegmentMetadataList, 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 _ PBasics.BITRSHIFT[page, 5]; }; <<>> doFreeOrAllocate: INTERNAL PROC [vmAddressForWhateverBitmap: YggFileInternal.PTAllocBitmap, run: YggDIDMap.Run, allocation: BOOL] ~ { <> currentPage: CARD _ run.segmentPage; pagesLeft: CARD _ run.pages; high: CARD; low5bits: bitIn32BitWord; bitsToDo: bitIn32BitWord; alloc: YggFileInternal.AllocWord; <> [high, low5bits] _ decomposePageNo[[currentPage]]; bitsToDo _ MIN[32-CARD[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; a1or0: CARD32 _ 0; IF ~allocation THEN a1or0 _ LOOPHOLE[0FFFFFFFFh]; allOnesOrAllZeros.card _ a1or0; FOR c: CARD IN [high..high+pagesToDo) DO TRUSTED {IF debugging AND PBasics.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[CARD[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; }; }; }; <<>> <> TRUSTED { Process.SetTimeout[condition: @myLatch, ticks: Process.MsecToTicks[250]]; }; <<>> <<>> <<>> }. <<>>