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