cfq-iosched.c 53.9 KB
Newer Older
Linus Torvalds's avatar
Linus Torvalds committed
1 2 3 4 5 6 7 8 9
/*
 *  CFQ, or complete fairness queueing, disk scheduler.
 *
 *  Based on ideas from a previously unfinished io
 *  scheduler (round robin per-process disk scheduling) and Andrea Arcangeli.
 *
 *  Copyright (C) 2003 Jens Axboe <axboe@suse.de>
 */
#include <linux/module.h>
Al Viro's avatar
Al Viro committed
10 11
#include <linux/blkdev.h>
#include <linux/elevator.h>
Linus Torvalds's avatar
Linus Torvalds committed
12 13
#include <linux/hash.h>
#include <linux/rbtree.h>
14
#include <linux/ioprio.h>
Linus Torvalds's avatar
Linus Torvalds committed
15 16 17 18

/*
 * tunables
 */
19 20 21 22 23
static const int cfq_quantum = 4;		/* max queue in one round of service */
static const int cfq_queued = 8;		/* minimum rq allocate limit per-queue*/
static const int cfq_fifo_expire[2] = { HZ / 4, HZ / 8 };
static const int cfq_back_max = 16 * 1024;	/* maximum backwards seek, in KiB */
static const int cfq_back_penalty = 2;		/* penalty of a backwards seek */
Linus Torvalds's avatar
Linus Torvalds committed
24

25
static const int cfq_slice_sync = HZ / 10;
Jens Axboe's avatar
Jens Axboe committed
26
static int cfq_slice_async = HZ / 25;
27
static const int cfq_slice_async_rq = 2;
28
static int cfq_slice_idle = HZ / 125;
29 30 31 32 33 34

#define CFQ_IDLE_GRACE		(HZ / 10)
#define CFQ_SLICE_SCALE		(5)

#define CFQ_KEY_ASYNC		(0)

35
static DEFINE_SPINLOCK(cfq_exit_lock);
36

Linus Torvalds's avatar
Linus Torvalds committed
37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
/*
 * for the hash of cfqq inside the cfqd
 */
#define CFQ_QHASH_SHIFT		6
#define CFQ_QHASH_ENTRIES	(1 << CFQ_QHASH_SHIFT)
#define list_entry_qhash(entry)	hlist_entry((entry), struct cfq_queue, cfq_hash)

#define list_entry_cfqq(ptr)	list_entry((ptr), struct cfq_queue, cfq_list)

#define RQ_DATA(rq)		(rq)->elevator_private

static kmem_cache_t *crq_pool;
static kmem_cache_t *cfq_pool;
static kmem_cache_t *cfq_ioc_pool;

52 53 54
static atomic_t ioc_count = ATOMIC_INIT(0);
static struct completion *ioc_gone;

55 56 57 58 59
#define CFQ_PRIO_LISTS		IOPRIO_BE_NR
#define cfq_class_idle(cfqq)	((cfqq)->ioprio_class == IOPRIO_CLASS_IDLE)
#define cfq_class_be(cfqq)	((cfqq)->ioprio_class == IOPRIO_CLASS_BE)
#define cfq_class_rt(cfqq)	((cfqq)->ioprio_class == IOPRIO_CLASS_RT)

Jens Axboe's avatar
Jens Axboe committed
60 61 62 63 64 65 66 67 68 69
#define ASYNC			(0)
#define SYNC			(1)

#define cfq_cfqq_dispatched(cfqq)	\
	((cfqq)->on_dispatch[ASYNC] + (cfqq)->on_dispatch[SYNC])

#define cfq_cfqq_class_sync(cfqq)	((cfqq)->key != CFQ_KEY_ASYNC)

#define cfq_cfqq_sync(cfqq)		\
	(cfq_cfqq_class_sync(cfqq) || (cfqq)->on_dispatch[SYNC])
70

71 72
#define sample_valid(samples)	((samples) > 80)

73 74 75
/*
 * Per block device queue structure
 */
Linus Torvalds's avatar
Linus Torvalds committed
76
struct cfq_data {
77 78 79 80 81 82 83 84 85 86 87 88 89 90
	request_queue_t *queue;

	/*
	 * rr list of queues with requests and the count of them
	 */
	struct list_head rr_list[CFQ_PRIO_LISTS];
	struct list_head busy_rr;
	struct list_head cur_rr;
	struct list_head idle_rr;
	unsigned int busy_queues;

	/*
	 * non-ordered list of empty cfqq's
	 */
Linus Torvalds's avatar
Linus Torvalds committed
91 92
	struct list_head empty_list;

93 94 95
	/*
	 * cfqq lookup hash
	 */
Linus Torvalds's avatar
Linus Torvalds committed
96 97
	struct hlist_head *cfq_hash;

98
	mempool_t *crq_pool;
Linus Torvalds's avatar
Linus Torvalds committed
99

100
	int rq_in_driver;
101
	int hw_tag;
Linus Torvalds's avatar
Linus Torvalds committed
102

103 104 105 106 107 108 109 110
	/*
	 * schedule slice state info
	 */
	/*
	 * idle window management
	 */
	struct timer_list idle_slice_timer;
	struct work_struct unplug_work;
Linus Torvalds's avatar
Linus Torvalds committed
111

112 113 114 115 116 117
	struct cfq_queue *active_queue;
	struct cfq_io_context *active_cic;
	int cur_prio, cur_end_prio;
	unsigned int dispatch_slice;

	struct timer_list idle_class_timer;
Linus Torvalds's avatar
Linus Torvalds committed
118 119

	sector_t last_sector;
120
	unsigned long last_end_request;
Linus Torvalds's avatar
Linus Torvalds committed
121

122
	unsigned int rq_starved;
Linus Torvalds's avatar
Linus Torvalds committed
123 124 125 126 127 128

	/*
	 * tunables, see top of file
	 */
	unsigned int cfq_quantum;
	unsigned int cfq_queued;
129
	unsigned int cfq_fifo_expire[2];
Linus Torvalds's avatar
Linus Torvalds committed
130 131
	unsigned int cfq_back_penalty;
	unsigned int cfq_back_max;
132 133 134
	unsigned int cfq_slice[2];
	unsigned int cfq_slice_async_rq;
	unsigned int cfq_slice_idle;
135 136

	struct list_head cic_list;
Linus Torvalds's avatar
Linus Torvalds committed
137 138
};

139 140 141
/*
 * Per process-grouping structure
 */
Linus Torvalds's avatar
Linus Torvalds committed
142 143 144 145 146
struct cfq_queue {
	/* reference count */
	atomic_t ref;
	/* parent cfq_data */
	struct cfq_data *cfqd;
147
	/* cfqq lookup hash */
Linus Torvalds's avatar
Linus Torvalds committed
148 149
	struct hlist_node cfq_hash;
	/* hash key */
150
	unsigned int key;
Linus Torvalds's avatar
Linus Torvalds committed
151 152 153 154 155 156 157 158 159 160 161
	/* on either rr or empty list of cfqd */
	struct list_head cfq_list;
	/* sorted list of pending requests */
	struct rb_root sort_list;
	/* if fifo isn't expired, next request to serve */
	struct cfq_rq *next_crq;
	/* requests queued in sort_list */
	int queued[2];
	/* currently allocated requests */
	int allocated[2];
	/* fifo list of requests in sort_list */
162
	struct list_head fifo;
Linus Torvalds's avatar
Linus Torvalds committed
163

164 165 166 167
	unsigned long slice_start;
	unsigned long slice_end;
	unsigned long slice_left;
	unsigned long service_last;
Linus Torvalds's avatar
Linus Torvalds committed
168

Jens Axboe's avatar
Jens Axboe committed
169 170
	/* number of requests that are on the dispatch list */
	int on_dispatch[2];
171 172 173 174 175

	/* io prio of this group */
	unsigned short ioprio, org_ioprio;
	unsigned short ioprio_class, org_ioprio_class;

Jens Axboe's avatar
Jens Axboe committed
176 177
	/* various state flags, see below */
	unsigned int flags;
Linus Torvalds's avatar
Linus Torvalds committed
178 179 180 181 182 183 184 185 186
};

struct cfq_rq {
	struct request *request;

	struct cfq_queue *cfq_queue;
	struct cfq_io_context *io_context;
};

Jens Axboe's avatar
Jens Axboe committed
187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222
enum cfqq_state_flags {
	CFQ_CFQQ_FLAG_on_rr = 0,
	CFQ_CFQQ_FLAG_wait_request,
	CFQ_CFQQ_FLAG_must_alloc,
	CFQ_CFQQ_FLAG_must_alloc_slice,
	CFQ_CFQQ_FLAG_must_dispatch,
	CFQ_CFQQ_FLAG_fifo_expire,
	CFQ_CFQQ_FLAG_idle_window,
	CFQ_CFQQ_FLAG_prio_changed,
};

#define CFQ_CFQQ_FNS(name)						\
static inline void cfq_mark_cfqq_##name(struct cfq_queue *cfqq)		\
{									\
	cfqq->flags |= (1 << CFQ_CFQQ_FLAG_##name);			\
}									\
static inline void cfq_clear_cfqq_##name(struct cfq_queue *cfqq)	\
{									\
	cfqq->flags &= ~(1 << CFQ_CFQQ_FLAG_##name);			\
}									\
static inline int cfq_cfqq_##name(const struct cfq_queue *cfqq)		\
{									\
	return (cfqq->flags & (1 << CFQ_CFQQ_FLAG_##name)) != 0;	\
}

CFQ_CFQQ_FNS(on_rr);
CFQ_CFQQ_FNS(wait_request);
CFQ_CFQQ_FNS(must_alloc);
CFQ_CFQQ_FNS(must_alloc_slice);
CFQ_CFQQ_FNS(must_dispatch);
CFQ_CFQQ_FNS(fifo_expire);
CFQ_CFQQ_FNS(idle_window);
CFQ_CFQQ_FNS(prio_changed);
#undef CFQ_CFQQ_FNS

static struct cfq_queue *cfq_find_cfq_hash(struct cfq_data *, unsigned int, unsigned short);
223
static void cfq_dispatch_insert(request_queue_t *, struct cfq_rq *);
224
static struct cfq_queue *cfq_get_queue(struct cfq_data *cfqd, unsigned int key, struct task_struct *tsk, gfp_t gfp_mask);
Linus Torvalds's avatar
Linus Torvalds committed
225

Andrew Morton's avatar
Andrew Morton committed
226 227 228 229 230 231
/*
 * scheduler run of queue, if there are requests pending and no one in the
 * driver that will restart queueing
 */
static inline void cfq_schedule_dispatch(struct cfq_data *cfqd)
{
232
	if (cfqd->busy_queues)
Andrew Morton's avatar
Andrew Morton committed
233 234 235 236 237 238 239
		kblockd_schedule_work(&cfqd->unplug_work);
}

static int cfq_queue_empty(request_queue_t *q)
{
	struct cfq_data *cfqd = q->elevator->elevator_data;

240
	return !cfqd->busy_queues;
Andrew Morton's avatar
Andrew Morton committed
241 242
}

243 244
static inline pid_t cfq_queue_pid(struct task_struct *task, int rw)
{
Jens Axboe's avatar
Jens Axboe committed
245
	if (rw == READ || rw == WRITE_SYNC)
246 247 248 249 250
		return task->pid;

	return CFQ_KEY_ASYNC;
}

Linus Torvalds's avatar
Linus Torvalds committed
251 252 253
/*
 * Lifted from AS - choose which of crq1 and crq2 that is best served now.
 * We choose the request that is closest to the head right now. Distance
254
 * behind the head is penalized and only allowed to a certain extent.
Linus Torvalds's avatar
Linus Torvalds committed
255 256 257 258 259 260
 */
static struct cfq_rq *
cfq_choose_req(struct cfq_data *cfqd, struct cfq_rq *crq1, struct cfq_rq *crq2)
{
	sector_t last, s1, s2, d1 = 0, d2 = 0;
	unsigned long back_max;
261 262 263
#define CFQ_RQ1_WRAP	0x01 /* request 1 wraps */
#define CFQ_RQ2_WRAP	0x02 /* request 2 wraps */
	unsigned wrap = 0; /* bit mask: requests behind the disk head? */
Linus Torvalds's avatar
Linus Torvalds committed
264 265 266 267 268

	if (crq1 == NULL || crq1 == crq2)
		return crq2;
	if (crq2 == NULL)
		return crq1;
269

270
	if (rq_is_sync(crq1->request) && !rq_is_sync(crq2->request))
271
		return crq1;
272
	else if (rq_is_sync(crq2->request) && !rq_is_sync(crq1->request))
273
		return crq2;
Linus Torvalds's avatar
Linus Torvalds committed
274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294

	s1 = crq1->request->sector;
	s2 = crq2->request->sector;

	last = cfqd->last_sector;

	/*
	 * by definition, 1KiB is 2 sectors
	 */
	back_max = cfqd->cfq_back_max * 2;

	/*
	 * Strict one way elevator _except_ in the case where we allow
	 * short backward seeks which are biased as twice the cost of a
	 * similar forward seek.
	 */
	if (s1 >= last)
		d1 = s1 - last;
	else if (s1 + back_max >= last)
		d1 = (last - s1) * cfqd->cfq_back_penalty;
	else
295
		wrap |= CFQ_RQ1_WRAP;
Linus Torvalds's avatar
Linus Torvalds committed
296 297 298 299 300 301

	if (s2 >= last)
		d2 = s2 - last;
	else if (s2 + back_max >= last)
		d2 = (last - s2) * cfqd->cfq_back_penalty;
	else
302
		wrap |= CFQ_RQ2_WRAP;
Linus Torvalds's avatar
Linus Torvalds committed
303 304

	/* Found required data */
305 306 307 308 309 310 311 312

	/*
	 * By doing switch() on the bit mask "wrap" we avoid having to
	 * check two variables for all permutations: --> faster!
	 */
	switch (wrap) {
	case 0: /* common case for CFQ: crq1 and crq2 not wrapped */
		if (d1 < d2)
Linus Torvalds's avatar
Linus Torvalds committed
313
			return crq1;
314
		else if (d2 < d1)
Linus Torvalds's avatar
Linus Torvalds committed
315
			return crq2;
316 317 318 319 320 321
		else {
			if (s1 >= s2)
				return crq1;
			else
				return crq2;
		}
Linus Torvalds's avatar
Linus Torvalds committed
322

323
	case CFQ_RQ2_WRAP:
Linus Torvalds's avatar
Linus Torvalds committed
324
		return crq1;
325
	case CFQ_RQ1_WRAP:
Linus Torvalds's avatar
Linus Torvalds committed
326
		return crq2;
327 328 329 330 331 332 333 334 335
	case (CFQ_RQ1_WRAP|CFQ_RQ2_WRAP): /* both crqs wrapped */
	default:
		/*
		 * Since both rqs are wrapped,
		 * start with the one that's further behind head
		 * (--> only *one* back seek required),
		 * since back seek takes more time than forward.
		 */
		if (s1 <= s2)
Linus Torvalds's avatar
Linus Torvalds committed
336 337 338 339 340 341 342 343 344 345 346
			return crq1;
		else
			return crq2;
	}
}

/*
 * would be nice to take fifo expire time into account as well
 */
static struct cfq_rq *
cfq_find_next_crq(struct cfq_data *cfqd, struct cfq_queue *cfqq,
347
		  struct cfq_rq *last_crq)
Linus Torvalds's avatar
Linus Torvalds committed
348
{
349 350 351 352
	struct request *last = last_crq->request;
	struct rb_node *rbnext = rb_next(&last->rb_node);
	struct rb_node *rbprev = rb_prev(&last->rb_node);
	struct cfq_rq *next = NULL, *prev = NULL;
Linus Torvalds's avatar
Linus Torvalds committed
353

354
	BUG_ON(RB_EMPTY_NODE(&last->rb_node));
Linus Torvalds's avatar
Linus Torvalds committed
355 356

	if (rbprev)
357
		prev = RQ_DATA(rb_entry_rq(rbprev));
Linus Torvalds's avatar
Linus Torvalds committed
358

359 360 361 362 363 364 365
	if (rbnext)
		next = RQ_DATA(rb_entry_rq(rbnext));
	else {
		rbnext = rb_first(&cfqq->sort_list);
		if (rbnext && rbnext != &last->rb_node)
			next = RQ_DATA(rb_entry_rq(rbnext));
	}
Linus Torvalds's avatar
Linus Torvalds committed
366

367
	return cfq_choose_req(cfqd, next, prev);
Linus Torvalds's avatar
Linus Torvalds committed
368 369
}

370
static void cfq_resort_rr_list(struct cfq_queue *cfqq, int preempted)
Linus Torvalds's avatar
Linus Torvalds committed
371
{
372 373
	struct cfq_data *cfqd = cfqq->cfqd;
	struct list_head *list, *entry;
Linus Torvalds's avatar
Linus Torvalds committed
374

Jens Axboe's avatar
Jens Axboe committed
375
	BUG_ON(!cfq_cfqq_on_rr(cfqq));
Linus Torvalds's avatar
Linus Torvalds committed
376

377
	list_del(&cfqq->cfq_list);
Linus Torvalds's avatar
Linus Torvalds committed
378

379 380 381 382 383 384 385 386 387 388 389 390
	if (cfq_class_rt(cfqq))
		list = &cfqd->cur_rr;
	else if (cfq_class_idle(cfqq))
		list = &cfqd->idle_rr;
	else {
		/*
		 * if cfqq has requests in flight, don't allow it to be
		 * found in cfq_set_active_queue before it has finished them.
		 * this is done to increase fairness between a process that
		 * has lots of io pending vs one that only generates one
		 * sporadically or synchronously
		 */
Jens Axboe's avatar
Jens Axboe committed
391
		if (cfq_cfqq_dispatched(cfqq))
392 393 394
			list = &cfqd->busy_rr;
		else
			list = &cfqd->rr_list[cfqq->ioprio];
Linus Torvalds's avatar
Linus Torvalds committed
395 396
	}

397 398
	/*
	 * if queue was preempted, just add to front to be fair. busy_rr
399
	 * isn't sorted, but insert at the back for fairness.
400 401
	 */
	if (preempted || list == &cfqd->busy_rr) {
402 403 404 405
		if (preempted)
			list = list->prev;

		list_add_tail(&cfqq->cfq_list, list);
Linus Torvalds's avatar
Linus Torvalds committed
406
		return;
407
	}
Linus Torvalds's avatar
Linus Torvalds committed
408 409

	/*
410
	 * sort by when queue was last serviced
Linus Torvalds's avatar
Linus Torvalds committed
411
	 */
412 413
	entry = list;
	while ((entry = entry->prev) != list) {
Linus Torvalds's avatar
Linus Torvalds committed
414 415
		struct cfq_queue *__cfqq = list_entry_cfqq(entry);

416 417 418
		if (!__cfqq->service_last)
			break;
		if (time_before(__cfqq->service_last, cfqq->service_last))
Linus Torvalds's avatar
Linus Torvalds committed
419 420 421 422 423 424 425 426
			break;
	}

	list_add(&cfqq->cfq_list, entry);
}

/*
 * add to busy list of queues for service, trying to be fair in ordering
427
 * the pending list according to last request service
Linus Torvalds's avatar
Linus Torvalds committed
428 429
 */
static inline void
430
cfq_add_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
Linus Torvalds's avatar
Linus Torvalds committed
431
{
Jens Axboe's avatar
Jens Axboe committed
432 433
	BUG_ON(cfq_cfqq_on_rr(cfqq));
	cfq_mark_cfqq_on_rr(cfqq);
Linus Torvalds's avatar
Linus Torvalds committed
434 435
	cfqd->busy_queues++;

436
	cfq_resort_rr_list(cfqq, 0);
Linus Torvalds's avatar
Linus Torvalds committed
437 438 439 440 441
}

static inline void
cfq_del_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
{
Jens Axboe's avatar
Jens Axboe committed
442 443
	BUG_ON(!cfq_cfqq_on_rr(cfqq));
	cfq_clear_cfqq_on_rr(cfqq);
444
	list_move(&cfqq->cfq_list, &cfqd->empty_list);
Linus Torvalds's avatar
Linus Torvalds committed
445 446 447 448 449 450 451 452 453 454 455

	BUG_ON(!cfqd->busy_queues);
	cfqd->busy_queues--;
}

/*
 * rb tree support functions
 */
static inline void cfq_del_crq_rb(struct cfq_rq *crq)
{
	struct cfq_queue *cfqq = crq->cfq_queue;
456
	struct cfq_data *cfqd = cfqq->cfqd;
457
	const int sync = rq_is_sync(crq->request);
Linus Torvalds's avatar
Linus Torvalds committed
458

459 460
	BUG_ON(!cfqq->queued[sync]);
	cfqq->queued[sync]--;
Linus Torvalds's avatar
Linus Torvalds committed
461

462
	elv_rb_del(&cfqq->sort_list, crq->request);
Linus Torvalds's avatar
Linus Torvalds committed
463

464
	if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY_ROOT(&cfqq->sort_list))
465
		cfq_del_cfqq_rr(cfqd, cfqq);
Linus Torvalds's avatar
Linus Torvalds committed
466 467 468 469 470 471 472
}

static void cfq_add_crq_rb(struct cfq_rq *crq)
{
	struct cfq_queue *cfqq = crq->cfq_queue;
	struct cfq_data *cfqd = cfqq->cfqd;
	struct request *rq = crq->request;
473
	struct request *__alias;
Linus Torvalds's avatar
Linus Torvalds committed
474

475
	cfqq->queued[rq_is_sync(rq)]++;
Linus Torvalds's avatar
Linus Torvalds committed
476 477 478 479 480

	/*
	 * looks a little odd, but the first insert might return an alias.
	 * if that happens, put the alias on the dispatch list
	 */
481 482
	while ((__alias = elv_rb_add(&cfqq->sort_list, rq)) != NULL)
		cfq_dispatch_insert(cfqd->queue, RQ_DATA(__alias));
Linus Torvalds's avatar
Linus Torvalds committed
483 484 485 486 487
}

static inline void
cfq_reposition_crq_rb(struct cfq_queue *cfqq, struct cfq_rq *crq)
{
488 489 490 491
	struct request *rq = crq->request;

	elv_rb_del(&cfqq->sort_list, rq);
	cfqq->queued[rq_is_sync(rq)]--;
Linus Torvalds's avatar
Linus Torvalds committed
492 493 494
	cfq_add_crq_rb(crq);
}

495 496
static struct request *
cfq_find_rq_fmerge(struct cfq_data *cfqd, struct bio *bio)
Linus Torvalds's avatar
Linus Torvalds committed
497
{
498 499
	struct task_struct *tsk = current;
	pid_t key = cfq_queue_pid(tsk, bio_data_dir(bio));
500
	sector_t sector = bio->bi_sector + bio_sectors(bio);
501
	struct cfq_queue *cfqq;
Linus Torvalds's avatar
Linus Torvalds committed
502

503
	cfqq = cfq_find_cfq_hash(cfqd, key, tsk->ioprio);
504 505
	if (cfqq)
		return elv_rb_find(&cfqq->sort_list, sector);
Linus Torvalds's avatar
Linus Torvalds committed
506 507 508 509

	return NULL;
}

510
static void cfq_activate_request(request_queue_t *q, struct request *rq)
Linus Torvalds's avatar
Linus Torvalds committed
511
{
512
	struct cfq_data *cfqd = q->elevator->elevator_data;
Jens Axboe's avatar
Jens Axboe committed
513

514
	cfqd->rq_in_driver++;
515 516 517 518 519 520 521 522 523

	/*
	 * If the depth is larger 1, it really could be queueing. But lets
	 * make the mark a little higher - idling could still be good for
	 * low queueing, and a low queueing number could also just indicate
	 * a SCSI mid layer like behaviour where limit+1 is often seen.
	 */
	if (!cfqd->hw_tag && cfqd->rq_in_driver > 4)
		cfqd->hw_tag = 1;
Linus Torvalds's avatar
Linus Torvalds committed
524 525
}

526
static void cfq_deactivate_request(request_queue_t *q, struct request *rq)
Linus Torvalds's avatar
Linus Torvalds committed
527
{
528 529 530 531
	struct cfq_data *cfqd = q->elevator->elevator_data;

	WARN_ON(!cfqd->rq_in_driver);
	cfqd->rq_in_driver--;
Linus Torvalds's avatar
Linus Torvalds committed
532 533
}

534
static void cfq_remove_request(struct request *rq)
Linus Torvalds's avatar
Linus Torvalds committed
535 536
{
	struct cfq_rq *crq = RQ_DATA(rq);
537 538 539 540
	struct cfq_queue *cfqq = crq->cfq_queue;

	if (cfqq->next_crq == crq)
		cfqq->next_crq = cfq_find_next_crq(cfqq->cfqd, cfqq, crq);
Linus Torvalds's avatar
Linus Torvalds committed
541

542 543
	list_del_init(&rq->queuelist);
	cfq_del_crq_rb(crq);
Linus Torvalds's avatar
Linus Torvalds committed
544 545 546 547 548 549 550 551
}

static int
cfq_merge(request_queue_t *q, struct request **req, struct bio *bio)
{
	struct cfq_data *cfqd = q->elevator->elevator_data;
	struct request *__rq;

552
	__rq = cfq_find_rq_fmerge(cfqd, bio);
553
	if (__rq && elv_rq_merge_ok(__rq, bio)) {
554 555
		*req = __rq;
		return ELEVATOR_FRONT_MERGE;
Linus Torvalds's avatar
Linus Torvalds committed
556 557 558 559 560
	}

	return ELEVATOR_NO_MERGE;
}

561 562
static void cfq_merged_request(request_queue_t *q, struct request *req,
			       int type)
Linus Torvalds's avatar
Linus Torvalds committed
563 564 565
{
	struct cfq_rq *crq = RQ_DATA(req);

566
	if (type == ELEVATOR_FRONT_MERGE) {
Linus Torvalds's avatar
Linus Torvalds committed
567 568 569 570 571 572 573 574 575 576
		struct cfq_queue *cfqq = crq->cfq_queue;

		cfq_reposition_crq_rb(cfqq, crq);
	}
}

static void
cfq_merged_requests(request_queue_t *q, struct request *rq,
		    struct request *next)
{
577 578 579 580 581 582 583
	/*
	 * reposition in fifo if next is older than rq
	 */
	if (!list_empty(&rq->queuelist) && !list_empty(&next->queuelist) &&
	    time_before(next->start_time, rq->start_time))
		list_move(&rq->queuelist, &next->queuelist);

584
	cfq_remove_request(next);
585 586 587 588 589 590 591 592 593 594 595 596 597 598
}

static inline void
__cfq_set_active_queue(struct cfq_data *cfqd, struct cfq_queue *cfqq)
{
	if (cfqq) {
		/*
		 * stop potential idle class queues waiting service
		 */
		del_timer(&cfqd->idle_class_timer);

		cfqq->slice_start = jiffies;
		cfqq->slice_end = 0;
		cfqq->slice_left = 0;
Jens Axboe's avatar
Jens Axboe committed
599 600
		cfq_clear_cfqq_must_alloc_slice(cfqq);
		cfq_clear_cfqq_fifo_expire(cfqq);
601 602 603 604 605
	}

	cfqd->active_queue = cfqq;
}

606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656
/*
 * current cfqq expired its slice (or was too idle), select new one
 */
static void
__cfq_slice_expired(struct cfq_data *cfqd, struct cfq_queue *cfqq,
		    int preempted)
{
	unsigned long now = jiffies;

	if (cfq_cfqq_wait_request(cfqq))
		del_timer(&cfqd->idle_slice_timer);

	if (!preempted && !cfq_cfqq_dispatched(cfqq)) {
		cfqq->service_last = now;
		cfq_schedule_dispatch(cfqd);
	}

	cfq_clear_cfqq_must_dispatch(cfqq);
	cfq_clear_cfqq_wait_request(cfqq);

	/*
	 * store what was left of this slice, if the queue idled out
	 * or was preempted
	 */
	if (time_after(cfqq->slice_end, now))
		cfqq->slice_left = cfqq->slice_end - now;
	else
		cfqq->slice_left = 0;

	if (cfq_cfqq_on_rr(cfqq))
		cfq_resort_rr_list(cfqq, preempted);

	if (cfqq == cfqd->active_queue)
		cfqd->active_queue = NULL;

	if (cfqd->active_cic) {
		put_io_context(cfqd->active_cic->ioc);
		cfqd->active_cic = NULL;
	}

	cfqd->dispatch_slice = 0;
}

static inline void cfq_slice_expired(struct cfq_data *cfqd, int preempted)
{
	struct cfq_queue *cfqq = cfqd->active_queue;

	if (cfqq)
		__cfq_slice_expired(cfqd, cfqq, preempted);
}

657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690
/*
 * 0
 * 0,1
 * 0,1,2
 * 0,1,2,3
 * 0,1,2,3,4
 * 0,1,2,3,4,5
 * 0,1,2,3,4,5,6
 * 0,1,2,3,4,5,6,7
 */
static int cfq_get_next_prio_level(struct cfq_data *cfqd)
{
	int prio, wrap;

	prio = -1;
	wrap = 0;
	do {
		int p;

		for (p = cfqd->cur_prio; p <= cfqd->cur_end_prio; p++) {
			if (!list_empty(&cfqd->rr_list[p])) {
				prio = p;
				break;
			}
		}

		if (prio != -1)
			break;
		cfqd->cur_prio = 0;
		if (++cfqd->cur_end_prio == CFQ_PRIO_LISTS) {
			cfqd->cur_end_prio = 0;
			if (wrap)
				break;
			wrap = 1;
Linus Torvalds's avatar
Linus Torvalds committed
691
		}
692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708
	} while (1);

	if (unlikely(prio == -1))
		return -1;

	BUG_ON(prio >= CFQ_PRIO_LISTS);

	list_splice_init(&cfqd->rr_list[prio], &cfqd->cur_rr);

	cfqd->cur_prio = prio + 1;
	if (cfqd->cur_prio > cfqd->cur_end_prio) {
		cfqd->cur_end_prio = cfqd->cur_prio;
		cfqd->cur_prio = 0;
	}
	if (cfqd->cur_end_prio == CFQ_PRIO_LISTS) {
		cfqd->cur_prio = 0;
		cfqd->cur_end_prio = 0;
Linus Torvalds's avatar
Linus Torvalds committed
709 710
	}

711 712 713
	return prio;
}

Jens Axboe's avatar
Jens Axboe committed
714
static struct cfq_queue *cfq_set_active_queue(struct cfq_data *cfqd)
715
{
716
	struct cfq_queue *cfqq = NULL;
717 718 719 720 721 722 723 724

	/*
	 * if current list is non-empty, grab first entry. if it is empty,
	 * get next prio level and grab first entry then if any are spliced
	 */
	if (!list_empty(&cfqd->cur_rr) || cfq_get_next_prio_level(cfqd) != -1)
		cfqq = list_entry_cfqq(cfqd->cur_rr.next);

725 726 727 728 729 730 731
	/*
	 * If no new queues are available, check if the busy list has some
	 * before falling back to idle io.
	 */
	if (!cfqq && !list_empty(&cfqd->busy_rr))
		cfqq = list_entry_cfqq(cfqd->busy_rr.next);

732 733 734 735 736 737 738 739 740 741 742 743 744 745 746
	/*
	 * if we have idle queues and no rt or be queues had pending
	 * requests, either allow immediate service if the grace period
	 * has passed or arm the idle grace timer
	 */
	if (!cfqq && !list_empty(&cfqd->idle_rr)) {
		unsigned long end = cfqd->last_end_request + CFQ_IDLE_GRACE;

		if (time_after_eq(jiffies, end))
			cfqq = list_entry_cfqq(cfqd->idle_rr.next);
		else
			mod_timer(&cfqd->idle_class_timer, end);
	}

	__cfq_set_active_queue(cfqd, cfqq);
Jens Axboe's avatar
Jens Axboe committed
747
	return cfqq;
748 749
}

750 751
#define CIC_SEEKY(cic) ((cic)->seek_mean > (128 * 1024))

752 753 754
static int cfq_arm_slice_timer(struct cfq_data *cfqd, struct cfq_queue *cfqq)

{
755
	struct cfq_io_context *cic;
756 757
	unsigned long sl;

758
	WARN_ON(!RB_EMPTY_ROOT(&cfqq->sort_list));
759 760 761 762 763 764 765
	WARN_ON(cfqq != cfqd->active_queue);

	/*
	 * idle is disabled, either manually or by past process history
	 */
	if (!cfqd->cfq_slice_idle)
		return 0;
Jens Axboe's avatar
Jens Axboe committed
766
	if (!cfq_cfqq_idle_window(cfqq))
767 768 769 770
		return 0;
	/*
	 * task has exited, don't wait
	 */
771 772
	cic = cfqd->active_cic;
	if (!cic || !cic->ioc->task)
773 774
		return 0;

Jens Axboe's avatar
Jens Axboe committed
775 776
	cfq_mark_cfqq_must_dispatch(cfqq);
	cfq_mark_cfqq_wait_request(cfqq);
777

778
	sl = min(cfqq->slice_end - 1, (unsigned long) cfqd->cfq_slice_idle);
779 780 781 782 783 784

	/*
	 * we don't want to idle for seeks, but we do want to allow
	 * fair distribution of slice time for a process doing back-to-back
	 * seeks. so allow a little bit of time for him to submit a new rq
	 */
785
	if (sample_valid(cic->seek_samples) && CIC_SEEKY(cic))
786
		sl = min(sl, msecs_to_jiffies(2));
787

788
	mod_timer(&cfqd->idle_slice_timer, jiffies + sl);
789
	return 1;
Linus Torvalds's avatar
Linus Torvalds committed
790 791
}

792
static void cfq_dispatch_insert(request_queue_t *q, struct cfq_rq *crq)
Linus Torvalds's avatar
Linus Torvalds committed
793 794 795
{
	struct cfq_data *cfqd = q->elevator->elevator_data;
	struct cfq_queue *cfqq = crq->cfq_queue;
796
	struct request *rq = crq->request;
797

798 799 800
	cfq_remove_request(rq);
	cfqq->on_dispatch[rq_is_sync(rq)]++;
	elv_dispatch_sort(q, rq);
801 802 803

	rq = list_entry(q->queue_head.prev, struct request, queuelist);
	cfqd->last_sector = rq->sector + rq->nr_sectors;
Linus Torvalds's avatar
Linus Torvalds committed
804 805 806 807 808 809 810 811
}

/*
 * return expired entry, or NULL to just start from scratch in rbtree
 */
static inline struct cfq_rq *cfq_check_fifo(struct cfq_queue *cfqq)
{
	struct cfq_data *cfqd = cfqq->cfqd;
812
	struct request *rq;
Linus Torvalds's avatar
Linus Torvalds committed
813 814
	struct cfq_rq *crq;

Jens Axboe's avatar
Jens Axboe committed
815
	if (cfq_cfqq_fifo_expire(cfqq))
Linus Torvalds's avatar
Linus Torvalds committed
816 817
		return NULL;

818
	if (!list_empty(&cfqq->fifo)) {
Jens Axboe's avatar
Jens Axboe committed
819
		int fifo = cfq_cfqq_class_sync(cfqq);
Linus Torvalds's avatar
Linus Torvalds committed
820

821
		crq = RQ_DATA(rq_entry_fifo(cfqq->fifo.next));
822 823
		rq = crq->request;
		if (time_after(jiffies, rq->start_time + cfqd->cfq_fifo_expire[fifo])) {
Jens Axboe's avatar
Jens Axboe committed
824
			cfq_mark_cfqq_fifo_expire(cfqq);
825 826
			return crq;
		}
Linus Torvalds's avatar
Linus Torvalds committed
827 828 829 830 831 832
	}

	return NULL;
}

/*
Jens Axboe's avatar
Jens Axboe committed
833 834 835
 * Scale schedule slice based on io priority. Use the sync time slice only
 * if a queue is marked sync and has sync io queued. A sync queue with async
 * io only, should not get full sync slice length.
Linus Torvalds's avatar
Linus Torvalds committed
836
 */
837 838 839 840 841 842 843 844 845 846
static inline int
cfq_prio_to_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
{
	const int base_slice = cfqd->cfq_slice[cfq_cfqq_sync(cfqq)];

	WARN_ON(cfqq->ioprio >= IOPRIO_BE_NR);

	return base_slice + (base_slice/CFQ_SLICE_SCALE * (4 - cfqq->ioprio));
}

Linus Torvalds's avatar
Linus Torvalds committed
847
static inline void
848
cfq_set_prio_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
Linus Torvalds's avatar
Linus Torvalds committed
849
{
850 851
	cfqq->slice_end = cfq_prio_to_slice(cfqd, cfqq) + jiffies;
}
Linus Torvalds's avatar
Linus Torvalds committed
852

853 854 855 856
static inline int
cfq_prio_to_maxrq(struct cfq_data *cfqd, struct cfq_queue *cfqq)
{
	const int base_rq = cfqd->cfq_slice_async_rq;
Linus Torvalds's avatar
Linus Torvalds committed
857

858
	WARN_ON(cfqq->ioprio >= IOPRIO_BE_NR);
Linus Torvalds's avatar
Linus Torvalds committed
859

860
	return 2 * (base_rq + base_rq * (CFQ_PRIO_LISTS - 1 - cfqq->ioprio));
Linus Torvalds's avatar
Linus Torvalds committed
861 862
}

863 864 865
/*
 * get next queue for service
 */
866
static struct cfq_queue *cfq_select_queue(struct cfq_data *cfqd)
Linus Torvalds's avatar
Linus Torvalds committed
867
{
868
	unsigned long now = jiffies;
Linus Torvalds's avatar
Linus Torvalds committed
869 870
	struct cfq_queue *cfqq;

871 872 873
	cfqq = cfqd->active_queue;
	if (!cfqq)
		goto new_queue;
Linus Torvalds's avatar
Linus Torvalds committed
874

875 876 877
	/*
	 * slice has expired
	 */
Jens Axboe's avatar
Jens Axboe committed
878 879
	if (!cfq_cfqq_must_dispatch(cfqq) && time_after(now, cfqq->slice_end))
		goto expire;
Linus Torvalds's avatar
Linus Torvalds committed
880

881 882 883 884
	/*
	 * if queue has requests, dispatch one. if not, check if
	 * enough slice is left to wait for one
	 */
885
	if (!RB_EMPTY_ROOT(&cfqq->sort_list))
886
		goto keep_queue;
887 888 889 890
	else if (cfq_cfqq_dispatched(cfqq)) {
		cfqq = NULL;
		goto keep_queue;
	} else if (cfq_cfqq_class_sync(cfqq)) {
891 892 893 894
		if (cfq_arm_slice_timer(cfqd, cfqq))
			return NULL;
	}

Jens Axboe's avatar
Jens Axboe committed
895
expire:
896
	cfq_slice_expired(cfqd, 0);
Jens Axboe's avatar
Jens Axboe committed
897 898
new_queue:
	cfqq = cfq_set_active_queue(cfqd);
899
keep_queue:
Jens Axboe's avatar
Jens Axboe committed
900
	return cfqq;
901 902 903 904 905 906 907 908
}

static int
__cfq_dispatch_requests(struct cfq_data *cfqd, struct cfq_queue *cfqq,
			int max_dispatch)
{
	int dispatched = 0;

909
	BUG_ON(RB_EMPTY_ROOT(&cfqq->sort_list));
910 911 912

	do {
		struct cfq_rq *crq;
Linus Torvalds's avatar
Linus Torvalds committed
913 914

		/*
915
		 * follow expired path, else get first next available
Linus Torvalds's avatar
Linus Torvalds committed
916
		 */
917 918 919 920 921 922
		if ((crq = cfq_check_fifo(cfqq)) == NULL)
			crq = cfqq->next_crq;

		/*
		 * finally, insert request into driver dispatch list
		 */
923
		cfq_dispatch_insert(cfqd->queue, crq);
Linus Torvalds's avatar
Linus Torvalds committed
924

925 926
		cfqd->dispatch_slice++;
		dispatched++;
Linus Torvalds's avatar
Linus Torvalds committed
927

928 929 930 931
		if (!cfqd->active_cic) {
			atomic_inc(&crq->io_context->ioc->refcount);
			cfqd->active_cic = crq->io_context;
		}
Linus Torvalds's avatar
Linus Torvalds committed
932

933
		if (RB_EMPTY_ROOT(&cfqq->sort_list))
934 935 936 937 938
			break;

	} while (dispatched < max_dispatch);

	/*
939
	 * if slice end isn't set yet, set it.
940 941 942 943 944 945 946 947 948 949
	 */
	if (!cfqq->slice_end)
		cfq_set_prio_slice(cfqd, cfqq);

	/*
	 * expire an async queue immediately if it has used up its slice. idle
	 * queue always expire after 1 dispatch round.
	 */
	if ((!cfq_cfqq_sync(cfqq) &&
	    cfqd->dispatch_slice >= cfq_prio_to_maxrq(cfqd, cfqq)) ||
950 951
	    cfq_class_idle(cfqq) ||
	    !cfq_cfqq_idle_window(cfqq))
952 953 954 955 956
		cfq_slice_expired(cfqd, 0);

	return dispatched;
}

957 958 959 960 961
static int
cfq_forced_dispatch_cfqqs(struct list_head *list)
{
	struct cfq_queue *cfqq, *next;
	struct cfq_rq *crq;
962
	int dispatched;
963

964
	dispatched = 0;
965 966 967 968 969 970 971
	list_for_each_entry_safe(cfqq, next, list, cfq_list) {
		while ((crq = cfqq->next_crq)) {
			cfq_dispatch_insert(cfqq->cfqd->queue, crq);
			dispatched++;
		}
		BUG_ON(!list_empty(&cfqq->fifo));
	}
972

973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994
	return dispatched;
}

static int
cfq_forced_dispatch(struct cfq_data *cfqd)
{
	int i, dispatched = 0;

	for (i = 0; i < CFQ_PRIO_LISTS; i++)
		dispatched += cfq_forced_dispatch_cfqqs(&cfqd->rr_list[i]);

	dispatched += cfq_forced_dispatch_cfqqs(&cfqd->busy_rr);
	dispatched += cfq_forced_dispatch_cfqqs(&cfqd->cur_rr);
	dispatched += cfq_forced_dispatch_cfqqs(&cfqd->idle_rr);

	cfq_slice_expired(cfqd, 0);

	BUG_ON(cfqd->busy_queues);

	return dispatched;
}

995
static int
996
cfq_dispatch_requests(request_queue_t *q, int force)
997 998
{
	struct cfq_data *cfqd = q->elevator->elevator_data;
999 1000
	struct cfq_queue *cfqq, *prev_cfqq;
	int dispatched;
1001 1002 1003 1004

	if (!cfqd->busy_queues)
		return 0;

1005 1006 1007
	if (unlikely(force))
		return cfq_forced_dispatch(cfqd);

1008 1009 1010
	dispatched = 0;
	prev_cfqq = NULL;
	while ((cfqq = cfq_select_queue(cfqd)) != NULL) {
1011 1012
		int max_dispatch;

1013 1014 1015 1016 1017 1018
		/*
		 * Don't repeat dispatch from the previous queue.
		 */
		if (prev_cfqq == cfqq)
			break;

Jens Axboe's avatar
Jens Axboe committed
1019 1020
		cfq_clear_cfqq_must_dispatch(cfqq);
		cfq_clear_cfqq_wait_request(cfqq);
1021 1022
		del_timer(&cfqd->idle_slice_timer);

1023 1024 1025
		max_dispatch = cfqd->cfq_quantum;
		if (cfq_class_idle(cfqq))
			max_dispatch = 1;
Linus Torvalds's avatar
Linus Torvalds committed
1026

1027 1028 1029 1030 1031 1032 1033 1034 1035 1036
		dispatched += __cfq_dispatch_requests(cfqd, cfqq, max_dispatch);

		/*
		 * If the dispatch cfqq has idling enabled and is still
		 * the active queue, break out.
		 */
		if (cfq_cfqq_idle_window(cfqq) && cfqd->active_queue)
			break;

		prev_cfqq = cfqq;
Linus Torvalds's avatar
Linus Torvalds committed
1037 1038
	}

1039
	return dispatched;
Linus Torvalds's avatar
Linus Torvalds committed
1040 1041 1042 1043 1044 1045 1046 1047 1048 1049
}

/*
 * task holds one reference to the queue, dropped when task exits. each crq
 * in-flight on this queue also holds a reference, dropped when crq is freed.
 *
 * queue lock must be held here.
 */
static void cfq_put_queue(struct cfq_queue *cfqq)
{
1050 1051 1052
	struct cfq_data *cfqd = cfqq->cfqd;

	BUG_ON(atomic_read(&cfqq->ref) <= 0);
Linus Torvalds's avatar
Linus Torvalds committed
1053 1054 1055 1056 1057

	if (!atomic_dec_and_test(&cfqq->ref))
		return;

	BUG_ON(rb_first(&cfqq->sort_list));
1058
	BUG_ON(cfqq->allocated[READ] + cfqq->allocated[WRITE]);
Jens Axboe's avatar
Jens Axboe committed
1059
	BUG_ON(cfq_cfqq_on_rr(cfqq));
Linus Torvalds's avatar
Linus Torvalds committed
1060

1061
	if (unlikely(cfqd->active_queue == cfqq))
Jens Axboe's avatar
Jens Axboe committed
1062
		__cfq_slice_expired(cfqd, cfqq, 0);
1063

Linus Torvalds's avatar
Linus Torvalds committed
1064 1065 1066 1067 1068 1069 1070 1071 1072
	/*
	 * it's on the empty list and still hashed
	 */
	list_del(&cfqq->cfq_list);
	hlist_del(&cfqq->cfq_hash);
	kmem_cache_free(cfq_pool, cfqq);
}

static inline struct cfq_queue *
Jens Axboe's avatar
Jens Axboe committed
1073 1074
__cfq_find_cfq_hash(struct cfq_data *cfqd, unsigned int key, unsigned int prio,
		    const int hashval)
Linus Torvalds's avatar
Linus Torvalds committed
1075 1076
{
	struct hlist_head *hash_list = &cfqd->cfq_hash[hashval];
1077 1078
	struct hlist_node *entry;
	struct cfq_queue *__cfqq;
Linus Torvalds's avatar
Linus Torvalds committed
1079

1080
	hlist_for_each_entry(__cfqq, entry, hash_list, cfq_hash) {
Al Viro's avatar
Al Viro committed
1081
		const unsigned short __p = IOPRIO_PRIO_VALUE(__cfqq->org_ioprio_class, __cfqq->org_ioprio);
Linus Torvalds's avatar
Linus Torvalds committed
1082

1083
		if (__cfqq->key == key && (__p == prio || !prio))
Linus Torvalds's avatar
Linus Torvalds committed
1084 1085 1086 1087 1088 1089 1090
			return __cfqq;
	}

	return NULL;
}

static struct cfq_queue *
Jens Axboe's avatar
Jens Axboe committed
1091
cfq_find_cfq_hash(struct cfq_data *cfqd, unsigned int key, unsigned short prio)
Linus Torvalds's avatar
Linus Torvalds committed
1092
{
Jens Axboe's avatar
Jens Axboe committed
1093
	return __cfq_find_cfq_hash(cfqd, key, prio, hash_long(key, CFQ_QHASH_SHIFT));
Linus Torvalds's avatar
Linus Torvalds committed
1094 1095
}

1096
static void cfq_free_io_context(struct io_context *ioc)
Linus Torvalds's avatar
Linus Torvalds committed
1097
{
1098
	struct cfq_io_context *__cic;
1099 1100
	struct rb_node *n;
	int freed = 0;
Linus Torvalds's avatar
Linus Torvalds committed
1101

1102 1103 1104
	while ((n = rb_first(&ioc->cic_root)) != NULL) {
		__cic = rb_entry(n, struct cfq_io_context, rb_node);
		rb_erase(&__cic->rb_node, &ioc->cic_root);
1105
		kmem_cache_free(cfq_ioc_pool, __cic);
1106
		freed++;
Linus Torvalds's avatar
Linus Torvalds committed
1107 1108
	}

1109 1110
	if (atomic_sub_and_test(freed, &ioc_count) && ioc_gone)
		complete(ioc_gone);
Linus Torvalds's avatar
Linus Torvalds committed
1111 1112
}

1113 1114 1115
static void cfq_trim(struct io_context *ioc)
{
	ioc->set_ioprio = NULL;
1116
	cfq_free_io_context(ioc);
1117 1118
}

1119 1120 1121 1122
/*
 * Called with interrupts disabled
 */
static void cfq_exit_single_io_context(struct cfq_io_context *cic)
Linus Torvalds's avatar
Linus Torvalds committed
1123
{
1124
	struct cfq_data *cfqd = cic->key;
1125 1126 1127 1128 1129 1130
	request_queue_t *q;

	if (!cfqd)
		return;

	q = cfqd->queue;
1131 1132 1133 1134 1135

	WARN_ON(!irqs_disabled());

	spin_lock(q->queue_lock);

1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148
	if (cic->cfqq[ASYNC]) {
		if (unlikely(cic->cfqq[ASYNC] == cfqd->active_queue))
			__cfq_slice_expired(cfqd, cic->cfqq[ASYNC], 0);
		cfq_put_queue(cic->cfqq[ASYNC]);
		cic->cfqq[ASYNC] = NULL;
	}

	if (cic->cfqq[SYNC]) {
		if (unlikely(cic->cfqq[SYNC] == cfqd->active_queue))
			__cfq_slice_expired(cfqd, cic->cfqq[SYNC], 0);
		cfq_put_queue(cic->cfqq[SYNC]);
		cic->cfqq[SYNC] = NULL;
	}
1149

1150
	cic->key = NULL;
1151
	list_del_init(&cic->queue_list);
1152
	spin_unlock(q->queue_lock);
Linus Torvalds's avatar
Linus Torvalds committed
1153 1154
}

1155
static void cfq_exit_io_context(struct io_context *ioc)
Linus Torvalds's avatar
Linus Torvalds committed
1156
{
1157
	struct cfq_io_context *__cic;
Linus Torvalds's avatar
Linus Torvalds committed
1158
	unsigned long flags;
1159
	struct rb_node *n;
1160

Linus Torvalds's avatar
Linus Torvalds committed
1161 1162 1163
	/*
	 * put the reference this task is holding to the various queues
	 */
1164
	spin_lock_irqsave(&cfq_exit_lock, flags);
1165 1166 1167 1168 1169

	n = rb_first(&ioc->cic_root);
	while (n != NULL) {
		__cic = rb_entry(n, struct cfq_io_context, rb_node);

1170
		cfq_exit_single_io_context(__cic);
1171
		n = rb_next(n);
Linus Torvalds's avatar
Linus Torvalds committed
1172 1173
	}

1174
	spin_unlock_irqrestore(&cfq_exit_lock, flags);
Linus Torvalds's avatar
Linus Torvalds committed
1175 1176
}

1177
static struct cfq_io_context *
Al Viro's avatar
Al Viro committed
1178
cfq_alloc_io_context(struct cfq_data *cfqd, gfp_t gfp_mask)
Linus Torvalds's avatar
Linus Torvalds committed
1179
{
1180
	struct cfq_io_context *cic = kmem_cache_alloc(cfq_ioc_pool, gfp_mask);
Linus Torvalds's avatar
Linus Torvalds committed
1181 1182

	if (cic) {
1183
		memset(cic, 0, sizeof(*cic));
1184
		cic->last_end_request = jiffies;
1185
		INIT_LIST_HEAD(&cic->queue_list);
1186 1187
		cic->dtor = cfq_free_io_context;
		cic->exit = cfq_exit_io_context;
1188
		atomic_inc(&ioc_count);
Linus Torvalds's avatar
Linus Torvalds committed
1189 1190 1191 1192 1193
	}

	return cic;
}

1194 1195 1196 1197 1198
static void cfq_init_prio_data(struct cfq_queue *cfqq)
{
	struct task_struct *tsk = current;
	int ioprio_class;

Jens Axboe's avatar
Jens Axboe committed
1199
	if (!cfq_cfqq_prio_changed(cfqq))