OSDI24-Nomad: Non-Exclusive Memory Tiering via Transactional Page Migration Wordsadvent n. 出现accommodate v. 容纳、使适应；顾及；帮助；迎合；调解demonstrate v. 证明thrashing n. 击败, v. 抽打，这里应该是抖动的意思。 recency v. 新进，崭新。 facilitate v. 促进、推动Background分层内存系统效果比较好、现有方案通过页面迁移管理分层内存，把Hot数据放在快速内存、把溢出的Cold内存放在低速内存。在Fast memory under pressure时，性能下降很厉害，页面是独占的，即要么在快速内存，要么在慢速内存，通过迁移来交换。页面迁移总是会发生在程序的关键路径上。导致用户感知带宽降低。作者首先测试了TPP及其Baseline（不分级，完全使用慢速内存）的性能，证明了TPP发生迁移的时候会严重影响内存性能，在WSS过大时更加显著的拖慢性能。TPP认为慢速内存中的页面不可以访问，并在page fault时决定是否提升Novelty提出一种非独占的页面迁移机制，保留最近从慢内存迁移到快内存的副本，并使得迁移异步。换句话说，我认为这可能是用低速内存空间换页面迁移时间的方法。Achievement在抖动的前提下，达到SoTA的6倍性能，在不抖动时也相较于Memtis快130%.更进一步的描述成果：Hot数据 < 高速内存 ： 预热时Nomad接近Memtis，优于TPP、稳定时Nomad与TPP相近（无论读写）Hot数据 = 高速内存： 预热时Nomad接近Memtis，优于TPP、稳定时Nomad显著超过TPP，但是写时可能会不如MemtisHot数据 > 高速内存：预热时Nomad虽然劣于Memtis，但是仍然可以超过TPP，稳定时读性能显著超过Nomad，写时不如MemtisDesign首先核心思想就是Novelty中所提到的那样，使得即使是在使用分层内存的前提下，也可以同时在高低速缓存中同时保存副本（也就是传统Cache“包含”的关系）整体设计思路还是比较清晰，在不破坏现有的页面迁移决策的基础上，异步的在可能得情况下对应该进行迁移的页面进行迁移。并且极大的缩短迁移时用户被页面错误阻断的时间。当页面downgrade时，由于低速内存保留了原来的副本，如果PTE显示页面未被dirty，则直接remap即可，不需要进行一次多余的Copy当页面upgrade时，系统仍然保留原有低速内存的页表，所以用户进程就可以直接访问低速内存，同时Copy页面到高速内存，如果拷贝过程中页面被dirty，直接放弃拷贝，直到某次拷贝成功，重新remap到高速内存，并仍然保留低速内存。也因此（我理解是类似于数据库事务，copy在dirty的情况下会被rollback，直到成功再提交）这个方法被他们称为Transactional Page Migration事务性页面迁移。

CSAPP 7.链接 本章的知识在《程序员的自我修养——链接、装载与库》中都有所提到，复习为主。可能有些说法和本书不同，如段Segment和节Section，希望读者自行甄别。链接：把各种代码和数据片段组合为一个单一文件的过程，这个单一文件可以被加载到内存并执行当下的链接主要分为静态链接和动态链接，静态链接于编译时执行，动态链接由装载或运行时执行。链接的重要意义之一就是增量编译、分离版本控制。我们需要更新部件的时候无需编译其他部分1 编译器驱动程序本章将以如下两段代码作为示例// main.c int sum(int *a, int n); int arr[2] = {1, 2}; int main() { int val = sum(arr, 2); return val; } // sum.c int sum(int *a, int n) { int i, s = 0; for(i = 0; i < n; i ++) { s += a[i]; } return s; }编译器驱动程序可以理解为编译各部分的封装控制器，对于gcc：gcc -o prog main.c sum.c它首先调用预处理器cpp，把源程序c文件翻译为ASCII码中间文件i文件main.i接下来，它调用C编译器cc1，把main.i翻译为一个ASCII汇编语言文件main.s然后运行汇编器as，把main.s翻译为目标文件main.o，同样的过程生成sum.o，它们是可重定位目标文件最后运行链接程序ld，把main.o、sum.o和一些其他的系统目标文件链接起来，创建一个可执行目标文件prog我们运行prog，shell会调用操作系统中的加载器，把prog的代码和数据复制到内存，把控制转移到prog的起始2 静态链接静态链接以可重定位目标文件和参数作为输入，生成一个链接后的可执行目标文件静态链接主要完成两个任务：符号解析：目标文件中会定义和引用符号，如全局变量，跳转的label、函数，连接器把它们的定义和引用进行关联重定位：链接器重排布代码和数据段的位置，并对符号引用进行修改，使他们真正指向对应的虚拟内存位置3 目标文件目标文件主要分为三种，前两种在上面提到过了，它们是可重定位目标文件：包含二进制的代码和数据，额可以在链接时与其它可重定位目标文件合并可执行目标文件：可以直接被复制到内存并执行共享目标文件：Shared Object so，可以在加载或运行时被动态加载进内存并链接Windows下使用PE格式，Mac系统使用Mach-O格式，Linux和Unix使用ELF格式4 可重定位目标文件ELF由ELF头、段表和各段组成ELF头中包括一些关键描述信息，如字大小、ELF版本、架构、字节顺序等，还有段表的条目大小和数量，帮助我们索引段表。一个典型的ELF包含如下几个段：.text: 已编译程序的机器码.rodata: 只读数据，比如switch的jt.data: 已初始化的全局和静态变量.bss: 未初始化、初始化为0的全局和静态变量，它们在目标文件中不占实际空间.symtab: 符号表，存放引用的全局变量和函数信息（但是对执行没有影响，可以通过strip去掉）.rel.text：text中需要重定位的位置列表.rel.data: 同理.debug:调试符号表5 符号和符号表符号表包含文件定义和引用符号信息，包括如下三种：由模块定义、能被其它模块引用的全局符号，对应C的非静态函数和全局变量由其它模块定义、本模块引用的全局符号，也被称为外部符号，对应其它C文件的非静态函数和全局变量只被当前模块定义和引用的局部符号，包括static修饰的函数和全局变量，只在模块内部可见符号表存在于.symtab段，由Elf64_Symbol（显然，也会有32）数组组成typedef struct { int name; char type:4, binding:4; char reserved; short section; long value; long size; } Elf64_Symbol;name时字符串表中的字节偏移value是符号的地址，是距定义目标的setcion的起始位置的偏移size是目标的大小type区别数据和函数，binding标识符号是本地还是全局的此外还有三个特殊的伪节，在段表中不存在ABS：不该被重定位的符号UNDEF：未定义的符号COMMON：未初始化的全局变量，bss是未初始化的静态、初始化为0的全局或静态6 符号解析把每个引用与目标文件符号表中的符号定义关联起来局部符号：每个模块每个局部符号只能有一个定义，静态局部变量名字唯一全局符号：遇到不在当前模块定义的符号时，假设其它模块定义该符号，生成一个链接器符号表条目，由链接器处理6.1 多重定义的全局符号全局符号分强弱，函数和已初始化的全局变量是强符号，未初始化的全局变量是弱符号如下三条规则处理：不允许有重名强符号如果一个强符号和其它弱符号重名，选择强符号如果多个弱符号重名，随机选择一个显然，第二条和第三条规则将带来一些我们不想看到的错误，也正是由于这两条规则，才带来了bss和COMMON微小的区别，对于初始化为0或者静态变量，不会存在歧义，编译器会放在bss，对于没有初始化的全局变量，由链接器决定选择COMMON段的哪个。6.2 静态库链接编译系统提供一种机制：把相关的目标模块打包成一个文件，称为静态库，linux中后缀为.a的文件就是一系列目标模块的打包。相关库函数被编译为独立的目标模块，以供链接时使用，当用户目标文件和静态库链接时，链接器复制需要的模块来链接，这避免了程序员手动链接所有目标文件的复杂性，也避免了一次链接所有文件导致的空间浪费。举个例子，一个带printf调用的main.c，编译时gcc会自动给链接器加上libc.a的参数，ld会从libc.a中扫描到printf.o和其它printf.o引用的模块进行链接。6.3 链接器如何使用静态库链接器按顺序从左到右扫描目标文件和存档(archive, .a)文件，维护一个目标文件的结合E、一个未解析符号集合U、一个已定义符号集合D对于输入文件f，判断f是目标文件还是存档文件，如果是目标文件，添加到E，根据f修改U和D对于存档文件f，尝试匹配U中未解析符号，如果某个成员m定义了U中需要的符号，把m加到E中，修改U和D。如果完成之后，U非空，输出错误，否则合并、重定位E中的文件。注意，链接器按从左到右的顺序，意味着输入顺序很重要，库可以在命令行参数中重复，以满足依赖。7 重定位重定位以合并后的文件作为输入，为符号分配运行时地址重定位节和符号定义：相同的节进行合并，作为输出文件的对应节。将运行时的内存地址赋给对应的节和符号重定位符号引用：基于重定位条目修改所有的符号引用， 使得引用指向正确的运行时地址7.1 重定位条目汇编器生成目标文件，遇到不能确定最终地址的引用时，即生成一个重定位条目，代码的条目放在.rel.text，数据的放在.rel.datastruct { long offset; long type:32, symbol:32; long addend; }Elf64_Rela;上面这个数据结构就是重定位条目，每个条目表示一个需要重定位的引用。Elf有很多种重定位类型，我们只关心两种。offset：被修改的引用的段偏移symbol：被修改的引用指向的符号type：如何修改新的引用R_X86_64_PC32：32位PC相对地址的引用，比如call指令，PC地址是下条指令的起始地址R_X86_64_32：32位绝对地址的引用这两种类型支持“小型代码模型”，假设代码和数据的总体大小小于2G，因此可以使用32位相对地址访问。Gcc默认使用小代码模型。addend：一个常数，部分重定位需要使用它对被修改引用的值进行调整。7.2 重定位符号引用遍历需要重定位的节对于所有当前节对应的重定位条目，根据节地址和条目offset取出需要重定位代码的地址根据条目type，进入不同的分支若为相对引用，首先获取当前指令的运行时地址这里其实有点问题，取的到底是当前指令地址、当前指令的引用数据部分地址，还是下条指令的地址？根据代码的行为，我推测应该是当前指令的引用数据部分地址，再根据addend修正到下条指令的地址（事实上也是这样的）然后修改需要重定位的字节序列为符号地址+addend-当前指令运行时地址若为绝对引用，修改重定位的字节序列为符号地址+addend8 可执行目标文件对于可执行目标文件，其头部还包括了程序的入口点（Entry Point），记录了程序第一条指令的地址。程序头部表：描述可执行文件映射到内存的关系，记录了段在目标文件中的偏移、内存地址、对齐、目标文件中的段大小、内存中的段大小和访问权限（rwx）。9 可执行文件的加载shell通过execve函数调用加载器，将ELF的代码和数据从磁盘复制到内存（实际上，应该只是简单建立映射，复制的工作似乎会由访问时的页错误完成，书中可能会在后面提到）然后跳转到程序的第一条指令或者入口点。Linux程序都会有一个运行时内存镜像，其结构我们在第三章中应该介绍过了。10. 动态链接库静态库有一些缺点：静态库更新时，程序员需要显式的重新链接比如printf这种函数，会在上百个进程的text段中分别存放，造成极大的浪费在内存加载时，共享库加载到内存的任意地址，并和内存中程序链接起来。Linux中为so（shared object），Win下为DLL（Dynamic Link Lib），Mac下为dylib在给定的文件系统中，一个库只有一个so文件，所有引用该库的文件共享这个so的代码和数据（可读写的数据似乎应该是进程独立的，不知道这里书上这么说是指什么，可能是只代表只读数据）。动态链接的过程会发生在加载时、加载器首先运行动态链接器、之后再由动态链接器把控制交还应用程序11 应用程序中加载和链接共享库Linux提供了一个接口，允许程序运行时加载链接库#include <dlfcn.h> void *dlopen(const char *filename, int flag); void *dlsym(void* handle, char* symbol); int dlclose(void *handle);dlopen函数加载共享库filename，根据flag的标志决定何时进行符号解析。成功返回一个handle指针，出错为NULLdlsym根据handle和符号名字返回符号地址dlclose在共享库空闲时卸载该共享库。12 位置无关代码（每次读这块都头疼）PIC位置无关代码：可以加载而无需重定位的代码。共享库需要通过这种方式来实现“加载到任意内存位置”，因为重定位时我们需要知道符号地址，而共享库是运行时才能确定地址的。12.1 数据引用全局偏移量表GOT：这个表在数据段开始的地方，每个被模块引用的全局数据目标都会在GOT表中有一个8字节条目，加载时动态链接器重定位GOT表中的每个条目，使得它包含目标正确的绝对地址。由于代码段和数据段之间距离不变，编译器产生的代码引用GOT中的条目对数据进行间接访问。12.2 函数调用延迟绑定：把过程地址绑定推迟到低依次调用过程时。延迟绑定可以很好的避免加载时进行不必要的重定位，GNU通过GOT和过程链接表PLT实现这个机制。GOT时数据段的一部分，PLT时代码段的一部分。PLT：PLT的每个条目是16字节代码，PLT[0]跳转到动态链接器中。每个条目负责一个具体的函数在这里，GOT除了前几个为动态链接器保留的条目外，每个条目对应一个函数，也对应一个PLT条目。GOT条目初始时指向对应的PLT条目的第二条指令。PLT的一个条目是这样的：4005a0: pushq *GOT[1] 4005a6: jmpq *GOT[2] ---- 4005c0: jmpq *GOT[4] 4005c6: pushq $0x1 4005cb: jmpq 4005a0GOT4对应这下面这条PLT（下面称为PLT2）。GOT0和GOT1包含动态链接器模块的地址，GOT2是动态链接器在ld-linux.so的入口点当发生第一次调用时，程序进入PLT2，PLT2对应我们要调用的函数f第一条PLT通过GOT4进行跳转，初始时GOT对应PLT的第二条指令，因此又跳到下面那条pushq指令上把函数f的ID（1）压入栈之后，跳转到PLT0，PLT0通过GOT1间接的把动态链接器的参数压栈，通过GOT2跳转到动态链接器中，动态链接器利用这两个栈上参数确定f的运行时位置，把这个地址重写给GOT4，再把控制交还给f在这之后，控制第二次传递到PLT2时，它会跳转到GOT4上保存的地址，而这个地址正是f的地址。13 库打桩机制我理解就是hook，可以截获调用，执行自己的代码，Hook可以发生在编译、链接和运行时。其实就是把调用函数替换成我们自己的实现嘛。这里不赘述了14 处理目标文件的工具AR：创建静态库、插入删除列举提取成员strings：列出目标文件中可打印字符串strip：删除符号表信息nm：列出符号表中的符号size：列出节的名字和大小readelf：显示目标文件的完整结构objdump：显示目标文件所有信息，尤其是可以反汇编text中的指令。ldd：列出需要的共享库

CSAPP 5.优化程序性能 优化程序性能本章的目标在于，了解编译器和目标机器的运行规律，通过调整代码的细节提升性能1. 编译器的能力与局限性在了解编译器优化能力的局限性时，不要忘记编译器的第一要务是保证其编译结果的正确性对于void f1(int *x, int *y) { *x += y; *x += y; } void f2(int *x, int *y) { *x += 2* *y; }两份代码，表面上有相同的行为，但是当xy指针指向同一个地址时，会产生截然不同的结果。内存别名使用：两个指针指向同一地址的情况当编译器优化时，必须确保在任何情况下都是正确的。2. 表示程序性能CPE：Cycles Per Element 每元素周期数，概略理解的话可以简单的当作每次执行循环所需要的CPU周期在本章的学习中，以如下的一个程序及其CPE来测量优化效率，其中 length 函数直接返回vec的len字段，get函数先判断下标是否越界，再返回对应的值。#define data_t double / long #define IDENT 0 / 1 #define OP + / * struct { long len; data_t *data; }vec; void comb1(vec v, data_t *res) { *res = IDENT; for(long i = 0; i < v.length(); i ++ ) { data_t val; v.get(i, &val); // put v[i] to val; *res = *res OP val; } }基础的comb1函数在O1优化下，整数加法CPE约为104. 消除循环的低效率消除隐藏的渐进低效率当使用strlen作为遍历字符串的循环条件时，编译器无法确定循环内是否对字符串长度存在可能的修改，因此会每次都调用该函数，造成复杂度错误因此，comb2把length外移，实现了第一个优化 long len = v.length(); for(long i = 0; i < len; i ++ )使得整数加法的CPE优化到了7。5. 减少过程调用过程调用会带来上下文的切换开销，我们对数组的访问并不会越界，但是get函数会进行越界检测。第二种优化直接使用数组的值，而不是调用函数 *res = *res OP data[i];很遗憾，这种优化并没有带来CPE的提升，换句话说，get函数反复的边界检查并没有让这个循环的性能变差。这是由于get函数中的分支预测永远为真，其带来的性能开销没有关键路径的性能开销大，关于关键路径，后面会详细说。6. 消除不必要内存引用在我们的代码中，每次结果都会写回给res，下次运算时还要再读取res参与运算，这样的读写很浪费，因为下次读取的正是循环刚刚写回的值。我们做第三个优化，减少内存读写。现在的函数变成了这样子：void comb4(vec v; data_t *res) { long len = v.length(); data_t* data = v.data; data_t acc = IDENT; for(long i = 0; i < len; i ++ ) { acc = acc OP data[i]; } *res = acc; }我们把结果累计在局部变量acc中，消除反复的读写，使得整数加法的CPE提升到了1.27，相比于上一步的7.17，这是一个很有成效的提升那么，为什么编译器没能做这么简单有效的优化？根据之前我们说的编译的第一要务是保证结果的正确性，我们可以举一个二义性的例子：comb3(v, &v.data[2]); comb4(v, &v.data[2]);当把数组内某个地址本身作为累加结果的位置时，我们的优化就行不通了。很显然，对于v:[2, 3, 5]，comb3的结果是5，comb4的结果是107 理解现代处理器指令级并行：处理器内部同时对多条指令求值，但对上层展示的结果和顺序执行一样。现代处理器可能可以有上百条指令同时在处理。延迟界限：当一系列操作按严格顺序执行程序所能达到的最大性能。数据相关会导致延迟界限对性能的限制吞吐量界限：硬件的原始计算能力，也是程序性能的最终限制。7.1 整体操作分支预测与投机执行：现代处理器会猜测是否选择分支，预测分支的目标地址，提前开始操作。若过后确定分支预测错误，会把状态重设为分支点的状态。一条包括内存引用的指令，比如 add rax, 8(rdx) 会被拆为多个操作，把内存引用和算术运算分开，对于这条指令，会分为加载、运算、写回。预测错误会导致很大的性能开销，现代处理器用退役单元记录处理情况，当预测成功时，退役单元内的内容退役，否则清空，丢弃所有已算出来的结果操作数通过寄存器重命名机制在处理单元中传送数据。使得已经运算出来的结果可以在写回之前被转发到另一个操作。7.2 功能单元的性能对于一个典型的i7 Haswell参考机：完全流水线化：发射时间为1的功能单元。吞吐量：对于容量为C，发射时间为I的操作，吞吐量为每时钟周期C/I 个操作对于该处理器，整数加法的延迟界限为1，浮点加法的延迟界限为3，整数加法的吞吐量界限为0.5，浮点加法的吞吐量界限为1很遗憾，在我的笔记中实在很难很好的描述数据流图和关键路径的概念，我只能尽可能的简洁口述对于comb4来说，循环内汇编可能是这样的（浮点乘）：label : vmulsd (%rdx), %xmm0, %xmm0 ; acc(in xmm0) = acc * data[i] addq $8, %rdx ; pdata += 8 cmpq %rax, %rdx; pdata cmp data_end jne label 可以看到，我们可以拆分为：load→mul→add→cmp→jne我们考虑两个循环，对于load，下一个循环依赖上一个循环的rdx，对于mul，下一个循环依赖load和上一个循环mul的结果，对于add，下一个循环依赖上一个循环的rdx，对于cmp，也是依赖rdx因此限制循环的因素就变成了xmm和rdx的更新，也就是mul和add的执行速度，而mul显然时更慢的，所以我们称更新xmm这条mul链为制约程序性能的关键路径。8 循环展开每次循环处理优化前k次迭代的内容，减少循环迭代次数，称为k*1循环展开对于comb的2*1循环展开例子for(long i = 0; i < len-1; i += 2) acc = (acc OP data[i]) OP data[i+1]; for(; i < len; i ++ ) acc = acc OP data[i];循环展开减少了循环开销，使得整数加法的CPE提升到了1.01，非常逼近延迟界限1.00了对循环展开后的结果画关键路径，还是存在N个mul操作，所以无法打破延迟界限。9 提高并行性之前关键路径受xmm0也就是acc变量更新影响，在前面的计算完成前，都不能计算后面的值，即使mul可以每个时钟周期开始一个新的操作，但是只能每L个周期开始一次操作9.1 多个累积变量由一个非常浅显的数学知识：数列P的累乘积等于数列P中奇数下标的累乘积乘以偶数下标的累乘积，由此我们引出2x2循环展开comb6data_t acc0 = IDENT, acc1 = IDENT; for(long i = 0; i < len-1; i += 2) { acc0 = acc0 OP data[i]; acc1 = acc1 OP data[i+1]; } for(; i < len; i ++ ) acc = acc OP data[i];整数加法CPE被优化到了约0.8，我们打破了延迟界限。在comb6的流程图中，出现了两条关键路径，每条关键路径上只有n/2个乘法。这也是性能提升的关键因素。9.2 重新结合变换对于语句acc = (acc OP data[i]) OP data[i+1]; acc = acc OP (data[i] OP data[i+1]);其实是不一样的，后者乘法的关键路径上只有n/2个操作，这是因为在acc被更新前，data[i]和data[i+1]的乘法无需等待前面的结果。我们减少了关键路径上一半的乘法，得到了接近2x2展开的性能提升。

CSAPP 3. 程序的机器级表示 程序的机器级表示长期的逆向工作，这一章可以说是我最熟悉的知识了。本章以复习记录为主，如有缺漏还请见谅。机器级表示 ：计算机使用字节序列编码操作，程序最终生成机器码。Benefits：理解编译器优化能力，分析关键代码效率了解高级语言隐藏的行为，如并发。本章讨论的都是x86_64下的机器码。2 程序编码机器码中可见的部分寄存器状态程序计数器PC：RIP寄存器整数寄存器：如RAX、RSI等条件码寄存器：如CF、OF等向量寄存器：XMM、YMM等机器不区分数据类型，包括整数与指针、有符号与无符号。编译器通过源代码、条件码寄存器等确定数据的行为汇编文件通过汇编器生成目标文件，目标文件中即为机器所用的字节序列。gdb中，使用 x/nt addr/sym 展示从addr开始的n个t类型长度的字节内容，如x/16b main展示从main开始的16个byteobjdump -d对文件进行反汇编，它只基于二进制文件获取信息。业界常用强大的IDA来做这项工作。3 数据格式对于各类整数数据类型不做区别。指令集中可以操作1、2、4、8字节的数据，即使是相同的操作，根据数据长度的不同，其汇编指令也不同，在机器码上以不同的编码体现，在汇编中用不同的后缀体现。在64位系统中，指针也长8字节大小后缀（整形）1b(yte)2w(ord)4l(ong word)、double words8q(uad words)4 访问信息通用寄存器共有十六个，包括rax-rdx，rs/di，rs/bp，r8-r15它们都有自己对应的低32、16、8位寄存器名，对于rax-rdx，分别为eax、ax、al（ah），（以此类推，下同）对于rsi-rbp，分别为esi、si、sil，对于r8-r15，分别为r8d、r8w、r8b在不同的时候，不同的寄存器可能会因为某些约定出现不一样的行为，比如在fastcall约定中，用si等寄存器传参数、使用sp、bp管理栈空间等。4.1 操作数指示符附上表即可，其中 M[addr]表示对存储器addr位置的引用，具体长度可以依据指令确定。R[r]代表对r寄存器的引用。4.2 数据传送指令MOV的核心只是数据传送，主要区别是源和目的的类型和大小，此外，当大小不同时，还涉及到如何扩展源和目的类型允许如下操作，其实就是不允许Mem互传和Imm作为目的，后者是显然的。SDImmRegRegRegMemRegImmMemRegMem零扩展用后缀z(ero)表示，符号扩展用后缀s(ign)表示，后接源和目的的大小，比如：movswl：符号扩展，字传送到双字此外，还有一个特殊的指令cltq，代表把eax符号扩展到rax，它和movslq eax rax是一样的，不过机器码更短。4.4 栈操作指令通过push/pop这组指令完成，push的过程可以看为：rsp -= 8M[rsp] = S而pop可以看为：D = M[rsp]rsp += 8显然，这样的操作也可以由add/sub和mov完成，但是pop和push的编码更短此外，先修改栈顶再压栈似乎有些奇怪，但是其实想一下栈是倒着增长的就能很容易理解5 算数和逻辑操作这部分没什么好说的，贴表格5.1 LEA指令lea是mov的变形，把操作数的内存地址写到目的操作数中，就像&S。在编译器中，它经常被用来优化简单的乘法加法操作，如leaq 7(rdx, rdx, 4), rax 等同于 rax = 5*rdx + 7 。5.3 位移操作位移操作无非就是左/右移、逻辑/算数移，对于左来讲，算数和逻辑一样，右移的算数SAR会在最左侧填符号位，而SHR会填0 。此外，位移量可以是立即数或者cl寄存器5.5 特殊算数对于乘除法，两个八字节的乘法需要16字节来表示，Intel称为o(ct)word。然而乘除法也无非是有符号、无符号两类罢了，加上一个把rdx和rdx拼在一起做操作数的小魔术。6 控制控制类语句帮助我们实现条件、循环与分支6.1 条件码CPU维护一组Flag寄存器，最常用的包括：CF：Carry Flag 进位ZF：Zero Flag 零SF：Sign Flag 符号OF：Overflow 溢出算数和逻辑运算的结果会影响上述Flag的值，而LEA指令不会。此外，还要引入CMP和TEST指令，CMP和SUB行为一致，TEST和AND行为一致，但是它们都不会改变目的寄存器的值。在这要多提一嘴，CPU如何判断大于、小于的呢？我们刚刚只说了条件码，没说它们和大小的关系。这是一个分类讨论问题。用以下几个例子解释一下。相等：ZF == 0小于（无符号）：CF ，其实就是两数相减不等于零、且产生了进位，也就是A+B的补码进位了，小于（有符号）：SF^OF，分类讨论：A-B为负数，那么在没溢出的情况下，A小于B。其他几个情况无非就是正负与是否有溢出，当只满足一个的情况下是小于。所有常见后缀包括：e/z：相等/零，以及前面加n的否定s：负数，以及前面加n的否定（下同）以下四个是有符号范畴内的大小比较g/nle ：大于ge/nl：大于等于l/nge：小于le/ng：小于等于以下四个是无符号范围内的大小比较a/nbe：超过ae/nb：超过或相等b/nae：低于be/na：低于或相等6.2 访问条件码我们有一组指令来访问条件码，然而在86的程序里我很少见到这类指令，反而是RISC系列的处理器用的多一点。主要就是set(cond) rd，比如sete/setz rax就是根据ZF的结果设置rax，其中e和z分别代表equal和zero，它们是等价的。其他的等价还包括g和le、ae和nb等（above&equal/not below）6.3 跳转指令跳转指令的构成和6.2说的set（cond）差不多，不过变成了j（cond）+ Label（*Operand），此外还加入了修改RIP寄存器的作用。并且有一组无条件转指令jmp条件转举一例：jg（jnle）*rax ：如果大于则跳转到rax中的值那个地址。6.5 条件控制实现分支一个典型的if-else结构，组成为if (expr) { then ... } else { else ... }我们可以翻译为t = expr; if(!t) goto false; then... goto done false : else ... done:这是一类通用的翻译方式。当然，我们可以第一步条件跳转到else，也就可以第一步条件转到then，翻译为如下t = expr; if(t) goto true; else ... goto done true: then... done:显然它们是等价的，但是我们一般选择第一种，因为在没有else的情况下，第一种更能节省代码。6.6 用条件传送实现分支现代处理器流水线依赖于分支预测，如果用上面这种方法，当分支预测失败的时候就会影响处理器性能，因此在特定情况下我们可以使用条件传送cmov系列指令。比如这种：int res; if(x < y) res = y-x; else res = x-y;显然，我们的流水线可以同时计算两个表达式的值，然后根据条件决定把哪个结果送入res里。CPU提供的条件传送（满足条件时mov）指令可以把原来的分支消除掉，不会出现分支预测失败的情况。至于什么是分支预测和为什么分支预测影响这么大，本书下一章应该会讲到（写到这里时我还不确定，如果没有请各位读者不要打我）。cmov指令的格式是cmov[diff] S, R，如cmovge rdx, rax是当ge为真时rax = rdx。公式：预测错误概率为p，没错误执行的时间时Tok，预测错误处罚是Tmp，则执行代码的平均时间：$$ T_{avg}(p)=(1-p)T_{ok}+p(T_{ok}+T_{mp}) = T_{ok} + pT_{mp} $$一类非法情况int *xp; a = xp ? *xp : 0;如果顺序的把三目运算符的两个结果都算完，再cmov，这时如果xp是0，就出现了一次对0的解引用，这显然是错误的。此外，如果then或者else的计算量很大，可能会导致浪费，所以并不是所有情况都适用这种优化。6.7 循环汇编中没有支持C语言多种循环结构的语句（其实8086里应该是有的，loop指令应该能支持do-while结构，不太清楚本书为什么没有提这个指令。），使用条件跳转实现do-while循环do { statements... } while(expr)等价于loop: statements... t = expr; if(t) goto loop;下面这种表达方式就很容易直接翻译成汇编了。while循环while(expr) statements...改写：jump to the middlegoto test; loop: statements...; test: t = expr; if(t) goto loop;其实就是在循环之前先跳到test一次。但是较高优化等级可能会采用另一种方式：guarded-dot = expr; if (!t) goto done; loop: statements...; t = expr; if(t) goto loop; done: ...编译器可能在这种方式下采取更多的优化，比如认为第一次进入测试的代码永远满足。for循环for(init; test; update) statements...其实学C语言的时候应该都有讲过，可以直接拆成whileinit; while(test) { statements...; update; }但是需要注意，在有continue语句的for循环中，不能直接简单的按上述方式转换为while翻译，否则就会出现少执行update的情况。for(init; test; update) { if(if_test) continue; print(haha); }上述应该改写成这样：init; while(test) { if(if_test) goto update_; print(haha); update_ : update; }6.8 switch语句刚学C语言的时候，很多人会把switch当成if-else结构的语法糖使用，但是其实switch结构在特定情况下对性能有很大优化跳转表：一个数组，表项i是当switch的开关索引是i的时候要跳转到的地址。当case们的条件是一个可作为索引的(char就是8b整数，我相信你是知道的)、且范围不超过255的值组的时候，编译器就会先把最小值归0，然后再生成跳转表。我觉得这里没有什么方式比放书上的例子更能方便理解的了。这样的优化是显然的，当情况很多时，jump-table只需要一次跳转，而if-else需要多次判断+跳转7 过程过程是对代码的封装、对功能的抽象，用一组指定的参数和一个可选的返回值（事实上，在现代语言中往往已经支持一组返回值了）实现某种功能。function、method、subroutine和handler都是过程的形式。过程往往需要实现如下几个机制：传递控制：进入过程时，PC应该被设置为Callee的起始地址，退出过程时，应该被设置为Caller调用Callee的下一条地址。传递数据：Caller向Callee提供参数，Callee提供返回值给Caller管理内存：进入Callee可能需要为Callee的局部变量分配空间，退出需要释放7.1 Runtime Stack大多数语言都用FILO的Stack来管理过程调用。对于一次调用，会为它分配一段独特的空间称为栈帧。x86-64为这种非常常见的操作提供了一组指令。一次函数调用的栈帧可能包含 局部变量、它所调用的过程将返回到的地址、它为调用的过程传递的参数和它为调用它的过程保存的寄存器等。以下以函数调用P→Q为例7.2 控制调用 call：把PC（rip）设为Q的起始位置把call Q后面那条指令的地址压栈其过程就相当于一组push+jmp跳转call可以是直接或者间接的，用call LABEL或者 call *Op都可以返回 ret：从栈中弹出返回地址跳转到返回地址7.3 数据当参数个数小于等于6（整形）时，按顺序用rdi、rsi、rdx、rcx、r8、r9传递当大于6时，多出来的参数需要放在P的栈帧上，因此P的栈帧最顶部（最低地址）的部分，也需要给它调用的参数最多的那个函数的调用（听起来有点拗口，就是所需空间取max）准备好传参的空间。其中排位最后的参数位于栈顶，所有数据向8对齐7.4 局部变量当寄存器不够存放所有的local数据（书上用的是本地，但是我觉得中文的本地并不能很好的描述这个意思，大概就是本次“运行时调用”需要的数据）对局部变量取地址局部变量是数组或结构体，需要通过引用被访问。这些情况时，局部变量需要分配在内存中，作为当前函数栈帧的一部分。7.5 寄存器中的局部空间callee-saved registers：rbx rbp，r12-r15caller-saved registers：除了以上寄存器及rsp顾名思义，不同的寄存器由不同的角色保护，当被调用者需要使用那些寄存器时，它需要先保存那些寄存器到栈，在返回之前再恢复它们。7.6 递归在栈模式下，P→P和P→Q没有什么本质上的不同，每个运行时的函数的局部数据由栈帧维护、隔离8 数组数组：将标量数据聚集成更大数据类型的方式8.1 基本原则声明：当有声明 T a[N];时，在内存中分配一个L*N字节的连续区域，L=sizeof T对于一次访问：a[i]，a的地址放在rdx，i的数值存放在rcx，就可以用(rdx, rcx, k)索引到该位置的值，其中k是伸缩因子，可以为1、2、4、8，足够覆盖所有基本简单数据类型8.2 指针运算若：指针p的类型为T，值为xp，则p+i的值为xp+L*i8.3 嵌套数组对于二维数组 a5，可以看成a是一个长度为5的数组，其中每个元素是一个长度为3的数组。在引用时，先计算第一维的地址，再加上第二维的偏移对于 T DR, &Di = val_D + L(C*i+j)8.4 定长数组对于定长数组，GCC有一些优化，可以减少很多不必要的运算，举一例：int A[16][16], B[16][16]; // original code for(j = 0; j < 16; j ++ ) res += A[i][j] * b[j][k]; // after optimize int *Ap = &A[i][0], *Bp = &B[0][k]; Bend = &B[16][k]; do { res += *Ap * *Bp; Ap ++; Bp += 16; } while(Bp != Bend);把未优化时的四次访存(A[i], Ai, B[j], Bj)变为了两次加法8.5 变长数组由于编译器不知道数组的大小，只能通过运行时的值确定偏移，该偏移必须要在运行时用一次乘法，其性能劣化很严重。但是这并不意味编译器无法进行优化。9 异质数据结构structunion9.1 结构对结构字段的访问：结构体基地址+字段偏移编译时处理字段与偏移信息，机器码中不包括结构具体信息9.2 联合联合体是允许用多种类型来引用相同的一段内存地址，一般只适用于一个内存地址在不同情况下互斥的情况的使用。9.3 数据对齐许多系统限制：某种类型对象的地址必须是某个值K的倍数。x86_64虽然能在不对齐的前提下正常工作，但是建议：任何K字节的基本对象地址必须是K的倍数。举一例struct s { int i; // offset : 0 char j; // 4 int k; // 8 }如果不对齐，单纯排列，k的偏移似乎应该是5，但是5-7这三个字节被插入了一个间隙。此外，即使把s的字段顺序改为i、k、j，也可能需要在j的后面填充三个字节。10、11 指针、内存溢出与浮点操作只给一些简略的概念罗列指针信息包括：类型、值，使用&创建，*引用指针可以指向函数内存溢出主要是栈溢出和堆溢出，本书只讲了栈溢出还记得返回地址写在栈上，当本层栈帧的某个变量可以任意控制长度和内容，我们就可以覆盖返回地址。进而进行攻击。缓解方法ASLR栈地址随机化Canary

CSAPP 1. 计算机系统漫游 计算机系统漫游本章跟随一个 hello, world 程序，介绍它的生命周期中出现的相关概念。1 从源程序开始文本文件：只由ASCII字符（现在也包括Unicode字符）组成的文件。文本文件实质上是一个由{0, 1}两个值组成的位(bit)序列8个bit被组织为一组，称为字节源程序：程序员通过编辑器创建并保存的文本文件。计算机系统中的一切信息，包括磁盘上的、内存上的、网络上的，都是由一串比特表示的。区分不同数据的唯一方法是我们读取到这些数据时的上下文。根据不同的上下文，一个同样的字节序列可能表示整数、浮点数、字符串或指令等。2 到目标文件源文件需要经过编译系统（包括{预处理器，编译器，汇编器，链接器}）转化为一系列机器指令，进而运行预处理负责处理以 # 开头的编译器命令，如展开 include 并直接插入到原文件编译阶段负责把上一阶段生成的文件翻译为汇编程序，它是语言无关、机器相关的。它仍是一个文本文件。汇编器负责把汇编程序翻译为二进制的目标程序。链接器负责把调用的库函数*插入到目标程序中，以供目标程序调用。*：实际上并不只是这样，其他文件的全局符号（包括函数、变量）也会被处理。根据链接方式的不同，可能也不是在这一步插入。这部分后面应该会有更详细的解释。3 为什么要了解编译系统了解机器语言级别，我们的高级代码是如何运转的，进一步的，可以寻觅提升性能的方法。了解链接出现的错误避免漏洞4 典型的硬件系统一个典型的硬件系统主要由如下几部分构成总线（Bus）：负责在各个部件间传递定长的信息，该定长一般称为字IO设备：如硬盘、鼠标等，作为用户输入输出，通过适配器或控制器与总线相连。主存：存放运行时程序和程序数据。逻辑上是一个线性的字节数组，其索引称为地址。处理器：执行主存中存放的指令的部件。处理器中有一系列大小为一个字的存储设备（寄存器）。包括通用寄存器和一系列只能执行特定功能的寄存器5 高速缓存程序与数据最初存放在磁盘上，在加载时被复制到主存。寄存器文件速度快、可存放内容少、造价高主存速度相对慢、可存放内容相对多、造价相对低高速缓存：作为暂时的集结区域，存放处理器近期可能需要的信息，速度比主存快很多高速缓存分级，L1容量可以达到数万字节，速度接近寄存器L2容量在数十万到百万字节，比L1慢5倍高速缓存由SRAM精彩随机访问存储器实现6 存储器层次结构存储器分层，高层做低层的高速缓存，期望达到接近高层的容量、低层的访问速度一个典型的层次结构从低到高可能包括：寄存器、L1-L3、主存、磁盘、远程存储（分布式文件系统、Web）7 操作系统管理硬件操作系统主要提供两个基本功能防止硬件被程序滥用为程序提供简单一致的机制控制复杂且不同的硬件设备，主要机制包括进程虚拟内存文件7.1 进程进程：OS对正在运行的程序的一种抽象，系统可以同时运行多个进程，每个进程认为自己独占硬件。并发运行：不同进程的指令是交错执行的，OS通过上下文切换实现这种机制上下文：进程运行所需的状态信息，主要包括程序计数器PC和寄存器的值主存的内容7.2 线程一个进程可以由多个称为线程的执行单元组成，共享代码和数据7.3 虚拟内存虚拟内存使得进程认为自己独占的使用主存，每个进程看到的内存都一致，称为虚拟地址空间。Linux下虚拟地址空间从低地址到高地址主要由这些内容组成：rodata和text：只读数据和代码data、bss：可读写的数据heap：堆，向上增长共享库的映射stack：由用户空间的最高地址向下增长kernel：内核的虚拟内存7.4 文件文件就是字节序列，在Linux（Unix）中，设备与网络都可以看作是文件。8 网络通信计算机系统通过网络和其他系统连接到一起，以实现信息的复制。9 总结系统：硬件和软件系统交织的结合体9.1 Amdalh定律定律：对系统的某个部分加速时，对系统性能影响取决于该部分重要性和加速程度。$$ 执行某程序时间T_{old},某部分执行时间与其之比为\alpha，该部分性能提升比例为k $$$$ 加速比S=\frac{1}{(1-\alpha)+\alpha/k} $$9.2 并发和并行并发：一个同时具有多个活动的系统并行：用并发使得一个系统运行的更快从高到低主要三个层次线程级并发：同时执行多个线程：超线程/多线程技术指令级并行：同时执行多条指令：pipeline单指令、多数据并行：单条指令同时处理多条数据：SIMD9.3 抽象文件是对IO设备的抽象虚拟内存是对存储器的抽象进程是对正在运行的程序的抽象。