本文主要是介绍DPDK ACL规则字段到tries树节点转换，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
示例ACL规则：
@39.7.6.0/24 146.11.37.196/32 0 : 65535 514 : 614 0x6/0xFF
ACL库中定义了三种字段类型，如下：
enum { RTE_ACL_FIELD_TYPE_MASK = 0,RTE_ACL_FIELD_TYPE_RANGE, RTE_ACL_FIELD_TYPE_BITMASK
};其中RTE_ACL_FIELD_TYPE_BITMASK与类型RTE_ACL_FIELD_TYPE_MASK，分别对应单字节的诸如协议号规则字段，和4字节如IP地址规则字段，这两者在转换为tries树节点node时，处理逻辑基本相同。类型RTE_ACL_FIELD_TYPE_RANGE对应规则中的端口范围字段，与前两者处理逻辑不同。
协议字段转换
以下函数acl_gen_mask_trie负责mask类的ACL字段转换到trie树节点node。对于RTE_ACL_FIELD_TYPE_BITMASK类型，以TCP协议号 6/0xff 为例，并且假设level等于1（ACL系统要求第一个字段为单字节，所以通常情况下协议号为第一个字段）。其size为1即一个字节。
|----------| |----------|| root | | node ||----------| |----------|level-1 level-2函数中的for循环为每一个字节数据分配一个rte_acl_node结构，并且依次递增其深度level的值。函数acl_gen_mask创建rte_acl_bitset类型的位图结构，并依据数值和掩码初始化位图。
static struct rte_acl_node * acl_gen_mask_trie(struct acl_build_context *context,const void *value, const void *mask, int size, int level, struct rte_acl_node **pend)
{struct rte_acl_node *root, *node, *prev;struct rte_acl_bitset bits;const uint8_t *val = value;const uint8_t *msk = mask;root = acl_alloc_node(context, level++);prev = root;for (n = size - 1; n >= 0; n--) {node = acl_alloc_node(context, level++);acl_gen_mask(&bits, val[n] & msk[n], msk[n]);acl_add_ptr(context, prev, node, &bits);prev = node;}*pend = prev;return root;
}对于TCP协议号6/0xff，位图生成函数acl_gen_mask，将位图bitset的第6位设置为1。由于掩码为0xff覆盖所有位，最终仅设置了第6位。由于acl_gen_mask函数处理的value和mask都是1个字节（ACL库实现步长为8bit的trie树），这里的参数定义为uint32_t感觉没有必要，函数返回值range并没有被使用到。
static int acl_gen_mask(struct rte_acl_bitset *bitset, uint32_t value, uint32_t mask)
{int range = 0;/* clear the bitset values */for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++) bitset->bits[n] = 0;/* for each bit in value/mask, add bit to set */for (n = 0; n < UINT8_MAX + 1; n++) {if ((n & mask) == value) {range++;bitset->bits[n / (sizeof(bits_t) * 8)] |= 1 << (n % (sizeof(bits_t) * 8));}}return range;
}完成位图初始化后，增加node节点关联指针。对于协议号6/0xff节点，函数acl_add_ptr将root节点的prts[0]的ptr指向第二级的node节点；与此ptr关联的value值为以上计算而来的bitset位图。由于此为root节点的第一个下级节点，root节点自身的位图值同样为0100 0000，如果之后出现分支节点，root节点自身的位图将等于所有分支位图的合集。由于trie树为8bit步长，此处的位图共256个bits，所以理论上来说，root节点最多可有256个二级分支。
static int acl_add_ptr(struct acl_build_context *context, struct rte_acl_node *node, struct rte_acl_node *ptr, struct rte_acl_bitset *bits)
{uint32_t n, num_ptrs;/* Find available ptr and add a new pointer to this node */for (n = node->min_add; n < node->max_ptrs; n++) {if (node->ptrs[n].ptr == NULL) {node->ptrs[n].ptr = ptr;acl_include(&node->ptrs[n].values, bits, 0);acl_include(&node->values, bits, -1);
}至此，协议字段proto已经完整的转换为了tries树的两个node节点，完成之后trie树节点图如下：
level-1 level-2|----------| |----------|| root | |----->| node ||----------| | |----------|| ||- ptrs[0].ptr -||- ptrs[0].value = 0100 0000|- value = 0100 0000IP地址字段装换
接下来，看一下IP地址字段的节点转换，IP地址字段属于RTE_ACL_FIELD_TYPE_MASK类型。以源IP地址39.7.6.0/24(0xffff ff00)为例，介绍其转换逻辑。与以上的协议字段相同，也是使用转换函数acl_gen_mask_trie实现，不同点在与此处size长度为4个字节。函数acl_gen_mask_trie的for循环每次处理一个字节，由最高字节开始（39）。由于之前的协议字段转换已经将node的level增加到了2，此处由level-3开始。
第一次循环创建最高字节（39）的node节点，level等于4。acl_gen_mask函数将39转换为bitset位图，由于对应的掩码为0xff，转换后位图的第39位设置为1。
|----------| |-------------|| root | | node(39) ||----------| |-------------|level-3 level-4函数acl_add_ptr，如上的介绍，建立两个node节点之间的联系，完成之后的trie树节点如下：
level-3 level-4|----------| |----------|| root | |----->| node ||----------| | |----------|| ||- ptrs[0].ptr -||- ptrs[0].value = 0x01 << 39|- value = 0x01 << 39之后的三次循环将创建剩余字节7.6.0/0xff ff00表示的node节点，如下。由于最后一个节点node-7，其值和掩码都为0，致使位图的256个位全部为1，表明查找时匹配任意值。IP地址最终的trie树节点图如下所示：
level-3 level-4 level-5 level-6 level-7|----------| |----------| |----------| |----------| |----------|| root | |-------->| node | |------>| node | |------>| node | |------>| node ||----------| | |----------| | |----------| | |----------| | |----------|| | | | | | | ||- ptrs[0].ptr -| |- ptrs[0].ptr -| |- ptrs[0].ptr -| |- ptrs[0].ptr -||- ptrs[0].value = 0x01 << 39 |- ptrs[0].value = 1000 0000 |- ptrs[0].value = 0100 0000 |- ptrs[0].value = all 1 in 256 bits|- value = 0x01 << 39 |- value = 1000 0000 |- value = 0100 0000 |- value = all 1 in 256 bits端口范围转换
最后，看一下类型RTE_ACL_FIELD_TYPE_RANGE字段转换trie树节点的处理。此类型使用函数acl_gen_range_trie转换trie树节点。以目的端口号范围字段514 : 614（0x202:0x266）为例，其size长度为2个字节。在此示例中端口范围的下限和上限值的高8位相等（都为0x2），意味着上限值的低8位一定大于下限值的低8位，在分配两个节点node之后，交由函数acl_alloc_node处理，属于比较简单的情况。由于在源IP地址处理完成后，level值增加到了7，在经过目的IP地址的node转换，level值又增加到了12，此处由level-13开始。
|----------| |-------------|| root | | pend ||----------| |-------------|level-13 level-15函数acl_gen_range_trie，在一开始就创建两个node节点，其中一个为头节点，另一个为尾节点，如上所示。对于此处讨论的端口范围（0x202:0x266），由于满足下限和上限值的高8位相等的条件，核心处理有函数acl_gen_range完成。
static struct rte_acl_node *
acl_gen_range_trie(struct acl_build_context *context, const void *min, const void *max, int size, int level, struct rte_acl_node **pend)
{struct rte_acl_node *root;const uint8_t *lo = min;const uint8_t *hi = max;*pend = acl_alloc_node(context, level+size);root = acl_alloc_node(context, level++);if (lo[size - 1] == hi[size - 1]) {acl_gen_range(context, hi, lo, size, level, root, *pend);}
}函数acl_gen_range实际上创建了一个node节点level-14。调用两次acl_add_ptr_range函数来建立两个相邻level节点之间的联系。
level-13 level-14 level-15|----------| |-------------| |-------------|| root | | node | | pend ||----------| |-------------| |-------------|由于端口字段的长度size为2个字节，函数中的for循环执行一次。
static void acl_gen_range(struct acl_build_context *context,const uint8_t *hi, const uint8_t *lo, int size, int level, struct rte_acl_node *root, struct rte_acl_node *end)
{struct rte_acl_node *node, *prev;prev = root;for (n = size - 1; n > 0; n--) {node = acl_alloc_node(context, level++);acl_add_ptr_range(context, prev, node, lo[n], hi[n]);prev = node;}acl_add_ptr_range(context, prev, end, lo[0], hi[0]);
}函数acl_add_ptr_range完成两个功能：位图的初始化，以及ptrs指针的赋值操作。对于范围限值的高8位数值（0x02），位图赋值为0x04，即第二位置1。对于范围限值的低8位（0x02:0x66），其位图为比特位由第2位到第102（0x66）位全部设置为1。
level-13 level-14 level-15 |----------| |----------| |----------| | root | |-------->| node | |------>| node | |----------| | |----------| | |----------| | | | | |- ptrs[0].ptr -| |- ptrs[0].ptr -| |- ptrs[0].value = 0000 0100 |- ptrs[0].value = all 1 in (2 - 102)bits |- value = 0000 0100 |- value = all 1 in (2 - 102)bits 函数acl_add_ptr_range如下，置位[low, high]直接的所有位。函数acl_add_ptr参见之前的介绍。
static int acl_add_ptr_range(struct acl_build_context *context,struct rte_acl_node *root, struct rte_acl_node *node, uint8_t low, uint8_t high)
{for (n = 0; n < UINT8_MAX + 1; n++)if (n >= low && n <= high)bitset.bits[n / (sizeof(bits_t) * 8)] |= 1 << (n % (sizeof(bits_t) * 8));return acl_add_ptr(context, root, node, &bitset);
}以上的端口范围（0x202:0x266）仅是比较简单的一种情况。对于端口范围274:581（0x112:0x245），与以上的示例不同，此时高8位不相等，函数acl_gen_range_trie生成的node节点如下，为保证上限值的低8位大于下限值的低8位，将以上的端口范围拆分为以下两个范围：（0x112:0x01ff）和（0x0200:0x245），创建具有两个分支的trie树。
level-13 level-14 level-15 |----------| |----------| |----------| | root | |-------->| node | |------>| node | |----------| | |----------| | |----------| | | | | |- ptrs[0].ptr -| |- ptrs[0].ptr -| |- ptrs[0].value = 0000 0100 |- ptrs[0].value = 1 in (0 - 0x45)bits |- value = 0000 0100 |- value = 1 in (0 - 0x45)bits ||| level-14 level-15 | |----------| |----------| | |----------->| node | |------>| node | | | |----------| | |----------| | | | | |- ptrs[1].ptr -| |- ptrs[0].ptr -| |- ptrs[1].value = 0000 0010 |- ptrs[0].value = 1 in (12 - 0xff)bits |- value = 0000 0010 |- value = 1 in (12 - 0xff)bits |- value = 0000 0110（最终root自身位图）总结函数acl_gen_range_trie的处理逻辑如下，其中下限值表示为Low[1]与Low[0]；上限值表示为Hi[1]与Hi[0]。索引0表示低位字节，1表示高位字节。每个端口范围生成一个trie树分支，例如对于c-1条件下，将生成具有3个分支的trie树。
a）端口范围上下限值的高位字节相等，即（Hi[1] == Low[1]）。
低位字节只有一种情况：Low[0] <= Hi[0]。生成的trie树只有一个分支，参见以上的端口范围（0x202:0x266）的介绍。
b）端口范围上下限值的高位字节差值等于1，即（Hi[1] - Low[1] == 1）。
b-1）Low[0] != 0x00，Hi[0] != 0xff。如端口范围（0x202:0x366），拆分成2个范围（0x202:0x2ff）和（0x300:0x366）。
b-2）Low[0] == 0x00，Hi[0] != 0xff。如端口范围（0x200:0x366），拆分成2个范围（0x200:0x2ff）和（0x300:0x366）。
b-3）Low[0] != 0x00，Hi[0] == 0xff。如端口范围（0x202:0x3ff），拆分成2个范围（0x202:0x2ff）和（0x300:0x3ff）。
b-4）Low[0] == 0x00，Hi[0] == 0xff。如端口范围（0x200:0x3ff），不拆分。
c）端口范围上下限值的高位字节差值大于1，即（Hi[1] - Low[1] > 1）。
c-1）Low[0] != 0x00，Hi[0] != 0xff。如端口范围（0x202:0x566），拆分成3个范围（0x202:0x2ff）和（0x300:0x4ff）和（0x500:0x566）。
c-2）Low[0] == 0x00，Hi[0] != 0xff。如端口范围（0x200:0x566），拆分成3个范围（0x200:0x2ff）和（0x500:0x566）。
c-3）Low[0] != 0x00，Hi[0] == 0xff。如端口范围（0x202:0x5ff），拆分成2个范围（0x202:0x2ff）和（0x300:0x5ff）。
c-4）Low[0] == 0x00，Hi[0] == 0xff。如端口范围（0x200:0x5ff），不拆分。
END
这篇关于DPDK ACL规则字段到tries树节点转换的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
