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; prev: LONG POINTER TO Basics.LongNumber _ NIL; DO -- outer loop UNTIL ref = NIL DO refType: Type _ LOOPHOLE[AllocatorOps.ReferentType[ref], Type]; -- NOTE XXX nextx: CARDINAL _ 0; first: REF ANY _ NIL; 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 { 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]; }; 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]] ELSE prev _ LOOPHOLE[@LOOPHOLE[ref, PAPtr][nextx - 1]]; ref _ first; 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 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]]; } 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; IsBackPointer: PROC[ptr: Basics.LongNumber] RETURNS[BOOL] = INLINE { RETURN[Basics.BITAND[ptr.highbits, BackPointerMarkBit] # 0]; }; 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. 0ReclaimerImpl.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 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. 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 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 the first object discovered while reclaiming ref^ that can also be reclaimed low index to high. DoFreeRef for ea. component ref ***Start this iteration of inner loop 1 Here*** at most 1 object referenced from within ref^ that can also be reclaimed (no extra objects to remember to reclaim later) more than 1 object referenced from within ref^ that can also be reclaimed (must remember to reclaim it later; use ref^ for storage) NIL unless at least one object referenced from within ref^ can also be reclaimed the given object and all objects referenced only from it (and recursively) have been reclaimed prev now addresses the last slot in the next container to empty a power of 2, one of the extra bits in a long pointer Ê˘šœ™Jšœ=™=Jšœ9™9—J˜šÏk ˜ Jšœ œ ˜Jšœ œ=˜OJšœœ œœ˜(Jšœ œÏc˜#Jšœ œ ˜Jšœœ˜$Jšœœ˜#Jšœœ œ˜Jšœœ˜.Jšœ œ˜—J˜šœ˜Jšœ œ5˜KJšœ ˜Jšœ˜ —šœ œ ˜J˜Jšœ+˜+Jšœ œœ˜J˜šÏnœœœ˜1Jšœ=˜?Jšœ˜!šœ˜Jšœœ˜&š œœœœœœœ˜9J™Ç—Jš œœœœœ˜.šœž ˜šœœ˜JšœÌ™ÌJšœœ)ž ˜Lšœœ˜šœ ™ Jšœ ™ Jšœ›™›——šœœœœ˜JšœL™L—J˜JšŸœœœ˜'J˜šŸ œœœœ˜#Jšœœœœ˜š œ œœœœœ˜IJšœœ˜ —Jšœ#˜#šœœœž˜/Jšœ œœ œ ˜+Jšœ˜—Jšœ˜—J˜šŸœœœž œ˜"šœ ˜ šœ˜Jšœ"œ˜:Jšœœ˜9Jšœ ˜ Jšœ˜—šœ˜Jšœœ˜=Jšœ˜J˜——Jšœ˜—J˜Jš Ÿœœœœœ˜>šœ2™2šœœ˜!Jšœœ˜ Jš œœœœœœœ˜Išœ ˜ šœœœ˜&Jšœ ˜Jšœ œœœœœœ˜<—Jšœ˜—Jš œœœœœœœ˜:—Jšœ6˜=Jšœ˜—J™Jšœ/™/šœ œž"˜Cš˜šœ ˜ š œœ œœ˜,Jšœœ˜ šœ˜šœœ˜Jšœ œ˜)Jšœ œ˜)Jšœ œ˜+Jšœ œ˜(—Jšœ˜——Jšœœ˜———šœ˜Jšœœœ.˜H—šœ ˜ šœ4˜8šœG™GJšœ/™/——šœœœ˜7šœI™IJšœ9™9———šœ ˜ JšœP™P——Jšœž˜J˜šœžŒ˜Jšœ˜šœ˜ šœ˜ Jšœ^™^—Jšœœ˜ šœž@˜GJšœ.œœ˜Dšœœ˜&Jšœ?™?—Jšœ˜—šœ˜Jšœœœ˜Jšœœœž5˜OJšœž#˜*Jšœ˜———Jšœž˜—Jšœž ˜Jšœž ˜—Jšœž˜—J˜šœœ ˜'Jšœ5™5——šŸ œœœœ˜;šœ˜Jšœœ(˜Jšœ˜ Jšœ˜——J˜šŸœœœ˜Lšœ˜Jšœœ˜9Jšœœ&˜BJšœ˜ Jšœ˜——J˜Jšœ˜J˜—…—”