Building your own Operating System (Week 08)

This is the seventh article in this series. In this article, I’m going to talk about page frame allocation. In the previous article, I explained virtual memory and paging. You can check it out by clicking here. For those coding and implementation staff, I’m following the guide “The little book about OS development” by Erik Helin and Adam Renberg.

The page frame allocator allows the operating system to divide the physical memory on a system into page frames, which may subsequently be used to allocate memory to programs using a separate paging function.

Managing Available Memory

Reading the multiboot structure provided to us by GRUB is the simplest approach to determine available memory. GRUB gathers the memory information we require, such as what is reserved, I/O mapped, read-only, and so on. We must additionally ensure that the memory utilized by the kernel is not marked as free (because GRUB does not identify this memory as reserved). Exporting labels at the beginning and end of the kernel binary from the linker script is one approach to figure out how much memory the kernel uses.

To do it we need to update the linker file.

We need to add these labels to directly be read from assembly code and pushed on the stack to make them available to C code.

The page frame allocator must keep track of which frames are available for use and which are not. Bitmaps, linked lists, trees, the Buddy System, and other techniques can be used to do this. Bitmaps are quite simple to use. Each page frame uses one bit, and one (or more) page frames are allocated to storing the bitmap.

How Can We Access a Page Frame?

The page frame allocator returns the page frame’s physical start address. There is no page table that points to this page frame since it is not mapped in.

What is the best way to read and write data to the frame? We must map the page frame into virtual memory by changing the kernel’s PDT and/or PT.

What if all of the accessible page tables are already occupied? Then we won’t be able to map the page frame into memory since we’ll need a new page table which will take up a whole page frame and we’ll need to map the page frame’s page frame to write to it.

One solution is to set aside a portion of the kernel’s higher-half page table for temporarily mapping page frames so that they are accessible. The kernel contains at least one page table if it is mapped at 0xC0000000 and 4 KB page frames are utilized. We may allocate the last item of this page table to temporary mappings if we assume or limit ourselves to a kernel with a maximum size of 4 MB minus 4 KB. We may add the page frame we wish to use as a page table to the paging directory and remove the temporary mapping once we’ve temporarily mapped it and set it up to map in our initial page frame.

Kernel Heap

We can implement malloc and free to use in the kernel now that we have a page frame allocator. The page frames provided by the page frame allocator must also be mapped to virtual addresses. To do it first we need the “kheap.h” header file.

Here’s the “kheap.c” file.

When sufficiently large blocks of memory are freed, a good implementation should also return page frames to the page frame allocator on call to free.

I think you all get a good idea about page frame allocation. You can also check my Github Repo using this link.

Thank you for reading and hope to see you in the next article as well!