去年学习Go语言时，有位同学说了一句让我至今仍深刻记忆的话：“我们有足够多的工具来进行性能分析，以找出性能问题的根源”。
后来我发现，Go语言的性能分析工具确实非常强大。更重要的是，它被设计成可以直接在生产环境中采样线上数据。
然而，当我写Lua代码时，我并没有自信能说出同样的话。尽管我之前曾多次实现Lua性能分析器。
这些分析器的实现原理与gprof类似，只是细节略有不同。在代码块进入时记录函数的进入时间，在退出时统计函数的执行时间和执行次数。
为了准确评估rpc:call等函数的CPU时间，还添加了一个选项用于去除coroutine的让出时间。
然而，这些性能分析器存在一些缺点：
首先，它们对宿主程序的性能影响很大。在以函数为区间进行耗时统计时，甚至可能达到1000%的性能影响。因此，不能在线上环境中使用，只能在开发期进行自测。
其次，它们只能统计Lua函数（包括C编写的闭包和lightCFunction），无法统计C模块内部的C函数开销。而使用其他C性能分析工具时，也无法分析与Lua函数相关的耗时。这在进行性能分析时会导致非常不连贯的感觉。
此外，当使用C的性能分析器进行分析时，我们会失去上下文信息。由于Lua是用C语言编写的虚拟机，当我们发现某个C函数的耗时很高时，无法确定是哪段Lua代码导致的。例如，当发现tremove函数的CPU使用率很高时，无法知道是哪段Lua代码引起的。
最后，这些性能分析器是实现在宿主进程中的。如果宿主进程陷入死循环，将无法获取任何性能分析数据。
但当时我并没有找到解决以上问题的好办法，直到最近我开始研究eBPF，我终于觉得自己可以解决这些缺点，并且实现一个和Go语言类似的性能分析器。
现在回想起来，已经过去一年了。
新的性能分析器和Go的性能分析器一样基于栈采样技术，这样可以做到对目标程序的性能影响最小。
和Go不同的是，我这次实现的Lua性能分析器和linux下的perf一样，是一个独立的程序。
这样可以做到对目标程序无侵入，并且在目标程序死循环的情况下，依然可以正常运行。
按照最初的想法，这并不是一件太困难的事情。只需要在bpf程序中获取C的callstack和Lua的callstack，然后在用户空间将它们合并。
最后，按照火焰图的格式进行输出并生成火焰图。
整个过程并不复杂。
然而，当我开始实际实现时，事情的发展远远超出了我的预期，整个过程触及了我知识的盲区。
我本以为eBPF发展了近9年，在内核空间获取C的callstack应该只是一个API的事情。然而，现实却给了我一个沉重的打击。
现代编译器只要开启优化，默认情况下会抹去栈帧指针。而bpf中的内置API只能在栈帧指针保留的情况下轻易获取整个callstack。
我面临两个选择：要求被性能分析的进程在编译时必须使用-fomit-frame-pointer编译选项，或者我必须手动进行栈回溯。
我的目标是对目标程序进行无侵入性能分析，我认为强制要求目标程序使用-fomit-frame-pointer也是一种形式的侵入。
目标程序需要不断忍受-fomit-frame-pointer带来的性能损失。
而且，我无法要求像libc等系统提供的so文件必须保留栈帧指针。
于是，我只剩下一种方案，就是手动进行栈回溯。
手动进行栈回溯也有两种方案。
一种是在bpf程序中将目标进程的完整栈数据复制到用户空间，然后使用libunwind进行栈回溯。
另一种是直接在bpf程序中进行栈回溯，并统计调用栈的出现次数，然后只将统计结果发送回用户空间。
很快，我否定了第一种方案。
bpf最初的目的是用于过滤网络数据包，因此eBPF程序应该基于此设计思路。
即在bpf程序中处理和加工所需的数据，然后只将需要的数据传回用户空间。
而且，如果我们在用户空间进行栈回溯，由于ringbuffer的异步性，我们无法及时采样到与收集到的栈数据相匹配的Lua调用栈（因为我们需要先回溯完C的callstack才能获取L指针，然后再对L进行栈回溯，而这期间目标程序的Lua调用栈早已经发生变化）。
对已经抹去栈帧指针的callstack进行手动回溯，完全触及了我知识的盲区。
最初，我考虑仿照gdb的方案，通过调试信息进行栈回溯。
但是，调试信息的数据量太大，不方便传送到内核。而且，解析调试信息这样的任务也不太适合由bpf完成。
一个偶然的机会，我发现了elf文件中的一个名为eh_frame的section，全名为exception handling frame。它被设计为在发生异常时为栈回溯提供完整的信息，这恰好符合我们的需求。
eh_frame是由一系列CFI指令组成的，用于为栈回溯提供指导信息。这些CFI指令按函数顺序执行，即程序执行到某一行代码时，要回溯所有寄存器的状态，需要执行函数开始到该行代码之前的所有CFI指令。
幸运的是，在回溯时我们只需要获取caller的EIP和包含luaState *L变量的寄存器的值，因此可以忽略大多数寄存器的回溯信息。
为了加快bpf程序的执行速度，我们可以在将eh_frame数据发送给bpf之前进行预处理。
通过模拟CFI指令的执行，我们可以获得每行汇编对应的所有寄存器的回溯信息。
这样当我们在bpf中获取到对应的EIP时，可以使用二分查找快速获取所有寄存器的回溯规则。
为了更好地利用缓存，我们还可以生成一个类似于eh_frame_header的数组，只包含EIP，专门供bpf程序进行二分查找。
一旦获取到索引，我们可以再查询真正的eh_frame信息。
尽管上述方案没有问题，但它忽略了一个条件。
我们从elf文件读取的是相对虚拟地址（PC），而在bpf程序中获取的是经过内核映射后的绝对虚拟地址（VA）。
在对eh_frame进行预处理时，我们需要将其中的PC转换为VA。这就需要使用到elf文件的Program Header Table信息。
Program Header Table提供了整个elf文件在进程空间中映射的分段情况。根据/proc/<pid>/smaps中的映射信息，我们可以将PC和VA进行转换。
具体的转换逻辑是，当<program Header Table>.p_offset与/proc/<pid>/smaps中的offset相同时，表示它们属于文件的同一映射区域。
一旦我们获得了eh_frame中的PC，只需计算其在ELF文件映射块中的偏移量，加上/proc/</pid><pid>/smaps中的映射基地址，即可得到PC在进程空间中的绝对虚拟地址（VA）。
现在，我们终于可以在bpf程序中进行C的栈回溯了。
Lua的调用栈相对简单，只需要遍历整个L->ci链表即可。
但是有一个特别的问题，由于Lua中的函数都是动态的，有可能某个函数在当前分析的时刻存在，但过一会就被垃圾回收（GC）掉了。
因此，在回溯Lua的调用栈时，我们需要保留当前的所有文件信息，否则稍后可能就无法获取它们了。
然而，直接在Lua的调用栈中存储文件路径和行号会浪费大量空间。
简单计算一下，如果我们要支持的最大Lua调用栈深度为128，并且每个文件路径的最大长度为64字节，那么每个调用栈就需要浪费128 * 64 + 4个字节的存储空间。
这种存储量级是不可接受的，并且在对调用栈进行计数时，也会导致性能严重损失。
为了简化设计，我在bpf程序中创建了一个字符串映射表strings。
在回溯Lua调用栈时，我们通过strings将字符串转换为uint32_t类型的id，然后使用id << 32 | line_num来构建一个虚拟地址。
为了标记这是一个合成地址而不是真实的虚拟地址，需要将即最终结果修改为(uint64)id << 32 | line_num | (1 << 63)。
这种方法的之所以有效，是因为在于用户空间，地址的bit63永远为0。
值得注意的是，strings是一个哈希表，因此无法保证冲突永不发生。
当字符串冲突时，我们将旧字符串和对应的id发送回用户空间，让用户空间进行存储，并为该槽位分配一个新的id。
我们利用了一个事实，Lua中的大部分函数都是常驻的，因此它们的源文件TString指针很可能是相同的。
尽管冲突存在，但我们并不太关心它们。因此，我们可以将源文件TString的指针视为该字符串的哈希值，当哈希值不同时，我们直接认为这是两个不同的字符串。
在bpf_helper中，有一个辅助函数bpf_get_stackid可将整个callstack映射为一个id。这对于生成火焰图非常有用。
由于我们正在手动进行栈回溯，我们需要自己实现该功能。然而，这也带来了一些好处。
通过与用户空间进行通信，我们可以利用用户空间的大内存来支持我们做一些bpf_get_stackid做不到的事情。
首先，我们需要定义一个名为stacks的哈希表。
当我们获取到一个栈回溯数据时，我们同时计算内核空间调用栈、用户空间调用栈和Lua调用栈的哈希值。然后，根据哈希值来确定stacks中对应的槽位。
如果槽位上已经有值，我们将比较它是否与当前的callstack相同，如果相同则数量加一。
如果不同，bpf_get_stackid将选择要么丢弃当前槽位上的旧callstack，要么丢弃新插入的callstack。
由于我们可以与用户空间进行通信，我们可以选择将旧的callstack发送回用户空间，并让新的callstack占据槽位。
将Lua调用栈和C调用栈也不是一帆风顺的。
从Lua 5.4版本开始，Lua支持在C函数中使用yield功能。
这可能导致在L->ci（Lua调用信息链表）中出现某个C函数或C闭包，但在C调用栈中并不存在相应的信息。
目前的解决方案是采用一种启发式的匹配策略。
当L->ci链表中的C函数与C调用栈中的C函数匹配时，我们认为从Lua调用栈的栈顶到当前C函数位置的部分是由当前C调用栈中的C函数产生的，并进行合并。
一些旁支末节。
在我最初学习eBPF程序时，我听说内核有一个bpf校验器，可以确保你编写的bpf程序永远不会损坏内核数据。
我一直觉得这很神奇，当时我在思考如果将这种技术应用于应用程序的检查中，会不会无敌。
最后才了解到，原来bpf校验器是采用宁可错杀一千也不可漏掉一人的方式进行检查的，各种报错会让人感到困惑和沮丧。
一个非常重要的知识点是，bpf校验器是在编译之后才开始校验的。
如果你写了相应的if检查，但校验器仍然报告你没有进行检查，那可能是因为你的检查被编译器优化掉了，你需要采用各种非常归的方法来阻止编译器的优化（我在这个问题上花了整整一个周末的时间来解决）。
最后源码在这里