[EXTERNAL] [PATCH dpdk] graph: replace circular buffer with priority-based bitmap scheduling

[Jerin Jacob]

On Wed, May 20, 2026 at 3:20 AM Robin Jarry <rjarry at redhat.com> wrote:
>
> Hi Jerin,
>
> Jerin Jacob, May 19, 2026 at 12:25:
> > Some high-level comments:
> >
> > 1)What will be the performance overhead for graph walk.  Try
> >   app/test/test_graph_perf.c and l3fwd_graph
>
> I have made some measurements. There was a regression caused by
> systematic access to a cache line. This will be fixed in v2.

Thanks. We will review the v2.



> > 2)If priorities are same, Does it have similar performance with
> >   existing code?
>
> Yes with v2. I have added a topo order as a fallback when all priorities
> are equal so that it behaves as previously.
>
> > 3)Does it have any effect on packet ordering on egress.i.e for a given
> >   flow ingress order != egress order
>
> Some independent flows "may" be reordered but that depends on the
> topology, not the graph walk algorithm.
>
> For example, the following graph:
>
>         +--------+
>         | eth_in |
>         +--------+
>         /        \
>        v          v
>    +-------+     +---------+
>    | ip_in | <-- | mpls_in |
>    +-------+     +---------+
>        |
>        |  ,------------.
>        v  v            |
>    +--------+     +----------+
>    | ip_out | --> | ipip_out |
>    +--------+     +----------+
>        |
>        v
>    +---------+
>    | eth_out |
>    +---------+
>
> If you receive the following stream of packets in "eth_in":
>
>    1. Eth/IP
>    2. Eth/IP
>    3. Eth/MPLS/IP
>    4. Eth/MPLS/IP
>    5. Eth/MPLS/IP
>    6. Eth/IP (needs IPIP encap)
>    7. Eth/IP (needs IPIP encap)
>    8. Eth/IP
>
> The "eth_out" node will see:
>
>    1. Eth/IP
>    2. Eth/IP
>    3. Eth/IP
>    4. Eth/IP
>    5. Eth/IP
>  * 8. Eth/IP <----------- reordered before 6 and 7
>    6. Eth/IP/IP
>    7. Eth/IP/IP
>
> With the FIFO circular buffer and with the new bitmap priority scheduler.
>
> The only difference with the bitmap system is that If you set "mpls_in"
> and "ip_out" higher priorities, the "ip_in" and "eth_out" nodes will be
> visited only once.
>
> > If there is performance regression we may need to consider new
> > RTE_GRAPH_MODEL_XXXXX to enable this feature
>
>
> --
> Robin
>
> > Times approximate.
>