Develop Your Own x86 Operating System(OS) #9
Page Frame Allocation
In the previous article we discussed about the virtual memory and paging in details. Through this article let’s get an idea about page frame allocation, the technique of informing the operating system, the parts of memory that are free to use when dealing with virtual memory.
If you haven’t gone through the previous article on paging, please be sure read it from here, in order to understand this article as this is an extension of that process.
Paging is an important part of virtual memory implementations in modern operating systems. It is the most common technique used in x86 to enable virtual memory. We discussed a lot of details about paging in the previous article. When writing an operating system for any architecture, one of the most important functions you’ll have to write is the page frame allocator. So, let’s discuss about page frame allocation now.
Page Frame Allocation is the process of allocating the part of memory to be used by the Operating system. More precisely, “When using virtual memory, how does the OS know which parts of memory are free to use?”, that is the role of the page frame allocator.
Therefore, let’s look in to the step by step of managing the available memory.
Add identity mapping for the first 4 MB of the virtual address space.
Add an entry for 0xC0100000 that maps to 0x00100000
We have to be careful when using memory-mapped I/O that uses specific memory locations. Ex: — The frame buffer is located at 0x000B800, but since there is no entry in the page table for the address 0x000B800 any longer, the address 0x000B800 must be used, since the virtual address 0xC000000 maps to the physical address 0x0000000.
Any explicit references to addresses within the multiboot structure needs to be changed to reflect the new virtual addresses as well.
Managing Available Memory
In order to manage the available memory first of all we have to know how much memory is available on the computer the OS is running on.
How Much Memory is There?
The simplest way that can be followed to do this is to read it from the multiboot structure passed to us by GRUB. I hope you can remember what a multiboot structure is as we have discussed it in a previous article (#7).
GRUB is on duty to collect the information we need to know about the memory (what part of memory is reserved, I/O mapped, read-only etc.). Specially remember that the GRUB doesn’t mark the part of memory used by the kernel as reserved so, it’s our responsibility to make sure that we don’t mark this memory as free.
There is one simple way to know the amount of memory the kernel uses. It is to export labels at the beginning and the end of the kernel binary from the linker script:
These labels can be read using assembly code and pushed on the stack to make them available to C code. Update loader.s file as below:
This way we get the labels as arguments to kmain.
Assembly code may be very bothersome to you, so you may prefer C over assembly. Hence, if you want to use C there you can easily to this by declaring the labels as functions and take the addresses of these functions. An example is given below for demonstration:
If you use GRUB modules you need to make sure the memory they use is marked as reserved as well.
The available memory to be used, does not need to be contiguous.
How can we manage available memory?
It’s convenient to divide the memory sections into complete page frames, since we can’t map part of pages into memory. But is there a way for us to fin about which page frames are in use and which are not?
As mentioned earlier in the article, it is the responsibility of the page frame allocator to keep track of page frames which are free and which aren’t.
There are many methods of page frame allocation, each with varying levels of complexity and efficiency. Some of those methods are Bitmaps, linked lists, trees, the Buddy System (used by Linux), sized portion scheme, hybrid scheme etc.
Bitmaps are easy to implement. Here, one bit is used for each page frame and one or more page frames are dedicated to store the bitmap. In Linked lists method, the address of each available physical frame is stored in a stack-like dynamic structure. Buddy Allocation System is the physical memory allocator of Linux kernel. A buddy for N pages is about twice the size of a bitmap for the same area, but it allows a faster location of collections of pages. In Hybrid scheme allocators may be chained so that for an example a stack only covers the last operations and that the ‘bottom’ of the stack is committed to a bitmap. In this way, if the stack lacks pages, it can scan the bitmap to find some.
Method of Accessing a Page Frame
The page frame allocator returns the physical start address of the page frame. But if this page frame is not mapped in, no page table will point to this page frame. So, how can we read and write data to the frame? It’s time to find out.
As the first step we need to map the page frame into virtual memory, by updating the PD or PT used by the kernel. But if all available page tables are full, then we can’t map the page frame into memory as we face with the necessity of a new page table. This will take up an entire page frame. Not only that in order to write to this page frame we’d need to map its page frame. May be we would find a solution if we succeed in breaking this dependency of pge tables and page frames on each other.
One solution is to reserve a part of the first page table used by the kernel (or some other higher-half page table) for temporarily mapping page frames to make them accessible. If the kernel is mapped at 0xC0000000 (page directory entry with index 768), and 4 KB page frames are used, then the kernel has at least one page table. If we assume - or limit us to - a kernel of size at most 4 MB minus 4 KB we can dedicate the last entry (entry 1023) of this page table for temporary mappings. The virtual address of pages mapped in using the last entry of the kernel’s PT will be:
After we’ve temporarily mapped the page frame we want to use as a page table, and set it up to map in our first page frame, we can add it to the paging directory, and remove the temporary mapping.
A Kernel Heap
So far we’ve only been able to work with fixed-size data, or directly with raw memory. Now that we have a page frame allocator we can implement malloc and free to use in the kernel.
The only modification we need to do is to replace calls to sbrk/brk with calls to the page frame allocator when more memory is needed. We must also make sure to map the page frames returned by the page frame allocator to virtual addresses. A correct implementation should also return page frames to the page frame allocator on call to free, whenever sufficiently large blocks of memory are freed.
References:
Writing A Page Frame Allocator
Hope you understand what page frame allocation is. Let’s meet with the next article of Develop Your Own x86 Operating System(OS) series. Thank you so much for reading!!!!!!!!!!
Isuruni Rathnayaka
