id	summary	reporter	owner	description	type	status	priority	milestone	component	resolution	keywords	cc
40	Add a topology description API	Nicolas Pouillon	Nicolas Pouillon	"= Overview =

== Goals ==

 * Abstract the low-level description APIs
  * [wiki:FlattenedDeviceTree 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 ==

{{{
#!c
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 ==

{{{
#!c
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:
{{{
#!c
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, …

{{{
#!c
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:
{{{
#!c
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 ==

{{{
#!c
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 ==

{{{
#!c
/**
 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 =

{{{
#!c
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;
};
}}}
"	task	new	major	Topology handling	drivers