[v1,00/26] graph: introduce graph subsystem

Message ID 20200318213551.3489504-1-jerinj@marvell.com (mailing list archive)


Jerin Jacob Kollanukkaran March 18, 2020, 9:35 p.m. UTC
  From: Jerin Jacob <jerinj@marvell.com>

It is the v1 version of the DPDK graph support based on the following
RFC http://patches.dpdk.org/cover/65432/

This patch set contains 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 patchset further includes performance enhancements and modularity
to the DPDK as discussed in more detail below.


1) Split the patch to more logical ones for review.
2) Added doxygen comments for the API
3) Code cleanup
4) Additional performance improvements.
Delta between l3fwd and l3fwd-graph is negligible now.
(~1%) on octeontx2.
5) Added SIMD routines for x86 in additional to arm64.

Pending items (Will be addressed in v2)
1) Add documentation as a patch for programming guide and l3fwd-graph
user guide.

Addional nodes planned for v20.08
1) Packet classification node
2) Support for IPV6 LPM node

This patchset 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
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/.

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

# l3fwd-graph performance is -1.2% 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

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.

Why Graph architecture
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
to another vendor. Going forward, We believe, API abstraction may not be
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
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
if not needed.

3) Use arm64 optimized memory copy for arm64 architecture by

Commands to run tests

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

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

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

# ./ip_pipeline --c 0xff0000 -- -s route.cli

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


Programming guide and API walk-through
# Anatomy of Node:
See the

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
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
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

f) nb_edges:

Number of downstream nodes connected to this node. The next_nodes[]
stores the
downstream nodes objects. rte_node_edge_update() and
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()

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
'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

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

Once nodes are available to the program, Application or node public API
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
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
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) {

# 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(),
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.
shall be used for creating a graph cluster with multiple graph objects
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
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.
This can be done using rte_node_enqueue_[x1|x2|x4]() api's if they are
to single next or
rte_node_enqueue_next() that takes array of nexts. 

In scenario where multiple intermediate nodes are present but most of
the time  each node using same next node for all its packets, cost of moving every
pointer from current node's stream to next node's stream could be avoided.
This is called home run and rte_node_next_stream_move() could be used to 
just move stream from current node to next node with least number of
Since this can be avoided only in the case where all the packets are
destined to the same next node, node implementation should be also having worst
case handling where every packet could be going to different next node.

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 with required space using
   rte_node_next_stream_get(next_node, space)
c) while n_left_from > 0 // Pkts left to be sent
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
       speculated next_node if it is more probable. 
	   Finally reset 'last_spec' to zero.
e) if n_left_from != 0
      goto c) to process remaining pkts.
f) if last_spec == nb_objs,
      All the objects passed were successfully speculated to single next
	  So, the current stream can be moved to next node using 
	  rte_node_next_stream_move(node, next_node). This is home run 
	  where memcpy of buffer pointers to next node is avoided.
g) 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 passed to it
	(src node stream) and does rte_node_next_stream_move() 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 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

c) librte_node/pkt_drop.c:
    This node frees all the objects passed to it considering them as
	rte_mbufs that need to be freed.

d) librte_node/ip4_lookup.c:
    This node is an intermediate node that does lpm lookup for the
    receive 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
      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.

f) librte_node/null.c:
      This is null node that just ignores the set of objects passed to
it and reports that all are processed.

Jerin Jacob (12):
  graph: define the public API for graph support
  graph: implement node registration
  graph: implement node operations
  graph: implement node debug routines
  graph: implement internal graph operation helpers
  graph: populate fastpath memory for graph reel
  graph: implement create and destroy APIs
  graph: implement graph operation APIs
  graph: implement Graphviz export
  graph: implement debug routines
  graph: implement stats support
  graph: implement fastpath API routines

Kiran Kumar K (2):
  graph: add unit test case
  node: add ipv4 rewrite node

Nithin Dabilpuram (10):
  node: add log infra and null node
  node: add ethdev Rx node
  node: add ethdev Tx node
  node: add ethdev Rx and Tx node ctrl API
  node: ipv4 lookup for arm64
  node: add ipv4 rewrite and lookup ctrl API
  node: add pkt drop node
  l3fwd-graph: add graph based l3fwd skeleton
  l3fwd-graph: add ethdev configuration changes
  l3fwd-graph: add graph config and main loop

Pavan Nikhilesh (2):
  graph: add performance testcase
  node: ipv4 lookup for x86

 MAINTAINERS                            |   13 +
 app/test/Makefile                      |    5 +
 app/test/meson.build                   |   11 +-
 app/test/test_graph.c                  |  820 +++++++++++++++++
 app/test/test_graph_perf.c             | 1057 ++++++++++++++++++++++
 config/common_base                     |   12 +
 config/rte_config.h                    |    4 +
 doc/api/doxy-api-index.md              |    5 +
 doc/api/doxy-api.conf.in               |    2 +
 examples/Makefile                      |    3 +
 examples/l3fwd-graph/Makefile          |   58 ++
 examples/l3fwd-graph/main.c            | 1113 ++++++++++++++++++++++++
 examples/l3fwd-graph/meson.build       |   13 +
 examples/meson.build                   |    6 +-
 lib/Makefile                           |    6 +
 lib/librte_graph/Makefile              |   28 +
 lib/librte_graph/graph.c               |  590 +++++++++++++
 lib/librte_graph/graph_debug.c         |   84 ++
 lib/librte_graph/graph_ops.c           |  169 ++++
 lib/librte_graph/graph_populate.c      |  234 +++++
 lib/librte_graph/graph_private.h       |  346 ++++++++
 lib/librte_graph/graph_stats.c         |  406 +++++++++
 lib/librte_graph/meson.build           |   11 +
 lib/librte_graph/node.c                |  421 +++++++++
 lib/librte_graph/rte_graph.h           |  786 +++++++++++++++++
 lib/librte_graph/rte_graph_version.map |   47 +
 lib/librte_graph/rte_graph_worker.h    |  541 ++++++++++++
 lib/librte_node/Makefile               |   30 +
 lib/librte_node/ethdev_ctrl.c          |  115 +++
 lib/librte_node/ethdev_rx.c            |  221 +++++
 lib/librte_node/ethdev_rx_priv.h       |   81 ++
 lib/librte_node/ethdev_tx.c            |   86 ++
 lib/librte_node/ethdev_tx_priv.h       |   62 ++
 lib/librte_node/ip4_lookup.c           |  631 ++++++++++++++
 lib/librte_node/ip4_rewrite.c          |  325 +++++++
 lib/librte_node/ip4_rewrite_priv.h     |   77 ++
 lib/librte_node/log.c                  |   14 +
 lib/librte_node/meson.build            |    8 +
 lib/librte_node/node_private.h         |   96 ++
 lib/librte_node/null.c                 |   23 +
 lib/librte_node/pkt_drop.c             |   26 +
 lib/librte_node/rte_node_eth_api.h     |   70 ++
 lib/librte_node/rte_node_ip4_api.h     |   87 ++
 lib/librte_node/rte_node_version.map   |    9 +
 lib/meson.build                        |    5 +-
 meson.build                            |    1 +
 mk/rte.app.mk                          |    2 +
 47 files changed, 8755 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_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_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