cluster-pm-race-avoidance.rst 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533
  1. =========================================================
  2. Cluster-wide Power-up/power-down race avoidance algorithm
  3. =========================================================
  4. This file documents the algorithm which is used to coordinate CPU and
  5. cluster setup and teardown operations and to manage hardware coherency
  6. controls safely.
  7. The section "Rationale" explains what the algorithm is for and why it is
  8. needed. "Basic model" explains general concepts using a simplified view
  9. of the system. The other sections explain the actual details of the
  10. algorithm in use.
  11. Rationale
  12. ---------
  13. In a system containing multiple CPUs, it is desirable to have the
  14. ability to turn off individual CPUs when the system is idle, reducing
  15. power consumption and thermal dissipation.
  16. In a system containing multiple clusters of CPUs, it is also desirable
  17. to have the ability to turn off entire clusters.
  18. Turning entire clusters off and on is a risky business, because it
  19. involves performing potentially destructive operations affecting a group
  20. of independently running CPUs, while the OS continues to run. This
  21. means that we need some coordination in order to ensure that critical
  22. cluster-level operations are only performed when it is truly safe to do
  23. so.
  24. Simple locking may not be sufficient to solve this problem, because
  25. mechanisms like Linux spinlocks may rely on coherency mechanisms which
  26. are not immediately enabled when a cluster powers up. Since enabling or
  27. disabling those mechanisms may itself be a non-atomic operation (such as
  28. writing some hardware registers and invalidating large caches), other
  29. methods of coordination are required in order to guarantee safe
  30. power-down and power-up at the cluster level.
  31. The mechanism presented in this document describes a coherent memory
  32. based protocol for performing the needed coordination. It aims to be as
  33. lightweight as possible, while providing the required safety properties.
  34. Basic model
  35. -----------
  36. Each cluster and CPU is assigned a state, as follows:
  37. - DOWN
  38. - COMING_UP
  39. - UP
  40. - GOING_DOWN
  41. ::
  42. +---------> UP ----------+
  43. | v
  44. COMING_UP GOING_DOWN
  45. ^ |
  46. +--------- DOWN <--------+
  47. DOWN:
  48. The CPU or cluster is not coherent, and is either powered off or
  49. suspended, or is ready to be powered off or suspended.
  50. COMING_UP:
  51. The CPU or cluster has committed to moving to the UP state.
  52. It may be part way through the process of initialisation and
  53. enabling coherency.
  54. UP:
  55. The CPU or cluster is active and coherent at the hardware
  56. level. A CPU in this state is not necessarily being used
  57. actively by the kernel.
  58. GOING_DOWN:
  59. The CPU or cluster has committed to moving to the DOWN
  60. state. It may be part way through the process of teardown and
  61. coherency exit.
  62. Each CPU has one of these states assigned to it at any point in time.
  63. The CPU states are described in the "CPU state" section, below.
  64. Each cluster is also assigned a state, but it is necessary to split the
  65. state value into two parts (the "cluster" state and "inbound" state) and
  66. to introduce additional states in order to avoid races between different
  67. CPUs in the cluster simultaneously modifying the state. The cluster-
  68. level states are described in the "Cluster state" section.
  69. To help distinguish the CPU states from cluster states in this
  70. discussion, the state names are given a `CPU_` prefix for the CPU states,
  71. and a `CLUSTER_` or `INBOUND_` prefix for the cluster states.
  72. CPU state
  73. ---------
  74. In this algorithm, each individual core in a multi-core processor is
  75. referred to as a "CPU". CPUs are assumed to be single-threaded:
  76. therefore, a CPU can only be doing one thing at a single point in time.
  77. This means that CPUs fit the basic model closely.
  78. The algorithm defines the following states for each CPU in the system:
  79. - CPU_DOWN
  80. - CPU_COMING_UP
  81. - CPU_UP
  82. - CPU_GOING_DOWN
  83. ::
  84. cluster setup and
  85. CPU setup complete policy decision
  86. +-----------> CPU_UP ------------+
  87. | v
  88. CPU_COMING_UP CPU_GOING_DOWN
  89. ^ |
  90. +----------- CPU_DOWN <----------+
  91. policy decision CPU teardown complete
  92. or hardware event
  93. The definitions of the four states correspond closely to the states of
  94. the basic model.
  95. Transitions between states occur as follows.
  96. A trigger event (spontaneous) means that the CPU can transition to the
  97. next state as a result of making local progress only, with no
  98. requirement for any external event to happen.
  99. CPU_DOWN:
  100. A CPU reaches the CPU_DOWN state when it is ready for
  101. power-down. On reaching this state, the CPU will typically
  102. power itself down or suspend itself, via a WFI instruction or a
  103. firmware call.
  104. Next state:
  105. CPU_COMING_UP
  106. Conditions:
  107. none
  108. Trigger events:
  109. a) an explicit hardware power-up operation, resulting
  110. from a policy decision on another CPU;
  111. b) a hardware event, such as an interrupt.
  112. CPU_COMING_UP:
  113. A CPU cannot start participating in hardware coherency until the
  114. cluster is set up and coherent. If the cluster is not ready,
  115. then the CPU will wait in the CPU_COMING_UP state until the
  116. cluster has been set up.
  117. Next state:
  118. CPU_UP
  119. Conditions:
  120. The CPU's parent cluster must be in CLUSTER_UP.
  121. Trigger events:
  122. Transition of the parent cluster to CLUSTER_UP.
  123. Refer to the "Cluster state" section for a description of the
  124. CLUSTER_UP state.
  125. CPU_UP:
  126. When a CPU reaches the CPU_UP state, it is safe for the CPU to
  127. start participating in local coherency.
  128. This is done by jumping to the kernel's CPU resume code.
  129. Note that the definition of this state is slightly different
  130. from the basic model definition: CPU_UP does not mean that the
  131. CPU is coherent yet, but it does mean that it is safe to resume
  132. the kernel. The kernel handles the rest of the resume
  133. procedure, so the remaining steps are not visible as part of the
  134. race avoidance algorithm.
  135. The CPU remains in this state until an explicit policy decision
  136. is made to shut down or suspend the CPU.
  137. Next state:
  138. CPU_GOING_DOWN
  139. Conditions:
  140. none
  141. Trigger events:
  142. explicit policy decision
  143. CPU_GOING_DOWN:
  144. While in this state, the CPU exits coherency, including any
  145. operations required to achieve this (such as cleaning data
  146. caches).
  147. Next state:
  148. CPU_DOWN
  149. Conditions:
  150. local CPU teardown complete
  151. Trigger events:
  152. (spontaneous)
  153. Cluster state
  154. -------------
  155. A cluster is a group of connected CPUs with some common resources.
  156. Because a cluster contains multiple CPUs, it can be doing multiple
  157. things at the same time. This has some implications. In particular, a
  158. CPU can start up while another CPU is tearing the cluster down.
  159. In this discussion, the "outbound side" is the view of the cluster state
  160. as seen by a CPU tearing the cluster down. The "inbound side" is the
  161. view of the cluster state as seen by a CPU setting the CPU up.
  162. In order to enable safe coordination in such situations, it is important
  163. that a CPU which is setting up the cluster can advertise its state
  164. independently of the CPU which is tearing down the cluster. For this
  165. reason, the cluster state is split into two parts:
  166. "cluster" state: The global state of the cluster; or the state
  167. on the outbound side:
  168. - CLUSTER_DOWN
  169. - CLUSTER_UP
  170. - CLUSTER_GOING_DOWN
  171. "inbound" state: The state of the cluster on the inbound side.
  172. - INBOUND_NOT_COMING_UP
  173. - INBOUND_COMING_UP
  174. The different pairings of these states results in six possible
  175. states for the cluster as a whole::
  176. CLUSTER_UP
  177. +==========> INBOUND_NOT_COMING_UP -------------+
  178. # |
  179. |
  180. CLUSTER_UP <----+ |
  181. INBOUND_COMING_UP | v
  182. ^ CLUSTER_GOING_DOWN CLUSTER_GOING_DOWN
  183. # INBOUND_COMING_UP <=== INBOUND_NOT_COMING_UP
  184. CLUSTER_DOWN | |
  185. INBOUND_COMING_UP <----+ |
  186. |
  187. ^ |
  188. +=========== CLUSTER_DOWN <------------+
  189. INBOUND_NOT_COMING_UP
  190. Transitions -----> can only be made by the outbound CPU, and
  191. only involve changes to the "cluster" state.
  192. Transitions ===##> can only be made by the inbound CPU, and only
  193. involve changes to the "inbound" state, except where there is no
  194. further transition possible on the outbound side (i.e., the
  195. outbound CPU has put the cluster into the CLUSTER_DOWN state).
  196. The race avoidance algorithm does not provide a way to determine
  197. which exact CPUs within the cluster play these roles. This must
  198. be decided in advance by some other means. Refer to the section
  199. "Last man and first man selection" for more explanation.
  200. CLUSTER_DOWN/INBOUND_NOT_COMING_UP is the only state where the
  201. cluster can actually be powered down.
  202. The parallelism of the inbound and outbound CPUs is observed by
  203. the existence of two different paths from CLUSTER_GOING_DOWN/
  204. INBOUND_NOT_COMING_UP (corresponding to GOING_DOWN in the basic
  205. model) to CLUSTER_DOWN/INBOUND_COMING_UP (corresponding to
  206. COMING_UP in the basic model). The second path avoids cluster
  207. teardown completely.
  208. CLUSTER_UP/INBOUND_COMING_UP is equivalent to UP in the basic
  209. model. The final transition to CLUSTER_UP/INBOUND_NOT_COMING_UP
  210. is trivial and merely resets the state machine ready for the
  211. next cycle.
  212. Details of the allowable transitions follow.
  213. The next state in each case is notated
  214. <cluster state>/<inbound state> (<transitioner>)
  215. where the <transitioner> is the side on which the transition
  216. can occur; either the inbound or the outbound side.
  217. CLUSTER_DOWN/INBOUND_NOT_COMING_UP:
  218. Next state:
  219. CLUSTER_DOWN/INBOUND_COMING_UP (inbound)
  220. Conditions:
  221. none
  222. Trigger events:
  223. a) an explicit hardware power-up operation, resulting
  224. from a policy decision on another CPU;
  225. b) a hardware event, such as an interrupt.
  226. CLUSTER_DOWN/INBOUND_COMING_UP:
  227. In this state, an inbound CPU sets up the cluster, including
  228. enabling of hardware coherency at the cluster level and any
  229. other operations (such as cache invalidation) which are required
  230. in order to achieve this.
  231. The purpose of this state is to do sufficient cluster-level
  232. setup to enable other CPUs in the cluster to enter coherency
  233. safely.
  234. Next state:
  235. CLUSTER_UP/INBOUND_COMING_UP (inbound)
  236. Conditions:
  237. cluster-level setup and hardware coherency complete
  238. Trigger events:
  239. (spontaneous)
  240. CLUSTER_UP/INBOUND_COMING_UP:
  241. Cluster-level setup is complete and hardware coherency is
  242. enabled for the cluster. Other CPUs in the cluster can safely
  243. enter coherency.
  244. This is a transient state, leading immediately to
  245. CLUSTER_UP/INBOUND_NOT_COMING_UP. All other CPUs on the cluster
  246. should consider treat these two states as equivalent.
  247. Next state:
  248. CLUSTER_UP/INBOUND_NOT_COMING_UP (inbound)
  249. Conditions:
  250. none
  251. Trigger events:
  252. (spontaneous)
  253. CLUSTER_UP/INBOUND_NOT_COMING_UP:
  254. Cluster-level setup is complete and hardware coherency is
  255. enabled for the cluster. Other CPUs in the cluster can safely
  256. enter coherency.
  257. The cluster will remain in this state until a policy decision is
  258. made to power the cluster down.
  259. Next state:
  260. CLUSTER_GOING_DOWN/INBOUND_NOT_COMING_UP (outbound)
  261. Conditions:
  262. none
  263. Trigger events:
  264. policy decision to power down the cluster
  265. CLUSTER_GOING_DOWN/INBOUND_NOT_COMING_UP:
  266. An outbound CPU is tearing the cluster down. The selected CPU
  267. must wait in this state until all CPUs in the cluster are in the
  268. CPU_DOWN state.
  269. When all CPUs are in the CPU_DOWN state, the cluster can be torn
  270. down, for example by cleaning data caches and exiting
  271. cluster-level coherency.
  272. To avoid wasteful unnecessary teardown operations, the outbound
  273. should check the inbound cluster state for asynchronous
  274. transitions to INBOUND_COMING_UP. Alternatively, individual
  275. CPUs can be checked for entry into CPU_COMING_UP or CPU_UP.
  276. Next states:
  277. CLUSTER_DOWN/INBOUND_NOT_COMING_UP (outbound)
  278. Conditions:
  279. cluster torn down and ready to power off
  280. Trigger events:
  281. (spontaneous)
  282. CLUSTER_GOING_DOWN/INBOUND_COMING_UP (inbound)
  283. Conditions:
  284. none
  285. Trigger events:
  286. a) an explicit hardware power-up operation,
  287. resulting from a policy decision on another
  288. CPU;
  289. b) a hardware event, such as an interrupt.
  290. CLUSTER_GOING_DOWN/INBOUND_COMING_UP:
  291. The cluster is (or was) being torn down, but another CPU has
  292. come online in the meantime and is trying to set up the cluster
  293. again.
  294. If the outbound CPU observes this state, it has two choices:
  295. a) back out of teardown, restoring the cluster to the
  296. CLUSTER_UP state;
  297. b) finish tearing the cluster down and put the cluster
  298. in the CLUSTER_DOWN state; the inbound CPU will
  299. set up the cluster again from there.
  300. Choice (a) permits the removal of some latency by avoiding
  301. unnecessary teardown and setup operations in situations where
  302. the cluster is not really going to be powered down.
  303. Next states:
  304. CLUSTER_UP/INBOUND_COMING_UP (outbound)
  305. Conditions:
  306. cluster-level setup and hardware
  307. coherency complete
  308. Trigger events:
  309. (spontaneous)
  310. CLUSTER_DOWN/INBOUND_COMING_UP (outbound)
  311. Conditions:
  312. cluster torn down and ready to power off
  313. Trigger events:
  314. (spontaneous)
  315. Last man and First man selection
  316. --------------------------------
  317. The CPU which performs cluster tear-down operations on the outbound side
  318. is commonly referred to as the "last man".
  319. The CPU which performs cluster setup on the inbound side is commonly
  320. referred to as the "first man".
  321. The race avoidance algorithm documented above does not provide a
  322. mechanism to choose which CPUs should play these roles.
  323. Last man:
  324. When shutting down the cluster, all the CPUs involved are initially
  325. executing Linux and hence coherent. Therefore, ordinary spinlocks can
  326. be used to select a last man safely, before the CPUs become
  327. non-coherent.
  328. First man:
  329. Because CPUs may power up asynchronously in response to external wake-up
  330. events, a dynamic mechanism is needed to make sure that only one CPU
  331. attempts to play the first man role and do the cluster-level
  332. initialisation: any other CPUs must wait for this to complete before
  333. proceeding.
  334. Cluster-level initialisation may involve actions such as configuring
  335. coherency controls in the bus fabric.
  336. The current implementation in mcpm_head.S uses a separate mutual exclusion
  337. mechanism to do this arbitration. This mechanism is documented in
  338. detail in vlocks.txt.
  339. Features and Limitations
  340. ------------------------
  341. Implementation:
  342. The current ARM-based implementation is split between
  343. arch/arm/common/mcpm_head.S (low-level inbound CPU operations) and
  344. arch/arm/common/mcpm_entry.c (everything else):
  345. __mcpm_cpu_going_down() signals the transition of a CPU to the
  346. CPU_GOING_DOWN state.
  347. __mcpm_cpu_down() signals the transition of a CPU to the CPU_DOWN
  348. state.
  349. A CPU transitions to CPU_COMING_UP and then to CPU_UP via the
  350. low-level power-up code in mcpm_head.S. This could
  351. involve CPU-specific setup code, but in the current
  352. implementation it does not.
  353. __mcpm_outbound_enter_critical() and __mcpm_outbound_leave_critical()
  354. handle transitions from CLUSTER_UP to CLUSTER_GOING_DOWN
  355. and from there to CLUSTER_DOWN or back to CLUSTER_UP (in
  356. the case of an aborted cluster power-down).
  357. These functions are more complex than the __mcpm_cpu_*()
  358. functions due to the extra inter-CPU coordination which
  359. is needed for safe transitions at the cluster level.
  360. A cluster transitions from CLUSTER_DOWN back to CLUSTER_UP via
  361. the low-level power-up code in mcpm_head.S. This
  362. typically involves platform-specific setup code,
  363. provided by the platform-specific power_up_setup
  364. function registered via mcpm_sync_init.
  365. Deep topologies:
  366. As currently described and implemented, the algorithm does not
  367. support CPU topologies involving more than two levels (i.e.,
  368. clusters of clusters are not supported). The algorithm could be
  369. extended by replicating the cluster-level states for the
  370. additional topological levels, and modifying the transition
  371. rules for the intermediate (non-outermost) cluster levels.
  372. Colophon
  373. --------
  374. Originally created and documented by Dave Martin for Linaro Limited, in
  375. collaboration with Nicolas Pitre and Achin Gupta.
  376. Copyright (C) 2012-2013 Linaro Limited
  377. Distributed under the terms of Version 2 of the GNU General Public
  378. License, as defined in linux/COPYING.