Android Native | 调用栈回溯-五八三

当程序出现异常时，我们通常依赖调用栈来展开分析。它表明了程序运行到某个位置时的函数调用关系。这个关系在开发者眼中是函数名和行号，但它背后其实是函数调用时跳转指令的地址。换言之，函数名和行号只是指令地址的代号，是方便人类可读的一层外套。因此，如果想要得到下面的调用栈信息，第一步需要收集每一帧的跳转指令地址，我们称它为“栈回溯”或“栈展开”(stack unwind)，第二步才是将指令地址转换为人类可读的字符串信息。

序号   ELF文件中的偏移    ELF文件的名称                                    函数名+函数中的偏移
#00 pc 0000000000056270  /apex/com.android.runtime/lib64/bionic/libc.so (abort+168)
#01 pc 00000000000bf9dc  /apex/com.android.runtime/lib64/bionic/libc.so (__pthread_internal_find(long, char const*)+200)
#02 pc 00000000000bf8f4  /apex/com.android.runtime/lib64/bionic/libc.so (__pthread_internal_gettid(long, char const*)+12)
#03 pc 00000000000c017c  /apex/com.android.runtime/lib64/bionic/libc.so (pthread_kill+52)

这个调用栈是从tombstone中截取的一个片段。Tombstone，中文译为“墓碑”，表示进程在native层发生crash时留下的最后影像。这里的pc值，譬如0x56270，表示的是指令地址相对于libc.so文件起始位置的偏移值。而abort加号后面的168，表示的则是指令地址相对于abort函数起始位置的偏移值。

那么如何回溯出调用栈中每一帧的跳转指令地址呢？

回溯本质上是调用的逆过程，因此为了弄明白回溯，我们首先要了解调用。

众所周知，寄存器的数量是有限的。因此随着调用的发生，势必会出现caller(调用者)和callee(被调用者)使用同一个寄存器的情况。解掉这个冲突有三种思路：

Caller不依赖这些寄存器，因此不要求它们在调用过程中保持不变。
Caller在调用前将这些寄存器保存在栈上，调用后再恢复它们。
Callee在使用这些寄存器之前将它们暂存到栈上，返回时再恢复它们。

上述第二和第三种思路的区别在于暂存值保存在谁的栈上。第二种思路知道caller依赖哪些寄存器，第三种思路知道callee使用哪些寄存器，因此从减少暂存范围的角度而言，二者各有优劣。AArch64架构采用的是第三种思路，因此寄存器也被分成不同的类型。X19-X28这些”Callee-saved Registers”表明callee使用前需要将它们暂存。在栈上分配空间并执行暂存操作的代码称为prologue(序幕)，而返回前执行恢复操作并释放栈空间的代码称为epilogue(尾声)。

X0-X7	X8-X15	X16-X23	X24-X30
Parameter and Result Registers (`X0-X7`)	`XR` (`X8`)	`IP0` (`X16`)	Callee-saved Registers (`X24-X28`)
–	Corruptible Registers (`X9-X15`)	`IP1` (`X17`)	`FP` (`X29`)
–	–	`PR` (`X18`)	`LR` (`X30`)
–	–	Callee-saved Registers (`X19-X23`)	–

除了callee-saved寄存器以外，其实还有个关键信息需要暂存：返回地址。AArch64采用LR(Link Register，也即x30)寄存器来保存返回地址，因此prologue中也需要暂存它。如下是libbinder.so中的BpBinder::linkToDeath函数，可以看到prologue中除了暂存x19-x25这些callee-saved registers外，也暂存了x30。不过这里需要注意一点，x30大多数情况下都暂存在栈上，但也有可能暂存在其他寄存器之中，这取决于编译器。

android::BpBinder::linkToDeath(android::sp<android::IBinder::DeathRecipient> const&, void*, unsigned int)():
   7207c: d503233f     	paciasp
   72080: d101c3ff     	sub	sp, sp, #112
   72084: a90367fe     	stp	x30, x25, [sp, #48]
   72088: a9045ff8     	stp	x24, x23, [sp, #64]
   7208c: a90557f6     	stp	x22, x21, [sp, #80]
   72090: a9064ff4     	stp	x20, x19, [sp, #96]
   72094: d53bd058     	mrs	x24, TPIDR_EL0

上面我们说想要回溯出每一帧的跳转指令地址，可是这里prologue暂存的是返回地址，那么二者之间有什么关系呢？

通常而言，返回地址指向跳转指令的下一条指令。因此拿到这些返回地址后，我们可以减去一定偏移，将它转换为跳转指令的地址。对于指令长度固定的架构，譬如A64（指令长度为4字节），我们可以减去固定的偏移。但对于指令长度变长的架构，譬如T32（指令长度为2字节或4字节），就无法减去固定的偏移。一个行之有效的方式是减一，因为不论指令长度为多少，减完之后的地址都会落在上一条指令的范围内。因此实际操作中通常用返回地址减一得到跳转指令的地址。

那么现在的问题就变成了：如何找到每一帧的LR暂存值？

这里分叉出两条不同的技术路线。一种是基于DWARF调试信息的常规方式，另一种是依赖编译选项开启的快速方式。

DWARF全称为”Debugging With Arbitrary Record Formats”，是一种调试信息的规范，如今已经发布到第五个版本。这个规范规定了各种调试信息的存储格式，其中与调用栈回溯相关的信息为”Call Frame Information”。它的主要目的就是根据callee的寄存器和栈内存来恢复出caller的寄存器和返回地址，换言之，caller的上下文。恢复出来的上下文一般有以下三个用途：

调试。某些变量的值或地址会存储在寄存器中，因此想要查看这些变量的信息，必须要恢复出这一帧的上下文。
异常处理。异常抛出后需要遍历调用栈，从而寻找可以处理该异常的帧，并跳转到相应的处理方法中，因此需要每一帧的返回地址。
调用栈打印。不论是崩溃分析还是性能分析，调用栈都是不可或缺的关键信息，因此也需要每一帧的返回地址。

以下是BpBinder::linkToDeath函数对应的Call Frame Information(CFI) Table。

00004ba0 0000000000000024 00004ba4 FDE cie=00000000 pc=000000000007207c..00000000000722e8
   LOC           CFA      x19   x20   x21   x22   x23   x24   x25   ra    
000000000007207c sp+0     u     u     u     u     u     u     u     u     
0000000000072080 sp+0     u     u     u     u     u     u     u     u     
0000000000072094 sp+112   c-8   c-16  c-24  c-32  c-40  c-48  c-56  c-64

CFA: Canonical Frame Address，通常被定义为前一帧中调用位置的sp的值。

ra: return address，返回地址寄存器。

u: Undefined rule，表明该寄存器暂时还没有使用，因此无需恢复，直接用就行。

c-16: c表示CFA的值。

首先我们注意到，这个表中的行数并不多，远远少于函数里的汇编指令数量。它们将函数地址分为三个区间([0x7207c, 0x72080); [0x72080, 0x72094); [0x72094, end of function])，pc值落在哪个区间，就采用哪一行的方式来恢复上下文。举个例子，当callee的pc=0x72098时，我们采用第三行的方式来恢复上下文。先用sp寄存器的值加上112得到CFA，之后再用CFA减去不同的偏移得到各个寄存器在栈上暂存的地址，最终获取到caller的上下文。这里的CFA是一个固定的锚点，通常被定义为前一帧中调用位置的sp的值。之所以不用这一帧的sp，是因为sp在函数内部可能会动态变化。

对于绝大多数经过Clang编译的64位函数而言，使用到的计算规则其实只有一套，也即上述列表的第三行。原因是prologue将寄存器暂存之后，如果sp后续都没有变化的话，那么计算规则也就无需改变。而这种情况在真实场景中占了绝大多数。那么为何上述表格中还存在三行呢？原因是函数起始位置占一行，PAC机制的引入又增加一行，余下的函数主体再占一行。

Android中使用的Call Frame Information来自ELF文件的eh_frame(eh: exception handling)段，而并非debug_frame段。事实上正常运行的库都只会有一个eh_frame段，原因是运行时需要支持异常处理，但并不需要支持动态调试。二者均遵照DWARF格式，但是内部有些细微的差别。譬如，eh_frame默认异常不会从prologue和epilogue抛出，因此不会为prologue和epilogue生成额外的处理规则，CFI Table中也不会体现。譬如BpBinder::linkToDeath中的指令地址0x72084，此时sp已经改变，但是CFI Table中的CFA计算规则并没有改变。原因就是unwind过程中根本不会存在pc值为0x72084的可能。

如下是具体的解释，感兴趣的可以了解下。

Ideally, eh_frame will be the minimal unwind instructions necessary to unwind the stack when exceptions are thrown/caught. eh_frame will not include unwind instructions for the prologue instructions or epilogue instructions — because we can’t throw an exception there, or have an exception thrown from a called function “below” us on the stack. We call these unwind instructions “synchronous” because they only describe the unwind state from a small set of locations.

debug_frame would describe how to unwind the stack at every instruction location. Every instruction of the prologue and epilogue. If the code is built without a frame pointer, then it would have unwind instructions at every place where the stack pointer is modified. We describe these unwind instructions as “asynchronous” because they describe the unwind state at every instruction location.

其实上面的表格是虚构的，它并不是eh_frame段真实的内容。真实的内容如下所示，是一系列DWARF指令的集合。运行时根据指令构造出如上的表格，继而找到对应的计算规则。这种方式对于表格很大，且上下行重复信息较多的场景非常有用（指令只描述上下差异的信息），可以有效压缩eh_frame段的大小。

    Program:
  DW_CFA_advance_loc: 4
  DW_CFA_AARCH64_negate_ra_state:
  DW_CFA_advance_loc: 20
  DW_CFA_def_cfa_offset: +112
  DW_CFA_offset: reg19 -8
  DW_CFA_offset: reg20 -16
  DW_CFA_offset: reg21 -24
  DW_CFA_offset: reg22 -32
  DW_CFA_offset: reg23 -40
  DW_CFA_offset: reg24 -48
  DW_CFA_offset: reg25 -56
  DW_CFA_offset: reg30 -64
  DW_CFA_nop:
  DW_CFA_nop:

稍微了解DWARF格式的朋友可能会好奇，这篇文章为什么不说一说CIE，FDE这些具体的结构。原因是我认为对于unwind而言，最直观的信息是上面的CFI table，而CIE和FDE只是这些信息的压缩和存储方式，它们对于理解unwind的核心概念无足轻重。况且，这些信息的介绍直接参考DWARF官方文档就好，没有人可以写得比它更好。

基于DWARF调试信息的这种方式适用范围广，但是性能差强人意，因此在很多需要频繁收集调用栈的场景中并不适用。既然我们在unwind过程中最终的目标是找到每一帧的返回地址，那么可以在栈中快速定位它么？事实上这种快速定位的方式早已存在，它被命名为fp-based unwind，依赖于特殊的编译选项-fno-omit-frame-pointer。

Frame pointer是一个固定的锚点，其作用相当于CFI Table中的CFA。当编译选项-fno-omit-frame-pointer被置上后，AArch64平台会将X29寄存器拿来专门存储frame pointer，并且在prologue中将它暂存到栈上，存储位置的地址将成为新一帧X29的值。因此，栈上每一帧的frame pointer构成了一个链表结构，调用栈回溯时可以快速地拿到它们。

fp unwind.png

可是光拿到这些frame pointer并没有用，我们想要的仍然是返回地址。如果能让暂存的返回地址和frame pointer有一个固定偏移，那么拿到返回地址也将容易很多。因此，-fno-omit-frame-pointer还有一个隐含的含义需要提及：Prologue中暂存的并非是单一的frame pointer，而是frame pointer和返回地址的组合，称为frame record。它们紧密相连，frame pointer在低地址，返回地址（LR寄存器的值）在高地址。这样一来，unwind过程就可以大大加速了。

如今Android中的系统库默认都打开了-fno-omit-frame-pointer编译选项，但是一些vendor库和APP的三方库并不能保证。因此fp-based unwind的适用范围依然很小，通常只在sanitizer开启的场景中使用（unwind非常频繁）。如果APP可以保证自己所用的三方库都开启了-fno-omit-frame-pointer，那么fp-based unwind无疑是最好的选择（不过需要判别JNI函数，从而采用不同的策略去穿越JNI、机器码执行和解释执行）。

退而求其次的方案是优化DWARF-based unwind，微信在这篇文章里讲述了一种优化策略，核心思路是省去unwind过程中对于callee-saved registers的恢复，只保留CFA和return address，取得了很好的效果。

Frame pointer的开启是一个趋势，纵然它会稍稍增大code size，但是带来的好处是更大的，否则Kernel和Android也不会默认将它打开。当下选择DWARF-based unwind更多是一种无奈（Android中的unwind库libunwindstack采用的是DWARF-based unwind），一种考虑兼容性和普适性的选择。

延伸讨论：

我在写这篇文章的时候参考了一些资料，发现介绍Call Frame Information Table时，给出的示例表中行数都比较多，其中大多数对应的都是prologue和epilogue的地址，譬如DWARF官方文档给出的示例（如下）。正是由于行数比较多，所以才需要压缩，才需要将表格信息转换为DWARF指令。

可是eh_frame是不考虑prologue和epilogue的。而且我实际看了几个Android的库，不论是否开启-fno-omit-frame-pointer，每个函数的Call Frame Information Table中都只有两行或三行，取决于是否开启PAC，而其中函数主体对应的计算规则只有一行。再进一步，如果我们只考虑CFA和return address，那么每个函数需要保存的信息将会非常非常少。这样一来，我们是否还需要压缩和运行时解释呢？

DWARF example.png