Implementation of an Operating System -Week 8

Welcome to the 8th step of this article series.

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 ?

When we are going to do the page frame allocation first we need to know how much memory is available on the computer the OS is running on. Reading it from the multiboot structure supplied to us by GRUB is the simplest way to do it. GRUB gathers the memory information we require, such as what is reserved, I/O mapped, read-only, and so on. We must also make certain that the memory used by the kernel is not marked as free.

Exporting labels at the beginning and end of the kernel binary from the linker script is one technique to figure out how much memory the kernel uses.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

We can obtain the labels as arguments to kmain this way. Declare the labels as functions and take the addresses of these functions if you wish to use C instead of assembly code:

void kernel_virtual_start(void);    /* ... */    unsigned int vaddr = (unsigned int) &kernel_virtual_start;

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 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 I mentioned earlier in the article, it is the responsibility of the page frame allocator to keep track of page frames that are free and which aren’t.

There are many methods of page frame allocation. Some of those methods are Bitmaps, linked lists, trees, the Buddy System (used by Linux), sized portion scheme, hybrid scheme etc.

How can we access a Page Frame?

The page frame allocator delivers 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 can’t map the page frame into memory since we’d have to create a new page table, which would take up a whole page frame, and we’d have to map this page frame’s page frame to write to it. This cyclic reliance must be broken in some way.

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:

(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

We’ve only been able to operate with fixed-size data or raw memory up until now. We can implement malloc and free to use in the kernel now that we have a page frame allocator. The only change we need to do is to invoke the page frame allocator instead of sbrk/brk when extra memory is required. The page frames provided by the page frame allocator must also be mapped to virtual addresses. 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.

Thank you!