Testing Strategy

Core Concepts to Validate

1. Heap Allocator Correctness

Before testing edge cases, verify the basics work:

Allocate X bytes → get a non-null pointer
Write to the memory → no crash
Read back what was written → data matches
Free the pointer → no crash
Allocate again → get a valid pointer (ideally the same one, reused)

2. Fragmentation Resistance

The real test of a heap allocator:

Allocate 100 blocks of 256 bytes each
Free every other block (blocks 0, 2, 4, ..., 98)
Allocate a 256-byte block → should succeed (reuse a freed slot)
Allocate a 512-byte block → depends on coalescing

Without coalescing, adjacent freed blocks remain separate. A 512-byte allocation may fail even though 512 bytes of free space exist split across two 256-byte slots.

3. vmalloc Page Mapping

Call vmalloc(8192)  → allocates 2 pages
Write to page 0
Write to page 1     → must be accessible even though physically separate
Read back both      → data must be correct
Call vfree(ptr)     → both pages unmapped, frames returned

Shell Commands to Add

Add a memtest command to NPS:

#![allow(unused)]
fn main() {
"memtest" => self.cmd_memtest(),
"meminfo" => self.cmd_meminfo(),
}

memtest

#![allow(unused)]
fn main() {
fn cmd_memtest(&self) {
    println!("=== Memory Test ===");

    // Test 1: Basic alloc/free
    let p1 = kmalloc(64);
    println!("kmalloc(64):   {:?}  {}", p1, if p1.is_null() { "FAIL" } else { "OK" });
    kfree(p1);

    // Test 2: Write and read back
    let p2: *mut u32 = kmalloc(16) as *mut u32;
    *p2 = 0xDEADBEEF;
    let ok = *p2 == 0xDEADBEEF;
    println!("write/read:    {}", if ok { "OK" } else { "FAIL" });
    kfree(p2 as *mut u8);

    // Test 3: Large allocation
    let p3 = kmalloc(1024 * 1024);  // 1MB
    println!("kmalloc(1MB):  {:?}  {}", p3, if p3.is_null() { "FAIL" } else { "OK" });
    kfree(p3);

    // Test 4: vmalloc
    let v1 = vmalloc(8192);
    println!("vmalloc(8KB):  {:?}  {}", v1, if v1.is_null() { "FAIL" } else { "OK" });
    vfree(v1);

    println!("=== Test complete ===");
}
}

meminfo

#![allow(unused)]
fn main() {
fn cmd_meminfo(&self) {
    println!("=== Memory Info ===");
    println!("Frame allocator:");
    println!("  Next free frame: 0x{:08x}", NEXT_FREE_FRAME);
    println!("  Max frames:      {}", MAX_FRAMES);
    println!("  Frames used:     {}", /* calculation */);
    println!("Heap:");
    println!("  Start:  0x{:08x}", HEAP_START);
    println!("  Size:   {} KB", HEAP_SIZE / 1024);
    println!("  Used:   {} bytes", /* walk and count */);
    println!("  Free:   {} bytes", /* walk and count */);
}
}

Red Flags to Watch For

Alignment Checklist

• kmalloc must return pointers aligned to at least 4 bytes (8 is safer)
• The block header must be sized so that header + size is also aligned
• vmalloc returns page-aligned pointers (4KB boundary) by definition
• Frame addresses from allocate_frame are always 4KB-aligned

Recommended Implementation Order

1. init_heap(start, size) — Create the first free block
2. kmalloc(size) — First-fit, no splitting
3. kfree(ptr) — Mark as free, no coalescing
4. Add splitting to kmalloc (don’t waste memory on small allocations)
5. Add coalescing to kfree (merge adjacent free blocks)
6. ksize(ptr) — Read from header
7. vmalloc(size) — Map pages into virtual space
8. vfree(ptr) — Unmap and return frames
9. vsize(ptr) — Read from metadata table
10. Add shell commands for testing and debugging