分页机制-支持多级页表 - ArceOS Tutorial Book

第一节分页机制- 支持多级页表

回顾一下第二章的第二节，当时我们实现了最基本的页表管理机制，那时还只是支持一级页表，即仅有根页表。这个根页表占用的内存页是内核预先分配的，操作时只要查出页表项的偏移，然后进行设置即可。这个单级的页表机制在管理上非常的粗放，也仅仅就是适应内核在启动的早期阶段对分页的需求。本节我们就来支持多级页表管理，一方面对虚拟地址空间进行更细粒度的控制，另一方面把设备 mmio 地址范围也映射到虚拟空间以纳入管理。

在讨论如何支持多级页表之前，我们需要先解决地址空间映射中可能遇到的对齐问题：

之前的 map 实现十分简单，只是映射了 1G，并且 va/pa 地址以及总长度 total_size 都是按 1G 对齐的。但是如果地址范围可能出现不对齐的情况，这是指开始/结束地址没有按照 best_size 对齐或者总长度就小于 best_size。例如我们期望按照 2M 的粒度进行映射（即 best_size 是 2M，如上图所示），但是起止地址都没有按照 2M 对齐，那就需要把映射范围分成三个部分：把中间按照 2M 对齐的部分截出来，按照 2M 的 best_size 进行映射；把前后两个剩余部分按照 4K 的粒度单独映射。

注：对于map方法来说，地址和长度至少是按照4K的基本页面长度对齐的，否则就是无效参数。

为了让我们的 map 方法更加通用，还需要增加一个 map_aligned 方法，由它们配合解决上面不对齐的情况。

对组件 page_table 进行扩展，首先是改造 PageTable::map(...) 方法：

// page_table/src/lib.rs
pub struct PageTable<'a> {
    pub fn map(&mut self, mut va: usize, mut pa: usize,
        mut total_size: usize, best_size: usize, flags: usize
    ) -> PagingResult {
        let mut map_size = best_size;
        if total_size < best_size {
            map_size = PAGE_SIZE;
        }
        let offset = align_offset(va, map_size);
        if offset != 0 {
            assert!(map_size != PAGE_SIZE);
            let offset = map_size - offset;
            self.map_aligned(va, pa, offset, PAGE_SIZE, flags)?;
            va += offset;
            pa += offset;
            total_size -= offset;
        }

        let aligned_total_size = align_down(total_size, map_size);
        total_size -= aligned_total_size;
        let ret = self.map_aligned(va, pa, aligned_total_size, map_size, flags)?;
        if total_size != 0 {
            va += aligned_total_size;
            pa += aligned_total_size;
            self.map_aligned(va, pa, total_size, PAGE_SIZE, flags)
        } else {
            ret
        }
    }
}

第 6~9 行：如果映射范围总长度小于 best_size，后面都直接按照 4K 页粒度映射。

第 10~18 行：如果地址范围的头部存在不对齐的部分，先按 4K 页粒度映射。

第 20~22 行：调用 map_aligned 方法按照 best_size 进行映射。

第 24~26 行：如果还存在剩余部分尚未映射，那这部分也是未对齐的部分，按照 4K 页粒度映射。

然后看一下新增的辅助方法 map_aligned 的实现，它在很大程度上继承了旧版 map 方法的逻辑：

// page_table/src/lib.rs
pub struct PageTable<'a> {
    fn map_aligned(&mut self, mut va: usize, mut pa: usize,
        mut total_size: usize, best_size: usize, flags: usize
    ) -> PagingResult {
        assert!(is_aligned(va, best_size));
        assert!(is_aligned(pa, best_size));
        assert!(is_aligned(total_size, best_size));
        let entry_size = self.entry_size();
        let next_size = min(entry_size, total_size);
        while total_size >= next_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, next_size, best_size, flags)?;
            }
            total_size -= next_size;
            va += next_size;
            pa += next_size;
        }
        Ok(())
    }
}

第 6~8 行：检查映射范围的虚拟/物理地址以及总长度是否对 best_size 对齐。

第 9 行：当前级别上，每个 entry 对应的地址范围长度。例如对于 Sv39 的顶级页表（level 0），它的 entry 长度就是 1G。

第 10 行：如果要求映射的总长度比当前级别页表的 entry 长度还小，那么映射就不会发生在本级页表，那将在下一级甚至更低级的页表上发生，所以这个代表映射步长的 next_size 需要取 entry_size 和 total_size 的最小值。

第 11~22 行：以 next_size 为步长，为当前页表的每一个页表项 entry 建立映射。这里有两种情况：一是期望在本级完成映射，按照第 14 行的方式直接设置 entry；二是要求在更低级别的页表上建立映射，那么首先要获得下级页表的引用，然后递归调用 map 方法去建立映射。

取得下级页表有两个方法 next_table_mut 和 next_table，它们的区别是前者在页表不存在时，将会动态申请内存页创建页表。

// page_table/src/lib.rs
pub struct PageTable<'a> {
    fn next_table_mut(&mut self, index: usize) -> PagingResult<PageTable> {
        if self.table[index].is_unused() {
            let table = Self::alloc_table(self.level + 1);
            self.table[index].set(table.root_paddr(), PAGE_TABLE);
            Ok(table)
        } else {
            self.next_table(index)
        }
    }
    pub fn next_table(&self, index: usize) -> PagingResult<PageTable> {
        assert!(self.table[index].is_present());
        let pa = self.table[index].paddr();
        let va = phys_to_virt(pa);
        Ok(Self::init(va, self.level + 1))
    }
    pub fn alloc_table(level: usize) -> Self {
        let layout = Layout::from_size_align(PAGE_SIZE, PAGE_SIZE).unwrap();
        let ptr = unsafe { alloc::alloc::alloc_zeroed(layout) };
        Self::init(ptr as usize, level)
    }
    pub fn root_paddr(&self) -> usize {
        virt_to_phys(self.table.as_ptr() as usize)
    }
    pub fn entry_at(&self, index: usize) -> PTEntry {
        self.table[index]
    }
}

第 18~22 行：负责创建页表，基于 Rust 标准的 alloc 方法先申请一页，注意长度和对齐都是 PAGE_SIZE 即 4K。

最后补充一下新增的对外部 crate 的引用和对页表项的扩展：

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

use core::cmp::min;
use core::alloc::Layout;
use axconfig::{PAGE_SHIFT, PAGE_SIZE, ASPACE_BITS};
use axconfig::{is_aligned, align_offset, align_down};
use axconfig::{phys_to_virt, virt_to_phys, pfn_phys};

extern crate alloc;

impl PTEntry {
    fn is_present(&self) -> bool {
        (self.0 as usize & _PAGE_V) == _PAGE_V
    }
    fn is_unused(&self) -> bool {
        self.0 == 0
    }
    pub fn paddr(&self) -> usize {
        pfn_phys(self.0 as usize >> PAGE_PFN_SHIFT)
    }
    pub fn flags(&self) -> usize {
        self.0 as usize & ((1 << PAGE_PFN_SHIFT) - 1)
    }
 }

现在多级页表的功能实现完毕，下面通过一个测试用例来验证我们的实现：

// page_table/tests/test_final.rs
use axconfig::SIZE_2M;
use page_table::{PageTable, PAGE_KERNEL_RWX};

#[test]
fn test_final() {
    let final_pgd: [u64; 512] = [0; 512];

    let mut pgd: PageTable = PageTable::init(final_pgd.as_ptr() as usize, 0);
    let _ = pgd.map(0xffff_ffc0_8020_a000, 0x8020_a000, 0x7df6000, SIZE_2M, PAGE_KERNEL_RWX);
    let pgd_index = pgd.entry_index(0xffff_ffc0_8020_a000);
    assert_eq!(pgd_index, 258);
    let pmd = pgd.next_table(pgd_index).unwrap();
    let pmd_index = pmd.entry_index(0xffff_ffc0_8020_a000);
    assert_eq!(pmd_index, 1);
    let pt = pmd.next_table(pmd_index).unwrap();
    let pt_index = pt.entry_index(0xffff_ffc0_8020_a000);
    assert_eq!(pt_index, 10);
    assert_eq!(pt.entry_at(pt_index).paddr(), 0x8020_a000);
    assert_eq!(pt.entry_at(pt_index).flags(), PAGE_KERNEL_RWX);
}

执行测试 make test，查看所有测试用例执行结果，全部通过！

ArceOS Tutorial Book

第一节 分页机制- 支持多级页表

第一节分页机制- 支持多级页表