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

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

File: block/as-iosched.c
Instrumentation mode: function-decision-multicondition
TER: 67 % (566/843)

Start/	End/
True	False	-	Line	Source
			1	/*
			2	*  Anticipatory & deadline i/o scheduler.
			3	*
			4	*  Copyright (C) 2002 Jens Axboe <axboe@suse.de>
			5	*                     Nick Piggin <nickpiggin@yahoo.com.au>
			6	*
			7	*/
			8	#include <linux/kernel.h>
			9	#include <linux/fs.h>
			10	#include <linux/blkdev.h>
			11	#include <linux/elevator.h>
			12	#include <linux/bio.h>
			13	#include <linux/config.h>
			14	#include <linux/module.h>
			15	#include <linux/slab.h>
			16	#include <linux/init.h>
			17	#include <linux/compiler.h>
			18	#include <linux/hash.h>
			19	#include <linux/rbtree.h>
			20	#include <linux/interrupt.h>
			21
			22	#define REQ_SYNC   1
			23	#define REQ_ASYNC   0
			24
			25	/*
			26	* See Documentation/block/as-iosched.txt
			27	*/
			28
			29	/*
			30	* max time before a read is submitted.
			31	*/
			32	#define default_read_expire (HZ / 8)
			33
			34	/*
			35	* ditto for writes, these limits are not hard, even
			36	* if the disk is capable of satisfying them.
			37	*/
			38	#define default_write_expire (HZ / 4)
			39
			40	/*
			41	* read_batch_expire describes how long we will allow a stream of reads to
			42	* persist before looking to see whether it is time to switch over to writes.
			43	*/
			44	#define default_read_batch_expire (HZ / 2)
			45
			46	/*
			47	* write_batch_expire describes how long we want a stream of writes to run for.
			48	* This is not a hard limit, but a target we set for the auto-tuning thingy.
			49	* See, the problem is: we can send a lot of writes to disk cache / TCQ in
			50	* a short amount of time...
			51	*/
			52	#define default_write_batch_expire (HZ / 8)
			53
			54	/*
			55	* max time we may wait to anticipate a read (default around 6ms)
			56	*/
			57	#define default_antic_expire ((HZ / 150) ? HZ / 150 : 1)
			58
			59	/*
			60	* Keep track of up to 20ms thinktimes. We can go as big as we like here,
			61	* however huge values tend to interfere and not decay fast enough. A program
			62	* might be in a non-io phase of operation. Waiting on user input for example,
			63	* or doing a lengthy computation. A small penalty can be justified there, and
			64	* will still catch out those processes that constantly have large thinktimes.
			65	*/
			66	#define MAX_THINKTIME (HZ/50UL)
			67
			68	/* Bits in as_io_context.state */
			69	enum as_io_states {
			70	AS_TASK_RUNNING=0,   /* Process has not exited */
			71	AS_TASK_IOSTARTED,   /* Process has started some IO */
			72	AS_TASK_IORUNNING,   /* Process has completed some IO */
			73	};
			74
			75	enum anticipation_status {
			76	ANTIC_OFF=0,      /* Not anticipating (normal operation)   */
			77	ANTIC_WAIT_REQ,      /* The last read has not yet completed  */
			78	ANTIC_WAIT_NEXT,   /* Currently anticipating a request vs
			79	last read (which has completed) */
			80	ANTIC_FINISHED,      /* Anticipating but have found a candidate
			81	* or timed out */
			82	};
			83
			84	struct as_data {
			85	/*
			86	* run time data
			87	*/
			88
			89	struct request_queue *q;   /* the "owner" queue */
			90
			91	/*
			92	* requests (as_rq s) are present on both sort_list and fifo_list
			93	*/
			94	struct rb_root sort_list[2];
			95	struct list_head fifo_list[2];
			96
			97	struct as_rq *next_arq[2];   /* next in sort order */
			98	sector_t last_sector[2];   /* last REQ_SYNC & REQ_ASYNC sectors */
			99	struct list_head *hash;      /* request hash */
			100
			101	unsigned long exit_prob;   /* probability a task will exit while
			102	being waited on */
			103	unsigned long exit_no_coop;   /* probablility an exited task will
			104	not be part of a later cooperating
			105	request */
			106	unsigned long new_ttime_total;    /* mean thinktime on new proc */
			107	unsigned long new_ttime_mean;
			108	u64 new_seek_total;      /* mean seek on new proc */
			109	sector_t new_seek_mean;
			110
			111	unsigned long current_batch_expires;
			112	unsigned long last_check_fifo[2];
			113	int changed_batch;      /* 1: waiting for old batch to end */
			114	int new_batch;         /* 1: waiting on first read complete */
			115	int batch_data_dir;      /* current batch REQ_SYNC / REQ_ASYNC */
			116	int write_batch_count;      /* max # of reqs in a write batch */
			117	int current_write_count;   /* how many requests left this batch */
			118	int write_batch_idled;      /* has the write batch gone idle? */
			119	mempool_t *arq_pool;
			120
			121	enum anticipation_status antic_status;
			122	unsigned long antic_start;   /* jiffies: when it started */
			123	struct timer_list antic_timer;   /* anticipatory scheduling timer */
			124	struct work_struct antic_work;   /* Deferred unplugging */
			125	struct io_context *io_context;   /* Identify the expected process */
			126	int ioc_finished; /* IO associated with io_context is finished */
			127	int nr_dispatched;
			128
			129	/*
			130	* settings that change how the i/o scheduler behaves
			131	*/
			132	unsigned long fifo_expire[2];
			133	unsigned long batch_expire[2];
			134	unsigned long antic_expire;
			135	};
			136
			137	#define list_entry_fifo(ptr)   list_entry((ptr), struct as_rq, fifo)
			138
			139	/*
			140	* per-request data.
			141	*/
			142	enum arq_state {
			143	AS_RQ_NEW=0,      /* New - not referenced and not on any lists */
			144	AS_RQ_QUEUED,      /* In the request queue. It belongs to the
			145	scheduler */
			146	AS_RQ_DISPATCHED,   /* On the dispatch list. It belongs to the
			147	driver now */
			148	AS_RQ_PRESCHED,      /* Debug poisoning for requests being used */
			149	AS_RQ_REMOVED,
			150	AS_RQ_MERGED,
			151	AS_RQ_POSTSCHED,   /* when they shouldn't be */
			152	};
			153
			154	struct as_rq {
			155	/*
			156	* rbtree index, key is the starting offset
			157	*/
			158	struct rb_node rb_node;
			159	sector_t rb_key;
			160
			161	struct request *request;
			162
			163	struct io_context *io_context;   /* The submitting task */
			164
			165	/*
			166	* request hash, key is the ending offset (for back merge lookup)
			167	*/
			168	struct list_head hash;
			169	unsigned int on_hash;
			170
			171	/*
			172	* expire fifo
			173	*/
			174	struct list_head fifo;
			175	unsigned long expires;
			176
			177	unsigned int is_sync;
			178	enum arq_state state;
			179	};
			180
			181	#define RQ_DATA(rq)   ((struct as_rq *) (rq)->elevator_private)
			182
			183	static kmem_cache_t *arq_pool;
			184
			185	static void as_move_to_dispatch(struct as_data *ad, struct as_rq *arq);
			186	static void as_antic_stop(struct as_data *ad);
			187
			188	/*
			189	* IO Context helper functions
			190	*/
			191
			192	/* Called to deallocate the as_io_context */
5515	5515		193	static void free_as_io_context(struct as_io_context *aic)
			194	{
			195	kfree(aic);
			196	}
			197
			198	/* Called when the task exits */
5515	5515		199	static void exit_as_io_context(struct as_io_context *aic)
			200	{
			201	WARN_ON(!test_bit(AS_TASK_RUNNING, &aic->state));
0	5515	-	201	if (__builtin_expect ( ! ! ( ( ! ( __builtin..
5515	0	-	201	ternary-?: __builtin_constant_p ( AS_TASK_RU..
0	5515	-	201	do-while (0)
			202	clear_bit(AS_TASK_RUNNING, &aic->state);
			203	}
			204
5688	0		205	static struct as_io_context *alloc_as_io_context(void)
			206	{
			207	struct as_io_context *ret;
			208
			209	ret = kmalloc(sizeof(*ret), GFP_ATOMIC);
5688	0	-	210	if (ret) {
			211	ret->dtor = free_as_io_context;
			212	ret->exit = exit_as_io_context;
			213	ret->state = 1 << AS_TASK_RUNNING;
			214	atomic_set(&ret->nr_queued, 0);
			215	atomic_set(&ret->nr_dispatched, 0);
			216	spin_lock_init(&ret->lock);
0	5688	-	216	do-while (0)
			217	ret->ttime_total = 0;
			218	ret->ttime_samples = 0;
			219	ret->ttime_mean = 0;
			220	ret->seek_total = 0;
			221	ret->seek_samples = 0;
			222	ret->seek_mean = 0;
			223	}
			224
5688			225	return ret;
			226	}
			227
			228	/*
			229	* If the current task has no AS IO context then create one and initialise it.
			230	* Then take a ref on the task's io context and return it.
			231	*/
1789E3	0		232	static struct io_context *as_get_io_context(void)
			233	{
			234	struct io_context *ioc = get_io_context(GFP_ATOMIC);
5688	1783E3		235	if (ioc && !ioc->aic) {
5688			235	T && T
	1783E3		235	T && F
	0	-	235	F && _
			236	ioc->aic = alloc_as_io_context();
0	5688	-	237	if (!ioc->aic) {
			238	put_io_context(ioc);
			239	ioc = NULL;
			240	}
			241	}
1789E3			242	return ioc;
			243	}
			244
1729E3	1729E3		245	static void as_put_io_context(struct as_rq *arq)
			246	{
			247	struct as_io_context *aic;
			248
0	1729E3	-	249	if (unlikely(!arq->io_context))
0		-	250	return;
			251
			252	aic = arq->io_context->aic;
			253
1178E3	551210		254	if (arq->is_sync == REQ_SYNC && aic) {
1178E3			254	T && T
	0	-	254	T && F
	551210		254	F && _
			255	spin_lock(&aic->lock);
			255	do
0	1178E3	-	255	do-while (0)
0	1178E3	-	255	do-while (0)
			256	set_bit(AS_TASK_IORUNNING, &aic->state);
			257	aic->last_end_request = jiffies;
			258	spin_unlock(&aic->lock);
			258	do
0	1178E3	-	258	do-while (0)
0	1178E3	-	258	do-while (0)
			259	}
			260
			261	put_io_context(arq->io_context);
			262	}
			263
			264	/*
			265	* the back merge hash support functions
			266	*/
			267	static const int as_hash_shift = 6;
			268	#define AS_HASH_BLOCK(sec)   ((sec) >> 3)
			269	#define AS_HASH_FN(sec)      (hash_long(AS_HASH_BLOCK((sec)), as_hash_shift))
			270	#define AS_HASH_ENTRIES      (1 << as_hash_shift)
			271	#define rq_hash_key(rq)      ((rq)->sector + (rq)->nr_sectors)
			272	#define list_entry_hash(ptr)   list_entry((ptr), struct as_rq, hash)
			273
4855E3	4855E3		274	static inline void __as_del_arq_hash(struct as_rq *arq)
			275	{
			276	arq->on_hash = 0;
			277	list_del_init(&arq->hash);
			278	}
			279
4857E3	4857E3		280	static inline void as_del_arq_hash(struct as_rq *arq)
			281	{
4855E3	1665		282	if (arq->on_hash)
			283	__as_del_arq_hash(arq);
			284	}
			285
4855E3	4855E3		286	static void as_add_arq_hash(struct as_data *ad, struct as_rq *arq)
			287	{
			288	struct request *rq = arq->request;
			289
			290	BUG_ON(arq->on_hash);
0	4855E3	-	290	if (__builtin_expect ( ! ! ( ( arq -> on_has..
0	4855E3	-	290	do-while (0)
			291
			292	arq->on_hash = 1;
			293	list_add(&arq->hash, &ad->hash[AS_HASH_FN(rq_hash_key(rq))]);
			294	}
			295
			296	/*
			297	* move hot entry to front of chain
			298	*/
275452	275452		299	static inline void as_hot_arq_hash(struct as_data *ad, struct as_rq *arq)
			300	{
			301	struct request *rq = arq->request;
			302	struct list_head *head = &ad->hash[AS_HASH_FN(rq_hash_key(rq))];
			303
0	275452	-	304	if (!arq->on_hash) {
			305	WARN_ON(1);
0	0	-	305	if (__builtin_expect ( ! ! ( ( 1 ) != 0 ) ..
0	0	-	305	do-while (0)
0		-	306	return;
			307	}
			308
6056	269396		309	if (arq->hash.prev != head) {
			310	list_del(&arq->hash);
			311	list_add(&arq->hash, head);
			312	}
			313	}
			314
1148E3	0		315	static struct request *as_find_arq_hash(struct as_data *ad, sector_t offset)
			316	{
			317	struct list_head *hash_list = &ad->hash[AS_HASH_FN(offset)];
			318	struct list_head *entry, *next = hash_list->next;
			319
813554	879474		320	while ((entry = next) != hash_list) {
			321	struct as_rq *arq = list_entry_hash(entry);
			322	struct request *__rq = arq->request;
			323
			324	next = entry->next;
			325
			326	BUG_ON(!arq->on_hash);
0	813554	-	326	if (__builtin_expect ( ! ! ( ( ! arq -> on..
0	813554	-	326	do-while (0)
			327
1665	811889		328	if (!rq_mergeable(__rq)) {
1665			328	!(!(T) && (_))
0		-	328	!(!(F) && (F))
	811889		328	!(!(F) && (T))
			329	as_del_arq_hash(arq);
1665			330	continue;
			331	}
			332
269030	542859		333	if (rq_hash_key(__rq) == offset)
269030			334	return __rq;
			335	}
			336
879474			337	return NULL;
			338	}
			339
			340	/*
			341	* rb tree support functions
			342	*/
			343	#define RB_NONE      (2)
			344	#define RB_EMPTY(root)   ((root)->rb_node == NULL)
			345	#define ON_RB(node)   ((node)->rb_color != RB_NONE)
			346	#define RB_CLEAR(node)   ((node)->rb_color = RB_NONE)
			347	#define rb_entry_arq(node)   rb_entry((node), struct as_rq, rb_node)
			348	#define ARQ_RB_ROOT(ad, arq)   (&(ad)->sort_list[(arq)->is_sync])
			349	#define rq_rb_key(rq)      (rq)->sector
			350
			351	/*
			352	* as_find_first_arq finds the first (lowest sector numbered) request
			353	* for the specified data_dir. Used to sweep back to the start of the disk
			354	* (1-way elevator) after we process the last (highest sector) request.
			355	*/
1008E3	0		356	static struct as_rq *as_find_first_arq(struct as_data *ad, int data_dir)
			357	{
			358	struct rb_node *n = ad->sort_list[data_dir].rb_node;
			359
0	1008E3	-	360	if (n == NULL)
0		-	361	return NULL;
			362
1166E3	0	-	363	for (;;) {
1008E3	158156		364	if (n->rb_left == NULL)
1008E3			365	return rb_entry_arq(n);
			366
			367	n = n->rb_left;
			368	}
			369	}
			370
			371	/*
			372	* Add the request to the rb tree if it is unique.  If there is an alias (an
			373	* existing request against the same sector), which can happen when using
			374	* direct IO, then return the alias.
			375	*/
1739E3	0		376	static struct as_rq *__as_add_arq_rb(struct as_data *ad, struct as_rq *arq)
			377	{
			378	struct rb_node **p = &ARQ_RB_ROOT(ad, arq)->rb_node;
			379	struct rb_node *parent = NULL;
			380	struct as_rq *__arq;
			381	struct request *rq = arq->request;
			382
			383	arq->rb_key = rq_rb_key(rq);
			384
4350E3	1739E3		385	while (*p) {
			386	parent = *p;
			387	__arq = rb_entry_arq(parent);
			388
697467	3652E3		389	if (arq->rb_key < __arq->rb_key)
			390	p = &(*p)->rb_left;
3652E3	0	-	391	else if (arq->rb_key > __arq->rb_key)
			392	p = &(*p)->rb_right;
			393	else
0		-	394	return __arq;
			395	}
			396
			397	rb_link_node(&arq->rb_node, parent, p);
			398	rb_insert_color(&arq->rb_node, ARQ_RB_ROOT(ad, arq));
			399
1739E3			400	return NULL;
			401	}
			402
1739E3	1739E3		403	static void as_add_arq_rb(struct as_data *ad, struct as_rq *arq)
			404	{
			405	struct as_rq *alias;
			406
0	1739E3	-	407	while ((unlikely(alias = __as_add_arq_rb(ad, arq)))) {
			408	as_move_to_dispatch(ad, alias);
			409	as_antic_stop(ad);
			410	}
			411	}
			412
1739E3	1739E3		413	static inline void as_del_arq_rb(struct as_data *ad, struct as_rq *arq)
			414	{
0	1739E3	-	415	if (!ON_RB(&arq->rb_node)) {
			416	WARN_ON(1);
0	0	-	416	if (__builtin_expect ( ! ! ( ( 1 ) != 0 ) ..
0	0	-	416	do-while (0)
0		-	417	return;
			418	}
			419
			420	rb_erase(&arq->rb_node, ARQ_RB_ROOT(ad, arq));
			421	RB_CLEAR(&arq->rb_node);
			422	}
			423
			424	static struct request *
879539	0		425	as_find_arq_rb(struct as_data *ad, sector_t sector, int data_dir)
			426	{
			427	struct rb_node *n = ad->sort_list[data_dir].rb_node;
			428	struct as_rq *arq;
			429
657243	873037		430	while (n) {
			431	arq = rb_entry_arq(n);
			432
219588	437655		433	if (sector < arq->rb_key)
			434	n = n->rb_left;
431153	6502		435	else if (sector > arq->rb_key)
			436	n = n->rb_right;
			437	else
6502			438	return arq->request;
			439	}
			440
873037			441	return NULL;
			442	}
			443
			444	/*
			445	* IO Scheduler proper
			446	*/
			447
			448	#define MAXBACK (1024 * 1024)   /*
			449	* Maximum distance the disk will go backward
			450	* for a request.
			451	*/
			452
			453	#define BACK_PENALTY   2
			454
			455	/*
			456	* as_choose_req selects the preferred one of two requests of the same data_dir
			457	* ignoring time - eg. timeouts, which is the job of as_dispatch_request
			458	*/
			459	static struct as_rq *
3442E3	0		460	as_choose_req(struct as_data *ad, struct as_rq *arq1, struct as_rq *arq2)
			461	{
			462	int data_dir;
			463	sector_t last, s1, s2, d1, d2;
			464	int r1_wrap=0, r2_wrap=0;   /* requests are behind the disk head */
			465	const sector_t maxback = MAXBACK;
			466
944140	2498E3		467	if (arq1 == NULL || arq1 == arq2)
914149			467	T || _
29991			467	F || T
	2498E3		467	F || F
944140			468	return arq2;
1365E3	1132E3		469	if (arq2 == NULL)
1365E3			470	return arq1;
			471
			472	data_dir = arq1->is_sync;
			473
			474	last = ad->last_sector[data_dir];
			475	s1 = arq1->request->sector;
			476	s2 = arq2->request->sector;
			477
			478	BUG_ON(data_dir != arq2->is_sync);
0	1132E3	-	478	if (__builtin_expect ( ! ! ( ( data_dir != a..
0	1132E3	-	478	do-while (0)
			479
			480	/*
			481	* Strict one way elevator _except_ in the case where we allow
			482	* short backward seeks which are biased as twice the cost of a
			483	* similar forward seek.
			484	*/
865215	266892		485	if (s1 >= last)
			486	d1 = s1 - last;
176958	89934		487	else if (s1+maxback >= last)
			488	d1 = (last - s1)*BACK_PENALTY;
			489	else {
			490	r1_wrap = 1;
			491	d1 = 0; /* shut up, gcc */
			492	}
			493
640766	491341		494	if (s2 >= last)
			495	d2 = s2 - last;
347772	143569		496	else if (s2+maxback >= last)
			497	d2 = (last - s2)*BACK_PENALTY;
			498	else {
			499	r2_wrap = 1;
			500	d2 = 0;
			501	}
			502
			503	/* Found required data */
114206	1017E3		504	if (!r1_wrap && r2_wrap)
114206			504	T && T
	927967		504	T && F
	89934		504	F && _
114206			505	return arq1;
60571	957330		506	else if (!r2_wrap && r1_wrap)
60571			506	T && T
	927967		506	T && F
	29363		506	F && _
60571			507	return arq2;
29363	927967		508	else if (r1_wrap && r2_wrap) {
29363			508	T && T
	0	-	508	T && F
	927967		508	F && _
			509	/* both behind the head */
8260	21103		510	if (s1 <= s2)
8260			511	return arq1;
			512	else
21103			513	return arq2;
			514	}
			515
			516	/* Both requests in front of the head */
189713	738254		517	if (d1 < d2)
189713			518	return arq1;
738090	164		519	else if (d2 < d1)
738090			520