Memory Management Deep Dive

This guide explains TilekarOS's three-layered memory management stack, spanning from physical hardware frames to user-space heap allocation.

1. Physical Memory Manager (PMM)

Source File: memory.c

The PMM is the lowest layer of memory management. It treats the entire 4GB RAM as a series of 4KB "frames."

Bitmap-Based Allocation

TilekarOS uses a Bitmap (physical_memory_bitmap) to track free frames. Each bit represents one 4KB frame: - 0: Free - 1: Allocated

Code Preview: memory.c (PMM Implementation)

#include "memory.h"
#include <stdbool.h>
#include <string.h>
#include "utils.h"
#include <stddef.h>

/*
 * Physical Memory Manager (PMM) Configuration
 *
 * We use a bitmap to track free/allocated physical frames.
 * Each bit corresponds to one 4KB page frame.
 *
 * Max RAM = 4GB (0x100000000)
 * Total Frames = 4GB / 4KB = 1,048,576 frames
 * Bitmap Size = 1,048,576 / 8 bits per byte = 131,072 bytes (128KB)
 */
#define TOTAL_PAGE_FRAMES (0x100000000 / PAGE_SIZE)
#define BITMAP_SIZE_BYTES (TOTAL_PAGE_FRAMES / 8)

static uint8_t physical_memory_bitmap[BITMAP_SIZE_BYTES];

static uint32_t page_frame_min; // Lowest frame index available for allocation
static uint32_t page_frame_max; // Highest frame index available (based on RAM size)
static uint32_t total_allocated; // Counter for allocated frames

static uint32_t total_mapped_pages; // Counter for mapped virtual pages

/*
 * Page Table Management
 *
 * We reserve a pool of page tables to be used by the kernel.
 * Each Page Directory Entry (PDE) points to a Page Table.
 * A Page Table contains 1024 Page Table Entries (PTEs).
 */
#define NUM_PAGE_DIRS 256
static uint32_t page_tables[NUM_PAGE_DIRS][1024] __attribute__((aligned(4096)));
static uint8_t page_tables_used[NUM_PAGE_DIRS];

/**
 * init_pmm - Initialize the Physical Memory Manager (PMM).
 * @mem_low: The starting physical address of free memory.
 * @mem_high: The ending physical address of available memory.
 *
 * Marks the range of available memory based on the boot information.
 */
static void init_pmm(uint32_t mem_low, uint32_t mem_high) {
    page_frame_min = CEIL_DIV(mem_low, PAGE_SIZE);
    page_frame_max = mem_high / PAGE_SIZE;
    total_allocated = 0;

    // Clear the bitmap (all frames free by default)
    // In a real PMM, we should mark kernel space as used first.
    memset(physical_memory_bitmap, 0, sizeof(physical_memory_bitmap));
}

/*
 * flush_tlb_entry - Invalidate a TLB entry
 * @vaddr: Virtual address to invalidate
 */
void flush_tlb_entry(uint32_t vaddr) {
    asm volatile("invlpg (%0)" :: "r"(vaddr) : "memory");
}

uint32_t* memory_get_current_pagedir(void) {
    uint32_t pd_phys;
    asm volatile("mov %%cr3, %0": "=r"(pd_phys));

    // Convert physical address to virtual address
    // This assumes the kernel is mapped at KERNEL_START
    return (uint32_t*)(pd_phys + KERNEL_START);
}

void memory_set_pagedir(uint32_t* pd) {
    // Convert virtual address to physical address
    uint32_t pd_phys = (uint32_t)pd - KERNEL_START;
    asm volatile("mov %0, %%cr3" :: "r"(pd_phys));
}

#define MAX_ACTIVE_PAGEDIRS 256
static uint32_t active_pagedirs[MAX_ACTIVE_PAGEDIRS];
static int active_pagedir_count = 0;

uint32_t* memory_create_user_pagedir(void) {
    uint32_t pd_phys = pmm_alloc_page_frame();
    if (!pd_phys) return NULL;

    // We temporarily map the new page directory to 0xE0000000 so we can initialize it.
    memory_map_page(0xE0000000, pd_phys, PAGE_FLAG_WRITE | PAGE_FLAG_PRESENT);
    uint32_t* pd = (uint32_t*)0xE0000000;

    // Clear the lower 3GB (user space PDEs)
    memset(pd, 0, 768 * sizeof(uint32_t));

    // Copy the upper 1GB (kernel space PDEs) from initial_page_dir
    for (int i = 768; i < 1024; i++) {
        pd[i] = initial_page_dir[i];
    }

    // Set up recursive mapping for the new directory
    pd[1023] = pd_phys | PAGE_FLAG_PRESENT | PAGE_FLAG_WRITE;

    // Unmap the temporary mapping
    uint32_t pd_index = 0xE0000000 >> 22;
    uint32_t pt_index = (0xE0000000 >> 12) & 0x3FF;
    uint32_t* pt = RECURSIVE_PAGE_TABLE(pd_index);
    pt[pt_index] = 0;
    flush_tlb_entry(0xE0000000);

    if (active_pagedir_count < MAX_ACTIVE_PAGEDIRS) {
        active_pagedirs[active_pagedir_count++] = pd_phys;
    }

    return (uint32_t*)(pd_phys + KERNEL_START);
}

static void memory_sync_pagedirs(void) {
    uint32_t flags = interrupt_save();

    // We use PDE 1022 of initial_page_dir to temporarily map other page directories
    // PDE 1022 corresponds to virtual address 0xFF800000.
    // When used as a Page Table via recursive mapping, its contents are visible at 0xFFFFE000.
    for (int i = 0; i < active_pagedir_count; i++) {
        uint32_t pd_phys = active_pagedirs[i];

        initial_page_dir[1022] = pd_phys | PAGE_FLAG_PRESENT | PAGE_FLAG_WRITE;
        flush_tlb_entry(0xFFFFE000); 

        uint32_t* target_pd = (uint32_t*)0xFFFFE000;

        // Copy kernel PDEs (768 to 1021).
        // 1022 is our temporary mapping, skip it.
        // 1023 is the recursive mapping, keep it untouched.
        for (int j = 768; j < 1022; j++) {
            target_pd[j] = initial_page_dir[j];
        }
    }

    // Clear the temporary mapping
    initial_page_dir[1022] = 0;
    flush_tlb_entry(0xFFFFE000);

    interrupt_restore(flags);
}

uint32_t pmm_alloc_page_frame(void) {
    uint32_t flags = interrupt_save();

    // Calculate start/end bytes in the bitmap
    uint32_t start_byte = page_frame_min / 8;
    uint32_t end_byte = (page_frame_max + 7) / 8;

    for (uint32_t b = start_byte; b < end_byte; b++) {
        uint8_t byte = physical_memory_bitmap[b];

        // Skip if all bits set (full)
        if (byte == 0xFF) {
            continue;
        }

        for (uint32_t i = 0; i < 8; i++) {
            // Check if bit 'i' is used (1) or free (0)
            bool used = (byte >> i) & 1;

            if (!used) {
                uint32_t frame_index = b * 8 + i;

                // Ensure we don't go past the max or below the min
                if (frame_index < page_frame_min) continue;
                if (frame_index >= page_frame_max) break;

                // Mark as used
                physical_memory_bitmap[b] |= (1 << i);
                total_allocated++;

                interrupt_restore(flags);
                return frame_index * PAGE_SIZE;
            }
        }
    }

    interrupt_restore(flags);
    return 0; // Out of memory
}

void memory_map_page(uint32_t virtual_addr, uint32_t phys_addr, uint32_t flags) {
    uint32_t intr_flags = interrupt_save();

    uint32_t pd_index = virtual_addr >> 22;
    uint32_t pt_index = (virtual_addr >> 12) & 0x3FF;

    uint32_t* page_dir = RECURSIVE_PAGE_DIR;
    uint32_t* pt = RECURSIVE_PAGE_TABLE(pd_index);

    // If mapping kernel space, ensure we are using the initial page directory
    // to keep global kernel mappings consistent.
    uint32_t* prev_pagedir = NULL;
    if (virtual_addr >= KERNEL_START) {
        prev_pagedir = memory_get_current_pagedir();
        if (prev_pagedir != initial_page_dir) {
            memory_set_pagedir(initial_page_dir);
        }
    }

    // Check if the page table is present in the directory
    if (!(page_dir[pd_index] & PAGE_FLAG_PRESENT)) {
        // Allocate a new page table
        uint32_t pt_phys = pmm_alloc_page_frame();
        if (!pt_phys) {
            interrupt_restore(intr_flags);
            return; // OOM
        }

        // Map the new page table into the directory
        page_dir[pd_index] = pt_phys | PAGE_FLAG_PRESENT | PAGE_FLAG_WRITE | (flags & PAGE_FLAG_OWNER) | (flags & PAGE_FLAG_USER);

        flush_tlb_entry((uint32_t)pt);

        // Clear the new page table
        memset(pt, 0, PAGE_SIZE);
    } else if (page_dir[pd_index] & (1 << 7)) {
        if (prev_pagedir != NULL && prev_pagedir != initial_page_dir) {
            memory_set_pagedir(prev_pagedir);
        }
        interrupt_restore(intr_flags);
        return;
    }

    // Map the page
    pt[pt_index] = phys_addr | PAGE_FLAG_PRESENT | flags;
    total_mapped_pages++;
    flush_tlb_entry(virtual_addr);

    // Restore previous page directory if we switched
    if (prev_pagedir != NULL && prev_pagedir != initial_page_dir) {
        memory_sync_pagedirs();
        memory_set_pagedir(prev_pagedir);
    }

    interrupt_restore(intr_flags);
}

uint32_t memory_get_phys(uint32_t virtual_addr) {
    uint32_t pd_index = virtual_addr >> 22;
    uint32_t pt_index = (virtual_addr >> 12) & 0x3FF;

    uint32_t* page_dir = RECURSIVE_PAGE_DIR;
    if (!(page_dir[pd_index] & PAGE_FLAG_PRESENT)) return 0;

    uint32_t* pt = RECURSIVE_PAGE_TABLE(pd_index);
    if (!(pt[pt_index] & PAGE_FLAG_PRESENT)) return 0;

    return (pt[pt_index] & ~0xFFF) | (virtual_addr & 0xFFF);
}

/*
 * init_memory - Initialize the memory system (Paging + PMM)
 * @mem_total_kb: Total available RAM in KB
 * @physical_alloc_start: Physical address where free allocation starts
 */
void init_memory(uint32_t mem_total_kb, uint32_t physical_alloc_start) {
    // 1. Unmap the identity mapping of the first 4MB (0-4MB).
    total_mapped_pages = 0;
    initial_page_dir[0] = 0;
    flush_tlb_entry(0);

    // 2. Set up recursive page directory mapping.
    uint32_t pd_phys_addr = ((uint32_t)initial_page_dir - KERNEL_START);
    initial_page_dir[1023] = pd_phys_addr | PAGE_FLAG_PRESENT | PAGE_FLAG_WRITE;
    flush_tlb_entry(0xFFFFF000);

    // 3. Initialize Physical Memory Manager.
    // mem_total_kb is total memory including first 1MB.
    init_pmm(physical_alloc_start, mem_total_kb * 1024);

    // 4. Clear the pre-allocated page table pool.
    memset(page_tables, 0, sizeof(page_tables));
    memset(page_tables_used, 0, sizeof(page_tables_used));
}

Why we use a bitmap

A bitmap is memory-efficient and easy to implement. For 4GB of RAM, the bitmap only takes 128 KB of space.

---

2. Virtual Memory Manager (VMM) & Paging

Source File: memory.c

The VMM manages 32-bit Paging, allowing the kernel to map virtual addresses to physical ones.

Higher-Half Memory Layout

block-beta
    columns 1

    block:recursive["Recursive Mapping (0xFFC00000 - 0xFFFFFFFF)"]
        columns 1
        pd["Page Directory (0xFFFFF000)"]
        pt["Page Tables (0xFFC00000)"]
    end

    block:kernel_space["Kernel Space (0xC0000000 - 0xFFBFFFFF)"]
        columns 1
        heap["Kernel Heap (0xD0000000+)"]
        kcode["Kernel Code & Data (0xC0100000+)"]
    end

    block:user_space["User Space (0x00000000 - 0xBFFFFFFF)"]
        columns 1
        ustack["User Stack"]
        ucode["User Code & Data"]
    end

Memory Layout Details

block-beta
    columns 1

    block:high_mem
        space
        text["High Memory (Available for Allocation)"]
        space
    end

    block:kernel_space_inner
        block:sections
            columns 3
            stack["Kernel Stack<br>(16 KB)"]
            bss[".bss Section<br>(Uninitialized)"]
            data[".data Section<br>(Initialized)"]
        end
        code[".text Section<br>(Kernel Code)"]
    end

    block:reserved
        vga["VGA Video Memory<br>(0xB8000 - 0xBFFFF)"]
        bios["BIOS Data Area & EBDA<br>(Reserved)"]
    end

Recursive Paging

TilekarOS implements Recursive Mapping for its Page Directory. The very last entry in the Page Directory (index 1023) points back to the Page Directory itself. See memory.h for the relevant constants.

This trick allows the kernel to access and modify page tables using special virtual addresses without needing to constantly map and unmap them.

• RECURSIVE_PAGE_DIR: 0xFFFFF000
• RECURSIVE_PAGE_TABLE(i): 0xFFC00000 + (i << 12)

graph TD
    VA[Virtual Address] --> VMM{VMM}
    VMM -->|Lookup PD| PD[Page Directory]
    PD -->|Lookup PT| PT[Page Table]
    PT -->|Frame Address| PA[Physical Memory]
    PA -->|Return Data| VA

Physical Address Translation

The kernel provides a memory_get_phys(uintptr_t vaddr) function. This is critical for DMA and low-level drivers that need to provide the actual physical memory addresses to hardware devices like the ATA controller.

OSDev Reference

For details on recursive mapping, see OSDev: Recursive Paging.

---

3. Kernel Heap (kmalloc)

Source File: kmalloc.c

The heap provides dynamic allocation for kernel objects using a First-Fit Linked List strategy.

Allocation Process (kmalloc):

1. First-Fit Search: Scans the block_header_t list for a free block that is large enough.
2. Splitting: If a block is much larger than requested, it is split into two, leaving the remainder free.
3. Heap Extension (heap_sbrk): If no suitable block is found, kmalloc requests more physical frames from the PMM and maps them into the virtual heap space (0xD0000000).

Code Preview: kmalloc.c

#include "kmalloc.h"
#include "utils.h"
#include "memory.h"
#include <string.h>
#include <stdbool.h>

#define ALIGN(x, a) (((x) + (a) - 1) & ~((a) - 1))
#define HEADER_SIZE (sizeof(block_header_t))

typedef struct block_header {
    size_t size;            // Payload size (excluding header)
    bool is_free;
    struct block_header *next;
    struct block_header *prev;
} block_header_t;

static block_header_t *head = NULL;
static void *heap_end = NULL;
static uintptr_t heap_mapped_top = 0;

static void* heap_sbrk(intptr_t increment);

void kmalloc_init(size_t initial_size) {
    heap_end = (void*)KERNEL_MALLOC;
    heap_mapped_top = KERNEL_MALLOC;
    head = NULL;

    if (initial_size > 0) {
        initial_size = ALIGN(initial_size, 4096);
        void* initial_block = heap_sbrk(initial_size);
        if (initial_block != (void*)-1) {
            head = (block_header_t*)initial_block;
            head->size = initial_size - HEADER_SIZE;
            head->is_free = true;
            head->next = NULL;
            head->prev = NULL;
        }
    }
}

static void* heap_sbrk(intptr_t increment) {
    if (increment == 0) return heap_end;

    uint32_t flags = interrupt_save();

    uintptr_t old_break = (uintptr_t)heap_end;
    uintptr_t new_break = old_break + increment;

    if (new_break > heap_mapped_top) {
        uintptr_t new_mapped_top = ALIGN(new_break, PAGE_SIZE);

        for (uintptr_t addr = heap_mapped_top; addr < new_mapped_top; addr += PAGE_SIZE) {
            uint32_t phys = pmm_alloc_page_frame();
            if (!phys) {
                interrupt_restore(flags);
                return (void*)-1; // Out of memory
            }
            memory_map_page(addr, phys, PAGE_FLAG_WRITE | PAGE_FLAG_PRESENT | PAGE_FLAG_OWNER);
        }
        heap_mapped_top = new_mapped_top;
    }

    heap_end = (void*)new_break;
    interrupt_restore(flags);
    return (void*)old_break;
}

void* kmalloc(size_t size) {
    if (size == 0) return NULL;

    size = ALIGN(size, 8);

    uint32_t flags = interrupt_save();

    block_header_t *current = head;
    block_header_t *last = NULL;

    // First fit search
    while (current) {
        if (current->is_free && current->size >= size) {
            // Found a free block. Can we split it?
            if (current->size >= size + HEADER_SIZE + 8) {
                block_header_t *new_block = (block_header_t*)((uint8_t*)current + HEADER_SIZE + size);
                new_block->size = current->size - size - HEADER_SIZE;
                new_block->is_free = true;
                new_block->next = current->next;
                new_block->prev = current;

                if (new_block->next) {
                    new_block->next->prev = new_block;
                }

                current->size = size;
                current->next = new_block;
            }
            current->is_free = false;
            interrupt_restore(flags);
            return (void*)(current + 1);
        }
        last = current;
        current = current->next;
    }

    // No free block found, extend heap.
    if (last && last->is_free) {
        size_t needed = size - last->size;
        void* res = heap_sbrk(needed);
        if (res == (void*)-1) {
            interrupt_restore(flags);
            return NULL;
        }
        last->size = size;
        last->is_free = false;
        interrupt_restore(flags);
        return (void*)(last + 1);
    }

    // Otherwise, allocate a completely new block
    size_t total_size = size + HEADER_SIZE;
    block_header_t *new_block = (block_header_t*)heap_sbrk(total_size);

    if (new_block == (void*)-1) {
        interrupt_restore(flags);
        return NULL; // OOM
    }

    new_block->size = size;
    new_block->is_free = false;
    new_block->next = NULL;
    new_block->prev = last;

    if (last) {
        last->next = new_block;
    } else {
        head = new_block;
    }

    interrupt_restore(flags);
    return (void*)(new_block + 1);
}

void* kmalloc_aligned(size_t size, size_t align) {
    if (size == 0) return NULL;
    if (align <= 8) return kmalloc(size); // Default alignment is 8

    // We allocate extra space to account for alignment and a potential new header
    size_t total_size = size + align + HEADER_SIZE;
    void* ptr = kmalloc(total_size);
    if (!ptr) return NULL;

    uintptr_t addr = (uintptr_t)ptr;
    uintptr_t aligned_addr = ALIGN(addr, align);

    if (aligned_addr == addr) return ptr;

    // This is a simplified aligned allocator. It doesn't allow kfree on the aligned pointer directly
    // unless we store the original pointer somewhere.
    // For now, let's just return the aligned pointer and assume it's for long-lived kernel structures.
    // TODO: Implement a proper aligned allocator that supports kfree.
    return (void*)aligned_addr;
}

void kfree(void* ptr) {
    if (!ptr) return;

    uint32_t flags = interrupt_save();

    block_header_t *block = (block_header_t*)ptr - 1;
    block->is_free = true;

    // Coalesce with next block
    if (block->next && block->next->is_free) {
        block->size += HEADER_SIZE + block->next->size;
        block->next = block->next->next;
        if (block->next) {
            block->next->prev = block;
        }
    }

    // Coalesce with previous block
    if (block->prev && block->prev->is_free) {
        block->prev->size += HEADER_SIZE + block->size;
        block->prev->next = block->next;
        if (block->next) {
            block->next->prev = block->prev;
        }
    }

    interrupt_restore(flags);
}


void* kcalloc(size_t nmemb, size_t size) {
    size_t total_size = nmemb * size;
    // Check for overflow
    if (nmemb != 0 && total_size / nmemb != size) return NULL;

    void *ptr = kmalloc(total_size);
    if (ptr) {
        memset(ptr, 0, total_size);
    }
    return ptr;
}

void* krealloc(void* ptr, size_t size) {
    if (!ptr) return kmalloc(size);
    if (size == 0) {
        kfree(ptr);
        return NULL;
    }

    block_header_t *block = (block_header_t*)ptr - 1;
    if (block->size >= size) {
        // We could split here if the new size is much smaller, but for now just return same ptr
        return ptr;
    }

    void *new_ptr = kmalloc(size);
    if (new_ptr) {
        memcpy(new_ptr, ptr, block->size);
        kfree(ptr);
    }
    return new_ptr;
}

Deallocation (kfree):

• Coalescing: When a block is freed, it is merged with its neighbors (if they are also free) to reduce fragmentation.

---

4. Test/Example: Stress-Testing the Heap

You can verify the heap's correctness by allocating large chunks and then freeing them to ensure coalescing works:

void test_heap() {
    // 1. Allocate 100 small chunks
    void* ptrs[100];
    for (int i = 0; i < 100; i++) {
        ptrs[i] = kmalloc(64);
    }

    // 2. Free alternating chunks (Creating gaps)
    for (int i = 0; i < 100; i += 2) {
        kfree(ptrs[i]);
    }

    // 3. Allocate a larger chunk (Should trigger coalescing)
    void* big = kmalloc(512);
    kfree(big);

    // 4. Free the rest
    for (int i = 1; i < 100; i += 2) {
        kfree(ptrs[i]);
    }
}

---

References

• OSDev: Paging
• OSDev: Physical Memory Manager
• Wikipedia: Memory Management Unit
• Wikipedia: C Dynamic Memory Allocation
• Wikipedia: Paging