前言

在内核中有一个非常好用的函数dump_stack, 该函数在我们调试内核的过程中可以打印出函数调用关系，该函数可以帮助我们进行内核调试，以及让我们了解内核的调用关系。同时当内核发生崩溃的时候就会自己将自己的调用栈输出到串口。 栈回溯非常有利于我们进行问题定位与代码跟踪。

在用户态如果想要展现出函数的调用栈，我们通常就需要使用gdb工具。在调试的时候可以使用gdb进行单步调试并显示栈。或者在程序崩溃的时候产生转储文件，再通过gdb进行分析崩溃时的程序堆栈。但是这样的工具似乎并不能完全替代dump_stack函数的作用。比如说通过dump_stack可以清晰的了解到一个函数是被从哪些地方进行的调用，以及通过dump_stack可以在一些错误的位置打印调用信息。

C库backtrace使用

#include <execinfo.h>
#include <stdio.h>
#include <stdlib.h>
#define BT_BUF_SIZE 100
void print_backtrace() {
    void *bt_buffer[BT_BUF_SIZE];
    int bt_size = backtrace(bt_buffer, BT_BUF_SIZE);
    char **bt_strings = backtrace_symbols(bt_buffer, bt_size);
    printf("backtrace:\n");
    for (int i = 0; i < bt_size; i++) {
        printf("%x %s\n", bt_strings[i]);
    }
    free(bt_strings);
}
int func_c() {
    print_backtrace();
    return 0;
}
int func_b() {
    return func_c();
}
int func_a() {
    return func_b();
}
int main() {
    return func_a();
}

上面是使用C库 backtrace进行栈回溯的例程，我们可以发现使用C库中的backtrace理论上可以轻松实现栈回溯功能。

但是嵌入式编译器往往对于这个接口的支持非常弱，很多情况下使用这个接口编译器是不支持的，就算支持很多时候是得不到函数的调用栈的，所以我们需要自己实现函数backtrace的功能。

ARM64 栈回溯实现

arm64的backtrace实现是最简单的，因为arm64 支持FP，且寄存器信息被存储于栈顶位置并且栈的结构非常固定。

arm64寄存器

下面是Arm64程序调用标准规定的通用寄存器的使用方法。

参数寄存器（X0-X7）函数参数数量小于等于8个时，使用X0-X7传递，大于8个时，多余的使用栈传递，函数返回时返回值保存在X0中。

调用者保存的临时寄存器（X9-X15） 调用者若使用到了X9-X15寄存器，在调用子函数之前，需要将X9-X15寄存器保存到自己的栈中，子函数使用这些寄存器的时候不需要保存和恢复。

被调用者保存的寄存器（X19-X29） 被调用者若使用到这些寄存器，需要将其保存到自己的栈中，返回时从栈中恢复。
特殊用途的寄存器

X8是间接结果寄存器。用于传递间接结果的地址位置，例如，函数返回一个大结构。

X16-X17过程内调用暂存寄存器。。

X18平台寄存器。

X29是栈帧（FP）寄存器。保存了调用函数的栈帧地址。

X30保存了返回地址（LR）。函数返回后跳转到该地址处运行。

arm64栈结构

arm64调用规则

实例代码：

nt func3()
{
    anycall_dump_stack();
    return 0;
}
 
void func2()
{
    func3();
}

void func1()
{
    func2();
}
int main()
{
    func1();
}

下图是main汇编代码

0000000000400804 <func3>:
  400804:	a9bf7bfd 	stp	x29, x30, [sp, #-16]!
  400808:	910003fd 	mov	x29, sp
  40080c:	97ffffc1 	bl	400710 <anycall_dump_stack@plt>
  400810:	52800000 	mov	w0, #0x0                   	// #0
  400814:	a8c17bfd 	ldp	x29, x30, [sp], #16
  400818:	d65f03c0 	ret

000000000040081c <func2>:
  40081c:	a9bf7bfd 	stp	x29, x30, [sp, #-16]!
  400820:	910003fd 	mov	x29, sp
  400824:	97fffff8 	bl	400804 <func3>
  400828:	d503201f 	nop
  40082c:	a8c17bfd 	ldp	x29, x30, [sp], #16
  400830:	d65f03c0 	ret

0000000000400834 <func1>:
  400834:	a9bf7bfd 	stp	x29, x30, [sp, #-16]!
  400838:	910003fd 	mov	x29, sp
  40083c:	97fffff8 	bl	40081c <func2>
  400840:	d503201f 	nop
  400844:	a8c17bfd 	ldp	x29, x30, [sp], #16
  400848:	d65f03c0 	ret

000000000040084c <main>:
  40084c:	a9bf7bfd 	stp	x29, x30, [sp, #-16]!
  400850:	910003fd 	mov	x29, sp
  400854:	97fffff8 	bl	400834 <func1>
  400858:	52800000 	mov	w0, #0x0                   	// #0
  40085c:	a8c17bfd 	ldp	x29, x30, [sp], #16
  400860:	d65f03c0 	ret

主要查看main函数的入口位置，函数的入口最早做的就是对函数跳转的现场进行保存：

40084c: a9bf7bfd stp x29, x30, [sp, #-16]!

这一行表示把上一个函数的FP和LR寄存器push保存到sp-16的位置上，并且对sp地址-16操作，也就是说对于 main 函数预留了16 bytes的堆栈空间进行使用。

400850: 910003fd mov x29, sp

第二行，表示更新main函数使用的堆栈帧地址到FP中。这样通过FP寄存器我们可以在后续调用中对main函数的栈帧再进行保存。参考后面调用func1函数的操作。

400854: 97fffff8 bl 400834 <func1>
这一步会执行跳转操作，同时会把返回地址更新到LR寄存器。

在FUNC1 子函数中，我们看到依然是同样的套路，第一步会先把FP和LR寄存器保存到堆栈中：

400834: a9bf7bfd stp x29, x30, [sp, #-16]!
这一行就把main函数使用的FP和LR寄存器保存到堆栈中了，并且对SP寄存器地址-16，含义就是预留了16 bytes的堆栈空间给func1使用。再接着看该函数的最后返回：

400844: a8c17bfd ldp x29, x30, [sp], #16
这里把上一级main函数使用的FP和LR从堆栈中恢复出来了。同时对sp寄存器执行+16操作，从而恢复上一级函数的堆栈指针现场，然后调用ret操作：

400848: d65f03c0 ret
这一行会自动把LR寄存器保存的地址赋值给PC，也就因此跳转回main函数继续运行。

arm64栈回溯方式

所以 arm64的栈回溯其实只需要不断对FP进行解引用，分别得到每一个栈帧的起始地址，然后就可以得到每一个栈中保存的函数返回地址与下一个栈帧地址。

代码大致如下：

实现效果

ARM 栈回溯实现

相对于ARM64 arm实现栈回溯要困难一些，因为arm的寄存器直接存储在栈底，需要借助FP去寻找到每一个栈底。

arm寄存器

arm栈结构

Arm 处理器总共有 37 个寄存器，其可以分为以下 2 类：

1. 通用寄存器（ 31 个）
   1. 不分组寄存器（ R0 — R7 ），共 8 个。
   2. 分组寄存器（ R8 — R14 ）共22个（R8-R12,五个，一共52=10，R13-14，两个，一共是216=12，总共10+12=22个）
   3. PC 指针（ R15 ）,共1个
2. 程序状态寄存器（ 6个 ）
   1. CPSR（ 1个 ）
   2. SPSR（ 5个 ）
      

arm调用规则

想要比较容易的在arm中实现栈回溯需要在编译的是时候添加-mapcs -marm参数来保证 编译器编出按照固定规则入栈的代码。

000106e8 <func3>:
   106e8:	e1a0c00d 	mov	ip, sp
   106ec:	e92dd800 	push	{fp, ip, lr, pc}
   106f0:	e24cb004 	sub	fp, ip, #4
   106f4:	ebffffc0 	bl	105fc <anycall_dump_stack@plt>
   106f8:	e3a03000 	mov	r3, #0
   106fc:	e1a00003 	mov	r0, r3
   10700:	e89da800 	ldm	sp, {fp, sp, pc}

00010704 <func2>:
   10704:	e1a0c00d 	mov	ip, sp
   10708:	e92dd800 	push	{fp, ip, lr, pc}
   1070c:	e24cb004 	sub	fp, ip, #4
   10710:	ebfffff4 	bl	106e8 <func3>
   10714:	e320f000 	nop	{0}
   10718:	e89da800 	ldm	sp, {fp, sp, pc}

0001071c <func1>:
   1071c:	e1a0c00d 	mov	ip, sp
   10720:	e92dd800 	push	{fp, ip, lr, pc}
   10724:	e24cb004 	sub	fp, ip, #4
   10728:	ebfffff5 	bl	10704 <func2>
   1072c:	e320f000 	nop	{0}
   10730:	e89da800 	ldm	sp, {fp, sp, pc}

00010734 <main>:
   10734:	e1a0c00d 	mov	ip, sp
   10738:	e92dd800 	push	{fp, ip, lr, pc}
   1073c:	e24cb004 	sub	fp, ip, #4
   10740:	ebfffff5 	bl	1071c <func1>
   10744:	e3a03000 	mov	r3, #0
   10748:	e1a00003 	mov	r0, r3
   1074c:	e89da800 	ldm	sp, {fp, sp, pc}

再添加-mapcs之后所有的入栈都将按照

   10734:	e1a0c00d 	mov	ip, sp
   10738:	e92dd800 	push	{fp, ip, lr, pc}

arm栈回溯实现

实现效果

MIPS 栈回溯实现

MIPS栈回溯相比于ARM与ARM64则更为复杂。因为MIPS平台，FP指针默认指向栈顶，而返回地址存在了栈底，所以说需要使用其他方法进行栈回溯。

MIPS寄存器

v0, v1: 用做函数调用的返回值。当这两个寄存器不够存放返回值时，就需要使用堆栈，调用者在堆栈里分配一个匿名的结构，设置一个指向该参数的指针，返回时v0指向这个对应的结构（由编译器自动完成）。

a0- a3: 用来传递前四个参数给子程序，不够的用堆栈。a0-a3和v0-v1以及ra一起来支持子程序／过程调用，分别用以传递参数，返回结果和存放返回地址。当需要使用更多的寄存器时，就需要使用堆栈，MIPS编译器总是为参数在堆栈中留有空间以防有参数需要存储。

fp: 不同的编译器对此寄存器的解释不同，GNU MIPS C编译器使用其作为帧指针，指向堆栈里的过程帧（一个子函数）的第一个字，子函数可以用其做一个偏移访问栈帧里的局部变量，sp也可以较为灵活的移动，因为在函数退出之前使用fp来恢复。

MIPS调用规则

如图 描述的是一种典型的(MIPS O32)嵌入式芯片的Stack Frame组织方式。在这张图中，计算机的栈空间采用的是向下增长的方式（MIPS架构没有专门入栈和出栈指令，栈的增长方向不定，可能是高地址向低地址增长，或是相反），SP(stack pointer)就是当前函数的栈指针，它指向的是栈底的位置。Current Frame所示即为当前函数(被调用者)的Frame，Caller’s Frame是当前函数的调用者的Frame 。
在没有BP(base pointer)寄存器的目标架构中，进入一个函数时需要将当前栈指针向下移动n字节，这个大小为n字节的存储空间就是此函数的Stack Frame的存储区域。此后栈指针便不再移动（在Linux内核代码TODO里面写着要加上在函数内部调整栈的考虑 – 虽然这通常不会发生），只能在函数返回时再将栈指针加上这个偏移量恢复栈现场。由于不能随便移动栈指针，所以寄存器压栈和出栈都必须指定偏移量，这与x86架构的计算机对栈的使用方式有着明显的不同。
RISC计算机一般借助于一个返回地址寄存器RA(return address)来实现函数的返回。几乎在每个函数调用中都会使用到这个寄存器，所以在很多情况下RA寄存器会被保存在堆栈上以避免被后面的函数调用修改，当函数需要返回时，从堆栈上取回RA然后跳转。移动SP和保存寄存器的动作一般处在函数的开头，叫做Function Prologue；
注意如果当前函数是叶子函数（不存在对其它函数的调用，就不保存ra寄存器，反之就保存）。恢复这些寄存器状态的动作一般放在函数的最后，叫做Function Epilogue。

我们可以看一下mips平台的反汇编代码：

004012fc <func3>:
  4012fc:	27bdffe0 	addiu	sp,sp,-32
  401300:	afbf001c 	sw	ra,28(sp)
  401304:	afbe0018 	sw	s8,24(sp)
  401308:	03a0f021 	move	s8,sp
  40130c:	0c100479 	jal	4011e4 <anycall_dump_stack>
  401310:	00000000 	nop
  401314:	0000c021 	move	t8,zero
  401318:	03001021 	move	v0,t8
  40131c:	03c0e821 	move	sp,s8
  401320:	8fbf001c 	lw	ra,28(sp)
  401324:	8fbe0018 	lw	s8,24(sp)
  401328:	27bd0020 	addiu	sp,sp,32
  40132c:	03e00008 	jr	ra
  401330:	00000000 	nop

00401334 <func2>:
  401334:	27bdffe0 	addiu	sp,sp,-32
  401338:	afbf001c 	sw	ra,28(sp)
  40133c:	afbe0018 	sw	s8,24(sp)
  401340:	03a0f021 	move	s8,sp
  401344:	0c1004bf 	jal	4012fc <func3>
  401348:	00000000 	nop
  40134c:	03c0e821 	move	sp,s8
  401350:	8fbf001c 	lw	ra,28(sp)
  401354:	8fbe0018 	lw	s8,24(sp)
  401358:	27bd0020 	addiu	sp,sp,32
  40135c:	03e00008 	jr	ra
  401360:	00000000 	nop

00401364 <func1>:
  401364:	27bdffe0 	addiu	sp,sp,-32
  401368:	afbf001c 	sw	ra,28(sp)
  40136c:	afbe0018 	sw	s8,24(sp)
  401370:	03a0f021 	move	s8,sp
  401374:	0c1004cd 	jal	401334 <func2>
  401378:	00000000 	nop
  40137c:	03c0e821 	move	sp,s8
  401380:	8fbf001c 	lw	ra,28(sp)
  401384:	8fbe0018 	lw	s8,24(sp)
  401388:	27bd0020 	addiu	sp,sp,32
  40138c:	03e00008 	jr	ra
  401390:	00000000 	nop

00401394 <main>:
  401394:	27bdffe0 	addiu	sp,sp,-32
  401398:	afbf001c 	sw	ra,28(sp)
  40139c:	afbe0018 	sw	s8,24(sp)
  4013a0:	03a0f021 	move	s8,sp
  4013a4:	0c1004d9 	jal	401364 <func1>
  4013a8:	00000000 	nop
  4013ac:	03001021 	move	v0,t8
  4013b0:	03c0e821 	move	sp,s8
  4013b4:	8fbf001c 	lw	ra,28(sp)
  4013b8:	8fbe0018 	lw	s8,24(sp)
  4013bc:	27bd0020 	addiu	sp,sp,32
  4013c0:	03e00008 	jr	ra
  4013c4:	00000000 	nop

我们可以看出函数调用都是先使用addiu sp,sp xxx开辟栈，然后将使用 sw ra,xxx压栈保存在栈底。

MIPS栈回溯实现

在MIPS平台开始栈回溯的时候，我们可以获取的信息有寄存器SP,PC,RA的内容，使用PC和RA我们可以得到当前函数和上一级函数地址，问题在于怎样通过SP寻找到上一级函数的栈，在没有直接获取栈地址的方法的情况下需要通过进行代码分析来实现。

004012fc <func3>:
  4012fc:	27bdffe0 	addiu	sp,sp,-32
  401300:	afbf001c 	sw	ra,28(sp)
  401304:	afbe0018 	sw	s8,24(sp)
  401308:	03a0f021 	move	s8,sp
  40130c:	0c100479 	jal	4011e4 <anycall_dump_stack>
  401310:	00000000 	nop
  401314:	0000c021 	move	t8,zero
  401318:	03001021 	move	v0,t8
  40131c:	03c0e821 	move	sp,s8
  401320:	8fbf001c 	lw	ra,28(sp)
  401324:	8fbe0018 	lw	s8,24(sp)
  401328:	27bd0020 	addiu	sp,sp,32
  40132c:	03e00008 	jr	ra
  401330:	00000000 	nop

1. anycall_dump_stack 获取sp,ra寄存器地址,其中ra指向func3的0x401314。
2. 从func3的返回地址（0x401314）开始向上进行命令查找，在0x401300的位置可以查找到ra寄存器入栈指令sw ra,xxx（0xafbf），取出立即数作为raoffset，其为返回地址在栈空间中的偏移。
3. 继续向上在0x4012fc查找到开辟栈空间的指令addiu sp,sp,-32（0x27bd）,去除立即数 stacksize 即为func3的栈空间大小。
4. 如此ra=sp[raoffset/sizeof(long))] 就可以获取到func1的返回地址，即func2中的0x40134c。
5. 然后nsp=sp+stacksize，可得func2的栈顶。
6. 如此可继续向上回溯。

实现效果

对外接口

int anycall_backtrace(void **array, int size)

获取从当前函数开始的回溯结果保存于array,最大深度size。

char ** anycall_backtrace_symbols(void *const *array, int size)

解析array，并返回符号信息。

int anycall_dump_stack(void)

打印从当前位置开始的堆栈信息