1. 简介
Brendan最近在USENIX LISA2021大会上做了一篇关于BPF内部原理的演讲，这篇演讲把BPF的内部逻辑剖析地非常清楚，本文大部分素材来自Brendan的这篇PPT, 额外加了一些kprobe原理的解释，分享给大家。
文中用到的术语解释
- AST: Abstract Syntax Tree
- LLVM: A compiler
- IR: Intermediate Representation
- JIT: Just-in-time compilation
- kprobes: Kernel dynamic instrumentation
- uprobes: User-level dynamic instrumentation
- tracepoints: Kernel static instrumentation
下图是BPF内部逻辑图，可以看出如何从bpftrace program经过AST，LLVM IR，BPF bytecode这几个阶段，最终得到machine code由CPU来执行。接下来我们详细介绍一下每个阶段。
2. bpftrace program → AST
我们以下面这个bpftrace One-Liner作为例子，介绍一下如何把bpftrace program转化成抽象语法树AST。
# bpftrace -e 'kprobe:do_nanosleep {
printf("PID %d sleeping...\n", pid);
}'
如上图所示，中间有个Parser模块包含了lex(词法分析)和yacc(语法分析)模块，学过编译原理的都知道，编译器把文本格式的代码翻译为中间代码一般会经过词法分析，语法分析，语义分析这几个阶段，这块内容我们在这不详细讨论，感兴趣可以阅读本文后面的参考文献。
经过lex和yacc处理后，我们就得到了抽象语法树AST，可以通过bpftrace -d参数打印出AST。
3. AST → LLVM IR
有了AST后，我们接下来看如何得到LLVM IR, 这其中需要经过几个模块的处理，上图中的Tracepoint & Clang struct parser模块在我们这个One-Liner例子中用不到，因为没有用到相关的结构体。
上图中的语义分析器，在本例中主要作用就是一些错误处理，例如错把pid写成了pidd,语义分析器会发现错误并打出错误日志。
经过Code Generation & IR Builder模块的处理，AST会被转化成LLVM IR，具体处理如下图所示。
LLVM IR也可以通过bpftrace -d打印出来。
4. LLVM IR → BPF bytecode
如何把LLVM IR转成BPF bytecode, 这里就用到了LLVM编译器。下图是BPF bytecode指令的格式，
BFP_CALL&JMP组合是0x85, get_current_pid_tgid对应的No是14，得到相应的BPF bytecode为85 00 00 e0 00 00 00，如下图所示。
5. BPF bytecode → machine code
得到了BPF bytecode后，接下来我们看如何得到machine code。
首先，第一个经过的模块为验证器Verifier, 验证器会拒绝那些不安全的操作，包括对无界循环的检查：BPF程序必须在有限的时间内完成。如下图。
经过了验证器验证，JIT编译器负责生成处理器可直接执行的机器指令。
因为要生成机器指令，所以JIT在不同的体系结构下处理方式是不一样的，下图罗列了x86/arm/sparc下的处理函数。
x86是在arch/x86/net/bpf_jit_comp.c的do_jit()函数中处理。
arm64下是在arch/arm64/net/bpf_jit_comp.c的build_insn()函数中处理。
我们可以用bpftool打印出最终的机器指令。
x86:
arm64:
6. kprobe
上面内容讲述了从bpftrace program到机器代码的转化过程，这时我们该考虑如何和kprobe结合了。
kprobe可以对任何内核函数进行插桩，可以实时在生产环境中启用，不需要重启系统，也不需要以特殊方式重启内核。
现在有以下三种接口可以访问kprobes.
- kprobe API: 如register_kprobe()等
- 基于Frace的，通过/sys/kernel/debug/tracing/kprobe_events:通过向这个文件写入字符串，可以配置开启和停止kprobes
- perf_event_open(): 与perf工具所使用的一样，现在BPF跟踪工具也开始使用这些函数
通过strace可以看到这里是使用perf_event_open()接口来和kprobe打交道。
kprobe工作原理
kprobe的工作过程如下(分几种情况)：
一. 对于一个kprobe插桩来说：
1) 将要插桩的目标地址中的字节内容复制并保存；
2) 以单步中断指令覆盖目标地址：在ARM上是BRK指令，X86是int3;
3) 当指令流执行到断点时，断点处理函数会检查这个断点是否是由kprobes注册的，如果是，就会执行kprobes注册函数；
4) 原始的指令会接着执行，指令流继续
5) 当不在需要kprobes时，原始的字节内容会被复制回目标地址上，这样这些指令就回到了他们的初始状态。
二. 如果这个kprobe是一个Ftrace已经做过插桩的地址（一般位于函数入口处），那么可以基于Ftrace进行kprobe优化，过程如下：
1) 将一个Ftrace kprobe处理函数注册为对应函数的Ftrace处理器
2) 当在函数起始处执行内建入口函数时（x86架构上为__fentry__）,该函数会调用Ftrace, Ftrace接下来会调用kprobe处理函数
3) 当kprobe不在被使用时，从Ftrace中移除Ftrace-kprobe处理函数
三. 如果是一个kretprobe：
1) 对函数入口进行kprobe插桩
2) 当函数入口被kprobe命中时，将返回地址保存并替换为一个「蹦床」(trampoline)函数：kretprobe_trampoline()
3) 当函数最终返回时（ret指令），CPU将控制交给蹦床函数处理
4) 在kretprobe处理完成之后再返回到之前保存的地址
5) 当不在需要kretprobe时，函数入口的kprobe就被移除了
最后我们看一下如何将结果返回给userspace, 这里用到了perf buffer空间。
这块空间是per cpu的。
最终在userspace打印出来。这块不细说了，具体内容可以看后面参考文献。
参考文献
https://www.brendangregg.com/blog/2021-06-15/bpf-internals.html
https://events.static.linuxfound.org/sites/events/files/slides/bpf_collabsummit_2015feb20.pdf
Linux include/uapi/linux/bpf_common.h
Linux include/uapi/linux/bpf.h
Linux include/uapi/linux/filter.h
https://docs.cilium.io/en/v1.9/bpf/#bpf-guide
BPF Performance Tools, Addison-Wesley 2020
https://ebpf.io/what-is-ebpf
http://www.brendangregg.com/ebpf.html
https://github.com/iovisor/bcc
https://github.com/iovisor/bpftrace
http://dinosaur.compilertools.net/
