内核block层IO调度器—bfq算法之2源码详解

内核block层IO调度器—bfq算法之2源码详解"/>

内核block层IO调度器—bfq算法之2源码详解

在前一篇《内核block层IO调度器—bfq算法之1整体流程介绍》文章的基础上，本文主要讲解bfq算法内核源码，建议先看看前一篇文章。本文基于centos 8.3，内核版本4.18.0-240.el8，详细源码注释见 .18.0-240.el8。

相对于deadline算法，bfq算法真的复杂，源码相当繁杂。我们先从bfq算法注册给block层的接口函数开始讲解：

1. static struct elevator_type iosched_bfq_mq = {
2.     .ops = {
3.         .limit_depth        = bfq_limit_depth,
4.         .prepare_request    = bfq_prepare_request,
5.         .requeue_request        = bfq_finish_requeue_request,
6.         .finish_request     = bfq_finish_requeue_request,
7.         .exit_icq       = bfq_exit_icq,
8.         .insert_requests    = bfq_insert_requests,//插入req
9.         .dispatch_request   = bfq_dispatch_request,//派发req
10.         .next_request       = elv_rb_latter_request,
11.         .former_request     = elv_rb_former_request,
12.         .allow_merge        = bfq_allow_bio_merge,
13.         .bio_merge      = bfq_bio_merge,
14.         .request_merge      = bfq_request_merge,
15.         .requests_merged    = bfq_requests_merged,
16.         .request_merged     = bfq_request_merged,
17.         .has_work       = bfq_has_work,
18.         .depth_updated      = bfq_depth_updated,
19.         .init_hctx      = bfq_init_hctx,
20.         .init_sched     = bfq_init_queue,
21.         .exit_sched     = bfq_exit_queue,
22.     },
23.     ...................
24. };

这么多接口函数，主要用到的bfq_insert_requests()和bfq_dispatch_request()。前者是把IO请求插入到bfq算法队列，后者是从bfq算法队列取出IO请求并派发给磁盘驱动，本文也主要介绍这两个函数。说明一点，bfq函数繁多，为了方便介绍，删减了一部分代码。

正式开讲前，还是再说明一点，bfq关键数据结构在内核源码和本文都是以简称出现，如下：

• 1：bfq_data简称bfqd
• 2：bfq_queue简称bfqq
• 3：bfq_entity简称entity
• 4：bfq_service_tree简称st
• 5：bfq_sched_data简称sd
• 6：IO请求request结构简称req

1: bfq_insert_request函数

bfq_insert_requests()里主要是执行bfq_insert_request()，这里先把bfq_insert_request()函数流程示意图贴下：

 bfq_insert_request()函数源码如下：

1. static void bfq_insert_request(struct blk_mq_hw_ctx *hctx, struct request *rq,
2.                    bool at_head)
3. {
4.      /*先查找rq->elv.priv[1]中是否有bfqq，有的话直接从取出返回。否则再尝试通过bic->bfqq[is_sync]得到bfqq，失败则针对异步或者同步IO分配新的bfqq并初始化。这里边有 rq->elv.priv[1] = bfqq*/
5.      bfqq = bfq_init_rq(rq);
6.      ...........
7.     //req插入bfqq->sort_list和bfqq->fifo链表，并选择设置下一次派发的req于bfqq->next_rq。可能激 活bfqq，把bfqq添加到st->active红黑树
8.      idle_timer_disabled = __bfq_insert_request(bfqd, rq);
9.      //这里是通过 rq->elv.priv[1] 再得到bfqq
10.      bfqq = RQ_BFQQ(rq);
11. }

bfq_insert_request()里主要是执行bfq_init_rq()和__bfq_insert_request()两个函数。bfq_init_rq()主要是为当前进程分配一个bfqq，__bfq_insert_request()主要是把IO请求req插入到bfq的算法队列里，并把bfqq插入到st->active红黑树，算是把bfqq激活。二者源码下边一一介绍。

1.1:bfq_init_rq函数

bfq_init_rq()函数源码如下：

1. static struct bfq_queue *bfq_init_rq(struct request *rq)
2. {
3.     //新的req插入时，先查找rq->elv.priv[1]中是否有bfqq，有的话直接从取出返回，rq->elv.priv[1]本身保存的是req所属的bfqq
4.     if (rq->elv.priv[1])
5.           return rq->elv.priv[1];//找到bfqq直接return，否则下边分配新的bfqq
6.     //由rq->elv.icq得到bic
7.      bic = icq_to_bic(rq->elv.icq);
8.      ...........
9.     //先尝试通过bic->bfqq[is_sync]得到bfqq，失败则针对异步或者同步IO分配新的bfqq，然后并初始化
10.     bfqq = bfq_get_bfqq_handle_split(bfqd, bic, bio, false, is_sync,
11.                      &new_queue);//新分配一个new_queue则new_queue设置true
12.     ..........
13.     rq->elv.priv[0] = bic;//rq->elv.priv[0]指向bic
14.     rq->elv.priv[1] = bfqq;//rq->elv.priv[1]指向bfqq
15.     ............
16.     return bfqq;
17. }

先查找rq->elv.priv[1]中是否有bfqq,有的话直接从取出返回，失败则执行bfq_get_bfqq_handle_split()分配新的bfqq并初始化。

1.2: bfq_get_bfqq_handle_split函数

bfq_get_bfqq_handle_split()函数源码如下：

1. static struct bfq_queue *bfq_get_bfqq_handle_split(struct bfq_data *bfqd,
2.                            struct bfq_io_cq *bic,
3.                            struct bio *bio,
4.                            bool split, bool is_sync,
5.                            bool *new_queue)
6. {
7.     //先尝试由 bic->bfqq[]得到bfqq
8.     struct bfq_queue *bfqq = bic_to_bfqq(bic, is_sync);
10.     //由bic得到的bfqq存在直接返回bfqq
11.      if (likely(bfqq && bfqq != &bfqd->oom_bfqq))
12.         return bfqq;
13.     //到这里说明肯定要执行bfq_get_queue()分配一个新的bfqq，则new_queue设置true
14.     if (new_queue)
15.         *new_queue = true;
16.     if (bfqq)
17.         bfq_put_queue(bfqq);
18.      //针对异步或者同步IO分配bfqq，并初始化bfqq和entity
19.      bfqq = bfq_get_queue(bfqd, bio, is_sync, bic);
20.      //新分配的bfqq设置到bic->bfqq[is_sync]数组
21.      bic_set_bfqq(bic, bfqq, is_sync);//bic->bfqq[is_sync] = bfqq
22.      ..............
23.      return bfqq;
24. }

这个函数先尝试通过bic->bfqq[is_sync]得到bfqq，失败则调用bfq_get_queue()分配一个新的bfqq。bfq_get_queue()函数下边讲解。

1.3 :bfq_get_queue函数

bfq_get_queue()函数如下：

1. //针对异步或者同步IO分配bfqq，并初始化bfqq和entity
2. static struct bfq_queue *bfq_get_queue(struct bfq_data *bfqd,
3.                        struct bio *bio, bool is_sync,
4.                        struct bfq_io_cq *bic)
5. {
6.     ........
7.     if (!is_sync) {
8.         //异步IO时，从这里得到一个新的异步bfqq
9.         async_bfqq = bfq_async_queue_prio(bfqd, bfqg, ioprio_class,
10.                           ioprio);
11.         bfqq = *async_bfqq;
12.         if (bfqq)
13.             goto out;
14.     }
15.     //同步IO，在这里分配一个新的同步 bfqq
16.     bfqq = kmem_cache_alloc_node(bfq_pool,
17.                      GFP_NOWAIT | __GFP_ZERO | __GFP_NOWARN,
18.                      bfqd->queue->node);
19.         if (bfqq) {
20.             //bfqq初始化
21.             bfq_init_bfqq(bfqd, bfqq, bic, current->pid,
22.                       is_sync);
23.             //bfqq的entity初始化
24.             bfq_init_entity(&bfqq->entity, bfqg);
25.         }  
26.     ............
27.     return bfqq;
28. }

bfq_get_queue()函数调用bfq_async_queue_prio()或kmem_cache_alloc_node()分配一个新的bfqq，然后调用bfq_init_bfqq()和bfq_init_entity()对bfqq和bfqq的entity初始化。下边讲解__bfq_insert_request()函数。

2:__bfq_insert_request函数

__bfq_insert_request()函数源码如下：

1. static bool __bfq_insert_request(struct bfq_data *bfqd, struct request *rq)
2. {
3.     //通过 rq->elv.priv[1] 再得到bfqq，为req分配新的bfqq后，会把bfqq暂存在 rq->elv.priv[1]
4.      struct bfq_queue *bfqq = RQ_BFQQ(rq),
5.      ...........
6.      //把req添加到bfqq->sort_list链表，并选择合适的req赋于bfqq->next_rq。可能激活bfqq，把bfqq添加到st->active红黑树
7.      bfq_add_request(rq);
8.     //计算req的fifo超时时间
9.      rq->fifo_time = ktime_get_ns() + bfqd->bfq_fifo_expire[rq_is_sync(rq)];
10.     //req插入bfqq->fifo链表，超时派发
11.      list_add_tail(&rq->queuelist, &bfqq->fifo);
12.     //没啥重点操作，里边可能会执行到bfq_bfqq_expire()
13.      bfq_rq_enqueued(bfqd, bfqq, rq);
14. }

重点是执行bfq_add_request()函数，把IO请求req添加到bfqq->sort_list链表，并选择合适的IO请求req赋于bfqq->next_rq。另一个重点是，该函数里会激活bfqq，把bfqq添加到st->active红黑树，下文讲解。

2.1:bfq_add_request和bfq_bfqq_handle_idle_busy_switch函数

bfq_add_request()函数源码如下：

1. //把req添加到bfqq->sort_list链表，并选择合适的req赋于bfqq->next_rq
2. static void bfq_add_request(struct request *rq)
3. {
4.     //通过rq->elv.priv[1]得到保存的bfqq
5.     struct bfq_queue *bfqq = RQ_BFQQ(rq);
6.     bfqq->queued[rq_is_sync(rq)]++;
7.     bfqd->queued++
8.     //bfq_add_request()中把req添加到bfqq->sort_list链表
9.     elv_rb_add(&bfqq->sort_list, rq);
10.     //第一次插入req时，bfqq->next_rq是NULL，
11.     prev = bfqq->next_rq;
12.     //从bfqq->next_rq和rq选个一个合适的req作为下次优先派发的req
13.     next_rq = bfq_choose_req(bfqd, bfqq->next_rq, rq, bfqd->last_position);
14.     //下次优先派发req
15.     bfqq->next_rq = next_rq;
16.     .............
17.     if (!bfq_bfqq_busy(bfqq))//重点操作是把bfqq插入到st->active红黑树
18.           bfq_bfqq_handle_idle_busy_switch(bfqd, bfqq, old_wr_coeff,rq, &interactive);
19. }

这个函数开头主要是把IO请求添加到各种链表，选择下次最合适派发的IO请求赋值给bfqq->next_rq。重点是，如果bfqq的entity不在st->active红黑树(比如是新分配的bfqq，或者bfqq的entity处于st->idle红黑树)，则执行bfq_bfqq_handle_idle_busy_switch()函数把bfqq添加到st->active红黑树。bfq_bfqq_handle_idle_busy_switch()函数源码如下：

1. //重点操作是把bfqq的entity插入到st->active红黑树
2. static void bfq_bfqq_handle_idle_busy_switch(struct bfq_data *bfqd,
3.                          struct bfq_queue *bfqq,
4.                          int old_wr_coeff,
5.                          struct request *rq,
6.                          bool *interactive)
7. {
8.      .............
9.      bfq_clear_bfqq_just_created(bfqq);
10.      .............
11.      bfq_clear_bfqq_softrt_update(bfqq);
12.      //把bfqq插入到st->active红黑树，标记bfqq busy
13.      bfq_add_bfqq_busy(bfqd, bfqq);
14. }

bfq_bfqq_handle_idle_busy_switch()函数主要是执行bfq_add_bfqq_busy()函数，下文讲解。

2.2: bfq_add_bfqq_busy函数

bfq_add_bfqq_busy()函数源码如下：

1. //把bfqq插入到st->active红黑树，标记bfqq busy
2. void bfq_add_bfqq_busy(struct bfq_data *bfqd, struct bfq_queue *bfqq)
3. {
4.     //把bfqq插入到st->active红黑树
5.     bfq_activate_bfqq(bfqd, bfqq);
6.     //标记bfqq busy
7.     bfq_mark_bfqq_busy(bfqq);
8.     //每向st->active红黑树添加一个bfqq，bfqq对应调度算法的bfqd->busy_queues[]成员加1
9.     bfqd->busy_queues[bfqq->ioprio_class - 1]++;
10.     ...........
11. }

该函数是先执行bfq_activate_bfqq()把bfqq插入到st->active红黑树，然后执行bfq_mark_bfqq_busy()标记bfqq busy。显然只要bfqq添加到bfq调度器相关的st->active红黑树，则就会标记bfqq busy，前文if (!bfq_bfqq_busy(bfqq))是判断bfqq是否busy。下文重点介绍bfq_activate_bfqq()函数。

3 :bfq_activate_bfqq和bfq_activate_requeue_entity函数

先把bfq_activate_bfqq()函数流程图发下：

bfq_activate_bfqq()函数源码如下：

1. void bfq_activate_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq)
2. {
3.      struct bfq_entity *entity = &bfqq->entity;
4.      //把bfqq插入到st->active红黑树
5.      bfq_activate_requeue_entity(entity, bfq_bfqq_non_blocking_wait_rq(bfqq),false, false);
6.      bfq_clear_bfqq_non_blocking_wait_rq(bfqq);
7. }

主要还是执行bfq_activate_requeue_entity()函数，源码如下：

1. static void bfq_activate_requeue_entity(struct bfq_entity *entity,
2.                     bool non_blocking_wait_rq,
3.                     bool requeue, bool expiration)
4. {
5.      struct bfq_sched_data *sd;
6.      for_each_entity(entity) {
7.          sd = entity->sched_data;
8.       /*如果entity是调度器正在使用的entiry或entity处于st->active红黑树,计算entity的虚拟运行时间并累加到entity->finish，把entity按照新的entity->finish插入st->active红黑树。否则计算新的entity->start，按照entity->budget计算entity的虚拟运行时间并累加到entity->finish，最后把entity按照entity->finish插入st->active红黑树*/
9.          __bfq_activate_requeue_entity(entity, sd, non_blocking_wait_rq);
10.         //从st查找合适的entity并更新到sd->next_in_service，作为下次派发IO请求优先使用的bfqq，没有找到则返回NULL
11.          if (!bfq_update_next_in_service(sd, entity, expiration) &&
12.               !requeue)
13.              break;
14.      }
15. }

bfq_activate_requeue_entity()函数，源码注释说的比较清楚。这里再简单总结一下： __bfq_activate_requeue_entity()函数本质是计算entity的entity->start 和 entity->finish，entity->start是entity的起始虚拟运行时间，来自bfq调度器的虚拟运行时间st->vtime(这个下文讲解)。我的理解entity->start就是entity插入st->active红黑树时的bfq调度器虚拟运行时间。entity->finish是entity的结束虚拟运行时间，可以简单理解成entity->finish=entity->start + entity消耗的配额/权重，这点下文也有讲解。entiry是按是entity->finish由小到大在红黑树里从左向右排列。bfq_update_next_in_service()函数从st查找合适的entity并更新到sd->next_in_service。

3.1:__bfq_activate_requeue_entity函数

__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或bfqq所属调度类对应的bfq_service_tree结构
6.      struct bfq_service_tree *st = bfq_entity_service_tree(entity);
7.     //如果entity是bfq调度器正在使用的entiry或entity处于st->active红黑树
8.      if (sd->in_service_entity == entity || entity->tree == &st->active)
9.         /*计算entity的虚拟运行时间并累加到entity->finish，最后把entity按照新的entity->finish插入st->active红黑树*/
10.            __bfq_requeue_entity(entity);
11.      else
12.         /*计算新的entity->start，按照entity->budget计算entity的虚拟运行时间并累加到entity->finish，把entity按照entity->finish插入st->active红黑树*/
13.            __bfq_activate_entity(entity, non_blocking_wait_rq);
14. }

__bfq_activate_requeue_entity()函数主要有两个分支：

1：如果entity是调度器正在使用的entiry或entity处于st->active红黑树,计算entity的虚拟运行时间并累加到entity->finish，把entity按照新的entity->finish插入st->active红黑树

2：否则计算新的entity->start，按照entity->budget计算entity的虚拟运行时间并累加到entity->finish，最后把entity按照entity->finish插入st->active红黑树

具体实现还是看下__bfq_requeue_entity 和 __bfq_activate_entity的源码实现。

3.2:__bfq_requeue_entity函数

先看下流程图

static void __bfq_requeue_entity(struct bfq_entity *entity)

1. {
2.     struct bfq_sched_data *sd = entity->sched_data;
3.     struct bfq_service_tree *st = bfq_entity_service_tree(entity);
5.     //entity是bfq调度器正在使用的entity
6.       if (entity == sd->in_service_entity) {
7.          /*根据entity->service/entity->weight计算entity已经消耗的虚拟运行时间，entity->start加上这段虚拟运行时间就是entity->finish*/
8.           bfq_calc_finish(entity, entity->service);
9.          //用entity->finish更新entity->start，重置了
10.           entity->start = entity->finish;
11.          //如果entity在st->active红黑树，则从st->acitve tree剔除entity，下边再把entity加入st->active红黑树
12.           if (entity->tree)
13.               bfq_active_extract(st, entity);
14.       } else {
15.         /*从st->acitve tree剔除entity。这里不禁有疑问，上边也是执行bfq_active_extract()，有什么区别?上边更新了entity->finish，这里没有。下边把entity重新插入st->active红黑树时，就是按照最新entity->finish把entity插入st->active*/
16.              bfq_active_extract(st, entity);
17.     }
18.    
19.      /*按照entity->budget计算entity的虚拟运行时间并累加到entity->finish，最后把entity按照新的entity->finish插入st->active红黑树*/
20.      bfq_update_fin_time_enqueue(entity, st, false);
21. }

__bfq_requeue_entity()函数主要作用是：if (entity == sd->in_service_entity)成立表示entity是bfq当前调度器正在使用的entity，则执行bfq_calc_finish()根据entity已经消耗的配额entity->service计算entity消耗的虚拟运行时间，entity->start加上这段虚拟运行时间得到entity->finish。如果if (entity == sd->in_service_entity)不成立，只是执行bfq_active_extract()把entity从st->active 红黑树剔除掉。最后，执行bfq_update_fin_time_enqueue()，还要再根据entity的配额entity->budget计算一次entity->finish，然后把entity按照最新的entity->finish插入st->active红黑树。下文依次介绍这些函数：

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.       /*service是entity已经消耗的配额，除以weight得到entity已经消耗的虚拟运行时间.entity->finish等于entity->start加上entity已经消耗的虚拟运行时间*/
5.       entity->finish = entity->start + bfq_delta(service, entity->weight);
6. }

根据service/entity->weight计算entity已经消耗的虚拟运行时间，entity->start加上这段虚拟运行时间就是entity->finish。bfq_active_extract()源码如下，就是从st->active红黑树剔除entity。

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

下边补个bfq_active_extract()函数流程图

下边看下bfq_update_fin_time_enqueue()函数

3.3 :bfq_update_fin_time_enqueue函数

先看下流程图

 static void bfq_update_fin_time_enqueue(struct bfq_entity *entity,

1.                     struct bfq_service_tree *st,
2.                     bool backshifted)
3. {
4.      struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
5.      st = __bfq_entity_update_weight_prio(st, entity, true);
6.      /*这里简化成entity->finish=entity->start+entity->budget/entity->weight，用entity的配额得到entity->finish，注意是entity的配额*/
7.      bfq_calc_finish(entity, entity->budget);
8.     …………………
9.      //把entity按照新的entity->finish插入st->active红黑树
10.      bfq_active_insert(st, entity);
11. }

先是按照entity->budget计算entity的虚拟运行时间并累加到entity->finish，最后把entity按照新的entity->finish插入st->active红黑树。注意，bfq_update_fin_time_enqueue()函数里执行bfq_calc_finish(entity, entity->budget)，是用entity的配额entity->budget计算得到entity->finish。接着，执行bfq_active_insert()函数把entity插入st->active红黑树。bfq_active_insert()函数源码如下：

3.4:bfq_active_insert函数

先看下流程图

bfq_active_insert()函数源码如下：

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

bfq_active_insert()源码注释写的比较清楚，不再赘述。bfq_insert()函数源码如下：

1. static void bfq_insert(struct rb_root *root, struct bfq_entity *entity)
2. {
3.      struct bfq_entity *entry;
4.      //st->idle或者st->active 树root节点
5.      struct rb_node **node = &root->rb_node;
6.      struct rb_node *parent = NULL;
7.      ............
8.      while (*node) {
9.           parent = *node;
10.           entry = rb_entry(parent, struct bfq_entity, rb_node);
11.          /*entity->finish小于红黑树节点的entry->finish则if成立，然后取出entry的左节点。显然，st->idle或者st->active红黑树中的的entity是按照entity->finish由小到大从左到右进行排序的*/
12.          if (bfq_gt(entry->finish, entity->finish))
13.               node = &parent->rb_left;
14.          else
15.               node = &parent->rb_right;
16.      }
17.       rb_link_node(&entity->rb_node, parent, node);
18.       rb_insert_color(&entity->rb_node, root);
19.       //entity->tree指向st->active或者st->idle红黑树根节点
20.       entity->tree = root;
21. }

把entity按照entity->finish插入st->idle或者st->active红黑树都要执行bfq_insert()函数，entity->finish越小entity在红黑树越靠左。接着，__bfq_activate_requeue_entity()里另一个分支的__bfq_activate_entity()函数。

3.5:__bfq_activate_entity函数

先看下示意图

__bfq_activate_entity()函数源码如下：

1. static void __bfq_activate_entity(struct bfq_entity *entity,
2.                   bool non_blocking_wait_rq)
3. {
4.      struct bfq_service_tree *st = bfq_entity_service_tree(entity);
5.      bool backshifted = false;
6.      unsigned long long min_vstart;
7.      //if和else分支测试可能成立，新分配的bfqq应该走else分支
8.      if (non_blocking_wait_rq && bfq_gt(st->vtime, entity->finish)) {
9.          backshifted = true;
10.          min_vstart = entity->finish;
11.      } else
12.          min_vstart = st->vtime;
13.      ............
14.      //entity现在处于st->idle红黑树
15.      if (entity->tree == &st->idle) {
16.          //entity从st->idle红黑树剔除掉，可能更新st->first_idle或st->last_idle
17.          bfq_idle_extract(st, entity);
18.          entity->start = bfq_gt(min_vstart, entity->finish) ?
19.              min_vstart : entity->finish;
20.      } else {//到这里说明entity之前不在st->idle或st->active红黑树。entity是新分配的也走这里
21.          entity->start = min_vstart;
22.          //st->wsum调度类st的active和idle tree上所有entity的权重之和，累加每一个entity的entity->weight
23.          st->wsum += entity->weight;
24.          bfq_get_entity(entity);
25.          entity->on_st_or_in_serv = true;
26.     }
27.     ................
28.      /*按照entity->budget计算entity的虚拟运行时间并累加到entity->finish，最后把entity按照新的entity->finish插入st->active红黑树*/
29.      bfq_update_fin_time_enqueue(entity, st, backshifted);
30. }

如果if (entity->tree == &st->idle)成立，说明之前entity处于st->idle红黑树，则要把它从st->idle红黑树剔除掉，重新计算它的entity->start，entity->start取自st->vtime和entity->finish的最大者。如果if (entity->tree == &st->idle)不成立，则说明该entity应该是新创建的bfqq的entity，则entity->start= st->vtime，st->wsum += entity->weight是令st->wsum += entity->weight累加该entity的权重，st->wsum会累加所有加入st->active或st->idle红黑树的entity的权重。

最后，是执行bfq_update_fin_time_enqueue()，按照entity->budget计算entity的虚拟运行时间并累加到entity->finish，最后把entity按照新的entity->finish插入st->active红黑树。这点前文已经说过。

4: bfq_dispatch_request函数

顾名思义bfq_dispatch_request()是派发IO请求的，它基本就只是执行了__bfq_dispatch_request()函数而已，下文先看下__bfq_dispatch_request()函数源码。

4.1:__bfq_dispatch_request函数

先看下流程图

static struct request *__bfq_dispatch_request(struct blk_mq_hw_ctx *hctx)

1. {
2.     ............
3.      /*1:如果bfqd->in_service_queue指向的bfqq为NULL，或者这个bfqq上没有要派发的req则选择一个新的bfqq。2:bfqd->in_service_queue指向bfqq如果配额足够则返回它。3:如果这个bfqq的配额被消耗光了，则先令bfqq失效，接着也选择一个新的bfqq*/
4.        bfqq = bfq_select_queue(bfqd);
5.      /*计算并返回传输本次IO请求需要配额served：根据本次传的配额served，增加entity配额entity->service和调度器虚拟运行时间st->vtime。计算新的bfqd->peak_rate，并选择一个新的IO请求作为bfqq->next_rq，计算更新新的entity->budget，把IO请求从bfqq->sort_list链表剔除。如果bfqq的entity配额被消耗光了，还有概率执行bfq_bfqq_expire()令bfqq失效*/
6.        rq = bfq_dispatch_rq_from_bfqq(bfqd, bfqq);
7.        if (rq) {
8. inc_in_driver_start_rq:
9.            bfqd->rq_in_driver++;
10. start_rq:
11.            rq->rq_flags |= RQF_STARTED;
12.      }
13. exit:
14.       return rq;
15. }

__bfq_dispatch_request()函数主要有两个重点，一个是执行bfq_select_queue()选择一个bfqq，然后执行bfq_dispatch_rq_from_bfqq()从该bfqq上选择一个待派发的IO请求并返回。

4.2 bfq_select_queue函数

1. static struct bfq_queue *bfq_select_queue(struct bfq_data *bfqd)
2. {
3.      //当前没有bfqqgoto new_queue
4.      bfqq = bfqd->in_service_queue;
5.      if (!bfqq)
6.          goto new_queue;
7.     .........
8. check_queue:
9.          next_rq = bfqq->next_rq;//选择优先派发的req
10.         if (next_rq) {
11.              /*bfq_serv_to_charge()是计算并返回传输本次req需要配额，bfq_bfqq_budget_left()是该bfqq还剩余的配额。前者大于后者，说明bfqq的配额不够了，则要是bfqq失效，选择新的bfqq*/
12.            if (bfq_serv_to_charge(next_rq, bfqq) >
13.                  bfq_bfqq_budget_left(bfqq)) {
14.                  ...............
15.                 reason = BFQQE_BUDGET_EXHAUSTED;
16.                 goto expire;
17.            } else {
18.               ...............
19.               goto keep_queue;
20.         }
21.     }
22.     ...............
23.      reason = BFQQE_NO_MORE_REQUESTS;//bfqq没有req要传输了
24. expire:
25.      ............
26.       /*bfqq的entity配额被消耗光了或者bfqq没有可派发的req了等，则令bfqq的entity从st->active红黑树踢掉。接着计算entity的虚拟运行时间并更新到entity->finish，把entity重新加入st->idle或st->active红黑树。如果bfqq不会再被调度，可能把entity及bfqq释放掉。*/
27.     bfq_bfqq_expire(bfqd, bfqq, false, reason);
28. new_queue:
29.      /*核心是取出sd->next_in_service赋于sd->in_service_entity作为马上要使用的entity，这就是新选择的bfqq的entity。最后从st查找合适的entity并更新到sd->next_in_service，没有找到则设置sd->next_in_service为NULL*/
30.      bfqq = bfq_set_in_service_queue(bfqd);
31.      if (bfqq) {
32.             //找到bfqq则goto check_queue分支
33.             bfq_log_bfqq(bfqd, bfqq, "select_queue: checking new queue");
34.             goto check_queue;
35.       }
36. keep_queue:
37.     ..................
38.     return bfqq;
39. }

在bfq_select_queue()函数中，主要分3种情况：

1:如果bfqd->in_service_queue指向的bfqq为NULL，则goto new_queue分支，执行bfqq = bfq_set_in_service_queue(bfqd)选择一个新的bfqq

2：next_rq = bfqq->next_rq是NULL，if (next_rq)不成立，说明这个bfqq上没有要派发的req了。执行reason = BFQQE_NO_MORE_REQUEST(bfqq上没有要派发的req)。接着执行bfq_bfqq_expire()令bfqq过期失效，执行bfqq = bfq_set_in_service_queue(bfqd)选择一个新的bfqq。

3: next_rq = bfqq->next_rq非NULL，if (next_rq)成立，if (bfq_serv_to_charge(next_rq, bfqq) >bfq_bfqq_budget_left(bfqq))不成立，这说明bfqq有足够的配额派发next_rq这个IO请求，则goto keep_queue直接返回bfqq即可。但如果if (bfq_serv_to_charge(next_rq, bfqq) >bfq_bfqq_budget_left(bfqq))成立，如果这个bfqq的配额被消耗光了，则reason = BFQQE_BUDGET_EXHAUSTED，接着执行bfq_bfqq_expire()令bfqq过期失效，执行bfqq = bfq_set_in_service_queue(bfqd)选择一个新的bfqq。

这个过程涉及的函数下文依次介绍。

4.3: bfq_set_in_service_queue函数

1. static struct bfq_queue *bfq_set_in_service_queue(struct bfq_data *bfqd)
2. {
3.      /*核心是取出sd->next_in_service赋于sd->in_service_entity作为马上要使用的entity，这就是新选择的bfq_queue的entity。最后从st查找合适的entity并更新到sd->next_in_service，没有找到则设置sd->next_in_service为NULL*/
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()函数选择一个新的bfqq作为当前要使用的bfqq，源码如下：

1. struct bfq_queue *bfq_get_next_queue(struct bfq_data *bfqd)
2. {
3.      struct bfq_entity *entity = NULL;
4.      struct bfq_sched_data *sd;
5.      struct bfq_queue *bfqq;
6.      //如果没有bfqq直接return NULL
7.      if (bfq_tot_busy_queues(bfqd) == 0)
8.         return NULL;
10.      sd = &bfqd->root_group->sched_data;
11.      for (; sd ; sd = entity->my_sched_data) {//测试时这个循环只执行了一
12.            //取出sd->next_in_service作为当前要使用的entity，赋值给sd->in_service_entity
13.           entity = sd->next_in_service;
14.           sd->in_service_entity = entity;
15.           ...........
16.           //如果没有多余的entity作为sd->next_in_service，则要从st->acitve tree剔除entity
17.           if (bfq_no_longer_next_in_service(entity))
18.                bfq_active_extract(bfq_entity_service_tree(entity),
19.                           entity);
20.       }
21.       bfqq = bfq_entity_to_bfqq(entity);
22.       for_each_entity(entity) {
23.            struct bfq_sched_data *sd = entity->sched_data;
24.          /*从st查找合适的entity并更新到sd->next_in_service，没有找到则设置sd->next_in_service为NULL*/
25.          if (!bfq_update_next_in_service(sd, NULL, false))
26.              break;
27.      }
28.      return bfqq;
29. }

我们要先知道为什么会执行到bfq_get_next_queue()函数。看下流程：bfq_select_queue()->bfq_set_in_service_queue()->bfq_get_next_queue()，这是为了得到一个新的bfqq，作为bfq调度器当前正在使用的bfqq，即sd->in_service_entity。

bfq_get_next_queue()函数主要是把sd->next_in_service指向的entiry赋于sd->in_service_entity。sd->next_in_service是下一次要使用的bfqq的entity，现在执行bfq_get_next_queue()要得到一个新的bfqq，自然要先从sd->next_in_service得到entity，这个bfqq就是sd->in_service_entity。bfqq = bfq_entity_to_bfqq(entity)得到entity对应的bfqq。

接着，要执行bfq_update_next_in_service()选一个新的下一次使用的bfqq的entity，赋于sd->next_in_service。下次执行bfq_get_next_queue()要得到一个新的bfqq时，直接从sd->next_in_service取出即可。

__bfq_set_in_service_queue()函数主要是bfqd->in_service_queue = bfqq，不造啰嗦。

1. static void __bfq_set_in_service_queue(struct bfq_data *bfqd,
2.                        struct bfq_queue *bfqq)
3. {
4.     if (bfqq) {
5.         bfq_clear_bfqq_fifo_expire(bfqq);
6.         ............
7.     }
8.     bfqd->in_service_queue = bfqq;
9. }

bfq_update_next_in_service()函数源码下文讲解。

5 :bfq_update_next_in_service函数

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.     if (new_entity && new_entity != sd->next_in_service) {
10.          change_without_lookup = true;//这里赋值change_without_lookup=true
11.          if (next_in_service) {
12.              unsigned int new_entity_class_idx =
13.                  bfq_class_idx(new_entity);
14.              struct bfq_service_tree *st = sd->service_tree + new_entity_class_idx;
15.              change_without_lookup =
16.                  //二者同一个调度策略
17.                  (new_entity_class_idx ==bfq_class_idx(next_in_service)
18.                   &&
19.                   //new_entity->start 小于 st->vtime
20.                   !bfq_gt(new_entity->start, st->vtime)
21.                   &&
22.                   //next_in_service->finish 大于 new_entity->finish
23.                   bfq_gt(next_in_service->finish,new_entity->finish));
24.          }
25.         ............
26.          /*change_without_lookup为true把传入的new_entity赋值给next_in_service，下边把new_entity分配给sd->next_in_service*/
27.          if (change_without_lookup)
28.               next_in_service = new_entity;
29.       }
30.      ............
31.     /*如果change_without_lookup为false则执行bfq_lookup_next_entity()选择下一个使用的bfqq的entity。可能找不到，则返回NULL*/
32.      if (!change_without_lookup)
33.          next_in_service = bfq_lookup_next_entity(sd, expiration);
34.      if (next_in_service) {
35.          bool new_budget_triggers_change =
36.              bfq_update_parent_budget(next_in_service);
37.          parent_sched_may_change = !sd->next_in_service ||
38.              new_budget_triggers_change;
39.      }
40.      /*为sd->next_in_servic赋值下一次使用的bfqq的entity。如果前边没找到则sd->next_in_service被赋值NULL*/
41.      sd->next_in_service = next_in_service;
42.      if (!next_in_service)
43.         return parent_sched_may_change;
44.      return parent_sched_may_change;
45. }

简单来说，就是为了找到下一次使用的entity并赋于sd->next_in_service。细节是从bfq调度器sd查找下一次使用的bfqq的entity并更新到sd->next_in_service，没有找到则设置sd->next_in_service为NULL，这些大部分在bfq_lookup_next_entity()函数完成，看下它的源码：

1. static struct bfq_entity *bfq_lookup_next_entity(struct bfq_sched_data *sd,
2.                          bool expiration)
3. {
4.      struct bfq_service_tree *st = sd->service_tree;
5.      ...........
6.      //在sd调度器每个调度策略st里都搜索可用的 entity，都找不到返回NULL
7.      for (; class_idx < BFQ_IOPRIO_CLASSES; class_idx++) {
8.          entity = __bfq_lookup_next_entity(st + class_idx,
9.                           sd->in_service_entity &&
10.                           !expiration);
11.          if (entity)
12.              break;
13.      }
14.      return entity;
15. }

bfq_lookup_next_entity()在sd调度器每个调度策略st里都搜索可用的 entity，而搜索一个st中可用的entiry是执行__bfq_lookup_next_entity()函数，看下它的源码：

1. static struct bfq_entity *
2. __bfq_lookup_next_entity(struct bfq_service_tree *st, bool in_service)
3. {
4.      struct bfq_entity *entity;
5.      u64 new_vtime;
6.      //st->active红黑树没有entiry则返回NULL。next entity必须从st->active的红黑树查询一个合适的entity
7.      if (RB_EMPTY_ROOT(&st->active))
8.            return NULL;
9.      //返回st虚拟运行时间，返回root_entity->min_start或者st->vtime
10.      new_vtime = bfq_calc_vtime_jump(st);
11.      //st没有正在service 的entity则可能st->vtime = new_vtime
12.      if (!in_service)
13.           bfq_update_vtime(st, new_vtime);
14.      //从st->active 红黑树左边查找entity->start小于new_vtime并且entity->start最小的entity
15.      entity = bfq_first_active_entity(st, new_vtime);
16.      return entity;
17. }

主要是执行bfq_first_active_entity()函数完成具体工作，源码如下：

1. static struct bfq_entity *bfq_first_active_entity(struct bfq_service_tree *st,
2.                           u64 vtime)
3. {
4.      struct bfq_entity *entry, *first = NULL;
5.      struct rb_node *node = st->active.rb_node;
6.      while (node)
7.     {
8.          entry = rb_entry(node, struct bfq_entity, rb_node);
9. left:
10.          // entry->start < vtime 则if成立，vtime 是st->vtime
11.          if (!bfq_gt(entry->start, vtime))
12.              first = entry;
13.          //如果entry有左节点，一直向左查找，有靠左的entry，entry->start和entry->min_start越小
14.           if (node->rb_left) {
15.               entry = rb_entry(node->rb_left,
16.                        struct bfq_entity, rb_node);
17.                  if (!bfq_gt(entry->min_start, vtime)) {
18.                       node = node->rb_left;
19.                       goto left;
20.                  }
21.           }
22.           if (first)
23.               break;
24.          node = node->rb_right;
25.      }
26.      return first;
27. }

bfq_first_active_entity()的查找规则是：从st->active红黑树根节点一直向左查找，找到最左边的并且entity->start小于st->vtime的entiry。为什么要这样查找后啊？因为这样可以找到entity->start最小的entity，这样的entiry更早插入st->active红黑树，当然这样的entity要更容易被选中使用，派发该entity对应的bfqq上的IO请求。ok，返回的entity就可能是下一次派发IO请求会用到的entiry，稍后到赋于sd->next_in_service。

ok，bfq_select_queue()函数到这里介绍完了，下边介绍bfq_bfqq_expire()函数。

6: bfq_bfqq_expire函数

1. void bfq_bfqq_expire(struct bfq_data *bfqd,
2.              struct bfq_queue *bfqq,
3.              bool compensate,
4.              enum bfqq_expiration reason)
5. {
6.      struct bfq_entity *entity = &bfqq->entity;
7.     ............   
8.      /*计算更新bfqq->max_budget，如果bfqq上还有req(bfqq->next_rq)要派发，则计算根据next_rq传输的字节数计算bfqq->entity的配额，保证bfqq的配额还能传输完next_rq*/
9.      __bfq_bfqq_recalc_budget(bfqd, bfqq, reason);
10.     ............
11.       /*bfqq的entity配额被消耗光了或者bfqq没有可派发的IO请求了等等，bfqq的entity会从st->active红黑树踢掉。接着计算entity的虚拟运行时间并更新到entity->finish，把entity重新加入st->idle或st->active红黑树。如果bfqq不会再被调度，可能把entity及bfqq释放掉。*/
12.      if (__bfq_bfqq_expire(bfqd, bfqq, reason))
13.          return;
14.     ...........
15. }

bfq_bfqq_expire()函数首先执行__bfq_bfqq_recalc_budget()：根据bfqq的过期失效原因，计算bfqq的最大配额bfqq->max_budget。令bfqq具体过期失效在__bfq_bfqq_expire()完成。先看下__bfq_bfqq_recalc_budget ()函数源码：

6.1 __bfq_bfqq_recalc_budget 函数

1. static void __bfq_bfqq_recalc_budget(struct bfq_data *bfqd,
2.                      struct bfq_queue *bfqq,
3.                      enum bfqq_expiration reason)
4. {
5.      struct request *next_rq;
6.      int budget, min_budget;
7.      ............
8.      min_budget = bfq_min_budget(bfqd);
9.      ............
10.      if (bfqq->wr_coeff == 1)//测试时有30或1
11.          budget = bfqq->max_budget;
12.      else
13.          budget = 2 * min_budget;
14.      .............
15.      if (bfq_bfqq_sync(bfqq) && bfqq->wr_coeff == 1) {
16.          //根据bfqq失效原因reason，计算budget
17.          switch (reason) {
18.          case BFQQE_TOO_IDLE:
19.         ...............
20.          case BFQQE_BUDGET_TIMEOUT:
21.              budget = min(budget * 2, bfqd->bfq_max_budget);
22.              break;
23.          case BFQQE_BUDGET_EXHAUSTED:
24.              budget = min(budget * 4, bfqd->bfq_max_budget);
25.              break;
26.          case BFQQE_NO_MORE_REQUESTS:
27.              budget = max_t(int, bfqq->entity.service, min_budget);
28.              break;
29.          default:
30.              return;
31.          }
32.      } else if (!bfq_bfqq_sync(bfqq)) {
33.          budget = bfqd->bfq_max_budget;
34.      }
35.      //更新bfqq->max_budget
36.      bfqq->max_budget = budget;
37.     ................
38.      /*如果bfqq上还有req(即bfqq->next_rq)要派发，则计算根据next_rq传输的字节数计算bfqq->entity的配额，保证bfqq的配额还能传输完next_rq*/
39.      next_rq = bfqq->next_rq;
40.      if (next_rq)
41.          bfqq->entity.budget = max_t(unsigned long, bfqq->max_budget,
42.                          bfq_serv_to_charge(next_rq, bfqq));
43. }

该函数是计算更新bfqq->max_budget，如果bfqq上还有IO请求(即bfqq->next_rq)要派发，则计算根据next_rq传输的字节数计算bfqq->entity的配额，保证bfqq的配额还能传输完next_rq。

6.2__bfq_bfqq_expire函数

1. static bool __bfq_bfqq_expire(struct bfq_data *bfqd, struct bfq_queue *bfqq,
2.                   enum bfqq_expiration reason)
3. {
4.     ...................
5.      if (RB_EMPTY_ROOT(&bfqq->sort_list) &&//bfqq上没有派发的req成立
6.          !(reason == BFQQE_PREEMPTED &&
7.            idling_needed_for_service_guarantees(bfqd, bfqq)))
8.     {
9.          if (bfqq->dispatched == 0)
10.              bfqq->budget_timeout = jiffies;
11.     /*1:把entity从st->active或st->idle红黑树踢掉，ins_into_idle_tree为true则把entity再插入st->idle红黑树，否则直接释放掉entity及bfqq。2:计算entity的虚拟运行时间并累加到entity->finish，最后把entity按照新的entity->finish插入st->idle或st->active红黑树*/
12.           bfq_del_bfqq_busy(bfqd, bfqq, true);
13.      } else {
14.     /*如果entity是调度器正在使用的entiry或entity处于st->active红黑树,计算entity的虚拟运行时间并累加到entity->finish，把entity按照新的entity->finish插入st->active红黑树。否则计算新的entity->start，按照entity->budget计算entity的虚拟运行时间并累加到entity->finish，最后把entity按照entity->finish插入st->active红黑树。最后从st查找合适的entity并更新到sd->next_in_service*/
15.          bfq_requeue_bfqq(bfqd, bfqq, true);
16.          .................
17.     }
18.     .....................
19.      //bfqd->in_service_queue = NULL 等
20.      return __bfq_bfqd_reset_in_service(bfqd);
21. }

__bfq_bfqq_expire()函数主要有两个分支：如果bfqq上没有要派发的IO请求了(bfqq->sort_list空)，则执行bfq_del_bfqq_busy()把bfqq的entity从st->active红黑树剔除掉，然后把entity加入到st->idle红黑树。bfq的调度器都是从st->active红黑树的寻找要使用的entity，然后返回entity的bfqq，再派发这个bfqq上的IO请求。另一个分支是执行bfq_requeue_bfqq()，计算entity的虚拟运行时间，更新entity->finish，然后把entity重新加入st->active红黑树。

bfq_del_bfqq_busy()函数源码如下：

1. void bfq_del_bfqq_busy(struct bfq_data *bfqd, struct bfq_queue *bfqq,
2.                bool expiration)
3. {
4.      //清理bfqq busy状态
5.      bfq_clear_bfqq_busy(bfqq);
6.      bfqd->busy_queues[bfqq->ioprio_class - 1]--;
7.     .................
8.      bfqg_stats_update_dequeue(bfqq_group(bfqq));
9.     /*1:把entity从st->active或st->idle红黑树踢掉，ins_into_idle_tree为true则把entity再插入st->idle红黑树，否则直接释放掉entity及bfqq。2:计算entity的虚拟运行时间并累加到entity->finish，最后可能把entity按照新的entity->finish插入st->idle红黑树*/
10.      bfq_deactivate_bfqq(bfqd, bfqq, true, expiration);
11.     ...........
12. }

主要过程是：bfqq没有IO请求派发了或者bfqq失效了，清理bfqq的busy状态，把bfqq的entity从st->active或st->idle红黑树踢掉，有可能再把bfqq插入到st->idle红黑树。

bfq_deactivate_bfqq函数源码如下：

1. void bfq_deactivate_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq,
2.              bool ins_into_idle_tree, bool expiration)
3. {
4.     struct bfq_entity *entity = &bfqq->entity;
5.     /*1:把entity从st->active或st->idle红黑树踢掉，ins_into_idle_tree为true则把entity再插入st->idle红黑树，否则直接释放掉entity及bfqq。2:计算entity的虚拟运行时间并累加到entity->finish，最后可能把entity按照新的entity->finish插入st->idle红黑树*/
6.     bfq_deactivate_entity(entity, ins_into_idle_tree, expiration);
7. }

显然，重点还是执行bfq_deactivate_entity函数，这个我们在下节介绍。现在先看下bfq_requeue_bfqq函数源码：

6.3:bfq_requeue_bfqq函数

先看下流程图

bfq_requeue_bfqq()函数源码如下：

1. void bfq_requeue_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq,
2.               bool expiration)
3. {
4.      struct bfq_entity *entity = &bfqq->entity;
5.     /*如果entity是调度器正在使用的entiry或entity处于st->active红黑树,计算entity的虚拟运行时间并累加到entity->finish，把entity按照新的entity->finish插入st->active红黑树。否则计算新的entity->start，按照entity->budget计算entity的虚拟运行时间并累加到entity->finish，最后把entity按照entity->finish插入st->active红黑树。最后从st查找合适的entity并更新到sd->next_in_service*/
6.      bfq_activate_requeue_entity(entity, false,
7.                      bfqq == bfqd->in_service_queue, expiration);
8. }

bfq_activate_requeue_entity()函数源码再前文已经介绍过，可回头查看。下节我们看看bfq_deactivate_entity函数。

7:bfq_deactivate_entity函数

1. static void bfq_deactivate_entity(struct bfq_entity *entity,
2.                   bool ins_into_idle_tree,
3.                   bool expiration)
4. {
5.      struct bfq_sched_data *sd;
6.      struct bfq_entity *parent = NULL;
7.      for_each_entity_safe(entity, parent)
8.     {
9.          sd = entity->sched_data;
10.          /*把entity从st->active或st->idle红黑树踢掉，ins_into_idle_tree为true则把entity再插入st->idle红黑树，否则直接释放掉entity及bfqq。剔除成功返回true*/
11.           if (!__bfq_deactivate_entity(entity, ins_into_idle_tree)) {
12.               return;
13.           }
14.            ............
15.          /*entity是正在sd->next_in_service指向的调度器正在使用的entiry，则要选择一个新的next_in_service entity*/
16.           if (sd->next_in_service == entity)
17.                 //从st查找合适的entity并更新到sd->next_in_service，没有找到则返回NULL
18.                 bfq_update_next_in_service(sd, NULL, expiration);
19.            ............
20.           if (sd->next_in_service || sd->in_service_entity) {
21.                      break;
22.            }
23.           ..............
24.           ins_into_idle_tree = true;
25.        }
26.     ..............
27. }

里边主要执行了两个函数__bfq_deactivate_entity()和bfq_update_next_in_service()。前者是重点：把entity从st->active或st->idle红黑树踢掉，ins_into_idle_tree为true则把entity再插入st->idle红黑树，否则直接释放掉entity及bfqq。然后，计算entity的虚拟运行时间并累加到entity->finish，最后可能把entity按照新的entity->finish插入st->idle红黑树。

bfq_update_next_in_service()函数在前边已经讲解，主要是选择下一个使用的entity，赋于sd->next_in_service，不再赘述。下文重点看__bfq_deactivate_entity()函数源码。

7.1: __bfq_deactivate_entity函数

先看下流程图

bool __bfq_deactivate_entity(struct bfq_entity *entity, bool ins_into_idle_tree)

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

可以发现，首先执行bfq_calc_finish(entity, entity->service)以entity已经消耗的配额entity->service计算entity->finish。注意，这里不是以entity的配额entity->weight计算entity->finish，bfq_update_fin_time_enqueue()函数中执行的bfq_calc_finish(entity, entity->budget)才是以entity的配额entity->budget计算entity->finish。最后，执行bfq_active_extract()或bfq_idle_extract()把entity从st->active或st->idle红黑树踢掉，ins_into_idle_tree为true则把entity再插入st->idle红黑树，否则直接释放掉entity及bfqq剔除返回true。

bfq_active_extract()前文介绍过，下边把bfq_idle_extract和bfq_idle_insert函数源码贴上。

7.2 :bfq_idle_extract和bfq_idle_insert函数

1. //entity从st->idle红黑树剔除掉，可能更新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->idle红黑树剔除，则选择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->idle红黑树剔除，则选择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->idle红黑树剔除掉
18.     bfq_extract(&st->idle, entity);
19.     if (bfqq)
20.          list_del(&bfqq->bfqq_list);
21. }

bfq_idle_extract()函数源码注释写的比较清楚，需要重点说明的一点是，在把entity从st->idle红黑树剔除掉前，需要更新st->first_idle和st->last_idle。st->first_idle永远指向st->idle红黑树最左边的entity，st->last_idle永远指向st->idle红黑树最右边的entity。

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.     //st->first_idle记录entity->finish最小的entity，就是st->idle红黑树最靠左的entity
10.      if (!first_idle || bfq_gt(first_idle->finish, entity->finish))
11.          st->first_idle = entity;
12.     //st->last_idle记录entity->finish最大的entity，就是st->idle红黑树最靠右的entity
13.      if (!last_idle || bfq_gt(entity->finish, last_idle->finish))
14.          st->last_idle = entity;
15.     //把entity按照entity->finish插入st->idle红黑树，entity->finish越小entity在红黑树越靠左
16.      bfq_insert(&st->idle, entity);
17.      if (bfqq)//加入st->idle 的红黑树都加入到bfqd->idle_list链表
18.          list_add(&bfqq->bfqq_list, &bfqq->bfqd->idle_list);
19. }

bfq_idle_insert()中是把entity插入st->idle树，并可能更新st->first_idle或st->last_idle。因为st->first_idle永远指向st->idle红黑树最左边的entity，st->last_idle永远指向st->idle红黑树最右边的entity。

8: 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.      /*计算并返回本次派发的IO请求需要的配额，配额以IO请求要传输字节数为基准，同步和异步IO计算方法不一样。*/
7.      service_to_charge = bfq_serv_to_charge(rq, bfqq);​​​​​​​
8.      /*根据本次传输IO请求的配额served，增加entity配额entity->service和调度器虚拟运行时间st->vtime*/
9.      bfq_bfqq_served(bfqq, service_to_charge);
10.      if (bfqq == bfqd->in_service_queue && bfqd->wait_dispatch) {
11.          bfqd->wait_dispatch = false;
12.          bfqd->waited_rq = rq;
13.      }
14.      /*计算新的bfqd->peak_rate，并选择一个新的req作为bfqq->next_rq，计算更新新的entity->budget，把req从bfqq->sort_list链表剔除*/
15.      bfq_dispatch_remove(bfqd->queue, rq);
16.      //bfqq不是正在使用的
17.      if (bfqq != bfqd->in_service_queue)
18.          goto return_rq;
19.      /*更新bfqq->bfqd->wr_busy_queues、bfqq->wr_coeff、bfqq->wr_cur_max_time、bfqq->last_wr_start_finish、bfqq->entity.prio_changed等参数*/
20.      bfq_update_wr_data(bfqd, bfqq);
21.      if (!(bfq_tot_busy_queues(bfqd) > 1 && bfq_class_idle(bfqq)))//这个if一般都成立
22.          goto return_rq;
23.      //这里一般执行不到
24.      bfq_bfqq_expire(bfqd, bfqq, false, BFQQE_BUDGET_EXHAUSTED);
25. return_rq:
26.      return rq;
27. }

首先执行bfq_serv_to_charge()函数计算并返回派发本次IO请求需要配额served。接着执行bfq_bfqq_served()函数根据本次派发的IO请求的配额served，累加到entity配额entity->service和调度器虚拟运行时间st->vtime。接着，执行bfq_dispatch_remove()计算新的bfqd->peak_rate，并选择下一次派发的IO请求赋于bfqq->next_rq，计算更新新的entity->budget，把IO请求从bfqq->sort_list链表剔等等。bfq_serv_to_charge()和bfq_bfqq_served()函数源码如下：

8.1: bfq_serv_to_charge和bfq_bfqq_served函数

bfq_serv_to_charge()函数源码如下：

1. //计算并返回传输本次req需要配额，配额以req要传输字节数为基准，同步和异步IO计算方法不一样。
2. static unsigned long bfq_serv_to_charge(struct request *rq,
3.                     struct bfq_queue *bfqq)
4. {
5.      if (bfq_bfqq_sync(bfqq) || bfqq->wr_coeff > 1 ||
6.            bfq_asymmetric_scenario(bfqq->bfqd, bfqq))
7.              return blk_rq_sectors(rq);//同步IO直接返回req要传输的字节数
8.       //异步IO是req要传输字节数乘以bfq_async_charge_factor
9.       return blk_rq_sectors(rq) * bfq_async_charge_factor;
10. }

很明显，就是根据派发的IO请求的字节数计算的配额，但是异步IO的话要乘以bfq_async_charge_factor。为什么呢？我推测是让异步IO请求的配额消耗更快，这样更容易过期失效而选择新的bfqq的IO请求而派发。

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.      struct bfq_entity *entity = &bfqq->entity;
5.      struct bfq_service_tree *st;
6.      if (!bfqq->service_from_backlogged)
7.          bfqq->first_IO_time = jiffies;
8.      if (bfqq->wr_coeff > 1)
9.          bfqq->service_from_wr += served;
10.      bfqq->service_from_backlogged += served;
11.      for_each_entity(entity) {
12.          //取出entity指向的调度器实体st
13.          st = bfq_entity_service_tree(entity);
14.          //entity->service累加待派发req的配额served
15.          entity->service += served;
16.          //st->vtime累加待派发req的配额served除以st->wsum算出的虚拟运行时间
17.          st->vtime += bfq_delta(served, st->wsum);
18.          /*处理st->idle红黑树的first_idle和last_idle，可能会把first_idle指向的entity从st->idle红黑树剔除掉，释放掉它的bfqq和entity*/
19.          bfq_forget_idle(st);
20.      }
21.      bfq_log_bfqq(bfqq->bfqd, bfqq, "bfqq_served %d secs", served);
22. }
23. static u64 bfq_delta(unsigned long service, unsigned long weight)
24. {
25.       return div64_ul((u64)service << WFQ_SERVICE_SHIFT, weight);
26. }

bfq_bfqq_served()函数比较重要，主要是根据本次派发IO请求的配额served，累加到entity->service。并且执行st->vtime += bfq_delta(served, st->wsum)计算bfq调度器的虚拟运行时间st->vtime。st->wsum是bfq调度器st中所有bfqq的entity(包括st->active和st->idle红黑树上的entity)的权重之和。bfq_delta(served, st->wsum)很巧妙，每派发调度器st上一个entity的一个IO请求，都要计算派发的IO请求的消耗的配额 (使用served*N/ st->wsum计算，N是一个常数)，然后累计到调度器的虚拟运行时间st->vtime。简单说st->vtime= (bfqq1派发的IO请求消耗的配额之和+ bfqq2的派发的IO请求消耗的配额之和+……….+bfqqN的派发的IO请求消耗的配额之和) /(bfqq1的entity的权重+ bfqq1的entity的权重+………+bfqqN的entity的权重)。

8.2: bfq_dispatch_remove 和 bfq_remove_request函数

1. static void bfq_dispatch_remove(struct request_queue *q, struct request *rq)
2. {
3.      struct bfq_queue *bfqq = RQ_BFQQ(rq);
4.      //派发的req数加1
5.       bfqq->dispatched++;
6.      /*核心是计算得到bfqd->peak_rate，bfq_calc_max_budget()中根据bfqd->peak_rate计算bfqd->bfq_max_budget*/
7.       bfq_update_peak_rate(q->elevator->elevator_data, rq);
8.      /*选择一个新的req作为bfqq->next_rq，计算更新新的entity->budget，把req从bfqq->sort_list链表剔除*/
9.       bfq_remove_request(q, rq);
10. }

bfq_dispatch_remove()函数中：执行bfq_update_peak_rate()计算新的bfqd->peak_rate，这个影响到bfqd->bfq_max_budget参数。接着，执行bfq_remove_request()选择一个新的IO请求req作为bfqq->next_rq，并计算更新新的entity->budget，把本次派发的IO请求从bfqq->sort_list链表剔除。

下边讲解bfq_remove_request()函数，先看下流程图

static void bfq_remove_request(struct request_queue *q,

1.                    struct request *rq)
2. {
3.      struct bfq_queue *bfqq = RQ_BFQQ(rq);
4.      struct bfq_data *bfqd = bfqq->bfqd;
5.      const int sync = rq_is_sync(rq);
6.      ............
7.      //如果要派发的req是bfqq->next_rq，则要选择一个新的bfqq->next_rq
8.      if (bfqq->next_rq == rq) {
9.          //从bfq调度器st红黑树或bfqq->sort_list或bfqq->fifo 选择下一个要派发的req
10.          bfqq->next_rq = bfq_find_next_rq(bfqd, bfqq, rq);
11.          //计算更新新的entity->budget，并执行bfq_requeue_bfqq()把bfqq重新插入队列
12.          bfq_updated_next_req(bfqd, bfqq);
13.      }
14.      if (rq->queuelist.prev != &rq->queuelist)
15.          list_del_init(&rq->queuelist);
16.      //派发一个req少一个，bfqq->queued[sync]和bfqd->queued减1
17.      bfqq->queued[sync]--;
18.      bfqd->queued--;
19.      //req从bfqq->sort_list链表剔除
20.      elv_rb_del(&bfqq->sort_list, rq);
21.      //req从rq->hash链表剔除
22.      elv_rqhash_del(q, rq);
23.      if (q->last_merge == rq)
24.            q->last_merge = NULL;
25.       ............  
26.      //如果bfqq上没有派发的req
27.      if (RB_EMPTY_ROOT(&bfqq->sort_list))
28.     {
29.            bfqq->next_rq = NULL;
30.          //如果bfqq有busy状态并且bfqq不是bfqd->in_service_queue正在使用的bfqq
31.            if (bfq_bfqq_busy(bfqq) && bfqq != bfqd->in_service_queue)
32.            {
33.              /*bfqq没有req派发了，清理bfqq的busy状态，把bfqq(entity)从st->active红黑树踢掉，有可能再把bfqq插入到st->idle红黑树*/
34.                  bfq_del_bfqq_busy(bfqd, bfqq, false);
35.                  bfqq->entity.budget = bfqq->entity.service = 0;
36.            }
37.         ............
38.     } else {}
39.     ............
40. }

bfq_remove_request()函数中，主要是选择一个新的IO请求req作为bfqq->next_rq，计算更新的entity->budget，把本次派发的IO请求req从bfqq->sort_list链表剔除。

本来还想对bfq源码做更详细的介绍，但是没想到bfq的源码真的复杂，本文篇幅已经过长，只能在稍后的篇章介绍。最后，水平有限，如有错误请指正。