7. 函数调用：为什么会发生stack overflow？
今天我们从程序的调用开始，讲讲「函数之间的相互调用」。在计算机指令层面是怎么实现的，以及什么情况下会出现「栈溢出」的报错。
为什么我们需要栈？
// 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);
}
$ gcc -g -c function_example.c
$ objdump -d -M intel -S function_example.o
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」函数，被编译后，首先是一条「push」指令和「mov」指令，在函数结束的时候，有一条「pop」指令和「ret」指令。这四条指令的执行就是压栈和出栈。
「函数调用」和「if...else」有些像，都是从原来顺序执行的指令过程里，执行了一个内存地址的「跳转指令」，让指令从原来顺序执行的过程里跳开，从跳转后新的位置开始执行。
但是两者又有区别，「if...else」是跳转后就不回来了，就在跳转后的新地址顺序执行指令。而「函数调用」是在对应函数的指令执行后，还会回到函数调用的位置，继续执行「call」指令后的指令。
那我们有没有一个可以不跳转回原来的地方，来实现「函数调用」呢？直觉上似乎有这么个办法，就是把调用函数的指令，直接插入到调用函数的地方，替换掉对应的「call」指令，然后编译器在编译的时候，直接把「函数调用」变成对应的指令替换掉。
不过，仔细琢磨一下，你会发现这个方法有些问题。如果函数 A 调用了函数 B，然后函数 B 再调用函数 A，我们就得面临在 A 里面插入 B 的指令，然后在 B 里面插入 A 的指令，这样就会产生无穷无尽地替换。
这个方法行不通，我们能不能把后面跳转回来执行的指令（call指令后的指令）地址记录下来？就像前面的「PC寄存器」一样，我们可以专门设立一个“程序调用寄存器”，来存储「要跳转回来执行的地址」。等函数调用结束后，从这个寄存器中取出地址，继续执行就好。
但是在多层函数中，简单的记录一个地址是不够的，比如「函数A」调用「函数B」，「函数B」调用「函数C」，这样一层层下去，在所有函数调用之前，每一次调用的「返回地址」都要记录下来，「寄存器」是不够用的。
最后想到的办法是，在内存中开辟一段空间，用栈这个先进后出的数据结构。
打个比方，「栈」相当于一个乒乓球桶，每次函数调用前，我们把「调用返回后的地址」写在一个乒乓球上，然后塞进这个乒乓球桶，这个操作就是「压栈」。如果函数执行完了，我们就从乒乓球桶中取出最上面的兵乓球，也就是「出栈」。
拿到出栈的兵乓球，上面写着地址，然后程序就跳转到该地址，就到了函数调用后下一条指令。如果函数A结束前，又调用了函数B，那么在取出乒乓球A前，又塞入了乒乓球B，而我们从乒乓球桶中取出的乒乓球，一定是最近的。乒乓球桶的底部，就是栈底，最上面的乒乓球所在的位置，就是栈顶。
在真实的程序中，压栈的不仅仅有「函数调用后返回的地址」。比如A调用B的时候，需要传入一些参数数据，在寄存器不够用的时候，这些参数也会被压入栈中。整个函数A所占的内存空间，就是A的栈帧。
并且，实际的程序中，底和顶跟我们刚刚讲的乒乓球桶是颠倒的，底在最上面，顶在最下面，这样的布局是因为「栈底的内存地址是在一开始就固定的」。而一层层压栈之后，栈顶的内存地址是在逐渐变小而不是变大。
我们看下上述对应的汇编代码，main函数调用add函数的时候，add函数的入口在0-1行，add函数结束在12-13行。我们在调用34行的「call」指令时，会把当前「PC寄存器」里的下一条指令（也就是第39行指令）的地址「压栈」，保留函数调用结束后要执行的指令地址。而add函数的第0行，「push rbp」这个指令就是在进行「压栈」。这里的rbp又叫「栈帧指针」，是一个存放了当前栈帧位置的「寄存器」（rbp此时指向的是「main函数栈帧」的栈底地址）。「push rbp」就是把之前调用函数，也就是 main 函数的栈帧的栈底地址，压到栈顶。 接着第1行指令「mov rbp, rsp」，就是把「rsp」里面的地址复制到「rbp」里，「rsp」始终指向栈顶，这个命令意味着，rbp 这个栈帧指针指向的地址，变成当前最新的栈顶，也就是 add 函数的栈帧的栈底地址了。
而在函数 add 执行完成之后，又会分别调用第 12 行的 「pop rbp」 来将当前的栈顶出栈，这部分操作维护好了我们整个栈帧。然后，我们可以调用第 13 行的 ret 指令，这时候同时要把 call 调用的时候压入的 「PC 寄存器」里的下一条指令（第39行指令）出栈，更新到 「PC 寄存器」中，将程序的控制权返回到出栈后的栈顶（main函数）。
如何利用函数内联进行性能优化？
上面我们提到一个方法，把一个实际调用的函数产生的指令，直接插入到的位置，来替换对应的函数的「函数调用指令」。尽管这个方法之前否决了，但是如果被调用的函数里，没有调用「其他函数」，这个方法是可以的。
事实上，这就是一个常见的编译器进行自动优化的场景，我们通常叫函数内联（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)
}
$ 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
内联带来的优化是，CPU 需要执行的指令数变少了，根据地址跳转的过程不需要了，压栈和出栈的过程也不用了。
不过内联也是有代价的，意味着，我们把「可以复用的程序指令」在调用它的地方完全展开了，如果一个函数在多个地方被调用，那么就会展开多次，整个程序占用的空间就更大了。
上图中，没有调用其他函数，只是被调用的函数，也叫做叶子函数。
如果你想一起学习这门课，可以扫下面的二维码购买：
