KoizOS - Virtual Memory Allocation

Introduction

After getting a basic physical memory allocator up and running, the next logical step would be dealing with virtual memory allocation. Like most modern operating systems, I'll be using Paging which chops up the memory space into pieces of fixed size. Paging techniques have been around since the the building of the Atlas computer in 1962. Since these posts are more of a journal to share my progress versus a fully fledged tutorial, I'll link to the OS Dev page for paging here if you'd like more information. I usually contribute more tutorial-like knowledge to OS Dev anyways.

Paging

In the last post, I briefly talked about the MMU, or memory management unit, which works to map memory through the use of both the page directory and the paging table. To get my operating system to work with paging, I'd need to set both of these structures up and tell the x86 CPU to enable paging.

The smallest page size is usually 4KiB, yet for our 32-bit x86 target, we also have the option of using 2MiB or 4MiB pages. It's also worth mentioning that some x86_64 processors support huge pages up to 1GB (provided they have the PDPE1GB cpu flag). In Koiz OS, I'll simply be using 4KiB pages since the physical memory allocator is already programmed to hand out 4KiB memory chunks.

I'll be using a two-level page table structure for x86 systems which the following diagram from Wikipedia's article on Page Tables does a great job outlining:

Implementation

The first function to write ties together the previous physical memory allocator with the current virtual memory allocator. Although these 4KiB chunks should already be properly aligned, I put in extra checks just in case.

uint32_t* vmem_alloc_pmem()
{
    /* Grab a page frame of physical ram to avoid 4kb static allocation in kernel */
    /* This also has the benefit of being automatically aligned (or should be) */
    uint32_t* ptr = pmem_alloc();

    /* Double-check that the physical page size should be page-aligned to 4096 otherwise paging would be weird! */
    if((uint32_t)ptr & 0xFFF != 0x0)
        panic("vmem_init: page directory needs to be 4096 aligned!");
    
    /* Physical page size should be at least as big as the array where we'll store stuff */
    if(PHYS_BLOCK_SIZE < sizeof(uint32_t[1024]))
        panic("vmem_init: physical block page size isn't large enough");

    return ptr;
}

Address translation helper functions can be written to help us easily translate between virtual and physical memory addresses. Note that this has a variable called proc_page_directory which stands for the current process's page directory.

uint32_t* vmem_get_phys_addr(uint32_t* proc_page_directory, uint32_t* virtual_addr) 
{
    /* Look up page directory and page table entries */
    uint32_t page_dir_entry = ((uint32_t)virtual_addr) >> 22;
    uint32_t page_table_entry = ((uint32_t)virtual_addr) >> 12 & 0x03FF;

    /* Obviously should never happen but you never know... */
    if(page_dir_entry > 1024)
        panic("vmem_get_phys_addr: page_dir_entry is will overflow");
    if(page_table_entry > 1024)
        panic("vmem_get_phys_addr: page_dir_entry is will overflow");
    if(proc_page_directory == 0)
        panic("vmem_get_phys_addr: page_directory was never declared!");

    /* Check if the entry in the page directory exists */
    if(proc_page_directory[page_dir_entry] == 0) {
        return 0;
    }

    /* Convert the entry to a proper address to access */
    uint32_t* page_table_addr = (uint32_t*) (proc_page_directory[page_dir_entry] & ~0xFFF);

    /* Check if the page table entry exists. If it does not, return 0 */
    if(page_table_addr[page_table_entry] == 0) {
        return 0;
    }

    /* It exists, we'll process it into a physical address */
    uint32_t phys_addr = (page_table_addr[page_table_entry] & ~0xFFF) + ((uint32_t)virtual_addr & 0xFFF);
    return (uint32_t*)phys_addr;
}

One sticking point for me was figuring out how paging works in a system that supports multiple processes. With each process, the address space is replaced with another and therefore the current entries in the TLB would likely be invalidated. So during a context switch, we'd likely need to flush the TLB after point to the new page structures for that process. I might be overlooking some things since I haven't fully explored this yet for the future, but good to be thinking about this now. This is the main reason why much of my functions take a page directory as an argument.

In initializing virtual memory, I'm simply identity mapping everything. This is less than ideal, but for simply starting out with virtual memory this is fine.

void vmem_init(void)
{
    int32_t i;

    /* We can use ptable_new to create the page directory */
    uint32_t* base_ptr = vmem_ptable_new();

    /* 
     * Identity page the entire kernel-space. This just makes it easier.
     * However, note that user processes are not paged this way
     */
    for(i = 0; i < 1024; i++) {

        /* Set kernel pagetable to present and read/write in the page directory */
        uint32_t* kernel_pt = vmem_ptable_new();
        base_ptr[i] = ((uint32_t)kernel_pt) | 3;

        /* Populate the pagetable with identity-map entries */
        uint32_t j;
        for(j = 0; j < 1024; j++) {
            uint32_t virt_addr_entry = ((i << 22) | (j << 12)) & ~0xFFF;
            kernel_pt[j] = virt_addr_entry | 1;
        }

    }

    /* Set the global page directory variable */
    page_directory = base_ptr;

    /* Enable the page directory */
    vmem_enable_page_dir(base_ptr);

    printf("Paging Enabled. First %d KB of kernel identity-mapped.\n", IDENTITY_MAP_SIZE / 1024);
}

The last step is enabling paging by using the CPU's CR0 register. I wrote this function in FASM. Notice that it's called in the last line of the previous function.

format elf
use32

include 'ccall.inc'

section '.text' executable

    public vmem_enable_page_dir

    extrn printf

    ; Enable the page directory
    ; Since we're using fastcall in gcc, we expect the page directory to be in ecx
    ; See https://gcc.gnu.org/onlinedocs/gcc-4.3.2//gcc/Function-Attributes.html#Function-Attributes
    vmem_enable_page_dir:
        PUSHAD

        mov eax, ecx
        mov cr3, eax
        
        ;ccall printf, msg, ecx
        
        mov eax, cr0
        or eax, 0x80000001
        mov cr0, eax

        POPAD
        ret

section '.rodata'
    msg db "Page Directory Address %x",0xA,0

Also important: Since I needed this function to play nice with GCC, I'm using fastcall conventions so the argument always ends up in register ECX versus sometimes being put on the stack. Setting the CR3 register to an undefined value in ECX is less than ideal.

extern void vmem_enable_page_dir(uint32_t* page_dir) __attribute__((fastcall));

...

/* Set the global page directory variable */
page_directory = base_ptr;

/* Enable the page directory */
vmem_enable_page_dir(base_ptr);

Testing everything out

I wrote a few tests to make sure the address translations and everything work correctly.

And it does! That's now the majority of baseline memory management stuff out of the way! I also wrote a function to test page faulting, which works as intended by leading to the correct interrupt being called.

The next step after this is writing a simple filesystem for the operating system.