深入浅出计算机组成原理——原理篇：指令和运算（05-10）

全文内容主要来自对课程《深入浅出计算机组成原理》的学习笔记。

05 | 计算机指令

最早是“打孔卡（Punched Card）”来使用计算机的，即输入一系列0/1。

CPU的任务

CPU 在硬件层面实现了加法、乘法等各种处理逻辑。即执行各种计算机指令（Instruction Code）的逻辑机器。

一种CPU对应一种语言，一般称为计算机指令集（Instruction Set）。Intel 和 ARM 就互不相同。

一个程序一般会有很多指令，而CPU不能存在这么多，一般都是在存储器中。这种就叫存储程序型计算机（Stored-program Computer）。

非存储程序型，比如用电线和插口组装某种固定程序的计算机，类似一次性的。

编译到汇编

一段C程序需要编译（Compile）成汇编语言（ASM，Assembly Language）才能在 Linux 上 run。

可以使用 gcc 和 objdump 把对应的汇编代码和机器码打印出来。

$ gcc -g -c test.c
$ objdump -d -M intel -S test.o

如下所示：

• 左侧有一堆数字，这些就是一条条机器码；
• 右边有一系列的 push、mov、add、pop 等，这些就是对应的汇编代码。

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    

实际上，机器码和汇编代码是一一对应的，之所以需要后者就是为了程序员使用方便。

解析指令和机器码

指令非常多，例如Intel就有2k多，但一般分为5大类：

1. 算数类；（加减乘除）
2. 数据传输类；（赋值、读写）
3. 逻辑类；（与或非）
4. 条件分支类；（if/else）
5. 无条件跳转。（函数调用）

例如，使用上面的 MIPS 指令集将下列的code转为机器码。

add $t0,$s2,$s1

如下转换过程：

1. opcode=0，rs表示寄存器1地址是17，rt表示寄存器2地址是18，rd表示临时寄存器地址8，位移是0；
2. 二进制则是每个code码对应结果；
3. 二进制code转为16进制，方式如下（结果对应4行打孔带）

   000000 10001 10010 01000 00000 100000
   =0000 0010 0011 0010 0100 0000 0010 0000（每4个一组分配，对应纵向打孔带）
   =0X02324020

---

06 | 指令跳转

CPU 是如何执行指令

指令很复杂，CPU 在软件层面已经为我们做好了封装，程序转为指令后是按顺序执行。

CPU 其实就是由一堆寄存器组成的。而寄存器由多个触发器（Flip-Flop）或者锁存器（Latches）组成的简单电路。

触发器和锁存器，其实就是两种不同原理的数字电路组成的逻辑门。

N 个触发器或者锁存器，就可以组成一个 N 位（Bit）的寄存器，能够保存 N 位的数据。

比方说，我们用的 64 位 Intel 服务器，寄存器就是 64 位的。

介绍最重要的3种特殊寄存器：

1. PC 寄存器（Program Counter Register）。

   我们也叫指令地址寄存器（Instruction Address Register），用来存放下一条需要执行的计算机指令的内存地址。

2. 指令寄存器（Instruction Register）

   用来存放当前正在执行的指令。

3. 条件码寄存器（Status Register）

   用里面的一个一个标记位（Flag），存放 CPU 进行算术或者逻辑计算的结果。

实际上还有很多寄存器：整数寄存器、浮点数寄存器、向量寄存器和地址寄存器等等，甚至还有通用寄存器。

一个程序的一条条指令，在内存里面是连续保存的，也会一条条顺序加载。

如下图，简单的if/else程序执行case：

注释：
cmp：比较前后的值，结果存入条件码寄存器
DWORD PTR：表示操作数据类型int32
[rbp-0x4]：表示变量r的地址
ZF：零标志码，在cmp指令运行后置为1
mov eax, 0x0，默认为0的返回值到累加器

实现循环

如下，是一个for循环的代码过程：

循环也是用 1e 这个地址上的 cmp 比较指令；
结合jle 条件跳转指令来实现；
往前跳转使得条件满足的时候，PC 寄存器会把指令地址设置到之前执行过的指令位置；

---

07 | 函数调用

Stack Overflow 的名字来自于一个常见的报错，就是栈溢出（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);
}

从上面程序开始，通过下述编译将code转为汇编代码。

$ 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    

注意：代码先执行了一条 push 指令和一条 mov 指令，结束后执行了一条 pop 和一条 ret 指令。 这就是压栈（Push）和出栈（Pop）操作。

如果使用寄存器记录函数调用的指令地址，寄存器数量的限制是卡点。在内存里面开辟一段空间，用栈这个后进先出（LIFO，Last In First Out）的数据结构。以此来记录，调用函数前将返回地址压栈，执行完将最上面的地址进行出栈。

实际上，栈不仅存返回地址，还要存参数，整个函数的空间就是栈帧（Stack Frame）。

注释：

• rbp： register base pointer 栈基址寄存器（栈帧指针），指向当前栈帧的栈底地址。
• rsp： register stack pointer 栈顶寄存器（栈指针），指向栈顶元素。

结合前面的汇编代码，过程：

1. main 的 34 行 call 会调用 0 行的 add， push rbp 就是压栈；
2. 接着， mov rbp, rsp 则是把 rsp 这个栈指针（Stack Pointer）的值复制到 rbp 里，而 rsp 始终会指向栈顶；
3. add 执行完成后，又会分别调用第 12 行的 pop rbp 来将当前的栈顶出栈；
4. 最后 13 行的 ret 指令，将下一条指令出栈到 PC 寄存器中，控制权返回到出栈后的栈顶。

stack overflow

对于递归调用，只需要使用好 rbp 和 rsp（两个维护栈顶所在地址的寄存器）。

不过，栈的大小也是有限的。如果函数调用层数太多，就会遇到栈溢出的错误，这就是大名鼎鼎的“stack overflow”。

函数内联进行性能优化

函数内联（Inline）：把一个实际调用的函数产生的指令，直接插入到调用的位置。

内联优化：CPU 需要执行的指令数变少了，根据地址跳转的过程不需要了，压栈和出栈的过程也不用了。

内联代价：复用的程序指令在调用它的地方完全展开了。展开次数越多，整个程序占用的空间就会越大。

没有调用其他函数，只会被调用的函数，我们一般称之为叶子函数（或叶子过程）。

---

08 | ELF和静态链接

既然程序最终都被变成了一条条机器码去执行，那为什么程序需要区分 Linux 或 Windows 操作系统才能执行呢？

编译、链接和装载：拆解程序执行

前面提过C语言转为机器码后CPU可以执行，那么怎么转的呢？

gcc 命令可以将*.c文件编译成*.o文件，但他们都不是可执行文件（Executable Program），称为目标文件（Object Faile），因为地址都是从 0 开始的。通过 gcc 的 -o 参数即可以生产可执行文件。

在C 语言代码 - 汇编代码 - 机器码过程中，实际是2步：

1. 由编译（Compile）、汇编（Assemble）以及链接（Link）三个阶段，生产可执行文件；
2. 装载器（Loader）把可执行文件装载（Load）到内存中，CPU 从内存中读指令和数据来执行。

ELF 格式和链接

可执行代码比目标代码复杂，使用ELF（Execuatable and Linkable File Format）格式，即可执行与可链接文件格式，存放指令和数据。

符号表：关联变量等名称和地址。

ELF 文件格式如下所示：

1. 代码段（Code Section），.text Section，保存程序的代码和指令；
2. 数据段（Data Section），.data Section，保存初始化数据；
3. 重定位表（Relocation Table），.rel.text Secion，保存跳转地址；
4. 符号表（Symbol Table），.symtab Section，保留定义的函数名称和对应地址的地址簿。

链接器将目标文件转为可执行文件（参考下图）：

1. 收集符号表信息，构建全局符号表；
2. 基于重定位表，修正需要跳转的地址代码；
3. 将所有目标文件对应段合并。

readelf -s link_example.o //查看符号表
objdump -r link_example.o //查看重定位表

基于ELF文件，装载起就不需要考虑跳转地址问题，只需要加载指令和数据让那个CPU执行即可。windows 则是 PE 文件。

总结：两个操作系统下可执行文件的格式不一样，导致程序不能直接跨系统执行。

---

09 | 程序装载

比尔·盖茨在上世纪 80 年代说的“640K ought to be enough for anyone”.

程序装载面临的挑战

装载器要满足两个要求：

• 可执行程序加载后占用的内存空间应该是连续的，以顺序执行。
• 我们需要同时加载很多个程序，并且不能让程序自己规定在内存中加载的位置。

方案：开辟一段物理内存空间，映射给程序指定的虚拟内存地址。

虚拟内存地址（Virtual Memory Address）：指令里用到的内存地址；
物理内存地址（Physical Memory Address）：实际在内存硬件里面的空间地址；

因此，只需要维护映射关系的起始地址和对应的空间大小，相当于分段映射。

内存分段

分段（Segmentation）：找出一段连续的物理内存和虚拟内存地址进行映射的方法。

内存碎片（Memory Fragmentation）是分段的问题。

解决的办法：内存交换（Memory Swapping）

即将大程序先存到硬盘再读回内存连续空间。如上图，蓝色部分读回时紧邻黄色部分，就可以腾出连续的256m内存。但效率慢。

内存分页

另一个思路是少出现一些内存碎片，当需要进行内存交换的时候，让涉及的数据更少一点，就叫作内存分页（Paging）。

分段：根据程序需要，分配一整段连续的空间；
分页：把整个物理内存空间提前切成一段段固定尺寸的大小（页-Page），后续均匀使用。

页的尺寸一般很小，在 Linux 下一般 4KB。可以通过下属code查看。

$ getconf PAGE_SIZE

页都能使用，如果需要交换，也可以很少的与磁盘交互，程序运行的时候可以只加载需要运行的部分。整个页的使用通过引入一个间接层做映射即可，开发者感知不到。

回到开头，内存是不是640K就够了?
原则上，CPU 只需要执行当前的指令，极限下内存也只需要加载一页。在需要用到对应的数据和指令的时候，从硬盘上交换到内存里面来就好。

那一提到和磁盘交互，必然性能是瓶颈，所以实际中内存增加还是很重要。

---

10 | 动态链接

程序的链接，是把对应的不同文件内的代码段，合并到一起，成为最后的可执行文件。

如此同样的功能开发一次，其他地方都能复用。

链接可以分动、静，共享运行省内存

在内存空间有限的大背景下，
动态链接（Dynamic Link）：同样功能的代码能够在不同程序里面复用，通过加载到内存中的共享库；
静态链接（Static Link）：把对应的不同文件内的代码段合并到一起。

共享库：
windows：共享库文件就是.dll，也就是 Dynamic-Link Libary（DLL，动态链接库）；
linux：.so 文件，也就是 Shared Object。

地址无关&相对地址

共享代码要求机器码必须地址无关，实际上大部分函数库其实都可以做到地址无关。
常见的地址相关的代码，比如绝对地址代码（Absolute Code）、利用重定位表的代码等等。

相对地址（Relative Address）：各种指令中使用到的内存地址，给出的不是一个绝对的地址空间，而是一个相对于当前指令偏移量的内存地址。

因为整个共享库是放在一段连续的虚拟内存地址中的，无论装载到哪一段地址，不同指令之间的相对地址都是不变的。

PLT 和 GOT

PLT：Procedure Link Table，程序链接表，存放要调用函数的地址；
GOT：Global Offset Table，全局偏移表，查当前运行程序的虚拟内存里的对应位置。

在共享库的 data section 里面，保存了 GOT。虽然共享库的代码部分的物理内存是共享的，只加载同一份。但是数据部分是各个动态链接它的应用程序里面各加载一份的，故通过各个可执行程序在加载时，生成的各不相同的 GOT 表，来找到它需要调用到的外部变量和函数的地址。

因此，函数调用->PLT查GOT地址->查虚拟内存地址->查真实内存地址。

加了一层PLT是为了做延迟绑定：如果函数没有实际被调用到，就不需要更新GOT里面的数值。因为很多动态装载的函数库都是不会被实际调用到的。

---