linux的CFQ调度器解析

1、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 是全局的 blki

2、o_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

3、.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

4、):首先通过 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_

5、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来得到块设备对应

6、的 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结构也保存了一个哈

7、希表，表头是 cfq_data-cfqg_list，该函数会把cfq_group也同时加到这个哈希表里【这里可以看到， blkio_cgroup会保存一个blkio_group的哈希表，每个cfq_data对应一个blkio_group】。同时 每个cfq_data也会保存一个哈希表，记录这个cfq_data对应的块设备下的所有cfq_groupcfq_get_io_context(structcfq_data *cfqd, gfp_tgfp_mask):/*Setup general io context and cfq io context. There can be several cf

8、qio contexts per general io context, if this process is doing io to morethan 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 仓ll建一个 cfq

9、_io_context，把这个 cfq_io_context 力口入U io_context 的 radix_tree 里(key 值为 cfq_data 指针)，如果有必要则调用 cfq_ioc_set_ioprio， cfq_ioc_set_cgroup 来设置 io priority 和 cgroupcfq_ioc_set_cgroup(struct io_context *ioc):对于 ioc 的哈希表 ioc-cic_list 中的每一个 hash node (实际上是 cfq_io_context)，调用 changed_cgroup。其中 changed_cgroup 的作用是

10、 把cfq_io_context的cfq_queue类型的同步队列设置为NULL，代码中的解释如下/*Drop reference to sync queue. A new sync queue will beassigned 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_c

11、ontext 保存 了 一个 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_contextcfq_cic_link(struct cfq_data *cfqd, struct io_context *ioc, struct cfq_io_contex

12、t *cic, gfp_tgfp_mask):具体的代码注释讲的很清楚了，跳过/*Add cic into ioc, using cfqd as the search key. This enables us to lookupthe 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) : c

13、fq_io_context 的 key 就是对应的 cfq_datacfq_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

14、_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

15、_to_slice 得到的 time slicecfq_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时间，基于 weigh

16、t的比例。cfq_set_prio_slice :设置 cfq_queue 中对应的 slice_start, slice_end, allocated_slicecfq_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

17、head right now. Distancebehind the head is penalized and only allowed to a certain extent.*/基本上可以认为，同步请求优先异步请求，其次根据请求的位置，按照和AS类似的算法决定优 先处理哪个请求_cfq_group_service_tree_add(structcfq_rb_root *st, structcfq_group *cfqg):向 service tree插入一个cfq_group，其中红黑树的key被编程为static inline s64cfqg_key(struct cfq_rb_roo

18、t *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调度器代

19、码，可以看出简单很多， cfq_get_cfqg 只是简单返回 cfq_data-root_groupcfq_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是按照这个起始时间来依次处理

20、挂在上面的所有 cfq_queue 的请求。 最后调用 cfq_group_notify_queue_add 来通矢日 cfq_datacfq_prio_tree_lookup, cfq_prio_tree_add :这两个函数都是把 cfq_queue 加到 cfq_data 里 的priority tree的红黑树中，cfq_data共有8个priority tree，对应不同的优先级，而红黑树中的 排序基于cfq_queue中第一个请求的sector positioncfq_resort_rr_list，cfq_add_cfqq_rr，cfq_del_cfqq_rr:前者把 cfq_qu

21、eue 加到 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_datacfq_del_rq_rb，cfq_add_rq_rb :这两个函数操作cfq_queue里面的re

22、quest请求，把请求从 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

23、 调用 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 中删除 rqcfq_find_rq_fmerge(struct cfq_data *cfqd, struct bio *bio):通过当前 current 的 task_struct 来找到io_context，从而调用cfq_cic_loo

24、kup来找到cfq_io_context，然后根据bio是否同步找 到对应的cfq_queue；下面找到bio之后的第一个sector，然后在cfq_queue-sort_list中基于 这个sector查找是否有对应的bio可以被mergecfq_merge :检查是否可以merge，如何可以修改对应的request，把bio给merge进requestcfq_merged_request:调用 cfq_reposition_rq_rb，把相应的 request 更新为已经 merge 了 bio 的 request_cfq_set_active_queue :似乎是初始化 cfq_queu

25、e，并将其设置为 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 ( 3.0.23 cfq-iosched.c)这里的 cfq_queue-slice_resid 似乎是还没有 用完的 slice_time nr_sync计算出cfq_group同步队列的个数 cfq_gr

26、oup_servedcharge表示已经用掉的配额，在不同模式下意义不同，如果是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 时间(

27、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_

28、queue被处理时，从这些红黑树中被摘下来，等到其slice expired之后，更新一系列参数后被放回原来的红黑树里；再进一步说，如果cfq_queue里已经 没有请求了，则会把他们从红黑树里移除掉，这应该就是CFQ大致的工作原理cfq_dist_from_last，cfq_rq_close :前者计算出request的sector和cfq_data的last_position对应的sector之间相隔的sector数，后者拿这个值和CFQ_CLOSE_THR比较，如果在这个范围内就认为两个request是相近的请求（言下之意不会对磁头转动造成太多的overhead）cfqq_close（s

29、truct cfq_data *cfqd, struct cfq_queue *cur_cfqq）/*First, if we find a request starting at the end of the lastrequest, choose it.*/首先调用 cfq_prio_tree_lookup 查找同一个 priority tree 下的 cfq_queue 中，有没有起始 sector 正好在cfq_data-last_position上的，如果有则返回这个离当前磁头位置最近的cfq_queue/*If the exact sector wasnt found, the p

30、arent of the NULL leafwill 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，如果不满足就返回NULLcfq_choose_wl, choose_service_tree :选择最优的 workload

31、 class, 和选择最优的 service treechoose_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 latencyproportional to the number of queues in that workload, overall the queues in the same priority c

32、lass*/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. Ju

33、st takingproportion of queues with-in same group will lead to higherasync ratio system wide as generally root group is goingto have higher weight. A more accurate thing would be tocalculate system wide asnc/sync ratio.*/static struct cfq_queue *cfq_select_queue(struct cfq_data *cfqd):/*Select a queu

34、e 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_queuecfq_may_dispatch(struct cfq_data *cfqd, struct cfq_queue *cfqq):判断是否可以向底层驱 动分发请求#2463如果cfq

35、_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的值并重新

36、和 cfq_queue-dispatched比较，具体原因请看代码注释/*Async queues must wait a bit before being allowed dispatch.We also ramp up the dispatch depth gradually for async IO,based on the last sync IO we serviced */再回到#2479，如果此时cfq_queue-dispatched已经超过了 max_dispatch，如果这是个同步 cfq_queue，同时此时块设备上只有这个cfq_queue有请求，那么不限制该队列的分发

37、请求数， 如下面注释/*If there is only one sync queuewe can ignore async queue here and give the syncqueue no dispatch limit. The reason is a sync queue canpreempt async queue, limiting the sync queue doesnt makesense. This is useful for aiostress test.*/否则如果只有一个 cfq_queue，放大一倍 max_dispatch 的值，到 cfq_data-cfq_

38、quantum = 8不管怎样，最后还是要比较一次cfq_queue-dispatched和max_dispatch的值，来决定是否给 底层驱动分发下一个请求cfq_exit_io_context:当一个 task 结束之后，需要对 io_context 关联的所有 cfq_io_context， 调用 cfq_exit_single_io_contextcfq_exit_single_io_context，_cfq_exit_single_io_context:对 cfq_io_context 的异步，同步队列，分别调用cfq_exit_cfqqchanged_cgroup(struct i

39、o_context *ioc, struct cfq_io_context *cic):首先无视掉cic对应的异步队列，由此也可以看出其实CFQ里，异步请求是不分cgroup的，下 面直接把cfq_io_context里的同步队列设置为NULL，代码中的注释告诉了为什么要这么做/*Drop reference to sync queue. A new sync queue will beassigned in new group upon arrival of a fresh request.*/cfq getqueue(struct cfq_data *cfqd, bool is_sync,

40、 struct io_context *ioc, gfp_tgfp_mask):如果是is_sync表示异步，调用cfq_async_queue_prio返回块设备对应的异步队 列；否则调用cfq_find_alloc_queue来创建一个新队列cfq getio context(struct cfq_data *cfqd, gfp_t gfp_mask):/*Setup general io context and cfq io context. There can be several cfqio contexts per general io context, if this proce

41、ss is doing io to morethan 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 仓ll建一个 cfq_io_context，并调用 cfq_cic_link 把 cfq_io_context 和 io_context 关联起来； 最后调用 cfq_ioc_set_ioprio, cfq_

42、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-cm

43、d_flags 包含了 REQ_NOIDLE，不考虑 idle；如果 slice_idle 为 0， 也不考虑idle；如果io_context-nr_tasks为0，也不考虑idle最后根据前后是否 idle，调用 cfq_mark_cfqq_idle_window/cfq_clear_cfqq_idle_windowcfq_should_preempt(struct cfq_data *cfqd, struct cfq_queue *new_cfqq, struct request *rq):判断new_cfqq是否可以抢占/*Check if new_cfqq should preemp

44、t the currently active queue. Return 0 forno or if we arent 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