rust_os_docs
Search…
内存管理模块
【部分内容已经过时】

概述

内存管理模块的职责是完成内存资源的管理。它主要建立在硬件提供的页机制之上,为使用者提供共享内存、页交换、写时复制等高级功能,并方便不同进程之间内存资源的管理。此模块功能相当于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实现了此接口,如:
目前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层面提供共享内存和写时复制的接口
  • 探讨尝试更优雅的接口与实现方式
Copy link
On this page
概述
实现
页表接口
页表的具体实现
写时复制
交换机制
内存管理器
其它部分
物理帧分配
堆空间管理
内核栈分配
总结:使用指南
TODO