DPDK 全称为 Data Plane Development Kit ，是近年来在高速网络通信行业中炙手可热的一种网络报文处理加速框架。DPDK 从十年前诞生直至发展到今天已经可以支持业界主流的高端网卡以及各类加速硬件设备，同时也支持主流的各个CPU 体系结构（可以运行于 X86, Arm, Power 等平台）。同时也可以运行于 Linux/FreeBsd/Windows 等主流操作系统之上。DPDK因为其优异的性能指标被广泛的应用于网关/负载均衡/SDN/虚拟交换的各个场景。
本文主要介绍 DPDK 中的 libgraph 设计思想以及实现，libgraph 的设计思想源自于开源项目 Vector Packet Processor(VPP)。VPP 中的向量包处理优化方案是 libgraph 的参照对象。因为 VPP 项目整体是一个非常全面的解决方案，从中剥离核心的设计框架为其它轻量级项目所用就变得很有意义。这也是 Libgraph 的产生背景。虽然它目前还是DPDK 中相对比较新的 lib，但是其优秀的设计思想还是值得学习参考。
下面将首先介绍 libgraph 架构的核心概念：标量和向量包处理（scalar vs vector packet processing）以及它们之间的区别。然后再介绍 libgraph 中的核心组件，以及它们之间的联系和交互方式。最后，我们将介绍 libgraph 的具体用例以及优缺点。
背景
DPDK libgraph 是一个向量包处理的框架。与传统的标量包处理模型（一系列函数负责处理一个数据包，重复直到所有数据包处理完毕）相比，向量数据包处理模型的差别则在于一系列的函数处理一批数据包。这种方法的主要目的是解决当 pipeline 变复杂时所遇到 i-cache miss 较高的问题。
<p align=center>标量处理模型 vs 向量处理模型</p>
标量处理模型在性能上不如向量处理模型的另一个原因，就是在不同处理函数（业务逻辑）之间，报文传递到下一个处理函数的方式上有所不同。前者只是简单地用 pointer assignment 的方法来传递，若处理基于不同批次的情况下，由于低效的 pointer assignment，会导致处理一批报文时性能低下。
而对于向量包处理模型而言，向量包处理模型反而可以减少上述标量处理模型因批处理而导致性能不理想的情况。这是因为在向量模型中，报文在业务逻辑之间的传输除了可以通过最原始的 pointer assignment 之外，也可以通过优化的 memory copy，最优情况下可以仅仅交换pointer。它不仅消除了标量处理模型会遇到的问题，而且在设计 pipeline 时还可以实现更优的内存分配并与业务逻辑解耦。
图片來源：https://fd.io/gettingstarted/technology/
<p align=center>向量处理模型，graph 有 1 个起点（dpdk-input, n packets）以及 7 个业务逻辑</p>
Graph 框架优点
总体而言，与传统的标量处理模型相比，以下概括了 graph 框架主要的优势
- 更好的 i-cache 管理，更好的icache locality。
- 灵活的 pipeline 模型（pipeline 框架是从业务逻辑中抽象出来的）
- 减少 pointer 复制
- Node 可以累积多个先前 node 所传递的报文，因此批处理性能更好
- 表驱动节点调度（便于支持QoS）而不是 hardcode pipeline
Graph 工作流程
现在来说一下整体上 graph 框架的工作流程。如上图所述的一样，一个 graph 是由不同的节点 (node) 所组成的。与传统的标量模型相比，两个框架其实都包含一样的逻辑。最大的不同是 graph 框架中 node 节点在运行时与其他 node节点的交互方式，或者具体地来说，是报文在node节点中的传递方式。
一个 node 中的 报文 传送到不同的 node，home run 情况 (优化案例) 以及正常 enqueue情况；动态增加 node 的 objects 队列 大小
Node 的 Object 队列大小
默认情况下，每个 node 都有一个 RTE_GRAPH_BURST_SIZE 大小（node->size）的 object 队列，它定义了该 node 中可以容纳和处理的报文数量。如果一个 node 试图将报文排队到下一个 node，但下一个 node 已经有报文在排队并且已满（例如在 l3fwd 中，用户可以有多个接收队列/ node 排队到同一个下一个 node pkt_cls），node 的 object 队列大小将会被动态的加倍。这意味着 node 具有批处理的优势，因为它可以累积报文。
注意：当前 API 不支持 node 的 object 队列大小在增大后再缩小
Objs 的传递 — 'home run'/normal enqueue
报文转换有两种类型，一种是正常的 enqueue，另一种是优化情况，“home run”。
Normal enqueue
在上面介绍 node 的 object 队列大小部分，我们提到将报文排队到下一个 node 的概念。对于普通的 enqueue，就是简单的将当前 node 中处理好的报文，通过使用 rte_memcpy / pointer assignment 作为传递方法， enqueue 到下一个可能的 node。
Home run
Home run 则是一种优化的情况，它不像普通的 enqueue 把报文复制到下一个 node，而是简单地交换当前 node 和下一个 node 之间的有关于报文的指针（例如报文、报文数目），从而消除 memory copy / pointer assignment 的开销。当满足以下条件时，home run 才会被触发：
- 所有已处理好的报文都将前往同一个 node
- 下一个 node 的 object 队列没有任何需要处理的报文 (node 的 object 队列为空)
/* Home run scenario */
/* Swap the pointers if dst don't have valid objs */
if (likely(dst->idx == 0)) {
void **dobjs = dst->objs;
uint16_t dsz = dst->size;
dst->objs = src->objs;
dst->size = src->size;
src->objs = dobjs;
src->size = dsz;
dst->idx = src->idx;
__rte_node_enqueue_tail_update(graph, dst);
}
Graph 遍历 node的流程
/**
* @file lib/graph/rte_graph_worker.h:rte_graph_walk
*/
/*
* Walk on the source node(s) ((cir_start - head) -> cir_start) and then
* on the pending streams (cir_start -> (cir_start + mask) -> cir_start)
* in a circular buffer fashion.
*
* +-----+ <= cir_start - head [number of source nodes]
* | |
* | ... | <= source nodes
* | |
* +-----+ <= cir_start [head = 0] [tail = 0]
* | |
* | ... | <= pending streams
* | |
* +-----+ <= cir_start + mask
*/
const rte_graph_off_t *cir_start = graph->cir_start;
const rte_node_t mask = graph->cir_mask;
uint32_t head = graph->head;
while (likely(head != graph->tail)) {
node = RTE_PTR_ADD(graph, cir_start[(int32_t)head++]);
RTE_ASSERT(node->fence == RTE_GRAPH_FENCE);
objs = node->objs;
rte_prefetch0(objs);
if (rte_graph_has_stats_feature()) {
[...]
} else {
node->process(graph, node, objs, node->idx);
}
node->idx = 0;
head = likely((int32_t)head > 0) ? head & mask : head;
}
graph->tail = 0;
注意：rte_graph_walk 调用 struct rte_graph 的内存布局以及 circular buffer (cir_start) 可以参考后面组件的介绍
graph walk 的概念简单明了，它总是有次序地去完成一系列操作：
- 21行：定位下一个需要处理的 node
- 23行：准备下一个需要处理的 node 的 objects /报文
- 29行：处理定位好的 node
- 32行：检查 graph walk 是否完成
在 graph walk 层面来看，最重要的就是第一步：定位下一个要处理的 node。DPDK 的 graph 框架利用了 circular buffer 和附带的 head 和 tail 指针定位下一个 node，如果 head 不等于 tail 指针，这就代表了 circular buffer 里有需要处理的 node，而在 libgraph 库中，这些待处理的 node 也被称为 pending stream。
回到第一步，它是以一个 circular buffer (cir_start[head++]) 的 head 来定位，或者更详细地从 graph walk 的始点说起，由于 graph->head 在初始化的时候被指定为 -src_node_count （负的 source node 数量，可以参考下一部分 rte_graph 的内存布局），所以 cir_start[head] 其实就是第一个 source node。那么 tail 的作用是什么？libgraph 是如何利用它来动态修改 circular buffer 和 pending stream 帮助 node 的定位呢？
在回答这些问题之前，我们首先来了解下面两个 API 函数，分别是 __rte_node_enqueue_prologue 和 __rte_node_enqueue_tail_update。
__rte_node_enqueue_prologue(struct rte_graph *graph, struct rte_node *node,
const uint16_t idx, const uint16_t space) {
/* Add to the pending stream list if the node is new */
if (idx == 0)
__rte_node_enqueue_tail_update(graph, node);
if (unlikely(node->size < (idx + space)))
__rte_node_stream_alloc(graph, node);
}
每次当前 node 需要将报文 enqueue 到任何下一个 node 时，都需要调用 __rte_node_enqueue_prologue去检查以下内容：
- 下一个 node 是否已被添加到 pending stream （待处理的 node）
- 是否需要为下一个 node 分配内存
其中变量 idx 和 space 分别表示下一个 node 已有的报文数目，以及当前 node 想要enqueue的数目。
static __rte_always_inline void
__rte_node_enqueue_tail_update(struct rte_graph *graph, struct rte_node *node)
{
uint32_t tail;
tail = graph->tail;
graph->cir_start[tail++] = node->off;
graph->tail = tail & graph->cir_mask;
}
而API 函数 __rte_node_enqueue_tail_update目的就是调整 tail 把下一个 node 放到 pending stream 里。
下图展示了报文的传递跟 node 是如何被加到 pending stream 的关系。
注意一下 node 添加到 pending stream 的顺序取决于处理报文时的顺序。例如，如果报文 1 和 3 到 node2，而 报文 2 和 4 到 node3，那么 circular buffer/pending stream 中 node1 和 node2 的顺序将被交换。
组件
libgraph 的核心组件是 graph 和 node。graph 作为调度 node 的全局数据结构，而 node 则是用来封装业务逻辑。
Graph
<p align=center>3 个node; 1 个 source node (源节点)和 2 个 node (非源节点)的 graph 结构</p>
上图显示了具有 3 个节点的 graph 结构，包含以下关键组件：
graph_list
存储所有创建成功的 graph。如果 graph 创建成功，graph 会被添加到 graph_list 中。与传统的 main loop 设计相比（把函数直接挂载到 CPU 核上），用户可以透过这种管理模式把 graph_list 中的 graph 映射到不同的 CPU 核上。
graph->node_list
每个创建成功的 graph 中的 node_list 都包含了先前添加到 graph 中的 node。注意此处使用的是 graph_node 结构，其中包含了本身的 node（struct node* node）以及其相邻的 node。
struct graph_node vs struct node
struct node 结构体的用法仅仅是用来描述对应的 node，和 graph 是没有关系的。而 struct graph_node 其实就是把 struct node 包装了一层，主要目的就是强调这个 node 在一个 graph 中。
struct rte_graph
接下来介绍 struct rte_graph（rte_*: runtime 时所用到的数据结构）的内存布局，建议先把先前的 graph walk 部分浏览一遍，以更好了解 rte_graph 是如何被使用。
<p align=center>rte_graph 内存布局。 注意此例除有 3 个 source node，而待处理的流 (pending stream)中有 2 个节点。</p>
现在可以更清楚地看到 struct graph 及其子组件 struct node 的目的是保存内部数据/用于设计，而 struct rte_graph 和 struct rte_node 是用于 runtime。runtime 的内存布局包含了所有必需的组件，比如所有source node、non-source nodes 以及 pending steam 的 node（从cir_start 开始）。
先前我们提到在 graph walk 时需要从 source node 开始，以及需要利用 circular buffer 来定位待处理的node。现在透过分析内存布局的帮助下，我们能更好地去想象 graph walk 是如何从 cir_start[-src_node_count] 开始，直到再没有任何 pending stream (head 等于 tail）为止。
struct node
理解了 graph 的运作原理后，我们现在讨论一下底层的关键组件 node。先前我们已经提到 graph_node 和 node 的部分区别，其实关键区别在于 node 实际包含了什么信息。
struct node {
STAILQ_ENTRY(node) next; /* Next node in the list. */
char name[RTE_NODE_NAMESIZE]; /* Name of the node. */
uint64_t flags; /* Node config flag - source node?*/
rte_node_process_t process; /* Node process function. */
rte_node_init_t init; /* Node init function. */
rte_node_fini_t fini; /* Node fini function. */
rte_node_t id; /* Allocated identifier for the node. */
rte_node_t parent_id; /* Parent node identifier. */
rte_edge_t nb_edges; /* Number of edges from this node. */
char next_nodes[][RTE_NODE_NAMESIZE]; /* Names of next nodes. */
};
<p align=center>Struct node 结构体 (lib/graph/graph_private.c)</p>
向量包处理的概念是一次处理一个向量/一批报文，所以一个节点其实就是代表一个function，只不过处理对象是一批报文。
一个节点除了包含相邻 node 的信息外，还包含有助于识别 node 的基本信息，例如 id、parent_id、flags、name 等。最重要的是，除了核心处理函数 rte_node_process_t process 以外，它还包含了在创建、销毁 graph 时运行的 init 和 fini 函数。 init 函数的一些实际可以是配置路由表、定义 ACL 规则等。
Node 的注册
node 的注册是通过 contructor scheme 的 (attribute((constructor))）来完成的。下面显示了一个非常简单的 node 注册示例。需要强调的是： .process 的函数定义突出了向量数据包处理的概念 （需要处理的报文 (**objs) 及其数量 (nb_objs)）。
/**
* @param objs
* Pointer to an array of objects to be processed.
* @param nb_objs
* Number of objects in the array.
*
*/
/* This hello world node simply does nothing but to return the number
of objects in the node */
static uint16_t
hello_world_process(struct rte_graph *graph, struct rte_node *node, void **objs,
uint16_t nb_objs)
{
printf( Hello World\n );
return nb_objs;
}
static struct rte_node_register hello_world_node = {
.process = hello_world_process,
.flags = RTE_NODE_SOURCE_F,
.name = hello_world_node ,
};
RTE_NODE_REGISTER(hello_world_node);
构造一个 print Hello World 的 source node
source node vs non-source node
在任何处理模型都必须有一个起点，而在 libgraph 中每个 graph pipeline 都必须从 source node 开始。而对于非 source node 来说，它们则是依赖于先前 node 是否会将报文排队到它们的节点，因此它们只会出现在动态的 pending stream 中。
总结
本文介绍了 DPDK graph API 的框架以及它内部是如何实现的。 graph 框架的优势在于减少 i-cache miss 、更好的抽象业务逻辑，以及提高用户设计 pipeline 的灵活度，但 graph 框架也同时带来下列缺点：
- 引入潜在内存安全风险
- 复杂的代码逻辑，需要大量的测试工作
- 初学者学习曲线陡峭
总体而言，与传统的 pipeline 模式相比，graph 框架也会出现 tradeoff。使用者需要考虑其业务逻辑的复杂程度，才能有计划地设计出可管理的 graph pipeline。graph 模型更适用于 pipeline 比较复杂的场景。有兴趣的读者可以持续关注后期即将发布的《DPDK Graph Pipeline 框架示例和性能分析》，以更好地理解 DPDK libgraph 的性能和实际用途。