cfq-iosched.c 58.1 KB
Newer Older
Linus Torvalds's avatar
Linus Torvalds committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
/*
 *  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/kernel.h>
#include <linux/fs.h>
#include <linux/blkdev.h>
#include <linux/elevator.h>
#include <linux/bio.h>
#include <linux/config.h>
#include <linux/module.h>
#include <linux/slab.h>
#include <linux/init.h>
#include <linux/compiler.h>
#include <linux/hash.h>
#include <linux/rbtree.h>
#include <linux/mempool.h>
22 23
#include <linux/ioprio.h>
#include <linux/writeback.h>
Linus Torvalds's avatar
Linus Torvalds committed
24 25 26 27 28 29

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

34
static int cfq_slice_sync = HZ / 10;
Jens Axboe's avatar
Jens Axboe committed
35
static int cfq_slice_async = HZ / 25;
36
static int cfq_slice_async_rq = 2;
Jens Axboe's avatar
Jens Axboe committed
37
static int cfq_slice_idle = HZ / 100;
38 39 40 41 42

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

#define CFQ_KEY_ASYNC		(0)
Jens Axboe's avatar
Jens Axboe committed
43
#define CFQ_KEY_ANY		(0xffff)
44 45 46 47

/*
 * disable queueing at the driver/hardware level
 */
48
static int cfq_max_depth = 2;
49

Linus Torvalds's avatar
Linus Torvalds committed
50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
/*
 * 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)

/*
 * for the hash of crq inside the cfqq
 */
#define CFQ_MHASH_SHIFT		6
#define CFQ_MHASH_BLOCK(sec)	((sec) >> 3)
#define CFQ_MHASH_ENTRIES	(1 << CFQ_MHASH_SHIFT)
#define CFQ_MHASH_FN(sec)	hash_long(CFQ_MHASH_BLOCK(sec), CFQ_MHASH_SHIFT)
#define rq_hash_key(rq)		((rq)->sector + (rq)->nr_sectors)
#define list_entry_hash(ptr)	hlist_entry((ptr), struct cfq_rq, hash)

#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)
Linus Torvalds's avatar
Linus Torvalds committed
69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91

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

/*
 * rb-tree defines
 */
#define RB_NONE			(2)
#define RB_EMPTY(node)		((node)->rb_node == NULL)
#define RB_CLEAR_COLOR(node)	(node)->rb_color = RB_NONE
#define RB_CLEAR(node)		do {	\
	(node)->rb_parent = NULL;	\
	RB_CLEAR_COLOR((node));		\
	(node)->rb_right = NULL;	\
	(node)->rb_left = NULL;		\
} while (0)
#define RB_CLEAR_ROOT(root)	((root)->rb_node = NULL)
#define rb_entry_crq(node)	rb_entry((node), struct cfq_rq, rb_node)
#define rq_rb_key(rq)		(rq)->sector

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

92 93 94 95 96
#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
97 98 99 100 101 102 103 104 105 106
#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])
107 108 109 110

/*
 * Per block device queue structure
 */
Linus Torvalds's avatar
Linus Torvalds committed
111
struct cfq_data {
112 113 114 115 116 117 118 119 120 121 122 123 124 125 126
	atomic_t ref;
	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
127 128
	struct list_head empty_list;

129 130 131
	/*
	 * cfqq lookup hash
	 */
Linus Torvalds's avatar
Linus Torvalds committed
132 133
	struct hlist_head *cfq_hash;

134 135 136 137
	/*
	 * global crq hash for all queues
	 */
	struct hlist_head *crq_hash;
Linus Torvalds's avatar
Linus Torvalds committed
138 139 140

	unsigned int max_queued;

141
	mempool_t *crq_pool;
Linus Torvalds's avatar
Linus Torvalds committed
142

143
	int rq_in_driver;
Linus Torvalds's avatar
Linus Torvalds committed
144

145 146 147 148 149 150 151 152
	/*
	 * 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
153

154 155 156 157 158 159
	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
160 161

	sector_t last_sector;
162
	unsigned long last_end_request;
Linus Torvalds's avatar
Linus Torvalds committed
163

164
	unsigned int rq_starved;
Linus Torvalds's avatar
Linus Torvalds committed
165 166 167 168 169 170

	/*
	 * tunables, see top of file
	 */
	unsigned int cfq_quantum;
	unsigned int cfq_queued;
171
	unsigned int cfq_fifo_expire[2];
Linus Torvalds's avatar
Linus Torvalds committed
172 173
	unsigned int cfq_back_penalty;
	unsigned int cfq_back_max;
174 175 176 177
	unsigned int cfq_slice[2];
	unsigned int cfq_slice_async_rq;
	unsigned int cfq_slice_idle;
	unsigned int cfq_max_depth;
Linus Torvalds's avatar
Linus Torvalds committed
178 179
};

180 181 182
/*
 * Per process-grouping structure
 */
Linus Torvalds's avatar
Linus Torvalds committed
183 184 185 186 187
struct cfq_queue {
	/* reference count */
	atomic_t ref;
	/* parent cfq_data */
	struct cfq_data *cfqd;
188
	/* cfqq lookup hash */
Linus Torvalds's avatar
Linus Torvalds committed
189 190
	struct hlist_node cfq_hash;
	/* hash key */
191
	unsigned int key;
Linus Torvalds's avatar
Linus Torvalds committed
192 193 194 195 196 197 198 199 200 201 202
	/* 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 */
203
	struct list_head fifo;
Linus Torvalds's avatar
Linus Torvalds committed
204

205 206 207 208
	unsigned long slice_start;
	unsigned long slice_end;
	unsigned long slice_left;
	unsigned long service_last;
Linus Torvalds's avatar
Linus Torvalds committed
209

Jens Axboe's avatar
Jens Axboe committed
210 211
	/* number of requests that are on the dispatch list */
	int on_dispatch[2];
212 213 214 215 216

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

Jens Axboe's avatar
Jens Axboe committed
217 218
	/* various state flags, see below */
	unsigned int flags;
Linus Torvalds's avatar
Linus Torvalds committed
219 220 221 222 223 224 225 226 227 228 229
};

struct cfq_rq {
	struct rb_node rb_node;
	sector_t rb_key;
	struct request *request;
	struct hlist_node hash;

	struct cfq_queue *cfq_queue;
	struct cfq_io_context *io_context;

Jens Axboe's avatar
Jens Axboe committed
230
	unsigned int crq_flags;
Linus Torvalds's avatar
Linus Torvalds committed
231 232
};

Jens Axboe's avatar
Jens Axboe committed
233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270
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,
	CFQ_CFQQ_FLAG_expired,
};

#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);
CFQ_CFQQ_FNS(expired);
#undef CFQ_CFQQ_FNS

enum cfq_rq_state_flags {
271
	CFQ_CRQ_FLAG_is_sync = 0,
Jens Axboe's avatar
Jens Axboe committed
272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291
};

#define CFQ_CRQ_FNS(name)						\
static inline void cfq_mark_crq_##name(struct cfq_rq *crq)		\
{									\
	crq->crq_flags |= (1 << CFQ_CRQ_FLAG_##name);			\
}									\
static inline void cfq_clear_crq_##name(struct cfq_rq *crq)		\
{									\
	crq->crq_flags &= ~(1 << CFQ_CRQ_FLAG_##name);			\
}									\
static inline int cfq_crq_##name(const struct cfq_rq *crq)		\
{									\
	return (crq->crq_flags & (1 << CFQ_CRQ_FLAG_##name)) != 0;	\
}

CFQ_CRQ_FNS(is_sync);
#undef CFQ_CRQ_FNS

static struct cfq_queue *cfq_find_cfq_hash(struct cfq_data *, unsigned int, unsigned short);
292
static void cfq_dispatch_insert(request_queue_t *, struct cfq_rq *);
Linus Torvalds's avatar
Linus Torvalds committed
293 294
static void cfq_put_cfqd(struct cfq_data *cfqd);

295
#define process_sync(tsk)	((tsk)->flags & PF_SYNCWRITE)
Linus Torvalds's avatar
Linus Torvalds committed
296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332

/*
 * lots of deadline iosched dupes, can be abstracted later...
 */
static inline void cfq_del_crq_hash(struct cfq_rq *crq)
{
	hlist_del_init(&crq->hash);
}

static inline void cfq_add_crq_hash(struct cfq_data *cfqd, struct cfq_rq *crq)
{
	const int hash_idx = CFQ_MHASH_FN(rq_hash_key(crq->request));

	hlist_add_head(&crq->hash, &cfqd->crq_hash[hash_idx]);
}

static struct request *cfq_find_rq_hash(struct cfq_data *cfqd, sector_t offset)
{
	struct hlist_head *hash_list = &cfqd->crq_hash[CFQ_MHASH_FN(offset)];
	struct hlist_node *entry, *next;

	hlist_for_each_safe(entry, next, hash_list) {
		struct cfq_rq *crq = list_entry_hash(entry);
		struct request *__rq = crq->request;

		if (!rq_mergeable(__rq)) {
			cfq_del_crq_hash(crq);
			continue;
		}

		if (rq_hash_key(__rq) == offset)
			return __rq;
	}

	return NULL;
}

Andrew Morton's avatar
Andrew Morton committed
333 334 335 336 337 338
/*
 * 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)
{
339
	if (!cfqd->rq_in_driver && cfqd->busy_queues)
Andrew Morton's avatar
Andrew Morton committed
340 341 342 343 344 345 346
		kblockd_schedule_work(&cfqd->unplug_work);
}

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

347
	return !cfqd->busy_queues;
Andrew Morton's avatar
Andrew Morton committed
348 349
}

Linus Torvalds's avatar
Linus Torvalds committed
350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365
/*
 * 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
 * behind the head are penalized and only allowed to a certain extent.
 */
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;
	int r1_wrap = 0, r2_wrap = 0;	/* requests are behind the disk head */
	unsigned long back_max;

	if (crq1 == NULL || crq1 == crq2)
		return crq2;
	if (crq2 == NULL)
		return crq1;
366 367 368 369

	if (cfq_crq_is_sync(crq1) && !cfq_crq_is_sync(crq2))
		return crq1;
	else if (cfq_crq_is_sync(crq2) && !cfq_crq_is_sync(crq1))
370
		return crq2;
Linus Torvalds's avatar
Linus Torvalds committed
371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436

	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
		r1_wrap = 1;

	if (s2 >= last)
		d2 = s2 - last;
	else if (s2 + back_max >= last)
		d2 = (last - s2) * cfqd->cfq_back_penalty;
	else
		r2_wrap = 1;

	/* Found required data */
	if (!r1_wrap && r2_wrap)
		return crq1;
	else if (!r2_wrap && r1_wrap)
		return crq2;
	else if (r1_wrap && r2_wrap) {
		/* both behind the head */
		if (s1 <= s2)
			return crq1;
		else
			return crq2;
	}

	/* Both requests in front of the head */
	if (d1 < d2)
		return crq1;
	else if (d2 < d1)
		return crq2;
	else {
		if (s1 >= s2)
			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,
		  struct cfq_rq *last)
{
	struct cfq_rq *crq_next = NULL, *crq_prev = NULL;
	struct rb_node *rbnext, *rbprev;

437
	if (!(rbnext = rb_next(&last->rb_node))) {
Linus Torvalds's avatar
Linus Torvalds committed
438
		rbnext = rb_first(&cfqq->sort_list);
439 440 441
		if (rbnext == &last->rb_node)
			rbnext = NULL;
	}
Linus Torvalds's avatar
Linus Torvalds committed
442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460

	rbprev = rb_prev(&last->rb_node);

	if (rbprev)
		crq_prev = rb_entry_crq(rbprev);
	if (rbnext)
		crq_next = rb_entry_crq(rbnext);

	return cfq_choose_req(cfqd, crq_next, crq_prev);
}

static void cfq_update_next_crq(struct cfq_rq *crq)
{
	struct cfq_queue *cfqq = crq->cfq_queue;

	if (cfqq->next_crq == crq)
		cfqq->next_crq = cfq_find_next_crq(cfqq->cfqd, cfqq, crq);
}

461
static void cfq_resort_rr_list(struct cfq_queue *cfqq, int preempted)
Linus Torvalds's avatar
Linus Torvalds committed
462
{
463 464
	struct cfq_data *cfqd = cfqq->cfqd;
	struct list_head *list, *entry;
Linus Torvalds's avatar
Linus Torvalds committed
465

Jens Axboe's avatar
Jens Axboe committed
466
	BUG_ON(!cfq_cfqq_on_rr(cfqq));
Linus Torvalds's avatar
Linus Torvalds committed
467

468
	list_del(&cfqq->cfq_list);
Linus Torvalds's avatar
Linus Torvalds committed
469

470 471 472 473 474 475 476 477 478 479 480 481
	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
482
		if (cfq_cfqq_dispatched(cfqq))
483 484 485
			list = &cfqd->busy_rr;
		else
			list = &cfqd->rr_list[cfqq->ioprio];
Linus Torvalds's avatar
Linus Torvalds committed
486 487
	}

488 489 490 491 492 493
	/*
	 * if queue was preempted, just add to front to be fair. busy_rr
	 * isn't sorted.
	 */
	if (preempted || list == &cfqd->busy_rr) {
		list_add(&cfqq->cfq_list, list);
Linus Torvalds's avatar
Linus Torvalds committed
494
		return;
495
	}
Linus Torvalds's avatar
Linus Torvalds committed
496 497

	/*
498
	 * sort by when queue was last serviced
Linus Torvalds's avatar
Linus Torvalds committed
499
	 */
500 501
	entry = list;
	while ((entry = entry->prev) != list) {
Linus Torvalds's avatar
Linus Torvalds committed
502 503
		struct cfq_queue *__cfqq = list_entry_cfqq(entry);

504 505 506
		if (!__cfqq->service_last)
			break;
		if (time_before(__cfqq->service_last, cfqq->service_last))
Linus Torvalds's avatar
Linus Torvalds committed
507 508 509 510 511 512 513 514
			break;
	}

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

/*
 * add to busy list of queues for service, trying to be fair in ordering
515
 * the pending list according to last request service
Linus Torvalds's avatar
Linus Torvalds committed
516 517
 */
static inline void
518
cfq_add_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
Linus Torvalds's avatar
Linus Torvalds committed
519
{
Jens Axboe's avatar
Jens Axboe committed
520 521
	BUG_ON(cfq_cfqq_on_rr(cfqq));
	cfq_mark_cfqq_on_rr(cfqq);
Linus Torvalds's avatar
Linus Torvalds committed
522 523
	cfqd->busy_queues++;

524
	cfq_resort_rr_list(cfqq, 0);
Linus Torvalds's avatar
Linus Torvalds committed
525 526 527 528 529
}

static inline void
cfq_del_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
{
Jens Axboe's avatar
Jens Axboe committed
530 531
	BUG_ON(!cfq_cfqq_on_rr(cfqq));
	cfq_clear_cfqq_on_rr(cfqq);
532
	list_move(&cfqq->cfq_list, &cfqd->empty_list);
Linus Torvalds's avatar
Linus Torvalds committed
533 534 535 536 537 538 539 540 541 542 543

	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;
544 545
	struct cfq_data *cfqd = cfqq->cfqd;
	const int sync = cfq_crq_is_sync(crq);
Linus Torvalds's avatar
Linus Torvalds committed
546

547 548
	BUG_ON(!cfqq->queued[sync]);
	cfqq->queued[sync]--;
Linus Torvalds's avatar
Linus Torvalds committed
549

550
	cfq_update_next_crq(crq);
Linus Torvalds's avatar
Linus Torvalds committed
551

552 553
	rb_erase(&crq->rb_node, &cfqq->sort_list);
	RB_CLEAR_COLOR(&crq->rb_node);
Linus Torvalds's avatar
Linus Torvalds committed
554

555 556
	if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY(&cfqq->sort_list))
		cfq_del_cfqq_rr(cfqd, cfqq);
Linus Torvalds's avatar
Linus Torvalds committed
557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589
}

static struct cfq_rq *
__cfq_add_crq_rb(struct cfq_rq *crq)
{
	struct rb_node **p = &crq->cfq_queue->sort_list.rb_node;
	struct rb_node *parent = NULL;
	struct cfq_rq *__crq;

	while (*p) {
		parent = *p;
		__crq = rb_entry_crq(parent);

		if (crq->rb_key < __crq->rb_key)
			p = &(*p)->rb_left;
		else if (crq->rb_key > __crq->rb_key)
			p = &(*p)->rb_right;
		else
			return __crq;
	}

	rb_link_node(&crq->rb_node, parent, p);
	return NULL;
}

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;
	struct cfq_rq *__alias;

	crq->rb_key = rq_rb_key(rq);
Jens Axboe's avatar
Jens Axboe committed
590
	cfqq->queued[cfq_crq_is_sync(crq)]++;
Linus Torvalds's avatar
Linus Torvalds committed
591 592 593 594 595 596

	/*
	 * looks a little odd, but the first insert might return an alias.
	 * if that happens, put the alias on the dispatch list
	 */
	while ((__alias = __cfq_add_crq_rb(crq)) != NULL)
597
		cfq_dispatch_insert(cfqd->queue, __alias);
Linus Torvalds's avatar
Linus Torvalds committed
598 599 600

	rb_insert_color(&crq->rb_node, &cfqq->sort_list);

Jens Axboe's avatar
Jens Axboe committed
601
	if (!cfq_cfqq_on_rr(cfqq))
602
		cfq_add_cfqq_rr(cfqd, cfqq);
Linus Torvalds's avatar
Linus Torvalds committed
603 604 605 606 607 608 609 610 611 612

	/*
	 * check if this request is a better next-serve candidate
	 */
	cfqq->next_crq = cfq_choose_req(cfqd, cfqq->next_crq, crq);
}

static inline void
cfq_reposition_crq_rb(struct cfq_queue *cfqq, struct cfq_rq *crq)
{
613 614
	rb_erase(&crq->rb_node, &cfqq->sort_list);
	cfqq->queued[cfq_crq_is_sync(crq)]--;
Linus Torvalds's avatar
Linus Torvalds committed
615 616 617 618

	cfq_add_crq_rb(crq);
}

619 620
static struct request *cfq_find_rq_rb(struct cfq_data *cfqd, sector_t sector)

Linus Torvalds's avatar
Linus Torvalds committed
621
{
Jens Axboe's avatar
Jens Axboe committed
622
	struct cfq_queue *cfqq = cfq_find_cfq_hash(cfqd, current->pid, CFQ_KEY_ANY);
Linus Torvalds's avatar
Linus Torvalds committed
623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643
	struct rb_node *n;

	if (!cfqq)
		goto out;

	n = cfqq->sort_list.rb_node;
	while (n) {
		struct cfq_rq *crq = rb_entry_crq(n);

		if (sector < crq->rb_key)
			n = n->rb_left;
		else if (sector > crq->rb_key)
			n = n->rb_right;
		else
			return crq->request;
	}

out:
	return NULL;
}

644
static void cfq_activate_request(request_queue_t *q, struct request *rq)
Linus Torvalds's avatar
Linus Torvalds committed
645
{
646
	struct cfq_data *cfqd = q->elevator->elevator_data;
Jens Axboe's avatar
Jens Axboe committed
647

648
	cfqd->rq_in_driver++;
Linus Torvalds's avatar
Linus Torvalds committed
649 650
}

651
static void cfq_deactivate_request(request_queue_t *q, struct request *rq)
Linus Torvalds's avatar
Linus Torvalds committed
652
{
653 654 655 656
	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
657 658
}

659
static void cfq_remove_request(struct request *rq)
Linus Torvalds's avatar
Linus Torvalds committed
660 661 662
{
	struct cfq_rq *crq = RQ_DATA(rq);

663 664
	list_del_init(&rq->queuelist);
	cfq_del_crq_rb(crq);
665
	cfq_del_crq_hash(crq);
Linus Torvalds's avatar
Linus Torvalds committed
666 667 668 669 670 671 672 673 674 675
}

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;
	int ret;

	__rq = cfq_find_rq_hash(cfqd, bio->bi_sector);
676 677 678
	if (__rq && elv_rq_merge_ok(__rq, bio)) {
		ret = ELEVATOR_BACK_MERGE;
		goto out;
Linus Torvalds's avatar
Linus Torvalds committed
679 680 681
	}

	__rq = cfq_find_rq_rb(cfqd, bio->bi_sector + bio_sectors(bio));
682 683 684
	if (__rq && elv_rq_merge_ok(__rq, bio)) {
		ret = ELEVATOR_FRONT_MERGE;
		goto out;
Linus Torvalds's avatar
Linus Torvalds committed
685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700
	}

	return ELEVATOR_NO_MERGE;
out:
	*req = __rq;
	return ret;
}

static void cfq_merged_request(request_queue_t *q, struct request *req)
{
	struct cfq_data *cfqd = q->elevator->elevator_data;
	struct cfq_rq *crq = RQ_DATA(req);

	cfq_del_crq_hash(crq);
	cfq_add_crq_hash(cfqd, crq);

701
	if (rq_rb_key(req) != crq->rb_key) {
Linus Torvalds's avatar
Linus Torvalds committed
702 703 704 705 706 707 708 709 710 711 712 713 714
		struct cfq_queue *cfqq = crq->cfq_queue;

		cfq_update_next_crq(crq);
		cfq_reposition_crq_rb(cfqq, crq);
	}
}

static void
cfq_merged_requests(request_queue_t *q, struct request *rq,
		    struct request *next)
{
	cfq_merged_request(q, rq);

715 716 717 718 719 720 721
	/*
	 * 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);

722
	cfq_remove_request(next);
723 724 725 726 727 728 729 730 731 732 733 734 735 736
}

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
737 738 739
		cfq_clear_cfqq_must_alloc_slice(cfqq);
		cfq_clear_cfqq_fifo_expire(cfqq);
		cfq_clear_cfqq_expired(cfqq);
740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778
	}

	cfqd->active_queue = cfqq;
}

/*
 * 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
779
		}
780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796
	} 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
797 798
	}

799 800 801
	return prio;
}

Jens Axboe's avatar
Jens Axboe committed
802
static struct cfq_queue *cfq_set_active_queue(struct cfq_data *cfqd)
803
{
Jens Axboe's avatar
Jens Axboe committed
804 805 806 807 808 809 810 811 812 813
	struct cfq_queue *cfqq;

	/*
	 * if current queue is expired but not done with its requests yet,
	 * wait for that to happen
	 */
	if ((cfqq = cfqd->active_queue) != NULL) {
		if (cfq_cfqq_expired(cfqq) && cfq_cfqq_dispatched(cfqq))
			return NULL;
	}
814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836

	/*
	 * 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);

	/*
	 * 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
837
	return cfqq;
838 839 840 841 842
}

/*
 * current cfqq expired its slice (or was too idle), select new one
 */
Jens Axboe's avatar
Jens Axboe committed
843 844 845
static void
__cfq_slice_expired(struct cfq_data *cfqd, struct cfq_queue *cfqq,
		    int preempted)
846
{
Jens Axboe's avatar
Jens Axboe committed
847
	unsigned long now = jiffies;
848

Jens Axboe's avatar
Jens Axboe committed
849 850
	if (cfq_cfqq_wait_request(cfqq))
		del_timer(&cfqd->idle_slice_timer);
851

Jens Axboe's avatar
Jens Axboe committed
852 853
	if (!preempted && !cfq_cfqq_dispatched(cfqq))
		cfqq->service_last = now;
854

Jens Axboe's avatar
Jens Axboe committed
855 856
	cfq_clear_cfqq_must_dispatch(cfqq);
	cfq_clear_cfqq_wait_request(cfqq);
857

Jens Axboe's avatar
Jens Axboe committed
858 859 860 861
	/*
	 * store what was left of this slice, if the queue idled out
	 * or was preempted
	 */
862 863
	if (time_after(cfqq->slice_end, now))
		cfqq->slice_left = cfqq->slice_end - now;
Jens Axboe's avatar
Jens Axboe committed
864 865
	else
		cfqq->slice_left = 0;
866

Jens Axboe's avatar
Jens Axboe committed
867 868
	if (cfq_cfqq_on_rr(cfqq))
		cfq_resort_rr_list(cfqq, preempted);
869

Jens Axboe's avatar
Jens Axboe committed
870
	if (cfqq == cfqd->active_queue)
871 872
		cfqd->active_queue = NULL;

Jens Axboe's avatar
Jens Axboe committed
873 874 875
	if (cfqd->active_cic) {
		put_io_context(cfqd->active_cic->ioc);
		cfqd->active_cic = NULL;
876 877 878 879 880
	}

	cfqd->dispatch_slice = 0;
}

Jens Axboe's avatar
Jens Axboe committed
881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896
static inline void cfq_slice_expired(struct cfq_data *cfqd, int preempted)
{
	struct cfq_queue *cfqq = cfqd->active_queue;

	if (cfqq) {
		/*
		 * use deferred expiry, if there are requests in progress as
		 * not to disturb the slice of the next queue
		 */
		if (cfq_cfqq_dispatched(cfqq))
			cfq_mark_cfqq_expired(cfqq);
		else
			__cfq_slice_expired(cfqd, cfqq, preempted);
	}
}

897 898 899 900 901 902 903 904 905 906 907
static int cfq_arm_slice_timer(struct cfq_data *cfqd, struct cfq_queue *cfqq)

{
	WARN_ON(!RB_EMPTY(&cfqq->sort_list));
	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
908
	if (!cfq_cfqq_idle_window(cfqq))
909 910 911 912 913 914 915
		return 0;
	/*
	 * task has exited, don't wait
	 */
	if (cfqd->active_cic && !cfqd->active_cic->ioc->task)
		return 0;

Jens Axboe's avatar
Jens Axboe committed
916 917
	cfq_mark_cfqq_must_dispatch(cfqq);
	cfq_mark_cfqq_wait_request(cfqq);
918 919

	if (!timer_pending(&cfqd->idle_slice_timer)) {
Jens Axboe's avatar
Jens Axboe committed
920
		unsigned long slice_left = min(cfqq->slice_end - 1, (unsigned long) cfqd->cfq_slice_idle);
921

Jens Axboe's avatar
Jens Axboe committed
922
		cfqd->idle_slice_timer.expires = jiffies + slice_left;
923 924 925 926
		add_timer(&cfqd->idle_slice_timer);
	}

	return 1;
Linus Torvalds's avatar
Linus Torvalds committed
927 928
}

929
static void cfq_dispatch_insert(request_queue_t *q, struct cfq_rq *crq)
Linus Torvalds's avatar
Linus Torvalds committed
930 931 932
{
	struct cfq_data *cfqd = q->elevator->elevator_data;
	struct cfq_queue *cfqq = crq->cfq_queue;
933 934

	cfqq->next_crq = cfq_find_next_crq(cfqd, cfqq, crq);
935
	cfq_remove_request(crq->request);
Jens Axboe's avatar
Jens Axboe committed
936
	cfqq->on_dispatch[cfq_crq_is_sync(crq)]++;
937
	elv_dispatch_sort(q, crq->request);
Linus Torvalds's avatar
Linus Torvalds committed
938 939 940 941 942 943 944 945
}

/*
 * 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;
946
	struct request *rq;
Linus Torvalds's avatar
Linus Torvalds committed
947 948
	struct cfq_rq *crq;

Jens Axboe's avatar
Jens Axboe committed
949
	if (cfq_cfqq_fifo_expire(cfqq))
Linus Torvalds's avatar
Linus Torvalds committed
950 951
		return NULL;

952
	if (!list_empty(&cfqq->fifo)) {
Jens Axboe's avatar
Jens Axboe committed
953
		int fifo = cfq_cfqq_class_sync(cfqq);
Linus Torvalds's avatar
Linus Torvalds committed
954

955 956 957
		crq = RQ_DATA(list_entry_fifo(cfqq->fifo.next));
		rq = crq->request;
		if (time_after(jiffies, rq->start_time + cfqd->cfq_fifo_expire[fifo])) {
Jens Axboe's avatar
Jens Axboe committed
958
			cfq_mark_cfqq_fifo_expire(cfqq);
959 960
			return crq;
		}
Linus Torvalds's avatar
Linus Torvalds committed
961 962 963 964 965 966
	}

	return NULL;
}

/*
Jens Axboe's avatar
Jens Axboe committed
967 968 969
 * 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
970
 */
971 972 973 974 975 976 977 978 979 980
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
981
static inline void
982
cfq_set_prio_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
Linus Torvalds's avatar
Linus Torvalds committed
983
{
984 985
	cfqq->slice_end = cfq_prio_to_slice(cfqd, cfqq) + jiffies;
}
Linus Torvalds's avatar
Linus Torvalds committed
986

987 988 989 990
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
991

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

994
	return 2 * (base_rq + base_rq * (CFQ_PRIO_LISTS - 1 - cfqq->ioprio));
Linus Torvalds's avatar
Linus Torvalds committed
995 996
}

997 998 999
/*
 * get next queue for service
 */
1000
static struct cfq_queue *cfq_select_queue(struct cfq_data *cfqd)
Linus Torvalds's avatar
Linus Torvalds committed
1001
{
1002
	unsigned long now = jiffies;
Linus Torvalds's avatar
Linus Torvalds committed
1003 1004
	struct cfq_queue *cfqq;

1005 1006 1007
	cfqq = cfqd->active_queue;
	if (!cfqq)
		goto new_queue;
Linus Torvalds's avatar
Linus Torvalds committed
1008

Jens Axboe's avatar
Jens Axboe committed
1009 1010 1011
	if (cfq_cfqq_expired(cfqq))
		goto new_queue;

1012 1013 1014
	/*
	 * slice has expired
	 */
Jens Axboe's avatar
Jens Axboe committed
1015 1016
	if (!cfq_cfqq_must_dispatch(cfqq) && time_after(now, cfqq->slice_end))
		goto expire;
Linus Torvalds's avatar
Linus Torvalds committed
1017

1018 1019 1020 1021 1022 1023
	/*
	 * if queue has requests, dispatch one. if not, check if
	 * enough slice is left to wait for one
	 */
	if (!RB_EMPTY(&cfqq->sort_list))
		goto keep_queue;
1024
	else if (cfq_cfqq_class_sync(cfqq) &&
1025 1026 1027 1028 1029
		 time_before(now, cfqq->slice_end)) {
		if (cfq_arm_slice_timer(cfqd, cfqq))
			return NULL;
	}

Jens Axboe's avatar
Jens Axboe committed
1030
expire:
1031
	cfq_slice_expired(cfqd, 0);
Jens Axboe's avatar
Jens Axboe committed
1032 1033
new_queue:
	cfqq = cfq_set_active_queue(cfqd);
1034
keep_queue:
Jens Axboe's avatar
Jens Axboe committed
1035
	return cfqq;
1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047
}

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

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

	do {
		struct cfq_rq *crq;
Linus Torvalds's avatar
Linus Torvalds committed
1048 1049

		/*
1050
		 * follow expired path, else get first next available
Linus Torvalds's avatar
Linus Torvalds committed
1051
		 */
1052 1053 1054 1055 1056 1057
		if ((crq = cfq_check_fifo(cfqq)) == NULL)
			crq = cfqq->next_crq;

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

1060 1061
		cfqd->dispatch_slice++;
		dispatched++;
Linus Torvalds's avatar
Linus Torvalds committed
1062

1063 1064 1065 1066
		if (!cfqd->active_cic) {
			atomic_inc(&crq->io_context->ioc->refcount);
			cfqd->active_cic = crq->io_context;
		}
Linus Torvalds's avatar
Linus Torvalds committed
1067

1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091
		if (RB_EMPTY(&cfqq->sort_list))
			break;

	} while (dispatched < max_dispatch);

	/*
	 * if slice end isn't set yet, set it. if at least one request was
	 * sync, use the sync time slice value
	 */
	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)) ||
	    cfq_class_idle(cfqq))
		cfq_slice_expired(cfqd, 0);

	return dispatched;
}

1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127
static int
cfq_forced_dispatch_cfqqs(struct list_head *list)
{
	int dispatched = 0;
	struct cfq_queue *cfqq, *next;
	struct cfq_rq *crq;

	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));
	}
	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;
}

1128
static int
1129
cfq_dispatch_requests(request_queue_t *q, int force)
1130 1131 1132 1133 1134 1135 1136
{
	struct cfq_data *cfqd = q->elevator->elevator_data;
	struct cfq_queue *cfqq;

	if (!cfqd->busy_queues)
		return 0;

1137 1138 1139 1140
	if (unlikely(force))
		return cfq_forced_dispatch(cfqd);

	cfqq = cfq_select_queue(cfqd);
1141
	if (cfqq) {
1142 1143 1144 1145 1146 1147 1148 1149 1150
		int max_dispatch;

		/*
		 * if idle window is disabled, allow queue buildup
		 */
		if (!cfq_cfqq_idle_window(cfqq) &&
		    cfqd->rq_in_driver >= cfqd->cfq_max_depth)
			return 0;

Jens Axboe's avatar
Jens Axboe committed
1151 1152
		cfq_clear_cfqq_must_dispatch(cfqq);
		cfq_clear_cfqq_wait_request(cfqq);
1153 1154
		del_timer(&cfqd->idle_slice_timer);

1155 1156 1157
		max_dispatch = cfqd->cfq_quantum;
		if (cfq_class_idle(cfqq))
			max_dispatch = 1;
Linus Torvalds's avatar
Linus Torvalds committed
1158

1159
		return __cfq_dispatch_requests(cfqd, cfqq, max_dispatch);
Linus Torvalds's avatar
Linus Torvalds committed
1160 1161
	}

1162
	return 0;
Linus Torvalds's avatar
Linus Torvalds committed
1163 1164 1165 1166 1167 1168 1169 1170 1171 1172
}

/*
 * 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)
{
1173 1174 1175
	struct cfq_data *cfqd = cfqq->cfqd;

	BUG_ON(atomic_read(&cfqq->ref) <= 0);
Linus Torvalds's avatar
Linus Torvalds committed
1176 1177 1178 1179 1180

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

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

1184
	if (unlikely(cfqd->active_queue == cfqq)) {
Jens Axboe's avatar
Jens Axboe committed
1185 1186
		__cfq_slice_expired(cfqd, cfqq, 0);
		cfq_schedule_dispatch(cfqd);
1187 1188
	}

Linus Torvalds's avatar
Linus Torvalds committed
1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199
	cfq_put_cfqd(cfqq->cfqd);

	/*
	 * 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
1200 1201
__cfq_find_cfq_hash(struct cfq_data *cfqd, unsigned int key, unsigned int prio,
		    const int hashval)
Linus Torvalds's avatar
Linus Torvalds committed
1202 1203 1204 1205 1206 1207
{
	struct hlist_head *hash_list = &cfqd->cfq_hash[hashval];
	struct hlist_node *entry, *next;

	hlist_for_each_safe(entry, next, hash_list) {
		struct cfq_queue *__cfqq = list_entry_qhash(entry);
Jens Axboe's avatar
Jens Axboe committed
1208
		const unsigned short __p = IOPRIO_PRIO_VALUE(__cfqq->ioprio_class, __cfqq->ioprio);
Linus Torvalds's avatar
Linus Torvalds committed
1209

Jens Axboe's avatar
Jens Axboe committed
1210
		if (__cfqq->key == key && (__p == prio || prio == CFQ_KEY_ANY))
Linus Torvalds's avatar
Linus Torvalds committed
1211 1212 1213 1214 1215 1216 1217
			return __cfqq;
	}

	return NULL;
}

static struct cfq_queue *
Jens Axboe's avatar
Jens Axboe committed
1218
cfq_find_cfq_hash(struct cfq_data *cfqd, unsigned int key, unsigned short prio)
Linus Torvalds's avatar
Linus Torvalds committed
1219
{
Jens Axboe's avatar
Jens Axboe committed
1220
	return __cfq_find_cfq_hash(cfqd, key, prio, hash_long(key, CFQ_QHASH_SHIFT));
Linus Torvalds's avatar
Linus Torvalds committed
1221 1222
}

1223
static void cfq_free_io_context(struct cfq_io_context *cic)
Linus Torvalds's avatar
Linus Torvalds committed
1224
{
1225 1226
	struct cfq_io_context *__cic;
	struct list_head *entry, *next;
Linus Torvalds's avatar
Linus Torvalds committed
1227

1228 1229 1230
	list_for_each_safe(entry, next, &cic->list) {
		__cic = list_entry(entry, struct cfq_io_context, list);
		kmem_cache_free(cfq_ioc_pool, __cic);
Linus Torvalds's avatar
Linus Torvalds committed
1231 1232
	}

1233
	kmem_cache_free(cfq_ioc_pool, cic);
Linus Torvalds's avatar
Linus Torvalds committed
1234 1235
}

1236 1237 1238 1239
/*
 * Called with interrupts disabled
 */
static void cfq_exit_single_io_context(struct cfq_io_context *cic)
Linus Torvalds's avatar
Linus Torvalds committed
1240
{
1241 1242 1243 1244 1245 1246 1247 1248
	struct cfq_data *cfqd = cic->cfqq->cfqd;
	request_queue_t *q = cfqd->queue;

	WARN_ON(!irqs_disabled());

	spin_lock(q->queue_lock);

	if (unlikely(cic->cfqq == cfqd->active_queue)) {
Jens Axboe's avatar
Jens Axboe committed
1249 1250
		__cfq_slice_expired(cfqd, cic->cfqq, 0);
		cfq_schedule_dispatch(cfqd);
1251 1252 1253 1254 1255
	}

	cfq_put_queue(cic->cfqq);
	cic->cfqq = NULL;
	spin_unlock(q->queue_lock);
Linus Torvalds's avatar
Linus Torvalds committed
1256 1257 1258
}

/*
1259 1260
 * Another task may update the task cic list, if it is doing a queue lookup
 * on its behalf. cfq_cic_lock excludes such concurrent updates
Linus Torvalds's avatar
Linus Torvalds committed
1261 1262 1263
 */
static void cfq_exit_io_context(struct cfq_io_context *cic)
{
1264 1265
	struct cfq_io_context *__cic;
	struct list_head *entry;
Linus Torvalds's avatar
Linus Torvalds committed
1266 1267
	unsigned long flags;

1268 1269
	local_irq_save(flags);

Linus Torvalds's avatar
Linus Torvalds committed
1270 1271 1272
	/*
	 * put the reference this task is holding to the various queues
	 */
1273
	list_for_each(entry, &cic->list) {
Linus Torvalds's avatar
Linus Torvalds committed
1274
		__cic = list_entry(entry, struct cfq_io_context, list);
1275
		cfq_exit_single_io_context(__cic);
Linus Torvalds's avatar
Linus Torvalds committed
1276 1277
	}

1278 1279
	cfq_exit_single_io_context(cic);
	local_irq_restore(flags);
Linus Torvalds's avatar
Linus Torvalds committed
1280 1281
}

1282
static struct cfq_io_context *
Al Viro's avatar
Al Viro committed
1283
cfq_alloc_io_context(struct cfq_data *cfqd, gfp_t gfp_mask)
Linus Torvalds's avatar
Linus Torvalds committed
1284
{
1285
	struct cfq_io_context *cic = kmem_cache_alloc(cfq_ioc_pool, gfp_mask);
Linus Torvalds's avatar
Linus Torvalds committed
1286 1287 1288 1289

	if (cic) {
		INIT_LIST_HEAD(&cic->list);
		cic->cfqq = NULL;
1290 1291 1292 1293 1294 1295 1296
		cic->key = NULL;
		cic->last_end_request = jiffies;
		cic->ttime_total = 0;
		cic->ttime_samples = 0;
		cic->ttime_mean = 0;
		cic->dtor = cfq_free_io_context;
		cic->exit = cfq_exit_io_context;
Linus Torvalds's avatar
Linus Torvalds committed
1297 1298 1299 1300 1301
	}

	return cic;
}

1302 1303 1304 1305 1306
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
1307
	if (!cfq_cfqq_prio_changed(cfqq))
1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331
		return;

	ioprio_class = IOPRIO_PRIO_CLASS(tsk->ioprio);
	switch (ioprio_class) {
		default:
			printk(KERN_ERR "cfq: bad prio %x\n", ioprio_class);
		case IOPRIO_CLASS_NONE:
			/*
			 * no prio set, place us in the middle of the BE classes
			 */
			cfqq->ioprio = task_nice_ioprio(tsk);
			cfqq->ioprio_class = IOPRIO_CLASS_BE;
			break;
		case IOPRIO_CLASS_RT:
			cfqq->ioprio = task_ioprio(tsk);
			cfqq->ioprio_class = IOPRIO_CLASS_RT;
			break;
		case IOPRIO_CLASS_BE:
			cfqq->ioprio = task_ioprio(tsk);
			cfqq->ioprio_class = IOPRIO_CLASS_BE;
			break;
		case IOPRIO_CLASS_IDLE:
			cfqq->ioprio_class = IOPRIO_CLASS_IDLE;
			cfqq->ioprio = 7;
Jens Axboe's avatar
Jens Axboe committed
1332
			cfq_clear_cfqq_idle_window(cfqq);
1333 1334 1335 1336 1337 1338 1339 1340 1341 1342
			break;
	}

	/*
	 * keep track of original prio settings in case we have to temporarily
	 * elevate the priority of this queue
	 */
	cfqq->org_ioprio = cfqq->ioprio;
	cfqq->org_ioprio_class = cfqq->ioprio_class;

Jens Axboe's avatar
Jens Axboe committed
1343
	if (cfq_cfqq_on_rr(cfqq))
1344 1345
		cfq_resort_rr_list(cfqq, 0);

Jens Axboe's avatar
Jens Axboe committed
1346
	cfq_clear_cfqq_prio_changed(cfqq);
1347 1348 1349 1350 1351 1352 1353 1354
}

static inline void changed_ioprio(struct cfq_queue *cfqq)
{
	if (cfqq) {
		struct cfq_data *cfqd = cfqq->cfqd;

		spin_lock(cfqd->queue->queue_lock);
Jens Axboe's avatar
Jens Axboe committed
1355
		cfq_mark_cfqq_prio_changed(cfqq);
1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376
		cfq_init_prio_data(cfqq);
		spin_unlock(cfqd->queue->queue_lock);
	}
}

/*
 * callback from sys_ioprio_set, irqs are disabled
 */
static int cfq_ioc_set_ioprio(struct io_context *ioc, unsigned int ioprio)
{
	struct cfq_io_context *cic = ioc->cic;

	changed_ioprio(cic->cfqq);

	list_for_each_entry(cic, &cic->list, list)
		changed_ioprio(cic->cfqq);

	return 0;
}

static struct cfq_queue *
Jens Axboe's avatar
Jens Axboe committed
1377
cfq_get_queue(struct cfq_data *cfqd, unsigned int key, unsigned short ioprio,
Al Viro's avatar
Al Viro committed
1378
	      gfp_t gfp_mask)
1379 1380 1381 1382 1383
{
	const int hashval = hash_long(key, CFQ_QHASH_SHIFT);
	struct cfq_queue *cfqq, *new_cfqq = NULL;

retry:
Jens Axboe's avatar
Jens Axboe committed
1384
	cfqq = __cfq_find_cfq_hash(cfqd, key, ioprio, hashval);
1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417

	if (!cfqq) {
		if (new_cfqq) {
			cfqq = new_cfqq;
			new_cfqq = NULL;
		} else if (gfp_mask & __GFP_WAIT) {
			spin_unlock_irq(cfqd->queue->queue_lock);
			new_cfqq = kmem_cache_alloc(cfq_pool, gfp_mask);
			spin_lock_irq(cfqd->queue->queue_lock);
			goto retry;
		} else {
			cfqq = kmem_cache_alloc(cfq_pool, gfp_mask);
			if (!cfqq)
				goto out;
		}

		memset(cfqq, 0, sizeof(*cfqq));

		INIT_HLIST_NODE(&cfqq->cfq_hash