//! Page-aligned free-RAM planning and a bounded single-CPU frame allocator.

use crate::{bootinfo, dtb::MAX_RESERVATIONS};
use core::cell::UnsafeCell;
use core::mem::MaybeUninit;
use core::sync::atomic::{AtomicBool, AtomicU64, Ordering};

pub const PAGE_SIZE: u64 = 4096;
// Each reservation can split one free region in two. Account for both the
// FDT sources, image/DTB, and two UEFI BootInfo-owned allocations.
const MAX_FREE: usize = 2 * MAX_RESERVATIONS + 5;

#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub struct Region {
    pub start: u64,
    pub end: u64,
}

#[derive(Debug, PartialEq, Eq)]
pub enum Error {
    Invalid,
    TooManyRegions,
    CorruptSignature,
}

/// A caller requesting an exact frame must not widen the admitted RAM set.
#[derive(Debug, PartialEq, Eq)]
pub enum FrameRequestError {
    InvalidAddress,
    OutsideAuthority,
    NotFree,
    Metadata(Error),
}

#[derive(Clone)]
pub struct FreeMap {
    regions: [Region; MAX_FREE],
    len: usize,
    signature: u64,
}

/// Allocates only pages present in the finalized free map. Metadata is kept
/// in the kernel image, not in guest RAM; a fragmented map can hit MAX_FREE.
pub struct FrameAllocator {
    allowed: FreeMap,
    free: FreeMap,
}

/// K466: an IRQ-masked, Normal-memory-only SMP owner for FrameAllocator.
/// Never acquire this lock while the MMU is off or from an IRQ handler.
pub struct LockedFrameAllocator {
    owned: AtomicBool,
    ready: AtomicBool,
    contentions: AtomicU64,
    value: UnsafeCell<MaybeUninit<FrameAllocator>>,
}

// SAFETY: every access to `value` after single-CPU initialization is under
// the acquire/release lock. The caller must keep it in shareable Normal RAM.
unsafe impl Sync for LockedFrameAllocator {}

struct FrameLockGuard<'a>(&'a LockedFrameAllocator);

impl Drop for FrameLockGuard<'_> {
    fn drop(&mut self) {
        self.0.owned.store(false, Ordering::Release);
    }
}

impl LockedFrameAllocator {
    pub const fn new() -> Self {
        Self {
            owned: AtomicBool::new(false),
            ready: AtomicBool::new(false),
            contentions: AtomicU64::new(0),
            value: UnsafeCell::new(MaybeUninit::uninit()),
        }
    }

    /// # Safety
    /// Call exactly once on the boot CPU before any secondary or IRQ can use
    /// this object. The allocator must outlive all users of the lock.
    pub unsafe fn initialize_single_cpu(&self, allocator: FrameAllocator) {
        assert!(!self.ready.load(Ordering::Relaxed));
        unsafe { (*self.value.get()).write(allocator) };
        self.ready.store(true, Ordering::Release);
    }

    pub fn with<R>(&self, operation: impl FnOnce(&mut FrameAllocator) -> R) -> Option<R> {
        if !self.ready.load(Ordering::Acquire) {
            return None;
        }
        while self
            .owned
            .compare_exchange_weak(false, true, Ordering::Acquire, Ordering::Relaxed)
            .is_err()
        {
            self.contentions.fetch_add(1, Ordering::Relaxed);
            core::hint::spin_loop();
        }
        let guard = FrameLockGuard(self);
        // SAFETY: initialization precedes sharing; the acquire lock gives
        // unique mutable access until the release guard is dropped.
        let result = operation(unsafe { (*self.value.get()).assume_init_mut() });
        drop(guard);
        Some(result)
    }

    pub fn contention_count(&self) -> u64 {
        self.contentions.load(Ordering::Relaxed)
    }
}

fn align_down(value: u64) -> u64 {
    value & !(PAGE_SIZE - 1)
}

fn align_up(value: u64) -> Result<u64, Error> {
    value
        .checked_add(PAGE_SIZE - 1)
        .map(align_down)
        .ok_or(Error::Invalid)
}

impl FreeMap {
    // A bounded metadata checksum detects accidental corruption before an
    // address can be handed out or returned. It is not a MAC against an
    // attacker who can rewrite both the map and its signature.
    fn calculated_signature(&self) -> u64 {
        let mut hash = 0xcbf2_9ce4_8422_2325u64;
        for byte in (self.len as u64).to_le_bytes() {
            hash = (hash ^ u64::from(byte)).wrapping_mul(0x100_0000_01b3);
        }
        for region in self.regions {
            for byte in region
                .start
                .to_le_bytes()
                .into_iter()
                .chain(region.end.to_le_bytes())
            {
                hash = (hash ^ u64::from(byte)).wrapping_mul(0x100_0000_01b3);
            }
        }
        hash
    }

    fn seal(&mut self) {
        self.signature = self.calculated_signature();
    }

    pub fn integrity_status(&self) -> Result<(), Error> {
        if self.len > MAX_FREE || self.signature != self.calculated_signature() {
            return Err(Error::CorruptSignature);
        }
        let mut prior_end = 0;
        for region in &self.regions[..self.len] {
            if region.start % PAGE_SIZE != 0
                || region.end % PAGE_SIZE != 0
                || region.start >= region.end
                || region.start < prior_end
            {
                return Err(Error::CorruptSignature);
            }
            prior_end = region.end;
        }
        Ok(())
    }

    pub fn from_ram(start: u64, size: u64) -> Result<Self, Error> {
        let end = start.checked_add(size).ok_or(Error::Invalid)?;
        let first = align_up(start)?;
        let last = align_down(end);
        if first >= last {
            return Err(Error::Invalid);
        }
        let mut regions = [Region::default(); MAX_FREE];
        regions[0] = Region {
            start: first,
            end: last,
        };
        let mut map = Self {
            regions,
            len: 1,
            signature: 0,
        };
        map.seal();
        Ok(map)
    }

    /// K512: UEFI boots admit only EfiConventionalMemory pages that also lie
    /// inside the DTB RAM extent. All other types and unreported gaps are
    /// withheld, including reclaimable BootServices pages, until a separate
    /// ownership policy deliberately releases them.
    pub fn from_uefi_conventional(
        ram_start: u64,
        ram_size: u64,
        map: &[u8],
        stride: usize,
    ) -> Result<Self, Error> {
        let ram_end = ram_start.checked_add(ram_size).ok_or(Error::Invalid)?;
        if stride < 40 || stride % 8 != 0 || map.is_empty() || map.len() % stride != 0 {
            return Err(Error::Invalid);
        }
        let mut regions = [Region::default(); MAX_FREE];
        let mut count = 0;
        for raw in map.chunks_exact(stride) {
            let descriptor = bootinfo::parse_memory_descriptor(raw).map_err(|_| Error::Invalid)?;
            if descriptor.kind != bootinfo::EFI_CONVENTIONAL_MEMORY {
                continue;
            }
            let lower = descriptor.start.max(ram_start);
            let upper = descriptor.end.min(ram_end);
            if lower >= upper {
                continue;
            }
            let start = align_up(lower)?;
            let end = align_down(upper);
            if start >= end {
                continue;
            }
            if count == MAX_FREE {
                return Err(Error::TooManyRegions);
            }
            regions[count] = Region { start, end };
            count += 1;
        }
        if count == 0 {
            return Err(Error::Invalid);
        }
        regions[..count].sort_unstable_by_key(|region| region.start);
        let mut merged = 0;
        for index in 0..count {
            let candidate = regions[index];
            if merged != 0 && candidate.start < regions[merged - 1].end {
                return Err(Error::Invalid);
            }
            if merged != 0 && candidate.start == regions[merged - 1].end {
                regions[merged - 1].end = candidate.end;
            } else {
                regions[merged] = candidate;
                merged += 1;
            }
        }
        regions[merged..].fill(Region::default());
        let mut free = Self {
            regions,
            len: merged,
            signature: 0,
        };
        free.seal();
        Ok(free)
    }

    pub fn reserve(&mut self, start: u64, size: u64) -> Result<(), Error> {
        self.integrity_status()?;
        if size == 0 {
            return Err(Error::Invalid);
        }
        let end = start.checked_add(size).ok_or(Error::Invalid)?;
        let cut_start = align_down(start);
        let cut_end = align_up(end)?;
        let mut next = [Region::default(); MAX_FREE];
        let mut count = 0;
        for region in self.regions() {
            if cut_end <= region.start || cut_start >= region.end {
                if count == MAX_FREE {
                    return Err(Error::TooManyRegions);
                }
                next[count] = *region;
                count += 1;
                continue;
            }
            if cut_start > region.start {
                if count == MAX_FREE {
                    return Err(Error::TooManyRegions);
                }
                next[count] = Region {
                    start: region.start,
                    end: cut_start,
                };
                count += 1;
            }
            if cut_end < region.end {
                if count == MAX_FREE {
                    return Err(Error::TooManyRegions);
                }
                next[count] = Region {
                    start: cut_end,
                    end: region.end,
                };
                count += 1;
            }
        }
        self.regions = next;
        self.len = count;
        self.seal();
        Ok(())
    }

    pub fn regions(&self) -> &[Region] {
        assert!(
            self.integrity_status().is_ok(),
            "corrupt free-map signature"
        );
        &self.regions[..self.len]
    }

    pub fn total_pages(&self) -> u64 {
        self.regions()
            .iter()
            .map(|region| (region.end - region.start) / PAGE_SIZE)
            .sum()
    }
}

impl FrameAllocator {
    pub fn new(map: FreeMap) -> Self {
        assert!(
            map.integrity_status().is_ok(),
            "corrupt initial free-map signature"
        );
        Self {
            allowed: map.clone(),
            free: map,
        }
    }

    pub fn remaining_pages(&self) -> u64 {
        self.free.total_pages()
    }

    /// Read-only, integrity-checked free-region audit. Equal page counts alone
    /// cannot prove that a failed transaction returned the same physical RAM.
    pub fn free_regions(&self) -> Result<&[Region], Error> {
        self.allowed.integrity_status()?;
        self.free.integrity_status()?;
        Ok(self.free.regions())
    }

    /// Allocate a particular page, subject to the same immutable authority as
    /// allocate(). A rejected request changes neither map nor page contents.
    /// This is also used by the UEFI acceptance image to probe both endpoints.
    pub fn allocate_at(&mut self, address: u64) -> Result<u64, FrameRequestError> {
        self.allowed
            .integrity_status()
            .map_err(FrameRequestError::Metadata)?;
        self.free
            .integrity_status()
            .map_err(FrameRequestError::Metadata)?;
        if address % PAGE_SIZE != 0 {
            return Err(FrameRequestError::InvalidAddress);
        }
        let end = address
            .checked_add(PAGE_SIZE)
            .ok_or(FrameRequestError::InvalidAddress)?;
        if !self
            .allowed
            .regions()
            .iter()
            .any(|r| r.start <= address && end <= r.end)
        {
            return Err(FrameRequestError::OutsideAuthority);
        }
        if !self
            .free
            .regions()
            .iter()
            .any(|r| r.start <= address && end <= r.end)
        {
            return Err(FrameRequestError::NotFree);
        }
        self.free
            .reserve(address, PAGE_SIZE)
            .map_err(FrameRequestError::Metadata)?;
        Ok(address)
    }

    pub fn allocate(&mut self) -> Option<u64> {
        if self.allowed.integrity_status().is_err() || self.free.integrity_status().is_err() {
            return None;
        }
        let region = self.free.regions[..self.free.len].first_mut()?;
        let address = region.start;
        region.start += PAGE_SIZE;
        if region.start == region.end {
            self.free.regions.copy_within(1..self.free.len, 0);
            self.free.len -= 1;
        }
        self.free.seal();
        Some(address)
    }

    pub fn release(&mut self, address: u64) -> Result<(), Error> {
        self.allowed.integrity_status()?;
        self.free.integrity_status()?;
        if address & (PAGE_SIZE - 1) != 0 {
            return Err(Error::Invalid);
        }
        let end = address.checked_add(PAGE_SIZE).ok_or(Error::Invalid)?;
        if !self
            .allowed
            .regions()
            .iter()
            .any(|region| region.start <= address && end <= region.end)
        {
            return Err(Error::Invalid);
        }
        let index = self
            .free
            .regions()
            .iter()
            .position(|region| region.start >= address)
            .unwrap_or(self.free.len);
        if index > 0 && self.free.regions[index - 1].end > address {
            return Err(Error::Invalid);
        }
        if index < self.free.len && self.free.regions[index].start < end {
            return Err(Error::Invalid);
        }
        let joins_left = index > 0 && self.free.regions[index - 1].end == address;
        let joins_right = index < self.free.len && self.free.regions[index].start == end;
        if joins_left && joins_right {
            self.free.regions[index - 1].end = self.free.regions[index].end;
            self.free
                .regions
                .copy_within(index + 1..self.free.len, index);
            self.free.len -= 1;
        } else if joins_left {
            self.free.regions[index - 1].end = end;
        } else if joins_right {
            self.free.regions[index].start = address;
        } else {
            if self.free.len == MAX_FREE {
                return Err(Error::TooManyRegions);
            }
            self.free
                .regions
                .copy_within(index..self.free.len, index + 1);
            self.free.regions[index] = Region {
                start: address,
                end,
            };
            self.free.len += 1;
        }
        self.free.seal();
        Ok(())
    }

    /// Validate an entire owner set against a staging map before returning
    /// any page. Duplicate, foreign or metadata-capacity failures leave the
    /// live allocator unchanged.
    pub fn release_many(&mut self, addresses: &[u64]) -> Result<(), Error> {
        self.allowed.integrity_status()?;
        self.free.integrity_status()?;
        let mut staged = Self {
            allowed: self.allowed.clone(),
            free: self.free.clone(),
        };
        for &address in addresses {
            staged.release(address)?;
        }
        self.free = staged.free;
        Ok(())
    }

    /// Check the entire return transaction before erasing every owned frame,
    /// then publish the freed set. An invalid/duplicate frame leaves both
    /// allocator state and contents unchanged.
    ///
    /// # Safety
    /// Every address must be an exclusively owned, writable, mapped physical
    /// frame. No CPU, device or page-table walker may still use these pages;
    /// the caller must have completed the required TLB/device quiescence.
    pub unsafe fn release_many_zeroed(&mut self, addresses: &[u64]) -> Result<(), Error> {
        self.allowed.integrity_status()?;
        self.free.integrity_status()?;
        let mut staged = Self {
            allowed: self.allowed.clone(),
            free: self.free.clone(),
        };
        for &address in addresses {
            staged.release(address)?;
        }
        for &address in addresses {
            // SAFETY: guaranteed by this function's exclusive ownership and
            // mapping precondition; the transaction was validated above.
            for word in 0..(PAGE_SIZE as usize / core::mem::size_of::<u64>()) {
                unsafe { core::ptr::write_volatile((address as *mut u64).add(word), 0) };
            }
        }
        core::sync::atomic::fence(core::sync::atomic::Ordering::SeqCst);
        self.free = staged.free;
        Ok(())
    }
}

#[cfg(test)]
mod tests {
    extern crate std;

    use super::*;
    use std::sync::{Arc, Barrier};
    use std::thread;
    use std::vec::Vec;

    #[test]
    fn k512_uefi_conventional_only_excludes_runtime_mmio_and_unreported_gaps() {
        fn descriptor(map: &mut [u8], index: usize, kind: u32, start: u64, pages: u64) {
            let row = &mut map[index * 48..(index + 1) * 48];
            row[0..4].copy_from_slice(&kind.to_le_bytes());
            row[8..16].copy_from_slice(&start.to_le_bytes());
            row[24..32].copy_from_slice(&pages.to_le_bytes());
        }
        let base = 0x4000_0000;
        let mut raw = [0u8; 5 * 48];
        descriptor(&mut raw, 0, 7, base + 0x9000, 3);
        descriptor(&mut raw, 1, 5, base + 0x8000, 1);
        descriptor(&mut raw, 2, 7, base + 0x4000, 4);
        descriptor(&mut raw, 3, 11, base + 0xc000, 1);
        descriptor(&mut raw, 4, 7, base + 0x20000, 1);
        let mut free = FreeMap::from_uefi_conventional(base, 0x10000, &raw, 48).unwrap();
        assert_eq!(
            free.regions(),
            &[
                Region {
                    start: base + 0x4000,
                    end: base + 0x8000
                },
                Region {
                    start: base + 0x9000,
                    end: base + 0xc000
                },
            ]
        );
        assert_eq!(free.total_pages(), 7);
        free.reserve(base + 0x5000, PAGE_SIZE).unwrap();
        let mut allocator = FrameAllocator::new(free);
        assert_eq!(allocator.allocate(), Some(base + 0x4000));
        assert_eq!(allocator.allocate(), Some(base + 0x6000));
        assert_eq!(allocator.release(base + 0x8000), Err(Error::Invalid));
        assert_eq!(allocator.release(base + 0xc000), Err(Error::Invalid));
        assert!(matches!(
            FreeMap::from_uefi_conventional(base, 0x10000, &raw, 47),
            Err(Error::Invalid)
        ));
    }

    #[test]
    fn k079_corrupt_free_map_signature_stops_all_frame_transitions() {
        let base = 0x4000_0000;
        let map = FreeMap::from_ram(base, 8 * PAGE_SIZE).unwrap();
        let mut allocator = FrameAllocator::new(map);
        let owned = allocator.allocate().unwrap();
        assert_eq!(owned, base);
        assert_eq!(allocator.free.integrity_status(), Ok(()));
        let original = allocator.free.regions[0];
        allocator.free.regions[0].start ^= PAGE_SIZE;
        let corrupt = allocator.free.regions[0];
        assert_eq!(
            allocator.free.integrity_status(),
            Err(Error::CorruptSignature)
        );
        assert_eq!(
            allocator.allocate(),
            None,
            "no frame may escape corrupt metadata"
        );
        assert_eq!(allocator.release(owned), Err(Error::CorruptSignature));
        assert_eq!(allocator.release_many(&[]), Err(Error::CorruptSignature));
        assert_eq!(
            allocator.free.regions[0], corrupt,
            "failed operations must not mutate the map"
        );
        allocator.free.regions[0] = original;
        assert_eq!(allocator.free.integrity_status(), Ok(()));
        allocator.free.signature ^= 1;
        assert_eq!(
            allocator.allocate(),
            None,
            "damaged signature itself must stop allocation"
        );
        assert_eq!(allocator.release(owned), Err(Error::CorruptSignature));
    }

    #[test]
    fn k079_reservation_and_allowed_map_corruption_fail_closed() {
        let base = 0x4000_0000;
        let mut map = FreeMap::from_ram(base, 8 * PAGE_SIZE).unwrap();
        map.regions[0].end ^= PAGE_SIZE;
        let corrupt = map.regions[0];
        assert_eq!(
            map.reserve(base + PAGE_SIZE, PAGE_SIZE),
            Err(Error::CorruptSignature)
        );
        assert_eq!(map.regions[0], corrupt);

        let mut allocator = FrameAllocator::new(FreeMap::from_ram(base, 8 * PAGE_SIZE).unwrap());
        let owned = allocator.allocate().unwrap();
        allocator.allowed.len = MAX_FREE + 1;
        assert_eq!(allocator.allocate(), None);
        assert_eq!(allocator.release(owned), Err(Error::CorruptSignature));
        assert_eq!(
            allocator.release_many(&[owned]),
            Err(Error::CorruptSignature)
        );
    }

    #[test]
    fn batch_release_is_atomic_on_duplicate_and_foreign_frames() {
        let base = 0x4000_0000;
        let map = FreeMap::from_ram(base, 4 * PAGE_SIZE).unwrap();
        let mut allocator = FrameAllocator::new(map);
        let a = allocator.allocate().unwrap();
        let b = allocator.allocate().unwrap();
        assert_eq!(allocator.remaining_pages(), 2);
        for invalid in [[a, a], [a, base + 4 * PAGE_SIZE], [a, base + 1]] {
            assert_eq!(allocator.release_many(&invalid), Err(Error::Invalid));
            assert_eq!(allocator.remaining_pages(), 2);
        }
        allocator.release_many(&[b, a]).unwrap();
        assert_eq!(allocator.remaining_pages(), 4);
        assert_eq!(allocator.allocate(), Some(a));
        assert_eq!(allocator.allocate(), Some(b));
    }

    #[test]
    fn excludes_kernel_and_dtb_pages() {
        let mut map = FreeMap::from_ram(0x4000_0000, 0x10000).unwrap();
        map.reserve(0x4000_1003, 0x1ffd).unwrap();
        map.reserve(0x4000_8000, 0x1000).unwrap();
        assert_eq!(map.total_pages(), 13);
        assert_eq!(
            map.regions(),
            &[
                Region {
                    start: 0x4000_0000,
                    end: 0x4000_1000
                },
                Region {
                    start: 0x4000_3000,
                    end: 0x4000_8000
                },
                Region {
                    start: 0x4000_9000,
                    end: 0x4001_0000
                },
            ]
        );
    }

    #[test]
    fn overlapping_reservations_do_not_reintroduce_pages() {
        let mut map = FreeMap::from_ram(0x4000_0000, 0x4000).unwrap();
        map.reserve(0x4000_1000, 0x2000).unwrap();
        map.reserve(0x4000_2000, 0x1000).unwrap();
        assert_eq!(map.total_pages(), 2);
    }

    #[test]
    fn ignores_outside_ram_and_clips_partial_reservations() {
        const BASE: u64 = 0x4000_0000;
        let mut map = FreeMap::from_ram(BASE, 4 * PAGE_SIZE).unwrap();
        let original = map.regions().to_vec();
        map.reserve(0x0900_0000, PAGE_SIZE).unwrap();
        map.reserve(BASE + 8 * PAGE_SIZE, PAGE_SIZE).unwrap();
        assert_eq!(map.regions(), original.as_slice());

        map.reserve(BASE - 0x800, 0x1800).unwrap();
        assert_eq!(
            map.regions(),
            &[Region {
                start: BASE + PAGE_SIZE,
                end: BASE + 4 * PAGE_SIZE,
            }]
        );
        map.reserve(BASE + 3 * PAGE_SIZE + 0x800, PAGE_SIZE)
            .unwrap();
        assert_eq!(
            map.regions(),
            &[Region {
                start: BASE + PAGE_SIZE,
                end: BASE + 3 * PAGE_SIZE,
            }]
        );
    }

    #[test]
    fn adjacent_and_nested_reservations_do_not_fragment_free_map() {
        const BASE: u64 = 0x4000_0000;
        let mut adjacent = FreeMap::from_ram(BASE, 8 * PAGE_SIZE).unwrap();
        adjacent.reserve(BASE + 2 * PAGE_SIZE, PAGE_SIZE).unwrap();
        adjacent
            .reserve(BASE + 3 * PAGE_SIZE, 2 * PAGE_SIZE)
            .unwrap();
        assert_eq!(
            adjacent.regions(),
            &[
                Region {
                    start: BASE,
                    end: BASE + 2 * PAGE_SIZE,
                },
                Region {
                    start: BASE + 5 * PAGE_SIZE,
                    end: BASE + 8 * PAGE_SIZE,
                },
            ]
        );

        let mut nested = FreeMap::from_ram(BASE, 8 * PAGE_SIZE).unwrap();
        nested.reserve(BASE + PAGE_SIZE, 5 * PAGE_SIZE).unwrap();
        let before = nested.regions().to_vec();
        nested.reserve(BASE + 2 * PAGE_SIZE, PAGE_SIZE).unwrap();
        assert_eq!(nested.regions(), before.as_slice());
        assert_eq!(nested.total_pages(), 3);
    }

    #[test]
    fn uart_mmio_is_never_allocated_as_ram() {
        const BASE: u64 = 0x4000_0000;
        const UART: u64 = 0x0900_0000;
        let mut map = FreeMap::from_ram(BASE, 3 * PAGE_SIZE).unwrap();
        map.reserve(UART, PAGE_SIZE).unwrap();
        let mut allocator = FrameAllocator::new(map);
        assert_eq!(allocator.release(UART), Err(Error::Invalid));
        for offset in 0..3 {
            assert_eq!(allocator.allocate(), Some(BASE + offset * PAGE_SIZE));
        }
        assert_eq!(allocator.allocate(), None);
    }

    #[test]
    fn reservation_order_preserves_the_same_free_ranges() {
        const BASE: u64 = 0x4000_0000;
        let cuts = [
            (BASE + PAGE_SIZE + 0x800, PAGE_SIZE),
            (BASE + 3 * PAGE_SIZE, 2 * PAGE_SIZE),
            (BASE + 2 * PAGE_SIZE, 2 * PAGE_SIZE),
        ];
        let mut forward = FreeMap::from_ram(BASE, 8 * PAGE_SIZE).unwrap();
        let mut reverse = forward.clone();
        for (start, size) in cuts {
            forward.reserve(start, size).unwrap();
        }
        for (start, size) in cuts.into_iter().rev() {
            reverse.reserve(start, size).unwrap();
        }
        assert_eq!(forward.regions(), reverse.regions());
        assert_eq!(forward.total_pages(), reverse.total_pages());
    }

    #[test]
    fn reserve_map_and_static_reservation_can_overlap() {
        let mut map = FreeMap::from_ram(0x4000_0000, 8 * PAGE_SIZE).unwrap();
        // The FDT reserve map and /reserved-memory may describe the same pages.
        map.reserve(0x4000_0000, 3 * PAGE_SIZE).unwrap();
        map.reserve(0x4000_1000, 3 * PAGE_SIZE).unwrap();
        assert_eq!(map.total_pages(), 4);
        let mut allocator = FrameAllocator::new(map);
        assert_eq!(allocator.allocate(), Some(0x4000_4000));
        assert_eq!(allocator.release(0x4000_1000), Err(Error::Invalid));
    }

    #[test]
    fn aligns_ram_inward_and_rejects_overflow() {
        let map = FreeMap::from_ram(0x4000_0001, 0x2fff).unwrap();
        assert_eq!(
            map.regions(),
            &[Region {
                start: 0x4000_1000,
                end: 0x4000_3000
            }]
        );
        assert!(matches!(
            FreeMap::from_ram(u64::MAX, 2),
            Err(Error::Invalid)
        ));
    }

    #[test]
    fn allocates_only_unreserved_pages_and_reports_exhaustion() {
        let mut map = FreeMap::from_ram(0x4000_0000, 0x5000).unwrap();
        map.reserve(0x4000_1000, 0x1000).unwrap();
        map.reserve(0x4000_3000, 0x1000).unwrap();
        let mut allocator = FrameAllocator::new(map);
        assert_eq!(allocator.remaining_pages(), 3);
        assert_eq!(allocator.allocate(), Some(0x4000_0000));
        assert_eq!(allocator.allocate(), Some(0x4000_2000));
        assert_eq!(allocator.allocate(), Some(0x4000_4000));
        assert_eq!(allocator.allocate(), None);
        assert_eq!(allocator.remaining_pages(), 0);
    }

    #[test]
    fn k466_locked_allocator_gives_two_threads_unique_frames_and_restores_count() {
        const EACH: usize = 64;
        let map = FreeMap::from_ram(0x4000_0000, (EACH * 2 * PAGE_SIZE as usize) as u64).unwrap();
        let shared = Arc::new(LockedFrameAllocator::new());
        assert!(shared.with(|_| ()).is_none());
        // SAFETY: no worker exists before the only initialization.
        unsafe { shared.initialize_single_cpu(FrameAllocator::new(map)) };
        let barrier = Arc::new(Barrier::new(3));
        let workers: Vec<_> = (0..2)
            .map(|worker_index| {
                let shared = Arc::clone(&shared);
                let barrier = Arc::clone(&barrier);
                thread::spawn(move || {
                    // Worker 0 enters the first allocation while holding the
                    // real allocator lock. Worker 1 crosses the barrier before
                    // trying it, so contention is observed rather than guessed
                    // from a short delay and host scheduler timing.
                    if worker_index == 1 {
                        barrier.wait();
                    }
                    let mut frames = [0u64; EACH];
                    for (index, slot) in frames.iter_mut().enumerate() {
                        *slot = shared
                            .with(|allocator| {
                                if worker_index == 0 && index == 0 {
                                    barrier.wait();
                                    let deadline = std::time::Instant::now()
                                        + std::time::Duration::from_secs(10);
                                    while shared.contention_count() == 0
                                        && std::time::Instant::now() < deadline
                                    {
                                        thread::yield_now();
                                    }
                                    assert!(
                                        shared.contention_count() > 0,
                                        "second worker did not attempt the held lock"
                                    );
                                }
                                for _ in 0..2000 {
                                    core::hint::spin_loop();
                                }
                                allocator.allocate().unwrap()
                            })
                            .unwrap();
                    }
                    frames
                })
            })
            .collect();
        barrier.wait();
        let first = workers
            .into_iter()
            .map(|worker| worker.join().unwrap())
            .collect::<Vec<_>>();
        let mut addresses = first.into_iter().flatten().collect::<Vec<_>>();
        addresses.sort_unstable();
        addresses.dedup();
        assert_eq!(addresses.len(), EACH * 2);
        assert_eq!(
            shared.with(|allocator| allocator.remaining_pages()),
            Some(0)
        );
        assert!(
            shared.contention_count() > 0,
            "workers did not contend for the lock"
        );
        shared
            .with(|allocator| allocator.release_many(&addresses).unwrap())
            .unwrap();
        assert_eq!(
            shared.with(|allocator| allocator.remaining_pages()),
            Some((EACH * 2) as u64)
        );
    }

    #[test]
    fn release_coalesces_regions_and_rejects_protected_or_double_free() {
        let mut map = FreeMap::from_ram(0x4000_0000, 0x5000).unwrap();
        map.reserve(0x4000_4000, 0x1000).unwrap();
        let mut allocator = FrameAllocator::new(map);
        for _ in 0..4 {
            assert!(allocator.allocate().is_some());
        }
        assert_eq!(allocator.release(0x4000_4000), Err(Error::Invalid));
        assert_eq!(allocator.release(0x4000_0001), Err(Error::Invalid));
        allocator.release(0x4000_0000).unwrap();
        allocator.release(0x4000_2000).unwrap();
        allocator.release(0x4000_1000).unwrap();
        allocator.release(0x4000_3000).unwrap();
        assert_eq!(allocator.release(0x4000_2000), Err(Error::Invalid));
        assert_eq!(allocator.remaining_pages(), 4);
        for offset in 0..4 {
            assert_eq!(allocator.allocate(), Some(0x4000_0000 + offset * PAGE_SIZE));
        }
    }

    #[test]
    fn k455_duplicate_release_preserves_every_coalescing_state() {
        const BASE: u64 = 0x4000_0000;
        const PAGES: usize = 8;
        let map = FreeMap::from_ram(BASE, PAGES as u64 * PAGE_SIZE).unwrap();
        let mut allocator = FrameAllocator::new(map);
        for offset in 0..PAGES {
            assert_eq!(allocator.allocate(), Some(BASE + offset as u64 * PAGE_SIZE));
        }
        assert_eq!(allocator.remaining_pages(), 0);
        // The ordering exercises isolated, left/right join and bridge cases.
        for offset in [3usize, 2, 4, 0, 7, 1, 5, 6] {
            let address = BASE + offset as u64 * PAGE_SIZE;
            allocator.release(address).unwrap();
            let before = allocator.free.clone();
            assert_eq!(allocator.release(address), Err(Error::Invalid));
            assert_eq!(allocator.free.regions(), before.regions());
            assert_eq!(allocator.remaining_pages(), before.total_pages());
        }
        assert_eq!(allocator.remaining_pages(), PAGES as u64);
        for offset in 0..PAGES {
            assert_eq!(allocator.allocate(), Some(BASE + offset as u64 * PAGE_SIZE));
        }
        assert_eq!(allocator.allocate(), None);
    }

    #[test]
    fn lifo_and_fifo_release_orders_restore_identical_ownership() {
        const BASE: u64 = 0x4000_0000;
        for reverse in [false, true] {
            let map = FreeMap::from_ram(BASE, 8 * PAGE_SIZE).unwrap();
            let mut allocator = FrameAllocator::new(map);
            let mut held = [0u64; 8];
            for frame in &mut held {
                *frame = allocator.allocate().unwrap();
            }
            assert_eq!(allocator.allocate(), None);
            if reverse {
                for address in held.iter().rev() {
                    allocator.release(*address).unwrap();
                }
            } else {
                for address in held {
                    allocator.release(address).unwrap();
                }
            }
            assert_eq!(allocator.remaining_pages(), 8);
            for offset in 0..8 {
                assert_eq!(allocator.allocate(), Some(BASE + offset * PAGE_SIZE));
            }
        }
    }

    #[test]
    fn exhaustion_recovers_after_one_frame_is_returned() {
        const BASE: u64 = 0x4000_0000;
        let map = FreeMap::from_ram(BASE, 2 * PAGE_SIZE).unwrap();
        let mut allocator = FrameAllocator::new(map);
        assert_eq!(allocator.allocate(), Some(BASE));
        assert_eq!(allocator.allocate(), Some(BASE + PAGE_SIZE));
        assert_eq!(allocator.allocate(), None);
        allocator.release(BASE).unwrap();
        assert_eq!(allocator.remaining_pages(), 1);
        assert_eq!(allocator.allocate(), Some(BASE));
        assert_eq!(allocator.allocate(), None);
    }

    #[test]
    fn low_and_high_ram_edges_stay_inside_allowed_range() {
        const BASE: u64 = 0x4000_0000;
        let mut map = FreeMap::from_ram(BASE, 6 * PAGE_SIZE).unwrap();
        // Model the kernel and DTB occupying the first two RAM pages.
        map.reserve(BASE, 2 * PAGE_SIZE).unwrap();
        let mut allocator = FrameAllocator::new(map);
        assert_eq!(allocator.remaining_pages(), 4);
        assert_eq!(allocator.allocate(), Some(BASE + 2 * PAGE_SIZE));
        assert_eq!(allocator.allocate(), Some(BASE + 3 * PAGE_SIZE));
        assert_eq!(allocator.allocate(), Some(BASE + 4 * PAGE_SIZE));
        assert_eq!(allocator.allocate(), Some(BASE + 5 * PAGE_SIZE));
        assert_eq!(allocator.allocate(), None);
        assert_eq!(allocator.release(BASE), Err(Error::Invalid));
        assert_eq!(allocator.release(BASE + 6 * PAGE_SIZE), Err(Error::Invalid));
    }

    #[test]
    fn fragmentation_limit_does_not_lose_a_frame() {
        let map = FreeMap::from_ram(0x4000_0000, 140 * PAGE_SIZE).unwrap();
        let mut allocator = FrameAllocator::new(map);
        for _ in 0..140 {
            assert!(allocator.allocate().is_some());
        }
        for index in 0..MAX_FREE {
            allocator
                .release(0x4000_0000 + index as u64 * 2 * PAGE_SIZE)
                .unwrap();
        }
        let next = 0x4000_0000 + MAX_FREE as u64 * 2 * PAGE_SIZE;
        assert_eq!(allocator.release(next), Err(Error::TooManyRegions));
        assert_eq!(allocator.remaining_pages(), MAX_FREE as u64);
        allocator.release(0x4000_0000 + PAGE_SIZE).unwrap();
        allocator.release(next).unwrap();
        assert_eq!(allocator.remaining_pages(), MAX_FREE as u64 + 2);
    }

    #[test]
    fn repeated_multi_frame_cycles_preserve_all_pages() {
        const PAGES: usize = 48;
        let mut map = FreeMap::from_ram(0x4000_0000, (PAGES as u64 + 3) * PAGE_SIZE).unwrap();
        map.reserve(0x4000_1000, 2 * PAGE_SIZE).unwrap();
        map.reserve(0x4000_2000, 2 * PAGE_SIZE).unwrap();
        assert_eq!(map.total_pages(), PAGES as u64);
        let mut allocator = FrameAllocator::new(map);
        for _ in 0..8 {
            let mut frames = [0; PAGES];
            for frame in &mut frames {
                *frame = allocator.allocate().unwrap();
                assert!(*frame < 0x4000_1000 || *frame >= 0x4000_4000);
            }
            assert_eq!(allocator.allocate(), None);
            for frame in frames.iter().step_by(3) {
                allocator.release(*frame).unwrap();
            }
            assert_eq!(allocator.remaining_pages(), 16);
            for frame in frames.iter().step_by(3) {
                assert_eq!(allocator.allocate(), Some(*frame));
            }
            for frame in frames.iter().rev() {
                allocator.release(*frame).unwrap();
            }
            assert_eq!(allocator.remaining_pages(), PAGES as u64);
        }
    }

    #[test]
    fn deterministic_fragmentation_preserves_page_ownership() {
        const PAGES: usize = 96;
        const BASE: u64 = 0x4000_0000;
        let mut map = FreeMap::from_ram(BASE, PAGES as u64 * PAGE_SIZE).unwrap();
        map.reserve(BASE + 5 * PAGE_SIZE, 2 * PAGE_SIZE).unwrap();
        map.reserve(BASE + 20 * PAGE_SIZE, 4 * PAGE_SIZE).unwrap();
        map.reserve(BASE + 50 * PAGE_SIZE, PAGE_SIZE).unwrap();
        let allowed = map.total_pages();
        assert_eq!(allowed, 89);
        let mut allocator = FrameAllocator::new(map);
        let mut held = [false; PAGES];
        let mut held_count = 0u64;
        let mut seed = 0x5455_524b_4f53u64;

        for _ in 0..4096 {
            seed = seed.wrapping_mul(6364136223846793005).wrapping_add(1);
            if (seed & 3 == 0 && held_count > 0) || allocator.remaining_pages() == 0 {
                let mut index = seed as usize % PAGES;
                while !held[index] {
                    index = (index + 1) % PAGES;
                }
                allocator.release(BASE + index as u64 * PAGE_SIZE).unwrap();
                held[index] = false;
                held_count -= 1;
            } else {
                let address = allocator.allocate().unwrap();
                let index = ((address - BASE) / PAGE_SIZE) as usize;
                assert!(index < PAGES && !held[index]);
                assert!(!((5..7).contains(&index) || (20..24).contains(&index) || index == 50));
                held[index] = true;
                held_count += 1;
            }
            assert_eq!(allocator.remaining_pages() + held_count, allowed);
        }
        for (index, occupied) in held.iter().enumerate() {
            if *occupied {
                allocator.release(BASE + index as u64 * PAGE_SIZE).unwrap();
            }
        }
        assert_eq!(allocator.remaining_pages(), allowed);
    }

    #[test]
    fn reserve_capacity_error_leaves_the_free_map_unchanged() {
        const BASE: u64 = 0x4000_0000;
        let mut map = FreeMap::from_ram(BASE, 140 * PAGE_SIZE).unwrap();
        for index in 0..MAX_FREE - 1 {
            map.reserve(BASE + (2 * index as u64 + 1) * PAGE_SIZE, PAGE_SIZE)
                .unwrap();
        }
        assert_eq!(map.regions().len(), MAX_FREE);
        let before = map.clone();
        let page_count = map.total_pages();
        assert_eq!(
            map.reserve(BASE + (2 * MAX_FREE as u64 - 1) * PAGE_SIZE, PAGE_SIZE),
            Err(Error::TooManyRegions)
        );
        assert_eq!(map.regions(), before.regions());
        assert_eq!(map.total_pages(), page_count);
    }
}