内存管理模块
【部分内容已经过时】
内存管理模块的职责是完成内存资源的管理。它主要建立在硬件提供的页机制之上,为使用者提供共享内存、页交换、写时复制等高级功能,并方便不同进程之间内存资源的管理。此模块功能相当于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
动态分配页表本身占用的物理内存。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); }
目前的做法是:直接使用上面的堆空间分配。
把内存管理相关逻辑独立成crate,一个重要目的就是方便复用。假设你在一个全新的平台上从头用Rust写了一个OS, 该怎么用这个库呢?下面就来简单梳理一下:
全局实例应该需要上锁。
如果不使用自映射,可能需要额外开辟空间维护页表的物理地址信息。
如果需要动态分配页表本身所占用的物理空间,就需要使用到 FRAME_ALLOCATOR。
后面所有的编辑页表操作,都通过它进行。
如果使用自映射,八成就需要访问ACTIVE_TABLE了。
完成后就可以使用MemorySet管理内存了。
对于Swapper和SwapManager,可以从库中选取,也可以自己实现。
- 实现其他堆分配算法:First Fit、Last Fit、Best Fit……
- 实现其他页交换算法
- 为物理帧分配提供大页支持