集群范围的电源启动/断电竞争避免算法¶

该文件记录了用于协调 CPU 和集群设置以及拆卸操作，并安全地管理硬件一致性控制的算法。

“原理”部分解释了该算法的用途及其必要性。“基本模型”使用系统的简化视图解释了一般概念。其他部分解释了正在使用的算法的实际细节。

原理¶

在包含多个 CPU 的系统中，期望具有在系统空闲时关闭各个 CPU 的能力，以降低功耗和散热。

在包含多个 CPU 集群的系统中，也期望具有关闭整个集群的能力。

关闭和打开整个集群是一项有风险的业务，因为它涉及到执行可能具有破坏性的操作，这些操作会影响一组独立运行的 CPU，而操作系统仍在继续运行。这意味着我们需要一些协调，以确保只有在真正安全的情况下才能执行关键的集群级别操作。

简单的锁定可能不足以解决此问题，因为像 Linux 自旋锁这样的机制可能依赖于当集群启动时不会立即启用的相干机制。由于启用或禁用这些机制本身可能是一个非原子操作（例如，写入一些硬件寄存器并使大型缓存无效），因此需要其他协调方法来保证集群级别的安全断电和上电。

本文档中介绍的机制描述了一种基于相干内存的协议，用于执行所需的协调。它旨在尽可能轻量级，同时提供所需的安全属性。

基本模型¶

每个集群和 CPU 都被分配一个状态，如下所示

DOWN (关闭)

COMING_UP (启动中)

UP (启动)

GOING_DOWN (关闭中)

    +---------> UP ----------+
    |                        v

COMING_UP                GOING_DOWN

    ^                        |
    +--------- DOWN <--------+

DOWN (关闭): CPU 或集群不相干，并且已断电或挂起，或者已准备好断电或挂起。
COMING_UP (启动中): CPU 或集群已承诺移动到 UP 状态。它可能正在初始化和启用相干性的过程中。
UP (启动): CPU 或集群在硬件级别处于活动状态且相干。内核不一定主动使用此状态下的 CPU。
GOING_DOWN (关闭中): CPU 或集群已承诺移动到 DOWN 状态。它可能正在拆卸和退出相干性的过程中。

在任何时间点，每个 CPU 都会分配到这些状态之一。CPU 状态在下面的“CPU 状态”部分中描述。

每个集群也分配有一个状态，但是有必要将状态值分为两个部分（“集群”状态和“入站”状态），并引入其他状态，以避免集群中不同的 CPU 同时修改状态时发生竞争。集群级别的状态在“集群状态”部分中描述。

为了帮助区分本文讨论中的 CPU 状态和集群状态，状态名称对于 CPU 状态给出 CPU_ 前缀，对于集群状态给出 CLUSTER_ 或 INBOUND_ 前缀。

CPU 状态¶

在此算法中，多核处理器中的每个单独的核心都称为“CPU”。假设 CPU 是单线程的：因此，CPU 在单个时间点只能做一件事情。

这意味着 CPU 非常适合基本模型。

该算法为系统中的每个 CPU 定义以下状态

CPU_DOWN (CPU 关闭)

CPU_COMING_UP (CPU 启动中)

CPU_UP (CPU 启动)

CPU_GOING_DOWN (CPU 关闭中)

 cluster setup and
CPU setup complete          policy decision
      +-----------> CPU_UP ------------+
      |                                v

CPU_COMING_UP                   CPU_GOING_DOWN

      ^                                |
      +----------- CPU_DOWN <----------+
 policy decision           CPU teardown complete
or hardware event

这四个状态的定义与基本模型的状态密切对应。

状态之间的转换如下所示。

触发事件（自发）意味着 CPU 可以通过仅进行本地操作来转换到下一个状态，而无需任何外部事件发生。

CPU_DOWN (CPU 关闭)

当 CPU 准备好断电时，它将达到 CPU_DOWN 状态。达到此状态后，CPU 通常会通过 WFI 指令或固件调用来自行断电或挂起。

下一个状态

CPU_COMING_UP (CPU 启动中)

条件

无

触发事件

显式的硬件上电操作，是由另一个 CPU 上的策略决策导致的；
硬件事件，例如中断。

CPU_COMING_UP (CPU 启动中)

在集群设置和相干之前，CPU 无法开始参与硬件相干。如果集群尚未准备好，则 CPU 将在 CPU_COMING_UP 状态下等待，直到集群已设置好。

下一个状态: CPU_UP (CPU 启动)
条件: CPU 的父集群必须处于 CLUSTER_UP 状态。
触发事件: 父集群过渡到 CLUSTER_UP 状态。

有关 CLUSTER_UP 状态的描述，请参阅“集群状态”部分。

CPU_UP (CPU 启动)

当 CPU 达到 CPU_UP 状态时，CPU 可以安全地开始参与本地相干。

这是通过跳转到内核的 CPU 恢复代码来完成的。

请注意，此状态的定义与基本模型定义略有不同：CPU_UP 并不意味着 CPU 已经相干，但确实意味着可以安全地恢复内核。内核处理剩余的恢复过程，因此其余步骤在竞争避免算法中不可见。

CPU 将保持此状态，直到做出明确的策略决策以关闭或挂起 CPU。

下一个状态: CPU_GOING_DOWN (CPU 关闭中)
条件: 无
触发事件: 显式策略决策

CPU_GOING_DOWN (CPU 关闭中)

在此状态下，CPU 会退出相干性，包括实现此目标所需的任何操作（例如，清理数据缓存）。

下一个状态: CPU_DOWN (CPU 关闭)
条件: 本地 CPU 拆卸完成
触发事件: （自发）

集群状态¶

集群是一组具有一些公共资源的连接的 CPU。由于集群包含多个 CPU，因此它可以同时执行多个操作。这有一些含义。特别是，一个 CPU 可以在另一个 CPU 拆卸集群时启动。

在此讨论中，“出站侧”是拆卸集群的 CPU 所看到的集群状态的视图。“入站侧”是设置 CPU 的 CPU 所看到的集群状态的视图。

为了在这种情况下实现安全的协调，重要的是，正在设置集群的 CPU 可以独立于正在拆卸集群的 CPU 来通告其状态。因此，集群状态分为两部分

“集群”状态：集群的全局状态；或者出站侧的状态

CLUSTER_DOWN (集群关闭)

CLUSTER_UP (集群启动)

CLUSTER_GOING_DOWN (集群关闭中)

“入站”状态：入站侧的集群状态。

INBOUND_NOT_COMING_UP (入站未启动)

INBOUND_COMING_UP (入站启动中)

这些状态的不同配对导致整个集群有六种可能的状态
                          CLUSTER_UP
        +==========> INBOUND_NOT_COMING_UP -------------+
        #                                               |
                                                        |
   CLUSTER_UP     <----+                                |
INBOUND_COMING_UP      |                                v

        ^             CLUSTER_GOING_DOWN       CLUSTER_GOING_DOWN
        #              INBOUND_COMING_UP <=== INBOUND_NOT_COMING_UP

  CLUSTER_DOWN         |                                |
INBOUND_COMING_UP <----+                                |
                                                        |
        ^                                               |
        +===========     CLUSTER_DOWN      <------------+
                     INBOUND_NOT_COMING_UP
转换 -----> 只能由出站 CPU 进行，并且仅涉及对“集群”状态的更改。

转换 ===##> 只能由入站 CPU 进行，并且仅涉及对“入站”状态的更改，除非出站侧没有进一步的转换可能（即，出站 CPU 已将集群置于 CLUSTER_DOWN 状态）。

竞争避免算法不提供确定集群中哪些 CPU 扮演这些角色的方法。这必须事先通过其他方式决定。有关更多说明，请参阅“最后一人和第一人选择”部分。

CLUSTER_DOWN/INBOUND_NOT_COMING_UP 是集群实际上可以断电的唯一状态。

入站和出站 CPU 的并行性通过从 CLUSTER_GOING_DOWN/INBOUND_NOT_COMING_UP（对应于基本模型中的 GOING_DOWN）到 CLUSTER_DOWN/INBOUND_COMING_UP（对应于基本模型中的 COMING_UP）的两条不同路径的存在来观察。第二条路径完全避免了集群拆卸。

CLUSTER_UP/INBOUND_COMING_UP 等效于基本模型中的 UP。到 CLUSTER_UP/INBOUND_NOT_COMING_UP 的最终转换是微不足道的，仅重置状态机以准备好下一个循环。

允许的转换的详细信息如下。

在每种情况下，下一个状态都表示为

<集群状态>/<入站状态> (<转换器>)

其中 <转换器> 是可以发生转换的一侧；入站侧或出站侧。

CLUSTER_DOWN/INBOUND_NOT_COMING_UP

下一个状态

CLUSTER_DOWN/INBOUND_COMING_UP (入站)

条件

无

触发事件

显式的硬件上电操作，是由另一个 CPU 上的策略决策导致的；
硬件事件，例如中断。

CLUSTER_DOWN/INBOUND_COMING_UP

在此状态下，入站 CPU 设置集群，包括在集群级别启用硬件相干性以及为实现此目的所需的任何其他操作（例如，缓存无效）。

此状态的目的是进行足够的集群级别设置，以使集群中的其他 CPU 能够安全地进入相干性。

下一个状态
CLUSTER_UP/INBOUND_COMING_UP (入站)

条件
集群级别设置和硬件相干性完成

触发事件
（自发）

CLUSTER_UP/INBOUND_COMING_UP

集群级别设置完成，并且为集群启用了硬件相干性。集群中的其他 CPU 可以安全地进入相干性。

这是一个瞬态状态，立即导致 CLUSTER_UP/INBOUND_NOT_COMING_UP。集群上的所有其他 CPU 都应将这两个状态视为等效状态。

下一个状态
CLUSTER_UP/INBOUND_NOT_COMING_UP (入站)

条件
无

触发事件
（自发）

CLUSTER_UP/INBOUND_NOT_COMING_UP

集群级别设置完成，并且为集群启用了硬件相干性。集群中的其他 CPU 可以安全地进入相干性。

集群将保持此状态，直到做出策略决策以关闭集群。

下一个状态
CLUSTER_GOING_DOWN/INBOUND_NOT_COMING_UP (出站)

条件
无

触发事件
关闭集群的策略决策

CLUSTER_GOING_DOWN/INBOUND_NOT_COMING_UP

出站 CPU 正在拆卸集群。选择的 CPU 必须在此状态下等待，直到集群中的所有 CPU 都处于 CPU_DOWN 状态。

当所有 CPU 都处于 CPU_DOWN 状态时，可以拆卸集群，例如通过清理数据缓存并退出集群级别相干性。

为了避免浪费不必要的拆卸操作，出站 CPU 应检查入站集群状态是否有异步转换到 INBOUND_COMING_UP。替代地，可以检查单个 CPU 是否进入 CPU_COMING_UP 或 CPU_UP。

下一个状态

CLUSTER_DOWN/INBOUND_NOT_COMING_UP (出站)

条件
集群已拆卸并准备好断电

触发事件
（自发）

CLUSTER_GOING_DOWN/INBOUND_COMING_UP (入站)

条件
无

触发事件

显式的硬件上电操作，是由另一个 CPU 上的策略决策导致的；

硬件事件，例如中断。

CLUSTER_GOING_DOWN/INBOUND_COMING_UP

集群正在（或曾经）拆卸，但是同时另一个 CPU 上线并尝试再次设置集群。

如果出站 CPU 观察到此状态，则它有两个选择

退出拆卸，将集群恢复到 CLUSTER_UP 状态；

完成拆卸集群并将集群置于 CLUSTER_DOWN 状态；入站 CPU 将从那里再次设置集群。

选择 (a) 允许通过避免在集群实际上不会断电的情况下进行不必要的拆卸和设置操作来消除一些延迟。

下一个状态

CLUSTER_UP/INBOUND_COMING_UP (出站)

条件
集群级别设置和硬件相干性完成

触发事件
（自发）

CLUSTER_DOWN/INBOUND_COMING_UP (出站)

条件
集群已拆卸并准备好断电

触发事件
（自发）

最后一人和第一人选择¶

在出站侧执行集群拆卸操作的 CPU 通常称为“最后一人”。

在入站侧执行集群设置的 CPU 通常称为“第一人”。

上面记录的竞争避免算法不提供选择应扮演这些角色的 CPU 的机制。

最后一人

关闭集群时，所有涉及的 CPU 最初都在执行 Linux，因此是相干的。因此，在 CPU 变得不相干之前，可以使用普通的自旋锁安全地选择最后一人。

第一人

由于 CPU 可能会异步响应外部唤醒事件而启动，因此需要一种动态机制来确保只有一个 CPU 尝试扮演第一人的角色并执行集群级别的初始化：任何其他 CPU 必须等待此操作完成才能继续。

集群级别初始化可能涉及诸如配置总线结构中的相干性控制之类的操作。

mcpm_head.S 中的当前实现使用单独的互斥机制来执行此仲裁。此机制在用于裸机互斥的 vlocks 中有详细记录。

功能和限制¶

实现

当前的基于 ARM 的实现分为 arch/arm/common/mcpm_head.S（低级别入站 CPU 操作）和 arch/arm/common/mcpm_entry.c（其他所有操作）

__mcpm_cpu_going_down() 指示 CPU 转换到 CPU_GOING_DOWN 状态。

__mcpm_cpu_down() 指示 CPU 转换到 CPU_DOWN 状态。

CPU 通过 mcpm_head.S 中的低级别上电代码转换到 CPU_COMING_UP，然后转换到 CPU_UP。这可能涉及 CPU 特定的设置代码，但在当前的实现中没有。

__mcpm_outbound_enter_critical() 和 __mcpm_outbound_leave_critical() 处理从 CLUSTER_UP 到 CLUSTER_GOING_DOWN 以及从那里到 CLUSTER_DOWN 或回到 CLUSTER_UP 的转换（在中止集群断电的情况下）。

由于在集群级别安全转换所需的额外的 CPU 间协调，因此这些函数比 __mcpm_cpu_*() 函数更复杂。

集群通过 mcpm_head.S 中的低级别上电代码从 CLUSTER_DOWN 转换回 CLUSTER_UP。这通常涉及特定于平台的设置代码，该代码由通过 mcpm_sync_init 注册的特定于平台的 power_up_setup 函数提供。

深层拓扑

按照当前的描述和实现，该算法不支持涉及两个以上级别的 CPU 拓扑（即，不支持集群的集群）。可以通过为其他拓扑级别复制集群级别状态，并修改中间（非最外层）集群级别的转换规则来扩展该算法。

版权声明¶

最初由 Dave Martin 为 Linaro Limited 创建和记录，并与 Nicolas Pitre 和 Achin Gupta 合作。

Linux 内核

目录

此页面