vector

vector表示对象的集合，所有的对象类型都相同，因为vector容纳着其他对象，所以vector也叫容器。
vecotr在头文件vector中，使用前需要包含该头文件，并进行using声明：

1
2
3

#include<vector>

using std::vector;

vector是一个类模板而不是类型。模板本身不是类或者函数，可以将模板看成编译器生成类或者函数编写的一份说明，编译器根据模板创建类或者函数的过程称为实例化，使用模板时需要指出编译器应该把类或者函数实例化成什么类型。
在模板名字后面跟上一对尖括号，括号内为具体的类型说明。

1
2

vector<int> ivec;   //表示int类型的vector
vector< vector<string> > file //vector中是string的vector。

vector对象的初始化

• 默认初始化

  1	vector<string> svec; //默认初始化，不含任何元素

• 列表初始化

1. 元素的初值只能放在花括号内，不能放在圆括号内
2. 给定类内初始值时只能使用拷贝初始化或者列表初始化。

1

vector<string> c = {"hello", "world"};

• 值初始化

1. 只提供给vector对象容纳的元素数量而不用略去初始值。会创建一个值初始化的元素初值，并把它赋给容器中所有元素，这个初始值由vector对象中元素类型决定。
2. 如果vector对象中元素类型是内置类型，如int，初始值自动设置为0。
3. 如果是某种类类型，比如string，由类默认初始化。
4. 有些类要求必须显式的给出初始值。如果vector中对象不支持默认初始化，必须提供初始值。
5. 如果值提供了元素的数量而没有设定初值，只能使用直接初始化。
6. 初始化的真实含义依赖于传递初始值时用的是花括号还是圆括号。花括号进行列表初始化，圆括号提供的信息构造vecotr对象。如果使用花括号中的形式，但是提供的值不能用来列表初始化，考虑使用值构造vector对象。但是如果使用圆括号提供不能构造vector对象的值，不能用来进行列表初始化。也就是说花括号可以用来列表初始化，也可以用来构建vector对象，但是圆括号只能用来构建vector对象。

vector添加元素

直接初始化的方式适用于三种情况：

1. 初始值已知，且数量较少
2. 初始值是另一个vector对象的副本
3. 所有元素的初始值都一样。

而当我们并不知道vector中有几个元素，元素的值也不知道的时候，就不适用直接初始化了，这个时候需要调用vector的成员函数push_back向其添加元素。

vector的最大优势是运行时能够高效的添加元素，它的容量能够在不够的时候，高效的增长，这样子在定义vector对象时设定大小没有太大的意义。只有一种情况，就是所有的元素值都一样的时候，指定vector的大小和初始值。否则更建议定义空的vector，然后向其中添加具体的而值。

vector对象的操作

1. vector的大小
2. 向vector添加新的元素
3. 下标[]只能用于访问元素，不能用于添加元素。通过下标访问超出vector范围的元素的行为非常常见，这种错误叫做缓冲区溢出。

弦割法

参考文献

1.http://www.math.drexel.edu/~tolya/300_secant.pdf

概念

• **时钟。**存储设备都是由同一个时钟控制的，时钟是一个周期性信号，决定什么时候把新值加载到设备中。

处理器体系结构

Y86-64指令集体系结构

逻辑设计和硬件控制语言

逻辑门

组合电路和HCL布尔表达式

字级的组合电路和HCL整数表达式

集合关系

存储器和时钟

存储设备都是由同一个时钟控制的，时钟是一个周期性信号，决定什么时候把新值加载到设备中。

Y86的顺序实现

将处理组织成阶段

处理一条指令通常包含很多操作。将它们组织成某个特殊的阶段序列，即使指令的动作差异很大，但所有的指令都能遵循统一的序列。每一步的具体处理处决于正在执行的指令。创建这样一个框架，能够设计一个充分利用硬件的处理器。下面是关于各个阶段以及每个阶段内执行操作的简略描述：

• 取指
• 译码
• 执行
• 访存
• 写回
• 更新PC

处理器无限循环，执行这些阶段。执行一条指令的时候，我们不仅必须执行指令所表明的操作，还必须计算地址，更新栈指针，以及确定下一条指令的地址。
我们的目标是把所有的指令都放入到这个通用框架中，

流水线的通用原理

流水线化的一个重要特性是提高了系统的吞吐量(throughput)，但是会稍微增加延迟(latency)。

计算流水线

流水线操作的详细说明

流水线的局限性

带反馈的流水线系统

参考文献

1.《CSAPP》

物理和虚拟寻址

计算机系统的主存被组织成一个由M个连续的字节数组，每字节都有一个唯一的物理地址。物理寻址：CPU使用物理地址访问主存。
早期PC使用物理寻址，现代处理器使用虚拟寻址。通过虚拟寻址，CPU通过一个虚拟地址访问主存，这个虚拟地址在送到内存前被转换成适当的物理地址。实现地址翻译的是内存管理单元(MMU)。

地址空间

地址空间是一个非负整数地址的集合，如果地址空间是连续的，叫做线性地址空间。
带有虚拟内存的系统，CPU从一个有N个地址的地址空间中生成虚拟地址，这个地址空间称为虚拟地址空间：{0,1,…, N-1}，N一般是2的n次幂（n为32或者64)，也叫做n位地址空间。
这个系统还需要还有一个物理地址空间，对应系统中物理内存的M个字节：{0,1,…,M-1}。M不要求是2的幂，但是一般假设M是2的m次幂。

地址空间区分了数据对象（字节）和它们的属性（地址）。允许每个数据对象有多个独立的地址，比如主存中的每个字节可能有一个虚拟地址，也有一个物理地址。

虚拟内存作为缓存的工具

虚拟内存可以用来缓存更大的虚拟地址空间的页面。
从概念上而言，虚拟内存被组织为一个由存放在磁盘上的N个连续的字节大小的单元组成的数组。每个字节都有一个唯一的虚拟地址，作为数组的索引。磁盘上数组的内容被缓存在主存中。
虚拟内存系统将虚拟内存分割成虚拟页(VP)，虚拟页存储在磁盘上。物理内存被分割成物理页(PP，也叫页帧)，物理页缓存在DRAM上。他们的大小都为P字节。

虚拟页面的集合被分为三个不相交的子集：

1. 未分配的。虚拟内存系统还没有创建或者分配的页，未分配的块没有任何数据和他们相关联，也就不占用磁盘空间。
2. 缓存的。已经缓存在物理内存中的已分配页。
3. 未缓存的。未缓存在物理内存中的已分配页。

DRAM缓存的组织结构

DRAM缓存表示虚拟内存系统的缓存，它在主存中缓存虚拟页。
SRAM缓存表示CPU和主存之间的L1, L2, L3高速缓存。
DRAM缓存的不命中率要比SRAM中的不命中昂贵的多，因为DRAM不命中，需要磁盘提供服务，而SRAM不命中需要DRAM提供服务。而DRAM比SRAM慢10倍，而磁盘比DRAM慢10万倍。而且从磁盘的第一个扇区读取第一个字节的时间开销比起读这个扇区中的连续字节要慢10万被。
因为大的不命中处罚和访问第一个字节的开销，虚拟页往往很大，通过是4KB到2MB。由于大的不命中处罚，DRAM缓存是全相连的，任何虚拟页都可以放置在任何物理页中。

页表

页表是一个数据结构，它和操作系统，MMU（内存管理单元中的）地址翻译硬件，一起提供了虚拟页的缓存的查找（当前虚拟页是否缓存在某个物理页中）和替换（如果不在替换哪个）等。
页表是一个常驻的主存，它是一个页表条目(page table entry)的数组，虚拟地址空间中的每个页在页表中都有一个PTE。假设PTE是由一个有效位和n位地址空间组成的，如果设置了有效位，地址指向物理页的起始位置，如果没有设置有效位，地址指向虚拟页在磁盘上的起始位置。

页命中和缺页

DRAM缓存不命中称为缺页page fault，命中叫做页命中。

1. 如果想要读取某个字，地址翻译硬件根据虚拟地址查找页表，然后找到一个页表项
2. 如果页表项标记当前页被缓存了，地址翻译硬件根据PTE中的物理内存地址构造这个字的物理地址，返回。
3. 如果页表项标记当前页没有被缓存，触发缺页异常，调用内核的缺页异常处理程序，选择一个物理页中的内存进行替换。
   替换的内容：将替换页的更新写入磁盘，以及将替换页的页表条目更新为没有缓存。将访问页从磁盘复制到主存，更新该页相应的页表项。异常处理程序返回时会重新启动导致缺页的指令，这个指令把缺页的虚拟地址重新发送到地址翻译硬件。接下来就相当于执行步骤2。

页面调度（交换）是指在磁盘和内存之间传送页的活动。
直到有不命中发生时，才进行页面调入（换入）和页面调出（换出）的策略叫做按需页面调度。

分配页面

比如调用malloc就会触发分配页面的操作：在磁盘上分配空间，然后它们映射到物理内存中的物理页面，并更新相应的页表项。

局部性和抖动

局部性使得虚拟内存的性能很好。尽管在整个运行过程中引用的不同页面总数可能超过物理内存的大小，但是局部性保证了在任意时刻，程序趋向于在一个较小的活动页面集合上工作，这个集合叫做工作集或者常驻集合。
不过，当工作集的大小超过物理内存的大小时，就会发生抖动（即页面不断的被换进换出）。

虚拟内存作为内存管理的工具

操作系统为每个进程都提供了一个独立的页表，也就是一个独立的地址空间。多个虚拟页面可以映射到同一个物理页面。
按需页面调度和独立的虚拟地址空间结合，有很多好处：

1. 简化链接。
2. 简化加载。
3. 简化共享。
4. 简化内存分配。

虚拟内存作为内存保护的工具

虚拟内存通过在页表项中添加SUP，READ，WRITE等字段，控制进程的权限。设置SUP位，表示只有内核进程可以访问页面，否则就没有权限。
违反了条件，就会触发Segmentation fault。

地址翻译

形式上来说，地址翻译是一个N元素的虚拟地址空间(Virtual Adress Space)中的元素和一个M元素的物理地址空间(Phicias Adress Space)中元素之间的映射。
一个n位的虚拟地址空间包含两部分：
- 一个是n-p位的虚拟页号(Virtual Page Number, VPN)，
- 一个是p位的虚拟页面偏移(virtual page offset, VPO)。
一个物理地也包含两部分：
- 一个是m-p位的物理页号(Phicial Page Number, PPN)，
- 一个是p位的物理页面偏移(phisical page offset, VPO)。
物理和虚拟页面都是p位的，VPO和PPO是相同的。
CPU的页表基址寄存器（Page table base register, PTBR)指向当前页表。
将虚拟页号加上页表基址寄存器中的页表初始偏移，找到这个虚拟页对应的物理页号，然后将物理页号和虚拟地址中的页面偏移相结合生成物理地址。

结合高速缓存和虚拟内存

利用TLB加速地址翻译

就是一个快表，一个小的页表。

多级页表

如果只用一个单独的页表进行地址翻译，假设是32位的地址空间，4KB的页面，4字节的PTE，那么即使进程只使用了虚拟地址空间中很小的一部分，也总是需要一个4MB的页表在内存中，对于64位的更严重。为什么一定需要这么多，因为是线性寻址的。
一级页表
VP 1
VP 2
…
VP 1M
总共需要1M个页表，也就是4M内存。

可以使用多级页表来解决这个问题，比如说使用4KB的页表，4字节的PTE，1K个一级页表，1K个二级页表。
VP 1
VP 2
…
VP 1K
总共有1K个一级页表
如果一个一级页表的PTE是空的，那么对应的二级页表就不会被创建。
只有以及页表才是常驻内存的，对于二级页表，只有在需要时才创建，减少了主存压力。

Linux虚拟内存系统

一个linux进程的虚拟内存分为两部分：
一个是内核虚拟内存，一个是进程虚拟内存。
内核虚拟内存分为对每个进程一样的和每个进程不一样的。每个进程都一样的是一些系统共享的资源，比如物理内存和内核代码和数据。还有一些是内核用来区分每个进程的，包括：

1. task_struct，包含PID，指向用户栈的指针，可执行目标文件的名字和程序计数器。其中还包含一个mm_struct。
2. mm_struct，这个结构体描述了虚拟内存的当前状态，其中有两个字段：
   • pgd，pgd指向第一级页表的基址。
   • mmap，而mmap指向一个vm_area_structs的链表，其中每个vm_area_structs都描述了当前虚拟地址空间中的一个区域。每一个具体的vm_area_struct都包含以下的字段：
     • vm_start，这个area的起始地址
     • vm_end，这个are的结束
     • vm_prot，这个区域内虚拟页的读写权限。
     • vm_flags，这个区域内的页面是与其他进程共享的，还是这个进程私有的。
     • vm_flags，指向链表中的下一个area。
3. page table
4. 内核栈

进程虚拟内存就是我们常说的那些代码段，堆栈段，数据段等。

内存映射

Linux通过将一个虚拟内存区域和磁盘上的对象关联起来，初始化这个虚拟内存区域中的内容，这个过程叫做内存映射(memory mapping)。

再看共享对象

再看fork函数

调用fork函数时，内核为新进程创建一个各种各样的数据结构，并给他分配一个唯一的PID，为了给这个进程创建虚拟内存，它创建了当前进程的mm_struct，area_struct和页表的副本。他讲两个进程中的每个页面都标记为只读，并将两个进程中的area_struct都标记为私有的copy on write。
当fork在新进程返回时，新进程的虚拟内存和调用fork之间进程的虚拟内存相同。当这两个进程中的任意一个进程写操作的时候，COW就会创建新页面。因此，也就为每个进程保持了私有地址空间。

再看execve函数

execve在用新的程序替换当前的程序时，包含以下的过程：

1. 删除已存在的用户区域。
2. 映射私有区域。
3. 映射共享区域。
4. 设置程序计数器。

动态内存分配

malloc和free

为什么要使用动态内存分配

分配器的要求和目标

碎片

实现问题

隐式空闲链表

放置已分配的块

分隔空闲块

获取额外的堆内存

合并空闲块

带边界标记的合并

实现一个简单的分配器

显式空闲链表

分离的空闲链表

垃圾收集

基本知识

Mark和Sweep垃圾收集器

C程序的保守Mark和Sweep

C中常见的内存相关错误

发生segment fault的情况[2]：

1. 解引用空指针。
2. 访问只读的内存地址。比如数据段中的字符串。
3. 栈溢出。函数循环引用。
4. 访问系统保护的内存地址。比如说把100当做地址。

怎么调试segment fault？

1. 使用printf调试。。。
2. 使用gdb调试，使用场景，可复现的错误。需要生成调试信息。
3. 使用core文件。core文件是一个加了调试信息的内存映像[3]。怎么样调试一个core文件，两种方法：
   • gdb -c core
   • gdb a.out core ，这里a.out是产生这个core文件的程序。
     为什么没有产生core文件，linux为一些文件设置了大小，ulimit(1)可以查看这些大小限制，core文件一般是0，所以就看不见了，可以使用ulmit -c 1024设置core文件的大小为1024字节。
     这种方法可以不用重新运行程序。
4. 使用dmesg找到发生错误的位置，然后使用objdump反汇编。

解引用坏指针

进程的虚拟地址空间中有较大的洞，没有映射到有意义的数。如果不小心使用了这些这些，就可能会发生segment fault，但是如果没有发生的话，更难被发现。

读取未初始化的内存

比如说，堆内存没有被显式初始化，解引用这些指针，就会发生错误。

允许栈缓冲区溢出

如果往栈中分配的临时数组写入的数据量超过了它的容量，就会发生溢出。

假设指针和它们指向的对象是相同大小的

指针的大小是不变的，在一台机器上都是确定的。

数组越界

数组越界。

引用指针，而不是它所指向的对象

对指针进行了操作，而不是对指针指向的对象进行操作。

误解引用指针

指针运算是以它们指向对象的大小为单位进行的。

引用不存在的变量

引用局部变量。

引用空闲堆块中的数据

引用被释放了的堆中的内存。

引起内存泄露

没有调用free释放内存。

参考文献

1.《CSAPP》
2.https://blog.csdn.net/qq_33249383/article/details/79483212
3.https://www.cnblogs.com/dongzhiquan/archive/2012/01/20/2328355.html
4.https://manybutfinite.com/post/how-the-kernel-manages-your-memory/

存储技术（storage technologies）

随机访问存储器（Random Acess Memory）

静态RAM(SRAM)

动态RAM(DRAM)

传统的DRAM

内存模块

其他DRAM

• Fast page mode DRAM (FPM DRAM)
• Extended data out DRAM (EDO DRAM)
• Synchronous DRAM (SDRAM)
• Double Data-Rate Synchronous DRAM (DDR SDRAM)
• Video RAM (VRAM)

非易失型存储器

• 只读存储器,Read-Only Memory (ROM)
• 可编程只读ROM, Programmable PROM (PROM)
• 可擦写可编程ROM, Erasable Programmable ROM (EPROM)
• Eletrically Erasable PROM (EEPROM)

访问主存

局部性(locality)

存储器层次结构

高速缓存存储器

通用的高速缓存存储器组织结构

直接映射高速缓存

组相连高速缓存

全相连高速缓存

高速缓存对程序性能的影响

参考文献

1.《CSAPP》

Intel x86由来

Intel处理器俗称x86。Intel处理器系列有好几个名字，包括IA32，也就是"Intel 32位体系结构（Intel Architecture 32-bit）"，以及最新的Intel 64，即IA32的64位扩展，也称为x864-64。最常用的名字是"x86"，我们用它来代指整个系列，也反映了直到i486处理器命名的惯例。

数据传送指令

参考文献

操作系统的功能

1. 处理器管理
2. 存储管理
3. 设备管理
4. 文件管理
5. 作业管理

参考文献

程序的机器级表示

Intel x86由来

Intel处理器俗称x86。Intel处理器系列有好几个名字，包括IA32，也就是"Intel 32位体系结构（Intel Architecture 32-bit）"，以及最新的Intel 64，即IA32的64位扩展，也称为x864-64。最常用的名字是"x86"，我们用它来代指整个系列，也反映了直到i486处理器命名的惯例。

程序编码

程序计数器(program counter)，通常称为PC，在x86-64中用%rip表示。

机器级代码

汇编代码格式

数据格式

因为是从16位体系结构扩展成32位的，Intel用术语字表示16位数据类型。用双字（double words）表示32位数据类型。用四字（quad words）表示64位数据类型。指针存储为8字节的四字。
以下是C语言类型在x86-64中的大小：

大多数GCC生成的汇编代码中都有一个字符的后缀，表明操作数的大小。比如数据传送指令的四个变种：
movb传送字节，movw传送字，movl传送双字，movq传送四字。后缀’l’表示双字，因为32位数被看成是长字（long word）。

信息访问

通用目的寄存器寄存器

一个x86-64的CPU提供了一组16个64位的通用目的寄存器，这些寄存器用来存储整数数据和指针（地址）。如下所示是这16个寄存器：

它们的名字都以%r开头，但是后面还跟着一些其他命名规则的名字，这是指令集历史演化造成的：

1. 最初的8086有8个16位寄存器，即%ax到%bp；
2. 扩展到IA32架构时，寄存器也扩展成32位寄存器，标号从%eax到%ebp
3. 扩展到x86-64后，原来的8个寄存器扩展成64位，标号从%rax到%rbp，此外，还增加了8个新的寄存器，它们的名字是%r8到%r15。

指令可以对这16个寄存器中的数据进行操作。字节级指令可以访问最低的字节，16位操作可以访问最低的16个字节。32位操作可以访问最低的32个字节，64位操作可以访问整个寄存器。
当指令以寄存器为目标时，对于生成小于8字节结果的指令，寄存器剩下的值该怎么变，有两条规则：

1. 生成1字节和2字节数字的指令会保持剩下的字节不变。
2. 生成4字节数字的指令会把高位4个字节置为0。

操作数寻址指令

大多数指令都有一个或者多个操作数，指示执行一个操作中要使用的源数据之，以及放置结果的目的位置。x86-64支持三类操作数格式：立即数，寄存器和内存引用。如下图所示：

1. 立即数。 在ATT格式的汇编代码中，立即数的写法是$后面跟一个标准C表示的整数。如$-144, $0xFF。
2. 寄存器。将寄存器集合看成一个数组R，用寄存器标识符作为索引，如R[%rax]。
3. 内存引用。根据计算出来的地址访问某个内存位置，将内存看成一个很大的字节数组，用符号Mb[Addr]表示对存储在内存中的地址Addr开始的b个字节的引用，通常省略下标b。内存引用有不同的寻址方式，如上图所示，后面9种都为内存引用，对应不同的寻址方式。

数据传送指令

将数组从一个位置复制到另一个位置的指令叫做数据传送指令。为了方便，把不同的指令划分为指令类，每一类中的指令执行相同的操作，只不过操作数大小不同。

x86-64加了一条限制，传送指令的两个操作数不能都指向内存位置。

MOV类

MOV类包含四条指令：movb, movw, movl, movq。它们把数据从源位置复制到目的位置。

MOV类指令的约束如下：

1. 源操作数指定的值是一个立即数，存储在寄存器中或者内存中
2. 目的操作数指定一个位置，要么是一个寄存器，要么是一个内存地址。
3. x86-64加了一条限制，传送指令的两个操作数不能都指向内存位置。
4. 大多数情况下，MOV指令只会更新目的操作数指定的那些寄存器字节或者内存位置。唯一的例外是movl指令以寄存器作为目的时，它会把寄存器的高位4字节设置为0，这里x86-32采用的惯例，任何为寄存器生成32位值的指令都会把该寄存器的高位部分置为0。
5. movq和movabsq的区别。moveq指令只能以表示为32位补码的立即数作为源操作数，然后把这个值符号扩展得到64位的值，放到目的位置。而movabsq指令能以任意64位立即数值作为源操作数。

MOVZ和MOVS类

MOVZ和MOVS类在将较小的源值复制到较大的目的位置时使用，它们都将数据从源（寄存器或者内存中）复制到目的寄存器。MOVZ中的指令把目的位置中剩余的位置填充为0，而MOVS通过符号扩展进行填充。如下图所示。

1. 每条指令名字的最后两个字符都是大小指示符：第一个字符指令源的大小，第二个字符指明目的的大小。注意在movz中，没有movzlq指令，这个指令不需要存在。因为，movl为寄存器生成32位值的指令时会把寄存器的高位部分置为0。
2. cltq指令没有操作数，它总是以寄存器%eax作为源，%rax作为符号扩展结果的目的。它的效果与指令movslq %eax, %rax完全一致。

压入和弹出栈数据

push操作可以把数据压入栈中，pop操作删除数据。栈指针%rsp保存着栈顶元素的地址。

pushq将一个四字值压入栈中，比如pushq %rsp相当于以下两条指令：

1
2

subq $8, %rsp
movq %rbp, (%rsp)

只不过pushq指令编码为1个字节，而上面两条指令编码为8个字节。
同理popq从栈中弹出一个四字，popq %rax相当于以下两条指令：

1
2

movq (%rsp), $rax
addq $8, %rsp

算术和逻辑操作

算术和逻辑操作可以分为四组，加载有效地址，一元操作，二元操作和移位。除了leaq外，所有的指令类都有四种不同大小数据类型的指令（字节，字，双字，四字）。它们的指令格式如下表所示：

加载有效地址

加载有效地址(lead effective address)指令leaq其实就是movq指令的变形。它的指令形式是从内存读数据到寄存器，但是它根本没有使用到内存，这个指令并不是从指定的位置读入数据，而是将源数据的有效地址写入到目的操作数。
此外，leaq还可以进行简普通的算术操作。比如，如果寄存器%rdx的值为x，指令leaq 7(%rdx, %rdx, 4), %rax设置寄存器的值为5x+7。

一元和二元操作

一元操作的源操作数和目的操作数是一样的，这个操作数可以是一个寄存器，也可以是一个内存位置。

二元操作的第二个操作数既是源操作数又是目的操作数。

移位操作

最后一组操作是移位操作，它的操作数有两个，第一个是移位量，它可以是一个立即数，也可以是存放在单字节寄存器%cl中的一个数值，只允许以这个特定的寄存器为操作数。第二个操作数是要移位的数。

移位操作分为算术移位和逻辑移位。而每种移位又可以分为左移和右移。算术左移和逻辑右移是一样的，都是用0来填充右面的位。而算术右移和逻辑右移不同，算术右移使用0填充左边，而逻辑左移使用最高位的符号位填充。

128位乘除法

两个64位有符号数或者无符号整数相乘得到的乘积需要128位，x86-64指令集对128位数的操作提供有限的支持。延续字，双字，四字，Intel把16字节（128位）的数叫做八字。如下所示：

128位乘法

imulq指令有两种不同的形式。一种接受两个操作数，一种接受一个操作数。前面介绍的imulq是接受双操作数的指令，这里介绍的两个mulq和imulq是两条不同的单操作数乘法指令，计算两个64位值的128位乘积，一个是无符号乘法，一个是补码乘法。这两条指令都要求一个参数必须在寄存器%rax中，另一个作为指令的源操作数给出，乘积存放在寄存器%rdx（高64位）和%rax（低64位）中。

128位除法

除法是由单操作数指令提供的。有符号除法指令idivl将寄存器%rdx（高64位）和%rax（第64位）中的128位作为被除数，而除数作为指令的操作数给出。指令将商存放在%rax中，余数存储在%rdx中。
通常情况下来说，除法的被除数通常也是64位的，这个值应该存放在%rax中，而%rdx应该置为0或者是%rax的符号位。可以使用cqto指令完成将%rax置为%rax的符号位，这条指令不需要操作数，默认读出%rax的符号位，并将它复制到%rdx的所有位。如果是无符号64位除法，不能使用cqto，需要使用movl $0, %edx，为什么不是movq $0, %rdx，因为movl能自动的将%rdx的高位4个字节置为0。

控制

条件码

x86 CPU维护了四个条件码：

• CF：进位标志。最近的操作使得最高位产生了进位，检测无符号操作的溢出。
• ZF：零标志。最近的操作得出的结果为0。
• SF：符号标志。最近的操作得到的结果为负数。
• OF：溢出标志。最近的操作导致一个补码溢出－正溢出或者负溢出。

leaq指令不会改变任何条件码，因为它是用来进行地址计算的。所有上一节介绍的算术和逻辑指令都会设置条件码。

访问条件码

条件码不会直接被读取，通常是在使用CMP指令类或者TEST指令类设置条件码之后，通常的使用方法有三种：

1. SET指令类根据条件码的某种组合，将一个字节设为0或者1。
2. 跳转指令类无条件或者条件跳转到程序的某个其他部分。
3. 可以有条件的传送数据。

CMP指令类和TEST指令类

CMP和TEST指令类只设置条件码而不改变任何寄存器。
除了CMP只设置条件码而不更新目的寄存器，CMP和SUB指令是一样的。
除了TEST只设置条件码而不改变目的寄存器的值，TEST指令类的行为和AND指令是一样的。

SET指令类

SET指令类根据条件码的某种组合，将一个字节设置为0或者1，不同的SET指令之间的区别就在于它们考虑的条件码的组合是什么，指令名字的后缀指明了它们所考虑的条件码的组合。
一条SET指令的目的操作数是低位单字节寄存器，或者一个字节的内存位置，SET指令将这个字节设置成0或者1。为了得到一个32位或者64位的结果，必须对高位清零。

跳转指令类

正常情况下，指令按照它们出现的顺序一条一条的执行。跳转指令会导致执行切换到程序中一个全新的位置。在汇编代码中，这些跳转的目的地通常用一个label指明。下面是两类不同的跳转指令：

1. **无条件跳转指令。*汇编语言中，直接跳转是给出一个label作为跳转目标的；间接跳转是’'号后面跟一个操作数指示符，如jmp *%rax，是内存操作数格式的一种。jmp是无条件跳转，它可以是直接跳转，也可以是间接跳转。
2. **条件跳转指令。**所有其他跳转指令都是有条件的，它们根据条件码的某种组合，进行跳转或者继续执行下一条指令，这些指令的名字和跳转指令的名字和设置条件是匹配的。条件跳转只能是直接跳转，不能是间接跳转。

跳转指令的编码

在汇编代码中，跳转目标用符号label书写。汇编器和链接器会产生跳转目标的适当编码。
跳转指令有几种不同的编码：

1. 最常使用的是PC相对(PC-relative)，它们会将目标指令的地址与紧跟在跳转指令后面的那条指令的地址之间的差作为编码（目标指令地址-跳转指令下一条的地址），在使用的时候，把下一条指令的地址加上PC相对量就得到了目标指令的地址。这些地址偏移量可以编码为1,2或者4个字节。
2. 第二种编码方式是给出绝对地址，用4个字节直接指定目标。

汇编器和链接器会选择适当的跳转目的编码。

条件控制实现条件分支

C语言中的if-else语句通用模板如下：

1
2
3
4
5
6
7
8

if(test-expr)
{
    then-statement
}
else
{
    else-statement
}

汇编实现通常如下所示（C语法表示）：

1
2
3
4
5
6
7
8

    t = test-expr;
    if(!t)
        goto false;
    then-statement;
    goto done;
false:
    else-statement
done:

汇编器会为then-statement和else-statement产生各自的代码块。即汇编器会插入条件和无条件分支，保证执行正确的代码块。　
还可以有另外一种实现：

1
2
3
4
5
6
7
8

    t = test-expr;
    if(t)
        goto true;
    else-statement
    goto done;
true:
    then-statement;
done:

条件传送实现条件分支

除了控制的条件转义，还有数据的条件转移。它只能用在部分情况下，但是如果可以使用的话，就比较简单。
下图列出了x86-64的一些条件传送指令：

考虑以下条件表达式：

1

v = test-expr? then-expr: else-expr;

如果使用条件控制编译，通常会得到如下形式：

1
2
3
4
5
6
7

    if(!test-expr)
        goto false;
    v= then-expr;
    goto done;
false:
    else-expr;
done:

条件传送和条件跳转的区别。而条件跳转必须预测test的结果提高流水线的效率，如果预测错了，效率会很低。比如处理器预测test-expr结果为真，就会只执行then-expr的部分，如果预测错了，即它就得重新计算else-expr的部分。
对于条件传送来说，处理器不预测test的结果，它对if-expr和else-expr中的片段都进行求值，然后再根据计算出来的两个结果，选择是否进行条件传送。
条件传送的问题，需要对if-expr和else-expr都进行求值，如果它们冲突了，就会产生错误。而且如果它们的计算量都很大的时候，就会产生大量浪费的计算。对于GCC来说，通常当它们都很容易计算时，才会使用条件传送。

循环

do-while循环

C语言的do-while语句如下：

1
2
3

do
    body-statement
    while(test-expr);

翻译成汇编语言（C语言形式）如下：

1
2
3
4
5

loop:
    body-statement
    t = test-expr;
    if(t)
        goto loop;

while循环

while循环有两种方式，一种相当于在do-while的前面加一个goto语句直接跳转到do-while的test-expr部分，另一种相当于直接在do-while前再加一个执行一次的test-expr，进行第一次条件判断，其实都一样。
C语言的while语句如下：

1
2

while(test-expr)
    body-statement;

翻译成汇编语言（C语言形式）如下：

1
2
3
4
5
6
7
8

    goto ;
loop:
    body-statment

test:
    t = test-expr;
    if(t)
        goto loop;

或者还可以用do-while表示while：

1
2
3
4
5
6
7

t = test-expr;
if(!t)
    goto done;
do
    body-statement
while(test-expr);
done:

翻译成汇编语言（C语言形式）如下：

1
2
3
4
5
6
7
8
9

t = test-expr
if(t)
    goto done;
loop:
    body-statement
    t = test-expr;
    if(t)
        goto loop;
done:

for循环

C语言for循环的形式如下：

1
2

for(init-expr; test-expr; update-expr)
    body-statement

C标准规定（除了含有continue语句的for循环），for循环的行为和下列while的行为是一样的：

1
2
3
4
5
6
7
8

init-expr;
while(test_expr)
{
    body-statement
    //if(i & 0x1)
    // continue;
    update-expr;
}

GCC为for循环产生的代码就是while循环两种中的一个，具体是哪一个取决于优化等级。
如果直接将含有continue语句的for循环修改成while语句，会陷入死循环，因为它无法执行update-expr操作，continue语句属于body-statement部分，可以看上面的代码块中的注释部分，所以需要额外使用goto语句使其跳转到update-expr部分。

switch语句

switch处理多种可能结果的测试，通过使用跳转表可以提高效率，使得执行switch语句的时间和switch的数量无关，一个跳转表可以线性时间跳转到任何一个switch分支。
如果忘了做一道题就OK了。

Procedures

Procedures（过程）是一种抽象，其实就是C/C++ 中的函数，Java的方法，还有子例程(subroutine)，处理函数(handler)等。
机器级的procedures，需要处理不同的属性，为了方便，假设过程P调用过程Q，过程Q执行完返回到过程P。这个过程包括下面一个或者多个部分：

• 传递控制。进入过程Q的时候，PC(%rip)被设置为Q的代码的起始地址，并且将返回地址（调用指令后面的那条指令地址）压入栈中。返回过程P时，弹出返回地址，并将PC设置为返回地址。
• 传递数据。过程P向过程Q提供一个或者多个参数，过程Q向过程P返回一个值。
• 分配和释放内存。在过程Q开始时，可能需要为局部变量分配空间；而在过程Q返回时，需要释放这些空间。

运行时栈

C语言函数（过程）调用使用了栈管理内存。如下所示：

栈从高地址向低地址增长，寄存器%rsp存放栈指针，指向栈顶元素。将栈指针减少一个适当的量可以在栈上分配空间，增加栈指针可以释放空间。
当一个函数需要的存储空间超出寄存器能够存放的大小时，就会在栈上分配空间，这部分空间称为栈帧，当前正在执行的函数的栈帧总是在栈顶。栈帧中可以存放返回地址，寄存器参变量，局部变量，向它调用的函数传递的参数等(函数通过寄存器最多可以传递6个整数，多余的哪些参数就需要通过栈帧传递）。
并不是所有的函数都有栈帧的所有部分，甚至很多函数其实不需要栈帧。比如函数的参数少于6个时，所有的参数都可以通过寄存器传递，这个时候不需要存放参数的那部分。当所有的局部变量都可以存放在寄存器中，并且该函数不会调用其他函数时，就不会创建栈帧（这个函数称为叶子过程）。

调用函数P的栈帧
参数1-n
返回地址
当前被调用函数的栈帧
保存的寄存器地址
局部变量
参数构造区

转移控制

转移控制完成的任务是函数调用和函数返回，通过call和ret指令实现这两个任务。
call由调用函数（caller）执行，call指令会将它的下一条指令的地址压入栈中，这个地址叫做返回地址，并设置PC为被调用函数的起始地址。
ret指令由被调用函数（callee）执行，从栈中将返回地址弹出，并设置PC为返回地址。

传递参数

函数可能需要传递参数，并且可能有返回值。x86-64中可以通过6个寄存器传递参数：

超过6个的需要使用寄存器传递，假设调用函数需要传递n个整数参数给被调用函数，需要在栈帧中分配第7-n个参数的空间，参数7位于调用函数(caller)栈帧的底部，也是栈顶（因为还没有调用callee，所以也就没有它的栈帧）。
通过栈传递参数时，需要使用8字节对齐（32位的机器）。

栈上的局部数据

当满足以下情况时：

1. 寄存器不足够存放所有的本地数据；
2. 对于一个局部变量使用&符号，因为需要能够为它产生一个地址；
3. 某些局部是数组或者结构，因此需要通过数据或者结构引用被访问到。

如果需要分配空间，先通过减少栈指针分配空间，然后在ret前增加栈指针回收空间。

寄存器存储局部数据

寄存器是唯一被所有函数（过程）共享的资源。为了保证函数调用发生时，被调用函数不会覆盖调用函数(caller)中的寄存器值，x86-64采用了一组统一的寄存器使用惯例，所有的函数都必须遵循：
%rbx, %rbp和%r12到%r15，是被调用者负责保存的寄存器，callee需要确保这些寄存器中的值在返回caller时不会改变，callee可以不使用这些寄存器，或者将它们的值存放在栈中，等到返回时将它们的值弹出。所有其他除了%rsp的寄存器都被划分为调用者保存寄存器，所以如果一个函数使用到了这些寄存器，在它调用其他函数之前，最好把它们的值存好，因为调用函数很有可能会修改它们。

递归调用

递归调用的过程就是不断的创建栈帧的过程，这个过程确保每个函数之间不会相互干扰，正常工作（没有stackoverflow）。

数组

CSAPP中介绍的是C语言中数组的寻址：一维数组和和多维数组，变长数组的寻址。GCC在对数组的操作过程中，一般会把数组元素寻址中的乘法改成加法，提高效率。

声明一个数组并没有介绍，其实就是在函数的栈帧上分配空间或者存放在全局区。

结构和联合（union）

结构体的寻址和联合的寻址，注意对齐就行，没啥特别的吧。

对于大多数x86-64指令来说，无论对齐不对齐，对结果的正确与否都没啥影响，但是Intel还是建议对齐提高性能。对齐的原则是任何K字节的基本对象的地址都必须是K(K通常是2, 4或者8)的倍数。在汇编中，使用.align 8可以指定8字节对齐。
但是另一方面，如果数据没有对齐，某些型号的Intel和AMD处理器对于部分实现多媒体操作的SSE指令，无法正确执行，这些指令对16字节数据块进行操作，在SSE单元和内存之间传送指令的数据的指令要求内存地址必须是16的倍数。任何以不满足对齐要求的地址来访问内存都会导致程序异常。
因此，任何针对x86-64的编译器和运行时系统都必须保证分配用来保存可能会被SSE寄存器读或写的数据结构的内存，都必须满足16字节对齐。这个要求有以下两个后果：

1. 任何内存分配函数(malloc, calloc或者realloc)生成的块的起始地址都必须是16的倍数；
2. 大多数函数的栈帧的边界都需要是16字节的倍数。

最近的x86-64处理器实现了AVX多媒体指令，除了提供SSE指令的超集，支持AVX的指令没有强制性的对齐要求。

机器级控制和数据的交互

指针

没啥新东西。

GDB

GDB是GNU的调试器，可以用来调试C, C++和机器级程序等。下面是一些常见的调试机器级程序的选项：

数组越界和缓冲区溢出

局部变量和状态信息（返回地址和保存的寄存器值）都存放在栈中，由于C语言不对数组引用进行边界检查，这两种情况同时发生时，就可能造成缓冲区溢出。当输入超过了分配的缓冲区数组大小时，就可能会造成严重的后果，比如覆盖掉返回地址或者保存的寄存器值等等。
缓冲区溢出可能会导致网络攻击，比如输入中包含恶意代码，用指向恶意代码的指针覆盖返回地址，执行ret指令跳转到了恶意代码存放的位置。还有其他攻击的形式等等。

解决缓冲区溢出

有三种方式可以用于解决缓冲区溢出问题：

1. 栈随机化。让栈的位置在程序每次运行时都有变化。
2. 栈破坏检测。
3. 限制可执行代码区域。

变长栈帧

对于拥有变长数组的函数来说，它的栈帧不是固定的，这个时候需要使用%rbp(base pointer)而不是%rsp作为栈指针进行管理。

浮点运算

浮点指令的发展，从SIMD到MMX，到SSE，以及最新的AVX，AVX2。这些指令都管理寄存器组中的数据，这些寄存器组在MMX中称为MM寄存器，SSE中称为XMM寄存器，AVX中称为YMM寄存器。MM是64位的，XMM是128位的，YMM是256位的。
浮点数拥有一套自己的操作：

1. 浮点传送和转换指令；
2. 浮点数的算术运算指令；
3. 浮点数的位运算指令；
4. 浮点数的比较运算指令。

参考文献

1.《CSAPP》

程序的执行过程

helloworld.c程序的生命周期是从一个ASCII码形式（文本文件）的源文件开始的，这种形式能被人读懂。
然后经过编译器驱动程序将它转换为一系列机器语言指令，按照一种称为可执行目标程序（可执行目标文件）的方式打包，以二进制磁盘文件的形式存放起来。
然后我们可以运行一个程序，即上面的二进制可执行程序，操作系统通过操作各种硬件资源执行该程序。

程序翻译过程

编译器驱动程序通过调用预处理器，编译器，汇编器和连接器，并进行其他各项需要的工作，将源程序文本文件，翻译成一个可执行文件。整个翻译过程可以分为四个阶段：

1. 预处理阶段。预处理器cpp根据以字符#开头的命令，修改原始程序，得到一个以.i为文件扩展名的另一个c程序。
2. 编译阶段。编译器cc1将.i文件翻译成以.s为扩展名的文本文件，它是一个汇编语言程序。每条汇编语句都用一种文本格式描述了一条低级机器语言指令，汇编语言为不同高级语言的编译器提供了通用的输出语言。
3. 汇编阶段。汇编器as将.s为扩展名的汇编程序翻译成机器语言指令，并且将他们打包成一种可重定位目标程序（relocatable object program）的格式，得到一个以.o为扩展名的二进制目标文件。
4. 链接阶段。链接器ld将各种代码和数据片段（包括调用的库函数的目标文件，以及可重定位目标文件等）收集并组合成一个单一文件的过程，这个文件可以被加载到内存并执行。

在这个过程中编译器驱动调用的调用的四个程序，即预处理器，编译器，汇编器和链接器，构成一个编译系统。而编译器驱动程序负责的是整个流程，什么时候自动的调用某个程序，并完成相应资源等的调度。

操作系统和硬件

我们可以把操作系统看成应用程序和硬件之间的一层软件。所有应用程序对于硬件的操作尝试都必须通过操作系统。
操作系统可以防止硬件被失控的应用程序滥用，还可以向应用程序提供简单一致的机制来控制复杂而又通常大不相同的低级硬件设备。操作系统通过几个基本的抽象概念：进程，虚拟内存和文件等，实现了这两个功能。

1. 进程是对处理器，主存和I/O设备的抽象表示。进程是操作系统对一个正在运行的程序的一种抽象。在一个系统上可以同时运行多个进程，并且每个进程看起来都在独占的使用硬件。并发运行指的是一个程序的指令和另一个进程的指令是交错执行的。在单核CPU上，同一时刻只能执行一个程序，而多核CPU在一个时刻可以同时执行多个程序。对于每个CPU（无论单核还是双核）来说，系统通过上文件切换可以实现多个进程的执行。
   线程。
2. 虚拟内存是对主存和I/O设备的抽象表示。它为进程提供了一个抽象，假设所有进程都在独占的使用内存，每个进程看到的内存都是一致的，称为虚拟地址空间。
3. 文件是对I/O设备的抽象表示。文件就是字节序列。每个I/O设备，磁盘，键盘，显示器，网络，等等，都可以看成是文件。系统中所有的输入输出都是通过UNIX I/O系统调用函数，如open, fopen等等实现的。它向应用程序提供了一个统一的视角看待系统中所有各式各样的I/O设备。

参考文献

1.《CSAPP》第五版

计算机系统

从机器的角度来看，程序仅仅是字节序列。

总线和字

• 总线。贯穿整个系统的一组电子管道，它携带信息字节并负责在各个部件之间传递。通常总线被设计成传送固定的字节块，也就是字。字中的字节数也就是字长，是一个基本的系统参数。总线包括系统总线，I/O总线，内存总线等。
• 字节，八位的位序列块，最小的可寻址内存单位。
• 字，总线传送的固定的字节块。
• 字长，字中的字节数。一个字长为w位的机器，虚拟地址的范围从0到$2^w -1$。

地址和虚拟内存

• 机器程序的虚拟内存，机器级程序将内存看成一个非常大的字节数组，称为虚拟内存。
• **（虚拟）**地址，虚拟内存的每个字节都由一个唯一的数字标示，这个数字叫做这个字节的地址。
• 虚拟地址空间，所有（虚拟）地址的集合称为虚拟地址空间。
• 大端和小端。大端，最高有效字节在最前面；小端，最低有效字节在最前面。用于跨多字节的对象，它的地址是什么，如何排列这些字节。在网络传输二进制数据时，可能会出现问题。

I/O设备

• I/O设备。输入输出设备是系统和外部世界的联系通道。常见的用户输入设备有键盘和鼠标，用户输出设备显示器，以及磁盘驱动器（磁盘）。每个I/O设备都通过一个控制器或者设配和I/O总线相连接，是适配器和控制器的功能都是在I/O总线和I/O设备之间传递信息。
• 控制器。控制器是I/O设备本身或者系统的主印制电路板上的芯片组。
• 适配器。而适配器是一块插在主板插槽上的卡。

处理器

• 处理器。中央处理单元，简称CPU，是解释（执行）存储在主存中指令的引擎。
• 程序计数器。处理器的核心是一个大小为一个字的存储设备（寄存器），称为程序计数器（PC）。在任何时刻，PC都指向主存中的某条机器指令。
• 指令集架构。处理器按照一个指令执行模型来操作，这个模型叫做指令集架构。指令集架构描述的是每条机器代码指令的效果。
• 微体系架构。微体系结构描述的是处理器是如何实现的。
• 算术/逻辑运算单元(ALU)。计算新的数据和地址值。

存储器

• 主存。
• 动态随机访问存储器
• 静态随机访问存储器
• 高速缓存存储器
• 闪存
• 磁盘存储器
• 寄存器文件。寄存器文件是一个小的存储设备，由一些单个字长的寄存器组成，每个寄存器都有一个唯一的名字。

程序和进程

• 程序。程序是一个存储在磁盘上的某个目录中的可执行文件。内核使用exec函数将程序读入内存，并执行该程序。
• 进程。程序的执行实例被称为进程(process)，是操作系统对一个正在运行的程序的抽象。
• 线程
• 并发
• 并行

运算

• 算术右移和逻辑右移。算术右移在左端补k个最高有效位的值，而逻辑右移在左端补k个0，C语言没有规定对于有符号数使用哪种右移，但是几乎所有的编译器和机器组合都对有符号数进行算术右移。对于无符号数，右移必须是逻辑右移。

机器指令和可执行文件

• 机器指令。
• 可执行目标程序(executable object program)，或者也叫可执行目标文件(executable object files)，是一种文件格式。将一系列形式机器指令以这种格式组织，然后存放成一个二进制文件。

编译器和编译器驱动程序

• 编译器，或者编译系统(compile system)。执行将源文件翻译成可执行目标文件过程的程序，即预处理器，编译器，汇编器和链接器，构成编译系统。
• 编译器驱动程序。编译器驱动程序自动的完成整个编译过程，即在需要时分别调用预处理器，编译器，汇编器和连接器，整个编译过程都是由编译器驱动程序负责的。[1,2]。
• 链接是将各种代码和数据片段收集并组合成一个单一文件的过程，这个文件可以被加载到内存并执行。
• **符号和符号表。**每一个可重定位模块m都有一个ELF符号表（.symtab)，有三种不同的符号：对应于本模块中定义的non-static的C函数和global variables的全局符号(global symbols)；对应其他模块中定义的non-static的C函数和global variables的外部符号(external symbol)；对应于C的static function和static global variables，static local variables的局部符号(local symbols)。
  每一个符号都被分配到某个section字段表示，section字段的取值还可以是在seciton header table中没有entry的三个特殊伪节(pseudosection)：UNDER表示未定义的符号, ABS表示不应该重定位的符号和COMMON表示还没有分配位置的未初始化的数据目标；对于COMMON符号，value字段给出对齐要求，size给出最小的大小。
  COMMON和.bss的区别：COMMON存放的是未初始化的全局变量，而.bss存放的是未初始化的静态变量，以及初始化为0的全局或者静态变量。
• **强符号和弱符号。**函数和已经初始化的全局变量是强符号，未初始化的全局变量是弱符号。

参考文献

1.《CSAPP》第三版
2.https://stackoverflow.com/a/58392562/8939281