ZCT.mesa
Definitions for the Cedar incremental collector
Paul Rovner, December 6, 1983 11:14 am
Bob Hagmann, May 10, 1984 3:23:00 pm PDT
Russ Atkinson (RRA) February 1, 1985 12:48:17 pm PST
Beach, February 23, 1985 9:30:13 am PST
Doug Wyatt, February 24, 1985 9:17:02 pm PST
DIRECTORY
Allocator USING[NHeaderP, SizeToBSIObj, BSIToSizeObj, BSIToFreeListObj],
PrincOps USING[wordsPerPage];
ZCT: DEFINITIONS
= BEGIN OPEN Allocator;
Types
zct: ZeroCountTable;
ZeroCountTable: TYPE = LONG POINTER TO ZCTObject;
zctBlockPages: NAT = 8;
zctBlockWords: INT = zctBlockPages*wordsPerPage;
wordsPerPage: NAT = PrincOps.wordsPerPage;
logZCTBlockPages: NAT = 3;
ZCTObject: TYPE = MACHINE DEPENDENT RECORD[
wp(0): LONG POINTER TO NHeaderP,
rp(2): LONG POINTER TO NHeaderP,
lastNP(4): LONG POINTER TO LONG POINTER,
pad(6: 0..14): [0 .. LAST[CARDINAL]/2],
markingDecrements(6: 15..15): BOOL,
residueMask(7): CARDINAL,
unused1(8): ARRAY [0..wordsPerPage-8) OF WORD,
bsiToFreeList(wordsPerPage): BSIToFreeListObj,
unused2(wordsPerPage+SIZE[BSIToFreeListObj]):
ARRAY [0..wordsPerPage-SIZE[BSIToFreeListObj]) OF WORD,
bsiToSize(2*wordsPerPage): BSIToSizeObj,
unused3(2*wordsPerPage+SIZE[BSIToSizeObj]):
ARRAY [0..wordsPerPage-SIZE[BSIToSizeObj]) OF WORD,
sizeToBSI(3*wordsPerPage): SizeToBSIObj,
unused4(3*wordsPerPage+SIZE[SizeToBSIObj]):
ARRAY [0..2*wordsPerPage-SIZE[SizeToBSIObj]) OF WORD
fosTable(5*wordsPerPage): FOSTableObject starts on a page bdry; integral # pages
];
rp points to the next zct entry to be examined by the collector. It might point to a zctBlock link.
rp is used only by the collector process; there are no critical sections required for it.
The last cell in each zctBlock contains either NIL or a pointer to the next zctBlock.
lastNP points to the cell (containing NIL) into which to put a pointer to the next (empty) zctBlock. lastNP is used to accelerate zct extension.
wp points either to the next zct entry into which to store an nhp or to a zctBlock link.
wp is used by client processes and by the collector process; critical sections are required.
FOSTableObject: TYPE = ARRAY FOSTableIndex OF FOSTableResidue;
FOSTableIndex: TYPE = [0..FOSTableLength);
FOSTableResidue: TYPE = CARDINAL;
except for fosWildCard and fosEmpty, FOSTableResidues will be in [0..3777B] for a 24-bit address space and [0..77777B] for a 28-bit address space
fosWildCard: FOSTableResidue = 177777B;
fosEmpty: FOSTableResidue = 100000B;
FOSTableLength: CARDINAL = 10000B; -- integral # pages
Procedures
StartMarkingDecrements: PROC;
StopMarkingDecrements: PROC;
ScanTheFrameHeap: PROC;
MapReclaimableObjects: PROC[reclaim: PROC[NHeaderP]];
ResetStackBits: PROC;
DoEnableFinalization: PROC[npr: NAT, nhp: NHeaderP];
DisableFinalization: PROC[npr: NAT, nhp: NHeaderP];
HandleRCUnderflow: PROC[ref: REF];
InnerHandleRCUnderflow: PROC[ref: REF];
HandleRCOverflow: PROC[ref: REF];
InnerHandleRCOverflow: PROC[ref: REF];
DecrForOverflow: PROC[rcDelta: NAT, nhp: NHeaderP] RETURNS[success: BOOL];
IncrForUnderflow: PROC[rcDelta: NAT, nhp: NHeaderP] RETURNS[success: BOOL];
TryToQItForFinalization: PROC[nhp: NHeaderP] RETURNS[success: BOOL];
Enter: PROC;
EnterAndCallBack: PROC[proc: PROC];
EnterRCOvAndCallBack: PROC[proc: PROC];
RCOvReset: PROC;
ExpandZCT: PROC;
InitializeCleanup: PROC;
Commentary
FINALIZATION
When the collector finds an object (nhp^) with
nhp.refCount = 0
AND with nhp.maybeOnStack = FALSE
AND with nhp.finalized = FALSE
it sets nhp.finalized ← TRUE, increments nhp.refCount by PackageCount[type] and puts the object on the finalization queue for type (all atomically).
NOTES:
(*) nhp.finalized = FALSE implies that nhp^ is of a finalizable type
and that the real reference count of nhp^ = nhp.refCount + PackageCount[type]
To enable finalization for a newly created object, the (SAFE) procedure EnableFinalization[<REF ANY>] must be called by the client after the object has been initialized and REFS to it have been inserted in any "package" data structures.
EnableFinalization does the following (atomically):
{nhp.finalized ← FALSE; nhp.refCount ← nhp.refCount - PackageCount[type]}
Error[illegalFinalizationAction] is raised if nhp.refCount < PackageCount[type] (and no change is made to nhp^).
EnableFinalization can also be used by the client to re-enable finalization for an object after removing it from its finalization queue, then deciding NOT to finalize the object for some reason. This will cause the object to be considered again for finalization by a future collection (as above). This may be useful in rare and wondrous cases.
END.