一. 概述

本節(jié)開頭還是先簡要回顧一下linux IO棧。當(dāng)對文件進行讀寫時，Page Cache或Direct IO層負(fù)責(zé)產(chǎn)生數(shù)據(jù)的IO請求，此時需要IO的數(shù)據(jù)保存在內(nèi)存中，使用struct bio進行描述，隨后映射層負(fù)責(zé)找到數(shù)據(jù)在磁盤中的位置，將此位置告訴通用層，如圖1.1中所示。

圖7.1 linux IO stack

二. 塊設(shè)備數(shù)據(jù)結(jié)構(gòu)

內(nèi)核需要處理各式各樣的塊設(shè)備，通用塊設(shè)備層抽象出所有塊設(shè)備的公共特征，描述了一種邏輯上的塊設(shè)備。通用層有3個關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)，他們之間的關(guān)系如圖7.2所示，1）gendisk表示一個真正的物理磁盤，除了自身設(shè)備號、分區(qū)設(shè)備號等信息外，其中最重要的信息是一個分區(qū)表和一個請求隊列，分區(qū)表是一個hd_struct指針數(shù)組；2）hd_struct描述一個分區(qū)的物理信息，包括起始扇區(qū)和總扇區(qū)數(shù)目，以及一些統(tǒng)計信息；3）block_device描述一個邏輯分區(qū)（或稱為文件卷），每個block_device都與/dev中的一個塊設(shè)備文件對應(yīng)，因此不管是物理磁盤還是邏輯分區(qū)都有一個block_device，各邏輯分區(qū)的bd_contains指向物理盤的bd_contains，各分區(qū)的bd_disk字段指向gendisk，各分區(qū)的bd_part字段指向其對應(yīng)的分區(qū)信息hd_struct。這部分內(nèi)容基于一些默認(rèn)的常識：1）同一個物理設(shè)備的邏輯分區(qū)的從設(shè)備號依次排布，并且第一個從設(shè)備號代表物理設(shè)備；2）LBA扇區(qū)編碼隊則中，第一個維度是柱面號，既，一段相鄰的扇區(qū)號位于同一柱面。

圖7.2 通用塊層各數(shù)據(jù)結(jié)構(gòu)之間的關(guān)系

三. 處理IO請求

3.1 請求的數(shù)據(jù)結(jié)構(gòu)

磁盤處理讀寫請求的模型是：當(dāng)CPU發(fā)起讀寫請求之后，由DMA負(fù)責(zé)異步完成該請求，一次請求的數(shù)據(jù)在磁盤上必須連續(xù)，但在內(nèi)存中卻可以分散到各個頁中，將一個頁中的數(shù)據(jù)作為一個段。用bio_vec結(jié)構(gòu)來表示一個段，該結(jié)構(gòu)包含頁的struct page以及數(shù)據(jù)在頁中的起始和長度，所以每次請求都使用一個bio結(jié)構(gòu)來表示，它記錄了一次請求中內(nèi)存中數(shù)據(jù)在磁盤上的位置，其核心成員包括bi_sector記錄請求的起始扇區(qū)；bi_io_vec記錄bio_vec鏈表；bi_flags記錄讀寫命令。

@ /include/linux/boi.h
struct bio {
    sector_t        bi_sector;  //該請求的起始扇區(qū)
    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鏈表，核心結(jié)構(gòu)
    atomic_t        bi_cnt;     /* pin count */
    void            *bi_private;
};

通用層會對上層發(fā)來的請求進行合并和排序，多個相鄰的bio會被合并到一個struct request中，struct request也是向設(shè)備驅(qū)動程序發(fā)送IO請求的單位。上一節(jié)提到，每個gendisk有一個請求鏈表，該設(shè)備的所有未處理請求都被放到該鏈表上，queuelist字段負(fù)責(zé)這個鏈表。nr_sectors表示提交扇區(qū)的總數(shù)目，current_nr_sectors表示當(dāng)前bio的扇區(qū)數(shù)目，hard_sector、 hard_cur_sectors與結(jié)構(gòu)中沒有hard_前綴的對應(yīng)成員語義相同，通常兩組變量的值相同，但在使用RAID時可能會有差別。bio鏈表的鏈表頭記錄在struct bio *bio中，鏈表尾記錄在struct bio *biotail中。最后， 所有等待該數(shù)據(jù)的進程在struct completion *waiting上掛起。

@ /include/linux/blkdev.h
struct request {
    struct list_head queuelist; 
    unsigned long flags;          // 請求的命令
    sector_t sector;              // 下一個要提交的扇區(qū)號
    unsigned long nr_sectors;    //提交扇區(qū)的總數(shù)目
    unsigned int current_nr_sectors; //當(dāng)前bio的扇區(qū)數(shù)目

    struct bio *bio;                      // bio鏈表頭
    struct bio *biotail;                 // bio鏈表尾
    void *elevator_private;         // 用于IO調(diào)度算法
    struct gendisk *rq_disk;       // 請求所屬的gendisk

    int tag;
    char *buffer;
    request_queue_t *q;
    struct request_list *rl;
    struct completion *waiting;  // 等待該數(shù)據(jù)的進程在此掛起
    unsigned int timeout;
};

3.2 請求入隊

在開始后兩節(jié)的討論之前，需要明確幾個概念：1）請求隊列有兩個狀態(tài)，阻塞狀態(tài)（plug）下隊列只進不出，只能向隊列提交新的請求，但新的請求不會得到執(zhí)行，排空狀態(tài)（drain）下，隊列只出不進，此時驅(qū)動程序正在處理隊列中已有的請求，但是新的請求不能提交，需要阻塞等待；2）請求是按照邏輯分區(qū)而不是物理磁盤提交的，所以提交入隊分為兩個階段，第一個階段為邏輯分區(qū)中的提交函數(shù)，主要檢查請求是否位于該分區(qū)內(nèi)，并將邏輯扇區(qū)號轉(zhuǎn)換為物理扇區(qū)號，第二階段為物理設(shè)備的提交函數(shù)，負(fù)責(zé)真正的請求提交。
submit_bio負(fù)責(zé)根據(jù)傳遞的bio實例創(chuàng)建一個新請求，它實際上調(diào)用generic_make_request完成核心功能。該函數(shù)首先檢查請求的扇區(qū)是否位于該分區(qū)內(nèi)，隨后檢查隊列是否處于排空狀態(tài)（drain），如果是則阻塞請求的提交。最后，將邏輯分區(qū)中的扇區(qū)號轉(zhuǎn)換成物理設(shè)備中的扇區(qū)號，調(diào)用物理設(shè)備的make_request_fn完成真正的提交。

@ /drivers/block/ll_rw_blk.c
void generic_make_request(struct bio *bio)
{
    // ......判斷請求的扇區(qū)是否位于該分區(qū)內(nèi)
    do {
        q = bdev_get_queue(bio->bi_bdev);
end_io:
        bio_endio(bio, bio->bi_size, -EIO);
        break;
        // 如果該隊列處于排空（drain）狀態(tài)，則該進程需要阻塞等待
        block_wait_queue_running(q);
        // 將邏輯分區(qū)中的扇區(qū)號轉(zhuǎn)換成物理設(shè)備中的扇區(qū)號
        blk_partition_remap(bio);
        //調(diào)用物理設(shè)備的make_request_fn
        ret = q->make_request_fn(q, bio);
    } while (ret);
}

__make_request函數(shù)負(fù)責(zé)將新的bio請求插入請求隊列中，該函數(shù)首先檢查是否為空，若為空則代表之前的請求已經(jīng)處理完成，將隊列設(shè)為阻塞狀態(tài)接收新的請求。隨后嘗試將新請求合并到原有請求上，如果合并成功就可以準(zhǔn)備退出該函數(shù)。如果合并不超過，則準(zhǔn)備構(gòu)建一個請求，先獲取新請求需要的存儲空間，然后為新請求賦值，最后調(diào)用add_request將新請求添加到調(diào)度隊列中，該功能由調(diào)度算法提供，新請求可能不直接插入調(diào)度隊列，而是先插入調(diào)度算法的私有隊列中，等到該請求可以執(zhí)行時再插入調(diào)度隊列。

@ /drivers/block/ll_rw_blk.c
static int __make_request(request_queue_t *q, struct bio *bio)
{
again:    // 檢查隊列是否為空，若空，將隊列設(shè)為阻塞狀態(tài)
    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;
    // 將新請求添加到調(diào)度隊列及調(diào)度算法的私有隊列中
    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 請求出隊

前文提到，為了請求的重排序與合并，隊列有兩個狀態(tài)，阻塞狀態(tài)（plug）和排空狀態(tài)（drain）。當(dāng)隊列處于阻塞狀態(tài)（plug）時，需要定時的切換到排空狀態(tài)（drain）排空請求。有兩個條件可以出發(fā)狀態(tài)切換：1）時間，進入阻塞狀態(tài)時，blk_plug_device函數(shù)會設(shè)置一個時鐘，其默認(rèn)值為3ms，時鐘到時后，隊列將自動切換到排空狀態(tài)（drain）2）已積攢請求的數(shù)量，如果當(dāng)前讀寫請求的數(shù)目達到unplug_thresh指定的閾值，則切換狀態(tài)，使等待的請求得到處理。

三. 處理IO請求

IO調(diào)度程序又稱為電梯算法，所有這類算法的目的都是減少磁盤的尋道時間（因為磁盤的尋道是機械運動，速度非常慢），其名稱來源于Linux 0.11中使用的Linus電梯算法，該算法向電梯搭載乘客的順序一樣處理IO請求，該算法可以最大化磁盤的吞吐，但會帶來嚴(yán)重的餓死問題。針對該問題，2.6版本中，在Linus電梯算法的基礎(chǔ)上提出了4中電梯算法。