CSAPP 全书笔记

#系统 · #CSAPP · #汇编 · #链接 · #虚拟内存 · #并发 · #网络编程

参考：深入理解计算机系统（CSAPP）第三版 - hansimov.gitbook.io，CMU 课程 15-213。以「知识点讲解 + 代码对照」方式组织。

全书结构

第一部分：程序结构和执行（第1~6章）—— 从程序员视角看计算机系统如何执行程序
第二部分：在系统上运行程序（第7~9章）—— 程序如何在操作系统上运行
第三部分：程序间的交互和通信（第10~12章）—— 程序如何与外部世界交互

第一部分：程序结构和执行

第1章：计算机系统漫游

1.1 信息就是位 + 上下文

计算机中所有信息——程序、数据、文件——最终都是一串比特（bit）。相同的比特在不同上下文中含义完全不同。

例如 0x4D502F46 可以是：

无符号整数 1296912198
有符号整数 -1296912198
浮点数
4 个 ASCII 字符 MP/F

// 用代码验证：同一组字节，不同解读方式
unsigned int ui = 0x4D502F46;
printf("无符号整数: %u\n", ui);       // → 1296912198
printf("有符号整数: %d\n", (int)ui);  // → -1296912198
printf("ASCII 字符: %c%c%c%c\n",
    ((char*)&ui)[0], ((char*)&ui)[1],
    ((char*)&ui)[2], ((char*)&ui)[3]); // → F/PM (小端序)

1.2 程序被其他程序翻译成不同的格式

从 C 源程序到可执行文件的四阶段：

mermaid

graph LR
    A["hello.c<br/>(源程序)"] -->|"预处理器<br/>(cpp)"| B["hello.i<br/>(修改后的源程序)"]
    B -->|"编译器<br/>(cc1)"| C["hello.s<br/>(汇编程序)"]
    C -->|"汇编器<br/>(as)"| D["hello.o<br/>(可重定位目标文件)"]
    D -->|"链接器<br/>(ld)"| E["hello<br/>(可执行目标文件)"]

// hello.c — 经典的第一个程序
#include <stdio.h>
int main() {
    printf("hello, world\n");
    return 0;
}

bash

# 逐步查看每个阶段的输出
gcc -E hello.c -o hello.i        # 预处理：展开 #include / #define
gcc -S hello.i -o hello.s        # 编译：C → 汇编
gcc -c hello.s -o hello.o        # 汇编：汇编 → 机器码
gcc hello.o -o hello             # 链接：合并库函数

1.3 了解编译系统如何工作是大有益处的

优化程序性能：理解机器代码和编译器优化，写出编译器能优化的代码
理解链接时错误：理解链接器如何解析符号，排查 "undefined reference" 等问题
避免安全漏洞：理解缓冲区溢出等原理，避免写出有安全漏洞的代码

1.4 处理器读并解释存储在内存中的指令

系统硬件组成：

mermaid

graph TB
    CPU["CPU"]
    PC["程序计数器 PC"]
    RF["寄存器文件"]
    ALU["ALU 算术/逻辑单元"]
    BUS["系统总线"]
    MEM["主存（内存）"]
    IO_BRIDGE["I/O 桥接器"]
    IO_BUS["I/O 总线"]
    USB["USB 控制器"]
    GFX["图形适配器"]
    DISK["磁盘控制器"]
    DISK_DEV["磁盘"]
    KB["键盘/鼠标"]
    DISPLAY["显示器"]

    CPU --> PC
    CPU --> RF
    CPU --> ALU
    CPU --> BUS
    BUS --> MEM
    BUS --> IO_BRIDGE
    IO_BRIDGE --> IO_BUS
    IO_BUS --> USB --> KB
    IO_BUS --> GFX --> DISPLAY
    IO_BUS --> DISK --> DISK_DEV

执行 hello 程序时发生的事（shell 命令行 ./hello）：

shell 读取 "./hello" 字符到寄存器
shell 调用 execve 加载 hello 可执行文件
用 DMA（直接内存存取） 将 hello 的数据从磁盘复制到主存，CPU 不参与
CPU 开始执行 hello 的 main 函数中的机器指令
机器指令将 "hello, world\n" 字节从主存复制到寄存器文件
再从寄存器文件复制到显卡的显存 → 显示器显示

1.5 高速缓存至关重要

存储器层次结构中的关键思想：利用局部性原理（Locality），用更小更快的存储设备作为更大更慢设备的缓存。

mermaid

graph TB
    REG["CPU 寄存器<br/>0 周期, ~100B"]
    L1["L1 Cache (SRAM)<br/>~4周期, ~32KB"]
    L2["L2 Cache (SRAM)<br/>~10周期, ~256KB"]
    L3["L3 Cache (SRAM)<br/>~40周期, ~8MB"]
    MEM["主存 (DRAM)<br/>~200周期, ~GBs"]
    DISK["本地磁盘 (SSD/HDD)<br/>~100K周期, ~TBs"]
    REMOTE["远程存储<br/>~网络延迟, ~无限"]

    REG --> L1 --> L2 --> L3 --> MEM --> DISK --> REMOTE

1.6 存储设备形成层次结构

层级	存储类型	特征
L0	寄存器	CPU 内部，最快
L1~L3	SRAM 高速缓存	片上/片外
L4	DRAM 主存	易失性
L5	本地磁盘	非易失性
L6	远程存储	分布式文件系统

1.7 操作系统管理硬件

操作系统是应用程序和硬件之间的中间层，提供三个基本抽象：

抽象	对应硬件	概念
文件	I/O 设备	字节序列，统一了所有 I/O
虚拟内存	主存 + 磁盘	每个进程独占的地址空间
进程	CPU + 主存 + I/O	正在运行的程序实例

1.8 系统之间利用网络通信

网络可视为另一种 I/O 设备。通过网络，系统可以访问远程资源，形成一个更大的"系统"。

1.9 重要主题

Amdahl 定律：对系统某部分加速时，整体性能提升取决于该部分的重要性。

S = \frac{1}{(1 - α) + α / k}

其中 $α$ 是可加速部分的比例， $k$ 是加速比。假设 60% 可并行且加速 3 倍，理论加速比 = 1 / (0.4 + 0.6/3) ≈ 1.67×。即便把 60% 加速到无穷，整体最多也只能加速 1/0.4 = 2.5 倍。

并发与并行：

线程级并发：多核 / 超线程（同时多线程，SMT）
指令级并行：流水线，超标量，每个周期执行多条指令
单指令多数据（SIMD）：一条指令处理多个数据

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

2.1 信息存储

字节（Byte） 是最小可寻址的内存单位。绝大多数计算机使用 8 位的字节。

大小端（Endian）：

字节序	说明	使用场景
小端序（Little Endian）	低字节存储在低地址	x86、ARM（大部分情况）
大端序（Big Endian）	高字节存储在低地址	网络字节序、PowerPC

示例：0x01234567 在地址 0x100 处的存储
小端：[0x100]=67, [0x101]=45, [0x102]=23, [0x103]=01
大端：[0x100]=01, [0x101]=23, [0x102]=45, [0x103]=67

C 语言中数据类型大小（字节）：

类型	x86-64
char	1
short	2
int	4
long	8
float	4
double	8
指针	8

// 大小端测试与字节查看
#include <stdio.h>

typedef unsigned char *byte_pointer;

void show_bytes(byte_pointer start, size_t len) {
    for (size_t i = 0; i < len; i++)
        printf(" %.2x", start[i]);
    printf("\n");
}

void show_int(int x)   { show_bytes((byte_pointer)&x, sizeof(int)); }
void show_float(float x) { show_bytes((byte_pointer)&x, sizeof(float)); }

int main() {
    int val = 0x87654321;
    byte_pointer p = (byte_pointer)&val;
    show_bytes(p, 1);  // 小端: 21  (最低字节在最低地址)
    show_bytes(p, 2);  // 小端: 21 43
    show_bytes(p, 3);  // 小端: 21 43 65

    // 判断本机字节序
    int x = 1;
    if (*(char*)&x == 1)
        printf("小端序 (Little Endian)\n");  // x86/ARM 通常输出这个
    else
        printf("大端序 (Big Endian)\n");     // 网络字节序
    return 0;
}

2.2 整数表示

补码（Two's Complement）：现代计算机普遍采用的整数编码方式。

正数：直接二进制表示
负数：对应正数按位取反 + 1
范围： $[- 2^{w - 1}, 2^{w - 1} - 1]$ （w 位）

w 位	无符号范围	补码范围
8	0 ~ 255	-128 ~ 127
16	0 ~ 65535	-32768 ~ 32767
32	0 ~ 4,294,967,295	-2,147,483,648 ~ 2,147,483,647
64	0 ~ 1.84×10¹⁹	-9.22×10¹⁸ ~ 9.22×10¹⁸

2.3 整数运算

溢出：结果超出表示范围时发生。

无符号加法溢出： $s = x + y \mod 2^{w}$ 补码加法溢出：正溢出（结果变为负数）、负溢出（结果变为正数）

#include <limits.h>
#include <stdio.h>

int main() {
    printf("INT_MAX = %d (0x%x)\n", INT_MAX, INT_MAX);   // 2147483647
    printf("INT_MIN = %d (0x%x)\n", INT_MIN, INT_MIN);   // -2147483648

    // 正溢出：结果变为负数
    int a = INT_MAX;
    printf("INT_MAX + 1 = %d\n", a + 1);  // → -2147483648

    // 负溢出：结果变为正数
    int b = INT_MIN;
    printf("INT_MIN - 1 = %d\n", b - 1);  // → 2147483647

    // 无符号溢出（绕回）
    unsigned int u = 0xFFFFFFFF;
    printf("0xFFFFFFFF + 1 = 0x%x\n", u + 1);  // → 0x0

    // 位运算经典操作
    int negate(int x) { return ~x + 1; }  // 取负数(补码)
    int least_bit(int x) { return x & (-x); }  // 获取最低有效位

    return 0;
}

2.4 浮点数

IEEE 754 浮点表示： $V = (- 1)^{s} \times M \times 2^{E}$

格式	符号位	阶码位	尾数位	总位数
单精度 (float)	1	8	23	32
双精度 (double)	1	11	52	64

四种情况：

阶码	尾数	含义
全 0	全 0	±0
全 0	非 0	非规格化数（极小值）
非全 0 且非全 1	任意	规格化数（常规）
全 1	全 0	±∞
全 1	非 0	NaN

精度问题：浮点数无法精确表示所有实数。0.1 + 0.2 != 0.3 源于二进制浮点数无法精确表示十进制小数。

#include <math.h>
#include <float.h>

int main() {
    // 浮点数无法精确表示 0.1
    float f = 0.1f;
    printf("0.1 的 float 表示: %.20f\n", f);  // 0.10000000149011611938

    // 经典的 0.1 + 0.2 != 0.3
    if (0.1f + 0.2f == 0.3f)
        printf("相等\n");
    else
        printf("0.1 + 0.2 != 0.3 (差: %.20f)\n", (0.1f + 0.2f) - 0.3f);

    // 浮点数比较的正确方式：用 epsilon
    float a = 0.1f + 0.2f, b = 0.3f;
    if (fabsf(a - b) < FLT_EPSILON)
        printf("近似相等\n");

    // IEEE 754 特殊值
    float inf = 1.0f / 0.0f;  // 正无穷
    float nan = 0.0f / 0.0f;  // NaN
    printf("inf = %f, isnan=%d\n", inf, isnan(nan));
    return 0;
}

整数的位级转换：

// short → unsigned short (位不变，解释变)
short sx = -12345;         // cf c7
unsigned short usx = sx;   // 53191 (= 65536 - 12345)
printf("sx = %d, usx = %u\n", sx, usx);

// 符号扩展 (高位填充符号位)
short s = -12345;          // cf c7
int i = s;                 // ff ff cf c7
printf("s=%d, i=%d\n", s, i);

// 截断
int big = 53191;           // 00 00 cf c7
short small = (short)big;  // cf c7 → 解释为 -12345
printf("big=%d, small=%d\n", big, small);

第3章：程序的机器级表示

3.1 历史观点

Intel 处理器系列俗称 x86，从 1978 年的 8086 发展到今天的 x86-64。x86-64 是 x86 的 64 位扩展，由 AMD 首创，后被 Intel 采纳。

3.2 程序编码

C 程序 → 汇编 → 目标文件 → 可执行文件。

两种汇编格式：

AT&T 格式：GCC/GDB 默认，movq %rax, %rbx（源 → 目标）
Intel 格式：Microsoft/Windows 默认，mov rbx, rax（目标 ← 源）

3.3 数据格式

C 类型	后缀	大小(字节)
char	b (byte)	1
short	w (word)	2
int	l (long word)	4
long / 指针	q (quad word)	8
float	s (single)	4
double	l (double)	8

3.4 访问信息

x86-64 寄存器：

64 位	32 位	16 位	8 位	用途
%rax	%eax	%ax	%al	返回值
%rbx	%ebx	%bx	%bl	被调用者保存
%rcx	%ecx	%cx	%cl	第4参数
%rdx	%edx	%dx	%dl	第3参数
%rsi	%esi	%si	%sil	第2参数
%rdi	%edi	%di	%dil	第1参数
%rsp	%esp	%sp	%spl	栈指针
%rbp	%ebp	%bp	%bpl	帧指针（可选）
%r8~%r15	%r8d~%r15d	%r8w~%r15w	%r8b~%r15b	第5~6参数+通用

操作数类型：

立即数：$0x1F、$577 — 常数值
寄存器：%rax — 寄存器内容
内存引用：(%rax)、8(%rbx,%rcx,4) — 内存地址的内容

3.5 算术和逻辑操作

指令	效果
mov S, D	D ← S
lea S, D	D ← &S（加载有效地址，不访问内存）
add S, D	D ← D + S
sub S, D	D ← D - S
and S, D	D ← D & S
or S, D	D ← D \| S
xor S, D	D ← D ^ S
sal/shl k, D	D ← D << k
sar k, D	D ← D >> k（算术右移，补符号位）
shr k, D	D ← D >> k（逻辑右移，补 0）

从 C 到汇编的代码对照：

// 源代码: exchange.c
long exchange(long *xp, long y) {
    long x = *xp;
    *xp = y;
    return x;
}

asm

# GCC -Og -S exchange.c 生成的汇编 (AT&T 格式)
exchange:
    movq    (%rdi), %rax    # 从 *xp 取值到 %rax (返回值)
    movq    %rsi, (%rdi)    # 把 y 写入 *xp
    ret                     # 返回，%rax 已包含原始 *xp

两种汇编格式对比：

asm

# AT&T 格式 (GCC/GDB/objdump 默认)
movq    %rax, %rbx        # 源寄存器 → 目标寄存器
movq    $0x10, (%rcx)     # 立即数 → 内存

# Intel 格式 (Microsoft/Windows)
mov     rbx, rax          # 目标 ← 源
mov     qword ptr [rcx], 10h

x86-64 过程调用约定：

前 6 个参数：%rdi, %rsi, %rdx, %rcx, %r8, %r9，返回值在 %rax，超过 6 个参数通过栈传递。

// 多参数函数
long proc(long a1, long *a1p, int a2, int *a2p,
          short a3, short *a3p, char a4, char *a4p) {
    *a1p += a1; *a2p += a2; *a3p += a3; *a4p += a4;
    return *a1p;
}

asm

# 参数寄存器映射: a1→%rdi, a1p→%rsi, a2→%edx, a2p→%rcx
#                  a3→%r8w, a3p→%r9, a4和a4p在栈上
proc:
    movq    16(%rsp), %rax     # 取 a4p (栈上第7个参数)
    addq    %rdi, (%rsi)       # *a1p += a1
    addl    %edx, (%rcx)       # *a2p += a2
    addw    %r8w, (%r9)        # *a3p += a3
    movzbl  8(%rsp), %edx      # 取 a4
    addb    %dl, (%rax)        # *a4p += a4
    movq    (%rsi), %rax       # 返回值 = *a1p
    ret

3.6 控制

条件码寄存器：

标志	含义
CF	进位标志（无符号溢出）
ZF	零标志（结果为 0）
SF	符号标志（结果为负）
OF	溢出标志（补码溢出）

跳转指令：jmp、je、jne、js、jns、jg、jge、jl、jle、ja、jae、jb、jbe

条件传送：cmov 系列指令在不进行分支预测的情况下实现条件赋值，减少分支预测失败的代价。现代编译器（-O1+）会尽可能将分支转为 cmov。

// 条件分支
long absdiff(long x, long y) {
    long result;
    if (x < y) result = y - x;
    else       result = x - y;
    return result;
}

asm

# 条件跳转版本 (分支版本)
absdiff:
    cmpq    %rsi, %rdi        # 比较 x 和 y
    jge     .L2               # x >= y 则跳转
    movq    %rsi, %rax
    subq    %rdi, %rax        # result = y - x
    ret
.L2:
    movq    %rdi, %rax
    subq    %rsi, %rax        # result = x - y
    ret

// 条件传送版本 — 消除分支预测
long absdiff_cmov(long x, long y) {
    long rval = y - x;
    long eval = x - y;
    long ntest = x >= y;
    if (ntest) rval = eval;
    return rval;
}

asm

# cmov 汇编 — 无分支!
absdiff_cmov:
    movq    %rsi, %rax
    subq    %rdi, %rax        # rval = y - x
    movq    %rdi, %rdx
    subq    %rsi, %rdx        # eval = x - y
    cmpq    %rsi, %rdi        # 比较 x, y
    cmovge  %rdx, %rax        # x>=y 时 rax=eval
    ret

循环的三种汇编形态：do-while 最简单、while 是"跳转到中间"(jump-to-middle)、for 是优化的 while (guarded-do)。

// C: while 循环 (阶乘)
long fact_while(long n) {
    long result = 1;
    while (n > 1) {
        result *= n;
        n = n - 1;
    }
    return result;
}

asm

# while → jump-to-middle 汇编
fact_while:
    movl    $1, %eax
    jmp     .L5                # 先跳转到测试条件
.L6:
    imulq   %rdi, %rax
    subq    $1, %rdi
.L5:
    cmpq    $1, %rdi           # 测试 n>1
    jg      .L6
    ret

3.7 过程

调用/返回指令：

call Proc   →  push rip; jmp Proc    （压入返回地址，跳转）
ret         →  pop rip               （弹出返回地址，返回）

被调用者保存寄存器：%rbx, %rbp, %r12~%r15 — 被调用的函数必须保证这些寄存器值不变 调用者保存寄存器：其他所有寄存器 — 调用者需自行保存

3.8 数组分配与访问

数组在内存中连续存储。访问 E[i] 相当于 &E[0] + i * sizeof(T)。

多维数组的行优先排列（C 语言）：

int A[R][C] → A[i][j] = &A + (i*C + j) * sizeof(int)

3.9 异质的数据结构

结构体（struct）：成员连续存储，但存在对齐要求：

每个成员的地址必须是其大小的倍数
结构体总大小必须是最大成员大小的倍数
成员之间可能有填充（padding）

// 结构体对齐：成员顺序影响总大小
struct S1 {
    char  c;    // 1B, 偏移 0
    int   i;    // 4B, 偏移 4 (不是 1! 需要对齐)
    short s;    // 2B, 偏移 8
};  // 总大小 12 (对齐到 4 的倍数)

struct S2 {
    int   i;    // 偏移 0
    char  c;    // 偏移 4
    short s;    // 偏移 6 (不是 5!)
};  // 总大小 8 — 仅仅调换顺序就节省了 4 字节!

int main() {
    printf("sizeof(S1) = %zu (预期12)\n", sizeof(struct S1));
    printf("sizeof(S2) = %zu (预期8)\n",  sizeof(struct S2));
    return 0;
}

3.10 缓冲区溢出与安全

在机器级别，指针就是地址。越界写入可能破坏返回地址，导致缓冲区溢出攻击。

// 经典的缓冲区溢出演示
void echo() {
    char buf[8];
    gets(buf);  // 危险！不检查缓冲区大小
    puts(buf);
}
// x86-64 栈布局: [返回地址 8B] [旧的%rbp 8B] [buf[7]...buf[0] 8B]
// buf 只有 8 字节，但 gets 可写入任意长度
// 写入超过 16 字节 = 覆盖返回地址!

// 安全替代: fgets 限制读取长度
void safe_echo() {
    char buf[8];
    fgets(buf, sizeof(buf), stdin);
    puts(buf);
}

对抗缓冲区溢出的三大防线：

栈随机化（ASLR）：每次运行程序，栈地址随机偏移
栈破坏检测（Stack Canary）：在栈帧中放入金丝雀值，检测是否被覆盖
限制可执行代码区域（NX/XD）：栈不可执行

bash

# 编译时启用保护
gcc -fstack-protector -D_FORTIFY_SOURCE=2 -O2 \
    -Wformat -Wformat-security \
    -fPIE -pie -z relro -z now  program.c

3.11 浮点代码

x86-64 使用 AVX/SSE 指令集处理浮点数，有独立的 16 个 256 位 YMM 寄存器（%ymm0~%ymm15）。

第4章：处理器体系结构

4.1 Y86-64 指令集体系结构

CSAPP 定义了一个简化的教学指令集 Y86-64，作为 x86-64 的子集。

4.2 逻辑设计和硬件控制语言 HCL

布尔代数在硬件设计中的应用。HCL（Hardware Control Language）用于描述处理器控制逻辑。

4.3 顺序实现（SEQ）

取指 → 译码 → 执行 → 访存 → 写回 → 更新 PC

每个阶段占一个时钟周期，每个周期处理一条指令。

4.4 流水线（PIPE）通用原理

流水线将指令处理分成多个阶段，使得多条指令可以同时在不同阶段执行。

mermaid

graph LR
    subgraph 非流水线
        A1["指令1: F|D|E|M|W"] --> A2["指令2: F|D|E|M|W"] --> A3["指令3: F|D|E|M|W"]
    end
    subgraph 流水线
        B1["指令1: F|D|E|M|W"]
        B2["指令2:    F|D|E|M|W"]
        B3["指令3:       F|D|E|M|W"]
        B4["指令4:          F|D|E|M|W"]
    end

吞吐量 = 1 条指令/周期（理想情况下性能提升 5×）

4.5 流水线冒险

冒险类型	描述	解决方案
数据冒险	后续指令依赖前面指令的结果	数据转发（Forwarding）、停顿（Stall）
控制冒险	分支指令不确定下一条指令地址	分支预测、分支预测错误惩罚

asm

# 数据冒险示例：I2 依赖 I1 的结果
addq %rax, %rbx    # I1: rbx = rbx + rax
subq %rbx, %rcx    # I2: rcx = rcx - rbx  ← 依赖 I1 的 rbx

# 无转发: I2 需等 I1 写回 (额外 2 个 nop)
# 有转发: ALU 输出直接转发到下次 ALU 输入，I2 无需等待

# 加载-使用冒险（最麻烦的数据冒险）
mrmovq (%rax), %rbx  # 加载 rbx (Mem 阶段才得到值)
addq   %rbx, %rcx    # 使用 rbx (Exec 阶段就需要)
# 即使有转发也需要 1 个 stall 周期

第5章：优化程序性能

5.1 优化编译器的能力和局限性

编译器受内存别名使用和函数调用副作用限制，不能随意优化。例如 *xp += *yp; *xp += *yp; 不能优化为 *xp += 2 * *yp;，因为 xp 和 yp 可能指向同一地址（别名）。

5.2 表示程序性能

每元素的周期数（CPE） 是衡量程序性能的有效指标。

5.3 消除循环的低效率

代码移动（Code Motion）：将循环不变量移出循环体。

// 差：每次循环都调用 strlen — O(n²)
for (int i = 0; i < strlen(s); i++) { ... }

// 好：strlen 只调用一次 — O(n)
int len = strlen(s);
for (int i = 0; i < len; i++) { ... }

5.4 减少过程调用 / 消除不必要的内存引用

// 使用寄存器中的累积变量，代替反复读写内存
// 版本1 (差): 每次循环读写 *dest (两次内存访问)
for (i = 0; i < length; i++) {
    *dest = *dest OP data[i];  // 读*dest, 加, 写*dest
}

// 版本2 (好): 用局部变量作为累积器 (只在寄存器操作)
data_t acc = IDENT;
for (i = 0; i < length; i++) {
    acc = acc OP data[i];      // 纯寄存器操作!
}
*dest = acc;                   // 最后写一次内存

asm

# 版本1 的循环体 (每次循环读写 *dest):
.L2:
    movq    (%rbx), %rax      # 从*dest读 (多余的内存读!)
    addq    (%rcx), %rax      # + val
    movq    %rax, (%rbx)      # 写回*dest (多余的内存写!)

# 版本2 的循环体 (只在寄存器操作):
.L2:
    addq    (%rcx), %rax      # acc += val  (rax 是寄存器)

5.5 理解现代处理器

超标量（Superscalar）：每个周期可以执行多条指令。 乱序执行（Out-of-Order）：处理器可以不按程序顺序执行指令。 关键路径（Critical Path）：限制程序性能的最大瓶颈——一系列必须顺序执行的操作。

5.6 循环展开与多累积变量

循环展开：减少循环开销和增加指令级并行性。 多个累积变量：打破顺序依赖，创建多条独立运算链让 CPU 并行执行。

// 2×2 展开 + 2个累积变量 — 打破关键路径
void combine6(vec_ptr v, data_t *dest) {
    long i, length = vec_len(v);
    long limit = length - 1;
    data_t acc0 = IDENT;
    data_t acc1 = IDENT;
    // 两条独立的运算链，CPU可并行执行
    for (i = 0; i < limit; i += 2) {
        acc0 = acc0 OP get_element(v, i);
        acc1 = acc1 OP get_element(v, i + 1);
    }
    for (; i < length; i++)
        acc0 = acc0 OP get_element(v, i);
    *dest = acc0 OP acc1;
}

mermaid

graph LR
    subgraph "单累积变量: 一条关键路径"
        A1["acc ← acc+data[i]"] --> A2["acc ← acc+data[i+1]"] --> A3["..."]
    end
    subgraph "双累积变量: 两条并行路径"
        B1["acc0 ← acc0+data[i]"] --> B3["..."]
        B2["acc1 ← acc1+data[i+1]"] --> B4["..."]
    end

5.7 存储器性能优化

// 内存别名使用限制编译器优化
void twiddle1(long *xp, long *yp) {
    *xp += *yp;    // 读*xp, 读*yp, 加, 写*xp
    *xp += *yp;    // 不能合并为 *xp += 2**yp!
}                  // 因为 xp 可能等于 yp (别名)

5.8 性能分析工具

bash

# gprof 分析
gcc -pg -O2 prog.c -o prog && ./prog && gprof prog gmon.out

# perf 分析 (更现代)
perf stat ./prog                      # 总体统计
perf record ./prog && perf report     # 热点分析
perf stat -e cache-misses,cache-references ./prog   # cache
perf stat -e branch-misses,branches ./prog          # 分支预测

第6章：存储器层次结构

6.1 存储技术

技术	访问时间	特性
SRAM	~4× CPU 周期	快、贵、用作 Cache
DRAM	~200× CPU 周期	较慢、便宜、用作主存
磁盘（机械）	~10ms	慢、大容量、非易失
SSD	~100μs	快于 HDD，无机械部件

6.2 局部性

时间局部性：刚访问过的数据很可能再次被访问。 空间局部性：即将访问的数据可能在刚访问数据的附近。

// 良好的局部性 (步长为1)
for (int i = 0; i < N; i++)
    sum += a[i];

// 较差的局部性 (大步长)
for (int i = 0; i < N; i++)
    sum += a[i * stride];

6.3 存储器层次结构

mermaid

graph TD
    L0["L0: 寄存器"]
    L1["L1: L1 Cache (SRAM)"]
    L2["L2: L2 Cache (SRAM)"]
    L3["L3: L3 Cache (SRAM)"]
    L4["L4: 主存 (DRAM)"]
    L5["L5: 本地二级存储 (SSD/HD)"]
    L6["L6: 远程存储 (分布式)"]

    L0 --> L1 --> L2 --> L3 --> L4 --> L5 --> L6

核心思想：每层缓存下一层的子集。程序倾向于访问层次中较上层的存储，这就是缓存命中的概念。

6.4 高速缓存存储器

Cache 结构参数：

S：组数
E：每组行数（E=1 为直接映射，E>1 为组相联）
B：每行的块大小

地址分解为：标记（Tag）| 组索引（Set Index）| 块偏移（Block Offset）

// 直接映射 Cache (E=1) 模拟实现
typedef struct { int valid; unsigned long tag; char block[64]; } cache_line_t;
cache_line_t cache[64]; // S=64

int cache_access(unsigned long addr) {
    int set_index = (addr >> 6) & 0x3F;    // 提取组索引
    unsigned long tag = addr >> 12;         // 提取标记
    if (cache[set_index].valid && cache[set_index].tag == tag)
        return 1;  // 命中!
    // 未命中：从内存加载
    cache[set_index].valid = 1;
    cache[set_index].tag = tag;
    return 0;
}

6.5 写与缓存

写命中：直写（Write-through，同时写内存）vs 写回（Write-back，只写 Cache，延迟写内存）
写不命中：写分配（Write-allocate，先加载到 Cache 再写）vs 非写分配（No-write-allocate，直接写内存）

现代 CPU 通常采用：写回 + 写分配。

6.6 真实 Cache 解剖

Intel Core i7 的 Cache 层次：每个核心有独立的 L1-I（32KB）、L1-D（32KB）、L2（256KB），共享 L3（8MB）。

6.7 缓存友好的代码

关注内层循环的访问模式
尽量使用步长为 1 的顺序访问
对多维数组使用正确的循环顺序

矩阵乘法分块（Tiling） — 将数据切分为 Cache 能装下的小块：

// 分块矩阵乘法 (CSAPP Cache Lab 风格)
// 目标: 3个 B×B 分块恰好放入 L1 Cache
// L1D=32KB, 3×B²×8 ≤ 32KB → B ≤ 36
void matmul_blocked(int N, double *A, double *B, double *C) {
    int BLOCK = 32;
    memset(C, 0, N * N * sizeof(double));
    for (int ii = 0; ii < N; ii += BLOCK)
        for (int jj = 0; jj < N; jj += BLOCK)
            for (int kk = 0; kk < N; kk += BLOCK)
                for (int i = ii; i < ii+BLOCK && i < N; i++)
                    for (int k = kk; k < kk+BLOCK && k < N; k++) {
                        double r = A[i*N + k];
                        for (int j = jj; j < jj+BLOCK && j < N; j++)
                            C[i*N + j] += r * B[k*N + j];
                    }
}

6.8 常见的与内存相关的错误

// 错误示例
void bad1() { int *p; *p = 42; }              // 未初始化指针
void bad3() {
    int *p = malloc(sizeof(int) * 5);
    *(p + 5) = 20;  // 越界! (5个元素, 索引0~4)
}
void bad4() { int *p = malloc(4); free(p); *p = 99; }  // use-after-free
void bad5() { int *p = malloc(4); free(p); free(p); }  // double-free

bash

# 内存错误检测工具
gcc -fsanitize=address -g prog.c -o prog  # AddressSanitizer (ASan)
valgrind --leak-check=full ./prog          # Valgrind

第二部分：在系统上运行程序

第7章：链接

7.1 编译器驱动程序

GCC 编译器驱动程序自动调用：预处理器 → 编译器 → 汇编器 → 链接器。

7.2 静态链接

链接器任务：

符号解析（Symbol Resolution）：将每个符号引用关联到唯一定义
重定位（Relocation）：将符号定义与内存地址关联

7.3 目标文件

三种目标文件：

可重定位目标文件（.o）：可与其他 .o 合并
可执行目标文件：可直接加载到内存执行
共享目标文件（.so）：可在运行时动态链接

7.4 可重定位目标文件（ELF 格式）

典型的 ELF 可重定位目标文件结构：

ELF 头
.text       (已编译程序的机器代码)
.rodata     (只读数据，如格式字符串)
.data       (已初始化的全局和静态变量)
.bss        (未初始化的全局和静态变量，不占实际空间)
.symtab     (符号表)
.rel.text   (.text 段的重定位信息)
.rel.data   (.data 段的重定位信息)
.debug      (调试符号表)
.line       (行号与指令地址映射)
.strtab     (字符串表)
段头部表    (描述各段的位置和大小)

7.5 符号和符号表

三种符号：

全局符号：由模块定义，可被其他模块引用
外部符号：由其他模块定义的全局符号
局部符号：只在本模块内可见（static 函数/变量）

7.6 符号解析

链接器将每个符号引用与一个符号定义关联起来。

多重定义处理规则：

不允许多个强符号（已初始化的全局变量/函数）
一个强符号 + 多个弱符号 → 选强符号
多个弱符号（未初始化的全局变量）→ 任选一个

// 强/弱符号规则演示
// file1.c
int x = 10;        // 强符号 (已初始化)
int y;             // 弱符号 (未初始化)

// file2.c
double x;          // 强符号! 类型不匹配 — 链接错误! 未定义行为!
int y = 20;        // 强符号! 覆盖 file1 的 y

// file3.c
int z;             // 弱符号

7.7 重定位

重定位节和符号定义：合并相同段，分配运行时地址
重定位节中的符号引用：修改代码中的引用地址

重定位类型：R_X86_64_PC32（PC 相对地址 32位）、R_X86_64_32（绝对地址 32位）

7.8~7.9 可执行目标文件与加载

加载器将可执行文件中的代码和数据从磁盘复制到内存，然后跳转到入口点（_start）。

实际的地址空间布局（Linux x86-64）：

0x7fff...  [栈]              ← %rsp（栈指针）
           ↓ 向下增长
           [共享库映射区域]
           [堆 (Heap)]
           ↑ 向上增长
0x00400000 [.bss / .data / .text]
0x00000000 [保留]

7.10 动态链接 — 实战对比

mermaid

flowchart TB
    subgraph Static["静态链接 (gcc -static)"]
        S1["main.o + libc.a<br/>全部打包进可执行文件"]
        S2["✅ 单文件部署，无依赖"]
        S3["❌ 二进制体积大 (2MB+)"]
        S4["❌ libc 有漏洞→全部重新编译"]
    end
    subgraph Dynamic["动态链接 (默认)"]
        D1["main.o + libc.so<br/>运行时加载 .so"]
        D2["✅ 二进制体积小 (KB级)"]
        D3["✅ 共享库可热升级"]
        D4["❌ 依赖缺失→无法启动"]
    end

维度	静态链接	动态链接
二进制大小	大 (所有 .a 打包)	小 (只存引用)
内存占用	高 (每进程独立副本)	低 (.so 各进程共享同一物理页)
部署便利性	✅ 单文件，scp 即可	❌ 需 libc.so + loader
安全更新	❌ 重新编译所有	✅ 只更新 .so 文件
启动速度	✅ 快 (无需加载 .so)	慢 (需 ld.so 解析动态符号)
符号冲突	编译期报错	运行时可能 crash (LD_PRELOAD)

共享库（.so） 在运行时或加载时被链接。位置无关代码（PIC） 可被加载到任意地址而不需修改。GOT（Global Offset Table） 和 PLT（Procedure Linkage Table） 实现延迟绑定（Lazy Binding）。

bash

# 创建共享库 (位置无关代码)
gcc -shared -fpic -o libvector.so addvec.c multvec.c
# 使用共享库
gcc -o prog main.c ./libvector.so
# 查看动态链接依赖
ldd ./prog
# 运行时指定额外搜索路径
LD_LIBRARY_PATH=/opt/mylibs ./prog
# 查看 ld.so 实际加载了哪个路径的 .so
LD_DEBUG=libs ./prog 2>&1 | head -30
# 静态编译 (包含所有依赖)
gcc -static -o myprogram myprogram.c

7.11~7.14

dlopen(), dlsym(), dlclose() 允许运行时动态加载。库打桩可拦截对共享库函数的调用，用于调试、性能分析。

// 运行时打桩: 拦截 malloc
// gcc -shared -fpic -o mymalloc.so mymalloc.c
// LD_PRELOAD="./mymalloc.so" ./prog

void *__real_malloc(size_t size);
void *malloc(size_t size) {
    printf("malloc(%zu) called\n", size);
    return __real_malloc(size);
}

工具	功能
`readelf`	查看 ELF 文件结构
`objdump`	反汇编和查看目标文件
`nm`	列出符号表
`ldd`	查看动态链接依赖
`size`	查看段大小

第8章：异常控制流

8.1 异常

异常（Exception） 是控制流的突发的、非本地的转移，响应处理器状态的变化。

异常处理过程：

处理器检测到异常事件
通过异常表跳转到异常处理程序
处理完成后根据异常类型决定返回位置

8.2 异常分类

类别	原因	异步/同步	返回行为
中断	I/O 设备信号	异步	总是返回到下一条指令
陷阱	有意（如系统调用）	同步	总是返回到下一条指令
故障	潜在可恢复错误（如缺页）	同步	可能返回到当前指令
终止	不可恢复错误（如硬件错误）	同步	不会返回

8.3 系统调用

syscall 指令触发陷阱进入内核模式。常用系统调用：

编号	名称	功能
0	read	读文件
1	write	写文件
2	open	打开文件
9	mmap	内存映射
57	fork	创建进程
59	execve	执行程序
60	_exit	退出进程

8.4 进程

进程是程序在运行时的实例，提供两个关键抽象：

独立逻辑控制流：每个进程独占 CPU
私有地址空间：每个进程独占内存

上下文切换：内核保存当前进程的上下文，恢复另一个进程的上下文。

8.5 进程控制

fork()：创建子进程，子进程返回 0，父进程返回子进程 PID
exit()：终止当前进程
waitpid()：等待子进程终止（回收僵尸进程）
execve()：加载并执行新程序

#include <unistd.h>
#include <sys/wait.h>
#include <stdio.h>

int main() {
    pid_t pid; int x = 1;

    pid = fork();
    if (pid == 0) {   // 子进程
        printf("child:  x=%d\n", ++x);  // x=2
        return 0;
    }
    printf("parent: x=%d\n", --x);      // x=0
    // 两个进程的 x 是独立的 (COW 隔离)

    int status;
    waitpid(pid, &status, 0);  // 等待子进程，避免僵尸
    return 0;
}

8.6 信号

信号（Signal） 是一种软件形式的异常，用于通知进程发生了某个事件。

常见信号：

信号	值	含义
SIGINT	2	Ctrl+C 中断
SIGKILL	9	强制终止（不可捕获）
SIGSEGV	11	段错误（无效内存访问）
SIGCHLD	17	子进程状态改变
SIGALRM	14	定时器到期

#include <signal.h>
volatile sig_atomic_t flag = 0;

void sigint_handler(int sig) {
    write(STDOUT_FILENO, "caught SIGINT\n", 14);
    flag = 1;  // 信号安全的标志变量
}

int main() {
    // 推荐使用 sigaction (可移植) 而非 signal
    struct sigaction sa;
    sa.sa_handler = sigint_handler;
    sigemptyset(&sa.sa_mask);
    sa.sa_flags = SA_RESTART;     // 自动重启被中断的系统调用
    sigaction(SIGINT, &sa, NULL);

    while (!flag) pause();  // 等待信号
    return 0;
}

8.7 非本地跳转

setjmp() / longjmp() 提供跨函数的控制流跳转，类似于 C 语言版 try/catch。

8.8 操作进程的工具

strace、ps、top、pmap、/proc 文件系统。

第9章：虚拟内存

9.1 物理和虚拟寻址

物理寻址：CPU 直接使用物理地址访问主存
虚拟寻址：CPU 使用虚拟地址，通过 MMU（内存管理单元）转换为物理地址

mermaid

graph LR
    CPU -->|"虚拟地址"| MMU["MMU<br/>(地址翻译)"]
    MMU -->|"物理地址"| MEM["主存"]

9.2 地址空间

虚拟地址空间是 N=2^n 个连续地址的集合。现代 64 位系统使用 48 位虚拟地址（256TB）。

9.3 虚拟内存作为缓存的工具

虚拟内存将虚拟页（VP） 映射到物理页（PP）。未分配的 VP 不占用任何磁盘空间。

页表（Page Table）：每个进程的页表将虚拟页映射到物理页。

9.4 虚拟内存作为内存管理的工具

简化链接：每个进程有统一的地址空间布局
简化加载：加载器从不实际复制数据，只映射
简化共享：共享库映射到多个进程的虚拟地址空间
简化内存分配：malloc 分配的是连续的虚拟地址

9.5 虚拟内存作为内存保护的工具

页表条目（PTE）包含权限位：SUP（内核模式）、READ/WRITE（读写权限）。

9.6 地址翻译

多级页表：现代系统使用四级页表减少内存开销。x86-64 使用 4 级页表，每级 9 位。

虚拟地址: [L4索引(9位) | L3索引(9位) | L2索引(9位) | L1索引(9位) | 偏移(12位)]

TLB（Translation Lookaside Buffer）：MMU 内部的小型硬件缓存，缓存最近使用的 PTE，加速地址翻译。

// 模拟最简单的单级页表地址翻译
#define VPN(va)   ((va) >> 12)        // 虚拟页号
#define VPO(va)   ((va) & 0xFFF)      // 页内偏移
#define PTE_P     1                    // Present 位

typedef struct { unsigned long ppn : 40; unsigned int flags : 16; } pte_t;

unsigned long translate(unsigned long va, pte_t *pt) {
    unsigned long vpn = VPN(va), vpo = VPO(va);
    if (!(pt[vpn].flags & PTE_P))
        return 0;  // 缺页! → 触发 page_fault_handler
    return (pt[vpn].ppn << 12) | vpo;
}

9.7 案例研究：Intel Core i7 / Linux 内存系统

Core i7 使用四级页表 + TLB。页大小可以是 4KB 或 2MB（大页）。

9.8 内存映射

mmap() 将磁盘文件映射到虚拟内存区域，实现零拷贝文件访问。

#include <sys/mman.h>
// 文件映射：像访问内存一样访问文件
int fd = open("file.txt", O_RDONLY);
off_t size = lseek(fd, 0, SEEK_END);
char *data = mmap(NULL, size, PROT_READ, MAP_PRIVATE, fd, 0);
// 现在 data[0], data[1]... 直接就是文件内容！无需 read() 拷贝
munmap(data, size);

9.9 动态内存分配

malloc / free 在堆区域管理动态内存。

分配器类型：

显式分配器：应用显式释放（malloc/free）
隐式分配器：垃圾收集器（GC）自动回收

CSAPP Malloc Lab 风格的简单分配器：

#define WSIZE 8
#define PACK(size, alloc) ((size) | (alloc))
#define GET(p)      (*(unsigned long *)(p))
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p)(GET(p) & 0x1)

static char *heap_listp;

void *simple_malloc(size_t size) {
    size_t asize = ((size + WSIZE - 1) / WSIZE + 1) * WSIZE;
    char *p = heap_listp;
    while (GET_SIZE(p) > 0) {              // 首次适配搜索
        if (!GET_ALLOC(p) && GET_SIZE(p) >= asize) {
            PUT(p, PACK(asize, 1));        // 放置
            return p + WSIZE;               // 返回有效载荷指针
        }
        p += GET_SIZE(p);
    }
    return NULL;
}

9.10 垃圾回收

Mark & Sweep：标记所有可达节点，清除不可达节点。Go 的三色标记就是它的变体。

9.11 常见的与内存相关的错误

详见 6.8 常见的与内存相关的错误中的代码示例（bad1~bad5）。本质上，虚拟内存相关的内存错误（越界、use-after-free、double-free）与缓存部分讨论的基础内存错误是一致的，区别在于虚拟内存层面还增加了对越界访问可能跨页导致缺页异常的情况。

bash

# 内存错误检测工具
gcc -fsanitize=address -g prog.c -o prog  # AddressSanitizer (ASan)
valgrind --leak-check=full ./prog          # Valgrind

9.12 mmap 实战 — 零拷贝文件 I/O

mmap 的本质是将文件映射到进程的虚拟地址空间，让 CPU 可以直接通过 load/store 指令读写文件——绕过 read/write 系统调用和用户态缓冲区：

#include <sys/mman.h>
#include <sys/stat.h>
#include <fcntl.h>

// 场景1: 读取大文件（比 read 快，尤其在顺序扫描时）
int fd = open("large_file.bin", O_RDONLY);
struct stat sb;
fstat(fd, &sb);
char *data = mmap(NULL, sb.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
// data[i] 直接访问文件内容，无需 read() 拷贝
munmap(data, sb.st_size);

// 场景2: 进程间共享内存（最快的 IPC）
int shm_fd = shm_open("/my_shm", O_CREAT | O_RDWR, 0644);
ftruncate(shm_fd, 4096);
char *shm = mmap(NULL, 4096, PROT_READ | PROT_WRITE, MAP_SHARED, shm_fd, 0);
// 父子进程/无关进程都可以映射同一个 shm_fd，数据立即可见

// 场景3: 匿名映射（替代 malloc 大块内存）
// MAP_ANONYMOUS: 不关联任何文件，直接分配物理内存
char *buf = mmap(NULL, 10*1024*1024, PROT_READ|PROT_WRITE,
                 MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
// 适合分配 1MB+ 的大块内存（glibc malloc 对大块也调用 mmap）

mermaid

flowchart LR
    subgraph Read["read() 路径：两次拷贝"]
        R1["磁盘"] -->|"DMA"| R2["Page Cache"]
        R2 -->|"CPU copy"| R3["用户态 buf"]
    end
    subgraph Mmap["mmap() 路径：零拷贝"]
        M1["磁盘"] -->|"DMA"| M2["Page Cache"]
        M2 -..->|"映射"| M3["用户可直接访问<br/>(虚拟地址映射到同一页)"]
    end

什么时候用 mmap 而不是 read：(1) 大文件顺序扫描 → mmap 通常更快；(2) 需要随机访问不同位置 → mmap 显著更快（不需反复 lseek+read）；(3) 小文件或一次性读取 → read 更简单。

第三部分：程序间的交互和通信

第10章：系统级 I/O

10.1 Unix I/O

所有 I/O 设备被模型化为文件，通过统一的接口访问。Unix I/O 核心操作：

打开文件：open() 返回文件描述符
读/写：read() / write()
改变文件位置：lseek()
关闭文件：close()

10.2 打开和关闭文件

每个进程维护一个打开文件表，文件描述符是小整数。

标准文件描述符：

fd	名称	用途
0	stdin	标准输入
1	stdout	标准输出
2	stderr	标准错误

10.3 读和写文件

ssize_t read(int fd, void *buf, size_t n);   // 返回实际读取的字节数
ssize_t write(int fd, const void *buf, size_t n);  // 可能写入少于 n 字节

10.4 用 RIO 包健壮地读写

处理**不足值（short count）**的情况——read / write 可能读写的数据比请求的少，需要循环重试：

// RIO 的健壮读写：自动处理不足值和信号中断
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) nread = 0;  // 被信号中断，重试
            else return -1;
        } else if (nread == 0)
            break;               // EOF
        nleft -= nread;
        bufp += nread;
    }
    return n - nleft;
}

10.5 读取文件元数据

stat() / fstat() 获取文件的元数据（大小、权限、类型等）。

10.6 共享文件

内核中的文件数据结构：

mermaid

graph LR
    FD1["描述符 1"] --> FTE1["文件表条目"]
    FD2["描述符 2"] --> FTE2["文件表条目"]
    FTE1 --> VNODE["v-node / i-node"]
    FTE2 --> VNODE

描述符表：每个进程独立（fd→文件表条目）
文件表：所有进程共享，记录文件偏移量
v-node 表：记录文件元数据（大小、权限等）

// fork 前打开的文件，父子进程共享文件偏移量！
int fd = open("foobar.txt", O_RDONLY);
if (fork() == 0) {
    read(fd, &c, 1);  // 子进程读第一个字符
    exit(0);
}
wait(NULL);
read(fd, &c, 1);  // 父进程读第二个字符 (偏移量被子进程更新了!)

10.7 I/O 重定向

dup2(oldfd, newfd) 复制描述符，实现 I/O 重定向。例如：dup2(fd, STDOUT_FILENO) 使 stdout 指向文件。

10.8~10.9 标准 I/O

C 标准库提供 fopen、fread、fprintf 等带缓冲的 I/O 函数。标准 I/O 有缓冲更好用，但不适合网络编程（会引起复杂问题）。

第11章：网络编程

11.1 客户端-服务器模型

基本操作：客户端发起请求，服务器响应请求。

11.2~11.3 网络基础

IP 地址 和端口唯一标识一个网络端点（套接字）。

协议栈层次：

层次	协议示例
应用层	HTTP, FTP, DNS
传输层	TCP, UDP
网络层	IP
链路层	Ethernet, WiFi

11.4 套接字接口

Socket API 核心函数调用流程：

mermaid

sequenceDiagram
    participant Client
    participant Server

    Server->>Server: socket()
    Server->>Server: bind()
    Server->>Server: listen()
    Server->>Server: accept() [阻塞]

    Client->>Client: socket()
    Client->>Server: connect()

    Server->>Server: accept() 返回

    Client->>Server: write() / read()
    Server->>Client: write() / read()

    Client->>Client: close()
    Server->>Server: close()

// CSAPP 风格的 echo 服务器
int open_listenfd(int port) {
    int listenfd = socket(AF_INET, SOCK_STREAM, 0);
    struct sockaddr_in serveraddr;
    memset(&serveraddr, 0, sizeof(serveraddr));
    serveraddr.sin_family = AF_INET;
    serveraddr.sin_addr.s_addr = htonl(INADDR_ANY);
    serveraddr.sin_port = htons((unsigned short)port);
    bind(listenfd, (struct sockaddr*)&serveraddr, sizeof(serveraddr));
    listen(listenfd, 1024);
    return listenfd;
}

void echo(int connfd) {
    char buf[1024]; ssize_t n;
    while ((n = read(connfd, buf, sizeof(buf))) > 0)
        write(connfd, buf, n);  // 原样回传
}

11.5~11.6 Web 服务器

使用 HTTP 协议处理 GET/HEAD 请求。CSAPP 提供了一个精简但完整的 Tiny Web 服务器实现——用 mmap 零拷贝发送静态文件。

第12章：并发编程

12.1 基于进程的并发

每个客户端请求由独立的子进程处理。优点：简单、地址空间隔离；缺点：进程创建开销大。

12.2 基于 I/O 多路复用的并发

select() / epoll() 让单个进程/线程管理多个文件描述符。

#include <sys/select.h>
fd_set read_set, ready_set;
FD_ZERO(&read_set);
FD_SET(listenfd, &read_set);

while (1) {
    ready_set = read_set;
    select(maxfd+1, &ready_set, NULL, NULL, NULL);
    for (int fd = 0; fd <= maxfd; fd++) {
        if (!FD_ISSET(fd, &ready_set)) continue;
        if (fd == listenfd) {  // 新连接
            int connfd = accept(listenfd, NULL, NULL);
            FD_SET(connfd, &read_set);
            if (connfd > maxfd) maxfd = connfd;
        } else {  // 已有连接 I/O
            char buf[1024]; int n = read(fd, buf, sizeof(buf));
            if (n > 0) write(fd, buf, n);
            else { close(fd); FD_CLR(fd, &read_set); }
        }
    }
}

12.3 基于线程的并发

线程是运行在进程上下文中的轻量级逻辑流，共享同一地址空间。

对比维度	进程	线程
地址空间	独立	共享
上下文切换开销	大（需切换页表）	小
创建/销毁开销	大	小
隔离性	强	弱（崩溃影响整个进程）

#include <pthread.h>
void *thread_handler(void *vargp) {
    int connfd = *((int*)vargp);
    free(vargp);
    pthread_detach(pthread_self());  // 分离线程，自动回收
    echo(connfd);
    close(connfd);
    return NULL;
}
// 每个请求创建一个线程
pthread_t tid;
pthread_create(&tid, NULL, thread_handler, connfdp);

12.4 多线程共享变量

多个线程共享全局变量和静态变量，但栈变量是私有的。

12.5 用信号量同步线程

信号量（Semaphore） 是 Edsger Dijkstra 提出的经典同步原语：

P(sem)：等待（如果 sem>0，sem--，否则阻塞）
V(sem)：发布（sem++，唤醒等待者）

// CSAPP 风格的生产者-消费者（有界缓冲区）
#include <semaphore.h>
typedef struct {
    int *buf; int n; int front, rear;
    sem_t mutex, slots, items;
} sbuf_t;

void sbuf_insert(sbuf_t *sp, int item) {
    sem_wait(&sp->slots);   // 等待空槽
    sem_wait(&sp->mutex);   // 锁定缓冲区
    sp->buf[(++sp->rear) % sp->n] = item;
    sem_post(&sp->mutex);
    sem_post(&sp->items);   // 通知有新物品
}

int sbuf_remove(sbuf_t *sp) {
    sem_wait(&sp->items);   // 等待有物品
    sem_wait(&sp->mutex);
    int item = sp->buf[(++sp->front) % sp->n];
    sem_post(&sp->mutex);
    sem_post(&sp->slots);   // 通知多了一个空槽
    return item;
}

12.6 读者-写者问题

// 读者优先策略
int readcnt = 0;            // 读者数量
sem_t mutex, w;             // mutex保护readcnt, w保护写者

void reader(void) {
    sem_wait(&mutex);
    readcnt++;
    if (readcnt == 1)
        sem_wait(&w);       // 第一个读者锁住写者
    sem_post(&mutex);

    /* 临界区: 读取操作 */

    sem_wait(&mutex);
    readcnt--;
    if (readcnt == 0)
        sem_post(&w);      // 最后一个读者释放写者锁
    sem_post(&mutex);
}

void writer(void) {
    sem_wait(&w);          // 写者互斥

    /* 临界区: 写入操作 */

    sem_post(&w);
}

12.8 CSAPP 并发 vs Go 并发 — 两种哲学

CSAPP 教授的并发（C + pthreads）和 Go 的并发（goroutine + channel）代表了两种根本不同的思维方式：

mermaid

flowchart LR
    subgraph CSAPP["CSAPP 模型: 共享内存 + 信号量"]
        C1["pthread_create()"]
        C2["sem_wait / sem_post"]
        C3["mutex_lock / mutex_unlock"]
        C4["共享全局变量"]
    end

    subgraph Go["Go 模型: CSP + channel"]
        G1["go func()"]
        G2["ch <- v / v := <-ch"]
        G3["sync.Mutex (备选)"]
        G4["channel 传递数据所有权"]
    end

维度	CSAPP (C + pthreads)	Go
并发单元	OS 线程 (pthread_create)	goroutine (go func())
同步原语	信号量、互斥锁、条件变量	channel（首选）、Mutex（备选）
通信方式	共享内存 + 锁保护	"通过通信来共享内存"
内存模型	需手动考虑内存序	Happens-Before 规则自动保证
死锁预防	全手动（锁顺序、trylock）	channel 部分消除 + `go race` 检测
调试工具	Valgrind (Helgrind/DRD)	`go run -race`（内置数据竞争检测）
学习曲线	陡峭（信号量容易用错）	平缓（channel 语义更直观）

// CSAPP 风格：生产者-消费者 (semaphore)
sem_wait(&empty);   // P(empty)
sem_wait(&mutex);   // P(mutex)
buffer[in] = item;   // 临界区
in = (in + 1) % N;
sem_post(&mutex);   // V(mutex)
sem_post(&full);    // V(full)
// 问题: 如果 P(empty) 和 P(mutex) 顺序写反 → 死锁！
// 如果忘记 sem_post → 永久阻塞！

// Go 风格：生产者-消费者 (channel)
ch := make(chan int, 10)
go func() { ch <- item }()       // 生产者
item := <-ch                      // 消费者
// 不需要 mutex、不需要信号量、不需要计数
// channel 内置了同步语义 + 阻塞机制

结论：CSAPP 教你的是"并发基础设施怎么工作"——信号量的 P/V 操作、互斥锁的 acquire/release、条件变量的 wait/signal。这些知识让你理解 Go channel 底层也是类似的机制（sudog 队列 + mutex）。但工程中应该用高层抽象——Go channel 把这些底层机制封装成了安全、易用的接口。

参考实验

CMU 15-213 配套 9 个 Lab：

Lab	名称	核心知识点
Data Lab	位操作实现	补码、浮点 IEEE 754、位运算
Bomb Lab	反汇编拆弹	x86-64 汇编、GDB 调试
Attack Lab	代码注入与 ROP	栈帧、缓冲区溢出、ROP 攻击链
Architecture Lab	Y86-64 处理器模拟	流水线设计、HCL 逻辑
Cache Lab	Cache 模拟器	缓存结构、矩阵分块、局部性优化
Shell Lab	简易 Shell	进程控制、信号、job control
Malloc Lab	动态内存分配器	隐式/显式空闲链表、分离适配、合并
Proxy Lab	Web 代理	网络编程、并发、Cache
Performance Lab	性能优化	CPE 分析、循环展开、SIMD

📌 本笔记以「知识点讲解 + 代码对照」方式梳理 CSAPP 全书，每个主题先讲原理概念，再用代码验证。深入主题请参见专题文档：CPU 微架构、进程线程协程、虚拟内存、内存布局、中断与异常、文件系统。

CSAPP 全书笔记 ​

全书结构 ​

第一部分：程序结构和执行 ​

第1章：计算机系统漫游 ​

1.1 信息就是位 + 上下文 ​

1.2 程序被其他程序翻译成不同的格式 ​

1.3 了解编译系统如何工作是大有益处的 ​

1.4 处理器读并解释存储在内存中的指令 ​

1.5 高速缓存至关重要 ​

1.6 存储设备形成层次结构 ​

1.7 操作系统管理硬件 ​

1.8 系统之间利用网络通信 ​

1.9 重要主题 ​

第2章：信息的表示和处理 ​

2.1 信息存储 ​

2.2 整数表示 ​

2.3 整数运算 ​

2.4 浮点数 ​

第3章：程序的机器级表示 ​

3.1 历史观点 ​

3.2 程序编码 ​

3.3 数据格式 ​

3.4 访问信息 ​

3.5 算术和逻辑操作 ​

3.6 控制 ​

3.7 过程 ​

3.8 数组分配与访问 ​

3.9 异质的数据结构 ​

3.10 缓冲区溢出与安全 ​

3.11 浮点代码 ​

第4章：处理器体系结构 ​

4.1 Y86-64 指令集体系结构 ​

4.2 逻辑设计和硬件控制语言 HCL ​

4.3 顺序实现（SEQ） ​

4.4 流水线（PIPE）通用原理 ​

4.5 流水线冒险 ​

第5章：优化程序性能 ​

5.1 优化编译器的能力和局限性 ​

5.2 表示程序性能 ​

5.3 消除循环的低效率 ​

5.4 减少过程调用 / 消除不必要的内存引用 ​

5.5 理解现代处理器 ​

5.6 循环展开与多累积变量 ​

5.7 存储器性能优化 ​

5.8 性能分析工具 ​

第6章：存储器层次结构 ​

6.1 存储技术 ​

6.2 局部性 ​

6.3 存储器层次结构 ​

6.4 高速缓存存储器 ​

6.5 写与缓存 ​

6.6 真实 Cache 解剖 ​

6.7 缓存友好的代码 ​

6.8 常见的与内存相关的错误 ​

第二部分：在系统上运行程序 ​

第7章：链接 ​

7.1 编译器驱动程序 ​

7.2 静态链接 ​

7.3 目标文件 ​

7.4 可重定位目标文件（ELF 格式） ​

7.5 符号和符号表 ​

7.6 符号解析 ​

7.7 重定位 ​

7.8~7.9 可执行目标文件与加载 ​

7.10 动态链接 — 实战对比 ​

7.11~7.14 ​

第8章：异常控制流 ​

8.1 异常 ​

8.2 异常分类 ​

8.3 系统调用 ​

8.4 进程 ​

8.5 进程控制 ​

8.6 信号 ​

8.7 非本地跳转 ​

8.8 操作进程的工具 ​

第9章：虚拟内存 ​

9.1 物理和虚拟寻址 ​

9.2 地址空间 ​

9.3 虚拟内存作为缓存的工具 ​

9.4 虚拟内存作为内存管理的工具 ​

CSAPP 全书笔记

全书结构

第一部分：程序结构和执行

第1章：计算机系统漫游

1.1 信息就是位 + 上下文

1.2 程序被其他程序翻译成不同的格式

1.3 了解编译系统如何工作是大有益处的

1.4 处理器读并解释存储在内存中的指令

1.5 高速缓存至关重要

1.6 存储设备形成层次结构

1.7 操作系统管理硬件

1.8 系统之间利用网络通信

1.9 重要主题

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

2.1 信息存储

2.2 整数表示

2.3 整数运算

2.4 浮点数

第3章：程序的机器级表示

3.1 历史观点

3.2 程序编码

3.3 数据格式

3.4 访问信息

3.5 算术和逻辑操作

3.6 控制

3.7 过程

3.8 数组分配与访问

3.9 异质的数据结构

3.10 缓冲区溢出与安全

3.11 浮点代码

第4章：处理器体系结构

4.1 Y86-64 指令集体系结构

4.2 逻辑设计和硬件控制语言 HCL

4.3 顺序实现（SEQ）

4.4 流水线（PIPE）通用原理

4.5 流水线冒险

第5章：优化程序性能

5.1 优化编译器的能力和局限性

5.2 表示程序性能

5.3 消除循环的低效率

5.4 减少过程调用 / 消除不必要的内存引用

5.5 理解现代处理器

5.6 循环展开与多累积变量

5.7 存储器性能优化

5.8 性能分析工具

第6章：存储器层次结构

6.1 存储技术

6.2 局部性

6.3 存储器层次结构

6.4 高速缓存存储器

6.5 写与缓存

6.6 真实 Cache 解剖

6.7 缓存友好的代码

6.8 常见的与内存相关的错误

第二部分：在系统上运行程序

第7章：链接

7.1 编译器驱动程序

7.2 静态链接

7.3 目标文件

7.4 可重定位目标文件（ELF 格式）

7.5 符号和符号表

7.6 符号解析

7.7 重定位

7.8~7.9 可执行目标文件与加载

7.10 动态链接 — 实战对比

7.11~7.14

第8章：异常控制流

8.1 异常

8.2 异常分类

8.3 系统调用

8.4 进程

8.5 进程控制

8.6 信号

8.7 非本地跳转

8.8 操作进程的工具

第9章：虚拟内存

9.1 物理和虚拟寻址

9.2 地址空间

9.3 虚拟内存作为缓存的工具

9.4 虚拟内存作为内存管理的工具