内部

深入探讨 libpas 的内部机制。

引言

本文档描述了截至 247029@main 的 libpas 工作原理，这比截至 246842@main 的 WebKit 版本稍新。Libpas 是一个快速且内存高效的内存分配工具包，能够同时支持多个堆，其设计宗旨是希望有一天它能用于 C/C++ 程序中所有 malloc/new 调用站点的全面同构堆（isoheaping）。

自 WebKit 186504@main 以来，我们一直在稳步启用 libpas 作为 WebKit 的 bmalloc 和 MetaAllocator 的替代品。迄今为止，这使得 Speedometer2 速度提升了约 2%，内存使用量改善了约 8%（在多个内存基准测试中）。其中一半的速度提升来自于替换 MetaAllocator，它曾是 JavaScriptCore 管理可执行内存的旧方式。现在，JSC 使用 libpas 的 jit_heap 来管理可执行内存。另一半的速度提升来自于替换 bmalloc 提供的所有功能——fastMalloc API、Gigacage API 和 IsoHeap<> API。所有的内存改进都来自于替换 bmalloc（MetaAllocator 本身已经相当内存高效）。

本文档结构如下。首先，我将描述 libpas 的目标；这些是使用 libpas 创建的类 malloc API 应该能够公开的快速且内存高效的功能。然后我将描述编码风格。接下来我将详细介绍设计。最后，我将讨论 libpas 的测试方式。

Libpas 的目标

Libpas 致力于实现以下目标：

• 快速。目标是在单线程代码上超越 bmalloc 的性能。Bmalloc 曾是 WebKit 已知最快的 malloc。
• 可伸缩。Libpas 旨在多核设备上良好伸缩。
• 内存高效。目标是全面超越 bmalloc 的内存使用效率。内存效率策略的一部分是始终使用首次适应分配（first-fit allocation）。
• 外部元数据。Libpas 从不将有关空闲对象的信息存储在该对象内部。元数据始终存储在其他地方。因此，使用已释放内存（use-after-free）无法破坏 libpas 对内存的理解。
• 多种堆配置。并非所有程序都需要相同的时间-内存权衡。一些 malloc 用户有非常奇特的需求，例如 JavaScriptCore 对其 ExecutableAllocator 的处理方式。目标是在一个库中同时支持各种特殊的分配器需求。
• 大量堆。Libpas 的编写旨在消除对所有权类型系统或其他编译器方法来修复使用已释放内存（use-after-frees）类型安全性的需求。这意味着我们需要为每种类型分配一个堆，并对此保持 100% 的严格性。因此，libpas 支持大量的堆。
• 类型感知。有时，malloc 决策需要知道类型的大小和对齐方式，例如在决定如何拆分和合并内存时。Libpas 旨在避免由于 malloc 对内存的“倾斜”重用而导致的类型错误。
• 通用释放。libpas 同构堆的用户在释放对象时无需知道该对象属于哪个堆。所有对象都应汇集到同一个释放函数中。此要求的一个例外是像 ExecutableAllocator 这样的情况，它需要 malloc，但不调用通用释放函数也无妨。
• 笼子（Cages）。WebKit 使用称为笼子（cages）的虚拟内存预留，在这种情况下，WebKit 分配虚拟内存，而 malloc 必须将该内存与某个堆关联起来。Libpas 支持多种类型的笼子。

Libpas 风格

Libpas 使用 C 语言编写。最终，我选择 C 语言是因为我认为该语言为极低层代码提供了更好的支持

• C++ 通常是我的最爱，因为它使代码更容易编写，但对于 libpas，我希望代码更容易阅读。在审查细微错误时，C 语言更容易阅读，因为它没有隐藏的东西。C 语言没有像析构函数调用或运算符重载之类的特性，这些特性在看似无害的代码中会导致令人惊讶的副作用。像 libpas 这样的内存管理代码需要大量阅读，所以 C 语言更好。
• C 语言以其类型转换运算符使得指针和整数之间的类型转换非常简单。在 C++ 中使用 C 风格的类型转换运算符感觉很奇怪，所以当我需要进行大量 uintptr_t 操作时，我更喜欢 C 语言。

如果你依赖 always_inline，C 语言可以让你实现 C++ 的大部分功能。以前并非如此，但现代 C 编译器会通过重复应用以下功能来对代码进行“肉磨”式优化：

• 内联任何 always_inline 调用，除非它是递归的，或者函数使用了 libpas 不使用的某些非常奇怪的特性（例如 goto pointer）。
• 将调用站点的参数值传播到使用这些值的函数中。

因此，传递一个函数指针（或函数指针结构），如果该指针指向一个 always_inline 函数且被调用者也是 always_inline，则会导致类似于模板单态化的特殊化。这适用于任何深度；编译器会一直处理直到不再有 always_inline 函数调用。编译器中这种偶然的进展使我能够在 C 语言中编写出非常好的模板代码。Libpas 通过包含函数指针的配置结构体在 C 语言中实现了模板——有时指向 always_inline 函数（当我们希望特殊化和内联时），有时指向非内联函数（当我们希望特殊化但不内联时）。此外，C 语言的模板风格允许我们拥有真正的多态函数。许多 libpas 慢速路径都很庞大，而且并不频繁执行。我们不希望这些代码针对每种配置都进行特殊化。幸运的是，这在 C 模板中运行良好——那些多态函数只需传递一个指向它们正在使用的配置的指针，并动态加载和调用该配置中的内容，几乎与特殊化代码所做的方式完全相同。这比 C++ 模板节省了大量的代码大小。

libpas 的大部分代码以面向对象风格编写。结构体用于创建按值（by-value）对象或堆分配（heap-allocated）对象。将它们视为类是有益的，但方式比较松散，因为 C 语言中有多种实现类的方式，libpas 会根据每个类的具体情况采用最佳技术。但是，堆分配对象有明确的约定：对于名为 foo 的类，我们将其结构体命名为 pas_foo；对于 foo 上的方法 bar，我们将其函数命名为 pas_foo_bar，并将其第一个参数设为 pas_foo*。创建 foo 实例的函数称为 pas_foo_create（或在重载情况下称为 pas_foo_create_blah_blah），并返回一个 pas_foo*。销毁 foo 对象的函数称为 pas_foo_destroy，并接受一个 pas_foo*。

Libpas 类通常在以下文件中实现：pas_foo.h（定义结构体和部分函数的头文件）、pas_foo_inlines.h（定义 foo 的内联函数，这些函数需要调用在 pas_foo.h 无法包含的头文件中声明的函数），以及 pas_foo.c（foo 函数的非内联实现）。

一些 libpas“类”是单例。在 libpas 中实现单例的标准方式是实际上没有结构体，只有在头文件中声明的全局变量和函数。请参阅 pas_page_malloc 或 pas_debug_heap 以获取单例示例。

并非 libpas 中的所有内容都是类。在许多非类但可以合理分组的情况下，我们通常会采用类似单例的方式。在函数无法轻易与某个类（甚至是单例）分组的情况下，我们会以函数名命名其所在的文件。这方面有很多例子，例如 pas_deallocate 或 pas_get_page_base。有时这会变得很有趣，比如 pas_get_page_base_and_kind_for_small_other_in_fast_megapage.h。

最后，libpas 甚至比 WebKit 通常更避免使用缩写。具有独特含义的函数通常有一个长名称，能够说明其作用。这样做的目的是为了在阅读代码时更容易理解算法的精妙之处。这类代码的复杂情况在任何抽象级别都应显得复杂。

Libpas 设计

Libpas 大致分为十一个领域：

1. 堆配置。这是我们告诉 libpas 如何组织堆的方式。堆配置可以控制很多方面。它们可以改变显而易见的东西，如最小对齐（minalign）和页大小，也可以改变更复杂的东西，如如何根据页找到页头部，反之亦然。
2. 大堆。这是一种基于数组、笛卡尔树和哈希表的首次适应堆。大堆具有出色的类型安全支持，可以安全地（尽管效率不高）用于小对象。
3. 元循环。Libpas 内部使用类似 malloc 的 API 来管理其状态。这些由所谓的自举堆（bootstrap heap）、实用堆（utility heap）和不朽堆（immortal heap）提供。
4. 隔离堆和 TLC（线程局部缓存）。Libpas 拥有一个超快速的简单隔离存储 Slab 分配器。它支持类型安全，并且是最常用的堆类型。
5. Bitfit 堆。这是一种基于 Slab 和位图的快速且内存高效的非类型安全堆。
6. 清道夫。Libpas 在一个清道夫线程中执行一系列周期性记账任务。这包括但不限于将内存返回给操作系统。
7. 巨页和页头部表。Libpas 有多种巧妙的技巧可以快速识别对象属于哪种类型的堆。这包括一个称为巨页的算术技巧和一些无锁哈希表。
8. 枚举器。Libpas 支持 malloc 堆枚举 API。
9. 基本配置模板，用于创建 bmalloc_heap API，该 API 用作 bmalloc 所有功能的替代品。
10. JIT 堆配置。
11. 快速路径。各种堆、TLC、巨页和页头部表通过为分配、释放和各种实用功能提供的快速路径连接在一起。

堆配置

pas_heap_config 结构体定义了 libpas 堆所有可配置的行为。这包括堆如何获取内存、哪些大小类使用隔离分配器、bitfit 分配器或大型分配器，以及许多其他方面。

堆配置以传值方式传递给旨在进行特殊化和内联的函数。为了支持这一点，定义堆配置的约定是创建一个宏（如 BMALLOC_HEAP_CONFIG），它提供一个堆配置字面表达式。因此，像 pas_get_allocation_size(ptr, BMALLOC_HEAP_CONFIG) 这样的调用将为你提供一个优化的快速路径，用于获取 bmalloc 中对象的分配大小。这之所以有效，是因为这些快速路径都是 always_inline 的。

堆配置以传指针方式传递给不打算进行特殊化的函数。为了支持这一点，所有堆配置也都有一个全局变量，如 bmalloc_heap_config，这样我们就可以执行 pas_large_heap_try_deallocate(base, &bmalloc_heap_config) 这样的操作。

堆配置最多可以有两个隔离页配置（config.small_segregated_config 和 config.medium_segregated_config）和最多三个 bitfit 页配置（config.small_bitfit_config、config.medium_bitfit_config 和 config.marge_bitfit_config）。任何页配置都可以禁用，但如果禁用了最小的配置（而不是禁用更大的配置），可能会发生奇怪的事情。页配置（pas_segregated_page_config、pas_bitfit_page_config 以及它们的通用超类型 pas_page_base_config）的使用方式与堆配置大体相同——对于特殊化和内联函数采用传值方式，对于非特殊化函数采用传指针方式。

堆和页配置还支持特殊化但非内联的函数。这些函数通过配置中额外的函数指针来支持，这些指针使用宏填充——因此在创建自己的配置（如 BMALLOC_HEAP_CONFIG 或 JIT_HEAP_CONFIG）时，你无需显式填充它们。这些宏会将它们填充为指向 never_inline 函数，这些函数会以常量形式传递配置来调用一些特殊化且内联的函数。这意味着例如：

BMALLOC_HEAP_CONFIG.specialized_local_allocator_try_allocate_small_segregated_slow(...);

是对 pas_local_allocator_try_allocate_small_segregated_slow 特殊化版本的非内联直接函数调用。而这将是对同一函数的虚调用。

pas_heap_config* config = ...;
config->specialized_local_allocator_try_allocate_small_segregated_slow(...);

请注意，在许多情况下，当您拥有一个 pas_heap_config 时，您处于专用代码中，并且堆配置在编译时是一个已知常量，因此

config.specialized_local_allocator_try_allocate_small_segregated_slow(...);

请注意，在许多情况下，当你拥有 pas_heap_config 时，你处于特殊化代码中，并且堆配置在编译时是一个已知常量，因此：

是非内联直接函数调用。

大堆

• Libpas 的大堆有多种用途：
• 一切都基于大堆进行自举。当隔离堆和 bitfit 堆分配内存时，它们都从某个大堆中进行分配。

隔离堆和 bitfit 堆的对象大小上限在数十到数百千字节。因此，对于其他堆来说过大的对象将从大堆中分配。

1. 大堆分为两部分：
2. 大空闲堆。在 libpas 的术语中，空闲堆（free heap）是指在释放时需要传入对象大小的堆，并且要求释放的对象大小与该对象分配时的大小匹配，如果未能遵守此规则，则不保证会发生什么混乱。
3. 大映射表。它将对象指针映射到大小和堆。

大堆。这是对 (1) 和 (2) 的抽象。

大空闲堆只维护一个空闲列表；它们对已分配对象一无所知。但结合大映射表，大堆提供了用户友好的释放 API：你只需提供对象指针，大映射表会处理其余部分，包括识别对象应释放到哪个空闲堆，以及传递给该空闲堆的大小。

大堆在单个全局锁（称为堆锁（heap lock））下操作。大多数 libpas 堆使用细粒度锁或完全避免锁。但对于大堆，libpas 目前只使用一个锁。

大空闲堆

大空闲堆是基于一种通用算法构建的，该算法不了解如何表示空闲列表，并且可以实例化为两种空闲列表表示之一：简单（simple）和快速（fast）。简单的大空闲堆使用合并空闲对象描述的无序数组。快速大空闲堆使用合并空闲对象描述的笛卡尔树。

空闲对象描述在 libpas 中由 pas_large_free 对象表示；为简洁起见，我们称之为大空闲（large free）。大空闲可以告诉你一块空闲内存的起始和结束位置。它们还可以判断内存是否已知为零以及空闲内存的类型偏移（type skew）是多少。大堆可用于管理某种类型的数组，该类型要么大于堆的最小对齐，要么小于对齐但不是对齐的约数。特别是当与 memalign 结合使用时，空闲堆必须跟踪未类型对齐的空闲内存。考虑一个大小为 1000 且以 16384 对齐分配的类型。memalign 的规则表明在这种情况下大小必须是 16384。假设空闲堆最初有 32768 字节的连续空闲内存，现在它将有 16384 字节，起始处有 384 字节的类型偏移。类型偏移，或 libpas 称之为 offset_in_type，是大空闲在堆类型内部起始位置的偏移量。在极其复杂的情况下，这意味着要找到某种类型和对齐方式下大空闲内部的第一个有效对象地址，需要计算偏移量的最小公倍数（参见 pas_coalign），这依赖于类型大小和对齐方式的扩展最大公约数（参见 pas_extended_gcd）的正确 Bezout 系数。

大空闲支持合并（libpas 称之为 merging）和拆分的 API。通用的大空闲堆负责搜索大空闲以找到第一个匹配特定大小和对齐方式的分配请求。它还通过搜索相邻的空闲内存，将已释放的内存合并回堆中。搜索通过一个函数指针结构体进行，该结构体可以高效实现（例如简单大空闲堆在无序数组中的 O(n) 搜索），也可以更高效地实现（例如快速大空闲堆中笛卡尔树上的 O(1) 或 O(log n) 操作）。通用算法使用 C 语言的泛型惯用法，因此在运行时没有实际的函数指针调用。

大空闲堆允许你为其提供分配和释放内存的回调函数。如果你向大空闲堆请求内存但它没有，分配回调函数将被调用。该分配回调函数可以从操作系统获取内存，也可以从其他堆获取内存。释放回调函数用于大空闲堆调用了分配回调后，决定将部分内存返还的情况。两个回调函数都是可选的（可以为 NULL），但分配回调为 NULL 而释放回调不为 NULL 的情况没有用处，因为释放回调只在有分配回调的路径上被调用。

请注意，大空闲堆不会对它们的空闲内存进行解除提交操作。大空闲堆中所有的内存解除提交都由大共享池（large sharing pool）完成，它是清道夫的一部分。

大映射表

大映射表是一个哈希表，将对象地址映射到大条目（large entries），这些条目包含对象的大小及其所属的堆。大映射表有一个相当复杂的哈希表算法，这是因为我过去曾尝试使大堆即使对于小对象也能至少保持一定效率。但在概念上，它是整个算法中一个简单的部分。向大映射表查询它不认识的对象也是合法的，在这种情况下，就像普通的哈希表一样，它只会告诉你它不认识你的对象。结合隔离堆和 bitfit 堆使用巨页表和页头部表的方式，这意味着 libpas 可以对 libpas 不管理的那些对象回退到另一个 malloc。

请注意，移除大映射表中的小对象优化可能是可以接受的。另一方面，它们是可靠的，并且已知不会增加算法的成本。拥有这种能力意味着，作为调整算法的一部分，尝试将一些小对象放入大堆以避免分配操作隔离堆或 bitfit 堆所需的数据结构，会比没有这种能力时更安全。

大堆

• 大空闲堆和大映射表通过 pas_large_heap 组合成一个高级 API。在状态方面，这仅仅是一个 pas_large_free_heap 加上一些有助于大映射表中小型对象优化数据。大堆的函数执行了许多额外的工作：
• 它们为空闲堆提供一个分配器，用于获取新内存。大堆将内存分配请求路由到堆配置的分配回调函数。
• 它们确保每个空闲堆分配都最终进入大映射表。
• 它们通过从大映射表中移除某个项，然后将其释放到空闲堆中来实现释放操作。

它们提供与清道夫的大共享池的集成，以便可以解除提交空闲内存。

大堆总是作为 pas_heap 对象的一个成员使用。将 pas_large_heap 视为永不独立存在的对象很有用；它更多是一种对 pas_heap 进行划分的方式。堆对象还包含一个隔离堆和其他一些内容。

元循环

• 我习惯于使用动态分配的对象进行编程。这让我能够构建数组、树、哈希表、查找表以及各种无锁数据结构。因此，我希望 libpas 的内部机制能够像其他任何算法一样分配对象。但是 libpas 的设计使其能够成为一个“世界底部”的 malloc——即它是 malloc 和 free 的实现，并且不能依赖除内核提供之外的任何内存分配原语。因此，libpas 使用自己的分配原语来为其自身对象分配内存，而这些对象又用于实现这些原语。其自举过程如下：
• 自举堆（bootstrap heap）是一个简单的大空闲堆。一个简单的大空闲堆需要能够精确地分配一个可变长度的大空闲数组。自举堆有一些技巧，允许它从自身分配该数组。这个技巧随后为 libpas 的内部使用提供了一个完整的 malloc 实现，尽管它相当慢，只能在堆锁下使用，并且在释放对象时需要我们知道对象的大小。所有其他简单的大空闲堆都从自举堆中分配它们的空闲列表。自举堆是 libpas 中唯一向操作系统请求内存的堆。所有其他堆要么向自举堆请求内存，要么向其他堆请求。
• 紧凑预留（compact reservation）是 libpas 用于那些假定 8 字节对齐且可以使用 24 位（3 字节）指针指向的对象的 128MB 内存。Libpas 需要管理大量的堆，这需要大量的内部元数据，而拥有紧凑指针可以降低这样做的成本。紧凑预留从自举堆中分配。
• 不朽堆（immortal heap）是一个从紧凑预留中进行碰撞分配（bump-allocate）的堆。它旨在用于不朽的小对象。
• 紧凑自举堆（compact bootstrap heap）类似于自举堆，不同之处在于它从紧凑预留中分配内存，并从自举堆而不是自身分配其空闲列表。
• 紧凑大实用空闲堆（compact large utility free heap）是一个快速大空闲堆，支持解除提交空闲内存（参见清道夫部分），并从紧凑自举堆中分配其内存。
• 实用堆（utility heap）是一个配置为尽可能简单的隔离堆（例如没有线程局部缓存），并且只能在持有堆锁时使用。它只支持达到某个大小（PAS_UTILITY_LOOKUP_SIZE_UPPER_BOUND）的对象，支持解除提交空闲内存，并从紧凑自举堆获取内存。实用堆的一个使用示例是用于实现快速大空闲堆的笛卡尔树中的节点。因此，例如，紧凑大实用空闲堆依赖于实用堆。

大实用空闲堆（large utility free heap）是一个快速大空闲堆，支持解除提交空闲内存并从自举堆分配其内存。

• 请注意这些堆如何相互拉取内存。通常，一个堆不会将内存返回给它从中获取内存的堆，除非是为了“撤销”刚刚完成的部分分配。因此，这种相互拉取内存的安排旨在实现类型安全、内存效率和优雅地支持奇怪的对齐方式。
• Libpas 使用解除提交而不是取消映射空闲内存，因为这确保了内存首次获得其类型后，我们永远不会改变内存的类型。
• 低级堆（如自举堆和紧凑自举堆）不支持解除提交。因此，如果一个支持解除提交的高级堆曾经将内存返回给低级堆，那么这些内存将永远不会被解除提交。

页分配 API 不允许我们轻松地以大于页大小的对齐方式进行分配。Libpas 通过过度分配来实现这一点（分配大小 + 对齐，然后在更大的预留中搜索第一个对齐的起始位置）。这一切都隐藏在自举堆内部；所有其他需要以某种特殊对齐方式获取内存的堆都只向其他堆（通常是自举堆）请求内存，而该堆或最终的自举堆会根据系统调用来处理这意味着什么。

元循环中缺少的一个部分是拥有一个使用线程局部缓存的快速实用堆（fast utility heap）。目前可能只有一个实用堆调用站点仅仅因为想要在实用堆中分配而获取堆锁。如果任何这样的调用站点改用快速实用堆，则有可能获得小幅加速，并且不需要锁定。目前尚不清楚这会多容易；可能需要一些糟糕的“黑客”手段才能允许使用 TLC 的代码调用另一个也使用 TLC 的堆。

隔离堆和 TLC（线程局部缓存）

• Libpas 的出色性能主要归功于隔离堆及其如何利用线程局部缓存。TLC 提供了一个全局内存缓存。在最佳情况下，此缓存可防止线程在分配和释放期间进行任何同步。即使必须进行一些同步，TLC 也使得一个线程不太可能想要获取由另一个线程持有的锁。其策略是三重的：
• TLC 拥有一个按大小类（per-size-class）的分配器，它会缓存该大小类的一部分内存。这意味着分配快速路径无需进行任何锁定或原子指令，除非其缓存耗尽。此时，它将不得不进行一些同步——在 libpas 的情况下，是细粒度锁定和一些无锁算法——以获取更多内存。每个分配器可以缓存的内存量是有限的（通常为 16KB），并且分配器在不使用内存的情况下只能保留大约一秒钟，之后内存就会被返回（参见清道夫部分）。
• TLC 有一个释放日志。释放隔离堆对象的快速路径是将其推送到释放日志中，无需任何锁定。慢速路径是遍历日志并释放所有对象。libpas 的释放日志刷新算法巧妙地避免了每个对象的锁定；在最佳情况下，它会在刷新整个日志之前获取几个锁，并在刷新完成后释放它们。

当释放日志刷新内存时，它会尝试首先将该内存专有地提供给释放它的线程，通过将空闲内存放入该线程中该大小类的局部视图缓存（local view cache）。内存只有在视图缓存满（其中包含约 1.6MB 内存）或大约一秒钟未使用（参见清道夫部分）的情况下，才会从局部视图缓存移入全局堆。

本节详细介绍了其工作原理。隔离堆（Segregated heaps）组织成隔离目录（segregated directories）。每个隔离目录都是页视图（views）的数组。每个页视图可能关联或不关联一个页（page）。一个视图可以是独占（exclusive）的（视图拥有该页本身），部分（partial）的（它是对其他人共享的页的视图），或者共享（shared）的（它表示由多个部分视图共享的页）。页有一个页边界（page boundary）（页起始地址）和一个页头部（page header）（描述页的对象，它可能实际在页内部或外部）。页维护分配位（alloc bits）来指示哪些对象是活着的。分配使用堆的查找表在 TLC 中找到正确的分配器索引（allocator index），这会产生一个局部分配器（local allocator）；该分配器通常有一个内存缓存可供分配。如果缓存不足，它首先尝试从局部视图缓存中弹出一个视图，如果失败，则使用相应目录上的查找第一个符合条件（find first eligible）算法来查找符合条件的视图。一旦分配器获得一个视图，它就会确保该视图有一个页，然后扫描分配位以在该页中创建空闲内存缓存。释放快速路径只是将对象推送到释放日志中。当日志满时，TLC 会刷新其日志，同时尝试分摊锁获取的成本。释放页中的对象意味着清除相应的分配位。一旦足够的分配位被清除，该页的视图要么最终进入视图缓存，要么目录被通知将该页标记为符合条件或空。以下章节将详细介绍这些概念。

线程局部缓存

• 每个线程有零个或一个 pas_thread_local_cache。在禁止创建 TLC 的情况下（例如当线程关闭时），Libpas 提供了不使用 TLC 进行分配和释放的慢速路径。但通常情况下，如果线程尚无 TLC，分配和释放操作会创建一个 TLC。TLC 的结构如下：
• TLC 包含一个固定大小的释放日志以及一个指示日志已满程度的索引。释放操作会将数据推送到该日志中。
• TLC 包含一个可变长度的分配器（allocators）数组，这些分配器实际上是局部分配器（local allocators）或局部视图缓存（local view caches）。分配器是可变长度的。客户端使用分配器索引访问分配器，该索引通常从分配器对应的目录中获取。
• TLC 可以被重新分配和释放，但它们总是指向一个 pas_thread_local_cache_node，这是一个不朽且紧凑的 TLC 描述符。TLC 节点是全局链表的一部分。每个 TLC 节点可能关联或不关联一个活动的 TLC。TLC 只能在持有堆锁的情况下创建或销毁，因此如果你持有堆锁，你可以遍历 TLC 节点链表以查找所有 TLC。

TLC 中分配器索引的布局由目录和 TLC 布局数据结构（pas_thread_local_cache_layout）共同控制。这是一个全局数据结构，可以告诉我们 TLC 中所有分配器的情况。在持有堆锁时，可以遍历 TLC 布局链表，查找所有有效的分配器索引，并检查这些索引处的内容。

线程局部缓存往往会变得很大，因为局部分配器和局部视图缓存都包含内联数组。局部分配器有一个位数组，指示空闲对象的位置。局部视图缓存有一个视图指针数组（最多 1.6MB / 16KB = 100 个条目，每个使用 24 位指针）。在单堆应用程序中，这些开销无关紧要——它们最终占整个进程内存占用（不仅在 WebKit 中，也包括我在守护进程中试验 libpas 时）的不到 10^-5。但当用于许多堆时，这些开销是相当大的。考虑到数千或数万个堆，TLC 占用高达 1% 的内存。因此，TLC 支持部分解除提交。那些只拥有非活动分配器的页面会被解除提交。请注意，TLC 解除提交已于 247029@main 合并到 libpas.git 仓库中，但尚未合并到 WebKit。

• TLC 释放日志刷新算法旨在实现两项性能优化：
• 它实现了对页头部访问的时间局部性。如果释放每个对象都意味着翻转页头部中的一个位，那么许多这样的操作都会导致缓存未命中，因为页头部在正常程序操作中不会被访问——它只在某些分配慢速路径和释放时被访问。但由于释放只在日志刷新期间访问页头部，并且日志刷新涉及大约 1000 个对象，因此刷新很可能会多次触及相同的页头部缓存行。

它减少了释放对象所需的平均锁获取次数。每个页使用自己的锁来保护其页头部以及页头部的 alloc_bits。但是，如果索引 i 处的对象和索引 i+1 处的对象使用相同的锁，则释放日志刷新不会进行任何锁定或解锁。页可以动态选择它们使用的锁（多亏了 page->lock_ptr），并且它们选择锁的方式使得由一个线程分配出的页倾向于共享相同的锁，因此释放日志刷新通常只在处理 1000 个对象开始时获取一个锁，并在完成 1000 个对象时释放该锁。

隔离堆

pas_segregated_heap 对象是 pas_heap 的一部分，负责隔离堆和 bitfit 堆的分配。bitfit 堆的详细信息将在后面的章节中讨论。隔离堆可以独立于 pas_heap 创建，但隔离堆几乎总是 pas_heap 的一部分（并且很容易重构 libpas，使其隔离堆始终是堆的一部分）。

隔离堆使用大小目录（size directories）来跟踪实际内存。分配和释放操作中最激动人心的部分发生在目录中。每个目录对应于某个大小类。隔离堆使得查找特定大小的目录变得容易。它们还使得遍历所有目录变得容易。此外，隔离堆使得查找特定大小的分配器索引变得容易（使用查找表，它本质上是你通过大小到目录查找表请求目录，然后向目录请求分配器索引时所得到结果的缓存）。隔离堆算法最激动人心的部分是 pas_segregated_heap_ensure_size_directory_for_size，它决定如何处理分配一个以前未遇到过的大小。该算法要么返回一个现有目录，要么创建一个新目录，甚至停用一个现有目录。它处理所有与类型大小、类型对齐以及当前 malloc 调用的对齐参数相关的问题。

• 隔离堆维护的查找表具有一些有趣的特性：
• 它们可以解除提交并重新物化。当拥有大量同构堆时，这是一种有用的空间节省。重新物化发生的原因是堆还维护着一个目录链表，该链表永远不会消失。链表中的每个目录都知道它在查找表中的表示形式。
• 它们是可选的。一些堆可以配置为具有首选大小，称为基本大小类（basic size class）。这对于同构堆非常常见，同构堆可能只分配一种大小。对于基于类型的同构堆，基本大小类就是该类型的大小。其他同构堆则根据第一次分配动态推断出首选大小。当一个堆只有基本大小类时，它将没有查找表。
• 对于较小尺寸有单独的查找表（与 small_segregated_config 无关——阈值是单独设置的），它们只是数组，其索引是大小除以堆的最小对齐（minalign）并向上取整。这些表可以在持有堆锁的情况下填充，而在访问时无需任何锁。因此，对它们的访问具有一些防竞争条件的保护措施。

对于中等大小（超出小查找表阈值的所有大小）有单独的查找表。中等表是一个排序数组，分配器对其进行二分查找。它可以在持有堆锁的情况下被修改、解除提交、重新物化或重新分配。该算法通过一系列编译器栅栏和变异计数检查来保护自身免受此影响。修改表意味着在进行更改之前进行“递增以修改”操作，并在更改完成后进行“递增以完成”操作。因此，无锁查找算法在二分查找之前和之后检查变异计数，并确保它们相同且均未表明正在进行变异。这涉及巧妙地使用依赖线程（例如 ARM64 的 eor-self 技巧）来确保变异计数读取确实发生在二分查找之前和之后。

隔离目录

• 隔离堆中内存管理的大部分操作发生在隔离目录中。有两种类型：
• 隔离大小目录，它们跟踪某个堆中属于某个大小类的视图。这些视图可以是拥有一个页的独占视图（exclusive views），也可以是拥有共享页（shared page）一部分的部分视图（partial views）。部分视图的大小范围从略低于 512 字节到可能是一个完整的页（在极少数情况下）。

隔离共享页目录，它们跟踪共享视图（shared views）。每个共享视图跟踪共享页以及哪些部分视图属于它。然而，当共享页被解除提交时，为了节省空间，共享视图会忘记哪些部分视图属于它；当有人第一次在其中分配时，它们会重新注册自己。

• 它们都依赖相同的基本状态，尽管使用方式略有不同：
• 一个无锁访问的紧凑视图指针向量。这些是 4 字节指针。之所以可能，是因为视图总是从紧凑预留中分配（它们通常在不朽堆中分配）。该向量可以被追加，但现有条目是不可变的。因此，调整大小时只是避免删除较小尺寸的向量，以便在发生竞争时它们仍然可以被访问。

一个无锁访问的位向量分段向量。有两个位向量，我们交错它们的 32 位比特字。符合条件（eligible）位向量告诉我们哪些视图可以进行分配。这对于大小目录和共享页目录的含义不同。对于大小目录，这些是具有一些空闲内存且当前没有人对其进行操作的视图。对于共享页目录，这些是尚未被部分视图完全占用的共享页。空（empty）位向量告诉我们哪些页完全空闲并可以解除提交。它从不为部分视图设置。它对于大小目录中的独占视图和共享页目录中的共享视图含义相同。

• 两个位向量都按顺序搜索：
• 符合条件的位向量采用首次适应搜索。

空的位向量采用末尾适应搜索。

• 搜索速度很快，因为目录使用 pas_versioned_field 的无锁技巧来维护两个索引：
• 一个首次符合条件索引。它总是指向第一个符合条件的位，除非某些线程已经设置了该位但尚未设置首次符合条件索引。换句话说，这可能存在一些滞后，但滞后是有限的。

一个末尾空加一索引。它总是指向最后一个空位之后的索引。如果它为零，则表示没有设置任何空位。如果它是视图的数量，则表示最后一个视图肯定为空，并且可能还有任意数量的其他空视图。

这些版本化索引在许多情况下无需任何原子指令即可读取，尽管对它们的大多数修改都需要一对 128 位比较并交换（compare-and-swap）操作。

符合条件的位向量与首次符合条件索引一起，使得查找第一个符合条件的视图的搜索速度非常快。位向量搜索本身就很快，即使是在分段向量上，因为分段向量有足够大的块。即使搜索整个位向量也相当高效，因为位向量 SIMD 的特性（即使用 32 位或 64 位或任意位宽的字来容纳那么多位）。但是，首次符合条件索引意味着大多数搜索永远不会超出该索引所指向的位置，因此当我们需要找到第一个符合条件的视图时，我们得到的是一个近似 O(1) 的行为。

空位向量为清道夫提供了类似的特性，清道夫会反向搜索以查找空视图。这里的效率源于以下事实：空页知道它们何时变空的时间戳，并且清道夫在找到一个太新近清空的页时会终止其反向搜索。

• 目录必须就如何添加视图做出一些选择。视图添加发生在堆锁下，并且必须按以下顺序进行：
• 首先，我们确保位向量在新索引处有足够的空间来容纳一个位。该算法依赖于视图向量的大小来告诉我们有多少个视图，因此位向量暂时过大是可以的。用于位向量的分段向量算法要求追加操作在堆锁下进行，但它可以与对向量的访问并发运行。它通过永不释放过小的向量脊柱来实现这一点。

然后我们将视图追加到视图向量中，可能会重新分配视图向量。重新分配会保留旧的过小向量副本，允许并发读取该向量。向量追加会存储值，执行一个 acqrel 栅栏（可能有点过度——可能只需要一个存储栅栏），然后增加大小。这确保了在准备好之前没有人能看到该视图。

目录只选择它们将创建哪种视图，然后创建该视图的空形式。因此，就在向量追加发生时，视图将报告自己尚未初始化。然而，任何线程都可以初始化一个空视图。正常的分配流程意味着请求一个视图“开始分配”。这实际上分两步发生（will_start_allocating 和 did_start_allocating）。will-start 步骤检查视图是否需要提交其内存，这将导致空的独占视图分配一个页。空的局部视图被置于局部原始（partial primordial）状态，在那里它们从某个共享视图中获取第一块内存，并准备根据需求可能获取更多该共享视图的块。但所有这些都发生在目录创建并追加视图之后。这意味着甚至可能出现一个线程创建了一个视图，但紧接着另一个线程就将其取走的情况。在这种情况下，第一个线程将循环并再次尝试，也许会找到在此期间已变得符合条件的其他视图，或者再次追加一个新的视图。

大小目录维护额外的状态，以便于页管理并加速分配。

已启用独占视图的大小目录有一个 full_alloc_bits 向量，其中设置了其页中对象可能起始的那些索引位。页使用按最小对齐（minalign）索引的位向量，并且只设置与有效对象偏移量对应的位。full_alloc_bits 向量是目录判断对象可能在页中何处的主要方式。另一种方式是使用 offset_from_page_boundary_to_first_object 和 offset_from_page_boundary_to_end_of_last_object，但算法对它们的依赖程度较低。

大小目录可以判断它们是否已被分配了分配器索引或视图缓存索引，并控制何时获取它们的策略。没有分配器索引的目录将从所有线程共享的基线分配器（baseline allocators）中进行分配。拥有分配器索引意味着该分配器索引也已存储在堆查找表的正确位置。拥有视图缓存索引意味着在目录中将符合条件的页面标记为符合条件之前，释放操作会将其放到视图缓存中。

页边界、头部和分配位

隔离堆中的“页”是一个可配置的概念。它们的大小以及头部位于何处可以通过其目录的 pas_segregated_page_config 进行配置。配置可以指示页的哪些部分可用作对象负载，并且它们可以提供用于查找页头部的回调函数。

• 页头部包含：
• 页的种类。隔离页头部是 pas_page_base 的子类型，我们支持从 pas_page_base* 到 pas_segregated_page* 的安全向下转型。拥有种类有助于实现这一点。
• 页当前是否正在用于分配。此字段仅适用于独占视图。独占页中的分配只有在某个局部分配器声明一个页时才能发生。对于共享页，此位存在于每个部分视图中。
• 页中是否在分配时也释放了对象。此字段仅适用于独占视图。当我们完成分配且该位被设置时，我们将执行原本在页未用于分配而释放对象时会执行的符合条件操作。对于共享页，此位存在于每个部分视图中。
• 页管理的对象大小。同样，这仅用于独占视图。对于共享页，每个部分视图可能具有不同的大小目录，并且大小目录指示对象大小。也可以通过询问独占视图的大小目录来获取对象大小，在这种情况下，你将得到与询问页时相同的答案。
• 指向页使用的锁的指针。页使用一种“锁舞蹈”来锁定：你加载 page->lock_ptr，锁定该锁，然后检查 page->lock_ptr 是否仍然指向你尝试锁定的那个锁。任何同时持有当前锁和另一个锁的人都可以将 page->lock_ptr 更改为另一个锁。对于共享页，lock_ptr 总是指向共享视图的所有权锁。对于独占视图，libpas 分配器会将页的锁更改为与其 TLC 关联的锁。如果 page->lock_ptr 上发生争用，则我们将锁更改回视图的所有权锁。这意味着在常见情况下，刷新释放日志会遇到一页又一页需要持有相同锁的页面——通常是 TLC 锁。这使得释放日志刷新在释放数千个对象时只需进行少量锁获取。
• 页变为空的时间戳，使用 libpas 称为纪元（epoch）的时间单位。
• 拥有该页的视图。这要么是独占视图，要么是共享句柄（shared handle），它是共享视图中为已解除提交的页而被释放的部分。注意：一个明显的改进是如果共享句柄实际上是页头部的一部分；它们之所以不是，仅仅是因为直到最近，独占页和共享页的页头部大小必须相同。
• 视图缓存索引，如果目录启用了视图缓存。这允许释放操作快速找出要使用的视图缓存。
• 分配位。
• 非空的 32 位分配位字的数量。

可选地，粒度使用计数。页配置可能指定页大小大于系统页大小，但该页被划分为系统页大小的粒度（granules）。在这种情况下，页头部将包含一个每粒度 1 字节的使用计数数组，用于计算该粒度中的对象数量。它们还跟踪粒度被解除提交时的特殊状态。medium_segregated_config 使用此功能来提供 128KB“页”的细粒度解除提交。

目前，我们有两种放置页头部的方式：要么在页的开头，即我们所说的页边界，要么在实用堆中分配的对象内部。在后一种情况下，我们使用大部分无锁的页头部表在页边界和页头部之间进行映射，反之亦然。页配置具有允许任一方法的调用。我也曾使用页配置“黑客”方式尝试其他策略，例如指定每 16MB 对齐的页块开头都包含一个页头部数组；但这些方法都不比目前两种方法中的任何一种更好。

• 页头部最重要的部分是分配位数组和 num_non_empty_words 计数器。这里是分配和释放操作发生的主要地方。算法的奥秘源于我们可以在 page->alloc_bits、full_alloc_bits（对于独占页来自大小目录，对于共享页来自部分视图）和 allocator->bits 上执行的简单位向量操作。这些操作使我们能够实现算法的大部分功能：
• 分配操作在 allocator->bits 上执行查找第一个设置位（find-first-set-bit），但效率非常高，因为分配器当前所处的64位位字（word of bits）已缓存到 allocator->current_word 中——因此分配很少搜索数组。所以，分配器只是加载当前字，执行 ctz 或 clz 类型的操作（这在现代CPU上开销极低），将结果左移页面配置的最小对齐值（minalign），并加上 allocator->page_ish（内存中对应于 current_word 中第一个位的地址）。这就是分配器的快速路径。
• 我们通过基本上设置 allocator->bits = full_alloc_bits & ~page->alloc_bits 来准备 allocator->bits。这是一个循环，因为每个 bits 都是一个位字数组，并且每个数组的大小都相同。对于一个16384大小的页面（small_segregated_config 的默认值）和minalign偏移量为4（因此minalign = 16，small_segregated_config 的默认值），这意味着1024位，或32个32位字，或128字节。编译器通常会完全展开这32个32位字的循环。没有循环相关的依赖。这个循环会出现在性能分析中，尽管我尝试过让它更快，但从未成功。

局部分配器

每个大小目录可以选择使用基线分配器或TLC局部分配器进行分配。每个大小目录可以选择是否拥有局部视图缓存。基线分配器只是全局的局部分配器，不属于任何TLC，分配时需要获取锁才能使用它们。TLC局部分配器访问时不需要任何锁定。

局部分配器可以处于以下任何模式：

• 它们完全未初始化。所有快速路径都将失败，慢速路径将通过请求TLC布局来初始化局部分配器。如果TLC解除提交导致局部分配器变为全零，则会出现此状态。
• 它们处于碰撞式分配模式。碰撞式分配发生在局部分配器决定在一个完全空的独占页面中分配时，或者用于原始部分分配。在前一种情况下，有时进行碰撞式分配能带来约1%的性能提升。在后一种情况下，使用碰撞式分配只是为了方便——慢速路径将决定部分视图应在共享页面内获得某个内存范围，并且它知道这块内存从未被使用过，因此自然而然地在该内存上设置一个碰撞范围。
• 它们处于空闲位模式。这比碰撞式模式稍微常见。在此模式下，allocator->bits 使用 full_alloc_bits & ~page->alloc_bits 计算，并包含每个空闲对象起始位置的一个位。
• 它们处于位适配（bitfit）模式。在此模式下，分配器只是将分配转发给 pas_bitfit_allocator。

局部分配器可以随时停止；这会导致它们将其所有空闲内存返回给堆。

TLC中的局部分配器无需任何传统锁定即可使用。然而，仍然存在同步，因为清理器（scavenger）被允许停止分配器。为了支持这一点，局部分配器在执行任何工作之前设置一个 in_use 位（非原子地，但受 pas_compiler_fence 保护），并在完成后清除它。清理线程将暂停拥有TLC的线程，然后在TLC暂停期间，它们可以停止任何未处于 in_use 状态的分配器。

位适配堆（Bitfit Heaps）

Libpas通常与分段堆（segregated heaps）和大型堆（large heaps）结合使用。然而，有时我们希望拥有一个比分段堆更节省空间但又不像大型堆那么慢的堆。位适配堆的风格与分段堆类似，但：

• 虽然位适配像分段堆一样，每个最小对齐（minalign）索引都有一个位，但位适配实际使用了所有的位。要在位适配中分配一个对象，该对象将使用的所有最小对齐粒度（minalign granules）对应的所有位在分配前都必须是空闲的，并且在分配后必须标记为非空闲。释放时必须清除所有的位。
• 同一个页面中可以分配任意大小的对象。例如，如果一个100字节的对象被释放，那么从释放的空间中分配两个50字节的对象是合法的（假设50是minalign的倍数）。
• 位适配目录不代表一个大小类别（size class）。一个位适配堆每个位适配页面配置有一个目录，并且每个页面配置支持大范围的大小（最大的对象比最小的大约250倍）。

位适配页面有 free_bits 和 object_end_bits。free_bits 指示每个空闲的最小对齐粒度。对于非空闲粒度，object_end_bits 为每个作为某个存活对象中最后一个粒度的粒度都有一个条目。这些位的使用方式如下：

• 要分配时，我们找到第一个已设置的空闲位，然后找到其后第一个已清除的空闲位。如果此范围足够大以进行分配，我们清除所有空闲位并设置对象结束位。如果不够大，我们继续搜索。当无法在页面中分配时，我们会执行特殊操作（见下文）。
• 要释放时，我们找到第一个已设置的对象结束位，这会给出对象大小。然后我们清除对象结束位并设置空闲位。

这种基本的分配方式通常被称为位图分配。位适配（Bitfit）是一种特殊的位图分配，它使得查找第一个有足够空间用于给定大小分配的页面变得廉价。位适配通过使用两个技巧，即使在管理大量页面时也能使分配快速：

• 位适配目录有一个位适配视图数组和一个对应的 max_free 字节数组。位适配视图是单态的，不像分段堆的多态视图。每个位适配视图要么未初始化，要么包含一个位适配页面。页面对应的 max_free 字节表示该页面中最大的空闲对象大小。因此，在最坏情况下，我们会搜索 max_free 向量以找到足够大用于我们分配的字节。
• 位适配使用大小类别来短路搜索。位适配利用分段堆来创建大小类别。分段大小目录在创建时选择是否支持分段分配或位适配分配。如果选择后者，该目录仅用作定位位适配大小类别的方式。与分段堆类似，每个局部分配器都与一个分段大小目录关联，即使它是配置为位适配的局部分配器。每个大小类别都维护目录中第一个视图/页面的索引，该视图/页面包含足够该大小类别的空闲对象。

对 max_free 的更新以及大小类别中短路索引的设置发生在页面中的分配失败时。这是设置这些索引的理想时机，因为分配失败也恰好告诉您页面中最大空闲对象的大小。

当页面中任何对象被释放时，我们都会将该页面标记为具有 PAS_BITFIT_MAX_FREE_UNPROCESSED 状态，并且不设置大小类别中的任何短路索引，我们只设置 pas_bitfit_directory 中的 first_unprocessed_free 索引。分配将从 directory->first_unprocessed_free 和 size_class->first_free 的最小值开始搜索。所有这些短路索引都使用 pas_versioned_field，就像分段目录中短路的工作方式一样。

位适配堆使用细粒度锁定，即每个视图都有自己的锁。但是，并没有尝试让不同线程避免在同一页面中分配。向位适配堆添加视图缓存之类的功能可能会使其速度大大加快。你甚至可以想象，我们不是拥有 directory->first_unprocessed_free，而是让页面中的释放操作将页面的视图放入该位适配目录的局部视图缓存中，然后我们从视图缓存中分配直到其为空。视图缓存中页面分配失败，则会告诉我们 max_free，从而允许我们在目录中将视图标记为符合条件。

清理器（The Scavenger）

Libpas通过调用 `madvise` 将内存返回给操作系统。对于试图提供强类型保证的 `malloc` 来说，这是有意义的。如果我们解映射内存，那么这块内存将来可能会被用于某种完全不相关的类型。但通过仅仅解除提交内存，我们既可以节省空闲内存页面，又可以保持类型安全。

`madvise` 系统调用——以及任何可能表示“此页面为空”的机制——的开销都足够大，以至于在页面变空时立即执行它并不合理。页面经常变空只是为了再次被填充。事实上，上次我测量时，大约一半的分配都走了碰撞式分配路径，而（除了启动时）这条路径是针对完全空的页面。因此，libpas有机制来存储页面已变空的信息，然后由一个清理线程通过 `madvise` 调用（或任何其他机制）将该内存返回给操作系统。清理线程默认配置为每100毫秒运行一次，但如果有一段时间不使用，它会自行关闭。在每次“滴答”时，它会返回所有已空闲一段时间（目前为300毫秒）的空页面。这两个阈值——周期和解除提交的目标时长——可以独立配置，并且（出于不同原因）将其中一个数字设置得比另一个数字大可能是有意义的。

本节详细描述了清理算法。这是使libpas快速且空间高效的重要组成部分。该算法中包含一些可能没有达到我预期效果的“疯狂”之处，但这些之处似乎在性能分析中并未显现。这某种程度上是该分配器在开发过程中多次调整和修改的结果。首先，我将描述延迟解除提交日志，这是我们合并madvise调用的方式。然后，我将描述页面共享池，这是一种供多个参与者报告他们拥有一些空闲页面的机制。接着，我将描述大型堆如何通过大型共享池（作为单例参与者之一）实现这一点。然后，我将描述分段目录参与者——它们对于共享页面目录和大小目录有所不同。我还会描述位适配目录参与者，它们与分段目录的“表亲”非常接近。最后，我将描述清理器执行的一些与页面共享池无关的操作，例如停止基线分配器、停止工具堆分配器、停止TLC分配器、刷新TLC解除分配日志、解除提交TLC中未使用的部分以及解除提交可消耗内存。

延迟解除提交日志

Libpas的解除提交算法会合并madvise调用——因此，如果两个相邻的页面，即使它们来自完全不相关的堆，都变空了，那么它们的解除提交将作为一次系统调用的一部分。这是通过在代码中需要解除提交内存的地方将该内存添加到延迟解除提交日志来实现的。该日志内部使用基于地址的最小堆。日志还存储了解除提交该范围所需的锁，因为解除提交算法依赖于内存的细粒度锁定，而不是全局提交锁。因此，当清理器要求页面共享池查找需要解除提交的内存时，它会提供一个延迟解除提交日志。页面共享池通常会一次性返回所有空页面，因此延迟解除提交日志可能会变得相当大。它们从引导空闲堆中分配（如果它们变得非常大，这不是最好的主意，因为引导空闲堆内存不会被解除提交——但目前这很方便，因为堆要支持解除提交，就需要与延迟解除提交日志通信，所以我们希望避免无限递归）。日志填满后，我们可以一次性解除提交日志中的所有内容。这包括将数组堆化，然后向后扫描并检测相邻范围。这就是实际调用解除提交的循环。第二个循环会解锁。

出现了两个有趣的复杂情况：

• 当页面共享池扫描内存以查找空页面时，它可能会以随机顺序到达页面，这可能与获取提交锁的任何有效顺序不同。因此，在获取第一个提交锁后，所有随后的锁获取都是 try_lock。如果任何 try_lock 失败，算法会提前返回，并且延迟解除提交日志有助于检测何时未能获取锁。
• 即使某些提交锁或堆锁被持有，Libpas 也支持调用该算法。在这种情况下，除了通过 try_lock 之外，尝试获取任何提交锁都是不合法的。延迟解除提交日志还将确保它不会重新锁定任何已持有的提交锁。

Libpas可以配置为通过madvise或mmap零填充来返回内存，这具有相似的语义效果但速度较慢。Libpas支持madvise的对称和非对称形式，尽管非对称形式更快，并且具有轻微（尽管主要是理论上的）内存使用优势。通过非对称，我的意思是您调用某种形式的madvise来解除提交内存，然后不进行任何提交操作。这在Darwin上有效且效率很高——如果您访问页面，内核将清除解除提交请求并为页面提供真实内存。内存分配器中不显式提交内存的内存使用优势在于，程序可能会分配大型数组但从不使用整个数组。将libpas配置为使用对称解除提交是可以的，但如果目标操作系统允许，非对称变体可能会更快或更高效。

页面共享池

不同类型的堆有不同的方式来发现它们拥有空页面。Libpas支持三种不同类型的堆（大型堆、分段堆和位适配堆），其中一种堆有两种不同的方式来发现空闲内存（分段共享页面目录和分段大小目录）。页面共享池是一种数据结构，可以处理任意数量的页面共享参与者，每个参与者都能够说明他们是否有空页面以及这些空页面是否足够旧以值得解除提交。

页面共享参与者需要能够回答以下查询：

• 获取最旧空闲页面的纪元。这可以是近似值；例如，只要不总是发生这种情况，参与者偶尔给出的纪元比真实最旧纪元更新也是可以的。我们称之为 use_epoch。
• 告知参与者是否认为自己符合条件，即目前是否有任何空闲页面。即使没有空闲页面，返回true也是可以的。如果有空闲页面却返回false，则是不允许的。如果返回true但没有空闲页面，则在有限次调用 take_least_recently_used 后，它必须返回false。通常，如果参与者错误地声称自己符合条件，那么该状态将在一次 take_least_recently_used 调用后清除。
• 获取最近最少使用的空页面（pas_page_sharing_participant_take_least_recently_used）。这允许返回实际上没有任何空页面。如果有空闲页面，这允许返回任意数量的页面（不一定只有一个）。页面通过延迟解除提交日志“返回”。

参与者在看到增量时也会通知页面共享池。看到增量意味着以下情况之一：

• 参与者发现了一个新的空闲页面，并且它之前认为自己没有任何空闲页面。
• 参与者发现最旧的空闲页面比之前认为的更旧。

只有当参与者知道它之前没有将自己宣传为符合条件时，才报告增量是可以的；每次找到空闲页面时报告增量也是可以的。大多数参与者会尽量避免报告增量，除非他们知道自己之前不符合条件。然而，一些参与者（分段目录和位适配目录）在报告最旧空闲页面的纪元方面很随意。这些参与者每当他们认为对最旧页面年龄的估计发生变化时，都会保守地报告一个增量。

页面共享池本身包含：

• 一个页面共享参与者指针的分段向量。每个指针都带有参与者的类型标签，这有助于池决定如何获取 use_epoch，决定参与者是否符合条件，以及从中获取空闲页面。
• 一个报告了增量的参与者位向量。
• 一个按最旧空闲内存的纪元排序的参与者最小堆。
• current_participant，只要没有增量，且当前参与者持续符合条件并持续报告相同的 `use_epoch`，页面共享池就会在执行任何其他操作之前向其请求页面。

如果当前参与者未设置或不符合条件，则获取堆锁，所有已设置增量位的参与者将根据更新的 `use_epoch` 重新插入到最小堆中。增量位可能导致最小堆中条目的移除（如果某些东西不再符合条件）。增量位可能导致之前不存在的条目的插入（如果某些东西刚刚变得符合条件）。并且条目可能被移除然后重新添加（如果 `use_epoch` 改变了）。然后，最小堆的最小值成为当前参与者，我们可以向它请求页面。

该池本身是一个类，但目前恰好是一个单例。将其保留为类可能是一个好主意，因为在尝试各种内存组织方法时，我曾有多个池的版本。总是存在物理页面共享池（单例），但我曾有过用于在线程之间移动页面的共享池，以及用于交换虚拟内存的共享池。

页面共享池暴露了从池中获取内存的API。有两种常用的变体：

• 获取设定数量的字节。页面共享池将尝试获取那么多内存，除非 `try_lock` 失败，在这种情况下，它会记录在下次调用时应该获取这额外数量的字节。
• 获取所有与某个 `max_epoch` 同龄或更旧的空闲页面。此API称为 pas_physical_page_sharing_pool_scavenge。此算法仅在完成时返回。在 `try_lock` 失败的情况下，它会重新循环，并且以一种避免自旋的方式进行。

预期的行为是，当页面共享池需要获取一批页面时，它通常会从某个参与者那里获得一系列页面——因此强调了 current_participant。然而，我可能对算法进行的各种调整已导致情况不再如此。在这种情况下，尝试找到一种重新计算 current_participant 的方法可能是有价值的，这种方法不需要持有 heap_lock。也许仅仅为页面共享池使用一个锁，而不是使用 heap_lock，就足以获得加速，在最好的情况下，这种加速将使其更容易增加清理器的频率。

页面共享池的清理API是清理器主要工作的一部分。接下来的部分将描述页面共享参与者的内部工作原理。

大型共享池

大型共享池是物理页面共享池中的一个单例参与者。它跟踪所有大型堆中哪些页面范围是空的。这样做的目的是允许大型堆有时在彼此之间拆分页面，这样就没有单个大型堆知道页面是否可以被解除提交。因此，所有大型堆以及大型工具空闲堆和紧凑型大型工具空闲堆都会在分配和解除分配内存时向大型共享池报告。

在内部，大型共享池维护一个红黑树和最小堆。该树跟踪合并的页面范围及其状态。该数据结构认为它了解所有内存，并以一个代表整个地址空间的单个节点“启动”，该节点声称已被分配和提交。当与大型共享池通信的堆获取内存时，它们会告诉共享池该内存现在是空闲的。任何空闲且已提交的范围也驻留在最小堆中，该最小堆按 `use_epoch`（内存变为空闲的时间）排序。

大型共享池只能在持有 heap_lock 时使用，但它使用一个单独的锁，即 pas_virtual_range_common_lock，用于提交和解除提交。因此，当libpas在madvise系统调用中被阻塞时，它不必持有 heap_lock，而另一个锁只在提交或解除提交大块内存时才会被获取。

大型共享池处理参与者API是很自然的

• 当最小堆非空时，大型共享池参与者表示它符合条件。
• 大型共享池参与者将最小堆的最小 `use_epoch` 报告为其 `use_epoch`（尽管可以配置为执行其他操作；这种其他操作可能不再有趣）。
• 大型共享池参与者通过从最小堆中移除最小值并将其节点的内存范围添加到延迟解除提交日志来获取最近最少使用的页面。

当某个大型堆向其报告第一块内存时，大型共享池会向物理页面共享池注册自己。

分段目录参与者

每个分段目录都是一个页面共享参与者。它们一旦拥有可能变空的页面就会注册自己。分段目录使用空闲位（empty bits）和last-empty-plus-one索引来满足页面共享池参与者API：

• 当last-empty-plus-one非零时，目录参与者表示它符合条件。
• 目录参与者报告last-empty-plus-one指向之前最后一个空页面的 `use_epoch`。请注意，在极端情况下，这意味着必须在位向量中搜索一个已设置的空闲位，因为在竞争条件下，last-empty-plus-one在设置到较低值时可能会滞后。
• 目录参与者通过从last-empty-plus-one向后搜索并获取最后一个空页面来获取最近最少使用的页面。此操作还会使用 pas_versioned_field 的无锁技巧更新last-empty-plus-one。

一旦找到空页面，基本思想是：

1. 清除空闲位。
2. 尝试获取资格；即，使页面不符合条件。我们在整个分段堆中使用“符合条件”位作为一种锁；例如，如果页面当前被某个局部分配器使用，它们将不符合条件。如果此操作失败，我们只需返回。请注意，由任何使页面不符合条件的人负责检查在他们再次使其符合条件后是否应设置空闲位。因此，清理器在清除空闲位并未能获取符合条件位后，不再设置空闲位是没关系的。这也防止了自旋，即清理器即使该页面不符合条件，仍不断尝试查看这个“据称”为空的页面。通过清除空闲位并在这种情况下不再设置它，清理器将避免此页面直到它变得符合条件。
3. 获取所有权锁以表明页面现已解除提交。
4. 获取提交锁，然后将页面放入延迟解除提交日志。
5. 使页面再次符合条件。

遗憾的是，这比那要复杂一些：

• 目录不跟踪页面；它们跟踪视图。共享页面目录拥有的页面视图，其实际资格由持有共享页面部分视图的分段大小目录中的合格位覆盖。因此，就获取资格是算法的一部分而言，共享页面目录必须为与共享视图关联的每个部分视图获取资格。
• 共享视图和独占视图都可能处于甚至没有页面的状态。因此，在查看视图的任何内容之前，有必要获取所有权锁。事实上，为了保证没有人会干扰页面，我们需要获取所有权锁并获取资格。实际的算法是同时执行这两个操作。
• 即使空闲位已设置，页面也可能实际上不为空。我们不要求当页面变得非空时清除空闲位。
• 解除提交的部分逻辑需要持有 page->lock_ptr，这可能是一个与所有权锁不同的锁。因此，算法实际上会先获取所有权锁，然后是页面锁，然后再次是所有权锁，最后是提交锁。
• 如果 `try_lock` 失败，那么我们设置符合条件位和空闲位，因为在这种情况下，我们确实希望页面共享池再次关注我们。

某些页面配置支持在其中包含多个系统页面的分段页面。在这种情况下，当任何系统页面变空时（使用粒度使用计数），空闲位会被设置，并且获取算法只会解除提交粒度而不是解除提交整个页面。

位适配目录参与者

位适配目录也使用空闲位向量，并且也支持粒度。尽管位适配目录是一段独立的代码，但它们参与页面共享池的方法与分段目录的做法完全相同。

关于页面共享池及其参与者的讨论到此结束。接下来，我将介绍清理器执行的其他一些操作。

停止基线分配器

清理器还会例行停止基线分配器。基线分配器很容易被清理器停止，因为任何持有其锁的人都可以使用它们。因此，清理器可以停止任何它想要的基线分配器。它只会停止那些一段时间未被使用的分配器（通过检查和重置脏位）。

停止工具堆分配器

清理器对工具分配器也做同样的事情。这只需要持有 heap_lock。

停止TLC分配器

TLC中的分配器也会被停止，但这需要更多的努力。当清理线程运行时，任何线程都可能正在使用其任何分配器，并且在这种情况下没有持有锁。因此，清理器使用以下算法：

• 首先，它尝试要求线程停止某些分配器。在每个分配慢路径中，分配器会检查TLC中是否有其他分配器已被清理器请求停止，如果是，则停止这些分配器。这不需要特殊的同步，因为拥有分配器的线程正在停止它。
• 如果这不起作用，清理器会暂停线程并停止所有未设置 in_use 位的分配器。in_use 位在线程对局部分配器执行任何操作时设置，并在之后清除。

停止分配器的一个小问题是，停止的分配器可能会被解除提交。这种协调的方式是，停止的分配器处于一种特殊状态，这意味着任何分配尝试都将走慢路径，该路径会获取TLC的清理锁，并可能重新提交一些页面，然后使分配器恢复正常状态。

刷新TLC解除分配日志

TLC解除分配日志可以由任何持有清理锁的线程刷新。因此，清理线程会刷新所有最近未被刷新的解除分配日志。

当一个线程刷新自己的日志时，它会持有清理锁。然而，追加操作不获取锁。为了实现这一点，当清理器刷新日志时，它会：

• 将日志中已解除分配的任何条目替换为零。实际上，解除分配日志刷新总是这样做。
• 不重置 thread_local_cache->deallocation_log_index。事实上，它除了读取该字段外什么都不做。

由于解除分配日志刷新的结构，它对从解除分配日志加载的所有内容进行空检查的开销很小。因此，当清理器完成刷新后，线程去刷新其日志时，它会看到一堆空条目，并会跳过它们。如果线程在清理器正在刷新日志时尝试向解除分配日志追加，那么这会正常工作，因为它最终会将新值存储在清理器所见之上。该对象仍留在日志中，并将在下次刷新时被解除分配。

解除提交TLC中未使用的部分

对于TLC中完全由停止的分配器组成的任何页面，清理器都可以解除提交这些页面。零值会触发局部分配器和局部视图缓存中的慢路径，然后提交页面并重新实例化分配器。这是费尽心思确保的；为了保持这个特性，您通常必须审计快速路径，查看它们访问分配器的哪些部分，并确保如果它们全部为零，分配器则走慢路径。该慢路径随后必须检查分配器是否已停止或解除提交，如果是，则获取TLC的清理锁并重新提交和重新实例化。

这项功能特别有价值，因为局部分配器和局部视图缓存的体积很大。当存在大量堆时，这在某些情况下可占用数十MB。因此，能够解除提交未使用的部分意义重大。

解除提交可消耗内存

分段堆维护查找表，这些表将“索引”（即对象大小除以堆的最小对齐值）映射到分配器索引和目录。共有三个表：

• 索引到分配器索引表。这仅适用于足够小的索引。
• 索引到目录表。这也仅适用于足够小的索引。
• 中等索引到目录元组的二分搜索数组。这适用于不够小的索引。

让这些表变得很大是有意义的。对于每个isoheap来说，拥有一个大型查找表可能也有意义。目前，它们使用一些较小的阈值。但为了不占用大量内存，我们需要能够解除提交只被无人使用的堆的查找表所使用的内存。

因此，libpas有一个名为 pas_expendable_memory 的奇怪东西，它允许我们分配不朽内存对象，如果我们不经常“触碰”它们，它们会自动解除提交。清理器会检查所有可消耗内存的状态，并解除提交那些一段时间未使用的页面。可消耗内存算法未连接为页面共享参与者，因为清理器每次执行“滴答”时确实需要检查算法维护的整个表；否则算法将无法工作。幸运的是，这种内存从来不多。所以，据我所知，这并不是一个性能问题。此外，它目前并没有节省那么多内存——但目前isoheap也使用较小尺寸的表。

关于清理器的讨论到此结束。总结来说，清理器会定期执行以下操作：

• 停止基线分配器。
• 停止工具堆分配器。
• 停止TLC分配器。
• 刷新TLC解除分配日志。
• 解除提交TLC中未使用的部分。
• 解除提交可消耗内存。
• 请求物理页面共享池进行清理。

在执行这些操作时，它会记录是否有任何东西处于值得再次运行的状态。稳定状态可能表现为所有空页面都已解除提交，而不仅仅是足够旧的页面才被解除提交。如果看起来正在达到稳定状态，清理器会先休眠一段时间，然后完全关闭。

巨页和页面头部表

Libpas为非大型堆提供了两种快速且可扩展的方法，用于根据对象的地址（例如在解除分配期间或在 `malloc_size` 等用户查询期间）来获取对象信息。

1. 巨页和巨页表。Libpas使用一个名为 pas_fast_megapage_kind 的两位枚举来描述每16MB的内存。零状态表示此地址没有快速巨页。另两种状态描述了两种不同类型的快速巨页，一种是您确切知道页面类型（小型独占分段），另一种是您必须通过查询页面头部来发现，但至少您知道它是小的（通常为16KB）。
2. 页面头部表。这是一个无锁读取的哈希表，它告诉您在哪里可以找到内存中某个页面的页面头部。对于使用页面头部的页面，我们还使用页面头部表来查明内存地址是否位于某种“页面”（分段页面或位适配页面）所拥有的内存中。

通常，小型分段和小型位适配配置使用巨页。中型分段、中型位适配和超大型位适配配置使用页面头部表。大型堆不使用任何一种，因为它们有大型映射。

枚举器

Libpas支持libmalloc枚举器API。它甚至包含相关的测试。其实现方式围绕 pas_enumerator 类展开。枚举器所需的许多数据结构都提供了支持枚举的API，这些API接受一个 pas_enumerator*。其工作原理的概念很简单：只需遍历堆——这在libpas中可以精确地完成——并报告元数据区域、可能包含对象的区域以及存活对象。但是，我们必须在遍历异进程中的堆时完成此操作，并且我们通过请求回调为我们创建的小副本查看该堆。枚举代码并不那么美观，但至少通过查找引用 pas_enumerator 的函数和文件，很容易找到大部分内容。

但是枚举的一个挑战是，它发生在远程进程在某个任意点停止时。该点必须是一个指令边界——所以CPU内存模型问题不是问题。但这意味着整个算法必须确保在任何指令边界，枚举器都能看到正确的东西。帮助枚举器在任何指令处仍能理解堆的逻辑分散在整个分配算法中。即使是大型堆使用的树和哈希表也有特殊的技巧，使其能够在任何指令边界进行枚举。

枚举器保持100%准确。任何差异——无论是报告的存活对象还是它们的大小——都会被 test_pas 标记为错误。目标应该是保持完美的枚举器准确性。这有两个原因：

1. 我尚未见到这样做会导致性能或内存回归的案例。
2. 它使得枚举器易于测试。我不知道如何测试一个设计上不准确的枚举器。如果它在设计上是准确的，那么测试对存活对象的理解与枚举器报告之间存在的任何差异都可以被标记为测试失败。如果它在设计上不准确，那么我不知道测试失败意味着什么，或者测试甚至可以断言什么。

基本配置模板

Libpas的堆配置和页面配置提供了极大的灵活性。像工具堆和 jit_heap 这样的功能利用这种灵活性来做一些奇怪的事情。然而，如果您使用libpas来创建一个普通的malloc，那么堆/页面配置中的许多可配置性就显得过多。一个“普通”的malloc是指作为一个普通API暴露的，而不是libpas内部的，并且管理不具有特殊属性（如标记为可执行且不可写入）的内存。

基本模板由 pas_heap_config_utils.h 提供。要基于此模板定义新的配置，您需要：

• 将适当的堆配置和页面配置类型添加到 pas_heap_config_kind.def、pas_segregated_page_config_kind.def 和 pas_bitfit_page_config_kind.def。即使您添加任何类型的配置，甚至是不使用模板的配置，也必须这样做。
• 创建文件 foo_heap_config.h 和 foo_heap_config.c。这些大部分是样板代码。

头文件通常如下所示：

#define ISO_MINALIGN_SHIFT ((size_t)4)
#define ISO_MINALIGN_SIZE ((size_t)1 << ISO_MINALIGN_SHIFT)

#define ISO_HEAP_CONFIG PAS_BASIC_HEAP_CONFIG( \
    iso, \
    .activate = pas_heap_config_utils_null_activate, \
    .get_type_size = pas_simple_type_as_heap_type_get_type_size, \
    .get_type_alignment = pas_simple_type_as_heap_type_get_type_alignment, \
    .dump_type = pas_simple_type_as_heap_type_dump, \
    .check_deallocation = true, \
    .small_segregated_min_align_shift = ISO_MINALIGN_SHIFT, \
    .small_segregated_sharing_shift = PAS_SMALL_SHARING_SHIFT, \
    .small_segregated_page_size = PAS_SMALL_PAGE_DEFAULT_SIZE, \
    .small_segregated_wasteage_handicap = PAS_SMALL_PAGE_HANDICAP, \
    .small_exclusive_segregated_logging_mode = pas_segregated_deallocation_size_oblivious_logging_mode, \
    .small_shared_segregated_logging_mode = pas_segregated_deallocation_no_logging_mode, \
    .small_exclusive_segregated_enable_empty_word_eligibility_optimization = false, \
    .small_shared_segregated_enable_empty_word_eligibility_optimization = false, \
    .small_segregated_use_reversed_current_word = PAS_ARM64, \
    .enable_view_cache = false, \
    .use_small_bitfit = true, \
    .small_bitfit_min_align_shift = ISO_MINALIGN_SHIFT, \
    .small_bitfit_page_size = PAS_SMALL_BITFIT_PAGE_DEFAULT_SIZE, \
    .medium_page_size = PAS_MEDIUM_PAGE_DEFAULT_SIZE, \
    .granule_size = PAS_GRANULE_DEFAULT_SIZE, \
    .use_medium_segregated = true, \
    .medium_segregated_min_align_shift = PAS_MIN_MEDIUM_ALIGN_SHIFT, \
    .medium_segregated_sharing_shift = PAS_MEDIUM_SHARING_SHIFT, \
    .medium_segregated_wasteage_handicap = PAS_MEDIUM_PAGE_HANDICAP, \
    .medium_exclusive_segregated_logging_mode = pas_segregated_deallocation_size_aware_logging_mode, \
    .medium_shared_segregated_logging_mode = pas_segregated_deallocation_no_logging_mode, \
    .use_medium_bitfit = true, \
    .medium_bitfit_min_align_shift = PAS_MIN_MEDIUM_ALIGN_SHIFT, \
    .use_marge_bitfit = true, \
    .marge_bitfit_min_align_shift = PAS_MIN_MARGE_ALIGN_SHIFT, \
    .marge_bitfit_page_size = PAS_MARGE_PAGE_DEFAULT_SIZE, \
    .pgm_enabled = false)

PAS_API extern pas_heap_config iso_heap_config;

PAS_BASIC_HEAP_CONFIG_DECLARATIONS(iso, ISO);

请注意 PAS_BASIC_HEAP_CONFIG 的使用，它创建一个配置字面量，根据您传递给 PAS_BASIC_HEAP_CONFIG 的参数，自动填充一堆堆配置、分段页面配置和位适配页面配置字段。对应的 .c 文件如下所示：

pas_heap_config iso_heap_config = ISO_HEAP_CONFIG;

PAS_BASIC_HEAP_CONFIG_DEFINITIONS(
    iso, ISO,
    .allocate_page_should_zero = false,
    .intrinsic_view_cache_capacity = pas_heap_runtime_config_zero_view_cache_capacity);

请注意，这只是配置新页面是否清零以及固有堆的视图缓存容量。固有堆是基本堆配置模板支持的四类堆之一：

• 固有堆是全局单例堆，就像用于基本类型的通用堆一样。WebKit的fastMalloc最终使用固有堆。
• 基本类型堆是用于基本无类型值的堆，但它们不是单例。您可以拥有许多基本类型堆。
• 类型化堆具有类型，且该类型具有固定大小和对齐。类型化堆允许分配该类型对象的单个实例或该类型的数组。
• 弹性堆（Flex heaps）用于具有柔性数组成员的对象。它们假装它们的类型大小和对齐都等于1，但实际上它们用于具有某个基础大小加上可变长度数组的对象。请注意，libpas不能正确管理大型堆中的弹性内存；我们需要一种大型堆的变体，它知道不能在不同大小之间重用弹性内存。

基本堆配置模板为堆的工作方式设置了一些基本默认值：

• 它使得小型分段和小型位适配页面配置将页面头部放在页面的开头，并安排这些页面从巨页中分配。
• 它使得中型分段、中型位适配和超大型位适配使用页面头部表。
• 它设置了一种从枚举器查找页面头部表等的方法。
• 它为每个分段页面配置设置了分段共享页面目录。

bmalloc_heap_config 是使用基本模板的配置示例。如果我们要将libpas放入其他malloc库中，我们可能会为该库创建一个堆配置，并且很可能会基于基本堆配置模板（尽管我们不一定非要这样做）。

JIT堆配置

JIT堆配置旨在取代MetaAllocator，作为WebKit中执行可执行内存分配的方式。它需要满足可执行内存分配的两个要求：

• 分配器不能读写它管理的内存，因为该内存可能随时具有奇怪的权限。
• 可执行分配器的客户端必须能够就地收缩分配。

大型堆轻松支持这两个要求。位适配堆轻松支持第二个要求，如果我们对所有类型的内存都使用页面头部表，而不仅仅是中型或超大型内存，则可以使其支持第一个要求。因此，JIT堆配置专注于只使用位适配和大型堆，并且即使对于小型位适配页面配置，它也强制位适配使用页面头部表。

安全考虑

概率保护malloc

概率保护malloc（Probabilistic Guard Malloc, PGM）是一种新的分配器，旨在捕获释放后使用尝试和越界访问。它的行为类似于AddressSanitizer（ASAN），但旨在将运行时开销降至最低。

分配

每次执行分配时，会在新分配的页面（或多个页面）的上方和下方添加一个额外的保护页。一个分配可能跨越多个页面。分配是随机左对齐或右对齐的，这确保了能够捕获溢出和下溢错误。

解除分配

执行解除分配时，已分配的页面将使用 `mprotect` 进行保护，以确保任何释放后使用都会触发崩溃。虚拟内存地址永不重用，因此我们绝不会遇到对象1被释放，对象2在相同地址空间上分配，然后对象1访问现在属于对象2的内存地址空间的情况。

内存使用

PGM确实增加了显著的内存开销。每次分配，无论大小，都会额外增加2个保护页（X86_64为8KB，ARM64为32KB）。此外，为用户分配的页面中可能还会剩余空闲内存。这部分内存可能不会被任何其他分配使用。

我们对虚拟内存和浪费内存设置了限制，以帮助限制内存对整个系统的影响。此分配器的虚拟内存限制为1GB。浪费的内存（即用户分配页面中未使用的内存）限制为1MB。这些总体限制应确保对系统的内存影响最小，同时有助于解决捕获释放后使用和越界访问的问题。

快速路径

前面所有讨论都是关于libpas的内部机制。但最终，客户端只想调用类似 `malloc` 和 `free` 的函数来管理内存。Libpas提供了快速路径模板，实际的堆实现会重用这些模板来提供 `malloc/free` 函数。快速路径包括：

• pas_try_allocate.h，这是isoheap的单对象分配快速路径。此函数只接受一个堆，不接受大小；它分配一个具有堆类型所需大小和对齐的对象。
• pas_try_allocate_array.h，这是isoheap的数组和对齐分配快速路径。您希望将其用于具有类型的堆，该类型具有大小和对齐，并且您希望分配该类型的数组或具有特殊对齐的该类型的实例。
• pas_try_allocate_primitive.h，这是没有类型的堆（即它们将基本类型作为其类型——该类型表示其大小和对齐都等于1）的基本对象分配快速路径。
• pas_try_allocate_intrinsic.h，这是固有堆分配快速路径。
• pas_try_reallocate.h，它提供了所有重新分配内存的分配器的变体。
• pas_deallocate.h，它提供了 free 的快速路径。
• pas_get_allocation_size.h，这是 malloc_size 的快速路径。

在处理快速路径时要记住的一点是，它们经过精心设计，使得 `malloc/free` 函数没有堆栈帧，没有被调用者保存寄存器，也不需要将 LR/FP 保存到堆栈。为了实现这一点，我们让快速路径调用一个仅内联的快速路径，如果失败，则调用一个“普通情况”（casual case）。仅内联的快速路径不进行任何非内联函数调用，因为如果这样做，我们将需要一个堆栈帧。唯一慢速调用（到普通情况）是一个尾调用。例如：

static PAS_ALWAYS_INLINE void* bmalloc_try_allocate_inline(size_t size)
{
    pas_allocation_result result;
    result = bmalloc_try_allocate_impl_inline_only(size, 1);
    if (PAS_LIKELY(result.did_succeed))
        return (void*)result.begin;
    return bmalloc_try_allocate_casual(size);
}

bmalloc_try_allocate_impl_inline_only 和 bmalloc_try_allocate_casual 函数的创建方式如下：

PAS_CREATE_TRY_ALLOCATE_INTRINSIC(
    bmalloc_try_allocate_impl,
    BMALLOC_HEAP_CONFIG,
    &bmalloc_intrinsic_runtime_config.base,
    &bmalloc_allocator_counts,
    pas_allocation_result_identity,
    &bmalloc_common_primitive_heap,
    &bmalloc_common_primitive_heap_support,
    pas_intrinsic_heap_is_designated);

所有分配快速路径都需要这种创建一系列函数（包括内联路径和非内联路径）的宏。解除分配、重新分配和其他快速路径更简单。例如，解除分配仅仅是：

static PAS_ALWAYS_INLINE void bmalloc_deallocate_inline(void* ptr)
{
    pas_deallocate(ptr, BMALLOC_HEAP_CONFIG);
}

如果您查看 pas_deallocate，您会看到巧妙之处，它确保慢路径调用是一个尾调用，类似于分配器的工作方式。然而，对于解除分配，我不需要在客户端显式地进行慢调用（像 bmalloc_try_allocate_inline 必须显式调用慢路径那样）。

至此，对libpas设计的讨论结束。

测试 Libpas

我已尝试为libpas中的每一种行为编写测试用例，达到如果 test_pas 通过，您就可以放心地将新的libpas放入WebKit（或任何其他地方）的程度。

test_pas 是一个白盒组件、回归和单元测试套件。它被允许调用任何libpas函数，甚至内部函数，有时也包括libpas仅为测试套件暴露的函数。

Libpas测试倾向于全面性，即使这会带来恼人的情况。许多测试会断言关于一个页面能容纳多少对象、对象在页面中的偏移量等详细信息。这意味着libpas中一些行为更改，即使没有错，也会触发测试套件中的错误。因此，在对libpas进行更改时，通常需要重新基于（rebase）测试。

libpas测试套件是用C++编写的，并使用其自己的测试工具，为每个测试创建子进程，因此每个测试都在一个完全原始的状态下运行。此外，测试套件可以随意使用 malloc 和 new，因为在测试套件中，libpas不替换 malloc 和 free。

最重要的libpas测试是所谓的混沌测试，它随机创建和销毁对象，并断言堆的状态仍然正常（例如没有存活对象重叠，所有存活对象都可枚举等）。

结论

Libpas是一个强大的malloc，为速度、内存效率和类型安全而设计。愿维护它的人能在这疯狂的代码库中找到乐趣！