Add a topology description API

[Nicolas Pouillon]

Overview

Goals

• Abstract the low-level description APIs
  • FlattenedDeviceTrees
  • ACPI
  • OpenFrimware
  • UEFI ?
• Enumerate the platform
  • Component connection topology
  • IRQ routing
  • Memory configuration (Cacheability, latency, …)
• Deduce the correct OS mapping
  • For memory allocators (region API)
  • Scheduler lists repartition
  • Shortest-path IRQ routing
  • SRL tasks/resources mapping

APIs

• Explore the topology
  • Extract journey costs
• Query the topology: Get nodes by a selector
  • Proximity (get all rams that are at less than 3 hops than cpu XX)
  • Properties (get all cpus of arch XX)
  • Properties (get all devices of type XX) -- maybe redundant with hexo's device_s tree

Optional features discussion

• Do we need to handle loads accounting (NoC load, CPU, memory, …) here ? (i.e. something like "Ok, for now on I use an avg 1 MBps of NoC path from X to Y, then report to others)
  • NoC is tightly coupled to topology, this could be interesting
  • CPU is somewhat highly dynamic, even if we can sometimes predict, is it obvious here ?
  • Memory has its own allocators, do not duplicate
• If we do not, we probably need a separate accounting library
  • Maybe a-la mem_alloc(), per resource
  • So we must duplicate topology for NoC accounting
• We can also put this is model-specific calls

libTopology data model

Conceptual

It is a graph of nodes. Nodes are associated to an element of the architecture. Some node examples:

• A routing element (DSPIN NoC (as a whole)), a local interconnect
• A CPU+cache
• A memory bank
• An ICU
• A device

Each node can be associated to a device -- There is at most 1 device per node, some nodes have no associated device (e.g. NoC has no dev)

Structures

struct topo_model_s; // forward decl. see below

struct topo_node_s
{
    const struct topo_model_s *model; /// model handling this node
    void *priv;                 /// model's private data
    struct device_s *dev;       /// associated device, if any
};

/**
  The only creteria telling two ports are different is
  private must be different. For models not using private,
  an useless but different value must be set.
 */
struct topo_port_s
{
    const struct topo_node_s *node;   // node owning the port
    void *private;              // port's private.
};

Needed APIs

Device to node bijection

struct device_s *topo_node_to_device(const struct topo_node_s *node);

struct topo_node_s *topo_device_to_node(const struct device_s *dev);

Topology exploration

There must be a high-level call to explore the path from a node to another. We will assume:

• There is one such path
• We do not cross address spaces during the exploration (route a data packet, cant transform it in an IRQ)
• There is one address type for destination

High level call which does the routing and accumulates round-trip metrics:

error_t topo_journey_metrics(
    const struct topo_node_s *start,
    const struct topo_addr_s *dest,
    struct topo_metrics_s *result);

(round-trip is sufficient as there is roughly the same energy involved in reads and writes, and also gives the model the choice of what a round-trip involves (totally different for a noc and a bus))

An address is a destination valid for a type of routing exploration, most of the time it will be a bus address, but may be an IRQ number, an USB device no, …

enum topo_addr_type_e
{
    TOPO_ADDR_BUS;
    TOPO_ADDR_IRQ;
};

struct topo_addr_s
{
    enum topo_addr_type_e type;
    union {
        struct {
            uintptr_t address;
        } bus;
        struct {
            size_t line_no;
        } irq;
    };
};

Accumulated metrics describe the features of the walked path:

struct topo_metrics_s
{
    size_t hop_count;
    uint32_t latency;          /// cycles ? µs ?
    uint32_t max_byte_per_sec; /// capped max on path
    uint32_t power_per_byte;   /// overall consumption estimation
};

Selection function

enum topo_crit_val_e
{
    TOPO_CRIT_DROP,   /// Node is not interesting, stop recursion here in the graph
    TOPO_CRIT_RECURS, /// Node is not selected, but we can recurs through it
    TOPO_CRIT_SELECT, /// Node is selected, and may be recursed down
};

enum topo_cmp_e
{
    TOPO_CMP_LEFT  = -1, /// left better than right
    TOPO_CMP_EQ    = 0,  /// left equals right
    TOPO_CMP_RIGHT = 1,  /// right better than left
};

struct topo_select_item_s
{
    const struct topo_node_s    *node;
    struct topo_metrics_s metrics; // not a pointer !
};

/**
  Selector function
  @param item Node/metrics to filter
  @param priv Selector private data
  @returns whether the node is interesting
*/
typedef enum topo_crit_val_e topo_crit_func_t(
    const struct topo_select_item_s *item,
    const void *priv);

/**
  Sort function
  @param left  Node/metrics to compare
  @param right Node/metrics to compare
  @param priv Sort private data
  @returns comparaison result
*/
typedef enum topo_cmp_e topo_sort_func_t(
    const struct topo_select_item_s *left,
    const struct topo_select_item_s *right,
    const void *priv);

error_t topo_select(
    const struct topo_node_s *start,         /// Start node
    topo_crit_func_t *crit, const void *crit_priv, /// Criterium function, telling whether a node is eligible
    topo_sort_func_t *sort, const void *sort_priv, /// Sorting function, telling order of nodes
    size_t max_items,                   /// Maximal number of nodes to return
    struct topo_select_item_s *items);  /// Output nodes+metrics. Table must be allocated by caller and be able to contain @tt max_items

Needed calls in model-specific functions

/**
 Initialize a topology node.
 */
typedef void topo_model_init_func_t(struct topo_node_s *node, const void *param);

/**
 Destroy a topology node. Reclaim all associated memory
 */
typedef void topo_model_cleanup_func_t(struct topo_node_s *node);

/**
 Compute routing and cost from this node to the next hop, routing
 towards a given destination

 @param node Node of our model where we are coming from
 @param input Input port in node. May be NULL on start node
 @param dest Destination address for the current address space
 @param metrics Metrics to update on the go
 @param peer_input Input port of the next hop
 */
typedef error_t topo_model_journey_next_func_t(
    const struct topo_node_s *node,
    const struct topo_port_s *input,
    const struct topo_addr_s *dest,
    struct topo_metrics_s *metrics,
    struct topo_port_s *peer_input);

/**
 Explore the topology graph. Each call to this function must return next
 valid port.

 @param node Current node
 @param input Port where we came from, exploration should not "go back" to this edge. May be NULL on recursion start
 @param metrics Metrics up to this node
 @param item Returned item for next recursion
 @param state Pointer to a void* where select_next can store its internal state.

 @tt *state is @tt NULL on first call for each node.

 Successive calls to select_next for a given node in a given exploration use the same @tt state value.

 @note As there is no warning for end of iteration, there is no way of calling @tt free(), so @tt *state should be a pointer to preallocated internal data.
 */
typedef error_t topo_model_select_next_func_t(
    const struct topo_node_s *node,
    const struct topo_port_s *input,
    const struct topo_metrics_s *input_metrics,
    struct topo_select_item_s *item,
    void **state);

topo_model_s struct

struct topo_model_s
{
    topo_model_init_func_t *init;
    topo_model_cleanup_func_t *cleanup;
    topo_model_journey_next_func_t *journey_next;
    topo_model_select_next_func_t *select_next;
};

[Nicolas Pouillon]

Bringing the discussion here

[Nicolas Pouillon]

• Fixing the recursion API, we needed the input port when walking
• Adding a selection API. Should be ala SQL select
  • a filter
  • an order
  • a limit
• Selection API still has to be modified
  • We still have to tell whether a node is better than another (a sorting function)

[Nicolas Pouillon]

Move selection function

[Nicolas Pouillon]

The node/model separation is exactly like the device/driver separation.

We should make topology a driver class. device <-> topo node bijection is then a subdevice handling.

We should merge this with device API rework ticket