Garbage Collection

Almost all modern programming languages of any consequence provide some variant of the nodes-and-pointers family of data structures, either implicitly or explicitly.

Efficiency-oriented languages such as C tend to be satisfied with providing something like malloc()/free(), but since the mid-60s at the latest, it has been normal for programmer-friendly languages to provide additional help in managing these data structures: Once such data structures reach a moderate level of complexity, manually keeping track of which nodes are no longer in use and can safely be free()d becomes a formidable and error-prone task, as witness the recurring problems with memory leaks in netservers and netclients alike.

The solution is to provide a "garbage collector": A program which automatically detects nodes which are no longer accessable to the program and can therefore safely be free()d.

The study of garbage collection algorithms is an interesting and active subfield of computer science, full of surprising ideas. For example, for some sorts of programs, an appropriate garbage collector can be faster than conventional stack-based allocation, because conventional stackbased allocation requires a minimum of one machine instruction in order to free each allocated block, while an efficient copying garbage collector can avoid touching free blocks altogether ... !

I am aware of three basic garbage collector designs:

• Classic mark-and-sweep garbage collectors which
  1. Set a FREE flag on every existing object;
  2. Recursively this flag on all reachable objects;
  3. free() all objects with the FREE flag still set.
• Copying garbage collectors, which copy all accessable objects out of a memory block, then simply free() the entire memory block;
• Reference counting, which keeps in each object a count of the number of pointers pointing to the object. When this drops to zero, the object can be free()d.

Each design approach has significant disadvantages:

• Mark-and-sweep garbage collectors tend to unexpectedly stop the program dead for a long time while they run -- bad for interactive applications and *extremely* bad for realtime applications such as flight control -- and they don't compact live objects into a single area, so the free space may be left in tiny fragments too small to be useful, even when 'successfully' free()d.
• Copying garbage collectors likewise tend to stop the system dead for awhile, and require enough spare space to construct a complete second copy of the program's datastructures.
• Reference counting is done incrementally every time a pointer is assigned, which inherently avoids big garbage collection pauses, but this scatters the overhead and code all through the interpreter, and they can't free() two nodes pointing to each other, even if there is no way for the program to ever access the node-pair.

After sleeping on the problem a few weeks, I think the copying garbage collector designs are the most natural to use in the Muq context: Muq needs to routinely make complete backups of the database anyhow and copying garbage collection can be piggybacked on this process at negligible performance cost and quite moderate coding cost.

The resulting code should be very nicely localized, making it simple and reliable. The standard copying garbage collector "disadvantage" of requiring space for two copies of the database is actually an asset in this situation, since we *want* to make backups.

We could argue that the remaining disadvantage of copying garbage collectors -- stopping the system dead for significant periods -- is in a sense not a disadvantage here, since we are already stopping the system dead for backup anyhow. I would prefer, however, to avoid having backup or garbage collection wreck interactive response, by having both done incrementally in the background, while the server continues to run.

For me, at least, the basic design decision required to implement this is quite simple since (other than reference counting, and the generation-based schemes if one wishes to consider them incremental?!) the only incremental garbage collection technique I'm aware of offhand is Djikstra's three-color algorithm. In this algorithm, at any given time, every object is either Black, Grey or White.

Black designates objects which may or may not be reachable, until we finish enumerating all reachable objects, at which point it designates garbage objects.

White designates objects which are known to be reachable, and which don't point to any Black objects.

All other objects are Grey.

Conceptually, the algorithm is very simple. All objects start out Black. We radiate a Grey wave out from the 'root' pointers defining objects immediately accessable to the program, following all pointers in the objects, by successively arbitrarily picking any Grey object O, coloring Grey all Black objects reachable from O, and then coloring O White. We stop when no more Grey objects remain, at which point all Black objects can be free()d. In effect, the Grey objects constitute a queue of work remaining to be done by the garbage collector on this pass.

The nice thing about this algorithm -- Djikstra's main design goal for it, I believe -- is that it adapts very nicely to being executed incrementally while the interpreter continues to run: All we need do is keep the interpreter operating only on White objects (Footnote 1). This may be achieved simply by stopping the interpreter whenever it reaches a Grey object O (it can't reach a Black object), processing O as our next incremental garbage collection step (since the algorithm doesn't care what order Grey objects are processed in, this is simple) and then continuing, O now being a standard White object.

Adapting this idea to vm.c, our idea is to have the mud keep running while in the background we copy our complete database from the existing 'old' fileset to a duplicate 'new' fileset. We start this process by flushing all dirty objects to disk, giving us a self-consistent 'old' db on disk; This is the last time we shall ever write to the old db. Thereafter, all dirty objects will be written to the 'new' fileset, and in addition we will incrementally copy all reachable objects from 'old' to 'new' fileset. When this copying process is complete, vm closes all files in the 'old' db and forgets all about it thereafter.

In a 'bit' more detail, while the incremental copying/garbage collection phase is under way, we have two complete filesets open, each with its own allocation bitmap per file. When objects are copied, their Vm_Obj pointer isn't changed: An object that was octave 5 offset 1366 in the 'old' fileset will be copied to octave 5 offset 1366 in the 'new' fileset.

Thus, during copying we have available two bits per object instead of one, one bit in the bitmap for the object in each fileset. (Note that we do not need to keep intact the memory bitmap for the 'old' fileset -- this bitmap was written to disk when we did the initial flush of all dirty objects to create a self-consistent image in 'old'.)

By a splendid coincidence, these two bits give us exactly enough states to label each object as Black, Grey, White or Free. Immediately after flushing dirty objects to 'old' and creating a 'new' fileset with (it being initially empty) all-zero bitmaps, all objects will be either Black or Free, indicated by a 0 in the 'new' bitmap and either '0' or '1' in the 'old' bitmap.

At this point, we color Grey all objects immediately accessable by the interpreter, by setting '1' on them in the 'new' bitmap. We then run the garbage collector until there are no Grey objects left in ram. (Assuming a moderate size ram buffer, this should run quickly enough to not create an objectionable pause, no disk I/O being involved.)

The point of this is that the interpreter cannot now access any Grey (or, of course, Black) object without reading from disk, which means in turn that we don't need to insert any extra garbage collection code in the fast handle-an-object-in-ram code, only in the read-an-object-from-disk code, which is so slow as to make any slowdown from our additional code completely negligible.

Note that there may well be Black objects in ram, especially initially. This poses no problem. These are simply objects which the interpreter either cannot reach at all, or can reach only via pointers which are currently on disk.

We implement White with a '0' in the 'old' bitmap and a '1' in the new, indicating that the object is now stored in the 'new' fileset when written.

Having performed the initial flush to disk followed by Whiting (Footnote 2) of all Grey objects in ram, we simply let the interpreter proceed on its merry way. Periodically --- when the interpreter is idle, every Nth instruction or object create, or whatever -- we White a few more Grey nodes, a small enough number so as not to pause the interpreter objectionably, and of course we White every Grey object which the interpreter tries to read from disk.

Since Grey objects by (our) definition live in the 'old' fileset, and since White objects (when not in ram) are saved in the 'new' fileset, this process of coloring will also automatically copy objects steadily from the 'old' fileset to the 'new' fileset.

When we run out of Grey objects, the interpreter is running completely out of the 'new' fileset, the 'old' fileset is a stable self-consistent backup which may be safely backed up by the system backup utility etc (unlike the active fileset, which at any given instant is unlikely to be self-consistent on disk, much less self-consistent on disk over the time taken to back up its component files), all objects which were garbage at the start of the garbage collect are Free in the 'new' fileset, and the system should have exhibited no objectionable pauses.

---------------------------------------------------------

Footnote 1:

Note that if we do not keep the interpreter operating only on White objects, we may easily wind up free()ing an object we should not: the interpreter can copy a pointer to a Black object B from a Grey object G to a White object W and then erase the original pointer in G, which can keep the garbage collector from ever coloring B White or Grey, even though B remains accessable to the program via the pointer in W. The garbage collector will thus wind up free()ing a node (B) in use by the program, a very definite no-no.

Footnote 2:

If it is not obvious, I define 'to White' as the process of coloring Grey all Black objects pointed to by a given Grey object O, followed by coloring O White.

NOTE: The above is not yet implemented. Muq currently uses a simple interim mark-and-sweep garbage collector. Furthermore, my ideas have evolved somewhat over the last two years. See comments at top of `vm.c' if interested.

Go to the first, previous, next, last section, table of contents.