lib/librte_graph/rte_graph_worker.h

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright(C) 2020 Marvell International Ltd.
   3  */
   4
   5 #ifndef _RTE_GRAPH_WORKER_H_
   6 #define _RTE_GRAPH_WORKER_H_
   7
   8 /**
   9  * @file rte_graph_worker.h
  10  *
  11  * @warning
  12  * @b EXPERIMENTAL: this API may change without prior notice
  13  *
  14  * This API allows a worker thread to walk over a graph and nodes to create,
  15  * process, enqueue and move streams of objects to the next nodes.
  16  */
  17
  18 #include <rte_common.h>
  19 #include <rte_cycles.h>
  20 #include <rte_prefetch.h>
  21 #include <rte_memcpy.h>
  22 #include <rte_memory.h>
  23
  24 #include "rte_graph.h"
  25
  26 #ifdef __cplusplus
  27 extern "C" {
  28 #endif
  29
  30 /**
  31  * @internal
  32  *
  33  * Data structure to hold graph data.
  34  */
  35 struct rte_graph {
  36         uint32_t tail;               /**< Tail of circular buffer. */
  37         uint32_t head;               /**< Head of circular buffer. */
  38         uint32_t cir_mask;           /**< Circular buffer wrap around mask. */
  39         rte_node_t nb_nodes;         /**< Number of nodes in the graph. */
  40         rte_graph_off_t *cir_start;  /**< Pointer to circular buffer. */
  41         rte_graph_off_t nodes_start; /**< Offset at which node memory starts. */
  42         rte_graph_t id; /**< Graph identifier. */
  43         int socket;     /**< Socket ID where memory is allocated. */
  44         char name[RTE_GRAPH_NAMESIZE];  /**< Name of the graph. */
  45         uint64_t fence;                 /**< Fence. */
  46 } __rte_cache_aligned;
  47
  48 /**
  49  * @internal
  50  *
  51  * Data structure to hold node data.
  52  */
  53 struct rte_node {
  54         /* Slow path area  */
  55         uint64_t fence;         /**< Fence. */
  56         rte_graph_off_t next;   /**< Index to next node. */
  57         rte_node_t id;          /**< Node identifier. */
  58         rte_node_t parent_id;   /**< Parent Node identifier. */
  59         rte_edge_t nb_edges;    /**< Number of edges from this node. */
  60         uint32_t realloc_count; /**< Number of times realloced. */
  61
  62         char parent[RTE_NODE_NAMESIZE]; /**< Parent node name. */
  63         char name[RTE_NODE_NAMESIZE];   /**< Name of the node. */
  64
  65         /* Fast path area  */
  66 #define RTE_NODE_CTX_SZ 16
  67         uint8_t ctx[RTE_NODE_CTX_SZ] __rte_cache_aligned; /**< Node Context. */
  68         uint16_t size;          /**< Total number of objects available. */
  69         uint16_t idx;           /**< Number of objects used. */
  70         rte_graph_off_t off;    /**< Offset of node in the graph reel. */
  71         uint64_t total_cycles;  /**< Cycles spent in this node. */
  72         uint64_t total_calls;   /**< Calls done to this node. */
  73         uint64_t total_objs;    /**< Objects processed by this node. */
  74         RTE_STD_C11
  75                 union {
  76                         void **objs;       /**< Array of object pointers. */
  77                         uint64_t objs_u64;
  78                 };
  79         RTE_STD_C11
  80                 union {
  81                         rte_node_process_t process; /**< Process function. */
  82                         uint64_t process_u64;
  83                 };
  84         struct rte_node *nodes[] __rte_cache_min_aligned; /**< Next nodes. */
  85 } __rte_cache_aligned;
  86
  87 /**
  88  * @internal
  89  *
  90  * Allocate a stream of objects.
  91  *
  92  * If stream already exists then re-allocate it to a larger size.
  93  *
  94  * @param graph
  95  *   Pointer to the graph object.
  96  * @param node
  97  *   Pointer to the node object.
  98  */
  99 __rte_experimental
 100 void __rte_node_stream_alloc(struct rte_graph *graph, struct rte_node *node);
 101
 102 /**
 103  * @internal
 104  *
 105  * Allocate a stream with requested number of objects.
 106  *
 107  * If stream already exists then re-allocate it to a larger size.
 108  *
 109  * @param graph
 110  *   Pointer to the graph object.
 111  * @param node
 112  *   Pointer to the node object.
 113  * @param req_size
 114  *   Number of objects to be allocated.
 115  */
 116 __rte_experimental
 117 void __rte_node_stream_alloc_size(struct rte_graph *graph,
 118                                   struct rte_node *node, uint16_t req_size);
 119
 120 /**
 121  * Perform graph walk on the circular buffer and invoke the process function
 122  * of the nodes and collect the stats.
 123  *
 124  * @param graph
 125  *   Graph pointer returned from rte_graph_lookup function.
 126  *
 127  * @see rte_graph_lookup()
 128  */
 129 __rte_experimental
 130 static inline void
 131 rte_graph_walk(struct rte_graph *graph)
 132 {
 133         const rte_graph_off_t *cir_start = graph->cir_start;
 134         const rte_node_t mask = graph->cir_mask;
 135         uint32_t head = graph->head;
 136         struct rte_node *node;
 137         uint64_t start;
 138         uint16_t rc;
 139         void **objs;
 140
 141         /*
 142          * Walk on the source node(s) ((cir_start - head) -> cir_start) and then
 143          * on the pending streams (cir_start -> (cir_start + mask) -> cir_start)
 144          * in a circular buffer fashion.
 145          *
 146          *      +-----+ <= cir_start - head [number of source nodes]
 147          *      |     |
 148          *      | ... | <= source nodes
 149          *      |     |
 150          *      +-----+ <= cir_start [head = 0] [tail = 0]
 151          *      |     |
 152          *      | ... | <= pending streams
 153          *      |     |
 154          *      +-----+ <= cir_start + mask
 155          */
 156         while (likely(head != graph->tail)) {
 157                 node = RTE_PTR_ADD(graph, cir_start[(int32_t)head++]);
 158                 RTE_ASSERT(node->fence == RTE_GRAPH_FENCE);
 159                 objs = node->objs;
 160                 rte_prefetch0(objs);
 161
 162                 if (rte_graph_has_stats_feature()) {
 163                         start = rte_rdtsc();
 164                         rc = node->process(graph, node, objs, node->idx);
 165                         node->total_cycles += rte_rdtsc() - start;
 166                         node->total_calls++;
 167                         node->total_objs += rc;
 168                 } else {
 169                         node->process(graph, node, objs, node->idx);
 170                 }
 171                 node->idx = 0;
 172                 head = likely((int32_t)head > 0) ? head & mask : head;
 173         }
 174         graph->tail = 0;
 175 }
 176
 177 /* Fast path helper functions */
 178
 179 /**
 180  * @internal
 181  *
 182  * Enqueue a given node to the tail of the graph reel.
 183  *
 184  * @param graph
 185  *   Pointer Graph object.
 186  * @param node
 187  *   Pointer to node object to be enqueued.
 188  */
 189 static __rte_always_inline void
 190 __rte_node_enqueue_tail_update(struct rte_graph *graph, struct rte_node *node)
 191 {
 192         uint32_t tail;
 193
 194         tail = graph->tail;
 195         graph->cir_start[tail++] = node->off;
 196         graph->tail = tail & graph->cir_mask;
 197 }
 198
 199 /**
 200  * @internal
 201  *
 202  * Enqueue sequence prologue function.
 203  *
 204  * Updates the node to tail of graph reel and resizes the number of objects
 205  * available in the stream as needed.
 206  *
 207  * @param graph
 208  *   Pointer to the graph object.
 209  * @param node
 210  *   Pointer to the node object.
 211  * @param idx
 212  *   Index at which the object enqueue starts from.
 213  * @param space
 214  *   Space required for the object enqueue.
 215  */
 216 static __rte_always_inline void
 217 __rte_node_enqueue_prologue(struct rte_graph *graph, struct rte_node *node,
 218                             const uint16_t idx, const uint16_t space)
 219 {
 220
 221         /* Add to the pending stream list if the node is new */
 222         if (idx == 0)
 223                 __rte_node_enqueue_tail_update(graph, node);
 224
 225         if (unlikely(node->size < (idx + space)))
 226                 __rte_node_stream_alloc(graph, node);
 227 }
 228
 229 /**
 230  * @internal
 231  *
 232  * Get the node pointer from current node edge id.
 233  *
 234  * @param node
 235  *   Current node pointer.
 236  * @param next
 237  *   Edge id of the required node.
 238  *
 239  * @return
 240  *   Pointer to the node denoted by the edge id.
 241  */
 242 static __rte_always_inline struct rte_node *
 243 __rte_node_next_node_get(struct rte_node *node, rte_edge_t next)
 244 {
 245         RTE_ASSERT(next < node->nb_edges);
 246         RTE_ASSERT(node->fence == RTE_GRAPH_FENCE);
 247         node = node->nodes[next];
 248         RTE_ASSERT(node->fence == RTE_GRAPH_FENCE);
 249
 250         return node;
 251 }
 252
 253 /**
 254  * Enqueue the objs to next node for further processing and set
 255  * the next node to pending state in the circular buffer.
 256  *
 257  * @param graph
 258  *   Graph pointer returned from rte_graph_lookup().
 259  * @param node
 260  *   Current node pointer.
 261  * @param next
 262  *   Relative next node index to enqueue objs.
 263  * @param objs
 264  *   Objs to enqueue.
 265  * @param nb_objs
 266  *   Number of objs to enqueue.
 267  */
 268 __rte_experimental
 269 static inline void
 270 rte_node_enqueue(struct rte_graph *graph, struct rte_node *node,
 271                  rte_edge_t next, void **objs, uint16_t nb_objs)
 272 {
 273         node = __rte_node_next_node_get(node, next);
 274         const uint16_t idx = node->idx;
 275
 276         __rte_node_enqueue_prologue(graph, node, idx, nb_objs);
 277
 278         rte_memcpy(&node->objs[idx], objs, nb_objs * sizeof(void *));
 279         node->idx = idx + nb_objs;
 280 }
 281
 282 /**
 283  * Enqueue only one obj to next node for further processing and
 284  * set the next node to pending state in the circular buffer.
 285  *
 286  * @param graph
 287  *   Graph pointer returned from rte_graph_lookup().
 288  * @param node
 289  *   Current node pointer.
 290  * @param next
 291  *   Relative next node index to enqueue objs.
 292  * @param obj
 293  *   Obj to enqueue.
 294  */
 295 __rte_experimental
 296 static inline void
 297 rte_node_enqueue_x1(struct rte_graph *graph, struct rte_node *node,
 298                     rte_edge_t next, void *obj)
 299 {
 300         node = __rte_node_next_node_get(node, next);
 301         uint16_t idx = node->idx;
 302
 303         __rte_node_enqueue_prologue(graph, node, idx, 1);
 304
 305         node->objs[idx++] = obj;
 306         node->idx = idx;
 307 }
 308
 309 /**
 310  * Enqueue only two objs to next node for further processing and
 311  * set the next node to pending state in the circular buffer.
 312  * Same as rte_node_enqueue_x1 but enqueue two objs.
 313  *
 314  * @param graph
 315  *   Graph pointer returned from rte_graph_lookup().
 316  * @param node
 317  *   Current node pointer.
 318  * @param next
 319  *   Relative next node index to enqueue objs.
 320  * @param obj0
 321  *   Obj to enqueue.
 322  * @param obj1
 323  *   Obj to enqueue.
 324  */
 325 __rte_experimental
 326 static inline void
 327 rte_node_enqueue_x2(struct rte_graph *graph, struct rte_node *node,
 328                     rte_edge_t next, void *obj0, void *obj1)
 329 {
 330         node = __rte_node_next_node_get(node, next);
 331         uint16_t idx = node->idx;
 332
 333         __rte_node_enqueue_prologue(graph, node, idx, 2);
 334
 335         node->objs[idx++] = obj0;
 336         node->objs[idx++] = obj1;
 337         node->idx = idx;
 338 }
 339
 340 /**
 341  * Enqueue only four objs to next node for further processing and
 342  * set the next node to pending state in the circular buffer.
 343  * Same as rte_node_enqueue_x1 but enqueue four objs.
 344  *
 345  * @param graph
 346  *   Graph pointer returned from rte_graph_lookup().
 347  * @param node
 348  *   Current node pointer.
 349  * @param next
 350  *   Relative next node index to enqueue objs.
 351  * @param obj0
 352  *   1st obj to enqueue.
 353  * @param obj1
 354  *   2nd obj to enqueue.
 355  * @param obj2
 356  *   3rd obj to enqueue.
 357  * @param obj3
 358  *   4th obj to enqueue.
 359  */
 360 __rte_experimental
 361 static inline void
 362 rte_node_enqueue_x4(struct rte_graph *graph, struct rte_node *node,
 363                     rte_edge_t next, void *obj0, void *obj1, void *obj2,
 364                     void *obj3)
 365 {
 366         node = __rte_node_next_node_get(node, next);
 367         uint16_t idx = node->idx;
 368
 369         __rte_node_enqueue_prologue(graph, node, idx, 4);
 370
 371         node->objs[idx++] = obj0;
 372         node->objs[idx++] = obj1;
 373         node->objs[idx++] = obj2;
 374         node->objs[idx++] = obj3;
 375         node->idx = idx;
 376 }
 377
 378 /**
 379  * Enqueue objs to multiple next nodes for further processing and
 380  * set the next nodes to pending state in the circular buffer.
 381  * objs[i] will be enqueued to nexts[i].
 382  *
 383  * @param graph
 384  *   Graph pointer returned from rte_graph_lookup().
 385  * @param node
 386  *   Current node pointer.
 387  * @param nexts
 388  *   List of relative next node indices to enqueue objs.
 389  * @param objs
 390  *   List of objs to enqueue.
 391  * @param nb_objs
 392  *   Number of objs to enqueue.
 393  */
 394 __rte_experimental
 395 static inline void
 396 rte_node_enqueue_next(struct rte_graph *graph, struct rte_node *node,
 397                       rte_edge_t *nexts, void **objs, uint16_t nb_objs)
 398 {
 399         uint16_t i;
 400
 401         for (i = 0; i < nb_objs; i++)
 402                 rte_node_enqueue_x1(graph, node, nexts[i], objs[i]);
 403 }
 404
 405 /**
 406  * Get the stream of next node to enqueue the objs.
 407  * Once done with the updating the objs, needs to call
 408  * rte_node_next_stream_put to put the next node to pending state.
 409  *
 410  * @param graph
 411  *   Graph pointer returned from rte_graph_lookup().
 412  * @param node
 413  *   Current node pointer.
 414  * @param next
 415  *   Relative next node index to get stream.
 416  * @param nb_objs
 417  *   Requested free size of the next stream.
 418  *
 419  * @return
 420  *   Valid next stream on success.
 421  *
 422  * @see rte_node_next_stream_put().
 423  */
 424 __rte_experimental
 425 static inline void **
 426 rte_node_next_stream_get(struct rte_graph *graph, struct rte_node *node,
 427                          rte_edge_t next, uint16_t nb_objs)
 428 {
 429         node = __rte_node_next_node_get(node, next);
 430         const uint16_t idx = node->idx;
 431         uint16_t free_space = node->size - idx;
 432
 433         if (unlikely(free_space < nb_objs))
 434                 __rte_node_stream_alloc_size(graph, node, nb_objs);
 435
 436         return &node->objs[idx];
 437 }
 438
 439 /**
 440  * Put the next stream to pending state in the circular buffer
 441  * for further processing. Should be invoked after rte_node_next_stream_get().
 442  *
 443  * @param graph
 444  *   Graph pointer returned from rte_graph_lookup().
 445  * @param node
 446  *   Current node pointer.
 447  * @param next
 448  *   Relative next node index..
 449  * @param idx
 450  *   Number of objs updated in the stream after getting the stream using
 451  *   rte_node_next_stream_get.
 452  *
 453  * @see rte_node_next_stream_get().
 454  */
 455 __rte_experimental
 456 static inline void
 457 rte_node_next_stream_put(struct rte_graph *graph, struct rte_node *node,
 458                          rte_edge_t next, uint16_t idx)
 459 {
 460         if (unlikely(!idx))
 461                 return;
 462
 463         node = __rte_node_next_node_get(node, next);
 464         if (node->idx == 0)
 465                 __rte_node_enqueue_tail_update(graph, node);
 466
 467         node->idx += idx;
 468 }
 469
 470 /**
 471  * Home run scenario, Enqueue all the objs of current node to next
 472  * node in optimized way by swapping the streams of both nodes.
 473  * Performs good when next node is already not in pending state.
 474  * If next node is already in pending state then normal enqueue
 475  * will be used.
 476  *
 477  * @param graph
 478  *   Graph pointer returned from rte_graph_lookup().
 479  * @param src
 480  *   Current node pointer.
 481  * @param next
 482  *   Relative next node index.
 483  */
 484 __rte_experimental
 485 static inline void
 486 rte_node_next_stream_move(struct rte_graph *graph, struct rte_node *src,
 487                           rte_edge_t next)
 488 {
 489         struct rte_node *dst = __rte_node_next_node_get(src, next);
 490
 491         /* Let swap the pointers if dst don't have valid objs */
 492         if (likely(dst->idx == 0)) {
 493                 void **dobjs = dst->objs;
 494                 uint16_t dsz = dst->size;
 495                 dst->objs = src->objs;
 496                 dst->size = src->size;
 497                 src->objs = dobjs;
 498                 src->size = dsz;
 499                 dst->idx = src->idx;
 500                 __rte_node_enqueue_tail_update(graph, dst);
 501         } else { /* Move the objects from src node to dst node */
 502                 rte_node_enqueue(graph, src, next, src->objs, src->idx);
 503         }
 504 }
 505
 506 #ifdef __cplusplus
 507 }
 508 #endif
 509
 510 #endif /* _RTE_GRAPH_WORKER_H_ */