因为近期又得搞基于 eBPF 的 ACL，所以再次研究基于 eBPF 的 ACL 的几篇论文和一个开源项目。

以前，我研究过 「eBPF技术实践：高性能ACL」，并实现了一个 demo for 「eBPF 技术实践：高性能 ACL」 验证其中的基于 bitmap 的规则匹配算法。

不过，demo 中有缺陷，导致不能很好地在项目中落地：

1. 每次网络包去匹配 bitmap 时，都遍历一次 bitmap 进行按位与操作。
2. 规则 bpf map 的 key 是 bitmap，这里可以将 key 的内存优化一下。

是我孤陋寡闻了。同事推荐了 xdp_acl 高性能 ACL 的开源实现；我就对该 xdp_acl 开源项目进行了深入的研究。

与此同时，认真学习了以下两篇论文：

1. eBPF / XDP based firewall and packet filtering
2. Securing Linux with a Faster and Scalable Iptables

最终，我 fork 并重构了 xdp_acl 开源项目：xdp_acl，解决了那两个缺陷。

解决缺陷 1

每次查询 bpf map 后，不再及时遍历得到的 bitmap，而是收集起来；查询所有 bpf map 后，才对所收集到的 bitmap 同时进行遍历。具体步骤如下：

1. 查询源地址的 bpf map，将得到的 bitmap 存到 bitmap_array 变量中。
2. 查询目的地址的 bpf map，将得到的 bitmap 存到 bitmap_array 变量中。
3. 查询源端口的 bpf map，将得到的 bitmap 存到 bitmap_array 变量中。
4. 查询目的端口的 bpf map，将得到的 bitmap 存到 bitmap_array 变量中。
5. 查询四层协议的 bpf map，将得到的 bitmap 存到 bitmap_array 变量中。
6. 同时遍历这 5 个 bitmap；遍历时，只要拿到一个值为 ‘1’ 的比特位，即终止遍历。
7. 最终得到两个整数：第一个是 bitmap （bitmap 的真实类型是 uint64 数组）的数组索引，第二个是 uint64 整数。
8. 需要计算第二个整数的第一个值为 ‘1’ 的比特位：(n&(-n))。
9. 拿着这两个整数去查询规则 bpf map，得到最终的 action。

这是原 xdp_acl 开源项目的做法。

解决缺陷 2

解决办法有 2 种，如下。

xdp_acl 中的解法

规则 bpf map 的 key 类型如下：

1
2
3
4
5

struct rule_action_key
{
    __u64 bitmap_ffs;
    __u64 bitmap_array_index;
};

其中 bitmap_array_index 即是第一个整数，bitmap_ffs 即是第二个整数进行 (n&(-n)) 的值。

噢，xdp_acl 中规则 bpf map 的类型是 PERCPU HASH。

改良后的解法

为了追求极致的性能，特别是针对 1Mpps 的场景，规则 bpf map 的类型可以使用查询效率更高的 PERCPU ARRAY。

这就需要想办法替换 PERCPU HASH 中的 hash 算法了：

1. 所有 ACL 规则按优先级排序，得到规则数组。
2. 规则 bpf map 的索引即为 ACL 规则在数组中的索引。
3. 将 解决缺陷 1 中得到的两个整数，换算成数组索引，换算算法如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

static __always_inline __u32
get_priority(__u64 bit, __u64 index) {
    __u64 shift = 0;
    if (bit >= ((__u64)1 << 32)) {
        bit >>= 32;
        shift += 32;
    }
    if (bit >= (1 << 16)) {
        bit >>= 16;
        shift += 16;
    }
    if (bit >= (1 << 8)) {
        bit >>= 8;
        shift += 8;
    }
    if (bit >= (1 << 4)) {
        bit >>= 4;
        shift += 4;
    }
    if (bit >= (1 << 2)) {
        bit >>= 2;
        shift += 2;
    }
    if (bit == 1) {
        shift++;
    } else if (bit == 2) {
        shift += 2;
    }

    return (__u32)((index << 6) + shift) - 1; // get the index of the '1' bit in bitmap
}

其中，bit 是第二个整数进行 (n&(-n)) 的值，index 是第二个整数。

这是我参考 Go 标准库函数 bits.LeadingZeros64() 得到的算法。

不过，为了使用 改良后的解法，XDP ACL 的控制面需要做不少配套的工作，且听下回讲解。

小结

今年国庆的时间都投在重构 xdp_acl 项目中，大耗心血，也算的上有所收获吧。

所有从 xdp_acl 开源项目和那两篇论文得到的收获，都凝聚在了重构后的 xdp_acl 开源项目中。

xdp_acl 开源项目的 License 是 GPL 2.0，就不能直接复制粘贴到项目中使用了，有点麻烦；还得我在项目中重新实现一遍。