docs/psci-pd-tree.md

------------
Requirements
------------

1.  A platform must export the `plat_get_aff_count()` and
    `plat_get_aff_state()` APIs to enable the generic PSCI code to
    populate a tree that describes the hierarchy of power domains in the
    system. This approach is inflexible because a change to the topology
    requires a change in the code.

    It would be much simpler for the platform to describe its power domain tree
    in a data structure.

2.  The generic PSCI code generates MPIDRs in order to populate the power domain
    tree. It also uses an MPIDR to find a node in the tree. The assumption that
    a platform will use exactly the same MPIDRs as generated by the generic PSCI
    code is not scalable. The use of an MPIDR also restricts the number of
    levels in the power domain tree to four.

    Therefore, there is a need to decouple allocation of MPIDRs from the
    mechanism used to populate the power domain topology tree.

3.  The current arrangement of the power domain tree requires a binary search
    over the sibling nodes at a particular level to find a specified power
    domain node. During a power management operation, the tree is traversed from
    a 'start' to an 'end' power level. The binary search is required to find the
    node at each level. The natural way to perform this traversal is to
    start from a leaf node and follow the parent node pointer to reach the end
    level.

    Therefore, there is a need to define data structures that implement the tree in
    a way which facilitates such a traversal.

4.  The attributes of a core power domain differ from the attributes of power
    domains at higher levels. For example, only a core power domain can be identified
    using an MPIDR. There is no requirement to perform state coordination while
    performing a power management operation on the core power domain.

    Therefore, there is a need to implement the tree in a way which facilitates this
    distinction between a leaf and non-leaf node and any associated
    optimizations.


------
Design
------

### Describing a power domain tree

To fulfill requirement 1., the existing platform APIs
`plat_get_aff_count()` and `plat_get_aff_state()` have been
removed. A platform must define an array of unsigned chars such that:

1.  The first entry in the array specifies the number of power domains at the
    highest power level implemented in the platform. This caters for platforms
    where the power domain tree does not have a single root node, for example,
    the FVP has two cluster power domains at the highest level (1).

2.  Each subsequent entry corresponds to a power domain and contains the number
    of power domains that are its direct children.

3.  The size of the array minus the first entry will be equal to the number of
    non-leaf power domains.

4.  The value in each entry in the array is used to find the number of entries
    to consider at the next level. The sum of the values (number of children) of
    all the entries at a level specifies the number of entries in the array for
    the next level.

The following example power domain topology tree will be used to describe the
above text further. The leaf and non-leaf nodes in this tree have been numbered
separately.

```
                                     +-+
                                     |0|
                                     +-+
                                    /   \
                                   /     \
                                  /       \
                                 /         \
                                /           \
                               /             \
                              /               \
                             /                 \
                            /                   \
                           /                     \
                        +-+                       +-+
                        |1|                       |2|
                        +-+                       +-+
                       /   \                     /   \
                      /     \                   /     \
                     /       \                 /       \
                    /         \               /         \
                 +-+           +-+         +-+           +-+
                 |3|           |4|         |5|           |6|
                 +-+           +-+         +-+           +-+
        +---+-----+    +----+----|     +----+----+     +----+-----+-----+
        |   |     |    |    |    |     |    |    |     |    |     |     |
        |   |     |    |    |    |     |    |    |     |    |     |     |
        v   v     v    v    v    v     v    v    v     v    v     v     v
      +-+  +-+   +-+  +-+  +-+  +-+   +-+  +-+  +-+   +-+  +--+  +--+  +--+
      |0|  |1|   |2|  |3|  |4|  |5|   |6|  |7|  |8|   |9|  |10|  |11|  |12|
      +-+  +-+   +-+  +-+  +-+  +-+   +-+  +-+  +-+   +-+  +--+  +--+  +--+
```


This tree is defined by the platform as the array described above as follows:

```
    #define PLAT_NUM_POWER_DOMAINS       20
    #define PLATFORM_CORE_COUNT          13
    #define PSCI_NUM_NON_CPU_PWR_DOMAINS \
                       (PLAT_NUM_POWER_DOMAINS - PLATFORM_CORE_COUNT)

    unsigned char plat_power_domain_tree_desc[] = { 1, 2, 2, 2, 3, 3, 3, 4};
```

### Removing assumptions about MPIDRs used in a platform

To fulfill requirement 2., it is assumed that the platform assigns a
unique number (core index) between `0` and `PLAT_CORE_COUNT - 1` to each core
power domain. MPIDRs could be allocated in any manner and will not be used to
populate the tree.

`plat_core_pos_by_mpidr(mpidr)` will return the core index for the core
corresponding to the MPIDR. It will return an error (-1) if an MPIDR is passed
which is not allocated or corresponds to an absent core. The semantics of this
platform API have changed since it is required to validate the passed MPIDR. It
has been made a mandatory API as a result.

Another mandatory API, `plat_my_core_pos()` has been added to return the core
index for the calling core. This API provides a more lightweight mechanism to get
the index since there is no need to validate the MPIDR of the calling core.

The platform should assign the core indices (as illustrated in the diagram above)
such that, if the core nodes are numbered from left to right, then the index
for a core domain will be the same as the index returned by
 `plat_core_pos_by_mpidr()` or `plat_my_core_pos()` for that core. This
relationship allows the core nodes to be allocated in a separate array
(requirement 4.) during `psci_setup()` in such an order that the index of the
core in the array is the same as the return value from these APIs.

#### Dealing with holes in MPIDR allocation

For platforms where the number of allocated MPIDRs is equal to the number of
core power domains, for example, Juno and FVPs, the logic to convert an MPIDR to
a core index should remain unchanged. Both Juno and FVP use a simple collision
proof hash function to do this.

It is possible that on some platforms, the allocation of MPIDRs is not
contiguous or certain cores have been disabled. This essentially means that the
MPIDRs have been sparsely allocated, that is, the size of the range of MPIDRs
used by the platform is not equal to the number of core power domains.

The platform could adopt one of the following approaches to deal with this
scenario:

1.  Implement more complex logic to convert a valid MPIDR to a core index while
    maintaining the relationship described earlier. This means that the power
    domain tree descriptor will not describe any core power domains which are
    disabled or absent. Entries will not be allocated in the tree for these
    domains.

2.  Treat unallocated MPIDRs and disabled cores as absent but still describe them
    in the power domain descriptor, that is, the number of core nodes described
    is equal to the size of the range of MPIDRs allocated. This approach will
    lead to memory wastage since entries will be allocated in the tree but will
    allow use of a simpler logic to convert an MPIDR to a core index.


### Traversing through and distinguishing between core and non-core power domains

To fulfill requirement 3 and 4, separate data structures have been defined
to represent leaf and non-leaf power domain nodes in the tree.

```
/*******************************************************************************
 * The following two data structures implement the power domain tree. The tree
 * is used to track the state of all the nodes i.e. power domain instances
 * described by the platform. The tree consists of nodes that describe CPU power
 * domains i.e. leaf nodes and all other power domains which are parents of a
 * CPU power domain i.e. non-leaf nodes.
 ******************************************************************************/
typedef struct non_cpu_pwr_domain_node {
    /*
     * Index of the first CPU power domain node level 0 which has this node
     * as its parent.
     */
    unsigned int cpu_start_idx;

    /*
     * Number of CPU power domains which are siblings of the domain indexed
     * by 'cpu_start_idx' i.e. all the domains in the range 'cpu_start_idx
     * -> cpu_start_idx + ncpus' have this node as their parent.
     */
    unsigned int ncpus;

    /* Index of the parent power domain node */
    unsigned int parent_node;

    -----
} non_cpu_pd_node_t;

typedef struct cpu_pwr_domain_node {
    unsigned long mpidr;

    /* Index of the parent power domain node */
    unsigned int parent_node;

    -----
} cpu_pd_node_t;
```

The power domain tree is implemented as a combination of the following data
structures.

```
non_cpu_pd_node_t psci_non_cpu_pd_nodes[PSCI_NUM_NON_CPU_PWR_DOMAINS];
cpu_pd_node_t psci_cpu_pd_nodes[PLATFORM_CORE_COUNT];
```

### Populating the power domain tree

The `populate_power_domain_tree()` function in `psci_setup.c` implements the
algorithm to parse the power domain descriptor exported by the platform to
populate the two arrays. It is essentially a breadth-first-search. The nodes for
each level starting from the root are laid out one after another in the
`psci_non_cpu_pd_nodes` and `psci_cpu_pd_nodes` arrays as follows:

```
psci_non_cpu_pd_nodes -> [[Level 3 nodes][Level 2 nodes][Level 1 nodes]]
psci_cpu_pd_nodes -> [Level 0 nodes]
```

For the example power domain tree illustrated above, the `psci_cpu_pd_nodes`
will be populated as follows. The value in each entry is the index of the parent
node. Other fields have been ignored for simplicity.

```
                      +-------------+     ^
                CPU0  |      3      |     |
                      +-------------+     |
                CPU1  |      3      |     |
                      +-------------+     |
                CPU2  |      3      |     |
                      +-------------+     |
                CPU3  |      4      |     |
                      +-------------+     |
                CPU4  |      4      |     |
                      +-------------+     |
                CPU5  |      4      |     | PLATFORM_CORE_COUNT
                      +-------------+     |
                CPU6  |      5      |     |
                      +-------------+     |
                CPU7  |      5      |     |
                      +-------------+     |
                CPU8  |      5      |     |
                      +-------------+     |
                CPU9  |      6      |     |
                      +-------------+     |
                CPU10 |      6      |     |
                      +-------------+     |
                CPU11 |      6      |     |
                      +-------------+     |
                CPU12 |      6      |     v
                      +-------------+
```

The `psci_non_cpu_pd_nodes` array will be populated as follows. The value in
each entry is the index of the parent node.

```
                      +-------------+     ^
                PD0   |      -1     |     |
                      +-------------+     |
                PD1   |      0      |     |
                      +-------------+     |
                PD2   |      0      |     |
                      +-------------+     |
                PD3   |      1      |     | PLAT_NUM_POWER_DOMAINS -
                      +-------------+     | PLATFORM_CORE_COUNT
                PD4   |      1      |     |
                      +-------------+     |
                PD5   |      2      |     |
                      +-------------+     |
                PD6   |      2      |     |
                      +-------------+     v
```

Each core can find its node in the `psci_cpu_pd_nodes` array using the
`plat_my_core_pos()` function. When a core is turned on, the normal world
provides an MPIDR. The `plat_core_pos_by_mpidr()` function is used to validate
the MPIDR before using it to find the corresponding core node. The non-core power
domain nodes do not need to be identified.