-- 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.