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];
Exported procedures for allocation
IsUsed:
PUBLIC
ENTRY
PROC [segment: YggFileInternal.SegmentMetadataList, page: YggFile.PageNumber]
RETURNS [inUse:
BOOL ←
FALSE] ~ {
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.
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] ~ {
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.
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] ~ {
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.
ENABLE UNWIND => NULL;
Restrict run length to LAST[CARDINAL], to maximize runs per run-table page
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!
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 IsUsedInternal[segment, pos]
THEN {
Expand around "pos" to see if there's a run of size at least "min"
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] ~ {
Set the disk resident bitmap for this run. The tid is a top level transaction that is trying to commit.
InnerStableAllocOrFree[segment, run, tid, TRUE];
InnerStableAllocOrFree:
INTERNAL
PROC [segment: YggFileInternal.SegmentMetadataList, run: YggDIDMap.Run, tid: Camelot.tidT, allocation:
BOOL] ~ {
Set the disk resident bitmap for this run. The tid is a top level transaction that is trying to commit.
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];
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], newValueCnt: size, raiseSignal: TRUE];
Free:
PUBLIC
ENTRY
PROC [segment: YggFileInternal.SegmentMetadataList, run: YggDIDMap.Run] ~ {
Mark the logical run free in the in-memory (shadow) bitmap.
InnerFree[segment, run];
};
InnerFree:
INTERNAL
PROC [segment: YggFileInternal.SegmentMetadataList, run: YggDIDMap.Run] ~ {
Mark the logical run free in the in-memory (shadow) bitmap.
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] ~ {
Mark the logical run free in the stable bitmap.
InnerStableAllocOrFree[segment, run, tid, FALSE];
};
AllocAndFree:
PUBLIC
ENTRY
PROC [segment: YggFileInternal.SegmentMetadataList, tid: Camelot.tidT, runOpsList: YggFileInternal.RunOpsList] ~ {
Set the disk resident bitmap for this run. The tid is a top level transaction that is trying to commit..
All changes for a segment are presented at one time for a transaction. This procedure is called in ascending segment order by a transaction. Since all latches are set for a transaction at one time and they are done in a determined order, we cannot deadlock.
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;
};
Latches
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] ~ {
Drop all locks in the bitmaps.
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;
};
};
Internal procedures
IsUsedInternal:
INTERNAL
PROC [segment:
YggFileInternal.SegmentMetadataList, page: YggFile.PageNumber]
RETURNS [inUse:
BOOL ←
FALSE] ~ {
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.
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] ~ {
Mark the logical run free in the in-memory (shadow) bitmap.
currentPage: CARD ← run.segmentPage;
pagesLeft: CARD ← run.pages;
high: CARD;
low5bits: bitIn32BitWord;
bitsToDo: bitIn32BitWord;
alloc: YggFileInternal.AllocWord;
Do individual bits on non-entire word
[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;
};
};
};