-- RTReclaimerImpl.Mesa-- last edited On 15-Oct-81 12:57:29 by Willie-Sue Haugeland-- last edited On February 24, 1983 12:17 pm by Paul RovnerDIRECTORY  Inline USING[BITAND, LongNumber, BITOR, LowHalf],  NewRCMapOps USING[GetBase],  PrincOps USING[StateVector],  Process USING[Yield],  RCMap USING[Index, Base],  Rope USING[RopeRep, ROPE],  RTBasic USING[Pointer],  RTFlags USING[clearing, checking, useMicrocode],  RTMicrocode USING                   [RECLAIMEDREF, ALTERCOUNT, ISPIRECLAIMABLE, GETREFERENTTYPE,                    FREEOBJECT, PPALTERCOUNT, FREEPREFIXEDNODE, FREEQUANTIZEDNODE,                    LONGZERO],  RTOS USING[MyLocalFrame],  RTRefCounts USING                   [rcoState, RefCt, rcAbsent, rcoFinalizedRef, ReclaimedRef,                    rcoDeleteRef, useUCodedGC, AlterCountEntry,                    nObjectsReclaimed, nWordsReclaimed, ProbeIndex, IsPiReclaimable,                    nRCEntry, GCState, MapRcePiRef, rcFinalize, --IsOiCushion,--                    DisableRC, GCMicrocodeExists],  RTStorageOps USING[OutOfOverflowTable],  RTTypesBasic USING[Type, GetReferentType],  RTTypesBasicPrivate USING                   [NPackageRefs, MapTiRcmx, PutForFinalization, DoFREEify,                    useCanonicalTypeMicroCode],  RTZones USING                   [PZone, SubZone, PFreeNode, PQuantizedZone,                    FromCollectibleZone, MapPtrZf, NodeLength, sizeNd, PNode,                    MapSziSz, ZoneFinger, MapZiZn, GetSzZi, FreeList, PPrefixedZone],  Runtime USING[CallDebugger],  SSExtra USING[useSizeToZn],  TrapSupport USING[BumpPC, GetTrapParam];RTReclaimerImpl: MONITOR  -- protects zones  LOCKS zn.LOCK USING zn: PZone  IMPORTS Inline, Process, NewRCMapOps, RTMicrocode, RTOS,             RTRefCounts, RTStorageOps, RTTypesBasic, RTTypesBasicPrivate,             RTZones, Runtime, TrapSupport  EXPORTS RTRefCounts, RTZones  SHARES Rope   = BEGIN OPEN RTBasic, RTFlags, RTMicrocode, RTRefCounts, RTStorageOps,                 RTTypesBasic, RTTypesBasicPrivate, RTZones;  -- GLOBAL VARIABLES  rcmb: RCMap.Base = NewRCMapOps.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 {Runtime.CallDebugger["BadRCEntry"];                    WHILE TRUE DO Process.Yield[]; ENDLOOP};          refType _ GetRefType[ref];          IF rc = (rcFinalize - NPackageRefs[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: Inline.LongNumber] RETURNS[BOOLEAN] =         INLINE {RETURN[Inline.BITAND[ptr.highbits, BackPointerMarkBit] # 0]};      MarkBackPointer: PROC[ptr: Inline.LongNumber] RETURNS[Inline.LongNumber] =         INLINE {ptr.highbits _ Inline.BITOR[ptr.highbits, BackPointerMarkBit]; RETURN[ptr]};      UnmarkBackPointer: PROC[ptr: Inline.LongNumber] RETURNS[Inline.LongNumber] =         INLINE {ptr.highbits _ Inline.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 NPackageRefs[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: 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 SSExtra.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 GETREFERENTTYPE[ref]                       ELSE GetReferentType[ref]]};  -- *** The reclaimer (end)  -- NOTE copied in RTTraceAndSweepImpl  INLFreeObject: PROC[ptr: 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 =>  {size: CARDINAL = MapSziSz[mz.szi].size;                  nWordsReclaimed _ nWordsReclaimed + size;                  IF clearing THEN [] _ LONGZERO[ptr, size]};       prefixed =>                 {size: CARDINAL = Inline.LowHalf[NodeLength[LOOPHOLE[ptr-sizeNd, PNode]]];                  nWordsReclaimed _ nWordsReclaimed + size;                  IF clearing THEN [] _ LONGZERO[ptr, size-sizeNd]};      ENDCASE => ERROR;     IF useFreeUCode THEN FREEOBJECT[ptr] ELSE DoFreeObject[ptr]}; --  if FREEOBJECT is not implemented  FreeObjectTrap: PUBLIC PROC[ptr: 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[RTOS.MyLocalFrame[]];     TRANSFER WITH state;   -- incantation   };  -- NOTE copied in RTTraceAndSweepImpl  DoFreeObject: PROC[ptr: 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 => FreeQuantizedNode[ptr, LOOPHOLE[MapZiZn[GetSzZi[mz.szi]]], MapSziSz[mz.szi]];        prefixed => FreePrefixedNode[ptr, LOOPHOLE[MapZiZn[mz.zi]]];       ENDCASE};-- OBJECT FREEING  -- *** The Quantum Object Free-er  FreeQuantizedHeapObject: PUBLIC PROC[self: LONG POINTER TO PQuantizedZone,                                       object: LONG POINTER] =   { IF checking      THEN {IF object = NIL                THEN {Runtime.CallDebugger["Attempt to FREE NIL; Proceed at your peril"];                         RETURN};               IF FromCollectibleZone[LOOPHOLE[object, REF ANY]]                THEN DO Runtime.CallDebugger                                  ["Attempt to treat a REF as if from an uncounted zone"];                        ENDLOOP};     IF useFreeUCode      THEN FREEQUANTIZEDNODE[object, self^]      ELSE FreeQuantizedNode[object,                                    self^,                                    MapSziSz[LOOPHOLE[MapPtrZf[object], sub ZoneFinger].szi]]};  -- NOTE copied in RTTraceAndSweepImpl  FreeQuantizedNode: ENTRY PROC[ptr: Pointer, zn: PZone, sz: SubZone] =INLINE   {LOOPHOLE[ptr, FreeList]^ _ sz.fl; sz.fl _ ptr}; --  if FREEQUANTIZEDNODE is not implemented  FreeQuantizedNodeTrap: PUBLIC PROC[ptr: 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;          FreeQuantizedNode[ptr, zn, MapSziSz[LOOPHOLE[MapPtrZf[ptr], sub ZoneFinger].szi]];     TrapSupport.BumpPC[2];     state.dest_ LOOPHOLE[RTOS.MyLocalFrame[]];     TRANSFER WITH state;   -- incantation   };  -- *** The Quantum Object Free-er (end)  -- *** 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: 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[RTOS.MyLocalFrame[]];      TRANSFER WITH state;   -- incantation    };  -- NOTE copied in RTTraceAndSweepImpl  FreePrefixedNode: ENTRY PROC[ptr: 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.      Э╩U  Ш JЪЦ╧cСЬ╧k	Ь
ЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬ2ЮЬЮЬЮ
ЬЮЬЮЬЮ
ЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬдЭЬCЮЬ%ЮЬ/ЮЬЗЮЬюЮЬЮЬЮЬ*ЮЬЭЬЮЬЮЬЮЬЮЬ,ЮЬzЮЬЮЬЮЬЮЬ{ЭЬAЮЬЭ	ЬЭЬ╧nЬЮЬЮЬЭ/Ь!ЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬ ЮЬЮЬЮЬ
ЮЬCЮЬЮЬsЮЬ
ЮЬЮЬ:ЮЬЮЬЮЬЮЬ3ЮЬ+ЮЬЭЬ@ЭYЬЮЬЮЬЮЬЭЬЮЬ2ЮЬJЮЬЭЬЮЬЮЬЮЬ#ЮЬ1ЮЬЮЬЮЬЮЬ
ЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬ#Я
ЬЮЬЮЬЮЬЮЬЮЬЮЬ'ЮЬЭ,ЬЮЬЮЬЮЬЭЬЮЬ/ЮЬЮЬЮЬЮЬЮЬЯЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬ)ЮЬЯЬЮЬЮЬЮЬЮЬЮЬЮЬ0ЯЬЮЬЮЬЮЬЮЬ$ЮЬЯЬЮЬЮЬЮЬЮЬ:ЮЬЮЬЮЬЮЬЮЬЮЬ	ЮЬЭЬЮЬЮЬЮЬЭЬЮЬЮЬЮЬЮЬЯЬЮЬЮЬЮЬ!Я	ЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬ
ЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬ$ЮЬЮЬЮЬЭOЬJЮЬ,ЮЬЮЬЮЬCЮЬ!ЮЬ.ЮЬЮ
Ь;ЮЬ?ЮЬЮЬ	ЮЬЮЬЮЬ ЯЬЮЬЮЬЮЬЮЬЮЬ ЮЬЮЬ7ЮЬЮЬHЮЬLЯЬЮЬ2Э2Ь
ЮЬЮЬЮЬЮЬ:ЮЬЮЬЮЬЮЬЮЬ(ЮЬЮЬЮЬЮЬЮЬЮЬЮЬ ЮЬEЮЬЮЬЮЬЮЬЮЬЮЬEЮЬЮЬЮЬЮЬЮЬЮЬ$ЮЬЮЬ/Э3Ь
ЮЬЮЬЮЬЭЬЮЬЮЬЮЬЮЬЮЬЮЬ*ЮЬ>ЮЬЮЬЮЬ8ЮЬSЮЬTЮЬTЮЬHЮЬЮЬ"ЮЬЮЬЮЬ-ЮЬЮЬЮЬЮЬЮЬЮЬ_ЮЬЭЬ	ЮЬЭЬ
ЮЬЮЬЮЬЮЬ#ЮЬЮЬЮЬЭ+ЬЮЬЮЬ?ЮЬЮЬЮЬЮЬЮЬЮЬЮЬЭЬ,ЮЬЭЬЭЬЯ
ЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬ2ЮЬЮЬЮЬЭЬЭ&ЬЯЬЮЬЮЬ*ЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬ8ЮЬЮЬЮЬЮЬhЮЬ
ЮЬЮЬ9ЮЬЮЬeЮЬ
ЮЬЮЬЮЬЮЬЮЬЮЬЮ
ЬЮЬЭ%ЬЯЬЮЬЮЬ?ЮЬЮЬЭЬЮЬЮЬЮЬ
ЮЬЮЬЮЬЮЬGЮЬЮЬЮЬЮЬ
ЭЬ	Э&ЬЯЬЮЬЮЭЬЮЬ
ЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬ#ЮЬЮЬЮЬ'ЮЬYЮЬЮЬЭЬЭ"ЬЯЬЮЬЮЬЮЬЮЬЮЬ@ЮЬЮЬ	ЮЬЮЬЮЬ
ЮЬЮЬ_ЮЬЮЬЮЬ	ЮЬЮЬЮЬЮЬЙЮЬЮЬЮЬЮЬЮЬsЮЬ.Э&ЬЯЬЮЬЮЬ)ЮЭЬЮЬ*Э,ЬЯЬЮЬЮЬJЮЬЮЬЭЬЮЬЮЬЮЬ
ЮЬЮЬЮЬЮЬ*ЮЬUЮЬЮЬЮЬЮЬ
ЭЬ	Э(ЬЭ#ЬЯЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬ	ЮЬ
ЮЬЮЬ
ЮЬЮЬЮЬЮЬЮЬ	ЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬ%Э+ЬЯЬЮЬЮЬLЮЬЮЬЭЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬRЮЬЮЬЮЬЮЬ
ЭЬ
Э&ЬЯЬЮЬЮЬЮЬЮЬЭ7ЬЯЬЮЬЮЬжЭ)ЬЭЬ ЮЬ!ЮЬШщlЧ ЕЧ    6l  >╟  