diff options
Diffstat (limited to 'boehm-gc/doc/gcdescr.html')
| -rw-r--r-- | boehm-gc/doc/gcdescr.html | 560 |
1 files changed, 0 insertions, 560 deletions
diff --git a/boehm-gc/doc/gcdescr.html b/boehm-gc/doc/gcdescr.html deleted file mode 100644 index cab6bde..0000000 --- a/boehm-gc/doc/gcdescr.html +++ /dev/null @@ -1,560 +0,0 @@ -<HTML> -<HEAD> - <TITLE> Conservative GC Algorithmic Overview </TITLE> - <AUTHOR> Hans-J. Boehm, HP Labs (Much of this was written at SGI)</author> -</HEAD> -<BODY> -<H1> <I>This is under construction, and may always be.</i> </h1> -<H1> Conservative GC Algorithmic Overview </h1> -<P> -This is a description of the algorithms and data structures used in our -conservative garbage collector. I expect the level of detail to increase -with time. For a survey of GC algorithms, see for example -<A HREF="ftp://ftp.cs.utexas.edu/pub/garbage/gcsurvey.ps"> Paul Wilson's -excellent paper</a>. For an overview of the collector interface, -see <A HREF="gcinterface.html">here</a>. -<P> -This description is targeted primarily at someone trying to understand the -source code. It specifically refers to variable and function names. -It may also be useful for understanding the algorithms at a higher level. -<P> -The description here assumes that the collector is used in default mode. -In particular, we assume that it used as a garbage collector, and not just -a leak detector. We initially assume that it is used in stop-the-world, -non-incremental mode, though the presence of the incremental collector -will be apparent in the design. -We assume the default finalization model, but the code affected by that -is very localized. -<H2> Introduction </h2> -The garbage collector uses a modified mark-sweep algorithm. Conceptually -it operates roughly in four phases, which are performed occasionally -as part of a memory allocation: - -<OL> - -<LI> -<I>Preparation</i> Each object has an associated mark bit. -Clear all mark bits, indicating that all objects -are potentially unreachable. - -<LI> -<I>Mark phase</i> Marks all objects that can be reachable via chains of -pointers from variables. Often the collector has no real information -about the location of pointer variables in the heap, so it -views all static data areas, stacks and registers as potentially containing -pointers. Any bit patterns that represent addresses inside -heap objects managed by the collector are viewed as pointers. -Unless the client program has made heap object layout information -available to the collector, any heap objects found to be reachable from -variables are again scanned similarly. - -<LI> -<I>Sweep phase</i> Scans the heap for inaccessible, and hence unmarked, -objects, and returns them to an appropriate free list for reuse. This is -not really a separate phase; even in non incremental mode this is operation -is usually performed on demand during an allocation that discovers an empty -free list. Thus the sweep phase is very unlikely to touch a page that -would not have been touched shortly thereafter anyway. - -<LI> -<I>Finalization phase</i> Unreachable objects which had been registered -for finalization are enqueued for finalization outside the collector. - -</ol> - -<P> -The remaining sections describe the memory allocation data structures, -and then the last 3 collection phases in more detail. We conclude by -outlining some of the additional features implemented in the collector. - -<H2>Allocation</h2> -The collector includes its own memory allocator. The allocator obtains -memory from the system in a platform-dependent way. Under UNIX, it -uses either <TT>malloc</tt>, <TT>sbrk</tt>, or <TT>mmap</tt>. -<P> -Most static data used by the allocator, as well as that needed by the -rest of the garbage collector is stored inside the -<TT>_GC_arrays</tt> structure. -This allows the garbage collector to easily ignore the collectors own -data structures when it searches for root pointers. Other allocator -and collector internal data structures are allocated dynamically -with <TT>GC_scratch_alloc</tt>. <TT>GC_scratch_alloc</tt> does not -allow for deallocation, and is therefore used only for permanent data -structures. -<P> -The allocator allocates objects of different <I>kinds</i>. -Different kinds are handled somewhat differently by certain parts -of the garbage collector. Certain kinds are scanned for pointers, -others are not. Some may have per-object type descriptors that -determine pointer locations. Or a specific kind may correspond -to one specific object layout. Two built-in kinds are uncollectable. -One (<TT>STUBBORN</tt>) is immutable without special precautions. -In spite of that, it is very likely that most C clients of the -collector currently -use at most two kinds: <TT>NORMAL</tt> and <TT>PTRFREE</tt> objects. -The <A HREF="http://gcc.gnu.org/java">gcj</a> runtime also makes -heavy use of a kind (allocated with GC_gcj_malloc) that stores -type information at a known offset in method tables. -<P> -The collector uses a two level allocator. A large block is defined to -be one larger than half of <TT>HBLKSIZE</tt>, which is a power of 2, -typically on the order of the page size. -<P> -Large block sizes are rounded up to -the next multiple of <TT>HBLKSIZE</tt> and then allocated by -<TT>GC_allochblk</tt>. Recent versions of the collector -use an approximate best fit algorithm by keeping free lists for -several large block sizes. -The actual -implementation of <TT>GC_allochblk</tt> -is significantly complicated by black-listing issues -(see below). -<P> -Small blocks are allocated in chunks of size <TT>HBLKSIZE</tt>. -Each chunk is -dedicated to only one object size and kind. The allocator maintains -separate free lists for each size and kind of object. -<P> -Once a large block is split for use in smaller objects, it can only -be used for objects of that size, unless the collector discovers a completely -empty chunk. Completely empty chunks are restored to the appropriate -large block free list. -<P> -In order to avoid allocating blocks for too many distinct object sizes, -the collector normally does not directly allocate objects of every possible -request size. Instead request are rounded up to one of a smaller number -of allocated sizes, for which free lists are maintained. The exact -allocated sizes are computed on demand, but subject to the constraint -that they increase roughly in geometric progression. Thus objects -requested early in the execution are likely to be allocated with exactly -the requested size, subject to alignment constraints. -See <TT>GC_init_size_map</tt> for details. -<P> -The actual size rounding operation during small object allocation is -implemented as a table lookup in <TT>GC_size_map</tt>. -<P> -Both collector initialization and computation of allocated sizes are -handled carefully so that they do not slow down the small object fast -allocation path. An attempt to allocate before the collector is initialized, -or before the appropriate <TT>GC_size_map</tt> entry is computed, -will take the same path as an allocation attempt with an empty free list. -This results in a call to the slow path code (<TT>GC_generic_malloc_inner</tt>) -which performs the appropriate initialization checks. -<P> -In non-incremental mode, we make a decision about whether to garbage collect -whenever an allocation would otherwise have failed with the current heap size. -If the total amount of allocation since the last collection is less than -the heap size divided by <TT>GC_free_space_divisor</tt>, we try to -expand the heap. Otherwise, we initiate a garbage collection. This ensures -that the amount of garbage collection work per allocated byte remains -constant. -<P> -The above is in fact an oversimplification of the real heap expansion -and GC triggering heuristic, which adjusts slightly for root size -and certain kinds of -fragmentation. In particular: -<UL> -<LI> Programs with a large root set size and -little live heap memory will expand the heap to amortize the cost of -scanning the roots. -<LI> Versions 5.x of the collector actually collect more frequently in -nonincremental mode. The large block allocator usually refuses to split -large heap blocks once the garbage collection threshold is -reached. This often has the effect of collecting well before the -heap fills up, thus reducing fragmentation and working set size at the -expense of GC time. Versions 6.x choose an intermediate strategy depending -on how much large object allocation has taken place in the past. -(If the collector is configured to unmap unused pages, versions 6.x -use the 5.x strategy.) -<LI> In calculating the amount of allocation since the last collection we -give partial credit for objects we expect to be explicitly deallocated. -Even if all objects are explicitly managed, it is often desirable to collect -on rare occasion, since that is our only mechanism for coalescing completely -empty chunks. -</ul> -<P> -It has been suggested that this should be adjusted so that we favor -expansion if the resulting heap still fits into physical memory. -In many cases, that would no doubt help. But it is tricky to do this -in a way that remains robust if multiple application are contending -for a single pool of physical memory. - -<H2>Mark phase</h2> - -At each collection, the collector marks all objects that are -possibly reachable from pointer variables. Since it cannot generally -tell where pointer variables are located, it scans the following -<I>root segments</i> for pointers: -<UL> -<LI>The registers. Depending on the architecture, this may be done using -assembly code, or by calling a <TT>setjmp</tt>-like function which saves -register contents on the stack. -<LI>The stack(s). In the case of a single-threaded application, -on most platforms this -is done by scanning the memory between (an approximation of) the current -stack pointer and <TT>GC_stackbottom</tt>. (For Itanium, the register stack -scanned separately.) The <TT>GC_stackbottom</tt> variable is set in -a highly platform-specific way depending on the appropriate configuration -information in <TT>gcconfig.h</tt>. Note that the currently active -stack needs to be scanned carefully, since callee-save registers of -client code may appear inside collector stack frames, which may -change during the mark process. This is addressed by scanning -some sections of the stack "eagerly", effectively capturing a snapshot -at one point in time. -<LI>Static data region(s). In the simplest case, this is the region -between <TT>DATASTART</tt> and <TT>DATAEND</tt>, as defined in -<TT>gcconfig.h</tt>. However, in most cases, this will also involve -static data regions associated with dynamic libraries. These are -identified by the mostly platform-specific code in <TT>dyn_load.c</tt>. -</ul> -The marker maintains an explicit stack of memory regions that are known -to be accessible, but that have not yet been searched for contained pointers. -Each stack entry contains the starting address of the block to be scanned, -as well as a descriptor of the block. If no layout information is -available for the block, then the descriptor is simply a length. -(For other possibilities, see <TT>gc_mark.h</tt>.) -<P> -At the beginning of the mark phase, all root segments -(as described above) are pushed on the -stack by <TT>GC_push_roots</tt>. (Registers and eagerly processed -stack sections are processed by pushing the referenced objects instead -of the stack section itself.) If <TT>ALL_INTERIOR_PTRS</tt> is not -defined, then stack roots require special treatment. In this case, the -normal marking code ignores interior pointers, but <TT>GC_push_all_stack</tt> -explicitly checks for interior pointers and pushes descriptors for target -objects. -<P> -The marker is structured to allow incremental marking. -Each call to <TT>GC_mark_some</tt> performs a small amount of -work towards marking the heap. -It maintains -explicit state in the form of <TT>GC_mark_state</tt>, which -identifies a particular sub-phase. Some other pieces of state, most -notably the mark stack, identify how much work remains to be done -in each sub-phase. The normal progression of mark states for -a stop-the-world collection is: -<OL> -<LI> <TT>MS_INVALID</tt> indicating that there may be accessible unmarked -objects. In this case <TT>GC_objects_are_marked</tt> will simultaneously -be false, so the mark state is advanced to -<LI> <TT>MS_PUSH_UNCOLLECTABLE</tt> indicating that it suffices to push -uncollectable objects, roots, and then mark everything reachable from them. -<TT>Scan_ptr</tt> is advanced through the heap until all uncollectable -objects are pushed, and objects reachable from them are marked. -At that point, the next call to <TT>GC_mark_some</tt> calls -<TT>GC_push_roots</tt> to push the roots. It the advances the -mark state to -<LI> <TT>MS_ROOTS_PUSHED</tt> asserting that once the mark stack is -empty, all reachable objects are marked. Once in this state, we work -only on emptying the mark stack. Once this is completed, the state -changes to -<LI> <TT>MS_NONE</tt> indicating that reachable objects are marked. -</ol> - -The core mark routine <TT>GC_mark_from</tt>, is called -repeatedly by several of the sub-phases when the mark stack starts to fill -up. It is also called repeatedly in <TT>MS_ROOTS_PUSHED</tt> state -to empty the mark stack. -The routine is designed to only perform a limited amount of marking at -each call, so that it can also be used by the incremental collector. -It is fairly carefully tuned, since it usually consumes a large majority -of the garbage collection time. -<P> -The fact that it perform a only a small amount of work per call also -allows it to be used as the core routine of the parallel marker. In that -case it is normally invoked on thread-private mark stacks instead of the -global mark stack. More details can be found in -<A HREF="scale.html">scale.html</a> -<P> -The marker correctly handles mark stack overflows. Whenever the mark stack -overflows, the mark state is reset to <TT>MS_INVALID</tt>. -Since there are already marked objects in the heap, -this eventually forces a complete -scan of the heap, searching for pointers, during which any unmarked objects -referenced by marked objects are again pushed on the mark stack. This -process is repeated until the mark phase completes without a stack overflow. -Each time the stack overflows, an attempt is made to grow the mark stack. -All pieces of the collector that push regions onto the mark stack have to be -careful to ensure forward progress, even in case of repeated mark stack -overflows. Every mark attempt results in additional marked objects. -<P> -Each mark stack entry is processed by examining all candidate pointers -in the range described by the entry. If the region has no associated -type information, then this typically requires that each 4-byte aligned -quantity (8-byte aligned with 64-bit pointers) be considered a candidate -pointer. -<P> -We determine whether a candidate pointer is actually the address of -a heap block. This is done in the following steps: -<NL> -<LI> The candidate pointer is checked against rough heap bounds. -These heap bounds are maintained such that all actual heap objects -fall between them. In order to facilitate black-listing (see below) -we also include address regions that the heap is likely to expand into. -Most non-pointers fail this initial test. -<LI> The candidate pointer is divided into two pieces; the most significant -bits identify a <TT>HBLKSIZE</tt>-sized page in the address space, and -the least significant bits specify an offset within that page. -(A hardware page may actually consist of multiple such pages. -HBLKSIZE is usually the page size divided by a small power of two.) -<LI> -The page address part of the candidate pointer is looked up in a -<A HREF="tree.html">table</a>. -Each table entry contains either 0, indicating that the page is not part -of the garbage collected heap, a small integer <I>n</i>, indicating -that the page is part of large object, starting at least <I>n</i> pages -back, or a pointer to a descriptor for the page. In the first case, -the candidate pointer i not a true pointer and can be safely ignored. -In the last two cases, we can obtain a descriptor for the page containing -the beginning of the object. -<LI> -The starting address of the referenced object is computed. -The page descriptor contains the size of the object(s) -in that page, the object kind, and the necessary mark bits for those -objects. The size information can be used to map the candidate pointer -to the object starting address. To accelerate this process, the page header -also contains a pointer to a precomputed map of page offsets to displacements -from the beginning of an object. The use of this map avoids a -potentially slow integer remainder operation in computing the object -start address. -<LI> -The mark bit for the target object is checked and set. If the object -was previously unmarked, the object is pushed on the mark stack. -The descriptor is read from the page descriptor. (This is computed -from information <TT>GC_obj_kinds</tt> when the page is first allocated.) -</nl> -<P> -At the end of the mark phase, mark bits for left-over free lists are cleared, -in case a free list was accidentally marked due to a stray pointer. - -<H2>Sweep phase</h2> - -At the end of the mark phase, all blocks in the heap are examined. -Unmarked large objects are immediately returned to the large object free list. -Each small object page is checked to see if all mark bits are clear. -If so, the entire page is returned to the large object free list. -Small object pages containing some reachable object are queued for later -sweeping, unless we determine that the page contains very little free -space, in which case it is not examined further. -<P> -This initial sweep pass touches only block headers, not -the blocks themselves. Thus it does not require significant paging, even -if large sections of the heap are not in physical memory. -<P> -Nonempty small object pages are swept when an allocation attempt -encounters an empty free list for that object size and kind. -Pages for the correct size and kind are repeatedly swept until at -least one empty block is found. Sweeping such a page involves -scanning the mark bit array in the page header, and building a free -list linked through the first words in the objects themselves. -This does involve touching the appropriate data page, but in most cases -it will be touched only just before it is used for allocation. -Hence any paging is essentially unavoidable. -<P> -Except in the case of pointer-free objects, we maintain the invariant -that any object in a small object free list is cleared (except possibly -for the link field). Thus it becomes the burden of the small object -sweep routine to clear objects. This has the advantage that we can -easily recover from accidentally marking a free list, though that could -also be handled by other means. The collector currently spends a fair -amount of time clearing objects, and this approach should probably be -revisited. -<P> -In most configurations, we use specialized sweep routines to handle common -small object sizes. Since we allocate one mark bit per word, it becomes -easier to examine the relevant mark bits if the object size divides -the word length evenly. We also suitably unroll the inner sweep loop -in each case. (It is conceivable that profile-based procedure cloning -in the compiler could make this unnecessary and counterproductive. I -know of no existing compiler to which this applies.) -<P> -The sweeping of small object pages could be avoided completely at the expense -of examining mark bits directly in the allocator. This would probably -be more expensive, since each allocation call would have to reload -a large amount of state (e.g. next object address to be swept, position -in mark bit table) before it could do its work. The current scheme -keeps the allocator simple and allows useful optimizations in the sweeper. - -<H2>Finalization</h2> -Both <TT>GC_register_disappearing_link</tt> and -<TT>GC_register_finalizer</tt> add the request to a corresponding hash -table. The hash table is allocated out of collected memory, but -the reference to the finalizable object is hidden from the collector. -Currently finalization requests are processed non-incrementally at the -end of a mark cycle. -<P> -The collector makes an initial pass over the table of finalizable objects, -pushing the contents of unmarked objects onto the mark stack. -After pushing each object, the marker is invoked to mark all objects -reachable from it. The object itself is not explicitly marked. -This assures that objects on which a finalizer depends are neither -collected nor finalized. -<P> -If in the process of marking from an object the -object itself becomes marked, we have uncovered -a cycle involving the object. This usually results in a warning from the -collector. Such objects are not finalized, since it may be -unsafe to do so. See the more detailed -<A HREF="http://www.hpl.hp.com/personal/Hans_Boehm/gc/finalization.html"> discussion of finalization semantics</a>. -<P> -Any objects remaining unmarked at the end of this process are added to -a queue of objects whose finalizers can be run. Depending on collector -configuration, finalizers are dequeued and run either implicitly during -allocation calls, or explicitly in response to a user request. -(Note that the former is unfortunately both the default and not generally safe. -If finalizers perform synchronization, it may result in deadlocks. -Nontrivial finalizers generally need to perform synchronization, and -thus require a different collector configuration.) -<P> -The collector provides a mechanism for replacing the procedure that is -used to mark through objects. This is used both to provide support for -Java-style unordered finalization, and to ignore certain kinds of cycles, -<I>e.g.</i> those arising from C++ implementations of virtual inheritance. - -<H2>Generational Collection and Dirty Bits</h2> -We basically use the concurrent and generational GC algorithm described in -<A HREF="http://www.hpl.hp.com/personal/Hans_Boehm/gc/papers/pldi91.ps.Z">"Mostly Parallel Garbage Collection"</a>, -by Boehm, Demers, and Shenker. -<P> -The most significant modification is that -the collector always starts running in the allocating thread. -There is no separate garbage collector thread. (If parallel GC is -enabled, helper threads may also be woken up.) -If an allocation attempt either requests a large object, or encounters -an empty small object free list, and notices that there is a collection -in progress, it immediately performs a small amount of marking work -as described above. -<P> -This change was made both because we wanted to easily accommodate -single-threaded environments, and because a separate GC thread requires -very careful control over the scheduler to prevent the mutator from -out-running the collector, and hence provoking unneeded heap growth. -<P> -In incremental mode, the heap is always expanded when we encounter -insufficient space for an allocation. Garbage collection is triggered -whenever we notice that more than -<TT>GC_heap_size</tt>/2 * <TT>GC_free_space_divisor</tt> -bytes of allocation have taken place. -After <TT>GC_full_freq</tt> minor collections a major collection -is started. -<P> -All collections initially run interrupted until a predetermined -amount of time (50 msecs by default) has expired. If this allows -the collection to complete entirely, we can avoid correcting -for data structure modifications during the collection. If it does -not complete, we return control to the mutator, and perform small -amounts of additional GC work during those later allocations that -cannot be satisfied from small object free lists. When marking completes, -the set of modified pages is retrieved, and we mark once again from -marked objects on those pages, this time with the mutator stopped. -<P> -We keep track of modified pages using one of several distinct mechanisms: -<OL> -<LI> -Through explicit mutator cooperation. Currently this requires -the use of <TT>GC_malloc_stubborn</tt>, and is rarely used. -<LI> -(<TT>MPROTECT_VDB</tt>) By write-protecting physical pages and -catching write faults. This is -implemented for many Unix-like systems and for win32. It is not possible -in a few environments. -<LI> -(<TT>PROC_VDB</tt>) By retrieving dirty bit information from /proc. -(Currently only Sun's -Solaris supports this. Though this is considerably cleaner, performance -may actually be better with mprotect and signals.) -<LI> -(<TT>PCR_VDB</tt>) By relying on an external dirty bit implementation, in this -case the one in Xerox PCR. -<LI> -(<TT>DEFAULT_VDB</tt>) By treating all pages as dirty. This is the default if -none of the other techniques is known to be usable, and -<TT>GC_malloc_stubborn</tt> is not used. Practical only for testing, or if -the vast majority of objects use <TT>GC_malloc_stubborn</tt>. -</ol> - -<H2>Black-listing</h2> - -The collector implements <I>black-listing</i> of pages, as described -in -<A HREF="http://www.acm.org/pubs/citations/proceedings/pldi/155090/p197-boehm/"> -Boehm, ``Space Efficient Conservative Collection'', PLDI '93</a>, also available -<A HREF="papers/pldi93.ps.Z">here</a>. -<P> -During the mark phase, the collector tracks ``near misses'', i.e. attempts -to follow a ``pointer'' to just outside the garbage-collected heap, or -to a currently unallocated page inside the heap. Pages that have been -the targets of such near misses are likely to be the targets of -misidentified ``pointers'' in the future. To minimize the future -damage caused by such misidentifications they will be allocated only to -small pointerfree objects. -<P> -The collector understands two different kinds of black-listing. A -page may be black listed for interior pointer references -(<TT>GC_add_to_black_list_stack</tt>), if it was the target of a near -miss from a location that requires interior pointer recognition, -<I>e.g.</i> the stack, or the heap if <TT>GC_all_interior_pointers</tt> -is set. In this case, we also avoid allocating large blocks that include -this page. -<P> -If the near miss came from a source that did not require interior -pointer recognition, it is black-listed with -<TT>GC_add_to_black_list_normal</tt>. -A page black-listed in this way may appear inside a large object, -so long as it is not the first page of a large object. -<P> -The <TT>GC_allochblk</tt> routine respects black-listing when assigning -a block to a particular object kind and size. It occasionally -drops (i.e. allocates and forgets) blocks that are completely black-listed -in order to avoid excessively long large block free lists containing -only unusable blocks. This would otherwise become an issue -if there is low demand for small pointerfree objects. - -<H2>Thread support</h2> -We support several different threading models. Unfortunately Pthreads, -the only reasonably well standardized thread model, supports too narrow -an interface for conservative garbage collection. There appears to be -no completely portable way to allow the collector -to coexist with various Pthreads -implementations. Hence we currently support only the more -common Pthreads implementations. -<P> -In particular, it is very difficult for the collector to stop all other -threads in the system and examine the register contents. This is currently -accomplished with very different mechanisms for some Pthreads -implementations. The Solaris implementation temporarily disables much -of the user-level threads implementation by stopping kernel-level threads -("lwp"s). The Linux/HPUX/OSF1 and Irix implementations sends signals to -individual Pthreads and has them wait in the signal handler. -<P> -The Linux and Irix implementations use -only documented Pthreads calls, but rely on extensions to their semantics. -The Linux implementation <TT>linux_threads.c</tt> relies on only very -mild extensions to the pthreads semantics, and already supports a large number -of other Unix-like pthreads implementations. Our goal is to make this the -only pthread support in the collector. -<P> -(The Irix implementation is separate only for historical reasons and should -clearly be merged. The current Solaris implementation probably performs -better in the uniprocessor case, but does not support thread operations in the -collector. Hence it cannot support the parallel marker.) -<P> -All implementations must -intercept thread creation and a few other thread-specific calls to allow -enumeration of threads and location of thread stacks. This is current -accomplished with <TT># define</tt>'s in <TT>gc.h</tt> -(really <TT>gc_pthread_redirects.h</tt>), or optionally -by using ld's function call wrapping mechanism under Linux. -<P> -Recent versions of the collector support several facilites to enhance -the processor-scalability and thread performance of the collector. -These are discussed in more detail <A HREF="scale.html">here</a>. -<P> -Comments are appreciated. Please send mail to -<A HREF="mailto:boehm@acm.org"><TT>boehm@acm.org</tt></a> or -<A HREF="mailto:Hans.Boehm@hp.com"><TT>Hans.Boehm@hp.com</tt></a> -<P> -This is a modified copy of a page written while the author was at SGI. -The original was <A HREF="http://reality.sgi.com/boehm/gcdescr.html">here</a>. -</body> -</html> |