1.. SPDX-License-Identifier: BSD-3-Clause 2 Copyright(C) 2020 Marvell International Ltd. 3 4Graph Library and Inbuilt Nodes 5=============================== 6 7Graph architecture abstracts the data processing functions as a ``node`` and 8``links`` them together to create a complex ``graph`` to enable reusable/modular 9data processing functions. 10 11The graph library provides API to enable graph framework operations such as 12create, lookup, dump and destroy on graph and node operations such as clone, 13edge update, and edge shrink, etc. The API also allows to create the stats 14cluster to monitor per graph and per node stats. 15 16Features 17-------- 18 19Features of the Graph library are: 20 21- Nodes as plugins. 22- Support for out of tree nodes. 23- Inbuilt nodes for packet processing. 24- Multi-process support. 25- Low overhead graph walk and node enqueue. 26- Low overhead statistics collection infrastructure. 27- Support to export the graph as a Graphviz dot file. See ``rte_graph_export()``. 28- Allow having another graph walk implementation in the future by segregating 29 the fast path(``rte_graph_worker.h``) and slow path code. 30 31Advantages of Graph architecture 32-------------------------------- 33 34- Memory latency is the enemy for high-speed packet processing, moving the 35 similar packet processing code to a node will reduce the I cache and D 36 caches misses. 37- Exploits the probability that most packets will follow the same nodes in the 38 graph. 39- Allow SIMD instructions for packet processing of the node.- 40- The modular scheme allows having reusable nodes for the consumers. 41- The modular scheme allows us to abstract the vendor HW specific 42 optimizations as a node. 43 44Performance tuning parameters 45----------------------------- 46 47- Test with various burst size values (256, 128, 64, 32) using 48 RTE_GRAPH_BURST_SIZE config option. 49 The testing shows, on x86 and arm64 servers, The sweet spot is 256 burst 50 size. While on arm64 embedded SoCs, it is either 64 or 128. 51- Disable node statistics (using ``RTE_LIBRTE_GRAPH_STATS`` config option) 52 if not needed. 53 54Programming model 55----------------- 56 57Anatomy of Node: 58~~~~~~~~~~~~~~~~ 59 60.. _figure_anatomy_of_a_node: 61 62.. figure:: img/anatomy_of_a_node.* 63 64The :numref:`figure_anatomy_of_a_node` diagram depicts the anatomy of a node. 65 66The node is the basic building block of the graph framework. 67 68A node consists of: 69 70process(): 71^^^^^^^^^^ 72 73The callback function will be invoked by worker thread using 74``rte_graph_walk()`` function when there is data to be processed by the node. 75A graph node process the function using ``process()`` and enqueue to next 76downstream node using ``rte_node_enqueue*()`` function. 77 78Context memory: 79^^^^^^^^^^^^^^^ 80 81It is memory allocated by the library to store the node-specific context 82information. This memory will be used by process(), init(), fini() callbacks. 83 84init(): 85^^^^^^^ 86 87The callback function will be invoked by ``rte_graph_create()`` on when 88a node gets attached to a graph. 89 90fini(): 91^^^^^^^ 92 93The callback function will be invoked by ``rte_graph_destroy()`` on when a 94node gets detached to a graph. 95 96Node name: 97^^^^^^^^^^ 98 99It is the name of the node. When a node registers to graph library, the library 100gives the ID as ``rte_node_t`` type. Both ID or Name shall be used lookup the 101node. ``rte_node_from_name()``, ``rte_node_id_to_name()`` are the node 102lookup functions. 103 104nb_edges: 105^^^^^^^^^ 106 107The number of downstream nodes connected to this node. The ``next_nodes[]`` 108stores the downstream nodes objects. ``rte_node_edge_update()`` and 109``rte_node_edge_shrink()`` functions shall be used to update the ``next_node[]`` 110objects. Consumers of the node APIs are free to update the ``next_node[]`` 111objects till ``rte_graph_create()`` invoked. 112 113next_node[]: 114^^^^^^^^^^^^ 115 116The dynamic array to store the downstream nodes connected to this node. Downstream 117node should not be current node itself or a source node. 118 119Source node: 120^^^^^^^^^^^^ 121 122Source nodes are static nodes created using ``RTE_NODE_REGISTER`` by passing 123``flags`` as ``RTE_NODE_SOURCE_F``. 124While performing the graph walk, the ``process()`` function of all the source 125nodes will be called first. So that these nodes can be used as input nodes for a graph. 126 127Node creation and registration 128~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 129* Node implementer creates the node by implementing ops and attributes of 130 ``struct rte_node_register``. 131 132* The library registers the node by invoking RTE_NODE_REGISTER on library load 133 using the constructor scheme. The constructor scheme used here to support multi-process. 134 135Link the Nodes to create the graph topology 136~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 137.. _figure_link_the_nodes: 138 139.. figure:: img/link_the_nodes.* 140 141The :numref:`figure_link_the_nodes` diagram shows a graph topology after 142linking the N nodes. 143 144Once nodes are available to the program, Application or node public API 145functions can links them together to create a complex packet processing graph. 146 147There are multiple different types of strategies to link the nodes. 148 149Method (a): 150^^^^^^^^^^^ 151Provide the ``next_nodes[]`` at the node registration time. See ``struct rte_node_register::nb_edges``. 152This is a use case to address the static node scheme where one knows upfront the 153``next_nodes[]`` of the node. 154 155Method (b): 156^^^^^^^^^^^ 157Use ``rte_node_edge_get()``, ``rte_node_edge_update()``, ``rte_node_edge_shrink()`` 158to update the ``next_nodes[]`` links for the node runtime but before graph create. 159 160Method (c): 161^^^^^^^^^^^ 162Use ``rte_node_clone()`` to clone a already existing node, created using RTE_NODE_REGISTER. 163When ``rte_node_clone()`` invoked, The library, would clone all the attributes 164of the node and creates a new one. The name for cloned node shall be 165``"parent_node_name-user_provided_name"``. 166 167This method enables the use case of Rx and Tx nodes where multiple of those nodes 168need to be cloned based on the number of CPU available in the system. 169The cloned nodes will be identical, except the ``"context memory"``. 170Context memory will have information of port, queue pair in case of Rx and Tx 171ethdev nodes. 172 173Create the graph object 174~~~~~~~~~~~~~~~~~~~~~~~ 175Now that the nodes are linked, Its time to create a graph by including 176the required nodes. The application can provide a set of node patterns to 177form a graph object. The ``famish()`` API used underneath for the pattern 178matching to include the required nodes. After the graph create any changes to 179nodes or graph is not allowed. 180 181The ``rte_graph_create()`` API shall be used to create the graph. 182 183Example of a graph object creation: 184 185.. code-block:: console 186 187 {"ethdev_rx-0-0", ip4*, ethdev_tx-*"} 188 189In the above example, A graph object will be created with ethdev Rx 190node of port 0 and queue 0, all ipv4* nodes in the system, 191and ethdev tx node of all ports. 192 193Multicore graph processing 194~~~~~~~~~~~~~~~~~~~~~~~~~~ 195In the current graph library implementation, specifically, 196``rte_graph_walk()`` and ``rte_node_enqueue*`` fast path API functions 197are designed to work on single-core to have better performance. 198The fast path API works on graph object, So the multi-core graph 199processing strategy would be to create graph object PER WORKER. 200 201In fast path 202~~~~~~~~~~~~ 203Typical fast-path code looks like below, where the application 204gets the fast-path graph object using ``rte_graph_lookup()`` 205on the worker thread and run the ``rte_graph_walk()`` in a tight loop. 206 207.. code-block:: c 208 209 struct rte_graph *graph = rte_graph_lookup("worker0"); 210 211 while (!done) { 212 rte_graph_walk(graph); 213 } 214 215Context update when graph walk in action 216~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 217The fast-path object for the node is ``struct rte_node``. 218 219It may be possible that in slow-path or after the graph walk-in action, 220the user needs to update the context of the node hence access to 221``struct rte_node *`` memory. 222 223``rte_graph_foreach_node()``, ``rte_graph_node_get()``, 224``rte_graph_node_get_by_name()`` APIs can be used to to get the 225``struct rte_node*``. ``rte_graph_foreach_node()`` iterator function works on 226``struct rte_graph *`` fast-path graph object while others works on graph ID or name. 227 228Get the node statistics using graph cluster 229~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 230The user may need to know the aggregate stats of the node across 231multiple graph objects. Especially the situation where each graph object bound 232to a worker thread. 233 234Introduced a graph cluster object for statistics. 235``rte_graph_cluster_stats_create()`` API shall be used for creating a 236graph cluster with multiple graph objects and ``rte_graph_cluster_stats_get()`` 237to get the aggregate node statistics. 238 239An example statistics output from ``rte_graph_cluster_stats_get()`` 240 241.. code-block:: diff 242 243 +---------+-----------+-------------+---------------+-----------+---------------+-----------+ 244 |Node |calls |objs |realloc_count |objs/call |objs/sec(10E6) |cycles/call| 245 +---------------------+-------------+---------------+-----------+---------------+-----------+ 246 |node0 |12977424 |3322220544 |5 |256.000 |3047.151872 |20.0000 | 247 |node1 |12977653 |3322279168 |0 |256.000 |3047.210496 |17.0000 | 248 |node2 |12977696 |3322290176 |0 |256.000 |3047.221504 |17.0000 | 249 |node3 |12977734 |3322299904 |0 |256.000 |3047.231232 |17.0000 | 250 |node4 |12977784 |3322312704 |1 |256.000 |3047.243776 |17.0000 | 251 |node5 |12977825 |3322323200 |0 |256.000 |3047.254528 |17.0000 | 252 +---------+-----------+-------------+---------------+-----------+---------------+-----------+ 253 254Node writing guidelines 255~~~~~~~~~~~~~~~~~~~~~~~ 256 257The ``process()`` function of a node is the fast-path function and that needs 258to be written carefully to achieve max performance. 259 260Broadly speaking, there are two different types of nodes. 261 262Static nodes 263~~~~~~~~~~~~ 264The first kind of nodes are those that have a fixed ``next_nodes[]`` for the 265complete burst (like ethdev_rx, ethdev_tx) and it is simple to write. 266``process()`` function can move the obj burst to the next node either using 267``rte_node_next_stream_move()`` or using ``rte_node_next_stream_get()`` and 268``rte_node_next_stream_put()``. 269 270Intermediate nodes 271~~~~~~~~~~~~~~~~~~ 272The second kind of such node is ``intermediate nodes`` that decide what is the 273``next_node[]`` to send to on a per-packet basis. In these nodes, 274 275* Firstly, there has to be the best possible packet processing logic. 276 277* Secondly, each packet needs to be queued to its next node. 278 279This can be done using ``rte_node_enqueue_[x1|x2|x4]()`` APIs if 280they are to single next or ``rte_node_enqueue_next()`` that takes array of nexts. 281 282In scenario where multiple intermediate nodes are present but most of the time 283each node using the same next node for all its packets, the cost of moving every 284pointer from current node's stream to next node's stream could be avoided. 285This is called home run and ``rte_node_next_stream_move()`` could be used to 286just move stream from the current node to the next node with least number of cycles. 287Since this can be avoided only in the case where all the packets are destined 288to the same next node, node implementation should be also having worst-case 289handling where every packet could be going to different next node. 290 291Example of intermediate node implementation with home run: 292^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 2931. Start with speculation that next_node = node->ctx. 294This could be the next_node application used in the previous function call of this node. 295 2962. Get the next_node stream array with required space using 297``rte_node_next_stream_get(next_node, space)``. 298 2993. while n_left_from > 0 (i.e packets left to be sent) prefetch next pkt_set 300and process current pkt_set to find their next node 301 3024. if all the next nodes of the current pkt_set match speculated next node, 303just count them as successfully speculated(``last_spec``) till now and 304continue the loop without actually moving them to the next node. else if there is 305a mismatch, copy all the pkt_set pointers that were ``last_spec`` and move the 306current pkt_set to their respective next's nodes using ``rte_enqueue_next_x1()``. 307Also, one of the next_node can be updated as speculated next_node if it is more 308probable. Finally, reset ``last_spec`` to zero. 309 3105. if n_left_from != 0 then goto 3) to process remaining packets. 311 3126. if last_spec == nb_objs, All the objects passed were successfully speculated 313to single next node. So, the current stream can be moved to next node using 314``rte_node_next_stream_move(node, next_node)``. 315This is the ``home run`` where memcpy of buffer pointers to next node is avoided. 316 3177. Update the ``node->ctx`` with more probable next node. 318 319Graph object memory layout 320-------------------------- 321.. _figure_graph_mem_layout: 322 323.. figure:: img/graph_mem_layout.* 324 325The :numref:`figure_graph_mem_layout` diagram shows ``rte_graph`` object memory 326layout. Understanding the memory layout helps to debug the graph library and 327improve the performance if needed. 328 329Graph object consists of a header, circular buffer to store the pending 330stream when walking over the graph, and variable-length memory to store 331the ``rte_node`` objects. 332 333The graph_nodes_mem_create() creates and populate this memory. The functions 334such as ``rte_graph_walk()`` and ``rte_node_enqueue_*`` use this memory 335to enable fastpath services. 336 337Inbuilt Nodes 338------------- 339 340DPDK provides a set of nodes for data processing. The following section 341details the documentation for the same. 342 343ethdev_rx 344~~~~~~~~~ 345This node does ``rte_eth_rx_burst()`` into stream buffer passed to it 346(src node stream) and does ``rte_node_next_stream_move()`` only when 347there are packets received. Each ``rte_node`` works only on one Rx port and 348queue that it gets from node->ctx. For each (port X, rx_queue Y), 349a rte_node is cloned from ethdev_rx_base_node as ``ethdev_rx-X-Y`` in 350``rte_node_eth_config()`` along with updating ``node->ctx``. 351Each graph needs to be associated with a unique rte_node for a (port, rx_queue). 352 353ethdev_tx 354~~~~~~~~~ 355This node does ``rte_eth_tx_burst()`` for a burst of objs received by it. 356It sends the burst to a fixed Tx Port and Queue information from 357node->ctx. For each (port X), this ``rte_node`` is cloned from 358ethdev_tx_node_base as "ethdev_tx-X" in ``rte_node_eth_config()`` 359along with updating node->context. 360 361Since each graph doesn't need more than one Txq, per port, a Txq is assigned 362based on graph id to each rte_node instance. Each graph needs to be associated 363with a rte_node for each (port). 364 365pkt_drop 366~~~~~~~~ 367This node frees all the objects passed to it considering them as 368``rte_mbufs`` that need to be freed. 369 370ip4_lookup 371~~~~~~~~~~ 372This node is an intermediate node that does LPM lookup for the received 373ipv4 packets and the result determines each packets next node. 374 375On successful LPM lookup, the result contains the ``next_node`` id and 376``next-hop`` id with which the packet needs to be further processed. 377 378On LPM lookup failure, objects are redirected to pkt_drop node. 379``rte_node_ip4_route_add()`` is control path API to add ipv4 routes. 380To achieve home run, node use ``rte_node_stream_move()`` as mentioned in above 381sections. 382 383ip4_rewrite 384~~~~~~~~~~~ 385This node gets packets from ``ip4_lookup`` node with next-hop id for each 386packet is embedded in ``node_mbuf_priv1(mbuf)->nh``. This id is used 387to determine the L2 header to be written to the packet before sending 388the packet out to a particular ethdev_tx node. 389``rte_node_ip4_rewrite_add()`` is control path API to add next-hop info. 390 391null 392~~~~ 393This node ignores the set of objects passed to it and reports that all are 394processed. 395