frame-alloc 0.1.0

//! Black-box API conformance suite.
//!
//! Every test here is written against the public `PhysicalAllocator` +
//! `RegionInit` + `AllocatorStats` contract and instantiated for all three
//! allocators via [`conformance_suite!`], so each implementation is held to one
//! identical spec (differential conformance).
//!
//! Assertions are *report-derived* — they read `free_bytes`/`total_bytes` from
//! the allocator rather than hard-coding capacity constants — so allocators that
//! carve metadata out of the managed pool (e.g. the bitmap buddy's in-pool
//! bitmap) pass without special-casing.
//!
//! `AllocatorStats` is gated behind the `stats` feature, so the report-derived
//! tests are too; run with `cargo test --features stats` for the full suite.
//! The contract-error tests (`InitError` taxonomy, request validation) need no
//! stats and run in every build. Implementation-specific behaviour lives in
//! the white-box unit tests under `src/tests`.

mod common;

use common::{N1, OwnedRegion, PS_64, PS_256, Regioned1, TestProvenance, n};
#[cfg(feature = "stats")]
use frame_alloc::AllocatorStats;
use frame_alloc::{
    AllocError, DepotAllocator, InitError, NoCpuId, PageSize, PhysRange, PhysicalAllocator,
    RegionInit, SummaryBuddyAllocator,
};

/// Page size below the base frame — must be rejected before any pool access.
const PS_32: PageSize = PageSize::from_log2(5);

/// Generate the full conformance suite for one allocator. `$make` is a closure
/// `Fn(PageSize) -> A` returning a freshly-constructed (un-initialised)
/// allocator.
macro_rules! conformance_suite {
    ($name:ident, $make:expr) => {
        mod $name {
            use super::*;
            #[cfg(feature = "stats")]
            use core::sync::atomic::{AtomicUsize, Ordering};
            #[cfg(feature = "stats")]
            use std::collections::HashSet;
            #[cfg(feature = "stats")]
            use std::sync::Arc;
            #[cfg(feature = "stats")]
            use std::thread;
            #[cfg(feature = "stats")]
            use std::vec::Vec;

            /// Build an `$frames`-frame, fully-usable pool aligned to the max
            /// block (so buddy registration is deterministic), binding `$a` to
            /// the allocator and `$region` to the backing memory (kept alive for
            /// the rest of the scope).
            macro_rules! pool {
                ($a:ident, $region:ident, $frames:expr) => {
                    let fs = PS_64.bytes();
                    let $region = OwnedRegion::new(fs * ($frames), PS_256.bytes());
                    let $a = ($make)(PS_64);
                    unsafe { $a.init_region($region.addr(), fs * ($frames)) };
                };
            }

            #[cfg(feature = "stats")]
            #[test]
            fn alloc_is_frame_aligned_and_roundtrips() {
                let fs = PS_64.bytes();
                pool!(a, _region, 8);
                let before = a.free_bytes();

                let p = a.allocate_physical(PS_64, N1).expect("single-frame alloc");
                assert_eq!(p % fs, 0, "address {p:#x} not frame-aligned");
                assert_eq!(
                    a.free_bytes(),
                    before - fs,
                    "exactly one frame leaves the free pool"
                );

                unsafe { a.deallocate_physical(PS_64, N1, p) };
                assert_eq!(a.free_bytes(), before, "free pool restored after dealloc");
            }

            #[cfg(feature = "stats")]
            #[test]
            fn total_bytes_stable_across_alloc() {
                pool!(a, _region, 8);
                let total = a.total_bytes();
                assert!(a.free_bytes() <= total, "free can never exceed total");
                assert!(
                    a.largest_free_bytes() <= total,
                    "largest free block can never exceed total"
                );

                let p = a.allocate_physical(PS_64, N1).expect("alloc");
                assert_eq!(
                    a.total_bytes(),
                    total,
                    "total_bytes must not shrink on alloc"
                );
                unsafe { a.deallocate_physical(PS_64, N1, p) };
                assert_eq!(a.total_bytes(), total, "total_bytes unaffected by dealloc");
            }

            #[cfg(feature = "stats")]
            #[test]
            fn drain_to_empty_then_recover() {
                let fs = PS_64.bytes();
                pool!(a, _region, 8);
                let capacity = a.free_bytes();

                let mut held = Vec::new();
                while let Ok(p) = a.allocate_physical(PS_64, N1) {
                    held.push(p);
                }
                assert_eq!(a.free_bytes(), 0, "drained pool reports zero free");
                assert_eq!(a.largest_free_bytes(), 0, "nothing left to hand out");
                assert_eq!(
                    held.len() * fs,
                    capacity,
                    "drained exactly the free capacity"
                );

                for p in held {
                    unsafe { a.deallocate_physical(PS_64, N1, p) };
                }
                assert_eq!(a.free_bytes(), capacity, "every frame recovered (no leak)");
            }

            #[test]
            fn page_size_below_base_is_invalid() {
                pool!(a, _region, 4);
                assert_eq!(
                    a.allocate_physical(PS_32, N1),
                    Err(AllocError::InvalidPageSize)
                );
            }

            #[test]
            fn oversized_request_errors() {
                pool!(a, _region, 8);
                assert!(a.allocate_physical(PS_64, n(1 << 40)).is_err());
            }

            #[test]
            fn init_err_leaves_allocator_retryable() {
                // A failed `try_init` leaves the allocator in its valid empty
                // state; a corrected retry succeeds and serves memory.
                let fs = PS_64.bytes();
                let frames = 16;
                let region = OwnedRegion::new(fs * frames, PS_256.bytes());
                let a = ($make)(PS_64);

                // phys_base + 1 is not base-frame aligned — a checkable failure.
                let bad = unsafe { a.try_init_region(region.addr() + 1, fs * frames) };
                assert_eq!(
                    bad,
                    Err(InitError::Misaligned {
                        required: PS_64.bytes()
                    })
                );

                // Untouched: the once was not consumed, so a corrected retry works.
                let ok = unsafe { a.try_init_region(region.addr(), fs * frames) };
                assert_eq!(ok, Ok(()));
                let p = a.allocate_physical(PS_64, N1).expect("alloc after retry");
                unsafe { a.deallocate_physical(PS_64, N1, p) };
            }

            #[test]
            fn second_successful_init_returns_already_initialized() {
                let fs = PS_64.bytes();
                let frames = 16;
                let region = OwnedRegion::new(fs * frames, PS_256.bytes());
                let a = ($make)(PS_64);

                let first = unsafe { a.try_init_region(region.addr(), fs * frames) };
                assert_eq!(first, Ok(()));

                let second = unsafe { a.try_init_region(region.addr(), fs * frames) };
                assert_eq!(second, Err(InitError::AlreadyInitialized));
            }

            #[test]
            fn unsorted_usable_errors() {
                let fb = PS_64.bytes();
                let region = OwnedRegion::new(16 * fb, PS_256.bytes());
                let base = region.addr();
                let usable = [
                    PhysRange {
                        base: base + 8 * fb,
                        len: 4 * fb,
                    },
                    PhysRange { base, len: 4 * fb },
                ];
                let a = ($make)(PS_64);
                let e = unsafe { a.try_init(base, 16 * fb, &usable) };
                assert_eq!(e, Err(InitError::InvalidUsable { index: 1 }));
            }

            #[test]
            fn overlapping_usable_errors() {
                let fb = PS_64.bytes();
                let region = OwnedRegion::new(16 * fb, PS_256.bytes());
                let base = region.addr();
                let usable = [
                    PhysRange { base, len: 8 * fb },
                    PhysRange {
                        base: base + 4 * fb,
                        len: 8 * fb,
                    },
                ];
                let a = ($make)(PS_64);
                let e = unsafe { a.try_init(base, 16 * fb, &usable) };
                assert_eq!(e, Err(InitError::InvalidUsable { index: 1 }));
            }

            #[test]
            fn out_of_span_usable_errors() {
                let fb = PS_64.bytes();
                let region = OwnedRegion::new(16 * fb, PS_256.bytes());
                let base = region.addr();
                // 20 frames of usable range in a 16-frame span.
                let usable = [PhysRange { base, len: 20 * fb }];
                let a = ($make)(PS_64);
                let e = unsafe { a.try_init(base, 16 * fb, &usable) };
                assert_eq!(e, Err(InitError::InvalidUsable { index: 0 }));
            }

            #[test]
            fn empty_range_errors() {
                let fb = PS_64.bytes();
                let region = OwnedRegion::new(16 * fb, PS_256.bytes());
                let base = region.addr();
                let usable = [PhysRange { base, len: 0 }];
                let a = ($make)(PS_64);
                let e = unsafe { a.try_init(base, 16 * fb, &usable) };
                assert_eq!(e, Err(InitError::InvalidUsable { index: 0 }));
            }

            #[test]
            fn unaligned_range_base_errors() {
                let fb = PS_64.bytes();
                let region = OwnedRegion::new(16 * fb, PS_256.bytes());
                let base = region.addr();
                let usable = [PhysRange {
                    base: base + 1,
                    len: 4 * fb,
                }];
                let a = ($make)(PS_64);
                let e = unsafe { a.try_init(base, 16 * fb, &usable) };
                assert_eq!(e, Err(InitError::InvalidUsable { index: 0 }));
            }

            #[test]
            fn unaligned_range_len_errors() {
                let fb = PS_64.bytes();
                let region = OwnedRegion::new(16 * fb, PS_256.bytes());
                let base = region.addr();
                let usable = [PhysRange {
                    base,
                    len: 4 * fb + 1,
                }];
                let a = ($make)(PS_64);
                let e = unsafe { a.try_init(base, 16 * fb, &usable) };
                assert_eq!(e, Err(InitError::InvalidUsable { index: 0 }));
            }

            #[test]
            fn init_zero_total_frames_errors() {
                let region = OwnedRegion::new(PS_256.bytes(), PS_256.bytes());
                let a = ($make)(PS_64);
                let e = unsafe { a.try_init_region(region.addr(), 0) };
                assert_eq!(e, Err(InitError::InvalidSpan));
            }

            #[cfg(feature = "stats")]
            #[test]
            fn holes_are_never_handed_out() {
                let fb = PS_64.bytes();
                let region = OwnedRegion::new(fb * 16, PS_256.bytes());
                let base = region.addr();
                let a = ($make)(PS_64);
                // Frames [0,4) and [12,16) usable; [4,12) reserved.
                let usable = [
                    PhysRange { base, len: 4 * fb },
                    PhysRange {
                        base: base + 12 * fb,
                        len: 4 * fb,
                    },
                ];
                unsafe { a.init(base, fb * 16, &usable) };

                // total_bytes counts usable frames only - With the pool fully free
                // it equals free_bytes, is frame-aligned, and never exceeds the 8
                // usable frames.
                let total = a.total_bytes();
                assert_eq!(total % fb, 0, "total_bytes is frame-aligned");
                assert_eq!(total, a.free_bytes(), "fully-free pool: total == free");
                assert!(total <= 8 * fb, "the 8 hole frames are excluded from total");

                // Drain every frame the pool will hand out. None may fall in the
                // hole, and the count must equal the capacity total_bytes
                // advertised.
                let (hole_lo, hole_hi) = (base + 4 * fb, base + 12 * fb);
                let mut handed = 0;
                while let Ok(p) = a.allocate_physical(PS_64, N1) {
                    assert!(
                        !(hole_lo..hole_hi).contains(&p),
                        "handed out a reserved hole frame {p:#x}"
                    );
                    handed += 1;
                }
                assert_eq!(
                    handed * fb,
                    total,
                    "drained capacity matches advertised total_bytes"
                );
            }

            #[cfg(feature = "stats")]
            #[test]
            fn add_usable_grows_free_pool() {
                let fb = PS_64.bytes();
                let region = OwnedRegion::new(fb * 16, PS_256.bytes());
                let base = region.addr();
                let a = ($make)(PS_64);
                let usable = [
                    PhysRange { base, len: 4 * fb },
                    PhysRange {
                        base: base + 12 * fb,
                        len: 4 * fb,
                    },
                ];
                unsafe { a.init(base, fb * 16, &usable) };
                let free_before = a.free_bytes();
                let total_before = a.total_bytes();
                assert_eq!(total_before, free_before, "fully-free pool: total == free");

                // Activate the previously-reserved 8-frame hole [4,12).
                unsafe { a.add_usable(base + 4 * fb, 8 * fb) };
                assert_eq!(
                    a.free_bytes(),
                    free_before + 8 * fb,
                    "activating the hole adds exactly its frames to the free pool"
                );
                assert_eq!(
                    a.total_bytes(),
                    total_before + 8 * fb,
                    "activating the hole raises total capacity by the same frames"
                );
                assert_eq!(
                    a.total_bytes(),
                    a.free_bytes(),
                    "still fully free: total == free"
                );

                // The newly activated frames are genuinely allocatable: draining
                // hands out exactly the grown capacity.
                let mut handed = 0;
                while a.allocate_physical(PS_64, N1).is_ok() {
                    handed += 1;
                }
                assert_eq!(
                    handed * fb,
                    free_before + 8 * fb,
                    "drained capacity matches the grown pool"
                );
            }

            #[cfg(feature = "stats")]
            #[cfg_attr(audit, ignore = "audit builds are sequential-only")]
            #[test]
            fn concurrent_alloc_no_duplicates() {
                const N_THREADS: usize = if cfg!(miri) { 4 } else { 8 };
                const N_FRAMES: usize = if cfg!(miri) { 16 } else { 64 };
                let fs = PS_64.bytes();
                let region = OwnedRegion::new(fs * N_FRAMES, PS_256.bytes());
                let a = Arc::new(($make)(PS_64));
                unsafe { a.init_region(region.addr(), fs * N_FRAMES) };

                // Allocatable frames (excludes any in-pool metadata reservation).
                let capacity = a.free_bytes() / fs;

                // The buddies' relaxed-peek fast path can return a spurious
                // OutOfMemory while a block is mid-split, so threads retry until
                // every allocatable frame is provably accounted for.
                let handed_out = Arc::new(AtomicUsize::new(0));
                let handles: Vec<_> = (0..N_THREADS)
                    .map(|_| {
                        let a = Arc::clone(&a);
                        let handed_out = Arc::clone(&handed_out);
                        thread::spawn(move || {
                            let mut local = Vec::new();
                            loop {
                                match a.allocate_physical(PS_64, N1) {
                                    Ok(addr) => {
                                        handed_out.fetch_add(1, Ordering::Relaxed);
                                        local.push(addr);
                                    }
                                    Err(_) => {
                                        if handed_out.load(Ordering::Relaxed) >= capacity {
                                            break;
                                        }
                                    }
                                }
                            }
                            local
                        })
                    })
                    .collect();

                let all: Vec<usize> = handles
                    .into_iter()
                    .flat_map(|h| h.join().unwrap())
                    .collect();
                let unique: HashSet<usize> = all.iter().copied().collect();
                assert_eq!(unique.len(), all.len(), "duplicate addresses allocated");
                assert_eq!(all.len(), capacity, "wrong total number of frames");

                for addr in unique {
                    unsafe { a.deallocate_physical(PS_64, N1, addr) };
                }
                assert_eq!(a.free_bytes(), capacity * fs, "pool fully reassembled");
            }

            #[cfg(feature = "stats")]
            #[cfg_attr(audit, ignore = "audit builds are sequential-only")]
            #[test]
            fn concurrent_alloc_dealloc_churn() {
                // A pool much smaller than the thread count forces every alloc to
                // race against other threads' concurrent deallocs.
                const N_THREADS: usize = if cfg!(miri) { 4 } else { 8 };
                const N_FRAMES: usize = 4;
                const ITERS: usize = if cfg!(miri) { 16 } else { 4000 };
                let fs = PS_64.bytes();
                let region = OwnedRegion::new(fs * N_FRAMES, PS_256.bytes());
                let a = Arc::new(($make)(PS_64));
                unsafe { a.init_region(region.addr(), fs * N_FRAMES) };
                let before = a.free_bytes();

                let handles: Vec<_> = (0..N_THREADS)
                    .map(|_| {
                        let a = Arc::clone(&a);
                        thread::spawn(move || {
                            for _ in 0..ITERS {
                                loop {
                                    if let Ok(p) = a.allocate_physical(PS_64, N1) {
                                        unsafe { a.deallocate_physical(PS_64, N1, p) };
                                        break;
                                    }
                                }
                            }
                        })
                    })
                    .collect();
                for h in handles {
                    h.join().unwrap();
                }

                assert_eq!(
                    a.free_bytes(),
                    before,
                    "every alloc matched by a dealloc; no leak"
                );
            }
        }
    };
}

conformance_suite!(summary_buddy, |ps: PageSize| {
    SummaryBuddyAllocator::<3, TestProvenance>::new(ps)
});
conformance_suite!(regioned, |ps: PageSize| {
    Regioned1::new(ps, SummaryBuddyAllocator::<3, TestProvenance>::new(ps))
});
conformance_suite!(depot, |ps: PageSize| {
    DepotAllocator::<_, NoCpuId, 4, 8, 16>::new(
        ps,
        SummaryBuddyAllocator::<3, TestProvenance>::new(ps),
    )
});
conformance_suite!(regioned_over_depot, |ps: PageSize| {
    Regioned1::new(
        ps,
        DepotAllocator::<_, NoCpuId, 4, 8, 16>::new(
            ps,
            SummaryBuddyAllocator::<3, TestProvenance>::new(ps),
        ),
    )
});