Chapter 11: Memory Management

Introduction

Memory management is one of the most critical responsibilities of an operating system. It involves allocating memory to processes, protecting processes from each other, enabling efficient use of limited RAM, and providing each process with the illusion of having unlimited memory. Understanding memory management is essential for system programmers working on kernels, drivers, or low-level applications.

Why This Matters

Every program you run requires memory. The OS must decide where in RAM to place code and data, how to prevent programs from interfering with each other, and how to handle situations where RAM is insufficient. Modern memory management enables multitasking, security, and efficient resource use. Without it, only one program could run at a time, and a single bug could crash the entire system.

How to Study This Chapter

1. Think visually - Draw memory layouts and page tables
2. Understand abstraction layers - Physical vs virtual addresses
3. Follow the translation - Virtual address → physical address
4. Experiment - Use tools to inspect process memory

Physical vs Virtual Memory

Physical Memory

Physical memory is the actual RAM installed in your computer. Addresses directly correspond to RAM chips.

Physical Address Space:
+-------------------+ 0xFFFFFFFF (4GB on 32-bit)
|                   |
|   Available RAM   |
|                   |
+-------------------+
|   Device Memory   | Memory-mapped I/O
+-------------------+
|   ROM/BIOS        |
+-------------------+ 0x00000000

Limitations of physical addressing:

• Each process sees all other processes' memory
• No protection between programs
• Fixed memory locations (hard to relocate programs)
• Limited by physical RAM size

Virtual Memory

Virtual memory gives each process its own private address space. The CPU's Memory Management Unit (MMU) translates virtual addresses to physical addresses.

Process A Virtual Space:        Physical RAM:
+-------------------+ 0xFFFFFFFF
|      Kernel       |              +-------------+
+-------------------+              |   Kernel    |
|      Stack        |              +-------------+
+-------------------+              | Process A   |
|       Heap        |    ------>   |   Pages     |
+-------------------+              +-------------+
|       Data        |              | Process B   |
+-------------------+              |   Pages     |
|       Code        |              +-------------+
+-------------------+ 0x00000000   |    Free     |
                                   +-------------+

Advantages:

• Each process has isolated address space
• Protection from other processes
• Can use more memory than physical RAM (swap)
• Simplifies programming (consistent addresses)

Memory Management Unit (MMU)

The MMU is hardware that translates virtual addresses to physical addresses.

Address Translation Process

Virtual Address
     |
     v
+----------+
|   MMU    |  <--- Page Tables (in RAM)
+----------+
     |
     v
Physical Address
     |
     v
   RAM Access

Translation Steps:

1. Program uses virtual address
2. MMU looks up mapping in page table
3. MMU produces physical address
4. RAM access completes

If no mapping exists, MMU triggers page fault exception.

Paging

Paging divides memory into fixed-size blocks called pages (typically 4 KB).

Concepts

• Page: Fixed-size block of virtual memory (e.g., 4 KB)
• Frame: Fixed-size block of physical memory (same size as page)
• Page Table: Data structure mapping pages to frames

Simple Page Table

Virtual address breakdown:

Virtual Address (32-bit):
+----------------------+----------------+
| Page Number (20 bit) | Offset (12 bit)|
+----------------------+----------------+

With 4 KB pages (2^12 bytes), offset is 12 bits. Remaining bits are page number.

Example translation:

Virtual Address: 0x00403004
Page Number: 0x00403 (bits 31-12)
Offset: 0x004 (bits 11-0)

Page Table Lookup:
  Page 0x00403 → Frame 0x12345

Physical Address: 0x12345004
  (Frame number 0x12345 + Offset 0x004)

Page Table Entry (PTE)

Each entry in the page table contains:

+--------+---+---+---+---+---+---------+
| Frame  | P | R | W | U | D | Reserved|
+--------+---+---+---+---+---+---------+

P = Present (1 if page is in RAM)
R = Read permission
W = Write permission
U = User mode accessible
D = Dirty (modified)

Example:

struct page_table_entry {
    uint32_t frame_number : 20;  // Physical frame number
    uint32_t present      : 1;   // Page is in RAM
    uint32_t writable     : 1;   // Write permission
    uint32_t user         : 1;   // User mode accessible
    uint32_t accessed     : 1;   // Recently accessed
    uint32_t dirty        : 1;   // Modified
    uint32_t reserved     : 7;
};

Multi-Level Paging

Single-level page tables waste memory. For 32-bit addresses with 4 KB pages, you need 1 million entries per process (4 MB per process!).

Two-Level Page Table

Split page number into directory and table indices.

Virtual Address (32-bit, x86):
+------------+------------+----------------+
| Directory  |   Table    |    Offset      |
| (10 bits)  | (10 bits)  |   (12 bits)    |
+------------+------------+----------------+

Translation process:

1. Use directory index to find page table address
2. Use table index to find frame number
3. Combine frame number with offset

Advantages:

• Only allocate tables for used memory regions
• Saves space for sparse address spaces

x64 Four-Level Paging

Modern 64-bit systems use 4-level paging (48-bit virtual addresses):

Virtual Address (x64):
+------+------+------+------+----------------+
| PML4 | PDPT |  PD  |  PT  |    Offset      |
| 9bit | 9bit | 9bit | 9bit |   (12 bits)    |
+------+------+------+------+----------------+

PML4 = Page Map Level 4
PDPT = Page Directory Pointer Table
PD   = Page Directory
PT   = Page Table

CR3 register holds the physical address of the PML4 table.

Translation Lookaside Buffer (TLB)

Page table lookups are expensive (multiple memory accesses per translation). The TLB is a cache of recent translations.

How TLB Works

Virtual Address
     |
     v
+---------+     Hit?
|   TLB   |-----------> Physical Address (fast!)
+---------+
     |
     | Miss
     v
+-------------+
| Page Tables | (slow, multiple memory accesses)
+-------------+
     |
     v
Physical Address
     |
Update TLB with new mapping

TLB management:

• On context switch, TLB must be flushed (or use ASIDs)
• invlpg instruction invalidates TLB entry (x86/x64)
• TLB misses are costly; optimize for locality

Page Faults

A page fault occurs when:

1. Page not present in RAM (swapped out)
2. Invalid access (protection violation)
3. Page never allocated

Page Fault Handler

void page_fault_handler(uint32_t error_code, uint32_t faulting_address) {
    if (error_code & 0x1) {
        // Page was present, but protection violation
        printf("Access violation at 0x%x\n", faulting_address);
        kill_process();
    } else {
        // Page not present - load from disk
        load_page_from_disk(faulting_address);
        update_page_table(faulting_address);
        // Return to faulting instruction (retry)
    }
}

Types of Page Faults

1. Minor fault: Page is in RAM but not mapped (just update page table)
2. Major fault: Page must be loaded from disk (slow)
3. Invalid fault: Illegal access (segmentation fault)

Demand Paging and Swapping

Demand Paging

Pages are loaded into RAM only when accessed (lazy loading).

Process starts:
  - Only load essential pages (code, initial stack)
  - Mark other pages as "not present"

On first access to page:
  - Page fault occurs
  - OS loads page from disk
  - Updates page table
  - Resumes execution

Benefits:

• Faster program startup
• Use less RAM
• Can run programs larger than RAM

Swapping

When RAM is full, OS moves pages to disk (swap space) to free RAM.

Page Replacement Algorithms:

1. FIFO (First-In-First-Out): Evict oldest page
2. LRU (Least Recently Used): Evict least recently used page
3. Clock: Approximation of LRU using "accessed" bit
4. Optimal: Evict page not used for longest time (theoretical)

Example: LRU

struct page_info {
    uint32_t frame_number;
    uint64_t last_access_time;
    bool dirty;
};

uint32_t evict_page_lru(struct page_info *pages, int count) {
    uint32_t oldest_index = 0;
    uint64_t oldest_time = pages[0].last_access_time;

    for (int i = 1; i < count; i++) {
        if (pages[i].last_access_time < oldest_time) {
            oldest_time = pages[i].last_access_time;
            oldest_index = i;
        }
    }

    if (pages[oldest_index].dirty) {
        write_page_to_disk(pages[oldest_index].frame_number);
    }

    return oldest_index;
}

Memory Allocation Strategies

Buddy Allocator

Efficiently manages free memory blocks by splitting into powers of 2.

#define MAX_ORDER 10  // Up to 2^10 pages

struct free_area {
    struct list_head free_list;  // List of free blocks
    unsigned long nr_free;        // Number of free blocks
};

struct free_area free_area[MAX_ORDER + 1];

// Allocate 2^order pages
void *alloc_pages(int order) {
    int current_order = order;

    // Find a block of sufficient size
    while (current_order <= MAX_ORDER) {
        if (!list_empty(&free_area[current_order].free_list)) {
            // Found a block
            struct page *page = list_first_entry(&free_area[current_order].free_list);
            list_del(&page->list);

            // Split if necessary
            while (current_order > order) {
                current_order--;
                struct page *buddy = page + (1 << current_order);
                list_add(&buddy->list, &free_area[current_order].free_list);
            }

            return page;
        }
        current_order++;
    }

    return NULL;  // Out of memory
}

Slab Allocator

Optimized for frequently allocated objects of same size (e.g., process descriptors).

struct kmem_cache {
    size_t object_size;
    struct list_head slabs_full;
    struct list_head slabs_partial;
    struct list_head slabs_free;
};

void *kmem_cache_alloc(struct kmem_cache *cache) {
    struct slab *slab;

    // Try partial slabs first
    if (!list_empty(&cache->slabs_partial)) {
        slab = list_first_entry(&cache->slabs_partial);
    } else if (!list_empty(&cache->slabs_free)) {
        slab = list_first_entry(&cache->slabs_free);
        list_move(&slab->list, &cache->slabs_partial);
    } else {
        // Allocate new slab
        slab = allocate_slab(cache->object_size);
        list_add(&slab->list, &cache->slabs_partial);
    }

    void *obj = slab_alloc_object(slab);

    if (slab_is_full(slab)) {
        list_move(&slab->list, &cache->slabs_full);
    }

    return obj;
}

x86/x64 Specific Memory Management

Setting Up Paging on x86

; Enable paging on x86
section .text
global enable_paging

enable_paging:
    ; Load page directory address into CR3
    mov eax, [page_directory]
    mov cr3, eax

    ; Enable paging by setting bit 31 of CR0
    mov eax, cr0
    or eax, 0x80000000          ; Set PG bit
    mov cr0, eax

    ret

section .data
align 4096
page_directory:
    times 1024 dd 0             ; 1024 page directory entries

Setting Up Paging on x64

; Enable long mode paging on x64
section .text
bits 32
global enable_long_mode

enable_long_mode:
    ; Load PML4 into CR3
    mov eax, pml4_table
    mov cr3, eax

    ; Enable PAE (Physical Address Extension)
    mov eax, cr4
    or eax, 1 << 5              ; Set PAE bit
    mov cr4, eax

    ; Enable long mode in EFER MSR
    mov ecx, 0xC0000080         ; EFER MSR
    rdmsr
    or eax, 1 << 8              ; Set LM bit
    wrmsr

    ; Enable paging
    mov eax, cr0
    or eax, 1 << 31             ; Set PG bit
    mov cr0, eax

    ret

section .data
align 4096
pml4_table:
    dq pdpt_table + 3           ; Present, writable
    times 511 dq 0

align 4096
pdpt_table:
    dq pd_table + 3
    times 511 dq 0

align 4096
pd_table:
    dq pt_table + 3
    times 511 dq 0

align 4096
pt_table:
    times 512 dq 0

Reading Page Fault Information (x64)

// Page fault error code bits
#define PF_PRESENT   (1 << 0)  // Page was present
#define PF_WRITE     (1 << 1)  // Write access
#define PF_USER      (1 << 2)  // User mode access
#define PF_RESERVED  (1 << 3)  // Reserved bits set
#define PF_FETCH     (1 << 4)  // Instruction fetch

__attribute__((interrupt))
void page_fault_handler(struct interrupt_frame *frame, uint64_t error_code) {
    // Get faulting address from CR2
    uint64_t fault_addr;
    asm volatile("mov %%cr2, %0" : "=r"(fault_addr));

    printf("Page fault at 0x%lx (error code: 0x%lx)\n", fault_addr, error_code);

    if (!(error_code & PF_PRESENT)) {
        printf("  Page not present\n");
    }
    if (error_code & PF_WRITE) {
        printf("  Write access\n");
    }
    if (error_code & PF_USER) {
        printf("  User mode\n");
    }

    // Handle the fault...
}

ARM Memory Management

ARM MMU Configuration

// ARMv7 page table entry
#define PTE_TYPE_SMALL  (2 << 0)  // 4KB page
#define PTE_CACHEABLE   (1 << 2)
#define PTE_BUFFERABLE  (1 << 3)
#define PTE_AP_RW       (3 << 10) // Read/write access
#define PTE_SHARED      (1 << 16)

// Create page table entry for 4KB page
uint32_t create_pte(uint32_t phys_addr, bool writable, bool user) {
    uint32_t pte = (phys_addr & 0xFFFFF000) | PTE_TYPE_SMALL;

    if (writable) {
        pte |= PTE_AP_RW;
    }

    pte |= PTE_CACHEABLE | PTE_BUFFERABLE;

    return pte;
}

// Enable MMU on ARM
void enable_mmu(uint32_t *page_table) {
    // Set translation table base
    asm volatile("mcr p15, 0, %0, c2, c0, 0" :: "r"(page_table));

    // Set domain access control (all domains as manager)
    uint32_t dacr = 0xFFFFFFFF;
    asm volatile("mcr p15, 0, %0, c3, c0, 0" :: "r"(dacr));

    // Enable MMU
    uint32_t sctlr;
    asm volatile("mrc p15, 0, %0, c1, c0, 0" : "=r"(sctlr));
    sctlr |= 0x1;  // Set M bit
    asm volatile("mcr p15, 0, %0, c1, c0, 0" :: "r"(sctlr));
}

Memory Protection

Page Permissions

// x86/x64 page permissions
#define PAGE_PRESENT    (1 << 0)
#define PAGE_WRITE      (1 << 1)
#define PAGE_USER       (1 << 2)
#define PAGE_NOCACHE    (1 << 4)
#define PAGE_ACCESSED   (1 << 5)
#define PAGE_DIRTY      (1 << 6)
#define PAGE_NX         (1ULL << 63)  // No execute (x64)

uint64_t create_page_entry(uint64_t phys_addr, int perms) {
    uint64_t entry = (phys_addr & 0xFFFFFFFFF000ULL) | PAGE_PRESENT;

    if (perms & PERM_WRITE)
        entry |= PAGE_WRITE;
    if (perms & PERM_USER)
        entry |= PAGE_USER;
    if (perms & PERM_NO_EXEC)
        entry |= PAGE_NX;

    return entry;
}

Memory Regions

struct memory_region {
    uint64_t start;
    uint64_t end;
    uint32_t permissions;
};

#define PERM_READ  (1 << 0)
#define PERM_WRITE (1 << 1)
#define PERM_EXEC  (1 << 2)

// Typical process memory layout
struct memory_region process_regions[] = {
    { 0x0000000000400000, 0x0000000000500000, PERM_READ | PERM_EXEC },  // Code
    { 0x0000000000600000, 0x0000000000700000, PERM_READ | PERM_WRITE }, // Data
    { 0x0000000000800000, 0x0000000001000000, PERM_READ | PERM_WRITE }, // Heap
    { 0x00007FFFFFFFE000, 0x0000800000000000, PERM_READ | PERM_WRITE }, // Stack
};

Key Concepts

• Virtual memory gives each process isolated address space
• MMU translates virtual addresses to physical addresses
• Paging divides memory into fixed-size pages (typically 4 KB)
• Page tables store virtual-to-physical mappings
• Multi-level paging reduces page table memory overhead
• TLB caches recent address translations
• Page faults occur when accessing unmapped or swapped pages
• Demand paging loads pages only when needed
• Page replacement evicts pages when RAM is full

Common Mistakes

1. Forgetting alignment - Page tables must be page-aligned
2. Not flushing TLB - After changing page tables, invalidate TLB
3. Incorrect permissions - Setting wrong read/write/execute bits
4. Identity mapping errors - Initial bootloader mappings must be correct
5. Stack overflow - Not allocating enough guard pages
6. Shared memory issues - Forgetting cache coherency
7. Race conditions - Page table updates must be atomic

Debugging Tips

• Check CR2/fault address - Tells you what address caused page fault
• Verify page table entries - Print PTEs to see mappings
• Use QEMU monitor - info tlb, info mem commands
• Enable MMU logging - Many emulators can log MMU activity
• Test incrementally - Enable paging in stages
• Map kernel first - Ensure kernel is accessible after enabling paging
• Watch for recursive faults - Page fault handler accessing unmapped memory

Mini Exercises

1. Calculate virtual-to-physical translation for given address
2. Implement a simple single-level page table
3. Write code to set up two-level paging on x86
4. Create a function to map virtual page to physical frame
5. Implement a basic FIFO page replacement algorithm
6. Write page fault handler that prints fault information
7. Create identity mapping for first 4 MB of memory
8. Implement function to check if virtual address is mapped
9. Write code to allocate and free pages using bitmap
10. Create a simple buddy allocator for page frames

Review Questions

1. What's the difference between virtual and physical memory?
2. How does the MMU translate virtual addresses to physical addresses?
3. Why do modern systems use multi-level page tables?
4. What is a TLB and why is it necessary?
5. What are the different types of page faults?

Reference Checklist

By the end of this chapter, you should be able to:

• Explain virtual memory and its benefits
• Understand how MMU translates addresses
• Describe paging and page tables
• Implement multi-level paging
• Explain TLB and its role
• Handle page faults
• Understand demand paging and swapping
• Set up paging on x86/x64 or ARM
• Configure page permissions
• Debug memory management issues

Next Steps

With memory management understood, the next chapter explores how computers boot. You'll learn about BIOS, UEFI, bootloaders, and what happens from pressing the power button to loading an operating system kernel.

---

Key Takeaway: Memory management is the foundation of modern multitasking operating systems. Understanding virtual memory, paging, and the MMU is essential for kernel development and system-level programming.