查看源代码 载体迁移

简介

ERTS 内存分配器以两种类型的原始内存块管理内存块。我们将这些原始内存块称为载体。单块载体只包含一个大的块，多块载体包含多个块。载体通常使用 Unix 系统上的 mmap() 创建。然而，载体是如何创建的并不重要。一个分配器实例通常管理单块和多块载体的混合。

问题

当一个载体为空时，即只包含一个大的空闲块时，它会被释放。由于多块载体可以同时包含已分配的块和空闲块，如果内存负载降低，分配器实例可能会被大量利用率低的载体所困扰。在内存使用高峰之后，预计并非所有内存都可以返回，因为仍然分配的块很可能分散在多个载体上。如果内存负载再次增加，通常可以重用这些利用率低的载体。然而，由于每个调度器线程管理自己的一组分配器实例，并且内存负载不一定与 CPU 负载相关，我们可能会遇到这样一种情况：一些分配器实例上有大量利用率低的多块载体，而我们需要在其他分配器实例上分配新的多块载体。在这种情况下，系统中对多块载体的需求可能会在系统中的实际内存需求减少的同时增加，这对最终用户来说既是不希望的，也是相当出乎意料的。

解决方案

为了防止出现这种情况，我们实现了对分配器实例之间多块载体迁移的支持。

空闲块的管理

为了能够将一个载体从一个分配器实例中移除并添加到另一个分配器实例中，我们需要能够在分配器实例之间移动对载体空闲块的引用。引用其管理的空闲块的分配器实例特定数据结构通常从多个位置引用同一个载体。例如，当使用地址顺序最佳拟合策略时，此数据结构是一个跨越分配器实例管理的所有载体的二叉搜索树。一个特定载体中的空闲块可能会被管理的潜在的每个其他载体引用，并且这种引用的数量可能很大。也就是说，从搜索树中删除这种载体的空闲块的工作量将是巨大的。解决这个问题的一种方法是不迁移包含大量空闲块的载体，但这会阻止我们迁移可能需要迁移的载体，以便解决我们最初提出的问题。

通过在每个载体中使用一个空闲块数据结构和一个分配器实例管理的载体范围数据结构，可以使移除和添加载体所需的工作量保持在最低限度。当在特定分配器类型上启用载体迁移时，我们要求使用具有这种实现的分配策略。目前，我们已经为三种不同的分配策略实现了这一点。所有这些策略都使用一个排序的载体搜索树，以便我们可以找到可以满足请求的地址最小的载体。在载体内部，我们使用另一个搜索树，该搜索树实现地址顺序首次拟合、地址顺序最佳拟合或最佳拟合。用于这些不同分配策略的缩写是 aoff、aoffcaobf 和 aoffcbf。

载体池

为了在分配器实例之间迁移载体，我们将它们通过一个载体池进行移动。为了完成载体迁移，一个调度器需要将载体移动到池中，另一个调度器需要将载体从池中取出。

池被实现为一个无锁、循环、双向链接列表。该列表包含一个哨兵，用作插入或从池中获取的起始点。池中的载体是此列表中的元素。

该列表可以由所有调度器线程同时修改。在修改过程中，允许双向链接列表变得有点“变形”。例如，沿着 next 指针到下一个元素，然后沿着 prev 指针并不总是带你回到你开始的地方。然而，以下始终成立

• 重复跟随 next 指针最终会带你到哨兵。
• 重复跟随 prev 指针最终会带你到哨兵。
• 跟随 next 或 prev 指针将带你到池中的元素，或者曾经在池中的元素。

当插入新元素时，我们仅跟随 next 指针来搜索插入元素的位置，并且我们总是从跳过遇到的第一个元素开始。当尝试获取元素时，我们做同样的事情，但改为仅跟随 prev 指针。

通过在插入和获取时朝不同的方向移动，我们尽可能避免了线程在插入和线程在获取之间发生争用。通过在开始搜索时跳过一个元素，我们尽可能保持哨兵不被修改。这很有好处，因为所有搜索操作都需要读取哨兵的内容。如果我们修改哨兵，包含哨兵的缓存行将在处理器之间不必要地来回传递。

列表中元素的 prev 和 next 字段包含指针的值、修改标记和删除标记。对这些字段的内存操作使用原子内存操作完成。当线程在字段中设置了修改标记时，除了设置标记的线程之外，任何人都不能修改该字段。如果需要设置多个修改标记，我们总是按照实际指针之后的顺序，首先从 next 字段开始，然后是 prev 字段。这保证不会发生死锁。

当从池中删除一个载体时，我们用一个线程进度值标记它，在允许修改 next 和 prev 字段之前，需要达到该线程进度值。也就是说，在我们达到此线程进度之前，我们不允许再次将该载体插入池中，并且我们不允许释放该载体。这确保了检查池的线程始终能够遍历池并到达有效元素。一旦我们达到了载体标记的线程进度值，我们就知道没有线程可能通过池引用它。

迁移

每个分配器实例都会跟踪其多块载体的当前利用率。当总利用率低于“放弃载体利用率限制”时，它会在进行释放时开始检查当前载体的利用率。如果载体的利用率也低于“放弃载体利用率限制”，则它会从其可用空闲块的数据结构中取消链接该载体，并将该载体插入池中。

由于载体已从可用空闲块的数据结构中取消链接，因此不会再在该载体中进行分配。

创建载体的分配器实例称为其所有者。所有权永远不会改变。

负责在载体中执行释放的分配器实例称为其雇主。如果载体不在池中，则雇主也可以执行分配。当从池中获取或插入载体时，雇佣关系可能会发生变化。

载体在池中时，对载体的释放始终由所有者执行。也就是说，所有池化载体都由其所有者雇用。

每个载体都有一个原子字，其中包含指向雇用分配器实例的指针和三个位标志；IN_POOL、BUSY 和 HOMECOMING。

从池中获取载体时，雇佣关系可能会发生变化，并且对载体的进一步释放将使用延迟释放功能重定向到新雇主。

当外国分配器实例将载体放弃回池中时，它也会使用延迟释放队列将其传递回其所有者。执行此操作时，它将设置 HOMECOMING 位标志以将其标记为“已入队”。所有者稍后将在载体出队时清除 HOMECOMING 位。此机制防止载体在出队之前再次入队。

当载体为空时，它将被释放。载体释放始终由分配载体的所有者完成。通过这样做，分配和释放载体的底层功能可以保持简单，并且不必担心多个线程。在 NUMA 系统中，我们也不会混合来自多个 NUMA 节点的载体。

如果池中的载体为空，它将从池中撤回并由已雇用它的所有者释放。

如果外国分配器雇用的载体变为空，它将使用延迟释放功能传递回所有者进行释放。

简而言之

• 创建载体的分配器实例拥有它。
• 空闲载体总是由其所有者解除分配。
• 所有权永远不会改变。
• 使用载体的分配器实例会占用它。
• 占用者可以将载体放弃到池中。
• 池中的载体不会被分配。
• 池中的载体总是被它们的所有者占用。
• 占用关系只能在载体从池中获取时，从所有者变为外部分配器。

搜索池

当分配器实例需要更多载体空间时，它会检查池。如果无法从池中获取任何载体，它将分配一个新的载体。无论分配器实例从哪里获取载体，它都会将载体链接到其空闲块的数据结构中。

为了保持实时特性，对池的搜索是有限的。我们只检查有限数量的载体。如果这些载体中没有一个空闲块足够大，无法满足分配请求，则搜索将失败。如果另一个线程当前正在对载体进行块解除分配工作，则池中的载体也可能处于繁忙状态（BUSY）。繁忙的载体也会被搜索跳过，因为它无法满足请求。池是无锁的，我们不希望阻塞并等待其他线程完成。

坏簇问题

在 OTP-17.4 之前，搜索算法存在一个问题，即搜索总是从池中的同一位置（哨兵）开始。这可能导致并发搜索进程之间的争用。但更糟糕的是，它可能导致“坏”状态，即搜索失败率很高，导致分配新的载体。由于利用率低，这些新的载体稍后可能会被插入到池中。如果插入池中的频率高于从池中成功获取的频率，内存最终将被耗尽。

这种“坏”状态包含一簇位于池中哨兵位置的小型和/或高度碎片化的载体。这种“坏”载体中最大的空闲块相当小，使其无法满足大多数分配请求。由于搜索总是从哨兵开始，任何遗留在池中的“坏”载体最终都会在哨兵处聚集在一起。所有搜索都必须首先跳过这簇“坏”载体才能到达“好”载体。当该簇的大小与搜索限制相同时，所有搜索基本上都会失败。

为了解决“坏簇”问题并缓解争用，搜索现在始终首先查看分配器自己的载体。也就是说，最初由分配器本身创建，后来被放弃到池中的载体。如果我们自己放弃的载体都无法满足需求，那么搜索将像以前一样继续进入池中，以寻找其他分配器创建的载体。但是，如果我们至少有一个自己放弃的载体无法满足请求，我们可以将其用作进入池的入口点。

结果是，我们倾向于使用线程本身创建的载体，这对于 NUMA 性能有好处。并且我们在搜索池时获得更多的入口点，这将缓解争用和聚集。

我们自己的池化树

为了在自己的载体中进行第一次搜索，每个分配器实例都有一个载体的pooled_tree。此树只能由分配器本身访问，并且只能包含其自己的载体。当载体被放弃并放入池中时，它也会被插入到pooled_tree中。如果载体已经被其所有者占用，则可以直接进行，或者通过延迟解除分配队列将其首先传递回所有者来进行。

当我们搜索pooled_tree并找到一个不再池中的载体时，我们会从pooled_tree中删除该载体，并将其标记为 TRAITOR，因为它现在被外部分配器占用。我们不会在pooled_tree中找到任何被其他线程标记为 BUSY 的载体。

如果pooled_tree中没有载体具有足够大的空闲块，我们会再次搜索它，以查找任何可以作为进入所有池化载体的共享列表的入口点的载体。这是为了尽可能避免从哨兵开始，从而缓解“坏聚集”问题。

此外，对计划解除分配的自有载体的搜索是作为最后一种搜索选项进行的。其想法是，重用一个利用率低的载体比复活一个即将释放回操作系统的空闲载体更好。

结果

这种放弃利用率低的载体并在对载体需求增加的分配器实例中重用它们的策略非常有效，并且完全消除了在 CPU 负载下降而内存负载没有下降时有时会出现的问题。

当使用aoffcaobf或aoff策略与gf或bf相比，由于我们在空闲块的数据结构中进行了更多的修改，我们会损失一些性能。然而，使用aoffcbf策略可以减少这种性能损失。然而，内存消耗和性能之间的权衡是不可避免的，这取决于用户来决定什么是最重要的。