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