[dpdk-dev] [RFC PATCH 0/5] graph: introduce graph subsystem

[<jerinj@marvell.com>]

From: Jerin Jacob <jerinj@marvell.com>

This RFC is targeted for v20.05 release.

This RFC patch includes an implementation of graph architecture for packet
processing using DPDK primitives.

Using graph traversal for packet processing is a proven architecture
that has been implemented in various open source libraries.

Graph architecture for packet processing enables abstracting the data
processing functions as “nodes” and “links” them together to create a complex
“graph” to create reusable/modular data processing functions. 

The RFC patch further includes performance enhancements and modularity
to the DPDK as discussed in more detail below.

What this RFC patch contains:
-----------------------------
1) The API definition to "create" nodes and "link" together to create a "graph"
for packet processing. See, lib/librte_graph/rte_graph.h  

2) The Fast path API definition for the graph walker and enqueue function
used by the workers. See, lib/librte_graph/rte_graph_worker.h

3) Optimized SW implementation for (1) and (2). See, lib/librte_graph/

4) Test case to verify the graph infrastructure functionality
See, app/test/test_graph.c
 
5) Performance test cases to evaluate the cost of graph walker and nodes
enqueue fast-path function for various combinations.

See app/test/test_graph_perf.c

6) Packet processing nodes(Null, Rx, Tx, Pkt drop, IPV4 rewrite, IPv4 lookup)
using graph infrastructure. See lib/librte_node/*

7) An example application to showcase l3fwd
(functionality same as existing examples/l3fwd) using graph infrastructure and
use packets processing nodes (item (6)). See examples/l3fwd-graph/.

Performance
-----------
1) Graph walk and node enqueue overhead can be tested with performance test
case application [1]
# If all packets go from a node to another node (we call it as "homerun") then
it will be just a pointer swap for a burst of packets.
# In the worst case, a couple of handful cycles to move an object from a node
to another node.

2) Performance comparison with existing l3fwd (The complete static code with out
any nodes) vs modular l3fwd-graph with 5 nodes
(ip4_lookup, ip4_rewrite, ethdev_tx, ethdev_rx, pkt_drop).
Here is graphical representation of the l3fwd-graph as Graphviz dot file: 
http://bit.ly/39UPPGm

# l3fwd-graph performance is -2.5% wrt static l3fwd.

# We have simulated the similar test with existing librte_pipeline application [4].
ip_pipline application is -48.62% wrt static l3fwd.

The above results are on octeontx2. It may vary on other platforms.
The platforms with higher L1 and L2 caches will have further better performance.

Tested architectures:
--------------------
1) AArch64
2) X86


Graph library Features
----------------------
1) Nodes as plugins
2) Support for out of tree nodes
3) Multi-process support.
4) Low overhead graph walk and node enqueue
5) Low overhead statistics collection infrastructure
6) Support to export the graph as a Graphviz dot file.
See rte_graph_export()
Example of exported graph: http://bit.ly/2PqbqOy
7) Allow having another graph walk implementation
in the future by segregating the fast path and slow path code.


Advantages of Graph architecture:
---------------------------------

1) Memory latency is the enemy for high-speed packet processing,
moving the similar packet processing code to a node will reduce
the I cache and D caches misses.
2) Exploits the probability that most packets will follow the same nodes in the graph.
3) Allow SIMD instructions for packet processing of the node.
4) The modular scheme allows having reusable nodes for the consumers.
5) The modular scheme allows us to abstract the vendor HW specific
optimizations as a node.


What is different than existing libpipeline library
---------------------------------------------------
At a very high level, libpipeline created to allow modular plugin interface.
Based on our analysis the performance is better in the graph model.
Check the details under the Performance section, Item (2).

This rte_graph implementation has taken care of fixing some of the
architecture/implementations limitations with libpipeline.

1) Use cases like IP fragmentation, TCP ACK processing
(with new TCP data sent out in the same context) 
have a problem as rte_pipeline_run() passes just pkt_mask of 64 bits to different
tables and packet pointers are stored in the single array in struct rte_pipeline_run.

In Graph architecture, The node has complete control of how many packets are
output to next node seamlessly.

2) Since pktmask is passed to different tables, it takes multiple for loops to
extract pkts out of fragmented pkts_mask. This makes it difficult to prefetch
ahead a set of packets. This issue does not exist in Graph architecture.

3) Every table have two/three function pointers unlike graph architecture that
has a single function pointer for node.

4) The current libpipeline main fast-path function doesn't support tree-like
topology where 64 packets can be redirected to 64 different tables.
It is currently limited to table-based next table id instead of per-packet
action based next table id. So in a typical case, we need to cascade tables and
sequentially go through all the tables to reach the last table.

5) pkt_mask limit is 64 bits which is the max burst size possible.
The graph library supports up to 256.

In short, both are significantly different architectures.
Allowing the end-user to choose the model would be a more appropriate decision
by keeping both in DPDK.
               

Why this RFC
------------
1) We believe, Graph architecture provides the best performance for 
reusable/modular packet processing framework.
Since DPDK does not have it, it is good to have it in DPDK.

2) Based on our experience, NPU HW accelerates are so different than one vendor 
to another vendor. Going forward, We believe, API abstraction may not be enough
abstract the difference in HW. The Vendor-specific nodes can abstract the HW
differences and reuse generic the nodes as needed.
This would help both the silicon vendors and DPDK end users.

3) The framework enables the protocol stack as use native mbuf for
graph processing to avoid any conversion between the formats for
better performance.

4) DPDK becomes the "goto library" for userspace HW acceleration.
It is good to have native Graph packet processing library in DPDK.

5) Obviously, Our customers are interested in Graph library in DPDK :-)

Identified tweaking for better performance on different targets
---------------------------------------------------------------
1) Test with various burst size values (256, 128, 64, 32) using
CONFIG_RTE_GRAPH_BURST_SIZE config option.
Based on our testing, on x86 and arm64 servers, The sweet spot is 256 burst size.
While on arm64 embedded SoCs, it is either 64 or 128.

2) Disable node statistics (use CONFIG_RTE_LIBRTE_GRAPH_STATS config option)
if not needed.

3) Use arm64 optimized memory copy for arm64 architecture by
selecting CONFIG_RTE_ARCH_ARM64_MEMCPY. 

Commands to run tests
---------------------

[1] 
perf test:
echo "graph_perf_autotest" | sudo ./build/app/test/dpdk-test -c 0x30

[2]
functionality test:
echo "graph_autotest" | sudo ./build/app/test/dpdk-test -c 0x30

[3]
l3fwd-graph:
./l3fwd-graph -c 0x100  -- -p 0x3 --config="(0, 0, 8)" -P

[4]
# ./ip_pipeline --c 0xff0000 -- -s route.cli

Route.cli: (Copy paste to the shell to avoid dos format issues)

https://pastebin.com/raw/B4Ktx7TT


Next steps
-----------------------------
1) Feedback from the community on the library.
2) Collect the API requirements from the community.
3) Sending the next version by addressing the community initial.
feedback and fixing the following identified "pending items".

 
Pending items (Will be addressed in next revision)
-------------------------------------------------
1) Add documentation as a patch
2) Add Doxygen API documentation
3) Split the patches at a more logical level for a better review.
4) code cleanup
5) more optimizations in the nodes and graph infrastructure.


Programming guide and API walk-through
--------------------------------------
# Anatomy of Node:
~~~~~~~~~~~~~~~~~
See the https://github.com/jerinjacobk/share/blob/master/Anatomy_of_a_node.svg

The above diagram depicts the anatomy of a node.
The node is the basic building block of the graph framework.

A node consists of:
a) process():

The callback function will be invoked by worker thread using
rte_graph_walk() function when there is data to be processed by the node.
A graph node process the function using process() and enqueue to next
downstream node using rte_node_enqueue*() function.

b) Context memory:  

It is memory allocated by the library to store the node-specific context
information. which will be used by process(), init(), fini() callbacks.

c) init():

The callback function which will be invoked by rte_graph_create() on when a node 
gets attached to a graph.

d) fini():

The callback function which will be invoked by rte_graph_destroy() on when a node 
gets detached to a graph.


e) Node name:

It is the name of the node. When a node registers to graph library, the library 
gives the ID as rte_node_t type. Both ID or Name shall be used lookup the node.
rte_node_from_name(), rte_node_id_to_name() are the node lookup functions.

f) nb_edges:

Number of downstream nodes connected to this node. The next_nodes[] stores the
downstream nodes objects. rte_node_edge_update() and rte_node_edge_shrink()
functions shall be used to update the next_node[] objects. Consumers of the node
APIs are free to update the next_node[] objects till rte_graph_create() invoked.

g) next_node[]:

The dynamic array to store the downstream nodes connected to this node.


# Node creation and registration
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a) Node implementer creates the node by implementing ops and attributes of
'struct rte_node_register'
b) The library registers the node by invoking RTE_NODE_REGISTER on library load
using the constructor scheme.
The constructor scheme used here to support multi-process.


# Link the Nodes to create the graph topology
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
See the https://github.com/jerinjacobk/share/blob/master/Link_the_nodes.svg

The above diagram shows a graph topology after linking the N nodes.

Once nodes are available to the program, Application or node public API functions
can links them together to create a complex packet processing graph.

There are multiple different types of strategies to link the nodes.

Method a) Provide the next_nodes[] at the node registration time.
See  'struct rte_node_register::nb_edges'. This is a use case to address the static
node scheme where one knows upfront the next_nodes[] of the node.

Method b) Use rte_node_edge_get(), rte_node_edge_update(), rte_node_edge_shrink() to
Update the next_nodes[] links for the node dynamically.

Method c) Use rte_node_clone() to clone a already existing node.
When rte_node_clone() invoked, The library, would clone all the attributes
of the node and creates a new one. The name for cloned node shall be
"parent_node_name-user_provided_name". This method enables the use case of Rx and Tx
nodes where multiple of those nodes need to be cloned based on the number of CPU
available in the system. The cloned nodes will be identical, except the "context memory".
Context memory will have information of port, queue pair incase of Rx and Tx ethdev nodes.
 
# Create the graph object
~~~~~~~~~~~~~~~~~~~~~~~~~
Now that the nodes are linked, Its time to create a graph by including
the required nodes. The application can provide a set of node patterns to
form a graph object.
The fnmatch() API used underneath for the pattern matching to include
the required nodes.

The rte_graph_create() API shall be used to create the graph.

Example of a graph object creation:

{"ethdev_rx_0_0", ipv4-*, ethdev_tx_0_*"}

In the above example, A graph object will be created with ethdev Rx
node of port 0 and queue 0, all ipv4* nodes in the system,
and ethdev tx node of port 0 with all queues.


# Multi core graph processing
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

In the current graph library implementation, specifically,
rte_graph_walk() and rte_node_enqueue* fast path API functions
are designed to work on single-core to have better performance.
The fast path API works on graph object, So the multi-core graph 
processing strategy would be to create graph object PER WORKER.
 

# In fast path:
~~~~~~~~~~~~~~~

Typical fast-path code looks like below, where the application
gets the fast-path graph object through rte_graph_lookup() 
on the worker thread and run the rte_graph_walk() in a tight loop.

struct rte_graph *graph = rte_graph_lookup("worker0");

while (!done) {
    rte_graph_walk(graph);
}

# Context update when graph walk in action
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

The fast-path object for the node is `struct rte_node`. 

It may be possible that in slow-path or after the graph walk-in action,
the user needs to update the context of the node hence access to 
struct rte_node * memory.

rte_graph_foreach_node(), rte_graph_node_get(), rte_graph_node_get_by_name()
APIs can be used to to get the struct rte_node*. rte_graph_foreach_node() iterator
function works on struct rte_graph * fast-path graph object while others
works on graph ID or name.


# Get the node statistics using graph cluster
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

The user may need to know the aggregate stats of the node across
multiple graph objects. Especially the situation where each
graph object bound to a worker thread.

Introduced a graph cluster object for statistics. rte_graph_cluster_stats_create()
shall be used for creating a graph cluster with multiple graph objects and
rte_graph_cluster_stats_get() to get the aggregate node statistics.

An example statistics output from rte_graph_cluster_stats_get()

+-----------+------------+-------------+---------------+------------+---------------+-----------+
|Node       |calls       |objs         |realloc_count  |objs/call   |objs/sec(10E6) |cycles/call|
+------------------------+-------------+---------------+------------+---------------+-----------+
|node0      |12977424    |3322220544   |5              |256.000     |3047.151872    |20.0000    |
|node1      |12977653    |3322279168   |0              |256.000     |3047.210496    |17.0000    |
|node2      |12977696    |3322290176   |0              |256.000     |3047.221504    |17.0000    |
|node3      |12977734    |3322299904   |0              |256.000     |3047.231232    |17.0000    |
|node4      |12977784    |3322312704   |1              |256.000     |3047.243776    |17.0000    |
|node5      |12977825    |3322323200   |0              |256.000     |3047.254528    |17.0000    |
+-----------+------------+-------------+---------------+------------+---------------+-----------+

# Node writing guide lines
~~~~~~~~~~~~~~~~~~~~~~~~~~

The process() function of a node is fast-path function and that needs to be written
carefully to achieve max performance.

Broadly speaking, there are two different types of nodes.

1) First kind of nodes are those that have a fixed next_nodes[] for the
complete burst (like ethdev_rx, ethdev_tx) and it is simple to write.
Process() function can move the obj burst to the next node either using
rte_node_next_stream_move() or using rte_node_next_stream_get() and
rte_node_next_stream_put().
   
   
2) The second kind of such node is `intermediate nodes` that decide what is the next_node[]
to send to on a per-packet basis. In these nodes,

a) Firstly, there has to be the best possible packet processing logic.
b) Secondly, each packet needs to be queued to its next node.

At least on some architectures, we get around ~10% more performance if we can avoid copying of 
packet pointers from one node to next as it is ~= memcpy(BURST_SIZE x sizeof(void *)) x NODE_COUNT.

This can be avoided only in the case where all the packets are destined to the same
next node. We call this as home run case and we use rte_node_next_stream_move() to
just move burst of object array by swapping the pointer. a.k.a move stream from one node to next node
with least number of cycles.

Example of intermediate node implementation with home run:
a) Start with speculation that next_node = ctx->next_node.
   This could be the next_node application used in the previous function call of this node.
b) Get the next_node stream array and space using
   rte_node_next_stream_get(next_node, &space)
c) while space != 0 and n_pkts_left != 0,
   prefetch next pkt_set and process current pkt_set to find their next node
d) if all the next nodes of the current pkt_set match speculated next node,
       just count them as successfully speculated(last_spec) till now and
       continue the loop without actually moving them to the next node.
   else if there is a mismatch,
       copy all the pkt_set pointers that were last_spec and
       move the current pkt_set to their respective next's nodes using
       rte_enqueue_next_x1(). Also one of the next_node can be updated as
       speculated next_node if it is more probable. Also set last_spec = 0
e) if n_pkts_left != 0 and space != 0
      goto c) as there is space in the speculated next_node.
f) if last_spec == n_pkts_left,
      then we successfully speculated all the packets to right next node.
      Just call rte_node_next_stream_move(node, next_node) to just move the
      stream/obj array to next node. This is home run where we avoided
      memcpy of buffer pointers to next node.
g) if space = 0 and n_pkts_left != 0
      goto b)
h) Update the ctx->next_node with more probable next node.

# In-tree node documentation
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a) librte_node/ethdev_rx.c:
    This node does rte_eth_rx_burst() into stream buffer acquired using
    rte_node_next_stream_get() and does rte_node_next_stream_put(count)
    only when there are packets received. Each rte_node works on only on
    one rx port and queue that it gets from node->context.
    For each (port X, rx_queue Y), a rte_node is cloned from ethdev_rx_base_node
    as "ethdev_rx-X-Y" in rte_node_eth_config() along with updating
    node->context. Each graph needs to be associated with a unique
    rte_node for a (port, rx_queue).

b) librte_node/ethdev_tx.c:
    This node does rte_eth_tx_burst() for a burst of objs received by it.
    It sends the burst to a fixed Tx Port and Queue information from
    node->context. For each (port X), this rte_node is cloned from
    ethdev_tx_node_base as "ethdev_tx-X" in rte_node_eth_config()
    along with updating node->context.
	Since each graph doesn't need more than one Txq, per port, 
	a Txq is assigned based on graph id to each rte_node instance.
	Each graph needs to be associated with a rte_node for each (port).

c) librte_node/pkt_drop.c:
    This node frees all the objects that are passed to it.

d) librte_node/ip4_lookup.c:
    This node is an intermediate node that does lpm lookup for the received
	ipv4 packets and the result determines each packets next node.
      a) On successful lpm lookup, the result contains the nex_node id and
         next-hop id with which the packet needs to be further processed.
      b) On lpm lookup failure, objects are redirected to pkt_drop node.
      rte_node_ip4_route_add() is control path API to add ipv4 routes.
      To achieve home run, we use rte_node_stream_move() as mentioned in above
      sections.

e) librte_node/ip4_rewrite.c:
      This node gets packets from ip4_lookup node with next-hop id for each
      packet is embedded in rte_node_mbuf_priv1(mbuf)->nh. This id is used
      to determine the L2 header to be written to the pkt before sending
      the pkt out to a particular ethdev_tx node.
      rte_node_ip4_rewrite_add() is control path API to add next-hop info.

Jerin Jacob (1):
  graph: introduce graph subsystem

Kiran Kumar K (1):
  test: add graph functional tests

Nithin Dabilpuram (2):
  node: add packet processing nodes
  example/l3fwd_graph: l3fwd using graph architecture

Pavan Nikhilesh (1):
  test: add graph performance test cases.

 app/test/Makefile                      |    5 +
 app/test/meson.build                   |   10 +-
 app/test/test_graph.c                  |  820 +++++++++++++++++
 app/test/test_graph_perf.c             |  888 +++++++++++++++++++
 config/common_base                     |   13 +
 config/rte_config.h                    |    4 +
 examples/Makefile                      |    3 +
 examples/l3fwd-graph/Makefile          |   58 ++
 examples/l3fwd-graph/main.c            | 1131 ++++++++++++++++++++++++
 examples/l3fwd-graph/meson.build       |   13 +
 examples/meson.build                   |    6 +-
 lib/Makefile                           |    6 +
 lib/librte_graph/Makefile              |   28 +
 lib/librte_graph/graph.c               |  578 ++++++++++++
 lib/librte_graph/graph_debug.c         |   81 ++
 lib/librte_graph/graph_ops.c           |  163 ++++
 lib/librte_graph/graph_populate.c      |  224 +++++
 lib/librte_graph/graph_private.h       |  113 +++
 lib/librte_graph/graph_stats.c         |  396 +++++++++
 lib/librte_graph/meson.build           |   11 +
 lib/librte_graph/node.c                |  419 +++++++++
 lib/librte_graph/rte_graph.h           |  277 ++++++
 lib/librte_graph/rte_graph_version.map |   46 +
 lib/librte_graph/rte_graph_worker.h    |  280 ++++++
 lib/librte_node/Makefile               |   30 +
 lib/librte_node/ethdev_ctrl.c          |  106 +++
 lib/librte_node/ethdev_rx.c            |  218 +++++
 lib/librte_node/ethdev_rx.h            |   17 +
 lib/librte_node/ethdev_rx_priv.h       |   45 +
 lib/librte_node/ethdev_tx.c            |   74 ++
 lib/librte_node/ethdev_tx_priv.h       |   33 +
 lib/librte_node/ip4_lookup.c           |  657 ++++++++++++++
 lib/librte_node/ip4_lookup_priv.h      |   17 +
 lib/librte_node/ip4_rewrite.c          |  340 +++++++
 lib/librte_node/ip4_rewrite_priv.h     |   44 +
 lib/librte_node/log.c                  |   14 +
 lib/librte_node/meson.build            |    8 +
 lib/librte_node/node_private.h         |   61 ++
 lib/librte_node/null.c                 |   23 +
 lib/librte_node/pkt_drop.c             |   26 +
 lib/librte_node/rte_node_eth_api.h     |   31 +
 lib/librte_node/rte_node_ip4_api.h     |   33 +
 lib/librte_node/rte_node_version.map   |    9 +
 lib/meson.build                        |    5 +-
 meson.build                            |    1 +
 mk/rte.app.mk                          |    2 +
 46 files changed, 7362 insertions(+), 5 deletions(-)
 create mode 100644 app/test/test_graph.c
 create mode 100644 app/test/test_graph_perf.c
 create mode 100644 examples/l3fwd-graph/Makefile
 create mode 100644 examples/l3fwd-graph/main.c
 create mode 100644 examples/l3fwd-graph/meson.build
 create mode 100644 lib/librte_graph/Makefile
 create mode 100644 lib/librte_graph/graph.c
 create mode 100644 lib/librte_graph/graph_debug.c
 create mode 100644 lib/librte_graph/graph_ops.c
 create mode 100644 lib/librte_graph/graph_populate.c
 create mode 100644 lib/librte_graph/graph_private.h
 create mode 100644 lib/librte_graph/graph_stats.c
 create mode 100644 lib/librte_graph/meson.build
 create mode 100644 lib/librte_graph/node.c
 create mode 100644 lib/librte_graph/rte_graph.h
 create mode 100644 lib/librte_graph/rte_graph_version.map
 create mode 100644 lib/librte_graph/rte_graph_worker.h
 create mode 100644 lib/librte_node/Makefile
 create mode 100644 lib/librte_node/ethdev_ctrl.c
 create mode 100644 lib/librte_node/ethdev_rx.c
 create mode 100644 lib/librte_node/ethdev_rx.h
 create mode 100644 lib/librte_node/ethdev_rx_priv.h
 create mode 100644 lib/librte_node/ethdev_tx.c
 create mode 100644 lib/librte_node/ethdev_tx_priv.h
 create mode 100644 lib/librte_node/ip4_lookup.c
 create mode 100644 lib/librte_node/ip4_lookup_priv.h
 create mode 100644 lib/librte_node/ip4_rewrite.c
 create mode 100644 lib/librte_node/ip4_rewrite_priv.h
 create mode 100644 lib/librte_node/log.c
 create mode 100644 lib/librte_node/meson.build
 create mode 100644 lib/librte_node/node_private.h
 create mode 100644 lib/librte_node/null.c
 create mode 100644 lib/librte_node/pkt_drop.c
 create mode 100644 lib/librte_node/rte_node_eth_api.h
 create mode 100644 lib/librte_node/rte_node_ip4_api.h
 create mode 100644 lib/librte_node/rte_node_version.map

-- 
2.24.1