-- RTRefCountsImpl.Mesa
-- last edited August 30, 1982 10:39 am by Willie-Sue
-- last edited February 16, 1983 11:31 am by Paul Rovner

DIRECTORY
  Environment USING [Byte],
  Frame USING[GetReturnLink],
  MiscAlpha USING[alpha],
  Mopcodes USING[zMISC],
  Inline USING[BITAND, BITOR, BITSHIFT, LowHalf, HighHalf, --LongNumber, -- BITXOR],
  PrincOps USING[ControlLink, StateVector],
  Process USING [Detach, Yield, SetPriority, priorityBackground],
  PSB USING[PsbIndex],
  RTBasic USING[Pointer, Address],
  RTCommon USING[--ShortenLongCardinal,-- RepAddrRef],
  RTFlags USING[takingStatistics, checking, useMicrocode],
  RTMicrocode USING[RTMOVESTATUS, microcodeVersion, ASSIGNREF, ASSIGNREFNEW,
                          ALTERCOUNT, RESETSTKBITS],
  RTOS USING[AllocateFrameBodyBuffer, FrameCopySpaceTooSmall, SnapshotTheFrameHeap,
                 MapRCFrameBodies, InMDS , GetDataPagesForGCTables,
                 MyLocalFrame, UnregisterCedarProcess, GetCurrent],
  RTQuanta USING[LASTAddress],
  RTRefCounts,
  RTSD USING[SD, sRTState],
  RTStorageAccounting USING[ResetNWordsAllocated, ResetTotalNWordsAllocatedOnly,
                                    nObjectsCreated],
  RTStorageOps USING[],
  RTTypesBasic USING[Type],
  RTTypesBasicPrivate USING[RMapTiTd, GetMapTiTd],
  RTZones USING[PMapZiZn, RMapSziSz, RMapQZf],
  RuntimeInternal USING[Codebase],
  SafeStorage USING[TrimAllZones, TrimRootBase, ReclamationReason, NWordsAllocated,
                        MergeAllPrefixedZones],
  SSExtra USING[useSizeToZn],
  TrapSupport USING[BumpPC, GetTrapParam];

RTRefCountsImpl: MONITOR        --protects the RCTable--
  IMPORTS Frame, Inline, Process, RuntimeInternal, RTCommon, RTMicrocode, RTOS, RTRefCounts,
             RTStorageAccounting, RTTypesBasicPrivate, SafeStorage, TrapSupport
  EXPORTS SafeStorage, RTStorageOps, RTRefCounts
= BEGIN
  OPEN PrincOps, RTCommon, RTBasic, SafeStorage, RTStorageOps, RTRefCounts, RTMicrocode,
         RTZones, RTTypesBasicPrivate;

  Type: TYPE = RTTypesBasic.Type;

-- Signals
  WrongMicrocodeVersion: ERROR[expectedVersion, actualVersion: CARDINAL] = CODE;
  BugFoundNewObject: SIGNAL[ref: REF] = CODE;
  OutOfOverflowTable: PUBLIC ERROR = CODE;
  NegativeRC: ERROR[ref: REF] = CODE;
  RceNotReclaimable: ERROR[nrce: nRCEntry] = CODE;

-- Signals (for debugging)
  AlterSuspectCount: SIGNAL[suspect: LONG POINTER] = CODE;
  piEQqProbe: SIGNAL = CODE;
  CheckRceError: SIGNAL = CODE;
  badOverflowEntry: SIGNAL = CODE;
  ErrorHalt:  SIGNAL = CODE;

-- System tables
  MapPiRce: LONG POINTER TO AMapPiRce;
  MapOiOe: LONG POINTER TO AMapOiOe;
  GCState: PUBLIC LONG POINTER TO AGCState;

-- variables for debugging
  qProbe: CARDINAL _ 177777B;  -- won't match any probe 'til set
  
  suspect: LONG POINTER _ NIL;
  takingStatistics: BOOLEAN = RTFlags.takingStatistics;
  checking: BOOLEAN = RTFlags.checking;

-- Other global variables
  undoStackBit: gcRState = [ fill0: 1, useStack: false, fill: 177B];    -- 177377B; turn off stack bit
  useUCodedGC: PUBLIC BOOLEAN _ RTFlags.useMicrocode;
  GCMicrocodeExists: PUBLIC BOOLEAN _ FALSE;
  nObjectsReclaimed: PUBLIC Count _ 0;
  nWordsReclaimed: PUBLIC Count _ 0;

  collectorRunning: BOOLEAN _ FALSE;
  alwaysTrim: BOOLEAN _ FALSE;
  trimZonesNeeded: BOOLEAN _ FALSE;
  frameBodyBufferPages: PUBLIC CARDINAL _ 40;
    -- Shared with TandS. May grow.

  nObjectsReclaimedAsOfThen, nWordsReclaimedAsOfThen: Count;  -- args to background collector

  tAndSToRun: BOOLEAN _ FALSE;
  collectorToRun: BOOLEAN _ FALSE;
  collectorProcess: PROCESS;

-- Condition variables
  CollectionInitiated: CONDITION;
  CollectionFinished: CONDITION;
  CollectorNeeded: CONDITION;

  OiFreed: CONDITION;
  TrimZonesFinished: CONDITION;


-- Statistics
        -- "= FALSE" suppresses compilation of statistics code
  Count: TYPE = LONG CARDINAL;

  CollectorInfo: TYPE =
    RECORD[incarnation: CARDINAL _ 0,
           reason: SafeStorage.ReclamationReason _ allocationInterval,
           wordsAllocated: LONG CARDINAL _ 0,
           objectsAllocated: LONG CARDINAL _ 0,
           totalWordsAllocated: LONG CARDINAL _ 0,  -- when collection started
           totalObjectsAllocated: LONG CARDINAL _ 0,
           wordsReclaimed: LONG CARDINAL _ 0,
           objectsReclaimed: LONG CARDINAL _ 0
          ];
  collectorIncarnation: CARDINAL _ 0;
  previousInfo: CollectorInfo _ [];
  currentInfo: CollectorInfo _ [];
  
  Bump: PROC[p: POINTER TO Count, delta: Count _ 1] =
    INLINE {IF takingStatistics THEN p^ _ p^+delta};

  RCStatsRec: TYPE = RECORD
    [ nCreated: Count _ 0,
      nFoundEmpty: Count _ 0,
      nFoundEntry: Count _ 0,
      nMissedEntry: Count _ 0,
      nFoundChain: Count _ 0,
      nStepsFoundChain: Count _ 0,
      nMissedChain: Count _ 0,
      nStepsMissedChain: Count _ 0,
      nRefCtMax: Count _ 0,
      nCreateOi: Count _ 0,
      nFreeOi: Count _ 0,
      nOutOfOverflowTable: Count _ 0,
      nReclaimable: Count _ 0,
      nResetDeleted: Count _ 0,
      nGFT: Count _ 0,
      nFrames: Count _ 0,
      nRefs: Count _ 0,
      nNonRefs: Count _ 0,
      nShortRefs: Count _ 0,
      nShortNonRefs: Count _ 0,
      nMapCalls: Count _ 0,
      frameCopySpaceExpanded: LONG CARDINAL _ 0,
      reclamationReasons: ARRAY ReclamationReason OF Count _ ALL[0]
    ];

  Stats: RCStatsRec _ [];  -- the one and only

--//////////////
-- PROCs for turning off reference counting

DisableReferenceCounting: PUBLIC ENTRY PROC =
    {ENABLE UNWIND => NULL;
     WHILE GCState.GCStateBasic.reclaimState = gcRunning
       DO WAIT CollectionFinished ENDLOOP;
     DoDisableReferenceCounting[]};

DisableRC: PUBLIC ENTRY PROC = {ENABLE UNWIND => NULL; DoDisableReferenceCounting[]};

DoDisableReferenceCounting: INTERNAL PROC =
    { GCState.GCStateBasic.reclaimState _ gcStopped;
             -- disable subsequent RC operations and collection
      GCState.GCStateBasic.collector _ NIL;
      []_ RTMOVESTATUS[toMemory, 0];
      previousInfo _ currentInfo;
      BROADCAST CollectionFinished};
--//////////////

SetAlwaysTrim: PUBLIC ENTRY PROC[sense: BOOLEAN] = {alwaysTrim _ sense};

--//////////////
-- initialization from other modules
StuffMapZiZn: PUBLIC PROC[p: LONG POINTER TO RTZones.PMapZiZn] =
   {GCState.GCStateBasic.mapZiZn _ p};
StuffMapSziSz: PUBLIC PROC[p: LONG POINTER TO RTZones.RMapSziSz] =
   {GCState.GCStateBasic.mapSziSz _ p};
StuffMapQZf: PUBLIC PROC[p: LONG POINTER TO RTZones.RMapQZf] =
   {GCState.GCStateBasic.mapQZf _ p};

--//////////////



--//////////////
-- AssignRef, AssignRefNew, CreateRef and friends. These go into the SD

-- For AssignRef and AssignRefNew, if the software is in use, and OutOfOverflowTable is raised, then
-- a collection will be initiated
-- after the stack is unwound (the stack is unwound to exit the monitor). If tracing the stack then
-- raises OutOfOverflowTable, reference counting will be disabled, and any subsequent collection or
-- RC operation will
-- return immediately (or, better, the trace-and-sweep collector will clean up the world). After the
-- collection, AssignRef (AssignRefNew) will be attempted again. If this fails, then
-- reference counting will be disabled and the raw assignment will be done.
 
AssignRef: PUBLIC PROC[refNew: REF, ptrRef: LONG POINTER TO REF] =
   { IF useUCodedGC THEN ASSIGNREF[refNew, ptrRef]
        ELSE StoreRef[refNew, ptrRef ! OutOfOverflowTable => GOTO CollectAndTryAgain];
     EXITS CollectAndTryAgain =>
        { ENABLE OutOfOverflowTable => RETRY;
          InternalReclaim[rcTableOverflow];
          StoreRef[refNew, ptrRef];
        }};

StoreRef: ENTRY PROC[refNew: REF, ptrRef: LONG POINTER TO REF] =
    { ENABLE UNWIND => NULL;
      refOld: REF = ptrRef^;
      PPAlterCount[rcoAddRef, refNew];
      PPAlterCount[rcoDeleteRef, refOld
              ! OutOfOverflowTable =>
                        PPAlterCount[rcoDeleteRef, refNew  -- and let it propogate up to AssignRef
                                ! OutOfOverflowTable => {SIGNAL ErrorHalt; WaitEnd[]};]];
      LOOPHOLE[ptrRef, LONG POINTER TO Pointer]^ _ LOOPHOLE[refNew, Pointer]};

AssignRefNew: PUBLIC PROC[refNew: REF, ptrRef: LONG POINTER TO REF] =
   { IF useUCodedGC THEN ASSIGNREFNEW[refNew, ptrRef]
      ELSE DoAssignRefNew[refNew, ptrRef ! OutOfOverflowTable => GOTO CollectAndTryAgain];
     EXITS CollectAndTryAgain =>
        { ENABLE OutOfOverflowTable => RETRY;
          InternalReclaim[rcTableOverflow];
          DoAssignRefNew[refNew, ptrRef];
        }};

DoAssignRefNew: ENTRY PROC[refNew: REF, ptrRef: LONG POINTER TO REF] =
    { ENABLE UNWIND => NULL;
      PPAlterCount[rcoAddRef, refNew];
      LOOPHOLE[ptrRef, LONG POINTER TO Pointer]^ _ LOOPHOLE[refNew, Pointer]};

-- For CreateRef, if the software is in use, if OutOfOverflowTable is raised, then
-- a collection will be initiated
-- after the stack is unwound (the stack is unwound to exit the monitor). If tracing the stack then
-- raises OutOfOverflowTable, reference counting will be disabled, and any subsequent collection or
-- RC operation will
-- return immediately (or, better, the trace-and-sweep collector will clean up the world). After the
-- collection, CreateRef will be attempted again. If this fails, then
-- reference counting will be disabled.

SoftwareCreateRef: PUBLIC PROC[npr: CARDINAL, refNew: REF ANY] =
   { DoCreateRef[npr, refNew ! OutOfOverflowTable => GOTO CollectAndTryAgain];
     EXITS CollectAndTryAgain =>
        { ENABLE OutOfOverflowTable => RETRY;
          InternalReclaim[rcTableOverflow];
          DoCreateRef[npr, refNew]}};

    -- build into altercount
DoCreateRef: ENTRY PROC[npr: CARDINAL, refNew: REF ANY] =
    {ENABLE UNWIND => NULL;
      rcv: rcoState_ [rcChange: LAST[RefCt] - npr, onStack: true];
      IF ~AlterCount[rcv, refNew] THEN {SIGNAL BugFoundNewObject[refNew]; WaitEnd[]}};

-- AssignRef, AssignRefNew, CreateRef and friends (end)
--//////////////
--  if the microcode can't do the assignment or there is no microcode, these get called
-- they are accessible thru the TrapSupport.OpTrapTable

RTMOVESTATUSTrap: PUBLIC PROC[direction: RTRefCounts.uCodeDirection,
                                              gcStateBank: CARDINAL]
    RETURNS[v: CARDINAL] =
   { state: PrincOps.StateVector;
     state _ STATE;   -- incantation
     v _ 0;    -- means no microcode
     TrapSupport.BumpPC[2];                -- length of opcode
     state.dest _ LOOPHOLE[RTOS.MyLocalFrame[]];
     TRANSFER WITH state;   -- incantation
   };

RCFINALIZECOUNTTrap: PUBLIC PROC RETURNS[v: CARDINAL] =
   { s: MACHINE DEPENDENT RECORD [a, b: UNSPECIFIED, state: PrincOps.StateVector];
     s.state _ STATE;   -- incantation
     v _ 177777B;    -- means no microcode counting
     TrapSupport.BumpPC[2];                -- length of opcode
     s.state.dest _ LOOPHOLE[RTOS.MyLocalFrame[]];
     TRANSFER WITH s.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, Frame.GetReturnLink[]];
     SELECT (IF RTRefCounts.GCMicrocodeExists THEN TrapSupport.GetTrapParam[] ELSE 0) FROM
         0 => AssignRef[refNew, alphaRef];   -- no microcode
         1 => {InternalReclaim[rcTableOverflow]; ASSIGNREF[refNew, alphaRef]};
         2 => {EnterCollectorMonitor[]; ASSIGNREF[refNew, alphaRef]};
         177777B => ERROR;
         ENDCASE => {SIGNAL ErrorHalt; WaitEnd[]};

     TrapSupport.BumpPC[2];                -- length of opcode
     state.dest _ LOOPHOLE[RTOS.MyLocalFrame[]];
     TRANSFER WITH state;   -- incantation
   };

EnterCollectorMonitor: ENTRY PROC = {NULL};
  
AssignRefNewTrap: PUBLIC PROC[refNew: REF, ptrRef: LONG POINTER TO REF] =
   { state: PrincOps.StateVector;
     alphaRef: LONG POINTER TO REF;
     state _ STATE;   -- incantation
     alphaRef_ AddAlphaByte[ptrRef, Frame.GetReturnLink[]];
     SELECT (IF RTRefCounts.GCMicrocodeExists THEN TrapSupport.GetTrapParam[] ELSE 0) FROM
         0 => AssignRefNew[refNew, alphaRef];   -- no microcode
         1 => {InternalReclaim[rcTableOverflow]; ASSIGNREFNEW[refNew, alphaRef]};
         2 => {EnterCollectorMonitor[]; ASSIGNREFNEW[refNew, alphaRef]};
         177777B => ERROR;
         ENDCASE => {SIGNAL ErrorHalt; WaitEnd[]};
     TrapSupport.BumpPC[2];                -- length of opcode
     state.dest _ LOOPHOLE[RTOS.MyLocalFrame[]];
     TRANSFER WITH state;   -- incantation
   };

--  read the alpha byte for the trapping opcode & add it to ptrRef
AddAlphaByte: PROC[ptrRef: LONG POINTER TO REF, ctL: ControlLink] 
  RETURNS [LONG POINTER TO REF] =
  {  codeB: LONG POINTER TO PACKED ARRAY OF Environment.Byte_
        LOOPHOLE[RuntimeInternal.Codebase[LOOPHOLE[ctL.frame.accesslink]]];
     alpha: Environment.Byte_ codeB[ctL.frame.pc+1];
     RETURN[LOOPHOLE[ptrRef+alpha]];
  };

-- InternalReclaim waits till there are at least 4 oiFrees.
-- Not foolproof, but avoids infinite recursion.

    -- 'called' from microcode CREATEREF either if there are too few
    -- overflow entries or if the tands is running
CREATEOutOfOverflowTable: PUBLIC PROC[npr: rcoState, refNew: REF ANY] =
   { state: PrincOps.StateVector;
     state _ STATE;   -- incantation
     SELECT (IF RTRefCounts.GCMicrocodeExists THEN TrapSupport.GetTrapParam[] ELSE 0) FROM
         0 => ERROR;   -- no microcode
         1 => InternalReclaim[rcTableOverflow];  -- too few oi's
         2 => EnterCollectorMonitor[];  -- tands running. Wait till done.
         177777B => ERROR;
         ENDCASE => {SIGNAL ErrorHalt; WaitEnd[]};
     [] _ CREATEREF[npr, refNew];  -- try again.
     TrapSupport.BumpPC[2];
     state.dest _ LOOPHOLE[RTOS.MyLocalFrame[]];
     TRANSFER WITH state;   -- incantation
   };

ReclaimedRefOutOfOverflowTable: PUBLIC PROC =
   { s: MACHINE DEPENDENT RECORD [a, b: UNSPECIFIED, state: PrincOps.StateVector];
     s.state _ STATE;   -- incantation
     ERROR OutOfOverflowTable
   };

    -- 'called' from microcode ALTERCOUNT
ALTERCOUNTOutOfOverflowTable: PUBLIC PROC =
   { s: MACHINE DEPENDENT RECORD [a, b: UNSPECIFIED, state: PrincOps.StateVector];
     s.state _ STATE;   -- incantation
     ERROR OutOfOverflowTable;
   };

    -- Something awful happened to the reference count table
 aREADREGS: MiscAlpha.alpha = 66B;
ReadUCodeRegs: PROC RETURNS[CARDINAL] = MACHINE CODE {Mopcodes.zMISC, aREADREGS};

ReadUCodeRegsTrap: PUBLIC PROC RETURNS[f: CARDINAL] =
  { s: MACHINE DEPENDENT RECORD [a: UNSPECIFIED, state: PrincOps.StateVector];
    s.state _ STATE;   -- incantation
    TrapSupport.BumpPC[2];                -- length of opcode
    f_ 0;
    s.state.dest _ LOOPHOLE[RTOS.MyLocalFrame[]];
    TRANSFER WITH s.state;   -- incantation
  };

-- ERRORs reported by the microcode
  EvenOTCellNotRCE: SIGNAL = CODE;
  BadOTPointer: SIGNAL = CODE;
  RefNotEven: SIGNAL = CODE;
  BadCreateRef: SIGNAL = CODE;  --  this may indicate a race with the tands; One could simply turn off rc here.
  DecRCZero: SIGNAL = CODE;
  MakingPrefixedNode: SIGNAL = CODE;
  FreeingPrefixedNode: SIGNAL = CODE;
  BoundsFault: SIGNAL = CODE;
  ReferentOnFreeList: SIGNAL = CODE;
  BadFLPointer1: SIGNAL = CODE;
  BadFlPointer2: SIGNAL = CODE;
  DelBadPtr: SIGNAL = CODE;

ClobberedOverflowTable: PUBLIC PROC =
   { OPEN RTRefCounts;
     state: PrincOps.StateVector;
     param: CARDINAL;
     rr: CARDINAL;

     state _ STATE;   -- incantation
     param_ (IF RTRefCounts.GCMicrocodeExists THEN TrapSupport.GetTrapParam[] ELSE 0);
     rr_ IF RTRefCounts.GCMicrocodeExists THEN ReadUCodeRegs[] ELSE 0;

      { rcv: rcoState;
        probe: ProbeIndex;
        residue: Residue;
        entry: RCEntry;
        onStack: CARDINAL;
        oiPrev0, oiPrev1: oRCEntry;
        gcTemp, gcTemp2, oofNum: CARDINAL;
        oiFreeList: oRCEntry;
        nOiFree: INTEGER;
        gcStateMask: gcRState;
        gcProcNum: PROCESS;
        rcFinalizeCount: CARDINAL;
        IF (param < 5) AND (rr # 0) THEN
         { rcv_ LOOPHOLE[GCState.dumpTable[0]];        -- microcode registers
           residue_ LOOPHOLE[GCState.dumpTable[1]];
           probe_ LOOPHOLE[GCState.dumpTable[2]];
           entry_ LOOPHOLE[GCState.dumpTable[3]];
           onStack_ GCState.dumpTable[4];
           oiPrev0_ LOOPHOLE[GCState.dumpTable[5]];
           oiPrev1_ LOOPHOLE[GCState.dumpTable[6]];
           gcTemp _ GCState.dumpTable[7];
           gcTemp2 _ GCState.dumpTable[8];
           oofNum_ GCState.dumpTable[9];
         };
--  these are always valid
        oiFreeList_ LOOPHOLE[GCState.dumpTable[10]];
        nOiFree_ LOOPHOLE[GCState.dumpTable[11]];
        gcStateMask_ LOOPHOLE[GCState.dumpTable[12]];
        gcProcNum_ LOOPHOLE[GCState.dumpTable[13]];
        rcFinalizeCount_ LOOPHOLE[GCState.dumpTable[14]];

     SELECT param FROM
         0 => SIGNAL EvenOTCellNotRCE;
         1 => SIGNAL BadOTPointer;
         2 => SIGNAL RefNotEven;
         3 => SIGNAL BadCreateRef;  --  this may indicate a race with the tands; One could simply turn off rc here.
         4 => SIGNAL DecRCZero;
         5 => SIGNAL MakingPrefixedNode;
         6 => SIGNAL FreeingPrefixedNode;
         7 => SIGNAL BoundsFault;
         8 => SIGNAL ReferentOnFreeList;
         9 => SIGNAL BadFLPointer1;
        10 => SIGNAL BadFlPointer2;
        11 => SIGNAL DelBadPtr;
        ENDCASE => {SIGNAL ErrorHalt};
     WaitEnd[];
      };
     };

--//////////////
-- procedures for maintaining reference counts

--  if new entry is created, return ref - used by CreateRef to make sure entry not already in table
--  in reclaimedRef case, return ref if entry not there - used by FreeRef

--  newest wrinkle; if doing AddRef and resulting rc>rcFinalize, then turn
--  off the onStack bit

--  W A R N I N G
-- this code simulates what the microcode will do, hence does not look much
--  like Mesa code and has numerous LOOPHOLEs

AlterCountEntry: PUBLIC ENTRY PROC[rcv: rcoState, ref: REF] = 
    {ENABLE UNWIND => NULL; []_ AlterCount[rcv, ref]; RETURN};

PPAlterCountEntry: ENTRY PROC[rcv: rcoState, ref: REF] = 
    {ENABLE UNWIND => NULL; [] _ AlterCount[rcv, ref]};

PPAlterCount: INTERNAL PROC[rcv: rcoState, ref: REF] = {[]_ AlterCount[rcv, ref]};

--  AlterCount returns true if ref was not found in the table
--  (or was in the table with rcAbsent and onStack)
--  This is used by DoCreateRef to check if a newly created object already exists
AlterCount: PROC[rcv: rcoState, ref: REF] RETURNS[BOOLEAN] =
    BEGIN OPEN Inline;
    pi: ProbeIndex;
    res: Residue;
    rce: RCEntry;
    delta: CARDINAL;
    onStack: CARDINAL;
    rc: RefCt;
    localRce: nRCEntry;
    oiPrev: MapOiOeIndex _ 0;
    oi: MapOiOeIndex;
    rcAbsentShifted: CARDINAL = LOOPHOLE[absentRCEntry];

    IF BITAND[LowHalf[ref], 1] # 0 THEN
     IF rcv = rcoFoundOnStack THEN RETURN[TRUE] ELSE         -- ref not even
      { SIGNAL ErrorHalt; WaitEnd[]};

    IF suspect # NIL THEN IF LOOPHOLE[ref, LONG POINTER] = suspect
      THEN SIGNAL AlterSuspectCount[suspect];

    IF ref = NIL
      OR (GCState.GCStateBasic.reclaimState = gcStopped
            AND LOOPHOLE[GCState.GCStateBasic.collector, PSB.PsbIndex] # RTOS.GetCurrent[])
     THEN RETURN[TRUE];
    delta _ BITAND[rcv, rcoChangeMask];

    onStack _ BITAND[BITAND[GCState.GCStateBasic.reclaimState, rcv], rcoOnstackMask];
    [pi, res] _ MapRefPiRes[ref];
    rce _ MapPiRce[pi];
    IF BITAND[LowHalf[ref], 1] # 0 THEN                 -- ref not even
      { SIGNAL ErrorHalt; WaitEnd[]};

    WITH rce: rce SELECT FROM
     normal =>
         { IF rce.res = res THEN
           { IF (rc_ rce.rc) # LAST[RefCt] THEN
              {localRce_ LOOPHOLE[BITOR[onStack,BITAND[LOOPHOLE[rce,CARDINAL]+delta,nrceMask]]];

               IF rcv = rcoAddRef AND localRce.rc > rcFinalize THEN
                        localRce _ BITAND[localRce, undoStackBit];
-- Becomes empty entry if rc=rcAbsent & ~onStack => must change to all zeroes
               IF RceEmpty[localRce] THEN MapPiRce[pi]_ rceEmpty
                ELSE MapPiRce[pi]_ localRce;        --store into MapPiRce
              };

             RETURN[rc = rcAbsent];        --for DoCreateRef
            }  --   end of rce.res = res

         ELSE  -- create overflow chain, store old and new entries in one overflow entry
          BEGIN
           oiNew: MapOiOeIndex = CreateOi[];

           IF rcv = rcoAddRef THEN onStack_ 0B;
           MapOiOe[oiNew] _
               [rce: LOOPHOLE[Inline.BITAND[delta+rcAbsentShifted+res+onStack,nrceMask]],
                     oe1: rce];
           MapPiRce[pi]_ [overflow [oi: oiNew]];
           RETURN[TRUE];
          END;
         };
      overflow =>   -- look at overflow table
       IF rce = rceEmpty
        THEN
         { IF rcv = rcoAddRef THEN onStack _ 0B;
           MapPiRce[pi] _
                 LOOPHOLE[Inline.BITAND[delta+rcAbsentShifted+res+onStack, nrceMask]];
           RETURN[TRUE];
         }
        ELSE
        BEGIN
        pOe: LONG POINTER TO OverflowEntry;
        prce: nRCEntry;
        oi_ rce.oi;

        DO
        IF oi < mapOiOeStart THEN { SIGNAL badOverflowEntry; WaitEnd[]};
        pOe _ @MapOiOe[oi];

        WITH LOOPHOLE[pOe.rce, RCEntry] SELECT FROM                --debugging
         overflow => {SIGNAL ErrorHalt; WaitEnd[]};
         ENDCASE;

          IF pOe.rce.res = res THEN  -- found a match
          BEGIN
            IF (rc_ pOe.rce.rc) # LAST[RefCt] THEN
            { prce _
               LOOPHOLE[BITOR[onStack,
                                    Inline.BITAND[LOOPHOLE[pOe.rce,CARDINAL]+delta,nrceMask]]];
              IF rcv = rcoAddRef AND prce.rc > rcFinalize THEN
                  prce _ LOOPHOLE[BITAND[LOOPHOLE[prce,CARDINAL], undoStackBit]];
               pOe.rce _ prce;
               IF RceEmpty[prce] THEN  -- delete the entry
                BEGIN
                 IF oiPrev = 0
                  THEN MapPiRce[pi]_ pOe.oe1
                  ELSE MapOiOe[oiPrev].oe1 _ pOe.oe1;
                FreeOi[oi];
                END;
             };  -- pOe.rce.rc # LAST[RefCt]
            RETURN[rc = rcAbsent];
          END;  -- of found a match

          WITH pOe.oe1 SELECT FROM
           rce1: normal RCEntry =>        -- end of chain, check second entry for match
           BEGIN
            IF rce1.res # res THEN EXIT;        -- not match, exit the loop
            {IF (rc_ rce1.rc) # LAST[RefCt] THEN
              { prce _ BITOR[onStack, Inline.BITAND[LOOPHOLE[rce1,CARDINAL]+delta,nrceMask]];
                IF rcv = rcoAddRef AND prce.rc > rcFinalize THEN
                  prce _ LOOPHOLE[BITAND[LOOPHOLE[prce,CARDINAL], undoStackBit]];
                 pOe.oe1 _ prce;
                 IF RceEmpty[prce] THEN  -- delete the entry (this is the end of the chain)
                  { IF oiPrev = 0
                     THEN MapPiRce[pi]_ pOe.rce                -- move other entry to main table
                     ELSE MapOiOe[oiPrev].oe1_ pOe.rce;        -- move other entry to previous slot
                    FreeOi[oi];
                  };
               };
              RETURN[rc = rcAbsent];
             };                -- end of pOe.oe1.res = res
           END;
           rce1: overflow RCEntry => { oiPrev _ oi;  oi _ rce1.oi };
           ENDCASE;
        ENDLOOP;
        END;
      ENDCASE;

 --  no match found, create a new entry just at the head of the chain
         { oi1: MapOiOeIndex _ CreateOi[];
           IF rcv = rcoAddRef THEN onStack_ 0B;
           MapOiOe[oi1] _
            [rce: LOOPHOLE[Inline.BITAND[delta+rcAbsentShifted+res+onStack, nrceMask]],
             oe1: MapPiRce[pi]];

           MapPiRce[pi]_ [overflow [ oi: oi1]];
          };
        RETURN[TRUE];
    END;  -- AlterCount

CreateOi: PROC RETURNS[oi: MapOiOeIndex] =
    { OPEN gcs: GCState.GCStateBasic;
      oi _ gcs.mapOiOeFrList.oi;
      IF oi = 0 THEN  -- really bad news
       {SIGNAL ErrorHalt; WaitEnd[]};
      IF gcs.reclaimState = gcRunning
           AND RTOS.GetCurrent[] = LOOPHOLE[gcs.collector]
        THEN {IF gcs.nOiFree < -gcThresholdNOiFree
                THEN ERROR OutOfOverflowTable}  -- really out
        ELSE {IF gcs.nOiFree < 0  -- soft threshold
                THEN ERROR OutOfOverflowTable}; -- cause collection

      gcs.mapOiOeFrList _ LOOPHOLE[MapOiOe[oi], OverflowFreeListEntry].link;
      gcs.nOiFree _ gcs.nOiFree - 1};

FreeOi: PROC[oi: MapOiOeIndex] =
    { OPEN gcs: GCState.GCStateBasic;
      LOOPHOLE[MapOiOe[oi], OverflowFreeListEntry].link _ gcs.mapOiOeFrList;
      gcs.mapOiOeFrList _ [overflow [oi: oi]];
      gcs.nOiFree _ gcs.nOiFree + 1};

IsOiCushion: PUBLIC ENTRY PROC RETURNS[BOOLEAN] =
    {RETURN[GCState.GCStateBasic.nOiFree>2*gcThresholdNOiFree]};

MapRefPiRes: PROC[ref: REF] RETURNS[pi: ProbeIndex, res: Residue] = INLINE
    { OPEN Inline;
      res_ MapRefRes[ref];
      pi_ BITXOR[BITSHIFT[LowHalf[ref], -1], res]};

MapRefRes: PROC[ref: REF] RETURNS[Residue] = INLINE
    {RETURN[Inline.HighHalf[ref]]};

RceEmpty: PROC[rce: nRCEntry] RETURNS[BOOLEAN] = INLINE
    {RETURN[rce.rc = rcAbsent AND rce.onStack = false]};

--  used after raising a catastrophic error, to allow any in progress allocation of space (and
--   use of temporary files) to finish, so that booting the client doesn't take forever

WaitEnd: PROC = { WHILE TRUE DO Process.Yield[]; ENDLOOP};

-- procedures for maintaining reference counts (end)
--//////////////


--//////////////
-- procedures for dealing with the collector

IsCollectorActive: PUBLIC SAFE PROC
      RETURNS[active: BOOLEAN, previousIncarnation: CARDINAL] =
    TRUSTED {RETURN[collectorRunning, collectorIncarnation]};

WaitForCollectorStart: PUBLIC ENTRY SAFE PROC
    RETURNS[incarnation: CARDINAL,
            reason: ReclamationReason,
            wordsAllocated: LONG CARDINAL,  -- since previous collection was initiated
            objectsAllocated: LONG CARDINAL] =
    TRUSTED {UNTIL collectorRunning DO WAIT CollectionInitiated ENDLOOP;
     RETURN[incarnation _ currentInfo.incarnation,
            reason _ currentInfo.reason,
            wordsAllocated _ currentInfo.wordsAllocated,
            objectsAllocated _ currentInfo.objectsAllocated]};

WaitForCollectorDone: PUBLIC ENTRY SAFE PROC
    RETURNS[incarnation: CARDINAL,
            reason: ReclamationReason,
            wordsReclaimed: LONG CARDINAL,
            objectsReclaimed: LONG CARDINAL] =
    TRUSTED {WHILE collectorRunning DO WAIT CollectionFinished ENDLOOP;
     RETURN[incarnation _ previousInfo.incarnation,
            reason _ previousInfo.reason,
            wordsReclaimed _ previousInfo.wordsReclaimed,
            objectsReclaimed _ previousInfo.objectsReclaimed]};

ReclaimForQuanta: PUBLIC PROC RETURNS[LONG CARDINAL] =
    { nor: Count = nObjectsReclaimed;
      InternalReclaim[quantaNeeded];
      RETURN[nObjectsReclaimed - nor]};

InternalReclaim: PUBLIC PROC[reason: ReclamationReason,
                               suspendMe: BOOLEAN _ FALSE,
                               doStack: BOOLEAN _ TRUE] =
    { DO
        DoInternalReclaim[reason, suspendMe, doStack];
        [] _ RTMOVESTATUS[toMemory, 0];
        IF GCState.GCStateBasic.nOiFree < 4 
          AND GCState.GCStateBasic.reclaimState # gcStopped
         THEN LOOP  -- keep trying while on the edge of the RCTable soft threshold
         ELSE RETURN;
       ENDLOOP};

DoInternalReclaim: ENTRY PROC[reason: ReclamationReason,
                                suspendMe: BOOLEAN,
                                doStack: BOOLEAN] =
    { ENABLE UNWIND => ERROR;

      IF alwaysTrim OR reason = quantaNeeded THEN trimZonesNeeded _ TRUE;

      IF IsTraceAndSweepEnabled[]
        AND (reason = clientTAndSRequest OR GCState.GCStateBasic.reclaimState = gcStopped)
       THEN tAndSToRun _ TRUE
       ELSE  -- not a tands
        {IF GCState.GCStateBasic.reclaimState = gcStopped
          THEN {RTStorageAccounting.ResetNWordsAllocated[];
                RETURN}};
          -- We're running without the collector.
          -- Obviate subsequent decisions (for one allocation interval) to collect

      RTStorageAccounting.ResetTotalNWordsAllocatedOnly[];
        -- obviate decisions to collect while the collector is running,
        -- but allow allocator hogs to be suspended during this time

      IF NOT collectorRunning
       THEN   -- initiate a collection
         { IF tAndSToRun
            THEN InitiateCollection[reason]
            ELSE
             {GCState.GCStateBasic.reclaimState _ gcRunning;
              GCState.GCStateBasic.collector _ LOOPHOLE[RTOS.GetCurrent[]];
              [] _ RTMOVESTATUS[toMemory, 0];
                 -- tell uc about gcs.collector and gcs.reclaimState. second arg doesn't matter.

              IF doStack THEN TraceTheStack[ ! OutOfOverflowTable => GOTO ret];
              InitiateCollection[reason];

              GCState.GCStateBasic.collector _ collectorProcess;
              [] _ RTMOVESTATUS[toMemory, 0];

              EXITS ret => RETURN -- reference-counting has been disabled
             };

           collectorToRun _ TRUE;
           NOTIFY CollectorNeeded;
         };
           

      [] _ RTMOVESTATUS[toMemory, 0];
      WHILE GCState.GCStateBasic.nOiFree < 4 AND collectorRunning
        DO WAIT OiFreed;
           [] _ RTMOVESTATUS[toMemory, 0]
       ENDLOOP;

      WHILE trimZonesNeeded AND collectorRunning DO WAIT TrimZonesFinished ENDLOOP;

      IF suspendMe
       THEN WHILE collectorRunning
              DO WAIT CollectionFinished ENDLOOP;  -- await completion
    };

TraceTheStack: INTERNAL PROC =
    { DO
       { RTOS.SnapshotTheFrameHeap[ ! RTOS.FrameCopySpaceTooSmall => GOTO expandFCS];
         ScanTheFrameHeap[ ! UNWIND => DoDisableReferenceCounting[]];
         RETURN;
        EXITS expandFCS =>
                {Bump[@Stats.frameCopySpaceExpanded];
                 RTOS.AllocateFrameBodyBuffer[frameBodyBufferPages _ frameBodyBufferPages+1]};
       } ENDLOOP};

        -- client interface
ReclaimCollectibleObjects: PUBLIC SAFE PROC
            [suspendMe: BOOLEAN _ TRUE, traceAndSweep: BOOLEAN _ FALSE] =
    TRUSTED {IF traceAndSweep
      THEN {DisableReferenceCounting[];
            InternalReclaim[reason: clientTAndSRequest, suspendMe: suspendMe]}
      ELSE  InternalReclaim[reason: clientRequest, suspendMe: suspendMe]};

PrivateReclaimCollectibleObjects: PUBLIC PROC RETURNS[LONG CARDINAL] =
    { nFreed: Count = nObjectsReclaimed;
      InternalReclaim[reason: clientNoTraceRequest, suspendMe: TRUE, doStack: FALSE];
          -- initiate collection
      RETURN[nObjectsReclaimed - nFreed]};

InitiateCollection: INTERNAL PROC[reason: ReclamationReason] =
   { first: BOOLEAN = (collectorIncarnation = 0);
     nw: LONG CARDINAL = NWordsAllocated[];
     nob: LONG CARDINAL = RTStorageAccounting.nObjectsCreated;

     Bump[@Stats.reclamationReasons[reason]];
     currentInfo _
          [incarnation: (collectorIncarnation _ collectorIncarnation + 1),
           reason: reason,
           wordsAllocated:   (IF first
                               THEN nw
                               ELSE nw - previousInfo.totalWordsAllocated),
           objectsAllocated: (IF first
                               THEN nob
                               ELSE nob - previousInfo.totalObjectsAllocated),
           totalWordsAllocated: nw,
           totalObjectsAllocated: nob];
     IF takingStatistics THEN {Stats.nCreated _ RTStorageAccounting.nObjectsCreated};
     nObjectsReclaimedAsOfThen _ nObjectsReclaimed;
     nWordsReclaimedAsOfThen _ nWordsReclaimed;

     collectorRunning _ TRUE;
     BROADCAST CollectionInitiated;
   };
    
    -- This guy is fired up as a detached process by the start code
DoBackgroundCollection: PROC =
   {  RTOS.UnregisterCedarProcess[RTOS.GetCurrent[]];
      Process.SetPriority[Process.priorityBackground];
      DO
        IF BackgroundCollectorInner[].doTandS
         THEN {trimZonesNeeded _ TRUE; TAndSCollectorInner[]}
         ELSE MapReclaimableObjects[];
        ResetStackBits[];
        RTStorageAccounting.ResetNWordsAllocated[];
        IF trimZonesNeeded
         THEN {TrimAllZones[]; [] _ TrimRootBase[]; FinishTZ[]}
         ELSE IF NOT SSExtra.useSizeToZn THEN MergeAllPrefixedZones[];
        FinishBC[];
       ENDLOOP};

BackgroundCollectorInner: ENTRY PROC RETURNS[doTandS: BOOLEAN] =
    {t: BOOLEAN;
     UNTIL collectorToRun DO WAIT CollectorNeeded ENDLOOP;
     t _ tAndSToRun;
     collectorToRun _ tAndSToRun _ FALSE;
     RETURN[t]};

TAndSCollectorInner: ENTRY PROC =
  {ENABLE UNWIND => NULL; DoTraceAndSweepCollection[]};

FinishBC: ENTRY PROC =
  { IF GCState.GCStateBasic.reclaimState = gcRunning
           THEN GCState.GCStateBasic.reclaimState _ gcReady;
    GCState.GCStateBasic.collector _ NIL;
    []_ RTMOVESTATUS[toMemory, 0];

    currentInfo.wordsReclaimed _ nWordsReclaimed - nWordsReclaimedAsOfThen;
    currentInfo.objectsReclaimed _ nObjectsReclaimed - nObjectsReclaimedAsOfThen;
    previousInfo _ currentInfo;
    collectorRunning _ FALSE;
    BROADCAST CollectionFinished;
    BROADCAST TrimZonesFinished;
    BROADCAST OiFreed;
  };

CheckRceReclaim: ENTRY PROC[xrce: nRCEntry, pi: ProbeIndex] =
   { ENABLE UNWIND => NULL;
     rce: RCEntry _ MapPiRce[pi];

     WITH rce: rce SELECT FROM
      normal => SIGNAL CheckRceError;
      overflow =>
       { oi: MapOiOeIndex_ rce.oi;
         IF oi < mapOiOeStart THEN {SIGNAL badOverflowEntry; WaitEnd[]};
         DO
           IF MapOiOe[oi].rce = xrce
            THEN {SIGNAL CheckRceError; EXIT}
            ELSE
             WITH rce: MapOiOe[oi].oe1 SELECT FROM
               normal => {IF rce = xrce THEN SIGNAL CheckRceError; EXIT};        -- end of chain
               overflow => oi _ rce.oi;
              ENDCASE;
        ENDLOOP;
       };
      ENDCASE;
   };

IsPiReclaimable: PUBLIC ENTRY PROC[pi: ProbeIndex]
      RETURNS [fpi: ProbeIndex, npi: CARDINAL] =
  { ENABLE UNWIND => NULL;
    count: CARDINAL_ 20B;
    nrce: RCEntry;
    rce: RCEntry;
    fpi_ pi;
    npi_ 0;

   DO
    rce_ MapPiRce[fpi];
    WITH rce: rce SELECT FROM
     normal =>
       IF rce.rc <= rcFinalize AND rce.onStack = false THEN
        {GCState.rceToReclaim[npi]_ rce; npi_ npi + 1; RETURN};
     overflow =>
      IF rce # rceEmpty THEN
      {oi: MapOiOeIndex_ rce.oi;
       
     DO
      IF oi < mapOiOeStart THEN {SIGNAL badOverflowEntry; WaitEnd[]};
      nrce_ MapOiOe[oi].rce;
       WITH nrce: nrce SELECT FROM
        normal =>
         IF nrce.rc <= rcFinalize AND nrce.onStack = false THEN
          { GCState.rceToReclaim[npi]_ nrce; npi_ npi + 1};
        overflow => {SIGNAL ErrorHalt; WaitEnd[]};
        ENDCASE;

        WITH nrce: MapOiOe[oi].oe1 SELECT FROM
         normal =>                -- end of chain
          { IF nrce.rc <= rcFinalize AND nrce.onStack = false
            THEN { GCState.rceToReclaim[npi]_ nrce; npi_ npi + 1; RETURN}
            ELSE EXIT};
         overflow => oi_ nrce.oi;
         ENDCASE;

        ENDLOOP;
       IF npi > 0 THEN RETURN;
      };
    ENDCASE;

    IF fpi = LAST[ProbeIndex] THEN RETURN;   -- npi is 0
    fpi_ fpi + 1;
    count_ count - 1;
    IF count = 0 THEN RETURN;
   ENDLOOP;
 };

ReclaimedRef: PUBLIC ENTRY PROC[ref: REF] RETURNS[REF] =
--  if ref not found in tables, don't enter and return ref; if found, do a deleteRef and return NIL
  { OPEN Inline;
    ENABLE UNWIND => NULL;
    pi: ProbeIndex;
    res: Residue;
    rce: RCEntry;
    localRce: nRCEntry;

    [pi, res] _ MapRefPiRes[ref];
    rce _ MapPiRce[pi];

    WITH rce: rce SELECT FROM
      normal =>
       IF rce.res = res
        THEN  -- found
         { IF rce.rc # LAST[RefCt]  -- i.e. not pinned
            THEN
             { localRce _ LOOPHOLE[BITAND[LOOPHOLE[rce, CARDINAL] + reclaimedRefDelta,
                                                   nrceMask]];
               IF RceEmpty[localRce]
                THEN MapPiRce[pi] _ rceEmpty
                ELSE MapPiRce[pi] _ localRce};
           RETURN[NIL]}
        ELSE RETURN[ref];                -- not found
         
      overflow =>             -- overflow chain
       IF rce = rceEmpty
        THEN RETURN[ref]
        ELSE
         { pOe: LONG POINTER TO OverflowEntry;
           prce: nRCEntry;
           oiPrev: MapOiOeIndex _ 0;
           oi: MapOiOeIndex _ rce.oi;
           DO
             pOe _ @MapOiOe[oi];

             WITH LOOPHOLE[pOe.rce, RCEntry] SELECT FROM
               overflow => {SIGNAL ErrorHalt; WaitEnd[]};
              ENDCASE;

             prce _ pOe.rce;
             IF prce.res = res
              THEN  -- found
               { IF prce.rc # LAST[RefCt]  -- i.e. not pinned
                  THEN
                   { prce _ LOOPHOLE[BITAND[LOOPHOLE[prce, CARDINAL] + reclaimedRefDelta,
                                                     nrceMask]];
                     pOe.rce _ prce;
                     IF RceEmpty[prce] THEN                -- delete this entry
                      {IF oiPrev = 0
                        THEN MapPiRce[pi] _ pOe.oe1
                        ELSE MapOiOe[oiPrev].oe1 _ pOe.oe1;
                       FreeOi[oi]}};                -- end prce.rc # LAST[RefCt]
                 RETURN[NIL]};                        -- end prce.res = res

             WITH pOe.oe1 SELECT FROM
               rce1: normal RCEntry =>                -- end of chain, check second entry for match
                IF rce1.res = res
                 THEN  -- found
                  {IF rce1.rc # LAST[RefCt] THEN
                    { rce1 _ LOOPHOLE[BITAND[LOOPHOLE[rce1, CARDINAL]+reclaimedRefDelta,
                                                      nrceMask]];
                      pOe.oe1 _ rce1;
                      IF RceEmpty[rce1] THEN
                       { IF oiPrev = 0 THEN MapPiRce[pi] _ prce ELSE MapOiOe[oiPrev].oe1 _ prce;
                         FreeOi[oi]}};                        -- end rce1.rc # LAST[RefCt]
                   RETURN[NIL]}                        -- end rce1.res = res
                 ELSE RETURN[ref];                -- end normal RCEntry
               rce1: overflow RCEntry => { oiPrev _ oi; oi _ rce1.oi};
              ENDCASE;  -- 2nd overflow entry variant
            ENDLOOP};
     ENDCASE => ERROR};  -- main table entry variant

FinishTZ: ENTRY PROC =
  { trimZonesNeeded _ FALSE;
    BROADCAST TrimZonesFinished};

ScanTheFrameHeap: INTERNAL PROC =  -- mark all items accessible from the stack
  { MarkRef: INTERNAL PROC[ref: REF] =
      { IF useUCodedGC
         THEN []_ ALTERCOUNT[rcoFoundOnStack, ref]
         ELSE [] _ AlterCount[rcoFoundOnStack, ref]};

    MarkCl: INTERNAL PROC[cl: ControlLink] =
      { NULL--[] _ AlterClCount[cl, foundOnStack]--};

    ConservativeScanner: INTERNAL PROC[pa: LONG POINTER TO Address, nWords: CARDINAL] =
       { IF nWords >= SIZE[REF] THEN
           FOR i: CARDINAL IN [0..nWords-SIZE[REF]] DO
             addr: Address = (pa+i)^;
             IF addr <= RTQuanta.LASTAddress AND NOT RTOS.InMDS[addr] THEN
               {Bump[@Stats.nRefs]; MarkRef[RepAddrRef[addr]]}
              ELSE Bump[@Stats.nNonRefs];
          ENDLOOP};

    RTOS.MapRCFrameBodies[ConservativeScanner];
  };

IncrementReferenceCount: PUBLIC PROC[ref: REF] =  -- called by the TraceAndSweep collector
      {IF useUCodedGC
         THEN [] _ ALTERCOUNT[rcoAddRef, ref]
         ELSE [] _ AlterCount[rcoAddRef, ref]};

DecrementReferenceCount: PUBLIC PROC[ref: REF] =  -- called by the TraceAndSweep collector
      {IF useUCodedGC
         THEN [] _ ALTERCOUNT[rcoDeleteRef, ref]
         ELSE [] _ AlterCount[rcoDeleteRef, ref]};

      -- reset stack bits, and delete entries with rc = rcAbsent (whether or not they were onStack)
ResetStackBits: PROC =
   { IF useUCodedGC THEN RESETSTKBITS[0] ELSE 
      FOR pi: ProbeIndex IN [0..LAST[ProbeIndex]] DO ResetPIStackBits[pi]; ENDLOOP;
   };

ResetPIStackBits: ENTRY PROC[pi: ProbeIndex] = -- not using ucode
   { rce: RCEntry _ MapPiRce[pi];

     WITH rce: rce SELECT FROM
      normal =>
       { IF rce.rc = rcAbsent THEN MapPiRce[pi]_ rceEmpty
          ELSE { rce.onStack_ false; MapPiRce[pi]_ rce};
       };
      overflow =>  -- overflow chain
       IF rce # rceEmpty THEN
        { oiPrev0: MapOiOeIndex _ 0;
          oiPrev1: MapOiOeIndex _ 0;
          oi: MapOiOeIndex_ rce.oi;
          pOe:  LONG POINTER TO OverflowEntry;
  
          DO
            pOe_ @MapOiOe[oi];
 
          WITH LOOPHOLE[pOe.rce, RCEntry] SELECT FROM
           overflow => {SIGNAL ErrorHalt; WaitEnd[]};
           ENDCASE;

           IF pOe.rce.rc = rcAbsent THEN  -- delete this entry
             WITH pOe.oe1 SELECT FROM
              rce: normal RCEntry =>                -- end of chain
               { IF rce.rc = rcAbsent THEN
                  { IF oiPrev1 = 0
                     THEN MapPiRce[pi]_ rceEmpty
                     ELSE
                      { rce_ LOOPHOLE[Inline.BITAND[MapOiOe[oiPrev1].rce, undoStackBit],
                                                             nRCEntry];
                        IF oiPrev0 = 0
                         THEN MapPiRce[pi]_ rce
                         ELSE MapOiOe[oiPrev0].oe1_ rce;
                        FreeOi[oiPrev1];
                      };
                  }
                 ELSE
                  { rce_ LOOPHOLE[Inline.BITAND[rce, undoStackBit], nRCEntry];
                    IF oiPrev1 = 0
                     THEN MapPiRce[pi]_ rce
                     ELSE MapOiOe[oiPrev1].oe1_ rce;
                  };
                 FreeOi[oi]; RETURN;                -- done with this PI
                };
              rce: overflow RCEntry =>                -- middle of chain
               { IF oiPrev1 = 0
                  THEN MapPiRce[pi]_ rce
                  ELSE MapOiOe[oiPrev1].oe1 _ rce;
                 FreeOi[oi];
                 oi_ rce.oi; LOOP;        -- keep on looking at this PI
               };
              ENDCASE
             ELSE pOe^.rce.onStack _ false;

            WITH pOe.oe1 SELECT FROM
             rce: normal RCEntry =>                -- end of chain
              { IF rce.rc = rcAbsent
                 THEN        -- delete this entry
                  { IF oiPrev1 = 0
                     THEN MapPiRce[pi]_ pOe.rce
                     ELSE MapOiOe[oiPrev1].oe1 _ pOe.rce;
                    FreeOi[oi];
                  }
                  ELSE LOOPHOLE[pOe^.oe1, nRCEntry].onStack _ false;
                RETURN;
               };
             rce: overflow RCEntry => {oiPrev0_ oiPrev1; oiPrev1 _ oi; oi_ rce.oi};
            ENDCASE;
          ENDLOOP;
       }
     ENDCASE;
   };

-- procedures for controlling the collector (end)
--//////////////



--  for debugging new microcode - dump the microcode registers
ReadRegs: PROC =
  { rcv: rcoState;
    probe: ProbeIndex;
    residue: Residue;
    entry: RCEntry;
    onStack: CARDINAL;
    oiPrev0, oiPrev1: oRCEntry;
    gcTemp, gcTemp2, oofNum, rcFinalizeCount: CARDINAL;
    oiFreeList: oRCEntry;
    nOiFree: INTEGER;
    gcStateMask: gcRState;
    gcProcNum: PROCESS;
    IF ReadUCodeRegs[] # 0 THEN
     {  rcv_ LOOPHOLE[GCState.dumpTable[0]];        -- microcode registers
        residue_ LOOPHOLE[GCState.dumpTable[1]];
        probe_ LOOPHOLE[GCState.dumpTable[2]];
        entry_ LOOPHOLE[GCState.dumpTable[3]];
        onStack_ GCState.dumpTable[4];
        oiPrev0_ LOOPHOLE[GCState.dumpTable[5]];
        oiPrev1_ LOOPHOLE[GCState.dumpTable[6]];
        gcTemp _ GCState.dumpTable[7];
        gcTemp2 _ GCState.dumpTable[8];
        oofNum_ GCState.dumpTable[9];
        oiFreeList_ LOOPHOLE[GCState.dumpTable[10]];
        nOiFree_ LOOPHOLE[GCState.dumpTable[11]];
        gcStateMask_ LOOPHOLE[GCState.dumpTable[12]];
        gcProcNum_ LOOPHOLE[GCState.dumpTable[13]];
        rcFinalizeCount_ LOOPHOLE[GCState.dumpTable[14]];
     };
   };

--//////////////
-- procedures used by CedarProbe

GetMapPiRce: PUBLIC PROC RETURNS[LONG POINTER TO AMapPiRce] = { RETURN[MapPiRce]};
GetMapOiOe: PUBLIC PROC RETURNS[LONG POINTER TO AMapOiOe] = { RETURN[MapOiOe]};

-- procedures used by CedarProbe (end)
--//////////////


    -- This is really an INTERNAL procedure, called only by the TAndS
    -- collector and the module initialization code below.
ClearRCTable: PUBLIC PROC =  -- called by the TraceAndSweep collector
   { OPEN gcs: GCState.GCStateBasic;

     FOR i: ProbeIndex IN ProbeIndex DO MapPiRce[i] _ rceEmpty ENDLOOP;

       -- now initialize the free list of overflow entries for the RCTable
       -- freelist is linked with oType_ 0, end of list is 0
     FOR oi: MapOiOeIndex IN [mapOiOeStart .. mapOiOeStart + mapOiOeLimit-1)
       DO LOOPHOLE[MapOiOe[oi], OverflowFreeListEntry]
                              _ [link: [overflow [oi: oi + 1]],
                                 oe1: [normal[ rc: 0, onStack: false, res: 0]]];
      ENDLOOP;

     LOOPHOLE[MapOiOe[mapOiOeStart + mapOiOeLimit-1], OverflowFreeListEntry]
                              _ [link: [overflow [oi: 0]],
                                  oe1: [normal [ rc: 0, onStack: false, res: 0]]];

      -- head of free list points to first entry
     gcs.mapOiOeFrList _ [overflow [oi: mapOiOeStart]];
     gcs.nOiFree _ mapOiOeLimit - gcThresholdNOiFree;
     [] _ RTMOVESTATUS[toUCodeRegisters, Inline.HighHalf[GCState]];
   };


-- START HERE

  RTOS.AllocateFrameBodyBuffer[frameBodyBufferPages];

  GCState _ RTOS.GetDataPagesForGCTables[];                -- 64K on a 64K boundary

  MapPiRce _ LOOPHOLE[GCState + LONG[SIZE[AGCState]], LONG POINTER];
  MapOiOe _ LOOPHOLE[GCState +  LONG[SIZE[AMapPiRce]], LONG POINTER];
          
  GCState.GCStateBasic.collector _ NIL;
  GCState.GCStateBasic.reclaimState _ gcReady;

  GCState.GCStateBasic.mapTiTd _ RTTypesBasicPrivate.GetMapTiTd[];

  ClearRCTable[];

  IF RTSD.SD[RTSD.sRTState] # 0 THEN ERROR;
  LOOPHOLE[LONG[@RTSD.SD[RTSD.sRTState]],
                LONG POINTER TO LONG POINTER TO AGCState]^ _ GCState;

  IF useUCodedGC THEN
   { mcVersion: CARDINAL _ RTMOVESTATUS[toUCodeRegisters, Inline.HighHalf[GCState]];
     useUCodedGC _ GCMicrocodeExists _ (mcVersion # 0);
     IF GCMicrocodeExists
      THEN IF mcVersion = microcodeVersion        -- must be equal for this release
                                                      -- substantial changes in the gc tables
              THEN {InitializeCleanup[Inline.HighHalf[GCState]]}
              ELSE ERROR WrongMicrocodeVersion[expectedVersion: microcodeVersion,
                                                          actualVersion: mcVersion];
   };

  Process.Detach[collectorProcess _ FORK DoBackgroundCollection[]];

END.



�Ê=–
"Mesa" style˜IprocšòÏc‡
œ
Ïk	œžœžœžœžœžœ
žœžœžœ�œ
žœžœ&žœ5žœ
žœžœžœ
�œžœ:žœ
žœž	œžœž
œžœžœ
žœÛ
žœ žœ
žœ
žœ#žœ{žœžœžœ"žœ2žœžœ{žœžœ*žœ�œžœAžœažœ*žœžœƒ
žœ�œžœ!žœžœžœžœžœžœ
žœžœžœžœžœžœžœ�œžœ
žœ
žœžœžœžœžœžœžœžœžœžœ�œžœ
žœ
žœžœ
žœ
žœžœ
žœ
žœ
žœ�œ
žœ
�"œžœ
žœžœžœ)žœ�œH�œžœ
žœ.žœ
žœžœžœžœ!žœžœžœžœžœžœžœ
žœ� œ?� œžœžœžœžœžœ�œž	œž	œž	œž	œž	œ�œ�7œ	žœžœ
žœžœžœžœhžœ
žœ#žœ
žœ&žœ
žœ�œ"žœ
žœ!žœ
žœ#žœ
žœ*žœRÏnœžœžœ
žœ žœžœžœ žœžœ�žœ
žœ žœžœ	žœ'�œ
�=œ
Ÿœžœ
žœ
žœžœ
žœžœžœ6žœ
žœžœ'Ÿ	œžœ
žœ
žœžœ
žœžœ"Ÿœžœ
žœE�3œ'žœžœ7ž	œ�œ
Ÿ
œžœ
žœ
žœžœ�6Ÿœžœ
žœžœ
žœ
žœ<Ÿ
œžœ
žœžœ
žœ
žœ>Ÿœžœ
žœžœ
žœ
žœ;�œ�Yœ
�ꜟ	œžœ
žœ	žœ
žœ
žœ
žœ
žœ	žœ
žœ
ž	œžœ1žœžœ!žœžœ_Ÿœžœ
žœ	žœ
žœ
žœ
žœ
žœ
žœ
žœžœžœ¼
�(œ9žœ!žœ	žœ
žœ
žœ
žœŸœžœ
žœ	žœ
žœ
žœ
žœ
žœ	žœ
žœ
žœžœ7žœžœ!žœžœeŸœžœ
žœ	žœ
žœ
žœ
žœ
žœ
žœ
žœžœ/žœ	žœ
žœ
žœ
žœ�¥œ
Ÿœžœ
žœžœ
žœ
žœ9žœžœ!žœžœY�Ÿœžœ
žœžœ
žœ
žœ	žœ
žœžœ"žœ%žœžœžœ*�Ù
œ
Ÿœžœ
žœcžœžœžœ3žœ�œ�œ+�œžœ
žœžœ
žœ
�œŸœžœ
žœ
žœžœžœ
ž	œ
žœžœ/žœ�œ�œ+�œžœ
žœžœ
žœ�œŸ
œžœ
žœ	žœ
žœ
žœ
žœ
žœ5žœ
žœ
žœ
žœžœ�œAžœžœžœžœžœ.�œ1ž	œ=ž	œ)žœžœžœD�œžœ
žœžœ
žœ
�œŸœžœ
žœžœŸœžœ
žœ	žœ
žœ
žœ
žœ
žœ5žœ
žœ
žœ
žœžœ�œAžœžœžœžœžœ1�œ1žœ=žœ)žœžœžœC�œžœ
žœžœ
žœ
�œ�CŸœžœ	žœ
žœ
žœ
žœžœžœ
žœ
žœ
žœžœ
žœ
žœ
žœ
žœ
žœžœžœTžœ
žœ�mœ�Aœ�/Ÿœžœ
žœžœ
žœ3žœ�œžœžœžœžœžœžœ�œ1�œ(�"œžœžœžœ"ž	œ�œ.žœ
žœžœ
žœ
�œŸœžœ
žœžœ
ž	œ
žœžœ/žœ�œžœ�&Ÿœžœ
žœžœ
ž	œ
žœžœ/žœ�œžœ �9œ#Ÿ
œžœ
žœ
žœžœ
žœŸœžœ
žœ
žœžœžœ
ž	œ
žœžœ.žœ�œ*�œžœ
žœžœ
žœ�œ�$œžœžœžœžœžœžœžœžœ�Pœ
žœžœžœžœžœžœžœžœžœžœžœžœžœžœžœžœŸœžœ
žœžœ<žœžœžœ�œ
žœžœžœžœžœžœzžœGžœ1žœ4žœžœ
žœ
žœ
žœžœ�œžœ*žœ*žœVžœ,žœ¢
�œžœ*žœ.žœ,žœ2žœžœžœžœ!žœžœžœ�Pœžœžœ#žœ$žœžœ#žœžœžœžœžœ/�@œ
�®
œ
�cœ
�Œ
œ
Ÿœžœ
žœ
žœžœ
žœ
žœžœžœŸœžœ
žœžœ
žœ
žœžœŸœžœ
žœžœ!�Ä
Ÿ
œžœžœžœ
žœžœ
žœLžœžœržœžœžœ
žœžœžœžœ
žœžœ	�œžœžœžœ
žœ
žœ
žœžœ
žœžœ
žœ"žœžœžœ<žœ
žœ!žœ
žœžœ
žœ
žœžœ%žœ
žœyžœ
žœžœ�œžœžœ
žœ
žœžœžœžœžœžœžœ
žœ	žœ
žœžœ%žœžœžœ$žœ�Nœžœžœ(žœ �œžœ�œ�œ
žœ�Jœ
žœ:žœžœ?žœžœ‹
žœ
žœ
žœ"�œžœžœžœžœ:žœžœ;žœ
žœžœ	žœžœ
žœ
žœEžœ	žœžœžœDžœ
žœžœ
žœ�œžœ!žœ
žœžœ�œ
žœ
žœžœžœ%žœ
žœ5žœ
žœ	žœ#žœžœžœžœ
žœ
žœžœAžœžœ�œžœžœžœ)žœLžœ�œžœžœ�œžœ	žœ
žœ+�.œžœ
žœžœ
žœ	�œ
žœžœžœžœžœ
žœžœ$žœžœžœžœ
žœ
žœžœEžœžœ�3œžœ!žœ&�"œžœ&�%œUžœ0�œžœRžœ
žœ
žœžœ�Eœ6žœžœ:žœžœ—
žœ
žœžœ�œ
Ÿœžœ
žœžœCžœžœ�œžœžœ)žœ
žœžœžœžœ3žœ
žœ�œžœžœ�œžœ
žœ�œžœRŸœžœžœ"žœ•
Ÿœžœ
žœ
žœ
žœ
žœ	žœ7Ÿœžœžœžœ!žœžœ.žœ
žœŸ	œžœžœžœžœžœŸœžœžœ
žœžœžœžœ�·
œ
Ÿœžœžœ
žœ
žœžœ�Fœ�>œ
Ÿœžœ
žœ
žœžœ	žœžœžœžœ,Ÿœžœ
žœ
žœ
žœžœžœEžœ
žœ�+œžœ
žœžœžœžœ
žœžœžœÊ
Ÿœžœ
žœ
žœ
žœžœžœEžœ
žœ žœ
žœžœžœžœ
žœžœžœÎ
Ÿœžœ
žœ
žœ
žœ
žœUžœŸœžœ
žœFžœžœ*žœžœ
žœEžœžœ-žœ8žœ
žœ�?œ	žœ
žœ	žœŸœžœ
žœGžœ+žœ
žœ
žœžœ	žœžœžœžœ	žœ"žœžœ7žœžœžœ�œ	žœ9žœ>žœ�(œ
�IœD�@œ�=œžœ
žœžœ�œžœžœ(žœmžœ
žœ#žœ �Pœžœ	žœ(žœ†
žœžœžœ
�(œ-žœ
žœ6žœžœ"žœžœ
žœžœžœ	žœžœžœ
žœžœ	žœžœ
žœ žœ
žœžœ�œŸ
œžœ
žœ	žœ
žœžœžœ*žœ,žœ
žœUžœSžœ�Ÿœžœ
žœ
žœžœžœžœžœžœžœžœsžœBŸ œžœ
žœ
žœ
žœ
žœlžœžœ
�œžœ Ÿœžœ
žœ*žœ(žœ
žœ žœ
žœî
žœ&žœ#žœGžœ&žœ$žœ}žœžœ¶
žœž	œ%�@Ÿœžœ	žœžœMžœ	žœ-žœžœ"žœpžœžœ<žœ
žœ
žœžœ5žœŸœžœ
žœ
žœ
žœžœžœžœ
žœžœ:žœžœŸœžœ
žœžœ
žœžœ!Ÿœžœ
žœžœ:žœSžœ
žœå
žœž	œž	œž	œŸœžœ
žœ(žœ
žœžœ*žœ
žœ
žœžœNžœžœžœ(žœžœ$žœžœžœžœžœžœ
žœžœžœ
žœžœ
�œ6žœ
žœžœ	Ÿœžœ
žœ
žœžœžœžœ
žœžœ
žœIžœžœ
žœ
žœžœžœžœ8žœžœžœ/žœžœžœžœCžœžœ
žœžœžœžœRžœ žœžœžœ
žœ#�œžœžœ"žœ2žœžœ
žœ.žœžœ	žœ	žœ
žœžœžœžœ
žœ
žœ�œ,žœžœ
žœžœŸœžœ
žœ
žœžœžœ
žœ�dœžœ
žœ
žœžœ’
žœ
žœ
žœžœžœ�	œžœ
žœ	�œžœžœ
žœ
žœžœežœ$žœ)žœ&žœ
žœžœ
žœ�
œ(�œžœžœ
žœžœžœ
žœ
žœ�
žœ0žœ
žœžœ
žœžœ&žœ-žœžœ�	œžœžœ	�œžœžœ
žœ
žœžœ’
žœžœ�œžœ$žœ0žœT�œžœ
žœ�œžœ	žœ
žœ7�.œžœ!žœ�	œžœžœžœžœ
žœ
žœžœ“
žœžœžœžœžœ[�œžœ
žœ�œžœ
žœ�œUžœ�œžœžœžœ�œ
Ÿœžœ
žœžœž	œŸœžœ
žœ�,œŸœžœ
žœžœžœžœž
œ žœ.Ÿœžœ
žœž�'œŸœžœ
žœžœ
žœ
žœžœ
žœžœ
žœžœžœžœ
žœžœ
žœžœ4žœžœ
žœ
žœ
žœNžœ"žœžœ.Ÿœžœ
žœžœ�)œžœžœž
œžœ$Ÿœžœ
žœžœ�)œžœžœž
œžœ-�^Ÿœžœžœ
žœ
žœžœžœžœžœžœžœ	Ÿœžœ
žœ�œ(žœ
žœ
žœžœžœ"žœH�œžœžœžœ
žœ
žœžœ,žœ
žœžœ
žœžœ#žœžœžœ�œ
žœ	žœ
žœ5�œžœžœžœ"žœ-žœžœžœ†
žœ&žœ,žœƒ
žœžœžœ4žœ"žœ(žœNžœ�œI�œžœžœ%žœWžœ	�œ žœžœ(žœ	žœ
žœ4�œžœ$žœ�œžœ"žœ,žœgžœ
žœ6žœtžœžœžœ	�Cœ�?ŸœžœdžœPžœ)žœ,žœžœžœžœ�œžœ'žœ'žœPžœ)žœ¡
žœ*žœ.žœ,žœ2žœ(�2œ
Ÿœžœ
žœ
žœ
žœ
žœ
žœžœ
Ÿ
œžœ
žœ
žœ
žœ
žœ
žœžœ
�8œ�Bœ�7Ÿœžœ
žœ�)œžœ"žœžœžœžœ
�Dœ�6œžœžœ8žœ
žœ¼
žœžœÕ
�+œxžœ6�œžœ=žœ+�œžœžœ
žœ
žœ
žœžœžœ
žœžœ
žœ1žœ‹
žœ
žœ
žœ
žœžœ
žœžœ
žœžœ
žœ
žœžœ
žœ
žœ
žœ
žœ
žœžœ
žœžœžœkžœžœ
žœ%�"œ6�(œžœ=žœ
žœº
žœžœ˜åì—…—¶hΫ