ReclaimerImpl.Mesa
Copyright © 1985, 1986 by Xerox Corporation. All rights reserved.
Richard Koo, July 2, 1984 4:53:39 pm PDT
Russ Atkinson (RRA) April 15, 1986 3:34:16 pm PST
DIRECTORY
Allocator USING [NHeaderP],
AllocatorOps USING [FreeObject, NHPToREF, PlausibleRef, 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;
PtrToRef: TYPE = LONG POINTER TO REF ANY;
RefIndex: TYPE = NAT;
This type is sufficient to index all references in an object when the object is treated as a PASeq. This should change when we get larger objects possible.
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 PASeq;
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.
PASeq: TYPE = RECORD [
SEQUENCE COMPUTED RefIndex OF Basics.LongNumber
];
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
head: Allocator.NHeaderP = AllocatorOps.REFToNHP[ref];
refType: Type ← head.type;
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 ← 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 {
IF checking AND NOT AllocatorOps.PlausibleRef[LOOPHOLE[r]] THEN ERROR;
r ← RCMicrocodeOps.ReclaimedRef[r];
SELECT TRUE FROM
r = NIL => {};
first = NIL => first ← r;
nextx = 0 => {
LOOPHOLE[ref, PAPtr][0] ← MarkBackPointer[LOOPHOLE[prev]];
LOOPHOLE[ref, PAPtr][1] ← LOOPHOLE[r, Basics.LongNumber];
nextx ← 2;
};
ENDCASE => {
LOOPHOLE[ref, PAPtr][nextx] ← LOOPHOLE[r, Basics.LongNumber];
nextx ← nextx + 1;
};
};
};
***Start this iteration of inner loop 1 Here***
{
rcmx: RCMap.Index;
IF refType = CODE[Rope.RopeRep] THEN
special (faster) case for ROPEs
WITH t: LOOPHOLE[ref, Rope.ROPE] SELECT FROM
text => GO TO none;
node => refType ←
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;
low index to high. DoFreeRef for ea. component ref
rcmx ← RTTypesBasicPrivate.MapTiTd[refType].rcmx;
WITH rcmr: rcmb[rcmx] SELECT FROM
null => {};
oneRef =>
DoFreeRef[(LOOPHOLE[ref, PtrToRef]+rcmr.offset)^];
simple =>
FOR i: CARDINAL IN [0..rcmr.length) DO
IF rcmr.refs[i] THEN DoFreeRef[(LOOPHOLE[ref, PtrToRef]+i)^];
ENDLOOP;
ref =>
DoFreeRef[LOOPHOLE[ref, PtrToRef]^];
ENDCASE =>
RTTypesBasicPrivate.DoFREEify[LOOPHOLE[ref, PtrToRef], rcmx, FreeRef];
EXITS none => {};
};
IF nextx = 0
THEN AllocatorOps.FreeObject[head]
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;
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;
SELECT TRUE FROM
prev = NIL => RETURN;
the given object and all objects referenced only from it (and recursively) have been reclaimed
IsBackPointer[p ← prev^] => {
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
};
ENDCASE => {
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;
ENDLOOP;
};
};
IsBackPointer: PROC [ptr: Basics.LongNumber] RETURNS[BOOL] = INLINE {
RETURN[Basics.BITAND[ptr.highbits, BackPointerMarkBit] # 0];
};
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];
};
END.