ReclaimerImpl.Mesa
last edited On January 18, 1984 8:53:32 am PST by Paul Rovner
last edited On July 2, 1984 4:53:39 pm PDT by Richard Koo
DIRECTORY
Allocator USING[NHeaderP],
AllocatorOps USING[FreeObject, NHPToREF, PlausibleRef, ReferentType, REFToNHP],
Basics USING[LongNumber, BITAND, BITOR],
Collector USING[], -- EXPORTS only
RCMapOps USING[GetBase],
RCMap USING[Index, Base, nullIndex],
RCMicrocodeOps USING[ReclaimedRef],
Rope USING[RopeRep, ROPE],
RTTypesBasicPrivate USING[DoFREEify, MapTiTd],
SafeStorage USING[Type];
ReclaimerImpl:
PROGRAM
IMPORTS AllocatorOps, Basics, RCMapOps, RCMicrocodeOps, RTTypesBasicPrivate
EXPORTS Collector
SHARES Rope
=
BEGIN OPEN SafeStorage;
rcmb: RCMap.Base = RCMapOps.GetBase[].base;
checking: BOOL = FALSE;
Reclaim:
PUBLIC
PROC[nhp: Allocator.NHeaderP] = {
IF RTTypesBasicPrivate.MapTiTd[nhp.type].rcmx = RCMap.nullIndex
THEN AllocatorOps.FreeObject[nhp]
ELSE {
ref: REF ← AllocatorOps.NHPToREF[nhp];
PAPtr:
TYPE =
LONG
POINTER
TO
ARRAY
OF Basics.LongNumber;
The 0th element is a marked (as a "backpointer") pointer. Its pointer part is either NIL or a pointer to the last REF in a previous such array. Other elements are REFs to objects that become reclaimable as other objects are reclaimed. This code avoids both the use of recursion and the use of extra storage by the reclaimer.
prev: LONG POINTER TO Basics.LongNumber ← NIL;
DO
-- outer loop
UNTIL ref =
NIL
DO
inner loop 1: each iteration walks the component refs of the current ref^, applying ReclaimedRef to each and remembering which of the objects so referenced can also be reclaimed. inner loop 1 terminates
refType: Type ← LOOPHOLE[AllocatorOps.ReferentType[ref], Type]; -- NOTE XXX
nextx:
CARDINAL ← 0;
nextx # 0 =>
first # NIL
nextx = the index relative to LOOPHOLE[ref, PAPtr] of the next place to push a ref to an object discovered while reclaiming ref^ that can also be reclaimed
first:
REF
ANY ←
NIL;
the first object discovered while reclaiming ref^ that can also be reclaimed
FreeRef: PROC[r: REF] = {DoFreeRef[r]};
DoFreeRef:
PROC[r:
REF] =
INLINE {
IF r = NIL THEN RETURN;
IF checking
AND
NOT AllocatorOps.PlausibleRef[
LOOPHOLE[r,
LONG
CARDINAL]]
THEN ERROR;
r ← RCMicrocodeOps.ReclaimedRef[r];
IF r #
NIL
THEN {
-- r^ can also be reclaimed.
IF first = NIL THEN first ← r ELSE Push[r];
};
};
Push:
PROC[r:
REF] =
--INLINE-- {
IF nextx = 0
THEN {
LOOPHOLE[ref, PAPtr][0] ← MarkBackPointer[LOOPHOLE[prev]];
LOOPHOLE[ref, PAPtr][1] ← LOOPHOLE[r, Basics.LongNumber];
nextx ← 2;
}
ELSE {
LOOPHOLE[ref, PAPtr][nextx] ← LOOPHOLE[r, Basics.LongNumber];
nextx ← nextx + 1;
};
};
FREEify: PROC[ptr: LONG POINTER, rcmx: RCMap.Index] = INLINE {
low index to high. DoFreeRef for ea. component ref
WITH rcmr: rcmb[rcmx]
SELECT
FROM
null => NULL;
oneRef => DoFreeRef[LOOPHOLE[ptr+rcmr.offset, LONG POINTER TO REF ANY]^];
simple =>
FOR i:
CARDINAL
IN [0..rcmr.length)
DO
IF rcmr.refs[i]
THEN {DoFreeRef[LOOPHOLE[ptr+i, LONG POINTER TO REF ANY]^]};
ENDLOOP;
ref => DoFreeRef[LOOPHOLE[ptr, LONG POINTER TO REF ANY]^];
ENDCASE => RTTypesBasicPrivate.DoFREEify[ptr, rcmx, FreeRef];
};
***Start this iteration of inner loop 1 Here***
IF refType =
CODE[Rope.RopeRep]
-- special (faster) case for ROPEs
THEN
refType ←
WITH t:
LOOPHOLE[ref, Rope.
ROPE]
SELECT
FROM
text => CODE[Rope.RopeRep.text],
node =>
WITH v: t
SELECT
FROM
substr => CODE[Rope.RopeRep.node.substr],
concat => CODE[Rope.RopeRep.node.concat],
replace => CODE[Rope.RopeRep.node.replace],
object => CODE[Rope.RopeRep.node.object]
ENDCASE => ERROR
ENDCASE => ERROR;
FREEify[
LOOPHOLE[ref, LONG POINTER], RTTypesBasicPrivate.MapTiTd[refType].rcmx];
IF nextx = 0
THEN AllocatorOps.FreeObject[AllocatorOps.REFToNHP[ref]]
at most 1 object referenced from within ref^ that can also be reclaimed
(no extra objects to remember to reclaim later)
ELSE prev ←
LOOPHOLE[@
LOOPHOLE[ref, PAPtr][nextx - 1]];
more than 1 object referenced from within ref^ that can also be reclaimed
(must remember to reclaim it later; use ref^ for storage)
ref ← first;
NIL unless at least one object referenced from within ref^ can also be reclaimed
ENDLOOP; -- inner loop 1
DO
-- inner loop 2: pop the next pushed ref, reclaiming its container if it becomes empty. If there's no pushed ref to pop, terminate Reclaim.
p: Basics.LongNumber;
IF prev =
NIL
THEN
RETURN
the given object and all objects referenced only from it (and recursively) have been reclaimed
ELSE IF IsBackPointer[p ← prev^]
THEN {
-- it's a back pointer; the container addressed by prev is empty
AllocatorOps.FreeObject[AllocatorOps.REFToNHP[LOOPHOLE[prev, REF]]];
prev ←
LOOPHOLE[UnmarkBackPointer[p]];
prev now addresses the last slot in the next container to empty
}
ELSE {
ref ← LOOPHOLE[p, REF];
prev ← prev - SIZE[REF]; -- prev addresses the previous slot in this container
EXIT; -- go around again with the new ref
};
ENDLOOP; -- inner loop 2
ENDLOOP; -- outer loop
}; -- end ELSE
}; -- end Reclaim
BackPointerMarkBit:
CARDINAL = 100000B;
a power of 2, one of the extra bits in a long pointer
MarkBackPointer:
PROC[ptr: Basics.LongNumber]
RETURNS[Basics.LongNumber] =
INLINE {
ptr.highbits ← Basics.BITOR[ptr.highbits, BackPointerMarkBit];
RETURN[ptr];
};
UnmarkBackPointer:
PROC[ptr: Basics.LongNumber]
RETURNS[Basics.LongNumber] =
INLINE {
BackPointerUnmarkMask: CARDINAL = BackPointerMarkBit - 1;
ptr.highbits ← Basics.BITAND[ptr.highbits, BackPointerUnmarkMask];
RETURN[ptr];
};