cluster-pm-race-avoidance.rst

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.