计算机组成原理指令和运算
在软硬件接口中，cpu帮我们做了什么事？
我们常说，cpu就是计算机的大脑。cpu的全程是Central Processing Unit，中文是中央处理器。
上一节说了，从硬件的角度来看，cpu就是一个超大规模集成电路，通过电路实现了加法、乘法乃至各种各样的处理逻辑。
如果我们从软件工程师的角度来讲，cpu就是一个执行各种计算机指令（Instruction Code）的逻辑机器。这里的计算机指令，就好比一门CPU能够听得懂的语言，我们也可以把它叫做机器语言（Machine Language）。
不同的cpu能够听懂的语言不太一样。比如，我们的个人电脑用的是Inter的CPU，苹果手机用的是ARM的CPU。这两者能听懂的语言就不太一样。类似这样两种CPU各自支持的语言，就是两组不同的计算机指令集，英文叫Instruction Set。这里面的Set，其实就是数学上的集合，代表不同的单词、语法。
所以，如果我们在自己电脑上写一个程序，然后把这个程序复制一下，装到自己的手机上，肯定是没有办法正常运行的，因为两者语言不通。而一台电脑上的程序，简单复制一下到另外一台电脑上，通过就能正常运行，因为这两台CPU有着相同的指令集，也就是说，它们的语言相同的。
一个计算机程序，不可能只有一条指令，而是由成千上万条指令组成。但是CPU里不能一直放着所有指令，所以计算机程序平时是存储在存储器中的。这种程序指令存储在存储器里面的计算机，我们就叫做存储程序型计算机（Stored-program Computer）。
说到这里，你可能要问了，难道还有不是存储程序型的计算机么？其实，在没有现代计算机之前，有着聪明才智的工程师，早就发明了一种叫Plugboard Computer的计算设备。我把它直译成“插线板计算机”。在一个布满各种插口和插座的板子上，工程师用不同的电线来连接不同的插口和插座，从而来完成各种计算任务。下面这个图就是一台IBM的Plugboard，看起来是不是有一股满满的蒸汽朋克范儿？
image.png
从编译到汇编，代码怎么变成机器码？
了解计算机指令和计算机指令集，接下来我们来看看，平时编写的代码，到底是怎么变成一条条计算机指令，最后被CPU执行的呢？我们拿一小段真是的C语言程序来看看
// test.c
int main()
{
int a = 1;
int b = 2;
a = a + b;
}
这是一段再简单不过的C语言程序，即便不了解C语言，应该也可以看懂了。我们给两个变量a、b分别赋值1、2，然后再将a、b量变量中的值加在一起，重新赋值给了a这个变量。
要让这段程序在一个Linux操作系统上跑起来，我们需要把整个程序翻译成一个汇编语言（ASM，Assembly Language）的程序，这个过程我们一般叫编译（Compile）成汇编代码。
针对汇编代码，我们可以再用汇编器（Assembler）翻译成机器码（Machine Code）。这些机器码由0和1组成的机器语言表示。这一条条机器码，就是一条条计算机指令。这样一串串的16进制数字，就是我们CPU能够真正认识的计算机指令。
在一个Linux操作系统上，我们可以简单地使用gcc和objdump这两条命令，把对应的汇编代码和机器码都打印出来。
$ gcc -g -c test.c
$ objdump -d -M intel -S test.o
可以看到，左侧有一堆数字，这些就是一条条机器码；右边有一系列的push、mov、add、pop等，这些就是杜英的汇编代码。一行C语言代码，有时候只对应一条机器码和汇编代码，有时候则是对应两条机器码和汇编代码。汇编代码和机器码之间是一一对应的。
test.o: file format elf64-x86-64
Disassembly of section .text:
0000000000000000 <main>:
int main()
{
0: 55 push rbp
1: 48 89 e5 mov rbp,rsp
int a = 1;
4: c7 45 fc 01 00 00 00 mov DWORD PTR [rbp-0x4],0x1
int b = 2;
b: c7 45 f8 02 00 00 00 mov DWORD PTR [rbp-0x8],0x2
a = a + b;
12: 8b 45 f8 mov eax,DWORD PTR [rbp-0x8]
15: 01 45 fc add DWORD PTR [rbp-0x4],eax
}
18: 5d pop rbp
19: c3 ret
这时候你可能又要问了，我们实际在用GCC（GUC编译器套装，GNU Compiler Cpllectipon）编译器的时候，可以直接把代码编译成机器码呀，为什么还需要汇编代码呢？原因很简单，你看着那一串数字表示的机器码，是不是摸不着头脑？但是即使你没学过汇编代码，看的时候也能“猜”出一些这些代码的含义。
因为汇编代码其实就是“给程序员看的机器码”，也正因为这样，机器码和汇编代码是一一对应的。我们人类很容易记住add、mov这些用英文表示的指令，而8b 45 f8这样的指令，由于很难一下子看明白是在干什么，所以会难以记忆。尽管早年互联网上到处流传，大神程序员拿着小刀在光盘上刻出操作系统的梗，但是要让你用打孔卡来写个程序，估计浪费的卡片比用的卡片要多的多。
image.png
从高级语言到汇编语言，再到机器码，就是一个日常开发程序，最终变成了CPU可以执行的计算机指令的过程。
解析指令和机器码
了解这个过程，下面我们放大局部，来看看这一行行的汇编代码和机器指令，到底是什么意思。
我们就从平时用的电脑、手机这些设备来说起。这些设备的CPU到底有哪些指令呢？这个还真有不少，我们日常用的Inter CPU，有2000条左右的CPU指令，实在是太多了，但是，常用的指令可以分成五大类/
第一类是算术类指令。我们的加减乘除，在CPU层面，都会变成一条条算术类指令。
第二类是数据传输类指令。给变量赋值、在内存里读写数据，用的都是数据传输类指令。
第三类是逻辑类指令，逻辑上的与或非，都是这一类指令。
第四类是条件分支类指令，日常我们写的if/else，其实都是条件分支类指令。
最后一类是无条件跳转指令，写一些大一点的程序，我们常常需要写一些函数或者方法。在调用函数的时候，其实就是发起了一个无条件跳转指令。
image.png
下面我们来看看，汇编器是怎么把对应的汇编代码，翻译成为机器码的。
我们说过，不同的CPU有不同的指令集，也就对应着不同的汇编语言和不同的机器码。为了方便快速理解这个机器码的计算方式，我们选用最简单的MIPS指令集，来看看机器码是如何生产的。
MIPS是一组由MIPS技术公司在80年代中期设计出来的CPU指令集。
image.png
MIPS的指令是一个32位的整数，高6位叫操作码（Opcode），也就是代表这条指令具体是一条什么样的指令，剩下的26位有三种格式，分别是R、I和J。
R指令是一般来做算术和逻辑操作，里面有读取和写入数据的寄存器的地址。如果是逻辑位移，后面还有位移操作和的位移量，而最后的功能码，则是在前面的操作码不够的时候，扩展操作码表示对应的具体指令的。
I指令，则通常使用在数据传输、条件分支，以及在运算的时候使用的并非变量还是常数的时候。这个时候，没有了位移量和操作码，也没有了第三个寄存器，而是把这三个部分直接合并成一个地址值或者一个常数。
J指令就是一个跳转指令，高6位之外的26位都是一个跳转后的地址。
add $t0,$s2,$s1
我以一个简单的加法算术指令add t0，s1，s2为例，给你解释。为了方便，我们下面都用十进制来表示对应的代码。
对应的MIPS指令里的opcode是0，rs代表第一个寄存器s1的地址是17，rt代表第二个寄存器s2的四肢是18，rd代表目标的临时寄存器t0的地址，是8。因为不是位移操作，所以位移量是0.这些数字拼在一起，就变成了一个MIPS的加法指令。
为了读起来方便，我们一般把对应的二进制数，用十六进制标识出来，也就是0x02324020。这个数字也就是这条指令对应的机器码。
image.png
CPU是如何执行指令的？
那我们的Inter CPU来说，里面差不多有几百亿个晶体管。实际上，一条条计算机指令执行起来非常复杂，好在CPU在软件层面已经为我们做好了封装。对于我们这些做软件的程序员来说，我们只要知道，写好的代码变成了指令之后，是一条一条顺序执行的就可以了。
我们先不管几百亿的晶体管的背后是怎么通过电路运转起来的，逻辑上，我们可以认为，CPU其实就是由一堆寄存器组成。而寄存器就是CPU内部，由多个触发器（Flip-Flop）或者锁存器（Latches）组成的简单电路。
触发器和锁存器，其实就是两种不同原理的数字电路组成的逻辑门。
N个触发器或者锁存器，就可以组成N位（bit）的寄存器，能够保存N位的数据。比方说，我们用64位Intel服务器，寄存器就是64位。
image.png
一个CPU里面会有很多中不同功能的寄存器，这里介绍三种比较特殊的。
一个是PC寄存器（Program Counter Register），也叫指令地址寄存器（Instruction Address Register）。顾名思义，它就是用来存放下一条需要执行的计算机指令的内存地址。
第二个是指令寄存器（Instruction Register），用来存放当前正在执行的指令。
第三个是条件寄存器（Status Register），用里面的一个一个标记位（Flag），存放CPU进行算术或者逻辑计算的结果。
除了这些特殊的寄存器，CPU里面还有更多用来存储数据和内存地址的寄存器。这样的寄存器通常一类里面不止一个。我们通常根据存放的数据内容来给它们命名，比如整数寄存器、浮点数寄存器、向量寄存器和地址寄存器等等。有些寄存器既可以存放数据，又能存放地址，我们就叫它通用寄存器。
image.png
实际上，一个程序执行的时候，CPU会根据PC寄存器里的地址，从内存里面把需要执行的指令读取到指令寄存器里面执行，然后根据指令长度自增，开始顺序读取下一条指令，可以看到，一个程序的一条条指令，在内存里面是连续保存的，也会一条条顺序加载。
而有些特殊指令，比如J类指令，也就是跳转指令，会修改PC寄存器里面的地址值。这样，下一条要执行的指令就不是从内存里面顺序加载的了。事实上，这些跳转指令的存在，也是我们可以在写程序的时候，使用if...else条件语句和while/for循环语句的原因。
从if...else来看程序的执行和跳转
我们现在就来看一个包含if...else的简单程序。
// test.c
#include <time.h>
#include <stdlib.h>
int main()
{
srand(time(NULL));
int r = rand() % 2;
int a = 10;
if (r == 0)
{
a = 1;
} else {
a = 2;
}
我们用rand生产了一个随机数r，r要么是0，要么是1。当r是0的时候，我们把之前定义的变量a设成1，不然就设成2.
$ gcc -g -c test.c
$ objdump -d -M intel -S test.o
我们把这个程序编译成汇编代码，你可以忽略前后无关的代码，只关注这里的if...else条件判断语句。对应的汇编代码是这样的：
if (r == 0)
3b: 83 7d fc 00 cmp DWORD PTR [rbp-0x4],0x0
3f: 75 09 jne 4a <main+0x4a>
{
a = 1;
41: c7 45 f8 01 00 00 00 mov DWORD PTR [rbp-0x8],0x1
48: eb 07 jmp 51 <main+0x51>
}
else
{
a = 2;
4a: c7 45 f8 02 00 00 00 mov DWORD PTR [rbp-0x8],0x2
51: b8 00 00 00 00 mov eax,0x0
}
可以看到，这里对于r==0的条件判断，被编译成了cmp和jne这两条指令。
cmp指令比较了前后两个操作数的值，这里的DWORD PTR代表操作的数据类型是32位整数，而[rbp-0x4]则是一个寄存器的地址。所以，第一个操作数就是从寄存器里拿到变量r的值。第二个操作数0x0就是我们设定的常量0的16进制表示。cmp指令的比较结果，会存入到条件码寄存器当中去。
在这里，如果比较的结果是True，也就是r == 0，就把零标志条件码（对应的条件码是ZF，Zero Flag）设置位1。除了零标志之外，Inter的CPU下还有进位标志（CF，Carry Flag）、符号标志（SF，Sign Flag）以及溢出标志（OF，Overflow Flag），用在不同的判断条件下。
cmp指令执行完成之后，PC寄存器会自动自增，开始执行下一条jne的指令。
跟着的jne指令，是jump if not equal的意思，它会查看对应的零标志位。如果为0，会跳转到后面跟着的操作数4a的位置。这个4a，对应这里汇编代码的行号，也就是上面设置的else条件里的第一条指令。当跳转发生的时候，PC寄存器就不再是自增变成下一条指令的地址，而是被直接设置成这里的4a这个地址。这个时候，CPU再把4a地址里的指令加载到指令寄存器中来执行。
跳转到执行地址为4a的指令，实际是一条mov指令，第一个操作数和前面的cmp指令一样，是另一个32为整型的寄存器地址，以及对应的2的16进制值0x2。mov指令把2设置到对应的寄存器里去，相当于一个赋值操作。然后，PC寄存器里的值继续自增，执行下一条mov指令。
这条mov指令的第一个操作数eax，代表累加寄存器，第二个操作数0x0则是16进制的0的表示。这条指令其实没有实际的作用。它的作用是一个占位符。我们回过头去看前面的if条件，如果满足的话，再赋值的mov指令执行完成之后，有一个jmp的无条件跳转指令。跳转的地址就是这一行的地址51。我们的main函数没有设定返回值，而mov eax， 0x0其实就是给main函数生成了一个默认的为0的返回值到累加器里面。if条件里面的内容执行完成之后也会跳转到这里。和else里的内容结束之后的位置是一样的。
image.png
如何通过if...else和goto来实现循环？
int main()
{
int a = 0;
for (int i = 0; i < 3; i++)
{
a += i;
}
}
我们再看一段简单的利用for循环的程序。我们循环自增变量i三次，三次之后，i >= 3，跳出循环。整个程序，对应的Intel汇编代码就是这样的：
for (int i = 0; i < 3; i++)
b: c7 45 f8 00 00 00 00 mov DWORD PTR [rbp-0x8],0x0
12: eb 0a jmp 1e <main+0x1e>
{
a += i;
14: 8b 45 f8 mov eax,DWORD PTR [rbp-0x8]
17: 01 45 fc add DWORD PTR [rbp-0x4],eax
for (int i = 0; i < 3; i++)
1a: 83 45 f8 01 add DWORD PTR [rbp-0x8],0x1
1e: 83 7d f8 02 cmp DWORD PTR [rbp-0x8],0x2
22: 7e f0 jle 14 <main+0x14>
24: b8 00 00 00 00 mov eax,0x0
}
可以看到，对应的循环也是用1e这个地址上的cmp比较指令，和紧接着的jle条件跳转指令来实现的。主要的差别在于，这里的jle跳转的地址，在这条指令之前的地址14，而非if...else编译出来的跳转指令之后。往前跳转使得条件满足的时候，PC寄存器会把指令地址设置到之前执行过的指令位置，从新执行之前执行过的指令，直到条件不满足，顺序往下执行jle之后的指令，整个循环才结束。
image.png
可以看到，对应的循环也是用1e这个地址上的cmp比较指令，和紧接着的jle条件跳转指令来实现的。主要的差别在于，这里的jle跳转的地址，在这条指令之前的地址14，而非if...else编译出来的跳转指令之后。往前跳转使得条件满足的时候，PC寄存器会把指令地址设置到之前执行过的指令位置重新执行之前执行过的指令，直到条件不满足，顺序往下执行jle之后的指令，整个循环才结束。
image.png
其实，你有没有觉得，jle和jmp指令，有点像程序语言里面的goto命令，直接指定了一个特定条件下的跳转位置。虽然我们在用高级语言开发程序的时候反对使用goto，但是实际在机器指令层面，无论是if...else也好，还是for/while也好，都是用和goto相同的跳转到特定指令位置的方式来实现的。
为什么我们需要程序栈？
从一个简单的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循环有点像。他们两个都是在原来顺序执行的指令过程里，执行了一个内存地址的跳转指令，让指令从原来顺序执行的过程里跳开，从新的跳转后的位置开始执行。
为什么我们需要程序栈？
从一个非常简单的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的指令，这样就会产生无穷无尽的替换。就好像两面镜子面对面放在一块，任何一面镜子里面都会看到无穷多面镜子。
image.png
看来，把被调用函数的指令直接插入在调用出的方法行不通。那我们就换一个思路，能不能把后面要跳回来执行的指令地址记录下来呢？就像前面讲的PC寄存器一样，我们可以专门设立一个“程序调用寄存器”，来存储接下来要跳转回来执行的指令地址。等到函数调用结束，从这个寄存器里取出地址，再跳转到这个记录的地址，继续执行就好了。
但是在多层函数调用里，简单值记录一个地址也是不够的。我们在调用函数A之后，A还可以调用函数B，B还能调用函数C。这一层又一层的调用并没有数量上的限制。在所有函数调用返回之前，每一次调用的返回地址都要记录下来，但是我们CPU里的寄存器数量并不多，向我们一般使用的Inter i7CPU只有16个64位寄存器，调用的层数一多就寸不下了。
最终，计算机科学家们想到了一个比单独记录跳转回来的地址更完善的办法。我们在内存里面开辟一段空间，用栈这个后进先出的数据结构。栈就像一个乒乓球桶，每次程序调用函数之前，我们都把返回后的地址写在一个乒乓球上，然后塞进这个球桶。这个操作其实就是我们常说的压栈。如果函数执行完了，我们就从球桶里取出最上面的那个乒乓球，很显然，这就是出栈。
拿到出栈的乒乓球，找到上面的地址，把程序跳转过去，就返回了函数调用后的下一条指令了。如果函数A在执行完成之前又调用了函数B，那么在取出乒乓球之前，我们需要往球桶里赛一个乒乓球。而我们从球桶最上面拿乒乓球的时候，拿的也一定是最近一次的，也就是最下面一层的函数调用完成后的地址。乒乓球桶的底部，就是栈底，最上面的乒乓球所在的位置，就是栈顶。
image.png
在真实的程序里，压栈的不只有函数调用完成后的返回地址。比如函数A在调用B的时候，需要传输一些参数数据，这些参数数据在寄存器不够用的时候也会被压入栈中。整个函数A所占用的所有内存空间，就是函数A的栈帧。Frame在中文里也有“相框”的意思，所以，每次到这里，我都有种感觉，整个函数A所需要的内存空间就像是被这么一个“相框”给框起来，放在了栈里面。
而实际的程序栈布局，顶和底与我们的乒乓球桶相比是倒过来。底在最上面，顶在最下面，这样的布局是因为栈底的内存地址是在一开始就固定的。而一层层压栈之后，栈顶的内存地址实在逐渐变小而不是变大。
image.png
对应上面函数add的汇编代码，我们来仔细看看，main函数调用add函数时，add函数入口在01行，add函数结束之后在1213行。
我们在调用第34行的call指令时，会把当前的PC寄存器里的下一条指令的地址压栈，保留函数调用结束后要执行的指令地址。而add函数的第0行，push rbp这个指令，就是在进行压栈。这里的rbp又叫栈帧指针，是一个存放了当前栈帧位置的寄存器。push rbp就把之前调用函数，也就是main函数的栈帧的栈底地址，压入栈顶。
接着，第1行的一条命令mov rbp，rsp里，则是把rsp这个栈指针的值复制到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.c的编译出来的汇编代码，没有把add函数单独编译成一段指令顺序，而是在调用u = add(x, y)的时候，直接替换成了一个add指令。
return a+b;
4c: 01 de add esi,ebx
除了依靠编译器的自动优化，你还可以在定义函数的地方，加上inline的关键字，来提示编译器对函数进行内联。
内联带来的优化是，CPU需要执行的指令数变少了，根据地址跳转的过程不需要了，压栈和出栈的过程也不用了。
不过内联并不是没有代价，内联意味着，我们把可以复用的程序指令在调用它的地方完全展开了。如果一个函数在很多地方都被调用了，那就会展开很多次，整个程序占用的空间就会变大了。
image.png
这样没有调用其它函数，只会被调用的函数，我们一般称之为叶子函数（或叶子过程）。
编译、链接和装载：拆解程序执行
写好c语言代码，可以通过编译器编译成汇编代码，然后汇编代码再通过汇编器变成cpu可以理解的机器码，于是cpu就可以执行这些机器码了。
我们通过gcc生成的文件和objdump获取到的汇编指令都有些小小的问题，我们先把add函数实例，拆分成两个add_lib.c和link_examplie.c。
// add_lib.c
int add(int a, int b)
{
return a+b;
}
// link_example.c
#include <stdio.h>
int main()
{
int a = 10;
int b = 5;
int c = add(a, b);
printf("c = %d\n", c);
}
我们通过gcc来编译这两个文件，然后通过objdump命令看看它们的汇编代码。
$ gcc -g -c add_lib.c link_example.c
$ objdump -d -M intel -S add_lib.o
$ objdump -d -M intel -S link_example.o
add_lib.o: file format elf64-x86-64
Disassembly of section .text:
0000000000000000 <add>:
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
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
link_example.o: file format elf64-x86-64
Disassembly of section .text:
0000000000000000 <main>:
0: 55 push rbp
1: 48 89 e5 mov rbp,rsp
4: 48 83 ec 10 sub rsp,0x10
8: c7 45 fc 0a 00 00 00 mov DWORD PTR [rbp-0x4],0xa
f: c7 45 f8 05 00 00 00 mov DWORD PTR [rbp-0x8],0x5
16: 8b 55 f8 mov edx,DWORD PTR [rbp-0x8]
19: 8b 45 fc mov eax,DWORD PTR [rbp-0x4]
1c: 89 d6 mov esi,edx
1e: 89 c7 mov edi,eax
20: b8 00 00 00 00 mov eax,0x0
25: e8 00 00 00 00 call 2a <main+0x2a>
2a: 89 45 f4 mov DWORD PTR [rbp-0xc],eax
2d: 8b 45 f4 mov eax,DWORD PTR [rbp-0xc]
30: 89 c6 mov esi,eax
32: 48 8d 3d 00 00 00 00 lea rdi,[rip+0x0] # 39 <main+0x39>
39: b8 00 00 00 00 mov eax,0x0
3e: e8 00 00 00 00 call 43 <main+0x43>
43: b8 00 00 00 00 mov eax,0x0
48: c9 leave
49: c3 ret
既然代码已经被编译成了指令，运行./link_examle.o，没有执行权限，我们遇到一个Permisssion denied错误。即使通过chmod命令赋予link_example.o文件可执行权限，运行./link_example.o仍然只会得到一条can not execute binary file：Exec format error的错误。
我们再仔细看一下onjdump出来的两个文件的代码，会发现两个程序都是从0开始的。如果地址是一样的，程序如果需要通过call指令调用函数的话，它怎么知道应该跳转到哪一个文件里呢？
这么说吧，无论是这里的运行报错，还是objdump出来的汇编代码里面的重复地址，都是因为add_lib.o以及link_example.o并不是一个可执行文件（Executable Program），而是目标文件（Object File）。只有通过链接器（Linker）把多个目标文件以及调用的各种函数库链接起来，我们才能得到一个可执行文件。
我们通过gcc的-o参数，可以生成对应的可执行文件，对应执行之后，就可以得到这个简单的加法调用函数的结果。
$ gcc -o link-example add_lib.o link_example.o
$ ./link_example
c = 15
实际上，c语言代码-汇编代码-机器码 这个过程，再我们的计算机上进行的时候是由两部分组成的。
第一个部分由编译（Compile）、汇编（Assemble）以及链接（Link）三个阶段组成。在这三个阶段完成之后，我们就生成了一个可执行文件。
第二部分，我们通过装载器（Loader）把可执行文件装载（Load）到内存中。cpu从内存中读取指令和数据，来开始真正执行程序。
image.png
ELF格式和链接：理解链接过程
程序最终是通过装载器变成指令和数据的，所以其实我们生成的可执行代码也不仅仅是一条条的指令。我们还是通过objdump指令，把可执行文件的内容拿出来看看。
link_example: file format elf64-x86-64
Disassembly of section .init:
...
Disassembly of section .plt:
...
Disassembly of section .plt.got:
...
Disassembly of section .text:
...
6b0: 55 push rbp
6b1: 48 89 e5 mov rbp,rsp
6b4: 89 7d fc mov DWORD PTR [rbp-0x4],edi
6b7: 89 75 f8 mov DWORD PTR [rbp-0x8],esi
6ba: 8b 55 fc mov edx,DWORD PTR [rbp-0x4]
6bd: 8b 45 f8 mov eax,DWORD PTR [rbp-0x8]
6c0: 01 d0 add eax,edx
6c2: 5d pop rbp
6c3: c3 ret
00000000000006c4 <main>:
6c4: 55 push rbp
6c5: 48 89 e5 mov rbp,rsp
6c8: 48 83 ec 10 sub rsp,0x10
6cc: c7 45 fc 0a 00 00 00 mov DWORD PTR [rbp-0x4],0xa
6d3: c7 45 f8 05 00 00 00 mov DWORD PTR [rbp-0x8],0x5
6da: 8b 55 f8 mov edx,DWORD PTR [rbp-0x8]
6dd: 8b 45 fc mov eax,DWORD PTR [rbp-0x4]
6e0: 89 d6 mov esi,edx
6e2: 89 c7 mov edi,eax
6e4: b8 00 00 00 00 mov eax,0x0
6e9: e8 c2 ff ff ff call 6b0 <add>
6ee: 89 45 f4 mov DWORD PTR [rbp-0xc],eax
6f1: 8b 45 f4 mov eax,DWORD PTR [rbp-0xc]
6f4: 89 c6 mov esi,eax
6f6: 48 8d 3d 97 00 00 00 lea rdi,[rip+0x97] # 794 <_IO_stdin_used+0x4>
6fd: b8 00 00 00 00 mov eax,0x0
702: e8 59 fe ff ff call 560 <printf@plt>
707: b8 00 00 00 00 mov eax,0x0
70c: c9 leave
70d: c3 ret
70e: 66 90 xchg ax,ax
...
Disassembly of section .fini:
...
你会发现，可执行代码dump出来的内容，和之前的目标代码长得差不多，但是长了很多。因为在linux下，可执行文件和目标文件所使用的都是一种叫ELF（Execuatable and Linkable File Format）的文件格式，中文名字叫可执行与可链接文件格式，这里面不仅存放了编译成的汇编指令，还保留了很多别的数据。
比如我们过去的所有objdump出来的代码里，你都可以看到对应的函数名称，像add、main等等，乃至你自己定义的全局可以访问的变量名称，都存放在这个ELF格式文件里。这些名字和它们对应的地址，在ELF文件里面，存储在一个叫做符号表（Symbols Table）的位置里。符号表相当于一个地址簿，把名字和地址关联了起来。
我们先只关注和我们add以及main函数相关的部分。你会发现，这里面，main函数里调用add的跳转地址，不再是下一条指令的地址了，而是add函数的入口地址了，这就是ELF格式和链接器的功劳。
image.png
ELF文件格式把各种信息，分成一个一个的Section保存起来。ELF有一个基本的文件头（File Header），用来表示这个文件的基本属性，比如是否是可执行文件，对应的CPU、操作系统等等。除了这些基本属性之外，大部分程序还有这么一些Section：
- 首先是.text Section，也叫做代码段或者指令段（Code Section），用来保存程序的代码和指令；
- 接着是.data Section，也叫数据段（Data Section），用来保存程序里面设置好的初始化数据信息；
- 然后就是.rel.text Section，叫做重定位表（Relocation Table）。重定位表里，保留的是当前文件里面，哪些跳转地址其实是我们不知道的。比如上面的link_example.o里面。我们在main函数里面调用了add和printf这两部分函数，但是链接发生之前，我们并不知道该跳转到哪里，这些信息就会存储在重定位表里。
- 最后是.sybtab Section，叫做符号表（Symbol Table）。符号表保留了我们所说的当前文件里面定义的函数名成和对应地址的地址簿。
链接器会扫描所有输入的目标文件，然后把所有符号表里的信息收集起来，构成一个全局的符号表。然后再根据重定位表，把所有不确定要跳转地址的代码，根据符号表里面存储的地址，进行一次修正。最后，把所有的目标文件的对应段进行一次合并，变成了最终的可执行代码。这也是为什么，可执行文件里面的函数调用的地址都是正确的。
image.png
在链接器把程序变成可执行文件之后，要装载器去执行程序就容易多了。装载器不再需要考虑地址跳转的问题，只需要解析ELF文件，把对应的指令和数据，加载到内存里面供CPU执行就可以了。
程序装载面临的跳转
上一将，我们看到了如果通过链接器，把多个文件合并成一个最终可执行文件。在运行这些可执行文件的时候，我们其实是通过一个装载器，解析ELF或者PE格式的可执行文件。装载器会把对应的指令和数据加载到内存里面来，让cpu去执行。
说起来只是装载到内存里面这一句话的事儿，实际上装载器需要满足两个要求。
第一，可执行程序加载后占用的内存空间应该是连续的。执行指令的时候，程序计数器是顺序地一条一条指令执行下去。这也就意味着，这一条条指令需要连续地存储在一起。
第二，我们需要同时加载很多个程序，并且不能让程序自己规定在内存中加载的位置。虽然编译出来的指令里已经有了对应的各种各样的内存地址，但是实际加载的时候，我们其实没有办法确保，这个程序一定加载在哪一段内存地址上。因为我们现在的计算机通常会同时运行很多个程序，可能你想要的内存地址已经被其它加载了的程序占用了。
要满足这两个基本的要求，我们很容易想到一个办法。那就是我们可以在内存里面，找到一段连续的内存空间，然后分配给装载的程序，然后把这段连续的内存空间地址，和整个程序指令里指定的内存地址做一个映射。
我们把指令里用到的内存地址叫做虚拟内存地址（Virtual Memory Address），实际在内存硬件里面的空间地址，我们叫物理内存地址（Physical Memory Address）。
程序里有指令和各种内存地址，我们只需要关心虚拟内存地址就可以了。对于任何一个程序来说，它看到的都是同样的内存地址。我们维护了一个虚拟内存到物理内存的映射表，这样实际程序指令执行的时候，会通过虚拟内存地址，找到对应的物理内存地址，然后执行。因为是连续的内存地址空间，所以我们只需要维护映射关系的起始地址和对应的空间大小就可以了。
内存分段
这种找出一段连续的物理内存和虚拟内存地址进行映射的方法，我们叫分段（Segmentation）。这里的段，就是系统分配出来的那个连续的内存空间。
image.png
分段的办法很好，解决了程序本身不需要关心具体的物理内存地址的问题。但它也有一些不足之处，第一个就是内存碎片（Memory Fragmentation）的问题。
我们来看这样一个例子。我现在手头的这台电脑，有1GB的内存，我们先启动一个图形渲染程序，占用了512MB的内存，接着启动要给Chrome浏览器，占用了128MB内存，再启动一个Python程序，占用了256MB内存。这个时候关掉Chrome，于是空闲内存还有1024 - 512 - 256 = 256MB。按理来说，我们有足够的空间再去装载一个200MB的程序。但是，这256MB的内存空间不是连续的，而是被分成了两段128MB的内存。因此，实际情况是，我们的程序没有办法加载进来。
image.png
当然，这个我们也有办法解决。解决的办法叫内存交换（Memory Swapping）。
我们可以把Python程序占用的那256MB内存写到硬盘上，然后再从硬盘上读回来到内存里。不过读回来的时候，我们不再把它加载到原来的位置，而是紧紧跟在那已经被占用了的512MB内存后面。这样，我们就有了连续的256MB内存空间，就可以去加载一个新的200MB的程序。如果你自己安装过Linux操作系统，你应该遇到过分配一个swap硬盘分区的问题。这块分出来的磁盘空间，起始就是专门给Linux操作系统进行内存交换用的。
虚拟内存、分段，再加上内存交换，看起来似乎已经解决了计算机同时装载运行很多个程序的问题。不过，这三者的组合仍然会遇到一个性能瓶颈。硬盘的访问速度要比内存慢的很多，而每一次内存交换，我们都需要把一大段连续的内存的内存数据写到硬盘上。所以，如果内存交换的时候，交换的是一个很占用内存空间的程序，这样整个机器都会显得卡顿。
内存分页
既然问题出在内存碎片和内存交换的空间太大上，那么解决问题的办法就是，少出现一些内存碎片。另外，当需要进行内存交换的时候，让需要交换写入或者从磁盘装载的数更少一点，这样就可以解决这个问题。这个办法，在现在计算机的内存管理里面，就叫做内存分页（Paging）。
和分段这样分配一整段连续的空间给到程序相比，分页是把整个物理内存空间切成一段段固定尺寸的大小。而对应的程序所需要占用的虚拟内存空间，也会同样切成一段段固定尺寸的大小。这样一个连续并且尺寸固定的内存空间，我们叫页（page）。从虚拟内存到物理内存的映射，不再是拿整段连续的内存的物理地址，而是按照一个一个页来的。页的尺寸一般远远小于整个程序的大小。在Linux下，我们通常只设置成4KB。你可以通过命令看看Linux系统设置的页的大小。
$ getconf PAGE_SIZE
由于内存空间都是预先划分好的，也就没有了不能使用的碎片，而只有被释放出来的很多4kb的页。即使内存空间不够，需要让现有的、正在运行的其它程序，通过内存交换释放出一些内存的页出来，一次性写入磁盘的页只有少数的一个页或者几个页，不会花太多时间，让整个机器被内存交换的过程给卡住。
image.png
更进一步地，分页的方式使得我们在加载程序的时候，不再需要一次性都把程序加载到物理内存中。我们完全可以在进行虚拟内存和物理内存的页之间的映射之后，并不真的把页加载到物理内存里，而是只在程序运行中，需要用到对应虚拟内存页里面的指令和数据时，再加载到物理内存里面去。
实际上，我们的操作系统，的确是这么做的。当要读取特定的页，却发现数据并没有加载到物理内存里的时候，就会触发一个来自于cpu的缺页错误（page Fault）。我们的操作系统会捕捉到这个错误，然后将对应的页，从存放再硬盘上的虚拟内存里读取出来，加载到物理内存里。这种方式，使得我们可以运行那些远大于我们实际物理内存的程序。同时，这样一来，任何程序都不要一次性加载完所有指令和数据，只需要加载当前需要用到的就行了。
通过虚拟内存、内存交换和内存分页这三个技术的组合，我们最终得到了一个让程序不需要考虑实际的物理内存地址、大小和当前分配空间的解决方案。这些技术和方法，对于我们程序的编写、编译和链接的过程都是透明的。这也是我们在计算机的软硬件开发中常用的一种方法，就是加入一个间接层。
通过引入虚拟内存、页映射和内存交换，我们的程序本身，就不再需要考虑对应的真实的内存地址、程序加载、内存管理等问题了。任何一个程序，都只需要把内存当成是一块完整而连续的空间来直接使用。
我们之前讲过，程序的链接，是把对应的不同文件内的代码段，合并到一起，成为最后的可执行文件。这个链接的方式，让我们在写代码的时候做到了“复用”。同样的功能代码只要写一次，然后提供给很多不同的程序进行链接就行了。
这么说来，“链接”其实有点儿像日常生活中的标准化、模块化生产。我们有一个可以生产标准螺帽的生产线，就可以生产很多个不同的螺帽。只要需要螺帽，我们都可以通过链接的方式，去复制一个出来，放到需要的地方去，大到汽车，小到信箱。
但是，如果我们有很多个程序都要通过装载器装载到内存里面，那里面链接好的同样的功能代码，也都需要再装载一遍，再占一遍内存空间。这就好比，假设每个人都有骑自行车的需要，那我们给每个人都生产一辆自行车带在身边，固然大家都有自行车了，但是马路上肯多会特别拥挤。
链接可以分动、静，共享运行省内存
上一节解决了程序装载到内存的时候，讲了很多方法。说起来，最根本的问题其实就是内存空间不够用。如果我们能够让同样功能的代码，在不同的程序里面，不需要各占一份内存空间，那该有多好啊！就好比，现在马路上的共享单车，我们并不需要给每个人都造一辆自行车，只要马路上有这些单车，谁需要的时候，直接通过手机扫码，都可以解锁骑行。
这个思路就引入一种新的链接方法，叫做动态链接（Dynamic Link）。相应的，我们之前说的合并代码的方法，就是静态链接（Static Link）。
在动态链接的过程中，我们想要“链接”的，不是存储在硬盘上的目标文件代码，而实加载到内存中的共享库（Shared Libraries）。顾名思义，这里的共享库重在“共享”这两个字。
这个加载到内存中的共享库会被很多个程序的指令调用到。在Windows下，这些共享库文件就是.dll文件，也就是Dynamic-Link Libary（DLL，动态链接库）。在Linux下，这些共享库文件就是.so文件，也就是Shared Object（动态链接库）。这两大操作系统下的文件名后缀，一个用了“动态链接”的意思，另一个用了“共享”的意思，正好覆盖了两方面的含义。
地址无关很重要，相对地址解烦恼
不过，要想要在程序运行的时候共享代码，也有一定的要求，就是这些机器码必须是“地址无关”的。也就是说，我们编译的共享库文件的指令代码，是地址无关码（Position-Independent Code）。换句话说就是，这段代码，无论加载在哪个内存地址，都能够正常执行。如果不是这样的代码，就是地址相关的代码。
如果还不明白，我再举个例子。如果我们有一个骑自行车的程序，要“前进500米，左转进入天安门广场，再前进500米”。它在500米之后要到天安门广场了，这就是地址相关的。如果程序是“前进500米，左转，再前进500米”，无论你在哪里都可以汽车走这1000米，没有具体地点的限制，这就是地址无关的。
你可以想想，大部分函数其实都可以做到地址无关，因为它们都接受特定的输入，进行确定操作，然后给出返回结果就好了。无论是实现一个向量加法，还是实现一个打印函数，这些代码逻辑和输入的数据在内存里面的位置并不重要。
而常见的地址相关的代码，比如绝对地址代码（Absolute Code）、利用重定位表的代码等等，都是地址相关的代码。你回想一下之前的重定位表。在程序链接的时候，我们就把函数调用后要跳转的地址确定下来了，这意味着，如果这个函数加载到一个不同的内存地址，跳转就会失败。
对于所有动态链接共享库的程序来讲，虽然我们的共享库用的是同一段物理内存地址，但是在不同的应用程序里，它所在的虚拟内存地址是不同的。我们没办法、也不应该要求动态链接同一个共享库的不同程序，必须把这个共享库所使用的虚拟内存地址变成一致。如果这样的话，我们写的程序就必须明确地知道内部的内存地址分配。
那么问题来了，我们要怎么样才能做到，动态共享库编译出来的代码指令，都是地址无关码呢？
动态代码库内部的变量和函数调用都很容易解决，我们只需要使用相对地址（Relative Address）就好了。各种指令中使用到的内存地址，给出的不是一个绝对的地址空间，而实一个相对于当前指令偏移量的内存地址。因为整个共享库是放在一段连续的虚拟内存地址中的，无论装载到哪一段地址，不同指令之间的相对地址都是不变的。
PLT和GOT，动态链接的解决方案
要实现动态链接共享库，并不困难，和前面的静态链接里的符号表和重定向表类似，还是和前面一样，我们还是拿出一小段代码来看看。
