OSDEV: Implementing a basic x86 page frame allocator in C
When writing an operating system for any architecture, one of the most important functions you’ll have to write is the page frame allocator. The page frame allocator allows the OS to divide the physical memory available on a system into chunks called page frames, which can then be used later to allocate memory to applications with a separate paging function.
There are many methods of page frame allocation, each with varying levels of complexity and efficiency. For an overview of many of these methods, see the OSDev Wiki. In this post we’ll be going over a much less efficient method than those outlined in the wiki for simplicity’s sake, but you can improve upon it later.
Unlike those outlined in the wiki, our page frame allocator isn’t actually going to be storing any data of its own. Instead, we’re going to piggyback off of the Multiboot information structure. If you’re following this tutorial, you hopefully already have a basic Multiboot kernel set up, as well as a basic understanding of the Multiboot specification (the PDF for which can be found here).
Without reading the entire specification, the rundown is that your Multiboot-compliant bootloader (probably GRUB) will provide you with an information structure that contains a lot data about the system you’re running on. Among this data is the Multiboot memory map, which provides a listing of all memory regions in the system, and which ones you’re allowed to write to (many regions are reserved for things like VGA video output).
To access this memory map, we must first pass a pointer to the information structure
to our kernel’s entry point. Luckily, our bootloader will put this pointer in the
ebx
register when we first boot up, so all we have to do is pass it as a parameter
to our entrypoint in assembly. Along with ebx
, we’ll also pass eax
which contains
a “magic value”, 0x2BADB002
, which you can use to verify that the bootloader is
in fact Multiboot-compliant.
Getting the Multiboot information structure
Before we start, we have to make sure that we’ve declared to our bootloader that we want the memory map to be included in the information structure, as it is optional by default. If you’re using the boot assembly code from the OSDev Bare Bones tutorial, this is already done for you. The code to specify we want the memory map looks like this (at the top of your file):
We’ll also have to make sure that the initial stack is at least 4096 bytes
(the size of a single page). As with the previous step, if you’re using the
OSDev Bare Bones code this is done already. I’ll be setting it to 16384 bytes,
but anything greater than 4096 bytes should suffice.
This change needs to be done in your boot.asm
or equivalent file.
Now that our stack is big enough, we can pass the Multiboot information structure as well as the magic value to our kernel entrypoint. Remember that we must push the values in the reverse order that we want to use them:
Now we can access these values in our kernel’s C entrypoint, we just have to change its parameters:
Defining the Multiboot information structure
To read the Multiboot information structure, we first need to declare a few
struct
s in C that define its layout. Luckily the aforementioned
Multiboot specification PDF has them written out for you on page 16.
While it does declare more than we’ll need for this tutorial, it’s not a bad idea
to include the whole file anyways as it may be useful in the future.
Once you have the structures and constants from the PDF included into your kernel, there’s one more thing we need to do before we can start parsing the information structure.
Validating the Multiboot magic value
As stated before, the Multiboot magic value is simply a constant that all Multiboot-compliant bootloaders will provide to prove that they are compliant. Before we even attempt to read the Multiboot information structure, we should verify this value so that we don’t try to read garbage in the event that the kernel is not booted properly.
Preparing to read the Multiboot information structure
Now that we’ve verified the magic value, we can read the Multiboot information structure and look for the memory map. As it’s possible the memory map wasn’t included (in the case of an incomplete bootloader or other error), it’s always good to check for its existence.
We’re almost there, but first, let’s set some global variables that will help us keep track of things and make our lives easier.
As you can see, we’ve made quite a few variables. First, we’ve got a pointer,
verified_mboot_hdr
where we can store our pointer to the information structure
so other functions can access it easily. Next, we’ve got mboot_reserved_start
and mboot_reserved_end
which, surprisingly enough, store the start and end
locations of the Multiboot information structure in memory so we don’t accidentally
overwrite it later. Finally, we’ve got next_free_frame
, which stores the number
of the next free frame. This will be explained in greater detail in a later section.
A page frame allocator
We’ve gone through all the steps to verify and prepare to read the Multiboot
information structure, but up until now you didn’t know why. As stated before,
our page frame allocator is going to piggyback off of the Multiboot memory map
to keep track of allocated frames. We’re going to do this by having a single
counter that increases by one every time we allocate a 4096 chunk (frame) of free memory
in the Multiboot memory map from start to end. This way, frame #1 is always the
first 4096 bytes marked as free in the memory map, #2 is the second 4096 bytes,
and so on. This is what the next_free_frame
variable in the previous section is
for.
Before we can write the actual allocator, we need a method to read the memory map and retrieve memory addresses that correspond to frame numbers, and vice versa. For this we’re going to create a separate function that accesses those varibles we created earlier.
While this code looks daunting, the basic concept behind it is quite simple. It essentially does the following:
- Read each entry in the memory map
- Split each entry into frame-sized chunks (4096 bytes)
- Iterate through each chunk until a valid address is found for the given frame number or a frame number is found for the given address.
Now that we can read the memory map, creating an allocator can be done quite simply:
Now, to allocate a page frame you simply have to call
Conclusion
Congratulations! You now have a working (albeit primitive) method of page frame allocation for your operating system. It cannot yet free frames, but it provides a good starting point for developing a paging system. In the future, I may write another post improving upon this allocator with freeing implemented, as well as some performance enhancements.
Resources
If you get stuck anywhere, I recommend taking a peek at my example OS ShawnOS, as well as the plethora of online resources related to OS development, such as the OSDev Wiki.