frame-alloc 0.1.0

//! White-box, summary-buddy-specific tests.
//!
//! Allocator-agnostic API conformance (alloc/dealloc round-trips, holes, stats
//! invariants, concurrency) and the randomised occupancy oracle live in the
//! external black-box suite under `tests/`.

extern crate std;

use crate::tests::common::{N1, OwnedRegion, TestProvenance, n};
use crate::{
    AllocError, AllocatorStats, InitError, PageSize, PhysRange, PhysicalAllocator, RegionInit,
    SummaryBuddyAllocator,
};
use alloc::vec::Vec;
use std::collections::HashSet;

const PS_64: PageSize = PageSize::from_log2(6);
const PS_256: PageSize = PageSize::from_log2(8);
const ORDERS: usize = 3;
const SUMMARY_ACTIVE_FRAMES: usize = 9_000;
const CURSOR_ACTIVE_FRAMES: usize = 132_000;

// `new` must be `const fn`.
static _STATIC_SUMMARY: SummaryBuddyAllocator<ORDERS, TestProvenance> =
    SummaryBuddyAllocator::new(PS_64);

/// Build a fully-usable `frames`-frame pool aligned to the max block, returning
/// the allocator and its backing region (which must outlive the allocator — the
/// bitmap pointer lives inside it).
fn pool(frames: usize) -> (SummaryBuddyAllocator<ORDERS, TestProvenance>, OwnedRegion) {
    let region = OwnedRegion::new(frames * PS_64.bytes(), PS_256.bytes());
    let alloc = SummaryBuddyAllocator::<ORDERS, TestProvenance>::new(PS_64);
    unsafe { alloc.init_region(region.addr(), frames * PS_64.bytes()) };
    (alloc, region)
}

#[test]
fn reserved_frames_carved_from_pool() {
    let fs = PS_64.bytes();
    let frames = 8;
    let region = OwnedRegion::new(fs * frames, PS_256.bytes());
    let alloc = SummaryBuddyAllocator::<ORDERS, TestProvenance>::new(PS_64);
    unsafe { alloc.init_region(region.addr(), fs * frames) };

    // The bitmap (L1 + summary) lives inside the pool, so at least one frame is
    // consumed and never handed out — total_bytes/free_bytes exclude it.
    let reserved = alloc.reserved_frames();
    assert!(reserved >= 1, "bitmap must occupy at least one frame");
    assert_eq!(
        alloc.total_bytes(),
        (frames - reserved) * fs,
        "total excludes the in-pool bitmap frames"
    );
    assert_eq!(
        alloc.free_bytes(),
        (frames - reserved) * fs,
        "a fresh pool is fully free apart from the bitmap"
    );
}

#[test]
fn reserved_frames_zero_before_init() {
    let alloc = SummaryBuddyAllocator::<ORDERS, TestProvenance>::new(PS_64);
    assert_eq!(alloc.reserved_frames(), 0, "no reservation before init");
}

#[test]
fn free_stats_split_and_merge() {
    let fb = PS_64.bytes();
    let span = 8 * fb;
    let region = OwnedRegion::new(span, PS_256.bytes());
    let base = region.addr();
    let alloc = SummaryBuddyAllocator::<ORDERS, TestProvenance>::new(PS_64);

    // Range [0,1) hosts the (one-frame) bitmap; range [4,8) is one order-2 block.
    let usable = [
        PhysRange { base, len: fb },
        PhysRange {
            base: base + 4 * fb,
            len: 4 * fb,
        },
    ];
    unsafe { alloc.init(base, span, &usable) };
    assert_eq!(
        alloc.free_stats(),
        [0, 0, 1],
        "the leftover range is a single top-order block"
    );
    assert!(
        alloc.debug_summary_exact(),
        "summary must track the L1 words after init"
    );

    let p = alloc.allocate_physical(PS_64, N1).expect("order-0 alloc");
    assert_eq!(p, base + 4 * fb, "served from the order-2 block");
    assert_eq!(
        alloc.free_stats(),
        [1, 1, 0],
        "split leaves one block at order 0 and order 1"
    );
    assert!(alloc.debug_summary_exact(), "summary tracks the split");

    unsafe { alloc.deallocate_physical(PS_64, N1, p) };
    assert_eq!(
        alloc.free_stats(),
        [0, 0, 1],
        "merges back to one top-order block"
    );
    assert!(alloc.debug_summary_exact(), "summary tracks the merge");
}

#[test]
fn stats_total_largest_and_free_bytes() {
    let fs = PS_64.bytes();
    // A whole-span pool: the one bitmap frame is carved off, leaving seven
    // allocatable frames laid out greedily as one block each at orders 0, 1, 2.
    let (alloc, _region) = pool(8);

    assert_eq!(
        alloc.free_stats(),
        [1, 1, 1],
        "greedy split of the remainder"
    );
    assert_eq!(alloc.total_bytes(), 7 * fs, "registered capacity");
    assert_eq!(alloc.free_bytes(), 7 * fs);
    assert_eq!(
        alloc.largest_free_bytes(),
        4 * fs,
        "the order-2 block is the largest run"
    );

    // Take the max-order block. The largest free run shrinks to the order-1
    // remainder, but total_bytes must not.
    let big = alloc.allocate_physical(PS_256, N1).expect("order-2 alloc");
    assert_eq!(
        alloc.largest_free_bytes(),
        2 * fs,
        "order-1 remainder after taking the max block"
    );
    assert_eq!(alloc.free_bytes(), 3 * fs);
    assert_eq!(
        alloc.total_bytes(),
        7 * fs,
        "total_bytes must not shrink on alloc"
    );

    unsafe { alloc.deallocate_physical(PS_256, N1, big) };
    assert_eq!(
        alloc.largest_free_bytes(),
        4 * fs,
        "coalesces back to the full block"
    );
    assert_eq!(alloc.free_bytes(), 7 * fs);
    assert_eq!(
        alloc.total_bytes(),
        7 * fs,
        "total_bytes unaffected by dealloc"
    );
}

#[test]
fn summary_consistent_under_churn() {
    // A pool big enough that order 0 spans several L1 words, so the summary has
    // more than one tracked bit and `sync_summary` must flip bits both ways as
    // words empty and refill.
    let (alloc, _region) = pool(130);
    assert!(
        alloc.debug_summary_exact(),
        "summary consistent on a fresh multi-word pool"
    );

    // Drain a batch of order-0 frames, checking the summary after every grab.
    let mut held = Vec::new();
    for _ in 0..48 {
        let Ok(p) = alloc.allocate_physical(PS_64, N1) else {
            break;
        };
        held.push(p);
        assert!(
            alloc.debug_summary_exact(),
            "summary diverged after an order-0 alloc"
        );
    }
    assert!(
        held.len() >= 2,
        "the pool must yield several order-0 frames"
    );

    // Return them in a non-sequential order (every other one, then the rest) so
    // merges and re-splits exercise both summary transitions.
    for &p in held.iter().step_by(2) {
        unsafe { alloc.deallocate_physical(PS_64, N1, p) };
        assert!(
            alloc.debug_summary_exact(),
            "summary diverged after an order-0 dealloc"
        );
    }
    for (i, &p) in held.iter().enumerate() {
        if i % 2 == 1 {
            unsafe { alloc.deallocate_physical(PS_64, N1, p) };
            assert!(
                alloc.debug_summary_exact(),
                "summary diverged draining the remainder"
            );
        }
    }
}

#[test]
fn phantom_prefix_reserved_for_unaligned_phys_base() {
    // Real usable RAM starts one base frame into a max block, so `phys_base` is
    // not max-page aligned. `init` rounds the coordinate origin down internally;
    // the gap [aligned, phys_base) is a phantom prefix that must never be handed
    // out. The caller passes its real `phys_base`/`span_len` — no pre-rounding.
    let fb = PS_64.bytes();
    let region = OwnedRegion::new(8 * fb, PS_256.bytes());
    let aligned = region.addr();
    let real_base = aligned + fb; // offset 64 B — not 256-aligned
    let real_len = 4 * fb;

    let alloc = SummaryBuddyAllocator::<ORDERS, TestProvenance>::new(PS_64); // max_page = 256

    unsafe {
        alloc.init(
            real_base,
            real_len,
            &[PhysRange {
                base: real_base,
                len: real_len,
            }],
        )
    };

    // Everything handed out lies inside the real RAM; never the phantom prefix
    // [aligned, real_base) nor beyond real RAM.
    let mut handed = Vec::new();
    while let Ok(p) = alloc.allocate_physical(PS_64, N1) {
        assert!(
            (real_base..real_base + real_len).contains(&p),
            "handed out a phantom-prefix or out-of-range frame {p:#x}"
        );
        handed.push(p);
    }
    assert!(!handed.is_empty(), "real RAM must yield at least one frame");
}

#[test]
#[should_panic(expected = "ORDERS must be > 0")]
fn zero_orders_panics() {
    // Call `with_max_page` directly: `new` would first underflow computing the
    // default max block for ORDERS = 0, panicking for a different reason.
    let _ = SummaryBuddyAllocator::<0, TestProvenance>::with_max_page(PS_64, PS_64);
}

#[test]
#[should_panic(expected = "max_page must be in base_frame")]
fn max_page_above_top_block_panics() {
    // max_page log2 = 9 == base.log2()(6) + ORDERS(3); the guard requires it to be
    // strictly less, so this is out of range.
    let _ = SummaryBuddyAllocator::<ORDERS, TestProvenance>::with_max_page(
        PS_64,
        PageSize::from_log2(9),
    );
}

#[test]
#[should_panic(expected = "deallocate_physical: invalid page size or count")]
fn dealloc_invalid_page_size_panics() {
    const PS_32: PageSize = PageSize::from_log2(5);
    let fb = PS_64.bytes();
    let region = OwnedRegion::new(fb * 4, PS_256.bytes());
    let base = region.addr();
    let alloc = SummaryBuddyAllocator::<ORDERS, TestProvenance>::new(PS_64);
    unsafe { alloc.init_region(base, fb * 4) };
    unsafe { alloc.deallocate_physical(PS_32, N1, base) };
}

#[test]
fn managed_frames_not_written() {
    let fs = PS_64.bytes();
    let total = 8;
    let region = OwnedRegion::new(fs * total, PS_256.bytes());
    let base = region.addr();
    let alloc = SummaryBuddyAllocator::<ORDERS, TestProvenance>::new(PS_64);
    unsafe { alloc.init_region(base, fs * total) };

    // A whole-span init hosts the bitmap at the span start, so allocatable frames
    // begin after `reserved` frames.
    let reserved = alloc.reserved_frames();
    let alloc_start = base + reserved * fs;
    let alloc_bytes = (total - reserved) * fs;
    let slice: &mut [u8] = unsafe {
        core::slice::from_raw_parts_mut(
            core::ptr::with_exposed_provenance_mut(alloc_start),
            alloc_bytes,
        )
    };
    slice.fill(0xAB);

    // Drain the whole allocatable pool and return it.
    let mut addrs = Vec::new();
    while let Ok(p) = alloc.allocate_physical(PS_64, N1) {
        addrs.push(p);
    }
    for &p in &addrs {
        unsafe { alloc.deallocate_physical(PS_64, N1, p) };
    }

    assert!(
        slice.iter().all(|&b| b == 0xAB),
        "allocator wrote into managed (non-bitmap) frames"
    );
}

#[test]
fn adjacent_add_regions_merge() {
    let half = PS_256.bytes() / 2;
    let (alloc, _region) = pool(16);

    let mut blocks = Vec::new();
    while let Ok(b) = alloc.allocate_physical(PS_256, N1) {
        blocks.push(b);
    }
    let block = *blocks.first().expect("at least one order-2 block");

    unsafe { alloc.add_usable(block, half) };
    unsafe { alloc.add_usable(block + half, half) };

    let merged = alloc
        .allocate_physical(PS_256, N1)
        .expect("merged block not available after adjacent add_region");
    assert_eq!(
        merged, block,
        "halves must merge back into one order-2 block"
    );

    unsafe { alloc.deallocate_physical(PS_256, N1, merged) };
    for b in blocks.into_iter().skip(1) {
        unsafe { alloc.deallocate_physical(PS_256, N1, b) };
    }
}

#[test]
fn multi_frame_count_rounds_up_to_order() {
    // count = 3 frames rounds up to the next power of two (4 = order 2), so a
    // single max block satisfies it and is returned max-block aligned.
    let fb = PS_64.bytes();
    let (alloc, _region) = pool(8);

    let count3 = n(3);
    let phys = alloc
        .allocate_physical(PS_64, count3)
        .expect("multi-frame alloc");
    assert_eq!(phys % (4 * fb), 0, "order-2 block must be 4-frame aligned");

    // dealloc must replay the same (ps, count) contract.
    unsafe { alloc.deallocate_physical(PS_64, count3, phys) };
    let phys2 = alloc
        .allocate_physical(PS_64, count3)
        .expect("re-alloc after dealloc");
    assert_eq!(phys2, phys, "same block after dealloc");
    unsafe { alloc.deallocate_physical(PS_64, count3, phys2) };
}

#[test]
fn request_exceeding_max_order_is_too_large() {
    let alloc = SummaryBuddyAllocator::<ORDERS, TestProvenance>::new(PS_64);
    // PS_256 (order 2) * 2 = 512 B = 8 frames -> order 3 == ORDERS. Rejected
    // before any pool access, so no init is required.
    assert_eq!(
        alloc.allocate_physical(PS_256, n(2)),
        Err(AllocError::RequestTooLarge)
    );
}

#[test]
fn init_phys_base_not_max_aligned_rounds_down() {
    let fb = PS_64.bytes();
    let region = OwnedRegion::new(8 * fb, PS_256.bytes());
    let base = region.addr();
    let alloc = SummaryBuddyAllocator::<ORDERS, TestProvenance>::new(PS_64);
    // base + one frame is base-frame aligned but not max_page (256 B) aligned.
    // This is no longer an error: init rounds the origin down to `base` and
    // reserves the one-frame phantom prefix.
    let r = unsafe { alloc.try_init_region(base + fb, 7 * fb) };
    assert_eq!(r, Ok(()));
    // Nothing handed out may fall in the phantom prefix [base, base + fb).
    while let Ok(p) = alloc.allocate_physical(PS_64, N1) {
        assert!(p >= base + fb, "handed out a phantom-prefix frame {p:#x}");
    }
}

#[test]
#[should_panic(expected = "falls outside the initialised span")]
fn add_usable_out_of_span_panics() {
    let total = 16;
    let (alloc, region) = pool(total);
    let base = region.addr();
    // One frame past the end of the initialised span.
    unsafe { alloc.add_usable(base + total * PS_64.bytes(), PS_64.bytes()) };
}

#[test]
#[should_panic(expected = "call init before deallocate")]
fn dealloc_on_uninit_panics() {
    let alloc = SummaryBuddyAllocator::<ORDERS, TestProvenance>::new(PS_64);
    unsafe { alloc.deallocate_physical(PS_64, N1, PS_64.bytes()) };
}

#[test]
fn alloc_on_uninit_returns_oom() {
    // Fail-safe: an uninitialised allocator has a null bitmap, but every
    // `free_counts[k]` is zero so the alloc scan short-circuits to OutOfMemory
    // rather than dereferencing the null pointer.
    let alloc = SummaryBuddyAllocator::<ORDERS, TestProvenance>::new(PS_64);
    assert_eq!(
        alloc.allocate_physical(PS_64, N1),
        Err(AllocError::OutOfMemory)
    );
}

#[test]
#[should_panic(expected = "called before init")]
fn add_usable_on_uninit_panics() {
    let alloc = SummaryBuddyAllocator::<ORDERS, TestProvenance>::new(PS_64);
    unsafe { alloc.add_usable(PS_64.bytes(), PS_64.bytes()) };
}

#[test]
fn empty_usable_metadata_wont_fit() {
    let region = OwnedRegion::new(16 * PS_64.bytes(), PS_256.bytes());
    let alloc = SummaryBuddyAllocator::<ORDERS, TestProvenance>::new(PS_64);
    // No usable range at all — there is nowhere to carve the bitmap from.
    let e = unsafe { alloc.try_init(region.addr(), 16 * PS_64.bytes(), &[]) };
    match e {
        Err(InitError::MetadataWontFit { required_bytes }) => {
            // The bitmap needs at least one frame; a plausible, non-zero figure.
            assert!(required_bytes >= PS_64.bytes());
            assert_eq!(required_bytes % PS_64.bytes(), 0);
        }
        other => panic!("expected MetadataWontFit, got {other:?}"),
    }
}

#[test]
fn bitmap_hosted_past_span_start_hole() {
    const TOTAL: usize = 16;
    let fb = PS_64.bytes();
    let region = OwnedRegion::new(TOTAL * fb, PS_256.bytes());
    let base = region.addr();
    let usable = [PhysRange {
        base: base + 8 * fb,
        len: 8 * fb,
    }];
    let alloc = SummaryBuddyAllocator::<ORDERS, TestProvenance>::new(PS_64);
    unsafe { alloc.init(base, TOTAL * fb, &usable) };

    let reserved = alloc.reserved_frames();
    assert!(reserved > 0, "bitmap should occupy at least one frame");
    let first_alloc_lo = base + 8 * fb + reserved * fb;

    let mut addrs = HashSet::new();
    while let Ok(a) = alloc.allocate_physical(PS_64, N1) {
        assert!(
            a >= first_alloc_lo,
            "frame {a:#x} fell in the span-start hole or the bitmap host prefix"
        );
        assert!(addrs.insert(a), "frame {a:#x} handed out twice");
    }
    assert_eq!(addrs.len(), 8 - reserved, "wrong allocatable count");
}

#[test]
fn with_max_page_relaxes_phys_base_alignment() {
    // max_page = 128 B (< 256 B max block), so a phys_base aligned to 128 but not
    // 256 is accepted - `new`'s default (max_page = 256) would panic here.
    const MID: PageSize = PageSize::from_log2(7); // 128 B
    let fb = PS_64.bytes();
    let region = OwnedRegion::new(8 * fb, PS_256.bytes()); // 256-aligned
    let phys = region.addr() + 2 * fb; // +128 -> 128-aligned, not 256
    assert_eq!(phys % MID.bytes(), 0);
    assert_ne!(phys % PS_256.bytes(), 0);
    let alloc = SummaryBuddyAllocator::<ORDERS, TestProvenance>::with_max_page(PS_64, MID);
    unsafe { alloc.init_region(phys, 6 * fb) };
    assert!(
        alloc.allocate_physical(PS_64, N1).is_ok(),
        "alloc after relaxed init"
    );
}

#[test]
fn allocate_physical_rejects_page_above_max_page() {
    // max_page caps the largest page a caller may request: a page larger than it is
    // rejected as InvalidPageSize even when ORDERS could otherwise hold the block.
    const MID: PageSize = PageSize::from_log2(7); // 128 B = order 1
    let fb = PS_64.bytes();
    let region = OwnedRegion::new(16 * fb, PS_256.bytes());
    let alloc = SummaryBuddyAllocator::<ORDERS, TestProvenance>::with_max_page(PS_64, MID);
    unsafe { alloc.init_region(region.addr(), 16 * fb) };
    assert_eq!(
        alloc.allocate_physical(PS_256, N1),
        Err(AllocError::InvalidPageSize)
    );
    assert!(
        alloc.allocate_physical(MID, N1).is_ok(),
        "a request at exactly max_page must succeed"
    );
}

#[cfg_attr(audit, ignore = "audit builds are sequential-only")]
#[test]
fn summary_multiword_scan() {
    let (alloc, _region) = pool(SUMMARY_ACTIVE_FRAMES);
    let n_alloc = SUMMARY_ACTIVE_FRAMES - alloc.reserved_frames();

    let addrs: Vec<usize> = (0..n_alloc)
        .map(|_| alloc.allocate_physical(PS_64, N1).expect("drain failed"))
        .collect();
    assert!(
        alloc.allocate_physical(PS_64, N1).is_err(),
        "pool should be exhausted"
    );

    let unique: HashSet<usize> = addrs.iter().copied().collect();
    assert_eq!(unique.len(), addrs.len(), "duplicate addresses handed out");

    for &a in addrs.iter().rev() {
        unsafe { alloc.deallocate_physical(PS_64, N1, a) };
    }
    assert_eq!(alloc.free_bytes(), n_alloc * PS_64.bytes());
    assert!(
        alloc.debug_summary_exact(),
        "summary inconsistent after multi-word drain/refill"
    );
}

#[test]
fn stale_positive_summary_bit_is_repaired_on_probe() {
    let (alloc, region) = pool(SUMMARY_ACTIVE_FRAMES);
    let n_alloc = SUMMARY_ACTIVE_FRAMES - alloc.reserved_frames();

    let addrs: Vec<usize> = (0..n_alloc)
        .map(|_| alloc.allocate_physical(PS_64, N1).expect("drain failed"))
        .collect();
    assert!(
        alloc.allocate_physical(PS_64, N1).is_err(),
        "pool should be exhausted"
    );

    let base = region.addr();
    let word_bits = usize::BITS as usize;
    let real = addrs
        .iter()
        .copied()
        .find(|&p| ((p - base) / PS_64.bytes()) / word_bits > 0)
        .expect("pool should contain an allocatable frame beyond L1 word 0");
    unsafe { alloc.deallocate_physical(PS_64, N1, real) };
    assert!(
        alloc.debug_summary_exact(),
        "single deallocation should leave an exact summary before corruption"
    );

    alloc.corrupt_set_summary_bit(0, 0);
    assert!(
        alloc.debug_summary_consistent(),
        "stale-positive bits are allowed by the one-sided invariant"
    );
    assert!(
        !alloc.debug_summary_exact(),
        "exact sequential checker should still detect the stale positive"
    );

    assert_eq!(
        alloc.allocate_physical(PS_64, N1),
        Ok(real),
        "allocation should skip the stale summary word and find the real free frame"
    );
    assert!(
        alloc.debug_summary_exact(),
        "probing the stale summary bit should repair it"
    );
}

#[cfg_attr(audit, ignore = "audit builds are sequential-only")]
#[test]
fn cursor_active_drain_refill() {
    let (alloc, _region) = pool(CURSOR_ACTIVE_FRAMES);
    let n_alloc = CURSOR_ACTIVE_FRAMES - alloc.reserved_frames();

    let addrs: Vec<usize> = (0..n_alloc)
        .map(|_| alloc.allocate_physical(PS_64, N1).expect("drain failed"))
        .collect();
    assert!(
        alloc.allocate_physical(PS_64, N1).is_err(),
        "pool should be exhausted"
    );

    let unique: HashSet<usize> = addrs.iter().copied().collect();
    assert_eq!(
        unique.len(),
        addrs.len(),
        "duplicate addresses with cursor active"
    );

    for &a in addrs.iter().rev() {
        unsafe { alloc.deallocate_physical(PS_64, N1, a) };
    }
    assert_eq!(alloc.free_bytes(), n_alloc * PS_64.bytes());
    assert!(
        alloc.debug_summary_exact(),
        "summary inconsistent after cursor-active drain/refill"
    );
}

#[cfg(audit)]
#[test]
#[should_panic(expected = "both free (should have merged)")]
fn audit_detects_unmerged_buddies() {
    // Order-0 block 1 (frame 1) is free after init; force its buddy (block 0,
    // the bitmap frame) free too — two free order-0 buddies the merge machinery
    // must never leave.
    let (alloc, _region) = pool(8);
    alloc.corrupt_set_free_bit(0, 0);
    alloc.run_audit();
}

#[cfg(audit)]
#[test]
#[should_panic(expected = "stray free bit")]
fn audit_detects_stray_bit() {
    // Order 0 has 8 blocks (bits 0..8); bit 60 lies in the word's padding tail.
    let (alloc, _region) = pool(8);
    alloc.corrupt_set_free_bit(0, 60);
    alloc.run_audit();
}