一. 概述

本节开头还是先简要回顾一下linux IO栈。当对文件进行读写时，Page Cache或Direct IO层负责产生数据的IO请求，此时需要IO的数据保存在内存中，使用struct bio进行描述，随后映射层负责找到数据在磁盘中的位置，将此位置告诉通用层，如图1.1中所示。

图7.1 linux IO stack

二. 块设备数据结构

内核需要处理各式各样的块设备，通用块设备层抽象出所有块设备的公共特征，描述了一种逻辑上的块设备。通用层有3个关键的数据结构，他们之间的关系如图7.2所示，1）gendisk表示一个真正的物理磁盘，除了自身设备号、分区设备号等信息外，其中最重要的信息是一个分区表和一个请求队列，分区表是一个hd_struct指针数组；2）hd_struct描述一个分区的物理信息，包括起始扇区和总扇区数目，以及一些统计信息；3）block_device描述一个逻辑分区（或称为文件卷），每个block_device都与/dev中的一个块设备文件对应，因此不管是物理磁盘还是逻辑分区都有一个block_device，各逻辑分区的bd_contains指向物理盘的bd_contains，各分区的bd_disk字段指向gendisk，各分区的bd_part字段指向其对应的分区信息hd_struct。这部分内容基于一些默认的常识：1）同一个物理设备的逻辑分区的从设备号依次排布，并且第一个从设备号代表物理设备；2）LBA扇区编码队则中，第一个维度是柱面号，既，一段相邻的扇区号位于同一柱面。

图7.2 通用块层各数据结构之间的关系

三. 处理IO请求

3.1 请求的数据结构

磁盘处理读写请求的模型是：当CPU发起读写请求之后，由DMA负责异步完成该请求，一次请求的数据在磁盘上必须连续，但在内存中却可以分散到各个页中，将一个页中的数据作为一个段。用bio_vec结构来表示一个段，该结构包含页的struct page以及数据在页中的起始和长度，所以每次请求都使用一个bio结构来表示，它记录了一次请求中内存中数据在磁盘上的位置，其核心成员包括bi_sector记录请求的起始扇区；bi_io_vec记录bio_vec链表；bi_flags记录读写命令。

@ /include/linux/boi.h
struct bio {
    sector_t        bi_sector;  //该请求的起始扇区
    struct bio      *bi_next;   // 同一请求中的bio链
    struct block_device *bi_bdev;
    unsigned long       bi_flags;   // status, command, etc
    unsigned long       bi_rw;      //请求的读写方向 READ/WRITE,

    unsigned short      bi_vcnt;    //该bio分散在多少页中
    unsigned short      bi_idx; // current index into bvl_vec 
    struct bio_vec      *bi_io_vec; //bio_vec链表，核心结构
    atomic_t        bi_cnt;     /* pin count */
    void            *bi_private;
};

通用层会对上层发来的请求进行合并和排序，多个相邻的bio会被合并到一个struct request中，struct request也是向设备驱动程序发送IO请求的单位。上一节提到，每个gendisk有一个请求链表，该设备的所有未处理请求都被放到该链表上，queuelist字段负责这个链表。nr_sectors表示提交扇区的总数目，current_nr_sectors表示当前bio的扇区数目，hard_sector、 hard_cur_sectors与结构中没有hard_前缀的对应成员语义相同，通常两组变量的值相同，但在使用RAID时可能会有差别。bio链表的链表头记录在struct bio *bio中，链表尾记录在struct bio *biotail中。最后， 所有等待该数据的进程在struct completion *waiting上挂起。

@ /include/linux/blkdev.h
struct request {
    struct list_head queuelist; 
    unsigned long flags;          // 请求的命令
    sector_t sector;              // 下一个要提交的扇区号
    unsigned long nr_sectors;    //提交扇区的总数目
    unsigned int current_nr_sectors; //当前bio的扇区数目

    struct bio *bio;                      // bio链表头
    struct bio *biotail;                 // bio链表尾
    void *elevator_private;         // 用于IO调度算法
    struct gendisk *rq_disk;       // 请求所属的gendisk

    int tag;
    char *buffer;
    request_queue_t *q;
    struct request_list *rl;
    struct completion *waiting;  // 等待该数据的进程在此挂起
    unsigned int timeout;
};

3.2 请求入队

在开始后两节的讨论之前，需要明确几个概念：1）请求队列有两个状态，阻塞状态（plug）下队列只进不出，只能向队列提交新的请求，但新的请求不会得到执行，排空状态（drain）下，队列只出不进，此时驱动程序正在处理队列中已有的请求，但是新的请求不能提交，需要阻塞等待；2）请求是按照逻辑分区而不是物理磁盘提交的，所以提交入队分为两个阶段，第一个阶段为逻辑分区中的提交函数，主要检查请求是否位于该分区内，并将逻辑扇区号转换为物理扇区号，第二阶段为物理设备的提交函数，负责真正的请求提交。
submit_bio负责根据传递的bio实例创建一个新请求，它实际上调用generic_make_request完成核心功能。该函数首先检查请求的扇区是否位于该分区内，随后检查队列是否处于排空状态（drain），如果是则阻塞请求的提交。最后，将逻辑分区中的扇区号转换成物理设备中的扇区号，调用物理设备的make_request_fn完成真正的提交。

@ /drivers/block/ll_rw_blk.c
void generic_make_request(struct bio *bio)
{
    // ......判断请求的扇区是否位于该分区内
    do {
        q = bdev_get_queue(bio->bi_bdev);
end_io:
        bio_endio(bio, bio->bi_size, -EIO);
        break;
        // 如果该队列处于排空（drain）状态，则该进程需要阻塞等待
        block_wait_queue_running(q);
        // 将逻辑分区中的扇区号转换成物理设备中的扇区号
        blk_partition_remap(bio);
        //调用物理设备的make_request_fn
        ret = q->make_request_fn(q, bio);
    } while (ret);
}

__make_request函数负责将新的bio请求插入请求队列中，该函数首先检查是否为空，若为空则代表之前的请求已经处理完成，将队列设为阻塞状态接收新的请求。随后尝试将新请求合并到原有请求上，如果合并成功就可以准备退出该函数。如果合并不超过，则准备构建一个请求，先获取新请求需要的存储空间，然后为新请求赋值，最后调用add_request将新请求添加到调度队列中，该功能由调度算法提供，新请求可能不直接插入调度队列，而是先插入调度算法的私有队列中，等到该请求可以执行时再插入调度队列。

@ /drivers/block/ll_rw_blk.c
static int __make_request(request_queue_t *q, struct bio *bio)
{
again:    // 检查队列是否为空，若空，将队列设为阻塞状态
    if (elv_queue_empty(q)) {
        blk_plug_device(q);
        goto get_rq;
    }
    //尝试将新请求合并到原有请求上
    el_ret = elv_merge(q, &req, bio);
    switch (el_ret) {
        case ELEVATOR_BACK_MERGE:
        case ELEVATOR_FRONT_MERGE:
        case ELEVATOR_NO_MERGE:
    }

get_rq:    // 获取新请求需要的存储空间
    if (freereq) {
        req = freereq;
        freereq = NULL;
    } else {
        if ((freereq = get_request(q, rw, GFP_ATOMIC)) == NULL) {
            freereq = get_request_wait(q, rw);
        }
        goto again;
    }
    // 为新请求赋值
    req->hard_sector = req->sector = sector;
    // 将新请求添加到调度队列及调度算法的私有队列中
    add_request(q, req);
out:
    if (bio_sync(bio))
        __generic_unplug_device(q);
    return 0;
end_io:
    bio_endio(bio, nr_sectors << 9, err);
    return 0;
}

3.3 请求出队

前文提到，为了请求的重排序与合并，队列有两个状态，阻塞状态（plug）和排空状态（drain）。当队列处于阻塞状态（plug）时，需要定时的切换到排空状态（drain）排空请求。有两个条件可以出发状态切换：1）时间，进入阻塞状态时，blk_plug_device函数会设置一个时钟，其默认值为3ms，时钟到时后，队列将自动切换到排空状态（drain）2）已积攒请求的数量，如果当前读写请求的数目达到unplug_thresh指定的阈值，则切换状态，使等待的请求得到处理。

三. 处理IO请求

IO调度程序又称为电梯算法，所有这类算法的目的都是减少磁盘的寻道时间（因为磁盘的寻道是机械运动，速度非常慢），其名称来源于Linux 0.11中使用的Linus电梯算法，该算法向电梯搭载乘客的顺序一样处理IO请求，该算法可以最大化磁盘的吞吐，但会带来严重的饿死问题。针对该问题，2.6版本中，在Linus电梯算法的基础上提出了4中电梯算法。