Rewriting Memory Management in xv6

xv6 is deliberately simple. Its physical page allocator is a free list, its kalloc pops from the head, and its kfree pushes back. This is exactly right for teaching and exactly wrong for understanding what a real allocator has to worry about.

So I replaced it, mostly to find out what the simplicity was costing.

What changed

The free list was fine until allocation and deallocation stopped being balanced. Under a workload that allocated in bursts and freed in a different order, the list would fragment in ways that never showed up in the standard test suite, because the standard test suite is not trying to be adversarial.

The rewrite added tracking that let the allocator make a decision rather than just taking whatever was at the front, plus enough instrumentation to see what the kernel’s memory actually looked like over time instead of guessing.

What I learned that I did not expect

Most of the difficulty was not the algorithm. It was that in kernel space you cannot use any of the tools you would normally reach for. There is no allocator to help you debug the allocator. Printing is expensive and changes the timing of the thing you are trying to observe. Every assumption has to be checked with code you also wrote.

That constraint is the actual lesson of an operating systems course, and it does not survive being described. You have to sit in it.

Status

Archived. It did what it was for. The code is on GitHub if you want to see a teaching kernel with a slightly more opinionated memory manager bolted into it.