本文是由字节跳动系统部 STE 团队出品的文章。
对于 Linux 而言，iptables / nftables 是主流的网络 ACL（Access Control List）解决方案。近些年随着 eBPF 技术的快速发展，bpfilter 也被提上了日程，有望取代 iptables/nftables，成为下一代网络 ACL 的解决方案。
本文追随 bpfilter 的脚步，利用 XDP+eBPF 技术解决 iptables / nftables 性能瓶颈，提供一种高性能网络 ACL 的技术解决方案。

iptables / nftables 性能瓶颈

由于 iptables 和 nftables 的技术相似，但 iptables 相较简单，所以我们用 iptables 举例分析：

O(N)匹配

iptables 的规则样式：

# iptables -A INPUT -m set --set black_list src -j DROP

# ......省略N条规则

# iptables -A INPUT -p tcp -m multiport --dports 53,80 -j ACCEPT

# ......省略N条规则

# iptables -A INPUT -p udp --dport 53 -j ACCEPT

如上所示，若匹配 DNS 的请求报文（目的端口 53 的 udp 报文），需要依次遍历所有规则，才能匹配中。其中，ipset/multiport 等 match 项，只能减少规则数量，无法改变 O(N)的匹配方式。

协议栈丢包

iptables 常常和 ipset 结合使用，设置一些 IP 地址黑名单，防御 DDOS（distributed denial-of-service）网络攻击。对于 DDOS 这样的网络攻击，更早地丢包，就能更好地缓解 CPU 的损耗。但是用 iptables 作为防 DDOS 攻击的手段，效果往往很差。是因为 iptables 基于 netfilter 框架实现，即便是攻击报文在 netfilter 框架 PREROUTING 的 hook 点（收包路径的最早 hook 点）丢弃，也已经走过了很多 Linux 网络协议栈的处理流程。网上有比较数据，利用 XDP 技术的丢包速率要比 iptables 高 4 倍左右：

预置条件：单条 udp 流、单个 CPU 处理
CPU: i7-6700K CPU @ 4.00GHz
NIC: 50Gbit/s Mellanox-CX4
iptables 规则：iptables -t raw -I PREROUTING -m set --set black_list src -j DROP
iptables 丢包速率：4,748,646 pps
XDP：PERCPU_HASH 类型的 eBPF map，存储 IP 黑名单
XDP 丢包速率：16,939,941 pps

XDP

XDP（eXpress Data Path）是基于 eBPF 实现的高性能、可编程的数据平面技术。基本的软件架构如下图所示：

XDP 位于网卡驱动层，当数据包经过 DMA 存放到 ring buffer 之后，分配 skb 之前，即可被 XDP 处理。数据包经过 XDP 之后，会有 4 种去向：

XDP_DROP：丢包
XDP_PASS：上送协议栈
XDP_TX：从当前网卡发送出去
XDP_REDIRECT：从其他网卡发送出去

由于 XDP 位于整个 Linux 内核网络软件栈的底部，能够非常早地识别并丢弃攻击报文，具有很高的性能。这为我们改善 iptables/nftables 协议栈丢包的性能瓶颈，提供了非常棒的解决方案。

eBPF

BPF（Berkeley Packet Filter）是 Linux 内核提供的基于 BPF 字节码的动态注入技术（常应用于 tcpdump、raw socket 过滤等）。eBPF(extended Berkeley Packet Filter)是针对于 BPF 的扩展增强，丰富了 BPF 指令集，提供了 Map 的 KV 存储结构。我们可以利用 bpf（）系统调用，初始化 eBPF 的 Program 和 Map，利用 netlink 消息或者 setsockopt（）系统调用，将 eBPF 字节码注入到特定的内核处理流程中（如 XDP、socket filter 等）。如下图所示：

至此，我们高性能 ACL 的技术方向已经明确，即利用 XDP 技术在软件栈的最底层做报文的过滤。

整体架构

如下图所示，ACL 控制平面负责创建 eBPF 的 Program、Map，注入 XDP 处理流程中。其中 eBPF 的 Program 存放报文匹配、丢包等处理逻辑，eBPF 的 Map 存放 ACL 规则。

匹配算法

为了提升匹配效率，我们将所有的 ACL 规则做了预处理，将链式的规则拆分存储。规则匹配时，我们参考内核的 O(1)调度算法，在多个匹配的规则中，快速选取高优先级的规则。

规则预处理

我们以之前的 iptables 规则举例，看如何将其拆分存储。首先，将所有规则根据优先级编号。比如，例子中的规则分别编号为：1(0x1)、16(0x10)、256(0x100)。其次，将所有规则的匹配项归类拆分。比如，例子中的匹配项可以归类为：源地址、目的端口、协议。最后，将规则编号、具体匹配项分类存储到 eBPF 的 Map 中。

# ipset create black_list hash:net
# ipset add black_list 192.168.3.0/24

# iptables -A INPUT -m set --set black_list src -j DROP

# ...... 省略15条规则

# iptables -A INPUT -p tcp -m multiport --dports 53,80 -j ACCEPT

# ...... 省略240条规则

# iptables -A INPUT -p udp --dport 53 -j ACCEPT

举例说明：

规则 1 只有源地址匹配项，我们用源地址 192.168.3.0/24 作为 key，规则编号 0x1 作为 value，存储到 src Map 中。

规则 16 有目的端口、协议 2 个匹配项，我们依次将 53、80 作为 key，规则编号 0x10 作为 value，存储到 dport Map 中；将 tcp 协议号 6 作为 key，规则编号 0x10 作为 value，存储到 proto Map 中。

规则 256 有目的端口、协议 2 个匹配项，我们将 53 作为 key，规则编号 0x100 作为 value，存储到 dport Map 中；将 udp 协议号 17 作为 key，规则编号 0x100 作为 value，存储到 proto Map 中。

我们依次将规则 1、16、256 的规则编号作为 key，动作作为 value，存储到 action Map 中。

交集

需要注意的是，规则 16、256 均有目的端口为 53 的匹配项，我们应该将 16、256 的规则编号进行按位或操作，然后进行存储，即 0x10 | 0x100 = 0x110。

通配

另外，规则 1 的目的端口、协议均为通配项，我们应该将规则 1 的编号按位或追加到现有的匹配项中（图中下划线的 value 值：0x111、0x11 等）。同理，将规则 16、256 的规则编号按位或追加到现有的源地址匹配项中（图中下划线的 value 值：0x111、0x110）。至此，我们的规则预处理完成，将所有规则的匹配项、动作拆分存储到 6 个 eBPF Map 中，如上图所示。

类 O(1)匹配

报文匹配时，我们报文的 5 元组（源、目的地址，源、目的端口、协议）依次作为 key，分别查找对应的 eBPF Map，得到 5 个 value。我们将这 5 个 value 进行按位与操作，得到一个 bitmap。这个 bitmap 的每个 bit，就表示了对应的一条规则；被置位为 1 的 bit，表示对应的规则匹配成功。

举例说明：

当用报文（192.168.4.1:10000 -> 192.168.4.100:53, udp）的 5 元组作为 key，查找 eBPF Map 后，得到的 value 分别为：src_value = 0x110、dst_value = NULL、sport_value = NULL、dport_value = 0x111、proto_value = 0x101。将非 NULL 的 value 进行按位与操作，得到 bitmap = 0x100（0x110 & 0x111 & 0x101）。由于 bitmap 只有一位被置位 1（只有一条规则匹配成功，即规则 256），利用该 bitmap 作为 key，查找 action Map，得到 value 为 ACCEPT。与 iptables 的规则匹配结果一致。

同理，当报文（192.168.4.1:1000 -> 192.168.4.100:53, tcp）的 5 元组作为 key，查找 eBPF Map 后，处理的流程和上面的一致，最终匹配到规则 16。

同样，当报文（192.168.3.1:1000 -> 192.168.4.100:53, udp）的 5 元组作为 key，查找 eBPF Map 后，处理的流程和上面的一致。不同的是，得到的 bitmap = 0x101，由于 bitmap 有两位被置位 1（规则 1、256），我们应该取优先级最高的规则编号作为 key，查找 action Map。这里借鉴了内核 O(1)调度算法的思想，做如下操作：

bitmap &= -bitmap

即可取到优先级最高的 bit，如 0x101 &= -(0x101)最终等于 0x1。我们用 0x1 作为 key，查找 action Map，得到 value 为 DROP。与 iptables 的规则匹配结果一致。

总结

本文基于 Linux 内核的 XDP 机制，提出了一种改善 iptables / nftables 性能的 ACL 方案。目前 eBPF 的技术在开源社区非常流行，特性非常丰富，我们可以利用这项技术做很多有意思的事情。感兴趣的朋友可以加入我们，一起讨论交流。

参考

ACL.

https://en.wikipedia.org/wiki/Access-control_list
BPF comes to firewalls.

https://lwn.net/Articles/747551/
XDP – eXpress Data Path Used for DDoS protection.

http://people.netfilter.org/hawk/presentations/OpenSourceDays2017/XDP_DDoS_protecting_osd2017.pdf

本文转载自公众号字节跳动技术团队（ID：toutiaotechblog）。

原文链接：

https://mp.weixin.qq.com/s/25mhUrNhF3HW8H6-ES7waA

创作场景

eBPF 技术实践：高性能 ACL