Bluejay Lisp progress – GC improvements

After a nearly year-long break from working on Bluejay, I finally got back to working on the Lisp compiler. The big news is that I finally got the garbage collector fully working. One of the cool parts of the GC is that it works with both C and Lisp functions sharing stack space — so a Lisp function can call a C function, which calls a Lisp function, which calls (gc), and everything will work correctly. The C function can even define which references it retains!

How the garbage collector works

When (gc) is called (or when it is invoked automatically), it inspects the stack for all Lisp values currently in use. When it finds a value, it marks it as referenced. If the value is something like a cons cell, it recursively marks the values it references. At the end of the marking process, all the referenced values are marked as such, and everything unmarked is known to be unreferenced. Finally, the GC “sweeps” the garbage by looking through all the allocations and freeing any that aren’t marked (i.e. aren’t referenced anywhere).

Walking the stack

This is the general layout of the stack in a Lisp function. The stack grows towards lower memory on x86, so the top of the stack is shown at the bottom. The ESP register points to the item on the top of the stack.

The GC knows that everything in the current “stack frame” — the memory range [ESP, EBP) — is a Lisp value to be marked. Once it gets to the end of the stack frame, EBP, it reads the old EBP value off the stack, skips over the return pointer (the address to jump back to after this function finishes, used by RET), and repeats the process for the function one up the call stack.

The problem

The difficulty occurs when you have C and Lisp functions sharing stack space. Some of the values stored on the stack in a C function won’t be Lisp values, so trying to mark them will lead to garbage data. E.g. if the C function has a variable int a = 0x101, the GC would interpret it as a reference to a cons cell, even though none exists at that address — leading to a memory error.

The solution is something I’ve called “GC segments.” The way it works is any C function that might invoke the GC during its runtime (for example, a C function which allocates memory or calls a Lisp function) needs to specify a GC segment. The segment defines the region of stack space that the function uses, so that the garbage collector can skip over it. It also allows the C programmer to define some Lisp values that are referenced by the function, so that they don’t get accidentally garbage collected.

The API looks like this:

value_t callable_from_lisp(value_t a, value_t b)
{
	// address of last argument, number of retained Lisp values
	gc_push_segment(&b, 2);

	// Tell the GC that these values are referenced and should not be
	// cleaned up
	gc_set_retained(0, a);
	gc_set_retained(1, b);

	// ...

	// Before calling a Lisp function:
	// 0 = num args
	gc_prepare_call(0);
	some_lisp_function();

	gc_pop_segment();
	return nil;
}

When the GC walks the stack now, if it encounters a C segment, it marks the retained values moves on to the callers stack frame.

This ends up working quite nicely in practice. Functions like (eval) which are implemented in C and have some local Lisp variables can easily define them, and the garbage collector works everywhere. In theory you could even just write plain C code using the Lisp data structures and the full garbage collector, although you have to manually declare all your Lisp object locals.

I wrote a simple test program to test that the garbage collector cleans up everything it should and nothing it shouldn’t, and it works without issue:

(defun test-gc-eval ()
  (eval '(progn
          (list "hello" "world")
          (gc))))

(defun main ()
  ;; Allocate some garbage
  (let1 (used "this should NOT be freed")
	    (list 1 2 3 4)
        (list "this" "is" "a" "list")
        (gc)
        (print (list "Current allocations" "GC runs"))
        (print (gc-stats)))
  (print "testing gc in eval")
  (test-gc-eval))

As expected, the GC frees all the temporary lists, but not the string used since it’s retained in the let1. It also doesn’t crash when called within (eval) because of the new segment system.

Future work

Currently the garbage collector uses a simple mark-and-sweep algorithm, with all allocations living in one big “bucket.” The marking process is unavoidable in any garbage collector, but the sweeping can be optimized. Once there are many thousands of allocations, walking each every GC run is time consuming, and there are simple ways of minimizing the workload.

One option is what’s called a generational garbage collector. It is based on the observation that objects that have already lived a long time will probably live longer, and therefore can be swept less frequently. The way it works is you have several generations which allocations can be members of (Microsoft .NET uses 3 for example), and all allocations start in generation 0. If an allocation survives a sweep if its generation, it moves up to the next generation. Each generation is only swept once its allocations total to a certain size in memory. Thus short lived objects will quickly be swept, while longer lived ones will be swept less frequently as they move up generations.

This should be simple enough to implement, and might decrease total garbage collector runtime, especially for long-running programs.

With that said, the present system works well enough for simple programs, and I’m really thrilled to finally have a compiler that’s becoming usable. The only real remaining steps are user-defined types, generic methods, and a complete standard library.