arch/arm/cluster-pm-race-avoidance.rst

2 Cluster-wide Power-up/power-down race avoidance algorithm
5 This file documents the algorithm which is used to coordinate CPU and
6 cluster setup and teardown operations and to manage hardware coherency
16 ---------
18 In a system containing multiple CPUs, it is desirable to have the
19 ability to turn off individual CPUs when the system is idle, reducing
23 to have the ability to turn off entire clusters.
27 of independently running CPUs, while the OS continues to run.  This
28 means that we need some coordination in order to ensure that critical
29 cluster-level operations are only performed when it is truly safe to do
32 Simple locking may not be sufficient to solve this problem, because
34 are not immediately enabled when a cluster powers up.  Since enabling or
35 disabling those mechanisms may itself be a non-atomic operation (such as
37 methods of coordination are required in order to guarantee safe
38 power-down and power-up at the cluster level.
41 based protocol for performing the needed coordination.  It aims to be as
46 -----------
50 	- DOWN
51 	- COMING_UP
52 	- UP
53 	- GOING_DOWN
57 	    +---------> UP ----------+
63 	    +--------- DOWN <--------+
68 	suspended, or is ready to be powered off or suspended.
71 	The CPU or cluster has committed to moving to the UP state.
75 UP:
81 	The CPU or cluster has committed to moving to the DOWN
86 Each CPU has one of these states assigned to it at any point in time.
89 Each cluster is also assigned a state, but it is necessary to split the
91 to introduce additional states in order to avoid races between different
92 CPUs in the cluster simultaneously modifying the state.  The cluster-
95 To help distinguish the CPU states from cluster states in this
101 ---------
103 In this algorithm, each individual core in a multi-core processor is
104 referred to as a "CPU".  CPUs are assumed to be single-threaded:
111 	- CPU_DOWN
112 	- CPU_COMING_UP
113 	- CPU_UP
114 	- CPU_GOING_DOWN
120 	      +-----------> CPU_UP ------------+
126 	      +----------- CPU_DOWN <----------+
131 The definitions of the four states correspond closely to the states of
136 A trigger event (spontaneous) means that the CPU can transition to the
138 requirement for any external event to happen.
143 	power-down.  On reaching this state, the CPU will typically
153 		a) an explicit hardware power-up operation, resulting
161 	cluster is set up and coherent.  If the cluster is not ready,
163 	cluster has been set up.
170 		Transition of the parent cluster to CLUSTER_UP.
172 	Refer to the "Cluster state" section for a description of the
177 	When a CPU reaches the CPU_UP state, it is safe for the CPU to
180 	This is done by jumping to the kernel's CPU resume code.
184 	CPU is coherent yet, but it does mean that it is safe to resume
190 	is made to shut down or suspend the CPU.
202 	operations required to achieve this (such as cleaning data
214 -------------
219 CPU can start up while another CPU is tearing the cluster down.
223 view of the cluster state as seen by a CPU setting the CPU up.
225 In order to enable safe coordination in such situations, it is important
226 that a CPU which is setting up the cluster can advertise its state
233 		- CLUSTER_DOWN
234 		- CLUSTER_UP
235 		- CLUSTER_GOING_DOWN
239 		- INBOUND_NOT_COMING_UP
240 		- INBOUND_COMING_UP
247 	          +==========> INBOUND_NOT_COMING_UP -------------+
250 	     CLUSTER_UP     <----+                                |
257 	  INBOUND_COMING_UP <----+                                |
260 	          +===========     CLUSTER_DOWN      <------------+
263 	Transitions -----> can only be made by the outbound CPU, and
264 	only involve changes to the "cluster" state.
267 	involve changes to the "inbound" state, except where there is no
271 	The race avoidance algorithm does not provide a way to determine
273 	be decided in advance by some other means.  Refer to the section
282 	INBOUND_NOT_COMING_UP (corresponding to GOING_DOWN in the basic
283 	model) to CLUSTER_DOWN/INBOUND_COMING_UP (corresponding to
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
309 		a) an explicit hardware power-up operation, resulting
317 	In this state, an inbound CPU sets up the cluster, including
320 	in order to achieve this.
322 	The purpose of this state is to do sufficient cluster-level
323 	setup to enable other CPUs in the cluster to enter coherency
329 		cluster-level setup and hardware coherency complete
336 	Cluster-level setup is complete and hardware coherency is
340 	This is a transient state, leading immediately to
354 	Cluster-level setup is complete and hardware coherency is
359 	made to power the cluster down.
366 		policy decision to power down the cluster
377 	cluster-level coherency.
379 	To avoid wasteful unnecessary teardown operations, the outbound
381 	transitions to INBOUND_COMING_UP.  Alternatively, individual
389 			cluster torn down and ready to power off
398 			a) an explicit hardware power-up operation,
408 	come online in the meantime and is trying to set up the cluster
413 		a) back out of teardown, restoring the cluster to the
418 		   set up the cluster again from there.
422 	the cluster is not really going to be powered down.
429 				cluster-level setup and hardware
437 			cluster torn down and ready to power off
444 --------------------------------
446 The CPU which performs cluster tear-down operations on the outbound side
447 is commonly referred to as the "last man".
450 referred to as the "first man".
453 mechanism to choose which CPUs should play these roles.
460 be used to select a last man safely, before the CPUs become
461 non-coherent.
466 Because CPUs may power up asynchronously in response to external wake-up
467 events, a dynamic mechanism is needed to make sure that only one CPU
468 attempts to play the first man role and do the cluster-level
469 initialisation: any other CPUs must wait for this to complete before
472 Cluster-level initialisation may involve actions such as configuring
476 mechanism to do this arbitration.  This mechanism is documented in
481 ------------------------
485 	The current ARM-based implementation is split between
486 	arch/arm/common/mcpm_head.S (low-level inbound CPU operations) and
489 	__mcpm_cpu_going_down() signals the transition of a CPU to the
492 	__mcpm_cpu_down() signals the transition of a CPU to the CPU_DOWN
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
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).
506 	functions due to the extra inter-CPU coordination which
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
520 	extended by replicating the cluster-level states for the
522 	rules for the intermediate (non-outermost) cluster levels.
526 --------
531 Copyright (C) 2012-2013  Linaro Limited