DPDK ACL算法介绍（二）

一些说明：

1.merge完后，对于有分支的边，”…” 表示匹配除了其它分支以外的所有值，图中表述不准确；

2.对于虚线的节点，表示merge完后会被释放；红色节点表示新建的node；红色的边，表示有修改或新增的边；实心节点表示match节点。

3.node创建的顺序是a\b\c\…，但决定node是否free，则是1\2\3\…，见红色节点的名称。

2.node array的构造

trie树构造完成后，会将其由指针跳转的形式转换为等效的数组索引形式，即node array，既可让匹配数据更紧凑，也可提高匹配算法的效率。

采用node array的方式进行状态点的压缩是很常见的优化方式，比如snort里面的ac算法(acsmx.c)：

ac 

通过将出边由指针方式修改为索引方式，整个匹配tree的内存占用只需要原来的1/5。

将指针方式转换为node array形式是优化的第一步，对于Next[256]出边又可以采用多种压缩方式，比如snort中新的ac算法(acsmx2.c)，就采用了Sparse rows和Banded rows等多种压缩方式，但其原理是将出边进行映射转换，本质上还是做DFA状态跳转。

2.1 node type

DPDK对边的压缩方式与上述类似，不过它优化的粒度更细，不同type的node有不同的压缩方式：

• 对于出边比较多的节点它会被标记为RTE_ACL_NODE_DFA；
• 对于出边比较少的节点则使用RTE_ACL_NODE_QRANGE；
• 如果节点出边仅一条则为RTE_ACL_NODE_SINGLE；
• 对于Match节点会被标记为RTE_ACL_NODE_MATCH。

比如在示例三中，node 1为DFA节点（根节点强制使用DFA方式），2、3、a5、b4、c3、d2为QRANGE，4、5为SINGLE，6、e1为MATCH。

2、3、a5、b4虽然在图上仅有一条有效边，但它不为SINGLE，因为对于无效的匹配其实也会有出边，所以它的真实出边数目并不唯一，只有像4、5这类全匹配节点才是真正的SINGLE节点。

在构造node array前，会调用acl_calc_counts_indices函数更新node的node type，fanout等信息。

node type依据其fanout值决定，fanout计算见acl_count_fanout函数，其原理是：

1. 计算node的values（bitmap）中连续为0的区间数；
2. 计算node的各个出边values（bitmap）中连续为1的区间数；
3. 将上述结果相加即为fanout值；

比如对于示例3中的d2节点：

1. node的values为：0xFFFF::FFFF࿰