boehm-gc/doc/gcdescr.html - gcc - Git at Google

 <HTML>
 <HEAD>
     <TITLE> Conservative GC Algorithmic Overview </TITLE>
     <AUTHOR> Hans-J. Boehm, Silicon Graphics</author>
 </HEAD>
 <BODY>
 <H1> <I>This is under construction</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:

 <OL>

 <LI>
 <I>Preparation</i> 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.  Normally 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
 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 applications currently
 use at most two kinds: <TT>NORMAL</tt> and <TT>PTRFREE</tt> objects.
 <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>.  This uses roughly what Paul Wilson has termed
 a "next fit" algorithm, i.e. first-fit with a rotating pointer.
 The implementation does check for a better fitting immediately
 adjacent block, which gives it somewhat better fragmentation characteristics.
 I'm now convinced it should use a best fit algorithm.  The actual
 implementation of <TT>GC_allochblk</tt>
 is significantly complicated by black-listing issues
 (see below).
 <P>
 Small blocks are allocated in blocks of size <TT>HBLKSIZE</tt>.
 Each block is
 dedicated to only one object size and kind.  The allocator maintains
 separate free lists for each size and kind of object.
 <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 fat an oversimplification of the real heap expansion
 heuristic, which adjusts slightly for root size and certain kinds of
 fragmentation.  In particular, programs with a large root set size and
 little live heap memory will expand the heap to amortize the cost of
 scanning the roots.
 <P>
 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.  6.x will chose 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
 will use the 5.x strategy.)
 <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>

 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 are pushed on the
 stack by <TT>GC_push_roots</tt>.  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_mark_stack</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 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.
 <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="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.
 <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 parallel and generational GC algorithm described in
 <A HREF="papers/pldi91.ps.gz">"Mostly Parallel Garbage Collection"</a>,
 by Boehm, Demers, and Shenker.
 <P>
 The most significant modification is that
 the collector always runs in the allocating thread.
 There is no separate garbage collector thread.
 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 three distinct mechanisms:
 <OL>
 <LI>
 Through explicit mutator cooperation.  Currently this requires
 the use of <TT>GC_malloc_stubborn</tt>.
 <LI>
 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>
 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.)
 </ol>

 <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 portable way to allow the collector to coexist with various Pthreads
 implementations.  Hence we currently support only a few of 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 different Pthreads
 implementations.  The Solaris implementation temporarily disables much
 of the user-level threads implementation by stopping kernel-level threads
 ("lwp"s).  The Irix implementation sends signals to individual Pthreads
 and has them wait in the signal handler.  The Linux implementation
 is similar in spirit to the Irix one.
 <P>
 The Irix implementation uses
 only documented Pthreads calls, but relies on extensions to their semantics,
 notably the use of mutexes and condition variables from signal
 handlers.  The Linux implementation should be far closer to
 portable, though impirically it is not completely portable.
 <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>, or optionally
 by using ld's function call wrapping mechanism under Linux.
 <P>
 Comments are appreciated.  Please send mail to
 <A HREF="mailto:boehm@acm.org"><TT>boehm@acm.org</tt></a>
 </body>