Changes between Version 4 and Version 5 of Ticket #40


Ignore:
Timestamp:
Oct 31, 2010, 10:15:31 AM (14 years ago)
Author:
Nicolas Pouillon
Comment:

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

Legend:

Unmodified
Added
Removed
Modified

  • Ticket #40 – Description

    v4 v5  
    66  * [wiki:FlattenedDeviceTree FlattenedDeviceTrees]
    77  * ACPI
     8  * OpenFrimware
     9  * UEFI ?
    810 * Enumerate the platform
    911  * Component connection topology
    … …  
    5355
    5456{{{
    55 struct topo_model_s
    56 {
    57   void (*init)(struct topo_node_s *node, void *param);
    58   void (*cleanup)(struct topo_node_s *node);
    59 
    60   // A bunch of function pointers for operations follows, see below
    61 };
    62 }}}
    63 
    64 {{{
     57#!c
     58struct topo_model_s; // forward decl. see below
     59
    6560struct topo_node_s
    6661{
    67   struct topo_model_s *model; /// model handling this node
    68   void *priv;                 /// model's private data
    69   struct device_s *dev;       /// associated device, if any
     62    const struct topo_model_s *model; /// model handling this node
     63    void *priv;                 /// model's private data
     64    struct device_s *dev;       /// associated device, if any
    7065};
    7166
    … …  
    7772struct topo_port_s
    7873{
    79   struct topo_node_s *node;   // node owning the port
    80   void *private;              // port's private.
     74    const struct topo_node_s *node;   // node owning the port
     75    void *private;              // port's private.
    8176};
    8277}}}
    … …  
    8681== Device to node bijection ==
    8782
    88 struct device_s *topo_node_to_device(struct topo_node_s *node);
    89 
    90 struct topo_node_s *topo_device_to_node(struct device_s *dev);
     83{{{
     84#!c
     85struct device_s *topo_node_to_device(const struct topo_node_s *node);
     86
     87struct topo_node_s *topo_device_to_node(const struct device_s *dev);
     88}}}
    9189
    9290== Topology exploration ==
    … …  
    9997High level call which does the routing and accumulates '''round-trip''' metrics:
    10098{{{
     99#!c
    101100error_t topo_journey_metrics(
    102    struct topo_metrics_s *result,
    103    struct topo_node_s *start,
    104    struct topo_addr_s *dest);
     101    const struct topo_node_s *start,
     102    const struct topo_addr_s *dest,
     103    struct topo_metrics_s *result);
    105104}}}
    106105(round-trip is sufficient as there is roughly the same energy
    … …  
    112111
    113112{{{
     113#!c
    114114enum topo_addr_type_e
    115115{
    116   TOPO_ADDR_BUS;
     116    TOPO_ADDR_BUS;
     117    TOPO_ADDR_IRQ;
    117118};
    118119
    119120struct topo_addr_s
    120121{
    121   enum topo_addr_type_e type;
    122   union {
    123     struct {
    124       uintptr_t address;
    125     } bus;
    126   };
     122    enum topo_addr_type_e type;
     123    union {
     124        struct {
     125            uintptr_t address;
     126        } bus;
     127        struct {
     128            size_t line_no;
     129        } irq;
     130    };
    127131};
    128132}}}
    … …  
    130134Accumulated metrics describe the features of the walked path:
    131135{{{
     136#!c
    132137struct topo_metrics_s
    133138{
    134   uint32_t hop_count;
    135   uint32_t latency;          /// cycles ? us ?
    136   uint32_t max_byte_per_sec; /// capped max on path
    137   uint32_t power_per_byte;   /// overall consumption estimation
     139    size_t hop_count;
     140    uint32_t latency;          /// cycles ? µs ?
     141    uint32_t max_byte_per_sec; /// capped max on path
     142    uint32_t power_per_byte;   /// overall consumption estimation
    138143};
    139144}}}
    … …  
    142147
    143148{{{
     149#!c
    144150enum topo_crit_val_e
    145151{
    146   CRIT_DROP,   /// Node is not interesting, stop recursion here in the graph
    147   CRIT_RECURS, /// Node is not selected, but we can recurs through it
    148   CRIT_SELECT, /// Node is selected, and may be recursed down
     152    TOPO_CRIT_DROP,   /// Node is not interesting, stop recursion here in the graph
     153    TOPO_CRIT_RECURS, /// Node is not selected, but we can recurs through it
     154    TOPO_CRIT_SELECT, /// Node is selected, and may be recursed down
     155};
     156
     157enum topo_cmp_e
     158{
     159    TOPO_CMP_LEFT  = -1, /// left better than right
     160    TOPO_CMP_EQ    = 0,  /// left equals right
     161    TOPO_CMP_RIGHT = 1,  /// right better than left
     162};
     163
     164struct topo_select_item_s
     165{
     166    const struct topo_node_s    *node;
     167    struct topo_metrics_s metrics; // not a pointer !
    149168};
    150169
    151170/**
    152171  Selector function
    153   @param node Node to filter
    154   @param metrics Metrics from start node to this one
     172  @param item Node/metrics to filter
    155173  @param priv Selector private data
    156174  @returns whether the node is interesting
    157175*/
    158 typedef enum topo_crit_val_e crit_func_t(struct topo_node_s *node, struct topo_metrics_s *metrics, void *priv);
    159 
    160 error_t select(
    161    struct topo_node_s *start,          /// Start node
    162    crit_func_t *crit, void *crit_priv, /// Criterium function, telling whether a node is eligible
    163    size_t max_nodes,                   /// Maximal number of nodes to return
    164    struct topo_node_s **nodes);        /// Output nodes. Table must be allocated by caller and be able to contain max_nodes
     176typedef enum topo_crit_val_e topo_crit_func_t(
     177    const struct topo_select_item_s *item,
     178    const void *priv);
     179
     180/**
     181  Sort function
     182  @param left  Node/metrics to compare
     183  @param right Node/metrics to compare
     184  @param priv Sort private data
     185  @returns comparaison result
     186*/
     187typedef enum topo_cmp_e topo_sort_func_t(
     188    const struct topo_select_item_s *left,
     189    const struct topo_select_item_s *right,
     190    const void *priv);
     191
     192error_t topo_select(
     193    const struct topo_node_s *start,         /// Start node
     194    topo_crit_func_t *crit, const void *crit_priv, /// Criterium function, telling whether a node is eligible
     195    topo_sort_func_t *sort, const void *sort_priv, /// Sorting function, telling order of nodes
     196    size_t max_items,                   /// Maximal number of nodes to return
     197    struct topo_select_item_s *items);  /// Output nodes+metrics. Table must be allocated by caller and be able to contain @tt max_items
    165198}}}
    166199
    … …  
    168201
    169202{{{
    170 error_t next(
    171     struct topo_node_s *node,        /// node of our model where we are coming from
    172     struct topo_port_s *input,       /// input in node. May be NULL on start node
    173     const struct topo_addr_s *dest,  /// destination address for the current address space
    174     struct topo_metrics_s *metrics,  /// Metrics to update on the go
    175     struct topo_port_s **output_peer); /// Input port of the next hop
    176 
    177 error_t select_next(
    178     struct topo_node_s *node,        /// node of our model where we are coming from
    179     struct topo_port_s *input,       /// input in node. May be NULL on start node
    180     struct topo_metrics_s *metrics,  /// Metrics to update on the go
    181     struct topo_port_s **output_peer); /// Input port of the next hop
    182 }}}
    183 
    184 
    185 = Open questions =
    186 
    187  * Are edges of graph internal to node's private data or are explicit ?
    188  * How to handle multiple output connexions of the same addressing type ?
    189   * Maybe add an "output" index with source node ? (after source node, there should be no hesitation possible)
    190 
     203#!c
     204/**
     205 Initialize a topology node.
     206 */
     207typedef void topo_model_init_func_t(struct topo_node_s *node, const void *param);
     208
     209/**
     210 Destroy a topology node. Reclaim all associated memory
     211 */
     212typedef void topo_model_cleanup_func_t(struct topo_node_s *node);
     213
     214/**
     215 Compute routing and cost from this node to the next hop, routing
     216 towards a given destination
     217
     218 @param node Node of our model where we are coming from
     219 @param input Input port in node. May be NULL on start node
     220 @param dest Destination address for the current address space
     221 @param metrics Metrics to update on the go
     222 @param peer_input Input port of the next hop
     223 */
     224typedef error_t topo_model_journey_next_func_t(
     225    const struct topo_node_s *node,
     226    const struct topo_port_s *input,
     227    const struct topo_addr_s *dest,
     228    struct topo_metrics_s *metrics,
     229    struct topo_port_s *peer_input);
     230
     231/**
     232 Explore the topology graph. Each call to this function must return next
     233 valid port.
     234
     235 @param node Current node
     236 @param input Port where we came from, exploration should not "go back" to this edge. May be NULL on recursion start
     237 @param metrics Metrics up to this node
     238 @param item Returned item for next recursion
     239 @param state Pointer to a void* where select_next can store its internal state.
     240
     241 @tt *state is @tt NULL on first call for each node.
     242
     243 Successive calls to select_next for a given node in a given exploration use the same @tt state value.
     244
     245 @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.
     246 */
     247typedef error_t topo_model_select_next_func_t(
     248    const struct topo_node_s *node,
     249    const struct topo_port_s *input,
     250    const struct topo_metrics_s *input_metrics,
     251    struct topo_select_item_s *item,
     252    void **state);
     253}}}
     254
     255= topo_model_s struct =
     256
     257{{{
     258#!c
     259struct topo_model_s
     260{
     261    topo_model_init_func_t *init;
     262    topo_model_cleanup_func_t *cleanup;
     263    topo_model_journey_next_func_t *journey_next;
     264    topo_model_select_next_func_t *select_next;
     265};
     266}}}