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的優(yōu)先級計算出的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.*/基本上可以認為，同步請求優(yōu)先異步請求，其次根據請求的位置，按照和AS類似的算法決定優(yōu) 先處理哪個請求_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，對應不同的優(yōu)先級，而紅黑樹中的 排序基于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真正把請求下發(fā)到底層驅動上，下面再調用 cfq_add_cfqq_rr把隊列掛到cfq_data代表的塊設備上，下面重新選擇cfq_queue-next_rq，如 果和之前的cfq_queue-next_rq不同，需要改動cfq_queue對應的優(yōu)先級并調整到隊列所在的 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 :選擇最優(yōu)的 workload

31、 class, 和選擇最優(yōu)的 service treechoose_service_tree 選擇的優(yōu)先級是 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指定的成員中；而對于異步請求而 言，由于異步的優(yōu)先級比同步要低，會再經過一些處理，具體的請參考代碼/*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):判斷是否可以向底層驅 動分發(fā)請求#2463如果cfq

35、_queue允許idle 一段時間，同時塊設備還有異步請求on-the-fly，暫時不分發(fā)#2469如果要分發(fā)的這個cfq_queue是一個異步隊列，同時塊設備上還有同步請求on-the-fly， 暫時不分發(fā)#2472先給max_dispatch設定個初始值，默認是cfq_quantum/2 = 4 #2473 對于 idle 級別的 cfq_queue，max_dispatch 設為 1 先看#2542,如果當前cfq_queue-dispatched,即已經分發(fā)的請求數目沒有超過max_dispatch, 如果是同步隊列則允許分發(fā)，異步隊列的話，需要修改下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有請求，那么不限制該隊列的分發(fā)

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的值，來決定是否給 底層驅動分發(fā)下一個請求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來創(chuàng)建一個新隊列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,如果沒有則創(chuàng)建 一個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的，其最低優(yōu)先級無法搶占#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