Writing an OS in Rust : Rust Heap Allocation 动态内存分配原理

原文地址

为了保证概念的严谨性，翻译时保留了英文原文。

This post adds support for heap allocation to our kernel. First, it gives an introduction to dynamic memory and shows how the borrow checker prevents common allocation errors. It then implements the basic allocation interface of Rust, creates a heap memory region, and sets up an allocator crate. At the end of this post, all the allocation and collection types of the built-in alloc crate will be available to our kernel.

这篇文章为我们的内核添加了对堆内存分配的支持。首先，它介绍了动态内存，并展示了借用检查器如何防止常见的分配错误。然后它实现 Rust 的基本分配接口，创建堆内存区域，并介绍了如何设置和使用 分配器 crate。在本文的结尾，alloc crate 中的内置分配和收集类型都将可供内核使用。

This blog is openly developed on GitHub. If you have any problems or questions, please open an issue there. You can also leave comments at the bottom. The complete source code for this post can be found in the post-10 branch.

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

1. 局部变量和静态变量(Local and Static Variables)

We currently use two types of variables in our kernel: local variables and static variables. Local variables are stored on the call stack and are only valid until the surrounding function returns. Static variables are stored at a fixed memory location and always live for the complete lifetime of the program.

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

1.1 局部变量(Local Variables)

Local variables are stored on the call stack, which is a stack data structure that supports push and pop operations. On each function entry, the parameters, the return address, and the local variables of the called function are pushed by the compiler:

局部变量存储在调用栈上，调用栈是支持 push 和 pop 操作的栈数据结构。在每个函数入口上，编译器都会push被调用函数的参数、返回地址和局部变量：

The above example shows the call stack after the outer function called the inner function. We see that the call stack contains the local variables of outer first. On the inner call, the parameter 1 and the return address for the function were pushed. Then control was transferred to inner, which pushed its local variables.

上面的示例显示了 outer 函数调用 inner 函数之后的调用栈。我们看到调用栈首先包含 outer 的局部变量。在 inner 调用中，参数 1 和函数的返回地址被push。然后控制权被转移到 inner ，然后push其局部变量。

After the inner function returns, its part of the call stack is popped again and only the local variables of outer remain:

inner 函数返回后，其调用栈部分将再次弹出，仅保留 outer 的局部变量：

We see that the local variables of inner only live until the function returns. The Rust compiler enforces these lifetimes and throws an error when we use a value for too long, for example when we try to return a reference to a local variable:

我们看到 inner 的局部变量只在函数返回之前有效。 Rust 编译器会强制执行这些生命周期检查，并在我们使用某个值的时间过长时抛出错误，例如当我们尝试返回对局部变量的引用时：

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

(run the example on the playground)

While returning a reference makes no sense in this example, there are cases where we want a variable to live longer than the function. We already saw such a case in our kernel when we tried to load an interrupt descriptor table and had to use a static variable to extend the lifetime.

虽然在本例中返回引用没有意义，但在某些情况下我们希望变量的寿命比函数的寿命长。当我们尝试加载中断描述符表并且必须使用 static 变量来延长生命周期时，我们已经在内核中看到了这种情况。

1.2 静态变量(Static Variables)

Static variables are stored at a fixed memory location separate from the stack. This memory location is assigned at compile time by the linker and encoded in the executable. Statics live for the complete runtime of the program, so they have the 'static lifetime and can always be referenced from local variables:

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

When the inner function returns in the above example, its part of the call stack is destroyed. The static variables live in a separate memory range that is never destroyed, so the &Z[1] reference is still valid after the return.

当上例中的 inner 函数返回时，其调用堆栈部分将被销毁。静态变量位于永远不会被破坏的单独内存范围中，因此 &Z[1] 引用在返回后仍然有效。

Apart from the 'static lifetime, static variables also have the useful property that their location is known at compile time, so that no reference is needed for accessing them. We utilized that property for our println macro: By using a static Writer internally, there is no &mut Writer reference needed to invoke the macro, which is very useful in exception handlers, where we don’t have access to any additional variables.

除了 'static 生命周期之外，静态变量还具有一个有用的属性，即它们的位置在编译时已知，因此无需引用即可访问它们。我们将该属性用于我们的 println 宏：通过在内部使用静态 Writer ，调用该宏不需要 &mut Writer 引用，这在以下情况下非常有用：异常处理程序，我们无法访问任何其他变量。

However, this property of static variables brings a crucial drawback: they are read-only by default. Rust enforces this because a data race would occur if, e.g., two threads modified a static variable at the same time. The only way to modify a static variable is to encapsulate it in a Mutex type, which ensures that only a single &mut reference exists at any point in time. We already used a Mutex for our static VGA buffer Writer.

然而，静态变量的这个属性带来了一个关键的缺点：它们默认是只读的。 Rust 强制执行此操作，因为如果两个线程同时修改静态变量，就会发生数据竞争。修改静态变量的唯一方法是将其封装在 Mutex 类型中，这确保在任何时间点仅存在单个 &mut 引用。我们已经将 Mutex 用于静态 VGA 缓冲区 Writer 。

2. 动态内存(Dynamic Memory)

Local and static variables are already very powerful together and enable most use cases. However, we saw that they both have their limitations:

局部变量和静态变量一起使用已经非常强大并且支持大多数用例。然而，我们看到它们都有其局限性：

• Local variables only live until the end of the surrounding function or block. This is because they live on the call stack and are destroyed after the surrounding function returns.

  局部变量仅存在于周围函数或块的末尾。这是因为它们存在于调用栈上，并在周围函数返回后被销毁。

• Static variables always live for the complete runtime of the program, so there is no way to reclaim and reuse their memory when they’re no longer needed. Also, they have unclear ownership semantics and are accessible from all functions, so they need to be protected by a Mutex when we want to modify them.

  静态变量在程序的整个运行时始终有效，因此当不再需要它们时，无法回收和重用它们的内存。此外，它们具有不明确的所有权语义，并且可以从所有函数访问，因此当我们想要修改它们时，需要使用 Mutex 来保护它们。

Another limitation of local and static variables is that they have a fixed size. So they can’t store a collection that dynamically grows when more elements are added. (There are proposals for unsized rvalues in Rust that would allow dynamically sized local variables, but they only work in some specific cases.)

局部变量和静态变量的另一个限制是它们具有固定的大小。因此，它们无法存储添加更多元素时动态增长的集合。 （Rust 中提出了unsized 大小的右值，允许动态调整局部变量的大小，但它们仅在某些特定情况下有效。）

To circumvent these drawbacks, programming languages often support a third memory region for storing variables called the heap. The heap supports dynamic memory allocation at runtime through two functions called allocate and deallocate. It works in the following way: The allocate function returns a free chunk of memory of the specified size that can be used to store a variable. This variable then lives until it is freed by calling the deallocate function with a reference to the variable.

为了避免这些缺点，编程语言通常支持第三个内存区域来存储变量，称为堆。堆通过两个名为 allocate 和 deallocate 的函数支持运行时动态内存分配。它的工作方式如下： allocate 函数返回指定大小的空闲内存块，可用于存储变量。然后，该变量将一直存在，直到通过使用该变量的引用调用 deallocate 函数将其释放为止。

Let’s go through an example:

让我们看一个例子：

Here the inner function uses heap memory instead of static variables for storing z. It first allocates a memory block of the required size, which returns a *mut u32 raw pointer. It then uses the ptr::write method to write the array [1,2,3] to it. In the last step, it uses the offset function to calculate a pointer to the i-th element and then returns it. (Note that we omitted some required casts and unsafe blocks in this example function for brevity.)

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

The allocated memory lives until it is explicitly freed through a call to deallocate. Thus, the returned pointer is still valid even after inner returned and its part of the call stack was destroyed. The advantage of using heap memory compared to static memory is that the memory can be reused after it is freed, which we do through the deallocate call in outer. After that call, the situation looks like this:

堆分配的内存一直存在，直到通过调用 deallocate 显式释放为止。因此，即使在 inner 返回并且其调用栈的一部分被销毁之后，返回的指针仍然有效。与静态内存相比，使用堆内存的优点是内存释放后可以重用，我们通过 outer 中的 deallocate 调用来实现这一点。调用之后，情况如下所示：

We see that the z[1] slot is free again and can be reused for the next allocate call. However, we also see that z[0] and z[2] are never freed because we never deallocate them. Such a bug is called a memory leak and is often the cause of excessive memory consumption of programs (just imagine what happens when we call inner repeatedly in a loop). This might seem bad, but there are much more dangerous types of bugs that can happen with dynamic allocation.

我们看到 z[1] 槽再次空闲，并且可以重新用于下一个 allocate 调用。然而，我们也看到 z[0] 和 z[2] 永远不会被释放，因为我们永远不会释放它们。这样的 bug 被称为内存泄漏，通常是程序内存消耗过多的原因（想象一下当我们在循环中重复调用 inner 时会发生什么）。这可能看起来很糟糕，但动态分配可能会出现更危险的错误类型。

2.1 常见错误（Common Errors）

Apart from memory leaks, which are unfortunate but don’t make the program vulnerable to attackers, there are two common types of bugs with more severe consequences:

除了内存泄漏（虽然不幸但不会使程序容易受到攻击者的攻击）之外，还有两种常见类型的错误会带来更严重的后果：

• When we accidentally continue to use a variable after calling deallocate on it, we have a so-called use-after-free vulnerability. Such a bug causes undefined behavior and can often be exploited by attackers to execute arbitrary code.

• 当我们在调用 deallocate 后不小心继续使用变量时，就会出现所谓的释放后使用漏洞。此类错误会导致未定义的行为，并且通常可以被攻击者利用来执行任意代码。

• When we accidentally free a variable twice, we have a double-free vulnerability. This is problematic because it might free a different allocation that was allocated in the same spot after the first deallocate call. Thus, it can lead to a use-after-free vulnerability again.

• 当我们不小心释放一个变量两次时，就会出现双重释放漏洞。这是有问题的，因为它可能会释放在第一次 deallocate 调用后在同一位置分配的不同分配。因此，它可能再次导致释放后使用漏洞。

These types of vulnerabilities are commonly known, so one might expect that people have learned how to avoid them by now. But no, such vulnerabilities are still regularly found, for example this use-after-free vulnerability in Linux (2019), that allowed arbitrary code execution. A web search like use-after-free linux {current year} will probably always yield results. This shows that even the best programmers are not always able to correctly handle dynamic memory in complex projects.

这些类型的漏洞是众所周知的，因此人们可能认为人们现在已经学会了如何避免它们。但事实并非如此，此类漏洞仍然经常被发现，例如 Linux（2019）中的释放后使用漏洞，该漏洞允许执行任意代码。像 use-after-free linux {current year} 这样的网络搜索可能总是会产生结果。这表明，即使是最好的程序员也并不总是能够正确处理复杂项目中的动态内存。

To avoid these issues, many languages, such as Java or Python, manage dynamic memory automatically using a technique called garbage collection. The idea is that the programmer never invokes deallocate manually. Instead, the program is regularly paused and scanned for unused heap variables, which are then automatically deallocated. Thus, the above vulnerabilities can never occur. The drawbacks are the performance overhead of the regular scan and the probably long pause times.

为了避免这些问题，许多语言（例如 Java 或 Python）使用一种称为垃圾收集的技术自动管理动态内存。这个想法是程序员永远不会手动调用 deallocate 。相反，程序会定期暂停并扫描未使用的堆变量，然后自动释放这些变量。因此，上述漏洞永远不会发生。缺点是定期扫描的性能开销以及可能较长的暂停时间。

Rust takes a different approach to the problem: It uses a concept called ownership that is able to check the correctness of dynamic memory operations at compile time. Thus, no garbage collection is needed to avoid the mentioned vulnerabilities, which means that there is no performance overhead. Another advantage of this approach is that the programmer still has fine-grained control over the use of dynamic memory, just like with C or C++.

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

2.2 Rust 中的内存分配 （Allocations in Rust ）

Instead of letting the programmer manually call allocate and deallocate, the Rust standard library provides abstraction types that call these functions implicitly. The most important type is Box, which is an abstraction for a heap-allocated value. It provides a Box::new constructor function that takes a value, calls allocate with the size of the value, and then moves the value to the newly allocated slot on the heap. To free the heap memory again, the Box type implements the Drop trait to call deallocate when it goes out of scope:

Rust 标准库提供了隐式调用这些函数的抽象类型，而不是让程序员手动调用 allocate 和 deallocate 。最重要的类型是 Box ，它是堆分配值的抽象。它提供了一个 Box::new 构造函数，该函数接受一个值，使用该值的大小调用 allocate ，然后将该值移动到堆上新分配的槽中。为了再次释放堆内存， Box 类型实现了 Drop 特征，以在超出范围时调用 deallocate ：

{
    let z = Box::new([1,2,3]);
    […]
} // z goes out of scope and `deallocate` is called

This pattern has the strange name resource acquisition is initialization (or RAII for short). It originated in C++, where it is used to implement a similar abstraction type called std::unique_ptr.

这种模式有一个奇怪的名字：资源获取就是初始化（resource acquisition is initialization）（或简称RAII）。它起源于 C++，用于实现名为 std::unique_ptr 的类似抽象类型。

Such a type alone does not suffice to prevent all use-after-free bugs since programmers can still hold on to references after the Box goes out of scope and the corresponding heap memory slot is deallocated:

单独这样的类型不足以防止所有释放后使用错误，因为在 Box 超出范围并且相应的堆内存槽被释放后，程序员仍然可以保留引用：

let x = {
    let z = Box::new([1,2,3]);
    &z[1]
}; // z goes out of scope and `deallocate` is called
println!("{}", x);

This is where Rust’s ownership comes in. It assigns an abstract lifetime to each reference, which is the scope in which the reference is valid. In the above example, the x reference is taken from the z array, so it becomes invalid after z goes out of scope. When you run the above example on the playground you see that the Rust compiler indeed throws an error:

这就是 Rust 所有权的用武之地。它为每个引用分配一个抽象的生命周期，即引用有效的范围。在上面的示例中， x 引用取自 z 数组，因此在 z 超出范围后它就会变得无效。当您在 Playground 上运行上面的示例时，您会发现 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

The terminology can be a bit confusing at first. Taking a reference to a value is called borrowing the value since it’s similar to a borrow in real life: You have temporary access to an object but need to return it sometime, and you must not destroy it. By checking that all borrows end before an object is destroyed, the Rust compiler can guarantee that no use-after-free situation can occur.

一开始这些术语可能有点令人困惑。引用一个值被称为借用该值，因为它类似于现实生活中的借用：您可以临时访问一个对象，但需要在某个时候返回它，并且不能销毁它。通过检查所有借用在对象被销毁之前是否结束，Rust 编译器可以保证不会发生释放后使用的情况。

Rust’s ownership system goes even further, preventing not only use-after-free bugs but also providing complete memory safety, as garbage collected languages like Java or Python do. Additionally, it guarantees thread safety and is thus even safer than those languages in multi-threaded code. And most importantly, all these checks happen at compile time, so there is no runtime overhead compared to hand-written memory management in C.

Rust 的所有权系统更进一步，不仅可以防止释放后使用错误，还可以提供完整的内存安全性，就像 Java 或 Python 等垃圾收集语言所做的那样。此外，它保证了线程安全，因此比多线程代码中的语言更安全。最重要的是，所有这些检查都发生在编译时，因此与 C 中手写的内存管理相比，没有运行时开销。

2.3 用例(Use Cases)

We now know the basics of dynamic memory allocation in Rust, but when should we use it? We’ve come really far with our kernel without dynamic memory allocation, so why do we need it now?

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

First, dynamic memory allocation always comes with a bit of performance overhead since we need to find a free slot on the heap for every allocation. For this reason, local variables are generally preferable, especially in performance-sensitive kernel code. However, there are cases where dynamic memory allocation is the best choice.

首先，动态内存分配总是会带来一些性能开销，因为我们需要在堆上为每次分配找到一个空闲槽。因此，局部变量通常更可取，特别是在性能敏感的内核代码中。但是，在某些情况下，动态内存分配是最佳选择。

As a basic rule, dynamic memory is required for variables that have a dynamic lifetime or a variable size. The most important type with a dynamic lifetime is Rc, which counts the references to its wrapped value and deallocates it after all references have gone out of scope. Examples for types with a variable size are Vec, String, and other collection types that dynamically grow when more elements are added. These types work by allocating a larger amount of memory when they become full, copying all elements over, and then deallocating the old allocation.

作为基本规则，具有动态生存期或可变大小的变量需要动态内存。具有动态生命周期的最重要的类型是 Rc ，它计算对其包装值的引用，并在所有引用超出范围后释放它。具有可变大小的类型的示例有 Vec 、 String 以及在添加更多元素时动态增长的其他集合类型。这些类型的工作原理是，当内存已满时，分配大量内存，复制所有元素，然后释放旧分配。

For our kernel, we will mostly need the collection types, for example, to store a list of active tasks when implementing multitasking in future posts.

对于我们的内核，我们主要需要集合类型，例如，在将来的帖子中实现多任务处理时存储活动任务列表。

3. 分配器接口(The Allocator Interface )

The first step in implementing a heap allocator is to add a dependency on the built-in alloc crate. Like the core crate, it is a subset of the standard library that additionally contains the allocation and collection types. To add the dependency on alloc, we add the following to our lib.rs:

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

// in src/lib.rs

extern crate alloc;

Contrary to normal dependencies, we don’t need to modify the Cargo.toml. The reason is that the alloc crate ships with the Rust compiler as part of the standard library, so the compiler already knows about the crate. By adding this extern crate statement, we specify that the compiler should try to include it. (Historically, all dependencies needed an extern crate statement, which is now optional).

与正常的依赖关系相反，我们不需要修改 Cargo.toml 。原因是 alloc 包作为标准库的一部分随 Rust 编译器一起提供，因此编译器已经知道该包。通过添加此 extern crate 语句，我们指定编译器应尝试包含它。 （从历史上看，所有依赖项都需要 extern crate 语句，现在是可选的）。

Since we are compiling for a custom target, we can’t use the precompiled version of alloc that is shipped with the Rust installation. Instead, we have to tell cargo to recompile the crate from source. We can do that by adding it to the unstable.build-std array in our .cargo/config.toml file:

由于我们正在针对自定义目标进行编译，因此我们无法使用 Rust 安装附带的 alloc 的预编译版本。相反，我们必须告诉 Cargo 从源代码重新编译 crate。我们可以通过将其添加到 .cargo/config.toml 文件中的 unstable.build-std 数组来做到这一点：

# in .cargo/config.toml

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

Now the compiler will recompile and include the alloc crate in our kernel.

现在编译器将重新编译并将 alloc 包包含在我们的内核中。

The reason that the alloc crate is disabled by default in #[no_std] crates is that it has additional requirements. When we try to compile our project now, we will see these requirements as errors:

alloc crate 在 #[no_std] 箱子中默认被禁用的原因是它有额外的要求。当我们现在尝试编译项目时，我们将看到这些要求错误：

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.

The error occurs because the alloc crate requires a heap allocator, which is an object that provides the allocate and deallocate functions. In Rust, heap allocators are described by the GlobalAlloc trait, which is mentioned in the error message. To set the heap allocator for the crate, the #[global_allocator] attribute must be applied to a static variable that implements the GlobalAlloc trait.

发生错误的原因是 alloc 包需要堆分配器，该分配器是提供 allocate 和 deallocate 函数的对象。在 Rust 中，堆分配器由错误消息中提到的 GlobalAlloc 特征描述。要设置 crate 的堆分配器，必须将 #[global_allocator] 属性应用于实现 GlobalAlloc 特征的 static 变量。

3.1 GlobalAlloc 特征（The GlobalAlloc Trait ）

The GlobalAlloc trait defines the functions that a heap allocator must provide. The trait is special because it is almost never used directly by the programmer. Instead, the compiler will automatically insert the appropriate calls to the trait methods when using the allocation and collection types of alloc.

GlobalAlloc 特征定义了堆分配器必须提供的函数。该特征很特殊，因为程序员几乎从不直接使用它。相反，当使用 alloc 的分配和集合类型时，编译器会自动插入对特征方法的适当调用。

Since we will need to implement the trait for all our allocator types, it is worth taking a closer look at its declaration:

由于我们需要为所有分配器类型实现该特征，因此值得仔细查看其声明：

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 { ... }
}

It defines the two required methods alloc and dealloc, which correspond to the allocate and deallocate functions we used in our examples:

它定义了两个必需的方法 alloc 和 dealloc ，它们对应于我们在示例中使用的 allocate 和 deallocate 函数：

• The alloc method takes a Layout instance as an argument, which describes the desired size and alignment that the allocated memory should have. It returns a raw pointer to the first byte of the allocated memory block. Instead of an explicit error value, the alloc method returns a null pointer to signal an allocation error. This is a bit non-idiomatic, but it has the advantage that wrapping existing system allocators is easy since they use the same convention.

  alloc 方法采用 Layout 实例作为参数，该实例描述了分配的内存应具有的所需大小和对齐方式。它返回指向已分配内存块的第一个字节的原始指针。 alloc 方法返回一个空指针来指示分配错误，而不是显式错误值。这有点不惯用，但它的优点是包装现有的系统分配器很容易，因为它们使用相同的约定。

• The dealloc method is the counterpart and is responsible for freeing a memory block again. It receives two arguments: the pointer returned by alloc and the Layout that was used for the allocation.

  dealloc 方法是对应的，负责释放内存块。它接收两个参数： alloc 返回的指针和用于分配的 Layout 。

The trait additionally defines the two methods alloc_zeroed and realloc with default implementations:

该特征还定义了两个方法 alloc_zeroed 和 realloc 以及默认实现：

• The alloc_zeroed method is equivalent to calling alloc and then setting the allocated memory block to zero, which is exactly what the provided default implementation does. An allocator implementation can override the default implementations with a more efficient custom implementation if possible.

  alloc_zeroed 方法相当于调用 alloc ，然后将分配的内存块设置为零，这正是提供的默认实现的作用。如果可能的话，分配器实现可以使用更有效的自定义实现来覆盖默认实现。

• The realloc method allows to grow or shrink an allocation. The default implementation allocates a new memory block with the desired size and copies over all the content from the previous allocation. Again, an allocator implementation can probably provide a more efficient implementation of this method, for example by growing/shrinking the allocation in-place if possible.

  realloc 方法允许增加或缩小分配。默认实现会分配一个具有所需大小的新内存块，并复制先前分配的所有内容。同样，分配器实现可能可以提供此方法的更有效的实现，例如，如果可能的话，通过就地增加/缩小分配。

3.1.1 不安全（Unsafety ）

One thing to notice is that both the trait itself and all trait methods are declared as unsafe:

需要注意的一件事是，特征本身和所有特征方法都声明为 unsafe ：

• The reason for declaring the trait as unsafe is that the programmer must guarantee that the trait implementation for an allocator type is correct. For example, the alloc method must never return a memory block that is already used somewhere else because this would cause undefined behavior.

  将特征声明为 unsafe 的原因是程序员必须保证分配器类型的特征实现是正确的。例如， alloc 方法绝不能返回已在其他地方使用的内存块，因为这会导致未定义的行为。

• Similarly, the reason that the methods are unsafe is that the caller must ensure various invariants when calling the methods, for example, that the Layout passed to alloc specifies a non-zero size. This is not really relevant in practice since the methods are normally called directly by the compiler, which ensures that the requirements are met.

  同样，方法之所以是 unsafe 是因为调用者在调用方法时必须保证各种不变量，例如传递给 alloc 的 Layout 指定非零大小。这在实践中并不真正相关，因为这些方法通常由编译器直接调用，这确保了满足要求。

3.2 一个 DummyAllocator（ A DummyAllocator ）

Now that we know what an allocator type should provide, we can create a simple dummy allocator. For that, we create a new allocator module:

现在我们知道分配器类型应该提供什么，我们可以创建一个简单的虚拟分配器。为此，我们创建一个新的 allocator 模块：

// in src/lib.rs

pub mod allocator;

Our dummy allocator does the absolute minimum to implement the trait and always returns an error when alloc is called. It looks like this:

我们的虚拟分配器支持了最小的操作集来实现该特征，并且在调用 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")
    }
}

The struct does not need any fields, so we create it as a zero-sized type. As mentioned above, we always return the null pointer from alloc, which corresponds to an allocation error. Since the allocator never returns any memory, a call to dealloc should never occur. For this reason, we simply panic in the dealloc method. The alloc_zeroed and realloc methods have default implementations, so we don’t need to provide implementations for them.

该结构不需要任何字段，因此我们将其创建为零大小类型。如上所述，我们总是从 alloc 返回空指针，这对应于分配错误。由于分配器永远不会返回任何内存，因此永远不应该调用 dealloc 。因此，我们只是在 dealloc 方法中恐慌。 alloc_zeroed 和 realloc 方法有默认实现，因此我们不需要为它们提供实现。

We now have a simple allocator, but we still have to tell the Rust compiler that it should use this allocator. This is where the #[global_allocator] attribute comes in.

我们现在有了一个简单的分配器，但我们仍然必须告诉 Rust 编译器它应该使用这个分配器。这就是 #[global_allocator] 属性的用武之地。

3.3 #[global_allocator] 属性(The #[global_allocator] Attribute )

The #[global_allocator] attribute tells the Rust compiler which allocator instance it should use as the global heap allocator. The attribute is only applicable to a static that implements the GlobalAlloc trait. Let’s register an instance of our Dummy allocator as the global allocator:

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

// in src/allocator.rs

#[global_allocator]
static ALLOCATOR: Dummy = Dummy;

Since the Dummy allocator is a zero-sized type, we don’t need to specify any fields in the initialization expression.

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

With this static, the compilation errors should be fixed. Now we can use the allocation and collection types of alloc. For example, we can use a Box to allocate a value on the heap:

有了这个静态，编译错误就应该被修复。现在我们可以使用 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();
}

Note that we need to specify the extern crate alloc statement in our main.rs too. This is required because the lib.rs and main.rs parts are treated as separate crates. However, we don’t need to create another #[global_allocator] static because the global allocator applies to all crates in the project. In fact, specifying an additional allocator in another crate would be an error.

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

When we run the above code, we see that a panic occurs:

当我们运行上面的代码时，我们看到发生了恐慌：

The panic occurs because the Box::new function implicitly calls the alloc function of the global allocator. Our dummy allocator always returns a null pointer, so every allocation fails. To fix this, we need to create an allocator that actually returns usable memory.

发生恐慌是因为 Box::new 函数隐式调用全局分配器的 alloc 函数。我们的虚拟分配器总是返回一个空指针，因此每次分配都会失败。为了解决这个问题，我们需要创建一个实际返回可用内存的分配器。

4. 创建内核堆(Creating a Kernel Heap)

Before we can create a proper allocator, we first need to create a heap memory region from which the allocator can allocate memory. To do this, we need to define a virtual memory range for the heap region and then map this region to physical frames. See the “Introduction To Paging” post for an overview of virtual memory and page tables.

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

The first step is to define a virtual memory region for the heap. We can choose any virtual address range that we like, as long as it is not already used for a different memory region. Let’s define it as the memory starting at address 0x_4444_4444_0000 so that we can easily recognize a heap pointer later:

第一步是为堆定义虚拟内存区域。我们可以选择任何我们喜欢的虚拟地址范围，只要它尚未用于不同的内存区域即可。我们将其定义为从地址 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

We set the heap size to 100 KiB for now. If we need more space in the future, we can simply increase it.

我们暂时将堆大小设置为 100 KiB。如果我们将来需要更多空间，我们可以简单地增加它。

If we tried to use this heap region now, a page fault would occur since the virtual memory region is not mapped to physical memory yet. To resolve this, we create an init_heap function that maps the heap pages using the Mapper API that we introduced in the “Paging Implementation” post:

如果我们现在尝试使用此堆区域，则会发生页面错误，因为虚拟内存区域尚未映射到物理内存。为了解决这个问题，我们创建一个 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,
    frame_allocator: &mut impl FrameAllocator,
) -> Result {
    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(())
}

The function takes mutable references to a Mapper and a FrameAllocator instance, both limited to 4 KiB pages by using Size4KiB as the generic parameter. The return value of the function is a Result with the unit type () as the success variant and a MapToError as the error variant, which is the error type returned by the Mapper::map_to method. Reusing the error type makes sense here because the map_to method is the main source of errors in this function.

该函数采用对 Mapper 和 FrameAllocator 实例的可变引用，通过使用 Size4KiB 作为通用参数，两者都限制为 4 KiB 页面。函数的返回值是一个 Result ，其中单元类型 () 作为成功变量， MapToError 作为错误变量，这是返回的错误类型通过 Mapper::map_to 方法。在这里重用错误类型是有意义的，因为 map_to 方法是该函数中错误的主要来源。

The implementation can be broken down into two parts:

实现可以分为两部分：

• Creating the page range:: To create a range of the pages that we want to map, we convert the HEAP_START pointer to a VirtAddr type. Then we calculate the heap end address from it by adding the HEAP_SIZE. We want an inclusive bound (the address of the last byte of the heap), so we subtract 1. Next, we convert the addresses into Page types using the containing_address function. Finally, we create a page range from the start and end pages using the Page::range_inclusive function.

  创建页范围：为了创建我们想要映射的页范围，我们将 HEAP_START 指针转换为 VirtAddr 类型。然后我们通过添加 HEAP_SIZE 来计算堆结束地址。我们想要一个包含边界（堆最后一个字节的地址），因此我们减去 1。接下来，我们使用 containing_address 函数将地址转换为 Page 类型。最后，我们使用 Page::range_inclusive 函数从起始页和结束页创建一个页面范围。

• Mapping the pages: The second step is to map all pages of the page range we just created. For that, we iterate over these pages using a for loop. For each page, we do the following:

  映射页面：第二步是映射我们刚刚创建的页面范围的所有页面。为此，我们使用 for 循环迭代这些页面。对于每个页面，我们执行以下操作：

  • We allocate a physical frame that the page should be mapped to using the FrameAllocator::allocate_frame method. This method returns None when there are no more frames left. We deal with that case by mapping it to a MapToError::FrameAllocationFailed error through the Option::ok_or method and then applying the question mark operator to return early in the case of an error.

    我们使用 FrameAllocator::allocate_frame 方法分配页面应映射到的物理页。当没有剩余页时，此方法返回 None 。我们通过 Option::ok_or 方法将其映射到 MapToError::FrameAllocationFailed 错误来处理这种情况，然后应用问号运算符在出现错误时尽早返回。

  • We set the required PRESENT flag and the WRITABLE flag for the page. With these flags, both read and write accesses are allowed, which makes sense for heap memory.

    我们为页面设置所需的 PRESENT 标志和 WRITABLE 标志。使用这些标志，允许读取和写入访问，这对于堆内存来说是有意义的。

  • We use the Mapper::map_to method for creating the mapping in the active page table. The method can fail, so we use the question mark operator again to forward the error to the caller. On success, the method returns a MapperFlush instance that we can use to update the translation lookaside buffer using the flush method.

    我们使用 Mapper::map_to 方法在活动页表中创建映射。该方法可能会失败，因此我们再次使用问号运算符将错误转发给调用者。成功时，该方法返回一个 MapperFlush 实例，我们可以使用该实例通过 flush 方法更新翻译后备缓冲区。

The final step is to call this function from our kernel_main:

最后一步是从我们的 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();
}

We show the full function for context here. The only new lines are the blog_os::allocator import and the call to the allocator::init_heap function. In case the init_heap function returns an error, we panic using the Result::expect method since there is currently no sensible way for us to handle this error.

我们在这里展示了上下文的完整功能。唯一的新行是 blog_os::allocator 导入和对 allocator::init_heap 函数的调用。如果 init_heap 函数返回错误，我们会使用 Result::expect 方法来恐慌，因为目前没有明智的方法来处理此错误。

We now have a mapped heap memory region that is ready to be used. The Box::new call still uses our old Dummy allocator, so you will still see the “out of memory” error when you run it. Let’s fix this by using a proper allocator.

现在我们有了一个可以使用的映射堆内存区域。 Box::new 调用仍然使用我们旧的 Dummy 分配器，因此运行它时您仍然会看到“内存不足”错误。让我们使用适当的分配器来解决这个问题。

5. 使用外部 分配器 crate（Using an Allocator Crate ）

Since implementing an allocator is somewhat complex, we start by using an external allocator crate. We will learn how to implement our own allocator in the next post.

由于实现分配器有些复杂，因此我们首先使用外部分配器crate。我们将在下一篇文章中学习如何实现我们自己的分配器。

A simple allocator crate for no_std applications is the linked_list_allocator crate. Its name comes from the fact that it uses a linked list data structure to keep track of deallocated memory regions. See the next post for a more detailed explanation of this approach.

no_std 应用程序的一个简单分配器 crate是 linked_list_allocator crate。它的名字来源于它使用链表数据结构来跟踪已释放的内存区域。有关此方法的更详细说明，请参阅下一篇文章。

To use the crate, we first need to add a dependency on it in our Cargo.toml:

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

# in Cargo.toml

[dependencies]
linked_list_allocator = "0.9.0"

Then we can replace our dummy allocator with the allocator provided by the crate:

然后我们可以用crate 提供的分配器替换我们的虚拟分配器：

// in src/allocator.rs

use linked_list_allocator::LockedHeap;

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

The struct is named LockedHeap because it uses the spinning_top::Spinlock type for synchronization. This is required because multiple threads could access the ALLOCATOR static at the same time. As always, when using a spinlock or a mutex, we need to be careful to not accidentally cause a deadlock. This means that we shouldn’t perform any allocations in interrupt handlers, since they can run at an arbitrary time and might interrupt an in-progress allocation.

该结构体被命名为 LockedHeap ，因为它使用 spinning_top::Spinlock 类型进行同步。这是必需的，因为多个线程可以同时访问 ALLOCATOR 静态。与往常一样，当使用自旋锁或互斥体时，我们需要小心，不要意外地导致死锁。这意味着我们不应该在中断处理程序中执行任何分配，因为它们可以在任意时间运行，并且可能会中断正在进行的分配。

Setting the LockedHeap as global allocator is not enough. The reason is that we use the empty constructor function, which creates an allocator without any backing memory. Like our dummy allocator, it always returns an error on alloc. To fix this, we need to initialize the allocator after creating the heap:

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

// in src/allocator.rs

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

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

    Ok(())
}

We use the lock method on the inner spinlock of the LockedHeap type to get an exclusive reference to the wrapped Heap instance, on which we then call the init method with the heap bounds as arguments. Because the init function already tries to write to the heap memory, we must initialize the heap only after mapping the heap pages.

我们在 LockedHeap 类型的内部自旋锁上使用 lock 方法来获取对包装的 Heap 实例的独占引用，然后在该实例上调用 init 以堆边界作为参数的方法。因为 init 函数已经尝试写入堆内存，所以我们必须在映射堆页之后才初始化堆。

After initializing the heap, we can now use all allocation and collection types of the built-in alloc crate without error:

初始化堆后，我们现在可以使用内置 alloc crate 中的所有分配和集合类型，不会出现错误：

// 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();
}

This code example shows some uses of the Box, Vec, and Rc types. For the Box and Vec types, we print the underlying heap pointers using the {:p} formatting specifier. To showcase Rc, we create a reference-counted heap value and use the Rc::strong_count function to print the current reference count before and after dropping an instance (using core::mem::drop).

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

When we run it, we see the following:

当我们运行它时，我们会看到以下内容：

As expected, we see that the Box and Vec values live on the heap, as indicated by the pointer starting with the 0x_4444_4444_* prefix. The reference counted value also behaves as expected, with the reference count being 2 after the clone call, and 1 again after one of the instances was dropped.

正如预期的那样，我们看到 Box 和 Vec 值位于堆上，如以 0x_4444_4444_* 前缀开头的指针所示。引用计数值的行为也符合预期，在 clone 调用后引用计数为 2，在删除其中一个实例后又再次为 1。

The reason that the vector starts at offset 0x800 is not that the boxed value is 0x800 bytes large, but the reallocations that occur when the vector needs to increase its capacity. For example, when the vector’s capacity is 32 and we try to add the next element, the vector allocates a new backing array with a capacity of 64 behind the scenes and copies all elements over. Then it frees the old allocation.

向量从偏移量 0x800 开始的原因并不是装箱值大 0x800 字节，而是当向量需要增加其容量时发生的重新分配。例如，当向量的容量为 32 并且我们尝试添加下一个元素时，向量会在幕后分配一个容量为 64 的新后备数组，并复制所有元素。然后它释放旧的分配。

Of course, there are many more allocation and collection types in the alloc crate that we can now all use in our kernel, including:

当然， alloc create 中还有更多分配和收集类型，我们现在可以在内核中使用它们，包括：

• the thread-safe reference counted pointer Arc

  线程安全引用计数指针 Arc

• the owned string type String and the format! macro

  拥有的字符串类型 String 和 format! 宏

• LinkedList

• the growable ring buffer VecDeque

  可增长的环形缓冲区 VecDeque

• the BinaryHeap priority queue

  BinaryHeap 优先级队列

• BTreeMap and BTreeSet BTreeMap 和 BTreeSet

These types will become very useful when we want to implement thread lists, scheduling queues, or support for async/await.

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

6. 添加测试(Adding a Test )

To ensure that we don’t accidentally break our new allocation code, we should add an integration test for it. We start by creating a new tests/heap_allocation.rs file with the following content:

为了确保我们不会意外破坏新的分配代码，我们应该为其添加集成测试。我们首先创建一个包含以下内容的新 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)
}

We reuse the test_runner and test_panic_handler functions from our lib.rs. Since we want to test allocations, we enable the alloc crate through the extern crate alloc statement. For more information about the test boilerplate, check out the Testing post.

我们重用 lib.rs 中的 test_runner 和 test_panic_handler 函数。由于我们想要测试分配，因此我们通过 extern crate alloc 语句启用 alloc 箱。有关测试样板的更多信息，请查看测试帖子。

The implementation of the main function looks like this:

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 {}
}

It is very similar to the kernel_main function in our main.rs, with the differences that we don’t invoke println, don’t include any example allocations, and call test_main unconditionally.

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

Now we’re ready to add a few test cases. First, we add a test that performs some simple allocations using Box and checks the allocated values to ensure that basic allocations work:

现在我们准备添加一些测试用例。首先，我们添加一个测试，使用 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);
}

Most importantly, this test verifies that no allocation error occurs.

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

Next, we iteratively build a large vector, to test both large allocations and multiple allocations (due to reallocations):

接下来，我们迭代地构建一个大向量，以测试大分配和多次分配（由于重新分配）：

// 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::(), (n - 1) * n / 2);
}

We verify the sum by comparing it with the formula for the n-th partial sum. This gives us some confidence that the allocated values are all correct.

我们通过将其与第 n 个部分和的公式进行比较来验证该和。这让我们有信心分配的值都是正确的。

As a third test, we create ten thousand allocations after each other:

作为第三个测试，我们依次创建一万个分配：

// 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);
    }
}

This test ensures that the allocator reuses freed memory for subsequent allocations since it would run out of memory otherwise. This might seem like an obvious requirement for an allocator, but there are allocator designs that don’t do this. An example is the bump allocator design that will be explained in the next post.

此测试可确保分配器重新使用已释放的内存进行后续分配，否则会耗尽内存。这似乎对分配器来说是一个明显的要求，但有些分配器设计并不这样做。一个例子是凹凸分配器设计，将在下一篇文章中解释。

Let’s run our new integration test:

让我们运行新的集成测试：

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

All three tests succeeded! You can also invoke cargo test (without the --test argument) to run all unit and integration tests.
三个测试全部成功！您还可以调用 cargo test （不带 --test 参数）来运行所有单元和集成测试。

7. 总结(Summary)

This post gave an introduction to dynamic memory and explained why and where it is needed. We saw how Rust’s borrow checker prevents common vulnerabilities and learned how Rust’s allocation API works.

这篇文章介绍了动态内存，并解释了为什么需要它以及在哪里需要它。我们了解了 Rust 的借用检查器如何防止常见漏洞，并了解了 Rust 的分配 API 的工作原理。

After creating a minimal implementation of Rust’s allocator interface using a dummy allocator, we created a proper heap memory region for our kernel. For that, we defined a virtual address range for the heap and then mapped all pages of that range to physical frames using the Mapper and FrameAllocator from the previous post.

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

Finally, we added a dependency on the linked_list_allocator crate to add a proper allocator to our kernel. With this allocator, we were able to use Box, Vec, and other allocation and collection types from the alloc crate.

最后，我们添加了对 linked_list_allocator 箱的依赖，以向内核添加适当的分配器。有了这个分配器，我们就可以使用 Box 、 Vec 以及 alloc 包中的其他分配和集合类型。

8. 下一步是什么？(What’s next?）

While we already added heap allocation support in this post, we left most of the work to the linked_list_allocator crate. The next post will show in detail how an allocator can be implemented from scratch. It will present multiple possible allocator designs, show how to implement simple versions of them, and explain their advantages and drawbacks.

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