DPDK ACL算法介绍（一）

DPDK提供了三种classify算法：最长匹配LPM、精确匹配（Exact Match）和通配符匹配（ACL）。

其中的ACL算法，本质是步长为8的Multi-Bit Trie，即每次可匹配一个字节。一般来说步长为n时，Trie中每个节点的出边为2^n，但DPDK在生成run-time structures时，采用DFA/QRANGE/SINGLE这几种不同的方式进行数据结构的压缩，有效去除了冗余的出边。本文将为大家介绍ACL算法的基本原理，主要内容包括：trie树的构造、运行时的node array生成和匹配原理。

0.规则的构造

0.1 定义匹配区域 rte_acl_field_def

ACL规则主要面向的是IP流量中的五元组信息，即IP/PORT/PROTO，算法在这个基础上进行了抽象，提供了三种类型的匹配区域：

• RTE_ACL_FIELD_TYPE_BITMASK：单字节区域如ip头部一个字节的proto字段；
• RTE_ACL_FIELD_TYPE_MASK：采用MASK方式描述，一般对应4字节的源/目的地址；
• RTE_ACL_FIELD_TYPE_RANGE：一般对应TCP或UDP头部2字节的PORT区域。

熟悉这三种类型的使用后，完全可以用它们去匹配网络报文的其它区域，甚至将其应用到其它场景中。

具体来说，rte_acl_field_def有5个成员：type、size、field_index、input_index、offset。

如果要深入理解算法，可以思考这几个字段的意义，或者换个角度来看：

前面提到的三种type，往往对应3种size，那么size字段是多余的吗，什么时候size与一般情况下的使用不同，为什么？
field_index，它一般采用enum类型定义，在 rte_acl_field_def结构中也基本是连续的，是否可以去掉?
offset用来指定匹配时data的偏移，那么是不是意味着匹配时不是逐字节匹配？
有了offset指名偏移，为什么还要input_index字段呢?

0.2 定义具体规则 acl_ipv4_rule

对于规则的定义，要注意如下两点：

a)对于每一个field给出明确的定义

比如定义了5个field，那么请给出每一个的具体定义：

    .field[0] = {.value.u8 = 0, .mask_range.u8 = 0x0,},
    .field[1] = {.value.u32 = IPv4(0, 0, 0, 0), .mask_range.u32 = 0,},
    .field[2] = {.value.u32 = IPv4(192, 168, 2, 4), .mask_range.u32 = 32,},
    .field[3] = {.value.u16 = 0, .mask_range.u16 = 0xffff,},
    .field[4] = {.value.u16 = 1024, .mask_range.u16 = 0xffff,},

像field[1]中IP和mask都为0，表示匹配所有的IP地址；field[3]中range由0到65535，表示匹配所有。类似这样的全匹配一定要显示的定义出来，因为如果不明确定义，这些字段的值取决于编译器的，最后编译的ACL规则很可能与原有设想存在偏差。

b)field的全匹配方式

如果在规则中，对于某个field不进行限制，对于不同type的field，规则书写时有一定差异：

对于BITMASK和MASK类型，全0代表匹配所有，如上例中的field[0]、field[1]；

对于RANGE，则按照上述field[3