27 Sep 2025 — 9 minute read
On today’s episode of developing Kiwi, I want to take a good amount of time to talk about the memory manager.
To recap, the memory manager is one of the core components of an OS kernel. Like the name implies, it is responsible for allocating and managing memory, and can be broken down into a physical memory manager, virtual memory manager, and a heap (i.e., malloc() and company, which are typically re-implemented separately in the user space.)
Today, I want to focus on the physical memory manager. Physical memory in practically all architectures is broken up into chunks called frames (or pages), where one physical frame corresponds to one virtual page, which is usually 4 KB.
To briefly touch down on the idea of a physical memory manager, here’s a high-level breakdown of our most basic functional requirements:
As is probably obvious by now, the memory manager is one of the most critical components in a kernel. Performance shortcomings here will really resonate throughout the system, and so efficiency is just as important as correctness. For that reason, I want to start by talking about how these requirements were met in my older project, before moving on to how I’ve improved them on Kiwi.
I think it’s fair and appropriate to use this moment to emphasize that even though there are countless reasons why Kiwi is a rewrite of luxOS, if I had to boil down those reasons into just two top reasons, the memory manager would make the cut. So let’s just get straight into it.
The physical memory manager on luxOS essentially had a flat bitmap, with one bit for every frame. If we were to imagine a system with 8 GB of RAM and 4 KB frames (i.e., roughly 2 million frames), we would have a bitmap that’s two million bits long (little under 250 KB of memory overhead.)
To allocate memory using that structure, we needed to linearly iterate through all the bits one by one until we found a zero bit (i.e., a free frame), and then we’d flip the bit to one and return its corresponding physical address. This is obviously a bad idea for many reasons. In the worst-case scenario with 8 GB of RAM where memory utilization is near 100%, we may require up to two million bit-checks! Clearly not my proudest moment and I’m honestly not even going to try to justify that choice. Only God knows what I was thinking at the time.
On top of the linear complexity issue, the synchronization problem (the third requirement) was another disaster of its own. Multiple cores would compete to allocate memory, so I needed a way to guarantee atomicity. This was addressed by guarding the entire bitmap with a single spinlock; a thread wanting to allocate memory would have to spin and block until it eventually won the race. The memory manager is one of the two most frequently run pieces of code in an OS, as contention for memory is realistically always high. This contention is inevitable, but managing it efficiently is not just possible, but also surprisingly practical.
Using these design and implementation shortcomings as a direct source of inspiration, I want to pivot to how I’m addressing these shortcomings on Kiwi. We have a clean slate this time and we can completely start over, which is exactly what we’re doing.
To address the first two requirements, I am now using a hierarchical bitmap instead of a flat bitmap. We can build one by applying a fanout factor N, so that each bit in a layer of the hierarchy corresponds to N bits of the layer below, and where the lowest layer is the linear bitmap where each bit corresponds to one physical frame. A bit in any layer above the lowest layer is only set to one when all the underlying frames are marked as used (i.e., there are no free frames in any “leaves” of that subtree.) We then impose the constraint that the highest layer of the hierarchy cannot be larger than N bits in length.
That’s a lot of words, and so to illustrate all this jargon, let’s reuse the 8 GB (2 million frames, each 4 KB) example from earlier and consider a fanout factor of N=64, which is the default fanout factor on Kiwi because it fits neatly in a 64-bit machine word. This resulting hierarchy would have 4 layers.
The lowest layer will have the 2 million bits, where each bit maps to one frame. This length is greater than 64, and so we condense it into a new layer above. This new layer will contain 2 million divided by 64 bits, which gives us 31,250 bits. Each bit in this layer now corresponds to 64 bits in the layer below, or 64 frames (256 KB). We can now read the summary of 64 frames using only one bit-check.
But we aren’t done, because our topmost layer now contains 31,250 bits which is still larger than 64, so we recursively repeat this process, giving us a layer with 489 bits, which is still larger than 64, so we recursively repeat this process one more time, until 489/64 rounds up to 8. Now, our topmost layer contains 8 bits (which satisfies the constraint of being less than 64) and we stop recursing. Each bit in this topmost layer corresponds to 643 or 262144 frames, or 1 GB of memory. We can now read the summary of an entire gigabyte using just one bit-check!
The idea here is that when allocating memory, we can read the summaries of the topmost layers first, and we only walk down the hierarchy when we know ahead of time that we will find a free frame in that subtree, completely minimizing the redundant checks of memory that is already utilized.
The obvious advantage of this approach is in its scalability. No matter how much memory we have, the fanout factor remains constant, and so we are bounded only by the height of the tree, letting us allocate memory in logarithmic time.
To make this more tangible, let’s imagine the same scenario from earlier, where we had near 100% memory utilization on an 8 GB RAM system. The old allocator would require potentially two million bit-checks to allocate a frame, while the new allocator can do the same task using no more than just 200 bit-checks (up to 8 bits of the topmost layer, followed by up to 64 bits for each of the underlying 3 layers), which is a theoretical improvement of one million percent, or 10,000 times fewer bit-checks.
In fact, this approach scales so well that even if we took the same example and increased the memory size to an absurd terabyte of RAM, the worst-case total number of bit-checks to allocate a block would still only be 272. That’s 128 times as much RAM for just 72 extra bit-checks!
To address the third requirement, we need to keep a few caveats in mind:
These caveats imply that we need a graceful way to handle contention, and that we need to be able to recover from failed allocations. It is relatively easy to avoid this problem entirely by implementing several functions when I get to multi-core support:
For the sake of correctness and sanity, it is also very important to only have a single source of truth when allocating memory. A frame is only considered to be allocated if an atomic bit-set operation at the leaf level succeeds. Parent summaries are advisory and may lag behind and thus are only eventually consistent. This means that while the allocator can theoretically fail when memory is actually available, it will never allocate a frame that is already in use.
To summarize, the physical memory manager on Kiwi is a big improvement over that of luxOS. With several caveats that we can work around, it is now able to allocate memory in logarithmic time, and it is designed to be lockless and highly concurrent. This is a huge step up from the linear time complexity and global lock contention issues of the old allocator. It also sets the stage to move on to the virtual memory manager, heap, and other components of the kernel.
// EOF — Made with 🥝 by jewelcodes.io