内核block层IO调度器—bfq算法之3源码要点总结

在《内核block层IO调度器—bfq算法之2源码详解》文章的基础上，本文主要总结一个bfq算法的源码要点，bfq算法真的复杂！本文基于centos 8.3，内核版本4.18.0-240.el8，详细源码注释见 https://github.com/dongzhiyan-stack/linux-4.18.0-240.el8。

要想了解bfq调度算法的工作原理，我觉得主要还得看派发IO请求的__bfq_dispatch_request()函数。该函数涉及怎么选择IO调度器使用的bfqq和entity、派发bfqq上的IO请求、bfqq因配额不够或者没有要派发的IO请求而过期失效、bfqq的entity过期失效而从st->active红黑树剔除而移动到st->active红黑树或者计算新的entity->finish而重新加入st->active红黑树、分配一个新的bfqq后把它的entity加入st->active红黑树、激活一个在st->active红黑树的entity而把它加入到st->active红黑树。下边先把涉及的流程框图贴下：

 下文围绕这个图较为深入的讲解一下bfq调度算法的工作原理。首先还是把涉及的核心源码简明扼要贴下：

1：bfq 重要函数源码总结

先从派发IO请求的__bfq_dispatch_request()函数开始。

1.1派发IO请求入口函数

1. static struct request *__bfq_dispatch_request(struct blk_mq_hw_ctx *hctx)
2. {
3.     //选择派发IO请求的bfqq
4.     bfqq = bfq_select_queue(bfqd);
5.     //从bfqq选择一个派发的IO请求req
6.     rq = bfq_dispatch_rq_from_bfqq(bfqd, bfqq);
7. }

入口函数__bfq_dispatch_request()，主要调用bfq_select_queue()和bfq_dispatch_rq_from_bfqq()两个函数。

1. static struct bfq_queue *bfq_select_queue(struct bfq_data *bfqd)
2. {
3.      bfqq = bfqd->in_service_queue;
4.      if (!bfqq)
5.           goto new_queue;
6.     ........
7. check_queue:
8.      next_rq = bfqq->next_rq;
9.      if (next_rq) {
10.          if (bfq_serv_to_charge(next_rq, bfqq) >bfq_bfqq_budget_left(bfqq)) {
11.              reason = BFQQE_BUDGET_EXHAUSTED;//bfqq 的配额消耗光了
12.              goto expire;//bfqq 的配额消耗光而令bfqq到期失效
13.          }else{
14.              goto keep_queue;//继续使用bfqd->in_service_queue这个bfqq，保持
15.          }
16.      }
17.      ...........
18.       reason = BFQQE_NO_MORE_REQUESTS;//bfqq没有req要传输了
19. expire:
20.       //bfqq过期失效
21.       bfq_bfqq_expire(bfqd, bfqq, false, reason);
22. new_queue:
23.      //选择一个新的bfqq赋于bfqd->in_service_queue，作为bfq当前使用的bfqq
24.      bfqq = bfq_set_in_service_queue(bfqd);
25.      if (bfqq) {
26.           goto check_queue;//goto check_queue 分支，派发新选中的bfqq的IO请求
27.      }
28. keep_queue:
29.      return bfqq;   
30. }

bfq_select_queue()中先判断bfqq=bfqd->in_service_queue是否有正在使用的bfqq，即判断bfqd->in_service_queue是否是NULL。如果bfqd->in_service_queue是NULL，表示没有正在使用的bfqq，则goto new_queue分支执行bfq_set_in_service_queue()选择一个bfqq赋于bfqd->in_service_queue，然后goto check_queue分支。如果bfqd->in_service_queue非NULL，则从bfqq->next_rq取出该bfqq要派发的IO请求。如果bfqq->next_rq是NULL，表示该bfqq没有要派发的IO请求了，则reason = BFQQE_NO_MORE_REQUESTS，然后执行bfq_bfqq_expire()令bfqq因没有派发的IO请求而过期失效。如果bfqq->next_rq非NULL，则判断该bfqq是否有足够的配额派发bfqq->next_rq这个IO请求，有足够的配额的话则goto keep_queue分支直接返回bfqd->in_service_queue这个bfqq。否则goto expire分支执行bfq_bfqq_expire()令bfqq因配额不够而过期失效。bfq_select_queue()函数有点复杂，在本文开头的示意图也有重点标出。下边把bfq_set_in_service_queue ()和bfq_bfqq_expire()函数源码简单列下：

1. static struct bfq_queue *bfq_set_in_service_queue(struct bfq_data *bfqd)
2. {
3.     //从sd->next_in_service取出entity赋于sd->in_service_entity，作为本次要使用的entity。然后查找一个新的entity赋于sd->next_in_service，作为下一次使用的entity
4.     struct bfq_queue *bfqq = bfq_get_next_queue(bfqd);
6.     //本质是 bfqd->in_service_queue = bfqq
7.     __bfq_set_in_service_queue(bfqd, bfqq);
8.     return bfqq;
9. }

下边看下bfq_bfqq_expire()函数相关源码

1. void bfq_bfqq_expire(struct bfq_data *bfqd,struct bfq_queue *bfqq,bool compensate,enum bfqq_expiration reason)
2. {
3.     ..............
4.     //计算更新bfqq->max_budget，如果bfqq上还有req(bfqq->next_rq)要派发，则计算根据next_rq传输的字节数计算bfqq->entity的配额，保证bfqq的配额还能传输完next_rq
5.     __bfq_bfqq_recalc_budget(bfqd, bfqq, reason);
6.     ..............
7.     //令bfqq过期失效
8.     if (__bfq_bfqq_expire(bfqd, bfqq, reason))
9.     ..............
10. }
12. static bool __bfq_bfqq_expire(struct bfq_data *bfqd, struct bfq_queue *bfqq,
13.                   enum bfqq_expiration reason)
14. {
15.     if (RB_EMPTY_ROOT(&bfqq->sort_list) &&//bfqq上没有派发的req
16.         !(reason == BFQQE_PREEMPTED &&
17.           idling_needed_for_service_guarantees(bfqd, bfqq)))
18.     {   //bfqq上没有IO请求要派发了而过期失效，把bfqq的entity从st->active红黑树剔除而移入st->active红黑树
19.         bfq_del_bfqq_busy(bfqd, bfqq, true);
20.     }else{
21.         //bfqq配额消耗光了而过期失效，把bfqq的entity重新加入到st->active红黑树。因为bfqq上还有IO请求要派发
22.         bfq_requeue_bfqq(bfqd, bfqq, true);
23.     }
24.     //bfqd->in_service_queue = NULL 清空
25.     return __bfq_bfqd_reset_in_service(bfqd);
26. }
28. void bfq_del_bfqq_busy(struct bfq_data *bfqd, struct bfq_queue *bfqq,
29.                bool expiration)
30. {
31.     //清理bfqq busy状态
32.     bfq_clear_bfqq_busy(bfqq);
33.     //从st->active 红黑树剔除bfqq的entity
34.     bfq_deactivate_bfqq(bfqd, bfqq, true, expiration);
35. }
37. void bfq_deactivate_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq,
38.              bool ins_into_idle_tree, bool expiration)
39. {
40.     struct bfq_entity *entity = &bfqq->entity;
41.     bfq_deactivate_entity(entity, ins_into_idle_tree, expiration);
42. }
43. //bfqd->in_service_queue指向的正在使用的bfqq，配额消耗光但bfqq上还有要派发IO请求，于是把bfqq重新插入到st->active红黑树，并且选择一个新的bfqq作为bfqd->in_service_queue。
44. void bfq_requeue_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq,
45.               bool expiration)
46. {
47.     struct bfq_entity *entity = &bfqq->entity;
48.     bfq_activate_requeue_entity(entity, false,bfqq == bfqd->in_service_queue, expiration);
49. }
50. //把entity加入到st->active红黑树
51. static void bfq_activate_requeue_entity(struct bfq_entity *entity,
52.                     bool non_blocking_wait_rq,
53.                     bool requeue, bool expiration)
54. {
55.     //把entity加入到st->active红黑树
56.     __bfq_activate_requeue_entity(entity, sd, non_blocking_wait_rq);
57.     ///查找新的 next_in_service entity赋于sd->next_in_service
58.     if (!bfq_update_next_in_service(sd, entity, expiration) &&!requeue)
59.         break;
60. }

可以发现，bfqq因没有要派发的IO请求而过期失效， bfq_bfqq_expire()函数的调用流程是bfq_bfqq_expire()->__bfq_bfqq_expire()->bfq_del_bfqq_busy()->bfq_deactivate_bfqq()->bfq_deactivate_entity()。bfqq因没有足够的配额派发IO请求而过期失效， bfq_bfqq_expire()函数的调用流程是bfq_bfqq_expire()->__bfq_bfqq_expire()->bfq_requeue_bfqq()->bfq_activate_requeue_entity()。

1.2 bfq_deactivate_entity()从st->active红黑树剔除entity

1. //把entity从st->active红黑树剔除
2. static void bfq_deactivate_entity(struct bfq_entity *entity,
3.                   bool ins_into_idle_tree,
4.                   bool expiration)
5. {
6.     //把entity从st->active 红黑树剔除，计算新的entity->finish把entity按照entity->>finish加入到st->active红黑树
7.     if (!__bfq_deactivate_entity(entity, ins_into_idle_tree))
8.     ...........
9.     //如果要从st->active红黑树剔除的entity是sd->next_in_service 指向的entity
10.     if (sd->next_in_service == entity)
11.          ///查找新的 next_in_service entity赋于sd->next_in_service
12.          bfq_update_next_in_service(sd, NULL, expiration);
13. }

bfq_deactivate_entity()中主要调用__bfq_deactivate_entity()和bfq_update_next_in_service()函数。__bfq_deactivate_entity()函数把entity从st->active红黑树剔除，bfq_update_next_in_service()函数选择下一次运行的entity赋于sd->next_in_service。先看下__bfq_deactivate_entity()源码，bfq_update_next_in_service()放最后讲解。

1. bool __bfq_deactivate_entity(struct bfq_entity *entity, bool ins_into_idle_tree)
2. {
3.     struct bfq_sched_data *sd = entity->sched_data;
4.     struct bfq_service_tree *st;
5.     bool is_in_service;
7.     //找到entiry所属st
8.     st = bfq_entity_service_tree(entity);
9.     //entity是sd正在使用的entity则is_in_service为true
10.     is_in_service = entity == sd->in_service_entity;
11.     //service是entity已经消耗的配额，除以weight得到entity已经消耗的虚拟运行时间，再加上entity->start得到entity->finish
12.     bfq_calc_finish(entity, entity->service);
13.     if (is_in_service)//把sd->in_service_entity指向的entity从红黑树剔除时，要把sd->in_service_entity清NULL
14.         sd->in_service_entity = NULL;
15.     else
16.         entity->service = 0;
17.     if (entity->tree == &st->active)//如果entity处于st->active树,从st->acitve tree剔除entity
18.         bfq_active_extract(st, entity);
19.     else if (!is_in_service && entity->tree == &st->idle)//如果entity处于st->idle树，并且entity不是st正在使用的entity
20.         bfq_idle_extract(st, entity);
21.     //ins_into_idle_tree为false则不会把entity再插入到st->idle,而是释放掉entity。或者st->vtime>=entity->finish也是释放掉entity
22.     if (!ins_into_idle_tree || !bfq_gt(entity->finish, st->vtime))
23.         bfq_forget_entity(st, entity, is_in_service);//entity不再被用到，释放bfqq,把entity剔除掉
24.     else
25.         bfq_idle_insert(st, entity);//把entity再插入st->idle树，并可能更新st->first_idle或st->last_idle
27.     return true;
28. }

__bfq_deactivate_entity()函数主要作用是：把entity从st->active或st->idle红黑树踢掉，ins_into_idle_tree为true则把entity再插入st->idle树，否则直接释放掉entity及bfqq。

1.3 bfq_activate_requeue_entity()把entity加入st->active红黑树

1. //把entity加入到st->active红黑树
2. static void bfq_activate_requeue_entity(struct bfq_entity *entity,
3.                     bool non_blocking_wait_rq,
4.                     bool requeue, bool expiration)
5. {
6.     //把entity加入到st->active红黑树
7.     __bfq_activate_requeue_entity(entity, sd, non_blocking_wait_rq);
8.     ///查找新的 next_in_service entity赋于sd->next_in_service
9.     if (!bfq_update_next_in_service(sd, entity, expiration) &&!requeue)
10.          break;
11. }

__bfq_activate_requeue_entity()函数主要调用__bfq_activate_requeue_entity()把entity加入st->active红黑树，然后也调用bfq_update_next_in_service()选择下一次运行的entity赋于sd->next_in_service。先看下__bfq_activate_requeue_entity()函数源码：

1. static void __bfq_activate_requeue_entity(struct bfq_entity *entity,
2.                       struct bfq_sched_data *sd,
3.                       bool non_blocking_wait_rq)
4. {
5.      //如果entity是调度器正在使用的entiry或entity处于st->active红黑树
6.     if (sd->in_service_entity == entity || entity->tree == &st->active)
7.          //根据entity->service计算entity的虚拟运行时间并累加到entity->finish，最后把entity按照新的entity->finish插入st->active红黑树
8.          __bfq_requeue_entity(entity);
9.     else//否则到这里说明entity 是新创建的
10.          //计算entity->start，按照entity->budget计算entity的虚拟运行时间并累加到entity->finish，把entity按照entity->finish插入st->active红黑树
11.          __bfq_activate_entity(entity, non_blocking_wait_rq);
12. }

该函数两个分支：如果entity是调度器正在使用的entiry或entity处于st->active树，然后根据entity->service计算entity的虚拟运行时间并累加到entity->finish，最后把entity按照新的entity->finish插入st->active红黑树。否则，entity及其bfqq是新创建的，计算entity->start，直接把entity插入st->active红黑树。这两个函数源码是：

1. //bfqq的entity之前就在st->active红黑树，这里根据entity->service计算entity的虚拟运行时间并累加到entity->finish，最后把entity按照新的entity->finish插入st->active红黑树
2. static void __bfq_requeue_entity(struct bfq_entity *entity)
3. {
4.     if (entity == sd->in_service_entity) {//entity是IO调度器正在使用的entity
5.         //根据entity->service/entity->weight计算entity已经消耗的虚拟运行时间，entity->start加上这段虚拟运行时间就是entity->finish
6.          bfq_calc_finish(entity, entity->service);
7.         //用entity->finish更新entity->start，重置了
8.          entity->start = entity->finish;
9.          if (entity->tree)//如果entity在st->active树，则从st->acitve tree剔除entity，下边再把entity加入st->active树
10.              bfq_active_extract(st, entity);
11.      }else{
12.              bfq_active_extract(st, entity);
13.      }
14.      //按照entity->budget计算entity的虚拟运行时间并累加到entity->finish，最后把entity按照新的entity->finish插入st->active红黑树
15.       bfq_update_fin_time_enqueue(entity, st, false);
16. }
18. //bfqq的entity是新创建的或者bfqq的entity之前在st->active红黑树，根据entity->budget计算entity的虚拟运行时间并累加到entity->finish，最后把entity按照新的entity->finish插入st->active红黑树
19. static void __bfq_activate_entity(struct bfq_entity *entity,
20.                   bool non_blocking_wait_rq)
21. {
22.     if (non_blocking_wait_rq && bfq_gt(st->vtime, entity->finish)) {
23.          backshifted = true;
24.          min_vstart = entity->finish;
25.     } else
26.          min_vstart = st->vtime;
28.     //entity现在处于st->active红黑树
29.     if (entity->tree == &st->idle) {
30.          //entity从st->active红黑树剔除掉，可能更新st->first_idle或st->last_idle
31.          bfq_idle_extract(st, entity);
32.          entity->start = bfq_gt(min_vstart, entity->finish) ?min_vstart : entity->finish;
33.     } else {//到这里说明entity之前不在st->idle或st->active红黑树，entity是新分配的也走这里
34.          entity->start = min_vstart;//更新entity->start
35.          //st->wsum调度类st的active和idle tree上所有entity的权重之和，累加每一个entity的entity->weight
36.          st->wsum += entity->weight;
37.     }
38.     //按照entity->budget计算entity的虚拟运行时间并累加到entity->finish，最后把entity按照新的entity->finish插入st->active红黑树
39.     bfq_update_fin_time_enqueue(entity, st, backshifted);
40. }

最后都是调用bfq_update_fin_time_enqueue()把entity插入st->active红黑树，看下它的源码：

1. //按照entity->budget计算entity的虚拟运行时间并累加到entity->finish，最后把entity按照新的entity->finish插入st->active红黑树
2. static void bfq_update_fin_time_enqueue(struct bfq_entity *entity,
3.                     struct bfq_service_tree *st,
4.                     bool backshifted)
5. {
6.      //这里简化成entity->finish=entity->start+entity->budget/entity->weight，用entity的配额得到entity->finish，注意是entity的配额
7.      bfq_calc_finish(entity, entity->budget);
8.     //把entity按照新的entity->finish插入st->active红黑树
9.      bfq_active_insert(st, entity);
10. }
12. //把entity按照新的entity->finish插入st->active红黑树
13. static void bfq_active_insert(struct bfq_service_tree *st,
14.                   struct bfq_entity *entity)
15. {
16.     //把entity按照entity->finish插入st->active红黑树，entity->finish越小entity在红黑树越靠左
17.     bfq_insert(&st->active, entity);
19.     if (node->rb_left)
20.         node = node->rb_left;
21.     else if (node->rb_right)
22.         node = node->rb_right;
23.    
24.     /*从entity的node所在节点，一直在红黑树向上得到它的parent节点，用entity->start更新这些红黑树节点的entity->min_start，同时也更新这些node在红黑树的左右子节点对应的entity的min_start。这个更新操作一直到根节点才结束*/
25.      bfq_update_active_tree(node);
26. }

1.4 bfq_set_in_service_queue()和bfq_get_next_queue()

1. static struct bfq_queue *bfq_set_in_service_queue(struct bfq_data *bfqd)
2. {
3.     //从sd->next_in_service取出entity赋于sd->in_service_entity，作为本次要使用的entity。然后查找一个新的entity赋于sd->next_in_service，作为下一次使用的entity
4.     struct bfq_queue *bfqq = bfq_get_next_queue(bfqd);
5.      //本质是 bfqd->in_service_queue = bfqq
6.      __bfq_set_in_service_queue(bfqd, bfqq);
7.      return bfqq;
8. }

bfq_set_in_service_queue()主要调用bfq_get_next_queue()函数：把sd->next_in_service赋值给sd->in_service_entity，sd->in_service_entity正是bfq调度器使用的entity，并且返回entity对应的bfqq。__bfq_set_in_service_queue()函数主要是把bfqq赋值给bfqd->in_service_queue，bfqd->in_service_queue正是bfq正在使用的bfqq。看下bfq_get_next_queue()函数源码：

1. //从sd->next_in_service取出entity赋于sd->in_service_entity，作为本次要使用的entity。然后查找一个新的entity赋于sd->next_in_service，作为下一次使用的entity
2. struct bfq_queue *bfq_get_next_queue(struct bfq_data *bfqd)
3. {
4.     for (; sd ; sd = entity->my_sched_data) {
5.         ///取出sd->next_in_service作为当前要使用的entity，赋值给sd->in_service_entity
6.          entity = sd->next_in_service;
7.          sd->in_service_entity = entity;
8.         //sd->in_service_entity这个entity作为bfq当前正在使用的entity，就要把entity从st->actvie tree剔除
9.          if (bfq_no_longer_next_in_service(entity))
10.              bfq_active_extract(bfq_entity_service_tree(entity),entity);
11.      }
12.      for_each_entity(entity) {
13.           struct bfq_sched_data *sd = entity->sched_data;
14.           ///查找新的 next_in_service entity赋于sd->next_in_service
15.           if (!bfq_update_next_in_service(sd, NULL, false))
16.               break;
17.      }
18. }

按照前文所说，该函数是从sd->next_in_service取出entity赋于sd->in_service_entity，作为本次要使用的entity。然后执行bfq_update_next_in_service()查找一个新的entity赋于sd->next_in_service，作为下一次使用的entity。bfq_update_next_in_service()前文已经提到了多次，下一小节讲解。

1.5 bfq_update_next_in_service()选择一个新的sd->next_in_service

看下bfq_update_next_in_service()函数重点代码，主要是调用bfq_lookup_next_entity()。

1. static bool bfq_update_next_in_service(struct bfq_sched_data *sd,
2.                        struct bfq_entity *new_entity,//new_entity有时是NULL，有时不是
3.                        bool expiration)//expiration为true说明是bfqq到期了，为false说明是其他情况，比如在bfq_update_next_in_service()
4. {
5.     struct bfq_entity *next_in_service = sd->next_in_service;
6.     bool parent_sched_may_change = false;
7.     bool change_without_lookup = false;
8. ………………
9.      //如果change_without_lookup为false则执行bfq_lookup_next_entity()选择下一个使用的bfqq的entity。可能找不到，则返回NULL
10.      if (!change_without_lookup)
11.           next_in_service = bfq_lookup_next_entity(sd, expiration);
12.     ........................
13.     //为sd->next_in_servic赋值下一次使用的bfqq的entity。如果前边没找到则sd->next_in_service被赋值NULL
14.      sd->next_in_service = next_in_service;
15.      return parent_sched_may_change;
16. }
18. static struct bfq_entity *bfq_lookup_next_entity(struct bfq_sched_data *sd,
19.                          bool expiration)
20. {
21.     //在sd调度器每个调度策略st里都搜索符合条件的 entity，都找不到返回NULL
22.     for (; class_idx < BFQ_IOPRIO_CLASSES; class_idx++) {
23.          entity = __bfq_lookup_next_entity(st + class_idx,sd->in_service_entity &&!expiration);
24.          if (entity)
25.              break;
26.     }
27.     return entity;
28. }
30. static struct bfq_entity *__bfq_lookup_next_entity(struct bfq_service_tree *st, bool in_service)
31. {
32.      //从st->active红黑树红黑树最左边查找entity->start最小并且entity->start小于vtime的entity
33.      entity = bfq_first_active_entity(st, new_vtime);
34.      return entity;
35. }

bfq_first_active_entity()函数主要是在st->active红黑树最左边查找一个entity->start最小并且entity->start小于st->vtime的entity，这就是要最终找到的合适的entity，接着就会赋值给sd->next_in_service。bfq_update_next_in_service()的调用主要有3处：

1：bfq_activate_bfqq() / bfq_requeue_bfqq() ->bfq_activate_requeue_entity()把entity加入st->active红黑树后，执行bfq_update_next_in_service()选择一个新的entity赋于sd->next_in_service，作为下次使用的entity。

2：bfq_del_bfqq_busy ()->bfq_deactivate_bfqq ()->bfq_deactivate_entity()从st->active红黑树剔除entity后，执行bfq_update_next_in_service()选择一个新的entity赋于sd->next_in_service，作为下次使用的entity。

:

3：派发IO请求过程执行到__bfq_dispatch_request ()->bfq_select_queue->bfq_set_in_service_queue()->bfq_get_next_queue()->bfq_update_next_in_service()函数，把sd->next_in_service赋于sd->in_service_entity后，执行bfq_update_next_in_service()选择一个新的entity赋于sd->next_in_service，作为下次使用的entity。

1.6 bfq_dispatch_rq_from_bfqq()派发IO请求的后半部分

最后看下bfq_dispatch_rq_from_bfqq()函数。

1. static struct request *bfq_dispatch_rq_from_bfqq(struct bfq_data *bfqd,
2.                          struct bfq_queue *bfqq)
3. {
4.      struct request *rq = bfqq->next_rq;
5.      unsigned long service_to_charge;
6.     //计算并返回本次传输req需要配额，配额以req要传输字节数为基准，同步和异步IO计算方法不一样。
7.      service_to_charge = bfq_serv_to_charge(rq, bfqq);
8.     //根据本次传输req的配额served，增加entity配额entity->service和调度器虚拟运行时间st->vtime
9.      bfq_bfqq_served(bfqq, service_to_charge);
10.     //计算新的bfqd->peak_rate，并选择一个新的req作为bfqq->next_rq，计算更新新的entity->budget，把req从bfqq->sort_list链表剔除
11.      bfq_dispatch_remove(bfqd->queue, rq);
12.    
13.      if (!(bfq_tot_busy_queues(bfqd) > 1 && bfq_class_idle(bfqq)))
14.          goto return_rq;
15. return_rq:
16.      return rq;//bfqq->next_rq作为本次派发的IO请求
17. }

bfq_dispatch_rq_from_bfqq()函数作用：从bfqq->next_rq选择为要派发IO请求，根据派发IO请求的数据量计算消耗的配额，累加到bfqq的entity->service和bfq调度器消耗的虚拟运行时间st->vtime。最后看下bfq_bfqq_served()函数：

1. //根据待派发req的配额served，增加entity配额entity->service和调度器虚拟运行时间st->vtime
2. void bfq_bfqq_served(struct bfq_queue *bfqq, int served)//served是当前要派发req消耗的配额
3. {
4.     …………
5.     bfqq->service_from_backlogged += served;
6.     for_each_entity(entity) {
7.          //取出entity指向的调度器实体st
8.          st = bfq_entity_service_tree(entity);
9.          //entity->service累加待派发req的配额served
10.          entity->service += served;
11.          //st->vtime累加待派发req的配额served除以st->wsum算出的虚拟运行时间
12.          st->vtime += bfq_delta(served, st->wsum);
13.         /*处理st->active红黑树的first_idle和last_idle，可能会把first_idle指向的entity从st->active红黑树剔除掉，释放掉它的bfqq和entity*/
14.          bfq_forget_idle(st);
15.     }
16. }

2：sd->next_in_service、sd->in_service_entity、bfqd->in_service_queue的使用与更新

第一节多次提到sd->next_in_service、sd->in_service_entity、bfqd->in_service_queue这3个变量，这一节主要介绍这3个变量的工作过程。sd->in_service_entity是bfq调度器当前正在使用的entity，bfqd->in_service_queue是bfq调度器正在使用的entity的bfqq，sd->next_in_service是bfq调度器下一次使用的entity。

派发IO请求执行到__bfq_dispatch_request->bfq_select_queue()函数，首先判断bfqd->in_service_queue是否为NULL，即 bfq是否有正在使用的bfqq。如果bfq没有正在使用的bfqq(bfqd->in_service_queue是NULL)，则要执行bfq_set_in_service_queue()把sd->next_in_service这个下一次使用的entity赋值给sd->in_service_entity。sd->in_service_entity正是bfq调度器正在使用的entity，bfqd->in_service_queue是该entity对应的bfqq。如果bfq_select_queue()函数中，bfqd->in_service_queue非NULL，即bfq有正在使用的bfqq，则从bfqq的IO队列取出要派发的IO请求(即bfqq->next_rq指向的IO请求)。

最后说下sd->next_in_service，sd->next_in_service的更新是在bfq_update_next_in_service()函数，主要有三处。bfq_deactivate_entity()函数中把entity从st->active红黑树剔除后，执行bfq_update_next_in_service()；bfq_activate_requeue_entity()函数中把entity加入st->active红黑树后，执行bfq_update_next_in_service()；派发IO请求__bfq_dispatch_request()->bfq_select_queue()函数中，bfqd->in_service_queue是NULL即bfq没有正在使用的bfqq，则执行bfq_set_in_service_queue()->bfq_get_next_queue()，把sd->next_in_service赋值给sd->in_service_entity，然后执行bfq_update_next_in_service()选择一个新的entity赋值给sd->next_in_service。

bfq_update_next_in_service()第1节介绍过，函数主要是从st->active红黑树最左边查找一个entity->start最小并且entity->start小于vtime的entity，这就是要最终找到的合适的entity，后边就会赋值给sd->next_in_service。

3：entity->start、entity->finish、entity->min_start的更新

3.1 entity->start的更新时机

entity->start是entity的起始虚拟运行时间，entity->finish是entity结束的虚拟运行时间。entity->start在什么时间更新呢？

1：在一个新的进程派发IO请求，分配创建新的bfqq后把bfqq的entity加入st->active红黑树函数流程：bfq_add_request()->bfq_bfqq_handle_idle_busy_switch()->bfq_add_bfqq_busy()->bfq_activate_bfqq()->bfq_activate_requeue_entity()->__bfq_activate_requeue_entity()->__bfq_activate_entity()，在__bfq_activate_entity()函数中，走了if (entity->tree == &st->idle)的else分支，用调度器的虚拟运行时间st->vtime赋值给entity->start。

2：在派发IO请求时，因为bfqq的配额消耗光而令bfqq过期失效过程__bfq_dispatch_request()->bfq_select_queue()->bfq_bfqq_expire()->__bfq_bfqq_expire()->bfq_requeue_bfqq()->bfq_activate_requeue_entity()->__bfq_activate_requeue_entity-> __bfq_requeue_entity()。在该函数中，执行bfq_calc_finish(entity, entity->service)用entity已经消耗的配额更新entity->finish，即entity->finish = entity->start + bfq_delta(service, entity-> service)，然后entity->start = entity->finish用entity->finish更新entity->start。

3：entity之前因为没有派发的IO请求过期失效而从st->active红黑树移动到st->active红黑树，然后又要派发派entity的bfqq上的IO请求，而把entity激活，函数流程是bfq_add_request()->bfq_bfqq_handle_idle_busy_switch()->bfq_add_bfqq_busy()->bfq_activate_bfqq()->bfq_activate_requeue_entity()->__bfq_activate_requeue_entity()->__bfq_activate_entity()，在__bfq_activate_entity()函数中，走了if (entity->tree == &st->idle)分支，用entity->finish和st->vtime更新entity->start。

3.2 entity->finish的更新时机

首先，entity加入st->active红黑树或者st->active红黑树时，都是按照entity->finish由小到大从左到右而排列。就是说，entity->finish越小，entity在st->active红黑树或者st->active红黑树越靠左。entity->finish的更新是在bfq_calc_finish()函数，如下：

1. static void bfq_calc_finish(struct bfq_entity *entity, unsigned long service)
2. {  //service是entity->budget或entity->service
3.      struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
4.      entity->finish = entity->start + bfq_delta(service, entity->weight);
5. }

函数形参service是entity已经消耗的配额或者entity的权重，这个计算可以简化成entity->finish = entity->start + service*N/entity->weight(N是个常数)。显然，entity->finish可以等同于entity->start+entity消耗的配额。

什么时机会调用到bfq_calc_finish()函数呢？

1：在派发IO请求时，因为bfqq的配额消耗光而令bfqq过期失效过程__bfq_dispatch_request()->bfq_select_queue()->bfq_bfqq_expire()->__bfq_bfqq_expire()->bfq_requeue_bfqq()->bfq_activate_requeue_entity()->__bfq_activate_requeue_entity-> __bfq_requeue_entity()。在该函数中，执行bfq_calc_finish(entity, entity->service)。用entity已经消耗的配额，乘以N再除以entity权重weight得到entity已经消耗的虚拟运行时间(N是个常数)，再加上entity->start得到entity->finish。

2：在派发IO请求时，因为bfqq上没有要派发的IO请求而令bfqq过期失效过程__bfq_dispatch_request()->bfq_select_queue()->bfq_bfqq_expire()->__bfq_bfqq_expire()->bfq_del_bfqq_busy()->bfq_deactivate_bfqq()->bfq_deactivate_entity()->__bfq_deactivate_entity()。在__bfq_deactivate_entity()函数中，执行bfq_calc_finish(entity, entity->service)，用 entity已经消耗的配额，乘以N再除以entity权重weight得到entity已经消耗的虚拟运行时间(N是个常数)，再加上entity->start得到entity->finish。

3：bfq_update_fin_time_enqueue()函数中，执行bfq_calc_finish(entity, entity->budget)。用entity的权重，乘以N再除以entity权重weight得到entity已经消耗的虚拟运行时间(N是个常数)，再加上entity->start得到entity->finish。然后执行bfq_active_insert(st, entity)把entity按照最新的entity->finish加入st->active红黑树。

需要说明一点，__bfq_requeue_entity()和__bfq_requeue_entity()都是执行bfq_calc_finish(entity, entity->service)，用 entity已经消耗的配额，乘以N再除以entity权重weight得到entity已经消耗的虚拟运行时间(N是个常数)，再加上entity->start得到entity->finish。而bfq_update_fin_time_enqueue()函数中，是用entity的权重，乘以N再除以entity权重weight得到entity已经消耗的虚拟运行时间(N是个常数)，再加上entity->start得到entity->finish。这是个很明显的区别。

还要说明一点，bfq_update_fin_time_enqueue()函数的调用有两个时机，一个是执行__bfq_dispatch_request()->bfq_select_queue()->bfq_bfqq_expire()->__bfq_bfqq_expire()->bfq_requeue_bfqq()->bfq_activate_requeue_entity()->__bfq_activate_requeue_entity-> __bfq_requeue_entity()->bfq_update_fin_time_enqueue()，把entity重新插入st->active红黑树最后，执行bfq_update_fin_time_enqueue()。

另一个时机是把一个新创建的bfqq的entity加入st->active红黑树或者把一个处于st->active红黑树的entity激活加入到st->active红黑树，函数流程是bfq_add_request()->bfq_bfqq_handle_idle_busy_switch()->bfq_add_bfqq_busy()->bfq_activate_bfqq()->bfq_activate_requeue_entity()->__bfq_activate_requeue_entity()->__bfq_activate_entity()->bfq_update_fin_time_enqueue()，__bfq_activate_entity()函数最后执行bfq_update_fin_time_enqueue()把entity插入st->active红黑树。

3.3 entity->min_start的更新时机

entity->min_start的更新在bfq_update_active_tree()函数，有两个时机：在entity从st->active 剔除最后执行的bfq_active_extract()函数和entity加入st->active红黑树最后执行的bfq_active_insert()函数。看下源码

1. //把entity按照新的entity->finish插入st->active红黑树
2. static void bfq_active_insert(struct bfq_service_tree *st,
3.                   struct bfq_entity *entity)
4. {
5.     ………………..
6.     //把entity按照entity->finish插入st->active红黑树，entity->finish越小entity在红黑树越靠左
7.     bfq_insert(&st->active, entity);
8.     /*从entity的node所在节点，一直在红黑树向上得到它的parent节点，用entity->start更新这些红黑树节点的entity->min_start，同时也更新这些node在红黑树的左右子节点对应的entity的min_start。这个更新操作一直到根节点才结束*/
9.     bfq_update_active_tree(node);
10. }

1. //从st->acitve tree剔除entity
2. static void bfq_active_extract(struct bfq_service_tree *st,
3.                    struct bfq_entity *entity)
4. {
5.     //返回entity所属红黑树下边的entiry对应节点
6.     node = bfq_find_deepest(&entity->rb_node);
7.     //把entiry从st active tree剔除
8.     bfq_extract(&st->active, entity);
9.     /*从entity的node所在节点，一直在红黑树向上得到它的parent节点，更新这些红黑树节点对应的bfq_entity的成员min_start，同时也更新这些node在红黑树的左右子节点对应的entity的min_start。这个更新操作一直到根节点才结束*/
10.      if (node)
11.          bfq_update_active_tree(node);
12. }

bfq_update_active_tree()函数源码如下：

1. /*从entity的node所在节点，一直在红黑树向上得到它的parent节点，更新这些红黑树节点对应的bfq_entity的成员min_start，同时也更新这些node在红黑树的左右子节点对应的entity的min_start。这个更新操作一直到根节点才结束*/
2. static void bfq_update_active_tree(struct rb_node *node)
3. {
4.     struct rb_node *parent;
5. up:
6.      //先更新当前node对应的entity的min_start
7.       bfq_update_active_node(node);
8.       parent = rb_parent(node);
9.       if (!parent)//更新entity的min_start，直到entity红黑树根节点才return返回
10.           return;
11.     //如果node这个entity是父节点parent的左节点，则更新parent节点的右节点对应的entity的min_start
12.       if (node == parent->rb_left && parent->rb_right)
13.            bfq_update_active_node(parent->rb_right);
14.       else if (parent->rb_left)//否则说明node这个entity是父节点parent的右节点，则更新parent节点的左节点对应的entity的min_start
15.           bfq_update_active_node(parent->rb_left);//更新entity->min_start
16.     node = parent;
17.     goto up;
18. }
20. //先把entity->start赋值给entity->min_start，如果entity在红黑树下边的左右子节点的entity的min_start更小，再重新赋值给entity->min_start
21. static void bfq_update_active_node(struct rb_node *node)
22. {
23.       struct bfq_entity *entity = rb_entry(node, struct bfq_entity, rb_node);
24.     //用entity->start更新entity->min_start
25.       entity->min_start = entity->start;
26.     //如果当前entity在红黑树下边的左子节点的entity的min_start更小，则赋值给当前entity的min_start
27.       bfq_update_min(entity, node->rb_right);
28.     //如果当前entity在红黑树下边的右子节点的entity的min_start更小，则赋值给当前entity的min_start
29.       bfq_update_min(entity, node->rb_left);
30. }

从entity的node所在节点，一直在红黑树向上得到它的parent节点，更新这些红黑树节点对应的bfq_entity的成员min_start，同时也更新这些node在红黑树的左右子节点对应的entity的min_start。这个更新操作一直到根节点才结束。

4：entity->service、st->vtime的更新和使用

entity->service是entity已经消耗的配额，st->vtime是bfq调度器的虚拟运行时间。在派发IO请求时，__bfq_dispatch_request()->bfq_dispatch_rq_from_bfqq()，先执行bfq_serv_to_charge()根据本次派发的IO请求bfqq->next_rq需要传输的字节数，计算需要消耗的配额served。然后执行到bfq_bfqq_served()函数，执行里边的entity->service += served把served累加到entity->service，同时执行st->vtime += bfq_delta(served, st->wsum)，等同于st->vtime += served*N/ st->wsum(N是个常数)，其实就是根据本次派发的IO请求消耗的配额累加到st->vtime。

显然，每派发一个IO请求，都要根据派发的IO请求消耗的配额，累加到entity->service，累计到st->vtime，entity->service和st->vtime随着派发IO请求个数增加而累加。

每派发调度器一个entity的一个IO请求，都要计算派发的IO请求的消耗的配额 (使用served*N/ st->wsum计算，N是一个常数)，然后累计到调度器的虚拟运行时间st->vtime。简单说st->vtime= (bfqq1派发的IO请求消耗的配额之和+ bfqq2的派发的IO请求消耗的配额之和+……….+bfqqN的派发的IO请求消耗的配额之和) /(bfqq1的entity的权重+ bfqq1的entity的权重+………+bfqqN的entity的权重)。

5：为什么bfq有利交互式进程IO快速响应

首先，一个新的进程派发IO请求前，会分配一个新的bfqq，然后把这个新创建的bfqq的entity加入st->active红黑树，函数流程是bfq_add_request()->bfq_bfqq_handle_idle_busy_switch()->bfq_add_bfqq_busy()->bfq_activate_bfqq()->bfq_activate_requeue_entity()->__bfq_activate_requeue_entity()->__bfq_activate_entity()，把__bfq_activate_entity()源码简化下：

1. static void __bfq_activate_entity(struct bfq_entity *entity,
2.                   bool non_blocking_wait_rq)
3. {
4.      if (non_blocking_wait_rq && bfq_gt(st->vtime, entity->finish)) {
5.          backshifted = true;
6.          min_vstart = entity->finish;
7.     } else
8.          min_vstart = st->vtime;
9.     ……………………..
10.       entity->start = min_vstart;//更新entity->start
11.     //st->wsum调度类st的active和idle tree上所有entity的权重之和，累加每一个entity的entity->weight
12.      st->wsum += entity->weight;
13.     //按照entity->budget计算entity的虚拟运行时间并累加到entity->finish，最后把entity按照新的entity->finish插入st->active红黑树
14.      bfq_update_fin_time_enqueue(entity, st, backshifted);
15. }

重点是用st->vtime 更新entity->start，然后执行bfq_update_fin_time_enqueue()，按照entity的初始权重entity->budget计算entity的虚拟运行时间并累加到entity->finish，最后把entity按照新的entity->finish插入st->active红黑树。这样可以保证entity的entity->start和entity->finish尽可能小，entity尽可能靠左插入到st->active红黑树。

然后在bfq_update_next_in_service()->bfq_lookup_next_entity()->__bfq_lookup_next_entity->bfq_first_active_entity()函数流程，在st->active红黑树选择一个最符合条件的entity即sd->next_in_service时。哪个entity最符合条件呢？是st->active红黑树最左边并且entity->start最小并且entity->start小于st->vtime的entity。一个entity的entity->finish越小在st->active红黑树 越靠左，entity->start越小越容易符合小于st->vtime的条件。因此新派发IO请求的进程创建的bfqq的entity插入st->active红黑树后，更容易在bfq_update_next_in_service()函数中选中被赋于sd->next_in_service。

bfq_update_next_in_service()的执行时机主要有3个，第1节有解过。

然后，等__bfq_dispatch_request()->bfq_select_queue()派发IO请求时，bfqd->in_service_queue这个正在的使用的bfqq过期失效，执行bfq_bfqq_expire()令bfqd->in_service_queue这个bfqq失效，然后执行bfq_set_in_service_queue()->bfq_get_next_queue()，把sd->next_in_service赋于sd->in_service_entity，sd->in_service_entity是bfq调度器当前使用的entity。然后返回sd->in_service_entity这个entity对应的bfqq。接着回到__bfq_set_in_service_queue()函数，执行bfqd->in_service_queue = bfqq，bfqd->in_service_queue是bfq当前使用的bfqq。好了，刚才那个新进程派发IO请求，创建的bfqq终于被bfq调度器使用到了，接着就可以派发这个进程的IO请求了。

6：st->first_idle 和 st->last_idle的更新

先把前文使用的贴图发下(为了演示简单，没有演示entity在红黑树中的树形排列形式，只是演示entity按照entity->finish由小到大从左向右排列)

 一个新bfqq的entity是先加入的st->active 红黑树，后续如果该bfqq没有要派发的IO请求了，则把该bfqq的entity移动到st->idle红黑树。st->idle红黑树上entity是按照entity->finish由小到大从左向右排列。st->first_idle指向st->idle红黑树entity->finish最小的entity， st-> last_idle指向st->idle红黑树entity->finish最大的entity。下边把用到st->first_idle和st-> last_idle的函数源码列下：

把entity从st->active红黑树剔除的函数流程bfq_deactivate_entity()->__bfq_deactivate_entity()->bfq_idle_extract()

1. //entity从st->active红黑树剔除掉，可能更新st->first_idle或st->last_idle
2. static void bfq_idle_extract(struct bfq_service_tree *st,
3.                  struct bfq_entity *entity)
4. {
5.     struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
6.     struct rb_node *next;
7.     /*entity是st->first_idle指向的entity，即st->idle红黑树最左边的entity。因为entiry要从st->active红黑树剔除，则选择entity右边的entity赋于st->first_idle*/
8.     if (entity == st->first_idle) {
9.          next = rb_next(&entity->rb_node);
10.          st->first_idle = bfq_entity_of(next);
11.     }
12.     /*entity是st->last_idle指向的entity，即st->idle红黑树最右边的entity。因为entiry要从st->active红黑树剔除，则选择entity左边的entity赋于st->last_idle*/
13.     if (entity == st->last_idle) {
14.          next = rb_prev(&entity->rb_node);
15.          st->last_idle = bfq_entity_of(next);
16.     }
17.     //entity从st->active红黑树剔除掉
18.     bfq_extract(&st->idle, entity);
19.     if (bfqq)
20.          list_del(&bfqq->bfqq_list);
21. }

把entity从st->active红黑树剔除，然后加入st->idle红黑树的函数流程bfq_deactivate_entity()->__bfq_deactivate_entity()->bfq_idle_insert()。

1. //把entity插入st->idle树，并可能更新st->first_idle或st->last_idle
2. static void bfq_idle_insert(struct bfq_service_tree *st,
3.                 struct bfq_entity *entity)
4. {
5.     struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
6.     struct bfq_entity *first_idle = st->first_idle;
7.     struct bfq_entity *last_idle = st->last_idle;
8.     //st->idle红黑树的最左边的entiry的finish最小，最右边的entity的finish最大。
9.    
10.     //st->first_idle记录entity->finish最小的entity，就是st->idle红黑树最靠左的entity
11.     if (!first_idle || bfq_gt(first_idle->finish, entity->finish))
12.         st->first_idle = entity;
13.     //st->last_idle记录entity->finish最大的entity，就是st->idle红黑树最靠右的entity
14.     if (!last_idle || bfq_gt(entity->finish, last_idle->finish))
15.         st->last_idle = entity;
16.     //把entity按照entity->finish插入st->idle红黑树，entity->finish越小entity在红黑树越靠左
17.     bfq_insert(&st->idle, entity);
19.     if (bfqq)//加入st->idle 的红黑树都加入到bfqd->idle_list链表
20.         list_add(&bfqq->bfqq_list, &bfqq->bfqd->idle_list);
21. }

派发IO请求时执行__bfq_dispatch_request ()->bfq_dispatch_rq_from_bfqq ()->bfq_bfqq_served()->bfq_forget_idle()，释放掉st->first_idle指向的entity。

1. //处理st->active红黑树的first_idle和last_idle，可能会把first_idle指向的entity从st->active红黑树剔除掉，释放掉它的bfqq和entity
2. static void bfq_forget_idle(struct bfq_service_tree *st)
3. {
4.     struct bfq_entity *first_idle = st->first_idle;
5.     struct bfq_entity *last_idle = st->last_idle;
6.     //st->active红黑树空并且last_idle->finish小于st->vtime则if成立，
7.     if (RB_EMPTY_ROOT(&st->active) && last_idle &&
8.         !bfq_gt(last_idle->finish, st->vtime)) {
9.         st->vtime = last_idle->finish;
10.     }
11.     //first_idle非空，并且st->vtime大于first_idle->finish则if成立
12.     if (first_idle && !bfq_gt(first_idle->finish, st->vtime))
13.         //first_idle指向的entity从st->active红黑树剔除掉，如果不再被用到，释放掉它的bfqq和entity
14.         bfq_put_idle_entity(st, first_idle);
15. }

bfq_forget_idle()函数需要重点说下，当st->first_idle->finish小于st->vtime，该函数会执行bfq_put_idle_entity()释放掉st->first_idle指向的entity。st->vtime随着派发一个又一个IO请求而不断增加，st->vtime大于st->first_idle->finish是迟早的事。讲到这里，感觉bfq还是有很多知识点没有讲通，后续再慢慢更新吧……..水平有限，如有错误请指正。

最后说下测试经验：为了能复现多个进程的bfqq同时存在st->active红黑树，然后在st->active红黑树中查找st->start最小的entity，fio测试时的参数iodepth要很大，numjobs也要尽可能多，如下：

fio -filename=/mnt/ext4/fio_test -direct=1 -iodepth 80 -thread -rw=randrw -rwmixread=50 -ioengine=libaio -bs=64k -size=10G -numjobs=6 -runtime=180 -group_reporting -name=test。同时，也要有脏页回写进程在频繁刷IO。