lk14_00 图 1:第 14 章章首插图

这一篇在干嘛?

磁盘是计算机里最慢的主要部件之一:寻道要几毫秒,而 CPU 和总线的操作是纳秒级的。本章讲 Linux 块 I/O 子系统的四层架构——通用块层、I/O 调度器(电梯)、块设备驱动——如何用 bio 结构、请求队列和调度算法把零散的 I/O 请求攒成批量、按最优顺序喂给磁盘,把慢设备用出高性能。这是理解文件系统性能(第 15、16 章)的关键。

块设备处理总览 | 通用块层 | I/O 调度器 | 块设备驱动 | 打开块设备文件

块设备处理总览

块设备驱动处理的对象是各种磁盘。块设备的核心矛盾是速度落差:磁盘平均访问时间极高——每次操作要几毫秒,主要耗在磁盘控制器把磁头移动到数据所在的精确位置上;可一旦磁头就位,数据传输速度可达每秒几十兆字节。Linux 块设备处理的组织因此相当复杂,好在总体架构是清晰的。

一次 read() 系统调用(写请求的处理方式本质上相同)会牵动一大串内核组件:

lk14_01 图 1:块设备操作涉及的内核组件

  1. read() 的服务例程激活相应的 VFS 函数,传入文件描述符和文件内偏移。VFS 是块设备处理架构的最上层,提供所有文件系统共用的统一文件模型(第 12 章)。
  2. VFS 判断所请求数据是否已经可用、必要时如何执行读操作。有时根本不需要访问磁盘,因为内核把最近读/写过块设备的数据保留在 RAM 里——这就是磁盘缓存(第 15 章);VFS 如何处理磁盘操作、如何与磁盘缓存和文件系统衔接,见第 16 章。
  3. 假设必须从块设备读数据,内核就得确定数据的物理位置。这由**映射层(mapping layer)**完成,通常两步:
    • 确定文件所在文件系统的块大小,把请求数据换算成文件块号——把文件看成许多块的序列,找出请求数据落在哪些块里;
    • 调用文件系统特定的函数访问文件的磁盘 inode,把文件块号映射为逻辑块号——把磁盘看成许多块的序列,找出数据存放在磁盘(或分区)开头的第几块。因为文件可能散落在不相邻的磁盘块上,磁盘 inode 里存的数据结构负责这个映射。映射层的实际运作见第 16 章,典型磁盘文件系统见第 18 章。
  4. 内核现在可以对块设备发读操作了。它使用**通用块层(generic block layer)**启动传输数据的 I/O 操作。一般每个 I/O 操作涉及磁盘上一组相邻的块;因为所求数据在磁盘上未必相邻,通用块层可能启动多个 I/O 操作。每个 I/O 操作用一个 bio 结构表示,收集下层组件满足请求所需的全部信息。通用块层隐藏了各硬件块设备的差异,还提供描述”磁盘”和”磁盘分区”的通用数据结构。
  5. 通用块层之下是 I/O 调度器,按预定义的内核策略为待处理的 I/O 传输请求排序,目的是把物理介质上位置相近的数据请求归拢到一起。
  6. 最底下,块设备驱动向磁盘控制器的硬件接口发送合适命令,完成实际数据传输。

扇区、块、段:三种数据尺寸

注意上面各组件管理磁盘数据用的”颗粒”不一样大:

  • 硬件块设备的控制器按**扇区(sector)**传输数据——固定长度的相邻字节组,I/O 调度器和块设备驱动必须按扇区管理数据;
  • VFS、映射层和文件系统按**块(block)**组织磁盘数据——块是文件系统内部的最小磁盘存储单元;
  • 块设备驱动要能对付段(segment)——一个内存页(或页的一部分),其中包含磁盘上物理相邻的数据块;
  • 磁盘缓存以为单位工作,每页放进一个页框;
  • 通用块层把上下各层粘在一起,所以扇区、块、段、页它都得认识。

虽然颗粒不同,它们通常共享同一批物理 RAM 单元。看一个 4096 字节页的典型布局:上层组件把它看成 4 个 1024 字节的块缓冲;页的最后 3 块正被块设备驱动传输,它们构成一个覆盖页末 3072 字节的段;硬盘控制器则把这个段看成 6 个 512 字节的扇区。

lk14_02 图 2:包含磁盘数据的页的典型布局

本章描述处理块设备的下面几层组件——通用块层、I/O 调度器、块设备驱动——因此聚焦扇区、块和段。

扇区

为达到可接受的性能,硬盘之类设备一次传输一组相邻字节,这组字节叫一个扇区。所谓”相邻”,指这些字节在磁盘表面上的记录方式使得一次寻道就能访问到。虽然磁盘的物理几何通常很复杂,硬盘控制器接受的命令把磁盘看成一个巨大的扇区数组

大多数磁盘的扇区是 512 字节,也有用更大扇区(1024、2048 字节)的设备。扇区是数据传输的基本单位:传输量永远不可能小于一个扇区,尽管多数磁盘能一次传多个相邻扇区。

Linux 约定扇区大小固定为 512 字节;如果块设备用更大的扇区,对应的底层驱动负责转换。块设备上的一组数据由它的位置(首个 512 字节扇区的索引)和长度(512 字节扇区的个数)标识。扇区索引存在 32 或 64 位的 sector_t 类型变量里。

扇区是硬件的传输单位,则是 VFS(进而是文件系统)的数据传输基本单位。比如内核访问一个文件的内容时,必须先从磁盘读出包含该文件磁盘 inode 的块(第 12 章),这个块对应一个或多个相邻扇区,VFS 把它们看成一个整体。

Linux 中,块大小必须是 2 的幂,不能大于一个页框,还必须是扇区大小的整数倍。因此在 80×86 上允许的块大小是 512、1024、2048、4096 字节。

块大小不属于块设备本身——创建磁盘文件系统时由管理员选择,同一磁盘的不同分区可以用不同块大小。而对块设备文件的每次读写都是绕过文件系统的”原始”访问,内核用最大的块(4096 字节)来执行它。

每个块需要自己的块缓冲(block buffer)——内核用来存放块内容的 RAM 区。从磁盘读块时,内核用硬件取得的数据填充缓冲;往磁盘写块时,用缓冲的实际值更新设备上那组相邻字节。缓冲大小与块大小一致。每个缓冲有一个 buffer_head 类型的”缓冲区首部”描述符,内核操作缓冲前先看它。详细字段在第 15 章讲,本章只关心四个:b_page(包含缓冲的页框的页描述符地址)、b_data(页框在高内存时存缓冲在页内的偏移,否则存缓冲的起始线性地址)、b_blocknr(逻辑块号,即块在磁盘分区内的索引)、b_bdev(使用该缓冲的块设备)。

每次磁盘 I/O 操作就是在某些 RAM 位置与一些相邻扇区之间传输内容。几乎所有情况下传输都由磁盘控制器用 DMA 直接完成(第 13 章),块设备驱动只是发命令触发传输;传输完成后控制器发中断通知驱动。

一次 DMA 传输的数据必须属于磁盘上相邻的扇区——这是物理约束:允许 DMA 传非相邻扇区的控制器传输率会很差,因为移动磁头很慢。

老式控制器只支持”简单” DMA:每次传输的内存端必须物理连续。新式控制器还支持 scatter-gather(分散-聚集)DMA:一次传输可以涉及多个不相邻的内存区。此时驱动要发给控制器:

  • 起始磁盘扇区号和要传输的扇区总数;
  • 一份内存区描述符列表(每项一个地址一个长度)。

控制器负责整个传输——读操作时它从相邻磁盘扇区取数据,分散(scatter)到各个内存区里。

为了用上 scatter-gather DMA,驱动必须按为单位处理数据:一个段就是一个内存页(或页的一部分),包含一些相邻磁盘扇区的数据。一次 scatter-gather DMA 可以同时涉及多个段。注意块设备驱动不需要知道块、块大小、块缓冲的存在——即使上层把段看成一个包含多个块缓冲的页,驱动也不关心。

通用块层还能合并段:如果对应的页框恰好在 RAM 里连续、对应的磁盘数据也相邻,合并产生的大内存区叫物理段(physical segment)。在通过专用总线电路(IO-MMU,第 13 章)处理总线地址与物理地址映射的体系结构上,还有第三种合并,结果叫硬件段(hardware segment)。80×86 没有这种动态映射,本章假设硬件段总是等于物理段。

通用块层

通用块层处理系统中所有块设备的请求。借助它,内核可以轻松做到:

  • 把数据缓冲放在高端内存——只有 CPU 要访问数据时才把页框映射进内核线性地址空间,用完立刻解除映射;
  • 实现(需额外努力)**零拷贝(zero-copy)**模式——磁盘数据直接放进用户态地址空间,不先拷到内核内存;本质上 I/O 传输用的缓冲就是映射在进程用户态线性地址空间里的页框;
  • 管理逻辑卷——如 LVM(逻辑卷管理器)和 RAID(廉价磁盘冗余阵列):几个磁盘分区(甚至跨不同块设备)可以看成一个分区;
  • 发挥最新磁盘控制器的高级特性——大容量板载磁盘缓存、增强的 DMA 能力、板载 I/O 传输请求调度等。

bio 结构

通用块层的核心数据结构是bio——一个进行中的块设备 I/O 操作的描述符。每个 bio 本质上包含:一个磁盘存储区的标识符(起始扇区号和扇区数),以及一个或多个描述本次 I/O 涉及内存区的段。关键字段:

类型字段说明
sector_tbi_sector块 I/O 操作在磁盘上的起始扇区
struct bio *bi_next请求队列中下一个 bio 的链接
block_device *bi_bdev块设备描述符指针
unsigned longbi_flagsbio 状态标志
unsigned longbi_rwI/O 操作标志
unsigned shortbi_vcntbio 的 bio_vec 数组中的段数
unsigned shortbi_idxbio 的段数组中的当前索引
unsigned shortbi_phys_segments合并后 bio 的物理段数
unsigned shortbi_hw_segments合并后的硬件段数
unsigned intbi_size待传输的字节数
unsigned intbi_max_vecsbio 的 bio_vec 数组允许的最大段数
struct bio_vec *bi_io_vec指向 bio 的段数组
bio_end_io_t *bi_end_iobio 的 I/O 操作结束时调用的方法
atomic_tbi_cntbio 的引用计数
void *bi_private通用块层和驱动 I/O 完成方法使用的指针
bio_destructor_t *bi_destructorbio 被释放时调用的析构方法

每个段用 bio_vec 结构表示:

类型字段说明
struct page *bv_page段所在页框的页描述符指针
unsigned intbv_len段的长度(字节)
unsigned intbv_offset段数据在页框内的偏移

bio 的内容在 I/O 操作进行中会不断变化。比如驱动一次 scatter-gather DMA 传不完整个 bio 时,bi_idx 就会更新以记录尚未传输的第一个段。驱动可以用 bio_for_each_segment 宏从当前段(索引 bi_idx)开始遍历 bio 的所有段。

通用块层启动新 I/O 操作时调 bio_alloc() 分配新 bio。通常经 slab 分配器分配,内核还保留一小池 bio 备内存紧张时用(第 8 章”内存池”);bio_vec 结构也有专门的内存池——分配了 bio 却分配不出段描述符毫无意义。bio_put() 减少引用计数 bi_cnt,归零时释放 bio 和相关的 bio_vec。

表示磁盘和分区

磁盘是通用块层处理的一个逻辑块设备。通常对应一个硬件设备(硬盘、软盘、CD-ROM),但也可以是构建在多个物理分区之上的虚拟设备,甚至可以是住在 RAM 专用页里的存储区。不管哪种,上层组件都通过通用块层的服务以相同方式操作它。

磁盘用 gendisk 对象表示(关键字段):

类型字段说明
intmajor磁盘的主设备号
intfirst_minor关联的第一个次设备号
intminors关联的次设备号范围
char [32]disk_name磁盘的常规名(通常即设备文件名)
struct hd_struct **part磁盘的分区描述符数组
struct block_device_operations *fops块设备方法表
struct request_queue *queue磁盘的请求队列
void *private_data块设备驱动的私有数据
sector_tcapacity磁盘存储区大小(扇区数)
intflags描述磁盘类型的标志
struct device *driverfs_dev磁盘硬件设备的 device 对象
struct kobjectkobj内嵌 kobject

flags 里最重要的是 GENHD_FL_UP(置位表示磁盘已初始化、正在工作)和 GENHD_FL_REMOVABLE(可移动介质,如软盘、CD-ROM)。

fops 指向一张 block_device_operations 表,存放块设备关键操作的定制方法:

方法触发时机
open打开块设备文件
release关闭对块设备文件的最后一个引用
ioctl对块设备文件发 ioctl()(使用大内核锁)
compat_ioctl同上(不使用大内核锁)
media_changed检查可移动介质是否已更换(如软盘)
revalidate_disk检查块设备上是否还有有效数据

硬盘常被划分成逻辑分区。每个块设备文件可以代表整个磁盘或磁盘内的一个分区:比如主 EIDE 盘用主号 3、次号 0 的 /dev/hda 表示,它的前两个分区用主号 3、次号 1 和 2 的 /dev/hda1/dev/hda2 表示。一般地,一个磁盘内的分区用连续的次设备号

磁盘有分区时,分区布局保存在一个 hd_struct 数组里,地址存在 gendisk 的 part 字段,数组下标是分区在磁盘内的相对索引:

类型字段说明
sector_tstart_sect分区在磁盘内的起始扇区
sector_tnr_sects分区长度(扇区数)
struct kobjectkobj内嵌 kobject
unsigned intreads / read_sectors分区上的读操作数 / 读取的扇区数
unsigned intwrites / write_sectors分区上的写操作数 / 写入的扇区数
intpolicy1 表示分区只读
intpartno分区在磁盘内的相对索引

内核发现新磁盘时(启动阶段、可移动介质插入、外接磁盘挂上),调 alloc_disk() 分配并初始化新的 gendisk 对象(磁盘有分区时还有 hd_struct 数组),然后调 add_disk() 把新 gendisk 描述符插入通用块层的数据结构。

提交一个请求

假设数据在磁盘上相邻、内核已确定其物理位置,向通用块层提交 I/O 请求的常见步骤是:先 bio_alloc() 分配新 bio 并初始化关键字段——bi_sector(数据起始扇区号,分区设备上相对于分区起点)、bi_size(覆盖数据的扇区数)、bi_bdev(块设备描述符地址)、bi_io_vec/bi_vcnt(段数组及段数)、bi_rw(操作标志,最重要的是传输方向 READ(0)/WRITE(1))、bi_end_io(操作完成时执行的收尾过程地址)。

bio 初始化好后,内核调用 generic_make_request()——通用块层的主入口,它执行:

  1. 检查 bio->bi_sector 是否超过块设备的扇区数。超过则设 BIO_EOF 标志、打印内核错误信息、调 bio_endio()(更新 bio 的 bi_sizebi_sector 并调用 bi_end_io 方法)后终止。
  2. 取出块设备关联的请求队列 q——地址在块设备描述符的 bd_disk 字段里,而该描述符由 bio->bi_bdev 指向。
  3. block_wait_queue_running() 检查当前 I/O 调度器是否正在被动态替换;是则进程睡眠,直到新调度器启动。
  4. blk_partition_remap() 检查块设备是否是磁盘分区(bio->bi_bdev 不等于 bio->bi_dev->bd_contains)。是则从 bio->bi_bdev 取分区 hd_struct 描述符:按传输方向更新分区的读/写统计字段;把 bio->bi_sector 从”相对分区”换算成”相对整个磁盘”;把 bio->bi_bdev 改设为整个磁盘的块设备描述符。从此通用块层、I/O 调度器、设备驱动都忘了分区的存在,直接在整盘上工作。
  5. q->make_request_fn 方法把 bio 请求插入请求队列 q。
  6. 返回。

make_request_fn 的典型实现见”I/O 调度器”一节末尾。

I/O 调度器

虽然块设备驱动一次能传一个扇区,块 I/O 层不会为每个要访问的扇区单独发起一次 I/O——那样磁盘性能会很差,因为在磁盘表面定位一个扇区太费时间。内核尽可能把多个扇区聚成一组整体处理,从而减少磁头移动的平均次数。

当内核组件想读写磁盘数据时,它实际创建的是一个块设备请求(request)——描述所请求的扇区和操作类型(读或写)。但内核不会请求一创建就满足它:I/O 操作只是被”排期”,稍后执行。这个人为的延迟恰恰是块设备性能提升的关键机制:新请求到来时,内核检查能否通过稍微扩大一个还在等待的旧请求来满足它(即不用额外寻道)。由于磁盘访问趋于顺序化,这个简单机制非常有效。

推迟请求让块设备处理复杂化了。比如进程打开一个文件,文件系统要读对应的 inode:请求进队列,进程挂起等待传输。但块设备驱动本身不能被阻塞——否则所有访问同一磁盘的进程都会被卡住。所以每个 I/O 操作都异步处理:通用块层调 I/O 调度器创建或扩大请求后立即返回;稍后被激活的块设备驱动调用**策略例程(strategy routine)**选一个待处理请求,向磁盘控制器发命令满足它;I/O 完成时控制器发中断,中断处理程序必要时再次调用策略例程处理下一个请求。

每个块设备驱动维护自己的请求队列,存放该设备的待处理请求;控制器管多块磁盘时通常每块物理设备一个队列。调度在每个队列上独立进行。

请求队列描述符

请求队列用一个大大的 request_queue 结构表示(关键字段):

类型字段说明
struct list_headqueue_head待处理请求链表
struct request *last_merge队列中优先考虑合并的请求
elevator_t *elevator电梯对象
struct request_listrq用于分配请求描述符的数据结构
request_fn_proc *request_fn驱动策略例程的入口方法
merge_request_fn *back_merge_fn / front_merge_fn检查能否把 bio 合并到队列最后/最前一个请求
merge_requests_fn *merge_requests_fn尝试合并队列中两个相邻请求
make_request_fn *make_request_fn新请求要入队时调用
prep_rq_fn *prep_rq_fn构造发给硬件设备处理此请求的命令
unplug_fn *unplug_fn拔掉(unplug)块设备的方法
unsigned intnr_requests每个方向允许的最大待处理请求数
unsigned intnr_congestion_on / nr_congestion_off队列进入/退出拥塞的阈值

本质上请求队列是一条双向链表,元素是请求描述符;链表元素的具体排序方式由各驱动决定,但 I/O 调度器提供了几种预定义的排序法(见下)。backing_dev_info 字段是一个小对象,存放底层设备的 I/O 数据流信息,比如预读和请求队列拥塞状态。

请求描述符

每个待处理请求用 request 结构描述(关键字段):

类型字段说明
struct list_headqueuelist请求队列链表指针
unsigned longflags请求标志
sector_tsector下一个要传输的扇区号
unsigned longnr_sectors整个请求中尚待传输的扇区数
unsigned intcurrent_nr_sectors当前 bio 当前段中尚待传输的扇区数
struct bio *bio请求中第一个未完全传输的 bio
struct bio *biotail请求链表中最后一个 bio
void *elevator_privateI/O 调度器的私有数据
intrq_status请求状态(RQ_ACTIVE 或 RQ_INACTIVE)
struct gendisk *rq_disk请求引用的磁盘描述符
unsigned longstart_time请求起始时间(jiffies)
unsigned shortnr_phys_segments请求的物理段数
unsigned shortnr_hw_segments请求的硬件段数

每个请求由一个或多个 bio 组成。最初通用块层创建的请求只含一个 bio;之后 I/O 调度器可以”扩展”请求——当新数据与请求中已有数据物理相邻时,往原 bio 加段,或把另一个 bio 链进请求。bio 字段指向第一个 bio,biotail 指向最后一个;rq_for_each_bio 宏遍历请求的所有 bio。许多字段是动态变化的:某个 bio 的数据传完后 bio 字段指向下一个;新 bio 加到尾部时 biotail 也变;nr_sectorscurrent_nr_sectors 等随传输推进不断更新。

标志字段里最重要的是 REQ_RW(传输方向 READ(0)/WRITE(1)),其他还有:REQ_FAILFAST(出错不重试)、REQ_SOFTBARRIER/REQ_HARDBARRIER(作为调度器[和驱动]的屏障,必须晚于更老的请求、早于更新的请求处理)、REQ_CMD(普通读写传输)、REQ_NOMERGE(不得扩展或合并)、REQ_STARTED(正在处理)、REQ_QUEUED(可同时管理多个未完成传输的设备上的”带标签”请求)、REQ_PC/REQ_BLOCK_PC(含直发硬件的命令)、REQ_SPECIAL(特殊命令,如驱动器复位)等。

请求描述符的分配管理

高负载高磁盘活动下,空闲动态内存可能成为往队列加新请求的进程的瓶颈。每个 request_queue 内含一个 request_list 结构:请求描述符的内存池(第 8 章)、读/写两个方向的已分配计数器、读/写两个”最近分配失败”标志、读/写两个等待队列(睡等可用描述符的进程),以及一个等待队列被清空的队列。

blk_get_request() 尝试从给定队列的内存池拿空闲请求描述符;内存紧张且池耗尽时,要么让当前进程睡眠,要么——内核控制路径不能阻塞时——返回 NULL。成功则把队列的 request_list 地址存进请求描述符的 rl 字段。blk_put_request() 释放描述符,引用计数归零时归还内存池。

避免请求队列拥塞

每个队列有最大待处理请求数(nr_requests,默认每方向 128 个)。待处理读(写)请求超限时,队列被 QUEUE_FLAG_READFULLQUEUE_FLAG_WRITEFULL)标志标记为满,可阻塞的进程在 request_list 对应的等待队列里入睡。

塞满的队列对系统性能有害——它强迫许多进程睡眠等待 I/O 完成。所以待处理请求数超过 nr_congestion_on(默认 113)时,内核视队列为拥塞,设法放慢新请求的产生速率;降到 nr_congestion_off(默认 111)以下才解除拥塞。blk_congestion_wait() 让当前进程睡到任一队列解除拥塞或超时。

激活块设备驱动:插上与拔下

前面说过,推迟激活驱动能提高相邻块请求聚类的机会。这个延迟靠**设备插上(plugging)/拔下(unplugging)**技术实现:只要块设备驱动处于”插上”状态,即使队列里有请求等着,驱动也不被激活。

  • blk_plug_device() 把队列”插上”:在 q->queue_flags 里设 QUEUE_FLAG_PLUGGED 位,并重启 q->unplug_timer 内嵌动态定时器;
  • blk_remove_plug() 把队列”拔下”:清 QUEUE_FLAG_PLUGGED 标志、取消定时器。内核在”视野内”所有可合并请求都入队后可显式调用它;此外队列中待处理请求数超过 unplug_thres(默认 4)时 I/O 调度器也会拔下队列;
  • 设备持续插上 q->unplug_delay(通常 3 毫秒)后定时器到期,执行 blk_unplug_timeout(),唤醒服务 kblockd_workqueue 工作队列的 kblockd 内核线程(工作队列见第 4 章),它执行 q->unplug_work 里登记的 blk_unplug_work(),后者调用 q->unplug_fn 方法——通常实现为 generic_unplug_device():先确认队列仍处于活动状态,然后调 blk_remove_plug(),最后执行策略例程(request_fn 方法)开始处理队列中下一个请求。

I/O 调度算法:电梯

新请求入队时,通用块层调 I/O 调度器决定它在队列中的确切位置。调度器尽量让请求队列按扇区排序——顺序取队列元素处理时,磁头从内道到外道(或反向)线性移动而不是随机跳道,寻道量大幅降低。这个启发式让人想起电梯应对各楼层上下行请求的方式:朝一个方向移动,到达该方向最后一个”预订楼层”后才换向。因此 I/O 调度器也叫电梯(elevator)

但重负载下严格按扇区号排序并不好使:若驱动正在处理队列头部(低扇区号)的请求,而新请求源源不断带着低扇区号进来,队尾请求很容易饿死。所以调度算法相当讲究。所有算法都使用一个派发队列(dispatch queue)——按驱动处理顺序排好的请求集合,下一个被服务的请求永远是派发队列的第一个元素(它就是 request_queue 描述符中 queue_head 字段为根的请求队列);几乎所有算法还用额外的队列来分类排序请求,全部允许驱动往现有请求加 bio、必要时合并两个”相邻”请求。

Linux 2.6 提供四种调度器:Anticipatory(预期)Deadline(最后期限)CFQ(完全公平队列)Noop(无操作)。内核启动参数 elevator=<name>(as/deadline/cfq/noop)指定大多数块设备的默认调度器,不给参数则用 Anticipatory。驱动可以换掉默认电梯,甚至自定义算法(极少这么做)。管理员还能运行时改某块设备的调度器:往 /sys/block/hda/queue/scheduler 文件写电梯名即可(sysfs 见第 13 章)。请求队列使用的算法用 elevator_t 类型的电梯对象表示,地址存在队列的 elevator 字段;电梯对象包含覆盖所有操作的方法(链接/解除链接、加入/合并/移出请求、取下一个请求等)。每个请求描述符还有一个 elevator_private 字段指向调度器处理该请求的附加数据结构。

提醒一句:设计 I/O 调度器如同设计 CPU 调度器(第 7 章)——启发式规则和常数值都是大量测试与基准测量的产物。下面从最简单到最复杂过一遍四种算法。

Noop 电梯:最简单。没有排序队列,新请求永远加在派发队列的头或尾,下一个处理的永远是队列第一个请求。适合完全不需要调度优化(或设备自带智能调度)的场景。

CFQ(Complete Fairness Queueing,完全公平队列)电梯:首要目标是在触发 I/O 请求的所有进程之间公平分配磁盘带宽。它用大量(默认 64 个)排序队列存放来自不同进程的请求:请求交给电梯时,内核用哈希函数把当前进程的线程组标识符(通常即 PID,第 3 章)换成队列下标,把请求插到该队列尾部——同进程的请求永远进同一个队列。补充派发队列时,电梯按轮转方式扫描输入队列,选中第一个非空队列,把一批请求移到派发队列尾部。

Deadline(最后期限)电梯:除派发队列外还用 4 个队列:两个排序队列分别按起始扇区号存放读写请求;两个最后期限队列存放同样的请求、但按”最后期限”排序。期限机制专门对付饥饿——调度策略长期冷落某个请求、偏爱离上次服务位置更近的其他请求。请求的最后期限本质是一个 expire 定时器,请求交给电梯时开始计时;默认读请求 500 毫秒、写请求 5 秒——读请求优先,因为它们通常阻塞着发起它们的进程。补充派发队列时:先定下一个请求的数据方向(读写都有就选”读”,除非”写”方向被冷落太多次——防写请求饥饿);然后查该方向的期限队列:若队首请求已过期,把它移到派发队列尾部,并从排序队列里紧跟它的请求起再带一批过去(请求在磁盘上物理相邻时批次更长,否则更短);若没有过期的,就从排序队列里上次取走位置的下一条开始派发一批;游标走到排序队列尾部再从头开始(“单程电梯”)。

Anticipatory(预期)电梯:最复杂精致,本质是 Deadline 的进化版:同样两个期限队列、两个排序队列,调度器交替扫描读写请求但偏爱读请求(默认读请求过期时间 125 毫秒、写请求 250 毫秒),扫描基本是顺序的、除非有请求过期。它额外增加了两个启发式:

  • 有时电梯会选排序队列中位于当前位置之前的请求,迫使磁头向后寻道——典型情形是该请求的寻道距离小于当前位置之后请求寻道距离的一半;
  • 电梯收集每个进程 I/O 操作模式的统计。刚派发了进程 P 的一个读请求后,若排序队列中下一个请求也来自 P,立即派发;否则电梯查统计:若判断 P 很快还会发读请求,就停顿一小段时间(默认约 7 毫秒),预期接收 P 即将发出的、在磁盘上”邻近”的读请求。

把请求交给调度器:__make_request()

前面”提交一个请求”一节里,generic_make_request() 调用队列的 make_request_fn 方法把请求传给调度器。这个方法通常由 __make_request() 实现,接收请求队列描述符 q 和 bio 描述符 bio,执行:

  1. blk_queue_bounce() 设置回弹缓冲(bounce buffer,见下文)。若创建了回弹缓冲,后续操作都针对它而非原 bio。
  2. elv_queue_empty() 检查队列里有没有待处理请求——注意派发队列可能为空而调度器的其他队列仍有请求。没有则调 blk_plug_device() 插上队列,跳第 5 步。
  3. 队列有待处理请求。调 elv_merge() 检查新 bio 能否并入现有请求,可能返回三个值:
    • ELEVATOR_NO_MERGE:不能并入,跳第 5 步;
    • ELEVATOR_BACK_MERGE:可作为某请求 req 的最后一个 bio——调 q->back_merge_fn 确认请求可扩展后,把 bio 插到 req 链表尾部并更新字段,再尝试与后一个请求合并(新 bio 可能正好填上两个请求之间的洞);
    • ELEVATOR_FRONT_MERGE:可作为某请求的第一个 bio——调 q->front_merge_fn 确认后插到 req 链表头部并更新字段,再尝试与前一个请求合并。
  4. bio 已并入现有请求,跳第 7 步。
  5. bio 必须放进新请求:分配新的请求描述符。若内存不足则挂起当前进程——除非 bio->bi_rw 里设了 BIO_RW_AHEAD 标志(表示这是预读操作,第 16 章),此时调 bio_endio() 后终止,数据传输放弃执行。
  6. 初始化请求描述符字段:按 bio 内容填扇区号、当前 bio、当前段等;设 REQ_CMD 标志(普通读写);第一个段的页框在低内存时把 buffer 字段设为该缓冲的线性地址;rq_disk 设为 bio->bi_bdev->bd_disk;把 bio 插入请求链表;start_time 设为 jiffies。
  7. 完成前检查 bio->bi_rwBIO_RW_SYNC 标志:设了就对请求队列调 generic_unplug_device() 拔下驱动。
  8. 终止。

如果调用 __make_request() 前队列非空,那么它要么已拔下、要么很快会拔下——每个插上且有请求的队列都有正在计时的 unplug 定时器;队列原本为空则被它插上。不管怎样,或早(BIO_RW_SYNC 置位时函数返回前)或晚(最坏情形定时器到期),队列终将被拔下,块设备驱动的策略例程终将处理派发队列里的请求。

blk_queue_bounce():回弹缓冲

blk_queue_bounce() 检查 q->bounce_gfp 标志和 q->bounce_pfn 阈值,判断是否需要回弹缓冲——当请求中的某些缓冲位于高端内存而硬件设备无法寻址它们时。

老式 ISA 总线 DMA 只能处理 24 位物理地址,此时回弹阈值设为 16 MB(页框号 4096)。不过块设备驱动对老设备通常不用回弹,而是直接把 DMA 缓冲分配在 ZONE_DMA 区。

如果设备应付不了高端内存,函数检查 bio 中是否真有需要回弹的缓冲,有就复制一份 bio 描述符(创建回弹 bio),然后对每个页框号不小于 q->bounce_pfn 的段:在 ZONE_NORMAL 或 ZONE_DMA 分配一个新页框;把回弹 bio 中该段的 bv_page 指向新页框描述符;若是写操作,调 kmap() 把高端内存页临时映射进内核地址空间、拷贝到低内存页、再 kunmap() 解除映射。最后设 BIO_BOUNCED 标志、初始化专门的 bi_end_io 方法、把原 bio 指针存进 bi_private。回弹 bio 的传输结束时,bi_end_io 方法把数据拷回高端内存缓冲(仅读操作)并释放回弹 bio。

常见坑:为什么磁盘慢?

很多人以为磁盘慢在”传输”,其实慢在寻道——磁头移动是机械动作,毫秒级;数据传输一旦开始可高达几十 MB/s。所以内核所有优化(请求合并、电梯排序、plug/unplug 延迟)本质上都在做同一件事:减少寻道次数、让磁头尽量顺序移动。理解了这一点,四种电梯算法的差异就只是”用哪种策略防饥饿、保公平”而已。

块设备驱动

块设备驱动是 Linux 块子系统的最底层组件:从 I/O 调度器拿到请求,做一切必要的事处理它们。

驱动当然集成在第 13 章的设备驱动模型里:每个驱动对应一个 device_driver 描述符,驱动的每块磁盘关联一个 device 描述符。但这些描述符太通用,块 I/O 子系统还得为每个块设备存额外的信息。

块设备

一个驱动可以处理多个块设备——比如 IDE 驱动管好几块 IDE 盘,每块盘是一个独立的块设备;每块盘通常还分区,每个分区也可以看成一个逻辑块设备。驱动必须照料所有对这些块设备的设备文件发出的 VFS 系统调用。

每个块设备用 block_device 描述符表示(关键字段):

类型字段说明
dev_tbd_dev块设备的主从设备号
struct inode *bd_inodebdev 文件系统中关联文件的 inode
intbd_openers块设备被打开的次数计数
struct semaphorebd_sem保护块设备打开/关闭的信号量
struct semaphorebd_mount_sem禁止在块设备上新挂载的信号量
struct list_headbd_inodes已打开设备文件 inode 链表头
void *bd_holder块设备描述符的当前持有者
intbd_holdersbd_holder 被多次设置的计数
struct block_device *bd_contains若本设备是分区,指向整盘的描述符;否则指向自身
unsignedbd_block_size块大小
struct hd_struct *bd_part分区描述符(非分区则为 NULL)
unsignedbd_part_count本设备包含的分区被打开的次数
intbd_invalidated需要读取分区表时置位
struct gendisk *bd_disk底层磁盘的 gendisk 结构
struct list_head *bd_list块设备描述符链表指针

所有 block_device 描述符插在一条全局链表里(表头 all_bdevs 变量,链接指针在 bd_list 字段)。

描述符指分区时,bd_contains 指向整盘的描述符,bd_part 指向 hd_struct 分区描述符;指整盘时,bd_contains 指向自身,bd_part_count 记录磁盘上分区被打开的次数。

bd_holder 存一个线性地址,代表块设备的持有者。持有者不是执行 I/O 传输的驱动,而是使用该设备并拥有独占特殊权限的内核组件(比如可自由使用描述符的 bd_private 字段)——典型持有者是挂在其上的文件系统;另一常见情形是以独占方式打开块设备文件时,持有者是相应的 file 对象。bd_claim() 设置 bd_holderbd_release() 清回 NULL。同一组件可以多次 bd_claim(),每次递增 bd_holders;要释放设备就得相应次数地 bd_release()

lk14_03 图 4:块设备描述符与块子系统其他主要数据结构的链接关系

访问一个块设备

内核收到打开块设备文件的请求时,首先要判断设备文件是否已经打开——已打开的话不能新建描述符,而应更新既有的。麻烦在于:主从号相同、路径不同的块设备文件被 VFS 看成不同的文件,尽管它们指同一设备。所以不能简单靠 inode 缓存里有没有对象来判断设备是否在用。

主从号与块设备描述符的对应关系通过 bdev 特殊文件系统(第 12 章)维护:每个块设备描述符配一个 bdev 特殊文件,描述符的 bd_inode 字段指向对应 inode;反过来该 inode 既编码块设备的主从号、又编码对应描述符的地址。bdget() 接收主从号:在 bdev 文件系统里找关联 inode,不存在就分配新 inode 和新描述符;无论如何返回对应描述符的地址。

找到描述符后,内核检查 bd_openers 字段判断设备是否在用(为正表示在用——可能通过另一个设备文件)。内核还维护已打开设备文件的 inode 链表(根在 bd_inodes 字段,inode 对象的 i_devices 字段存链接指针)。

驱动注册与初始化八步曲

下面用自定义驱动 foo 走一遍建立块设备驱动的主要步骤(第 13 章讲过的通用注册步骤略去;块设备通常属于 PCI、SCSI 这类标准总线,内核辅助函数顺带就完成了驱动模型注册)。

第一步:定义自定义驱动描述符。

struct foo_dev_t {
    [...]
    spinlock_t lock;
    struct gendisk *gd;
    [...]
} foo;

描述符存放驱动硬件所需的信息:编程设备用的 I/O 端口、设备中断的 IRQ 线、设备内部状态等。lock 自旋锁保护 foo 的字段,其地址常传给内核辅助函数,从而保护驱动专属的块 I/O 子系统数据结构;gd 指向代表驱动所管整块磁盘的 gendisk 描述符。

第二步:保留主设备号。

err = register_blkdev(FOO_MAJOR, "foo");
if (err) goto error_major_is_busy;

与第 13 章的 register_chrdev() 类似:保留主设备号 FOO_MAJOR 并关联名字 foo。注意:没有 register_chrdev_region() 的对应物——不能分配次号子区间;保留的主号与驱动数据结构之间也不建立链接register_blkdev() 唯一可见的效果是在 /proc/devices 特殊文件的已注册主号列表里加一项。

第三步:初始化自定义描述符。

spin_lock_init(&foo.lock);
foo.gd = alloc_disk(16);
if (!foo.gd) goto error_no_gendisk;

初始化自旋锁,然后分配磁盘描述符。gendisk 结构对块 I/O 子系统至关重要,它引用许多其他数据结构。alloc_disk() 还分配磁盘的分区描述符数组,参数是数组中 hd_struct 元素的个数——16 意味着驱动可支持最多含 15 个分区的磁盘(分区 0 不用)。

第四步:初始化 gendisk 描述符。

foo.gd->private_data = &foo;
foo.gd->major = FOO_MAJOR;
foo.gd->first_minor = 0;
foo.gd->minors = 16;
set_capacity(foo.gd, foo_disk_capacity_in_sectors);
strcpy(foo.gd->disk_name, "foo");
foo.gd->fops = &foo_ops;

foo 描述符的地址存进 gendisk 的 private_data,这样被块 I/O 子系统当方法调用的底层驱动函数能立刻找到驱动描述符——驱动同时管多块盘时效率尤其重要。set_capacity() 用 512 字节扇区数初始化 capacity 字段——这个值一般靠探测硬件、询问磁盘参数得到。

第五步:初始化块设备方法表。 fops 指向自定义的 block_device_operations 表。如果设备支持可移动磁盘,通用块层会调 media_changed 方法检查自上次挂载/打开后磁盘是否更换——通常靠向硬件控制器发底层命令,实现必然是驱动专属的。ioctl 方法只在通用块层不认识某个 ioctl 命令时被调——典型是查询磁盘几何参数(柱面数、磁道数、扇区数、磁头数),实现也是驱动专属的。

第六步:分配并初始化请求队列。

foo.gd->rq = blk_init_queue(foo_strategy, &foo.lock);
if (!foo.gd->rq) goto error_no_request_queue;
blk_queue_hardsect_size(foo.gd->rd, foo_hard_sector_size);
blk_queue_max_sectors(foo.gd->rd, foo_max_sectors);
blk_queue_max_hw_segments(foo.gd->rd, foo_max_hw_segments);
blk_queue_max_phys_segments(foo.gd->rd, foo_max_phys_segments);

blk_init_queue() 分配请求队列描述符、按默认值初始化大多数字段;参数是驱动自旋锁地址(存进 queue_lock 字段)和策略例程地址(存进 request_fn 字段)。它还初始化 elevator 字段,强制驱动先用默认调度算法;驱动想换电梯可以事后覆盖该字段。随后的辅助函数按驱动特性设置队列的硬件扇区大小、单请求最大扇区数、最大硬件/物理段数等字段。

第七步:设置中断处理程序。 按第 4 章”I/O 中断处理”所述为设备注册 IRQ 线:

request_irq(foo_irq, foo_interrupt,
SA_INTERRUPT|SA_SHIRQ, "foo", NULL);

foo_interrupt() 是设备的中断处理程序,特点见下文。

第八步:注册磁盘。 最后执行:

add_disk(foo.gd);

add_disk() 接收 gendisk 描述符地址,执行:置 gd->flagsGENHD_FL_UP 标志;调 kobj_map() 建立驱动与设备主号及其次号区间的链接(注意这次 kobject 映射域是 bdev_map 变量);把 gendisk 内嵌的 kobject 注册进设备驱动模型(如 /sys/block/foo);扫描磁盘分区表,为每个找到的分区初始化 foo.gd->part 数组中对应的 hd_struct 描述符并注册进驱动模型(如 /sys/block/foo/foo1);把请求队列描述符内嵌的 kobject 也注册进去(如 /sys/block/foo/queue)。

add_disk() 一返回,驱动就开始工作了。初始化函数收工,策略例程和中断处理程序接管 I/O 调度器传来的每个请求。

策略例程

**策略例程(strategy routine)**是驱动中与硬件块设备交互、满足派发队列中请求的函数(或一组函数),通过请求队列描述符的 request_fn 方法调用(例中的 foo_strategy()),I/O 调度器层把请求队列描述符地址 q 传给它。它通常在”往空队列插入新请求”之后被启动;激活后应处理队列中的所有请求,队列空了才终止。

朴素实现是:逐个取出请求、与控制器交互、干等传输完成、再取下一个。这不高效——即使有 DMA,策略例程也必须挂起自己等 I/O 完成(意味着它得跑在专用内核线程上,总不能惩罚无关的用户进程吧?),而且没法支持能同时处理多个 I/O 传输的现代磁盘控制器。

所以大多数驱动采用中断驱动策略:

  • 策略例程为队列第一个请求启动一次数据传输,把控制器设置成传输完成时发中断,然后立即返回
  • 控制器发中断时,中断处理程序再次调用策略例程(常直接调用,有时通过激活工作队列):或者为当前请求启动下一轮传输;或者——请求的数据全部传完——把请求从派发队列摘掉,开始处理下一个请求。

请求可由多个 bio 组成,bio 又可由多个段组成。驱动用 DMA 的两种方式:为请求中每个 bio 的每个段分别设置一次 DMA 传输;或用一次 scatter-gather DMA 服务请求中所有 bio 的所有段。策略例程的最终设计取决于控制器的特性——每台物理设备都与众不同(比如软盘驱动把块按磁道分组、一次 I/O 传整个磁道),对”驱动该怎么服务请求”做一般性假设没有意义。

例中的 foo_strategy() 可以这么做:

  1. 调调度器辅助函数 elv_next_request() 从派发队列取当前请求;队列为空则返回:
req = elv_next_request(q);
if (!req) return;
  1. 执行 blk_fs_request 宏检查请求的 REQ_CMD 标志——是否普通读写操作:
if (!blk_fs_request(req))
    goto handle_special_request;
  1. 若控制器支持 scatter-gather DMA,编程控制器一次传输整个请求的数据、传输完成时发中断。blk_rq_map_sg() 辅助函数返回可直接用来启动传输的 scatter-gather 列表。

  2. 否则驱动必须逐段传输。策略例程执行 rq_for_each_biobio_for_each_segment 宏遍历 bio 列表及每个 bio 内的段列表:

rq_for_each_bio(bio, rq)
bio_for_each_segment(bvec, bio, i) {
    /* 传输第 i 个段 bvec */
    local_irq_save(flags);
    addr = kmap_atomic(bvec->bv_page, KM_BIO_SRC_IRQ);
    foo_start_dma_transfer(addr + bvec->bv_offset, bvec->bv_len);
    kunmap_atomic(bvec->bv_page, KM_BIO_SRC_IRQ);
    local_irq_restore(flags);

待传数据可能在高端内存,所以需要 kmap_atomic()/kunmap_atomic()foo_start_dma_transfer() 编程硬件设备启动 DMA 传输、完成时发中断。

  1. 返回。

中断处理程序

块设备驱动的中断处理程序在 DMA 传输结束时被激活。它检查请求中的数据是否全部传完:传完就调策略例程处理派发队列的下一个请求;否则更新请求描述符字段,调策略例程继续剩余传输。典型片段:

irqreturn_t foo_interrupt(int irq, void *dev_id, struct pt_regs *regs)
{
    struct foo_dev_t *p = (struct foo_dev_t *) dev_id;
    struct request_queue *rq = p->gd->rq;
    [...]
    if (!end_that_request_first(rq, uptodate, nr_sectors)) {
    blkdev_dequeue_request(rq);
    end_that_request_last(rq);
    }
    rq->request_fn(rq);
    [...]
    return IRQ_HANDLED;
}

结束一个请求的活分给两个函数。end_that_request_first() 接收请求描述符、指示 DMA 是否成功完成的标志、本次 DMA 传输的扇区数(end_that_request_chunk() 类似,但收字节数)。它扫描请求中的 bio 和每个 bio 内的段,更新请求描述符字段:把 bio 指向请求中第一个未完成的 bio;把未完成 bio 的 bi_idx 指向第一个未完成的段;把未完成段的 bv_offsetbv_len 改为尚待传输的数据。对每个完全传完的 bio 调 bio_endio()。若请求的所有数据都传完了返回 0,否则返回 1。

返回 1 时,中断处理程序重启策略例程继续处理同一请求;返回 0 时,处理程序把请求从队列摘除(通常用 blkdev_dequeue_request())、调用 end_that_request_last()、重启策略例程处理下一个请求。end_that_request_last() 更新磁盘使用统计、把请求描述符从 rq->elevator 调度器的派发队列移除、唤醒所有睡等该请求完成的对象、释放描述符。

通关标准

能顺着一次 read() 讲清五层组件(VFS→映射层→通用块层→I/O 调度器→驱动)各自干什么;能说清 bio、request、gendisk、block_device 四个结构的关系;能解释 plug/unplug 的意义和四种电梯算法防饥饿的手段。

打开块设备文件

本章以描述 VFS 打开块设备文件的步骤收尾。

内核在三种情况下打开块设备文件:文件系统挂载到磁盘或分区上、交换分区被激活、用户态进程对块设备文件发 open()。所有情况下内核做的事本质相同:找到块设备描述符(设备未在使用则可能新分配一个),并为即将到来的数据传输设置文件操作方法。

第 13 章讲过,dentry_open() 在打开设备文件时定制 file 对象的方法。这里 file 对象的 f_op 被设为 def_blk_fops 表的地址:

方法函数
openblkdev_open()
releaseblkdev_close()
llseekblock_llseek()
readgeneric_file_read()
writeblkdev_file_write()
aio_readgeneric_file_aio_read()
aio_writeblkdev_file_aio_write()
mmapgeneric_file_mmap()
fsyncblock_fsync()
ioctlblock_ioctl()
compat-ioctlcompat_blkdev_ioctl()
readvgeneric_file_readv()
writevgeneric_file_write_nolock()
sendfilegeneric_file_sendfile()

这里只关心 open 方法。blkdev_open() 接收 inode 和 filp 两个对象地址,执行:

  1. 执行 bd_acquire(inode) 取得块设备描述符地址 bdev。这个函数:先查 inode 对象的 i_bdev 字段——非 NULL 说明该设备文件已打开过(字段存着对应描述符地址),增加关联 bdev inode 的使用计数后直接返回该地址;否则调 bdget(inode->i_rdev) 按设备文件的主从号取描述符(不存在则分配;注意描述符可能已存在——比如设备正通过另一个设备文件被访问)。把描述符地址存进 inode->i_bdev 加速以后的打开操作;把 inode->i_mapping 设为 bdev inode 的对应字段(指向 address_space 对象的指针,第 15 章讲);把 inode 插入 bdev->bd_inodes 根的已打开 inode 链表;返回描述符地址。
  2. filp->i_mapping 设为 inode->i_mapping 的值。
  3. 取该块设备的 gendisk 描述符地址:disk = get_gendisk(bdev->bd_dev, &part)。若打开的是分区,part 局部变量返回分区索引,否则为 0。get_gendisk() 只是拿主从号在 bdev_map kobject 映射域上调 kobj_lookup()
  4. bdev->bd_openers 不为零(设备已打开过):检查 bdev->bd_contains——等于 bdev 则是整盘:如有定义则调 bdev->bd_disk->fops->open 块设备方法,再检查 bdev->bd_invalidated 字段、必要时调 rescan_partitions();不等于 bdev 则是分区:递增 bdev->bd_contains->bd_part_count。然后跳第 8 步。
  5. 设备首次被访问:把 bdev->bd_disk 初始化为 gendisk 描述符地址 disk。
  6. 若是整盘(part 为 0):如有定义执行 disk->fops->open 方法(驱动定义的”最后一分钟”定制初始化);从 disk->queue 请求队列的 hardsect_size 字段取扇区字节数,设置 bdev->bd_block_sizebdev->bd_inode->i_blkbits,并用 disk->capacity 算出磁盘大小设进 bdev->bd_inode->i_size;若 bdev->bd_invalidated 置位,调 rescan_partitions() 扫描分区表、更新分区描述符(该标志由只适用于可移动设备的 check_disk_change 块设备方法置位)。
  7. 若是分区(part 非零):再次调 bdget()——这次传 disk->first_minor——取得整盘的块设备描述符地址 whole;对整盘描述符重复第 3–6 步(必要时初始化它);把 bdev->bd_contains 设为整盘描述符地址;递增 whole->bd_part_count;把 bdev->bd_part 设为 disk->part[part-1](分区的 hd_struct 描述符地址),并执行 kobject_get(&bdev->bd_part->kobj) 递增分区引用计数;同第 6 步设置分区的大小和扇区大小相关 inode 字段。
  8. 递增 bdev->bd_openers
  9. 若设备文件以独占模式打开(filp->f_flagsO_EXCL 置位),调 bd_claim(bdev, filp) 设置持有者;失败(设备已有持有者)则释放描述符并返回 -EBUSY
  10. 返回 0(成功)。

blkdev_open() 结束后,open() 系统调用照常继续。此后对该文件的每个系统调用都触发默认块设备文件操作之一——正如第 16 章将看到的,块设备的每次数据传输实际上都是通过向通用块层提交请求来实现的。