-- RTRefCounts.Mesa
-- last edited 13-Oct-81 16:32:05 by Willie-Sue
-- last edited May 19, 1982 8:01 pm by Paul Rovner

DIRECTORY
  Environment USING[wordsPerPage],
  Inline USING[LongNumber, BITXOR, BITSHIFT],
  MiscAlpha USING[alpha],
  Mopcodes USING[zMISC],
  RTQuanta USING[LASTAddress],
  RTTypesBasic USING[maxNPackageRefs],
  RTTypesBasicPrivate USING[RMapTiTd],
  RTZones USING[RMapQZf, RMapSziSz, PMapZiZn, ZoneIndex],
  SafeStorage USING[ReclamationReason];

RTRefCounts: DEFINITIONS
  IMPORTS Inline
= BEGIN

-- P A R A M E T E R S   and   T Y P E S

-- Reference count table parameters and TYPEs

  AMapPiRce: TYPE = ARRAY ProbeIndex OF RCEntry; -- the TYPE of the reference count table

  ProbeSize: CARDINAL = 100000B;  -- NOTE ucode & the 3 MapPi fns depend on this!!
  ProbeIndex: TYPE = [0..ProbeSize);  -- "pi"

  RCEntry: TYPE = MACHINE DEPENDENT RECORD		  -- "rce"  (setup for microcode)
   [ rcentry(0:0..15):
      SELECT eType(0:0..0): entryType FROM
        normal =>   [ rc(0:1..7): RefCt,		  -- eType = 0
		      onStack(0:8..8): uBoolean _ false,
		      res(0:9..15): Residue],
        overflow => [ oi(0:1..14): MapOiOeIndex,	  -- eType = 1
      		      fill(0:15..15): [0..1] _ 0],
       ENDCASE];

  nRCEntry: TYPE = normal RCEntry;
  oRCEntry: TYPE = overflow RCEntry;

  entryType: TYPE = MACHINE DEPENDENT { normal(0), overflow(1) };
  RefCt: TYPE = [0..(LAST[CARDINAL]/4)/ResidueSize]; 
                -- "rc" (7 bits) so normal RCEntry fits in one word
  rcFinalize: CARDINAL = RTTypesBasic.maxNPackageRefs+1;
  rcAbsent: CARDINAL = rcFinalize + 1;
  absentRCEntry: nRCEntry = [normal [rc: rcAbsent, onStack: false, res: 0]];	-- res a don't care
  nrcEntry: nRCEntry = [normal [rc: LAST[RefCt], onStack: true, res: LAST[Residue]]];
  nrceMask: CARDINAL = LOOPHOLE[nrcEntry];
  rceEmpty: oRCEntry = LOOPHOLE[177777B, oRCEntry];
       --  empty is overflow entry that is odd; making it all ones simplifies the microcode  


  uBoolean: TYPE = MACHINE DEPENDENT { false(0), true(1) };
                -- "don't depend on Mesa's representation of TRUE/FALSE
  Residue: TYPE = [0..ResidueSize);  -- "res", 7 bits
  ResidueSize: CARDINAL =
                LOOPHOLE[(RTQuanta.LASTAddress+1)/ProbeSize, Inline.LongNumber].lowbits;
                          -- nonsense, should be NARROW[(LASTAddress+1)/ProbeSize]

-- Reference count overflow table parameters and TYPEs

  AMapOiOe: TYPE = ARRAY MapOiOeIndex OF OverflowEntry; -- the TYPE of the overflow table

  MapOiOeIndex: TYPE = [0..mapOiOeLimit + mapOiOeStart);
       -- depends on the layout of AGCState. Indexing cleverness simplifies the microcode.

  OverflowEntry: TYPE = MACHINE DEPENDENT RECORD          -- "oe"
   [ rce(0:0..15): nRCEntry, oe1(1:0..15): RCEntry];

  OverflowFreeListEntry: TYPE = MACHINE DEPENDENT RECORD
   [ link(0:0..15): oRCEntry, oe1(1:0..15): RCEntry];

       --  Entries at the end of overflow chains contain two normal entries:
       --  EndOfChainOE: TYPE = MACHINE DEPENDENT RECORD [ rce: nRCEntry, oe1: nRCEntry]

       --  Entries in the middle of overflow chains contain a normal and an overflow entry
       --  MiddleOfChainOE: TYPE = MACHINE DEPENDENT RECORD [ rce: nRCEntry, oe1: oRCEntry]

       --  NOTE the microcode uses all 16 bits of an overflow RCEntry as an index into MapOiOe,
       --       which is really based at GCState. The mesa code uses only the middle 14 bits,
       --       adds in an offset (see MapOiOeIndex) and multiplies by SIZE[OverflowEntry],
       --       which is known to be 2.
       --  The software's value of MapOiOe will be greater than the ucode's
       --  by ProbeSize/SIZE[OverflowEntry]


  mapOiOePages: INTEGER = 80;
  OverflowEntrySize: CARDINAL = 2;  -- needed to avoid circular defs

  mapOiOeStart: CARDINAL = AGCStateSize/OverflowEntrySize;
  mapOiOeLimit: CARDINAL = mapOiOePages*Environment.wordsPerPage/OverflowEntrySize;

       --  The freelist in the overflow table is threaded through the even words.
       --  The contents of the odd words are ignored: [ rce: oRCEntry, oe1: don't care]

	
-- Access (for the microcode) to runtime tables: parameters and TYPEs
  AGCStateSize: CARDINAL = Environment.wordsPerPage;
       -- using a full page simplifies the microcode

  AGCState: TYPE = MACHINE DEPENDENT RECORD
   [
    GCStateBasic: aGCStateBasic,
    toBeUsedLater: toBeUsedSpace,
    GCEventCounters: aGCEventCounters,
    rceToReclaim: RCEToReclaimVec,  -- communication from the microcode to the collector
    dumpTable: gcDumpTable
--    MapPiRce: AMapPiRce	 an array 32K long
--    MapOiOe: AMapOiOe		 an array 20K long
   ];

  aGCStateBasic: TYPE = MACHINE DEPENDENT RECORD
   [
      -- these two goodies plus rcFnzCount are kept in microcode
      -- registers, and moved to memory via
      --    RTMOVESTATUS[toMemory, 0],
      -- from memory via
      --    RTMOVESTATUS[toUCodeRegisters, Inline.HighHalf[GCState]
    mapOiOeFrList(0:0..15): oRCEntry,  -- the overflow FreeList chain
    nOiFree(1:0..15): INTEGER,         -- (length of FreeList chain) - gcThresholdNOiFree 

      -- these two goodies are kept in microcode registers, and
      -- are ALWAYS moved there by RTMOVESTATUS
      -- (e.g. RTMOVESTATUS[toMemory, 0] does it). Groan.
    reclaimState(2:0..15): gcRState _ gcReady,
    collector(3:0..15): PROCESS _ NIL,

    mapQZf(4:0..31): LONG POINTER TO RTZones.RMapQZf _ NIL,
    mapSziSz(6:0..31): LONG POINTER TO RTZones.RMapSziSz _ NIL,
    mapZiZn(10B:0..31): LONG POINTER TO RTZones.PMapZiZn _ NIL,
    mapTiTd(12B:0..31): LONG POINTER TO RTTypesBasicPrivate.RMapTiTd _ NIL,
    rcFnzCount(14B:0..15): CARDINAL_ 0,
    tba1(15B:0..15): CARDINAL_ 0,
    tba2(16B:0..15): CARDINAL_ 0,
    tba3(17B:0..15): CARDINAL_ 0
  ];

  gcThresholdNOiFree: CARDINAL = mapOiOeLimit/4;
        -- enuff extra (hopefully!!) for expansion during collection

  gcRState: TYPE = MACHINE DEPENDENT RECORD  -- software status, encoded to simplify ucode
   [ fill0(0:0..0): [0..1]_ 0,
     rcMask(0:1..7): RefCt _ LAST[RefCt],
     useStack(0:8..8): uBoolean,
     fill(0:9..15): [0..177B] _ 0
   ];
  gcReady: gcRState = [ useStack: false];                  -- 77400B
  gcRunning: gcRState = [ useStack: true];                -- 77600B
  gcStopped: gcRState = [ fill0: 1, useStack: false];     -- 1xxxxx

  toBeUsedSize: CARDINAL = 2*rceReclaimLimit-SIZE[aGCStateBasic]-SIZE[aGCEventCounters];
  toBeUsedSpace: TYPE = ARRAY[0..toBeUsedSize) OF CARDINAL;
  
  aGCEventCounters: TYPE = MACHINE DEPENDENT RECORD
   [
    AlterCountNIL: LONG INTEGER,		-- AlterCount with NIL or odd arg
    AlterCountZeroChange: LONG INTEGER,		-- AlterCount w/o changing RefCt
    AlterCountDecrement: LONG INTEGER,		-- AlterCount decrementing RefCt
    AlterCountIncrement: LONG INTEGER,		-- AlterCount incrementing RefCt
    OTCellDelete: LONG INTEGER,			-- OT cell deletions
    OTCellCreate: LONG INTEGER,			-- OT cell creations
    HTCellDelete: LONG INTEGER,			-- HT cell deletions
    HTCellCreate: LONG INTEGER,			-- HT cell creations
    ReclaimedRefNIL: LONG INTEGER,		-- ReclaimedRef with NIL result
    ReclaimedRefNoDel: LONG INTEGER,		-- ReclaimedRef completions (not deleted)
    ReclaimedRefDel: LONG INTEGER,		-- ReclaimedRef completions (already deleted)
    ResetOnStackC: LONG INTEGER,		-- ResetOnStack completions
    ReclaimAllC: LONG INTEGER,			-- ReclaimAll completions
    CreateRefC: LONG INTEGER,			-- CreateRef completions
    AssignRefC: LONG INTEGER,			-- AssignRef+AssignRefNew completions
    AssignRefNewI:  LONG INTEGER,		-- AssignRefNew inititations
      -- (= AssignRefNew completions with page fault restarts as an error term)
    RefOldEQNIL: LONG INTEGER,			-- RefOld=NIL in AssignRef
      -- (plus page fault restarts & collector disabled AssignRefs as an error term)
    RefNewEQNil: LONG INTEGER,			-- RefNew=NIL in AssignRef(New)
    RefOldEQRefNew: LONG INTEGER		-- RefOld=RefNew in AssignRef
   ];
   
  RCEToReclaimVec: TYPE = ARRAY[0..rceReclaimLimit) OF nRCEntry;
       --  RCEToReclaimVec is big enough to hold the longest possible chain of overflow entries,
       --  which is 64 entries (REFs are even)
  rceReclaimLimit: CARDINAL = (LAST[Residue] + 1)/2;


  gcDumpTable: TYPE = ARRAY[0..rceReclaimLimit) OF CARDINAL;	-- for microcode debugging

-- Miscellany
  uCodeDirection: TYPE = MACHINE DEPENDENT  -- used by RTMOVESTATUSTrap and InitializeCleanup
  		{ toMemory(0),  -- this is badly named, but means "move info about overflow free list to memory, and move other status info from memory to microcode.
		  toUCodeRegisters(177777B)};


-- Parameter bundle for the microcode (AlterCount), for use with bit tweezers
  rcoState: TYPE = MACHINE DEPENDENT RECORD
   [ fill0(0:0..0): [0..1]_ 0,
     rcChange(0:1..7): [0..177B],
     onStack(0:8..8): uBoolean,
     fill(0:9..15): [0..177B]_ 0
   ];

  rcoAddRef: rcoState = [ rcChange: 1, onStack: true];		--   600B
  rcoDeleteRef: rcoState = [ rcChange: 177B, onStack: true];	-- 77600B
  rcoJustCreated: rcoState = [ rcChange: 177B, onStack: true];	-- 77600B
  rcoFinalizedRef: rcoState = [ rcChange: 1, onStack: false];	--   400B
  rcoNilifyRef: rcoState = [ rcChange: 177B, onStack: false];	-- 77400B
  rcoFoundOnStack: rcoState = [ rcChange: 0, onStack: true];	--   200B

  rcoChangeMask: rcoState = [rcChange: 177B, onStack: false];
  rcoOnstackMask: rcoState = [rcChange: 0,  onStack: true];
  rcoReclaimedRef: rcoState = [rcChange: 177B, onStack: false];
  reclaimedRefDelta: CARDINAL = LOOPHOLE[rcoReclaimedRef];    


-- V A R I A B L E S
  GCMicrocodeExists:  BOOLEAN;
  useUCodedGC:  BOOLEAN;
  nObjectsReclaimed:  LONG CARDINAL;
  nWordsReclaimed:  LONG CARDINAL;
  GCState:  LONG POINTER TO AGCState;
  frameBodyBufferPages: CARDINAL;


-- P R O C E D U R E S

  StuffZi: PROC[zi: RTZones.ZoneIndex, zone: ZONE];
  StuffMapZiZn: PROC[p: LONG POINTER TO RTZones.PMapZiZn];
  StuffMapSziSz: PROC[p: LONG POINTER TO RTZones.RMapSziSz];
  StuffMapQZf: PROC[p: LONG POINTER TO RTZones.RMapQZf];

  IsTraceAndSweepEnabled: PROC RETURNS[BOOLEAN];
  DoTraceAndSweepCollection: PROC;
  ReclaimForQuanta: PROC RETURNS[LONG CARDINAL];  -- returns number of objects reclaimed
  MapReclaimableObjects: PROC;

  InternalReclaim: PROC[reason: SafeStorage.ReclamationReason, suspendMe: BOOLEAN _ FALSE, doStack: BOOLEAN _ TRUE];


  aCREATEREF: MiscAlpha.alpha = 67B;
  CREATEREF: PROC[npr: rcoState, ref: REF] =
    MACHINE CODE {Mopcodes.zMISC, aCREATEREF };

  CreateRef: PROC[npr: CARDINAL, refNew: REF] =  -- called by the allocator
    INLINE
      {IF useUCodedGC
        THEN {rco: rcoState _ [rcChange: npr, onStack: false]; [] _ CREATEREF[rco, refNew]}
        ELSE SoftwareCreateRef[npr, refNew]};
    
  SoftwareCreateRef: PROC[npr: CARDINAL, refNew: REF];

  ClearRCTable: PROC;  -- called by the TraceAndSweep collector
  IncrementReferenceCount: PUBLIC PROC[ref: REF];  -- called by the TraceAndSweep collector
  DecrementReferenceCount: PUBLIC PROC[ref: REF];  -- called by the TraceAndSweep collector

--  used when the microcode traps or there is no microcode support
  RTMOVESTATUSTrap: PROC[direction: uCodeDirection, gcStateBank: CARDINAL]
        RETURNS[CARDINAL];
  AssignRefTrap: PROC[refNew: REF, ptrRef: LONG POINTER TO REF];
  AssignRefNewTrap: PROC[refNew: REF, ptrRef: LONG POINTER TO REF];
  CREATEOutOfOverflowTable: PROC[npr: rcoState, refNew: REF ANY];
  ReclaimedRefOutOfOverflowTable: PROC;
  ALTERCOUNTOutOfOverflowTable: PROC;
  ClobberedOverflowTable: PROC;
  ReadUCodeRegsTrap: PROC RETURNS[f: CARDINAL];
  
  DisableRC: PROC;
  AlterCountEntry:  PROC[rcv: rcoState, ref: REF];
  ReclaimedRef: PROC[ref: REF] RETURNS[REF]; 
  IsPiReclaimable: PROC[pi: ProbeIndex] RETURNS [fpi: ProbeIndex, npi: CARDINAL];
  MapRcePiRef: PROC[rce: nRCEntry, pi: ProbeIndex] RETURNS[REF] = INLINE
    { OPEN Inline;
      res: Residue = rce.res;
      RETURN[LOOPHOLE[LongNumber[num[highbits: res,
      				 lowbits: BITSHIFT[BITXOR[pi, res], 1]]]]]};
  IsOiCushion: PROC RETURNS[BOOLEAN];

  GetMapPiRce: PROC RETURNS[LONG POINTER TO AMapPiRce];
  GetMapOiOe: PROC RETURNS[LONG POINTER TO AMapOiOe];
  InitializeCleanup: PROC[gcStateBank: CARDINAL];

  SetAlwaysTrim: PROC[sense: BOOLEAN];



-- statistics stuff for performance analysis (VOLATILE)

Count: TYPE = LONG CARDINAL;
AllocatorTrapStatsRec: TYPE = RECORD
    [ NoUCodeTraps: Count_ 0,
      OldUCodeTraps: Count_ 0,
      ZoneLockedTraps: Count_ 0,
      NoBlockFoundTraps: Count_ 0,
      LongFreeListTraps: Count_ 0,
      UnKnownTraps: Count_ 0
    ];

PrefixedAllocatorTrapStats, QuantizedAllocatorTrapStats: AllocatorTrapStatsRec;

END.