CSAPP

Sept 27, 2023 edition

笔者前言

写来尝试造福学弟学妹们。很惭愧，只是想要做一点微小的工作。

内容仅包含北京邮电大学课程《计算机系统基础》的部分讲授和期末考核内容，并不严格包含 CSAPP 一书中的完整章节。

CSAPP 是一本优秀的书，但其中也有些内容过于理论化、已经过时，也难免出现错误（CSAPP 英文原书第三版官方勘误（尚在不断补充中）），其中文译本也存在翻译水平底下、难以阅读的问题。瑕不掩瑜，我们仍然推荐大家使用本书学习，本文即是尝试为学习这一册书的后来的朋友提供些许帮助。

CSAPP 的第一部分以 C 语言为媒介过渡到了 x86-64 汇编这一更低的抽象层级，这个过渡方式本身是没有问题的；然而 C 语言本身也在不断的更新迭代、发展优化中，书中一系列“C 语言中负数采用补码”“整数右移采用算术右移”“int x = foo(); x * x >= 0 有可能返回假”“char 有符号”等论断并不一定符合 C 语言的客观实际，其中有些没有遵守 C 语言规定但符合 x86-64 实际，有些两者都不一定遵守，有些在应用层级的 C 语言中会被直接优化成为期望之外的行为。笔者认为应当将书中采用的 C 语言与其他场合中的 C 语言分开看作两门语言，它们的语法相互贯通，但对于某些特定情况下的行为不应混淆。这一点非常重要，所以在前言中指出。

笔者水平有限，无法保证全文正确且易懂；欢迎勘误或改进，目前请通过邮件。目前也可以通过邮件索要本文的 markdown 源文件。

感谢阅读。

2. 信息与不带优化的操作系统级 C

二进制 & 无符号数 & 补码有符号数

无符号数就是二进制位加权求和，权是 $2$$2$ 的幂。

补码有符号数的二进制最高位是符号位。它和无符号数的区别只在于符号位的权取相反数。

这就是全部，就这么简单。

• 一个显然的推论：补码有符号负数向无符号数转换时，加符号位权的绝对值的二倍即可。

C 的整数类型

CSAPP 在这里故弄玄虚。实际上的规则很简单，大体包含了类型系统、整数常量（字面量）、隐式转换三部分。

我更习惯让你去读 C++ 的材料。我觉得它相比 C 的易读很多，并且其中两门语言的重合部分中 80% 是适用 C 语言的。

• 整数类型：https://zh.cppreference.com/w/cpp/language/types

• 算术运算：https://zh.cppreference.com/w/cpp/language/operator_arithmetic

• 整数常量、字符常量（C 语言条目）：https://zh.cppreference.com/w/c/language/integer_constant, https://zh.cppreference.com/w/c/language/character_constant

• 整数提升和整数转换：https://zh.cppreference.com/w/cpp/language/implicit_conversion#.E6.95.B4.E6.95.B0.E6.8F.90.E5.8D.87

• 比较运算：https://zh.cppreference.com/w/cpp/language/operator_comparison

整数的类型系统大体就是说，整数类型的排序是 char < short < int < long < long long，其中每种类型的 signed 版本低于 unsigned 版本。

字面量的默认类型是 int，如果不能容纳会向上尝试更高的类型。你也可以在字面量中添加后缀指定类型，例如 -1u。

• 有几点注意

  • CSAPP 全书暗戳戳地将 char 当作了 signed char 来讲解而未加任何说明。实际上 char 是非常特殊的：char, signed char, unsigned char 是相互独立的三个类型，在不同机器上、不同编译选项下，char 的行为可以是后两者中的任何一个（但并不意味着名义上是同一个类型）。

    • 特殊在哪里呢？对于其他不特殊的所有整数类型，比如 int，int 和 signed int 是同一个类型的两个名字。

  • long 在现行 64 位 Windows 的数据模型下是 32 位整数，而 64 位 Linux / macOS 的数据模型下是 64 位整数。而 CSAPP 全书大言不惭采用了后者，默认它是 64 位整数。

    • 这意味着如果你要在自己的 Windows 机器上运行书中的代码，应该果断使用 long long 替换 long。很多同学似乎没能独立意识到这一点。

  • long long 实际上是 C99 / GNU C++98 / ISO C++11 才有的类型。我们现在决不应该使用上世纪的语言标准 C89 和 C++98 了。笔者写作时最新的语言标准是 C23 和 C++23。

系统级 C 的整数类型的算术运算和比较运算

对于除移位以外的算术运算，首先会将所有低于 int 的操作数提升到 int，称之为“整数提升”（狭义）。

• 比如你如果用 C++ 的 std::cout 输出 'A' + ' '，会发现结果是 97 而不是 'a'。

• C 也是一样，但是不太容易观测，你可以尝试求值表达式 (((short)1 + (short)2) & 0.)，编译器的 error 会告诉你找不到 int 和 double 之间的运算符 &（而非 short 和 double 之间的）。不再用字符常量举例是因为 C 语言中的单字节字符常量（比如 'A'）本身就是 int 类型的。

接着，如果两个操作数类型仍然不同，会将其中较低的类型隐式转换到较高的。

• 比如 -1u - 114514 的结果是 unsigned int 类型的 4294852781，而不是 -114515。

比较运算的操作数如果是算术类型（整数类型当属其中），也会实施如上所述的算术转换。

移位运算不会实施上述的算术转换。此外，考试中若不加说明，我们一般认为 >> 会发生算术右移，但是将来若你在实际环境中遇到这个问题，行为如何还需具体测试。

C 的浮点类型

接着整数类型说。C 有三种浮点类型 float < double < long double，隐式类型转换中它们均高于任何整数类型。

• 这并不意味着它们的精度更高，实际上 float 在 32 位整数范围内保存整数的精度甚至不如 int。

• double 的精度严格优于 int 和 float。

• long double 是个实现强相关的类型，它占用的字节数和结构不一定是典型的 64 位 IEEE 浮点数，也不一定是 80 位或 128 位，我们略去不表。

IEEE 浮点数

和大多数编程语言一样，C 语言采用 IEEE 754 规定的浮点数，其中 float 和 double 分别采用 32 位（单精度）和 64 位（双精度）的 IEEE 浮点数典型标准。

IEEE 浮点数的实际值以 $V=(-1{)}^s\times 2^E\times M$$V = (-1)^{\color{Blue}s} \times 2^{\color{Green}E} \times {\color{Red}M}$ 的形式表示，其中

• 符号 $s$$s$ 决定浮点数的正负。

• 阶码 $E$$E$ 对浮点数加权，使得阶码的不同位在计算实际值时最终具有 $\cdots ,2^0,2^{-1}$$\cdots, 2^0, 2^{-1}$（小数点前后第一位）$,2^{-2},\cdots$$, 2^{-2}, \cdots$ 的权，造成小数点实际上浮动的效果，“浮点”的名字因此得来。

  • 没有来源，我自己 YY 的，但这真的很形象啊。

  • 这个网站在实现 64 位 IEEE 浮点数可视化的同时捎带着做了小数点浮动的动画，推荐（需要**）：https://bartaz.github.io/ieee754-visualization/

• 尾数 $M$$M$ 在不同情况下具有 $0\sim 1-\epsilon$$0\sim 1 - \varepsilon$ 或 $1\sim 2-\epsilon$$1\sim 2 - \varepsilon$ 的取值范围，由于 $E$$E$ 的加权给实际值产生不同的贡献。

典型地，IEEE 单精度和双精度浮点数分别拥有以下的结构：

我们在 exponent 和 significand 的分界处放置一个小数点，左侧各位的权依次为 $2^0,2^1,2^2,\cdots$$2^0, 2^1, 2^2, \cdots$，右侧各位的权依次为 $2^{-1},2^{-2},2^{-3},\cdots$$2^{-1}, 2^{-2}, 2^{-3}, \cdots$。记 exponent 编码出的一个整数为 $e$$e$，significand 编码出的一个小数为 $f$$f$。

根据 $e$$e$ 的值，浮点数被分为三类。

1. 规格化的值，适用于 $e$$e$ 既非全 0 也非全 1（单精度 $255$$255$，双精度 $2047$$2047$）的情况。

   令 $k$$k$ 为 exponent 的位数，设置一个偏置量 $B=2^{k-1}-1$$B = 2^{k - 1} - 1$（单精度 $127$$127$，双精度 $2047$$2047$）。

   此时 $E=e-B$$E = e - B$，$M=1+f$$M = 1 + f$。

2. 非规格化的值，适用于 $e$$e$ 为 $0$$0$ 的情况。

   此时 $E=e-B$$E = e - B$，$M=f$$M = f$。

   非规格化的值用于表示非常接近 $0$$0$ 的数（包括 $+0$$+0$ 和 $-0$$-0$）。

3. 特殊值，适用于 $e$$e$ 为全 1 的情况。

   此时，若 $f=0$$f = 0$，则 $V=\mathrm{\infty }$$V = \infty$ 或 $V=-\mathrm{\infty }$$V = -\infty$，取决于符号位 $s$$s$。否则 $V=\text{NaN}$$V = \textrm{NaN}$（Not a Number）。

   $\text{NaN}$$\textrm{NaN}$ 是一个非常特殊的数字，用于描述不能被表示的运算结果。$\text{NaN}$$\textrm{NaN}$ 具有“吞噬性”，任何它参与的算术运算全部返回 $\text{NaN}$$\textrm{NaN}$；$\text{NaN}$$\textrm{NaN}$ 不具有和其他浮点数的偏序性质，它参与的比较运算（包括 nan == nan）全部返回假，唯一的例外是 nan != nan 返回真。

用移位优化常量乘法

众所周知硬件计算乘法远慢于加法、减法和移位。

尝试用加减和移位优化计算常量 $K$$K$ 乘以变量时可以考察 $K$$K$ 的二进制表示中 $\mathtt{\text{0}}$$\texttt0$ 的数量$+1$${} + 1$ 和 $\mathtt{\text{1}}$$\texttt1$ 的数量中的较小值。

3. 不带优化的操作系统级 C 与 x86-64 at&t 汇编

x86-64 通用寄存器

16 位和 8 位的那些真**难背啊，背这玩意干啥啊。

l 结尾的是 8 位的，否则稀奇古怪的是 16 位的。r 开头的是 64 位的，e 开头的是 32 位的。

前 6 个参数分别是 %rdi, %rsi, %rdx, %rcx, %r8, %r9；返回值是 %rax。

%rsp 是栈指针；%rbx, %rbp, %r12~%r15 是 callee-saved，剩下的是 caller-saved。

x86-64 条件码寄存器

CSAPP 一书中涉及到了以下四个位：

• CF：最高位进位

• ZF：零

• SF：符号位（负数）

• OF：溢出（上溢和下溢）

所有的算术运算指令会根据其结果设置这些寄存器位的值。

汇编寻址

$s$$s$ 的值似乎只能是 $1,2,4$$1, 2, 4$ 或 $8$$8$。

at&t 汇编指令后缀

就是说操作数大小不一定的指令可以加 b, w, l, q 指示字节数。 b 是字节 byte，w 是字 word，l 是双字，q 是四字。

• 其实还有少量命令以 o 结尾，处理八字，下文中会提到这么一个。不过不算严格意义上的后缀。

感觉可能其实有挺多人更习惯用 Intel 汇编的方式啊，况且 at&t 汇编也不是一定要加这个后缀的。

不过考试要考。

x86-64 汇编的一些指令

• mov S, D

  • 存储 source 的值到 destination。

  • mov 指令的 source 操作数若为立即数最多为 32 位。若需传送 64 位整数，有 movabsq I, R 指令。

  • movz** S, R 以零扩展传送。没有 movzlq，因为 movl 本来就会把高位置零。

    • 注意操作数是 R 的时候基本都是指寄存器，就像 I 都指立即数一样。

  • movs** S, R 以符号扩展传送。

  • cltq 没有操作数，等价于 movslq %eax, %rax。专门搞出一条指令是为了省空间。

• pushq S

  • subq $8, %rsp; movq S, (%rsp) 的语法糖。

• popq D

  • movq (%rsp), D; addq $8, %rsp 的语法糖。

• leaq S, D

  • 名义上是加载内存地址，实际上可以让寻址表达式 S 只计算地址而不寻址然后存储给 D。可以拿来做运算，但不在算术运算指令之列。

• 一堆算术运算指令

  指令	效果
  inc D	D <- D + 1
  dec D	D <- D - 1
  neg D	D <- -D
  not D	D <- ~D
  add S, D	D <- D + S
  sub S, D	D <- D - S
  imul S, D	D <- D * S
  xor S, D	D <- D ^ S
  or S, D	D <- D | S
  and S, D	D <- D & S
  sal S, D, shl S, D	D <- D << S
  sar S, D	D <- D >> S
  shr S, D	D <- D >>> S

  • 注意移位指令 sal, shl, sar, shr，它们的第一个操作数只能是立即数或寄存器 %cl。

    • CSAPP 书中称指令后缀分别为 b, w, l, q 时，移位量分别采用第一个操作数（立即数或 %cl）的最低 3, 4, 5, 6 位。但是笔者经过实际测试和查阅文档，认为移位量分别会采用其最低 5, 5, 5, (5 或 6) 位，参见 https://godbolt.org/z/K1Wxh8fWv， https://www.felixcloutier.com/x86/sal:sar:shl:shr#description 和 Intel® 64 and IA-32 Architectures Software Developer’s Manual Vol. 2B 4-594。

• 几个特殊的算术运算指令，共同点是用到一对 64 位寄存器 %rdx:%rax 组成 128 位的空间。

  • clto 没有操作数，将 %rax 符号扩展到 %rdx:%rax，类似于 cltq。q 和 o 分别代表四字 quad-word 和八字 oct-word。

  • imulq S：%rdx:%rax <- S * %rax，有符号乘法。

    • 这里的 imulq 指令只有一个操作数，与上表中的不同。

  • mulq S：%rdx:%rax <- S * %rax，无符号乘法。

    • imulq 和 mulq 的区别在于如何对待操作数的符号位。

  • idivq S：%rdx <- %rdx:%rax mod S; %rax <- %rdx:%rax / S，有符号除法。

  • divq S：%rdx <- %rdx:%rax mod S; %rax <- %rdx:%rax / S，无符号除法。

• 两个只设置条件码的指令

  • cmp S1, S2：计算 S2 - S1 的值并设置条件码。

    • 典型地，该指令的意义是将 S2 与 S1 比较，也即“setg 会判断 S2 是否大于 S1”，而不是相反。

  • test S1, S2：计算 S2 & S1 的值并设置条件码。

    • 典型地，S1 和 S2 相同时表现为将其与 0 比较。

• set：使用条件码的指令

  指令	效果（不用死记）	描述
  sete D, setz D	D <- ZF	相等 / 零
  setne D, setnz D	D <- ~ZF	不相等 / 非零
  sets D	D <- SF	负数
  setns D	D <- ~SF	非负数
  setg D, setnle D	D <- ~(SF ^ OF) & ~ZF	有符号大于
  setge D, setnl D	D <- ~(SF ^ OF)	有符号大于等于
  setl D, setnge D	D <- SF ^ OF	有符号小于
  setle D, setng D	D <- (SF ^ OF) |ZF	有符号小于等于
  seta D, setnbe D	D <- ~CF & ~ZF	无符号大于
  setae D, setnb D	D <- ~CF	无符号大于等于
  setb D, setnae D	D <- CF	无符号小于
  setbe D, setna D	D <- CF | ZF	无符号小于等于

  • set 指令接受的操作数是 8 位寄存器。若条件为真，将其值设为 0000 0001，否则设为 0000 0000。

    • CSAPP 原书对此含混其词，仅说“将字节设为 0 或 1”。

• jmp：跳转指令

  • 同样使用条件码，且有和 set 相同的变体 je, jne 等。

  • jmp Label 直接跳转，jmp *Operand 从寄存器或内存中取地址间接跳转。

  • 当执行 pc 相对寻址时，pc 的值是跳转指令之后一条指令的地址。因此跳转指令的编码的相对地址要使用下一条指令的地址进行计算。

• cmov：条件传送指令

  • 同样使用条件码，且有和 set 相同的变体 cmove, cmove 等。

  • 题外话：CSAPP 中关于分支预测的一系列结论已经不完全适用现代 CPU 了。它们应对这种小小分支的能力超出这本书的想象，低抽象下的开发者没有必要担心性能下降而用三目运算符替代 if-else 控制流（高抽象下当然更没有必要）。万一实际中遇到非常复杂的情况，你也可以/应该现场 benchmark 一下。

控制流、语法糖与汇编

1. goto

   我们不管这个东西。它和裸汇编已经差不太多了。下面所有控制流都可以说是 goto 的语法糖。

2. if-else 分支

   xxxxxxxxxx
   if (condition) {
     then_statement;
   } else {
     else_statement;
   }
   

   典型地会被实现为

   xxxxxxxxxx
     if (!condition)
       goto false_tag;
     then_statement;
     goto done;
   false_tag:
     else_statement;
   done:
   

   此外还有另一种转译方式，请自行思考。

3. do-while 循环

   xxxxxxxxxx
   do {
     statement;
   } while (condition);
   

   典型地会被实现为

   xxxxxxxxxx
   loop:
     statement;
     if (condition)
       goto loop;
   

4. while 循环

   xxxxxxxxxx
   while (condition) {
     statement;
   }
   

   第一种转译方法是 gcc 在优化等级 -Og 下的转译方式，称为“跳转到中间（jump to middle）”：

   xxxxxxxxxx
     goto test;
   loop:
     statement;
   test:
     if (condition)
       goto loop;
   

   第二种转译方法是 gcc 在优化等级 -O1 下的转译方式，称为“guarded-do”，它实际上将 while 循环转译成了 do-while 循环：

   xxxxxxxxxx
     if (!condition)
       goto done;
   loop:
     statement;
     if (condition)
       goto loop;
   done:
   

5. for 循环

   xxxxxxxxxx
   for (initialisation; condition; increment) {
     statement;
   }
   

   实际上就是 while 循环的语法糖：

   xxxxxxxxxx
   {
     initialisation;
     while (condition) {
       statement;
       increment;
     }
   }
   

   此后和 while 循环的两种转译方式完全相同，不再赘述。

6. switch-case 分支

   这玩意就比较玄了。书上讲的是跳转表，但是感觉这玩意并没那么普适的样子。

   跳转表最重点的就是形如 jmp *L4(,%rdi,8) 的那一句。它本身实际上就是在连续的地址（此处是 %rdi 指向的）上又存放了一些地址，然后用前面提到过的 jmp *Operand 间接跳转过去。

函数调用 & 栈 & 数组/指针运算

感觉好水啊，对着书看五分钟完事了吧。

结构体对齐与空间

对齐规则：$K$$K$ 字节的基本对象的地址必须是 $K$$K$ 的倍数；结构体本身亦需要一定的对齐量满足所有成员的对齐要求。

要使结构体所占空间最小，贪心地将所有字段按照大小降序排序即可。

当然实际应用中可以手动扰动或者对齐一下，在不更优（但也不一定更劣）的空间下让内存布局更好用一点。

7. 链接

section

• .text 已编译程序的机器代码

• .data 已初始化的全局和静态变量

• .bss 未初始化的全局和静态变量

  • COMMON 未初始化的全局变量；.bss 未初始化的静态变量以及初始化为 0 的全局或静态变量

• .symtab 定义和引用的函数和全局变量

• ABS 不应该被重定位的符号

• UNDEF 未定义的符号

• COMMON 还未被分配位置的未初始化的数据目标

强弱符号

• 强符号：函数和已初始化的全局变量

• 弱符号：未初始化的全局变量

重定位

xxxxxxxxxx
for (auto &s : sections) {
  for (auto &r : relocation_entries) {
    auto refptr = s + r.offset;
    
    if (r.type == R_X86_64_PC32) {
      refaddr = ADDR(s) + r.offset;
      *refptr = static_cast<unsigned>(ADDR(r.symbol) + r.addend - refaddr);
    }
    
    if (r.type == R_X86_64_32)
      *refptr = static_cast<unsigned>(ADDR(r.symbol) + r.addend);
  }
}

8. 异常控制流

异常

进程控制

​x
#include <sys/types.h>
#include <unistd.h>

pid_t fork(void); // 子进程返回 0；父进程返回子进程 pid，出错返回 -1

xxxxxxxxxx
#include <sys/types.h>
#include <sys/wait.h>

pid_t waitpid(pid_t pid, int *statusp, int options); // 成功返回子进程 pid，WNOHANG 返回 0，出错返回 -1

pid_t wait(int *statusp); // wait(&status) 等价于 waitpid(-1, &status, 0);

10. Linux 系统 I/O 接口

xxxxxxxxxx
#include <unistd.h>

ssize_t read(int fd, void *buf, size_t n); // 成功返回读的字节数，EOF 返回 0，失败返回 -1

int dup2(int oldfd, int newfd); // 成功返回非负的描述符，失败返回 -1