0%

eBPF 指令集

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 编译之后的代码

  • filterbpf_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 由下面几部分组成:

  1. 11 个 64 位寄存器(这些寄存器包含 32 位子寄存器)
  2. 一个程序计数器(program counter,PC)
  3. 一个 512 字节大小的 BPF 栈空间

寄存器的名字从 r0r10默认的运行模式是 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_64arm64 和其他 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 位的,原因:

  1. 64 位处理器架构上指针也是 64 位的,我们希望与内核函数交互时,输入输出的都是 64 位值。如果使用 32 位 eBPF 寄存器,就需要定义 register-pair ABI,导致无法 直接将 eBPF 寄存器映射到物理寄存器,JIT 就必须为与函数调用相关的每个寄存器承 担 拼装/拆分/移动 等等操作,不仅复杂,而且很容易产生 bug,效率也很低。
  2. 另一个原因是 eBPF 使用了 64 位的原子计数器(atomic 64-bit counters)。

条件跳转:jt/fall-through 取代 jt/jf

cBPF 的设计中有条件判断:

1
2
3
4
if (cond)
jump_true;
else
jump_false;

现在被下面的结构取代了:

1
2
3
4
if (cond)
jump_true;

/* else fall-through */

引入 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
2
3
u64 f1() { return (*_f2)(1); }
u64 f2(u64 a) { return f3(a + 1, a); }
u64 f3(u64 a, u64 b) { return a - b; }

GCC 能将 f1 和 f3 编译成 x86_64:

1
2
3
4
5
6
7
8
9
f1:
movl $1, %edi ; 将常量 1 加载到 edi 寄存器
movq _f2(%rip), %rax ; 将 _f2 地址加载到 rax 寄存器
jmp *%rax ; 跳转到 rax 寄存器中指定的地址(即函数 _f2 的起始地址)

f3:
movq %rdi, %rax ; 将寄存器 rdi 中的值加载到寄存器 rax
subq %rsi, %rax ; 将寄存器 rax 中的值减去寄存器 rsi 中的值(即 a-b)
ret ; 返回

f2 的 eBPF 代码可能如下:

1
2
3
4
5
f2:
bpf_mov R2, R1 ; 即 R2 = a
bpf_add R1, 1 ; 即 R1 = a + 1
bpf_call f3 ; 调用 f3,传递给 f3 的两个参数分别在 R1 和 R2 中
bpf_exit ; 退出
  • 如果 f2 是 JIT 编译的,函数地址保存为变量 _f2,那调用链 f1 -> f2 -> f3 及返回就都是连续的。
  • 如果没有 JIT,就需要调用解释器 __bpf_prog_run() 来调用执行 f2。

出于一些实际考虑,

  1. 所有 eBPF 程序都只有一个参数 ctx,放在 R1 寄存器中,例如 __bpf_prog_run(ctx)
  2. 函数调用最多支持传递 5 个参数,但如果将来有需要,这个限制也可以进一步放宽。

eBPF 寄存器到 x86_64 硬件寄存器一一映射关系

在 64 位架构上,所有寄存器都能一一映射到硬件寄存器。例如,由于 x86_64 ABI 硬性规定

  1. rdi、rsi、rdx、rcx、r8、 r9 寄存器作为参数传递;
  2. rbx,以及 r12 - r15 由被调用方(callee)保存;

因此 x86_64 编译会做如下映射

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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)保存
...

示例解析(二):C 调 eBPF 代码编译成 x86_64 汇编后的样子

根据上面的映射关系,下面的 BPF 程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// BPF 指令格式:
// <指令> <目的寄存器> <源寄存器/常量>

bpf_mov R6, R1 ; 将 ctx 保存到 R6
bpf_mov R2, 2 ; 将常量 2(即将调用的函数 foo() 的参数)加载到 R2 寄存器
bpf_mov R3, 3
bpf_mov R4, 4
bpf_mov R5, 5
bpf_call foo ; 调用 foo 函数
bpf_mov R7, R0 ; 将 foo() 的返回值(在 R0 中)保存到 R7 中
bpf_mov R1, R6 ; 从 R6 中恢复 ctx 状态,保存到 R1;这样下次执行调用函数调用时就可以继续使用了;
bpf_mov R2, 6 ; 将常量 2(即将调用的函数 bar() 的参数)加载到 R2 寄存器
bpf_mov R3, 7
bpf_mov R4, 8
bpf_mov R5, 9
bpf_call bar ; 调用 bar() 函数
bpf_add R0, R7 ; 将 bar() 的返回值(在 R0 中)与 foo() 的返回值(在 R7 中)相加
bpf_exit

在 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// x86_64 指令格式:注意源和目的寄存器的顺序与 BPF 指令是相反的
// <指令> <源寄存器/常量> <目的寄存器>

// 下面这几行是 x86_64 的初始化指令,与 eBPF 还没有直接对应关系
// 解读参考:https://stackoverflow.com/questions/41912684/what-is-the-purpose-of-the-rbp-register-in-x86-64-assembler
push %rbp // 将帧指针(frame pointer)在栈地址空间中前移,即栈空间增长一个单位(一个单位 64bit)
mov %rsp, %rbp // 将栈指针(stack pointer)保存到 %rbp 位置(即上一行刚在栈上分配的位置)
sub $0x228, %rsp // 栈指针 rsp -= 0x228(栈向下增长,这一行表示再分配 0x228 个单位的栈空间)
mov %rbx, -0x228(%rbp) // 将 %rbx(对应 eBPF R6)的值保存到新分配空间的起始处(占用 8 个字节),因为 eBPF 程序返回时会占用 rbx 寄存器
mov %r13, -0x220(%rbp) // 将 %r13 (对应 eBPF R7)的值保存到下一个位置(起始位置 = 0x228 - 0x8 = 0x220,也是占用 8 个字节),理由同上
// 接下来还应该有三条指令,分别将 r14、15、rbp 依次保存到栈上,理由同上。
// 这样,这 5 条指令占用 5*8 = 40byte = 0x28 字节。刚才总共申请了 0x228 字节,
// 0x228 - 0x28 = 0x200 = 512 字节,也就是 eBPF 文档里常说的:eBPF 虚拟机最大支持 512 字节的栈空间。

// 下面这段与上面的 eBPF 指令能一一对应上
mov %rdi, %rbx // R6 = R1
mov $0x2, %esi // R2 = 2
mov $0x3, %edx // R3 = 3
mov $0x4, %ecx // R4 = 4
mov $0x5, %r8d // R5 = 5
callq foo
mov %rax, %r13 // R7 = R0
mov %rbx, %rdi // R1 = R6
mov $0x6, %esi // R2 = 6
mov $0x7, %edx // R3 = 7
mov $0x8, %ecx // R4 = 8
mov $0x9, %r8d // R5 = 9
callq bar
add %r13, %rax // R7 += R0

mov -0x228(%rbp), %rbx
mov -0x220(%rbp), %r13
leaveq
retq

下面是对应的 C 代码:

1
2
3
u64 bpf_filter(u64 ctx) {
return foo(ctx, 2, 3, 4, 5) + bar(ctx, 6, 7, 8, 9);
}

内核函数 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
2
3
4
bpf_mov   R1, 1
bpf_call foo
bpf_mov R0, R1
bpf_exit

在执行 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 运行在一个确定性的受控环境中,内核能依据下面两个步骤,轻松地对 程序的安全性作出判断:

  1. 首先进行深度优先搜索(depth-first-search),禁止循环;其他 CFG 验证。
  2. 以上一步生成的指令作为输入,遍历所有可能的执行路径。具体说 就是模拟每条指令的执行,观察寄存器和栈的状态变化

opcode encoding

为方便 cBPF 到 eBPF 的转换,eBPF 复用了 cBPF 的大部分 opcode encoding。

算术和跳转指令

对于算术和跳转指令(arithmetic and jump instructions),eBPF 的 8bit op 字段进一步分为三部分:

1
2
3
4
5
+----------------+--------+--------------------+
| 4 bits | 1 bit | 3 bits |
| operation code | source | instruction class |
+----------------+--------+--------------------+
(MSB) (LSB)

最后的 3bit 表示的是指令类型,包括:

1
2
3
4
5
6
7
8
9
10
11
12
===================     ===============
Classic BPF classes eBPF classes
=================== ===============
BPF_LD 0x00 BPF_LD 0x00
BPF_LDX 0x01 BPF_LDX 0x01
BPF_ST 0x02 BPF_ST 0x02
BPF_STX 0x03 BPF_STX 0x03
BPF_ALU 0x04 BPF_ALU 0x04
BPF_JMP 0x05 BPF_JMP 0x05
BPF_RET 0x06 BPF_JMP32 0x06
BPF_MISC 0x07 BPF_ALU64 0x07
=================== ===============

BPF_ALU 和 BPF_JMP 的 operand

BPF_CLASS(code) == BPF_ALU or BPF_JMP 时,第 4 bit 表示的源操作数(source operand)可以是:

1
2
3
BPF_K     0x00 // 32bit 立即数作为源操作数(use 32-bit immediate as source operand),对 cBPF/eBPF 一样
BPF_X 0x08 // 对 cBPF,表示用寄存器 X 作为源操作数
// 对 eBPF,表示用寄存器 src_reg 作为源操作数

BPF_ALU 和 BPF_ALU64 (eBPF) 的 opcode

BPF_CLASS(code) == BPF_ALU or BPF_ALU64 [ in eBPF ], BPF_OP(code) 可以是:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
BPF_ADD   0x00
BPF_SUB 0x10
BPF_MUL 0x20
BPF_DIV 0x30
BPF_OR 0x40
BPF_AND 0x50
BPF_LSH 0x60
BPF_RSH 0x70
BPF_NEG 0x80
BPF_MOD 0x90
BPF_XOR 0xa0
BPF_MOV 0xb0 /* eBPF only: mov reg to reg */
BPF_ARSH 0xc0 /* eBPF only: sign extending shift right */
BPF_END 0xd0 /* eBPF only: endianness conversion */

BPF_JMP 和 BPF_JMP32 (eBPF) 的 opcode

BPF_CLASS(code) == BPF_JMP or BPF_JMP32 [ in eBPF ]BPF_OP(code) 可以是:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
BPF_JA    0x00  /* BPF_JMP only */
BPF_JEQ 0x10
BPF_JGT 0x20
BPF_JGE 0x30
BPF_JSET 0x40
BPF_JNE 0x50 /* eBPF only: jump != */
BPF_JSGT 0x60 /* eBPF only: signed '>' */
BPF_JSGE 0x70 /* eBPF only: signed '>=' */
BPF_CALL 0x80 /* eBPF BPF_JMP only: function call */
BPF_EXIT 0x90 /* eBPF BPF_JMP only: function return */
BPF_JLT 0xa0 /* eBPF only: unsigned '<' */
BPF_JLE 0xb0 /* eBPF only: unsigned '<=' */
BPF_JSLT 0xc0 /* eBPF only: signed '<' */
BPF_JSLE 0xd0 /* eBPF only: signed '<=' */

指令 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
2
3
4
5
+--------+--------+-------------------+
| 3 bits | 2 bits | 3 bits |
| mode | size | instruction class |
+--------+--------+-------------------+
(MSB) (LSB)

2bit 的 size modifier 可以是:

1
2
3
4
BPF_W   0x00    /* word */
BPF_H 0x08 /* half word */
BPF_B 0x10 /* byte */
BPF_DW 0x18 /* eBPF only, double word */

表示的是 load/store 操作的字节数:

1
2
3
4
B  - 1 byte
H - 2 byte
W - 4 byte
DW - 8 byte (eBPF only)

Mode modifier 可以是:

1
2
3
4
5
6
7
BPF_IMM  0x00  /* used for 32-bit mov in classic BPF and 64-bit in eBPF */
BPF_ABS 0x20
BPF_IND 0x40
BPF_MEM 0x60
BPF_LEN 0x80 /* classic BPF only, reserved in eBPF */
BPF_MSH 0xa0 /* classic BPF only, reserved in eBPF */
BPF_XADD 0xc0 /* eBPF only, exclusive add */

两个 eBPF non-generic 指令:BPF_ABS 和 BPF_IND,用于访问 skb data

eBPF 有两个 non-generic 指令,用于兼容 cBPF:

  1. BPF_ABS | <size> | BPF_LD
  2. BPF_IND | <size> | BPF_LD

二者用来访问数据包中的数据(packet data)。

  1. 这两个指令 cBPF 中就有了,必须 eBPF 也必须要支持,而且 eBPF 解释器还要高效地执行这两条指令。
  2. 执行这个两个指令时,传递给解释器的上下文必须是 struct *sk_buff, 并且隐含了 7 个操作数
    • R6 作为隐式输入,存放的必须是 struct *sk_buff
    • R0 作为隐式输出,存放的是从包中读取的数据;
    • R1-R5 作为 scratch registers,不能在多次 BPF_ABS | BPF_LDBPF_IND | BPF_LD 指令之间在这几个寄存器中保存数据(每次调用执行之后,都会将这些寄存器置空);
  3. 这些指令还有隐含的程序退出条件。当 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
2
3
4
5
BPF_MEM  | <size> | BPF_STX:  *(size *)(dst_reg + off) = src_reg
BPF_MEM | <size> | BPF_ST : *(size *)(dst_reg + off) = imm32
BPF_MEM | <size> | BPF_LDX: dst_reg = *(size *)(src_reg + off)
BPF_XADD | BPF_W | BPF_STX: lock xadd *(u32 *)(dst_reg + off16) += src_reg
BPF_XADD | BPF_DW | BPF_STX: lock xadd *(u64 *)(dst_reg + off16) += src_reg

其中,size 是:

  1. BPF_B
  2. BPF_H
  3. BPF_W
  4. BPF_DW

注意:这里不支持 1 或 2 字节的原子递增操作。

加载 64bit 立即数的 eBPF 指令

eBPF 有一个 16-byte instruction: BPF_LD | BPF_DW | BPF_IMM,功能是将 64bit 立即数(imm64)加载到寄存器:

  1. 这条指令由两个连续 struct bpf_insn 8-byte blocks 组成,会被解释器解释为单个指令,
  2. 功能就是上面提到的,将一个 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
    2
    bpf_mov R0 = R2
    bpf_exit

    将会被拒绝,因为程序开始之后,R2 还没有初始化过。

  • 内核函数执行完成后,R1-R5 将被重置为不可读状态,R0 保存函数的返回值。

  • 由于 R6-R9 是被调用方(callee)保存的,因此它们的状态在函数调用结束之后还是有效的。

    1
    2
    3
    4
    bpf_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
2
3
4
bpf_mov R1 = 1
bpf_mov R2 = 2
bpf_xadd *(u32 *)(R1 + 3) += R2
bpf_exit

将会被拒,因为执行到第三行时,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
2
bpf_ld R0 = *(u32 *)(R10 - 4)
bpf_exit

是非法程序。因为虽然 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 种指针类型

依据它们指向的数据结构类型,又可以分为:

  1. PTR_TO_CTX:指向 bpf_context 的指针。

  2. CONST_PTR_TO_MAP:指向 struct bpf_map 的指针。 是常量(const),因为不允许对这种类型指针进行算术操作。

  3. PTR_TO_MAP_VALUE:指向 bpf map 元素的指针。

  4. PTR_TO_MAP_VALUE_OR_NULL:指向 bpf map 元素的指针,可为 NULL。 访问 map 的操作会返回这种类型的指针。禁止算术操作

  5. PTR_TO_STACK:帧指针(Frame pointer)。

  6. PTR_TO_PACKET:指向 skb->data 的指针。

  7. PTR_TO_PACKET_END:指向 skb->data + headlen 的指针。禁止算术操作。

  8. PTR_TO_SOCKET:指向 struct bpf_sock_ops 的指针,内部有引用计数。

  9. PTR_TO_SOCKET_OR_NULL:指向 struct bpf_sock_ops 的指针,或 NULL。

    socket lookup 操作会返回这种类型。有引用计数, 因此程序在执行结束时,必须通过 socket release 函数释放引用。禁止算术操作。

这些指针都称为 base 指针。

指针偏移(offset)触发寄存器状态更新

实际上,很多有用的指针都是 base 指针加一个 offset(指针算术运算的结果), 这是通过两方面来个跟踪的:

  1. ‘fixed offset’(固定偏移):offset 是个常量(例如,立即数)。
  2. ‘variable offset’(可变偏移):offset 是个变量。这种类型还用在 SCALAR_VALUE 跟踪中,来跟踪寄存器值的可能范围。

校验器对可变 offset 的知识包括:

  1. 无符号类型:最小和最大值;
  2. 有符号类型:最小和最大值;
  3. 关于每个 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_stateid 字段

struct bpf_reg_state 结构体有一个 id 字段,

1
2
3
4
5
6
7
8
9
10
11
12
// include/linux/bpf_verifier.h

/* For PTR_TO_PACKET, used to find other pointers with the same variable
* offset, so they can share range knowledge.
* For PTR_TO_MAP_VALUE_OR_NULL this is used to share which map value we
* came from, when one is tested for != NULL.
* For PTR_TO_MEM_OR_NULL this is used to identify memory allocation
* for the purpose of tracking that it's freed.
* For PTR_TO_SOCKET this is used to share which pointers retain the
* same reference to the socket, to determine proper reference freeing.
*/
u32 id;

如注释所述,该字段针对不同指针类型有不同用途,下面分别解释。

PTR_TO_PACKET

id 字段对共享同一 variable offset 的多个 PTR_TO_PACKET 指针 都是可见的,这对skb 数据的范围检查非常重要。举个例子:

1
2
3
1:  A = skb->data // A 是指向包数据的指针
2: B = A + var2 // B 是从 A 开始往前移动 var2 得到的地址
3: A = A + 4 // A 往前移动 4 个字节

在这个程序中,寄存器 A 和 B 将将共享同一个 id

  • A 已经从最初地址向前移动了 4 字节(有一个固定偏移 +4),
  • 如果这个边界通过校验了,也就是确认小于 PTR_TO_PACKET_END,那现在 寄存器 B 将有一个范围至少为 4 字节的可安全访问范围

更多关于这种指针的信息,见下面的 ‘Direct packet access’ 章节。

PTR_TO_MAP_VALUE

与上面的用途类型,具体来说:

  1. 这一字段对共享同一基础指针的多个 PTR_TO_MAP_VALUE 指针可见;
  2. 这些指针中,只要一个指针经验证是非空的,就认为其他指针(副本)都是非空的(因此减少重复验证开销);

另外,与 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->dataskb->data_end 指针访问包数据

简单例子

1
2
3
4
5
6
7
1:  r4 = *(u32 *)(r1 +80)  /* load skb->data_end */
2: r3 = *(u32 *)(r1 +76) /* load skb->data */
3: r5 = r3
4: r5 += 14
5: if r5 > r4 goto pc+16
R1=ctx R3=pkt(id=0,off=0,r=14) R4=pkt_end R5=pkt(id=0,off=14,r=14) R10=fp # 校验器标记
6: r0 = *(u16 *)(r3 +12) /* access 12 and 13 bytes of the packet */

上面从包数据中加载 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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
6: r0 = *(u8 *)(r3 +7) /* load 7th byte from the packet */
7: r4 = *(u8 *)(r3 +12)
8: r4 *= 14
9: r3 = *(u32 *)(r1 +76) /* load skb->data */
10: r3 += r4
11: r2 = r1
12: r2 <<= 48
13: r2 >>= 48
14: r3 += r2
15: r2 = r3
16: r2 += 8
17: r1 = *(u32 *)(r1 +80) /* load skb->data_end */
18: if r2 > r1 goto pc+2
R0=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R1=pkt_end R2=pkt(id=2,off=8,r=8) R3=pkt(id=2,off=0,r=8) R4=inv(id=0,umax_value=3570,var_off=(0x0; 0xfffe)) R5=pkt(id=0,off=14,r=14) R10=fp
19: r1 = *(u8 *)(r3 +4)
校验器标记信息解读

第 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
2
3
4
5
6
7
8
9
10
11
12
13
14
void *data = (void *)(long)skb->data;
void *data_end = (void *)(long)skb->data_end;
struct eth_hdr *eth = data;
struct iphdr *iph = data + sizeof(*eth);
struct udphdr *udp = data + sizeof(*eth) + sizeof(*iph);

if (data + sizeof(*eth) + sizeof(*iph) + sizeof(*udp) > data_end)
return 0;
if (eth->h_proto != htons(ETH_P_IP))
return 0;
if (iph->protocol != IPPROTO_UDP || iph->ihl != 5)
return 0;
if (udp->dest == 53 || udp->source == 9)
...;

相比使用 LD_ABS 之类的指令,这种程序写起来方便多了。

Pruning

校验器实际上并不会模拟执行程序的每一条可能路径

对于每个新条件分支:校验器首先会查看它自己当前已经跟踪的所有状态。如果这些状态 已经覆盖到这个新分支,该分支就会被剪掉(pruned)—— 也就是说之前的状态已经被接受 (previous state was accepted)能证明当前状态也是合法的。

举个例子:

  1. 当前的状态记录中,r1 是一个 packet-pointer
  2. 下一条指令中,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
2
3
4
static struct bpf_insn prog[] = {
BPF_EXIT_INSN(),
BPF_EXIT_INSN(),
};

Error:

1
unreachable insn 1

程序读取未初始化的寄存器

1
2
BPF_MOV64_REG(BPF_REG_0, BPF_REG_2),
BPF_EXIT_INSN(),

Error:

1
2
0: (bf) r0 = r2
R2 !read_ok

程序退出前未设置 R0 寄存器

1
2
BPF_MOV64_REG(BPF_REG_2, BPF_REG_1),
BPF_EXIT_INSN(),

Error:

1
2
3
0: (bf) r2 = r1
1: (95) exit
R0 !read_ok

程序访问超出栈空间

1
2
BPF_ST_MEM(BPF_DW, BPF_REG_10, 8, 0),
BPF_EXIT_INSN(),

Error::

1
2
0: (7a) *(u64 *)(r10 +8) = 0
invalid stack off=8 size=8

未初始化栈内元素,就传递该栈地址

1
2
3
4
5
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_LD_MAP_FD(BPF_REG_1, 0),
BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
BPF_EXIT_INSN(),

Error::

1
2
3
4
5
0: (bf) r2 = r10
1: (07) r2 += -8
2: (b7) r1 = 0x0
3: (85) call 1
invalid indirect read from stack off -8+0 size 8

程序执行 map_lookup_elem() 传递了非法的 map_fd

1
2
3
4
5
6
BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_LD_MAP_FD(BPF_REG_1, 0),
BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
BPF_EXIT_INSN(),

Error:

1
2
3
4
5
6
0: (7a) *(u64 *)(r10 -8) = 0
1: (bf) r2 = r10
2: (07) r2 += -8
3: (b7) r1 = 0x0
4: (85) call 1
fd 0 is not pointing to valid bpf_map

程序未检查 map_lookup_elem() 的返回值是否为空就开始使用

1
2
3
4
5
6
7
BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_LD_MAP_FD(BPF_REG_1, 0),
BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0),
BPF_EXIT_INSN(),

Error:

1
2
3
4
5
6
7
0: (7a) *(u64 *)(r10 -8) = 0
1: (bf) r2 = r10
2: (07) r2 += -8
3: (b7) r1 = 0x0
4: (85) call 1
5: (7a) *(u64 *)(r0 +0) = 0
R0 invalid mem access 'map_value_or_null'

程序访问 map 内容时使用了错误的字节对齐

程序虽然检查了 map_lookup_elem() 返回值是否为 NULL,但接下来使用了错误的对齐:

1
2
3
4
5
6
7
8
BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_LD_MAP_FD(BPF_REG_1, 0),
BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 1),
BPF_ST_MEM(BPF_DW, BPF_REG_0, 4, 0),
BPF_EXIT_INSN(),

Error:

1
2
3
4
5
6
7
8
9
0: (7a) *(u64 *)(r10 -8) = 0
1: (bf) r2 = r10
2: (07) r2 += -8
3: (b7) r1 = 1
4: (85) call 1
5: (15) if r0 == 0x0 goto pc+1
R0=map_ptr R10=fp
6: (7a) *(u64 *)(r0 +4) = 0
misaligned access off 4 size 8

程序在 fallthrough 分支中使用了错误的字节对齐访问 map 数据

程序检查了 map_lookup_elem() 返回值是否为 NULL,在 if 分支中使用了正确的字节对齐, 但在 fallthrough 分支中使用了错误的对齐:

1
2
3
4
5
6
7
8
9
10
BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_LD_MAP_FD(BPF_REG_1, 0),
BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 2),
BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0),
BPF_EXIT_INSN(),
BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 1),
BPF_EXIT_INSN(),

Error:

1
2
3
4
5
6
7
8
9
10
11
12
13
0: (7a) *(u64 *)(r10 -8) = 0
1: (bf) r2 = r10
2: (07) r2 += -8
3: (b7) r1 = 1
4: (85) call 1
5: (15) if r0 == 0x0 goto pc+2
R0=map_ptr R10=fp
6: (7a) *(u64 *)(r0 +0) = 0
7: (95) exit

from 5 to 8: R0=imm0 R10=fp
8: (7a) *(u64 *)(r0 +0) = 1
R0 invalid mem access 'imm'

程序执行 sk_lookup_tcp(),未检查返回值就直接将其置 NULL

1
2
3
4
5
6
7
8
9
10
BPF_MOV64_IMM(BPF_REG_2, 0),
BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_2, -8),
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_MOV64_IMM(BPF_REG_3, 4),
BPF_MOV64_IMM(BPF_REG_4, 0),
BPF_MOV64_IMM(BPF_REG_5, 0),
BPF_EMIT_CALL(BPF_FUNC_sk_lookup_tcp),
BPF_MOV64_IMM(BPF_REG_0, 0),
BPF_EXIT_INSN(),

Error:

1
2
3
4
5
6
7
8
9
10
11
0: (b7) r2 = 0
1: (63) *(u32 *)(r10 -8) = r2
2: (bf) r2 = r10
3: (07) r2 += -8
4: (b7) r3 = 4
5: (b7) r4 = 0
6: (b7) r5 = 0
7: (85) call bpf_sk_lookup_tcp#65
8: (b7) r0 = 0
9: (95) exit
Unreleased reference id=1, alloc_insn=7

这里的信息提示是 socket reference 未释放,说明 sk_lookup_tcp() 返回的是一个非空指针, 直接置空导致这个指针再也无法被解引用。

程序执行 sk_lookup_tcp() 但未检查返回值是否为空

1
2
3
4
5
6
7
8
9
BPF_MOV64_IMM(BPF_REG_2, 0),
BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_2, -8),
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_MOV64_IMM(BPF_REG_3, 4),
BPF_MOV64_IMM(BPF_REG_4, 0),
BPF_MOV64_IMM(BPF_REG_5, 0),
BPF_EMIT_CALL(BPF_FUNC_sk_lookup_tcp),
BPF_EXIT_INSN(),

Error:

1
2
3
4
5
6
7
8
9
10
0: (b7) r2 = 0
1: (63) *(u32 *)(r10 -8) = r2
2: (bf) r2 = r10
3: (07) r2 += -8
4: (b7) r3 = 4
5: (b7) r4 = 0
6: (b7) r5 = 0
7: (85) call bpf_sk_lookup_tcp#65
8: (95) exit
Unreleased reference id=1, alloc_insn=7

这里的信息提示是 socket reference 未释放,说明 sk_lookup_tcp() 返回的是一个非空指针, 直接置空导致这个指针再也无法被解引用。

testing

内核自带了一个 BPF 测试模块,覆盖了 cBPF 和 eBPF 的很多测试场景,能用来测试解释 器和 JIT 编译器。源码见 lib/test_bpf.c,编译是 Kconfig 启用:

1
CONFIG_TEST_BPF=m

编译之后用 insmodmodprobe 加载 test_bpf 模块。 测试结果带有 ns 精度的时间戳日志,打印到内核日志(dmesg 查看)。

参考资料