GC - Garbage Collector

Δ Overview

This project is a simple Garbage Collector (GC) for C programs running on 64-bit systems. Just like the famous Boehm collector, our GC is conservative, where the collector assumes that all bit patterns resembling pointers are indeed pointers. C programmers can replace calls to malloc() with the corresponding call to gc_malloc() and remove all calls to free() (and any deallocation logic) altogether. Unlike the Boehm collector, our GC design and implementation is very simple. The entire collector fits into a single file gc.c and is around ~1300 lines of code. The simplicity of the design leads to a richer memory API, which enables some interesting new applications...

Δ Implementation Details

Our GC design is based on overcommit memory. The basic idea is as follows: when a program allocates a large chunk of memory from the OS, the OS need not ensure there is enough physical memory to satisfy the request. Instead, the OS reserves a suitably sized chunk of the virtual address space and returns a pointer to the start of the chunk. Only when the process starts using the memory (i.e. reading/writing, etc.) does the OS associate allocate physical pages to the virtual addresses. As a consequence of this design, it is actually possible to "allocate" much more memory that is physically available (including swap).

The design of our GC takes advantage of this. When the program starts, the GC "allocates" (via mmap) a HUGE chunk of memory from the OS. The current implementation currently requests 4096GB (!) of memory up front. This is possible on 64-bit systems where the virtual address space is big enough to accommodate such requests. (This trick does not work on 32-bit systems -- where the maximum virtual address space size of 4GB is too small.)

Once allocated, the memory chuck is subdivided into smaller chunks (a.k.a. "buckets"), where each bucket handles allocation of a specific size range. The allocation algorithm for each bucket is very simple: either allocate from a "free-list" (if available from a previous collection), or simply allocate fresh space from the appropriate bucket by incrementing a pointer. Usually only a tiny fraction of the reserved 4096GB is ever touched, corresponding to the actual memory usage of the program.

Δ API Overview

The GC API comes with (the GC versions of) standard allocation functions:

  • GC_malloc(size), GC_free(ptr) (optional), and GC_realloc(ptr, size).
Like most GC implementations, a garbage collection may be explicitly forced:
  • GC_collect()
Thanks to the simplicity of the GC's design, we can efficiently (O(1)) map GC-allocated pointers to the size of the allocation (to some approximation):
  • GC_size(ptr)
Likewise, we can efficiently map (O(1)) an interior pointer to the base (a.k.a. exterior) pointer of a GC allocated object:
  • GC_base(ptr)
This operation is basic pointer arithmetic: base + ((ptr - base) / size) * size where size = GC_size(ptr) and base is the base address of the bucket from which ptr was allocated.

Δ Caveats

There are some caveats that should be considered before using this GC.

  • Only 64-bit CPUs are supported. This is a fundamental limitation of this kind of GC.
  • The collector is not (yet) a drop-in replacement for the Boehm collector. Specifically our collector requires explicit initialization (including initialization for each thread). Our collector does not automatically scan global variable memory, nor malloc'ed memory unless the memory is explicitly declared as a root pointer (see GC_root() and GC_dynamic_root()). (This is partly why our collector implementation is a lot smaller than the Boehm collector.)
  • The maximum allocation size is 255MB.
  • No support for "atomic" memory allocation.
  • No multi-threaded support.
We hope to fix some of these issues in future releases.

Δ Download

Currently the GC (and sample programs) are released under the terms of the GNU General Public License v3:

Δ Related Work

The memory allocation algorithm (described above) forms the basis of our work on program hardening with low fat pointers. The basic idea is to use the efficient size and base operations (GC_size/GC_base) to lookup object bounds meta information at runtime. This bounds meta information can then be used to check for object bounds errors such as buffer overflows. This work has resulted in two publications so far:

Note that the implementation evaluated by these papers is different from the current GC code.

© Copyright 2017, all rights reserved