C/C++：堆栈面面观(一）

学习C语言，我们都听过堆（heap）和栈（stack）的概念。也是C/C++码农面试的常见考点，今天带大家来深入浅出一下。本文写于大四，写作初衷也是来自于曾经的面试经历、大学课程所学 以及各种网络资料，融合《CSAPP》的读书感悟总结而成。需要注意的是：有些地方“堆栈”这个词特指的是栈，而不是堆和栈。命名约定：本文中堆栈一次出现的地方，指的是两种东西，而非一种。

在数据结构中，我们也听过栈和堆这两种数据结构，当然和我本文要讲的东西是不同的概念。不过数据结构中的栈（算法、数学意义上的一种抽象），和本文中的栈（实际存在的存储区）有一共同之处就是FILO —— 先入后出。但是数据结构中的堆和我们本文中的堆则是毫不相干。

栈

无图言卵

注意，这里指的都是虚拟内存空间，并不是实际的物理内存布局。每一个进程都有自己的虚拟内存空间，也就是说我们程序中指针所表示的地址实际是虚拟地址，而不是物理地址。

增长方式

所谓地址增长方式，是指堆或栈在分配内存的时候，其分得的内存空间的地址的增长方式。堆的地址增长方式是从低到高的，而栈的地址增长方式是从高到低的。（在说这句话的时候，要明确的一点就是这是指的x86系统，并非所有架构的系统都如此）

之所以它们会呈现出相反的两种地址增长方式是有其历史原因的：

早期的机器上内存的大小十分有限，如果堆和栈使用相同的地址增长方式（比如，都是从低到高），假设，一段内存空间的起始位置（先忽略其他段）设置为堆的起始地址，那么栈的起始地址必然在这段内存空间的中间某处，这个起始点如果选择得太靠后，则可能导致栈的内存大小不够，太靠前则会导致堆在分配内存的时候，可能与栈地址冲突。这时x86系统的设计师们，巧妙地将栈的起始位置定于内存空间的另一端，而其地址增长方式也是和堆相反的从高到低，这样从一定程度上，减轻了堆栈内存地址冲突或栈空间不足的可能性。就好比两个小伙伴在同一本笔记本上记笔记，两个人分别从笔记本的首页和尾页开始写，其笔记冲突的概率大大减小。

函数栈

栈与函数有莫大的关系。简单说来，我们在函数中声明的任何局部变量（非静态）都是在栈中分配的（编译期间完成）。并且函数的参数，以及返回值也是依赖于栈。

为了深入地探讨这些概念，我们需要从汇编角度来展开研究。在使用gcc编译的时候，-S选项可以生成汇编代码。但此时生成的汇编代码是AT&T风格的，我们可以用-masm=intel生成intel风格的汇编。比如：gcc -S -masm=intel hello.c 这时就会生成汇编文件hello.s。请注意我们此时探讨的真相都是不开编译器优化选项的，因为如果开了编译器优化选项，那么其汇编行为往往已经完全不是我们代码本来的执行细节了。（编译器保证的是最终一致性，为了优化可能会改变我们的程序的细节）

变量

看一个简单的例子：

int main()
{
    int a;
    int b = 1;
    int c = 2;
}

其通过gcc -S -masm=intel汇编之后的汇编代码主要部分如下，注意不同版本的gcc编译器，不同位数的操作系统（32位或64位）其汇编代码可能不同，但大致的意思相同。

main:
.LFB0:
  .cfi_startproc
  push  rbp
  .cfi_def_cfa_offset 16
  .cfi_offset 6, -16
  mov  rbp, rsp
  .cfi_def_cfa_register 6
  mov  DWORD PTR [rbp-8], 1
  mov  DWORD PTR [rbp-4], 2
  pop  rbp
  .cfi_def_cfa 7, 8
  ret
  .cfi_endproc

可以忽略掉其中点号. 开头的语句。再看一遍：

main:
.LFB0:
  push  rbp
  mov  rbp, rsp
  mov  DWORD PTR [rbp-8], 1
  mov  DWORD PTR [rbp-4], 2
  pop  rbp
  ret

因为我是64位系统，所以汇编代码中的寄存器都是r打头的（rbp，rsp）64位寄存器。x86架构（通常是32位系统）是e打头的（ebp，esp）。以下涉及到寄存器时，我通常会省略其前缀，而直接用bp和sp来称呼。bp是基址寄存器，sp是栈顶指针寄存器（sp的位置，是我们实际能使用的栈的大小）。

请自行区分操作系统位数和cpu架构位数的区别。x64（x86-64），x86是CPU架构。如果你是x64的CPU装了32位系统，那么也不会使用到x64的寄存器（比如r8d），或者不能完整使用x64CPU的寄存器，比如rax。你只能使用该寄存器的一半：eax

首先将bp入栈（push rbp），然后将当前sp位置存取bp（mov rbp, rsp）。这两步是通用操作。下面是重点。

给变量分配空间，可以看到只有两个赋值语句，说明我们的int a因为没有初始化，所以实际不会被分配空间。

请注意下面（低地址）是栈顶。可以看到c在高地址，b在低地址。这与变量的初始化顺序相反。（如果你开优化选项-O来观察的话，你会发现汇编代码里什么都没有做，这是因为声明的变量b，c虽然被初始化了，但是后续并没有被调用，所以编译器在优化的时候，就什么都不做了。所以再次提醒请不要开编译器优化选项来研究本文的内容，本文不是讨论编译器优化原理的，因为举得例子过于简单，可能就被编译器优化抹掉了）

再验证一下，变量被分配的栈位置是否和变量初始化顺序相反：

int main()
{
    int a;
    int b = 1;
    int c = 2;
    a = 0;
}

其栈内存布局为：

如果是数组的初始化，则每个数组元素分配的栈地址，与其初始化顺序就没有关系了。下标越大的地址越高。比如：int a[4];.....。那么a[0]是数组中栈地址最低的元素，a[3]是地址最高的元素。这里我就不一一演示了，大家可以自己写个demo，汇编一下看看。。其实很好里面，数组的地址位置与其下标的关系一定要严格遵守，这样才方便随机访问（通过下标直接计算偏移）。要注意的是，a[0]在最低的地址。

参数

面试的时候你可能遇到过以下类型的题目：

int main()
{
    int a = 1;
    int b = 2;
    printf("%d,%d",a, a=a+b );
}

上面这段代码的输出结果是什么？结果是：3,3。出现这样的结果，一些编程书籍中可能会做出解释：因为函数参数的入栈顺序是从右到左的。这句话应该是对的，它揭露了一个事实，那就是函数参数是存入栈中的，如果参数是表达式，那么一定要先计算出表达式的值，然后再入栈。所以上面的printf中，会首先计算表达式a=a+b的值。此时a的值就变化了。这样解释应该是没有问题的，面试官也应该不会挑刺。其实真正的编译器行为没有这么简单。看下它的汇编代码：

.LC0:
  .string  "%d,%d"
  .text
  .globl  main
  .type  main, @function
main:
.LFB0:
  push  rbp
  mov  rbp, rsp
  sub  rsp, 16
  mov  DWORD PTR [rbp-8], 1   ；a = 1
  mov  DWORD PTR [rbp-4], 2   ；b = 2
  mov  eax, DWORD PTR [rbp-4] ；将b的值存入寄存器eax
        add  DWORD PTR [rbp-8], eax        ；执行a=a+b的操作，此时a的栈空间中存放3
  mov  edx, DWORD PTR [rbp-8] ;将a的值3存入寄存器edx
  mov  eax, DWORD PTR [rbp-8] ;将a的值3存入寄存器eax
  mov  esi, eax                               ；将eax的值3存入寄存器esi
  mov  edi, OFFSET FLAT:.LC0      ；将字符串"%d,%d"存入寄存器edi
  mov  eax, 0                                  ；eax清零。用于存放返回值
  call  printf
  leave

我删除一些不必要的信息，并且增加了注释。

可以看到，上面的代码中，函数参数并未使用到栈来传递参数，而是通过寄存器来传递参数。当然这并不能说用栈来传递参数的说法是错的，因为寄存器的数量是有限的。来看一个拥有7个参数的函数：

int add(int a, int b, int c, int d, int e, int f, int g)
{
    return a + b + c + d + e + f + g;
}

其汇编代码为：

add:
.LFB0:
  push  rbp
  mov  rbp, rsp
  mov  DWORD PTR [rbp-4], edi
  mov  DWORD PTR [rbp-8], esi
  mov  DWORD PTR [rbp-12], edx
  mov  DWORD PTR [rbp-16], ecx
  mov  DWORD PTR [rbp-20], r8d
  mov  DWORD PTR [rbp-24], r9d
  mov  edx, DWORD PTR [rbp-4]
  mov  eax, DWORD PTR [rbp-8]
  add  edx, eax
  mov  eax, DWORD PTR [rbp-12]
  add  edx, eax
  mov  eax, DWORD PTR [rbp-16]
  add  edx, eax
  mov  eax, DWORD PTR [rbp-20]
  add  edx, eax
  mov  eax, DWORD PTR [rbp-24]
  add  edx, eax
  mov  eax, DWORD PTR [rbp+16]
  add  eax, edx
  pop  rbp
  ret

可以看到函数从6个寄存器和1个栈地址中读取参数。曾几何时，以为面试官也曾经问我，函数的参数是通过什么传递的，我就说寄存器，寄存器不够了，就用栈。然后他接着问我几个寄存器不够了，就用栈了。我有点哑口无言。说了个四五个。其实这种问题是很开放的。通过上面的代码我们可以看到是6个寄存器。edi，esi，edx，ecx，r8d，r9d。然而，这只是我64位系统上的（r8d，r9d是X64上才有的），X86（32位）则不同（具体我没试）。那么是不是说，你和面试官说，“在64位系统中，使用的是6个寄存器来传递函数参数，参数多了，就使用栈来传递”。这样回答就完美了么？其实不是的。

刚才的示例代码中都规避了一些情景。上面我使用的函数的参数类型都是整型int。而如果参数类型是浮点型，指针等等其他类型就不能使用寄存器来传递函数参数了。具体这些问题探究起来就太多了，我在这里也只是抛砖引玉。大家可以自己去试试。推荐一篇文章《X86-64寄存器和栈帧》

说个题外话，上面我的代码如果开了优化会怎么样呢？用gcc -S -masm=intel -O 来编译一下看看。此时它的汇编代码为：

main:
.LFB25:
  sub  rsp, 8
  mov  edx, 28
  mov  esi, OFFSET FLAT:.LC0
  mov  edi, 1
  mov  eax, 0
  call  __printf_chk
  add  rsp, 8
  ret

哈哈。看到了吧，开了优化之后main函数里面连函数调用都没有。直接把28赋值给了寄存器edx，然后让printf来打印。28是啥？正是1 + 2 + 3 + 4 + 5 + 6 +7=28是也。所以我强调，尽量不要在开启优化选项的时候研究编译器行为，开了优化以后编译器保证的只是最终一致性，破坏力原有的程序逻辑。不具备通用性，不利于理解编程语言和编译器行为。当然大家也不要断章取义。其实我只是说在研究本文所探讨的问题的时候，不要开优化。如果正常的生产环境下，编译器优化可是很有用的。另外如果你研究的就是编译器的优化行为那么优化开关当然也要打开了。

sp和bp

前面已经解释过sp（栈顶指针寄存器）和bp（基址寄存器）。需要明确的是：

sp所指向的栈顶是我们所能分配的栈空间的极限，如果栈空间不够则需要移动sp指针，分配更多的栈空间。如前文所述，栈的地址增长方式是从高地址到低地址，所以sp指向的是我们能够使用的栈地址的最低出。

看一段C代码：

#include <stdio.h>
int add(int a, int b)
{
    int c = a + b;
    return c;
}
int main()
{
    int a = 2;
    int b = 3;
    int c = add(a, b);
    printf("%d\n", c);
}

其主要汇编代码为：

add:
.LFB0:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-20], edi
        mov     DWORD PTR [rbp-24], esi
        mov     eax, DWORD PTR [rbp-24]
        mov     edx, DWORD PTR [rbp-20]
        add     eax, edx
        mov     DWORD PTR [rbp-4], eax
        mov     eax, DWORD PTR [rbp-4]
        pop     rbp
        ret
.LFE0:
        .size   add, .-add
        .section        .rodata
.LC0:
        .string "%d\n"
        .text
        .globl  main
        .type   main, @function
main:
.LFB1:
        push    rbp
        mov     rbp, rsp
        sub     rsp, 16
        mov     DWORD PTR [rbp-4], 2
        mov     DWORD PTR [rbp-8], 3
        mov     edx, DWORD PTR [rbp-8]
        mov     eax, DWORD PTR [rbp-4]
        mov     esi, edx
        mov     edi, eax
        call    add
        mov     DWORD PTR [rbp-12], eax
        mov     eax, DWORD PTR [rbp-12]
        mov     esi, eax
        mov     edi, OFFSET FLAT:.LC0
        mov     eax, 0
        call    printf
        leave
        ret

可以看到在main函数开始部分有三步走：

先将原始bp入栈

然后将bp赋值给sp

最后进行了一个sp减16的操作。（栈顶向下移动16，即多分配16字节空间）

前两步是每个函数开始的必备操作，保存原始的栈位置（bp入栈，便于函数调用结束后恢复原函数的栈位置）。第三步不是必备操作，仅当函数中局部变量过多时会进行栈指针的移动来分配更多的空间，我们可以看到add函数的开始部分是没有这个操作的。

接着看一下add函数的结束部分。两步操作：

出栈，将保存在栈里的值（原始bp）恢复给bp（pop rbp）

结束当前函数，控制权转移给调用它的函数（ret）。

这两个是函数结束时的必备操作。关于函数的返回值主要是通过eax寄存器来返回。本文聚焦堆、栈，不再过多介绍寄存器的知识。

看一个trick现象：

#include <stdio.h>
void declare()
{
    int i;
    int a[100];
    for (i = 0;i < 100; i++)
    {
        a[i] = i;
    }
}
void print()
{
    int i;
    int a[100];
    for (i = 0;i < 100; i++)
    {
        printf("%d\n", a[i]);
    }
}
int main()
{
    declare();
    print();
}

用gcc编译一下，看看该程序的运行结果是什么，教科书告诉我们：在declare函数中声明的局部变量a[100]在函数结束后被销毁了，在print函数中去打印a[100]数组将输出不确定的值。

yes，这样理解完全没有问题。but，这个程序确确实实可以成功打印出0到99这100个数。why？

汇编代码我们就不看了。原理很简单，那就是：decalre函数返回之后确实它的栈空间被销毁了，其实所谓的销毁只不过是sp指针回到declare函数被调用前的原位，即main函数中sp位置，实际上declare函数给栈空间中赋的值却并不会被删除。当print函数被调用的时候，sp指针又继续向下移动，这时的循环输出语句会将之前储存在栈空间中的值进行打印。

通过这个例子，我只想说明关于栈自动销毁释放的真实情况，其实只是sp指针的移动而已。然而我们并不能依赖上述这种行为，比如：我们开了优化之后gcc -O去编译一下，其输出结果却是又是未定义的了。