分配内存

使用 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，这些函数在 std::alloc 中可用于稳定的 Rust。预计这些函数将被弃用，转而使用 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() {}