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