深入理解Linux内核-章节笔记

我心中的《深入理解Linux内核》

《深入理解Linux内核》毋庸置疑是一本阐述Linux内核各个模块的经典之作，它不是一本教授如何使用系统调用，进而实现用户进程功能的最佳实践，而是以数据结构为切入点，通过解释各个子系统的实现原理来帮助读者提升内功。

这么好的一本书，也还是有一些缺憾：

• 占位符太多
  虽然作者已经根据知识的推进过程合理地对各个章节进行了布局，但是无奈知识点太多，且呈网状分布，文章中还是存在不少类似”某某内容留在某某章节详细讨论”的占位符，如果阅读过程中不来回参考，容易顾此失彼。

• 缺少子系统间的架构图
  本书在每个章节间都有一些配图说明复杂的数据结构和内容，但是子系统之间却缺少一些架构图来帮助读者抓住它们之间的一些要害，容易让读者陷入细节，一叶障目。

• 缺少每章总结
  本书每章都配有引导词，简单介绍本章内容的布局。但是末尾却缺少相应的总结，无法做到提纲挈领。这也是我写这篇总结的主要原因。

本篇文章是我间隔五年第二遍阅读本书之后所作的个人梳理，会不断更新和勘误（解答自己遗留下来的问题），也欢迎大家留言一起讨论指正。

补充：每章总结

第一章：绪论

绪论主要是对Linux特性的简单阐述，我们暂且忽略。

第二章：内存寻址

感受

管好内存数据的第一步是找到它。

关键点

• 地址关系
  逻辑地址|分段单元 -> 线性地址|分页单元 -> 物理地址。

  • 逻辑地址
    由段（segment） + 段内偏移（offset）构成，CPU使用。
  • 线性地址
    程序可寻址的空间。
  • 物理地址
    物理内存的地址空间。

• 权限控制

  • 分段单元（CS段指明CPU当前特权级，段描述符DPL字段指定要求的CPU最小优先级）
  • 分页单元（页表项上指明页框权限）

• 物理内存布局
  1MB前的物理地址保留，内核安装在1MB之后，3MB之前。

• 进程/内核页表

  • 每个进程有自己独立的一套页表（线性空间）
  • 进程在用户态只能寻址前3G，内核态额外寻址第4G
  • 内核拥有自己的一套全局页表（swapper_pg_dir），初始化时前3G置空，并把第4G的前896M映射到物理内存0开始的前896M，留下128M空间实现非连续内存（高端）及固定映射

核心数据结构

• 全局描述符表（GDT） - 主存
  代码段/数据段/任务段/局部段。
• 分级页表（页目录+页表）- 主存
  页框的物理地址（最高20bit） + 权限（Present|Read/Write|User/Supervisor）。

算法

• 触发缺页
  页表项中Present=0即触发缺页，细分为两种情况：

1. present=0, page_size=1（pte_present()=1）
   页在主存中，无写权限，触发写时复制。

2. present=0, page_size=0（pte_present()=0）
   页不在主存中，触发调页。

优化

• 加速：

1. 专用寄存器缓存段描述符
2. 硬件高速缓存加速内存读写（WriteThrough/WriteBack策略）
3. 转换后援缓冲器（TLB）缓存线性地址到物理地址的映射

• 推迟：

1. TLB懒惰
   内核线程（区分内核进程与普通进程的内核态）不访问用户态地址，因此不响应用户态地址TLB失效的请求。

Linux特色

1. 归一化用户代码段/数据段，内核代码段/数据段，使得offset的值与线性地址的值一致
2. 使用4级分页（x86_64:9+9+9+9+12）兼容各种情况

第三章：进程

感受

进程是计算所需所有资源的载体。

关键点

• 进程描述符关联了所有属于该进程的资源：包括寄存器，内存，文件系统，打开的文件，信号，资源限制等等。

• 进程有自己的状态机（详见图1）。
  

• 进程间关系：

1. 父子
   每一个进程都有一个父亲，如果父亲先于自己死亡，自己将被托管给init进程。
   每一个进程可以有多个子进程，但没有系统调用可以直接获取自己所有子进程的列表。
   每一个子进程结束后，在父进程调用wait系统调用收集子进程结束结果前，处于僵尸（zombie）状态。

2. 组
   通过PID查找属于同一组（进程组/线程组/会话组）的进程。

• 进程组织
  通过运行时队列（按优先级细分链表）把可运行进程串成链表。
  正在睡眠的进程按照正在等待的各种事件组织成等待队列，唤醒进程意味着将进程状态设置为可运行。

• 进程切换发生在内核态，特指用目标进程替换被替换进程的过程（硬件上下文切换），大体上分两步：

1. 切换进程全局页目录（cr3寄存器内容被保存在目标进程描述符的thread字段中）
2. 切换内核态堆栈和硬件上下文

• 进程创建/终结

1. 进程创建
   父进程负责分配子进程的用户态堆栈，内核负责创建子进程的内核态堆栈。
   子进程创建完成后在不同的堆栈上返回2次，父进程用户态堆栈返回子进程PID，子进程用户态堆栈返回0。

2. 进程终结
   设置进程flags中的PF_DEAD，供调度程序使用。

• 内核进程
  内核进程只运行在内核态，只访问内核空间。

1. 进程0 - swapper/idle(每CPU)
   系统启动时通过静态分配的数据结构加载，作为兜底进程执行空转。
   是所有进程描述符构成的链表的表头。
   是所有内存描述符构成的链表的表头。

2. 进程1 - init
   由进程0产生的子进程，并通过exec执行自己的逻辑（init可执行程序）。

核心数据结构

• 进程描述符task_struct
• PID哈希列表pid_hashes
• 运行队列（每CPU）
• 等待队列

在以上这些地方都能找到进程描述符。

算法

• 通用循环链表/哈希链表
  将链表的prev/next单独作为一种通用结构内嵌入被链接的对象，使得对象可以同时处于不同的链表中。

优化

• 技巧

1. 将esp(内核栈)和thread_info作为一个整体（一般是2个页）分配内存，则可以通过esp快速得到当前的进程
2. 切换进程的过程中(A->B,B->C,C->A)通过寄存器eax作为中转保存在A恢复运行后获取C（实际情况会把C存在原来A的地址中）
3. 切换过程中将内核栈esp保存在TSS段中(每CPU的所有进程共享)，供进程进行系统调用时获取内核栈地址

• 加速

1. 空间换时间：将运行队列按优先级拆分

• 推迟

1. FPU/MMX等寄存器在进程切换时按需保存，且推迟到下一个进程使用这些寄存器时再恢复。

Linux特色

1. 使用轻量级进程实现多线程程序
   轻量级进程间共享大部分数据（代码+堆），拥有自己的执行流（堆栈）。
2. fork()/vfork()/clone()在系统调用中都用sys_clone实现。

遗留问题

1. 会话组的作用
2. 进程组/线程组的区别

第四章：中断和异常

感受

中断是系统的神经中枢（响应硬件）。

关键点

• 定义
  中断和异常用来迫使CPU响应紧急事件（改变代码执行流），通过中断向量（vector）编码（异常<32，中断IRQ线+32）。
  中断对应于外部设备的请求，通过中断控制器转化为对应的中断向量。
  异常主要对应于代码产生的异常条件，主要发生在用户态（缺页除外，也可以发生在内核态）。

• 性质

1. 可嵌套执行
   为了提高硬件吞吐量，中断的优先级最高，并可以在中断处理逻辑/异常处理逻辑中嵌套。
   异常不能抢占正在执行的中断处理逻辑。
2. 可屏蔽
   应答某个IRQ会暂时屏蔽该条IRQ线，但期间该IRQ产生的中断不会丢失。
   可屏蔽中断可以通过设置CPU的flags寄存器进行全局屏蔽。大部分中断门处理程序都会屏蔽中断（但是执行具体irqaction过程中根据参数可能会打开）。
3. 并发性
   中断由多CPU并发处理。
4. 进程相关性
   异常处理和当前进程相关，中断处理一般和当前进程无关。

• 处理逻辑触发点
  CPU在执行完一条指令后，都会检查是否存在触发的异常或中断，如果有，根据中断描述符表找到对应的内核逻辑处理（可能需要切换到内核态堆栈并在内核栈中保存硬件上下文）。

• 处理结果
  大部分异常处理程序会给引发异常的进程发送信号。
  大部分中断依次执行IRQ描述符内存储的相应动作（irqaction）。

• 退出时处理
  如果退出后返回内核态，考虑内核抢占。
  如果退出后返回用户态，考虑重新调度（进程设置了NEED_RESCHED）及处理挂起信号。

• 软中断
  激活：软中断把自己挂起在irq_stat（每CPU）变量中，并唤醒ksoftirqd。
  执行：每个硬中断执行结束时/刚启用软中断时/ksoftirqd被唤醒时。
  并发：软中断可以在不同CPU上并发，在同一个CPU只能串行。

• tasklet（作为2种软中断存在，硬件驱动首选）
  激活：把tasklet描述符加入本地CPU链表，并激活对应软中断。
  执行：作为软中断的一部分执行。
  并发：同一个tasklet只能在一个CPU上执行。

• 工作队列（支持阻塞）
  激活：将work描述符加入workqueue对应本地CPU的链表中。
  执行：由keventd或者其它专用工作内核线程执行（内核线程数量由CPU数量决定）

核心数据结构

• 中断描述符表IDT
• IRQ描述符irq_desc_t
• 中断动作irqaction
• 软中断向量（下标为优先级）softirq_vec
• 挂起的软中断irq_stat（每CPU）
• 内核抢占（硬中断+软中断计数）thread_info->preempt_count
• Tasklet向量tasklet_vec[cpu编号]
• Tasklet描述符tasklet_struct
• Workqueue向量workqueue_struct[cpu标号]
• Work描述符work_struct

算法

暂无。

优化

• 推迟

1. 本地CPU发现一个IRQ中断如果已经由另一个CPU处理，则推迟给相同CPU处理。

• 平衡

1. 一次软中断处理只跑10次循环，如果还有软中断发生，唤醒ksoftirqd处理（网卡可以在软中断处理中不断激活自己）。

Linux特色

1. Default TSS段
   针对Double fault这种严重错误，使用GDT中最后一个TSS段装载eip/esp，使得CPU在自己的私有栈上处理。
2. 多内核栈
   如果thread_union结构为4K，则所有异常处理使用原先的内核栈，另外额外开辟两个唯一的内核栈（硬中断内核栈和软中断内核栈）。

遗留问题

1. 有没有系统调用可以让用户态进程使用工作队列？
   有，可以使用POSIX消息队列。

第五章：内核同步

感受

快来给程序并发控制的祖师爷磕个头～
锁可以在并发中用来保护一个数据结构，也可以用来保护一段逻辑。

关键点

• 内核抢占
  正在执行内核态的代码（异常处理）能够被切换成其它进程执行。
  抢占一般发生在硬中断处理返回/软中断处理结束启用可延迟函数/异常处理程序主动调用preempt_enable()时，且都会检查TIF_NEED_RESCHED标志。

• 内核进程临界区的同步原则

1. 硬中断处理代码不需要是可重入的（一次处理会屏蔽同种硬中断）
2. 只由软中断和tasklet访问的每CPU变量不需要同步（软中断和tasklet在同一个CPU上串行执行）
3. 仅被一种tasklet访问的数据结构不需要同步（同种tasklet一次在一个CPU上串行执行）

• 并发场景

1. 多CPU
   多CPU尝试访问相同的数据结构。
2. 内核抢占
   内核抢占导致同一个数据结构可能在同一个CPU上被不同的进程交替访问（某种意义上可以看成另一种虚拟CPU）。

• 处理并发的基本思想

1. 操作不同的对象
2. 对同一个对象的操作进行同步（原子/上锁等）

• 同步原语

1. 每CPU变量（CPU读写属于自己的数据）
2. 原子操作（汇编指令级别通过锁地址总线实现，是实现锁的基础）
3. 优化和内存屏障（保证汇编指令执行顺序，也是实现锁的基础）
4. 自旋锁（在忙等时支持被内核抢占）
5. 读写自旋锁/顺序自旋锁（增加自旋锁的并发能力）
6. RCU(类似数据库的MVCC机制，需要清理不再使用的数据结构副本)
7. 信号量（忙等时被挂起，支持可睡眠函数）
8. 读写信号量
9. 补充（对于同一个信号量禁止并发）

核心数据结构

• 自旋锁spinlock_t
• 信号量semaphore

算法

• 悲观并发/乐观并发
  普通的自旋锁/信号量是一种悲观并发，读写信号量使用了乐观并发。

优化

• 技巧

1. 拥有大内核锁的进程被内核抢占时，将lock_depth暂时设置为-1，这样schedule()就不会释放大内核锁

Linux特色

1. 大内核锁由信号量实现，由其保护的临界区允许内核抢占，提升并发效果

遗留问题

1. 什么时候设置TIF_NEED_RESCHED？
2. 挂起和内核抢占的区别？
3. 对于补充和信号量区别的理解需要加深
4. 补充高级语言中并发相关技巧和内核级别技巧的映射

第六章：定时测量

感受

时钟中断是系统的心脏。

关键点

• 时钟中断
  节拍一般为1ms，每个节拍产生一次时钟中断。

• 全局时钟中断与本地时钟中断
  全局时钟中断处理与全局有关的信息（更新时间）。
  本地时钟中断处理与本地CPU有关的信息（系统负载/激活软定时器和延时函数/进程时间片/平衡多CPU运行队列）。

• 软定时器和延迟函数
  内核使用软定时器执行定时逻辑，并适用于精确度高的实时程序。
  延迟函数解决驱动程序对于时间间隔特别短的要求（纳秒级）。

核心数据结构

• 变量jiffies
  保存开机以来经过的节拍数。jiffies_64由两个32bit的计数器合成，用顺序锁保护。

• 变量xtime
  保存当前日期和时间，精确度到纳秒。

• 动态定时器timer_list

算法

暂无。

优化

• 加速
  空间换时间：动态定时器按照expires标定的节拍数放在分组（8-6-6-6-6）的不同链表中，并定时把后一组的内容更新进前一组。

Linux特色

• 非屏蔽中断NMI监视器
  不能由CPU的cli指令屏蔽的中断，监视CPU是否冻结。

遗留问题

暂无。

第七章：进程调度

感受

因材施教是当家长的最高境界。

关键点

• 调度的本质
  在可运行队列中选择合适的目标进行切换，切换前被切换进程状态的修改不是必要条件。

• 设计系统调度策略的建模过程：

1. 定位核心指标：进程时间片
2. 找到影响核心指标的因子：静态时间片（静态优先级, 标志性的值5ms/100ms/800ms） + 平均睡眠时间（动态优先级）
3. 建模：动态调整

• 避免饥饿
  将运行队列分成活动和过期两组，用完时间片根据进程类型（启发式判断：交互式/批处理/实时）决定是否进入过期组，最终保证所有进程（低优先级）都有机会运行。

• 调度发生时间点

1. 主动

• 内核代码因为等待资源主动放弃（设置自身进程状态为睡眠）

2. 被动（设置TIF_NEED_RESCHED）

• 时间中断处理程序扣减进程时间片为0

• 唤醒进程后发现进程优先级大于当前

• 调度过程

1. 将非运行状态的被替换进程从运行队列中删除
2. 找到进程切换目标（O1复杂度）
3. 进行切换
4. 如果被切换进程已经死亡，回收进程描述符

核心数据结构

• 进程队列runqueue

算法

1. 计算动态优先级
   动态优先级 = max(100, min(静态优先级 - bonus + 5, 139))

优化

• 技巧

1. 通过互换活动/过期队列的指针完成快速切换
2. 拥有大内核锁的进程被调度时，schedule()负责调度前后释放后重新获取

Linux特色

1. 内核线程共享被替换线程的内存描述符，通过runqueue->prev_mm中转

遗留问题

暂无。

第八章：内存管理

感受

预分配和缓存是提高内存使用效率的关键。

关键点

• 层次化

1. 管理区分配器（使用分区页框分配器+每CPU页框高速缓存）负责从管理区获取/释放连续页框
2. 内存区通过slab分配器负责以对象为单位从页框分配/释放专用/通用对象

• 区分高端内存
  预留小部分线性空间（<128M）专用于高端内存的映射：

1. 永久映射（一个页表，最多4M）
2. 临时映射（每CPU13个页表项）
3. 分连续内存区

核心数据结构

• 节点描述符pg_data_t
• 管理区描述符zone
• 高速缓存描述符k_mem_cache_t
• slab描述符slab
• 非连续内存区描述符vm_struct

算法

• 伙伴算法
  分区页框分配器使用伙伴算法减少外部碎片（即使合并相连的可用页框）。

• slab着色
  给同属一个高速缓存的slab增加不同的offset以增加高速缓存效能。

优化

• 加速

1. 每个管理区有自己的保留页框池供内核路径的原子页框情求（保证必然成功）
2. 分区页框分配器使用每CPU页框高速缓存加速单页框分配和释放
3. CPU包含共享和本地空闲slab对象缓存加速对象分配

• 推迟

1. 分配非连续内存区只修改内核页表，推迟到缺页处理再同步进程内核空间的对应表项

Linux特色

1. 使用节点描述符兼容NUMA和UMA

遗留问题

1. 内存区分DMA的用处

第九章：进程地址空间

感受

用户态/内核态管理内存的共同问题是减少碎片。

关键点

• 减少碎片
  分配和释线性区时考虑及时合并和拆分（减少碎片）。

• 处理缺页错误

1. 用户态空间的页不存在 - 调页
2. 用户态空间的页存在但没写权限 - 写时复制
3. 内核态空间的页不存在 - 从主内核页表复制
4. 考虑用户态堆栈需要扩展的额外情况

• 进程创建时

1. 轻量级进程共享父进程内存描述符对象指针
2. 普通进程复制父进程页表，并为写时复制进行设置

• 堆
  用户态使用单独的线性区表示堆（管理动态内存）。

核心数据结构

• 内存描述符mm_struct
• 线性区vm_area_struct

算法

• 红黑树

1. 每节点为红或黑
2. 树的根为黑
3. 红色节点的孩子必为黑
4. 每个节点到叶子节点的黑色节点数量相等
   线性区使用红黑树加速查找和添加/删除操作，使用链表加速已知一个节点的情况下查找下一个节点。

优化

• 缓存
  内存描述符中缓存了上一次查找完成时候的线性地址，加速下次查找。

• 推迟

1. 写时复制机制推迟了给进程分配页框的时机

Linux特色

1. 内核线程共享上一个执行进程的内存描述符

遗留问题

暂无。

第十章：系统调用

感受

一夫当关，万夫莫开。

关键点

系统调用是用户态进程调用操作系统功能（和硬件交互）的唯一入口。统一的入口带来两个直接的好处：

• 安全性
  可以在入口处针对参数做统一的检查。
• 可移植性
  不同系统在各自提供的库函数中提供符合POSIX标准的API，使得C代码可以在不同系统间移植。

由于要通过寄存器在用户态堆栈和内核态堆栈间传递参数，特别将系统调用分成几个层次：

• 封装例程（wrapper routine）
  供应用程序调用的用户态库函数，负责将参数存入寄存器，调用系统调用处理程序及返回结果（errno）的转换。
  多个封装例程可以调用相同的系统调用，一个封装例程也可以组合多个系统调用实现复杂功能。
• 系统调用处理程序（call handler）
  运行在内核态的胶水代码，将寄存器中的参数保存到内核态堆栈（涉及cdecl调用约定），并调用系统调用服务例程，最后恢复寄存器值。
• 系统调用服务例程（system call service routine）
  实现具体工作的具体C函数。

核心数据结构

暂无。

算法

暂无。

优化

• 推迟

1. 对作为参数传递的地址进行检查
   系统调用只检查该地址是否属于用户态空间，其是否属于用户进程空间被推迟到分页单元（缺页处理）

Linux特色

1. 兼容sysenter指令和int编程异常两种调用方式
2. int编程异常是异常处理的实例，大量复用中断异常处理逻辑

遗留问题

1. 内核线程通过init实现系统调用是否合理（不存在用户态堆栈和内核态堆栈的切换）？

第十一章：信号

感受

信号是进程之间的传令兵，但点到即止。

关键点

• 信号和中断的比较

1. 信号和中断处理过程都会阻塞（屏蔽）同种信号再次触发（保证串行），但被屏蔽的中断不会丢失，而被阻塞的非实时的信号会丢失
2. 中断处理发生在内核态，信号处理发生在用户态
3. 两者都能继续嵌套中断

• 产生和传递

1. 产生负责修改目标进程的数据结构将其挂起（可以是共享或者私有挂起队列）
2. 传递发生在内核态切回用户态（时钟中断保证最低频率1ms），会处理所有挂起信号（忽略/默认/私有函数）

• 重新执行系统调用
  系统调用等待资源时会被调度并返回一个错误码，若接收到信号而被恢复，信号处理程序负责根据错误码决定是否自动重新执行系统调用。

核心数据结构

• 信号位图sigset_t
• 信号描述符signal_struct
• 信号处理描述符sighand_struct
• 信号动作k_sigaction
• 信号挂起队列sigqueue

算法

暂无。

优化

暂无。

Linux特色

1. 执行用户态信号处理函数的方法
   内核态负责在内核态堆栈和用户态堆栈间传递硬件上下文。

遗留问题

1. 能否通过不断给一个进程发送信号，迫使其卡在信号处理？
2. 用户态信号函数执行期间能否有办法修改内核态硬件上下文？

第十二章：虚拟文件系统

感受

面向对象设计在系统中最好的示范。

关键点

• 虚拟文件系统对象关系图(详见图2)
  

• 五种Unix标准文件类型

1. 普通文件（存放普通数据）
2. 目录文件（存放目录内存在文件和目录的数据）
3. 符号链接文件（存放目标文件的路径）
4. 设备文件
5. 管道文件

所有节点形成树形层次结构（加上符号链接变成有限图型），且节点可读可写的结构都可适用于虚拟文件系统。

• 挂载
  子文件系统可以挂载在父文件系统的目录（挂载点）上，并屏蔽父文件系统该目录下的内容。

• 文件锁
  提供文件区块上的共享/互斥锁。

核心数据结构

• 超级块对象super_block
• 索引节点对象inode
• 文件对象file
• 目录项对象dentry
• 命名空间namespace
• 文件系统类型file_system_type
• 文件系统共挂载vfsmount
• 文件锁file_lock

算法

• 路径遍历算法
  考虑路径是符号链接/被子文件系统覆盖/只需要获取父目录信息等情况

优化

• 加速

1. 目录项高速缓存/索引节点高速缓存加速磁盘内容读取（需要写回机制）

Linux特色

• 根目录文件系统挂载

1. 系统初始化时先挂载rootfs特殊文件系统，提供空目录
2. 在主设备上依次尝试创建根文件系统，成功后转移到根目录

遗留问题

1. 有哪些文件锁的经典使用案例？

第十三章：I/O体系结构和设备驱动程序

感受

设备驱动程序构成的层次结构是VFS的应用之一。

关键点

• I/O空间包含I/O端口（65535个）
  和寻址内存相独立，CPU通过系统总线关联I/O设备，并通过总线地址和数据总线读写I/O设备内部的I/O端口。
  I/O端口也可以映射到内存物理空间，并通过DMA访问。
  硬件共享I/O存储也需要映射到内存空间访问，并通过DMA访问。

• 设备驱动程序模型
  总线/设备/驱动/类通过内嵌的kobject组成层级结构，并通过sysfs特殊文件系统展示，sysfs目录即逻辑设备，文件即设备属性。

• 设备文件
  针对I/O设备在/dev目录下生成对应的设备文件，对应的索引节点标明设备类型（通过主设备号/次设备号区分）。
  不同的设备驱动程序提供VFS对应的方法。

• 设备驱动程序
  注册设备驱动程序的目标是关联自己能够处理的设备文件。

• 直接内存访问DMA
  能够绕过CPU直接让硬件和内存间进行数据传输。

• 字符设备驱动程序

核心数据结构

• 内嵌对象kobject
• 设备device
• 驱动程序driver
• 总线bus
• 类class
• 字符设备驱动程序cdev

算法

• 字符设备驱动程序缓冲策略
  使用多个元素的循环缓冲区

优化

暂无。

Linux特色

1. 通过ioctl()系统调用实现对于硬件标准操作之外的操作

遗留问题

1. 如何将I/O端口映射到内存物理空间？
2. I/O端口如何与驱动程序关联？
3. cdev_map和chrdevs散列表的区别？
4. 打开字符设备时文件对象上的ops引用的是cdev的fops而非设备对应索引节点上预定义的fops?

第十四章：块设备驱动程序

感受

为了高效地读写磁盘上的块，内核煞费苦心。

关键点

• 何为块
  块指文件系统和设备处理数据的最小逻辑单位（物理单位是扇区）。
  不同的块设备可以指定不同的块大小。

• 块设备处理的层次

1. VFS（inode了解块）
   读写块设备上的文件（通过特定文件系统）/直接读写块设备文件（/dev下）。
2. 磁盘高速缓存（了解页）
3. 映射层
   将文件块号（由文件系统定义的块大小决定）转换为磁盘逻辑块号（文件系统提供方法）。
4. 通用块层（了解段，块，扇区）
   发出块I/O请求（处理段），并插入请求队列。
5. I/O调度
   根据物理扇区位置合并请求，定时插拔队列驱动块设备驱动程序。
6. 块设备驱动程序
   按段传送数据给磁盘。
7. 磁盘控制器
   按扇区读写磁盘。

• 块设备驱动程序

1. 块设备主次设备号与设备描述符的映射由bdev特殊文件系统维护
2. 驱动程序初始化/设置块设备操作/初始化并注册磁盘以及队列

• 打开块设备
  目标是生成块描述符（执行块设备方法中的open，由块设备驱动个自定义）和对应的文件描述符，给文件描述符设置恰当的操作（def_blk_fops）。

核心数据结构

• 块I/O bio
• 磁盘/磁盘分区gendisk
• 分区表hd_struct
• 请求队列request_queue
• 请求request
• 块设备block_device

算法

• 电梯算法（noop/CFQ/最后期限/预期）
  通过增加排序队列/最后期限队列来优化调度队列。

优化

• 避免拥堵
  请求队列上通过阀值进行类似TCP协议的流量控制。

• 加速
  VFS索引节点的i_bdev/i_cdev存放已打开的设备描述符，加速以后的打开过程。

Linux特色

• 插入/撤销设备驱动程序
  插入时，不读写磁盘。相反撤销时驱动一次读写。

遗留问题

1. block_wait_queue_running()检查当前正在使用的I/O调度程序是否可以被动态取代是什么意思？
2. 插入/撤销请求队列的语义相当晦涩

第十五章：页高速缓存

感受

为什么Linux会把内存占满？页高速缓存是缓存体系里的胖子。

关键点

• 页高速缓存的内容
  各类文件的内容都可以存放在页高速缓存中加速。两种典型是属于普通文件和块设备文件的数据页，会出现冗余。
  另外还有已经交换到磁盘的用户态进程数据页和IPC共享内存页。

• 地址空间(address_space)
  把硬盘上的文件和块设备的内容分割成页大小的地址空间，用32bit（决定了能读写的文件大小）的页索引查找。
  地址空间还包含了读/写/同步等一系列针对页的操作集合。

• 缓冲区页
  读写不相邻的文件页或者设备页（块设备原始数据）时，会把多个块缓冲区组织成缓冲区页，块缓冲区之间用块缓冲区首部链接。
  内核以块为目标单位从缓冲区页查找数据。

• 刷新脏页
  在脏页超过一定比例/脏页存在过久的情况下，唤醒pdflush内核线程将脏页进行同步（并不释放页）。

核心数据结构

• 地址空间address_space
• 基数节点radix_tree_root/radix_tree_node
• 缓冲区首部buffer_head

算法

• 基树
  动态层级，每个节点扇出为64的树，树的叶子节点为页描述符指针，中间节点聚合叶子节点的两种状态（PG_dirty/PG_writeback）。

优化

• 平衡
  根据系统负载，动态调整pdflush系统线程数量，最少2，最多8。

• 加速
  维护一个每CPU的缓冲区首部LRU缓存。

Linux特色

• 块设备的基树
  块设备的基数存储在bdev特殊文件系统块设备对应的索引节点（称为该块设备的主索引节点）中，VFS的索引节点引用该主索引节点。

• 复用页描述符的private字段
  被页高速缓存使用时（已使用），指向块缓存首部链表的首个节点；
  被伙伴系统使用时（空闲），存放所属分组的order。

遗留问题

1. 页高速缓存和交换高速缓存的关系？
2. 刷新脏页的机制如何影响页高速缓冲内的IPC共享内存页？

第十六章：访问文件

感受

访问文件是I/O操作的集大成者。

关键点

• 五种模式

1. 普通访问
   默认访问模式，读操作的终点是用户态空间，写操作的终点页高速缓存。
2. 直接访问（O_DIRECT）
   绕过页高速缓存组件，直接从用户态缓冲区读写数据。
3. 同步访问（O_SYNC）
   保证页高速缓存页被写入硬盘后返回（目标是磁盘自己的缓冲区，并不完全安全）。
4. 异步访问（通过专用系统调用）
   将I/O操作交由工作队列所属内核线程异步执行。
5. 内存映射
   将文件映射在用户态空间进行读写（共享模式依然依赖页高速缓存）。
   包含线性/非线性两种映射方式。

• 共性
  所有文件访问操作都通过address_space定义的方法操作页高速缓存（直接访问除外），并且最后都转化为bio。
  块设备文件和包含不连续块的文件页需要考虑操作块缓冲区。

核心数据结构

• 用户态缓冲区iovec
• 同步/异步I/O状态kiocb
• 预读状态file_ra_state

算法

• 预读
  根据当前是否是顺序读动态调整预读窗口，提高I/O操作效率。

优化

• 延迟

1. 写操作延迟从页高速缓存将脏页同步到磁盘的过程，提高效率
2. 内存映射只生成对应的线性区，数据延迟到调页操作读取

Linux特色

• 写时复制在内存映射时的应用
  当进程要写私有模式的内存映射时，会把原来的页复制一份并替换相应页表项。

• 实现异步的内核调用
  只支持直接访问（O_DIRECT）文件，使用环形缓冲保存异步操作的完成报告。

遗留问题

1. 写入操作存在不考虑块缓冲区的情况吗（文件页也都是缓冲区页）？

第十七章：回收页框

感受

不要问太多为什么，我是内存回收的祖师爷。

关键点

• 回收对象：页框
  页框分为两大类：

1. 映射页
   包含了普通文件/块设备文件内容的页
2. 匿名页
   包含进程自己数据（堆栈/堆）的页

• 页框的状态及回收对策

  • 初始化
    系统初始化后就把内存容量划分为页框（约占总内存的1%）。
  • 空闲
    空闲页框存放在伙伴系统中。
  • 使用中（可以回收）
    • 用户态空间
      1. 匿名页（数据保存到交换区）
      2. 映射页（数据同步到块设备）
    • 内核态空间
      1. 页高速缓存（数据同步到块设备）
      2. 块设备缓冲区（数据同步到块设备）
      3. 索引节点/目录项高速缓存（从slab回收）
      4. 交换高速缓存（匿名页换入换出的中间状态）
  • 使用中（不可以回收）
    1. 内核态动态分配页
    2. 进程内核态堆栈页

• 总体原则

1. 优先回收页高速缓存页（不用修改用户态页表项）
2. 除了锁定页，用户态空间的页都可以窃取
3. 优先回收使用少的页（通过把页按LRU链表分代）
4. 最后手段中止进程

• 回收触发时间

  • 内存紧张时
  • 周期性
    1. kswapd内核线程
       当管理区空闲页数低于阀值时触发。
    2. cache_reap()函数
       由工作队列执行，回收slab。

• 反向映射
  为了快速从页倒推出页表项，需要新的数据结构支持。

  1. 匿名页
     直接记录映射条目数太多，通过在中间增加线性区的层次解决。
  2. 映射页
     通过优先搜索树解决。

• 交换区
  为匿名线性区在块设备上准备的临时持久化区域。被交换出去的页在页表项记录换出页标识符。
  在换入换出时现将页归入交换高速缓存（独立地址空间swapper_space），以解决并发问题。

核心数据结构

• 匿名线性区链表anon_vma
• LRU链表zone->active_list/zone->inactive_list
• 交换区描述符swap_info_struct

算法

• 优先搜索树PST
  快速找到包含一个页的所有线性区的树（基索引+堆索引+大小索引）

• 计算交换倾向值
  交换倾向值 = 映射比率/2 + 负荷值 + 交换值
  交换倾向值>=100时才考虑回收进程用户态空间的页。

优化

• 加速
  通过mm_sturct->mapping最后一位是否为0区分映射页（address_space）还是匿名页（因为address_space是对齐的）。

• 延迟
  把页加入管理区的活动/非活动链表时先修改pagevec临时数据结构。

Linux特色

• 交换标记
  为了防止类似死锁的情况，可以给进程设置交换标记，使该进程免于回收。

遗留问题

1. 释放线性区时会先删除再插入（清空交换区时考虑）？

第十八章：Ext2和Ext3文件系统

感受

文件系统的作用是为了更好的管理原信息和文件在磁盘上的物理布局，提高读写效率。

关键点

• 块分为元数据块和普通数据块

  • Ext2的元数据块分类
    • 超级块
      储存文件系统元信息。
    • 块组描述符
      储存块组元信息。
    • 索引节点位图
      快速编码索引节点使用情况。
    • 块节点位图
      快速编码块节点使用情况。
    • 索引节点
      储存索引信息。
    • 间接块
      通过文件块寻址逻辑块使用的中间块。

• 将块分成块组
  同一个目录的子目录或者文件尽量放在同一组块组中，提高读写效率。

核心数据结构

• 磁盘超级块ext2_super_block
• 组描述符ext2_group_desc
• 节点索引表bg_inode_table
• 索引节点对象ext2_inode_info
• 目录项数据块ext2_dir_entry_2

算法

• 数据块寻址
  通过索引节点的i_block字段实现分级（最多3级）间接寻址。

优化

• 冗余
  超级块和块组描述符在每个块组中都有一份拷贝，恢复时可以使用。

• 提前
  在为文件分配数据块时总是预先分配额外的8个数据块。

Linux特色

• 块组的债
  每增加一个目录，债务增加，否则债务减少，作为分配目录时选择块组的一个依据。

• 文件的洞
  文件中的空字符并不占用磁盘空间。

遗留问题

暂无。

第十九章：进程间通信

感受

内核提供给应用程序完成同步和通信的武器库。

关键点

• 管道和FIFO
  通过读写内核区的环形缓冲区进行进程间消息传递。
  管道存在于pipefs特殊文件系统中，FIFO（命名管道）可以存在于普通文件系统中。

• IPC资源在进程间的引用方式

  • 通过预设一个IPC关键词，直到这个IPC关键词的进程可以获取到对应的IPC资源
  • 随机分配，并将分配的到的IPC标识符在进程间共享

• IPC信号量

  • IPC信号量内部包含多个原始信号量
  • IPC信号量提供进程死亡时安全撤销的机制

• IPC消息
  通过内核缓冲区传送可以区分用户类型的消息。

• IPC共享内存
  通过内存映射机制共享数据。
  由于映射的文件在磁盘上并不存在，只能通过交换回收页框。

• POSIX消息队列
  额外支持消息优先级/消息到达的异步通知/阻塞发送接受操作的超时机制等高级特性。

核心数据结构

• 管道索引节点pipe_inode_info
• 管道缓冲区pipe_buffer
• IPC信号量sem_array
• IPC消息队列sem_queue

算法

• 管道环形缓冲区
• IPC标识符计算公式
  IPC标识符 = s（位置使用序号）* M （可分配资源的最大数目）+ i（位置索引）

优化

暂无。

Linux特色

• mqueue特殊文件系统
  POSIX消息队列通过mqueue特殊文件系统，复用VFS接口。

遗留问题

1. 页高速缓存如何影响IPC共享内存？
2. 有哪些使用进程间通信的最佳实践？

第二十章：程序的执行

感受

程序的执行是整个系统的集大成者。

关键点

• 内核如何支持不同的可执行格式
  通过注册可执行格式，可以让系统进行自动适配。

  1. 注册魔数/后缀和对应的解释程序（JAVA程序）
  2. 在文件第一行以#!开头，自动通过把第一行的其它部分解释成可执行程序执行这个文件

• 程序段

  • 正文段
  • 以初始化数据段
  • 未初始化数据段
  • 堆栈段
  • 堆段（匿名）
    每个段对应一个线性区。

• 线性区布局
  经典布局和灵活布局的区别在于匿名和文件映射线性区是从0x40000000（用户态第1G之后）还是用户态堆栈开始分布。
  当进程定义了用户态堆栈的最大空间，就可以使用灵活布局更好的利用用户态空间。

• 用户态堆栈布局（栈顶到栈底）

  • 返回地址
  • 参数数量
  • 参数数组地址
  • 环境变量地址
  • 动态链接程序使用的表（用于建立动态链接程序上下文，链接动态库函数符号）
  • 命令行实际参数
  • 环境字符串参数
  • NULL

• exec系统调用

  • 释放原有进程资源
  • 为新进程分配线性区
  • 载入动态链接程序
  • 返回用户态，执行动态链接程序，分配库函数线性地址（链接）
  • 动态链接程序跳转程序主入口

核心数据结构

• 可执行文件格式linux_binfmt

算法

暂无。

优化

暂无。

Linux特色

• 通过binfmt_misc特殊文件系统注册新的可执行文件
  :name:type:offset:string:mask:interpreter:flags

遗留问题

暂无。

参考文献

1. Daniel P. Bovet, (2005). Understanding the Linux Kernel