Writing an OS in Rust

四月 08, 2025 [Rust] #Rust #obsidian

Writing an OS in Rust

Philipp Oppermann's blog

分页实现

Mar 14, 2019

翻译内容: 这是对原文章**Paging Implementation** 的社区中文翻译。它可能不完整,过时或者包含错误。可以在 这个 Issue 上评论和提问!

翻译者: @weijiew.With contributions from @liuyuran.

这篇文章展示了如何在我们的内核中实现分页支持。它首先探讨了使物理页表帧能够被内核访问的不同技术,并讨论了它们各自的优点和缺点。然后,它实现了一个地址转换功能和一个创建新映射的功能。

这个系列的 blog 在GitHub上开放开发,如果你有任何问题,请在这里开一个 issue 来讨论。当然你也可以在底部留言。你可以在

post-09

找到这篇文章的完整源码。

前文已经对分页的概念做了介绍。通过比较分页和分段来证明分页的优势,然后解释了分页和页表如何工作,最后介绍了x86_64的4级页表设计。此时 bootloader 已经为内核建立了一个页表层次结构,这意味着内核已经在虚拟地址上运行。这样做提高了安全性,因为非法的内存访问会导致页面故障异常,而不是修改任意的物理内存。

这篇文章最后说,我们不能从内核中访问页表,因为它们存储在物理内存中,而内核已经在虚拟地址上运行。

这篇文章探讨了使页表框能够被内核访问的不同方法。接下来将讨论每种方法的优点和缺点,最后决定内核采用哪种方法。

为了实现这个方法,我们需要 bootloader 的支持,所以首先要配置它。之后将实现一个遍历页表层次结构的函数,以便将虚拟地址转换为物理地址。最后,我们学习如何在页表中创建新的映射,以及如何为创建新的页表找到未使用的内存框。

从内核中访问页表并不像它看起来那么容易。为了理解这个问题,让我们再看一下上一篇文章中的4级页表层次结构的例子。

一个4级页层次结构的例子,每个页表都显示在物理内存中

这里重要的是,每个页面条目都存储了下一个表的 物理 地址。这就避免了对这些地址也要进行翻译,这对性能不利,而且容易造成无休止的翻译循环。

此时的问题是,内核无法直接访问物理地址,因为内核也是在虚拟地址之上运行的。例如,当访问地址4 KiB时,访问的是 虚拟 地址4 KiB,而不是存储4级页表的 物理 地址4 KiB。

因此,为了访问页表框架,我们需要将一些虚拟页面映射到它们。有不同的方法来创建这些映射,这些映射都允许我们访问任意的页表框架。

一个简单的解决方案是所有页表的身份映射。

一个虚拟和一个物理地址空间,各种虚拟页以相同的地址映射到物理帧上

在这个例子中,我们看到各种直接映射的页表框架。页表的物理地址也是有效的虚拟地址,这样我们就可以很容易地访问从CR3寄存器开始的各级页表。

然而,它使虚拟地址空间变得杂乱无章,并使寻找较大尺寸的连续内存区域更加困难。例如,想象一下,我们想在上述图形中创建一个大小为1000 KiB的虚拟内存区域,例如: memory-mapping a file。我们不能在28 KiB处开始区域,因为它将与1004 KiB处已经映射的页面相撞。所以我们必须进一步寻找,直到找到一个足够大的未映射区域,例如在1008 KiB。这是一个类似于segmentation的碎片化问题。

同样,这也使得创建新的页表更加困难,因为我们需要找到对应的页还没有被使用的物理框。例如,让我们假设我们为我们的内存映射文件保留了 虚拟 1000 KiB内存区域,从1008 KiB开始。现在我们不能再使用任何物理地址在1000 KiB和2008 KiB之间的帧,因为我们不能对它进行 identity map 。

为了避免虚拟地址空间的杂乱问题,我们可以使用一个单独的内存区域来进行页表映射。因此,我们不是以直接映射页表帧,而是以虚拟地址空间中的固定偏移量来映射它们。例如,偏移量可以是10 TiB。

与直接映射的数字相同,但每个映射的虚拟页偏移了10TiB。

通过使用范围为10 TiB...(10 TiB + 物理内存大小)的虚拟内存专门用于页表映射,避免了直接映射的碰撞问题。只有当虚拟地址空间比物理内存大小大得多时,保留如此大的虚拟地址空间区域才有可能。这在x86_64上不是一个问题,因为48位的地址空间有256 TiB大。

这种方法仍然有一个缺点,即每当我们创建一个新的页表时,我们都需要创建一个新的映射。另外,它不允许访问其他地址空间的页表,这在创建新进程时是很有用的。

我们可以通过映射完整的物理内存来解决这些问题,而不是只映射页表框架。

与偏移量映射的数字相同,但每个物理帧都有一个映射(在10 TiB + X),而不是只有页表帧。

这种方法允许我们的内核访问任意的物理内存,包括其他地址空间的页表框架。保留的虚拟内存范围的大小与以前一样,不同的是它不再包含未映射的页面。

这种方法的缺点是,需要额外的页表来存储物理内存的映射。这些页表需要存储在某个地方,所以它们会占用一部分物理内存,这在内存较小的设备上可能是个问题。

然而,在x86_64上,我们可以使用大小为2 MiB的巨大页面进行映射,而不是默认的4 KiB页面。这样,映射32 GiB的物理内存只需要132 KiB的页表,因为只需要一个3级表和32个2级表。巨大页面也是更有效的缓存,因为它们在转换查找缓冲器(TLB)中使用的条目更少。

对于物理内存数量非常少的设备,我们可以在需要访问页表帧时,只对其进行临时映射页表。为了能够创建临时映射,我们只需要一个 identity-mapped 的1级表。

一个虚拟和一个物理地址空间,有一个 identity-mapped  的1级表,该表将其第0个条目映射到2级表帧,从而将该帧映射到地址为0的页面上

该图中的第1级表控制着虚拟地址空间的前2 MiB。这是因为它可以通过从CR3寄存器开始,按照第4级、第3级和第2级页面表中的第0个条目到达。索引为8的条目将地址为32 KiB的虚拟页映射到地址为32 KiB的物理帧,从而对1级表本身进行身份映射。图形显示了这种 identity-mapping ,在 “32 KiB “处有一个水平箭头。

通过写到 identity-mapped 的1级表,我们的内核可以创建多达511个临时映射(512减去直接映射需要的条目)。在上面的例子中,内核创建了两个临时映射。

现在内核可以通过写到0KiB页来访问2级页表,通过写到36KiB页来访问4级页表。

访问具有临时映射的任意页表框架的过程是:

这种方法重复使用相同的512个虚拟页来创建映射,因此只需要4 KiB的物理内存。缺点是有点麻烦,尤其是一个新的映射可能需要对多个表层进行修改,这意味着我们需要多次重复上述过程。

另一种有趣的方法是根本不需要额外的页表,即映射页表的递归。这种方法背后思想是将一个条目从第4级页面表映射到第4级表本身。通过这样做,我们有效地保留了虚拟地址空间的一部分,并将所有当前和未来的页表框架映射到该空间。

让我们通过一个例子来了解这一切是如何进行的。

一个4级页层次结构的例子,每个页表都显示在物理内存中。第4级页的条目511被映射到帧4KiB,即第4级表本身的帧。

与本文开头的例子的唯一区别是在4级表中的索引511处增加了一个条目,它被映射到物理帧4 KiB,即4级表本身的帧。

通过让CPU跟随这个条目进行翻译,它不会到达3级表,而是再次到达同一个4级表。这类似于一个调用自身的递归函数,因此这个表被称为 递归页表 。重要的是,CPU假定4级表的每个条目都指向3级表,所以它现在把4级表当作3级表。这是因为所有级别的表在x86_64上都有完全相同的布局。

在我们开始实际翻译之前,通过跟随递归条目一次或多次,我们可以有效地缩短CPU所穿越的层数。例如,如果我们跟随递归条目一次,然后进入第3级表,CPU会认为第3级表是第2级表。再往前走,它把第2级表当作第1级表,把第1级表当作映射的框架。这意味着我们现在可以读写第1级页表了,因为CPU认为它是映射的帧。下面的图形说明了这五个转换步骤。

上述例子中的4级页面层次结构有5个箭头。从CR4到4级表的 “第0步”,从4级表到4级表的 “第1步”,从4级表到3级表的 “第2步”,从3级表到2级表的 “第3步”,以及从2级表到1级表的 “第4步”。

同样地,我们可以在开始翻译之前,先跟随递归条目两次,将遍历的层数减少到两个。

同样的4级页面层次结构,有以下4个箭头。从CR4到4级表的 “第0步”,从4级表到4级表的 “第1&2步”,从4级表到3级表的 “第3步”,以及从3级表到2级表的 “第4步”。

让我们一步一步地看下去。首先,CPU跟踪4级表的递归条目,认为它到达了3级表。然后,它再次跟踪递归条目,认为它到达了2级表。但实际上,它仍然是在第4级表中。当CPU现在跟随一个不同的条目时,它到达了一个3级表,但认为它已经在1级表上。因此,当下一个条目指向第2级表时,CPU认为它指向了映射的框架,这使得我们能够读写第2级表。

访问第3级和第4级表的方法是一样的。为了访问第3级表,我们沿着递归条目走了三次,诱使CPU认为它已经在第1级表上了。然后我们跟随另一个条目,到达第3级表,CPU将其视为一个映射的框架。对于访问第4级表本身,我们只需跟随递归条目四次,直到CPU将第4级表本身视为映射的框架(在下面的图形中为蓝色)。

同样的4级页面层次结构,有以下3个箭头。从CR4到4级表的 “步骤0”,从4级表到4级表的 “步骤1,2,3”,以及从4级表到3级表的 “步骤4”。蓝色的是替代的 “步骤1,2,3,4 “箭头,从4级表到4级表。

可能需要一些时间来理解这个概念,但在实践中效果相当好。

在下面的章节中,我们将解释如何构建虚拟地址,用于跟随递归条目一次或多次。在我们的实现中,我们不会使用递归分页,所以你不需要阅读它就可以继续阅读本帖。如果你感兴趣,只需点击 “地址计算” 来展开。



递归分页是一种有趣的技术,它显示了页表中的单个映射可以有多么强大。它比较容易实现,而且只需要少量的设置(只是一个单一的递归条目),所以它是第一次实验分页的一个好选择。

然而,它也有一些弊端:

所有这些方法的设置都需要对页表进行修改。例如,需要创建物理内存的映射,或者需要对4级表的一个条目进行递归映射。问题是,如果没有访问页表的现有方法,我们就无法创建这些所需的映射。

这意味着我们需要 bootloader 的帮助,bootloader 创建了内核运行的页表。Bootloader 可以访问页表,所以它可以创建内核需要的任何映射。在目前的实现中,“bootloader” 工具箱支持上述两种方法,通过 cargocargo features 进行控制。

我们为我们的内核选择了第一种方法,因为它很简单,与平台无关,而且更强大(它还允许访问非页表框架)。为了启用所需的引导程序支持,我们在 “引导程序” 的依赖中加入了 “map_physical_memory“功能。

[dependencies]
bootloader = { version = "0.9", features = ["map_physical_memory"]}

启用这个功能后,bootloader 将整个物理内存映射到一些未使用的虚拟地址范围。为了将虚拟地址范围传达给我们的内核,bootloader 传递了一个 启动信息 结构。

Bootloader 板块定义了一个

BootInfo

结构,包含了它传递给我们内核的所有信息。这个结构还处于早期阶段,所以在更新到未来的 semver-incompatible bootloader 版本时,可能会出现一些故障。在启用 “map_physical_memory” 功能后,它目前有两个字段 “memory_map” 和 “physical_memory_offset”。

Bootloader将 BootInfo 结构以 &'static BootInfo参数的形式传递给我们的内核,并传递给我们的_start函数。我们的函数中还没有声明这个参数,所以让我们添加它。

// in src/main.rs

use bootloader::BootInfo;

#[unsafe(no_mangle)]
pub extern "C" fn _start(boot_info: &'static BootInfo) -> ! { // new argument
    […]
}

以前省去这个参数并不是什么问题,因为x86_64的调用惯例在CPU寄存器中传递第一个参数。因此,当这个参数没有被声明时,它被简单地忽略了。然而,如果我们不小心使用了一个错误的参数类型,那将是一个问题,因为编译器不知道我们入口点函数的正确类型签名。

🔗entry_point 宏

由于我们的_start函数是在外部从引导程序中调用的,所以没有对我们的函数签名进行检查。这意味着我们可以让它接受任意参数而不出现任何编译错误,但在运行时它会失败或导致未定义行为。

为了确保入口点函数总是具有引导程序所期望的正确签名,bootloader板块提供了一个

entry_point

宏,它提供了一种类型检查的方法来定义一个Rust函数作为入口点。让我们重写我们的入口点函数来使用这个宏。

// in src/main.rs

use bootloader::{BootInfo, entry_point};

entry_point!(kernel_main);

fn kernel_main(boot_info: &'static BootInfo) -> ! {
    […]
}

我们不再需要使用extern "C"或no_mangle作为我们的入口点,因为宏为我们定义了真正的低级_start入口点。kernel_main函数现在是一个完全正常的Rust函数,所以我们可以为它选择一个任意的名字。重要的是,它是经过类型检查的,所以当我们使用一个错误的函数签名时,例如增加一个参数或改变参数类型,就会发生编译错误。

让我们在我们的lib.rs中进行同样的修改。

// in src/lib.rs

#[cfg(test)]
use bootloader::{entry_point, BootInfo};

#[cfg(test)]
entry_point!(test_kernel_main);

/// Entry point for `cargo test`
#[cfg(test)]
fn test_kernel_main(_boot_info: &'static BootInfo) -> ! {
    // like before
    init();
    test_main();
    hlt_loop();
}

由于这个入口点只在测试模式下使用,我们在所有项目中添加了#[cfg(test)]属性。我们给我们的测试入口点一个独特的名字test_kernel_main,以避免与我们的main.rs的kernel_main混淆。我们现在不使用BootInfo参数,所以我们在参数名前加上_,以消除未使用变量的警告。

现在我们可以访问物理内存了,我们终于可以开始实现我们的页表代码了。首先,我们将看一下我们的内核目前运行的活动页表。第二步,我们将创建一个转换函数,返回一个给定的虚拟地址所映射到的物理地址。作为最后一步,我们将尝试修改页表,以便创建一个新的映射。

在我们开始之前,我们为我们的代码创建一个新的memory模块。

// in src/lib.rs

pub mod memory;

对于该模块,我们创建一个空的src/memory.rs文件。

在上一篇文章的结尾,我们试图查看我们的内核运行的页表,但是由于我们无法访问CR3寄存器所指向的物理帧而失败了。我们现在可以通过创建一个active_level_4_table函数来继续,该函数返回对活动的4级页面表的引用。

// in src/memory.rs

use x86_64::{
    structures::paging::PageTable,
    VirtAddr,
};

/// 返回一个对活动的4级表的可变引用。
///
/// 这个函数是不安全的,因为调用者必须保证完整的物理内存在传递的
/// `physical_memory_offset`处被映射到虚拟内存。另外,这个函数
/// 必须只被调用一次,以避免别名"&mut "引用(这是未定义的行为)。
pub unsafe fn active_level_4_table(physical_memory_offset: VirtAddr)
    -> &'static mut PageTable
{
    use x86_64::registers::control::Cr3;

    let (level_4_table_frame, _) = Cr3::read();

    let phys = level_4_table_frame.start_address();
    let virt = physical_memory_offset + phys.as_u64();
    let page_table_ptr: *mut PageTable = virt.as_mut_ptr();

    unsafe { &mut *page_table_ptr }
}

首先,我们从CR3寄存器中读取活动的4级表的物理帧。然后我们取其物理起始地址,将其转换为u64,并将其添加到physical_memory_offset中,得到页表框架映射的虚拟地址。最后,我们通过as_mut_ptr方法将虚拟地址转换为*mut PageTable原始指针,然后不安全地从它创建一个&mut PageTable引用。我们创建一个&mut引用,而不是&引用,因为我们将在本篇文章的后面对页表进行突变。

现在我们可以用这个函数来打印第4级表格的条目。

// in src/main.rs

fn kernel_main(boot_info: &'static BootInfo) -> ! {
    use blog_os::memory::active_level_4_table;
    use x86_64::VirtAddr;

    println!("Hello World{}", "!");
    blog_os::init();

    let phys_mem_offset = VirtAddr::new(boot_info.physical_memory_offset);
    let l4_table = unsafe { active_level_4_table(phys_mem_offset) };

    for (i, entry) in l4_table.iter().enumerate() {
        if !entry.is_unused() {
            println!("L4 Entry {}: {:?}", i, entry);
        }
    }

    // as before
    #[cfg(test)]
    test_main();

    println!("It did not crash!");
    blog_os::hlt_loop();
}

首先,我们将 “BootInfo” 结构的 “physical_memory_offset “转换为

VirtAddr

,并将其传递给 active_level_4_table 函数。然后我们使用iter函数来迭代页表条目,并使用enumerate

组合器为每个元素增加一个索引i。我们只打印非空的条目,因为所有512个条目在屏幕上是放不下的。当我们运行它时,我们看到以下输出。

QEMU打印条目0 (0x2000, PRESENT, WRITABLE, ACCESSED),条目1 (0x894000, PRESENT, WRITABLE, ACCESSED, DIRTY),条目31 (0x88e000, PRESENT, WRITABLE, ACCESSED, DIRTY),条目175 (0x891000, PRESENT, WRITABLE, ACCESSED, DIRTY),以及条目504 (0x897000, PRESENT, WRITABLE, ACCESSED, DIRTY)

我们看到有各种非空条目,它们都映射到不同的3级表。有这么多区域是因为内核代码、内核堆栈、物理内存映射和启动信息都使用独立的内存区域。

为了进一步遍历页表,看一下三级表,我们可以把一个条目的映射帧再转换为一个虚拟地址。

// in the `for` loop in src/main.rs

use x86_64::structures::paging::PageTable;

if !entry.is_unused() {
    println!("L4 Entry {}: {:?}", i, entry);

    // get the physical address from the entry and convert it
    let phys = entry.frame().unwrap().start_address();
    let virt = phys.as_u64() + boot_info.physical_memory_offset;
    let ptr = VirtAddr::new(virt).as_mut_ptr();
    let l3_table: &PageTable = unsafe { &*ptr };

    // print non-empty entries of the level 3 table
    for (i, entry) in l3_table.iter().enumerate() {
        if !entry.is_unused() {
            println!("  L3 Entry {}: {:?}", i, entry);
        }
    }
}

对于查看2级和1级表,我们对3级和2级条目重复这一过程。你可以想象,这很快就会变得非常冗长,所以我们不在这里展示完整的代码。

手动遍历页表是很有趣的,因为它有助于了解CPU是如何进行转换的。然而,大多数时候,我们只对给定的虚拟地址的映射物理地址感兴趣,所以让我们为它创建一个函数。

为了将虚拟地址转换为物理地址,我们必须遍历四级页表,直到到达映射的帧。让我们创建一个函数来执行这种转换。

// in src/memory.rs

use x86_64::PhysAddr;

/// 将给定的虚拟地址转换为映射的物理地址,如果地址没有被映射,则为`None'。
///
/// 这个函数是不安全的,因为调用者必须保证完整的物理内存在传递的`physical_memory_offset`处被映射到虚拟内存。
pub unsafe fn translate_addr(addr: VirtAddr, physical_memory_offset: VirtAddr)
    -> Option<PhysAddr>
{
    translate_addr_inner(addr, physical_memory_offset)
}

我们将该函数转发到一个安全的translate_addr_inner函数,以限制unsafe的范围。正如我们在上面指出的,Rust把一个unsafe fn的完整主体当作一个大的不安全块。通过调用一个私有的安全函数,我们使每个unsafe操作再次明确。

私有内部函数包含真正的实现:

// in src/memory.rs

/// 由 `translate_addr`调用的私有函数。
///
/// 这个函数是安全的,可以限制`unsafe`的范围,
/// 因为Rust将不安全函数的整个主体视为不安全块。
/// 这个函数只能通过`unsafe fn`从这个模块的外部到达。
fn translate_addr_inner(addr: VirtAddr, physical_memory_offset: VirtAddr)
    -> Option<PhysAddr>
{
    use x86_64::structures::paging::page_table::FrameError;
    use x86_64::registers::control::Cr3;

    // 从CR3寄存器中读取活动的4级 frame
    let (level_4_table_frame, _) = Cr3::read();

    let table_indexes = [
        addr.p4_index(), addr.p3_index(), addr.p2_index(), addr.p1_index()
    ];
    let mut frame = level_4_table_frame;

    // 遍历多级页表
    for &index in &table_indexes {
        // 将该框架转换为页表参考
        let virt = physical_memory_offset + frame.start_address().as_u64();
        let table_ptr: *const PageTable = virt.as_ptr();
        let table = unsafe {&*table_ptr};

        // 读取页表条目并更新`frame`。
        let entry = &table[index];
        frame = match entry.frame() {
            Ok(frame) => frame,
            Err(FrameError::FrameNotPresent) => return None,
            Err(FrameError::HugeFrame) => panic!("huge pages not supported"),
        };
    }

    // 通过添加页面偏移量来计算物理地址
    Some(frame.start_address() + u64::from(addr.page_offset()))
}

我们没有重复使用active_level_4_table函数,而是再次从CR3寄存器读取4级帧。我们这样做是因为它简化了这个原型的实现。别担心,我们一会儿就会创建一个更好的解决方案。

VirtAddr结构已经提供了计算四级页面表索引的方法。我们将这些索引存储在一个小数组中,因为它允许我们使用for循环遍历页表。在循环之外,我们记住了最后访问的frame,以便以后计算物理地址。frame在迭代时指向页表框架,在最后一次迭代后指向映射的框架,也就是在跟随第1级条目之后。

在这个循环中,我们再次使用physical_memory_offset将帧转换为页表引用。然后我们读取当前页表的条目,并使用

PageTableEntry::frame

函数来检索映射的框架。如果该条目没有映射到一个框架,我们返回None。如果该条目映射了一个巨大的2 MiB或1 GiB页面,我们就暂时慌了。让我们通过翻译一些地址来测试我们的翻译功能。

// in src/main.rs

fn kernel_main(boot_info: &'static BootInfo) -> ! {
    // new import
    use blog_os::memory::translate_addr;

    […] // hello world and blog_os::init

    let phys_mem_offset = VirtAddr::new(boot_info.physical_memory_offset);

    let addresses = [
        // the identity-mapped vga buffer page
        0xb8000,
        // some code page
        0x201008,
        // some stack page
        0x0100_0020_1a10,
        // virtual address mapped to physical address 0
        boot_info.physical_memory_offset,
    ];

    for &address in &addresses {
        let virt = VirtAddr::new(address);
        let phys = unsafe { translate_addr(virt, phys_mem_offset) };
        println!("{:?} -> {:?}", virt, phys);
    }

    […] // test_main(), "it did not crash" printing, and hlt_loop()
}

当我们运行它时,我们看到以下输出。

0xb8000 -> 0xb8000, 0x201008 -> 0x401008, 0x10000201a10 -> 0x279a10, “panicked at ‘huge pages not supported’

正如预期的那样,身份映射的地址0xb8000翻译成了相同的物理地址。代码页和堆栈页翻译成了一些任意的物理地址,这取决于引导程序如何为我们的内核创建初始映射。值得注意的是,最后12位在翻译后总是保持不变,这是有道理的,因为这些位是*page offset*,不是翻译的一部分。

由于每个物理地址都可以通过添加physical_memory_offset来访问,physical_memory_offset地址的翻译本身应该指向物理地址0。然而,翻译失败了,因为映射使用了巨大的页面来提高效率,而我们的实现还不支持。

将虚拟地址转换为物理地址是操作系统内核中的一项常见任务,因此x86_64内核为它提供了一个抽象。这个实现已经支持巨大的页面和除了 “translate_addr “之外的其他几个页表函数,所以我们将在下面使用它,而不是在我们自己的实现中添加巨大的页面支持。

抽象的基础是两个特征,它们定义了各种页表映射功能。