Kestrel Computer Project

Now that I’ve completed substantial amounts of work on the STS V1.5 operating system for the Kestrel-3, I feel emboldened, perhaps foolishly, to document the lessons I’ve learned from the project. From today until Christmas, I’ll be posting at least one lesson learned from working on STS.

Today’s lesson is very brief: the value of garbage collection.

When implementing the filesystem dispatch mechanism in STS V1.5, I ran into a surprising number of double-free bugs. Individually, none were too difficult to debug and fix; but, collectively, it wasted a significant amount of time. Fixing one bug often uncovered another.

In a seemingly unrelated area of experience, during the implementation of getmem and fremem (manual memory management system calls in STS), I spent considerable time tracking down bugs in the heap defragmentation code. Note that both getmem and fremem incrementally defragment free chunks of memory.

Considering I spend maybe four hours a week on Kestrel work, I’m not happy with the level of debugging effort the filesystem required. If I could automate memory management all-together, that would greatly simplify the software using the memory allocator, while simultaneously simplifying the implementation of the allocator as well. Less code means fewer bugs, and that means more time to spend with my wife.

Lesson Learned

If your project deals with a potentially complex web of related entities, you should consider using garbage collection for those entities. Even if nothing else in your project relies on GC, you can at least be confident that your web of entities will never have stray pointers which can be double-freed.

In particular, I recommend a Cheney-style collector. It’s a semi-space, compacting collector which should be plenty sufficient for nearly anything you throw at it. It’s also pretty trivial to write from scratch. My experiments with this collector suggests you can implement one in only half the amount of code needed to write a manual memory manager.

So, not only would it help eliminate the possibility of screwing up your entity relationships, but it actually uses less code in the process.

The only two disadvantages I can think of are that a naive implementation requires double the amount of RAM you expect to maximally allocate, and that a naive implemention cannot gaurantee real-time performance. However, if you keep your pools small and focused, the total pool size(s) should be small enough to ameliorate these effects.

For example, with STS, I could maintain a managed memory pool just for the in-core filesystem layout, relying on manual memory management for other aspects of the system.

Besides, if you’re opening files by walking name by name in a mount hierarchy, you’ve already destroyed any hope for real-time performance anyway.

Alas, I don’t have time to expound on what a Cheney algorithm implementation looks like now; I will need to make a separate blog article about that some day. If I forget, someone remind me!