iOS 调用栈回溯
前言
在做「大内存分配监控系统」时，我深入学习了一下堆栈回溯相关的底层原理，以及符号化相关的知识。这篇文章是当时记下的学习笔记。
调用栈回溯的目的是追踪某个函数的调用链。比如函数 A 调用了函数 B，函数 B 又调用了函数 C，调用链就是 A → B → C。调用栈回溯拿到的一般是函数的内存地址信息，无法看到函数名，需要再做一次符号化操作。
本文参考： App LibcArm DeveloperProcessor_registerDive into System
CPU 寄存器
CPU 寄存器是 CPU 芯片上数据存储的小型区域，位于内存结构的顶部，具有最快的数据访问速度，用来暂时存放参与运算的数据和运算结果。 ARM64 指令集提供了下列用于调用栈的寄存器：
x0~x30 通用寄存器负责的功能如下：
- x0~x7: 参数寄存器，用于把参数传递给函数并返回结果。可以用作临时寄存器或调用者保存的寄存器变量，可以在调用其他函数之间的函数内保存中间值。
- x8: 间接(indirect)结果寄存器，传递间接结果的地址位置。
- x9~x15: 调用者保存的临时寄存器。
- x16~x17: 过程调用临时寄存器。
- x18: 平台寄存器，保留共 ABI (Application Binary Interface) 平台使用。
- x19~x28: 被调用者保存的寄存器。
- x29: 栈帧指针寄存器 (FP)。
- x30: 链接寄存器(LR)。
SP (Stack Pointer) 栈指针是编译器保留用于维护堆栈布局的寄存器，总是指向栈顶。
PC (Program Counter) 是程序计数器，也叫指令寄存器，指向 CPU 即将要执行的下一条指令，存储的是代码内存区域的地址（一般是 Text 区域）。
FP (Frame Pointer) 是栈帧指针寄存器，指向当前堆栈帧的基址，也就是栈帧的起始地址。
LR (Link Register) 是链接寄存器，存储当前函数结束后需要执行的下一指令的地址（这个地址是代码区的地址）。
SP 和 FP 是相关的本地数据寄存器。一个是「本地数据在哪里」，另一个是「最后一个本地数据在哪里」。对于单核处理器，实现多线程并发的本质是通过时间片算法让处理器在多个任务之间反复切换，制造出假并发现象。在多任务模式下，每个任务都有自己的栈空间，每个栈空间都能存储当前 CPU 寄存器的状态，以及当前栈指针的位置。当调度程序认为有必要进行任务切换时，只需将当前线程栈的上下文信息进行保存（保存在内存中某个位置），切换到另一个线程的上下文信息即可。这个操作通常由一个特殊的队列进行控制，被挂起的线程会被置于这个队列的末尾，并在将来某个时间被恢复执行。
调用栈结构
计算机系统中函数调用信息是存储在线程调用栈中的。每个函数的调用信息入栈时以「栈帧 (stack frame)」为单位入栈，栈帧包含了单个函数的参数、局部变量以及返回地址等信息。
有必要说一下，调用栈里面有负责存储寄存器值的内存区域，比如存储 x29(FP) 以及 x30(LR) 。这是为了某个函数调用完成后，栈帧 pop 后，寄存器能恢复成函数调用者的状态。负责存储 x29(FP) 的内存块存储的是上一个栈帧的 FP 寄存器的值，类似于一个链表的结构，能够向高地址方向溯源。
下图是 arm64 的栈帧结构，灰色区域为被调用者 Callee 的函数栈帧，蓝色区域为调用者 Caller 的栈帧。在图中我们可以看到两个寄存器指针 SP 和 FP，SP 指向了当前栈的栈顶（下图向上为高地址，栈向下增长），FP 指针指向当前栈帧负责存储 FP 数据的区域。
栈在内存中由高地址向低地址增长，而堆由低地址向高地址增长。当两者相遇时，表示计算机已经没有可用内存分配给当前进程，会触发 OOM 崩溃。
寄存器和堆栈的运作
上面的内容介绍了寄存器和堆栈的一些基础知识。这部分内容就就说一下在函数调用的过程中，寄存器和堆栈是怎么配合的。
代码转汇编
先用一段简单的 C 代码模拟一下函数调用关系吧。
#include <stdio.h>
int assign() {
int y = 40;
return y;
}
int adder() {
int a;
return a + 2;
}
int main() {
int x;
assign();
x = adder();
printf("x is: %d\n", x);
return 0;
}
把这段代码转为汇编（用 Xcode 就可以转，当然也可以用一些终端指令 gcc -o prog prog.c objdump -d prog ）。下面的转换后的函数地址都去掉了开头的 0xffffffff 。
0000000000000724 <assign>:
724: d10043ff sub sp, sp, #0x10
728: 52800500 mov w0, #0x28 // #40
72c: b9000fe0 str w0, [sp, #12]
730: b9400fe0 ldr w0, [sp, #12]
734: 910043ff add sp, sp, #0x10
738: d65f03c0 ret
000000000000073c <adder>:
73c: d10043ff sub sp, sp, #0x10
740: b9400fe0 ldr w0, [sp, #12]
744: 11000800 add w0, w0, #0x2
748: 910043ff add sp, sp, #0x10
74c: d65f03c0 ret
0000000000000750 <main>:
750: a9be7bfd stp x29, x30, [sp, #-32]!
754: 910003fd mov x29, sp
758: 97fffff3 bl 724 <assign>
75c: 97fffff8 bl 73c <adder>
760: b9001fa0 str w0, [x29, #28]
764: 90000000 adrp x0, 0 <_init-0x598>
768: 91208000 add x0, x0, #0x820
76c: b9401fa1 ldr w1, [x29, #28]
770: 97ffffa8 bl 610 <printf@plt>
774: 52800000 mov w0, #0x0 // #0
778: a8c27bfd ldp x29, x30, [sp], #32
77c: d65f03c0 ret
注意汇编语言前面的第一列地址不是进程的堆栈区内存地址，而是 Text 区域的地址，也就是程序代码区域的地址。
寄存器和堆栈工作原理
下图表示程序刚开始执行时的堆栈区域和寄存器状况。 0xef10 0xef18 这些是堆栈中的地址，可以看到这个栈正在由高地址向低地址增长。0xef50 为栈的起始地址，被存储在 sp 和 x29 (fp) 寄存器中，其他寄存器存储的是初始脏数据。这时候，pc 寄存器存储的是将要执行汇编程序中地址为 0x750 的指令。
处理器开始执行 0x750 那行指令。首先将 sp 指针减去 32 字节，得到 0xef30，存到 sp 寄存器里，意味着为新的栈帧开辟一片空间。然后 stp 操作将 x29 和 x30 这两个寄存器的当前值存到栈里，对应的栈内存地址分别为 sp 和 sp+8。这时候栈帧里面的 fp 块就指向了当前栈帧的内存起始地址（注意这是栈帧里面存储的 fp 的值，并不是 fp 寄存器）。紧接着，pc 寄存器下移 4 字节，指向下一条将要执行的指令。
下一条指令 mov x29 sp 将 x2 (fp) 寄存器更新为 sp 的值。现在 x29，也就是 fp 指针，指向了 main 函数的栈帧起始位置。接着 pc 继续下移 4 字节，准备执行下一条指令。
b1 指令将 pc+4 存储到 x30 (lr) 寄存器中，表示即将调用另一个函数，将返回地址 0x75c 存到 lr 寄存器中。assign 函数返回后，程序将回到 lr 寄存器存的指令地址。然后 pc 寄存器更新值为 0x724，也就是 assign 函数第一条指令的地址。
程序来到了 assign 函数里面。sub sp, sp, #0x10 将 sp 地址减去 16 字节。现在 fp 和 sp 之间就是当前活跃的栈帧区域了。pc 继续下移 4 字节，准备执行下一条指令。
mov w0, #0x28 将常量 0x28 存到 w0 寄存器中。pc 继续下移 4 字节。
这里的0x28就是十进制 40 的十六进制表示。这一行汇编指令意在执行 assign 函数里面的代码：int y = 40;
str w0, [sp, #12] 将 0x28 存到距离 sp 偏移 12 个字节的地方，也就是堆栈地址为 0xef2c 的地方。pc 下移 4 字节。
ldr w0, [sp, #12] 将堆栈地址 0xef2c 中的 0x28 保存到寄存器 w0 中。pc 下移到下一条指令。
add sp, sp, #0x10 将 sp 地址加 16 个字节，跟上面减 16 个字节相反。这一步意思是当前函数即将结束，当前栈帧要 pop 掉，因此将 sp 恢复到先前值 0xef30。
ret 指令将 pc 寄存器的值换成 x30 (lr) 寄存器中的值，即 0x75c。表示 assign 函数结束，返回到 main 函数地址为 0x75c 那一行的指令。
bl 73c <adder> 指令和上面的 bl 724 <assign> 类似，表示要进入函数 adder 里了。x30 寄存器更新值为 pc+4，即 0x760。pc 值更新为 0x73c，即 adder 函数指令的起始地址。
adder 函数第一条指令 sub sp, sp, #0x10 将 sp 地址减去 16 字节，意味着给新的函数栈帧开辟空间。x29 (fp) 和 sp 之间的堆栈内存区域现在是新的栈帧活跃边界。pc 指针下移 4 字节。
ldr 20, [sp, #12] 将 sp+12 地址的初始（脏）数据加载并存储到 w0 寄存器中。可以看到程序并没有给 w0 赋初始值，因为我们的代码就没写初始化操作，只是声明了一个变量。pc 指针继续下移。
当前正在执行 adder 函数里面的这一行代码： int a;现在 w0 (局部变量 a) 的脏数据就是上面调用 assign 函数留下来的 0x28，即十进制 40。
add w0, w0, #0x2 指令将 w0 寄存器存的值加 2，把结果 0x2A 仍旧存到寄存器 w0 中。pc 指针下移 4 字节。
add sp, sp, #0x10 将 sp 地址加 16 字节，表示当前函数 adder 即将返回，要销毁当前栈帧。这一操作将 sp 地址指向了先前值（调用 adder 函数之前的值）。pc 指针继续下移到下一条指令。
ret 指令将 pc 寄存器值更新为 x30 寄存器存的值，下一条指令将会是地址为 0x760 的那一行指令。
str w0, [x29, #28] 指令将 w0 寄存器中的内容 0x2A 存到 x29 + 28 字节的地方，也就是 0xef4c。
adrp x0, 0x0 将地址 0x0 存到 x0 寄存器中。w0 寄存器是 32 位的，x0 是 64 位的，而地址一般是 8 字节长度，因此使用 x0 寄存器。add x0, x0, #0x820 将 x0 加上了 0x820，x0 存储的是内存地址 0x820。而内存地址 0x820 里存储的是字符串 “x is %d\n”。pc 指针下移。
ldr w1, [x29, #28] 指令将之前存放在内存地址 0xef4c （也就是 x29 偏移 28 个字节）里面的 0x2A 拿出来存到 w1 寄存器里。
bl 610 <printf@plt> 开始调用 printf 函数：
int printf(const char * format, ...)printf 函数代码地址为 0x610，接收若干个参数（在本例子里是两个）。对于接收若干参数的函数，gcc 编译器会将前 8 个参数放到 x0 ~ x7 寄存器中，剩下放不完的会放到堆栈内存中 fp 指针下面。
当 printf 函数调用时，x30 寄存器更新值为 pc+4 （也就是 0x774)，pc 寄存器指向 printf 的代码地址 0x610，sp 栈指针指向为 printf 函数开辟的栈帧的栈顶。
当 printf 函数结束调用后，0x2A 对应的十进制 42 这个值会被输出到屏幕上。sp 寄存器回到之前的值，pc 寄存器更新为之前存到 x30 寄存器中的值 0x774。
mov w0, #0x0 将常量 0x0 存到 w0 寄存器中。这个值将会在 main 函数结束时被返回。pc 下移到下一条指令。
ldp x29, x30, [sp], #32 指令先将 sp 和 sp+8 的值分别拷贝到 x29 和 x30 寄存器中，即恢复这两个寄存器的值为执行 main 函数之前存储的值。ldp 指令的最后一部分，即 [sp], #32 将 sp 指针向高地址偏移 32 字节，即恢复到执行 main 函数之前的栈顶。ldp 指令结束后，sp, x29, x30 三个寄存器都恢复到了执行 main 函数之前的值。pc 寄存器下移到下一个指令。
ret 指令将存在 w0 寄存器中的 0x0 返回，意味着程序正常结束运行。
调用栈回溯
回溯原理
根据上面的寄存器和堆栈的关系示例以及调用栈的结构图，可以得知： 函数 A 在调用函数 B 时，调用栈会开辟一个栈帧，并且把 x29 寄存器存的栈帧地址存放到新的栈帧里。顺着这些存起来的栈帧指针，就能将调用栈完整的回溯一遍。回溯调用栈的时候，我们能在栈帧里面拿到存放的 x30 寄存器的返回函数的汇编代码内存地址，这样就能边回溯边拿到各个函数的代码内存地址。通过代码内存地址以及符号表偏移量就能进一步获取函数的签名信息，从而拿到可读的调用栈信息。
手搓代码
不通过系统 API 直接获取调用栈信息，手动遍历栈帧地址。
int KEPStackTraceHelper::mach_backtrace(thread_t thread, void** stack, int maxSymbols) {
_STRUCT_MCONTEXT machineContext;
mach_msg_type_number_t stateCount = THREAD_STATE_COUNT;
kern_return_t kret = thread_get_state(thread, THREAD_STATE_FLAVOR, (thread_state_t)&(machineContext.__ss), &stateCount);
if (kret != KERN_SUCCESS) {
return 0;
}
int i = 0;
#if defined(__arm__) || defined (__arm64__)
stack[i] = (void *)machineContext.__ss.__lr;
++i;
#endif
void **currentFramePointer = (void **)machineContext.__ss.__framePointer;
while (i < maxSymbols) {
void **previousFramePointer = (void **) *currentFramePointer;
if (!previousFramePointer) break;
// int sizeofFP = (*currentFramePointer); 可以看到 *currentFramePointer 类型的大小是 8 字节
stack[i] = *(currentFramePointer+1); // 加 8 bytes
currentFramePointer = previousFramePointer;
++i;
}
return i;
}
从获取 _STRUCT_MCONTEXT 类型的 machineContext 可以看出，大部分操作系统都有栈空间的概念。CPU 在时间片切换时，将一个线程的寄存器信息保存到内存里，把另一个将要活跃的线程的寄存器信息从内存中读出来。
backtrace API
Linux、macOS、iOS 内核都提供了一个 backtrace 函数，能够直接获取当前调用栈的函数代码内存地址：
vm_address_t *stacks_2[128];
int depth = backtrace((void **)stacks_2, 128); // 结果存放到 stacks_2 里面
backtrace 函数源码可以在 Apple Libc 里面找到，下载地址见文章开头。
