-- RTRefCountsImpl.Mesa
-- last edited August 30, 1982 10:39 am by Willie-Sue
-- last edited December 8, 1982 11:09 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],
RuntimeInternal USING[Codebase],
SafeStorage USING[TrimAllZones, TrimRootBase, ReclamationReason, NWordsAllocated,
MergeAllPrefixedZones],
TrapSupport USING[BumpPC, GetTrapParam],
RTZones USING[PMapZiZn, RMapSziSz, RMapQZf];

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 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.