【计算机内功修炼】八：函数运行时在内存中是什么样子？
在开始本篇的内容前，我们先来思考几个问题。
我们先来看一段简单的代码：
void func(int a) { if (a > 100000000) return; int arr[100] = {0}; func(a + 1);}
你能看出这段代码会有什么问题吗？
我们在之前的文章《高性能高并发服务器是如何实现的》一中提到了一项关键技术——协程，你知道协程的本质是什么吗？有的同学可能会说是用户线程，那么什么是用户态线程，这是怎么实现的？
函数运行起来后是什么样子？
这个问题看似没什么关联，但这背后有一样东西你需要理解，这就是所谓的函数运行时栈，run time stack。
接下来我们就好好看看到底什么是函数运行时栈，为什么彻底理解函数运行时栈对程序员来说非常重要。
从进程、线程到函数调用
汽车在高速上行驶时有很多信息，像速度、位置等等，通过这些信息我们可以直观的感受汽车的运行时状态。
pexels-mike-945443
同样的，程序在运行时也有很多信息，像有哪些程序正在运行、这些程序执行到了哪里等等，通过这些信息我们可以直观的感受系统中程序运行的状态。
其中，我们创造了进程、线程这样的概念来记录有哪些程序正在运行，关于进程和线程的概念请参见《看完这篇还不懂进程和线程你来打我》。
进程和线程的运行体现在函数执行上，函数的执行除了函数内部执行的顺序执行还有子函数调用的控制转移以及子函数执行完毕的返回。其中函数内部的顺序执行乏善可陈，重点是函数的调用。
因此接下来我们的视角将从宏观的进程和线程拉近到微观下的函数调用，重点来讨论一下函数调用是怎样实现的。
函数调用的活动轨迹：栈
玩过游戏的同学应该知道，有时你为了完成一项主线任务不得不去打一些支线的任务，支线任务中可能还有支线任务，当一个支线任务完成后退回到前一个支线任务，这是什么意思呢，举个例子你就明白了。
假设主线任务西天取经 A 依赖支线任务收服孙悟空 B 和收服猪八戒 C，也就是说收服孙悟空 B 和收服猪八戒 C 完成后才能继续主线任务西天取经 A；
支线任务收服孙悟空 B 依赖任务拿到紧箍咒 D，只有当任务 D 完成后才能回到任务 B；
整个任务的依赖关系如图所示：
1603672619352
现在我们来模拟一下任务完成过程。
首先我们来到任务 A，执行主线任务：
1603672811135
执行任务 A 的过程中我们发现任务 A 依赖任务 B，这时我们暂停任务 A 去执行任务 B：
1603673078596
执行任务 B 的时候，我们又发现依赖任务 D：
1603673983874
执行任务 D 的时候我们发现该任务不再依赖任何其它任务，因此 C 完成后我们可以会退到前一个任务，也就是 B：
1603673078596
任务 B 除了依赖任务 C 外不再依赖其它任务，这样任务 B 完成后就可以回到任务 A：
1603672811135
现在我们回到了主线任务 A，依赖的任务 B 执行完成，接下来是任务 C：
1603673950126
和任务 D 一样，C 不依赖任何其它其它任务，任务 C 完成后就可以再次回到任务 A，再之后任务 A 执行完毕，整个任务执行完成。
让我们来看一下整个任务的活动轨迹：
1603674440674
仔细观察，实际上你会发现这是一个 First In Last Out 的顺序，天然适用于栈这种数据结构来处理。
再仔细看一下栈顶的轨迹，也就是 A、B、D、B、A、C、A，实际上你会发现这里的轨迹就是任务依赖树的遍历过程，是不是很神奇，这也是为什么树这种数据结构的遍历除了可以用递归也可以用栈来实现的原因。
A box
函数调用也是同样的道理，你把上面的 ABCD 换成函数 ABCD，本质不变。
因此，现在我们知道了，使用栈这种结构就可以用来保存函数调用信息。
和游戏中的每个任务一样，当函数在运行时每个函数也要有自己的一个“小盒子”，这个小盒子中保存了函数运行时的各种信息，这些小盒子通过栈这种结构组织起来，这个小盒子就被称为栈帧，stack frames，也有的称之为 call stack，不管什么命名方式，总之，就是这里所说的小盒子，这个小盒子就是函数运行起来后占用的内存，这些小盒子构成了我们通常所说的栈区。关于栈区详细的讲解你可以参考《深入理解操作系统：程序员应如何理解内存》一文。
那么函数调用时都有哪些信息呢？
函数调用与返回信息
我们知道当函数 A 调用函数 B 的时候，控制从 A 转移到了 B，所谓控制其实就是指 CPU 执行属于哪个函数的机器指令，CPU 从开始执行属于函数 A 的指令切换到执行属于函数 B 的指令，我们就说控制从函数 A 转移到了函数 B。
控制从函数 A 转移到函数 B，那么我们需要有这样两个信息：
我从哪里来 (返回)
要到去哪里 (跳转)
是不是很简单，就好比你出去旅游，你需要知道去哪里，还需要记住回家的路。
函数调用也是同样的道理。
当函数 A 调用函数 B 时，我们只要知道：
函数 A 对于的机器指令执行到了哪里 (我从哪里来，返回)
函数 B 第一条机器指令所在的地址 (要到哪里去，跳转)
有这两条信息就足以让 CPU 开始执行函数 B 对应的机器指令，当函数 B 执行完毕后跳转回函数 A。
那么这些信息是怎么获取并保持的呢？
现在我们就可以打开这个小盒子，看看是怎么使用的了。
假设函数 A 调用函数 B，如图所示：
1603845345171
当前，CPU 执行函数 A 的机器指令，该指令的地址为 0x400564，接下来 CPU 将执行下一条机器指令也就是:
call 0x400540
这条机器指令是什么意思呢？
这条机器指令对应的就是我们在代码中所写的函数调用，注意 call 后有一条机器指令地址，注意观察上图你会看到，该地址就是函数 B 的第一条机器指令，从这条机器指令后 CPU 将跳转到函数 B。
现在我们已经解决了控制跳转的“要到哪里去”问题，当函数 B 执行完毕后怎么跳转回来呢？
原来，call 指令除了给出跳转地址之外还有这样一个作用，也就是把 call 指令的下一条指令的地址，也就是 0x40056a push 到函数 A 的栈帧中，如图所示：
1603845893680
现在，函数 A 的小盒子变大了一些，因为装入了返回地址：
1603846004468
现在 CPU 开始执行函数 B 对应的机器指令，注意观察，函数 B 也有一个属于自己的小盒子(栈帧)，可以往里面扔一些必要的信息。
1603846305325
如果函数 B 中又调用了其它函数呢？
道理和函数 A 调用函数 B 是一样的。
让我们来看一下函数 B 最后一条机器指令 ret，这条机器指令的作用是告诉 CPU 跳转到函数 A 保存在栈帧上的返回地址，这样当函数 B 执行完毕后就可以跳转到函数 A 继续执行了。
至此，我们解决了控制转移中“我从哪里来”的问题。
参数传递与返回值
函数调用与返回使得我们可以编写函数，进行函数调用。但调用函数除了提供函数名称之外还需要传递参数以及获取返回值，那么这又是怎样实现的呢？
在 x86-64 中，多数情况下参数的传递与获取返回值是通过寄存器来实现的。
假设函数 A 调用了函数 B，函数 A 将一些参数写入相应的寄存器，当 CPU 执行函数 B 时就可以从这些寄存器中获取参数了。
同样的，函数 B 也可以将返回值写入寄存器，当函数 B 执行结束后函数 A 从该寄存器中就可以读取到返回值了。
我们知道寄存器的数量是有限的，当传递的参数个数多于寄存器的数量该怎么办呢？
这时那个属于函数的小盒子也就是栈帧又能发挥作用了。
原来，当参数个数多于寄存器数量时剩下的参数直接放到栈帧中，这样被调函数就可以从前一个函数的栈帧中获取到参数了。
现在栈帧的样子又可以进一步丰富了，如图所示：
1603948689593
从图中我们可以看到，调用函数 B 时有部分参数放到了函数 A 的栈帧中，同时函数 A 栈帧的顶部依然保存的是返回地址。
局部变量
我们知道在函数内部定义的变量被称为局部变量，这些变量在函数运行时被放在了哪里呢？
原来，这些变量同样可以放在寄存器中，但是当局部变量的数量超过寄存器的时候这些变量就必须放到栈帧中了。
因此，我们的栈帧内容又一步丰富了。
1604018423586
细心的同学可能会有这样的疑问，我们知道寄存器是共享资源可以被所有函数使用，既然可以将函数 A 的局部变量写入寄存器，那么当函数 A 调用函数 B 时，函数 B 的局部变量也可以写到寄存器，这样的话当函数 B 执行完毕回到函数 A 时寄存器的值已经被函数 B 修改过了，这样会有问题吧。
这样的确会有问题，因此我们在向寄存器中写入局部变量之前，一定要先将寄存器中开始的值保存起来，当寄存器使用完毕后再恢复原值就可以了。
那么我们要将寄存器中的原始值保存在哪里呢？
有的同学可能已经猜到了，没错，依然是函数的栈帧中。
1604019378874
最终，我们的小盒子就变成了如图所示的样子，当寄存器使用完毕后根据栈帧中保存的初始值恢复其内容就可以了。
现在你应该知道函数在运行时到底是什么样子了吧，以上就是问题 3 的答案。
Big Picture
需要再次强调的一点就是，上述讨论的栈帧就位于我们常说的栈区。
栈区，属于进程地址空间的一部分，如图所示，我们将栈区放大就是图左边的样子。
1604020019183
关于栈区详细的讲解你可以参考《深入理解操作系统：程序员应如何理解内存》这篇。
最后，让我们回到文章开始的这段简单代码：
void func(int a) { if (a > 100000000) return; int arr[100] = {0}; func(a + 1);}void main(){ func(0);}
想一想这段代码会有什么问题？
总结
本章我们从几个看似没什么关联的问题出发，详细讲解了函数运行时栈是怎么一回事，为什么我们不能创建过多的局部变量。细心的同学会发现第 2 个问题我们没有解答，这个问题讲解放到下一篇，也就是协程中讲解。
希望这篇文章能对大家理解函数运行时栈有所帮助。
版权声明: 本文为 InfoQ 作者【码农的荒岛求生】的原创文章。
原文链接:【http://xie.infoq.cn/article/85162795fc23b998fbc3213f4】。文章转载请联系作者。
还未添加个人签名 2019.01.07 加入
公众号：码农的荒岛求生
评论