内核block层IO调度器—bfq算法之深入探索1"/>
内核block层IO调度器—bfq算法之深入探索1
之前已经写了3篇介绍bfq算法的文章:《内核block层IO调度器—bfq算法之1整体流程介绍》、《内核block层IO调度器—bfq算法之2源码详解》、《内核block层IO调度器—bfq算法之3源码要点总结》,介绍了一下 bfq的基本的工作原理,是否代表对bfq算法就理解透彻了呢?No!首先,bfq算法本身比deadline庞大很多,能把大部分源码看懂已经很不错!同时,bfq算法还有很多关键细节,比如源码里经常能看到bic、bfq_bfqq_wait_request、bfq_bfqq_non_blocking_wait_rq、bfq_bfqq_busy、bfqd->peak_rate、bfqq->max_budget、bfqq->budget_timeout、idle_slice_timer等等,这些宏定义或者变量表面看着波澜不惊,但对bfq算法起着重要作用。本文先介绍其中一大部分,奈何bfq算法的这些宏定义或变量太多,一片文章讲不完!
在看本文前,希望读者先看下之前写的3篇介绍bfq算法的文章,打个基础。本文基于centos 8.3,内核版本4.18.0-240.el8,详细源码注释见 .18.0-240.el8。
1 bic和rq->elv.priv 原理
首先问个问题,我们知道每个派发IO请求的进程都要先分配一个bfqq,后续该进程的IO请求req也是添加到bfqq的队列,每个派发IO的进程都要绑定一个bfqq!之后,进程每派发一个IO请求,都消耗bfqq一定的配额,等bfqq的配额消耗光了,就要令bfqq过期失效。当然,如果bfqq没有要派发的IO请求了,也要令bfqq过期失效。但有一个不同点,此时还要把bfqq的entity移动到st->idle 红黑树。后续如果该进程又有新的IO请求要派发,就要先取出该进程绑定的bfqq,然后激活bfqq,把它的entity加入st->active红黑树。问题来了,“后续如果该进程又有新的IO请求要派发,就要先取出该进程绑定的bfqq”,从哪里取出进程绑定的bfqq呢?没错,就是通过bic和rq->elv.priv!下边看下源码:
这里有3个关键的数据结构,bic、ioc、icq,后边后经常用到,先把他们的原型定义列下:
- struct bfq_io_cq {//bic
- struct io_cq icq;//bic包含icq
- struct bfq_queue *bfqq[2];
- ..........
- }
- struct io_cq {//icq
- struct request_queue *q;
- struct io_context *ioc; //icq指向ioc
- }
- struct io_context {//ioc
- .........
- //icq在ioc的icq_tree
- struct radix_tree_root icq_tree;
- struct io_cq __rcu *icq_hint
- }
继续,进程把IO请求添加到bfqq的队列过程,是先尝试通过rq->elv.priv[1]查找bfqq,能找到直接返回,否则就通过bic查找bfqq,源码如下:
- static struct bfq_queue *bfq_init_rq(struct request *rq)
- {
- const int is_sync = rq_is_sync(rq);
- //新的IO请求req插入bfqq队列时,先查找rq->elv.priv[1]中是否有bfqq,有的话直接返回。rq->elv.priv[1]本身保存的是req所属的bfqq
- if (rq->elv.priv[1])
- return rq->elv.priv[1];
- //由 rq->elv.icq 得到bic
- bic = icq_to_bic(rq->elv.icq);
- //先尝试通过 bic->bfqq[is_sync]得到bfqq,失败则分配新的bfqq
- bfqq = bfq_get_bfqq_handle_split(bfqd, bic, bio, false, is_sync,&new_queue);
- .........
- rq->elv.priv[0] = bic;//rq->elv.priv[0]保存bic
- rq->elv.priv[1] = bfqq;//rq->elv.priv[1] 保存bfqq
- }
- //通过rq->elv.icq得到bic
- static struct bfq_io_cq *icq_to_bic(struct io_cq *icq)
- {
- return container_of(icq, struct bfq_io_cq, icq);
- }
- struct request {
- ..........
- union {
- struct {
- //新的req插入时,bfq_init_rq()中icq_to_bic(rq->elv.icq)由icq得到struct bfq_io_cq *bic。blk_mq_sched_assign_ioc()中赋值
- struct io_cq *icq;
- /*rq->elv.priv[1]保存新分配的bfqq,rq->elv.priv[0]保存bic,bic来自req->elv->icq指针所在的bfq_io_cq。bfq_init_rq()新的req插入时,先查找rq->elv.priv[1]中是否有bfqq,有的话直接从取出返回,否则才会分配新的bfqq。bfq_init_rq()中rq->elv.priv[0] = bic;rq->elv.priv[1] = bfqq*/
- void *priv[2];
- } elv;
- }
- }
通过bic查找bfqq重点是执行bfq_get_bfqq_handle_split()函数,然后把找到的bfqq保存到rq->elv.priv[1],把bic结构保存到rq->elv.priv[0]。
bic = icq_to_bic(rq->elv.icq)是个重点,本质就是通过icq得到bic,rq->elv.icq是什么时间赋值的呢?是传输IO请求前分配struct request结构时,看下这个流程blk_mq_make_request->__blk_mq_alloc_request()->blk_mq_rq_ctx_init()->blk_mq_sched_assign_ioc(),重点是blk_mq_sched_assign_ioc()函数。
- void blk_mq_sched_assign_ioc(struct request *rq)
- {
- struct request_queue *q = rq->q;
- struct io_context *ioc;
- struct io_cq *icq;
- //取出进程ioc
- ioc = current->io_context;
- ........
- //由ioc找到icq,本质是在ioc->icq_tree树种根据request_queue ID查找icq
- icq = ioc_lookup_icq(ioc, q);
- if (!icq) {
- //分配icq并把icq按照request_queue ID插入 ioc->icq_tree树
- icq = ioc_create_icq(ioc, q, GFP_ATOMIC);
- }
- ........
- //icq赋于rq->elv.icq
- rq->elv.icq = icq;
- }
- struct io_cq *ioc_lookup_icq(struct io_context *ioc, struct request_queue *q)
- {
- /*以request_queue->id这个块设备队列索引在ioc->icq_tree 中找到icq。ioc我猜测代表当前进程读写的块设备的总结构,一个进程可能会读写多个块设备的文件系统,每个块设备对应进程都有一个icq,以块设备运行队列q->id插入到ioc->icq_tree这个redix tree*/
- icq = radix_tree_lookup(&ioc->icq_tree, q->id);
- return icq;
- }
看到没,struct io_context *ioc其实来自进程task_struct结构的current->io_context,然后执行icq = ioc_lookup_icq(ioc, q)在ioc->icq_tree树种根据request_queue ID查找icq。ioc代表的是一个进程,icq代表的是一个块设备,根据该块设备的request_queue ID保存在ioc->icq_tree树。一个进程可能会读写多个块设备,因此ioc->icq_tree树中可能有多个块设备的icq,不知道我的理解对不对?
icq是在icq = ioc_lookup_icq(ioc, q)找不到的情况下,执行icq = ioc_create_icq(ioc, q, GFP_ATOMIC)分配icq并把icq按照request_queue ID插入 ioc->icq_tree树。
疑问来了,ioc是什么时间分配的?是在进程传输IO请求的submit_bio->generic_make_request->generic_make_request_checks->create_io_context->create_task_io_context()环节,看下源码:
- static inline struct io_context *create_io_context(gfp_t gfp_mask, int node)
- {
- if (unlikely(!current->io_context))
- create_task_io_context(current, gfp_mask, node);
- return current->io_context;
- }
- int create_task_io_context(struct task_struct *task, gfp_t gfp_flags, int node)
- {
- struct io_context *ioc;
- int ret;
- //分配ioc
- ioc = kmem_cache_alloc_node(iocontext_cachep, gfp_flags | __GFP_ZERO,node);
- //ioc赋值给进程task->io_context
- task->io_context = ioc;
- }
- bic、ioc、icq错综复杂的关系,把他们的定义再发下:
- struct bfq_io_cq {//bic
- struct io_cq icq;//bic包含icq
- struct bfq_queue *bfqq[2];
- ..........
- }
- struct io_cq {//icq
- struct request_queue *q;
- struct io_context *ioc; //icq指向ioc
- }
- struct io_context {//ioc
- .........
- //icq在ioc的icq_tree
- struct radix_tree_root icq_tree;
- struct io_cq __rcu *icq_hint
- }
通过进程的task_struct结构current->io_context可以找到ioc,通过ioc的icq_tree找到icq,而icq是bic的成员,自然也可以通过icq找到bic,这就是bic、ioc、icq错综复杂的关系。同时呢,分配IO请求blk_mq_make_request->__blk_mq_alloc_request()->blk_mq_rq_ctx_init()->blk_mq_sched_assign_ioc()流程又rq->elv.icq = icq,把icq保存到了rq->elv.icq。因此等把该IO请求添加到bfqq队列,执行到bfq_init_rq()函数,在它里边执行bic = icq_to_bic(rq->elv.icq)通过rq->elv.icq先得到icq,再通过icq得到bic。
错综复杂的关系终于理的差不多了。最后从bfq_init_rq()执行到bfq_get_bfqq_handle_split()函数:
- static struct bfq_queue *bfq_get_bfqq_handle_split(struct bfq_data *bfqd,
- struct bfq_io_cq *bic,
- struct bio *bio,
- bool split, bool is_sync,
- bool *new_queue)
- {
- //先从 bic->bfqq[is_sync] 得到bfqq
- struct bfq_queue *bfqq = bic_to_bfqq(bic, is_sync);
- //从 bic->bfqq[is_sync] 成功得到bfqq则直接return
- if (likely(bfqq && bfqq != &bfqd->oom_bfqq))
- return bfqq;
- //分配一个新的bfqq
- bfqq = bfq_get_queue(bfqd, bio, is_sync, bic);
- //新分配的bfqq设置到 bic->bfqq[is_sync] 数组
- bic_set_bfqq(bic, bfqq, is_sync);//bic->bfqq[is_sync] = bfqq
- …………………
- }
- struct bfq_queue *bic_to_bfqq(struct bfq_io_cq *bic, bool is_sync)
- {
- return bic->bfqq[is_sync];
- }
先通过bic_to_bfqq(bic, is_sync)看能否找到bfqq,注意,bic->bfqq[2]有两个成员,一个是同步bfqq,一个是异步bfqq。如果找不到bfqq则执行bfq_get_queue()针对IO请求的同步或异步属性分配一个异步或者同步bfqq,然后执行bic_set_bfqq()把分配的bfqq保存到bic->bfqq[] 数组。后续就可以直接bfq_init_rq()->bfq_get_bfqq_handle_split(),通过bic_to_bfqq(bic, is_sync)从bic->bfqq[]数组得到bfqq。
最后,做个总结:进程第一派发IO请求,分配ioc、IO请求req、bfqq。bic->bfqq[]数组保存了bfqq。等下次该进程继续派发IO请求,在分配IO请求时执行到 blk_mq_make_request->__blk_mq_alloc_request()->blk_mq_rq_ctx_init()->blk_mq_sched_assign_ioc() ,取出当前进程的 ioc,再从 ioc 的radix tree 取出icq,再把 icq 赋于 rq->elv.icq。然后执行到 bfq_init_rq(),执行bic = icq_to_bic(rq->elv.icq)由icq得到bic,再 执行 bfq_get_bfqq_handle_split()->bic_to_bfqq(bic, is_sync) 从 bic->bfqq[is_sync] 取出进程绑定的 bfqq。
2:bfqq_wait_request和 idle_slice_timer原理讲解
bfqq_wait_request是bfqq的一种标记,执行bfq_mark_bfqq_wait_request(bfqq)设置该该标记,执行bfq_bfqq_wait_request(bfqq)用来判断bfqq是否设置了该标记,执行bfq_clear_bfqq_wait_request(bfqq)清理该标记。bfq源码有很多类似用法,这3种函数原型如下:
- void bfq_mark_bfqq_##name(struct bfq_queue *bfqq) \
- { \
- __set_bit(BFQQF_##name, &(bfqq)->flags); \
- } \
- void bfq_clear_bfqq_##name(struct bfq_queue *bfqq) \
- { \
- __clear_bit(BFQQF_##name, &(bfqq)->flags); \
- } \
- int bfq_bfqq_##name(const struct bfq_queue *bfqq) \
- { \
- return test_bit(BFQQF_##name, &(bfqq)->flags); \
- }
bfqq_wait_request有啥作用呢?它是bfq的idle_slice_timer定时器配合使用的。顾名思义,idle_slice_timer是一个定时器,跟bfq idle可能有关系?通过源码一探究竟。
首先,在IO请求传输完成执行的回调函数bfq_completed_request()里,
- static void bfq_completed_request(struct bfq_queue *bfqq, struct bfq_data *bfqd)
- {
- //bfq总的已经派发但是还没传输完成的IO请求个数减1
- bfqd->rq_in_driver--;
- //还没有传输完成的IO请求个数,为0表示所有的IO请求都传输完成了,跟bfqd->rq_in_driver类似
- bfqq->dispatched--;
- ..................
- //bfqq是bfq调度器当前正在使用的bfqd->in_service_queue
- if (bfqd->in_service_queue == bfqq)
- {/*bfqq上没有要派发的IO请求了,但有较大概率bfqq绑定的进程很快还有IO要传输,故bfqq还不能立即过期失效,而是进入idle状态(与bfqq的entity处于st->idle红黑树的idle状态不一样),启动idle_slice_timer定时器等待可能马上来的新的IO请求*/
- if (bfq_bfqq_must_idle(bfqq))
- {
- //bfqq上的IO请求额
- if (bfqq->dispatched == 0)
- //这里边启动 idle_slice_timer 定时器函数,定时器函数是 bfq_idle_slice_timer()
- bfq_arm_slice_timer(bfqd);
- return;
- } else if (bfq_may_expire_for_budg_timeout(bfqq))
- bfq_bfqq_expire(bfqd, bfqq, false,BFQQE_BUDGET_TIMEOUT);
- else if (RB_EMPTY_ROOT(&bfqq->sort_list) && (bfqq->dispatched == 0 ||!bfq_better_to_idle(bfqq)))
- bfq_bfqq_expire(bfqd, bfqq, false,BFQQE_NO_MORE_REQUESTS);
- }
- ..................
- }
如果本次传输完成的IO请求所属的bfqq是bfq调度器当前正在使用的bfqd->in_service_queue,并且bfqq->dispatched是0,说明这是bfqq最后一个传输完成的IO请求。如果if (bfq_bfqq_must_idle(bfqq))成立话,则执行bfq_arm_slice_timer(),启动idle_slice_timer 定时器函数。
bfq_bfqq_must_idle(bfqq)什么作用?我觉得主要是说,bfqq虽然最后一个IO请求派发完成了,但是有可能bfqq上还有要派发的IO请求,或者bfqq绑定的进程还有可能有新的IO请求马上就来,故不能令bfqq过期失效,然后执行bfq_arm_slice_timer(bfqd),接着直接return走。否则,就可能会执行bfq_bfqq_expire(bfqd, bfqq, false,BFQQE_BUDGET_TIMEOUT)令bfqq超时时间到而失效,或者执行bfq_bfqq_expire(bfqd, bfqq, false,BFQQE_NO_MORE_REQUESTS)令bfqq因没有要派发的IO请求而过期失效。
bfq_arm_slice_timer(bfqd)有什么神奇的地方,看下源码:
- static void bfq_arm_slice_timer(struct bfq_data *bfqd)
- {
- struct bfq_queue *bfqq = bfqd->in_service_queue;
- u32 sl;
- bfq_mark_bfqq_wait_request(bfqq);//mark bfqq_wait_request
- bfqd->last_idling_start = ktime_get();
- bfqd->last_idling_start_jiffies = jiffies;
- //启动 idle_slice_timer 定时器
- hrtimer_start(&bfqd->idle_slice_timer, ns_to_ktime(sl),HRTIMER_MODE_REL);
- }
首先执行bfq_mark_bfqq_wait_request()对bfqq标记bfqq_wait_request,然后执行hrtimer_start()启动idle_slice_timer定时器,定时器函数是 bfq_idle_slice_timer()。于是再看下bfq_idle_slice_timer()。
- //idle_slice_timer 定时器函数
- static enum hrtimer_restart bfq_idle_slice_timer(struct hrtimer *timer)
- {
- struct bfq_data *bfqd = container_of(timer, struct bfq_data,
- idle_slice_timer);
- struct bfq_queue *bfqq = bfqd->in_service_queue;
- bfq_idle_slice_timer_body(bfqd, bfqq);
- return HRTIMER_NORESTART;
- }
里边主要是执行bfq_idle_slice_timer_body(),看下它:
- static void bfq_idle_slice_timer_body(struct bfq_data *bfqd, struct bfq_queue *bfqq)
- {
- if (bfqq != bfqd->in_service_queue) {
- spin_unlock_irqrestore(&bfqd->lock, flags);
- return;
- }
- bfq_clear_bfqq_wait_request(bfqq);//clear bfqq_wait_request
- //bfqq超时时间到,则令bfqq因BFQQE_BUDGET_TIMEOUT而过期失效
- if (bfq_bfqq_budget_timeout(bfqq))
- reason = BFQQE_BUDGET_TIMEOUT;
- //bfqq没有要发的IO请求了,则令bfqq因BFQQE_TOO_IDLE而过期失效
- else if (bfqq->queued[0] == 0 && bfqq->queued[1] == 0)
- reason = BFQQE_TOO_IDLE;
- else//否则,跳到schedule_dispatch分支继续派发bfqq上的IO请求
- goto schedule_dispatch;
- //令bfqq因BFQQE_BUDGET_TIMEOUT或BFQQE_TOO_IDLE而过期失效
- bfq_bfqq_expire(bfqd, bfqq, true, reason);
- schedule_dispatch:
- spin_unlock_irqrestore(&bfqd->lock, flags);
- bfq_schedule_dispatch(bfqd);
- }
bfq_idle_slice_timer_body()主要先bfq_clear_bfqq_wait_request()清理bfqq的bfqq_wait_request标记,然后就看bfqq的超时时间是否到了,或者bfqq上是否没有要派发的IO请求了,如果是的话则令bfqq因BFQQE_BUDGET_TIMEOUT或BFQQE_TOO_IDLE而过期失效。否则,执行bfq_schedule_dispatch()继续派发bfqq上的IO请求。
然而呢,从IO传输完成bfq_completed_request()->bfq_arm_slice_timer()启动idle_slice_timer定时器,到定时时间到执行bfq_idle_slice_timer()这段时间里,如果有新的IO请求来了并插入到bfqq的队列,会发生什么呢?
首先看下派发IO请求的流程__bfq_dispatch_request()->bfq_select_queue()
- static struct bfq_queue *bfq_select_queue(struct bfq_data *bfqd)
- {
- bfqq = bfqd->in_service_queue;
- .............
- next_rq = bfqq->next_rq;//选择优先派发的req
- if (next_rq) {
- //bfq_serv_to_charge()是计算并返回传输本次req需要配额,bfq_bfqq_budget_left()是该bfqq还剩余的配额。前者大于后者,说明
- //bfqq的配额不够了,则要是bfqq失效,选择新的bfqq
- if (bfq_serv_to_charge(next_rq, bfqq) >
- bfq_bfqq_budget_left(bfqq)) {
- reason = BFQQE_BUDGET_EXHAUSTED;
- goto expire;
- } else {
- if (bfq_bfqq_wait_request(bfqq)) {//使用 bfqq_wait_request
- bfq_clear_bfqq_wait_request(bfqq);//clear bfqq_wait_request
- hrtimer_try_to_cancel(&bfqd->idle_slice_timer);//取消 idle_slice_timer 定时器
- }
- goto keep_queue;
- }
- }
- ...........
- }
在bfq_select_queue()中,取出从bfqd->in_service_queue取出还没有失效的bfqq,然后派发bfqq->next_rq这个IO请求。继续,如果bfqq的配额足够,则if (bfq_serv_to_charge(next_rq, bfqq) >bfq_bfqq_budget_left(bfqq))不成立,继而执行else分支。先判断if (bfq_bfqq_wait_request(bfqq))判断bfqq是否被设置了bfqq_wait_request标记,是的话则执行bfq_clear_bfqq_wait_request(bfqq)清理该标记,并执行hrtimer_try_to_cancel(&bfqd->idle_slice_timer)取消idle_slice_timer 定时器。后续就是真正派发bfqq->next_rq这个IO请求。
到这里,我们发现bfqq的bfqq_wait_request标记和idle_slice_timer定时器主要是令bfqq延迟过期失效,因为bfqq可能还有要派发的IO请求,或者bfqq马上就来了新的IO请求,这样就能快速派发这些IO请求,避免延迟。
正常情况,当bfqq最后一个IO请求派发后,执行到bfq_completed_request()里,是执行下边的bfq_bfqq_expire()令bfqq过期失效。这样如果bfqq过了短暂的时间,bfqq又有新的IO请求来了,bfqq还得激活,还得被bfq调度到,才能派发这个IO请求,这就会造成延迟。现在是令bfqq本没有要派发的IO请求了而延迟过期失效,如果短时间内就来了新的IO请求,就能立即调度派发,挺巧妙。
另外提一点,在派发IO请求执行到bfq_select_queue()函数,如果bfqq被设置了bfqq_wait_request标记,说明它启动了ilde timer延迟失效,但现在新的IO请求派发,于是就bfq_clear_bfqq_wait_request()清理bfqq_wait_request标记,并hrtimer_try_to_cancel()取消idle timer定时器。
3:bfqq_non_blocking_wait_rq原理讲解
bfqq_non_blocking_wait_rq跟bfqq_wait_request标记的使用原理是一样的,但作用有差异。首先看下它是什么标记的,
- void bfq_bfqq_expire(struct bfq_data *bfqd,
- struct bfq_queue *bfqq,
- bool compensate,
- enum bfqq_expiration reason)
- {
- _bfq_bfqq_expire(bfqd, bfqq, reason);
- if (!bfq_bfqq_busy(bfqq) &&//使用 bfqq_busy
- reason != BFQQE_BUDGET_TIMEOUT &&
- reason != BFQQE_BUDGET_EXHAUSTED)
- {
- bfq_mark_bfqq_non_blocking_wait_rq(bfqq);//mark bfqq_non_blocking_wait_rq
- } else
- entity->service = 0;
- }
在bfqq到期失效执行bfq_bfqq_expire()函数时,如果bfqq的配额没消耗光(即失效reason是BFQQE_NO_MORE_REQUESTS)而只是没有要派发的IO请求而导致bfqq失效。则执行_bfq_bfqq_expire()函数把bfqq的entity从st->active红黑树剔除而加入st->idle红黑树,并清除bfqq的busy状态。bfq_bfqq_busy(bfqq)返回false,并因为reason是BFQQE_NO_MORE_REQUESTS。则if (!bfq_bfqq_busy(bfqq) &&reason != BFQQE_BUDGET_TIMEOUT &&reason != BFQQE_BUDGET_EXHAUSTED)判断成立,执行bfq_mark_bfqq_non_blocking_wait_rq()设置bfqq的bfqq_non_blocking_wait_rq标记。
然后等该bfqq绑定的进程又来了新的IO请求,则需要先激活bfqq,并把bfqq的entity插入的st->active 红黑树。这个过程先执行bfq_activate_bfqq()函数:
- void bfq_activate_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq)
- {
- struct bfq_entity *entity = &bfqq->entity;
- //把bfqq的entity插入到st->active红黑树
- bfq_activate_requeue_entity(entity,bfq_bfqq_non_blocking_wait_rq(bfqq),false, false);//使用 bfqq_non_blocking_wait_rq
- //clear bfqq_non_blocking_wait_rq
- bfq_clear_bfqq_non_blocking_wait_rq(bfqq);
- }
首先执行bfq_bfqq_non_blocking_wait_rq(bfqq)判断bfqq是否设置了bfqq_non_blocking_wait_rq标记,设置的话返回true,然后执行bfq_activate_bfqq->bfq_activate_requeue_entity->__bfq_activate_requeue_entity(entity, sd, non_blocking_wait_rq)->__bfq_activate_entity(entity, non_blocking_wait_rq),在__bfq_activate_entity()函数里,
- static void __bfq_activate_entity(struct bfq_entity *entity,
- bool non_blocking_wait_rq)
- {
- /*如果bfqq被设置了non_blocking_wait_rq标记,并且 st->vtime大于 entity->finish,则 min_vstart 设置为 entity->finish。为什么这样做?这样可以保证下边把bfqq的entity插入st->active tree时,更靠近st->active tree左边,这样更容易被调度到。*/
- if (non_blocking_wait_rq && bfq_gt(st->vtime, entity->finish)) {
- backshifted = true;
- min_vstart = entity->finish;
- } else
- min_vstart = st->vtime;
- //entity现在处于st->idle tree
- if (entity->tree == &st->idle) {
- //entity从st->idle tree剔除掉,可能更新st->first_idle或st->last_idle
- bfq_idle_extract(st, entity);
- entity->start = bfq_gt(min_vstart, entity->finish) ?
- min_vstart : entity->finish;
- }
- //按照entity->budget计算entity的虚拟运行时间并累加到entity->finish,最后把entity按照新的entity->finish插入st->active红黑树
- bfq_update_fin_time_enqueue(entity, st, backshifted);
- }
如果bfqq被设置了bfqq_non_blocking_wait_rq标记,则non_blocking_wait_rq是true,并且 st->vtime大于 entity->finish,则min_vstart = entity->finish,然后再执行下边的entity->start = bfq_gt(min_vstart, entity->finish) ?min_vstart : entity->finish,本质entity->start= entity->finish而不是entity->start=st->vtime,entity->finish更小。这样下边执行bfq_update_fin_time_enqueue()用entity->start计算entity->finish时,entity->finish就更小。
bfqq_non_blocking_wait_rq 的意义是什么呢?就是在bfqq因没消耗光配额而只是没有要派发的IO请求而导致bfqq失效的情况下,把bfqq的entirty加入到st->idle红黑树,设置bfqq_non_blocking_wait_rq标记。这样将来该bfqq绑定的进程有派发了新的IO请求时,把该bfqq重新激活时,因为 bfqq被设置了bfqq_non_blocking_wait_rq标记,则令 entity->start = min_vstart = entity->finish ,这样bfq_update_fin_time_enqueue()计算出来的 entity->finish = entity->start + entity->budget/N ,entity->finish更小。从而保证把bfqq的entity插入st->active红黑树时,更靠近st->active tree左边,这样更容易被调度到,尽可能早的派发该bfqq的IO请求。这就是 bfqq_non_blocking_wait_rq 的意义。
4:bfqq_busy原理讲解
bfqq_busy相对就简单多了,把bfqq激活就设置bfqq_busy,bfqq失效就清理bfqq_busy。
- void bfq_add_bfqq_busy(struct bfq_data *bfqd, struct bfq_queue *bfqq)
- {
- bfq_activate_bfqq(bfqd, bfqq);
- bfq_mark_bfqq_busy(bfqq);//mark bfqq_busy
- //每向st->active红黑树添加一个bfqq,bfqq对应调度算法的bfqd->busy_queues[]成员加1
- bfqd->busy_queues[bfqq->ioprio_class - 1]++;
- if (!bfqq->dispatched)
- if (bfqq->wr_coeff == 1)//bfqq->wr_coeff
- bfq_weights_tree_add(bfqd, bfqq,&bfqd->queue_weights_tree);
- if (bfqq->wr_coeff > 1)//bfqq->wr_coeff
- bfqd->wr_busy_queues++;
- }
- void bfq_del_bfqq_busy(struct bfq_data *bfqd, struct bfq_queue *bfqq,bool expiration)
- {
- bfq_clear_bfqq_busy(bfqq);//clear bfqq_busy
- //每从st->active红黑树剔除一个bfqq,bfqq对应调度算法的bfqd->busy_queues[]成员见1
- bfqd->busy_queues[bfqq->ioprio_class - 1]--;
- if (bfqq->wr_coeff > 1)//bfqq->wr_coeff
- bfqd->wr_busy_queues--;
- bfq_deactivate_bfqq(bfqd, bfqq, true, expiration);
- }
使用bfq_bfqq_busy的地方挺多的,比如上一节的bfq_bfqq_expire()函数,这里不再赘述。
5:bfqq->budget_timeout原理讲解
bfqq->budget_timeout就是防止一个bfqq派发IO请求耗时太长而影响其他bfqq,在__bfq_dispatch_request)->bfq_select_queue->bfq_set_in_service_queue->__bfq_set_in_service_queue()派发IO请求,选中一个bfqq作为bfqd->in_service_queue后,就要设置bfqq->budget_timeout,看下源码:
- static void __bfq_set_in_service_queue(struct bfq_data *bfqd,
- struct bfq_queue *bfqq)
- {
- //设置bfqq的超时时间
- bfq_set_budget_timeout(bfqd, bfqq);
- bfqd->in_service_queue = bfqq;
- }
- static void bfq_set_budget_timeout(struct bfq_data *bfqd,
- struct bfq_queue *bfqq)
- {
- //设置bfqq超时时间
- bfqq->budget_timeout = jiffies + bfqd->bfq_timeout * timeout_coeff;
- }
在__bfq_insert_request()->bfq_rq_enqueued()向bfqq插入IO请求时,
- static void bfq_rq_enqueued(struct bfq_data *bfqd, struct bfq_queue *bfqq,
- struct request *rq)
- {
- if (rq->cmd_flags & REQ_META)
- bfqq->meta_pending++;
- //赋值req扇区结束地址
- bfqq->last_request_pos = blk_rq_pos(rq) + blk_rq_sectors(rq);
- //bfqq是正在使用的,并且bfqq设置了bfqq_wait_request标记
- if (bfqq == bfqd->in_service_queue && bfq_bfqq_wait_request(bfqq))
- {
- //rq传输的扇区数小于32,bfqq只有rq这一个同步IO或者异步IO请求
- bool small_req = bfqq->queued[rq_is_sync(rq)] == 1 &&
- blk_rq_sectors(rq) < 32;
- //bfqq超时时间到返回true
- bool budget_timeout = bfq_bfqq_budget_timeout(bfqq);
- /*如果要传输的IO请求数据量小于32个扇区并且bfqq没有过期超时等等,则直接return。这样避免bfq_clear_bfqq_wait_request清理bfqq_wait_request标记和bfqq失效,而保证够立即派发这个IO请求,因为它的bfqq是bfqd->in_service_queue*/
- if (small_req && idling_boosts_thr_without_issues(bfqd, bfqq) &&
- !budget_timeout)
- return;
- //到这里才会清理bfqq_wait_request标记并取消idle_slice_timer
- bfq_clear_bfqq_wait_request(bfqq);
- hrtimer_try_to_cancel(&bfqd->idle_slice_timer);
- ///budget_timeout为true说明bfqq传输IO请求时间已经很长则令bfqq超时过期失效
- if (budget_timeout)
- bfq_bfqq_expire(bfqd, bfqq, false,
- BFQQE_BUDGET_TIMEOUT);
- }
- }
- //bfqq超时时间到返回true
- static bool bfq_bfqq_budget_timeout(struct bfq_queue *bfqq)
- { //bfqq->budget_timeout <= jiffies 返回true,说明超时时间到了
- return time_is_before_eq_jiffies(bfqq->budget_timeout);
- }
if (bfqq == bfqd->in_service_queue && bfq_bfqq_wait_request(bfqq)) 的作用是:bfq_bfqq_wait_request()成立说明bfqq原本的IO请求已经传输完成了,但是bfqq没有立即失效,而是等待bfqq的进程是否很快又会有新的IO请求要派发,bfqq保持bfqd->in_service_queue保持不变。现在正是向这个bfqq添加新的IO请求,因为bfqq设置了bfqq_wait_request标记,则有很大概率立即派发这个IO请求,这是if (small_req && idling_boosts_thr_without_issues(bfqd, bfqq) &&!budget_timeout)可能成立,直接return。
但是如果bfqq的超时时间到了,if (small_req && idling_boosts_thr_without_issues(bfqd, bfqq) &&!budget_timeout)不成立,bfq_bfqq_budget_timeout(bfqq)返回true,则budget_timeout是true,就要执行bfq_bfqq_expire(bfqd, bfqq, false,BFQQE_BUDGET_TIMEOUT)令bfqq过期失效。
需要说明,如果bfqq超时时间不到,但bfq_rq_enqueued()中向bfqq添加的IO请求要传输的扇区数大于32个扇区,if (small_req && idling_boosts_thr_without_issues(bfqd, bfqq) &&!budget_timeout)不成立,就要bfq_clear_bfqq_wait_request()清理bfqq_wait_request标记和取消idle_slice_timer。之后bfqq就没有bfqq_wait_request标记了,就不能再享有bfqq_wait_request优先派发IO请求特权了。
使用bfq_bfqq_budget_timeout()判断bfqq是否超时的地方挺多的,比如
- //判断bfqq的超时时间是否到了
- static bool bfq_may_expire_for_budg_timeout(struct bfq_queue *bfqq)
- {
- return (!bfq_bfqq_wait_request(bfqq) ||//bfqq没有启动 idle timer
- bfq_bfqq_budget_left(bfqq) >= bfqq->entity.budget / 3)//bfqq配额消耗了三分之一
- &&
- bfq_bfqq_budget_timeout(bfqq);//bfqq->budget_timeout 超时时间到
- }
bfq_may_expire_for_budg_timeout()是在IO请求传输完成的bfq_completed_request()函数执行,用来判断bfqq是够该因传输耗时太长而过期失效。其他使用bfq_bfqq_budget_timeout()的地方不再赘述。
6:bfqd->peak_rate和bfqq->max_budget原理讲解
bfqd->peak_rate跟派发IO请求的速率有关系,它直接影响bfqq的配额计算。bfqd->peak_rate的更新是在派发IO请求的__bfq_dispatch_request->bfq_dispatch_rq_from_bfqq->bfq_dispatch_remove()->bfq_update_peak_rate()流程:
- static void bfq_update_peak_rate(struct bfq_data *bfqd, struct request *rq)
- {
- u64 now_ns = ktime_get_ns();
- ...............
- /*bfqd->last_dispatch是上次派发IO请求的时间,now_ns是本次的,如果相差时间大于100ms,并且派发的req全都传输完,直接goto update_rate_and_reset分支重置peak_rate*/
- if (now_ns - bfqd->last_dispatch > 100*NSEC_PER_MSEC &&
- bfqd->rq_in_driver == 0)
- goto update_rate_and_reset;
- //每派发一个req则bfqd->peak_rate_samples加1
- bfqd->peak_rate_samples++;
- /*1:如果还有IO请求没传输完成或者前后两个派发的IO请求的时间间隔小于BFQ_MIN_TT,2:前后两次派发的IO请求扇区地址接近等等。则if成立而令bfqd->sequential_samples加1。bfqd->sequential_samples与bfqd->peak_rate_samples意思接近,但是bfqd->sequential_samples在连续快速派发IO请求时才会加1,否则不加*/
- if ((bfqd->rq_in_driver > 0 ||
- now_ns - bfqd->last_completion < BFQ_MIN_TT)
- && !BFQ_RQ_SEEKY(bfqd, bfqd->last_position, rq))
- bfqd->sequential_samples++;
- //累加派发的req的字节数
- bfqd->tot_sectors_dispatched += blk_rq_sectors(rq);
- //每派发32个IO请求就重置一次bfqd->last_rq_max_size
- if (likely(bfqd->peak_rate_samples % 32))
- bfqd->last_rq_max_size =
- max_t(u32, blk_rq_sectors(rq), bfqd->last_rq_max_size);
- else
- bfqd->last_rq_max_size = blk_rq_sectors(rq);
- //从派发第一个req到当前派发req之间的时间差
- bfqd->delta_from_first = now_ns - bfqd->first_dispatch;
- //从派发第一个IO请求到当前派发IO请求之间的时间差太小直接goto update_last_values返回。否则时间执行下边的bfq_update_rate_reset()
- if (bfqd->delta_from_first < BFQ_RATE_REF_INTERVAL)
- goto update_last_values;
- update_rate_and_reset:
- //根据本段时间派发的IO请求的情况重新计算bfqd->peak_rate
- bfq_update_rate_reset(bfqd, rq);
- update_last_values:
- //本次派发的IO请求的结束扇区
- bfqd->last_position = blk_rq_pos(rq) + blk_rq_sectors(rq);
- if (RQ_BFQQ(rq) == bfqd->in_service_queue)
- bfqd->in_serv_last_pos = bfqd->last_position;
- //记录本次要派发req是的时间
- bfqd->last_dispatch = now_ns;
- }
bfq_update_peak_rate()函数更新一堆参数,注释写的比较清楚。,如果bfqq连续派发IO请求的时间间隔达到BFQ_RATE_REF_INTERVAL,则执行bfq_update_rate_reset()重新计算bfqd->peak_rate。
- //根据bfqd->delta_from_first这段时间派发的IO请求的情况重新计算bfqd->peak_rate
- static void bfq_update_rate_reset(struct bfq_data *bfqd, struct request *rq)
- {
- u32 rate, weight, divisor;
- //这段时间派发的IO请求数不能低于BFQ_RATE_MIN_SAMPLES,并且这段时间不能小于BFQ_RATE_MIN_INTERVAL。否则不重新计算bfqd->peak_rate
- if (bfqd->peak_rate_samples < BFQ_RATE_MIN_SAMPLES ||
- bfqd->delta_from_first < BFQ_RATE_MIN_INTERVAL)
- goto reset_computation;
- bfqd->delta_from_first =
- max_t(u64, bfqd->delta_from_first,
- bfqd->last_completion - bfqd->first_dispatch);
- //rate=传输IO请求的字节数/这段传输时间bfqd->delta_from_first,这是计算bfqd->delta_from_first这段时间传输IO请求数据量的速率
- rate = div64_ul(bfqd->tot_sectors_dispatched<<BFQ_RATE_SHIFT,
- div_u64(bfqd->delta_from_first, NSEC_PER_USEC));
- /*1:bfqd->sequential_samples是连续派发的IO请求次数,如果小于 bfqd->peak_rate_samples的3/4,并且新计算的IO请求传输速率rate小于bfqd->peak_rate。 2:新计算的IO请求传输rate大于20Msectors/s。这两个条件有一个成立都不会重新计算bfqd->peak_rate*/
- if ((bfqd->sequential_samples < (3 * bfqd->peak_rate_samples)>>2 &&
- rate <= bfqd->peak_rate) ||
- rate > 20<<BFQ_RATE_SHIFT)
- goto reset_computation;
- //bfqd->sequential_samples肯定小于bfqd->peak_rate_samples,计算出的weight在0~8
- weight = (9 * bfqd->sequential_samples) / bfqd->peak_rate_samples;
- //根据本次派发IO请求的时间bfqd->delta_from_first,重新计算weight
- weight = min_t(u32, 8,
- div_u64(weight * bfqd->delta_from_first,
- BFQ_RATE_REF_INTERVAL));
- //divisor在10~2
- divisor = 10 - weight;
- //peak_rate = peak_rate * (divisor-1) / divisor + rate / divisor
- bfqd->peak_rate *= divisor-1;
- bfqd->peak_rate /= divisor;
- rate /= divisor;
- bfqd->peak_rate += rate;
- //bfqd->peak_rate最小值必须是1
- bfqd->peak_rate = max_t(u32, 1, bfqd->peak_rate);
- //用bfqd->peak_rate计算bfqd->bfq_max_budget,应该是bfqd->peak_rate越大则bfqd->bfq_max_budget越大
- update_thr_responsiveness_params(bfqd);
- reset_computation:
- //bfqd->last_dispatch、bfqd->peak_rate_samples、bfqd->sequential_samples、bfqd->tot_sectors_dispatched重置
- bfq_reset_rate_computation(bfqd, rq);
- }
- static void update_thr_responsiveness_params(struct bfq_data *bfqd)
- {
- if (bfqd->bfq_user_max_budget == 0) {//bfqd->bfq_user_max_budget默认是0
- //用bfqd->peak_rate计算bfqd->bfq_max_budget,应该是bfqd->peak_rate越大则bfqd->bfq_max_budget越大
- bfqd->bfq_max_budget = bfq_calc_max_budget(bfqd);
- }
- }
- static unsigned long bfq_calc_max_budget(struct bfq_data *bfqd)
- {
- return (u64)bfqd->peak_rate * USEC_PER_MSEC *
- jiffies_to_msecs(bfqd->bfq_timeout)>>BFQ_RATE_SHIFT;
- }
bfqd->peak_ratede 计算过程挺繁琐的,但是我感觉主要是依据bfqd->tot_sectors_dispatched和bfqd->delta_from_first来计算得到该段时间内派发IO请求数据量的速率。bfqd->delta_from_first是bfqq派发IO请求的这段时间差,bfqd->tot_sectors_dispatched是这段时间累加派发的IO请求数据量。经过复杂的计算得到bfqd->peak_rate,然后执行执行update_thr_responsiveness_params()用bfqd->peak_rate计算得到bfqd->bfq_max_budget。我觉得如果派发IO请求的速率越快,bfqd->bfq_max_budget就越大,但目前还没有数据支撑。
bfqd->bfq_max_budget将会影响到bfqq->max_budget和bfqq的配额entity->budget,看下源码。首先在bfqq过期失效过程:
- void bfq_bfqq_expire(struct bfq_data *bfqd,
- struct bfq_queue *bfqq,
- bool compensate,
- enum bfqq_expiration reason)
- {
- __bfq_bfqq_recalc_budget(bfqd, bfqq, reason);
- __bfq_bfqq_expire(bfqd, bfqq, reason);
- }
在__bfq_bfqq_recalc_budget()函数根据bfqq的失效原因根据bfqd->bfq_max_budget计算bfqq->max_budget和bfqq的配额entity.budget,看下源码:
- //用 bfqd->bfq_max_budget 重新计算 bfqq->max_budget 和 bfqq->entity.budget
- static void __bfq_bfqq_recalc_budget(struct bfq_data *bfqd,
- struct bfq_queue *bfqq,
- enum bfqq_expiration reason)
- {
- struct request *next_rq;
- int budget, min_budget;
- min_budget = bfq_min_budget(bfqd);
- if (bfqq->wr_coeff == 1)//测试时有30或1
- budget = bfqq->max_budget;
- else
- budget = 2 * min_budget;
- .............
- if (bfq_bfqq_sync(bfqq) && bfqq->wr_coeff == 1) {
- //根据bfqq失效原因reason,计算budget
- switch (reason) {
- case BFQQE_TOO_IDLE:
- if (bfqq->dispatched > 0)
- budget = min(budget * 2, bfqd->bfq_max_budget);
- else {
- if (budget > 5 * min_budget)
- budget -= 4 * min_budget;
- else
- budget = min_budget;
- }
- case BFQQE_BUDGET_TIMEOUT:
- budget = min(budget * 2, bfqd->bfq_max_budget);
- break;
- case BFQQE_BUDGET_EXHAUSTED:
- budget = min(budget * 4, bfqd->bfq_max_budget);
- break;
- case BFQQE_NO_MORE_REQUESTS:
- budget = max_t(int, bfqq->entity.service, min_budget);
- break;
- default:
- return;
- }
- } else if (!bfq_bfqq_sync(bfqq)) {
- budget = bfqd->bfq_max_budget;
- }
- //更新bfqq->max_budget
- bfqq->max_budget = budget;
- ................
- /*如果bfqq上还有IO请求 (即bfqq->next_rq)要派发,则计算根据next_rq传输的字节数计算bfqq->entity的配额,保证bfqq的配额还能传输完next_rq*/
- next_rq = bfqq->next_rq;
- if (next_rq)
- bfqq->entity.budget = max_t(unsigned long, bfqq->max_budget,
- bfq_serv_to_charge(next_rq, bfqq));
- }
- static int bfq_min_budget(struct bfq_data *bfqd)
- {
- if (bfqd->budgets_assigned < bfq_stats_min_budgets)
- return bfq_default_max_budget / 32;
- else
- return bfqd->bfq_max_budget / 32;
- }
源码比较简单,bfqq失效的原因不一样,则budget配额的计算方式不同。但是可以发现一个规律,如果bfqq是因为配额消耗光了,则budget = min(budget * 4, bfqd->bfq_max_budget),这样计算出来的配额较大;如果bfqq是没有要派发的IO请求了,则budget = max_t(int, bfqq->entity.service, min_budget),这样计算出来的配额就较小。这点是合理的,如果bfqq是因为配额消耗光而过期失效,说明的它的配额不够,就应该加大配额。如果bfqq是没有要派发的IO请求而过期失效,说明配额足够的,浪费了,就应该给其他bfqq让点配额。
在bfq_updated_next_req()会使用bfqq->max_budget 计算新的entity->budget,看下源码:
- static void bfq_updated_next_req(struct bfq_data *bfqd,
- struct bfq_queue *bfqq)
- {
- struct bfq_entity *entity = &bfqq->entity;
- struct request *next_rq = bfqq->next_rq;
- unsigned long new_budget;
- if (!next_rq)
- return;
- //bfqq是正在使用则直接返回
- if (bfqq == bfqd->in_service_queue)
- return;
- //用bfqq->max_budget 计算新的entity->budget
- new_budget = max_t(unsigned long,
- max_t(unsigned long, bfqq->max_budget,
- bfq_serv_to_charge(next_rq, bfqq)),
- entity->service);
- if (entity->budget != new_budget) {
- //更新新的entity->budget
- entity->budget = new_budget;
- bfq_requeue_bfqq(bfqd, bfqq, false);
- }
- }
bfq_updated_next_req()函数什么情况下会执行呢?下边看下
1:派发IO请求流程__bfq_dispatch_request->bfq_dispatch_rq_from_bfqq->bfq_dispatch_remove()->bfq_remove_request()->bfq_updated_next_req()
2:把IO请求插入到到bfqq队列过程__bfq_insert_request()->bfq_add_request()->bfq_updated_next_req()。但是情况2下需要bfqq不是bfqd->in_service_queue才会执行到用bfqq->max_budget 计算新的entity->budget的代码,具体可以看下bfq_updated_next_req()代码。并且,此时bfqq必须已经激活,即处于st->active红黑树,不能是过期失效处于st->idle红黑树。
文章结束,bfqq还有很多知识点每讲解到,比如bfqq->wr_coeff、bfqq_in_large_burst、bfqq_just_created、bfqq_softrt_update、bfqq_split_coop、bfqq_coop。等待后续的研究吧,bfq算法真的复杂!本文如果错误请指出。
更多推荐
内核block层IO调度器—bfq算法之深入探索1
发布评论