*-----------------------------------------------------------
Title[DMesaRefCount.mc...December 13, 1982 3:14 PM..WSH];
*-----------------------------------------------------------
** PILOT ONLY version
*-----------------------------------------------------------
top level;
*-----------------------------------------------------------
* ALTERCOUNT[rcv, ref] RETURNS nothing
*-----------------------------------------------------------
ALTERCOUNT: MiscTable[61], * AlterCount
rbase← rbase[rcv], Stack&-3;
residue← T AND (77C);
T← (Stack&+1), membase← gcMapPiRce;
branch[acOK, R even], Q← Stack&-2; * check for refLo being ODD
pd← T XOR (onStackBit);
branch[.+2, alu=0], T← 2C;
branch[cats]; * ref ODD and not setting onStack
IFUNext0; * ref ODD and doing onStack => do nothing
acOK: rcv ← T AND (refCtMask);
onStack← T AND (onStackBit);
T← (B← Q) rsh 1;
probe← (residue) XOR T;
oofNum ← T - T, Call[HTFind];
IFUNext0;
*-----------------------------------------------------------
* CREATEREF[npr, ref] RETURNS nothing or calls Catastrophe
*-----------------------------------------------------------
CREATEREF: MiscTable[67], * CreateRef
rbase← rbase[rcv], Stack&-3;
Q← (Stack&+2);
T← (deleteRefCt);
rcv← T - (Q);
onStack← onStackBit;
call[MapRefPiRes];
branch[crf2, R<0], probe; * branch if gc is stopped
oofNum ← 1C;
Call[HTFind]; * returns stored entry in T
T← T AND (refCtMask), Stack&-1; * point to npr
T← T + (Stack); * RefCt + npr
pd← T XOR (rcFinalizeShifted); * should have RefCt+npr = rcFinalize
branch[.+2, alu=0], T← 3C;
branch[cats]; * entry already in table with RefCt#Absent
Stack&-1, IFUNext0;
knowrbase[rcv];
crf2: pd← gcProcNum;
branch[.+2, alu#0], rbase← rbase[TrapParam]; * skip if T&S not running
IFUNext0, Stack&-2; * ref was NIL or gcStopped => FALSE
TrapParam← 2C;
branch[MiscOpCodeTrap];
*-----------------------------------------------------------
IFUR[WCLB, 2, LPtr]; * Write counted long byte
** ASSIGNREF[refNew, ptrRef] => RETURNS nothing
* (<[stack[top],,stack[top-1]> + alpha)↑ ← <stack[top-2],,stack[top-3]>
** implementsAlterCount[refOld, DeleteRef], ptrRef↑ ← refNew, then AlterCount[refNew, AddRef]
*-----------------------------------------------------------
T← ID, Stack&-1, Branch[arm1];
:IfMEP;
T← ID, Stack&-1← MD, Branch[arm1];
T← ID, Branch[arm1];
:EndIf;
arm1: call[LPtrfromStackT]; * load LPtr from Stack + T
knowrbase[rcv];
** StkP points to refNewLo
Stack&+3;
branch[doAssign, R<0], Stack&-2;
** StkP points to refNewHi
** refOld is in Md,,T; see if refNew (StkP,,StkP-1) = refOld
pd← (Stack&-1) XOR Md; * compare hi parts
branch[.+2, alu=0], pd← (Stack&+3) XOR T; * compare low parts
branch[arm1x], pd← T OR Md;
branch[arm1x, alu#0];
Stack&-4, IFUNext0; * refNew = refOld => do nothing
** need to worry about possible page faults
** do DeleteRef on refOld (in Md,,T(probe))
** then set the hi bit of ptrRef (at Top of Stack) as a flag
** if the AddRef on refNew page faults, we won't do another DeleteRef
arm1x: branch[arm2, R>=0], T← gcStateMask;
pd← gcProcnum; * gcStopped, check if TandS running
branch[armx, alu#0];
branch[arm2x], Stack← (Stack) OR (100000C);
arm2: onStack← T AND (onStackBit), T← Md;
T← residue← T AND (77C);
pd← (probe) OR T;
branch[.+2, alu#0], probe← (probe) rsh 1; * refOld=NIL
branch[arm2x], Stack← (Stack) OR (100000C);
probe← (probe) XOR T, membase← gcMapPiRce;
oofNum← 2C;
rcv← DeleteRefCt, call[HTFind];
** StkP points to PtrRefHi
Stack← (Stack) OR (100000C); * set hi bit of ptrRefHi as flag
arm2x: Stack&-2; * point to refNewHi
doAssign: membase← LPtr, oofNum← T- T - 1;
store← 1s, dbuf← Stack&-1;
store← 0s, dbuf← (Stack&+1); * do assignment
onStack← onStackBit; * StkP points to refNewHi
b← Md, call[MapRefPiRes]; * make sure assignment completed
rcv← AddRefCt, call[HTFind]; * returns pointing to refNewLo
b← Md, Stack&-1, IFUNext0;
*-----------------------------------------------------------
IFUR[ICLB, 2, LPtr]; * Initialize counted long byte
** ASSIGNREFNEW[refNew, ptrRef] => RETURNS nothing
* (<[stack[top],,stack[top-1]> + alpha)↑ ← <stack[top-2],,stack[top-3]>
** implements AlterCount[refNew, AddRef], and ptrRef↑ ← refNew
*-----------------------------------------------------------
T← ID, Stack&-1, Branch[arnm1];
:IfMEP;
T← ID, Stack&-1← MD, Branch[arnm1];
T← ID, Branch[arnm1];
:EndIf;
arnm1: call[LPtrfromStackT]; * load LPtr from Stack + T
knowrbase[rcv];
branch[.+2, R<0], gcStateMask; * skip if gcStopped
Stack&+1, branch[doAssign]; * StkP was left at refNewLo
pd← gcProcNum;
branch[.+2, alu#0]; * check if TandS running
Stack&+1, branch[doAssign]; * StkP was left at refNewLo
rbase← rbase[TrapParam], branch[.+2];
armx: rbase← rbase[TrapParam]; * gcStopped, TandS running
TrapParam← 2C;
branch[OpCodeTrap];
*-----------------------------------------------------------
* LPtrfromStackT
*-----------------------------------------------------------
subroutine; * T has offset to be added to ptrRefLo
LPtrfromStackT:
T← T + (Stack&+1), rbase← rbase[rcv];
BrLo← T, T← Stack&-3, branch[.+2, carry'];
T← T + 1; * carry into hi part of address
BrHi← T;
fetch← 0s;
fetch← 1s, T← Md;
store← 0s, probe← dbuf← T;
store← 1s, dbuf← Md, return; * leave value in Md,,T(probe)
top level;
*-----------------------------------------------------------
* MapRefPiRes
* StkP points to refHi, sets probe and residue, masks onStack with gcReclaimState
*-----------------------------------------------------------
subroutine;
MapRefPiRes:
branch[.+3, R>=0], T← gcStateMask;
Stkp-1; * to match later Stack&-1
return, probe← 100000C; * gc is turned off if gcStateMask<0
onStack← (onStack) AND T;
T← (Stack&-1) and (77C); * refHi masked to 6 bits
pd← (Stack) OR (Q← T);
branch[.+2, alu#0], T← (Stack) rsh 1; * branch if ref#NIL
return, probe← 100000C; * ref was NIL
** Q has hi 6 bits of ref (residue -- assumes 22-bit addresses)
** probe← ((refLo rsh 1) XOR residue) *which is 15 bits
probe← T XOR Q;
residue← Q, return, membase← gcMapPiRce;
*-----------------------------------------------------------
* HTFind
* rcv, onStack, oofNum are set
*-----------------------------------------------------------
** an entry in the main table is laid out as:
** eType[0..0], refCt[1..7], onStack[8..8], residue[9..15]
** if eType = 0, then this is a normal entry
** if eType = 1, then entry is an index into the overflow table
HTFind: branch[.+2, R>=0], probe;
** if probe<0 (100000C) means gcStopped or ref=NIL => don't do anything
return;
fetch← probe;
T← (rcv) + (rcv);
rTemp0← T;
** check for overflow entry FIRST
T← entry← Md;
htfind1: branch[notEmpty, R>=0], T← ResidueField[entry];
branch[overflow, R even], entry; * empty entry is odd & overflow
pd← oofNum;
branch[.+2, alu<0], T← (residue) + (rcAbsentShifted);
T← T OR (onStack); * don't set onStack if AddRef & new entry
rcv← T + (rcv);
T← (rcv) AND (nrceMask);
store← probe, dbuf← (Q← T); * T is used by CREATEREF
T← HTCCrLo;
** keep track of HTCell increments & decrements
** Q has entry to return, T points to counter to increment
HTCellAcct:
membase← gcStateBR;
fetch← T;
gctemp← (Md) + 1;
T← (store← T) + 1, dbuf← gctemp, branch[htc1, Carry'];
fetch← T;
gctemp← (Md) + 1;
store← T, dbuf← gctemp;
htc1: T← Q;
** check if rcFinalizeCount increased
rcCheck: rcv← RefCtField[T];
pd← (rcv) XOR (rcFinalize);
branch[.+2, alu#0], Q← T; * most code doesn't go thru HTCellAcct
rcFnzCount← (rcFnzCount) + 1; * new=rcFinalize
** keep track of RefCt increments, decrements or no changes
RefCtAcct: Q← T; * some code doesn't go thru rcCheck
rbase← rbase[rTemp0];
branch[doDec, R<0], pd← rTemp0, membase← gcStateBR;
branch[doZero, alu=0], T← ACIncLo;
rfct0: fetch← T;
rTemp1← (Md) + 1;
T← (store← T) + 1, dbuf← rTemp1, branch[rfct1, Carry'];
fetch← T;
rTemp1← (Md) + 1;
store← T, dbuf← rTemp1;
rfct1: rbase← rbase[rcv], T← Q, return;
doDec:
branch[rfct0], T← ACDecLo;
doZero:
branch[rfct0], T← ACZeroLo;
knowrbase[rcv];
HTCellDec: T← reclaimedRefDelta; * from ReclaimedRef
rTemp0← T;
T← HTCDelLo, branch[HTCellAcct];
RefCtDec: T← reclaimedRefDelta; * from ReclaimedRef
rTemp0← T, branch[htc1];
*-----------------------------------------------------------
knowrbase[rcv];
** T← ResidueField[entry];
notEmpty:
pd← T XOR (residue);
branch[noMatch, alu#0], T← RefCtField[entry];
** case rce.res = residue
pd← T XOR (rcFinalize);
branch[.+3, alu#0], pd← T XOR (lastRefCt);
rcFnzCount← (rcFnzCount) - 1; * old=rcFinalize
pd← oofNum, branch[.+3];
branch[.+2, alu#0], pd← oofNum;
Q← entry, branch[RefCtAcct]; * don't need to check FnzCount
branch[ne1, alu>=0], T← (rcv) + Md; * entry still in Md
** AddRef case, turn off stackBit if refCt>rcFinalize (refCt>=rcAbsent)
residue← RefCtField[T];
pd← (residue) - (rcAbsent);
branch[ne2, alu<0], T← T OR (onStack);
T ← T AND (undoStackBit), branch[ne2];
ne1: T← T OR (onStack);
ne2: gcTemp← RefCtStkField[T];
pd← (gcTemp) XOR (becameEmpty);
branch[.+2, alu=0], T← T AND (nrceMask);
store← probe, dbuf← (Q← T), branch[rcCheck]; * found a match
store← probe, T← dbuf← rceEmpty;
Q← T;
T← HTCDelLo, branch[HTCellAcct]; * don't need to check FnzCount
*-----------------------------------------------------------
** probe already contained an entry, so must make an overflow
*** entry with two entries on it
noMatch:
membase← gcStateBR;
T← (residue) + (rcAbsentShifted);
gLink← Link;
TOP LEVEL;
call[createOi], rcv← T + (rcv);
** returns with T having addr of even word in overflow table
** rcv is the new entry, entry is the one found in MapPirce
pd← oofNum;
branch[.+2, alu<0], Q← onStack;
rcv← (rcv) OR Q; * don't set onStack if AddRefC
rcv← (rcv) AND (nrceMask);
T← (store← T) + 1, dbuf← rcv; * new entry
T← (store← T) - 1, dbuf← entry; * entry from MapPiRce
membase← gcMapPiRce;
store← probe, dbuf← T; ** update MapPiRce
link← gLink;
SUBROUTINE;
T← rcv, branch[rcCheck]; ** no match found
*-----------------------------------------------------------
* need to look at an overflow chain
overflow:
membase← gcStateBR, oiPrev0← T - T;
oiPrev1← T - T;
gLink← Link;
rme[oiCurrent, entry];
ofLoop:
oiCurrent← (fetch← oiCurrent) + 1;
gcTemp← Md;
branch[.+2, R>=0], T← ResidueField[gcTemp];
branch[cats], T← A0; * malformed overflow chain
pd← T XOR (residue);
ofL0: branch[.+2, alu=0], T← RefCtField[gcTemp];
branch[ofNoMatch];
* p0e.rce.res = residue
pd← T XOR (rcFinalize);
branch[.+3, alu#0], pd← T XOR (lastRefCt);
rcFnzCount← (rcFnzCount) - 1; * old=rcFinalize
T← (rcv) + Md, branch[.+3];
branch[.+2, alu#0], T← (rcv) + Md;
T← gcTemp, branch[RefCtAcct]; * found match, but didn't change it
T← T OR (onStack);
gcTemp← T← T AND (nrceMask);
pd← oofNum;
branch[ofLoop1, alu>=0], T← RefCtField[gcTemp]; * refCt
pd← T - (rcAbsent);
branch[of1, alu<0], T← RefCtStkField[gcTemp];
gcTemp← T← (gcTemp) AND (undoStackBit); *AddRef case, refCt>=rcAbsent
ofLoop1: T← RefCtStkField[gcTemp];
of1: pd← T XOR (becameEmpty);
branch[of2, alu=0], T← (oiCurrent) - 1;
* found match, entry did not become vacant
Link← glink;
SUBROUTINE;
store← T, T← dbuf← gcTemp, branch[rcCheck];
* entry just became empty - take it off the list
** NOTE: entry has not been stored into, but that's OK
TOP LEVEL;
of2: T← (fetch← oiCurrent) - 1;
call[FreeOi], gcTemp2← Md; *oiCurrent.oe1
branch[.+2, R<0], T← oiPrev1;
membase← gcMapPiRce, T← probe; * oiPrev = 0
Link← glink;
SUBROUTINE;
store← T, dbuf← gcTemp2;
T← rceEmpty, branch[RefCtAcct]; * don't check FnzCount
TOP LEVEL;
* current entry doesn't match, see if second entry is end of chain
ofNoMatch:
fetch← oiCurrent;
gcTemp2← Md;
branch[ofMidChain, R<0], T← ResidueField[gcTemp2];
pd← T XOR (residue);
branch[endofChain, alu#0], T← RefCtField[gcTemp2];
pd← T XOR (rcFinalize);
branch[.+3, alu#0], pd← T XOR (lastRefCt);
rcFnzCount← (rcFnzCount) - 1; * old=rcFinalize
T← rcv, branch[matchAtEnd];
branch[matchAtEnd, alu#0], T← rcv;
Link← gLink;
SUBROUTINE;
T← gcTemp2, branch[RefCtAcct];
TOP LEVEL;
ofMidChain: oiPrev0← oiPrev1;
oiPrev1← oiCurrent;
oiCurrent← Md, branch[ofLoop];
matchAtEnd: T← (gcTemp2) + T;
T← T AND (nrceMask);
gcTemp2← T OR (onStack);
pd← oofNum;
branch[mae0, alu>=0], T← RefCtStkField[gcTemp2];
T← RefCtField[gcTemp2];
pd← T - (rcFinalize1);
branch[.+2, alu>=0];
gctemp2← (gctemp2) AND (undoStackBit);
T← RefCtStkField[gcTemp2];
mae0: pd← T XOR (becameEmpty);
branch[endBecameEmpty, alu=0], T← oiCurrent;
Link← glink;
SUBROUTINE;
store← T, T← dbuf← gcTemp2, branch[rcCheck];
TOP LEVEL;
endBecameEmpty:
T← (oiCurrent) - 1;
fetch← T;
call[FreeOi], gcTemp2← Md; * OiCurrent.rce
branch[.+2, R<0], T← oiPrev1;
membase← gcmapPiRce, T← probe;
mae1: Link← glink;
SUBROUTINE;
store← T, dbuf← gcTemp2;
T← rceEmpty, branch[RefCtAcct]; * don't check FnzCount
TOP LEVEL;
** end of overflow chain without a match
* create a new overflow entry and put it at the head of the chain
TOP LEVEL;
endofChain:
T← (residue) + (rcAbsentShifted);
branch[.+2, R<0], oofNum;
T← T OR (onStack); * don't set onStack if AddRef
call[createOi], rcv← (rcv) + T;
rcv← (rcv) AND (nrceMask);
membase← gcMapPiRce;
fetch← probe;
store← probe, dbuf← T, flipmembase;
T← T + 1, Link← glink;
SUBROUTINE;
T← (store← T) - 1, dbuf← Md; * store link first
store← T, T← dbuf← rcv, branch[rcCheck];
*-----------------------------------------------------------
* createOi returns the overflow index in T
** expects membase← GCState, rbase← rbase[rcv]
*-----------------------------------------------------------
* theshhold = (IF (GCState.reclaimState = gcRunning) AND
* (Process.GetCurrent[] = GCState.collector) THEN don't check ELSE 0);
subroutine;
createOi:
pd← (gcStateMask) AND (gcRunningC), global;
branch[co1, alu=0], T← (nOiFree) - 1;
rbase← rbase[RTemp0], T← gcProcNum;
pd← (CurrentPSB) xor T, rbase← rbase[gcTemp2];
branch[co1x, alu#0], T← (nOiFree) - 1;
nOiFree← T, branch[co2x]; * collector needs an overflow entry
co1: dblbranch[outofOverflowTab, co2, alu<0];
co1x: branch[outofOverflowTab, alu<0];
** for debugging running out of overflow table
* pd← (oofNum) xor (3C);
* branch[.+2, alu#0]; * DeleteRef case of ASSIGNREF only
* branch[outofOverflowTab];
* nop;
** for debugging running out of overflow table
co2: nOiFree← T; * update nOiFree
co2x: T← fetch← oiFreeList, branch[coError, R>=0], oiFreeList;
oiFreeList← Md, Q← T;
T← OTCCrLo;
CellAcct:
fetch← T; * membase is gcStateBR
rbase← rbase[rTemp1];
rTemp1← (Md) + 1;
T← (store← T) + 1, dbuf← rTemp1, branch[otc1, alu#0];
Fetch← T;
rTemp1← (Md) + 1;
store← T, dbuf← rTemp1;
otc1: T← Q, rbase← rbase[rcv], return;
RstkCellAcct: T← HTCDelLo, branch[CellAcct];
top level;
coError: branch[cats], T← 1C; * OiError, next is not in overflowtable
*-----------------------------------------------------------
* FreeOi - put the entry pointed to by T back on the
* freelist of Oi's (linked thru even words) - T is even
*-----------------------------------------------------------
subroutine;
FreeOi:
store← T, dbuf← oiFreeList;
oiFreeList← T;
nOiFree← (nOiFree) + 1; * update count of free entries
T← OTCDelLo, branch[CellAcct];
*-----------------------------------------------------------
top level;
* HTFind leaves StkP pointing to second (hi) word of ref
** SD[171C] => RTStartImpl.ClobberedOverflowTable[] if oofNum = 4 or OiError
outofOverflowTab:
T← (oofNum) + 1, rbase← rbase[RTemp0];
BDispatch← T;
branch[oof0], TrapParam← 1C;
DispTable[4]; **********************
oof0: b← Md, branch[OpCodeTrap]; * ASSIGNREFNEW, Addref part of ASSIGNREF
b← Md, branch[MiscOpCodeTrap]; * ALTERCOUNT
branch[MiscOpCodeTrap]; *CREATEREF
b← Md, branch[OpCodeTrap]; * DeleteRef part of ASSIGNREF
top level;
cats: Q← T;
call[rrx];
rbase← rbase[RTemp0], b← Md;
T← SDCatastrophe;
TrapParam← Q, branch[SavePCAndTrap];
*-----------------------------------------------------------
RcFinalizeCount: rbase← rbase[rcv], MiscTable[64];
T← rcFnzCount;
Stack← T, IFUNext0;
*-----------------------------------------------------------
*Misc70: branch[MiscOpCodeTrap], MiscTable[70];
*-----------------------------------------------------------
ReadRegs: call[rrx], MiscTable[66];
Stack← T - T - 1, IFUNext0;
SUBROUTINE;
rrx: rbase← rbase[rcv];
membase← gcStateBr;
T← dumpTableOffset; ** dumpTable part of GCstate
T← (store← T) + 1, dbuf← rcv;
T← (store← T) + 1, dbuf← residue;
T← (store← T) + 1, dbuf← probe;
T← (store← T) + 1, dbuf← entry;
T← (store← T) + 1, dbuf← onStack;
T← (store← T) + 1, dbuf← oiPrev0;
T← (store← T) + 1, dbuf← oiPrev1;
T← (store← T) + 1, dbuf← gcTemp;
T← (store← T) + 1, dbuf← gcTemp2;
T← (store← T) + 1, dbuf← oofNum;
T← (store← T) + 1, dbuf← oiFreeList;
T← (store← T) + 1, dbuf← nOiFree;
T← (store← T) + 1, dbuf← gcStateMask;
T← (store← T) + 1, dbuf← gcProcNum;
T← (store← T) + 1, dbuf← rcFnzCount, return;
*-----------------------------------------------------------
top level;
*-----------------------------------------------------------
** debugging
*-----------------------------------------------------------
*DUMPINDEX[probe] RETURNS [count]
*-----------------------------------------------------------
* arrive with rbase[rTemp0], T has probe
knowrbase[rTemp0];
DUMPINDEX: MiscTable[70], * Dump a probe index
membase← gcMapPiRce;
fetch← T, Stack&-1; * reset to top of Stack
rTemp0← dumpTableOffset; * count
T← rTemp1← Md;
branch[storeLast, R>=0], rTemp1, membase← GCStateBR;
branch[diLoop, R EVEN], rTemp1; * branch if overflow entry
Stack← A0, IFUNext0; * no entries
*---------------------------- normal entry
storeLast:
rTemp0← (store← rTemp0) + 1, dbuf← T;
sL1: T← (rTemp0) - (dumpTableOffset);
Stack← T, IFUNext0; * one entry
*---------------------------- must look at an overflow chain of entries
diLoop: T← (fetch← T) + 1; * fetch first part of overflow entry
dL1: T← Md, fetch← T;
rTemp0← (store← rTemp0) + 1, dbuf← T;
T← pd← Md;
branch[.+2, alu>=0]; * end of chain
T← (fetch← T) + 1, branch[dL1];
rTemp0← (store← rTemp0) + 1, dbuf← T, branch[sL1];