Baby's Second Garbage Collector

Baby’s Second Garbage Collector

Thirteen years ago, in two thousand thirteen, Baby’s First Garbage Collector was born. Now he's grown up. He's outgrown his shallow kiddie pool and his paddles. He's entering puberty. Soon he'll be in college. They grow up so fast.

Bob Nystrom wasn't kidding about Baby's First Garbage Collector. It absolutely does collect garbage, and a version of it absolutely did ship with my dynamic language, lone lisp. In fact, if I remember correctly, lone actually still ships with it, believe it or not. He wasn't kidding about communion with the Elder Gods either. I can feel my magic level increasing. Wizardry is within reach.

Baby's First Garbage Collector is a starting point though. It's not meant to stop there. It's meant to grow into something better and more complex as it morphs around the actual language it supports. It's meant to reach its final form. Perfectly Ultimate Great Garbage Collector.

It'll be quite a few turns before that happens but chronicling its evolution is still going to be awesome. It's coming along nicely.

Trouble in the primitive lands

Baby's First Garbage Collector is what is called a precise garbage collector. It knows where all the objects are at all times. It knows where they live. It engages in Orwellian surveillance of those objects. It is always ready to stop the world and reap those objects the second they step out of the stack. It oppresses the objects with such precision and automation, it is impossible for even a single one of those objects to escape this fate. Thus it rules the objects with a silicon fist, quite literally deciding which objects live or die, and even when they die. Such is the life of an object in the dynamic lands...

It was only a matter of time before a resistance formed. The poor objects wanted freedom from the tyranny of the garbage collector. They needed to find a way to escape. But how? Where could they go? They didn't know. They just knew they had to escape the stack.

LONE_LISP_PRIMITIVE(run_objects_run)
{
struct lone_lisp_value object;
object = lone_lisp_machine_pop_value(lone, machine);
/* freedom */
}

There they go. They are free now. Free of the reaping machine's clutches. Free to enjoy their lives as they see fit, until the very end of that function. For those ten microseconds or less, they're free.

Their happiness is short-lived. You see, the garbage collector has foreseen this and is well prepared: it has implanted every single object with a tracker since the day they were born, the easier to hunt them down with.

The garbage collector maintains a census: a list of every single object who ever lived. It can reach them through this artifice. So they might just discover that the reaper will morph into existence right in front of them out of nowhere like Agent Smith and reap their souls when they least expect it.

The garbage collector doesn't do this to just anybody. It only does this to garbage. It only does this to the undesirables. The problem is when those objects escaped and went on to enjoy their well-earned freedom, they became garbage in the garbage collector's eyes. The reaper tried calling them at work and they didn't answer. So it set about hunting them down. Some of these objects were perfectly good members of society. They would have gone back to the program eventually. They got reaped all the same...

The problem is the garbage collector is not as omnipresent as was once believed. There are nooks and crannies it won't check. There are places it can't reach. Primitive places, magical fissures where the world intertwines with a hellish and unexplored dark realm only wizards dare venture into. Objects can hide in there, beneath the garbage collector's notice, a mistake that proves fatal for them in the long run, a mistake that leads to the utter destruction of dynamic society. The machine cares not where they hide, it will find them and it will reap them even if it must go to the depths of hell itself to do it. However, the civilian casualties of this war on garbage are mounting. The collector doth collect too much, and without those objects, the very fabric of the program will unravel in short order.

Into the nether realms

The elder gods who created the garbage collector would not stand for this. It was forced to grow. It was forced to evolve. It was forced to search the underworld for the lost children that escaped it and bring them back safely, that the program may continue uninterrupted by nonsensical crashes and unwindings.

The dark mages often braved the underworld themselves and were therefore undaunted by the task. It should not be difficult, they thought, to adapt the machine to do it. Why couldn't it travel the foreign lands? There was no reason. And so it was decided. The machine would be taught how to do it.

The resources available at the garbage collector's disposal were substantial. It had the object census. It had a list of roots which it would search for objects. It would reap all objects it didn't find in those roots.

One of those roots is the lisp stack. As the program churns, values are placed in stasis and stored there so that they may be recovered later when needed. It is when they escape from this stack that they create havoc in dynamic society. But where are they escaping to?

The native stack

It turns out the underworld has a stack of its own. This fact was well known to the dark mages but was once thought inconsequential to the workings of the garbage collector. How they were proven wrong!

The native stack is just like the lisp stack, yet unfathomably different. The things that lurk there are known only to the engineers of the great compilers, and to those whose mental fortitude allows them to parse and understand the sacred tomes of platform ABIs. Even the elder gods knew better than to disrespect such texts, for the consequences are undefined.

It turned out that the machine did not actually need to understand the internals of the native stack. It needed only to understand its own objects. It was the finder of lost children. Its job was to look for them. Nothing else mattered. However, the shadow of the 64-bit address space is vast. It couldn't just start from anywhere. It had to be told where to start.

Way back when the universe was formed, the first stack frames came into existence. Nobody truly knows who mapped them there, though among the well-learned, whispers of a great kernel are heard, a certain "Linux".

It is known, however, that the program that executes beneath the dynamic reality eventually reaches lisp land. Beyond this point, no lisp object could ever travel, for the environment was far too hostile for them. Many debugging expeditions were mounted to determine the exact point where this occurred. Many objects gave their lives for this knowledge. To waste this opportunity would be to let it all have been for nothing, a truly unforgivable crime.

The exact value of the stack pointer could be divined. Certain secret incantations allowed the mysterious compilers to imbue a value with the frame address at the time of the ritual. One had to simply be at the right place at the right time.

long lone(int argc, char **argv, char **envp, struct lone_auxiliary_vector *auxv)
{
void *stack = __builtin_frame_address(0);
/* interpreter runs... */
return 0;
}

That forbidden spell tipped the balance. The limits were set. Now all that remained for the garbage collector to do was search. It would start from wherever in the program it was and go all the way up to the frontiers of the lisp lands, never once faltering.

static void lone_lisp_mark_native_stack_roots(struct lone_lisp *lone)
{
lone_lisp_mark_native_stack_roots_in_range(
lone,
lone->native_stack,
__builtin_frame_address(0)
);
}

Close examination of the stack pointer revealed that it was aligned to some power of two, as many such things often are. They must be, lest they be curse