This wiki article contains incomplete and informal notes about the MPS, the precursor to more formal documentation. Not confidential. Readership: MPS users and developers.
Tracing is when the MPS follows the directed graph of references to find all reachable objects.
ref --> Object
Root [ ref, ref, ref ]
Object [ ref, ref, ref ]
Refs are conceptually just the address (in virtual memory address-space) of the referent, but there may be some encoding (tag bits, auto_header offsets). The referent is an Object. (Whereas a root may have no address, so there's no general way for a Ref to refer to a root).
Refs should be usually be managed. A "managed reference" is one which the MPS knows is part of the object graph, such as references in declared roots, and references in managed objects with a format-scan method. The MPS keeps managed references freesh. Unmanaged refs may become stale, and are only safe in very restricted circumstances (see allocation point protocol).
All managed refs in externally allocated memory must be Roots (scannable, not collectable). (We could support externally-allocated non-root Objects (scannable, non-collectable), with extra work, but there's no requirement). A root is usually (currently: always) unprotectable, which has several consequences: it must be scanned at mutator flip, and its summary will always be RefSetUNIV.
All Objects are MPS-allocated, ie. in a Segment.
Possible attributes of an Object:
Objects may be collectable but not scannable: eg. leaf objects. Objects may be scannable but not collectable: eg. finalization guardians. Objects may be formatted but neither collectable nor scannable.
If a scannable Object is never condemned, then it acts quite like a root. This is how finalization guardians work: they are part of the graph (scannable), their segs are RankFINAL (see MRGRefSegInit()), and they are never condemned. (Aside: how come they are never condemned? The pool has no chain, so is not eligible for full (sic) collection. The pool does not have AttrGC, so it is not condemned in minor collections (see TraceCondemnZones())).
To scan a Root or Object means to find all the refs within it.
To fix a ref means: do whatever is necessary to make sure that ref will be correct and useful when the trace ends. That often includes:
A black Object is preserved (that is: it will not be reclaimed) and all refs it contains are fixed (according to the above definition of "fix"). A grey Object is preserved but contains unfixed refs. A white Object is not preserved and contains unfixed refs.
Optimisations avoid the fix operation where possible:
The trace-band determines the rank at which the fix occurs. This must be at least as early as the rank of the ref, but may be earlier (for example, barrier-hits on weak refs may cause fixes at an earlier rank, such as exact).
The Object end of the fix detects whether this fix is a "discovery fix" (such that immediately before the fix the object was not marked for preservation), or a "re-encounter fix" (the object was marked for preservation already). This determines whether a weak ref should be splatted: a discovery fix at trace-band weak should cause the ref to be splatted and the object to remain unmarked, but a re-encounter fix should maintain the weak ref. The discovery/re-encounter property is also reported to the ref end of the fix, via ss->wasMarked; this is important for finalization (prompting a finalization message).
The Object end of the fix may also determine a new value for the reference, which is passed back to the ref end and overwrites the old value of the ref. This is used for Objects in pools that preserve by moving, causing snap-out of the ref. It is also used for weakness, splatting the ref.
The unit of trace scanning is the segment. Trace calls PoolScan(&wasTotal, &ss, SegPool(seg), seg). PoolScan must make the seg non-grey, or return a failure code.
When scan encounters a ref, the ref and the referent object get fixed. Fixing can cause several kinds of change; these changes happen immediately, right in the middle of scanning. WARNING: These changes can be on the same segment we are scanning:
Scanning code must behave correctly when these changes affect the segment currently being scanned. The tricky issues are: not crashing, completeness of de-greying, getting the final summary correct, doing the accounting correctly, etc.
Looping is all about completeness of de-greying; it is affected by both colour and buffers.
.scan.loop.once: If the seg is full and non-white (eg. all grey) when scanning starts, then a single linear scan will make the seg non-grey (in fact: all black). In this case only, we do not need a loop.
Otherwise, there are two ways new grey objects can appear in the segment while we are scanning it:
.scan.loop.white: If the seg contains some white objects when we start a linear scan, then a Ref that points backwards into the same seg can fix and grey an object that was skipped as white when the linear scan passed over it. So scanning must loop until it the whole seg is non-grey. (This condition is a case of .scan.change.obj-colour).
.scan.loop.buffer: If the seg has, or could get, a Forwarding-grey (or Mutator-grey, not yet implemented) buffer, then new grey objects can arrive during the scan. WARNING: buffers move around during scanning: a buffer could be attached, or detached, several times during scanning a single segment, especially in low memory situations. (This condition is a case of .scan.change.buffer).
.scan.loop.terminate: There needs to be communication between the thing that makes new grey objects, and the scan loop termination condition.
.scan.loop.terminate.no-new-marks: The usual termination condition for .scan.loop.white is that the last iteration produced no new marks. A newMarks boolean is used by AMC and AMS. (Perhaps it is also needed for other reasons?). [Note: It might be reasonable to make buffers touch the same newMarks boolean, to provide the termination condition for .scan.loop.buffer. RHSK 2007-01-18].
[.scan.loop.terminate.seggrey: An alternative would be for newly fixed or forwarded objects to do SegSetGrey to trigger another iteration. They have to do this anyway, for the case that the preserved object is on a different seg. To use this to control scan loop termination, scan would have to de-grey the seg at scan start, which is slightly alarming. But I can't think of any actual problem with it, except that the mutator musn't see the seg yet, which mucks up the shield abstraction. Hmmm. It still might be better than lots of special-case code in pools though? RHSK 2007-01-18]
.scan.loop.de-grey: After a resOK scan, the seg is set non-grey by traceScanSegRes() in trace.c.
.scan.loop.no-escape: So there is no way to 'escape from' the complete-degrey requirement, and no way to mark this seg as 'still grey' at the end of the scan, except by returning an error.
.scan.loop.emergency: Any error returned by scan (which must be in the ResIsAllocFailure category) will put the traces into emergency mode and cause an immediate re-scan.
Total versus non-Total scans is all about updating the segment summary; it is affected by both colour and buffers.
The current design is that the segment summary is not updated as new refs (from relocating fixes or splats) are written into the seg during the scan. Instead, the summary of the old and new refs seen by the scan is kept in the scan state: ss->unfixedSummary and ss->fixedSummary.
.scan.total.not: A scan does not necessarily see all objects: objects that were already black at scan start are usually skipped; and objects that remain white at scan end are always skipped. This is the !wasTotal case, and the fixedSummary resulting from the scan must be unioned into the segment summary.
.scan.total.yes: But if all objects in the segment were scanned*, PoolScan sets wasTotal to true. (*: for example, if the whole seg was grey at scan start). The trace then uses ss->fixedSummary to replace the old segment summary.
This is how a non-trivial scan of a seg happens in AMC:
traceScanSeg /* without fail: if needed triggers emergency retry (cannot fail) */
traceScanSegRes
ScanStateInit
ss->fix = TraceFix, or TraceFixEmergency
ShieldExpose
PoolScan
(*pool->class->scan)
AMCScan
while (buffer still leaving trail)
(*pool->format->scan)(ss, base, limit);
[for example]
dylan_scan
mps_fix
MPS_FIX12
ss->unfixedSummary += ref
(*ss->fix)(ss, ref_io)
TraceFix
TraceSetInter(TractWhite(tract(ref)), ss->traces)?
TRACT_SEG?
PoolFix(pool, ss, seg, refIO)
= (*pool->fix)(pool, ss, seg, refIO)
...see below...
ss->fixedSummary += newRef
ShieldCover
Where:
PoolFix(pool, ss, seg, refIO)
= (*pool->fix)(pool, ss, seg, refIO)
AMCFix, AMCHeaderFix
ShieldExpose(ref)
(*pool->format->isMoved)(ref)?
no:
/* Forward */
newRef = BUFFER_RESERVE(seg->gen->forward)
ShieldExpose(newRef)
union colour
union summary
AddrCopy(*newRef = *ref)
ShieldCover(newRef)
BUFFER_COMMIT
(*pool->format->move)(ref, newRef)
ref = newRef
yes:
/* Snap out */
ref = newRef
ShieldCover(ref)
2007-01-12 RHSK Created. 2007-01-16 RHSK .scan.loop, .scan.total. 2007-01-18 RHSK .scan.change. 2010-11-05 RHSK Introduction: how tracing works with refs and Objects
This document is copyright © 2007,2010 Ravenbrook Limited. All rights reserved. This is an open source license. Contact Ravenbrook for commercial licensing options.
Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
This software is provided by the copyright holders and contributors "as is" and any express or implied warranties, including, but not limited to, the implied warranties of merchantability, fitness for a particular purpose, or non-infringement, are disclaimed. In no event shall the copyright holders and contributors be liable for any direct, indirect, incidental, special, exemplary, or consequential damages (including, but not limited to, procurement of substitute goods or services; loss of use, data, or profits; or business interruption) however caused and on any theory of liability, whether in contract, strict liability, or tort (including negligence or otherwise) arising in any way out of the use of this software, even if advised of the possibility of such damage.