内存管理模块

【部分内容已经过时】
概述
内存管理模块的职责是完成内存资源的管理。它主要建立在硬件提供的页机制之上，为使用者提供共享内存、页交换、写时复制等高级功能，并方便不同进程之间内存资源的管理。此模块功能相当于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     改进时钟算法
模块内为页表接口提供了模拟实现，因此就可以为建立在其上的各种算法编写单元测试，使用以下命令即可运行：
cd crate/memory
rustup override set nightly-2018-09-13
cargo test
页表接口
位于src/paging/mod.rs，定义了两个trait：PageTable,Entry
/// （可修改的）页表接口
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 ，并配合x86_64库中的实现，加深理解。
RISCV32中基本继承了x86_64的实现方式。不过值得注意的是：RISCV下的页表规范阻碍了自映射的实现。原因是RISCV页表项中的flags，明确表示它指向的是数据页（VRW），还是下层页表（V）。假如把一个二级页表项，当做一级页表项来解读，就会触发异常，而这是自映射机制中必须的操作。为了绕开这个问题，就要求在访问一级页表虚地址期间，将它所对应的二级页表项flags置为VRW。此外，为了访问二级页表本身，还需要再加一个自映射的二级页表项，其flags为VRW。
写时复制
TODO
详见cow.rs
交换机制
位于swap/mod.rs，首先定义了以下接口：
SwapManager：实现具体的页交换算法，本质是一个所有可交换页的优先队列
Swapper：交换的具体执行者，负责将数据换入/换出到其它存储设备
其它3个文件都是对上述接口的实现。
基于上述接口，定义了实现交换操作的扩展结构：
SwapExt <T: PageTable, M: SwapManager, S: Swapper>
使用时，构造一个SwapExt结构套在原有的PageTable结构外面，例如：
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的用法简单示意如下：
// 构造一个MemorySet
// 在背后会自动分配一个内核栈、创建一个页表（映射了内核空间）
let mut ms = MemorySet::<T>::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的具体定义了：
/// 表示一个未生效的，暂时不可编辑的页表
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<PhysAddr>;
    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接口。当你实现了global_allocator之后，就可以使用Box在堆上存储数据，进而可以使用alloc库中提供的丰富数据结构，如Vec、BTreeSet等。
原ucore中物理内存管理部分的诸多算法，如：First Fit、Last Fit、Best Fit，都可以在这个接口下实现（然而目前尚未实现）。
此外还有诸多crate实现了此接口，如：
​linked_list_allocator：blog_os作者自己造的轮子
​slab_allocator：拓展了上面的算法，Redox使用
目前RustOS就直接使用了第一个轮子。用法非常简单：
// 定义在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。 
内核栈分配
目前的做法是：直接使用上面的堆空间分配。
总结：使用指南
把内存管理相关逻辑独立成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层面提供共享内存和写时复制的接口
探讨尝试更优雅的接口与实现方式
Bootloader
线程管理模块
Last modified 4yr ago