也谈栈和栈帧(一)

    一个码农要是没遇见过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、ARM、PowerPC的图形化栈帧解说。