rust-kernel

//! Paging: page tables, address translation and a physical frame allocator.
//!
//! x86_64 uses 4-level page tables (L4 -> L3 -> L2 -> L1 -> 4 KiB page).
//! CR3 holds the *physical* address of the active level-4 table. But the CPU
//! (and our code) only uses *virtual* addresses, so to read or edit a page
//! table we need it mapped somewhere. The bootloader's `map_physical_memory`
//! feature maps all of physical RAM at `physical_memory_offset`, so
//!     virtual address = physical_memory_offset + physical address.
//! `OffsetPageTable` from the x86_64 crate implements exactly that.
//!
//! Address spaces (for user processes): every process gets its own level-4
//! table. Its entries are copied from the kernel's level-4 table, so the
//! kernel (code, heap, stacks, the physical-memory window) is mapped
//! identically everywhere -- just *without* the USER_ACCESSIBLE flag, so ring
//! 3 code can't touch it. User code and stack go into L4 slot 1
//! (`USER_START..USER_END`), which the kernel doesn't use. Switching CR3 then
//! swaps only the user part. (Linux does the same with the upper half; our
//! bootloader put the kernel in the *lower* half, so we use a free slot.)

use alloc::collections::BTreeMap;
use bootloader::bootinfo::{MemoryMap, MemoryRegionType};
use core::sync::atomic::{AtomicU64, Ordering};
use spin::Mutex;
use x86_64::instructions::interrupts::without_interrupts;
use x86_64::{
    PhysAddr, VirtAddr,
    registers::control::Cr3,
    structures::paging::{
        FrameAllocator, Mapper, OffsetPageTable, Page, PageTable, PageTableFlags, PhysFrame,
        Size4KiB, Translate, mapper::TranslateResult,
    },
};

/// User space: from 4 MiB (where `gcc -static` puts a program, 0x400000)
/// to 1 TiB, i.e. level-4 slots 0 and 1. The first 2 MiB of slot 0 stay the
/// kernel's (VGA text buffer at 0xb8000, the SMP trampoline at 0x8000, the
/// bootloader's tables): every address space shares that one kernel-only
/// table. 2..4 MiB is a gap, so a NULL pointer plus a big offset still faults.
pub const USER_START: u64 = 0x0000_0000_0040_0000;
pub const USER_END: u64 = 0x0000_0100_0000_0000; // exclusive
/// The level-4 slots holding user space (slot 0 only partly, see above).
const USER_L4_SLOTS: [usize; 2] = [0, 1];
/// Slot 1 is user-only: the kernel must never map anything there.
const USER_L4_INDEX: usize = 1;
/// End of the kernel's low identity-mapped area in slot 0 (one L2 entry).
const LOW_KERNEL_END: u64 = 0x20_0000;

/// Where all physical memory is mapped (set by `init`).
static PHYS_OFFSET: AtomicU64 = AtomicU64::new(0);
/// Physical address of the kernel's (boot) level-4 table (set by `init`).
static KERNEL_L4: AtomicU64 = AtomicU64::new(0);
/// The frame allocator, once `init_frame_allocator` hands it over.
static FRAME_ALLOCATOR: Mutex<Option<BootInfoFrameAllocator>> = Mutex::new(None);

/// Create an `OffsetPageTable` for the currently active page tables.
///
/// Unsafe: the caller must guarantee that all physical memory really is
/// mapped at `physical_memory_offset`, and must call this only once (two
/// `&mut` to the same page table would be undefined behaviour).
pub unsafe fn init(physical_memory_offset: VirtAddr) -> OffsetPageTable<'static> {
    PHYS_OFFSET.store(physical_memory_offset.as_u64(), Ordering::Relaxed);
    KERNEL_L4.store(Cr3::read().0.start_address().as_u64(), Ordering::Relaxed);
    // CR0.WP: read-only pages are read-only for the kernel too. Without it
    // a kernel write into a copy-on-write page would silently change the
    // frame that parent and child share. (The bootloader sets it already;
    // this makes sure. The other CPUs copy our CR0 in smp.rs.)
    unsafe {
        use x86_64::registers::control::{Cr0, Cr0Flags};
        Cr0::update(|flags| flags.insert(Cr0Flags::WRITE_PROTECT));
    }
    unsafe {
        let level_4_table = active_level_4_table(physical_memory_offset);
        OffsetPageTable::new(level_4_table, physical_memory_offset)
    }
}

/// Find the active level-4 table via CR3 and return a reference to it.
unsafe fn active_level_4_table(physical_memory_offset: VirtAddr) -> &'static mut PageTable {
    let (level_4_table_frame, _flags) = Cr3::read();
    let phys = level_4_table_frame.start_address();
    let virt = physical_memory_offset + phys.as_u64();
    let page_table_ptr: *mut PageTable = virt.as_mut_ptr();
    unsafe { &mut *page_table_ptr }
}

/// Demo: map the virtual page containing `page` to the VGA text buffer's
/// physical frame (0xb8000). Writing through that page then shows on screen.
pub fn create_example_mapping(
    page: Page,
    mapper: &mut OffsetPageTable,
    frame_allocator: &mut impl FrameAllocator<Size4KiB>,
) {
    let frame = PhysFrame::containing_address(PhysAddr::new(0xb8000));
    let flags = PageTableFlags::PRESENT | PageTableFlags::WRITABLE;

    // Unsafe because mapping the same frame twice could create aliasing
    // `&mut`s. Fine here: it's only the VGA buffer, for a demo.
    // `map_to` may need new page tables (L3/L2/L1) -> takes a frame allocator.
    let map_to_result = unsafe { mapper.map_to(page, frame, flags, frame_allocator) };
    // `flush` removes the stale entry from the TLB (the CPU's mapping cache).
    map_to_result.expect("map_to failed").flush();
}

/// Hands out unused physical 4 KiB frames, taken from the memory map the
/// bootloader got from the BIOS (E820). Very simple: it never frees, and
/// walks the map from the start on every call (fine for now).
pub struct BootInfoFrameAllocator {
    memory_map: &'static MemoryMap,
    next: usize, // how many frames we've handed out so far
}

impl BootInfoFrameAllocator {
    /// Unsafe: the caller must guarantee that every frame marked `Usable` in
    /// the memory map really is unused.
    pub unsafe fn init(memory_map: &'static MemoryMap) -> Self {
        BootInfoFrameAllocator { memory_map, next: 0 }
    }

    /// All usable frames, in order.
    fn usable_frames(&self) -> impl Iterator<Item = PhysFrame> {
        self.memory_map
            .iter()
            .filter(|r| r.region_type == MemoryRegionType::Usable) // only free RAM
            .map(|r| r.range.start_addr()..r.range.end_addr()) // -> address ranges
            .flat_map(|r| r.step_by(4096)) // -> each frame's start address
            .map(|addr| PhysFrame::containing_address(PhysAddr::new(addr)))
    }
}

unsafe impl FrameAllocator<Size4KiB> for BootInfoFrameAllocator {
    fn allocate_frame(&mut self) -> Option<PhysFrame> {
        let frame = self.usable_frames().nth(self.next);
        self.next += 1;
        frame
    }
}

/// Total usable RAM in bytes, according to the memory map (for printing).
pub fn usable_memory_bytes(memory_map: &MemoryMap) -> u64 {
    memory_map
        .iter()
        .filter(|r| r.region_type == MemoryRegionType::Usable)
        .map(|r| r.range.end_addr() - r.range.start_addr())
        .sum()
}

// ---------------------------------------------------------------------------
// Global frame allocator + per-process address spaces
// ---------------------------------------------------------------------------

/// Hand the frame allocator over to the kernel (after the heap is set up),
/// so processes can get page tables and pages later.
pub fn init_frame_allocator(frame_allocator: BootInfoFrameAllocator) {
    // For sysinfo/statfs (stage 17): how much RAM there is, and how much of
    // it was gone (kernel heap, early page tables) before the hand-over.
    TOTAL_FRAMES.store(usable_memory_bytes(frame_allocator.memory_map) / 4096, Ordering::Relaxed);
    EARLY_FRAMES.store(frame_allocator.next as u64, Ordering::Relaxed);
    without_interrupts(|| *FRAME_ALLOCATOR.lock() = Some(frame_allocator));
    init_kernel_stack_area(); // must happen before any process exists
    crate::vdso::init(); // stage 19: the vDSO's frames, before any process too
}

/// Frames given back with `free_frame`, as a linked list threaded through
/// the free frames themselves: the first 8 bytes of each free frame hold the
/// physical address of the next one (0 = end). No heap memory needed.
struct FreeList {
    head: u64,
    len: usize,
}
static FREE_FRAMES: Mutex<FreeList> = Mutex::new(FreeList { head: 0, len: 0 });
/// Frames handed out by the boot allocator so far (for statistics).
static BOOT_FRAMES_USED: AtomicU64 = AtomicU64::new(0);

/// One physical frame (contents undefined), or None if out of memory / not
/// initialized. Recycled frames first, then fresh ones from the memory map.
///
/// The frame locks are only ever taken with interrupts off (see the locking
/// rule in thread.rs): the scheduler and interrupt handlers free frames too.
pub fn alloc_frame() -> Option<PhysFrame> {
    without_interrupts(|| {
        {
            let mut free = FREE_FRAMES.lock();
            if free.head != 0 {
                let frame = PhysFrame::containing_address(PhysAddr::new(free.head));
                free.head = unsafe { *phys_to_virt(frame.start_address()).as_ptr::<u64>() };
                free.len -= 1;
                return Some(frame);
            }
        }
        fresh_frame()
    })
}

/// A never-used frame straight from the boot allocator.
fn fresh_frame() -> Option<PhysFrame> {
    let frame = without_interrupts(|| FRAME_ALLOCATOR.lock().as_mut()?.allocate_frame())?;
    BOOT_FRAMES_USED.fetch_add(1, Ordering::Relaxed);
    Some(frame)
}

/// Give a frame back. The caller promises nothing uses it any more (no page
/// table maps it, no device writes to it).
pub fn free_frame(frame: PhysFrame) {
    without_interrupts(|| {
        let mut free = FREE_FRAMES.lock();
        unsafe { *phys_to_virt(frame.start_address()).as_mut_ptr::<u64>() = free.head };
        free.head = frame.start_address().as_u64();
        free.len += 1;
    })
}

/// Usable RAM in 4 KiB frames, and frames used before `init_frame_allocator`.
static TOTAL_FRAMES: AtomicU64 = AtomicU64::new(0);
static EARLY_FRAMES: AtomicU64 = AtomicU64::new(0);

/// (total, free) RAM in 4 KiB frames, for sysinfo and the ramfs's statfs.
pub fn frame_totals() -> (u64, u64) {
    let total = TOTAL_FRAMES.load(Ordering::Relaxed);
    let used = EARLY_FRAMES.load(Ordering::Relaxed) + frames_in_use() as u64;
    (total, total.saturating_sub(used))
}

/// How many frames are in use right now (handed out and not freed).
pub fn frames_in_use() -> usize {
    without_interrupts(|| BOOT_FRAMES_USED.load(Ordering::Relaxed) as usize - FREE_FRAMES.lock().len)
}

/// `FrameAllocator` adapter around the global allocator (for `map_to`, which
/// may need frames for new page tables).
struct GlobalFrameAllocator;

unsafe impl FrameAllocator<Size4KiB> for GlobalFrameAllocator {
    fn allocate_frame(&mut self) -> Option<PhysFrame> {
        alloc_frame()
    }
}

/// Virtual address through which the kernel can reach physical address `phys`.
pub fn phys_to_virt(phys: PhysAddr) -> VirtAddr {
    VirtAddr::new(PHYS_OFFSET.load(Ordering::Relaxed) + phys.as_u64())
}

/// The kernel's level-4 table frame (what kernel threads run with).
pub fn kernel_l4_frame() -> PhysFrame {
    match KERNEL_L4.load(Ordering::Relaxed) {
        0 => Cr3::read().0, // `init` not called yet: we're still on the boot tables
        addr => PhysFrame::containing_address(PhysAddr::new(addr)),
    }
}

/// Does the CPU honour the NO_EXECUTE page flag? (EFER.NXE, which our
/// bootloader turns on. With it off, setting the bit would be an error.)
pub fn nx_enabled() -> bool {
    use x86_64::registers::model_specific::{Efer, EferFlags};
    Efer::read().contains(EferFlags::NO_EXECUTE_ENABLE)
}

/// `count` physically *contiguous*, zeroed frames (device DMA buffers like
/// virtio queues must be contiguous in physical memory). Our allocator hands
/// out frames in address order, so consecutive frames are usually adjacent;
/// if a run gets broken (end of a memory region) we start over and simply
/// leak the frames we skipped. Fine for a few boot-time allocations.
pub fn alloc_contiguous_frames(count: usize) -> Option<PhysAddr> {
    // Fresh frames only: recycled ones come back in no particular order.
    let mut start = fresh_frame()?.start_address();
    let mut got = 1;
    while got < count {
        let frame = fresh_frame()?.start_address();
        if frame == start + (got as u64) * 4096 {
            got += 1;
        } else {
            start = frame; // not adjacent: restart the run here
            got = 1;
        }
    }
    let ptr: *mut u8 = phys_to_virt(start).as_mut_ptr();
    unsafe { core::ptr::write_bytes(ptr, 0, count * 4096) };
    Some(start)
}

/// A frame filled with zeros (new page tables and user pages must not leak
/// old data).
pub fn alloc_zeroed_frame() -> Option<PhysFrame> {
    let frame = alloc_frame()?;
    let ptr: *mut u8 = phys_to_virt(frame.start_address()).as_mut_ptr();
    unsafe { core::ptr::write_bytes(ptr, 0, 4096) };
    Some(frame)
}

/// Page-table view of the address space whose level-4 table is `l4`.
///
/// Unsafe: the caller must not create two of these for the same table at the
/// same time (both would hand out `&mut` to the same memory).
unsafe fn mapper_for(l4: PhysFrame) -> OffsetPageTable<'static> {
    let table: *mut PageTable = phys_to_virt(l4.start_address()).as_mut_ptr();
    let offset = VirtAddr::new(PHYS_OFFSET.load(Ordering::Relaxed));
    unsafe { OffsetPageTable::new(&mut *table, offset) }
}

/// Create a new address space: a fresh level-4 table that shares all kernel
/// mappings (entries copied from the kernel's table) and has an empty user part.
pub fn new_address_space() -> Option<PhysFrame> {
    let frame = alloc_zeroed_frame()?;
    unsafe {
        let new: &mut PageTable = &mut *phys_to_virt(frame.start_address()).as_mut_ptr();
        let kernel: &PageTable = &*phys_to_virt(kernel_l4_frame().start_address()).as_ptr();
        // The kernel must not use our user slot, or user mappings would end up
        // in page tables shared with the kernel (and every other process).
        assert!(kernel[USER_L4_INDEX].is_unused(), "kernel uses the user L4 slot");
        for i in 1..512 {
            new[i] = kernel[i].clone();
        }
    }
    // Slot 0 is shared between the kernel (first 2 MiB) and the user (the
    // rest), so it gets its own level-3 and level-2 tables; only the kernel's
    // first level-2 entry (0..2 MiB, not USER_ACCESSIBLE) is copied in.
    let Some(l3) = alloc_zeroed_frame() else {
        free_frame(frame);
        return None;
    };
    let Some(l2) = alloc_zeroed_frame() else {
        free_frame(l3);
        free_frame(frame);
        return None;
    };
    table_mut(l2)[0] = kernel_low_l2_entry();
    table_mut(l3)[0].set_frame(l2, USER_TABLE_FLAGS);
    table_mut(frame)[0].set_frame(l3, USER_TABLE_FLAGS);
    Some(frame)
}

/// The kernel's level-2 entry for 0..2 MiB. Checks that the kernel maps
/// nothing else in slot 0 (that part belongs to user programs now: the
/// kernel image itself is linked at 0x200_0000_0000, see the target JSON).
fn kernel_low_l2_entry() -> x86_64::structures::paging::page_table::PageTableEntry {
    let kernel = table_mut(kernel_l4_frame());
    let l3 = table_mut(kernel[0].frame().expect("kernel slot 0 has no level-3 table"));
    assert!(l3.iter().skip(1).all(|e| e.is_unused()), "kernel maps memory in user space (slot 0)");
    let l2 = table_mut(l3[0].frame().expect("kernel slot 0 has no level-2 table"));
    let low = (LOW_KERNEL_END >> 21) as usize;
    assert!(l2.iter().skip(low).all(|e| e.is_unused()), "kernel maps memory in user space (below 1 GiB)");
    l2[0].clone()
}

/// Where the 2 MiB covered by level-2 entry `[i4][i3][i2]` starts.
fn l2_base(i4: usize, i3: usize, i2: usize) -> u64 {
    ((i4 as u64) << 39) | ((i3 as u64) << 30) | ((i2 as u64) << 21)
}

/// Free everything a process's address space owns: every user page's frame
/// (or just our share of it, see `release_frame`), the page tables of the
/// user slot (levels 3, 2, 1) and the level-4 table. The kernel entries
/// are shared with every other address space, so they're left alone.
///
/// Unsafe: `l4` must not be in use by any thread (not loaded in CR3, and the
/// thread that ran in it must have finished).
pub unsafe fn free_address_space(l4: PhysFrame) {
    clear_user_space(l4);
    // What clear_user_space keeps: slot 0's own level-3 and level-2 tables.
    let entry = &mut table_mut(l4)[0];
    if let Ok(l3) = entry.frame() {
        if let Ok(l2) = table_mut(l3)[0].frame() {
            free_frame(l2);
        }
        free_frame(l3);
    }
    entry.set_unused();
    free_frame(l4);
}

/// A page table, reached through the physical-memory map.
fn table_mut(frame: PhysFrame) -> &'static mut PageTable {
    unsafe { &mut *phys_to_virt(frame.start_address()).as_mut_ptr() }
}

/// Remove the whole user part of address space `l4` (execve does this to
/// the running process: the caller must flush the TLB afterwards). The
/// level-4 table itself stays.
pub fn clear_user_space(l4: PhysFrame) {
    // User space only has 4 KiB pages (no huge ones). In slot 0 the kernel's
    // low entry (0..2 MiB) is skipped, and slot 0's own level-3 table and
    // first level-2 table stay (free_address_space frees them).
    for i4 in USER_L4_SLOTS {
        let Ok(l3) = table_mut(l4)[i4].frame() else { continue };
        for (i3, e3) in table_mut(l3).iter_mut().enumerate().filter(|(_, e)| !e.is_unused()) {
            let Ok(l2) = e3.frame() else { continue };
            for (i2, e2) in table_mut(l2).iter_mut().enumerate().filter(|(_, e)| !e.is_unused()) {
                if l2_base(i4, i3, i2) < USER_START {
                    continue; // the kernel's
                }
                if let Ok(l1) = e2.frame() {
                    for e1 in table_mut(l1).iter().filter(|e| !e.is_unused()) {
                        if let Ok(page) = e1.frame() {
                            release_frame(page);
                        }
                    }
                    free_frame(l1);
                }
                e2.set_unused();
            }
            if (i4, i3) != (0, 0) {
                free_frame(l2);
                e3.set_unused();
            }
        }
        if i4 != 0 {
            free_frame(l3);
            table_mut(l4)[i4].set_unused();
        }
    }
}

// ---------------------------------------------------------------------------
// Shared frames (copy-on-write and shared memory)
// ---------------------------------------------------------------------------
//
// After fork, parent and child map the *same* frames until one of them
// writes (copy-on-write); MAP_SHARED memory is mapped by several processes
// for good. A frame may only be freed when the last of them lets go, so
// shared frames carry a reference count. Most frames are never shared, so
// instead of a counter for every frame of RAM (Linux's `struct page`) we
// keep a small map with only the shared ones: no entry = one owner.

/// Physical address -> number of owners (always >= 2). Locked with
/// interrupts off (frames are released in the scheduler, see thread.rs).
static SHARED_FRAMES: Mutex<BTreeMap<u64, u32>> = Mutex::new(BTreeMap::new());

/// One more address space maps `frame`.
pub fn share_frame(frame: PhysFrame) {
    without_interrupts(|| {
        let mut shared = SHARED_FRAMES.lock();
        let count = shared.entry(frame.start_address().as_u64()).or_insert(1);
        *count += 1;
    })
}

/// How many address spaces map `frame` (1 if it isn't shared).
pub fn frame_refcount(frame: PhysFrame) -> u32 {
    without_interrupts(|| SHARED_FRAMES.lock().get(&frame.start_address().as_u64()).copied().unwrap_or(1))
}

/// An address space stops using `frame`: free it if that was the last one.
pub fn release_frame(frame: PhysFrame) {
    let last = without_interrupts(|| {
        let mut shared = SHARED_FRAMES.lock();
        let addr = frame.start_address().as_u64();
        match shared.get_mut(&addr) {
            Some(count) => {
                *count -= 1;
                if *count == 1 {
                    shared.remove(&addr); // one owner left: no entry needed
                }
                false
            }
            None => true,
        }
    });
    if last {
        free_frame(frame);
    }
}

/// Number of frames with more than one owner right now (for tests).
pub fn shared_frame_count() -> usize {
    without_interrupts(|| SHARED_FRAMES.lock().len())
}

// ---------------------------------------------------------------------------
// User page-table entries, one page at a time (mm.rs decides what goes where)
// ---------------------------------------------------------------------------

/// Flags for the L3/L2/L1 tables above user pages: always present, writable
/// and user-accessible. The *leaf* entry alone decides what's allowed (the
/// CPU combines all levels, so the upper ones must allow everything).
const USER_TABLE_FLAGS: PageTableFlags =
    PageTableFlags::PRESENT.union(PageTableFlags::WRITABLE).union(PageTableFlags::USER_ACCESSIBLE);

fn user_page(addr: u64) -> Page<Size4KiB> {
    assert!((USER_START..USER_END).contains(&addr), "not a user address");
    Page::containing_address(VirtAddr::new(addr))
}

/// The frame and flags mapped at user address `addr` in `l4`, if any.
pub fn user_pte(l4: PhysFrame, addr: u64) -> Option<(PhysFrame, PageTableFlags)> {
    let mapper = unsafe { mapper_for(l4) };
    match mapper.translate(VirtAddr::new(addr & !0xfff)) {
        TranslateResult::Mapped { frame, flags, .. } => {
            Some((PhysFrame::containing_address(frame.start_address()), flags))
        }
        _ => None,
    }
}

/// Map `frame` at user address `addr` (must be unmapped) with `flags`.
pub fn map_user_frame(l4: PhysFrame, addr: u64, frame: PhysFrame, flags: PageTableFlags) -> Option<()> {
    let mut mapper = unsafe { mapper_for(l4) };
    let page = user_page(addr);
    unsafe { mapper.map_to_with_table_flags(page, frame, flags, USER_TABLE_FLAGS, &mut GlobalFrameAllocator).ok()?.ignore() };
    Some(())
}

/// Change the flags of the page at `addr` (must be mapped).
pub fn set_user_pte_flags(l4: PhysFrame, addr: u64, flags: PageTableFlags) {
    let mut mapper = unsafe { mapper_for(l4) };
    if let Ok(flush) = unsafe { mapper.update_flags(user_page(addr), flags) } {
        flush.ignore(); // the caller flushes (flush_user_page)
    }
}

/// Point the (mapped) page at `addr` to another frame. Returns the old one.
pub fn replace_user_frame(l4: PhysFrame, addr: u64, frame: PhysFrame, flags: PageTableFlags) -> Option<PhysFrame> {
    let old = unmap_user_page(l4, addr)?;
    map_user_frame(l4, addr, frame, flags)?;
    Some(old)
}

/// Remove the mapping at `addr`; returns its frame (the caller releases it).
/// The page tables stay (they're freed with the address space).
pub fn unmap_user_page(l4: PhysFrame, addr: u64) -> Option<PhysFrame> {
    let mut mapper = unsafe { mapper_for(l4) };
    let (frame, flush) = mapper.unmap(user_page(addr)).ok()?;
    flush.ignore();
    Some(frame)
}

/// Drop this CPU's cached translation of user page `addr` (call after
/// changing a mapping of the *active* address space; for an inactive one
/// it's harmless). Other CPUs can't have it cached: a process runs on one
/// CPU at a time and switching CR3 flushes user mappings.
pub fn flush_user_page(addr: u64) {
    x86_64::instructions::tlb::flush(VirtAddr::new(addr & !0xfff));
}

/// Copy the user part of address space `src` into the (empty) `dst`, for
/// fork. Both end up mapping the same frames (each frame's reference count
/// goes up). `flags(addr, old)` decides the new flags of each page, in
/// *both* address spaces -- fork uses it to make private pages read-only,
/// so the first write to them faults and gets its own copy.
/// On failure (out of memory) `dst` may be partly filled: free it.
pub fn clone_user_space(src: PhysFrame, dst: PhysFrame, mut flags: impl FnMut(u64, PageTableFlags) -> PageTableFlags) -> Option<()> {
    for i4 in USER_L4_SLOTS {
        let Ok(l3) = table_mut(src)[i4].frame() else { continue };
        for (i3, e3) in table_mut(l3).iter().enumerate().filter(|(_, e)| !e.is_unused()) {
            let l2 = e3.frame().ok()?;
            for (i2, e2) in table_mut(l2).iter().enumerate().filter(|(_, e)| !e.is_unused()) {
                if l2_base(i4, i3, i2) < USER_START {
                    continue; // the kernel's low 2 MiB: dst has it already
                }
                let l1 = e2.frame().ok()?;
                for (i1, e1) in table_mut(l1).iter_mut().enumerate().filter(|(_, e)| !e.is_unused()) {
                    let addr = l2_base(i4, i3, i2) + ((i1 as u64) << 12);
                    let frame = e1.frame().ok()?;
                    let new_flags = flags(addr, e1.flags());
                    e1.set_flags(new_flags);
                    map_user_frame(dst, addr, frame, new_flags)?;
                    share_frame(frame);
                }
            }
        }
    }
    Some(())
}

/// Make sure `page` (in user space) is mapped in address space `l4` with at
/// least `flags` (USER_ACCESSIBLE + PRESENT are added). A new page gets a
/// zeroed frame; an already mapped one keeps its frame and gets the union
/// of old and new flags. Returns the backing frame.
pub fn map_user_page(l4: PhysFrame, page: Page, flags: PageTableFlags) -> Option<PhysFrame> {
    let addr = page.start_address().as_u64();
    assert!((USER_START..USER_END).contains(&addr), "not a user address");
    let flags = flags | PageTableFlags::PRESENT | PageTableFlags::USER_ACCESSIBLE;

    let mut mapper = unsafe { mapper_for(l4) };
    if let TranslateResult::Mapped { frame, flags: old, .. } = mapper.translate(page.start_address()) {
        // Already mapped (two ELF segments sharing a page): widen the flags.
        // Keep NO_EXECUTE only if both want it.
        let mut new = old | flags;
        if !(old & flags).contains(PageTableFlags::NO_EXECUTE) {
            new.remove(PageTableFlags::NO_EXECUTE);
        }
        unsafe { mapper.update_flags(page, new).ok()?.ignore() };
        return Some(PhysFrame::containing_address(frame.start_address()));
    }
    let frame = alloc_zeroed_frame()?;
    // map_to also creates missing L3/L2/L1 tables; since `flags` contains
    // USER_ACCESSIBLE, those parent entries get it too (the CPU checks the
    // user bit at every level). The TLB doesn't matter: this address space
    // may not even be active, and the mapping is new. Hence `ignore`.
    unsafe { mapper.map_to_with_table_flags(page, frame, flags, USER_TABLE_FLAGS, &mut GlobalFrameAllocator).ok()?.ignore() };
    Some(frame)
}

/// Can user code legitimately access `len` bytes at `addr` in the *current*
/// address space? Checks the range is inside user space and every page is
/// mapped USER_ACCESSIBLE (and WRITABLE if `write`). Syscalls call this
/// before touching any pointer a user program hands them; otherwise a program
/// could make the kernel read or overwrite kernel memory for it.
pub fn user_range_ok(addr: u64, len: u64, write: bool) -> bool {
    let Some(end) = addr.checked_add(len) else { return false };
    if addr < USER_START || end > USER_END {
        return false;
    }
    if len == 0 {
        return true;
    }
    let mapper = unsafe { mapper_for(Cr3::read().0) };
    let first = Page::<Size4KiB>::containing_address(VirtAddr::new(addr));
    let last = Page::<Size4KiB>::containing_address(VirtAddr::new(end - 1));
    Page::range_inclusive(first, last).all(|page| match mapper.translate(page.start_address()) {
        TranslateResult::Mapped { flags, .. } => {
            flags.contains(PageTableFlags::USER_ACCESSIBLE)
                && (!write || flags.contains(PageTableFlags::WRITABLE))
        }
        _ => false,
    })
}

// ---------------------------------------------------------------------------
// Kernel-space mappings for kernel stacks (see stack.rs)
// ---------------------------------------------------------------------------

/// The L4 slot that holds every kernel stack (0x0000_6400_0000_0000).
pub const STACKS_L4_INDEX: usize = 200;

/// Protects the kernel's own page tables. Taken with interrupts off.
static KERNEL_TABLES: Mutex<()> = Mutex::new(());

/// Give the kernel-stack slot its level-3 table *now*, before any process
/// address space is created. New address spaces copy the kernel's L4
/// entries, so they all point at this one L3 table, and every stack mapped
/// later shows up in every address space automatically.
pub fn init_kernel_stack_area() {
    without_interrupts(|| {
        let _lock = KERNEL_TABLES.lock();
        let l4: &mut PageTable = unsafe { &mut *phys_to_virt(kernel_l4_frame().start_address()).as_mut_ptr() };
        if l4[STACKS_L4_INDEX].is_unused() {
            let l3 = alloc_zeroed_frame().expect("no memory for the kernel stack area");
            l4[STACKS_L4_INDEX].set_frame(l3, PageTableFlags::PRESENT | PageTableFlags::WRITABLE);
        }
    })
}

/// Map `page` (inside the kernel stack area) to a fresh zeroed frame:
/// present, writable, not executable, kernel-only.
pub fn map_kernel_page(page: Page) -> Option<()> {
    let frame = alloc_zeroed_frame()?;
    let mut flags = PageTableFlags::PRESENT | PageTableFlags::WRITABLE;
    if nx_enabled() {
        flags |= PageTableFlags::NO_EXECUTE;
    }
    let ok = without_interrupts(|| {
        let _lock = KERNEL_TABLES.lock();
        let mut mapper = unsafe { mapper_for(kernel_l4_frame()) };
        match unsafe { mapper.map_to(page, frame, flags, &mut GlobalFrameAllocator) } {
            Ok(flush) => {
                flush.flush(); // drop any stale TLB entry on *this* CPU
                true
            }
            Err(_) => false,
        }
    });
    if !ok {
        free_frame(frame);
    }
    ok.then_some(())
}

/// Unmap a page mapped by `map_kernel_page` and free its frame. (The page
/// tables stay: the next stack in the same place reuses them.)
pub fn unmap_kernel_page(page: Page) {
    without_interrupts(|| {
        let _lock = KERNEL_TABLES.lock();
        let mut mapper = unsafe { mapper_for(kernel_l4_frame()) };
        if let Ok((frame, flush)) = mapper.unmap(page) {
            flush.flush();
            free_frame(frame);
        }
    })
}

/// Make device registers at physical `phys..phys + len` (a PCI memory BAR)
/// reachable and return their virtual address. The bootloader's physical
/// memory map usually covers them already (it maps up to 4 GiB, holes
/// included); BARs placed above that get mapped here, page by page, with
/// caching off (a device register must be read from the device every time).
pub fn map_mmio(phys: u64, len: u64) -> VirtAddr {
    let virt = phys_to_virt(PhysAddr::new(phys));
    without_interrupts(|| {
        let _lock = KERNEL_TABLES.lock();
        let mut mapper = unsafe { mapper_for(kernel_l4_frame()) };
        let first = phys & !0xfff;
        for page_phys in (first..phys + len).step_by(4096) {
            let page: Page = Page::containing_address(phys_to_virt(PhysAddr::new(page_phys)));
            if let TranslateResult::Mapped { .. } = mapper.translate(page.start_address()) {
                continue;
            }
            let frame = PhysFrame::containing_address(PhysAddr::new(page_phys));
            let flags = PageTableFlags::PRESENT | PageTableFlags::WRITABLE | PageTableFlags::NO_CACHE;
            if let Ok(flush) = unsafe { mapper.map_to(page, frame, flags, &mut GlobalFrameAllocator) } {
                flush.flush();
            }
        }
    });
    virt
}