[PATCH dpdk/26.11 v3 0/2] graph: topological bitmap scheduling

[Robin Jarry]

Replace the FIFO circular buffer in rte_graph with a bitmap and a
topologically-sorted schedule table. The old circular buffer appended
nodes in enqueue order, effectively a partial DFS driven by per-node
process functions. This caused convergence nodes to be visited before
all upstream branches had run, resulting in redundant visits with
smaller batches.

Nodes are now sorted by (topo_order, node_id) using BFS depth from
source nodes, ensuring upstream nodes are always visited before
downstream ones. The diamond perf test shows a ~10% throughput
improvement (converge visited once at 256 objs/call instead of twice
at 128).

Changes v2 -> v3:
 - dropped explicit priority field (int16_t) from rte_node_register
   and struct node; topological ordering from BFS is sufficient
 - removed hiprio worker node type from diamond test; topo_order
   alone provides correct ordering without user intervention
 - updated documentation and SVG diagram accordingly

Changes v1 -> v2:
 - split diamond perf test into separate preparatory patch
 - added topological depth (topo_order) as secondary sort key to
   preserve upstream-before-downstream ordering, preventing a
   regression in the reverse tree test
 - restored idx == 0 guard on bitmap set in the enqueue path to
   avoid a ~15% throughput regression caused by touching the pending
   bitmap cache line on every enqueue call
 - added performance numbers measured before and after

Cc: Christophe Fontaine <cfontain at redhat.com>
Cc: David Marchand <david.marchand at redhat.com>
Cc: Jerin Jacob <jerinj at marvell.com>
Cc: Kiran Kumar Kokkilagadda <kirankumark at marvell.com>
Cc: Konstantin Ananyev <konstantin.ananyev at huawei.com>
Cc: Maxime Leroy <maxime at leroys.fr>
Cc: Nithin Kumar Dabilpuram <ndabilpuram at marvell.com>
Cc: Vladimir Medvedkin <vladimir.medvedkin at intel.com>
Cc: Zhirun Yan <yanzhirun_163 at 163.com>

Robin Jarry (2):
  graph: add diamond topology performance test
  graph: replace circular buffer with topological bitmap

 app/test/test_graph_perf.c                    |  130 +-
 doc/guides/prog_guide/graph_lib.rst           |   29 +-
 .../prog_guide/img/graph_mem_layout.svg       | 1823 +++++++----------
 lib/graph/graph.c                             |   27 +-
 lib/graph/graph_debug.c                       |   12 +-
 lib/graph/graph_ops.c                         |   46 +
 lib/graph/graph_populate.c                    |  107 +-
 lib/graph/graph_private.h                     |   41 +-
 lib/graph/rte_graph_model_mcore_dispatch.h    |   34 +-
 lib/graph/rte_graph_model_rtc.h               |   63 +-
 lib/graph/rte_graph_worker.h                  |    2 +-
 lib/graph/rte_graph_worker_common.h           |   78 +-
 12 files changed, 1158 insertions(+), 1234 deletions(-)

-- 
2.55.0