How To Build An Operating System: Page Frame Allocation- Part 08

Pubudu Wickramathunge
3 min readSep 10, 2021

--

This is the 8th article of this building an own operating system article series. If you didn’t read the first seven articles in this series, I recommend you to read those articles first.

We talked about virtual memory and paging in the last article. In this article, we will discuss page frame allocation. It uses to decide how many frames allocate to each process.

Managing available memory

To manage the memory we need to know how much memory is left in the computer. We can read that from the multiboot structure passed by the GRUB. GRUB collects the information about the memory like I/O mapped, what it reserved so on. GRUB doesn’t mark the memory as reserved by the kernel, we should also make sure that we don’t mark that part of the memory used by the kernel as free. We can know how much memory uses by the kernel, is to export labels from the linker script at the beginning and the end of the kernel binary as follows.

These labels can be read directly from the assembly code. It will make them available to C code.

    extern kernel_virtual_start
extern kernel_virtual_end
extern kernel_physical_start
extern kernel_physical_end

; ...

push kernel_physical_end
push kernel_physical_start
push kernel_virtual_end
push kernel_virtual_start

call kmain

Using these we get the labels as arguments to kmain. You can declare the labels as functions and take the addresses of those functions if you want to use C language instead of assembly language.

    void kernel_virtual_start(void);

/* ... */

unsigned int vaddr = (unsigned int) &kernel_virtual_start;

And also if you are using GRUB modules, you should make sure that the memory they use is marked as reserved. The available memory doesn’t need to be contiguous. Because we can’t map part of pages into memory it is convenient to divide the memory sections into complete page frames.

The page frame allocator needs to keep track of which page frames are free and which are in use. There are several ways to track that. Some of them are bitmaps, linked lists, trees, the Buddy System, etc. Here we are going to use bitmaps because it is easy to implement compared to other methods. In bitmaps, One bit is used for each page frame, and one or more page frames are dedicated to storing the bitmap.

Accessing a Page Frame

By updating the PDT and/or PT used by the kernel we should map the page frame into virtual memory. We can’t map the page frame into memory if all available page tables are full, because we would need a new page table that takes up an entire page frame, and to write to this page frame we would need to map its page frame. So this circular dependency must be broken. A solution is to reserve a part of the first-page table used by the kernel for temporarily mapping page frames to make them accessible. If the kernel is mapped at 0xC0000000, and the 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 of this page table for temporary mappings.

The virtual address of pages mapped using the last entry of the kernel’s PT will be:

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

After adding the page frame, we want to use as a page table and set it up to map in the first-page frame, we can add it to the paging directory, and remove the temporary mapping.

To this point, we have only been able to work directly with raw memory, or with fixed-size data. Now we have a page frame allocator and now we can implement malloc and free to use in the kernel.

So this is all for this week. See you next week.

Thanks for reading!.

References,

--

--