Kernel_block

大部分在linux源码有所介绍, 这里针对代码层的实现大概讲解下 (可以用 https://code.woboq.org/linux/linux/include/linux/blk-mq.h.html 看, 但是最后还是下载到本地看代码了)

block I/O 请求是以 I/O 向量的形式进行提交和处理的

主要的数据结构

基本概念

部分基本概念在 深入理解linux内核 中有讲解.

sector: 硬件控制器的基本单元(传输数据的基本单元), 通常是512 block: vfs、fs 的基本数据单元(磁盘存储单元的最小视角), 扇区大小的整数倍, 比如2k、4k 段: 一个段就是一个内存页或者页的一部分. 管来管理磁盘上物理相邻的数据块 bio: 一次io操作. (block io的缩写, 包含多个段, 因为后续请求可能merge进来) 磁盘高速缓存: 用于磁盘数据的页 块缓冲区: 还没有接触到 物理段: 通用块层 将 ram页框连续并且磁盘上的数据块也是相邻的 进行合并 产生的内存区 硬件段: IO-MMU 处理的 物理地址->硬件地址的映射进行的合并产生的内存区

基本数据结构:

linux/include/linux/blk_types.h
/*
 * main unit of I/O for the block layer and lower layers (ie drivers and
 * stacking drivers)
 */
struct bio {   // 一个 bio 有多个链表组成, 所以经常 bio_for_each_segment
	struct bio		*bi_next;	/* request queue link */ // 一个请求中会合并相邻的bio, 所以是链表
	bio_end_io_t		*bi_end_io;
	struct bio_vec		*bi_io_vec;	/* the actual vec list */ // 存放数据的页列表
	struct bio_set		*bi_pool; 
	....
};

// linux/inlucde/linux/bvec.h
struct bio_vec {
	struct page	*bv_page;
	unsigned int	bv_len;
	unsigned int	bv_offset;
};

// linux/include/linux/blkdev.h
struct request {  
	// 一个request初始化的时候只有一个bio, 但是IO调度的时候 会将多个bio合并, 或者bio关联新的段
	// blk 的请求描述符, device 处理的基本单位
	// 不懂: 有一个 nr_requests, 又有一个 queue_depth
	struct request_queue *q;
	struct blk_mq_ctx *mq_ctx;
	struct blk_mq_hw_ctx *mq_hctx;

	int tag;
	int internal_tag;
	struct bio *bio;
	struct list_head queuelist; // 这个的用处 ? 
	.... // 省略部分字段
};

struct request_queue {  // 需要找下部分字段的意义
	struct elevator_queue	*elevator;
	const struct blk_mq_ops	*mq_ops;  // device自定义的处理函数

	/* sw queues */
	struct blk_mq_ctx __percpu	*queue_ctx;

	unsigned int		queue_depth;

	/* hw dispatch queues */
	struct blk_mq_hw_ctx	**queue_hw_ctx; // 每个device可以有多个 blk_mq_hw_ctx, 绑定相应的 queue 回调等函数, nbd 只有一个
	unsigned int		nr_hw_queues;
	
	unsigned long		nr_requests;	/* Max # of requests */

	struct list_head	requeue_list;  // 深入理解linux内核 有描述, 但是对不上, 这里应该是 重新投递的队列, 参考 `blk_mq_requeue_work`
	struct blk_mq_tag_set	*tag_set;
	struct list_head	tag_set_list;
	...
}

enum hctx_type {  // hctx类型, 用于 request_queue->blk_mq_tag_set
	HCTX_TYPE_DEFAULT,
	HCTX_TYPE_READ,
	HCTX_TYPE_POLL,

	HCTX_MAX_TYPES,
};

// bk-mq-tag.c
struct blk_mq_tag_set {   // ctx->hctx 映射, 同时进行限流
	struct blk_mq_queue_map	map[HCTX_MAX_TYPES]; // 映射表
	unsigned int		nr_maps;        // nbd 1 
	const struct blk_mq_ops	*ops;
	unsigned int		nr_hw_queues;   // nbd 1
	unsigned int		queue_depth;    // nbd 128? 用处? 
	unsigned int		reserved_tags;  // nbd 0 
	unsigned int		cmd_size;
	int			numa_node;
	unsigned int		timeout;
	unsigned int		flags;  // nbd BLK_MQ_F_SHOULD_MERGE | BLK_MQ_F_BLOCKING;
	void			*driver_data;

	struct blk_mq_tags	**tags; // 硬件队列个数/nr_hw_queues的 *blk_mq_tags, 

	struct mutex		tag_list_lock;
	struct list_head	tag_list;
};

// blk-mq.h
// Map software queues to hardware queues, 目前映射方式是 round-robin, 因为 software queue 是每个 cpu 映射的, 因此直接 cpu round-robin 就行了
struct blk_mq_queue_map {
	unsigned int *mq_map;   // cpu/soft queue -> hw_queue
	unsigned int nr_queues;  // nbd 为1, set->nr_hw_queues
	unsigned int queue_offset; // 第一个cpu映射的地址, round-robin 是从这个地址开始的. 相当于随机起始地址. 因为 set 的 tags 取的是 第一个硬件对应的cpu的node. 相当于随机化了
};


// blk-mq-tags.h
// Tag address space map.
struct blk_mq_tags { 
	unsigned int nr_tags;      // set->queue_depth
	unsigned int nr_reserved_tags; // set->reserved_tags

	atomic_t active_queues;

	struct sbitmap_queue bitmap_tags;  // round-robin 分配 nr_tags, sbitmap_queue_init_node.调用 sbitmap_queue_init_node, 不懂了 参数 bt, depth=128, -1, round_robin, GFP_KERNEL, node 
	struct sbitmap_queue breserved_tags;

	struct request **rqs;            // nr_tags 数量, 没太看懂
	struct request **static_rqs;	 // nr_tags 数量, 分配在页上
	struct list_head page_list;      // 存放request的地方
};


// blk-mq.h
// struct blk_mq_hw_ctx - State for a hardware queue facing the hardware block device
struct blk_mq_hw_ctx { 
	struct {
		/** @lock: Protects the dispatch list. */
		spinlock_t		lock;
		/**
		 * @dispatch: Used for requests that are ready to be
		 * dispatched to the hardware but for some reason (e.g. lack of
		 * resources) could not be sent to the hardware. As soon as the
		 * driver can send new requests, requests at this list will
		 * be sent first for a fairer dispatch.
		 */
		struct list_head	dispatch;  // 有 bypass 的调度场景
		....
	} ____cacheline_aligned_in_smp;
	/**
	 * @ctx_map: Bitmap for each software queue. If bit is on, there is a
	 * pending request in that software queue.
	 */
	struct sbitmap		ctx_map;    
	/** @nr_ctx: Number of software queues. */
	unsigned short		nr_ctx;
	/** @ctxs: Array of software queues. */
	struct blk_mq_ctx	**ctxs;     // 没有IO Scheduler的场景, 会遍历每一个ctx进行dispatch
	/**
	 * @tags: Tags owned by the block driver. A tag at this set is only
	 * assigned when a request is dispatched from a hardware queue.
	 */
	struct blk_mq_tags	*tags; // set->tags[hctx_idx]
	/**
	 * @sched_tags: Tags owned by I/O scheduler. If there is an I/O
	 * scheduler associated with a request queue, a tag is assigned when
	 * that request is allocated. Else, this member is not used.
	 */
	struct blk_mq_tags	*sched_tags; // 
	...
}

struct blk_mq_ctxs {
	struct kobject kobj;
	struct blk_mq_ctx __percpu	*queue_ctx;
};

// blk-mq.h
/**
 * struct blk_mq_ctx - State for a software queue facing the submitting CPUs
 */
struct blk_mq_ctx {
	struct {
		spinlock_t		lock;
		struct list_head	rq_lists[HCTX_MAX_TYPES];   // 没有调度器, 则存储request
	} ____cacheline_aligned_in_smp;

	unsigned int		cpu;
	unsigned short		index_hw[HCTX_MAX_TYPES];
	struct blk_mq_hw_ctx 	*hctxs[HCTX_MAX_TYPES];

	struct blk_mq_ctxs      *ctxs;
} ____cacheline_aligned_in_smp;

ps: 深入理解linux内核 对 plug 的描述已经过时了, 没发现blk_plug_device 和 blk_unplug_device. 另外, device层(比如nbd.c)调用的 blk_mq_init_queue 是很多函数启动和自定义的地方.

注意, request_queue 提到了 sw queues(struct blk_mq_ctx __percpu *queue_ctx) 和 hw dispatch queue(struct blk_mq_hw_ctx **queue_hw_ctx), 其中, hw dispatch queue 维护了 request 资源(分配/限流)、回调入队任务(分发到device)、超时任务 等.

软件队列(soft_queue) blk_mq_ctx 是每个cpu的, 可以利用 blk_mq_ctx 提升并发度, 单个cpu内的操作尽可能闭环, 比如: __blk_mq_complete_request/__blk_mq_insert_req_list, 除此之外, 没有调度器的场景下, 会将请求插入到 blk_mq_ctx->rq_lists. 比如调用路径:

blk_mq_sched_insert_requests -> blk_mq_insert_requests -> ... -> `__blk_mq_run_hw_queue`->blk_mq_sched_dispatch_requests(既支持从 调度器进行flush, 也支持从 soft queue flush) -> blk_mq_flush_busy_ctxs

blk_mq_sched_insert_request 可能 `__blk_mq_insert_request` 插入到 soft queue

主流程

当需要发起块设备读写请求时，kernel 首先根据需求构造 bio 结构（毕竟是 I/O 请求单位哦），其中包含了读写的地址、长度、设备、回调函数等信息，然后 kernel 通过 submit_bio 函数将请求转发给块设备

入口函数位于 blk-core.c: submit_bio -> generic_make_request -> make_request -> 调用提前注册好的 blk_mq_make_request(blk-mq.c).

先梳理一下流程:

第一步: 1. 将 bio 转换为 request 第二步: 投递到 plug 进行蓄洪, 主要是排序, 短时间内的操作都是一个设备的, 通过上层接口使用(个数 > 16, 或者当前请求大小超过 128k) 第三步: 投递到 elevator scheduler, 有多种实现, 比如 kyber, 将不同类型的请求聚合批次 第四步: 延迟任务 从 elevator scheudler 中获取请求 并分发给 device 的 requeue接口, 下游 device处理完成后, 会调用 blk 的处理函数

当然也存在快速路径, 加快分发, 比如 token 不够了的场景, 就会同步第四步提前flush 来释放token.

io转换

bio 实例化为 request(因为request是提前实例化好的, 所以应该是抢占一个): blk_mq_get_request data->ctx = blk_mq_get_ctx(q); // 获取当前cpu的 soft queue/blk_mq_ctx data->hctx = blk_mq_map_queue(…) // 获取相应类型的 hw queue/blk_mq_hw_ctx tag = blk_mq_get_tag(data); // 获取响应的tags, 有调度器走 hctx->sched_tags, 否则 hctx->tags; 没有可用的tag则 就立即触发同步的 blk_mq_run_hw_queue, 释放一些. io_schedule 不懂. blk_mq_rq_ctx_init // 从 static_tag 获取 request(tag是递增的), data信息 大量赋值给 rq,

可以发现, reqeust 是从 hctx 分配的.

plug [从 blk_mq_make_request 看/blk-mq.c]

上层负责实例化 plug, 比如 ext4调用的, blk_start_plug/blk_finish_plug 是一对控制组, 一个负责实例化, 一个负责销毁, 也就是说: 那么每个控制就有一个 mq_list. 实例化后的plug 存放在 task_struct内部, 常用变量名: current.

主要使用的两个函数: blk_add_rq_to_plug 和 blk_flush_plug_list(ps: 实现从 blk-mq.c -> blk-core.c -> blk-mq.c … 跳来跳去有些乱)

这个流程:

添加到 plug->mq_list -> 排序后, 将 相同 mq_ctx 和  mq_hctx 放在一起调用(不相同的分开来调用) -> blk_mq_sched_insert_requests(就是上面的调度层)

plug中的排序是 mq_ctx -> mq_hctx -> blk_rq_pos. 奇怪, 为什么要比较 mq_ctx? 需要理一理

IO-scheduler [从 blk_mq_make_request 看/blk-mq.c]

在实现内部, 是支持不走 scheduler 和 走scheduler 两种模型的.

1. 无scheduler, 通过调用 blk_mq_sched_dispatch_requests, 将 request 插入到 hctx->dispatch, 最终被硬件队列 flush
2. 有scheduler, 内部实现有很多(mq的IO调度器: mq-deadline/bfq/kyber. code: mq-deadline.c/bfq-iosched.c/kyber-iosched.c),

kyber

以 kyber 为例子:

	blk_mq_make_request[blk-mq.c] -> blk_mq_sched_insert_request[blk-mq-sched.c] -> insert_requests[注册sheduler的函数] kyber添加到 hctx->sched_data(常用变量名khd, 实际类型kyber_hctx_data)->kcqs[x](kyber_ctx_queue)->rq_list -> .....异步的hw dispatch work -> [注册scheduler的dispatch函数] 将 kyber domain的 kyber_hctx_data->kcqs[x](kyber_ctx_queue)->rq_list 迁移到 hctx->sched_data(kyber_hctx_data)->rqs[x], 再根据调用一个个返回 -> device#queue_rq

需要注意的是, 插入是存放在 hctx->sched_data->kcqs[x]->rq_list, 但是 device分发的时候, 存在一次迁移操作, 是获取 hctx->sched_data->rqs 的请求. 这样及时释放 kcqs 的空间, 加快了处理?

ps: kcqs(hctx->sched_data->kcqs) 这个为什么和 分发队列 hctx->sched_data->rqs 分开来设计呢 ? 是因为更快?

mq-deadline

deadline-iosched.rst

看样子, 请求会先聚合成batch, 按照 batch的deadline 进行排队, 是 低延迟和吞吐量 之间的取舍, 参看参数 fifo_batch(默认是16). 因为整体上偏向read, 为了避免 write stravation, 支持了 writes_starved 参数(默认是2), 当read多少次, 就会进行写

bfq

注释很全,

各种队列总结

这里面涉及到多个内部的队列, 因为本质上都是 list 链表操作, 性能还是能够保证的. 比如: plug 内部有 mq_list(投递到mq_list, flush的时候排个序再进入第四步), kyber 针对不同类型的实例化相应的 kyber_hctx_data->kcqs[type]->rq_list, scheduler 被回调要flush的时候, 又会将 kyber_hctx_data->kcqs[type]->rq_list 迁移到 kyer_hctx_data->rqs, 然后由 rqs 不断返回request 给 device dispatch

除了流程中的队列的概念, 还有 soft_queue 和 hardware_queue 的概念, ……

存在特殊的 hctx->dispatch, 这个在 无scheduler的场景下, 调用 blk_mq_request_bypass_insert 就是直接插入到 hctx->dispatch, 而且是异步flush的. 看注释的情况下, IO request 会被插入到 scheduler queue/sw queue/dispatch queue.

补充重新投递: nbd 底层在发送socket失败的时候, 就会重新投递: nbd_requeue_cmd->blk_mq_requeue_request->blk_mq_sched_requeue_request(kyber scheduler 就是归还token)+blk_mq_add_to_requeue_list(添加到queue->reque_list), 最终被 queue->requeuw_work/blk_mq_requeue_work 调度 (根据情况是直接bypass还是insert scheduler)

有意识的一点, requeue 和 timeout 是queue级别的(blk_mq_init_allocated_queue), 但是 blk_mq_run_work_fn 是 hctx 级别的(blk_mq_alloc_hctx)

device 自定义

不同的device需要定义不同的处理函数, 完整的定义在 blk_mq_ops[blk-mq.h]. 这里以 nbd为例子, 看几个重要的函数.

init_request

比较特殊, request 是提前注册好的, 所以这个 回调函数 并不是 每个bio进来后 进行实例化.

调用路径: 有多条, 从 nbd的角度来看, 主要是: err = blk_mq_alloc_tag_set(&nbd->tag_set); 和 q = blk_mq_init_queue(&nbd->tag_set);, 奇怪了为什么要两次呢?

device实现调用 -> blk_mq_alloc_tag_set -> blk_mq_alloc_rq_maps -> __blk_mq_alloc_rq_maps -> __blk_mq_alloc_rq_map -> blk_mq_alloc_rqs -> blk_mq_init_request // 负责回调 


device实现调用 -> blk_mq_init_queue->blk_mq_init_queue_data->blk_mq_init_allocated_queue->blk_mq_realloc_hw_ctxs->blk_mq_alloc_and_init_hctx->blk_mq_init_hctx -> blk_mq_init_request // 负责回调 init_request

其实在 elevator scheduler的实现中, 也会调用

elevator_switch_mq/(blk_mq_init_allocated_queue->elevator_init_mq) -> blk_mq_init_sched -> blk_mq_sched_alloc_tags -> blk_mq_alloc_rqs

看 blk_mq_alloc_rqs 的实现, 每个request是分配在 page 上的, 一个page有多个request // 注意是 tags->static_rqs[i] 也是引用了 每个request. tags的实现越来越奇怪了.

queue 入队回调

这个触发的场景也非常多, 通常以 queue实例化过程中 启动的延迟任务为准:

device调用 -> blk_mq_init_queue -> blk_mq_init_queue_data -> blk_mq_realloc_hw_ctxs -> blk_mq_alloc_and_init_hctx -> blk_mq_alloc_hctx -> blk_mq_run_work_fn(初始化了延迟任务) -> `__blk_mq_run_hw_queue` -> blk_mq_sched_dispatch_requests -> blk_mq_dispatch_rq_list // 会调用 q->mq_ops->queue_rq(hctx, &bd); 

主要看下blk_mq_alloc_hctx实现, 每个 hctx 一个任务 入队任务, 用来分发 hctx 的内容. 除此之外, blk_mq_alloc_hctx 还会为每个 hctx 配置一个wait触发器: blk_mq_dispatch_wake, 会调用 blk_mq_run_hw_queue.

但是也是支持直接调用的, 比如初始化request的时候, 如果tag不够了, 就会触发 blk_mq_run_hw_queue(层层调用到blk_mq_dispatch_rq_list) (参看 blk_mq_get_tag[blk-mq-tag.c]), 提前dispatch 释放一些资源.

从入队的 request 的来源来看, 分别来自于 IO scheduler(blk_mq_do_dispatch_sched)、soft queue(blk_mq_do_dispatch_ctx[hctx->dispatch_busy, 一个个投递]/blk_mq_flush_busy_ctxs[攒成rq_list发送]).

IO complete

这个比较有意识了, io 完成的行为是 device 触发的, 比如 nbd 在 异步recv_work 收到了响应 或者 超时的时候, 会通过 blk_mq_complete_request 触发, 但是最终又回调了注册 device complete 函数 (因为执行device的cpu 和 执行 completion的cpu 可能不是一个)

blk_mq_complete_request->__blk_complete_request/blk_done_softirq(blk-softirq.c)/__blk_mq_complete_request/__blk_mq_complete_request_remote非本cpu的complete处理 // 会调用 q->mq_ops->complete(rq);

除此之外, mq_ops->complete 可能是 软中断触发的, 参考函数 blk_done_softirq(blk-softirq.c) 和 __blk_complete_request(blk-softirq.c) 以及初始化 blk_softirq_init, 是 __blk_mq_complete_request 在 单队列控制器的场景下触发

timeout

blk_mq_init_allocated_queue 会启动任务 blk_mq_timeout_work -> blk_mq_check_expired -> blk_mq_rq_timed_out // 会回调超时 mq_ops->timeout, 如果自定义函数不是 DONE, 则继续添加到 timer. 比如重试语义不一致.

超时的启动是在 device层的, 比如 nbd->nbd_handle_cmd(blk_mq_start_request)

问题排查工具

blktrace , ftrace iotop, iostat

问题

1. soft_queue 和 hardware_queue 有什么作用?

hw_queue 维护了 request 资源和流控、io scheduler 以及 绑定的 timeout worker、queue worker. 一个硬件可以多个 hw_queue(rr 的方式将 hw_queue 分担到 cpu).

很多概念扫盲: https://my.oschina.net/u/2475751/blog/1615220

hctx 在 hctx->queue->nr_hw_queues == 1 是 WORK_CPU_UNBOUND的

软件队列(soft_queue) blk_mq_ctx 是每个cpu的, 可以利用 blk_mq_ctx 提升并发度, 单个cpu内的操作尽可能闭环, 比如: __blk_mq_complete_request/__blk_mq_insert_req_list, 除此之外, 没有调度器的场景下, 会将请求插入到 blk_mq_ctx->rq_lists.

因此队列应该分两种, soft_queue -> hw_queue, 和 io_scheduler_queue -> hw_queue. 这里没有算 plug queue.

2. hctx->dispatch 用处

3. blk_mq_tags、blk_mq_tag_set 怎么理解

目前看下来仅仅是 维护request资源. 将不同 hw_type 和 hw_queue 分开来

特殊的设计

sbitmap

参考

• buget faire scheduler: https://lwn.net/Articles/601799/ https://lwn.net/Articles/709202/
• kyber scheduler: https://lwn.net/Articles/720675/
• biodoc.rst
• Multi-queue 架构分析
• Linux Block IO: Introducing Multi-queue SSD Access on Multi-core Systems
• linux mq pr: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=320ae51feed5c2f13664aa05a76bec198967e04d
• 别人的 block 学习: https://zohead.com/archives/linux-kernel-learning-block-layer/
• 别人的 block 学习: http://kernel.pursuitofcloud.org/710227
• 别人整理的各个文件的作用: https://blog.csdn.net/ljy1988123/article/details/48978591
• Linux Block IO: Introducing Multi-queue SSD Access on Multi-core Systems
• High Performance Storage with blk-mq and scsi-mq

///============================tldr

细节:

IO scheduler queue

submit_bio(block-core.c)-> generic_make_request(为什么遍历? 得细看) -> [之前设置的]blk_mq_make_request(将bio转换为request提交给device) blk_queue_bounce: ? q->limits.bounce_pfn 这个设计是为啥 ? __blk_queue_split: 将大的 bio 进行切分 blk_mq_sched_bio_merge // ? rq_qos_throttle

这里讨论 blk_mq_make_request 的几种调度策略:

1. bypass scheduler: 上面讨论了, 不赘述. 直接回调 device 的 queue_rq
2. plug (HDD的时候使用, read场景可能触发, 触发条件再理理), flush 触发机制: 个数 > 16, 或者当前请求大小超过 128k. blk_flush_plug_list->blk_mq_sched_insert_requests // 满了要flush的机制, 排序后会分 mq_hctx、mq_ctx 投递到 sched blk_mq_sched_insert_requests 调度细节: 1. e->type->ops.insert_requests(hctx, list, false); //
   2.1 blk_mq_try_issue_list_directly // 回调 q->mq_ops->queue_rq 2.2 blk_mq_insert_requests // 细节看看, 没看到 hwctx. ctx 和 hwctx 怎么关联? blk_mq_run_hw_queue
   blk_add_rq_to_plug // 进行 plug 的机制, 添加到头部 // 上层调用 blk_start_plug[block-core.c], 将plug 放到 task_struct, device 无感知, 上层比如ext4调用的. current 机制就是 当前的 task_struct. 不明白的地方? plug multiple_queues 设计? 这里有个问题, 是多 soft mq 吗? (多队列或者>2, 会排序)

struct blk_plug {
	struct list_head mq_list; /* blk-mq requests */
	struct list_head cb_list; /* md requires an unplug callback */
	unsigned short rq_count;
	bool multiple_queues; // mq_list 的 request 是否都是一个 queue的, 这个标记的用处是? 
};

3. scheduler:

/*
 * each queue has an elevator_queue associated with it
 */
struct elevator_queue
{
	struct elevator_type *type;
	void *elevator_data;
	struct kobject kobj;
	struct mutex sysfs_lock;
	unsigned int registered:1;
	DECLARE_HASHTABLE(hash, ELV_HASH_BITS);
};
/*
 * identifies an elevator type, such as AS or deadline
 */
struct elevator_type
{
	/* managed by elevator core */
	struct kmem_cache *icq_cache;

	/* fields provided by elevator implementation */
	struct elevator_mq_ops ops;  // 各种函数的集合
 
	size_t icq_size;	/* see iocontext.h */
	size_t icq_align;	/* ditto */
	struct elv_fs_entry *elevator_attrs;
	const char *elevator_name;
	const char *elevator_alias;
	const unsigned int elevator_features;
	struct module *elevator_owner;
#ifdef CONFIG_BLK_DEBUG_FS
	const struct blk_mq_debugfs_attr *queue_debugfs_attrs;
	const struct blk_mq_debugfs_attr *hctx_debugfs_attrs;
#endif

	/* managed by elevator core */
	char icq_cache_name[ELV_NAME_MAX + 6];	/* elvname + "_io_cq" */
	struct list_head list;
};

首先确定只有 evelator 算法. 具体实现: bfq-iosched.c/kyber-iosched.c/mq-deadline.c

这里主要看下: kyber-iosched.c

// 设计思路: 根据请求类型分成多个 domain, 分别有不同的 depth、latency、batch_szie.
通过 kyber_sched 注册自己的处理行为

kyber_init_sched
kyber_init_hctx
kyber_bio_merge
kyber_prepare_request  // flush 请求会触发
kyber_insert_requests
kyber_dispatch_request
....

// 实现里面有个计算百分比的公式可以学习下 kyber_insert_requests:
就是放到指定的列表: rq_list中 kyber_init_sched: // 分配数据结构 kyber_init_hctx: kyber_bio_merge // ? blk_mq_make_request -> blk_mq_sched_bio_merge -> __blk_mq_sched_bio_merge// 调用 scheduler 的merge: 将新提交的bio进行merge到已有的queue的rq中, 具体实现参考 blk-merge.c, 有很多细节, 读写类型相同的、同一个设备的 … 并且前后sector相连的 才可以合并, bio 会放到 request 中.

但是什么时候提交呢? kyber_domain_wake -> blk_mq_run_hw_queue, 还是异步的 (最终实现就是/但是延迟服务会调用[不是kyber_domain_wake的主要作用] blk_mq_sched_dispatch_requests(blk-mq-sched.c), 会将之前的 hctx->dispatch 分发掉, 以及 如果scheduler 有分发, blk_mq_do_dispatch_sched, 没有schedule, 则 blk_mq_do_dispatch_ctx/blk_mq_flush_busy_ctxs) blk_mq_do_dispatch_sched(blk-mq-sched.c): // 遍历flush 到 device e->type->ops.dispatch_request -> kyber_dispatch_request -> kyber_dispatch_cur_domain // 获取指定domain的 request 队列, 每个循环内获取的是一个domain的request队列 blk_mq_dispatch_rq_list // 进行分发

kyber_domain_wake 是在 kyber_init_hctx 针对每个 domain 进行初始化的, token唤醒后？进行触发 wait

static int kyber_init_hctx(struct blk_mq_hw_ctx *hctx, unsigned int hctx_idx){
	...
	init_waitqueue_func_entry(&khd->domain_wait[i].wait,
					  kyber_domain_wake);
	...
}
static int kyber_domain_wake(...) {
	sbitmap_del_wait_queue(wait);
}

kyber_finish_request ？

token的概念: kyber_get_domain_token: nr = __sbitmap_queue_get(domain_tokens); // -> sbitmap_get(sbitmap.c) sbitmap_add_wait_queue(domain_tokens, ws, wait); sbitmap_del_wait_queue(wait);

struct kyber_queue_data {
	struct request_queue *q;
	struct sbitmap_queue domain_tokens[KYBER_NUM_DOMAINS];
	... // domain_wait
}

todo: 学习下 sbitmap.c(等待空闲bits的bitmap) wait.h(队列模型) 整体的在 kyber 中的唤醒流程: kyber_finish_request->rq_clear_domain_token(kyber-iosched.c)->sbitmap_queue_clear/sbitmap_queue_wake_all/sbitmap_queue_update_wake_batch->sbitmap_queue_wake_up(sbitmap.c)->__sbq_wake_up->wake_up_nr(wait.h)->__wake_up(wait.c)->__wake_up_common_lock

那么 kyber_finished_request 什么时候调用呢? 看注册关系, 主要是 finished_request/requeue_request

blk_mq_check_expired/__blk_mq_end_request->blk_mq_free_request(blk-mq.c)->finish_request

blk_mq_dispatch_rq_list/blk_mq_try_issue_directly/blk_mq_try_issue_list_directly -> blk_mq_end_request -> __blk_mq_end_request

blk_mq_init_allocated_queue 启动worker调度 -> blk_mq_timeout_work -> blk_mq_check_expired

具体的mq调用->blk_mq_requeue_request(blk-mq.c)->blk_mq_sched_requeue_request(blk-mq-sched.h)->requeue_request

奇怪了, request -> plug -> scheduler -> dispatch hw to device 但是 kyber 的 scheduler 调度依赖 wait, 但是触发 wait 就需要 dispatch hw 或者 timeout, 感觉死循环了? 因为 dispatch hw 是异步的, 所以还好. 但是 request 完成之后, 为什么还需要又 kyber_domain_wake

// request->queuelist 用来做什么呢?

每个 hw queue 都有一个elevator_queue.

hctx->queue->elevator

blk_mq_make_request -> blk_mq_sched_insert_request

blk_mq_make_request 支持直接投递到 hw_queue, 不进行IO调度

// mq.h blk_mq_plug的注释 plug的设计: 延迟将bio插入到 evelator 来提升 BIO merging 的机会; 怎么实现的呢? (有些翻译称呼为 蓄洪, 比如: https://blog.csdn.net/g382112762/article/details/53221272), 读场景会触发 submit_io -> generic_make_request -> make_request -> bio_queue_io -> list_add_tail ? blk_start_plug ?

elevator: blk_mq_init_queue 的时候并不会实例化 evelator, add_disk 的时候才会调用 (比如 nbd)

nomerge:

tag

从实现上看, 就是对 request 资源的管理, 从上面可以知道, request 是预分配好的(blk_mq_tags->static_rqs 已经在page上分配了), 每个 硬件队列 hctx 有一个 blk_mq_tags, 通过 blk_mq_tags->bitmap-tags 进行资源控制, 每一个资源就是一个 tag, 本质上就是 blk_mq_tags->static_rqs 的一个索引.

sbitmap

这个看提交记录应该是2016年才提交的代码部分. 常规的bitmap 在 bitmap.h(include/linux/bitmap/h) 以及 bitmao.c(lib/bitmap), 架构相关的函数实现在 include/asm-<arch>/bitops.h, sbitmap 的实现 考虑到了 伪共享的问题, 相比于 bitmap的常规定义:

#define DECLARE_BITMAP(name,bits) \
	unsigned long name[BITS_TO_LONGS(bits)]

sbitmap 的设计成了 sbitmap 和 sbitmap_word 两个数据结构, sbitmap不直接维护long, 而是依靠 sbitmao_word, 其中, sbitmap_word 中要操作的 long 型字段(word/cleared) 以及自己 都标记成了 ____cacheline_aligned_in_smp(64位系统上64对齐), 实现L1缓存分离.

和bitmap类似, sbitmap 用 sbitmap_word 替换了 bitmap 中的 long, 因此, 操作bit 需要先定位到 sbitmap_word, 在定位到 sbitmap_word 中的long的bit. 比较有意识的是, sbitmap_word 的bit clear不是立即生效的, 而是存储在 sbitmap_word->cleared 字段上, 并且和 sitmap_word->word 字段分离, 这样, 多个cpu在 获取、重置 同一个 word 的bit 可以避免伪共享, 但是随之而来的成本就是, 如果 sbitmap_word 中的bit被用光了, 就需要一次置换操作, 这个时候需要加锁: sbitmap_word->swap_lock.

除此之外, 还在sbitmap的基础上扩展了 sbitmap_queue 的实现, 增加了 wait 的语意. 放在 sbitmap_queue->sbq_wait_state.

相比于常规的锁实现, sbitmap 将资源的数量 分散到了 多个L1 不共享的 bitmap_word, 降低了 ping-pong 的性能损耗; 当资源耗尽, 那么都是常规的 wait, 这个场景下性能应该是一致的 (sbitmap_queue 应该存在遍历的开销?).

• 主要的数据结构 sbitmap_queue->ws: 是一个 sbq_wait_state 数组

struct sbitmap_word {
	/**
	 * @depth: Number of bits being used in @word/@cleared
	 */
	unsigned long depth;     // 可以使用的bit

	/**
	 * @word: word holding free bits
	 */
	unsigned long word ____cacheline_aligned_in_smp; // 64bit 

	/**
	 * @cleared: word holding cleared bits
	 */
	unsigned long cleared ____cacheline_aligned_in_smp; // 释放的时候放到 cleared 

	/**
	 * @swap_lock: Held while swapping word <-> cleared
	 */
	spinlock_t swap_lock; // 当 word 满的时候, 需要加锁 swap_lock, 用来 clear 交换到 word, 并置为0. 可以通过 sb->map[i].word & ~sb->map[i].cleared 判断是否bit使用了
} ____cacheline_aligned_in_smp;

/**
 * struct sbitmap - Scalable bitmap.
 *
 * A &struct sbitmap is spread over multiple cachelines to avoid ping-pong. This
 * trades off higher memory usage for better scalability.
 */
struct sbitmap {
	/**
	 * @depth: Number of bits used in the whole bitmap.
	 */
	unsigned int depth;  // 总计可以使用的bit, word的depth 加起来就是 这个值

	/**
	 * @shift: log2(number of bits used per word)
	 */
	unsigned int shift; // 可以对 bits 进行shift 实现查找 map 的index, 也可以查找 word内的bit

	/**
	 * @map_nr: Number of words (cachelines) being used for the bitmap.
	 */
	unsigned int map_nr; // word 数量

	/**
	 * @map: Allocated bitmap.
	 */
	struct sbitmap_word *map; // sbitmap_word 数组
};

/**
 * struct sbitmap_queue - Scalable bitmap with the added ability to wait on free
 * bits.
 *
 * A &struct sbitmap_queue uses multiple wait queues and rolling wakeups to
 * avoid contention on the wait queue spinlock. This ensures that we don't hit a
 * scalability wall when we run out of free bits and have to start putting tasks
 * to sleep.
 */
struct sbitmap_queue {
	struct sbitmap sb;
	unsigned int __percpu *alloc_hint;  // 是 cpu 级别的,  [0, queueu->depth), 记录上次成功分配的空闲bit
	unsigned int wake_batch; // 唤醒waiter之前必须被释放的bit数量 (初始化是queue大小)
	struct sbq_wait_state *ws; // 等待队列的数组, 看 sbitmap_queue_init_node 实现应该就8个. 每次排队都会自增
	atomic_t wake_index;  	 // 下一个要被唤醒ws的索引
	atomic_t ws_active;		 // 当前活跃的等待队列数量
	bool round_robin;        // 按照 rount-robin 方式分配
	unsigned int min_shallow_depth;  // ?
}

struct sbq_wait_state {
	atomic_t wait_cnt;  // 唤醒前需要保证空闲的数量, 不懂作用了. value是 wake_batch
	wait_queue_head_t wait; // 等待的元素
} ____cacheline_aligned_in_smp;

struct sbq_wait {
	struct sbitmap_queue *sbq;	/* if set, sbq_wait is accounted */
	struct wait_queue_entry wait;
};

#define BIT_MASK(nr)		(UL(1) << ((nr) % BITS_PER_LONG))
#define BIT_WORD(nr)		((nr) / BITS_PER_LONG)
#define BITS_PER_LONG 64  // 64位系统
#define SBQ_WAIT_QUEUES 8
#define SBQ_WAKE_BATCH 8

• 主要的函数功能记录:

sbitmap_queue_init_node
	sbitmap_init_node: 
		一个word若干bit(bit数量少, 算下来是少于 256, 那么会保证至少 4个word. 算法如下: 找到 4U << shift) <= depth 的shift的最大值, 相当于减少 shift 的值), word数量 (depth / bits 的上界), word->depth 一般为 min(depth, bits_per_word);
	假设 128, 那么 shift 为5, words 数量为4, 每个 word->depth=32, 也就是说 每个word的可用bit是 32. wake_batch=8, 
	因为兼容了 非 2的指数的场景, 所以代码有些复杂. 

sbitmap_deferred_clear_bit: 延迟清除, 放到 bitmap
sbitmap_queue_clear: ->sbitmap_deferred_clear_bit(设置清空标志), 并唤醒: sbitmap_queue_wake_up
(blk场景里, `__blk_mq_free_request`->blk_mq_put_tag, rq_clear_domain_token, )

sbq_wake_ptr: 获取 sbitmap_queue->ws(sbq_wait_state数组) 中有等待的sbq_wait_state, 并自增等待索引
sbitmap_free: 
sbitmap_get:  // 遍历 word, 获取word下一个非零bit 并set. 返回的是总的 number
sbitmap_queue_init_node
`__sbitmap_queue_get`:  // 调用 sbitmap_get, 看情况会更新 alloc_hint

sbitmap_queue_wake_all: 循环唤醒 sbitmap_queue->ws(数组)/sbq_wait_state -> wake_up(&ws->wait);

sbitmap_queue_wake_up: sbq_wake_ptr, ws->wait_cnt 减1, 如果跌0, 则唤醒一个batch -> wake_up_nr(&ws->wait, wake_batch);

sbitmap_prepare_to_wait: 将 sbq_wait->wait_queue_entry 挂载到 sbitmap_queue->sbq_wait_state 后面, 会
							设置线程状态
sbitmap_finish_wait: 从 sbitmap_queue->sbq_wait_state 删除 sbq_wait->wait_queue_entry, 并恢复线程状态
sbitmap_add_wait_queue: 和prepare类似, 除了不设置状态 
sbitmap_del_wait_queue: 和finish类似, 除了不设置状态

• commits 看上去代码大部分是2016年完成的, 所以网上基本没资料, 主要的一些提交记录:

	f4a644db86669 (Omar Sandoval     2016-09-17 01:28:24
	88459642cba45 (Omar Sandoval 	 2016-09-17 08:38:44
	c05e667337881 (Omar Sandoval     2017-04-14 00:59:58
	7930d0a00ff5d (Ming Lei          2017-10-14 17:22:27
	4ace53f1ed40a (Omar Sandoval     2018-02-27 16:56:43
	14b470b56840d (Arnd Bergmann 	 2018-07-06 22:19:07
	5d2ee7122c73b (Jens Axboe        2018-11-29 17:36:41
	ea86ea2cdced2 (Jens Axboe    	 2018-11-30 13:18:06

• 问答:

为什么要设计一个这个: sbq_wait? 用来给外层routine 维护一个wait_entry 实现复用, 以及检测是否存在等待的情况, 比如 kyber-iosched.c

• usage

看上去每个硬件队列一个 wait_index, 那么 sbitmap_queue 有多个 hw ?

kyber-iosched.c 中使用 sbitmap_queue 进行资源的管理, 避免下游磁盘处理太慢, 实现对上游request的depth限流

kyber_finish_request rq_clear_domain_token rq_get_domain_token: 获取request记录的bit nr. sbitmap_queue_clear(): 标记bit nr cleared, 并将nr记录到 cpu的 alloc_hint. 尝试唤醒(当存在等待的时候, 设计了批量唤醒的机制, 没有释放 batch 数量的bit, 则什么也不做, 只是减少计数)

kyber_dispatch_cur_domain kyber_get_domain_token __sbitmap_queue_get // 遍历word, 获取一个空闲的bit sbitmap_add_wait_queue(domain_tokens, ws, wait); // 添加到等待队列 rq_set_domain_token: 将bit nr 设置到 rq->elv.priv[0]

参考书籍

深入理解 linux 内核 内核利用通用块层(general block layer)启动IO操作来传递所请求的数据, 因为每次IO操作在磁盘上的块不一定连续, 所以需要启动多次IO操作

问题

dispatch_wait 的触发逻辑不懂 softirq 复习下 struct kobject * mq_kobj; 付下下 sbitmap 是 slab 分配的map, 奇怪了, 为什么要node 呢?
bounce 的设计点 ?

补充学习

front merge & backend merge: https://zhuanlan.zhihu.com/p/40742877