OSDev.org

In my OS, I'm starting to implement basic memory management components. I've currently created a free list manager, which passes out free pages from a linked list (where there are lists per-cache color per-NUMA domain), and paging code, which creates a new page directory for the kernel, modules, and data structures and switches to it. Now I want to implement a kernel heap, since most other components of the kernel will depend on it. This made me step back a little bit and think about how the heap is allocated, not in physical memory (I have that down already), but in virtual memory. I'm not satisfied with just placing the heap at some static location, I want to be able to manage the kernel address space dynamically. Furthermore, other components like the module loader will need this support as well in order to place modules somewhere in the address space. This got me wondering about how I would actually go about implementing a virtual address allocator.

For simplicity, I could implement a virtual address allocator by just keeping a pointer to free virtual addresses and incrementing that pointer every time an allocation is made. I actually do this early on in my bootloader, since it needs to allocate several data structures for the kernel (namely the page frame database, per-CPU and NUMA domain areas, Local APIC MMIO region). Such a method is fine in a bootloader, since those virtual addresses will never be reclaimed, but it's not ideal in a kernel where you can free regions and create holes in the address space. Say the kernel allocates 4 pages, a module allocates 4 pages, the module frees all those pages, and then the kernel allocates a page, you'd be ignoring 4 virtual address space pages.

Another idea (which I got from reavengrey on the IRC) is managing the virtual address space using a linked list of free regions. Although it seems like you'd require a working kernel heap for this, I realized (or so I thought) that you actually don't. You can start out with one large, statically-allocated, region entry covering the whole address space. Each time you allocate a virtual address, you go through the linked list, find the first entry with a suitable size, and modify it to account for the fact that you allocated some pages. Allocating a new region entry is only required if you free some virtual addresses and end up creating a hole between two other free regions.

However, I then realized that upon allocating a virtual address range, you'd want to move it into a different data structure to keep track of used memory. This would require allocating new region entries upon allocations, creating a deadlocked dependency between the virtual address allocator and the kernel heap. Say you allocate 0x1000 bytes of kernel address space. This requires allocating a new region entry, so the memory manager asks the kernel heap for some memory for that. Let's say that the heap is out of virtual address space and needs more, so it decides to ask the kernel for more. Now it's impossible to continue and the kernel deadlocks. This scenario actually seems pretty likely, since the only way to expand the kernel heap is to get more space for virtual addresses.

So anyway, my question is what people think of these 2 mechanisms, how could they potentially be improved, or what are other methods I could use?

One simple solution is to allocate address space and physical memory for the requested allocations and for the various accompanying data structures together in one step.

For example, you could lay out things in the address space like so:

heap start
block 0 header (size, control info)
block 0 (free/reserved only/reserved and mapped)
block 0 footer (size, control info)
block 1 header (size, control info)
block 1 (free/reserved only/reserved and mapped)
block 1 footer (size, control info)
...
block N header (size, control info)
block N (free/reserved only/reserved and mapped)
block N footer (size, control info)
heap end

You begin with just one huge block that is free, but whose header and footer are properly mapped and initialized. You then slice it when making allocations. When you free a block, you try to combine it with its neighbors. Everything is as usual.

If you want a list of free regions or any other kind of list of blocks, you store the list entries (or the tree nodes, if it's a tree) in the header or the footer.

Strictly speaking, you don't need a header and a footer around every block. But having both makes it very trivial to reach neighbors of any given block, which you typically need when freeing a block and combining its space with those of its neighbors. Having both may also help detecting buffer overruns.

IOW, you start out with 2 pages properly mapped at both ends of the heap region and put there the header and the footer for the initial block. When you split it, you may need to allocate and map a few more pages for the header and the footer of the new block. This is how you reserve address space. The next step is to allocate and map pages between the header and the footer to actually allocate memory, which you're already able to do as I understand.

As for the free list itself, I've once used a red-black tree, in which the nodes representing available address space regions are ordered by their size. This makes finding big enough holes fast even in the presence of many allocations and fragmentation. Better than the linear search anyway.

Just one simple idea.

I created a class to do just address space allocations, called "ASA" for Address Space Allocator. It can allocate just a region of size X with a given alignment, or a specific region of size X. It will prevent collisions between multiple users of the same space. It is structured such that it uses a single sequential blob of memory to keep track of storage.

It assumes malloc/free are available and working. This means that malloc/free must have a bootstrap method, but fortunately this is not too hard to do (ie, to move the requirement to the bootloader) by having an initial_heap in .bss that you put at the end of kernel memory & give to malloc/free initially. That only requires you to have bootstrapped before running out of that space, but that's doable.

Thanks for everyone's suggestions, but I decided to solve the problem in a different way. The virtual address space allocator, called addrspace_alloc(), now takes two arguments, the number of bytes to reserve and the number of bytes to commit initially. This scheme allows for demand paging, where you reserve space in the address space but don't allocate any pages, and wait until page faults to do so. However, it's also useful for resolving this deadlocked dependency. Let's say addrspace_alloc() requires allocating metadata, and this metadata allocation requires allocating more heap space. This virtual address allocation will be told by the heap to reserve and commit the amount of space needed, rather than using demand paging, which would require recording metadata. Since all the needed heap space is committed, you can allocate metadata to record the allocation and then go back to your original allocation, allocating its metadata.