北京英本科技有限公司 www.ingben.com
1 / 19
读者须知：此文档为英本网(http://www.ingben.com/)原创，版权归英本网所
有。谨以此奉献给 linux爱好者，研究者，英本学员等。技术讨论 QQ群：67962133
我们知道，每个块设备程序都有一个请求队列与之关联。在块设备初始化时，会分配并
初始化请求队列。在这个时候，我们便可以为块设备驱动程序指定特定的 IO调度算法，默
认情况下是强制使用系统默认的调度算法。
注意：每一个磁盘设备都有一个队列 equest_queue，每个队列中都有一个 struct
elevator_queue 用来表示这个磁盘设备将会用到的是什么调度算法
（noop,deadline,as,cfq）。
熟悉块设备驱动的人知道，内核是通过 generic_make_request函数来不断下发 bio，
直到该 bio被挂载到物理设备的请求队列中。generic_make_request函数会获取 bio所指
向 bdev的请求队列，并通过请求队列的 q->make_request_fn方法来下发 bio。如果该 bdev
指向的是物理设备时，make_request_fn是由内核的__make_request函数来实现，通常 IO
调度也就是在该函数中发生。该函数过程分析如下(只列出与 IO调度有关系的部分)。
扇区(Sectors)：任何块设备硬件对数据处理的基本单位。通常，1个扇区的大小为 512byte。
块(Blocks)：由 Linux制定对内核或文件系统等数据处理的基本单位。通常，1个块由 1个
或多个扇区组成。
段(Segments)：由若干个相邻的块组成。是 Linux内存管理机制中一个内存页或者内存页的
一部分。
在通用块层中，通常用一个 bio结构体来对应一个 I/O请求，它代表了正在活动的以段
(Segment)链表形式组织的块 IO操作，对于它所需要的所有段又用 bio_vec结构体表示。所
以，一个 segment最多是一个 page大小。
队列的默认设置如下：
void blk_set_default_limits(struct queue_limits *lim)
{
lim->max_segments = BLK_MAX_SEGMENTS;//128
lim->max_integrity_segments = 0;
lim->seg_boundary_mask = BLK_SEG_BOUNDARY_MASK;
lim->max_segment_size = BLK_MAX_SEGMENT_SIZE;//65536
lim->max_sectors = lim->max_hw_sectors = BLK_SAFE_MAX_SECTORS;//255
lim->max_discard_sectors = 0;
lim->discard_granularity = 0;
lim->discard_alignment = 0;
lim->discard_misaligned = 0;
lim->discard_zeroes_data = 0;
lim->logical_block_size = lim->physical_block_size = lim->io_min = 512;
www.ingben.com
ww
w.
in
gb
en
.c
om
北京英本科技有限公司 www.ingben.com
2 / 19
lim->bounce_pfn = (unsigned long)(BLK_BOUNCE_ANY >> PAGE_SHIFT);
lim->alignment_offset = 0;
lim->io_opt = 0;
lim->misaligned = 0;
lim->cluster = 1;
}
EXPORT_SYMBOL(blk_set_default_limits)
172 void blk_queue_make_request(struct request_queue *q, make_request_fn *mfn)
173 {
174
177 q->nr_requests = BLKDEV_MAX_RQ;//128磁盘的队列中最多 128个请求。
179 q->make_request_fn = mfn;
180 blk_queue_dma_alignment(q, 511);
///队列中所有请求的配额。q->nr_congestion_on被处理请求的最大上限，默认是 111；
q->nr_congestion_off没有被处理请求的最大上限，默认 103
181 blk_queue_congestion_threshold(q);
182 q->nr_batching = BLK_BATCH_REQ;
183
184 blk_set_default_limits(&q->limits);
189 blk_queue_bounce_limit(q, BLK_BOUNCE_HIGH);
190 }
191 EXPORT_SYMBOL(blk_queue_make_request);
从上面的默认设置中，我们可以推断出每个 segment的大小是 512字节。
一个队列中有多少个请求？一个请求中有多少个 bio？一个 bio中有多少个
bi_phys_segments?
队列中有很多请求项，队列中最多的扇区数为：
enum blk_default_limits {
BLK_MAX_SEGMENTS = 128,
BLK_SAFE_MAX_SECTORS = 255,
#ifndef CONFIG_KERNEL_DESKTOP
BLK_DEF_MAX_SECTORS = 2048,
#else
BLK_DEF_MAX_SECTORS = 1024,
#endif
BLK_MAX_SEGMENT_SIZE = 65536,
www.ingben.com
ww
w.
in
gb
en
.c
om
北京英本科技有限公司 www.ingben.com
3 / 19
BLK_SEG_BOUNDARY_MASK = 0xFFFFFFFFUL,
};
参数 q：块设备请求对应的队列，bio即将处理的数据
static int __make_request(struct request_queue *q, struct bio
*bio) 1364 {
1365 const bool sync = !!(bio->bi_rw & REQ_SYNC);
1366 struct blk_plug *plug;
//ELEVATOR_INSERT_SORT用来把新的 bio重新排序到已经存在的请求中去。至于会用那个
请求 req是根据距离最近迭代算法计算出来的（具体函数见 elv_rqhash_find）。
//ELEVATOR_INSERT_FLUSH把新产生的 req请求，插入到磁盘公共块层的队列中去。
1367 int el_ret, rw_flags, where = ELEVATOR_INSERT_SORT;
1368 struct request *req;
1369 unsigned int request_count = 0;
//此函数是从回弹缓冲区池中分配一些 Page出来，分配 Page的多少是由传入的参数 bio
中的 page个数决定的，并把 bio中 page的数据拷贝到回弹缓冲区的页中；然后再设置传人
参数 bio中回弹读写回调函数；最后是更新传人参数 bio中的状态统计信息。
1376 blk_queue_bounce(q, &bio);
1377
1378 if (bio_integrity_enabled(bio) && bio_integrity_prep(bio)) {
1379 bio_endio(bio, -EIO);
1380 return -EIO;
1381 }
1383 if (bio->bi_rw & (REQ_FLUSH | REQ_FUA)) {
1384 spin_lock_irq(q->queue_lock);
1385 where = ELEVATOR_INSERT_FLUSH;
1386 goto get_rq;
1387 }
//当前进程尝试把 bio合并到当前进程的队列(注：当前进程有很多队列，选的是和磁盘设
备一样的队列)中的一个请求中去。一个队列中有很多个请求，是哪个请求是需要 IO调度算
法来定的。attempt_plug_merge函数最终会调用核心函数
e->ops->elevator_allow_merge_fn(q, rq, bio)来判断是否允许合并操作，不同的电梯调
度算法有不同的 elevator_allow_merge_fn实现，但是在 3.1内核中只有 cfq实现了本函数
cfq_bio_merged，cfq_bio_merged主要是更新 per cpu blkio 组的状态（direction
和 sync位，以及同步计数 seq加 1操作）。返回成功跳转到 Out，然后退出，否则继续
向下执行。
1393 if (attempt_plug_merge(q, bio, &request_count))
1394 goto out;
1395 //如果尝试合并 bio到请求中队列中的任何一个请求失败，则执行下面
流程
快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计
。
www.ingben.com
ww
w.
in
gb
en
.c
om
北京英本科技有限公司 www.ingben.com
4 / 19
1396 spin_lock_irq(q->queue_lock);
1398 el_ret = elv_merge(q, &req, bio);
//处理见下面
1399 if (el_ret == ELEVATOR_BACK_MERGE) {
1400 if (bio_attempt_back_merge(q, req, bio)) {
1401 elv_bio_merged(q, req, bio);
1402 if (!attempt_back_merge(q, req))
1403 elv_merged_request(q, req, el_ret);
1404 goto out_unlock;
1405 }
1406 } else if (el_ret == ELEVATOR_FRONT_MERGE) {
1407 if (bio_attempt_front_merge(q, req, bio)) {
1408 elv_bio_merged(q, req, bio);
1409 if (!attempt_front_merge(q, req))
1410 elv_merged_request(q, req, el_ret);
1411 goto out_unlock;
1412 }
1413 }
1414//创建新的请求 req，请求的分配是从磁盘队列的请求池中分配的，所以我们开大请求
池来优化。因为系统中请求可以被消耗完，尤其是大量 IO请求发生的时候。研究下请求池
最开始分配的是多大空间？
1415 get_rq:
1421 rw_flags = bio_data_dir(bio);
1422 if (sync)
1423 rw_flags |= REQ_SYNC;
1429 req = get_request_wait(q, rw_flags, bio);
1430 if (unlikely(!req)) {
1431 bio_endio(bio, -ENODEV);
1432 goto out_unlock;
1433 }
//init_request_from_bio(req, bio)初始化请求描述符中的字段。主要有：
a) 根据 bio描述符的
内容
财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容
初始化各个字段，包括扇区数、当前 bio以及当前段。
b) 设置 flags字段中的 REQ_CMD标志（说明这次 request是一个标准的读或写操作）。
c) 如果第一个 bio段的页框存放在低端内存，则将 buffer字段设置为缓冲区的线性地址。
d) 将 rc_disk字段设置为 bio->bi_bdev->bd_disk的地址。
e) 将 bio插入请求链表。
www.ingben.com
ww
w.
in
gb
en
.c
om
北京英本科技有限公司 www.ingben.com
5 / 19
f) 将 start_time字段设置为 jiffies的值。
1441 init_request_from_bio(req, bio);
1443 if (test_bit(QUEUE_FLAG_SAME_COMP, &q->queue_flags) ||
1444 bio_flagged(bio, BIO_CPU_AFFINE)) {
1445 req->cpu = blk_cpu_to_group(get_cpu());
1446 put_cpu();
1447 }
1448
1449 plug = current->plug;
//当前进程是支持 plug的话，则把新的 req添加到进程的 plug->list中去。
1450 if (plug) {
1457 if (list_empty(&plug->list))
1458 trace_block_plug(q);
1459 else {
1460 if (!plug->should_sort) {
1461 struct request *__rq;
1463 __rq = list_entry_rq(plug->list.prev);
1464 if (__rq->q != q)
1465 plug->should_sort = 1;
1466 }
1467 if (request_count >= BLK_MAX_REQUEST_COUNT) {
1468 blk_flush_plug_list(plug, false);
1469 trace_block_plug(q);
1470 }
1471 }
1472 list_add_tail(&req->queuelist, &plug->list);
1473 drive_stat_acct(req, 1);
1474 } else {
1475 spin_lock_irq(q->queue_lock);
//当前进程不支持 plug，则插入该请求
1476 add_acct_request(q, req, where);
1477 __blk_run_queue(q);
1478 out_unlock:
1479 spin_unlock_irq(q->queue_lock);
1480 }
1481 out:
1482 return 0;
1483 }
//尝试着合并
www.ingben.com
ww
w.
in
gb
en
.c
om
北京英本科技有限公司 www.ingben.com
6 / 19
1312 static bool attempt_plug_merge(struct request_queue *q, struct bio
*bio, unsigned int *request_count)
1324 list_for_each_entry_reverse(rq, &plug->list, queuelist) {
1325 int el_ret;
1327 if (rq->q == q)
1328 (*request_count)++;
1330 if (rq->q != q || !blk_rq_merge_ok(rq, bio))
1331 continue;
1332//决定 bio如何合并的方向？
1333 el_ret = blk_try_merge(rq, bio);
1334 if (el_ret == ELEVATOR_BACK_MERGE) {
//如果函数 bio_attempt_back_merge返回 0,不能退出，则继续找队列中的其他请求后进行
向后合并，直到向后合并成功为止。
1335 ret = bio_attempt_back_merge(q, rq, bio);
1336 if (ret)
1337 break;
//如果函数 bio_attempt_front_merge返回 0.不能退出，则继续找队列中的其他请求后进
行向前合并，直到向后前并成功为止。
1338 } else if (el_ret == ELEVATOR_FRONT_MERGE) {
1339 ret = bio_attempt_front_merge(q, rq, bio);
1340 if (ret)
1341 break;
1342 }
1343 }
1344 out:
1345 return ret;
1346 }
477 int blk_try_merge(struct request *rq, struct bio *bio)
478 {
//如果请求中当前扇区+请求中剩余扇区等于 bio中扇区的话，则认为是像后合并。
bio->bi_sector表示 bio中的第一个扇区位置位置。bio_sectors(bio)表示 bio中连续传
输的扇区个数。
479 if (blk_rq_pos(rq) + blk_rq_sectors(rq) == bio->bi_sector)
480 return ELEVATOR_BACK_MERGE;
//如果请求中当前扇区-bio中扇区数等于 bio中扇区 id的话，则认为是向后前合并。
481 else if (blk_rq_pos(rq) - bio_sectors(bio) == bio->bi_sector)
482 return ELEVATOR_FRONT_MERGE;
www.ingben.com
ww
w.
in
gb
en
.c
om
北京英本科技有限公司 www.ingben.com
7 / 19
483 return ELEVATOR_NO_MERGE;
484 }
1243 static bool bio_attempt_back_merge(struct request_queue *q, struct request
*req,struct bio *bio)
1245 {
1246 const int ff = bio->bi_rw & REQ_FAILFAST_MASK;
1247 //ll_back_merge_fn函数是计算出 bio中 segment的个数后更新到 req的 segment中
去，返回值为 1说明成功更新，否则返回 0就不能继续下面执行。
1248 if (!ll_back_merge_fn(q, req, bio))
1249 return false;
1251 trace_block_bio_backmerge(q, bio);
1252 //给请求的标记位 cmd_flags或 REQ_MIXED_MERGE计算，说明请求中将要添加 bio了。
并将这个 req请求中已经存在的所有 bio进行 REQ_FAILFAST_MASK或操作。
1253 if ((req->cmd_flags & REQ_FAILFAST_MASK) != ff)
1254 blk_rq_set_mixed_merge(req);
1255 //更新请求中的链表操作，把入参 bio添加到请求的 biotail后面。
1256 req->biotail->bi_next = bio;
1257 req->biotail = bio;
1258 req->__data_len += bio->bi_size;
//将 bio的优先级和请求中的优先级进行比较，存放最小的优先级到请求 req中。请求 req
中的每一个 Bio都是有优先级的。
1259 req->ioprio = ioprio_best(req->ioprio, bio_prio(bio));
1260 //更改 cpu和磁盘的关联信息
1261 drive_stat_acct(req, 0);
1262 return true;
1263 }
int ll_back_merge_fn(struct request_queue *q, struct request *req,
struct bio *bio)
{
if (blk_rq_sectors(req) + bio_sectors(bio) >
blk_rq_get_max_sectors(req)) {
req->cmd_flags |= REQ_NOMERGE;
if (req == q->last_merge)
q->last_merge = NULL;
return 0;
}
//判断 req请求中的最后一个 bio是否是有效的，无效的话，则调用 blk_recount_segments
来填充请求中最后一个 bio中的部分字段。
www.ingben.com
ww
w.
in
gb
en
.c
om
北京英本科技有限公司 www.ingben.com
8 / 19
if (!bio_flagged(req->biotail, BIO_SEG_VALID))
blk_recount_segments(q, req->biotail);
//判断传入的参数 bio是否有效，无效的话，则调用 blk_recount_segments来填充当前 bio
中的部分字段。
if (!bio_flagged(bio, BIO_SEG_VALID))
blk_recount_segments(q, bio);//这里的 segment指的是 Bio里面有多
少个 Page，一个 page是一个 segment
return ll_new_hw_segment(q, req, bio);
}
202 static inline int ll_new_hw_segment(struct request_queue *q,
203 struct request *req,
204 struct bio *bio)
205 {
206 int nr_phys_segs = bio_phys_segments(q, bio);
207 //如果当前 req请求中的 segment数目+当前 bio中 segment的数目大于整个队列中的
segment，则该 req中无法添加 bio了
208 if (req->nr_phys_segments + nr_phys_segs > queue_max_segments(q))
209 goto no_merge;
211 if (bio_integrity(bio) && blk_integrity_merge_bio(q, req, bio))
212 goto no_merge;
//把 bio中的 segment加到请求中去
218 req->nr_phys_segments += nr_phys_segs;
219 return 1;
221 no_merge:
222 req->cmd_flags |= REQ_NOMERGE;
223 if (req == q->last_merge)
224 q->last_merge = NULL;
225 return 0;
226 }
//bio在请求中向前合并核心处理函数，其他部分函数和向后处理类似，不再敖述！
1265 static bool bio_attempt_front_merge(struct request_queue *q,
1266 struct request *req, struct bio *bio)
1267 {
1268 const int ff = bio->bi_rw & REQ_FAILFAST_MASK;
1270 if (!ll_front_merge_fn(q, req, bio))
1271 return false;
1273 trace_block_bio_frontmerge(q, bio);
1275 if ((req->cmd_flags & REQ_FAILFAST_MASK) != ff)
www.ingben.com
ww
w.
in
gb
en
.c
om
北京英本科技有限公司 www.ingben.com
9 / 19
1276 blk_rq_set_mixed_merge(req);
1277 //把 bio添加到请求中 bio链表的最前面去。
1278 bio->bi_next = req->bio;
1279 req->bio = bio;
//讲 bio中的 page转换成映射后的虚拟地址存放到 req的 buffer中。
1286 req->buffer = bio_data(bio);
1287 req->__sector = bio->bi_sector;
1288 req->__data_len += bio->bi_size;
//同上面，更新最小的优先级到请求中保存。
1289 req->ioprio = ioprio_best(req->ioprio, bio_prio(bio));
1290
1291 drive_stat_acct(req, 0);
1292 return true;
1293 }
//开始新的方式来合并
425 int elv_merge(struct request_queue *q, struct request **req, struct bio *bio)
426 {
427 struct elevator_queue *e = q->elevator;
428 struct request *__rq;
429 int ret;
//如果队列标记中 QUEUE_FLAG_NOMERGES打开，则不能合并，返回。
437 if (blk_queue_nomerges(q))
438 return ELEVATOR_NO_MERGE;
//选择队列中的最后一个请求出来，并尝试是否可以把 bio合并进去？
443 if (q->last_merge && elv_rq_merge_ok(q->last_merge, bio)) {
444 ret = blk_try_merge(q->last_merge, bio);
445 if (ret != ELEVATOR_NO_MERGE) {
446 *req = q->last_merge;
447 return ret;
448 }
449 }
451 if (blk_queue_noxmerges(q))
452 return ELEVATOR_NO_MERGE;
457 __rq = elv_rqhash_find(q, bio->bi_sector);
458 if (__rq && elv_rq_merge_ok(__rq, bio)) {
459 *req = __rq;
460 return ELEVATOR_BACK_MERGE;
461 }
www.ingben.com
ww
w.
in
gb
en
.c
om
北京英本科技有限公司 www.ingben.com
10 / 19
462//调用电梯的特定算法来合并，在 3.0以后的内核中，还保留了 cfq和 deadline的算
法实现，他们分别是 cfq_merge和 deadline_merge。
463 if (e->ops->elevator_merge_fn)
464 return e->ops->elevator_merge_fn(q, req, bio);
465
466 return ELEVATOR_NO_MERGE;
467 }
//用 Hash算法先查找。
282 static struct request *elv_rqhash_find(struct request_queue *q, sector_t
offset)
283 {
284 struct elevator_queue *e = q->elevator;
//基于 offset变量找到 hash值链表
285 struct hlist_head *hash_list = &e->hash[ELV_HASH_FN(offset)];
286 struct hlist_node *entry, *next;
287 struct request *rq;
288//基于此 hash值，迭代该 hash链表上所有的请求 req直到满足"rq_hash_key(rq) ==
offset"为止。
289 hlist_for_each_entry_safe(rq, entry, next, hash_list, hash) {
290 BUG_ON(!ELV_ON_HASH(rq));
291
292 if (unlikely(!rq_mergeable(rq))) {
293 __elv_rqhash_del(rq);
294 continue;
295 }
296
297 if (rq_hash_key(rq) == offset)
298 return rq;
299 }
300
301 return NULL;
302 }
图解 Hash查找，因此可以增加 HASH项来优化，从而内存使用就会增加了。
www.ingben.com
ww
w.
in
gb
en
.c
om
北京英本科技有限公司 www.ingben.com
11 / 19
1610 static int cfq_merge(struct request_queue *q, struct request **req,
1611 struct bio *bio)
1612 {//获得 cfq电梯算法的数据
1613 struct cfq_data *cfqd = q->elevator->elevator_data;
1614 struct request *__rq;
1615 //在 sort_list队列中找一个最靠谱的（距离将处理 bio扇区最近的）req请求出来
1616 __rq = cfq_find_rq_fmerge(cfqd, bio);
1617 if (__rq && elv_rq_merge_ok(__rq, bio)) {
1618 *req = __rq;
1619 return ELEVATOR_FRONT_MERGE;
1620 }
1621
1622 return ELEVATOR_NO_MERGE;
1623 }
1549 static struct request *
1550 cfq_find_rq_fmerge(struct cfq_data *cfqd, struct bio *bio)
1551 {
1552 struct task_struct *tsk = current;
1553 struct cfq_io_context *cic;
1554 struct cfq_queue *cfqq;
1555 //从当前进程的 io上下文 radix树中查找满足本磁盘 io cfq调度算法的
cfq_io_context 。
1556 cic = cfq_cic_lookup(cfqd, tsk->io_context);
1557 if (!cic)
1558 return NULL;
www.ingben.com
ww
w.
in
gb
en
.c
om
北京英本科技有限公司 www.ingben.com
12 / 19
1559 //将磁盘通用块层的队列 request_queue转成了磁盘特定算法的队列 cfq_queue
1560 cfqq = cic_to_cfqq(cic, cfq_bio_sync(bio));
1561 if (cfqq) {
1562 sector_t sector = bio->bi_sector + bio_sectors(bio);
1563 //利用红黑树查找即将处理的 bio中的扇区最接近的是哪一个 req请求。执行结果是
返回了紧挨着即将处理 bio的那个扇区的 req请求。用的 sort_list队列，此队列中存储是
所有待处理的请求集合。
1564 return elv_rb_find(&cfqq->sort_list, sector);
1565 }
1566
1567 return NULL;
1568 }
//插入请求 req到队列中去
1074 static void add_acct_request(struct request_queue *q, struct request *rq,
1075 int where)
1076 {
//见上面分析 drive_stat_acct（）
1077 drive_stat_acct(rq, 1);
1078 __elv_add_request(q, rq, where);
1079 }
595 void __elv_add_request(struct request_queue *q, struct request *rq, int where)
596 {
597 trace_block_rq_insert(q, rq);
598 //更新请求 req的队列指针
599 rq->q = q;
600 //如果请求是来自于文件系统且请求属于屏障，则把该队列的最后一个扇区更新成请
求的最后扇区，把该请求 req列入为队列中的相邻请求（因为请求 req中的扇区或许和队列
中的其他请求处理扇区是相邻的）
601 if (rq->cmd_flags & REQ_SOFTBARRIER) {
602
603 if (rq->cmd_type == REQ_TYPE_FS) {
604 q->end_sector = rq_end_sector(rq);
605 q->boundary_rq = rq;
606 }
607 } else if (!(rq->cmd_flags & REQ_ELVPRIV) &&
608 (where == ELEVATOR_INSERT_SORT ||
609 where == ELEVATOR_INSERT_SORT_MERGE))
610 where = ELEVATOR_INSERT_BACK;
612 switch (where) {
613 case ELEVATOR_INSERT_REQUEUE://重新入队
www.ingben.com
ww
w.
in
gb
en
.c
om
北京英本科技有限公司 www.ingben.com
13 / 19
614 case ELEVATOR_INSERT_FRONT:
615 rq->cmd_flags |= REQ_SOFTBARRIER;
//新产生的 req请求插队到队列的最前面，目的是让该请求 req最先被处理
616 list_add(&rq->queuelist,
浙公网安备 33021202002483