THE MEMORY POOL SYSTEM: THIRTY PERSON-YEARS OF MEMORY MANAGEMENT DEVELOPMENT GOES OPEN SOURCE Richard Brooksby, Ravenbrook Limited, rb@ravenbrook.com Nicholas Barnes, Ravenbrook Limited, nb@ravenbrook.com 2002-01-30 0. ABSTRACT The Memory Pool System (MPS) is a very general, adaptable, flexible, reliable, and efficient memory management system. It permits the flexible combination of memory management techniques, supporting manual and automatic memory management, in-line allocation, finalization, weakness, and multiple concurrent co-operating incremental generational garbage collections. It also includes a library of memory pool classes implementing specialized memory management policies. The MPS represents about thirty person-years of development effort. It contains many innovative techniques and abstractions which have hitherto been kept secret. We are happy to announce that Ravenbrook Limited is publishing the source code and documentation under an open source licence. This paper gives an overview of the system. abstract 0.1. Categories and Subject Descriptors D.2.3 [Software Engineering]: Coding Tools and Techniques; D.3.3 [Programming Languages]: Language constructs and features -- dynamic storage management; D.3.4 [Programming Languages]: Processors -- memory management; D.4.2 [Operating Systems]: Storage Management 0.2. General Terms Algorithms, Design, Reliability 0.3. Keywords Garbage collection, memory management, software engineering 1. INTRODUCTION The Memory Pool System (MPS) is a flexible, extensible, adaptable, and robust memory management system, now available under an open source licence from Ravenbrook Limited. Between 1994 and 2001, Harlequin Limited (now Global Graphics Software Limited) invested about thirty person-years of effort developing the MPS. It contains many innovative techniques and abstractions which have hitherto been kept secret. In 1997, Richard Brooksby, the manager and chief architect of the project, and Nicholas Barnes, a senior developer, left Harlequin to form their own consultancy company, Ravenbrook Limited, and in 2001, Ravenbrook acquired the MPS technology from Global Graphics. Our goals in going open source are that as many people as possible benefit from the hard work that the members of the (now defunct) Memory Management Group put in to the MPS design and implementation. We also hope to develop the MPS further, through commercial licensing and consultancy. This paper gives an overview of the MPS, with particular emphasis on innovative things that it does. 2. BACKGROUND 2.1. History The original Memory Management Group, set up in 1994, consisted of Richard Brooksby and P. Tucker Withington. Richard had previously worked in the ML Group and implemented the MLWorks memory manager and garbage collector. Tucker joined from the ailing Symbolics Inc, where he maintained the Lisp Machine's memory systems. The initial brief of the group was to provide a memory manager for Harlequin's new Dylan system. Harlequin was also interested in a broader set of memory management products, and in absorbing the memory managers of other products, such as ScriptWorks (the high-end PostScript language compatible raster image processor), LispWorks, and MLWorks. Initial prototyping and design work concentrated on a flexible memory management framework which would meet Dylan's requirements but also be adaptable to other projects, and form a stand-alone product. Richard's concerns about the subtlety of a generic memory management interface, the pain of debugging memory managers, and the complexity of the Dylan implementation, led him to push for a fairly formal requirements specification. This set the tone for the group's operations, and led to extensive use of formal software engineering techniques such as inspections. At its height, the group was operating a Capability Maturity Model level 3 process [CMMI1.02]. As a result, the MPS was very robust and had a very low defect rate. This enabled the group to concentrate on development. The Memory Management Group collaborated with the Laboratory for the Foundations of Computer Science at Edinburgh University, with the goal of formally verifying some of the algorithms [Goguen 1999]. The MPS was incorporated into the run-time system of Harlequin's DylanWorks compiler and development environment (now available as "Functional Developer" from Functional Objects, Inc). Later, it replaced the highly optimized memory manager in Harlequin's ScriptWorks, improving performance and reliability to this day as part of Global Graphics' Harlequin RIP. 2.2. Requirements The MPS had a fairly large and complex set of requirements from the beginning. The Harlequin Dylan project was formed from highly experienced Lisp system developers who knew what they wanted [RB 1996-10-02a]. The requirements of ScriptWorks were even more complex [RB 1995-11-01]. On top of this, we were always striving to anticipate future requirements. This section describes the overall architectural requirements that guided all aspects of the design [RB 1997-01-28]: Adaptability: The MPS has to be easy to modify to meet new requirements. This makes the MPS suitable for new applications and ensures it has long and useful life. Flexibility: The MPS must fit into a number of different products and meet differing requirements in diverse environments. It must do this with as little modification as possible, so that it can be deployed at low cost. Flexibility gives the MPS broad application, and reduces the need to maintain special versions of the MPS for different clients. Code re-use also leads to robustness through use testing. Reliability: Memory management defects are very costly. In development they are difficult to find and fix, and once deployed they are virtually impossible to reproduce. The MPS may be shipped to third and fourth parties, further increasing the cost of a defect. Reliability is therefore very important to the viability of the MPS. Efficiency: Efficiency will always be required by clients; after all, memory management is about the efficient utilization of resources to meet requirements. However, the tradeoffs between those requirements will differ from application to application, hence the need for adaptability and flexibility. A generally efficient system will make it easier to meet these requirements. 3. ARCHITECTURE The MPS consists of three main parts: - the Memory Pool Manager (MPM) - the pool classes, and - the arena classes. See Figure 1. Each pool class may be instantiated zero or more times, creating a "pool". A pool contains memory allocated for the client program. The memory is managed according to the memory management policy implemented by its pool class. For example, a pool class may implement a type of garbage collection, or manage a particular kind of object efficiently. Each pool can be instantiated with different parameters, creating variations on the policy. The arena classes implement large-scale memory layout. Pools allocate tracts of memory from the arena in which they manage client data. Some arena classes use virtual memory techniques to give control over the addresses of objects, in order to make mapping from objects to other information very efficient (critically, whether an object is not white). Other arena classes work in real memory machines, such as printer controllers. The MPM co-ordinates the activities of the pools, interfaces with the client, and provides abstractions on which the memory management policies in the pools are implemented. This architecture gives the MPS flexibility, its primary requirement, by allowing an application of the memory manager to combine specialized behaviour implemented by pool classes in flexible configurations. It also contributes to adaptability because pool classes are less effort to implement than a complete new memory manager for each new application. Reliability is enhanced by the fact that the MPM code can be mature code even in new applications. However, efficiency is reduced by the extra layer of the MPM between the client code and the memory management policy. This problem is alleviated by careful critical path analysis and optimization of the MPM, and by providing abstractions that allow the MPM to cache critical information. 4. IMPLEMENTATION The MPS is about 62 Kloc of extremely portable ISO standard C [ANSI C]. Except for a few well-defined interface modules, it is freestanding (doesn't depend on external libraries*1. We have been known to port to a new operating system in less than an hour. The code is written to strict standards. It is heavily asserted, with checks on important and subtle invariants. Every data structure has a run-time type signature, and associated consistency checking routines which are called frequently when the MPS is compiled in "cool" mode*2. Much of the code has been put through formal code inspection (at 10 lines/minute or less) by between four and six experienced memory management developers [Gilb 1995]. It was developed by a team working at approximately Capability Maturity Model level 3 [CMMI1.02]. As a result, it is extremely robust, and has a very low defect rate. The MPS is designed to work efficiently with threads, but is not currently multi-threaded. Fast allocation is achieved by a non-locking in-line allocation mechanism (see section 5.2, "Efficient in-line allocation"). 5. KEY FEATURES AND ATTRIBUTES 5.1. Flexible combination of memory management techniques The most important feature of the MPS is the ability to combine memory management policies efficiently. In particular, multiple instances of differing garbage collection techniques can be combined. In the Harlequin Dylan system, for example, a mostly-copying main pool is combined with a mark-sweep pool for handling weak key hash-tables, a manually-managed pool containing guardians implementing user-level weakness and finalization, and a mark-sweep pool for leaf objects. The same codebase is used with a very different configuration of pools in the Harlequin RIP*3. An overview of the abstractions that allow flexible combination can be found in section 6. 5.2. Efficient in-line allocation The MPS achieves high-speed multi-threaded allocation using the abstraction of "allocation points" backed by allocation buffers [RB 1996-09-02]. The allocation point protocol also allows garbage collection to take place without explicit synchronization with the mutator threads. An allocation point (AP) consists of three pointers: "init", "alloc", and "limit". Before allocation, "init" is equal to "alloc". The thread owning the AP "reserves" a block by increasing "alloc" by the size of the object. If the result exceeds "limit", it calls the MPS to complete the reservation, but otherwise it can initialize the object at "init". Once the object is initialized, the thread "commits" it, by setting "init" equal to "alloc", checking to see if "limit" is zero, and calling the MPS if it is. At this point the MPS may return a flag indicating that the object has been invalidated, and must be allocated and initialized again. Both the reserve and commit operations take very few instructions, and can be inlined. The exact implementation of the AP protocol depends on the pool from which the thread is allocating. Some pools may guarantee that an object is never invalidated, for example, and so the commit check can be omitted. Most pools implement APs by backing them with allocation buffers, fairly large contiguous blocks of memory from which they can allocate without ever calling the MPS. The AP protocol allows in-line allocation of formatted objects (see section 5.5, "Client object formats") containing references that need tracing by a garbage collection. The MPS knows that objects up to "init" have been initialized and can therefore be scanned. It also knows that an object that is half-initialized (somewhere between reserve and commit) when a flip occurs (see section 5.7, "Five phase collection") can't be scanned, and may therefore contain bad references, that is, references which have not been fixed (see section 6.5, "Scanning and Fixing"). Hence the commit check, and the re-allocation protocol. The chances of a flip occurring between a reserve and commit are very low, and re-allocation rarely happens in practice. The AP protocol relies on atomic ordered access to words in memory, and some care must be taken to prevent some processors from re-ordering memory accesses. The design of allocation buffers was inspired by the Symbolics Lisp Machine allocator, which supports a similar protocol in microcode, but requires atomic initialization of objects. 5.3. A library of pool classes 5.3.1. A: Allocate only A simple pool class which only supports in-line allocation. This is useful when objects need to be allocated rapidly then deleted together (by destroying the pool). Allocation is very fast. This pool is not currently in the open sources. 5.3.2. AMC : Automatic Mostly Copying The most complex and well-developed pool class, this was originally designed as the main pool for Harlequin's implementation of Dylan, but is a general purpose moving pool. It implements a generational mostly-copying algorithm [Bartlett 1989]. 5.3.3. AMS : Automatic Mark Sweep This is the general-purpose non-moving counterpart of AMC. Not generational. 5.3.4. AWL : Automatic Weak Linked A specialized pool originally designed to support weak key hash tables in Dylan. In a weak key hash table, the value is nulled out when the key dies (see section 6.4, "Reference ranks for ambiguity, weakness, and finalization"). The pool implements mark sweep collection on its contents. 5.3.5. LO : Leaf Object This pool stores leaf objects (objects not containing references). It was originally designed for use with the Dylan foreign function interface (FFI), guaranteeing that the objects will not be protected by the MPS under a hardware read or write barrier, because interactions with foreign code would be unpredictable. 5.3.6. MFS : Manual Fixed Small A simple pool which allocates objects of fixed (regular) small (much less than a page) size, though each instance of the pool can hold a different size. Not garbage collected. Used internally to the MPS for the management of some of its own dynamic structures. 5.3.7. MRG : Manual Rank Guardian This pool is used internally in the MPS to implement user-level finalization of objects in other pools. Some techniques from [Dybvig 1993] were used in its design. 5.3.8. MV : Manual Variable A manually managed pool for variable sized objects. This is the pool class used internally by the MPS as the control pool for many MPS data structures. It is designed to be very robust, and, like many other MPS pools, keeps all of its data structures away from the objects it manages. It is first-fit, with the usual eager coalescing. 5.3.9. MV2 : Manual Variable 2 An unfinished manually managed pool for variable sized objects, using bitmaps and crossing maps. Designed for high-performance freelists with subtle theory of block reuse. MVFF is bascially a light version of the same that just uses the high performance freelist and first fit. 5.3.10. MVFF : Manual Variable First Fit A general-purpose manually-managed pool for variable sized objects, implementing address-ordered first-fit, but with in-line worst-fit allocation. It is optimized for high performance when there is frequent deallocation in various patterns. 5.4. Support for location dependency Some data structures and algorithms use the address of an object. This can be a problem if the memory manager moves objects around. The MPS provides an abstraction called "location dependency" (LD) which allows client code to depend on the locations of moving objects. The design of LDs was inspired by the Symbolics Lisp Machine which has hardware support for something similar, and an evolution of an algorithm developed by P. Tucker Withington for simulating the LispM hardware on stock hardware when writing the Lisp Machine emulator. 5.5. Client object formats Garbage collectors always have some information about the format of the objects they manage. For example, a non-conservative garbage collector must be able to find and interpret references within the objects it manages. A garbage collector must be able to compute the size of an object given a reference to that object. If the object allocation is entirely handled by the client (as in the MPS; see section 5.2, "Efficient in-line allocation"), the size information is encoded somehow in the object format. This format information is usually entangled deeply in the source code of the collector, for instance in the innermost scan/fix loop. Adapting such a collector to a new object format may be difficult and may introduce some very complex defects. The MPS includes no object format information; rather it allows each MPS client to specify one or more object formats, by providing a small set of methods which operate on pieces of memory. When a client creates a pool of a formatted pool class, it specifies an object format for the objects allocated in that pool. The pool class is then able to invoke these methods as necessary to perform format-specific operations. In particular, the "scan" and "fix" methods of the pool class interact closely with the format methods (see section 6.5, "Scanning and Fixing"). Different pool classes will use formats in different ways. For example, a copying garbage-collected pool may need methods to: - calculate the size of an object; - copy an object; - scan an object; - replace an object with a "broken heart" (containing a forwarding pointer). A non-moving mark-and-sweep pool, on the other hand, may only need methods to calculate the size of an object and to scan an object. The format methods include the following [NB 2001-11-14]: skip: Skips a pointer over an object. copy: Makes a copy of the object in another location. Objects are usually copied byte by byte, but some uncommon object formats might contain relative pointers that have to be fixed up when the object is moved. pad: Fills a block of memory with a dummy object. This should work just like a real object in all the other methods, but contain no data. This method is used by the MPS to fill in odd corners that need to be scannable. fwd: Replaces an object with a "broken heart" of the same size, containing a forwarding pointer. It is used when the MPS has moved an object to a new location in memory. isfwd: distinguishes between a broken heart and a real object, returning the forwarding pointer of a broken heart. scan: locates all references in a contiguous set of objects and tells the MPS where they are. The objects may include dummy objects and broken hearts. align: is an integer value defining the alignment of objects allocated with this format. Note that a single client may use more than one object format, even within the same pool class. A client may choose to have many formatted pools, specializing format methods to the kind of object which is allocated within a given pool. 5.6. Multiple arenas Memory managers, and garbage collectors especially, usually work well with exactly one client. They take over the whole memory infrastructure of a process and provide a single instance of an abstraction to a single client. For instance, they often assume that they have total control over memory protection and memory mappings. In today's modular software world, such an approach has obvious drawbacks. How do you link together two components, possibly written in different languages, with different memory management infrastructures? The design of the MPS avoids such assumptions about the environment in which it runs. It abstracts its entire interface with a client into an "arena" object. There is no "global state" of the MPS (apart from the set of arenas). Separate arenas are managed entirely independently. All MPS operations (e.g., allocation, pool creation, garbage collection) are per-arena. There is more than one way to provide the underlying memory which the MPS manages: it may be a dynamic amount obtained from a virtual memory subsystem, or it may be a fixed amount of client memory (for instance, in an embedded controller or an application which needs a constant memory footprint). These are implemented as distinct "arena classes". Note that the MPS may manage arenas from more than one arena class simultaneously. For testing purposes, there is also an arena class which obtains memory from the C standard library "malloc" function. 6. THE TRACER The Tracer co-ordinates the garbage collection of memory pools. The Tracer is designed to drive multiple simultaneous garbage collection processes, known as "traces", and therefore allows several garbage collections to be running simultaneously on the same heap. Each trace is concerned with refining a "reference partition" (section 6.1, "Reference partitions") using a five-phase garbage collection algorithm that allows for incremental generational non-moving write-barrier type collection (possibly with ambiguous references) combined with incremental generational moving read-barrier type collection, while simultaneously maintaining generational and inter-pool remembered sets. Furthermore, the Tracer co-ordinates garbage collection across pools. A trace can include any set of pools. The Tracer knows nothing of the details of the objects allocated in the pools. This section describes the abstractions used to design such a general system. The definitions are rather abstract and mathematical, but lead to some very practical bit twiddling. The current MPS implementation doesn't make full use of these abstractions. Nonetheless, they were critical in ensuring the that the MPS algorithms were correct. It is our hope that they will be of great use to future designers of garbage collection algorithms. 6.1. Reference Partitions The MPS was originally based on a theory of "reference partitions", which we developed to generalize the familiar idea of "tri-colour marking" [Dijkstra 1976]. Subsequently the MPS was refined to include more varied barrier techniques [Pirinen 1998], but we present the basic theory here to give a flavour of the MPS. A "reference partition" is a colouring of the nodes in a directed graph of objects. Every object is either "black", "grey", or "white" in any reference partition. A partition (B, G, W) of a directed graph is a reference partition if and only if there are no nodes in B which have a reference to any node in W, that is, nothing black can refer to anything white. An "initial" partition is one with no black nodes: (empty, G, W). All initial partitions are trivially reference partitions. A "final" partition is one with no grey nodes: (B, empty, W). For a predicate P, we say some reference partition (B, G, W) is a reference partition "with respect to" P if and only if everything with P is in W, that is, P(x) => x in W. If we can determine a final reference partition such that the client process roots are contained in B then W is unreachable by the mutator, cannot affect future computation, and can be reclaimed. Tracing is a way of finding final reference partitions by refinement. We start out by defining an initial reference partition with respect to a "condemned" property, such as being a member of a generation. We then move reachable objects from G to B, preserving the reference partition invariant by moving objects from W to G where necessary, until we end up with a final reference partition. The key observation here is that any number of partitions can exist for a graph, and so there's no theoretical reason that multiple garbage collections can't happen simultaneously. A second important observation is that because reference partitions can be defined for any property, one could have, for example, a reference partition with respect to a certain size of objects. The MPS uses the reference partition abstraction to implement something equivalent to "remembered sets" [Ungar 1984] by maintaining reference partitions with respect to areas of address space called "zones". This is described further in section 6.2, "Induced graphs". Reference partitions can be usefully combined. If P and Q are reference partitions, then we can define reference partitions P union Q as ( B_P intersection B_Q, ( G_P union G_Q ) - ( W_P union W_Q ), W_P union W_Q ) and P intersection Q as ( B_P union B_Q, ( G_P union G_Q ) - ( B_P union B_Q ), W_P intersection W_Q ). 6.2. Induced graphs Given a directed graph and an equivalence relation on the nodes we can define an "equivalence-class induced graph" whose nodes are the equivalence classes. If there's an edge between two nodes in the graph, then there's an edge between the equivalence classes in the induced graph. We can define reference partitions on the induced graph, and do refinement on those partitions in just the same way as for the original graph. We can garbage collect the induced graph. In fact, you can think of conventional garbage collectors as doing this all the time. Consider a language in which an object may have sub-objects (inlined within its representation in memory), and an object may refer directly to sub-objects of other objects. You can represent the sub-object relationship with implicit references between sub-objects. Then there is a graph on the sub-objects, including both the usual references and these implicit references as edges. The graph of objects we normally discuss is induced from this graph, the equivalence classes being the sets of sub-objects of separate objects. Theoretically we could garbage collect individual sub-objects by tracing this lower level graph, and reclaim the memory occupied by parts of objects! The MPS is general enough to support this, though we have not implemented a pool class which does it. Given "two" equivalence relations R and S on a directed graph G, we can define an "equivalence-class relation induced by R and S", which is a binary relation between the equivalence classes of R and the equivalence classes of S. (R(x), S(y)) is in the relation if the graph includes an edge from x to y in the graph. The MPS divides address space into large areas called "zones". The set of zones is called Z. The number of zones is equal to the number of bits in the target machine word, so any set of zones (subset of Z) can be represented by a word. Given an equivalence relation R, the equivalence-class relation induced by R and Z is called the "summary" of each equivalence class of R. Roughly speaking, it summarizes the set of zones to which that class refers. This is a BIBOP-like technique adapted from the Symbolics Lisp Machine's hardware assisted garbage collection [Moon 1984]. The Tracer groups objects into "segments", and maintains a conservative approximation of the summary of each segment. By doing this, it is maintaining a reference partition with respect to each zone. Segments which don't have a zone in their summary are "black" for that zone, segments which do are "grey" if they aren't in the zone, and "white" if they are. The Tracer uses this information to refine traces during phase 1 of collection; see section 5.7, "Five phase collection". 6.3. Segments The Tracer doesn't deal with individual client program objects. All details of object allocation and format is delegated to the pool. The Tracer deals with areas of memory defined by pool classes called "segments". The segment descriptor contains these fields important to tracing: white: The set of traces for which the segment is white. A superset of the union of the trace whiteness of all the objects in the segment. More precisely, if a trace is not in the set, then the segment doesn't contain white objects for that trace. grey: The set of traces for which the segment is grey. (See "white" above.) summary: A summary (see section 6.2, "Induced graphs") of all the references in the segment. ranks: A superset of the ranks of all the references in the segment (see section 6.4, "Reference ranks for ambiguity, weakness, and finalization"). In addition, the Tracer maintains a set of traces for which the mutator is grey (and assumes it's black for all other traces), and a summary for the mutator. The mutator is a graph node which consists of the processor registers, and any references in memory that can't be protected against transfers to and from the registers. This is _not_ usually the same as the root set. Memory barriers*4 are used to preserve the reference partitions represented by the traces in the face of mutation by the client process. These invariants are maintained by the MPS at all times: - Any segment whose grey trace set is not a subset of the mutator's grey trace set is protected from reads by the mutator. This prevents the mutator from reading a reference to a white object when the mutator is black. If the mutator reads the segment, the MPS catches the memory exception and scans the segment to turn it black for all traces in the difference between the sets. (An theoretical alternative would be to "unflip", making the mutator grey for the union of the sets, but this would seriously set back the progress of a trace.) - Any segment whose grey trace set is not a superset of the mutator's grey trace set is protected from writes by the mutator. This prevents the mutator from writing a reference to a white object into a black object. If the mutator writes to the segment, the MPS catches the memory exception and makes the segment grey for the union of the sets. (An alternative would be to "flip", making the mutator black for the difference between the sets, but this would generally be premature, pushing the colletion's progress along too fast.) - Any segment which has a summary which is not a superset of the mutator's summary is protected from writes by the mutatorThe current implementation of the MPS assumes that the mutator has a universal summary. In other words, it assumes that the mutator could refer to any zone. This could be improved.. If the mutator writes to the segment, the MPS catches the memory exception and unions the summary with the mutator's summary, removing the protection. Abstractly, this is the same invariant as for the grey trace set (see above), because the summaries represent reference partitions with respect to zones. The barrier prevents the mutator writing a pointer to a white object (the zone) into a black object (which doesn't refer to the zone). 6.4. Reference Ranks for Ambiguity, Exactness, Weakness, and Finalization The "rank" of a reference controls the order in which references are traced while refining the reference partition. All references of lower numbered rank are scanned before any references of higher rank. The current MPS implementation supports four ranks: 1. ambiguous: An "ambiguous reference" is a machine word which may or may not be a reference. It must be treated as a reference by the MPS in that it preserves its referent if it's reachable from the client process roots, but can't be updated in case it isn't a reference, and so its referent can't be moved. Ambiguous references are used to implement conservative garbage collection boeh88. 2. exact: An "exact reference" is definitely a reference to an object if it points into a pool. Depending on the pool, the referent may be moved, and the reference may be updated. 3. final: A "final reference" is just like an exact reference, except that a message (sometimes called a "near death notice") is sent to the client process if the MPS finds no ambiguous or exact references to the referent. This mechanism is used to implement finalization haye92,dybv93. 4. weak: A "weak reference" is just like an exact reference, except that it doesn't preserve its referent even if it is reachable from the client process roots. So, if no reachable ambiguous, exact, or final references are found, the weak reference is simply nulled out. This mechanism is used to implement weakness. Note that the pool which owns the reference may implement additional semantics. For example, when a weak reference is nulled out, the AWL pool nulls out an associated strong reference in order to support weak key hash tables. Ranks are by no means a perfect abstraction. Parts of the Tracer have to know quite a bit about the special semantics of ambiguous references. The Tracer doesn't take any special action for final and weak references other than to scan them in the right order. It's the pools that implement the final and weak semantics. For example, the MRG pool class is one which implements the sending of near death notices to the client process. The current implementation of the Tracer does not support segments with more than one rank, but is designed to be extended to do so. The current MPS ordering puts weak after final, and is equivalent to Java's "phantom references". It would be easy to extend the MPS with additional ranks, such as a weak-before-final (like Java's "weak references"). 6.5. Scanning and Fixing In order to allow pools to co-operate during a trace the MPS needs a protocol for discovering references. This protocol is the most time critical part of the MPS, as it may involve every object that it is managing. The MPS protocol is both abstract and highly optimized. Each pool class may implement a "scan" and "fix" method. These are used to implement a generic scan and generic fix method which dispatch to the pool's method as necessary. The scan method maps the generic fix method over the references in a segment. The fix method preserves the referent of a reference (except when it is applied to weak references), moving it out of the white set for one or more traces. The most important optimization is part of the generic fix method which is inlined into the scan methods. The generic fix method first looks up the reference in the interesting set (see section 5.7, "Five phase collection"), which takes about three instructions. This eliminates almost all irrelevant references, such as references to generations which aren't being collected, or references to objects not being managed by the MPS. A second level optimization in the generic fix method checks to see if the reference is to a segment managed by the MPS, and then whether the segment is white for any of the traces for which the reference is being fixed. This eliminates many more references. Only if a reference passes these tests is the pool's fix method called. A pool need not implement both scan and fix methods. A pool which doesn't contain references, but does contain garbage collected objects, will have a "fix" method but no "scan" method. Note that such objects are either black or white. A pool which contains references involved in tracing, but not garbage collected objects, will have a "scan" method but no "fix" method. Such a pool would be a pool of roots, its objects either grey or black. A pool with neither method is not involved in tracing, for example, a manually managed pool storing strings. 6.6. Roots Roots are objects declared to the MPS by the client process as being "a priori" alive. The purpose of tracing is to discover objects which aren't referenced by transitive closure from the roots and recycle the memory they occupy. The MPS supports various kinds of roots. In particular, a thread can be declared as a root, in which case its stack and registers are scanned during a collection. Roots have "grey" and "summary" fields just like segments, and may be protected from reads and writes by the mutator using the same rules. However, roots are never white for any trace, since their purpose is to be alive. 6.7. Five phase collection The Tracer runs each trace through five phases designed to allow pools to co-operate in the same trace even though they may implement very different kinds of garbage collection. 6.7.1. Phase 1: Condemn The set of objects we want to try to recycle, the "condemned set" is identified, and a newly allocated trace is added to the white trace set for the segments containing them. At this stage, all segments containing any references (even the white ones) are assumed to be grey for the trace, because we don't know whether they contain references to objects in the white set. The roots are made grey for the trace, because they are "a priori" alive. The mutator is also assumed to be grey for the trace, because it has had access to all the grey data. Thus we start out with a valid initial reference partition (see section 6.1, "Reference partitions"). We then use any existing reference partitions to reduce the number of grey segments for the trace as much as possible, using this rule: Let P be the set of reference partitions whose white sets are supersets of the new white set. Any node which is in the union of the black sets of P cannot refer to any member of the new white set, and so is also black with respect to it. In practical terms, we work out the set of zones occupied by the white set. We call this the "interesting set". We can then make any segment or root whose summary doesn't intersect with the interesting set black for the new trace. This is just a bitwise AND between two machine words. A pool will usually arrange for a generation to occupy a single zone, so this refinement step can eliminate a large number of grey segments. This is how the MPS implements remembered sets. In a similar way, the MPS could also use the current status of other traces to refine the new trace. Imagine a large slow trace which is performing a copying collection of three generations. A fast small trace could condemn the old space of just one of the generations. Any object which is black for the large trace is also black for the small trace. Such refinement is not implemented in the MPS at present. Note that these refinement steps could be applied at any time: they are just refinements that preserve reference partitions. The MPS currently only applies them during the condemn step. 6.7.2. Phase 2: Grey Mutator Tracing This phase most resembles a write-barrier non-moving garbage collector [Appel 1988]. Any segment "blacker" than the mutator is write protected (see section 6.3, "Segments"). At this point the mutator is grey for the trace. Note that, at any stage, the mutator may be grey or black for different traces independently. In addition, newly allocated objects are grey, because they are being initialized by the mutator. An object can be moved provided that it is white for any trace for which the mutator is black, because the mutator can't see references to that object. During phases 2 and 4 the Tracer makes progress by scanning segments which are grey for one or more traces (see section 6.5, "Scanning and Fixing") in order to make them black. Thus we make progress towards a final reference partition (see section 6.1, "Reference partitions"). 6.7.3. Phase 3: Flip Flipping for a set of traces means turning the mutator black for those traces. This may entail scanning the client process thread registers and any unprotectable data. The mutator can't be running while this is happening, so the MPS stops all mutator threads. This is also the point at which the MPS sets the "limit" fields of any formatted allocation points to zero, so that unscannable half-allocated objects are invalidated (see section 5.2, "Efficient in-line allocation"). 6.7.4. Phase 4: Black Mutator Tracing This phase most resembles a read-barrier possibly-moving garbage collector [Boehm 1991]. Any segment "greyer" than the mutator is read protected (see section 6.3, "Segments"). At this point the mutator is black for the trace. In addition, newly allocated objects are black, and don't need to be scanned. 6.7.5. Phase 5: Reclaim When the grey set for a trace is empty after flip then it represents a final reference partition. The Tracer looks for segments which are white for the trace and calls the owning pool to reclaim the space occupied by remaining white objects within. It's up to the pool to decide whether to return the reclaimed space to its own free list, or to the arena. 7. FUTURE DIRECTIONS The Memory Management Group at Harlequin was whittled away to nothing as Harlequin slid into financial trouble. Parts of the system are incomplete or have unclear status. A large amount of design documentation exists, but it is fairly disorganized and incomplete. We would like to organize all this information to make the MPS a more useful resource. The MPS was designed around many abstractions that make it very adaptable, but it is not very well packaged and is unlikely to work in new applications without some modification. We would like to improve the MPS to make it easier to apply without modification. The MPS is currently commercially licensed to Global Graphics Software Limited for use in the Harlequin RIP, and to Configura Sverige AB for use in their Configura business system. We are seeking further licensees and consultancy. 8. AVAILABILITY The MPS project tree is available on the web at . It includes all of the non-confidential source code and design documentation. This is a mirror of the tree in Ravenbrook's configuration management repository, so it will continue to reflect the development of the MPS. 9. RELATED WORK The MPS resembles the Customisable Memory Management (CMM) framework for C++ [Attardi 1998] and shares some of its design goals. The MPS was not designed for C++, but as a memory manager for dynamic language run-time systems. In fact, it was specifically designed not to require C++. The Memory Management Reference Bibliography contains all the papers that we collected during the project, and can be found on the web at . 10. CONCLUSIONS During our stay at Harlequin we were often frustrated by confidentiality. We were not able to reveal ideas and techniques which we believed were both innovative and useful. The MPS contains many such ideas -- the results of hard work by many people (see section 11, "Acholedgements"). Now, at last, we can reveal almost all. The MPS is a highly portable, robust, extensible, and flexible system for memory management, based on very powerful abstractions. It contains many more useful concepts and abstractions not covered in this paper. We hope that the ideas, techniques, and code of the MPS will be useful. We also hope that companies will license the MPS or engage us to extend and develop it further. 11. Acknowledgements The authors would like to thank all the members of the Memory Management Group for their contributions to the design and implementation of the MPS. The members of the Memory Management Group were: Name Period of membership Nick Barnes 1995-08/1997-11 Richard Brooksby 1994-02/1997-11 Nick "Sheep" Dalton 1997-04/1998-07 Lars Hansen 1998-06/1998-09 David Jones 1994-10/1999-06 Richard Kistruck 1998-02/1999-06 Tony Mann 1998-02/2000-02 Gavin Matthews 1996-08/1998-11 David Moore 1995-04/1996-04 Pekka P. Pirinen 1997-06/2001-04 Richard Tucker 1996-10/1999-09 P. Tucker Withington 1994-02/1998-11 A. REFERENCES [Need to import from BibTeX files] [ANSI C] [Appel 1988] [Attardi 1998] [Bartlett 1989] [Boehm 1991] [CMMI1.02] "CMMI(SM) for Systems Engineering/Software Engineering, Version 1.02 (CMMI-SE/SW, V1.02) (Staged Representation)"; CMMI Product Development Team; Software Engineering Institute; CMU/SEI-2000-TR-018. [Dybvig 1993] [Gilb 1995] "Software Inspection"; Tom Gilb, Dorothy Graham; Addison-Wesley, 1995; ISBN 0-201-63181-4. [Goguen 1999] "Memory Management: An Abstract Formulation of Incremental Tracing"; Types for Proofs and Programs, International Workshop TYPES'99, pp 148-161; Springer, 2000. [Moon 1984] [NB 2001-11-14] "MPS Format Protocol"; Nicholas Barnes; MPS Project Documentation; . [Pirinen 1998] [RB 1995-11-01] "MM/EP-Core Requirements"; MPS Project Documentation. [RB 1996-09-02] "Allocation Buffers and Allocation Points"; Richard Brooksby; MPS Project Documentation; . [RB 1997-01-28] "The Architecture of the MPS"; Richard Brooksby; MPS Project Documentation; . [Ungar 1984] B. DOCUMENT HISTORY C. LICENCE Copyright 2002 Ravenbrook Limited. This document is provided "as is", without any express or implied warranty. You may make and distribute copies of all or part of this document provided that you do not make copies for profit or commercial advantage, and that copies bear this notice and the full citation at the head of the document. D. NOTES 1. Ironically, a lot of clever design went into the interfaces (MPM and the plinth) to make robust and efficient binary interfaces for a closed-source MPS library.). 2. The MPS can be compiled with various flags to give different "varieties". The "cool" varieties are intended for debugging and testing. The "hot" varieties are for delivery. Some level of internal consistency checking is present in all varieties. 3. The details of the Harlequin RIP configuration and the the RIP-specific pool class implementations are confidential, and not available under an open source licence. 4. The MPS uses memory protection (hardware memory barrier) for this, but could easily be adapted to a software barrier (if we have control over the compiler). The MPS abstraction of memory barriers distinguishes between read and write barriers, even if the specific environment cannot. $Id: //info.ravenbrook.com/project/mps/doc/2002-01-30/ismm2002-paper/ismm2002.txt#1 $