CTC++ Coverage Report - Execution Profile    #94/1532

Files Summary | Functions Summary | Execution Profile | Index | No Index
First | Previous | Next | Last

File: block/cfq-iosched.c
Instrumentation mode: function-decision-multicondition
TER: 1 % ( 11/1118)

Start/	End/
True	False	-	Line	Source
			1	/*
			2	*  CFQ, or complete fairness queueing, disk scheduler.
			3	*
			4	*  Based on ideas from a previously unfinished io
			5	*  scheduler (round robin per-process disk scheduling) and Andrea Arcangeli.
			6	*
			7	*  Copyright (C) 2003 Jens Axboe <axboe@suse.de>
			8	*/
			9	#include <linux/kernel.h>
			10	#include <linux/fs.h>
			11	#include <linux/blkdev.h>
			12	#include <linux/elevator.h>
			13	#include <linux/bio.h>
			14	#include <linux/config.h>
			15	#include <linux/module.h>
			16	#include <linux/slab.h>
			17	#include <linux/init.h>
			18	#include <linux/compiler.h>
			19	#include <linux/hash.h>
			20	#include <linux/rbtree.h>
			21	#include <linux/mempool.h>
			22	#include <linux/ioprio.h>
			23	#include <linux/writeback.h>
			24
			25	/*
			26	* tunables
			27	*/
			28	static const int cfq_quantum = 4;      /* max queue in one round of service */
			29	static const int cfq_queued = 8;      /* minimum rq allocate limit per-queue*/
			30	static const int cfq_fifo_expire[2] = { HZ / 4, HZ / 8 };
			31	static const int cfq_back_max = 16 * 1024;   /* maximum backwards seek, in KiB */
			32	static const int cfq_back_penalty = 2;      /* penalty of a backwards seek */
			33
			34	static const int cfq_slice_sync = HZ / 10;
			35	static int cfq_slice_async = HZ / 25;
			36	static const int cfq_slice_async_rq = 2;
			37	static int cfq_slice_idle = HZ / 100;
			38
			39	#define CFQ_IDLE_GRACE      (HZ / 10)
			40	#define CFQ_SLICE_SCALE      (5)
			41
			42	#define CFQ_KEY_ASYNC      (0)
			43	#define CFQ_KEY_ANY      (0xffff)
			44
			45	/*
			46	* disable queueing at the driver/hardware level
			47	*/
			48	static const int cfq_max_depth = 2;
			49
			50	/*
			51	* for the hash of cfqq inside the cfqd
			52	*/
			53	#define CFQ_QHASH_SHIFT      6
			54	#define CFQ_QHASH_ENTRIES   (1 << CFQ_QHASH_SHIFT)
			55	#define list_entry_qhash(entry)   hlist_entry((entry), struct cfq_queue, cfq_hash)
			56
			57	/*
			58	* for the hash of crq inside the cfqq
			59	*/
			60	#define CFQ_MHASH_SHIFT      6
			61	#define CFQ_MHASH_BLOCK(sec)   ((sec) >> 3)
			62	#define CFQ_MHASH_ENTRIES   (1 << CFQ_MHASH_SHIFT)
			63	#define CFQ_MHASH_FN(sec)   hash_long(CFQ_MHASH_BLOCK(sec), CFQ_MHASH_SHIFT)
			64	#define rq_hash_key(rq)      ((rq)->sector + (rq)->nr_sectors)
			65	#define list_entry_hash(ptr)   hlist_entry((ptr), struct cfq_rq, hash)
			66
			67	#define list_entry_cfqq(ptr)   list_entry((ptr), struct cfq_queue, cfq_list)
			68	#define list_entry_fifo(ptr)   list_entry((ptr), struct request, queuelist)
			69
			70	#define RQ_DATA(rq)      (rq)->elevator_private
			71
			72	/*
			73	* rb-tree defines
			74	*/
			75	#define RB_NONE         (2)
			76	#define RB_EMPTY(node)      ((node)->rb_node == NULL)
			77	#define RB_CLEAR_COLOR(node)   (node)->rb_color = RB_NONE
			78	#define RB_CLEAR(node)      do {   \
			79	(node)->rb_parent = NULL;   \
			80	RB_CLEAR_COLOR((node));      \
			81	(node)->rb_right = NULL;   \
			82	(node)->rb_left = NULL;      \
			83	} while (0)
			84	#define RB_CLEAR_ROOT(root)   ((root)->rb_node = NULL)
			85	#define rb_entry_crq(node)   rb_entry((node), struct cfq_rq, rb_node)
			86	#define rq_rb_key(rq)      (rq)->sector
			87
			88	static kmem_cache_t *crq_pool;
			89	static kmem_cache_t *cfq_pool;
			90	static kmem_cache_t *cfq_ioc_pool;
			91
			92	#define CFQ_PRIO_LISTS      IOPRIO_BE_NR
			93	#define cfq_class_idle(cfqq)   ((cfqq)->ioprio_class == IOPRIO_CLASS_IDLE)
			94	#define cfq_class_be(cfqq)   ((cfqq)->ioprio_class == IOPRIO_CLASS_BE)
			95	#define cfq_class_rt(cfqq)   ((cfqq)->ioprio_class == IOPRIO_CLASS_RT)
			96
			97	#define ASYNC         (0)
			98	#define SYNC         (1)
			99
			100	#define cfq_cfqq_dispatched(cfqq)   \
			101	((cfqq)->on_dispatch[ASYNC] + (cfqq)->on_dispatch[SYNC])
			102
			103	#define cfq_cfqq_class_sync(cfqq)   ((cfqq)->key != CFQ_KEY_ASYNC)
			104
			105	#define cfq_cfqq_sync(cfqq)      \
			106	(cfq_cfqq_class_sync(cfqq) || (cfqq)->on_dispatch[SYNC])
			107
			108	/*
			109	* Per block device queue structure
			110	*/
			111	struct cfq_data {
			112	atomic_t ref;
			113	request_queue_t *queue;
			114
			115	/*
			116	* rr list of queues with requests and the count of them
			117	*/
			118	struct list_head rr_list[CFQ_PRIO_LISTS];
			119	struct list_head busy_rr;
			120	struct list_head cur_rr;
			121	struct list_head idle_rr;
			122	unsigned int busy_queues;
			123
			124	/*
			125	* non-ordered list of empty cfqq's
			126	*/
			127	struct list_head empty_list;
			128
			129	/*
			130	* cfqq lookup hash
			131	*/
			132	struct hlist_head *cfq_hash;
			133
			134	/*
			135	* global crq hash for all queues
			136	*/
			137	struct hlist_head *crq_hash;
			138
			139	unsigned int max_queued;
			140
			141	mempool_t *crq_pool;
			142
			143	int rq_in_driver;
			144
			145	/*
			146	* schedule slice state info
			147	*/
			148	/*
			149	* idle window management
			150	*/
			151	struct timer_list idle_slice_timer;
			152	struct work_struct unplug_work;
			153
			154	struct cfq_queue *active_queue;
			155	struct cfq_io_context *active_cic;
			156	int cur_prio, cur_end_prio;
			157	unsigned int dispatch_slice;
			158
			159	struct timer_list idle_class_timer;
			160
			161	sector_t last_sector;
			162	unsigned long last_end_request;
			163
			164	unsigned int rq_starved;
			165
			166	/*
			167	* tunables, see top of file
			168	*/
			169	unsigned int cfq_quantum;
			170	unsigned int cfq_queued;
			171	unsigned int cfq_fifo_expire[2];
			172	unsigned int cfq_back_penalty;
			173	unsigned int cfq_back_max;
			174	unsigned int cfq_slice[2];
			175	unsigned int cfq_slice_async_rq;
			176	unsigned int cfq_slice_idle;
			177	unsigned int cfq_max_depth;
			178	};
			179
			180	/*
			181	* Per process-grouping structure
			182	*/
			183	struct cfq_queue {
			184	/* reference count */
			185	atomic_t ref;
			186	/* parent cfq_data */
			187	struct cfq_data *cfqd;
			188	/* cfqq lookup hash */
			189	struct hlist_node cfq_hash;
			190	/* hash key */
			191	unsigned int key;
			192	/* on either rr or empty list of cfqd */
			193	struct list_head cfq_list;
			194	/* sorted list of pending requests */
			195	struct rb_root sort_list;
			196	/* if fifo isn't expired, next request to serve */
			197	struct cfq_rq *next_crq;
			198	/* requests queued in sort_list */
			199	int queued[2];
			200	/* currently allocated requests */
			201	int allocated[2];
			202	/* fifo list of requests in sort_list */
			203	struct list_head fifo;
			204
			205	unsigned long slice_start;
			206	unsigned long slice_end;
			207	unsigned long slice_left;
			208	unsigned long service_last;
			209
			210	/* number of requests that are on the dispatch list */
			211	int on_dispatch[2];
			212
			213	/* io prio of this group */
			214	unsigned short ioprio, org_ioprio;
			215	unsigned short ioprio_class, org_ioprio_class;
			216
			217	/* various state flags, see below */
			218	unsigned int flags;
			219	};
			220
			221	struct cfq_rq {
			222	struct rb_node rb_node;
			223	sector_t rb_key;
			224	struct request *request;
			225	struct hlist_node hash;
			226
			227	struct cfq_queue *cfq_queue;
			228	struct cfq_io_context *io_context;
			229
			230	unsigned int crq_flags;
			231	};
			232
			233	enum cfqq_state_flags {
			234	CFQ_CFQQ_FLAG_on_rr = 0,
			235	CFQ_CFQQ_FLAG_wait_request,
			236	CFQ_CFQQ_FLAG_must_alloc,
			237	CFQ_CFQQ_FLAG_must_alloc_slice,
			238	CFQ_CFQQ_FLAG_must_dispatch,
			239	CFQ_CFQQ_FLAG_fifo_expire,
			240	CFQ_CFQQ_FLAG_idle_window,
			241	CFQ_CFQQ_FLAG_prio_changed,
			242	};
			243
			244	#define CFQ_CFQQ_FNS(name)                  \
			245	static inline void cfq_mark_cfqq_##name(struct cfq_queue *cfqq)      \
			246	{                           \
			247	cfqq->flags |= (1 << CFQ_CFQQ_FLAG_##name);         \
			248	}                           \
			249	static inline void cfq_clear_cfqq_##name(struct cfq_queue *cfqq)   \
			250	{                           \
			251	cfqq->flags &= ~(1 << CFQ_CFQQ_FLAG_##name);         \
			252	}                           \
			253	static inline int cfq_cfqq_##name(const struct cfq_queue *cfqq)      \
			254	{                           \
			255	return (cfqq->flags & (1 << CFQ_CFQQ_FLAG_##name)) != 0;   \
			256	}
			257
0	0	-	258	CFQ_CFQQ_FNS(on_rr);
0	0	-	258	FUNCTION cfq_clear_cfqq_on_rr()
0	0	-	258	FUNCTION cfq_cfqq_on_rr()
0		-	258	return ( cfqq -> flags & ( 1 << CFQ_CFQQ_FLAG_..
0	0	-	259	CFQ_CFQQ_FNS(wait_request);
0	0	-	259	FUNCTION cfq_clear_cfqq_wait_request()
0	0	-	259	FUNCTION cfq_cfqq_wait_request()
0		-	259	return ( cfqq -> flags & ( 1 << CFQ_CFQQ_FLAG_..
0	0	-	260	CFQ_CFQQ_FNS(must_alloc);
0	0	-	260	FUNCTION cfq_clear_cfqq_must_alloc()
0	0	-	260	FUNCTION cfq_cfqq_must_alloc()
0		-	260	return ( cfqq -> flags & ( 1 << CFQ_CFQQ_FLAG_..
0	0	-	261	CFQ_CFQQ_FNS(must_alloc_slice);
0	0	-	261	FUNCTION cfq_clear_cfqq_must_alloc_slice()
0	0	-	261	FUNCTION cfq_cfqq_must_alloc_slice()
0		-	261	return ( cfqq -> flags & ( 1 << CFQ_CFQQ_FLAG_..
0	0	-	262	CFQ_CFQQ_FNS(must_dispatch);
0	0	-	262	FUNCTION cfq_clear_cfqq_must_dispatch()
0	0	-	262	FUNCTION cfq_cfqq_must_dispatch()
0		-	262	return ( cfqq -> flags & ( 1 << CFQ_CFQQ_FLAG_..
0	0	-	263	CFQ_CFQQ_FNS(fifo_expire);
0	0	-	263	FUNCTION cfq_clear_cfqq_fifo_expire()
0	0	-	263	FUNCTION cfq_cfqq_fifo_expire()
0		-	263	return ( cfqq -> flags & ( 1 << CFQ_CFQQ_FLAG_..
0	0	-	264	CFQ_CFQQ_FNS(idle_window);
0	0	-	264	FUNCTION cfq_clear_cfqq_idle_window()
0	0	-	264	FUNCTION cfq_cfqq_idle_window()
0		-	264	return ( cfqq -> flags & ( 1 << CFQ_CFQQ_FLAG_..
0	0	-	265	CFQ_CFQQ_FNS(prio_changed);
0	0	-	265	FUNCTION cfq_clear_cfqq_prio_changed()
0	0	-	265	FUNCTION cfq_cfqq_prio_changed()
0		-	265	return ( cfqq -> flags & ( 1 << CFQ_CFQQ_FLAG_..
			266	#undef CFQ_CFQQ_FNS
			267
			268	enum cfq_rq_state_flags {
			269	CFQ_CRQ_FLAG_is_sync = 0,
			270	};
			271
			272	#define CFQ_CRQ_FNS(name)                  \
			273	static inline void cfq_mark_crq_##name(struct cfq_rq *crq)      \
			274	{                           \
			275	crq->crq_flags |= (1 << CFQ_CRQ_FLAG_##name);         \
			276	}                           \
			277	static inline void cfq_clear_crq_##name(struct cfq_rq *crq)      \
			278	{                           \
			279	crq->crq_flags &= ~(1 << CFQ_CRQ_FLAG_##name);         \
			280	}                           \
			281	static inline int cfq_crq_##name(const struct cfq_rq *crq)      \
			282	{                           \
			283	return (crq->crq_flags & (1 << CFQ_CRQ_FLAG_##name)) != 0;   \
			284	}
			285
0	0	-	286	CFQ_CRQ_FNS(is_sync);
0	0	-	286	FUNCTION cfq_clear_crq_is_sync()
0	0	-	286	FUNCTION cfq_crq_is_sync()
0		-	286	return ( crq -> crq_flags & ( 1 << CFQ_CRQ_FLA..
			287	#undef CFQ_CRQ_FNS
			288
			289	static struct cfq_queue *cfq_find_cfq_hash(struct cfq_data *, unsigned int, unsigned short);
			290	static void cfq_dispatch_insert(request_queue_t *, struct cfq_rq *);
			291	static void cfq_put_cfqd(struct cfq_data *cfqd);
			292
			293	#define process_sync(tsk)   ((tsk)->flags & PF_SYNCWRITE)
			294
			295	/*
			296	* lots of deadline iosched dupes, can be abstracted later...
			297	*/
0	0	-	298	static inline void cfq_del_crq_hash(struct cfq_rq *crq)
			299	{
			300	hlist_del_init(&crq->hash);
			301	}
			302
0	0	-	303	static inline void cfq_add_crq_hash(struct cfq_data *cfqd, struct cfq_rq *crq)
			304	{
			305	const int hash_idx = CFQ_MHASH_FN(rq_hash_key(crq->request));
			306
			307	hlist_add_head(&crq->hash, &cfqd->crq_hash[hash_idx]);
			308	}
			309
0	0	-	310	static struct request *cfq_find_rq_hash(struct cfq_data *cfqd, sector_t offset)
			311	{
			312	struct hlist_head *hash_list = &cfqd->crq_hash[CFQ_MHASH_FN(offset)];
			313	struct hlist_node *entry, *next;
			314
0	0	-	315	hlist_for_each_safe(entry, next, hash_list) {
0		-	315	T && (T)
	0	-	315	T && (F)
	0	-	315	F && (_)
			316	struct cfq_rq *crq = list_entry_hash(entry);
			317	struct request *__rq = crq->request;
			318
0	0	-	319	if (!rq_mergeable(__rq)) {
0		-	319	!(!(T) && (_))
0		-	319	!(!(F) && (F))
	0	-	319	!(!(F) && (T))
			320	cfq_del_crq_hash(crq);
0		-	321	continue;
			322	}
			323
0	0	-	324	if (rq_hash_key(__rq) == offset)
0		-	325	return __rq;
			326	}
			327
0		-	328	return NULL;
			329	}
			330
			331	/*
			332	* scheduler run of queue, if there are requests pending and no one in the
			333	* driver that will restart queueing
			334	*/
0	0	-	335	static inline void cfq_schedule_dispatch(struct cfq_data *cfqd)
			336	{
0	0	-	337	if (cfqd->busy_queues)
			338	kblockd_schedule_work(&cfqd->unplug_work);
			339	}
			340
0	0	-	341	static int cfq_queue_empty(request_queue_t *q)
			342	{
			343	struct cfq_data *cfqd = q->elevator->elevator_data;
			344
0		-	345	return !cfqd->busy_queues;
			346	}
			347
			348	/*
			349	* Lifted from AS - choose which of crq1 and crq2 that is best served now.
			350	* We choose the request that is closest to the head right now. Distance
			351	* behind the head are penalized and only allowed to a certain extent.
			352	*/
			353	static struct cfq_rq *
0	0	-	354	cfq_choose_req(struct cfq_data *cfqd, struct cfq_rq *crq1, struct cfq_rq *crq2)
			355	{
			356	sector_t last, s1, s2, d1 = 0, d2 = 0;
			357	int r1_wrap = 0, r2_wrap = 0;   /* requests are behind the disk head */
			358	unsigned long back_max;
			359
0	0	-	360	if (crq1 == NULL || crq1 == crq2)
0		-	360	T || _
0		-	360	F || T
	0	-	360	F || F
0		-	361	return crq2;
0	0	-	362	if (crq2 == NULL)
0		-	363	return crq1;
			364
0	0	-	365	if (cfq_crq_is_sync(crq1) && !cfq_crq_is_sync(crq2))
0		-	365	T && T
	0	-	365	T && F
	0	-	365	F && _
0		-	366	return crq1;
0	0	-	367	else if (cfq_crq_is_sync(crq2) && !cfq_crq_is_sync(crq1))
0		-	367	T && T
	0	-	367	T && F
	0	-	367	F && _
0		-	368	return crq2;
			369
			370	s1 = crq1->request->sector;
			371	s2 = crq2->request->sector;
			372
			373	last = cfqd->last_sector;
			374
			375	/*
			376	* by definition, 1KiB is 2 sectors
			377	*/
			378	back_max = cfqd->cfq_back_max * 2;
			379
			380	/*
			381	* Strict one way elevator _except_ in the case where we allow
			382	* short backward seeks which are biased as twice the cost of a
			383	* similar forward seek.
			384	*/
0	0	-	385	if (s1 >= last)
			386	d1 = s1 - last;
0	0	-	387	else if (s1 + back_max >= last)
			388	d1 = (last - s1) * cfqd->cfq_back_penalty;
			389	else
			390	r1_wrap = 1;
			391
0	0	-	392	if (s2 >= last)
			393	d2 = s2 - last;
0	0	-	394	else if (s2 + back_max >= last)
			395	d2 = (last - s2) * cfqd->cfq_back_penalty;
			396	else
			397	r2_wrap = 1;
			398
			399	/* Found required data */
0	0	-	400	if (!r1_wrap && r2_wrap)
0		-	400	T && T
	0	-	400	T && F
	0	-	400	F && _
0		-	401	return crq1;
0	0	-	402	else if (!r2_wrap && r1_wrap)
0		-	402	T && T
	0	-	402	T && F
	0	-	402	F && _
0		-	403	return crq2;
0	0	-	404	else if (r1_wrap && r2_wrap) {
0		-	404	T && T
	0	-	404	T && F
	0	-	404	F && _
			405	/* both behind the head */
0	0	-	406	if (s1 <= s2)
0		-	407	return crq1;
			408	else
0		-	409	return crq2;
			410	}
			411
			412	/* Both requests in front of the head */
0	0	-	413	if (d1 < d2)
0		-	414	return crq1;
0	0	-	415	else if (d2 < d1)
0		-	416	return crq2;
			417	else {
0	0	-	418	if (s1 >= s2)
0		-	419	return crq1;
			420	else
0		-	421	return crq2;
			422	}
			423	}
			424
			425	/*
			426	* would be nice to take fifo expire time into account as well
			427	*/
			428	static struct cfq_rq *
0	0	-	429	cfq_find_next_crq(struct cfq_data *cfqd, struct cfq_queue *cfqq,
			430	struct cfq_rq *last)
			431	{
			432	struct cfq_rq *crq_next = NULL, *crq_prev = NULL;
			433	struct rb_node *rbnext, *rbprev;
			434
0	0	-	435	if (!(rbnext = rb_next(&last->rb_node))) {
			436	rbnext = rb_first(&cfqq->sort_list);
0	0	-	437	if (rbnext == &last->rb_node)
			438	rbnext = NULL;
			439	}
			440
			441	rbprev = rb_prev(&last->rb_node);
			442
0	0	-	443	if (rbprev)
			444	crq_prev = rb_entry_crq(rbprev);
0	0	-	445	if (rbnext)
			446	crq_next = rb_entry_crq(rbnext);
			447
0		-	448	return cfq_choose_req(cfqd, crq_next, crq_prev);
			449	}
			450
0	0	-	451	static void cfq_update_next_crq(struct cfq_rq *crq)
			452	{
			453	struct cfq_queue *cfqq = crq->cfq_queue;
			454
0	0	-	455	if (cfqq->next_crq == crq)
			456	cfqq->next_crq = cfq_find_next_crq(cfqq->cfqd, cfqq, crq);
			457	}
			458
0	0	-	459	static void cfq_resort_rr_list(struct cfq_queue *cfqq, int preempted)
			460	{
			461	struct cfq_data *cfqd = cfqq->cfqd;
			462	struct list_head *list, *entry;
			463
			464	BUG_ON(!cfq_cfqq_on_rr(cfqq));
0	0	-	464	if (__builtin_expect ( ! ! ( ( ! cfq_cfqq_on..
0	0	-	464	do-while (0)
			465
			466	list_del(&cfqq->cfq_list);
			467
0	0	-	468	if (cfq_class_rt(cfqq))
			469	list = &cfqd->cur_rr;
0	0	-	470	else if (cfq_class_idle(cfqq))
			471	list = &cfqd->idle_rr;
			472	else {
			473	/*
			474	* if cfqq has requests in flight, don't allow it to be
			475	* found in cfq_set_active_queue before it has finished them.
			476	* this is done to increase fairness between a process that
			477	* has lots of io pending vs one that only generates one
			478	* sporadically or synchronously
			479	*/
0	0	-	480	if (cfq_cfqq_dispatched(cfqq))
			481	list = &cfqd->busy_rr;
			482	else
			483	list = &cfqd->rr_list[cfqq->ioprio];
			484	}
			485
			486	/*
			487	* if queue was preempted, just add to front to be fair. busy_rr
			488	* isn't sorted.
			489	*/
0	0	-	490	if (preempted || list == &cfqd->busy_rr) {
0		-	490	T || _
0		-