极客时间已完结课程限时免费阅读

07 | 函数调用：为什么会发生stack overflow？

07 | 函数调用：为什么会发生stack overflow？-极客时间

07 | 函数调用：为什么会发生stack overflow？

2019-05-10 徐文浩 来自北京
《深入浅出计算机组成原理》
课程介绍

讲述：徐文浩

时长12:08大小11.08M

在开发软件的过程中我们经常会遇到错误，如果你用 Google 搜过出错信息，那你多少应该都访问过Stack Overflow这个网站。作为全球最大的程序员问答网站，Stack Overflow 的名字来自于一个常见的报错，就是栈溢出（stack overflow）。
今天，我们就从程序的函数调用开始，讲讲函数间的相互调用，在计算机指令层面是怎么实现的，以及什么情况下会发生栈溢出这个错误。

为什么我们需要程序栈？

和前面几讲一样，我们还是从一个非常简单的 C 程序 function_example.c 看起。
// function_example.c
#include <stdio.h>
int static add(int a, int b)
{
return a+b;
}
int main()
{
int x = 5;
int y = 10;
int u = add(x, y);
}
这个程序定义了一个简单的函数 add，接受两个参数 a 和 b，返回值就是 a+b。而 main 函数里则定义了两个变量 x 和 y，然后通过调用这个 add 函数，来计算 u=x+y，最后把 u 的数值打印出来。
$ gcc -g -c function_example.c
$ objdump -d -M intel -S function_example.o
我们把这个程序编译之后，objdump 出来。我们来看一看对应的汇编代码。
int static add(int a, int b)
{
0: 55 push rbp
1: 48 89 e5 mov rbp,rsp
4: 89 7d fc mov DWORD PTR [rbp-0x4],edi
7: 89 75 f8 mov DWORD PTR [rbp-0x8],esi
return a+b;
a: 8b 55 fc mov edx,DWORD PTR [rbp-0x4]
d: 8b 45 f8 mov eax,DWORD PTR [rbp-0x8]
10: 01 d0 add eax,edx
}
12: 5d pop rbp
13: c3 ret
0000000000000014 <main>:
int main()
{
14: 55 push rbp
15: 48 89 e5 mov rbp,rsp
18: 48 83 ec 10 sub rsp,0x10
int x = 5;
1c: c7 45 fc 05 00 00 00 mov DWORD PTR [rbp-0x4],0x5
int y = 10;
23: c7 45 f8 0a 00 00 00 mov DWORD PTR [rbp-0x8],0xa
int u = add(x, y);
2a: 8b 55 f8 mov edx,DWORD PTR [rbp-0x8]
2d: 8b 45 fc mov eax,DWORD PTR [rbp-0x4]
30: 89 d6 mov esi,edx
32: 89 c7 mov edi,eax
34: e8 c7 ff ff ff call 0 <add>
39: 89 45 f4 mov DWORD PTR [rbp-0xc],eax
3c: b8 00 00 00 00 mov eax,0x0
}
41: c9 leave
42: c3 ret
可以看出来，在这段代码里，main 函数和上一节我们讲的的程序执行区别并不大，它主要是把 jump 指令换成了函数调用的 call 指令。call 指令后面跟着的，仍然是跳转后的程序地址。
这些你理解起来应该不成问题。我们下面来看一个有意思的部分。
我们来看 add 函数。可以看到，add 函数编译之后，代码先执行了一条 push 指令和一条 mov 指令；在函数执行结束的时候，又执行了一条 pop 和一条 ret 指令。这四条指令的执行，其实就是在进行我们接下来要讲压栈（Push）和出栈（Pop）操作。
你有没有发现，函数调用和上一节我们讲的 if…else 和 for/while 循环有点像。它们两个都是在原来顺序执行的指令过程里，执行了一个内存地址的跳转指令，让指令从原来顺序执行的过程里跳开，从新的跳转后的位置开始执行。
但是，这两个跳转有个区别，if…else 和 for/while 的跳转，是跳转走了就不再回来了，就在跳转后的新地址开始顺序地执行指令，就好像徐志摩在《再别康桥》里面写的：“我挥一挥衣袖，不带走一片云彩”，继续进行新的生活了。而函数调用的跳转，在对应函数的指令执行完了之后，还要再回到函数调用的地方，继续执行 call 之后的指令，就好像贺知章在《回乡偶书》里面写的那样：“少小离家老大回，乡音未改鬓毛衰”，不管走多远，最终还是要回来。
那我们有没有一个可以不跳转回到原来开始的地方，来实现函数的调用呢？直觉上似乎有这么一个解决办法。你可以把调用的函数指令，直接插入在调用函数的地方，替换掉对应的 call 指令，然后在编译器编译代码的时候，直接就把函数调用变成对应的指令替换掉。
不过，仔细琢磨一下，你会发现这个方法有些问题。如果函数 A 调用了函数 B，然后函数 B 再调用函数 A，我们就得面临在 A 里面插入 B 的指令，然后在 B 里面插入 A 的指令，这样就会产生无穷无尽地替换。就好像两面镜子面对面放在一块儿，任何一面镜子里面都会看到无穷多面镜子。
Infinite Mirror Effect，如果函数 A 调用 B，B 再调用 A，那么代码会无限展开，图片来源
看来，把被调用函数的指令直接插入在调用处的方法行不通。那我们就换一个思路，能不能把后面要跳回来执行的指令地址给记录下来呢？就像前面讲 PC 寄存器一样，我们可以专门设立一个“程序调用寄存器”，来存储接下来要跳转回来执行的指令地址。等到函数调用结束，从这个寄存器里取出地址，再跳转到这个记录的地址，继续执行就好了。
但是在多层函数调用里，简单只记录一个地址也是不够的。我们在调用函数 A 之后，A 还可以调用函数 B，B 还能调用函数 C。这一层又一层的调用并没有数量上的限制。在所有函数调用返回之前，每一次调用的返回地址都要记录下来，但是我们 CPU 里的寄存器数量并不多。像我们一般使用的 Intel i7 CPU 只有 16 个 64 位寄存器，调用的层数一多就存不下了。
最终，计算机科学家们想到了一个比单独记录跳转回来的地址更完善的办法。我们在内存里面开辟一段空间，用栈这个后进先出（LIFO，Last In First Out）的数据结构。栈就像一个乒乓球桶，每次程序调用函数之前，我们都把调用返回后的地址写在一个乒乓球上，然后塞进这个球桶。这个操作其实就是我们常说的压栈。如果函数执行完了，我们就从球桶里取出最上面的那个乒乓球，很显然，这就是出栈。
拿到出栈的乒乓球，找到上面的地址，把程序跳转过去，就返回到了函数调用后的下一条指令了。如果函数 A 在执行完成之前又调用了函数 B，那么在取出乒乓球之前，我们需要往球桶里塞一个乒乓球。而我们从球桶最上面拿乒乓球的时候，拿的也一定是最近一次的，也就是最下面一层的函数调用完成后的地址。乒乓球桶的底部，就是栈底，最上面的乒乓球所在的位置，就是栈顶。
在真实的程序里，压栈的不只有函数调用完成后的返回地址。比如函数 A 在调用 B 的时候，需要传输一些参数数据，这些参数数据在寄存器不够用的时候也会被压入栈中。整个函数 A 所占用的所有内存空间，就是函数 A 的栈帧（Stack Frame）。Frame 在中文里也有“相框”的意思，所以，每次到这里，我都有种感觉，整个函数 A 所需要的内存空间就像是被这么一个“相框”给框了起来，放在了栈里面。
而实际的程序栈布局，顶和底与我们的乒乓球桶相比是倒过来的。底在最上面，顶在最下面，这样的布局是因为栈底的内存地址是在一开始就固定的。而一层层压栈之后，栈顶的内存地址是在逐渐变小而不是变大。
图中，rbp 是 register base pointer 栈基址寄存器（栈帧指针），指向当前栈帧的栈底地址。rsp 是 register stack pointer 栈顶寄存器（栈指针），指向栈顶元素。
对应上面函数 add 的汇编代码，我们来仔细看看，main 函数调用 add 函数时，add 函数入口在 0～1 行，add 函数结束之后在 12～13 行。
我们在调用第 34 行的 call 指令时，会把当前的 PC 寄存器里的下一条指令的地址压栈，保留函数调用结束后要执行的指令地址。而 add 函数的第 0 行，push rbp 这个指令，就是在进行压栈。这里的 rbp 又叫栈帧指针（Frame Pointer），是一个存放了当前栈帧位置的寄存器。push rbp 就把之前调用函数，也就是 main 函数的栈帧的栈底地址，压到栈顶。
接着，第 1 行的一条命令 mov rbp, rsp 里，则是把 rsp 这个栈指针（Stack Pointer）的值复制到 rbp 里，而 rsp 始终会指向栈顶。这个命令意味着，rbp 这个栈帧指针指向的地址，变成当前最新的栈顶，也就是 add 函数的栈帧的栈底地址了。
而在函数 add 执行完成之后，又会分别调用第 12 行的 pop rbp 来将当前的栈顶出栈，这部分操作维护好了我们整个栈帧。然后，我们可以调用第 13 行的 ret 指令，这时候同时要把 call 调用的时候压入的 PC 寄存器里的下一条指令出栈，更新到 PC 寄存器中，将程序的控制权返回到出栈后的栈顶。

如何构造一个 stack overflow？

通过引入栈，我们可以看到，无论有多少层的函数调用，或者在函数 A 里调用函数 B，再在函数 B 里调用 A，这样的递归调用，我们都只需要通过维持 rbp 和 rsp，这两个维护栈顶所在地址的寄存器，就能管理好不同函数之间的跳转。不过，栈的大小也是有限的。如果函数调用层数太多，我们往栈里压入它存不下的内容，程序在执行的过程中就会遇到栈溢出的错误，这就是大名鼎鼎的“stack overflow”。
要构造一个栈溢出的错误并不困难，最简单的办法，就是我们上面说的 Infiinite Mirror Effect 的方式，让函数 A 调用自己，并且不设任何终止条件。这样一个无限递归的程序，在不断地压栈过程中，将整个栈空间填满，并最终遇上 stack overflow。
int a()
{
return a();
}
int main()
{
a();
return 0;
}
除了无限递归，递归层数过深，在栈空间里面创建非常占内存的变量（比如一个巨大的数组），这些情况都很可能给你带来 stack overflow。相信你理解了栈在程序运行的过程里面是怎么回事，未来在遇到 stackoverflow 这个错误的时候，不会完全没有方向了。

如何利用函数内联进行性能优化？

上面我们提到一个方法，把一个实际调用的函数产生的指令，直接插入到的位置，来替换对应的函数调用指令。尽管这个通用的函数调用方案，被我们否决了，但是如果被调用的函数里，没有调用其他函数，这个方法还是可以行得通的。
事实上，这就是一个常见的编译器进行自动优化的场景，我们通常叫函数内联（Inline）。我们只要在 GCC 编译的时候，加上对应的一个让编译器自动优化的参数 -O，编译器就会在可行的情况下，进行这样的指令替换。
我们来看一段代码。
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
int static add(int a, int b)
{
return a+b;
}
int main()
{
srand(time(NULL));
int x = rand() % 5
int y = rand() % 10;
int u = add(x, y)
printf("u = %d\n", u)
}
为了避免编译器优化掉太多代码，我小小修改了一下 function_example.c，让参数 x 和 y 都变成了，通过随机数生成，并在代码的最后加上将 u 通过 printf 打印出来的语句。
$ gcc -g -c -O function_example_inline.c
$ objdump -d -M intel -S function_example_inline.o
上面的 function_example_inline.c 的编译出来的汇编代码，没有把 add 函数单独编译成一段指令顺序，而是在调用 u = add(x, y) 的时候，直接替换成了一个 add 指令。
return a+b;
4c: 01 de add esi,ebx
除了依靠编译器的自动优化，你还可以在定义函数的地方，加上 inline 的关键字，来提示编译器对函数进行内联。
内联带来的优化是，CPU 需要执行的指令数变少了，根据地址跳转的过程不需要了，压栈和出栈的过程也不用了。
不过内联并不是没有代价，内联意味着，我们把可以复用的程序指令在调用它的地方完全展开了。如果一个函数在很多地方都被调用了，那么就会展开很多次，整个程序占用的空间就会变大了。
这样没有调用其他函数，只会被调用的函数，我们一般称之为叶子函数（或叶子过程）。

总结延伸

这一节，我们讲了一个程序的函数间调用，在 CPU 指令层面是怎么执行的。其中一定需要你牢记的，就是程序栈这个新概念。
我们可以方便地通过压栈和出栈操作，使得程序在不同的函数调用过程中进行转移。而函数内联和栈溢出，一个是我们常常可以选择的优化方案，另一个则是我们会常遇到的程序 Bug。
通过加入了程序栈，我们相当于在指令跳转的过程种，加入了一个“记忆”的功能，能在跳转去运行新的指令之后，再回到跳出去的位置，能够实现更加丰富和灵活的指令执行流程。这个也为我们在程序开发的过程中，提供了“函数”这样一个抽象，使得我们在软件开发的过程中，可以复用代码和指令，而不是只能简单粗暴地复制、粘贴代码和指令。

推荐阅读

如果你觉得还不过瘾，可以仔细读一下《深入理解计算机系统（第三版）》的 3.7 小节《过程》，进一步了解函数调用是怎么回事。
另外，我推荐你花一点时间，通过搜索引擎搞清楚 function_example.c 每一行汇编代码的含义，这个能够帮你进一步深入了解程序栈、栈帧、寄存器以及 Intel CPU 的指令集。

课后思考

在程序栈里面，除了我们跳转前的指令地址外，还需要保留哪些信息，才能在我们在函数调用完成之后，跳转回到指令地址的时候，继续执行完函数调用之后的指令呢？
你可以想一想，查一查，然后在留言区留下你的思考和答案，也欢迎你把今天的内容分享给你的朋友，和他一起思考和进步。
分享给需要的人，Ta购买本课程，你将得20元
生成海报并分享

赞 100

提建议

© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
上一篇
06 | 指令跳转：原来if...else就是goto
下一篇
08 | ELF和静态链接：为什么程序无法同时在Linux和Windows下运行？
unpreview
 写留言

精选留言(135)

  • CGer_AJ
    2019-05-10
    这个很好 讲的很细 这两章我要反复看 并手动实践 感觉作者 把这个课讲的生动形象~这个绝对是最值的课程
    共 2 条评论
    80
  • kdb_reboot
    2019-05-10
    倒数第二图比较好 补充一下寄存器说明 rbp - register base pointer (start of stack) rsp - register stack pointer (current location in stack, growing downwards) 建议将图编号这样评论的时候也能有所指代

    作者回复: kdb_reboot，谢谢建议。这个建议不错，我麻烦编辑稍后加上。

    共 7 条评论
    56
  • chengzise
    2019-05-10
    老师这里需要补冲一下，函数调用call指令时，（PC）指令地址寄存器会自动压栈，即返回地址压栈，函数返回ret指令时会自动弹栈，即返回地址赋值给PC寄存器，把之前。图片有显示压栈，没有文字说明，其他同学可以不太理解。

    作者回复: 👍，谢谢 chengzise 同学，谢谢补充。call 在调用的时候会做push eip的操作，而在ret的时候会做pop eip的操作。

    共 2 条评论
    44
  • Geek_dark
    2020-05-14
    https://manybutfinite.com/post/journey-to-the-stack/ 这篇文章将汇编指令操作栈的步骤一步步画出来了，大家可以看看，浅显易懂。
    共 5 条评论
    41
  • 杰杰
    2020-06-23
    查了一下，个人理解。 call 就相当于 push rip 和 jmp 的结合。rip 是指令地址寄存器，也就是会将返回地址入栈，并跳转到相应函数处执行。而 ret 就相当于 pop rip 和 jmp 的结合。 rbp 和 rsp 用于维护当前栈帧，rbp 指向栈帧的栈底地址，rsp 指向栈顶地址。 push rbp 和 mov rbp, rsp 主要是为了从 main 函数栈帧调整为 add 函数栈帧。 push rbp 是将之前 main 函数栈帧的栈底地址入栈，之后的 pop rbp 就可以将该栈底地址出栈，从而又调整为 main 函数栈帧。 rsp 指向 main 函数栈帧的栈顶地址，也就是当前 add 函数栈帧的栈底地址。mov rbp, rsp 就是把 rbp 从 main 函数栈帧的栈底地址 调整为 add 函数栈帧的栈底地址。 在 push 时 rsp 会减小，在 pop 时 rsp 会增大，从而 rsp 始终指向栈顶位置。
    展开
    共 3 条评论
    29
  • 秋天
    2019-05-27
    现在有点模糊的是栈只是用来做函数调用，记录跳转地址的？它和寄存器的本质区别吗？这两者能给解释一下吗？谢谢！

    作者回复: 秋天同学你好， 我们在这里先要分清楚 抽象概念 和 实际的硬件实现部分。 寄存器 和 内存，是在硬件层面就是放在不同的位置，使用不同的物理硬件来实现的。 而栈是一个抽象概念，实际是存放在内存里面的。栈是用来管理函数调用的“现场”的。确保函数调用完成后，还能回到调用者那里。

    27
  • 董某人
    2019-05-15
    老师，既然push rbp 的作用是把"main 函数栈帧的栈底地址，压到栈顶"，那下一句mov rbp,rsp 又是把"栈顶地址复制给栈帧"。 原本rbp 中存储的不就是main 函数栈帧地址，压到栈顶后rsp 中存储的不也是main 函数栈帧地址，mov 这句的作用究竟是什么呢？
    共 6 条评论
    26
  • JStFs
    2019-06-20
    “push rbp 就把之前调用函数，也就是 main 函数的栈帧的栈底地址，压到栈顶。” 一直不明白为什么要把main的栈底压到栈顶？没有图很难理解
    共 13 条评论
    21
  • Better me
    2019-05-10
    push rbp； mov rbp rsp； 老师，想问这两句是如何控制函数调用的

    作者回复: 这两个是在维护函数调用的栈帧。 指令地址本身的压栈和出栈是在 call 和 ret 的部分进行的。 你可以认为 call 的同时进行了一次 push rip 把PC寄存器里面的内容压栈了，而在 ret 的时候 pop 把这部分数据出栈写回到PC寄存器里面了。

    共 5 条评论
    19
  • 蚂蚁内推+v
    2019-06-06
    老师 巨大数组为什么是分配在栈空间的呢？（java里面是分配到堆上的 c预约和java不同吗）

    作者回复: 如果是函数作用域内的临时变量，就是分配在栈上的啊。 首先Java运行时候的JVM自己就是一个应用程序，和C编译出来的机器码就不一样。 Java通过New出来的对象是在堆上，但是函数作用域里面的临时变量，以及对应的引用都是放在栈上的。

    共 2 条评论
    17
  • Allen
    2019-05-16
    int main() { d: 55 push ebp e: 89 e5 mov ebp,esp 10: 83 ec 18 sub esp,0x18 int x = 5; 13: c7 45 f4 05 00 00 00 mov DWORD PTR [ebp-0xc],0x5 int y = 10; 1a: c7 45 f8 0a 00 00 00 mov DWORD PTR [ebp-0x8],0xa 老师，请教下： sub esp,0x18 的目的是干什么？ 0x18 是怎么计算的？
    展开

    作者回复: 这个是在维护栈帧，因为后面有两个临时变量需要在调用其他函数之前保留到栈里面。0x18是16进制的24 两个int各需要8 bit,一共16bit，然后ebp本来就要8bit，一共只有24bit,考虑对齐到16bit的整数倍还要额外的8bit一共24bit

    共 2 条评论
    15
  • DreamItPossible
    2019-07-30
    首先，以函数P调用函数Q为例进行说明： 程序栈里需要保存的信息有： - 函数P调用函数Q完成后的下一个指令的地址，即返回地址； - 如果函数Q的参数个数超过6个，则剩余的参数值需要保存在栈上； - 某些共用的寄存器值； - 为指针类型参数生成的地址信息； - 数组和结构体等复杂数据结构； 其次，需要保存的信息其实可以反过来解答文章开头的问题：为什么需要程序栈？ 最后，总结一下：资源有限，即寄存器个数有限，需要结合栈来实现复杂的功能，比如函数调用等
    展开
    13
  • once
    2019-08-28
    老师 call指令已经将pc寄存器里的下一个指令（add函数执行完的跳转地址）压栈了 那 add函数里面的 push rbp压的又是什么栈 还有把main函数从栈底压到栈顶这个是什么意思 没有图看了好几遍也懵懵的 help老师

    作者回复: 这两个是在维护函数调用的栈帧。 指令地址本身的压栈和出栈是在 call 和 ret 的部分进行的。 你可以认为 call 的同时进行了一次 push rip 把PC寄存器里面的内容压栈了，而在 ret 的时候 pop 把这部分数据出栈写回到PC寄存器里面了。 这一部分的确是有不少同学表示写得不够清楚，我晚点看单独会在FAQ里面更详细地写一下这个过程。也再修订一下这一讲希望能讲解地更清楚一些。

    共 4 条评论
    12
  • 小猪
    2019-05-22
    老师，我觉得用goto就可以实现函数调用，起先跳转到函数，运行完，在用goto跳回来就行了

    作者回复: 小猪同学你好， 那么被调用的函数运行完之后，怎么知道要跳回到哪一个地址呢？

    共 7 条评论
    9
  • Akizuki
    2019-05-12
    function_example.c 反汇编结果： int u = add(x, y); 2a: 8b 55 f8 mov edx, DWORD PTR [rbp-0x8] 2d: 8b 45 fc mov eax, DWORD PTR [rbp-0x4] 30: 89 d6 mov esi, edx 32: 89 c7 mov edi, eax 老师，这里为什么没有编译成： mov esi, DWORD PTR [rbp-0x8] mov edi, DWORD PTR [rbp-0x4] 谢谢～
    展开
    共 1 条评论
    9
  • 秋天
    2019-05-27
    java程序应该不是那种分页的形式，在虚机起动的时候我们根据配置或者是起动参数指定需要的内存大小，应该是预先分配好一大段连续的内存供程序使用，所以在程序运行过程中如果超出啦，预分配大小的内存就会出现内存溢出的错误

    作者回复: java虚拟机其实是一个应用层的程序，java虚拟机的内部内存分配其实是在虚拟内存地址层面的分配。的确不涉及到操作系统和硬件层面的分页问题。

    8
  • Alphalin
    2019-05-15
    请问地址34后面的地址怎么直接到39了？ 35地址在哪呢

    作者回复: 34的整个指令有长度啊，你数一数这条指令对应的机器码需要多少空间呢？

    共 2 条评论
    7
  • 曾立涵
    2020-02-17
    大家可以结合这篇文章看一下，带图的好理解一些https://blog.csdn.net/fistraiser/article/details/80270473
    6
  • tlseek
    2019-11-03
    说一下个人理解，函数调用的栈是以栈帧单位，调用一个函数就会出现一个栈帧。但汇编指令的push和pop的操作对象并不是栈帧，而是rsp(栈顶指针)。要记住任何对栈操作的指令都会使rsp移动。 push rbp是指将rbp的内容（前一个函数的栈基地址）压入栈中，rsp向前移一位。 此时rsp指向的当前函数调用的栈基地址，而栈基地址所存放的内容是前一个函数调用的栈基地址。 mov rbp, rsp 是将当前函数调用栈基地址设置到rbp中，便于当前函数后续的指令使用。 pop rbp 指将rbp所指向的内存的内容（前一个函数栈基地址）移出栈（rsp向后移一位），并将此内容存入rbp中。这时rbp就指向前一个函数的栈基了。
    展开
    5
  • 楼外楼
    2019-07-15
    ESP/RSP：栈指针寄存器(extended stack pointer)，其内存放着一个指针，该指针永远指向系统栈最上面一个栈帧的栈顶。（64位机器变为RSP） EBP/RBP：基址指针寄存器(extended base pointer)，其内存放着一个指针，该指针永远指向系统栈最上面一个栈帧的底部。（64位机器变为RBP）
    5