eBPF 技术实践:高性能 ACL
本文是由字节跳动系统部 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.
-
BPF comes to firewalls.
-
XDP – eXpress Data Path Used for DDoS protection.
http://people.netfilter.org/hawk/presentations/OpenSourceDays2017/XDP_DDoS_protecting_osd2017.pdf