Dive into eBPF (1): 从 BPF 说起
近来将 eBPF 研究了一通，遂记录笔记于此文。
BPF born
eBPF 是 extended BPF 的简称，而 BPF 的全称是 Berkeley Packet Filter, 即伯克利报文过滤器，它的设计思想来源于 1992 年的一篇论文PDF。最初，BPF 是在 BSD 内核实现的，后来，由于其出色的设计思想，其他操作系统也将其引入, 包括 Linux , 有意思的是，Linux 最初将它的实现命名为 LSF (Linux Socket Filter)，看上去是想将它与 Berkeley 划清界限，不过后来可能也许觉得没什么意义，便还是沿用 BPF 这个名字了，内核文档也大方地写上了 Linux Socket Filtering aka Berkeley Packet Filter (BPF)。
那么 BPF 有什么功能呢？ 从 Berkeley Packet Filter 这个名字看，它是报文( Packet )过滤器( Filter )，而实际上，它的功能也确实如其名字一样单纯：用户可以使用它将感兴趣的报文过滤出来，也就是抓包.这有没有让你想到 tcpdump ?! 事实上，tcpdump 正是使用了 BPF，具体方式稍后本文会有描述。
为了对 BPF 有一个整体上的认识，所以让我们首先来看看 BPF 的结构图(图片来源于论文)吧
从图中可以看出，BPF 是作为内核报文传输路径的一个旁路存在的，当报文到达内核驱动程序后，内核在将报文上送协议栈的同时，会额外将报文的一个副本交给 BPF。之后，报文会经过 BPF 内部逻辑的过滤(当然，这个逻设置)，然后最终送给用户程序(比如 tcpdump)
BPF Pseudo-Machine
tcpdump 如何过滤指定的报文呢？ 举个例子，当我使用 tcpdump tcp dst port 8080 时，BPF 的过滤逻辑如何将目的端口为 8080 的 TCP 报文过滤出来? 可能最容易想到的方式就是粗暴的硬编码了, 比如像下面这样编写内核模块。
switch (protocol)
{
case (TCP):
if (dstport != 8080)
drop
......
case (UDP):
......
case (ICMP):
......
}
但是，这样的方式也太傻了，难道每次抓包都需要加载内核模块？ 这显然不是 BPF 能成为经典的原因。
BPF 采用的是一种 Pseudo-Machine 的方式。
什么是 Pseudo-Machine ? 我更愿意将这个词翻译为虚拟机，它是 BPF 过滤功能的核心逻辑。这个虚拟机并不负责，它只有一个累加器( accumulator ),一个索引寄存器 ( index register )，一小段内存空间 ( memory store )，和一个隐式的 PC 指针( implicit program counter )。
它支持的指令集也非常有限，可分为以下几类 (翻译自论文)
- LOAD 指令：将一个数值加载入 accumulator 或者 index register，这个值可以为一个立即数( immediate value )、报文的指定偏移、报文长度或者内存空间存放的值
- STORE 指令：将 accumulator 或者 index register 中存储的值存入内存空间
- ALU 指令：对 accumulator 存储的数进行逻辑或者算术运算
- BRANCH 指令：简单的 if 条件控制指令的执行流
- RETURN 指令：退出虚拟机，若返回 FALSE (0)，则表示丢弃该报文
- 其他指令：accumulator 和 index register 的值的相互传递
其支持的指令的长度也是固定的：
其中 opcode 表示指令类型，而 jt ( jump true ) 和 jf ( jump false ) 用于条件控制，它们用于 BRACH 指令中，指示如果条件为真/假时，下一条应该执行的指令。而 k 表示地址/值，这个字段在不同的 opcode 中有不同的意义。
上面这一段也许太抽象了，还是以 tcpdump tcp dst port 8080 这个例子来解释好了。
tcpdump 提供了一个内置的选项 -d，可以将匹配规则对应的 BPF 指令以易读的方式展示出来。
tcpdump -d tcp dst port 8080
root@ubuntu-1:/home/user1# tcpdump -d tcp dst port 8080
(000) ldh [12] // 以太网首部共 14 byte: DMAC(6 bytes) + SMAC(6 bytes) + Type(2 bytes), 因此这里表示将 Type 的值加载进 accumulator
(001) jeq #0x86dd jt 2 jf 6 // 将 accumulator 的值与 0x86dd (IPv6) 比较. 若为真, 则继续执行 002, 否则 jump 到指令 006
(002) ldb [20] // 将 IPv6 首部中表示传输层协议的 Next Header 加载到 accumulator
(003) jeq #0x6 jt 4 jf 15 // 将 accumulator 的值与 6 (TCP) 比较. 若为真，则继续执行 004，否则 jump 到 015
(004) ldh [56] // 将 TCP 首部中的 Destination Port 的值加载到 accumulator
(005) jeq #0x1f90 jt 14 jf 15 // 将 accumulator 的值与 0x1f90 (8080) 比较. 若为真，则 jump 到 014, 否则 jump 到 015
(006) jeq #0x800 jt 7 jf 15 // 将 accumulator 与 0x0800 (IPv4) 比较. 若为真，则继续执行 007, 否则 jump 到 015
(007) ldb [23] // 将 IPv4 首部中表示传输层协议的 Protocol 加载到 accumulator
(008) jeq #0x6 jt 9 jf 15 // 将 accumulator 的值与 6 (TCP) 比较. 若为真，则继续执行 009，否则 jump 到 015
(009) ldh [20] // 将 IPv4 首部中表示传输层协议的 Flags + Fragment Offset 加载到 accumulator
(010) jset #0x1fff jt 15 jf 11 // 将 accumulator 的值与 0x1fff 按位与(得到 Fragment Offset)，如果为真(非首片的分片报文) 则 jump 到 015, 否则继续执行 011
(011) ldxb 4*([14]&0xf) // 将 IPv4 首部中的 IHL * 4 的值加载到 index register，即得到 IPv4 首部的长度 (为了得到找到 TCP 首部的位置)
(012) ldh [x + 16] // 将 TCP 首部中的 Destination Port 的值加载到 accumulator. eg. 不包含 IP 选项时，x = 20, 那么这里就等效于 [36]
(013) jeq #0x1f90 jt 14 jf 15 // 将 accumulator 的值与 0x1f90 (8080) 比较. 若为真，则 jump 到 014, 否则 jump 到 015
(014) ret #262144 // 返回非0 表示该报文通过过滤
(015) ret #0 // 返回0 表示该报文需要丢弃
如果对上面的指令偏移有疑问，那么最好的办法就是对照协议首部的格式，请参考RFC 791: IPv6 RFC 2490: IP RFC 793: TCP
在我们使用 tcpdump 时, libpcap 会将我们的过滤语句翻译为 bpf 虚拟机能识别的机器码，然后将其下载到内核。
How BPF works in linux
我们不妨以 tcpdump 过滤抓取接收方向的数据包(skbuff)过程来看看 linux 中的 BPF 是如何工作的。
在inet socket 与 packet socket一文中，我们知道可以 tcpdump 通过创建关心所有类型 (ETH_P_ALL) 的 Packet Socket，使得报文能在 netif_receive_skb 时被 deliver_skb.
__netif_receive_skb(struct sk_buff *skb)
{
......
list_for_each_entry_rcu(ptype, &ptype_all, list) {
if (!ptype->dev || ptype->dev == skb->dev) {
if (pt_prev)
ret = deliver_skb(skb, pt_prev, orig_dev); // 里面调用 pt_prev->func(skb, skb->dev, pt_prev, orig_dev) ,
pt_prev = ptype;
}
}
......
}
Packet Socket 在创建时注册的 func 为 packet_rcv，在这里便会进行过滤操作 run_filter
static int packet_rcv(struct sk_buff *skb, struct net_device *dev,
struct packet_type *pt, struct net_device *orig_dev)
{
......
sk = pt->af_packet_priv;
......
res = run_filter(skb, sk, snaplen);
......
}
而 run_filter 的功能就是取下 sk 上设置的 sk_filter 结构, 然后 SK_RUN_FILTER 这个结构
static unsigned int run_filter(const struct sk_buff *skb,
const struct sock *sk,
unsigned int res)
{
struct sk_filter *filter;
rcu_read_lock();
filter = rcu_dereference(sk->sk_filter);
if (filter != NULL)
res = SK_RUN_FILTER(filter, skb); // For non-JIT: sk_run_filter(SKB, filter->insns) ; For JIT： (*filter->bpf_func)(SKB, filter->insns)
rcu_read_unlock();
return res;
}
这里 SK_RUN_FILTER 根据是否内核使用 JIT 有两种定义，JIT 是一种通过将 BPF 虚拟机指令码映射成主机指令，从而提升 BPF filter 性能的方式。由于本文的中心是 BPF, 因此就只考虑不使用 JIT 的情景。即这里是使用 SK_RUN_FILTER 等于调用 sk_run_filter
而 sk_run_filter 正是 BPF 虚拟机逻辑的核心。贴一段函数的开头吧，从这里可以看到 BPF 设计的 accumulator (A)， index register (X)，内存空间(mem)，而函数逻辑便是虚拟机处理指令的逻辑
unsigned int sk_run_filter(const struct sk_buff *skb,
const struct sock_filter *fentry)
{
void *ptr;
u32 A = 0; /* Accumulator */
u32 X = 0; /* Index Register */
u32 mem[BPF_MEMWORDS]; /* Scratch Memory Store */
u32 tmp;
int k;
......
}
从上面可以看出, sk_filter 是 Linux 的 BPF 实现中一个很关键的数据结构，也的确是这样，sk_filter 记录了用户设置的虚拟机指令。
struct sk_filter
{
......
unsigned int len; /* BPF 指令的数目, 也就是 insns 的长度 */
unsigned int (*bpf_func)(const struct sk_buff *skb, /* For JIT */
const struct sock_filter *filter);
......
struct sock_filter insns[0]; /* BPF 指令 */
};
那么问题来了，这个 sk_filter 中记录的指令是如何被设置的呢？ 还有 sk_filter 本身是何时被设置到 sk->sk_filter 上的呢？
答案是：通过 Socket 的 SO_ATTACH_FILTER 选项，用户可以将用户空间准备好的 BPF 虚拟机指令灌入内核.
int sock_setsockopt(struct socket *sock, int level, int optname,
char __user *optval, unsigned int optlen)
......
case SO_ATTACH_FILTER:
ret = -EINVAL;
if (optlen == sizeof(struct sock_fprog)) {
struct sock_fprog fprog;
ret = -EFAULT;
if (copy_from_user(&fprog, optval, sizeof(fprog))) // 从用户空间拷贝 BPF 虚拟机指令码
break;
ret = sk_attach_filter(&fprog, sk);
}
break;
Next：eBPF
下一篇文章，我们将正式进入 eBPF.