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 --- rsnix/src/memory.rs | 663 +++++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 626 insertions(+), 37 deletions(-) (limited to 'rsnix/src/memory.rs') 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 + } +} -- cgit v1.2.3