分类： LINUX
2012-05-08 14:18:04
cfq_queue的属性中，包括workload priority：IDLE, BE, RT，包括workload type：ASYNC, SYNC_NOIDLE, SYNC。同时cfq_queue虽然基于CFQ调度器，但其内部的算法还是基于dead-line的
cfq_group包含了多个红黑树service tree，对应不同workload priority, workload type
一些工具性质的函数：
cfq_find_cfqg(struct cfq_data *cfqd, struct blkio_cgroup *blkcg)： 如果blkcg是全局的blkio_root_cgroup，则返回cfq_data->root_group，否则首先调用 blkiocg_lookup_group在全局的blkio_cgroup的hash列表中查找__key为cfq_data指针的 blkio_cgroup结构。通过blkio_cgroup查找cfq_group的方法很简单，通过一个container_of宏就可以。说的通俗 一点，就是我们已经通过进程找到了对应的blkio_cgroup，可能是一个根cgroup也可能是某个子cgroup，但这个cgroup的设置未必 会有相应的device，e.g. 只设置了blkio.weight而没有设置blkio.dev_weight，这时cfq_data就派上用场了。假设这种场景：一个cgroup中的 不同进程读写不同的block device，甚至一个进程读写不同的device，但proportional weight只是针对单个块设备来的，【这里应该理解为什么blkio_cgroup会有多个blkio_group的哈希项了吧】，因此需要通过 cfq_data这个key来找到那个blkio_group结构（顺便填入cfq_group->blkg.dev，通过 cfq_data->queue->backing_dev_info得来）
cfq_get_cfqg(struct cfq_data *cfqd)：首先通过 current指向的当前的task_struct，查找其所属的blkio_cgroup，如果当前task_struct还没有加入cgroup，则 返回全局的blkio_root_cgroup，其对应的cfq_group结构是cfq_data->root_group。再调用 cfq_find_cfqg，由于传入了cfq_data，因此可以找到cfq_data对应的cfq_cgroup结构。如果没有找到则调 cfq_alloc_cfqg初始化一个cfq_group结构，再通过current找到blkio_cgroup，最后调用 cfq_init_add_cfqg_lists把cfq_data, cfq_group, blkio_cgroup三个结构关联起来。
cfq_get_queue(struct cfq_data *cfqd, bool is_sync, struct io_context *ioc, gfp_t gfp_mask)： 通过ioc得到cfq_data所关联的块设备上进程的cfq_queue，其关键函数为cfq_find_alloc_queue，该函数首先调用 cfq_get_cfqg，通过current指向的当前CPU上在跑的进程来找到cfqd所在块设备上的cfq_group；其次调用 cfq_cic_lookup来得到块设备对应的cfq_io_context， 从而得到对应的cfq_queue（根据其是否同步请求）；最后如果这时cfq_queue为空，则调用kmem_cache_alloc_node重新 分配一个cfq_queue，并将其初始化完毕
cfq_init_add_cfqg_lists(struct cfq_data *cfqd, struct cfq_group *cfqg, struct blkio_cgroup *blkcg)： 把cfqg->blkg这个block_group加到blkcg的哈希表中，这里哈希键值是cfq_data的指针值。同时cfqd这个 cfq_data结构也保存了一个哈希表，表头是cfq_data->cfqg_list，该函数会把cfq_group也同时加到这个哈希表里 【这里可以看到，blkio_cgroup会保存一个blkio_group的哈希表，每个cfq_data对应一个blkio_group】。同时每个 cfq_data也会保存一个哈希表，记录这个cfq_data对应的块设备下的所有cfq_group
cfq_get_io_context(struct cfq_data *cfqd, gfp_t gfp_mask)：
/*
* Setup general io context and cfq io context. There can be several cfq
* io contexts per general io context, if this process is doing io to more
* than one device managed by cfq.
*/
上面这段解释了为什么一个io_context里会有多个cfq_io_context，因为一个进程可能同时读写多个设备，这时需要通过cfq_data来确定块设备，从而得到基于这个块设备IO的cfq_io_context
该函数首先调用cfq_cic_lookup查找是否已有cfq_io_context，如果有了就退出，否则调用 cfq_alloc_io_context创建一个cfq_io_context，把这个cfq_io_context加入到io_context的 radix_tree里（key值为cfq_data指针），如果有必要则调用 cfq_ioc_set_ioprio，cfq_ioc_set_cgroup来设置io priority和cgroup
cfq_ioc_set_cgroup(struct io_context *ioc)： 对于ioc的哈希表ioc->cic_list中的每一个hash node（实际上是cfq_io_context），调用changed_cgroup。 其中changed_cgroup的作用是把cfq_io_context的cfq_queue类型的同步队列设置为NULL，代码中的解释如下
/*
* Drop reference to sync queue. A new sync queue will be
* assigned in new group upon arrival of a fresh request.
*/
cfq_ioc_set_ioprio(struct io_context *ioc)：和cfq_ioc_set_cgroup类似，跳过了
cfq_cic_lookup(struct cfq_data *cfqd, struct io_context *ioc)：io_context 保存了一个radix_tree，其树根为io_context->radix_root。据我猜测，io_context为什么要包含一个 cfq_io_context的radix tree呢？可能是因为进程会同时读写多个块设备，因此根据cfq_data的成员cic_index，里面是cfq_data对应的块设备在radix tree里的索引。最后返回io_context中相应块设备对应的cfq_io_context
cfq_cic_link(struct cfq_data *cfqd, struct io_context *ioc, struct cfq_io_context *cic, gfp_t gfp_mask)：具体的代码注释讲的很清楚了，跳过
/*
* Add cic into ioc, using cfqd as the search key. This enables us to lookup
* the process specific cfq io context when entered from the block layer.
* Also adds the cic to a per-cfqd list, used when this queue is removed.
*/
cic_to_cfqd(struct cfq_io_context *cic)：cfq_io_context的key就是对应的cfq_data
cfq_set_request(struct request_queue *q, struct request *rq, gfp_t gfp_mask)： 这里可以看到，有struct cfq_data *cfqd = q->elevator->elevator_data 说明cfq_data是基于块设备的。该函数作用是为一个request来分配相应的cfq_io_context, cfq_queue并存到request->elevator_private中。
cfq_scaled_cfqq_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)： 通过一系列公式，计算出一个cfq_queue所占用的time_slice。首先计算cfq_cgroup中的平均cfq_queue个数，以及每个 cfq_queue的time slice，相乘得到expect_latency为这个cgroup希望得到的time slice；同时调用cfq_group_slice按照权重比例计算出cgroup的time slice；如果这个time slice小于expect_latency，则调整之前根据cfq_queue的优先级计算出的slice，否则返回之前调用 cfq_prio_to_slice得到的time slice
cfq_prio_slice cfq_prio_to_slice cfq_scale_slice：这三个函数都是计算队列的服务时间slice time的
cfq_group_slice：cfq_data->grp_service_tree 为一个cfq_rb_root为一个红黑树树根，其成员total_weight为这个块设备上所有cgroup的权重值，而 cfq_group->weight为该cgroup的权重值，因此该函数返回基于cfq_target_latency，300ms，各个 cgroup所占用的slice时间，基于weight的比例。
cfq_set_prio_slice：设置cfq_queue中对应的slice_start, slice_end, allocated_slice
cfq_choose_req(struct cfq_data *cfqd, struct request *rq1, struct request *rq2, sector_t last)：看代码中的解释
/*
* Lifted from AS - choose which of rq1 and rq2 that is best served now.
* We choose the request that is closest to the head right now. Distance
* behind the head is penalized and only allowed to a certain extent.
*/
基本上可以认为，同步请求优先异步请求，其次根据请求的位置，按照和AS类似的算法决定优先处理哪个请求
__cfq_group_service_tree_add(struct cfq_rb_root *st, struct cfq_group *cfqg)：向service tree插入一个cfq_group，其中红黑树的key被编程为
static inline s64
cfqg_key(struct cfq_rb_root *st, struct cfq_group *cfqg)
{
return cfqg->vdisktime - st->min_vdisktime;
}
这边vdisktime和min_vdisktime是干什么用的，目前我也不清楚
cfq_link_cfqq_cfqg(struct cfq_queue *cfqq, struct cfq_group *cfqg)：这个函数本身没啥可说的，但是验证了在CFQ调度器中，所有的异步请求都属于cfq_data->root_group这个cgroup，因此不受指定cgroup的任何限制
#1248 - #1267这段代码，是不需要cgroup调度支持的cfq调度器代码，可以看出简单很多，cfq_get_cfqg只是简单返回cfq_data->root_group
cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq, bool add_front)： 该函数目的是把cfq_queue加入到cfq_group对应的service_tree的红黑树中。首先根据io class, io priority来找到cfq_group对应的service_tree，类型为cfq_rb_root，其中插入的key是计算出来的一个起始时间， 应该cfq_group是按照这个起始时间来依次处理挂在上面的所有cfq_queue的请求。最后调用 cfq_group_notify_queue_add来通知cfq_data
cfq_prio_tree_lookup，cfq_prio_tree_add：这两个函数都是把cfq_queue加到cfq_data里的priority tree的红黑树中，cfq_data共有8个priority tree，对应不同的优先级，而红黑树中的排序基于cfq_queue中第一个请求的sector position
cfq_resort_rr_list，cfq_add_cfqq_rr，cfq_del_cfqq_rr：
前者把cfq_queue加到cfq_data中的cgroup对应的service_tree数组，以及cfq_data的priority tree的红黑树中。
后者除了调用cfq_resort_rr_list以外，还递增了cfq_data->busy_queues，cfq_data->busy_sync_queues
最后把cfq_queue移除出service tree，和priority tree，并调用cfq_group_notify_queue_del通知cfq_data
cfq_del_rq_rb，cfq_add_rq_rb：这两个函数操作cfq_queue里面的request请求，把请求从cfq_queue中添加或者删除
cfq_add_rq_rb首先调用elv_rb_add把请求插到cfq_queue->sort_list这个红黑树中，基于请求的起始 sector，再调用cfq_dispatch_insert真正把请求下发到底层驱动上，下面再调用cfq_add_cfqq_rr把队列挂到 cfq_data代表的块设备上，下面重新选择cfq_queue->next_rq，如果和之前的cfq_queue->next_rq不 同，需要改动cfq_queue对应的优先级并调整到队列所在的cfq_data下的priority tree中
cfq_del_rq_rb调用elv_rb_del把请求从cfq_queue->sort_list中删除，如果此时cfq_queue->sort_list为空了，而该队列又在cfq_data的priority tree中，则从红黑树里删除掉
cfq_remove_request(struct request *rq)：调用cfq_del_rq_rb从cfq_queue中删除rq
cfq_find_rq_fmerge(struct cfq_data *cfqd, struct bio *bio)： 通过当前current的task_struct来找到io_context，从而调用cfq_cic_lookup来找到 cfq_io_context，然后根据bio是否同步找到对应的cfq_queue；下面找到bio之后的第一个sector，然后在 cfq_queue->sort_list中基于这个sector查找是否有对应的bio可以被merge
cfq_merge：检查是否可以merge，如何可以修改对应的request，把bio给merge进request
cfq_merged_request：调用cfq_reposition_rq_rb，把相应的request更新为已经merge了bio的request
__cfq_set_active_queue：似乎是初始化cfq_queue，并将其设置为active_queue
__cfq_slice_expired(struct cfq_data *cfqd, struct cfq_queue *cfqq, bool timed_out)：
/*
* current cfqq expired its slice (or was too idle), select new one
*/
#1744 - #1751 (kernel.org 3.0.23 cfq-iosched.c) 这里的cfq_queue->slice_resid似乎是还没有用完的slice_time
nr_sync 计算出cfq_group同步队列的个数
cfq_group_served
charge表示已经用掉的配额，在不同模式下意义不同，如果是iops模式，用cfq_queue->slice_dispatch，也就 是dispatch的请求个数作为不同的cfq_queue的配额，如果是异步请求则用cfq_queue->allocated_slice，也 就是分配给该队列的时间作为配额；否则是同步非iops模式则等同于used_sl （通过cfq_cfqq_slice_usage计算得出）
#975 - #978 cfq_group->vdisktime似乎是改cgroup至今所有用掉的slice总和
如果当前的cfq_group的expire时间（cfq_data->workload_expires）在jiffies之前，那啥也不 用做了，不然保存相应的cfq_group的 saved_workload_slice，saved_workload，saved_serving_prio
最后调用cfq_resort_rr_list，把cfq_queue插到cfq_group，cfq_data对应的service tree, prio tree的红黑树中
所以代码看下来，我猜测所有的cfq_queue开始时都在cfq_data和其对应的cfq_group的service tree，priority tree中，当轮到这个cfq_queue被处理时，从这些红黑树中被摘下来，等到其slice expired之后，更新一系列参数后被放回原来的红黑树里；再进一步说，如果cfq_queue里已经没有请求了，则会把他们从红黑树里移除掉，如果此 时cfq_queue的time slice还没用完，会留着下次再用
这应该就是CFQ大致的工作原理
cfq_dist_from_last，cfq_rq_close：
前者计算出request的sector和cfq_data的last_position对应的sector之间相隔的sector数，后者拿这个 值和CFQ_CLOSE_THR比较，如果在这个范围内就认为两个request是相近的请求（言下之意不会对磁头转动造成太多的overhead）
cfqq_close(struct cfq_data *cfqd, struct cfq_queue *cur_cfqq)：
/*
* First, if we find a request starting at the end of the last
* request, choose it.
*/
首先调用cfq_prio_tree_lookup查找同一个priority tree下的cfq_queue中，有没有起始sector正好在cfq_data->last_position上的，如果有则返回这个离当前磁头位置最近的cfq_queue
/*
* If the exact sector wasn't found, the parent of the NULL leaf
* will contain the closest sector.
*/
如果cfq_prio_tree_lookup没有找到，则返回的parent参数包含了sector差别最小的那个cfq_queue，如果这个cfq_queue->next_rq满足了cfq_rq_close的要求，则返回这个cfq_queue
如果不满足的，开始遍历这个红黑树（只遍历一次），再次判断这个cfq_queue是否满足cfq_rq_close，如果不满足就返回NULL
cfq_choose_wl，choose_service_tree：选择最优的workload class，和选择最优的service tree
choose_service_tree选择的优先级是RT > BE > IDLE，这个决定了cfq_data->serving_prio，然后调用cfq_choose_wl来决定cfq_data->serving_type，
/*
* the workload slice is computed as a fraction of target latency
* proportional to the number of queues in that workload, over
* all the queues in the same priority class
*/
group_slice调用cfq_group_slice，根据group的权重计算出来，而slice则是这个workload里的queues占所有busy_queues_avg的比例而计算得出的
对于同步请求而言，slice在经过一系列的比对之后，会把cfq_data->workload_expires = jiffies + slice，即当前服务的cfq_queue的配额时间被放到cfq_data指定的成员中；而对于异步请求而言，由于异步的优先级比同步要低，会再经过 一些处理，具体的请参考代码
/*
* Async queues are currently system wide. Just taking
* proportion of queues with-in same group will lead to higher
* async ratio system wide as generally root group is going
* to have higher weight. A more accurate thing would be to
* calculate system wide asnc/sync ratio.
*/
static struct cfq_queue *cfq_select_queue(struct cfq_data *cfqd)：
/*
* Select a queue for service. If we have a current active queue,
* check whether to continue servicing it, or retrieve and set a new one.
*/
这里可以参考之前关于cfq_slice_expired函数的解析，可以看到cfq_data每个时刻只服务一个cfq_queue，就是cfq_data->active_queue
cfq_may_dispatch(struct cfq_data *cfqd, struct cfq_queue *cfqq)：判断是否可以向底层驱动分发请求
#2463 如果cfq_queue允许idle一段时间，同时块设备还有异步请求on-the-fly，暂时不分发
#2469 如果要分发的这个cfq_queue是一个异步队列，同时块设备上还有同步请求on-the-fly，暂时不分发
#2472 先给max_dispatch设定个初始值，默认是cfq_quantum/2 = 4
#2473 对于idle级别的cfq_queue，max_dispatch设为1
先看#2542，如果当前cfq_queue->dispatched，即已经分发的请求数目没有超过max_dispatch，如果是同步 队列则允许分发，异步队列的话，需要修改下max_dispatch的值并重新和cfq_queue->dispatched比较，具体原因请看代 码注释
/**/
再回到#2479，如果此时cfq_queue->dispatched已经超过了max_dispatch，如果这是个同步cfq_queue，同时此时块设备上只有这个cfq_queue有请求，那么不限制该队列的分发请求数，如下面注释
/*
* If there is only one sync queue
* we can ignore async queue here and give the sync
* queue no dispatch limit. The reason is a sync queue can
* preempt async queue, limiting the sync queue doesn't make
* sense. This is useful for aiostress test.
*/
否则如果只有一个cfq_queue，放大一倍max_dispatch的值，到cfq_data->cfq_quantum = 8
不管怎样，最后还是要比较一次cfq_queue->dispatched和max_dispatch的值，来决定是否给底层驱动分发下一个请求
cfq_exit_io_context：当一个task结束之后，需要对io_context关联的所有cfq_io_context，调用cfq_exit_single_io_context
cfq_exit_single_io_context，__cfq_exit_single_io_context：对cfq_io_context的异步，同步队列，分别调用cfq_exit_cfqq
changed_cgroup(struct io_context *ioc, struct cfq_io_context *cic)：
首先无视掉cic对应的异步队列，由此也可以看出其实CFQ里，异步请求是不分cgroup的，下面直接把cfq_io_context里的同步队列设置为NULL，代码中的注释告诉了为什么要这么做
/*
* Drop reference to sync queue. A new sync queue will be
* assigned in new group upon arrival of a fresh request.
*/
cfq_get_queue(struct cfq_data *cfqd, bool is_sync, struct io_context *ioc, gfp_t gfp_mask)：如果是is_sync表示异步，调用cfq_async_queue_prio返回块设备对应的异步队列；否则调用cfq_find_alloc_queue来创建一个新队列
cfq_get_io_context(struct cfq_data *cfqd, gfp_t gfp_mask)：
/*
* Setup general io context and cfq io context. There can be several cfq
* io contexts per general io context, if this process is doing io to more
* than one device managed by cfq.
*/
首先调用get_io_context，获取current指向的task_struct对应的io_context，如果没有则创建一个 io_context；下面调用cfq_cic_lookup获取cfq_io_context，如果为空则调用 cfq_alloc_io_context创建一个cfq_io_context，并调用cfq_cic_link把cfq_io_context和 io_context关联起来；最后调用cfq_ioc_set_ioprio，cfq_ioc_set_cgroup，实际上是对每个 cfq_io_context，调用changed_ioprio，changed_cgroup，这些函数是设置个ioprio_changed, cgroup_changed之类的标签
cfq_update_idle_window(struct cfq_data *cfqd, struct cfq_queue *cfqq, struct cfq_io_context *cic)：
首先，如果是异步队列或者队列级别为IDLE，不考虑idle（slice_idle, group_idle之类的磁头停留时间）
如果cfq_queue->next_rq->cmd_flags包含了REQ_NOIDLE，不考虑idle；如果slice_idle为0，也不考虑idle；如果io_context->nr_tasks为0，也不考虑idle
最后根据前后是否idle，调用cfq_mark_cfqq_idle_window/cfq_clear_cfqq_idle_window
cfq_should_preempt(struct cfq_data *cfqd, struct cfq_queue *new_cfqq, struct request *rq)：判断new_cfqq是否可以抢占
/*
* Check if new_cfqq should preempt the currently active queue. Return 0 for
* no or if we aren't sure, a 1 will cause a preempt.
*/
#3317 如果new_cfqq是idle class的，其最低优先级无法抢占
#3320 如果cfqq，也就是cfq_data->active_queue是idle class的，必定可以被抢占
#3326 不允许非RT抢占RT的cfq_queue
#3333 当前cfqq不是同步队列，那么同步请求所在队列可以抢占
#3336 如果两个队列不属于同一个cgroup，不可抢占
#3339 如果当前cfqq时间片已经用完，可以抢占
#3353 如果请求是基于元数据的，可以抢占
#3359 RT请求可以抢占非RT的请求
cfq_preempt_queue(struct cfq_data *cfqd, struct cfq_queue *cfqq)：
/*
* cfqq preempts the active queue. if we allowed preempt with no slice left,
* let it have half of its nominal slice.
*/
cfq_rq_enqueued(struct cfq_data *cfqd, struct cfq_queue *cfqq, struct request *rq)：
/*
* Called when a new fs request (rq) is added (to cfqq). Check if there's
* something we should do about it
*/
#3419 - #3421 可以看出cfq_data->rq_queued代表了块设备调度器等待处理的request，cfq_queue->meta_pending代表了每个队列的元数据请求
#3429 - #3451 如果请求所在的队列就是当前cfq_data的active_queue
/*
* Remember that we saw a request from this process, but
* don't start queuing just yet. Otherwise we risk seeing lots
* of tiny requests, because we disrupt the normal plugging
* and merging. If the request is already larger than a single
* page, let it rip immediately. For that case we assume that
* merging is already done. Ditto for a busy system that
* has other work pending, don't risk delaying until the
* idle timer unplug to continue working.
*/
#3452 - #3460 这时意味着要抢占
无论上述哪种情况，都会调用__blk_run_queue，该函数会调用request_queue->request_fn，这个函数由 底层驱动初始化，用来从调度队列里获取请求。一般这个函数会调用电梯算法的__elv_next_request，可能会再调用 elevator_dispatch_fn。同时也意味着除此之外的情况不需要把请求立刻交给底层驱动
cfq_kick_queue(struct work_struct *work)：该函数是一个工作队列的延迟执行函数，被赋值给cfq_data->unplug_work，该函数最后执行__blk_run_queue
void cfq_idle_slice_timer(unsigned long data)：
/*
* Timer running if the active_queue is currently idling inside its time slice
*/
我猜测是队列slice_idle时间过去之后，触发的timer执行的函数
如果cfq_cfqq_must_dispatch(cfqq)为true，无脑dispatch掉；如果time slice过期，调用cfq_slice_expired；如果cfq_data还有其他的busy queue，不作为；如果cfq_queue->sort_list不为空，dispatch掉
分发的方式是调用cfq_schedule_dispatch，通过一个工作队列调用cfq_data->unplug_work，这个unplug_work可以看到调用cfq_kick_queue来让底层驱动得到请求
