动态内存之堆的分配（一）

这篇文章我们会向你介绍内核是如何添加对堆分配的支持，首先我会介绍动态内存，并展示了借用检查器如何防止常见的分配漏洞。然后，它实现Rust的基本分配接口，创建一个堆内存区域，并设置一个分配器crate。在这篇文章的结尾，内置alloc crate的所有分配和收集类型将对我们的内核可用。另外，此文所介绍的完整源代码可以post-10 分支中找到。

局部和静态变量

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

局部变量

局部变量存储在调用堆栈中，该堆栈是支持推入和弹出操作的堆栈数据结构。在每个函数项上，被调用函数的参数、返回地址和局部变量由编译器推送：

上面的示例显示了外部函数调用内部函数后的调用堆栈，我们看到调用堆栈包含外部优先的局部变量。在内部调用中，参数1和函数的返回地址被推送。然后将控制权转移到内部，从而推送其局部变量。

内部函数返回后，它的调用堆栈部分再次弹出，只有外部的局部变量保留：

可以看到，内部的局部变量只在函数返回之前有效。当我们使用太长的值时，例如当我们尝试返回对局部变量的引用时，Rust编译器会强制执行这些生存期并引发漏洞：

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

虽然在此示例中返回引用毫无意义，但在某些情况下，我们希望变量的寿命比函数更长。当我们已经在内核中看到过这种情况，当时我们试图加载一个中断描述符表，并且必须使用一个静态变量来延长生存期。

静态变量

静态变量存储在与堆栈分开的固定内存位置。链接器在编译时分配了此存储位置，并在可执行文件中进行了编码。静态变量在程序的完整运行时中都有效，因此它们具有“静态寿命”，并且始终可以从局部变量中进行引用：

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

除了“静态生存期”之外，静态变量还有一个有用的属性，即它们的位置在编译时是已知的，因此访问它不需要引用。我们在println宏中使用了这个属性：通过在内部使用静态Writer，不需要＆mut Writer引用即可调用该宏，这在我们无法访问任何其他变量的异常处理程序中非常有用。

但是，静态变量的此属性带来一个关键的缺点：默认情况下，它们是只读的。 Rust强制执行此操作，因为如果两个线程同时修改一个静态变量，就会发生数据竞争。修改静态变量的惟一方法是将其封装在互斥类型中，这可以确保在任何时间点都只存在单个&mut引用。我们已经为静态VGA缓冲区写入器使用了互斥锁。

动态内存

局部变量和静态变量一起已经非常强大，并且支持大多数用例。然而，我们发现它们都有各自的局限性：

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

2. 静态变量总是在程序的完整运行时存在，所以当不再需要它们时，没有办法回收和重用它们的内存。此外，它们的所有权语义不明确，并且可以从所有函数访问，因此当我们想要修改它们时，需要使用互斥锁来保护它们。

局部变量和静态变量的另一个限制是它们的大小是固定的。因此，它们不能存储一个在添加更多元素时动态增长的集合。有人建议在Rust中使用未调整大小的rvalue，这将允许动态调整局部变量的大小，但是它们只在某些特定的情况下起作用。

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

让我们来看一个例子：

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

分配的内存一直存在，直到通过调用deallocate显式释放它。因此，即使内部返回并销毁了调用堆栈的一部分，返回的指针仍然有效。与静态内存相比，使用堆内存的优点是释放内存后可以重用它，这是通过外部的deallocate调用实现的。因此调用之后，情况是这样的：

我们看到z [1]槽又空了，可以重新用于下一个分配调用。但是，我们也看到z [0]和z [2]从未被释放，因为我们从未释放过它们。这种漏洞称为内存泄漏，通常会导致程序内存消耗过多。想象一下，当我们在循环中反复调用inner时会发生什么，这可能看起来很糟糕，但是动态分配可能会发生更多危险的漏洞类型。

常见漏洞

除了不幸的但不会使程序容易受到攻击的内存泄漏外，还有两种常见的漏洞类型，其后果更为严重：

当我们意外地在调用deallocate之后继续使用一个变量时，我们就有了所谓的“释放后可重用”漏洞。这样的漏洞会导致未定义的行为，而且攻击者经常可以利用它来执行任意代码。

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

这些类型的漏洞是众所周知的，因此人们可以期望人们现在已经学会了如何避免它们。但是，没有，仍然经常发现此类漏洞，例如，Linux中最近的这种“先用后用”漏洞允许任意代码执行。这表明即使是最好的程序员也不一定总是能够正确处理复杂项目中的动态内存。

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

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

RustRust中的分配方式

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

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

此模式有一个奇怪的名称:资源获取是初始化或简称为RAII。它起源于c++，用于实现称为std :: unique_ptr的相似抽象类型。

单靠这种类型还足以防止所有的释放后可重用漏洞，因为程序员仍然可以在Box超出范围和相应的堆内存槽释放后保留引用：

let x = {
    let z = Box::new([1,2,3]);
    &z[1]
}; // z goes out of scope and `deallocate` is called
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的所有权不仅可以防止使用后使用的漏洞，而且可以像Java或Python这样的垃圾收集语言提供完全的内存安全性。另外，它保证线程安全，因此比多线程代码中的那些语言更安全。最重要的是，所有这些检查都在编译时进行，因此与C中的手写内存管理相比，没有运行时的消耗。

用例

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

首先，动态内存分配总是会带来一些性能消耗，因为我们需要为每个分配在堆上找到一个空闲插槽。因此，通常最好使用局部变量，尤其是在性能敏感的内核代码中。但是，在某些情况下，动态内存分配是最佳选择。

作为基本规则，具有动态生存期或可变大小的变量需要动态内存。动态生存期最重要的类型是Rc，它计算对其包装值的引用，并在所有引用超出范围后将其释放。具有大小可变的类型的示例包括Vec，String和其他集合类型，这些集合类型在添加更多元素时会动态增长。这些类型的工作方式是在它们变满时分配大量内存，将所有元素复制过来，然后取消分配旧分配。

对于我们的内核，我们最需要的是集合类型，例如，在以后的文章中实现多任务处理时，用于存储活动任务列表。

分配器界面

实现堆分配器的第一步是在内置的alloc crate上添加一个依赖项。与core crate一样，它也是标准库的一个子集，另外还包含了分配和收集类型。为了添加对alloc的依赖，我们在lib中添加了以下内容：

// in src/lib.rs

extern crate alloc;

与正常的依赖关系相反，我们不需要修改Cargo.toml，原因是alloc crate与Rust编译器一起作为标准库的一部分提供，因此我们只需要启用它即可。这就是extern crate语句的作用，曾经，所有依赖项都需要extern crate语句，现在该语句是可选的。

在#[no_std]中，alloc crate在默认情况下是禁用的，原因是它有额外的要求。现在尝试编译项目时，我们可以将这些需求视为漏洞：

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

发生第一个漏洞是因为alloc crate需要堆分配器，该堆分配器是提供分配和解除分配功能的对象。在Rust中，堆分配器由GlobalAlloc trait描述，该trait在漏洞消息中提到。要设置crate的堆分配器，必须将#[global_allocator]属性应用于实现GlobalAlloctrait的静态变量。

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

在下一篇文章中，我们将详细描述这些函数的属性。