Operating System : Page Frame Allocation
This article is part of a series of articles explaining the development of an x86 Operating System. You can find all of the previous articles at the end.
In my last article, I explained about organizing memory in an Operating System using Paging. You can go back to that article to know all about integrating a simple paging setup into the memory, using this link below.
But we didn’t stop there. We took our OS to the next level by relocating the kernel to 3 GB in the virtual address space. For that I wrote a separate article dedicating to all about the higher-half kernel, which can go to using this link below.
<link will be updated later>
Since we need some sort of basic paging set up to go further in our OS development, I recommend you to go back to these articles and catch up. If everything is set up we can move on to our next step in paging.
Since we have our paging integrated and kernel working safely in the higher half, why don’t we just allocate a user process to a page frame and see if it works?
This is what turns us to the page frame allocator.
What is the Page Frame Allocator?
When writing an operating system for any architecture, one of the most important functions you’ll have to write is the page frame allocator.
Although you may find the coding part of it a bit daunting, the basic concept behind it is quite simple. The Page Frame Allocator 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.
In this article, I’ll show how to write functions to satisfy all of these.
But before getting into all that we need to know about managing memory. When using virtual memory, how does our OS know which parts of memory are free to use?
Managing Available Memory
Exactly how much Memory is there?
The memory capacity changes from each computer. So the first thing we need to know is how much memory is available on the computer the OS is running on. We can simply read it from the multiboot structure passed to us by GRUB.
But the GRUB doesn’t mark the part of the memory used by the kernel as reserved. In order to change that, we need to export labels at the beginning and the end of the kernel binary from the linker script, like this,
We can read these labels directly from the assembly code. And push them onto the stack to make them available to our C code.
So now we get these labels as arguments for our kmain. But for us to get the address from these labels we need to declare the labels as functions first.
Since we are using a GRUB module for our simple “deadbeef” program, we need to make sure we reserve that memory as well.
Managing Available Memory using Bitset
And now we KNOW which part of the memory is actually free. But is that enough for the page frame allocation? No. We need to how to manage that available memory.
First, we need to know which page frames are currently in use? Because the page frame allocator needs to keep track of which are free and which aren’t.
There’s a couple of ways to do this. From bitmaps to linked lists to trees and to the Buddy System, which is what Linux uses. For this OS, I’ll be using Bitset. Which is similar to using Bitmaps. Because they are quite easy to implement. One bit is used for each page frame and one (or more) page frames are dedicated to storing the bitset. Check this code below from our paging.c.
All those functions are used to manage the available memory using Bitset.
But how can we Access a Page Frame?
First, we need a function to get the page frame for us. It will need to do these things for us.
- Turn the address into an index.
- Find the page table containing this address.
- If this table is already assigned, return the physical start address of the page frame.
But what happens if there is no page table that points to this page frame? We need our function to go to the directory and simply create a new table. Check this function below.
Then we need another function to map the page frame into the virtual memory. Now in a more advanced setup, this function will also take into account if all available page tables are full. But our function will, for now, simply allocate page frames into the virtual memory.
Summary
In this article, we first discussed how to reserve the memory for our kernel and GRUB Modules. Next, we discussed how to manage the rest of the available memory using Bitset. Finally, we discussed how to access the page frames allocated. In short, we have now integrated a simple but adequate page frame allocator.
With this article, along with the previous two articles we have finally set up paging to our operating system. If you want to get the complete code with all the parts of paging integrated, you can do that from my GitHub, right here,
Hope to see you in the next article as well!
Thank you!
Reference: Helin, E., & Renberg, A. (2015). The little book about OS development
