rCore OS Note - Chapter 4 - 一只豆腐

该章节是目前最复杂的一个章节，涉及到操作系统的内存管理的策略和方法。在 no_std 裸机环境下， rCore 使用 buddy_system_allocator 为需要动态内存分配的数据结构提供 Global Allocator。该章节的主要目的就是实现一个 地址空间（Address Space） 抽象，并在内核中建立虚实地址空间的映射机制，给应用程序提供一个基于地址空间的安全虚拟内存环境并灵活使用内存。

现代计算机基本使用 分页内存管理，以使得内核始终以一个固定的极小单位管理应用数据，这既能利用插槽式的简单的内存分配算法避免生成 内存外碎片，又能使未使用的 内存内碎片 尽可能小以提高内存的使用率。关于内存地址映射个人觉得 rCore 讲的比较啰嗦， MIT 的 xv6 的教材很简略但很容易理解可以先阅读 xv6 book - Page tables 建立相关概念再阅读 rCore 的教材。

Address Space OS Details, rCore

0. 资料汇总

RISC-V
- RISC-V ELF psABI: Processor-specific application binary interface document.
- RISC-V Supervisor Binary Interface: Spec for SBI.
- RISC-V C API: RISC-V-specific predefined macros, function attributes and language extensions.
- RISC-V Assembly Programmer’s Manual: Document for pseudoinstructions and assembly directives.
- RISC-V Specifications:
  - Unprivileged Specification version 20191213
  - Privileged Specification version 20211203
- RISC-V ACLINT specification: ACLINT (Advanced Core Local Interruptor) specification defines a set of memory mapped devices which provide inter-processor interrupt and timer functionality for each HART of a multi-HART (or multi-processor) RISC-V platform.
- RISC-V Assembly Programmer’s Manual: Provide guidance to assembly programmers targeting the standard RISC-V assembly language.
rCore
- rCore 第四章相关内容的实现记录在 Github Tag: [ch4]
- rCore source code of labs for spring 2023: rCore-Tutorial-Guide-2023S Source Code
- rCore Concise Manual: rCore-Tutorial-Guide-2023S
- rCore Detail Book: rCore-Tutorial-Book-v3

1. Sv39 多级页表的机制

RISC-V address translation details, MIT xv6

rCore 和 xv6 都使用了 Sv39 模式，这意味着 64-bit 的 VA (Virtual Address) 仅有低端的 39 bits 是被使用的。而这 39 位又被划分为两部分，被称为 VPN (Virtual Page Number) 的高 27 位用于索引 PTE (Page Table Entry)， PTE 是存放在每个应用的 Page Table 中，由 44 位的 PPN (Physical Page Number) 与 10 位标志位组成，这 PTE 实际构成了虚拟地址与物理地址的索引关系。另外低 12 位是表示页内的偏移量，这是因为我们使用 分页内存管理，最小的内存单位是页，这低 12 位最终会与 PPN 组合成为实际的 56 位物理地址。

需要明确的是 \(One Page: 2^{12} = 4096\)，因而虚拟地址的低 12 位才被称作是页内的偏移量，因为 12 位正好构成了一个页的大小。

上图描述了三级页表的查询方式， Sv48 可以使用四级页表，具体的设计依具体情况而定。多级页表的构建是为了节省内存开销，我们只需要按需增添 PTE。我们可以通过三级页表进行逐级索引，依据上图由 L2 的 512 个一级页表可以索引， L1 的 \(512\times{512}\) 个二级页表，这样的开销会比直接映射的页表小得多。例如我们当前仅需要建立一个地址映射，那么只需要各使用 L2， L1， L0 三级页表中的一个 PTE，我们节省了 511 个 L1 PTE， \(511\times{512}\) 个 L0 PTE。

如果每个地址映射都需要经历三级查表效率肯定会低，因而 MMU 会提供 TLB (Translation Look-Aside Buffer) 缓存来加快映射查询，但需要注意的是，映射关系发生改变后缓存就失效了，我们需要通过 sfence.vma 指令刷新 TLB。

Translation process, rCore

在 rCore 中，虚拟地址 (VA, Virtual Address) 中的最小单位被称为 Page，其对应的物理地址 (PA, Physical Address) 中的最小单位被称为 Frame，这二者的关系可以从上图可以窥见一斑，二者大小一样都是 4096 Bytes。

2. Sv39 分页管理设计

2.1 frame allocator - 物理页帧管理

rCore 中内核直接管理了虚拟内存和物理内存。 Frame 所在的空间位于 ekernel 与 MEMORY_END 之间。 rCore 使用 struct StackFrameAllocator 实现 FRAME_ALLOCATOR，并开放给其他内核模块两个用以分配和回收物理地址 frame 的接口： frame_alloc 以及 frame_dealloc。值得注意的是 frame_alloc 返回的类型是封装 PhysPageNum 的 FrameTracker 类型，该类型实现了 Drop Trait，这是一种 RAII 的思想，当 FrameTracker 的声明周期结束，其包裹的 PhysPageNum 能通过编译器自动回收到 FRAME_ALLOCATOR。

// os/src/mm/frame_allocator.rs

pub struct FrameTracker {
    pub ppn: PhysPageNum,
}

impl Drop for FrameTracker {
    fn drop(&mut self) {
        frame_dealloc(self.ppn);
    }
}

内核访问物理页帧

为了让内核能访问实际的物理地址， rCore 设计了三种粒度的访问方式：基于 PTE，基于 Bytes，基于变量类型。至此，物理地址空间的分配以及访问的框架已经建成，后续需要做的就是构建虚拟地址与物理地址映射的 页表(Page Table)。

// os/src/mm/address.rs

impl PhysPageNum {
    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;
}

2.2 Page Table - 映射表构建

构建页表的基本单元就是 PTE(Page Table Entry)，这里有个关键概念需要澄清，页表的存储位置。其实从 xv6 的那张 RISC-V address translation details, MIT xv6 也可以看出，通过索引从 Lx 定位到的 PPN 会指向下一级 Page Table，这意味着 Page Table 实际上也是存储在具体的物理页帧上的，并且每个 PTE 对应唯一的一个 PPN。因而 rCore 对 Page Table 的数据结构的设计就包括了定位 Page Table 的 root_ppn 以及 Page Table 中包含的各个 PTE 项 frames。

估计是为了让 root_ppn 和 frames 的指向和含义统一才把 PTE 命名为 frame，个人感觉直接用 PTE 会清晰很多。这里 rCore 又提及 RAII 的思想， frames 内部变量通过 Vec 数据结构绑定 FrameTracker，可以保证声明周期结束后对 FrameTracker 的内存自动回收。

// os/src/mm/page_table.rs

pub struct PageTable {
    root_ppn: PhysPageNum,
    frames: Vec<FrameTracker>,
}

这样就不难理解 struct PageTable 初始化的流程了，每个 Page Table 都需要向 frame allocator 先申请一个物理页帧将其 PPN 作为 root_ppn 唯一标识。

2.3 建立 VA 与 PA 的映射关系

Page Table 必然是动态变化的，程序运行的时候会通过 Page Fault Trap 来实现对内存页的按需分配。当我们知道虚拟地址空间的某个 VA 的时候，需要通过前述的 Page Table 找到或建立一个关于物理页帧映射。 Xv6 中是通过 walk 函数实现的， rCore 提供了两个基础函数 find_pte_create 以及 find_pte，区别就在于是否在某一级页表的 PTE 未创建时创建一个新的 PTE。

// os/src/mm/address.rs

impl VirtPageNum {
    pub fn indexes(&self) -> [usize; 3] {
        let mut vpn = self.0;
        let mut idx = [0usize; 3];
        for i in (0..3).rev() {
            idx[i] = vpn & 511;
            vpn >>= 9;
        }
        idx
    }
}

// os/src/mm/page_table.rs

impl PageTable {
    fn find_pte_create(&mut self, vpn: VirtPageNum) -> Option<&mut PageTableEntry>;
    fn find_pte(&self, vpn: VirtPageNum) -> Option<&mut PageTableEntry>;
}

rCore 通过 indexes 解析 VPN (Virtual Page Number)，找到三级页表每一级中的 leaf PTE 的索引号。这里会用到 PTE 中的 Flags 部分的信息。标志位 V 表示当前的 PTE 为合法有效的，在建立新的 PTE 的时候需要更新该标志位，否则会引起 Page Fault。基于这几个函数， rCore 封装了两个更便利的函数方便 Page Table 的维护，用 map/unmap 为当前的 Page Table 增加或删除 PTE。

// os/src/mm/page_table.rs

impl PageTable {
    pub fn map(&mut self, vpn: VirtPageNum, ppn: PhysPageNum, flags: PTEFlags) {
        let pte = self.find_pte_create(vpn).unwrap();
        assert!(!pte.is_valid(), "vpn {:?} is mapped before mapping", vpn);
        *pte = PageTableEntry::new(ppn, flags | PTEFlags::V);
    }
    pub fn unmap(&mut self, vpn: VirtPageNum) {
        let pte = self.find_pte(vpn).unwrap();
        assert!(pte.is_valid(), "vpn {:?} is invalid before unmapping", vpn);
        *pte = PageTableEntry::empty();
    }
}

手动页表查询： Page Table 还实现了两个特殊的函数模仿 MMU 获取 Page Table。 from_token 直接读取 satp 寄存器中的 PPN 段获取一个 Page Table，之后就能直接通过 translate 函数得到 VPN 对应的第三级的 PTE。

3. 地址空间与抽象

rCore 抽象了两种概念来管理整个虚拟内存及其映射的物理内存。

Address space abstraction, HangX-Ma

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

rCore 使用 sruct MapArea 表示逻辑段。
- vpn_range 表明该逻辑段的在虚拟地址的范围以及长度；
- map_type 则表示了虚拟地址和物理地址的映射办法，直接映射（MapType::Identical）又或是通过 FRAME_ALLOCATOR 随机分配物理帧（MapType::Framed）（外设地址都是直接映射的，这样区分有助于后续的应用拓展）；
- 既然区分了映射方式，存储映射关系的数据结构也会不同， data_frames 用于存储 leaf PTE 的 PPN 与其对应的 VPN 之间的关系，仅用在 Framed 映射办法。
- 最后的 map_perm 其实就和 Linux 系统的 RWXU 的含义基本接近了。
```
// os/src/mm/memory_set.rs

pub struct MapArea {
    vpn_range: VPNRange,
    data_frames: BTreeMap<VirtPageNum, FrameTracker>,
    map_type: MapType,
    map_perm: MapPermission,
}
```
地址空间：一系列有关联的逻辑段

rCore 通过 struct MemorySet 封装这些逻辑段，这是因为虽然逻辑段本身是连续的一段虚拟地址，但多个逻辑段之间可能并不是连续的。注意这里的 page_table 是一个 Root Page Table，包含了该所有的 PTE 的物理页帧，而 areas 则包含了数据所在的物理页帧，这样的的设计构成了一个地址空间所需的所有的物理页帧。
```
  // os/src/mm/memory_set.rs

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

3.1 内核地址空间

Sv39 规定 64 位虚拟地址的 [63:39] 这 25 位必须和第 38 位相同，否则 MMU 会直接认定它是一个不合法的虚拟地址。因而虚拟地址空间可以被划分为低地址的 \(2^{39}\) bytes (512 GB)，以及当第 38 位为 1 时的 512 GB，分别称为 High Half 以及 Low Half。 rCore 设计的内核空间如下图所示。

Kernel address space high half, rCore

Kernel address space low half, rCore

3.2 应用地址空间

rCore 设计的内核空间如下图所示，具体含义和解释见 rCore Tutorial 相关章节的内容。需要注意的是，几个具有不同访问权限的逻辑段之间需要通过页面对齐进行限制与区分。

Application address space, rCore

4. 基于地址空间的分时多任务

4.1 Trampoline

Trampoline 部分的代码是由原来的 trap.S 更改得到的，其特殊之处在于 Kernel 以及 App 的地址空间的同一位置都有这一段数据，并且被映射到同一个存放该段代码的物理页帧。这种设计保证内核态和用户态的虚拟地址空间的切换使用的映射方式相同，保证这段切换地址空间的指令控制流可以平滑执行。为方便实现， rCore 直接在多级页表中插入了对 trampoline 的映射而不是新增一个逻辑段。

另外这里提到了虚拟地址空间的切换，这是 trampoline 命名的由来以及其需要解决的问题。由于 RISC-V 仅提供了一个 sscratch 寄存器用以周转数据，但开启虚拟映射后，应用地址空间切换到内核应用空间需要用到 satp 寄存器，我们无法通过一个寄存器完成 satp 与 sp 两个寄存器信息的流转。因而，比较合适的办法就是将应用的 Trap Context 保存在每个应用的用户态虚拟地址空间的 High Half，紧贴着 Trampoline。

4.2 改进 syscall

rCore 的手册更改了 sys_write 系统调用，通过 translated_byte_buffer 在内核空间中开辟了一个可以访问应用数据的区域（实际上是将应用数据从用户态虚拟地址空间拷贝到了内核态虚拟地址空间以供内核访问）。相应的，前述章节需要访问应用态数据的系统调用均需要通过这种间接的方式进行数据的访问与更改。这也就是 sys_get_time 以及 sys_task_info 在第四章失效的原因。

5. 课后练习

5.1 编程练习

TODO: 这部分回头再说

5.2 实验练习

重写 sys_get_time 和 sys_task_info

// os/src/syscall/process.rs

pub fn sys_get_time(ts: *mut TimeVal, _tz: usize) -> isize {
    let us = get_time_us();
    let dst_vec = translated_byte_buffer(
        current_user_token(),
        ts as *const u8, core::mem::size_of::<TimeVal>()
    );
    let ref time_val = TimeVal {
            sec: us / 1_000_000,
            usec: us % 1_000_000,
    };
    let src_ptr = time_val as *const TimeVal;
    for (idx, dst) in dst_vec.into_iter().enumerate() {
        let unit_len = dst.len();
        unsafe {
            dst.copy_from_slice(core::slice::from_raw_parts(
                src_ptr.wrapping_byte_add(idx * unit_len) as *const u8,
                unit_len)
            );
        }
    }
    0
}

pub fn sys_task_info(ti: *mut TaskInfo) -> isize {
    let dst_vec = translated_byte_buffer(
        current_user_token(),
        ti as *const u8, core::mem::size_of::<TaskInfo>()
    );
    let ref task_info = TaskInfo {
        status: get_current_task_status(),
        syscall_times: get_current_task_syscall_times(),
        time: get_current_task_time_cost(),
    };
    // println!("[kernel]: time {} syscall_time {}", task_info.time, task_info.syscall_times[super::SYSCALL_GET_TIME]);
    let src_ptr = task_info as *const TaskInfo;
    for (idx, dst) in dst_vec.into_iter().enumerate() {
        let unit_len = dst.len();
        unsafe {
            dst.copy_from_slice(core::slice::from_raw_parts(
                src_ptr.wrapping_byte_add(idx * unit_len) as *const u8,
                unit_len)
            );
        }
    }
    0
}

具体实现可参考 commit#b1ac23a 以及 commit#db31455

mmap 和 munmap 匿名映射

// os/src/syscall/process.rs

/// port: page permission [2:0] X|W|R
pub fn sys_mmap(start: usize, len: usize, port: usize) -> isize {
    if start % PAGE_SIZE != 0 /* start need to be page aligned */ || 
        port & !0x7 != 0 /* other bits of port needs to be zero */ ||
        port & 0x7 ==0 /* No permission set, meaningless */ ||
        start >= MAXVA /* mapping range should be an legal address */ {
        return -1;
    }

    // check the range [start, start + len)
    let start_vpn = VirtAddr::from(start).floor();
    let end_vpn = VirtAddr::from(start + len).ceil();
    let vpns = VPNRange::new(start_vpn, end_vpn);
    for vpn in vpns {
       if let Some(pte) = get_current_task_page_table(vpn) {
            // we find a pte that has been mapped
            if pte.is_valid() {
                return -1;
            }
       }
    }
    // all ptes in range has pass the test
    create_new_map_area(
        start_vpn.into(),
        end_vpn.into(),
        MapPermission::from_bits_truncate((port << 1) as u8) | MapPermission::U
    );
    0
}


/// munmap the mapped virtual addresses
pub fn sys_munmap(start: usize, len: usize) -> isize {
    if start >= MAXVA || start % PAGE_SIZE != 0 {
        return -1;
    }
    // avoid undefined situation
    let mut mlen = len;
    if start > MAXVA - len {
        mlen = MAXVA - start;
    }
    unmap_consecutive_area(start, mlen)
}

// os/src/task/mod.rs

//* ch4-lab2, mmap, munmap
pub fn get_current_task_page_table(vpn: VirtPageNum) -> Option<PageTableEntry> {
    let inner = TASK_MANAGER.inner.exclusive_access();
    let current = inner.current_task;
    inner.tasks[current].memory_set.translate(vpn)
}

pub fn create_new_map_area(start_va: VirtAddr, end_va: VirtAddr, perm: MapPermission) {
    let mut inner = TASK_MANAGER.inner.exclusive_access();
    let current = inner.current_task;
    inner.tasks[current].memory_set.insert_framed_area(start_va, end_va, perm);
}

pub fn unmap_consecutive_area(start: usize, len: usize) -> isize {
    let mut inner = TASK_MANAGER.inner.exclusive_access();
    let current = inner.current_task;
    let start_vpn = VirtAddr::from(start).floor();
    let end_vpn = VirtAddr::from(start + len).ceil();
    let vpns = VPNRange::new(start_vpn, end_vpn);
    for vpn in vpns {
        if let Some(pte) = inner.tasks[current].memory_set.translate(vpn) {
            if !pte.is_valid() {
                return -1;
            }
            inner.tasks[current].memory_set.get_page_table().unmap(vpn);
        } else {
            // Also unmapped if no PTE found
            return -1;
        }
    }
    0
}

具体实现可参考 commit#5e57b47 以及 commit#165bda8

PREVIOUSrCore OS Note - Chapter 3

NEXTrCore OS Note - Chapter 5