rsnix: memory management — free-list heap, bitmap pages, paging adoption

- uefi.rs: full EfiMemoryType constants (0-14) + memory_type_name(); fix
  MEMORY_TYPE_LOADER_DATA from 6 to 2 per the UEFI spec
- memory.rs: replace the bump allocator with a first-fit free-list heap
  (splitting, coalescing, 8-byte back-pointer for alignment-safe free);
  add a bitmap physical page allocator (heap region reserved, page-0
  guard, aligned runs); grow the heap from the page allocator on demand
- paging.rs: identity page-table helpers — adopt_tables() rebuilds the
  firmware map into our own tables (OVMF maps its tables read-only, so
  the firmware tree can't be modified in place) and switches CR3;
  map_page/unmap_page/is_mapped with 2 MB/1 GB large-page splitting
- main.rs: boot self-tests for heap, pages, and paging

5 files changed, 1050 insertions, 42 deletions

diff --git a/rsdos/src/main.rs b/rsdos/src/main.rs
index 543556b..1169785 100644
--- a/rsdos/src/main.rs
+++ b/rsdos/src/main.rs
@@ -106,6 +106,38 @@ pub extern "efiapi" fn efi_main(image_handle: Handle, system_table: *mut SystemT
 
     dump_memory_summary();
 
+    if rsnix::memory::self_test() {
+        rsnix::serial_println!("heap: self-test OK (alloc/free/coalesce)");
+    } else {
+        rsnix::serial_println!("heap: self-test FAILED");
+    }
+
+    if rsnix::memory::init_page_allocator() {
+        rsnix::serial_println!("pages: bitmap allocator ready");
+    } else {
+        rsnix::serial_println!("pages: init FAILED");
+    }
+    if rsnix::memory::page_self_test() {
+        rsnix::serial_println!("pages: self-test OK (alloc/free/runs)");
+    } else {
+        rsnix::serial_println!("pages: self-test FAILED");
+    }
+
+    if rsnix::paging::adopt_tables() {
+        rsnix::serial_println!(
+            "pg: adopted own page tables (cr3={:#x})",
+            rsnix::paging::cr3()
+        );
+    } else {
+        rsnix::serial_println!("pg: adopt_tables FAILED");
+    }
+
+    if rsnix::paging::self_test() {
+        rsnix::serial_println!("pg: self-test OK (map/unmap/split)");
+    } else {
+        rsnix::serial_println!("pg: self-test FAILED");
+    }
+
     rsnix::serial_println!("boot: entering shell");
     shell::run();
 }
diff --git a/rsnix/src/lib.rs b/rsnix/src/lib.rs
index 0bc0cb9..d2dacf0 100644
--- a/rsnix/src/lib.rs
+++ b/rsnix/src/lib.rs
@@ -6,6 +6,7 @@ pub mod font;
 pub mod gop;
 pub mod interrupts;
 pub mod memory;
+pub mod paging;
 pub mod ps2;
 pub mod serial;
 pub mod uefi;
diff --git a/rsnix/src/memory.rs b/rsnix/src/memory.rs
index 39fd88d..d33c781 100644
--- a/rsnix/src/memory.rs
+++ b/rsnix/src/memory.rs
@@ -16,46 +16,247 @@ static mut MAP_KEY: usize = 0;
 static mut MAP_WORK_BUF: [u8; 65536] = [0u8; 65536];
 
 // ---------------------------------------------------------------------------
-// Bump allocator — no deallocation, just pointer advancement.
+// Free-list heap allocator — first fit, splitting, coalescing.
 // Used as Rust's #[global_allocator] once the heap region is set up.
+//
+// Every block (free or allocated) starts with a 16-byte header:
+//
+//     [ size: usize ][ free: usize ]
+//
+//   - `size` covers the whole block including the header.
+//   - `free` is 1 for free blocks, 0 for allocated blocks.
+//
+// Free blocks are linked into one address-sorted doubly-linked list; the
+// prev/next links live in the block's payload (free space is unused, so
+// it's free real estate for the links).  Allocating walks the list for the
+// first fit, splits the remainder into a fresh free block, and records the
+// block address in an 8-byte back-pointer immediately before the returned
+// payload — needed because alignment can leave a gap between the block
+// header and the payload.  Freeing reads the back-pointer to find its
+// block, marks it free, re-inserts it in address order, and coalesces with
+// any adjacent free neighbours.
+//
+// All sizes are rounded to 16 bytes so block boundaries stay 16-aligned
+// and every payload is at least 16-byte aligned.
 // ---------------------------------------------------------------------------
-struct BumpAllocator;
 
-unsafe impl Sync for BumpAllocator {}
+const HEADER_SIZE: usize = 16; // size + free flag
+const MINI_SIZE: usize = 8; // back-pointer before the payload
+const MIN_BLOCK: usize = 32; // smallest block we will create (header + links)
+const MIN_ALIGN: usize = 16;
 
-unsafe impl GlobalAlloc for BumpAllocator {
+/// Block header — first 16 bytes of every block.
+#[repr(C)]
+struct Header {
+    size: usize,
+    free: usize,
+}
+
+impl Header {
+    /// Where the free-list links live (only meaningful while free).
+    #[inline]
+    fn links(&self) -> *mut FreeLinks {
+        unsafe { (self as *const Header as *mut u8).add(HEADER_SIZE) as *mut FreeLinks }
+    }
+}
+
+/// Free-list links, stored in the payload of free blocks only.
+#[repr(C)]
+struct FreeLinks {
+    prev: *mut Header,
+    next: *mut Header,
+}
+
+/// Head of the address-sorted free list (lowest address first).
+static mut FREE_LIST: *mut Header = ptr::null_mut();
+
+/// Heap region bounds (set by `init_heap`).
+static mut HEAP_START: usize = 0;
+static mut HEAP_END: usize = 0;
+/// Total heap capacity — the original region plus pages added by growth.
+static mut HEAP_CAPACITY: usize = 0;
+
+/// Minimum pages `grow_heap` takes from the page allocator per growth.
+const HEAP_GROW_PAGES: usize = 64;
+
+#[inline]
+fn align_up(x: usize, a: usize) -> usize {
+    (x + a - 1) & !(a - 1)
+}
+
+/// Insert `block` into the address-sorted free list.
+/// Caller guarantees `block` is not already in the list.
+unsafe fn free_list_insert(block: *mut Header) {
+    let addr = block as usize;
+    let mut prev: *mut Header = ptr::null_mut();
+    let mut cur = FREE_LIST;
+    while !cur.is_null() && (cur as usize) < addr {
+        prev = cur;
+        cur = unsafe { (*(*cur).links()).next };
+    }
+    unsafe {
+        let links = (*block).links();
+        (*links).prev = prev;
+        (*links).next = cur;
+        if prev.is_null() {
+            FREE_LIST = block;
+        } else {
+            (*(*prev).links()).next = block;
+        }
+        if !cur.is_null() {
+            (*(*cur).links()).prev = block;
+        }
+    }
+}
+
+/// Unlink `block` from the free list.
+unsafe fn free_list_remove(block: *mut Header) {
+    unsafe {
+        let links = (*block).links();
+        let prev = (*links).prev;
+        let next = (*links).next;
+        if prev.is_null() {
+            FREE_LIST = next;
+        } else {
+            (*(*prev).links()).next = next;
+        }
+        if !next.is_null() {
+            (*(*next).links()).prev = prev;
+        }
+    }
+}
+
+/// Merge `block` with any adjacent free neighbours (both directions).
+/// `block` must already be in the free list.
+unsafe fn coalesce(block: *mut Header) {
+    unsafe {
+        // Absorb the next free block if it sits right after us.
+        let next = (*(*block).links()).next;
+        if !next.is_null() && (block as usize) + (*block).size == next as usize {
+            (*block).size += (*next).size;
+            let next_links = (*next).links();
+            (*(*block).links()).next = (*next_links).next;
+            if !(*next_links).next.is_null() {
+                (*(*(*next_links).next).links()).prev = block;
+            }
+        }
+        // Be absorbed by the previous free block if it ends right before us.
+        let prev = (*(*block).links()).prev;
+        if !prev.is_null() && (prev as usize) + (*prev).size == block as usize {
+            (*prev).size += (*block).size;
+            let block_links = (*block).links();
+            (*(*prev).links()).next = (*block_links).next;
+            if !(*block_links).next.is_null() {
+                (*(*(*block_links).next).links()).prev = prev;
+            }
+        }
+    }
+}
+
+/// First-fit search: find the first block big enough for `size` aligned to
+/// `align`, split it, and return the aligned payload (back-pointer written).
+/// Returns null when no block fits.
+unsafe fn alloc_from_free_list(size: usize, align: usize) -> *mut u8 {
+    unsafe {
+        let mut cur = FREE_LIST;
+        while !cur.is_null() {
+            let block = cur;
+            let block_size = (*block).size;
+            // Payload sits after the header + back-pointer, aligned up.
+            let payload = align_up(block as usize + HEADER_SIZE + MINI_SIZE, align);
+            if payload + size <= (block as usize) + block_size {
+                let consumed = payload + size - (block as usize);
+                let remainder = block_size - consumed;
+
+                free_list_remove(block);
+
+                if remainder >= MIN_BLOCK {
+                    // Split: carve the tail into a fresh free block.
+                    let rem = (payload + size) as *mut Header;
+                    (*rem).size = remainder;
+                    (*rem).free = 1;
+                    free_list_insert(rem);
+                    (*block).size = consumed;
+                }
+                (*block).free = 0;
+
+                // Back-pointer so `free` can find the block even when
+                // alignment left a gap before the payload.
+                *((payload as *mut usize).sub(1)) = block as usize;
+                return payload as *mut u8;
+            }
+            cur = (*(*block).links()).next;
+        }
+        ptr::null_mut()
+    }
+}
+
+/// Expand the heap by taking `pages` contiguous physical pages from the
+/// page allocator and adding them to the free list as one free block.
+/// Returns false when the page allocator can't provide them.
+unsafe fn grow_heap(pages: usize) -> bool {
+    unsafe {
+        if let Some(addr) = alloc_pages(pages) {
+            let block = addr as *mut Header;
+            (*block).size = pages * PAGE_SIZE;
+            (*block).free = 1;
+            free_list_insert(block);
+            coalesce(block);
+            HEAP_CAPACITY += pages * PAGE_SIZE;
+            true
+        } else {
+            false
+        }
+    }
+}
+
+/// The kernel heap allocator.
+struct Allocator;
+
+unsafe impl Sync for Allocator {}
+
+unsafe impl GlobalAlloc for Allocator {
     unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
-        let align = layout.align().max(16);
-        let size = layout.size();
+        let size = align_up(layout.size().max(1), MIN_ALIGN);
+        let align = layout.align().max(MIN_ALIGN);
         unsafe {
-            let a = (HEAP_CURSOR + align - 1) & !(align - 1);
-            let e = a + size;
-            if e > HEAP_END || e < a {
-                return ptr::null_mut();
+            // First fit; when the free list is exhausted, grow the heap
+            // from the page allocator and retry.  Growth is proportional
+            // to the request (min HEAP_GROW_PAGES), so large allocations
+            // converge quickly.
+            loop {
+                let p = alloc_from_free_list(size, align);
+                if !p.is_null() {
+                    return p;
+                }
+                let need = (size / PAGE_SIZE + 1).max(HEAP_GROW_PAGES);
+                if !grow_heap(need) {
+                    return ptr::null_mut();
+                }
             }
-            HEAP_CURSOR = e;
-            a as *mut u8
         }
     }
 
-    unsafe fn dealloc(&self, _ptr: *mut u8, _layout: Layout) {
-        // Bump allocator — cannot free individual allocations.
-        // Memory is reclaimed on reboot.  Good enough for now.
+    unsafe fn dealloc(&self, ptr: *mut u8, _layout: Layout) {
+        if ptr.is_null() {
+            return;
+        }
         unsafe {
-            core::ptr::read_volatile(&_ptr);
+            let block = *((ptr as *const usize).sub(1)) as *mut Header;
+            debug_assert!(
+                (*block).free == 0,
+                "heap: double free at {:#x}",
+                ptr as usize
+            );
+            (*block).free = 1;
+            free_list_insert(block);
+            coalesce(block);
         }
-        let _ = _layout;
     }
 }
 
 #[global_allocator]
-static ALLOCATOR: BumpAllocator = BumpAllocator;
-
-/// Heap bump allocator bounds (`static mut` accessed only inside
-/// `GlobalAlloc` impl, which is already `unsafe`).
-static mut HEAP_START: usize = 0;
-static mut HEAP_END: usize = 0;
-static mut HEAP_CURSOR: usize = 0;
+static ALLOCATOR: Allocator = Allocator;
 
 /// Capture the UEFI memory map into the static buffer.  Uses a pre-allocated
 /// .bss working buffer so no pool allocation (and thus no memory-map change)
@@ -131,7 +332,7 @@ pub fn capture_memory_map(bs: &BootServices) -> Result<usize, Status> {
     // Do NOT free anything — the static buffer stays.  Map key is still
     // valid because no pool allocation/free happened after GetMemoryMap.
 
-    init_bump_allocator();
+    init_heap();
     Ok(map_key)
 }
 
@@ -146,7 +347,7 @@ pub fn refresh_and_exit(bs: &BootServices, image_handle: Handle) -> Result<usize
     }
 }
 
-fn init_bump_allocator() {
+fn init_heap() {
     unsafe {
         let mut best_start = 0usize;
         let mut best_size = 0usize;
@@ -163,10 +364,18 @@ fn init_bump_allocator() {
         if best_size > 2 * 1024 * 1024 {
             let s = best_start + 2 * 1024 * 1024;
             let e = best_start + best_size;
-            if s < e {
+            if s < e && e - s >= MIN_BLOCK {
                 HEAP_START = s;
                 HEAP_END = e;
-                HEAP_CURSOR = s;
+                HEAP_CAPACITY = e - s;
+                // Seed the free list with one block covering the whole heap.
+                let block = s as *mut Header;
+                (*block).size = e - s;
+                (*block).free = 1;
+                let links = (*block).links();
+                (*links).prev = ptr::null_mut();
+                (*links).next = ptr::null_mut();
+                FREE_LIST = block;
             }
         }
     }
@@ -174,15 +383,8 @@ fn init_bump_allocator() {
 
 #[allow(dead_code)]
 pub fn allocate(size: usize) -> *mut u8 {
-    unsafe {
-        let a = (HEAP_CURSOR + 15) & !15;
-        let e = a + size;
-        if e > HEAP_END || e < a {
-            return ptr::null_mut();
-        }
-        HEAP_CURSOR = e;
-        a as *mut u8
-    }
+    let layout = unsafe { Layout::from_size_align_unchecked(size.max(1), MIN_ALIGN) };
+    unsafe { ALLOCATOR.alloc(layout) }
 }
 
 #[allow(dead_code)]
@@ -194,3 +396,390 @@ pub fn get_map() -> (&'static [MemoryDescriptor], usize) {
         )
     }
 }
+
+// ---------------------------------------------------------------------------
+// Heap statistics + self-test
+// ---------------------------------------------------------------------------
+
+/// Snapshot of current heap usage.
+#[derive(Debug, Clone, Copy)]
+pub struct HeapStats {
+    pub heap_start: usize,
+    pub heap_end: usize,
+    pub heap_size: usize,
+    pub free_bytes: usize,
+    pub free_blocks: usize,
+}
+
+/// Current heap usage — walks the free list (cheap, it stays short).
+pub fn heap_stats() -> HeapStats {
+    unsafe {
+        let mut free_bytes = 0usize;
+        let mut free_blocks = 0usize;
+        let mut cur = FREE_LIST;
+        while !cur.is_null() {
+            free_bytes += (*cur).size;
+            free_blocks += 1;
+            cur = (*(*cur).links()).next;
+        }
+        HeapStats {
+            heap_start: HEAP_START,
+            heap_end: HEAP_END,
+            heap_size: HEAP_CAPACITY,
+            free_bytes,
+            free_blocks,
+        }
+    }
+}
+
+/// Allocator smoke test — exercises alloc/free/coalesce without touching
+/// the heap itself (fixed-size stack arrays only).  Returns true on success.
+pub fn self_test() -> bool {
+    unsafe {
+        const N: usize = 128;
+        // (ptr, size, align) triplets — fixed array on the stack.
+        let mut blocks: [(usize, usize, usize); N] = [(0, 0, 0); N];
+
+        // Allocate a mixed batch: sizes 1..2048, aligns 16..2048.
+        let mut seed: u64 = 0x9E37_79B9_7F4A_7C15;
+        let mut n = 0usize;
+        for i in 0..N {
+            let size = ((seed as usize) % 2048) + 1;
+            seed = seed.wrapping_mul(6364136223846793005).wrapping_add(1);
+            let align = 16usize << (seed as usize % 8);
+            seed = seed.wrapping_mul(6364136223846793005).wrapping_add(1);
+            let layout = Layout::from_size_align(size, align).unwrap();
+            let p = ALLOCATOR.alloc(layout);
+            if p.is_null() {
+                break; // heap exhausted — stop
+            }
+            if !(p as usize).is_multiple_of(align) {
+                return false; // alignment violated
+            }
+            core::ptr::write_bytes(p, i as u8 + 1, size); // scribble
+            blocks[n] = (p as usize, size, align);
+            n += 1;
+        }
+        if n < 16 {
+            return false; // should easily fit in the heap
+        }
+
+        // Free every third block.
+        let mut i = 0;
+        while i < n {
+            let (ptr, size, align) = blocks[i];
+            let layout = Layout::from_size_align(size, align).unwrap();
+            ALLOCATOR.dealloc(ptr as *mut u8, layout);
+            blocks[i] = (0, 0, 0);
+            i += 3;
+        }
+
+        // Reallocate the freed slots — space must be reused.
+        for i in 0..n {
+            if blocks[i].0 != 0 {
+                continue; // still live
+            }
+            let size = ((seed as usize) % 2048) + 1;
+            seed = seed.wrapping_mul(6364136223846793005).wrapping_add(1);
+            let align = 16usize << (seed as usize % 8);
+            seed = seed.wrapping_mul(6364136223846793005).wrapping_add(1);
+            let layout = Layout::from_size_align(size, align).unwrap();
+            let p = ALLOCATOR.alloc(layout);
+            if p.is_null() {
+                return false; // failed to reuse freed space
+            }
+            if !(p as usize).is_multiple_of(align) {
+                return false;
+            }
+            core::ptr::write_bytes(p, 0x5A, size);
+            blocks[i] = (p as usize, size, align);
+        }
+
+        // Free everything and check the heap coalesces back to one block.
+        for (ptr, size, align) in blocks.iter() {
+            if *ptr == 0 {
+                continue;
+            }
+            let layout = Layout::from_size_align(*size, *align).unwrap();
+            ALLOCATOR.dealloc(*ptr as *mut u8, layout);
+        }
+        let stats = heap_stats();
+        stats.free_blocks == 1 && stats.free_bytes == stats.heap_size
+    }
+}
+
+// ---------------------------------------------------------------------------
+// Physical page allocator — bitmap over the usable (conventional) regions.
+// ---------------------------------------------------------------------------
+// One bit per 4 KB page: 0 = free, 1 = allocated.  The bitmap spans the whole
+// [lowest conventional page, highest conventional page] range; pages that are
+// NOT conventional inside that span stay marked allocated, so MMIO holes and
+// firmware-reserved gaps are never handed out.  The kernel heap region is also
+// reserved, keeping the heap and page allocators from double-allocating the
+// same RAM.
+// ---------------------------------------------------------------------------
+
+pub const PAGE_SIZE: usize = 4096;
+
+/// Bitmap storage (allocated once from the heap at init).
+static mut BITMAP: *mut u8 = ptr::null_mut();
+/// Number of bytes in the bitmap.
+static mut BITMAP_BYTES: usize = 0;
+/// Page number that bitmap bit 0 refers to.
+static mut BASE_PAGE: usize = 0;
+/// Number of pages covered by the bitmap.
+static mut SPAN_PAGES: usize = 0;
+/// Running count of free pages (kept in sync with the bitmap).
+static mut FREE_PAGES: usize = 0;
+
+/// Snapshot of physical page usage.
+#[derive(Debug, Clone, Copy)]
+pub struct PageStats {
+    pub base_page: usize,
+    pub span_pages: usize,
+    pub span_bytes: usize,
+    pub free_pages: usize,
+    pub used_pages: usize,
+}
+
+/// Current physical page usage.
+pub fn page_stats() -> PageStats {
+    unsafe {
+        PageStats {
+            base_page: BASE_PAGE,
+            span_pages: SPAN_PAGES,
+            span_bytes: SPAN_PAGES * PAGE_SIZE,
+            free_pages: FREE_PAGES,
+            used_pages: SPAN_PAGES.saturating_sub(FREE_PAGES),
+        }
+    }
+}
+
+/// Build the bitmap from the stashed memory map and reserve the heap.
+/// Returns false if there is no conventional memory or the bitmap cannot
+/// be allocated.
+pub fn init_page_allocator() -> bool {
+    unsafe {
+        // Lowest and highest conventional page numbers.
+        let mut low: usize = usize::MAX;
+        let mut high: usize = 0;
+        for i in 0..MAP_ENTRIES {
+            let d = &MEMORY_MAP[i];
+            if d.kind == MEMORY_TYPE_CONVENTIONAL {
+                let s = d.physical_start as usize;
+                let e = s + d.number_of_pages as usize * PAGE_SIZE;
+                if s < low {
+                    low = s;
+                }
+                if e > high {
+                    high = e;
+                }
+            }
+        }
+        if low == usize::MAX || high <= low {
+            return false;
+        }
+
+        let base_page = low / PAGE_SIZE;
+        let span_pages = high.div_ceil(PAGE_SIZE) - base_page;
+        let bytes = span_pages.div_ceil(8);
+
+        // The bitmap itself lives in the heap (one allocation, never freed).
+        // `bytes` >= 1 and align 16 is a power of two, so this cannot fail.
+        let layout = unsafe { Layout::from_size_align_unchecked(bytes, 16) };
+        let bm = ALLOCATOR.alloc(layout);
+        if bm.is_null() {
+            return false;
+        }
+
+        // Start everything allocated, then free only usable pages.
+        core::ptr::write_bytes(bm, 0xFF, bytes);
+
+        for i in 0..MAP_ENTRIES {
+            let d = &MEMORY_MAP[i];
+            if d.kind == MEMORY_TYPE_CONVENTIONAL {
+                let s = d.physical_start as usize / PAGE_SIZE;
+                let e = (d.physical_start as usize + d.number_of_pages as usize * PAGE_SIZE)
+                    .div_ceil(PAGE_SIZE);
+                for p in s..e {
+                    let idx = p - base_page;
+                    *bm.add(idx / 8) &= !(1 << (idx % 8));
+                }
+            }
+        }
+
+        // Reserve the heap so the page allocator never hands out its pages.
+        if HEAP_END > HEAP_START {
+            let s = HEAP_START / PAGE_SIZE;
+            let e = HEAP_END.div_ceil(PAGE_SIZE);
+            for p in s..e {
+                let idx = p - base_page;
+                *bm.add(idx / 8) |= 1 << (idx % 8);
+            }
+        }
+
+        // Never hand out page 0 (the null-pointer trap page).
+        if base_page == 0 {
+            *bm |= 0x01;
+        }
+
+        // Count free pages once; keep the count in sync from here on.
+        let mut free = 0usize;
+        for i in 0..span_pages {
+            if (*bm.add(i / 8) >> (i % 8)) & 1 == 0 {
+                free += 1;
+            }
+        }
+
+        BITMAP = bm;
+        BITMAP_BYTES = bytes;
+        BASE_PAGE = base_page;
+        SPAN_PAGES = span_pages;
+        FREE_PAGES = free;
+        true
+    }
+}
+
+/// Allocate `count` contiguous physical pages.  Returns the physical
+/// address of the first page, or None when no run fits.
+pub fn alloc_pages(count: usize) -> Option<usize> {
+    alloc_pages_aligned(count, 1)
+}
+
+/// Allocate `count` contiguous physical pages whose start address is
+/// aligned to `align_pages` (a power of two, in page units).
+pub fn alloc_pages_aligned(count: usize, align_pages: usize) -> Option<usize> {
+    if count == 0 || !align_pages.is_power_of_two() {
+        return None;
+    }
+    unsafe {
+        if BITMAP.is_null() || FREE_PAGES < count {
+            return None;
+        }
+        let span = SPAN_PAGES;
+        let mask = align_pages - 1;
+        let mut run_start = 0usize;
+        let mut run_len = 0usize;
+        for idx in 0..span {
+            let free = (*BITMAP.add(idx / 8) >> (idx % 8)) & 1 == 0;
+            if free {
+                if run_len == 0 {
+                    run_start = idx;
+                }
+                run_len += 1;
+                // Aligned page number within (or just past) this run.
+                let p = BASE_PAGE + run_start;
+                let p_align = (p + mask) & !mask;
+                if p_align == 0 {
+                    // Candidate starts at page 0 — restart the run here.
+                    run_start = idx;
+                    run_len = 1;
+                    continue;
+                }
+                let idx_align = p_align - BASE_PAGE;
+                if idx_align + count <= run_start + run_len {
+                    // Mark the run allocated.
+                    for k in idx_align..idx_align + count {
+                        *BITMAP.add(k / 8) |= 1 << (k % 8);
+                    }
+                    FREE_PAGES -= count;
+                    return Some(p_align * PAGE_SIZE);
+                }
+            } else {
+                run_len = 0;
+            }
+        }
+        None
+    }
+}
+
+/// Free `count` physical pages starting at `addr`.  The range must be
+/// page-aligned and previously allocated by `alloc_pages`.
+pub fn free_pages(addr: usize, count: usize) {
+    unsafe {
+        if BITMAP.is_null() || count == 0 {
+            return;
+        }
+        let base = BASE_PAGE;
+        let span = SPAN_PAGES;
+        let first = addr / PAGE_SIZE;
+        let in_range =
+            addr.is_multiple_of(PAGE_SIZE) && first >= base && first + count <= base + span;
+        if !in_range {
+            debug_assert!(false, "free_pages: bad range {:#x} len {}", addr, count);
+            return;
+        }
+        for p in first..first + count {
+            let idx = p - base;
+            debug_assert!(
+                (*BITMAP.add(idx / 8) >> (idx % 8)) & 1 != 0,
+                "free_pages: double free at {:#x}",
+                p * PAGE_SIZE
+            );
+            *BITMAP.add(idx / 8) &= !(1 << (idx % 8));
+        }
+        FREE_PAGES += count;
+    }
+}
+
+/// Smoke test for the page allocator: distinct single pages, a contiguous
+/// run, scribble/readback, and a clean return to the baseline free count.
+pub fn page_self_test() -> bool {
+    unsafe {
+        let before = page_stats();
+        if before.free_pages < 1024 {
+            return false; // not enough free pages to play with
+        }
+
+        // 64 single pages — all distinct, page-aligned, non-zero.
+        let mut pages: [usize; 64] = [0; 64];
+        for i in 0..64 {
+            let Some(addr) = alloc_pages(1) else {
+                return false;
+            };
+            if addr % PAGE_SIZE != 0 || addr == 0 {
+                return false;
+            }
+            pages[i] = addr;
+        }
+        for i in 0..64 {
+            for j in 0..i {
+                if pages[i] == pages[j] {
+                    return false; // overlap
+                }
+            }
+        }
+
+        // A contiguous run of 16.
+        let Some(run) = alloc_pages(16) else {
+            return false;
+        };
+        if run % PAGE_SIZE != 0 || run == 0 {
+            return false;
+        }
+
+        // Free count must drop by exactly 64 + 16.
+        if page_stats().free_pages != before.free_pages - 64 - 16 {
+            return false;
+        }
+
+        // Scribble through the run and read it back (it's real RAM).
+        for k in 0..16 {
+            core::ptr::write_volatile((run + k * PAGE_SIZE) as *mut u8, 0xAB);
+        }
+        for k in 0..16 {
+            if core::ptr::read_volatile((run + k * PAGE_SIZE) as *const u8) != 0xAB {
+                return false;
+            }
+        }
+
+        // Free everything and check we're back to baseline.
+        for &p in pages.iter() {
+            free_pages(p, 1);
+        }
+        free_pages(run, 16);
+
+        let after = page_stats();
+        after.free_pages == before.free_pages
+    }
+}
diff --git a/rsnix/src/paging.rs b/rsnix/src/paging.rs
new file mode 100644
index 0000000..766bde3
--- /dev/null
+++ b/rsnix/src/paging.rs
@@ -0,0 +1,356 @@
+// ---------------------------------------------------------------------------
+// Identity page-table helpers — 4-level paging (x86_64).
+//
+// The kernel keeps an identity-mapped 4-level tree (no higher half).  At
+// boot it runs on UEFI's tables; `adopt_tables()` rebuilds that map into
+// our own tables (UEFI maps its own table pages read-only, so the firmware
+// tree cannot be modified in place) and switches CR3.  After that the
+// helpers walk our tree to map / unmap / query individual 4 KB pages 1:1.
+// Page-table pages come from the physical page allocator.  Firmware may
+// have used 2 MB / 1 GB large pages for RAM, so the walk splits large pages
+// into 4 KB tables on demand.  Split tables stay allocated afterwards (no
+// refcounting) — fine for a kernel that owns all memory.
+// ---------------------------------------------------------------------------
+
+use crate::memory::{alloc_pages, free_pages, PAGE_SIZE};
+
+pub const PAGE_PRESENT: u64 = 1 << 0;
+pub const PAGE_WRITABLE: u64 = 1 << 1;
+pub const PAGE_USER: u64 = 1 << 2;
+pub const PAGE_PS: u64 = 1 << 7; // large page (2 MB PDE, 1 GB PDPTE)
+pub const PAGE_NX: u64 = 1 << 63;
+
+/// Physical address bits in a page-table entry.
+const PHYS_ADDR_MASK: u64 = 0x000F_FFFF_FFFF_F000;
+
+const PAGE_2M: usize = 1 << 21;
+const PAGE_1G: usize = 1 << 30;
+
+/// Current PML4 root (physical address, identity-mapped).
+pub fn cr3() -> usize {
+    let val: usize;
+    unsafe {
+        core::arch::asm!("mov {0}, cr3", out(reg) val, options(nostack, preserves_flags));
+    }
+    val
+}
+
+/// Full TLB flush by reloading CR3 (slow but bulletproof; map/unmap are
+/// rare operations in this kernel).
+fn flush_tlb_all() {
+    unsafe {
+        let cr3: usize;
+        core::arch::asm!("mov {0}, cr3", out(reg) cr3, options(nostack, preserves_flags));
+        core::arch::asm!("mov cr3, {0}", in(reg) cr3, options(nostack, preserves_flags));
+    }
+}
+
+/// Rebuild the identity map into our own page tables and switch CR3.
+///
+/// UEFI maps its own page-table pages read-only (R/W clear), so we cannot
+/// modify the firmware tree in place: map/unmap would #PF.  Instead, walk
+/// the current tables, replicate every present leaf (4 KB / 2 MB / 1 GB)
+/// into fresh tables from the page allocator, force R/W so the tree stays
+/// editable, then load the new PML4 into CR3.
+pub fn adopt_tables() -> bool {
+    unsafe {
+        let old_pml4 = cr3() as *const u64;
+        let Some(new_pml4) = alloc_pages(1) else {
+            return false;
+        };
+        core::ptr::write_bytes(new_pml4 as *mut u8, 0, PAGE_SIZE);
+        let new_pml4 = new_pml4 as *mut u64;
+
+        for l4 in 0..512 {
+            let l4e = old_pml4.add(l4).read_volatile();
+            if l4e & PAGE_PRESENT == 0 {
+                continue;
+            }
+            // Replicate this PDPT into a fresh one.
+            let old_pdpt = (l4e & PHYS_ADDR_MASK) as *const u64;
+            let Some(new_pdpt) = alloc_pages(1) else {
+                return false;
+            };
+            core::ptr::write_bytes(new_pdpt as *mut u8, 0, PAGE_SIZE);
+            let new_pdpt = new_pdpt as *mut u64;
+            *new_pml4.add(l4) =
+                (new_pdpt as u64) | PAGE_PRESENT | PAGE_WRITABLE | (l4e & PAGE_USER);
+
+            for l3 in 0..512 {
+                let pdpte = old_pdpt.add(l3).read_volatile();
+                if pdpte & PAGE_PRESENT == 0 {
+                    continue;
+                }
+                if pdpte & PAGE_PS != 0 {
+                    // 1 GB large page — copy the leaf, force writable.
+                    *new_pdpt.add(l3) = pdpte | PAGE_WRITABLE;
+                    continue;
+                }
+                let old_pd = (pdpte & PHYS_ADDR_MASK) as *const u64;
+                let Some(new_pd) = alloc_pages(1) else {
+                    return false;
+                };
+                core::ptr::write_bytes(new_pd as *mut u8, 0, PAGE_SIZE);
+                let new_pd = new_pd as *mut u64;
+                *new_pdpt.add(l3) =
+                    (new_pd as u64) | PAGE_PRESENT | PAGE_WRITABLE | (pdpte & PAGE_USER);
+
+                for l2 in 0..512 {
+                    let pde = old_pd.add(l2).read_volatile();
+                    if pde & PAGE_PRESENT == 0 {
+                        continue;
+                    }
+                    if pde & PAGE_PS != 0 {
+                        // 2 MB large page — copy the leaf, force writable.
+                        *new_pd.add(l2) = pde | PAGE_WRITABLE;
+                        continue;
+                    }
+                    let old_pt = (pde & PHYS_ADDR_MASK) as *const u64;
+                    let Some(new_pt) = alloc_pages(1) else {
+                        return false;
+                    };
+                    core::ptr::write_bytes(new_pt as *mut u8, 0, PAGE_SIZE);
+                    let new_pt = new_pt as *mut u64;
+                    *new_pd.add(l2) =
+                        (new_pt as u64) | PAGE_PRESENT | PAGE_WRITABLE | (pde & PAGE_USER);
+
+                    for l1 in 0..512 {
+                        let pte = old_pt.add(l1).read_volatile();
+                        if pte & PAGE_PRESENT != 0 {
+                            *new_pt.add(l1) = pte | PAGE_WRITABLE;
+                        }
+                    }
+                }
+            }
+        }
+
+        // Switch to the new tables (CR3 reload flushes the TLB).
+        let new_cr3 = new_pml4 as usize;
+        core::arch::asm!("mov cr3, {0}", in(reg) new_cr3, options(nostack, preserves_flags));
+        true
+    }
+}
+
+/// Ensure the PDPT entry points at a page-directory table, splitting a
+/// 1 GB large page at `base_1g` if present.  Returns the PD pointer.
+unsafe fn ensure_pd(pdpte: &mut u64, base_1g: usize) -> Option<*mut u64> {
+    unsafe {
+        if *pdpte & PAGE_PRESENT == 0 {
+            let page = alloc_pages(1)? as *mut u64;
+            core::ptr::write_bytes(page as *mut u8, 0, PAGE_SIZE);
+            *pdpte = (page as u64) | PAGE_PRESENT | PAGE_WRITABLE;
+            return Some(page);
+        }
+        if *pdpte & PAGE_PS != 0 {
+            // Split the 1 GB page into 512 × 2 MB pages.
+            let pd = alloc_pages(1)? as *mut u64;
+            core::ptr::write_bytes(pd as *mut u8, 0, PAGE_SIZE);
+            let inherit = *pdpte & (PAGE_USER | PAGE_NX);
+            for i in 0..512 {
+                let p = base_1g + i * PAGE_2M;
+                *pd.add(i) = (p as u64) | PAGE_PRESENT | PAGE_WRITABLE | PAGE_PS | inherit;
+            }
+            *pdpte = (pd as u64) | PAGE_PRESENT | PAGE_WRITABLE | (*pdpte & PAGE_USER);
+            return Some(pd);
+        }
+        Some(((*pdpte & PHYS_ADDR_MASK) as usize) as *mut u64)
+    }
+}
+
+/// Ensure the PD entry points at a page table, splitting a 2 MB large page
+/// at `base_2m` if present.  Returns the PT pointer.
+unsafe fn ensure_pt(pde: &mut u64, base_2m: usize) -> Option<*mut u64> {
+    unsafe {
+        if *pde & PAGE_PRESENT == 0 {
+            let page = alloc_pages(1)? as *mut u64;
+            core::ptr::write_bytes(page as *mut u8, 0, PAGE_SIZE);
+            *pde = (page as u64) | PAGE_PRESENT | PAGE_WRITABLE;
+            return Some(page);
+        }
+        if *pde & PAGE_PS != 0 {
+            // Split the 2 MB page into 512 × 4 KB pages.
+            let pt = alloc_pages(1)? as *mut u64;
+            core::ptr::write_bytes(pt as *mut u8, 0, PAGE_SIZE);
+            let inherit = *pde & (PAGE_USER | PAGE_NX);
+            for i in 0..512 {
+                let p = base_2m + i * PAGE_SIZE;
+                *pt.add(i) = (p as u64) | PAGE_PRESENT | PAGE_WRITABLE | inherit;
+            }
+            *pde = (pt as u64) | PAGE_PRESENT | PAGE_WRITABLE | (*pde & PAGE_USER);
+            return Some(pt);
+        }
+        Some(((*pde & PHYS_ADDR_MASK) as usize) as *mut u64)
+    }
+}
+
+/// Identity-map the physical page at `phys` (must be 4 KB aligned).
+/// `flags` adds to PRESENT (e.g. PAGE_WRITABLE, PAGE_USER).
+pub fn map_page(phys: usize, flags: u64) -> bool {
+    if !phys.is_multiple_of(PAGE_SIZE) {
+        return false;
+    }
+    unsafe {
+        let pml4 = cr3() as *mut u64;
+        let l4 = (phys >> 39) & 0x1FF;
+        let l3 = (phys >> 30) & 0x1FF;
+        let l2 = (phys >> 21) & 0x1FF;
+        let l1 = (phys >> 12) & 0x1FF;
+
+        let pml4e = &mut *pml4.add(l4);
+        if *pml4e & PAGE_PRESENT == 0 {
+            let Some(page) = alloc_pages(1) else {
+                return false;
+            };
+            core::ptr::write_bytes(page as *mut u8, 0, PAGE_SIZE);
+            *pml4e = (page as u64) | PAGE_PRESENT | PAGE_WRITABLE;
+        }
+        // PML4 entries are never large pages.
+
+        let base_1g = phys & !(PAGE_1G - 1);
+        let pdpte = &mut *(((*pml4e & PHYS_ADDR_MASK) as usize) as *mut u64).add(l3);
+        let Some(pd) = ensure_pd(pdpte, base_1g) else {
+            return false;
+        };
+
+        let base_2m = phys & !(PAGE_2M - 1);
+        let pde = &mut *pd.add(l2);
+        let Some(pt) = ensure_pt(pde, base_2m) else {
+            return false;
+        };
+
+        let pte = &mut *pt.add(l1);
+        *pte = (phys as u64) | flags | PAGE_PRESENT;
+        flush_tlb_all();
+        true
+    }
+}
+
+/// Identity-map `count` consecutive pages starting at `phys`.
+pub fn map_range(phys: usize, count: usize, flags: u64) -> bool {
+    for i in 0..count {
+        if !map_page(phys + i * PAGE_SIZE, flags) {
+            return false;
+        }
+    }
+    true
+}
+
+/// Unmap the 4 KB page at `phys`.  Splits large pages as needed so only
+/// this one page is removed.  Returns false if it wasn't mapped.
+pub fn unmap_page(phys: usize) -> bool {
+    if !phys.is_multiple_of(PAGE_SIZE) {
+        return false;
+    }
+    unsafe {
+        let pml4 = cr3() as *mut u64;
+        let l4 = (phys >> 39) & 0x1FF;
+        let l3 = (phys >> 30) & 0x1FF;
+        let l2 = (phys >> 21) & 0x1FF;
+        let l1 = (phys >> 12) & 0x1FF;
+
+        let pml4e = &mut *pml4.add(l4);
+        if *pml4e & PAGE_PRESENT == 0 {
+            return false;
+        }
+        let base_1g = phys & !(PAGE_1G - 1);
+        let pdpte = &mut *(((*pml4e & PHYS_ADDR_MASK) as usize) as *mut u64).add(l3);
+        if *pdpte & PAGE_PRESENT == 0 {
+            return false;
+        }
+        let Some(pd) = ensure_pd(pdpte, base_1g) else {
+            return false;
+        };
+        let base_2m = phys & !(PAGE_2M - 1);
+        let pde = &mut *pd.add(l2);
+        if *pde & PAGE_PRESENT == 0 {
+            return false;
+        }
+        let Some(pt) = ensure_pt(pde, base_2m) else {
+            return false;
+        };
+        let pte = &mut *pt.add(l1);
+        if *pte & PAGE_PRESENT == 0 {
+            return false;
+        }
+        *pte = 0;
+        flush_tlb_all();
+        true
+    }
+}
+
+/// Is the page at `phys` mapped (present at any level, incl. large pages)?
+pub fn is_mapped(phys: usize) -> bool {
+    unsafe {
+        let pml4 = cr3() as *const u64;
+        let l4 = (phys >> 39) & 0x1FF;
+        let l3 = (phys >> 30) & 0x1FF;
+        let l2 = (phys >> 21) & 0x1FF;
+        let l1 = (phys >> 12) & 0x1FF;
+
+        let pml4e = *pml4.add(l4);
+        if pml4e & PAGE_PRESENT == 0 {
+            return false;
+        }
+        let pdpte = *((pml4e & PHYS_ADDR_MASK) as *const u64).add(l3);
+        if pdpte & PAGE_PRESENT == 0 {
+            return false;
+        }
+        if pdpte & PAGE_PS != 0 {
+            return true; // 1 GB page covers phys
+        }
+        let pde = *((pdpte & PHYS_ADDR_MASK) as *const u64).add(l2);
+        if pde & PAGE_PRESENT == 0 {
+            return false;
+        }
+        if pde & PAGE_PS != 0 {
+            return true; // 2 MB page covers phys
+        }
+        let pte = *((pde & PHYS_ADDR_MASK) as *const u64).add(l1);
+        pte & PAGE_PRESENT != 0
+    }
+}
+
+/// Smoke test: allocate two physical pages, unmap one, verify the mapping
+/// state, remap it, verify data still works, and free both.
+pub fn self_test() -> bool {
+    let Some(p1) = alloc_pages(1) else {
+        return false;
+    };
+    let Some(p2) = alloc_pages(1) else {
+        return false;
+    };
+
+    // Both pages must already be identity-mapped (they're RAM).
+    if !is_mapped(p1) || !is_mapped(p2) {
+        return false;
+    }
+
+    // Unmap p1 — only p1 should disappear.
+    if !unmap_page(p1) {
+        return false;
+    }
+    if is_mapped(p1) {
+        return false;
+    }
+    if !is_mapped(p2) {
+        return false;
+    }
+
+    // Remap and verify we can write through the mapping.
+    if !map_page(p1, PAGE_WRITABLE) {
+        return false;
+    }
+    if !is_mapped(p1) {
+        return false;
+    }
+    unsafe {
+        core::ptr::write_volatile(p1 as *mut u8, 0xCD);
+        if core::ptr::read_volatile(p1 as *const u8) != 0xCD {
+            return false;
+        }
+    }
+
+    free_pages(p1, 1);
+    free_pages(p2, 1);
+    true
+}
diff --git a/rsnix/src/uefi.rs b/rsnix/src/uefi.rs
index 2e3ed6b..619739e 100644
--- a/rsnix/src/uefi.rs
+++ b/rsnix/src/uefi.rs
@@ -116,13 +116,43 @@ pub struct MemoryDescriptor {
     pub attribute: u64,
 }
 
-pub const MEMORY_TYPE_CONVENTIONAL: u32 = 7;
-#[allow(dead_code)]
-pub const MEMORY_TYPE_LOADER_DATA: u32 = 6;
-#[allow(dead_code)]
+pub const MEMORY_TYPE_RESERVED: u32 = 0;
+pub const MEMORY_TYPE_LOADER_CODE: u32 = 1;
+pub const MEMORY_TYPE_LOADER_DATA: u32 = 2;
 pub const MEMORY_TYPE_BOOT_SERVICES_CODE: u32 = 3;
-#[allow(dead_code)]
 pub const MEMORY_TYPE_BOOT_SERVICES_DATA: u32 = 4;
+pub const MEMORY_TYPE_RUNTIME_CODE: u32 = 5;
+pub const MEMORY_TYPE_RUNTIME_DATA: u32 = 6;
+pub const MEMORY_TYPE_CONVENTIONAL: u32 = 7;
+pub const MEMORY_TYPE_UNUSABLE: u32 = 8;
+pub const MEMORY_TYPE_ACPI_RECLAIM: u32 = 9;
+pub const MEMORY_TYPE_ACPI_NVS: u32 = 10;
+pub const MEMORY_TYPE_MMIO: u32 = 11;
+pub const MEMORY_TYPE_MMIO_PORT: u32 = 12;
+pub const MEMORY_TYPE_PAL_CODE: u32 = 13;
+pub const MEMORY_TYPE_PERSISTENT: u32 = 14;
+
+/// Human-readable name for a UEFI memory type.
+pub fn memory_type_name(kind: u32) -> &'static str {
+    match kind {
+        0 => "Reserved",
+        1 => "LoaderCode",
+        2 => "LoaderData",
+        3 => "BootServicesCode",
+        4 => "BootServicesData",
+        5 => "RuntimeCode",
+        6 => "RuntimeData",
+        7 => "Conventional",
+        8 => "Unusable",
+        9 => "ACPIReclaim",
+        10 => "ACPINVS",
+        11 => "MMIO",
+        12 => "MMIOPort",
+        13 => "PalCode",
+        14 => "Persistent",
+        _ => "Unknown",
+    }
+}
 
 // ---------------------------------------------------------------------------
 // Boot services table