cfq-iosched.c 57.4 KB
Newer Older
Linus Torvalds's avatar
Linus Torvalds committed
1 2 3 4 5 6 7 8 9 10
/*
 *  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/config.h>
#include <linux/module.h>
Al Viro's avatar
Al Viro committed
11 12
#include <linux/blkdev.h>
#include <linux/elevator.h>
Linus Torvalds's avatar
Linus Torvalds committed
13 14
#include <linux/hash.h>
#include <linux/rbtree.h>
15
#include <linux/ioprio.h>
Linus Torvalds's avatar
Linus Torvalds committed
16 17 18 19

/*
 * tunables
 */
20 21 22 23 24
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
25

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

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

#define CFQ_KEY_ASYNC		(0)

36
static DEFINE_SPINLOCK(cfq_exit_lock);
37

Linus Torvalds's avatar
Linus Torvalds committed
38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
/*
 * 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)
56
#define list_entry_fifo(ptr)	list_entry((ptr), struct request, queuelist)
Linus Torvalds's avatar
Linus Torvalds committed
57 58 59 60 61 62 63 64

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

/*
 * rb-tree defines
 */
#define RB_EMPTY(node)		((node)->rb_node == NULL)
#define RB_CLEAR(node)		do {	\
65
		memset(node, 0, sizeof(*node)); \
Linus Torvalds's avatar
Linus Torvalds committed
66 67 68 69 70 71 72 73 74
} 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;

75 76 77
static atomic_t ioc_count = ATOMIC_INIT(0);
static struct completion *ioc_gone;

78 79 80 81 82
#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
83 84 85 86 87 88 89 90 91 92
#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])
93

94 95
#define sample_valid(samples)	((samples) > 80)

96 97 98
/*
 * Per block device queue structure
 */
Linus Torvalds's avatar
Linus Torvalds committed
99
struct cfq_data {
100 101 102 103 104 105 106 107 108 109 110 111 112 113
	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
114 115
	struct list_head empty_list;

116 117 118
	/*
	 * cfqq lookup hash
	 */
Linus Torvalds's avatar
Linus Torvalds committed
119 120
	struct hlist_head *cfq_hash;

121 122 123 124
	/*
	 * global crq hash for all queues
	 */
	struct hlist_head *crq_hash;
Linus Torvalds's avatar
Linus Torvalds committed
125

126
	mempool_t *crq_pool;
Linus Torvalds's avatar
Linus Torvalds committed
127

128
	int rq_in_driver;
129
	int hw_tag;
Linus Torvalds's avatar
Linus Torvalds committed
130

131 132 133 134 135 136 137 138
	/*
	 * 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
139

140 141 142 143 144 145
	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
146 147

	sector_t last_sector;
148
	unsigned long last_end_request;
Linus Torvalds's avatar
Linus Torvalds committed
149

150
	unsigned int rq_starved;
Linus Torvalds's avatar
Linus Torvalds committed
151 152 153 154 155 156

	/*
	 * tunables, see top of file
	 */
	unsigned int cfq_quantum;
	unsigned int cfq_queued;
157
	unsigned int cfq_fifo_expire[2];
Linus Torvalds's avatar
Linus Torvalds committed
158 159
	unsigned int cfq_back_penalty;
	unsigned int cfq_back_max;
160 161 162
	unsigned int cfq_slice[2];
	unsigned int cfq_slice_async_rq;
	unsigned int cfq_slice_idle;
163 164

	struct list_head cic_list;
Linus Torvalds's avatar
Linus Torvalds committed
165 166
};

167 168 169
/*
 * Per process-grouping structure
 */
Linus Torvalds's avatar
Linus Torvalds committed
170 171 172 173 174
struct cfq_queue {
	/* reference count */
	atomic_t ref;
	/* parent cfq_data */
	struct cfq_data *cfqd;
175
	/* cfqq lookup hash */
Linus Torvalds's avatar
Linus Torvalds committed
176 177
	struct hlist_node cfq_hash;
	/* hash key */
178
	unsigned int key;
Linus Torvalds's avatar
Linus Torvalds committed
179 180 181 182 183 184 185 186 187 188 189
	/* 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 */
190
	struct list_head fifo;
Linus Torvalds's avatar
Linus Torvalds committed
191

192 193 194 195
	unsigned long slice_start;
	unsigned long slice_end;
	unsigned long slice_left;
	unsigned long service_last;
Linus Torvalds's avatar
Linus Torvalds committed
196

Jens Axboe's avatar
Jens Axboe committed
197 198
	/* number of requests that are on the dispatch list */
	int on_dispatch[2];
199 200 201 202 203

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

Jens Axboe's avatar
Jens Axboe committed
204 205
	/* various state flags, see below */
	unsigned int flags;
Linus Torvalds's avatar
Linus Torvalds committed
206 207 208 209 210 211 212 213 214 215 216
};

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
217
	unsigned int crq_flags;
Linus Torvalds's avatar
Linus Torvalds committed
218 219
};

Jens Axboe's avatar
Jens Axboe committed
220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255
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

enum cfq_rq_state_flags {
256
	CFQ_CRQ_FLAG_is_sync = 0,
Jens Axboe's avatar
Jens Axboe committed
257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276
};

#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);
277
static void cfq_dispatch_insert(request_queue_t *, struct cfq_rq *);
278
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
279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315

/*
 * 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
316 317 318 319 320 321
/*
 * 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)
{
322
	if (cfqd->busy_queues)
Andrew Morton's avatar
Andrew Morton committed
323 324 325 326 327 328 329
		kblockd_schedule_work(&cfqd->unplug_work);
}

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

330
	return !cfqd->busy_queues;
Andrew Morton's avatar
Andrew Morton committed
331 332
}

333 334
static inline pid_t cfq_queue_pid(struct task_struct *task, int rw)
{
Jens Axboe's avatar
Jens Axboe committed
335
	if (rw == READ || rw == WRITE_SYNC)
336 337 338 339 340
		return task->pid;

	return CFQ_KEY_ASYNC;
}

Linus Torvalds's avatar
Linus Torvalds committed
341 342 343
/*
 * 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
344
 * behind the head is penalized and only allowed to a certain extent.
Linus Torvalds's avatar
Linus Torvalds committed
345 346 347 348 349 350
 */
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;
351 352 353
#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
354 355 356 357 358

	if (crq1 == NULL || crq1 == crq2)
		return crq2;
	if (crq2 == NULL)
		return crq1;
359 360 361 362

	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))
363
		return crq2;
Linus Torvalds's avatar
Linus Torvalds committed
364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384

	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
385
		wrap |= CFQ_RQ1_WRAP;
Linus Torvalds's avatar
Linus Torvalds committed
386 387 388 389 390 391

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

	/* Found required data */
395 396 397 398 399 400 401 402

	/*
	 * 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
403
			return crq1;
404
		else if (d2 < d1)
Linus Torvalds's avatar
Linus Torvalds committed
405
			return crq2;
406 407 408 409 410 411
		else {
			if (s1 >= s2)
				return crq1;
			else
				return crq2;
		}
Linus Torvalds's avatar
Linus Torvalds committed
412

413
	case CFQ_RQ2_WRAP:
Linus Torvalds's avatar
Linus Torvalds committed
414
		return crq1;
415
	case CFQ_RQ1_WRAP:
Linus Torvalds's avatar
Linus Torvalds committed
416
		return crq2;
417 418 419 420 421 422 423 424 425
	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
426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441
			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;

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

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

466
static void cfq_resort_rr_list(struct cfq_queue *cfqq, int preempted)
Linus Torvalds's avatar
Linus Torvalds committed
467
{
468 469
	struct cfq_data *cfqd = cfqq->cfqd;
	struct list_head *list, *entry;
Linus Torvalds's avatar
Linus Torvalds committed
470

Jens Axboe's avatar
Jens Axboe committed
471
	BUG_ON(!cfq_cfqq_on_rr(cfqq));
Linus Torvalds's avatar
Linus Torvalds committed
472

473
	list_del(&cfqq->cfq_list);
Linus Torvalds's avatar
Linus Torvalds committed
474

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

493 494
	/*
	 * if queue was preempted, just add to front to be fair. busy_rr
495
	 * isn't sorted, but insert at the back for fairness.
496 497
	 */
	if (preempted || list == &cfqd->busy_rr) {
498 499 500 501
		if (preempted)
			list = list->prev;

		list_add_tail(&cfqq->cfq_list, list);
Linus Torvalds's avatar
Linus Torvalds committed
502
		return;
503
	}
Linus Torvalds's avatar
Linus Torvalds committed
504 505

	/*
506
	 * sort by when queue was last serviced
Linus Torvalds's avatar
Linus Torvalds committed
507
	 */
508 509
	entry = list;
	while ((entry = entry->prev) != list) {
Linus Torvalds's avatar
Linus Torvalds committed
510 511
		struct cfq_queue *__cfqq = list_entry_cfqq(entry);

512 513 514
		if (!__cfqq->service_last)
			break;
		if (time_before(__cfqq->service_last, cfqq->service_last))
Linus Torvalds's avatar
Linus Torvalds committed
515 516 517 518 519 520 521 522
			break;
	}

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

/*
 * add to busy list of queues for service, trying to be fair in ordering
523
 * the pending list according to last request service
Linus Torvalds's avatar
Linus Torvalds committed
524 525
 */
static inline void
526
cfq_add_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
Linus Torvalds's avatar
Linus Torvalds committed
527
{
Jens Axboe's avatar
Jens Axboe committed
528 529
	BUG_ON(cfq_cfqq_on_rr(cfqq));
	cfq_mark_cfqq_on_rr(cfqq);
Linus Torvalds's avatar
Linus Torvalds committed
530 531
	cfqd->busy_queues++;

532
	cfq_resort_rr_list(cfqq, 0);
Linus Torvalds's avatar
Linus Torvalds committed
533 534 535 536 537
}

static inline void
cfq_del_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
{
Jens Axboe's avatar
Jens Axboe committed
538 539
	BUG_ON(!cfq_cfqq_on_rr(cfqq));
	cfq_clear_cfqq_on_rr(cfqq);
540
	list_move(&cfqq->cfq_list, &cfqd->empty_list);
Linus Torvalds's avatar
Linus Torvalds committed
541 542 543 544 545 546 547 548 549 550 551

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

555 556
	BUG_ON(!cfqq->queued[sync]);
	cfqq->queued[sync]--;
Linus Torvalds's avatar
Linus Torvalds committed
557

558
	cfq_update_next_crq(crq);
Linus Torvalds's avatar
Linus Torvalds committed
559

560
	rb_erase(&crq->rb_node, &cfqq->sort_list);
Linus Torvalds's avatar
Linus Torvalds committed
561

562 563
	if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY(&cfqq->sort_list))
		cfq_del_cfqq_rr(cfqd, cfqq);
Linus Torvalds's avatar
Linus Torvalds committed
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 590 591 592 593 594 595 596
}

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
597
	cfqq->queued[cfq_crq_is_sync(crq)]++;
Linus Torvalds's avatar
Linus Torvalds committed
598 599 600 601 602 603

	/*
	 * 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)
604
		cfq_dispatch_insert(cfqd->queue, __alias);
Linus Torvalds's avatar
Linus Torvalds committed
605 606 607

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

Jens Axboe's avatar
Jens Axboe committed
608
	if (!cfq_cfqq_on_rr(cfqq))
609
		cfq_add_cfqq_rr(cfqd, cfqq);
Linus Torvalds's avatar
Linus Torvalds committed
610 611 612 613 614 615 616 617 618 619

	/*
	 * 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)
{
620 621
	rb_erase(&crq->rb_node, &cfqq->sort_list);
	cfqq->queued[cfq_crq_is_sync(crq)]--;
Linus Torvalds's avatar
Linus Torvalds committed
622 623 624 625

	cfq_add_crq_rb(crq);
}

626 627
static struct request *
cfq_find_rq_fmerge(struct cfq_data *cfqd, struct bio *bio)
Linus Torvalds's avatar
Linus Torvalds committed
628
{
629 630 631
	struct task_struct *tsk = current;
	pid_t key = cfq_queue_pid(tsk, bio_data_dir(bio));
	struct cfq_queue *cfqq;
Linus Torvalds's avatar
Linus Torvalds committed
632
	struct rb_node *n;
633
	sector_t sector;
Linus Torvalds's avatar
Linus Torvalds committed
634

635
	cfqq = cfq_find_cfq_hash(cfqd, key, tsk->ioprio);
Linus Torvalds's avatar
Linus Torvalds committed
636 637 638
	if (!cfqq)
		goto out;

639
	sector = bio->bi_sector + bio_sectors(bio);
Linus Torvalds's avatar
Linus Torvalds committed
640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655
	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;
}

656
static void cfq_activate_request(request_queue_t *q, struct request *rq)
Linus Torvalds's avatar
Linus Torvalds committed
657
{
658
	struct cfq_data *cfqd = q->elevator->elevator_data;
Jens Axboe's avatar
Jens Axboe committed
659

660
	cfqd->rq_in_driver++;
661 662 663 664 665 666 667 668 669

	/*
	 * 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
670 671
}

672
static void cfq_deactivate_request(request_queue_t *q, struct request *rq)
Linus Torvalds's avatar
Linus Torvalds committed
673
{
674 675 676 677
	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
678 679
}

680
static void cfq_remove_request(struct request *rq)
Linus Torvalds's avatar
Linus Torvalds committed
681 682 683
{
	struct cfq_rq *crq = RQ_DATA(rq);

684 685
	list_del_init(&rq->queuelist);
	cfq_del_crq_rb(crq);
686
	cfq_del_crq_hash(crq);
Linus Torvalds's avatar
Linus Torvalds committed
687 688 689 690 691 692 693 694 695 696
}

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);
697 698 699
	if (__rq && elv_rq_merge_ok(__rq, bio)) {
		ret = ELEVATOR_BACK_MERGE;
		goto out;
Linus Torvalds's avatar
Linus Torvalds committed
700 701
	}

702
	__rq = cfq_find_rq_fmerge(cfqd, bio);
703 704 705
	if (__rq && elv_rq_merge_ok(__rq, bio)) {
		ret = ELEVATOR_FRONT_MERGE;
		goto out;
Linus Torvalds's avatar
Linus Torvalds committed
706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721
	}

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

722
	if (rq_rb_key(req) != crq->rb_key) {
Linus Torvalds's avatar
Linus Torvalds committed
723 724 725 726 727 728 729 730 731 732 733 734 735
		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);

736 737 738 739 740 741 742
	/*
	 * 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);

743
	cfq_remove_request(next);
744 745 746 747 748 749 750 751 752 753 754 755 756 757
}

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
758 759
		cfq_clear_cfqq_must_alloc_slice(cfqq);
		cfq_clear_cfqq_fifo_expire(cfqq);
760 761 762 763 764
	}

	cfqd->active_queue = cfqq;
}

765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815
/*
 * 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);
}

816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849
/*
 * 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
850
		}
851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867
	} 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
868 869
	}

870 871 872
	return prio;
}

Jens Axboe's avatar
Jens Axboe committed
873
static struct cfq_queue *cfq_set_active_queue(struct cfq_data *cfqd)
874
{
875
	struct cfq_queue *cfqq = NULL;
876 877 878 879 880 881 882 883

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

884 885 886 887 888 889 890
	/*
	 * 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);

891 892 893 894 895 896 897 898 899 900 901 902 903 904 905
	/*
	 * 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
906
	return cfqq;
907 908 909 910 911
}

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

{
912
	struct cfq_io_context *cic;
913 914
	unsigned long sl;

915 916 917 918 919 920 921 922
	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
923
	if (!cfq_cfqq_idle_window(cfqq))
924 925 926 927
		return 0;
	/*
	 * task has exited, don't wait
	 */
928 929
	cic = cfqd->active_cic;
	if (!cic || !cic->ioc->task)
930 931
		return 0;

Jens Axboe's avatar
Jens Axboe committed
932 933
	cfq_mark_cfqq_must_dispatch(cfqq);
	cfq_mark_cfqq_wait_request(cfqq);
934

935
	sl = min(cfqq->slice_end - 1, (unsigned long) cfqd->cfq_slice_idle);
936 937 938 939 940 941 942 943 944

	/*
	 * 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
	 */
	if (sample_valid(cic->seek_samples) && cic->seek_mean > 131072)
		sl = 2;

945
	mod_timer(&cfqd->idle_slice_timer, jiffies + sl);
946
	return 1;
Linus Torvalds's avatar
Linus Torvalds committed
947 948
}

949
static void cfq_dispatch_insert(request_queue_t *q, struct cfq_rq *crq)
Linus Torvalds's avatar
Linus Torvalds committed
950 951 952
{
	struct cfq_data *cfqd = q->elevator->elevator_data;
	struct cfq_queue *cfqq = crq->cfq_queue;
953 954

	cfqq->next_crq = cfq_find_next_crq(cfqd, cfqq, crq);
955
	cfq_remove_request(crq->request);
Jens Axboe's avatar
Jens Axboe committed
956
	cfqq->on_dispatch[cfq_crq_is_sync(crq)]++;
957
	elv_dispatch_sort(q, crq->request);
Linus Torvalds's avatar
Linus Torvalds committed
958 959 960 961 962 963 964 965
}

/*
 * 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;
966
	struct request *rq;
Linus Torvalds's avatar
Linus Torvalds committed
967 968
	struct cfq_rq *crq;

Jens Axboe's avatar
Jens Axboe committed
969
	if (cfq_cfqq_fifo_expire(cfqq))
Linus Torvalds's avatar
Linus Torvalds committed
970 971
		return NULL;

972
	if (!list_empty(&cfqq->fifo)) {
Jens Axboe's avatar
Jens Axboe committed
973
		int fifo = cfq_cfqq_class_sync(cfqq);
Linus Torvalds's avatar
Linus Torvalds committed
974

975 976 977
		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
978
			cfq_mark_cfqq_fifo_expire(cfqq);
979 980
			return crq;
		}
Linus Torvalds's avatar
Linus Torvalds committed
981 982 983 984 985 986
	}

	return NULL;
}

/*
Jens Axboe's avatar
Jens Axboe committed
987 988 989
 * 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
990
 */
991 992 993 994 995 996 997 998 999 1000
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
1001
static inline void
1002
cfq_set_prio_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
Linus Torvalds's avatar
Linus Torvalds committed
1003
{
1004 1005
	cfqq->slice_end = cfq_prio_to_slice(cfqd, cfqq) + jiffies;
}
Linus Torvalds's avatar
Linus Torvalds committed
1006

1007 1008 1009 1010
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
1011

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

1014
	return 2 * (base_rq + base_rq * (CFQ_PRIO_LISTS - 1 - cfqq->ioprio));
Linus Torvalds's avatar
Linus Torvalds committed
1015 1016
}

1017 1018 1019
/*
 * get next queue for service
 */
1020
static struct cfq_queue *cfq_select_queue(struct cfq_data *cfqd)
Linus Torvalds's avatar
Linus Torvalds committed
1021
{
1022
	unsigned long now = jiffies;
Linus Torvalds's avatar
Linus Torvalds committed
1023 1024
	struct cfq_queue *cfqq;

1025 1026 1027
	cfqq = cfqd->active_queue;
	if (!cfqq)
		goto new_queue;
Linus Torvalds's avatar
Linus Torvalds committed
1028

1029 1030 1031
	/*
	 * slice has expired
	 */
Jens Axboe's avatar
Jens Axboe committed
1032 1033
	if (!cfq_cfqq_must_dispatch(cfqq) && time_after(now, cfqq->slice_end))
		goto expire;
Linus Torvalds's avatar
Linus Torvalds committed
1034

1035 1036 1037 1038 1039 1040
	/*
	 * 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;
1041
	else if (cfq_cfqq_class_sync(cfqq) &&
1042 1043 1044 1045 1046
		 time_before(now, cfqq->slice_end)) {
		if (cfq_arm_slice_timer(cfqd, cfqq))
			return NULL;
	}

Jens Axboe's avatar
Jens Axboe committed
1047
expire:
1048
	cfq_slice_expired(cfqd, 0);
Jens Axboe's avatar
Jens Axboe committed
1049 1050
new_queue:
	cfqq = cfq_set_active_queue(cfqd);
1051
keep_queue:
Jens Axboe's avatar
Jens Axboe committed
1052
	return cfqq;
1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064
}

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
1065 1066

		/*
1067
		 * follow expired path, else get first next available
Linus Torvalds's avatar
Linus Torvalds committed
1068
		 */
1069 1070 1071 1072 1073 1074
		if ((crq = cfq_check_fifo(cfqq)) == NULL)
			crq = cfqq->next_crq;

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

1077 1078
		cfqd->dispatch_slice++;
		dispatched++;
Linus Torvalds's avatar
Linus Torvalds committed
1079

1080 1081 1082 1083
		if (!cfqd->active_cic) {
			atomic_inc(&crq->io_context->ioc->refcount);
			cfqd->active_cic = crq->io_context;
		}
Linus Torvalds's avatar
Linus Torvalds committed
1084

1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108
		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;
}

1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144
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;
}

1145
static int
1146
cfq_dispatch_requests(request_queue_t *q, int force)
1147 1148 1149 1150 1151 1152 1153
{
	struct cfq_data *cfqd = q->elevator->elevator_data;
	struct cfq_queue *cfqq;

	if (!cfqd->busy_queues)
		return 0;

1154 1155 1156 1157
	if (unlikely(force))
		return cfq_forced_dispatch(cfqd);

	cfqq = cfq_select_queue(cfqd);
1158
	if (cfqq) {
1159 1160
		int max_dispatch;

Jens Axboe's avatar
Jens Axboe committed
1161 1162
		cfq_clear_cfqq_must_dispatch(cfqq);
		cfq_clear_cfqq_wait_request(cfqq);
1163 1164
		del_timer(&cfqd->idle_slice_timer);

1165 1166 1167
		max_dispatch = cfqd->cfq_quantum;
		if (cfq_class_idle(cfqq))
			max_dispatch = 1;
Linus Torvalds's avatar
Linus Torvalds committed
1168

1169
		return __cfq_dispatch_requests(cfqd, cfqq, max_dispatch);
Linus Torvalds's avatar
Linus Torvalds committed
1170 1171
	}

1172
	return 0;
Linus Torvalds's avatar
Linus Torvalds committed
1173 1174 1175 1176 1177 1178 1179 1180 1181 1182
}

/*
 * 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)
{
1183 1184 1185
	struct cfq_data *cfqd = cfqq->cfqd;

	BUG_ON(atomic_read(&cfqq->ref) <= 0);
Linus Torvalds's avatar
Linus Torvalds committed
1186 1187 1188 1189 1190

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

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

1194
	if (unlikely(cfqd->active_queue == cfqq))
Jens Axboe's avatar
Jens Axboe committed
1195
		__cfq_slice_expired(cfqd, cfqq, 0);
1196

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

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

1216
		if (__cfqq->key == key && (__p == prio || !prio))
Linus Torvalds's avatar
Linus Torvalds committed
1217 1218 1219 1220 1221 1222 1223
			return __cfqq;
	}

	return NULL;
}

static struct cfq_queue *
Jens Axboe's avatar
Jens Axboe committed
1224
cfq_find_cfq_hash(struct cfq_data *cfqd, unsigned int key, unsigned short prio)
Linus Torvalds's avatar
Linus Torvalds committed
1225
{
Jens Axboe's avatar
Jens Axboe committed
1226
	return __cfq_find_cfq_hash(cfqd, key, prio, hash_long(key, CFQ_QHASH_SHIFT));
Linus Torvalds's avatar
Linus Torvalds committed
1227 1228
}

1229
static void cfq_free_io_context(struct io_context *ioc)
Linus Torvalds's avatar
Linus Torvalds committed
1230
{
1231
	struct cfq_io_context *__cic;
1232 1233
	struct rb_node *n;
	int freed = 0;
Linus Torvalds's avatar
Linus Torvalds committed
1234

1235 1236 1237
	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);
1238
		kmem_cache_free(cfq_ioc_pool, __cic);
1239
		freed++;
Linus Torvalds's avatar
Linus Torvalds committed
1240 1241
	}

1242 1243
	if (atomic_sub_and_test(freed, &ioc_count) && ioc_gone)
		complete(ioc_gone);
Linus Torvalds's avatar
Linus Torvalds committed
1244 1245
}

1246 1247 1248
static void cfq_trim(struct io_context *ioc)
{
	ioc->set_ioprio = NULL;
1249
	cfq_free_io_context(ioc);
1250 1251
}

1252 1253 1254 1255
/*
 * Called with interrupts disabled
 */
static void cfq_exit_single_io_context(struct cfq_io_context *cic)
Linus Torvalds's avatar
Linus Torvalds committed
1256
{
1257
	struct cfq_data *cfqd = cic->key;
1258 1259 1260 1261 1262 1263
	request_queue_t *q;

	if (!cfqd)
		return;

	q = cfqd->queue;
1264 1265 1266 1267 1268

	WARN_ON(!irqs_disabled());

	spin_lock(q->queue_lock);

1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281
	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;
	}
1282

1283
	cic->key = NULL;
1284
	list_del_init(&cic->queue_list);
1285
	spin_unlock(q->queue_lock);
Linus Torvalds's avatar
Linus Torvalds committed
1286 1287
}

1288
static void cfq_exit_io_context(struct io_context *ioc)
Linus Torvalds's avatar
Linus Torvalds committed
1289
{
1290
	struct cfq_io_context *__cic;
Linus Torvalds's avatar
Linus Torvalds committed
1291
	unsigned long flags;
1292
	struct rb_node *n;
1293

Linus Torvalds's avatar
Linus Torvalds committed
1294 1295 1296
	/*
	 * put the reference this task is holding to the various queues
	 */
1297
	spin_lock_irqsave(&cfq_exit_lock, flags);
1298 1299 1300 1301 1302

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

1303
		cfq_exit_single_io_context(__cic);
1304
		n = rb_next(n);
Linus Torvalds's avatar
Linus Torvalds committed
1305 1306
	}

1307
	spin_unlock_irqrestore(&cfq_exit_lock, flags);
Linus Torvalds's avatar
Linus Torvalds committed
1308 1309
}

1310
static struct cfq_io_context *
Al Viro's avatar
Al Viro committed
1311
cfq_alloc_io_context(struct cfq_data *cfqd, gfp_t gfp_mask)
Linus Torvalds's avatar
Linus Torvalds committed
1312
{
1313
	struct cfq_io_context *cic = kmem_cache_alloc(cfq_ioc_pool, gfp_mask);
Linus Torvalds's avatar
Linus Torvalds committed
1314 1315

	if (cic) {
1316
		memset(cic, 0, sizeof(*cic));
1317
		cic->last_end_request = jiffies;
1318
		INIT_LIST_HEAD(&cic->queue_list);