-- RTReclaimerImpl.Mesa -- last edited On 15-Oct-81 12:57:29 by Willie-Sue Haugeland -- last edited On June 14, 1983 9:38 am by Paul Rovner -- Last Edited by: Levin, August 8, 1983 5:28 pm DIRECTORY Basics USING [LongNumber], DebuggerSwap USING[CallDebugger], RCMapOps USING[GetBase], PrincOps USING[StateVector], PrincOpsUtils USING[BITAND, BITOR, MyLocalFrame, ZERO], Process USING[Yield], RCMap USING[Index, Base], Rope USING[RopeRep, ROPE], RTFlags USING[clearing, checking, useMicrocode], RTMicrocode USING [ALTERCOUNT, FREEOBJECT, FREEPREFIXEDNODE, GETCANONICALREFERENTTYPE, ISPIRECLAIMABLE, PPALTERCOUNT, RECLAIMEDREF], RTRefCounts USING [rcoState, RefCt, rcAbsent, rcoFinalizedRef, ReclaimedRef, rcoDeleteRef, useUCodedGC, AlterCountEntry, nObjectsReclaimed, nWordsReclaimed, ProbeIndex, IsPiReclaimable, nRCEntry, GCState, MapRcePiRef, rcFinalize, --IsOiCushion,-- DisableRC, GCMicrocodeExists], RTTypesBasicPrivate USING [NumberPackageRefs, MapTiRcmx, PutForFinalization, DoFREEify, useCanonicalTypeMicroCode], RTZones USING [FromCollectibleZone, MapPtrZf, MapZiZn, NodeLength, PFreeNode, PNode, PPrefixedZone, PZone, sizeNd, useSizeToZn, ZoneFinger], SafeStorage USING[Type, GetReferentType], SafeStoragePrivate USING[OutOfOverflowTable], SSTraps USING[], TrapSupport USING[BumpPC, GetTrapParam]; RTReclaimerImpl: MONITOR -- protects zones LOCKS zn.LOCK USING zn: PZone IMPORTS DebuggerSwap, PrincOpsUtils, Process, RCMapOps, RTMicrocode, RTRefCounts, SafeStoragePrivate, RTTypesBasicPrivate, RTZones, SafeStorage, TrapSupport EXPORTS RTRefCounts, RTZones, SSTraps SHARES Rope = BEGIN OPEN RTFlags, RTMicrocode, RTRefCounts, RTTypesBasicPrivate, RTZones, SafeStorage, SafeStoragePrivate; -- GLOBAL VARIABLES rcmb: RCMap.Base = RCMapOps.GetBase[].base; useFreeUCode: BOOLEAN _ RTFlags.useMicrocode; -- PROCS -- *** The reclaimer MapReclaimableObjects: PUBLIC PROC = -- process finalizable and reclaimable objects { pi: ProbeIndex _ 0; DO npi: CARDINAL; noneReclaimed: BOOLEAN _ TRUE; [pi, npi]_ (IF useUCodedGC THEN ISPIRECLAIMABLE[pi] ELSE IsPiReclaimable[pi]); FOR i: CARDINAL IN [0..npi) DO rce: nRCEntry _ GCState.rceToReclaim[i]; ref: REF ANY _ MapRcePiRef[rce, pi]; rc: RefCt_ rce.rc; refType: Type; rco: rcoState; IF checking AND rc = 0 THEN {DebuggerSwap.CallDebugger["BadRCEntry"]; WHILE TRUE DO Process.Yield[]; ENDLOOP}; refType _ GetRefType[ref]; IF rc = (rcFinalize - NumberPackageRefs[refType]) THEN -- reclaim it { rco _ [rcChange: rcAbsent - rc, onStack: false]; -- use ALTERCOUNT to change the RefCt to absent, so entry will be taken out of the table IF useUCodedGC THEN PPALTERCOUNT[rco, ref] -- can fail if error in table ELSE AlterCountEntry[rco, ref ! OutOfOverflowTable => GOTO disableRC]; Reclaim[ref, refType ! OutOfOverflowTable => GOTO disableRC]; -- can fail noneReclaimed _ FALSE; } ELSE IF rc = rcFinalize AND FinalizeIt[ref, refType ! OutOfOverflowTable => GOTO disableRC] THEN noneReclaimed _ FALSE; ENDLOOP; IF noneReclaimed THEN IF pi = LAST[ProbeIndex] THEN RETURN ELSE pi _ pi + 1; ENDLOOP; EXITS disableRC => DisableRC[] }; FinalizeIt: PROC[ref: REF ANY, refType: Type] RETURNS[BOOLEAN] = { IF PutForFinalization[refType, ref] THEN -- PutForFinalization does no RC operations {IF useUCodedGC THEN PPALTERCOUNT[rcoFinalizedRef, ref] -- can fail ELSE AlterCountEntry[rcoFinalizedRef, ref]; RETURN[TRUE]} ELSE RETURN[FALSE]}; Reclaim: PROC[ref: REF ANY, refType: Type] = INLINE { PAPtr: TYPE = LONG POINTER TO ARRAY OF LONG UNSPECIFIED; BackPointerMarkBit: CARDINAL = 100000B; BackPointerUnmarkMask: CARDINAL = 77777B; IsBackPointer: PROC[ptr: Basics.LongNumber] RETURNS[BOOLEAN] = INLINE {RETURN[PrincOpsUtils.BITAND[ptr.highbits, BackPointerMarkBit] # 0]}; MarkBackPointer: PROC[ptr: Basics.LongNumber] RETURNS[Basics.LongNumber] = INLINE {ptr.highbits _ PrincOpsUtils.BITOR[ptr.highbits, BackPointerMarkBit]; RETURN[ptr]}; UnmarkBackPointer: PROC[ptr: Basics.LongNumber] RETURNS[Basics.LongNumber] = INLINE {ptr.highbits _ PrincOpsUtils.BITAND[ptr.highbits, BackPointerUnmarkMask]; RETURN[ptr]}; prev: LONG POINTER TO REF _ NIL; DO -- outer loop UNTIL ref = NIL DO -- inner loop 1 nextx: CARDINAL _ 0; first: REF ANY _ NIL; FreeRef: PROC[ref: REF ANY] = {DoFreeRef[ref]}; DoFreeRef: PROC[ref: REF ANY] = INLINE { refToFree: REF ANY; IF ref = NIL THEN RETURN; IF checking AND NOT FromCollectibleZone[ref] THEN ERROR; refToFree _ (IF useUCodedGC THEN RECLAIMEDREF[ref] ELSE ReclaimedRef[ref]); IF refToFree # NIL THEN -- got another. refToFree is NOT in the table, but would have an rc=rcFinalize { type: Type = GetRefType[refToFree]; IF NumberPackageRefs[type] # 0 THEN {IF NOT PutForFinalization[type, refToFree] THEN {IF useUCodedGC THEN ALTERCOUNT[rcoDeleteRef, refToFree] ELSE AlterCountEntry[rcoDeleteRef,refToFree]}} ELSE {IF first = NIL THEN first _ refToFree ELSE Push[refToFree]}}}; Push: PROC[r: REF ANY] = INLINE {IF nextx = 0 THEN {LOOPHOLE[ref, PAPtr][nextx] _ LOOPHOLE[MarkBackPointer[LOOPHOLE[prev]]]; nextx _ 1}; LOOPHOLE[ref, PAPtr][nextx] _ r; nextx _ nextx + 1}; FREEify: PROC[ptr: LONG POINTER, rcmx: RCMap.Index] = -- low index to high. DoFreeRef for ea. inner ref INLINE {WITH rcmr: rcmb[rcmx] SELECT FROM simple => FOR i: CARDINAL IN [0..rcmr.length) DO IF rcmr.refs[i] THEN {DoFreeRef[LOOPHOLE[ptr+i, LONG POINTER TO REF ANY]^]}; ENDLOOP; oneRef => DoFreeRef[LOOPHOLE[ptr+rcmr.offset, LONG POINTER TO REF ANY]^]; ref => DoFreeRef[LOOPHOLE[ptr, LONG POINTER TO REF ANY]^]; null => NULL; ENDCASE => DoFREEify[ptr, rcmx, FreeRef]}; -- ***Start this iteration of inner loop 1 Here*** IF useSizeToZn AND refType = CODE[Rope.RopeRep] -- XXX THEN refType _ WITH t: LOOPHOLE[ref, Rope.ROPE] SELECT FROM text => CODE[Rope.RopeRep.text], node => WITH v: t SELECT FROM substr => CODE[Rope.RopeRep.node.substr], concat => CODE[Rope.RopeRep.node.concat], replace => CODE[Rope.RopeRep.node.replace], object => CODE[Rope.RopeRep.node.object], ENDCASE => ERROR, ENDCASE => ERROR; FREEify[LOOPHOLE[ref], MapTiRcmx[refType]]; IF nextx = 0 THEN INLFreeObject[LOOPHOLE[ref]] ELSE prev _ LOOPHOLE[@LOOPHOLE[ref, PAPtr][nextx - 1]]; ref _ first; refType _ GetRefType[ref]; ENDLOOP; -- inner loop 1 DO -- inner loop 2 IF prev = NIL THEN RETURN; ref _ prev^; IF IsBackPointer[LOOPHOLE[ref]] THEN -- it's a back pointer; container is empty {ref _ LOOPHOLE[UnmarkBackPointer[LOOPHOLE[ref]]]; INLFreeObject[prev]; prev _ LOOPHOLE[ref]} ELSE {prev _ prev - SIZE[REF ANY]; EXIT} ENDLOOP; -- inner loop 2 refType _ GetRefType[ref]; ENDLOOP; -- outer loop }; -- end Reclaim GetRefType: PROC[ref: REF ANY] RETURNS[type: Type] = INLINE { RETURN[IF useCanonicalTypeMicroCode THEN GETCANONICALREFERENTTYPE[ref] ELSE GetReferentType[ref]]}; -- *** The reclaimer (end) -- NOTE copied in RTTraceAndSweepImpl INLFreeObject: PROC[ptr: LONG POINTER] = INLINE {mz: ZoneFinger = MapPtrZf[ptr]; IF checking THEN {IF ptr = NIL THEN ERROR; IF NOT FromCollectibleZone[LOOPHOLE[ptr, REF ANY]] THEN ERROR}; nObjectsReclaimed _ nObjectsReclaimed + 1; WITH mz: mz SELECT FROM sub => ERROR; prefixed => {size: CARDINAL = NodeLength[LOOPHOLE[ptr-sizeNd, PNode]]; nWordsReclaimed _ nWordsReclaimed + size; IF clearing THEN [] _ PrincOpsUtils.ZERO[ptr, size-sizeNd]}; ENDCASE => ERROR; IF useFreeUCode THEN FREEOBJECT[ptr] ELSE DoFreeObject[ptr]}; -- if FREEOBJECT is not implemented FreeObjectTrap: PUBLIC PROC[ptr: LONG POINTER] = { state: PrincOps.StateVector; param: CARDINAL; state_ STATE; -- incantation param _ IF useFreeUCode THEN TrapSupport.GetTrapParam[] ELSE 0; IF param = 0 THEN useFreeUCode _ FALSE; DoFreeObject[ptr]; TrapSupport.BumpPC[2]; state.dest_ LOOPHOLE[PrincOpsUtils.MyLocalFrame[]]; TRANSFER WITH state; -- incantation }; -- NOTE copied in RTTraceAndSweepImpl DoFreeObject: PROC[ptr: LONG POINTER] = INLINE { mz: ZoneFinger; IF checking THEN { IF ptr = NIL THEN ERROR; IF NOT FromCollectibleZone[LOOPHOLE[ptr, REF ANY]] THEN ERROR}; mz _ MapPtrZf[ptr]; WITH mz: mz SELECT FROM sub => ERROR; prefixed => FreePrefixedNode[ptr, LOOPHOLE[MapZiZn[mz.zi]]]; ENDCASE}; -- OBJECT FREEING -- *** The Prefixed Object Free-er FreePrefixedHeapObject: PUBLIC PROC[self: LONG POINTER TO PPrefixedZone, object: LONG POINTER] = { IF checking THEN { IF object = NIL THEN ERROR; IF FromCollectibleZone[LOOPHOLE[object, REF ANY]] THEN ERROR; WITH self.linkage SELECT FROM heap => IF typeRepresentation THEN ERROR; ENDCASE => ERROR}; IF useFreeUCode THEN FREEPREFIXEDNODE[object, self^] ELSE FreePrefixedNode[object, self^]}; -- if FREEPREFIXEDNODE is not implemented FreePrefixedNodeTrap: PUBLIC PROC[ptr: LONG POINTER, zn: PZone] = { state: PrincOps.StateVector; param: CARDINAL; state _ STATE; -- incantation param _ IF useFreeUCode THEN TrapSupport.GetTrapParam[] ELSE 0; IF param = 0 THEN useFreeUCode _ FALSE; FreePrefixedNode[ptr, zn]; TrapSupport.BumpPC[2]; state.dest_ LOOPHOLE[PrincOpsUtils.MyLocalFrame[]]; TRANSFER WITH state; -- incantation }; -- NOTE copied in RTTraceAndSweepImpl FreePrefixedNode: ENTRY PROC[ptr: LONG POINTER, zn: PZone] = INLINE {LinkHeapNode[ptr-sizeNd, @LOOPHOLE[zn, PPrefixedZone].fnd]}; -- NOTE copied in RTPrefAllocImpl, RTTraceAndSweepImpl LinkHeapNode: PROC[pfn, pfnPrev: PFreeNode] = INLINE {pfnNext: PFreeNode = pfnPrev.pfnNext; pfn.body _ free[pfnPrev: pfnPrev, pfnNext: pfnNext]; pfnNext.pfnPrev _ pfn; pfnPrev.pfnNext _ pfn}; -- *** The Prefixed Object Free-er (end) -- START HERE useFreeUCode _ useFreeUCode AND RTRefCounts.GCMicrocodeExists; END.