内核block层IO调度器—bfq算法简单调试总结

本文主要记录bfqq实际调试数据，主要涉及多进程IO传输时bfq调度器如何选择哪个bfqq的entity去使用。在看本文前，建议读者先下之前写的3篇文章《内核block层IO调度器—bfq算法之1整体流程介绍》、《内核block层IO调度器—bfq算法之2源码详解》、《内核block层IO调度器—bfq算法之3源码要点总结》，打个基础。本文基于centos 8.3，内核版本4.18.0-240.el8，详细源码注释见 https://github.com/dongzhiyan-stack/linux-4.18.0-240.el8。

 废话不多说，先看下bfqq的entity在bfq调度器st->active和st->idle 红黑树的排布(为了演示简单，没有演示entity在红黑树中的树形排列形式，只是演示entity按照entity->finish由小到大从左向右排列)，如图：

一个进程派发IO请求都要先分配一个bfqq，然后把bfqq的entity按照entity->finish插入到st->acive 红黑树，entity->finish越小，entity在st->active红黑树越靠左，越容易被bfq调度器选中作为bfqd->in_service_queue，然后才能派发该bfqq上的IO请求。如果bfqq因bfqq没有要派发的IO请求了，则令bfqq过期失效而加入到st->ilde 红黑树。如果bfqq因为配额消耗光了，则令bfqq过期失效，然后是把bfqq重新加入st->active红黑树。

bfqq因配额消耗光而过期失效，函数流程是：__bfq_dispatch_request->bfq_select_queue()->bfq_bfqq_expire()->__bfq_bfqq_expire()->bfq_activate_requeue_entity()

1. static void bfq_activate_requeue_entity(struct bfq_entity *entity,
2.                     bool non_blocking_wait_rq,
3. {
4.       __bfq_activate_requeue_entity(entity, sd, non_blocking_wait_rq);
5.       if (!bfq_update_next_in_service(sd, entity, expiration) &&!requeue)
6.           break;
7. }

bfqq因配额消耗光而过期失效，最后只是执行__bfq_activate_requeue_entity()把bfqq的entity重新加入st->active红黑树。只是呢？在st->active红黑树排列的靠后！然后执行bfq_update_next_in_service()从st->active红黑树查找最新的合适的entity赋于sd->next_in_service。之后回到bfq_select_queue()函数，执行bfq_set_in_service_queue(bfqd)-> bfq_get_next_queue()，再把最新找到的sd->next_in_service赋于sd->in_service_entity，这就是bfq调度器当前使用的entity。回到bfq_set_in_service_queue()函数再执行__bfq_set_in_service_queue(bfqd, bfqq)，把sd->in_service_entity这个entity所属bfqq赋于bfqd->in_service_queue，这就是bfq调度器当前正在使用bfqq。

 bfq_update_next_in_service()函数中寻找最新的合适的entity赋于sd->next_in_service的过程是，bfq_update_next_in_service()->bfq_lookup_next_entity()->__bfq_lookup_next_entity()->bfq_first_active_entity()，最重要的代码是bfq_first_active_entity()中实现的，把它的源码再贴下：

1. //从st->active tree红黑树最左边查找entity->start最小并且entity->start小于vtime的entity
2. static struct bfq_entity *bfq_first_active_entity(struct bfq_service_tree *st,
3.                           u64 vtime) //从vtime大部分情况是st->vtime
4. {
5.     struct bfq_entity *entry, *first = NULL;
6.     struct rb_node *node = st->active.rb_node;
7.     while (node)
8.     {
9.          entry = rb_entry(node, struct bfq_entity, rb_node);
10. left:
11.  printk("1:%s %d %s %d entry:%llx entry->start:%lld vtime:%lld pid:%d\n",__func__,__LINE__,current->comm,current->pid,(u64)entry,entry->start,vtime,bfq_entity_to_bfqq(entry)->pid);
12.         if (!bfq_gt(entry->start, vtime))//entry->start < vtime 则if成立
13.                first = entry;
14.         //如果entry有左节点，一直向左查找，有靠左的entry，entry->start和entry->min_start越小
15.         if (node->rb_left)
16.        {
17.              entry = rb_entry(node->rb_left,
18.                      struct bfq_entity, rb_node);
19.              printk("2:%s %d %s %d entry:%llx entry->min_start:%lld vtime:%lld pid:%d\n",__func__,__LINE__,current->comm,current->pid,(u64)entry,entry->min_start,vtime,bfq_entity_to_bfqq(entry)->pid);
20.              if (!bfq_gt(entry->min_start, vtime)) {
21.                    node = node->rb_left;
22.                    goto left;
23.               }
24.         }
25.         if (first)
26.               break;
27.         node = node->rb_right;
28.     }
29.     return first;
30. }

本质就是在st->active红黑树最左边找一个entry->start最小并且entity->start小于st->vtime的entity。我们知道，st->active红黑树上的entity是按照entity->finish由小达大从左向右排列的，跟entry->start有什么关系？还不知道！感觉是个核心知识点。下文是在bfq_first_active_entity()中添加调试信息，打印涉及的变量及数据，如上bfq_first_active_entity()函数红色部分代码。

• //第1次找到 entry:ffff942b330eb888(绑定的进程pid是 6067)，但 entry->start > vtime 导致该entity不符合条件
• 1:bfq_first_active_entity 1511 kworker/3:1H 487 entry:ffff942b330eb888 entry->start:14821446688905 vtime:14820509868269 pid:6067
• //继续查找，找到entry:ffff942b330eb888 在红黑树再左边的节点 entry:ffff942b337ffc88，因 entry->min_start < vtime ，goto left分支
• 2:bfq_first_active_entity 1519 kworker/3:1H 487 entry:ffff942b337ffc88 entry->min_start:14820400546738 vtime:14820509868269 pid:6070
• //第2次找到 entry:ffff942b337ffc88(绑定的进程pid是 6070)，但 entry->start < vtime 成立，找到第1个符合条件的entity
• 1:bfq_first_active_entity 1511 kworker/3:1H 487 entry:ffff942b337ffc88 entry->start:14820437246898 vtime:14820509868269 pid:6070
• //继续查找，找到entry:ffff942b337ffc88 在红黑树再左边的节点entry:ffff942b330e9288，因 entry->min_start < vtime ，goto left分支
• 2:bfq_first_active_entity 1519 kworker/3:1H 487 entry:ffff942b330e9288 entry->min_start:14820437246898 vtime:14820509868269 pid:6071
• //第3次找到 entry:ffff942b330e9288(绑定的进程pid是 6071)，但 entry->start < vtime 成立，找到第2个符合条件的entity，终于找到st->active 最左边的entity
• 1:bfq_first_active_entity 1511 kworker/3:1H 487 entry:ffff942b330e9288 entry->start:14820437246898 vtime:14820509868269 pid:6071

 显然，最后从st->active红黑树终于找到符合条件的entity:ffff942b330e9288。这段是我fio测试+正常文件读写时，有大概6个进程同时传输IO请求时出现的打印。很明显，此时st->active红黑树至少有PID是6067、6070、6071的进程所属的bfqq的entity，是一直向st->active 红黑树左边查找合适的entity：先是entity的start小于vtime，同时该entity如果在红黑树有左节点，该左节点的entity的min_start还必须大于vtime，该entity才是最终查找到的entity。为了便于理解，画了entity在st->active tree红黑树中的排列情况，如下：

vtime经测试一般都是st->vtime，即调度器的虚拟运行时间。如图，6067号进程 的entity:0xffff942b330eb888是st->active 红黑树的根节点，再向左边是6070和6071号进程对应的entity。可以发现， entity->start越小，entity在st->active红黑树越靠左。之前我们说过，entity按照entity->finish插入st->active红黑树时，entity->finish越小，在st->active红黑树越靠左。而entity->finish的计算规则可以简化成：entity->finish = entity->start + entity->budget/(entity->weight*N)，如下看下源码：

1. static void bfq_update_fin_time_enqueue(struct bfq_entity *entity,
2.                     struct bfq_service_tree *st,
3.                     bool backshifted)
4. {
5.      //根据entity->budget/entity->weight计算entity已经消耗的虚拟运行时间，entity->start加上这段虚拟运行时间得到entity->finish
6.      bfq_calc_finish(entity, entity->budget);
7.      //把entity按照新的entity->finish插入st->active红黑树
8.      bfq_active_insert(st, entity);
9. }

因此，在配额entity->budget和权重entity->weight都是默认情况下，entity->finish和entity->start成线性正比关系。另外一个疑问点是就是entry->min_start，在bfq_first_active_entity()函数中查找合适的entity时，除了entity->start要小于vtime(调度器的虚拟运行时间)，还要看该entity左节点的entity的entity->min_start是否大于vtime，大于vtime才能说明该entity是最终要找的合适的entity。这点还需要后续再摸索一下。

bfq调度算法比较复杂，关于entity->start、entity->finish、entity->min_start、st->vtime、entity->budget、entity->weight，以及entity在st->active红黑树的排列何更新规则，还需要多实践和总结。本文结束，如有错误请指出！