> For the complete documentation index, see [llms.txt](https://rcore.gitbook.io/rust-os-docs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://rcore.gitbook.io/rust-os-docs/nei-cun-guan-li-mo-kuai.md). # 内存管理模块 【部分内容已经过时】 ## 概述 内存管理模块的职责是完成内存资源的管理。它主要建立在硬件提供的页机制之上，为使用者提供共享内存、页交换、写时复制等高级功能，并方便不同进程之间内存资源的管理。此模块功能相当于ucore lab3。 具体而言，使用者需要实现以下接口： * 页表（项） * 页交换算法 即可使用模块提供的以下功能： * 页交换 * 写时复制 * 共享内存 * 内存管理器 ## 实现 此模块作为独立的crate存在，代码位于：`crate/memory` src目录结构及各文件功能如下： ``` . ├── lib.rs 根模块 ├── addr.rs 定义基本数据类型 ├── cow.rs 写时复制和共享内存 ├── memory_set.rs 内存管理器 ├── paging 页表 │   ├── mock_page_table.rs 页表mock实现 │   └── mod.rs 页表接口 └── swap 交换机制 ├── mod.rs 接口定义和交换框架的实现 ├── mock_swapper.rs 交换到内存的实现 ├── fifo.rs FIFO算法 └── enhanced_clock.rs 改进时钟算法 ``` 模块内为页表接口提供了模拟实现，因此就可以为建立在其上的各种算法编写单元测试，使用以下命令即可运行： ```bash cd crate/memory rustup override set nightly-2018-09-13 cargo test ``` ### 页表接口 位于`src/paging/mod.rs`，定义了两个trait：`PageTable`,`Entry` ```rust /// （可修改的）页表接口 pub trait PageTable { /// 关联类型，指向一个Entry接口的实现 type Entry: Entry; /// 映射一个虚拟页到一个物理帧，返回该页对应的页表项，可做进一步的修改 fn map(&mut self, addr: VirtAddr, target: PhysAddr) -> &mut Self::Entry; /// 取消一个虚拟页的映射 fn unmap(&mut self, addr: VirtAddr); /// 获取一个虚地址在页表中对应的页表项 /// TODO：目前没考虑非法输入，会导致page fault fn get_entry(&mut self, addr: VirtAddr) -> &mut Self::Entry; /// 以下仅用于mock页表的测试 fn get_page_slice_mut<'a,'b>(&'a mut self, addr: VirtAddr) -> &'b mut [u8]; fn read(&mut self, addr: VirtAddr) -> u8; fn write(&mut self, addr: VirtAddr, data: u8); } /// 页表项接口 pub trait Entry { /// 【重要】执行TLB flush使之前的修改生效 fn update(&mut self); // 获取状态位信息 fn accessed(&self) -> bool; fn dirty(&self) -> bool; fn writable(&self) -> bool; fn present(&self) -> bool; fn user(&self) -> bool; fn execute(&self) -> bool; // 修改状态位信息 fn clear_accessed(&mut self); fn clear_dirty(&mut self); fn set_writable(&mut self, value: bool); fn set_present(&mut self, value: bool); fn set_user(&mut self, value: bool); fn set_execute(&mut self, value: bool); // 获取和设置映射的物理帧 fn target(&self) -> PhysAddr; fn set_target(&mut self, target: PhysAddr); // 用于写时复制的状态位 fn writable_shared(&self) -> bool; fn readonly_shared(&self) -> bool; fn set_shared(&mut self, writable: bool); fn clear_shared(&mut self); // 用于交换机制的状态位 fn swapped(&self) -> bool; fn set_swapped(&mut self, value: bool); } ``` 读者可查看`MockPageTable`的实现，了解接口的具体使用方法。 ### 页表的具体实现 x86\_64/RV32下的实现位于：`kernel/src/arch/../paging.rs`，其实只是套了层壳，诸如map等复杂操作的实现位于x86\_64/riscv库中。 64位下的页表由于层数较多，难以像ucore for x86\_32的实现一样，预先将每个页表节点分配到固定的物理帧上，并建立描述结构。为了方便页表本身的编辑，我们使用**自映射机制**，这样页表中的每个节点都映射到唯一的虚地址。并使用**物理帧分配器**`FrameAllocator`动态分配页表本身占用的物理内存。 关于自映射机制的实现细节，推荐阅读 [Page Tables | Writing an OS in Rust](https://os.phil-opp.com/first-edition) ，并配合[x86\_64库中的实现](https://docs.rs/x86_64/0.2.11/x86_64/structures/paging/index.html)，加深理解。 RISCV32中基本继承了x86\_64的实现方式。不过值得注意的是：**RISCV下的页表规范阻碍了自映射的实现。**原因是RISCV页表项中的flags，明确表示它指向的是数据页（VRW），还是下层页表（V）。假如把一个二级页表项，当做一级页表项来解读，就会触发异常，而这是自映射机制中必须的操作。为了绕开这个问题，就要求**在访问一级页表虚地址期间，将它所对应的二级页表项flags置为VRW**。此外，为了访问二级页表本身，还需要再加一个自映射的二级页表项，其flags为VRW。 ### 写时复制 TODO 详见`cow.rs` ### 交换机制 位于`swap/mod.rs`，首先定义了以下接口： * SwapManager：实现具体的页交换算法，本质是一个所有可交换页的优先队列 * Swapper：交换的具体执行者，负责将数据换入/换出到其它存储设备 其它3个文件都是对上述接口的实现。 基于上述接口，定义了实现交换操作的扩展结构： ```rust SwapExt ``` 使用时，构造一个SwapExt结构套在原有的PageTable结构外面，例如： ```rust let pt = MockPageTable::new(); let pt = SwapExt::new(pt, swap_manager, swapper); ``` 它可被视为PageTable的一个“装饰器”，由于实现了Deref trait，它“继承“了PageTable的全部方法，同时还增加了以下新方法： * swap\_in：换入一个指定页 * swap\_out：换出一个指定页 * swap\_out\_any：换出任意一个可交换页 * page\_fault\_handler：发生PageFault后，需要调用此函数，如返回true，说明发生了交换，不是一个异常。 ### 内存管理器 位于`memory_set.rs`，定义了一个主要结构`MemorySet`，以及提供底层支持接口`InactivePageTable`。 一个MemorySet负责维护**一个线程所使用的内存资源**，相当于原版ucore中的`mm_struct`。一个MemorySet中包含若干`MemoryArea`结构，它用来描述**一段连续的、属性相同的虚地址空间及其映射**，相当于原版ucore中的`vma_struct`。其中又定义了`MemoryAttr`类型用来描述映射的**属性和访问权限**。 此外，每个MemorySet还包含一个唯一的页表（拥有它的所有权），即`InactivePageTable`，它里面的内存映射保持和各个MemoryArea相同。 由于MemorySet**掌管其控制的内存资源**，因此它实现了析构函数（即Drop特性），会在自己销毁时将内部各段从页表中取消映射，释放物理帧。当一个线程控制块销毁时，它所对应的MemorySet也自动销毁，由此实现内存资源的自动释放。 MemorySet的用法简单示意如下： ```rust // 构造一个MemorySet // 在背后会自动分配一个内核栈、创建一个页表（映射了内核空间） let mut ms = MemorySet::::new(); // 添加不同内存段 // 每次push的同时会在内部页表中建立映射 // 可使用MemoryArea不同的构造函数： // * new_identity：虚实地址相同 // * new_physical：虚实地址有一个偏移 // * new：动态分配物理内存 ms.push(MemoryArea::new_identity(text_begin, text_end, MemoryAttr::default().execute().readonly(), "text")); ms.push(MemoryArea::new_identity(data_begin, data_end, MemoryAttr::default(), "data")); ms.push(MemoryArea::new(bss_begin, bss_end, MemoryAttr::default(), "bss")); // 使页表生效（设置CR3/satp） unsafe { ms.activate(); } ``` 在内核中的使用场景有两处： * 为RISCV映射内核：`arch/riscv32/memory.rs::remap_the_kernel()` * 映射用户程序：`process/context.rs::memory_set_from(elf)` 为了使用MemorySet，需要实现`InactivePageTable` 接口。这里有必要解释一下：既然已经有了`PageTable`接口，为什么还要定义一个新的？这两种页表到底有什么区别？ 我们在上面【页表的具体实现】一节中提到，目前的实现使用**自映射机制**完成对页表自身的修改，它带来的一个问题是：要编辑一个页表，必须要求【当前生效页表的自映射项】指向这个待编辑页表。因此：在修改每个页表的前后，都要修改【当前生效页表的自映射项】。换句话说，任何一个**未生效**的页表都是**不可访问**的，必须完成特定操作才能让它**可被访问**。（在RISCV中更甚：任何一个一级页表都是**不可访问**的，必须修改相应页表项中的属性位，才能让它**可被访问**） 因此，我们必须用一个新的接口表示**暂时不可编辑的页表**。它包含一个方法，可以将自己临时转换为可编辑的状态。现在我们可以来看`InactivePageTable`的具体定义了： ```rust /// 表示一个未生效的，暂时不可编辑的页表 pub trait InactivePageTable { /// 关联类型，指向可编辑的页表类 type Active: PageTable; /// 创建一个新的页表，同时映射内核空间 fn new() -> Self; /// 创建一个新的页表，除设置自映射外，完全空白。 /// 在设置第一个内核页表时使用。 fn new_bare() -> Self; /// 修改此页表，在函数f中完成具体操作 fn edit(&mut self, f: impl FnOnce(&mut Self::Active)); /// 使此页表生效 unsafe fn activate(&self); /// 临时使此页表生效，然后执行函数f。 /// 用于完成用户程序的映射后，复制数据进去。 unsafe fn with(&self, f: impl FnOnce()); /// 返回此页表生效时的CR3/satp。 /// 用于线程切换。 fn token(&self) -> usize; // 以下接口为MemorySet的依赖操作。 // 其实和页表无关（注意没有&self），为了简洁，放在这里。 fn alloc_frame() -> Option; fn dealloc_frame(target: PhysAddr); fn alloc_stack() -> Stack; } ``` x86\_64/RV32下的实现位于：`kernel/src/arch/../paging.rs` ## 其它部分 作为独立crate存在的内存管理模块，其实更适合被称为**虚存管理模块**。还有一些其他与内存管理相关的工作，已经有现成的crate完成了。 ### 物理帧分配 物理帧分配是虚存管理的底层支持之一，对应的接口是`FrameAllocator`。 在原版ucore中，物理内存管理需要从可用的物理空间中分配和回收**不定长**的内存段（= malloc in C, new in C++），这一工作在RustOS中转移到了下面的**堆空间管理**。 在RustOS中的物理内存管理，被简化成在可用的物理空间中分配和回收**固定大小**的物理帧，其本质上是**对N个整数的分配和回收**。我们使用了类似线段树的分层Bitset结构，高效地完成上述工作。其实现位于独立的crate `bit-allocator`。 当然考虑到页表支持大页映射（32位：4M，64位：2M/1G），未来可对数据结构做一些修改。不过这会增加整体的逻辑复杂度。 ### 堆空间管理 堆空间管理的任务是：在一片连续的内存空间中，分配和回收不定长的片段，给对象使用。 在Rust的core库中，定义了专门的[Alloc接口](https://doc.rust-lang.org/alloc/alloc/trait.GlobalAlloc.html)。当你实现了global\_allocator之后，就可以使用Box在堆上存储数据，进而可以使用alloc库中提供的丰富数据结构，如Vec、BTreeSet等。 原ucore中物理内存管理部分的诸多算法，如：First Fit、Last Fit、Best Fit，都可以在这个接口下实现（然而目前尚未实现）。 此外还有诸多crate实现了此接口，如： * [linked\_list\_allocator](https://docs.rs/crate/linked_list_allocator)：blog\_os作者自己造的轮子 * [slab\_allocator](https://docs.rs/crate/slab_allocator)：拓展了上面的算法，Redox使用 目前RustOS就直接使用了第一个轮子。用法非常简单： ```rust // 定义在lib.rs中 use linked_list_allocator::LockedHeap; #[global_allocator] static ALLOCATOR: LockedHeap = LockedHeap::empty(); // 使用前初始化 unsafe { ALLOCATOR.lock().init(heap_start, heap_size); } ``` 关于堆管理的实现细节，推荐阅读 [Kernel Heap | Writing an OS in Rust](https://os.phil-opp.com/kernel-heap/)。 ### 内核栈分配 目前的做法是：直接使用上面的堆空间分配。 ## 总结：使用指南 把内存管理相关逻辑独立成crate，一个重要目的就是方便复用。假设你在一个全新的平台上从头用Rust写了一个OS，该怎么用这个库呢？下面就来简单梳理一下： #### 1. 选择或实现一个物理帧分配器，定义一个全局实例 FRAME\_ALLOCATOR 全局实例应该需要上锁。 #### 2. 为该平台实现页表接口：PageTable，Entry 如果不使用自映射，可能需要额外开辟空间维护页表的物理地址信息。 如果需要动态分配页表本身所占用的物理空间，就需要使用到 FRAME\_ALLOCATOR。 #### 2.1 定义一个PageTable的全局实例 ACTIVE\_TABLE 后面所有的编辑页表操作，都通过它进行。 #### 3. 实现InactivePageTable接口 如果使用自映射，八成就需要访问ACTIVE\_TABLE了。 完成后就可以使用MemorySet管理内存了。 #### 4.1 如需写时复制：在ACTIVE\_TABLE外面套一层 CowExt结构 #### 4.2 如需交换机制：在ACTIVE\_TABLE外面套一层 SwapExt结构 对于Swapper和SwapManager，可以从库中选取，也可以自己实现。 #### 4.3 如使用上面拓展：在缺页异常处理中调用`ACTIVE_TABLE.page_fault_handler()` #### 5. 选择或实现一个global\_allocator，开启堆空间 ## TODO * [ ] 实现其他堆分配算法：First Fit、Last Fit、Best Fit…… * [ ] 实现其他页交换算法 * [ ] 为物理帧分配提供大页支持 * [ ] 实现延迟分配物理帧 * [ ] 在MemorySet层面提供共享内存和写时复制的接口 * [ ] 探讨尝试更优雅的接口与实现方式