gcdescr.html

A garbage collector for C and C

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:[e-mail]"><TT>[e-mail]</tt></a> or
<A HREF="mailto:[e-mail]"><TT>[e-mail]</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>