Before I got distracted by the tail recursion brouhaha, I was writing about some Lisp machine esoterica. I want to describe how the LMI Lambda does garbage collection. The Lisp machine had the first commercial generational garbage collector. The implementation was fairly straightforward, but it had some features that I haven't seen in other garbage collectors. There is nothing special that would prevent these from being implemented in another GC, it just seems that no one does it.

To understand the Lambda garbage collector, you have to know a bit about the memory system. Memory in the Lambda is contained in ‘regions’. A region is a contiguous chunk of virtual address space that is aligned on a 64-page block boundary and contains an integral number of 64-page blocks. The reason for the alignment and size restrictions is because the memory mapping hardware uses the top 12 bits of the virtual address (bits [24:13] inclusive) as an index into the level one memory map. There are usually several regions in use at any time.

Every region has a free-pointer. Addresses within the region, but below the free-pointer are in use, addresses within the region but equal to or greater than the free-pointer are not in use.

Now let me digress a little. Assuming you're not using one of those broken reference-count hacks that don't actually work, the standard garbage collection model you see everywhere is this:

1. Garbage collection is triggered when you run out of memory.
2. The garbage collector starts with a root set of objects, then either
   • recursively walks the tree of objects marking the ones in use.
   • scans the root set and relocates objects in use to a new place in memory.
3. Step 2 continues until the transitive closure of objects is marked or moved.
4. The collector frees the memory that is no longer in use (the coset of the memory in use).
5. Some or all of the freed memory is now available for allocation. In particular, the allocation that triggered the garbage collection can now proceed.

The Lisp machine model of garbage collection is a bit different. Here's how I would characterize it:

1. The fundamental unit of allocation and deallocation for the memory system is the region.
2. To allocate an object within a region, you check the free pointer to determine if there is sufficient remaining room.
   • If there is room, you simply move the free pointer and initialize the storage.
   • If the region is full, you look for a different appropriate region. (Some regions are reserved for different uses.) If you find one, allocate there.
   • If there are no appropriate regions with room, you request the creation a new region from the memory system.
   • If this succeeds, you begin allocation within this new region.
   • If this fails, then you are out of memory and the machine halts. (An error is signalled before you are absolutely out of memory, so you won't be suddenly surprised, but if you continue to ignore the error and not release any storage at all, the machine will eventually halt because it is unable to fulfill your request.)
3. The garbage collector works by freeing entire regions of memory. The basic plan is this:
   • select one or more of the allocated regions and mark them as ‘condemned’. No new objects can be allocated there.
   • Evacuate (relocate) the live objects from the condemned regions.
   • When there are no more live objects in the region, return the region to the memory system.
   
   The garbage collector runs as a separate process on par with the other processes. Its job is to free memory and return it to the operating system. It monitors memory usage and initiates a garbage collection cycle when it determines that memory needs to be freed. The decision when to initiate garbage collection is based on the current rate of allocation, the estimated rate of recovery, the estimated machine resources used during collection, and user parameters.
   
   In other words, allocation is decoupled from garbage collection. The decision of when (or even if) to garbage collect is not made by the allocator. You can turn the garbage collector off at any time, or turn it back on at any time. Of course you run the risk of running out of memory if you leave it off for too long.

Next: Oldspace and the transporter