X

曜彤.手记

随记,关于互联网技术、产品与创业

吉 ICP 备10004938号

《CSAPP 第三版》读书笔记(第 1-3 章)


旧书清理系列,今年年初计划要看完的一本书,属于程序员必读系列。据说内容与《程序员的自我修养 — 链接、装载与库》有部分重合,但整体内容规划应该会更加全面。注:笔记超长。

第一章、计算机系统漫游

  1. (Page:2)在不同的上下文中,一个同样的字节序列可能表示一个整数、浮点数、字符串或机器指令。
  2. (Page:2)C 语言的成功离不开当初 Unix(由 C 语言编写)所获得巨大成功。C 语言的设计十分简洁,以至于 K&R 这本经典书籍仅用了 261 页便完整描述了 C 语言及其标准库。
  3. (Page:3)编译系统(流程):

  1. (Page:4)GNU 是 “GNU’s Not Unix” 的缩写。
  2. (Page:6)一个典型系统的硬件组成:

  1. (Page:7)处理器的指令集架构微体系架构:前者描述的是每条机器代码指令的效果;后者描述的是处理器实际上是如何实现的。
  2. (Page:8)利用“直接存储器存取(DMA)”技术,数据可以不通过 CPU 处理器而直接从磁盘到达主存。
  3. (Page:9)为了弥补处理器与主存之间的数据读取效率差异,系统设计者采用了更小更快的存储设备“高速缓存存储器”来存储处理器近期可能会需要的信息(Locality)。现代系统可能存在三级高速缓存(使用 SRAM 实现):L1 \ L2 \ L3,其可存储容量依次降低。

  1. (Page:10)操作系统通过几个基本的抽象概念来管理硬件与应用程序:

  1. (Page:11)POSIX 标准:IEEE 曾努力标准化的 Unix 开发,由 Richard Stallman 命名。标准涵盖了包括:Unix 系统调用的 C 语言接口、Shell 程序和工具、线程与网络编程等多方面内容。
  2. (Page:12)进程的上下文切换(由内核进行管理):

  1. (Page:12)线程共享同一进程的代码和全局数据(非 Thread-Local 数据)。
  2. (Page:13)进程虚拟地址空间(VAS):

  1. (Page:14)每个 I/O 设备,包括磁盘、键盘、显示器,甚至网络,都可以看成是文件。系统中的所有输入输出都是通过使用一小组称为 Unix I/O 的系统函数调用读写文件实现的。
  2. (Page:16)Amdahl 定律(Amdahl’s Law):当我们对系统的某个部分加速时,其对系统整体性能的影响取决于该部分的重要性和加速程度。要想显著加速整个系统,必须提升全系统中相当大部分的速度
  3. (Page:17)并发(concurrency)和并行(parallelism)的三个层次(由高到低):
  1. (Page:18)多核处理器结构:

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

  1. (Page:22)由于表示的精度优先,浮点数是不可结合的。整数的表示只能编码一个相对较小的数值范围,但却是准确的;而浮点数虽然可以编码一个较大的数值范围,但表示却是近似的。
  2. (Page:24)C 编译器维护着指针和该指针对应的类型信息,但实际生成的机器级程序却并不包含数据类型的信息
  3. (Page:27)字长:指明指针数据的标称大小(决定了虚拟地址空间 VAS 的最大大小。w 位 -> 可寻址范围 0~2^w-1)。
  4. (Page:27)(32位 / 64位)程序:区别在于该程序是如何编译的,而不是其运行的机器类型。
  5. (Page:28)ISO C99 引入了一类数据类型,其数据大小是固定的,不随编译器和机器设置而变化,如:int32_t \ int64_t 等。
  6. (Page:29)对象的地址为所使用字节中最小的地址(低地址端)。
  7. (Page:29)许多较新的微处理器采用双端法,即可以将它们配置成小端或大端两种模式,但实际情况是一旦选择了特定的操作系统,那么字节序也就固定了下来。属于“小端”和“大端”来自于《格列佛游记》一书,其中交战的两个派别无法就应该从哪一端打开一个半熟的鸡蛋达成一致。
  8. (Page:33)通过命令 man ascii 可以得到一张 ASCII 字符码的表。
  9. (Page:36)“位向量”的一个应用是可以用于表示“有限集合”
a = [01101001] -> A = {0, 3, 5, 6}
b = [01010101] -> B = {0, 2, 4, 6}
  1. (Page:40)逻辑右移算数右移:前者在最高位补 0;而后者在最高位补最高有效位的值(可保持符号性)。几乎所有的编译器/机器都对有符号数使用算数右移,而无符号数则使用逻辑右移。Java 会对右移的类型进行明确的区分(>> 与 >>>)。
  2. (Page:44)补码(Two’s-complement):其中最高有效位称为“符号位”,其“权重”为 -2^(w-1)(w 为位向量的长度)。

  1111([111...1])
- 0101 原码(5)
------------------
  1010 反码(-5)

 10000(2^w)
- 0101 补码(5)
------------------
  1011 补码(-5)
  1. (Page:49)强制类型转换的结果保持位值不变,只是改变了解释这些位的方式
int main(int argc, char** argv) {
  short int v = -12345;
  unsigned short uv = static_cast<unsigned short>(v);
  std::cout << uv << std::endl;  // 53191(与 -12345 的补码表示完全一致).
  return 0;
}
  1. (Page:50)补码与无符号数的相互转换:

  1. (Page:54)符号扩展(Sign Extension)与零扩展(Zero Extension):前者在扩展时填充最高有效位的值;后者在扩展时填充 0。两者可以分别对应到算数右移与逻辑右移相似的逻辑。
  2. (Page:56)C 语言类型转换会先转换数据大小,再转换符号性
short sx = -12345;
unsigned uy = sx;  // (unsigned)(int)sx.
  1. (Page:57)数字的截断:

  1. (Page:59)size_t 通常被定义为无符号类型。
  2. (Page:61)无符号数加法:

int isUnsignedAdditionOverflow(unsigned short x, unsigned short y) {
  unsigned short sum = x + y;
  return sum < x ? 0 : 1;
}
  1. (Page:63)补码加法:

int isSignedAdditionOverflow(short x, short y) {
  short sum = x + y;
  if (x > 0 && y > 0 && sum < 0) {
    return 1;  // 正溢出;
  } else if (x < 0 && y < 0 && sum > 0) {
    return -1;  // 负溢出;
  }
  return 0;
}
  1. (Page:66)对于 w 位的补码加法来说,TMin(w) 是自己的加法的逆
TMin(w) + TMin(w) = -2^(w-1) + -2^(w-1) = -2^w (Overflow) = -2^w + 2^w = 0 
  1. (Page:66)执行位级补码非()的几种方式:
  1. (Page:67)无符号乘法(截断为结果的低 w 位):

  1. (Page:67)补码乘法(截断为结果的低 w 位):

  1. (Page:70)由于整数乘法相当慢(需要 3-10 个时钟周期),因此可以选择使用“位移+加法”组合的方式来实现:左移一个数值等价于执行一个与 2 的幂相乘的无符号乘法

  2. (Page:71)常数乘法优化:

// 一个乘法替换为三个位移和两个加法;
x*14 -> x*(2^3 + 2^2 + 2^1) -> (x<<3)+(x<<2)+(x<<1)
// 一个乘法替换为两个位移和一个减法;
x*14 -> x*(2^4 - 2^1) -> (x<<4)-(x<<1)
  1. (Page:72)在大多数机器上,整数除法要比整数乘法更慢 — 需要30个或更多的时钟周期
  1. (Page:76)小数的二进制表示法只能表示那些能够被写成 x \ 2^y* 的数,其他的值只能够被近似表示。而增加二进制表示的长度可以提高表示的精度。

  1. (Page:78)IEEE-754 浮点数单精度浮点表示(其他类似):

  1. (Page:82)整数到浮点数的转换:
12345(原始十进制数)
[11000000111001](展开二进制)
12345 = 1.1000000111001 * 2^13(浮点数二进制表示)
[10000001110010000000000](丢弃个位数 “1”,补充小数字段)
[1000110010000001110010000000000](计算阶码字段,幂+偏置阶码)
[01000110010000001110010000000000](添加符号位)
  1. (Page:82)浮点数的舍入(Rounding):

  1. (Page:85)IEEE-754 中定义 1/-0 将得到负无穷,而 1/+0 将得到正无穷;“无穷”和 NaN 无逆元。
  2. (Page:85)浮点数的乘法和加法是不可结合的(指全范围内):
// 超过最大安全数(小数位全为 1)的范围;
(3.14 + 1e209) - 1e209  // 0.
3.14 + (1e209 - 1e209)  // 3.14.

第三章、程序的机器级表示

  1. (Page:109)编译器基于编程语言的规则目标机器的指令集(ISA)和操作系统遵循的惯例(Calling Convention),经过一系列的阶段生成机器代码。
  2. (Page:110)IA32 为 X86-64 的 32 位前身,是 Intel 于 1985 年提出的。
  3. (Page:110)当前的 64 位机器能够使用多达 256TB(2^48 字节)的内容空间,而且很容易就可以扩展至 16EB(2^64 字节)。在目前的实现中,虚拟地址的高 16 位必须设置为 0
  4. (Page:111)8087 协处理器(FPU)建立了 X86 系列的浮点模型,通常被称为 “X87”。浮点运算寄存器:SSE -> SSE2 -> AVX(这些也同时被作为 SIMD 寄存器,最初的为 MMX)。
  5. (Page:115)生成汇编代码(-S):
clang++ -S -std=c++2a <file>
  1. (Page:116)X86-64 的指令长度为 1-15 个字节不等。
  2. (Page:119)由于是从 16 位体系结构扩展成 32 位的,Intel 用术语“字(word)”来表示 16 位数据类型。因此 32 位数为“双字”,64 位数为“四字”。

  1. (Page:120)通用目标寄存器:

  1. (Page:121)操作数格式(R 表示寄存器的值,M 表示将该值作为地址,即该地址存放的值):

mov rax, [rdx + 8 * rcx + 42]
; ATT 汇编;
movl $0x4050, %eax
movw %bp, %sp
movb (%rdi, %rcx), %al
movb $-17, (%rsp)
movq %rax, -12(%rbp)
  1. (Page:122)数据传送指令:

  1. (Page:127)栈操作:

  1. (Page:129)算数和逻辑操作:

; R(%rax) = 5R(%rdx) + 7.
leaq 7(%rdx, %rdx, 4), %rax
; 从 %rdx 中减去 %rax;
subq %rax, %rdx
  1. (Page:133)特殊的算数操作:

  1. (Page:136)CMP 指令(cmpb \ cmpw \ cmpl \ cmpq)与 SUB 指令的行为是一致的(判断基于减法的结果值),只是前者不会更改目的寄存器的值。
  2. (Page:136)TEST 指令(testb \ testw \ testl \ testq)与 AND 指令的行为是一致的(判断基于“算数与的结果值”),只是前者不会更改目的寄存器的值。典型的用法是:两个操作数是一样的或其中一个是一个掩码,用来指示哪些位应该被测试。
  3. (Page:136)条件码的三种使用方式:

; int comp(data_t a, data_t b)
; a in %rdi, b in %rsi.
comp:
  cmpq %rsi, %rdi  ; Compare a:b.
  setl %al  ; Set low-order byte of %eax to 0 or 1.
  movzbl %al, %eax  ; Clear rest of %eax (and rest of %rax).
  ret

; long absdiff(long x, long y)
; x in %rdi, y in %rsi.
absdiff:
  movq %rsi, %rax  ; y.
  subq %rdi, %rax  ; rval = y-x.
  movq %rdi, %rdx
  subq %rsi, %rdx  ; eval = x-y.
  cmpq %rsi, %rdi  ; Compare x:y.
  cmovge %rdx, %rax  ; If >=, rval = eval.
  ret  ; Return tval.
  1. (Page:152)while 语句的两种实现方式(for 循环可以用类似的方式实现):
; long fact_while(long n)
; n in %rdi.
fact_while:
  movl $1, %eax     ; Set result = 1.
  jmp .L5           ; Goto test.
.L6:              ; loop:
  imulq %rdi, %rax  ; Compute result *= n.
  subq $1, %rdi     ; Decrement n.
.L5:              ; test:
  cmpq $1, %rdi     ; Compare n:1
  jg .L6            ; If >, goto loop.
  rep; ret          ; Return.
; long fact_while(long n)
; n in %rdi.
fact_while:
  cmpq $1, %rdi     ; Compare n:1.
  jle .L7           ; If <=, goto done.
  movl $1, %eax     ; Set result = 1.
.L6:              ; loop:
  imulq %rdi, %rax  ; Compute result *= n.
  subq $1, %rdi     ; Decrement n.
  cmpq $1, %rdi     ; Compare n:1.
  jne .L6           ; If !=, goto loop.
  rep; ret          ; Return.
.L7:              ; done:
  movl $1, %eax     ; Compute result = 1.
  ret               ; Return.
  1. (Page:159)Switch 语句可以使用“跳转表”(Jump Table)来实现。跳转表是一个数组,表项 i 是一个代码段的地址,这个代码段实现当开关索引值等于 i 时程序应该采取的动作。当 case 子句大于 4 且值的范围跨度较小时,就会使用跳转表

  1. (Page:165)通过寄存器,“过程”之间可以最多传递 6 个整数值。许多函数甚至不需要“栈帧”,当所有的局部变量都可以保存在寄存器,而且该函数不会调用任何其他函数时(叶子过程),便可以这样处理。
  2. (Page:165)转移控制指令:

  1. (Page:177)数组引用及对应汇编代码:

  1. (Page:187)一个联合(union)的总大小等于它最大字段的大小。可以用来以一个对象来表示多个不同的“互斥量”。
// 一个二叉树节点;
typedef enum { N_LEAF, N_INTERNAL } nodetype_t;
struct node_t {
  nodetype_t type;  // 标记当前联合的类型;
  union {
    struct {
      struct node_t *left;
      struct node_t *right;
    } internal;  // 内部节点;
    double data[2];  // 叶子节点;
  } info;
};
double uu2double(unsigned wordA, unsigned wordB) {
  union {
    double d;
    unsigned u[2];
  } temp;
  temp.u[0] = wordA;  // 小端,则为低 4 位;
  temp.u[1] = wordB;  // 小端,则为高 4 位;
  return temp.d;
}
  1. (Page:189)数据对齐:原则是任何 K 字节的基本对象的起始地址必须是 K 的倍数。另外,编译器还会对结构体的末尾进行一些填充,以满足在结构体数组中每个元素的对齐要求。
.align 8  ; 保证后面数据的起始地址为 8 的倍数;
struct S {
  int i;  // 偏移 0 字节;
  char c;  // 偏移 4 字节;
  int j;  // 对齐到 8 字节(填充 3 字节);
};
  1. (Page:192)指针相关:
  1. (Page:196)使用 fgets 函数代替 gets 函数以防止“缓冲区溢出”错误(可通过溢出来替换栈上的返回地址,达到攻击的效果)。
  2. (Page:198)一些对抗缓冲区溢出攻击的机制

  1. (Page:201)在不使用 %rbp(栈帧寄存器、基指针)时,编译器必须能够计算出在退出“子函数”前需要释放的栈高度,这需要能够在静态分析情况下分析出子函数局部变量的内存使用情况。否则,则需要通过 %rbp 来释放栈。(在较早的 X86 代码中,每个函数都使用基指针,但现在仅在栈帧长度可变的情况下才会使用)
; 等同于 leave;
movq %rbp, %rsp
popq %rbp
  1. (Page:204)浮点体系结构与寄存器

  1. (Page:206)浮点传送和转换操作(以下均为 AVX2 浮点指令集):

; float float_mov(float v1, float* src, float* dst)
; v1 in %mm0, src in %rdi, dst in %rsi.
float_mov:
  vmovaps %xmm0, %xmm1  ; Copy v1.
  vmovss (%rdi), %xmm0  ; Read v2 from src.
  vmovss %xmm1, (%rsi)  ; Write v1 to dst.
  ret                   ; Return v2 in %xmm0.

  1. (Page:210)浮点运算操作

  1. (Page:212)浮点数常量:AVX 浮点数操作不能以立即数作为操作数。因此,编译器必须为所有的常量值分配和初始化存储空间,然后使用时从内存中读取。
; double cel2fahr(double temp)
; temp in %xmm0.
cel2fahr:
  vmulsd .LC2(%rip), %xmm0, %xmm0  ; Multiply by 1.8.
  vaddsd .LC3(%rip), %xmm0, %xmm0  ; Add 32.0.
  ret
.LC2:
  .long 3435973837                 ; Low-order 4 bytes of 1.8.
  .long 1073532108                 ; High-order 4 bytes of 1.8.
.LC3:
  .long 0                          ; Low-order 4 bytes of 32.0.
  .long 1077936128                 ; High-order 4 bytes of 32.0.
  1. (Page:212)浮点数的位级操作

  1. (Page:213)浮点数的比较操作



这是文章底线,下面是评论
  暂无评论,欢迎勾搭 :)