frame-alloc 0.1.0

//! Property / oracle tests: randomised alloc/free sequences checked against an
//! independent reference model of frame occupancy.
//!
//! This is a black-box test over the public `PhysicalAllocator` + `RegionInit`
//! API: every allocator is held to the *same* model built from first principles
//! (a set of occupied frame addresses), so any genuine aliasing, out-of-range, or
//! leak bug is caught regardless of how the allocator is implemented.
//!
//! The model-checked invariants, on every operation:
//!
//! * **No aliasing** — an allocation never returns a frame that another live
//!   allocation already holds. This is the cardinal allocator bug; the occupancy
//!   set catches it directly, with a wide detection window (frames stay marked for
//!   as long as the allocation is live).
//! * **In range** — every returned frame lies inside a usable range (never in a
//!   reserved hole or outside the pool).
//! * **Frame alignment** — every returned address is base-frame aligned.
//! * **Conservation** — after freeing everything, the full allocatable count is
//!   recoverable (nothing leaked). The allocatable count is *measured* up front by
//!   draining the fresh pool, so allocators that carve metadata out of the pool
//!   (e.g. the bitmap buddy's in-pool bitmap) are handled without special-casing.
//!
//! Requests use power-of-two frame counts, so a buddy's power-of-two rounding and
//! a list's exact sizing both consume exactly `count` contiguous frames — keeping
//! the oracle allocator-agnostic.

mod common;

use common::{HhdmProvenance, OwnedRegion, TestProvenance, n};
use core::sync::atomic::{AtomicUsize, Ordering};
use frame_alloc::{
    CpuId, DepotAllocator, NoCpuId, NoInterruptControl, PageSize, PhysRange, PhysicalAllocator,
    RegionInit, RegionedAllocator, SummaryBuddyAllocator,
};
use std::collections::HashSet;

pub type RegionedDepot<
    const REGIONS: usize,
    A,
    S,
    const SLOTS: usize,
    const CAP: usize = 128,
    const DEPOT_CAP: usize = 512,
    I = NoInterruptControl,
> = RegionedAllocator<REGIONS, DepotAllocator<A, S, SLOTS, CAP, DEPOT_CAP, I>, S>;

const BASE: PageSize = PageSize::from_log2(6);
const ORDERS: usize = 4;
const FRAMES: usize = 256;
const STEPS: usize = 50_000;

const SEEDS: [u64; 6] = [
    0x1D4C_E550_4242_1AD1,
    0x9E37_79B9_7F4A_7C15,
    0xD1B5_4A32_D192_ED03,
    0xA076_1D64_78BD_642F,
    0xE703_7ED1_A0B4_28DB,
    0x2545_F491_4F6C_DD1D,
];

fn max_block() -> usize {
    BASE.bytes() << (ORDERS - 1)
}

/// Drain every order-0 frame the (freshly-initialised) pool can hand out, count
/// them, and return them all so the pool is fully free again. This is the
/// allocatable capacity the conservation check measures against — independent of
/// any metadata the allocator reserves inside the pool.
fn measure_capacity<A: PhysicalAllocator>(a: &A) -> usize {
    let mut drained = Vec::new();
    while let Ok(addr) = a.allocate_physical(BASE, n(1)) {
        drained.push(addr);
    }
    let count = drained.len();
    for addr in drained {
        unsafe { a.deallocate_physical(BASE, n(1), addr) };
    }
    count
}

/// Drive `a` through a randomised power-of-two alloc/free churn seeded by `seed`,
/// checking the occupancy invariants on every step. `usable` is the set of
/// `[lo, hi)` byte ranges that may legitimately be handed out (one entry for a
/// contiguous pool, several for a holed memory map); every returned block must
/// lie entirely within one of them — never in a hole.
///
/// Leaves the pool fully free again on return, so the same allocator can be
/// replayed under several seeds.
fn oracle_churn<A: PhysicalAllocator>(a: &A, usable: &[(usize, usize)], seed: u64) {
    let fb = BASE.bytes();
    let capacity = measure_capacity(a);
    assert!(capacity > 0, "pool has no allocatable frames");

    let mut occupied: HashSet<usize> = HashSet::new();
    let mut live: Vec<(usize, usize)> = Vec::new();
    let mut rng = seed;
    let mut next = || {
        rng ^= rng << 13;
        rng ^= rng >> 7;
        rng ^= rng << 17;
        rng
    };

    for step in 0..STEPS {
        let do_alloc = live.is_empty() || (next() & 1 == 0);
        if do_alloc {
            let count = 1usize << ((next() as usize) % ORDERS);
            if let Ok(addr) = a.allocate_physical(BASE, n(count)) {
                assert_eq!(
                    addr % fb,
                    0,
                    "step {step}: address {addr:#x} not frame-aligned"
                );
                let end = addr + count * fb;
                assert!(
                    usable.iter().any(|&(lo, hi)| addr >= lo && end <= hi),
                    "step {step}: block [{addr:#x}, {end:#x}) is not contained in any usable range \
                     (fell in a hole or outside the pool)"
                );
                for f in 0..count {
                    let fa = addr + f * fb;
                    assert!(
                        occupied.insert(fa),
                        "step {step}: ALIASING — frame {fa:#x} already held by a live allocation"
                    );
                }
                live.push((addr, count));
            }
        } else {
            let idx = (next() as usize) % live.len();
            let (addr, count) = live.swap_remove(idx);
            for f in 0..count {
                occupied.remove(&(addr + f * fb));
            }
            unsafe { a.deallocate_physical(BASE, n(count), addr) };
        }
    }

    // Conservation: free everything still live, then confirm full recovery
    // against the capacity measured before the churn.
    for &(addr, count) in &live {
        unsafe { a.deallocate_physical(BASE, n(count), addr) };
    }
    let mut recovered: Vec<usize> = Vec::new();
    while let Ok(addr) = a.allocate_physical(BASE, n(1)) {
        recovered.push(addr);
    }
    assert_eq!(
        recovered.len(),
        capacity,
        "frames leaked: recovered {} of {capacity}",
        recovered.len()
    );

    // Return everything so the pool is fully free (and re-coalesced) again,
    // ready for the next seed's replay on this same allocator.
    for addr in recovered {
        unsafe { a.deallocate_physical(BASE, n(1), addr) };
    }
}

/// Build a holed span: a max-block-aligned region of `total` frames with a hole
/// punched at `[hole_lo, hole_hi)` (in frames). Returns the two usable byte
/// ranges (sorted) for the oracle to validate against.
fn holed_usable(base: usize, total: usize, hole_lo: usize, hole_hi: usize) -> [(usize, usize); 2] {
    let fb = BASE.bytes();
    [
        (base, base + hole_lo * fb),
        (base + hole_hi * fb, base + total * fb),
    ]
}

fn holed_ranges(base: usize, total: usize, hole_lo: usize, hole_hi: usize) -> [PhysRange; 2] {
    let fb = BASE.bytes();
    [
        PhysRange {
            base,
            len: hole_lo * fb,
        },
        PhysRange {
            base: base + hole_hi * fb,
            len: (total - hole_hi) * fb,
        },
    ]
}

// Hole straddling the interior; both sides max-block aligned so merges work.
const HOLE: (usize, usize) = (64, 96);

#[test]
fn summary_buddy_matches_occupancy_oracle() {
    let span = FRAMES * BASE.bytes();
    let region = OwnedRegion::new(span, max_block());
    let a = SummaryBuddyAllocator::<ORDERS, TestProvenance>::new(BASE);
    unsafe { a.init_region(region.addr(), span) };
    let usable = [(region.addr(), region.addr() + span)];
    for &seed in &SEEDS {
        oracle_churn(&a, &usable, seed);
    }
}

#[test]
fn summary_buddy_matches_occupancy_oracle_hhdm() {
    let span = FRAMES * BASE.bytes();
    let region = OwnedRegion::new(span, max_block());
    let phys_base = region.phys_addr();
    let a = SummaryBuddyAllocator::<ORDERS, HhdmProvenance>::new(BASE);
    unsafe {
        a.init(
            phys_base,
            span,
            &[PhysRange {
                base: phys_base,
                len: span,
            }],
        )
    };
    let usable = [(phys_base, phys_base + span)];
    for &seed in &SEEDS {
        oracle_churn(&a, &usable, seed);
    }
}

#[test]
fn summary_buddy_matches_occupancy_oracle_holed() {
    let span = FRAMES * BASE.bytes();
    let region = OwnedRegion::new(span, max_block());
    let base = region.addr();
    let usable = holed_usable(base, FRAMES, HOLE.0, HOLE.1);
    let ranges = holed_ranges(base, FRAMES, HOLE.0, HOLE.1);
    let a = SummaryBuddyAllocator::<ORDERS, TestProvenance>::new(BASE);
    unsafe { a.init(base, span, &ranges) };
    for &seed in &SEEDS {
        oracle_churn(&a, &usable, seed);
    }
}

/// A CPU selector that rotates on every query, so the wrapper's start region
/// cycles during churn (rather than always beginning at region 0).
static ROTATING_CPU: AtomicUsize = AtomicUsize::new(0);
struct RotatingCpu;
impl CpuId for RotatingCpu {
    fn current_cpu() -> usize {
        ROTATING_CPU.fetch_add(1, Ordering::Relaxed)
    }
}

/// (wrapper, backing regions kept alive by the caller, usable byte ranges for the oracle)
type RegionedPool<const REGIONS: usize> = (
    RegionedAllocator<REGIONS, SummaryBuddyAllocator<ORDERS, TestProvenance>, RotatingCpu>,
    [OwnedRegion; REGIONS],
    Vec<(usize, usize)>,
);

/// Build a `REGIONS`-region wrapper over `REGIONS` disjoint, fully-usable spans of
/// `frames` frames each.
fn regioned_pool<const REGIONS: usize>(frames: usize) -> RegionedPool<REGIONS> {
    let bytes = frames * BASE.bytes();
    let regions: [OwnedRegion; REGIONS] =
        core::array::from_fn(|_| OwnedRegion::new(bytes, max_block()));
    let a: RegionedAllocator<REGIONS, SummaryBuddyAllocator<ORDERS, TestProvenance>, RotatingCpu> =
        RegionedAllocator::new(
            BASE,
            [const { SummaryBuddyAllocator::<ORDERS, TestProvenance>::new(BASE) }; REGIONS],
        );
    let mut usable = Vec::new();
    for (i, r) in regions.iter().enumerate() {
        unsafe {
            a.init_at(
                i,
                r.addr(),
                bytes,
                &[PhysRange {
                    base: r.addr(),
                    len: bytes,
                }],
            );
        }
        usable.push((r.addr(), r.addr() + bytes));
    }
    (a, regions, usable)
}

/// As [`regioned_pool`], but punches a reserved hole `[hole.0, hole.1)` (in
/// frames) into every region's span.
fn regioned_pool_holed<const REGIONS: usize>(
    frames: usize,
    hole: (usize, usize),
) -> RegionedPool<REGIONS> {
    let bytes = frames * BASE.bytes();
    let regions: [OwnedRegion; REGIONS] =
        core::array::from_fn(|_| OwnedRegion::new(bytes, max_block()));
    let a: RegionedAllocator<REGIONS, SummaryBuddyAllocator<ORDERS, TestProvenance>, RotatingCpu> =
        RegionedAllocator::new(
            BASE,
            [const { SummaryBuddyAllocator::<ORDERS, TestProvenance>::new(BASE) }; REGIONS],
        );
    let mut usable = Vec::new();
    for (i, r) in regions.iter().enumerate() {
        let ranges = holed_ranges(r.addr(), frames, hole.0, hole.1);
        unsafe { a.init_at(i, r.addr(), bytes, &ranges) };
        usable.extend(holed_usable(r.addr(), frames, hole.0, hole.1));
    }
    (a, regions, usable)
}

#[test]
fn regioned_matches_occupancy_oracle_two_regions() {
    let (a, _regions, usable) = regioned_pool::<2>(FRAMES / 2);
    for &seed in &SEEDS {
        oracle_churn(&a, &usable, seed);
    }
}

#[test]
fn regioned_matches_occupancy_oracle_three_regions() {
    let (a, _regions, usable) = regioned_pool::<3>(FRAMES / 2);
    for &seed in &SEEDS {
        oracle_churn(&a, &usable, seed);
    }
}

#[test]
fn regioned_matches_occupancy_oracle_holed() {
    let (a, _regions, usable) = regioned_pool_holed::<2>(FRAMES / 2, (32, 48));
    for &seed in &SEEDS {
        oracle_churn(&a, &usable, seed);
    }
}

/// Regioned-over-magazine: a per-CPU cache *inside* each region.
///
/// `SLOTS = 1` keeps a single magazine per region, so the oracle's drain-to-OOM
/// conservation check can never strand frames in an idle sibling slot (the same
/// reasoning as [`magazine_pool`]'s `NoCpuId`).
type RegionedDep<const REGIONS: usize> =
    RegionedDepot<REGIONS, SummaryBuddyAllocator<ORDERS, TestProvenance>, RotatingCpu, 1, 8>;

fn regioned_mag_pool<const REGIONS: usize>(
    frames: usize,
) -> (
    RegionedDep<REGIONS>,
    [OwnedRegion; REGIONS],
    Vec<(usize, usize)>,
) {
    let bytes = frames * BASE.bytes();
    let regions: [OwnedRegion; REGIONS] =
        core::array::from_fn(|_| OwnedRegion::new(bytes, max_block()));
    let a: RegionedDep<REGIONS> = RegionedAllocator::new(
        BASE,
        [const {
            DepotAllocator::new(
                BASE,
                SummaryBuddyAllocator::<ORDERS, TestProvenance>::new(BASE),
            )
        }; REGIONS],
    );
    let mut usable = Vec::new();
    for (i, r) in regions.iter().enumerate() {
        unsafe {
            a.init_at(
                i,
                r.addr(),
                bytes,
                &[PhysRange {
                    base: r.addr(),
                    len: bytes,
                }],
            );
        }
        usable.push((r.addr(), r.addr() + bytes));
    }
    (a, regions, usable)
}

#[test]
fn regioned_over_magazine_matches_occupancy_oracle() {
    let (a, _regions, usable) = regioned_mag_pool::<2>(FRAMES / 2);
    for &seed in &SEEDS {
        oracle_churn(&a, &usable, seed);
    }
}

/// A depot over a single contiguous span. Progressive multi-frame OOM recovery
/// is covered by the wrapper-specific tests; this oracle exercises randomized
/// allocation occupancy and conservation.
fn depot_pool() -> DepotAllocator<SummaryBuddyAllocator<ORDERS, TestProvenance>, NoCpuId, 4, 8, 16>
{
    DepotAllocator::new(
        BASE,
        SummaryBuddyAllocator::<ORDERS, TestProvenance>::new(BASE),
    )
}

#[test]
fn depot_matches_occupancy_oracle() {
    let span = FRAMES * BASE.bytes();
    let region = OwnedRegion::new(span, max_block());
    let a = depot_pool();
    unsafe { a.init_region(region.addr(), span) };
    let usable = [(region.addr(), region.addr() + span)];
    for &seed in &SEEDS {
        oracle_churn(&a, &usable, seed);
    }
}

#[test]
fn depot_matches_occupancy_oracle_holed() {
    let span = FRAMES * BASE.bytes();
    let region = OwnedRegion::new(span, max_block());
    let base = region.addr();
    let usable = holed_usable(base, FRAMES, HOLE.0, HOLE.1);
    let ranges = holed_ranges(base, FRAMES, HOLE.0, HOLE.1);
    let a = depot_pool();
    unsafe { a.init(base, span, &ranges) };
    for &seed in &SEEDS {
        oracle_churn(&a, &usable, seed);
    }
}