集合

最终，您将希望在程序中使用动态数据结构（也称为集合）。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 特性。

为了完整起见，并使本节尽可能自包含，我们将实现一个简单的碰撞指针分配器，并将其用作全局分配器。但是，我们强烈建议您在程序中使用来自 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 调用都可能产生内存不足条件。因此，某些操作可能隐式失败。一些 alloc 集合公开了 try_reserve 方法，这些方法允许您在增长集合时检查潜在的内存不足条件，但您需要主动使用它们。

如果您专门使用 heapless 集合，并且您没有为其他任何内容使用内存分配器，那么内存不足条件是不可能的。相反，您将不得不逐案处理集合容量不足的情况。也就是说，您将不得不处理 heapless::Vec.push 等方法返回的所有 Result。

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

内存使用情况

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

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

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

但是，固定容量集合不能缩小，这会导致比可重定位集合所能达到的更低的负载因子（集合大小与其容量之比）。

最坏情况执行时间 (WCET)

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

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

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

易用性

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

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

嵌入式 Rust 手册