1. 背景

派发队列(q->queuehead)(the block device dispatch queue) 为空时，将request从 I/O调度队列(io scheduler queue) 转移到 派发队列, 具体是 通过 调用I/O调度算法的elevatordispatch_fn来完成的:
linux-3.10.86/block/blk.h

__elv_next_request
{
    while (1) {
        if (!list_empty(&q->queue_head)) {
            rq = list_entry_rq(q->queue_head.next);
            return rq;
        }
        ...
        if ( ... || !q->elevator->type->ops.elevator_dispatch_fn(q, 0))//比如deadline_dispatch_requests
            return NULL;
    }       
}

具体调度策略有 cfq-iosched, deadline-iosched等.

I/O调度队列 是调度器的队列, 所以是特定于io调度策略的 队列.

2. 添加到I/O调度队列

linux-3.10.86/block/deadline-iosched.c

static struct elevator_type iosched_deadline = {
    .ops = {
        .elevator_add_req_fn =      deadline_add_request,
        ...
    },
    ...
};  


deadline_add_request
{

    deadline_add_rq_rb
    list_add_tail
}

rq会被同时添加到 rb树, 和 链表fifo_list中.

struct deadline_data {
    /*
     * run time data
     */

    /*
     * requests (deadline_rq s) are present on both sort_list and fifo_list
    request既在sort_list, 又在fifo_list, see deadline_add_request()

    see deadline_merge(), 根据__sector (而不是__sector+ bi_size>>9)在树上放置各request.

    __sector+ bi_size>>9是用来实现back merge, 在独立于io调度策略的层 用来hash的, 
    see struct elevator_queue的hash, 
    and see blk_queue_bio -> elv_merge -> elv_rqhash_find
     */
    struct rb_root sort_list[2];
    /*由于是fifo, 所以, 自然时间上递增, 新添加的放在后面*/
    struct list_head fifo_list[2]; //fong:see deadline_add_request()

    /*
     * next in sort order. read, write or both are NULL

    问题:这个有啥用?
    答:batch模式下, 该rq会被dispatch.

     谁修改该指针?
     deadline_latter_request()修改指针, see deadline_move_request()
     问题:按什么排序? 
     答:扇区编号递增, see deadline_add_request -> deadline_add_rq_rb
     */
    struct request *next_rq[2];
    /*
    如果batching<fifo_batch, 则不按 过期时间来dispatch.
    fifo_batch是setting, batching是run time data.
    */
    unsigned int batching;      /* number of sequential requests made */
    sector_t last_sector;       /* head position  这个注释如何理解??? 被引用比如deadline_move_request()*/
    unsigned int starved;       /* times reads have starved writes */

    /*
     * settings that change how the i/o scheduler behaves

     这几个值是不随进度而变化的.
     */
    int fifo_expire[2];
    /*攒够这个数 才 开始考虑 fifo_list*/
    int fifo_batch;
    int writes_starved;
    int front_merges;
}

​

3. 移动到派发队列

/*
从队列中挑选出一个合适的request, 派发之
*/
deadline_dispatch_requests
{

    if (rq && dd->batching < dd->fifo_batch)
        goto dispatch_request;

}

为简化讨论, 如果系统的读写都比较多, 通常在每次dispatch fifobatch个 (准确地说, 是除首次外, 其他 是每fifobatch-1个) rq后, 才有一个根据 过期时间来选择rq的机会 , batch模式下都是根据sector来选择rq. 假定fifo_batch为1, 则效果是first-come first-served.

4. 调用路径

会到标题2的内容, 添加到io调度队列的路径/回溯:

假定没有plug:

blk_queue_bio
|--elv_merge 之类的 bio合并到rq
|   |-- ->elevator_merged_fn
|--为io分配rq, 然后init_request_from_bio
|--add_acct_request -> __elv_add_request(, ELEVATOR_INSERT_SORT)
|   |--elv_rqhash_add  //不依赖 具体的iosched
|   |--q->elevator->type->ops.elevator_add_req_fn  //依赖 具体的iosched

调用合并的路径:
linux-3.10.86/block/deadline-iosched.c

static struct elevator_type iosched_deadline = {
    .ops = {
        .elevator_merge_fn =        deadline_merge,
        .elevator_merged_fn =       deadline_merged_request,
        .elevator_merge_req_fn =    deadline_merged_requests,
    ...

elevatormergefn, elevatormergedfn, elevatormergereq_fn 的区别是啥?
答: linux-3.10.86/include/linux/elevator.h

struct elevator_ops
{
    //比如deadline_merge
    elevator_merge_fn *elevator_merge_fn; /*仅检查, 不做合并, 合并由elevator_merge_req_fn执行*/
    /*这个是merge*d*, 在合并 *后* 调用, 比如对于deadline-iosched, 要修改rb树*/
    elevator_merged_fn *elevator_merged_fn;
    /*和elevator_merge_fn的区别?
    答:
    typedef int (elevator_merge_fn) (struct request_queue *, struct request **,
                     struct bio *);
    这个原型中有bio, 是查找可以和bio合并的request.

    typedef void (elevator_merge_req_fn) (struct request_queue *, struct request *, struct request *);
    这个名字中给出了 谓宾, 用来合并两struct request.
    */
    elevator_merge_req_fn *elevator_merge_req_fn;

问题:何时调用 deadlinemergedrequests?
答: attemptbackmerge -> attemptmerge -> elvmergerequests -> elevatormergereqfn -> deadlinemergedrequests

blk_queue_bio
{

    el_ret = elv_merge(q, &req, bio);
    if (el_ret == ELEVATOR_BACK_MERGE) {
        if (bio_attempt_back_merge(q, req, bio)) {
            elv_bio_merged(q, req, bio);
            /*
            上面是把bio合并到request中, 图示的[b, c]是刚合并的bio, 合并为[a', c]这个request,
            ---| |---| |---
            a' a b   c d

            现在考虑request [a', c]是否能够和request [d, ]合并.
            */
            if (!attempt_back_merge(q, req))
                elv_merged_request(q, req, el_ret);
            goto out_unlock;
        }
    }

}

问题:struct elevator_queue()和io调度器的关系?
答:

submit_bio() -> generic_make_request -> blk_queue_bio
|--无锁 attempt_plug_merge
|--spin_lock_irq(q->queue_lock);
|--elv_merge(struct request_queue *q, ...) /*没有进行队列的插入操作, 仅判断是否能够完成merge.*/
|   |--struct elevator_queue *e = q->elevator;
|   |--e->type->ops.elevator_merge_fn  -> deadline_merge(struct request_queue *q, ...)
|   |   |--struct deadline_data *dd = q->elevator->elevator_data;

elevatorqueue是 各调度策略通用的结构体. 再通过 elevator->elevatordata 转到 各调度策略 特定的结构体.

本文地址: https://awakening-fong.github.io/posts/io/deadline-iosched

转载请注明出处: https://awakening-fong.github.io