From 5e03409586efc37931f07b40ee0c71a9a9e109f7 Mon Sep 17 00:00:00 2001 From: salmonik Date: Fri, 31 Jul 2026 15:51:28 +0200 Subject: rsnix: memory management — free-list heap, bitmap pages, paging adoption MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit - 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 --- rsdos/src/main.rs | 32 +++ rsnix/src/lib.rs | 1 + rsnix/src/memory.rs | 663 +++++++++++++++++++++++++++++++++++++++++++++++++--- rsnix/src/paging.rs | 356 ++++++++++++++++++++++++++++ rsnix/src/uefi.rs | 40 +++- 5 files changed, 1050 insertions(+), 42 deletions(-) create mode 100644 rsnix/src/paging.rs 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 { // 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 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 { + 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 { + 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 -- cgit v1.2.3