Develop our own operating system! #part08

Page Frame Allocation

6 min readSep 10, 2021

Welcome again to the 8th step of developing our own operating system. I hope you remember that last time we discuss about paging. If you have missed that article you can read it from here because that knowledge about paging is absolutely necessary for today’s discussion and this is more like a second part of that last discussion.

So, as you know we have already initiated paging for our operating system. But now, the problem is ‘how we can allocate that process pages to the RAM?’. Or in other words ‘How do we allocate free page frames in the RAM to process pages?’. With today’s article you can have a clear idea about how we can do this.

How Much Memory is There?

Now, Think about our RAM. What is in there so far? This is very important question that we should know the answer. Because before anything else we need to know that how much memory is available on the RAM when the OS is running on. ( In the first 1 MB there are several I/O-mapped memory sections, as well as memory used by GRUB and the BIOS. Other parts of the memory might be similarly unavailable.)

The easiest way to do this is to read it from the multiboot structure passed to us by GRUB. (If you want to refresh your knowledge about multiboot structure here is the article.) GRUB collects the information we need about the memory such as what is reserved, I/O mapped, read-only etc.

Since GRUB doesn’t mark the memory as reserved by kernel, we must also make sure that we don’t mark that part of memory used by the kernel as free. One way to know how much memory the kernel uses is to export labels at the beginning and the end of the kernel binary from the linker script. You can do this as follows:

    ENTRY(loader)  /* the name of the entry symbol */

    . = 0xC0100000 /* the code should be relocated to 3 GB + 1 MB */

    /* these labels get exported to the code files */
    kernel_virtual_start = .;
    kernel_physical_start = . - 0xC0000000;

    /* align at 4 KB and load at 1 MB */
    .text ALIGN (0x1000) : AT(ADDR(.text)-0xC0000000)
    {
        *(.text)    /* all text sections from all files */
    }

    /* align at 4 KB and load at 1 MB + . */
    .rodata ALIGN (0x1000) : AT(ADDR(.rodata)-0xC0000000)
    {
        *(.rodata*) /* all read-only data sections from all files */
    }

    /* align at 4 KB and load at 1 MB + . */
    .data ALIGN (0x1000) : AT(ADDR(.data)-0xC0000000)
    {
        *(.data)            /* all data sections from all files */
    }

    /* align at 4 KB and load at 1 MB + . */
    .bss ALIGN (0x1000) : AT(ADDR(.bss)-0xC0000000)
    {
        *(COMMON)           /* all COMMON sections from all files */
        *(.bss)             /* all bss sections from all files */
    }

    kernel_virtual_end = .;
    kernel_physical_end = . - 0xC0000000;

These labels (kernel_virtual_end , kernel_physical_end) can directly be read from assembly code and pushed on the stack to make them available to C code. (We have done something very similar to this when we were creating functions with arguments.) You can do this as follows.

    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

As I mentioned before in this way we can get the labels as arguments to kmain. If you want to use C instead of assembly code, we can do that by declare the labels as functions and take the addresses of these functions:

    void kernel_virtual_start(void); /*the function*/

    /* ... */

    unsigned int vaddr = (unsigned int) &kernel_virtual_start;
    /*Taking the address to a variable*/

Since we are using GRUB modules we need to make sure the memory they use is marked as reserved as well. ( Hope you remember that in a earlier stage we created a simple program to push a number to EAX register using modules.)

Remember that the available memory does not need to be contiguous. But it’s convenient to divide the memory sections into complete page frames, because we can’t map part of pages into memory.

How Can We Access a Page Frame?

How do we know which page frames are in use? The most important functions you’ll have to write is the page frame allocator. The page frame allocator will keep track of which are free and which aren’t. There are several ways to do this: bitmaps, linked lists, trees, the Buddy System (used by Linux) etc.

Bitmaps 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.

Bitmap

A large array of N/8 bytes is used as a large bit map of the memory usage (that is, bit #i in byte #n define the status of page #n*8+i). Setting the state of a given page is fast (O(1)), allocating a page may take time (O(N)).

an uint32_t comparison can test up to 32 bits at once and thus speed up allocations
keeping a pointer to the last allocated bit may improve the performance of the next search (keeping information about the fact all the previous bytes were searched unsuccessfully)

After the execution the page frame allocator returns the physical start address of a free page frame. That means this page frame is not mapped in or no page table points to this page frame.

So, how can we read and write data to the frame?

At first, we need to map this page frame into virtual memory, by updating the Page Directory Table and/or Page Table used by the kernel.

When all accessible page tables are full, however, there will be a conflict. We can’t map the page frame into memory in this case because we’d need a new page table that takes up a whole page frame, and we’d have to map the page frame to write to it. This circular reliance must be broken in some way.

One option is to set aside a portion of the kernel’s first page table (or another 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 (page directory entry with index 768) and 4 KB page frames are used. We can allocate the last entry (entry 1023) 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. The virtual address of pages mapped in with the kernel’s PT’s last entry will be:

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

We may add the page frame we wish to use as a page table to the paging directory and remove the temporary mapping after we’ve temporarily mapped it and set it up to map in our initial page frame.

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. 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.

So that’s about page frame allocation! Hope you got a good understanding about page frame allocation with this article. Until we meet with another exciting topic be motivated! keep learning! :)

Written by,

R.A.W. Lalendra

Undergraduate in Bsc(hons) Software Engineering

University of Kelaniya Sri Lanka.