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];
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] ~ {
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]];
};




}.

	YggFileSegmentImpl.mesa 
Copyright ำ 1988, 1989 by Xerox Corporation.  All rights reserved.
Bob Hagmann February 20, 1989 1:33:58 pm PST

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.

Set the disk resident bitmap for this run.  The tid is a top level transaction that is trying to commit.

Mark the logical run free in the in-memory (shadow) bitmap.

Mark the logical run free in the in-memory (shadow) bitmap.

Mark the logical run free in the stable bitmap.
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.
Latches
Drop all locks in the bitmaps.
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

Initialization




สื˜
codeš
œ™Kš
œB™BK™,K™Kš
œ%™%K™H—K™š
ฯk	˜	Kšœœœ

œ˜7Kšœœ4˜AKšœœœœ˜5Kšœœœ
˜*Kšœœœ˜Kšœ
œ˜!Kšœœ
˜Kšœœ0˜=KšœœN˜c—K˜š
ฯnœœ
œ
œœ-˜hKšœ;˜BKšœ˜Kš
œ˜—
head™Kšœœœ
˜—˜Kšœœœ	˜$K˜šœœœ
˜K˜—K˜K˜—š
œ"™"šžœœ
œ
œJœ	œœ˜„
Jš
œถ
™ถ
Jšœœ
˜
Jš
œ˜Jš
œ!˜!Jš
œ)˜)Jšœ;˜BJšœ˜J˜J™—šžœœ

œ#œ#œœœœ˜™
Jš
œา
™า
Jšœœ
˜
Jš
œ˜Jš
œ!˜!Jš
œ)˜)Jšœ;˜BJšœœ
œ
œ
˜)šœ
œ˜Jšœœ
˜Jšœ
œ˜J˜—J˜—J™šžœœ

œ#œ`˜ฆ
šœ˜"Kš
œบ™บKšœ
œœ
˜Kš
œJ™JKš
œ˜Kš
œ ˜ Kš
œ œ
œ
œ
œ˜SKšœ
œ
œ˜,Kšœœ(˜:Kšœœœœ˜7Kšœœœ˜5Kšœœœฯc(˜HKš
œ/™/šœ(˜1Kšœœ˜+šœ
œœ˜*Kš
œB™BKš
œ%˜%K˜šœœ˜)Kšœ$œ
œ
˜0Kš
œ˜Kš
œ˜Kšœ
˜—šœ%œ˜CKšœ"œ
œ
˜.Kš
œ˜Kš
œ˜Kšœ
˜—Kšœœœ˜?Kš
œ˜—Kš
œ˜Kšœ
œœ˜.Kšœ
˜—Kš
œ@˜@Kšœช
œœ˜ธ
Kšœœ)˜:Kš
œ*˜*Kš
œ˜Kš
œ˜K˜——K˜šžœœ
œ
œZ˜xK™hKšœ*œ˜0˜K™——šžœœ
œcœ˜‘
K™hKšœ
œ˜Kš
œ˜Kšœœ
˜Kšœ
œ
˜Kšœœ
˜
Kš
œ)˜)Kš
œ˜Kš
œ/˜/Kš
œ@˜@Kš
œ ˜ Kš
œX˜XKšœgœ˜mKšœœ˜&Kšœœ+œIœeœ
œ˜Kš
œM˜MKšœbœ)œWœ˜๘
˜K™——šžœœ
œ
œG˜^Kš
œ;™;Kš
œ˜K˜K™—šž	œœ
œG˜_Kš
œ;™;Kšœ@œ˜GKš
œ>˜>K˜K™—š
ž
œœ
œ
œ#œ,˜wKš
œ/™/Kš
œ1˜1K˜K˜—šžœœ
œ
œn˜
Kš
œi™iKš
œƒ™ƒšœ8œœ
˜Mšœ˜š
œ˜KšœSœ˜YKš
œ;˜;K˜—š
œ˜KšœSœ˜ZKš
œ;˜;K˜—š
œ˜KšœSœ˜ZKš
œ0˜0Kš
œ;˜;K˜—š
œ˜Kš
œ0˜0K˜—Kšœœ
˜—Kšœ
˜—K˜—K˜K˜—™J˜Jš	œ
œœœœ˜JJ˜)J˜/˜Jš
œ-˜-J˜J˜J˜—šž
œœ
œZ˜sJšœœ
˜Jšœœ
˜Jšœ
œ
˜Jšœœ˜8Jšœœ.˜Gšœ#œœ
˜8Jšœœ
œ
˜)šœ
œ˜Jšœœœ˜<Jš
œ˜J˜—Jšœ
˜—š
˜Jšœ	œœ
˜šœ5œœ
˜IJšœœ
˜šœ
œ˜Jšœœœ
œ
˜LJšœ
œ
˜J˜—Jšœ
˜—Jš
œ	œ
œ	œ
œ
˜'Jšœ
˜—Jšœœ2˜LJ˜J˜—šžœœ
œ
œF˜eKš
œ™Jšœœ
˜šœ#œœ
˜8Jšœœ
œ
˜)Jšœ
˜—šœœ
œ˜Jšœœ
œœ
˜&šœ5œœ
˜Išœœ˜Jšœœ
œ˜8Jšœ
œ˜$J˜
—Jšœ
œ˜Jšœ
˜—Kš	œ	˜K˜—K˜——š
œ™šžœœ
œ#œœ	œœ˜ˆ
Jš
œถ
™ถ
Jšœœ
˜
Jš
œ˜Jš
œ!˜!Jš
œ)˜)Jšœ;˜BJšœ˜J˜J™—šฯbœœœœ˜bJšœœ
˜%Jšœ	œ
˜"J˜J™—š œœ
œ]œ˜…
Kš
œ;™;Kšœ
œ˜$Kšœœ
˜Jšœœ
˜Jš
œ˜Jš
œ˜š
œ!˜!J™%—Jš
œ2˜2Jšœœ˜-šœœ˜Jšœ-˜4šœœ˜=Kšœœ œ
œ
˜;Kš
œ˜Kšœ
˜—Jšœ,˜3Kš
œ%˜%Kš
œ!˜!K˜—šœœ˜Kšœœ
˜Jš
œ.˜.Jš
œ2˜2šœœ˜Jš
œ-˜-Jšœ
œ
˜Jšœ
œ	œ
˜1Jš
œ˜šœœ
œ˜(Kšœœœ	œ
œœ%œ
œ˜
Kšœ6˜=Kš
œ˜Kš
œ˜Kšœ
˜—J˜—Jš
œ2˜2Jšœœ˜-šœœ˜Jšœ-˜4šœœ˜=Kšœœ œ
œ
˜;Kš
œ˜Kšœ
˜—Jšœ,˜3Kš
œ%˜%Kš
œ!˜!K˜—K˜—K˜K™—K˜—™
code2šœ˜	Mš
œI˜IMš
œ˜K™K™—˜K™—K˜K˜K˜—Kš
œ˜K˜K™—…—(ˆ=w