The design of the automatic mostly-copying memory pool class

THE DESIGN OF THE AUTOMATIC MOSTLY-COPYING MEMORY POOL CLASS design.mps.poolamc incomplete design richard 1995-08-25 INTRODUCTION .intro: This is the design of the AMC Pool Class. AMC stands for Automatic Mostly-Copying. This design is highly fragmentory and some may even be sufficiently old to be misleading. .readership: The intended readership is any MPS developer. OVERVIEW .overview: This class is intended to be the main pool class used by Harlequin Dylan. It provides garbage collection of objects (hence "automatic"). It uses generational copying algorithms, but with some facility for handling small numbers of ambiguous references. Ambiguous references prevent the pool from copying objects (hence "mostly copying"). It provides incremental collection. [ lot of this design is awesomely old -- drj 1998-02-04] DEFINITIONS .def.grain: Grain. An quantity of memory which is both aligned to the pool's alignment and equal to the pool's alignment in size. IE the smallest amount of memory worth talking about. DESIGN Segments .seg.class: AMC allocates segments of class AMCSegClass, which is a subclass of GCSegClass. Instances contain a segTypeP field, which is of type int*. .seg.gen : AMC organizes the segments it manages into generations. .seg.gen.map: Every segment is in exactly one generation. .seg.gen.ind: The segment's segTypeP field indicates which generation (that the segment is in) (an AMCGenStruct see blah below). .seg.typep: The segTypeP field actually points to either the type field of a generation or to the type field of a nail board. .seg.typep.distinguish: The type field (which can be accessed in either case) determines whether the segTypeP field is pointing to a generation or to a nail board. .seg.gen.get: The map from segment to generation is implemented by AMCSegGen which deals with all this. Fixing and Nailing [.fix.nail.* are placeholders for design rather than design really-- drj 1998-02-04] .fix.nail: .nailboard: AMC uses a nail board structure for recording ambiguous references to segments. A nail board is a bit table with one bit per grain in the segment. .nailboard.create: Nail boards are allocated dynamically whenever a segment becomes newly ambiguously referenced. .nailboard.destroy: They are deallocated during reclaim. Ambiguous fixes simply set the appropriate bit in this table. This table is used by subsequent scans and reclaims in order to work out what objects were marked. .nailboard.emergency: During emergency tracing two things relating to nail boards happen that don't normally: .nailboard.emergency.nonew: Nail boards aren't allocated when we have new ambiguous references to segments (.nailbaord.emergency.nonew.justify: We could try and allocate a nail board, but we're in emergency mode so short of memory so it's unlikely to succeed, and there would be additional code for yet another error path which complicates things); .nailboard.emergency.exact: nail boards are used to record exact references in order to avoid copying the objects. .nailboard.hyper-c onservative: Not creating new nail boards (.nailboard.emergency.nonew above) means that when we have a new reference to a segment during emergency tracing then we nail the entire segment and preserve everything in place. .fix.nail.states: Partition the segment states into 4 sets: white segment and not nailed (and has no nail board) white segment and nailed and has no nail board white segment and nailed and has nail board the rest .fix.nail.why: A segment is recorded as being nailed when either there is an ambiguous reference to it, or there is an exact reference to it and the object couldn't be copied off the segment (because there wasn't enough memory to allocate the copy). In either of these cases reclaim cannot simply destroy the segment (usually the segment will not be destroyed because it will have live objects on it, though see .nailboard.limitations.middle below). If the segment is nailed then we might be using a nail board to mark objects on the segment. However, we cannot guarantee that being nailed implies a nail board, because we might not be able to allocate the nail board. Hence all these states actually occur in practice. .fix.nail.distinguish: The nailed bits in the segment descriptor (SegStruct) are used to record whether a segment is nailed or not. The segTypeP field of the segment either points to (the "type" field of) an AMCGen or to an AMCNailBoard, the type field can be used to determine which of these is the case. (see .seg.typep above). .nailboard.limitations.single: Just having a single nail board per segment prevents traces from improving on the findings of each other: a later trace could find that a nailed object is no longer nailed or even dead. Until the nail board is discarded, that is. .nailboard.limitations.middle: An ambiguous reference into the middle of an object will cause the segment to survive, even if there are no surviving objects on it. .nailboard.limitations.reclaim: AMCReclaimNailed could cover each block of reclaimed objects between two nailed objects with a single padding object, speeding up further scans. Emergency Tracing .emergency.fix: AMCFixEmergency is at the core of AMC's emergency tracing policy (unsurprisingly). AMCFixEmergency chooses exactly one of three options: a) use the existing nail board structure to record the fix, b) preserve and nail the segment in its entirety, c) snapout an exact (or high rank) pointer to a broken heart to the broken heart's forwarding pointer. If the rank of the reference is AMBIG then it either does a) or b) depending on wether there is an existing nail board or not. Otherwise (the rank is exact or higher) if there is a broken heart it is used to snapout the pointer. Otherwise it is as for an AMBIG ref (we either do a) or b)). .emergency.scan: This is basically as before, the only complication is that when scanning a nailed segment we may need to do multiple passes, as FixEmergency may introduce new marks into the nail board. Buffers .buffer.class: AMC uses buffer of class AMCBufClass (a subclass of SegBufClass) .buffer.gen: Each buffer allocates into exactly one generation. .buffer.gen: AMCBuf buffer contain a gen field which points to the generation that the buffer allocates into. .buffer.fill.gen: AMCBufferFill uses the generation (obtained from the gen field) to initialise the segment's segTypeP field which is how segments get allocated in that generation. .buffer.condemn: We condemn buffered segments, but not the contents of the buffers themselves, because we can't reclaim uncommitted buffers (see design.mps.buffer for details). If the segment has a forwarding buffer on it, we detach it [why? @@@@ forwarding buffers are detached because they used to cause objects on the same segment to not get condemned, hence caused retention of garbage. Now that we condemn the non-buffered portion of buffered segments this is probably unnecessary -- drj 1998-06-01 But it's probably more efficient than keeping the buffer on the segment, because then the other stuff gets nailed -- pekka 1998-07-10]. If the segment has a mutator buffer on it, we nail the buffer. If the buffer cannot be nailed, we give up condemning, since nailing the whole segment would make it survive anyway. The scan methods skip over buffers and fix methods don't do anything to things that have already been nailed, so the buffer is effectively black. AMCStruct .struct: AMCStruct is the pool class AMC instance structure. .struct.pool: Like other pool class instances, it contains a PoolStruct containing the generic pool fields. .struct.format: The "format" field points to a Format structure describing the object format of objects allocated in the pool. The field is intialized by AMCInit from a parameter, and thereafter it is not changed until the pool is destroyed. [actually the format field is in the generic PoolStruct these days. drj 1998-09-21] [lots more fields here] Generations .gen: Generations partition the segments that a pool manages (see .seg.gen.map above). .gen.collect: Generations are more or less the units of condemnation in AMC. And also the granularity for forwarding (when copying objects during a collection): all the objects which are copied out of a generation use the same forwarding buffer for allocating the new copies, and a forwarding buffer results in allocation in exactly one generation. .gen.rep: Generations are represented using an AMCGenStruct structure. .gen.create: All the generation are create when the pool is created (during AMCInitComm). .gen.manage.ring: An AMC's generations are kept on a ring attached to the AMCStruct (the genRing field). .gen.manage.array: They are also kept in an array which is allocated when the pool is created and attached to the AMCStruct (the gens field holds the number of generations, the gen field points to an array of AMCGen). [it seems to me that we could probably get rid of the ring -- drj 1998-09-22] .gen.number: There are AMCTopGen + 2 generations in total. "normal" generations numbered from 0 to AMCTopGen inclusive and an extra "ramp" generation (see .gen.ramp below). .gen.forward: Each generation has an associated forwarding buffer (stored in the "forward" field of AMCGen). This is the buffer that is used to forward objects out of this generation. When a generation is created in AMCGenCreate, its forwarding buffer has a NULL p field, indicating that the forwarding buffer has no generation to allocate in. The collector will assert out (in AMCBufferFill where it checks that buffer->p is an AMCGen) if you try to forward an object out of such a generation. .gen.forward.setup: All the generation's forwarding buffer's are associated with generations when the pool is created (just after the generations are created in AMCInitComm). Ramps .ramp: Ramps usefully implement the begin/end mps_alloc_pattern_ramp interface. .gen.ramp: To implement ramping (request.dylan.170423), AMC uses a special "ramping mode", where promotions are redirected. .gen.ramp.before: While ramping, objects promoted from a designated (AMCRampGenFollows) generation are forwarded into a special "ramp generation", instead of their usual generation. .gen.ramp.itself: The ramp generation is promoted into itself during ramping mode; after this mode ends, it is promoted into the generation after AMCRampGenFollows (even if ramping mode is immediately re-entered, but only once in that case). .ramp.mode: Ramping is controlled using the rampMode field of the pool. There are five modes: enum { outsideRamp, beginRamp, ramping, finishRamp, collectingRamp }; [These would perhaps be better if they all start Ramp* or AMCRamp* drj 1998-08-07] .ramp.count: The pool just counts the number of ap's that have begun ramp mode (and not ended). .ramp.begin: Basically, when the count goes up from zero, the pool enters into beginRamp mode; however, that doesn't happen if it is already in finishRamp mode, thereby ensuring at least one (decision to start a) collection when leaving ramp mode even if a new ramp starts immediately (but see .ramp.collect below). When a new GC begins in beginRamp mode, and a segment in generation AMCRampGenFollows is condemned, AMCWhiten switches the generations to forward in the ramping way (.gen.ramp); the pool enters ramping mode. (This assumes that each generation is condemned together with all lower generations.) .ramp.end: After the ramp count goes back to zero, the pool enters finishRamp mode, or outsideRamp directly, if there's no ramp generation (this means we never collected generation AMCRampGenFollows, and hence never switched the promotion). When a new GC begins in finishRamp mode (this GC will always collect the ramp generation, because we jig the benefits to ensure that), and a segment in generation AMCRampGenFollows is condemned, AMCWhiten switches the generations to forward in the usual way (.gen.ramp); the pool enters collectingRamp mode. .ramp.collect: The purpose of collectingRamp mode is to ensure the pool will switch back into ramping if the ramp count goes immediately back up, but not before having collected the ramp generation once. So this mode tells AMCReclaim to check the ramp count, and change the mode to beginRamp or outsideRamp. .ramp.collect-all: There are two flavours of ramp collections: the normal one that collects the ramp generation and the younger ones, and the collect-all flavour that does a full GC (this is a hack for producing certain Dylan statistics). The collection will be of collect-all flavour, if any of the RampBegins during the corresponding rank asked for that. Ramp beginnings and collections are asynchronous, so we need two fields to implement this behaviour: collectAll to indicate whether the ramp collection that is about to start should be collect-all, and collectAllNext to keep track of whether the current ramp has any requests for it. Headers : AMC supports a fixed-size header on objects, with the client pointers pointing after the header, rather than the base of the memory block. See format documentation for details of the interface. : The code mostly deals in client pointers, only computing the base and limit of a block when these are needed (such as when an object is copied). In several places, the code gets a block of some sort, a segment or a buffer, and creates a client pointer by adding the header length (pool->format->headerLength). : There are two versions of the fix method, due to its criticality, with (AMCHeaderFix) and without (AMCFix) headers. The correct one is selected in AMCInitComm, and placed in the pool's fix field. This is the main reason why fix methods dispatch through the instance, rather than the class like all other methods. OLD AND AGING NOTES BELOW HERE: AMCFinish .finish: .finish.forward: 103 /* If the pool is being destroyed it is OK to destroy */ 104 /* the forwarding buffers, as the condemned set is about */ 105 /* to disappear. */ AMCBufferEmpty .flush: Removes the connexion between a buffer and a group, so that the group is no longer buffered, and the buffer is reset and will cause a refill when next used. .flush.pad: The group is padded out with a dummy object so that it appears full. .flush.expose: The buffer needs exposing before writing the padding object onto it. If the buffer is being used for forwarding it might already be exposed, in this case the segment attached to it must be covered when it leaves the buffer. See .fill.expose. .flush.cover: The buffer needs covering whether it was being used for forwarding or not. See .flush.expose. AMCBufferFill .fill: 185 * Reserve was called on an allocation buffer which was reset, 186 * or there wasn't enough room left in the buffer. Allocate a group 187 * for the new object and attach it to the buffer. 188 * .fill.expose: 189 * .fill.expose: If the buffer is being used for forwarding it may 190 * be exposed, in which case the group attached to it should be 191 * exposed. See .flush.cover. AMCBufferTrip .trip: 239 * A flip occurred between a reserve and commit on a buffer, and 240 * the buffer was "tripped" (limit set to zero). The object wasn't 241 * scanned, and must therefore be assumed to be invalid, so the 242 * reservation must be rolled back. This function detaches the 243 * buffer from the group completely. The next allocation in the 244 * buffer will cause a refill, and reach AMCFill. AMCBufferFinish .buffer-finish: 264 * Called from BufferDestroy, this function detaches the buffer 265 * from the group it's attached to, if any. AMCFix .fix: 281 * fix an ambiguous reference to the pool 282 * 283 * Ambiguous references lock down an entire segment by removing it 284 * from old-space and also marking it grey for future scanning. 285 * 286 * fix an exact, final, or weak reference to the pool 287 * 288 * These cases are merged because the action for an already 289 * forwarded object is the same in each case. After that 290 * situation is checked for, the code diverges. 291 * 292 * Weak references are either snapped out or replaced with 293 * ss->weakSplat as appropriate. 294 * 295 * Exact and final references cause the referenced object to be copied t o 296 * new-space and the old copy to be forwarded (broken-heart installed) 297 * so that future references are fixed up to point at the new copy. 298 * 299 * .fix.exact.expose: In order to allocate the new copy the 300 * forwarding buffer must be exposed. This might be done more 301 * efficiently outside the entire scan, since it's likely to happen 302 * a lot. 303 * 304 * .fix.exact.grey: The new copy must be at least as grey as the old one, 305 * as it may have been grey for some other collection. AMCGrey .grey: 453 * Turns everything in the pool which is not condemned for a trace 454 * grey. AMCSegScan .seg-scan: 485 * .seg-scan.blacken: One a group is scanned it is turned black, i.e. 486 * the ti is removed from the grey TraceSet. However, if the 487 * forwarding buffer is still pointing at the group it could 488 * make it grey again when something is fixed, and cause the 489 * group to be scanned again. We can't tolerate this at present, 490 * the the buffer is flushed. The solution might be to scan buffers 491 * explicitly. .seg-scan.loop: 505 /* While the group remains buffered, scan to the limit of */ 506 /* initialized objects in the buffer. Either it will be reached, */ 507 /* or more objects will appear until the segment fills up and the */ 508 /* buffer moves away. */ .seg-scan.finish: 520 /* If the group is unbuffered, or becomes so during scanning */ 521 /* (e.g. if the forwarding buffer gets flushed) then scan to */ 522 /* the limit of the segment. */ .seg-scan.lower: 540 /* The segment is no longer grey for this collection, so */ 541 /* it no longer needs to be shielded. */ AMCScan .scan: 556 * Searches for a group which is grey for the trace and scans it. 557 * If there aren't any, it sets the finished flag to true. AMCReclaim .reclaim: 603 * After a trace, destroy any groups which are still condemned for the 604 * trace, because they must be dead. 605 * 606 * .reclaim.grey: Note that this might delete things which are grey 607 * for other collections. This is OK, because we have conclusively 608 * proved that they are dead -- the other collection must have 609 * assumed they were alive. There might be a problem with the 610 * accounting of grey groups, however. 611 * 612 * .reclaim.buf: If a condemned group still has a buffer attached, we 613 * can't destroy it, even though we know that there are no live objects 614 * there. Even the object the mutator is allocating is dead, because 615 * the buffer is tripped. AMCAccess .access: 648 * This is effectively the read-barrier fault handler. 649 * 650 * .access.buffer: If the page accessed had and still has the 651 * forwarding buffer attached, then trip it. The group will now 652 * be black, and the mutator needs to access it. The forwarding 653 * buffer will be moved onto a fresh grey page. 654 * 655 * .access.error: @@@@ There really ought to be some error recovery. 656 * 657 * .access.multi: @@@@ It shouldn't be necessary to scan more than 658 * once. Instead, should use a multiple-fix thingy. This would 659 * require the ScanState to carry a _set_ of traces rather than 660 * just one. OLD NOTES Group Scanning

C. Copyright and License

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.

Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

Redistributions in any form must be accompanied by information on how to obtain complete source code for the this software and any accompanying software that uses this software. The source code must either be included in the distribution or be available for no more than the cost of distribution plus a nominal fee, and must be freely redistributable under reasonable conditions. For an executable file, complete source code means the source code for all modules it contains. It does not include source code for modules or files that typically accompany the major components of the operating system on which the executable file runs.

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.

$Id: //info.ravenbrook.com/project/mps/branch/2002-05-22/open-source-prep/design/poolamc/index.html#1 $

Ravenbrook / Projects / Memory Pool System / Master Product Sources / Design Documents

A. References

B. Document History

C. Copyright and License