Linux IO Scheduler-CFQ(上)

Linux IO Scheduler–CFQ(下)

      前文介绍了CFQ调度器的一些概念和结构之间的关系，这里再结合实际的代码，来分析CFQ的工作流程。CFQ调度器的定义如下：

static struct elevator_type iosched_cfq = {
	.ops = {
		.elevator_merge_fn = 		cfq_merge,
		.elevator_merged_fn =		cfq_merged_request,
		.elevator_merge_req_fn =	cfq_merged_requests,
		.elevator_allow_merge_fn =	cfq_allow_merge,
		.elevator_dispatch_fn =		cfq_dispatch_requests,
		.elevator_add_req_fn =		cfq_insert_request,
		.elevator_activate_req_fn =	cfq_activate_request,
		.elevator_deactivate_req_fn =	cfq_deactivate_request,
		.elevator_queue_empty_fn =	cfq_queue_empty,
		.elevator_completed_req_fn =	cfq_completed_request,
		.elevator_former_req_fn =	elv_rb_former_request,
		.elevator_latter_req_fn =	elv_rb_latter_request,
		.elevator_set_req_fn =		cfq_set_request,
		.elevator_put_req_fn =		cfq_put_request,
		.elevator_may_queue_fn =	cfq_may_queue,
		.elevator_init_fn =		cfq_init_queue,
		.elevator_exit_fn =		cfq_exit_queue,
		.trim =				cfq_free_io_context,
	},
	.elevator_attrs =	cfq_attrs,
	.elevator_name =	"cfq",
	.elevator_owner =	THIS_MODULE,
};

可以看到CFQ调度器涉及到的操作函数还是比较多的，这里我只打算选一些和提交bio以及request相关的函数进行分析。在提交bio的时候，如果在通用层寻找可以合并bio的途径失败，要通过cfq_merge()来判断是否能够将bio插入到某个request的bio链表首部

static struct request *
cfq_find_rq_fmerge(struct cfq_data *cfqd, struct bio *bio)
{
	struct task_struct *tsk = current;
	struct cfq_io_context *cic;
	struct cfq_queue *cfqq;

	//在进程的io_context中，找到进程特定于块设备的cfq_io_context
	cic = cfq_cic_lookup(cfqd, tsk->io_context);
	if (!cic)
		return NULL;

	//根据同步还是异步，确定cfq_queue
	cfqq = cic_to_cfqq(cic, cfq_bio_sync(bio));
	if (cfqq) {
		sector_t sector = bio->bi_sector + bio_sectors(bio);//得到末尾扇区号

		//从cfq_queue的红黑树中查找对应的节点
		return elv_rb_find(&cfqq->sort_list, sector);
	}

	return NULL;
}

cfq_find_rq_fmerge()进行实际的搜索工作，要确定bio的归属request，必须先确定进程的通信对象是谁(因为一个进程有可能和多个块设备通信)，也就是要找到进程对应的cfq_io_context结构，其中包含了进程的同步请求队列和异步请求队列的地址，只要找到了相应的cfq_io_context，就可以通过bio的同异步性确定对应的cfq_queue了，最后再判断对应的cfq_queue中是否存在可以容纳bio的request。推导cfq_io_context的关键在于以块设备CFQ调度器的描述结构cfq_data的地址为关键值，在进程的io_context的基数树中进行搜索

static struct request *
cfq_find_rq_fmerge(struct cfq_data *cfqd, struct bio *bio)
{
	struct task_struct *tsk = current;
	struct cfq_io_context *cic;
	struct cfq_queue *cfqq;

	//在进程的io_context中，找到进程特定于块设备的cfq_io_context
	cic = cfq_cic_lookup(cfqd, tsk->io_context);
	if (!cic)
		return NULL;

	//根据同步还是异步，确定cfq_queue
	cfqq = cic_to_cfqq(cic, cfq_bio_sync(bio));
	if (cfqq) {
		sector_t sector = bio->bi_sector + bio_sectors(bio);//得到末尾扇区号

		//从cfq_queue的红黑树中查找对应的节点
		return elv_rb_find(&cfqq->sort_list, sector);
	}

	return NULL;
}

通过基数树寻找对应设备的cfq_io_context:

static struct cfq_io_context *

cfq_cic_lookup(struct cfq_data *cfqd, struct io_context *ioc)

{

	struct cfq_io_context *cic;

	unsigned long flags;

	void *k;

	if (unlikely(!ioc))

		return NULL;
	rcu_read_lock();
	/*

	 * we maintain a last-hit cache, to avoid browsing over the tree

	 */
	//由于进程很有可能连续访问同一块设备，因此先将cic中的关键值直接与cfqd比较

	cic = rcu_dereference(ioc->ioc_data);

	if (cic && cic->key == cfqd) {

		rcu_read_unlock();

		return cic;

	}
	do {//在进程io_context的基数树中寻找对应访问的块设备的cfq_data结构

		cic = radix_tree_lookup(&ioc->radix_root, (unsigned long) cfqd);

		rcu_read_unlock();

		if (!cic)

			break;

		/* ->key must be copied to avoid race with cfq_exit_queue() */

		k = cic->key;

		if (unlikely(!k)) {

			cfq_drop_dead_cic(cfqd, ioc, cic);

			rcu_read_lock();

			continue;

		}
		//保存cic到ioc->ioc_data

		spin_lock_irqsave(&ioc->lock, flags);