深入理解栈内存与函数调用栈——以C语言为例

前言
作为数据结构的栈
IA-32寄存器简介
栈内存布局与栈帧
函数调用栈分析
The End

前言

直接借用之前写的《为什么-128的补码是1000 0000？》的开头，毕竟动机相同。

这个问题并不是什么面试题，而是今晚（注：昨晚）刚上大一初学C语言的小辈问我的，一瞬间竟然有点发蒙，不知道该如何回答。好在最后还是理清了思路，顺便将这个非常基础（？）的知识点总结下吧。

问题的起源是如下的照片：

图0

第一眼看到它的时候，内心OS：

这玩意儿为什么会出现在大一上学期的教材里？

吐槽完了。那么今天就把函数调用栈（function call stack）的细节掰开揉碎，彻底弄清楚。本文基于通用的IA-32（即俗称的Intel 32位）指令集架构来研究，下面先来点预备知识。

作为数据结构的栈

栈（stack）是一种后进先出（LIFO）的线性数据结构，数据元素在逻辑上呈堆叠式存储。元素发生进出的一端叫做栈顶（stack top），相对的一端则叫做栈底（stack base）。栈支持压入（push）和弹出（pop）两种操作，如下图所示。

图1

可见，push操作就像是“穿烤串”，pop操作就像是“吃烤串”。

IA-32寄存器简介

寄存器（register）是CPU存储指令和数据的单元。下图示出IA-32架构中的部分寄存器，不包含与本文无关的状态寄存器和段寄存器。

图2

其中，EAX~EDX四个32位寄存器为通用寄存器（general purpose registers），理论上讲是存储什么都可以的。但是在指令集的发展过程中，有一部分指令会有特殊要求，需要以特定的通用寄存器来存储操作数或输出结果。所以，EAX经常被用作累加器（A=accmulator），EBX作为数据基地址的暂存器（B=base），ECX作为循环计数器（C=counter），EDX作为操作数或操作结果暂存器（D=data）。

为了方便存储较短的数据，通用寄存器都可以只使用低16位，此时称为AX~DX。低16位还可以进一步拆分为两个更小的8位寄存器，低8位称为AL~DL，高8位称为AH~DH。

ESI和EDI有时也被包括在通用寄存器内，但它们不能拆分，一般用作字符串操作的源指针和目的指针，不再赘述。那么剩下的ESP和EBP寄存器是做什么的呢？它们与栈内存密切相关，下面来看。

栈内存布局与栈帧

所有x86架构的实现都会在内存中划分堆区和栈区。堆区是支持动态内存分配的空间，由用户自行管理和利用，而栈区是由系统管理的内存空间，简要的布局如下图所示。

图3

可见，堆区是按照地址空间顺序生长的，栈区则是逆序生长的，栈底位于高地址，栈顶位于低地址。也就是说，栈区的实际组织方式可以想象成一个倒扣着的杯子（里面装的东西不会主动掉出来）。

那么系统如何知道栈顶现在在哪里？栈顶地址储存在图2所示的ESP寄存器内，SP就是“栈指针”（stack pointer）的缩写。向栈压入元素时，ESP指向的地址值会减小（IA-32中就是减小32位，4个字节），弹出元素则会增大。也就是说，如果我们将EAX寄存器中的数据入栈：

push eax

实际上等价于做了如下两步操作：

sub esp, 4                     ; 栈顶下移
mov DWORD PTR SS:[esp], eax    ; EAX的数据传送到新栈顶的地址

同理，如果将栈顶的数据弹出到EAX：

pop eax

就等价于：

mov eax, DWORD PTR SS:[esp]    ; 当前栈顶地址的数据传送到EAX
add esp, 4                     ; 栈顶上移

栈顶的问题解决了，还有一个新的问题：栈区在物理上是连续而大的空间，如果把它当做一整块区域来用，必然很不方便。所以栈区在逻辑上会组织成多个小的栈，每个小栈叫做栈帧（stack frame）。而EBP寄存器存储的就是位于栈区顶部那个栈帧的栈底地址，BP即“基指针”（base pointer）。这句话有点拗口，画图表示之。

图4

这样，通过EBP和ESP寄存器分别标识当前栈帧的头和尾，我们就可以自如地操作栈帧了。

栈区和栈帧的最主要用途就是保存（C语言的）函数调用栈——包括函数的调用过程与所有上下文信息，如参数、局部变量、返回地址等。下面我们结合实例来探索。

函数调用栈分析

用图0里的那段程序稍微改一改。

int func(int a, int b) {
  int x = 99, y = 77, z;
  z = (a - b) * x / y;
  return z;
}

void caller() {
  int m = 55, n = 33, k;
  k = func(m, n);
}

int main() {
  caller();
  return 0;
}

其中，函数caller()称为主调函数（英文也是caller），函数func()称为被调函数（callee）。执行如下命令，将C代码编译为32位汇编代码：

gcc -S -m32 main.c

查看生成的汇编文件main.s，节选main()函数→caller()函数→func()函数的调用链。

    .globl  _func                   ## -- Begin function func
    .p2align    4, 0x90
_func:                                  ## @func
    .cfi_startproc
## %bb.0:
    pushl   %ebp
    .cfi_def_cfa_offset 8
    .cfi_offset %ebp, -8
    movl    %esp, %ebp
    .cfi_def_cfa_register %ebp
    subl    $20, %esp
    movl    12(%ebp), %eax
    movl    8(%ebp), %ecx
    movl    $99, -4(%ebp)
    movl    $77, -8(%ebp)
    movl    8(%ebp), %edx
    subl    12(%ebp), %edx
    imull   -4(%ebp), %edx
    movl    %eax, -16(%ebp)         ## 4-byte Spill
    movl    %edx, %eax
    cltd
    idivl   -8(%ebp)
    movl    %eax, -12(%ebp)
    movl    -12(%ebp), %eax
    movl    %ecx, -20(%ebp)         ## 4-byte Spill
    addl    $20, %esp
    popl    %ebp
    retl
    .cfi_endproc
                                        ## -- End function
    .globl  _caller                 ## -- Begin function caller
    .p2align    4, 0x90
_caller:                                ## @caller
    .cfi_startproc
## %bb.0:
    pushl   %ebp
    .cfi_def_cfa_offset 8
    .cfi_offset %ebp, -8
    movl    %esp, %ebp
    .cfi_def_cfa_register %ebp
    subl    $24, %esp
    movl    $55, -4(%ebp)
    movl    $33, -8(%ebp)
    movl    -4(%ebp), %eax
    movl    -8(%ebp), %ecx
    movl    %eax, (%esp)
    movl    %ecx, 4(%esp)
    calll   _func
    movl    %eax, -12(%ebp)
    addl    $24, %esp
    popl    %ebp
    retl
    .cfi_endproc
                                        ## -- End function
    .globl  _main                   ## -- Begin function main
    .p2align    4, 0x90
_main:                                  ## @main
    .cfi_startproc
## %bb.0:
    pushl   %ebp
    .cfi_def_cfa_offset 8
    .cfi_offset %ebp, -8
    movl    %esp, %ebp
    .cfi_def_cfa_register %ebp
    subl    $8, %esp
    movl    $0, -4(%ebp)
    calll   _caller
    xorl    %eax, %eax
    addl    $8, %esp
    popl    %ebp
    retl
    .cfi_endproc
                                        ## -- End function

注意该代码中的形如d(%ebp)的表示方法，它是相对寻址，即以EBP为基地址，偏移量为d个字节的内存空间中的内容。另外，$d表示值为d的十进制立即数。看不太懂也没关系，下面直接给出发生函数调用时与栈相关的动作过程：

主调函数把被调函数需要的参数值（实参）从右至左入栈；
主调函数使用call指令正式调用被调函数，并把返回地址（即call指令的下一条指令的地址）入栈。返回地址入栈这一步是隐含的；
被调函数将主调函数的栈底地址(%ebp)入栈，并将该地址作为被调函数的栈顶地址(%esp)；
将被调函数中定义的局部变量按照定义的自然顺序（从左至右）入栈；
被调函数执行完毕后，将(%esp)上移，找到之前主调函数的栈底地址，并将它出栈。最后使用ret指令返回主调函数。

由此可见，每个栈帧都会存储上一栈帧的EBP内存储的基地址，并且它是作为分界线：向被调函数传入的参数位于该EBP的栈底方向（较高地址），而被调函数自己的局部变量位于该EBP的栈顶方向（较低地址），进退自如。下面画图示出函数调用栈的全貌，小单元格表示4字节的内存空间。

图5

由于每个函数的栈帧都维护有上一级主调函数的EBP地址，这就保证被调函数调用完毕后，通过上移ESP即可废弃当前栈帧，并且通过弹出主调函数的EBP地址就能恢复主调函数的现场。通过不断扩展栈帧结构，就形成了多级函数的调用栈。

为了有更直观的感受，我们在上述程序中再加几句。

#define MEM_ADDR(x) printf("&"#x" = %p\n", &x)

int func(int a, int b, int c) {
  int x = 99, y = 77, z;
  z = (a - b + c) * x / y;
  MEM_ADDR(a);
  MEM_ADDR(b);
  MEM_ADDR(c);
  MEM_ADDR(x);
  MEM_ADDR(y);
  MEM_ADDR(z);
  return z;
}

void caller(int p) {
  int m = 55, n = 33, k;
  k = func(m, n, p);
  MEM_ADDR(p);
  MEM_ADDR(m);
  MEM_ADDR(n);
  MEM_ADDR(k);
}

int main() {
  caller(11);
  return 0;
}

定义了一个MEM_ADDR宏，用来输出各个变量的地址。看官可以用32位的GCC编译运行一下，看看输出的地址是否符合函数调用栈结构的预期。

The End

弄懂函数调用栈之后，可以极大地方便我们理解递归（recursion）与递归的特例——尾递归（tail recursion）。不过本文已经很长了，关于递归的细节就另外写文章吧。

晚安。