使用Rust编写操作系统 - 3.3 - 内存堆分配

本文所有内容均为翻译，原文：Heap Allocation；原项目：Writing an OS in Rust

本文将为内核添加对堆分配的支持。首先将介绍动态内存机制，并展示Rust借用检查器如何防止常见的分配错误。然后将实现Rust的基础分配器接口，创建一个堆内存区域，并编写一个分配器crate。在本文结束时，内核将能够支持Rust内置alloccrate中的所有分配和收集类型。

这个博客是在GitHub上公开开发的。如果你有任何问题或疑问，请在那里开一个issue。你也可以在底部留言。这篇文章的完整源代码可以在post-10分支中找到。

局部变量和静态变量

当前，我们在内核中使用两种类型的变量：局部变量和static变量。局部变量存储在调用栈中，并且仅在其所在的函数返回之前有效。静态变量存储在固定的内存位置，并且在程序的整个生命周期中始终有效。

局部变量

局部变量存储在调用栈中，这是一个支持push和pop操作的栈数据结构。对于每个被调用的函数，编译器都将其参数、返回地址和局部变量压栈：

上图中的例子展示了outer函数调用了inner函数之后的调用栈。可以看到调用栈先是包含了outer函数的局部变量。在inner函数被调用时，参数1和返回地址被压栈。接下来控制权转给了inner函数，并继续将其局部变量压栈。

inner函数返回后，其位于调用栈中的相关部分弹栈，此时调用栈中仅剩下outer函数相关的局部变量：

我们看到inner的局部变量仅在函数返回之前有效。当我们持有变量时间过长时——比如尝试返回对局部变量的引用时——Rust编译器就会强行生命周期并引发编译错误：

fn inner(i: usize) -> &'static u32 {
    let z = [1, 2, 3];
    &z[i]
}

（使用play rust在线运行上面的代码）

虽然本例中返回引用并无意义，但在某些情况下，我们希望变量比其所在函数的生命周期更长。我们已经在编写内核的过程中遇到了这种情况，比如在尝试加载中断描述符表时就不得不使用static变量来延长其生命周期。

静态变量

静态变量存储在栈以外的固定内存位置中。此存储位置由链接器在编译时分配并编码在可执行文件中。静态变量在程序的完整运行时内始终有效，因此它们具有'static生命周期，并且始终可以被局部变量引用：

上图中的inner函数返回时，其在调用栈中的相关部分被析构。而静态变量位于一个独立的内存范围中，并不会被析构，因此&Z[1]的引用在函数返回后仍然有效。

除了'static生命周期以外，静态变量还有另一个有用的属性，即其内存位置在编译时就已确定，因此不需要引用就能够对其进行访问。我们利用该属性实现了println：通过在内部使用静态Writer，即便不使用&mut Writer引用也能够调用该宏。这在异常处理程序中非常有用，因为在其中我们无法访问任何其他变量。

但是，静态变量的这个属性也带来了一个致命缺点：它们默认是只读的。Rust强制此规则是为了避免数据竞争，比如当两个线程同时修改一个静态变量时。修改静态变量的唯一方法是将其封装在Mutex类型中，从而确保在任何时刻中仅存在一个&mut引用。我们已经将Mutex用于静态VGA缓冲区Writer。

动态内存

结合使用局部变量和静态变量已经能够实现非常强大的功能，足以应付大多数用例了。但是，它们仍然具有一定的局限性：

• 局部变量仅其所在的函数或块结束前有效。这是因为它们存在于调用栈中，并在上下文函数返回后被析构。
• 静态变量在程序的完整运行时内始终有效，因此无法在不再需要它们时回收和重用它们的内存。此外，它们的所有权语义不明确，且能够被任意函数访问，所以我们才会在需要修改时使用Mutex对其进行保护。

局部变量和静态变量的另一个局限性，就是它们的大小固定，因此，遇到需要添加更多元素的情况时，它们将无法存储这些动态增长的集合。（Rust中有一些关于unsized rvalues的提案，以允许局部变量具有动态大小，但它们仅在某些特定情况下有效。）

为了避开这些缺点，编程语言通常会提供第三块用于存放变量的内存区域，称为堆。堆使用两个叫做allocate和deallocate的函数在运行时动态内存分配。其工作方式为：allocate函数返回指定大小的可用内存块，用于存储变量。然后，该变量会一直有效，直到在其引用上调用deallocate函数将其释放为止。

让我们来看一个例子：

在这里，inner函数使用堆内存而不是静态变量来存储z。首先按照所需大小分配内存块，然后返回*mut u32裸指针。然后使用ptr::write方法写入数组[1,2,3]。最后使用offset函数计算指向第i个元素的指针，并将其返回。（请注意，为简洁起见，在此示例函数中，我们省略了一些必需的强制转换和unsafe块。）

分配的内存将会一直有效，直到通过调用dealloc显式释放为止。因此，即使在inner返回且其相关部分的调用栈被析构之后，返回的指针依然有效。与静态内存相比，使用堆内存的优势在于内存可以在释放后重用，这是通过outer的deallocate调用实现的。调用结束后的情形如下：

可以看到z[1]所在堆中的位置又空闲了，可以重新用于下一次allocate调用。但是，还可以看到z[0]和z[2]从未释放，因为我们从未释放过它们。这种错误称为内存泄漏，也通常是导致程序过度消耗内存的原因（试想一下，当我们在循环中重复调用inner时会发生什么）。这看起来很不好，然而动态分配可能会导致更多种危险的错误。

常见错误

内存泄漏虽然会导致过度消耗内存，但并不会使程序更容易受到攻击。除此之外，还有两种常见的错误类型，其后果更为严重：

• 当我们在调用deallocate后意外地继续使用变量时，便产生了一个称作释放后使用的漏洞。这种漏洞会导致未定义的行为，此外，攻击者也经常通过该漏洞来执行任意代码。
• 当我们不小心两次释放变量时，便产生了一个双重释放漏洞。这是有问题的，因为它这可能会释放第一次调用deallocate后在该位置重新分配的变量。因此，它可能再次导致释放后使用漏洞。

这些种类的漏洞是很常见的，看起来可以期望人们现在已经学会了如何规避它们。现实很遗憾，这些漏洞仍然经常出现，例如，近日Linux中出现的释放后使用漏洞允许执行任意代码。这也表明即使是最优秀的程序员也不一定总是能够正确处理复杂项目中的动态内存。

为了规避这些漏洞，许多语言——例如Java或Python——都使用称为垃圾回收的技术自动管理动态内存。其意图是使程序员不再需要手动调用deallocate，转而使程序定期暂停并扫描未使用的堆变量，然后将它们自动释放。于是，上述漏洞也就不会再出现了。不过，其缺点是常规扫描有一定的性能开销，以及暂停的时间可能会较长。

针对此问题Rust采用了不同的解决方案：它使用一种称为所有权的概念，能够在编译时检查动态内存操作的正确性。因此，Rust不需要垃圾收集也能避免上述漏洞，这意味着没有性能开销。该方案的另一个优点是，程序员仍然可以像使用C或C++一样对动态内存进行细粒度的控制。

Rust中的堆分配

Rust标准库提供了隐式调用allocate和deallocate抽象类型，省去程序员显示调用这些函数的麻烦。其中最重要的类型是Box，它是堆分配值的抽象。该类提供了构造函数Box::new，构造函数接受一个值并使用该值的大小调用allocate，再将该值移动到堆上新分配的空间中。为了能够释放堆内存，Box类型实现了Droptrait，以在变量离开作用域时调用deallocate：

{
    let z = Box::new([1,2,3]);
    […]
} // z离开作用域后，`deallocate`将被调用

此模式具有一个奇怪的名字——资源获取即初始化（或简称RAII）。它起源于C++，用于实现类似的抽象类型std::unique_ptr。

单靠这种类型不足以防止所有的释放后使用漏洞，因为在Box离开作用域并释放相应的堆内存空间之后，程序员仍然可以保留对其的引用：

let x = {
    let z = Box::new([1,2,3]);
    &z[1]
}; // z离开作用域后，`deallocate`将被调用
println!("{}", x);

而这便是Rust所有权机制大放异彩之处。所有权会为每个引用分配一个抽象的生命周期，就是该引用的有效的范围。在上例中，x引用来自于z数组，因此在z离开作用域后将变得无效。在线运行上例时，您将看到Rust编译器的确出现了编译错误：

error[E0597]: `z[_]` does not live long enough
 --> src/main.rs:4:9
  |
2 |     let x = {
  |         - borrow later stored here
3 |         let z = Box::new([1,2,3]);
4 |         &z[1]
  |         ^^^^^ borrowed value does not live long enough
5 |     }; // z goes out of scope and `deallocate` is called
  |     - `z[_]` dropped here while still borrowed

此时看这些术语可能会有些混乱。在Rust中，引用一个值称为借用值，因为它类似于现实生活中的借东西：你可以临时访问某个对象，但需要在某个时刻将其归还，而且一定不可以析构它。通过确保所有借用在其原对象被析构之前生命周期便已结束，Rust编译器可以保证不会发生释放后使用的情况。

Rust的所有权机制非常强大，不仅可以防止释放后使用的漏洞，而且能够像Java或Python这样的垃圾收集语言一样提供完整的内存安全。另外，它还能保证线程安全，因此其多线程代码比这些垃圾收集语言的更安全。最重要的是，所有这些检查都在编译时进行，因此与C语言中的手写内存管理相比一样没有运行时开销。

用例

现在我们知道了Rust中动态内存分配的基础知识，但是要在什么时候应该使用动态内存呢？我们的内核在没有动态内存分配情况下也已经走得很远了，那么为什么现在又需要动态内存呢？

不过，动态内存分配总是会带来一些性能开销，因为我们需要为每一个分配在堆上找到一个尚未使用的位置。因此，通常情况下尽可能使用局部变量，尤其是在对性能要求极高的内核代码中。但是，在某些情况下，动态内存分配才是最佳选择。

作为基本规则，具有动态生命周期或可变大小的变量需要动态内存。动态生命周期最重要的类型是Rc，它对其内部封装值的引用进行计数，并在所有引用均超出作用域后将内部封装值释放。具有可变大小的类型的示例包括Vec、String和其他集合类型，这些集合类型在添加更多元素时将会动态增长。这些类型的工作原理是，当集合装满时重新分配更大的内存，再将所有元素复制过来，最后取消旧的内存分配。

在内核中，我们非常需要集合类型，比如后文中在实现多任务处理时，用于存储活动任务的列表。

分配器接口

实现堆分配器的第一步是添加对内置alloc crate的依赖。像core crate一样，它也是标准库的子集，同时它还包含分配器和集合类型。要添加对alloc的依赖需要将以下内容添加到lib.rs中：

in src/lib.rs

extern crate alloc;

与添加普通依赖不同，我们并不需要修改Cargo.toml。原因是alloccrate与Rust编译器一起作为标准库的一部分供我们使用，因此编译器已经知道了该crate。通过添加此extern crate语句，我们指定编译器去尝试包含该crate。（在以前的Rust中，所有依赖项都需要一个extern crate语句，不过现在该语句是可选的）。

由于我们正在为自定义目标系统进行编译，因此无法使用随Rust一起安装的alloc预编译版本。此处，我们必须告诉cargo用源码重新编译该crate。这可以通过将该crate添加到.cargo/config.toml文件中的unstable.build-std数组中来实现：

in .cargo/config.toml

[unstable]
build-std = ["core", "compiler_builtins", "alloc"]

现在，编译器将重新编译alloc并其包括在内核中。

默认在#[no_std]的诸多crate中禁用alloccrate的原因是它还有其他要求。现在尝试编译项目时，我们可以看到这些要求引发的编译错误：

error: no global memory allocator found but one is required; link to std or add
       #[global_allocator] to a static item that implements the GlobalAlloc trait.

error: `#[alloc_error_handler]` function required, but not found

发生第一个错误是因为alloccrate需要堆分配器，以提供具有allocate和deallocate函数的对象。在Rust中，堆分配器GlobalAlloc trait，如错误消息所示。要为crate提供堆分配器，必须为实现GlobalAlloctrait的static变量添加#[global_allocator]属性。

发生第二个错误是因为调用allocate可能会失败，最常见的情况是在没有更多内存可用时。我们的程序必须能够对这种情况做出反应，这就是#[alloc_error_handler]函数的作用。

在下文的各小节中，我们将详细描述这些特征和属性。

GlobalAlloctrait

GlobalAlloctrait定义了堆分配器必须提供的函数。该特性非常特殊，通常程序员不会使用到。而当程序员使用alloc中的分配器和集合类型时，编译器将自动将调用适当的trait函数。

由于我们将需要为所有分配器类型实现该trait，因此有必要仔细研究其声明：

pub unsafe trait GlobalAlloc {
    unsafe fn alloc(&self, layout: Layout) -> *mut u8;
    unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout);

    unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 { ... }
    unsafe fn realloc(
        &self,
        ptr: *mut u8,
        layout: Layout,
        new_size: usize
    ) -> *mut u8 { ... }
}

该trait定义了两个必须实现的方法alloc与dealloc，并与我们在示例中使用的allocate和deallocate函数相对应：

• alloc方法将Layout实例作为参数，该实例描述了所分配的内存应具有的大小和对齐方式。该方法返回一个裸指针，并指向所分配内存块的第一个字节。当发生分配错误时，alloc方法返回一个空指针，而不是显式的错误值。虽然这有点不符合Rust的使用习惯，不过由于现有系统也使用相同的约定，所以其优点是可以很容易的封装现有的系统的分配器。
• dealloc方法是分配的另一半，它负责释放内存块。该方法接收两个参数，即alloc返回的指针和分配时用的Layout。

该trait还使额外定义了两个带有默认实现的方法alloc_zeroed和realloc：

• alloc_zeroed方法等效于先调用alloc再将分配的内存块全部置为零，正如其默认实现中所做的那样。如果自定义实现比默认实现更高效的话，也可以使用它来覆盖默认实现。
• realloc方法允许增加或减少分配空间。默认实现会分配一个所需大小的新内存块，并会将先前分配中的所有内容复制进来。与上一个方法相同，自定义的分配器实现也可能会提供此一个更高效的实现，比如实现就地扩展/缩小原分配。

非安全特性

需要注意的是，trait本身的所有方法都被声明为unsafe：

• 将该trait声明为unsafe的原因是，程序员必须保证分配器类型的trait实现是正确的。例如，alloc方法绝不能返回已在其他地方使用的内存块，因为这将导致未定义的行为。
• 同样，其方法均为unsafe的原因是，调用者在调用方法时必须确保各种不变性，例如，传递给alloc的Layout实例指定的大小应是非零的。不过在实践中这并不重要，因为方法通常是由编译器直接调用的，可以确保满足要求。

编写一个DummyAllocator

既然已经知道了要为分配器类型提供什么，我们就可以实现一个简单的假分配器。首先创建一个新的分配器模块：

in src/lib.rs

pub mod allocator;

我们的假分配器将实现特征的最低要求，即在调用alloc时始终返回错误。看起来像这样：

in src/allocator.rs

use alloc::alloc::{GlobalAlloc, Layout};
use core::ptr::null_mut;

pub struct Dummy;

unsafe impl GlobalAlloc for Dummy {
    unsafe fn alloc(&self, _layout: Layout) -> *mut u8 {
        null_mut()
    }

    unsafe fn dealloc(&self, _ptr: *mut u8, _layout: Layout) {
        panic!("dealloc should be never called")
    }
}

该结构体不需要任何字段，于是我们将其创建为零大小类型。就像描述的那样，我们总是用alloc返回空指针，这正对应了分配错误。由于分配器从不返回任何内存，所以永远不应该调用dealloc。因此，我们仅在dealloc中panic即可。alloc_zeroed和realloc方法具有默认实现，因此无需为其提供实现。

这就实现了一个简单的分配器，但是我们仍然需要告诉Rust编译器它应该使用这个分配器。这就需要用到#[global_allocator]属性了。

#[global_allocator]属性

#[global_allocator]将属性告诉Rust编译器应该使用哪个分配器实例作为全局堆分配器。该属性仅适用于实现了GlobalAlloc特性的static对象。让我们将分配器Dummy的一个实例注册为全局分配器：

src/allocator.rs

#[global_allocator]
static ALLOCATOR: Dummy = Dummy;

由于Dummy分配器是零大小类型，因此我们不需要在初始化表达式中指定任何字段。

现在尝试编译，第一个错误消失了。让我们继续修复第二个错误：

error: `#[alloc_error_handler]` function required, but not found

#[alloc_error_handler]属性

正如我们在讨论GlobalAlloctrait时所了解的那样，alloc函数可以通过返回空指针来表示分配错误。那么Rust在运行时应如何应对这种分配失败呢？这就是#[alloc_error_handler]属性起作用的地方了。该属性将指定发生分配错误时调用的处理函数，类似于在发生panic时调用panic处理程序。

我们来添加一个这样的函数以修复该编译错误：

in src/lib.rs

#![feature(alloc_error_handler)] // 需要写在源文件开头

#[alloc_error_handler]
fn alloc_error_handler(layout: alloc::alloc::Layout) -> ! {
    panic!("allocation error: {:?}", layout)
}

alloc_error_handler函数仍然不稳定，因此我们需要一个特性门来启用它。该函数接收一个参数，即发生分配错误时传递给alloc的Layout实例。我们无法纠正该错误，因此仅在处理函数中进行panic并打印关于Layout实例的信息。

应用该函数就可以修复编译错误。现在我们可以使用alloc的分配器和集合类型了，例如，我们可以使用Box在堆上分配一个值：

in src/main.rs

extern crate alloc;

use alloc::boxed::Box;

fn kernel_main(boot_info: &'static BootInfo) -> ! {
    // […] print "Hello World!", call `init`, create `mapper` and `frame_allocator`

    let x = Box::new(41);

    // […] call `test_main` in test mode

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

注意，我们也需要在main.rs中指定extern crate alloc语句。这是必需的，因为lib.rs和main.rs部分被视为各自独立的crate。但是，我们不需要创建另一个#[global_allocator]静态变量，因为全局分配器适用于项目中的所有crate。实际上，在另一个crate中指定其他分配器将引发错误。

运行上面的代码，我们将看到alloc_error_handler函数被调用：

错误处理程序被调用是因为Box::new函数隐式调用了全局分配器的alloc函数。因为假分配器始终返回空指针，所以每次分配都将会失败。为了解决这个问题，我们需要创建一个真分配器，用以返回可以使用的内存。

创建内核堆

在创建适当的分配器之前，我们首先需要创建一个堆内存区域，使得分配器可以从该区域分配内存。为此，我们需要为堆区域定义一个虚拟内存范围，然后将该区域映射到物理帧上。有关虚拟内存和页表的介绍，请参见“内存分页简介”一文。

第一步是为堆定义虚拟内存区域。我们可以选择我们喜欢的任何虚拟地址范围，只要它尚未用于其他内存区域即可。让我们将其定义为从地址0x_4444_4444_0000开始的内存，以便未来可以轻松识别堆指针：

in src/allocator.rs

pub const HEAP_START: usize = 0x_4444_4444_0000;
pub const HEAP_SIZE: usize = 100 * 1024; // 100 KiB

目前将堆大小设置为100 KiB。如果将来我们需要更多空间，将该值改大即可。

如果我们现在尝试使用此堆区域，就会发生页面错误，因为虚拟内存区域尚未映射到物理内存。为了解决这个问题，我们创建init_heap函数并使用在“内存分页实现”一文中介绍的Mapper API映射堆页面：

in src/allocator.rs

use x86_64::{
    structures::paging::{
        mapper::MapToError, FrameAllocator, Mapper, Page, PageTableFlags, Size4KiB,
    },
    VirtAddr,
};

pub fn init_heap(
    mapper: &mut impl Mapper<Size4KiB>,
    frame_allocator: &mut impl FrameAllocator<Size4KiB>,
) -> Result<(), MapToError<Size4KiB>> {
    let page_range = {
        let heap_start = VirtAddr::new(HEAP_START as u64);
        let heap_end = heap_start + HEAP_SIZE - 1u64;
        let heap_start_page = Page::containing_address(heap_start);
        let heap_end_page = Page::containing_address(heap_end);
        Page::range_inclusive(heap_start_page, heap_end_page)
    };

    for page in page_range {
        let frame = frame_allocator
            .allocate_frame()
            .ok_or(MapToError::FrameAllocationFailed)?;
        let flags = PageTableFlags::PRESENT | PageTableFlags::WRITABLE;
        unsafe {
            mapper.map_to(page, frame, flags, frame_allocator)?.flush()
        };
    }

    Ok(())
}

该函数接受Mapper和FrameAllocator实例的可变引用作为参数，这两个实例均使用Size4KiB作为泛型参数指定页面大小为4KiB。该函数的返回值为Result，以单位类型()作为成功结果，以MapToError作为失败结果，该失败结果是由Mapper::map_to方法返回的错误类型。之所以在此处复用了该错误类型是因为map_to方法是此函数中错误的主要来源。

实现可以分为两部分：

• 创建页面范围：首先需要将HEAP_START指针转换为VirtAddr类型。然后用起始地址加上HEAP_SIZE计算出堆结束地址。我们想要一个闭区间（堆的最后一个字节的地址），故而减1。接下来使用containing_address函数将这些地址转换为Page类型。最后使用Page::range_inclusive函数创建从起始页面到结束页面的页面范围。
• 映射页面：第二步是映射刚刚创建的页面范围内的所有页面。为此，我们使用for循环遍历该范围内的页面。我们为每个页面执行以下操作：
  • 使用FrameAllocator::allocate_frame方法将页面应映射到分配的物理帧上。当没有额外的帧时，该方法将返回None。遇到没有额外帧的情况时，我们使用Option::ok_or方法将错误映射到MapToError::FrameAllocationFailed，然后接问号运算符以在出错时提前返回。
  • 为页面设置了必要的PRESENT和WRITABLE标志，以允许读取和写入访问，这对于堆内存是有实际意义的。
  • 使用Mapper::map_to方法在活动页面表中创建映射。该方法可能会失败，因此我们再次使用问号运算符将错误传播给调用方。若成功，该方法将返回一个MapperFlush实例，然后使用该实例使用flush方法来更新转换后备缓冲区。

最后一步是从kernel_main中调用此函数：

in src/main.rs

fn kernel_main(boot_info: &'static BootInfo) -> ! {
    use blog_os::allocator; // new import
    use blog_os::memory::{self, BootInfoFrameAllocator};

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

    let phys_mem_offset = VirtAddr::new(boot_info.physical_memory_offset);
    let mut mapper = unsafe { memory::init(phys_mem_offset) };
    let mut frame_allocator = unsafe {
        BootInfoFrameAllocator::init(&boot_info.memory_map)
    };

    // new
    allocator::init_heap(&mut mapper, &mut frame_allocator)
        .expect("heap initialization failed");

    let x = Box::new(41);

    // […] call `test_main` in test mode

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

上面的代码显示了函数完整的上下文。这里仅有的新增行是blog_os::allocator的导入和allocator::init_heap函数的调用。如果init_heap函数返回错误，我们将使用Result::expect方法产生panic，因为目前还没有适当的处理此错误的方法。

现在，我们有一个准备使用的映射堆内存区域。但是Box::new调用仍然使用旧的Dummy分配器，因此如果此时运行仍会看到“内存不足”错误。让我们通过使用适当的分配器来解决此问题。

使用分配器crate

鉴于实现分配器较为复杂，我们先临时使用已有的分配器crate。在下一篇文章中，我们将学习如何实现自己的分配器。

对于no_std的应用程序，linked_list_allocator crate是一个简单的分配器实现。之所以叫这个名字，是因为该crate使用链表数据结构来跟踪释放的内存区域。有关该实现的详情参见下一篇文章。

要使用该crate，首先需要在Cargo.toml中添加其依赖：

in Cargo.toml

[dependencies]
linked_list_allocator = "0.8.0"

然后便可以使用该crate提供的分配器代替我们的假分配器了：

in src/allocator.rs

use linked_list_allocator::LockedHeap;

#[global_allocator]
static ALLOCATOR: LockedHeap = LockedHeap::empty();

该结构体叫做LockedHeap，是因为它使用spining_top::Spinlock类型进行同步。这是必需的，因为多个线程可以同时访问ALLOCATOR静态对象。一如往常，在使用自旋锁或互斥锁时，我们需要注意不要意外引发死锁。这意味着我们不应该在中断处理程序中执行任何分配，因为它们可以在任意时间运行，并且可能会中断正在进行的分配。

仅将LockedHeap设置为全局分配器是不够的。原因是我们使用了构造函数empty，创建了一个没有任何后备内存的分配器。就像我们的假分配器一样，它总是在alloc时返回错误。为了解决这个问题，我们需要在创建堆之后初始化分配器：

in src/allocator.rs

pub fn init_heap(
    mapper: &mut impl Mapper<Size4KiB>,
    frame_allocator: &mut impl FrameAllocator<Size4KiB>,
) -> Result<(), MapToError<Size4KiB>> {
    // […] map all heap pages to physical frames

    // new
    unsafe {
        ALLOCATOR.lock().init(HEAP_START, HEAP_SIZE);
    }

    Ok(())
}

我们在LockedHeap类型的内部自旋锁上使用lock方法来获取对封装后的Heap实例的排他引用，然后在该实例上调用以堆边界为参数的init方法。重要的是，我们在映射堆页面之后才初始化堆，因为init函数已经在尝试写入堆内存了。

初始化堆之后就可以使用内置alloccrate的所有分配和收集类型，而且并不会出现错误：

in src/main.rs

use alloc::{boxed::Box, vec, vec::Vec, rc::Rc};

fn kernel_main(boot_info: &'static BootInfo) -> ! {
    // […] initialize interrupts, mapper, frame_allocator, heap

    // allocate a number on the heap
    let heap_value = Box::new(41);
    println!("heap_value at {:p}", heap_value);

    // create a dynamically sized vector
    let mut vec = Vec::new();
    for i in 0..500 {
        vec.push(i);
    }
    println!("vec at {:p}", vec.as_slice());

    // create a reference counted vector -> will be freed when count reaches 0
    let reference_counted = Rc::new(vec![1, 2, 3]);
    let cloned_reference = reference_counted.clone();
    println!("current reference count is {}", Rc::strong_count(&cloned_reference));
    core::mem::drop(reference_counted);
    println!("reference count is {} now", Rc::strong_count(&cloned_reference));

    // […] call `test_main` in test context
    println!("It did not crash!");
    blog_os::hlt_loop();
}

代码展示了Box、Vec和Rc类型的部分使用。对于Box和Vec类型，我们使用{:p}格式说明符来打印底层堆指针。为了展示Rc，我们创建一个引用计数的堆值，并在删除实例（使用core::mem::drop）前后分别使用Rc::strong_count函数两次打印引用计数。

运行将会看到以下内容：

不出所料，我们看到Box和Vec值存在于堆中，正如以0x_4444_4444_*为前缀的指针所指示。引用计数值也可以按预期方式运行，调用clone后，引用计数为2，在删除其中一个实例后，引用计数变为1。

向量从偏移量0x800开始的原因并不是Box类型的值大小为0x800字节，而是因为向量需要扩充容量时发生了再分配。例如，当向量的容量为32且我们尝试添加下一个元素时，向量将在后台分配一个容量为64的新后备数组，并将所有元素复制到到新数组，然后再释放掉旧分配。

当然，我们还有很多alloccrate中的其他分配器和集合类型可以在内核中使用，包括：

• 线程安全引用计数指针Arc
• Rust的字符串类型String和format!格式化宏
• 链表LinkedList
• 可增长的环形缓冲区VecDeque
• 优先级队列BinaryHeap
• BTreeMap和BTreeSet

当我们要实现线程列表、调度队列、或async/await支持时，这些类型将会非常有用。

添加测试

为了确保新的分配器代码不会被意外破坏，我们应该为其添加一个集成测试。首先创建一个新的tests/heap_allocation.rs文件，其内容如下：

in tests/heap_allocation.rs

#![no_std]
#![no_main]
#![feature(custom_test_frameworks)]
#![test_runner(blog_os::test_runner)]
#![reexport_test_harness_main = "test_main"]

extern crate alloc;

use bootloader::{entry_point, BootInfo};
use core::panic::PanicInfo;

entry_point!(main);

fn main(boot_info: &'static BootInfo) -> ! {
    unimplemented!();
}

#[panic_handler]
fn panic(info: &PanicInfo) -> ! {
    blog_os::test_panic_handler(info)
}

我们重用了lib.rs中的test_runner和test_panic_handler函数。由于我们要测试分配器，所以需要使用extern crate alloc语句启用alloccrate。 有关测试样板的更多信息，请查看前面的测试一文。

main函数的实现如下所示：

in tests/heap_allocation.rs

fn main(boot_info: &'static BootInfo) -> ! {
    use blog_os::allocator;
    use blog_os::memory::{self, BootInfoFrameAllocator};
    use x86_64::VirtAddr;

    blog_os::init();
    let phys_mem_offset = VirtAddr::new(boot_info.physical_memory_offset);
    let mut mapper = unsafe { memory::init(phys_mem_offset) };
    let mut frame_allocator = unsafe {
        BootInfoFrameAllocator::init(&boot_info.memory_map)
    };
    allocator::init_heap(&mut mapper, &mut frame_allocator)
        .expect("heap initialization failed");

    test_main();
    loop {}
}

它与main.rs中的kernel_main函数非常相似，不同之处在于我们不调用println，不包括任何分配示例，并且无条件调用test_main。

现在我们准备添加一些测试用例。首先，我们添加一个测试，以使用Box执行一些简单的分配并检查分配的值，以确保基本分配有效：

in tests/heap_allocation.rs

use alloc::boxed::Box;

#[test_case]
fn simple_allocation() {
    let heap_value_1 = Box::new(41);
    let heap_value_2 = Box::new(13);
    assert_eq!(*heap_value_1, 41);
    assert_eq!(*heap_value_2, 13);
}

最重要的是，此测试可验证是否发生分配错误。

接下来，我们循环新建一个大型向量，以测试大型分配和多重分配（以测试再分配）：

in tests/heap_allocation.rs

use alloc::vec::Vec;

#[test_case]
fn large_vec() {
    let n = 1000;
    let mut vec = Vec::new();
    for i in 0..n {
        vec.push(i);
    }
    assert_eq!(vec.iter().sum::<u64>(), (n - 1) * n / 2);
}

我们通过与求和公式进行比较来验证向量求和。这使我们确信分配的值都是正确的。

作为第三项测试，我们在执行一万次分配：

in tests/heap_allocation.rs

use blog_os::allocator::HEAP_SIZE;

#[test_case]
fn many_boxes() {
    for i in 0..HEAP_SIZE {
        let x = Box::new(i);
        assert_eq!(*x, i);
    }
}

此测试确保分配器将释放的内存重新用于后续分配，否则分配器将耗尽内存。这似乎是对分配器的基本要求，但是有些分配器设计并没有这样做。一个示例是线性分配器，我们将在下一篇文章中进行解释。

运行新的集成测试：

> cargo test --test heap_allocation
[…]
Running 3 tests
simple_allocation... [ok]
large_vec... [ok]
many_boxes... [ok]

三个测试全部通过！你还可以调用cargo test（不使用--test参数）来运行所有单元测试和集成测试。

小结

在这篇文章中，我们了解了动态内存的概念、为什么要使用动态内存以及需要在什么地方使用动态内存。我们了解了Rust的借用检查器如何防止常见漏洞，以及Rust分配器API的工作方式。

在使用假分配器创建了Rust分配器接口的最小化实现之后，我们为内核创建了一个适当的堆内存区域。为此，我们为堆定义了一个虚拟地址范围，然后使用上一篇文章中的Mapper和FrameAllocator将地址范围中的所有页面映射到物理帧。

最后，我们添加了对linked_list_allocatorcrate的依赖，以在内核中应用已有的分配器实现。利用此分配器，我们能够使用Box、Vec以及alloc crate中的其他分配器和集合类型。

下期预告

虽然我们已经在本文中添加了堆分配支持，但也将大部分工作留给了现成的linked_list_allocatorcrate。下一篇文章将详细展示如何从头开始实现分配器，并将介绍多种可能的分配器设计，展示如何实现它们的简单版本，并阐述它们的优缺点。

支持本项目

创建和维护这个博客和相关库是一项繁重的工作，但我真的很喜欢。通过支持我，您可以让我在新内容、新功能和持续维护上投入更多时间。

支持我的最好方式是在GitHub上赞助我，因为他们不收取任何中间费用。如果你喜欢其他平台，我也有Patreon和Donorbox账户。后者是最灵活的，因为它支持多种货币和一次性捐款。

感谢您的支持！