介绍一种性能较好的 Android native unwind 技术
介绍一种有点不同于目前 Android 平台上常用的 native backtrace 技术，在支持 Android ART unwind 的情况下，通过损失少数可回溯场景换取性能提升。方案有一些优势和局限性，适用于部分场景。
通常如何在 Android native 中进行栈回溯
其实 Android 上实现 native 栈回溯的方式并没有很多，罗列一下大概就两种：一种是基于函数栈帧基地址（fp=frame pointer）寄存器的栈回溯，另一种是基于异常处理（EH=Exception Handling）或调试信息（Dwarf）的回溯。我们先大概看看这两种方式：
1. 基于函数栈帧基地址寄存器的栈回溯（fp-based unwinder）
如果能用 fp 进行栈回溯事情会很轻松。假如你在编译的时候启用了 -fno-omit-frame-pointer 选项（clang 默认启用这个选项），编译器会把某个特定的寄存器当 fp 寄存器，用来保存当前函数调用栈的起始地址。按照 ARM 的调用约定（AAPCS）[1] ，在 fp 寄存器指向的栈空间上紧凑的存着上一层函数的 fp 地址和函数返回地址。大概样子就是下图这样。额外提一下，特定的 fp 寄存器在 64 位上是 x29 寄存器，32 位则是 r7(Thumb Code) 或 r11(ARM Code) [2] 。
fp 回溯性能是最好的，因为够直接了当，读取的内存也相近。不过它也有些问题，比如在 Arm 32 位上某些情况 fp 会被忽略掉或不准确 [3] ，也不能回溯穿过 JNI 和 OAT （没遵守 fp 的约定）。
[1]. Procedure Call Standard for the Arm: https://developer.arm.com/documentation/ihi0055/latest/
[2]. -fno-omit-frame-pointer: https://developer.arm.com/documentation/dui0774/g/Compiler-Command-line-Options/-fomit-frame-pointer---fno-omit-frame-pointer
[3]. https://gcc.gnu.org/legacy-ml/gcc-help/2018-07/msg00093.html
2. 基于异常处理或调试信息的回溯
这种方式稍微复杂一些。ELF 文件的 .eh_frame 或 .debug_frame section 中存储着一堆结构紧凑的数据，它描绘了很多张“表”（unwind tables），当你的代码执行到某一“行”时，根据此时的 pc 我们可以从这张表中查询到退出当前函数栈时，各个寄存器该怎么进行恢复，比如它可能描述了寄存器的值该在从当前栈的哪个位置上读回来。例如下图：
P.S. fs = frame stack size, s = same value, u = undefined, rN = register(N)
上图是 Dwarf 标准文档附录里的 example [4] ，方便理解一起贴上对应的汇编代码：
从前面那张“表”中可以看到 foo 函数每一“行”都写着从 R0 到 R8 寄存器的值该怎么恢复，有些当前没用到或者没变化的寄存器被标记为 u 或 s。而有变化的条目例如 R6 寄存器，在执行到 foo+8 时被它存储到栈基地址偏移 -8 的位置上，所以从 foo+12 这行开始 R6 就变成了 c-8。这个 c 指的是表中 CFA 一列，可以把它理解成一个虚拟的保存着栈帧基地址的 stack pointer 寄存器，所以 c 的值就是当前的栈基地址。
有了 unwind tables 我们能找出来当前函数栈帧起始的位置以及可以计算出寄存器保存的返回地址是多少，经过多轮这样的迭代就可以回溯出整个调用栈。
P.S. '.eh_frame' 和 '.debug_frame' 的区别：.eh_frame 是 Linux 标准规范制定 [5] 用来支持如 C++ 的 Exceptions 能力，它的内容同 Dwarf 的 .debug_frame 基本一样，都能用来回溯。不过 .debug_frame 在编译 release 库的时候通常会被去掉（OAT 和 JIT 会使用 .debug_frame）。
前面快速的了解了 unwind tables 的内容，比较粗糙重在理解，更详细的内容可以参考 Dwarf 文档 6.4 Call Frame Information 章节 [6] 。
不过事情到这里还没有完全讲完，Android 平台上总会稍微啰嗦一点。
在 ARM 32 位平台上，ARM 提供了一套不同的 Exception Handling 机制（因为比较早），同样可以一帧一帧计算出寄存器的值、栈帧起始以及返回地址。ARM EH 的数据存放在 ELF 的 .ARM.exidx 和 .ARM.extab 中 [7] 。下图是 ARM 定义的回溯指令集合，相比 Dwarf 的实现简单一些。
用 ndk 命令 arm-linux-androideabi-readelf -u lib<your32bit>.so 可以看到 Android 各种 32 位 so 的 ARM Unwind table。
[4]. Call Frame Information Example: http://www.dwarfstd.org/doc/DWARF4.pdf#page=253
[5]. Ehframe: https://refspecs.linuxfoundation.org/LSB_3.0.0/LSB-Core-generic/LSB-Core-generic/ehframechpt.html
[6]. Dwarf 标准: http://www.dwarfstd.org/doc/DWARF4.pdf#page=140
[7]. ARM Exception Handling: https://developer.arm.com/documentation/ihi0038/b/
如何改进栈回溯的实现方式
假如你使用过基于 EH 的回溯库，能体会到它的性能负担有多大。基本可以确定，在能使用 fp 的情况下从性能角度来说是最好的。不过我们也会遇到某些 frame pointer 无法应对的场景：比如当我们想针对某个 so 库（源码可能也不太容易获取）进行 Hook 或 Tracing 的时候，它可能并没有开启 frame pointer，这在 32 位上比较常遇到，而通常这些 so 会附带着 unwind tables，此时基本只能选像 libunwind 或者 libunwindstack 这类基于 EH 的回溯库。
另外前面也提到过用 fp 回溯没办法穿过 JNI 函数以及系统生成 OAT 代码的，因为这些 Android 平台实现没有遵守 fp 的使用约定。
我们能做哪些改进？
当把目光聚焦在 unwind tables 表格上的时候，可能会留意到这样一个问题：我们为了拿到函数的返回地址，却完整的恢复每一帧所有寄存器的状态。在处理异常或者调试的时候这样做非常有用，但栈回溯的时候貌似有些浪费。
进一步，我们还会看到在 .eh_frame 和 .debug_frame 的情况下还存在更多损耗性能的地方。
扒开 .eh_frame 的内部，unwind tables “表”数据被叫做 Frame Description Entry(FDE) 的结构保存着，FDE 包含了某个范围里的 pc 地址该如何恢复寄存器的一组组具体操作指令集合。每个 FDE 引用一个 Common Information Entry(CIE)， CIE 保存共用的操作指令集合用于共享，所以多个 FDE 可以引用相同的 CIE。这些设计节省空间的同时，也增加了 unwind 需要的操作，当需要寻找某个 pc 对应的 CFA(Canonical Frame Address) 计算规则时，在找到 FDE 时可能会需要逐行计算直到找到 pc 所在的“行”。同时 Dwarf 标准为计算每个寄存器提供了计算的规则，其中最复杂的 expression 和 val_expression 规则支持了一套基于栈的完备操作指令，如果遇到这些规则，性能也会被拖累。这样来看也能理解为何 EH unwind 库的性能会比较差。
所以我们也许可以抛弃掉不需要恢复的寄存器，同时把寄存器的计算简化（抛弃可能涉及到多个寄存器参与的计算、同时简化必要寄存器取值规则），性能上应该会有很大改善。
方便理解用 .ARM.exidx 来举个例子（.eh_frame 的命令解释起来有点麻烦）：
上图是一个 .ARM.exidx entry，描述虚拟栈寄存器 vsp 的回溯，pop 命令描述了其后跟随的寄存器将从栈上读取自己的值，同时再次修改 vsp。整个过程下来 vsp 计算了三次，而我们可能只关心 r14 这个存放了返回地址的寄存器具体是多少（r14 是 lr 寄存器）。所以整个计算可以简化 vsp 直接偏移 28 + 256 + (4 * 9) = 320，4 字节乘以 9 个寄存器，r14 则保存在 vsp 计算后偏移 -4 的内存地址上， 写成操作就是：vsp = vsp + 320; r14 = [vsp - 4];
.eh_frame 也能做类似的简化具体不介绍了，大概就是这样。
如何回溯穿过 JNI、OAT、JIT
接下来我们还要顺便解决另外 3 个问题：回溯穿过 JNI 函数、OAT 代码、JIT 代码。Android 在官方提供的 libunwindstack 库中已经支持了回溯 Android 虚拟机各种特性的能力。为了避免啰嗦，我们直接看具体的做法。
1. 穿过 JNI
Android 的 JNI 函数调用是有保存栈帧基地址到某个特定寄存器的，32 位上是 r10，64 位是 x28，具体可以看 AOSP 代码 [8.1] [8.2] 。我们只要持续恢复 JNI 的特定寄存器就可以回溯穿过 JNI 函数了。
2. 穿过 OAT
Android 生成的 OAT 本质上是一个 ELF 文件。在 Android 8.0 之后的版本的 OAT 都带有 .debug_frame section。在 7.1 ~ 6.0 需要 setprop debug.generate-debug-info true 才行 [9] ，所以一般来说 8.0 之前没法穿过 OAT。Android 8.0 之后的 OAT 不但提供了 .debug_frame，还可以用 OAT 函数地址从符号表中查询到对应的 Java 函数名称。
如果是解释模式下，虚拟机都运行在 libart.so 里，这时 r4 寄存器（32 位）和 x19/x20 寄存（64 位）保存的 dex pc 描述了当前正在执行的 dex 指令地址，具体可查看 AOSP 代码 [10.1] [10.2] [10.3]。所以我们可以顺便恢复 dex pc，这样在打印堆栈的时候可以从 Dex 里找回对应的函数签名。
3. 穿过 JIT
Android 的 JIT 稍微有点繁琐，当 Java 函数被执行足够多次（默认 1 万次）之后就会被 JIT 成机器码，存放在 jit-cache 的内存中。虽然和 OAT 一样都是机器代码，但 jit-cache 不是 ELF 结构的，他的 debug info 被单独存放在 __jit_debug_descriptor [11] ，专门留给调试工具获取 JIT debug info，也是从 Android 8.0 开始出现在 AOSP 中。
[8.1] art_quick_generic_jni_trampoline(arm): https://cs.android.com/android/platform/superproject/+/android-11.0.0_r3:art/runtime/arch/arm/quick_entrypoints_arm.S;drc=fa458ac21af98b3bdde2c62ed86b9c192b994372;l=1584
[8.1] art_quick_generic_jni_trampoline(arm64): https://cs.android.com/android/platform/superproject/+/android-11.0.0_r3:art/runtime/arch/arm64/quick_entrypoints_arm64.S;drc=fa458ac21af98b3bdde2c62ed86b9c192b994372;l=1870
[9] generate-debug-info: http://androidxref.com/7.1.1_r6/xref/art/dex2oat/dex2oat.cc#328
[10.1] Why r4: https://cs.android.com/android/platform/superproject/+/master:art/runtime/interpreter/mterp/arm/main.S;l=97?q=CFI_DEX
[10.2] Why x20(mterp): https://cs.android.com/android/platform/superproject/+/master:art/runtime/interpreter/mterp/arm64/main.S;l=99?q=CFI_DEX
[10.3] Why x19(switch): https://cs.android.com/android/platform/superproject/+/master:art/runtime/arch/arm64/quick_entrypoints_arm64.S;drc=81a6bd5a05ee3b2bb87ec4a0b471198dbbef3ce3;l=2556
[11] __jit_debug_descriptor: https://cs.android.com/android/platform/superproject/+/android-11.0.0_r3:art/runtime/jit/debugger_interface.cc;drc=4d125afe9c92bc1d58da74355de80c4c38377eae;l=39
Quicken Unwind Table
如何精简回溯计算、如何穿过 Android 虚拟机都已弄清楚，然后我们需要的就是一套符合自己诉求的操作指令集，在 unwind 时解释执行。
模仿 ARM 我们也编辑了一张 QUT 的指令表。可以看到只有我们关心的寄存器才有相应的指令，比如 r7/r11 是 fp 寄存器，r4 可能存放了 dex pc，r10 存放着 JNI 的栈基地址，lr 是返回地址。
性能表现
我们从 ELF 文件的 .eh_frame、.debug_frame、.ARM.exidx 经过精简生成出对应的 QUT 表，就可以用来在运行时快速的进行栈回溯。通过 Benchmark 进行对比，QUT 回溯速度相较于 EH unwind（基于 libunwindstack 库），60 帧调用栈的回溯速度提升约 15 ~ 30 倍（性能越差的机器提升越明显）。18 帧调用栈不穿过虚拟机时，相较于 fp ，QUT 耗时约是 fp 耗时的 4 ~ 5 倍。
回溯覆盖率
QUT 精简掉了不支持的寄存器恢复以及基于这些寄存器进行计算的相关规则。为了评估牺牲掉的无法回溯场景情况，我们收集了几个不同厂商 ROM 的 system libraries 及 boot.oat + boot-framework.oat 加上微信进行统计计算，发现不支持的情况非常少。
生成 QUT 数据
还需要考虑的问题是何时生成 QUT 数据。一个可选的时机是在 APP 编译时顺便生成，但这会对包体积带来负担，并且 OAT 文件要在手机环境下才能获取到。所以运行时生成，是一个综合来说更好的选择。
QUT 数据生成速度通常很快，大多数的库只需要几十毫秒，然而有个例外：boot-framework.oat，这个系统 oat 包含的 entry 以及对应行数非常庞大，慢的情况可能需要数分钟的时间来生成。
QUT 数据占用的空间不大，整个系统库以及 oat 加上微信的 so 全部生成出来的数据大概是 10 ~ 20M。因为最终数据将通过 mmap 到内存，根据实际使用到的情况，可能有大概 10M 左右的内存消耗。
QUT 的优势和局限性
QUT 具有比 unwind tables 高出 15 ~ 30 倍的性能提升，不过对比 fp 的回溯仍然处于劣势（ fp 的 4 ~ 5 倍，波动性相比 fp 也更大）。它更适合在 fp 实际使用情况复杂的 ARM 32 位环境下得到出场机会。
QUT 也能同时获取到 Java 堆栈（因为可以回溯 JNI/OAT/JIT）。在需要回溯出 Java 堆栈的情况下，我们也尝试对比了 QUT 和 native 获取 Java 堆栈的性能，总的来说 QUT 有基本不输于 Java 堆栈的获取性能（遇到性能较差的机器可能会稍好一些），而且避免了涉及和改变虚拟机状态，适用性会更广一点。
还需要留意到 QUT 在运行时生成，会需要一个预热（Warm-up）的过程，并且受限于 ELF 文件是否携带了 Exceptions Handling 信息（有可能没带）。在预热完成前会根据遇到的 entry 生成临时的 QUT 数据。
总结
设计实现 QUT 的初衷是希望在 32 位环境下通过 hook 监控某些资源使用的调用栈，过程中察觉到 libunwindstack 的性能问题也发现基于异常处理的回溯有不少的改善空间。业界也有人提出类似的思路，比如 Reliable and Fast DWARF-Based Stack Unwinding 这篇论文 [12] 就描述了精简回溯过程后直接生成机器码的技术，有很大参考意义。
[12] https://hal.inria.fr/hal-02297690/document
QUT 的兼容性和适应性会比较强，因为实现原理都是依托于业界标准以及 Android 主动提供的调试能力（基础是异常处理和 Android 虚拟机提供的 debug info 及 JNI 约定）。但同时也有一些明显的局限性，得根据实际需要来使用，比如在缺少 fp 寄存器或从 Native 直接穿过 ART 虚拟机（可直接获取 Java 调用栈）等。
实现 QUT 没有想象的复杂，因为标准中涉及到栈基地址计算的指令很有限，除此之外都是可以精简的部分。
生成 QUT 可以基于 libunwindstack 改造实现，源码已经回流到 Matrix v1.0 版本中：
https://github.com/Tencent/matrix
欢迎一键三连。