深入理解计算机系统第 6 课 Machine Procedures

之前我们学习了机器是如何利用跳转实现流程控制的，这一讲我们来看一个更加复杂的机制：过程调用（也就是调用函数）具体在 CPU 和内存中是怎么实现了。理解之后，对于递归会有更加清晰的认识。

在过程调用中主要涉及三个重要的方面：

传递控制：包括如何开始执行过程代码，以及如何返回到开始的地方
传递数据：包括过程需要的参数以及过程的返回值
内存管理：如何在过程执行的时候分配内存，以及在返回之后释放内存

以上这三点，都是凭借机器指令实现的

Stack Structure

在 x86-64 中，所谓的栈，实际上一块内存区域，这个区域的数据进出满足先进后出的原则。越新入栈的数据，地址越低，所以栈顶的地址是最小的。下图中箭头所指的就是寄存器 %rsp 的值，这个寄存器是栈指针，用来记录栈顶的位置。

对于 push 操作，对应的是 pushq Src 指令，具体会完成下面三个步骤：

从地址 Src 中取出操作数
把 %rsp 中的地址减去 8（也就是到下一个位置）
把操作数写入到 %rsp 的新地址中

如下图所示：

对于 pop 操作，对应的是 popq Dest 指令，具体会完成下面三个步骤：

从 %rsp 中存储的地址中读入数据
把 %rsp 中的地址增加 8（回到上一个位置）
把刚才取出来的值放到 Dest 中（这里必须是一个寄存器）

如下图所示：

Calling Conventions

了解了栈的结构之后，我们先通过一个函数调用的例子，来感受一下（代码中有详细注释，请理解后再继续）：

可以看到，过程调用是利用栈来进行的，通过 call label 来进行调用（先把返回地址入栈，然后跳转到对应的 label），返回的地址，将是下一条指令的地址，通过 ret 来进行返回（把地址从栈中弹出，然后跳转到对应地址）

用上面的代码来做说明：

在执行到 400544 那一行的时候 %rsp 指向栈顶（存储着栈顶的地址），%rip 指向当前要执行的指令（也就是 400544）

在上一步操作完成之后，因为跳转的关系，%rip 指向 mult2 函数开始的地方（也就是 400550），之前的压栈操作也使得栈顶改变（返回值的位置），于是 %rsp 对应进行改变。

接着执行到了 retq 那句，这个时候要做的就是从栈中取出栈顶位置（这样就可以从跳转处继续了），然后对寄存器做对应的修改，最后得到下图：

具体的传值我们可以发现，是利用 %rax 来保存过程调用的返回值，以便程序继续运行的。这就是基本的过程调用的控制流程。

那么过程调用的参数会放在哪里呢？

如果参数没有超过六个，那么会放在：%rdi, %rsi, %rdx, %rcx, %r8, %r9 中。如果超过了，会另外放在一个栈中。而返回值会放在 %rax 中。

还是刚才的例子，看看数据的存放：

既然是利用栈来进行函数调用，自然而然就可以推广到递归的情况，而对于每个过程调用来说，都会在栈中分配一个帧 Frames。每一帧里需要包含：

返回信息
本地存储（如果需要）
临时空间（如果需要）

整一帧会在过程调用的时候进行空间分配，然后在返回时进行回收，如下图所示（箭头所指位栈顶）：

这里是一个调用的例子：

在 x86-64/Linux 中，栈帧的结构是固定的，当前的要执行的栈中包括：

Argument Build: 需要使用的参数
如果不能保存在寄存器中，会把一些本地变量放在这里
已保存的寄存器上下文
老的栈帧的指针（可选）

而调用者的栈帧则包括：

返回地址（因为 call 指令被压入栈的）
调用所需的参数

具体如下图所示：

下面用一个程序来说明一下，就比较清晰了：

在函数调用前，需要移动 %rsp 指针存入调用者的变量压入栈中

具体调用的时候，会根据返回值对应修改地址和数据。

寄存器保存数值的时候也有一些习惯的用法，这里也举个例子说明：

这里的 yoo 被称为调用者 caller，who 被称为被调用者 callee。于是就有一个问题，能不能用寄存器（这里是 %rdx）来保存临时变量呢？

似乎不大可以，因为在两个函数中都进行了修改，所以在这之前需要做一些额外的操作。对于调用者来说，需要把临时变量保存在栈帧中，然后进行调用；对于被调用者来说，可以在栈帧中保存临时变量，但是在返回的时候需要恢复成原来的样子（让调用者继续工作）

一般来说用法是这样的：

这里的变量都会被保存到 caller 的栈帧中（因为可能之后会被修改）

除了 %rsp 外，这里都会保存在 callee 的栈帧中，并且在调用完成之后需要恢复成原来的数值。

递归的描述

有了前面的的基础，要理解递归就简单很多了，直接上例子

long pcount_r(unsigned long x) {
	if (x == 0)
		return 0;
	else
		return (x & 1) + pcount_r(x >> 1);
}

对应的汇编代码为：

实际执行的过程中，会不停进行压栈，直到最后返回，所以递归本身就是一个隐式的栈实现，但是系统一般对于栈的深度有限制（每次一都需要保存当前栈帧的各种数据），所以一般来说会把递归转换成显式栈来进行处理以防溢出。

这一讲的内容就这么多，需要好好理解。

Stack Structure

Calling Conventions

递归的描述

相关文章