-- RTRefCounts.Mesa
-- last edited 13-Oct-81 16:32:05 by Willie-Sue
-- last edited May 17, 1983 12:43 pm by Paul Rovner
-- Last Edited by: Levin, August 8, 1983 4:55 pm

DIRECTORY
Basics USING[BITXOR, BITSHIFT, LongNumber],
PrincOps USING[wordsPerPage, zMISC, alpha],
RTQuanta USING[LASTAddress],
RTTypesBasicPrivate USING[RMapTiTd],
RTZones USING[RMapQZf, PMapZiZn, ZoneIndex],
SafeStorage USING[ReclamationReason, maxNPackageRefs];

RTRefCounts: DEFINITIONS
IMPORTS Basics
= 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 = SafeStorage.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 = (RTQuanta.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*PrincOps.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 = PrincOps.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[upDate, 0],
-- from memory via
-- RTMOVESTATUS[initialize, 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[upDate] 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 ← 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
MSOperation: TYPE = MACHINE DEPENDENT -- arg to RTMOVESTATUS
  { upDate(0), -- this means "move info about overflow free list to memory, and move other status info from memory to microcode.
   initialize(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: INT;
nWordsReclaimed: INT;
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];
StuffMapQZf: PROC[p: LONG POINTER TO RTZones.RMapQZf];

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

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

-- NOTE copied in RTMicrocode to break DEFS circularity
aCREATEREF: PrincOps.alpha = 67B;
CREATEREF: PROC[npr: rcoState, ref: REF] =
MACHINE CODE { PrincOps.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

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 Basics;
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];

END.