//! Minimal EL1, 4 KiB-granule identity tables for the default Image and MMU test images.
//! The production Image also calls this module. Tables remain allocated until
//! the guest stops; they must never be returned while translation is on.

use crate::dtb::Reservation;
use crate::memory::{FrameAllocator, PAGE_SIZE};

const RAM_BASE: u64 = 0x4000_0000;
const GIB: u64 = 1 << 30;
const MIB2: u64 = 1 << 21;
const ENTRIES: usize = 512;
pub const HEAP_WINDOW_START: u64 = RAM_BASE + 0x10_0000;
pub const HEAP_WINDOW_PAGES: usize = 16;
pub const HEAP_INITIAL_PAGES: usize = 4;
const TABLE_COUNT: usize = 5;
// A bounded early-boot owner list keeps table setup allocation-free. A DTB
// requiring more split blocks fails before TTBR0 is written.
const MAX_EXTRA_L3: usize = 16;
const MAX_TABLE_COUNT: usize = TABLE_COUNT + MAX_EXTRA_L3 + 1; // optional GICR probe table

const VALID_TABLE_OR_PAGE: u64 = 0b11;
const VALID_BLOCK: u64 = 0b01;
const ATTR_NORMAL: u64 = 0;
const ATTR_DEVICE: u64 = 1 << 2;
const AP_READ_ONLY: u64 = 0b10 << 6;
const AP_EL0_ACCESS: u64 = 1 << 6;
// User translations must be ASID-tagged, unlike shared kernel identity pages.
const NON_GLOBAL: u64 = 1 << 11;
const SHARE_INNER: u64 = 0b11 << 8;
const ACCESS_FLAG: u64 = 1 << 10;
const PXN: u64 = 1 << 53;
const UXN: u64 = 1 << 54;

pub const USER_CODE_VA: u64 = 0x8000_0000;
pub const USER_DATA_VA: u64 = USER_CODE_VA + PAGE_SIZE;
pub const USER_GUARD_VA: u64 = USER_DATA_VA + PAGE_SIZE;
pub const USER_STACK_VA: u64 = USER_GUARD_VA + PAGE_SIZE;
pub const USER_STACK_TOP: u64 = USER_STACK_VA + PAGE_SIZE;
const USER_OWNED_FRAMES: usize = 6; // L1, L2, L3, code, data, stack.

pub fn user_window_disjoint_from_kernel_ram(ram_base: u64, ram_size: u64) -> bool {
    ram_base == RAM_BASE
        && ram_size >= MIB2
        && ram_size <= GIB
        && ram_base
            .checked_add(ram_size)
            .is_some_and(|end| end <= USER_CODE_VA)
        && USER_STACK_TOP <= (1 << 39)
}

/// One private TTBR0 root. Kernel L1 entries are shared but EL0-inaccessible;
/// index two covers a distinct user VA window backed by six owned frames.
/// Deliberately not Clone: duplicating this owner would allow both tasks to
/// return the same table/data frames. A future fork requires a separate COW
/// or deep-copy contract; build_user_space currently creates a fresh owner.
#[derive(Debug)]
pub struct UserSpace {
    pub root: u64,
    frames: [u64; USER_OWNED_FRAMES],
}

impl UserSpace {
    pub fn code_frame(&self) -> u64 {
        self.frames[3]
    }
    pub fn data_frame(&self) -> u64 {
        self.frames[4]
    }
    pub fn stack_frame(&self) -> u64 {
        self.frames[5]
    }
    pub fn descriptor(&self, index: usize) -> Option<u64> {
        if index >= 4 {
            return None;
        }
        Some(unsafe { core::ptr::read_volatile((self.frames[2] as *const u64).add(index)) })
    }

    pub fn contract_valid(&self, kernel_root: u64) -> bool {
        self.root != kernel_root
            && self.root % PAGE_SIZE == 0
            && self.descriptor(0)
                == Some(
                    (ram_page(self.frames[3], true, true) | AP_EL0_ACCESS | NON_GLOBAL | PXN)
                        & !UXN,
                )
            && self.descriptor(1)
                == Some(ram_page(self.frames[4], false, false) | AP_EL0_ACCESS | NON_GLOBAL)
            && self.descriptor(2) == Some(0)
            && self.descriptor(3)
                == Some(ram_page(self.frames[5], false, false) | AP_EL0_ACCESS | NON_GLOBAL)
            && unsafe { core::ptr::read_volatile((self.root as *const u64).add(2)) }
                == table(self.frames[1])
    }

    /// # Safety
    /// The caller has switched TTBR0 away from this root, invalidated every
    /// translation for its old ASID on all participating CPUs, and ensures no
    /// concurrent walker or owner can still use these six frames.
    pub unsafe fn release_after_tlbi(
        self,
        allocator: &mut FrameAllocator,
        kernel_root: u64,
    ) -> Result<(), (Error, Self)> {
        if !self.contract_valid(kernel_root) {
            return Err((Error::UnsupportedLayout, self));
        }
        unsafe { allocator.release_many_zeroed(&self.frames) }
            .map_err(|_| (Error::UnsupportedLayout, self))
    }
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Error {
    UnsupportedLayout,
    OutOfFrames,
}

#[derive(Clone, Copy)]
pub struct Layout {
    pub ram_base: u64,
    pub ram_size: u64,
    pub uart_base: u64,
    pub image_start: u64,
    pub text_start: u64,
    pub text_end: u64,
    pub rodata_end: u64,
    pub image_end: u64,
    pub irq_guard_page: Option<u64>,
    pub heap_start: Option<u64>,
}

impl Layout {
    fn validate(self) -> Result<(), Error> {
        if self.ram_base != RAM_BASE
            || self.ram_size < MIB2
            || self.ram_size > GIB
            || self.ram_size % MIB2 != 0
            || self.uart_base >= GIB
            || self.uart_base % PAGE_SIZE != 0
            || self.image_start < RAM_BASE
            || self.image_start % PAGE_SIZE != 0
            || self.text_start % PAGE_SIZE != 0
            || self.text_end % PAGE_SIZE != 0
            || self.rodata_end % PAGE_SIZE != 0
            || !(self.image_start < self.text_start
                && self.text_start < self.text_end
                && self.text_end <= self.rodata_end
                && self.rodata_end <= self.image_end
                && self.image_end <= RAM_BASE + MIB2)
            || ((self.image_end + PAGE_SIZE - 1) & !(PAGE_SIZE - 1)) >= RAM_BASE + MIB2
            || self.irq_guard_page.is_some_and(|guard| {
                guard % PAGE_SIZE != 0
                    || guard < self.rodata_end
                    || guard
                        .checked_add(PAGE_SIZE)
                        .is_none_or(|end| end > self.image_end)
            })
            || self.heap_start.is_some_and(|start| {
                let image_guard_end = (self.image_end + PAGE_SIZE - 1) & !(PAGE_SIZE - 1);
                start != HEAP_WINDOW_START
                    || start < image_guard_end + PAGE_SIZE
                    || start
                        .checked_add(HEAP_WINDOW_PAGES as u64 * PAGE_SIZE)
                        .is_none_or(|end| end > RAM_BASE + MIB2)
            })
        {
            return Err(Error::UnsupportedLayout);
        }
        Ok(())
    }

    fn validate_no_map(self, reservations: &[Reservation]) -> Result<(), Error> {
        let image_page_end = self
            .image_end
            .checked_add(PAGE_SIZE - 1)
            .ok_or(Error::UnsupportedLayout)?
            & !(PAGE_SIZE - 1);
        for region in reservations.iter().filter(|region| region.no_map) {
            let end = region
                .start
                .checked_add(region.size)
                .ok_or(Error::UnsupportedLayout)?;
            if region.size == 0 {
                return Err(Error::UnsupportedLayout);
            }
            if overlaps(
                region.start,
                end,
                self.uart_base,
                self.uart_base + PAGE_SIZE,
            ) || overlaps(region.start, end, self.image_start, image_page_end)
                || self.heap_start.is_some_and(|heap| {
                    overlaps(
                        region.start,
                        end,
                        heap,
                        heap + HEAP_WINDOW_PAGES as u64 * PAGE_SIZE,
                    )
                })
            {
                return Err(Error::UnsupportedLayout);
            }
        }
        Ok(())
    }
}

fn split_blocks(
    layout: Layout,
    reservations: &[Reservation],
) -> Result<([bool; ENTRIES], usize), Error> {
    layout.validate_no_map(reservations)?;
    let mut split = [false; ENTRIES];
    let mut count = 0;
    for index in 1..(layout.ram_size / MIB2) as usize {
        let block_start = RAM_BASE + index as u64 * MIB2;
        let block_end = block_start + MIB2;
        if reservations
            .iter()
            .filter(|region| region.no_map)
            .any(|region| {
                // validate_no_map checked these additions before planning begins.
                overlaps(
                    region.start,
                    region.start + region.size,
                    block_start,
                    block_end,
                )
            })
        {
            if count == MAX_EXTRA_L3 {
                return Err(Error::UnsupportedLayout);
            }
            split[index] = true;
            count += 1;
        }
    }
    Ok((split, count))
}

fn overlaps(first_start: u64, first_end: u64, second_start: u64, second_end: u64) -> bool {
    first_start < second_end && second_start < first_end
}

fn ram_page_descriptor(layout: Layout, address: u64, reservations: &[Reservation]) -> u64 {
    let guard_start = (layout.image_end + PAGE_SIZE - 1) & !(PAGE_SIZE - 1);
    if address == guard_start
        || layout.irq_guard_page == Some(address)
        || layout.heap_start.is_some_and(|start| {
            start <= address && address < start + HEAP_WINDOW_PAGES as u64 * PAGE_SIZE
        })
    {
        return 0;
    }
    if reservations.iter().any(|region| {
        region.no_map
            && overlaps(
                address,
                address + PAGE_SIZE,
                region.start,
                region.start + region.size,
            )
    }) {
        return 0;
    }
    let executable = layout.text_start <= address && address < layout.text_end;
    let read_only = layout.image_start <= address && address < layout.rodata_end;
    ram_page(address, executable, read_only)
}

pub struct Tables {
    pub root: u64,
    // Keep the addresses visible for diagnostics; no Drop is intentional.
    frames: [u64; MAX_TABLE_COUNT],
    count: usize,
    block_count: usize,
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum TableFrameRole {
    Root,
    DeviceL2,
    UartL3,
    RamL2,
    FirstRamL3,
    AdditionalTranslation,
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct TaggedTableFrame {
    pub address: u64,
    pub role: TableFrameRole,
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct WxAudit {
    pub tables: usize,
    pub leaves: usize,
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum WxAuditError {
    UnknownTable(u64),
    InvalidDescriptor(u64),
    WritableExecutable(u64),
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum DeviceAuditError {
    InvalidWindow,
    UnknownTable(u64),
    InvalidDescriptor(u64),
    UnexpectedDevice(u64),
    El0Accessible(u64),
    ExecutableDevice(u64),
    NonIdentityDevice(u64),
    MissingDevicePages,
}

/// Physical frames backing the first heap pages remain owned until all heap
/// objects are gone, then each translation is invalidated before frame return.
pub struct HeapPages {
    pub frames: [u64; HEAP_INITIAL_PAGES],
}

impl HeapPages {
    pub fn count(&self) -> usize {
        self.frames.len()
    }
}

impl Tables {
    /// Inspect every owned leaf reachable from one live user root. The
    /// expected DTB-derived windows must be the *complete* set of Device
    /// mappings for this image; unmapped devices remain translation faults.
    /// Callers must exclude concurrent page-table writers during the scan.
    pub fn audit_device_el0(
        &self,
        user: &UserSpace,
        windows: &[(u64, u64)],
    ) -> Result<usize, DeviceAuditError> {
        let mut expected_pages = 0usize;
        for (index, &(base, size)) in windows.iter().enumerate() {
            let end = base
                .checked_add(size)
                .ok_or(DeviceAuditError::InvalidWindow)?;
            if base == 0 || base % PAGE_SIZE != 0 || size == 0 || size % PAGE_SIZE != 0 || end > GIB
            {
                return Err(DeviceAuditError::InvalidWindow);
            }
            for &(prior, length) in &windows[..index] {
                if overlaps(base, end, prior, prior + length) {
                    return Err(DeviceAuditError::InvalidWindow);
                }
            }
            expected_pages += (size / PAGE_SIZE) as usize;
        }
        let mut found = 0usize;
        self.audit_device_table(user.root, 1, 0, user, windows, &mut found)?;
        if found != expected_pages {
            return Err(DeviceAuditError::MissingDevicePages);
        }
        Ok(found)
    }

    fn audit_device_table(
        &self,
        address: u64,
        level: u8,
        prefix: u64,
        user: &UserSpace,
        windows: &[(u64, u64)],
        found: &mut usize,
    ) -> Result<(), DeviceAuditError> {
        let owned =
            self.frames[..self.count].contains(&address) || user.frames[..3].contains(&address);
        if !owned || address == 0 || address % PAGE_SIZE != 0 {
            return Err(DeviceAuditError::UnknownTable(address));
        }
        let shift = match level {
            1 => 30,
            2 => 21,
            3 => 12,
            _ => unreachable!(),
        };
        for index in 0..ENTRIES {
            // SAFETY: the table is retained in Tables or UserSpace, aligned,
            // and the entry index stays within its 4 KiB physical frame.
            let descriptor =
                unsafe { core::ptr::read_volatile((address as *const u64).add(index)) };
            let va = prefix | ((index as u64) << shift);
            match descriptor & 3 {
                0 => continue,
                3 if level < 3 => self.audit_device_table(
                    descriptor & 0x0000_ffff_ffff_f000,
                    level + 1,
                    va,
                    user,
                    windows,
                    found,
                )?,
                3 if level == 3 => {
                    if va < RAM_BASE && descriptor & AP_EL0_ACCESS != 0 {
                        return Err(DeviceAuditError::El0Accessible(va));
                    }
                    if descriptor & (7 << 2) == ATTR_DEVICE {
                        if !windows
                            .iter()
                            .any(|&(base, size)| base <= va && va < base + size)
                        {
                            return Err(DeviceAuditError::UnexpectedDevice(va));
                        }
                        if descriptor & AP_EL0_ACCESS != 0 {
                            return Err(DeviceAuditError::El0Accessible(va));
                        }
                        if descriptor & (PXN | UXN) != PXN | UXN {
                            return Err(DeviceAuditError::ExecutableDevice(va));
                        }
                        if descriptor & 0x0000_ffff_ffff_f000 != va {
                            return Err(DeviceAuditError::NonIdentityDevice(va));
                        }
                        *found += 1;
                    }
                }
                1 if level < 3 => {
                    if va < RAM_BASE && descriptor & AP_EL0_ACCESS != 0 {
                        return Err(DeviceAuditError::El0Accessible(va));
                    }
                    if descriptor & (7 << 2) == ATTR_DEVICE {
                        return Err(DeviceAuditError::UnexpectedDevice(va));
                    }
                }
                _ => return Err(DeviceAuditError::InvalidDescriptor(va)),
            }
        }
        Ok(())
    }

    /// Walk one owned TTBR0 tree, including the shared kernel branches of a
    /// private user root. A table pointer outside the known owner set fails
    /// closed before it is dereferenced. This is a point-in-time descriptor
    /// audit; callers must exclude concurrent page-table writers.
    pub fn audit_wx(&self, user: Option<&UserSpace>) -> Result<WxAudit, WxAuditError> {
        let mut audit = WxAudit {
            tables: 0,
            leaves: 0,
        };
        self.audit_wx_table(
            user.map_or(self.root, |space| space.root),
            1,
            0,
            user,
            &mut audit,
        )?;
        Ok(audit)
    }

    fn audit_wx_table(
        &self,
        address: u64,
        level: u8,
        prefix: u64,
        user: Option<&UserSpace>,
        audit: &mut WxAudit,
    ) -> Result<(), WxAuditError> {
        let owned = self.frames[..self.count].contains(&address)
            || user.is_some_and(|space| space.frames[..3].contains(&address));
        if !owned || address == 0 || address % PAGE_SIZE != 0 {
            return Err(WxAuditError::UnknownTable(address));
        }
        audit.tables += 1;
        let shift = match level {
            1 => 30,
            2 => 21,
            3 => 12,
            _ => unreachable!(),
        };
        for index in 0..ENTRIES {
            // SAFETY: the pointer is one aligned frame retained by Tables or
            // UserSpace, and index stays within its 4 KiB table page.
            let descriptor =
                unsafe { core::ptr::read_volatile((address as *const u64).add(index)) };
            let va = prefix | ((index as u64) << shift);
            match descriptor & 3 {
                0 => continue,
                3 if level < 3 => self.audit_wx_table(
                    descriptor & 0x0000_ffff_ffff_f000,
                    level + 1,
                    va,
                    user,
                    audit,
                )?,
                3 if level == 3 => {
                    audit.leaves += 1;
                    if descriptor & AP_READ_ONLY == 0
                        && (descriptor & PXN == 0
                            || (descriptor & AP_EL0_ACCESS != 0 && descriptor & UXN == 0))
                    {
                        return Err(WxAuditError::WritableExecutable(va));
                    }
                }
                1 if level < 3 => {
                    audit.leaves += 1;
                    if descriptor & AP_READ_ONLY == 0
                        && (descriptor & PXN == 0
                            || (descriptor & AP_EL0_ACCESS != 0 && descriptor & UXN == 0))
                    {
                        return Err(WxAuditError::WritableExecutable(va));
                    }
                }
                _ => return Err(WxAuditError::InvalidDescriptor(va)),
            }
        }
        Ok(())
    }

    /// Allocate a separate user root and a four-page VA region above all
    /// supported QEMU RAM. Nothing is published until all six pages are owned.
    ///
    /// # Safety
    /// This CPU exclusively owns the current root and allocator; allocated
    /// frames are identity-mapped writable RAM and remain owned while the new
    /// TTBR0 root is active.
    pub unsafe fn build_user_space(
        &self,
        allocator: &mut FrameAllocator,
        ram_base: u64,
        ram_size: u64,
    ) -> Result<UserSpace, Error> {
        if !user_window_disjoint_from_kernel_ram(ram_base, ram_size)
            || self.root == 0
            || unsafe { core::ptr::read_volatile((self.root as *const u64).add(2)) } != 0
        {
            return Err(Error::UnsupportedLayout);
        }
        let mut frames = [0; USER_OWNED_FRAMES];
        for index in 0..USER_OWNED_FRAMES {
            let Some(frame) = allocator.allocate() else {
                for owned in frames[..index].iter().rev().copied() {
                    allocator.release(owned).expect("new user-space frame");
                }
                return Err(Error::OutOfFrames);
            };
            frames[index] = frame;
        }
        for frame in frames {
            unsafe { core::ptr::write_bytes(frame as *mut u8, 0, PAGE_SIZE as usize) };
        }
        for index in 0..ENTRIES {
            let descriptor =
                unsafe { core::ptr::read_volatile((self.root as *const u64).add(index)) };
            unsafe { write(frames[0], index, descriptor) };
        }
        unsafe {
            write(frames[0], 2, table(frames[1]));
            write(frames[1], 0, table(frames[2]));
            write(
                frames[2],
                0,
                (ram_page(frames[3], true, true) | AP_EL0_ACCESS | NON_GLOBAL | PXN) & !UXN,
            );
            write(
                frames[2],
                1,
                ram_page(frames[4], false, false) | AP_EL0_ACCESS | NON_GLOBAL,
            );
            write(
                frames[2],
                3,
                ram_page(frames[5], false, false) | AP_EL0_ACCESS | NON_GLOBAL,
            );
        }
        Ok(UserSpace {
            root: frames[0],
            frames,
        })
    }

    /// Invalidate the page immediately below a dedicated 16 KiB EL1t task
    /// stack. This is image-owned BSS, not an allocator frame. The caller
    /// must perform DSB/TLBI/DSB/ISB before entering the task.
    ///
    /// # Safety
    /// This CPU exclusively owns the first-RAM L3 table, and no code accesses
    /// the guard VA between clearing its descriptor and invalidating the TLB.
    pub unsafe fn unmap_task_stack_guard(
        &self,
        guard: u64,
        stack_start: u64,
        image_start: u64,
        image_end: u64,
    ) -> Result<(), Error> {
        let Some(stack_end) = stack_start.checked_add(4 * PAGE_SIZE) else {
            return Err(Error::UnsupportedLayout);
        };
        if guard % PAGE_SIZE != 0
            || guard < RAM_BASE
            || guard.checked_add(PAGE_SIZE) != Some(stack_start)
            || guard < image_start
            || stack_end > image_end
            || stack_end > RAM_BASE + MIB2
            || self.count < TABLE_COUNT
        {
            return Err(Error::UnsupportedLayout);
        }
        let index = ((guard - RAM_BASE) / PAGE_SIZE) as usize;
        let slot = (self.frames[4] as *mut u64).wrapping_add(index);
        if unsafe { core::ptr::read_volatile(slot) } != ram_page(guard, false, false) {
            return Err(Error::UnsupportedLayout);
        }
        unsafe { core::ptr::write_volatile(slot, 0) };
        Ok(())
    }

    pub fn task_stack_guard_unmapped(&self, guard: u64) -> bool {
        if guard < RAM_BASE
            || guard >= RAM_BASE + MIB2
            || guard % PAGE_SIZE != 0
            || self.count < TABLE_COUNT
        {
            return false;
        }
        let index = ((guard - RAM_BASE) / PAGE_SIZE) as usize;
        unsafe { core::ptr::read_volatile((self.frames[4] as *const u64).add(index)) == 0 }
    }

    pub fn heap_window_unmapped(&self) -> bool {
        let base = ((HEAP_WINDOW_START - RAM_BASE) / PAGE_SIZE) as usize;
        let l3 = self.frames[4] as *const u64;
        (0..HEAP_WINDOW_PAGES).all(|index| unsafe {
            // SAFETY: the first-RAM L3 table is owned for this boot.
            core::ptr::read_volatile(l3.add(base + index)) == 0
        })
    }

    pub fn heap_tail_unmapped(&self) -> bool {
        let base = ((HEAP_WINDOW_START - RAM_BASE) / PAGE_SIZE) as usize;
        let l3 = self.frames[4] as *const u64;
        (HEAP_INITIAL_PAGES..HEAP_WINDOW_PAGES).all(|index| unsafe {
            // SAFETY: the first-RAM L3 table is owned for this boot.
            core::ptr::read_volatile(l3.add(base + index)) == 0
        })
    }

    /// Populate the first four private heap VAs before TTBR0 is installed.
    /// All fallible allocation checks happen before any descriptor is written.
    ///
    /// # Safety
    /// The caller owns the first-RAM L3 table, uses a finalized allocator
    /// that excludes the heap VA's identity range, and retains HeapPages for
    /// the full lifetime of the translation regime.
    pub unsafe fn map_heap_prefix(
        &self,
        allocator: &mut FrameAllocator,
    ) -> Result<HeapPages, Error> {
        if !self.heap_window_unmapped() {
            return Err(Error::UnsupportedLayout);
        }
        let mut frames = [0; HEAP_INITIAL_PAGES];
        for index in 0..HEAP_INITIAL_PAGES {
            let Some(frame) = allocator.allocate() else {
                for prior in frames[..index].iter().rev().copied() {
                    allocator.release(prior).expect("new heap frame");
                }
                return Err(Error::OutOfFrames);
            };
            if (HEAP_WINDOW_START..HEAP_WINDOW_START + HEAP_WINDOW_PAGES as u64 * PAGE_SIZE)
                .contains(&frame)
                || self.frames[..self.count].contains(&frame)
            {
                allocator.release(frame).expect("new heap frame");
                for prior in frames[..index].iter().rev().copied() {
                    allocator.release(prior).expect("new heap frame");
                }
                return Err(Error::UnsupportedLayout);
            }
            frames[index] = frame;
        }
        let base = ((HEAP_WINDOW_START - RAM_BASE) / PAGE_SIZE) as usize;
        let l3 = self.frames[4];
        for (index, frame) in frames.iter().copied().enumerate() {
            // SAFETY: each allocated frame is writable identity-mapped RAM;
            // descriptor targets were proven zero and TTBR0 is not yet active.
            unsafe {
                core::ptr::write_bytes(frame as *mut u8, 0, PAGE_SIZE as usize);
                write(l3, base + index, ram_page(frame, false, false));
            }
        }
        Ok(HeapPages { frames })
    }

    /// Remove one heap translation. The caller must invalidate the TLB entry
    /// with DSB/TLBI/DSB/ISB before returning `physical` to FrameAllocator.
    ///
    /// # Safety
    /// The caller owns this table and physical page, has stopped all users of
    /// the VA, and performs the required translation barrier before reuse.
    pub unsafe fn detach_heap_page(&self, index: usize, physical: u64) -> Result<(), Error> {
        if index >= HEAP_INITIAL_PAGES || physical == 0 || physical % PAGE_SIZE != 0 {
            return Err(Error::UnsupportedLayout);
        }
        let base = ((HEAP_WINDOW_START - RAM_BASE) / PAGE_SIZE) as usize;
        let slot = (self.frames[4] as *mut u64).wrapping_add(base + index);
        // SAFETY: caller owns the first-RAM L3 table and this entry.
        if unsafe { core::ptr::read_volatile(slot) } != ram_page(physical, false, false) {
            return Err(Error::UnsupportedLayout);
        }
        unsafe { core::ptr::write_volatile(slot, 0) };
        Ok(())
    }

    pub fn frame_count(&self) -> usize {
        self.frames[..self.count].len()
    }

    /// Account every frame retained by the live TTBR0 owner. Extra split-RAM
    /// or mapped-device tables share one conservative role: neither may be
    /// returned while a translation can still walk through them.
    pub fn tagged_frames(&self) -> impl Iterator<Item = TaggedTableFrame> + '_ {
        self.frames[..self.count]
            .iter()
            .copied()
            .enumerate()
            .map(|(index, address)| TaggedTableFrame {
                address,
                role: match index {
                    0 => TableFrameRole::Root,
                    1 => TableFrameRole::DeviceL2,
                    2 => TableFrameRole::UartL3,
                    3 => TableFrameRole::RamL2,
                    4 => TableFrameRole::FirstRamL3,
                    _ => TableFrameRole::AdditionalTranslation,
                },
            })
    }

    pub fn owns_table_frame(&self, address: u64) -> bool {
        self.frames[..self.count].contains(&address)
    }

    /// K466: audit the live, owned TTBR0 path for one writable Normal,
    /// Inner-Shareable identity-mapped data address before sharing atomics.
    /// No page-table writer may run concurrently with this point-in-time walk.
    pub fn normal_shareable_identity(&self, address: u64) -> bool {
        if address < RAM_BASE || address >= RAM_BASE + GIB {
            return false;
        }
        // SAFETY: build_identity_tables owns the root and index 1 is its RAM
        // branch. Every descendant is checked against the owned-frame list
        // before a table pointer is dereferenced.
        let l1 = unsafe { core::ptr::read_volatile((self.root as *const u64).add(1)) };
        if l1 & 3 != 3 {
            return false;
        }
        let l2_address = l1 & 0x0000_ffff_ffff_f000;
        if !self.owns_table_frame(l2_address) {
            return false;
        }
        let l2_index = ((address - RAM_BASE) / MIB2) as usize;
        let l2 = unsafe { core::ptr::read_volatile((l2_address as *const u64).add(l2_index)) };
        let (leaf, physical) = if l2 & 3 == VALID_BLOCK {
            (l2, (l2 & 0x0000_ffff_ffe0_0000) | (address & (MIB2 - 1)))
        } else if l2 & 3 == VALID_TABLE_OR_PAGE {
            let l3_address = l2 & 0x0000_ffff_ffff_f000;
            if !self.owns_table_frame(l3_address) {
                return false;
            }
            let index = ((address / PAGE_SIZE) & 511) as usize;
            let l3 = unsafe { core::ptr::read_volatile((l3_address as *const u64).add(index)) };
            if l3 & 3 != VALID_TABLE_OR_PAGE {
                return false;
            }
            (
                l3,
                (l3 & 0x0000_ffff_ffff_f000) | (address & (PAGE_SIZE - 1)),
            )
        } else {
            return false;
        };
        physical == address
            && leaf & (7 << 2) == ATTR_NORMAL
            && leaf & SHARE_INNER == SHARE_INNER
            && leaf & ACCESS_FLAG != 0
            && leaf & (AP_READ_ONLY | AP_EL0_ACCESS) == 0
            && leaf & (PXN | UXN) == PXN | UXN
    }

    pub fn block_count(&self) -> usize {
        self.block_count
    }

    /// Describe one valid-to-valid L3 replacement in the first RAM block.
    /// The caller performs break-before-make and the TLBI barriers.
    ///
    /// # Safety
    /// Both physical pages must be exclusively owned writable data frames;
    /// translation must already identity-map the table and old/new frames.
    pub unsafe fn probe_replacement(
        &self,
        virtual_address: u64,
        old_physical: u64,
        new_physical: u64,
    ) -> Result<(*mut u64, u64), Error> {
        let valid = |address: u64| {
            address >= RAM_BASE
                && address < RAM_BASE + MIB2
                && address % PAGE_SIZE == 0
                && !self.frames[..self.count].contains(&address)
        };
        if !valid(virtual_address)
            || !valid(old_physical)
            || !valid(new_physical)
            || old_physical == new_physical
        {
            return Err(Error::UnsupportedLayout);
        }
        let index = ((virtual_address - RAM_BASE) / PAGE_SIZE) as usize;
        let slot = (self.frames[4] as *mut u64).wrapping_add(index);
        // SAFETY: the table frame is owned, identity mapped and index < 512.
        if unsafe { core::ptr::read_volatile(slot) } != ram_page(old_physical, false, false) {
            return Err(Error::UnsupportedLayout);
        }
        Ok((slot, ram_page(new_physical, false, false)))
    }

    /// Map exactly one device window before TTBR0 is installed. The caller
    /// keeps this extra table frame owned for the entire translated boot.
    ///
    /// # Safety
    /// The DTB window must be a real MMIO range and the supplied allocator
    /// must own identity-addressable RAM. This must run before enabling MMU.
    pub unsafe fn map_device_window(
        &mut self,
        allocator: &mut FrameAllocator,
        base: u64,
        size: u64,
        uart_base: u64,
    ) -> Result<(), Error> {
        let plan = plan_device_window(base, size, uart_base).ok_or(Error::UnsupportedLayout)?;
        let device_l2 = self.frames[1];
        // SAFETY: build_identity_tables owns device_l2 and the index is in range.
        let prior = unsafe { core::ptr::read_volatile((device_l2 as *const u64).add(plan.l2)) };
        if prior != 0 || self.count == MAX_TABLE_COUNT {
            return Err(Error::UnsupportedLayout);
        }
        let page = allocator.allocate().ok_or(Error::OutOfFrames)?;
        // SAFETY: the newly owned page is writable identity-mapped RAM.
        unsafe {
            core::ptr::write_bytes(page as *mut u8, 0, PAGE_SIZE as usize);
            for offset in 0..plan.pages {
                write(
                    page,
                    plan.first_page + offset,
                    device_page(base + offset as u64 * PAGE_SIZE),
                );
            }
            // Publish the parent only after every child descriptor is ready.
            write(device_l2, plan.l2, table(page));
        }
        self.frames[self.count] = page;
        self.count += 1;
        Ok(())
    }
}

struct DeviceWindowPlan {
    l2: usize,
    first_page: usize,
    pages: usize,
}

fn plan_device_window(base: u64, size: u64, uart_base: u64) -> Option<DeviceWindowPlan> {
    let end = base.checked_add(size)?;
    if base == 0
        || base % PAGE_SIZE != 0
        || size == 0
        || size % PAGE_SIZE != 0
        || end > GIB
        || base / MIB2 != (end - 1) / MIB2
        || base / MIB2 == uart_base / MIB2
    {
        return None;
    }
    Some(DeviceWindowPlan {
        l2: ((base >> 21) & 511) as usize,
        first_page: ((base >> 12) & 511) as usize,
        pages: (size / PAGE_SIZE) as usize,
    })
}

fn table(address: u64) -> u64 {
    address | VALID_TABLE_OR_PAGE
}

fn ram_page(address: u64, executable: bool, read_only: bool) -> u64 {
    address
        | VALID_TABLE_OR_PAGE
        | ATTR_NORMAL
        | ACCESS_FLAG
        | SHARE_INNER
        | if read_only { AP_READ_ONLY } else { 0 }
        | if executable { 0 } else { PXN }
        | UXN
}

fn ram_block(address: u64) -> u64 {
    address | VALID_BLOCK | ATTR_NORMAL | ACCESS_FLAG | SHARE_INNER | PXN | UXN
}

fn device_page(address: u64) -> u64 {
    address | VALID_TABLE_OR_PAGE | ATTR_DEVICE | ACCESS_FLAG | PXN | UXN
}

fn allocate_table_frames(
    allocator: &mut FrameAllocator,
    count: usize,
) -> Result<[u64; MAX_TABLE_COUNT], Error> {
    debug_assert!(count <= MAX_TABLE_COUNT);
    let mut frames = [0; MAX_TABLE_COUNT];
    for index in 0..count {
        let Some(address) = allocator.allocate() else {
            for owned in frames[..index].iter().rev().copied() {
                allocator.release(owned).expect("fresh MMU table frame");
            }
            return Err(Error::OutOfFrames);
        };
        frames[index] = address;
    }
    Ok(frames)
}

/// # Safety
/// The allocator must own genuinely writable identity-addressed RAM. The
/// caller must keep the returned frames allocated for as long as TTBR0 uses
/// them. This layout is deliberately restricted to QEMU virt's test address
/// range, not a general-purpose mapper or a substitute for DTB no-map rules.
pub unsafe fn build_identity_tables(
    allocator: &mut FrameAllocator,
    layout: Layout,
    reservations: &[Reservation],
) -> Result<Tables, Error> {
    layout.validate()?;
    let (split, extra_count) = split_blocks(layout, reservations)?;
    let total_count = TABLE_COUNT + extra_count;
    let frames = allocate_table_frames(allocator, total_count)?;
    for address in frames[..total_count].iter().copied() {
        // SAFETY: all table pages were exclusively obtained from the allocator.
        unsafe { core::ptr::write_bytes(address as *mut u8, 0, PAGE_SIZE as usize) };
    }
    let [root, device_l2, uart_l3, ram_l2, first_ram_l3] =
        [frames[0], frames[1], frames[2], frames[3], frames[4]];
    let mut block_count = 0;
    // SAFETY: each index is within the 512-entry page and all pages are owned.
    unsafe {
        write(root, 0, table(device_l2));
        write(root, 1, table(ram_l2));
        write(
            device_l2,
            ((layout.uart_base >> 21) & 511) as usize,
            table(uart_l3),
        );
        write(
            uart_l3,
            ((layout.uart_base >> 12) & 511) as usize,
            device_page(layout.uart_base),
        );
        write(ram_l2, 0, table(first_ram_l3));
        for index in 0..ENTRIES {
            let address = RAM_BASE + index as u64 * PAGE_SIZE;
            write(
                first_ram_l3,
                index,
                ram_page_descriptor(layout, address, reservations),
            );
        }
        let mut next_extra = TABLE_COUNT;
        for index in 1..(layout.ram_size / MIB2) as usize {
            let block_start = RAM_BASE + index as u64 * MIB2;
            if split[index] {
                let l3 = frames[next_extra];
                next_extra += 1;
                write(ram_l2, index, table(l3));
                for page_index in 0..ENTRIES {
                    let address = block_start + page_index as u64 * PAGE_SIZE;
                    write(
                        l3,
                        page_index,
                        ram_page_descriptor(layout, address, reservations),
                    );
                }
            } else {
                write(ram_l2, index, ram_block(block_start));
                block_count += 1;
            }
        }
        debug_assert_eq!(next_extra, total_count);
    }
    Ok(Tables {
        root,
        frames,
        count: total_count,
        block_count,
    })
}

unsafe fn write(table_address: u64, index: usize, descriptor: u64) {
    debug_assert!(index < ENTRIES);
    // SAFETY: caller owns a zeroed 4 KiB table page and supplies a valid index.
    unsafe { core::ptr::write_volatile((table_address as *mut u64).add(index), descriptor) };
}

/// T0SZ=25 selects a 39-bit TTBR0 range whose first table is level 1.
/// TTBR1 walks are disabled. PARange is copied from ID_AA64MMFR0_EL1.
pub fn tcr_el1(parange: u64) -> Option<u64> {
    if parange > 5 {
        return None;
    }
    Some(25 | (1 << 8) | (1 << 10) | (3 << 12) | (1 << 23) | (parange << 32))
}

/// Attr0: Normal WB/WA, Attr1: Device-nGnRnE.
pub const MAIR_EL1: u64 = 0x00ff;

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

    use super::*;
    use std::boxed::Box;

    #[test]
    fn k076_table_owner_tags_cover_every_retained_frame_once() {
        let mut frames = [0; MAX_TABLE_COUNT];
        for (index, frame) in frames.iter_mut().take(7).enumerate() {
            *frame = RAM_BASE + index as u64 * PAGE_SIZE;
        }
        let tables = Tables {
            root: frames[0],
            frames,
            count: 7,
            block_count: 0,
        };
        let tagged: std::vec::Vec<_> = tables.tagged_frames().collect();
        assert_eq!(tagged.len(), tables.frame_count());
        assert_eq!(
            tagged
                .iter()
                .map(|tag| tag.role)
                .collect::<std::vec::Vec<_>>(),
            [
                TableFrameRole::Root,
                TableFrameRole::DeviceL2,
                TableFrameRole::UartL3,
                TableFrameRole::RamL2,
                TableFrameRole::FirstRamL3,
                TableFrameRole::AdditionalTranslation,
                TableFrameRole::AdditionalTranslation,
            ]
        );
        for (index, tag) in tagged.iter().enumerate() {
            assert_eq!(tag.address, RAM_BASE + index as u64 * PAGE_SIZE);
            assert!(tables.owns_table_frame(tag.address));
        }
        assert!(!tables.owns_table_frame(RAM_BASE + 7 * PAGE_SIZE));
    }

    #[repr(align(4096))]
    struct HostTablePages([u8; 3 * PAGE_SIZE as usize]);

    #[test]
    fn k466_normal_shareable_identity_audit_rejects_changed_descriptor() {
        let mut backing = Box::new(HostTablePages([0; 3 * PAGE_SIZE as usize]));
        let root = backing.0.as_mut_ptr() as u64;
        let l2 = root + PAGE_SIZE;
        let l3 = l2 + PAGE_SIZE;
        let mut tables = Tables {
            root,
            frames: [0; MAX_TABLE_COUNT],
            count: 3,
            block_count: 0,
        };
        tables.frames[..3].copy_from_slice(&[root, l2, l3]);
        unsafe {
            write(root, 1, table(l2));
            write(l2, 0, table(l3));
            write(l3, 0, ram_page(RAM_BASE, false, false));
            write(l2, 1, ram_block(RAM_BASE + MIB2));
        }
        assert!(tables.normal_shareable_identity(RAM_BASE + 8));
        assert!(tables.normal_shareable_identity(RAM_BASE + MIB2 + 8));
        assert!(!tables.normal_shareable_identity(RAM_BASE - PAGE_SIZE));
        assert!(!tables.normal_shareable_identity(RAM_BASE + PAGE_SIZE));
        for corrupted in [
            device_page(RAM_BASE),
            ram_page(RAM_BASE, false, true),
            ram_page(RAM_BASE, false, false) & !SHARE_INNER,
            ram_page(RAM_BASE, false, false) & !ACCESS_FLAG,
            ram_page(RAM_BASE + PAGE_SIZE, false, false),
            ram_page(RAM_BASE, true, false),
        ] {
            unsafe { write(l3, 0, corrupted) };
            assert!(!tables.normal_shareable_identity(RAM_BASE + 8));
        }
        unsafe { write(l3, 0, ram_page(RAM_BASE, false, false)) };
        unsafe { write(root, 1, table(root + 3 * PAGE_SIZE)) };
        assert!(!tables.normal_shareable_identity(RAM_BASE));
    }

    #[repr(align(4096))]
    struct HostHeapPages([u8; 6 * PAGE_SIZE as usize]);

    #[repr(align(4096))]
    struct HostUserPages([u8; 8 * PAGE_SIZE as usize]);

    #[repr(align(4096))]
    struct HostDualUserPages([u8; 14 * PAGE_SIZE as usize]);

    #[repr(align(4096))]
    struct HostDeviceAuditPages([u8; 5 * PAGE_SIZE as usize]);

    #[test]
    fn k452_every_live_device_leaf_in_user_root_denies_el0() {
        let mut backing = Box::new(HostDeviceAuditPages([0; 5 * PAGE_SIZE as usize]));
        let mut user_backing = Box::new(HostUserPages([0; 8 * PAGE_SIZE as usize]));
        let base = backing.0.as_mut_ptr() as u64;
        let private = user_backing.0.as_mut_ptr() as u64;
        let mut tables = Tables {
            root: base,
            frames: [0; MAX_TABLE_COUNT],
            count: 5,
            block_count: 0,
        };
        tables.frames[..5].copy_from_slice(&[
            base,
            base + PAGE_SIZE,
            base + 2 * PAGE_SIZE,
            base + 3 * PAGE_SIZE,
            base + 4 * PAGE_SIZE,
        ]);
        let user = UserSpace {
            root: private,
            frames: [
                private,
                private + PAGE_SIZE,
                private + 2 * PAGE_SIZE,
                private + 3 * PAGE_SIZE,
                private + 4 * PAGE_SIZE,
                private + 5 * PAGE_SIZE,
            ],
        };
        let windows = [
            (0x0900_0000, PAGE_SIZE),
            (0x080a_0000, 0x2_0000),
            (0x0a00_0000, 4 * PAGE_SIZE),
        ];
        let uart = base + 2 * PAGE_SIZE;
        let gicr = base + 3 * PAGE_SIZE;
        let virtio = base + 4 * PAGE_SIZE;
        unsafe {
            write(base, 0, table(base + PAGE_SIZE));
            write(private, 0, table(base + PAGE_SIZE));
            write(base + PAGE_SIZE, 72, table(uart));
            write(base + PAGE_SIZE, 64, table(gicr));
            write(base + PAGE_SIZE, 80, table(virtio));
            write(uart, 0, device_page(0x0900_0000));
            for index in 0..32 {
                write(
                    gicr,
                    160 + index,
                    device_page(0x080a_0000 + index as u64 * PAGE_SIZE),
                );
            }
            for index in 0..4 {
                write(
                    virtio,
                    index,
                    device_page(0x0a00_0000 + index as u64 * PAGE_SIZE),
                );
            }
        }
        assert_eq!(tables.audit_device_el0(&user, &windows), Ok(37));
        assert_eq!(
            tables.audit_device_el0(&user, &windows[..2]),
            Err(DeviceAuditError::UnexpectedDevice(0x0a00_0000))
        );
        assert_eq!(
            tables.audit_device_el0(&user, &[(0x0900_0000, PAGE_SIZE), (0x0900_0000, PAGE_SIZE)]),
            Err(DeviceAuditError::InvalidWindow)
        );
        for (frame, index, va) in [
            (uart, 0, 0x0900_0000),
            (gicr, 191, 0x080b_f000),
            (virtio, 3, 0x0a00_3000),
        ] {
            let original = unsafe { core::ptr::read_volatile((frame as *const u64).add(index)) };
            unsafe { write(frame, index, original | AP_EL0_ACCESS) };
            assert_eq!(
                tables.audit_device_el0(&user, &windows),
                Err(DeviceAuditError::El0Accessible(va))
            );
            unsafe { write(frame, index, original) };
        }
        unsafe { write(gicr, 160, 0) };
        assert_eq!(
            tables.audit_device_el0(&user, &windows),
            Err(DeviceAuditError::MissingDevicePages)
        );
        unsafe { write(gicr, 160, device_page(0x080a_0000)) };
        unsafe { write(gicr, 0, ram_page(0x0800_0000, false, false) | AP_EL0_ACCESS) };
        assert_eq!(
            tables.audit_device_el0(&user, &windows),
            Err(DeviceAuditError::El0Accessible(0x0800_0000))
        );
        unsafe { write(gicr, 0, 0) };
        unsafe { write(virtio, 0, device_page(0x0a00_1000)) };
        assert_eq!(
            tables.audit_device_el0(&user, &windows),
            Err(DeviceAuditError::NonIdentityDevice(0x0a00_0000))
        );
        unsafe { write(virtio, 0, device_page(0x0a00_0000)) };
        unsafe { write(base + PAGE_SIZE, 80, table(private + 7 * PAGE_SIZE)) };
        assert_eq!(
            tables.audit_device_el0(&user, &windows),
            Err(DeviceAuditError::UnknownTable(private + 7 * PAGE_SIZE))
        );
    }

    #[test]
    fn private_user_root_has_disjoint_va_permissions_and_transactional_frames() {
        for mib in [256, 512, 1024] {
            assert!(user_window_disjoint_from_kernel_ram(
                RAM_BASE,
                mib * 1024 * 1024
            ));
        }
        assert!(!user_window_disjoint_from_kernel_ram(
            RAM_BASE + PAGE_SIZE,
            256 * 1024 * 1024
        ));
        assert!(!user_window_disjoint_from_kernel_ram(
            RAM_BASE,
            GIB + PAGE_SIZE
        ));
        assert!(!user_window_disjoint_from_kernel_ram(RAM_BASE, 0));
        let mut backing = Box::new(HostUserPages([0; 8 * PAGE_SIZE as usize]));
        let base = backing.0.as_mut_ptr() as u64;
        let mut tables = Tables {
            root: base,
            frames: [0; MAX_TABLE_COUNT],
            count: TABLE_COUNT,
            block_count: 0,
        };
        tables.frames[0] = base;
        unsafe {
            write(base, 0, table(base));
            write(base, 1, table(base + PAGE_SIZE));
        }
        let short = crate::memory::FreeMap::from_ram(base + PAGE_SIZE, 5 * PAGE_SIZE).unwrap();
        let mut short_allocator = FrameAllocator::new(short);
        assert!(matches!(
            unsafe { tables.build_user_space(&mut short_allocator, RAM_BASE, GIB) },
            Err(Error::OutOfFrames)
        ));
        assert_eq!(short_allocator.remaining_pages(), 5);
        let enough = crate::memory::FreeMap::from_ram(base + PAGE_SIZE, 7 * PAGE_SIZE).unwrap();
        let mut allocator = FrameAllocator::new(enough);
        unsafe { write(base, 2, table(base + 2 * PAGE_SIZE)) };
        assert!(matches!(
            unsafe { tables.build_user_space(&mut allocator, RAM_BASE, GIB) },
            Err(Error::UnsupportedLayout)
        ));
        assert_eq!(allocator.remaining_pages(), 7);
        unsafe { write(base, 2, 0) };
        let user = unsafe { tables.build_user_space(&mut allocator, RAM_BASE, GIB) }.unwrap();
        assert_ne!(user.root, tables.root);
        assert_eq!(allocator.remaining_pages(), 1);
        assert_eq!(
            unsafe { core::ptr::read_volatile((user.root as *const u64).add(0)) },
            table(base)
        );
        assert_eq!(
            unsafe { core::ptr::read_volatile((user.root as *const u64).add(1)) },
            table(base + PAGE_SIZE)
        );
        assert_eq!(
            unsafe { core::ptr::read_volatile((tables.root as *const u64).add(2)) },
            0
        );
        assert_eq!(
            unsafe { core::ptr::read_volatile((user.root as *const u64).add(2)) },
            table(user.frames[1])
        );
        let code = user.descriptor(0).unwrap();
        let data = user.descriptor(1).unwrap();
        let stack = user.descriptor(3).unwrap();
        assert_eq!(code & 0x0000_ffff_ffff_f000, user.code_frame());
        assert_eq!(
            code & (AP_EL0_ACCESS | AP_READ_ONLY | NON_GLOBAL | PXN | UXN),
            AP_EL0_ACCESS | AP_READ_ONLY | NON_GLOBAL | PXN
        );
        for (descriptor, physical) in [(data, user.data_frame()), (stack, user.stack_frame())] {
            assert_eq!(descriptor & 0x0000_ffff_ffff_f000, physical);
            assert_eq!(
                descriptor & (AP_EL0_ACCESS | AP_READ_ONLY | NON_GLOBAL | PXN | UXN),
                AP_EL0_ACCESS | NON_GLOBAL | PXN | UXN
            );
        }
        assert_eq!(user.descriptor(2), Some(0));
        assert_eq!(user.descriptor(4), None);
        assert!(user.contract_valid(tables.root));
    }

    #[test]
    fn k450_retired_user_frames_are_zero_before_same_frame_reuse() {
        let mut backing = Box::new(HostUserPages([0; 8 * PAGE_SIZE as usize]));
        let base = backing.0.as_mut_ptr() as u64;
        let mut tables = Tables {
            root: base,
            frames: [0; MAX_TABLE_COUNT],
            count: 1,
            block_count: 0,
        };
        tables.frames[0] = base;
        let free = crate::memory::FreeMap::from_ram(base + PAGE_SIZE, 7 * PAGE_SIZE).unwrap();
        let mut allocator = FrameAllocator::new(free);
        let first = unsafe { tables.build_user_space(&mut allocator, RAM_BASE, GIB) }.unwrap();
        let retired = first.frames;
        assert_eq!(allocator.remaining_pages(), 1);
        for (index, frame) in retired[3..].iter().copied().enumerate() {
            unsafe {
                core::ptr::write_bytes(
                    frame as *mut u8,
                    [0xa5, 0x5a, 0xc3][index],
                    PAGE_SIZE as usize,
                )
            };
        }
        assert!(first.contract_valid(tables.root));
        unsafe { first.release_after_tlbi(&mut allocator, tables.root) }.unwrap();
        assert_eq!(allocator.remaining_pages(), 7);
        for frame in retired {
            let page =
                unsafe { core::slice::from_raw_parts(frame as *const u8, PAGE_SIZE as usize) };
            assert!(
                page.iter().all(|byte| *byte == 0),
                "retired frame still contains secret bytes"
            );
        }
        let next = unsafe { tables.build_user_space(&mut allocator, RAM_BASE, GIB) }.unwrap();
        assert_eq!(
            next.frames, retired,
            "new task did not reuse the retired physical frames"
        );
        for frame in [next.code_frame(), next.data_frame(), next.stack_frame()] {
            let page =
                unsafe { core::slice::from_raw_parts(frame as *const u8, PAGE_SIZE as usize) };
            assert!(
                page.iter().all(|byte| *byte == 0),
                "next task observed previous owner data"
            );
        }
        unsafe { core::ptr::write_bytes(next.data_frame() as *mut u8, 0x7a, PAGE_SIZE as usize) };
        allocator.release(next.stack_frame()).unwrap();
        let before_failed_return = allocator.remaining_pages();
        let (error, still_owned) =
            unsafe { next.release_after_tlbi(&mut allocator, tables.root) }.unwrap_err();
        assert_eq!(error, Error::UnsupportedLayout);
        assert_eq!(allocator.remaining_pages(), before_failed_return);
        let data = unsafe {
            core::slice::from_raw_parts(still_owned.data_frame() as *const u8, PAGE_SIZE as usize)
        };
        assert!(
            data.iter().all(|byte| *byte == 0x7a),
            "invalid return partially scrubbed a live page"
        );
    }

    #[test]
    fn user_root_exhaustion_rolls_back_every_partial_allocation() {
        for available in 0..USER_OWNED_FRAMES {
            let mut backing = Box::new(HostUserPages([0x5a; 8 * PAGE_SIZE as usize]));
            let base = backing.0.as_mut_ptr() as u64;
            let mut tables = Tables {
                root: base,
                frames: [0; MAX_TABLE_COUNT],
                count: TABLE_COUNT,
                block_count: 0,
            };
            tables.frames[0] = base;
            unsafe {
                core::ptr::write_bytes(base as *mut u8, 0, PAGE_SIZE as usize);
                write(base, 0, table(base));
                write(base, 1, table(base + PAGE_SIZE));
            }
            let capacity = available.max(1);
            let free =
                crate::memory::FreeMap::from_ram(base + PAGE_SIZE, capacity as u64 * PAGE_SIZE)
                    .unwrap();
            let mut allocator = FrameAllocator::new(free);
            let held = if available == 0 {
                Some(allocator.allocate().unwrap())
            } else {
                None
            };
            assert_eq!(allocator.remaining_pages(), available as u64);
            assert!(matches!(
                unsafe { tables.build_user_space(&mut allocator, RAM_BASE, GIB) },
                Err(Error::OutOfFrames)
            ));
            assert_eq!(allocator.remaining_pages(), available as u64);
            assert_eq!(
                unsafe { core::ptr::read_volatile((base as *const u64).add(0)) },
                table(base)
            );
            assert_eq!(
                unsafe { core::ptr::read_volatile((base as *const u64).add(1)) },
                table(base + PAGE_SIZE)
            );
            assert_eq!(
                unsafe { core::ptr::read_volatile((base as *const u64).add(2)) },
                0
            );
            let mut reacquired = [0; USER_OWNED_FRAMES - 1];
            for frame in reacquired.iter_mut().take(available) {
                *frame = allocator.allocate().expect("rollback frame available");
                assert_eq!(
                    unsafe { core::ptr::read_volatile(*frame as *const u8) },
                    0x5a
                );
                assert_eq!(
                    unsafe { core::ptr::read_volatile((*frame + PAGE_SIZE - 1) as *const u8) },
                    0x5a
                );
            }
            assert_eq!(allocator.remaining_pages(), 0);
            for frame in reacquired.iter().take(available).rev() {
                allocator.release(*frame).unwrap();
            }
            if let Some(frame) = held {
                allocator.release(frame).unwrap();
            }
            assert_eq!(allocator.remaining_pages(), capacity as u64);
        }
    }

    fn process_elf_fixture() -> [u8; 512] {
        let mut file = [0u8; 512];
        file[..7].copy_from_slice(&[0x7f, b'E', b'L', b'F', 2, 1, 1]);
        file[16..18].copy_from_slice(&2u16.to_le_bytes());
        file[18..20].copy_from_slice(&183u16.to_le_bytes());
        file[20..24].copy_from_slice(&1u32.to_le_bytes());
        file[24..32].copy_from_slice(&USER_CODE_VA.to_le_bytes());
        file[32..40].copy_from_slice(&64u64.to_le_bytes());
        file[52..54].copy_from_slice(&64u16.to_le_bytes());
        file[54..56].copy_from_slice(&56u16.to_le_bytes());
        file[56..58].copy_from_slice(&1u16.to_le_bytes());
        file[64..68].copy_from_slice(&1u32.to_le_bytes());
        file[68..72].copy_from_slice(&5u32.to_le_bytes());
        file[72..80].copy_from_slice(&320u64.to_le_bytes());
        file[80..88].copy_from_slice(&USER_CODE_VA.to_le_bytes());
        file[96..104].copy_from_slice(&4u64.to_le_bytes());
        file[104..112].copy_from_slice(&8u64.to_le_bytes());
        file[112..120].copy_from_slice(&1u64.to_le_bytes());
        file[320..324].copy_from_slice(&[0x1f, 0x20, 0x03, 0xd5]); // NOP
        file
    }

    #[test]
    fn p10_k528_bad_elf_and_post_load_argv_restore_identity_regions_and_zero_pages() {
        use crate::{elf, process::ProcessTable, process_image};
        let mut backing = Box::new(HostUserPages([0; 8 * PAGE_SIZE as usize]));
        let base = backing.0.as_mut_ptr() as u64;
        let tables = Tables {
            root: base,
            frames: [0; MAX_TABLE_COUNT],
            count: 1,
            block_count: 0,
        };
        let mut allocator = FrameAllocator::new(
            crate::memory::FreeMap::from_ram(base + PAGE_SIZE, 7 * PAGE_SIZE).unwrap(),
        );
        let mut processes = ProcessTable::new();
        let original = processes.clone();
        let regions = allocator.free_regions().unwrap().to_vec();
        let file = process_elf_fixture();
        let oversized = [b'x'; elf::MAX_ARGUMENT_BYTES + 1];
        for case in 0..4 {
            // These six frames are acquired before ELF/argv validation.
            unsafe {
                core::ptr::write_bytes((base + PAGE_SIZE) as *mut u8, 0xa5, 6 * PAGE_SIZE as usize)
            };
            let mut damaged = file;
            let (expected, arguments): (elf::Error, &[&[u8]]) = match case {
                0 => {
                    damaged[0] = 0;
                    (elf::Error::BadMagic, &[b"init"])
                }
                1 => {
                    damaged[68..72].copy_from_slice(&7u32.to_le_bytes());
                    (elf::Error::WritableExecutable, &[b"init"])
                }
                2 => {
                    damaged[24..32].copy_from_slice(&(USER_CODE_VA + 1).to_le_bytes());
                    (elf::Error::BadEntry, &[b"init"])
                }
                _ => (elf::Error::BadArguments, &[&oversized]),
            };
            assert!(
                matches!(unsafe { process_image::spawn(&mut processes, &mut allocator, &tables, RAM_BASE, GIB, &damaged, arguments) },
                Err(process_image::Error::Elf(error)) if error == expected)
            );
            assert_eq!(processes, original);
            assert_eq!(allocator.remaining_pages(), 7);
            assert_eq!(allocator.free_regions().unwrap(), regions);
            assert!(backing.0[4096..7 * 4096].iter().all(|byte| *byte == 0));
        }
        assert_eq!(
            processes.create().unwrap().generation,
            1,
            "rejected spawn consumed identity generation"
        );
    }

    #[test]
    fn p10_k528_every_partial_allocation_and_full_process_table_are_atomic() {
        use crate::{process::ProcessTable, process_image};
        for available in 0..6usize {
            let mut backing = Box::new(HostUserPages([0; 8 * PAGE_SIZE as usize]));
            let base = backing.0.as_mut_ptr() as u64;
            let tables = Tables {
                root: base,
                frames: [0; MAX_TABLE_COUNT],
                count: 1,
                block_count: 0,
            };
            let mut allocator = FrameAllocator::new(
                crate::memory::FreeMap::from_ram(
                    base + PAGE_SIZE,
                    available.max(1) as u64 * PAGE_SIZE,
                )
                .unwrap(),
            );
            let held = if available == 0 {
                allocator.allocate()
            } else {
                None
            };
            let regions = allocator.free_regions().unwrap().to_vec();
            let mut processes = ProcessTable::new();
            let original = processes.clone();
            assert!(matches!(
                unsafe {
                    process_image::spawn(
                        &mut processes,
                        &mut allocator,
                        &tables,
                        RAM_BASE,
                        GIB,
                        &process_elf_fixture(),
                        &[b"init"],
                    )
                },
                Err(process_image::Error::Space(Error::OutOfFrames))
            ));
            assert_eq!(processes, original);
            assert_eq!(allocator.free_regions().unwrap(), regions);
            if let Some(frame) = held {
                allocator.release(frame).unwrap();
            }
        }
        let mut processes = ProcessTable::new();
        for _ in 0..crate::process::PROCESS_CAPACITY {
            processes.create().unwrap();
        }
        let original = processes.clone();
        let mut allocator =
            FrameAllocator::new(crate::memory::FreeMap::from_ram(0x4000_0000, PAGE_SIZE).unwrap());
        let tables = Tables {
            root: 0,
            frames: [0; MAX_TABLE_COUNT],
            count: 0,
            block_count: 0,
        };
        assert!(matches!(
            unsafe {
                process_image::spawn(
                    &mut processes,
                    &mut allocator,
                    &tables,
                    RAM_BASE,
                    GIB,
                    &process_elf_fixture(),
                    &[],
                )
            },
            Err(process_image::Error::Identity(
                crate::process::Error::Capacity
            ))
        ));
        assert_eq!(processes, original);
        assert_eq!(allocator.remaining_pages(), 1);
    }

    #[test]
    fn p10_k527_complete_elf_is_bound_to_new_ready_process_and_private_frames() {
        use crate::{
            process::{ProcessTable, State},
            process_image,
        };
        let mut backing = Box::new(HostUserPages([0; 8 * PAGE_SIZE as usize]));
        let base = backing.0.as_mut_ptr() as u64;
        let tables = Tables {
            root: base,
            frames: [0; MAX_TABLE_COUNT],
            count: 1,
            block_count: 0,
        };
        let mut allocator = FrameAllocator::new(
            crate::memory::FreeMap::from_ram(base + PAGE_SIZE, 7 * PAGE_SIZE).unwrap(),
        );
        let mut processes = ProcessTable::new();
        let image = unsafe {
            process_image::spawn(
                &mut processes,
                &mut allocator,
                &tables,
                RAM_BASE,
                GIB,
                &process_elf_fixture(),
                &[b"init"],
            )
        }
        .unwrap();
        assert_eq!(image.identity.generation, 1);
        assert_eq!(processes.state(image.identity), Ok(State::Ready));
        assert_eq!(image.loaded.entry, USER_CODE_VA);
        assert_eq!(image.loaded.code_bytes, 4);
        assert_eq!(image.initial.argc, 1);
        assert_eq!(allocator.remaining_pages(), 1);
        assert!(image.space.contract_valid(tables.root));
        let bytes =
            unsafe { core::slice::from_raw_parts(image.space.code_frame() as *const u8, 8) };
        assert_eq!(bytes, &[0x1f, 0x20, 0x03, 0xd5, 0, 0, 0, 0]);
        unsafe { image.space.release_after_tlbi(&mut allocator, tables.root) }.unwrap();
        assert_eq!(allocator.remaining_pages(), 7);
    }

    #[test]
    fn two_user_roots_own_distinct_frames_at_identical_virtual_addresses() {
        let mut backing = Box::new(HostDualUserPages([0; 14 * PAGE_SIZE as usize]));
        let base = backing.0.as_mut_ptr() as u64;
        let mut tables = Tables {
            root: base,
            frames: [0; MAX_TABLE_COUNT],
            count: TABLE_COUNT,
            block_count: 0,
        };
        tables.frames[0] = base;
        unsafe {
            write(base, 0, table(base));
            write(base, 1, table(base + PAGE_SIZE));
        }
        let free = crate::memory::FreeMap::from_ram(base + PAGE_SIZE, 13 * PAGE_SIZE).unwrap();
        let mut allocator = FrameAllocator::new(free);
        let a = unsafe { tables.build_user_space(&mut allocator, RAM_BASE, GIB) }.unwrap();
        let b = unsafe { tables.build_user_space(&mut allocator, RAM_BASE, GIB) }.unwrap();
        assert_eq!(allocator.remaining_pages(), 1);
        assert!(a.contract_valid(tables.root));
        assert!(b.contract_valid(tables.root));
        assert_eq!(
            unsafe { core::ptr::read_volatile((base as *const u64).add(2)) },
            0
        );
        for left in a.frames {
            assert!(!b.frames.contains(&left));
        }
        assert_ne!(a.root, b.root);
        for index in [0, 1, 3] {
            assert_ne!(a.descriptor(index), b.descriptor(index));
        }
        assert_eq!(a.descriptor(2), Some(0));
        assert_eq!(b.descriptor(2), Some(0));
        assert!(matches!(
            unsafe { tables.build_user_space(&mut allocator, RAM_BASE, GIB) },
            Err(Error::OutOfFrames)
        ));
        assert_eq!(allocator.remaining_pages(), 1);
        let wrong_root = a.root;
        let a = match unsafe { a.release_after_tlbi(&mut allocator, wrong_root) } {
            Err((Error::UnsupportedLayout, owner)) => owner,
            other => panic!("wrong-root reclaim must retain ownership: {other:?}"),
        };
        assert_eq!(allocator.remaining_pages(), 1);
        // Host tests have no guest TLB. The live user-dual teardown supplies
        // the TTBR0 switch and TLBI required by this unsafe ownership step.
        unsafe { a.release_after_tlbi(&mut allocator, tables.root) }.unwrap();
        assert_eq!(allocator.remaining_pages(), 7);
        unsafe { b.release_after_tlbi(&mut allocator, tables.root) }.unwrap();
        assert_eq!(allocator.remaining_pages(), 13);
        assert_eq!(
            unsafe { core::ptr::read_volatile((base as *const u64).add(2)) },
            0
        );
    }

    #[test]
    fn task_stack_guard_unmap_rejects_wrong_owner_before_clear() {
        let mut backing = Box::new(HostTablePages([0; 3 * PAGE_SIZE as usize]));
        let base = backing.0.as_mut_ptr() as u64;
        let mut tables = Tables {
            root: 0,
            frames: [0; MAX_TABLE_COUNT],
            count: TABLE_COUNT,
            block_count: 0,
        };
        tables.frames[4] = base;
        let guard = 0x4009_2000;
        let stack_start = guard + PAGE_SIZE;
        let slot = unsafe { (base as *mut u64).add(((guard - RAM_BASE) / PAGE_SIZE) as usize) };
        unsafe { core::ptr::write_volatile(slot, ram_page(guard, false, false)) };
        for (address, stack, image_start, image_end) in [
            (guard + 1, stack_start, 0x4008_0000, 0x4009_7000),
            (guard, stack_start + PAGE_SIZE, 0x4008_0000, 0x4009_7000),
            (guard, stack_start, guard + PAGE_SIZE, 0x4009_7000),
            (guard, stack_start, 0x4008_0000, 0x4009_5000),
        ] {
            assert_eq!(
                unsafe { tables.unmap_task_stack_guard(address, stack, image_start, image_end) },
                Err(Error::UnsupportedLayout)
            );
            assert_eq!(
                unsafe { core::ptr::read_volatile(slot) },
                ram_page(guard, false, false)
            );
        }
        unsafe { core::ptr::write_volatile(slot, ram_page(guard, true, false)) };
        assert_eq!(
            unsafe { tables.unmap_task_stack_guard(guard, stack_start, 0x4008_0000, 0x4009_7000) },
            Err(Error::UnsupportedLayout)
        );
        unsafe { core::ptr::write_volatile(slot, ram_page(guard, false, false)) };
        assert_eq!(
            unsafe { tables.unmap_task_stack_guard(guard, stack_start, 0x4008_0000, 0x4009_7000) },
            Ok(())
        );
        assert!(tables.task_stack_guard_unmapped(guard));
        assert_eq!(
            unsafe { tables.unmap_task_stack_guard(guard, stack_start, 0x4008_0000, 0x4009_7000) },
            Err(Error::UnsupportedLayout)
        );
    }

    #[test]
    fn heap_window_is_unmapped_and_cannot_overlap_image_or_no_map() {
        let heap = Layout {
            heap_start: Some(HEAP_WINDOW_START),
            ..layout()
        };
        assert_eq!(heap.validate(), Ok(()));
        for index in 0..HEAP_WINDOW_PAGES {
            assert_eq!(
                ram_page_descriptor(heap, HEAP_WINDOW_START + index as u64 * PAGE_SIZE, &[]),
                0
            );
        }
        assert_ne!(
            ram_page_descriptor(heap, HEAP_WINDOW_START - PAGE_SIZE, &[]),
            0
        );
        assert_ne!(
            ram_page_descriptor(
                heap,
                HEAP_WINDOW_START + HEAP_WINDOW_PAGES as u64 * PAGE_SIZE,
                &[]
            ),
            0
        );
        for bad in [HEAP_WINDOW_START - PAGE_SIZE, HEAP_WINDOW_START + PAGE_SIZE] {
            assert_eq!(
                Layout {
                    heap_start: Some(bad),
                    ..heap
                }
                .validate(),
                Err(Error::UnsupportedLayout)
            );
        }
        assert_eq!(
            Layout {
                image_end: HEAP_WINDOW_START,
                ..heap
            }
            .validate(),
            Err(Error::UnsupportedLayout)
        );
        assert_eq!(
            heap.validate_no_map(&[Reservation {
                start: HEAP_WINDOW_START,
                size: PAGE_SIZE,
                no_map: true
            }]),
            Err(Error::UnsupportedLayout)
        );
    }

    #[test]
    fn heap_frame_mapping_is_transactional_and_owned() {
        let mut backing = Box::new(HostHeapPages([0; 6 * PAGE_SIZE as usize]));
        let base = backing.0.as_mut_ptr() as u64;
        let mut tables = Tables {
            root: 0,
            frames: [0; MAX_TABLE_COUNT],
            count: TABLE_COUNT,
            block_count: 0,
        };
        tables.frames[4] = base;
        assert!(tables.heap_window_unmapped());
        let short = crate::memory::FreeMap::from_ram(base + PAGE_SIZE, 3 * PAGE_SIZE).unwrap();
        let mut short_allocator = FrameAllocator::new(short);
        // SAFETY: all three candidate frames and the fake L3 table are host-owned.
        assert!(matches!(
            unsafe { tables.map_heap_prefix(&mut short_allocator) },
            Err(Error::OutOfFrames)
        ));
        assert_eq!(short_allocator.remaining_pages(), 3);
        assert!(tables.heap_window_unmapped());
        let enough = crate::memory::FreeMap::from_ram(base + PAGE_SIZE, 5 * PAGE_SIZE).unwrap();
        let mut allocator = FrameAllocator::new(enough);
        // SAFETY: the test owns the L3 page and all five allocator pages.
        let owned = unsafe { tables.map_heap_prefix(&mut allocator) }.unwrap();
        assert_eq!(owned.count(), HEAP_INITIAL_PAGES);
        assert_eq!(allocator.remaining_pages(), 1);
        assert!(!tables.heap_window_unmapped());
        assert!(tables.heap_tail_unmapped());
        for (index, frame) in owned.frames.iter().copied().enumerate() {
            assert!(!owned.frames[..index].contains(&frame));
            assert_eq!(frame % PAGE_SIZE, 0);
            let slot = ((HEAP_WINDOW_START - RAM_BASE) / PAGE_SIZE) as usize + index;
            // SAFETY: slot belongs to the initialized fake L3 host page.
            assert_eq!(
                unsafe { core::ptr::read_volatile((base as *const u64).add(slot)) },
                ram_page(frame, false, false)
            );
        }
        // SAFETY: a second mapping attempt must fail before allocator mutation.
        assert!(matches!(
            unsafe { tables.map_heap_prefix(&mut allocator) },
            Err(Error::UnsupportedLayout)
        ));
        assert_eq!(allocator.remaining_pages(), 1);
        // SAFETY: wrong owner/index cannot alter the table; after each valid
        // detach the host test has no guest TLB and may return the page.
        assert!(unsafe { tables.detach_heap_page(0, owned.frames[1]) }.is_err());
        assert!(unsafe { tables.detach_heap_page(HEAP_INITIAL_PAGES, owned.frames[0]) }.is_err());
        for (index, frame) in owned.frames.iter().copied().enumerate().rev() {
            unsafe { tables.detach_heap_page(index, frame) }.unwrap();
            allocator.release(frame).unwrap();
        }
        assert!(tables.heap_window_unmapped());
        assert_eq!(allocator.remaining_pages(), 5);
    }

    #[test]
    fn gicr_table_mapping_owns_one_frame_and_keeps_neighbor_pages_invalid() {
        let mut backing = Box::new(HostTablePages([0; 3 * PAGE_SIZE as usize]));
        let base = backing.0.as_mut_ptr() as u64;
        let free = crate::memory::FreeMap::from_ram(base + PAGE_SIZE, 2 * PAGE_SIZE).unwrap();
        let mut allocator = FrameAllocator::new(free);
        let mut tables = Tables {
            root: 0,
            frames: [0; MAX_TABLE_COUNT],
            count: TABLE_COUNT,
            block_count: 0,
        };
        tables.frames[1] = base;
        // SAFETY: the test owns three aligned, writable host pages; the first
        // is a fake device L2, and the allocator owns the other two.
        unsafe {
            tables
                .map_device_window(&mut allocator, 0x080a_0000, 0x2_0000, 0x0900_0000)
                .unwrap();
        }
        assert_eq!(tables.frame_count(), TABLE_COUNT + 1);
        assert_eq!(allocator.remaining_pages(), 1);
        let l2 = base as *const u64;
        let l3 = (base + PAGE_SIZE) as *const u64;
        // SAFETY: indices are within the allocated, initialized host pages.
        unsafe {
            assert_eq!(*l2.add(64), table(base + PAGE_SIZE));
            assert_eq!(*l3.add(159), 0);
            assert_eq!(*l3.add(160), device_page(0x080a_0000));
            assert_eq!(*l3.add(191), device_page(0x080b_f000));
            assert_eq!(*l3.add(192), 0);
            assert_eq!(
                tables.map_device_window(&mut allocator, 0x080a_0000, 0x2_0000, 0x0900_0000),
                Err(Error::UnsupportedLayout)
            );
        }
        assert_eq!(
            allocator.remaining_pages(),
            1,
            "duplicate mapping leaked a table frame"
        );
    }

    #[test]
    fn tlb_probe_replacement_rejects_wrong_old_or_unsafe_frames() {
        let mut backing = Box::new(HostTablePages([0; 3 * PAGE_SIZE as usize]));
        let base = backing.0.as_mut_ptr() as u64;
        let mut tables = Tables {
            root: 0,
            frames: [0; MAX_TABLE_COUNT],
            count: TABLE_COUNT,
            block_count: 0,
        };
        tables.frames[4] = base;
        let old = RAM_BASE + 5 * PAGE_SIZE;
        let new = RAM_BASE + 6 * PAGE_SIZE;
        // SAFETY: the host test owns the aligned table page and its entry.
        unsafe {
            core::ptr::write_volatile((base as *mut u64).add(5), ram_page(old, false, false));
            let (slot, descriptor) = tables.probe_replacement(old, old, new).unwrap();
            assert_eq!(slot, (base as *mut u64).add(5));
            assert_eq!(descriptor, ram_page(new, false, false));
            for (va, before, after) in [
                (old, new, old),
                (old + 1, old, new),
                (old, old, RAM_BASE + MIB2),
                (old, old, old),
                (old, old, base),
            ] {
                assert_eq!(
                    tables.probe_replacement(va, before, after),
                    Err(Error::UnsupportedLayout)
                );
            }
        }
    }

    #[test]
    fn gicr_window_uses_exact_device_pages_and_rejects_aliases() {
        let plan = plan_device_window(0x080a_0000, 0x2_0000, 0x0900_0000).unwrap();
        assert_eq!((plan.l2, plan.first_page, plan.pages), (64, 160, 32));
        let descriptor = device_page(0x080a_0000);
        assert_eq!(descriptor & 3, VALID_TABLE_OR_PAGE);
        assert_ne!(descriptor & ATTR_DEVICE, 0);
        assert_ne!(descriptor & PXN, 0);
        assert_ne!(descriptor & UXN, 0);
        for (base, size) in [
            (0, 0x2_0000),
            (0x080a_0001, 0x2_0000),
            (0x080a_0000, 0),
            (0x081f_0000, 0x2_0000),
            (0x0900_0000, 0x2_0000),
            (RAM_BASE, 0x2_0000),
            (u64::MAX - PAGE_SIZE + 1, 0x2_0000),
        ] {
            assert!(plan_device_window(base, size, 0x0900_0000).is_none());
        }
    }

    fn layout() -> Layout {
        Layout {
            ram_base: RAM_BASE,
            ram_size: 256 * 1024 * 1024,
            uart_base: 0x0900_0000,
            image_start: 0x4008_0000,
            text_start: 0x4008_1000,
            text_end: 0x4009_0000,
            rodata_end: 0x4009_1000,
            image_end: 0x4009_f123,
            irq_guard_page: None,
            heap_start: None,
        }
    }

    #[test]
    fn k447_owned_live_roots_have_no_writable_executable_leaf() {
        let mut kernel_pages = Box::new(HostTablePages([0; 3 * PAGE_SIZE as usize]));
        let mut user_pages = Box::new(HostUserPages([0; 8 * PAGE_SIZE as usize]));
        let base = kernel_pages.0.as_mut_ptr() as u64;
        let private = user_pages.0.as_mut_ptr() as u64;
        let mut tables = Tables {
            root: base,
            frames: [0; MAX_TABLE_COUNT],
            count: 3,
            block_count: 1,
        };
        tables.frames[..3].copy_from_slice(&[base, base + PAGE_SIZE, base + 2 * PAGE_SIZE]);
        let user = UserSpace {
            root: private,
            frames: [
                private,
                private + PAGE_SIZE,
                private + 2 * PAGE_SIZE,
                private + 3 * PAGE_SIZE,
                private + 4 * PAGE_SIZE,
                private + 5 * PAGE_SIZE,
            ],
        };
        unsafe {
            write(base, 1, table(base + PAGE_SIZE));
            write(base + PAGE_SIZE, 0, table(base + 2 * PAGE_SIZE));
            write(base + PAGE_SIZE, 1, ram_block(RAM_BASE + MIB2));
            write(base + 2 * PAGE_SIZE, 0, ram_page(RAM_BASE, true, true));
            write(
                base + 2 * PAGE_SIZE,
                1,
                ram_page(RAM_BASE + PAGE_SIZE, false, false),
            );
            write(private, 1, table(base + PAGE_SIZE));
            write(private, 2, table(private + PAGE_SIZE));
            write(private + PAGE_SIZE, 0, table(private + 2 * PAGE_SIZE));
            write(
                private + 2 * PAGE_SIZE,
                0,
                (ram_page(user.code_frame(), true, true) | AP_EL0_ACCESS | NON_GLOBAL | PXN) & !UXN,
            );
            write(
                private + 2 * PAGE_SIZE,
                1,
                ram_page(user.data_frame(), false, false) | AP_EL0_ACCESS | NON_GLOBAL,
            );
        }
        assert_eq!(
            tables.audit_wx(None),
            Ok(WxAudit {
                tables: 3,
                leaves: 3
            })
        );
        assert_eq!(
            tables.audit_wx(Some(&user)),
            Ok(WxAudit {
                tables: 5,
                leaves: 5
            })
        );

        let kernel_data = ram_page(RAM_BASE + PAGE_SIZE, false, false);
        unsafe { write(base + 2 * PAGE_SIZE, 1, kernel_data & !PXN) };
        assert_eq!(
            tables.audit_wx(None),
            Err(WxAuditError::WritableExecutable(RAM_BASE + PAGE_SIZE))
        );
        unsafe { write(base + 2 * PAGE_SIZE, 1, kernel_data) };
        unsafe { write(base + PAGE_SIZE, 1, ram_block(RAM_BASE + MIB2) & !PXN) };
        assert_eq!(
            tables.audit_wx(None),
            Err(WxAuditError::WritableExecutable(RAM_BASE + MIB2))
        );
        unsafe { write(base + PAGE_SIZE, 1, ram_block(RAM_BASE + MIB2)) };

        let user_data = user.descriptor(1).unwrap();
        unsafe { write(private + 2 * PAGE_SIZE, 1, user_data & !UXN) };
        assert_eq!(
            tables.audit_wx(Some(&user)),
            Err(WxAuditError::WritableExecutable(USER_DATA_VA))
        );
        unsafe { write(private + 2 * PAGE_SIZE, 1, user_data) };
        let user_code = user.descriptor(0).unwrap();
        unsafe { write(private + 2 * PAGE_SIZE, 0, user_code & !AP_READ_ONLY) };
        assert_eq!(
            tables.audit_wx(Some(&user)),
            Err(WxAuditError::WritableExecutable(USER_CODE_VA))
        );
        unsafe { write(private + 2 * PAGE_SIZE, 0, user_code) };

        unsafe { write(private, 2, table(private + 6 * PAGE_SIZE)) };
        assert_eq!(
            tables.audit_wx(Some(&user)),
            Err(WxAuditError::UnknownTable(private + 6 * PAGE_SIZE))
        );
        unsafe { write(private, 2, table(private + PAGE_SIZE)) };
        unsafe { write(private + 2 * PAGE_SIZE, 1, (user_data & !3) | 2) };
        assert_eq!(
            tables.audit_wx(Some(&user)),
            Err(WxAuditError::InvalidDescriptor(USER_DATA_VA))
        );
        unsafe { write(private + 2 * PAGE_SIZE, 1, user_data) };
        assert_eq!(
            tables.audit_wx(Some(&user)),
            Ok(WxAudit {
                tables: 5,
                leaves: 5
            })
        );
    }

    #[test]
    fn descriptor_kinds_and_w_x_are_distinct() {
        let code = ram_page(0x4008_0000, true, true);
        let data = ram_page(0x4009_1000, false, false);
        let uart = device_page(0x0900_0000);
        assert_eq!(code & 3, 3);
        assert_eq!(ram_block(0x4020_0000) & 3, 1);
        assert_eq!(table(0x4000_1000) & 3, 3);
        assert_eq!(code & PXN, 0);
        assert_ne!(code & AP_READ_ONLY, 0);
        assert_ne!(data & PXN, 0);
        assert_eq!(data & AP_READ_ONLY, 0);
        assert_eq!(uart & (7 << 2), ATTR_DEVICE);
        assert_eq!(code & (7 << 2), ATTR_NORMAL);
        assert_ne!(uart & (PXN | UXN), 0);
    }

    #[test]
    fn early_identity_descriptors_never_grant_el0_access() {
        for descriptor in [
            ram_page_descriptor(layout(), layout().text_start, &[]),
            ram_page_descriptor(layout(), layout().rodata_end, &[]),
            ram_block(RAM_BASE + 2 * MIB2),
            device_page(layout().uart_base),
        ] {
            assert_eq!(descriptor & AP_EL0_ACCESS, 0);
            assert_eq!(descriptor & NON_GLOBAL, 0);
        }
    }

    #[test]
    fn linker_header_text_rodata_and_data_have_distinct_permissions() {
        let header = ram_page_descriptor(layout(), layout().image_start, &[]);
        let text = ram_page_descriptor(layout(), layout().text_start, &[]);
        let rodata = ram_page_descriptor(layout(), layout().text_end, &[]);
        let data = ram_page_descriptor(layout(), layout().rodata_end, &[]);
        assert_ne!(header & AP_READ_ONLY, 0);
        assert_ne!(header & PXN, 0);
        assert_ne!(text & AP_READ_ONLY, 0);
        assert_eq!(text & PXN, 0);
        assert_ne!(rodata & AP_READ_ONLY, 0);
        assert_ne!(rodata & PXN, 0);
        assert_eq!(data & AP_READ_ONLY, 0);
        assert_ne!(data & PXN, 0);
    }

    #[test]
    fn invalid_no_map_page_has_no_access_permissions() {
        let hole = [Reservation {
            start: RAM_BASE + MIB2 + PAGE_SIZE,
            size: PAGE_SIZE,
            no_map: true,
        }];
        let descriptor = ram_page_descriptor(layout(), hole[0].start, &hole);
        assert_eq!(descriptor, 0);
        assert_eq!(descriptor & (AP_READ_ONLY | ACCESS_FLAG | PXN | UXN), 0);
        assert_ne!(
            ram_page_descriptor(layout(), hole[0].start + PAGE_SIZE, &hole),
            0
        );
    }

    #[test]
    fn image_end_guard_is_invalid_and_adjacent_ram_remains_mapped() {
        let guard = (layout().image_end + PAGE_SIZE - 1) & !(PAGE_SIZE - 1);
        assert_eq!(ram_page_descriptor(layout(), guard, &[]), 0);
        assert_ne!(ram_page_descriptor(layout(), guard - PAGE_SIZE, &[]), 0);
        assert_ne!(ram_page_descriptor(layout(), guard + PAGE_SIZE, &[]), 0);
        assert_eq!(layout().validate(), Ok(()));
        assert_eq!(
            Layout {
                image_end: RAM_BASE + MIB2,
                ..layout()
            }
            .validate(),
            Err(Error::UnsupportedLayout)
        );
    }

    #[test]
    fn irq_lower_guard_page_is_unmapped_but_stack_page_is_writable() {
        let layout = Layout {
            irq_guard_page: Some(0x4009_a000),
            ..layout()
        };
        assert_eq!(layout.validate(), Ok(()));
        assert_ne!(ram_page_descriptor(layout, 0x4009_9000, &[]), 0);
        assert_eq!(ram_page_descriptor(layout, 0x4009_a000, &[]), 0);
        assert_ne!(ram_page_descriptor(layout, 0x4009_b000, &[]), 0);
        for bad_guard in [0x4009_a001, 0x4009_0000, 0x4009_f000, u64::MAX] {
            assert_eq!(
                Layout {
                    irq_guard_page: Some(bad_guard),
                    ..layout
                }
                .validate(),
                Err(Error::UnsupportedLayout)
            );
        }
    }

    #[test]
    fn access_flag_shareability_and_mair_indices_are_consistent() {
        let page = ram_page(RAM_BASE + MIB2 + PAGE_SIZE, false, false);
        let block = ram_block(RAM_BASE + 2 * MIB2);
        let device = device_page(0x0900_0000);
        for descriptor in [page, block, device] {
            assert_ne!(descriptor & ACCESS_FLAG, 0);
        }
        assert_eq!(page & SHARE_INNER, SHARE_INNER);
        assert_eq!(block & SHARE_INNER, SHARE_INNER);
        assert_eq!(device & SHARE_INNER, 0);
        assert_eq!(page & (7 << 2), ATTR_NORMAL);
        assert_eq!(block & (7 << 2), ATTR_NORMAL);
        assert_eq!(device & (7 << 2), ATTR_DEVICE);
        assert_eq!(MAIR_EL1 & 0xff, 0xff);
        assert_eq!((MAIR_EL1 >> 8) & 0xff, 0x00);
    }

    #[test]
    fn page_and_block_descriptors_preserve_physical_address_bits() {
        let address = RAM_BASE + MIB2 + 3 * PAGE_SIZE;
        let page = ram_page_descriptor(layout(), address, &[]);
        assert_eq!(page & 0x0000_ffff_ffff_f000, address);
        assert_eq!(page & 0b11, VALID_TABLE_OR_PAGE);
        let block_address = RAM_BASE + 2 * MIB2;
        let block = ram_block(block_address);
        assert_eq!(block & 0x0000_ffff_ffe0_0000, block_address);
        assert_eq!(block & 0b11, VALID_BLOCK);
    }

    #[test]
    fn layout_rejects_unmapped_or_misaligned_ranges() {
        assert_eq!(layout().validate(), Ok(()));
        assert_eq!(
            Layout {
                ram_size: GIB + MIB2,
                ..layout()
            }
            .validate(),
            Err(Error::UnsupportedLayout)
        );
        assert_eq!(
            Layout {
                text_end: 0x4009_0001,
                ..layout()
            }
            .validate(),
            Err(Error::UnsupportedLayout)
        );
        assert_eq!(
            Layout {
                text_start: 0x4008_0001,
                ..layout()
            }
            .validate(),
            Err(Error::UnsupportedLayout)
        );
        assert_eq!(
            Layout {
                image_end: RAM_BASE + MIB2 + 1,
                ..layout()
            }
            .validate(),
            Err(Error::UnsupportedLayout)
        );
        assert_eq!(
            Layout {
                uart_base: GIB,
                ..layout()
            }
            .validate(),
            Err(Error::UnsupportedLayout)
        );
    }

    #[test]
    fn tcr_rejects_unsupported_address_width() {
        assert_eq!(
            tcr_el1(2),
            Some(25 | (1 << 8) | (1 << 10) | (3 << 12) | (1 << 23) | (2 << 32))
        );
        assert_eq!(tcr_el1(6), None);
        assert_eq!(MAIR_EL1, 0xff);
    }

    #[test]
    fn no_map_hole_rounds_outward_and_keeps_neighbor() {
        let hole = [Reservation {
            start: RAM_BASE + 1,
            size: PAGE_SIZE - 1,
            no_map: true,
        }];
        assert_eq!(layout().validate_no_map(&hole), Ok(()));
        assert_eq!(ram_page_descriptor(layout(), RAM_BASE, &hole), 0);
        assert_ne!(
            ram_page_descriptor(layout(), RAM_BASE + PAGE_SIZE, &hole),
            0
        );
        assert_ne!(
            ram_page_descriptor(
                layout(),
                RAM_BASE,
                &[Reservation {
                    no_map: false,
                    ..hole[0]
                }]
            ),
            0
        );
    }

    #[test]
    fn no_map_edge_crosses_l2_boundary_without_hiding_neighbor() {
        let hole = [Reservation {
            start: RAM_BASE + MIB2 - 1,
            size: 2,
            no_map: true,
        }];
        let (split, count) = split_blocks(layout(), &hole).unwrap();
        assert_eq!(count, 1);
        assert!(split[1]);
        assert_eq!(
            ram_page_descriptor(layout(), RAM_BASE + MIB2 - PAGE_SIZE, &hole),
            0
        );
        assert_eq!(ram_page_descriptor(layout(), RAM_BASE + MIB2, &hole), 0);
        assert_ne!(
            ram_page_descriptor(layout(), RAM_BASE + MIB2 + PAGE_SIZE, &hole),
            0
        );
    }

    #[test]
    fn distant_no_map_splits_only_touched_blocks() {
        let hole = [Reservation {
            start: RAM_BASE + MIB2 + PAGE_SIZE,
            size: PAGE_SIZE,
            no_map: true,
        }];
        let (split, count) = split_blocks(layout(), &hole).unwrap();
        assert_eq!(count, 1);
        assert!(split[1]);
        assert!(!split[2]);
        assert_eq!(ram_page_descriptor(layout(), hole[0].start, &hole), 0);
        assert_ne!(
            ram_page_descriptor(layout(), hole[0].start - PAGE_SIZE, &hole),
            0
        );
        assert_ne!(
            ram_page_descriptor(layout(), hole[0].start + PAGE_SIZE, &hole),
            0
        );
        let ordinary = [Reservation {
            no_map: false,
            ..hole[0]
        }];
        assert_eq!(split_blocks(layout(), &ordinary).unwrap().1, 0);
    }

    #[test]
    fn two_no_map_pages_in_one_block_share_one_l3_table() {
        let holes = [
            Reservation {
                start: RAM_BASE + MIB2 + PAGE_SIZE,
                size: PAGE_SIZE,
                no_map: true,
            },
            Reservation {
                start: RAM_BASE + MIB2 + 3 * PAGE_SIZE,
                size: PAGE_SIZE,
                no_map: true,
            },
        ];
        let (split, count) = split_blocks(layout(), &holes).unwrap();
        assert_eq!(count, 1);
        assert_eq!(TABLE_COUNT + count, 6);
        assert!(split[1]);
        assert!(!split[2]);
        assert_eq!(ram_page_descriptor(layout(), holes[0].start, &holes), 0);
        assert_eq!(ram_page_descriptor(layout(), holes[1].start, &holes), 0);
        assert_ne!(
            ram_page_descriptor(layout(), RAM_BASE + MIB2 + 2 * PAGE_SIZE, &holes),
            0
        );
    }

    #[test]
    fn no_map_pages_in_two_blocks_require_two_extra_l3_tables() {
        let holes = [
            Reservation {
                start: RAM_BASE + MIB2 + PAGE_SIZE,
                size: PAGE_SIZE,
                no_map: true,
            },
            Reservation {
                start: RAM_BASE + 2 * MIB2 + PAGE_SIZE,
                size: PAGE_SIZE,
                no_map: true,
            },
        ];
        let (split, count) = split_blocks(layout(), &holes).unwrap();
        assert_eq!(count, 2);
        assert_eq!(TABLE_COUNT + count, 7);
        assert!(split[1] && split[2]);
        assert!(!split[3]);
        for hole in &holes {
            assert_eq!(ram_page_descriptor(layout(), hole.start, &holes), 0);
            assert_ne!(
                ram_page_descriptor(layout(), hole.start + PAGE_SIZE, &holes),
                0
            );
        }
    }

    #[test]
    fn full_no_map_block_has_no_live_page_descriptors() {
        let hole = [Reservation {
            start: RAM_BASE + MIB2,
            size: MIB2,
            no_map: true,
        }];
        let (split, count) = split_blocks(layout(), &hole).unwrap();
        assert_eq!(count, 1);
        assert!(split[1]);
        assert!(!split[2]);
        for page in 0..ENTRIES {
            assert_eq!(
                ram_page_descriptor(layout(), hole[0].start + page as u64 * PAGE_SIZE, &hole),
                0
            );
        }
        assert_ne!(
            ram_page_descriptor(layout(), RAM_BASE + MIB2 - PAGE_SIZE, &hole),
            0
        );
        assert_ne!(ram_page_descriptor(layout(), RAM_BASE + 2 * MIB2, &hole), 0);
    }

    #[test]
    fn too_many_split_blocks_fail_closed() {
        let hole = [Reservation {
            start: RAM_BASE + MIB2,
            size: (MAX_EXTRA_L3 as u64 + 1) * MIB2,
            no_map: true,
        }];
        assert!(matches!(
            split_blocks(layout(), &hole),
            Err(Error::UnsupportedLayout)
        ));
    }

    #[test]
    fn table_allocation_failure_returns_all_owned_frames() {
        let mut allocator =
            FrameAllocator::new(crate::memory::FreeMap::from_ram(RAM_BASE, 6 * PAGE_SIZE).unwrap());
        assert_eq!(allocator.remaining_pages(), 6);
        assert!(matches!(
            allocate_table_frames(&mut allocator, 7),
            Err(Error::OutOfFrames)
        ));
        assert_eq!(allocator.remaining_pages(), 6);
        let frames = allocate_table_frames(&mut allocator, 6).unwrap();
        assert_eq!(frames[0], RAM_BASE);
        assert_eq!(frames[5], RAM_BASE + 5 * PAGE_SIZE);
    }

    #[test]
    fn no_map_rejects_unrepresentable_or_live_regions() {
        for (start, size) in [
            (layout().image_start, PAGE_SIZE),
            (layout().image_end, 1),
            (layout().uart_base, PAGE_SIZE),
            (RAM_BASE, 0),
        ] {
            assert_eq!(
                layout().validate_no_map(&[Reservation {
                    start,
                    size,
                    no_map: true
                }]),
                Err(Error::UnsupportedLayout)
            );
        }
        assert_eq!(
            layout().validate_no_map(&[Reservation {
                start: u64::MAX - 1,
                size: PAGE_SIZE,
                no_map: true,
            }]),
            Err(Error::UnsupportedLayout)
        );
    }
}