Computer Science from the Bottom Up

计算的基础

在开始阅读本章之前，请先思考一个问题：为什么计算机使用二进制，而不是我们人类习以为常的十进制？这个问题的答案不在数学里，而在物理学里。计算机的基本构成单元是晶体管，晶体管本质上是一个电子开关：它要么导通（高电平），要么截止（低电平）。让电路可靠地区分两种状态非常容易——只要电压高于某个阈值就是 1，低于另一个阈值就是 0，中间留出足够的噪声容限。但如果要让电路区分十种不同的电压水平来表示十进制的 0 到 9，那么每一档之间的间隔就会变得非常小，任何微小的电磁干扰、温度漂移或元件老化都可能让电路把 5 误读成 6。工程上的可靠性要求决定了：状态越少，抗噪声能力越强。于是二进制成为了几乎所有现代计算机的基础。 | 表示方案 | 编码方式 | 零的表示 | 加减法统一 | 范围 (8-bit) | 缺点 | |---------|---------|---------|-----------|-------------|------| | 原码 | 符号位+绝对值 | 两种 (+0, -0) | 需判断符号 | -127 ~ +127 | 零不唯一，加减复杂 | | 反码 | 按位取反 | 两种 (+0, -0) | 需末端进位 | -127 ~ +127 | 零不唯一 | | 补码 | 取反+1 | 唯一 (全0) | 天然统一 | -128 ~ +127 | 不对称范围 | | IEEE 754 单精度 | 1+8+23 位 | 唯一 | 不适用 | ±3.4x10^38 | 精度有限 | | IEEE 754 双精度 | 1+11+52 位 | 唯一 | 不适用 | ±1.8x10^308 | 64 位开销 | 二进制的数学基础是布尔代数。1847 年，英国数学家 George Boole 发表了《逻辑的数学分析》，提出了一套用代数方法处理逻辑命题的体系。在当时，这纯粹是一种数学游戏，没有人想到它会有什么实际用途。将近一百年后，1937 年，麻省理工学院的硕士生 Claude Shannon 发表了后来被誉为「数字电路圣经」的硕士论文《继电器与开关电路的符号分析》。Shannon 敏锐地发现，Boole 代数中的真与假，恰好对应开关电路中的闭合与断开：AND 对应串联电路，OR 对应并联电路，NOT 对应继电器常闭触点。这篇论文完成了从抽象数学到工程实现的关键一跃，奠定了整个数字时代的基础。可以说，你今天使用的每一台计算机，都是 Boole 和 Shannon 两人跨越时空合作的产物。 有了布尔运算，我们就可以搭建加法器、寄存器、存储器，进而搭建完整的计算机。但新的问题接踵而至：如何用有限的二进制位表示现实世界中无限的数字？负数怎么表示？小数怎么表示？非常大的数和非常小的数怎么办？这些问题催生了原码、反码、补码的演进，催生了 IEEE 754 浮点数标准，也催生了无数程序员的深夜调试。1996 年，阿丽亚娜 5 号火箭在首飞 37 秒后爆炸，直接原因是一行看似无害的类型转换代码把 64 位浮点数转成了 16 位有符号整数并发生了溢出——这次价值 3.7 亿美元的事故让全世界认识到，数字表示不是教科书上的抽象概念，而是实实在在的工程生命线。2000 年问题（Y2K）同样源于数字表示：早期程序员为了节省昂贵的存储空间，用两位数字表示年份，结果在世纪之交引发了全球范围的系统恐慌。 本章将带你从最底层的比特出发，理解计算机如何表示整数、负数、小数和实数。你会学到补码为什么能让加法和减法共用同一套电路，会亲眼看到 0.1 + 0.2 != 0.3 背后的二进制真相，会理解大端序和小端序这场持续了四十年的「圣战」，还会掌握一系列实用的位运算技巧。这些知识是后续所有章节——CPU 架构、操作系统、编译工具链——的共同地基。Ian Wienand 在书中强调「from the bottom up」的方法论：只有真正理解了最底层的表示方式，你才能理解上层软件的行为，才能在遇到诡异 bug 时知道问题出在哪里。让我们从第一个比特开始。

CPU 的工作原理

如果把计算机比作一座城市，那么 CPU 就是这座城市的市政厅——所有指令都在这里被解读和执行。但 CPU 的内部世界远比大多数人想象的复杂：一颗现代桌面处理器包含上百亿个晶体管，每秒钟执行数百亿条指令，而这些指令的执行方式早已不是「一条接一条」那么简单。本章将打开 CPU 这个黑盒子，看看里面到底发生了什么。 | 存储层级 | 典型容量 | 访问延迟 | 带宽 | 每字节成本 | 管理方式 | |---------|---------|---------|------|-----------|---------| | 寄存器 | 数百字节 | 0 周期 | - | 最高 | 编译器分配 | | L1 缓存 | 32-64 KB | 3-4 周期 | ~2 TB/s | 高 | 硬件自动 | | L2 缓存 | 256 KB-1 MB | 10-14 周期 | ~1 TB/s | 中 | 硬件自动 | | L3 缓存 | 4-32 MB | 40-70 周期 | ~500 GB/s | 低 | 硬件自动 | | 主存 DRAM | 8-256 GB | 200-300 周期 | ~50 GB/s | 很低 | OS 页表 | | SSD | 256 GB-4 TB | ~10 us | ~3 GB/s | 极低 | OS 文件系统 | | HDD | 1-20 TB | ~5 ms | ~200 MB/s | 最低 | OS 文件系统 | 一切从一个最基本的循环开始：取指（Fetch）、解码（Decode）、执行（Execute）、写回（Write Back）。这是 1945 年冯·诺依曼在 EDVAC 报告草案中描述的计算模型，八十年来所有计算机的骨架都没有变过：程序和数据一起存放在存储器中，CPU 按顺序取出指令并执行。早期的 CPU 确实就是这样工作的——取一条指令，执行完，再取下一条。但这种方式有一个巨大的浪费：取指单元、解码单元、执行单元在大部分时间里都在互相等待。1960 年代的 IBM Stretch 和 CDC 6600 率先引入了流水线的思想：把指令执行拆成多个阶段，让不同的指令同时处于不同的阶段，就像工厂的装配流水线一样。流水线不减少单条指令的延迟，但成倍提高了吞吐量——这是计算机体系结构史上第一个伟大的思想。 流水线一旦引入，新的问题随之而来。当一条加法指令的结果还没写回，下一条依赖它的指令就已经进入执行阶段，怎么办？这是数据冒险。当一条分支指令还没算出跳转方向，后面的指令该不该继续取？这是控制冒险。当两条指令同时需要使用同一个硬件单元？这是结构冒险。为了解决控制冒险，工程师发明了分支预测器——现代处理器的两级自适应预测器准确率高达 95% 以上，预测错误的代价是清空流水线的十几个周期。为了解决数据冒险并进一步挖掘并行性，1967 年 Robert Tomasulo 在 IBM System/360 Model 91 的浮点单元中提出了划时代的乱序执行算法：指令不必按程序顺序执行，只要操作数就绪就可以开工，通过保留站和寄存器重命名消除假依赖，再用重排序缓冲区保证对外呈现顺序执行的结果。乱序执行加上超标量设计（每个周期发射多条指令），让现代 CPU 的指令级并行度达到每周期 4-6 条指令。 但 CPU 再快，也快不过内存的鸿沟。这就是著名的「内存墙」问题：过去四十年 CPU 主频增长了上千倍，而内存访问延迟只改善了几倍。今天一次 L1 缓存命中约 1 纳秒，而访问主存需要约 100 纳秒——如果按人类感知比例缩放，L1 命中相当于拿起桌上的一本书，主存访问则相当于睡了一整夜。为了填平这道鸿沟，计算机体系结构构建了精密的内存层次：寄存器、L1、L2、L3 缓存、主存、SSD、磁盘，每一层都是上一层的缓存，利用程序访问的时间局部性和空间局部性，让 CPU 在绝大多数时候不必直面缓慢的主存。理解缓存的组织方式（直接映射、组相联、全相联）、缓存行、写策略，是写出高性能代码的必修课——矩阵乘法按行遍历和按列遍历的性能可以相差十倍，原因全在缓存。 最后，2005 年前后，单核 CPU 撞上了功耗墙：频率提升带来的功耗按超线性增长，散热无法承受，「免费午餐」结束了。处理器厂商转向多核，把频率停在 3-5GHz，用核心数量换取算力。这一转变深刻改变了软件行业——从此性能提升不再自动获得，程序员必须显式地思考并行。本章将带你走完这条从单条指令到多核处理器的完整认知路径，这正是「from the bottom up」方法论的核心：理解了 CPU 如何工作，你才能理解操作系统的调度、编译器的优化，以及你的代码为什么快或为什么慢。

硬件与应用的抽象层

假设没有操作系统，你的程序需要做什么？它需要自己初始化显卡驱动、自己管理内存分配、自己监听键盘中断、自己把数据写到磁盘的特定扇区。更糟糕的是，如果同时运行两个程序，它们会互相覆盖对方的内存，一个程序的崩溃会拖垮整台机器。操作系统（Operating System, OS）就是为了终结这种混乱而诞生的：它站在硬件和应用程序之间，向上提供简洁统一的抽象，向下管理复杂多样的硬件资源。理解操作系统，是「from the bottom up」旅程中承上启下的关键一站——它把第 1、2 章的硬件知识（内存、CPU、中断）转化为程序员可以依赖的服务。 | 抽象层 | 核心概念 | 提供的服务 | 关键数据结构 | 切换开销 | |-------|---------|-----------|------------|---------| | 硬件层 | 电信号、总线、寄存器 | 原始计算能力 | 无 | - | | 指令集 (ISA) | 指令、寻址、寄存器 | 可编程的机器 | 程序计数器 | - | | 内核态 | 页表、中断描述符、TCB | 资源管理 | 进程控制块 | - | | 系统调用 | read/write/mmap/fork | 文件、进程、内存 | 文件描述符表 | ~1000 周期 | | 用户态进程 | 虚拟地址空间、线程 | 独立执行环境 | 堆、栈、代码段 | 上下文切换 ~us | | 应用程序 | 函数、对象、模块 | 业务逻辑 | 应用数据结构 | - | 操作系统的历史就是一部「资源利用率与用户体验不断进化」的历史。1940 年代的计算机没有操作系统，程序员预约机时，手工装卸纸带，机器大部分时间在闲置。1950 年代的批处理系统（Batch System）把作业成批输入，由监督程序自动衔接，减少了人工干预。1960 年代的多道程序（Multiprogramming）系统让多个作业同时驻留内存，一个作业等待 I/O 时 CPU 立即切换到另一个作业，把昂贵的 CPU 利用率从 20% 提升到 70% 以上。同一时期的分时系统（Time-Sharing）——MIT 的 CTSS、贝尔实验室与通用电气合作的 Multics——让多个用户通过终端同时交互使用计算机，每个用户感觉自己独占机器。Multics 项目虽然商业上失败了，但它的一位年轻工程师 Ken Thompson 在 1969 年把其中的思想大幅简化，写出了 Unix 的第一个版本；Dennis Ritchie 随后发明了 C 语言，1973 年 Unix 内核用 C 重写，操作系统第一次摆脱了对特定硬件的依赖，可以移植到任何有 C 编译器的机器上。这直接催生了 Linux（1991 年 Linus Torvalds）、BSD、macOS 等整个 Unix 家族。实时操作系统（RTOS）则走上了另一条路：不追求平均吞吐量，而保证最坏情况下的响应时间，用于航空航天、工业控制和医疗设备。 操作系统的三大核心抽象是：进程（CPU 的抽象）、虚拟内存（物理内存的抽象）和文件（I/O 设备的抽象）。进程让每个程序都以为自己独占 CPU——实际上操作系统以毫秒级的时间片在几十上百个进程之间轮转，每次切换都要保存和恢复完整的 CPU 状态。虚拟内存让每个进程都以为自己独占一条从 0 开始的连续地址空间——实际上 MMU 硬件和操作系统的页表把虚拟地址动态翻译到物理地址，不同进程的同一个虚拟地址指向完全不同的物理内存，从而实现隔离；而共享又通过让多个进程映射同一物理页来实现，动态链接库正是靠这个机制让一份 libc 代码服务所有进程。文件抽象则把磁盘、终端、网络套接字甚至进程信息（Linux 的 /proc）统一成「字节流 + read/write/open/close」的接口，「一切皆文件」是 Unix 最深刻的设计哲学。 这些抽象不是免费的。每次系统调用都要经历用户态到内核态的特权级切换，每次进程切换都要付出寄存器保存、TLB 刷新和缓存污染的代价，每次缺页中断都要陷入内核走一遍页表甚至访问磁盘。理解这些开销的来源和数量级，你才能理解为什么高性能服务器要用 epoll 而不是每连接一个 select，为什么要用 mmap 而不是反复 read 大文件，为什么数据库要自己管理缓冲池。本章将深入进程、虚拟内存、地址翻译、系统调用和信号五大主题，把操作系统从黑盒变成你手中的透明机器。

从源代码到可执行文件

当你敲下 gcc hello.c -o hello 然后回车，一秒钟后一个可执行文件就躺在了磁盘上。这一秒钟里发生了什么？答案是：四个独立的程序接力完成了一场精密的翻译——预处理器（cpp）展开宏和头文件，编译器（cc1）把 C 代码翻译成汇编语言，汇编器（as）把汇编翻译成机器码并打包成目标文件，链接器（ld）把多个目标文件和库拼装成最终的可执行文件。这条流水线就是「工具链」（Toolchain）。大多数程序员一辈子只把它当作一个黑盒命令，但 Ian Wienand 在书中坚持：理解工具链，是理解「程序到底是什么」的必经之路。因为可执行文件不是源代码的「编译结果」这么简单——它是一个有精确格式的二进制数据结构，操作系统按这个格式加载它，动态链接器按这个格式解析它，调试器按这个格式解读它。 | 阶段 | 工具 | 输入 | 输出 | 核心任务 | 关键产物 | |------|------|------|------|---------|---------| | 预处理 | cpp (gcc -E) | .c 源文件 | 展开后的 .c | 宏展开、文件包含、条件编译 | 纯文本，无 # 指令 | | 编译 | cc1 (gcc -S) | 预处理后 .c | .s 汇编文件 | 语法分析、优化、代码生成 | 汇编指令序列 | | 汇编 | as (gcc -c) | .s 汇编文件 | .o 目标文件 | 指令编码、符号表生成 | ELF 目标文件 | | 链接 | ld (gcc -o) | .o + .a/.so | 可执行文件 | 符号解析、重定位、合并 | ELF 可执行文件 | 为什么需要这么多阶段？根源在于关注点分离。C 语言的宏和头文件是文本层面的机制，预处理器用纯文本替换实现它们，根本不懂 C 语法——这解释了为什么宏的坑如此之多（忘记加括号、多次求值），因为预处理器眼里只有字符。编译器前端把 C 翻译成中间表示（IR），中端在 IR 上做与机器无关的优化（常量折叠、死代码消除、循环优化），后端把 IR 翻译成特定架构的汇编——这个三段式设计让 GCC 能用一套优化代码支持几十种 CPU。汇编器做几乎一对一的翻译，把助记符变成机器码，但此时函数调用的目标地址还是未知的——main.c 里调用 printf，printf 在另一个文件甚至另一个库里，地址要等链接时才能确定，所以汇编器在目标文件里留下「重定位条目」（relocation entry），标记「这里将来要填一个地址」。链接器负责最后的拼图：收集所有目标文件，把同名的节合并（所有 .text 拼成一个大代码段），解析符号引用（谁定义了 printf？在 libc 里），再根据重定位条目把真实地址填进去。 这一切的载体是 ELF 格式（Executable and Linkable Format）——Unix 世界的通用二进制容器。ELF 文件有两套「视图」：链接视图由节头表（Section Header Table）描述，把文件切成 .text、.data、.bss、.rodata、.symtab 等节，供链接器使用；执行视图由程序头表（Program Header Table）描述，把文件切成若干个段（Segment），告诉操作系统内核如何把文件映射进内存。同一个字节序列，两种解释方式，这是 ELF 设计最精妙也最让初学者困惑的地方。理解了 ELF，你就能回答一系列实际问题：为什么全局变量初始化为 0 不占文件体积（.bss 只记录大小不记录内容）？为什么字符串常量改不了（.rodata 映射为只读页）？为什么 strip 之后程序变小但还能运行（符号表是调试信息，执行不需要）？为什么 readelf 和 objdump 看到的结构不一样（一个按节一个按指令）？ 本章还将对比编译型、解释型和混合型语言的实现策略，理解静态库与共享库的权衡——这直接引出第 5 章动态链接的主题。学完本章，建议你养成一个新习惯：每写一个 C 程序，都用 gcc -E/-S/-c/-v 把四个阶段的中间产物都看一遍，用 readelf 解剖生成的 ELF。工具链不再是黑盒，而是你手中透明的、可检查的、可操纵的工具——这正是「bottom up」思维方式的体现。

共享库的加载

在 Linux 上运行 ldd /bin/ls，你会看到它依赖七八个共享库：libc、libselinux、libacl……这些库的代码并不在 ls 的可执行文件里，而是在程序启动时（甚至第一次调用某个函数时）才被找到、加载、连接。完成这一切的幕后英雄是动态链接器（Dynamic Linker，Linux 上是 /lib64/ld-linux-x86-64.so.2）。本章是全书工具链部分的收官：第 4 章讲了链接器如何在构建时把目标文件拼成可执行文件，本章讲剩下的另一半故事——那些被推迟到运行时的链接工作是如何完成的。 | 链接方式 | 链接时机 | 可执行文件大小 | 内存占用 | 更新便利性 | 启动速度 | |---------|---------|-------------|---------|-----------|---------| | 静态链接 | 编译时 | 大（包含所有库代码） | 高（每进程独立副本） | 需重新编译 | 快（无链接开销） | | 动态链接（eager） | 启动时 | 小（仅引用） | 低（多进程共享） | 替换 .so 即可 | 慢（启动时解析全部） | | 动态链接（延迟绑定） | 首次调用时 | 小（仅引用） | 低（多进程共享） | 替换 .so 即可 | 快（按需解析） | | 静态链接 + PIE | 编译时 | 大 | 高 | 需重新编译 | 快，支持 ASLR | 为什么要发明动态链接？回到 1980 年代的 Unix：当时磁盘以 MB 计、内存以 KB 计，每个程序都静态链接一份 libc，几十个程序就是几十份相同的代码副本，磁盘和内存被大量浪费。共享库的思想是：把公共代码抽出来做成 .so 文件，磁盘上只存一份；运行时所有进程的 libc 代码段映射到同一批物理页（回忆第 3 章的虚拟内存共享机制），物理内存中也只有一份；库升级时只需替换 .so 文件，所有程序下次启动自动用上新版本——安全补丁可以在几分钟内推送到全系统，而不必重编译每一个程序。这个机制如此成功，以至于今天几乎没有 Linux 程序是完全静态链接的。 但把链接推迟到运行时带来了三个技术难题。第一，加载地址不确定：共享库会被不同进程加载到不同的虚拟地址（ASLR 更是每次运行都随机化），库代码中不能含有写死的绝对地址——解决方案是位置无关代码（PIC）：代码段通过 PC 相对寻址访问，数据段通过一张运行时填写的地址表（GOT）间接访问，于是代码段在所有进程中完全相同可以共享物理页，只有每个进程私有的 GOT/.data 需要独立副本。第二，符号解析开销：程序可能引用库里成千上万个函数，启动时全部解析太慢——解决方案是延迟绑定（Lazy Binding）：通过 PLT 桩代码，函数第一次被调用时才解析地址，之后直接跳转。第三，版本兼容：库升级后函数行为或结构体布局变了，老程序怎么办——解决方案是符号版本控制（Symbol Versioning）：glibc 的每个符号都带版本标签（如 memcpy@GLIBC_2.14），同一函数可以共存多个版本的实现，程序链接时锁定它构建时的版本，永不意外改变行为。 动态链接的强大也是一把双刃剑。LD_PRELOAD 环境变量可以让任意共享库抢在所有库之前加载，其中的同名符号会拦截（interpose）系统库的函数——这是调试和性能分析的神器（可以拦截 malloc 统计内存、拦截 connect 记录网络调用），也是提权攻击的通道（setuid 程序若不防范，恶意库可以劫持它的任何 libc 调用）。理解 GOT/PLT 的机制，你还能看懂一整类安全攻防：GOT 覆写攻击、返回导向编程（ROP）为什么盯着可写又含指针的 GOT 表、RELRO（Relocation Read-Only）加固为什么要把 GOT 变成只读。 本章将沿着「程序启动」的时间线完整走一遍动态链接的全过程：内核加载 ELF 并把控制权交给动态链接器，链接器递归加载所有依赖库，重定位数据符号，设置 PLT 桩，最后跳转到程序入口。每一步都配有可以用 readelf、objdump、LD_DEBUG 亲手验证的实验。学完本章，你对「一个程序如何跑起来」的理解将贯穿从比特（第 1 章）、CPU（第 2 章）、操作系统（第 3 章）、构建工具（第 4 章）到运行时链接的完整链条——这正是 Computer Science from the Bottom Up 这本书的终极目标。