Linux内核设计与实现(Linux Kernel Development)

1. C1 Linux内核简介
2. C2 从内核出发
3. C3 进程管理
4. C4 进程调度
5. C5 系统调用
6. C6 内核数据结构
7. C7 中断和中断处理
8. C8 下半部和推后执行的工作
9. C9 内核同步介绍
10. C10 内核同步方法
11. C11 定时器和时间管理
12. C12 内存管理
13. C13 虚拟文件系统
14. C14 块I/O层
15. C15 进程地址空间
16. C16 页高速缓存和页回写
17. C17 设备与模块
18. C18 调试
19. C19 可移植性
20. C20 补丁, 开发和社区

1. C1 Linux内核简介

每个处理器在任何指定时间点上活动必然是其中一种:

运行于用户空间, 执行用户进程
运行于内核空间, 处于进程上下文, 代表特定的进程执行
运行于内核空间, 处于中断上下文, 与任何进程无关, 处理某个特定中断

2. C2 从内核出发

配置内核选项通常是二选一或是三选一. 二选一就是yes/no. 比如CONFIG_PREEMPT就是二选一表示是否开启抢占功能. CONFIG_SMP标识是否开启对称多处理器功能. 三选一就是yes/no/module. 通常驱动程序使用三选一配置项: yes表示把功能编入内核, module表示编译成为可以动态加载的模块. 一些销售商比如Cannoical/Ubuntu和RedHat/Fedora提供的内核几乎把所有的驱动程序都编译成为模块.

内核开发和应用程序开发重要的差异包括以下几种, 内核开发:

不能使用libc. 主要原因是速度和大小.
必须使用GNU C编译器. 内核代码使用了许多GNU C额外功能(比如内联汇编). 这些功能可能在现代编译器如clang也已经具备, 所以理论上也可以使用clang这样的编译器编译内核.
缺乏内存保护机制
难以执行浮点运算
每个进程只有一个很小的定长内核堆栈. 4KB, 8KB, 16KB, 随体系结构不同而不同. 每个处理器都有自己的栈.
因为内核支持异步中断, 抢占和SMP, 所以必须时刻注意并发和同步

3. C3 进程管理

task_struct(~1.7KB)用来描述进, 通过slab分配器分配出来. 在每个进程内核堆栈尾部存放thread_info结构, 这个结构的第一个字段就是task_struct*. 所以内核可以很快速地拿到某个进程的进程描述符task_struct. 比如如果kernel stack size = 8K的话, 那么thread_info地址就在%esp & 8k上, 同时因为第一个字段就是task_struct*, 我们其实就已经得到结果.

Linux实现线程的机制非常独特. 从内核角度来看, 它没有线程这样的概念. Linux把所有的线程都当做进程来实现. 内核并没有准备特别的调度算法或是定义特别的数据结构来表达线程, 仅仅将线程看做一个与其他进程共享某些资源的进程, 每个线程也都对应一个task_struct.

一直很不理解kernel space到底和user space有什么区别. 这篇文章 (Why do 32-bit Linux kernels only recognize 3GB of RAM?, btw, 第一个回复者就是本书作者) 可能会让你有点启发. 我觉得可以这样理解: 从计算机加电, 读取BIOS加载内核代码到内存之后, 每个CPU都运行相同内核代码(驱动), 但是会共享一些数据比如slab分配器, 网络协议栈数据等. 内核会为每个运行进程分配一个内核栈(物理内存), 这个内核栈可能是1-2个page, 用于 a. 保存用户进程切换到内核态时状态 b. 内核代码开辟临时变量以及函数调用等. 内核使用的物理内存(ZONE_DMA, ZONE_NORMAL), 理论上内核可以映射到任何虚拟地址上. 只不过约定地内核将和内核相关的text, stack, data等映射到kernel space(不太确定kernel space布局是否和user space相同), 而将用户空间物理内存映射到user space.

4. C4 进程调度

Linux有两个重要的调度器实现O(1)和CFS.

Linux2.4以及之前的调度器相当简陋近乎原始, 虽然很容易理解, 但是不适合调度大量进程以及在多处理器下工作.
Linux2.5引入O(1)调度器, 可以在数以十计(不是数以百计)的多处理器环境下表现出近乎完美的性能和扩展性. O(1)比较适合服务器负载(强调吞吐), 但是不适合交互程序(强调响应)的桌面系统
Linux2.6引入CFS调度器, 完全(Completely)公平(Fair)调度器(Scheduler). 解决O(1)调度器的问题, 同时适合服务器和桌面系统

O(1)和CFS都是基于优先级的调度. 每个进程都有一个nice值[-20, 19]. nice越大表示这个进程比较好说话优先级越低. 进程被调度之后能够持续运行一段时间, 这段时间称为时间片(timeslice). O(1)和CFS最重要的区别在于, O(1)使用nice直接计算出进程可运行的时间片, 而CFS预估所有进程可运行总时间, 然后使用nice作为权重来从中分配时间片.

O(1)将nice映射成为时间片有两个问题. 首先是如何映射, 假设按照算术分配的话默认最大时间片200ms, 那么

nice = 0, 1分配时间片是 (20 - 0) / 40 * 200 = 100ms, (20 - 1) * 200 / 40 = 95ms
nice = 18, 19分配时间片是 (20 - 18) / 40 * 200 = 10ms, (20 - 19) * 200 / 40 = 5ms

0, 1时间运行时间比例是差不多的, 但是18, 19时间比例却是2倍. 另外可以看到调度间隔最小是5ms, 但是如果系统定时器精度>5ms比如(10ms)的话, 那么我们就需要将最大时间片拉到400ms. 我们可以很明显看到其不合理之处. 但是也是有解决办法的话, 就是使用几何分配(对数)而不是算术分配. 另外一个问题是O(1)不太适合交互式应用: 我们希望交互式应用响应要快, 自然分配优先级要更高, 按照O(1)调度器分配给交互式应用时间片越大. 但是这却不符合交互式应用特点(IO密集而非CPU密集).

CFS工作原理大致是这样的:

预估系统目标延迟. 比如40ms. 假设存在n个nice相同的进程, 那么每个进程可分配到时间片为40/n ms (# 但是运行时间片要高于时钟精度)
对于优先级比较高的任务, 分配的时间片也就更多. 和O(1)遇到的问题一样, 这里必须使用几何分配而非算术分配
在调度记录上, CFS会将进程运行绝对时间转换成为一个相对时间. 这就意味着虽然某个进程运行时间长, 但是如果优先级足够高, 但是其相对时间(虚拟时间)可能也非常小
选择下一个可运行任务时, 挑选运行虚拟时间最小的进程. (# 对于新来任务如何处理? 这个问题没有讲清楚. 比较简单的办法是, 对于新加入任务虚拟运行时间赋予当前最小运行虚拟时间)

update: O(1)和CFS之间差别在于, O(1)是用nice值来分配绝对时间片(而不作为pick next指标), 而CFS是使用nice作为pick next指标但是依然使用固定时间片. 根据一段时间内的(应该分配时间片, 实际时钟时间)比重, 可以很很容易知道系统属于什么workload, 是interactive(io intensive)或是batch(cpu intensive), 从而指定不同的优先级.

Linux调度器是以模块方式提供的, 这种模块化结构被成为调度器类(scheduler classes), 允许多个不同的可动态添加的调度算法并存, 调度属于自己范畴的进程. 每个调度器有自己的优先级别. 内核按照优先级顺序遍历调度类, 如果某个调度类有进程选出的话那么就返回. O(1)和CFS都是针对普通进程的调度类(SCHED_NORMAL, SCHED_OTHER). 实时类有两种SCHED_FIFO和SCHED_RR. Linux的实时调度算法提供的是软实时, 睢冉不能保证硬实时工作方式, 但是基本上可以满足严格的时间要求.

5. C5 系统调用

6. C6 内核数据结构

7. C7 中断和中断处理

硬件通过中断控制器告诉CPU产生一个中断请求(IRQ), 然后CPU中断内核保存当前寄存器, 然后执行内核初始化时注册的中断处理程序或中断服务例程(ISR, interrupt service routine), 完成后恢复寄存器返回内核.

中断可能随时发生, 因此中断处理程序也就随时可能执行. 因为中断处理程序实际上打断了内核代码, 所以必须保证中断处理程序能够快速执行. 通常我们把中断处理程序分为两个部分: 上半部(top half)和下半部(bottom half). 上半部工作是对中断立刻做出响应, 然后在内核中记录下来. 而下半部则是内核根据上半部的记录采取措施. 打断内核代码的是上半部, 因此上半部的代码必须简洁高效, 尽可能地将工作放在下半部完成.

如果当前有一个中断处理程序正在执行, 在最好的情况下(如果IRQF_DISABLED没有被设置), 与该中断同级别的其他中断会被屏蔽. 在最坏的情况下(如果设置IRQF_DISABLED), 那么当前处理器上所有其他中断都会被屏蔽. 中断屏蔽后硬件与操作系统无法通信, 所以这也是为什么中断处理程序执行越快越好的另外一个原因.

/proc/interrupts存放了系统中与中断相关的统计信息. 第一列是IRQ, 之后是各个CPU响应中断的次数, 第三列是中断控制器, 第四列是中断相关的设备名字

➜  ~  cat /proc/interrupts
           CPU0       CPU1       CPU2       CPU3       CPU4       CPU5       CPU6       CPU7
  0:         15          0          0          0          0          0          0          0   IO-APIC-edge      timer
  1:          0          1          0          0          1          0          0          0   IO-APIC-edge      i8042
  5:          0          0          0          0          0          0          0          0   IO-APIC-edge      parport0
  8:          0          0          1          0          0          0          0          0   IO-APIC-edge      rtc0
  9:          3          0          0          0          0          0          0          0   IO-APIC-fasteoi   acpi
 12:          2          0          0          0          0          1          1          0   IO-APIC-edge      i8042
 16:       5713         16          4         11      40064         18          5         33   IO-APIC-fasteoi   ehci_hcd:usb1
 23:         15          1          3          0          4          0          0         10   IO-APIC-fasteoi   ehci_hcd:usb2
 40:          0          0          0          0          0          0          0          0   PCI-MSI-edge      xhci_hcd
 41:     164224         10          8          3         35          1          9          4   PCI-MSI-edge      eth0
 42:      13733       1417      39774        783       9170       1775      94333       1211   PCI-MSI-edge      ahci
 43:         10          1          1          0          9          1          0          2   PCI-MSI-edge      mei_me
 44:     240530      28013      24634      19673      57747      39523      32998      28314   PCI-MSI-edge      i915
 45:         41         52          1         53        101         64         86         11   PCI-MSI-edge      snd_hda_intel
NMI:         40         40         39         40         21         23         26         22   Non-maskable interrupts
LOC:     591019     647496     652400     649676     313131     293444     326093     307739   Local timer interrupts
SPU:          0          0          0          0          0          0          0          0   Spurious interrupts
PMI:         40         40         39         40         21         23         26         22   Performance monitoring interrupts
IWI:      20614      31621      31246      31537       9568      10072       9511      10984   IRQ work interrupts
RTR:          6          0          0          0          0          0          0          0   APIC ICR read retries
RES:     101301      92590      82353      84742      37285      34751      38561      33887   Rescheduling interrupts
CAL:        528        600        551        560        588        484        464        641   Function call interrupts
TLB:     345796     347255     351332     349519     189273     189826     182712     181183   TLB shootdowns
TRM:          0          0          0          0          0          0          0          0   Thermal event interrupts
THR:          0          0          0          0          0          0          0          0   Threshold APIC interrupts
MCE:          0          0          0          0          0          0          0          0   Machine check exceptions
MCP:         28         28         28         28         28         28         28         28   Machine check polls
ERR:          0
MIS:          0

8. C8 下半部和推后执行的工作

下半部(bottom half)实现机制有下面几种:

BH(Bottom Half, 同名). 废弃, 从2.5中去除
任务队列(task queues). 废弃, 从2.5中去除
软中断(soft irq). 2.3引入
tasklet. 2.3引入
工作队列(work queues) 2.5引入

这里只说后面三种. tasklet依赖于软中断, 原理上两者相同, 只是稍有细微差别.

软中断(soft irq)相对应的应该是硬中断(hard irq, 那些来自硬件设备触发的中断), 和系统调用软件中断(software interrupt)是两个不同概念. 软中断是在编译期静态分配的, 最多只能有32个软中断.

struct softirq_action {
    void (*action)(struct softirq_action*);
    // 调用方式 my_softirq->action(my_softirq);
    // 可以在softirq_action结构后面带上自定义数据
};
static struct softirq_action softirq_vec[NR_SOFTIRQS]; // NR_SOFTIRQS == 32

要求在设备驱动初始化时将软中断注册上之后不在更改. 在单个处理器上最多运行一个软中断, 但是其他处理器可能也会同时运行(甚至相同的)软中断. 因此软中断必须处理同步问题. 所以软中断可以充分利用多核优势, 适合性能要求高的场景, 但是实现难度也更大. 中断上半部(top half)完成之后会标记对应的软中断成为触发软中断(raise softirq). 在下面这些地方, 待处理的软中断会被检查和执行:

从一个硬件中断代码返回处; (raise softirq返回之后立刻执行)
在ksoftirq内核线程中; (这个放在后面说)
在那些显示检查和执行待处理的软中断代码中比如网络子系统. (就是说在软中断代码中也会检查)

目前已经使用软中断的有(按照优先级排列)

HI_SOFTIRQ 优先级别最高
TIMER_SOFTIRQ 定时器
NET_TX_SOFTIRQ 发送网络数据包
NET_RX_SOFTIRQ 接受网络数据包
BLOCK_SOFTIRQ
TASKLET_SOFTIRQ tasklet
SCHED_SOFTIRQ
HRTIMER_SOFTIRQ 高分辨定时器
RCU_SOFTIRQ

网络设备上的数据处理实时性要求比较高, 所以使用软中断非常合理. 但是有一些下半部对性能要求不高, 也不想考虑多处理器同步问题, 那么就比较适合使用tasklet. 并且tasklet可以动态创建和执行, 使用上比较灵活. tasklet实现是依赖软中断的. 所有tasklet可以组织成为一个链表. 当需要调度tasklet时候, 也可以选择性地挂在HI_SOFTIRQ或是TASKLET_SOFTIRQ软中断上. 同时tasklet内置一个状态标记, 表示自己是否正在运行. 如果同一个tasklet被多个处理器执行的话, 会通过判断这个标记确保只有这个tasklet只在一个处理器上运行.

不管是软中断还是tasklet都面临一个问题, 就是软中断触发频率过高(处理软中断的时候, 另外一个硬中断到来, 触发新的软中断). a. 在软中断处理之后继续检查新触发的软中断 b. 将新触发软中断放在下一轮软中断处理. ab两个方案是在负载和延迟方面做取舍. 理想办法应该是如果负载比较低的话应该就近执行, 否则应该适当地延迟处理. 适当延迟处理使用线程池ksoftirqd. 线程池有n个线程, 其中n = # CPU, 名字叫做ksoftirqd/<i>对应地处理#i处理器上的软中断. 通常ksoftirqd都是处于空闲状态, 只有当太多软中断待处理的时候, 内核才会唤起ksoftirqd. ksoftirqd优先级被设置为最低, 目的就是为避免和其他重要任务抢夺资源.

最后是工作队列. 工作队列的引入, 是因为某些下半部需要睡眠. 此时这些下半部使用软中断还是tasklet都是不合适的, 因此需要单独开辟线程池来处理. 默认工作线程池叫做events/n, 其中n = # CPU. 当然用户也可以自己创建线程池而不是用默认线程池.

9. C9 内核同步介绍

10. C10 内核同步方法

11. C11 定时器和时间管理

体系结构提供了两种设备计时, 一中是实时时钟. 一种是系统定时器.

实时时钟(RTC)是用来持久存放系统时间的设备, 即便系统关闭后, 它也可以靠主板上的微型电池提供的电力保持系统的计时. 在PC体系结构中, RTC和CMOS集成在一起, 而且RTC的运行和BIOS的保存设置都是通过同一个电池供电的. 当系统启动时, 内核通过读取RTC来初始化墙上的时钟, 该时间存放在xtime变量中. 虽然内核通常不会在系统启动后再读取xtime变量, 但是有些体系结构(比如x86)会周期性地将当前时间存回RTC中. 尽管如此, 实时时钟主要作用仍是在启动时初始化xtime变量.
尽管不同体系结构中定时器实现不同, 但是根本思想都是通过周期性触发中断实现的. x86体系结构中采用可编程中断时钟(PIT). 内核在启动时对PIT进行编程初始化, 以HZ频率产生时钟中断. x86体系结构中其他时钟资源还包括本地APIC时钟和时间戳计数器(TSC)等. HZ通常设置为100/1000, 表示每隔10ms/1ms就会产生一次时钟中断(TIMER_SOFTIRQ). 这个频率通常也称为定时器节拍率(tick rate).

操作系统是否一定要有固定时钟? Linux内核也支持"无节拍操作"的选项. 本质上就是可以通过系统负载来动态设置时钟中断频率. 高HZ可以提供系统精确度, 代价则是上下文切换开销. 通过系统负载来动态设置时钟频率, 减少开销是一方面, 但是实质性收益还是省电, 尤其是在系统空闲时. 基于节拍的标准系统中, 即使在系统空闲期间, 内核也需要未时钟中断提供服务. 而对于无节拍的系统而言, 空闲档期不会被不必要的时钟中断打断, 于是减少了系统的能耗.

内核使用全局变量jiffies来记录系统启动以来产生的节拍总数. 启动时初始化为0, 每次时钟中断时+1. 除此之外时钟中断处理程序还会: a. 更新xtime以及墙上时钟 b. 更新资源消耗统计值, 将tick记入当前进程 c. 触发定时器软中断(TIMER_SOFTIRQ). 在软中断中会执行动态定时器.

动态定时器的引入是为了延迟执行. 假设我们想sleep 1s, 如果只是忙等的话那么纯粹就是在无谓地消耗CPU, 而这1s如果分配给其他进程则可以做许多事情. 更加合理的方式应该是设置一个定时器, 将自己yield出去, 等1s过去之后再回来. 但是如果我们只想等待很短一段时间(比如100us)的话, 动态定时器是做不到的, 因为时钟精度达不到. 比如重新设置网卡的以太模式需要花费2ms, 所以在设定网卡速度后, 驱动程序必须等待2ms才能运行. 此时我们只能通过消耗CPU来等待这段短时间. 问题来了, 假设我们想等待100us, 那么代码应该怎么实现. 为了精度, 代码应该使用汇编编写并且屏蔽本地CPU中断以及禁止抢占.

movl %rcx, <loop-times>
loop:
addl %rdx, 1
subl %rcx, 1
jnz loop

接下来问题就是这个loop-times应该设置多少呢? 我们就有了BogoMIPS. BogoMIPS可以在dmesg中看到. 它记录处理器在给定时间内忙循环执行的次数, 在内核启动时利用calibrate_delay计算出, 存放在loops_per_jiffy中可以从/proc/cpuinfo中读取.

[    0.004000] tsc: Detected 3491.869 MHz processor
[    0.000002] Calibrating delay loop (skipped), value calculated using timer frequency.. 6983.73 BogoMIPS (lpj=13967476)

processor	: 0
vendor_id	: GenuineIntel
cpu family	: 6
model		: 58
model name	: Intel(R) Core(TM) i7-3770K CPU @ 3.50GHz
cpu MHz		: 1600.000
cache size	: 8192 KB
bogomips	: 6983.73

12. C12 内存管理

Linux用户空间与内核空间

内核把物理页作为内存管理的基本单元. 尽管处理器的最小可寻址单位通常为字(甚至字节), 但是内存管理单元(MMU, 管理内存并把虚拟地址转换成为物理地址的硬件)通常以页为单位进行处理. 正因为如此, MMU以页(page)大小为单位来管理系统中的页表. 从虚拟内存的角度来看, 页就是最小单位. 内核用struct page结构表示系统中的每个物理页.

由于硬件限制, 内核不是对所有页一视同仁. 所以内核把页划分为不同的区(zone). 内核使用区来对具体相似特性的页进行分组. Linux必须处理如下两种由于硬件存在缺陷而引起的内存寻址问题:

一些硬件只能用特定的内存地址来执行DMA(direct memory access)
一些体系结构的内存物理寻址比虚拟寻址范围大得多, 这样一些内存不能永久映射到内核空间上(HIGHMEM)

因为存在这些制约条件, Linux使用了4种区:

ZONE_DMA. 这个区的页只能用来执行DMA操作
ZOME_DMA32. 和ZONE_DMA类似, 但是只能被32位设备访问
ZONE_NORMAL. 这个区包含的都是能正常映射的页
ZONE_HIGHMEM. 高端内存, 其中页不能永久地映射到内核地址空间.

对于HIGHMEM, 我的理解是这样的: 32位linux系统内核空间在3~4GB(1GB). 如果物理内存超过1GB的话, 那么对于超过1GB的物理内存内核是无法访问的. 同理对于64位系统来说内核空间有128TB. 理论上如果物理内存超过128TB的话, 内核要使用访问超过128TB内存也需要使用HIGHMEM. 但是现实中超过128TB内存情况非常少, 所以可以认为64位系统没有HIGHMEM这个区. (64位系统0x0000,0000,0000,0000 - 0x0000,7fff,ffff,f000这128T地址用于用户空间, 0xffff,8000,0000,0000 - 0xffff,ffff,ffff,ffff这128T用于内核空间, 中间是一个巨大空洞为以后扩展预留).

x86(MMU相关)-32(虚拟地址相关)系统上区是这样分配的

区	描述	物理内存
ZONE_DMA	DMA	<16MB
ZONE_NORMAL	正常可寻址页	16~896MB
ZONE_HIGHMEM	动态映射页	>896MB

假设我们物理内存>1GB, 那么应该如何访问超过1GB的内存呢? 答案就是我们先不将ZONE_HIGHMEM固定映射到[896M, 1G]物理地址范围上, 而是允许内核临时借用这段虚拟地址范围映射到高端内存上去, 使用完成之后立即归还.

所有内存分配器分配函数都有gfp_mask标志. 标志可以分为三类: a. 行为修饰符 b. 区修饰符(DMA, HIGHMEM) c. 类型(ab一些可能组合, 用来简化使用). 行为修饰符涉及到许多策略, 这些策略和系统环境和使用场景相关, 好的内存分配器就需要考虑各种使用场景:

GFP_WAIT. 允许睡眠
GFP_HIGH. 允许访问紧急事件缓冲区
GFP_IO. 允许启动磁盘IO
GFP_FS. 允许启动文件系统IO
GFP_COLD. 应该使用高速缓存中快要淘汰出去的页
GFP_NOWARN. 不打印失败警告
GFP_REPEAT. 分配失败时重新分配, 接下来允许失败
GFP_NOFALL 无限地重复进行分配, 分配不能失败
GFP_NORETRY 失败时绝对不会重新分配
GFP_NOGROW 由slab内部使用
GFP_COMP 添加混合页元数据, 在hughtlb代码内部使用

13. C13 虚拟文件系统

用户空间-VFS(虚拟文件系统)-文件系统(ext4, ntfs, etc.)-物理介质

VFS中有四个主要的对象类型分别是:

超级块(super block)对象. 代表一个已经安装的文件系统. 管理inode, 挂载点等.
索引节点(inode)对象. 代表一个具体文件.
目录项(dir entry)对象. 代表一个目录项, 是路径的一个组成部分(/sbin/ifconfg, 有三个目录项 /, sbin, ifconfig)
文件对象. 代表进程打开的文件.

还有两个和文件系统相关的数据结构: a. file_system_type 用来描述特定文件系统类型, 最重要的方法就是创建super block对象 b. vfsmount 理清文件系统和其他安装点的关系.

有三个数据结构将VFS层和系统进程紧密联系

files_struct. 进程所有打开的文件
fs_struct. 进程根目录路径以及当前工作路径
mnt_namespace. 进程使用的挂载点

线程在创建时使用CLONE_FILES和CLONE_FS标识, 所以多个线程会共享files_struct以及fs_struct结构体.

struct files_struct {
  atomic_t count; // 使用计数
  struct fdtable *fdt; // 指向其他fd表
  struct fdtable fdtab; // 基本fd表. 指向fd_array
  spinlock_t file_lock;
  int next_fd; // 缓存下个可用fd
  struct embedded_fd_set close_on_exec_init; // exec时关闭的文件描述符
  struct embedded_fd_set open_fds_init // 打开文件描述符
  struct file *fd_array[NR_OPEN_DEFAULT];  // 缺省文件对象数组. NR_OPEN_DEFAULT = 64
};

如果打开文件数量超过NR_OPEN_DEFAULT, 才会使用fdt分配fdtable. 否则使用fdtab. 因此如果打开文件数量很少的话, 对文件对象的访问会很快.

14. C14 块I/O层

块(block)在大小上, 一方面要求是设备最小寻址单元的2^n倍, 另外一方面要求页大小是块大小的2^m倍. 当一个块被调入内存时, 它要存储在一个缓冲区中. 因为页大小是块大小整数倍, 所以一个页(page)可以容纳多个缓冲区(buffer). 每个缓冲区都有一个缓冲区头(分开存放), 用于描述磁盘块和缓冲区之间的映射关系. 在2.6内核以前, 缓冲区头还作为内核IO操作单元, 但是比较缺乏效率: 1. 缓冲区头部非常复杂不容易管理 2. 一次IO会涉及很多块, 那么就需要开辟很多buffer head, 管理和空间开销上都有负担. 所以在2.6之后使用bio结构体描述IO操作单元, 具体地使用IO向量, 每个向量是(物理页, 偏移, 长度)三元组表示一个缓冲区. 所有IO请求都加入请求队列, 然后由IO调度程序调度执行.

IO调度程序管理块设备的请求队列, 决定队列中请求排列顺序以及什么时候派发请求到快设备上, 目的是为了减少磁盘寻址时间提高全局吞吐. 主要通过两种办法: 合并和排序

Linus电梯: 每次插入请求时看是否可以合并, 否则尝试按照顺序找到正确插入点. 如果发现队列中有驻留时间过长请求, 那么将请求放在尾部. 问题是, 即便将请求放在尾部, 也不能改善那个驻留时间过长的请求.
最终期限(deadline)IO: 在Linus电梯上改进. 分离读写请求(通常写请求是异步的, 而读请求则是同步. 所以为写请求设置超时时间5s, 而读请求设置超时500ms). 设置3个队列, a. ReadFIFO 读FIFO队列 b. WriteFIFO 写FIFO队列 c. 排序队列(和Linus电梯一样). 读请求会被加入a和c, 写请求加入b和c. 然后同时从abc队列读取, 默认地先从c获取, 但是如果发现ab出现超时的话那么先响应ab. 注意完成之后需要将ab中的请求从c移除避免重复执行
预测(as)IO: 假设一个系统处理很繁重写操作期间, 每次提交读请求, deadline IO都会去有限响应, 这就造成写-读-写-读多次寻址. as-IO在deadline-IO上改进, 完成读操作后不立即取下一个请求, 而是等待片刻(比如6ms)查看是否有新的读请求到来. 如果有新读请求到来并且请求相邻位置, 那么可以立刻得到处理. 我们要预测这个等待时间, 如果预测准确率足够高的话, 那么既减少读响应时间, 又减少寻址次数和时间.
完全公平队列(Completely Fair Queuing, CFQ)IO: 每个进程维护一个请求队列, 以时间片轮转调度队列, 从每个队列中选取请求数(默认值4), 加入到全局排序队列中(做全局合并排序). 能够确保每个进程接收公平的磁盘带宽片断.
空操作(noop)IO: 只做合并不做排序, 专门为随机访问设备比如ssd设计.

15. C15 进程地址空间

内核使用内存描述符(mm_struct)结构体表示进程的地址空间, 包含了和进程地址空间有关的全部信息. 内核将所有的内存描述符(mm_struct)使用双向链表连接起来, 链表头是init进程的地址空间init_mm. 进程地址空间由多个虚拟内存区域组成(virtual memory area), 内核使用vm_area_struct来表示虚拟内存区域(VMA). 内存描述符里面记录了该进程所使用的所有虚拟内存区域(VMA). 为了方便管理VMA, 内存描述符使用两种方式来组织这些内存区域 a. 链表 b. 红黑树. 链表是为了能够遍历所有的VMA, 而红黑树则是为了快速定位某个内存地址对应的VMA.

内核进程没有单独分配内存描述符, 而是使用调度前一个进程的内存描述符. 这样一方面避免额外内存开销, 另一方面避免浪费处理器向新地址空间切换.

/proc/<pid>/maps以及pmap工具可以查看进程地址空间. pmap输出字段分别是起始地址, 区域大小, 权限, 以及二进制文件. proc输出还包括主次设备号和inode节点.

➜  notes git:(master) ✗ pmap 3252
3252:   python -m SimpleHTTPServer 8080
0000000000400000   2804K r-x-- python2.7
00000000008bc000      4K r---- python2.7
00000000008bd000    468K rw--- python2.7
0000000000932000     72K rw---   [ anon ]
0000000000bbc000   1880K rw---   [ anon ]
00007f9307157000     44K r-x-- libnss_files-2.19.so
00007f9307162000   2044K ----- libnss_files-2.19.so
00007f9307361000      4K r---- libnss_files-2.19.so
00007f9307362000      4K rw--- libnss_files-2.19.so

➜  notes git:(master) ✗ cat /proc/3252/maps
00400000-006bd000 r-xp 00000000 08:01 2491354                            /usr/bin/python2.7
008bc000-008bd000 r--p 002bc000 08:01 2491354                            /usr/bin/python2.7
008bd000-00932000 rw-p 002bd000 08:01 2491354                            /usr/bin/python2.7
00932000-00944000 rw-p 00000000 00:00 0
00bbc000-00d92000 rw-p 00000000 00:00 0                                  [heap]
7f9307157000-7f9307162000 r-xp 00000000 08:01 5130143                    /lib/x86_64-linux-gnu/libnss_files-2.19.so
7f9307162000-7f9307361000 ---p 0000b000 08:01 5130143                    /lib/x86_64-linux-gnu/libnss_files-2.19.so
7f9307361000-7f9307362000 r--p 0000a000 08:01 5130143                    /lib/x86_64-linux-gnu/libnss_files-2.19.so
7f9307362000-7f9307363000 rw-p 0000b000 08:01 5130143                    /lib/x86_64-linux-gnu/libnss_files-2.19.so

Linux使用三级页表完成虚拟地址到物理地址的转换. 为了加快转换, 多数体系结构都实现了转译后备缓冲区(translate lookaside buffer, TLB).

16. C16 页高速缓存和页回写

页高速缓存(page cahce)的目标是缓存任何基于页的对象, 包括各种类型的文件和各种类型的内存映射, 但是主要是为了缓存磁盘文件来加快读写速度. Linux使用address_space对象来管理页高速缓存, 内部inode指针表示对应的磁盘文件. 一个文件在整个系统中只对应一个address_space对象.

页高速缓存(page cache)和块缓冲区(block cache, block buffer)之间的关系非常微妙. C14中提到了, 在2.6之前, 所以IO操作都是通过提交块缓冲区来执行的. 也就是说, 用户态写文件, 首先会写page cache, 同时也会写入block cache来发起IO操作. 一个磁盘块数据可以同时存于两个缓存中, 不仅浪费内存, 还需要考虑同步两个缓存中的数据. 2.6之后使用通过bio来管理IO请求, block cache就可以不再参与文件读写. 但是block cache依然有一些作用 a. 读写inode节点 b. 直接操作块底层(O_DIRECT). block cache和page cache大小可以从 `free -t` 命令中看到. 其中 `buffers` 对应block cache, `cached` 对应page cache.

➜  notes git:(master) ✗ free -t
             total       used       free     shared    buffers     cached
Mem:       8047140    3786604    4260536     393104     334472    1405072
-/+ buffers/cache:    2047060    6000080
Swap:      4891644          0    4891644
Total:    12938784    3786604    9152180

17. C17 设备与模块

并不是所有设备都表示物理设备, 有些设备驱动是虚拟的, 仅提供访问内核功能而已, 我们称为"伪设备"(pseudo device). 常见的如内核随机发生器(dev/random, /dev/urandom), 空设备(/dev/null), 零设备(/dev/zero), 满设备(/dev/full), 内存设备(/dev/mem). 然而大部分设备驱动都表示物理设备.

18. C18 调试

通过打印来调试: 基本上所有地方可以使用printk来打印, 不用考虑是在进程还是中断上下文, 或是是否持有特定锁以及运行在SMP环境下. 唯一例外就是系统启动过程中, 终端还没有完成初始化. 即便如此核心硬件部分的黑客依然能靠已经初始化的硬件设备与外界通信(比如串口设备)来实现打印调试.

内核消息都被保存在一个LOG_BUF_LEN大小的环形队列中, 缓冲区大小可以在编译时通过CONFIG_LOG_BUF_SHIFT进行调整, 默认是16KB. see dmesg.

SysRq 可以在系统崩溃时进行调试和挽救.

kgdb是一个补丁, 可以让我们在远端主机上通过串口利用gdb的所有功能对内核进行调试. 这需要两台机器: 一台运行带有kgdb补丁的内核, 一台通过串行线使用gdb对第一台进行调试.