Implementation of an Operating System ( 8-Page Frame Allocation)

This is my 8th article of my Implementation of an Operating System. So in this article I’m going to talk about Page Frame Allocation. But first I want to inform that you, If you are a new reader for my article series, I think you must go to begging and read begging. Because If you don’t do that you can’ understand what I am saying in this chapter. You can go to the begging in this link.

First we can see what is the mean of managing memory.

Managing Available Memory

Memory Management is the process of controlling and coordinating computer memory, assigning portions known as blocks to various running programs to optimize the overall performance of the system.

It is the most important function of an operating system that manages primary memory. It helps processes to move back and forward between the main memory and execution disk. It helps OS to keep track of every memory location, irrespective of whether it is allocated to some process or it remains free.

First we need to know how much memory is available on the computer the OS is running on. The easiest way to do this is to read it from the multiboot structure [19] passed to us by GRUB. GRUB collects the information we need about the memory — what is reserved, I/O mapped, read-only etc. We must also make sure that we don’t mark the part of memory used by the kernel as free (since GRUB doesn’t mark this memory as reserved). 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.

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 can directly be read from assembly code and pushed on the stack to 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

This way we get the labels as arguments to kmain. If you want to use C instead of assembly code, one way to do it is to declare the labels as functions and take the addresses of these functions:

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

If you use GRUB modules you need to make sure the memory they use is marked as reserved as well.

Note that the available memory does not need to be contiguous. 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.

It’s convenient to divide the memory sections into complete page frames, as we can’t map part of pages into memory.

Then we can see how Can We Access a Page Frame;

How Can We Access a Page Frame

A page, memory page, or virtual page is a fixed-length contiguous block of virtual memory, described by a single entry in the page table. It is the smallest unit of data for memory management in a virtual memory operating system. Similarly, a page frame is the smallest fixed-length contiguous block of physical memory into which memory pages are mapped by the operating system.

A transfer of pages between main memory and an auxiliary store, such as a hard disk drive, is referred to as paging or swapping.

We need to map the page frame into virtual memory, by updating the PDT and/or PT used by the kernel. What if all available page tables are full? 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 to write to this page frame we’d need to map its page frame… Somehow this circular dependency must be broken.

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

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, we can add it to the paging directory, and remove the temporary mapping.

Next

A Kernel Heap

A heap is a vital component of both application programs and the kernel. It is also generally superseded by a higher level of memory management that deals with larger chunks of memory. For most operating systems memory will be allocated based on pages or other large chunks. A page on the X86 and X64 architectures is generally 4KB, but can be larger. However, for smaller allocations the entire page would be wasted. For example if you only needed 24 bytes and you allocate an entire 4KB page you will have wasted a lot of memory. So most applications and kernels will implemented a second memory management scheme that uses memory allocated in 4KB chunks (or larger) and break these strips of pages or individual pages into smaller parts as they are requested.

Standard Library, Applications, And Kernel

Applications in most operating systems have their own heap implementation as a part of the standard library and do not use the implementation that the kernel uses. So therefore not only is the heap for the kernel separate from the heap of each application, but it may very well use a different heap implementation. Also, this allows each application to use it’s own implementation depending on which standard library is was built against or with. However, there is no reason why a kernel could not provide heap services directly to applications. It must be noted too that there is no way to enforce an application to use a specific heap or implementation because a clever programmer could simply use the memory allocated to supply it’s own implementation.

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.

Kernighan and Ritchie [8] have an example implementation in their book that we can draw inspiration from. The only modification we need to do is to replace calls to sbrk/brk with calls to the page frame allocator when more memory is needed. We must also make sure to map the page frames returned by the page frame allocator to virtual addresses. 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.

Thank you!

References;

wikipedia.com

littleosbook

You can refer this book : https://littleosbook.github.io/