Use unallocated memory to keep track of unallocated memory.
A simple solution to keeping track of unused physical frames is to have a stack full of pointers. When the stack grows too big, then you pop an unused physical frame off it, map it somewhere, and then you have another pageful of pointers available. You can then push/pop to the stack and have constant time physical frame allocation, and when the stack is empty, you just start eating the pages you used to map the memory with, and there is no overhead in memory usage when you need the memory.
In addition, you need some system for keeping allocating virtual memory ranges. The kernel heap can simply be a region that has a lot of places to go (perhaps 256 MiB or much more) so allocating more virtual memory areas will always succeed for the kernel given that the heap doesn't get too large. Other virtual memory allocations will need some data structure that is allocated from the kernel heap, but it can rely on that.
Lastly, you would need a component that simply maps the allocated physical frames at the allocated memory range. For example, if you have a driver that needs 16 physical frames and mapping them somewhere, then it can do:
Code: Select all
unsigned long physical_frames[16];
allocate_physical_frame(physical_frames, 16);
unsigned long map_at;
allocate_virtual_kernel_address_space(&map_at, PAGE_SIZE * 16);
for ( size_t i = 0; i < 16; i++ )
map_physical_frame_at(physical_frame[i], map_at + PAGE_SIZE * i);
memory_flush();
It's a good idea to detach the concept of allocating virtual address space from allocating actual physical frames. This allows a driver that does memory mapped IO to bring its own physical frames, allocate somewhere to map them, and then just map them. Of course, this procedure is a bit bothersome in this case where you just want 16 pages somewhere, but you can build nice utility functions based on this.
To implement malloc, you must first code a system for allocating a memory region for the kernel heap. You can simply statically decide somewhere nice where you know there will be plenty of room and then simply map a page there or two. Once that isn't enough, you simply increase the pointer, pop a few physical frames and map them there. It may also be useful with a shrinking primitive, but probably not really.
Your malloc will now simply ask the size of this regionand its location from the memory region backend. It will initialize be 0 bytes, but gradually grow. The task is now simply to manage this large memory buffer and implement the traditional malloc semantics.
