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 dag of references to find all reachable objects.
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.
This document is copyright © 2007 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.