也谈栈和栈帧

一个码农要是没遇见过coredump，那他就是神仙了。core file(coredump的转储文件)中保存的最重要内容之一，就是函数的call trace。还原这部分内容 (栈回溯) ，并与原代码对应上，尽快找出程序崩溃的位置和原因，是码农们一生的责任。当然，你如果有良好的开发环境和开发习惯，保留了现场环境（core file and lib file等）和unstrip的原程序，那么恭喜，也许你不用太费神，直接用GDB的backtrace功能，就可以找到症结所在。当然如果栈被冲掉了一部分， backtrace出来的就是一堆问号，要找出call trace就不容易了。这在缓冲区溢出时经常碰到。

好了废话少说，切入正题，先谈与call trace密切相关的栈和栈帧概念。

1. 栈和栈帧
栈（stack）相对整个系统而言，调用栈（Call stack）相对某个进程而言，栈帧（stack frame）则是相对某个函数而言，调用栈就是正在使用的栈空间，由多个嵌套调用函数所使用的栈帧组成。具体来说，Call stack就是指存放某个程序的正在运行的函数的信息的栈。Call stack 由 stack frames 组成，每个 stack frame 对应于一个未完成运行的函数。

在当今多数计算机体系架构中，函数的参数传递、局部变量的分配和释放都是通过操纵栈来实现的。栈还用来存储返回值信息、保存寄存器以供恢复调用前处理机状态。每次调用一个函数，都要为该次调用的函数实例分配栈空间。为单个函数分配的那部分栈空间就叫做 stack frame，或者这样说，stack frame 这个说法主要是为了描述函数调用关系的。

Stack frame 组织方式的重要性和作用体现在两个方面：

第一，它使调用者和被调用者达成某种约定。这个约定定义了函数调用时函数参数的传递方式，函数返回值的返回方式，寄存器如何在调用者和被调用者之间进行共享；

第二，它定义了被调用者如何使用它自己的 stack frame 来完成局部变量的存储和使用。

2. 压栈和出栈
在 RISC 计算机中主要参与计算的是寄存器，saved registers 就是指在进入一个函数后，如果某个保存原函数信息的寄存器会在当前函数中被使用，就应该将此寄存器保存到堆栈上，当函数返回时恢复此寄存器值。而且由于 RISC 计算机大部分采用定长指令或者定变长指令，一般指令长度不会超过32个位。而现代计算机的内存地址范围已经扩展到 32 位甚至64位，这样在一条指令里就不足以包含有效的内存地址，所以RISC计算机一般借助于一个返回地址寄存器 RA(return address) 来实现函数的返回。几乎在每个函数调用中都会使用到这个寄存器，所以在很多情况下 RA 寄存器会被保存在堆栈上以避免被后面的函数调用修改，当函数需要返回时，从堆栈上取回 RA 然后跳转。
移动 SP 和保存寄存器的动作一般处在函数的开头，这个压栈过程也叫做 function prologue；恢复这些寄存器状态的动作一般放在函数的最后，出栈过程也叫做 function epilogue。压栈出栈指令各个CPU也不相同。
Stack Frame 中所存放的内容和存放顺序，则由目标体系架构的调用约定(calling convention)定义。下面，我们看看图形化的函数栈帧，以栈向下增长为例来了解几种常用CPU的 stack frame 组织方式。

3. MIPS栈帧
先看MIPS的栈帧布局图：

此图描述的是一种典型的MIPS stack frame 组织方式。在这张图中，sp(stack pointer)/s8 (栈基址,又称fp) 就是当前函数的栈指针，它指向栈顶的位置。Callee Frame 所示即为当前函数(被调用者)的 frame，Caller Frame 是当前函数的调用者的 frame。general register area根据需要保存ra、gp、s8等 caller的寄存器信息，保存位置和顺序暂时没有发现明确的规律。

在MIPS这种没有BP(base pointer) 寄存器的目标架构中，进入一个函数时需要将当前栈指针向下移动 n个byte ( 字节 ) ，这个大小为n个 byte 的存储空间就是此函数的 stack frame 的存储区域。此后栈指针便不再移动，只能在函数返回时再将栈指针加上这个偏移量恢复栈现场。由于不能随便移动栈指针，所以寄存器压栈和出栈都必须指定偏移量，这与 x86 架构的计算机对栈的使用方式有着明显的不同。所以， MIPS一般是sp跟s8一致，只有调用alloca或动态数组后fp才会移到新的frame边界。

另外提一下两个重要的寄存器。MIPS有个寄存器 t9，专门用来跳转子函数时预装子函数地址。跳转子函数的汇编命令是：jalr t9。这条命令后面8个 byte 的地址就是子函数栈帧中保留的ra值。 MIPS的寄存器gp则用来存放某些变量或GOT信息，它的获取是在函数的开头三条语句完成，计算公式：gp = x <<16 + y + t9 。三条语句是：

lui gp, x
addiu gp, gp, y
addu gp, gp, t9 #t9就是当前函数的地址，它永远保留着最后一个被调用函数的地址

MIPS的压栈出栈指令分别是ld和sd。

谈x86的栈帧之前，补充一下堆和栈的认识。

1. 堆和栈的关系

我们平时说的堆栈其实是指栈，而实际上堆和栈是两种不同的内存分配。简单罗列一下各方面的异同点。

1).堆需要用户在程序中显式申请，栈不用，由系统自动完成。申请/释放堆内存的API，在C中是malloc/free，在C++中是new/delete。申请与释放一定要配对使用，否则会造成内存泄漏(memory leak)，久而久之系统就无内存可用了，出现OOM（Out Of Memory）错误。一般在return/exit或break/continue等语句时容易忘记释放内存，所以检查内存泄漏的代码时要关注这些语句，看它们前面是否有必要的释放语句free/delete。

2).堆的空间比较大，栈比较小。所以申请大的内存一般在堆中申请；栈上不要有较大的内存使用，比如大的静态数组；而且除非算法必要，否则一般不要使用较深的迭代函数调用，那样栈消耗内存会随着迭代次数的增加飞涨。

3).关于生命周期。栈较短，随着函数退出或返回，本函数的栈就完成了使用；堆就要看什么时候释放，生命周期就什么时候结束。

说了这么多，我们发现解析Coredump还是跟栈的关系相对紧密，跟堆的关系是有一种产生Coredump的原因是访问堆内存出错。

2. x86的栈帧

继续谈栈帧布局，这次说说x86的栈帧布局和操作方法，见栈帧布局图：

上图描述的是一般x86的stack frame栈帧布局方式，当前帧为当前函数(被调用者)的stack frame，调用者的帧为调用函数(调用者)的stack frame。栈底在高地址，栈向下增长。图中，ebp(base pointer)就是栈基址，它指向当前函数的栈帧起始地址；esp(stack pointer)则是当前函数的栈指针，它指向栈顶的位置。压栈的顺序依次为栈基址ebp、其它寄存器、本地变量和临时变量。注意所传递的参数和返回地址lr一般放在调用者的栈帧中，当然按照实际的压栈过程，也有人认为previous ebp也在调用者栈帧内，这个暂时影响不大。

相比于MIPS，x86比较可爱的地方是刚刚提到的两点，就是可以用栈基址和栈指针明确标示栈帧的位置，栈指针esp一直移动，同时压栈的顺序有一定的规律，一个栈空间内的地址前面，必然有一个代码地址（lr）明确标示着调用函数位置内的某个地址。

3. x86的栈操作

x86有一对表示栈底和栈顶的寄存器，寄存器ebp是栈基址指针，指栈帧的底部（高地址），寄存器esp是栈指针，指栈帧的顶部（地址地）。

函数的返回结果是通过寄存器eax传递的，因此在函数退出前会将计算结果拷贝到eax中，然后再出栈返回调用者。

再来关注几个常用的函数内外跳转指令：

call：调用一个函数。以寄存器和偏移量来调用函数和c++里的虚函数调用很类似

ret：从一个函数返回。_stdcall调用规范要求如果有返回值，就要将返回值从堆栈的栈顶弹出

leave：是move ESP EBP/pop EBP的简写，用来退出函数，同时释放了为局部变量分配的空间

jmp：无条件跳转

je：如果相等则跳转

jne：如果不等则跳转

顺便提一下数据的传递操作mov和movl，mov是将右操作数复制到左操作数，而movl传递方向相反，是将左操作数复制到右操作数。装入有效地址指令(即用来得到局部变量和函数参数的指针)lea和leal也一样。

最后，x86的压栈出栈指令众人皆知，分别是push和pop，或者其各种变体，比如puchad/popad是对所有通用寄存器的栈操作。

这次讲ARM的栈帧布局和操作方法。
1. ARM的栈帧
先来看看ARM的栈帧布局图：

上图描述的是ARM的栈帧布局方式，main stack frame为调用函数的栈帧，func1 stack frame为当前函数(被调用者)的栈帧，栈底在高地址，栈向下增长。图中FP就是栈基址，它指向函数的栈帧起始地址；SP则是函数的栈指针，它指向栈顶的位置。ARM压栈的顺序很是规矩(也比较容易被黑客攻破么)，依次为当前函数指针PC、返回指针LR、栈指针SP、栈基址FP、传入参数个数及指针、本地变量和临时变量。如果函数准备调用另一个函数，跳转之前临时变量区先要保存另一个函数的参数。
ARM也可以用栈基址和栈指针明确标示栈帧的位置，栈指针SP一直移动，相比于x86，ARM更为鲜明的特点是，两个栈空间内的地址（SP+FP）前面，必然有两个代码地址（PC+LR）明确标示着调用函数位置内的某个地址。

2. ARM的汇编指令和栈操作
    ARM微处理器共有37个寄存器，其中31个为通用寄存器，6个为状态寄存器。但是这些寄存器不能被同时访问，具体哪些寄存器是可编程访问的，取决于微处理器的工作状态及具体的运行模式。但在任何时候，通用寄存器R0～R15、一个或两个状态寄存器都是可访问的。有三个特殊的通用寄存器：
寄存器R13：在ARM指令中常用作堆栈指针SP
寄存器R14：也称作子程序连接寄存器（Subroutine Link Register）即连接寄存器LR
寄存器R15：也称作程序计数器PC
    ARM进行函数内压栈和出栈往往使用如下的语句：
stmfd sp!, {r0-r9, lr}    ; 满递减入栈,给寄存器r0-r9,lr压栈,sp不断减4
ldmfd sp!, {r0-r9, pc}    ; 满递减出栈,给寄存器r0-r9出栈，并使程序跳转回函数的调用点,sp不断增4
    常用的函数内外跳转指令有mov和BL，ARM有两种跳转方式：
（1）mov pc, <跳转地址〉
    这种向程序计数器PC直接写跳转地址，能在4GB连续空间内任意跳转。
（2）通过 B BL BLX BX 可以完成在当前指令向前或者向后32MB的地址空间的跳转（为什么是32MB呢？寄存器是32位的，此时的值是24位有符号数，所以32MB？后面再查查看）。B是最简单的跳转指令。要注意的是，跳转指令的实际值不是绝对地址，而是相对地址——是相对当前PC值的一个偏移量，它的值由汇编器计算得出。BL很常用,它在跳转之前会在寄存器LR(R14)中保存PC的当前内容。BL的经典用法如下：
    bl NEXT       ; 跳转到NEXT
    ……
    NEXT
    ……
    mov pc, lr    ; 从子程序返回。

这次来看看PowerPC体系架构CPU的栈帧布局和操作方法。PowerPC用得不多，有不对的地方大家拍砖啊~~

1. PowerPC的栈帧
先来看看PowerPC的栈帧布局图：

上图描述的是PowerPC的栈帧布局方式，PowerPC的栈生长方向也是由高到低，caller是调用者，current是被调用者。压栈的顺序依次是FPR、GPR、CR、Local Variable、Function Parameters、Padding、LR和Back Chain Word。具体涵义如下：
(1)函数参数域FPR（Function Parameter Register）：这个区域的大小是变化的，当调用者传递给被调用者的参数少于8个时，用GPR3-GPR10这8个寄存器就行，被调用者的栈帧中就可不要这个区域；但如果传递的参数多于8个时就需要这个区域。
(2)通用寄存器GPR（General Parameter Register）：当需要保存GPR寄存器中的一个寄存器GPRx时，就需要把从GPRx-GPR31的值都保存到堆栈帧中。
(3)CR寄存器：即使修改了CR寄存器的某一个段CRx（x=0至7），都要保存这个CR寄存器的内容。
(4)局部变量域（Local Variables Area）：同上FPR所示，如果临时寄存器的数量不足以提供给被调用者的临时变量使用时，就会使用这个区域。
(5)Function Parameters：跟第一个FPR重复了？暂时不知。
(6)Padding：是补齐字节数，让当前栈帧的长度保持8Bytes的倍数。
(7)LR：也就是ra寄存器，是指返回时的函数指针。
(8)Back Chain Word：是调用者函数帧的栈顶esp，即上一个栈帧的低地址，当前函数栈帧的基址ebp。
跟x86和ARM一样，压栈的顺序有一定的规律，一个栈空间内的地址前面，必然有一个代码地址明确标示着调用函数位置内的某个地址。而且很容易发现，跟x86一样（如果x86中ebp算是调用者栈帧的话），栈帧的最后两个位置存储的也是ra和ebp。所以可以考虑向x86学习，根据当前ebp的值回溯出整个任务的调用栈，如图中蓝箭头所示，具体操作后面再专门讲述。

2. PowerPC的寄存器
PowerPC的ABI规定的寄存器的使用规则如下：
(1)GPR0：属于易失性寄存器，ABI规定普通用户不能使用此寄存器。GCC编译器用此寄存器来保存LR寄存器，Linux PowerPC用此寄存器来传递系统调用号码。
(2)GPR1：属于专用寄存器，ABI规定用次寄存器来保存堆栈的栈顶指针。注：PowerPC构架没有独立的栈顶指针，这一点和X86体系结构是不同的！
(3)GPR2：属于专用寄存器，ABI规定普通用户不使用才寄存器，Linux PowerPC用此寄存器来保存当前进程的进程描述符地址。
(4)GPR3-GPR4：属于易失性寄存器，ABI使用这两个寄存器来保存函数的返回值，或者用来传递参数。
(5)GPR5-GPR10：也属于易失性寄存器，加上GPR3和GPR4共8个寄存器用来传递函数的参数。当函数的参数超过八个时使用堆栈来传递。
(6)GPR11-GPR12：属于易失性寄存器，ABI规定普通用户不使用该寄存器，Linux PowerPC有时用这两个寄存器来存放临时变量，但是GCC编译器没有使用这两个寄存器。
(7)GPR13：属于专用寄存器，ABI规定该寄存器sdata段的基地址指针。Linux PowerPC在系统初始化时使用该寄存器来存放临时变量。GCC有时会根据某些规则将一些常用的数据放入sdata或者sbss段中。应用程序对sdata或者sbss段数据的访问与对data和bss段数据的访问机制不同，访问sdata段的数据速度更快。
(8)GPR14-GPR31：属于非易失性寄存器。ABI使用这些寄存器来存放一些临时变量，在应用程序中可以自由使用这些变量。

3. PowerPC的汇编指令和栈操作
    PowerPC寄存器没有专用的push和pop指令来执行堆栈操作，所以PowerPC构架使用存储器访问指令stwu、lwzu来代替push和pop指令。
    下面我们通过一个例子来说明堆栈帧的建立、使用和移除过程：
    func1中开始几行汇编会为自己建立栈帧：
func1:    mflr %r0                ;Get link register
          stwu %r1,-88(%r1)       ;Save back chain then move sp
          stw %r0,+92(%r1)        ;Save link register
          stmw %r28,+72(%r1)      ;Save 4 non-volatiles r28-r31
    func1的结尾几行，会移除前面建立的栈帧，并使得SP（即GPR1）寄存器指向上一个栈帧的栈顶(即栈帧的最低地址处，也就是back chair)
    如下所示：
          lwz %r0,+92(%r1)       ;Get saved link register
          mtlr %r0               ;Restore link register
          lmw %r28,+72(%r1)      ;Restore non-volatiles
          addi %r1,%r1,88        ;Remove frame from stack
          blr                    ;Return to caller function

程序发生Crash时，一般会coredump出转储文件core file。Crash调查的最直接目标是根据core file进行栈回溯或还原栈帧, 即find call trace。同时根据寄存器和出错处汇编代码，分析Crash的深层次原因，并提出解决方法。

1. coredump设置
    要使coredump时产生合适的core file，需正确设置corefile format，这个在procfs中可以定制：
/proc/sys/kernel/core_pattern
    core_pattern包含全路径，比如是/var/core/%e-%p-%t，则表示：/var/core/进程名-进程PID-CrashTime
    顺便关注一下内核源码中，core file及其名字的生成过程：
do_signal                            # arch/x86/kernel/signal.c
-> get_signal_to_deliver            # kernel/signal.c
->    do_coredump
->      format_corename              # fs/exec.c

为了使生成的core file发挥更为直观的作用，要注意编译exec file（executed-file）时加上-g选项，这样通过gdb工具查找到的信息才更有价值。关于core file和exec file，有几个注意点。

MUST have exec file together, the unstrip is better;
MUST have shared lib file together, if some code is in lib;
MUST accordant with core file and exec file!

2. Crash调查
如果做到了上面说的几点，发生coredump时能保留现场环境，那么正常情况下gdb的backtrace命令就能找到call trace。也就不用下面那么费劲。
但总会出现一些不好处理的异常情况。比如在x86结构CPU的程序crash时，也许会出现一堆问号，如下所示：
(gdb) bt
#0 0xb5ff6106 in raise () from /lib/libc.so.6
#1 0xb6112ff4 in ?? () from /lib/libc.so.6
#2 0xb459f900 in ?? ()
#3 0xbfed551c in ?? ()
#4 0xb5ff7be1 in abort () from /lib/libc.so.6
#5 0x00000004 in ?? ()
Previous frame inner to this frame (corrupt stack?)

出现异常的可能原因是exec file的symbol不存在或不匹配。根据之前对x86栈帧布局图的分析（http://blog.chinaunix.net/uid-16459552-id-3328601.html），bp-ra（即栈帧基址-返回地址）必定在栈帧顶端的固定位置，可以利用这个分布特点进行栈回溯。从当前的bp0开始，找到上一个bp1=*bp0，ra1=*(bp0 + 4)，ra1就是调用函数的地址。继续回溯，bp2=*bp1，ra2=*(bp1 + 4)，ra2应该是再上一级调用函数的地址。如此循环，同时用info symbol $ra* 打印出来每一级函数，就找到实际的call trace信息了。

3. 栈回溯示例
    获取pc(即eip)和bp(即ebp)的值，为回溯第一步作准备。执行gdb命令info register：
(gdb) i r
eax            0x0 0
ecx            0x3e4a 15946
edx            0x6 6
ebx            0x3e4a 15946
esp            0xbfed53f8     0xbfed53f8
ebp            0xbfed5400 0xbfed5400
esi            0xbfed54a0 -1074965344
edi            0xb6111ff4 -1240391692
eip            0xb5ff6206 0xb5ff6206 <raise+70>
eflags         0x202 [ IF ]
cs             0x73 115
ss             0x7b 123
ds             0x7b 123
es             0x7b 123
fs             0x0 0
gs             0x33 51

实现上述栈回溯的shell脚本代码关键部分如下：

 echo  "Call func is: " 
 info symbol $pc        #打印当前函数的符号（即名字） 
 x/4x $ebp              #显示上一个栈帧顶部 4 个内存地址中的值，首先是上一个栈帧的bp和调用函数ra。保存在文件call trace .log中最后一行 
 #下面是循环迭代部分 
 bp_now=$(tail -l  "calltrace.log" | awk -F:  '{print$1}' )     #当前栈帧基址 
 bp_up=$(tail -l  "calltrace.log" | awk  '{print$2}' )          #上一个栈帧基址 
 func_up=$(tail -l  "calltrace.log" | awk  '{print$3}' )        #上一个栈帧对应函数 
 if  [ $bp_up =  "Cannot"  -o $bp_up =  "can't"  ]; then 
      exit 
 else 
      gdb -q  "$exec_file" "$core_file" << EOF 
      set loggint redirect on 
      set prompt 
      set logging file  "calltrace.log" 
      set height  0 
      echo Call  function in : 
      print/x $func_up 
      info symbol $func_up          #打印上一个栈帧对应函数的符号（即名字），形成call  trace ! 
      echo Upper frame bp  is : 
      print/x $bp_up 
      x/4x $bp_up                   #为下一次回溯作准备! 
      quit 
 EOF 
 fi   

一次回溯的打印结果如下所示：
Call func is:
raise + 70 in section .text #当前函数
0xbfed5400: 0xbfed552c 0xb5ff7bd1 0x00000006 0xbfed54a0

Call function in:$1 = 0xb5ff7bd1
abort + 257 in section .text #上一个调用函数
Upper frame bp is:$2 = 0xbfed552c
0xbfed552c: 0xbfed5b78 0xb602f2ab 0x00000004 0xbfed5664

......

x86的backtrace异常还有一种情况是只能回溯一二级栈帧，如下所示：

(gdb) bt
#0 0xb5ff6106 in raise () from /lib/libc.so.6
(gdb) x $ebp
0x0: Cannot acess memory at adderss 0x0

这种情况一般是因为栈溢出，最外层的部分栈帧被冲掉了，所以无法进行栈回溯。这时，还是可以利用bp-ra在固定位置的分布特点来调查，从当前sp开始找“栈地址-函数地址”对，找到后就开始按上面的方法回溯。

4. PowerPC和ARM的栈回溯
鉴于PowerPC和ARM结构的CPU也有类似的栈帧布局，也可以采用上面的方法解决backtrace异常的问题。PowerPC栈帧布局特点见http://blog.chinaunix.net/uid-16459552-id-3459993.html ，ARM栈帧布局特点见http://blog.chinaunix.net/uid-16459552-id-3364761.html 。由于暂时没有target环境，也未找到合适的虚拟硬件场景技术，所以无法为PowerPC和ARM类型的CPU程序Crash调查提供栈回溯例子，以后有机会补上。