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を決定するには、プロセスの通信オブジェクトが誰であるか(1つのプロセスが複数のブロックデバイスと通信する可能性があるため)、すなわちプロセスに対応するcfq_を見つける必要がある.io_プロセスの同期要求キューと非同期要求キューのアドレスが含まれているcontext構造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);
		rcu_assign_pointer(ioc->ioc_data, cic);
		spin_unlock_irqrestore(&ioc->lock, flags);
		break;
	} while (1);

	return cic;
}

汎用レイヤ_make_request()関数でbioが受信オブジェクトを見つけられない場合は、requestを再作成して受信します.リクエストを割り当てるには初期化が必要で、cfq_を呼び出す必要があります.set_request()関数.前の手順と似ているのは、requestが受信したcfq_を先に見つけることです.Queue、次にここで問題が発生しました.このrequestがプロセスの最初の同期要求または非同期要求である場合、新しいcfq_を割り当てる必要があります.リクエストを受信します.同期要求と非同期要求の処理状況は少し違います.プロセスは独自の同期要求キューを持っており、プロセスの非同期要求はcfq_を共有しているからです.Dataの非同期リクエストキューのため、requestが同期リクエストである場合にのみcfq_Queueの割当て

static int
cfq_set_request(struct request_queue *q, struct request *rq, gfp_t gfp_mask)
{
	struct cfq_data *cfqd = q->elevator->elevator_data;
	struct cfq_io_context *cic;
	const int rw = rq_data_dir(rq);
	const bool is_sync = rq_is_sync(rq);
	struct cfq_queue *cfqq;
	unsigned long flags;

	might_sleep_if(gfp_mask & __GFP_WAIT);

	//           cfq_io_context  
	cic = cfq_get_io_context(cfqd, gfp_mask);

	spin_lock_irqsave(q->queue_lock, flags);

	if (!cic)
		goto queue_fail;

new_queue:
	cfqq = cic_to_cfqq(cic, is_sync);//       ，        cfq_queue
	if (!cfqq || cfqq == &cfqd->oom_cfqq) {//        cfqq     
		cfqq = cfq_get_queue(cfqd, is_sync, cic->ioc, gfp_mask);//  cfq_queue
		cic_set_cfqq(cic, cfqq, is_sync);//  cic->cfqq[is_sync] = cfqq
	} else {
		/*
		 * If the queue was seeky for too long, break it apart.
		 */
		if (cfq_cfqq_coop(cfqq) && should_split_cfqq(cfqq)) {
			cfq_log_cfqq(cfqd, cfqq, "breaking apart cfqq");
			cfqq = split_cfqq(cic, cfqq);
			if (!cfqq)
				goto new_queue;
		}

		/*
		 * Check to see if this queue is scheduled to merge with
		 * another, closely cooperating queue.  The merging of
		 * queues happens here as it must be done in process context.
		 * The reference on new_cfqq was taken in merge_cfqqs.
		 */
		if (cfqq->new_cfqq)
			cfqq = cfq_merge_cfqqs(cfqd, cic, cfqq);
	}

	cfqq->allocated[rw]++;
	atomic_inc(&cfqq->ref);

	spin_unlock_irqrestore(q->queue_lock, flags);

	rq->elevator_private = cic;//  cfq_io_context request
	rq->elevator_private2 = cfqq;//  cfq_queue request
	return 0;

queue_fail:
	if (cic)
		put_io_context(cic->ioc);

	cfq_schedule_dispatch(cfqd);
	spin_unlock_irqrestore(q->queue_lock, flags);
	cfq_log(cfqd, "set_request fail");
	return 1;
}

requestが初期化を作成すると、対応するキューに挿入されます.cfq_insert_request()関数はこの機能を完了し、deadlineスケジューラと同様に、requestは2つのキューに格納されます.1つは、応答期限に従って並べられたチェーンテーブル(fifo)です.

static void cfq_insert_request(struct request_queue *q, struct request *rq)
{
	struct cfq_data *cfqd = q->elevator->elevator_data;
	struct cfq_queue *cfqq = RQ_CFQQ(rq);

	cfq_log_cfqq(cfqd, cfqq, "insert_request");
	cfq_init_prio_data(cfqq, RQ_CIC(rq)->ioc);//  ioc  cfq_queue         

	cfq_add_rq_rb(rq);// rq   cfq_queue    

	//     
	rq_set_fifo_time(rq, jiffies + cfqd->cfq_fifo_expire[rq_is_sync(rq)]);
	list_add_tail(&rq->queuelist, &cfqq->fifo);//   fifo

	cfq_rq_enqueued(cfqd, cfqq, rq);
}

1つのrequestが新しいbioに組み込まれると、他のrequestとマージできるかどうかを考慮し、bioをチェーンテーブルの末尾に挿入する場合はsort_listでrequestの後のrequestを取得し(関数elv_rb_latter_request()で取得)、前者の終了セクタと前者の開始セクタが同じかどうかを判断します.これらの作業はすべて再汎用レイヤコードで完了し、2つのrequestが汎用レイヤのレビューとマージ操作を完了するとcfq_が呼び出されます.merged_requestsはキューの追加作業を行います

tatic void
cfq_merged_requests(struct request_queue *q, struct request *rq,
		    struct request *next)
{
	/*
	 * reposition in fifo if next is older than rq
	 */
	if (!list_empty(&rq->queuelist) && !list_empty(&next->queuelist) &&
	    time_before(rq_fifo_time(next), rq_fifo_time(rq))) {
		list_move(&rq->queuelist, &next->queuelist);
		rq_set_fifo_time(rq, rq_fifo_time(next));
	}

	cfq_remove_request(next);
}

ここでは主に2つのrequestの期限を考察するが,いずれも後者を前者に統合するため,後者の期限時間が前者より小さい場合にはdeadlineスケジューラと同様に調整する.
 
最後に分析したのは、各スケジューラの最も重要な関数であるelevator_です.dispatch_fn
CFQスケジューラがrequest最下位層ブロックデバイスを送信する際の流れは、概ね以下の通りである.
1.cfq_を選択queue
2.cfq_からqueueでrequestを選択して送信
cfq_を選択Queueの考え方は以下の通りです.
1.現在のcfq_の場合Queueのタイムスライスがまだ切れていない場合は、現在のcfq_を続行します.queue
2.現在のcfq_の場合Queueのタイムスライスが消費されると、対応するprio_が優先されるtreeでcfq_を選択queue,このcfq_queueの最初のアクセスセクタとスケジューラ全体が最後に処理したセクタとの差は、1つのしきい値よりも小さくなければならない.OKであれば、このcfq_を選択するqueue
3.こんなcfqが見つからなかったらQueue、サービスからtreeで他のcfq_をスケジューリングqueue

static int cfq_dispatch_requests(struct request_queue *q, int force)
{
	struct cfq_data *cfqd = q->elevator->elevator_data;
	struct cfq_queue *cfqq;

	if (!cfqd->busy_queues)
		return 0;

	if (unlikely(force))
		return cfq_forced_dispatch(cfqd);

	//        
	cfqq = cfq_select_queue(cfqd);
	if (!cfqq)
		return 0;

	/*
	 * Dispatch a request from this cfqq, if it is allowed
	 */
	 //    cfq_queue   request    
	if (!cfq_dispatch_request(cfqd, cfqq))
		return 0;

	cfqq->slice_dispatch++;
	cfq_clear_cfqq_must_dispatch(cfqq);

	/*
	 * expire an async queue immediately if it has used up its slice. idle
	 * queue always expire after 1 dispatch round.
	 */
	 /*  service_tree          ，        
	                              ，
	           ，   idle                  
	 */
	if (cfqd->busy_queues > 1 && ((!cfq_cfqq_sync(cfqq) &&
	    cfqq->slice_dispatch >= cfq_prio_to_maxrq(cfqd, cfqq)) ||
	    cfq_class_idle(cfqq))) {
		cfqq->slice_end = jiffies + 1;
		cfq_slice_expired(cfqd, 0);
	}

	cfq_log_cfqq(cfqd, cfqq, "dispatched a request");
	return 1;
}

 
cfq_select_Queue()はキューを選択するために使用され、active_Queueは現在実行中のキューです

static struct cfq_queue *cfq_select_queue(struct cfq_data *cfqd)
{
	struct cfq_queue *cfqq, *new_cfqq = NULL;

	/*   active_queue*/
	cfqq = cfqd->active_queue;
	if (!cfqq)//    active_queue    new_queue       
		goto new_queue;

	/*
	 * The active queue has run out of time, expire it and select new.
	 */
	 //   active_queue,                 
	if (cfq_slice_used(cfqq) && !cfq_cfqq_must_dispatch(cfqq))
		goto expire;

	/*
	 * The active queue has requests and isn't expired, allow it to
	 * dispatch.
	 */
	 /*           ，    cfq_queue sort_list    */
	if (!RB_EMPTY_ROOT(&cfqq->sort_list))
		goto keep_queue;

	/*
	 * If another queue has a request waiting within our mean seek
	 * distance, let it run.  The expire code will check for close
	 * cooperators and put the close queue at the front of the service
	 * tree.  If possible, merge the expiring queue with the new cfqq.
	 */
	 //      active_queue        ，          cfq_queue
	new_cfqq = cfq_close_cooperator(cfqd, cfqq);
	if (new_cfqq) {
		if (!cfqq->new_cfqq)
			cfq_setup_merge(cfqq, new_cfqq);
		goto expire;
	}

	/*
	 * No requests pending. If the active queue still has requests in
	 * flight or is idling for a new request, allow either of these
	 * conditions to happen (or time out) before selecting a new queue.
	 */
	if (timer_pending(&cfqd->idle_slice_timer) ||
	    (cfqq->dispatched && cfq_cfqq_idle_window(cfqq))) {
		cfqq = NULL;
		goto keep_queue;
	}

expire:
	cfq_slice_expired(cfqd, 0);//        active_queue    service_tree
new_queue:
	cfqq = cfq_set_active_queue(cfqd, new_cfqq);//  new_cfqq   active_tree     
keep_queue:
	return cfqq;
}

cfq_close_cooperatorはセクタアドレスで要求を満たすキューを検索します.この操作は同期要求キューにのみ有効です.

static struct cfq_queue *cfq_close_cooperator(struct cfq_data *cfqd,
					      struct cfq_queue *cur_cfqq)
{
	struct cfq_queue *cfqq;

	if (!cfq_cfqq_sync(cur_cfqq))
		return NULL;
	if (CFQQ_SEEKY(cur_cfqq))
		return NULL;

	/*
	 * We should notice if some of the queues are cooperating, eg
	 * working closely on the same area of the disk. In that case,
	 * we can group them together and don't waste time idling.
	 */
	 //       ，          
	cfqq = cfqq_close(cfqd, cur_cfqq);
	if (!cfqq)
		return NULL;

	/*
	 * It only makes sense to merge sync queues.
	 */
	if (!cfq_cfqq_sync(cfqq))
		return NULL;
	if (CFQQ_SEEKY(cfqq))
		return NULL;

	return cfqq;
}

cfqq_closeは実際の作業を実行する

static struct cfq_queue *cfqq_close(struct cfq_data *cfqd,
				    struct cfq_queue *cur_cfqq)
{
	struct rb_root *root = &cfqd->prio_trees[cur_cfqq->org_ioprio];
	struct rb_node *parent, *node;
	struct cfq_queue *__cfqq;
	sector_t sector = cfqd->last_position;//          

	if (RB_EMPTY_ROOT(root))
		return NULL;

	/*
	 * First, if we find a request starting at the end of the last
	 * request, choose it.
	 */
	 //                              cfq_queue
	__cfqq = cfq_prio_tree_lookup(cfqd, root, sector, &parent, NULL);
	if (__cfqq)//           cfq_queue    
		return __cfqq;

	/*
	 * If the exact sector wasn't found, the parent of the NULL leaf
	 * will contain the closest sector.
	 */
	 //parent             ，        cfq_queue，        cfq_queue
	__cfqq = rb_entry(parent, struct cfq_queue, p_node);
	
	/*  __cfqq        (next_rq  )                              ，
	      cfq_queue*/
	if (cfq_rq_close(cfqd, cur_cfqq, __cfqq->next_rq))
		return __cfqq;

	/*       ，   next_rq sector     ，
	           __cfqq               */
	if (blk_rq_pos(__cfqq->next_rq) < sector)
		node = rb_next(&__cfqq->p_node);
	else
		node = rb_prev(&__cfqq->p_node);
	if (!node)
		return NULL;

	//                  ，        ，      ，    NULL
	__cfqq = rb_entry(node, struct cfq_queue, p_node);
	if (cfq_rq_close(cfqd, cur_cfqq, __cfqq->next_rq))
		return __cfqq;

	return NULL;
}

このようなキューが見つかった場合、cfq_set_active_Queue()関数でキューを実行キューに設定します.そうしないとservice_からtreeでスケジューリングポイントが最も隣接するキュー

static struct cfq_queue *cfq_set_active_queue(struct cfq_data *cfqd,
					      struct cfq_queue *cfqq)
{
	if (!cfqq)//     cfqq，  service_tree      
		cfqq = cfq_get_next_queue(cfqd);

	__cfq_set_active_queue(cfqd, cfqq);//  active_queue cfqq
	return cfqq;
}

 
キューの選択が完了しました.次にcfq_を通過します.dispatch_request()関数キューで適切なrequestを選択して送信
 

static bool cfq_dispatch_request(struct cfq_data *cfqd, struct cfq_queue *cfqq)
{
	struct request *rq;

	BUG_ON(RB_EMPTY_ROOT(&cfqq->sort_list));

	//         cfqq    
	if (!cfq_may_dispatch(cfqd, cfqq))
		return false;

	/*
	 * follow expired path, else get first next available
	 */
	 /*     fifo    ，  fifo    fifo            ，      request*/
	rq = cfq_check_fifo(cfqq);
	if (!rq)//  fifo   rq  ，      next_rq，next_rq             
		rq = cfqq->next_rq;

	/*
	 * insert request into driver dispatch list
	 */
	cfq_dispatch_insert(cfqd->queue, rq);// rq          

	if (!cfqd->active_cic) {
		struct cfq_io_context *cic = RQ_CIC(rq);

		atomic_long_inc(&cic->ioc->refcount);
		cfqd->active_cic = cic;
	}

	return true;
}

特定のリクエストを送信する前に、キューにリクエストを発行するのに適しているかどうかを決定します.主に、キューがタイムスライス内で送信されたリクエストの数が超過しているかどうかを判断します.

static bool cfq_may_dispatch(struct cfq_data *cfqd, struct cfq_queue *cfqq)
{
	unsigned int max_dispatch;

	/*
	 * Drain async requests before we start sync IO
	 */
	 //  cfqq   idle           ，             
	if (cfq_cfqq_idle_window(cfqq) && cfqd->rq_in_driver[BLK_RW_ASYNC])
		return false;

	/*
	 * If this is an async queue and we have sync IO in flight, let it wait
	 */
	 //            request_queue            ，    
	if (cfqd->sync_flight && !cfq_cfqq_sync(cfqq))
		return false;
	//  max_dispatch    cfq_quantum,    cfqq       dispatch
	//cfq_quantum   
	max_dispatch = cfqd->cfq_quantum;

	//  cfqq      idle，        dispatch    
	if (cfq_class_idle(cfqq))
		max_dispatch = 1;

	/*
	 * Does this cfqq already have too much IO in flight?
	 */
	 //              
	if (cfqq->dispatched >= max_dispatch) {
		/*
		 * idle queue must always only have a single IO in flight
		 */
		if (cfq_class_idle(cfqq))//   idle   ，       
			return false;

		/*
		 * We have other queues, don't allow more IO from this one
		 */
		if (cfqd->busy_queues > 1)//               ，      
			return false;

		/*
		 * Sole queue user, allow bigger slice
		 */
		 //  service_tree      ，      idle，   max_dispatch   
		max_dispatch *= 4;
	}

	/*
	 * Async queues must wait a bit before being allowed dispatch.
	 * We also ramp up the dispatch depth gradually for async IO,
	 * based on the last sync IO we serviced
	 */
	 /*                                  ，   
	   depth，  depth  max_dispatch，                   
	           ，           */
	if (!cfq_cfqq_sync(cfqq) && cfqd->cfq_latency) {
		unsigned long last_sync = jiffies - cfqd->last_end_sync_rq;
		unsigned int depth;

		depth = last_sync / cfqd->cfq_slice[1];
		if (!depth && !cfqq->dispatched)
			depth = 1;
		if (depth < max_dispatch)
			max_dispatch = depth;
	}

	/*
	 * If we're below the current max, allow a dispatch
	 */
	return cfqq->dispatched < max_dispatch;
}

チェック後、requestの選択を正式に開始します.fifoの最初のリクエストの期限が切れた場合、リクエストを選択します.そうでなければnext_を選択します.rqポインタは、物理セクタの連続性から常に考慮される要求を指す要求を指定する.最後にcfq_を呼び出すdispatch_Insert()関数requestをrequest_に挿入Queueでは、ブロックデバイスの応答を待つ

static void cfq_dispatch_insert(struct request_queue *q, struct request *rq)
{
	struct cfq_data *cfqd = q->elevator->elevator_data;
	struct cfq_queue *cfqq = RQ_CFQQ(rq);

	cfq_log_cfqq(cfqd, cfqq, "dispatch_insert");

	cfqq->next_rq = cfq_find_next_rq(cfqd, cfqq, rq);//               next_rq          
	cfq_remove_request(rq);// rq sort_list fifo   
	cfqq->dispatched++;
	elv_dispatch_sort(q, rq);// rq   request queue         

	if (cfq_cfqq_sync(cfqq))
		cfqd->sync_flight++;
}