Posted Updated Basics2 hours read (About 17850 words)0 visits

CSAPP

Representing and Manipulating Information

Information Storage

  1. 计算机程序把计算机的内存看成一段非常大的bytes数组，这个连续的bytes数组被称为虚拟内存(virtual memory)。虚拟内存的每一个byte都会被一个唯一的数字表示，这个数字称为这块内存的地址。所有的地址组成的集合被称为虚拟地址空间(virtual address space)

Data Sizes

  1. 每一台计算机都有一个字长(word size)，它指明了指针的大小(也就是地址的长度)，所以通过字长可以判断一台机器的虚拟地址空间的最大大小。比如一台机器的字长是w bit，那么它的虚拟地址的范围就是0到2的w次方减1。
  2. 需要明确的是，本书中默认地址字长和数据子长是相等的，所以统一用字长表示，但其实很多CPU的地址总线与数据总线不一样长，虚拟地址的范围是由地址字长决定的。比如早期8086CPU有16位数据总线，但是有20位地址总线，那么它的最大虚拟地址空间是2的20次方，也就是1MB。当然这里还有一个问题就是数据总线只有16位，我们从寄存器中取出的地址只有16位，这个时候需要通过段寄存器进行地址偏移来得到最后的20位地址。
  3. C语言中定义的变量在32位和64位机器中可能有不同的长度，比如long在32位机器中是4个字节，但是在64位机器中是8个字节。如果想要确保所使用类型的字节大小，可以使用int32_t这种固定长度的自定义类型。

Addressing and Byte Ordering

  1. 对于跨越多个字节的程序对象，我们需要建立两条规则：我们使用多个字节中的哪一个表示这个对象？如何在内存中排列这些字节？
  2. 对于第一条规则，现在计算机会将多字节对象存储为一块连续的字节序列，并且使用最小的地址作为整个对象的地址。比如一个int型的变量的地址是0x100，那么代表这个int变量会被存放在0x100，0x101，0x102，0x103这段连续的内存中。
  3. 对于第二条规则，现在计算机有两种排列方式，分别是大端存储(big endian)和小端存储(little endian)。大端存储指的是对象的高位字节先存储，小端储存指的是对象的低位字节先存储。假设我们要在0x100的地址处存储一个0x01234567的int变量，下面是例子：
    1
    2
    3
    0x100 0x101 0x102 0x103
    01    23    45    67        大端
    67    45    23    01        小端
  4. 大小端存储并没有好坏之分，只是对于多字节对象的存储排列形式不同而已，但是在某些情况下，我们需要注意大小端，常见的有C语言中的类型转换和union。假设我在一块内存中定义了一个int变量，并且将其强制类型转换为char[]数组，那么这个时候大小端排列就对char[]数组中存储的值有影响。

Introduction to Boolean Algebra

  1. a^b代表逻辑异或，异或只有在a和b一个为0一个为1时，结果才为1，否则为0。异或有一些有趣的性质，a^a = 0并且异或符合交换律，所以我们可以得出(a^b)^a = b。
  2. 布尔运算的另一个应用是可以表示集合运算，假设一个位向量a = [01101001]表示集合A = {0, 3, 5, 6}，另一个位向量b = [01010101]表示集合B = {0, 2, 4, 6}，这个时候或运算相当于取并集，与运算相当于取交集。计算机网络中的子网掩码就是一个与运算的应用。

Shift Operations in C

  1. x << k表示将x按位左移k位，丢掉最高的k位，将最低的k位补0
  2. x >> k表示将x按位右移k位，但是对于右移，我们常常将其分为逻辑右移和算术右移。逻辑右移指的是向右移动k位以后，在高位全部补位0；算数右移指的是向右移动k位后，在高位全部补上原本变量的最高位(0或者1)。
  3. 对于有符号数，大多数编译器都会使用算数右移，而对于无符号数，编译器会使用逻辑右移。在Java中，>>表示算术右移，>>>逻辑右移。

Integer Representations

Unsigned Encodings

  1. 无符号数的编码很容易理解，能够编码的范围是0到2的w次方(w是字长)

Two’s Complement Encodings

  1. 无符号数的编码无法表示负数，补码的存在是为了表示负数。补码所表示的数的第一位叫做符号位，它在计算时的权重是负的，所以如果一个4位的补码整数1000表示的是-8。
  2. 由于补码第一位的权重是负的，其他位的权重都是正的，所以用补码表示负数时，1000表示最小的负数-8，1111表示最大的负数-1。即使当位数增加的时候，111...111永远代表的是-1。
  3. 补码所能表示的负数比正数多一个，这是因为二进制能表示的数都是2的倍数，但是我们需要一个0000来代表0，这就造成了补码所能表示的负数总是比正数多一个。
  4. 符号数的编码还有原码和反码，但是他们比起补码由各自的问题，现代计算机都是统一使用补码表示有符号数：https://www.zhihu.com/question/20159860
  5. 使用补码最大的好处就是补码的加减运算可以直接通过二进制表示的加减运算得到，比如计算0101+1001，我们直接按照我们从小学习的最熟悉的十进制运算进行加减，只不过这里是遇2进位。国内的教材总喜欢说负数的补码就是正数取反加一，这只是一个运算的技巧，个人认为还是按照符号位的理解比较好。取反加一的技巧很好推断出来：正数 + 负数 = 0000，我们知道任何一个数与它的反相加结果都是1111，再加1自然而然就得到0了

Conversions between Signed and Unsigned

  1. 在C语言中当我们想要对有符号数和无符号数进行强制类型转换的时候，内部的实现是根据位的角度，而不是数的角度。当我们进行强制转换的时候，二进制的表示不会发生变化，但由于符号数和无符号数使用不同的编码，所以最终所表示的数也是不同的
  2. 假设我们有下面的一段程序： 
    1
    2
    3
    short int v  = -12345;
    unsigned short uv = (unsigned short) v;
    printf("v = %d, uv = %u\n", v, uv); //v= -12345, uv = 53191
    这里我们会发现，无符号数53191和有符号数-12345有着相同的二进制表达0xCFC7，也就是说C语言在进行强制类型转换的时候不会改变二进制的表达，而只是使用不同的编码方式。
  3. 我们还发现无符号数53191和有符号数-12345之间存在某些联系，前面我们提到两者的二进制表达式完全一样的，只是补码将第一位的1翻译成负的32768(2的15次方)，而无符号数编码将第一位的1翻译成正的32768，所以其实两个数之间差了65536(2的16次方)。这个特性适用于其他位数，补码表示的负数与无符号数编码表示的正数相差2的w次方(两者二进制表达相同)。

Signed versus Unsigned in C

  1. 当C语言的表达式中，如果一个运算数是有符号的而另一个是无符号的，那么C语言会隐式的将有符号数强制类型转换为无符号数。所以我们会看到下面这些奇怪的表达式： 
    1
    2
    -1 < 0U //false，因为-1会被转换成无符号数，而-1的二进制表达式全是1
    2147483647U > -2147483647-1 //false，因为-2147483648会被转换成无符号数

Expanding the Bit Representation of a Number

  1. 当扩大一个无符号数的时候，我们在它的高位上填充0
  2. 当扩大一个有符号数(补码)的时候，我们在它的高位上填充它本来的符号位。 
    1
    2
    3
    4
    short sx = -12345;//12345, 二进制表达：cf c7
    unsigned short usx = sx; //53191，二进制表达：cf c7
    int x = sx; //-12345，二进制表达：ff ff cf c7
    unsigned ux = usx; //53191，二进制表达：00 00 cf c7
    我们可以看到扩大后的无符号数与有符号数的二进制表达不再相同。
  3. 这里我们会发现一个有趣的结论，在有符号数的高位填充符号位不会改变补码所表示的数字。这对于正数(即添加0)是显而易见的，但是为什么在负数的高位填充1仍旧不改变补码的值呢？ 
    1
    2
    3
    101 代表 -4+1=3
    1101 代表 -8+4+1 = 3
    11101 代表 -16+8+4+1 = 3
    其实原因就是原本负数的最高位由于更高位的填充变成正值，一来一去就是两倍的原本负数的最高位的值，再加上前面的正值，正好等于新的负数的最高位。
  4. 如果我们将short转为unsigned int，程序会先转变变量的大小，然后才是类型。假设sx表示一个short变量，对于(unsigned)sx，等价于(unsigned)(int)sx。

Truncating Numbers

  1. 上一节介绍了扩大有符号数或者无符号数，如果是缩小的话，二进制的高位会被丢掉。

Integer Arithmetic

Unsigned Addition/Two’s Complement Addition

  1. 不论是无符号数的加法还是补码的加法，都会出现溢出的问题，其中无符号数的加法只会有正数的溢出，补码的加法不仅有正数的溢出，还存在负数的溢出，面对溢出的做法就是丢掉溢出位。

Unsigned Multiplication/Two’s Complement Mutiplication

  1. 乘法的运算也会导致溢出的产生，同样的，我们把溢出的位丢掉即可得到结果。

Multiplying by Constants

  1. 历史上，计算机的整数乘法是一种相对慢的运算，通常需要十个或更多的时钟周期来进行计算，然而加减法以及移位运算只需要一个时钟周期即可完成，所以编译器会尝试将乘法替换成加减法和移位运算。
  2. 我们知道对一个无符号数或者补码左移k位，相当于乘以2的k次方，我们可以利用这条规律来把整数表示为2的幂之间的加和，所以最终我们就可以实现用加法和移位运算代替乘法

Deviding by Powers of 2

  1. 整数的除法是比乘法还要慢的运算，通常需要30或者更多个时钟周期，如果所计算的除法是除以2的幂，这个时候可以使用右移运算代替，需要注意的是，无符号数使用逻辑右移，而补码使用算术右移。
  2. 需要注意的是，整数每右移一位相当于除以2，那么如果遇到除不开会怎样？答案是向下取整(正数和负数都是向下取整)。比如14(二进制是00001110)右移两位，结果是3(二进制是00000011)；-14(二进制是11110010)右移两位，按除法结果是-14/4 = -3.5，向下取整就是-4(二进制是11111100)。

Floating Point

Fractional Binary Number

  1. 二进制的小数通过在添加小数点来表示是，比如101.11表示的就是1*4+0*2+1*1+1*0.5+1*0.25 = 5.75。
  2. 一个很重要的规则：当我们把小数点向左移的时候，相当于对结果除以2；当我们把小数点向右移的时候，相当于对结果乘2.比如1011.1表示的就是11.5。
  3. 类似十进制小数无法表示某些数，比如三分之一，二进制小数也有一些无法表示的数，比如0.20。

IEEE Floating-Point Representation

  1. IEEE浮点数分为三个组成部分：符号位s(sign)，尾数M(significant)，阶数E(exponent)。这三个组成部分得到的结果是V = -1的s次幂 * M * 2的E次幂。至于这三个数是如何根据32位的float和64位的double计算出来的，可以参考三种不同的情况：Normalized Values，Denormalized Values，Special Case。
  2. M在Normalized Values情况下表示1到2的小数，在Denomalized Values情况下表示0到1的小数，而阶数E就相当于在对M的小数进行左右移动(根据E是正数还是负数)，这也就是浮点数名字的由来，看起来就像小数点在移动。

Examples Numbers

  1. 从书中的例子可以看出来，Denormalized Values表示的是靠近0的很小的小数，最大的Denormalized Values与最小的Normalized Values是很接近的。

Data Lab

位运算的一些小技巧

  1. 利用位的&和|运算，也可以巧妙地达到类似&&和||的逻辑效果。用0x01表示true，0x00表示false。
  2. 判断两个数是否相等，可以使用^。所以使用!(a^b)就可以达到a和b相同时返回true(0x01)，不同时返回false(0x00) 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    /* 
    * isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' to '9')
    *   Example: isAsciiDigit(0x35) = 1.
    *            isAsciiDigit(0x3a) = 0.
    *            isAsciiDigit(0x05) = 0.
    *   Legal ops: ! ~ & ^ | + << >>
    *   Max ops: 15
    *   Rating: 3
    */
    int isAsciiDigit(int x) {
    int y = x>>4;
    int flag = !(y^0x03);
    int z = x&0xF;
    int zeroToSeven = !(z>>3);
    int eight = !(z^0x8);
    int nine = !(z^0x9);
    return flag & (zeroToSeven | eight | nine);
    }
    这道题就使用前两个技巧。首先flag的目的是为了确定x的高四位是0x3，所以这里的操作是先右移四位，然后判断是否与0x03相等，相等的话返回true(0x01)。其次我们需要确认低四位是1到9。这里是分别判断低四位是0到7或者8或者9，将它们的结果进行或运算。最后再与flag进行与运算。
  3. 巧用模的&运算，可以保留某些位不变，其他位变为0 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    /* 
    * allOddBits - return 1 if all odd-numbered bits in word set to 1
    *   where bits are numbered from 0 (least significant) to 31 (most significant)
    *   Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
    *   Legal ops: ! ~ & ^ | + << >>
    *   Max ops: 12
    *   Rating: 2
    */
    int allOddBits(int x) {
        int y = 0xAA;
        y += y<<8;
        y += y<<16;//0xAAAAAAAA作为模
        return !((y&x)^y);
    }
    这道题就巧用了0xAAAAAAAA作为模，与0xAAAAAAAA进行与运算后仍旧与0xAAAAAAAA相等，证明x的偶数位都是1。

浮点数运算

  1. 一个规则：1.1101 * 2 = 11.101。也就是乘2相当于小数点左移，除以2相当于小数点右移
    所以浮点数，M的小数点一开始在开头，我们可以看作是M的小数点在左移或者右移E的位数。

Machine-Level Representation of Programs

  1. 计算机运行的时候执行二进制的机器码，机器码的生成根据编程语言，计算机指令集，操作系统的不同而不同，所以二进制的机器码往往是不能跨平台使用的。
  2. GCC C编译器(compiler)先根据代码生成汇编代码，然后调用汇编器(assembler)和链接器(linker)生成可执行的机器代码。
  3. 使用C语言而不是直接写汇编的好处：现代的编译器会自动优化我们C语言生成的汇编代码，使得它的执行效率更高；C语言是跨平台跨机器的，而汇编语言在不同平台不同机器是不同的。但是能够读懂汇编语言对于优化代码是有帮助的。

Program Encodings

  1. 假设我们有p1.c和p2.c两个C语言程序想要编译，我们执行gcc -Og -o p p1.c p2.c命令后，从C语言代表到可执行机器代码的过程：
    • C预处理器会把#include和#define替换成相应的代码
    • 编译器生成两个源文件的汇编代码，分别为p1.s和p2.s
    • 汇编器将汇编代码转换成二进制的目标代码(object code)，分别为p1.o和p2.o。目标代码是机器代码的一种，它包含了所有指令的二进制形式，但是全局变量的地址还没有被填入
    • 链接器将两个目标代码以及库函数(比如printf)连接在一起，生成最终的可执行机器代码p
  2. 命令中的-Og代表汇编语言的优化程度，-Og的优化程度不高，但是方便我们理解汇编语言并进行debug，还有其他的优化程度比如-O0等。

Machine-Level Code

  1. 指令集架构(instruction set architecture, ISA)定义了处理器的状态，指令的格式以及这些指令对处理器状态的作用效果。我们常说的x86-64就是64位intel CPU的指令集架构，32位intel CPU的指令集架构叫做IA-32(x86-64兼容IA-32)。
  2. 部分处理器状态：
    • 程序计数器(program counter, PC)，在x86-64指令级架构里叫做%rip。程序计数器总是指出下一个要执行的指令的地址。
    • 整数寄存器文件(integer register file)包含了16个命名的位置，分别储存64位的值。这些寄存器可以储存地址或者整数数据，有的寄存器被用来记录某些重要的程序状态，有写被用来保存临时数据，比如过程的参数，局部变量和返回值。
    • 条件码寄存器保存着最近执行的算数或逻辑指令的状态，根据这些状态我们可以实现流程控制。
    • 一组向量寄存器可以存放整数或者浮点数。
  3. 机器语言与汇编语言：机器语言是二进制机器码，是由CPU指令集规定的，不同的二进制数代表不同的CPU操作。汇编语言相当于对于机器语言的一种助记形式，方便我们用文本描述CPU支持的操作，汇编语言最终都会通过汇编器翻译成机器码并在CPU中运行。比如x86-64指令集提供将%rbx寄存器存储的内容放入栈(stack)的操作，它的机器码是16进制的53，那么如果CPU读取机器码并识别到53，那么CPU就会执行上述的操作。但是问题是，人类不可能记住这些二进制机器码对应的操作，所以产生了汇编语言，比如汇编语言对于上述操作的代码是push %rbx，汇编器可以把相应的汇编代码翻译成机器码53，这样CPU就能进行相应的操作了。
  4. 汇编语言有两种代码格式：ATT和Intel。通过上面我们知道汇编语言不过是一种机器语言的助记形式罢了，所以不论代码格式怎样，只不过是相应需要使用的汇编器不同罢了，最终翻译成的机器码都是确定的。本书中的例子都是使用的ATT格式。
  5. 不同的指令集架构对应的指令的格式(机器码)肯定不同，比如x86-64指令集提供将%rbx寄存器存储的内容放入栈(stack)的操作，它的机器码是16进制的53，但是相同的操作在ARM架构下的机器码肯定不同，甚至寄存器的名字都不一样。

Data Formats

  1. 由于Intel CPU起源于16位，所以Intel使用word来表示16位的数据类型，用double words表示32位的数据类型，使用quad words表示64位的数据类型。
  2. x86-64指令集架构下的数据类型： 
    1
    2
    3
    4
    5
    6
    7
    8
    C declaration  |  Intel data type  |  Assembly-code suffix  |  Size(bytes)
    char           |  Byte             |  b                     |  1
    short          |  Word             |  w                     |  2           
    int            |  Double word      |  l                     |  4
    long           |  Quad word        |  q                     |  8
    char*(pointer) |  Quad word        |  q                     |  8
    float          |  Single precision |  s                     |  4
    double         |  Double precision |  l                     |  8
  3. 大多数GCC生成的汇编语言指令都会有一个字符的后缀，表明操作数的大小。比如数据传送指令有四个变种：movb(move byte)，movw(move word)，movl(move double word)，movq(move quad word)。int和double都是用l作为后缀，但是这不会造成歧义，因为浮点数使用的是一套完全不同的指令集和寄存器。

Accessing Information

  1. 最开始的8086 CPU只有八个16位的寄存器，在书中图3.2标记为寄存器%ax到%bp。当CPU被升级为32位的IA32指令集后，这些寄存器也被升级为32位，在书中图3.2中标记为rax到%rbp。当升级为64位的x86-64指令集后，八位寄存器也被升级为64位，并在图中被标记为%rax到%rbp，另外，加入了八个新的寄存器，它们在图中被标记为%r8到%r15。
  2. 汇编指令会生成1，2，4，8字节的值，当这些指令使用寄存器作为目的地的时候，我们需要考虑1，2，4字节值的高位。原则是：生成1和2字节值的指令会保持高位不变；生成四字节值的指令会将寄存器的高四位设置为0。

Operand Specifier

  1. 大多数汇编指令有一个或者多个操作数(operand)，来指明执行一个操作要使用的源数据值，以及放置结果的目的地。源数据值可以是常量或者从寄存器或内存中读取，结果可以被储存在寄存器或者内存中。
  2. 汇编指令支持三种操作数类型：
    • 立即数(immediate)：使用$加上一个整数表示，比如$-577和$0x1F
    • 寄存器：表示寄存器中存储的值，在图3.3中，我们使用R[寄存器名字]来表示寄存器中存储的值
    • 内存引用：通过计算出来的地址(通常称为有效地址，effective address)来访问某个内存地址，图3.3中给出了很多计算有效地址的形式

Data Movement Instructions

  1. 数据移动指令是使用最频繁的指令： 
    1
    2
    3
    4
    5
    6
    7
    Instruction                     Effects           Description
    MOV            S, D             D <-- S           Move instructions
      movb                                            Move byte
      movw                                            Move word
      movl                                            Move double word
      movq                                            Move quad word
    movabsq        I, R             R <-- I           Move absolute quad word
  2. 源操作数(source operand)可以是立即数(immediate)，寄存器或者内存引用；目的地操作数(destination operand)只能是寄存器或者内存引用。同时x86-64有一个限制：move指令的两个操作数不能都是内存地址，也就是说如果我们想要拷贝一个一个内存地址中的值到另一个内存地址，那么需要两个move操作。我们需要先把源内存地址中的值放入寄存器中，然后再把寄存器中的值移动到目的地内存。
  3. 大多数move指令只改变特定寄存器的值，但是有一个特例是使用movl并且把寄存器作为目的地。由于movl指令生成的结果是4字节(32位)，符合前面我们提到的例，所以movl指令会把寄存器的高四位填位0。
  4. 下面是一些数据移动指令的例子： 
    1
    2
    3
    4
    5
    movl %0x4050,%eax //Immediate->Regester, 4 bytes
    movw %bp,%sp //Register->ReGISTER, 2 bytes
    movb (%rdi,%rcx),%al //Memeory->Register, 1 byte
    movb $-17,(%esp) //Immediate->Memory, 1 byte
    movq %ras,-12(%rbp) //Register->Memory, 8 bytes
  5. 图3.5和3.6介绍了movz和movs指令集，它们的作用都是把一个小的源数据值移动到一个应该储存更大数据值的目的地。movz会把高位填0，而movs会把高位填上符号位。

Pushing and Popping Stack Data

  1. pushq和popq指令负责在栈区(stack)的栈顶放入或者移除一个quad word，内存中的栈区是向低地址方向增长的，先入后出的。%rsp总是指向栈顶的地址。
  2. pushq %rbp指令就相当于subq %8,%rsp movq %rbp,%(rsp)，使用pushq的好处就在于pushq只是单字节命令，而其等价的指令需要8个字节。
  3. popq %rbp指令就相当于movq %(rsp),%rax addq %8,%rsp，我们可以看到对于popq操作，我们只是把栈顶的值放入%rax用来当做返回值，然后移动栈顶的指针，原本栈顶存储的值并没有被删除。原本栈顶储存的值不会被改动，直到被其它指令覆盖。

Arithmetic and Logical Operations

  1. 图3.10列出了x86-64部分的整数和逻辑操作的指令，这些操作可以被分成四类：load effective address，unary，binary，shifts

Load Effective Address

  1. load effective address(leaq)指令其实是movq指令的变形，它的指令形式是从内存读数据到寄存器，但实际上它并没有引用内存的值。它的第一个操作数看起来是一个内存引用，但实际上是把内存的有效地址拷贝到目的地。
  2. leaq指令可以表示一些常用的算术运算，比如如果%rdx寄存器中保存着x，那么指令leaq 7(%rdx,%rdx,4),%rax就会把寄存器%rax设置为5x+7

Unary and Binary Operations

  1. Unary指令的source和destination都是相同的，常见的指令有INC，DEC等
  2. Binary指令第一个opearand是source，第二个opearand是destination，比如subq %rax,%rdx相当于寄存器%rdx的值减去%rax的值。并且与MOV指令相同，binary指令的两个operand不能同时是内存

Shift Opearions

  1. shift指令的第一个操作数是移动的位数，第二个操作时被移位的值。移动的位数可以是立即数，也可以是单字节寄存器%cl。需要注意的是，当使用寄存器%cl的时候，对于不同的字节数，只有部分的低位有效，比如对于salb指令，那么寄存器只有低三位有效，高位都被忽略，在比如对于salq指令，那么寄存器的低六位有效，高位被忽略(因为低六位足够进行64位数的移位运算了)。

Special Arithmetic Operations

  1. 书中图3.12展示了几条特殊的算数运算指令，主要是当进行64位的乘法和除法运算的时候，会产生128位的oct word，这些指令使用特定的寄存器储存运算的结果。
  2. cqto指令会把%rax寄存器中储存的64位值扩展为128位，高64位储存在%rdx中，高64位的值由%rax的符号位决定。

Control

Condition Codes

  1. 除了整数寄存器外，CPU还维护着一组单个位(single-bit)的条件码，用来描述最近的算数或逻辑操作的属性，这些条件码寄存器后面可以被用来检测是否执行某些条件分支指令(if，while，for，switch)：

    • CF(Carry Flag)：进位标志。最近的操作使最高位产生了进位。可以用来检查无符号操作的溢出。
    • ZF(Zero Flag)：零标志。最近的操作得出的结果为0。
    • SF(Sign Flag)：符号标志。最近的操作得出的结果为负。
    • OF(Overflow Flag)：溢出标志。最近的操作导致补码的溢出(正溢出或者负溢出)。

  2. leaq指令不会改变状态码，因为它的作用是进行地址计算。其他出现在书中图3.10的指令都会导致状态码的改变。

  3. 图3.13展示了CMP和TEST指令，它们不会对别的寄存器造成改动，而是只是影响状态位。CMP指令就像SUB指令，TEST指令就像AND指令，只不过他们都不会改变目标寄存器的值，而是单纯的根据结果改变状态位。

Accessing the Condition Codes

  1. 条件码通常不会直接读取，常用的使用方法有三种：

    • 我们能够根据一些状态码的组合，使用SET指令，把单个字节设置为0或者1
    • 我们能够根据一些状态码的组合，使用JUMP指令，跳转到程序的不同位置
    • 我们能够根据一些状态码的组合，使用CMOV指令，转移某些数据

  2. 图3.14展示了SET指令集的用法，通过某些状态码的组合来设置一个指令的单字节寄存器。虽然所有的算数和逻辑运算都会改变状态码，但是SET指令的描述是根据假设一个CMP指令t=a-b被执行，然后SET指令根据CMP指令的结果设置寄存器。比如setl的意思是如果a-b的结果less than 0，那么就把寄存器设置为1。

  3. 书中240页有介绍为什么setl指令的判断依据是SF^OF，但是感觉不是很重要，直接根据SET指令的后缀来得到判断条件就好了。

Jump Instructions

  1. 图3.15展示了JMP指令集的用法，其中需要特殊说明的是无条件jmp跳转指令。无条件跳转指令分为直接跳转和间接跳转。直接跳转指令使用label作为跳转的目的地，例子如下： 
    1
    2
    3
    4
    5
        movq $0,%rax
        jmp .L1
        movq (%rax),%rdx
    .L1:
        popq %rdx
    间接跳转的格式是jmp *Destination，例子如下： 
    1
    2
    jmp *%rax //以%rax寄存器中的值作为跳转目标
    jmp *(%rax) //以%rax寄存器中的值作为内存地址，从内存中读取跳转目标

Jump Instruction Encodings

  1. 本章介绍了JMP汇编代码被编码成机器代码的两种方式：
    • PC relative：将目标指令的地址与紧跟在跳转指令后面那条指令的地址之间的差作为编码，这些地址偏移量可以编码为1，2或者4个字节
    • absolute：用四个字节直接指定想要跳转的指令的地址
  2. 下面是一个PC relative编码的例子： 
    1
    2
    3
    4
    5
    6
    7
    8
        movq %rdi,%rax
        jmp .L2
    .L3 
        sarq %rax
    .L2
        testq %rax,%rax
        jg .L3
        rep;ret
    上面的汇编代码产生的机器码是： 
    1
    2
    3
    4
    5
    6
    0:  48 89 f8    movq %rdi,%rax 
    3:  eb 03       jmp 8 <loop+0x8>
    5:  48 d1 f8    sarq %rax
    8:  48 85 c0    testq %rax,%rax
    b:  7f f8       jg 5<loop+0x5>
    d:  f3 c3       rep;ret
    我们可以看到，第一个跳转指令jmp .L2被编码成eb 03，03代表了相对偏移量，跳转语句的下一句指令的地址是0x05，所以跳转的地址是0x05+03=0x08(相对地址是根据跳转指令的下一句来计算的)。同样的，第二条跳转指令的计算是0x0d+0xf8=0x05

Implementing Conditional Branches with Conditional Control

  1. 我们可以使用跳转指令实现C语言的if-else，C语言的if-else的一般形式为： 
    1
    2
    3
    4
    if(test-expr)
        then-statement
    else 
        else-statement
    那么对应的汇编实现方式是(这里用C语言的goto语法表示)： 
    1
    2
    3
    4
    5
    6
    7
    8
        t = test-expr;
        if(!t)
            goto false;
        then-statement
        goto done;
    false:
        else-statement;
    done:

Implementing Conditional Branches with Conditional Moves

  1. 上面我们介绍了通过JMP指令实现控制的转移，也就是通过JMP指令决定下一句该执行什么指令，以此来实现了if-else(Conditional Jump)。这一章我们介绍一种效率更高，但是使用场景受限的数据转移方式实现的if-else(Conditional Move)。
  2. Conditional Move的原理就是把if-else不同情况下的结果先计算出来，然后通过cmov语句把结果放到对应寄存器中，由于计算机的CPU的计算能力都是很快的，对于Conditional Jump，在没有到达需要跳转的语句之前，计算机只能尽可能的猜测下一步执行的命令并进行计算，但一旦condition的结果与计算机猜测的不同，那么计算机需要重新执行另一个分支的命令。但是对于Conditional Move来说，不存在计算机选择分支的情况，所有的命令结果都会被加载进CPU进行计算，所以相对来说效率更高。
  3. 但是书中也提到了，只有if-else的命令很简单(比如只是一条add语句)的时候，CPU才会使用conditional move，其他情况下还是使用conditiaonl jump，所以感觉没啥大用，只是作者在这里提一下，说明这是一个潜在的优化可能。

Loops

Do-While Loops

  1. Do-While的C语言goto代码： 
    1
    2
    3
    4
    5
    loop:
        body_statement
        t = test-expr;
        if (t)
            goto loop;

While Loops

  1. While的C语言goto代码有两种形式，已汇总时jump to middle： 
    1
    2
    3
    4
    5
    6
    7
        goto test;
    loop:
        body-statement
    test:
        t = test-expr;
        if (t)
            goto loop;
  2. 另一种形式叫做guarded do： 
    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 Loops

  1. For Loops与While Loops是等价的： 
    1
    2
    for(init-expr; test-expr; update-expr)
        body-statement
    等价于 
    1
    2
    3
    4
    5
    init-expr;
    while (test-expr) {
        body-statement
        update-expr;
    }
    所以For Loops的汇编代码可以用While Loops的两种形式来表示。

Procedures

  1. 过程(或者叫做函数，方法等)是程序执行的一种重要抽象，几乎所有的编程语言都实现了过程。假设有一个过程P调用过程Q，Q执行后返回到P，那么我们需要下面的机制来完成这个操作：
    • Passing control：程序计数器(Program counter，PC)必须指向Q过程代码的起始地址，并且在Q执行完返回P的时候，PC回到原本P过程的执行代码的地址。
    • Passing data：P可以传递参数给Q，Q可以传递返回值给P。
    • Allocating and deallocating memory：在Q过程开始时，可能需要为局部变量分配内存空间，并且在返回P前释放这些空间。

The Run-Time Stack

  1. 前面在介绍pushq和popq指令的时候已经简单介绍过后入先出的栈结构：x86-64的栈朝着低地址方向增长，并且栈指针%rsp指向栈的顶部。
  2. 图3.25展示了栈的结构，当x86-64的过程需要的储存空间超过寄存器能够存放的大小时，就会在栈上分配空间，这个空间称作栈帧(stack frame)，也就是说每一个过程都会有自己的栈帧并且正在执行的过程总是在栈顶。大多数的栈帧都是固定大小的，它的大小在过程开始的时候被分配好，但是也有一些过程的栈帧不是固定大小，这部分内容会在后面介绍。
  3. 栈帧有多个部分组成，负责存储不同的变量，x86-64只会在需要储存相应变量时才会分配相应的栈帧部分。比如如果一个过程所需的变量数量不多(都可以储存在寄存器中)，并且不调用其他过程，那么就完全不需要分配栈帧。

Control Transfer

  1. 如果我们想要从函数P跳到函数Q，可以很简单的把PC指向Q函数代码的起始地址，但是问题是在执行完Q函数以后，我们需要知道应该返回到P函数的什么位置。x86-64通过call Q指令解决上述问题，call Q指令的作用是把地址A压入栈(push to stack)，并把PC设置为Q的起始地址。这个地址A被叫做返回地址(return address)，它的值是call命令紧邻这的下一句指令的地址。
  2. 书中图3.26展示了执行call指令是栈以及寄存器的变化。注意到%rsp早执行完call指令后从0x7fffffffe840变成0x7fffffffe838，可以看出这里把返回地址压入了栈，并且返回地址是8字节。

Data Transfer

  1. x86-64的寄存器可以存储最多六个函数参数(图3.28)，如果函数参数多于六个，那么这些参数会被储存在图3.25的Argument build area，并且Argument 7在栈顶。

Local Storage

  1. 某些情况下，函数中的局部变量需要存储在栈上：
    • 没有足够的寄存器储存本地变量
    • 使用了&操作符去获取变量地址，这个时候我们需要将本地变量储存在栈上，因为寄存器没有地址
    • 数组或者结构需要储存在栈上

Local Storage in Registers

  1. 前面我们提及到，函数参数或者局部变量都可以保存在寄存器中，但是所有的函数都共用这些有限的寄存器，我们如何保证我们想要保存在寄存器中的值不被call的函数改变呢？x86-64因此将寄存器分为两类：
    • callee saved registers：%rbx，%rbp。%r12-%r15。当过程P调用过程Q的时候，过程Q必须先将这些寄存器的值压入栈顶，也就是图3.25的save registers部分，这样Q才能自由使用这些寄存器，在返回到P过程前会把栈中保存的值弹出。
    • caller saved registers：除了栈指针%rsp以外的其他寄存器。这些寄存器所有的函数都可以修改，所以如果还是P调用Q，那么过程P必须先把使用到的caller save registers压入堆栈，因为Q不负责帮P保存这些寄存器的值。一旦P没有保存，而Q又使用了这些寄存器，那么就会导致错误。

Array Allocation and Access

Basic Principles

  1. 假设有一个数组T A[N]，数组的起始地址是X，数组中每个数据的长度是L字节，那么数组中第i个元素的地址就是X+L*i
  2. 假设我们有一个指针p指向数组A，那么对于指针的运算结果p+i等于X+L*i。

Nested Arrays

  1. 嵌套数组在栈上是连续排列的，顺序是从左到右，从上到下的，参考图3.36.

Heterogeneous Data Structures

Data Alignment

  1. 假设处理器每次读取内存的时候都会抓取8字节的数据，那么地址必须为8的倍数。如果我们在内存中存储了一个double数据，并且不按照8的倍数对齐数数据，那么我们需要两次内存访问才能抓取到这个double。x86-64硬件在没有数据对齐的情况下也可以正确工作，但是Intel建议使用数据对齐以提升内存系统的效率。对齐原则是任何K字节的基本对象的地址必须是K的倍数。书中有两个比较好理解的图例。 
    1
    2
    3
    4
    5
    K  | 类型
    1   char
    2   short
    4   int, float
    8   long, double, char*

Combining Control and Data in Machines-Level Programs

  1. 这一章buffer overflow以及放置它的一些措施。最常见的就是我们声明了一个不定长数组，然后我们越界了，程序修改了他不该修改的内存。

The Memory Hierarchy

Storage Technologies

  1. 简单介绍了一下内存，磁盘，固态的原理和历史以及如何通过总线与CPU进行数据交换

Locality

  1. 局部性主要有两种，时间局部性和空间局部性。时间局部性指的是一块内存区域被引用后会在不远的将来多次再被引用，空间局部性指的是一块内存空间被引用后，附近的内存会在不远的将来多次再被引用。

The Memory Hierarchy

  1. 书中图6.21介绍了存储器的体系结构、一般来说，当我们从高层向底层移动的时候，存储设备变得更慢，更便宜，更大。上层的存储设备为下层的存储设备提供缓存。缓存是计算机体系结构中随处可见的东西，使用了局部性原理，之前学习计算机网络的时候也见过很多缓存使用的例子。

Cache Memories

  1. 早期的存储器体系结构中只有CPU寄存器，主存和磁盘，但是随着CPU和主存之间的速度逐渐加大，系统设计者被迫在CPU寄存器和主存之间插入了一个小的SRAM高速缓存存储器，称为L1高速缓存(一级缓存)。随着CPU和主存之间的性能差距不断增大，系统设计者在L1高速缓存和主存之间有插入了一个更大的高速缓存，称为L2高速缓存，有的现代系统中还包括一个更大的L3高速缓存。在本节的讨论中，我们假设一个简单的存储器结构，也就是CPU和主存之间只有一个L1高速缓存。

Generic Cache Memory Organization

  1. 书中图6.25展示了高速缓存存储器的结构，假设我们要用高速缓存存储器来缓存一个有着m位地址的内存(大小是2的m次方)，那么我们可以把这m位地址分成三部分，用来在高速缓存存储器中尝试寻找缓存(类似hash table)。高速缓存存储器的大小等于S*E*B，其中S代表高速缓存的set数量，E代表每个set中的line的数量，B代表每一条line的缓存块(cache block)可以缓存B bytes的数据。

Direct-Mapped Caches

  1. 如果E等于1，也就是每个set中只有一条line，那么这样的高速缓存叫做Direct-Mapped Caches。CPU读取高速缓存以查看想要读取的内存地址是否在高速缓存中的过程可以分为三步：
    • set selection：m位地址被分成三部分，通过其中的Set index位可以确认我们想要选中的set
    • line matching：由于E等于1，所以代表着set中只有一条line，所以我们需要做的比较m位地址中的Tag位与选中的line的tag位是否相等，相等代表cache hit，不相等代表cache miss
    • word extraction：如果cache hit，那么可以通过m位地址中的Block offset位，来从Cache block中获取想要查询的地址的内存数据
    • line replacement on misses in diorect-mapped caches：如果发生了cache misses，那么CPU会去主存中获取相应地址的数据，并且把它缓存在高速缓存上，如果此时高速缓存已满，那么代替规则很简单：目前被选中的line会被新的line代替(这里没有使用诸如LRU或者LFU这样的算法)
  2. Conflict Misses in Direct-Mapped Caches: 由于高速缓存的大小是远小于内存的，所以不同的内存可能映射到同一块cache block上，所以可能会出现一块cache block上的内容被不断刷新的情况。

Set Associative Caches

  1. 对于1<E<C/B的情况，我们称作Set Associative Caches。比起Direct-Mapped Caches，Set Associative Caches更容易避免Conflict Misses，因为一条set中有多条line。
  2. 代替算法：对于一个set有多个line的情况，如果出现cache miss并且所有的line都已经有数据的情况下，需要使用LFU或者LRU这样的算法

Fully Associative Caches

  1. 高速缓存只有一个set，这个set含有全部的line。

Putting It Together: The Impact of Caches on Program Permormance

Exploiting Locality in your program

1.三条建议：
- 当有多层循环的时候，更多的关注内层循环的局部性问题
- 尽可能的使用步长1来读数据，因为附近的数据很可能已经被缓存在高速缓存中了，不要跳跃着读数据(这就是为什么读取二维数组的时候要一行一行读，不要一列一列读)，这可以最大可能利用空间局部性
- 一旦存储器中读入了一个数据对象，就尽可能的多使用它，从而使得程序中的时间局部性最大

Linking

  1. CSAPP的链接讲的有点概括，直接读很难读懂，相关的知识推荐阅读程序员的自我修养，这本书对于链接的讲解很透彻。由于CSAPP不过多展开链接的内容，这里我也只是简单了解一下大概。

Compiler Drivers

  1. 假设我们有两个C语言源文件main.c和sum.c，当我们执行gcc -Og -o prog main.c sum.c指令生成可执行文件的过程是这样的：
    • 首先调用C预处理器cpp对源文件进行预处理，比如替换#define和#include这些预处理命令，生成main.i和sum.i
    • 然后调用C编译器cc1对预处理过的文件进行编译，将C语言编译成汇编语言。编译的过程包括语法分析，词法分析，语义分析等步骤，这些都属于编译原理这门课的内容。生成的结果是main.s和sum.s
    • 然后调用C汇编器as将汇编语言汇编成对应的二进制的可重定位目标文件(relocatable object file)，这项工作相对简单，只需要将汇编语言与机器码进行映射即可。生成的结果是main.o和sum.o
    • 最后调用C链接器ld将可重定位目标文件main.o和sum.o以及某些需要的系统对象文件一起链接成可执行对象文件(executable object file)

Static Linking

  1. 静态链接主要做两个事情：
    • 符号解析(symbol resolution)：目标文件定义并且引用符号，每个符号对应一个函数，全局变量或者静态变量。符号在一个目标文件是唯一的，但是多个目标文件中可能有相同的符号，所以符号解析的目的是确保一个符号引用只对应一个符号的定义
    • 重定位(relocation)：编译器和汇编器生成的目标文件使用的都是从0开始的假地址，链接器会把目标文件的段(section)重定位成操作系统的虚拟地址，并且修改所有符号的地址

Object Files

  1. 对象文件有三种形式：
    • 可重定位目标文件：汇编器生成的，需要链接以后才能被执行
    • 可执行目标文件：链接器生成的
    • 共享目标文件：一种可以在加载或者运行时期被动态的加载进内存并链接的目标文件，用在动态链接的部分

Relocatable Object Files

  1. 图7.2展示了ELF格式的可重定位目标文件。
    • ELF header描述了目标文件的信息，包括word size，byte ordering，目标文件类型(relocatable, executable, or shared)，机器类别(比如x86-64)，section header table的偏移位置(用来找到section header table的位置)，section header table的大小和存储条目的数量。
    • 通过section header table的偏移位置，系统可以找到section header table，这里描述了这个对象文件所包含的所有的section(他们的大小和位置)
    • 其他的部分都是这个目标文件的section
      • .text 保存机器码的section
      • .data 保存初始化的全局变量和静态变量，需要注意的是，局部变量是不保存在section中的，它们都是在runtime的时候有cpu生成在stack上的
      • .bss 保存未初始化的全局变量和静态变量，或者初始化为0的全局变量和静态变量。这些变量不会占据目标文件的大小，他们仅仅作为占位符，当把对象文件加载到内存中的时候，这里的变量自动声明位0。 .bss段的好处是节省了目标文件的空间
      • .symtab 保存符号表
      • .rel .text .text段保存的机器码指令可能调用外部函数或者引用全局变量(比如call main，然后main函数的定义在另一个目标文件)，汇编过后的代码使用的地址是假地址，在链接的时候我们需要替换成虚拟地址，这个时候我们需要使用这个段的信息，告诉我们哪些指令需要进行重定位
      • .rel .data 如果一个变量保存的是一个全局变量的地址或者外部函数的地址，那么它的值在链接期间也需要重定位

Symbols and Symbol Tables

  1. 下面是一个Symbol Table的例子： 
    1
    2
    3
    4
    Num:    Value           Size Type   Bind    Vis         Ndx Name
    8:  0000000000000000    24  FUNC    GLOBAL  DEFAULT     1   main
    9:  0000000000000000    8   OBJECT  GLOBAL  DEFAULT     3   array
    10: 0000000000000000    0   NOTYPE  GLOBAL  DEFAULT     und sum
    Value表示的是相对于所在段起点的地址，Type表示这个符号的类型，Ndx表示这个符号属于哪个段(1表示属于.text，3表示属于.data，undefine表示这个符号在这个目标文件中有引用，但是它的定义在其它目标文件)

Symbol Resolution

  1. 讲解了如果多个目标文件中有相同的symbol该如何解决，以及库文件是如何被链接进去的，具体内容可以看书

Relocation

  1. 经过Symbol Resolution步骤，现在代码中的每个符号都只和一个符号定义关联，下面可以开始重定位步骤：
    • Relocating sections and symbol defination：这一步，链接器把多个目标文件中相同的段合并在一起，并为它们分配虚拟地址
    • Relocating symbol references within sections：代码段和数据段中会使用到符号，链接器会将它们指向的地址重定位
  2. 具体内容可以看书

Loading Executable Object Files

  1. 图7.15展示了可执行文件是如何映射到虚拟地址中的。
  2. 装载程序的过程：
    • 首先把二进制可执行文件加载到虚拟内存的代码段和数据段
    • loader跳到程序的起点，一般是_start函数的地址，这个函数被定义在系统对象文件crt1.o中
    • _start函数调用系统启动函数__libc_start_main，这个函数被定义在libc.so中，负责初始化执行唤醒，调用用户的main函数，处理返回值等

动态链接

  1. 这部分知识后面有时间再去细看。

Exception Control Flow

  1. 控制流(control flow)指的是程序指令一条一条的执行的序列。最简单的控制流就是每一条指令都位于相邻的内存中，一条接一条的平滑的执行下去。如果想要改变这种简单的空指令，我们可以使用前面学习过的jumps，calls，return等跳转指令，这些指令根据内部程序变量的值决定跳转的目的地。除了通过内部程序的值来改变控制流，我们的程序也需要能够对系统的变化做出反应，比如一个硬件定时器定期产生信号，这个事件必须处理；包到达网络适配器后，程序必须将其存放在内存中；子进程终止时，创造这些子进程的父进程必须得到通知。这些都是通过异常控制流来进行处理的。
  2. 本章描述了在计算机系统各个层级的异常处理流(Exception Control Flow, ECF)。首先介绍的是位于硬件和操作系统交接部分的异常(会讨论系统调用，它们是为应用程序提供从操作系统接口的异常)；然后介绍位于操作系统和应用交接部分的信号；最后讨论应用层中的非本地跳转。

Exceptions

  1. 异常(这里的异常与我们常说的Java异常不是一回事，这里是硬件的异常)是由于处理器的状态发生了某些重大变化，当前的控制流需要改变，转而去处理这个异常。触发异常的信号可能与正在执行的指令有关，比如由于当前指令的操作导致了虚拟内存的页错误或者当前指令进行了除0操作；另一方面，触发异常的信号也可能完全与当前指令无关，比如一个系统定时器计时结束或者一个硬件I/O请求完成。
  2. 异常发生后，会有对应的exception handler对异常进行处理，处理结束后，根据异常种类的不同，会有三种结果发生：
    • exception handler将控制返回给当前指令，也就是异常发生时正在执行的指令
    • exception handler将控制返回给下一条指令，也就是如果没有异常发生将会执行的下一条指令
    • exception handler终止被中断的程序

Exception Handling

  1. 系统中每一种异常都被赋予一个单独的非负整数，叫做exception number，这些数字有的是处理器的设计人员赋予的，比如页错误，overflow；有的是操作系统内核的设计人员赋予的，比如系统调用和外部I/O设备的信号。在系统启动的时候，操作系统会生成一张异常表(exception table)，里面存放着exception number和其对应的handler。一旦硬件触发了异常，剩下的工作有是有软件，也就是exception handler来完成的。
  2. 对于异常的处理非常像调用程序，但是有一些不同之处：
    • 程序调用会把返回地址放入栈中，但是根据异常的不同，异常处理的返回地址可能是当前指令，也可能是下一个指令
    • 处理器会把某些额外的处理器状态压入栈中当调用exception handler的时候，这些状态会用来帮助恢复被中断的程序
    • 由于异常处理程序写在操作系统内核中，所以前面提到的压入栈指的是内核栈，而不是用户栈
    • 异常处理程序运行在内核模式下，这意味着它对所有的系统资源都有完全的访问权限

Classes of Exceptions

  1. 如书中图8.4所示，异常分为四种类别，后面本章中主要讨论的异常是系统调用。
  2. 系统调用的作用是给予用户某些操作硬件系统的接口，比如用户想要读取硬件上的某些文件，或者想要新建一个进程的时候，我们的操作系统需要提供某种接口，用户通过调用这个接口，通知操作系统自己想要进行的硬件操作，随后操作系统就可以对硬件进行相应的操作了。 从一个程序员的角度，系统调用和常规的函数调用是完全相同的，但是它们的内部是现实完全不同的，常规的函数调用工作在用户态，只是改变程序的执行流程；系统调用工作在内核态，因为他需要更高的权限以进行硬件的操作。

Processes

  1. 进程的定义是一个执行中程序的实例，系统中的每个程序都运行在某个进行的上下文(context)中。上下文是由程序正确运行所需的状态组成的，这个状态包括存放在内存中的程序代码和数据，栈，通用寄存器，PC，环境变量等。
  2. 本书不会具体讨论操作系统是如何实现进程的，但是会关注进程提供给应用程序的关键抽象：
    • 一个独立的逻辑控制流(logic control flow)，使得我们的程序看起来在独占的使用处理器
    • 一个私有的地址空间，使得我们的程序看起来在独占的使用内存系统

Logical Control Flow

  1. 图8.12展示了逻辑控制流，在计算机上有A，B，C三个进程同时在运行，处理器不断执行A->B->C->A->B->C，由于切换的时间很短，所以看起来处理器一直在处理一个进程，A执行的流程就是一个逻辑控制流。

Concurrent Flows

  1. 并发流指的是两条逻辑流(两个进程)在执行的时候有重合的时间，在图8.12中，A和B，A和C都是并发流，因为他们执行的时候有重合的时间，但是B和C不是并发流。需要强调的是，并发流和计算机CPU核数无关，即使多个进程运行在单核CPU上，只要他们的运行时间存在重合，他们就是并发流。如果两条逻辑流(两个进程)同时运行在不同的核上，那么我们称它们并行流。
  2. 并行与并发：https://www.zhihu.com/question/33515481

Private Address Space

  1. 图8.13展示了进程的地址空间

User and Kernel Modes

  1. 处理器中在某些控制寄存器中提供一个模式位，表明现在系统处于用户模式还是内核模式，处理器在内核模式可以执行指令集中的所有指令并且获取任意内存地址的数据，但是如果处理器处于用户模式，那么某些特权指令就不被允许执行(比如进行I/O操作)，也不允许获取内核区域内存的代码和数据。用户模式如果想执行这些指令或者获取内核区域内存的东西，必须使用系统调用。
  2. 一个运行普通应用的进程刚开始工作在用户蔑视，唯一可以使它切换到内核模式的方式是通过异常，当发生异常的时候，控制权会被转移到exception handler处，处理器会切换到内核模式进行异常处理，处理结束后返回应用，在切换成用户模式。

Context Switches

  1. 上下文切换：
    • 保存当前进程的上下文
    • 恢复某个之前保存的进程的上下文
    • 将控制权交到这个恢复的进程

Process Control

Creating and Terminating Processes

  1. 一个父进程想要创建一个新的子进程，那么可以调用fork函数。新创建的子进程与父进程非常相似，子进程会得到父进程用户级别虚拟地址的靠背，包括代码和数据段，堆和栈，子进程也会得到父进程的open file desciptors(所以子进程可以读或者写任何父进程打开的文件)。子进程与父进程最大的不同在于PID(process ID)不同。
  2. fork函数有趣的地方在于它被调用一次，却会被返回两次。在父进程中会返回生成的子进程的PID，在子进程中会返回0。子进程和父进程并发运行，所以执行顺序是不确定的。
  3. 子进程的特点：
    • Duplicate but seperate address spaces：由于子进程在生成的时候是对父进程的拷贝，所以他们有着完全一样的上下文，但是由于他们是不同的进程，所以他们的虚拟地址不同，所以内存只是拷贝，而不是共享。
    • Shared files：前面说了进行了拷贝，而不是共享，但是对于父进程打开的文件，两个进程是共享的。

Reaping Child Processes

  1. 一个进程因为某些原因终止了，系统并不会立即把它从系统中清除，相反，进程被保持在一种已终止的状态，直到它被父进程回收(reap)。一个被终止但是没有被回收的子进程叫做僵尸进程。
  2. 系统中有一个init进程，它的PID是1，是由内核在系统启动的时候创建的，永远不会终止，并且是所有进程的祖先。如果一个进程在终止前没有回收它的僵尸进程，那么内核会让init进程去回收这个僵尸进程。但是对于某些长期运作的程序，比如shell或者服务器，他们总是应该回收这些僵尸进程，因为这些僵尸进程在运行的时候仍旧消耗内存资源。
  3. 孤儿进程指当一个父进程退出，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。孤儿进程将被init进程(进程号为1)所收养，并由init进程对它们完成状态收集工作。
  4. 一个进程通过调用waitpid函数来等待它的子进程终止或者停止： 
    1
    2
    3
    4
    #include <sys/types.h>
    #include <sys/wait.h>

    pid_t waitpid(pid_t pid, int  *statusp, int options);
    默认的时候options等于0，这个时候waitpid会阻塞父进程直到一个wait set中的子进程终止。书中还列举一些其它的选项。
  5. wait set中的成员是这么决定的：
    • 如果pid>0，那么wait set中只有PID等于pid的子进程
    • 如果pid=-1，那么wait set中包含父进程的所有子进程
    • waitpid函数还包括其他种类的wait set，包括unix进程组，但是这本书中不讨论

Loading and Running Programs

  1. execve函数负责在当前进程的上下文中加载并运行一个新的可执行程序： 
    1
    2
    3
    #include <unistd.h>

    int execve(const char *filename, const char *argv[], const char *envp[]);
    execve函数与fork函数执行一次返回两次不同，execve函数执行一次，却从不返回，除非是诸如filename找不到这种错误发生才会返回调用程序，否则永远不会返回。

Signals

Signal Terminology

  1. 一个信号被发送到目的地进程分为两个步骤：
    • 发送信号：操作系统内核通过改变目的地进程的某些上下文状态，来通知目的地进程某个信号已经发送了。发送信号一般有两种原因。一种是操作系统内核检测到某些系统事件(比如divide-by-zero error或者一个子进程的终止)；另一种是一个进程通过调用kill函数，来显式的请求内核发送一个信号到目的地进程。一个进程可以给自己发信号
    • 收取信号：目的地进程收到了内核发来的信号，它可以忽略，终止或者通过执行用户级别的signal handler来处理信号
  2. 一个被发送但是还没有被接收的信号叫做待处理信号(pending signal)，任何时间，同一种信号只能有一个等待信号，后面相同的信号不会进入队列，而是直接被丢掉。
  3. 一个进程可以有选择性的阻塞接收某种信号，当一种信号被每个进程阻塞时，他任然可以被发送，但是产生的待处理信号不会被接收。
  4. pending和blocked的实现原理是内核会为每个进程维护一个pending位向量和blocked位向量。

Sending Signals

  1. Unix系统提供了很多发送信号的机制，这些机制都依赖进程组的概念。每一个进程都属于一个进程组，一个进程默认的进程组与它父进程的进程组相同。
  2. /bin/kill程序可以用来发送信号到另一个进程： 
    1
    linux> /bin/kill -9 15213
    执行上面的命令，会发送第九号信号(SIGKILL)到进程15213 
    1
    linux> /bin/kill -9 -15213
    如果一个PID是负的，代表这个信号会发送到这个进程组的所有进程中去
  3. 可以使用C语言的kill函数来发送信号： 
    1
    2
    3
    4
    #include <sys/types.h>
    #include <signal.h>

    int kill(pid_t pid, int sig);
    如果pid大于0，那么发送这个信号到这个进程；如果pid等于0，那么发送这个信号到当前进程的进程组的所有进程；如果pid小于0，那么发送这个信号到pid进程组的所有进程

Receiving Signals

  1. 当内核将一个进程p从内核模式切换到用户模式的时候(比如完成上下文切换或者从系统调用返回的时候)，它会检查未处理并且没有被阻塞(pending&~blocked)的信号，如果存在的话，内核会强迫进程p去接收信号(接收的顺序通常按照信号号从小到大)并进行某些处理，处理完以后才会执行进程原本的下一条指令。
  2. 进程对于信号的默认处理有以下几种：
    • 进程终止
    • 进程终止，并且把数据段和内存段的内容存储到磁盘中(dump core)
    • 进程停止(stop)，在收到SIGCONT信号之前保持停止
    • 进程忽略信号
  3. 可以使用signal函数自定义信号的handler： 
    1
    2
    3
    4
    #include <signal.h>
    typedef void (*sighandler_t)(int);

    sighandler_t signal(int signum, sighandler_t handler);

Blocking and Unblocking Signals

  1. 本章介绍了如何修改blocked位向量，具体函数见书

后三节

  1. 后三章介绍了如何编写signal handler来处理并发以及race condition。具体内容见书。

Nonlocal Jumps

Shell Lab

  1. 有的时候printf但是没有结果，这时候可能结果存在缓冲区内，可以使用fflush(stdout)强制打印
  2. 使用Sigprocmask(SIG_BLOCK, &mask_one, &prev_one);可以阻塞某些信号的处理，但是这些信号仍旧被线程接收到了，一旦把相应的blocked位解除，那么这些信号就会被处理。所以我们不需要担心fork子进程发送的SIGCHLD会由于父进程阻塞相应的信号而收不到，信号会被父进程收到，只是由于blocked位向量的存在不会立刻处理。
  3. 做完Shell Lab后对System call和Signal有了更好的了解，System call是操作系统提供的一些接口，我们可以利用这些接口做一些机器层面的操作；Signal是进程间交流的机制，比如子进程STOP或者TERMINATE都会像父进程发送SIGCHLD信号。System call中有一个kill函数可以用来发送信号，也就是我们使用这个接口可以人为的向进程发送信号。
  4. 进程中原本在运行的程序和Signal handler可能存在race condition，最好的例子就是我们要在运行的程序中addjobs，但是要在Signal handler中deletejobs，我们希望发生的顺序是当我们创建一个新的子进程后，就调用addjobs，然后当子进程运行结束后，我们通过SIGCHLD的Signal hanlder来执行deletejobs。但是由于子进程与父进程的执行顺序未知，会存在子进程先terminated，父进程的Signal handler被先于addjobs调用，这就产生了race condition。所以我们需要使用Sigprocmask在某些情况暂时阻塞某些信号的处理。

Virtual Memory

Physical and Virtual Addressing

  1. 计算机系统的主存被组织成一个连续的字节大小的单元组成的数组，每一个字节都有一个唯一的物理地址(Physical Address, PA)。由于有这样简单的组织方式，CPU访问内存最自然的方式就是使用物理地址，这种方法我们叫做物理寻址。早期的计算机，单片机，DSP等使用物理寻址。
  2. 现在计算机使用一种叫做虚拟寻址的技术，CPU生成虚拟地址，随后虚拟地址被MMU(memory management unit)转换成合适的物理地址，以该物理地址访问内存。将虚拟地址转换成物理地址被叫做地址翻译(address translation)，地址翻译需要CPU硬件与操作系统的紧密合作，用来进行地址翻译的硬件叫做MMU，它负责查询主存中存储的一个表，而这个表的维护由操作系统负责。

Address Spaces

  1. 物理地址空间就是一台计算机上物理地址的集合，虚拟地址空间指的是我们定义的虚拟地址的集合，现代系统通常支持32位或者64位的虚拟地址空间。对于内存上的同一byte，它在不同的地址空间的地址是独立的，它在虚拟地址空间可能有一个地址d1，而在物理地址空间有另一个地址d2，这也是为什么我们需要地址翻译存在的原因，本质上是不同地址空间之间的映射。

VM as a Tool for Caching

  1. 进程的虚拟内存被储存在磁盘上，然后使用物理内存作虚拟内存的缓存。假设我们计算机中有十个正在运行的进程，每个进程都有各自的N大小的虚拟地址，计算机的总物理地址是M，10*N肯定远大于M，那么为什么我们还能为每个进程分配看起来一致并且范围很大的虚拟地址呢？原因就在于每个进程正在使用的虚拟内存往往很小，大部分的虚拟内存都储存在磁盘上，只有正在使用的小部分虚拟内存被缓存到物理内存中，并被CPU访问
  2. 为了实现虚拟内存(被缓存的数据，存放在磁盘中)和物理内存(缓存地点)之间的数据交换，虚拟地址和物理地址都被进行了分页(page，与L1 cache的block概念相同，只是换了个名字)，每一页有P字节大小的数据。虚拟内存的每一页叫做虚拟页(virtual pages, VPs)，物理内存的每一页叫做物理页(physical pages, PPs)，物理页也被叫做页帧(page frames)。
  3. 任意时间，虚拟页被分成三种类别，例子见书中图9.3
    • Unallocated：VM系统还未分配(或者创建)的页，未分配的块没有任何数据，也就不占据任何磁盘空间
    • Caches：当前已缓存在物理内存中的已分配页
    • Uncaches：未缓存在物理内存中的已分配页
  4. 这里对虚拟内存和分页的理解有些错误，虚拟内存中未被使用的部分是不会映射到物理内存的，详情见操作系统部分。

DRAM Cache Organization

  1. 本书中用SRAM cache表示CPU和主存之间的L1, L2, L3缓存，用DRAM cache表示VM系统的缓存(在主存中缓存虚拟页)。由于从磁盘中读取数据相对较慢，所以DRAM缓存的不命中处罚(miss penalty)很大，所有虚拟页一般来说都很大，通常是4KB到2MB；DRAM缓存的替换策略也更重要，因为替换错了虚拟页的处罚也很高，所以DRAM缓存相比SRAM缓存使用更复杂的替换算法。

Page Tables

  1. 前面我们提到过MMU使用内存中的一个表来进行虚拟地址到物理地址的地址翻译，这个表叫做页表(Page Table)。地址翻译的过程会在后面详细介绍，本章只介绍页表的结构。页表就是一个PTE(page table entries)组成的数组，每一条PTE都有一个valid bit和n位的地址，如果valid bit是1，表示这个虚拟页已经缓存在内存中，对应的物理页的起始地址就是这个n位地址；如果valid bit是0并且n位地址不是空，那么表示这个虚拟页没有被缓存在内存中，n位地址表示其在磁盘中的位置；如果valid bit是0并且n位地址也是空，那么表示这个虚拟地址还未分配。
  2. 图9.4展示了一个页表的例子，页表的维护由操作系统负责。

Page Hits

  1. 我们想要访问的虚拟地址所在的虚拟页在页表上的valid set是1，表示这个虚拟页已经被内存所缓存了。

Page Faults

  1. 在虚拟内存的术语中，DRAM缓存的缓存不命中被叫做页错误。如果产生了页错误，那么会调用操作系统内核的页错误handler，handler会选择一个受害者页(victim page)来替换找不到的页。书中图9.6和9.7展示了页错误发生和处理的过程。

Allocating Pages

  1. 图9.8展示了操作系统如何分配新的页(比如在调用malloc函数后)

VM as a Tool for Memory Management

  1. 操作系统为每一个进程提供单独的页表，也就是说提供单独的地址空间。需要注意的是不同进程的虚拟页可以映射到同一处物理页。如书中图9.9所示。
  2. Demanding paging和seperate virtual address spaces为我们的系统提供了很多好处：
    • Simplifying linking：由于每个进程有独立的地址空间，而这些地址空间的格式又是相同的，所以我们内存段在虚拟地址的分布是固定的。比如代码段总是从虚拟地址的0x400000处开始，而我们不需要关注真正的物理地址。这种固定的虚拟地址为后续的链接起到了帮助，因为链接后的可执行文件使用的是虚拟地址而不是实际的物理地址
    • Simplifying loading
    • Simplifying sharing：计算机中同时运行的进程往往都会使用到C语言标准库和其他一些常用库文件，由于不同进程的虚拟页可以映射到同一处物理页，所以多个进程可以分享同一块物理页
    • Simplifying mempry allocation

VM as a Tool for Memory Protection

  1. VM为不同进程提供了分离的地址空间，我们可以通过简单的扩展页表来达到对物理地址的访问控制。图9.10展示了这种扩展，原理就是增加一些权限位，通过这些权限位可以判断是否有权限读或者写相应的物理地址。

Address Translation

  1. 图9.12展示了如何使用页表来进行地址翻译。首先，CPU有一个page table base register(PTBR)，指向当前进程的页表。n位的虚拟地址被分成两部分：p位的虚拟页偏移(virtaul page offset, VPO)和(n-p)位的虚拟页号(virtual page number, VPN)。MMU使用VPN来选择合适的PTE，比如VPN等于0的话选择PTE0，VPN等于1的话选择PTE1。得到PTE后，如果valid set为1，那么代表PTE中存储的就是虚拟页号(physical page number, PPN)，我们将PPN和PPO(physical page offset)连接得到最终的物理地址。
  2. PPO与VPO的值是一样的，因为PPN和VPN负责确认选中的是哪一页，在页中的偏移量对于虚拟页和物理页都是一样的。这其实很好理解，磁盘和内存之间不断交换的是页，页表的映射关系也是虚拟页和物理页的映射，当CPU想要请求某个地址的时候，这个地址在对应的虚拟页和物理页的偏移肯定是相同的。
  3. 页表保存在内存中，当MMU需要进行地址翻译工作时，不需要获取全部的页表，只需要根据VPN获取需要的那一条PTE就可以了

Integrating Caches and VM

  1. 图9.14展示了当存在L1缓存的时候该如何进行地址翻译。一般有两种做法，使用虚拟地址或者物理地址，也就是MMU在L1缓存的后面还是MMU在L1缓存的前面，大多数现代计算机的L1缓存使用物理地址作为缓存的地址。
  2. 前面我们说过，MMU从内存中获取PTE，然后使用PTE进行地址翻译，PTE和其他的数据一样也可以缓存在L1缓存中。

Speeding Up Address Translation with a TLB

  1. CPU每次生成一个地址，MMU都需要通过参考相应的PTE来将虚拟地址翻译成物理地址，在最差的情况下，我们需要从内存中获取PTE，那么需要几百个时钟周期，如果PTE恰好缓存在L1缓存中，那么获取时间会缩短到几个时钟周期。但是大多数的计算机系统都会通过添加一个更小的缓存translation lookaside buffer(TLB)来进一步减少这个时间。
  2. TLB是一个很小的使用虚拟寻址的缓存，通常TLB有着高相联度(一个set中有多个行)，但是每一行只储存一个block，这个block就是一个PTE。TLB的tag和index的获取见图9.15，由于一行只有一个block，所以不需要block offset。

Multi-Level Page Tables

  1. 前面我们假设一个进程使用一个页表来做地址翻译，但是对于32位和64位的虚拟地址空间，这样会导致页表很大，所以通常的做法是使用分级的树形结构页表。

Putting It Together

  1. 把前面介绍的地址翻译的知识结合起来，在这一章举了一个例子。

Case Study: The Intel Core i7/Linux Memory System

Core i7 address Translation

  1. 介绍了酷睿i7的地址翻译，可以结合书中的图进行理解。

Linux Virtual Memory System

  1. 图9.26展示了kernel virtual memory的具体组成，有些部分被所有进程分享，有的部分所有的进程都不相同。
  2. 图9.27展示了linux虚拟内存的组织形式，linux虚拟内存被分割成很多个区域(也叫段)，每一个区域都有一块连续的分配好的虚拟页组成，这些虚拟页的作用可能是类似的，比如我们已知的代码段，数据段，堆，共享库段，用户栈等，任何不属于这些段的虚拟内存都不存在，也不会占据磁盘资源。
  3. 当一个页错误被handler处理时，handler会进行下面的判断：
    • Segmentation fault：首先判断访问的段是否存在，不存在返回Segmentation fault
    • Protection execption：判断访问的段是否有权限
    • Normal page fault：常规的页错误，也就是找不到对应的页，需要去磁盘拉取

Memory Mapping

  1. 前面我们提到过虚拟内存本质上存储在磁盘上，虚拟内存以对象文件的形式存储在磁盘上，对象文件分为两种：
    • Regular file in the Linux file system：常规的磁盘文件，比如可执行对象文件，虚拟内存的数据段和代码段就是映射到可执行对象文件。由于系统采用按需进行页面调度(demanding paging)，所以这些磁盘中的虚拟页不会被加载到物理内存中，知道CPU第一次使用这些虚拟页
    • Anonymous file：匿名文件是为stack或者heap准备的，由于他们是在程序执行期间临时生成的变量，不像代码或者全局变量那样存储在可执行对象文件中，所以操作系统内核会创建一个匿名文件用来进行映射，匿名文件只含有二进制0。
  2. 一旦一个虚拟页被初始化了，那么它就会不断在内存和磁盘中进行交换(swap)，所以我们称它们为交换文件(swap file)或者交换空间(swap area)。交换空间的大小限制了当前进程所能分配的虚拟页数量。

Shared Objects Revisited

  1. 每个C语言程序都需要使用标准C语言库，如果每个进程都保存一份相同的代码在虚拟地址和磁盘，无疑很浪费空间，所以我们可以使用内存映射来解决这个问题。前面我们说过内存映射可以映射两种对象文件，而对象文件被映射的时候又可以被看作两种类型的对象：
    • A shared object：如图9.29，同一个文件被多个进程的虚拟内存所映射，如果在某一个进程中改变了共享对象，那么磁盘中的共享对象也会被改变，同时别的进程也会获知这个改变(因为文件只有一个，被所有进程共享)
    • A private object：如图9.30，同一个文件仍然可以被多个进程的虚拟内存映射，但是仅仅是可读的，一旦任意一个进程想要改变这个文件的某个页，那么就会触发protection fault，内核会在物理内存中建立那个尝试被修改页的拷贝，同时开启这个拷贝页的写权限。这叫做copy-on-write，可以让不同的进程最大限度的使用同一个私有对象，直到其中一个进程对私有对象进行了写操作

Dynamic Memory Allocation

  1. 介绍了heap中动态分配内存以及释放内存的数据结构和算法，具体内容见书

Garbage Collection

  1. 清理内存分为主动清理和自动清理，上一节介绍了C语言使用malloc和free函数分配和释放内存，这属于程序员主动清理。本章简单的介绍了如Java语言等存在的自动清理内存的方式-Garbage Collection。最简单的算法就是mark&sweep
#
Follow

Catalogue

×