This is under construction, and may always be.

Conservative GC Algorithmic Overview

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 Paul Wilson's excellent paper. For an overview of the collector interface, see here.

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.

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.

Introduction

1. Preparation Each object has an associated mark bit. Clear all mark bits, indicating that all objects are potentially unreachable.
2. Mark phase 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.
3. Sweep phase 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.
4. Finalization phase Unreachable objects which had been registered for finalization are enqueued for finalization outside the collector.

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.

Allocation

Most static data used by the allocator, as well as that needed by the rest of the garbage collector is stored inside the _GC_arrays 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 GC_scratch_alloc. GC_scratch_alloc does not allow for deallocation, and is therefore used only for permanent data structures.

The allocator allocates objects of different kinds. 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 (STUBBORN) 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: NORMAL and PTRFREE objects. The gcj runtime also makes heavy use of a kind (allocated with GC_gcj_malloc) that stores type information at a known offset in method tables.

The collector uses a two level allocator. A large block is defined to be one larger than half of HBLKSIZE, which is a power of 2, typically on the order of the page size.

Large block sizes are rounded up to the next multiple of HBLKSIZE and then allocated by GC_allochblk. Recent versions of the collector use an approximate best fit algorithm by keeping free lists for several large block sizes. The actual implementation of GC_allochblk is significantly complicated by black-listing issues (see below).

Small blocks are allocated in chunks of size HBLKSIZE. Each chunk is dedicated to only one object size and kind. The allocator maintains separate free lists for each size and kind of object.

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.

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 GC_init_size_map for details.

The actual size rounding operation during small object allocation is implemented as a table lookup in GC_size_map.

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 GC_size_map 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 (GC_generic_malloc_inner) which performs the appropriate initialization checks.

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 GC_free_space_divisor, 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.

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:

• Programs with a large root set size and little live heap memory will expand the heap to amortize the cost of scanning the roots.
• 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.)
• 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.

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.

Mark phase

• The registers. Depending on the architecture, this may be done using assembly code, or by calling a setjmp-like function which saves register contents on the stack.
• 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 GC_stackbottom. (For Itanium, the register stack scanned separately.) The GC_stackbottom variable is set in a highly platform-specific way depending on the appropriate configuration information in gcconfig.h. 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.
• Static data region(s). In the simplest case, this is the region between DATASTART and DATAEND, as defined in gcconfig.h. 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 dyn_load.c.

At the beginning of the mark phase, all root segments (as described above) are pushed on the stack by GC_push_roots. (Registers and eagerly processed stack sections are processed by pushing the referenced objects instead of the stack section itself.) If ALL_INTERIOR_PTRS is not defined, then stack roots require special treatment. In this case, the normal marking code ignores interior pointers, but GC_push_all_stack explicitly checks for interior pointers and pushes descriptors for target objects.

The marker is structured to allow incremental marking. Each call to GC_mark_some performs a small amount of work towards marking the heap. It maintains explicit state in the form of GC_mark_state, 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:

1. MS_INVALID indicating that there may be accessible unmarked objects. In this case GC_objects_are_marked will simultaneously be false, so the mark state is advanced to
2. MS_PUSH_UNCOLLECTABLE indicating that it suffices to push uncollectable objects, roots, and then mark everything reachable from them. Scan_ptr 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 GC_mark_some calls GC_push_roots to push the roots. It the advances the mark state to
3. MS_ROOTS_PUSHED 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
4. MS_NONE indicating that reachable objects are marked.

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 scale.html

The marker correctly handles mark stack overflows. Whenever the mark stack overflows, the mark state is reset to MS_INVALID. 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.

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.

We determine whether a candidate pointer is actually the address of a heap block. This is done in the following steps: