[v2,00/28] graph: introduce graph subsystem

  From: Jerin Jacob <jerinj@marvell.com>

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.

v2..v1:
------
1) Added programmer guide/implementation documentation and l3fwd-graph doc

Hosted in netlify for easy reference:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Programmer’s Guide:
https://dpdk-graph.netlify.com/doc/html/guides/prog_guide/graph_lib.html

l3fwd-graph doc:
https://dpdk-graph.netlify.com/doc/html/guides/sample_app_ug/l3_forward_graph.html

API doc:
https://dpdk-graph.netlify.com/doc/html/api/rte__graph_8h.html
https://dpdk-graph.netlify.com/doc/html/api/rte__graph__worker_8h.html
https://dpdk-graph.netlify.com/doc/html/api/rte__node__eth__api_8h.html
https://dpdk-graph.netlify.com/doc/html/api/rte__node__ip4__api_8h.html

2) Added the release notes for the this feature

3) Fix build issues reported by CI for v1:
http://mails.dpdk.org/archives/test-report/2020-March/121326.html

RFC..v1:
--------

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.

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


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


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

Jerin Jacob (13):
  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
  doc: add graph library programmer's guide guide

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

Nithin Dabilpuram (11):
  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
  doc: add l3fwd graph application user guide

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

 MAINTAINERS                                   |   14 +
 app/test/Makefile                             |    7 +
 app/test/meson.build                          |   12 +-
 app/test/test_graph.c                         |  819 ++++
 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 +
 doc/guides/prog_guide/graph_lib.rst           |  397 ++
 .../prog_guide/img/anatomy_of_a_node.svg      | 1078 ++++++
 .../prog_guide/img/graph_mem_layout.svg       |  702 ++++
 doc/guides/prog_guide/img/link_the_nodes.svg  | 3330 +++++++++++++++++
 doc/guides/prog_guide/index.rst               |    1 +
 doc/guides/rel_notes/release_20_05.rst        |   32 +
 doc/guides/sample_app_ug/index.rst            |    1 +
 doc/guides/sample_app_ug/intro.rst            |    4 +
 doc/guides/sample_app_ug/l3_forward_graph.rst |  327 ++
 examples/Makefile                             |    3 +
 examples/l3fwd-graph/Makefile                 |   58 +
 examples/l3fwd-graph/main.c                   | 1111 ++++++
 examples/l3fwd-graph/meson.build              |   13 +
 examples/meson.build                          |    6 +-
 lib/Makefile                                  |    6 +
 lib/librte_graph/Makefile                     |   28 +
 lib/librte_graph/graph.c                      |  589 +++
 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              |  347 ++
 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           |  542 +++
 lib/librte_node/Makefile                      |   32 +
 lib/librte_node/ethdev_ctrl.c                 |  116 +
 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                  |  619 +++
 lib/librte_node/ip4_rewrite.c                 |  326 ++
 lib/librte_node/ip4_rewrite_priv.h            |   77 +
 lib/librte_node/log.c                         |   14 +
 lib/librte_node/meson.build                   |   10 +
 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 +
 56 files changed, 14623 insertions(+), 5 deletions(-)
 create mode 100644 app/test/test_graph.c
 create mode 100644 app/test/test_graph_perf.c
 create mode 100644 doc/guides/prog_guide/graph_lib.rst
 create mode 100644 doc/guides/prog_guide/img/anatomy_of_a_node.svg
 create mode 100644 doc/guides/prog_guide/img/graph_mem_layout.svg
 create mode 100644 doc/guides/prog_guide/img/link_the_nodes.svg
 create mode 100644 doc/guides/sample_app_ug/l3_forward_graph.rst
 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
  

On Thu, Mar 26, 2020 at 10:26 PM <jerinj@marvell.com> wrote:
>
> From: Jerin Jacob <jerinj@marvell.com>
>
> 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.
>
> v2..v1:
> ------
> 1) Added programmer guide/implementation documentation and l3fwd-graph doc
>
> Hosted in netlify for easy reference:
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

In case if someone interested to know the steps to host DPDK
documentation for free in netlify.

1) Create a DPDK repo with your code(documentation files) in GitHub

2) Open https://app.netlify.com/ URL

3) Sign in  netlify with GitHub account

4) Hosting procedure in netlify:
         a) Select "New site from git"
         b) Select the DPDK repo in Github
         c) Configure the following Build settings and deploy:
                  i) Repository: < Point to Selected DPDK repo in Github>
                 ii) Base directory: Not set
                  iii) Build command: pip install sphinx && pip
install sphinx_rtd_theme && make doc-api-html && make doc-guides-html
                  iv) Publish directory: build
d) Update the "Site details" if needed like Site name. The final site
will be "your site name".netlify.com/,

Once it is deployed,

1) Guide URL will be at: "your site name".netlify.com/doc/html/guides/

Example: https://dpdk-graph.netlify.com/doc/html/guides/prog_guide/graph_lib.html

2) API doc URL will be at: "your site name".netlify.com/doc/html/api/

example: https://dpdk-graph.netlify.com/doc/html/api/rte__graph_8h.html

> Programmer’s Guide:
> https://dpdk-graph.netlify.com/doc/html/guides/prog_guide/graph_lib.html
>
> l3fwd-graph doc:
> https://dpdk-graph.netlify.com/doc/html/guides/sample_app_ug/l3_forward_graph.html
>
> API doc:
> https://dpdk-graph.netlify.com/doc/html/api/rte__graph_8h.html
> https://dpdk-graph.netlify.com/doc/html/api/rte__graph__worker_8h.html
> https://dpdk-graph.netlify.com/doc/html/api/rte__node__eth__api_8h.html
> https://dpdk-graph.netlify.com/doc/html/api/rte__node__ip4__api_8h.html
>
  

27/03/2020 07:49, Jerin Jacob:
> In case if someone interested to know the steps to host DPDK
> documentation for free in netlify.
> 
> 1) Create a DPDK repo with your code(documentation files) in GitHub
> 
> 2) Open https://app.netlify.com/ URL
> 
> 3) Sign in  netlify with GitHub account
> 
> 4) Hosting procedure in netlify:
>          a) Select "New site from git"
>          b) Select the DPDK repo in Github
>          c) Configure the following Build settings and deploy:
>                   i) Repository: < Point to Selected DPDK repo in Github>
>                  ii) Base directory: Not set
>                   iii) Build command: pip install sphinx && pip
> install sphinx_rtd_theme && make doc-api-html && make doc-guides-html
>                   iv) Publish directory: build
> d) Update the "Site details" if needed like Site name. The final site
> will be "your site name".netlify.com/,
> 
> Once it is deployed,
> 
> 1) Guide URL will be at: "your site name".netlify.com/doc/html/guides/
> 
> Example: https://dpdk-graph.netlify.com/doc/html/guides/prog_guide/graph_lib.html
> 
> 2) API doc URL will be at: "your site name".netlify.com/doc/html/api/
> 
> example: https://dpdk-graph.netlify.com/doc/html/api/rte__graph_8h.html

Thanks, that looks convenient and very helpful!