Home Linux Block IO层多队列机制(blk-mq)介绍
Post
Cancel

Linux Block IO层多队列机制(blk-mq)介绍

导读

本文首先从背景和架构上简单介绍blk-mq框架,随后会通过数据结构和具体流程去更加深入了解该机制的内部实现。

背景

什么是blk-mq

The Multi-Queue Block IO Queueing Mechanism is an API to enable fast storage
devices to achieve a huge number of input/output operations per second (IOPS)
through queueing and submitting IO requests to block devices simultaneously,
benefiting from the parallelism offered by modern storage devices.

TL;DR blk-mq是内核block层的多队列IO框架,适用于高IOPS要求的多队列存储设备。

为什么需要blk-mq

bottleneck 软件瓶颈

主要原因是multi-core和multi-queue的发展,性能瓶颈从硬件本身转移到软件层面上:单队列框架对于锁竞争和远端内存访问成为了性能问题。因此,重构是必须的。

benchmark-IOPS

benchmark-latency

在具体的跑分上,可以看出单队列框架(SQ)在扩展性上是无法满足硬件发展的。

框架概览

overview

为了减少锁争用和尽可能利用局部性原理,blk-mq把同时负责提交和派发的单一队列拆分为多层级和多队列。

blk-mq框架中有2种形式的队列:

  • per-cpu级别的软件队列Software Staging Queue。
    • 一般称为software queue、software staging queue、ctx (context)。
    • 对应于数据结构blk_mq_ctx
  • 对应于存储设备硬件队列的Hardware Dispatch Queue。
    • 一般有hardware queue、hctx (hardware context)、hwq等奇怪命名。
    • 对应于数据结构blk_mq_hw_ctx
    • 进入该队列的request意味着已经经过了调度。

而每个存储设备有一个controlling structure,为blk_mq_tag_set,用于维护队列的关系:

字段 类型 用途 备注
.mq_maps int*,实际作为一个int[]数组使用,长度为CPU个数 实现CPU到硬件队列的映射 下标为CPU编号,对应值为映射的硬件队列编号。比如set->mq_map[cpu_j] = hw_queue_i,其中ij互不相干
.tags blk_mq_tags**,实际作为一个(blk_mq_tags*)[]数组使用,长度为CPU个数 管理request分配,为每个hwq分配set->tags[hw_queue_id]  

硬件队列关联了tag(从而间接关联到request),其结构体对应于blk_mq_tags

字段 类型 用途 备注
.static_rqs request**,实际作为一个(request*)[]数组使用,长度为队列深度参数set->queue_depth buddy中预先分配set->queue_depthrequest实例,等待后续使用 该数组需要tag分配,由搭配的一个位图(sbitmap)来快速获得空闲的tag。每一次派发request前需要获取到tag与之绑定
.rqs request**,实际作为一个(request*)[]数组使用,长度为队列深度参数set->queue_depth static_rqs[tag]中获得的request实例在非电梯调度下会放入该数组中(同下标),表示in-flight request 实际我不知道是干嘛的,一种可能的用法是给driver提供一个遍历所有使用中的request的迭代器。所有细节都在这里

tag-set与ctx的关系可以看下图:

tag

ctx

框架的初始化

流程之nvme_probe

blk-mq框架在driver层完成初始化,以nvme设备为例,初始化阶段分为上下半部。上半部开始于nvme_probe函数:

nvme_probe(...)
    dev = kzalloc_node(...)
    ...
    INIT_WORK(..., nvme_reset_work)


在异步流程中
nvme_reset_work(work)
    dev = container_of(work, ...)
    ...
    nvme_dev_add(dev)
    ...

nvme_dev_add(dev)
    dev->tagset.ops = nvme_mq_ops
    dev->tagset.nr_hw_queues = ...
        hwq的数目最终会被限制到min(硬件队列数,CPU数)
    dev->tagset.queue_depth = min(dev->q_dep, 10240) - 1
        这里tagset的队列深度还不是最后确定的,如果后续过程构造失败,kernel会尝试深度折半继续重试,直到深度只有1
    dev->tagset.flags = BLK_MQ_F_SHOULD_MERGE
    blk_mq_alloc_tag_set(alias set = dev->tagset)
        set->tags = kcalloc_node(nr_cpu_ids, sizeof *, ...)
            这里说明tags是一个元素类型为blk_mq_tags*,长度为CPU数的数组
        set->mq_map = kcalloc_node(nr_cpi_ids, sizeof, ...)
            mq_map是一个元素类型为int,长度为CPU数的数组
        blk_mq_update_queue_map(set)
            这个过程完成了CPU到hw queue的映射
            for-each cpu: set->mq_map[cpu] = 0
            set->ops->map_queues(ret)
                对应于实现nvme_pci_map_queues
                for-each hwq: for-each cpu-in-mask: set->mq_map[cpu] = queue
        blk_mq_alloc_rq_maps(set)
            构造set->tags[0...hctx_max-1]
            忽略深度折半的特殊情况
            for-each hwq, i: __blk_mq_alloc_rq_map(set, alias hctx_idx = i)
                构造set->tags[hctx_idx]
                set->tags[hctx_idx] = blk_mq_alloc_rq_map(set, hctx_id, ...)
                    获取numa_node node
                    定义(对应队列的)tags = blk_mq_init_tags(...)
                        tags->nr_tags和tags_nr_reserved_tags的确认
                        以及sbitmap的构造
                    tags->rqs = kcalloc_node(nr_tags, sizeof *)
                        rqs是一个元素类型为request*的长度为队列深度的数组
                    tags->static_rqs = kcalloc_node(nr_tgags, sizeof *)
                    return tags
                blk_mq_alloc_rqs(set, set->tags[hctx_id], hctx_id, queue_depth)
                    构造tags->page_list,按队列深度d将带payload的request大小乘上d,从buddy分配对应的page,(换行)\
                        并且用page的虚拟地址存放到static_rqs[...],其中多个page可以通过page_list遍历到
                    分配request后,可以从set->ops->init_request自定义初始化request
    dev->ctrl.tagset = dev->tagset

流程之nvme_alloc_ns

下半部的caller调用栈为:

nvme_alloc_ns
nvme_validate_ns
nvme_scan_ns_list
nvme_scan_work(async)
nvme_init_ctrl

其中,nvme_init_ctrl是使用workqueue异步触发nvme_scan_work

nvme_alloc_ns(ctrl, nsid)
    nvme_ns *ns = kzalloc_node(...)
    ns->queue = blk_mq_init_queue(ctrl->tagset) ⭐
    ns->queue->queuedata = ns
    ns->ctrl = ctrl
    ...
    disk = alloc_disk_node(...)
    disk->fops = nvme_fops
    disk->private_data = ns
    disk->queue = ns->queue
    ns->disk = disk
    ...

可以看出这里正式进入了blk-mq框架,并且把在上半部就构造好的tagset也传递到框架中。

此外,gendisk也建立了与nvme的关联,与blk-mq有关的地方就是disk->queue是来自ns且经过blk-mq框架构造的queue

流程之blk_mq_init_queue

这个流程是request_queue的初始化流程,涉及其绑定的ctxhctx

blk_mq_init_queue(set)
    q = blk_alloc_queue_node(GFP_KERNEL, ...)
        略,只返回一个未(半)构造已分配的request queue
    return blk_mq_init_allocated_queue(set, q)
        q->mq_ops = set->ops
        q->queue_ctx = alloc_percpu(...)
        q->queue_hw_ctx = kcalloc_node(nr_cpu_ids)
            hwctx是一个元素为指针,长度为CPU个数的数组
        q->mq_map = set->mq_map
        blk_mq_realloc_hw_ctxes(set, q)
            这里实际分配hctx实例
            for-each(i, 0, set->nr_hw_queues)
                only for empty hctxs[i]
                hctxs[i] = kzalloc_node(...)
                blk_mq_init_hctx(q, set, hctxs[i], alias hctx_idx = i)
                    hctx->queue = q
                    hctx->flag &= ~shared
                    hctx->tags = set->tags[hctx_idx]
                    hctx->ctxs = kmalloc_array_node(nr_cpu_ids, sizeof *)
                    hctx->nr_ctx = 0
                    set->ops->init_hctx(hctx, ...)
                        nvme的话主要是关联驱动层nvme_queue和hctx的关系
                    blk_mq_sched_init_hctx(q, hctx, hctx_idx)
                        构造hctx->sched_tags
                        elevator e = q->elevator
                        blk_mq_sched_alloc_tags(q, hctx, hctx_id)
                            hctx->sched_tags = blk_mq_alloc_rq_map()
                                重复,见nvme流程,构造sched_tags[...]每个元素实例
                            blk_mq_alloc_rqs(set, hctx->sched_tags, ...)
                                重复,见nvme流程,static_rq相关
                        e->type->ops.mq.init_hctx(...)
                            差不多吧,只是变成了sched_tag
                    hctx->fq = ...
                    blk_mq_init_request()
                        重复了,略
            TODO 这里会有调度层hctx构造
        q->nr_queues = nr_cpu_ids
        blk_queue_make_request
            注册q->make_request_fn回调为blk_mq_make_request
            q->nr_batching = BLK_BATCH_REQ = 32
        q->nr_request = set->queue_depth
        blk_mq_init_cpu_queues(q, set->nr_hw_queues)
            for-each cpu, i:
                get percpu ctx
                ctx->cpu = i
                ctx->queue = q
                ...
        blk_mq_add_queue_tag_set(set, q)
            基本上是关联q->tag_set = set
            以及处理shared模式下的hctx,略
        blk_mq_map_swqueue(q)
            处理软件队列到硬件对垒的映射
            for-each cpu, i:
                hctx_id = q->mq_map[i]
                    从map获取CPU到hctx的映射ID
                hctx = q->queue_hw_ctx[q->mq_map[cpu]]
                cpumask_set_cpu(i, hctx->cpumask)
                ctx->index_hw = hctx->nr_ctx
                hctx->ctxes[hctx->nr_ctx++] = ctx
                    一个hctx可以对应多个ctx,因此用index_hw表示ctx在hctx->ctxes[]中的下标
                for-each hctx(q, hctx, i):
                    hctx->tags = set->tags[i]
                    ...
        elevator_init_mq(q)
            选择默认的elevator
            单队列选择mq-deadline
            多队列或者没有mq-deadline选择none
        return q

框架的IO流程

流程之提交IO

userspace进行的IO操作,具体的IO类型和操作对象会以bio结构体描述,并在内核中会通过submit_bio统一接口进行提交。

submit_bio(bio)
    ...
    IO accounting stuff
    ...
    return generic_make_request_(bio)
        q = bio->bi_disk->queue
        ...
        workaround for stacked devices
        ...
        return q->make_request_fn(q, bio) ⭐

从前面的流程可以知道,blk-mq下的make_request_fn注册实例为blk_mq_make_request

blk_mq_init_allocated_queue()
    ...
    blk_queue_make_request(q, blk_mq_make_request)
        set default blk-mq limits
        q->make_request_fn = blk_mq_make_request
    ...

流程之处理IO

处理IO简而言之就是把bio转换为request结构体,并插入到请求队列中。

相较于提交IO是在当前进程的内核栈上进行,处理IO还有可能会在kblockd内核线程中异步执行。

blk_mq_make_request(q, bio)
    按需执行bio split(通常是按软硬件限制)
    按需合并到进程的plug队列,成功则结束
        precondition: !FLUSH_FUA && !NOMERGE
    blk_mq_sched_bio_merge
        尝试将sched队列中的pending request合并,成功则返回
    wbt_wait
        当超过writeback limit时,在这里提供一个阻塞点
    blk_mq_get_request
        返回一个request,需要static_rqs和sbitmap搭配使用
        note: 上面的按需合并没有完成,因此需要request
    条件分支:
        1. flush or fua
            需要尽快下达,跳过scheduler,request插入到单独的flush队列,唤醒执行hctx
        2. plug && q->nr_hw_queues == 1
            单队列设备且plug则加入plug的mq_list中
        3. plug && !no_merge
            和case2差不多,但这里是多队列的plug,略
        4. q->nr_hw_queues > 1 && sync
            多队列,没有plug走blk_mq_try_issue_directly
            读操作的话,应该适用于这里
        5. others
            走blk_mq_sched_insert_request
            这里会继续细分情况,比如是否flush,是否有elevator

如果是case4:
    • 非电梯情况下,就是直走到driver层提供的入队函数
    • 否则,走电梯sched_insert

如果是case5:
    • 非电梯情况下,会插入到ctx队列中
    • 否则,走电梯sched_insert

还需要查看run_queue设置,如果有,紧接着blk_mq_run_hw_queue执行hctx来批量派发IO
一般来说是run_queue = true,除非driver层告知hctx不可用

执行hctx(hw queue)的过程blk_mq_run_hw_queue可能是sync(同步)的,也可能是async(异步)的。在上述的条件分支中:

  • 如果是case4,那就是sync。
  • 如果是case5,那就是async。
blk_mq_run_hw_queue
    __blk_mq_delay_run_hw_queue
        __blk_mq_run_hw_queue
            blk_mq_sched_dispatch_requests
                这里就是sync入口

blk_mq_sched_dispatch_requests(hctx)
    LIST_HEAD(rq_list)
    if hctx->dispatch is not empty
        list_splice_init(hctx->dispatch, rq_list)
            在hctx实例中,dispatch字段是实质意义的请求队列,现在将其移交到栈上申请的rq_list
    分几种情况:
    1. blk_mq_dispatch_rq_list
        优先派发之前在hctx中没有派发的请求到驱动
    2. blk_mq_do_dispatch_sched
        将sched队列中的请求移入rq_list,然后调用blk_mq_dispatch_rq_list,派发到驱动
    3. blk_mq_do_dispatch_ctx
        在hctx busy的情况下,直接将ctx的rq移入到rq_list,然后派发给驱动, 公平起见,会考虑到轮流对多个ctx执行派发
    4. blk_mq_dispatch_rq_list
        其它情况将rq_list中请求派发给驱动处理

这个过程比较复杂,整体来看就是按照IO的特征来进行划分:

  • 设备:单队列还是多队列。
  • 硬件队列(hctx):繁忙还是空闲。
  • IO调度器(电梯):是否附着于blk-mq。
  • 蓄流操作:是否使能plug。
  • 请求类型:同步还是异步。

处理分类就是依据上面的特征来组合出不同分支路径:

  1. 是否紧急,紧急直接下发,flush->hctx。
  2. 是否慢速设备,也就是单队列且plug。
  3. 多队列plug。
  4. IO调度器附着,表示与ctx互斥。
  5. plug且nomerges且无附着,基本是前面条件的corner case的意思。
  6. 是否跳过ctx,即无IO调度器附着、设备多队列、hctx空闲且IO同步。
  7. 默认分支,无IO调度且无plug的情况。
  8. 隐藏分支,本次IO处理失败,下次按照紧急情况处理。

上面组合后的结果一般是遵循如下的队列顺序:

        -> flush ------------------------>
request -> [pluglist] -> [ctx || sched] -> hctx -> drivers/...

一些备注:

  • IO调度器队列与软件队列是互斥关系。IO调度器附着到blk-mq则不使用ctx。
  • plug是可选的。
  • hctx空闲时,部分请求是可以跳过ctx直达hctx(比如路径6)。

根据前人(一些原因,我不能提供参考链接)的分析结果,以下条件适用于默认路径(7):

  • EMMC设备(高速无plug单队列)的IO请求。
  • NVME设备,异步的IO请求。
  • NVME设备,同步的IO请求,并且hctx繁忙。

回到blk_mq_run_hw_queue,异步流程会有稍微不同的入口:

blk_mq_run_hw_queue
    __blk_mq_delay_run_hw_queue
-       __blk_mq_run_hw_queue
+       kblockd_mod_delayed_work_on
+       mod_delayed_work_on(cpu = hctx_next_cpu, kblockd_workqueue, dwork = hctx->run_work, delay = 0)

任务分配的注册在前面的初始化流程:

blk_mq_init_hctx
    ...
    INIT_DELAYED_WORK(&hctx->run_work, blk_mq_run_work_fn)

这里涉及到workqueue机制,关注一下它的使用context:

  • 线程实例:kblockd
  • 任务类型:delayed_work类型的hctx->run_work
  • 具体任务:其run_work对应于blk_mq_run_work_fn
blk_mq_run_work_fn(work)
    hctx = container_of(work, ...)
    __blk_mq_run_hw_queue(hctx)

其实blk_mq_run_work_fn峰回路转,还是回到了sync流程,只不过是交给了kblockd来处理。

不太重要的细节

  • blk-mq的硬件队列与驱动层的队列无关。
  • 虽然软件队列一般认为是per-cpu级别,但是maintainer也指出:如果在NUMA架构中,L3缓存足够大的话,软件队列可以设置为per-socket级别,这样也许能从cache友好和锁竞争中获取一个平衡点。
  • 硬件队列个数在不同的场合下是有歧义的,因为kernel里面会把超过CPU个数的硬件队列数目当作看不见(原因是超出部分没有意义),所以并不绝对等于硬件意义上的硬件队列个数。
  • tag虽然是给硬件队列使用,但是blk_mq_tags实际长度是按CPU个数给的。
  • tag对应的request数虽然是set提供的队列深度数,但是每次分配失败的话,会尝试把队列深度数目折半,这也会实际影响到set->queue_depth
  • 预分配request的每个实例中其实还藏有driver层所需要的payload。
  • ns->queue即是request_queue实例。
  • 提交IO过程中,generic_make_request已经随着SQ框架的移除也被移除,改为blk_mq_submit_bio,不过本质不变。
  • 处理IO过程中,case4走sync运行hctx是因为IO操作本来就是sync类型的。
  • “派发到driver层”指的是最终被queue_rq接口调用,具体实现和驱动是强相关的。

一些使用建议

Q. 我用的是比较传统的单队列设备,需要回归单队列框架吗?

A. 不需要。一是blk-mq实测性能仍高于sq框架,二是内核版本5.0后已经把sq框架彻底删了。


Q. 多队列框架下是否需要使用IO调度器?

A. 如果是HDD,要。对于(足够高性能的)SSD的话,比方说你需要公平调度,或者做一些QoS也许用得着,但只看性能的话,这是一个开放的话题(不服跑个分吧)。


Q. 如果确实需要选用IO调度器,该怎么选?

A. redhat文档中给出了一些场景选择,为了节省你的IO,我把要点摘抄下来了:

Use case Disk scheduler
Traditional HDD with a SCSI interface Use mq-deadline or bfq.
High-performance SSD or a CPU-bound system with fast storage Use none, especially when running enterprise applications. Alternatively, use kyber.
Desktop or interactive tasks Use bfq.
Virtual guest Use mq-deadline. With a host bus adapter (HBA) driver that is multi-queue capable, use none.

Q. 你这些调度器选项太naive了,有没有更加pro的调优选项?

A. 是我太菜了……这里有另外一份redhat文档可以自行参考。

TODO(已鸽🕊)

毫不意外的又鸽了相当一部分的内容:

  • 完成IO流程(中断相关)。
  • 处理IO流程的细节完善。
  • 合并、拆分IO流程。
  • 更新内核版本。

References

Multi-Queue Block IO Queueing Mechanism (blk-mq) – The Linux Kernel Archives
Linux Block IO: Introducing Multi-queue SSD Access on Multi-core Systems
Chapter 11. Setting the disk scheduler – Red Hat Customer Portal
Chapter 32. Factors affecting I/O and file system performance – Red Hat Customer Portal
An Introduction to the Linux Kernel Block I/O Stack – IBM

This post is licensed under CC BY 4.0 by the author.
Contents