分页机制 - 页表和页表项 - ArceOS Tutorial Book

第二节分页机制 - 页表和页表项

本节先来建立分页机制的基本数据结构 - 页表和页表项，为后面正式启用分页做准备。

从根页表开始，每一级页表都占用一个内存页，关于内存页大小，我们采用最典型的 4096 字节。Sv39 是针对 64 位系统的分页方案，即页表项长度是 8 字节，所以每个页表包含 512 个页表项。页表作为多级嵌套结构，由页表 page_table 和页表项 page_table_entry 两种基本元素交替构成，它们符合如下的模式：

每个页表 page_table 对应一个内存页，每个页划分为 512 个页表项 page_table_entry；页表项 page_table_entry 由物理页帧号 pfn 和标志位组 flags 这两部分构成。根据标志位不同，页表项有三种情况：

空页表项：尚未与物理页建立映射；
指向下级页表：pfn 保存的是下级页表的物理页帧号，当进行地址映射时，需要递归到下一级页表继续处理；
指向最终页：这种是叶子页表项（leaf entry），它的 pfn 直接就保存着一个物理页或者大页的页帧号。

下面来看一下 flags 各个位的具体功能定义，这里部分参照了 Linux 对各个位的命名：

/*
 * RiscV64 PTE format:
 * | XLEN-1  10 | 9             8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0
 *       PFN      reserved for SW   D   A   G   U   X   W   R   V
 */
const _PAGE_V : usize = 1 << 0;     /* Valid */
const _PAGE_R : usize = 1 << 1;     /* Readable */
const _PAGE_W : usize = 1 << 2;     /* Writable */
const _PAGE_E : usize = 1 << 3;     /* Executable */
const _PAGE_U : usize = 1 << 4;     /* User */
const _PAGE_G : usize = 1 << 5;     /* Global */
const _PAGE_A : usize = 1 << 6;     /* Accessed (set by hardware) */
const _PAGE_D : usize = 1 << 7;     /* Dirty (set by hardware)*/

const PAGE_TABLE: usize = _PAGE_V;
pub const PAGE_KERNEL_RO: usize = _PAGE_V | _PAGE_R | _PAGE_G | _PAGE_A | _PAGE_D;
pub const PAGE_KERNEL_RW: usize = PAGE_KERNEL_RO | _PAGE_W;
pub const PAGE_KERNEL_RX: usize = PAGE_KERNEL_RO | _PAGE_E;
pub const PAGE_KERNEL_RWX: usize = PAGE_KERNEL_RW | _PAGE_E;

flags 从第 10 位往上是物理页帧号 pfn，而第 10 位是页表项的属性标志位。

第 0 位 V：页表项是否有效，当访问无效页面时，MMU 触发 Page Fault 之类的异常，这通常作为 Linux 等内核缺页加载的基本机制；

第 1~3 位 RWE：对映射后的页面是否分别具备读、写、执行权限，当越权访问时，MMU 触发 Access Fault 之类的异常，在 Linux 等内核实现中，可以基于该类异常实现 COW 写时拷贝；

第 4 位 U：表示这是用户页。由于实验内核是 Unikernel 形态，不存在用户态，所以这个位直接清零。

第 5 位 G：表示是全局页。这个位与 tlb 刷新有关。我们的 Unikernel 内核中，所有用到的页面都设置为全局页。

第 6~7 位 AD：分别表示 Accessed 访问过和 Dirty 被改写过。对于 Linux 等内核，通常是先把它们清零，如果运行过程中访问或改写了对应映射的页面，MMU 硬件会自动把它们置一，内核只要检查这两个位，就能知道是否发生过访问或改写的情况，这通常对页面置换策略有帮助。但是对我们的内核，没有涉及页面置换的问题，所以初始化时，只是简单的把它们都设置成一。

基于上述位，对外提供两个公开的复合标识。PAGE_KERNEL_RW 作为默认的地址映射标识，表示映射的页面存在并可以读写；PAGE_KERNEL_RWX 在此基础上增加执行权限。

实现一个新组件 page_table，首先包含上述标识定义，然后定义页表和页表项的数据结构和页表的初始化函数：

// page_table/src/lib.rs
#![no_std]

use axconfig::phys_pfn;

#[derive(Debug)]
pub enum PagingError {}
pub type PagingResult<T = ()> = Result<T, PagingError>;
const PAGE_PFN_SHIFT: usize = 10;
const ENTRIES_COUNT: usize = 1 << (PAGE_SHIFT - 3);

#[derive(Clone, Copy)]
#[repr(transparent)]
pub struct PTEntry(u64);

impl PTEntry {
    pub fn set(&mut self, pa: usize, flags: usize) {
        self.0 = Self::make(phys_pfn(pa), flags);
    }

    fn make(pfn: usize, prot: usize) -> u64 {
        ((pfn << PAGE_PFN_SHIFT) | prot) as u64
    }
}

pub struct PageTable<'a> {
    level: usize,
    table: &'a mut [PTEntry],
}

impl PageTable<'_> {
    pub fn init(root_pa: usize, level: usize) -> Self {
        let table = unsafe {
            core::slice::from_raw_parts_mut(root_pa as *mut PTEntry, ENTRIES_COUNT)
        };
        Self { level, table }
    }
}

第 14 行：页表项 PTEntry 是 64 位长度的数据项，后面会实现一些具体方法针对 pfn 和 flags 两个位域进行操作。

第 26~29 行：页表 PageTable 包括两个成员，level 是该页表所在的级别，根页表是 0，以此类推；table 数组对应页表包含的页表项序列。然后来看 init 初始化方法，以页表对应页面的物理地址为开始指针，构造页表项数组类型。注意：此时还没有启用分页，所以直接用物理地址。

页表操作的重点是映射方法 map，它负责建立从虚拟地址到物理地址的映射，先来看基于 SV39 分页方案，MMU 映射的原理：

SV39 包含三级页表，寄存器 satp 保持着根页表（0 级）页表的基地址，当访问虚拟地址 VA 时，它的低 39 位有效，MMU 的工作过程：

截取虚拟地址 VA 的第 30 至 38 位总共 9 位，作为索引查询根页表，找到对应页表项，分析页表项的flags；
如果页表项包含的是下级页表，则重复 1 和 2 的过程，最后定位到目标物理页帧，VA 的低 12 位作为页内偏移，与物理页帧合成最终的物理地址，完成映射；
如果页表项就是 Leaf 节点 - 即大页映射，则直接把 VA 剩余部分作为页内偏移，合并成最终的物理地址，提前完成映射。SV39 可能包含的大页有两级，1G 粒度和 2M 粒度。

我们在页表上执行 map 操作的目的，就是设置页表去匹配上面 MMU 的工作机制。

第一节最后提到，本章我们只需要建立初始的地址空间，即只映射包含 SBI 和内核的 1G 区间范围。根页表（evel0 table）是通过 linker.lds 在内核布局中预留的一页，不用额外分配，剩下的工作就是建立这 1G 空间的直接映射和设置 satp 寄存器来启用页表。下面先解决映射的问题，下一节实现页表启用。

我们为地址空间映射设计一个名为 map 的方法，原型如下：

fn map(&mut self, mut va: usize, mut pa: usize, mut total_size: usize, best_size: usize, flags: usize);

涉及五个参数：

地址范围在虚拟空间中的开始位置，即虚拟地址 va；
地址范围在物理空间中的开始位置，即物理地址 pa；
地址范围的总长度 total_size；
期望按照哪一级粒度进行映射，可以是第一级 1G，第二级 2M 或第三级 4K，用 best_size 表示。第二章第二节中，就是基于第一级建立的 1G 大页映射。这个是期望，不是强制的。前三个参数必须按照 best_size 对齐；
映射的标志位集合 flags，决定映射的有效性、权限等等。

当前阶段的映射函数 map 非常简单，就是建立 1G 空间从虚拟到物理的映射，并且映射涉及的虚拟地址 va 和物理地址 pa 都是按照 1G 对齐的，所以 best_size 直接就是 1G，这样省略了很多额外的处理过程。等到了第四章重建地址空间映射时，情况会复杂的多，到时候我们再讨论不对齐的情况。

当前 map 方法的具体实现：

// page_table/src/lib.rs
impl PageTable<'_> {
    const fn entry_shift(&self) -> usize {
        ASPACE_BITS - (self.level + 1) * (PAGE_SHIFT - 3)
    }
    const fn entry_size(&self) -> usize {
        1 << self.entry_shift()
    }
    pub const fn entry_index(&self, va: usize) -> usize {
        (va >> self.entry_shift()) & (ENTRIES_COUNT - 1)
    }

    pub fn map(&mut self, mut va: usize, mut pa: usize,
        mut total_size: usize, best_size: usize, flags: usize
    ) -> PagingResult {
        let entry_size = self.entry_size();
        while total_size >= entry_size {
            let index = self.entry_index(va);
            if entry_size == best_size {
                self.table[index].set(pa, flags);
            } else {
                let mut pt = self.next_table_mut(index)?;
                pt.map(va, pa, entry_size, best_size, flags)?;
            }
            total_size -= entry_size;
            va += entry_size;
            pa += entry_size;
        }
        Ok(())
    }

    fn next_table_mut(&mut self, _index: usize) -> PagingResult<PageTable> {
        unimplemented!();
    }
}

第 3~5 行：方法 entry_shift 用来计算当前页表的页表项粒度，以 2^shift^ 表示。对于 SV39，ASPACE_BITS 是 39 位，这样 0 级根页表的页表项覆盖范围就是 1G，1 级页表的页表项对应 2M。

第 6~8 行：基于 entry_shift，计算页表项 entry 以数值方式表示的覆盖范围。

第 9~11 行：基于 entry_shift，把虚拟地址 VA 转化为当前页表中的对应索引值。

第 13~35 行：方法 map 的基本实现。参数 total_size 代表要映射的总范围，参数 best_size 则指明我们希望映射粒度到哪一级，可选值是 1G、2M 和 4K，如果选前两个值会建立大页映射。具体实现时，分别处理了直接大页映射和建立下级页表的情况。对于建立下级页表 next_table_mut，需要动态内存分配功能的支持，这里只预留了函数框架，等到第四章再补全，本章实验不会执行到这里。

现在页表的基本机制已经建立了，下面通过一个组件级的测试用例，验证页表功能，本章我们只需要验证第一级映射（即 level 0）。

// page_table/tests/test_early.rs
use axconfig::SIZE_1G;
use page_table::{PageTable, PAGE_KERNEL_RWX};

#[test]
fn test_early() {
    let boot_pt: [u64; 512] = [0; 512];

    let mut pt: PageTable = PageTable::init(boot_pt.as_ptr() as usize, 0);
    let _ = pt.map(0x8000_0000, 0x8000_0000, SIZE_1G, SIZE_1G, PAGE_KERNEL_RWX);
    let _ = pt.map(0xffff_ffc0_8000_0000, 0x8000_0000, SIZE_1G, SIZE_1G, PAGE_KERNEL_RWX);
    assert_eq!(boot_pt[2], 0x200000ef, "pgd[2] = {:#x}", boot_pt[2]);
    assert_eq!(boot_pt[0x102], 0x200000ef, "pgd[0x102] = {:#x}", boot_pt[0x102]);
}

在根目录下 Cargo.toml 中，members 中追加 "page_table"，执行 make test 测试：

Running tests/test_early.rs (target/debug/deps/test_early-45021e16a6b88d19)

running 1 test test test_early ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

ArceOS Tutorial Book

第二节 分页机制 - 页表和页表项

第二节分页机制 - 页表和页表项