CSAPP深入理解计算机系统笔记_不周山之读薄 csapp

csapp的学习从2019.3.18开始。从05.10-08.01这几个月一直工作，重心转去学了点软件工程和面向对象的东西，中断了这部分的学习。从08.01重新继续这部分的学习，但平时工作忙，只能挤出很少的时间。

---

前言：

如果是第一次看csapp这本书，建议先不要看，直接去看上交软院的课程主页，按照上面的课件学习。推荐一个个人博客“不周山之读薄CSAPP”，也可以按这个博客学习。

这本书的必读章节：1，2，3，5，7；选读章节：8，9；有更好替代的章节：4，6，第三部分（10，11，12）

第4，5，6章会感到稍许吃力，因为涉及很多硬件东西可能缺少铺垫，读的时候也可以先跳过。2-3章对应“汇编语言”；4-6章对应“计算机系统要素”；7-8章对应“程序员的自我修养”；9-12章对应“现代操作系统”

 

第二章：信息的表示和处理

2.1 信息的存储

2.2 整数的表示

2.3 整数算法

2.4 浮点数

2.5 总结

三种最常用的表示数字的方法：1）unsigned无符号整型， 2）two‘s-complement补码， 3）浮点型：2为基的科学记数法，用以表示实数

特点：整型表达可编码的数字范围较小但更精确，浮点型能编码的数字范围更大但只是近似表示。

了解数字在计算机中被表达（编码）的原理对于写出适用于全数域和移植性好的代码至关重要。

2.1 信息的存储

最小可寻址单元是字节byte，每个字节对应一个地址address。

hexadecimal notation：

2进制转16进制：快速写出2^11对应的十六进制数：2^11==(2^4)^2  *  2^3=0x800

words：

一个地址是用一个“字”来编码，每个机器上对应的字长也就是该机器的integer的长度，也与该机器上虚地址空间最大位置对应。例如，若字长为w位，则对应寻址空间为2^w字节。通常一个字要么是4字节（32位机），要么是8字节（64位机）

如今大多数机器的字长都是64位的。

data sizes：

数据类型char代表了一个单个字节，虽然从字面上看char类型应该是用于存储一个英文字母的，但它实际上也可用于存放整型数值。

在C语言中为不同数据类型分配的字节数通常如下表，当然也可能随机器和编译器改变而有所不同：

牢记下述准则：
* ANSI C标准规定，一个char的长度一定是8位。
*尽管没有规定int类型的长度是32位，但在Linux当前所有支持的体系结构中，它都是32位的。short类型也类似，虽然没有明文规定，但我们知道的都是16位的。
*决不应该假定指针和long的长度，它们原则上可以在32位和64位中变化。
*由于不同的体系结构long的长度不同，决不应该假设sizeof( int ) == sizeof( long )。
*类似地，也不要假设指针和int长度相等。
评注：C语言标准为各数据类型的具体字节数设置了下限但没有上限。在80年代32位机大行其道的时候，按当时的标准通常认为一个int类型的对象也可以用来保存指针。但时至今日多数机器已经是64位，所以以前的代码如果直接移植到现在的机器上来可能会产生问题。作为程序员，为了写出可移植性高的代码，必须尽量降低程序对数据类型真实长度的敏感性。

addressing and bytes ordering：

当一个保存在内存中的数据对象跨过了几个字节时，其占据的最低地址被认为是该对象的起始地址。比如，int x长度为4字节，在内存中占据的地址总共有四个：0x100，0x101，0x102，0x103，其地址就是0x100。在保存它的值时我们总是一个字节一个字节地存。假设我们想要保存的这个整型的值为x==0x01234567，分为01，23，45，67这四个字节来存，那么它保存在内存中的顺序有两种：

1）第一种big-endian，大端（尾）序。所谓大尾，也就是说字串的末尾放在大地址一侧（低位字节存放在高地址）：

2）第二种是little-endian，小端（尾）序。所谓小尾，也就是说把字串的尾巴放在小地址一侧（低位字节放在低地址）。注意，在保存每一个字节时该字节内部的位序总是顺序存储的：

注：如何记忆？从英文名称上顾名思义即可：big-endian，也就是说末尾放在大地址一侧；little-endian类比。也可以这样记忆：大端序是按照数字的书写顺序进行存储的，而小端序是颠倒书写顺序进行存储的。

一般来说如何处理这些存放方式是交给机器自己处理的，但有些时候程序员不得不亲自上手处理：

1）当需要在一个big-endian和一个little-endian机器之间传输数据时，必须协商和转换好数据信息，这需要程序员自己注意；

2）在进行机器级别的编程时，小端序机器产生的机器码中数据字节是与我们的阅读习惯反着的。

3）当使用强制类型转换来访问和打印不同类型对象在内存中的字节表示时。强制类型转换在系统级编程中很常用，比如如下代码：

void show_int(int x){
   show_bytes((unsigned char*)&x, sizeof(int));
}
 
void show_bytes(unsigned char* start, int len){
   for(int i=0; i<len; i++)
      printf("%.2x", start[i]); 
      //在这里使用数组表示法来引用指针，表示我们想要读取
      //以start指向的位置为起始的第i个位置处的字节
}

为了输出int x在内存中的字节表示，必须将指向int的指针强制转换为unsigned char*指针，这样就可以一次打印一个字节了。这种强制类型转换告诉编译器，程序应该把这个指针看成指向一个字节序列，而不是指向一个原始数据类型的对象。从输出结果我们可以看到该字节序列在内存中是按little endian还是big endian存放的。

另外有时候我们会直接以二进制文件来保存数据，读写二进制文件时就需要按字节操作并分清楚其采用的保存顺序，从而进行正确的解析。关于这一点可参考我另一篇文章中的介绍：https://mp.csdn.net/postedit/88124002

representing strings：

字串是以null（值为零）字符结尾的字符数组。英文字符可使用ASCII字符码进行编码；而更一般的语言文本可使用Unicode的统一字符集进行编码（每个字符使用4字节编码）。简化版的替代编码例如UTF-8，使用单字节编码一个字符（与ASCII一样）。

representing code：

即便是同样的机器，由于安装不同操作系统，导致同一段源代码编译后得到的机器码也是不同的。

introduction to boolean algebra：

布尔运算～：逻辑运算非NOT

布尔运算&：逻辑运算与AND

布尔运算|：逻辑运算或OR

布尔运算^：逻辑运算异或（两者一真一假时为真）

bit-level operations in C：

C的一个特点就是支持按位进行布尔运算，这些运算可以对任何“整型的”数据类型，如type char或int生效。

异或运算的结果体现的是两个操作数之间的不同（只有两个数在某位上不同时，对应结果位才为1；只要相同那么结果位就是0），记住以下三条关于异或的规则：

1) 0与任何数进行异或，不改变该数的值

2) 一个整数自己跟自己异或，结果为0   

3) 异或满足结合律和交换律

一个应用：怎样不使用额外的内存空间交换两个整型变量的值？

void inplace_swap(int* x, int* y)
{
   *y = *x ^ *y;
   *x = *x ^ *y;
   *y = *x ^ *y;
}

其实现过程是这样的：

这种交换过程是利用了异或运算体现了两个操作数之间的差异这一性质。当然，也有别的方法来实现原地交换，比如使用加法操作。先将a加上b，再利用这个新的a减去b就得到b，从而实现将b换成了a。

logical operations in C:

逻辑或，与，非操作：||，&&，！。任何非零的值在逻辑上都被看作TRUE，只有值为零时被看作FALSE。

shift operations in C：

shift操作从左边结合。例如，x<<i<<j满足左结合律，即等价于(x<<i)<<j。

加法运算的优先级高于shift操作。

左移时右边补零。

右移分为两种情况——逻辑右移：即右移时左边补零；算数右移：即右移时左边补最高位的值。例如，1001 0101算数右移4位得到：1111 1001。对于无符号数，必须使用逻辑右移；对于有符号数，原则上两种右移都可以采用，但实际中几乎所有编译器都使用算数右移。

2.2 整数的表示

整数的编码方法总体分为两种：一种只能表示非负整数；一种则能表示负数，零和正数。

integral data type：

在32位机上常见的C整形数据的数值表示范围如下表：

在64位机上，唯一的改变是long的范围变成了跟32位机上long long的范围一样，64位机上用8字节表示long，而32位机上用4字节。

64位机上的long long跟32位机维持一样。

注意：

C标准中只规定了数据类型最小的size，而不是规定精确的size，因而不同机器上使用long所表示的具体数值范围可能是不一样的，这一点要特别注意。为解决这一问题，在ISO C99中在文件stdint.h中引入了一种新的整数类：intN_t和uintN_t，用于显式地指定N位有符号和无符号整数。同时还定义了一些宏：INTN_MIN, INTN_MAX和UINTN_MAX表示N位数的最大最小值。

如果对int型能表示的整数范围不太有把握，只需记住：绝对值在10^9范围内的整数都可以定义为int型。如果超过了2*10^9，就最好采用long long来表示。

unsigned encodings:

无符号整形编码时，w位二进制数能表示的最大值为[1,1,...,1]，即UMax = 2^w-1，最小值为0。

two‘s-complement encodings：

最常用的负整数编码方式是使用补码：二进制数的最高位采用负权重：如1011 = -1*2^3+1*2^1+1*2^0 = -8+2+1 = -5。在这种编码方式下，最小的数形为：[1,0,...,0]；最大的数形为：[0,1,...,1]。即最小值为：TMin = -2^(w-1)，最大值为：TMax = 2^(w-1)-1。

在补码编码下，负整数-1的形式就是：[1,1,...,1]，这恰好是unsigned形式能表达的最大值。

关于补码原理的说明：

https://blog.csdn.net/qq_41230365/article/details/88763908

conversions between signed and unsigned：

UMax = 2TMax + 1：[0,1,...,1](TMax)->[1,1,...,1](UMax).

casting(强制类型转换)：数据的二进制表示都是相同的，只是解释这些bits的方式被改变了。

总结起来：当x的值处在范围：0<=x<=2^(w-1)时，其无符号和补码表示都是相同的；当超过这个范围，两种表示间相差2^w。

例子：

int i = -1;
unsigned int j = static_cast<unsigned int>(i);
cout << j <<endl;    //输出结果是2^32-1 == 4294967295

上面这种用法：unsigned int invalid_unsigned_int = static_cast<unsigned int>(-1);常用来表示能被写成unsigned整型的最大数字，在实际代码中时有见到。

signed vs. unsigned in C：

使用printf打印变量时，不考虑变量本身被声明的类型，而只看采用的是%d(有符号十进制), %u(无符号十进制)还是%x(十六进制)。例如：

int x = -1;
printf("x = %u = %d\n",x,x);

输出结果为：x = 4294967295 = -1.

当有符号数和无符号数之间产生运算时，C会隐式地把有符号数转换为无符号数。例如下面这个比较运算：

-1 < 0U，由于这里的0是无符号数，因此在比较时会先把-1转为unsigned，导致无符号的-1大于0.

又比如：

unsigned i;
for(i = cnt-2; i >= 0; i--)
   a[i] += a[i+1];

对于上面这个程序，将导致永远的循环。

更不容易debug的程序如：

#define DELTA sizeof(int)
 
for(int i=CNT; i-DELTA>=0; i-=DELTA)
   ...

在这里sizeof()函数返回的是一个unsigned的类型！！那么i-DELTA的结果也是一个unsigned，从而永远大于等于零！

正确使用unsigned作loop index的方法是：

unsigned i;
for(i = cnt-2; i < cnt; i--) //不要将unsigned与0比较，而是与其最大值比较
   a[i] += a[i+1] 

因为在C标准严格规定unsigned加法会类似modular算法一样，也就是0减去1得到的是UMAX。

更好的做法是：

size_t i;
for(i = cnt-2; i < cnt; i --)
   ...

这里size_t定义了长度等于word size的一个unsigned值。即使cnt==UMAX，代码也能运行。

expanding the bit representation of a number：

把无符号数扩展为一个更大的数字类型时，只需要加0即可（zero extension）；

把有符号数扩展为更大的数字类型时，需要采用sign extension，即把最高位（符号位）进行扩展。比如-8 = 1000 = 11000（-2^4 + 2^3 = -2^3*(2-1)）。解释：对一个有符号w位的二进制数，添加一个最高位1代表增加-2^w，由于增加了新最高位，原先的最高位就变为了正值2^(w-1)，因而新的值为-2^w+2^(w-1) = -2^(w-1)，与原先的值是一样的。

注意：从short变为unsigned int的(C标准要求)步骤：先把short扩展为int，再把int变为unsigned int；而不是先unsigned short，再unsigned int。

truncating numbers：

把w位数字截取为k位时，直接丢掉高w-k位。

对于无符号数x，截取为k位等价于取模（余）：x mod 2^k，直接理解就是把高于2^k权重的位全扔掉，只保留小于2^k权重的余数。

对于补码形式的x，先当作无符号数那样取模x mod 2^k，再将结果转为有符号数。比如：

-6 = 1 1010-->1010，截取为4位，仍为-6。-6 mod 2^4 = (26u mod 16) = 10u = -6。

如果在截取时符号位的值发生了改变，即符号发生了改变，则值可能变化。例如：

10 = 0 1010-->1010，变为了-6。10 mod 16 = (10u mod 16) = 10u = -6。

 

2.3 整型算法

unsigned addition:

由于机器能保存的字长是有限的，故计算和的时候可能会发生溢出。这导致的效果跟数学上的模运算效果是一样的。也就是说，我们可以使用模运算来描述计算机上进行无符号运算的特性。例如下面的代码，233+213的和是446，但由于8位长度模为256，溢出舍去最高位后实际的运算结果是190，这与446 mod 256=190是一致的。

unsigned char  1110 1001    E9    233
             + 1101 0101  + D5  + 213
             -----------  ----  -----
             1 1011 1110  1 BE    446
             -----------  ----  -----
               1011 1110    BE    190

two's-complement addition:

补码的加法在bit-level上的操作与无符号加法是一样的，不产生溢出时其结果可以理解，只不过在产生溢出时其结果较难理解。以4bits为例，其补码能表示的范围是[-8, 7]。当求和结果超过范围时，分为两种溢出情况：

若sum >= 2^(w-1)（正溢出）：值变成负值。例如：

0101(5)+0101(5)=01010(10)，舍最高位，得到1010(-6)。

若sum < -2^(w-1)（负溢出） ：值变为正值。例如：

1000(-8)+1011(-5) = 10011(-13),舍最高位，得到0011(3)

two's-complement negation:

...

unsigned multiplication:

两个w-bit的数相乘，乘积最大字长为2w bits。故而做乘法时可能需要扩展字长，当然这是交给软件来做。默认处理方法仍然是截断，其效果就是module运算。

two's-complement multiplication:

两个w-bit的数相乘，最小值(负)可达：2w-1 bits；最大值(正)可达：2w bits

multiplying by constants:

如果是乘以2^k，直接左移k位即可。可利用这种移位来构造对任意数的乘法：

（u<<5）-（u<<3）== u*24

大多数机器执行移位比执行乘法快，编译器自动产生上述的代码。

从理论上讲，二进制乘法运算过程如下：

           1010
           1110    拆为1*2^3 + 1*2^2 + 1*2^1 + 0*2^0
       --------
           0000    先乘以0*2^0
          1010     再乘以1*2^1，即左移一位
         1010      ...
        1010
       --------
       10001100    各项累加起来

dividing by powers of two:

unsigned：如果是除以2^k，直接右移k位即可（逻辑右移补最高位）。

two‘s complement：

y      -951 1111_1100 0100_1001
y>>4   -60  1111_1111 1100_0100  真实结果应该是-59.4375

当无法整除时要舍入，区别在于：补码计算舍入时是往负无穷方向取约数(round)，而无符号数是往0取约数。

乘以一个非2^k的数可以转变为2^m-2^n这种形式，但在除法中没有这种类似的处理方法。

negation：complement & increment：

将补码按位取反（包括符号位也取反）再加一得到的是原数的相反数，因为：~x + x==11...11==-1，所以~x + 1 == -x

这里有个特例是对Tmin(1000)求相反数：按位取反为0111，加1得到1000。也就是说Tmin的相反数还是Tmin！

final thoughts on integer arithmetic:

...

2.4 浮点数

fractional binary numbers：

首先我们类比常用的十进制小数的表达方式，看一下如果类比地用在二进制数上，得到的表达式如何理解。

1011.101代表什么意义？

小数点右边依次代表2^(-1)，2^(-2)...代表分数。

值                表达式
5 3/4 = 23/4      101.11     = 4+1+1/2+1/4
2 7/8 = 23/8       10.111    = 2+1/2+1/4+1/8
1 7/16= 23/16       1.0111   = 1+1/4+1/8+1/16     

从上面可以看到：

* 小数点的位置是不变的，我们把二进制表达式右移意味着除以二

* 0.11111...这个数的值无限接近1.0但比1.0小

* 能精确表达的只是x/2^k这种形式的值，其他有理数会出现无穷循环，如1/3=0.0101010101...

注意，由于计算机只能精确地表示x/2^k这样形式的数，所以很多小数都只能近似表示。事实上，对于所有的最后一位以5结尾的十进制有限小数，都可以化成二进制的有限小数（虽然这个小数可能长到没谱），而不是以5结尾的小数就不可能精确地表示为二进制浮点数。所以，由于浮点数的非精确存储，在程序中两个浮点数往往不能直接比较相等，而只能使用“if(fabs(x-y) < epsilon )”这种方法。在这个链接中有相关说明。

ieee floating-point representation：

如果采用上一节介绍的方法（即定点表示法positional notation，与浮点相对），本质上是使用小数点位置来表征每个数位的权重。这种方法的缺点是不够高效，随着数位增多，每两位之间的所表示的权值差越来越小，因此为了表达一个很接近于0的小数，需要用相当长的数位（这其实就是y=2^x这个函数在趋近于x轴时的特性）。为了解决在有限位数里，能表示的小数太少 这一问题，我们采用下面介绍的二进制编码方法，即直接给出科学记数法 x * 2^y 中x和y的值。

关于为什么浮点数编码方式来编码小数，在这个链接中作了更详细的解释：https://www.jianshu.com/p/a755e01e6eb4

在制定浮点数标准时，numerical analyst主导而非硬件设计师主导，这在标准制定的历史上是很罕见的。这些标准很好地支持了rounding，overflow，underflow，但在硬件上很难再提升速度。

在ieee标准中，规定浮点数以科学记数法形式表示：。例如： 。其中：

* 符号位s：决定其正负；

* 有效数字M：通常是位于[1.0，2.0)的一个分数。实际上，这部分的编码方式就是上面介绍过的定点小数表示法，只不过在这里只将其用于编码有效数部分；

* 指数E：将值乘以2的幂次

编码如下：

                                         高位                                                                                                 低位

其中s是符号位；exp编码了E（但不等于E）；frac编码了M（但不等于M）

precision options：

一般来说可按下面所述规定exp和frac占的位数，但关于这点没有严格规定。exp影响能表达的数字的范围；frac影响能表达的精度。

单精度：32bits。有效数字大概为7位十进制，能表示的大小大概为10(+-38)量级。

尾数用23位存储，加上小数点前有一位隐藏的1(IEEE754规约数表示法)，2^(23+1) = 16777216。因为 10^7 < 16777216 < 10^8，所以说单精度浮点数的有效位数是7位。

指数部分用了8位，能表示的指数大小大概为-126～127，2^127 约等于10^(+-38)。可见这个量级比同样位数能表示的整数的量级都大得多。但浮点表示法的有效数位很小，所以如果还用这种方法来编码int，就无法精确编码有效数字很长的整数。int采用的补码，表达出的整数数值是完全精确的。

双精度：64bits。有效数字大概为16位十进制，能表示的大小大概为10^(+-308)量级。

注：

在使用浮点数时，我们更关注的是其有效精度范围，而非其数值大小范围。

float小数点前后加起来有效数字只有6～7位（按十进制）；double小数前后加起来的有效数字只有15～16位。所以一条使用准则是，在需要浮点数的时候，不要使用float，而是尽量都采用double来存储。可以看看这里的代码示例：https://blog.csdn.net/cbnotes/article/details/38920511

---

在具体解释编码的含义时，根据exp的值，又可以以三种不同的方式进行翻译：

case 1: normalized values（有效数位的编码暗含一个1）

当exp既不是0，也不是11...11时判定该数字是按normalized方式编码的。

x = 

* 指数域的编码被解释为一个经过偏置的有符号整数：    E = exp - bias

其中bias = 2^(k-1)-1，可将exp编码值[1，254]映射到E=[-126，127]区间。

* 有效数字编码被解释的方式是： M = 1.xxxx

其中xxxx就是frac区的编码，也就是说编码本身没有包含1，这个1是暗含的。frac最小为000...0，对应M=1.0；frac最大为111...1，对应M≈2。这样编码是为了节省一位，使得能多一位精度。

例子：

15213d = 11101101101101                
       = 1.1101101101101 * 2^13
significand
  M    = 1.1101101101101 
  frac =   1101101101101 0000000000
exponent
  E    = 13
  bias = 127
  exp  = 140 = 10001100
最终编码：0 10001100 11011011011010000000000
        s   exp           frac

case 2: denormalized values

在这种情况下，指数域编码全为0。

* 指数值：E = 1-bias（而不是exp-bias）

* 有效数字：M=0.xxxx（而不是1.xxxx），其中xxxx就是frac编码。

* 特例：当exp=000...0，frac=000...0时，代表0值，注意+0和-0的区别。当exp=000...0，frac≠000...0时，数值非常接近0。

* 能表示的最小的数大概是0.11111..*2^(-126)，刚好与normalized case里能表示的最接近0的数1.0*2^(-126)接上。

case 3: infinity

* 当计算发生溢出时，exp变为最大1111..，frac全为0，则M=1.0，此时代表了正无穷。

* 例如：1.0/0.0 = -1.0/-0.0 = infinity

case 4:NaN

 

* 当exp变为最大1111...，而frac并不是0说明并没有溢出。这代表这不是一个正常的数。

* 例如：sqrt(-1)

关于浮点数更详细些的介绍，这个教程不错：https://www.cnblogs.com/zhcncn/articles/3782286.html

floating-point operations（rounding， addition， multiplication）：

舍入分为：

* towards zero：往零凑整

* round down（-inf）：往负无穷凑整

* round up（+inf）：往正无穷凑整

* nearest even*（默认模式）：往最近的偶数凑整，如果恰好在中点处例如1.5，则往偶数舍入：2。

在小数模式下，rounding应向使得rounding后数字的最低有效位为偶数。例如，7.895000rounding to  nearest hundredth，有两种选择：7.89或7.90，应选择7.90。

在二进制中，当保留位的右侧为1000...这种形式时就代表处在中点位置，既可以向上舍入也可以向下舍入。应使得舍入后的数字的最低位为偶数。

乘法：

 x 

精确结果：

* sign s：s1^s2

* significand M：M1 x M2

* exponent E：E1+E2

修订：

* 若M≥2，将M往右移，并增加指数E的值

* 若指数E超过了范围，发生溢出

* 舍入M以适应frac能表达的精度

例子（小数部分使用4bits）：

1.010*2^2 x 1.110*2^3 = 10.001100*2^5
                      = 1.00011*2^6
                      = 1.001*2^6     舍入

加法例子：

1.010*2^2 + 1.110*2^3 = (0.1010 + 1.1100)*2^3 取较大指数，对齐底数
                      = 10.0110*2^3  有效数大于2，进位
                      = 1.00110*2^4
                      = 1.010 * 2^4

浮点数加法：大多数情况下都满足一般加法的运算性质，除了结合律：

(3.14+1e10)-1e10 = 0,   //一个大数与一个小数想加会发生截断，这就造成舍入误差。
3.14+(1e10-1e10) = 3.14

浮点数乘法：不满足结合律和分配律：

由于可能发生了溢出，或者舍入误差导致
不满足结合律：
(1e20*1e20)*1e-20 = inf
1e20 *(1e20*1e-20)=1e20
不满足分配律：
1e20*(1e20-1e20) = 0.0
1e20*1e20 - 1e20*1e20 = NaN

floating point in C：

转换关系：

* 在int，float，double间的强制转换会改变bit表达式
* double/float->int：

   截断fraction部分；

   往0取整；

   对于NaN，设置为Tmin

* int->double：

   只要int字长小于等于53位，就是精确转换

* int->float：

   float能表示的最大范围很可能小于int值，此时会根据rounding mode进行舍入

第三章：机器级的代码表示

3.1 历史观点

3.2 程序编码

3.3 数据格式

3.4 获取信息

3.5 算数和逻辑操作

3.6 控制

3.7 程序

3.8 数组分配和获取

3.9 各种数据结构

3.10 汇总：理解指针

3.11 工程实际：使用调试器

3.12 访问越界和缓存溢出

3.13 x86-64：扩展IA32到64位

3.14 浮点程序的机器级别表示

3.1 历史观点

第一代单芯片16位微处理器称为8086，之后经过几十年时间发展出了很多版本。我们通常以x86来代指Intel处理器的整个系列，此外它也有名字IA32（Intel architecture 32-bit），以及其扩展版本x86-64。

ISA：instruction set architecture——指令集体系结构：即为了写出汇编或机器码必须了解的关于处理器设计的部分，包括intel系列的x86，IA32，x86-64；ARM系列的等。

3.2 程序编码

machine-level code：

反汇编指令：

objdump -d code.o    //使用反汇编器objdump将目标文件code.o进行反汇编
objdump -d prog      //将可执行文件prog进行反汇编

notes on formatting：

>> gcc -O1 -S code.c       //采用1级optimization，得到汇编代码code.s
>> gcc -O1 -c code.c       //采用1级optimization，得到二进制目标代码code.o

得到的汇编代码中，以单点 . 开头的行是专用于汇编器和链接器的一些指令，通常我们可以忽略它们。 

3.3 数据格式

* “integer”型的1，2，4，8字节：1）整型数据；2）地址值（无类型的指针）

* 浮点型的4，8，10字节

* （SIMD向量数据类型，8，16，32，64字节）

* 代码：字节序列，编码了一系列指令

* 数组和结构体：内存中连续分配的字节

3.4 获取信息

operand specifiers：

 

data movement instructions：

不能直接从内存到内存进行数据传递，而必须要经过寄存器周转！

3.5 算数和逻辑操作

load effective address：
地址计算格式：

D(Rb，Ri，S)-->Mem[Reg[Rb]+S*Reg[Ri]+D]

其中：

D：常量位移，1，2或4字节
Rb：Base寄存器（任意16位整数寄存器）
Ri：index寄存器（任意，除了%rsp）
S：Scale：1，2，4或8

例子：假设%rdx=0xf000，那么0x80(, %rdx, 2)表示的地址是： 2*0xf000+0x80 = 0x1e080

leaq a(b, c, d), %rax
 
功能：
先计算地址a + b + c * d，然后把最终地址载到寄存器rax中。

lea指令是mov指令的变种，据说，lea指令是x86体系结构中，是一条最古老但是从某个方面来讲又是最神奇的指令。
表面上看它做的事情非常简单，根据括号里的源操作数来计算地址，然后把地址加载到目标寄存器中。最逗的是leaq不引用源操作数里的寄存器，只是单纯的计算。那这样的完全可以把它当作乘法指令使用。

例如: 要计算rbx * 3 - 1，按如下指令：

movq $8, %rbx                  //%rbx存放8
leaq -1(%rbx, %rbx, 2), %rax   //-1+%rbx+2*%rbx，即-1+3*%rbx，然后放入%rax

什么时候用lea指令呢: 在打算用五六条指令来完成某个乘法运算之前，看看能否通过两三条lea指令来代替它。

注意事项: d的取值范围是1,2,4,8(64位cpu)
 

unary and binary operations：

实际例子：

long arith(long x, long y, long z)  arith:
{
   long t1 = x+y;                   leaq (%rdi, %rsi), %rax     //%rdi+%rsi，放入rax中
   long t2 = z+t1;                  addq %rdx, %rax             //将rax加上rdx，即将z加到t1上
   long t3 = x+4;                   leaq (%rsi, %rsi, 2), %rdx  //y+2*y，即得到3y并放入rdx
   long t4 = y * 48;                salq $4, %rdx               //将rdx值左移4位，即3y乘以2^4，得48y
   long t5 = t3+t4;                 leaq 4(%rdi, %rdx), %rcx    //4+%rdi+%rdx，即4+x+t4
   long rval = t2*t5;               imulq %rcx, %rax            //将rcx乘到rax上
   return rval;                     ret                         //返回rax
}
 
注：第一个参数放在%rdi，第二个参数放在%rsi，第三个参数放在%rdx，返回值放在%rax
(%rdi, %rsi)的含义是将寄存器rdi与rsi的值相加，即x+y
(%rsi, %rsi, 2)的含义是%rsi+2*%rsi，即y+2*y

在上面的计算中，由于使用了leaq和salq运算，使得真正的multiplication运算只用到了一次，这使得代码更高效。

shift operations：

 

special arithmetic operations：

下表给出了有符号和无符号数的全64位乘法和除法。一对寄存器%edx和%eax组成一个64位的四字。 

3.6 控制

condition codes：

accessing the condition codes：

 

jump instructions and their encodings：

translating conditional branches：

 

loops：

 

conditional move instructions：

 

switch statements：

 

3.7 过程（procedures）

machanisms：

* 传递控制权

* 传递数据

* 内存管理

* 使用机器指令来实现其机制

我们使用机器指令来实现其机制，但个中选择依赖于设计者。这些不同的选择构成了application binary interface（ABI）。

stack frame structures：

pushq Src
 
功能：
1）获取Src处的操作数
2）将%rsp值减8
3）在%rsp指向的地址处写入操作数

popq Dest
 
功能：
1）读取%rsp指向的地址处的值
2）将%rsp值加8
3）将读取的值存入Dest（通常是个寄存器）

栈帧是实现递归的机制。

                       -------------------
                        |               |
                        |   previous    |
                        |    frame      |
                        |               |
                        |---------------|
                        | arguments 7+  |    //可能保存着当前被调函数的参数
                        |---------------|
                        | return addr   |    //返回地址是由call指令push入栈的
                        |---------------|
  frame pointer: %rbp-> |  old %rbp     |
           (optional)  -------------------      
                        |saved registers|    //保存寄存器值
                        |       +       |
                        |local variables|    //局部变量，如果无法保存在寄存器中就入栈
                        |               |
                        |---------------|
                        |argument build |    //调用其他函数时可能需要的参数
                        |  (optional)   |
  stack pointer: %rsp->-------------------
 
//调用者的返回地址就存放在ebp+4地址单元处。存放完返回地址，
//紧挨着的高位地址处存放的就是调用者传递给被调者的输入参数(ebp+8, ebp+12....)

---

举个例子：

void i386_init(void)
{
   test_backtrace(5);
}

在进入test_backtrace()之前，%esp == 0xf010ffe0，%ebp==0xf010fff8。

即当前i386_init()函数的栈帧为：0xf010ffe0～0xf010fff8。而它把即将要调用test_backtrace()需传入的参数‘5’保存在地址0xf010ffe0处。

在进入test_backtrace()之前，保存返回地址，即将%esp值下移并压入返回地址。此时%esp==0xf010ffdc。

然而进入test_backtrace()的范围，先执行几条准备命令：

push %ebp            //保存上一栈帧的%ebp值
mov  %esp, %ebp      //现在%ebp是当前函数栈帧底，它指向的地址保存的是上一栈帧的%ebp！
push %ebx            //保存%ebx的值，以备在test_backtrace()中使用
sub  $0xc, %esp      //将栈指针下移，即为当前函数开辟栈帧空间

这几条命令执行完之后，新的栈帧建立起来，%esp==0xf010ffc8，%ebp==0xf010ffd8。

即当前test_backtrace()的栈帧为：0xf010ffc8～0xf010ffd8。

如果在test_backtrace()中继续调用子函数，那么在进入进一步的栈帧之前，%esp指向的地址将保存返回地址。

总结：在运行时，每一栈帧将对应两个寄存器：%ebp指向的单元保存上一栈帧的%ebp；在进入下一函数前，%esp指向的单元保存当前栈帧的返回地址。

---

栈帧中的内容有：

1）返回信息

2）局部存储信息（如果需要的话）

3）暂时的空间（如果需要的话）

管理方法：

1）当进入某一过程时开辟空间

     * “set-up”代码

     *call指令包含了push

2）离开过程时释放空间

     *“finish”代码

     *ret指令包含了pop

transfering control：

在执行程序时，指令寄存器%rip始终保存下一指令的地址（指向指令），栈指针寄存器%rsp始终保存栈顶地址（指向栈顶）。当需要调用子函数时，先将该函数的下一条指令的地址入栈，然后%rip变成子函数的入口地址。

register usage conventions：

函数的参数用哪些寄存器来存放呢？

按惯例，前6个arguments存放在：

如果超过了6个，更多的参数则存放到栈中。

函数的返回值使用寄存器%rax来保存。

在函数调用时由谁保管暂时值？

“caller saved”：由caller在它自己的frame中保管暂存值，在执行call之前保管

“callee saved”：由callee在它的frame中保管；callee负责在返回给caller时恢复它们的值

按惯例，%eax，%edx，%ecx归类为caller-save寄存器，主调函数用于暂存它需要的值，当主调函数调用其他函数时需要先把这些寄存器的值入栈；%ebx，%esi，%edi被归类为callee-save寄存器，被调函数用于暂存它需要的值，当被调函数被调用时需要先把这些寄存器的值入栈。

procedure example：

 

recursive procedures：

 

3.8

 

3.12 存储器的越界引用和缓冲区溢出

 

第十章 系统级IO（2019.8.17我直接跳到这里开始学习）

10.1 Unix I/O

1. 一个linux“文件”实际上就是m个bytes组成的序列：B0，B1，...，Bm-1

2. 所有I/O设备都用“文件”来表示：/dev/sdat2（/usr disk partition）；/dev/tty2（终端）

3. 甚至内核也是用文件来表示的：/boot/vmlinuz-3.13.0-55-generic（kernel镜像）

10.2打开和关闭文件

每个文件有个type用于指示它在系统中的角色：1.regular file：包含任意数据；2.directory：相关的一组文件的索引；3.socket：为了与另一台机器上的进程通信

其他的一些文件类型（在这里我们不深究）：Named pipes（FIFOs）、Symbolic links、Character and block devices

Regular files：

在应用中常常区分为文本文件和二进制文件：文本文件是只含ASCII或Unicode字符的regular file；所有其余的文件都是二进制文件（包括JPEG图像、视频文件、目标文件等）。但注意，内核并不能区分出一个文件到底是文本文件还是二进制文件，这种区别仅仅只有应用程序能区别。

文本文件是一系列test lines的序列：每个文本行都使用一个newline字符（‘\n’，0xa）来结束。

Opening files：

//打开一个文件，通知内核你已经准备好访问该文件了
int fd;    //file descriptor
 
if((fd = open("/etc/hosts", O_RDONLY)) < 0){
    perror("open");
    exit(1);
}
//返回一个标识整数file descriptor（例如，这个数是1024，表示能同时打开的文件数量最多为1024个），如果为-1，表示发生了错误

* 每一个linux shell在创建进程时，会自动打开三个与终端相关联的文件：

   0: 标准输入（stdin） 

   1: 标准输出（stdout）

   3: 标准错误（stderr）

Closing files：

int fd;        //file descriptor
int retval;    //return value
 
if((retval = close(fd)) < 0){
    perror("close");
    exit(1);
}

* 尝试关闭一个本已经关闭的文件常常是多线程程序中灾难的原因。 

10.3 读和写文件

Reading files：

char buf[512];
int fd;        //file descriptor
int nbytes;    //number of bytes read
 
//打开文件fd， 然后从中读取最多512个字节的数据到buf。称之为short write。
//从当前文件位置开始读，拷贝到内存中，然后刷新当前指向的文件位置
if((nbytes = read(fd, buf, sizeof(buf))) < 0){
    perror("read");
    exit(1);
}

Writing files:

char buf[512];
int fd;        //file descriptor
int nbytes;    
 
//写最多512字节到fd文件中去
if((nbytes = write(fd, buf, sizeof(buf))) < 0){
    perror("write");
    exit(1);
}

例子：

#include "csapp.h"
 
int main(){
    char c;
    while(Read(STDIN_FIELD, &c, 1) != 0)        //读文件STDIN
        Write(STDOUT_FIELD, &c, 1);             //写文件STDOUT   
    exit(0);
}

short count：

在有些时候，read和write传送的字节数比应用程序要求的少，返回的值称为“不足值”（short count），这些不足值不表示有错误。出现这种情况的原因有：

1. 读时遇到EOF，此时读函数返回0以表示读到了文件末尾；

2. 从终端读文本行。若打开文件是与终端相关联的，那么每个read函数将一次传送一个文本行，返回的不足值等于文本行的大小。

3. 读和写网络套接字（socket）。若打开的文件对应于网络套接字，那么较长的网络延迟和内部缓冲约束会引起read和write返回不足值。对unix管道调用read和write时也可能出现不足值。

10.4 用RIO包健壮地读写

在上面我们讲到了使用系统I/O函数进行读写时会发生返回不足值的问题，为了自动处理这些不足值的情况，可以自己编写一些更稳定的I/O函数来使用。

Unbuffered RIO Input and Output：

与Unix的read和write有相同的接口，尤其适用于在网络sockets上传输数据。

#include "casapp.h"
 
ssize_t rio_readn(int fd, void *usrbuf, size_t n);
ssize_t rio_writen(int fd, void *usrbuf, size_t n);
 
//如果传输正常，返回num字节；如果遇到EOF（只对rio_readn），返回0；如果错误，返回-1

1.  rio_readn 只在遇到EOF时返回short count。只有当你知道需要读取多少字节时才使用这个函数。

2. rio_writen 永远不会返回short count。

//rio_readn - robustly read n bytes (unbuffered)
//由于系统的I/O函数可能会产生short count的问题，所以我们自己写一个更稳定一点的读写函数
ssize_t rio_readn(int fd, void *usrbuf, size_t n){
    size_t nleft = n;
    ssize_t nread;
    char* bufp = usrbuf;
    
    while(nleft > 0){
        if((nread = read(fd, bufp, nleft)) < 0){
            if(errno == EINTR)    //interrupted by sig handler return
                nread = 0;        //and call read() again
            else
                return -1;        //errno set by read()
        }
        else if(nread == 0)
            break;                //EOF
        nleft -= nread;
        bufp += nread;
    }
    return (n - nleft);           //return >= 0
}

 

10.5 读取文件元数据

 

10.6 共享文件

 

10.7 I/O重定向

 

10.8 标准I/O

 

10.9 综合：我该使用哪些I/O函数

第十一章  网络编程

11.1 客户端-服务器编程模型

11.2 网络

每台主机上有个网络适配器，从网络上接收到的数据经由适配器->I/O总线->存储总线->到达主存。

适配器一端连接主机，另一端连接到集线器的一个端口上。集线器不加分辨地将从一个端口上收到的每个“位”复制到其他所有端口上。因此，每台主机都能看到每个位。每个适配器有一个唯一的48位地址（MAC address，如f0:18:98:4f:d0:be），当它发送一段“位”（帧）到网段上的任何主机时，每个主机适配器都能看到这个帧，但只有目的主机实际读取它。

这样的多个计算机（host）由一些电缆连接到一个集线器上（hub）构成的网络称为以太网段，这是最底层的网络结构。比如，一个机房内的十多台电脑连到一个集线器上，它们就构成一个以太网段。hub的功能本质上就是个复读机+广播，它把从任意端口接收到的信息都复制，再广播给其他端口。

如果把不同区域的集线器使用被称作“网桥”（bridge）（高密度端口的网桥其实就是交换机）的盒子连接起来，那就组成覆盖域更大一些的所谓“桥接以太网”。比如一个公司、一个学校就可以采用这种方式来互联通信。集线器只是复读机，而网桥则更聪明，它能学会有选择性地传输信息。到这个层面依然只是局域网（LAN）。

如果把不同区域的不兼容局域网采用被称作“路由器”（router）的盒子连接起来，那就组成了所谓的“互联网”（internet）。

问题来了：如何在不兼容的局域网、广域网之间传输信息呢？

策略：在每个主机和路由器上运行协议软件（protocol software）——

1）提供命名格式：为每台主机地址定义统一的格式host address，根据主机所处的网络拓扑结构为其分配ip地址

2）提供传输机制：定义一种标准的传输单元packet = header + payload

11.3 全球IP因特网

基于TCP/IP协议族：

* IP（Internet Protocol）：提供基本命名格式和不可靠的传输机制，是host-to-host的；

* UDP（Unreliable Datagram Protocol）：稍微扩展了IP协议，包可以在process-to-process间传递，而不是在主机间传送；

* TCP（Transmission Control Protocol）：构建在IP协议之上的复杂协议，提供了可靠的process-to-process连接（connections）。

A Programmer‘s View of the Internet：

1. 主机被映射到一个32位的IP地址：如 172.20.10.9（每个字节写成一个十进制数，例如0x8002C2F2 == 128.2.194.242）

2. IP地址被映射为域名：如www.cs.cmu.edu，注：域名与IP地址是多对多的映射。DNS（域名服务器）

3. 一个位于网络上的主机上的进程可以通过一个“connection”与另一个主机上的进程进行信息交流。

注：32位的IP地址是IPv4（第四代），升级到128位之后称为IPv6

Internet Connections：

客户端和服务端是通过“连接”（connections）来传输字节流的。

一个套接字是连接的一个端点，每个套接字有相应的套接字地址，由一个因特网地址和一个16位的整数端口组成：IPaddress：port。

一个端口用于标记一个进程。当客户端发起连接请求时，其套接字地址中的端口是由内核自动分配，称为临时端口。然而，服务器套接字地址中的端口通常是某个知名端口，例如ssh servers：22/ssh；email server：25/smtp；Web servers：80/http。在unix机器上，在/etc/services中包含了这台机器提供的服务及其知名端口。

由客户端发起一个请求：128.2.194.242: 80（即网页服务），服务端128.2.194.242的内核收到该信号，建立起与自己的Web server的连接。套接字对：（cliaddr::cliport, servaddr::servport）

                                       

Sockets：

对于开发者来说，一个Socket就是一个file descriptor，它使得应用程序能读或者写网络。注：所有Unix I/O设备，包括网络，都被抽象成了文件！

对于内核来说，一个socket就是通信的一个端点。