Description

Having implemented several simple lisp interpreters I got tired of reimplementing the garbage collector every time. This is the first attempt at a generic garbage collector that can be reused in different software projects. The garbage collector itself is nothing fancy, as it employs the mark-and-sweep algorithm and stops the execution of the program while collecting garbage.

The primary goals were:

• to keep it really simple to implement: a mark-and-sweep garbage collector seemed simple for me to implement, thanks to Peter Michaux’s great explanation of the theory
• to keep it simple to use: the garbage collector is non-invasive, i.e. it works with any objects/structs that already exist, without having to modify them in any way

Portability

The garbage collector has only been tested on an i686 architecture. Since the garbage collector uses no fancy pointer tricks it should work without problems also on other architectures.

Correctness

Running the provided example program with valgrind (v. 3.7.0) produces neither errors nor memory leaks.

Implementation

A good explanation of how mark-and-sweep garbage collectors work can be found here.

This garbage collector allocates all necessary memory for managing that object plus the memory required for an object at once. The address returned however is only that of the object, excluding the management information.

The root set and list of protected memory locations are stored in linked lists. Node for that list are malloc’d normally, but put onto a separated list when not needed anymore. When creating a new node, the garbage collector first tries to get a new node from that list and only mallocs a new one if that fails.

In order to keep the interface clean and tidy, the size of the managed objects is associated with a single garbage collector instance. As a consequence it is necessary to create a new garbage collector instance for each memory size requested. Since the typical use case consists of requesting structures of a fixed size, only a handful of garbage collectors is necessary.

Usage

The garbage collector can manage only objects of a fixed size. If it is necessary to manage objects of different sizes, several garbage collectors can be instantiated.

The basic series of steps is:

1. Instantiate a garbage collector
2. Request objects from the garbage collector
3. (optional) Increase the amount of objects the garbage collector manages
4. (optional) Add objects to the root set of the garbage collector. These objects will never be reclaimed by the collector.
5. (optional) Protect an object found at a specific memory location from being reclaimed.
6. (optional) Expose memory locations from step 5 to the garbage collector. Objects at that location can be reclaimed then.
7. Free the garbage collector and destroy all objects the collector manages.

Each step corresponds to one function in the simple-gc API:

1. gc_create instantiates a garbage collector that manages nobjects of size size. Whenever an object is marked, collected or destroyed the function on_mark, on_collect or on_destroy is called with that object as an argument
2. gc_alloc requests a single object from the garbage collector. If there are no more free objects available, the garbage collector tries to collect unused objects. If there are still no objects available after doing so, the function returns NULL, otherwise it returns a valid pointer to an object
3. gc_add increases the amount of objects the garbage collector manages by nobjects
4. gc_root adds an object to the root set. An object can be removed with a call to gc_unroot
5. gc_protect protects objects found at a specific memory location. This function is mostly useful when allocating objects within a function
6. gc_expose exposes the n most recently protected memory locations to the garbage collector
7. gc_free destroys a garbage collector and all objects managed by it. The pointer to the garbage collector is set to NULL afterwards

Additionally there are functions that usually don’t need to be called directly:

• gc_collect tries to reclaim objects that are neither protected nor reachable through the root set. This function is automatically called when there are no more free objects available to the garbage collector
• gc_mark marks an object to be not reclaimable. This function needs to be used when creating objects that reference other objects. If cont is given, that function is called with the marked object as an argument.

License and Copyright

Copyright (c) 2012, Dario Hamidi <dario.hamidi@gmail.com> All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

• Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
• Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
• Neither the name of the author nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS “AS IS” AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL DARIO HAMIDI BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.