Start of a platform-independent paging interface.

8 files changed, 595 insertions, 163 deletions

diff --git a/crates/kernel/src/alloc.rs b/crates/kernel/src/alloc.rs
index 94b4267..f634c73 100644
--- a/crates/kernel/src/alloc.rs
+++ b/crates/kernel/src/alloc.rs
@@ -1,23 +1,19 @@
 //! Global structures for the allocators.
 
-use crate::arch::{
-    paging::{PageTable, PageTableEntry, ASID, PAGE_TABLE_BITS, PAGE_TABLE_LEVELS},
-    MAX_PAGE_SIZE_BITS, PAGE_SIZE, PAGE_SIZE_BITS,
+use crate::paging::{
+    BuddyAllocator, MapError, MappingFlags, PageTable, ASID, LOMEM_TOP, MAX_PAGE_SIZE_BITS,
+    PAGE_SIZES,
 };
+use allocator_api2::alloc::AllocError;
 use contracts::requires;
-use core::ptr::NonNull;
+use core::{num::NonZero, ptr::NonNull};
 use spin::mutex::FairMutex;
-use vernos_alloc_buddy::BuddyAllocator;
-use vernos_utils::BelieveMeSend;
 
 /// The global instance of the physical page allocator.
-static BUDDY_ALLOCATOR: FairMutex<
-    Option<BuddyAllocator<PAGE_SIZE, PAGE_SIZE_BITS, { 1 + MAX_PAGE_SIZE_BITS - PAGE_SIZE_BITS }>>,
-> = FairMutex::new(None);
+static BUDDY_ALLOCATOR: FairMutex<Option<BuddyAllocator>> = FairMutex::new(None);
 
 /// The global kernel page table.
-static KERNEL_PAGE_TABLE: FairMutex<BelieveMeSend<Option<NonNull<PageTable>>>> =
-    FairMutex::new(BelieveMeSend(None));
+static KERNEL_PAGE_TABLE: FairMutex<Option<&'static mut PageTable>> = FairMutex::new(None);
 
 /// Initializes the allocator and enables paging.
 ///
@@ -26,44 +22,96 @@ static KERNEL_PAGE_TABLE: FairMutex<BelieveMeSend<Option<NonNull<PageTable>>>> =
 /// - Paging must not have been enabled previously.
 /// - The buddy allocator must be valid.
 #[requires(BUDDY_ALLOCATOR.lock().is_none())]
-#[ensures(BUDDY_ALLOCATOR.lock().is_some())]
 #[requires(KERNEL_PAGE_TABLE.lock().is_none())]
+#[ensures(BUDDY_ALLOCATOR.lock().is_some())]
 #[ensures(KERNEL_PAGE_TABLE.lock().is_some())]
-pub unsafe fn init(
-    mut buddy_allocator: BuddyAllocator<
-        'static,
-        PAGE_SIZE,
-        PAGE_SIZE_BITS,
-        { 1 + MAX_PAGE_SIZE_BITS - PAGE_SIZE_BITS },
-    >,
-) {
+pub unsafe fn init_kernel_page_table(buddy_allocator: BuddyAllocator) {
+    // Just making this mut above gets a warning thanks to the contracts macros...
+    let mut buddy_allocator = buddy_allocator;
+
     // Allocate a page to use (for now) as the global kernel page table. Later we'll actually
     // replace it with the hart0 initial stack's page, since we'll never free the root page of the
     // kernel page table, and we can't return that page to the buddy allocator anyway.
-    let mut page_table = buddy_allocator
+    let page_table = buddy_allocator
         .alloc_zeroed::<PageTable>()
-        .expect("failed to allocate the kernel page table");
+        .expect("failed to allocate the kernel page table")
+        .as_mut();
 
     // Create identity mappings for the lower half of memory.
-    for (i, entry) in page_table
-        .as_mut()
-        .iter_mut()
-        .enumerate()
-        .take(1 << (PAGE_TABLE_BITS - 1))
-    {
-        let addr = (i as u64) << ((PAGE_TABLE_LEVELS - 1) * PAGE_TABLE_BITS + PAGE_SIZE_BITS);
-        let mut pte = PageTableEntry::default();
-        pte.set_valid(true).set_rwx(true, true, true).set_addr(addr);
-        *entry = pte;
+    for page_num in 0..(LOMEM_TOP >> MAX_PAGE_SIZE_BITS) {
+        let addr = page_num << MAX_PAGE_SIZE_BITS;
+        let flags = MappingFlags::R | MappingFlags::W | MappingFlags::X;
+        page_table
+            .map(
+                &mut buddy_allocator,
+                addr,
+                addr,
+                1 << MAX_PAGE_SIZE_BITS,
+                flags,
+            )
+            .expect("failed to set up identity mapping for low memory in the kernel page table");
     }
 
     // Set the page table as the current page table.
-    page_table.as_mut().make_current(ASID::KERNEL);
+    PageTable::make_current(NonNull::from(&*page_table), ASID::KERNEL);
+
+    // Print the page table.
+    vernos_utils::dbg!(&page_table);
 
     // Save the buddy allocator and kernel page table.
     *BUDDY_ALLOCATOR.lock() = Some(buddy_allocator);
-    KERNEL_PAGE_TABLE.lock().0 = Some(page_table);
+    *KERNEL_PAGE_TABLE.lock() = Some(page_table);
+}
+
+#[requires(BUDDY_ALLOCATOR.lock().is_some())]
+#[requires(KERNEL_PAGE_TABLE.lock().is_some())]
+pub unsafe fn init_kernel_virtual_memory_allocator(himem_top: usize) {
+    todo!()
+}
+
+/// Tries to allocate a page of physical memory of the given size, returning its physical address.
+#[requires(PAGE_SIZES.contains(&len))]
+pub fn alloc_page(len: usize) -> Result<NonZero<usize>, AllocError> {
+    let mut buddy_allocator = BUDDY_ALLOCATOR.lock();
+    let buddy_allocator = buddy_allocator.as_mut().unwrap();
+    buddy_allocator.alloc_of_size(len).map(|addr| {
+        // SAFETY: NonNull guarantees the address will be nonzero.
+        unsafe { NonZero::new_unchecked(addr.as_ptr() as usize) }
+    })
+}
+
+/// Log the kernel page table.
+pub fn kernel_log_page_table() {
+    let kernel_page_table = KERNEL_PAGE_TABLE.lock();
+    let kernel_page_table = kernel_page_table.as_ref().unwrap();
+
+    let count = kernel_page_table.debug_mappings().count();
+    log::info!(
+        "The kernel page table had {count} mapping{}",
+        match count {
+            0 => "s.",
+            1 => ":",
+            _ => "s:",
+        }
+    );
+    for mapping in kernel_page_table.debug_mappings() {
+        log::info!("{mapping:?}");
+    }
+}
 
-    // Print the page table after this.
-    vernos_utils::dbg!(page_table.as_mut());
+/// Adds a mapping into the kernel page table.
+pub fn kernel_map(
+    vaddr: usize,
+    paddr: usize,
+    len: usize,
+    flags: MappingFlags,
+) -> Result<(), MapError> {
+    let mut buddy_allocator = BUDDY_ALLOCATOR.lock();
+    let mut kernel_page_table = KERNEL_PAGE_TABLE.lock();
+    let buddy_allocator = buddy_allocator.as_mut().unwrap();
+    let kernel_page_table = kernel_page_table.as_mut().unwrap();
+    kernel_page_table.map(&mut *buddy_allocator, vaddr, paddr, len, flags)?;
+    log::warn!("TODO: sfence.vma");
+    log::warn!("TODO: TLB shootdown");
+    Ok(())
 }
diff --git a/crates/kernel/src/arch/mod.rs b/crates/kernel/src/arch/mod.rs
index 1afe41c..bfdfcc7 100644
--- a/crates/kernel/src/arch/mod.rs
+++ b/crates/kernel/src/arch/mod.rs
@@ -9,6 +9,3 @@ cfg_if::cfg_if! {
         compile_error!("unsupported platform");
     }
 }
-
-/// The size of a regular-sized page of memory.
-pub const PAGE_SIZE: usize = 1 << PAGE_SIZE_BITS;
diff --git a/crates/kernel/src/arch/riscv64/mod.rs b/crates/kernel/src/arch/riscv64/mod.rs
index 15f44c7..011e244 100644
--- a/crates/kernel/src/arch/riscv64/mod.rs
+++ b/crates/kernel/src/arch/riscv64/mod.rs
@@ -1,12 +1,6 @@
 pub mod interrupts;
 pub mod paging;
 
-/// The number of bits in the size of a regular-sized page of memory.
-pub const PAGE_SIZE_BITS: usize = 12;
-
-/// The number of bits in the size of the largest huge page.
-pub const MAX_PAGE_SIZE_BITS: usize = 30;
-
 /// Halts the hart.
 pub fn sleep_forever() -> ! {
     loop {
diff --git a/crates/kernel/src/arch/riscv64/paging.rs b/crates/kernel/src/arch/riscv64/paging.rs
index 6b81881..5b87b64 100644
--- a/crates/kernel/src/arch/riscv64/paging.rs
+++ b/crates/kernel/src/arch/riscv64/paging.rs
@@ -1,8 +1,22 @@
-use crate::arch::{PAGE_SIZE, PAGE_SIZE_BITS};
+use crate::paging::{BuddyAllocator, MapError, MappingFlags, PAGE_SIZE, PAGE_SIZE_BITS};
 use contracts::requires;
-use core::{arch::asm, fmt, iter, ops::RangeInclusive, str};
+use core::{arch::asm, fmt, iter, ops::RangeInclusive, ptr::NonNull, str};
 use either::Either;
-use vernos_utils::debug;
+
+/// One past the largest address in "low memory."
+pub const LOMEM_TOP: usize = 0x0000_0040_0000_0000;
+
+/// The smallest address in "high memory."
+pub const HIMEM_BOT: usize = 0xffff_ffc0_0000_0000;
+
+/// The number of possible page sizes.
+pub const PAGE_SIZE_COUNT: usize = 3;
+
+/// The `log2`s of the possible page sizes, from largest to smallest.
+pub const PAGE_SIZES_BITS: [usize; PAGE_SIZE_COUNT] = [30, 21, 12];
+
+/// The `log2`s of the possible page sizes, from largest to smallest.
+pub const PAGE_SIZES: [usize; PAGE_SIZE_COUNT] = [1 << 30, 1 << 21, 1 << 12];
 
 /// The number of bits looked up in each page table entry.
 pub const PAGE_TABLE_BITS: usize = 9;
@@ -11,7 +25,7 @@ pub const PAGE_TABLE_BITS: usize = 9;
 pub const PAGE_TABLE_LEVELS: usize = 3;
 
 /// An address space ID.
-#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
+#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
 pub struct ASID(u16);
 
 impl ASID {
@@ -20,22 +34,27 @@ impl ASID {
 }
 
 /// A single page table.
+#[derive(Debug)]
 #[repr(align(4096))]
-pub struct PageTable([PageTableEntry; 512]);
+pub struct PageTable([PageTableEntry; 1 << PAGE_TABLE_BITS]);
 
 impl PageTable {
-    /// Set this as the root page table. Note that this does _not_ perform a TLB shootdown.
+    /// Set the page table whose _physical_ address is `page_table` as the current root page table.
+    ///
+    /// This performs appropriate invalidation or fencing as required by the platform, but does
+    /// _not_ perform a TLB shootdown.
     ///
     /// # Safety
     ///
     /// - All the safety conditions that would apply for setting `satp` and issuing an
     ///   `sfence.vma`.
+    /// - The page table must not be dropped while it is the current root page table!
     #[requires((asid.0 & !0xfff) == 0)]
-    #[requires(((self as *const PageTable as usize) & 0xff00_0000_0000_0fff) == 0)]
+    #[requires(((page_table.as_ptr() as usize) & 0xff00_0000_0000_0fff) == 0)]
     #[inline(never)]
-    pub unsafe fn make_current(&self, asid: ASID) {
+    pub unsafe fn make_current(page_table: NonNull<PageTable>, asid: ASID) {
         let mode = 8; // Sv39
-        let addr = self as *const PageTable as usize as u64;
+        let addr = page_table.as_ptr() as usize as u64;
         let satp = (mode << 60) | ((asid.0 as u64) << 44) | (addr >> 12);
         asm!("sfence.vma", "csrw satp, {satp}", "sfence.vma", satp = in(reg) satp)
     }
@@ -49,56 +68,114 @@ impl PageTable {
     pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut PageTableEntry> {
         self.0.iter_mut()
     }
-}
 
-impl fmt::Debug for PageTable {
-    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
-        // Get an iterator over the valid leaf page table entries.
-        let mut mappings = iter_level_2_mappings(&self.0, 0).peekable();
-
-        // Make an iterator that merges adjacent entries that have the same flags.
-        let mappings = iter::from_fn(|| {
-            let (entry, mut vaddrs) = mappings.next()?;
+    /// Iterates over the valid mappings. Each item is a triple of virtual address range, physical
+    /// address range, and entry.
+    pub fn iter_mappings(
+        &self,
+    ) -> impl '_ + Iterator<Item = (RangeInclusive<usize>, RangeInclusive<usize>, PageTableEntry)>
+    {
+        iter_level_2_mappings(&self.0, 0).map(|(entry, vaddrs)| {
+            let len = vaddrs.end() - vaddrs.start();
             let paddrs_start = entry.addr() as usize;
-            let mut len = (vaddrs.end() - vaddrs.start()) + 1;
-
-            while let Some((next_entry, next_vaddrs)) = mappings.peek() {
-                let next_paddrs_start = next_entry.addr() as usize;
-
-                if entry.flag_bits() != next_entry.flag_bits()
-                    || vaddrs.end().wrapping_add(1) != *next_vaddrs.start()
-                    || paddrs_start.wrapping_add(len) != next_paddrs_start
-                {
-                    break;
-                }
-                // UNWRAP: .peek() already showed us that there's a next entry.
-                let (_, next_vaddrs) = mappings.next().unwrap();
-                vaddrs = *vaddrs.start()..=*next_vaddrs.end();
-                len = (next_vaddrs.end() - vaddrs.start()) + 1;
+            let paddrs = paddrs_start..=paddrs_start + len;
+            (vaddrs, paddrs, entry)
+        })
+    }
+
+    /// Attempts to add a mapping of a particular size to the page tables. This does not issue an
+    /// `SFENCE.VMA`, nor a TLB shootdown.
+    ///
+    /// This may require allocating new intermediate page tables, so it may fail to allocate
+    /// memory.
+    pub fn map(
+        &mut self,
+        buddy_allocator: &mut BuddyAllocator,
+        vaddr: usize,
+        paddr: usize,
+        len: usize,
+        flags: MappingFlags,
+    ) -> Result<(), MapError> {
+        // Ignore the bits of the flags that we don't want to set.
+        let flags = MappingFlags::from_bits(flags.bits())
+            .ok_or(MapError::InvalidFlags)?
+            .difference(MappingFlags::A | MappingFlags::D);
+
+        // Check that we had some permissions bits set in the flags.
+        if !flags.intersects(MappingFlags::R | MappingFlags::W | MappingFlags::X) {
+            return Err(MapError::InvalidFlagPermissions);
+        }
+
+        // Check that the page size is valid, and that the physical and virtual addresses are
+        // aligned for it.
+        let page_size_class = PAGE_SIZES
+            .iter()
+            .position(|&page_size| page_size == len)
+            .ok_or(MapError::InvalidLength)?;
+        let page_size_bits = PAGE_SIZES_BITS[page_size_class];
+        if paddr & (len - 1) != 0 {
+            return Err(MapError::MisalignedPAddr);
+        }
+        if vaddr & (len - 1) != 0 {
+            return Err(MapError::MisalignedVAddr);
+        }
+
+        // Check that the vaddr isn't in the "dead zone" between lomem and himem.
+        if (LOMEM_TOP..HIMEM_BOT).contains(&vaddr) {
+            return Err(MapError::InvalidVAddr);
+        }
+
+        // If the virtual address is in himem, move it down to hide the dead zone. This is wrong,
+        // but makes the math simpler.
+        let vaddr = if vaddr >= HIMEM_BOT {
+            vaddr - (HIMEM_BOT - LOMEM_TOP)
+        } else {
+            vaddr
+        };
+
+        // Traverse the page tables, so that an entry in the table referenced by `page_table` is
+        // the right size class of page. This may involve allocating new page tables.
+        //
+        // TODO: Can we deallocate these if an error occurs later?
+        let mut page_table = self;
+        for page_size_bits in PAGE_SIZES_BITS.iter().take(page_size_class) {
+            let entry_slot =
+                &mut page_table.0[(vaddr >> page_size_bits) & ((1 << PAGE_TABLE_BITS) - 1)];
+            if !entry_slot.valid() {
+                // Allocate a new page table.
+                let next_page_table = buddy_allocator.alloc_zeroed::<PageTable>()?;
+                let mut entry = PageTableEntry::default();
+                entry
+                    .set_valid(true)
+                    .set_addr(next_page_table.as_ptr() as u64);
+                *entry_slot = entry;
+            }
+            if entry_slot.leaf_pte() {
+                return Err(MapError::MappingAlreadyExisted);
             }
-            let paddrs = paddrs_start..=paddrs_start + (len - 1);
-            Some((entry, vaddrs, paddrs))
-        });
-
-        // Turn the iterator into an iterator over Debugs.
-        let debug_mappings = mappings.map(|(entry, vaddrs, paddrs)| {
-            debug(move |fmt| {
-                let flags = entry.flags_str();
-                // UNWRAP: The flags must be ASCII by the postcondition of flags_str().
-                let flags = str::from_utf8(&flags).unwrap();
-                write!(
-                    fmt,
-                    "[V|{:16x}-{:16x}][P|{:16x}-{:16x}][F|{}]",
-                    *vaddrs.start(),
-                    *vaddrs.end(),
-                    *paddrs.start(),
-                    *paddrs.end(),
-                    flags
-                )
-            })
-        });
-
-        fmt.debug_list().entries(debug_mappings).finish()
+
+            // UNSAFE, UNWRAP: We maintain the invariant that all entries marked valid actually are valid.
+            page_table = unsafe { entry_slot.page_table().as_mut().unwrap() };
+        }
+
+        // Find the entry that we need to set, making sure it's not already occupied.
+        let entry_slot =
+            &mut page_table.0[(vaddr >> page_size_bits) & ((1 << PAGE_TABLE_BITS) - 1)];
+        if entry_slot.valid() {
+            return Err(MapError::MappingAlreadyExisted);
+        }
+
+        // Otherwise, put the entry in.
+        let mut entry = PageTableEntry::default();
+        entry
+            .set_valid(true)
+            .set_readable(flags.contains(MappingFlags::R))
+            .set_writable(flags.contains(MappingFlags::W))
+            .set_executable(flags.contains(MappingFlags::X))
+            .set_user(flags.contains(MappingFlags::U))
+            .set_addr(paddr as u64);
+        *entry_slot = entry;
+        Ok(())
     }
 }
 
@@ -107,6 +184,19 @@ impl fmt::Debug for PageTable {
 pub struct PageTableEntry(u64);
 
 impl PageTableEntry {
+    /// The value that `crate::paging::MappingFlags::R` should have.
+    pub const FLAG_R: usize = 0b00000010;
+    /// The value that `crate::paging::MappingFlags::W` should have.
+    pub const FLAG_W: usize = 0b00000100;
+    /// The value that `crate::paging::MappingFlags::X` should have.
+    pub const FLAG_X: usize = 0b00001000;
+    /// The value that `crate::paging::MappingFlags::U` should have.
+    pub const FLAG_U: usize = 0b00010000;
+    /// The value that `crate::paging::MappingFlags::A` should have.
+    pub const FLAG_A: usize = 0b01000000;
+    /// The value that `crate::paging::MappingFlags::D` should have.
+    pub const FLAG_D: usize = 0b10000000;
+
     /// Returns the physical page number of the backing page or next level page table.
     #[requires(self.valid())]
     #[ensures((ret & !0x0000_0fff_ffff_ffff) == 0)]
@@ -114,21 +204,19 @@ impl PageTableEntry {
         (self.0 >> 10) & 0x0000_0fff_ffff_ffff
     }
 
-    /// Returns the bits of the entry that correspond to flags.
-    ///
-    /// This isn't `pub` because this isn't portable, though maybe it makes sense to instead export
-    /// a predicate for "do these two entries have the _same_ flags bits," since that should be
-    /// more portable.
+    /// Returns whether the flag bits of the entry matched the other entry's.
     #[requires(self.valid())]
-    #[ensures((ret & !0xffc0_0000_0000_03ff) == 0)]
-    fn flag_bits(&self) -> u64 {
-        self.0 & 0xffc0_0000_0000_03ff
+    #[requires(other.valid())]
+    pub fn flag_bits_eq(&self, other: &PageTableEntry) -> bool {
+        let lhs = self.0 & 0xffc0_0000_0000_03ff;
+        let rhs = other.0 & 0xffc0_0000_0000_03ff;
+        lhs == rhs
     }
 
     /// Returns bytes that correspond to an ASCII string with the flags.
     #[requires(self.valid())]
     #[ensures(ret.iter().all(|ch| ch.is_ascii()))]
-    fn flags_str(&self) -> [u8; 7] {
+    pub fn flags_str_bytes(&self) -> [u8; 7] {
         let mut flags = *b"rwxugad";
         let char_disabled = b'-';
         if !self.readable() {
@@ -322,8 +410,8 @@ impl fmt::Debug for PageTableEntry {
     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
         if self.valid() {
             let addr = self.addr() as *const ();
-            let flags = self.flags_str();
-            // UNWRAP: The flags must be ASCII by the postcondition of flags_str().
+            let flags = self.flags_str_bytes();
+            // UNWRAP: The flags must be ASCII by the postcondition of flags_str_bytes().
             let flags = str::from_utf8(&flags).unwrap();
             write!(fmt, "PageTableEntry({addr:018p}, {flags})")
         } else {
@@ -335,7 +423,7 @@ impl fmt::Debug for PageTableEntry {
 /// See `PageTable::iter_mappings`. This needs to be its own function because of `impl Trait`; we
 /// can't allocate here, and we want a fixed-size iterator.
 fn iter_level_2_mappings(
-    table: &[PageTableEntry; 512],
+    table: &[PageTableEntry; 1 << PAGE_TABLE_BITS],
     base_addr: usize,
 ) -> impl '_ + Iterator<Item = (PageTableEntry, RangeInclusive<usize>)> {
     const ENTRY_SIZE: usize = 1 << (12 + 9 + 9);
@@ -363,7 +451,7 @@ fn iter_level_2_mappings(
 /// See `PageTable::iter_mappings`. This needs to be its own function because of `impl Trait`; we
 /// can't allocate here, and we want a fixed-size iterator.
 fn iter_level_1_mappings(
-    table: &[PageTableEntry; 512],
+    table: &[PageTableEntry; 1 << PAGE_TABLE_BITS],
     base_addr: usize,
 ) -> impl '_ + Iterator<Item = (PageTableEntry, RangeInclusive<usize>)> {
     const ENTRY_SIZE: usize = 1 << (12 + 9);
@@ -388,7 +476,7 @@ fn iter_level_1_mappings(
 /// See `PageTable::iter_mappings`. This needs to be its own function because of `impl Trait`; we
 /// can't allocate here, and we want a fixed-size iterator.
 fn iter_level_0_mappings(
-    table: &[PageTableEntry; 512],
+    table: &[PageTableEntry; 1 << PAGE_TABLE_BITS],
     base_addr: usize,
 ) -> impl '_ + Iterator<Item = (PageTableEntry, RangeInclusive<usize>)> {
     const ENTRY_SIZE: usize = 1 << 12;
diff --git a/crates/kernel/src/constants.rs b/crates/kernel/src/constants.rs
new file mode 100644
index 0000000..9c53bd8
--- /dev/null
+++ b/crates/kernel/src/constants.rs
@@ -0,0 +1,2 @@
+/// The size of kernel stacks.
+pub const STACK_SIZE: usize = 2 << 20;
diff --git a/crates/kernel/src/lib.rs b/crates/kernel/src/lib.rs
index 517ace9..8c964af 100644
--- a/crates/kernel/src/lib.rs
+++ b/crates/kernel/src/lib.rs
@@ -1,9 +1,13 @@
 //! The static library that forms the core of the kernel.
 #![no_std]
 
-use crate::arch::{sleep_forever, PAGE_SIZE, PAGE_SIZE_BITS};
+use crate::{
+    alloc::{alloc_page, init_kernel_page_table, kernel_log_page_table, kernel_map},
+    constants::STACK_SIZE,
+    paging::{MappingFlags, PAGE_SIZE, PAGE_SIZE_BITS},
+};
 use core::ptr::NonNull;
-use log::{debug, info};
+use log::debug;
 use vernos_alloc_buddy::BuddyAllocator;
 use vernos_alloc_physmem_free_list::FreeListAllocator;
 use vernos_device_tree::FlattenedDeviceTree;
@@ -13,34 +17,87 @@ mod panic;
 
 pub mod alloc;
 pub mod arch;
+pub mod constants;
 pub mod logger;
+pub mod paging;
+
+/// Some addresses passed from the entrypoint to hart0.
+#[derive(Debug)]
+#[repr(C)]
+pub struct EarlyBootAddrs {
+    device_tree: *const u8,
+    kernel_start: *const [u8; PAGE_SIZE],
+    kernel_end: *const [u8; PAGE_SIZE],
+    kernel_rx_end: *const [u8; PAGE_SIZE],
+    kernel_ro_end: *const [u8; PAGE_SIZE],
+    kernel_rw_end: *const [u8; PAGE_SIZE],
+    initial_stack_start: *const [u8; PAGE_SIZE],
+    stack_end: *const [u8; PAGE_SIZE],
+    trampoline_start: *const [u8; PAGE_SIZE],
+}
+
+impl EarlyBootAddrs {
+    /// Looks for a DeviceTree at address in the `EarlyBootAddrs`, and returns it if it looks
+    /// valid. Panics if the DeviceTree is invalid.
+    ///
+    /// ## Safety
+    ///
+    /// - The `EarlyBootAddrs` must be accurate.
+    /// - The `device_tree` pointer must be a valid pointer into physical memory. See
+    ///   `device_tree::FlattenedDeviceTree::from_ptr` for the precise requirements.
+    unsafe fn flattened_device_tree(&self) -> FlattenedDeviceTree {
+        FlattenedDeviceTree::from_ptr(
+            self.device_tree,
+            self.kernel_start as usize..self.kernel_end as usize,
+        )
+        .expect("invalid DeviceTree")
+    }
+}
 
 /// The first stage of booting the kernel. This should be executed by hart0 alone. It runs with
 /// paging disabled, and:
 ///
 /// - sets up a physical memory allocator
 /// - sets up paging
-/// - allocates some global structures in the higher half of memory:
-///   - a logger's buffer
-///   - a stack for this kernel thread
-///   - the DeviceTree in tree form
+/// - sets up a virtual memory allocator
+/// - sets up an allocator
+/// - maps the trampoline page
+/// - maps the kernel to higher-half memory
+/// - allocates and maps a kernel stack for hart0
 ///
-/// It returns the top address of the stack for this kernel thread.
+/// It updates several fields in `early_boot_addrs` to point to the appropriate himem addresses:
+///
+/// - `kernel_start`
+/// - `stack_end`
 ///
 /// # Safety
 ///
 /// - The `device_tree` pointer must be a valid pointer into physical memory. See
 ///   `device_tree::FlattenedDeviceTree::from_ptr` for the precise requirements.
+/// - The `kernel_start`, `kernel_rx_end`, `kernel_ro_end`, `kernel_rw_end`, and `kernel_end`
+///   addresses must be accurate and page-aligned.
+/// - The `stack_start` and `stack_end` addresses must be accurate and page-aligned.
+/// - The `trampoline_start` pointer must be accurate and page-aligned.
 /// - This must be called in supervisor mode with paging disabled.
 /// - Any other harts must not be running concurrently with us.
 #[no_mangle]
-pub unsafe extern "C" fn hart0_early_boot(device_tree: *const u8) -> ! {
-    // Set up the logger.
-    logger::init();
+pub unsafe extern "C" fn hart0_early_boot(early_boot_addrs: &mut EarlyBootAddrs) {
+    // Set up the early-boot logger.
+    logger::init_early();
+    vernos_utils::dbg!(&*early_boot_addrs);
+
+    // Assert that stuff is aligned properly.
+    assert!(early_boot_addrs.kernel_start.is_aligned());
+    assert!(early_boot_addrs.kernel_end.is_aligned());
+    assert!(early_boot_addrs.kernel_rx_end.is_aligned());
+    assert!(early_boot_addrs.kernel_ro_end.is_aligned());
+    assert!(early_boot_addrs.kernel_rw_end.is_aligned());
+    assert!(early_boot_addrs.initial_stack_start.is_aligned());
+    assert!(early_boot_addrs.stack_end.is_aligned());
+    assert!(early_boot_addrs.trampoline_start.is_aligned());
 
     // Parse the DeviceTree.
-    let flattened_device_tree =
-        unsafe { FlattenedDeviceTree::from_ptr(device_tree) }.expect("invalid DeviceTree");
+    let flattened_device_tree = unsafe { early_boot_addrs.flattened_device_tree() };
 
     // Find the available physical memory areas and initialize the physical memory
     // free-list.
@@ -84,16 +141,91 @@ pub unsafe extern "C" fn hart0_early_boot(device_tree: *const u8) -> ! {
     let alloc_buddy = BuddyAllocator::new(physical_memory_free_list)
         .expect("failed to configure the buddy allocator");
 
-    // Set up the allocators.
-    alloc::init(alloc_buddy);
+    // Set up the kernel page table.
+    init_kernel_page_table(alloc_buddy);
+
+    // Map the trampoline page.
+    let mut vaddr_bump = usize::MAX - PAGE_SIZE + 1;
+    kernel_map(
+        vaddr_bump,
+        early_boot_addrs.trampoline_start as usize,
+        PAGE_SIZE,
+        MappingFlags::R | MappingFlags::X,
+    )
+    .expect("failed to map the trampoline page to himem");
+
+    // Skip a page down for a guard page, then map the kernel.
+    let total_kernel_pages = early_boot_addrs
+        .kernel_rw_end
+        .offset_from(early_boot_addrs.kernel_start) as usize;
+    vaddr_bump -= PAGE_SIZE * (total_kernel_pages + 1);
+    let new_kernel_start = vaddr_bump;
+    for i in 0..total_kernel_pages {
+        let vaddr = vaddr_bump + (i * PAGE_SIZE);
+        let paddr = early_boot_addrs.kernel_start.add(i);
+        let flags = if paddr < early_boot_addrs.kernel_rx_end {
+            MappingFlags::R | MappingFlags::X
+        } else if paddr < early_boot_addrs.kernel_ro_end {
+            MappingFlags::R
+        } else {
+            MappingFlags::R | MappingFlags::W
+        };
+
+        kernel_map(vaddr, paddr as usize, PAGE_SIZE, flags)
+            .expect("failed to map the kernel to himem");
+    }
+
+    // Skip a page down for a guard page, then map the top page of the stack.
+    vaddr_bump -= PAGE_SIZE;
+    let new_stack_end = vaddr_bump;
+    vaddr_bump -= PAGE_SIZE;
+    kernel_map(
+        vaddr_bump,
+        early_boot_addrs.initial_stack_start as usize,
+        PAGE_SIZE,
+        MappingFlags::R | MappingFlags::W,
+    )
+    .expect("failed to map the initial stack to himem");
+
+    // Allocate and map more pages for the stack.
+    let new_stack_start = new_stack_end - STACK_SIZE;
+    vaddr_bump = new_stack_start;
+    for i in 0..((STACK_SIZE >> PAGE_SIZE_BITS) - 1) {
+        let vaddr = new_kernel_start + i << PAGE_SIZE_BITS;
+        let paddr =
+            alloc_page(PAGE_SIZE).expect("failed to allocate memory for a hart0 stack page");
+        kernel_map(
+            vaddr,
+            paddr.into(),
+            PAGE_SIZE,
+            MappingFlags::R | MappingFlags::W,
+        )
+        .expect("failed to map a hart0 stack page");
+    }
+
+    // Skip another page down for a guard page.
+    vaddr_bump -= PAGE_SIZE;
 
-    todo!()
+    // Set up the kernel virtual memory allocator (and general allocator).
+    init_kernel_virtual_memory_allocator(vaddr_bump);
+
+    // Set the fields in `early_boot_addrs` that we promise to.
+    early_boot_addrs.kernel_start = new_kernel_start as *const [u8; PAGE_SIZE];
+    early_boot_addrs.stack_end = new_stack_end as *const [u8; PAGE_SIZE];
+
+    // Log and return.
+    kernel_log_page_table();
 }
 
-/// The entrypoint to the kernel, to be run after paging is set up. This should be executed by
-/// hart0 alone. It performs some early boot tasks, then wakes up any other harts.
+/// The entrypoint to the kernel, to be run after paging and the allocator have been set up, and
+/// the stack has been switched to be in himem. This should be executed by hart0 alone. It performs
+/// some early boot tasks, then wakes up any other harts.
+///
+/// The tasks it performs are:
 ///
-/// It receives the stack canary from the initial stack, and validates it.
+/// - converts the DeviceTree into a global key-value mapping
+/// - upgrades the logger to one that can dynamically grow
+/// - TODO
 ///
 /// # Safety
 ///
@@ -102,34 +234,12 @@ pub unsafe extern "C" fn hart0_early_boot(device_tree: *const u8) -> ! {
 ///   supervisor mode.
 /// - Any other harts must not be running concurrently with us. TODO: Define their state.
 #[no_mangle]
-pub unsafe extern "C" fn hart0_boot(stack_canary: u64) -> ! {
-    assert_eq!(stack_canary, 0xdead0bad0defaced);
-
-    /*
-    // After this point, everything else is for debugging.
-    #[cfg(target_arch = "riscv64")]
-    {
-        flattened_device_tree
-            .for_each_node(|node| {
-                if node.is_unit(&["", "cpus"]) {
-                    if let Some(timebase_frequency) = node.get_prop_u32("timebase-frequency") {
-                        // SAFETY: Other harts are not concurrently running, so they can't be
-                        // concurrently accessing or modifying this.
-                        unsafe {
-                            vernos_driver_riscv_timer::TIMEBASE_FREQUENCY = timebase_frequency;
-                        }
-                    }
-                }
-                Ok(())
-            })
-            .unwrap_or_else(|err| void::unreachable(err));
-        arch::interrupts::example_timer();
-    }
-    */
+pub unsafe extern "C" fn hart0_boot(early_boot_addrs: &mut EarlyBootAddrs) -> ! {
+    // Check that the stack canary was present.
+    assert_eq!(
+        *(early_boot_addrs.initial_stack_start as *const u64),
+        0xdead0bad0defaced
+    );
 
-    if true {
-        todo!();
-    }
-    info!("sleeping forever...");
-    sleep_forever();
+    todo!("hart0_boot");
 }
diff --git a/crates/kernel/src/logger.rs b/crates/kernel/src/logger.rs
index 696c9a6..7cc3f70 100644
--- a/crates/kernel/src/logger.rs
+++ b/crates/kernel/src/logger.rs
@@ -4,7 +4,7 @@
 use core::fmt::{self, Write};
 
 /// Initializes the logger. This should be called exactly once, early in boot.
-pub fn init() {
+pub fn init_early() {
     log::set_logger(&Logger).expect("failed to set logger");
     log::set_max_level(log::LevelFilter::Trace);
     log::warn!("Using a bad unportable logger that only works on qemu-virt");
diff --git a/crates/kernel/src/paging.rs b/crates/kernel/src/paging.rs
new file mode 100644
index 0000000..76c603d
--- /dev/null
+++ b/crates/kernel/src/paging.rs
@@ -0,0 +1,193 @@
+//! An architecture-independent interface to the page tables.
+
+use crate::arch;
+pub use crate::arch::paging::{HIMEM_BOT, LOMEM_TOP, PAGE_SIZES, PAGE_SIZES_BITS, PAGE_SIZE_COUNT};
+use allocator_api2::alloc::AllocError;
+use core::{
+    fmt, iter,
+    ptr::{addr_of_mut, NonNull},
+    str,
+};
+use vernos_utils::debug;
+
+/// The number of bits in the size of a regular-sized page of memory.
+pub const PAGE_SIZE_BITS: usize = PAGE_SIZES_BITS[PAGE_SIZE_COUNT - 1];
+
+/// The size of a regular-sized page of memory.
+pub const PAGE_SIZE: usize = 1 << PAGE_SIZE_BITS;
+
+/// The number of bits in the size of the largest huge page.
+pub const MAX_PAGE_SIZE_BITS: usize = PAGE_SIZES_BITS[0];
+
+/// The buddy allocator, specialized for the details of our paging subsystem.
+pub type BuddyAllocator = vernos_alloc_buddy::BuddyAllocator<
+    'static,
+    PAGE_SIZE,
+    PAGE_SIZE_BITS,
+    { 1 + MAX_PAGE_SIZE_BITS - PAGE_SIZE_BITS },
+>;
+
+/// A wrapper for the root page table, providing an architecture-independent interface to it.
+///
+/// This should be behind a pointer.
+pub struct PageTable(arch::paging::PageTable);
+
+impl PageTable {
+    /// Allocates a new page table in pages retrieved from the given buddy allocator.
+    pub fn new_in(buddy_allocator: &mut BuddyAllocator) -> Result<NonNull<PageTable>, AllocError> {
+        buddy_allocator.alloc_zeroed::<PageTable>()
+    }
+
+    /// Set the page table whose _physical_ address is `page_table` as the current root page table.
+    ///
+    /// This performs appropriate invalidation or fencing as required by the platform, but does
+    /// _not_ perform a TLB shootdown.
+    ///
+    /// # Safety
+    ///
+    /// - There must not be any live references to pages that are no longer mapped or are mapped
+    ///   differently in the new page table.
+    pub unsafe fn make_current(page_table: NonNull<PageTable>, asid: ASID) {
+        let page_table = NonNull::new_unchecked(addr_of_mut!((*page_table.as_ptr()).0));
+        arch::paging::PageTable::make_current(page_table, asid.0)
+    }
+
+    /// Attempts to add a mapping of a particular size to the page tables.
+    ///
+    /// This may require allocating new intermediate page tables, so it may fail to allocate
+    /// memory.
+    ///
+    /// TODO: Fences and shootdowns?
+    pub fn map(
+        &mut self,
+        buddy_allocator: &mut BuddyAllocator,
+        vaddr: usize,
+        paddr: usize,
+        len: usize,
+        flags: MappingFlags,
+    ) -> Result<(), MapError> {
+        self.0.map(buddy_allocator, vaddr, paddr, len, flags)
+    }
+
+    /// Returns an iterator over `Debug`s that show the mapping in this page table.
+    pub fn debug_mappings(&self) -> impl '_ + Iterator<Item = impl fmt::Debug> {
+        // Get an iterator over the valid leaf page table entries.
+        let mut mappings = self.0.iter_mappings().peekable();
+
+        // Make an iterator that merges adjacent entries that have the same flags.
+        let merged_mappings = iter::from_fn(move || {
+            let (mut vaddrs, mut paddrs, entry) = mappings.next()?;
+            while let Some((next_vaddrs, next_paddrs, next_entry)) = mappings.peek() {
+                // We use .checked_add() instead of .wrapping_add() because we _don't_ want to have
+                // ranges that wrap around.
+                if !entry.flag_bits_eq(next_entry)
+                    || vaddrs.end().checked_add(1) != Some(*next_vaddrs.start())
+                    || paddrs.end().checked_add(1) != Some(*next_paddrs.start())
+                {
+                    break;
+                }
+                // UNWRAP: .peek() already showed us that there's a next entry.
+                let (next_vaddrs, next_paddrs, _) = mappings.next().unwrap();
+                vaddrs = *vaddrs.start()..=*next_vaddrs.end();
+                paddrs = *paddrs.start()..=*next_paddrs.end();
+            }
+            Some((vaddrs, paddrs, entry))
+        });
+
+        // Turn the iterator into an iterator over Debugs.
+        merged_mappings.map(|(vaddrs, paddrs, entry)| {
+            debug(move |fmt| {
+                let flags = entry.flags_str_bytes();
+                // UNWRAP: The flags must be ASCII by the postcondition of flags_str_bytes().
+                let flags = str::from_utf8(&flags).unwrap();
+                write!(
+                    fmt,
+                    "[V|{:16x}-{:16x}][P|{:16x}-{:16x}][F|{}]",
+                    *vaddrs.start(),
+                    *vaddrs.end(),
+                    *paddrs.start(),
+                    *paddrs.end(),
+                    flags
+                )
+            })
+        })
+    }
+}
+
+impl fmt::Debug for PageTable {
+    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
+        fmt.debug_list().entries(self.debug_mappings()).finish()
+    }
+}
+
+unsafe impl Send for PageTable {}
+
+bitflags::bitflags! {
+    /// The flags associated with a mapping.
+    #[derive(Clone, Copy, Debug)]
+    pub struct MappingFlags: usize {
+        /// Whether the mapping is readable.
+        const R = arch::paging::PageTableEntry::FLAG_R;
+
+        /// Whether the mapping is writable.
+        const W = arch::paging::PageTableEntry::FLAG_W;
+
+        /// Whether the mapping is executable.
+        const X = arch::paging::PageTableEntry::FLAG_X;
+
+        /// Whether the mapping is accessible to userspace or to kernelspace. Note that a mapping
+        /// that is accessible to one is not necessarily accessible to the other.
+        const U = arch::paging::PageTableEntry::FLAG_U;
+
+        /// Whether the mapping has been read from since it was last set. This is ignored by
+        /// `PageTable::map`, but may be returned by `PageTable::get_mapping`.
+        const A = arch::paging::PageTableEntry::FLAG_A;
+
+        /// Whether the mapping has been written to since it was last set. This is ignored by
+        /// `PageTable::map`, but may be returned by `PageTable::get_mapping`.
+        const D = arch::paging::PageTableEntry::FLAG_D;
+    }
+}
+
+/// An error creating a mapping.
+#[derive(Debug)]
+pub enum MapError {
+    /// A failure to allocate memory to store the page table in.
+    AllocError,
+
+    /// An unknown flag bit was set.
+    InvalidFlags,
+
+    /// None of `R`, `W`, or `X` were set.
+    InvalidFlagPermissions,
+
+    /// The length of the mapping is not supported for this virtual address range.
+    InvalidLength,
+
+    /// The mapping would cover an invalid virtual address.
+    InvalidVAddr,
+
+    /// The mapping would overlap with an existing mapping or guard page.
+    MappingAlreadyExisted,
+
+    /// The mapping's physical address isn't aligned.
+    MisalignedPAddr,
+
+    /// The mapping's virtual address isn't aligned.
+    MisalignedVAddr,
+}
+
+impl From<AllocError> for MapError {
+    fn from(AllocError: AllocError) -> Self {
+        MapError::AllocError
+    }
+}
+
+/// The type of address-space IDs. If a target does not have ASIDs, this may be a ZST.
+#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
+pub struct ASID(arch::paging::ASID);
+
+impl ASID {
+    /// The kernel's ASID.
+    pub const KERNEL: ASID = ASID(arch::paging::ASID::KERNEL);
+}