集合

最终，你将希望在你的程序中使用动态数据结构（又称集合）。std 提供了一组常用的集合：Vec、String、HashMap 等。std 中实现的所有集合都使用全局动态内存分配器（又称堆）。

正如定义的那样，core 不进行内存分配，因此这些实现不可用，但它们可以在编译器附带的 alloc crate 中找到。

如果你需要集合，堆分配的实现不是你唯一的选择。你也可以使用固定容量的集合；一个这样的实现可以在 heapless crate 中找到。

在本节中，我们将探索和比较这两种实现。

使用 `alloc`

alloc crate 随标准 Rust 发行版一起提供。要导入该 crate，你可以直接 use 它，而无需在你的 Cargo.toml 文件中将其声明为依赖项。

#![feature(alloc)]

extern crate alloc;

use alloc::vec::Vec;

要使用任何集合，你首先需要使用 global_allocator 属性来声明你的程序将使用的全局分配器。你选择的分配器必须实现 GlobalAlloc trait。

为了完整性和使本节尽可能自包含，我们将实现一个简单的碰撞指针分配器，并将其用作全局分配器。但是，我们强烈建议你在你的程序中使用 crates.io 中经过实战检验的分配器，而不是这个分配器。

// Bump pointer allocator implementation

use core::alloc::{GlobalAlloc, Layout};
use core::cell::UnsafeCell;
use core::ptr;

use cortex_m::interrupt;

// Bump pointer allocator for *single* core systems
struct BumpPointerAlloc {
    head: UnsafeCell<usize>,
    end: usize,
}

unsafe impl Sync for BumpPointerAlloc {}

unsafe impl GlobalAlloc for BumpPointerAlloc {
    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
        // `interrupt::free` is a critical section that makes our allocator safe
        // to use from within interrupts
        interrupt::free(|_| {
            let head = self.head.get();
            let size = layout.size();
            let align = layout.align();
            let align_mask = !(align - 1);

            // move start up to the next alignment boundary
            let start = (*head + align - 1) & align_mask;

            if start + size > self.end {
                // a null pointer signal an Out Of Memory condition
                ptr::null_mut()
            } else {
                *head = start + size;
                start as *mut u8
            }
        })
    }

    unsafe fn dealloc(&self, _: *mut u8, _: Layout) {
        // this allocator never deallocates memory
    }
}

// Declaration of the global memory allocator
// NOTE the user must ensure that the memory region `[0x2000_0100, 0x2000_0200]`
// is not used by other parts of the program
#[global_allocator]
static HEAP: BumpPointerAlloc = BumpPointerAlloc {
    head: UnsafeCell::new(0x2000_0100),
    end: 0x2000_0200,
};

除了选择全局分配器之外，用户还必须使用不稳定的 alloc_error_handler 属性来定义如何处理内存不足 (OOM) 错误。

#![feature(alloc_error_handler)]

use cortex_m::asm;

#[alloc_error_handler]
fn on_oom(_layout: Layout) -> ! {
    asm::bkpt();

    loop {}
}

一旦所有这些都就绪，用户最终就可以使用 alloc 中的集合了。

#[entry]
fn main() -> ! {
    let mut xs = Vec::new();

    xs.push(42);
    assert!(xs.pop(), Some(42));

    loop {
        // ..
    }
}

如果你使用过 std crate 中的集合，那么这些会很熟悉，因为它们是完全相同的实现。

使用 `heapless`

heapless 不需要设置，因为它的集合不依赖于全局内存分配器。只需 use 其集合并继续实例化它们即可

// heapless version: v0.4.x
use heapless::Vec;
use heapless::consts::*;

#[entry]
fn main() -> ! {
    let mut xs: Vec<_, U8> = Vec::new();

    xs.push(42).unwrap();
    assert_eq!(xs.pop(), Some(42));
    loop {}
}

你会注意到这些集合与 alloc 中的集合之间有两个差异。

首先，你必须预先声明集合的容量。heapless 集合永远不会重新分配，并且具有固定的容量；此容量是集合类型签名的一部分。在本例中，我们声明 xs 的容量为 8 个元素，即该向量最多可以容纳 8 个元素。这由类型签名中的 U8 (请参阅 typenum) 表示。

其次，push 方法和许多其他方法都返回一个 Result。由于 heapless 集合具有固定容量，因此所有将元素插入集合的操作都可能失败。API 通过返回一个 Result 来反映这个问题，指示操作是否成功。相反，alloc 集合将在堆上重新分配自身以增加其容量。

从 v0.4.x 版本开始，所有 heapless 集合都将其所有元素内联存储。这意味着诸如 let x = heapless::Vec::new(); 之类的操作将在堆栈上分配集合，但也可能在 static 变量上，甚至在堆上 (Box<Vec<_, _>>) 分配集合。

权衡

在堆分配的可重定位集合和固定容量集合之间进行选择时，请记住以下几点。

内存不足和错误处理

对于堆分配，内存不足始终是一种可能性，并且可能发生在集合可能需要增长的任何地方：例如，所有 alloc::Vec.push 调用都可能生成 OOM 条件。因此，某些操作可能会隐式失败。一些 alloc 集合公开了 try_reserve 方法，让你可以在集合增长时检查潜在的 OOM 条件，但你需要主动使用它们。

如果你专门使用 heapless 集合，并且不使用内存分配器进行其他任何操作，那么 OOM 条件是不可能发生的。相反，你必须在个案的基础上处理集合超出容量的问题。也就是说，你必须处理诸如 Vec.push 之类的方法返回的所有 Result。

OOM 失败可能比在 heapless::Vec.push 返回的所有 Result 上使用 unwrap 更难调试，因为观察到的失败位置可能与问题的原因位置不匹配。例如，如果分配器几乎耗尽，即使 vec.reserve(1) 也可以触发 OOM，因为某些其他集合正在泄漏内存（在安全 Rust 中可能发生内存泄漏）。

内存使用

很难推断堆分配集合的内存使用情况，因为长期存在的集合的容量可能在运行时发生变化。某些操作可能会隐式地重新分配集合，从而增加其内存使用量，并且某些集合会公开诸如 shrink_to_fit 之类的方法，这些方法可能会减少集合使用的内存——最终，这取决于分配器来决定是否实际缩小内存分配。此外，分配器可能必须处理内存碎片，这会增加表面上的内存使用量。

另一方面，如果你专门使用固定容量集合，将它们中的大多数存储在 static 变量中，并为调用堆栈设置最大大小，那么链接器将检测你是否尝试使用超出物理可用内存的内存。

此外，在堆栈上分配的固定容量集合将由 -Z emit-stack-sizes 标志报告，这意味着分析堆栈使用情况的工具（如 stack-sizes）将它们包含在其分析中。

但是，固定容量集合不能缩小，这可能导致负载因子（集合的大小与其容量之间的比率）低于可重定位集合可以实现的负载因子。

最坏情况执行时间 (WCET)

如果你正在构建时间敏感的应用程序或硬实时应用程序，那么你可能会非常关心程序不同部分的最坏情况执行时间。

alloc 集合可以重新分配，因此可能会增长集合的操作的 WCET 也将包括重新分配集合所需的时间，这本身取决于集合的运行时容量。这使得很难确定例如 alloc::Vec.push 操作的 WCET，因为它取决于正在使用的分配器及其运行时容量。

另一方面，固定容量集合永远不会重新分配，因此所有操作都具有可预测的执行时间。例如，heapless::Vec.push 在恒定时间内执行。

易用性

alloc 需要设置全局分配器，而 heapless 则不需要。但是，heapless 需要你选择要实例化的每个集合的容量。

几乎所有 Rust 开发人员都熟悉 alloc API。heapless API 试图紧密模仿 alloc API，但由于其显式的错误处理，它永远不会完全相同——一些开发人员可能会觉得显式的错误处理是过度的或过于繁琐的。

嵌入式 Rust 指南