Build your own OS (part 8)

4 min readSep 10, 2021

Page Frame allocation

image source: https://www.freepik.com/free-vector/operating-system-concept-illustration_9233847.htm#page=1&query=operating%20system&position=3

Welcome again everyone to the 8th part of my OS development article series. In the 7th article, I discussed virtual memory and how we can implement virtual memory through paging to our OS (For your convenience, I’ll include links to all previous articles at the end). However there’s one thing we need to consider before using virtual memory.However there’s one thing we need to consider before using virtual memory.

The operating system must know which parts of memory are available for use. That is accomplished by the page frame allocator.

How Much Memory Is Available?

First, we must determine how much memory is available on the computer that the operating system is running on. The simplest way to do this is to read it from the multiboot structure that GRUB has passed to us. GRUB gathers the memory information we require, such as what is reserved, I/O mapped, read-only, and so on. We must also ensure that we do not mark the kernel’s memory as free (because GRUB does not mark this memory as reserved). One method for determining how much memory the kernel consumes is to export labels from the linker script at the beginning and end of the kernel binary. We can use the following linker script to achieve that:

These labels can be read directly from assembly code and pushed onto the stack, making them available to C code:

We get the labels as arguments to kmain this way. If you want to use C instead of assembly code, one option is to declare the labels as functions and take their addresses:

If you use GRUB modules, make sure the memory they use is also marked as reserved.

It should be noted that the available memory does not have to be contiguous. There are several I/O-mapped memory sections in the first 1 MB, as well as memory used by GRUB and the BIOS. Other parts of the memory may also be inaccessible.

Because we can’t map parts of pages into memory, it’s easier to divide the memory sections into complete page frames.

Managing Available Memory

Now we need to know which page frames are in use and which are not? The page frame allocator is needed to do that for us. There are several methods for doing this, including bitmaps, linked lists, trees, the Buddy System (used by Linux), and so on. We will be using Bitmaps as they are quite easy to implement. One bit is used for each page frame and one (or more) page frames are dedicated to store the bitmap.

Accessing a Page Frame

The page frame allocator returns the page frame’s physical start address. This page frame is not mapped in — no page table refers to it. How do we read and write data to and from the frame?

We must map the page frame into virtual memory by updating the kernel’s PDT and/or PT. What if all of the available page tables are taken? Then we can’t map the page frame into memory because we’d need a new page table, which takes up an entire page frame, and in order to write to this page frame, we’d have to map its page frame… This circular dependency must be broken in some way.

One solution is to set aside a portion of the kernel’s first page table (or another higher-half page table) for temporarily mapping page frames to make them accessible. If the kernel is mapped to 0xC0000000 (page directory entry with index 768) and 4 KB page frames are used, the kernel must have at least one page table. We can dedicate the last entry (entry 1023) of this page table for temporary mappings if we assume — or limit ourselves to — a kernel with a maximum size of 4 MB minus 4 KB. The virtual address of pages mapped in using the kernel’s PT’s last entry will be:

(768 << 22) | (1023 << 12) | 0x000 = 0xC03FF000

We can add it to the paging directory and remove the temporary mapping 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. Now that we have a page frame allocator we can implement malloc and free to use in the kernel.

That’s it for this part of the article series. At the end of the article, I’ll include a link to my Github repo so you can clearly understand the implementation. I will meet you with another article soon. Until then, Goodbye & Stay Safe.