iddqd：最难的一种不安全Rust

# iddqd，或最难的那种不安全 Rust | Oxide Computer Company 来源：https://oxide.computer/blog/iddqd-unsafe 我是 `iddqd`（https://docs.rs/iddqd）的主要作者，这是一个 Rust 库，用于实现键从值中借用的映射（以 Doom 作弊码（https://doomwiki.org/wiki/Doom_cheat_codes#All_Doom_engine_versions）命名）。在 Oxide，我们在 Omicron（https://github.com/oxidecomputer/omicron）中广泛使用它，这是我们的控制平面——运行在每个 Oxide 机箱核心（https://rfd.shared.oxide.computer/rfd/0048）的软件，为客户配置计算和存储等资源，并确保机箱长期稳定运行。`iddqd` 维护着此类大型记录的内存索引，这些记录在像这样的系统中随处可见，例如磁盘（https://github.com/oxidecomputer/omicron/blob/2e319eb3b9b9fcffb8cee71cffb9cd13397cb316/sled-agent/config-reconciler/src/internal_disks.rs#L602-L637）或 sled 库存（https://github.com/oxidecomputer/omicron/blob/2e319eb3b9b9fcffb8cee71cffb9cd13397cb316/nexus/types/src/inventory.rs#L682-L717）。因此，它必须是正确的：如果它行为异常，我们的控制平面可能会出现难以预测和诊断的故障。`iddqd` 底层包含相当多的不安全代码。最近有一些关于 Rust 重写中不安全代码数量的担忧（https://github.com/oven-sh/bun/issues/30719），所以我想写一些关于 `iddqd` 中的不安全代码以及我们如何驯服它的内容。 ## iddqd 解决了什么问题？ (https://oxide.computer/blog/iddqd-unsafe#what-problem-does-iddqd-solve) 在 Rust 的标准库映射中，键与值分开存储。假设你想存储一个以电子邮件地址为键的记录映射。使用 `std::collections::BTreeMap`（https://doc.rust-lang.org/std/collections/struct.BTreeMap.html），你可能会写类似这样的代码： ```rust // Email 通常是一个 newtype，用于验证电子邮件地址格式是否正确。 // 在此示例中，为了简单起见，我们将其别名为 String。 type Email = String; struct User { name: String, age: u8, } let mut users = BTreeMap::<Email, User>::new(); users.insert( "[email protected]".to_string(), User { name: "Alice".to_string(), age: 30 }, ); users.insert( "[email protected]".to_string(), User { name: "Bob".to_string(), age: 35 }, ); ``` 这种方法有一个我认为相当严重的缺点：键（电子邮件）不与值（记录的其余部分）存储在同一个结构体中。你会如何处理这个问题？一种方法是同时传递电子邮件和用户，例如使用 `get_key_value`（https://doc.rust-lang.org/std/collections/struct.BTreeMap.html#method.get_key_value）： ```rust fn process_user(email: &Email, user: &User) { /* ... */ } let (email, user) = users.get_key_value("[email protected]").unwrap(); process_user(email, user); ``` 作为扩展，你可以在获取时创建一个结合两者的结构体： ```rust struct UserRecord<'a> { email: &'a Email, user: &'a User, } let (email, user) = users.get_key_value("[email protected]").unwrap(); let record = UserRecord { email, user }; ``` 在实践中，当需要处理大量不同类型的记录时，这变得非常笨拙。或者，你可以将电子邮件在键和值中重复： ```rust struct User { email: Email, name: String, age: u8, } let mut users = BTreeMap::<Email, User>::new(); let email = "[email protected]".to_string(); users.insert( email.clone(), User { email, name: "Alice".to_string(), age: 30 }, ); ``` 但这存在风险：键和值中存储的电子邮件可能会不同步。 `iddqd` 提供了一个更好的替代方案。使用 `IdOrdMap`（https://docs.rs/iddqd/latest/iddqd/struct.IdOrdMap.html），你可以这样写： ```rust struct User { email: Email, name: String, age: u8, } // 你实现一个 trait，告诉 iddqd 如何从记录中提取键。 impl IdOrdItem for User { // 键类型可以从值借用！ type Key<'a> = &'a Email; fn key(&self) -> Self::Key<'_> { &self.email } // 这个宏展开为少量样板代码，用于解决 Rust 借用检查器的限制。 id_upcast!(); } // 然后，你可以插入记录： let mut users = IdOrdMap::<User>::new(); users .insert_unique(User { email: "[email protected]".to_string(), name: "Alice".to_string(), age: 30, }) .unwrap(); users .insert_unique(User { email: "[email protected]".to_string(), name: "Bob".to_string(), age: 35, }) .unwrap(); // 并通过电子邮件查找： assert_eq!(&users.get("[email protected]").unwrap().name, "Alice"); assert_eq!(users.get("[email protected]").unwrap().age, 35); ``` 在 Oxide，这已被证明是一种非常宝贵的模式：我们控制平面中的许多记录都非常大（比如数据库查找），而 `iddqd` 非常适合它们。它还带有其他几个功能，直接解决了我们在 Oxide 遇到的一些痛点。值得一提的几个功能包括： - 对从多个字段借用的复杂键提供一等支持（https://docs.rs/iddqd/latest/iddqd/#examples），无需诉诸动态分发（https://github.com/sunshowers-code/borrow-complex-key-example）等变通方法。 - 每个项具有两个（https://docs.rs/iddqd/latest/iddqd/struct.BiHashMap.html）或三个（https://docs.rs/iddqd/latest/iddqd/struct.TriHashMap.html）键的映射，每个键独立索引相同的记录，无需手动维护多个映射。 - Serde 实现将其序列化（https://docs.rs/iddqd/latest/iddqd/struct.IdOrdMap.html#impl-Serialize-for-IdOrdMap%3CT%3E）为序列而不是映射，以便非字符串键可以在 JSON 中序列化\[1\]（https://oxide.computer/blog/iddqd-unsafe#_footnotedef_1）。重要的是，这些实现会拒绝重复键。（为了向后兼容，也支持作为映射序列化（https://docs.rs/iddqd/latest/iddqd/id_ord_map/struct.IdOrdMapAsMap.html）。） 与我们的许多其他 crate 一样，`iddqd` 是为 Oxide 的需求而构建的，但对 Rust 社区也普遍有用。欢迎（https://crates.io/crates/iddqd）你在自己的项目中使用它。 ## 关于不安全 Rust (https://oxide.computer/blog/iddqd-unsafe#on-unsafe-rust) 在我继续之前，我想谈谈 `unsafe` 在一种内存安全语言中存在的意义。最大的问题是**未定义行为**（https://doc.rust-lang.org/reference/behavior-considered-undefined.html）（UB）：程序行为不可预测，因为语言或编译器所做的核心假设被违反。如果没有任何安全代码可以利用它导致 UB，则称该抽象是*sound*的，否则是*unsound*的。绝大多数 Rust 代码是安全的，这（假设安全代码使用的任何不安全代码都是 sound 的）意味着不会发生 UB。 然而，由于静态分析的基本不可判定性（参见 Rice 定理（https://en.wikipedia.org/wiki/Rice%27s_theorem）），Rust 编译器（或任何终止的算法）不可能接受所有没有 UB 的程序并拒绝所有带有 UB 的程序。因此，在编写这样的算法时，作者必须做出决定：是拒绝一些没有 UB 的程序，接受一些带有 UB 的程序，还是两者兼而有之？Rust 编译器做了前者：在安全 Rust 的上下文中，它拒绝所有带有 UB 的程序，但也拒绝一些没有 UB 的程序。（这是正确的选择！） 如果你的程序处于无人区，虽然你知道它没有 UB，但仍然被拒绝，该怎么办？为了表达这类程序，Rust 编译器提供了一个逃生舱口：`unsafe` 关键字。通过编写它，作者承担了 soundness 的责任：他们保证没有安全代码可以利用此代码导致 UB，并且编译器应该信任他们。 什么是不安全代码没有 UB 的含义？非正式地说，它必须遵循 Rust 的规则（https://cacm.acm.org/research/safe-systems-programming-in-rust/）——即编译器为安全 Rust 证明的所有规则。这些规则的一些例子包括： - 没有数据竞争。 - 不能读取未初始化或已释放的内存。 - 对同一内存区域不能有多个 `&mut` 引用的别名。 - 不可变数据不能被修改。 Rust 的规则非常难以推理！我认为它们比 C 的规则难得多，特别是关于可变别名的规则\[2\]（https://oxide.computer/blog/iddqd-unsafe#_footnotedef_2）。因此，谨慎使用不安全 Rust 通常涉及将其封装在一个安全抽象后面。 ### 不安全 Rust 需要对安全 Rust 进行推理 (https://oxide.computer/blog/iddqd-unsafe#unsafe-rust-requires-reasoning-about-safe-rust) 除最简情况外，如果不推理周围的安全 Rust，就不可能确定这样的抽象是 sound 的。在本节中，我将按难度递增的顺序讲解三个例子。 第一个例子是切片上的 `split_at_mut` 方法（https://doc.rust-lang.org/std/primitive.slice.html#method.split_at_mut）。此方法将可变切片分成两个独立的部分。`split_at_mut` 是一个安全的方法，但安全 Rust 缺乏表达这种切片分区的方式。因此，`split_at_mut` 需要不安全 Rust。其实现大致如下： ```rust fn split_at_mut(slice: &mut [T], mid: usize) -> (&mut [T], &mut [T]) { assert!(mid <= slice.len()); let ptr = slice.as_mut_ptr(); let remaining = slice.len() - mid; unsafe { ( std::slice::from_raw_parts_mut(ptr, mid), std::slice::from_raw_parts_mut(ptr.add(mid), remaining), ) } } ``` 要确保 unsafe 块的正确性，你还需要考虑周围安全代码的几个方面： - 该函数接收了一个 `&mut [T]`，而不是例如 `&[T]` - `assert!` 确保 `mid` 在边界内 - 事实 `remaining` 是 `slice.len() - mid`，而不是例如 `(slice.len() - mid) + 1` 如果这些不变量（都是安全 Rust）中的任何一个没有被满足，安全抽象就会变得 unsound。 下一个级别是，在许多情况下，你还需要分析不安全代码所在的*整个模块*。考虑这个向量类型： ```rust struct MyVec<T> { ptr: NonNull<T>, len: usize, cap: usize, } impl<T> MyVec<T> { pub fn get(&self, i: usize) -> Option<&T> { (i < self.len).then(|| unsafe { &*self.ptr.as_ptr().add(i) }) } } ``` `get` 的 soundness 依赖于**模块中的每个其他方法**（安全和不安全的）确保 `len` 是正确的并且在边界内。封装和隐私（`len` 不能从模块外部修改）在这里承担了负载。 然而，最困难的情况是不安全代码是泛型的，并且回调到用户提供的代码中。在这种情况下，基本原则（https://doc.rust-lang.org/nomicon/safe-unsafe-meaning.html）是：*安全 Rust 代码，无论多么病态或恶意编写，绝不能导致不安全代码表现出未定义行为。*换句话说，你不再享有只分析你所看到的安全代码的奢侈；你必须站在攻击者的角度，考虑每一个可以编写的安全 Rust 程序，并对*所有*它们都具有弹性。 例如，用户代码可能以导致内部表或数据结构损坏的方式行为不当。安全但错误的 Rust 可能会导致不安全代码变慢、产生不正确的结果，甚至 panic，但绝不能导致 UB！（为什么要假设最坏情况？你可能会争辩说，善意的 Rust 开发者不太可能编写对抗性代码。一个严格的规则的原因在于，防范对抗性代码意味着也防范无辜的错误；一条明确的界限使得分配防范 UB 的责任变得更容易。） 一个例子是 `ExactSizeIterator`（https://doc.rust-lang.org/std/iter/trait.ExactSizeIterator.html）trait，它有一个 `len` 方法返回迭代器的确切大小。开发者可能会倾向于在不安全 Rust 中利用这一点： ```rust pub fn collect_exact<I>(iter: I) -> MyVec<T> where I: ExactSizeIterator<Item = T>, { let n = iter.len(); let mut v = MyVec::with_capacity(n); for (i, item) in iter.enumerate() { unsafe { std::ptr::write(v.ptr.as_ptr().add(i), item); } } v.len = n; v } ``` 如果迭代器行为良好，此代码不会导致 UB。但无法保证这种行为！完全可以在安全 Rust 中编写一个损坏的 `ExactSizeIterator` 实现，返回虚假的结果： ```rust struct BadIterator { remaining: usize, } impl Iterator for BadIterator { type Item = u32; fn next(&mut self) -> Option<u32> { (self.remaining > 0).then(|| { self.remaining -= 1; 42 }) } } impl ExactSizeIterator for BadIterator { fn len(&self) -> usize { 0 // 但实际上这会产生 `self.remaining` 个项！ } } ``` `collect_exact` 在这种情况下会写入未分配的内存，因此它一般是不 sound 的\[3\]（https://oxide.computer/blog/iddqd-unsafe#_footnotedef_3）。 另一个例子是 `std::io::Read` trait（https://doc.rust-lang.org/std/io/trait.Read.html），其中安全但错误的 `Read` 实现可能返回错误的读取字节数。有关更多讨论，请参见 Rust RFC 2930（https://github.com/rust-lang/rfcs/blob/master/text/2930-read-buf.md）。 `iddqd` 正好处于这种情况下：它由泛型数据结构组成，这些结构会调用用户提供的代码，因此它工作在最困难的级别\[4\]（https://oxide.computer/blog/iddqd-unsafe#_footnotedef_4）。 ## iddqd 的工作原理 (https://oxide.computer/blog/iddqd-unsafe#how-iddqd-works) `iddqd` 的架构相当简单：它结合使用项列表（内部称为 `ItemSet`）和带有槽索引的表。例如，`IdHashMap`（https://docs.rs/iddqd/latest/iddqd/struct.IdHashMap.html）由以下部分组成： - 一个 `ItemSet`，它（类似于 `slab` crate（https://docs.rs/slab））内部具有： - 一个 `Vec<ItemSlot<T>>`，其中 `ItemSlot` 是一个有两个变体的枚举： - `Occupied(T)` - `Vacant { next: ItemIndex }`（其中 `ItemIndex` 表示 `Vec<ItemSlot<T>>` 中的整数索引） - 一个 `free_head: ItemIndex`，它指向最近释放的 `Vacant` 槽，或者是一个哨兵（在下图中标记为 `SENT`），表示没有空闲的 `Vacant` 槽可用。（`free_head` 和 `Vacant` 槽的组合形成一个*空闲链*。） - 一个基于 `ItemIndex` 的 `hashbrown::HashTable`（https://docs.rs/hashbrown/latest/hashbrown/struct.HashTable.html）（`hashbrown` 是标准库使用的高速哈希表实现） 例如，一个包含三个项的 `IdHashMap` 可能如下图所示。第一行是 `ItemIndex` 上的哈希表；第二行是 `Vec<ItemSlot<T>>`。 [iddqd diagram 01] 添加一个新项包括检查 `free_head` 以查看是否有任何 `Vacant` 槽可用。如果有，我们从该 `Vacant` 槽中读取 `next` 索引，用 `Occupied(...)` 覆盖该槽，然后将 `free_head` 设置为我们读取的 `next` 值。否则，我们在末尾推送一个新的 `Occupied` 槽。最后，更新哈希表，获取键并计算哈希，然后将新索引记录在哈希表中。 从上述状态开始：假设我们要插入一个新项 `t3`。调用 `insert(t3)` 会从空闲链中回收槽 `2`，将 `free_head` 前进到 `1`，并记录新的哈希条目： [iddqd diagram 02] 根据键删除项的过程与此相反：首先，使用从键计算的哈希查询哈希表，并从哈希表中移除找到的索引。拿到索引后，将 `ItemSlot` 替换为 `Vacant`，设置内部的 `next` 为当前的 `free_head` 值。最后，将 `free_head` 设置为刚刚替换为 `Vacant` 的索引。 从上述插入后的状态继续：调用 `remove(k0)` 会丢弃 `k0` 的哈希条目，将槽 `3` 标记为 `Vacant`，其 `next` 指向旧的 `free_head`（`1`），并将 `free_head` 更新为 `3`： [iddqd diagram 04] 这种模式推广到其他映射类型： - `IdOrdMap`（https://docs.rs/id