RHSK's AMC Seg state diagram. 2007-03-20 This diagram is slightly over-simplified; see .simplify.* below. DIAGRAM ------- mBf >|traceStart|> [goto mBf] uncondemned mBf >|traceStart|> [goto mGf] greyen mBn mBs >|traceStart|> mBs mB uncondemned mB // m0n ..alloc..> mBn ..alloc..> mB mBn mBs >|traceStart|> mGs ==[1a]==> mBs mB greyen |> mG ==[1b]==> mB ^detach**^ ^detach**^ mGf ==[1c+]==> mBf / |traceStart|> mW*Fs whiten --(A)--> bGW*Fs ==[2]==> bBW*Fs ==[2et+]=> <-(et)-- ^we never encounter A here --(et)--> sGFs ==[3]==> sBFs STATES ------ AMC segment modes: m : mobile b : boarded (a nailboard has been allocated) s : stuck (SegNailed, but we can't allocate a nailboard) Object colours: B : black G : grey W : white F : forwarding pointer (these are also white) 0 : no objects in seg Buffers: f : forwarding buffer n : neo (mutator buffer, still alive) s : possible stalo (mutator buffer, has been tripped, stale object, dead) When a buffer detaches, it is replaced by a pad object (I think). If the mutator is between reserve and commit, the collector cannot detach the stalo buffer. Therefore any old (pre-flip) segment may have stale mutator buffer, which will never advance (init may, but the scanner must respect initAtFlip). However, with threads, it could (I think) detach during scan of a segment. This should be easy for scanners to cope with, because it is replaced by a pad, which may be scanned or not with no effect. TRANSITIONS ----------- Scan: ==[]==> : scan (G->B transition happens after scan is complete) .no-transition: no transition can happen *during* the scan (except for buffer-detach, see [1c+]) [1a] scan old mobile grey seg with a stale mutator buffer on it. [1b] scan old or new mobile grey seg, no buffer. [1c+] scan new mobile grey seg with a fwding buffer on it; must loop, until Cheney catchup; buffer may detach during the scan (see needs to loop until no more grey objects (no new marks). [3] scan a stuck segment. Discovery fix: (referent object W in this seg must be preserved) --(et)-->: during emergency tracing: W->G --(A)--> : via Ambiguous ref during non-emergency: W->G * : via Exact ref during non-emergency: forward + W->F Reencounter fix: (referent object FGB has already been preserved) F : snap out (always: normal or emergency tracing) (we should AVER this is not via Ambiguous ref!) GB : do nothing Forward objects into: >fwd-to> : objects forwarded into forwarding buffer on this seg Other transitions: >traceStart> : state change on TraceStart() // : segment created post-flip ..alloc..> : mutator allocates ^detach**^ : forwarding causes buffer to detach, perhaps while scanning this seg THE THREE ROLES --------------- During the main part of a trace, the three possible roles for a segment are: - being scanned; - holding the referent object ('being fixed'); - receiving the forwarded object. Scanning changes the segment summary. Fixing does not change the referent object's segment's summary. Forwarding changes the receiving segment's summary. SIMULTANEOUS ROLES ------------------ Can fixes happen in the seg we are scanning? Yes: - discovery fix: (referent object W in this seg must be preserved) So only in [2] and [2et+]: -- (et), during emergency tracing, W->G: Make new nailboard mark and loop. -- (A), via Ambiguous ref during non-emergency, W->G: Never encountered. -- *, via Exact ref during non-emergency, forward + W->F: Does not affect scan progress. - reencounter fix: (referent object FGB has already been preserved) In [2], [2et+], and [3]: -- F, snap out: Does not affect scan progress, but changes segment summary. In any scan: -- GB, the fix is trivial, and does not affect scan or summary. - can a fix cause a transition? No: see .no-transition. Can objects be forwarded into the seg we are scanning? Yes: see scan [1c+]. TRUE STATEMENTS --------------- .stat.fwdbuf-nand-white: Can never get a white object and a forwarding buffer on the same seg. .stat.fwdbuf-nand-white.why: The only thing that makes white objects is AMCWhiten(), which detaches any forwarding buffer before whitening. The only thing that makes forwarding buffers is AMCBufferFill, which always calls SegAlloc() to get a new seg, which is always non-white (see SegInit and TractInit). CONJECTURES ----------- .stat.fwdbuf-survives: A forwarding buffer can survive traceStart and flip while remaining attached to the same segment : "mBf >traceStart> m(something)f". It may get greyened (by traceStart, or when objects are subsequently forwarded into it), or not. SIMPLIFICATIONS --------------- Some of these simplifications may happen to be true, but they are unverified. .simplify.trip-all-neo: Assume all mutator buffers get tripped (n -> s) at traceStart. .simplify.reclaim-not-shown: Reclaim is not shown. HISTORY 2007-03-20 RHSK Created, and checked with DRJ. 2007-03-23 RHSK sG is sGF; explicitly show the s(stalo) everywhere; analyse discovery and reencounter fixes. 2007-03-23 RHSK Complete note on stale mutator buffers. Fixes don't change summary, but forwarding does in [1c+]. 2007-04-30 RHSK Show both fwdbuf-survives transitions as [goto]. Describe three roles for a segment. --end--