<> <> <> <> DIRECTORY Allocator: TYPE USING [bsiEscape, ExtendedHeader, HeaderP, NHeaderP, QuantumIndex, wordsPerQuantum, LastAddress, NormalHeader], AllocatorOps: TYPE USING [EnterAndCallBack, NHPToREF, REFToNHP, TAndSFreeObject, IsValidRef, quantumMap, Reset, BlockSize], Basics: TYPE USING [BITAND, LowHalf], Collector: TYPE USING [EstablishTAndSProc], DebuggerSwap: TYPE USING [CallDebugger], LoadState: TYPE USING [Acquire, Release, local, EnumerateAllModules, ConfigID, ModuleIndex, ModuleToGlobalFrame, GlobalFrameToType], PrincOps: TYPE USING[GlobalFrameHandle, wordsPerPage], RCMap: TYPE USING [nullIndex], RCMicrocodeOps: TYPE USING [OnZ, ZCTFull, RCOverflowOccurred, RCUnderflowOccurred, ASSIGNREF], RTFrameHeapSnapshot: TYPE USING [AcquireFrameHeapSnapshot, ReleaseFrameHeapSnapshot, MapUncountedBodies], RTTypesBasicPrivate: TYPE USING [MapRefs, MapTiRcmx, NumberPackageRefs], SafeStorage: TYPE USING [nullType, Type, GetReferentType, ReclaimCollectibleObjects], VM: TYPE USING [AddressForPageNumber, Allocate, Interval, Free, PageNumberForAddress], ZCT: TYPE USING [EnterAndCallBack, EnterRCOvAndCallBack, InnerHandleRCOverflow, InnerHandleRCUnderflow, zct, zctBlockWords, RCOvReset]; TraceAndSweepImpl: PROGRAM IMPORTS AllocatorOps, Basics, Collector, DebuggerSwap, LoadState, RCMicrocodeOps, RTFrameHeapSnapshot, RTTypesBasicPrivate, SafeStorage, VM, ZCT = BEGIN OPEN Allocator, AllocatorOps, SafeStorage; <> nRetainedObjects: LONG CARDINAL _ 0; <> rpa: ARRAY [0..maxNRPIndex] OF LONG POINTER _ ALL[NIL]; maxNRPIndex: CARDINAL = 20; nextRpaIndex: CARDINAL _ 0; destructiveTestEnabled: BOOL _ FALSE; < do a second TandS without the stack scan, then punt>> findingCircularGarbage: BOOL _ FALSE; < remember stuff found; don't reclaim it>> refStackChain: RefStack _ NIL; refStackFree: RefStack _ NIL; nRefsPushed: INT _ 0; <> objectsSeen: LONG CARDINAL _ 0; objectsReclaimed: LONG CARDINAL _ 0; objectsKept: LONG CARDINAL _ 0; nGlobalFrames: LONG CARDINAL _ 0; nRCGlobalFrames: LONG CARDINAL _ 0; nLocalFrames: LONG CARDINAL _ 0; <> SuspectSeen: SIGNAL = CODE; suspect: LONG POINTER TO UNSPECIFIED _ LOOPHOLE[LONG[-1]]; <> RefStackRep: TYPE = RECORD [ next: RefStack, size, max: CARDINAL, refs: SEQUENCE COMPUTED CARDINAL OF LONG POINTER ]; RefStack: TYPE = LONG POINTER TO RefStackRep; <> suspectRef: LONG POINTER TO UNSPECIFIED _ NIL; -- a LOOPHOLE'd REF APNodes: TYPE = ARRAY [0..maxNReferers) OF NHeaderP; suspectReferers: REF APNodes _ NEW[APNodes _ ALL[NIL]]; maxNReferers: NAT = 10; 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; <> <> <> WhoPointsTo: 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[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]; }; <<>> <> FindCircularGarbage: PROC = { SafeStorage.ReclaimCollectibleObjects[suspendMe: TRUE]; findingCircularGarbage _ TRUE; SafeStorage.ReclaimCollectibleObjects[suspendMe: TRUE, traceAndSweep: TRUE]; findingCircularGarbage _ FALSE; }; IncRC: PROC [ref: REF] = { dummy: REF _ NIL; RCMicrocodeOps.ASSIGNREF[rhs: ref, lhs: @dummy ! RCMicrocodeOps.RCOverflowOccurred => {ZCT.InnerHandleRCOverflow[ref]; RETRY}; ]; dummy _ NIL; }; DecRC: PROC [ref: REF] = { dummy: REF _ ref; RCMicrocodeOps.ASSIGNREF[rhs: NIL, lhs: @dummy ! RCMicrocodeOps.RCUnderflowOccurred => {ZCT.InnerHandleRCUnderflow[ref]; RETRY}]; dummy _ NIL; }; <> 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, LONG CARDINAL]], ZCT.zctBlockWords-1 ]; <> <> ZCT.RCOvReset[]; AllObjects[clearRC]; <> IF NOT ignoreStack THEN RTFrameHeapSnapshot.MapUncountedBodies[TraceLocalFrame]; [] _ LoadState.local.EnumerateAllModules[order: newestFirst, proc: TraceGlobalFrame]; <> UNTIL EmptyRefStack[] DO TraceRefsInObject[LOOPHOLE[PopRef[], REF]] ENDLOOP; <> FreeRefStacks[]; <<>> <> <> AllObjects[visitOneObject]; <> IF objectsReclaimed + objectsKept # objectsSeen THEN ERROR; -- check for consistency }; -- end ActuallyDoIt DoTraceAndSweepCollection: PROC = {ENABLE UNWIND => NULL; haveAllocatorLocked: PROC = { -- here with the loader and allocator locked haveRCOvLocked: PROC = { <> haveZCTLocked: PROC = { <> RTFrameHeapSnapshot.AcquireFrameHeapSnapshot[]; { ENABLE UNWIND => RTFrameHeapSnapshot.ReleaseFrameHeapSnapshot[]; ActuallyDoIt[ignoreStack: FALSE]; IF destructiveTestEnabled THEN { ActuallyDoIt[ignoreStack: TRUE]; DebuggerSwap.CallDebugger["destructive collection finished."]; }; -- look at XXX from the debugger RTFrameHeapSnapshot.ReleaseFrameHeapSnapshot[]; }; }; <> <> ZCT.EnterAndCallBack[haveZCTLocked]; }; <> <> ZCT.EnterRCOvAndCallBack[haveRCOvLocked]; }; -- end haveAllocatorLocked <<>> <> <> LoadState.local.Acquire[exclusive]; <> AllocatorOps.EnterAndCallBack[haveAllocatorLocked ! UNWIND => LoadState.local.Release[]]; <> LoadState.local.Release[]; }; -- end DoTraceAndSweepCollection <> <<(this includes reconstructing the RC for the object) >> MarkRef: PROC [ref: REF, countIt: BOOL _ TRUE] = INLINE { IF NOT Marked[ref] THEN { <> SetMark[ref]; IF RefContaining[ref] THEN PushRef[LOOPHOLE[ref, LONG POINTER]]; }; IF countIt THEN IncRC[ref] }; <> visitOneObject: PROC [nhp: NHeaderP] = { IF nhp.f THEN { -- adjust refCount FOR i: CARDINAL IN [1..RTTypesBasicPrivate.NumberPackageRefs[nhp.type]] DO DecRC[NHPToREF[nhp] ! RCMicrocodeOps.ZCTFull => DebuggerSwap.CallDebugger["TAndS disaster."]]; ENDLOOP; }; IF nhp.f OR Marked[AllocatorOps.NHPToREF[nhp]] THEN { objectsKept _ objectsKept + 1; IF NOT findingCircularGarbage THEN ClearMark[nhp]; IF nhp.refCount = 0 AND NOT nhp.rcOverflowed THEN { IF NOT nhp.f THEN { rpa[nextRpaIndex] _ LOOPHOLE[NHPToREF[nhp], LONG POINTER]; IF nextRpaIndex < maxNRPIndex THEN nextRpaIndex _ nextRpaIndex + 1; nRetainedObjects _ nRetainedObjects + 1; }; <> RCMicrocodeOps.OnZ[nhp ! RCMicrocodeOps.ZCTFull => DebuggerSwap.CallDebugger["TAndS disaster."]]; }; } ELSE { IF findingCircularGarbage THEN {objectsKept _ objectsKept + 1; RETURN}; objectsReclaimed _ objectsReclaimed + 1; AllocatorOps.TAndSFreeObject[nhp]; }; }; TraceLocalFrame: PROC [d: LONG DESCRIPTOR FOR ARRAY OF WORD] = { <> <> pa: LONG POINTER TO LONG CARDINAL = LOOPHOLE[BASE[d], LONG POINTER TO LONG CARDINAL]; nWords: CARDINAL = LENGTH[d]; nLocalFrames _ nLocalFrames + 1; IF nWords >= SIZE[REF] THEN FOR i: CARDINAL IN [0..nWords-SIZE[REF]] DO addr: LONG CARDINAL = (pa+i)^; IF addr # 0 AND AllocatorOps.IsValidRef[LOOPHOLE[addr, LONG POINTER]] THEN { <> ref: REF = LOOPHOLE[addr, REF]; IF suspectRef # NIL AND LOOPHOLE[addr, LONG POINTER] = suspectRef THEN suspectRefFoundInLocalFrame _ TRUE; MarkRef[ref: ref, countIt: FALSE]; }; 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] = { IF ref = NIL THEN RETURN; IF suspectRef # NIL AND LOOPHOLE[ref, LONG POINTER] = suspectRef THEN gfhToSuspectRef _ gfh; MarkRef[ref]; }; 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 _ GetReferentType[container]; refererPushed: BOOL _ FALSE; procRef: PROC [ref: REF] = { IF ref = NIL THEN RETURN; IF suspectRef # NIL AND LOOPHOLE[ref, LONG POINTER] = suspectRef AND 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 {circularStructureFound _ TRUE; EXIT} ENDLOOP; IF NOT circularStructureFound AND nInnerReferers < maxNInnerReferers THEN { innerReferers[nInnerReferers] _ nhp; nInnerReferers _ nInnerReferers + 1; }; }; MarkRef[ref]; }; -- end procRef 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 _ 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, LONG CARDINAL] < LastAddress AND quantumMap[LPToQuantumIndex[hp]] DO nhp: NHeaderP = LOOPHOLE [ IF IsExtendedBlock[hp] THEN hp + SIZE[ExtendedHeader] - SIZE[NormalHeader] ELSE hp, NHeaderP ]; blockSize _ BlockSize[hp]; visit[nhp]; ENDLOOP; IF LOOPHOLE[hp, LONG CARDINAL] >= LastAddress THEN RETURN; qi _ LPToQuantumIndex[hp]; ENDLOOP; }; LPToQuantumIndex: PROC[lp: LONG POINTER] RETURNS[QuantumIndex] = { RETURN[LOOPHOLE[lp, LONG CARDINAL]/wordsPerQuantum]; }; QuantumIndexToLP: PROC[qi: QuantumIndex] RETURNS[LONG POINTER] = { n: LONG CARDINAL _ qi; RETURN[LOOPHOLE[n*wordsPerQuantum, LONG POINTER]]; }; IsExtendedBlock: PROC[hp: HeaderP] RETURNS[BOOL] = { RETURN[LOOPHOLE[hp, NHeaderP].blockSizeIndex = bsiEscape]; }; Marked: PROC [ref: REF] RETURNS [BOOL] = INLINE { <> RETURN [REFToNHP[ref].inZCT--i.e. marked--]}; SetMark: PROC [ref: REF] = INLINE { <> REFToNHP[ref].inZCT--i.e. marked-- _ TRUE}; ClearMark: PROC [nhp: NHeaderP] = INLINE { <> nhp.inZCT--i.e. marked-- _ FALSE}; 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.Allocate[count: 1].page]; stack.next _ NIL; stack.size _ 0; stack.max _ (PrincOps.wordsPerPage - (SIZE[RefStackRep])) / (SIZE[LONG POINTER]); } 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]; }; EmptyRefStack: PROC RETURNS [BOOL] = INLINE { <> RETURN [refStackChain = 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: 1]]; refStackFree _ stack ENDLOOP; }; RefContaining: PROC [ref: REF] RETURNS [BOOL] = INLINE { <> IF ref = NIL THEN RETURN[FALSE]; RETURN [RTTypesBasicPrivate.MapTiRcmx[GetReferentType[ref]] # RCMap.nullIndex]; }; <> Collector.EstablishTAndSProc[DoTraceAndSweepCollection] END.