InvisiCaps：Fil-C 能力模型

# InvisiCaps：Fil-C 能力模型 来源：https://fil-c.org/invisicaps Fil-C 确保 C 和 C++ 语言中所有操作的内存安全。(https://fil-c.org/gimso.html)C 内存安全最困难的部分是指针安全。Fil-C 通过针对指针的**能力模型**来实现指针安全。具体来说，每个指针动态地记录它被允许访问的内存中的对象，使用该指针访问任何不属于该对象的内存都会被动态禁止。 使用指针能力模型来实现内存安全意味着： - 禁止超出指针允许访问对象边界的访问。 - 禁止访问已被释放的对象。 - 禁止对只读数据进行写操作。 - 禁止对非数据对象进行读写，例如函数指针，或 Fil-C 运行时内部的“特殊”对象（如线程或 `jmp_buf` 的内部结构）。 - 禁止可能损坏 Fil-C 对任何指针能力理解的读写操作，导致无法有效执行上述任何规则。 除了内存安全，Fil-C 的另一个目标是狂热的兼容性。这意味着 Fil-C 的能力模型还必须允许大多数（或理想情况下所有）指针的“安全”使用；也就是说，那些广泛使用且不会导致漏洞的惯用法，除非违反了上述规则。这甚至包括支持 C 规范认为是未定义行为的指针用法。并且需要保持 `sizeof(T*)` 与你预期的一致——即在 64 位平台上为 8 字节。 本文描述了 Fil-C 的能力模式（称为 InvisiCaps，即隐形能力）如何实现所有这些目标，同时提供合理的性能和内存使用。 ## 这到底有多难？ 设计一个满足这些要求的能力模型非常困难，以至于它仍然是一个活跃的研究领域。Fil-C 已经经历了多种能力系统；InvisiCaps 只是最新的一个。要理解这一旅程的难度，让我们回顾一下之前的模型以及它们被放弃的原因： - **PLUT（Pointer Lower Upper Type，指针下限上限类型）**：这需要将指针变为 256 位（四个 64 位指针）。该模型需要预先知道每个分配的类型，并且不能有效支持联合体。PLUT 也不是线程安全的，这意味着它们在多线程程序中不是内存安全的。PLUT 不需要 GC；它们与 isoheap 分配器耦合。释放后使用不是错误（无法检测），但不能用来破坏能力。 - **SideCaps（Sidecar plus Capability，侧车加能力）**：这是一个巧妙的能力模型，解决了 PLUT 的线程安全问题。SideCaps 是一种英勇的竞态原子协议，允许仅使用 128 位原子操作对 256 位数据进行原子编码。我为 SideCaps 感到非常自豪，但它们很糟糕。它们非常慢（那时 Fil-C 比普通 C 慢 200 倍）。而且，它们需要在分配时知道类型，因此不能有效支持联合体。释放后使用不是错误（无法检测），但不能用来破坏任何 SideCaps。 - **MonoCaps（Monotonic Capabilities，单调能力）**：切换到 MonoCaps 的主要优势是不必在分配时确定对象的类型，而是随着程序使用对象而单调地揭示。这允许一定程度的联合体使用，并消除了在 malloc 调用点推断类型的需要。MonoCaps 还将 Fil-C 的性能开销降低到大约 10 倍，将指针大小减少到 128 位，解锁了对 C++ 的支持，并增加了对释放后使用进行确定性恐慌的能力，而不仅仅是防止释放后使用对能力的破坏。MonoCaps 也与 Fil 的不可思议垃圾收集器 (https://fil-c.org/fugc.html) 的引入同时发生。没有 GC 就不可能实现 MonoCaps。 InvisiCaps 相比 MonoCaps 是一个重大改进： - InvisiCaps 在 64 位系统上允许使用 64 位指针（如果 Fil-C 支持 32 位系统，也将允许 32 位指针）。 - 到目前为止，InvisiCaps 已经将性能开销降低到较差情况下大约 4 倍。InvisiCaps 还有一些我尚未探索的性能优化机会，因此它们可能会变得更快。 - InvisiCaps 允许有意义的联合体使用。内存位置的类型可以在其生命周期内改变。 InvisiCaps 在实现这些目标的同时，没有牺牲能力模型的线程安全性。 ## InvisiCaps 最像什么？ InvisiCaps 可以被认为是 SoftBound (https://dl.acm.org/doi/10.1145/1543135.1542504) 的一个实用实现且完全线程安全的变体。InvisiCaps 深受这项工作的启发。与 SoftBound 不同，InvisiCaps 不允许通过指针竞赛来逃避内存安全，并且允许使 C 和 C++ 的所有功能变得安全，包括像函数指针使用这样微妙的东西。SoftBound 和 InvisiCaps 最大的相似之处在于，它们都将能力元数据放置在程序可见的地址空间“外部”。 InvisiCaps 也可以被认为是 CHERI (https://www.cl.cam.ac.uk/research/security/ctsrd/cheri/) 的一个软件实现。与 CHERI 不同，InvisiCaps 更加兼容（指针是 64 位，而不是 128 位或 256 位），并且 InvisiCaps 对释放后使用有更确定性的处理。 ## InvisiCaps 的直觉 让我们从一个简单的直觉开始，了解 InvisiCaps 是如何工作的，而不担心指针及其能力如何在内存中存储。我们只考虑： - 一个局部变量中的指针，不在内存中。我们称之为**飞行指针**。 - 指针所指向对象的布局。 在我们的示例中，考虑一个指向对象中间某处的指针。 Fil-C 对象和飞行指针的布局 飞行指针有两个部分： - **下界指针**。这为我们提供了用于检查指针访问边界的下界。它*也*指向**紧挨着对象头部上方**的位置，对象头部包含： - **上界指针**。我们将用它来进行上界检查。它必须至少与下界指针一样大。对于完全不能访问的对象（如自由对象或特殊对象），它可以完全等于下界指针。 - **辅助字**。我们稍后会回到它！它很狡猾！ - **指针整数值**。这是指针的原始整数值，对 C 程序可见。当 C 程序推理指针的值时（使用算术、类型转换、打印指针、将指针与其他指针比较等），它只看到整数值。 我们将飞行指针的两个部分简称为**下界**和**整数值**（但请注意，Fil-C 源代码通常将整数值称为“ptr”）。 C 程序不能修改**下界**；你分配对象时会得到一个**下界**，然后从分配器返回的指针派生的任何指针都具有该**下界**。**下界**受 Fil-C 运行时信任，因为它用于边界检查（直接用于下界检查，以及间接用于依赖于**下界**指向位置**正下方**的对象头部的所有检查）。 **整数值**可以由 C 程序修改，并且完全不受 Fil-C 运行时信任。 每次内存访问都涉及一个不受信任的**整数值**（指示程序想要访问的位置）和一个受信任的**下界**（指示该特定指针可以访问哪些地址以及如何访问）。 作为一个额外功能，**下界**可以为 NULL。**下界**为 NULL 的指针无法被访问（访问总会触发错误，提示**下界**为 NULL）。 如果指针只能存在于局部变量中，而不能存储到堆上，那么这就是全部内容了！ ## 静止的 InvisiCaps 当指针存储到堆上时，我们称之为**驻留指针**。与飞行指针一样，驻留指针必须知道其**下界**和**整数值**。针对驻留指针的 InvisiCaps 实现了以下目标： - 如果你将一个指针存储到堆上，然后以整数形式加载回来，你会得到整数值。 - 如果你将一个整数存储到堆上，然后以指针形式加载回来，你会得到一个**下界**为空的指针，或者该位置上次存储的指针的**下界**。你绝不会得到一个无效或损坏的**下界**。 - 无法访问存储**下界**的位置的指针；没有任何能力在其边界内包含用于存储**下界**（或任何其他 Fil-C 元数据）的位置。*这是 InvisiCaps 的关键属性，也是使它们“隐形”的原因——C 程序只看到指针的整数值部分。* - 对指针访问进行竞态操作会导致程序加载某个有效的**下界**（只是可能不是你想要的**下界**，因此你可能会在访问时触发陷阱）。 - 原子指针访问（使用 `_Atomic`、`volatile` 或 `std::atomic`）是真正的原子且无锁的。 实现这一点的关键见解是 InvisiCaps 的归纳假设： *每个飞行指针的**下界**都指向一个对象头部的顶部，该头部的辅助字包含一种获取存储到该对象负载中的所有指针的**下界**的方法。* 没有指针的对象的辅助字只是 NULL。但如果一个对象中存储了任何指针，就会分配一个**辅助分配**，其大小与该对象的负载相同。然后辅助字指向该辅助分配。*如果我们暂时忽略原子指针，*对象中所有驻留指针的**下界**都位于辅助分配中，而**整数值**位于对象负载中。 指向另一个对象的 Fil-C 对象布局 在这个示例中，我们考虑两个对象。对象 #1 的负载中有一个驻留指针，指向对象 #2。因此，它的辅助字指向一个辅助分配，其中包含该指针的**下界**。该指针的**整数值**位于对象负载中。请注意，我们示例中的飞行指针指向对象 #1 中的驻留指针。 因此，所有非原子指针的加载和存储都会访问辅助分配（通过辅助字，它就在**下界**指向位置的正下方）和对象负载。存储可能会导致辅助分配被延迟创建。 请注意，这种方法对垃圾收集 (https://fil-c.org/fugc.html) 非常友好： - 如果辅助字未设置，那么 GC 将对象视为叶节点（从 GC 的角度来看，它没有向外的指针）。 - 如果设置了辅助字，那么 GC 只在辅助分配中查找指针。 ## 原子 InvisiCaps 但如果一个驻留指针是 `_Atomic`、`volatile`、`std::atomic`，或者使用任何其他需要原子性的类型或机制（clang 认为需要）存储，会发生什么？ Fil-C 原子指针的布局 辅助分配可以包含**下界**或**原子盒指针**。辅助分配中条目的类型由该条目的低位决定（0 表示**下界**，1 表示原子盒指针）。原子盒是 16 字节、16 字节对齐的分配，其中包含一个我们使用 128 位原子操作存储的飞行指针。或者，如果系统不支持双 CAS，我们可以对原子盒指针本身使用 64 位原子操作，并在每次原子突变发生时分配一个新的原子盒（幸运的是，X86_64 和 ARM64 都有 128 位原子操作，所以这没有必要）。 请注意，当驻留指针是原子时，负载中包含整数值的副本，纯粹是为了允许整数加载看到整数值。然而，将整数访问与指针访问进行竞态可能会导致时间旅行，但不会导致原子盒损坏——它只会是一个逻辑错误。 这种方法允许 Fil-C 在程序需要原子性时支持原子 InvisiCaps，同时在不需要原子性时使用更便宜的指针方法。 ## 其他考虑因素 辅助字仅使用其低 48 位来存储辅助分配指针；高 16 位用于标志和额外数据。这些额外数据对于非标准对象分配以及特殊对象（如函数、线程和 Fil-C 运行时提供的其他内置类型）很有用。让我们看一些例子。 ### 对齐分配 如果使用 `posix_memalign` 或类似 API 分配对象，并且请求了足够大的对齐，那么**下界**减去对象头部大小会指向对齐分配内部。因此，GC 不能简单地从**下界**减去对象头部大小来计算分配的基础地址。辅助字中的额外标志有足够的空间来编码对象对齐，这可以用来计算分配的真实基础地址。 ### 内存映射 `mmap` 和 Sys-V 共享内存需要特殊处理。GC 知道如何管理即使是这些分配，但必须特别注意它们。如果对象需要这种特殊处理，辅助字中会设置标志。 ### 函数指针 函数指针的整数值指向实际的函数入口点，而**下界**指向一个函数能力，该能力： - 上界等于**下界**，这阻止了所有数据访问。 - 设置了标志以指示该能力确实是一个函数。 - 辅助字的剩余部分用于指示真实的函数入口点，以便函数调用可以检查函数指针是否确实指向入口点。 函数指针类型转换是动态处理的（Fil-C 调用约定 (https://fil-c.org/calling_convention.html) 动态解决调用者传递的类型与被调用者期望的类型之间的不匹配）。 ### 线程 Fil-C 的内部线程抽象称为 `zthread`，被 musl 和 glibc 的 pthread 实现内部使用。由于 `zthread` 包含大量内部运行时状态，它需要特殊保护。指向 `zthread`（或任何其他内置类型）的指针具有以下结构： - **下界**指向内部 `zthread` 负载。 - 上界等于**下界**，因此无法进行数据访问。 - 辅助字中的标志指示这确实是一个 `zthread` 对象。 所有接受 `zthread` 指针的内置函数都会通过查看辅助字的标志来检查给定的指针是否真的是一个 `zthread` 指针。 ### 已释放的对象 释放对象会导致在访问已释放内存时发生确定性恐慌。这很容易实现： - 释放将指针的上界设置为等于**下界**，从而阻止所有访问。 - 在辅助字中设置一个**释放**位，这样当程序恐慌时打印的诊断消息会指示这是由于释放后使用。 ## 结论 Fil-C 使用指针的能力模型来确保内存安全。为了确保最大兼容性，Fil-C 的 **InvisiCap** 能力模型在 64 位系统上给人一种指针只是 64 位的错觉，并允许灵活地重新解释内存类型（包括违反活动成员联合规则），同时保持能力模型本身的健全性。无论程序多么邪恶，它要么得到一个内存安全的结果（所有指针访问都在指针合法拥有的能力范围内），要么得到一个 Fil-C 恐慌。 延伸阅读： - 通过示例理解 InvisiCaps (https://fil-c.org/invisicaps_by_example.html) - Fil-C 反汇编解释 (https://fil-c.org/compiler_example.html) - Fil 的不可思议的 C 编译器 (https://fil-c.org/compiler.html) - 垃圾进，内存安全出！(https://fil-c.org/gimso.html)