Memory Management - cupidthecat/cupid-os GitHub Wiki

Memory Management

cupid-os implements a complete memory management system that provides physical memory allocation, virtual memory mapping, and dynamic heap allocation. The system is designed to be simple, educational, and transparent, allowing users to understand how modern operating systems manage memory.

Overview

The memory management system consists of three main components:

Physical Memory Manager (PMM): Tracks and allocates physical memory pages
Virtual Memory (Paging): Maps virtual addresses to physical addresses
Heap Allocator: Provides dynamic memory allocation (kmalloc/kfree)

Physical Memory Manager (PMM)

Bitmap-Based Allocation

cupid-os uses a bitmap to track the allocation status of physical memory pages:

#define BITMAP_SIZE (TOTAL_MEMORY_BYTES / PAGE_SIZE / 32)
static uint32_t page_bitmap[BITMAP_SIZE];

Memory range: First 32MB of physical memory
Page size: 4KB (4096 bytes)
Bitmap size: 256 bits (32-bit integers) = 8192 pages tracked
Bit mapping: 1 = allocated, 0 = free

Memory Layout

0x00000000 - 0x0009FFFF: Low memory (640KB)
  0x00000000 - 0x0007FFFF: Free (512KB)
  0x00080000 - 0x0009FFFF: Kernel + stack (128KB)

0x000A0000 - 0x000FFFFF: Video/BIOS area (384KB)
  0x000A0000 - 0x000BFFFF: VGA memory
  0x000C0000 - 0x000FFFFF: BIOS/ROM

0x00100000 - 0x02000000: Extended memory (31MB)
  Available for allocation (with some reserved regions)

Reserved Regions

During initialization, critical memory regions are marked as allocated:

void pmm_init(uint32_t kernel_end) {
    // Mark kernel region as allocated
    pmm_mark_region(0, kernel_end, 1);

    // Reserve VGA text buffer
    pmm_mark_region(0xB8000, 0xC0000, 1);

    // Reserve kernel stack
    pmm_mark_region(0x90000 - (16 * PAGE_SIZE), 0x90000, 1);

    // Reserve legacy video/BIOS hole
    pmm_mark_region(0xA0000, 0x100000, 1);
}

Allocation Functions

Single Page Allocation

void* pmm_alloc_page(void) {
    return pmm_alloc_contiguous(1);
}

Contiguous Page Allocation

void* pmm_alloc_contiguous(uint32_t page_count) {
    // Find contiguous free pages in bitmap
    // Mark them as allocated
    // Return physical address
}

Algorithm: First-fit contiguous allocation
Return value: Physical address of first page, or NULL if failed
Alignment: All allocations are page-aligned (4KB)

Page Deallocation

void pmm_free_page(void* address) {
    // Validate address
    // Clear corresponding bit in bitmap
}

Statistics Functions

uint32_t pmm_free_pages(void);    // Count free pages
uint32_t pmm_total_pages(void);   // Total pages available

Virtual Memory (Paging)

x86 Page Table Structure

cupid-os implements two-level paging:

Page Directory: 1024 entries, each pointing to a page table
Page Tables: 1024 entries each, pointing to physical pages

Virtual Address: 32 bits
┌─────────────────┬─────────────────┬─────────────────┐
│ Directory Index │  Table Index    │   Offset        │
│     (10 bits)   │    (10 bits)    │   (12 bits)     │
│   31        22  │  21         12  │  11          0  │
└─────────────────┴─────────────────┴─────────────────┘

Identity Mapping

cupid-os uses identity mapping where virtual addresses equal physical addresses:

static void map_page_identity(uint32_t address) {
    uint32_t directory_index = address >> 22;
    uint32_t table_index = (address >> 12) & 0x3FF;

    uint32_t* table = get_page_table(directory_index);
    table[table_index] = (address & 0xFFFFF000) | PAGE_PRESENT | PAGE_RW | PAGE_USER;
}

Virtual address: Same as physical address
Page size: 4KB
Permissions: Present, Read/Write, User accessible

Page Directory Setup

void paging_init(void) {
    // Allocate page directory
    page_directory = (uint32_t*)pmm_alloc_page();

    // Initialize to zero
    memset(page_directory, 0, PAGE_SIZE);

    // Identity map first 32MB
    for (uint32_t addr = 0; addr < IDENTITY_MAP_SIZE; addr += PAGE_SIZE) {
        map_page_identity(addr);
    }

    // Load page directory into CR3
    __asm__ volatile("mov %0, %%cr3" :: "r"(page_directory));

    // Enable paging (set PG bit in CR0)
    __asm__ volatile("mov %%cr0, %0" : "=r"(cr0));
    cr0 |= 0x80000000;
    __asm__ volatile("mov %0, %%cr0" :: "r"(cr0));
}

Page Table Entry Format

Each page table entry contains:

Bits	Field	Description
0	P	Present (1 = mapped)
1	RW	Read/Write (1 = writable)
2	US	User/Supervisor (1 = user accessible)
3	PWT	Page Write Through
4	PCD	Page Cache Disable
5	A	Accessed
6	D	Dirty
7	PAT	Page Attribute Table
8	G	Global
9-11	-	Available for OS use
12-31	Address	Physical page address (4KB aligned)

Heap Allocator

Block-Based Allocation

The heap uses a linked list of blocks with headers:

typedef struct heap_block {
    size_t size;           // Size of data area
    struct heap_block* next; // Next block in list
    uint8_t free;          // 1 = free, 0 = allocated
} heap_block_t;

Allocation Strategy

kmalloc

void* kmalloc(size_t size) {
    // Align size to 8 bytes
    size = align_up(size, 8);

    // Find suitable free block
    heap_block_t* block = find_free_block(size);

    // If no block found, request more memory from PMM
    if (!block) {
        block = heap_request_block(size);
    }

    // Split block if too large
    split_block(block, size);

    // Mark as allocated
    block->free = 0;

    // Return pointer to data area
    return (void*)((uint8_t*)block + sizeof(heap_block_t));
}

kfree

void kfree(void* ptr) {
    // Get block header
    heap_block_t* block = (heap_block_t*)((uint8_t*)ptr - sizeof(heap_block_t));

    // Mark as free
    block->free = 1;

    // Merge with adjacent free blocks
    merge_with_next(block);
}

Block Splitting

When allocating from a larger free block:

static void split_block(heap_block_t* block, size_t requested) {
    size_t total_needed = requested + sizeof(heap_block_t);

    if (block->size <= total_needed + HEAP_MIN_SPLIT) {
        return;  // Don't split if remaining space is too small
    }

    // Create new block in remaining space
    heap_block_t* new_block = (heap_block_t*)((uint8_t*)block + sizeof(heap_block_t) + requested);
    new_block->size = block->size - requested - sizeof(heap_block_t);
    new_block->next = block->next;
    new_block->free = 1;

    // Adjust original block
    block->size = requested;
    block->next = new_block;
}

Block Merging

When freeing adjacent blocks:

static void merge_with_next(heap_block_t* block) {
    if (!block || !block->next) return;

    uint8_t* block_end = (uint8_t*)block + sizeof(heap_block_t) + block->size;

    if (block_end == (uint8_t*)block->next && block->next->free) {
        // Adjacent and free - merge
        heap_block_t* next = block->next;
        block->size += sizeof(heap_block_t) + next->size;
        block->next = next->next;
    }
}

Memory Initialization Sequence

Kernel Startup

PMM Initialization: Set up bitmap, reserve kernel regions
Paging Setup: Create page directory, identity map memory
Heap Initialization: Allocate initial heap pages
Enable Paging: Load CR3, set PG bit in CR0

void kernel_main() {
    // ... other initialization

    // Initialize memory systems
    pmm_init(kernel_end);
    paging_init();
    heap_init(HEAP_INITIAL_PAGES);

    // Memory system ready
    // ... start shell
}

Memory Usage Examples

Basic Allocation

// Allocate a single page
void* page = pmm_alloc_page();
if (page) {
    // Use physical memory at 'page'
    // ...
    pmm_free_page(page);
}

// Allocate contiguous pages
void* buffer = pmm_alloc_contiguous(4);  // 16KB
if (buffer) {
    // Use 16KB of contiguous physical memory
    pmm_free_page(buffer);  // Note: only frees first page
}

// Dynamic heap allocation
char* string = (char*)kmalloc(100);
if (string) {
    strcpy(string, "Hello, World!");
    print(string);
    kfree(string);
}

Data Structure Allocation

typedef struct {
    int id;
    char name[32];
    void* data;
} my_struct_t;

// Allocate structure
my_struct_t* obj = (my_struct_t*)kmalloc(sizeof(my_struct_t));
if (obj) {
    obj->id = 42;
    strcpy(obj->name, "example");

    // Allocate additional data
    obj->data = kmalloc(1024);

    // ... use object ...

    // Clean up
    kfree(obj->data);
    kfree(obj);
}

Memory Diagnostics

PMM Statistics

uint32_t free = pmm_free_pages();
uint32_t total = pmm_total_pages();
print("Memory: ");
print_int(free);
print("/");
print_int(total);
print(" pages free\n");

Heap Inspection

Currently, heap statistics are not exposed, but could be added:

// Future enhancement: heap statistics
uint32_t heap_used_bytes(void);
uint32_t heap_free_bytes(void);
uint32_t heap_total_blocks(void);

Limitations and Future Enhancements

Current Limitations

Fixed memory size: Only manages first 32MB
Identity mapping only: No virtual address translation
No page protection: All pages have same permissions
Simple heap: No advanced features like garbage collection
No swapping: All memory must be resident

Potential Enhancements

Advanced PMM Features

Buddy allocator: More efficient for different allocation sizes
Defragmentation: Compact free memory regions
Memory zones: DMA-safe, high memory regions

Virtual Memory Features

Demand paging: Page in from disk when accessed
Page protection: Separate read/write/execute permissions
Virtual address spaces: Per-process address spaces
Memory-mapped files: Map files into virtual memory

Heap Improvements

Multiple heaps: Specialized allocators for different use cases
Debug features: Memory leak detection, buffer overrun checking
Alignment support: Allocate with specific alignment requirements
Statistics: Track allocation patterns and fragmentation

Debugging Memory Issues

Common Problems

Double Free

void* ptr = kmalloc(100);
// ... use ptr ...
kfree(ptr);
// ... later ...
kfree(ptr);  // Error: double free

Symptoms: Heap corruption, crashes on subsequent allocations

Use After Free

void* ptr = kmalloc(100);
kfree(ptr);
// ... later ...
*ptr = 42;  // Error: accessing freed memory

Symptoms: Data corruption, page faults

Buffer Overflow

char* buffer = (char*)kmalloc(10);
for (int i = 0; i < 20; i++) {
    buffer[i] = 'x';  // Error: overflow
}

Symptoms: Heap corruption, crashes in unrelated code

Debugging Techniques

Memory Inspection

// Check if address is allocated
void* ptr = some_address;
if ((uint32_t)ptr < TOTAL_MEMORY_BYTES) {
    uint32_t page_index = (uint32_t)ptr / PAGE_SIZE;
    if (bitmap_test(page_index)) {
        print("Page is allocated\n");
    } else {
        print("Page is free\n");
    }
}

Heap Validation

// Walk heap and check consistency
heap_block_t* current = heap_head;
while (current) {
    if (current->size == 0) {
        print("Error: zero-size block\n");
        break;
    }
    current = current->next;
}

Page Fault Analysis

When page faults occur, use the fault shell to inspect:

CR2: Faulting address
Error code: Type of access attempted
EIP: Code that caused the fault

Performance Considerations

Allocation Speed

PMM: O(n) for allocation (bitmap scan), O(1) for free
Heap: O(n) for allocation (list traversal), O(1) for free
Splitting/merging: Reduces fragmentation but adds overhead

Memory Efficiency

Bitmap overhead: 1 bit per 4KB page (0.003% overhead)
Heap overhead: 12 bytes per allocation (heap_block_t)
Alignment waste: Up to 7 bytes per kmalloc due to 8-byte alignment

Fragmentation

External fragmentation: PMM may have scattered free pages
Internal fragmentation: Heap blocks may waste space
Mitigation: Block splitting and merging reduce fragmentation

References

Intel Architecture Manuals: Memory management specifications
OSDev Wiki: x86 paging and memory management guides
Knuth's Art of Computer Programming: Memory allocation algorithms

For more information about memory-related features:

Page Fault Handler - Interactive fault handling
Interrupts and Exceptions - Exception processing
Development Guide - Memory usage patterns