DIRECTORY
Allocator USING [bsiEscape, ExtendedHeader, HeaderP, LastAddress, logPagesPerQuantum, NHeaderP, NormalHeader, QuantumIndex, wordsPerQuantum],
AllocatorOps USING [AddressToQuantumIndex, BlockSize, EnterAndCallBack, IsValidRef, NHPToREF, quantumMap, REFToNHP, Reset, TAndSFreeObject],
AMBridge USING [TVForReferent, TVToLC],
AMModelContextImpl USING [GFContextRec],
AMTypes USING [Class, Error, Index, IndexToTV, IsComputed, IsNil, IsOverlaid, NComponents, Referent, TypeClass, TV, TVType, UnderClass, UnderType, Variant],
Basics USING [BITAND, CARD, DoubleShiftLeft, LowHalf],
CircularGarbageTraceAndSweep USING [APNodes, maxNReferers],
Collector USING [EstablishTAndSProc],
DebuggerSwap USING [CallDebugger],
List USING [Reverse],
LoadState USING [Acquire, ConfigID, EnumerateAllModules, GlobalFrameToType, local, ModuleIndex, ModuleToGlobalFrame, Release],
PrincOps USING [GlobalFrameHandle, logWordsPerPage, wordsPerPage],
Process USING [MsecToTicks, Pause],
RCMap USING [nullIndex],
RCMicrocodeOps USING [ASSIGNREF, OnZ, RCOverflowOccurred, RCUnderflowOccurred, ZCTFull],
Rope USING [RopeRep],
RTFrameHeapSnapshot USING [AcquireFrameHeapSnapshot, MapUncountedBodies, ReleaseFrameHeapSnapshot],
RTTypesBasicPrivate USING [MapRefs, MapTiRcmx, NumberPackageRefs],
RTTypesPrivate USING [TypedVariableRec],
SafeStorage USING [GetReferentType, nullType, ReclaimCollectibleObjects, Type, WaitForCollectorDone],
UnsafeStorage USING [GetSystemUZone],
VM USING [AddressForPageNumber, Free, PageNumberForAddress, SimpleAllocate],
ZCT USING [EnterAndCallBack, EnterRCOvAndCallBack, InnerHandleRCOverflow, InnerHandleRCUnderflow, RCOvReset, zct, zctBlockWords];

CircularGarbageTraceAndSweepImpl: PROGRAM
IMPORTS AllocatorOps, AMBridge, AMTypes, Basics, Collector, DebuggerSwap, List, LoadState, Process, RCMicrocodeOps, RTFrameHeapSnapshot, RTTypesBasicPrivate, SafeStorage, UnsafeStorage, VM, ZCT
EXPORTS CircularGarbageTraceAndSweep
SHARES AMModelContextImpl, Rope
= BEGIN OPEN Allocator;

CARD: TYPE = Basics.CARD;
Type: TYPE = SafeStorage.Type;
nullType: Type = SafeStorage.nullType;


nRetainedObjects: CARD _ 0;
rpa: ARRAY [0..maxNRPIndex] OF LONG POINTER _ ALL[NIL];
maxNRPIndex: CARDINAL = 20;
nextRpaIndex: CARDINAL _ 0;

destructiveTestEnabled: BOOL _ FALSE; 
findingCircularGarbage: BOOL _ FALSE; 
circularGarbageObject: TYPE = RECORD[
put: INT _ 0,
max: INT _ 0,
item: SEQUENCE size: CARDINAL OF NHeaderP
];
circularGarbageSeq: LONG POINTER TO circularGarbageObject _ NIL;
typedVariableType: Type;
listOfGFContextRecType: Type;
ropeRepType: Type;

refStackChain: RefStack _ NIL; 
refStackFree: RefStack _ NIL;
nRefsPushed: INT _ 0; 
rememberRopes: BOOL;

objectsSeen: CARD _ 0;
objectsReclaimed: CARD _ 0; 
objectsKept: CARD _ 0; 
objectsGarbage: CARD _ 0; 
nGlobalFrames: CARD _ 0; 
nRCGlobalFrames: CARD _ 0; 
nLocalFrames: CARD _ 0; 


SuspectSeen: SIGNAL = CODE; 
suspect: LONG POINTER TO UNSPECIFIED _ LOOPHOLE[LONG[-1]];
forgiving: BOOL _ TRUE;
forgivingLog: ForgivingLog _ NIL;
forgivingLogCount: INT _ 0;
forgivingLogIndex: [0..ForgivingLogEntries) _ 0;

ForgivingLogPages: NAT = 4;
ForgivingLog: TYPE = LONG POINTER TO ForgivingLogRep;
ForgivingLogRep: TYPE = ARRAY [0..ForgivingLogEntries) OF ForgivingLogEntry;
ForgivingLogEntry: TYPE = RECORD [
nhp: Allocator.NHeaderP,
header: Allocator.NormalHeader
];
ForgivingLogEntries: NAT = (ForgivingLogPages*PrincOps.wordsPerPage)/SIZE[ForgivingLogEntry];


RefStackRep: TYPE = RECORD [
next: RefStack _ NIL, 
size: CARDINAL _ 0,
max: CARDINAL _ RefStackMax, 
refs: SEQUENCE COMPUTED CARDINAL OF LONG POINTER
];
RefStack: TYPE = LONG POINTER TO RefStackRep;
RefStackPages: NAT = 4;
RefStackMax: NAT = (PrincOps.wordsPerPage*RefStackPages - (SIZE[RefStackRep])) / (SIZE[LONG POINTER]);

suspectRef: LONG POINTER _ NIL;  -- a LOOPHOLE'd REF

APNodes: TYPE = CircularGarbageTraceAndSweep.APNodes;
suspectReferers: REF APNodes _ NEW[APNodes _ ALL[NIL]];
maxNReferers: NAT =  CircularGarbageTraceAndSweep.maxNReferers;
nSuspectReferers: NAT _ 0;

AIPNodes: TYPE = ARRAY [0..maxNInnerReferers) OF NHeaderP;
innerReferers: REF AIPNodes _ NEW[AIPNodes _ ALL[NIL]];
maxNInnerReferers: NAT = 50;
nInnerReferers: NAT _ 0;

gfhToSuspectRef: PrincOps.GlobalFrameHandle _ NIL;
suspectRefFoundInLocalFrame: BOOL _ FALSE;
circularStructureFound: BOOL _ FALSE;


REFToNHP: PUBLIC PROC[ref: REF ANY] RETURNS[Allocator.NHeaderP] = {
RETURN[AllocatorOps.REFToNHP[ref]];
};

NHPToREF: PUBLIC PROC[nhp: Allocator.NHeaderP] RETURNS[REF ANY] = {
RETURN[AllocatorOps.NHPToREF[nhp]];
};

WhoPointsToRef: PUBLIC PROC [ref: REF, cycleLimit: NAT _ 20] RETURNS [ referers: LIST OF REF _ NIL, gfh: PrincOps.GlobalFrameHandle, foundInLocalFrame, foundInCircularStructure: BOOL, cycles: NAT _ 0] = {
nhp: NHeaderP;
referersAPNodes: REF APNodes;
nhp _ AllocatorOps.REFToNHP[ref];
[referersAPNodes, gfh, foundInLocalFrame, foundInCircularStructure, cycles] _ WhoPointsTo[nhp, cycleLimit];
FOR index: INT IN [0..maxNReferers) DO
IF referersAPNodes[index] = NIL THEN EXIT;
referers _ CONS[AllocatorOps.NHPToREF[referersAPNodes[index]], referers];
referers _ List.Reverse[referers];
ENDLOOP;
RETURN ;
};

WhoPointsTo: PUBLIC PROC [nhp: NHeaderP, cycleLimit: NAT _ 20] RETURNS [ referers: REF APNodes, gfh: PrincOps.GlobalFrameHandle, foundInLocalFrame, foundInCircularStructure: BOOL, cycles: NAT _ 0] = {
FOR i: NAT IN [0..maxNReferers) DO suspectReferers[i] _ NIL ENDLOOP;
suspectReferers[0] _ nhp;
nSuspectReferers _ 1;

FOR i: NAT IN [0..maxNInnerReferers) DO innerReferers[i] _ NIL ENDLOOP;
nInnerReferers _ 0;

gfhToSuspectRef _ NIL;
suspectRefFoundInLocalFrame _ FALSE;
circularStructureFound _ FALSE;

UNTIL gfhToSuspectRef # NIL
OR circularStructureFound
OR suspectRefFoundInLocalFrame
OR nSuspectReferers > 1
OR nSuspectReferers = 0
OR cycles = cycleLimit
DO 
suspectRef _ LOOPHOLE[AllocatorOps.NHPToREF[suspectReferers[0]], LONG POINTER];
FOR i: NAT IN [0..maxNReferers) DO suspectReferers[i] _ NIL ENDLOOP;
nSuspectReferers _ 0;
SafeStorage.ReclaimCollectibleObjects[suspendMe: TRUE, traceAndSweep: TRUE];
cycles _ cycles + 1;
ENDLOOP;
suspectRef _ NIL;
RETURN[
referers: suspectReferers,
gfh: gfhToSuspectRef,
foundInLocalFrame: suspectRefFoundInLocalFrame,
foundInCircularStructure: circularStructureFound,
cycles: cycles];
};
InitFindCircularGarbage: PROC [nObjects: CARDINAL, uZone: UNCOUNTED ZONE, reportRopes: BOOL] = {
incrCollectCnt: INT _ 0;
incrWordsReclaimed: INT _ 0;
lastWordsReclaimed: INT _ LAST[INT];
UNTIL (incrCollectCnt > 20) OR (incrWordsReclaimed >= lastWordsReclaimed AND incrCollectCnt > 3) DO
SafeStorage.ReclaimCollectibleObjects[suspendMe: TRUE];
incrWordsReclaimed _ SafeStorage.WaitForCollectorDone[].wordsReclaimed;
Process.Pause[Process.MsecToTicks[100]];
lastWordsReclaimed _ incrWordsReclaimed;
incrCollectCnt _ incrCollectCnt + 1;
ENDLOOP;
findingCircularGarbage _ TRUE;
objectsGarbage _ 0;
rememberRopes _ reportRopes;
typedVariableType _ CODE[RTTypesPrivate.TypedVariableRec];
listOfGFContextRecType _ CODE [RECORD[first: AMModelContextImpl.GFContextRec, rest: LIST OF AMModelContextImpl.GFContextRec]];
ropeRepType _ CODE[Rope.RopeRep];
circularGarbageSeq _ uZone.NEW[circularGarbageObject[nObjects]];
circularGarbageSeq.max _ nObjects;
SafeStorage.ReclaimCollectibleObjects[suspendMe: TRUE, traceAndSweep: TRUE];
};

FindCircularGarbageTypes: PUBLIC PROC [nObjects: CARDINAL, reportRopes: BOOL _ TRUE] RETURNS [ nGarbage, nSeen: INT, garbage: LIST OF Type _ NIL] = {
uZone: UNCOUNTED ZONE = UnsafeStorage.GetSystemUZone[];
InitFindCircularGarbage [nObjects: nObjects, uZone: uZone, reportRopes: reportRopes]; 
FOR index: INT _ circularGarbageSeq.put, index-1 UNTIL index <= 0 DO
garbage _ CONS[circularGarbageSeq[index-1].type, garbage];
circularGarbageSeq[index-1] _ NIL;
ENDLOOP;
uZone.FREE[@circularGarbageSeq];
circularGarbageSeq _ NIL;
findingCircularGarbage _ FALSE;
nGarbage _ objectsGarbage;
nSeen _ objectsSeen;
};

FindCircularGarbage: PUBLIC PROC [nObjects: CARDINAL, reportRopes: BOOL _ TRUE] RETURNS [ nGarbage, nSeen: INT, garbage: LIST OF REF _ NIL] = {
uZone: UNCOUNTED ZONE = UnsafeStorage.GetSystemUZone[];
InitFindCircularGarbage [nObjects: nObjects, uZone: uZone, reportRopes: reportRopes]; 
FOR index: INT _ circularGarbageSeq.put, index-1 UNTIL index <= 0 DO
garbage _ CONS[AllocatorOps.NHPToREF[circularGarbageSeq[index-1]], garbage];
circularGarbageSeq[index-1] _ NIL;
ENDLOOP;
uZone.FREE[@circularGarbageSeq];
circularGarbageSeq _ NIL;
findingCircularGarbage _ FALSE;
nGarbage _ objectsGarbage;
nSeen _ objectsSeen;
};

FindConnectedComponent: PUBLIC PROC [rootObject: REF ANY, nObjects: CARDINAL, reportRopes: BOOL _ TRUE] RETURNS [ allOnList: BOOL _ TRUE, countReturned: INT _ 1, circularObjects: LIST OF REF _ NIL ] = {
putAREF: PROC [itemToPut: REF, ItemTV: AMTypes.TV] RETURNS [tooMany: BOOL _ FALSE] = {
isADup: PROC [itemREF: REF] RETURNS [dup: BOOL _ FALSE] = {
FOR l: LIST OF REF _ circularObjects, l.rest UNTIL l = NIL DO
IF l.first = itemREF THEN RETURN[TRUE];
ENDLOOP;
};
IF ~isADup[itemToPut] AND ~AMTypes.IsNil[ItemTV] THEN {
IF countReturned >= nObjects THEN RETURN[TRUE];
lastItem.rest _ CONS[itemToPut, NIL];
lastItem _ lastItem.rest;
countReturned _ countReturned + 1;
};
};
putList: PROC [node: AMTypes.TV] RETURNS [tooMany: BOOL _ FALSE] = {
WHILE node # NIL DO 
elem: AMTypes.TV;
elemREF: REF;
elemLC: LONG CARDINAL;
elem _ AMTypes.IndexToTV[node, 2];
IF node = NIL THEN EXIT; 
IF reportRopes OR AMTypes.TVType[elem] # ropeRepType THEN {
elemLC _ AMBridge.TVToLC[elem];
elemREF _ LOOPHOLE[elemLC];
IF putAREF[elemREF, elem] THEN RETURN[TRUE];
};
node _ AMTypes.Referent[AMTypes.IndexToTV[node, 2]];
ENDLOOP; 
};
doRecord: PROC [recordTV: AMTypes.TV] RETURNS [tooMany: BOOL _ FALSE] = {
currentType: SafeStorage.Type;
underClassCurrentType: AMTypes.Class;
currentType _ AMTypes.TVType[recordTV];
underClassCurrentType _ AMTypes.UnderClass[currentType];
IF underClassCurrentType = record OR underClassCurrentType = structure THEN {
components: AMTypes.Index;
components _ AMTypes.NComponents[currentType];
FOR index: AMTypes.Index IN  [1..components] DO
underTypeAndClass: PROC [type: Type] RETURNS [under: Type, class: AMTypes.Class] = {
under _ type;
WHILE (class _ AMTypes.TypeClass[under]) = definition DO
under _ AMTypes.UnderType[under];
ENDLOOP;
};
refIsOK: BOOL _ TRUE;
itemTV: AMTypes.TV;
itemType: SafeStorage.Type;
itemUnderType: SafeStorage.Type;
itemClass: AMTypes.Class;
itemREF: REF;
itemTV _ AMTypes.IndexToTV[recordTV, index];
itemType _ AMTypes.TVType[itemTV];
[itemUnderType, itemClass] _ underTypeAndClass[itemType];
SELECT itemClass FROM
ref => {
itemLC: LONG CARDINAL;
IF ~reportRopes AND itemType = ropeRepType THEN LOOP;
itemLC _ AMBridge.TVToLC[itemTV];
IF refIsOK THEN {
itemREF _ LOOPHOLE[itemLC];
IF putAREF[itemREF, itemTV] THEN RETURN[TRUE];
};
};
list => {
IF AMTypes.IsNil[itemTV] THEN LOOP;
IF putList[AMTypes.Referent[itemTV]] THEN RETURN [TRUE];
};
union => {
IF index = components THEN {
IF ~AMTypes.IsOverlaid[itemUnderType] AND ~AMTypes.IsComputed[itemUnderType] THEN {
variantTV: AMTypes.TV;
variantTV _ AMTypes.Variant[itemTV];
IF doRecord[variantTV] THEN RETURN [TRUE];
};
};
};
ENDCASE;
ENDLOOP;
};
};
lastItem: LIST OF REF _ NIL;
currentItem: LIST OF REF _ NIL;
circularObjects _ CONS[rootObject, NIL];
lastItem _ circularObjects;
ropeRepType _ CODE[Rope.RopeRep];
currentItem _ circularObjects;
WHILE currentItem # NIL DO
currentTV: AMTypes.TV;
currentType: SafeStorage.Type;
skipThisOne: BOOL _ FALSE;
underClassCurrentType: AMTypes.Class;
currentTV _ AMBridge.TVForReferent[ref: currentItem.first ! AMTypes.Error => {skipThisOne _ TRUE; CONTINUE;}];  -- error on ATOMs and ROPEs
IF ~skipThisOne THEN {
currentType _ AMTypes.TVType[currentTV];
underClassCurrentType _ AMTypes.UnderClass[currentType];
IF underClassCurrentType = record OR underClassCurrentType = structure THEN {
IF doRecord[currentTV] THEN RETURN[FALSE, countReturned, circularObjects];
};
};
currentItem _ currentItem.rest;
ENDLOOP;
};

ActuallyDoIt: PROC [ignoreStack: BOOL _ FALSE] = {
clearRC: PROC [nhp: NHeaderP] = {
objectsSeen _ objectsSeen + 1;
nhp.inZCT _ FALSE;
nhp.maybeOnStack _ FALSE;
nhp.refCount _ 0;
nhp.rcOverflowed _ FALSE;
};
objectsSeen _ 0;
objectsKept _ objectsReclaimed _ 0;
nRCGlobalFrames _ nGlobalFrames _ nLocalFrames _ 0;
nRetainedObjects _ 0;
nextRpaIndex _ 0;

nRefsPushed _ 0;
ZCT.zct.bsiToFreeList _ ALL[NIL];
AllocatorOps.Reset[];
ZCT.zct.markingDecrements _ FALSE;
ZCT.zct.rp
_ ZCT.zct.wp
_ ZCT.zct.rp
- Basics.BITAND[
Basics.LowHalf[LOOPHOLE[ZCT.zct.rp, CARD]],
ZCT.zctBlockWords-1
];

ZCT.RCOvReset[];
AllObjects[clearRC];
IF NOT ignoreStack THEN RTFrameHeapSnapshot.MapUncountedBodies[TraceLocalFrame];
[] _ LoadState.local.EnumerateAllModules[order: newestFirst, proc: TraceGlobalFrame];
UNTIL refStackChain = NIL DO
TraceRefsInObject[LOOPHOLE[PopRef[], REF]]
ENDLOOP;

FreeRefStacks[];
AllObjects[visitOneObject];
IF objectsReclaimed + objectsKept # objectsSeen THEN ERROR;
};

DoTraceAndSweepCollection: PROC = {
haveAllocatorLocked: PROC = {
haveRCOvLocked: PROC = {
haveZCTLocked: PROC = {
RTFrameHeapSnapshot.AcquireFrameHeapSnapshot[];
{ ENABLE UNWIND => RTFrameHeapSnapshot.ReleaseFrameHeapSnapshot[];
ActuallyDoIt[ignoreStack: FALSE];
IF destructiveTestEnabled THEN {
ActuallyDoIt[ignoreStack: TRUE];
DebuggerSwap.CallDebugger["destructive collection finished."];
};
RTFrameHeapSnapshot.ReleaseFrameHeapSnapshot[];
};
};
ZCT.EnterAndCallBack[haveZCTLocked];
};
ZCT.EnterRCOvAndCallBack[haveRCOvLocked];
};
LoadState.local.Acquire[exclusive];
AllocatorOps.EnterAndCallBack[haveAllocatorLocked ! UNWIND => LoadState.local.Release[]];
LoadState.local.Release[];
};

visitOneObject: PROC [nhp: NHeaderP] = {
dummy: REF _ NIL;
ref: REF = AllocatorOps.NHPToREF[nhp];
bumpRC: PROC [] = {
RCMicrocodeOps.ASSIGNREF[rhs: ref, lhs: @dummy
! RCMicrocodeOps.RCOverflowOccurred => {
ZCT.InnerHandleRCOverflow[ref]; RETRY};
];
dummy _ NIL;
};
header: Allocator.NormalHeader _ nhp^;
IF findingCircularGarbage AND nhp.type = listOfGFContextRecType THEN {
bumpRC[];
header _ nhp^;
};
SELECT TRUE FROM
NOT header.f AND NOT header.inZCT => {
IF findingCircularGarbage AND nhp.type # nullType THEN {
objectsGarbage _ objectsGarbage + 1;
bumpRC[];
bumpRC[];
bumpRC[];
bumpRC[];
IF nhp.type # typedVariableType AND nhp.type # listOfGFContextRecType AND (nhp.type # ropeRepType OR rememberRopes) THEN {
IF circularGarbageSeq.put < circularGarbageSeq.max THEN {
circularGarbageSeq[circularGarbageSeq.put] _ nhp;
circularGarbageSeq.put _ circularGarbageSeq.put + 1;
};
};
header _ nhp^;
}
 ELSE {
objectsReclaimed _ objectsReclaimed + 1;
AllocatorOps.TAndSFreeObject[nhp];
RETURN;
};
};
header.f => {
packageCount: NAT _ RTTypesBasicPrivate.NumberPackageRefs[nhp.type];
dummy: REF _ AllocatorOps.NHPToREF[nhp];
FOR i: CARDINAL IN [1..packageCount] DO
IF nhp.refCount = 0 AND NOT nhp.rcOverflowed THEN {
IF forgivingLog = NIL THEN
forgivingLog _ VM.AddressForPageNumber[VM.SimpleAllocate[ForgivingLogPages].page];
forgivingLog[forgivingLogIndex] _ ForgivingLogEntry[nhp, header];
forgivingLogCount _ forgivingLogCount + 1;
IF NOT forgiving THEN DebuggerSwap.CallDebugger["Unforgivable!"L];
IF forgivingLogIndex = ForgivingLogEntries-1
THEN forgivingLogIndex _ 0
ELSE forgivingLogIndex _ forgivingLogIndex + 1;
EXIT;
};
RCMicrocodeOps.ASSIGNREF[rhs: NIL, lhs: @dummy
! RCMicrocodeOps.RCUnderflowOccurred => {
ZCT.InnerHandleRCUnderflow[dummy]; RETRY}];
ENDLOOP;
header _ nhp^;
};
ENDCASE;


objectsKept _ objectsKept + 1; 
nhp.inZCT _ FALSE;
IF header.refCount = 0 AND NOT header.rcOverflowed THEN {
IF NOT header.f THEN {
rpa[nextRpaIndex] _ LOOPHOLE[AllocatorOps.NHPToREF[nhp], LONG POINTER];
IF nextRpaIndex < maxNRPIndex THEN nextRpaIndex _ nextRpaIndex + 1;
nRetainedObjects _ nRetainedObjects + 1;
};
RCMicrocodeOps.OnZ[nhp
! RCMicrocodeOps.ZCTFull => DebuggerSwap.CallDebugger["TAndS disaster."]];
};
};

TraceLocalFrame: PROC [d: LONG DESCRIPTOR FOR ARRAY OF WORD] = {
pa: LONG POINTER TO LONG POINTER
= LOOPHOLE[BASE[d], LONG POINTER TO LONG POINTER];
nWords: CARDINAL = LENGTH[d];
nLocalFrames _ nLocalFrames + 1; 
IF nWords >= SIZE[REF] THEN 
FOR i: CARDINAL IN [0..nWords-SIZE[REF]] DO
addr: LONG POINTER = (pa+i)^;
IF addr # NIL AND AllocatorOps.IsValidRef[addr] THEN {
ref: REF = LOOPHOLE[addr, REF];
nhp: Allocator.NHeaderP _ AllocatorOps.REFToNHP[ref];
IF suspectRef # NIL AND addr = suspectRef THEN
suspectRefFoundInLocalFrame _ TRUE;
IF NOT nhp.inZCT THEN {
nhp.inZCT _ TRUE;
IF RTTypesBasicPrivate.MapTiRcmx[SafeStorage.GetReferentType[ref]] # RCMap.nullIndex THEN PushRef[LOOPHOLE[ref, LONG POINTER]];
};
}; 
ENDLOOP;
}; 

TraceGlobalFrame: PROC [configID: LoadState.ConfigID, moduleIndex: LoadState.ModuleIndex] RETURNS [stop: BOOL _ FALSE] = {
gfh: PrincOps.GlobalFrameHandle
= LoadState.local.ModuleToGlobalFrame[configID, moduleIndex];
type: Type _ LoadState.local.GlobalFrameToType[gfh];
procRef: PROC [ref: REF] = {
SELECT LOOPHOLE[ref, LONG POINTER] FROM
NIL => RETURN;
suspectRef => gfhToSuspectRef _ gfh;
ENDCASE;
{
nhp: Allocator.NHeaderP _ AllocatorOps.REFToNHP[ref];
dummy: REF _ NIL;
IF NOT nhp.inZCT THEN {
nhp.inZCT _ TRUE;
IF RTTypesBasicPrivate.MapTiRcmx[SafeStorage.GetReferentType[ref]] # RCMap.nullIndex THEN PushRef[LOOPHOLE[ref, LONG POINTER]];
};
RCMicrocodeOps.ASSIGNREF[rhs: ref, lhs: @dummy
! RCMicrocodeOps.RCOverflowOccurred => {
ZCT.InnerHandleRCOverflow[ref]; RETRY};
];
};
};
nGlobalFrames _ nGlobalFrames + 1;
IF type # nullType THEN {
nRCGlobalFrames _ nRCGlobalFrames + 1;
RTTypesBasicPrivate.MapRefs[LONG[gfh], RTTypesBasicPrivate.MapTiRcmx[type], procRef];
};
RETURN[FALSE];
};

TraceRefsInObject: PROC [container: REF] = {
type: Type _ SafeStorage.GetReferentType[container]; 
refererPushed: BOOL _ FALSE; 
procRef: PROC [ref: REF] = {
SELECT LOOPHOLE[ref, LONG POINTER] FROM
NIL => RETURN;
suspectRef => IF NOT refererPushed THEN {
nhp: NHeaderP = AllocatorOps.REFToNHP[container];
refererPushed _ TRUE;
IF nSuspectReferers < maxNReferers THEN {
suspectReferers[nSuspectReferers] _ nhp;
nSuspectReferers _ nSuspectReferers + 1;
};
FOR i: NAT IN [0..nInnerReferers) DO
IF nhp = innerReferers[i] THEN GO TO circular;
ENDLOOP;
IF NOT circularStructureFound AND nInnerReferers < maxNInnerReferers THEN {
innerReferers[nInnerReferers] _ nhp;
nInnerReferers _ nInnerReferers + 1;
};
EXITS circular => circularStructureFound _ TRUE;
};
ENDCASE;
{
nhp: Allocator.NHeaderP _ AllocatorOps.REFToNHP[ref];
dummy: REF _ NIL;
IF NOT nhp.inZCT THEN {
nhp.inZCT _ TRUE;
IF RTTypesBasicPrivate.MapTiRcmx[SafeStorage.GetReferentType[ref]] # RCMap.nullIndex THEN PushRef[LOOPHOLE[ref, LONG POINTER]];
};
RCMicrocodeOps.ASSIGNREF[rhs: ref, lhs: @dummy
! RCMicrocodeOps.RCOverflowOccurred => {
ZCT.InnerHandleRCOverflow[ref]; RETRY};
];
};
};
DO
oldNRefsPushed: INT = nRefsPushed; 
RTTypesBasicPrivate.MapRefs[
LOOPHOLE[container, LONG POINTER],
RTTypesBasicPrivate.MapTiRcmx[type],
procRef];
IF nRefsPushed-oldNRefsPushed # 1 THEN RETURN;
container _ LOOPHOLE[PopRef[], REF];
type _ SafeStorage.GetReferentType[container];
refererPushed _ FALSE;
ENDLOOP;
}; 

AllObjects: PROC [visit: PROC [NHeaderP]] = {
qi: QuantumIndex _ FIRST[QuantumIndex];
DO
hp: HeaderP;
blockSize: INT _ 0;
UNTIL AllocatorOps.quantumMap[qi] DO
IF qi = LAST[QuantumIndex] THEN RETURN;
qi _ qi+1;
ENDLOOP;
FOR hp _ QuantumIndexToLP[qi], hp + blockSize
WHILE LOOPHOLE[hp, CARD] < LastAddress
AND AllocatorOps.quantumMap[LPToQuantumIndex[hp]] DO
nhp: NHeaderP _ LOOPHOLE[hp];
IF nhp.blockSizeIndex = bsiEscape THEN
nhp _ nhp + (SIZE[ExtendedHeader] - SIZE[NormalHeader]);
blockSize _ AllocatorOps.BlockSize[hp];
visit[nhp];
ENDLOOP;
IF LOOPHOLE[hp, CARD] >= LastAddress THEN RETURN;
qi _ LPToQuantumIndex[hp];
ENDLOOP;
};

logWordsPerQuantum: NAT = PrincOps.logWordsPerPage+Allocator.logPagesPerQuantum;

LPToQuantumIndex: PROC [lp: LONG POINTER] RETURNS [QuantumIndex] = INLINE {
RETURN[AllocatorOps.AddressToQuantumIndex[LOOPHOLE[lp]]];
};

QuantumIndexToLP: PROC [qi: QuantumIndex] RETURNS [LONG POINTER] = INLINE {
RETURN [Basics.DoubleShiftLeft[ [pair[lo: qi, hi: 0]], logWordsPerQuantum].lp ];
};

PushRef: PROC [pref: LONG POINTER] = {
stack: RefStack _ refStackChain;
IF stack = NIL OR stack.size = stack.max THEN { 
IF refStackFree = NIL 
THEN {
stack _ VM.AddressForPageNumber[VM.SimpleAllocate[RefStackPages].page];
stack.next _ NIL; 
stack.size _ 0; 
stack.max _ RefStackMax;
} 
ELSE {
stack _ refStackFree; 
refStackFree _ stack.next;
}; 
stack.next _ refStackChain; 
refStackChain _ stack;
}; 
stack[stack.size] _ pref; 
stack.size _ stack.size + 1;
nRefsPushed _ nRefsPushed + 1;
}; 

PopRef: PROC RETURNS [pref: LONG POINTER] = {
stack: RefStack _ refStackChain;
IF stack # NIL THEN { 
size: CARDINAL _ stack.size; 
IF size = 0 THEN { 
refStackChain _ stack.next; 
stack.next _ refStackFree; 
refStackFree _ stack; 
IF (stack _ refStackChain) = NIL THEN RETURN [NIL]; 
IF (size _ stack.size) = 0 THEN ERROR;
}; 
size _ size - 1; 
stack.size _ size; 
RETURN [stack[size]];
}; 
RETURN [NIL];
}; 

FreeRefStacks: PROC = {
IF refStackChain # NIL THEN ERROR; -- should never happen, but check anyway
WHILE refStackFree # NIL DO
stack: RefStack _ refStackFree.next;
VM.Free[[page: VM.PageNumberForAddress[refStackFree], count: RefStackPages]];
refStackFree _ stack
ENDLOOP;
}; 


Collector.EstablishTAndSProc[DoTraceAndSweepCollection];

END.

CircularGarbageTraceAndSweepImpl.mesa
Copyright c 1985 by Xerox Corporation.  All rights reserved.
Russ Atkinson (RRA) June 24, 1985 3:21:02 pm PDT
Bob Hagmann August 13, 1985 1:14:16 pm PDT
This module implements a trace-and-sweep garbage collector for Cedar ("DoTraceAndSweepCollection").  It uses auxilliary storage for a reference stack.  To allow subsequent incremental collection, DoTraceAndSweepCollection restores reference counts to correct values.  No collectible storage is allocated while DoTraceAndSweepCollection is active, nor are any REFs change in counted storage during that time.  Client processes that attempt to do so are suspended until after DoTraceAndSweepCollection finishes.
Variables
number of objects retained only because REFs appear onstack
destructiveTestEnabled TRUE => do a second TandS without the stack scan, then punt
findingCircularGarbage TRUE => remember stuff found; don't reclaim it
interesting statistics   
debugging aids
IF TRUE, then logs finalizable objects with counts that are too small
IF FALSE, then crashes for finalizable objects with counts that are too small
ForgivingLog declarations
TYPEs and constants
Leave room for the header info
support for WhoPointsTo and FindCircularGarbage
PROCS
Look up the referer chain. Stop if a gfh found, or if foundInLocalFrame, or if a loop is found, or if more than 1 referer is found, or if no referers are found (changed conserv scan)

This procedure first does a standard incremental collection.  Then it goes thru the motions of a TandS, but does not reclaim any garbage. Instead, it records the Types in a list.  Do not do two of these at once!!
This procedure first does a standard incremental collection.  Then it goes thru the motions of a TandS, but does not reclaim any garbage. Instead, it records the REFs in a list.  Do not do two of these at once!!
This procedure takes the rootObject, and find all object that it recursively points to.
itemREF _ AMBridge.RefFromTV[itemTV ! AMTypes.Error => {refIsOK _ FALSE; CONTINUE;}];
Leave the f flag and the type field alone

Initialize
Clear all free lists
Clear the zero-count table
mask rp by (LastAddress-(zctBlockWords-1))
Clear all ref counts and count objects
trace from all local and global frames in the world    
continue marking from the ref stack and from objects

Free the objects
Reclaim unmarked and free stuff, rebuild the zct and remember retained stuff due to frame heap only
here with the loader and allocator locked
here with the loader, allocator and RCOvBank locked
here with the loader, allocator, RCOvBank and ZCT locked
START haveRCOvLocked HERE
Acquire the lock on the ref counting machinery, do the work, then release the lock.
START haveAllocatorLocked HERE
Acquire the lock on the RCOverflowBank, do the work, then release the lock.

START DoTraceAndSweepCollection HERE
First, acquire the lock on the loader (REFs in GF's are counted)
Next, acquire the lock on the allocator, do the work, then release the lock.
Release the loader's lock
Reclaim unmarked and free stuff, rebuild the zct and remember retained stuff due to only frame heap
This sample is useful for debugging
``LIST OF AMModelContextImpl.GFContextRec'' have some problem, probably due to some unsafety in the interpreter.  Bump the reference count to avoid it.
This one is NOT being retained (and has no finalization) unless we are finding circular garbage
Resample to make it all consistent
This object has finalization enabled, so adjust refCount to reflect the package count.
RRA: We are trying to decrement a reference count for a finalizable object that already has a reference count of 0.  The most likely cause of this is that a permanent reference is not being maintained to the object.  If only a circularity is holding the count high, then this bug may ONLY surface during trace and sweep.  We keep a log of this stuff to allow the world to continue.  If we are not forgiving this fault we crash and burn immediately.
Decrement the reference count
Resample to make it all consistent
At this point we keep the object in play
The reference count is 0.
put it on zct
this procedure is used to mark refs in a local frame; RCs must be decremented on first encounter
if this REF is valid, non-NIL
this REF is valid and not seen before
this procedure is used to mark refs from a global frame
the algorithm is essentially the same as for regular objects
Mark the object as being seen.
this REF is valid and not seen before
Increment the reference count
applies P to each reference in the indicated object (ref)
Mark the object as being seen.
this REF is valid and not seen before
Increment the reference count
this proc visits all collectible objects (free AND allocated)
Find the beginning of the next run of quanta from the quantum map
Start parsing at the beginning of this run
The shift distance = Log2[wordsPerPage*pagesPerQuantum]
pushes ref to object onto the reference stack
time to get a new stack node
oh well, nothing comes for free
pops ref to object from the reference stack
START TraceAndSweepImpl HERE
Bob Hagmann July 11, 1985 7:45:30 am PDT
changes to: DIRECTORY, InitFindCircularGarbage, FindCircularGarbageTypes, FindCircularGarbage
Bob Hagmann July 29, 1985 2:54:34 pm PDT
Ignore LIST OF AMModelContextImpl.GFContextRec
changes to: InitFindCircularGarbage, visitOneObject

Bob Hagmann July 30, 1985 12:51:07 pm PDT
changes to: bumpRC (local of visitOneObject), visitOneObject
Bob Hagmann August 9, 1985 5:18:41 pm PDT
changes to: CircularGarbageTraceAndSweepImpl, InitFindCircularGarbage, FindCircularGarbageTypes, FindCircularGarbage, visitOneObject, DIRECTORY

Bob Hagmann August 12, 1985 9:32:55 am PDT
changes to: DIRECTORY, FindCircularStructure, WhoPointsToRef
Bob Hagmann August 13, 1985 1:07:40 pm PDT
added lists and sequences to FindCircularStructure, and renamed FindCircularStructure to FindConnectedComponent

Κ˜
codeš
œ%™%Kšœ
Οm
œ1™<K™0K™*—K˜Kš
œύ™ύK˜š
Οk	˜	Kšœ
žœ~˜
Kšœ
žœz˜Œ
Kšœ	žœ˜'Kšœžœ˜(Kšœžœ
˜œ
Kšœžœžœžœ˜6Kš
œ;˜;Kšœ
žœ˜%Kšœ
žœ˜"Kšœžœ˜Kšœ
žœo˜~Kšœ	žœ4˜BKšœžœ˜#Kšœžœ
˜Kšœžœž	œ9˜XKšœžœ˜KšœžœJ˜cKšœžœ)˜BKšœžœ˜(KšœžœT˜eKšœžœ˜%Kšžœ
žœD˜LKšžœ
žœx˜
K˜—šœ"ž˜)Kšžœ±
žœž˜Α
Kšžœ˜$Kšžœ˜Kšœžœ
žœ˜K˜Kšžœžœ
žœ
˜šœžœ˜Kš
œ&˜&—K˜š
œ	™	K˜šœžœ˜Kš
œ;™;—Kš
œžœžœ
žœ
žœžœ
žœ˜7Kšœ
žœ˜Kšœžœ˜K˜šœžœžœ˜&Kšœžœ7™R—šœžœžœ˜&Kšœžœ*™E—šœžœžœ
˜%Kšœžœ˜
Kšœžœ˜
Kšœžœžœ
žœ	˜)K˜—Kš	œžœ
žœ
žœžœ
˜@Kš
œ˜Kš
œ˜š
œ˜K˜—Kšœžœ˜Kšœžœ
˜Kšœ
žœ˜Kšœžœ
˜K˜—š
œ™Kšœ
žœ˜Kšœžœ˜Kšœ
žœ˜Kšœžœ˜Kšœžœ˜Kšœžœ˜Kšœžœ˜K˜—š
œ™K˜Kšœ
žœžœ˜Kš
œ	žœ
žœ
žœ
žœžœ
žœ˜:šœžœžœ
˜Kšžœ
žœ>™EKšžœ
žœE™M—Kšœžœ
˜!Kšœžœ˜Kš
œ0˜0K˜š
œ™Kšœžœ˜Kš	œžœžœ
žœ
žœ˜5Kšœžœžœžœ˜Lšœžœžœ˜"Kš
œ˜Kš
œ˜K˜—Kšœžœ-žœ˜]K˜——š
œ™K˜šœ
žœžœ˜Kšœžœ˜Kšœžœ˜Kšœžœ˜Kšœžœ
žœ
žœ
žœ
žœ
ž˜0Kš
œ˜—š	œ
žœžœ
žœ
žœ
˜-Kšœžœ˜šœ
žœ+žœžœ
žœ
žœ˜fKš
œ™——K˜Kš
œ/™/Kšœžœ
žœžœΟc˜4K˜Kšœ	žœ(˜5Kš	œžœžœžœ
žœ˜7Kšœžœ.˜?Kšœžœ˜K˜Kšœ
žœžœžœ
˜:Kš	œžœžœžœ
žœ˜7Kšœžœ˜Kšœžœ˜K˜Kšœ.žœ
˜2Kšœžœžœ
˜*Kšœžœžœ
˜%K˜——š
œ™K˜šΟnœžœ
žœžœ
žœžœ˜CKšžœ˜#K˜K˜—š œžœ
žœžœ
žœ
žœ˜CKšžœ˜#K˜K˜—š œžœ
žœžœžœžœ
žœ
žœ
žœžœPžœ
žœ	˜Μ
Kš
œ˜Kš
œ˜Kš
œ!˜!Kš
œk˜kšžœžœ
žœž˜&Kšžœžœ
žœ
žœ
˜*Kšœžœ:˜IKš
œ"˜"Kšžœ
˜—Kšžœ˜K˜K˜—š œžœžœžœ
žœXžœ
žœ	˜Θ
Kš
œΆ
™Ά
Kšžœžœ
žœžœžœ
žœ
˜DKš
œ˜K˜K˜Kšžœžœ
žœžœžœ
žœ
˜GK˜K˜Kšœžœ
˜Kšœžœ
˜$Kšœžœ
˜K˜šžœžœ
žœžœžœžœžœžœ
˜Ÿ
Kšœ
žœ,žœ
žœ˜OKšžœžœ
žœžœžœ
žœ
˜DK˜Kšœ1žœžœ˜LK˜Kšžœ
˜—Kšœ
žœ
˜šžœ
˜Kš
œ˜K˜K˜/K˜1K˜—K˜K™—š œžœžœ	ž	œ
žœ
žœ˜`Kšœžœ˜Kšœžœ˜Kšœžœžœ
žœ˜$šžœžœCž˜cKšœ1žœ˜7Kš
œG˜GKš
œ(˜(Kš
œ(˜(K˜$Kšžœ
˜—Kšœžœ
˜Kš
œ˜Kš
œ˜Kšœžœ"˜:Kš	œžœžœ/žœ
žœ#˜~Kšœžœ˜!Kšœžœ"˜@Kš
œ"˜"Kšœ1žœžœ˜LK˜K˜—š œžœž
œ
žœžœžœžœžœ
žœžœ˜•
Kš
œΤ
™Τ
Kšœž	œ
žœ"˜7Kš
œV˜Všžœžœ#žœž˜DKšœ
žœ,˜:Kšœžœ
˜"Kšžœ
˜—Kšœžœ˜ Kšœžœ
˜Kšœžœ
˜Kš
œ˜Kš
œ˜K˜K˜—š œžœž
œ
žœžœžœžœžœ
žœ
žœžœ˜
Kš
œΣ
™Σ
Kšœž	œ
žœ"˜7Kš
œV˜Všžœžœ#žœž˜DKšœ
žœ>˜LKšœžœ
˜"Kšžœ
˜—Kšœžœ˜ Kšœžœ
˜Kšœžœ
˜Kš
œ˜Kš
œ˜K˜K˜—š  œžœ
žœžœ
žœžœžœžœžœžœžœžœžœ
žœ
žœžœ˜Κ
Kš
œW™WšΟbœžœ
žœžœžœžœžœ˜Všœžœžœžœžœžœ˜;š
žœžœ
žœ
žœžœžœ
ž˜=Kšžœžœ
žœ
žœ˜'Kšžœ
˜—K˜—šžœžœžœ˜7Kšžœžœ
žœ
žœ˜/Kšœžœžœ˜%Kš
œ˜Kš
œ"˜"K˜—K˜—š‘œžœžœžœžœžœ˜Dšžœžœ
žœ
˜Kšœ
žœ
˜Kšœ	žœ
˜
Kšœžœ
žœ
˜Kš
œ"˜"Kšžœžœ
žœ
žœ˜šžœ
žœ$žœ˜;Kš
œ˜Kšœ
žœ	˜Kšžœžœ
žœ
žœ˜,K˜—K˜4Kšžœ˜	—Kš
œ˜—š‘œžœžœžœžœžœ˜IKš
œ˜Kš
œ%˜%Kš
œ'˜'Kš
œ8˜8šžœ žœ#žœ˜MKš
œ˜Kš
œ.˜.šžœžœž˜/šœžœžœ(˜TK˜
šžœ1ž˜8K˜!Kšžœ
˜—K˜—Kšœ	žœžœ
˜Kšœžœ
˜Kš
œ˜Kš
œ ˜ Kš
œ˜Kšœ	žœ
˜
Kš
œ,˜,Kš
œ"˜"Kš
œ9˜9šžœž˜š
œ˜Kšœžœ
žœ
˜Kšžœžœžœ
žœ
˜5Kš
œ!˜!KšœBžœžœ™Ušžœ	žœ˜Kšœ
žœ	˜Kšžœžœ
žœ
žœ˜.K˜—K˜—š
œ	˜	Kšžœžœ
žœ
˜#Kšœ%žœ
žœžœ˜8Kš
œ˜—š
œ
˜
šžœžœ˜šžœ$žœ$žœ˜SKšœžœ
˜Kš
œ$˜$Kšžœžœ
žœžœ˜*K˜—K˜—K˜—Kšžœ
˜—Kšžœ
˜—K˜—K˜—Kš	œ
žœ
žœ
žœžœ
˜Kš	œ
žœ
žœ
žœžœ
˜Kšœžœ
žœ˜(Kš
œ˜Kšœžœ˜!Kš
œ˜šžœžœ
ž˜Kšœžœ
˜Kš
œ˜Kšœ
žœžœ
˜Kš
œ%˜%Kšœ\žœžœŸ˜‹
šžœžœ˜Kš
œ(˜(Kš
œ8˜8šžœ žœ#žœ˜MKšžœžœ
žœ
žœ"˜JK˜—K˜—Kš
œ˜Kšžœ
˜—K˜K˜—š œžœžœžœ˜2š‘œžœ˜!Kš
œ˜Kšœžœ
˜Kšœžœ
˜Kš
œ)™)Kš
œ˜Kšœžœ
˜Kš
œ˜K™—Kš
œ
™
Kš
œ˜Kš
œ#˜#Kš
œ3˜3K˜K˜K˜˜Kš
œ™—Kšžœžœ
žœ˜!š
œ˜Kš
œ™—Kšžœžœ
˜"šžœ˜
Kšœžœ˜šœžœ˜šœ	žœ
˜Kšœžœ
žœ	žœ˜+Kšžœ˜Kš
œ˜——Kš
œ*™*—K˜Kš
œ&™&Kšžœ
˜š
œ˜Kš
œ7™7—Kšžœ
žœ
žœ9˜Pš
œU˜UKš
œ4™4—šžœžœ
ž˜Kšœžœžœ˜*Kšžœ
˜K˜—K˜K™š
œ™K™c—Kš
œ˜Kšžœ.žœ
žœ
˜;Kš
œ˜K˜—š œžœ˜#š‘œžœ˜Kš
œ)™)š‘œžœ˜Kš
œ3™3š‘
œžœ˜Kš
œ8™8Kš
œ/˜/šœžœ
žœ3˜BKšœžœ˜!šžœžœ˜ Kšœžœ˜ K˜>Kš
œ˜—K˜/K˜—K˜—šžœž™Kš
œS™S—Kšžœ!˜$K˜—šžœž™Kš
œK™K—Kšžœ&˜)Kš
œ˜—K™šžœž™$Kš
œ@™@—š
œ#˜#Kš
œL™L—šœ4žœ˜YKš
œ™—Kš
œ˜Kš
œ˜K˜—š‘œžœ˜(K™cKšœžœžœ
˜Kšœžœ˜&šœžœ˜šœž	œ˜.š
œ(˜(Kšžœžœ˜'—Kš
œ˜—Kšœžœ
˜K˜—š
œ&˜&Kš
œ#™#—šžœžœ#žœ˜FKš
œ—
™—
Kš
œ	˜	Kš
œ˜Kš
œ˜—šžœ
žœ
ž˜šžœ
žœ
žœ˜&Kš
œ_™_šžœžœžœ˜8Kš
œ$˜$Kš
œ	˜	Kš
œ	˜	Kš
œ	˜	Kš
œ	˜	š
žœžœ#žœžœžœ˜zšžœ1žœ˜9Kš
œ1˜1Kš
œ4˜4K˜—K˜—š
œ˜Kš
œ"™"—K˜
šœ
žœ˜Kš
œ(˜(Kš
œ"˜"Kšžœ
˜Kš
œ˜——K˜—š
œ
˜
Kš
œV™VKšœžœ3˜DKšœžœ˜(šžœžœ
žœž˜'šžœžœ
žœžœ˜3Kšžœ™žœ 
™ΐšžœžœ
ž˜Kšœžœžœ)˜R—Kš
œA˜AKš
œ*˜*Kšžœ
žœžœ-˜Bšžœ*˜,Kšžœ˜Kšžœ+˜/—Kšžœ
˜K˜—Kš
œ™šœž	œžœ
˜.š
œ)˜)Kšžœ žœ˜+——Kšžœ
˜—š
œ˜Kš
œ"™"—K˜—Kšžœ
˜K˜—Kš
œ(™(K˜Kš
œ˜Kšœžœ
˜šžœžœ
žœžœ˜9Kš
œ™šžœ
žœ
žœ˜Kšœžœžœ
žœ˜GKšžœžœ!˜CK˜(K˜—K™
š
œ˜Kš
œJ˜J—Kš
œ˜—K˜K˜—š œžœžœ
ž
œ
žœ
žœ
žœ
žœ˜@Kš
œ`™`Kšœžœ
žœ
žœ
žœ
žœžœ
žœžœ
žœ
žœ
žœ
žœ˜SKšœžœžœ˜Kš
œ!˜!šžœžœ
žœžœ
˜šžœžœ
žœžœ
žœž˜+Kšœžœ
žœ˜šžœžœ
žœžœ˜6Kš
œ™Kšœžœžœžœ˜Kš
œ5˜5šžœžœ
žœž˜.Kšœžœ
˜#—šžœ
žœžœ˜Kš
œ%™%Kšœžœ
˜Kš
žœSžœ	žœžœ
žœ˜K˜—K˜—Kšžœ
˜——š
œ˜K˜——š
 œžœDžœžœžœ˜zKš
œ]˜]Kš
œ7™7Kš
œ<™<Kš
œ4˜4šœ	žœžœ˜š	žœ
žœžœ
žœž˜'Kšžœžœ
˜Kš
œ$˜$Kšžœ
˜—˜
Kš
œ™Kš
œ5˜5Kšœžœžœ
˜šžœ
žœžœ˜Kš
œ%™%Kšœžœ
˜Kš
žœSžœ	žœžœ
žœ˜K˜—Kš
œ™šœž	œ˜.š
œ(˜(Kšžœžœ˜'—Kš
œ˜—K˜—K˜—Kš
œ"˜"šžœžœ˜Kš
œ&˜&Kšœžœ5˜UK˜—Kšžœ
žœ˜Kš
œ˜K˜—š œžœ
žœ˜,Kš
œ9™9Kš
œ5˜5Kšœžœžœ˜šœ	žœžœ˜š	žœ
žœžœ
žœž˜'Kšžœžœ
˜šœžœ
žœžœ˜)Kš
œ1˜1Kšœžœ
˜šžœ!žœ˜)Kš
œ(˜(K˜(K˜—šžœžœ
žœž˜$Kšžœžœ
žœ
žœ
˜.Kšžœ
˜—šžœ
žœžœ$žœ˜KKš
œ$˜$K˜$K˜—Kšžœ&žœ
˜0K˜—Kšžœ
˜—˜
Kš
œ™Kš
œ5˜5Kšœžœžœ
˜šžœ
žœžœ˜Kš
œ%™%Kšœžœ
˜Kš
žœSžœ	žœžœ
žœ˜K˜—Kš
œ™šœž	œ˜.š
œ(˜(Kšžœžœ˜'—Kš
œ˜—K˜—Kš
œ˜—š
ž˜Kšœžœ˜#š
œ˜Kšžœžœ
žœ˜"Kš
œ$˜$Kš
œ	˜	—Kšžœ žœ
žœ
˜.Kšœžœžœ˜$Kš
œ.˜.Kšœžœ
˜Kšžœ
˜—š
œ˜K˜——š 
œžœ	žœ˜-Kš
œ=™=Kšœžœ˜'š
ž˜Kš
œA™AKš
œ˜Kšœžœ˜šžœž˜$Kšžœžœžœ
žœ
˜'Kš
œ
˜
Kšžœ
˜—Kš
œ*™*šžœ*žœ
žœžœžœ.ž˜‰
Kšœžœ˜šžœ ž˜&Kšœ
žœžœ˜8—Kš
œ'˜'Kš
œ˜Kšžœ
˜—Kš
žœ
žœžœžœ
žœ
˜1Kš
œ˜Kšžœ
˜—Kš
œ˜K˜—šœžœ9˜PKš
œ7™7K˜—š œžœžœ
žœžœžœ˜KKšžœ$žœ˜9Kš
œ˜K˜—š œžœžœžœ
žœžœ˜KKšžœJ˜PKš
œ˜K˜—š œžœžœ
žœ˜&Kš
œ-™-K˜ šžœ	žœ
žœžœ˜0Kš
œ™šžœžœ
˜Kš
œ™šžœ˜Kšœžœžœ%˜GKšœ
žœ˜K˜Kš
œ˜Kš
œ˜—šžœ˜Kš
œ˜K˜K˜—K˜K˜—K˜—K˜K˜K˜K˜K˜—š
 œžœ
žœžœ
žœ˜-Kš
œ+™+K˜ šžœ	žœ
žœ˜Kšœžœ˜šžœ
žœ˜K˜K˜K˜Kš
žœžœ
žœ
žœžœ˜4Kšžœžœ
žœ
˜&Kš
œ˜—K˜K˜Kšžœ˜Kš
œ˜—Kšžœžœ˜
Kš
œ˜K˜—š 
œžœ˜Kš	žœžœ
žœ
žœŸ(˜Kšžœžœ
ž˜K˜$Kšžœ
žœ<˜MK˜Kšžœ
˜—š
œ˜K˜——K™K˜Kš
œ8˜8—K˜Kšžœ
˜K˜™(KšœΟrQ™]—™(Kš
œ.™.Kšœ’'™3—K™™)Kšœ’œ’™<—™)Kšœ’ƒ
™
—K™™*Kšœ’0™<—™*Kšœ’œ’œ™o—K™—…—SHˆL