:IF[WithCedar]; ******************************
TITLE[Cedar0];
%
Ed Fiala 27 April 1983: move GC/GChi from 64-65 to 20-21.
Ed Fiala 21 December 1982: Renumber AssignRef and AssignRefNew as 372 and 373
rename opcodes as follows: AssignRef to WCDLB, AssignRefNew to WCIDLB,
ReclaimAll to FindReclaimableRefs, CreateRef to NewRef, AllocHeap to
AllocPrefixed, GCSetup to CedarState, CollectCount to ReadZeroCount,
LongBlkZ to BLZL; add PSCDLB and PSCIDLB opcodes which reverse args for
SCDLB and WCIDLB.
Ed Fiala 19 May 1982: Convert for Trinity: change traps, Esc alpha
assignments, NopInt calls; move dispatch onto moPage; split into two
files; absorb LongBlkZ and LocalBlkZ opcodes.
Ed Fiala 11 May 1982: Make change to GetRefType trying to avoid bug.
Ed Fiala 22 April 1982: Add GetRefType and GetCRefType opcodes; fix
bug in CreateRef change; fix bug in AssignRef not preserving OnStack when
RefCnt .le. RCFinalize; while doing this, speed up AssignRef and CreateRef
slightly; make AssignRefNew same as AssignRef; speed up ReclaimRef by
6 cycles; bum many mi.
Ed Fiala 24 February 1982: Change error check in CreateRef to crash
only if RefCnt in existing entry .ne. value CreateRef would have put
there. If RefCounting disabled in gcRCEMask and if gcProcNo .ne. 0,
then trap on AssignRef, AssignRefNew, and CreateRef with TrapParm .eq. 2.
If ref counting disabled and gcProcNo .eq. 0 then CreateRef = Noop and
AssignRef and AssignRefNew = store 2 words. Fix page fault problem in
AssignRef by doing NIL store after refOld update and by writing the new
value after refNew update. Add RCeqRCFinalize counter. Fix tasking after
gcFind calls in ReclaimRef and AssignRef. Change UVersion to 13b.
Ed Fiala 8 October 1981: Create from Dorado implementation.
1) Modify ReclaimAll to use 128d-entry table so one call exhausts a PI.
2) Add ReclaimRef opcode replacing unusual AlterCount used previously.
Change AlterCount to never return a value and to manipulate OnStack and
RefCnt fields in a consistent way for all calls.
3) Eliminate RCEReclaim (An appropriate AlterCount is equivalent).
4) Rearrange data structure so that a single base register suffices;
change word allignment for the Dolphin.
5) Use odd word of last OT cell in a chain for RCE.
6) Reverse args for CreateRef.
7) Thread free list through even words of OT cells (Must terminate with 0).
8) Change in the Collector process wakeup algorithm.
9) Require Ref’s to be even; change hashing algorithm and RCE format.
10) Restrict NPR < RCFinalize and RCFinalize=(2↑n)-1.

The collector stores RCEs for Refs; an RCE newly-created by NewRef is
entered with RefCnt .eq. RCFinalize-NPR (NPR = no. package references, an
argument .le. 2); as each new pointer to the Ref is created by WCDLB,
RefCnt is increased by 1, up to 127d. An RCE attaining RefCnt=127d freezes
at that value, becoming uncollectable. As Refs are dereferenced (by
WCDLB, ReclaimRef, and AlterCount), RefCnt is reduced by 1. The
Collector will examine RCEs with RefCnt .le. RCFinalize.

To reduce table size, RCEs with RefCnt=RCFinalize+1 (the most common case)
are not kept in the table (unless the OnStack bit is also 1); this is
accomplished by the following algorithm:

Add 1Sub 1
127dRemains 127d.127dRemains 127d.
RCFinalizeIf OnStack=0, destroy0Crash--bug.
RCE; elseRCFinalize+2If OnStack=0, destroy
RefCnt ← RefCnt+1.RCE; else
otherRefCnt ← RefCnt+1.RefCnt ← RefCnt-1.
no entryCreate with RefCntotherRefCnt ← RefCnt-1.
.eq. RCFinalize+2no entryCreate with RefCnt=
and OnStack=0RCFinalize, OnStack=
(rcMask & OnStack).

The collector uses a contiguous 64k-aligned block of storage. The GC base
register points at its origin and all pointers in the hash table (HT) and
overflow table (OT) are relative to GC. Words of interest are as follows:

0gcFLdisplacement to 1st cell on free list
1gcFLCount
biased count of OT free list cells; trap when an OT cell is
needed and gcFLCount .le. 0 unless collector is running.
2gcRCEMask
00 if ref-counting allowed; 1 if ref-counting disabled
1:7RCEMask (always 177b)
8dOnStack (0 normally, 1 during a collection)
9:15dzeroes
3gcProcNo
Collector process id (.eq. 0 when collector not running)
4- 5LP to table indexed by Ref rsh 10d containing zone (.ge 0)
or zone index (.ls. 0).?? RTZones.RMapQMz
6- 7LP to table describing zones by subzones. RTZones.RMapSziSz
10- 11LP to table indexed by zone index containing LP to zone.
RTZones.PMapZiZn.
12- 13LP to table indexed by type containing LP to canonical type.
RTTypesBasicPrivate.RMapTiTd.
14- 15Count of HT or OT entries with RefCnt .eq. RCFinalize.
16- 131unused
132- 177Optional counters (defined for Mesa debugger prettyprint--
these counts don’t necessarily occur) defined later.
200- 377table for entries with RefCnt<=RCFinalize on FindReclaimableRefs
400-100377HT (hash table--1 word/cell)
100400-177777OT (overflow table--2 words/cell, length determined by
software)

gcFL and gcFLCount are initialized by the GCSetup opcode and are then handled
only by opcodes in this module--this allows both words to be cached in
registers. gcRCEMask, gcProcNo, and optional counters may also be cached in
registers--software must execute another GCSetup opcode after one of these
registers changes before and after a collection. The switch argument to
GCSetup determines whether or not gcFL, gcFLCount, and optional counters are
being loaded from storage on initialization or being stored back into storage
prior to examination by software.

An RCE is accessed by hashing a 22-bit Ref into a 15-bit probe index (PI) and
6-bit residue (R). PI is bits 10:15d xor bits 16:30d; R = bits 10:15d; PI
indexes HT, formatted as follows: A one-long chain is contained within the
HT cell; otherwise, HT points to an OT cell containing a RCE in the 1st word
and either a RCE or a pointer to another OT cell in the 2nd word. Every word
in HT or OT has the following form:
If bit 0 is 0, the word is a RCE:
1:7RefCnt
8OnStack
9:15Residue (allows one extra bit)
else if bit 0 is 1, the word is a pointer or empty:
0:15dindex of next OT cell in chain (always even);
-1 denotes an empty entry (HT only--illegal in OT)

The 1st word of an OT cell is NEVER a pointer and the 2nd word is NEVER empty.
In other words, a NIL pointer or empty word is disallowed since the chain can
be collapsed in this case.

The free list pointed to by gcFL threads through even words of OT cells and
is terminated by a 0 (odd word values are ’don’t care’). gcFLCount is
initialized to the number of cells on the free list minus a parameter. Any
process which tries to create a new cell and finds gcFLCount .le. 0 will trap
unless the process is the Collector. Software then wakes the Collector and
blocks. The Collector process can acquire OT cells until the free list is
entirely exhausted (denoted by a 0 pointer in gcFL).

Initially the Collector is quiescent and OnStack bits in RCE’s are all 0;
clients set OnStack=0 on every operation. When a collection starts, the
Collector sets OnStack=1 in gcRCEMask and executes another GCSetup to transmit
the gcRCEMask change to microcode. The only operations affected by OnStack
in gcRCEMask are NewRef and WCDLB, which sets OnStack=1 when
decrementing RefCnt as described earlier.

The Collector uses AlterCount to mark RCEs with OnStack=1 for all double
words on process stacks; a pointer with no HT/OT entry is entered with
RefCnt=RCFinalize+1 and OnStack=1. If the conservative algorithm creates some
RCEs for non-Ref doublewords, no great harm is done because those RCEs will
be discarded after collection, and NewRef can cope with such an extraneous
RCE that happens to match a Ref being created.

RCEs with RefCnt<=RCFinalize & OnStack=0 are enumerated by FindReclaimableRefs.
For each of these, software determines whether reclaim is possible; if so,
ReclaimRef is used on Refs inside the object, and any of these having its
RefCnt decremented to RCFinalize is handled in the same way as those
enumerated by FindReclaimableRefs (If RefCnt for one of these was already .le.
RCFinalize, then FindReclaimableRefs already enumerated or will enumerate it,
so no futher action is necessary).

When done, the collector sets OnStack mode for client processes to normal
again and uses ClearOnStack to sweep HT/OT clearing OnStack bits and
release RCEs with RefCnt=RCFinalize+1.

NOTES:
1) Opcodes that call gcFind and the *RefType opcodes may trap with TrapParm=1;
NewRef, and WCDLB map trap with TrapParm=2. The first is for a
collector wakeup; the second is because the trace and sweep is running and
wants the world to be stable.
2) Page 0 of GC must be locked down for statistics counters and GCSetup.
3) Software should check for RefCnt=0 in the RCEs returned by
FindReclaimableRefs and flag a bug if this ever happens (Microcode checks for
RefCnt going below 0, but exactly 0 check is too expensive).

Possible Changes or problems:
1) Change some opcode from Esc to regular after WCIDLB eliminated.
2) Use 8 unused bits in GChi and/or the wasted bit in gcFL to indicate
"collector off" and "collection in progress" eliminating gcRCEMask; then
need only one more permanent register for gcProcNo.
3) Permanent register for RCeqRCFinalize.
4) Gather precisely those stats needed to decide when to collect.
5) Disallowing RCE’s for Ref’s .ls. 64k saves 2 cycles per gcFind call.
6) Consider RCE-to-Ref opcode.
7) Consider swapping the collector microcode (ReclaimRef, AlterCount,
FindReclaimableRefs, ClearOnStack).
%

RV2[GC,GChi,20];*Permanent base register
RV2[gcFL,gcFLCount,24];*permanent free list pointer and count

*General temporaries
*TrapParm (RM 50) holds alpha.
*RTemp (RM 52) holds alpha and must be preserved until trap is impossible.
RV2[gcRCEMask,gcProcNo,44];
RV2[gcStat0,gcStat1,46];
RV2[gcCAR,gcCDR,70];*gcCDR is used for HT cells and odd words in OT
*cells, gcCAR for even words in OT cells.

*LP and LPhi (RM 66 & 67) are used by @WCDLB.
*RM 40 and 56-57 are for sure available here (maybe others).
RV2[gcRef0,gcResidue,72];*For @WCDLB; gcResidue for gcFind
RV[gcReturnPC,72];*For gcFind
RV2[gcCADR,gcCDDR,72];*For @ClearOnStack
RV[gcRecIndex,72];*For @FindReclaimableRefs
RV[gcRAVal,73];*For @FindReclaimableRefs
RV[gcPred,53];*For gcFind, @ClearOnStack
RV[gcNewCell,51];*For gcFind

MC[OnStack,200];
Set[RCFinalize,3];
MC[RCFinalizePlus1,4];
MC[RCFinalizePlus1LSh1,10];

*Displacements in GC structure
Set[QMap,4];*Long pointer to quantum map; word 0 is nentries
*(always 4096d); one-word entry contains 14d-bit
*type if bit 0 is 0 else 15d-bit zone).
Set[SubZMap,6];*Long pointer to subzone map; word 0 is nentries;
*entries are long pointers to zones.
*Word 0 of a zone is its type.
Set[CMap,12];*Long pointer to ? table indexed by type. Word 0
*is nentries; words 1-2, 3-4, etc. are long pointers
*to the word containing the canonical type.
MC[ReclaimOffset,200];*0th word of 200b-word Reclaim table
MC[HTOffset,400];
MC[HTLength,100000];**Branch conditions "know" this value.
MC[OTOffset,100400];

MC[sCatastrophe,171];
MC[OTCarNotEntry,0];*Even word of OT cell not a RCE (.ls. 0)
MC[BadOTPointer,1];*Pointer in HT or OT .ls. OTOffset
MC[RefNotEven,2];*Ref arg not even
MC[BadCreate,3];*NewRef on already-existing RCE with OnStack=0
MC[RCBelowZero,4];*Attempt to make RefCnt<0
*Codes 6 reported by Dorado microcode.
MC[BadMapIndex,7];*Table index .gr. word 0 of the table
MC[ReferentOnFL,10];
MC[BadFLPointer1,11];*Pointer from free list odd
MC[BadFLPointer2,12];*Pointer from free list .ls. 100400b.
MC[DelBadPtr,13];*Pointer added to FL not even or .ls. 100400b
MC[BadPackRefCnt,14];*Package reference count not in range 0 to 2.
* MC[BadHTE,15];*HT entry .ls. 0, odd, and .ne. -1

MC[ARFakeAlpha,0];*Fake Esc alpha value for @WCDLB traps.

MC[FLEmptyTP,1];*Free list empty trap parameter (from gcFind).
MC[NotCanonicalizedTP,1];
MC[TSRunningTP,2];*Trace and sweep collector running trap parameter.

MC[UVersion,13];*Must agree with declaration in AllocRC.Mesa

*Also have 21b mi on moPage and 16b mi on opPage3
Set[gcPage,2];*344b mi (+26b mi if gcStats=1)
*1-5, 10-15, 21-23, 25-30, and 32-34 are used in FindRetTab
Loca[FindRetTab,gcPage,0];
Set[gcPage2,2];*1b mi
Set[gcPage3,2];*1b mi
Set[gcPage4,3];*154b mi (+10b mi if gcStats=1) must have refill


%To look at the GC structure with the Mesa debugger:
Set Root Configuration RT
Set Module Context RTRefCountsImpl
GCState↑looks at first 400b words of GC
MapPiRce[n]looks at HT entry n
MapOiOe[m]looks at OT entry m

The constants below are offsets from GC to double-precision event counters
that are implemented if gcStats=1.

Number of existing Refs is CRCtr-RRDelCtr+ACSubCtr-ACAddCtr.
Number of Refs freed is ACAddCtr+RRDelCtr (i.e., ACAddCtr counts Refs
delivered by FindReclaimableRefs that are freed and RRDelCtr counts the number
threading from those which are freed).

One proposed algorithm for deciding when to do a collection needs the best
guess possible for the amount of storage reclaimable by a collection.
An estimate for this quantity can be made by estimating:
(1) No. Refs enumerated by FindReclaimableRefs that will be freed;
(2) The expected number of Refs reclaimed for each of the ones enumerated;
(3) The expected size of each item reclaimed.
(1) can be approximated by the number of Refs with RefCnt=RCFinalize; the
error in this approximation is ones that are OnStack plus (?) ones that have
experienced finalization. ACAddCtr+RRDelCtr/ACAddCtr approximates (2) by its
historical average. (3) can be estimated either by tracking block size and
number of frees in previous collections or by tracking storage allocated
since the last collection.

RCeqRCFinalize is used algorithmically (therefor not optional).

ACZeroCtr, ACSubCtr, ACAddCtr, OTDelCtr, OTCreCtr, HTDelCtr, HTCreCtr are
displayed by software as of 18 February 1982, but not used algorithmically
(therefor can change or deimplement). Dorado has the AC*Ctrs used for
all gcFind calls not just AlterCount calls.
%
MC[RCeqRCFinalize,14];*HT/OT entries with RefCnt .eq. RCFinalize.

Set[gcStats,1];*Enables optional event counters enumerated below


*Numbers in () are for an early run of a Poplar test program.
MC[FreeQCtr,114];*() FreeQuantized completions
MC[FreeHCtr,116];*() FreeHeap completions
MC[FreeObjCtr,120];*() FreeObject completions
MC[AllocQCtr,122];*() Allocate Quantized completions
MC[AllocHCtr,124];*() Allocate Heap completions
MC[RefTypeCtr,126];*() RefType completions
MC[CRefTypeCtr,130];*() CRefType completions
MC[ACIllCtr,132];*( 9394) AlterCount calls with NIL or odd Ref arg.
MC[ACZeroCtr,134];*( 37957) AlterCount completions not changing RefCnt
*(must be setting OnStack=1).
MC[ACSubCtr,136];*( 0) AlterCount completions subtracting from
*RefCnt (must be fixing RefCnt for a ReclaimRef which
*found no RCE but had finalization).
MC[ACAddCtr,140];**( 81656) AlterCount completions adding to RefCnt (must be
*flushing RCE delivered by FindReclaimableRefs).
MC[OTDelCtr,142];*( 25107) OT cell deletions
MC[OTCreCtr,144];*( 25223) OT cell creations
MC[HTDelCtr,146];**(404897) HT deletions
MC[HTCreCtr,150];**(420811) HT creations
MC[RRNilCtr,152];*( 0) ReclaimRef completions with NIL arg
MC[RRNoDelCtr,154];*( 192353) ReclaimRef completions (not deleted)
MC[RRDelCtr,156];**(259909) ReclaimRef completions (already deleted)
MC[RACtr,162];*( 123) FindReclaimableRefs completions
MC[CRCtr,164];*( 351059) NewRef completions
MC[ARCtr,166];*(1047322) WCDLB completions refNew non-NIL
* (not including those with the collector disabled).
*MC[ARNCtr,170];*Deimplemented
MC[RONilCtr,172];*( 737678) RefOld=NIL in WCDLB (+ page fault restarts
*and collector disabled WCDLBs as an error term)
MC[RNNilCtr,174];*( 272916) WCDLB completions with RefNew=NIL
*MC[ROeqRNCtr,176];*RefOld=RefNew in WCDLB

gcRefill:
PFetch4[PCB,IBuf,4], GoToP[MesaRefill], At[LShift[gcPage,10],377];

gcCount:
PFetch2[GC,gcStat0];
gcCount1:
gcStat0 ← (gcStat0) + 1;
gcStat1 ← (gcStat1) + 1, UseCOutAsCIn;
PStore2[GC,gcStat0], GoTo[gcRet];

gcUnimp:
T ← RTemp ← (RTemp) + (EscTrapOffset), GoToP[BackTrap];

*Jump here when data structure is found to be inconsistent.
gcBug:StkP ← RZero;*For Midas breakpoint
LoadPage[opPage3];
T ← sCatastrophe, GoToP[kfcr];

*Jump here from @ReclaimRef, @FindReclaimableRefs
gcPushTTail:
LU ← NextInst[IBuf];*Odd placement; paired with gcRAInt-1
gcPushTTailx:
Stack&+1 ← T, NIRet;

%Esc dispatch. Timing = 14.5 cycles (including buffer refill) to the 1st
working mi for the opcode.
T ← MNBR ← CNextData[IBuf], Call[.+2], Opcode[273];
LU ← NextInst[IBuf], Call[P6Tailx];
RTemp ← T, LoadPage[moPage], Skip[H2Bit8];
Dispatch[RTemp[10,4], GoToP[.+3];
LU ← (RTemp) - (EscLast) - 1, GoToP[.+1];
OnPage[moPage];
Dispatch[RTemp,10,4], GoTo[moUnimp,ALU>=0];
Dispatch[RTemp,14,4], Disp[.+1];
...
%
TrapParm ← T, LoadPage[gcPage], Disp[@ReclaimRef], At[EscTop,6];

:IF[gcStats]; **************************************
OnPage[gcPage];
gcUnimpCount:
PFetch2[GC,gcStat0], Call[gcCount1];
LoadPage[opPage0], GoTo[gcUnimp];

@Esc73:T ← AllocQCtr, GoToP[gcUnimpCount], At[EscD6,13];*AllocQuantized
@Esc74:T ← AllocHCtr, GoToP[gcUnimpCount], At[EscD6,14];*AllocPrefixed
@Esc75:T ← FreeObjCtr, GoToP[gcUnimpCount], At[EscD6,15];*FreeObject
@Esc76:T ← FreeQCtr, GoToP[gcUnimpCount], At[EscD6,16];*FreeQuantized
@Esc77:T ← FreeHCtr, GoToP[gcUnimpCount], At[EscD6,17];*FreePrefixed
:ELSE; *********************************************
@Esc73:LoadPage[opPage0], GoToP[gcUnimp], At[EscD6,13];*AllocQuantized
@Esc74:LoadPage[opPage0], GoToP[gcUnimp], At[EscD6,14];*AllocHeap
@Esc75:LoadPage[opPage0], GoToP[gcUnimp], At[EscD6,15];*FreeObject
@Esc76:LoadPage[opPage0], GoToP[gcUnimp], At[EscD6,16];*FreeQuantized
@Esc77:LoadPage[opPage0], GoToP[gcUnimp], At[EscD6,17];*FreePrefixed
:ENDIF; ********************************************

%gcDelChk is called with the results of gcFind to store the RCE or flush
it if RefCnt=RCFinalize+1 and OnStack=0. Have pointer to predecessor in
gcPred, pointer to word holding RCE in MNBR, and other word from OT cell
(if from OT) in gcCDR. No references here can be illegal or fault.
gcDelChk is the entry for AlterCount; gcDelChk0 for ReclaimRef, AlterCount,
and WCDLB; gcPreserve for NewRef and WCDLB; gcDelete for
WCDLB. T contains (RCFinalize+1) lshift 1 at gcDelChk.

Timing: 22 (5 free) if not deleting RCE and RefCnt .ne. RCFinalize,
50 (13 free) if RefCnt .eq. RCFinalize,
25 (14 free) if deleting HT entry, or
43 (14 free) if deleting CDR[OT] or CAR[OT].
"5 free" etc. indicates the dead time of the final PStore reference.
Although these times are long, the references can’t page fault, so the
tasking behavior may be marginally acceptable.
%
OnPage[gcPage];

gcDelChk:*Check OnStack=0 & RefCnt=RCFinalize+1
LU ← (LdF[gcCAR,0,11]) - T;
gcDelChk0:
T ← MNBR, GoTo[gcDelete,ALU=0];
gcPreserve:
PStore1[GC,gcCAR];*Fixup RCE
T ← (gcCAR) xor (LShift[RCFinalize,10]C), Skip[R>=0];
TrapParm ← RCBelowZero, CallX[gcBug];
LU ← (R400) - T - 1;
Skip[ALU<0];
T ← RCeqRCFinalize, GoTo[gcCount];
gcRet:Return;

gcDelete:
LU ← (gcPred) xor T;*Flush the entry
T ← gcPred, GoTo[gcDelOT,ALU#0];
:IF[gcStats]; **************************************
PStore1[GC,AllOnes];*Delete from HT
T ← HTDelCtr, GoTo[gcCount];
:ELSE; *********************************************
PStore1[GC,AllOnes], Return;*Delete from HT
:ENDIF; ********************************************
gcDelOT:
PStore1[GC,gcCDR];*Delete from OT: copy gcCDR into predecessor.
gcCollectMNBR:*Only 1 entry here (from @ClearOnStack)
T ← gcFL;
gcCollectCAR:*Only 1 entry here (from @ClearOnStack)
gcNewCell ← T;
T ← 1C;
T ← (MNBR) and not T, Skip[R<0];
TrapParm ← DelBadPtr, CallX[gcBug];
gcCollectAny:
gcFLCount ← (gcFLCount) + 1;
gcFL ← T;
:IF[gcStats]; **************************************
PStore1[GC,gcNewCell];
T ← OTDelCtr, GoTo[gcCount];
:ELSE; *********************************************
PStore1[GC,gcNewCell], Return;
:ENDIF; ********************************************

*gcCDR even, .ls. 0 checks here would be redundant
gcCollectCDR:*Only 1 entry here (from @ClearOnStack)
T ← gcCDR, GoTo[gcCollectAny];

%gcResidue holds R and T holds the PI for an entry to be looked up; an
absent entry (RefCnt .eq. RCFinalize+1) is recreated with OnStack=0 except
when the calling mi is at an even location (only ReclaimRef has its call on
an even location); for ReclaimRef, exit with StkP advanced by 1.
Return pointer to the predecessor in gcPred, pointer to the RCE in MNBR,
and the RCE in gcCAR; gcCDR contains the other word if the RCE came from
an OT cell. The three cases are:
1) gcPred .eq. MNBR (entry is in HT);
2) gcPred .ne. MNBR and MNBR odd (entry is in odd word of OT cell);
3) gcPred .ne. MNBR and MNBR even (entry is in even word of OT cell).

Caller must have fetched gcProcNo before the call (except on ReclaimRef) and
must store gcCAR into the word pointed at by MNBR after the return. gcCDR
holds the other word of the OT cell so that gcDelChk can flush the RCE
faster later.

Caller will modify gcCAR and then call gcDelChk to store back the results.
The caller must task before calling gcDelChk because at exit from gcFind
the time since last task may be over 20 cycles.

Timing:28 cycles (31 for @ReclaimRef) not found in empty chain
66 (10 free) cycles (28 for @ReclaimRef) not found in one-long chain
92 (10 free) (54 for @ReclaimRef) + 24*N cycles not found in OT chain
*Longer times when found occur for RefCnt .eq. RCFinalize
(31 or 61 (10 free)) cycles found in one-long chain
(48 or 78 (10 free)) + 24*N cycles found in CAR of OT chain
(63 or 93 (10 free)) + 24*N cycles found in CDR of OT chain
where N is the number of OT cells preceding the one in which match occurs
or preceding the last cell in the chain if no match. "14 free" means that
the next 14 cycles are during the dead time of a memory reference.
+ 9 cycles if not found during a collection when gcFLCount .ls. 0
%
gcRefUneven:
TrapParm ← RefNotEven, CallX[gcBug];*Odd placement
gcFind:T ← (R400) + T, LoadPage[gcPage4];*Know HTOffset=400b
PFetch1[GC,gcCDR];*Fetch HT entry
OnPage[gcPage4];
gcPred ← T, UseCTask;*Bypass kludge ok since GC=0
T ← APCTask&APC, Task;
gcReturnPC ← T;
MNBR ← gcPred, Task;
T ← gcResidue;
LU ← (LdF[gcCDR,11,7]) xor T, GoTo[gcFindIndEmpty,R<0];
*A single entry is in gcCDR and its residue in T--check for match.
T ← gcCDR, GoTo[gcFindNM,ALU#0];
*Match.
gcCAR ← T;
%Reduce the count of RCE’s with RefCnt .eq. RCFinalize, whenever gcFind
returns such an entry. Caller must call gcDelChk, which increments
the count if the value stored back has REfCnt .eq. RCFinalize.
%
gcRCFinalizeCount:
T ← (gcCAR) xor (LShift[RCFinalize,10]C);
LU ← (R400) - T - 1, Call[gcRCF1];
gcStat0 ← (gcStat0) - 1;*Single precision since GC 64k words
PStore1[GC,gcStat0,RCeqRCFinalize!], GoTo[gcFExit];

gcRCF1:APCTask&APC ← gcReturnPC, GoTo[gcFRet,ALU<0];
PFetch1[GC,gcStat0,RCeqRCFinalize!], GoTo[gcFRet];

:IF[gcStats]; **************************************
gcFindLogHT:
gcReturnPC, LoadPage[gcPage], Skip[R Odd];
T ← HTCreCtr, GoToP[gcCount];
gcFindRRLog:
T ← RRDelCtr, GoToP[gcCount];
:ENDIF; *******************************************

%Entry not found and one or more other RCE’s at the HT chain where it would
be. Recreate it using a cell from the free list; however, trap if
gcFLCount .le. 0 so that software can wake up the collector process.
The previous final list element is put in the odd word of the new cell and
the new entry in the even word; the predecessor is replaced by a pointer to
the new cell.
Timing from gcFind to here: 21 from HT, 47 + 24*N from OT.
%
gcFindNM:
gcReturnPC, GoTo[gcFindNotRR,R Even];
*gcFind called by @ReclaimRef; finish up and exit.
:IF[gcStats]; **************************************
LoadPage[gcPage], Call[gcFindRRLog];
:ENDIF; ********************************************
LU ← NextInst[IBuf];
gcFindPushTailx:
Stack&+1, NIRet;
gcFindNotRR:
T ← MNBR ← gcFL, Skip[R Even];
TrapParm ← BadFLPointer1, CallX[gcFBug];
*The PFetch1 to advance the free list unfortunately has to be before all
*three references below because of a possible page fault.
*Extra ref at end of free list must not (and won’t) fault because the free
*list is terminated with 0.
PFetch1[GC,gcFL], FreezeResult, GoTo[gcFindNM1,ALU<0];
LU ← gcFL, GoTo[gcOTEmpty,ALU=0];*Totally out of free OT cells
TrapParm ← BadFLPointer2, CallX[gcFBug];
gcFindNM1:
gcNewCell ← T;*Bypass kludge ok since GC=0
*Store 2nd word of new cell (gcCDR). Storing gcCAR is unnecessary because
*the caller always changes it and stores it. PStore1 below will page fault
*whenever the PFetch1 above faults.
T ← (MNBR) + 1;
PStore1[GC,gcCDR];
T ← (gcResidue) + (LShift[RCFinalizePlus1!,10]C), Call[gcTtoCAR];
*Trap to software if no freelist entries are left during a collection
*(indicated by a 0 in gcFL) or if gcFLCount .ls. 0 otherwise--gcFLCount is
*biased.
gcFLCount ← (gcFLCount) - 1, Skip[R<0];
T ← gcPred, GoTo[gcFindNMGo];
*Allow GC process to go ahead when count runs out; trap others.
T ← prCurrentPsb, Call[gcFRet];
LU ← (gcProcNo) xor T;
T ← gcPred, GoTo[gcFindNMGo,ALU=0];
*Fix gcFL, gcFLCount, and StkP prior to trap
gcFLCount ← (gcFLCount) + 1;
T ← MNBR;
gcOTEmpty:*Jump here from above when FL totally exhausted.
RTemp ← (RTemp) + (Sub[EscTrapOffset!,SDOffset!]C);
gcFL ← T, LoadPage[opPage0];
TrapParm ← FLEmptyTP, GoToP[P4Trap];
OnPage[gcPage4];
*Store pointer to OT cell in predecessor
*Returns to caller 21 (10 free) cycles from last task.
gcFindNMGo:
PStore1[GC,gcNewCell];
:IF[gcStats]; **************************************
LoadPage[gcPage];
T ← OTCreCtr, Call[gcCount];
:ENDIF; ********************************************
gcFExit:
APCTask&APC ← gcReturnPC, GoTo[gcFRet];

*19 cycles from gcFind to here.
gcFindIndEmpty:
T ← gcCDR, GoTo[gcFindI1,R Even];
*HT cell was empty.
:IF[gcStats]; **************************************
Call[gcFindLogHT];
:ENDIF; ********************************************
T ← (gcResidue) + (LShift[RCFinalizePlus1!,10]C);
*Return to caller 12 cycles from last task.
APCTask&APC ← gcReturnPC, Skip[R Even];
*gcFind called by @ReclaimRef--adjust StkP and exit
LU ← NextInst[IBuf], CallX[gcFindPushTailx];
*Other gcFind calls return result in gcCAR--do not have to store gcCAR
*because caller will do it.
gcTtoCAR:
gcCAR ← T, Return;

gcFindInd:
T ← gcCDR, Skip[R Even];*Even placement
TrapParm ← BadOTPointer, CallX[gcFBug];
*Fetch OT cell into gcCAR/gcCDR
PFetch2[GC,gcCAR];*Bypass kludge OK since GC=0
*Next 3 mi do gcPred←MNBR+1, MNBR←T.
gcPred ← T, Task;
T ← (MNBR) + 1;
MNBR ← gcPred, gcPred ← T, NoRegILockOK, GoTo[gcFindI2];

*Jump here with the HT word in T known to point at an OT cell.
gcFindI1:
PFetch2[GC,gcCAR];*HT cell was indirect
gcNewCell ← T, Task;
MNBR ← gcNewCell;
gcFindI2:
T ← gcResidue, Call[gcFindI3];
MNBR ← gcCDR, gcCDR ← T, NoRegILockOK, Call[gcMNBRToT];
*APCTask&APC ← gcReturnPC; MNBR ← gcCAR, gcCAR ← T, NoRegILockOK, Return;
*Done. Match in gcCDR.
MNBR ← gcCAR, gcCAR ← T, NoRegILockOK, GoTo[gcRCFinalizeCount];

gcFindI3:
LU ← (LdF[gcCAR,11,7]) xor T, Skip[R>=0];
TrapParm ← OTCarNotEntry, CallX[gcFBug];
*APCTask&APC ← gcReturnPC, GoTo[gcFRet,ALU=0];
GoTo[gcRCFinalizeCount,ALU=0];*Done if match in gcCAR.
*Even word of OT cell doesn’t match, check odd word.
LU ← (LdF[gcCDR,11,7]) xor T, GoTo[gcFindInd,R<0];
T ← (MNBR) + 1, Skip[ALU=0];
*No match in OT cell. Put new entry in even word of cell from free list.
gcPred ← T, GoTo[gcFindNM];
*Match in odd word of OT cell.
*Next six mi do: MNBR←MNBR+1, Exchange(gcCDR,gcCAR)
MNBR ← gcCAR, gcCAR ← T, NoRegILockOK;
gcMNBRToT:
T ← MNBR, Return;

gcFBug:LoadPage[gcPage];
GoToP[gcBug];

gcFRet:*Even; paired with gcFindI3+3
Return;

:INSERT[Cedar1];