分配内存

使用 NonNull 会给 Vec（实际上是所有 std 集合）的一个重要特性带来麻烦：创建空的 Vec 实际上根本不会分配内存。这与分配一个零大小的内存块不同，全局分配器不允许这样做（这会导致未定义的行为！）。因此，如果我们不能分配内存，也不能在 ptr 中放置空指针，那么在 Vec::new 中应该怎么做呢？好吧，我们就在那里放一些其他的垃圾值！

这完全没问题，因为我们已经将 cap == 0 作为没有分配内存的哨兵。我们甚至不需要在几乎任何代码中对其进行特殊处理，因为我们通常需要检查 cap > len 或 len > 0。推荐的 Rust 值是 mem::align_of::<T>()。NonNull 为此提供了一个便利：NonNull::dangling()。在很多地方我们都想使用 dangling，因为没有真正的分配可言，但 null 会导致编译器做坏事。

所以

use std::mem;

impl<T> Vec<T> {
    pub fn new() -> Self {
        assert!(mem::size_of::<T>() != 0, "We're not ready to handle ZSTs");
        Vec {
            ptr: NonNull::dangling(),
            len: 0,
            cap: 0,
        }
    }
}
fn main() {}

我在那里偷偷地加入了断言，因为零大小类型需要在我们的代码中进行一些特殊处理，我想暂时推迟这个问题。如果没有这个断言，我们的一些早期草案将会做一些非常糟糕的事情。

接下来，我们需要弄清楚当我们确实想要空间时该怎么做。为此，我们使用全局分配函数 alloc、realloc 和 dealloc，它们在稳定版 Rust 的 std::alloc 中可用。在 std::alloc::Global 类型稳定后，预计这些函数将被弃用，转而使用该类型的方法。

我们还需要一种方法来处理内存不足（OOM）的情况。标准库提供了一个函数 alloc::handle_alloc_error，它将以平台特定的方式中止程序。我们选择中止而不是 panic 的原因是，展开可能会导致分配内存，而当你的分配器刚刚返回“嘿，我没有更多内存”时，这样做似乎不是什么好事。

当然，这有点傻，因为大多数平台实际上并不会以传统的方式耗尽内存。如果你真的开始耗尽所有内存，你的操作系统可能会通过其他方式杀死应用程序。我们最有可能触发 OOM 的方式是一次性请求过多的内存（例如，理论地址空间的一半）。因此，panic 可能是可以的，不会发生什么坏事。不过，我们正在努力尽可能地模仿标准库，所以我们只会杀死整个程序。

好了，现在我们可以编写增长逻辑了。粗略地说，我们希望有这样的逻辑

if cap == 0:
    allocate()
    cap = 1
else:
    reallocate()
    cap *= 2

但 Rust 唯一支持的分配器 API 级别太低，我们需要做很多额外的工作。我们还需要防范一些特殊情况，这些情况可能发生在真正大的分配或空分配中。

特别是，ptr::offset 会给我们带来很多麻烦，因为它具有 LLVM 的 GEP inbounds 指令的语义。如果你有幸没有接触过这条指令，这里简单介绍一下 GEP：别名分析，别名分析，还是别名分析。对于优化编译器来说，能够推断数据依赖性和别名是非常重要的。

举个简单的例子，考虑以下代码片段

*x *= 7;
*y *= 3;

如果编译器可以证明 x 和 y 指向内存中的不同位置，那么理论上可以并行执行这两个操作（例如，将它们加载到不同的寄存器中并独立地处理它们）。然而，编译器通常无法做到这一点，因为如果 x 和 y 指向内存中的同一个位置，则需要对同一个值执行操作，并且不能在事后简单地合并它们。

当你使用 GEP inbounds 时，你是在明确地告诉 LLVM，你要进行的偏移量在一个“已分配”实体的范围内。最终的好处是，LLVM 可以假设，如果已知两个指针指向两个不相交的对象，那么这些指针的所有偏移量也已知不会发生别名（因为你不会最终到达内存中的某个随机位置）。LLVM 经过高度优化，可以处理 GEP 偏移量，而 inbounds 偏移量是最好的，因此尽可能多地使用它们非常重要。

这就是 GEP 的作用，它怎么会给我们带来麻烦呢？

第一个问题是我们使用无符号整数索引数组，但 GEP（以及 ptr::offset）接受有符号整数。这意味着数组中看似有效的一半索引将导致 GEP 溢出，并实际上朝错误的方向移动！因此，我们必须将所有分配限制为 isize::MAX 个元素。这实际上意味着我们只需要担心字节大小的对象，因为例如 > isize::MAX 个 u16 将真正耗尽系统的所有内存。然而，为了避免将 < isize::MAX 个对象的数组重新解释为字节时出现微妙的极端情况，std 将所有分配限制为 isize::MAX 个字节。

在 Rust 当前支持的所有 64 位目标上，我们都被人为地限制在远小于地址空间所有 64 位的范围内（现代 x64 平台只公开 48 位寻址），因此我们可以依赖于首先耗尽内存。然而，在 32 位目标上，特别是那些使用地址空间扩展的目标（PAE x86 或 x32），理论上可以成功分配超过 isize::MAX 字节的内存。

然而，由于这是一个教程，我们在这里不会特别追求最优，而是无条件地进行检查，而不是使用聪明的平台特定的 cfg。

我们需要担心的另一个极端情况是空分配。我们需要担心两种空分配：所有 T 的 cap = 0，以及零大小类型的 cap > 0。

这些情况很棘手，因为它们归结为 LLVM 对“已分配”的定义。LLVM 对分配的概念比我们通常使用的概念要抽象得多。因为 LLVM 需要处理不同语言的语义和自定义分配器，所以它无法真正深入地理解分配。相反，分配背后的主要思想是“不与其他东西重叠”。也就是说，堆分配、栈分配和全局变量不会随机重叠。是的，这与别名分析有关。因此，只要 Rust 的做法一致，它在技术上就可以在分配的概念上玩一些花招。

回到空分配的情况，在一些地方，我们希望偏移量为 0，这是泛型代码的结果。那么问题是：这样做是否一致？对于零大小类型，我们得出的结论是，对任意数量的元素进行 GEP inbounds 偏移量确实是合理的。这是一个运行时无操作，因为每个元素都不占用空间，并且可以假装在 0x01 处分配了无限个零大小类型。任何分配器都不会分配该地址，因为它们不会分配 0x00，并且它们通常会分配到比字节更高的最小对齐位置。此外，通常情况下，内存的整个第一页都被保护起来，防止被分配（在许多平台上是整整 4k）。

然而，对于正大小类型呢？这就有点棘手了。原则上，你可以说偏移量为 0 不会向 LLVM 提供任何信息：地址之前或之后都有一个元素，但它无法知道是哪个。然而，我们选择保守地假设它可能会做坏事。因此，我们将明确地防范这种情况。

呼

好了，说了这么多废话，让我们来实际分配一些内存吧

use std::alloc::{self, Layout};

impl<T> Vec<T> {
    fn grow(&mut self) {
        let (new_cap, new_layout) = if self.cap == 0 {
            (1, Layout::array::<T>(1).unwrap())
        } else {
            // This can't overflow since self.cap <= isize::MAX.
            let new_cap = 2 * self.cap;

            // `Layout::array` checks that the number of bytes is <= usize::MAX,
            // but this is redundant since old_layout.size() <= isize::MAX,
            // so the `unwrap` should never fail.
            let new_layout = Layout::array::<T>(new_cap).unwrap();
            (new_cap, new_layout)
        };

        // Ensure that the new allocation doesn't exceed `isize::MAX` bytes.
        assert!(new_layout.size() <= isize::MAX as usize, "Allocation too large");

        let new_ptr = if self.cap == 0 {
            unsafe { alloc::alloc(new_layout) }
        } else {
            let old_layout = Layout::array::<T>(self.cap).unwrap();
            let old_ptr = self.ptr.as_ptr() as *mut u8;
            unsafe { alloc::realloc(old_ptr, old_layout, new_layout.size()) }
        };

        // If allocation fails, `new_ptr` will be null, in which case we abort.
        self.ptr = match NonNull::new(new_ptr as *mut T) {
            Some(p) => p,
            None => alloc::handle_alloc_error(new_layout),
        };
        self.cap = new_cap;
    }
}
fn main() {}

Rust 秘典

分配内存