*-----------------------------------------------------------
Title[DMesaRefCount.mc...September 6, 1983  11:08 AM..Taft];
*-----------------------------------------------------------
** PILOT ONLY version
** PATCHED to permit coexistence with the new Cedar 5.0 reference-counting microcode.
*-----------------------------------------------------------
   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];	* skip if T&S not running
    IFUNext0, Stack&-2;		* ref was NIL or gcStopped => FALSE
    T_ 2C, branch[OpcodeTrap];

*-----------------------------------------------------------
OldWCLB: * IFUR[WCLB, 2, LPtr];	* Write counted long byte
**** This is now reached conditionally from ASSIGNREF in the new RC microcode ****
** 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;

armx:  T_ 2C, branch[OpcodeTrap]; * gcStopped, TandS running
   
*-----------------------------------------------------------
* 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:
    branch[OpcodeTrap], T_ 1C;

    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:	T_ A0, branch[OpcodeTrap],	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];