rCore Lab2(Chapter4)

刚开始像做 Lab1 那样随便看了看，结果看完立马就忘了，概念有点多，于是认真记一下。

---

基础概念

分页内存管理

页表实现

Page Table

• 页面（Page）：每个应用的地址空间被分成的小块

• 页帧（Frame）：可用的物理内存被分成的小块

• 虚拟页号（VPN, Virtual Page Number）

• 物理页号（PPN, Physical Page Number）

• 页表（Page Table）：每个应用有一个页表，用于 VPN 与 PPN 转换，其中每个 VPN 也有一组保护位（rwx）表示权限。页表同样存放在内存中

• 逻辑段：由多个虚拟页面组成，在应用视角是一块连续内存

多级页表：Trie 实现

默认 MMU（Memory Management Unit）未启用，需修改 CSR satp

satp

MODE：页表模式，0 表示访问物理地址，8 表示 SV39 虚拟地址 PPN：根页表的物理页号

地址格式

Address Format

单个页面大小设置为 4KiB，则如图 Page Offset 为 12 位

SV39 分页模式下虚拟地址只有 39 位有效长度，则只有最低 256 GiB（38 位为 0），最高 256 GiB（38 位为 1）有效

页表项

PTE（Page Table Entry）

PTE

其中 \([53:10]\) 为 PPN，V(Valid) 表示是否合法，R/W/X 代表 读/写/执行，U(User) 表示是否允许 U 特权级访问

多级页表

虚拟地址 VA 有 39 位，则 VPN 有 \(2^{27}\) 种，如果存储所有的 PTE 则需大量内存，因此可以使用 Trie 动态插入。

将 VPN 分为 3 段，则每段 9 位，对应到 Trie 上则有 512 个 子节点，对于叶节点每个子节点对应一个 PTE，大小 8 字节，正好可以放进一个物理页帧内，则用页帧表示 Trie 的一个节点；而非叶节点每一个子节点对应一个节点，即用 PPN 表示，此即三级页表。

对于非叶节点，此页帧其中每一个 PTE的表项中，V 为 0 表示无效，V 为 1 且 R/W/X 均为 0 表示其指向下一级页表，V 为 1 且 R/W/X 不全为 0 则其对应一个合法的 PTE。

• 快表（TLB）：相当于多级页表的一个 Cache，在修改 CSR satp 或修改一个 PTE 后失效，可以使用 sfence.vma 手动刷新整个或其中一个映射项

---

管理 SV39 多级页表

• 物理页帧管理器：StackFrameAllocator

pub struct StackFrameAllocator {
    current: usize,         // 空闲内存的起始物理页号
    end: usize,             // 空闲内存的结束物理页号
    recycled: Vec<usize>,   // 回收的 PPN
}

impl FrameAllocator for StackFrameAllocator {
    // 申请 / 回收
    fn alloc(&mut self) -> Option<PhyPageNum>;
    fn dealloc(&mut self, ppn: PhysPageNum);
}

// 公共接口
pub fn frame_alloc() -> Option<FrameTracker>;
pub fn frame_dealloc(ppn: PhysPageNum);

• 物理页帧（PPN 的包装）：FrameTracker

// 实现了 Drop Trait 自动回收
pub struct FrameTracker {
    pub ppn: PhysPageNum,
}

多级页表实现

如之前所说，页表的每一个节点都存在一个 Frame 中

• 页表根节点

pub struct PageTable {
    root_ppn: PhysPageNum,
    frames: Vec<FrameTracker>,  // 保存所有节点（包括根节点），方便自动回收
}

impl PageTable {
    // 页表插入 / 删除接口
    pub fn map(&mut self, vpn: VirtPageNum, ppn: PhysPageNum, flags: PTEFlags);
    pub fn unmap(&mut self, vpn: VirtPageNum);
}

在启用分页模式后，S 和 U 特权级下访问内存都需要经过 MMU 翻译，则需要提前在页表中插入相应的 VPN -> PPN 映射关系。这里采用恒等映射（VPN = PPN）

内核访问内存

impl PhysPageNum {
    // 通过 `core::slice::from_raw_parts_mut` 将 Frame 转换为不同类型的切片
    pub fn get_pte_array(&self) -> &'static mut [PageTableEntry];
    pub fn get_bytes_array(&self) -> &'static mut [u8];
    pub fn get_mut<T>(&self) -> &'static mut T;
}

impl PageTable {
    // 在页表中查找 PTE，前者在不存在时新建
    fn find_pte_create(&mut self, vpn: VirtPageNum) -> Option<&mut PageTableEntry>;
    fn find_pte(&self, vpn: VirtPageNum) -> Option<&mut PageTableEntry>;
}

• 手动查询

impl PageTable {
    // 手动由 satp 创建页表并提供查询
    pub fn from_token(satp: usize) -> Self;
    pub fn translate(&self. vpn: VirPageNum) -> Option<PageTableEntry>;
}

---

内核与应用的地址空间

实现地址空间抽象

• 逻辑段：一段连续地址的虚拟内存

pub struct MapArea {
    vpn_range: VPNRange,    // 虚拟页号的连续区间
    data_frames: BTreeMap<VirtPageNum, FrameTracker>,   // VPN PPN 映射方式
    map_type: MapType,          // 映射类型
    map_perm: MapPermission,    // 访问权限
}

pub enum MapType {
    Identical,  // 恒等映射
    Framed,     // 随机映射
}

• 地址空间：一系列有关联的不一定连续的逻辑段，可视为一个应用或内核的全部空间

pub struct MemorySet {
    page_table: PageTable,
    areas: Vec<MapArea>,
}

impl MemorySet {

    pub fn new_bare() -> Self;

    // 在当前地址空间插入一个新的逻辑段，可选初始化数据（映射方式为 Framed）
    fn push(&mut self, mut map_area: MapArea, data: Option<&[u8]>);

    // 调用 push 在当前地址空间插入一个逻辑段（映射方式为 Framed）
    pub fn insert_framed_area(&mut self, start_va: VirtAddr, end_va: VirtAddr, permission: MapPermission);

    pub fn new_kernal() -> Self;    // 生成内核的地址空间
    pub fn from_elf(elf_data: &[u8]) -> (Self, usize, usize);   // 生成 elf 文件对应的地址空间
}

impl MapArea {
    pub fn new(start_va: VirtAddr, end_va: VirtAddr, map_type: MapType, map_perm: MapPermission) -> Self;

    // 在对应的页表中添加或删除逻辑段
    pub fn map(&mut self, page_table: &mut PageTable);
    pub fn unmap(&mut self, page_table: &mut PageTable);

    // 将数据拷贝到当前逻辑段在页表中对应的位置
    pub fn copy_data(&mut self, page_table: &mut PageTable, data: &[u8]);

    // 根据 MapType 映射，是 map / unmap 的基础
    pub fn map_one(&mut self, page_table: &mut PageTable, vpn: VirtPageNum);
    pub fn unmap_one(&mut self, page_table: &mut PageTable, vpn: VirtPageNum);
}

内核地址空间

在 SV39 分页模式下，内核访问内存也经过 MMU 翻译，因此需要为内核构造一个地址空间，允许内核各数据段能够正常访问，包含所有应用的内核栈和一个跳板（Trampoline）（后面会提到）

通过 MMU 检查的高 256GiB 与 低 256GiB：

Kernel Address Space (High)

Kernel Address Space (Low)

保护页面（Guard Page）：当应用内核栈溢出时被访问到即引发异常

根据地址空间分布就可以实现 MemorySet 中的 new_kernel() 函数了

应用地址空间

在启用分页模式后，应用访问的为虚拟地址，所有应用可以使用同一个链接脚本。起始地址 BASE_ADDRESS 设为 0x00010000（0x0 通常代表空指针）

应用地址空间布局：

Application Address Space

加载应用的 loader 模块：

pub fn get_num_app() -> usize;

pub fn get_app_data(app_id: usize) -> &'static [u8];

build.rs 生成的应用保留 ELF 逻辑段信息，则可以通过外部 crate 进行解析：

impl MemorySet {
    pub fn from_elf(elf_data: &[u8]) -> (Self, usize, usize);
}

---

分页模式下任务切换

切换 satp 导致多级页表不同，而切换 satp 后 pc 只是简单地自增，则要求前后指令在两个页表的映射下地址连续。

如之前所述，Trap 上下文需要放在应用地址空间中而非内核栈，因为在保存到内核栈前，我们需要先切换地址空间（token 写入 satp），保存内核栈栈顶地址，则需要两个 CSR，而 RISC-V 只提供了一个 sscratch

因此，__alltraps 和 __restore 也要进行一定的修改

为了保证页表切换前后指令的连续，将 trap.S 存在跳板段，而对于内核和应用跳板都处于同一个位置，则可以连续运行

---

编程作业

重写 sys_get_time 和 sys_task_info

首先注意到，sys_get_time 中的 ts 是应用视角的地址，而在实际的 syscall 调用中系统处于内核态，这也是源函数失效的原因

因此，我们需要把 ts 转为内核态下的地址，为了方便可以新增一个从指定 token 进行翻译的函数：

// os/src/mm//mod.rs
pub fn translate_by_token(token: usize, va: VirtAddr) -> Option<PhysAddr> {
    let ppn = PageTable::from_token(token).translate(va.floor())?.ppn();
    Some(PhysAddr::from(PhysAddr::from(ppn).0 + va.page_offset()))
}

于是我们就可以轻松实现 sys_get_time：

// os/src/syscall/process.rs
pub fn sys_get_time(_ts: *mut TimeVal, _tz: usize) -> isize {
    let us = get_time_us();
    let ts_pa = translate_by_token(current_user_token(), VirtAddr::from(_ts as usize)).unwrap().0 as *mut TimeVal;
    unsafe {
        *ts_pa = TimeVal {
            sec: us / 1_000_000,
            usec: us % 1_000_000,
        };
    }
    0
}

于是 sys_task_info 同理，在 lab1 的基础上加上地址的翻译即可：

// os/src/syscall/process.rs
pub fn sys_task_info(ti: *mut TaskInfo) -> isize {
    let ti_pa = translate_by_token(current_user_token(), VirtAddr::from(ti as usize)).unwrap().0 as *mut TaskInfo;
    unsafe {
        *ti_pa = TaskInfo {
            status: get_current_task_status(),
            syscall_times: get_syscall_times(),
            time: get_current_run_time(),
        }
    }
    0
}

然而我在 lab1 中用的奇怪 get_time_ms 方法在 lab2 里面本地测试可以通过，Github CI 却过不了，最终写成朴素的 get_time_us() / 1000 就过了。。为此浪费了几小时（Github CI 这个自动测试是真的慢）

实现 mmap 和 munmap

刚开始想着自己用 frame_alloc 实现，结果写了一大堆还跑不起来。。

发现应用的 TaskControlBlock 的 MemorySet 中存在 insert_framed_area 方法，直接调用即可。主要接口在 TaskManager 中实现

// os/src/syscall/process.rs
pub fn sys_mmap(start: usize, len: usize, port: usize) -> isize {
    task_mmap(start, len, port)
}

pub fn sys_munmap(start: usize, len: usize) -> isize {
    task_munmap(start, len)
}

// os/src/task/mod.rs
impl TaskManager {
    fn task_mmap(&self, start: usize, len: usize, port: usize) -> isize {
        let start_va = VirtAddr::from(start);
        let end_va = VirtAddr::from(start + len);
        if !start_va.aligned() || (port & !0x7) != 0 || (port & 0x7) == 0 {
            return -1;
        }
        let mut inner = self.inner.exclusive_access();
        let current_task = inner.current_task;
        let memory_set = &mut inner.tasks[current_task].memory_set;
        let start_vpn = start_va.floor();
        let end_vpn = end_va.ceil();
        for vpn in VPNRange::new(start_vpn, end_vpn) {
            if let Some(pte) = memory_set.translate(vpn) {
                if pte.is_valid() {
                    return -1;
                }
            }
        }
        let map_perm = MapPermission::from_bits((port as u8) << 1).unwrap() | MapPermission::U;
        memory_set.insert_framed_area(start_va, end_va, map_perm);
        0
    }

    fn task_munmap(&self, start: usize, len: usize) -> isize {
        let start_va = VirtAddr::from(start);
        let end_va = VirtAddr::from(start + len);
        if !start_va.aligned() {
            return -1;
        }
        let mut inner = self.inner.exclusive_access();
        let current_task = inner.current_task;
        let memory_set = &mut inner.tasks[current_task].memory_set;
        let start_vpn = start_va.floor();
        let end_vpn = end_va.ceil();
        for vpn in VPNRange::new(start_vpn, end_vpn) {
            if let Some(pte) = memory_set.translate(vpn) {
                if !pte.is_valid() {
                    return -1;
                }
            } else {
                return -1;
            }
        }
        memory_set.unmap(start_vpn, end_vpn);
        0
    }
}

pub fn task_mmap(start: usize, len: usize, port: usize) -> isize {
    TASK_MANAGER.task_mmap(start, len, port)
}

pub fn task_munmap(start: usize, len: usize) -> isize {
    TASK_MANAGER.task_munmap(start, len)
}

其中为实现方便在 MemorySet 中增添了一个 unmap 接口：

// os/src/mm/memory_set.rs
impl MemorySet {
    pub fn unmap(&mut self, start_vpn: VirtPageNum, end_vpn: VirtPageNum) {
        for vpn in VPNRange::new(start_vpn, end_vpn) {
            self.page_table.unmap(vpn);
        }
    }
}

Github Repository