张亦鸣 : eBPF 简史 (上篇)

本文出处:https://www.ibm.com/developerworks/cn/linux/l-lo-eBPF-history/index.html

eBPF现在在Linux的牛逼程度应该是不用多说了,赶紧学习了。

前言

数日之前,笔者参加某一技术会议之时,为人所安利了一款开源项目,演讲者对其性能颇为称道,称其乃基于近年在内核中炙手可热的 eBPF 技术。

对这 eBPF 的名号,笔者略有些耳熟,会后遂一番搜索学习,发现 eBPF 果然源于早年间的成型于 BSD 之上的传统技术 BPF(Berkeley Packet Filter),但无论其性能还是功能已然都不是 BPF 可以比拟的了,慨叹长江后浪推前浪,前浪死在沙滩上之余,笔者也发现国内相关文献匮乏,导致 eBPF 尚不为大众所知,遂撰此文,记录近日所得,希冀可以为广大读者打开新世界的大门。

源头:一篇 1992 年的论文

考虑到 BPF 的知名度,在介绍 eBPF 之前,笔者自觉还是有必要先来回答另一个问题:

什么是 BPF?

笔者在前文中说过了,BPF 的全称是 Berkeley Packet Filter,顾名思义,这是一个用于过滤(filter)网络报文(packet)的架构。

其实 BPF 可谓是名气不大,作用不小的典范:如果笔者一开始提出 BPF 的同时还捎带上大名鼎鼎的 tcpdump 或wireshark,估计绝大部分读者都会了然了:BPF 即为 tcpdump 抑或 wireshark 乃至网络监控(Network Monitoring)领域的基石。

今天我们看到的 BPF 的设计,最早可以追溯到 1992 年刊行在 USENIX conference 上的一篇论文:The BSD Packet Filter: A New Architecture for User-level Packet Capture。由于最初版本的 BPF 是实现于BSD 系统之上的,于是在论文中作者称之为"BSD Packet Filter";后来由于 BPF 的理念渐成主流,为各大操作系统所接受,B 所代表的 BSD 便也渐渐淡去,最终演化成了今天我们眼中的 Berkeley Packet Filter。

诚然,无论 BSD 和 Berkeley 如何变换,其后的 Packet Filter 总是不变的,这两个单词也基本概括了 BPF的两大核心功能:

  1. 过滤(Filter): 根据外界输入的规则过滤报文;
  2. 复制(Copy):将符合条件的报文由内核空间复制到用户空间;

以 tcpdump 为例:熟悉网络监控(network monitoring)的读者大抵都知道 tcpdump 依赖于 pcap 库,tcpdump中的诸多核心功能都经由后者实现,其整体工作流程如下图所示:

图 1. Tcpdump 工作流程

由图 1 不难看出,位于内核之中的 BPF 模块是整个流程之中最核心的一环:它一方面接受 tcpdump 经由 libpcap 转码而来的滤包条件(Pseudo Machine Language) ,另一方面也将符合条件的报文复制到用户空间最终经由 libpcap 发送给 tcpdump。

读到这里,估计有经验的读者已经能够在脑海里大致勾勒出一个 BPF 实现的大概了,图 2 引自文献 1,读者们可以管窥一下当时 BPF 的设计:

图 2. BPF Overview

时至今日,传统 BPF 仍然遵循图 2 的路数:途经网卡驱动层的报文在上报给协议栈的同时会多出一路来传送给BPF,再经后者过滤后最终拷贝给用户态的应用。除开本文提及的 tcpdump,当时的 RARP 协议也可以利用 BPF 工作(Linux 2.2 起,内核开始提供 rarp 功能,因此如今的 RARP 已经不再需要 BPF 了)。

整体来说,BPF 的架构还是相对浅显易懂的,不过要是深入细节的话就没那么容易了:因为其中的 filter 的设计(也是文献 1中着墨最多的地方)要复杂那么一点点。

Pseudo Machine Language

估计在阅读本文之前,相当数量的读者都会误以为所谓的 Filter

的是挂在 tcpdump 末尾处的 expression 吧,类似于图 1 中的"tcp and dst port 7070"这样。但倘若我们如下文这样在 tcpdump 的调用中加入一个-d,还会发现其中大有乾坤:

清单 1 tcpdump -d

#以下代码可以在任意支持 tcpdump 的类 Unix 平台上运行,输出大同小异  
bash-3.2$ sudo tcpdump -d -i lo tcp and dst port 7070
(000) ldh [12]
(001) jeq #0x86dd jt 2 jf 6 #检测是否为 ipv6 报文,若为假(jf)则按照 ipv4 报文处理(L006)
(002) ldb [20]
(003) jeq #0x6 jt 4 jf 15 #检测是否为 tcp 报文
(004) ldh [56]
(005) jeq #0x1b9e jt 14 jf 15 #检测是否目标端口为 7070(0x1b9e),若为真(jt)则跳转 L014
(006) jeq #0x800 jt 7 jf 15 #检测是否为 ipv4 报文
(007) ldb [23]
(008) jeq #0x6 jt 9 jf 15 #检测是否为 tcp 报文
(009) ldh [20]
(010) jset #0x1fff jt 15 jf 11 #检测是否为 ip 分片(IP fragmentation)报文
(011) ldxb 4*([14]&0xf)
(012) ldh [x + 16] #找到 tcp 报文中 dest port 的所在位置
(013) jeq #0x1b9e jt 14 jf 15 #检测是否目标端口为 7070(0x1b9e),若为真(jt)则跳转 L014
(014) ret #262144 #该报文符合要求
(015) ret #0 #该报文不符合要求

根据 man page,tcpdump 的-d 会将输入的 expression 转义为一段"human readable"的"compiled packet-matching code"。当然,如清单 1 中的内容,对于很多道行不深的读者来说,基本是"human unreadable"的,于是笔者专门加入了一些注释加以解释,但是相较于-dd 和-ddd反人类的输出,这确可以称得上是"一目了然"的代码了。

这段看起来类似于汇编的代码,便是 BPF 用于定义 Filter 的伪代码,亦即图 1 中 libpcap 和内核交互的 pseudo machine language(也有一种说法是,BPF 伪代码设计之初参考过当时大行其道的 RISC 令集的设计理念),当 BPF 工作时,每一个进出网卡的报文都会被这一段代码过滤一遍,其中符合条件的(ret #262144)会被复制到用户空间,其余的(ret #0)则会被丢弃。

BPF 采用的报文过滤设计的全称是 CFG(Computation Flow Graph),顾名思义是将过滤器构筑于一套基于 if-else的控制流(flow graph)之上,例如清单 1 中的 filter 就可以用图 3 来表示:

图 3 基于 CFG实现的 filter 范例

CFG 模型最大的优势是快,参考文献 1 中就比较了 CFG 模型和基于树型结构构建出的 CSPF 模型的优劣,得出了基于 CFG模型需要的运算量更小的结论;但从另一个角度来说,基于伪代码的设计却也增加了系统的复杂性:一方面伪指令集已经足够让人眼花缭乱的了;另一方面为了执行伪代码,内核中还需要专门实现一个虚拟机(pseudo-machine),这也在一定程度上提高了开发和维护的门槛。

当然,或许是为了提升系统的易用性,一方面 BPF 设计者们又额外在 tcpdump 中设计了我们今天常见的过滤表达式(实际实现于libpcap,当然两者也都源于 Lawrence Berkeley Lab),令过滤器真正意义上"Human Readable"了起来;另一方面,由于设计目标只是过滤字节流形式的报文,虚拟机及其伪指令集的设计相对会简单不少:整个虚拟机只实现了两个 32 位的寄存器,分别是用于运算的累加器 A 和通用寄存器 X;且指令集也只有寥寥 20 来个,如表 1 所示:

Category

Opcodes

Address modes

Load Instructions

ldb

k

x+k

ldh

k

x+k

ld

#k

#len

Mk

k

x+k

ldx

#k

#len

Mk

4 * (k & 0xf)

Store Instructions

st

Mk

stx 

Mk 

ALU Instruction

add

#k

x  

 mul

#k 

x  

div 

#k 

x  

and  

#k 

x  

or  

#k 

x  

lsh 

#k 

x  

rsh 

#k 

x  

 Branch Instruction

jmp 

L  

jeq 

#k, Lt, Lf 

jgt 

#k, Lt, Lf 

jge 

#k, Lt, Lf  

 jset

#k, Lt, Lf 

易用性方面的提升很大程度上弥补了 BPF 本身的复杂度带来的缺憾,很大程度上推动了 BPF 的发展,此后数年,BPF 逐渐称为大众所认同,包括 Linux 在内的众多操作系统都开始将 BPF 引入了内核。

鉴于 Linux 上 BPF 如火如荼的大好形势,本文余下的部分笔者将基于 Linux 上的 BPF 实现进行展开。

LSF: Linux 下的BPF 实现

BPF 是在 1997 年首次被引入 Linux 的,当时的内核版本尚为 2.1.75。准确的说,Linux内核中的报文过滤机制其实是有自己的名字的:Linux Socket Filter,简称 LSF。但也许是因为 BPF 名声太大了吧,连内核文档都不大买这个帐,直言 LSF 其实就是(aka)BPF。

当然,LSF 和 BPF 除了名字上的差异以外,还是有些不同的,首当其冲的分歧就是接口:传统的 BSD 开启 BPF 的方式主要是靠打开(open)/dev/bpfX 设备,之后利用 ioctl 来进行控制;而 linux 则选择了利用套接字选项(sockopt)SO_ATTACH_FILTER/SO_DETACH_FILTER来执行系统调用,篇幅所限,这部分内容笔者就不深入了,有兴趣的读者可以通过移步socket 的 manual page或内核 filter 文档深入了解。这里笔者只给出一个例子来让读者们对 Linux 下的 BPF 的开发有一个直观的感受:

清单 2 BPF Sample

#include <……>
// tcpdump -dd 生成出的伪代码块
// instruction format:
// opcode: 16bits; jt: 8bits; jf: 8bits; k: 32bits
static struct sock_filter code[] = {
    { 0x28, 0, 0, 0x0000000c }, // (000) ldh [12]
    { 0x15, 0, 4, 0x000086dd }, // (001) jeq #0x86dd jt 2 jf 6
    { 0x30, 0, 0, 0x00000014 }, // (002) ldb [20]
    { 0x15, 0, 11, 0x00000006 }, // (003) jeq #0x6 jt 4 jf 15
    { 0x28, 0, 0, 0x00000038 }, // (004) ldh [56]
    { 0x15, 8, 9, 0x00000438 }, // (005) jeq #0x438 jt 14 jf 15
    { 0x15, 0, 8, 0x00000800 }, // (006) jeq #0x800 jt 7 jf 15
    { 0x30, 0, 0, 0x00000017 }, // (007) ldb [23]
    { 0x15, 0, 6, 0x00000006 }, // (008) jeq #0x6 jt 9 jf 15
    { 0x28, 0, 0, 0x00000014 }, // (009) ldh [20]
    { 0x45, 4, 0, 0x00001fff }, // (010) jset #0x1fff jt 15 jf 11
    { 0xb1, 0, 0, 0x0000000e }, // (011) ldxb 4*([14]&0xf)
    { 0x48, 0, 0, 0x00000010 }, // (012) ldh [x + 16]
    { 0x15, 0, 1, 0x00000438 }, // (013) jeq #0x438 jt 14 jf 15
    { 0x6, 0, 0, 0x00040000 }, // (014) ret #262144
    { 0x6, 0, 0, 0x00000000 }, // (015) ret #0
};
int main(int argc, char **argv)
{
    // ……
    struct sock_fprog bpf = { sizeof(code)/sizeof(struct sock_filter), code };
    // ……
    // 1. 创建 raw socket
    s = socket(AF_PACKET, SOCK_RAW, htons(ETH_P_ALL));
    // ……
    // 2. 将 socket 绑定给指定的 ethernet dev
    name = argv[1]; // ethernet dev 由 arg 1 传入
    memset(&addr, 0, sizeof(addr));
    addr.sll_ifindex = if_nametoindex(name);
    // ……
    if (bind(s, (struct sockaddr *)&addr, sizeof(addr))) {
        // ……
    }
    // 3. 利用 SO_ATTACH_FILTER 将 bpf 代码块传入内核
    if (setsockopt(s, SOL_SOCKET, SO_ATTACH_FILTER, &bpf, sizeof(bpf))) {
        // ……
    }
    for (; ;) {
        bytes = recv(s, buf, sizeof(buf), 0); // 4. 利用 recv()获取符合条件的报文
        // ……
        ip_header = (struct iphdr *)(buf + sizeof(struct ether_header));
        inet_ntop(AF_INET, &ip_header->saddr, src_addr_str, sizeof(src_addr_str));
        inet_ntop(AF_INET, &ip_header->daddr, dst_addr_str, sizeof(dst_addr_str));
        printf("IPv%d proto=%d src=%s dst=%s\n",
        ip_header->version, ip_header->protocol, src_addr_str, dst_addr_str);
    }
    return 0;
}

篇幅所限,清单 2 中笔者只列出了部分代码,代码分析也以注释为主。有兴趣的读者可以移步这里阅读完全版。

由于主要是和过滤报文打交道,内核中(before 3.18)的 BPF 的绝大部分实现都被放在了net/core/filter.c下,篇幅原因笔者就不对代码进行详述了,文件不长,600 来行(v2.6),比较浅显易懂,有兴趣的读者可以移步品评一下。值得留意的函数有两个,sk_attach_filter()和sk_run_filter():前者将 filter 伪代码由用户空间复制进内核空间;后者则负责在报文到来时执行伪码解析。

演进:JIT For BPF

BPF 被引入 Linux 之后,除了一些小的性能方面的调整意外,很长一段时间都没有什么动静。直到 3.0才首次迎来了比较大的革新:在一些特定硬件平台上,BPF 开始有了用于提速的 JIT(Just-In-Time) Compiler。

最先实现 JIT 的是x86平台,其后包括arm、ppc、S390、mips等一众平台纷纷跟进,到今天 Linux 的主流平台中支持 JIT For BPF 的已经占了绝大多数了。

BPF JIT 的接口还是简单清晰的:各平台的 JIT 编译函数都实现于bpf_jit_compile()之中(3.16 之后,开始逐步改为bpf_int_jit_compile()),如果 CONFIG_BPF_JIT 被打开,则传入的 BPF伪代码就会被传入该函数加以编译,编译结果被拿来替换掉默认的处理函数 sk_run_filter()。JIT 的实现不在本文讨论之列,其代码基本位于 arch/<platform>/net 之下,有致力于优化的同学可以尝试学习一下。

打开 BPF 的 JIT 很简单,只要向/proc/sys/net/core/bpf_jit_enable 写入 1 即可;对于有调试需求的开发者而言,如果写入 2 的话,还可以在内核 log 中看到载入 BPF 代码时候 JIT生成的优化代码,内核开发者们还提供了一个更加方便的工具bpf_jit_disam,可以将内核 log 中的二进制转换为汇编以便阅读。

JIT Compiler 之后,针对 BPF 的小改进不断:如将 BPF 引入 seccomp(3.4);添加一些 debug 工具如 bpf_asm 和 bpf_dbg(3.14)。不过比较革命性的大动作就要等到 3.17 了,这次的改进被称为 extended BPF,即 eBPF。

《张亦鸣 : eBPF 简史 (下篇)》

本文来源于 linuxer 微信公众号

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人人都是极客

蓝牙遥控平衡小车的制作

出于业余爱好,以及学习自动化控制PID理论,经过多种选择后决定制作平衡车进行实际操练。刚开始试着用单纯的裸机,完成直立控制,然后慢慢的又增加了屏幕显示,用于参数...

631
来自专栏杨建荣的学习笔记

关于MySQL学习大纲(r5笔记第26天)

首先需要自我反省,因为自己圈内朋友中MySQL大牛太多,自己就先班门弄斧了,莫见怪:) 前段时间很荣幸通过了YEP(Young Expert Program)的...

4118
来自专栏FD的专栏

国外整理的一套渗透测试资源合集

1173
来自专栏肖洒的博客

基于Python的微信好友分析

“如果我比别人看得远,那是因为我站在巨人的肩膀上”–不知道牛顿说了没 本文利用Python3的itchat包简单的分析了一下自己的微信好友。

762
来自专栏Vamei实验室

协议森林02 小喇叭开始广播 (以太网与WiFi协议)

“小喇叭开始广播啦”,如果你知道这个,你一定是老一辈的人。“小喇叭”是五十年代到八十年代的儿童广播节目。在节目一开始,都会有一段这样的播音:“小朋友,小喇叭开始...

18010
来自专栏维恩的派VNPIE

vn.py多账户交易系统配置思路

本文主要介绍了一个‘如何利用多个账号同时进行交易’的思路。感谢‘图扬量化’在「维恩的派」论坛内的分享!(下为原贴)

1343
来自专栏张善友的专栏

Windows Phone 7 实战第二天 二维码QRcode

越来越多的收据具备自动对焦的拍摄功能,这也意味着这些手机可以具备条码扫描功能,手机具备条码扫描功能,可以优化购物流程,快速存储电子名片(二维码)等。 QR 码是...

22410
来自专栏葡萄城控件技术团队

WinRT开发语言的功能和效率

WinRT开发有着多种选择性,就编程语言这一点就表现的很突出;这里就这一点 深入展开,探讨在WinRT开发之初如何依据各 个编程语言的特性、功能和效率来对 产品...

1806
来自专栏较真的前端

[译] 响应式脑电波 — 如何使用 RxJS、Angular、Web 蓝牙以及脑电波头戴设备来让我们的大脑做一些更酷的事

1978
来自专栏Kirito的技术分享

如何存储用户的密码才能算安全?

前段时间将一个集成了 spring-security-oauth2 的旧项目改造了一番,将 springboot 升级成了 springboot 2.0,众所周...

943

扫码关注云+社区