Sep 1, 2016

函数调用原理

栈的基本概念

在计算机科学中，栈（stack）是一种特殊的串行数据结构，它的特点是只能允许在链表或数组的一端进行添加数据和删除数据的操作，按照后进先出（LIFO）的原理运作。 可操作的一端称为栈顶（top），栈顶可指向栈的第一个元素或者第一个元素前的空地址，这依赖于栈的实现，在x86_64的机器上栈顶指向第一个元素。 不可操作的一端称为栈底，栈底是栈开始的地址。 栈有两个最重要的操作，添加数据的操作称为push，删除数据的操作称为pop。 高级语言（high-level language）的一个重要特征是引入了过程（procedure）和函数（function）。 函数的原理类似于跳转，即一个函数结束时会将控制权交回调用它的函数。这个特点的高级抽象就是后进先出，因此它的实现需要借助栈。 进程为了实现函数机制，在地址空间中专门开辟了一块栈段。 进程地址空间大致被分为三个区域：代码段、数据段，堆栈段。 这三个段区依次由低地址向高地址排布（x86_64的机器）。如下图：

进程的地址空间

虽然进程的地址空间是从低地址向高地址排布，但是栈段是从高地址向低地址生长的（这一点很重要），即栈底为高地址，栈顶为低地址。  

程序的栈帧

函数调用栈（call stack）使用栈数据结构保存进程中函数调用信息。 函数调用栈位于进程地址空间的栈段。 每个正在运行的函数在栈段都有自己的栈帧，栈帧的排布根据函数的调用关系后进先出，如下图。

程序的栈帧

一个挂起函数的栈帧包括调用函数（也是上一个栈帧）的栈底地址、局部变量、被保存的寄存器、临时变量、调用下一个函数的参数、返回地址。

单个函数的栈帧

切换过程

在x86_64机器上，使用两个寄存器标记当前函数的栈帧，rbp和rsp。 rbp称为基址寄存器，标记当前栈帧的栈底，rsp可称为栈寄存器，标记当前栈帧的栈顶。 栈帧的切换，也是函数调用的过程就是围绕这两个寄存器实现的。 当函数foo调用bar时： - 1）在新的栈帧中保存旧栈帧的栈底地址%rbp，在此之前 1)’ rsp向下移动一格 - 2）将新栈帧的栈底地址%rsp保存到rbp中，同时使 2)’ rbp指向新栈帧的栈底

新建栈帧流程

新建栈帧过程是通过下面两条汇编代码实现的。

1) push    %rbp
2) mov     %rsp,    %rbp

当函数bar返回foo时： - 3）将栈底指针的地址%rbp保存到rsp中，同时使 3)’ 栈顶指针指向栈底 - 4）旧栈底的地址保存到rbp中，同时使 4)’ rbp指向旧栈底，rsp向上移动一格

恢复栈帧流程

这个过程是通过leave指令实现，它等价于下面的汇编代码。

3) mov     %rbp,     %rsp
4) pop     %rbp

函数调用涉及到过程的转移，支持过程转移的汇编指令主要是call和ret。 call指令有一个目标操作数，这格操作数是被调用过程的起始的指令地址。 call指令的效果是将返回地址入栈，并跳转到被调函数的起始处。 返回地址是在程序中call指令后面的那条指令地址，当被调函数返回时，控制流会从这个地址继续执行。 ret指令从栈中弹出返回地址，并跳转到这个位置继续执行，此时被调函数结束。

实例演示

现在实现一个程序，在foo函数中调用bar函数，使用GDB来观察函数的栈帧和真实的栈帧切换。

foo函数的c代码、汇编和地址信息：

foo函数代码

bar函数的c代码、汇编和地址信息：

bar函数代码

在foo函数中，调用bar函数的指令callq指向的地址正是bar函数的起始地址0x400494。 另一个需要注意的地址是函数调用的返回地址0x4004c6。 在foo调用bar后，在bar函数的栈帧中可以看到这个地址。

foo函数的callq将控制流从foo转移到bar函数和bar函数的retq将控制流从bar函数交回给foo函数。

foo函数和bar函数的前两个指令和倒数第二个指令相同，分别是建帧和恢复帧的指令。 foo函数的第三条指令是预分配局部变量指令，会统一预留16字节的空间，此时修改了rsp的值，然后开始分配局部变量的空间。 但是在bar函数中并没有这条指令，因为bar函数是最后调用的简单函数，没有使用rsp。 我们在16行和10行加上断点，运行程序。

断点运行

程序在第16行暂停，此时程序在执行foo函数，我们查看rbp和rsp的内容，它们指向的是foo的栈帧，并验证栈是从高地址向低地址生长的。

foo的栈信息

然后让程序继续运行，程序在第10行停止，此时程序在执行bar函数，我们查看rbp和rsp的内容。

bar的栈信息

rbp和rsp的值已经更新，指向了bar的栈帧。我们查看当前的内存，

内存中的内容

bar栈帧的rbp指向的地址内保存的是foo栈帧的rbp地址，内存块1的值是地址3的值。 我们可以计算出当前foo的栈帧地址为0x7fffffffe4d0 – 0x7fffffffe4c8。 内存块2的值即为调用返回的指令地址。

在第17行加上断点查看bar返回后rbp和rsp的值。

恢复foo栈帧后的栈信息

此时rbp和rsp的值和调用前一样了。

小恶作剧

既然知道了函数栈帧的原理，我们可以通过修改返回地址，实现最简单的栈溢出例子。

void foo() {
    int *ret;
    ret = &ret + 2;
    (*ret) += 1;
}

void main() {
    int x;
    x = 0;
    foo();
    x = 1;
    printf("x=%d\n", x);    //output:  x=0
    return;
}

我们通过将局部变量ret地址往高地址移动2个单位可以找到返回地址的地址，然后修改返回地址，程序将跳过x=1这行，直接打印出x等于0。

偏移计算

本文使用的gcc版本为4.4.5 20110214 (Red Hat 4.4.5-6)，编译时没有使用优化选项。

参考文献：

1. https://en.wikipedia.org/wiki/Stack_(abstract_data_type)

2. 《深入理解计算机系统》

3. < Smashing The Stack For Fun And Profit>

4. http://www.cnblogs.com/bangerlee/archive/2012/05/22/2508772.html

5. http://blog.chinaunix.net/uid-23069658-id-3981406.html

Tags: 计算机基础