MODULES := core/fdt.rad core/platform.rad core/frames.rad

CHECK_MODULES := check/boot.rad check/fixture.rad check/frames.rad

record the contracts established through step 3 of the 22-step plan.

## Physical frame ownership

- Frame indexes and counts use u32: MAX_PAGES = 65536 is not representable in u16.

- Frame indices address the first 256 MiB of physical memory. Discovered RAM

  must fit in this build's physical address range.

- Allocation clears frames before a new domain receives access. Kernel/image,

  FDT, boot data, firmware reservations, and MMIO regions are excluded.

- Contiguous allocations validate complete ranges and fail without partial

  ownership when memory or metadata capacity is unavailable.

Exercise contiguous allocation, clearing, reservation exclusion, exhaustion, and exact physical boundaries.

mod frames;

    frames::run();

//! Physical allocator bounds, fragmentation, and data-isolation checks.

use core::fdt;

use core::frames;

use core::platform;

/// Test-owned physical memory spanning more than one bitmap word.

static MEMORY: [u8; 68 * frames::PAGE_SIZE] = undefined;

/// Clear only the physical range supplied by the allocator.

fn clear(base: u64, size: u32) {

    let start = base as u32;

    assert base < MEMORY.len as u64;

    assert size <= MEMORY.len - start;

    for i in start..start + size { set MEMORY[i] = 0; }

}

/// Require a contiguous allocation request to fail without taking frames.

fn exhausted(pool: *mut frames::Pool, count: u32) {

    let available = pool.available;

    let allocation = try frames::allocate(pool, count, clear) catch {

        assert pool.available == available;

        return;

    };

    frames::discard(pool, allocation);

    panic "exhausted: allocation unexpectedly succeeded";

}

/// Check unaligned RAM, reserved overlaps, bitmap boundaries, and zeroing.

export fn run() {

    for i in 0..MEMORY.len { set MEMORY[i] = 0xa5; }

    let mut machine: platform::Platform = undefined;

    set machine.memoryCount = 1;

    set machine.memory[0] = fdt::Range {

        base: frames::PAGE_SIZE as u64 + 1,

        size: frames::PAGE_SIZE as u64 * 66 - 1,

    };

    set machine.reservedCount = 1;

    set machine.reserved[0] = fdt::Range {

        base: frames::PAGE_SIZE as u64 * 3 + 1,

        size: frames::PAGE_SIZE as u64,

    };

    let mut pool: frames::Pool = undefined;

    try! frames::init(&mut pool, &machine);

    assert pool.available == 63;

    let allocation = try! frames::allocate(&mut pool, 2, clear);

    let run = frames::install(allocation);

    assert run.first == 5 and run.count == 2;

    for i in 5 * frames::PAGE_SIZE..7 * frames::PAGE_SIZE {

        assert MEMORY[i] == 0;

    }

    assert MEMORY[5 * frames::PAGE_SIZE - 1] == 0xa5;

    assert MEMORY[7 * frames::PAGE_SIZE] == 0xa5;

    exhausted(&mut pool, 61);

    let rest = try! frames::allocate(&mut pool, 60, clear);

    let last = try! frames::allocate(&mut pool, 1, clear);

    assert pool.available == 0;

    exhausted(&mut pool, 1);

    frames::discard(&mut pool, last);

    frames::discard(&mut pool, rest);

    frames::reclaim(&mut pool, run);

    assert pool.available == 63;

    set machine.memory[0] = fdt::Range { base: 0, size: MEMORY.len as u64 };

    set machine.reservedCount = 0;

    try! frames::init(&mut pool, &machine);

    let whole = try! frames::allocate(&mut pool, 68, clear);

    assert pool.available == 0;

    frames::discard(&mut pool, whole);

    assert pool.available == 68;

    exhausted(&mut pool, 0);

    exhausted(&mut pool, frames::MAX_FRAMES + 1);

}

export mod frames;

//! Contiguous physical frames with explicit allocation ownership.

use core::fdt;

use core::platform;

/// Physical allocation unit in bytes.

export constant PAGE_SIZE: u32 = 4096;

/// Number of physical frames supported by this build.

export constant MAX_FRAMES: u32 = 65536;

/// Words in the frame availability bitmap.

constant BITMAP_WORDS: u32 = MAX_FRAMES / 64;

/// Invalid allocation input or insufficient contiguous frames.

export union Error: Copy {

    /// The request has zero frames or exceeds the supported physical range.

    Invalid,

    /// No contiguous free range satisfies the request.

    OutOfMemory,

}

/// Physical range metadata held by kernel page objects.

export record Run: Copy {

    /// Index of the first physical frame.

    first: u32,

    /// Number of contiguous frames.

    count: u32,

}

/// An allocation that must be installed into a kernel object or returned.

export union Allocation: Once {

    /// Cleared frames exclusively held by this obligation.

    Frames(Run),

}

/// A bitmap of available physical frames.

export record Pool: Copy {

    /// A set bit identifies a complete, unreserved, unallocated RAM frame.

    free: [u64; BITMAP_WORDS],

    /// Exclusive high frame index of discovered RAM.

    limit: u32,

    /// Number of currently available frames.

    available: u32,

}

/// Initialize available frames from physical RAM and boot reservations.

export fn init(pool: *mut Pool, machine: *platform::Platform) throws (Error) {

    for i in 0..BITMAP_WORDS { set pool.free[i] = 0; }

    set pool.limit = 0;

    set pool.available = 0;

    let physicalLimit = MAX_FRAMES as u64 * PAGE_SIZE as u64;

    for i in 0..machine.memoryCount {

        let range = machine.memory[i];

        if range.base > physicalLimit or range.size > physicalLimit - range.base {

            throw Error::Invalid;

        }

        let first = ((range.base + PAGE_SIZE as u64 - 1) / PAGE_SIZE as u64) as u32;

        let end = ((range.base + range.size) / PAGE_SIZE as u64) as u32;

        for frame in first..end {

            let bit = 1 as u64 << (frame as u64 & 63);

            if pool.free[frame / 64] & bit == 0 {

                set pool.free[frame / 64] |= bit;

                set pool.available += 1;

            }

        }

        if end > pool.limit { set pool.limit = end; }

    }

    for i in 0..machine.reservedCount {

        let range = machine.reserved[i];

        if range.size == 0 or range.base > 0xffffffffffffffff - range.size {

            throw Error::Invalid;

        }

        let first = range.base / PAGE_SIZE as u64;

        let endByte = range.base + range.size;

        let mut end = endByte / PAGE_SIZE as u64;

        if endByte % PAGE_SIZE as u64 <> 0 { set end += 1; }

        if first >= pool.limit as u64 { continue; }

        if end > pool.limit as u64 { set end = pool.limit as u64; }

        for frame in first as u32..end as u32 {

            let bit = 1 as u64 << (frame as u64 & 63);

            if pool.free[frame / 64] & bit <> 0 {

                set pool.free[frame / 64] &= ~bit;

                set pool.available -= 1;

            }

        }

    }

}

/// Take contiguous frames and clear them before returning their ownership.

/// The clear function must write exactly the supplied physical byte range.

export fn allocate(pool: *mut Pool, count: u32, clear: fn(u64, u32)) -> Allocation throws (Error) {

    if count == 0 or count > MAX_FRAMES { throw Error::Invalid; }

    if count > pool.available { throw Error::OutOfMemory; }

    let mut length: u32 = 0;

    let mut frame: u32 = 0;

    while frame < pool.limit {

        let word = pool.free[frame / 64];

        if word == 0 {

            set length = 0;

            set frame = (frame + 64) & ~63;

            continue;

        }

        if word & (1 as u64 << (frame as u64 & 63)) <> 0 {

            set length += 1;

            if length == count {

                let first = frame + 1 - count;

                for current in first..frame + 1 {

                    set pool.free[current / 64] &= ~(1 as u64 << (current as u64 & 63));

                }

                set pool.available -= count;

                clear(first as u64 * PAGE_SIZE as u64, count * PAGE_SIZE);

                return Allocation::Frames(Run { first, count });

            }

        } else {

            set length = 0;

        }

        set frame += 1;

    }

    throw Error::OutOfMemory;

}

/// Consume allocation ownership when a page object assumes its lifetime.

export fn install(allocation: Allocation) -> Run {

    match allocation {

        case Allocation::Frames(run) => return run,

    }

}

/// Return frames after all object and persistent-grant lifetimes have ended.

export fn reclaim(pool: *mut Pool, run: Run) {

    assert run.count > 0 and run.first <= pool.limit;

    assert run.count <= pool.limit - run.first;

    for frame in run.first..run.first + run.count {

        let bit = 1 as u64 << (frame as u64 & 63);

        assert pool.free[frame / 64] & bit == 0;

        set pool.free[frame / 64] |= bit;

    }

    set pool.available += run.count;

}

/// Return an allocation that was not installed into a page object.

export fn discard(pool: *mut Pool, allocation: Allocation) {

    let run = install(allocation);

    reclaim(pool, run);

}