*----------------------------------------------------------- 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)^ _ ** 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)^ _ ** 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];