DIRECTORY Allocator USING[NHeaderP, NormalHeader, RefCount, BlockSizeIndex, FNHeaderP], AllocatorOps USING[PlausibleRef, REFToNHP, sizeToBSI, bsiToSize, ExpandNormalFreeList, FreeObject], Basics USING[Byte, BITAND, BITOR, BITSHIFT, BITXOR, LowHalf, LongNumber], CedarMicrocode USING[RECLAIMABLEREF, DISABLEMICROCODE, ENABLEMICROCODE], Collector USING[InternalReclaim, Disposition, Reclaim], DebuggerSwap USING[CallDebugger], PrincOps USING[ControlLink, StateVector, zRET], PrincOpsUtils USING[Codebase, GetReturnLink, MyLocalFrame], RCMap USING[nullIndex], RCMicrocodeOps USING[FOSTableHash, ASSIGNREF, OnZ, CREATEREF, RECLAIMABLEREF, RECLAIMEDREF, DISABLEMICROCODE, ENABLEMICROCODE, RCOverflowOccurred, RCUnderflowOccurred, LookFurtherAtReclaimedRef, ZCTFull, rcMicrocodeExists, rcMicrocodeWasEnabled, ALLOCATE, FREEPLEASE, NormalFreeListEmpty], RTFrameHeapSnapshot USING[AcquireFrameHeapSnapshot, MapUncountedBodies, ReleaseFrameHeapSnapshot], RTTypesBasicPrivate USING[MapTiTd], SafeStorage USING[Type, nullType], StorageTraps USING[], TrapSupport USING[BumpPC, GetTrapParam], VM USING[Allocate, Free, Interval, AddressForPageNumber], ZCT USING[fosEmpty, FOSTableIndex, FOSTableObject, FOSTableResidue, HandleRCOverflow, HandleRCUnderflow, InitializeCleanup, logZCTBlockPages, TryToQItForFinalization, zct, zctBlockPages, zctBlockWords, ZCTObject, ZeroCountTable]; ZCTImpl: MONITOR -- protects the ZeroCountTable and object headers, notably their refCounts IMPORTS AllocatorOps, Basics, CedarMicrocode, Collector, DebuggerSwap, PrincOpsUtils, RCMicrocodeOps, RTFrameHeapSnapshot, RTTypesBasicPrivate, TrapSupport, VM, ZCT EXPORTS RCMicrocodeOps, StorageTraps, ZCT = BEGIN OPEN Allocator, AllocatorOps, Collector, RCMicrocodeOps, ZCT; checking: BOOL = FALSE; takingStatistics: BOOL = TRUE; Bump: PROC[p: POINTER TO INT, delta: INT _ 1] = INLINE {IF takingStatistics THEN p^ _ p^+delta}; StatsRec: TYPE = RECORD [ nExpandZCTCalls: INT _ 0, nZCTBlocks: INT _ 0 ]; stats: StatsRec _ []; -- the one and only SoftwareCreateRef: PUBLIC PROC[nhp: NHeaderP] = { DO { DoCreateRef[nhp ! ZCTFull => GOTO zctFull]; EXIT; EXITS zctFull => ExpandZCT[]; }; ENDLOOP; }; AssignRefNew: PROC[rhs: REF ANY, lhs: LONG POINTER TO REF ANY] = { IF checking AND lhs^ # NIL THEN ERROR; AssignRef[rhs, lhs]; }; AssignRef: --PUBLIC-- PROC[rhs: REF, lhs: LONG POINTER TO REF] = { DO { DoAssignRef[rhs, lhs ! -- PageFault => {SatisfyPageFault[]; RETRY}; RCUnderflowOccurred => GOTO handleRCUnderflow; RCOverflowOccurred => GOTO handleRCOverflow; ZCTFull => GOTO zctFull; ]; RETURN; EXITS handleRCUnderflow => HandleRCUnderflow[lhs^]; handleRCOverflow => HandleRCOverflow[rhs]; -- increment, assnmt were NOT DONE zctFull => ExpandZCT[]; }; ENDLOOP; }; SoftwareReclaimedRef: PUBLIC PROC[ref: REF ANY] RETURNS[ans: REF ANY _ NIL] = { DO { ans _ DoReclaimedRef[ref -- if a signal, the decrement was NOT DONE ! RCUnderflowOccurred => GOTO handleRCUnderflow; ZCTFull => GOTO zctFull; LookFurtherAtReclaimedRef => GOTO lookFurther; ]; RETURN; EXITS zctFull => ExpandZCT[]; handleRCUnderflow => HandleRCUnderflow[ref]; }; ENDLOOP; EXITS lookFurther => FinalizeReclaimedRef[ref]; }; SoftwareAllocate: PUBLIC PROC[size: CARDINAL, type: SafeStorage.Type] RETURNS[r: REF _ NIL] = { DO { r _ SoftwareAllocateEntry[size, type ! NormalFreeListEmpty => GOTO expandNormalFreeList; ZCTFull => GOTO zctFull]; RETURN; EXITS expandNormalFreeList => ExpandNormalFreeList[sizeToBSI[size]]; zctFull => ExpandZCT[]; }; ENDLOOP; }; SoftwareFree: PUBLIC PROC[nhp: NHeaderP] RETURNS[success: BOOL] = {success _ SoftwareFreeEntry[nhp]}; ScanTheFrameHeap: PUBLIC PROC = { PlausibleRefFoundOnStack: PROC[lc: LONG CARDINAL] = { index: FOSTableIndex; residue: FOSTableResidue; fosTable: LONG POINTER TO FOSTableObject = LOOPHOLE[zct+SIZE[ZCTObject], LONG POINTER TO FOSTableObject]; [index, residue] _ FOSTableHash[LOOPHOLE[lc - SIZE[NormalHeader], NHeaderP--maybe bogus--]]; IF fosTable[index] = fosEmpty THEN fosTable[index] _ residue ELSE IF fosTable[index] # residue THEN fosTable[index] _ Basics.BITOR[fosEmpty, Basics.BITOR[fosTable[index], residue]]; }; ConservativeScanner: 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]; IF nWords >= SIZE[REF] THEN FOR i: CARDINAL IN [0..nWords-SIZE[REF]] DO addr: LONG CARDINAL = (pa+i)^; IF PlausibleRef[addr] THEN PlausibleRefFoundOnStack[addr]; ENDLOOP; }; RTFrameHeapSnapshot.AcquireFrameHeapSnapshot[]; RTFrameHeapSnapshot.MapUncountedBodies[ConservativeScanner ! UNWIND => RTFrameHeapSnapshot.ReleaseFrameHeapSnapshot[]]; RTFrameHeapSnapshot.ReleaseFrameHeapSnapshot[]; }; -- end ScanTheFrameHeap MapReclaimableObjects: PUBLIC PROC[reclaim: PROC[NHeaderP]] = { -- and compactify zct wp: LONG POINTER TO NHeaderP = ReadWP[]; IF reclaim # NIL THEN ERROR; FOR nhp: NHeaderP _ PullNextEntry[wp, FALSE], PullNextEntry[wp, FALSE] UNTIL nhp = NIL DO d: Disposition; IF nhp.refCount # 0 THEN DO { OnZEntry[nhp ! ZCTFull => GOTO zctFull]; -- put it back on the ZCT so that ResetStackBits will eliminate it and clean the maybeOnStack bit d _ continue; EXIT; EXITS zctFull => ExpandZCT[]; }; ENDLOOP ELSE DO { d _ ReclaimableRef[nhp ! ZCTFull => GOTO zctFull]; EXIT; EXITS zctFull => ExpandZCT[]; }; ENDLOOP; SELECT d FROM continue => NULL; -- either it was re-queued on zct or left off reclaimIt => IF RTTypesBasicPrivate.MapTiTd[nhp.type].rcmx = RCMap.nullIndex THEN AllocatorOps.FreeObject[nhp] ELSE Collector.Reclaim[nhp]; finalizeIt => --rc = 0 & ~ not onstack & f IF NOT TryToQItForFinalization[nhp] THEN -- finalization q is full DO { OnZEntry[nhp ! ZCTFull => GOTO zctFull]; EXIT; EXITS zctFull => ExpandZCT[]; }; ENDLOOP; ENDCASE => ERROR; ENDLOOP; }; -- end MapReclaimableObjects ReclaimableRef: PROC[nhp: NHeaderP] RETURNS[Disposition] = { IF rcMicrocodeExists THEN RETURN[CedarMicrocode.RECLAIMABLEREF[nhp]] ELSE RETURN[SoftwareReclaimableRef[nhp]]; }; SoftwareReclaimableRef: PROC[nhp: NHeaderP] RETURNS[d: Disposition] = { DO { d _ DoReclaimableRef[nhp ! ZCTFull => GOTO zctFull]; RETURN; EXITS zctFull => ExpandZCT[]; }; ENDLOOP; }; ResetStackBits: PUBLIC PROC = { -- and compactify zct wp: LONG POINTER TO NHeaderP = ReadWP[]; FOR nhp: NHeaderP _ PullNextEntry[wp, TRUE], PullNextEntry[wp, TRUE] UNTIL nhp = NIL DO IF nhp.refCount = 0 AND NOT nhp.rcOverflowed THEN DO { --- put it back OnZEntry[nhp ! ZCTFull => GOTO zctFull]; EXIT; EXITS zctFull => ExpandZCT[]; }; ENDLOOP; ENDLOOP; ClearFOSTable[]; }; PullNextEntry: PROC[wp: LONG POINTER TO NHeaderP, clearOnStack: BOOL] RETURNS[nhp: NHeaderP _ NIL] = { DO n: CARDINAL; IF zct.rp = wp THEN RETURN[NIL]; -- nomore nhp _ zct.rp^; IF checking AND nhp = NIL THEN ERROR; n _ Basics.BITAND[Basics.LowHalf[LOOPHOLE[zct.rp, LONG CARDINAL]], zctBlockWords-1]; IF n = zctBlockWords - SIZE[LONG POINTER] -- rp points to the link; nhp has it THEN { -- we're done with this zctBlock zct.rp^ _ NIL; -- clears the link to the next zctBlock. [] _ DoExpandZCT[zct.rp + SIZE[LONG POINTER] - zctBlockWords, FALSE]; zct.rp _ LOOPHOLE[nhp, LONG POINTER TO NHeaderP]; } ELSE { zct.rp _ zct.rp + SIZE[LONG POINTER]; nhp.inZCT _ FALSE; -- was TRUE (no race!!) IF clearOnStack THEN nhp.maybeOnStack _ FALSE; -- called from ResetStackBits IF nhp.refCount = 0 OR (~clearOnStack AND nhp.maybeOnStack) THEN RETURN; --to scrutinize this guy further }; ENDLOOP; }; ExpandZCT: PUBLIC PROC = { success: BOOL; zbInterval: VM.Interval = VM.Allocate[count: zctBlockPages, alignment: logZCTBlockPages]; p: LONG POINTER _ VM.AddressForPageNumber[zbInterval.page]; Bump[@stats.nExpandZCTCalls]; InternalReclaim[reason: rcTableOverflow, suspendMe: FALSE]; -- just poke it LOOPHOLE[p + zctBlockWords - SIZE[LONG POINTER], LONG POINTER TO NHeaderP]^ _ NIL; -- clear the link success _ DoExpandZCT[p, TRUE]; IF success THEN Bump[@stats.nZCTBlocks] ELSE VM.Free[zbInterval]; }; ClearFOSTable: PROC = { LOOPHOLE[zct+SIZE[ZCTObject], LONG POINTER TO FOSTableObject]^ _ ALL[fosEmpty]}; Enter: PUBLIC ENTRY PROC = {ENABLE UNWIND => NULL; NULL}; EnterAndCallBack: PUBLIC ENTRY PROC[proc: PROC] = { ENABLE UNWIND => [] _ EnableMicrocode[zct]; DisableMicrocode[zct]; proc[]; [] _ EnableMicrocode[zct]; }; DoAssignRef: ENTRY PROC[rhs: REF, lhs: LONG POINTER TO REF] = { ENABLE UNWIND => [] _ EnableMicrocode[zct]; DisableMicrocode[zct]; ASSIGNREF[rhs, lhs]; [] _ EnableMicrocode[zct]; }; DoCreateRef: ENTRY PROC[nhp: NHeaderP] = { ENABLE UNWIND => [] _ EnableMicrocode[zct]; DisableMicrocode[zct]; CREATEREF[nhp]; [] _ EnableMicrocode[zct]; }; StartMarkingDecrements: PUBLIC ENTRY PROC = { ENABLE UNWIND => [] _ EnableMicrocode[zct]; DisableMicrocode[zct]; zct.markingDecrements _ TRUE; zct.residueMask _ Basics.BITOR[Basics.BITSHIFT[zct.residueMask, 3], Basics.BITSHIFT[zct.residueMask, -13]]; [] _ EnableMicrocode[zct]; }; StopMarkingDecrements: PUBLIC ENTRY PROC = { ENABLE UNWIND => [] _ EnableMicrocode[zct]; DisableMicrocode[zct]; zct.markingDecrements _ FALSE; [] _ EnableMicrocode[zct]; }; DoReclaimableRef: ENTRY PROC[nhp: NHeaderP] RETURNS[d: Disposition] = { ENABLE UNWIND => [] _ EnableMicrocode[zct]; DisableMicrocode[zct]; d _ RECLAIMABLEREF[nhp]; -- The only call on RECLAIMABLEREF [] _ EnableMicrocode[zct]; }; DoReclaimedRef: ENTRY PROC[ref: REF ANY] RETURNS[ans: REF ANY _ NIL] = { ENABLE UNWIND => [] _ EnableMicrocode[zct]; DisableMicrocode[zct]; ans _ RECLAIMEDREF[ref]; [] _ EnableMicrocode[zct]; }; ReadWP: ENTRY PROC RETURNS[wp: LONG POINTER TO Allocator.NHeaderP] = { ENABLE UNWIND => [] _ EnableMicrocode[zct]; DisableMicrocode[zct]; wp _ zct.wp; [] _ EnableMicrocode[zct]; }; FinalizeReclaimedRef: PROC[ref: REF] = { nhp: NHeaderP = REFToNHP[ref]; DO { DecrementForFinalizeReclaimedRef[nhp ! RCUnderflowOccurred => GOTO handleRCUnderflow]; EXIT; EXITS handleRCUnderflow => HandleRCUnderflow[ref]; }; ENDLOOP; IF NOT TryToQItForFinalization[nhp] THEN -- finalization q is full DO { OnZEntry[nhp ! ZCTFull => GOTO zctFull]; EXIT; EXITS zctFull => ExpandZCT[]; }; ENDLOOP; }; DecrementForFinalizeReclaimedRef: ENTRY PROC[nhp: NHeaderP] = { ENABLE UNWIND => [] _ EnableMicrocode[zct]; rc: RefCount; DisableMicrocode[zct]; rc _ nhp.refCount; IF checking AND rc = 0 AND NOT nhp.rcOverflowed THEN ERROR; IF rc = 0 AND nhp.rcOverflowed THEN ERROR RCUnderflowOccurred; -- no changes have been made nhp.refCount _ rc - 1; [] _ EnableMicrocode[zct]; }; DoEnableFinalization: PUBLIC ENTRY PROC[npr: NAT, nhp: NHeaderP] = { ENABLE UNWIND => [] _ EnableMicrocode[zct]; rc: RefCount; DisableMicrocode[zct]; IF checking AND nhp.f THEN ERROR; rc _ nhp.refCount; IF checking AND rc < npr AND NOT nhp.rcOverflowed THEN ERROR; IF rc < npr AND nhp.rcOverflowed THEN ERROR RCUnderflowOccurred; IF rc = npr AND NOT nhp.rcOverflowed THEN OnZ[nhp]; -- might raise ZCTFull nhp.refCount _ rc - npr; nhp.f _ TRUE; nhp.maybeOnStack _ zct.markingDecrements; [] _ EnableMicrocode[zct]; }; DisableFinalization: PUBLIC ENTRY PROC[npr: NAT, nhp: NHeaderP] = { ENABLE UNWIND => [] _ EnableMicrocode[zct]; rc: RefCount; DisableMicrocode[zct]; IF checking AND NOT nhp.f THEN ERROR; rc _ nhp.refCount; FOR i: NAT IN [0..npr) DO IF rc + i = LAST[RefCount] THEN ERROR RCOverflowOccurred ENDLOOP; nhp.refCount _ rc + npr; nhp.f _ FALSE; nhp.maybeOnStack _ FALSE; [] _ EnableMicrocode[zct]; }; DecrForOverflow: PUBLIC ENTRY PROC[rcDelta: NAT, nhp: NHeaderP] RETURNS[success: BOOL _ FALSE] = { ENABLE UNWIND => [] _ EnableMicrocode[zct]; DisableMicrocode[zct]; IF nhp.refCount = LAST[RefCount] THEN { nhp.refCount _ nhp.refCount - rcDelta; success _ TRUE; }; [] _ EnableMicrocode[zct]; }; IncrForUnderflow: PUBLIC ENTRY PROC[rcDelta: NAT, nhp: NHeaderP] RETURNS[success: BOOL _ FALSE] = { ENABLE UNWIND => [] _ EnableMicrocode[zct]; DisableMicrocode[zct]; IF nhp.refCount = 0 THEN { nhp.refCount _ nhp.refCount + rcDelta; success _ TRUE; }; [] _ EnableMicrocode[zct]; }; DoExpandZCT: ENTRY PROC[newZCTBlock: LONG POINTER, onlyIfNeeded: BOOL] RETURNS[success: BOOL _ TRUE] = { ENABLE UNWIND => [] _ EnableMicrocode[zct]; DisableMicrocode[zct]; IF NOT onlyIfNeeded OR zct.lastNP = ComputeLastNP[zct.wp] -- zct.lastNP^ = NIL THEN { zct.lastNP^ _ newZCTBlock; zct.lastNP _ LOOPHOLE[newZCTBlock + zctBlockWords-SIZE[LONG POINTER], LONG POINTER TO LONG POINTER]; } ELSE success _ FALSE; [] _ EnableMicrocode[zct]; }; ComputeLastNP: INTERNAL PROC[wp: LONG POINTER TO NHeaderP] RETURNS[lastNP: LONG POINTER TO LONG POINTER] = { n: Basics.LongNumber _ LOOPHOLE[wp, Basics.LongNumber]; n.lowbits _ Basics.BITXOR[n.lowbits, Basics.BITAND[n.lowbits, zctBlockWords-1]]; RETURN[LOOPHOLE[n, LONG POINTER TO NHeaderP] + zctBlockWords - SIZE[LONG POINTER] ]; }; SoftwareAllocateEntry: ENTRY PROC[size: CARDINAL, type: SafeStorage.Type] RETURNS[r: REF _ NIL] = { ENABLE UNWIND => [] _ EnableMicrocode[zct]; DisableMicrocode[zct]; r _ RCMicrocodeOps.ALLOCATE[size, type]; [] _ EnableMicrocode[zct]; }; SoftwareFreeEntry: ENTRY PROC[nhp: NHeaderP] RETURNS[success: BOOL] = { ENABLE UNWIND => [] _ EnableMicrocode[zct]; DisableMicrocode[zct]; success _ RCMicrocodeOps.FREEPLEASE[nhp]; [] _ EnableMicrocode[zct]; }; InsertQuanta: PUBLIC ENTRY PROC[bsi: BlockSizeIndex, first, last: FNHeaderP] = { ENABLE UNWIND => [] _ EnableMicrocode[zct]; DisableMicrocode[zct]; last.nextFree _ zct.bsiToFreeList[bsi]; zct.bsiToFreeList[bsi] _ first; [] _ EnableMicrocode[zct]; }; DoFREE: PUBLIC ENTRY PROC[fnhp: FNHeaderP, bsi: BlockSizeIndex] = { ENABLE UNWIND => [] _ EnableMicrocode[zct]; DisableMicrocode[zct]; fnhp.fnh.type _ SafeStorage.nullType; -- mark the object as free fnhp.nextFree _ zct.bsiToFreeList[bsi]; zct.bsiToFreeList[bsi] _ fnhp; [] _ EnableMicrocode[zct]; }; Initialize: ENTRY PROC = { ENABLE UNWIND => NULL; zct.rp _ zct.wp _ LOOPHOLE[ VM.AddressForPageNumber[ VM.Allocate[count: zctBlockPages, alignment: logZCTBlockPages].page ], LONG POINTER TO Allocator.NHeaderP ]; zct.lastNP _ LOOPHOLE[zct.wp+zctBlockWords-SIZE[LONG POINTER], LONG POINTER TO LONG POINTER]; zct.lastNP^ _ NIL; ClearFOSTable[]; zct.markingDecrements _ FALSE; zct.residueMask _ 76031B; zct.bsiToFreeList _ ALL[NIL]; zct.sizeToBSI _ sizeToBSI^; zct.bsiToSize _ bsiToSize^; InitializeCleanup[]; }; OnZEntry: ENTRY PROC[nhp: NHeaderP] = { ENABLE UNWIND => [] _ EnableMicrocode[zct]; DisableMicrocode[zct]; OnZ[nhp]; [] _ EnableMicrocode[zct]; }; DisableMicrocode: INTERNAL PROC[zct: ZeroCountTable] = { IF rcMicrocodeExists THEN CedarMicrocode.DISABLEMICROCODE[zct] ELSE DISABLEMICROCODE[zct]; rcMicrocodeWasEnabled _ FALSE; }; EnableMicrocode: INTERNAL PROC[zct: ZeroCountTable] RETURNS[ucVersion: NAT] = { IF rcMicrocodeExists THEN ucVersion _ CedarMicrocode.ENABLEMICROCODE[zct] ELSE ucVersion _ ENABLEMICROCODE[zct]; rcMicrocodeWasEnabled _ TRUE; }; DisableMicrocodeTrap: PUBLIC PROC[zct: ZeroCountTable] = { state: PrincOps.StateVector; state _ STATE; -- incantation SELECT (IF rcMicrocodeExists THEN TrapSupport.GetTrapParam[] ELSE 0) FROM 0 => NULL; -- no microcode ENDCASE => ERROR; TrapSupport.BumpPC[2]; -- length of opcode state.dest _ LOOPHOLE[PrincOpsUtils.MyLocalFrame[]]; TRANSFER WITH state; -- incantation }; EnableMicrocodeTrap: PUBLIC PROC[zct: ZeroCountTable] RETURNS[ucVersion: NAT _ 0] = { state: PrincOps.StateVector; state _ STATE; -- incantation SELECT (IF rcMicrocodeExists THEN TrapSupport.GetTrapParam[] ELSE 0) FROM 0 => NULL; -- no microcode ENDCASE => ERROR; TrapSupport.BumpPC[2]; -- length of opcode state.dest _ LOOPHOLE[PrincOpsUtils.MyLocalFrame[]]; TRANSFER WITH state; -- incantation }; ReclaimableRefTrap: PUBLIC PROC[nhp: NHeaderP] RETURNS[d: Disposition] = { state: PrincOps.StateVector; state _ STATE; -- incantation SELECT (IF rcMicrocodeExists THEN TrapSupport.GetTrapParam[] ELSE 0) FROM 0 => d _ SoftwareReclaimableRef[nhp]; -- no microcode 2 => { -- uCode is disabled; someone is inside this monitor p: PROC[nhp: NHeaderP] = MACHINE CODE{PrincOps.zRET}; Enter[]; state.dest _ LOOPHOLE[PrincOpsUtils.MyLocalFrame[]]; TRANSFER WITH state; -- incantation p[nhp]; -- try again }; 4 => { -- zctFull p: PROC[nhp: NHeaderP] = MACHINE CODE{PrincOps.zRET}; ExpandZCT[]; state.dest _ LOOPHOLE[PrincOpsUtils.MyLocalFrame[]]; TRANSFER WITH state; -- incantation p[nhp]; }; 5 => DebuggerSwap.CallDebugger["ZCT disaster: ReclaimableRef"]; -- DISASTER ENDCASE => ERROR; TrapSupport.BumpPC[2]; -- length of opcode state.dest _ LOOPHOLE[PrincOpsUtils.MyLocalFrame[]]; TRANSFER WITH state; -- incantation }; ReclaimedRefTrap: PUBLIC PROC[ref: REF ANY] RETURNS[ans: REF ANY _ NIL] = { state: PrincOps.StateVector; state _ STATE; -- incantation SELECT (IF rcMicrocodeExists THEN TrapSupport.GetTrapParam[] ELSE 0) FROM 0 => ans _ SoftwareReclaimedRef[ref]; -- no microcode 2 => { -- uCode is disabled; someone is inside this monitor p: PROC[ref: REF ANY] = MACHINE CODE{PrincOps.zRET}; Enter[]; state.dest _ LOOPHOLE[PrincOpsUtils.MyLocalFrame[]]; TRANSFER WITH state; -- incantation p[ref]; -- try again }; 3 => { p: PROC[ref: REF ANY] = MACHINE CODE{PrincOps.zRET}; HandleRCUnderflow[ref]; state.dest _ LOOPHOLE[PrincOpsUtils.MyLocalFrame[]]; TRANSFER WITH state; -- incantation p[ref]; -- try again }; 4 => { -- zctFull p: PROC[ref: REF ANY] = MACHINE CODE{PrincOps.zRET}; ExpandZCT[]; state.dest _ LOOPHOLE[PrincOpsUtils.MyLocalFrame[]]; TRANSFER WITH state; -- incantation p[ref]; }; 5 => DebuggerSwap.CallDebugger["ZCT disaster: ReclaimedRef"]; -- DISASTER 6 => FinalizeReclaimedRef[ref]; -- LookFurtherAtReclaimedRef ENDCASE => ERROR; TrapSupport.BumpPC[2]; -- length of opcode state.dest _ LOOPHOLE[PrincOpsUtils.MyLocalFrame[]]; TRANSFER WITH state; -- incantation }; CreateRefTrap: PUBLIC PROC[nhp: NHeaderP] = { state: PrincOps.StateVector; state _ STATE; -- incantation SELECT (IF rcMicrocodeExists THEN TrapSupport.GetTrapParam[] ELSE 0) FROM 0 => SoftwareCreateRef[nhp]; -- no microcode 2 => { -- uCode is disabled; someone is inside this monitor p: PROC[nhp: NHeaderP] = MACHINE CODE{PrincOps.zRET}; Enter[]; state.dest _ LOOPHOLE[PrincOpsUtils.MyLocalFrame[]]; TRANSFER WITH state; -- incantation p[nhp]; }; 4 => { -- zctFull p: PROC[nhp: NHeaderP] = MACHINE CODE{PrincOps.zRET}; ExpandZCT[]; state.dest _ LOOPHOLE[PrincOpsUtils.MyLocalFrame[]]; TRANSFER WITH state; -- incantation p[nhp]; }; ENDCASE => ERROR; TrapSupport.BumpPC[2]; -- length of opcode state.dest _ LOOPHOLE[PrincOpsUtils.MyLocalFrame[]]; TRANSFER WITH state; -- incantation }; AssignRefTrap: PUBLIC PROC[refNew: REF, ptrRef: LONG POINTER TO REF] = { state: PrincOps.StateVector; alphaRef: LONG POINTER TO REF; state _ STATE; -- incantation alphaRef _ AddAlphaByte[ptrRef, PrincOpsUtils.GetReturnLink[]]; SELECT (IF rcMicrocodeExists THEN TrapSupport.GetTrapParam[] ELSE 0) FROM 0 => AssignRef[refNew, alphaRef]; -- no microcode 1 => { -- handleRCOverflow: rc ops and assnmt were NOT DONE p: PROC[refNew: REF, ptrRef: LONG POINTER TO REF] = MACHINE CODE{PrincOps.zRET}; HandleRCOverflow[refNew]; state.dest _ LOOPHOLE[PrincOpsUtils.MyLocalFrame[]]; TRANSFER WITH state; -- incantation p[refNew, ptrRef]; -- try again }; 2 => { -- uCode is disabled; someone is inside this monitor p: PROC[refNew: REF, ptrRef: LONG POINTER TO REF] = MACHINE CODE{PrincOps.zRET}; Enter[]; state.dest _ LOOPHOLE[PrincOpsUtils.MyLocalFrame[]]; TRANSFER WITH state; -- incantation p[refNew, ptrRef]; -- try again }; 3 => { p: PROC[refNew: REF, ptrRef: LONG POINTER TO REF] = MACHINE CODE{PrincOps.zRET}; HandleRCUnderflow[alphaRef^]; state.dest _ LOOPHOLE[PrincOpsUtils.MyLocalFrame[]]; TRANSFER WITH state; -- incantation p[refNew, ptrRef]; -- try again }; 4 => { -- zctFull p: PROC[refNew: REF, ptrRef: LONG POINTER TO REF] = MACHINE CODE{PrincOps.zRET}; ExpandZCT[]; state.dest _ LOOPHOLE[PrincOpsUtils.MyLocalFrame[]]; TRANSFER WITH state; -- incantation p[refNew, ptrRef]; -- try again }; 5 => DebuggerSwap.CallDebugger["ZCT disaster: AssignRef"]; -- DISASTER ENDCASE => ERROR; TrapSupport.BumpPC[2]; -- length of opcode state.dest _ LOOPHOLE[PrincOpsUtils.MyLocalFrame[]]; TRANSFER WITH state; -- incantation }; AddAlphaByte: PROC[ptrRef: LONG POINTER TO REF, ctL: PrincOps.ControlLink] RETURNS [LONG POINTER TO REF] = { codeB: LONG POINTER TO PACKED ARRAY OF Basics.Byte _ LOOPHOLE[PrincOpsUtils.Codebase[LOOPHOLE[ctL.frame.accesslink]]]; alpha: Basics.Byte _ codeB[ctL.frame.pc + 1]; RETURN[LOOPHOLE[ptrRef + alpha]]; }; Initialize[]; END. šZCTImpl.mesa Implementation of the Zero Count Table for the Cedar incremental collector Paul Rovner, January 18, 1984 9:36:15 am PST Richard Koo, July 2, 1984 8:54:24 pm PDT CONSTANTS STATISTICS usage: Bump[@stats.nExpandZCTCalls]; PROCEDURES REFERENCE COUNTING See CREATEREF, the ucode replacement for this guy See ASSIGNREF, the ucode replacement for this guy See ASSIGNREF, the ucode replacement for this guy this is the only catch for RCOverflowOccurred See RECLAIMEDREF, the ucode replacement for this guy ReclaimedRef is called by the reclaimer on each (non-NIL) ref that it finds within an object being reclaimed. ReclaimedRef will decrement the reference count on ref^ and return a non-NIL result (= ref) if the referenced object can be reclaimed (it will not enter it in the zct in this case). If ref^ can't be reclaimed, ReclaimedRef will return NIL. ReclaimedRef will queue ref^ for finalization if necessary. It will deal with rc underflow. It is possible (a finalized object, no room on its finalization queue) that ReclaimedRef will enter the ref on the zct. If the zct is full, ReclaimedRef will expand the zct. END REFERENCE COUNTING ALLOCATION AND RECLAMATION END ALLOCATION AND RECLAMATION COLLECTOR, ZCT nhp has been removed from zct rc = 0 & not onstack & ~f: reclaim it (it was removed from zct)! it should stay in the zct This may raise ZCTFull. Ifso, no changes have been made This is called only from MapReclaimableObjects See RECLAIMABLEREF, the ucode replacement for this guy This is called only from ReclaimableRef nhp has been removed from zct This is called by MapReclaimableObjects and ResetStackBits This is the only proc that sets nhp.inZCT _ FALSE or reads or writes zct.rp wp will never point to a link This returns NIL if there are no more ZCT entries to read This is the next good candidate for implementation in microcode Here with non-NIL nhp; maybe a link and go around again END COLLECTOR, ZCT ENTRY PROCS 0. Enter ... used by trap handlers and TraceAndSweepImpl 1. AssignRef This is called only from AssignRef This may raise ZCTFull, RCOverflowOccurred, RCUnderflowOccurred 2. CreateRef This is called only from SoftwareCreateRef DoCreateRef may raise ZCTFull 3. Collector and reclaimer This is called only from SoftwareReclaimableRef This is called only from SoftwareReclaimedRef This may raise ZCTFull, RCUnderflowOccurred, LookFurtherAtReclaimedRef 4. Finalization ... called from FQImpl Called from ReclaimedRefTrap and from SoftwareReclaimedRef refCount = 1 & ~ rcOverflowed & ~ maybeOnStack & ~ inZCT & f i.e. if the object has npr + 1 REFs, is referenced from an object that is being reclaimed and is to be finalized. Decrement its rc and try to q it. it should stay in the zct called only from FinalizeReclaimedRef. May raise RCUnderflowOccurred. called only from FQImpl.EnableFinalization. May raise ZCTFull or RCUnderflowOccurred. no changes have been made NOTE if npr > 1 then this will be reported as a finalization error but shouldn't be. The (implementation) problem is that an RCUnderflowOccurred handler can't deal with npr > 1 called only from FQImpl.TryToQItForFinalization. May raise RCOverflowOccurred. NOTE if npr > 1 then this will be reported as a finalization error but shouldn't be. The (implementation) problem is that an RCOverflowOccurred handler can't deal with npr > 1 increment was NOT done The handler for RCOverflowOccurred makes adjustments, not changes 5. RC overflow ... called from RCOvImpl called only from RCOvImpl.HandleRCOverflow called only from RCOvImpl.HandleRCUnderflow 6. ZCT expansion. These are called during recovery from a ZCTFull signal. called from ExpandZCT and from PullNextEntry 7. Allocation, reclamation See AllocatorImpl.TAndSDoFreeNormalFragment 8. Utilities This may raise ZCTFull. See DISABLEMICROCODE, the ucode replacement for this guy cause rc operations to trap (except EnableMicrocode) See ENABLEMICROCODE, the ucode replacement for this guy END ENTRY PROCS TRAP HANDLERS handleRCUnderflow: decrement was NOT DONE handleRCUnderflow: decrement, assnmt were NOT DONE (this does the decrement, assigns NIL, then goes around again) read the alpha byte for the trapping opcode & add it to ptrRef END TRAP HANDLERS Κ ˜Jšœ ™ JšœJ™JJšœ,™,J™(˜šΟk ˜ Jšœ œ>˜MJšœ œQ˜cJšœœœœ˜IJšœœ1œ˜HJšœ œ(˜7Jšœ œ˜!Jšœ œ!˜/Jšœœ(˜;Jšœœ ˜Jšœœ œ œœ œœœyœ œ˜‘JšœœI˜bJšœœ ˜#Jšœ œ˜"Jšœ œ˜Jšœ œ˜(Jšœœ1˜9Jšœœά˜εJ˜——šœ œΟcJ˜\š˜Jšœ•œ˜œ—š˜Jšœ˜!——J˜Jšœœœ3œ˜EJ˜™ Jšœ œœ˜J™—™ Jšœœœ˜š Οnœœœœœ œ˜/Jšœ$™$Jšœœœ˜0—J˜šœ œ˜Jšœœ˜Jšœœ˜J˜—Jšœž˜*—˜J™—šœ ™ J˜™˜Jšœ1™1—šŸœœœ˜1šœ˜Jšœœ ˜+Jšœ˜Jšœ˜J˜—Jšœ˜Jšœ˜—˜Jšœ1™1—šŸ œœœœœœœœœ˜BJš œ œœœœ˜&Jšœ˜J˜—˜Jšœ1™1—šŸ œž œœœœœœœ˜Bšœ˜˜Jšœž,˜.Jšœœ˜.šœœ˜,Jšœ-™-—Jšœ œ ˜J˜—Jšœ˜š˜Jšœ-˜-Jšœ,ž"˜NJšœ˜—J˜—Jšœ˜Jšœ˜—˜Jšœ œ$™4Jšœν™ν—šŸœœœœœœœœœ˜Ošœ˜šœž*˜DJšœœ˜0Jšœ œ ˜Jšœœ ˜/Jšœ˜—Jšœ˜š˜Jšœ˜Jšœ,˜,—Jšœ˜—Jšœ˜Jšžœ)˜/Jšœ˜—J™J™Iproc™—™J™šŸœœœœ˜EJšœ œ˜š˜˜šœ$˜$šœœ˜3Jšœ œ ˜——Jšœ˜š˜Jšœ>˜>Jšœ˜——J˜—Jšœ˜Jšœ˜—J˜šΟb œœœ˜(Jšœ œ'˜<—J˜J™J™—šœ™K˜šŸœ œ˜!šŸœœœœ˜5Kšœ˜Kšœ˜šœ œœœ˜(Kš œœœ œœœ˜@—šœ˜Kšœœœžœ˜K—šœ˜Kšœ˜Kš œœœœœ˜x—Kšœ˜—šŸœœœ œœœœœ˜Cš œœœœœ˜!Kšœœœœœœœœ˜3—Kšœœœ˜šœ œœ˜š œœœ œœ˜+Kšœœœ ˜Kšœœ ˜:—Kšœ˜—Kšœ˜—Kšœ/˜/šœ:˜:Kšœœ4˜<—Kšœ/˜/Jšœž˜—J˜š Ÿœœœ œž˜UJšœœœœ˜(Jšœ œœœ˜šœ#œœ˜Fšœœ˜Jšœ™Jšœ˜šœœ˜Jšœœ ža˜ŒJšœ ˜ Jšœ˜Jšœ˜J˜Jš˜—šœœ˜ Jšœ$œ ˜2Jšœ˜Jšœ˜J˜Jšœ˜—šœ˜ Jšœ œž-˜@šœ ˜ šœ=˜?Jšœœ˜>—Jšœ@™@—šœž˜*šœœœž˜Cšœ˜Jšœ™Jšœœ ˜(Jšœ˜Jšœ˜J˜Jšœ˜———Jšœœ˜——Jšœ˜—Jšœž˜ ˜Jšœ7™7Jšœ.™.—šŸœœœ˜<šœ˜Jšœœœ˜/Jšœœ˜)—Jšœ˜—™Jšœœ$™6Jšœ'™'—šΠbnœœœ˜Gšœ˜Jšœ&œ ˜4Jšœ˜Jšœ˜Jšœ˜Jšœ˜—Jšœ˜—J™—šŸœœœž˜5Jšœœœœ˜(šœ#œœ˜Dšœœ˜Jšœ™šœœœ˜,š˜šœž˜Jšœœ ˜(Jšœ˜Jšœ˜J˜Jšœ˜————Jšœ˜—Jšœ˜Jšœ˜—˜Jšœ:™:Jšœ,œ™KJ™Jšœ9™9Jšœ?™?—š Ÿ œœœœœœ˜EJšœœ˜ š˜Jšœœ˜ Jš œ œœœž ˜+Jšœ˜Jš œ œœœœ˜%Jšœ#™#š œ œœ œœ˜BJšœ˜—š œœœœž$˜Ošœž ˜(Jšœ œž(˜8Jš œœœœœ˜EJš œ œœœœ ˜1Jšœ™Jšœ˜—šœ˜Jšœœœœ˜%Jšœ œž˜+Jšœœœž˜MJš œœœœœž ˜jJšœ˜——Jš˜—Jšœ˜—J™šŸ œ œ˜Jšœ œ˜Jšœ œ œ=˜YJšœœœœ'˜;Jšœ˜Jšœ4œž˜Lšœœœœ˜0Jš œœœœœž˜8—Jšœœ˜Jšœ œœ˜AJšœ˜—J˜šŸ œœ˜Jš œœ œœœœ ˜P—J˜Jšœ™J™—šœ ™ J™šœ8™8J˜JšŸœ œœœœœœ˜9J˜š Ÿœœœœœ˜3Jšœœ˜+Jšœ˜Jšœ˜Jšœ˜Jšœ˜—J™—šœ ™ ˜Jšœ"™"JšœΟiž’™?—šŸ œœœœœœœœ˜?Jšœœ˜+Jšœ˜Jš œ ˜Jšœ˜Jšœ˜—J˜—šœ ™ ˜Jšœ*™*Jšœ™—šŸ œœœ˜*Jšœœ˜+Jšœ˜Jš œ˜Jšœ˜Jšœ˜J˜—J™—šœ™J™šŸœœ œ˜-Jšœœ˜+Jšœ˜Jšœœ˜Jšœœœœ˜kJšœ˜Jšœ˜—J˜šŸœœ œ˜,Jšœœ˜+Jšœ˜Jšœœ˜Jšœ˜Jšœ˜—˜Jšœ/™/—šŸœœœœ˜GJšœœ˜+Jšœ˜Jšœœž"˜—Jšœ˜Jšœ˜Jšœ˜—˜JšœU™U—šŸœ œœœ˜DJšœœ˜+Jšœ ˜ Jšœ˜Jšœ œœœ˜!Jšœ˜Jš œ œ  œœœ˜=š œ œžœœ˜@Jšžœ™Jšœ°™°—Jšœ  œœ ž˜KJšœ˜Jšœœ˜ Jšœ)˜)Jšœ˜Jšœ˜—˜JšœO™O—šŸœ œœœ˜CJšœœ˜+Jšœ ˜ Jšœ˜Jš œ œœœœ˜%Jšœ˜šœœœ ˜š œœ œ œœœ˜DJšœ―™―—Jšœ™JšœA™A—Jšœ˜Jšœœ˜Jšœœ˜Jšœ˜Jšœ˜—J˜—šœ'™'™Jšœ*™*—š ‘œœœœ œ˜?Jšœ œœ˜"Jšœœ˜+Jšœ˜šœœ œ˜'Jšœ&˜&Jšœ œ˜Jšœ˜—Jšœ˜Jšœ˜—˜Jšœ+™+—š ‘œœœœ œ˜@Jšœ œœ˜"Jšœœ˜+Jšœ˜šœžœ˜Jšœ&˜&Jšœ œ˜Jšœ˜—Jšœ˜Jšœ˜J˜—J˜—šœI™I˜Jšœ,™,—š Ÿ œœœœœœ˜FJšœ œœ˜!Jšœœ˜+Jšœ˜šœœœ%ž˜Ošœ˜Jšœ˜š œ œœœœ˜EJš œœœœœœ˜$—Jšœ˜—Jšœ œ˜—Jšœ˜Jšœ˜J˜š Ÿ œœœœœœ ˜:Jš œ œœœœœ˜1Jšœœ˜7Jšœœœ˜Pš œœœœœ ˜,Jšœ˜šœœœœ˜Jšœ˜——Jšœ˜——J˜—šœ™J˜šŸœœœœ˜IJšœ œ˜Jšœœ˜+Jšœ˜Jšœœ ˜(Jšœ˜Jšœ˜—J˜š   Ÿœœœœ œ˜GJšœœ˜+Jšœ˜Jšœœ œ˜)Jšœ˜Jšœ˜—J˜šŸ œ œœ1˜PJšœœ˜+Jšœ˜Jšœ'˜'Jšœ˜Jšœ˜J˜—J˜Jšœ+™+šŸœ œœ*˜CJšœœ˜+Jšœ˜Jšœ'ž˜AJšœ'˜'Jšœ˜Jšœ˜J˜J˜—J˜—šœ ™ J˜šŸ œœœ˜Jšœœœ˜šœœ˜šœ˜JšœC˜CJšœ˜—Jšœœœ˜"Jšœ˜—š œ œœœœ˜>Jš œœœœœœ˜$—Jšœœ˜Jšœ˜Jšœœ˜Jšœ˜Jšœœœ˜Jšœ˜Jšœ˜Jšœ˜Jšœ˜—˜Jšœ™—š‘œœœ˜'Jšœœ˜+Jšœ˜Jšœ ˜ Jšœ˜Jšœ˜—™Jšœœ$™8—šŸœœœ˜8Jšœ4™4šœ˜Jšœœ˜)Jšœœ˜—Jšœœ˜Jšœ˜—™Jšœœ$™7—š Ÿœœœœ œ˜Ošœ˜Jšœœ˜4Jšœ œ˜&—Jšœœ˜Jšœ˜——J˜Jšœ™J™—™ J˜šŸœœœ˜:Jšœ˜Jšœœž˜šœœœœ˜Dš˜Jšœœž˜Jšœœ˜——Jšœ&ž˜9Jšœ œ˜4Jšœœ ž˜%Jšœ˜—J˜šŸœœœ˜5Jšœ œ ˜Jšœ˜Jšœœž˜šœœœœ˜Dš˜Jšœœž˜Jšœœ˜——Jšœ&ž˜9Jšœ œ˜4Jšœœ ž˜%Jšœ˜—J˜šŸœœœœ˜JJšœ˜Jšœœž˜šœœœœ˜Dš˜Jšœ(ž˜7šœž4˜;Jšœœœœ˜5J˜Jšœ œ˜4Jšœœ ž˜%Jšœ ž ˜J˜—šœž ˜Jšœœœœ˜5Jšœ ˜ Jšœ œ˜4Jšœœ ž˜%Jšœ˜J˜—Jšœ@ž ˜KJšœœ˜——Jšœ&ž˜9Jšœ œ˜4Jšœœ ž˜%Jšœ˜—J˜šŸœœœœœœœœœ˜KJšœ˜Jšœœž˜šœœœœ˜Dš˜Jšœ(ž˜7šœž4˜;Jš œœœœœœ˜4J˜Jšœ œ˜4Jšœœ ž˜%Jšœ ž ˜J˜—šœ˜Jšœ)™)Jš œœœœœœ˜4Jšœ˜Jšœ œ˜4Jšœœ ž˜%Jšœ ž ˜J˜—šœž ˜Jš œœœœœœ˜4Jšœ ˜ Jšœ œ˜4Jšœœ ž˜%Jšœ˜J˜—Jšœ>ž ˜IJšœ ž˜>Jšœœ˜——Jšœ&ž˜9Jšœ œ˜4Jšœœ ž˜%Jšœ˜—J˜šŸ œœœ˜-Jšœ˜Jšœœž˜šœœœœ˜Dš˜Jšœž˜.šœž4˜;Jšœœœœ˜5J˜Jšœ œ˜4Jšœœ ž˜%Jšœ˜J˜—šœž ˜Jšœœœœ˜5Jšœ ˜ Jšœ œ˜4Jšœœ ž˜%Jšœ˜J˜—Jšœœ˜——Jšœ&ž˜9Jšœ œ˜4Jšœœ ž˜%Jšœ˜—J˜šŸ œœœ œ œœœœ˜HJšœ˜Jš œ œœœœ˜Jšœœž˜Jšœ?˜?šœœœœ˜Dš˜Jšœ$ž˜3šœž4˜;š œœ œ œœœœ˜1Jšœœœ˜—Jšœ˜Jšœ œ˜4Jšœœ ž˜%Jšœž ˜ J˜—šœž4˜;š œœ œ œœœœ˜1Jšœœœ˜—J˜Jšœ œ˜4Jšœœ ž˜%Jšœž ˜ J˜—šœ˜Jšœq™qš œœ œ œœœœ˜1Jšœœœ˜—Jšœ˜Jšœ œ˜4Jšœœ ž˜%Jšœž ˜ J˜—šœž ˜š œœ œ œœœœ˜1Jšœœœ˜—Jšœ ˜ Jšœ œ˜4Jšœœ ž˜%Jšœž ˜ J˜—Jšœ:ž ˜GJšœœ˜——Jšœ&ž˜9Jšœ œ˜4Jšœœ ž˜%Jšœ˜—˜Jšœ>™>š Ÿ œœ œœœœ˜KJš œœœœœ˜!š œœœœœœœ ˜2Jšœœœ˜C—Jšœ-˜-Jšœœ˜!Jšœ˜J˜——J™—J˜J˜ J˜—Jšœ˜J˜J˜—…—PX€ύ