eBPF 是一个通用目的 RISC 指令集,其最初的设计目标是:用 C 语言的一个子集编写程序,然后用一个编译器后端(例如 LLVM)将其编译成 BPF 指令,稍后内核再通过一个位于内核中的(in-kernel)即时编译器(JIT Compiler)将 BPF 指令映射成处理器的原生指令(opcode ),以取得在内核中的最佳执行性能。本文将深入解析 eBPF 的指令集,展示 eBPF 从 C 语言代码到 eBPF 字节码,再经过 JIT 编译器的整个流程。在 这篇文章中 介绍了 cBPF 的原理与实现,本文主要介绍 eBPF 指令集。
在内核内部,解释器(the kernel interpreter)使用的是与 cBPF 类似、但属于另一种指令集的格式。 这种指令集格式的参考处理器原生指令集建模,因此更接近底层处理器架构, 性能更好(后面会详细介绍)。
这种新的指令集称为 “eBPF”,也叫 “internal BPF”。
注意:eBPF 这个名字源自 [e]xtended BPF(直译为“扩展的 BPF”), 它与 BPF extensions(直译为 “BPF 扩展”,见前面章节)并不是一个概念!
- eBPF 是一种指令集架构(ISA),
- BPF extensions 是早年 cBPF 中对
BPF_LD | BPF_{B,H,W} | BPF_ABS
几个指令进行 overloading 的技术。
eBPF 设计考虑
- 力求 JIT 编译时,能将 eBPF 指令一一映射到原生指令, 这种设计也给 GCC/LLVM 等编译器打开了方便之门,因为它们可以通过各自的 eBPF 后端生成优化的、与原生编译之后的代码几乎一样快的 eBPF 代码。
- 最初设计时,目标是能用 “受限的 C 语言” 来编写程序,然后 通过可选的 GCC/LLVM 后端编译成 eBPF,因此它能以两步最小的性能开销,即时映射成 现代 64 位 CPU 指令,即 C -> eBPF -> native code。
将这些指令下放到内核中可以带来如下好处:
- 无需在内核/用户空间切换 就可以实现内核的可编程。例如,Cilium 这种和网络相关 的 BPF 程序能直接在内核中实现灵活的容器策略、负载均衡等功能,而无需将包送先到用户空间,处理之后再送回内核。需要在 BPF 程序之间或内核/用户空间之间共享状态时,可以使用 BPF map。
- 可编程 datapath 具有很大的灵活性,因此程序能在编译时将不需要的特性禁用掉, 从而极大地优化程序的性能。例如,如果容器不需要 IPv4,那编写 BPF 程序时就可以 只处理 IPv6 的情况,从而节省了快速路径(fast path)中的资源。
- 对于网络场景(例如 tc 和 XDP),BPF 程序可以在无需重启内核、系统服务或容器的情况下实现原子更新,并且不会导致网络中断。另外,更新 BPF map 不会导致程序 状态(program state)的丢失。
- BPF 给用户空间提供了一个稳定的ABI,而且不依赖任何第三方内核模块。BPF 是 Linux 内核的一个核心组成部分,而 Linux 已经得到了广泛的部署,因此可以保证现 有的 BPF 程序能在新的内核版本上继续运行。这种保证与系统调用(内核提供给用 户态应用的接口)是同一级别的。另外,BPF 程序在不同平台上是可移植的。
- BPF 程序与内核协同工作,复用已有的内核基础设施(例如驱动、netdevice、 隧道、协议栈和 socket)和工具(例如 iproute2),以及内核提供的安全保证。和内核模块不同,BPF 程序会被一个位于内核中的校验器(in-kernel verifier)进行校验, 以确保它们不会造成内核崩溃、程序永远会终止等等。例如,XDP 程序会复用已有的内核驱动,能够直接操作存放在 DMA 缓冲区中的数据帧,而不用像某些模型(例如 DPDK) 那样将这些数据帧甚至整个驱动暴露给用户空间。而且,XDP 程序复用内核协议栈而 不是绕过它。BPF 程序可以看做是内核设施之间的通用“胶水代码”,用于设计巧妙的程序 ,解决特定的问题。
BPF 程序在内核中的执行总是事件驱动的!例如:
- 如果网卡的 ingress 路径上 attach 了 BPF 程序,那当网卡收到包之后就会触发这 个 BPF 程序的执行。
- 在某个有 kprobe 探测点的内核地址 attach 一段 BPF 程序后,当 内核执行到这个地址时会发生陷入(trap),进而唤醒 kprobe 的回调函数,后 者又会触发 attach 的 BPF 程序的执行。
cBPF->eBPF 自动转换
下列 cBPF 的经典使用场景中:
- seccomp BPF
- classic socket filters
- cls_bpf traffic classifier
- team driver’s classifier for its load-balancing mode
- netfilter’s xt_bpf extension
- PTP dissector/classifier
- and much more.
cBPF 已经在内核中被透明地转换成了 eBPF,然后在 eBPF 解释器中执行。
在 in-kernel handlers 中,可以使用下面的函数:
bpf_prog_create()
创建过滤器;bpf_prog_destroy()
销毁过滤器。
BPF_PROG_RUN(filter, ctx)
执行过滤代码,它或者透明地触发 eBPF 解释器执行,或者执行 JIT 编译之后的代码。
filter
是bpf_prog_create()
的返回值,类型是struct bpf_prog *
类型;ctx
是程序上下文(例如 skb 指针)。
在转换成新指令之前,会通过 bpf_check_classic()
检查 cBPF 程序是否有问题。
当前,在大部分 32 位架构上,都是用 cBPF 格式做 JIT 编译; 而在 x86-64, aarch64, s390x, powerpc64, sparc64, arm32, riscv64, riscv32 架构上,直接从 eBPF 指令集执行 JIT 编译。
eBPF 相比 cBPF 的核心变化
寄存器数量从 2 个增加到 10 个
- 老格式(cBPF)只有两个寄存器 A 和 X,以及一个隐藏的栈指针(frame pointer)。
- 新格式(eBPF)扩展到了 10 个内部寄存器,以及一个只读的栈指针。
传参寄存器数量
由于 64 位 CPU 都是通过寄存器传递函数参数的,因此从 eBPF 程序 传给内核函数(in-kernel function)的参数数量限制到 5 个,另有 一个寄存器用来接收内核函数的返回值,
考虑到具体的处理器架构,
x86_64
有 6 寄存器用于传参,6 个被调用方(callee)负责保存的寄存器;- aarch64/sparcv9/mips64 有 7-8 个传参寄存器,11 个被调用方(callee)负责保存的寄存器。
BPF 由下面几部分组成:
- 11 个 64 位寄存器(这些寄存器包含 32 位子寄存器)
- 一个程序计数器(program counter,PC)
- 一个 512 字节大小的 BPF 栈空间
寄存器的名字从 r0
到 r10
。默认的运行模式是 64 位,32 位子寄存器只能 通过特殊的 ALU(arithmetic logic unit)访问。向 32 位子寄存器写入时,会用 0 填充 到 64 位。
r10
是唯一的只读寄存器,其中存放的是访问 BPF 栈空间的栈帧指针(frame pointer) 地址。r0
- r9
是可以被读/写的通用目的寄存器。
BPF 程序可以调用核心内核(而不是内核模块)预定义的一些辅助函数。BPF 调用约定 定义如下:
r0
存放被调用的辅助函数的返回值r1
-r5
存放 BPF 调用内核辅助函数时传递的参数r6
-r9
由被调用方(callee)保存,在函数返回之后调用方(caller)可以读取
BPF 调用约定足够通用,能够直接映射到 x86_64
、arm64
和其他 ABI,因此所有 的 BPF 寄存器可以一一映射到硬件 CPU 寄存器,JIT 只需要发出一条调用指令,而不 需要额外的放置函数参数(placing function arguments)动作。这套约定在不牺牲性能的 前提下,考虑了尽可能通用的调用场景。目前不支持 6 个及以上参数的函数调用,内核中 BPF 相关的辅助函数(从 BPF_CALL_0()
到 BPF_CALL_5()
函数)也特意设计地与此相 匹配。
r0
寄存器还用于保存 BPF 程序的退出值。退出值的语义由程序类型决定。另外, 当将执行权交回内核时,退出值是以 32 位传递的。
r1
- r5
寄存器是 scratch registers,意思是说,如果要在多次辅助函数调用之 间重用这些寄存器内的值,那 BPF 程序需要负责将这些值临时转储(spill)到 BPF 栈上 ,或者保存到被调用方(callee)保存的寄存器中。Spilling(倒出/泼出/溅出/涌出) 的意思是这些寄存器内的变量被移到了 BPF 栈中。相反的操作,即将变量从 BPF 栈移回寄 存器,称为 filling(填充)。spilling/filling 的原因是寄存器数量有限。
BPF 程序开始执行时,r1
寄存器中存放的是程序的上下文(context)。上下文就是 程序的输入参数(和典型 C 程序的 argc/argv
类似)。BPF 只能在单个上下文中 工作(restricted to work on a single context)。这个上下文是由程序类型定义的, 例如,网络程序可以将网络包的内核表示(skb
)作为输入参数。
BPF 的通用操作都是 64 位现在的,这和默认的 64 位架构模型相匹配,这样可以对指针进 行算术操作,以及在调用辅助函数时传递指针和 64 位值;另外,BPF 还支持 64 位原子操 作。
每个 BPF 程序的最大指令数限制在 4096 条以内,这意味着从设计上就可以保证每 个程序都会很快结束。虽然指令集中包含前向和后向跳转,但内核中的 BPF 校验器禁止 程序中有循环,因此可以永远保证程序会终止。因为 BPF 程序运行在内核,校验器的工作 是保证这些程序在运行时是安全的,不会影响到系统的稳定性。这意味着,从指令集的角度 来说循环是可以实现的,但校验器会对其施加限制。另外,BPF 中有尾调用的概念,允许一 个 BPF 程序调用另一个 BPF 程序。类似地,这种调用也是有限制的,目前上限是 32 层调 用;现在这个功能常用来对程序逻辑进行解耦,例如解耦成几个不同阶段。
eBPF 调用约定
因此,eBPF 调用约定(calling convention)定义如下:
- R0 - return value from in-kernel function, and exit value for eBPF program
- R1 - R5 - arguments from eBPF program to in-kernel function
- R6 - R9 - callee saved registers that in-kernel function will preserve
- R10 - read-only frame pointer to access stack
这样的设计,使所有的 eBPF 寄存器都能一一映射到 x86_64、aarch64 等架构上的硬件寄存器,eBPF 调用约定也直接映射到 64 位的内核 ABI。
在 32 位架构上,JIT 只能编译那些只使用了 32bit 算术操作的程序,其他更复杂的程序,交给解释器来执行。
寄存器位宽从 32bit 扩展到 64bit
原来的 32bit ALU 操作仍然是支持的,通过 32bit 子寄存器执行。 所有 eBPF 寄存器都是 64bit 的,如果对 32bit 子寄存器有写入操作,它会被 zero-extend 成 64bit。 这种行为能直接映射到 x86_64 和 arm64 子寄存器的定义,但对其他处理器架构来说,JIT 会更加困难。
32-bit 的处理器架构上,通过解释器执行 64-bit 的 eBPF 程序。这种平台上的 JIT 编译器 只能编译那些只使用了 32bit 子寄存器的程序,其他不能编译的程序,通过解释器执行。
eBPF 操作都是 64 位的,原因:
- 64 位处理器架构上指针也是 64 位的,我们希望与内核函数交互时,输入输出的都是 64 位值。如果使用 32 位 eBPF 寄存器,就需要定义 register-pair ABI,导致无法 直接将 eBPF 寄存器映射到物理寄存器,JIT 就必须为与函数调用相关的每个寄存器承 担 拼装/拆分/移动 等等操作,不仅复杂,而且很容易产生 bug,效率也很低。
- 另一个原因是 eBPF 使用了 64 位的原子计数器(atomic 64-bit counters)。
条件跳转:jt/fall-through
取代 jt/jf
cBPF 的设计中有条件判断:
1 | if (cond) |
现在被下面的结构取代了:
1 | if (cond) |
引入 bpf_call
指令和寄存器传参约定,实现零(额外)开销内核函数调用
引入的寄存器传参约定,能实现 零开销内核函数调用(zero overhead calls from/to other kernel functions)。
在调用内核函数之前,eBPF 程序需要按照调用约定,将参数依次放到 R1-R5 寄存器; 然后解释器会从这些寄存器读取参数,传递给内核函数。
原理:JIT 实现零(额外)开销内核函数调用
如果 R1-R5 能一一映射到处理器上的寄存器,JIT 编译器就无需 emit 任何额外的指令:
- 函数参数已经在(硬件处理器)期望的位置;
- 只需要将 eBPF
BPF_CALL
JIT 编译成一条处理器原生的call
指令就行了。 - 这种无性能损失的调用约定设计,足以覆盖大部分场景。
函数调用结束后,R1-R5 会被重置为不可读状态(unreadable),函数返回值存放在 R0。 R6-R9 是被调用方(callee)保存的,因此函数调用结束后里面的值是可读的。
示例解析(一):eBPF/C 函数混合调用,JIT 生成的 x86_64 指令
考虑下面的三个 C 函数:
1 | u64 f1() { return (*_f2)(1); } |
GCC 能将 f1 和 f3 编译成 x86_64:
1 | f1: |
f2 的 eBPF 代码可能如下:
1 | f2: |
- 如果 f2 是 JIT 编译的,函数地址保存为变量
_f2
,那调用链f1 -> f2 -> f3
及返回就都是连续的。 - 如果没有 JIT,就需要调用解释器
__bpf_prog_run()
来调用执行 f2。
出于一些实际考虑,
- 所有 eBPF 程序都只有一个参数
ctx
,放在 R1 寄存器中,例如__bpf_prog_run(ctx)
。 - 函数调用最多支持传递 5 个参数,但如果将来有需要,这个限制也可以进一步放宽。
eBPF 寄存器到 x86_64 硬件寄存器一一映射关系
在 64 位架构上,所有寄存器都能一一映射到硬件寄存器。例如,由于 x86_64 ABI 硬性规定了
- rdi、rsi、rdx、rcx、r8、 r9 寄存器作为参数传递;
- rbx,以及 r12 - r15 由被调用方(callee)保存;
因此 x86_64 编译会做如下映射:
1 | R0 -> rax |
示例解析(二):C 调 eBPF 代码编译成 x86_64 汇编后的样子
根据上面的映射关系,下面的 BPF 程序:
1 | // BPF 指令格式: |
在 JIT 成 x86_64 之后,可能长下面这样:
将 “eBPF 寄存器 -> x86_64 硬件寄存器” 映射关系贴到这里方便下面程序对照
1
2
3
4
5
6
7
8
9
10
11 R0 -> rax
R1 -> rdi // 传参,调用方(caller)保存
R2 -> rsi // 传参,调用方(caller)保存
R3 -> rdx // 传参,调用方(caller)保存
R4 -> rcx // 传参,调用方(caller)保存
R5 -> r8 // 传参,调用方(caller)保存
R6 -> rbx // 被调用方(callee)保存
R7 -> r13 // 被调用方(callee)保存
R8 -> r14 // 被调用方(callee)保存
R9 -> r15 // 被调用方(callee)保存
R10 -> rbp // 被调用方(callee)保存
1 | // x86_64 指令格式:注意源和目的寄存器的顺序与 BPF 指令是相反的 |
下面是对应的 C 代码:
1 | u64 bpf_filter(u64 ctx) { |
内核函数 foo()
和 bar()
原型:
1 | u64 (*)(u64 arg1, u64 arg2, u64 arg3, u64 arg4, u64 arg5); |
它们从规定好的寄存器中获取传入参数,并将函数返回值放到 %rax
寄存器,也就是 eBPF 中的 R0 寄存器。 起始和结束的汇编片段(prologue and epilogue)是由 JIT emit 出来的,是解释器内置的。
上面添加了对起始汇编片段的一些解读,尤其是:为什么 “eBPF 虚拟机的最大栈空间是 512 字节”。 译注。
R0-R5 are scratch registers,因此 eBPF 程序需要在多次函数调用之间保存这些值。 下面这个程序例子是不合法的:
1 | bpf_mov R1, 1 |
在执行 call
之后,寄存器 R1-R5 包含垃圾值,不能读取。 内核中的校验器(in-kernel eBPF verifier)负责验证 eBPF 程序的合法性。
eBPF 程序最大指令数限制
eBPF 最初限制最大指令数 4096,现在已经将这个限制放大到了 100 万条。
cBPF 和 eBPF 都是两操作数指令(two operand instructions),有助于 JIT 编译时将 eBPF 指令一一映射成 x86 指令。
eBPF 程序上下文(ctx)参数
触发解释器执行时,传递给它的上下文指针(the input context pointer)是一个通用结构体, 结构体中的信息是由具体场景来解析的。例如
- 对于 seccomp 来说,R1(也就是
ctx
)指向 seccomp_data, - 对于 eBPF filter(包括从 cBPF 转换过来的)来说,R1 指向一个 skb。
cBPF -> eBPF 转换若干问题
内部的 cBPF -> eBPF 转换格式如下:
1 | op:16, jt:8, jf:8, k:32 ==> op:8, dst_reg:4, src_reg:4, off:16, imm:32 |
- 目前已经实现了 87 条 eBPF 指令;
- 8bit 的
op
字段最多支持 256 条,因此还有扩展空间,可用于增加新指令; - Some of them may use 16/24/32 byte encoding;
- eBPF 指令必须是 8 字节对齐的,以保持后向兼容。
eBPF 是一个通用目的 RISC 指令集。在将 cBPF 转成 eBPF 的过程中 ,不是每个寄存器和每条指令都会用到。例如,
- socket filters 没有用到
exclusive add
指令,而 tracing filters 可能会在维护 事件计数器时用到这种 add; - socket filters 也没有用到 R9 寄存器,但更加复杂的 filters 可能会用完所有的寄 存器(还不够),因此还有用的 spill/fill to stack 之类的技术。
某种意义上来说,eBPF 作为一个通用汇编器(generic assembler), 是性能优化的最后手段,
- socket filters 和 seccomp 就是把它当做汇编器在用;
- Tracing filters 可以用它作为汇编器,从内核生成代码。
eBPF 的安全性
内核内使用(in kernel usage)可能没有安全顾虑,因为生成的 eBPF 代码只是用于优化 内核内部代码路径,不会暴露给用户空间。eBPF 的安全问题可能会出自校验器本身(TBD )。因此在上述这些场景,可以把它作为一个安全的指令集来使用。
与 cBPF 类似,eBPF 运行在一个确定性的受控环境中,内核能依据下面两个步骤,轻松地对 程序的安全性作出判断:
- 首先进行深度优先搜索(depth-first-search),禁止循环;其他 CFG 验证。
- 以上一步生成的指令作为输入,遍历所有可能的执行路径。具体说 就是模拟每条指令的执行,观察寄存器和栈的状态变化。
opcode encoding
为方便 cBPF 到 eBPF 的转换,eBPF 复用了 cBPF 的大部分 opcode encoding。
算术和跳转指令
对于算术和跳转指令(arithmetic and jump instructions),eBPF 的 8bit op
字段进一步分为三部分:
1 | +----------------+--------+--------------------+ |
最后的 3bit 表示的是指令类型,包括:
1 | =================== =============== |
BPF_ALU 和 BPF_JMP 的 operand
当 BPF_CLASS(code) == BPF_ALU or BPF_JMP
时,第 4 bit 表示的源操作数(source operand)可以是:
1 | BPF_K 0x00 // 32bit 立即数作为源操作数(use 32-bit immediate as source operand),对 cBPF/eBPF 一样 |
BPF_ALU 和 BPF_ALU64 (eBPF) 的 opcode
BPF_CLASS(code) == BPF_ALU or BPF_ALU64 [ in eBPF ]
, BPF_OP(code)
可以是:
1 | BPF_ADD 0x00 |
BPF_JMP 和 BPF_JMP32 (eBPF) 的 opcode
BPF_CLASS(code) == BPF_JMP or BPF_JMP32 [ in eBPF ]
,BPF_OP(code)
可以是:
1 | BPF_JA 0x00 /* BPF_JMP only */ |
指令 BPF_ADD | BPF_X | BPF_ALU
在 cBPF 和 eBPF 中都表示 32bit 加法:
- cBPF 中只有两个寄存器,因此它表示的是
A += X
; - eBPF 中表示的是
dst_reg = (u32) dst_reg + (u32) src_reg
。
类似的,BPF_XOR | BPF_K | BPF_ALU
表示:
- cBPF 中:
A ^= imm32
; - eBPF 中:
src_reg = (u32) src_reg ^ (u32) imm32
。
BPF_MISC 与 BPF_ALU64(eBPF 64bit 寄存器加法操作)
cBPF 用 BPF_MISC 类型表示 A = X 和 X = A 操作。
eBPF 中与此对应的是 BPF_MOV | BPF_X | BPF_ALU
。 由于 eBPF 中没有 BPF_MISC 操作,因此 class 7 空出来了,用作了新指令类型 BPF_ALU64,表示 64bit BPF_ALU 操作。 因此,BPF_ADD | BPF_X | BPF_ALU64
表示 64bit 加法,例如 dst_reg = dst_reg + src_reg
。
cBPF/eBPF BPF_RET 指令的不同
cBPF 用整个 BPF_RET class 仅仅表示一个 ret
操作,非常浪费。 其 BPF_RET | BPF_K
表示将立即数 imm32 拷贝到返回值寄存器,然后退出函数。
eBPF 是模拟 CPU 建模的,因此 eBPF 中 BPF_JMP | BPF_EXIT
只表示退出函数操作。 eBPF 程序自己负责在执行 BPF_EXIT 之前,将返回值拷贝到 R0。
BPF_JMP 与 eBPF BPF_JMP32
Class 6 in eBPF 用作 BPF_JMP32,表示的意思与 BPF_JMP 一样,但操作数是 32bit 的。
加载指令(load/store)
load and store 指令的 8bit code 进一步分为三部分:
1 | +--------+--------+-------------------+ |
2bit 的 size modifier 可以是:
1 | BPF_W 0x00 /* word */ |
表示的是 load/store 操作的字节数:
1 | B - 1 byte |
Mode modifier 可以是:
1 | BPF_IMM 0x00 /* used for 32-bit mov in classic BPF and 64-bit in eBPF */ |
两个 eBPF non-generic 指令:BPF_ABS 和 BPF_IND,用于访问 skb data
eBPF 有两个 non-generic 指令,用于兼容 cBPF:
BPF_ABS | <size> | BPF_LD
BPF_IND | <size> | BPF_LD
二者用来访问数据包中的数据(packet data)。
- 这两个指令 cBPF 中就有了,必须 eBPF 也必须要支持,而且 eBPF 解释器还要高效地执行这两条指令。
- 执行这个两个指令时,传递给解释器的上下文必须是
struct *sk_buff
, 并且隐含了 7 个操作数:- R6 作为隐式输入,存放的必须是
struct *sk_buff
; - R0 作为隐式输出,存放的是从包中读取的数据;
- R1-R5 作为 scratch registers,不能在多次
BPF_ABS | BPF_LD
或BPF_IND | BPF_LD
指令之间在这几个寄存器中保存数据(每次调用执行之后,都会将这些寄存器置空);
- R6 作为隐式输入,存放的必须是
- 这些指令还有隐含的程序退出条件。当 eBPF 程序试图访问数据包边界之外的数据时,解释器 会终止(abort)程序的执行。因此,eBPF JIT 编译器也必须实现这个特性。
src_reg
和 imm32 字段是这些指令的显式输入。
看个例子,BPF_IND | BPF_W | BPF_LD
翻译成 C 语言表示: R0 = ntohl(\*(u32 \*) (((struct sk_buff \*) R6)->data + src_reg + imm32))
。 过程中会用到 R1-R5(R1-R5 were scratched)。
通用 eBPF load/store 指令
与 cBPF 指令集不同,eBPF 有通用 load/store 操作:
1 | BPF_MEM | <size> | BPF_STX: *(size *)(dst_reg + off) = src_reg |
其中,size 是:
BPF_B
BPF_H
BPF_W
BPF_DW
注意:这里不支持 1 或 2 字节的原子递增操作。
加载 64bit 立即数的 eBPF 指令
eBPF 有一个 16-byte instruction: BPF_LD | BPF_DW | BPF_IMM
,功能是将 64bit 立即数(imm64)加载到寄存器:
- 这条指令由两个连续
struct bpf_insn
8-byte blocks 组成,会被解释器解释为单个指令, - 功能就是上面提到的,将一个 64bit 立即值 load 到
dst_reg
。
cBPF 中有一个类似指令 BPF_LD | BPF_W | BPF_IMM
,功能是将一个 32bit 立即值(imm)加载到寄存器。
eBPF verifier
eBPF 程序的安全是通过两个步骤来保证的:
- 首先做一次 DAG 检查,确保没有循环,并执行其他 CFG validation。特别地,这会检查程序中是否有 无法执行到的指令(unreachable instructions,虽然 cBPF checker 是允许的)。
- 第二步是从程序的第一条指令开始,遍历所有的可能路径。这一步会模拟执行每一条指令,在过程中观察寄存器和栈的状态变化。
模拟执行
程序开始时,R1 中存放的是上下文指针(
ctx
),类型是PTR_TO_CTX
。- 接下来,如果校验器看到 R2=R1,那 R2 的类型也变成了 PTR_TO_CTX,并且接下来就能用在表达式的右侧。
- 如果 R1=PTR_TO_CTX 接下来的指令是 R2=R1+R1,那 R2=SCALAR_VALUE, 因为两个合法指针相加,得到的是一个非法指针。(在 “secure” 模式下, 校验器会拒绝任何类型的指针运算,以确保内核地址不会泄露给 unprivileged users)。
从来没有写入过数据的寄存器是不可读的,例如:
1
2bpf_mov R0 = R2
bpf_exit将会被拒绝,因为程序开始之后,R2 还没有初始化过。
内核函数执行完成后,R1-R5 将被重置为不可读状态,R0 保存函数的返回值。
由于 R6-R9 是被调用方(callee)保存的,因此它们的状态在函数调用结束之后还是有效的。
1
2
3
4bpf_mov R6 = 1
bpf_call foo
bpf_mov R0 = R6
bpf_exit以上程序是合法的。如果换成了
R0 = R1
,就会被拒绝。
load/store 指令检查
load/store 指令只有当寄存器类型合法时才能执行,这里的类型包括 PTR_TO_CTX、PTR_TO_MAP、PTR_TO_STACK。会对它们做边界和对齐检查。例如:
1 | bpf_mov R1 = 1 |
将会被拒,因为执行到第三行时,R1 并不是一个合法的指针类型。
定制化校验器,限制程序只能访问 ctx
特定字段
程序开始时,R1 类型是 PTR_TO_CTX(指向通用类型 struct bpf_context
的指针)。 可以通过 callback 定制化校验器,指定 size 和对齐,来 限制 eBPF 程序只能访问 ctx 的特定字段。 例如,下面的指令:
1 | bpf_ld R0 = *(u32 *)(R6 + 8) |
- 如果 R6=PTR_TO_CTX,通过
is_valid_access()
callback,校验器就能知道从 offset 8 处读取 4 个字节的操作是合法的,否则,校验器就会拒绝这个程序。 - 如果 R6=PTR_TO_STACK,那访问就应该是对齐的,而且在栈空间范围内,即
[-MAX_BPF_STACK, 0)
。在这里例子中 offset 是 8,因此校验会失败,因为超出 栈空间边界。
读取栈空间
只有程序向栈空间写入数据后,校验器才允许它从中读取数据。cBPF 通过 M[0-15]
memory slots 执行类似的检查,例如
1 | bpf_ld R0 = *(u32 *)(R10 - 4) |
是非法程序。因为虽然 R10 是只读寄存器,类型 PTR_TO_STACK 也是合法的,并且 R10 - 4
也在栈边界内,但在这次读取操作之前,并没有往这个位置写入数据。
其他
指针寄存器(pointer register)spill/fill 操作也会被跟踪,因为 对一些程序来说,四个 (R6-R9) callee saved registers 显然是不够的。
可通过
bpf_verifier_ops->get_func_proto()
来定制允许执行哪些函数。 eBPF 校验器会检查寄存器与参数限制是否匹配。调用结束之后,R0 用来存放函数返回值。函数调用是扩展 eBPF 程序功能的主要机制,但每种类型的 BPF 程 序能用到的函数是不同的,例如 socket filters 和 tracing 程序。
如果一个函数设计成对 eBPF 可见的,那必须从安全的角度对这个函数进行考量。校验 器会保证调用该函数时,参数都是合法的。
cBPF 中, seccomp 的安全限制与 socket filter 是不同的,它依赖两个级联的校验器:
- 首先执行 cBPF verifier,
- 然后再执行 seccomp verifier
而在 eBPF 中,所有场景都共用一个(可配置的)校验器。
更多关于 eBPF 校验器的信息,可参考 kernel/bpf/verifier.c。
register value tracking
为保证 eBPF 程序的安全,校验器必须跟踪每个寄存器和栈上每个槽位 (stack slot)值的范围。这是通过 struct bpf_reg_state
实现的,定义在 include/linux/bpf_verifier.h, 它统一了对标量和指针类型的跟踪(scalar and pointer values)。
每个寄存器状态都有一个类型,
NOT_INIT
:该寄存器还未写入数据SCALAR_VALUE
:标量值,不可作为指针- 指针类型
9 种指针类型
依据它们指向的数据结构类型,又可以分为:
PTR_TO_CTX
:指向bpf_context
的指针。CONST_PTR_TO_MAP
:指向struct bpf_map
的指针。 是常量(const),因为不允许对这种类型指针进行算术操作。PTR_TO_MAP_VALUE
:指向 bpf map 元素的指针。PTR_TO_MAP_VALUE_OR_NULL
:指向 bpf map 元素的指针,可为 NULL。 访问 map 的操作会返回这种类型的指针。禁止算术操作。PTR_TO_STACK
:帧指针(Frame pointer)。PTR_TO_PACKET
:指向skb->data
的指针。PTR_TO_PACKET_END
:指向skb->data + headlen
的指针。禁止算术操作。PTR_TO_SOCKET
:指向struct bpf_sock_ops
的指针,内部有引用计数。PTR_TO_SOCKET_OR_NULL
:指向struct bpf_sock_ops
的指针,或 NULL。socket lookup 操作会返回这种类型。有引用计数, 因此程序在执行结束时,必须通过 socket release 函数释放引用。禁止算术操作。
这些指针都称为 base 指针。
指针偏移(offset)触发寄存器状态更新
实际上,很多有用的指针都是 base 指针加一个 offset(指针算术运算的结果), 这是通过两方面来个跟踪的:
- ‘fixed offset’(固定偏移):offset 是个常量(例如,立即数)。
- ‘variable offset’(可变偏移):offset 是个变量。这种类型还用在 SCALAR_VALUE 跟踪中,来跟踪寄存器值的可能范围。
校验器对可变 offset 的知识包括:
- 无符号类型:最小和最大值;
- 有符号类型:最小和最大值;
- 关于每个 bit 的知识,以 ‘tnum’ 的格式: 一个 u64 ‘mask’ 加一个 u64 ‘value’。
1s in the mask represent bits whose value is unknown; 1s in the value represent bits known to be 1. Bits known to be 0 have 0 in both mask and value; no bit should ever be 1 in both。 例如,如果从内存加载一个字节到寄存器,那该寄存器的前 56bit 已知是全零,而后 8bit 是未知的 —— 表示为 tnum (0x0; 0xff)
。如果我们将这个值与 0x40 进行 OR 操作,就得到 (0x40; 0xbf)
;如果加 1 就得到 (0x0; 0x1ff)
,因为可能的进位操 作。
条件分支触发寄存器状态更新
除了算术运算之外,条件分支也能更新寄存器状态。例如,如果判断一个 SCALAR_VALUE 大于 8,那
- 在 true 分支,这个变量的最小值
umin_value
(unsigned minimum value)就是 9; - 在 false 分支,它的最大值就是 umax_value of 8。
有符号比较触发寄存器状态更新
有符号比较(BPF_JSGT or BPF_JSGE)也会相应更新有符号变量 的最大最小值。
有符合和无符号边界的信息可以结合起来;例如如果一个值先判断小于无 符号 8,后判断大于有符合 4,校验器就会得出结论这个值大于无符号 4,小于有符号 8 ,因为这个边界不会跨正负边界。
struct bpf_reg_state
的 id
字段
struct bpf_reg_state
结构体有一个 id
字段,
1 | // include/linux/bpf_verifier.h |
如注释所述,该字段针对不同指针类型有不同用途,下面分别解释。
PTR_TO_PACKET
id
字段对共享同一 variable offset 的多个 PTR_TO_PACKET 指针 都是可见的,这对skb 数据的范围检查非常重要。举个例子:
1 | 1: A = skb->data // A 是指向包数据的指针 |
在这个程序中,寄存器 A 和 B 将将共享同一个 id
,
- A 已经从最初地址向前移动了 4 字节(有一个固定偏移 +4),
- 如果这个边界通过校验了,也就是确认小于
PTR_TO_PACKET_END
,那现在 寄存器 B 将有一个范围至少为 4 字节的可安全访问范围。
更多关于这种指针的信息,见下面的 ‘Direct packet access’ 章节。
PTR_TO_MAP_VALUE
与上面的用途类型,具体来说:
- 这一字段对共享同一基础指针的多个 PTR_TO_MAP_VALUE 指针可见;
- 这些指针中,只要一个指针经验证是非空的,就认为其他指针(副本)都是非空的(因此减少重复验证开销);
另外,与 range-checking 类型,跟踪的信息(the tracked information)还用于确保指针访问的正确对齐。 例如,在大部分系统上,packet 指针都 4 字节对齐之后再加 2 字节。如果一个程序将这个指针加 14(跳过 Ethernet header)然后读取 IHL,并将指针再加上 IHL * 4
,最终的指针将有一个 4n + 2
的 variable offset,因此,加 2 (NET_IP_ALIGN
) gives a 4-byte alignment,因此通过这个指针进行 word-sized accesses 是安全的。
PTR_TO_SOCKET
与上面用途类似,只要一个指针验证是非空的,其他共享同一 id
的 PTR_TO_SOCKET 指针就都是非空的;此外, 还负责跟踪指针的引用(reference tracking for the pointer)。
PTR_TO_SOCKET 隐式地表示对一个 struct sock
的引用。为确保引用没有泄露,需要强制对引用进行非空(检查), 如果非空(non-NULL),将合法引用传给 socket release 函数。
直接数据包访问(direct packet access)
对于 cls_bpf 和 act_bpf eBPF 程序,校验器允许直接通过 skb->data
和 skb->data_end
指针访问包数据。
简单例子
1 | 1: r4 = *(u32 *)(r1 +80) /* load skb->data_end */ |
上面从包数据中加载 2 字节的操作是安全的,因为程序编写者在第五行主动检查了数据边界: if (skb->data + 14 > skb->data_end) goto err
,这意味着能执行到第 6 行时(fall-through case), R3(skb->data
)至少有 14 字节的直接可访问数据,因此 校验器将其标记为 R3=pkt(id=0,off=0,r=14)
:
id=0
表示没有额外的变量加到这个寄存器上;off=0
表示没有额外的常量 offset;r=14
表示安全访问的范围,即[R3, R3+14)
指向的字节范围都是 OK 的。
这里注意 R5 被标记为 R5=pkt(id=0,off=14,r=14)
,
- 它也指向包数据,但常量 14 加到了寄存器,因为它执行的是
skb->data + 14
, - 因此可访问的范围是
[R5, R5 + 14 - 14)
,也就是 0 个字节。
复杂例子
下面是个更复杂一些的例子:
1 | R0=inv1 R1=ctx R3=pkt(id=0,off=0,r=14) R4=pkt_end R5=pkt(id=0,off=14,r=14) R10=fp |
校验器标记信息解读
第 18 行之后,寄存器 R3 的状态是 R3=pkt(id=2,off=0,r=8)
,
id=2
表示之前已经跟踪到两个r3 += rX
指令,因此 r3 指向某个包内的某个 offset,由于程序员在 18 行已经做了if (r3 + 8 > r1) goto err
检查,因此安全范围是[R3, R3 + 8)
。- 校验器只允许对 packet 寄存器执行 add/sub 操作。其他操作会将 寄存器状态设为 SCALAR_VALUE,这个状态是不允许执行 direct packet access 的。
操作 r3 += rX
可能会溢出,变得比起始地址 skb->data 还小,校验器必须要能检查出这种情况。 因此当它看到 r3 += rX
指令并且 rX 比 16bit 值还大时,接下来的任何将 r3 与 skb->data_end
对比的操作都不会返回范围信息,因此尝试通过 这个指针读取数据的操作都会收到 invalid access to packet 错误。 例如,
r4 = *(u8 *)(r3 +12)
之后,r4 的状态是R4=inv(id=0,umax_value=255,var_off=(0x0; 0xff))
,意思是 寄存器的 upper 56 bits 肯定是 0,但对于低 8bit 信息一无所知。 在执行完r4 *= 14
之后,状态变成R4=inv(id=0,umax_value=3570,var_off=(0x0; 0xfffe))
,因为一个 8bit 值乘以 14 之后, 高 52bit 还是 0,此外最低 bit 位为 0,因为 14 是偶数。- 类似地,
r2 >>= 48
使得R2=inv(id=0,umax_value=65535,var_off=(0x0; 0xffff))
,因为移位是无符号扩展。 这个逻辑在函数adjust_reg_min_max_vals()
中实现,它又会调用adjust_ptr_min_max_vals()
adjust_scalar_min_max_vals()
对应的 C 代码
最终的结果是:eBPF 程序编写者可以像使用普通 C 语言一样访问包数据:
1 | void *data = (void *)(long)skb->data; |
相比使用 LD_ABS 之类的指令,这种程序写起来方便多了。
Pruning
校验器实际上并不会模拟执行程序的每一条可能路径。
对于每个新条件分支:校验器首先会查看它自己当前已经跟踪的所有状态。如果这些状态 已经覆盖到这个新分支,该分支就会被剪掉(pruned)—— 也就是说之前的状态已经被接受 (previous state was accepted)能证明当前状态也是合法的。
举个例子:
- 当前的状态记录中,r1 是一个 packet-pointer
- 下一条指令中,r1 仍然是 packet-pointer with a range as long or longer and at least as strict an alignment,那 r1 就是安全的。
类似的,如果 r2 之前是 NOT_INIT
,那就说明之前任何代码路径都没有用到这个寄存器 ,因此 r2 中的任何值(包括另一个 NOT_INIT)都是安全的。
实现在 regsafe()
函数。
Pruning 过程不仅会看寄存器,还会看栈(及栈上的 spilled registers)。 只有证明二者都安全时,这个分支才会被 prune。这个过程实现在 states_equal()
函数。
理解 eBPF 校验器提示信息
提供几个不合法的 eBPF 程序及相应校验器报错的例子。
The following are few examples of invalid eBPF programs and verifier error messages as seen in the log:
程序包含无法执行到的指令
1 | static struct bpf_insn prog[] = { |
Error:
1 | unreachable insn 1 |
程序读取未初始化的寄存器
1 | BPF_MOV64_REG(BPF_REG_0, BPF_REG_2), |
Error:
1 | 0: (bf) r0 = r2 |
程序退出前未设置 R0 寄存器
1 | BPF_MOV64_REG(BPF_REG_2, BPF_REG_1), |
Error:
1 | 0: (bf) r2 = r1 |
程序访问超出栈空间
1 | BPF_ST_MEM(BPF_DW, BPF_REG_10, 8, 0), |
Error::
1 | 0: (7a) *(u64 *)(r10 +8) = 0 |
未初始化栈内元素,就传递该栈地址
1 | BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), |
Error::
1 | 0: (bf) r2 = r10 |
程序执行 map_lookup_elem()
传递了非法的 map_fd
1 | BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0), |
Error:
1 | 0: (7a) *(u64 *)(r10 -8) = 0 |
程序未检查 map_lookup_elem()
的返回值是否为空就开始使用
1 | BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0), |
Error:
1 | 0: (7a) *(u64 *)(r10 -8) = 0 |
程序访问 map 内容时使用了错误的字节对齐
程序虽然检查了 map_lookup_elem()
返回值是否为 NULL,但接下来使用了错误的对齐:
1 | BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0), |
Error:
1 | 0: (7a) *(u64 *)(r10 -8) = 0 |
程序在 fallthrough 分支中使用了错误的字节对齐访问 map 数据
程序检查了 map_lookup_elem()
返回值是否为 NULL,在 if
分支中使用了正确的字节对齐, 但在 fallthrough 分支中使用了错误的对齐:
1 | BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0), |
Error:
1 | 0: (7a) *(u64 *)(r10 -8) = 0 |
程序执行 sk_lookup_tcp()
,未检查返回值就直接将其置 NULL
1 | BPF_MOV64_IMM(BPF_REG_2, 0), |
Error:
1 | 0: (b7) r2 = 0 |
这里的信息提示是 socket reference 未释放,说明 sk_lookup_tcp()
返回的是一个非空指针, 直接置空导致这个指针再也无法被解引用。
程序执行 sk_lookup_tcp()
但未检查返回值是否为空
1 | BPF_MOV64_IMM(BPF_REG_2, 0), |
Error:
1 | 0: (b7) r2 = 0 |
这里的信息提示是 socket reference 未释放,说明 sk_lookup_tcp()
返回的是一个非空指针, 直接置空导致这个指针再也无法被解引用。
testing
内核自带了一个 BPF 测试模块,覆盖了 cBPF 和 eBPF 的很多测试场景,能用来测试解释 器和 JIT 编译器。源码见 lib/test_bpf.c
,编译是 Kconfig 启用:
1 | CONFIG_TEST_BPF=m |
编译之后用 insmod
或 modprobe
加载 test_bpf
模块。 测试结果带有 ns
精度的时间戳日志,打印到内核日志(dmesg
查看)。