요약·해설과 원문, 전문 번역을 서로 분리했습니다. API 이름, symbol, source path는 원문 표기를 사용합니다.
1. 요약·해설
원문의 핵심 논리와 kernel programming 관점의 보충 설명입니다. 아래의 전문 번역과는 별도로 작성했습니다.
2. 영어 원문 전체
번역 기준이 된 Linux v6.18.37 원문입니다. 줄 번호는 이 버전의 파일 좌표입니다.
원문 전체 펼치기
=========================================================
Cluster-wide Power-up/power-down race avoidance algorithm
=========================================================
This file documents the algorithm which is used to coordinate CPU and
cluster setup and teardown operations and to manage hardware coherency
controls safely.
The section "Rationale" explains what the algorithm is for and why it is
needed. "Basic model" explains general concepts using a simplified view
of the system. The other sections explain the actual details of the
algorithm in use.
Rationale
---------
In a system containing multiple CPUs, it is desirable to have the
ability to turn off individual CPUs when the system is idle, reducing
power consumption and thermal dissipation.
In a system containing multiple clusters of CPUs, it is also desirable
to have the ability to turn off entire clusters.
Turning entire clusters off and on is a risky business, because it
involves performing potentially destructive operations affecting a group
of independently running CPUs, while the OS continues to run. This
means that we need some coordination in order to ensure that critical
cluster-level operations are only performed when it is truly safe to do
so.
Simple locking may not be sufficient to solve this problem, because
mechanisms like Linux spinlocks may rely on coherency mechanisms which
are not immediately enabled when a cluster powers up. Since enabling or
disabling those mechanisms may itself be a non-atomic operation (such as
writing some hardware registers and invalidating large caches), other
methods of coordination are required in order to guarantee safe
power-down and power-up at the cluster level.
The mechanism presented in this document describes a coherent memory
based protocol for performing the needed coordination. It aims to be as
lightweight as possible, while providing the required safety properties.
Basic model
-----------
Each cluster and CPU is assigned a state, as follows:
- DOWN
- COMING_UP
- UP
- GOING_DOWN
::
+---------> UP ----------+
| v
COMING_UP GOING_DOWN
^ |
+--------- DOWN <--------+
DOWN:
The CPU or cluster is not coherent, and is either powered off or
suspended, or is ready to be powered off or suspended.
COMING_UP:
The CPU or cluster has committed to moving to the UP state.
It may be part way through the process of initialisation and
enabling coherency.
UP:
The CPU or cluster is active and coherent at the hardware
level. A CPU in this state is not necessarily being used
actively by the kernel.
GOING_DOWN:
The CPU or cluster has committed to moving to the DOWN
state. It may be part way through the process of teardown and
coherency exit.
Each CPU has one of these states assigned to it at any point in time.
The CPU states are described in the "CPU state" section, below.
Each cluster is also assigned a state, but it is necessary to split the
state value into two parts (the "cluster" state and "inbound" state) and
to introduce additional states in order to avoid races between different
CPUs in the cluster simultaneously modifying the state. The cluster-
level states are described in the "Cluster state" section.
To help distinguish the CPU states from cluster states in this
discussion, the state names are given a `CPU_` prefix for the CPU states,
and a `CLUSTER_` or `INBOUND_` prefix for the cluster states.
CPU state
---------
In this algorithm, each individual core in a multi-core processor is
referred to as a "CPU". CPUs are assumed to be single-threaded:
therefore, a CPU can only be doing one thing at a single point in time.
This means that CPUs fit the basic model closely.
The algorithm defines the following states for each CPU in the system:
- CPU_DOWN
- CPU_COMING_UP
- CPU_UP
- CPU_GOING_DOWN
::
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
The definitions of the four states correspond closely to the states of
the basic model.
Transitions between states occur as follows.
A trigger event (spontaneous) means that the CPU can transition to the
next state as a result of making local progress only, with no
requirement for any external event to happen.
CPU_DOWN:
A CPU reaches the CPU_DOWN state when it is ready for
power-down. On reaching this state, the CPU will typically
power itself down or suspend itself, via a WFI instruction or a
firmware call.
Next state:
CPU_COMING_UP
Conditions:
none
Trigger events:
a) an explicit hardware power-up operation, resulting
from a policy decision on another CPU;
b) a hardware event, such as an interrupt.
CPU_COMING_UP:
A CPU cannot start participating in hardware coherency until the
cluster is set up and coherent. If the cluster is not ready,
then the CPU will wait in the CPU_COMING_UP state until the
cluster has been set up.
Next state:
CPU_UP
Conditions:
The CPU's parent cluster must be in CLUSTER_UP.
Trigger events:
Transition of the parent cluster to CLUSTER_UP.
Refer to the "Cluster state" section for a description of the
CLUSTER_UP state.
CPU_UP:
When a CPU reaches the CPU_UP state, it is safe for the CPU to
start participating in local coherency.
This is done by jumping to the kernel's CPU resume code.
Note that the definition of this state is slightly different
from the basic model definition: CPU_UP does not mean that the
CPU is coherent yet, but it does mean that it is safe to resume
the kernel. The kernel handles the rest of the resume
procedure, so the remaining steps are not visible as part of the
race avoidance algorithm.
The CPU remains in this state until an explicit policy decision
is made to shut down or suspend the CPU.
Next state:
CPU_GOING_DOWN
Conditions:
none
Trigger events:
explicit policy decision
CPU_GOING_DOWN:
While in this state, the CPU exits coherency, including any
operations required to achieve this (such as cleaning data
caches).
Next state:
CPU_DOWN
Conditions:
local CPU teardown complete
Trigger events:
(spontaneous)
Cluster state
-------------
A cluster is a group of connected CPUs with some common resources.
Because a cluster contains multiple CPUs, it can be doing multiple
things at the same time. This has some implications. In particular, a
CPU can start up while another CPU is tearing the cluster down.
In this discussion, the "outbound side" is the view of the cluster state
as seen by a CPU tearing the cluster down. The "inbound side" is the
view of the cluster state as seen by a CPU setting the CPU up.
In order to enable safe coordination in such situations, it is important
that a CPU which is setting up the cluster can advertise its state
independently of the CPU which is tearing down the cluster. For this
reason, the cluster state is split into two parts:
"cluster" state: The global state of the cluster; or the state
on the outbound side:
- CLUSTER_DOWN
- CLUSTER_UP
- CLUSTER_GOING_DOWN
"inbound" state: The state of the cluster on the inbound side.
- INBOUND_NOT_COMING_UP
- INBOUND_COMING_UP
The different pairings of these states results in six possible
states for the cluster as a whole::
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
Transitions -----> can only be made by the outbound CPU, and
only involve changes to the "cluster" state.
Transitions ===##> can only be made by the inbound CPU, and only
involve changes to the "inbound" state, except where there is no
further transition possible on the outbound side (i.e., the
outbound CPU has put the cluster into the CLUSTER_DOWN state).
The race avoidance algorithm does not provide a way to determine
which exact CPUs within the cluster play these roles. This must
be decided in advance by some other means. Refer to the section
"Last man and first man selection" for more explanation.
CLUSTER_DOWN/INBOUND_NOT_COMING_UP is the only state where the
cluster can actually be powered down.
The parallelism of the inbound and outbound CPUs is observed by
the existence of two different paths from CLUSTER_GOING_DOWN/
INBOUND_NOT_COMING_UP (corresponding to GOING_DOWN in the basic
model) to CLUSTER_DOWN/INBOUND_COMING_UP (corresponding to
COMING_UP in the basic model). The second path avoids cluster
teardown completely.
CLUSTER_UP/INBOUND_COMING_UP is equivalent to UP in the basic
model. The final transition to CLUSTER_UP/INBOUND_NOT_COMING_UP
is trivial and merely resets the state machine ready for the
next cycle.
Details of the allowable transitions follow.
The next state in each case is notated
<cluster state>/<inbound state> (<transitioner>)
where the <transitioner> is the side on which the transition
can occur; either the inbound or the outbound side.
CLUSTER_DOWN/INBOUND_NOT_COMING_UP:
Next state:
CLUSTER_DOWN/INBOUND_COMING_UP (inbound)
Conditions:
none
Trigger events:
a) an explicit hardware power-up operation, resulting
from a policy decision on another CPU;
b) a hardware event, such as an interrupt.
CLUSTER_DOWN/INBOUND_COMING_UP:
In this state, an inbound CPU sets up the cluster, including
enabling of hardware coherency at the cluster level and any
other operations (such as cache invalidation) which are required
in order to achieve this.
The purpose of this state is to do sufficient cluster-level
setup to enable other CPUs in the cluster to enter coherency
safely.
Next state:
CLUSTER_UP/INBOUND_COMING_UP (inbound)
Conditions:
cluster-level setup and hardware coherency complete
Trigger events:
(spontaneous)
CLUSTER_UP/INBOUND_COMING_UP:
Cluster-level setup is complete and hardware coherency is
enabled for the cluster. Other CPUs in the cluster can safely
enter coherency.
This is a transient state, leading immediately to
CLUSTER_UP/INBOUND_NOT_COMING_UP. All other CPUs on the cluster
should consider treat these two states as equivalent.
Next state:
CLUSTER_UP/INBOUND_NOT_COMING_UP (inbound)
Conditions:
none
Trigger events:
(spontaneous)
CLUSTER_UP/INBOUND_NOT_COMING_UP:
Cluster-level setup is complete and hardware coherency is
enabled for the cluster. Other CPUs in the cluster can safely
enter coherency.
The cluster will remain in this state until a policy decision is
made to power the cluster down.
Next state:
CLUSTER_GOING_DOWN/INBOUND_NOT_COMING_UP (outbound)
Conditions:
none
Trigger events:
policy decision to power down the cluster
CLUSTER_GOING_DOWN/INBOUND_NOT_COMING_UP:
An outbound CPU is tearing the cluster down. The selected CPU
must wait in this state until all CPUs in the cluster are in the
CPU_DOWN state.
When all CPUs are in the CPU_DOWN state, the cluster can be torn
down, for example by cleaning data caches and exiting
cluster-level coherency.
To avoid wasteful unnecessary teardown operations, the outbound
should check the inbound cluster state for asynchronous
transitions to INBOUND_COMING_UP. Alternatively, individual
CPUs can be checked for entry into CPU_COMING_UP or CPU_UP.
Next states:
CLUSTER_DOWN/INBOUND_NOT_COMING_UP (outbound)
Conditions:
cluster torn down and ready to power off
Trigger events:
(spontaneous)
CLUSTER_GOING_DOWN/INBOUND_COMING_UP (inbound)
Conditions:
none
Trigger events:
a) an explicit hardware power-up operation,
resulting from a policy decision on another
CPU;
b) a hardware event, such as an interrupt.
CLUSTER_GOING_DOWN/INBOUND_COMING_UP:
The cluster is (or was) being torn down, but another CPU has
come online in the meantime and is trying to set up the cluster
again.
If the outbound CPU observes this state, it has two choices:
a) back out of teardown, restoring the cluster to the
CLUSTER_UP state;
b) finish tearing the cluster down and put the cluster
in the CLUSTER_DOWN state; the inbound CPU will
set up the cluster again from there.
Choice (a) permits the removal of some latency by avoiding
unnecessary teardown and setup operations in situations where
the cluster is not really going to be powered down.
Next states:
CLUSTER_UP/INBOUND_COMING_UP (outbound)
Conditions:
cluster-level setup and hardware
coherency complete
Trigger events:
(spontaneous)
CLUSTER_DOWN/INBOUND_COMING_UP (outbound)
Conditions:
cluster torn down and ready to power off
Trigger events:
(spontaneous)
Last man and First man selection
--------------------------------
The CPU which performs cluster tear-down operations on the outbound side
is commonly referred to as the "last man".
The CPU which performs cluster setup on the inbound side is commonly
referred to as the "first man".
The race avoidance algorithm documented above does not provide a
mechanism to choose which CPUs should play these roles.
Last man:
When shutting down the cluster, all the CPUs involved are initially
executing Linux and hence coherent. Therefore, ordinary spinlocks can
be used to select a last man safely, before the CPUs become
non-coherent.
First man:
Because CPUs may power up asynchronously in response to external wake-up
events, a dynamic mechanism is needed to make sure that only one CPU
attempts to play the first man role and do the cluster-level
initialisation: any other CPUs must wait for this to complete before
proceeding.
Cluster-level initialisation may involve actions such as configuring
coherency controls in the bus fabric.
The current implementation in mcpm_head.S uses a separate mutual exclusion
mechanism to do this arbitration. This mechanism is documented in
detail in vlocks.txt.
Features and Limitations
------------------------
Implementation:
The current ARM-based implementation is split between
arch/arm/common/mcpm_head.S (low-level inbound CPU operations) and
arch/arm/common/mcpm_entry.c (everything else):
__mcpm_cpu_going_down() signals the transition of a CPU to the
CPU_GOING_DOWN state.
__mcpm_cpu_down() signals the transition of a CPU to the CPU_DOWN
state.
A CPU transitions to CPU_COMING_UP and then to CPU_UP via the
low-level power-up code in mcpm_head.S. This could
involve CPU-specific setup code, but in the current
implementation it does not.
__mcpm_outbound_enter_critical() and __mcpm_outbound_leave_critical()
handle transitions from CLUSTER_UP to CLUSTER_GOING_DOWN
and from there to CLUSTER_DOWN or back to CLUSTER_UP (in
the case of an aborted cluster power-down).
These functions are more complex than the __mcpm_cpu_*()
functions due to the extra inter-CPU coordination which
is needed for safe transitions at the cluster level.
A cluster transitions from CLUSTER_DOWN back to CLUSTER_UP via
the low-level power-up code in mcpm_head.S. This
typically involves platform-specific setup code,
provided by the platform-specific power_up_setup
function registered via mcpm_sync_init.
Deep topologies:
As currently described and implemented, the algorithm does not
support CPU topologies involving more than two levels (i.e.,
clusters of clusters are not supported). The algorithm could be
extended by replicating the cluster-level states for the
additional topological levels, and modifying the transition
rules for the intermediate (non-outermost) cluster levels.
Colophon
--------
Originally created and documented by Dave Martin for Linaro Limited, in
collaboration with Nicolas Pitre and Achin Gupta.
Copyright (C) 2012-2013 Linaro Limited
Distributed under the terms of Version 2 of the GNU General Public
License, as defined in linux/COPYING.
3. 한국어 전문 번역
영어 원문의 문단 순서와 의미를 유지한 전체 번역입니다. 코드, 함수명, symbol과 URL은 원문 표기를 유지합니다.
Cluster-wide Power-up/power-down race avoidance algorithm
1-14이 문서는 CPU와 cluster의 setup·teardown을 조정하고 hardware coherency control을 안전하게 관리하는 algorithm을 설명합니다.
`Rationale`은 algorithm의 목적과 필요성을, `Basic model`은 단순화한 system view로 일반 개념을 설명합니다. 나머지 절에서는 실제 사용하는 algorithm의 세부 동작을 다룹니다.
Rationale
15-44CPU가 여러 개인 system에서는 idle일 때 개별 CPU를 꺼 power consumption과 thermal dissipation을 줄이는 기능이 바람직합니다. CPU cluster가 여러 개인 system이라면 cluster 전체를 끌 수 있는 기능도 필요합니다.
cluster 전체를 켜고 끄는 일은 독립적으로 실행 중인 CPU group에 영향을 주는 잠재적으로 파괴적인 작업을 OS 실행 중 수행하므로 위험합니다. 따라서 critical cluster-level operation은 실제로 안전할 때만 실행되도록 조정해야 합니다.
단순 lock만으로는 충분하지 않을 수 있습니다. Linux spinlock 같은 mechanism은 cluster power-up 직후 아직 켜지지 않은 coherency mechanism에 의존할 수 있기 때문입니다. hardware register 쓰기와 대형 cache invalidate처럼 coherency를 켜거나 끄는 작업 자체도 atomic하지 않을 수 있으므로 cluster-level power-down과 power-up의 안전을 보장할 다른 조정 방식이 필요합니다.
여기서 제시하는 방식은 coherent memory 기반 protocol로 필요한 조정을 수행합니다. 요구되는 safety property를 제공하면서 가능한 한 가볍게 동작하는 것이 목표입니다.
Basic model
45-99각 cluster와 CPU에는 `DOWN`, `COMING_UP`, `UP`, `GOING_DOWN` 중 하나의 state가 지정됩니다.
+---------> UP ----------+
| v
COMING_UP GOING_DOWN
^ |
+--------- DOWN <--------+setup과 teardown이 한 방향으로 진행되는 네 상태 순환입니다.
| state | 정의 |
|---|---|
| DOWN | CPU 또는 cluster가 coherent하지 않으며 power off/suspend 상태이거나 그렇게 전환할 준비가 끝난 상태입니다. |
| COMING_UP | UP으로 전환하기로 확정했으며 initialization과 coherency enable 과정의 중간일 수 있습니다. |
| UP | hardware level에서 active하고 coherent합니다. 이 state의 CPU를 kernel이 반드시 활발히 사용하는 것은 아닙니다. |
| GOING_DOWN | DOWN으로 전환하기로 확정했으며 teardown과 coherency exit 과정의 중간일 수 있습니다. |
각 CPU는 언제나 이 네 state 중 하나를 가지며 자세한 내용은 `CPU state` 절에서 설명합니다.
cluster에도 state를 지정하지만, cluster 안의 여러 CPU가 동시에 state를 바꿀 때 생기는 race를 피하려면 값을 `cluster` state와 `inbound` state 두 부분으로 나누고 추가 state를 도입해야 합니다. 자세한 내용은 `Cluster state` 절에 있습니다.
CPU state와 cluster state를 구분하기 위해 CPU에는 `CPU_`, cluster 쪽에는 `CLUSTER_` 또는 `INBOUND_` prefix를 붙입니다.
CPU state
100-140이 algorithm에서는 multi-core processor의 각 core를 CPU라고 부릅니다. CPU는 single-threaded라고 가정하므로 한 시점에 한 가지 작업만 수행할 수 있고, 따라서 기본 model에 밀접하게 들어맞습니다.
system의 각 CPU에는 `CPU_DOWN`, `CPU_COMING_UP`, `CPU_UP`, `CPU_GOING_DOWN` 네 state가 정의됩니다.
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 eventpolicy·hardware event가 시작을 유발하고 cluster setup과 CPU teardown 완료가 후속 전이를 확정합니다.
네 정의는 기본 model과 거의 같습니다. trigger event가 spontaneous라는 말은 외부 event를 기다리지 않고 CPU가 local progress만으로 다음 state로 전이할 수 있다는 뜻입니다.
CPU_DOWN
141-158CPU는 power-down 준비가 끝나면 `CPU_DOWN`에 도달합니다. 보통 WFI instruction 또는 firmware call을 통해 스스로 power off하거나 suspend합니다.
| 항목 | 내용 |
|---|---|
| 다음 state | `CPU_COMING_UP` |
| 조건 | 없음 |
| trigger a | 다른 CPU의 policy decision에 따른 명시적 hardware power-up operation |
| trigger b | interrupt 같은 hardware event |
CPU_COMING_UP
159-175cluster가 setup되어 coherent해지기 전에는 CPU가 hardware coherency에 참여할 수 없습니다. cluster가 준비되지 않았다면 CPU는 setup이 끝날 때까지 `CPU_COMING_UP`에서 기다립니다.
| 항목 | 내용 |
|---|---|
| 다음 state | `CPU_UP` |
| 조건 | parent cluster가 `CLUSTER_UP`이어야 함 |
| trigger | parent cluster가 `CLUSTER_UP`으로 전이 |
`CLUSTER_UP`의 의미는 `Cluster state` 절에서 설명합니다.
CPU_UP
176-199CPU가 `CPU_UP`에 도달하면 local coherency 참여를 시작해도 안전합니다. 실제 진입은 kernel의 CPU resume code로 jump해 수행합니다.
이 정의는 기본 model과 조금 다릅니다. `CPU_UP`은 CPU가 이미 coherent하다는 뜻은 아니지만 kernel resume이 안전하다는 뜻입니다. 나머지 resume 단계는 kernel이 처리하므로 race avoidance algorithm에서는 보이지 않습니다.
CPU는 shutdown 또는 suspend하라는 명시적 policy decision이 내려질 때까지 이 state에 머뭅니다.
| 항목 | 내용 |
|---|---|
| 다음 state | `CPU_GOING_DOWN` |
| 조건 | 없음 |
| trigger | 명시적 policy decision |
CPU_GOING_DOWN
200-212이 state에서 CPU는 data cache clean처럼 필요한 작업을 포함해 coherency에서 빠져나옵니다.
| 항목 | 내용 |
|---|---|
| 다음 state | `CPU_DOWN` |
| 조건 | local CPU teardown 완료 |
| trigger | spontaneous |
Cluster state
213-301cluster는 공통 resource를 가진 연결된 CPU group입니다. 여러 CPU를 포함하므로 동시에 여러 일을 할 수 있고, 한 CPU가 cluster를 teardown하는 동안 다른 CPU가 시작할 수도 있습니다.
`outbound side`는 cluster를 teardown하는 CPU가 보는 cluster state이고, `inbound side`는 CPU를 setup하는 CPU가 보는 cluster state입니다.
이 상황을 안전하게 조정하려면 cluster를 setup하는 CPU가 teardown 중인 CPU와 독립적으로 자신의 state를 알릴 수 있어야 합니다. 그래서 cluster state를 두 부분으로 나눕니다.
| 부분 | 가능한 state |
|---|---|
| `cluster` state 또는 outbound view | `CLUSTER_DOWN`, `CLUSTER_UP`, `CLUSTER_GOING_DOWN` |
| `inbound` state | `INBOUND_NOT_COMING_UP`, `INBOUND_COMING_UP` |
두 부분의 조합으로 cluster 전체에는 여섯 가지 가능한 state가 생깁니다.
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_UPoutbound는 cluster state를 바꾸고 inbound는 inbound state를 바꿉니다. race가 없으면 아래 주 경로로 순환합니다.
`----->` 전이는 outbound CPU만 만들 수 있고 `cluster` state만 바꿉니다. `===##>` 전이는 inbound CPU만 만들 수 있고 보통 `inbound` state만 바꿉니다. 다만 outbound 쪽에 더 진행할 전이가 없어 cluster가 `CLUSTER_DOWN`에 놓인 경우는 예외입니다.
algorithm 자체는 cluster 안에서 어떤 CPU가 inbound와 outbound 역할을 맡는지 정하지 않습니다. 이는 다른 방법으로 미리 결정해야 하며 `Last man and first man selection` 절에서 설명합니다.
`CLUSTER_DOWN/INBOUND_NOT_COMING_UP`만 cluster를 실제로 power down할 수 있는 state입니다.
inbound와 outbound CPU의 병렬성 때문에 `CLUSTER_GOING_DOWN/INBOUND_NOT_COMING_UP`에서 `CLUSTER_DOWN/INBOUND_COMING_UP`으로 가는 길이 두 개입니다. 두 번째 길은 cluster teardown을 완전히 피합니다.
`CLUSTER_UP/INBOUND_COMING_UP`은 기본 model의 UP과 같습니다. 마지막 `CLUSTER_UP/INBOUND_NOT_COMING_UP` 전이는 state machine을 다음 cycle에 맞게 reset할 뿐인 단순 전이입니다.
아래 상세 설명에서 다음 state는 `<cluster state>/<inbound state> (<transitioner>)` 형식이며 transitioner는 inbound 또는 outbound 중 전이를 수행할 side입니다.
CLUSTER_DOWN/INBOUND_NOT_COMING_UP
302-314| 항목 | 내용 |
|---|---|
| 다음 state | `CLUSTER_DOWN/INBOUND_COMING_UP` (inbound) |
| 조건 | 없음 |
| trigger a | 다른 CPU의 policy decision에 따른 명시적 hardware power-up operation |
| trigger b | interrupt 같은 hardware event |
CLUSTER_DOWN/INBOUND_COMING_UP
315-333inbound CPU가 cluster-level hardware coherency enable과 cache invalidate 같은 필요한 작업을 포함해 cluster를 setup합니다.
목적은 cluster의 다른 CPU가 coherency에 안전하게 들어갈 수 있을 만큼 cluster-level setup을 끝내는 것입니다.
| 항목 | 내용 |
|---|---|
| 다음 state | `CLUSTER_UP/INBOUND_COMING_UP` (inbound) |
| 조건 | cluster-level setup과 hardware coherency 완료 |
| trigger | spontaneous |
CLUSTER_UP/INBOUND_COMING_UP
334-351cluster-level setup이 끝나고 cluster의 hardware coherency가 활성화되어 다른 CPU가 안전하게 coherency에 들어갈 수 있습니다.
즉시 `CLUSTER_UP/INBOUND_NOT_COMING_UP`으로 이어지는 transient state입니다. cluster의 다른 모든 CPU는 두 state를 동등하게 취급해야 합니다.
| 항목 | 내용 |
|---|---|
| 다음 state | `CLUSTER_UP/INBOUND_NOT_COMING_UP` (inbound) |
| 조건 | 없음 |
| trigger | spontaneous |
CLUSTER_UP/INBOUND_NOT_COMING_UP
352-368cluster-level setup과 hardware coherency enable이 완료되어 다른 CPU가 안전하게 coherency에 들어갈 수 있습니다. cluster power-down policy decision이 내려질 때까지 이 state에 머뭅니다.
| 항목 | 내용 |
|---|---|
| 다음 state | `CLUSTER_GOING_DOWN/INBOUND_NOT_COMING_UP` (outbound) |
| 조건 | 없음 |
| trigger | cluster를 power down하라는 policy decision |
CLUSTER_GOING_DOWN/INBOUND_NOT_COMING_UP
369-404outbound CPU가 cluster를 teardown합니다. 선택된 CPU는 cluster의 모든 CPU가 `CPU_DOWN`이 될 때까지 이 state에서 기다려야 합니다.
모든 CPU가 `CPU_DOWN`이면 data cache clean과 cluster-level coherency exit 등을 수행해 cluster를 teardown할 수 있습니다.
쓸데없는 teardown을 피하려면 outbound CPU가 inbound cluster state의 비동기 `INBOUND_COMING_UP` 전이를 확인해야 합니다. 대신 개별 CPU가 `CPU_COMING_UP` 또는 `CPU_UP`에 들어가는지 검사할 수도 있습니다.
| 다음 state | transitioner | 조건 | trigger |
|---|---|---|---|
| `CLUSTER_DOWN/INBOUND_NOT_COMING_UP` | outbound | cluster teardown 완료, power off 준비 | spontaneous |
| `CLUSTER_GOING_DOWN/INBOUND_COMING_UP` | inbound | 없음 | 다른 CPU의 policy decision에 따른 hardware power-up 또는 interrupt 같은 hardware event |
CLUSTER_GOING_DOWN/INBOUND_COMING_UP
405-442cluster가 teardown 중이거나 막 teardown되었지만 다른 CPU가 그 사이 online이 되어 cluster setup을 다시 시도하는 race state입니다.
outbound CPU가 이 state를 보면 두 선택지가 있습니다. 첫째, teardown을 취소해 cluster를 `CLUSTER_UP`으로 복구합니다. 둘째, teardown을 끝내 `CLUSTER_DOWN`으로 만든 뒤 inbound CPU가 거기서 cluster를 다시 setup하게 합니다.
첫 번째 선택은 cluster가 실제로 power down되지 않을 상황에서 불필요한 teardown과 setup을 피하므로 latency를 줄일 수 있습니다.
| 다음 state | transitioner | 조건 | trigger |
|---|---|---|---|
| `CLUSTER_UP/INBOUND_COMING_UP` | outbound | cluster-level setup과 hardware coherency 완료 | spontaneous |
| `CLUSTER_DOWN/INBOUND_COMING_UP` | outbound | cluster teardown 완료, power off 준비 | spontaneous |
Last man and First man selection
443-479outbound side에서 cluster teardown을 수행하는 CPU를 흔히 `last man`, inbound side에서 cluster setup을 수행하는 CPU를 `first man`이라고 부릅니다. 위 race avoidance algorithm은 어느 CPU가 이 역할을 맡을지 선택하는 mechanism을 제공하지 않습니다.
last man 선택 시에는 shutdown에 참여하는 모든 CPU가 처음에는 Linux를 실행하며 coherent합니다. 따라서 CPU가 non-coherent해지기 전에 일반 spinlock으로 last man을 안전하게 고를 수 있습니다.
first man은 외부 wake-up event에 반응해 여러 CPU가 비동기적으로 power up할 수 있으므로 동적 mechanism이 필요합니다. CPU 하나만 first man 역할을 맡아 cluster-level initialization을 수행하고, 나머지는 완료될 때까지 기다려야 합니다.
cluster-level initialization에는 bus fabric의 coherency control 설정 같은 작업이 포함될 수 있습니다. 현재 `mcpm_head.S` 구현은 이 arbitration을 위해 별도 mutual exclusion mechanism을 사용하며 자세한 내용은 `vlocks.txt`에 있습니다.
Features and Limitations
480-524현재 ARM 구현은 low-level inbound CPU operation을 담당하는 `arch/arm/common/mcpm_head.S`와 그 밖의 작업을 담당하는 `arch/arm/common/mcpm_entry.c`로 나뉩니다.
| symbol 또는 경로 | 역할 |
|---|---|
| `__mcpm_cpu_going_down()` | CPU가 `CPU_GOING_DOWN`으로 전이했음을 알림 |
| `__mcpm_cpu_down()` | CPU가 `CPU_DOWN`으로 전이했음을 알림 |
| `mcpm_head.S` low-level power-up | CPU를 `CPU_COMING_UP`에서 `CPU_UP`으로 전이시킴. CPU별 setup code를 포함할 수 있으나 현재 구현에는 없음 |
| `__mcpm_outbound_enter_critical()` | `CLUSTER_UP`에서 `CLUSTER_GOING_DOWN` 전이를 처리 |
| `__mcpm_outbound_leave_critical()` | `CLUSTER_GOING_DOWN`에서 `CLUSTER_DOWN` 또는 취소 시 `CLUSTER_UP`으로 복귀하는 전이를 처리 |
`__mcpm_outbound_enter_critical()`과 `__mcpm_outbound_leave_critical()`은 cluster-level 안전 전이에 필요한 추가 inter-CPU coordination 때문에 `__mcpm_cpu_*()` 함수보다 복잡합니다.
cluster는 `mcpm_head.S`의 low-level power-up code를 통해 `CLUSTER_DOWN`에서 `CLUSTER_UP`으로 돌아갑니다. 보통 `mcpm_sync_init`을 통해 등록한 platform-specific `power_up_setup` 함수가 platform별 setup을 제공합니다.
현재 설명과 구현은 두 level을 넘는 CPU topology, 즉 cluster의 cluster를 지원하지 않습니다. 추가 topology level마다 cluster-level state를 복제하고 중간, 즉 outermost가 아닌 cluster level의 transition rule을 수정하면 확장할 수 있습니다.
Colophon
525-533Dave Martin이 Nicolas Pitre, Achin Gupta와 협력하여 Linaro Limited를 위해 이 algorithm을 처음 만들고 문서화했습니다.
Copyright (C) 2012-2013 Linaro Limited. `linux/COPYING`에 정의된 GNU General Public License Version 2 조건으로 배포됩니다.
요약과 해설
cluster-pm-race-avoidance.rst:1-533핵심은 coherency 자체에 의존하는 spinlock을 쓸 수 없는 구간을 coherent memory protocol로 건너는 것입니다. CPU는 단일 네-state cycle을 따르고, cluster는 inbound와 outbound view를 분리해 teardown과 동시 wake-up race를 안전하게 처리합니다.
CPU는 단일 state를, cluster는 독립적인 두 state component의 조합을 사용합니다.